# Closed paths whose steps are roots of unity

Gilbert Labelle¹ and Annie Lacasse²

¹LaCIM et Dép. de Mathématiques, UQAM, Montréal, Québec, Canada

²LIRMM, Montpellier, France

**Abstract.** We give explicit formulas for the number $U_n(N)$ of closed polygonal paths of length $N$ (starting from the origin) whose steps are $n^{th}$ roots of unity, as well as asymptotic expressions for these numbers when $N \to \infty$. We also prove that the sequences $(U_n(N))_{N \ge 0}$ are P-recursive for each fixed $n \ge 1$ and leave open the problem of determining the values of $N$ for which the dual sequences $(U_n(N))_{n \ge 1}$ are P-recursive.

**Résumé.** Nous donnons des formules explicites pour le nombre $U_n(N)$ de chemins polygonaux fermés de longueur $N$ (débutant à l'origine) dont les pas sont des racines $n$-ièmes de l'unité, ainsi que des expressions asymptotiques pour ces nombres lorsque $N \to \infty$. Nous démontrons aussi que les suites $(U_n(N))_{N \ge 0}$ sont P-récursives pour chaque $n \ge 1$ fixé et laissons ouvert le problème de déterminer les valeurs de $N$ pour lesquelles les suites duales $(U_n(N))_{n \ge 1}$ sont P-récursives.

**Keywords:** closed polygonal paths, roots of unity, P-recursive, asymptotics

## 1 Introduction

The subject of random walks is classical and appears in many areas of mathematics, physics and computer science (see, for example, http://en.wikipedia.org/wiki/Random_walks). In this paper we combinatorially analyse a new type of closed random walks in the complex plane — a kind of restricted Brownian motion — whose steps are given by $n^{th}$-roots of unity. For $n \ge 1$, let $\Omega_n = \{1, \omega_n, \omega_n^2, \dots, \omega_n^{n-1}\}$ be the set of all $n$-th roots of unity, where $\omega_n = \exp(2\pi i/n) \in \mathbb{C}$. A polygonal path of length $N$, starting at the origin in the complex plane, whose steps are $n$-th roots of unity can be encoded by the sequence $w = [\omega_n^{k_1}, \dots, \omega_n^{k_N}]$ of its successive steps, $\omega_n^{k_j} \in \Omega_n, j = 1, \dots, N$. For $\nu = 0, \dots, n-1$, let $m_\nu$ be the number of times that $\omega_n^\nu$ appears in $w$. We call the sequence $\vec{m} = [m_0, \dots, m_{n-1}]$ the type of $w$, and write $\vec{m} = \text{type}(w)$. Of course, the path $w$ is closed if and only if if $\omega_n^{k_1} + \dots + \omega_n^{k_N} = 0$ if and only if

$$m_0 + m_1\omega_n + m_2\omega_n^2 + \dots + m_{n-1}\omega_n^{n-1} = 0. \quad (1.1)$$

We call a sequence $\vec{m} = [m_0, m_1, \dots, m_{n-1}] \in \mathbb{N}^n$ admissible if (1.1) is satisfied. Figure 1 shows a closed pentagon made of 18-th roots of unity encoded by $[\omega_{18}^3, \omega_{18}^{11}, \omega_{18}^5, \omega_{18}^{12}, \omega_{18}^{17}]$ and a closed 11-gon made of 14-th roots of unity encoded by $[\omega_{14}^{12}, \omega_{14}^4, \omega_{14}^5, \omega_{14}^7, \omega_{14}^5\omega_{14}^{11}, \omega_{14}^{11}, \omega_{14}^9, \omega_{14}^3, \omega_{14}^{13}]$.

Clearly, the number of closed paths, of length $N$, with admissible type $\vec{m}$ is given by the multinomial coefficient $N!/m_0!m_1!\dots m_{n-1}!$. This implies that the number $U_n(N)$ of closed polygonal paths of
<figure><img src="image_1.png" /><figcaption>Fig. 1: Pentagon and 11-gon made of 18-th and 14-th roots of unity.</figcaption></figure>

length $N$ whose steps are $n$-th roots of unity is given by the formula

$$ U_n(N) = \sum_{\substack{\vec{m}: \text{admissible} \\ m_0 + \cdots + m_{n-1} = N}} \frac{N!}{m_0! m_1! \cdots m_{n-1}!} \quad (1.2) $$

In Section 2, we characterize admissibility and express the numbers $U_n(N)$ as constant term extractions in suitable rational expressions. We also give a formula from which the computation of the numbers $U_n(N)$ can be reduced to the computation of the numbers $U_q(N')$, where $N' \le N$ and $q$ is a suitable divisor of $n$. Section 3 is devoted to an analysis of recursive and asymptotic properties of the numbers $U_n(N)$. Finally, some tables are given.

## 2 Constant term and reduction formulas

To take advantage of formula (1.2) for $U_n(N)$ on a symbolic algebra system, we state first a simple characterization of admissibility for a sequence $\vec{m} \in \mathbb{N}^n$. This is done using the classical cyclotomic polynomials $\Phi_n(z) = \prod(z - \omega)$, where $\omega$ runs through the primitive $n$-th roots of unity. Equivalently, this means that $\omega = \exp(2k\pi i/n)$, where $1 \le k \le n$ and $\text{GCD}(n, k) = 1$. Since $z^n - 1 = \prod_{d|n} \Phi_d(z)$, Moebius inversion implies that $\Phi_n(z) = \prod_{d|n}(x^d - 1)^{\mu(n/d)}$, where $\mu$ denotes the Moebius function. This shows that $\Phi_n(z)$ is a monic polynomial in $\mathbb{Z}[z]$ of degree $\varphi(n)$, the Euler function of $n$. The following very easy, but basic lemma characterizes admissibility.

**Lemma 2.1 (criteria for admissibility).** For $n \ge 1$, the sequence $\vec{m} = [m_0, \dots, m_{n-1}] \in \mathbb{N}^n$ is admissible if and only if the cyclotomic polynomial $\Phi_n(z)$ divides the polynomial

$$ P_{\vec{m}}(z) = m_0 + m_1 z + \cdots + m_{n-1} z^{n-1}. $$

**Proof:** Consider the euclidean division of $P_{\vec{m}}(z)$ by $\Phi_n(z)$ in the ring $\mathbb{Z}[z]$:

$$ P_{\vec{m}}(z) = \Phi_n(z) Q_{\vec{m}}(z) + R_{\vec{m}}(z), \quad (2.1) $$

where $\deg R_{\vec{m}}(z) < \deg \Phi_n(z) = \varphi(n)$. Since $\Phi_n(\omega_n) = 0$ this shows that $\vec{m}$ is admissible if and only if $P_{\vec{m}}(\omega_n) = 0$ if and only if $R_{\vec{m}}(\omega_n) = 0$. But $R_{\vec{m}}(\omega_n) = 0$ if and only if $R_{\vec{m}}(z) = 0$ identically since $\Phi_n(z)$ is known to be the minimal polynomial of any of its roots and $\deg R_{\vec{m}} < \deg \Phi_n$. $\square$
Euclidean division shows that the coefficients of $R_{\vec{m}}(z)$ are $\mathbb{Z}$-linear combinations $l_k(m_0, \dots, m_{n-1})$ of the $m_i$'s. Hence, $\vec{m}$ is admissible if and only if $l_k(m_0, \dots, m_{n-1}) = 0$ for $k = 0, \dots, \varphi(n) - 1$. Table 1, made using the *rem* command in Maple gives the values of the $l_k$'s for $n = 1, \dots, 20$. For example, for $n = 6$, $\varphi(n) = 2$ and using Table 1, formula (1.2) takes the form

$$U_6(N) = \sum_{\substack{m_0+\dots+m_5=N \\ m_0+m_5=m_2+m_3 \\ m_4+m_5=m_1+m_2}} \frac{N!}{m_0!\dots m_5!}$$

Note that, by the multinomial formula, this is equivalent to the following *constant term* formula

$$U_6(N) = \mathrm{CT}((t_1 + t_2 + \frac{t_1}{t_2} + \frac{t_2}{t_1} + t_1^{-1} + t_2^{-1})^N),$$

where $\mathrm{CT}(L(t_1, t_2, \dots))$ denotes the constant term of the full expansion of $L$ as a Laurent series in $t_1, t_2, \dots$. This is generalized as follows.

**Theorem 2.2** There is a *Laurent polynomial*, $\Lambda_n(t_1, \dots, t_{\varphi(n)})$, such that $U_n(N) = \mathrm{CT}(\Lambda_n(t_1, \dots, t_{\varphi(n)}))^N$. Moreover, $\Lambda_n(t_1, \dots, t_{\varphi(n)})$ is computed as follows. Let $m_0 + \dots + m_{n-1}z^{n-1} = \Phi_n(z)Q(z) + R(z)$, where the remainder is $R(z) = \sum_{k=0}^{\varphi(n)-1} l_k(m_0, \dots, m_{n-1})z^k$, with $l_k(m_0, \dots, m_{n-1}) = \sum_{i=0}^{n-1} c_{k,i}m_i$, $c_{k,i} \in \mathbb{Z}$, $k = 0, \dots, \varphi(n) - 1$. Then,

$$\Lambda_n(t_1, \dots, t_{\varphi(n)}) = \sum_{j=0}^{n-1} t_1^{c_{0,j}} t_2^{c_{1,j}} t_3^{c_{2,j}} \dots t_{\varphi(n)}^{c_{\varphi(n)-1,j}}. \qquad (2.2)$$

**Proof:** By the multinomial theorem,

$$\left( \sum_{j=0}^{n-1} t_1^{c_{0,j}} \cdots t_{\varphi(n)}^{c_{\varphi(n)-1,j}} \right)^N \\
= \sum_{m_0+\cdots+m_{n-1}=N} \frac{N!}{m_0! \cdots m_{n-1}!} \left( t_1^{c_{0,0}} \cdots t_{\varphi(n)}^{c_{\varphi(n)-1,0}} \right)^{m_0} \cdots \left( t_1^{c_{0,n-1}} \cdots t_{\varphi(n)}^{c_{\varphi(n)-1,n-1}} \right)^{m_{n-1}} \\
= \sum_{m_0+\cdots+m_{n-1}=N} \frac{N!}{m_0! \cdots m_{n-1}!} t_1^{l_0(m_0, \dots, m_{n-1})} \cdots t_{\varphi(n)}^{l_{\varphi(n)-1}(m_0, \dots, m_{n-1})}.$$

The result follows since the constant term is given by taking the sum of the terms corresponding to the exponents $l_k = 0$ for $k = 0, \dots, \varphi(n) - 1$. $\square$

Table 2 gives the rational functions $\Lambda_n(t_1, \dots, t_{\varphi(n)})$ for $n = 1, \dots, 20$. Let $n = p_1^{\alpha_1} \cdots p_s^{\alpha_s}$ be the canonical decomposition of the integer $n$. By definition, the *radical* of $n$ is the square-free integer $q = \mathrm{rad}(n) = p_1 \cdots p_s$ consisting of the product of the $p_i$'s. The computation of the cyclotomic polynomial $\Phi_n(z)$ is greatly simplified by making use of the well-known reduction formula

$$\Phi_n(z) = \Phi_q(z^{n/q}), \quad q = \mathrm{rad}(n). \qquad (2.3)$$

This implies that the computation of the exponential generating function of the sequence $(U_n(N))_{N \ge 0}$ is reduced to that of $(U_q(N))_{N \ge 0}$ as follows.
**Proposition 2.3 (reduction formula for $U_n(N)$).** Let $n \ge 1$ and $q = \text{rad}(n)$. Then,

$$ \sum_{N \ge 0} U_n(N) \frac{X^N}{N!} = \left( \sum_{N \ge 0} U_q(N) \frac{X^N}{N!} \right)^{n/q} . \qquad (2.4) $$

**Proof:** Using the remainder function, we have by linearity,

$$ R_{\vec{m}}(z) = \text{rem}(P_{\vec{m}}(z), \Phi_n(z)) = \sum_{k=0}^{n-1} m_k \text{rem}(z^k, \Phi_n(z)). \qquad (2.5) $$

Now, for $0 \le \nu \le q - 1$, consider the euclidean division

$$ z^{\nu} = \Phi_{q}(z)Q_{\nu}(z) + \rho_{\nu}(z), \qquad (2.6) $$

where $\rho_\nu(z) = \text{rem}(z^\nu, \Phi_q(z))$. The substitution $z \to z^{n/q}$ in (2.6) followed by a multiplication by $z^r$ gives, using (2.3), $z^{\nu n/q+r} = \Phi_q(z^{n/q})z^r Q_\nu(z^{n/q}) + z^r \rho_\nu(z^{n/q}) = \Phi_n(z)z^r Q_\nu(z^{n/q}) + z^r \rho_\nu(z^{n/q})$. Let $k = \nu n/q + r$, where $0 \le r < n/q$. Then,

$$ \deg z^r \rho_\nu(z^{n/q}) = r + \frac{n}{q} \deg \rho_\nu(z) \le r + \frac{n}{q}(\varphi(q) - 1) = r + \varphi(n) - \frac{n}{q} < \varphi(n). $$

This implies that $\text{rem}(z^k, \Phi_n(z)) = z^r \rho_\nu(z^{n/q})$. Substituting this into (2.5) and collecting terms, we find that the $\varphi(n)$ conditions for admissibility, $[l_k(m_0, m_1, \dots, m_{n-1}) = 0]_{0 \le k \le \varphi(n)-1}$, split into $n/q$ blocks of $\varphi(q)$ conditions, $[l_i(m_j, m_{\frac{n}{q}+j}, m_{2\frac{n}{q}+j}, \dots, m_{(q-1)\frac{n}{q}+j}) = 0]_{0 \le i \le \varphi(q)-1}$, $0 \le j \le \frac{n}{q} - 1$, from which (2.4) follows. $\square$

Table 3 gives the numerical values of $U_n(N)$ for $1 \le n \le 20$ and $0 \le N \le 20$.

## 3 Analysis of the sequences

Let us say that a path is *normalized* if its first step is the complex number 1 (i.e. the path starts horizontally along the positive real axis). Each normalized path $[1, \omega_n^{\nu_2}, \dots, \omega_n^{\nu_N}]$ generates, by rotation, $n$ distinct paths $\omega_n^k[1, \omega_n^{\nu_2}, \dots, \omega_n^{\nu_N}] = [\omega_n^k, \omega_n^{k+\nu_2}, \dots, \omega_n^{k+\nu_N}]$, $k = 0, 1, \dots, n-1$. This implies that $n$ divides $U_n(N)$ for every $n \ge 1$ and $N \ge 1$. As Tables 1 and 2 indicate, the structure of the sequence $(U_n(N))_{N \ge 0}$ heavily depend on the arithmetical nature of $n$. For example, let $n = p$ be a prime number. Then for such values of $n$, admissibility for a vector $\vec{m} \in \mathbb{N}^p$ means that $m_0 = m_1 = \dots = m_{p-1}$ since, in this case, $\Phi_p(z) = 1 + z + \dots + z^{p-1}$ and $R_{\vec{m}}(z) = (m_0 - m_{p-1}) + (m_1 - m_{p-1})z + \dots + (m_{p-2} - m_{p-1})z^{p-2}$, (see Table 1, for example). Formula (1.2) then takes the form

$$ U_p(N) = \frac{N!}{\left(\frac{N}{p}\right)!p} \quad \text{if } p \mid N, 0 \text{ otherwise.} \qquad (3.1) $$

Note that when $p = 2$, (3.1) corresponds to the classical central binomial coefficients enumerating one-dimensional closed lattice paths of length $N$. When $p = 3$, (3.1) corresponds to the De Bruijn numbers
(sequence A006480 in Sloane-Plouffe encyclopedia [Sloane(2010)]). For prime powers $n = p^{\alpha}$, we have by Proposition 2.3,

$$ \sum_{N \ge 0} U_{p^\alpha}(N) \frac{X^N}{N!} = \left( \sum_{k \ge 0} \frac{X^{kp}}{k!p} \right)^{p^{\alpha-1}} \quad (3.2) $$

since, in this case $q = p$. Note that when $n = 8 = 2^3$, then $U_8(N)$ is the number of 4-dimensional closed lattice paths in $\mathbb{Z}^4$ of length $N$ starting at the origin (see sequence A039699 in Sloane). The reader can check that, more generally, $U_{2\alpha}(N)$ is the number of closed lattice paths in $\mathbb{Z}^{2\alpha-1}$ of length $N$ starting at the origin. Interestingly enough, for any other dimension $d \ne 2^{\alpha-1}$, such a connection betweens lattice paths in $\mathbb{Z}^d$ and plane paths whose steps are roots of unity does not exist.

When $n$ is not a prime power, the situation is more delicate. For example, if $n = 6$, then, using the Maple package GFUN [Salvy and Zimmermann(1994)], it can be seen that $(U_n(N))_{N \ge 0}$ satisfies the following linear recurrence with polynomial coefficients,

$$ (N+3)^2 U_6(N+3) = (N+2)(N+3)U_6(N+2) + 24(N+2)^2 U_6(N+1) + 36(N+1)(N+2)U_6(N) \quad (3.3) $$

with initial conditions $U_6(0) = 1$, $U_6(1) = 0$, $U_6(2) = 6$. Such sequences are called polynomially recursive (P-recursive for short) and are characterized by the fact that their (ordinary or exponential) generating series are D-finite (i.e. satisfy a linear differential equation with polynomial coefficients). As a consequence, P-recursive sequences are closed under many operations including linear combinations, pointwise and Cauchy products [Stanley(1980)]. Moreover their asymptotic estimates, as $N \to \infty$, are well behaved. In our context, the general situation is summarized by Theorem 3.2. below. We need first the following technical lemma.

**Lemma 3.1** Let $\vec{t} = (t_1, \dots, t_{\varphi(n)}) \in \mathbb{C}^{\varphi(n)}$. Then the Laurent polynomial $\Lambda_n$ satisfies

$$ \max_{\substack{|t_\nu|=1 \\ 1 \le \nu \le \varphi(n)}} |\Lambda_n(\vec{t})| = n. \quad (3.4) $$

Moreover, if $n = p^{\alpha}$, a prime power, then the maximum value (3.4) is attained precisely at the $p$ distinct points $(e^{2\pi i \nu/p}, \dots, e^{2\pi i \nu/p})$, $\nu = 0, \dots, p-1$ and we have $\Lambda_n(e^{2\pi i \nu/p}, \dots, e^{2\pi i \nu/p}) = ne^{2\pi i \nu/p}$. If $n$ is not a prime power, then the maximum value (3.4) is attained only at the point $(1, \dots, 1)$ and we have $\Lambda_n(1, \dots, 1) = n$.

**Proof:** By Theorem 2.2, $\Lambda_n$ can be written as a sum of $n$ terms,

$$ \Lambda_n(\vec{t}) = t_1 + \dots + t_{\varphi(n)} + \Gamma_n(\vec{t}), \quad (3.5) $$

where $\Gamma_n$ is a sum of $n - \varphi(n)$ unitary Laurent monomials in $t_1, \dots, t_{\varphi(n)}$. Each of the $n$ terms in $\Lambda_n$ has modulus 1 when $|t_\nu| = 1$, $\nu = 1, \dots, \varphi(n)$. Hence (3.4) follows from the triangular inequality and the fact that $\Lambda_n(1, \dots, 1) = n$. Note that the maximum value in (3.4) is attained only at points $\vec{t}^* = (t_1^*, \dots, t_{\varphi(n)}^*)$ for which the $n$ monomials take a common value, $e^{i\theta^*}$, say. In particular, from (3.5), we must have $t_1^* = t_2^* = \dots = t_{\varphi(n)}^* = e^{i\theta^*}$. We consider two cases:

(i) if $n = p^{\alpha}$, then it can be checked that each term in $\Gamma_n$ has total degree $-(p-1)$. This implies that $e^{i\theta^*} = e^{-i(p-1)\theta^*}$. That is, $e^{i\theta^*}$ is a $p$-th root of unity: $e^{2\pi i \nu/p}$, $\nu = 0, \dots, p-1$;
(ii) if $n \neq p^{\alpha}$, the situation is more delicate. If we can show that at least one of the terms in $\Gamma_n$ has total degree 0, then the maximal value in (3.4) will be attained only at the point $(1, \dots, 1)$, since this would imply that $e^{i\theta^*} = (e^{i\theta^*})^0 = 1$. The existence of such a 0-degree term is proved as follows. By (2.2), the general term $t_1^{c_{0,j}} t_2^{c_{1,j}} \dots t_{\varphi(n)}^{c_{\varphi(n)-1,j}}$ has total degree $\sum_{k=0}^{\varphi(n)-1} c_{k,j}$. When $j = \varphi(n)$, this total degree is 0. To see this, note that $\sum_{k=0}^{\varphi(n)-1} c_{k,j}z^k = \text{rem}(z^j, \Phi_n(z))$. Taking $j = \varphi(n)$, $z = 1$, this gives $\sum_{k=0}^{\varphi(n)-1} c_{k,\varphi(n)} = \text{rem}(z^{\varphi(n)}, \Phi_n(z))|_{z=1} = (z^{\varphi(n)} - \Phi_n(z))|_{z=1} = 0$, since $\Phi_n(1) = 1$ when $n \neq p^{\alpha}$.

□

**Theorem 3.2** For any $n > 1$, we have an asymptotic estimate of the form

$$U_n(N) \sim a_n \frac{n^N}{N^{\frac{1}{2}\varphi(n)}} \left( 1 + \frac{b_{1,n}}{N} + \frac{b_{2,n}}{N^2} + \dots \right), \quad \text{as } N \to \infty, \quad (3.6)$$

where $a_n, b_{j,n}$ are independent of $N$. When $n = p^{\alpha}$ is a prime power, then $N$ must be a multiple of $p$ as it goes to infinity in (3.6). More explicitly, the leading coefficient $a_n$ is given by

$$a_n = \begin{cases} \frac{(n/2\pi)^{\frac{1}{2}\varphi(n)}}{\sqrt{\prod_{p|n} p^{\varphi(n)/(p-1)}}} & \text{if } n \text{ is not a prime power,} \\ \frac{p \cdot (n/2\pi)^{\frac{1}{2}\varphi(n)}}{\sqrt{\prod_{p|n} p^{\varphi(n)/(p-1)}}} & \text{if } n = p^{\alpha} \text{ is a prime power.} \end{cases}$$

For each $n \ge 1$, the sequence $(U_n(N))_{N \ge 0}$ is P-recursive but is not algebraic when $n > 2$.

**Proof:** In order to establish the asymptotic estimate (3.6), first note that the constant term extraction $U_n(N) = \text{CT}(\Lambda_n(t_1, \dots, t_{\varphi(n)})^N)$ can be expressed as the multiple integral

$$U_n(N) = \frac{1}{(2\pi)^{\varphi(n)}} \int \dots \int_{(-\pi, \pi]^{\varphi(n)}} \Lambda_n(e^{iu_1}, \dots, e^{iu_{\varphi(n)})^N} du_1 \dots du_{\varphi(n)} \quad (3.7)$$

which is the average value of $\Lambda_n^N$ over the $\varphi(n)$-dimensional torus $\{(t_1, \dots, t_{\varphi(n)}) \in \mathbb{C}^{\varphi(n)} | |t_{\nu}| = 1, \nu = 1, \dots, \varphi(n)\}$. Now by Theorem 2.2,

$$L_n(\vec{u}) := \Lambda_n(e^{iu_1}, \dots, e^{iu_{\varphi(n)}}) = \sum_{j=0}^{n-1} e^{i\lambda_j(\vec{u})}, \quad (3.8)$$

where $\lambda_j(\vec{u}) = \sum_{k=0}^{\varphi(n)-1} c_{k,j} u_{k+1}$ is a real-valued linear combination of $u_1, \dots, u_k, 0 \le j \le \varphi(n)-1$. By the triangular inequality, $|L_n(\vec{u})| \le n$ for every $\vec{u} \in (-\pi, \pi]^{\varphi(n)}$. To obtain the asymptotic estimate of (3.6) it suffices to approximate (3.7) by a gaussian distribution around each point $\vec{u}^* = (u_1^*, \dots, u_{\varphi(n)}^*) \in (-\pi, \pi]^{\varphi(n)}$ for which the maximum value $|L_n(\vec{u}^*)| = |ne^{i\theta^*}| = n$ is attained. This is Laplace's method [De Bruijn(1981)]. By Lemma 3.1,

(i) if $n \neq p^{\alpha}$, then $\vec{u}^* = \vec{0}$ is the only point in $(-\pi, \pi]^{\varphi(n)}$ for which $|L_n(\vec{u}^*)| = n$. In fact $\theta^* = 0$;

(ii) if $n = p^{\alpha}$, then there are exactly $p$ possible values of $u^*$ for which $|L_n(u^*)| = n$. In fact $\theta^* = 2\nu\pi/p \mod 2\pi \in (-\pi, \pi], \nu = 0, \dots, p-1$.
We conclude by estimating (3.7) by a sum of moments of gaussian distributions in the following way:

$$U_n(N) \sim \frac{n^N}{(2\pi)^\varphi(n)} \sum_{L_n(\vec{u}^*)=n e^{i\theta^*}} e^{iN\theta^*} \int_{-\infty}^{+\infty} \cdots \int_{-\infty}^{+\infty} e^{-\frac{N}{2n}Q^*(\vec{u}-\vec{u}^*)} H^*(\vec{u}-\vec{u}^*)^N du_1 \cdots du_{\varphi(n)},$$

where, for each $\vec{u}^*$ such that $L_n(\vec{u}^*) = n e^{i\theta^*}$,

$$\frac{1}{n} L_n(\vec{u}) = e^{i\theta^*} \left( 1 - \frac{1}{2n} Q^*(\vec{u} - \vec{u}^*) + O(\|\vec{u} - \vec{u}^*\|^3) \right) = e^{i\theta^*} e^{-\frac{1}{2n} Q^*(\vec{u} - \vec{u}^*)} H^*(\vec{u} - \vec{u}^*), \quad (3.9)$$

where $Q^*(\vec{v})$ is the positive definite quadratic form associated to the symmetric $\varphi(n) \times \varphi(n)$ matrix $K = CC^T$ in which $C = [c_{k,j}]_{0 \le k \le \varphi(n)-1, 0 \le j \le n-1}$, where the $c_{k,j}$'s are defined by (2.2) and $H^*(\vec{v}) = 1 + O(\|\vec{v}\|^3)$. It turns out that $\det(K) = \prod_{p|n} p^{\varphi(n)/(p-1)}$, which is a consequence of the known fact that the absolute value of the discriminant of $\Phi_n(z)$ is equal to $n^{\varphi(n)} \prod_{p|n} p^{\varphi(n)/(p-1)}$, for $n > 2$.

The P-recursivity of $(U_n(N))_{N \ge 0}$ is established as follows. Fix $n \ge 1$ and let $k = \varphi(n)$. We shall show that the series

$$\sum_{N \ge 0} U_n(N) X^N = \mathrm{CT}_{t_1, \dots, t_k} \frac{1}{1 - X \Lambda_n(t_1, \dots, t_k)} \quad (3.10)$$

is D-finite in $X$ where $\mathrm{CT}_{t_1, \dots, t_k}$ means constant term extraction relative to the variables $t_1, \dots, t_k$. First, fix integers $m_1 > 0, \dots, m_k > 0$ in such a way that $t_1^{m_1} \dots t_k^{m_k} \Lambda_n(t_1, \dots, t_k)$ is a polynomial in $t_1, \dots, t_k$. The rational function

$$f(t_1, \dots, t_k, X) = \frac{1}{1 - t_1^{m_1} \dots t_k^{m_k} X \Lambda_n(t_1, \dots, t_k)} = \sum_{n_1, \dots, n_k, N \ge 0} a(n_1, \dots, n_k, N) t_1^{n_1} \dots t_k^{n_k} X^N \quad (3.11)$$

is obviously D-finite in the variables $t_1, \dots, t_k, X$. By Theorem 2.2, the numbers $U_n(N)$ can be expressed as the following coefficient extraction in $f(t_1, \dots, t_k, X)$:

$$U_n(N) = [t_1^{m_1 N} \dots t_k^{m_k N} X^N] f(t_1, \dots, t_k, X).$$

Hence, by (3.10),

$$\sum_{N \ge 0} U_n(N) X^N = \sum_{N \ge 0} a(m_1 N, \dots, m_k N, N) X^N. \quad (3.12)$$

Consider now the algebraic, hence D-finite, series

$$g(t_1, \dots, t_k, X) = \sum_{n_1, \dots, n_k, N \ge 0} b(n_1, \dots, n_k, N) t_1^{n_1} \dots t_k^{n_k} X^N,$$

where $b(n_1, \dots, n_k, N) = a(m_1 n_1, \dots, m_k n_k, N)$. Formula (3.12) shows that

$$\sum_{N \ge 0} U_n(N) X^N = \sum_{N \ge 0} b(N, \dots, N, N) X^N$$

which is a (full) diagonal of $g(t_1, \dots, t_k, X)$. We conclude using the fact that any diagonal of a D-finite series is also D-finite, a result due to Lipshitz [Lipshitz(1988)]. The non algebraicity of $(U_n(N))_{N \ge 0}$,
for each $n > 2$, follows from the fact that $\varphi(n)$ is even and the dominant term of the asymptotic formula contains $N^{-\text{positive integer}}$. This is incoherent with Puiseux expansion around an algebraic singularity. $\square$

A better control of the coefficients $b_{j,n}$ can be achieved by a smooth local change of variables, $\vec{u} = \vec{u}^* + \vec{g}(\vec{w})$, $\vec{g}(\vec{0}) = \vec{0}$ in (3.9) such that $\frac{1}{n}L_n(\vec{u}) = e^{i\theta^*} e^{-\frac{1}{2n}Q^*(\vec{w})}$. This is always possible by Morse Lemma [Morse(1925)]. The first terms of the asymptotic estimates of Theorem 3.2 are given in Table 4 for $n = 1, \dots, 20$.

**Corollary 3.3** If $n$ is not a prime power, then $\exists N_0 = N_0(n)$ such that $U_n(N) > 0$ for $N \ge N_0$. $\square$

<figure><img src="image_2.png" /></figure>

The sequences $(U_n(N))_{N \ge 0}$, $n = 1, 2, \dots$, can be considered in a dual way: for each fixed $N$, one can consider the sequence $(\tilde{U}_n(N))_{n \ge 1}$ by reading each column of Table 3. The first five of these dual sequences, $(U_n(0))_{n \ge 1}$, $(U_n(1))_{n \ge 1}$, \dots, $(U_n(4))_{n \ge 1}$, are P-recursive. The fifth one, $(U_n(4))_{n \ge 1}$, can be described as follows: $U_n(4) = 3n(n-1)\chi(2|n)$, where $\chi(T(n)) = 1$ if $T(n)$ is true and 0 otherwise. This can be checked by noting that closed paths of length 4 whose steps are $n^{\text{th}}$ roots of unity are (possibly degenerated and non-convex) rhombuses. Following extensive computations we conjecture that $(U_n(5))_{n \ge 1}$ is also P-recursive and is of the form $U_n(5) = 24n\chi(5|n) + 20n(n-3)\chi(6|n)$. We leave open the problem of determining the values of $N$ for which $(U_n(N))_{n \ge 1}$ is P-recursive.

**Acknowledgements.** The authors wish to thank B. Salvy for his assistance in the proof of the second part of Theorem 3.2, J. Tremblay for his LaTeX/Maple help, and a referee for his constructive suggestions.

## References

[De Bruijn(1981)] N. G. De Bruijn. *Asymptotic methods in analysis*. New York Dover Publications, 1981. ISBN 0486642216.

[Lipshitz(1988)] L. Lipshitz. The diagonal of a D-finite power series is D-finite. *Journal of Algebra*, 113: 373–378, 1988.

[Morse(1925)] M. Morse. Relations between the critical points of a real function of $n$ independent variables. *Trans. Amer. Math. Soc.*, 27:345–396, 1925.

[Salvy and Zimmermann(1994)] B. Salvy and P. Zimmermann. Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable. *ACM Transactions on Mathematical Software*, 20(2):163–177, 1994.

[Sloane(2010)] N. J. A. Sloane. *The On-Line Encyclopedia of Integer Sequences*. Enlarged edition, 2010. Published electronically at http://oeis.org/classic/index.html.

[Stanley(1980)] R. P. Stanley. Differentiably finite power series. *Europ. J. Combinatorics*, 1:175–188, 1980.
<table><caption>Tab. 1: The linear combinations $(l_k(\vec{m}))_{0 \le k \le \varphi(n)-1}$ for admissibility, $n = 1, \dots, 20$.</caption><thead><tr><th>n</th><th>Linear combinations for admissibility</th></tr></thead><tbody><tr><td>1</td><td>[m<sub>0</sub>]</td></tr><tr><td>2</td><td>[m<sub>0</sub> - m<sub>1</sub>]</td></tr><tr><td>3</td><td>[m<sub>0</sub> - m<sub>2</sub>, m<sub>1</sub> - m<sub>2</sub>]</td></tr><tr><td>4</td><td>[m<sub>0</sub> - m<sub>2</sub>, m<sub>1</sub> - m<sub>3</sub>]</td></tr><tr><td>5</td><td>[m<sub>0</sub> - m<sub>4</sub>, m<sub>1</sub> - m<sub>4</sub>, m<sub>2</sub> - m<sub>4</sub>, m<sub>3</sub> - m<sub>4</sub>]</td></tr><tr><td>6</td><td>[m<sub>0</sub> - m<sub>2</sub> - m<sub>3</sub> + m<sub>5</sub>, m<sub>1</sub> + m<sub>2</sub> - m<sub>4</sub> - m<sub>5</sub>]</td></tr><tr><td>7</td><td>[m<sub>0</sub> - m<sub>6</sub>, m<sub>1</sub> - m<sub>6</sub>, m<sub>2</sub> - m<sub>6</sub>, m<sub>3</sub> - m<sub>6</sub>, m<sub>4</sub> - m<sub>6</sub>, m<sub>5</sub> - m<sub>6</sub>]</td></tr><tr><td>8</td><td>[m<sub>0</sub> - m<sub>4</sub>, m<sub>1</sub> - m<sub>5</sub>, m<sub>2</sub> - m<sub>6</sub>, m<sub>3</sub> - m<sub>7</sub>]</td></tr><tr><td>9</td><td>[m<sub>0</sub> - m<sub>6</sub>, m<sub>1</sub> - m<sub>7</sub>, m<sub>2</sub> - m<sub>8</sub>, m<sub>3</sub> - m<sub>6</sub>, m<sub>4</sub> - m<sub>7</sub>, m<sub>5</sub> - m<sub>8</sub>]</td></tr><tr><td>10</td><td>[m<sub>0</sub> - m<sub>4</sub> - m<sub>5</sub> + m<sub>9</sub>, m<sub>1</sub> + m<sub>4</sub> - m<sub>6</sub> - m<sub>9</sub>, m<sub>2</sub> - m<sub>4</sub> - m<sub>7</sub> + m<sub>9</sub>, m<sub>3</sub> + m<sub>4</sub> - m<sub>8</sub> - m<sub>9</sub>]</td></tr><tr><td>11</td><td>[m<sub>0</sub> - m<sub>10</sub>, m<sub>1</sub> - m<sub>10</sub>, m<sub>2</sub> - m<sub>10</sub>, m<sub>3</sub> - m<sub>10</sub>, m<sub>4</sub> - m<sub>10</sub>, m<sub>5</sub> - m<sub>10</sub>, m<sub>6</sub> - m<sub>10</sub>, m<sub>7</sub> - m<sub>10</sub>, m<sub>8</sub> - m<sub>10</sub>, m<sub>9</sub> - m<sub>10</sub>]</td></tr><tr><td>12</td><td>[m<sub>0</sub> - m<sub>4</sub> - m<sub>6</sub> + m<sub>10</sub>, m<sub>1</sub> - m<sub>5</sub> - m<sub>7</sub> + m<sub>11</sub>, m<sub>2</sub> + m<sub>4</sub> - m<sub>8</sub> - m<sub>10</sub>, m<sub>3</sub> + m<sub>5</sub> - m<sub>9</sub> - m<sub>11</sub>]</td></tr><tr><td>13</td><td>[m<sub>0</sub> - m<sub>12</sub>, m<sub>1</sub> - m<sub>12</sub>, m<sub>2</sub> - m<sub>12</sub>, m<sub>3</sub> - m<sub>12</sub>, m<sub>4</sub> - m<sub>12</sub>, m<sub>5</sub> - m<sub>12</sub>, m<sub>6</sub> - m<sub>12</sub>, m<sub>7</sub> - m<sub>12</sub>, m<sub>8</sub> - m<sub>12</sub>, m<sub>9</sub> - m<sub>12</sub>, m<sub>10</sub> - m<sub>12</sub>, m<sub>11</sub> - m<sub>12</sub>]</td></tr><tr><td>14</td><td>[m<sub>0</sub> - m<sub>6</sub> - m<sub>7</sub> + m<sub>13</sub>, m<sub>1</sub> + m<sub>6</sub> - m<sub>8</sub> - m<sub>13</sub>, m<sub>2</sub> - m<sub>6</sub> - m<sub>9</sub> + m<sub>13</sub>, m<sub>3</sub> + m<sub>6</sub> - m<sub>10</sub> - m<sub>13</sub>, m<sub>4</sub> - m<sub>6</sub> - m<sub>11</sub> + m<sub>13</sub>, m<sub>5</sub> + m<sub>6</sub> - m<sub>12</sub> - m<sub>13</sub>]</td></tr><tr><td>15</td><td>[m<sub>0</sub> - m<sub>8</sub> - m<sub>9</sub> - m<sub>10</sub> + m<sub>13</sub> + m<sub>14</sub>, m<sub>1</sub> + m<sub>8</sub> - m<sub>11</sub> - m<sub>13</sub>, m<sub>2</sub> + m<sub>9</sub> - m<sub>12</sub> - m<sub>14</sub>, m<sub>3</sub> - m<sub>8</sub> - m<sub>9</sub> + m<sub>14</sub>, m<sub>4</sub> + m<sub>8</sub> - m<sub>13</sub> - m<sub>14</sub>, m<sub>5</sub> - m<sub>8</sub> - m<sub>10</sub> + m<sub>13</sub>, m<sub>6</sub> - m<sub>9</sub> - m<sub>11</sub> + m<sub>14</sub>, m<sub>7</sub> + m<sub>8</sub> + m<sub>9</sub> - m<sub>12</sub> - m<sub>13</sub> - m<sub>14</sub>]</td></tr><tr><td>16</td><td>[m<sub>0</sub> - m<sub>8</sub>, m<sub>1</sub> - m<sub>9</sub>, m<sub>2</sub> - m<sub>10</sub>, m<sub>3</sub> - m<sub>11</sub>, m<sub>4</sub> - m<sub>12</sub>, m<sub>5</sub> - m<sub>13</sub>, m<sub>6</sub> - m<sub>14</sub>, m<sub>7</sub> - m<sub>15</sub>]</td></tr><tr><td>17</td><td>[m<sub>0</sub> - m<sub>16</sub>, m<sub>1</sub> - m<sub>16</sub>, m<sub>2</sub> - m<sub>16</sub>, m<sub>3</sub> - m<sub>16</sub>, m<sub>4</sub> - m<sub>16</sub>, m<sub>5</sub> - m<sub>16</sub>, m<sub>6</sub> - m<sub>16</sub>, m<sub>7</sub> - m<sub>16</sub>, m<sub>8</sub> - m<sub>16</sub>, m<sub>9</sub> - m<sub>16</sub>, m<sub>10</sub> - m<sub>16</sub>, m<sub>11</sub> - m<sub>16</sub>, m<sub>12</sub> - m<sub>16</sub>, m<sub>13</sub> - m<sub>16</sub>, m<sub>14</sub> - m<sub>16</sub>, m<sub>15</sub> - m<sub>16</sub>]</td></tr><tr><td>18</td><td>[m<sub>0</sub> - m<sub>6</sub> - m<sub>9</sub> + m<sub>15</sub>, m<sub>1</sub> - m<sub>7</sub> - m<sub>10</sub> + m<sub>16</sub>, m<sub>2</sub> - m<sub>8</sub> - m<sub>11</sub> + m<sub>17</sub>, m<sub>3</sub> + m<sub>6</sub> - m<sub>12</sub> - m<sub>15</sub>, m<sub>4</sub> + m<sub>7</sub> - m<sub>13</sub> - m<sub>16</sub>, m<sub>5</sub> + m<sub>8</sub> - m<sub>14</sub> - m<sub>17</sub>]</td></tr><tr><td>19</td><td>[m<sub>0</sub> - m<sub>18</sub>, m<sub>1</sub> - m<sub>18</sub>, m<sub>2</sub> - m<sub>18</sub>, m<sub>3</sub> - m<sub>18</sub>, m<sub>4</sub> - m<sub>18</sub>, m<sub>5</sub> - m<sub>18</sub>, m<sub>6</sub> - m<sub>18</sub>, m<sub>7</sub> - m<sub>18</sub>, m<sub>8</sub> - m<sub>18</sub>, m<sub>9</sub> - m<sub>18</sub>, m<sub>10</sub> - m<sub>18</sub>, m<sub>11</sub> - m<sub>18</sub>, m<sub>12</sub> - m<sub>18</sub>, m<sub>13</sub> - m<sub>18</sub>, m<sub>14</sub> - m<sub>18</sub>, m<sub>15</sub> - m<sub>18</sub>, m<sub>16</sub> - m<sub>18</sub>, m<sub>17</sub> - m<sub>18</sub>]</td></tr><tr><td>20</td><td>[m<sub>0</sub> - m<sub>8</sub> - m<sub>10</sub> + m<sub>18</sub>, m<sub>1</sub> - m<sub>9</sub> - m<sub>11</sub> + m<sub>19</sub>, m<sub>2</sub> + m<sub>8</sub> - m<sub>12</sub> - m<sub>18</sub>, m<sub>3</sub> + m<sub>9</sub> - m<sub>13</sub> - m<sub>19</sub>, m<sub>4</sub> - m<sub>8</sub> - m<sub>14</sub> + m<sub>18</sub>, m<sub>5</sub> - m<sub>9</sub> - m<sub>15</sub> + m<sub>19</sub>, m<sub>6</sub> + m<sub>8</sub> - m<sub>16</sub> - m<sub>18</sub>, m<sub>7</sub> + m<sub>9</sub> - m<sub>17</sub> - m<sub>19</sub>]</td></tr></tbody></table>
<table><caption>**Tab. 2:** The Laurent polynomials $\Lambda_n$ for $n = 1, \dots, 20$.</caption>
  <thead>
    <tr>
      <th>n</th>
      <th>&Lambda;<sub>n</sub>(t<sub>1</sub>, ..., t<sub>&varphi;(n)</sub>)</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>1</td>
      <td>t<sub>1</sub></td>
    </tr>
    <tr>
      <td>2</td>
      <td>(t<sub>1</sub> + t<sub>1</sub><sup>-1</sup>)</td>
    </tr>
    <tr>
      <td>3</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + <sup>1</sup>&frasl;<sub>t<sub>1</sub>t<sub>2</sub></sub>)</td>
    </tr>
    <tr>
      <td>4</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + t<sub>1</sub><sup>-1</sup> + t<sub>2</sub><sup>-1</sup>)</td>
    </tr>
    <tr>
      <td>5</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + t<sub>3</sub> + t<sub>4</sub> + <sup>1</sup>&frasl;<sub>t<sub>1</sub>t<sub>2</sub>t<sub>3</sub>t<sub>4</sub></sub>)</td>
    </tr>
    <tr>
      <td>6</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + <sup>t<sub>1</sub></sup>&frasl;<sub>t<sub>2</sub></sub> + <sup>t<sub>2</sub></sup>&frasl;<sub>t<sub>1</sub></sub> + t<sub>1</sub><sup>-1</sup> + t<sub>2</sub><sup>-1</sup>)</td>
    </tr>
    <tr>
      <td>7</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + t<sub>3</sub> + t<sub>4</sub> + t<sub>5</sub> + t<sub>6</sub> + <sup>1</sup>&frasl;<sub>t<sub>1</sub>t<sub>2</sub>t<sub>3</sub>t<sub>4</sub>t<sub>5</sub>t<sub>6</sub></sub>)</td>
    </tr>
    <tr>
      <td>8</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + t<sub>3</sub> + t<sub>4</sub> + t<sub>1</sub><sup>-1</sup> + t<sub>2</sub><sup>-1</sup> + t<sub>3</sub><sup>-1</sup> + t<sub>4</sub><sup>-1</sup>)</td>
    </tr>
    <tr>
      <td>9</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + t<sub>3</sub> + t<sub>4</sub> + t<sub>5</sub> + t<sub>6</sub> + <sup>1</sup>&frasl;<sub>t<sub>1</sub>t<sub>4</sub></sub> + <sup>1</sup>&frasl;<sub>t<sub>2</sub>t<sub>5</sub></sub> + <sup>1</sup>&frasl;<sub>t<sub>3</sub>t<sub>6</sub></sub>)</td>
    </tr>
    <tr>
      <td>10</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + t<sub>3</sub> + t<sub>4</sub> + <sup>t<sub>1</sub>t<sub>3</sub></sup>&frasl;<sub>t<sub>2</sub>t<sub>4</sub></sub> + <sup>t<sub>2</sub>t<sub>4</sub></sup>&frasl;<sub>t<sub>1</sub>t<sub>3</sub></sub> + t<sub>1</sub><sup>-1</sup> + t<sub>2</sub><sup>-1</sup> + t<sub>3</sub><sup>-1</sup> + t<sub>4</sub><sup>-1</sup>)</td>
    </tr>
    <tr>
      <td>11</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + t<sub>3</sub> + t<sub>4</sub> + t<sub>5</sub> + t<sub>6</sub> + t<sub>7</sub> + t<sub>8</sub> + t<sub>9</sub> + t<sub>10</sub> + <sup>1</sup>&frasl;<sub>t<sub>1</sub>t<sub>2</sub>t<sub>3</sub>t<sub>4</sub>t<sub>5</sub>t<sub>6</sub>t<sub>7</sub>t<sub>8</sub>t<sub>9</sub>t<sub>10</sub></sub>)</td>
    </tr>
    <tr>
      <td>12</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + t<sub>3</sub> + t<sub>4</sub> + <sup>t<sub>1</sub></sup>&frasl;<sub>t<sub>3</sub></sub> + <sup>t<sub>3</sub></sup>&frasl;<sub>t<sub>1</sub></sub> + <sup>t<sub>2</sub></sup>&frasl;<sub>t<sub>4</sub></sub> + <sup>t<sub>4</sub></sup>&frasl;<sub>t<sub>2</sub></sub> + t<sub>1</sub><sup>-1</sup> + t<sub>2</sub><sup>-1</sup> + t<sub>3</sub><sup>-1</sup> + t<sub>4</sub><sup>-1</sup>)</td>
    </tr>
    <tr>
      <td>13</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + t<sub>3</sub> + t<sub>4</sub> + t<sub>5</sub> + t<sub>6</sub> + t<sub>7</sub> + t<sub>8</sub> + t<sub>9</sub> + t<sub>10</sub> + t<sub>11</sub> + t<sub>12</sub> + <sup>1</sup>&frasl;<sub>t<sub>1</sub>t<sub>2</sub>t<sub>3</sub>t<sub>4</sub>t<sub>5</sub>t<sub>6</sub>t<sub>7</sub>t<sub>8</sub>t<sub>9</sub>t<sub>10</sub>t<sub>11</sub>t<sub>12</sub></sub>)</td>
    </tr>
    <tr>
      <td>14</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + t<sub>3</sub> + t<sub>4</sub> + t<sub>5</sub> + t<sub>6</sub> + <sup>t<sub>1</sub>t<sub>3</sub>t<sub>5</sub></sup>&frasl;<sub>t<sub>2</sub>t<sub>4</sub>t<sub>6</sub></sub> + <sup>t<sub>2</sub>t<sub>4</sub>t<sub>6</sub></sup>&frasl;<sub>t<sub>1</sub>t<sub>3</sub>t<sub>5</sub></sub> + t<sub>1</sub><sup>-1</sup> + t<sub>2</sub><sup>-1</sup> + t<sub>3</sub><sup>-1</sup> + t<sub>4</sub><sup>-1</sup> + t<sub>5</sub><sup>-1</sup> + t<sub>6</sub><sup>-1</sup>)</td>
    </tr>
    <tr>
      <td>15</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + t<sub>3</sub> + t<sub>4</sub> + t<sub>5</sub> + t<sub>6</sub> + t<sub>7</sub> + t<sub>8</sub> + <sup>t<sub>1</sub>t<sub>4</sub>t<sub>7</sub></sup>&frasl;<sub>t<sub>3</sub>t<sub>5</sub>t<sub>8</sub></sub> + <sup>t<sub>2</sub>t<sub>5</sub>t<sub>8</sub></sup>&frasl;<sub>t<sub>1</sub>t<sub>4</sub>t<sub>6</sub></sub> + <sup>t<sub>1</sub>t<sub>6</sub></sup>&frasl;<sub>t<sub>2</sub>t<sub>5</sub>t<sub>8</sub></sub> + <sup>t<sub>3</sub>t<sub>8</sub></sup>&frasl;<sub>t<sub>1</sub>t<sub>4</sub>t<sub>7</sub></sub> + <sup>1</sup>&frasl;<sub>t<sub>1</sub>t<sub>6</sub></sub> + <sup>1</sup>&frasl;<sub>t<sub>2</sub>t<sub>7</sub></sub> + <sup>1</sup>&frasl;<sub>t<sub>3</sub>t<sub>8</sub></sub>)</td>
    </tr>
    <tr>
      <td>16</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + t<sub>3</sub> + t<sub>4</sub> + t<sub>5</sub> + t<sub>6</sub> + t<sub>7</sub> + t<sub>8</sub> + t<sub>1</sub><sup>-1</sup> + t<sub>2</sub><sup>-1</sup> + t<sub>3</sub><sup>-1</sup> + t<sub>4</sub><sup>-1</sup> + t<sub>5</sub><sup>-1</sup> + t<sub>6</sub><sup>-1</sup> + t<sub>7</sub><sup>-1</sup> + t<sub>8</sub><sup>-1</sup>)</td>
    </tr>
    <tr>
      <td>17</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + ... + t<sub>16</sub> + <sup>1</sup>&frasl;<sub>t<sub>1</sub>t<sub>2</sub>t<sub>3</sub>t<sub>4</sub>t<sub>5</sub>t<sub>6</sub>t<sub>7</sub>t<sub>8</sub>t<sub>9</sub>t<sub>10</sub>t<sub>11</sub>t<sub>12</sub>t<sub>13</sub>t<sub>14</sub>t<sub>15</sub>t<sub>16</sub></sub>)</td>
    </tr>
    <tr>
      <td>18</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + t<sub>3</sub> + t<sub>4</sub> + t<sub>5</sub> + t<sub>6</sub> + <sup>t<sub>1</sub></sup>&frasl;<sub>t<sub>4</sub></sub> + <sup>t<sub>4</sub></sup>&frasl;<sub>t<sub>1</sub></sub> + <sup>t<sub>2</sub></sup>&frasl;<sub>t<sub>5</sub></sub> + <sup>t<sub>5</sub></sup>&frasl;<sub>t<sub>2</sub></sub> + <sup>t<sub>3</sub></sup>&frasl;<sub>t<sub>6</sub></sub> + <sup>t<sub>6</sub></sup>&frasl;<sub>t<sub>3</sub></sub> + t<sub>1</sub><sup>-1</sup> + t<sub>2</sub><sup>-1</sup> + t<sub>3</sub><sup>-1</sup> + t<sub>4</sub><sup>-1</sup> + t<sub>5</sub><sup>-1</sup> + t<sub>6</sub><sup>-1</sup>)</td>
    </tr>
    <tr>
      <td>19</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + ... + t<sub>18</sub> + <sup>1</sup>&frasl;<sub>t<sub>1</sub>t<sub>2</sub>t<sub>3</sub>t<sub>4</sub>t<sub>5</sub>t<sub>6</sub>t<sub>7</sub>t<sub>8</sub>t<sub>9</sub>t<sub>10</sub>t<sub>11</sub>t<sub>12</sub>t<sub>13</sub>t<sub>14</sub>t<sub>15</sub>t<sub>16</sub>t<sub>17</sub>t<sub>18</sub></sub>)</td>
    </tr>
    <tr>
      <td>20</td>
      <td>(t<sub>1</sub> + t<sub>2</sub> + ... + t<sub>8</sub> + <sup>t<sub>1</sub>t<sub>5</sub></sup>&frasl;<sub>t<sub>3</sub>t<sub>7</sub></sub> + <sup>t<sub>3</sub>t<sub>7</sub></sup>&frasl;<sub>t<sub>1</sub>t<sub>5</sub></sub> + <sup>t<sub>2</sub>t<sub>6</sub></sup>&frasl;<sub>t<sub>4</sub>t<sub>8</sub></sub> + <sup>t<sub>4</sub>t<sub>8</sub></sup>&frasl;<sub>t<sub>2</sub>t<sub>6</sub></sub> + t<sub>1</sub><sup>-1</sup> + t<sub>2</sub><sup>-1</sup> + t<sub>3</sub><sup>-1</sup> + t<sub>4</sub><sup>-1</sup> + t<sub>5</sub><sup>-1</sup> + t<sub>6</sub><sup>-1</sup> + t<sub>7</sub><sup>-1</sup> + t<sub>8</sub><sup>-1</sup>)</td>
    </tr>
  </tbody>
</table>
<table><caption>Tab. 3: The sequences $(U_n(N))_{0 \le N \le 20}$ for $n = 1, \dots, 20$.</caption><thead><tr><th>n</th><th>U<sub>n</sub>(N), N = 0, ..., 20</th></tr></thead><tbody><tr><td>1</td><td>1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0</td></tr><tr><td>2</td><td>1, 0, 2, 0, 6, 0, 20, 0, 70, 0, 252, 0, 924, 0, 3432, 0, 12870, 0, 48620, 0, 184756</td></tr><tr><td>3</td><td>1, 0, 0, 6, 0, 0, 90, 0, 0, 1680, 0, 0, 34650, 0, 0, 756756, 0, 0, 17153136, 0, 0</td></tr><tr><td>4</td><td>1, 0, 4, 0, 36, 0, 400, 0, 4900, 0, 63504, 0, 853776, 0, 11778624, 0, 165636900, 0, 2363904400, 0, 34134779536</td></tr><tr><td>5</td><td>1, 0, 0, 0, 0, 120, 0, 0, 0, 0, 113400, 0, 0, 0, 0, 168168000, 0, 0, 0, 0, 305540235000</td></tr><tr><td>6</td><td>1, 0, 6, 12, 90, 360, 2040, 10080, 54810, 290640, 1588356, 8676360, 47977776, 266378112, 1488801600, 8355739392, 47104393050, 266482019232, 1512589408044, 8610448069080, 49144928795820</td></tr><tr><td>7</td><td>1, 0, 0, 0, 0, 0, 5040, 0, 0, 0, 0, 0, 681080400, 0, 0, 0, 0, 0, 0</td></tr><tr><td>8</td><td>1, 0, 8, 0, 168, 0, 5120, 0, 190120, 0, 7939008, 0, 357713664, 0, 16993726464, 0, 839358285480, 0, 42714450658880, 0, 2225741588095168</td></tr><tr><td>9</td><td>1, 0, 0, 18, 0, 0, 2430, 0, 0, 640080, 0, 0, 215488350, 0, 0, 84569753268, 0, 0, 36905812607664, 0, 0</td></tr><tr><td>10</td><td>1, 0, 10, 0, 270, 240, 10900, 25200, 551950, 2116800, 32458860, 169092000, 2120787900, 13427013600, 149506414200, 1075081207200, 11143223412750, 87198375264000, 865743970019500, 7171730187336000, 69416724049550020</td></tr><tr><td>11</td><td>1, 0, 0, 0, 0, 0, 0, 0, 0, 39916800, 0, 0, 0, 0, 0, 0, 0, 0</td></tr><tr><td>12</td><td>1, 0, 12, 24, 396, 2160, 23160, 186480, 1845900, 17213280, 171575712, 1703560320, 17365421304, 178323713568, 1856554560432, 19487791106784, 206411964321420, 2201711191213248, 23642813637773616, 255355132936441824, 2772650461148938656</td></tr><tr><td>13</td><td>1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6227020800, 0, 0, 0, 0, 0, 0, 0</td></tr><tr><td>14</td><td>1, 0, 14, 0, 546, 0, 32900, 10080, 2570050, 2540160, 238935564, 465696000, 25142196156, 76886409600, 2900343069624, 12211317518400, 359067702643650, 1915829643087360, 47006105030584700, 300455419743198720, 6437718469449262996</td></tr><tr><td>15</td><td>1, 0, 0, 30, 0, 360, 7650, 0, 302400, 4544400, 11226600, 324324000, 4310633250, 24324300000, 437404968000, 5634178329780, 459729270000000, 697866761592000, 8962716395833200, 88725951057744000, 1258898645656852200</td></tr><tr><td>16</td><td>1, 0, 16, 0, 720, 0, 50560, 0, 4649680, 0, 514031616, 0, 64941883776, 0, 9071319628800, 0, 1369263687414480, 0, 219705672931613440, 0, 37024402443528248320</td></tr><tr><td>17</td><td>1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 355687428096000, 0, 0, 0</td></tr><tr><td>18</td><td>1, 0, 18, 36, 918, 5400, 82800, 801360, 10907190, 132053040, 1802041668, 24199809480, 340640607384, 4834708246368, 70229958125184, 1032223723667136, 15391538570569590, 231935110984687968, 3531542904056225916, 54244559313713885688, 839979883121036697468</td></tr><tr><td>19</td><td>1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 121645100408832000, 0</td></tr><tr><td>20</td><td>1, 0, 20, 0, 1140, 480, 102800, 151200, 12310900, 38707200, 1812247920, 9574488000, 313983978000, 2391608419200, 62051403928800, 611744666332800, 13627749414064500, 160896284989440000, 3253345101771050000, 43527416858084016000, 829176006298475046640</td></tr></tbody></table>
<table><caption>**Tab. 4:** Asymptotic estimates of $U_n(N)$ as $N \to \infty$, for $n = 1, \dots, 20$.</caption><thead><tr><th>n</th><th>Asymptotic estimate of U<sub>n</sub>(N) as N → ∞</th><th>Extra condition</th></tr></thead><tbody><tr><td>1</td><td>0</td><td>NIL</td></tr><tr><td>2</td><td><sup>√2</sup>⁄<sub>√π</sub> · <sup>2N</sup>⁄<sub>√N</sub> (1 - <sup>1</sup>⁄<sub>4N</sub> + <sup>1</sup>⁄<sub>32N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>N ≡ 0 (mod 2)</td></tr><tr><td>3</td><td><sup>3√3</sup>⁄<sub>2π</sub> · <sup>3N</sup>⁄<sub>N</sub> (1 - <sup>2</sup>⁄<sub>3N</sub> + <sup>2</sup>⁄<sub>9N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>N ≡ 0 (mod 3)</td></tr><tr><td>4</td><td><sup>2</sup>⁄<sub>π</sub> · <sup>4N</sup>⁄<sub>N</sub> (1 - <sup>1</sup>⁄<sub>2N</sub> + <sup>1</sup>⁄<sub>8N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>N ≡ 0 (mod 2)</td></tr><tr><td>5</td><td><sup>25√5</sup>⁄<sub>4π<sup>2</sup></sub> · <sup>5N</sup>⁄<sub>N<sup>2</sup></sub> (1 - <sup>2</sup>⁄<sub>N</sub> + <sup>2</sup>⁄<sub>N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>N ≡ 0 (mod 5)</td></tr><tr><td>6</td><td><sup>√3</sup>⁄<sub>2π</sub> · <sup>6N</sup>⁄<sub>N</sub> (1 - <sup>1</sup>⁄<sub>2N</sub> + <sup>1</sup>⁄<sub>12N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>NIL</td></tr><tr><td>7</td><td><sup>343√7</sup>⁄<sub>8π<sup>3</sup></sub> · <sup>7N</sup>⁄<sub>N<sup>3</sup></sub> (1 - <sup>4</sup>⁄<sub>N</sub> + <sup>8</sup>⁄<sub>N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>N ≡ 0 (mod 7)</td></tr><tr><td>8</td><td><sup>8</sup>⁄<sub>π<sup>2</sup></sub> · <sup>8N</sup>⁄<sub>N<sup>2</sup></sub> (1 - <sup>1</sup>⁄<sub>N</sub> + <sup>1</sup>⁄<sub>N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>N ≡ 0 (mod 2)</td></tr><tr><td>9</td><td><sup>243√3</sup>⁄<sub>8π<sup>3</sup></sub> · <sup>9N</sup>⁄<sub>N<sup>3</sup></sub> (1 - <sup>3</sup>⁄<sub>N</sub> + <sup>4</sup>⁄<sub>N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>N ≡ 0 (mod 3)</td></tr><tr><td>10</td><td><sup>5√5</sup>⁄<sub>4π<sup>2</sup></sub> · <sup>10N</sup>⁄<sub>N<sup>2</sup></sub> (1 - <sup>1</sup>⁄<sub>N</sub> + <sup>3</sup>⁄<sub>4N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>NIL</td></tr><tr><td>11</td><td><sup>161051√11</sup>⁄<sub>32π<sup>5</sup></sub> · <sup>11N</sup>⁄<sub>N<sup>5</sup></sub> (1 - <sup>10</sup>⁄<sub>N</sub> + <sup>50</sup>⁄<sub>N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>N ≡ 0 (mod 11)</td></tr><tr><td>12</td><td><sup>3</sup>⁄<sub>π<sup>2</sup></sub> · <sup>12N</sup>⁄<sub>N<sup>2</sup></sub> (1 - <sup>1</sup>⁄<sub>N</sub> + <sup>2</sup>⁄<sub>3N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>NIL</td></tr><tr><td>13</td><td><sup>4826809√13</sup>⁄<sub>64π<sup>6</sup></sub> · <sup>13N</sup>⁄<sub>N<sup>6</sup></sub> (1 - <sup>14</sup>⁄<sub>N</sub> + <sup>98</sup>⁄<sub>N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>N ≡ 0 (mod 13)</td></tr><tr><td>14</td><td><sup>49√7</sup>⁄<sub>8π<sup>3</sup></sub> · <sup>14N</sup>⁄<sub>N<sup>3</sup></sub> (1 - <sup>3</sup>⁄<sub>2N</sub> + <sup>3</sup>⁄<sub>N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>NIL</td></tr><tr><td>15</td><td><sup>1125</sup>⁄<sub>16π<sup>4</sup></sub> · <sup>15N</sup>⁄<sub>N<sup>4</sup></sub> (1 - <sup>4</sup>⁄<sub>N</sub> + <sup>25</sup>⁄<sub>3N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>NIL</td></tr><tr><td>16</td><td><sup>512</sup>⁄<sub>π<sup>4</sup></sub> · <sup>16N</sup>⁄<sub>N<sup>4</sup></sub> (1 - <sup>2</sup>⁄<sub>N</sub> + <sup>9</sup>⁄<sub>N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>N ≡ 0 (mod 2)</td></tr><tr><td>17</td><td><sup>6975757441√17</sup>⁄<sub>256π<sup>8</sup></sub> · <sup>17N</sup>⁄<sub>N<sup>8</sup></sub> (1 - <sup>24</sup>⁄<sub>N</sub> + <sup>288</sup>⁄<sub>N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>N ≡ 0 (mod 17)</td></tr><tr><td>18</td><td><sup>81√3</sup>⁄<sub>8π<sup>3</sup></sub> · <sup>18N</sup>⁄<sub>N<sup>3</sup></sub> (1 - <sup>3</sup>⁄<sub>2N</sub> + <sup>5</sup>⁄<sub>2N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>NIL</td></tr><tr><td>19</td><td><sup>322687697779√19</sup>⁄<sub>512π<sup>9</sup></sub> · <sup>19N</sup>⁄<sub>N<sup>9</sup></sub> (1 - <sup>30</sup>⁄<sub>N</sub> + <sup>450</sup>⁄<sub>N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>N ≡ 0 (mod 19)</td></tr><tr><td>20</td><td><sup>125</sup>⁄<sub>π<sup>4</sup></sub> · <sup>20N</sup>⁄<sub>N<sup>4</sup></sub> (1 - <sup>2</sup>⁄<sub>N</sub> + <sup>7</sup>⁄<sub>N<sup>2</sup></sub> + O(<sup>1</sup>⁄<sub>N<sup>3</sup></sub>))</td><td>NIL</td></tr></tbody></table>