\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand\HH{\mathcal H}
\newcommand\card{\mathrm{card}}
\newcommand\tr{\mathrm{tr}}
\newcommand\Id{\mathrm{Id}}
\newcommand\ZZ{\mathbb{Z}}
\newcommand\CC{\mathbb{C}}
\newcommand\FF{\mathbb{F}}
\newcommand\Pg{\overline{P}}
\newcommand\TT{\overline{T}}
\newcommand\IS{\mathrm{IS}}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf Pairs of Intertwined Integer Sequences
}
\vskip 1cm
\large
Christian Kassel\\
Institut de Recherche Math\'e\-ma\-tique Avanc\'ee\\
Universit\'e de Strasbourg \& CNRS \\
7~rue Ren\'e-Descartes\\
67084 Strasbourg\\
France\\
\href{mailto:kassel@math.unistra.fr}{\tt kassel@math.unistra.fr} \\
\ \\
Christophe Reutenauer\\
Math\'ematiques \\
Universit\'e du Qu\'ebec \`a Mont\-r\'eal\\
CP 8888, succ.\ centre-ville\\
Montr\'eal, PQ  H3C 3P8 \\ 
Canada \\
\href{mailto:reutenauer.christophe@uqam.ca}{\tt reutenauer.christophe@uqam.ca} \\
\end{center}

\vskip .2 in
\begin{abstract}
In previous work we computed the number~$C_n(q)$ of ideals of codimension~$n$ of 
the algebra $\FF_q[x,y,x^{-1}, y^{-1}]$ of two-variable Laurent polynomials over a finite field~$\FF_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\geq 1$ let~$\Pg_n(X) \in \ZZ[X]$ be the degree~$n-1$ polynomial such that 
$\Pg_n(q+q^{-1}) = P_n(q)/q^{n-1}$.
In this article we show that for every integer~$N$ the integer value $\Pg_n(N)$ is close to the value at~$N$ of the 
degree~$n-1$ polynomial $F_{n-1}(X) = 1 + \sum_{k=1}^{n-1} \, \TT_k(X)$,
which is a sum of monic versions $\TT_k(X)$ of Chebyshev polynomials of the first kind.
We give a precise formula for~$\Pg_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, $\Pg_n(X) = F_{n-1}(X)$ if and only if $n$ is a power of~$2$.
We exhibit similar formulas for~$C_n(q)$.
\end{abstract}


\section{Introduction}\label{sec-intro}

In this article, for each integer~$N$ we produce a pair $(\Pg_n(N), (F_{n-1}(N))_{n\geq 1}$ of integer sequences.
Both sequences, though of differing origin,
consist of amazingly close elements. Some of them do even coincide: we have $\Pg_n(N) = F_{n-1}(N)$ whenever $n$ is a power of~$2$.
The reader is invited to examine Table~\ref{table-values} 
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{table}[ht]
\renewcommand\arraystretch{1.30}
\noindent\[
\centering
\begin{array}{|c||c|c||c|c||c|c||}
\hline
n &  \Pg_n(3) & F_{n-1}(3) &  \Pg_n(4) & F_{n-1}(4) & \Pg_n(5) & F_{n-1}(5) \\
\hline\hline
{1}  & \textbf{1} &  \textbf{1} &\textbf{1}  & \textbf{1}  & \textbf{1} & \textbf{1}\\ 
\hline
{2} &  \textbf{4} & \textbf{4} & \textbf{5} & \textbf{5} & \textbf{6}  & \textbf{6} \\
\hline
3 &  \textit{10} & \textit{11} &  \textit{18} & \textit{19} & \textit{28} & \textit{29} \\ 
\hline
{4} &  \textbf{29}  & \textbf{29}  & \textbf{71} & \textbf{71} & \textbf{139} & \textbf{139}  \\ 
\hline
5 &   72 & 76 & 260 & 265 & 660 & 666\\ 
\hline
6 &    \textit{200} &  \textit{199} & \textit{990} & \textit{989} & \textit{3192} & \textit{3191}  \\
\hline
7 &  510  & 521  &  3672 & 3691 & 15260 & 15289 \\ 
\hline
{8} &  \textbf{1364} & \textbf{1364} & \textbf{13775} & \textbf{13775} & \textbf{73254} & \textbf{73254} \\ 
\hline
9 &  3546  & 3571  & 51343 & 51409 & 350848 &  350981 \\
\hline
10 &  \textit{9348}  &  \textit{9349}  & \textit{191860} & \textit{191861} & \textit{1681650} & \textit{1681651}  \\
\hline
11 &  24400  & 24476  & 715770 & 716035 & 8056608 & 8057274 \\
\hline
12 &  64090 & 64079 & 2672298 & 2672279 & 38604748 & 38604719 \\
\hline
13 & 167562  & 167761 & 9972092 & 9973081 & 184963130 & 184966321 \\
\hline
14 & 439200  & 439204 & 37220040 & 37220045 &886226880 & 886226886 \\
\hline
15 &  1149360 &1149851  & 138903480 & 138907099 &4246152960 & 4246168109 \\
\hline
{16} & \textbf{3010349} & \textbf{3010349} & \textbf{518408351} & \textbf{518408351} & \textbf{20344613659} & \textbf{20344613659}\\
\hline
\end{array}
\]
\caption{Values of $\Pg_n(N)$ and $F_{n-1}(N)$ for $N = 3,4,5$.}\label{table-values}
\end{table}

Let us now describe the components of such pairs. Starting with~$\Pg_n(N)$,
let~$\FF_q$ be a finite field of cardinality~$q$ and $\FF_q[x,y,x^{-1}, y^{-1}]$ be the algebra of
two-variable Laurent polynomials with coefficients in~$\FF_q$.
For every integer $n\geq 1$, let $C_n(q)$ denote the number of ideals~$I$ of codimension~$n$ of~$\FF_q[x,y,x^{-1}, y^{-1}]$, 
i.e., such that the quotient $\FF_q[x,y,x^{-1}, y^{-1}]/I$ is a $\FF_q$-vector space of dimension~$n$.
(For algebraic geometers, $C_n(q)$ counts the $\FF_q$-points of the Hil\-bert scheme 
of $n$~points on the two-dimensional torus.)
The authors\ \cite{KR2} 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~\cite[Th.\ 1.1]{KR3} gave explicit formulas for the coefficients of~$C_n(q)$; 
also see \S~\ref{ssec-Cnq} 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 \emph{nonnegative};
actually, each coefficient of~$P_n(q)$ can be expressed as the number of divisors of~$n$ in a certain real interval;
see~\cite[Thm.\ 1.3]{KR3} and \S~\ref{ssec-approx} below.

The authors~\cite[Thm.\ 1.6]{KR3} 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) = \sigma(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 \geq 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~$\Pg_n(X)$ 
in the variable~$X$, defined by
\begin{equation}\label{Pg-P}
\Pg_n(q + q^{-1}) = P_n(q)/q^{n-1} .
\end{equation}
(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~$\Pg_n(X)$ at integers~$N$.

Searching the \emph{On-Line Encyclopedia of Integer Sequences} (OEIS)~\cite{OEIS}
for the sequence 
\[
(\Pg_1(5), \Pg_2(5),\Pg_3(5), \Pg_4(5), \Pg_5(5), \Pg_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 $\Pg_n(3)$ and $\Pg_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:
\begin{equation}\label{gf-F}
\sum_{k\geq 0} \, F_k(X) \, t^k 
= \frac{1+t}{1 - Xt + t^2} \, .
\end{equation}
It turns out that each polynomial $F_k(X)$ is of degree~$k-1$, has integer coefficients, and we have
\begin{equation}\label{eq-FFTT}
F_k(X) = 1 + \sum_{m=1}^{k} \, \TT_m(X) ,
\end{equation}
which is the sum of the monic versions~$\TT_m(X)$ of the Chebyshev polynomials of the first kind
defined in \S~\ref{ssec-Tchb} below.

With this notation we establish that each~$\Pg_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~\ref{th-approx} for a precise statement). 

More interestingly, $\Pg_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$:
\begin{equation}\label{formula-PFodd}
\Pg_n(X) = \sum_{d | n, \, d \, \mathrm{odd} \atop r_n(d) \geq 0} \, F_{r_n(d)}(X) 
- \sum_{d | n, \, d \, \mathrm{odd} \atop r_n(d) <0} \, F_{-r_n(d) -1}(X) ,
\end{equation}
where $r_n(d) = {n/d} - {(d+1)/2}$; see Theorem~\ref{th-PFodd}.
For $d=1$ we have $r_n(1) = n-1$, which implies the presence of~$F_{n-1}(X)$ in~\eqref{formula-PFodd} for all $n\geq 1$.

Since the powers of~$2$ are the only integers with a unique odd divisor, namely $d=1$, 
we have $\Pg_n(X) = F_{n-1}(X)$ if and only if $n$ is a power of~$2$.
This explains the coincidences observed in Table~\ref{table-values}.

We deduce Formula~\eqref{formula-PFodd} from the following new expression for~$C_n(q)$:
\begin{equation}\label{formula-Cnodd}
C_n(q) = q^n \, \sum_{d | n , \, d \, \mathrm{odd}} \, 
\left( 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}} \right) .
\end{equation}
See Theorem~\ref{th-Cn}.

Formula~\eqref{formula-Cnodd} 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 \S~\ref{ssec-zeta}).

Let us detail the content of each section.
In Section~\ref{sec-Pn}, for each $n\geq 1$ we define the degree~$n-1$ polynomial~$\Pg_n(X)$ by~\eqref{Pg-P}.
As mentioned above, the integers of interest to us are the values~$\Pg_n(N)$ at arbitrary integers~$N$.
Building on previous work~\cite{KR3}, 
we show that the function $n \mapsto |\Pg_n(N)|$ is multiplicative if $N= -2, -1, 0$ or~$2$; 
for all remaining integer values of~$N$ it is not multiplicative.

Section~\ref{sec-aux} is devoted to the monic versions $\TT_k(X)$ of the Chebyshev polynomials of the first kind
and to the polynomials~$F_k(X)$ defined above.

In Section~\ref{sec-resultsP} we state the results on~$\Pg_n(X)$ mentioned above.
Theorem~\ref{th-approx} and Theorem~\ref{th-PFodd} with Formula~\eqref{formula-PFodd} are the main results.
As special cases of~\eqref{formula-PFodd} we obtain formulas for~$P_n(X)$ in terms of the polynomials~$F_k(X)$ 
for various families of integers~$n$.

Section~\ref{sec-Cnq} is devoted to the polynomials~$C_n(q)$:
we prove~\eqref{formula-Cnodd} and state the formulas for the zeta functions mentioned above.
In Section~\ref{pf-th-PFodd} we use the results of Section~\ref{sec-Cnq} to prove Theorem~\ref{th-PFodd}.


\section{The polynomials $\Pg_n(X)$}\label{sec-Pn}


\subsection{Definition and basic properties}\label{ssec-defPn}

For every positive integer~$n$ we define the degree $n-1$ polynomial $\Pg_n(X)$ by
\begin{equation}\label{def-Pgn}
\Pg_n(q + q^{-1}) = P_n(q)/q^{n-1} ,
\end{equation}
where $P_n(q)$ was introduced in Section~\ref{sec-intro}. 
This makes sense since $P_n(q)$ is a palindromic polynomial of degree~$2n-2$. 
As $P_n(q)$ has integer coefficients, so does~$\Pg_n(X)$.

As a consequence of~\cite[Cor.\ 1.4]{KR2}, we have the equality of formal power series
\begin{equation*}\label{gf-Pnq}
1 + (q + q^{-1} - 2) \sum_{n\geq 1} \, \frac{P_n(q)}{q^{n-1}}  \, t^n
= \prod_{i\geq 1}\, \frac{(1-t^i)^2}{1-(q+q^{-1})t^i + t^{2i}} \, .
\end{equation*}
This translates into the following equality for the polynomials~$\Pg_n (X)$:
\begin{equation}\label{gf-Pgn}
1 + (X - 2) \sum_{n\geq 1} \, \Pg_n (X)  \, t^n
= \prod_{i\geq 1}\, \frac{(1-t^i)^2}{1- X t^i + t^{2i}} \, .
\end{equation}

The authors~\cite[Thm.\ 1.3]{KR3} established that each polynomial~$P_n(q)$ is of the form
\begin{equation}\label{Pn-coeff}
P_n(q) = a_{n,0}\, q^{n-1}  + \sum_{i=1}^{n-1} \, a_{n,i} \, \left( q^{n+i-1} + q^{n-i-1} \right) , 
\end{equation}
where the coefficients~$a_{n,i}$ are all \emph{nonnegative integers} (to be expressed explicitly in the proof of Lemma~\ref{lem-ani}).
It follows that for each positive integer~$n$,
\begin{equation}\label{PPTT}
\Pg_n(X) = a_{n,0}  + \sum_{i=1}^{n-1} \, a_{n,i} \, \TT_i(X) ,
\end{equation}
where $\TT_i(X)$ is the monic Chebyshev polynomial of degree~$i$ defined by~\eqref{defTT} below.
Since the coefficients~$a_{n,i}$ are nonnegative integers, 
each~$\Pg_n(X)$ is a \emph{sum} of the polynomials~$\TT_k(X)$.

A list of the polynomials $\Pg_n(X)$ for $1 \leq n \leq 12$ is given in Table~\ref{tablePP}.
It is based on the corresponding list of $P_n(q)$ in Table~2 of either~\cite{KR2} or~\cite{KR3}.

\begin{table}[H]
\renewcommand\arraystretch{1.25}
\noindent\[
\centering
\begin{array}{|c||c|}
\hline
n & \Pg_n(X) \\
\hline\hline
1 & 1   \\ 
\hline
2 & X + 1  \\
\hline
3 & X^2 + X - 2  \\ 
\hline
4 & X^3 + X^2 - 2X -1  \\ 
\hline
5 & X^4 + X^3 - 3 X^2 - 3X  \\ 
\hline
6 &  X^5 + X^4 - 4X^3 - 3 X^2 + 3X + 2   \\
\hline
7 & X^6 + X^5 - 5 X^4 -4 X^3 + 5X^2 + 2X  \\ 
\hline
8 &  X^7 +X^6 - 6X^5 - 5 X^4 + 10 X^3 + 6 X^2 - 4X -1  \\ 
\hline
9 &  X^8 + X^7 - 7 X^6 - 6 X^5 +15 X^4 + 9 X^3 - 11 X^2 - X +3  \\
\hline
10 & X^9 + X^8 -8 X^7 -7 X^6 + 21 X^5  + 15 X^4 - 20 X^3 - 10 X^2 + 5X   \\
\hline
&  X^{10} + X^9 - 9 X^8 - 8 X^7 + 28 X^6 + 21 X^5  \\
11 &   - 36 X^4 - 21 X^3 + 18 X^2 + 7X - 2  \\
\hline
&   X^{11} + X^{10} - 10 X^9 - 9 X^8 + 36 X^7 + 28 X^6  \\
12 & - 56 X^5 -35 X^4 + 35 X^3 + 16 X^2 - 5 X  -2  \\
\hline
\end{array}
\]
\caption{The polynomials $\Pg_n (X)$.}\label{tablePP}
\end{table}

The following result explains why all entries in Table~\ref{table-values} are positive.

\begin{proposition}
Let $N$ be an integer $\geq 2$. Then $\Pg_n(N) > 0$ for all $n \geq 1$.
\end{proposition}

\begin{proof}
This is a consequence of Proposition~\ref{TTpos} below and 
of the fact mentioned above that each $\Pg_n(X)$ is a sum of the $\TT_k(X)$.
\end{proof}

\subsection{Multiplicative values of $|P_n(q)|$ at roots of unity}\label{ssec-mult}

The content of this subsection is an addendum to \cite[Th.\ 1.6]{KR3}. It concerns the cases when $q + q^{-1} = N$
is an integer such that $-2 \leq N \leq 2$, 
equivalently when $q$ is a root of unity of order $d = 1, 2, 3, 4$ or~$6$. 

\begin{proposition}\label{prop-mult}
Let $q$ be a complex root of unity of order $d = 1, 2, 3$ or $4$. 
Then the sequence of nonnegative integers 
\begin{equation*}
\left |P_n(q) \right |  = \left | P_n(q)/q^{n-1} \right | =  \left |\Pg_n(q + q^{-1}) \right |
\end{equation*}
is multiplicative as a function of~$n$.
\end{proposition}

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

\begin{proof}
When $q = 1$, by \cite[Cor.\ 1.2]{KR2} we have $\Pg_n(2) = P_n(1) = \sigma(n)$, the sum of divisors of~$n$,
which is well-known to be multiplicative. See Apostol \cite[Sect.\ 2.13]{Ap} and the OEIS~\cite{OEIS} at \seqnum{A000203}.

For $q = -1$ we have $\Pg_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~\cite[\seqnum{A002654}]{OEIS} 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
$\Pg_n(-1) = P_n(j)/j^{n-1} = \lambda(n)$, where $\lambda(n)$ is the sequence \seqnum{A113063} in the OEIS~\cite{OEIS}.
Fine \cite[Sect.\ 32, p.\ 79]{Fi} states that $\lambda(n)$ is multiplicative. See also Caballero~\cite{RC2}.

Let $i$ be a square root of~$-1$. It follows again from~\cite[Th.\ 1.6]{KR3} that we have
\[
|\Pg_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 \seqnum{A002325} in the OEIS~\cite{OEIS}
is known to be multiplicative.
\end{proof}

The case when $q = \omega$ is a root of unity of order~$6$ is slightly more involved. 

\begin{proposition}\label{prop-mult1}
Let $\omega$ be a root of unity of order~$6$. 
Then for all pairs $(m,n)$ of coprime positive integers we have
\begin{equation*}
|P_m(\omega)| |P_n(\omega)| = |P_{mn}(\omega)| \; \text{when} \; (m,n) \equiv (0,1), (1,1)  \;  \text{or} \; (1,2) 
\hskip -10pt \pmod{3},
\end{equation*}
\begin{equation*}
|P_m(\omega)| |P_n(\omega)| = 2 \, |P_{mn}(\omega)| \quad \text{when} \;\; (m,n) \equiv (0,2)  \pmod{3},
\end{equation*}
\begin{equation*}
|P_m(\omega)| |P_n(\omega)| = 4 \, |P_{mn}(\omega)| \quad \text{when} \;\; (m,n) \equiv (2,2) \pmod{3}.
\end{equation*}
\end{proposition}

\begin{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~\cite[Th.\ 1.1]{KR1} and~\cite[Th.\ 1.6\,(d)]{KR3}:
\begin{equation*}
|P_n(\omega)| = 
\begin{cases}
r(n),  & \text{if $n \equiv 0 \pmod{3}$;}  \\
r(n)/4,  & \text{if $n \equiv 1 \pmod{3}$;} \\
r(n)/2,   & \text{if $n \equiv 2 \pmod{3}$.}
\end{cases}
\end{equation*}
\end{proof}

We have the following consequence of Propositions\,\ref{prop-mult} and\,\ref{prop-mult1}.

\begin{corollary}
Given a pair $(m,n)$ of coprime positive integers,
the polynomial $\Pg_{mn}(X)^2 - \Pg_m(X)^2 \Pg_n(X)^2$ is divisible by $X(X+1)(X^2-4)$,
and moreover by $X-1$ if $(m,n) \equiv (0,1), (1,1)$ or $(1,2) \pmod{3}$.
\end{corollary}

We may wonder whether there are other integers $N$ such that $n \mapsto |\Pg_n(N)|$ is a multiplicative function. 
The answer is no.

\begin{proposition}
The function $n \mapsto |\Pg_n(N)|$ is multiplicative if and only if $N= -2, -1, 0$ or~$2$.
\end{proposition}

\begin{proof}
The ``if direction'' is a reformulation of Proposition~\ref{prop-mult}. Conversely,
if $n \mapsto |\Pg_n(N)|$ is multiplicative, then we have $|\Pg_6(N)| = |\Pg_2(N)| |\Pg_3(N)|$ as a special case. 
Now the polynomial $\Pg_6(X)^2  -  \Pg_2(X)^2 \, \Pg_3(X)^2$ can be factored as
\begin{equation*}
\Pg_6(X)^2  -  \Pg_2(X)^2 \, \Pg_3(X)^2 = X(X-1)^3 (X+1)^3 (X-2)(X+2)^2 .
\end{equation*}
This implies that multiplicativity holds only for integers~$N$ such that $|N| \leq 2$.
We rule out the case $N = 1$ in view of Proposition~\ref{prop-mult1}.
\end{proof}



\section{The polynomials $F_n(X)$}\label{sec-aux}

Let us define the monic Chebyshev polynomials and the polynomials~$F_n(X)$ mentioned in the introduction. 


\subsection{Monic Chebyshev polynomials}\label{ssec-Tchb}

Given an integer $k\geq 0$, the \emph{standard Chebyshev polynomial of the first kind}~$T_k(X)$ is the degree~$k$
polynomial defined by
\begin{equation*}
\cos(k \theta) = T_k(\cos (\theta)) ,
\end{equation*}
equivalently by
\begin{equation*}
\frac{q^k + q^{-k}}{2} = T_k \left( \frac{q + q^{-1}}{2} \right) .
\end{equation*}
Rivlin~\cite{Ri} gave a useful overview of the important properties of Chebyshev polynomials.

We are interested in the following variant of~$T_k(X)$:
let $\TT_k(X)$ be the degree~$k$ polynomial defined by
\begin{equation}\label{defTT}
q^k + q^{-k} = \TT_k (q + q^{-1}).
\end{equation}
Both $T_k (X)$ and~$\TT_k(X)$ have integer coefficients.
They are clearly related by
\begin{equation}\label{eq-TTT}
\TT_k (X) = 2 T_k(X/2) .
\end{equation}

The polynomials $\TT_k (X)$ are monic for all $k\geq 1$. 
That is why we call them \emph{monic Chebyshev polynomials}.
Abramowitz et al.\ \cite[p.\ 778, Eq.~22.5.11]{AS} denote the polynomials~$\TT_k (X)$ by~$C_k$;
Horadam~\cite{Ho} calls them \emph{Vieta--Lucas polynomials} and denotes them by~$v_n(x)$.

Table\,\ref{tableTT} lists the polynomials~$\TT_k (X)$ for $1 \leq k \leq 12$.

\begin{table}[H]
\renewcommand\arraystretch{1.25}
\noindent\[
\centering
\begin{array}{|c||c|}
\hline
k & \TT_k(X)  \\
\hline\hline
0 & 2  \\ 
\hline
1 & X  \\ 
\hline
2 & X^2 - 2   \\
\hline
3 & X^3 - 3X   \\ 
\hline
4 & X^4 - 4X^2 +2  \\ 
\hline
5 & X^5 - 5X^3 + 5X  \\ 
\hline
6 &  X^6 - 6X^4 + 9 X^2 - 2 \\
\hline
7 & X^7 - 7 X^5 + 14 X^3 - 7X  \\ 
\hline
8 & X^8 - 8 X^6 + 20 X^4 -16 X^2 +2 \\ 
\hline
9 &  X^9 - 9 X^7 + 27 X^5 - 30 X^3 + 9 X   \\
\hline
10 &  X^{10} - 10 X^8 + 35 X^6 - 50 X^4 + 25 X^2 - 2  \\
\hline
11 &  X^{11} - 11 X^9 + 44 X^7 - 77 X^5 + 55 X^3 - 11X   \\
\hline
12 &   X^{12} - 12 X^{10} + 54 X^8 - 112 X^6 + 105 X^4 - 36 X^2 +2  \\
\hline
\end{array}
\]
\caption{The monic Chebyshev polynomials $\TT_k (X)$.}\label{tableTT}
\end{table}

Let us state a few properties of the polynomials~$\TT_k (X)$ which can be easily derived from well-known properties
of~$T_k (X)$. 

First, the polynomials~$\TT_k (X)$ can be defined inductively by
$\TT_0 (X) = 2$, $\TT_1 (X) = X$, and for $k\geq 1$ by
\begin{equation}\label{rec-TT}
\TT_{k+1}(X) = X\TT_k(X) - \TT_{k-1}(X) .
\end{equation}
The previous linear recurrence relation can be written in matrix form as
\begin{equation}\label{matrix-TT}
\begin{pmatrix}
\TT_{k+1}(X) \\ \TT_k(X)
\end{pmatrix}
=  M
\begin{pmatrix}
\TT_k(X) \\ \TT_{k-1}(X)
\end{pmatrix}, \;\; \text{where} \; M = 
\begin{pmatrix}
X & - 1\\
 1 & 0
\end{pmatrix} .
\end{equation}

Next, the generating function of the polynomials~$\TT_k (X)$ is the power series expansion of the 
following rational function:
\begin{equation}\label{genfun-TT}
\sum_{k \geq 0} \, \TT_k (X) \, t^k = \frac{2 - Xt}{1 - Xt + t^2} .
\end{equation}

We have the following expression of~$\TT_n(X)$ in terms of powers of~$X$:
\begin{equation*}\label{eq-TX}
\TT_n(X) = \sum_{m=0}^{[n/2]} \, (-1)^m \left( \binom{n-m}{m} - \binom{n-m-1}{m-1} \right) X^{n-2m} .
\end{equation*}

We also have a positivity result for the polynomials $\TT_k(X)$.

\begin{proposition}\label{TTpos}
For each $k \geq 0$, we have $\TT_k (x) > 0$ if $x$ is a real number $\geq 2$.
\end{proposition}

\begin{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~\eqref{eq-TTT} the zeros of~$\TT_k(X)$ lie in $(-2,2)$. On the other, since $\TT_k(X)$ is monic,
$\lim_{x \to + \infty} \, \TT_k(x) = + \infty$. Combining these two facts implies the desired positivity.
\end{proof}

We close our summary on~$\TT_k (X)$ with the following result, which may be of independent interest.

\begin{proposition}\label{prop-recTT}
For all $k\geq 0$ we have $\TT_k (X) = \tr(M^k)$, where $M$ is the $2 \times 2$-matrix defined in \eqref{matrix-TT}.
\end{proposition}

\begin{proof}
First, observe that $\tr(M) = X = \TT_1(X)$ and $\tr(M^0) = \tr(\Id) = 2 = \TT_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\geq 0}$ satisfies the linear recurrence relation~\eqref{rec-TT}. 
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.
\end{proof}


\subsection{Definition and basic properties of $F_n(X)$}\label{ssec-F}

We define the sequence of polynomials $(F_n(X))_{n\geq 0}$ inductively by $F_0(X) = 1$ and by
\begin{equation}\label{def-F}
F_n(X) = F_{n-1}(X) + \TT_n(X)
\end{equation}
for $n\geq 1$. In other words,
\begin{equation}\label{def-F2}
F_n(X) = 1 + \sum_{k=1}^n \, \TT_k(X) .
\end{equation}
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 \leq 11$ in Table~\ref{table-F}.

\begin{table}[ht]
\renewcommand\arraystretch{1.25}
\noindent\[
\centering
\begin{array}{|c||c|}
\hline
n & F_n(X)  \\
\hline\hline
0 & 1  \\ 
\hline
1 & X + 1   \\
\hline
2 & X^2 + X - 1 \\ 
\hline
3 & X^3 + X^2 - 2X -1  \\ 
\hline
4 & X^4 + X^3 - 3 X^2 - 2X +1 \\ 
\hline
5 &  X^5 + X^4 - 4X^3 - 3 X^2 + 3X + 1  \\
\hline
6 & X^6 + X^5 - 5 X^4 -4 X^3 + 6X^2 + 3X -1 \\ 
\hline
7 & X^7 +X^6 - 6X^5 - 5 X^4 + 10 X^3 + 6 X^2 - 4X -1  \\ 
\hline
8 & X^8 + X^7 - 7 X^6 - 6 X^5 + 15 X^4 + 10 X^3 -10 X^2 -4 X +1  \\
\hline
&   X^9 + X^8 -8 X^7 -7 X^6  + 21 X^5 + 15 X^4  \\
9 &  - 20 X^3 - 10 X^2 + 5X + 1 \\
\hline
 &  X^{10} + X^9 - 9 X^8 - 8 X^7 + 28 X^6 + 21 X^5  \\
10 &   - 35 X^4 - 20 X^3 + 15 X^2 + 5X -1   \\
\hline
 & X^{11} + X^{10} - 10 X^9 - 9 X^8 + 36 X^7 + 28 X^6   \\
11 &  - 56 X^5 -35 X^4 + 35 X^3 + 15 X^2 - 6 X  - 1  \\
\hline
\end{array}
\]
\caption{The polynomials $F_n (X)$.}\label{table-F}
\end{table}

Our first result is the following.

\begin{proposition}\label{prop-gfF}
The generating function of the polynomials $F_n(X)$ is the power series expansion of the following rational function:
\[
\sum_{n \geq 0} \,  F_n(X) \,  t^n = \frac{1+t}{1-Xt +t^2} \, . 
\]
\end{proposition}

\begin{proof}
Using~\eqref{genfun-TT}, we obtain
\begin{eqnarray*}
1 + \sum_{k \geq 1} \, \TT_k (X) \, t^k & = & \frac{2 - Xt}{1 - Xt + t^2} + 1 - \TT_0(X) \\
& = & \frac{2 - Xt}{1 - Xt + t^2} - 1 =  \frac{1 - t^2}{1 - Xt + t^2} \, .
\end{eqnarray*}
Therefore, 
\begin{eqnarray*}
\sum_{n \geq 0} \,  F_n(X) \,  t^n 
& = & \sum_{n \geq 0} \, \left( 1 + \sum_{m=1}^n \, \TT_m(X) \right) t^n \\
& = & \left( \sum_{\ell \geq 0} \, t^{\ell} \right) \left( 1 + \sum_{k \geq 1} \, \TT_k (X) \, t^k \right) \\
& = & \frac{1}{1-t} \cdot \frac{1 - t^2}{1 - Xt + t^2} =  \frac{1 + t}{1 - Xt + t^2} \, .
\end{eqnarray*}
\end{proof}

Setting $X= 0$ in the formula of Proposition~\ref{prop-gfF} yields the \emph{constant term} of~$F_n(X)$:
for all $m \geq 0$ we have
\begin{equation*}\label{constant-F}
F_{2m}(0) = F_{2m+1}(0) = (-1)^m .
\end{equation*}

For the remaining coefficients of~$F_n(X)$ we have the following expression.

\begin{proposition}\label{prop-Fn}
For $n\geq 1$ we have
\[
F_n(X) = \sum_{0 \leq m \leq n/2} \, (-1)^m \binom{n - m}{m} \, X^{n-2m}
+  \sum_{0 \leq m \leq (n-1)/2} \, (-1)^m  \binom{n - m - 1}{m} \, X^{n-2m-1}  .
\]
\end{proposition}


\begin{proof}
Expanding the following fraction, we obtain
\begin{eqnarray*}
\frac{1}{1-Xt +t^2} & = & 1 + \sum_{r \geq 1} \, t^r (X - t)^r \\
& = & 1 + \sum_{r \geq 1} \sum_{s = 0}^r \, (-1)^s \binom{r}{s} X^{r-s} t^{r+s} \\
& = & 1 + \sum_{n \geq 1} \, \sum_{0 \leq m \leq n/2} \, (-1)^m \binom{n-m}{m} X^{n-2m} t^n .
\end{eqnarray*}
In view of Proposition~\ref{prop-gfF}, 
multiplying by $1+t$ yields the desired formula for~$F_n(X)$.
\end{proof}

\begin{corollary}\label{coro-Fn}
For $n \geq 5$ we have 
\begin{eqnarray*}
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} \\
&& {} + {\rm \text{\rm monomials of degree}} \leq n-6 .
\end{eqnarray*}
\end{corollary}

In Section~\ref{pf-th-PFodd} we need the following linear recurrence relation satisfied by the polynomials~$F_k(X)$.

\begin{proposition}\label{prop-recF} 
For $k\geq 1$ we have $F_{k+1}(X) = X F_k(X) - F_{k-1}(X)$.
\end{proposition}

\begin{proof}
The rational function expressing the generating function in Proposition~\ref{prop-gfF} has the same denominator
as the rational function in~\eqref{genfun-TT}.
Therefore the polynomials $F_k(X)$ satisfy the same linear recurrence relation 
as the polynomials $\TT_k(X)$ in~\eqref{rec-TT}; see, e.g., Berstel et~al.\ \cite[Chap.\ 6, Prop.\ 1.2 and Cor.\ 1.3]{BR}.
\end{proof}



\section{Results for the polynomials $\Pg_n(X)$}\label{sec-resultsP}

Now we establish a connection between the polynomials $\Pg_n(X)$ and the polynomials~$F_k(X)$.
We start with an approximation result.


\subsection{Approximating $\Pg_n(X)$ by $F_{n-1}(X)$}\label{ssec-approx}

The aim of this subsection is the following result.

\begin{theorem}\label{th-approx}
For all $n\geq 2$, the difference $\Pg_n(X) - F_{n-1}(X)$ is a polynomial 
whose degree is smaller than $n/2 - 1$.
\end{theorem}

Recall that $\Pg_n(X)$ and $F_{n-1}(X)$ are both of degree~$n-1$. 
The theorem states that they coincide in every degree $\geq n/2-1$.

The bound on degrees is sharp as can be seen from Table~\ref{table-PPTTF}:
indeed, $\Pg_9(X) - F_8(X) = - F_3(X) + F_1(X)$ is of degree~$3 < 9/2 - 1$; 
similarly, $\Pg_{11}(X) - F_{10}(X) = - F_4(X)$ is of degree~$4 < 11/2 - 1$,
and $\Pg_{15}(X) - F_{14}(X)$ is of degree~$6 < 15/2 - 1$.

Together with Corollary~\ref{coro-Fn} we derive the following.

\begin{corollary}
For all $n \geq 10$ we have
\begin{eqnarray*}
\Pg_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}  \\
&& {} + {\rm \text{\rm monomials of degree}}  \leq n-7 .
\end{eqnarray*}
\end{corollary}

Recall the (nonnegative) coefficients $a_{n,i}$ of~$\Pg_n(X)$ appearing in \eqref{Pn-coeff} and~\eqref{PPTT}.
For the proof of Theorem~\ref{th-approx} we need the following result.

\begin{lemma}\label{lem-ani}
We have $a_{n,i} = 1$ for all $i$ such that $n/2 - 1 \leq i \leq n-1$.
\end{lemma}

\begin{proof}
Given $0 \leq i \leq n-1$, 
the authors~\cite[Thm.\ 1.3]{KR3} 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} = \left( \frac{i + \sqrt{2n+ i^2}}{2}, i + \sqrt{2n+ i^2} \right] .
\]
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 $\leq n/2$,
it suffices to check that $n \leq i + \sqrt{2n+ i^2}$ and $n/2 \leq (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 \leq 2n$, which simplifies into $n-2i \leq 2$ hence to $i \geq (n-2)/2= n/2 - 1$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{th-approx}]
By \eqref{def-F2} and~\eqref{PPTT} we have
\begin{eqnarray*}
\Pg_n(X) - F_{n-1}(X) 
& = & (a_{n,0} - 1)  + \sum_{1 \leq i \leq n - 1} \, (a_{n,i} -1) \, \TT_i(X) \\
& = & (a_{n,0} - 1)  + \sum_{1 \leq i < n/2 - 1} \, (a_{n,i} -1) \, \TT_i(X) .
\end{eqnarray*}
The last equality is a consequence of Lemma~\ref{lem-ani}.
Since $\TT_i(X)$ is of degree~$i$, we obtain the desired result.
\end{proof}
 
\begin{remark}
The sequence of integers $\Pg_n(3)$ is Sequence \seqnum{A329156} in the OEIS \cite{OEIS}.
The sequence $(F_{n-1}(3))_{n\geq 1}$ is \seqnum{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~$(\Pg_n(4))_{n\geq 1}$ is now referenced as \seqnum{A386706} in the OEIS~\cite{OEIS}.
According to Kimberling's remark in the OEIS~\cite[\seqnum{A001834}]{OEIS}, the sequence $(F_{n-1}(4))_{n\geq 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~$(\Pg_n(5))_{n\geq 1}$ is now \seqnum{A387017} and the sequence~$(F_{n-1}(5))_{n\geq 1}$ 
is \seqnum{A030221} in the OEIS~\cite{OEIS}.
The latter consists of the values of Chebyshev even-indexed $U$-polynomials at~$\sqrt{7}/2$. 
\end{remark}

 
\subsection{Odd divisors}\label{ssec-oddP}

Now we give a formula for $\Pg_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$ ($\geq 1$) as the product
$n = 2^a p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}$,
where $p_1, p_2, \ldots, p_r$ are distinct odd primes and $a, a_1, a_2, \ldots, a_r$ are nonnegative integers, 
then the number of \emph{odd divisors} of~$n$ (including~$1$) is equal to
\[
(a_1 + 1)(a_2 + 1) \cdots (a_r + 1) \geq 1.
\]
Observe that $(a_1 + 1)(a_2 + 1) \cdots (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\geq 1$ and every odd divisor~$d$ of~$n$, define $r_n(d)$ to be the integer 
\begin{equation}\label{eq-rnd}
r_n(d)  = \frac{n}{d} - \frac{d+1}{2} \, .
\end{equation}
When $d$ is the trivial divisor~$1$, we have $r_n(1) = n - 1$. 

Let us state our main result for $\Pg_n(X)$.

\begin{theorem}\label{th-PFodd}
For all $n\geq 1$, 
\[
\Pg_n(X) = \sum_{d | n, \, d \, \mathrm{odd} \atop r_n(d) \geq 0} \, F_{r_n(d)}(X) 
- \sum_{d | n, \, d \, \mathrm{odd} \atop r_n(d) <0} \, F_{-r_n(d) -1}(X) .
\]
\end{theorem}

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~\ref{th-PFodd} will be given in Section~\ref{pf-th-PFodd}.

In Table~\ref{table-PPTTF} each polynomial~$\Pg_n(X)$ ($1 \leq n \leq 16$) is expressed
as a sum of the polynomials~$\TT_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.


\begin{table}[H]
\renewcommand\arraystretch{1.30}
\noindent\[
\centering
\begin{array}{|c||c|c|}
\hline
n &  \text{As sums of} \, \TT_k & \text{In terms of}\, F_k \\
\hline\hline
1 & 1 & F_0 \\ 
\hline
2 &  1 + \TT_1 & F_1 \\
\hline
3 &  \TT_1 + \TT_2 & F_2 - F_0 \\ 
\hline
4 &  1 + \TT_1 + \TT_2 + \TT_3 & F_3 \\ 
\hline
5 &  \TT_2 + \TT_3 + \TT_4 & F_4 - F_1 \\ 
\hline
6 &  \TT_0 + \TT_1 + \TT_2 + \TT_3 + \TT_4 + \TT_5  & F_5 + F_0 \\
\hline
7 &  \TT_3 + \TT_4 + \TT_5 + \TT_6 & F_6 - F_2 \\ 
\hline
8 &  1 + \TT_1 + \TT_2 + \TT_3 + \TT_4 + \TT_5 + \TT_6 + \TT_7  & F_7 \\ 
\hline
9 &  1 + \TT_1 + \TT_4 + \TT_5 + \TT_6 + \TT_7 + \TT_8 & F_8 - F_3 + F_1 \\
\hline
10 &  \TT_1 + \TT_2 + \TT_3 + \TT_4 + \TT_5 + \TT_6 + \TT_7  + \TT_8 + \TT_9 & F_9 - F_0 \\
\hline
11 &  \TT_5 + \TT_6 + \TT_7 + \TT_8 + \TT_9 + \TT_{10} & F_{10} - F_4  \\
\hline
&  \TT_0 + 2 \TT_1 + 2\TT_2 + \TT_3 + \TT_4 + \TT_5 & \\
12 &  + \TT_6 + \TT_7 + \TT_8 + \TT_9 + \TT_{10} +  \TT_{11} &  F_{11} + F_2 \\
\hline
13 &   \TT_6 + \TT_7 + \TT_8 + \TT_9 + \TT_{10} +  \TT_{11} +  \TT_{12} &  F_{12} - F_5 \\
\hline
&  \TT_2 + \TT_3 + \TT_4 + \TT_5 +  \TT_6 + \TT_7& \\
14 &  + \TT_8 + \TT_9 + \TT_{10} +  \TT_{11} +  \TT_{12} +  \TT_{13} &  F_{13} - F_1 \\
\hline
&  \TT_0 + \TT_1 + \TT_2 + \TT_3  + \TT_7 + \TT_8 & F_{14}(X) - F_6(X) \\
15 &   + \TT_9 + \TT_{10} +  \TT_{11} +  \TT_{12} +  \TT_{13} +  \TT_{14} &   {}+ F_3(X) + F_0(X)  \\
\hline
&  1 + \TT_1 + \TT_2 + \TT_3 + \TT_4 + \TT_5 +  \TT_6 + \TT_7 & \\
16 &  + \TT_8 + \TT_9 + \TT_{10} +  \TT_{11}  +  \TT_{12}  +  \TT_{13}  +  \TT_{14}  +  \TT_{15} &  F_{15}  \\
\hline
\end{array}
\]
\caption{Expressing $\Pg_n (X)$ in terms of $\TT_k(X)$ and of $F_k(X)$.}\label{table-PPTTF}
\end{table}


Since $d= 1$ is an odd divisor for every~$n\geq 1$ and $r_n(1) = n - 1 \geq 0$, the polynomial $F_{n-1}(X)$ always
appears, with a positive sign, in the formula of Theorem~\ref{th-PFodd}. 

We remarked above that only powers of~$2$ have a unique odd divisor, namely $d=1$.
This implies the following consequence of~Theorem~\ref{th-PFodd}, which explains the coincidences
$\Pg_n(N) = F_{n-1}(N)$  (set in boldface) observed in Table~\ref{table-values} for $N = 3$, $4$, and $5$.

\begin{corollary}
We have $\Pg_n(X) = F_{n-1}(X)$ if and only if $n$ is a power of~$2$.
\end{corollary}



As special cases of Theorem~\ref{th-PFodd}, we obtain the following formulas for $\Pg_n(X)$.


\subsubsection{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~$\Pg_p(X)$ has two summands. We have
\begin{equation*}
\Pg_p(X) = F_{p-1}(X) - F_{(p-3)/2}(X) = \sum_{m=(p-1)/2}^{p-1} \, \TT_m(X) .
\end{equation*}

Now consider the case $n = 2^a p$, where $a \geq 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 \geq 0$, which is equivalent to $p \leq 2^{a+1} - 1$, then 
\begin{equation*}
\Pg_{2^a p}(X) = F_{2^a p-1}(X) + F_{2^a - (p+1)/2}(X)  .
\end{equation*}
For instance, $\Pg_{6}(X) = F_{5}(X) + F_{0}(X)$ and $\Pg_{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 
\begin{equation*}
\Pg_{2^a p}(X) = F_{2^a p-1}(X) - F_{(p-1)/2 - 2^a}(X)  .
\end{equation*}
As special cases, $\Pg_{10}(X) = F_{9}(X) - F_{0}(X)$ and $\Pg_{14}(X) = F_{13}(X) - F_{1}(X)$.


\subsubsection{Three odd divisors}

If $n = p^2$ for some odd prime~$p$, then
\begin{equation*}
\Pg_{p^2}(X) = F_{p^2-1}(X) - F_{(p^2 - 3)/2}(X) + F_{(p -1)/2}(X) .
\end{equation*}
For instance, $\Pg_9(X) = F_8(X) - F_3(X) + F_1(X)$.


\subsubsection{Four odd divisors}

If $n = p^3$ for some odd prime~$p$, then $n$ has four odd divisors. We have
\begin{equation*}
\Pg_{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) .
\end{equation*}
For $p=3$, we obtain $\Pg_{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~$\geq 7$.
Then $n$ has four odd divisors, namely $1, 3, p, 3p$, and
\begin{equation*}
\Pg_{3p}(X) = F_{3p-1}(X) - F_{3(p-1)/2} + F_{p-2}(X) - F_{(p-7)/2} \, .
\end{equation*}
For $p= 5$ and $n = 15$, we have
$\Pg_{15}(X) = F_{14}(X) - F_6(X) + F_3(X) + F_0(X)$.



\begin{remark}
In Table~\ref{table-values} we set the values $\Pg_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
$\Pg_n(X) = F_{n-1}(X) + 1 = F_{n-1}(X) + F_0(X) $
if and only if the integer~$n$ is an even \emph{perfect} number; equivalently,
$n = 2^a p$, where $p = 2^{a+1} - 1$ is a \emph{Mersenne prime} such as $3, 7, 31, 127$
(see the OEIS~\cite[\seqnum{A000668}]{OEIS}). The corresponding~$n$ are $n = 6, 28, 496, 8128$.

Similarly, 
$\Pg_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 \emph{Fermat prime} such as $3$, $5$, $17$, $257$
(see the OEIS~\cite[\seqnum{A000215}]{OEIS}). The corresponding~$n$ are $3$, $10$, $136$, $32896$.

In general, the formula for $\Pg_n(X)$ in Theorem~\ref{th-PFodd} contains $\pm F_0(X)$ as a summand if and only if 
$n$ is \emph{triangular}, i.e., $n = r(r+1)/2$ for some $r\geq 1$.
The smallest triangular integers are $1$, $3$, $6$, $10$, $15$, $21$, $28$, $36$.
\end{remark}

\begin{remark}
For which natural numbers~$n$ do we have $\Pg_n(X) = F_{n-1}(X) \pm F_1(X)$?

We have $\Pg_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 \seqnum{A050415} and \seqnum{A181703} in the OEIS~\cite{OEIS}).

Similarly, $\Pg_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~\cite[\seqnum{A057733}]{OEIS}); 
they correspond to $n= 5$, $14$, $44$, $152$, $2144$.

More generally, $F_1(X)$ appears in the formula for $\Pg_n(X)$ in Theorem~\ref{th-PFodd} if and only if
$n = r(r+3)/2$ for some $r\geq 1$; see the OEIS~\cite[\seqnum{A000096}]{OEIS} for a list of such~$n$.
\end{remark}




\section{Formulas for $C_n(q)$}\label{sec-Cnq}

In order to prove Theorem~\ref{th-PFodd} we need new expressions for the polynomial~$C_n(q)$.
Recall that $C_n(q)$ and $\Pg_n(X)$ are related by the equalities
\begin{equation*}
\frac{C_n(q)}{q^n} = \frac{(q-1)^2}{q} \, \frac{P_n(q)}{q^{n-1}} = \frac{(q-1)^2}{q} \, \Pg_n(q + q^{-1}) .
\end{equation*}


\subsection{Increasing sequences}\label{ssec-IS}

We need the following material borrowed from Mason~\cite{Ma}.

We call \emph{increasing sequence} every finite nonempty ordered set of consecutive integers $\{ a+1, \ldots, 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 \emph{positive}  if $a\geq 0$
and \emph{negative} if $a < 0$.
It is called \emph{odd} if $h$ is odd and \emph{even} if $h$ is even.

We say that an integer~$n \geq 1$ is \emph{represented} by~$\IS(a,h)$, and we write 
\[
\IS(a,h) \models n,
\] 
if $n$ is equal to the sum of all elements of~$\IS(a,h)$.

There is an involution $\IS(a,h) \mapsto \IS(\check{a},\check{h})$ on increasing sequences determined by
\begin{equation}\label{def-invIS}
a + \check{a} +1 = 0 \quad \text{and} \quad \check{a} + \check{h} = a + h.
\end{equation}
If $\IS(a,h)$ represents~$n$, so does~$\IS(\check{a},\check{h})$. 
Since $\check{h} - h = a - \check{a} = 2a + 1$, we conclude that $h$ and $\check{h}$ are of opposite parity.
In other words, $\IS(a,h)$ is even (resp., odd) if and only if $\IS(\check{a},\check{h})$ is odd (resp., even).
Moreover, if $\IS(a,h)$ is positive (resp., negative), then $\IS(\check{a},\check{h})$ is negative (resp., positive).

Let $n \geq 1$ be a positive integer.
With every \emph{odd} divisor~$d$ of~$n$ we associate the odd increasing sequence $\IS(a,h)$, where 
\begin{equation}\label{eq-ah}
a = \frac{n}{d} - \frac{d+1}{2}
\quad\text{and}\quad 
h = d .
\end{equation}
It is centered around~$n/d$, namely we have
\begin{equation}\label{def-ISd}
\IS(a,h) = \left\{ \frac{n}{d} - \frac{d-1}{2}, \ldots, \frac{n}{d} -1, \frac{n}{d}, \frac{n}{d} +1, \ldots, \frac{n}{d} + \frac{d-1}{2} \right\}.
\end{equation}
This odd increasing sequence may be positive or negative, depending on~$d$. We have $\IS(a,h) \models n$.

Starting from $a = n/d - (d+1)/2$ and $h = d$, we have
\begin{equation}\label{eq-ah2}
\check{a} = -\frac{n}{d} + \frac{d-1}{2}
\quad\text{and}\quad
\check{h} = \frac{2n}{d}.
\end{equation}
We thus obtain the even increasing sequence
\begin{equation}\label{def-ISdv}
\IS(\check{a},\check{h}) 
= \left\{ -\frac{n}{d} + \frac{d+1}{2}, \ldots, \frac{n}{d} + \frac{d-1}{2} \right\} \models n .
\end{equation}

Clearly, if $\IS(a,h)$ is positive, then $\IS(a,h) \subset \IS(\check{a},\check{h})$ and
\begin{equation}\label{def-ISdv1}
\IS(\check{a},\check{h}) \setminus \IS(a,h)
= \left\{ -\frac{n}{d} + \frac{d+1}{2}, \ldots, \frac{n}{d} - \frac{d+1}{2} \right\}  .
\end{equation}
If $\IS(a,h)$ is negative, then $\IS(\check{a},\check{h}) \subset \IS(a,h)$ and
\begin{equation}\label{def-ISdv2}
 \IS(a,h) \setminus \IS(\check{a},\check{h})
= \left\{ \frac{n}{d} - \frac{d-1}{2}, \ldots, -\frac{n}{d} + \frac{d-1}{2} \right\}  .
\end{equation}

For both pairs $(a,h)$ and $(\check{a}, \check{h})$ we have the same relation, namely
\begin{equation}\label{eq-IS}
\frac{h(h+2a+1)}{2} = n
= \frac{\check{h}(\check{h}+2\check{a}+1)}{2}  .
\end{equation}

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 \emph{odd} element of~$\{h, \check{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\geq 1$ we have a pair $(a,h)$ of integers with $h\geq 1$ verifying Equation~\eqref{eq-IS},
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~\eqref{eq-ah}.
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~\eqref{eq-ah2}.

\begin{example}
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), \ldots, -1,0,1, \ldots, n-1,n\}.
\]
\end{example}

\begin{example}
Every other integer~$n$ has odd divisors $d\neq 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$, $\check{a} = -5$, $\check{h} = 12$, and 
\[
\IS(4,3) = \{ 5,6,7\} \quad \text{and}\quad  
\IS(-5, 12) = \{-4, -3, \ldots, 3, 4, 5, 6, 7\} .
\]

If $d = 9$, then $a = -3$, $h=9$, $\check{a} = 2$, $\check{h} = 4$, and 
\[
\IS(-3,9) = \{ -2, -1, 0, 1, 2, 3, 4, 5,6 \} \quad \text{and}\quad  
\IS(2,4) = \{ 3, 4, 5, 6\} .
\]
\end{example}


\subsection{New formulas for~$C_n(q)$}\label{ssec-Cnq}

The authors \cite[Th.\ 1.1]{KR3} gave the following explicit expression for~$C_n(q)$:
\begin{equation*}\label{Cn-coeffi}
\frac{C_n(q)}{q^n} = c_{n,0}  + \sum_{i=1}^n \, c_{n,i} \, \left( q^{i} + q^{-i} \right) , 
\end{equation*}
where
\begin{equation}\label{formula-cn0}
c_{n,0} = 2 (-1)^r
\end{equation}
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 \leq i \leq n$) we have
\begin{equation}\label{formula-cni}
c_{n,i} =
\begin{cases}
(-1)^k ,  & \text{if $n = k(k+2i +1)/2$ for some integer $k  \geq 1$;}  \\
(-1)^{k-1} ,  & \text{if $n = k(k+2i -1)/2$ for some integer $k  \geq 1$;} \\
0, & \text{otherwise.} 
\end{cases}
\end{equation}

Observe that in (\ref{formula-cni}) the first two conditions are mutually exclusive, 
as shown by the authors~\cite[Lemma~3.5 (ii)]{KR3}. This may also be verified as follows: suppose
\[
k(k+2i+1)=h(h+2i-1)
\] 
with $i,h,k\geq 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\geq h$, nor in the case~$k<h$.

\begin{lemma}\label{formula1} 
We have
\[
\frac{C_n(q)}{q^n} = \sum\,  (-1)^h \, \left( q^a + q^{-a} \right), 
\]
where the summation is over all $h\in\ZZ_{\geq 1}$ and $a\in \ZZ$ 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.
\end{lemma}
 
\begin{proof}
It follows from~\eqref{formula-cn0} that both sides have the same constant term. 

Henceforth we concentrate on the case when $a$ is a nonzero integer.
Let $i\geq 1$.
Suppose that $n=k(k+2i +1)/2$ with $k\geq 1$ as in the first row of~\eqref{formula-cni}; 
then $n=h(h+2a +1)/2$ with $h=k \geq 1$, $a=i\in \ZZ \setminus \{0\}$, and $(-1)^k=(-1)^h$. 

Now suppose that $n = k(k+2i -1)/2$ with $k\geq 1$ as in the second row of~\eqref{formula-cni}; 
then $n=h(h+2a +1)/2$ with $h=k+2i-1\geq 1$, $a=-i\in \ZZ \setminus \{0\}$, and $(-1)^{k-1}=(-1)^h$. 

Conversely, let $n=h(h+2a +1)/2$ with $h\geq 1$, $i\in \ZZ$, and $a\neq 0$. 
Then either $a\geq 1$, and then $n=k(k+2i +1)/2$ with $k=h$, $i=a\geq 1$, and $(-1)^k=(-1)^h$; 
or $a < 0$, and then $n=k(k+2i-1)/2$, $k=h+2a+1\geq 1$, $i = -a > 0$, and $(-1)^{k-1}=(-1)^h$.

This proves the lemma in view of the observation made just before its statement.
\end{proof}

 
We have the following new formulas for~$C_n(q)$.

\begin{theorem}\label{th-Cn}
For each integer $n\geq 1$ we have 
\[
\frac{C_n(q)}{q^n} = \sum \, (-1)^h \, \left( q^a + q^{-a} \right),
\] 
where the summation is taken over all increasing sequences $\IS(a,h)$ such that $\IS(a,h) \models n$. 
Moreover, for given $|a|$, there is a unique increasing sequence $\IS(a,h)$ with $\IS(a,h) \models n$. 

We also have
\[
\frac{C_n(q)}{q^n} = \sum_{d | n , \, d \, \mathrm{odd}} \, 
\left( 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}} \right) .
\] 
In the previous sum, all monomials $\neq q^0$ are distinct.
\end{theorem}

\begin{proof} 
The first formula follows from Lemma~\ref{formula1} since the sum of the elements in $\IS(a,h)$ is 
equal to 
\[
a+1+a+2+ \cdots+a+h = ha+h(h+1)/2 = h(h+2a+1)/2.
\]

As in \S~\ref{ssec-IS}, with each odd divisor~$d$ of~$n$ we associate the two increasing 
sequences $\IS(a,h)$ and $\IS(\check a,\check h)$, respectively odd and even, defined by \eqref{def-ISd} and \eqref{def-ISdv}. 
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(\check{a}, \check{h})$ and the last two to~$\IS(a,h)$.
\end{proof}


The previous result immediately implies the following.

\begin{corollary}\label{coro-vacni} 
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$.
\end{corollary}


\subsection{Zeta functions}\label{ssec-zeta}

The following consequences of Theorem~\ref{th-Cn} may be of interest to algebraic geometers. 

Recall that the \emph{local zeta function}~$Z_{\HH^n/\FF_q}(t)$ 
of the Hilbert scheme~$\HH^n$ of $n$~points on the two-dimensional torus over the finite field~$\FF_q$ 
is the formal power series
\begin{equation}\label{def-Z}
Z_{X/\FF_q}(t) = \exp\left(\sum_{m\geq 1}\, C_n(q^m) \, \frac{t^m}{m} \right) .
\end{equation}
The authors \cite[Th.\ 2.1]{KR3} showed that $Z_{X/\FF_q}(t)$ is equal to the formal power series expansion
of the following rational function:
\[
Z_{\HH^n/\FF_q}(t) = \frac{1}{(1-q^nt)^{c_{n,0}}} \, \prod_{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 \S~\ref{ssec-Cnq}.
Rewriting this formula in view of Theorem~\ref{th-Cn} yields the following statement, where $r_n(d) = n/d - (d+1)/2$
is the integer introduced in~\eqref{eq-rnd}.

\begin{proposition}\label{prop-zeta}
For $n\geq 1$ we have
\begin{equation*}
Z_{\HH^n/\FF_q}(t) 
= \prod_{d | n , \, d \, \mathrm{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)} .
\end{equation*}
\end{proposition}

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_{\HH^n/\FF_q}(t)$ in two special cases. 
For $n=4$, which has only~$1$ as an odd divisor, we have $r_4(1) = 3$. Hence,
\begin{equation*}
Z_{\HH^4/\FF_q}(t)  = \frac{(1-q^{7}t)(1-qt)}{(1-q^{8}t)(1-t)} .
\end{equation*}
For $n=3$, which has two odd divisors, we have $r_3(1) = 2$ and $r_3(3) = -1$. Hence,
\begin{equation*}
Z_{\HH^3/\FF_q}(t)  = \frac{(1-q^{5}t)(1-qt)}{(1-q^{6}t)(1-t)} \cdot \frac{(1-q^{2}t)(1-q^4t)}{(1-q^{3}t)^2} .
\end{equation*}

Proposition~\ref{prop-zeta} allows us to give a similar formula for the \emph{Hasse--Weil zeta function} 
$\zeta_{\HH^n}(s)$ of the above Hilbert scheme; this zeta function is defined over the complex numbers by
\begin{equation*}\label{def-HWZ}
\zeta_{\HH^n}(s) = \prod_{p \; \text{prime}} \, Z_{{\HH^n}/\FF_p}(p^{-s}), \qquad (s \in \CC)
\end{equation*}
where the product is taken over all prime integers~$p$. 
As an immediate consequence of the formula for the local zeta functions~$Z_{\HH^n/\FF_q}(t)$ we have
\begin{equation}
\zeta_{\HH^n}(s) = \prod_{d | n , \, d \, \mathrm{odd}} \, 
\frac{ \zeta(s - n - r_n(d)) \, \zeta(s - n + r_n(d) ) }{ \zeta(s - n - r_n(d) -1) \, \zeta(s - n + r_n(d) +1) } \, , 
\end{equation}
where $\zeta(s)$ is Riemann's zeta function.
Recall from \cite[Sect.\ 2]{KR3} that the Hasse--Weil zeta function satisfies the simple functional equation
\begin{equation}
\zeta_{\HH^n}(s) = \zeta_{\HH^n}(2n-s).
\end{equation}


\section{Proof of Theorem~\ref{th-PFodd}}\label{pf-th-PFodd}

The following lemma exhibits a crucial link between the polynomials $F_r(X)$ and
the expression in parentheses in the second formula of Theorem~\ref{th-Cn}.

\begin{lemma}\label{lem-CF}
For $r \geq 0$ we have
\[
q^{r+1} + q^{-r-1} - q^{r} - q^{-r}  = q^{-1}(q-1)^2 F_r(q + q^{-1}) .
\]
\end{lemma}

\begin{proof}
The formula can be rephrased in terms of polynomials in the indeterminate~$X$
as $\TT_{r+1}(X) - \TT_r(X) = (X-2) F_r(X)$. 
By \eqref{def-F} the latter is equivalent to 
\[
\bigl( F_{r+1}(X) - F_r(X) \bigr) - \bigl( F_r(X) - F_{r-1}(X) \bigr) = X F_r(X) - 2 F_r(X),
\]
hence to the linear recurrence relation of Proposition~\ref{prop-recF}.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{th-PFodd}]
It follows from the second formula of Theorem~\ref{th-Cn} that
\[
q^{-1}(q-1)^2 \frac{P_n(q)}{q^{n-1}}   = \frac{C_n(q)}{q^n}
= \sum_{d | n , \, d\, \mathrm{odd}} \, 
\left( 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}} \right) .
\]
We partition the previous sum into two sums depending on the sign of $r_n(d) = n/d - (d+1)/2$.
We obtain 
\begin{eqnarray*}
q^{-1}(q-1)^2 \frac{P_n(q)}{q^{n-1}}  
& = & \sum_{d | n, \, d \, \mathrm{odd} \atop r_n(d) \geq 0} \,
\left( 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}} \right) \\
& & \hskip -10pt + \sum_{d | n, \, d \, \mathrm{odd} \atop r_n(d) < 0} \,
\left( 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}} \right) .
\end{eqnarray*} 
Now replacing $r$ by $r_n(d)$ in Lemma~\ref{lem-CF}, we see that the sum of monomials corresponding to $r_n(d) \geq 0$
is equal to 
\[
q^{-1}(q-1)^2 \sum_{d | n, \, d \, \mathrm{odd} \atop r_n(d) \geq 0} \, F_{r_n(d)}(q + q^{-1}).
\]
Replacing $r$ by $-r_n(d) - 1$ in Lemma~\ref{lem-CF}, we observe that the sum of monomials corresponding to $r_n(d) < 0$, 
equivalently to $-r_n(d) - 1 \geq 0$, is equal to
\[
q^{-1}(q-1)^2 \sum_{d | n, \, d \, \mathrm{odd} \atop r_n(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} = \Pg_n(q + q^{-1})$.
\end{proof}

We close this section with another formula for $P_n(q)/q^{n-1}$.

\begin{proposition}\label{formula2}
We have
\[
\frac{P_n(q)}{q^{n-1}} =
\sum_{d|n, \,d\,\mathrm{odd} \atop r_n(d) \geq 0} \; \sum_{i \in  \IS(\check{a},\check{h}) \setminus \IS(a,h)} \, q^i
- \sum_{d|n, \,d\,\mathrm{odd} \atop r_n(d) < 0}  \; \sum_{i \in  \IS(a,h)\setminus   \IS(\check{a},\check{h})}\, q^i  ,
\]
where $a = r_n(d)$ and $\check{a} = - r_n(d) - 1$, and
$\IS(a,h)$ and $\IS(\check{a},\check{h})$ are defined respectively by \eqref{def-ISd} and \eqref{def-ISdv}.
\end{proposition}

\begin{proof}
It follows from Theorem~\ref{th-PFodd} and the explicit descriptions~\eqref{def-ISdv1} and \eqref{def-ISdv2}.
\end{proof}

\begin{remark}
Sums of powers of $q$ indexed by odd divisors have also appeared in work of Caballero~\cite{RC1}
(especially in Chapter~II).
\end{remark}


\section{Acknowledgments}
We are grateful to Jos\'e Bastidas Olaya for his help with SageMath
and to V\'aclav Kot\v{e}\v{s}ovec for having corrected the value~$\Pg_7(4)$ in Table~\ref{table-values}.
We thank Christophe Pouzat and Marcus Slupinski for suggesting the title of the present paper.


\begin{thebibliography}{99}

\bibitem{AS}
M. Abramowitz and I. A. Stegun (eds.),
\emph{Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables},  
Dover, 1972.

\bibitem{Ap} T. M. Apostol, 
\emph{Introduction to Analytic Number Theory}. Springer Verlag, 1986. 

\bibitem{BR} J. Berstel and C. Reutenauer, 
\emph{Noncommutative Rational Series with Applications},
Encyclopedia of Mathematics and its Applications, 137, Cambridge University Press, 2011.

\bibitem{RC1} J. M. R. Caballero,
Propri\'et\'es arithm\'etiques du $E$-polyn\^ome du sch\'ema de Hilbert de $n$~points dans le tore bidimensionnel,
M\'emoire de ma\^\i trise en math\'ematiques, Universit\'e du Qu\'ebec \`a Montr\'eal, 2018.

\bibitem{RC2} J. M. R. Caballero,
On Kassel-Reutenauer $q$-analog of the sum of divisors and the ring $\FF_3[X]/X^2\FF_3[X]$,
\emph{Finite Fields Appl.} \textbf{51} (2018), 183--190.

\bibitem{Fi}
N. J. Fine, \emph{Basic Hypergeometric Series and Applications}, Mathematical Surveys and Monographs,~27,
American Mathematical Society, 1988.

\bibitem{Ho}
A. F. Horadam, Vieta polynomials, \emph{Fibonacci Quarterly} \textbf{40} (2002), 223--232.

\bibitem{KR1}
C. Kassel and C. Reutenauer, 
The Fourier expansion of $\eta(z)\eta(2z)\eta(3z)/\eta(6z)$,
\emph{Arch.\ Math.\ (Basel)} \textbf{108} (2017), 453--463.

\bibitem{KR2}
C.~Kassel and C.~Reutenauer, 
Counting the ideals of given codimension of the algebra of Laurent polynomials in two variables,
\emph{Michigan Math.~J}.\ \textbf{67} (2018), 715--741.

\bibitem{KR3}
C.~Kassel and C.~Reutenauer, 
Complete determination of the zeta function of the Hilbert scheme of $n$~points on a two-dimensional torus,
\emph{Ramanujan~J}.\ \textbf{46} (2018), 633--655.

\bibitem{Ma}
T. E. Mason, 
On the representation of an integer as the sum of consecutive integers, 
\emph{Amer.\ Math.\ Monthly} \textbf{19} (1912), 46--50.

\bibitem{OEIS} OEIS~Foundation Inc., The {O}n-{L}ine {E}ncyclopedia of {I}nteger {S}equences, 2026.
Published electronically at \url{https://oeis.org/}.

\bibitem{Ri}
T. J. Rivlin, \emph{Chebyshev Polynomials}, Wiley, 1990.



\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 11T55; Secondary 05A30, 14N10.

\noindent \emph{Keywords: } integer sequence, generating function, infinite product, polynomial, 
Chebyshev polynomial, approximation, multiplicative function.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  September 19 2025; 
revised version received  March 2 2026.
Published in {\it Journal of Integer Sequences}, July 4 2026.

\bigskip
\hrule
\bigskip

\noindent
Return to \href{https://cs.uwaterloo.ca/journals/JIS/}{Journal of Integer Sequences home page}.
\vskip .1in

\end{document} 


