# Equidistribution of high traces of random matrices over finite fields and
cancellation in character sums of high conductor

Ofir Gorodetsky, Valeriya Kovaleva

###### Abstract

Let $g$ be a random matrix distributed according to uniform probability
measure on the finite general linear group $\mathrm{GL}_{n}(\mathbb{F}_{q})$.
We show that $\mathrm{Tr}(g^{k})$ equidistributes on $\mathbb{F}_{q}$ as
$n\to\infty$ as long as $\log k=o(n^{2})$ and that this range is sharp. We
also show that nontrivial linear combinations of
$\mathrm{Tr}(g^{1}),\ldots,\mathrm{Tr}(g^{k})$ equidistribute as long as $\log
k=o(n)$ and this range is sharp as well. Previously equidistribution of either
a single trace or a linear combination of traces was only known for $k\leq
c_{q}n$, where $c_{q}$ depends on $q$, due to work of the first author and
Rodgers.

We reduce the problem to exhibiting cancellation in certain short character
sums in function fields. For the equidistribution of $\mathrm{Tr}(g^{k})$ we
end up showing that certain explicit character sums modulo $T^{k+1}$ exhibit
cancellation when averaged over monic polynomials of degree $n$ in
$\mathbb{F}_{q}[T]$ as long as $\log k=o(n^{2})$. This goes far beyond the
classical range $\log k=o(n)$ due to Montgomery and Vaughan. To study these
sums we build on the argument of Montgomery and Vaughan but exploit additional
symmetry present in the considered sums.

##  1 Introduction

Fix $\mathbb{F}_{q}$, the finite field of $q$ elements. We denote its
characteristic by $\mathrm{char}(\mathbb{F}_{q})$. Let
$g\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ be an invertible $n\times n$ matrix over
$\mathbb{F}_{q}$ chosen according to the uniform probability measure. The
first author and Rodgers [12, Thm. 1.1] showed that $\mathrm{Tr}(g^{k})$
equidistributes in $\mathbb{F}_{q}$ as $n\to\infty$, uniformly for $k\leq
c_{q}n$ for some sufficiently small $c_{q}$ depending on $q$, and the rate of
convergence is superexponential. However, nothing beyond $k=O(n)$ was known.
We describe our three main results.

######  Theorem 1.1.

Let $g\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ be chosen uniformly at random. Let
$k=k(n)$ be a positive integer such that $\log k=o(n^{2})$. The distribution
of $\mathrm{Tr}(g^{k})$ tends to the uniform distribution on $\mathbb{F}_{q}$
as $n$ tends to $\infty$.

The range $\log k=o(n^{2})$ in Theorem 1.1 is optimal in the sense that we
cannot replace it with $\log k=O(n^{2})$. Indeed, if we take
$k=|\mathrm{GL}_{n}(\mathbb{F}_{q})|=\prod_{i=0}^{n-1}(q^{n}-q^{i})$ then
$\log k\asymp_{q}n^{2}$ and, by Lagrange’s theorem, $g^{k}=I_{n}$ for
$g\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ and so $\mathrm{Tr}(g^{k})\equiv n$ does
not equidistribute. (This shows $\mathrm{Tr}(g^{k})$ is periodic in $k$.)
Theorem 1.1 leaves open the question, not explored in this paper, whether the
range can be extended to $\log k\leq c_{q}n^{2}$ for some constant $c_{q}>0$
depending on $q$; we believe the answer is negative. We also prove a theorem
for combination of traces.

######  Theorem 1.2.

Let $g\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ be chosen uniformly at random. Let
$k=k(n)$ be a positive integer such that $\mathrm{char}(\mathbb{F}_{q})\nmid
k$ and $\log k=o(n)$. Let $a_{j}\in\mathbb{F}_{q}$ for $j=1,\ldots,k$ be
arbitrary constants with $a_{k}\neq 0$. Then the distribution of $\sum_{1\leq
i\leq k}a_{i}\mathrm{Tr}(g^{i})$ tends to the uniform distribution on
$\mathbb{F}_{q}$ as $n$ tends to $\infty$.

Over $\mathbb{F}_{q}$ we have
$\mathrm{Tr}(g^{\mathrm{char}(\mathbb{F}_{q})})=\mathrm{Tr}(g)^{\mathrm{char}(\mathbb{F}_{q})}$
and the condition $\mathrm{char}(\mathbb{F}_{q})\nmid k$ is necessary to avoid
trivial linear combinations. The range $\log k=o(n)$ in Theorem 1.2 is optimal
in the sense that it cannot be replaced by $\log k=O(n)$, as we now
demonstrate by giving an example where $\sum_{1\leq i\leq
k}a_{i}\mathrm{Tr}(g^{i})$ ($\mathrm{char}(\mathbb{F}_{q})\nmid k$, $a_{k}\neq
0$) is not equidistributed and $\log k\asymp_{q}n$. Let
$\overline{\mathbb{F}_{q}}$ denote an algebraic closure of $\mathbb{F}_{q}$,
and let $f\in\mathbb{F}_{q}[T]$ be a monic polynomial. Given its factorization
$f(T)=\prod_{j=1}^{\deg f}(T-\lambda_{j})$ over $\overline{\mathbb{F}_{q}}$,
we define its $i$th ($i\geq 0$) power sum symmetric polynomial as

$p_{i}(f):=\sum_{j=1}^{\deg f}\lambda_{j}^{i}\in\overline{\mathbb{F}_{q}}.$
(1.1)

By Newton’s identities $p_{i}(f)$ is an integral multivariate polynomial in
coefficients of $f$, hence $p_{i}(f)$ is in fact in $\mathbb{F}_{q}$.
Moreover, we have $p_{i}(fg)=p_{i}(f)+p_{i}(g)$ for any monic
$f,g\in\mathbb{F}_{q}[T]$. If $f(T)=\det(I_{n}T-g)$ is the characteristic
polynomial of a matrix $g$, then $p_{i}(f)=\mathrm{Tr}(g^{i})$.

Let $F(T):=\sum_{i=0}^{k}a_{i}T^{i}$ be the product of all monic irreducible
polynomials in $\mathbb{F}_{q}[T]$ of degree at most $n$ (so $a_{k}=1$,
$a_{0}=0$). Then, for any $\lambda\in\cup_{j=1}^{n}\mathbb{F}_{q^{j}}$,

$F(\lambda)=\sum_{i=1}^{k}a_{i}\lambda^{i}=0.$

Hence $\sum_{i=1}^{k}a_{i}p_{i}(f)=0$ for any $f$ with $\deg f\leq n$ and

$\sum_{i=1}^{k}a_{i}\mathrm{Tr}(g^{i})=\sum_{i=1}^{k}a_{i}p_{i}(\det(I_{n}T-g))=0$
(1.2)

for all $g\in\mathrm{GL}_{n}(\mathbb{F}_{q})$. Finally, $k=\deg F\asymp q^{n}$
by the Prime Polynomial Theorem (see Lemma 3.1). If $k$ happens to be
divisible by $\mathrm{char}(\mathbb{F}_{q})$, we can replace $F$ by $TF$.

The question whether the range of Theorem 1.2 can be extended to $\log k\leq
c_{q}n$ for some constant $c_{q}>0$, for which we believe the answer is
negative, remains open and is not explored here.

For certain values of $k$, for example, primes, we can go beyond the range
$\log k=o(n^{2})$ of Theorem 1.1 using the following arithmetic criterion.

######  Theorem 1.3.

Let $g\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ be chosen uniformly at random. Let
$k=k(n)$ be a positive integer. Suppose

$\sum_{\begin{subarray}{c}12\log_{q}n<d\leq n\\\
\gcd(k,q^{d}-1)<q^{d/3}\end{subarray}}d^{-1}\to\infty$ (1.3)

as $n\to\infty$. Then, the distribution of $\mathrm{Tr}(g^{k})$ tends to the
uniform distribution on $\mathbb{F}_{q}$ as $n$ tends to $\infty$.

As we shall see later, Theorem 1.1 is a consequence of Theorem 1.3.

###  1.1 Comparison with random matrix theory

Our investigation was motivated by results in random matrix theory, although
we do not use any techniques from this area. Let $\text{U}_{n}(\mathbb{C})$ be
the group of $n\times n$ unitary matrices over complex numbers, endowed with
Haar measure of total mass 1. A classical result of Diaconis and Shahshahani
[9] states that for any $k\geq 1$, the vector
$X_{k}=(\mathrm{Tr}(U),\mathrm{Tr}(U^{2})/\sqrt{2},\ldots,\mathrm{Tr}(U^{k})/\sqrt{k})$
converges in distribution to $Y_{k}=(Z_{1},Z_{2},\ldots,Z_{k})$, where
$(Z_{j})_{j=1}^{k}$ are independent standard complex Gaussians. Johansson [18,
Thm. 2.6] showed that the rate of convergence of a linear combination of
$\mathrm{Tr}(U^{i})$ to a suitable Gaussian is superexponential in total
variation distance. In [19], Johansson and Lambert extended [18] to the total
variation distance of $X_{k}$ from $Y_{k}$ uniformly for $k\ll
n^{2/3-\varepsilon}$, and in [6], Courteaut and Johansson established similar
results for orthogonal and symplectic groups. In a recent work, Courteaut,
Johansson, and Lambert [7] studied the convergence of
$\mathrm{Tr}(U^{k})/\sqrt{k}$ to $Z_{k}$ as $k$ varies, obtaining, among other
results, that the distance goes to $0$ for any $k$ in the range $1\leq k<n$.
As for the complementary range, Rains [24] proved that there is a stabilizing
phenomenon once $k\geq n$: The eigenvalues of $U^{k}$ become distributed as
$n$ independent uniform random variables on the unit circle, and in particular
$\mathrm{Tr}(U^{k})/\sqrt{n}$ tends in distribution to the standard complex
Gaussian.

###  1.2 Symmetric function perspective

Let us also formulate a natural problem in symmetric functions that will turn
out to share strong similarities with the equidistribution of
$\mathrm{Tr}(g^{k})$. Let $e_{k}(t_{1},\ldots,t_{n})$ be the $k$th elementary
symmetric polynomial

$e_{k}(t_{1},\ldots,t_{n}):=\sum_{1\leq j_{1}<j_{2}<\cdots<j_{k}\leq
n}t_{j_{1}}t_{j_{2}}\cdots t_{j_{k}}$ (1.4)

and $p_{k}(t_{1},\ldots,t_{n})$ be the $k$th power sum symmetric polynomial

$p_{k}(t_{1},\ldots,t_{k}):=\sum_{i=1}^{n}t_{i}^{k}.$

Let $\mathbf{X}=(X_{i})_{i=1}^{n}$ be $n$ $\overline{\mathbb{F}_{q}}$-valued
random variables such that $e_{1}(\mathbf{X}),\ldots,e_{n}(\mathbf{X})$ are
independent and uniformly distributed on $\mathbb{F}_{q}$. By Newton’s
identities, $p_{k}(\mathbf{X})$ must also be $\mathbb{F}_{q}$-valued. We ask,
is $p_{k}(\mathbf{X})$ close to uniform?

Here is one way to construct such a sequence $\mathbf{X}$. Taking
$a_{1},\ldots,a_{n}$ to be independent uniform random variables on
$\mathbb{F}_{q}$, the polynomial
$T^{n}-a_{1}T^{n-1}+a_{2}T^{n-2}\mp\ldots+(-1)^{n}a_{n}$ is distributed
uniformly among $\mathcal{M}_{n,q}\subseteq\mathbb{F}_{q}[T]$, the subset of
monic polynomials of degree $n$. Setting $(X_{i})_{i=1}^{n}$ to be its $n$
roots in some order, we have that $e_{j}(\mathbf{X})=a_{j}$ satisfy the
conditions above, and $p_{i}(f)$ defined in (1.1) coincides with
$p_{i}(\mathbf{X})$. We prove the following.

######  Theorem 1.4.

Let $n\geq 1$. Let $k=k(n)$ be a positive integer. Suppose
$\mathbf{X}=(X_{i})_{i=1}^{n}$ are $n$ random variables such that
$(e_{1}(\mathbf{X}),\ldots,e_{n}(\mathbf{X}))$ has the uniform distribution on
$(\mathbb{F}_{q})^{n}$. Then:

  1. 1.

If $\log k=o(n^{2})$ then the distribution of $p_{k}(\mathbf{X})$ tends to the
uniform distribution on $\mathbb{F}_{q}$.

  2. 2.

Let $a_{1},\ldots,a_{k}\in\mathbb{F}_{q}$. If $\log k=o(n)$, $a_{k}\neq 0$ and
$\mathrm{char}(\mathbb{F}_{q})\nmid k$ then the distribution of
$\sum_{i=1}^{k}a_{i}p_{i}(\mathbf{X})$ tends to the uniform distribution on
$\mathbb{F}_{q}$.

  3. 3.

If the sum in (1.3) diverges then the distribution of $p_{k}(\mathbf{X})$
tends to the uniform distribution on $\mathbb{F}_{q}$.

Theorem 1.4 is about $p_{k}(f)$ when we choose $f$ uniformly at random from
$\mathcal{M}_{n,q}$, while Theorems 1.1–1.3 are about $p_{k}(f)$ for a
polynomial $f$ drawn from the space of possible characteristic polynomials of
a matrix from $\mathrm{GL}_{n}(\mathbb{F}_{q})$ endowed with the uniform
measure. As proved in [12, Thm. 1.4], the total variation distance of the law
of the first $k$ next-to-leading coefficients of $\det(I_{n}T-g)$ from the
uniform distribution on $\mathbb{F}_{q}^{k}$ tends to $0$ as $n\to\infty$ for
$k$ as large as $n-o(\log n)$, so the setup of Theorem 1.4 is not that
different from the setup of Theorems 1.1–1.3.

###  1.3 Cancellation in character sums of high conductor

Given $n\geq 0$ we denote by $\mathcal{M}_{n,q}\subseteq\mathbb{F}_{q}[T]$ the
subset of monic polynomials of degree $n$. We denote by
$\mathcal{M}_{q}=\cup_{n\geq 0}\mathcal{M}_{n,q}$ the set of monic polynomials
in $\mathbb{F}_{q}[T]$. We denote by
$\mathcal{P}_{n,q}\subseteq\mathcal{M}_{n,q}$ the set of irreducible
polynomials of degree $n$ and let $\mathcal{P}_{q}=\cup_{n\geq
0}\mathcal{P}_{n,q}$. Throughout, the letter $P$ is reserved for elements of
$\mathcal{P}_{q}$.

Given $k\geq 1$ and a nontrivial additive character
$\psi\colon\mathbb{F}_{q}\to\mathbb{C}$, we define a function
$\chi_{k,\psi}\colon\mathcal{M}_{q}\to\mathbb{C}$ by

$\chi_{k,\psi}(f):=\begin{cases}\psi(p_{-k}(f)),&\text{if $(f,T)=1$},\\\
0,&\text{otherwise.}\end{cases}$

######  Remark 1.1.

If $i$ is a negative integer, then $p_{i}(f)$, as defined in (1.1), is well
defined as long as $T\nmid f$. Moreover, the usual properties are preserved:
$p_{i}(fg)=p_{i}(f)+p_{i}(g)$ if $T\nmid fg$; if $f(T)=\deg(I_{n}T-g)$ then
$p_{i}(f)=\mathrm{Tr}(g^{i})$. When $T\nmid f$, $p_{i}(f)=p_{-i}(f(1/T)T^{\deg
f}/f(0))$, where $f(1/T)T^{\deg f}/f(0)$ is a monic polynomial, proving
$p_{i}(f)\in\mathbb{F}_{q}$ as well.

We show in Lemma 2.1 that the function $\chi_{k,\psi}$ is a primitive
Dirichlet character modulo $T^{k+1}$. The following theorem is the main
component behind the proof of Theorem 1.1.

######  Theorem 1.5.

We have, uniformly for $n\geq 1$ and $k\geq 1$,

$q^{-n}\sum_{f\in\mathcal{M}_{n,q}}\chi_{k,\psi}(f)\ll\frac{1+\log_{q}n+\sqrt{\log_{q}k}}{n}.$

In particular, we have cancellation when $\log k=o(n^{2})$ as $n\to\infty$.

Note that the range $\log k=o(n^{2})$ is optimal because for
$k=\prod_{i=1}^{n}(q^{i}-1)$ we have $\gamma^{-k}=1$ for every
$\gamma\in\cup_{i=1}^{n}\mathbb{F}_{q^{i}}^{\times}$ and thus $p_{-k}(f)\equiv
n$ on $\\{f\in\mathcal{M}_{n,q}:T\nmid f\\}$. Hence, there is no cancellation
for such $k$. We do not know if cancellation for $\log k=o(n^{2})$ persists if
we restrict to $\mathcal{P}_{n,q}$ instead of $\mathcal{M}_{n,q}$; the proof
of Theorem 1.5 relies on summing over all degree-$n$ polynomials.

It is instructive to compare Theorem 1.5 to results about character sums for
integers and polynomials. We switch temporarily to the integer setting. Let
$\chi$ be a nonprincipal Dirichlet character modulo $m$ and consider the sum
$S_{x,\chi}:=\sum_{n\leq x}\chi(n)$ as $x\to\infty$. Montgomery and Vaughan
[22, Lem. 2] proved under the generalized Riemann hypothesis for $L(s,\chi)$
that if $m\geq x$ and $y\in[(\log m)^{4},x]$ is a parameter, then

$S_{x,\chi}=\sum_{\begin{subarray}{c}n\leq x\\\ p\mid n\implies p\leq
y\end{subarray}}\chi(n)+O(xy^{-1/2}(\log m)^{4}).$ (1.5)

Recall $\sum_{n\leq x:\,p\mid n\implies p\leq y}1$ is $o(x)$ if $\log x/\log
y\to\infty$ [8, eq. (1.9)]. Taking $y=(\log m)^{9}$, we see that $S_{x,\chi}$
exhibits cancellation if $\log\log m=o(\log x)$. Granville and Soundararajan
improved the error term in (1.5) and also showed that this range is optimal
[13, Cor. A], in the sense that for any given $A>0$ and for any prime $m$,
there exists a nonprincipal character $\chi\bmod m$ with
$|S_{x,\chi}|\gg_{A}x$, where $x=\log^{A}m$.

Much less is known unconditionally. Burgess proved $S_{x,\chi}$ exhibits
cancellation when $m\leq x^{3-\varepsilon}$, and this can be extended to
$m\leq x^{4-\varepsilon}$ if $m$ is cubefree [4, 5]. When the conductor is
smooth, better results exist [17, Ch. 12]. In particular, if $m=p^{r}$, then
Banks and Shparlinski [1] showed one has cancellation in the range $\log
m=o((\log x)^{3/2})$ (if $r\geq C$ and $p\leq x^{c}$ for some absolute $C>0$
and $c>0$); this improved earlier work of Postnikov [17, Thm. 12.16]. It is
worthwhile to recall $\sum_{n\leq x}n^{it}$ exhibits cancellation when
$\log(|t|+2)=o((\log x)^{3/2})$, a result due to Vinogradov [17, Cor. 8.26].
The bound we prove for the sum of $f\mapsto\chi_{k,\psi}(f)$ also holds for
the function $f\mapsto\psi(p_{k}(f))$, which is an analogue of $n\mapsto
n^{it}$, see Remark 2.1 and [12, Lem. 2.2].

Now let us return to the polynomial setting. The generalized Riemann
hypothesis in $\mathbb{F}_{q}[T]$ is a seminal theorem due to A. Weil [28].
Let $\chi$ be a nonprincipal Dirichlet character modulo a polynomial
$Q\in\mathbb{F}_{q}[T]$. In [2, Thm. 3], Bhowmick and Lê adapted (1.5) to the
polynomial setting, proving unconditionally that

$\sum_{f\in\mathcal{M}_{n,q}}\chi(f)=\sum_{\begin{subarray}{c}f\in\mathcal{M}_{n,q}\\\
P\mid f\implies\deg P\leq m\end{subarray}}\chi(f)+O\left(q^{n-\frac{m}{2}}\deg
Q\right)$ (1.6)

holds for $m\in[2\log_{q}\deg Q,n]$. Taking $m=\lceil 4\log_{q}\deg Q\rceil$
shows that, as $n\to\infty$, $\sum_{f\in\mathcal{M}_{n,q}}\chi(f)$ exhibits
cancellation when $\log_{q}\deg Q=o(n)$. (For a self-contained bound on the
sum in the right-hand side of (1.6), see Lemma 3.5.)

The range $\log k=o(n^{2})$ in Theorem 1.5 is far beyond the ranges that the
generalized Riemann hypothesis implies, and heavily exploits a special
symmetry satisfied by $\chi_{k,\psi}$, which is shown in Lemma 3.8. We are not
aware of any other explicit family of characters, in either integers or
polynomials, where the generalized Riemann hypothesis implies cancellation
when the conductor exceeds the Montgomery–Vaughan range $\log\log m=o(\log x)$
in $\mathbb{Z}$ or $\log\deg Q=o(n)$ in $\mathbb{F}_{q}[T]$.

In §A we prove a new bound on general character sums in function fields which
is not used in the paper.

###  1.4 Structure of the paper

In Section 2, we discuss the connection between the distribution of traces and
character sums in more detail, and bound the total variation distance between
our respective distributions and the uniform distribution by corresponding
character sums. By doing so, we reduce Theorem 1.1 and the first part of
Theorem 1.4 to Theorem 1.5, and Theorem 1.2 and the second part of Theorem 1.4
to obtaining bounds for the character sum in (1.6). The latter is quite
straightforward as shown in Lemma 2.2, while the former requires more careful
treatment. We prove Theorem 1.5 in Section 3; we consider this to be the
technical part of the paper. We start with observing that there is underlying
symmetry in sums of $\chi_{k,\psi}$ against primes. To see this, in Lemma 3.8,
we prove

$\sum_{f\in\mathcal{M}_{n,q}}\Lambda(f)\chi_{k,\psi}(f)=\sum_{f\in\mathcal{M}_{n,q}}\Lambda(f)\chi_{k^{\prime},\psi}(f),$

where $\Lambda(f)$ is the function field von Mangoldt function, and
$k^{\prime}=\gcd(k,q^{n}-1)$. This identity allows us to improve the Weil
bound

$\bigg{|}\sum_{f\in\mathcal{M}_{n,q}}\Lambda(f)\chi_{k,\psi}(f)\bigg{|}\leq
q^{\frac{n}{2}}k$

to

$\bigg{|}\sum_{f\in\mathcal{M}_{n,q}}\Lambda(f)\chi_{k,\psi}(f)\bigg{|}\leq
q^{\frac{n}{2}}k^{\prime}=q^{\frac{n}{2}}\gcd(k,q^{n}-1)$ (1.7)

as shown in Corollary 3.9. This is helpful when $\gcd(k,q^{n}-1)$ is small.
Motivated by Montgomery and Vaughan [22, Lem. 2] given
$S\subseteq\\{1,\ldots,n\\}$, we write

$q^{-n}\sum_{f\in\mathcal{M}_{n,q}}\chi_{k,\psi}(f)=q^{-n}\sum_{\begin{subarray}{c}f\in\mathcal{M}_{n,q}\\\
P\mid f\implies\deg P\not\in
S\end{subarray}}\chi_{k,\psi}(f)+q^{-n}\sum_{\begin{subarray}{c}f\in\mathcal{M}_{n,q}\\\
\exists P\mid f\text{ such that }\deg P\in S\end{subarray}}\chi_{k,\psi}(f).$
(1.8)

In our case, choosing

$S=\\{\lceil 12\log_{q}n\rceil\leq d\leq n:\gcd(k,q^{d}-1)<q^{d/3}\\}$

allows us to bound the second sum on the right-hand side of (1.8) using (1.7)
(see Lemma 3.4) while a sieve bound (Lemma 3.5) bounds the first sum on the
right-hand side of (1.8). This strategy ends up proving the following
criterion.

######  Proposition 1.6.

Let $n\geq 1$ and $k\geq 1$. Let
$\psi\colon\mathbb{F}_{q}\to\mathbb{C}^{\times}$ be a nontrivial additive
character. We have

$q^{-n}\sum_{f\in\mathcal{M}_{n,q}}\chi_{k,\psi}(f)\ll
n^{-1}+\exp\bigg{(}-\sum_{\begin{subarray}{c}12\log_{q}n<d\leq n\\\
\gcd(k,q^{d}-1)<q^{d/3}\end{subarray}}d^{-1}\bigg{)}.$ (1.9)

In particular, a sufficient criterion for cancellation is that the sum in
(1.3) diverges as $n\to\infty$.

In Section 2, we reduce Theorem 1.3 and the third part of Theorem 1.4 to
Proposition 1.6. To deduce Theorem 1.5 from Proposition 1.6, we prove a sharp
upper bound on $\sum_{L<d\leq 2L}\log\gcd(k,q^{d}-1)$ in Lemma 3.6, that may
be of independent interest.

The criterion above is particularly interesting because it allows us to
exhibit cancellation on the left-hand side of (1.9) for arbitrarily large $k$,
for example, whenever $k$ is a prime, or a product of a bounded number of
primes, the sum in (1.3) diverges simply because the following shorter sum
does:

$\sum_{\begin{subarray}{c}12\log_{q}n<d\leq n\\\
\gcd(k,q^{d}-1)=1\end{subarray}}d^{-1}.$

######  Remark 1.2.

Proposition 1.6, and hence Theorem 1.5, apply as is to
$\sum_{f\in\mathcal{M}_{n,q}}\mu(f)\chi_{k,\psi}(f)$ where $\mu$ is the Möbius
function, see Remark 3.3. Recall $\mu$ is multiplicative with $\mu(P)=-1$ and
$\mu(P^{e})=0$ for $e\geq 2$. However, we do not know that $\log k=o(n^{2})$
is optimal in this case.

######  Remark 1.3.

For every $\varepsilon>0$, there are examples where $\log k\sim\varepsilon
n^{2}$ for which Proposition 1.6 does not yield cancellation, for example,
$k=\prod_{i=1}^{\lfloor\varepsilon^{\prime}n\rfloor}(q^{i}-1)$ where taking
logarithm shows $\varepsilon^{\prime}>0$ is defined via
$\varepsilon=\varepsilon^{\prime 2}(\log q)/2$.

######  Remark 1.4.

It is natural to ask whether analogues of Theorems 1.1 and 1.2 hold for other
groups. Consider for instance $\mathrm{U}(n,q)$, the unitary group over
$\mathbb{F}_{q^{2}}$. Then, as in Section 2, we are led to consider the sums
$\sum_{f\in\mathcal{M}_{n,q^{2}}}\mathrm{P}_{\mathrm{U}}(f)\chi(f)$ where
$\mathrm{P}_{\mathrm{U}}(f):=\mathbb{P}_{g\in\mathrm{U}(n,q)}(\det(I_{n}T-g)=f)$
is a function studied in [12, §5] and $\chi$ is a Dirichlet character
depending on $k$ (if we are in the situation of Theorem 1.1) or on
$a_{1},\ldots,a_{k}$ (if we are in the situation of Theorem 1.2). The support
of $\mathrm{P}_{\mathrm{U}}$ is restricted since the characteristic polynomial
of any matrix from $\mathrm{U}(n,q)$ is unitary self-reciprocal, that is, it
belongs to

$\mathcal{M}_{n,q^{2}}^{usr}:=\left\\{f\in\mathcal{M}_{n,q^{2}}:f(0)\neq
0,\,f(T)=T^{\deg
f}\frac{\sigma(f(1/T))}{\sigma(f(0))}\right\\},\qquad\sigma\big{(}\sum
c_{i}T^{i}\big{)}:=\sum c_{i}^{q}T^{i}.$

Using the strategy in Section 2 together with [12, Thm. 5.10], the problem
ultimately reduces to bounding character sums over
$\mathcal{M}_{n,q^{2}}^{usr}$,
$\sum_{f\in\mathcal{M}_{n,q^{2}}^{usr}}\chi(f)$. We expect that it is possible
to adapt our proofs to bound such sums with additional work, although various
complications arise, and this problem deserves further study. For a review of
character sums over such sets, we refer the reader to [12, §5].

##  2 Reductions

###  2.1 An involution

Given $f\in\mathcal{M}_{q}$ we use the notation $p_{i}(f)$ introduced in
(1.1). Given $a_{1},\ldots,a_{k}\in\mathbb{F}_{q}$ and an additive character
$\psi\colon\mathbb{F}_{q}\to\mathbb{C}^{\times}$, define a function
$\xi_{\mathbf{a},\psi}\colon\mathcal{M}_{q}\to\mathbb{C}$ by

$\xi_{\mathbf{a},\psi}(f):=\psi\bigg{(}\sum_{i=1}^{k}p_{i}(f)a_{i}\bigg{)}.$

The function $\xi_{\mathbf{a},\psi}$, sometimes called a short interval
character, is closely related to a certain Dirichlet character modulo
$T^{k+1}$ as observed by Hayes [16, pp. 115–116] and Keating and Rudnick [21,
§4.1][20, p. 389]. Let us explain this idea. We let
$\mathcal{M}^{gl}_{q}:=\\{f\in\mathcal{M}_{q}:(f,T)=1\\}$ (this notation,
borrowed from [12, §3.1], is motivated by the fact that the characteristic
polynomial of any matrix from $\cup_{n\geq 0}\mathrm{GL}_{n}(\mathbb{F}_{q})$
lies in $\mathcal{M}^{gl}_{q}$). We define an involution $\iota$ on
$\mathcal{M}^{gl}_{q}$ by

$\iota(f):=f(1/T)T^{\deg f}/f(0).$

If we factorize $f\in\mathcal{M}^{gl}_{q}$ as $f(T)=\prod_{j=1}^{\deg
f}(T-\lambda_{j})$ over $\overline{\mathbb{F}_{q}}$, we find that

$\iota(f)=\prod_{j=1}^{\deg f}(T-\lambda_{j}^{-1})$

so $p_{k}(f)=p_{-k}(\iota(f))$ (see Remark 1.1 for the definition of
$p_{-k}$). For any function $\alpha\colon\mathcal{M}_{q}\to\mathbb{C}$, we
define $\iota_{\alpha}\colon\mathcal{M}_{q}\to\mathbb{C}$ by

$\iota_{\alpha}(f):=\begin{cases}\alpha(\iota(f))&\text{if
}f\in\mathcal{M}^{gl}_{q},\\\ 0&\text{if
}f\not\in\mathcal{M}^{gl}_{q}.\end{cases}$

We say that a function $\alpha\colon\mathcal{M}_{q}\to\mathbb{C}$ is
completely multiplicative if $\alpha(fg)=\alpha(f)\alpha(g)$ holds for all
$f,g\in\mathcal{M}_{q}$ and $\alpha(1)=1$. If $\alpha$ is completely
multiplicative, then so is $\iota_{\alpha}$ because $\iota$ is (when extended
to $\mathcal{M}_{q}$ via $\iota(T)=0$). Given an arithmetic function
$\alpha\colon\mathcal{M}_{q}\to\mathbb{C}$, we use the notation

$S(n,\alpha):=\sum_{f\in\mathcal{M}_{n,q}}\alpha(f).$

Letting

$\chi_{0}(f):=\mathbf{1}_{T\nmid f},$

we have

$\displaystyle S(n,\alpha\cdot\chi_{0})=S(n,\iota_{\alpha})$ (2.1)

and, since
$S(n,\alpha\cdot\chi_{0})=S(n,\alpha)-\alpha(T)S(n-1,\alpha)\mathbf{1}_{n\geq
1}$ holds for completely multiplicative $\alpha$,

$\displaystyle
S(n,\alpha)=\sum_{i=0}^{n}S(i,\alpha\cdot\chi_{0})\alpha(T)^{n-i}=\sum_{i=0}^{n}S(i,\iota_{\alpha})\alpha(T)^{n-i}.$
(2.2)

A variant of the following lemma was established in [12, Lem. 2.2].

######  Lemma 2.1.

Let $a_{1},\ldots,a_{k}\in\mathbb{F}_{q}$ with $a_{k}\neq 0$ and
$\mathrm{char}(\mathbb{F}_{q})\nmid k$. Let
$\psi\colon\mathbb{F}_{q}\to\mathbb{C}^{\times}$ be a nontrivial additive
character, and let $\alpha=\xi_{\mathbf{a},\psi}$. Then, $\iota_{\alpha}$ is a
primitive Dirichlet character modulo $T^{k+1}$.

###### Proof.

We know $\iota_{\alpha}$ is completely multiplicative, vanishes at multiples
of $T$ and $\iota_{\alpha}(1)=1$. It remains to show that it only depends on
the residue of the input modulo $T^{k+1}$ and that it is primitive. Newton’s
identities yield that $p_{i}(f)$ is a function of the $i$ first next-to-
leading coefficients of $f$, where the $j$th ($j\geq 1$) next-to-leading
coefficient of $T^{n}+\sum_{i=0}^{n-1}a_{i}T^{i}$ is defined to be $a_{n-j}$
if $j\leq n$ and to be $0$ otherwise. Hence, $\alpha=\xi_{\mathbf{a},\psi}(f)$
only depends on the $k$ first next-to-leading coefficients of $f$. Since by
definition $\iota(f)$ reverses the coefficients of $f$ and normalizes by
$f(0)$, it follows that $\iota_{\alpha}(f)$ depends only on the last $k+1$
coefficients of $f$, that is, on $f\bmod T^{k+1}$. Finally,
$\iota_{\alpha}(T^{k+1}-c)=1$ for every $c\in\mathbb{F}_{q}^{\times}$ while a
short computation using Newton’s identities shows
$\iota_{\alpha}(T^{k}-c)=\psi(ka_{k}/c)$ is not equal to $1$ for suitable $c$.
∎

For $k\geq 1$ and an additive character
$\psi\colon\mathbb{F}_{q}\to\mathbb{C}$, with a slight abuse of notation, let

$\displaystyle\xi_{k,\psi}(f)$ $\displaystyle:=\psi(p_{k}(f)),$ (2.3)

which coincides with $\xi_{\mathbf{a},\psi}$ for $a_{1}=\ldots=a_{k-1}=0$,
$a_{k}=1$. By definition, we have

$\chi_{k,\psi}=\iota_{\xi_{k,\psi}}=\iota_{\xi_{k,\psi}\cdot\chi_{0}}.$

######  Remark 2.1.

We have $S(n,\xi_{k,\psi})=\sum_{i=0}^{n}S(i,\chi_{k,\psi})$ by (2.2). In
particular, $q^{-n}S(n,\chi_{k,\psi})\ll(1+\log_{q}n+\sqrt{\log_{q}k})/n$
implies $q^{-n}S(n,\xi_{k,\psi})\ll(1+\log_{q}n+\sqrt{\log_{q}k})/n$ and vice
versa.

###  2.2 Reduction of Theorem 1.4 to character sum estimates

Recall that $\mathbf{X}=(X_{i})_{i=1}^{n}\in\overline{\mathbb{F}_{q}}^{n}$ are
$n$ random variables such that $e_{1}(\mathbf{X}),\ldots,e_{n}(\mathbf{X})$
are independent and uniformly distributed on $\mathbb{F}_{q}$, and that one
can take $X_{i}$ to be the zeros of a polynomial $f$ chosen uniformly at
random from $\mathcal{M}_{n,q}$.

Let $a_{1},\ldots,a_{k}\in\mathbb{F}_{q}$ and denote by
$\widehat{\mathbb{F}_{q}}$ the group of $q$ additive characters from
$\mathbb{F}_{q}$ to $\mathbb{C}^{\times}$, with $\psi_{0}$ denoting the
trivial character. By Fourier analysis on $\mathbb{F}_{q}$, given
$x\in\mathbb{F}_{q}$,

$\mathbb{P}(\sum_{i=1}^{k}a_{i}p_{i}(\mathbf{X})=x)=\mathbb{P}_{f\in\mathcal{M}_{n,q}}(\sum_{i=1}^{k}a_{i}p_{i}(f)=x)\\\
=q^{-1}\sum_{\psi\in\widehat{\mathbb{F}_{q}}}\overline{\psi}(x)\mathbb{E}_{f\in\mathcal{M}_{n,q}}\psi(\sum_{i=1}^{k}a_{i}p_{i}(f))=q^{-1}\sum_{\psi\in\widehat{\mathbb{F}_{q}}}q^{-n}\overline{\psi}(x)S(n,\xi_{\mathbf{a},\psi}).$
(2.4)

Since $S(n,\xi_{\mathbf{a},\psi_{0}})=q^{n}$, the triangle inequality implies

$\sum_{x\in\mathbb{F}_{q}}\big{|}\mathbb{P}(\sum_{i=1}^{k}a_{i}p_{i}(\mathbf{X})=x)-q^{-1}\big{|}\leq\sum_{\psi_{0}\neq\psi\in\widehat{\mathbb{F}_{q}}}|q^{-n}S(n,\xi_{\mathbf{a},\psi})|.$
(2.5)

By (2.5), (2.2), and the triangle inequality,

$\sum_{x\in\mathbb{F}_{q}}\big{|}\mathbb{P}(\sum_{i=1}^{k}a_{i}p_{i}(\mathbf{X})=x)-q^{-1}\big{|}\leq\sum_{j=0}^{n}q^{j-n}\sum_{\psi_{0}\neq\psi\in\widehat{\mathbb{F}_{q}}}|q^{-j}S(j,\iota_{\xi_{\mathbf{a},\psi}})|.$
(2.6)

A special case of (2.6) is

$\sum_{x\in\mathbb{F}_{q}}\big{|}\mathbb{P}(p_{k}(\mathbf{X})=x)-q^{-1}\big{|}\leq\sum_{j=0}^{n}q^{j-n}\sum_{\psi_{0}\neq\psi\in\widehat{\mathbb{F}_{q}}}|q^{-j}S(j,\chi_{k,\psi})|.$
(2.7)

The first part of Theorem 1.4 is immediate from (2.7) and Theorem 1.5. The
third part follows from (2.7) and Proposition 1.6. For the second part of
Theorem 1.4, we use (2.6) and observe $\iota_{\xi_{\mathbf{a},\psi}}$ is a
nonprincipal Dirichlet character modulo $T^{k+1}$ by Lemma 2.1, and the result
follows from applying the following lemma.

######  Lemma 2.2 (Bhowmick–Lê).

Let $\chi\colon\mathcal{M}_{q}\to\mathbb{C}$ be a nonprincipal Dirichlet
character modulo $Q$. We have

$q^{-n}S(n,\chi)\ll\frac{1+\log_{q}(1+\deg Q)}{n+1}.$

Lemma 2.2 follows from (1.6) with $m=\lceil 2\log_{q}(n(1+\deg Q))\rceil$ (see
Section 3.3 for details).

###  2.3 Reductions of Theorems 1.1–1.3 to character sum estimates

We define an arithmetic function
$\mathrm{P}_{\mathrm{GL}}\colon\mathcal{M}_{q}\to\mathbb{C}$ as follows. If
$f\in\mathcal{M}_{q}$ and $n=\deg f$, then

$\mathrm{P}_{\mathrm{GL}}(f):=\mathbb{P}_{g\in\mathrm{GL}_{n}(\mathbb{F}_{q})}(\det(I_{n}T-g)=f),$
(2.8)

where $\mathrm{GL}_{n}(\mathbb{F}_{q})$ is endowed with the uniform measure.
It follows from the work of Reiner [25] and Gerstenhaber [11] that
$\mathrm{P}_{\mathrm{GL}}$ is multiplicative (in the sense that
$\mathrm{P}_{\mathrm{GL}}(fg)=\mathrm{P}_{\mathrm{GL}}(f)\mathrm{P}_{\mathrm{GL}}(g)$
when $\gcd(f,g)=1$) and supported on $\mathcal{M}^{gl}_{q}$. Their works also
show that on prime powers it is given by $\mathrm{P}_{\mathrm{GL}}(T^{e})=0$
and

$\mathrm{P}_{\mathrm{GL}}(P^{e})=q^{-e\deg P}\prod_{i=1}^{e}(1-q^{-i\deg
P})^{-1},$ (2.9)

where $P\in\mathcal{P}_{q}\setminus\\{T\\}$ and $e\geq 1$ (cf. [12, Thm.
3.3]). The following identity is a quick consequence of (2.9) (it can also be
derived directly from [12, Thm. 3.4]). Recall $|f|=q^{\deg f}$.

######  Lemma 2.3.

We have $\mathrm{P}_{\mathrm{GL}}=\alpha_{1}*\alpha_{2}$ where
$\alpha_{1}(f)=|f|^{-1}\cdot\mathbf{1}_{T\nmid f}$ and
$\alpha_{2}(f)=\mathrm{P}_{\mathrm{GL}}(f)/|f|$.

Let $a_{1},\ldots,a_{k}\in\mathbb{F}_{q}$. By Fourier analysis on
$\mathbb{F}_{q}$, given $x\in\mathbb{F}_{q}$, we have

$\mathbb{P}_{g\in\mathrm{GL}_{n}(\mathbb{F}_{q})}\big{(}\sum_{i=1}^{k}a_{i}\mathrm{Tr}(g^{i})=x\big{)}=q^{-1}\sum_{\psi\in\widehat{\mathbb{F}_{q}}}\mathbb{E}_{g\in\mathrm{GL}_{n}(\mathbb{F}_{q})}\overline{\psi}(x)\psi(\sum_{i=1}^{k}a_{i}\mathrm{Tr}(g^{i})).$

The trivial character $\psi_{0}$ contributes $1/q$ to the right-hand side.
Recall $p_{k}(f)$ ($f\in\mathcal{M}_{q}$) is defined in (1.1). Since
$p_{i}(\deg(I_{n}T-g))=\mathrm{Tr}(g^{i})$,

$\mathbb{P}_{g\in\mathrm{GL}_{n}(\mathbb{F}_{q})}\big{(}\sum_{i=1}^{k}a_{i}\mathrm{Tr}(g^{i})=x\big{)}-q^{-1}=q^{-1}\sum_{\psi_{0}\neq\psi\in\widehat{\mathbb{F}_{q}}}\overline{\psi}(x)\sum_{f\in\mathcal{M}_{n,q}}\mathrm{P}_{\mathrm{GL}}(f)\xi_{\mathbf{a},\psi}(f).$

Summing over $x$ and using the triangle inequality gives

$\sum_{x\in\mathbb{F}_{q}}\big{|}\mathbb{P}_{g\in\mathrm{GL}_{n}(\mathbb{F}_{q})}\big{(}\sum_{i=1}^{k}a_{i}\mathrm{Tr}(g^{i})=x\big{)}-q^{-1}\big{|}\leq\sum_{\psi_{0}\neq\psi\in\widehat{\mathbb{F}_{q}}}|S(n,\mathrm{P}_{\mathrm{GL}}\cdot\xi_{\mathbf{a},\psi})|.$
(2.10)

In [12, Thm. 3.6], the first author and Rodgers showed that

$|S(n,\mathrm{P}_{\mathrm{GL}}\cdot\xi_{\mathbf{a},\psi})|\leq
q^{-\frac{n^{2}}{2k}+O_{q}(n)}.$ (2.11)

For fixed $k$ this is essentially optimal up to constants, because
$|S(n,\mathrm{P}_{\mathrm{GL}}\cdot\xi_{\mathbf{a},\psi})|$ cannot decay
faster than exponentially in $n^{2}$ due to
$|\mathrm{GL}_{n}(\mathbb{F}_{q})|=q^{\Theta(n^{2})}$. In this paper, we focus
on the range of cancellation rather than the rate of cancellation, and in this
aspect, we can do better. Observe that from Lemma 2.3,

$S(n,\mathrm{P}_{\mathrm{GL}}\cdot\xi_{\mathbf{a},\psi})=q^{-n}\sum_{i+j=n}\sum_{f\in\mathcal{M}_{i,q},\,T\nmid
f}\xi_{\mathbf{a},\psi}(f)\sum_{g\in\mathcal{M}_{j,q}}\mathrm{P}_{\mathrm{GL}}(g)\xi_{\mathbf{a},\psi}(g).$

Since $\mathrm{P}_{\mathrm{GL}}$ is a probability measure on
$\mathcal{M}_{j,q}$, the triangle inequality yields

$|S(n,\mathrm{P}_{\mathrm{GL}}\cdot\xi_{\mathbf{a},\psi})|\leq
q^{-n}\sum_{i=0}^{n}|S(i,\xi_{\mathbf{a},\psi}\cdot\chi_{0})|.$ (2.12)

From (2.12), (2.10), and (2.1),

$\sum_{x\in\mathbb{F}_{q}}\big{|}\mathbb{P}_{g\in\mathrm{GL}_{n}(\mathbb{F}_{q})}\big{(}\sum_{i=1}^{k}a_{i}\mathrm{Tr}(g^{i})=x\big{)}-q^{-1}\big{|}\leq
q^{-n}\sum_{\psi_{0}\neq\psi\in\widehat{\mathbb{F}_{q}}}\sum_{i=0}^{n}|S(i,\iota_{\xi_{\mathbf{a},\psi}})|.$
(2.13)

Similarly to the symmetric function case, we see that Theorem 1.2 follows from
(2.13) and Lemma 2.2.

In the special case $a_{1}=\ldots=a_{k-1}$ and $a_{k}=1$, we have

$\sum_{x\in\mathbb{F}_{q}}\big{|}\mathbb{P}_{g\in\mathrm{GL}_{n}(\mathbb{F}_{q})}\big{(}\mathrm{Tr}(g^{k})=x\big{)}-q^{-1}\big{|}\leq
q^{-n}\sum_{\psi_{0}\neq\psi\in\widehat{\mathbb{F}_{q}}}\sum_{i=0}^{n}|S(i,\chi_{k,\psi})|.$
(2.14)

Theorem 1.1 follows from (2.14) and Theorem 1.5. Theorem 1.3 follows from
(2.14) and Proposition 1.6.

##  3 Proof of Theorem 1.5

The von Mangoldt function $\Lambda\colon\mathcal{M}_{q}\to\mathbb{C}$ is
defined as

$\Lambda(f)=\begin{cases}\deg P&\text{if }f=P^{k},P\in\mathcal{P}_{q},\,k\geq
1,\\\ 0&\text{otherwise.}\end{cases}$ (3.1)

Gauss’ identity [27, Thm. 2.2] states that

$\sum_{f\in\mathcal{M}_{n,q}}\Lambda(f)=\sum_{d\mid
n}|\mathcal{P}_{d,q}|d=q^{n},$ (3.2)

and is known to imply the following.

######  Lemma 3.1.

[23, Lem. 4] We have $q^{n}/n-2q^{n/2}/n\leq|\mathcal{P}_{n,q}|\leq q^{n}/n$
for $n\geq 1$.

Given a Dirichlet character $\chi$ its $L$-function is defined as

$L(u,\chi)=\sum_{f\in\mathcal{M}_{q}}\chi(f)u^{\deg
f}=\prod_{P\in\mathcal{P}_{q}}(1-\chi(P)u^{\deg P})^{-1},$ (3.3)

which converges absolutely for $|u|<1/q$. If $\chi$ is a nonprincipal
character modulo $Q$, then $L(u,\chi)$ is a polynomial of degree at most $\deg
Q-1$ as follows from the orthogonality relations for $\chi$. We set

$d(\chi):=\deg L(u,\chi)<\deg Q.$

######  Theorem 3.2 (Weil’s RH [28]).

Let $\chi$ be a nonprincipal Dirichlet character. Factoring $L(u,\chi)$ as

$L(u,\chi)=\prod_{i=1}^{d(\chi)}(1-\gamma_{i}u),$ (3.4)

we have $|\gamma_{i}|\in\\{1,\sqrt{q}\\}$ for all $1\leq i\leq d(\chi)$.

######  Lemma 3.3.

Let $\chi$ be a nonprincipal Dirichlet character, then

$\displaystyle\bigg{|}\sum_{f\in\mathcal{M}_{n,q}}\chi(f)\Lambda(f)\bigg{|}\leq
q^{\frac{n}{2}}d(\chi).$ (3.5)

###### Proof.

We take the logarithmic derivative of the Euler product (3.3) and (3.4) and
compare coefficients to obtain

$\sum_{f\in\mathcal{M}_{n,q}}\chi(f)\Lambda(f)=-\sum_{i=1}^{d(\chi)}\gamma_{i}^{n}$
(3.6)

for all $n\geq 1$. Then, Theorem 3.2 implies the lemma via the triangle
inequality. ∎

Let $\alpha\colon\mathcal{M}_{q}\to\mathbb{C}$ be a completely multiplicative
function. Given any subset $T$ of the positive integers $\mathbb{N}$, we
define

$F_{T}(u,\alpha):=\sum_{\begin{subarray}{c}f\in\mathcal{M}_{q}\\\ P\mid
f\implies\deg P\in T\end{subarray}}\alpha(f)u^{\deg
f}=\prod_{P\in\mathcal{P}_{q},\,\deg P\in T}(1-\alpha(P)u^{\deg P})^{-1}.$

Let us write $[u^{m}]F$ for the $m$th coefficient of a power series $F$. Our
starting point is the identity

$\begin{split}\sum_{f\in\mathcal{M}_{n,q}}\alpha(f)&=[u^{n}]F_{\mathbb{N}}(u,\alpha)=[u^{n}]F_{T^{c}}(u,\alpha)F_{T}(u,\alpha)\\\
&=[u^{n}]F_{T^{c}}(u,\alpha)+[u^{n}]F_{T^{c}}(u,\alpha)(F_{T}(u,\alpha)-1)\\\
&=q^{-n}\sum_{\begin{subarray}{c}f\in\mathcal{M}_{n,q}\\\ P\mid f\implies\deg
P\not\in
T\end{subarray}}\alpha(f)+q^{-n}\sum_{\begin{subarray}{c}f\in\mathcal{M}_{n,q}\\\
\exists P\mid f\text{ such that }\deg P\in
T\end{subarray}}\alpha(f),\end{split}$ (3.7)

where $T^{c}=\mathbb{N}\setminus T$ is the complement of $T$.

###  3.1 Montgomery and Vaughan’s estimate

To bound the second term in (3.7), we prove the following lemma generalizing
an estimate of Montgomery and Vaughan [22, Lem. 2] in the polynomial setting.

######  Lemma 3.4.

Let $\alpha\colon\mathcal{M}_{q}\to\mathbb{C}$ be a $1$-bounded completely
multiplicative function, meaning $|\alpha(f)|\leq 1$ for all
$f\in\mathcal{M}_{q}$. Let $n\geq 1$ and $S\subseteq\\{1,\ldots,n\\}$ be a set
of positive integers, and $S^{c}=\\{1,\ldots,n\\}\setminus S$ be its
complement. Let $s_{0}=\min_{s\in S}s$. Then,

$q^{-n}\sum_{\begin{subarray}{c}f\in\mathcal{M}_{n,q}\\\ \exists P\mid f\text{
such that }\deg P\in S\end{subarray}}\alpha(f)\ll\exp(A_{1})(\exp(A_{2})-1),$

where

$A_{1}=\sum_{d\in S^{c}}\frac{1}{d},\qquad A_{2}=\sum_{d\in
S}\frac{q^{-d}}{d}\bigg{|}\sum_{f\in\mathcal{M}_{d,q}}\alpha(f)\Lambda(f)\bigg{|}+O(q^{-\frac{s_{0}}{2}}/s_{0}).$

######  Remark 3.1.

In [2] Lemma 3.4 is proved in the special case $S=\\{m+1,m+2,m+3,\ldots,n\\}$
and $\alpha$ being a Dirichlet character. For this choice, one immediately
recovers (1.6) from (3.5).

###### Proof.

Using identity (3.7) and noticing that we can restrict the set of degrees to
$\\{1,\ldots,n\\}$, we have

$X:=q^{-n}\sum_{\begin{subarray}{c}f\in\mathcal{M}_{n,q}\\\ \exists P\mid
f\text{ such that }\deg P\in
S\end{subarray}}\alpha(f)=[u^{n}]F_{S^{c}}(u,\alpha)(F_{S}(u,\alpha)-1).$

Because $\alpha$ is $1$-bounded, the coefficients in the series of
$F_{S^{c}}(u,\alpha)$ are bounded in absolute value by the respective
coefficients of

$Z_{S^{c}}(u):=\sum_{\begin{subarray}{c}f\in\mathcal{M}_{q}\\\ P\mid
f\implies\deg P\in S^{c}\end{subarray}}u^{\deg
f}=\prod_{P\in\mathcal{P}_{q},\,\deg P\in S^{c}}(1-u^{\deg P})^{-1}.$

Further, we may write $F_{S}(u,\alpha)$ as

$\displaystyle F_{S}(u,\alpha)$
$\displaystyle=\prod_{P\in\mathcal{P}_{q},\,\deg P\in S}(1-\alpha(P)u^{\deg
P})^{-1}=\exp\left(\sum_{d\in S}\sum_{i\geq
1}i^{-1}u^{di}\sum_{P\in\mathcal{P}_{d,q}}\alpha(P)^{i}\right)$ (3.8)
$\displaystyle=\exp\left(\sum_{d\in
S}u^{d}\sum_{P\in\mathcal{P}_{d,q}}\alpha(P)+\sum_{d\in S}\sum_{i\geq
2}i^{-1}u^{di}\sum_{P\in\mathcal{P}_{d,q}}\alpha(P)^{i}\right)$ (3.9)
$\displaystyle=\exp\left(\sum_{d\in
S}\frac{u^{d}}{d}\sum_{f\in\mathcal{M}_{d,q}}\alpha(f)\Lambda(f)+\sum_{d\in
S}\sum_{i\geq
2}\frac{u^{di}}{i}\sum_{P\in\mathcal{P}_{d,q}}\alpha(P)^{i}-\sum_{d\in
S}\frac{u^{d}}{d}\sum_{\begin{subarray}{c}e\mid d\\\ e\neq
d\end{subarray}}e\sum_{P\in\mathcal{P}_{e,q}}\alpha(P)^{d/e}\right).$ (3.10)

It follows that $[u^{j}](F_{S}(u,\alpha)-1)$ for $0\leq j\leq n$ are bounded
in absolute value by the coefficients of $u^{j}$ in

$Z_{S,\alpha}(u):=\exp\left(\sum_{d\in
S}\frac{u^{d}}{d}\bigg{|}\sum_{f\in\mathcal{M}_{d,q}}\alpha(f)\Lambda(f)\bigg{|}+\sum_{d\in
S}\sum_{i\geq 2}\frac{u^{di}}{i}|\mathcal{P}_{d,q}|+\sum_{d\in
S}\frac{u^{d}}{d}\sum_{\begin{subarray}{c}e\mid d\\\ e\neq
d\end{subarray}}e|\mathcal{P}_{e,q}|\right)-1.$ (3.11)

Putting this together, we have

$|X|=\big{|}[u^{n}]F_{S^{c}}(u,\alpha)(F_{S}(u,\alpha)-1)\big{|}\leq[u^{n}]Z_{S^{c}}(u)(Z_{S,\alpha}(u)-1).$

We make a general observation. If the coefficients of a power series
$F(u)=\sum_{i\geq 0}f_{i}u^{i}$ are bounded in absolute value by the
respective coefficients of $G(u)=\sum_{i\geq 0}g_{i}u^{i}$, then $|f_{n}|\leq
G(R)R^{-n}$ for every $0<R<C$ such that $G(R)$ converges. Indeed,

$G(R)R^{-n}=\sum_{i=0}^{\infty}g_{i}R^{i-n}\geq
g_{n}R^{n-n}=g_{n}\geq|f_{n}|.$

Applying this observation with $R=1/q$, we get

$|X|\leq q^{n}Z_{S^{c}}(1/q)(Z_{S,\alpha}(1/q)-1).$ (3.12)

We estimate $Z_{S^{c}}(1/q)$ using Lemma 3.1 as

$Z_{S^{c}}(1/q)=\exp\left(\sum_{\deg P\in S^{c}}(q^{-\deg P}+O(q^{-2\deg
P}))\right)=\exp\left(\sum_{d\in S^{c}}d^{-1}+O(1)\right).$ (3.13)

Similarly,

$\sum_{d\in S}\sum_{i\geq 2}\frac{q^{-di}}{i}|\mathcal{P}_{d,q}|+\sum_{d\in
S}\frac{q^{-d}}{d}\sum_{\begin{subarray}{c}e\mid d\\\ e\neq
d\end{subarray}}e|\mathcal{P}_{e,q}|\leq\sum_{d\in S}\sum_{i\geq
2}\frac{q^{-di}}{i}\frac{q^{d}}{d}+2\sum_{d\in
S}\frac{q^{-\frac{d}{2}}}{d}\ll\frac{q^{-s_{0}/2}}{s_{0}},$ (3.14)

where $s_{0}=\min_{s\in S}s$. The required estimate then follows from (3.12),
(3.13), (3.11), and (3.14). ∎

We now move on to estimating the first term in (3.7).

###  3.2 Sieve estimate

######  Lemma 3.5 (Sieve bound).

Let $S\subseteq\\{1,\ldots,n\\}$ be a set of positive integers, and
$S^{c}=\\{1,\ldots,n\\}\setminus S$ be its complement. Then

$\sum_{\begin{subarray}{c}f\in\mathcal{M}_{n,q}\\\ P\mid f\implies\deg
P\not\in S\end{subarray}}1\ll\frac{q^{n}}{n}\exp\left(\sum_{d\in
S^{c}}d^{-1}\right)\asymp q^{n}\exp\left(-\sum_{d\in S}d^{-1}\right).$

######  Remark 3.2.

In the integer setting, the estimate $\sum_{n\leq x:\,(n,k)=1}1\ll
x\prod_{p\mid k}(1-1/p)$ for any positive integer $k$ whose prime factors do
not exceed $x$ is a classical consequence of Selberg’s sieve (see [15] for a
discussion of this and an alternative proof). A permutation analogue of Lemma
3.5 was established (in greater generality) by Ford [10, Thm. 1.5]. The proof
we give is self-contained and is in the spirit of [15, 14, 10].

###### Proof.

Let

$A_{i}:=\sum_{\begin{subarray}{c}f\in\mathcal{M}_{i,q}\\\ P\mid f\implies\deg
P\not\in S\end{subarray}}1,$

and define

$F(u):=\prod_{\deg P\in S^{c}}(1-u^{\deg P})^{-1}=\exp\left(\sum_{\deg P\in
S^{c}}\sum_{k\geq 1}\frac{u^{k\deg
P}}{k}\right)=:\sum_{i=0}^{\infty}\widetilde{A}_{i}u^{i}.$ (3.15)

The coefficients satisfy $\widetilde{A}_{i}=A_{i}$ for $0\leq i\leq n$.
Differentiating (3.15) formally, we see that

$\sum_{i\geq 1}i\widetilde{A}_{i}u^{i}=F(u)G(u),$ (3.16)

where

$G(u)=\sum_{i\geq 1}B_{i}u^{i},\qquad B_{i}:=\sum_{\begin{subarray}{c}k\geq
1,\,\deg P\in S^{c}\\\ k\deg P=i\end{subarray}}\deg
P=\sum_{\begin{subarray}{c}d\in S^{c}\\\ d\mid
i\end{subarray}}d|\mathcal{P}_{d,q}|.$

Comparing coefficients in (3.16), we obtain

$A_{n}=n^{-1}\sum_{i=1}^{n}A_{n-i}B_{i}.$

Lemma 3.1 implies

$B_{i}\leq\mathbf{1}_{i\not\in S}(i|\mathcal{P}_{i,q}|)+\sum_{d\leq
i/2}d|\mathcal{P}_{d,q}|\leq\mathbf{1}_{i\not\in S}q^{i}+2q^{i/2},$

and so

$A_{n}\leq n^{-1}\sum_{i\in
S^{c}}q^{i}A_{n-i}+2n^{-1}\sum_{i=1}^{n}A_{n-i}q^{i/2}.$

The trivial bound $A_{n-i}\leq q^{n-i}$ implies

$A_{n}\leq n^{-1}\sum_{i\in S^{c}}q^{i}A_{n-i}+5n^{-1}q^{n}\leq
n^{-1}q^{n}\left(\sum_{0\leq i\leq n}q^{-i}A_{i}+5\right).$

Since

$F(1/q)=\sum_{i\geq 0}q^{-i}\widetilde{A}_{i}\geq\sum_{0\leq i\leq
n}q^{-i}A_{i},$

we find that

$A_{n}\leq n^{-1}q^{n}\bigl{(}F(1/q)+5\bigr{)}.$

By Lemma 3.1,

$\log F(1/q)=\sum_{d\in S^{c}}|\mathcal{P}_{d,q}|\sum_{k\geq
1}\frac{q^{-kd}}{k}\leq\sum_{d\in S^{c}}\frac{1+q^{-d}}{d}\leq\sum_{d\in
S^{c}}\frac{1}{d}+1,$

and recalling $\log n=\sum_{d=1}^{n}d^{-1}+O(1)$, we conclude that

$A_{n}\ll n^{-1}q^{n}\exp\left(\sum_{d\in S^{c}}d^{-1}\right)\asymp
q^{n}\exp\left(-\sum_{d\in S}d^{-1}\right)$

as needed. ∎

###  3.3 Proof of Lemma 2.2

Due to the trivial estimate $|S(n,\chi)|\leq q^{n}$, we may assume $n\geq
12(1+\log_{q}(1+\deg Q))$. Since $S(n,\chi)=0$ for $n\geq\deg Q$ we may also
assume $\deg Q>n$. Applying Lemma 3.4 with $\alpha=\chi$ and
$S=\\{m+1,m+2,\ldots,n\\}$ for some $m\in(2\log_{q}\deg Q,n]$ (as indicated in
Remark 3.1), we find that (1.6) indeed holds by appealing to Lemma 3.3. By
Lemma 3.5,

$q^{-n}\sum_{\begin{subarray}{c}f\in\mathcal{M}_{n,q}\\\ P\mid f\implies\deg
P\leq m\end{subarray}}\chi(f)\ll
q^{-n}\sum_{\begin{subarray}{c}f\in\mathcal{M}_{n,q}\\\ P\mid f\implies\deg
P\leq m\end{subarray}}1\ll\frac{m}{n}.$

Choosing $m=\lceil 2\log_{q}(n(1+\deg Q))\rceil$ in (1.6) yields the statement
of the lemma.

###  3.4 Bound on a $\gcd$ sum

For $L\geq 1$, let

$B_{L,k}:=\sum_{L\leq d<2L}\log\gcd(k,q^{d}-1).$

We trivially have $B_{L,k}\ll L\min\\{\log k,L\log q\\}$, and this bound is
optimal when $\log_{q}k\gg L^{2}$. For example, take $k=\prod_{1\leq
i<2L}(q^{i}-1)=q^{\Theta(L^{2})}$, then $q^{d}-1\mid k$ for all $L\leq d<2L$
so that $B_{L,k}\asymp L^{2}\log q$. For smaller $k$, however, this bound is
too generous.

######  Lemma 3.6.

Suppose $L\geq\sqrt{\log_{q}k}$. Then $B_{L,k}\ll L\sqrt{\log k\log q}$.

To prove this result we will need a couple of facts concerning cyclotomic
polynomials. Recall that the cyclotomic polynomials $(\phi_{n}(x))_{n\geq 1}$
are defined recursively by $\prod_{d\mid n}\phi_{d}(x)=x^{n}-1$. They lie in
$\mathbb{Z}[x]$ and can be written as
$\phi_{n}(x)=\prod_{j\in(\mathbb{Z}/n\mathbb{Z})^{\times}}(x-e^{2\pi ij/n})$.
This last relation shows that if $m$ and $p$ are coprime where $p$ is a prime
then $\phi_{mp^{i}}(x)=\phi_{m}(x^{p^{i}})/\phi_{m}(x^{p^{i-1}})$ for $i\geq
1$.

The following lemma is classical but we could not find it explicitly stated in
the literature and so we give a proof based on an argument implicit in Roitman
[26].

######  Lemma 3.7.

Fix an integer $a$. For a prime $p$ define $A_{p}:=\\{n\geq
1:p\mid\phi_{n}(a)\\}$. If $p\mid a$, then $A_{p}=\varnothing$. Otherwise,
$A_{p}=\\{p^{i}\mathrm{ord}_{p}(a):i\geq 0\\}$ where $\mathrm{ord}_{p}(a)$ is
the multiplicative order of $a$ modulo $p$.

###### Proof.

If $p\mid\phi_{n}(a)$, then $p\mid a^{n}-1$ since $\phi_{n}(a)\mid a^{n}-1$.
If $p\mid a$, then $a^{n}-1\equiv-1\bmod p$, which is a contradiction. Thus,
$A_{p}=\varnothing$ in this case.

Now suppose $p\nmid a$. By definition, we have $p\mid
a^{\mathrm{ord}_{p}(a)}-1$. Suppose $p\mid\phi_{n}(a)\mid a^{n}-1$ for some
positive integer $n$, then

$p\mid\gcd(a^{n}-1,a^{\mathrm{ord}_{p}(a)}-1)=a^{\gcd(n,\mathrm{ord}_{p}(a))}-1.$

Since $\mathrm{ord}_{p}(a)=\min\\{n\geq 1:p\mid a^{n}-1$}, we have
$\gcd(n,\mathrm{ord}_{p}(a))\geq\mathrm{ord}_{p}(a)$ and thus
$\mathrm{ord}_{p}(a)\mid n$. This shows

$A_{p}\subseteq\\{m\cdot\mathrm{ord}_{p}(a):m\geq 1\\}.$ (3.17)

Next we show $\mathrm{ord}_{p}(a)\in A_{p}$. Since $p\mid
a^{\mathrm{ord}_{p}(a)}-1=\prod_{e\mid\mathrm{ord}_{p}(a)}\phi_{e}(a)$, it
follows that $A_{p}$ contains some divisor of $\mathrm{ord}_{p}(a)$, which by
(3.17) then has to be $\mathrm{ord}_{p}(a)$ itself. Next, we want to show that
for $n\in A_{p}$, $n/\mathrm{ord}_{p}(a)$ is a power of $p$. If $p^{\prime}$
is a prime dividing $n/\mathrm{ord}_{p}(a)$, then $\mathrm{ord}_{p}(a)\mid
n/p^{\prime}$ and so

$p\mid\phi_{n}(a)=\frac{a^{n}-1}{\prod_{d\mid n,\,d\neq
n}\phi_{d}(a)}\mid\frac{a^{n}-1}{\prod_{d\mid
n/p^{\prime}}\phi_{d}(a)}=\frac{a^{n}-1}{a^{n/p^{\prime}}-1}=\sum_{i=0}^{p^{\prime}-1}a^{in/p^{\prime}}\equiv\sum_{i=0}^{p^{\prime}-1}1=p^{\prime}\bmod
p,$

where we used that by definition of $\mathrm{ord}_{p}(a)$

$a^{n/p^{\prime}}=(a^{\mathrm{ord}_{p}(a)})^{\frac{n}{p^{\prime}\mathrm{ord}_{p}(a)}}\equiv
1^{\frac{n}{p^{\prime}\mathrm{ord}_{p}(a)}}\equiv 1\bmod p.$

Hence, $p^{\prime}$ must be $p$, and $n$ is indeed $\mathrm{ord}_{p}(a)$ times
a power of $p$. This shows $A_{p}\subseteq\\{p^{i}\mathrm{ord}_{p}(a):i\geq
0\\}$. Finally, the relation
$\phi_{p^{i}m}(a)=\phi_{m}(a^{p^{i}})/\phi_{m}(a^{p^{i-1}})$ for $\gcd(m,p)=1$
and $i\geq 1$ implies $p^{i}\mathrm{ord}_{p}(a)\in A_{p}$ for every $i\geq 1$
since
$\phi_{m}(a^{p^{i}})/\phi_{m}(a^{p^{i-1}})\equiv\phi_{m}(a)^{p^{i}-p^{i-1}}\bmod
p$. ∎

###### Proof of Lemma 3.6.

Recall that $q^{d}-1=\prod_{e\mid d}\phi_{e}(q)$. Because
$\gcd(A,ab)\leq\gcd(A,a)\gcd(A,b)$, it then follows that

$\log\gcd(k,q^{d}-1)\leq\sum_{e\mid d}\log\gcd(k,\phi_{e}(q))=\sum_{e\mid
d}\sum_{p\mid k}\log\gcd(p^{\nu_{p}(k)},\phi_{e}(q)),$

where $p$ stands for prime and $\nu_{p}(k)$ is the multiplicity of $p$ in $k$
(i.e., the $p$-adic valuation of $k$). Hence,

$B_{L,k}\leq\sum_{L\leq d<2L}\sum_{\begin{subarray}{c}p\mid k,\,\phi_{e}(q)\\\
e\mid d\end{subarray}}\log\gcd(p^{\nu_{p}(k)},\phi_{e}(q)).$

We introduce a parameter $T\geq 1$. We shall show

$B_{L,k}\ll T\log k+\frac{L^{2}\log q}{T},$ (3.18)

and then take $T=L/\sqrt{\log_{q}k}$. We consider separately the contribution
of $e>d/T$ and $e\leq d/T$, obtaining

$B_{L,k}\leq B_{L,k,1}+B_{L,k,2},$

where

$\displaystyle B_{L,k,1}$ $\displaystyle=\sum_{L\leq
d<2L}\sum_{\begin{subarray}{c}p\mid k,\,\phi_{e}(q)\\\ e\mid d\\\
e>d/T\end{subarray}}\log\gcd(p^{\nu_{p}(k)},\phi_{e}(q)),$ (3.19)
$\displaystyle B_{L,k,2}$ $\displaystyle=\sum_{L\leq
d<2L}\sum_{\begin{subarray}{c}p\mid k,\,\phi_{e}(q)\\\ e\mid d\\\ e\leq
d/T\end{subarray}}\log\gcd(p^{\nu_{p}(k)},\phi_{e}(q)).$ (3.20)

Let us bound $B_{L,k,1}$. By interchanging the order of summation,

$\displaystyle B_{L,k,1}\leq\sum_{\begin{subarray}{c}e,\,p:\,p\mid
k,\,\phi_{e}(q)\\\ L/T<e<2L\end{subarray}}\nu_{p}(k)\log
p\sum_{\begin{subarray}{c}L\leq d<2L\\\ e\mid d\end{subarray}}1\ll
L\sum_{\begin{subarray}{c}e,\,p:\\\ p\mid k,\,\phi_{e}(q)\\\
L/T<e<2L\end{subarray}}\frac{\nu_{p}(k)\log p}{e}.$ (3.21)

Let $A_{p}:=\\{n\geq 1:p\text{ divides }\phi_{n}(q)\\}$. By Lemma 3.7, $A_{p}$
is either empty or is a geometric progression with step size $p$, so that

$\sum_{\begin{subarray}{c}e:\,p\mid\phi_{e}(q)\\\
L/T<e<2L\end{subarray}}\frac{1}{e}\ll\frac{T}{L}\sum_{i\geq
0}p^{-i}\ll\frac{T}{L}$

and it follows that

$\displaystyle B_{L,k,1}$ $\displaystyle\ll T\sum_{p\mid k}\nu_{p}(k)\log
p=T\log k.$ (3.22)

Next, omitting the restriction $p\mid k$ and using $\phi_{e}(q)\mid
q^{e}-1\leq q^{e}$, we have

$B_{L,k,2}\leq\sum_{L\leq d<2L}\sum_{\begin{subarray}{c}e\mid d\\\ e\leq
d/T\end{subarray}}\log\phi_{e}(q)\leq\log q\sum_{L\leq
d<2L}\sum_{\begin{subarray}{c}e\mid d\\\ e\leq d/T\end{subarray}}e\ll L\log
q\sum_{1\leq e<2L/T}1\ll\frac{L^{2}\log q}{T}.$

This implies (3.18), and thus the statement of the lemma. ∎

###  3.5 Symmetry of character sums

######  Lemma 3.8.

Let $\psi\colon\mathbb{F}_{q}\to\mathbb{C}^{\times}$ be an additive character.
Let $k,n\geq 1$, and let $k^{\prime}=\gcd(k,q^{n}-1)$. Then,

$\sum_{f\in\mathcal{M}_{n,q}}\Lambda(f)\chi_{k,\psi}(f)=\sum_{f\in\mathcal{M}_{n,q}}\Lambda(f)\chi_{k^{\prime},\psi}(f).$

###### Proof.

Consider a surjective map

$\Phi\colon\mathbb{F}_{q^{n}}^{\times}\to\\{f\in\mathcal{M}_{n,q}\setminus\\{T\\}:\Lambda(f)\neq
0\\}$

given by

$\Phi(x)=\prod_{\sigma\in\mathrm{Gal}(\mathbb{F}_{q^{n}}/\mathbb{F}_{q})}(T-\sigma(x))=\prod_{i=0}^{n-1}(T-x^{q^{i}}).$

Alternatively, one can also write $\Phi(x)=m_{\alpha}(x)^{n/\deg m_{\alpha}}$,
where $m_{\alpha}$ is the minimal polynomial of $x$ over $\mathbb{F}_{q}$.
Every element $f$ in the image of $\Phi$ has $\Lambda(f)$ preimages given by
the Galois conjugates of a given preimage, namely, $\\{x^{q^{i}}:0\leq i<d\\}$
if $\deg m_{x}=d$. Because $\chi_{k,\psi}(f)$ is defined in terms of the zeros
of $f$, the map $\Phi$ allows us to conveniently write

$\sum_{f\in\mathcal{M}_{n,q}}\Lambda(f)\chi_{k,\psi}(f)=\sum_{x\in\mathbb{F}_{q^{n}}^{\times}}\psi(\sum_{i=0}^{n-1}(x^{q^{i}})^{-k}).$

By Euclid’s algorithm, we can write $k^{\prime}=\gcd(k,q^{n}-1)=ak+b(q^{n}-1)$
for some coprime integers $a$ and $b$. In particular,
$x^{k^{\prime}}=(x^{k})^{a}$. Conversely,
$x^{k}=(x^{k^{\prime}})^{k/k^{\prime}}$. It follows that the group
endomorphisms $x\mapsto x^{k}$ and $x\mapsto x^{\gcd(k,q^{n}-1)}$ defined on
$\mathbb{F}_{q^{n}}^{\times}$ have the same image and kernel. This implies
that every element in the image is attained the same number of times, and so

$\sum_{x\in\mathbb{F}_{q^{n}}^{\times}}\psi(\sum_{i=0}^{n-1}(x^{q^{i}})^{-k})=\sum_{x\in\mathbb{F}_{q^{n}}^{\times}}\psi(\sum_{i=0}^{n-1}(x^{q^{i}})^{-k^{\prime}})=\sum_{f\in\mathcal{M}_{n,q}}\Lambda(f)\chi_{k^{\prime},\psi}(f)$

as required. ∎

From Lemmas 2.1, 3.3, and 3.8, we conclude the following.

######  Corollary 3.9.

Let $\psi\colon\mathbb{F}_{q}\to\mathbb{C}^{\times}$ be a nontrivial additive
character. Let $k,n\geq 1$. We have

$\bigg{|}\sum_{f\in\mathcal{M}_{n,q}}\Lambda(f)\chi_{k,\psi}(f)\bigg{|}\leq
q^{\frac{n}{2}}\gcd(k,q^{n}-1).$

###  3.6 Proof of Proposition 1.6

Let $m:=\lceil 12\log_{q}n\rceil$, and

$S=\\{m\leq d\leq n:\gcd(k,q^{d}-1)<q^{d/3}\\}.$ (3.23)

Let $S^{c}=\\{1,\ldots,n\\}\setminus S$. As before, let

$q^{-n}\sum_{f\in\mathcal{M}_{n,q}}\chi_{k,\psi}(f)=q^{-n}\sum_{\begin{subarray}{c}f\in\mathcal{M}_{n,q}\\\
\exists P\mid f\text{ such that }\deg P\in
S\end{subarray}}\chi_{k,\psi}(f)+q^{-n}\sum_{\begin{subarray}{c}f\in\mathcal{M}_{n,q}\\\
P\mid f\implies\deg P\in S^{c}\end{subarray}}\chi_{k,\psi}(f).$

Applying Lemma 3.4 for $\alpha=\chi_{k,\psi}$ and our chosen $S$ together with
Corollary 3.9, we get

$\displaystyle q^{-n}\sum_{\begin{subarray}{c}f\in\mathcal{M}_{n,q}\\\ \exists
P\mid f\text{ such that }\deg P\in S\end{subarray}}\chi_{k,\psi}(f)$ (3.24)
$\displaystyle\ll\exp\left(\sum_{d\in
S^{c}}d^{-1}\right)\left(\exp\left(\sum_{d\in
S}\frac{q^{-d/6}}{d}+O(q^{-m/2}/m)\right)-1\right)\ll\frac{nq^{-m/6}}{m}\ll
n^{-1}.$ (3.25)

By Lemma 3.5,

$q^{-n}\sum_{\begin{subarray}{c}f\in\mathcal{M}_{n,q}\\\ P\mid f\implies\deg
P\in S^{c}\end{subarray}}\chi_{k,\psi}(f)\ll
q^{-n}\sum_{\begin{subarray}{c}f\in\mathcal{M}_{n,q}\\\ P\mid f\implies\deg
P\in S^{c}\end{subarray}}1\ll\exp(-\sum_{d\in S}d^{-1}).$

######  Remark 3.3.

The same proof works as is if we replace $\chi_{k,\psi}$ by
$\mu\cdot\chi_{k,\psi}$, because

$\sum_{f\in\mathcal{M}_{d,q}}\chi_{k,\psi}(f)\Lambda(f)=-\sum_{f\in\mathcal{M}_{d,q}}\mu(f)\chi_{k,\psi}(f)\Lambda(f)+O(q^{d/2}).$

###  3.7 Conclusion of proof of Theorem 1.5

Due to the trivial estimate $|S(n,\chi)|\leq q^{n}$, we may assume $n\geq
12(1+\sqrt{\log_{q}k})$. In view of Proposition 1.6 it suffices to show

$-\sum_{d\in S}d^{-1}\leq\log(1+\sqrt{\log_{q}k}+\log_{q}n)-\log n+O(1),$

where $S$ is as in (3.23). To show this, first observe that $-\sum_{d\in
S}d^{-1}=\sum_{d\in S^{c}}d^{-1}-\log n+O(1)$. Let $m^{\prime}=\max\\{\lceil
12\log_{q}n\rceil,\sqrt{\log_{q}k}\\}$. Since $\mathbf{1}_{A\geq B}\leq\log
A/\log B$,

$\sum_{d\in S^{c}}d^{-1}\leq\sum_{d\leq
m^{\prime}}d^{-1}+\sum_{\begin{subarray}{c}m^{\prime}\leq d\leq n\\\
\gcd(k,q^{d}-1)\geq q^{d/3}\end{subarray}}d^{-1}\leq\log
m^{\prime}+O(1)+\sum_{m^{\prime}\leq d\leq
n}d^{-1}\frac{\log\gcd(k,q^{d}-1)}{\log(q^{d/3})}.$

By Lemma 3.6, the last $d$-sum is $O(\sqrt{\log_{q}k}/m^{\prime})$, finishing
the proof.

## Acknowledgments

We thank Brad Rodgers and Zeev Rudnick for comments on an earlier version of
the paper. We appreciate the comments and suggestions given by the anonymous
referee, which improved the presentation of the paper. O.G. was supported by
the European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (grant agreement number 851318). V.K. was
supported by ERC LogCorRM (grant number 740900) and by CRM-ISM postdoctoral
fellowship.

##  Appendix A Squareroot cancellation in character sums

Under the generalized Riemann hypothesis for $L(s,\chi)$ one has $\sum_{n\leq
x}\chi(n)\ll\sqrt{x}\exp(C\log m/\log\log m)$ for a nonprincipal Dirichlet
character $\chi$ modulo $m$ [3]. Bhowmick, Lê and Liu [3] proved the function
field analogue

$\sum_{f\in\mathcal{M}_{n,q}}\chi(f)\ll
q^{n/2}\exp\left(C_{q}\left(\frac{n\log\log\deg Q}{\log\deg Q}+\frac{\deg
Q}{\log^{2}\deg Q}\right)\right)$ (A.1)

unconditionally, for a constant $C_{q}$ that depends only on $q$, where $\chi$
is a character modulo $Q\in\mathbb{F}_{q}[T]$. The estimate (A.1) implies
$\sum_{f\in\mathcal{M}_{n,q}}\chi(f)\ll q^{\frac{n}{2}(1+o(1))}$ for $\deg
Q=o(n\log^{2}n)$. Here we prove that squareroot cancellation holds in the
wider range $\deg Q\leq n^{1+o(1)}$.

######  Proposition A.1.

Let $\chi$ be a nonprincipal Dirichlet character modulo
$Q\in\mathbb{F}_{q}[T]$. There is a constant $C_{q}$ that depends only on $q$
such that

$\sum_{f\in\mathcal{M}_{n,q}}\chi(f)\ll_{q}q^{\frac{n}{2}}\exp\left(\max\left\\{C_{q}n\frac{\log(\deg
Q\log\deg Q/n)}{\log(1+\deg Q)},0\right\\}\right).$ (A.2)

Recall $d(\chi):=\deg L(u,\chi)<\deg Q$. If $d(\chi)<n$ we have $S(n,\chi)=0$,
so from now on we assume that $d(\chi)\geq n$. In view of the trivial bound
$|S(n,\chi)|\leq q^{n}$ we may also assume that $n$ is larger than a fixed
constant, as well as that $d\leq n^{1+\delta}$ for a fixed $\delta>0$. From
(3.3),

$L(u,\chi)=\exp\left(\sum_{k\geq
1}\frac{u^{k}}{k}\sum_{f\in\mathcal{M}_{k,q}}\chi(f)\Lambda(f)\right).$ (A.3)

Set $L:=\lfloor 2\log_{q}d\rfloor$. For $k\leq L$ the trivial bound

$\left|\sum_{f\in\mathcal{M}_{k,q}}\chi(f)\Lambda(f)\right|\leq\sum_{f\in\mathcal{M}_{k,q}}\Lambda(f)=q^{k}$
(A.4)

coming from (3.2) is superior to (3.5). We see from (3.5) and (A.4) that the
coefficients of $L(u,\chi)$ are bounded (in absolute value) from above by
those of

$\exp\bigg{(}\sum_{k\geq
1}\frac{u^{k}}{k}\min\\{q^{k},d(\chi)q^{k/2}\\}\bigg{)},$

hence, writing $[u^{n}]F$ for the $n$th coefficient of a power series $F$,

$\displaystyle|S(n,\chi)|=q^{n/2}|[u^{n}]L(u/\sqrt{q},\chi)|$
$\displaystyle\leq q^{n/2}[u^{n}]\exp\bigg{(}\sum_{k\geq
1}\frac{u^{k}}{k}\min\\{q^{k/2},d(\chi)\\}\bigg{)}$ (A.5) $\displaystyle\leq
q^{n/2}\exp\bigg{(}\sum_{k\geq
1}\frac{R^{k}}{k}\min\\{q^{k/2},d(\chi)\\}\bigg{)}R^{-n}$ (A.6)

for any $R\in(0,1)$ (this is the same observation used in the proof of Lemma
3.4). If $6/(5\sqrt{q})<R<1$ then

$\sum_{1\leq k\leq L}\frac{R^{k}}{k}\min\\{q^{k/2},d(\chi)\\}=\sum_{1\leq
k\leq L}\frac{(R\sqrt{q})^{k}}{k}\leq\sum_{1\leq k\leq
L}(R\sqrt{q})^{k}\leq\frac{(R\sqrt{q})^{L}}{1-(R\sqrt{q})^{-1}}\leq
6d(\chi)R^{L}$ (A.7)

and

$\sum_{k>L}\frac{R^{k}}{k}\min\\{q^{k/2},d(\chi)\\}\leq
d(\chi)\sum_{k>L}\frac{R^{k}}{k}\leq\frac{d(\chi)}{L+1}\sum_{k>L}R^{k}=\frac{d(\chi)}{L+1}\frac{R^{L+1}}{1-R},$
(A.8)

so that

$|S(n,\chi)/q^{n/2}|\leq\exp\Big{(}6d(\chi)R^{L}\Big{(}1+\frac{R}{(L+1)(1-R)}\Big{)}-n\log
R\Big{)}.$ (A.9)

Set $a:=\log(d(\chi)\log d(\chi)/n)$ and take $R=q^{-a/(2\log d(\chi))}$. The
assumption $d(\chi)\geq n$ implies $a>0$ (at least if $n\geq 3$) and so $R<1$.
(This choice of $R$ differs from the choice in [3], where $a$ is chosen to be
of order $\log\log d(\chi)$.) Since we may assume $n\leq d(\chi)\leq
n^{1+\delta}$ and $n\geq C$ for $\delta$ and $C$ we choose, we may also assume
$a/\log d(\chi)$ is at most $\delta^{\prime}$ for a $\delta^{\prime}$ we want.
In particular, $R>6/(5\sqrt{q})$ may be assumed from now on by taking small
enough $\delta^{\prime}$. Moreover,

$-n\log R\leq(\log q)n\frac{\log(d(\chi)\log d(\chi)/n)}{\log d(\chi)},\qquad
R^{L}\leq q^{-\frac{\log(d(\chi)\log d(\chi)/n)}{2\log
d(\chi)}(2\log_{q}d(\chi)-1)}\leq\frac{2}{(d(\chi)\log d(\chi)/n)}$ (A.10)

for large enough $n$. Additionally, $a\log q/\log d(\chi)\in(0,1)$ holds (by
taking small enough $\delta^{\prime}$) which implies $R\leq 1-a\log q/(4\log
d(\chi))$, and so

$\frac{R}{(L+1)(1-R)}\leq\frac{1}{L+1}\frac{1}{1-R}\leq\frac{\log q}{2\log
d(\chi)}\frac{4\log d(\chi)}{\log q\log(d(\chi)\log
d(\chi)/n)}=\frac{2}{\log(d(\chi)\log d(\chi)/n)}\leq 1$ (A.11)

for large enough $n$. All in all,

$|S(n,\chi)/q^{n/2}|\leq\exp\bigg{(}\frac{24n}{\log d(\chi)}+(\log
q)n\frac{\log(d(\chi)\log d(\chi)/n)}{\log
d(\chi)}\bigg{)}\leq\exp\bigg{(}C_{q}n\frac{\log(d(\chi)\log d(\chi)/n)}{\log
d(\chi)}\bigg{)}.$ (A.12)

Since $\deg Q>d(\chi)$, the claim follows.

## References

  * [1] W. D. Banks and I. E. Shparlinski.  Bounds on short character sums and $L$-functions with characters to a powerful modulus.  J. Anal. Math., 139(1):239–263, 2019.
  * [2] A. Bhowmick and T. H. Lê.  On primitive elements in finite fields of low characteristic.  Finite Fields Appl., 35:64–77, 2015.
  * [3] A. Bhowmick, T. H. Lê, and Y.-R. Liu.  A note on character sums in finite fields.  Finite Fields Appl., 46:247–254, 2017.
  * [4] D. A. Burgess.  On character sums and $L$-series. II.  Proc. Lond. Math. Soc. (3), 13:524–536, 1963.
  * [5] D. A. Burgess.  The character sum estimate with $r=3$.  J. London Math. Soc. (2), 33(2):219–226, 1986.
  * [6] K. Courteaut and K. Johansson.  Multivariate normal approximation for traces of orthogonal and symplectic matrices.  Ann. Inst. Henri Poincaré, Probab. Stat., 60(1):312–342, 2024\.
  * [7] K. Courteaut, K. Johansson, and G. Lambert.  From Berry-Esseen to super-exponential.  Electron. J. Probab., 29:48, 2024.  Id/No 11.
  * [8] N. G. de Bruijn.  On the number of positive integers $\leq x$ and free of prime factors $>y$.  Nederl. Akad. Wet., Proc., Ser. A, 54:50–60, 1951.
  * [9] P. Diaconis and M. Shahshahani.  On the eigenvalues of random matrices.  J. Appl. Probab., 31A:49–62, 1994.
  * [10] K. Ford.  Cycle type of random permutations: a toolkit.  Discrete Anal., 2022.  Paper No. 9, 36.
  * [11] M. Gerstenhaber.  On the number of nilpotent matrices with coefficients in a finite field.  Illinois J. Math., 5:330–333, 1961.
  * [12] O. Gorodetsky and B. Rodgers.  Traces of powers of matrices over finite fields.  Trans. Amer. Math. Soc., 374(7):4579–4638, 2021.
  * [13] A. Granville and K. Soundararajan.  Large character sums.  J. Amer. Math. Soc., 14(2):365–397, 2001.
  * [14] H. Halberstam and H.-E. Richert.  On a result of R. R. Hall.  J. Number Theory, 11(1):76–89, 1979.
  * [15] R. R. Hall.  Halving an estimate obtained from Selberg’s upper bound method.  Acta Arith., 25:347–351, 1973/74.
  * [16] D. R. Hayes.  The distribution of irreducibles in $GF[q,x]$.  Trans. Amer. Math. Soc., 117:101–127, 1965.
  * [17] H. Iwaniec and E. Kowalski.  Analytic number theory, volume 53 of Colloq. Publ., Am. Math. Soc. Providence, RI: American Mathematical Society (AMS), 2004.
  * [18] K. Johansson.  On random matrices from the compact classical groups.  Ann. of Math. (2), 145(3):519–545, 1997.
  * [19] K. Johansson and G. Lambert.  Multivariate normal approximation for traces of random unitary matrices.  Ann. Probab., 49(6):2961–3010, 2021.
  * [20] J. Keating and Z. Rudnick.  Squarefree polynomials and Möbius values in short intervals and arithmetic progressions.  Algebra Number Theory, 10(2):375–420, 2016.
  * [21] J. P. Keating and Z. Rudnick.  The variance of the number of prime polynomials in short intervals and in residue classes.  Int. Math. Res. Not. IMRN, (1):259–288, 2014.
  * [22] H. L. Montgomery and R. C. Vaughan.  Exponential sums with multiplicative coefficients.  Invent. Math., 43(1):69–82, 1977.
  * [23] P. Pollack.  Irreducible polynomials with several prescribed coefficients.  Finite Fields Appl., 22:70–78, 2013.
  * [24] E. M. Rains.  High powers of random elements of compact Lie groups.  Probab. Theory Related Fields, 107(2):219–241, 1997.
  * [25] I. Reiner.  On the number of matrices with given characteristic polynomial.  Illinois J. Math., 5:324–329, 1961.
  * [26] M. Roitman.  On Zsigmondy primes.  Proc. Amer. Math. Soc., 125(7):1913–1919, 1997.
  * [27] M. Rosen.  Number theory in function fields, volume 210 of Graduate Texts in Mathematics.  Springer, New York, 2002.
  * [28] A. Weil.  Basic number theory, volume 144 of Grundlehren Math. Wiss. Springer, Cham, 1967.

Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK

E-mail address<EMAIL_ADDRESS>

Départment de Mathématiques et Statistique, Université de Montréal, Montréal,
QC H3C 3J7, Canada

E-mail address<EMAIL_ADDRESS>