Pairs of Intertwined Integer Sequences

Christian Kassel Institut de Recherche Mathématique Avancée Université de Strasbourg & CNRS 7 rue René-Descartes 67084 Strasbourg France

                kassel@math.unistra.fr

Christophe Reutenauer Mathématiques Université du Québec à Montréal CP 8888, succ. centre-ville Montréal, PQ H3C 3P8 Canada

             reutenauer.christophe@uqam.ca

Abstract

In previous work we computed the number C_{n}(q) of ideals of codimension n of the algebra 𝔽_{q}[x, y, x^{−1}, y^{−1}] of two-variable Laurent polynomials over a finite field 𝔽_{q}: it turned out that C_{n}(q) is a palindromic polynomial of degree 2n in q, divisible by (q−1)^{2}. The quotient P_{n}(q) = C_{n}(q)/(q − 1)^{2} is a palindromic polynomial of degree 2n − 2. For each n ≥ 1 let \overline{P}_{n}(X) ∈ ℤ[X] be the degree n − 1 polynomial such that \overline{P}_{n}(q + q^{−1}) = P_{n}(q)/q^{n−1}. In this article we show that for every integer N the integer value \overline{P}_{n}(N) is close to the value at N of the degree n − 1 polynomial F_{n−1}(X) = 1 + ∑_{k=1}^{n−1} \overline{T}_{k}(X), which is a sum of monic versions \overline{T}_{k}(X) of Chebyshev polynomials of the first kind. We give a precise formula for \overline{P}_{n}(X) as a linear combination of the F_{k}(X), each appearance of the latter being indexed by an odd divisor of n. As a consequence, \overline{P}_{n}(X) = F_{n−1}(X) if and only if n is a power of 2. We exhibit similar formulas for C_{n}(q).

1 Introduction

In this article, for each integer N we produce a pair (\overline{P}_{n}(N), (F_{n−1}(N))_{n≥1} of integer sequences. Both sequences, though of differing origin, consist of amazingly close elements. Some of them do even coincide: we have \overline{P}_{n}(N) = F_{n−1}(N) whenever n is a power of 2. The reader is invited to examine Table 1 which exhibits such pairs for N = 3, 4, 5. In this table coinciding values have been set in boldface and values differing by 1 in italics.

\begin{matrix}n & \overline{P}_{n}(3) & F_{n−1}(3) & \overline{P}_{n}(4) & F_{n−1}(4) & \overline{P}_{n}(5) & F_{n−1}(5) \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 4 & 4 & 5 & 5 & 6 & 6 \\ 3 & 10 & 11 & 18 & 19 & 28 & 29 \\ 4 & 29 & 29 & 71 & 71 & 139 & 139 \\ 5 & 72 & 76 & 260 & 265 & 660 & 666 \\ 6 & 200 & 199 & 990 & 989 & 3192 & 3191 \\ 7 & 510 & 521 & 3672 & 3691 & 15260 & 15289 \\ 8 & 1364 & 1364 & 13775 & 13775 & 73254 & 73254 \\ 9 & 3546 & 3571 & 51343 & 51409 & 350848 & 350981 \\ 10 & 9348 & 9349 & 191860 & 191861 & 1681650 & 1681651 \\ 11 & 24400 & 24476 & 715770 & 716035 & 8056608 & 8057274 \\ 12 & 64090 & 64079 & 2672298 & 2672279 & 38604748 & 38604719 \\ 13 & 167562 & 167761 & 9972092 & 9973081 & 184963130 & 184966321 \\ 14 & 439200 & 439204 & 37220040 & 37220045 & 886226880 & 886226886 \\ 15 & 1149360 & 1149851 & 138903480 & 138907099 & 4246152960 & 4246168109 \\ 16 & 3010349 & 3010349 & 518408351 & 518408351 & 20344613659 & 20344613659 \end{matrix}

Table 1: Values of \overline{P}_{n}(N) and F_{n−1}(N) for N = 3, 4, 5.

Let us now describe the components of such pairs. Starting with \overline{P}_{n}(N), let 𝔽_{q} be a finite field of cardinality q and 𝔽_{q}[x, y, x^{−1}, y^{−1}] be the algebra of two-variable Laurent polynomials with coefficients in 𝔽_{q}. For every integer n ≥ 1, let C_{n}(q) denote the number of ideals I of codimension n of 𝔽_{q}[x, y, x^{−1}, y^{−1}], i.e., such that the quotient 𝔽_{q}[x, y, x^{−1}, y^{−1}]/I is a 𝔽_{q}-vector space of dimension n. (For algebraic geometers, C_{n}(q) counts the 𝔽_{q}-points of the Hilbert scheme of n points on the two-dimensional torus.) The authors [9] showed that C_{n}(q) is a monic polynomial of degree 2n with integer coefficients in the variable q; moreover, C_{n}(q) is palindromic and divisible by (q − 1)^{2}. They [10, Th. 1.1] gave explicit formulas for the coefficients of C_{n}(q); also see § 5.2 below.

The polynomial C_{n}(q) being divisible by (q − 1)^{2}, we may consider the degree 2n − 2 polynomial P_{n}(q) = C_{n}(q)/(q − 1)^{2}: it is monic, palindromic and has integer coefficients. One of the most striking features of P_{n}(q) is that its coefficients are all nonnegative; actually, each coefficient of P_{n}(q) can be expressed as the number of divisors of n in a certain real interval; see [10, Thm. 1.3] and § 4.1 below.

The authors [10, Thm. 1.6] also computed the values taken by P_{n}(q) when q is a complex root of unity of order 1, 2, 3, 4 or 6, equivalently when q+q^{−1} takes one of the respective values 2, −2, −1, 0, 1, thus recovering well-known arithmetical functions. For instance, P_{n}(1) = σ(n) is equal to the sum of divisors of n and P_{n}(−1) = r(n)/4, where r(n) is the number of representations of n as a sum of squares of two integers.

More generally, for every integer n ≥ 1, the Laurent polynomial P_{n}(q)/q^{n−1} takes integer values whenever q + q^{−1} = N is an integer. Computing such values is the main objective of this paper. For simplicity we replace the Laurent polynomial P_{n}(q)/q^{n−1} in the variable q by the degree n − 1 polynomial \overline{P}_{n}(X) in the variable X, defined by

\overline{P}_{n}(q + q^{−1}) = P_{n}(q)/q^{n−1}.  (1)

(This is possible since P_{n}(q) is palindromic of degree 2n − 2.) We have thus reduced our problem to the computation of the values of \overline{P}_{n}(X) at integers N.

Searching the On-Line Encyclopedia of Integer Sequences (OEIS) [12] for the sequence

(\overline{P}_{1}(5), \overline{P}_{2}(5), \overline{P}_{3}(5), \overline{P}_{4}(5), \overline{P}_{5}(5), \overline{P}_{6}(5)) = (1, 6, 28, 139, 660, 3192)

yielded, as of January 7 2025, what the OEIS called an “approximate match”, namely the sequence of integers consisting of the first few coefficients of the power series expansion of the rational function

\frac{1 + t}{1 − 5t + t^{2}} .

Replacing 5 by 3 and by 4 in this rational function has produced similar approximate matches for \overline{P}_{n}(3) and \overline{P}_{n}(4) respectively. In view of this, it was natural for us to replace 3, 4, 5 by an indeterminate X as follows.

The second integer sequence mentioned above consists of integer values at N of the polynomials F_{k}(X) defined by the following equality of formal power series:

∑_{k≥0} F_{k}(X) t^{k} = \frac{1 + t}{1 − Xt + t^{2}} .  (2)

It turns out that each polynomial F_{k}(X) is of degree k − 1, has integer coefficients, and we have

F_{k}(X) = 1 + ∑_{m=1}^{k} \overline{T}_{m}(X),  (3)

which is the sum of the monic versions \overline{T}_{m}(X) of the Chebyshev polynomials of the first kind defined in § 3.1 below.

With this notation we establish that each \overline{P}_{n}(X) can be approximated by F_{n−1}(X) in the sense that the difference between these two monic polynomials, both of degree n − 1, is a polynomial of much lower degree (see Theorem 12 for a precise statement).

More interestingly, \overline{P}_{n}(X) can be expressed as the following linear combination of F_{k}(X), whose terms are indexed by the odd divisors d of n:

\overline{P}_{n}(X) = ∑_{{d|n, d odd \atop rn(d)≥0}} F_{r_{n}(d)}(X) − ∑_{{d|n, d odd \atop rn(d)<0}} F_{−r_{n}(d)−1}(X),  (4)

where r_{n}(d) = n/d − (d + 1)/2; see Theorem 16. For d = 1 we have r_{n}(1) = n − 1, which implies the presence of F_{n−1}(X) in (4) for all n ≥ 1.

Since the powers of 2 are the only integers with a unique odd divisor, namely d = 1, we have \overline{P}_{n}(X) = F_{n−1}(X) if and only if n is a power of 2. This explains the coincidences observed in Table 1.

We deduce Formula (4) from the following new expression for C_{n}(q):

C_{n}(q) = q^{n} ∑_{d|n, d odd} (q^{\frac{n}{d} − \frac{d−1}{2}} + q^{− \frac{n}{d} + \frac{d−1}{2}} − q^{\frac{n}{d} − \frac{d+1}{2}} − q^{− \frac{n}{d} + \frac{d+1}{2}} ) .  (5)

See Theorem 23.

Formula (5) allows us to express the local zeta function and the Hasse–Weil zeta function of the Hilbert scheme of n points on the two-dimensional torus as products whose factors are indexed by the odd divisors of n (see § 5.3).

Let us detail the content of each section. In Section 2, for each n ≥ 1 we define the degree n − 1 polynomial \overline{P}_{n}(X) by (1). As mentioned above, the integers of interest to us are the values \overline{P}_{n}(N) at arbitrary integers N. Building on previous work [10], we show that the function n ↦ |\overline{P}_{n}(N)| is multiplicative if N = −2, −1, 0 or 2; for all remaining integer values of N it is not multiplicative.

Section 3 is devoted to the monic versions \overline{T}_{k}(X) of the Chebyshev polynomials of the first kind and to the polynomials F_{k}(X) defined above.

In Section 4 we state the results on \overline{P}_{n}(X) mentioned above. Theorem 12 and Theorem 16 with Formula (4) are the main results. As special cases of (4) we obtain formulas for P_{n}(X) in terms of the polynomials F_{k}(X) for various families of integers n.

Section 5 is devoted to the polynomials C_{n}(q): we prove (5) and state the formulas for the zeta functions mentioned above. In Section 6 we use the results of Section 5 to prove Theorem 16.

2 The polynomials \overline{P}_{n}(X)

2.1 Definition and basic properties

For every positive integer n we define the degree n − 1 polynomial \overline{P}_{n}(X) by

\overline{P}_{n}(q + q^{−1}) = P_{n}(q)/q^{n−1},  (6)

where P_{n}(q) was introduced in Section 1. This makes sense since P_{n}(q) is a palindromic polynomial of degree 2n − 2. As P_{n}(q) has integer coefficients, so does \overline{P}_{n}(X).

As a consequence of [9, Cor. 1.4], we have the equality of formal power series

1 + (q + q^{−1} − 2) ∑_{n≥1} \frac{P_{n}(q)}{q^{n−1}} t^{n} = ∏_{i≥1} \frac{(1 − t^{i})^{2}}{1 − (q + q^{−1})t^{i} + t^{2i}} .

This translates into the following equality for the polynomials \overline{P}_{n}(X):

1 + (X − 2) ∑_{n≥1} \overline{P}_{n}(X) t^{n} = ∏_{i≥1} \frac{(1 − t^{i})^{2}}{1 − Xt^{i} + t^{2i}} .  (7)

The authors [10, Thm. 1.3] established that each polynomial P_{n}(q) is of the form

P_{n}(q) = a_{n,0} q^{n−1} + ∑_{i=1}^{n−1} a_{n,i} (q^{n+i−1} + q^{n−i−1}) ,  (8)

where the coefficients a_{n,i} are all nonnegative integers (to be expressed explicitly in the proof of Lemma 14). It follows that for each positive integer n,

\overline{P}_{n}(X) = a_{n,0} + ∑_{i=1}^{n−1} a_{n,i} \overline{T}_{i}(X),  (9)

where \overline{T}_{i}(X) is the monic Chebyshev polynomial of degree i defined by (10) below. Since the coefficients a_{n,i} are nonnegative integers, each \overline{P}_{n}(X) is a sum of the polynomials \overline{T}_{k}(X).

A list of the polynomials \overline{P}_{n}(X) for 1 ≤ n ≤ 12 is given in Table 2. It is based on the corresponding list of P_{n}(q) in Table 2 of either [9] or [10].

n  \overline{P}_{n}(X)
1  1
2  X + 1
3  X^{2} + X − 2
4  X^{3} + X^{2} − 2X − 1
5  X^{4} + X^{3} − 3X^{2} − 3X
6  X^{5} + X^{4} − 4X^{3} − 3X^{2} + 3X + 2
7  X^{6} + X^{5} − 5X^{4} − 4X^{3} + 5X^{2} + 2X
8  X^{7} + X^{6} − 6X^{5} − 5X^{4} + 10X^{3} + 6X^{2} − 4X − 1
9  X^{8} + X^{7} − 7X^{6} − 6X^{5} + 15X^{4} + 9X^{3} − 11X^{2} − X + 3
10 X^{9} + X^{8} − 8X^{7} − 7X^{6} + 21X^{5} + 15X^{4} − 20X^{3} − 10X^{2} + 5X
X^{10} + X^{9} − 9X^{8} − 8X^{7} + 28X^{6} + 21X^{5}
11  −36X^{4} − 21X^{3} + 18X^{2} + 7X − 2
X^{11} + X^{10} − 10X^{9} − 9X^{8} + 36X^{7} + 28X^{6}
12  −56X^{5} − 35X^{4} + 35X^{3} + 16X^{2} − 5X − 2
Table 2: The polynomials \overline{P}_{n}(X).

The following result explains why all entries in Table 1 are positive. Proposition 1. Let N be an integer ≥ 2. Then \overline{P}_{n}(N) > 0 for all n ≥ 1. Proof. This is a consequence of Proposition 6 below and of the fact mentioned above that each \overline{P}_{n}(X) is a sum of the \overline{T}_{k}(X).

2.2 Multiplicative values of |P_{n}(q)| at roots of unity

The content of this subsection is an addendum to [10, Th. 1.6]. It concerns the cases when q + q^{−1} = N is an integer such that −2 ≤ N ≤ 2, equivalently when q is a root of unity of order d = 1, 2, 3, 4 or 6. Proposition 2. Let q be a complex root of unity of order d = 1, 2, 3 or 4. Then the sequence of nonnegative integers

|P_{n}(q)| = |P_{n}(q)/q^{n−1}| = |\overline{P}_{n}(q + q^{−1})|

is multiplicative as a function of n.

Recall that a function f(n) defined on positive integers is multiplicative if f(mn) = f(m)f(n) whenever m and n are coprime.

Proof. When q = 1, by [9, Cor. 1.2] we have \overline{P}_{n}(2) = P_{n}(1) = σ(n), the sum of divisors of n, which is well-known to be multiplicative. See Apostol [2, Sect. 2.13] and the OEIS [12] at \underline{A000203}.

For q = −1 we have \overline{P}_{n}(−2) = P_{n}(−1) = r(n)/4, where r(n) is the number of representations of n as a sum of squares of two integers. By the OEIS [12, \underline{A002654}] the sequence r(n)/4 is multiplicative. Then so is P_{n}(−1).

For q = j, a root of unity of order 3, we have \overline{P}_{n}(−1) = P_{n}(j)/j^{n−1} = λ(n), where λ(n) is the sequence \underline{A113063} in the OEIS [12]. Fine [6, Sect. 32, p. 79] states that λ(n) is multiplicative. See also Caballero [5].

Let i be a square root of −1. It follows again from [10, Th. 1.6] that we have

|\overline{P}_{n}(0)| = |P_{n}(i)/i^{n−1}| = r′(n)/2,

where r′(n) is the number of representations of n as a sum of a square and twice another square. The sequence of integers r′(n)/2 listed as \underline{A002325} in the OEIS [12] is known to be multiplicative.

The case when q = ω is a root of unity of order 6 is slightly more involved.

Proposition 3. Let ω be a root of unity of order 6. Then for all pairs (m, n) of coprime positive integers we have

|P_{m}(ω)||P_{n}(ω)| = |P_{mn}(ω)| when (m, n) ≡ (0, 1), (1, 1) or (1, 2) (mod 3),
|P_{m}(ω)||P_{n}(ω)| = 2 |P_{mn}(ω)| when (m, n) ≡ (0, 2) (mod 3),
|P_{m}(ω)||P_{n}(ω)| = 4 |P_{mn}(ω)| when (m, n) ≡ (2, 2) (mod 3).

Proof. This is a consequence of the multiplicativity of the sequence r(n)/4 observed above and of the following reformulation of a result due to the authors [8, Th. 1.1] and [10, Th. 1.6 (d)]:

|P_{n}(ω)| = \begin{cases}r(n), & if n ≡ 0 (mod 3); \\ r(n)/4, & if n ≡ 1 (mod 3); \\ r(n)/2, & if n ≡ 2 (mod 3). \end{cases}

We have the following consequence of Propositions 2 and 3.

Corollary 4. Given a pair (m, n) of coprime positive integers, the polynomial \overline{P}_{mn}(X)^{2} − \overline{P}_{m}(X)^{2}\overline{P}_{n}(X)^{2} is divisible by X(X + 1)(X^{2} − 4), and moreover by X − 1 if (m, n) ≡ (0, 1), (1, 1) or (1, 2) (mod 3).

We may wonder whether there are other integers N such that n ↦ |\overline{P}_{n}(N)| is a multiplicative function. The answer is no.

Proposition 5. The function n ↦ |\overline{P}_{n}(N)| is multiplicative if and only if N = −2, −1, 0 or 2.

Proof. The “if direction” is a reformulation of Proposition 2. Conversely, if n ↦ |\overline{P}_{n}(N)| is multiplicative, then we have |\overline{P}_{6}(N)| = |\overline{P}_{2}(N)||\overline{P}_{3}(N)| as a special case. Now the polynomial \overline{P}_{6}(X)^{2} − \overline{P}_{2}(X)^{2} \overline{P}_{3}(X)^{2} can be factored as

\overline{P}_{6}(X)^{2} − \overline{P}_{2}(X)^{2} \overline{P}_{3}(X)^{2} = X(X − 1)^{3}(X + 1)^{3}(X − 2)(X + 2)^{2}.

This implies that multiplicativity holds only for integers N such that |N| ≤ 2. We rule out the case N = 1 in view of Proposition 3.

3 The polynomials F_{n}(X)

Let us define the monic Chebyshev polynomials and the polynomials F_{n}(X) mentioned in the introduction.

3.1 Monic Chebyshev polynomials

Given an integer k ≥ 0, the standard Chebyshev polynomial of the first kind T_{k}(X) is the degree k polynomial defined by

cos(kθ) = T_{k}(cos(θ)),

equivalently by

\frac{q^{k} + q^{−k}}{2} = T_{k} (\frac{q + q^{−1}}{2} ) .

Rivlin [13] gave a useful overview of the important properties of Chebyshev polynomials.

We are interested in the following variant of T_{k}(X): let \overline{T}_{k}(X) be the degree k polynomial defined by

q^{k} + q^{−k} = \overline{T}_{k}(q + q^{−1}).  (10)

Both T_{k}(X) and \overline{T}_{k}(X) have integer coefficients. They are clearly related by

\overline{T}_{k}(X) = 2T_{k}(X/2).  (11)

The polynomials \overline{T}_{k}(X) are monic for all k ≥ 1. That is why we call them monic Chebyshev polynomials. Abramowitz et al. [1, p. 778, Eq. 22.5.11] denote the polynomials \overline{T}_{k}(X) by C_{k}; Horadam [7] calls them Vieta–Lucas polynomials and denotes them by v_{n}(x).

Table 3 lists the polynomials \overline{T}_{k}(X) for 1 ≤ k ≤ 12.

\begin{matrix}k & \overline{T}_{k}(X) \\ 0 & 2 \\ 1 & X \\ 2 & X^{2} − 2 \\ 3 & X^{3} − 3X \\ 4 & X^{4} − 4X^{2} + 2 \\ 5 & X^{5} − 5X^{3} + 5X \\ 6 & X^{6} − 6X^{4} + 9X^{2} − 2 \\ 7 & X^{7} − 7X^{5} + 14X^{3} − 7X \\ 8 & X^{8} − 8X^{6} + 20X^{4} − 16X^{2} + 2 \\ 9 & X^{9} − 9X^{7} + 27X^{5} − 30X^{3} + 9X \\ 10 & X^{10} − 10X^{8} + 35X^{6} − 50X^{4} + 25X^{2} − 2 \\ 11 & X^{11} − 11X^{9} + 44X^{7} − 77X^{5} + 55X^{3} − 11X \\ 12 & X^{12} − 12X^{10} + 54X^{8} − 112X^{6} + 105X^{4} − 36X^{2} + 2 \end{matrix}

Table 3: The monic Chebyshev polynomials \overline{T}_{k}(X).

Let us state a few properties of the polynomials \overline{T}_{k}(X) which can be easily derived from well-known properties of T_{k}(X).

First, the polynomials \overline{T}_{k}(X) can be defined inductively by \overline{T}_{0}(X) = 2, \overline{T}_{1}(X) = X, and for k ≥ 1 by

\overline{T}_{k+1}(X) = X\overline{T}_{k}(X) − \overline{T}_{k−1}(X).  (12)

The previous linear recurrence relation can be written in matrix form as

(\begin{matrix}\overline{T}_{k+1}(X) \\ \overline{T}_{k}(X) \end{matrix}) = M (\begin{matrix}\overline{T}_{k}(X) \\ \overline{T}_{k−1}(X) \end{matrix}) , where M = (\begin{matrix}X & −1 \\ 1 & 0 \end{matrix}) .  (13)

Next, the generating function of the polynomials \overline{T}_{k}(X) is the power series expansion of the following rational function:

∑_{k≥0} \overline{T}_{k}(X) t^{k} = \frac{2 − Xt}{1 − Xt + t^{2}} .  (14)

We have the following expression of \overline{T}_{n}(X) in terms of powers of X:

\overline{T}_{n}(X) = ∑_{m=0}^{[n/2]} (−1)^{m} (\binom{n − m}{m} − \binom{n − m − 1}{m − 1}) X^{n−2m}.

We also have a positivity result for the polynomials \overline{T}_{k}(X).

Proposition 6. For each k ≥ 0, we have \overline{T}_{k}(x) > 0 if x is a real number ≥ 2.

Proof. On one hand, as is well known, the zeros of the standard Chebyshev polynomials T_{k}(X) all lie in the open interval (−1, 1). Hence, in view of (11) the zeros of \overline{T}_{k}(X) lie in (−2, 2). On the other, since \overline{T}_{k}(X) is monic, lim_{x→+∞} \overline{T}_{k}(x) = +∞. Combining these two facts implies the desired positivity.

We close our summary on \overline{T}_{k}(X) with the following result, which may be of independent interest.

Proposition 7. For all k ≥ 0 we have \overline{T}_{k}(X) = tr(M^{k}), where M is the 2×2-matrix defined in (13).

Proof. First, observe that tr(M) = X = \overline{T}_{1}(X) and tr(M^{0}) = tr(Id) = 2 = \overline{T}_{0}(X), where Id is the identity matrix. In order to complete the proof of the desired equality, it suffices to show that the sequence (tr(M^{k}))_{k≥0} satisfies the linear recurrence relation (12). By the Cayley–Hamilton theorem applied to the matrix M, we have

M^{2} = tr(M)M − det(M)Id = XM − Id.

Now multiply both sides by M^{k−1} and take traces.

3.2 Definition and basic properties of F_{n}(X)

We define the sequence of polynomials (F_{n}(X))_{n≥0} inductively by F_{0}(X) = 1 and by

F_{n}(X) = F_{n−1}(X) + \overline{T}_{n}(X)  (15)

for n ≥ 1. In other words,

F_{n}(X) = 1 + ∑_{k=1}^{n} \overline{T}_{k}(X).  (16)

It is clear that each F_{n}(X) has integer coefficients and is monic of degree n. We give a list of the polynomials F_{n}(X) for n ≤ 11 in Table 4.

Our first result is the following.

Proposition 8. The generating function of the polynomials F_{n}(X) is the power series expansion of the following rational function:

∑_{n≥0} F_{n}(X) t^{n} = \frac{1 + t}{1 − Xt + t^{2}} .

Proof. Using (14), we obtain

1 + ∑_{k≥1} \overline{T}_{k}(X) t^{k} = \frac{2 − Xt}{1 − Xt + t^{2}} + 1 − \overline{T}_{0}(X)

= \frac{2 − Xt}{1 − Xt + t^{2}} − 1 = \frac{1 − t^{2}}{1 − Xt + t^{2}} .

n  F_{n}(X)
0  1
1  X + 1
2  X^{2} + X − 1
3  X^{3} + X^{2} − 2X − 1
4  X^{4} + X^{3} − 3X^{2} − 2X + 1
5  X^{5} + X^{4} − 4X^{3} − 3X^{2} + 3X + 1
6  X^{6} + X^{5} − 5X^{4} − 4X^{3} + 6X^{2} + 3X − 1
7  X^{7} + X^{6} − 6X^{5} − 5X^{4} + 10X^{3} + 6X^{2} − 4X − 1
8 X^{8} + X^{7} − 7X^{6} − 6X^{5} + 15X^{4} + 10X^{3} − 10X^{2} − 4X + 1

X^{9} + X^{8} − 8X^{7} − 7X^{6} + 21X^{5} + 15X^{4}

9  −20X^{3} − 10X^{2} + 5X + 1

X^{10} + X^{9} − 9X^{8} − 8X^{7} + 28X^{6} + 21X^{5}

10  −35X^{4} − 20X^{3} + 15X^{2} + 5X − 1

X^{11} + X^{10} − 10X^{9} − 9X^{8} + 36X^{7} + 28X^{6}

11  −56X^{5} − 35X^{4} + 35X^{3} + 15X^{2} − 6X − 1

Table 4: The polynomials F_{n}(X).

Therefore,

∑_{n≥0} F_{n}(X) t^{n} = ∑_{n≥0} (1 + ∑_{m=1}^{n} \overline{T}_{m}(X)) t^{n}
= (∑_{ℓ≥0} t^{ℓ}) (1 + ∑_{k≥1} \overline{T}_{k}(X) t^{k})
= \frac{1}{1 − t} · \frac{1 − t^{2}}{1 − Xt + t^{2}} = \frac{1 + t}{1 − Xt + t^{2}} .

Setting X = 0 in the formula of Proposition 8 yields the constant term of F_{n}(X): for all m ≥ 0 we have

F_{2m}(0) = F_{2m+1}(0) = (−1)^{m}.

For the remaining coefficients of F_{n}(X) we have the following expression.

Proposition 9. For n ≥ 1 we have

F_{n}(X) = ∑_{0≤m≤n/2} (−1)^{m}\binom{n − m}{m} X^{n−2m} + ∑_{0≤m≤(n−1)/2} (−1)^{m}\binom{n − m − 1}{m} X^{n−2m−1}.

Proof. Expanding the following fraction, we obtain

\frac{1}{1 − Xt + t^{2}} = 1 + ∑_{r≥1} t^{r}(X − t)^{r}

= 1 + ∑_{r≥1} ∑_{s=0}^{r} (−1)^{s}\binom{r}{s}X^{r−s}t^{r+s}

= 1 + ∑_{n≥1} ∑_{0≤m≤n/2} (−1)^{m}\binom{n − m}{m}X^{n−2m}t^{n}.

In view of Proposition 8, multiplying by 1 + t yields the desired formula for F_{n}(X).

Corollary 10. For n ≥ 5 we have

F_{n}(X) = X^{n} + X^{n−1} − (n − 1)X^{n−2} − (n − 2)X^{n−3}

+ \frac{(n − 2)(n − 3)}{2}X^{n−4} + \frac{(n − 3)(n − 4)}{2}X^{n−5}

+ monomials of degree ≤ n − 6.

In Section 6 we need the following linear recurrence relation satisfied by the polynomials F_{k}(X).

Proposition 11. For k ≥ 1 we have F_{k+1}(X) = XF_{k}(X) − F_{k−1}(X).

Proof. The rational function expressing the generating function in Proposition 8 has the same denominator as the rational function in (14). Therefore the polynomials F_{k}(X) satisfy the same linear recurrence relation as the polynomials \overline{T}_{k}(X) in (12); see, e.g., Berstel et al. [3, Chap. 6, Prop. 1.2 and Cor. 1.3].

4 Results for the polynomials \overline{P}_{n}(X)

Now we establish a connection between the polynomials \overline{P}_{n}(X) and the polynomials F_{k}(X). We start with an approximation result.

4.1 Approximating \overline{P}_{n}(X) by F_{n−1}(X)

The aim of this subsection is the following result.

Theorem 12. For all n ≥ 2, the difference \overline{P}_{n}(X) − F_{n−1}(X) is a polynomial whose degree is smaller than n/2 − 1.

Recall that \overline{P}_{n}(X) and F_{n−1}(X) are both of degree n − 1. The theorem states that they coincide in every degree ≥ n/2 − 1.

The bound on degrees is sharp as can be seen from Table 5: indeed, \overline{P}_{9}(X) − F_{8}(X) = −F_{3}(X) + F_{1}(X) is of degree 3 < 9/2 − 1; similarly, \overline{P}_{11}(X) − F_{10}(X) = −F_{4}(X) is of degree 4 < 11/2 − 1, and \overline{P}_{15}(X) − F_{14}(X) is of degree 6 < 15/2 − 1.

Together with Corollary 10 we derive the following.

Corollary 13. For all n ≥ 10 we have

\overline{P}_{n}(X) = X^{n−1} + X^{n−2} − (n − 2)X^{n−3} − (n − 3)X^{n−4}

+ \frac{(n − 3)(n − 4)}{2}X^{n−5} + \frac{(n − 4)(n − 5)}{2}X^{n−6}

+ monomials of degree ≤ n − 7.

Recall the (nonnegative) coefficients a_{n,i} of \overline{P}_{n}(X) appearing in (8) and (9). For the proof of Theorem 12 we need the following result.

Lemma 14. We have a_{n,i} = 1 for all i such that n/2 − 1 ≤ i ≤ n − 1.

Proof. Given 0 ≤ i ≤ n − 1, the authors [10, Thm. 1.3] showed that the coefficient a_{n,i} is equal to the number of divisors of n belonging to the half-open interval

I_{n,i} = (\frac{i + \sqrt{2n + i^{2}}}{2} , i + \sqrt{2n + i^{2}}] .

It is enough to show that n is the only divisor of n belonging to I_{n,i}. Since all other divisor of n are ≤ n/2, it suffices to check that n ≤ i + \sqrt{2n + i^{2}} and n/2 ≤ (i + \sqrt{2n + i^{2}})/2; the latter inequality is equivalent to the former. They are both equivalent to n(n − 2i) = (n − i)^{2} − i^{2} ≤ 2n, which simplifies into n − 2i ≤ 2 hence to i ≥ (n − 2)/2 = n/2 − 1.

Proof of Theorem 12. By (16) and (9) we have

\overline{P}_{n}(X) − F_{n−1}(X) = (a_{n,0} − 1) + ∑_{1≤i≤n−1} (a_{n,i} − 1) \overline{T}_{i}(X)
= (a_{n,0} − 1) + ∑_{1≤i<n/2−1} (a_{n,i} − 1) \overline{T}_{i}(X).

The last equality is a consequence of Lemma 14. Since \overline{T}_{i}(X) is of degree i, we obtain the desired result.

Remark 15. The sequence of integers \overline{P}_{n}(3) is Sequence \underline{A329156} in the OEIS [12]. The sequence (F_{n−1}(3))_{n≥1} is \underline{A002878}: we have F_{n−1}(3) = L(2n + 1), where L(n) is the Lucas sequence defined by L(n) = L(n − 1) + L(n − 2), L(0) = 2, and L(1) = 1.

The sequence (\overline{P}_{n}(4))_{n≥1} is now referenced as \underline{A386706} in the OEIS [12]. According to Kimberling’s remark in the OEIS [12, \underline{A001834}], the sequence (F_{n−1}(4))_{n≥1} consist of the numerators p_{n} of the even-rank convergents p_{n}/q_{n} to \sqrt{3}; these are the convergents that are smaller than \sqrt{3}.

The sequence (\overline{P}_{n}(5))_{n≥1} is now \underline{A387017} and the sequence (F_{n−1}(5))_{n≥1} is \underline{A030221} in the OEIS [12]. The latter consists of the values of Chebyshev even-indexed U-polynomials at \sqrt{7}/2.

4.2 Odd divisors

Now we give a formula for \overline{P}_{n}(X) as a linear combination of the polynomials F_{k}(X), each appearance of F_{k}(X) being indexed by an odd divisor of n.

Recall that if we express n (≥ 1) as the product n = 2^{a}p_{1}^{a_{1}}p_{2}^{a_{2}} ⋯ p_{r}^{a_{r}}, where p_{1}, p_{2}, …, p_{r} are distinct odd primes and a, a_{1}, a_{2}, …, a_{r} are nonnegative integers, then the number of odd divisors of n (including 1) is equal to

(a_{1} + 1)(a_{2} + 1) ⋯ (a_{r} + 1) ≥ 1.

Observe that (a_{1} + 1)(a_{2} + 1) ⋯ (a_{r} + 1) = 1 if and only if n is a power of 2; otherwise, the number of odd divisors of n is at least 2.

For n ≥ 1 and every odd divisor d of n, define r_{n}(d) to be the integer

r_{n}(d) = \frac{n}{d} − \frac{d + 1}{2} .  (17)

When d is the trivial divisor 1, we have r_{n}(1) = n − 1.

Let us state our main result for \overline{P}_{n}(X).

Theorem 16. For all n ≥ 1,

\overline{P}_{n}(X) = ∑_{{d|n, d odd \atop rn(d)≥0}} F_{r_{n}(d)}(X) − ∑_{{d|n, d odd \atop rn(d)<0}} F_{−r_{n}(d)−1}(X).

The number of terms F_{r}(X) in the previous formula is clearly equal to the number of odd divisors of n. The proof of Theorem 16 will be given in Section 6.

In Table 5 each polynomial \overline{P}_{n}(X) (1 ≤ n ≤ 16) is expressed as a sum of the polynomials \overline{T}_{k}(X) as well as a linear combination of the polynomials F_{k}(X). In order to save space we left out the indeterminate X from the table.

n  As sums of \overline{T}_{k}  In terms of F_{k}
1  1  F_{0}
2  1 + \overline{T}_{1}  F_{1}
3  \overline{T}_{1} + \overline{T}_{2}  F_{2} − F_{0}
4  1 + \overline{T}_{1} + \overline{T}_{2} + \overline{T}_{3}  F_{3}
5  \overline{T}_{2} + \overline{T}_{3} + \overline{T}_{4}  F_{4} − F_{1}
6  \overline{T}_{0} + \overline{T}_{1} + \overline{T}_{2} + \overline{T}_{3} + \overline{T}_{4} + \overline{T}_{5}  F_{5} + F_{0}
7  \overline{T}_{3} + \overline{T}_{4} + \overline{T}_{5} + \overline{T}_{6}  F_{6} − F_{2}
8  1 + \overline{T}_{1} + \overline{T}_{2} + \overline{T}_{3} + \overline{T}_{4} + \overline{T}_{5} + \overline{T}_{6} + \overline{T}_{7}  F_{7}
9  1 + \overline{T}_{1} + \overline{T}_{4} + \overline{T}_{5} + \overline{T}_{6} + \overline{T}_{7} + \overline{T}_{8}  F_{8} − F_{3} + F_{1}
10 \overline{T}_{1} + \overline{T}_{2} + \overline{T}_{3} + \overline{T}_{4} + \overline{T}_{5} + \overline{T}_{6} + \overline{T}_{7} + \overline{T}_{8} + \overline{T}_{9}  F_{9} − F_{0}
11  \overline{T}_{5} + \overline{T}_{6} + \overline{T}_{7} + \overline{T}_{8} + \overline{T}_{9} + \overline{T}_{10}  F_{10} − F_{4}
\overline{T}_{0} + 2\overline{T}_{1} + 2\overline{T}_{2} + \overline{T}_{3} + \overline{T}_{4} + \overline{T}_{5}
12  +\overline{T}_{6} + \overline{T}_{7} + \overline{T}_{8} + \overline{T}_{9} + \overline{T}_{10} + \overline{T}_{11}  F_{11} + F_{2}
13  \overline{T}_{6} + \overline{T}_{7} + \overline{T}_{8} + \overline{T}_{9} + \overline{T}_{10} + \overline{T}_{11} + \overline{T}_{12}  F_{12} − F_{5}
\overline{T}_{2} + \overline{T}_{3} + \overline{T}_{4} + \overline{T}_{5} + \overline{T}_{6} + \overline{T}_{7}
14  +\overline{T}_{8} + \overline{T}_{9} + \overline{T}_{10} + \overline{T}_{11} + \overline{T}_{12} + \overline{T}_{13}  F_{13} − F_{1}
\overline{T}_{0} + \overline{T}_{1} + \overline{T}_{2} + \overline{T}_{3} + \overline{T}_{7} + \overline{T}_{8}  F_{14}(X) − F_{6}(X)
15  +\overline{T}_{9} + \overline{T}_{10} + \overline{T}_{11} + \overline{T}_{12} + \overline{T}_{13} + \overline{T}_{14}  + F_{3}(X) + F_{0}(X)
1 + \overline{T}_{1} + \overline{T}_{2} + \overline{T}_{3} + \overline{T}_{4} + \overline{T}_{5} + \overline{T}_{6} + \overline{T}_{7}
16 +\overline{T}_{8} + \overline{T}_{9} + \overline{T}_{10} + \overline{T}_{11} + \overline{T}_{12} + \overline{T}_{13} + \overline{T}_{14} + \overline{T}_{15}  F_{15}

Table 5: Expressing \overline{P}_{n}(X) in terms of \overline{T}_{k}(X) and of F_{k}(X).

Since d = 1 is an odd divisor for every n ≥ 1 and r_{n}(1) = n − 1 ≥ 0, the polynomial F_{n−1}(X) always appears, with a positive sign, in the formula of Theorem 16.

We remarked above that only powers of 2 have a unique odd divisor, namely d = 1. This implies the following consequence of Theorem 16, which explains the coincidences \overline{P}_{n}(N) = F_{n−1}(N) (set in boldface) observed in Table 1 for N = 3, 4, and 5.

Corollary 17. We have \overline{P}_{n}(X) = F_{n−1}(X) if and only if n is a power of 2.

As special cases of Theorem 16, we obtain the following formulas for \overline{P}_{n}(X).

4.2.1 Two odd divisors

If n = p is an odd prime, then it has two odd divisors, namely 1 and p, so that the formula for \overline{P}_{p}(X) has two summands. We have

\overline{P}_{p}(X) = F_{p−1}(X) − F_{(p−3)/2}(X) = ∑_{m=(p−1)/2}^{p−1} \overline{T}_{m}(X).

Now consider the case n = 2^{a}p, where a ≥ 1 and p is an odd prime. Such an integer n also has exactly two odd divisors.

If r_{n}(p) = 2^{a} − (p + 1)/2 ≥ 0, which is equivalent to p ≤ 2^{a+1} − 1, then

\overline{P}_{2^{a}p}(X) = F_{2^{a}p−1}(X) + F_{2^{a}−(p+1)/2}(X).

For instance, \overline{P}_{6}(X) = F_{5}(X) + F_{0}(X) and \overline{P}_{12}(X) = F_{11}(X) + F_{2}(X)

If r_{n}(p) = 2^{a} − (p + 1)/2 < 0, which is equivalent to p > 2^{a+1} − 1, then

\overline{P}_{2^{a}p}(X) = F_{2^{a}p−1}(X) − F_{(p−1)/2−2^{a}}(X).

As special cases, \overline{P}_{10}(X) = F_{9}(X) − F_{0}(X) and \overline{P}_{14}(X) = F_{13}(X) − F_{1}(X).

4.2.2 Three odd divisors

If n = p^{2} for some odd prime p, then

\overline{P}_{p^{2}}(X) = F_{p^{2}−1}(X) − F_{(p^{2}−3)/2}(X) + F_{(p−1)/2}(X).

For instance, \overline{P}_{9}(X) = F_{8}(X) − F_{3}(X) + F_{1}(X).

4.2.3 Four odd divisors

If n = p^{3} for some odd prime p, then n has four odd divisors. We have

\overline{P}_{p^{3}}(X) = F_{p^{3}−1}(X) − F_{(p^{3}−3)/2}(X) + F_{(2p^{2}−p−1)/2}(X) − F_{(p^{2}−2p−1)/2}(X).

For p = 3, we obtain \overline{P}_{27}(X) = F_{26}(X) − F_{12}(X) + F_{7}(X) − F_{1}(X).

Similarly, consider an integer of the form n = 3p, where p is an odd prime ≥ 7. Then n has four odd divisors, namely 1, 3, p, 3p, and

\overline{P}_{3p}(X) = F_{3p−1}(X) − F_{3(p−1)/2} + F_{p−2}(X) − F_{(p−7)/2} .

For p = 5 and n = 15, we have \overline{P}_{15}(X) = F_{14}(X) − F_{6}(X) + F_{3}(X) + F_{0}(X).

Remark 18. In Table 1 we set the values \overline{P}_{n}(N) and F_{n−1}(N) differing by 1 in italics, which occurs for n = 3, 6, and 10. These quasi-coincidences between values can be explained as follows.

We have \overline{P}_{n}(X) = F_{n−1}(X) + 1 = F_{n−1}(X) + F_{0}(X) if and only if the integer n is an even perfect number; equivalently, n = 2^{a}p, where p = 2^{a+1} − 1 is a Mersenne prime such as 3, 7, 31, 127 (see the OEIS [12, \underline{A000668}]). The corresponding n are n = 6, 28, 496, 8128.

Similarly, \overline{P}_{n}(X) = F_{n−1}(X) − 1 = F_{n−1}(X) − F_{0}(X) if and only if n = 2^{a}p, where p = 2^{a+1} + 1 is a Fermat prime such as 3, 5, 17, 257 (see the OEIS [12, \underline{A000215}]). The corresponding n are 3, 10, 136, 32896.

In general, the formula for \overline{P}_{n}(X) in Theorem 16 contains ±F_{0}(X) as a summand if and only if n is triangular, i.e., n = r(r + 1)/2 for some r ≥ 1. The smallest triangular integers are 1, 3, 6, 10, 15, 21, 28, 36.

Remark 19. For which natural numbers n do we have \overline{P}_{n}(X) = F_{n−1}(X) ± F_{1}(X)?

We have \overline{P}_{n}(X) = F_{n−1}(X) + F_{1}(X) if and only if n = 2^{a}p, where p is a prime of the form p = 2^{a+1} − 3. Primes p = 5, 13, 29, 61 are of this form; the corresponding n are n = 20, 104, 464, 1952 (see \underline{A050415} and \underline{A181703} in the OEIS [12]).

Similarly, \overline{P}_{n}(X) = F_{n−1}(X) − F_{1}(X) if and only if n = 2^{a}p, where p is a prime of the form p = 2^{a+1} + 3. Primes p = 5, 7, 11, 19, 67 are of this form (see the OEIS [12, \underline{A057733}]); they correspond to n = 5, 14, 44, 152, 2144.

More generally, F_{1}(X) appears in the formula for \overline{P}_{n}(X) in Theorem 16 if and only if n = r(r + 3)/2 for some r ≥ 1; see the OEIS [12, \underline{A000096}] for a list of such n.

5 Formulas for C_{n}(q)

In order to prove Theorem 16 we need new expressions for the polynomial C_{n}(q). Recall that C_{n}(q) and \overline{P}_{n}(X) are related by the equalities

\frac{C_{n}(q)}{q^{n}} = \frac{(q − 1)^{2}}{q} \frac{P_{n}(q)}{q^{n−1}} = \frac{(q − 1)^{2}}{q} \overline{P}_{n}(q + q^{−1}).

5.1 Increasing sequences

We need the following material borrowed from Mason [11].

We call increasing sequence every finite nonempty ordered set of consecutive integers {a + 1, …, a + h} with smallest element a + 1 and largest element a + h. Here a is an integer (positive, negative or zero) and h is a positive integer. We denote this set by IS(a, h); it has h elements. An increasing sequence IS(a, h) is called positive if a ≥ 0 and negative if a < 0. It is called odd if h is odd and even if h is even.

We say that an integer n ≥ 1 is represented by IS(a, h), and we write

IS(a, h) ⊧ n,

if n is equal to the sum of all elements of IS(a, h).

There is an involution IS(a, h) ↦ IS(ǎ, ȟ) on increasing sequences determined by

a + ǎ + 1 = 0 and ǎ + ȟ = a + h.  (18)

If IS(a, h) represents n, so does IS(ǎ, ȟ). Since ȟ − h = a − ǎ = 2a + 1, we conclude that h and ȟ are of opposite parity. In other words, IS(a, h) is even (resp., odd) if and only if IS(ǎ, ȟ) is odd (resp., even). Moreover, if IS(a, h) is positive (resp., negative), then IS(ǎ, ȟ) is negative (resp., positive).

Let n ≥ 1 be a positive integer. With every odd divisor d of n we associate the odd increasing sequence IS(a, h), where

a = \frac{n}{d} − \frac{d + 1}{2} and h = d.  (19)

It is centered around n/d, namely we have

IS(a, h) = \{\frac{n}{d} − \frac{d − 1}{2}, …, \frac{n}{d} − 1, \frac{n}{d}, \frac{n}{d} + 1, …, \frac{n}{d} + \frac{d − 1}{2}\} .  (20)

This odd increasing sequence may be positive or negative, depending on d. We have IS(a, h) ⊧ n.

Starting from a = n/d − (d + 1)/2 and h = d, we have

ǎ = −\frac{n}{d} + \frac{d − 1}{2} and ȟ = \frac{2n}{d}.  (21)

We thus obtain the even increasing sequence

IS(ǎ, ȟ) = \{−\frac{n}{d} + \frac{d + 1}{2}, …, \frac{n}{d} + \frac{d − 1}{2}\} ⊧ n.  (22)

Clearly, if IS(a, h) is positive, then IS(a, h) ⊂ IS(ǎ, ȟ) and

IS(ǎ, ȟ) \ IS(a, h) = \{−\frac{n}{d} + \frac{d + 1}{2}, …, \frac{n}{d} − \frac{d + 1}{2}\} .  (23)

If IS(a, h) is negative, then IS(ǎ, ȟ) ⊂ IS(a, h) and

IS(a, h) \ IS(ǎ, ȟ) = \{\frac{n}{d} − \frac{d − 1}{2}, …, −\frac{n}{d} + \frac{d − 1}{2}\} .  (24)

For both pairs (a, h) and (ǎ, ȟ) we have the same relation, namely

\frac{h(h + 2a + 1)}{2} = n = \frac{ȟ(ȟ + 2ǎ + 1)}{2}.  (25)

Conversely, starting from an increasing sequence IS(a, h) we obtain an odd divisor d of n as follows: d is equal to the only odd element of {h, ȟ}. In this way we have a bijection between the set of odd divisors of n and the set of positive increasing sequences representing n, which is in bijection with the set of negative increasing sequences representing n.

Suppose that given n ≥ 1 we have a pair (a, h) of integers with h ≥ 1 verifying Equation (25), which we rewrite as h(h + 2a + 1) = 2n. If h is odd, hence coprime to 2, then d = h is an odd divisor of n and a = n/d − (d + 1)/2, as in (19). If h is even, then d = h + 2a + 1 is odd; being a divisor of 2n, it is an odd divisor of n; in this case h = 2n/d and a = −n/d + (d − 1)/2, as in (21).

Example 20. If n is a power of 2, then it has only one odd divisor, namely d = 1; the corresponding positive increasing sequence is

IS(n − 1, 1) = {n}

and its negative counterpart is

IS(−n, 2n) = {−(n − 1), …, −1, 0, 1, …, n − 1, n}.

Example 21. Every other integer n has odd divisors d ≠ 1, hence more than one positive (or negative) increasing sequences. For instance, consider n = 18 with odd divisors d = 3 and d = 9.

If d = 3, then a = 4, h = 3, ǎ = −5, ȟ = 12, and

IS(4, 3) = {5, 6, 7} and IS(−5, 12) = {−4, −3, …, 3, 4, 5, 6, 7}.

If d = 9, then a = −3, h = 9, ǎ = 2, ȟ = 4, and

IS(−3, 9) = {−2, −1, 0, 1, 2, 3, 4, 5, 6} and IS(2, 4) = {3, 4, 5, 6}.

5.2 New formulas for C_{n}(q)

The authors [10, Th. 1.1] gave the following explicit expression for C_{n}(q):

\frac{C_{n}(q)}{q^{n}} = c_{n,0} + ∑_{i=1}^{n} c_{n,i} (q^{i} + q^{−i}) ,

where

c_{n,0} = 2(−1)^{r}  (26)

if n = r(r + 1)/2 for some positive integer r and c_{n,0} = 0 otherwise. For the remaining coefficients c_{n,i} (1 ≤ i ≤ n) we have

c_{n,i} = \begin{cases}(−1)^{k}, & if n = k(k + 2i + 1)/2 for some integer k ≥ 1; \\ (−1)^{k−1}, & if n = k(k + 2i − 1)/2 for some integer k ≥ 1; \\ 0, & otherwise. \end{cases}  (27)

Observe that in (27) the first two conditions are mutually exclusive, as shown by the authors [10, Lemma 3.5 (ii)]. This may also be verified as follows: suppose

k(k + 2i + 1) = h(h + 2i − 1)

with i, h, k ≥ 1; then k^{2} + 2ik + k = h^{2} + 2ih − h, which can be rewritten as

(k − h + 1)(k + h) + 2i(k − h) = 0.

It is readily seen that the left-hand side cannot vanish, neither in the case k ≥ h, nor in the case k < h.

Lemma 22. We have

\frac{C_{n}(q)}{q^{n}} = ∑ (−1)^{h} (q^{a} + q^{−a}) ,

where the summation is over all h ∈ ℤ_{≥1} and a ∈ ℤ such that n = h(h+1+2a)/2. Moreover, if n has such a representation and |a| is given, then the pair (a, h) is unique.

Proof. It follows from (26) that both sides have the same constant term.

Henceforth we concentrate on the case when a is a nonzero integer. Let i ≥ 1. Suppose that n = k(k + 2i + 1)/2 with k ≥ 1 as in the first row of (27); then n = h(h + 2a + 1)/2 with h = k ≥ 1, a = i ∈ ℤ \ {0}, and (−1)^{k} = (−1)^{h}.

Now suppose that n = k(k + 2i − 1)/2 with k ≥ 1 as in the second row of (27); then n = h(h + 2a + 1)/2 with h = k + 2i − 1 ≥ 1, a = −i ∈ ℤ \ {0}, and (−1)^{k−1} = (−1)^{h}.

Conversely, let n = h(h + 2a + 1)/2 with h ≥ 1, i ∈ ℤ, and a ≠ 0. Then either a ≥ 1, and then n = k(k + 2i + 1)/2 with k = h, i = a ≥ 1, and (−1)^{k} = (−1)^{h}; or a < 0, and then n = k(k + 2i − 1)/2, k = h + 2a + 1 ≥ 1, i = −a > 0, and (−1)^{k−1} = (−1)^{h}.

This proves the lemma in view of the observation made just before its statement.

We have the following new formulas for C_{n}(q).

Theorem 23. For each integer n ≥ 1 we have

\frac{C_{n}(q)}{q^{n}} = ∑ (−1)^{h} (q^{a} + q^{−a}) ,

where the summation is taken over all increasing sequences IS(a, h) such that IS(a, h) ⊧ n. Moreover, for given |a|, there is a unique increasing sequence IS(a, h) with IS(a, h) ⊧ n.

We also have

\frac{C_{n}(q)}{q^{n}} = ∑_{d|n, d odd} (q^{\frac{n}{d} − \frac{d−1}{2}} + q^{− \frac{n}{d} + \frac{d−1}{2}} − q^{\frac{n}{d} − \frac{d+1}{2}} − q^{− \frac{n}{d} + \frac{d+1}{2}} ) .

In the previous sum, all monomials ≠ q^{0} are distinct.

Proof. The first formula follows from Lemma 22 since the sum of the elements in IS(a, h) is equal to

a + 1 + a + 2 + ⋯ + a + h = ha + h(h + 1)/2 = h(h + 2a + 1)/2.

As in § 5.1, with each odd divisor d of n we associate the two increasing sequences IS(a, h) and IS(ǎ, ȟ), respectively odd and even, defined by (20) and (22). All increasing sequences representing n are obtained in this way. The second formula then follows from the first one: the first two terms correspond to IS(ǎ, ȟ) and the last two to IS(a, h).

The previous result immediately implies the following.

Corollary 24. The sum of the absolute values of the coefficients of C_{n}(q) is equal to four times the number of odd divisors of n.

5.3 Zeta functions

The following consequences of Theorem 23 may be of interest to algebraic geometers.

Recall that the local zeta function Z_{H^{n}/𝔽_{q}}(t) of the Hilbert scheme H^{n} of n points on the two-dimensional torus over the finite field 𝔽_{q} is the formal power series

Z_{X/𝔽_{q}}(t) = exp (∑_{m≥1} C_{n}(q^{m}) \frac{t^{m}}{m} ) .  (28)

The authors [10, Th. 2.1] showed that Z_{X/𝔽_{q}}(t) is equal to the formal power series expansion of the following rational function:

Z_{H^{n}/𝔽_{q}}(t) = \frac{1}{(1 − q^{n}t)^{c_{n,0}}} ∏_{i=1}^{n} \frac{1}{[(1 − q^{n+i}t)(1 − q^{n−i}t)]^{c_{n,i}}} ,

where c_{n,i} are the coefficients of C_{n}(q) defined in § 5.2. Rewriting this formula in view of Theorem 23 yields the following statement, where r_{n}(d) = n/d − (d + 1)/2 is the integer introduced in (17).

Proposition 25. For n ≥ 1 we have

Z_{H^{n}/𝔽_{q}}(t) = ∏_{d|n, d odd} \frac{(1 − q^{n+r_{n}(d)}t)(1 − q^{n−r_{n}(d)}t)}{(1 − q^{n+r_{n}(d)+1}t)(1 − q^{n−r_{n}(d)−1}t)}.

The right-hand side is a rational function whose numerator and denominator are factored into degree-one polynomials. Clearly, the number of such factors in the numerator (resp., in the denominator) is equal to twice the number of odd divisors of n.

Let us display the product formula for Z_{H^{n}/𝔽_{q}}(t) in two special cases. For n = 4, which has only 1 as an odd divisor, we have r_{4}(1) = 3. Hence,

Z_{H^{4}/𝔽_{q}}(t) = \frac{(1 − q^{7}t)(1 − qt)}{(1 − q^{8}t)(1 − t)}.

For n = 3, which has two odd divisors, we have r_{3}(1) = 2 and r_{3}(3) = −1. Hence,

Z_{H^{3}/𝔽_{q}}(t) = \frac{(1 − q^{5}t)(1 − qt)}{(1 − q^{6}t)(1 − t)} · \frac{(1 − q^{2}t)(1 − q^{4}t)}{(1 − q^{3}t)^{2}}.

Proposition 25 allows us to give a similar formula for the Hasse–Weil zeta function ζ_{H^{n}}(s) of the above Hilbert scheme; this zeta function is defined over the complex numbers by

ζ_{H^{n}}(s) = ∏_{p prime} Z_{H^{n}/𝔽_{p}}(p^{−s}), (s ∈ ℂ)

where the product is taken over all prime integers p. As an immediate consequence of the formula for the local zeta functions Z_{H^{n}/𝔽_{q}}(t) we have

ζ_{H^{n}}(s) = ∏_{d|n, d odd} \frac{ζ(s − n − r_{n}(d)) ζ(s − n + r_{n}(d))}{ζ(s − n − r_{n}(d) − 1) ζ(s − n + r_{n}(d) + 1)} ,  (29)

where ζ(s) is Riemann’s zeta function. Recall from [10, Sect. 2] that the Hasse–Weil zeta function satisfies the simple functional equation

ζ_{H^{n}}(s) = ζ_{H^{n}}(2n − s).  (30)

6 Proof of Theorem 16

The following lemma exhibits a crucial link between the polynomials F_{r}(X) and the expression in parentheses in the second formula of Theorem 23.

Lemma 26. For r ≥ 0 we have

q^{r+1} + q^{−r−1} − q^{r} − q^{−r} = q^{−1}(q − 1)^{2}F_{r}(q + q^{−1}).

Proof. The formula can be rephrased in terms of polynomials in the indeterminate X as \overline{T}_{r+1}(X) − \overline{T}_{r}(X) = (X − 2)F_{r}(X). By (15) the latter is equivalent to

(F_{r+1}(X) − F_{r}(X)) − (F_{r}(X) − F_{r−1}(X)) = XF_{r}(X) − 2F_{r}(X),

hence to the linear recurrence relation of Proposition 11.

Proof of Theorem 16. It follows from the second formula of Theorem 23 that

q^{−1}(q − 1)^{2} \frac{P_{n}(q)}{q^{n−1}} = \frac{C_{n}(q)}{q^{n}} = ∑_{d|n, d odd} (q^{\frac{n}{d} − \frac{d−1}{2}} + q^{− \frac{n}{d} + \frac{d−1}{2}} − q^{\frac{n}{d} − \frac{d+1}{2}} − q^{− \frac{n}{d} + \frac{d+1}{2}} ) .

We partition the previous sum into two sums depending on the sign of r_{n}(d) = n/d−(d+1)/2. We obtain

q^{−1}(q − 1)^{2} \frac{P_{n}(q)}{q^{n−1}} = ∑_{{d|n, d odd \atop rn(d)≥0}} (q^{\frac{n}{d} − \frac{d−1}{2}} + q^{− \frac{n}{d} + \frac{d−1}{2}} − q^{\frac{n}{d} − \frac{d+1}{2}} − q^{− \frac{n}{d} + \frac{d+1}{2}} )

+ ∑_{{d|n, d odd \atop rn(d)<0}} (q^{\frac{n}{d} − \frac{d−1}{2}} + q^{− \frac{n}{d} + \frac{d−1}{2}} − q^{\frac{n}{d} − \frac{d+1}{2}} − q^{− \frac{n}{d} + \frac{d+1}{2}} ) .

Now replacing r by r_{n}(d) in Lemma 26, we see that the sum of monomials corresponding to r_{n}(d) ≥ 0 is equal to

q^{−1}(q − 1)^{2} ∑_{{d|n, d odd \atop rn(d)≥0}} F_{r_{n}(d)}(q + q^{−1}).

Replacing r by −r_{n}(d)−1 in Lemma 26, we observe that the sum of monomials corresponding to r_{n}(d) < 0, equivalently to −r_{n}(d) − 1 ≥ 0, is equal to

q^{−1}(q − 1)^{2} ∑_{{d|n, d odd \atop rn(d)<0}} F_{−r_{n}(d)−1}(q + q^{−1}).

To conclude, it suffices to divide by q^{−1}(q − 1)^{2} and to appeal to the equality P_{n}(q)/q^{n−1} = \overline{P}_{n}(q + q^{−1}).

We close this section with another formula for P_{n}(q)/q^{n−1}.

Proposition 27. We have

\frac{P_{n}(q)}{q^{n−1}} = ∑_{{d|n, d odd \atop rn(d)≥0}} ∑_{i∈IS(ǎ,ȟ)\IS(a,h)} q^{i} − ∑_{{d|n, d odd \atop rn(d)<0}} ∑_{i∈IS(a,h)\IS(ǎ,ȟ)} q^{i},

where a = r_{n}(d) and ǎ = −r_{n}(d) − 1, and IS(a, h) and IS(ǎ, ȟ) are defined respectively by (20) and (22).

Proof. It follows from Theorem 16 and the explicit descriptions (23) and (24).

Remark 28. Sums of powers of q indexed by odd divisors have also appeared in work of Caballero [4] (especially in Chapter II).

7 Acknowledgments

We are grateful to José Bastidas Olaya for his help with SageMath and to Václav Kotěšovec for having corrected the value \overline{P}_{7}(4) in Table 1. We thank Christophe Pouzat and Marcus Slupinski for suggesting the title of the present paper.

References

[1] M. Abramowitz and I. A. Stegun (eds.), Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, Dover, 1972.

[2] T. M. Apostol, Introduction to Analytic Number Theory. Springer Verlag, 1986.

[3] J. Berstel and C. Reutenauer, Noncommutative Rational Series with Applications, Encyclopedia of Mathematics and its Applications, 137, Cambridge University Press, 2011.

[4] J. M. R. Caballero, Propriétés arithmétiques du E-polynôme du schéma de Hilbert de n points dans le tore bidimensionnel, Mémoire de maîtrise en mathématiques, Université du Québec à Montréal, 2018.

[5] J. M. R. Caballero, On Kassel-Reutenauer q-analog of the sum of divisors and the ring 𝔽_{3}[X]/X^{2}𝔽_{3}[X], Finite Fields Appl. 51 (2018), 183–190.

[6] N. J. Fine, Basic Hypergeometric Series and Applications, Mathematical Surveys and Monographs, 27, American Mathematical Society, 1988.

[7] A. F. Horadam, Vieta polynomials, Fibonacci Quarterly 40 (2002), 223–232.

[8] C. Kassel and C. Reutenauer, The Fourier expansion of η(z)η(2z)η(3z)/η(6z), Arch. Math. (Basel) 108 (2017), 453–463.

[9] C. Kassel and C. Reutenauer, Counting the ideals of given codimension of the algebra of Laurent polynomials in two variables, Michigan Math. J. 67 (2018), 715–741.

[10] C. Kassel and C. Reutenauer, Complete determination of the zeta function of the Hilbert scheme of n points on a two-dimensional torus, Ramanujan J. 46 (2018), 633–655.

[11] T. E. Mason, On the representation of an integer as the sum of consecutive integers, Amer. Math. Monthly 19 (1912), 46–50.

[12] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2026. Published

electronically at https://oeis.org/.

[13] T. J. Rivlin, Chebyshev Polynomials, Wiley, 1990.

2020 Mathematics Subject Classification: Primary 11T55; Secondary 05A30, 14N10. Keywords: integer sequence, generating function, infinite product, polynomial, Chebyshev polynomial, approximation, multiplicative function.

(Concerned with sequences \underline{A000096}, \underline{A000203}, \underline{A000215}, \underline{A000668}, \underline{A001834}, \underline{A002325}, \underline{A002654}, \underline{A002878}, \underline{A030221}, \underline{A050415}, \underline{A057733}, \underline{A113063}, \underline{A181703}, \underline{A329156}, \underline{A386706}, and \underline{A387017}.)

Received September 19 2025; revised version received March 2 2026. Published in Journal of Integer Sequences, July 4 2026.

Return to Journal of Integer Sequences home page.