# Fekete polynomials
of principal Dirichlet characters

Shiva Chidambaram, Ján Mináč, Tung T. Nguyen, Nguy$\tilde{\text{\^{E}}}$n Duy
Tân  Department of Mathematics, Massachusetts Institute of Technology,
Massachusetts Avenue Cambridge, MA 02139-4307<EMAIL_ADDRESS>Department of
Mathematics, Western University, London, Ontario, Canada N6A 5B7<EMAIL_ADDRESS>Department of Mathematics, Western University, London, Ontario, Canada N6A 5B7
<EMAIL_ADDRESS>School of Applied Mathematics and Informatics, Hanoi
University of Science and Technology, 1 Dai Co Viet Road, Hanoi, Vietnam
<EMAIL_ADDRESS>
###### Abstract.

Fekete polynomials associated to quadratic Dirichlet characters have
interesting arithmetic properties, and have been studied in many works. In
this paper, we study a seemingly simpler yet rich variant: the Fekete
polynomial $F_{n}(x)=\sum_{a=1}^{n}\chi_{n}(a)x^{a}$ associated to a principal
Dirichlet character $\chi_{n}$ of modulus $n$. We investigate the cyclotomic
factors of $F_{n}$ and conjecturally describe all of them. One interesting
observation from our computations is that the non-cyclotomic part $f_{n}$ of
$F_{n}(x)/x$ is usually irreducible. We study this factor closely in the
special case that $n$ is a product of two odd primes, proving basic properties
like separability in specific cases, and studying its coefficients and special
values. Combining these theoretical results with computational evidence lets
us identify the Galois group of $f_{n}$ for small $n$, and raises precise
questions in general.

###### Key words and phrases:

Fekete polynomials, cyclotomic polynomials, separability, irreducibility,
Galois groups

###### 2020 Mathematics Subject Classification:

Primary 11C08, 11R09, 11M06, 11Y70

SC was supported by Simons Foundation grant 550033. JM is partially supported
by the Natural Sciences and Engineering Research Council of Canada (NSERC)
grant R0370A01. He gratefully acknowledges the Western University Faculty of
Science Distinguished Professorship 2020-2021. JM and TN acknowledge the
support of the Western Academy for Advanced Research. NDT is funded by
Vingroup Joint Stock Company and supported by Vingroup Innovation Foundation
(VinIF) under the project code VINIF.2021.DA00030

###### Contents

  1. 1 Introduction
  2. 2 Cyclotomic factors of $F_{n}$ and their multiplicity
    1. 2.1 Reduction to the squarefree case
    2. 2.2 Cyclotomic factors of $F_{n}$
    3. 2.3 Multiplicity of cyclotomic factors
    4. 2.4 Cyclotomic factors of $F_{n}$ with small degree
  3. 3 The case $n=pq$
    1. 3.1 Further properties of the resultant $R_{q}(y)$
  4. 4 The case $n=3p$
  5. 5 The case $n=5p$
  6. 6 Irreducibility test for $f_{n}$
  7. 7 Galois theory for $f_{n}$ and $g_{n}$
    1. 7.1 The Galois group of $g_{n}$
    2. 7.2 The Galois group of $f_{n}$
  8. A Zeros on the unit circle

##  1\. Introduction

Let
$\chi:(\operatorname{\mathbb{Z}}/n)^{\times}\to\operatorname{\mathbb{C}}^{\times}$
be a Dirichlet character with modulus $n>1.$ Associated to $\chi$ is the
Dirichlet $L$-function defined by

$L(\chi,s)=\sum_{a=1}^{\infty}\frac{\chi(a)}{a^{s}}.$

This infinite series is absolutely convergent when $\Re(s)>1$. The function
$L(\chi,s)$ has a meromorphic continuation to the entire complex plane, with a
simple pole at $s=1$ in the case $\chi$ is a principal character. Furthermore,
$L(\chi,s)$ has the following integral representation (see [21, Proposition
3.3]. The character $\chi$ is assumed to be primitive in [21], but it is not
necessary and the proof goes through without this assumption)

(1.1) $\Gamma(s)L(\chi,s)=\int_{0}^{1}\frac{(-\log
t)^{s-1}}{t}\frac{F_{\chi}(t)}{1-t^{n}}dt,$

where $\Gamma(s)$ is the Gamma function and

$F_{\chi}(x)=\sum_{a=0}^{n-1}\chi(a)x^{a}.$

While studying quadratic characters $\chi=\left(\frac{\cdot}{p}\right)$ of
prime conductor $p$, Fekete made the observation that if $F_{\chi}(x)$ has no
real zeroes in the interval $0<x<1$, then $L(s,\chi)$ has no real zeroes on
$(0,\infty)$. In this sense, the study of $F_{\chi}(x)$ could shed light on
the existence of Siegel zeroes near $s=1$. For this historical reason, the
$F_{\chi}(x)$ are called Fekete polynomials.

Fekete polynomials have a rich mathematical history. They appear in Gauss’s
sixth proof of the quadratic reciprocity law (see [19, Chapter 10, Section
3]). Various aspects of Fekete polynomials have been studied over the years,
including their extremal properties (see [3, 4]), Mahler measure (see [11,
18]), connections to oscillations of quadratic $L$-functions (see [1]), and
distribution of their complex roots ([9]).

In recent works ([21, 22]), the last named three authors have analyzed the
arithmetic properties of Fekete polynomials when $\chi$ is a primitive
quadratic Dirichlet character. These works have shown that Fekete polynomials
contain valuable arithmetic information, such as class number and orders of
$K$-groups of certain quadratic fields. Furthermore, extensive computational
evidence suggests that $F_{\chi}(x)/x$ has exactly one irreducible non-
cyclotomic factor $f_{\chi}$, and that the Galois group of $f_{\chi}$ is as
large as possible, as stated in [22, Conjecture 4.9, Conjecture 4.13] and [21,
Conjecture 11.16].

In this article, we consider the story for principal Dirichlet characters.
Already in this seemingly simple situation, we notice some interesting
phenomena akin to the primitive quadratic case discussed above. Concretely, we
consider
$\chi_{n}:\operatorname{\mathbb{Z}}\to\operatorname{\mathbb{C}}^{\times}$
defined by

$\chi_{n}(a)=\begin{cases}0&{\text{if }}\;\gcd(a,n)>1\\\ 1&{\text{if
}}\;\gcd(a,n)=1.\end{cases}$

and let $F_{n}(x)$ denote the associated Fekete polynomial $F_{\chi_{n}}(x)$.
That is,

(1.2) $\displaystyle F_{n}(x)=\sum_{\begin{subarray}{c}0\leq a\leq n-1\\\
\gcd(a,n)=1\end{subarray}}x^{a}.$

Since $\gcd(n-1,n)=1$, the degree of $F_{n}$ is $n-1.$ In this article, we
begin the study of $F_{n}$, focusing in particular on the determination and
arithmetic of the factors of $F_{n}$, both cyclotomic and non-cyclotomic.

We observe that the non-cyclotomic part of $F_{n}(x)/x$, which we denote by
$f_{n}$, seems to be always irreducible. Similar to the case of quadratic
characters investigated in [21, 22], the Galois group of $f_{n}$ is as large
as possible subject to a condition on the discriminant. We also notice that
the coefficients of $f_{n}$ are relatively small. When $n=3p$ for a prime
$p>3$, we prove in 4.2 that the coefficients of $f_{3p}$ belong to the set
$\\{-2,-1,0,1,2\\}$. This suggests that $f_{n}$ may have noteworthy extremal
properties that we intend to explore in the future. It is important to note
that we approach this project from a computational standpoint, meaning that we
discovered many results in our article by computing and analyzing a large
dataset. The codes and data are available in the GitHub repository [8].

We remark that the theory of Fekete polynomials is closely related to the
construction of certain Paley graphs. When $\chi$ is a primitive quadratic
Dirichlet character, this connection is discussed in [20]. When $\chi$ is a
principal Dirichlet character, the corresponding Paley graph is called a
unitary Caley graph (see [2, 17]). These types of Paley graphs have found
applications in various fields such as coding and cryptography theory (see
[13, 16]). We hope that this work sheds more light on further applications of
Fekete polynomials and Paley graphs.

The article is structured as follows. In Section 2, we present our main
results concerning the factors of $F_{n}$. Firstly in Section 2.1, we show
that restricting to squarefree $n$ does not miss any interesting phenomena. We
then proceed to describe in 2.19 a large source of cyclotomic factors of
$F_{n}$ and prove in 2.28 that all cyclotomic factors are simple factors, with
the exception of the $4$-th cyclotomic polynomial $\Phi_{4}(x)=x^{2}+1$ which
occurs with multiplicity $2$ when $n$ is even. We also make a conjecture
relating to the full description of cyclotomic factors of $F_{n}$ (see 2.11).
Section 3 is devoted to the case where $n=pq$ for distinct odd primes $p,q$.
We conjecturally determine all cyclotomic factors of $F_{n}$ in this special
case (see 3.2). Based on this, we define the Fekete polynomial $f_{n}$ and its
trace polynomial $g_{n}$. We then study some arithmetic properties of $F_{n}$
in characteristic $p$ with the goal of showing that $f_{n}$ is separable. In
Section 4, we focus on the case $n=3p$. We show in 4.2 that the coefficients
of $f_{3p}$ lie in the set $\\{-2,-1,0,1,2\\}$. We also prove that $f_{3p}$ is
separable, by first proving it in characteristic $p$. In Section 5 we consider
the case $n=5p$, once again establishing separability of $f_{n}$, although the
proof is more involved. The last two sections discuss computational techniques
and results. Section 6 discusses algorithms for checking irreducibility of
$f_{n}$ and $g_{n}$, and Section 7 investigates their Galois groups. Finally
Appendix A discusses a tangential question of an analytic flavor, about the
proportion of complex zeroes of $F_{n}$ on the unit circle, using the approach
of [9].

##  2\. Cyclotomic factors of $F_{n}$ and their multiplicity

###  2.1. Reduction to the squarefree case

Let $n$ be a positive integer and $n_{0}$ the radical of $n$ which is defined
as the product of the distinct prime divisors of $n$. Let $\chi_{n}$ and
$\chi_{n_{0}}$ be the principal Dirichlet characters associated with $n$ and
$n_{0}$ as explained in the introduction. For an integer $a$, we know that
$\gcd(a,n)=1$ if and only if $\gcd(a,n_{0})=1.$ Therefore, by definition, we
see that $L(\chi_{n},s)=L(\chi_{n_{0}},s).$ By the integral representations of
these $L$-functions Eq. 1.1 we conclude that for all $s>1$

$\int_{0}^{1}\frac{(-\log(t))^{s-1}}{t}\frac{F_{n}(t)}{1-t^{n}}dt=\int_{0}^{1}\frac{(-\log(t))^{s-1}}{t}\frac{F_{n_{0}}(t)}{1-t^{n_{0}}}dt.$

This suggests the following proposition.

######  Proposition 2.1.

Let $n$ be an integer and $n_{0}$ the radical of $n$. Then we have the
following equality

$\frac{F_{n_{0}}(x)}{1-x^{n_{0}}}=\frac{F_{n}(x)}{1-x^{n}}.$

###### Proof.

Since $n_{0}$ is the radical of $n$, we have $\gcd(a,n)=1$ if and only if
$\gcd(a,n_{0})=1$. Therefore, we have

$\frac{F_{n_{0}}(x)}{1-x^{n_{0}}}=F_{n_{0}}(x)\sum_{k=0}^{\infty}x^{kn_{0}}=\sum_{\begin{subarray}{c}1\leq
a\\\ \gcd(a,n_{0})=1\end{subarray}}x^{a}=\sum_{\begin{subarray}{c}1\leq a\\\
\gcd(a,n)=1\end{subarray}}x^{a}=\frac{F_{n}(x)}{1-x^{n}}.$

∎

######  Corollary 2.2.

Let $f\in\operatorname{\mathbb{Z}}[x]$ be a non-cyclotomic irreducible
polynomial. Then $f$ is a divisor of $F_{n}$ if and only if $f$ is a divisor
of $F_{n_{0}}$. ∎

######  Corollary 2.3.

Suppose that $n$ is an odd integer and $n_{0}$ is its radical. Then
$F_{n}(-1)=F_{n_{0}}(-1)=0$ and $F_{n}^{\prime}(-1)=F_{n_{0}}^{\prime}(-1)$. ∎

###  2.2. Cyclotomic factors of $F_{n}$

We let $n$ be a positive squarefree integer here onwards, thanks to 2.1. To
get started we calculate the Fekete polynomial $F_{n}(x)$ in a few simple
situations.

######  Example 2.4.

Let $p$ be a prime number. Then we have the factorisation of $F_{p}(x)$.

(2.1) $\displaystyle
F_{p}(x)=x+x^{2}+\ldots+x^{p-1}=x\frac{1-x^{p-1}}{x-1}=x\prod_{\begin{subarray}{c}d|p-1\\\
d>1\end{subarray}}\Phi_{d}(x).$

######  Example 2.5.

Let $p$ be an odd prime. Then we have the following factorisation of
$F_{2p}(x)$.

(2.2)
$\displaystyle\begin{split}F_{2p}(x)&=(x+x^{3}+\cdots+x^{p-2})+(x^{p+2}+x^{p+4}+\cdots+x^{2p-1})\\\
&=x(1+x^{2}+\cdots+x^{p-3})(1+x^{p+1})=x\dfrac{x^{p-1}-1}{x^{2}-1}\dfrac{x^{2(p+1)}-1}{x^{p+1}-1}\\\
&=x\prod_{2<d\mid(p-1)}\Phi_{d}(x)\prod_{\begin{subarray}{c}d\mid 2(p+1)\\\
d\nmid p+1\end{subarray}}\Phi_{d}(x).\end{split}$

While we were able to completely describe the cyclotomic factors of $F_{n}$ in
the two examples above, this is quite delicate in general. Moreover, these
examples are unrepresentative of the general situation where non-cyclotomic
factors also show up. Using SageMath we computed the factorisation of the
Fekete polynomial $F_{n}$ as defined in Eq. 1.2 for all $n<10000$. When $n\neq
p$ or $2p$ for any prime $p$, we observe that $F_{n}(x)/x$ has many cyclotomic
factors and _exactly one_ irreducible non-cyclotomic factor. This striking
observation leads us to the study of the cyclotomic factors of $F_{n}$.

Our starting point in this endeavor is the result that if $d|n$ then the
$d$-th cyclotomic polynomial $\Phi_{d}$ is _not_ a factor of $F_{n}$. This is
a direct consequence of the theory of Ramanujan sums (see [15] for a detailed
treatment) which is partially summarized in the following proposition.

######  Proposition 2.6.

Let $n$ be a positive integer and $d$ a divisor of $n$. Let $k$ be a field
such that $d$ is invertible in $k$. Suppose $\zeta_{d}$ is a primitive $d$-th
root of unity in $k$. Then

$F_{n}(\zeta_{d})=\frac{\mu(d)\varphi(n)}{\varphi(d)}.$

Here $\mu$ denotes the Mobius function and we consider $F_{n}[x]$ as a
polynomial over $k[x]$ under the canonical map
$\operatorname{\mathbb{Z}}[x]\to k[x].$

###### Proof.

If $\mathrm{char}(k)=0$, by embedding the subfield
$\operatorname{\mathbb{Q}}(\zeta_{d})\subseteq k$ in $\mathbf{C}$, we have

$F_{n}(\zeta_{d})=\sum_{\begin{subarray}{c}1\leq a\leq n\\\
\gcd(a,n)=1\end{subarray}}\exp\left(\frac{2\pi ia}{d}\right),$

which is a Ramanujan sum (see [15, Section 5.6]). Hence by [15, Theorem 272],
we have $F_{n}(\zeta_{d})=\frac{\mu(d)\varphi(n)}{\varphi(d)}$.

To deal with positive characteristics, we first note that the statement is
entirely algebraic with all objects defined over the ring of integers
$\mathcal{O}_{F}=Z[\zeta_{d}]$ of the cyclotomic field
$F=\operatorname{\mathbb{Q}}(\zeta_{d})$. Indeed, we have

$F_{n}(x)\in\operatorname{\mathbb{Z}}[x],\quad\zeta_{d}\in\mathcal{O}_{F},\quad\mu(d)=\sum_{\begin{subarray}{c}1\leq
a\leq n\\\
\gcd(a,n)=1\end{subarray}}\zeta_{d}^{a}\in\mathcal{O}_{F},\quad\phi(n)=\sum_{\begin{subarray}{c}1\leq
a\leq n\\\ \gcd(a,n)=1\end{subarray}}1\in\operatorname{\mathbb{Z}}.$

If $\mathrm{char}(k)=p$, by considering reduction modulo a prime ideal of
$\mathcal{O}_{F}$ above $p$, we see that the same formula should hold over
$k$. ∎

######  Corollary 2.7.

If $d|n$ then $F_{n}(\zeta_{d})\neq 0.$ In other words, $\Phi_{d}$ is not a
factor of $F_{n}.$ ∎

Hereafter we assume that $d\nmid n$. Let $d_{1}=\gcd(d,n)$ so that $d_{1}\neq
d$, and let $S$ be the set $\\{0\leq a<d|\gcd(a,d_{1})=1\\}$. Note that if we
identify the integer residues modulo $d$ with the set
$[d]=\\{0,1,\ldots,d-1\\}$, then $S\subset[d]$ is the preimage of the set
$(\operatorname{\mathbb{Z}}/d_{1})^{\times}$ under the reduction map
$\operatorname{\mathbb{Z}}/d\to\operatorname{\mathbb{Z}}/d_{1}$. Thus we have
$\\#S=\frac{\varphi(d_{1})d}{d_{1}}$. Consider the polynomial
$F_{S}(x)=\sum_{s\in S}x^{s}$. The following lemma gives some useful
information about $F_{S}$.

######  Lemma 2.8.

With notation as above, we have
$F_{S}(x)=\frac{1-x^{d}}{1-x^{d_{1}}}F_{d_{1}}(x)$. Let $m|d$ be a positive
integer, and $\zeta=\zeta_{m}$ be a primitive $m$-th root of unity. Then

$F_{S}(\zeta)=\begin{cases}0&{\text{if }}\;m\nmid d_{1}\\\
\frac{d}{d_{1}}\frac{\mu(m)\varphi(d_{1})}{\varphi(m)}&{\text{if
}}\;m|d_{1}.\end{cases}$

###### Proof.

Noting that the expression $(1-x^{d_{1}})F_{S}(x)$ is a telescopic sum, we get

$(1-x^{d_{1}})F_{S}(x)=(1-x^{d_{1}})\sum_{0\leq
j<d/d_{1}}\sum_{\begin{subarray}{c}1\leq i\leq d_{1}\\\
(i,d_{1})=1\end{subarray}}x^{jd_{1}+i}=(1-x^{d})F_{d_{1}}(x).$

Since $m|d$ we have $1-\zeta^{d}=0$. If $m\nmid d_{1}$, then
$1-\zeta^{d_{1}}\neq 0$. So $F_{S}(\zeta)=0$. If $m|d_{1}$, then the value of
$\frac{1-x^{d}}{1-x^{d_{1}}}$ at $x=\zeta$ is $\frac{d}{d_{1}}$. Further 2.6
gives $F_{d_{1}}(\zeta)=\frac{\mu(m)\varphi(d_{1})}{\varphi(m)}$. ∎

We can now state a sufficient condition for the $d$-th cyclotomic polynomial
$\Phi_{d}$ to be a factor of $F_{n}$. Note that, in order to determine whether
$F_{n}(\zeta_{d})$ is zero or not, it is sufficient to consider
$F_{n}(x)\pmod{x^{d}-1}$.

######  Proposition 2.9.

Let $n$ be a positive squarefree integer. Let $d>1$ be an integer not dividing
$n$. Let $d_{1}=\gcd(d,n)$ and $S=\\{1\leq a\leq d|\gcd(a,d_{1})=1\\}$. If the
elements of $\\{1\leq a\leq n|\gcd(a,n)=1\\}$ when reduced modulo $d$,
equidistribute among the elements of $S$, then the $d$-th cyclotomic
polynomial $\Phi_{d}$ divides $F_{n}$.

###### Proof.

Let $F_{S}(x)=\sum_{s\in S}x^{s}$ be the polynomial introduced earlier. If the
equidistribution condition holds, then by reducing modulo $d$ the exponents of
monomials in $F_{n}$, we see that $F_{n}(x)\equiv cF_{S}(x)\pmod{x^{d}-1}$ for
some constant $c$. To be precise,
$c=c_{n,d}=\frac{\varphi(n)}{\\#S}=\frac{\varphi(n)d_{1}}{\varphi(d_{1})d}$.
So it is enough to show that $F_{S}(\zeta_{d})=0$, which we get from 2.8 since
$d>d_{1}$. ∎

######  Remark 2.10.

In the proof above, we saw that the equidistribution property implies
$F_{n}\equiv cF_{S}\pmod{x^{d}-1}$. In fact they are equivalent. If
$F_{n}=cF_{S}+(x^{d}-1)G$ for some $G\in\operatorname{\mathbb{Q}}[x]$, then
for each $s\in S$, we can sum the coefficients of the monomials $x^{a}$ with
$a\equiv s\pmod{d}$ occuring on each side. This gives us that $\\#\\{1\leq
a\leq n|\gcd(a,n)=1,a\equiv s\pmod{d}\\}=c$ independent of $s$, yielding
equidistribution.

It is interesting to ask if the converse of 2.9 is true. In all cases we have
computed, the converse holds. See 2.23 for the cases where the converse is
proven to be true. This prompts us to make the conjecture.

######  Conjecture 2.11.

Let $n,d,d_{1},S$ be as in 2.9. Then $\Phi_{d}$ divides $F_{n}$ if and only if
the elements of $\\{1\leq a\leq n|\gcd(a,n)=1\\}$ when reduced modulo $d$,
equidistribute in $S$. Equivalently, $\Phi_{d}$ divides $F_{n}$ if and only if
$x^{d}-1$ divides $F_{n}-\frac{\varphi(n)d_{1}}{\varphi(d_{1})d}F_{S}$

######  Remark 2.12.

In Section 3 we give a complete description of the cyclotomic factors of
$F_{n}$ when $n=pq$ is a product of two odd primes, contingent on 2.11.

######  Remark 2.13.

If $d=p$ is a prime not dividing $n$, then it is straightforward to see that
2.11 holds. This is because the only linear relation among
$\\{1,\zeta_{p},\zeta_{p}^{2},\ldots,\zeta_{p}^{p-1}\\}$ is that they sum to
$0$.

We now write down a recursive formula for $F_{n}$. This will be useful in
obtaining a neater description of $F_{n}$ in 2.17, which will be crucial in
describing certain explicit cyclotomic factors of $F_{n}$ (2.19) and their
multiplicites (2.28).

######  Proposition 2.14.

Let $p$ be a prime number such that $\gcd(p,n)=1.$ Then we have the following
recursive formula

$\frac{F_{np}(x)}{1-x^{np}}=\dfrac{F_{n}(x)}{1-x^{n}}-\frac{F_{n}(x^{p})}{1-x^{np}}.$

###### Proof.

We have

$\begin{aligned} \dfrac{F_{np}(x)}{1-x^{np}}&=\sum_{\begin{subarray}{c}1\leq
a\\\ \gcd(a,np)=1\end{subarray}}x^{a}=\sum_{\begin{subarray}{c}1\leq a\\\
\gcd(a,n)=1\end{subarray}}x^{a}-\sum_{\begin{subarray}{c}1\leq a\\\
\gcd(a,n)=1\end{subarray}}x^{pa}=\dfrac{F_{n}(x)}{1-x^{n}}-\dfrac{F_{n}(x^{p})}{1-x^{np}}.\end{aligned}\qed$

######  Corollary 2.15.

Let $n>1$ be a squarefree integer and $d$ a positive integer not dividing $n$.
If $\Phi_{d}$ is a factor of $F_{n}$, then $\Phi_{d}$ is also a factor of
$F_{np}$ for every prime number $p$ with ${\rm gcd}(d,p)=1$.

###### Proof.

If $\zeta$ is a primitive $d$-th root of unity, $\zeta^{p}$ is also a
primitive $d$-th root of unity. Hence $F_{n}(\zeta)=F_{n}(\zeta^{p})=0$.
Therefore, 2.14 implies $F_{np}(\zeta)=0$ as well. ∎

######  Corollary 2.16.

Let $n>1$ be a squarefree integer and $d$ a positive integer not dividing $n$.
Let $p,q$ be two distinct primes such that $p\equiv q\pmod{d}$. Then
$\Phi_{d}$ is a factor of $F_{np}$ if and only if it is a factor of $F_{nq}.$

###### Proof.

Since $p\neq q$ and $p\equiv q\pmod{d}$, we get that $p\nmid d$. So $d\nmid
np$ and we can evalute the formula in 2.14 at $\zeta_{d}$. Since
$\zeta_{d}^{p}=\zeta_{d}^{q}$, we deduce that
$F_{np}(\zeta_{d})=F_{nq}(\zeta_{d})$. ∎

Using this recursive formula of 2.14, we get the following description for
$F_{n}$ as a sum over divisors of $n$. This will used crucially in what
follows.

######  Proposition 2.17.

Let $n>1$ be a squarefree integer. Then

(2.3)
$\displaystyle\frac{F_{n}(x)}{1-x^{n}}=\sum_{m|n}\mu(m)\frac{x^{m}}{1-x^{m}}.$

###### Proof.

We prove by induction on the number of prime factors of $n$. If $n=q$ is prime
then

$\frac{F_{q}(x)}{1-x^{q}}=\frac{x+x^{2}+\cdots+x^{q}-x^{q}}{1-x^{q}}=\dfrac{x}{1-x}-\dfrac{x^{q}}{1-x^{q}}=\sum_{m|q}\frac{\mu(m)x^{m}}{1-x^{m}}.$

Now suppose that the statement is true for a squarefree integer $n$. Let $p$
be a prime number such that $\gcd(p,n)=1$. We show that the statement holds
true for $np$. Indeed, by 2.14 and the induction hypothesis we have

$\displaystyle\dfrac{F_{np}(x)}{1-x^{np}}$
$\displaystyle=\dfrac{F_{n}(x)}{1-x^{n}}-\dfrac{F_{n}(x^{p})}{1-x^{np}}=\sum_{m|n}\mu(m)\frac{x^{m}}{1-x^{m}}-\sum_{m|n}\mu(m)\frac{x^{pm}}{1-x^{pm}}$
$\displaystyle=\sum_{m|n}\mu(m)\frac{x^{m}}{1-x^{m}}+\sum_{pm|pn}\mu(pm)\frac{x^{pm}}{1-x^{pm}}=\sum_{m|np}\mu(m)\frac{x^{m}}{1-x^{m}}.$

∎

One consequence of 2.17 is a formula for $F_{n}^{\prime}(-1)$. This will be
useful later in Section 3 to describe the value of the reduced Fekete
polynomial $f_{n}(x)$ at $x=-1$.

######  Proposition 2.18.

Let $n>1$ be an integer and $n_{0}$ its radical. Then

$F_{n}^{\prime}(-1)=\sum_{1\leq k\leq
n,\gcd(k,n)=1}(-1)^{k-1}k=\begin{cases}\dfrac{n\varphi(n)}{2}&\text{if $n$ is
even }\\\ \dfrac{\mu(n_{0})\varphi(n_{0})}{2}&\text{if $n$ is odd.
}\end{cases}$

###### Proof.

Suppose $n$ is even. Then

$\displaystyle F_{n}^{\prime}(-1)=\sum_{\begin{subarray}{c}1\leq k\leq n\\\
\gcd(k,n)=1\end{subarray}}(-1)^{k-1}k=\sum_{\begin{subarray}{c}1\leq k\leq
n\\\ \gcd(k,n)=1\end{subarray}}k=\sum_{\begin{subarray}{c}1\leq k\leq n/2\\\
\gcd(k,n)=1\end{subarray}}\left(k\quad+\quad
n-k\right)=\dfrac{n\varphi(n)}{2}.$

Now suppose $n$ is odd. By 2.3, we may assume that $n$ is squarefree.
Differentiating Eq. 2.3, we get

$F^{\prime}_{n}(x)=nx^{n-1}\sum_{m|n}\mu(m)\frac{x^{m}}{x^{m}-1}+(x^{n}-1)\sum_{m|n}\mu(m)\frac{-mx^{m-1}}{(x^{m}-1)^{2}}.$

Hence

$F^{\prime}_{n}(-1)=\dfrac{n}{2}\sum_{m|n}\mu(m)+\dfrac{1}{2}\sum_{m|n}\mu(m)m=\dfrac{1}{2}\mu(n)\sum_{m|n}\mu(n/m)m=\dfrac{1}{2}\mu(n)\varphi(n).$

∎

We now utilize 2.17 and the inclusion-exclusion principle to catch a big chunk
of cyclotomic factors of $F_{n}$.

######  Theorem 2.19.

Let $n$ be a positive squarefree integer. Suppose $N>1$ is a divisor of $n$
and $T$ is a partition of the set of all divisors of $N$ into two-element
subsets $\\{a_{1},b_{1}\\},\\{a_{2},b_{2}\\},\ldots,\\{a_{l},b_{l}\\}$. Let
$D=\gcd_{i}(a_{i}+\mu(a_{i})\mu(b_{i})b_{i})$. Then $\Phi_{d}$ divides $F_{n}$
for every $d|D$ such that $d\nmid n$.

###### Proof.

Let $\zeta$ be a primitive $d$-th root of unity. Since $d\nmid n$, we can
evaluate Eq. 2.3 at $\zeta$.

$\displaystyle\frac{F_{n}(\zeta)}{1-\zeta^{n}}=\sum_{m|n}\frac{\mu(m)\zeta^{m}}{1-\zeta^{m}}=\sum_{m|(n/N)}\sum_{i=1}^{l}\frac{\mu(a_{i}m)\zeta^{a_{i}m}}{1-\zeta^{a_{i}m}}+\frac{\mu(b_{i}m)\zeta^{b_{i}m}}{1-\zeta^{b_{i}m}}.$

Without loss of generality, suppose that $\mu(a_{i})=\mu(b_{i})$ for $1\leq
i\leq l_{0}$ and $\mu(a_{i})=-\mu(b_{i})$ for $i>l_{0}$. Note that this means

$\displaystyle
2\sum\limits_{i=1}^{l_{0}}\mu(a_{i})=\sum\limits_{i=1}^{l_{0}}\left(\mu(a_{i})+\mu(b_{i})\right)=\sum\limits_{i=1}^{l}\left(\mu(a_{i})+\mu(b_{i})\right)=\sum\limits_{k|N}\mu(k)=0.$

For $i>l_{0}$, since $d|(a_{i}-b_{i})$ we have $\zeta^{a_{i}}=\zeta^{b_{i}}$
and hence

$\displaystyle\frac{\mu(a_{i}m)\zeta^{a_{i}m}}{1-\zeta^{a_{i}m}}+\frac{\mu(b_{i}m)\zeta^{b_{i}m}}{1-\zeta^{b_{i}m}}=0.$

For $i\leq l_{0}$, since $d|(a_{i}+b_{i})$ we have
$\zeta^{a_{i}}=\zeta^{-b_{i}}$ and hence

$\displaystyle\frac{\mu(a_{i}m)\zeta^{a_{i}m}}{1-\zeta^{a_{i}m}}+\frac{\mu(b_{i}m)\zeta^{b_{i}m}}{1-\zeta^{b_{i}m}}=-\mu(a_{i}m).$

Putting things together, we get that

$\displaystyle\frac{F_{n}(\zeta)}{1-\zeta^{n}}=\sum_{m|n}\frac{\mu(m)\zeta^{m}}{1-\zeta^{m}}=\sum_{m|(n/N)}\sum_{i=1}^{l_{0}}-\mu(a_{i}m)=-\sum_{m|(n/N)}\mu(m)\sum_{i=1}^{l_{0}}\mu(a_{i})=0.$

This proves that $F_{n}(\zeta)=0$, and hence $\Phi_{d}$ divides $F_{n}$. ∎

We will use the following special case of this theorem the most.

######  Corollary 2.20.

Let $r$ be a prime factor of $n$ and suppose $d$ is an integer dividing $r-1$
such that $d\nmid n$. Then $\Phi_{d}$ divides $F_{n}$. ∎

For a prime number $p$, we also have a necessary condition for $\Phi_{p}$ to
divide $F_{n}$.

######  Proposition 2.21.

Let $p$ be a prime number such that $p\nmid n$. If $\Phi_{p}$ is a factor of
$F_{n}$ then $p|\varphi(n)$, i.e., there exists a prime divisor $r$ of $n$
such that $p|r-1.$

###### Proof.

If $\Phi_{p}$ is a factor of $F_{n}$ then $F_{n}=\Phi_{p}Q$ for some
$Q\in\operatorname{\mathbb{Z}}[x]$. Hence
$\varphi(n)=F_{n}(1)=\Phi_{p}(1)Q(1)=pQ(1)$ and thus $p\mid\varphi(n)$.
Alternatively, by 2.13, we know that 2.11 holds in this case. So the elements
of $\\{1\leq a\leq n|\gcd(a,n)=1\\}$ when reduced modulo $p$, equidistribute
in $S=\\{0,1,\ldots,p-1\\}$. Therefore $p=\\#S$ divides $\varphi(n)$. ∎

Combining 2.20 and 2.21, we have the following.

######  Corollary 2.22.

Let $p$ be a prime number. Then $\Phi_{p}$ is a factor of $F_{n}$ if and only
if $p\nmid n$ and there exists a prime divisor $r$ of $n$ such that $p|r-1$. ∎

We observe that all cyclotomic factors described by 2.19 satisfy the
equidistribution condition mentioned in 2.9.

######  Theorem 2.23.

Let $n,N,D$ be as in 2.19. Suppose $D\nmid n$. Let $d=D$ and
$d_{1}=\gcd(d,n)$. Then the elements of $\\{1\leq a\leq n\mid\gcd(a,n)=1\\}$
when reduced modulo $d$, equidistribute in $S=\\{1\leq a\leq
d|\gcd(a,d_{1})=1\\}$. Equivalently, we have that $x^{d}-1$ divides
$F_{n}-cF_{S}=F_{n}-c\sum\limits_{s\in S}x^{s}$ for some constant $c$.

###### Proof.

Let $c=\frac{\varphi(n)d_{1}}{d\varphi(d_{1})}$ and consider the polynomial
$W(x)=F_{n}(x)-cF_{S}(x)$. By 2.10 it is enough to show that $x^{d}-1$ divides
$W(x)$.

Let $m$ be any integer dividing $d$, and $\zeta_{m}$ be a primitive $m$-th
root of unity. If $m\nmid n$ then we know $F_{n}(\zeta_{m})=0$ by 2.19 and
$F_{S}(\zeta_{m})=0$ by 2.8. Hence $W(\zeta_{m})=0$. If $m|n$ then
$m|d_{1}=\gcd(d,n)$, and we again deduce that $W(\zeta_{m})=0$ by 2.6 and 2.8.
∎

###  2.3. Multiplicity of cyclotomic factors

In this section, we determine the multiplicity of cyclotomic factors of
$F_{n}.$ To do so, we need to investigate the value
$F^{\prime}_{n}(\zeta_{d})$ whenever $F_{n}(\zeta_{d})=0$. By 2.7, $\zeta_{d}$
is not a root of $F_{n}$ if $d|n$. Therefore, we can assume that $d\nmid n$ in
our investigation. By 2.17 we have

(2.4)
$F^{\prime}_{n}(x)=nx^{n-1}\sum_{m|n}\mu(m)\frac{x^{m}}{x^{m}-1}+(x^{n}-1)\sum_{m|n}\mu(m)\frac{-mx^{m-1}}{(x^{m}-1)^{2}}.$

We introduce the following polynomial

$G_{n}(x)=(x^{n}-1)^{2}\sum_{m|n}\mu(m)\frac{mx^{m}}{(x^{m}-1)^{2}},$

so that Eq. 2.4 becomes

(2.5) $x(x^{n}-1)F^{\prime}_{n}(x)=nx^{n}F_{n}(x)-G_{n}(x).$

Expanding this out using the definition of $F_{n}$, we have the following
explicit formula

(2.6)
$\begin{split}G_{n}(x)&=nx^{n}F_{n}(x)-(x^{n+1}-x)F^{\prime}_{n}(x)=\sum_{\begin{subarray}{c}1\leq
a\leq n\\\ \gcd(a,n)=1\end{subarray}}\left(ax^{a}+(n-a)x^{n+a}\right)\\\
&=\sum_{\begin{subarray}{c}1\leq a\leq n\\\
\gcd(a,n)=1\end{subarray}}(n-a)[x^{n+a}+x^{n-a}]=x^{n}\sum_{\begin{subarray}{c}1\leq
a\leq n\\\ \gcd(a,n)=1\end{subarray}}(n-a)[x^{a}+x^{-a}]\end{split}$

######  Lemma 2.24.

Let $d$ be a positive integer and $n$ a positive squarefree integer. Let
$\zeta=\zeta_{d}$ be a primitive $d$-th root of unity.

  1. (1)

If $n$ is even then $\zeta_{4}$ is a root of $G_{n}.$

  2. (2)

If $d\geq 2n$ then $G_{n}(\zeta)\neq 0$ unless $n=2$ and $d=4.$

###### Proof.

The first part follows immediately from Eq. 2.6 and the fact that
$\zeta_{4}^{a}+\zeta_{4}^{-a}=0$ for odd integers $a$. For the second part we
first rewrite Eq. 2.6 as follows

$\displaystyle x^{-n}G_{n}(x)$ $\displaystyle=\sum_{\begin{subarray}{c}1\leq
a\leq\frac{n}{2}\\\
\gcd(a,n)=1\end{subarray}}\left[(n-a)(x^{a}+x^{-a})+a(x^{n-a}+x^{a-n})\right]$
$\displaystyle=\sum_{\begin{subarray}{c}1\leq a\leq\frac{n}{2}\\\
\gcd(a,n)=1\end{subarray}}(n-2a)[x^{a}+x^{-a}]+\sum_{\begin{subarray}{c}1\leq
a\leq\frac{n}{2}\\\
\gcd(a,n)=1\end{subarray}}a[x^{a}+x^{-a}+x^{n-a}+x^{a-n}].$

Working over $\operatorname{\mathbb{C}}$, if we let $\zeta_{d}=e^{\frac{2\pi
i}{d}}$, then by Euler formula we have

$\zeta_{d}^{-n}G_{n}(\zeta_{d})=2\sum_{\begin{subarray}{c}1\leq
a\leq\frac{n}{2}\\\ \gcd(a,n)=1\end{subarray}}(n-2a)\cos\left(\frac{2\pi
a}{d}\right)+4a\sum_{\begin{subarray}{c}1\leq a\leq\frac{n}{2}\\\
\gcd(a,n)=1\end{subarray}}\cos\left(\frac{\pi
n}{d}\right)\cos\left(\frac{(n-2a)\pi}{d}\right)$

Since $d\geq 2n$ and $1\leq a\leq\frac{n}{2}$, each term in the sum is non-
negative and we get $\zeta_{d}^{-n}G_{n}(\zeta_{d})\geq 0$. Further, if
$G_{n}(\zeta_{d})=0$ then it must be the case that
$(n-2)\cos\left(\frac{2\pi}{d}\right)=0$ and
$\cos\left(\frac{n\pi}{d}\right)\cos\left(\frac{(n-2)\pi}{d}\right)=0$. This
implies that $d=4$ and $n=2.$ ∎

We remark that by Eq. 2.5, $\zeta=\zeta_{d}$ is simple root of $F_{n}$ if and
only if $F_{n}(\zeta)=0$ and $G_{n}(\zeta)\neq 0$. Using the definition of
$G_{n}$, we also get the following recursive formula for $G_{n}$ analogous to
the one for $F_{n}$ described in 2.14. If $p\nmid n$, then

$G_{np}(x)=\left(\frac{1-x^{np}}{1-x^{n}}\right)^{2}G_{n}(x)-pG_{n}(x^{p}).$

To study the multiplicity of $\Phi_{d}$ as a factor of $G_{n}$, we will use a
general proposition.

######  Proposition 2.25.

Let $G(x)=\frac{P(x)}{Q(x)}$ where $P(x),Q(x)$ are polynomials with rational
coefficients. Let $d$ be a positive number and $\zeta=\zeta_{d}$ a primitive
$d$-th root of unity such that $Q(\zeta)\neq 0$. Let $p$ be a prime number
such that $p\nmid d$. Let $G_{p}(x)$ be the following rational function

$G_{p}(x)=G(x)-pG(x^{p}).$

Then

${\rm mult}_{\zeta_{d}}(G)={\rm mult}_{\zeta_{d}}(G_{p}).$

###### Proof.

By induction, we can see that for each $k\geq 0$

(2.7) $G_{p}^{(k)}(x)=G^{(k)}(x)-p^{k+1}x^{k(p-1)}G^{(k)}(x^{p})+\sum_{0\leq
h\leq k-1}M_{k,h}(x)G^{(h)}(x^{p}),$

where $M_{k,h}\in\operatorname{\mathbb{Q}}[x].$ In order to prove the above
statement, we will show that for all $k\geq 0$,
$G(\zeta)=\cdots=G^{(k)}(\zeta)=0$ if and only if
$G_{p}(\zeta)=\cdots=G_{p}^{(k)}(\zeta)=0$.

Let us consider the base case $k=0.$ Suppose that $G(\zeta)=0.$ Since $\zeta$
and $\zeta^{p}$ are Galois-conjugate and $G$ is a rational function with
rational coefficients, $G(\zeta^{p})=0$ as well. We conclude that
$G_{p}(\zeta)=0$. Conversely, suppose that $G_{p}(\zeta)=0$, i.e.,
$G(\zeta)=pG(\zeta^{p})$. Since $G_{p}\in\operatorname{\mathbb{Q}}(x)$, we
have this equality for any primitive $d$-th root of unity. In particular
$G(\zeta)=pG(\zeta^{p})=p^{2}G(\zeta^{p^{2}})=\ldots=p^{\varphi(d)}G(\zeta)$.
This means that $G(\zeta)=0$.

Assume that the statement holds for $k-1.$ Let us show that it is true for $k$
as well. First, suppose that $G(\zeta)=\cdots=G^{(k)}(\zeta)=0$. By the
induction hypothesis, we already know that
$G_{p}(\zeta)=\cdots=G_{p}^{(k-1)}(\zeta)=0$. Since $\zeta$ and $\zeta^{p}$
are Galois conjugate over $\operatorname{\mathbb{Q}}$, we know that
$G^{(h)}(\zeta^{p})=0$ for $0\leq h\leq k$ as well. By Eq. 2.7, we conclude
that $G_{p}^{(k)}(\zeta)=0$. Conversely, assume that
$G_{p}(\zeta)=\cdots=G_{p}^{(k)}(\zeta)=0$. By the induction hypothesis, we
know that $G(\zeta)=\cdots=G^{(k-1)}(\zeta)=0$. Let us show that
$G^{(k)}(\zeta)=0$. Because of Galois conjugacy we again know that
$G(\zeta^{p})=\cdots=G^{(k-1)}(\zeta^{p})=0$. Additionally, since
$G_{p}^{(k)}(\zeta)=0$, Eq. 2.7 tells us that

$G^{(k)}(\zeta)=p^{k+1}\zeta^{k(p-1)}G^{(k)}(\zeta^{p}).$

Since this equality holds for any primitive $d$-th root of unity, a similar
argument as in the base case lets us conclude that $G^{(k)}(\zeta)=0$. ∎

######  Corollary 2.26.

Suppose that $p\nmid nd$ and $d\nmid n$. Let $\zeta=\zeta_{d}$ be a primitive
$d$-th root of unity. Then ${\rm mult}_{\zeta}(G_{n})={\rm
mult}_{\zeta}(G_{np})$.

###### Proof.

Consider the slightly modified function

$\tilde{G}_{n}(x)=\frac{G_{n}(x)}{(1-x^{n})^{2}}.$

Since $d\nmid np$, $\zeta=\zeta_{d}$ is not a root of $x^{np}-1$. So ${\rm
mult}_{\zeta}(G_{n})={\rm mult}_{\zeta}(\tilde{G}_{n})$ and ${\rm
mult}_{\zeta}(G_{np})={\rm mult}_{\zeta}(\tilde{G}_{np})$. Furthermore we have
$\tilde{G}_{np}(x)=\tilde{G}_{n}(x)-p\tilde{G}(x^{p})$. Applying 2.25 to
$\tilde{G}_{n}$ gives the desired statement. ∎

When $n=q$ is a prime number, we have

$G_{q}(x)=(x^{q}-1)^{2}\left[\frac{x}{(1-x)^{2}}-\frac{qx^{q}}{(1-x^{q})^{2}}\right]=xH_{q}(x),$

where

$H_{q}(x)=\left(\frac{1-x^{q}}{1-x}\right)^{2}-qx^{q-1}.$

Note that $H_{2}(x)=x^{2}+1=\Phi_{4}(x)$.

######  Lemma 2.27.

The polynomial $H_{q}(x+1)$ is an Eisenstein polynomial at the prime $q.$
Consequently, $H_{q}(x)$ is irreducible. Moreover, if $q$ is odd, then
$\zeta_{d}$ is not a root of $H_{q}$ for any $d$, and hence $\zeta_{d}$ is not
a root of $G_{q}$.

###### Proof.

Over $\operatorname{\mathbb{F}}_{q}$ we have $H_{q}(x)=(1-x)^{2(q-1)}$.
Additionally $H_{q}(1)=q^{2}-q$. This shows that $H_{q}(x+1)$ is an Eisenstein
polynomial at the prime $q$.

Suppose on the contrary that $\zeta_{d}$ is a root of $H_{q}.$ Since
$\Phi_{d}(x)$ and $H_{q}(x)$ are both irreducible, we must have
$\Phi_{d}=H_{q}.$ In particular

$q^{2}-q=H_{q}(1)=\Phi_{d}(1).$

If $d=p^{k}$ is a prime power ($k\geq 1$) then $\Phi_{d}(1)=p$. In this case,
we have $p=q^{2}-q$, which implies that $q|p$ and hence $q=p=2$. If $d$ is not
a prime power then $\Phi_{d}(1)=1$. But there is no prime $q$ such that
$q^{2}-q=1$. ∎

With these preparations, we can now describe the multiplicity of any
cyclotomic factor $\Phi_{d}$ of $F_{n}$.

######  Theorem 2.28.

Let $n>1$ be a squarefree integer. Let $d$ be a positive integer and
$\zeta=\zeta_{d}$ a primitive $d$-th root of unity such that $F_{n}(\zeta)=0$.
Then we have the following.

  1. (1)

If $d\neq 4$, then $\zeta_{d}$ is a simple roof of $F_{n}.$

  2. (2)

If $d=4$ and $n$ is odd, then $\zeta_{d}$ is a simple roof of $F_{n}.$

  3. (3)

If $d=4$ and $n$ is even, then $\zeta_{d}$ is a double root of $F_{n}.$

###### Proof.

We will prove the first and second statements by showing the contrapositive.
Suppose that $\zeta=\zeta_{d}$ is a repeated root of $F_{n}.$ Then we know
that $d\nmid n$ and that $F_{n}(\zeta)=G_{n}(\zeta)=0.$ Let $d_{1}=\gcd(n,d).$
Let us write $n=d_{1}n_{1}$ where $\gcd(n_{1},d)=1.$ Since $n$ is a squarefree
integer, this also implies that $\gcd(n_{1},d_{1}d)=1.$ Since
$G_{n}(\zeta)=G_{d_{1}n_{1}}(\zeta)=0$, 2.26 implies that $G_{d_{1}}(\zeta)=0$
as well. Since $d\geq 2d_{1}$ we conclude by 2.24 that $d=4$ and $d_{1}=2$
meaning that $n$ is even.

When $d=4$ and $n$ is even, we know by 2.26 that ${\rm
mult}_{\zeta_{4}}(G_{n})={\rm mult}_{\zeta_{4}}(G_{2})=1$. Eq. 2.5 then shows
that $F_{n}(\zeta_{4})=F_{n}^{\prime}(\zeta_{4})=0$ but
$F_{n}^{\prime\prime}(\zeta_{4})\neq 0.$ This proves that $\zeta_{4}$ is a
double root of $F_{n}$. ∎

######  Remark 2.29.

It is not true that ${\rm mult}_{\zeta_{4}}(F_{n})=2$ for all even squarefree
integers $n$. For instance, 2.5 says that for odd primes $p$,
$F_{2p}(\zeta_{4})=0$ if and only if $p\equiv 1\pmod{4}$. 2.28 only asserts
${\rm mult}_{\zeta_{4}}(F_{n})=2$ on the condition that $\zeta_{4}$ is a root
of $F_{n}$. In the next section we will classify all $n$ such that $\zeta_{4}$
is a root of $F_{n}$.

###  2.4. Cyclotomic factors of $F_{n}$ with small degree

In this section, we give explicit descriptions of the squarefree integers $n$
such that $\Phi_{d}$ is a factor of $F_{n}$, for each $d\leq 7$. The cases
$d=2,3,5,7$ are already dealt with by 2.22. We will show that the same
statement also holds for $d=4,6$.

######  Remark 2.30.

This statement fails for $d=8$, with the smallest example coming from $n=15$.
By 2.19, we know that $\Phi_{8}$ is a factor of $F_{n}$, but $n$ has no prime
factor congruent to $1\pmod{8}$.

In order to simplify our calculations, we consider the modified function
$\tilde{F}_{n}(x)=\frac{F_{n}(x)}{1-x^{n}}$. The value
$\tilde{F}_{n}(\zeta_{d})$ is well-defined as long as $d\nmid n$, and
furthermore it is zero if and only if $F_{n}(\zeta_{d})=0.$ We also recall the
recursive formula $\tilde{F}_{np}(x)=\tilde{F}_{n}(x)-\tilde{F}_{n}(x^{p})$
for $p\nmid n$ from 2.14, which will be used repeatedly in this section.

We now consider the case $d=4$. By 2.20, if $n$ has a prime factor $p\equiv
1\pmod{4}$ then $F_{n}(\zeta_{4})=0.$ It turns out that the converse is true
as well.

######  Proposition 2.31.

Suppose that $n=2^{s}p_{1}p_{2}\ldots p_{r}$ where $s\in\\{0,1\\}$ and
$p_{1},\ldots,p_{r}$ are distint odd primes of the form $4k+3$. Then
$\tilde{F}_{n}(\zeta_{4})=2^{r-1}\zeta_{4}$. In particular,
$F_{n}(\zeta_{4})\neq 0.$

###### Proof.

Let us write $\zeta=\zeta_{4}$ for simplicity. If $s=1$ and
$m=p_{1}p_{2}\ldots p_{r}$ we get using the recursive formula that

$\tilde{F}_{n}(\zeta)=\tilde{F}_{m}(\zeta)-\tilde{F}_{m}(\zeta^{2})=\tilde{F}_{m}(\zeta)-\tilde{F}_{m}(-1)=\tilde{F}_{m}(\zeta),$

since $F_{m}(-1)=0$ by 2.20. So it is sufficient to prove the statement for
odd $n$. We will do this by induction on the number of prime factors of $n$.

When $n=p$ is a prime of the form $4k+3$, we have
$\tilde{F_{n}}(\zeta)=\frac{1}{1-\zeta^{p}}\frac{\zeta(1-\zeta^{p-1})}{1-\zeta}=\zeta$.
Suppose that the formula is true when $n$ is a product of $r$ primes of the
form $4k+3$. Let us now suppose that $n=p_{1}p_{2}\ldots p_{r+1}$. Let
$m=p_{2}\ldots p_{r+1}$. By the induction hypothesis, we know that
$\tilde{F}_{m}(\zeta)=2^{r-1}\zeta$. By Galois conjugation, we get that
$\tilde{F}_{m}(\zeta^{3})=2^{r-1}\zeta^{3}=-2^{r-1}\zeta$. Now applying the
recursive formula gives us the desired statement.

$\tilde{F}_{n}(\zeta)=\tilde{F}_{m}(\zeta)-\tilde{F}_{m}(\zeta^{p_{1}})=\tilde{F}_{m}(\zeta)-\tilde{F}_{m}(\zeta^{3})=2^{r}\zeta.$

This finishes the proof by induction. ∎

For $d=6$, 2.20 tells us that if $6\nmid n$ and $n$ has a prime factor
$p\equiv 1\pmod{6}$, then $F_{n}(\zeta_{6})=0$. It again turns out that the
converse is true. We first need a lemma.

######  Lemma 2.32.

Suppose that $n=p_{1}p_{2}\ldots p_{r}$ for distinct primes
$p_{1},\ldots,p_{r}$ of the form $3k+2$. Then
$\tilde{F}_{n}(\zeta_{3})=2^{r-1}(1+2\zeta_{3})/3$.

###### Proof.

When $r=1$, direct calculation gives
$\tilde{F}_{p_{1}}(\zeta_{3})=\frac{1}{1-\zeta_{3}^{p_{1}}}\frac{\zeta_{3}(1-\zeta_{3}^{p_{1}-1})}{1-\zeta_{3}}=(1+2\zeta_{3})/3$.
In the general case, we let $m=p_{2}\ldots p_{r}$ and use the recursive
formula

$\tilde{F}_{n}(\zeta_{3})=\tilde{F}_{mp_{1}}(\zeta_{3})=\tilde{F}_{m}(\zeta_{3})-\tilde{F}_{m}(\zeta_{3}^{p_{1}})=\tilde{F}_{m}(\zeta_{3})-\tilde{F}_{m}(\zeta_{3}^{2}).$

Now the induction hypothesis
$\tilde{F}_{m}(\zeta_{3})=2^{r-2}(1+2\zeta_{3})/3$ and Galois conjugacy
implies that
$\tilde{F}_{n}(\zeta_{3})=\frac{2^{r-2}}{3}\left((1+2\zeta_{3})-(1+2\zeta_{3}^{2})\right)=2^{r-1}(1+2\zeta_{3})/3$.
∎

######  Proposition 2.33.

$F_{n}(\zeta_{6})=0$ if and only if $6\nmid n$ and there exists a prime
divisor $p$ of $n$ such that $p\equiv 1\pmod{6}.$

###### Proof.

The “if” part follows from 2.20. So we focus on the “only if” part. By 2.7 we
know that if $6\mid n$ then $F_{n}(\zeta_{6})\neq 0$. So let us assume that
$6\nmid n$. Suppose that $n$ has no prime factor $p\equiv 1\pmod{6}$. We
consider three cases according to whether $\gcd(n,6)=1$, $2$ or $3$.

In the first case, $n=p_{1}p_{2}\ldots p_{r}$ for distinct primes $p_{i}\equiv
5\pmod{6}$, and we can show by induction that
$\tilde{F}_{n}(\zeta_{6})=2^{r-1}(2\zeta_{6}-1)\neq 0$.

In the second case, we write $n=2m=2p_{1}p_{2}\ldots p_{r}$ for distinct
primes $p_{i}\equiv 5\pmod{6}$. The recursive formula then tells us that

$\tilde{F}_{n}(\zeta_{6})=\tilde{F}_{m}(\zeta_{6})-\tilde{F}_{m}(\zeta_{6}^{2})=2^{r-1}(2\zeta_{6}-1)-2^{r-1}\frac{1+2\zeta_{6}^{2}}{3}\neq
0,$

where we have used the formula from the first case, and 2.32.

In the last case, we write $n=3m=3p_{1}p_{2}\ldots p_{r}$ for distinct primes
$p_{i}\equiv 5\pmod{6}$ and get

$\tilde{F}_{n}(\zeta_{6})=\tilde{F}_{m}(\zeta_{6})-\tilde{F}_{m}(\zeta_{6}^{3})=\tilde{F}_{m}(\zeta_{6})-\tilde{F}_{m}(-1)=\tilde{F}_{m}(\zeta_{6})=2^{r-1}(2\zeta_{6}-1)\neq
0.$

We conclude that in all cases $\tilde{F}_{n}(\zeta_{6})\neq 0.$ This completes
the proof. ∎

##  3\. The case $n=pq$

In this section, we study more closely the case where $n$ is a product of two
odd primes $p>q$. The following proposition is a direct consequence of 2.19.
If we assume that 2.11 holds, this proposition in fact captures _all_
cyclotomic factors of $F_{pq}$.

######  Proposition 3.1.

The $d$-th cyclotomic polynomial $\Phi_{d}$ divides $F_{n}$ if $d>1$ and one
of the following holds

  1. (a)

$d$ divides $q-1$;

  2. (b)

$d$ divides $p-1$ and $d\neq q$;

  3. (c)

$d$ divides $\gcd(qp+1,p+q)$. ∎

######  Theorem 3.2.

Assume 2.11 is true. Then 3.1 is a complete characterization of all cyclotomic
factors of $F_{n}$, when $n=pq$ is a product of two odd primes $p>q$.

###### Proof.

We have

(3.1)
$\displaystyle\begin{split}(x^{p}-1)(x^{q}-1)F_{n}(x)=(x^{p}-1)\sum_{1\leq
i\leq q-1}\left(x^{qp+i}+x^{ip}-x^{i}-x^{ip+q}\right)\\\
=x^{qp}-x^{p}-x^{qp+q}+x^{p+q}+\sum_{1\leq i\leq
q-1}\left(x^{(q+1)p+i}-x^{qp+i}-x^{p+i}+x^{i}\right).\end{split}$

To evaluate a polynomial at a primitive $d$-th root of unity $\zeta_{d}$, it
is enough to consider its reduction modulo $x^{d}-1$. In particular, we may
reduce the monomial exponents modulo $d$.

By 2.7 we know that $d\nmid n$. Suppose $d=d_{1}e_{1}$ with $d_{1}=\gcd(d,n)$
and $e_{1}>1$. We have the following cases depending on whether $d_{1}$ is
$p,q$ or $1$.
Case 1: Suppose $d_{1}=p$. The equidistribution from 2.11 implies that
$\\#S=\varphi(d_{1})e_{1}=\varphi(p)e_{1}$ divides
$\varphi(n)=\varphi(p)\varphi(q)$. Hence $e_{1}|\varphi(q)$ and
$d|p\varphi(q)$. Reducing Eq. 3.1 modulo $x^{p\varphi(q)}-1$ without loss of
generality, we get

$\displaystyle\sum_{1\leq i\leq
q-1}\left(x^{2p+i}-2x^{p+i}+x^{i}\right)=(x^{p}-1)^{2}\sum_{1\leq i\leq
q-1}x^{i}=(x^{p}-1)^{2}\frac{x(x^{q-1}-1)}{x-1},$

whose value at $\zeta_{d}$ is clearly non-zero.
Case 2: Suppose $d_{1}=q$. 2.11 implies that $\\#S=\varphi(d_{1})e_{1}$
divides $\varphi(n)$. Hence $e_{1}|\varphi(p)$ and $d|q\varphi(p)$. Reducing
Eq. 3.1 modulo $x^{q\varphi(p)}-1$, we get

$\displaystyle\sum_{1\leq i\leq
q}\left(x^{p+q-1+i}-x^{q+i}-x^{p-1+i}+x^{i}\right)$
$\displaystyle=(x^{p+q-1}-x^{q}-x^{p-1}+1)\frac{x(x^{q}-1)}{x-1}$
$\displaystyle=(x^{p-1}-1)\frac{x(x^{q}-1)^{2}}{x-1},$

whose value at $\zeta_{d}$ is zero if and only $d|p-1$ and $d\neq q$.
Case 3: Suppose $d_{1}=1$. 2.11 implies that $\\#S=e_{1}=d$ divides
$\varphi(n)$. Reducing Eq. 3.1 modulo $x^{\varphi(n)}-1$, we get

$\displaystyle x^{p+q-1}-x^{p}-x^{p+2q-1}+x^{p+q}+\sum_{1\leq i\leq
q-1}\left(x^{2p+q+i-1}-x^{p+q+i-1}-x^{p+i}+x^{i}\right)$
$\displaystyle=\sum_{i\in S_{1}}x^{i}-\sum_{i\in S_{2}}x^{i},$

where $S_{1}=\\{1\leq i\leq q-1\\}\cup\\{p+q-1,p+q\\}\cup\\{2p+q\leq i\leq
2p+2q-2\\}$ and $S_{2}=\\{p\leq i\leq p+2q-1\\}$. Note that $S_{2}$ is a
sequence of $2q$ consecutive integers. Therefore, this polynomial evaluated at
$\zeta_{d}$ is zero if and only if $S_{1}$ modulo $d$ is equal to the same set
of consecutive residues modulo $d$. This happens if and only if $d$ divides
$p-1$, $q-1$, or $p+q$. If $d$ divides $p+q$, then $d$ also divides $pq+1$
because $pq+1=\varphi(n)+(p+q)$. ∎

Let $S_{n}$ be the set of integers $d$ described in 3.1, namely

(3.2) $S_{n}=\\{d>1,d\not=q,d\mid p-1\\}\cup\\{d>1,d\mid
q-1\\}\cup\\{d>1,d\mid\gcd(pq+1,p+q)\\}.$

######  Definition 3.3.

Suppose $n=pq$ for odd primes $p>q$. Let $S_{n}$ be as above. We define the
Fekete polynomial $f_{n}(x)\in\operatorname{\mathbb{Z}}[x]$ to be the
polynomial such that

$\displaystyle F_{n}(x)$ $\displaystyle=f_{n}(x)\cdot x\cdot\prod_{d\in
S_{n}}\Phi_{d}(x)$

######  Proposition 3.4.

Suppose $n=pq$ for odd primes $p>q$. Let $f_{n}$ be the Fekete polynomial as
in Definition 3.3. Let $D_{1}=\gcd(p-1,q-1)$, $D_{2}=\gcd(pq+1,p+q)$,
$D_{3}=\gcd(pq+1,p+q,p-1)=\gcd(p-1,q+1)$,
$D_{4}=\gcd(pq+1,p+q,q-1)=\gcd(p+1,q-1)$. Then $f_{n}$ is a reciprocal
polynomial of even degree. More precisely,

$\displaystyle\deg(f_{n})=\begin{cases}pq-
p-q-1+D_{1}+D_{3}+D_{4}-D_{2}\quad&\text{if }p\not\equiv 1\pmod{q}\\\
pq-p-2+D_{1}+D_{3}+D_{4}-D_{2}\quad&\text{if }p\equiv 1\pmod{q}.\end{cases}$

Furthermore, we have

$\displaystyle
f_{n}(1)=\begin{cases}\dfrac{D_{1}D_{3}D_{4}}{2D_{2}}\quad&\text{if
}p\not\equiv 1\pmod{q}\\\ \dfrac{qD_{1}D_{3}D_{4}}{2D_{2}}\quad&\text{if
}p\equiv 1\pmod{q},\\\ \end{cases}$ $\displaystyle
f_{n}(-1)=\frac{-D_{1}D_{3}D_{4}}{2D_{2}}.$

###### Proof.

Let

$\displaystyle f(x)=\prod_{\begin{subarray}{c}d\mid q-1\\\ d\neq
1\end{subarray}}\Phi_{d}(x),\quad g(x)=\prod_{\begin{subarray}{c}d\mid p-1\\\
d\neq q\\\ d\nmid q-1\end{subarray}}\Phi_{d}(x),\quad
h(x)=\prod_{\begin{subarray}{c}d\mid\gcd(pq+1,p+q)\\\ d\nmid q-1,d\nmid
p-1\end{subarray}}\Phi_{d}(x).$

Then we have $F_{n}(x)=xf(x)g(x)h(x)f_{n}(x)$. Using the inclusion-exclusion
principle, we get the following formulas for $f,g,h$ in this decomposition:

$\displaystyle f(x)=\frac{1-x^{q-1}}{1-x}=\frac{F_{q}(x)}{x},\quad
g(x)=\begin{cases}\frac{1-x^{p-1}}{1-x^{D_{1}}}\quad&\text{if }p\not\equiv
1\pmod{q}\\\ \frac{(1-x^{p-1})(1-x)}{(1-x^{D_{1}})(1-x^{q})}\quad&\text{if
}p\equiv 1\pmod{q},\\\ \end{cases}$ $\displaystyle
h(x)=\frac{(1-x^{D_{2}})(1-x^{2})}{(1-x^{D_{3}})(1-x^{D_{4}})}.$

Since each of the polynomials $F_{n}(x)/x$, $f,g,h$ are reciprocal, we deduce
that $f_{n}$ is also a reciprocal polynomial. The formula for $\deg(f_{n})$
can also be deduced easily from the explicit descriptions of $f,g,h$ given
above.

It is also clear from this description that

$\displaystyle f(1)=q-1,\quad g(1)=\begin{cases}\frac{p-1}{D_{1}}\quad\text{if
}p\not\equiv 1\pmod{q}\\\ \frac{p-1}{qD_{1}}\quad\text{if }p\equiv
1\pmod{q},\end{cases}$ $\displaystyle h(1)=\frac{2D_{2}}{D_{3}D_{4}}.$

Since $F_{n}(1)=(p-1)(q-1)$, we infer the value of $f_{n}(1)$.

Note that $D_{i}$ is even for $1\leq i\leq 4$, and hence $g(-1),h(-1)\neq 0$
whereas $F_{n}(-1)=f(-1)=0$. Hence
$F^{\prime}_{n}(-1)=(-1)f^{\prime}(-1)g(-1)h(-1)f_{n}(-1)$. Thus, we calculate
$F_{n}^{\prime}(-1)$ and $f^{\prime}(-1)$ using 2.18, and $g(-1)$ and $h(-1)$
using calculus, to infer the value of $f_{n}(-1)$:

$\displaystyle F_{n}^{\prime}(-1)=\frac{(p-1)(q-1)}{2},\quad$ $\displaystyle
f^{\prime}(-1)=-F_{q}^{\prime}(-1)=\frac{q-1}{2},$ $\displaystyle
g(-1)=\frac{p-1}{D_{1}},\quad$ $\displaystyle
h(-1)=\frac{2D_{2}}{D_{3}D_{4}}.$

∎

######  Corollary 3.5.

$f_{pq}(x)$ is not a product of cyclotomic polynomials. In particular,
$f_{pq}(x)$ is not a cyclotomic polynomial.

###### Proof.

Suppose on the contrary that $f_{pq}(x)=\prod_{i=1}^{r}\Phi_{m_{i}}(x)$, where
$1\leq m_{1}\leq m_{2}\dots\leq m_{r}$ are positive integers. Since
$f_{pq}(1)f_{pq}(-1)\neq 0$, we can assume that $m_{1}>2$. By [6, Lemma 7], we
have $\Phi_{m_{i}}(-1)>0$ for all $1\leq i\leq r.$ Consequently
$f_{pq}(-1)>0.$ This contradicts the above determination of $f_{pq}(-1).$ ∎

######  Definition 3.6.

We define $g_{n}$ to be the trace polynomial of $f_{n}$, i.e., it is the
unique polynomial such that
$g_{n}\left(x+\frac{1}{x}\right)=x^{-\deg(f_{n})/2}f_{n}(x)$.

######  Proposition 3.7.

Suppose $n=pq$ for odd primes $p>q$. Let $f_{n}$ be the Fekete polynomial as
in Definition 3.3, and $g_{n}$ its trace polynomial as in Definition 3.6.
Assume $\operatorname{{\rm disc}}(g_{n})$ (or equivalently $\operatorname{{\rm
disc}}(f_{n})$) is nonzero).
If $p\not\equiv 1\pmod{q}$, then up to squares, we have

$\displaystyle\operatorname{{\rm disc}}(f_{n})=\begin{cases}-1\quad&\text{if
}p,q\equiv 1\pmod{4}\\\ 1\quad&\text{otherwise}.\end{cases}$

If $p\equiv 1\pmod{q}$, then up to squares, we have

$\displaystyle\operatorname{{\rm disc}}(f_{n})=\begin{cases}q\quad&\text{if
}p\equiv 3\pmod{4}~{}\text{ and }q\equiv 1\pmod{4}\\\
-q\quad&\text{otherwise}.\end{cases}$

###### Proof.

Since $f_{n}$ is a reciprocal polynomial,

$\displaystyle\operatorname{{\rm
disc}}(f_{n})=(-1)^{\deg(f_{n})/2}f_{n}(1)f_{n}(-1)\operatorname{{\rm
disc}}(g_{n})^{2}.$

Therefore 3.4 tells us that up to squares, we have

$\displaystyle\operatorname{{\rm
disc}}(f_{n})=\begin{cases}(-1)^{\deg(f_{n})/2}(-1)\quad&\text{if }p\not\equiv
1\pmod{q}\\\ (-1)^{\deg(f_{n})/2}(-q)\quad&\text{if }p\equiv
1\pmod{q}.\end{cases}$

Calculating $\deg(f_{n})$ modulo $4$, again using 3.4, we obtain the stated
result. ∎

We now investigate roots of the Fekete polynomial $F_{pq}$ in
$\overline{\operatorname{\mathbb{F}}}_{p}$. The objective of this study is to
prove that $f_{n}$ is separable over $\operatorname{\mathbb{Z}}$. We will see
later that, in some special cases, this can be done by proving separability
over $\operatorname{\mathbb{F}}_{p}$. We first recall the following
definition.

######  Definition 3.8.

Let $f,g$ be two polynomials. The Wronskian $W(f,g)$ of $f$ and $g$ is defined
by the formula $W(f,g)=f^{\prime}g-g^{\prime}f$.

Let $q$ be a prime. We now introduce the polynomial
$u_{q}(x)=W(s_{q}(x),F_{q}(x))\in\operatorname{\mathbb{Z}}[x]$ where
$s_{q}(x)=x^{q}-1$ and $F_{q}(x)=\sum\limits_{i=1}^{q-1}x^{i}$. Then $u_{q}$
has the following explicit formula

(3.3) $u_{q}(x)=\sum_{1\leq i\leq q-1}(q-i)x^{q-1+i}+\sum_{1\leq i\leq
q-1}ix^{i-1}=\Phi_{q}(x)^{2}-qx^{q-1}.$

######  Lemma 3.9.

Over $\operatorname{\mathbb{F}}_{q}$, we have $u_{q}(x)=(x-1)^{2q-2}\pmod{q}$.

###### Proof.

We have

$F_{q}(x)=x\frac{x^{q-1}-1}{x-1}=\frac{x^{q}-x}{x-1},\quad
F^{\prime}_{q}(x)=\frac{(qx^{q-1}-1)(x-1)-(x^{q}-x)}{(x-1)^{2}}.$

Over $\operatorname{\mathbb{F}}_{q}$ this becomes

$F^{\prime}_{q}(x)=\frac{1-x^{q}}{(x-1)^{2}}=-(x-1)^{q-2}.$

We also have that $s_{q}(x)=(x-1)^{q}$ and $s^{\prime}_{q}(x)=0$ over
$\operatorname{\mathbb{F}}_{q}$. Hence

$u_{q}(x)=s^{\prime}_{q}(x)F_{q}(x)-F^{\prime}_{q}(x)s_{q}(x)=(x-1)^{2q-2}\pmod{q}.\qed$

######  Corollary 3.10.

The polynomial $u_{q}$ is irreducible.

###### Proof.

Let $v_{q}(x)=u_{q}(x+1).$ Then $v_{q}(x)\equiv x^{2q-2}\pmod{q}$ and
$v_{q}(0)=u_{q}(1)=q(q-1)$. By Eisenstein’s criterion for irreducibility, we
conclude that $v_{q}$ (and hence $u_{q}$) is irreducible. ∎

######  Proposition 3.11.

Suppose $n=pq$ for odd primes $p>q$. Let
$x_{0}\in\overline{\operatorname{\mathbb{F}}}_{p}$ be a root of $F_{n}$. Then

  1. (a)

${\rm mult}_{x_{0}}(F_{n})-1={\rm mult}_{x_{0}}(u_{q})$.

  2. (b)

If $\operatorname{{\rm disc}}(u_{q})\neq 0\mod p$, then ${\rm
mult}_{x_{0}}(F_{n})\leq 2$.

  3. (c)

Suppose $x_{0}\in\operatorname{\mathbb{F}}_{p}$. Then ${\rm
mult}_{x_{0}}(F_{n})-1={\rm mult}_{x_{0}}(f_{n})$.

###### Proof.

Using the recursive formula from 2.14, we have

$\displaystyle F_{n}(x)=\frac{x^{qp}-1}{x^{q}-1}F_{q}(x)-F_{q}(x^{p}),$

and hence

$\displaystyle F_{n}(x)$
$\displaystyle\equiv(x^{q}-1)^{p-1}F_{q}(x)-F_{q}(x)^{p}\pmod{p},$
$\displaystyle F^{\prime}_{n}(x)$ $\displaystyle\equiv
F^{\prime}_{q}(x)(x^{q}-1)^{p-1}-qx^{q-1}F_{q}(x)(x^{q}-1)^{p-2}\pmod{p}$
$\displaystyle\equiv-(x^{q}-1)^{p-2}u_{q}(x)\pmod{p}.$

  1. (a)

2.6 says that $F_{n}(\zeta_{q})=-\varphi(p)\equiv 1\pmod{p}$, and
$F_{n}(1)=\varphi(n)=(q-1)(p-1)\equiv 1-q\not\equiv 0\pmod{p}$. Therefore, if
$x_{0}\in\overline{\operatorname{\mathbb{F}}}_{p}$ is a zero of $F_{n}$, then
it is not a zero of $x^{q}-1$. Hence the relation of $F^{\prime}_{n}$ and
$u_{q}$ obtained above shows that ${\rm mult}_{x_{0}}(u_{q})={\rm
mult}_{x_{0}}(F_{n})-1$.

  2. (b)

This is a straight-forward consequence of Part (a). If $\operatorname{{\rm
disc}}(u_{q})\neq 0\mod p$, then the reduction of $u_{q}$ modulo $p$ is
separable. Hence ${\rm mult}_{x_{0}}(u_{q})\leq 1$ and ${\rm
mult}_{x_{0}}(F_{n})\leq 2$.

  3. (c)

Since $x_{0}\in\operatorname{\mathbb{F}}_{p}$, it is a $(p-1)$-th root of
unity. Since $x_{0}$ is a zero of $F_{n}$, we know as in Part (a) that it is
not a $q$-th root of unity. So there exists some $d$ dividing $p-1$, $d\neq
q$, such that $x_{0}$ is a root of the $d$-th cyclotomic polynomial
$\Phi_{d}$. Therefore by 3.1 we get that ${\rm mult}_{x_{0}}(F_{n})-1={\rm
mult}_{x_{0}}(f_{n})$.

∎

######  Remark 3.12.

We note that irreducibility of the polynomial
$u_{q}\in\operatorname{\mathbb{Z}}[x]$ implies in particular that
$\operatorname{{\rm disc}}(u_{q})\neq 0$. Therefore for primes $p$
sufficiently large compared to $q$, we have $\operatorname{{\rm
disc}}(u_{q})\neq 0\pmod{p}$ and hence ${\rm mult}_{x_{0}}(F_{pq})\leq 2$.

To further study separability of $F_{n}$ over $\operatorname{\mathbb{F}}_{p}$,
we introduce the following auxiliary polynomials. Let

$a(x,y)=s_{q}(x)-yt_{q}(x)~{}\text{ where
}s_{q}(x)=x^{q}-1,~{}t_{q}(x)=F_{q}(x)=\sum_{i=1}^{q-1}x^{i},$

and let $R_{q}(y)$ be the resultant of $u_{q}(x)$ and $a(x,y)$ with respect to
the variable $x$. There is a direct link between separability of $F_{n}$ and
the arithmetic of $R_{q}$.

######  Proposition 3.13.

Suppose that $F_{n}$ has a repeated root
$x_{0}\in\overline{\operatorname{\mathbb{F}}}_{p}.$ Then $R_{q}$ has a root
$\mu\in\operatorname{\mathbb{F}}_{p}$.

###### Proof.

By 3.11 Part (a), ${\rm mult}_{x_{0}}(u_{q})={\rm mult}_{x_{0}}(F_{n})-1\geq
1$, i.e., $x_{0}$ is a root of $u_{q}$. We claim that $x_{0}$ is not a root of
$F_{q}$. Suppose on the contrary that it is a root of $F_{q}$. Then firstly it
is a simple root because $(x-1)F_{q}(x)=x(x^{q-1}-1)$ is separable over
$\operatorname{\mathbb{F}}_{p}$. Since $x_{0}$ is a repeated root of
$F_{n}(x)=(x^{q}-1)^{p-1}F_{q}(x)-F_{q}(x)^{p}$, and only a simple root of
$F_{q}(x)$, we deduce that $x_{0}$ must be a root of $x^{q}-1$. On the other
hand, since $x_{0}\neq 0$ and $x_{0}(x_{0}^{q-1}-1)=(x_{0}-1)F_{q}(x_{0})=0$,
we get that $x_{0}^{q-1}-1$. This forces
$x_{0}=x_{0}^{q}-1-x_{0}(x_{0}^{q-1}-1)+1=1$. But this is a contradiction
because $F_{n}(1)=\varphi(n)=(p-1)(q-1)\neq 0\pmod{p}$.

Now $0=F_{n}(x_{0})=(x_{0}^{q}-1)^{p-1}F_{q}(x_{0})-F_{q}(x_{0})^{p}$ implies
that $(x_{0}^{q}-1)^{p-1}=F_{q}(x_{0})^{p-1}$. Hence $x_{0}^{q}-1=\mu
F_{q}(x_{0})$ for some $\mu\in\operatorname{\mathbb{F}}_{p}^{\times}$. Thus
$x_{0}$ is a root of the polynomial $a(x,\mu)=x^{q}-1-\mu
F_{q}(x)\in\operatorname{\mathbb{F}}_{p}[x]$. In particular, $a(x,\mu)$ and
$u_{q}(x)$ have a common root. Therefore

${\rm resultant}(u_{q}(x),a(x,\mu))=R_{q}(\mu)=0.\qed$

###  3.1. Further properties of the resultant $R_{q}(y)$

We record in this section a few interesting properties of the resultant
polynomial $R_{q}(y)$. We need the following lemma.

######  Lemma 3.14.

Let $q$ be an odd prime, and $s_{q}(x)=x^{q}-1$ and
$t_{q}(x)=\sum\limits_{i=1}^{q-1}x^{i}$. Then

  1. (a)

$\operatorname{{\rm Res}}(s_{q}(x),s_{q}^{\prime}(x))=q^{q}.$

  2. (b)

$\operatorname{{\rm Res}}(t_{q}(x),t_{q}^{\prime}(x))=-(q-1)^{q-3}.$

  3. (c)

$\operatorname{{\rm Res}}(t_{q}(x),s_{q}(x))=q-1.$

###### Proof.

  1. (a)

Let $\zeta_{k}$, $k=1,\ldots,q$, be all the $q$-th roots of unity. Then

$\operatorname{{\rm
Res}}(s_{q}(x),s^{\prime}_{q}(x))=\prod_{k=1}^{q}s^{\prime}_{q}(\zeta_{k})=q^{q}\left(\prod_{k=1}^{q}\zeta_{k}\right)^{q-1}=q^{q}.$

  2. (b)

Since $(x-1)t_{q}(x)=x^{q}-x$, we have

${\rm disc}(x^{q}-x)={\rm disc}(x-1){\rm disc}(t_{q}(x))\operatorname{{\rm
Res}}(x-1,t_{q}(x))^{2}.$

Let $\zeta_{k}$, $k=1,\ldots,q-1$, be all the $(q-1)$-th roots of unity. Then

$\displaystyle{\rm disc}(x^{q}-x)$
$\displaystyle=(-1)^{q(q-1)/2}\operatorname{{\rm Res}}(x^{q}-x,qx^{q-1}-1)$
$\displaystyle=(-1)^{q(q-1)/2}\cdot(-1)\cdot\prod_{k=1}^{q-1}(q\zeta_{k}^{q-1}-1)=-(-1)^{q(q-1)/2}(q-1)^{q-1}.$

Also, we have $\operatorname{{\rm
Res}}(x-1,t_{q}(x))^{2}=t_{q}(1)^{2}=(q-1)^{2}$. Hence

$\operatorname{{\rm disc}}(t_{q}(x))=-(-1)^{q(q-1)/2}(q-1)^{q-3},$

and thus

$\operatorname{{\rm Res}}(t_{q}(x),t^{\prime}_{q}(x))=(-1)^{(q-1)(q-2)/2}{\rm
disc}(t_{q}(x))=-(q-1)^{q-3}.$

  3. (c)

Let $\zeta_{k}$, $k=1,\ldots,q$, be all the $q$-th roots of unity, where
$\zeta_{q}=1$. Then

$\operatorname{{\rm
Res}}(s_{q}(x),t_{q}(x))=\prod_{k=1}^{n}t_{q}(\zeta_{k})=(q-1)\prod_{k=1}^{q-1}\dfrac{\zeta_{k}^{q}-\zeta_{k}}{\zeta_{k}-1}=(q-1)\prod_{k=1}^{q-1}\dfrac{1-\zeta_{k}}{\zeta_{k}-1}=q-1.\qed$

######  Proposition 3.15.

Over $\operatorname{\mathbb{F}}_{q}$, the polynomial $R_{q}(y)$ factors as
$R_{q}(y)=y^{2q-2}$.

###### Proof.

Using the property that $\operatorname{{\rm Res}}(AB,C)=\operatorname{{\rm
Res}}(A,C)\operatorname{{\rm Res}}(B,C)$ and using 3.9 which says that
$u_{q}(x)=(x-1)^{2q-2}$ over $\operatorname{\mathbb{F}}_{q}$, we have

$\displaystyle R_{q}(y)=\operatorname{{\rm Res}}(a(x,y),u_{q}(x))$
$\displaystyle=\operatorname{{\rm
Res}}(a(x,y),(x-1)^{2q-2})=\left(\operatorname{{\rm
Res}}(a(x,y),x-1)\right)^{2q-2}$
$\displaystyle=a(1,y)^{2q-2}=(q-1)^{2q-2}y^{2q-2}=y^{2q-2}\pmod{q}.\qed$

######  Proposition 3.16.

The polynomial $R_{q}(y)$ is an even polynomial of degree $2q-2$, i.e., it is
a polynomial in $y^{2}$. It has leading coefficient $-(q-1)^{q-2}$ and
constant coefficient $(q-1)q^{q}$.

###### Proof.

We first note that

$\displaystyle a\left(1/x,y\right)$
$\displaystyle=s_{q}\left(1/x\right)-yt_{q}\left(1/x\right)=-x^{-q}\left(s_{q}(x)+yt_{q}(x)\right).$

and hence $x^{q}a\left(1/x,y\right)a(x,y)=(y^{2}t_{q}(x)^{2}-s_{q}(x)^{2})$ is
a polynomial in the variables $x,y^{2}$. Let $z_{1},z_{2},\ldots,z_{2q-2}$ be
the roots of $u_{q}$. Since $u_{q}$ is a reciprocal polynomial, we can assume
further that $z_{i}z_{2q-1-i}=1$. Thus we have

$\displaystyle R_{q}(y)=\operatorname{{\rm
Res}}(a(x,y),u_{q}(x))=\prod_{i=1}^{2q-2}a(z_{i},y)=\prod_{i=1}^{q-1}\left(a(z_{i},y)a\left(1/z_{i},y\right)\right)$

which shows that $R_{q}$ is an even polynomial. The formula

$R_{q}(y)=\prod_{i=1}^{2q-2}a(z_{i},y)=\prod_{i=1}^{2q-2}(s_{q}(z_{i})-yt_{q}(z_{i}))$

also shows that the leading coefficient of $R_{q}$ is
$\prod\limits_{i=1}^{2q-2}t_{q}(z_{i})=\operatorname{{\rm
Res}}(t_{q}(x),u_{q}(x))$, and the constant coefficient of $R_{q}$ is
$\prod\limits_{i=1}^{2q-2}s_{q}(z_{i})=\operatorname{{\rm
Res}}(s_{q}(x),u_{q}(x)).$ We can compute them using 3.14. We compute the
leading coefficient as follows

$\displaystyle\operatorname{{\rm Res}}(t_{q}(x),u_{q}(x))$
$\displaystyle=\operatorname{{\rm
Res}}(t_{q}(x),s_{q}^{\prime}(x)t_{q}(x)-s_{q}(x)t_{q}^{\prime}(x))=\operatorname{{\rm
Res}}(t_{q}(x),-s_{q}(x)t_{q}^{\prime}(x))$ $\displaystyle=\operatorname{{\rm
Res}}(t_{q}(x),s_{q}(x))\operatorname{{\rm
Res}}(t_{q}(x),t_{q}^{\prime}(x))=-(q-1)^{q-2}.$

Similarly, the constant coefficient of $R_{q}$ is $(q-1)q^{q}.$ ∎

##  4\. The case $n=3p$

In this section, we focus on the special case $n=3p$ for some prime $p>3$. We
note that the set $S_{3p}$ described in Eq. 3.2 can be rewritten explicity.

$S_{3p}=\begin{cases}\\{d\in\operatorname{\mathbb{N}}\mid d>1,d\not=3,d\mid
p-1\\}\cup\\{8\\}&\text{ if }p\equiv 1\mod{12}\\\
\\{d\in\operatorname{\mathbb{N}}\mid d>1,d\mid p-1\\}\cup\\{8\\}&\text{ if
}p\equiv 5\mod{12}\\\ \\{d\in\operatorname{\mathbb{N}}\mid d>1,d\not=3,d\mid
p-1\\}&\text{ if }p\equiv 7\mod{12}\\\ \\{d\in\operatorname{\mathbb{N}}\mid
d>1,d\mid p-1\\}&\text{ if }p\equiv 11\mod{12}.\end{cases}$

Accordingly, we have the explicit description

(4.1) $\displaystyle\begin{split}F_{3p}(x)&=f_{3p}(x)\cdot x\cdot\prod_{d\in
S_{3p}}\Phi_{d}(x)\\\
&=\begin{cases}f_{3p}(x)x\dfrac{x^{p-1}-1}{x^{3}-1}&\text{ if }p\equiv
1,7,19\pmod{24}\\\ f_{3p}(x)x\dfrac{x^{p-1}-1}{x^{3}-1}\Phi_{8}(x)&\text{ if
}p\equiv 13\pmod{24}\\\ f_{3p}(x)x\dfrac{x^{p-1}-1}{x-1}\Phi_{8}(x)&\text{ if
}p\equiv 5\pmod{24}\\\ f_{3p}(x)x\dfrac{x^{p-1}-1}{x-1}&\text{ if }p\equiv
11,17,23\pmod{24}.\\\ \end{cases}\end{split}$

######  Proposition 4.1.

Let $p>3$ be a prime. Then the polynomial $f_{3p}$ has the explicit formula

$f_{3p}(x)=\begin{cases}x^{2p+2}+x^{2p+1}+x^{p+2}+x^{p}+x+1&\text{ if }p\equiv
1,7,19\pmod{24}\\\ \dfrac{x^{2p+2}+x^{2p+1}+x^{p+2}+x^{p}+x+1}{x^{4}+1}&\text{
if }p\equiv 13\pmod{24}\\\
\dfrac{x^{2p+2}+x^{2p+1}+x^{p+2}+x^{p}+x+1}{(x^{2}+x+1)(x^{4}+1)}&\text{ if
}p\equiv 5\pmod{24}\\\
\dfrac{x^{2p+2}+x^{2p+1}+x^{p+2}+x^{p}+x+1}{x^{2}+x+1}&\text{ if }p\equiv
11,17,23\pmod{24}.\end{cases}$

and

$\deg f_{3p}=\begin{cases}2p+2&\text{ if }p\equiv 1,7,19\pmod{24}\\\
2p-2&\text{ if }p\equiv 13\pmod{24}\\\ 2p-4&\text{ if }p\equiv 5\pmod{24}\\\
2p&\text{ if }p\equiv 11,17,23\pmod{24}.\end{cases}$

###### Proof.

The statements follow from noting that

$\displaystyle(x^{3}-1)F_{3p}$
$\displaystyle=x^{3p+2}+x^{3p+1}+x^{2p}+x^{p}-(x^{2p+3}+x^{p+3}+x^{2}+x)$
$\displaystyle=(x^{p}-x)(x^{2p+2}+x^{2p+1}+x^{p+2}+x^{p}+x+1).$

∎

It is a classical theorem that for any distinct odd primes $p,q$, the
coefficients of the cyclotomic polynomial $\Phi_{pq}$ are in $\\{0,-1,1\\}$
(see [5]). The smallest integer $n$ such that $\Phi_{n}$ has a coefficient not
contained in $\\{0,-1,1\\}$ is $n=105$. Along these lines, we observe that the
coefficients of $f_{3p}$ are quite small. In fact, for $p<1200$, we verify
using SageMath that the coefficients of $f_{3p}$ are in the set
$\\{-2,-1,0,1,2\\}$. In fact this is true for all $p$ as the next theorem
shows.

######  Theorem 4.2.

Let $p>3$ be a prime. The coefficients of $f_{3p}$ are in the set
$\\{-2,-1,0,1,2\\}$.

###### Proof.

Suppose that $p\equiv 1\pmod{3}$. If $p\equiv 1,7,19\pmod{24}$, the statement
is clear from 4.1. If $p\equiv 13\pmod{24}$, say $p=13+24a$ for some
$a\in\operatorname{\mathbb{N}}$, then

$\displaystyle x^{2p+2}+1$
$\displaystyle=(x^{4})^{7+12a}+1=(x^{4}+1)\sum_{k=0}^{6+12a}(-1)^{k}x^{4k}$
$\displaystyle x^{2p+1}+x^{p+2}$
$\displaystyle=x^{p+2}[(x^{4})^{3+6a}+1]=(x^{4}+1)\sum_{k=0}^{2+6a}(-1)^{k}x^{4k+15+24a}$
$\displaystyle x^{p}+x$
$\displaystyle=x[(x^{4})^{3+6a}+1]=(x^{4}+1)\sum_{k=0}^{2+6a}(-1)^{k}x^{4k+1}.$

Hence

$f_{3p}(x)=\sum_{k=0}^{6+12a}(-1)^{k}x^{4k}+\sum_{k=0}^{2+6a}(-1)^{k}x^{4k+15+24a}+\sum_{k=0}^{2+6a}(-1)^{k}x^{4k+1}$

which shows that all the coefficients of $f_{3p}$ are in $\\{-1,0,1\\}$.

Now suppose that $p\equiv 2\pmod{3}$. Write $p=2+3a$ for some
$a\in\operatorname{\mathbb{N}}$. Let

$g(x)=\sum_{k=a+1}^{2a+1}x^{3k+1}-\sum_{k=a+1}^{2a}x^{3k+2}+\sum_{k=0}^{a}x^{3k}-\sum_{k=0}^{a-1}x^{3k+2}.$

It is straightforward to check that

$\displaystyle(x^{2}+x+1)g(x)$
$\displaystyle=x^{6a+6}+x^{6a+5}+x^{3a+4}+x^{3a+2}+x+1$
$\displaystyle=x^{2p+2}+x^{2p+1}+x^{p+2}+x^{p}+x+1.$

Now if $p\equiv 11,17,23\pmod{24}$, then 4.1 says that $f_{3p}(x)=g(x)$, and
so all the coefficients of $f_{3p}$ are in $\\{-1,0,1\\}$. The last remaining
case is $p\equiv 5\pmod{24}$. If we write
$g(x)=\sum\limits_{k=0}^{2p}b_{k}x^{k}$, then the coefficients $b_{k}$ are
given by

$b_{k}=\begin{cases}1&\text{ if $k\equiv 1\pmod{3}$ and $p+2\leq k\leq 2p$}\\\
-1&\text{ if $k\equiv 2\pmod{3}$, ~{}$k\leq 2p$ and $k\not=p$}\\\ 1&\text{ if
$k\equiv 0\pmod{3}$ and $0\leq k\leq p-2$}\\\ 0&\text{ otherwise}\end{cases}$

In particular we have $b_{k}=b_{k^{\prime}}$ whenever $k\equiv
k^{\prime}\pmod{3}$ and $0\leq k,k^{\prime}\leq p-1$. 4.1 says that in this
case we have $f_{3p}(x)(x^{4}+1)=g(x)$. If we write
$f_{3p}(x)=\sum\limits_{k=0}^{2p-4}a_{k}x^{k}$, then we get that the
coefficients of $g$ and $f_{3p}$ are related by

$\displaystyle b_{k}=\begin{cases}a_{k}\quad&\text{ if }\quad 0\leq k\leq 3\\\
a_{k}+a_{k-4}\quad&\text{ if }\quad 4\leq k\leq 2p-4\\\ a_{k-4}\quad&\text{ if
}\quad 2p-3\leq k\leq 2p.\end{cases}$

For $24\leq k\leq p-1$, using the recursive formula $b_{k}=a_{k}+a_{k-4}$
repeatedly, we have

$\displaystyle a_{k}-a_{k-24}$
$\displaystyle=b_{k}-b_{k-4}+b_{k-8}-b_{k-12}+b_{k-16}-b_{k-20}$
$\displaystyle=(b_{k}-b_{k-12})-(b_{k-4}-b_{k-16})+(b_{k-8}-b_{k-20})=0.$

showing that the sequence $a_{0},a_{1},\ldots,a_{p-1}$ is periodic with a
period $24$. It is straightforward to check that the sequence
$a_{0},a_{1},\ldots,a_{23}$ is

$1,0,-1,1,-1,-1,2,-1,0,2,-2,0,1,-2,1,1,-1,1,0,-1,0,0,0,0.$

Hence $a_{k}\in\\{-2,-1,0,1,2\\}$ for $0\leq k\leq p-1$. Since $f_{3p}$ is
reciprocal, we know that $a_{k}=a_{2p-4-k}$ and so $a_{k}\in\\{-2,-1,0,1,2\\}$
for all $0\leq k\leq 2p-4$. ∎

######  Corollary 4.3.

Let $a_{\frac{\deg f_{3p}}{2}}$ be the middle coefficient of $f_{3p}$. Then

$a_{\frac{\deg f_{3p}}{2}}=\begin{cases}0&\text{ if }p\equiv
1,7,11,17,19,23\pmod{24}\\\ 1&\text{ if }p\equiv 5\pmod{24}\\\ -1&\text{ if
}p\equiv 13\pmod{24}.\end{cases}$

∎

Next, we study more properties of $f_{3p}$ in characteristic $p$. We start
with the following theorem which is an improved version of 3.11 in the special
case $n=3p$.

######  Theorem 4.4.

Let $p>3$ be a prime. Let $x_{0}\in\overline{\operatorname{\mathbb{F}}}_{p}$
be a root of $F_{3p}$.

  1. (1)

The multiplicity of $x_{0}$ as a root of $F_{3p}$ is at most $2$.

  2. (2)

The multiplicity of $x_{0}$ as a root of $F_{3p}$ is $2$ if and only if
$x_{0}\in\operatorname{\mathbb{F}}_{p}$ and $x_{0}$ is a root of
$u_{3}(x)=x^{4}+2x^{3}+2x+1$.

###### Proof.

We have ${\rm disc}(u_{3})=-1728=-2^{6}\times 3^{3}\neq 0\pmod{p}$. So the
first statement follows from 3.11 Part (b).

The ‘if’ part of the second statement follows from 3.11 Part (a). Now we
discuss the ‘only if’ part. Suppose that the multiplicity of $x_{0}$ as a root
of $F_{3p}$ is $2$. 3.11 Part (a) immediately implies that $x_{0}$ is a root
of $u_{3}$. So the only thing left to show is that
$x_{0}\in\operatorname{\mathbb{F}}_{p}$.

As described in the proof of 3.13, there exists
$\mu\in\operatorname{\mathbb{F}}_{p}$ such that

$a_{3}(x_{0},\mu)=0,\quad\text{and}\quad R_{3}(\mu)={\rm
resultant}(a_{3}(x,\mu),u_{3}(x))=-2\mu^{4}+36\mu^{2}+54=0.$

The latter equation implies that $108=(\mu^{2}-9)^{2}$ and hence $3$ is a
square modulo $p$. Write $3=c^{2}$ for some
$c\in\operatorname{\mathbb{F}}_{p}$. We have

$u_{3}(x)=(x^{2}+x+1)^{2}-3x^{2}=(x^{2}+(1+c)x+1)(x^{2}+(1-c)x+1)\in\operatorname{\mathbb{F}}_{p}[x].$

Let $b(x)\in\operatorname{\mathbb{F}}_{p}[x]$ be the minimal polynomial of
$x_{0}$ over $\operatorname{\mathbb{F}}_{p}$. Then $b(x)$ is an irreducible
factor of both $u_{3}(x)$ and $a_{3}(x,\mu)$. In particular $\deg b(x)=1$ or
$2$.

If $\deg b(x)=2$, then $b(x)=x^{2}+(1\pm c)x+1$ is reciprocal. Hence the
zeroes of $b(x)$ are $x_{0}$ and $1/x_{0}$. Since $b(x)$ divides
$a_{3}(x,\mu)=x^{3}-\mu x^{2}-\mu x-1$, the zeroes of $a_{3}(x,\mu)$ are
$x_{0},1/x_{0}$ and $\beta$, for some
$\beta\in\overline{\operatorname{\mathbb{F}}}_{p}$. By Vieta’s formula,
$\beta=x_{0}\cdot(1/x_{0})\cdot\beta=1$. Hence $0=a_{3}(1,\mu)=-2\mu$, a
contradiction since $R_{3}(0)=54\neq 0\in\operatorname{\mathbb{F}}_{p}$.

The above argument shows that $\deg b(x)=1$ and hence
$x_{0}\in\operatorname{\mathbb{F}}_{p}$. ∎

######  Corollary 4.5.

Let $p>3$ be a prime. Then ${\rm disc}(F_{3p})=0\pmod{p}$ if and only if
$u(x)=x^{4}+2x^{3}+2x+1$ has a root modulo $p$. In particular,

  1. (a)

if $p\equiv\pm 5\pmod{12}$ then $p\nmid{\rm disc}(F_{3p})$,

  2. (b)

if $p\equiv 11\pmod{12}$ then $p\mid{\rm disc}(F_{3p})$,

  3. (c)

if $p\equiv 1\pmod{12}$ then $p\mid{\rm disc}(F_{3p})$ if and only if $12$ is
a quartic residue mod $p$.

###### Proof.

The first statement follows immediately from 4.4. In particular if $p\equiv\pm
5\pmod{12}$ then $\left(\dfrac{3}{p}\right)=-1$ and hence
$u_{3}(x)=(x^{2}+x+1)^{2}-3x^{2}$ has no root in
$\operatorname{\mathbb{F}}_{p}$. Therefore ${\rm disc}(F_{3p})\neq 0\pmod{p}$.

Now suppose $p\equiv\pm 1\pmod{12}$. Then $\left(\dfrac{3}{p}\right)=1$. Let
$c\in\operatorname{\mathbb{F}}_{p}$ such that $3=c^{2}$.

$u_{3}(x)=(x^{2}+x+1)^{2}-3x^{2}=(x^{2}+(1+c)x+1)(x^{2}+(1-c)x+1).$

The discriminant of $x^{2}+(1+c)x+1$ is equal to $(1+c)^{2}-4=2c$, and the
discriminant of $x^{2}+(1-c)x+1$ is equal to $(1-c)^{2}-4=-2c$.

If $p\equiv 11\pmod{12}$ then $\left(\dfrac{-1}{p}\right)=-1$. Hence either
$2c$ or $-2c$ is a square in $\operatorname{\mathbb{F}}_{p}$. Therefore,
either $x^{2}+(1+c)x+1$ or $x^{2}+(1-c)x+1$ has a root in
$\operatorname{\mathbb{F}}_{p}$. So 4.4 implies that $F_{3p}$ has a double
root in $\operatorname{\mathbb{F}}_{p}$, and so $p\mid{\rm disc}(F_{3p})$.

If $p\equiv 1\pmod{12}$ then
$\left(\dfrac{2c}{p}\right)=\left(\dfrac{-2c}{p}\right)$. By 4.4, we get that
$p\mid{\rm disc}(F_{3p})$ if and only if there exists
$a\in\operatorname{\mathbb{F}}_{p}$ such that $a^{2}=2c$. Since $c^{2}=3$,
this is true if and only if there exists $a\in\operatorname{\mathbb{F}}_{p}$
such that $a^{4}=12$, i.e., $12$ is a quartic residue mod $p$. ∎

######  Corollary 4.6.

Let $x_{0}\in\operatorname{\mathbb{F}}_{p}$. Then $x_{0}$ is a root of the
Fekete polynomial $f_{3p}$ if and only if it is a root of
$u_{3}(x)=x^{4}+2x^{3}+2x+1.$

###### Proof.

Suppose $x_{0}\in\operatorname{\mathbb{F}}_{p}$ is a root of $u_{3}(x)$. Then
4.4 says that $x_{0}$ is a double root of $F_{3p}$. By the explicit
description of the cyclotomic factors of $F_{3p}$ given in Eq. 4.1, it is
clear that $x\prod\limits_{d\in S_{3p}}\Phi_{d}(x)$ is separable over
$\operatorname{\mathbb{F}}_{p}$. So we can deduce that $x_{0}$ is a root of
$f_{3p}$.

Conversely, suppose $x_{0}\in\operatorname{\mathbb{F}}_{p}$ is a root of
$f_{3p}$. So it is also a root of $F_{3p}$. We know by 2.6 that
$F_{3p}(1)=2(p-1)=-2\neq 0\in\operatorname{\mathbb{F}}_{p}$ and
$F_{3p}(\zeta_{3})=-(p-1)=1\neq 0\in\operatorname{\mathbb{F}}_{p}$. This means
that $x_{0}^{3}\neq 1$. On the other hand, since
$x_{0}\in\operatorname{\mathbb{F}}_{p}$, we know that $x_{0}^{p-1}=1$.
Therefore by Eq. 4.1, we see that $x_{0}$ has multiplicity at least $2$ as a
root of $F_{3p}$. 4.4 then gives us that $x_{0}$ is a root of $u_{3}(x)$. ∎

######  Corollary 4.7.

The polynomial $f_{3p}$ is separable over $\operatorname{\mathbb{F}}_{p}$, and
hence also separable over $\operatorname{\mathbb{Z}}$. Consequently, $g_{3p}$
is separable as well.

###### Proof.

Suppose on the contrary that $f_{3p}$ is not separable over
$\operatorname{\mathbb{F}}_{p}$. Let
$x_{0}\in\overline{\operatorname{\mathbb{F}}}_{p}$ be a root of $f_{3p}$ with
${\rm mult}_{x_{0}}(f_{3p})\geq 2$. Then ${\rm mult}_{x_{0}}(F_{3p})\geq 2$
and 4.4 says that ${\rm mult}_{x_{0}}(F_{3p})=2$ and
$x_{0}\in\operatorname{\mathbb{F}}_{p}$. This is absurd because $x_{0}$ is
also a root of $x\prod\limits_{d\in S_{3p}}\Phi_{d}(x)$ by Eq. 4.1, but that
makes ${\rm mult}_{x_{0}}(F_{3p})\geq 3$. ∎

We now write down explicitly the values $f_{3p}(1)$ and $f_{3p}(-1)$. These
can be obtained directly from 3.4, or computed using the explicit formula for
$f_{3p}$ in 4.1. We then use this information to prove a fact about
$\operatorname{{\rm disc}}(f_{3p})$ that was first discovered by experimental
data. Note that $\operatorname{{\rm disc}}(f_{3p})\neq 0$ since $f_{3p}$ is
separable.

######  Lemma 4.8.

Let $p>3$ be a prime. Then

$f_{3p}(1)=\begin{cases}6&\text{ if }p\equiv 1,7,19\pmod{24}\\\ 3&\text{ if
}p\equiv 13\pmod{24}\\\ 1&\text{ if }p\equiv 5\pmod{24}\\\ 2&\text{ if
}p\equiv 11,17,23\pmod{24}.\end{cases}f_{3p}(-1)=\begin{cases}-1&\text{ if
}p\equiv 5,13\pmod{24}\\\ -2&\text{ otherwise.}\end{cases}$

######  Proposition 4.9.

Let $p>3$ be a prime. If $p\equiv 1\pmod{3}$ then $\operatorname{{\rm
disc}}(f_{3p})<0$. If $p\equiv 2\pmod{3}$ then $\operatorname{{\rm
disc}}(f_{3p})$ is a nonzero perfect square.

###### Proof.

Since $f_{3p}$ is a reciprocal polynomial with $g_{3p}$ its trace polynomial,
we have

$\operatorname{{\rm
disc}}(f_{3p})=(-1)^{\frac{\deg(f_{3p})}{2}}f_{3p}(-1)f_{3p}(1)\operatorname{{\rm
disc}}(g_{3p})^{2}.$

Calculating using 4.8 and 4.1, we get

$\displaystyle\operatorname{{\rm disc}}(f_{3p})$
$\displaystyle=\begin{cases}(-1)^{p+1}\cdot(-2)\cdot 6\cdot\operatorname{{\rm
disc}}(g_{3p})^{2}&\text{ if }p\equiv 1,7,19\pmod{24}\\\
(-1)^{p-1}\cdot(-1)\cdot 3\cdot\operatorname{{\rm disc}}(g_{3p})^{2}&\text{ if
}p\equiv 13\pmod{24}\\\ (-1)^{p-2}\cdot(-1)\cdot 1\cdot\operatorname{{\rm
disc}}(g_{3p})^{2}&\text{ if }p\equiv 5\pmod{24}\\\ (-1)^{p}\cdot(-2)\cdot
2\cdot\operatorname{{\rm disc}}(g_{3p})^{2}&\text{ if }p\equiv
11,17,23\pmod{24}\end{cases}$
$\displaystyle=\begin{cases}-12\operatorname{{\rm disc}}(g_{3p})^{2}&\text{ if
}p\equiv 1,7,19\pmod{24}\\\ -3\operatorname{{\rm disc}}(g_{3p})^{2}&\text{ if
}p\equiv 13\pmod{24}\\\ \operatorname{{\rm disc}}(g_{3p})^{2}&\text{ if
}p\equiv 5\pmod{24}\\\ 4\operatorname{{\rm disc}}(g_{3p})^{2}&\text{ if
}p\equiv 11,17,23\pmod{24}.\end{cases}$

∎

##  5\. The case $n=5p$

In this section, we provide some partial results for the case $n=5p$ where $p$
is a prime greater than $5$. The goal is to prove the following analog of 4.4.

######  Theorem 5.1.

Let $p>5$ be a prime. Let $x_{0}\in\overline{\operatorname{\mathbb{F}}}_{p}$
be a root of $F_{5p}$.

  1. (a)

The multiplicity of $x_{0}$ as a root of $F_{5p}$ is at most $2$.

  2. (b)

The multiplicity of $x_{0}$ as a root of $F_{5p}$ is $2$ if and only
$x_{0}\in\operatorname{\mathbb{F}}_{p}$ and $u_{5}(x_{0})=0$.

###### Proof of 5.1 Part (a).

By 3.11 Part (b), if the discriminant of $u_{5}$ is not zero modulo $p$, we
get the desired result. We compute that

$\operatorname{{\rm disc}}(u_{5})=-2^{12}\cdot 5^{7}\cdot 11^{2}.$

When $p=11$, we check directly that $F_{5p}=F_{55}$ has no repeated root in
$\operatorname{\overline{\mathbb{F}}}_{11}$. ∎

In this section, we use $a_{\mu}(x)$ for
$a_{5}(x,\mu)=(x^{5}-1)-\mu(x+x^{2}+x^{3}+x^{4})$. Using SageMath, we see that
the resultant of $a_{\mu}(x)$ and $u_{5}(x)$ is given by

$R_{5}(\mu)=\operatorname{{\rm
Res}}(a_{\mu}(x),u_{5}(x))=-(64\mu^{8}-400\mu^{6}-500\mu^{4}-25000\mu^{2}-12500).$

Because $a_{\mu}(x)$ and $u_{5}(x)$ have a common root, their resultant must
be $0$. In other words, we know that $\mu\in\operatorname{\mathbb{F}}_{p}$ is
a root of $R_{5}(y).$ Using SageMath, we can see that we can rewrite
$R_{5}(y)$ in the following form

$-R_{5}(y)=(8y^{4}-25y^{2}+125)^{2}-5(25y^{2}+75)^{2}.$

######  Lemma 5.2.

Suppose that $F_{5p}(x)$ has a repeated root
$x_{0}\in\overline{\operatorname{\mathbb{F}}}_{p}$, then
$\left(\frac{5}{p}\right)=1.$

###### Proof.

As explained above, the existence of a repeated root
$x_{0}\in\overline{\operatorname{\mathbb{F}}}_{p}$ implies that $R_{5}(y)$ has
a root $\mu\in\operatorname{\mathbb{F}}_{p}$ where

$-R_{5}(y)=(8y^{4}-25y^{2}+125)^{2}-5(25y^{2}+75)^{2}.$

If $25\mu^{2}+75\neq 0$, then we conclude that $\left(\frac{5}{p}\right)=1.$
Otherwise, we must have $\mu^{2}+3=0$. Consequently

$0=-R_{5}(\mu)=(8\mu^{4}-25\mu^{2}+125)^{2}=2^{4}\times 17.$

Since $p>5$, we conclude that $p=17.$ This is impossible because
$\left(\frac{-3}{17}\right)=-1$, and hence the equation $\mu^{2}+3=0$ has no
solution in $\operatorname{\mathbb{F}}_{p}.$ ∎

######  Corollary 5.3.

If $\left(\frac{5}{p}\right)=-1$ then $F_{5p}$ is separable over
$\operatorname{\mathbb{F}}_{p}$. ∎

We now complete the proof of 5.1.

###### Proof of 5.1 Part(2).

Suppose $x_{0}\in\operatorname{\mathbb{F}}_{p}$ is a root of $u_{5}(x)$. By
Eq. 3.3, since we know that $u_{5}(1)=q(q-1)\neq
0\in\operatorname{\mathbb{F}}_{p}$ and $u_{5}(\zeta_{5})=-5\zeta_{5}^{4}\neq
0\in\overline{\operatorname{\mathbb{F}}}_{p}$ for any primitive $5$-th root of
unity $\zeta_{5}\in\overline{\operatorname{\mathbb{F}}}_{p}$, we get that
$x_{0}^{5}\neq 0$. On the other hand $x_{0}^{p-1}=1$. Hence $F_{5p}(x_{0})=0$.
So 3.11 Part (a) says that ${\rm mult}_{x_{0}}(F_{5p})\geq 2$. Combining with
5.1 Part(a), we conclude that ${\rm mult}_{x_{0}}(F_{5p})=2$.

Conversely suppose that $x_{0}\in\overline{\operatorname{\mathbb{F}}}_{p}$ is
a double root of $F_{5p}$. By 5.2, one has $\left(\frac{5}{p}\right)=1.$ Let
$c\in\operatorname{\mathbb{F}}_{p}$ be such that $c^{2}=5$. Then we have

$\displaystyle u_{5}(x)$ $\displaystyle=(1+x+x^{2}+x^{3}+x^{4})^{2}-5x^{2}$
$\displaystyle=(1+x+x^{2}+x^{3}+x^{4}-cx^{2})(1+x+x^{2}+x^{3}+x^{4}+cx^{2}).$

Let $m(x)$ be the minimal polynomial of $x_{0}$ over
$\operatorname{\mathbb{F}}_{p}$. Then $m(x)$ is a common divisor of $u_{5}(x)$
and $a_{\mu}(x).$ Up to a choice of $c$, we can assume that $m(x)$ is a
divisor of

$v(x)=1+x+x^{2}+x^{3}+x^{4}-cx^{2}.$

By polynomial division, we see that $a_{\mu}(x)=(x-\mu-1)v(x)+w(x)$, where
$w(x)=cx^{3}-(c+c\mu)x^{2}+\mu$. Since $x_{0}$ is a common root of $v(x)$ and
$a_{\mu}(x)$, we get that $x_{0}$ is a common root of $v(x)$ and $w(x)$. Hence
$\deg m\leq 2$. Suppose that $\deg m=2$ and $m(x)=x^{2}+ax+b$, for some
$a,b\in\operatorname{\mathbb{F}}_{p}$.

Case 1: $b=1$, i.e., $m(x)$ is reciprocal. In this case, the roots of $m(x)$
are $x_{0}$ and $1/x_{0}$. This implies that $1/x_{0}$ is also a root of
$a_{\mu}(x)$. Hence

$0=x_{0}^{5}a_{\mu}(1/x_{0})=(1-x_{0}^{5})-\mu(x_{0}+x_{0}^{2}+x_{0}^{3}+x_{0}^{4}).$

From $a_{\mu}(x_{0})=0$, we see that
$x_{0}^{5}-1=\mu(x_{0}+x_{0}^{2}+x_{0}^{3}+x_{0}^{4})=1-x_{0}^{5}$. Hence
$x_{0}^{5}-1=0$. Thus
$0=(x_{0}^{5}-1)=(1+x_{0}+x_{0}^{2}+x_{0}^{3}+x_{0}^{4})(x_{0}-1)=cx_{0}^{2}(x_{0}-1)$.
This implies that $x_{0}=0$ or $1$, a contradiction.

Case 2: $b\not=1$, i.e., $m(x)$ is not reciprocal. In this case, since $v(x)$
is reciprocal of degree 4, one has

$v(x)=\dfrac{1}{b}(x^{2}+ax+b)(1+ax+bx^{2}).$

By comparing the corresponding coefficients, we obtain

$\dfrac{a+ab}{b}=1\quad\text{ and }\dfrac{1+a^{2}+b^{2}}{b}=1-c.$

Hence

$a+ab=b\text{ and }1+a^{2}+b^{2}=b-bc.$

Also, since $m(x)=x^{2}+ax+b$ is a divisor of $w(x)=cx^{3}-(c+c\mu)x^{2}+\mu$,
one can write

$cx^{3}-(c+c\mu)x^{2}+\mu=(x^{2}+ax+b)(cx-d)=cx^{3}+(ac-d)x^{2}+(bc-ad)x-bd,$

for some $d\in\operatorname{\mathbb{F}}_{p}$. By comparing the corresponding
coefficients, we obtain that

$ac-d=-c-c\mu,\quad bc-ad=0,\quad\text{ and }-bd=\mu.$

Hence

$bc=ad=a(ac+c+c\mu)=a^{2}c+ac+ac\mu.$

Thus $b=a^{2}+a+a\mu$. Also, we have

$a\mu=-abd=-b^{2}c.$

Hence

$b=a^{2}+a-b^{2}c.$

In summary, we obtain the following three relations

$a+ab=b\;(1),\quad 1+a^{2}+b^{2}=b-bc\;(2),\quad b=a^{2}+a-b^{2}c\;(3).$

From $(2)$ and $(3)$ we get

$b+a^{2}b+b^{3}=b^{2}-b^{2}c=b^{2}+b-(a^{2}+a).$

Hence

$b^{2}-b^{3}=a^{2}+a^{2}b+a=ab+a=b.$

(For the second and last equality, we use (1).) Since $b\not=0$, we obtain
that $b^{2}-b+1=0$.

Now from (2), we have $-bc=1+a^{2}+b^{2}-b=a^{2}$. Hence
$a^{4}=b^{2}c^{2}=5b^{2}$. From (1), we obtain $b=a(1+b)$. Hence
$b^{4}=a^{4}(1+b)^{4}=5b^{2}(1+b)^{4}$. Thus

$b^{2}=5(1+b)^{4}=5(1+2b+b^{2})^{2}=5(3b)^{2}=45b^{2}.$

We obtain that $p\mid 44$. Hence $p=11$. But we can check directly that
$F_{5\cdot 11}(x)$ has no repeated root in
$\overline{\operatorname{\mathbb{F}}}_{p}$, a contradiction. ∎

######  Corollary 5.4.

The polynomial $f_{5p}$ is separable over $\operatorname{\mathbb{F}}_{p}$, and
hence also separable over $\operatorname{\mathbb{Z}}$. Consequently, $g_{5p}$
is separable as well.

######  Remark 5.5.

One may wonder if a similar statement as 5.1 holds for general $n=pq$. It
turns out that the answer is no. We provide some concrete counterexamples.

  1. (1)

When $q=7,p=101$, the polynomial $x^{2}+42x+10$ is an irreducible factor of
$F_{pq}$ (and $f_{pq}$) over $\operatorname{\mathbb{F}}_{p}$, with
multiplicity equal to $2$.

  2. (2)

When $q=11,p=13$, the polynomial $x^{2}+9x+10$ is an irreducible factor of
$F_{pq}$ (and $f_{pq}$) over $\operatorname{\mathbb{F}}_{p}$, with
multiplicity equal to $2$.

  3. (3)

When $q=11,p=61$, the polynomial $x^{2}+16x+14$ is an irreducible factor of
$F_{pq}$ (and $f_{pq}$) over $\operatorname{\mathbb{F}}_{p}$, with
multiplicity equal to $2$.

It would be interesting to investigate this problem further. For instance, can
we get upper bounds on the multiplicity of a repeated root
$x_{0}\in\overline{\operatorname{\mathbb{F}}}_{p}$ of $F_{n}(x)$?

##  6\. Irreducibility test for $f_{n}$

In this section, we discuss some methods to verify the irreducibility of
$f_{n}$ over $\operatorname{\mathbb{Z}}[x].$ Generally speaking, there are
some built-in functions to test whether a given polynomial
$f\in\operatorname{\mathbb{Z}}[x]$ is irreducible or not. While these built-in
functions work quite well for polynomials of small degrees, it becomes
computationally expensive when we work with polynomials of large degrees. For
our problem, we exploit the fact that $f_{n}$ is a reciprocal polynomial. In
some cases, the irreducibility of $f_{n}$ is equivalent to the irreducibility
of $g_{n}$. The advantage of working with $g_{n}$ is that its degree is only
half of the degree of $f_{n}$. Furthermore, some modular methods apply to
$g_{n}$ but not to $f_{n}$ (for example, when the discriminant of $f_{n}$ is a
perfect square, $f_{n}$ is reducible over $\operatorname{\mathbb{F}}_{q}[x]$
for all prime $q$, see e.g. [21, Remark 11.3]). We start with the following
proposition.

######  Proposition 6.1.

(See [7, Theorem 11]) Let $f$ be a monic reciprocal polynomial of degree $2n$.
Let $g$ be the trace polynomial of $f$. Suppose that $g$ is irreducible. Then
$f$ is also irreducible if at least one of the following conditions holds.

  1. (1)

$|f(1)|$ and $|f(-1)|$ are not perfect squares.

  2. (2)

$f(1)$ and the middle coefficient of $f$ have different signs.

  3. (3)

The middle coefficient of $f$ is $0$ or $\pm{1}$.

In what follows, we propose some modifications to this proposition. First, we
introduce the following definition.

######  Definition 6.2.

(see [7]) Let $h$ be a polynomial of degree $n$. We define the reversal
polynomial of $h$ by $h_{{\text{rev}}}=x^{n}h(1/x)$.

######  Lemma 6.3.

Let $f$ be a monic reciprocal polynomial of degree $2n$. Let $g$ be the trace
polynomial of $f$. Suppose that $g$ is irreducible. If $f$ is reducible, then
there exists $a\in\\{-1,1\\}$ and a monic polynomial
$h(x)\in\operatorname{\mathbb{Z}}[x]$ such that

$f(x)=ah(x)h_{{\text{rev}}}(x).$

Furthermore, if $f(1)>0$ then $a=1.$

###### Proof.

This follows from the proof of [7, Theorem 11]. ∎

######  Proposition 6.4.

Let $f$ be a monic reciprocal polynomial of degree $4n$. Let $g$ be the trace
polynomial of $f$. Suppose that $g$ is irreducible and that $f(1)f(-1)<0.$
Then $f$ is irreducible.

###### Proof.

Suppose that $f$ is reducible. Then 6.3, $f(x)=ax^{2n}h(x)h(\frac{1}{x})$
where $h\in\operatorname{\mathbb{Z}}[x]$ and $a\in\\{1,-1\\}.$ We have
$f(1)=ah(1)^{2}$ and $f(-1)=ah(-1)^{2}.$ Consequently

$f(1)f(-1)=a^{2}h(1)^{2}h(-1)^{2}.$

This is impossible because $f(1)f(-1)<0.$ ∎

We can apply this proposition to our $f_{pq}$ because $f_{pq}(1)>0$ and
$f_{pq}(-1)<0$ provided that the degree of $f_{pq}$ is divisible by $4$ (see
3.4).

######  Proposition 6.5.

Let $f=\sum_{k=0}^{2n}a_{k}x^{k}$ be a monic reciprocal polynomial of degree
$2n$ such that $f(1)f(-1)\neq 0$. Let $g$ be the trace polynomial of $f$.
Suppose that $g$ is irreducible. Suppose that the middle coefficient
$|a_{n}|\leq 2.$ Then $f$ is irreducible.

###### Proof.

Suppose that $f$ is reducible. Without loss of generality, we can assume that
$f(1)>0.$ Then we can find a monic $h(x)\in\operatorname{\mathbb{Z}}[x]$ such
that $f(x)=h(x)h_{{\text{rev}}}(x)$. Let $h(x)=\sum_{k=0}^{n}c_{k}x^{k}.$ By
definition $c_{n}=1$. Furthermore, by comparing the leading coefficients of
both sides, we must have $c_{0}=1$ as well. Additionally, by comparing the
middle coefficients of both sides we have

$a_{n}=\sum_{k=0}^{n}c_{k}^{2}.$

Since $c_{n}=c_{0}=1$, we conclude that $c_{k}=0$ for $1\leq k\leq n$. In
other words, $h(x)=x^{n}+1.$ If $n$ is odd then $h(-1)=0$ and so $f(-1)=0$
which is a contradiction. If $n$ is even then $h(x)$ and $h_{{\text{rev}}}(x)$
are both reciprocal polynomials. This forces $g(x)$ to be reducible which is
also a contradiction. We conclude that $f(x)$ must be irreducible. ∎

######  Remark 6.6.

By 4.2, the middle coefficient of $f_{3p}\in\\{-2,-1,0,1,2\\}$. We checked
that for $q=5$ and $p\leq 1000$, this is still true. However, this is
unfortunately not true for $q=7$ (the middle coefficient of $f_{7\times 601}$
is $3$.)

######  Proposition 6.7.

Let $f$ be a monic reciprocal polynomial of degree $2n$. Let $g$ be the trace
polynomial of $f$. Suppose that $g$ is irreducible. Suppose that there exists
a prime number $q_{1}$ and a number $m$ that the number of irreducible factors
of degree $m$ of $f$ modulo $q_{1}$ is an odd number. Then $f$ is irreducible.

###### Proof.

As before, if $f$ is reducible then $f(x)=\pm h(x)h_{rev}(x).$ If $a(x)$ is an
irreducible factor of $h(x)$ modulo $q$ then so is $a_{{\text{rev}}}(x).$
Therefore, the degree $\deg(a(x))$ must appear an even number of time. This
contradicts the assumption, hence $f$ must be irreducible. ∎

######  Algorithm 6.8.

To apply the criterion mentioned in 6.7 to $f_{pq}$, we do the following two
steps.

  * •

Step 1: Show that $g_{pq}$ is irreducible. This can be achieved by finding a
prime number $q_{2}$ such that $g_{pq}$ is irreducible modulo $q_{2}$.

  * •

Step 2: Find a prime number $q_{1}$ that satisfies the condition of 6.7.

######  Example 6.9.

We demonstrate this method with a concrete example. Let us take
$f_{15}(x)=x^{6}-x^{4}+x^{3}-x^{2}+1$. We have

$g_{15}(x)=x^{3}-4x+1.$

We can check that $g_{15}(x)$ is irreducible over
$\operatorname{\mathbb{F}}_{3}(x)$, so it is irreducible over
$\operatorname{\mathbb{Z}}[x]$ as well. Furthermore, over
$\operatorname{\mathbb{F}}_{2}(x)$, $f(x)$ factors as follow

$f_{15}(x)=(x^{2}+x+1)(x^{4}+x^{3}+x^{2}+x+1).$

We see that the degree $2$ factors appear only one time. Therefore, by 6.7
$f_{15}(x)$ must be irreducible.

######  Conjecture 6.10.

Let $n=pq$ be a product of two distinct odd primes. Then $f_{n}$ and $g_{n}$
are both irreducible.

######  Remark 6.11.

Using the strategy described in 6.8, we have verified that 6.10 holds for
$n=pq$ with $13\leq q<p$ and $n\leq 7200$ as of July 2023 (the case $q<13$
will be studied in more detail in the next section). It is interesting to
remark that while the values of $q_{2}$ vary with respect to the size of $n$,
the values $q_{1}$ are often small. We refer the readers to the GitHub
repository [8] for the data regarding this issue.

##  7\. Galois theory for $f_{n}$ and $g_{n}$

For a polynomial $f\in\operatorname{\mathbb{Q}}[x]$, we let
$\operatorname{\mathbb{Q}}(f)$ be the splitting field of $f.$ For $n=pq$, we
let $f_{n}$ and (respectively $g_{n}$) be the Fekete polynomial associated
with $n$ (respectively its trace polynomial). In this section, we investigate
the Galois groups of $f_{n}$ and $g_{n}.$

###  7.1. The Galois group of $g_{n}$

Let $m$ be the degree of $g_{n}.$ Then the Galois group of $g_{n}$ is a
naturally a subgroup of $S_{m}$ permuting the roots of $g_{n}$. In our
investigation, it turns out that the Galois group of $g_{n}$ is always $S_{m}$
for the cases that we consider. In order to verify this fact, we use a modular
technique. Specifically, by [22, Propisition 4.10], it is sufficient to find a
triple $(q_{1},q_{2},q_{3})$ such that

  1. (1)

$g(x)$ is irreducible in $\operatorname{\mathbb{F}}_{q_{1}}[x]$.

  2. (2)

Over$\operatorname{\mathbb{F}}_{q_{2}}[x]$, $g(x)=(x+c)h(x)$ where
$c\in\operatorname{\mathbb{F}}_{q_{2}}$ and $h(x)$ is an irreducible
polynomial of degree $m-1$.

  3. (3)

Over $\operatorname{\mathbb{F}}_{q_{3}}[x]$, $g(x)=m_{1}(x)m_{2}(x)$ where
$m_{1}(x)$ is an irreducible polynomial of degree $2$ and $m_{2}(x)$ is a
product of distinct irreducible polynomials of odd degrees.

We demonstrate this strategy with a concrete example.

######  Example 7.1.

Let $n=3\times 7$. In this case, $g_{n}(x)$ is the following degree $8$
polynomial

$g_{n}(x)=x^{8}+x^{7}+2x^{6}+3x^{5}+4x^{3}+4x^{2}+4x+2.$

Using SageMath, we see that $g_{n}(x)$ is irreducible over
$\operatorname{\mathbb{F}}_{5}[x].$ Over $\operatorname{\mathbb{F}}_{19}[x]$,
$g(x)$ factors as

$g_{n}(x)=(x+8)(x^{7}+12x^{6}+10x^{5}+8x^{4}+13x^{3}+5x^{2}+x+5).$

Finally, over $\operatorname{\mathbb{F}}_{7}(x)$, $g_{n}$ factors as

$g_{n}(x)=(x^{2}+x+4)(x^{3}+4)(x^{3}+2x+1).$

We conclude that the Galois group of $g_{n}$ is $S_{8}.$

Based on the extensive numerical data that we produced, it seems reasonable to
propose the following question.

######  Question 7.2.

Let $n=pq$ be a product of two distinct odd prime numbers, and
$m=\deg(g_{n})$. Is the Galois group of $g_{n}$ isomorphic to the full
symmetric group $S_{m}$?

Using this strategy, we have verified the following.

######  Proposition 7.3.

The answer for 7.2 is affirmative for the following values of $n$

  1. (1)

$n=3p$ with $3<p<1000.$

  2. (2)

$n=5p$ with $5<p<1000.$

  3. (3)

$n=7p$ with $p<600.$

  4. (4)

$n=11p$ with $p<500.$

  5. (5)

$n=pq$ with $13\leq q<p$ and $n<2500.$

###### Proof.

The data for the required triple $(q_{1},q_{2},q_{3})$ required to compute the
Galois group of $g_{n}$ is contained in the GitHub repository [8]. ∎

###  7.2. The Galois group of $f_{n}$

By definition of $g_{n}$ and $f_{n}$, we know that there is an exact sequence
of Galois groups

$1\to\operatorname{\text{Gal}}(\operatorname{\mathbb{Q}}(f_{n})/\operatorname{\mathbb{Q}}(g_{n}))\to\operatorname{\text{Gal}}(\operatorname{\mathbb{Q}}(f_{n})/\operatorname{\mathbb{Q}})\to\operatorname{\text{Gal}}(\operatorname{\mathbb{Q}}(g_{n})/\operatorname{\mathbb{Q}})\to
1.$

As explained in the previous section, the Galois group
$\operatorname{\text{Gal}}(\operatorname{\mathbb{Q}}(g_{n})/\operatorname{\mathbb{Q}})$
is naturally a subgroup of $S_{m}.$ Additionally, the Galois group
$\operatorname{\text{Gal}}(\operatorname{\mathbb{Q}}(f_{n})/\operatorname{\mathbb{Q}}(g_{n}))$
is naturally a subgroup of $(\operatorname{\mathbb{Z}}/2)^{m}.$ The symmetric
group $S_{m}$ acts naturally on $(\operatorname{\mathbb{Z}}/2)^{m}$ by
permutation. From the above exact sequence, we conclude that
$\operatorname{\text{Gal}}(\operatorname{\mathbb{Q}}(f_{n})/\operatorname{\mathbb{Q}})$
is a subgroup of $(\operatorname{\mathbb{Z}}/2)^{m}\rtimes S_{m}.$ We note
that we can also consider $(\operatorname{\mathbb{Z}}/2)^{m}\rtimes S_{m}$ as
a subgroup of $S_{2m}$ (see [10, Section 2]). We will utilize the following
propositions to determine the Galois group of $f_{n}.$

######  Proposition 7.4.

([21, Proposition 11.11]) Let $f(x)$ be a monic reciprocal polynomial with
integer coefficients of even degree $2m$. Let $g$ be the trace polynomial of
$f$. Assume that

  1. (1)

The Galois group of $g$ is $S_{m}.$

  2. (2)

There exists a prime number $q$ such that over
$\operatorname{\mathbb{F}}_{q}[x]$, $f(x)=p_{2}(x)h(x)$ where $p_{2}(x)$ is an
irreducible polynomial of degree $2$, and $h(x)$ is a product of distinct
irreducible polynomials of odd degrees.

Then the Galois group of $f$ is $(\operatorname{\mathbb{Z}}/2)^{m}\rtimes
S_{m}.$

######  Proposition 7.5.

(See [21, Proposition 11.8]) Let $f(x)$ be a monic reciprocal polynomial with
integer coefficients of even degree $2m$. Let $g$ be the trace polynomial of
$f$. Assume that

  1. (1)

The Galois group of $g$ is $S_{m}.$

  2. (2)

The discriminant of $f$, or equivalently $(-1)^{m}f(1)f(-1)$, is a perfect
square.

  3. (3)

There exists a prime number $q$ such that over
$\operatorname{\mathbb{F}}_{q}[x]$, $f(x)=p_{2}(x)p_{4}(x)h(x)$ where
$p_{2}(x)$ is an irreducible polynomial of degree $2$, $p_{4}(x)$ is an
irreducible polynomial of degree $4$, and $h(x)$ is a product of distinct
irreducible polynomials of odd degrees.

Then the Galois group of $f$ is $\ker(\Sigma^{\prime})\rtimes S_{n}$ where
$\Sigma^{\prime}$ is the summation map

$\Sigma^{\prime}(a_{1},a_{2},\ldots,a_{m})=\prod_{i=1}^{m}a_{i}.$

We demonstrate the usage of these criteria with some concrete examples.

######  Example 7.6.

Let us consider the case $n=3\times 7$. As demonstrated in 7.1, we know that
the Galois group of $g_{n}$ is $S_{8}$. By 3.7, the discriminant of $f_{n}$ is
not a perfect square. Furthermore, over $\operatorname{\mathbb{F}}_{227}[x]$,
$f_{n}$ factors as follow

$\displaystyle f_{n}(x)$
$\displaystyle=(x^{2}+12x+1)(x^{7}+78x^{6}+173x^{5}+18x^{4}+119x^{3}+129x^{2}+107x+9)$
$\displaystyle\times(x^{7}+138x^{6}+90x^{5}+215x^{4}+2x^{3}+221x^{2}+160x+101).$

By 7.4, we conclude that the Galois group of $f_{n}$ is
$(\operatorname{\mathbb{Z}}/2)^{8}\rtimes S_{8}.$

######  Example 7.7.

Let us consider the case $n=5\times 7.$ In this case, we can check that
$g_{n}(x)$ is a polynomial of degree $11$

$g_{n}(x)=x^{11}-11x^{9}+43x^{7}+x^{6}-71x^{5}-5x^{4}+46x^{3}+4x^{2}-8x+2.$

We can check that the triple $(q_{1},q_{2},q_{3})=(29,47,31)$ guarantees that
the Galois group of $g_{n}$ is $S_{11}.$ By 3.7, we know that the discriminant
of $f_{n}$ is a perfect square. We can check that over
$\operatorname{\mathbb{F}}_{433}[x]$, $f_{n}$ factors as

$\displaystyle(x+97)(x+125)(x^{2}+41x+1)(x^{4}+124x^{3}+295x^{2}+124x+1)$
$\displaystyle\times(x^{7}+190x^{6}+62x^{5}+191x^{4}+406x^{3}+37x^{2}+393x+313)$
$\displaystyle\times(x^{7}+289x^{6}+393x^{5}+76x^{4}+168x^{3}+50x^{2}+251x+350).$

By 7.5, we conclude that the Galois group of $f_{n}$ is
$\ker(\Sigma^{\prime})\rtimes S_{11}$ where $\Sigma^{\prime}$ is the summation
map

$\Sigma^{\prime}:(\operatorname{\mathbb{Z}}/2)^{11}\to\operatorname{\mathbb{Z}}/2.$

Based on the extensive numerical data that we found, it seems reasonable to
ask the following question.

######  Question 7.8.

Let $n=pq$ as before and $2m=\deg(f_{n}).$ Is it true that the following
statements hold

  1. (1)

If $p\equiv 1\pmod{q}$ then the Galois group of $f_{n}$ is
$(\operatorname{\mathbb{Z}}/2)^{m}\rtimes S_{m}.$

  2. (2)

If $p\not\equiv 1\pmod{q}$ and $p,q\equiv 1\pmod{4}$, then the Galois group of
$f_{n}$ is $(\operatorname{\mathbb{Z}}/2)^{m}\rtimes S_{m}.$

  3. (3)

In the remaining case, namely $p\not\equiv 1\pmod{q}$ and at least one of $p$
or $q$ is not of the form $4k+1$, then the Galois group of $f_{n}$ is
$\ker(\Sigma^{\prime})\rtimes S_{m}$ where $\Sigma^{\prime}$ is the summation
map

$\Sigma^{\prime}:(\operatorname{\mathbb{Z}}/2)^{m}\to\operatorname{\mathbb{Z}}/2.$

Using 7.4 and 7.5 we have verified the following.

######  Proposition 7.9.

The answer to 7.8 is affirmative for the following values of $n$

  1. (1)

$n=3p$ with $3<p<1000.$

  2. (2)

$n=5p$ with $5<p<500.$

  3. (3)

$n=7p$ with $7<p<500.$

  4. (4)

$n=11p$ with $11<p<300.$

  5. (5)

$n=pq$ with $13\leq q<p$ and $n<1500.$

## Code availability

An open-source code repository for this work is available on GitHub [8].

## Acknowledgments

We thank Oleksiy Klurman, Andrew Granville, Bjorn Poonen and Kannan
Soundararajan for helpful discussions and correspondence. The third named
author would like to thank William Stein for his help with the platform Cocalc
where our computations are based.

##  Appendix A Zeros on the unit circle

The complex zeros of classical Fekete polynomials
$f_{p}(x)=\sum\limits_{a=0}^{p-1}\chi(a)x^{a}$ for quadratic Dirichlet
characters $\chi=\left(\frac{\cdot}{p}\right)$ of prime conductor $p$ were
studied in [9]. It was shown in [9] that at least half of the zeros of $f_{p}$
lie on the unit circle, and further that there exists a constant $1/2<k_{0}<1$
such that the fraction of zeros of $f_{p}$ lying on the unit circle converges
to $k_{0}$ as $p$ goes to infinity. In this section, we use the approach of
[9] to analyze complex zeros of the Fekete polynomials $F_{n}$ corresponding
to principal Dirichlet characters. We remark that since the coefficients of
$F_{n}$ are either $0$ or $1$, the Erdos-Turan theorem implies that the roots
of this polynomial are almost all clustered around the unit circle and
equidistributed in angle (see [12, Theorem 1] and [14, Theorem 1.3]). We thank
Professor Kannan Soundararajan for pointing this out to us.

Let
$H_{n}:\operatorname{\mathbb{C}}\setminus(0,\infty)\rightarrow\operatorname{\mathbb{C}}$
be the function defined by $H_{n}(z)=z^{-n/2}F_{n}(z)$ where we make a choice
of the square root $z^{1/2}$. If $z=e^{2\pi it}$ we have

$\displaystyle H_{n}(z)$ $\displaystyle=z^{-n/2}\sum_{\begin{subarray}{c}1\leq
a\leq n-1\\\ \gcd(a,n)=1\end{subarray}}z^{a}=\sum_{\begin{subarray}{c}1\leq
a\leq(n-1)/2\\\ \gcd(a,n)=1\end{subarray}}(x^{a-n/2}+x^{n/2-a})$
$\displaystyle=\sum_{\begin{subarray}{c}1\leq a\leq(n-1)/2\\\
\gcd(a,n)=1\end{subarray}}2\cos\left(\pi t(2a-n)\right).$

Let
$\operatorname{\mathbb{C}}_{1}=\\{z\in\operatorname{\mathbb{C}}:\left\lvert
z\right\rvert=1\\}$ denote the unit circle in $\operatorname{\mathbb{C}}$.
Thus $H_{n}$ defines a continuous real valued function on
$\operatorname{\mathbb{C}}_{1}\setminus\\{1\\}$. For
$k\in\operatorname{\mathbb{Z}}$, let $d_{k}$ denote $n/\gcd(n,k)$. By 2.6, if
$0<k<n$ and $\zeta_{n}=e^{2\pi i/n}$, we have

(A.1) $\displaystyle
H_{n}(\zeta_{n}^{k})=\zeta_{n}^{-nk/2}F_{n}(\zeta_{n}^{k})=\frac{(-1)^{k}\mu(d_{k})\phi(n)}{\phi(d_{k})}$

If $k$ is such that $\gcd(n,k)=\gcd(n,k+1)=1$, then $H_{n}$ changes sign on
the arc from $\zeta_{n}^{k}$ to $\zeta_{n}^{k+1}$. Therefore, $H_{n}$ and
hence $F_{n}$ must have a zero on this arc.

Let $\phi_{1}(n)$ denote the cardinality of the set $\\{0\leq
a<n|\gcd(n,a)=\gcd(n,a+1)=1\\}$. Then
$\phi_{1}:\operatorname{\mathbb{N}}\rightarrow\operatorname{\mathbb{N}}$ is a
multiplicative function by Chinese Remainder theorem, and
$\phi_{1}(p^{k})=p^{k}(1-2p^{-1})$. Thus we have the formula
$\phi_{1}(n)=n\prod_{p|n}\left(1-\frac{2}{p}\right)$. In summary, we have just
proved the following.

######  Proposition A.1.

$F_{n}$ has at least $\phi_{1}(n)$ roots on the unit circle where

$\phi_{1}(n)=n\prod_{p|n}\left(1-\frac{2}{p}\right).$

If $n=p$ or $n=2p$ where $p$ is a prime number then all factors of $F_{n}$,
except $x$, are cyclotomic polynomials as explained in Examples 2.4 and 2.5.
The case where $n$ has exactly two odd prime factors is more interesting.
Specifically, let us consider the following special case: we fix an odd prime
$q$ and consider $n=pq$ for varying primes $p$. Then
$\phi_{1}(n)\sim\left(1-\frac{2}{q}\right)n$ as $p\rightarrow\infty$.
Therefore, the number of complex zeros of $F_{n}$ on the unit circle grows at
least as fast as $k_{0}n$ in this limit, with $k_{0}=1-\frac{2}{q}$. It would
be interesting to study this question for general $n.$

## References

  * [1] R. Baker and H. L. Montgomery.  Oscillations of quadratic L-functions.  In Analytic Number Theory, pages 23–40. Springer, 1990.
  * [2] M. Bašić and A. Ilić.  Polynomials of unitary Cayley graphs.  Filomat, 29(9):2079–2086, 2015.
  * [3] P. Borwein.  Computational excursions in analysis and number theory.  Springer Science & Business Media, 2002.
  * [4] P. Borwein, K.-K. Choi, and S. Yazdani.  An extremal property of Fekete polynomials.  Proceedings of the American Mathematical Society, 129(1):19–27, 2001.
  * [5] G. Brookfield.  The coefficients of cyclotomic polynomials.  Mathematics Magazine, 89(3):179–188, 2016.
  * [6] B. Bzdega, A. Herrera-Poyatos, and P. Moree.  Cyclotomic polynomials at roots of unity.  Acta Arithmetica, 184(3):215–230, 2018.
  * [7] A. Cafure and E. Cesaratto.  Irreducibility criteria for reciprocal polynomials and applications.  The American Mathematical Monthly, 124(1):37–53, 2017.
  * [8] S. Chidambaram, J. Mináč, T. T. Nguyen, and N. D. Tân.  Fekete polynomials of principal Dirichlet characters.  https://github.com/tungprime/fekete_polynomials_principal_characters, 2023\.
  * [9] B. Conrey, A. Granville, B. Poonen, and K. Soundararajan.  Zeros of Fekete polynomials.  Annales de l’institut Fourier, 50(3):865–889, 2000.
  * [10] S. Davis, W. Duke, and X. Sun.  Probabilistic Galois theory of reciprocal polynomials.  Expositiones Mathematicae, 16:263–270, 1998.
  * [11] T. Erdélyi.  Improved lower bound for the Mahler measure of the Fekete polynomials.  Constructive Approximation, 48(2):283–299, 2018.
  * [12] P. Erdos and P. Turán.  On the distribution of roots of polynomials.  Annals of mathematics, pages 105–119, 1950.
  * [13] D. Ghinelli and J. D. Key.  Codes from incidence matrices and line graphs of Paley graphs.  Advances in Mathematics of Communications, 5(1):93, 2011.
  * [14] A. Granville.  The distribution of roots of a polynomial.  In Equidistribution in number theory, an introduction, pages 93–102. Springer, 2007.
  * [15] G. H. Hardy and E. M. Wright.  An introduction to the theory of numbers.  Oxford university press, 1979.
  * [16] J. Javelle.  Cryptographie Quantique: Protocoles et Graphes.  PhD thesis, Université de Grenoble, 2014.
  * [17] W. Klotz and T. Sander.  Some properties of unitary Cayley graphs.  The electronic journal of combinatorics, pages R45–R45, 2007.
  * [18] O. Klurman, Y. Lamzouri, and M. Munsch.  $l\\_q$ norms and Mahler measure of Fekete polynomials.  arXiv preprint arXiv:2306.07156, 2023.
  * [19] F. Lemmermeyer.  Quadratic number fields.  Springer Undergraduate Mathematics Series. Springer, 2021.
  * [20] J. Mináč, L. Muller, T. T. Nguyen, and N. D. Tân.  On the Paley graph of a quadratic character.  arXiv preprint arXiv:2212.02005, 2022.
  * [21] J. Mináč, T. T. Nguyen, and N. D. Tân.  On the arithmetic of generalized Fekete polynomials.  arXiv preprint arXiv:2206.11778, 2022.
  * [22] J. Mináč, T. T. Nguyen, and N. D. Tân.  Fekete polynomials, quadratic residues, and arithmetic.  Journal of Number Theory, 242:532–575, 2023.