# Universality for low degree factors of random polynomials over finite fields

Jimmy He  Department of Mathematics, MIT, Cambridge, MA 02139<EMAIL_ADDRESS>,  Huy Tuan Pham  Department of Mathematics, Stanford University, Stanford, CA
94305<EMAIL_ADDRESS>and  Max Wenqiang Xu  Department of Mathematics,
Stanford University, Stanford, CA 94305<EMAIL_ADDRESS>
###### Abstract.

We show that the counts of low degree irreducible factors of a random
polynomial $f$ over $\mathbb{F}_{q}$ with independent but non-uniform
coefficients behave like that of a uniform random polynomial, exhibiting a
form of universality for random polynomials over finite fields. Our strongest
results require various assumptions on the parameters, but we are able to
obtain results requiring only $q=p$ a prime with $p\leq\exp({n^{1/13}})$ where
$n$ is the degree of the polynomial. Our proofs use Fourier analysis, and rely
on tools recently applied by Breuillard and Varjú [6, 7] to study the $ax+b$
process, which show equidistribution for $f(\alpha)$ at a single point. We
extend this to handle multiple roots and the Hasse derivatives of $f$, which
allow us to study the irreducible factors with multiplicity.

###### Key words and phrases:

Random polynomials, finite field, irreducible factors, universality

###### 1991 Mathematics Subject Classification:

60C05 (Primary), 60B99, 11T06 (Secondary)

##  1\. Introduction

Let $\overline{f}(x)=x^{n}+\sum_{i=0}^{n-1}\varepsilon_{i}x^{i}$ be a random
monic polynomial with independent uniformly distributed coefficients in a
finite field $\mathbb{F}_{q}$, and consider $N_{i}^{\prime}(\overline{f})$,
the number of irreducible factors of $\overline{f}$ in $\mathbb{F}_{q}[x]$ of
degree $i$. The moments can be explicitly computed using generating function
arguments, and the work of Arratia, Barbour and Tavaré established strong
asymptotics for these random variables [2].

In this paper, we study random polynomials
$f(x)=\sum_{i=0}^{n}\varepsilon_{i}x^{i}$, where the $\varepsilon_{i}$ are
independent but no longer uniformly distributed in $\mathbb{F}_{q}$. We
establish results that suggest the distribution of the
$N_{i}^{\prime}(\overline{f})$ are universal, at least when $i$ is not too
large compared to $n$. For example, we show the joint distribution of the
counts under the non-uniform and uniform models, $N_{i}^{\prime}(f)$ and
$N_{i}^{\prime}(\overline{f})$, for $i\leq n^{\frac{1}{13}}$, are close in
total variation distance as long as $q=p$ is prime and $p\leq
e^{n^{\frac{1}{13}}}$. We also obtain results for $q=p^{e}$ as long as $q$ is
not too large compared to $n$.

We study these polynomials $f(x)$ using Fourier-analytic methods. Note that
the value of $f(\alpha)$ for some $\alpha\in\mathbb{F}_{q^{d}}$ can be viewed
as the state of a random walk defined by $X_{t+1}=\alpha
X_{t}+\varepsilon_{t+1}$ where $\varepsilon_{t+1}$ is drawn from some non
trivial distribution. This is known as the $ax+b$ process or the
Chung–Diaconis–Graham process, and we use recent tools developed to study this
process in [6, 7]. For this reason, our strongest results apply only when the
coefficients lie in $\mathbb{F}_{p}$.

This also leads us to study the distribution of $N_{i}(f)$, the number of
_distinct_ irreducible factors of degree $i$, since these values are more
closely related to the equidistribution of $X_{n+1}=f(\alpha)$. To study the
$N_{i}^{\prime}(f)$, which count irreducible factors with multiplicity, we
instead study the equidistribution of the values of $f$ along with its Hasse
derivatives. This requires extending the tools developed in [6, 7].

Finally, we remark that certain universality results on random matrices over
finite fields, and especially on their eigenvalues (which are of course the
roots of the characteristic polynomial), seem to be at least morally related
to our results. Recent works [27, 14, 17] seem to indicate that the
eigenvalues of random matrices over $\mathbb{F}_{q}$ also exhibit universal
behaviour. It would be very interesting to see if there is a deeper
connection, as well as if other examples of universal behaviour for random
objects defined over finite fields could be found.

###  1.1. Statistics for the uniform model

Uniformly random polynomials (or equivalently monic polynomials) have been
intensely studied in both the probability and combinatorics literature. Some
of the strongest results are due to Arratia, Barbour and Tavaré [2], who
established strong, quantitative approximation results for not only the low
degree factors, but also the high degree ones. They also established a
functional central limit theorem and Poisson-Dirichlet limit theorems. Their
results fit into the subsequent general theory of logarithmic combinatorial
structures, see [3]. However, their methods rely heavily on the fact that the
polynomials are uniformly sampled, and except for certain special deformations
analogous to the Ewen’s sampling formula for random permutations, their
results do not extend to more general models of random polynomials.

Our results show that the low degree irreducible factors of $f$ behave very
similarly to those for a uniformly random monic polynomial. This is useful
because the distribution of $N_{i}(\overline{f})$ and
$N_{i}^{\prime}(\overline{f})$ are very well understood, and this knowledge
can be transferred to say something about $N_{i}(f)$ and $N_{i}^{\prime}(f)$.
We briefly survey some results on low degree factors for the uniform model
$\overline{f}$. We note that in this section only, $N_{1}(f)$ and
$N^{\prime}_{1}(f)$ include the irreducible factor $x$, which we exclude for
the rest of the paper.

######  Theorem 1.1 ([2, Theorem 3.1, Corollary 3.3]).

Let $\pi(i)$ denote the number of monic irreducible polynomials of degree $i$
in $\mathbb{F}_{q}[x]$. For $i\geq 1$, let $X_{i}$ and $Y_{i}$ be independent
binomial and negative binomial random variables of parameters $\pi(i)$ and
$q^{-i}$. Then

$d_{TV}\left((N_{i}(\overline{f}))_{i\leq N},(X_{i})_{i\leq
N}\right)=O\left(N\exp\left(-\frac{n}{2N}\log\frac{4}{3}\right)\right)$

and

$d_{TV}\left((N_{i}^{\prime}(\overline{f}))_{i\leq N},(Y_{i})_{i\leq
N}\right)=O\left(N\exp\left(-\frac{n}{2N}\log\frac{4}{3}\right)\right).$

Note that when $q$ is large, $\pi(i)\sim\frac{q^{i}}{i}$, and so both $X_{i}$
and $Y_{i}$ become close to Poisson random variables of mean $\frac{1}{i}$. In
fact, when $q$ is large, the $N^{\prime}_{i}(\overline{f})$ (and also the
$N_{i}(\overline{f})$) are extremely close to the distribution of cycles in a
random permutation.

######  Theorem 1.2 ([2, Corollary 5.6]).

Let $C_{i}$ denote the number of cycles of size $i$ in a uniformly random
permutation in $S_{n}$. Then

$d_{TV}\left((N^{\prime}_{i}(\overline{f}))_{i=1}^{n},(C_{i})_{i=1}^{n}\right)\leq
q^{-1}+O\left(q^{-\frac{3}{2}}\right).$

In fact, a lower bound of order $q^{-1}$ is also known [2], and this theorem
was given another proof in [4].

Our results imply that all these statements hold for $N_{i}(f)$ and
$N_{i}^{\prime}(f)$ as well, albeit for a much lower upper bound on the
highest degree $i$.

Actually Theorem 1.1 follows from the following more general result on the
joint distributions of all multiplicities of irreducible factors up to a given
degree.

######  Theorem 1.3 ([2, Theorem 3.1]).

Let $N_{\phi}(\overline{f})$ denote the multiplicity of an irreducible factor
$\phi$ in $\overline{f}$. Let $Z_{\phi}$ denote independent geometric random
variables of parameter $q^{-\deg(\phi)}$. Then for all $N\geq 1$,

$d_{TV}\left((N_{\phi}(\overline{f}))_{\deg(\phi)\leq
N},(Z_{\phi})_{\deg(\phi)\leq
N}\right)=O\left(N\exp\left(-\frac{n}{2N}\log\frac{4}{3}\right)\right).$

Finally, we also mention some results on the high degree factors. Recall that
the _Poisson-Dirichlet_ process is a random variable taking values in infinite
vectors $(x_{i})$ with $x_{1}\geq x_{2}\geq\dotsc$ and $\sum x_{i}=1$. It has
a natural description in terms of the following stick-breaking process. Let
$U_{i}$ be independent uniform random variables on $[0,1]$, and let
$V_{i}=U_{i}\prod_{j<i}(1-U_{j})$. One can think of the $V_{i}$ as sampled by
placing points inductively, uniformly on the rightmost interval. Then the
Poisson-Dirichlet process is given by the sorted lengths of the intervals
defined by the points $V_{i}$.

######  Theorem 1.4 ([2, Remark 5.13]).

Let $L=(L_{i}(\overline{f})/n)$ denote the normalized degrees of the
irreducible factors of $\overline{f}$ a uniformly chosen monic polynomial of
degree $n$, in descending order. Then $L$ converges to the Poisson-Dirichlet
process.

Much is also known about the total number of factors. It’s known that the
number of factors is close to a Poisson of mean $H_{n}$, where $H_{n}$ is the
$n$th harmonic number.

######  Theorem 1.5 ([2, Theorem 6.8]).

Let $N^{\prime}(\overline{f})$ denote the total number of irreducible factors
for a random monic polynomial of degree $n$. Let $Z$ denote a Poisson random
variable of mean $H_{n}$. Then

$d_{TV}(N^{\prime}(\overline{f}),Z)=O\left(\log^{-\frac{1}{2}}n\right).$

There is also recent work of Elboim and Gorodetsky, who obtained optimal total
variation bounds to the number of cycles in a random permutation [16], which
in particular implies Theorem 1.5.

###  1.2. Main results

Our main results establish a form of universality for the number of low degree
irreducible factors of random polynomials over finite fields. Since our
strongest results require some technical assumptions and are only effective
for certain ranges of the parameters we consider, we have left their
statements for Section 7. Instead, we state some simpler consequences which
apply with only mild restrictions.

Let $f\in\mathbb{F}_{p}[x]$ be the random polynomial defined by

$f(x)=\sum_{i=0}^{n}\varepsilon_{i}x^{i},$

with the $\varepsilon_{i}$ independently drawn from some distribution $\mu$ on
$\mathbb{F}_{p}$. Let $\eta=1-\max_{x\in\mathbb{F}_{p}}\mu(x)$. This parameter
has previously appeared in the study of universality for random matrices over
$\mathbb{F}_{p}$ (see e.g. [27]), and $\eta>0$ ensures that $\mu$ is not
concentrated at a single point. Let $\overline{f}(x)$ be a uniformly random
monic polynomial in $\mathbb{F}_{p}[x]$ of degree $n$. For any polynomial $g$,
let $N_{i}(g)$ denote the number of distinct irreducible factors of $g$ of
degree $i$, and let $N_{i}^{\prime}(g)$ denote the total number of irreducible
factors of $g$ of degree $i$, counted with multiplicity. We note that
$N_{1}(g)$ and $N^{\prime}_{1}(g)$ exclude factors of $x$, since the number of
these clearly depends on the distribution $\mu$.

Our most general results apply even when $p$ grows rapidly with $n$, but
require the coefficients to lie in $\mathbb{F}_{p}$ for a prime $p$. We first
consider the joint distribution of the number of distinct irreducible factors
of degrees not too large in $n$.

######  Corollary 1.6.

Suppose that $p\leq e^{n^{\frac{1}{8}}}$. Then for any $\delta>0$,

$d_{TV}\left((N_{i}(f))_{i\leq
n^{\frac{1}{8}-\delta}},(N_{i}(\overline{f}))_{i\leq
n^{\frac{1}{8}-\delta}}\right)=O(n^{-\delta}),$

where the implicit constant depends only on $\eta$ and $\delta$.

We also consider the number of irreducible factors counted with multiplicity.

######  Corollary 1.7.

Suppose that $p\leq e^{n^{\frac{1}{13}}}$. Then for any $\delta>0$,

$d_{TV}\left((N^{\prime}_{i}(f))_{i\leq
n^{\frac{1}{13}-\delta}},(N^{\prime}_{i}(\overline{f}))_{i\leq
n^{\frac{1}{13}-\delta}}\right)=O(n^{-3\delta}),$

where the implicit constant depends only on $\eta$ and $\delta$.

Together with Theorem 1.1, this immediately implies the following limit
theorems.

######  Corollary 1.8.

Let $X_{i}$ and $Y_{i}$ be independent binomial and negative binomial random
variables of parameters $\pi(i)$ and $p^{-i}$. For any $\delta$, if $p\leq
e^{n^{\frac{1}{8}}}$, then

$d_{TV}\left((N_{i}(f))_{2\leq i\leq n^{\frac{1}{8}-\delta}},(X_{i})_{2\leq
i\leq n^{\frac{1}{8}-\delta}}\right)=O(n^{-\delta}),$

and if $p\leq e^{n^{\frac{1}{13}}}$, then

$d_{TV}\left((N^{\prime}_{i}(f))_{2\leq i\leq
n^{\frac{1}{13}-\delta}},(Y_{i})_{2\leq i\leq
n^{\frac{1}{13}-\delta}}\right)=O(n^{-3\delta}).$

######  Remark 1.9.

We note that it is necessary to exclude the irreducible factor $x$, because
whether it divides $f$ and with what multiplicity is easily seen to be
dependent on $\mu(0)$. In particular, the multiplicity of $x$ as a factor is a
truncated geometric random variable of parameter $\mu(0)$. We will ignore
factors of $x$, and it is safe to simply assume that $\mu(0)=0$, although this
is not necessary for our results to hold. This essentially amounts to
randomizing the degree and conditioning on the constant term being non-zero,
which would ultimately not affect our arguments.

This is also why Corollary 1.8 is stated with $i\geq 2$. For $i=1$, one needs
to specifically remove $0$, and so the limiting distribution should be
binomial and negative binomial with parameters $\pi(1)-1=p-1$ and $p^{-1}$.
One could use the same arguments as in [2] to include $i=1$ as well.

######  Remark 1.10.

There are many models we could draw $\overline{f}$ from, whether uniformly
from all polynomials of degree $n$, those of degree at most $n$, or monic
polynomials of degree $n$. It makes no difference in our analysis, since the
small irreducible factors have basically the same distribution, and indeed our
proof uses a moment matching argument which only sees low-order moments, which
are nearly identical for all these models. This is easy to see, as the roots
do not depend on whether the polynomial is taken to be monic or not, and a
uniform polynomial of degree at most $n$ is exponentially likely to have a
large degree, and so will have statistics close to that of a random monic
polynomial.

For this paper, we will always work with monic polynomials, as they are a bit
easier to work with and most results in the literature are on this model.

######  Remark 1.11.

These results are stated to maximize the degree of the irreducible factors
considered. We can take $p$ up to $e^{n^{\frac{1}{4}-\delta}}$ for any
$\delta>0$ at the cost of considering lower degree irreducible factors.

For a single degree, we can show that the number of irreducible factors of a
fixed degree $i$ of $f$ and of the uniform model $\overline{f}$ have
approximately the same distribution for $i$ up to $n^{1/2-\epsilon}$.

######  Corollary 1.12.

Suppose that $i\leq n^{1/2-2\epsilon}$ and $p<\exp(n^{1/2-\epsilon}/i)$. Then

$d_{TV}(N_{i}(f),N_{i}(\overline{f}))=O_{\epsilon,\eta}(\exp(-n^{c\epsilon})+\min(\exp(-ci),n^{-c})),$

where $c$ is an absolute constant independent of $\eta$ and $\epsilon$.

We obtain similar conclusions for linear statistics of the number of
irreducible factors of degree up to $n^{1/2-\epsilon}$, for example, the total
number of irreducible factors of degree at most $n^{1/2-\epsilon}$. Similar
results could also be derived for a bounded or slowly growing number of such
statistics. We remark that the threshold $n^{1/2}$ seems to be the fundamental
limit of our technique, and it would be very interesting to derive
universality results beyond this threshold.

If we fix the finite field, we can in fact handle coefficients in an arbitrary
finite field $\mathbb{F}_{q}$. We now take $\mu$ to be a distribution on
$\mathbb{F}_{q}$, and let $\eta=1-\max_{V\subseteq\mathbb{F}_{q}}\mu(V)$ where
the maximum is taken over all proper $\mathbb{F}_{p}$ affine subspaces $V$,
and let $f$ and $\overline{f}$ be defined as above, but with coefficients in
$\mathbb{F}_{q}$.

######  Corollary 1.13.

Fix a prime power $q$. Then for some small constant $c$ depending only on
$\eta$ and $q$, if $N=cn^{\frac{1}{4}}/\log^{\frac{1}{2}}n$, then

$d_{TV}\left((N_{i}(f))_{i\leq N},(N_{i}(\overline{f}))_{i\leq
N}\right)=O(e^{-n^{\frac{1}{4}}})$

and if $N=cn^{\frac{1}{5}}/\log^{\frac{4}{5}}n$, then

$d_{TV}\left((N^{\prime}_{i}(f))_{i\leq
N},(N^{\prime}_{i}(\overline{f}))_{i\leq N}\right)=O(e^{-n^{\frac{1}{5}}}),$

where the constants depends only on $\eta$ and $q$.

Again, together with Theorem 1.1 this implies that the $N_{i}(f)$ and
$N_{i}^{\prime}(f)$ converge to independent binomial and negative binomial
random variables.

All of the results in this section follow from stronger bounds which are
stated in Section 7, and their proofs are given there as well.

######  Remark 1.14.

While we focus on a few statistics in this paper, mainly the statistics
$N_{i}(f)$ and $N_{i}^{\prime}(f)$, in fact our techniques can handle any
reasonable function of the irreducible factors of $f$ and their multiplicity,
subject to the restrictions that the irreducible factors have low degree, and
that the number of statistics considered is small. We did not find a way to
make this precise, but we note that other statistics of interest such as the
joint multiplicities of a small number of possible irreducible factors, or the
number of irreducible factors of degree $i$ and multiplicity $m$, could be
studied with our techniques, and quantitative bounds could be obtained.

In particular, using our methods and Theorem 1.3, one could bound the distance
between the joint multiplicities of irreducible polynomials
$\phi_{1},\dotsc,\phi_{k}$ and geometric random variables of parameters
$q^{-\deg(\phi_{1})},\dotsc,q^{-\deg(\phi_{k})}$.

###  1.3. Further questions

Given the wealth of knowledge on the irreducible factors of uniform random
polynomials, it is natural to wonder to what extent these distributions are
universal.

######  Question 1.15.

To what extent are the statistics of the irreducible factors of random
polynomials in $\mathbb{F}_{q}[x]$ universal? That is, let
$f=\sum\varepsilon_{i}x^{i}$ be a random polynomial with independent and
identically distributed coefficients in $\mathbb{F}_{q}$. What statistics are
close to that of a uniformly chosen monic polynomial?

Our results answer this question for low degree factors. Our methods are not
suitable for studying the high degree irreducible factors. On the other hand,
numerical simulations suggest that even the high degree irreducible factors
exhibit universality. Based on this, we make the following conjecture on the
maximal degree of an irreducible factor.

######  Conjecture 1.16.

Let $f=\sum\varepsilon_{i}x^{i}$ be a random polynomial with independent
coefficients in $\mathbb{F}_{p}$. The maximal degree of an irreducible factor
of $f$, normalized by the total degree, converges to the maximum of a Poisson-
Dirichlet process.

We give some evidence in Section 8. This would immediately follow from the
following stronger conjecture, which we do not have any additional evidence
for.

######  Conjecture 1.17.

Let $f=\sum\varepsilon_{i}x^{i}$ be a random polynomial with independent
coefficients in $\mathbb{F}_{p}$. Then the normalized degrees of the
irreducible factors converge to a Poisson-Dirichlet process.

In addition, one could ask similar questions about the total number of
factors, the medium-degree factors, and so on. We leave all of these questions
as open problems.

###  1.4. Proof idea

We now give a heuristic explanation for the bounds we obtain, and an idea of
their proof.

The starting point is that the values of the random polynomial
$f(x)=\sum_{i=0}^{n}\varepsilon_{i}x^{i}$ at an element
$\alpha\in\mathbb{F}_{p^{e}}$ has the same distribution as the states at time
$n$ of the Markov chains defined by $X_{t}=\alpha X_{t-1}+\varepsilon_{t}$. It
is not hard to show that these Markov chains converge to the uniform
distribution, and in fact recent work of Breuillard and Varjú [6, 7] show that
if $q=p$ is prime, for most $\alpha$ and $p$, this Markov chain converges
quickly. Note that their work cannot be applied to all $\alpha$, and so a
major difficulty in our work is to show that there are not so many exceptional
$\alpha$, and that they can be dealt with separately. Once the Markov chain
equidistributes, we can immediately conclude that $\alpha$ is a root of $f(x)$
with probability $q^{-1}$, matching the probability for the uniform model
$\overline{f}(x)$.

In fact, while we ultimately avoid studying these random walks, we use the
same techniques, extending them to handle the joint distribution of
$f(\alpha_{i})$ at multiple roots $\alpha_{i}$, along with the derivatives of
$f$. We ultimately obtain two bounds on the Fourier coefficients for the
distribution of the $f(\alpha_{i})$, given by Proposition 3.2 and Theorem 4.1.

The first bound we obtain, Proposition 3.2, morally comes from the fact that
these Markov chains converge to stationarity in at most order $q^{2}$ steps.
This already allows us to handle the case of constant $q$, and is effective
for small $q$.

The other bound, Theorem 4.1 uses a bound originally due to Konyagin, see [6,
7], and so morally comes from the fact that if $q=p$ is prime, for most
$\alpha$, these Markov chains converge to stationarity in order
$\log^{2}p\log^{5}\log p$ steps. We cannot use the more precise techniques
that give the sharper bounds obtained in [7, 6, 15], as these do not extend as
readily to handle multiple roots or derivatives. In particular, when
considering derivatives, the measures one considers lack the self-similarity
property that was crucial in the analysis done in [7], but Konyagin’s argument
still works.

This lets us handle roots of high multiplicative order. We then handle the
remaining roots by showing that they do not appear with high probability, and
this requires that $p$ is large enough. This method is effective up to $p\leq
e^{n^{c}}$ for reasonable $c>0$, but gives a polynomial rather than
exponential error bound.

The second bound, Theorem 4.1, is more involved, and relies on an argument
originally due to Konyagin [26] which shows that the $\alpha$ for which the
Markov chain above mixes slowly must have low multiplicative order. We extend
this argument to handle multiple the values of $f$ and its derivatives at
multiple roots, giving us information on their joint distribution. This allows
us to effectively approximate the joint moments of the $N_{i}(f)$ and
$N_{i}^{\prime}(f)$ by the same moments for the uniform model.

Once we have these moment estimates, we then use these to obtain a bound on
the total variation distance via the following proposition, which we could not
find in the literature (although similar ideas have appeared, see e.g. [23])
and may be of independent interest.

######  Proposition 1.18.

Let $Z=(Z_{1},\dotsc,Z_{N})$ and
$Z^{\prime}=(Z_{1}^{\prime},\dotsc,Z_{N}^{\prime})$ be two integer-valued
random vectors. Fix $H\in\mathbb{N}$ and let

(1.1) $\varepsilon=\sup_{\sum k_{i}\leq
H}\left|\operatorname{\mathbb{E}}\left(\prod_{i=1}^{N}Z_{i}^{k_{i}}\right)-\operatorname{\mathbb{E}}\left(\prod_{i=1}^{N}Z_{i}^{\prime
k_{i}}\right)\right|.$

Suppose that

(1.2)
$\operatorname{\mathbb{E}}\left(\sum_{i=1}^{N}|Z_{i}|\right)^{H},\operatorname{\mathbb{E}}\left(\sum_{i=1}^{N}|Z^{\prime}_{i}|\right)^{H}\leq
C.$

Then for all $a\in\mathbb{Z}^{N}$,

$|\operatorname{\mathbb{P}}[Z=a]-\operatorname{\mathbb{P}}[Z^{\prime}=a]|\leq
N^{H-1}e^{\pi}\varepsilon+2\frac{C\pi^{H}}{H!}.$

######  Remark 1.19.

Note that Proposition 1.18 must be summed over the support of $Z$ and
$Z^{\prime}$ to obtain a total variation bound, so in practice $\varepsilon$
must be very small or one needs good tail bounds for this bound to be useful.
The easiest case is when $\varepsilon=0$ and the moments match exactly. In our
application, $\varepsilon$ will be exponentially small, and so we must
carefully pick our parameters to ensure that the bound is effective. This
result can also be sharpened in the case when the errors are not uniformly
small.

######  Remark 1.20.

We do not explicitly make the connection, but our results imply mixing time
bounds of order $\log^{2}p\log^{5}\log p$ for certain higher-dimensional
analogues of the $ax+b$ process. These are weaker than the expected order
$\log p\log\log p$ mixing time, but this improvement would not give very much
in our setting, improving the dependence on $p$ in the upper bounds. Recent
work of Dubail and Massoulié [13] establishes this bound for a large class of
higher-dimensional analogues, but unfortunately their results do not apply to
our setting, and their bounds do not give a uniform control which is necessary
for our applications. Nevertheless, it would be interesting to see if these
ideas, or the more refined ideas giving the $\log p\log\log p$ mixing time
bound for the $1$-dimensional $ax+b$ chain, could be used in our setting.

###  1.5. Related work

Our work seems morally related to results on universality for random
polynomials over $\mathbb{R}$ or $\mathbb{C}$. Here, the comparison is with a
random polynomial with Gaussian coefficients. We do not attempt to review all
the literature, and refer the reader to the cited papers for further
background and references. The limiting density for roots [22] and local
correlations [34, 11] are known to exhibit universal behaviour. More recently,
it has been established that the moduli of the roots converge to a Poisson
point process [9], again matching the behaviour of the Gaussian model [29]. It
is interesting to note that [8, 9] use similar techniques, studying random
walks related to their random polynomial and their derivatives, as well as
using Fourier-theoretic arguments.

There has also been some recent progress on the roots of random $p$-adic
polynomials. Recent work of Shmueli [32] found the expected number of roots
for a random polynomial over $\mathbb{Q}_{p}$ whose coefficients are randomly
drawn from $\mathbb{Z}_{p}$, but are not necessarily Haar-distributed. There
are some striking similarities with the finite field case that we study, and
it would be interesting to see if some of our results and methods could be
used to approach this problem as well.

Random matrices over finite fields have also been quite intensely studied
recently, and many properties of uniform random matrices over finite fields
are now known to be universal. We will only survey some recent results, and
refer the reader to [27] for more references.

Recent work of Luh, Meehan and Nguyen [27] show that the rank distribution and
the small factors of the characteristic polynomial of a random matrix over
$\mathbb{F}_{p}$ are universal, at least when $p$ is fixed. The analogous
results [33, 30] for the uniform model were known much earlier. Eberhard [14]
strengthened the error bounds and extended some of these results to
$\mathbb{F}_{q}$, and Ferber, Jain, Sah and Sawhney [17] showed similar
results for the rank distribution of symmetric matrices. These latter two
works were motivated by the study of random $\pm 1$ matrices over
$\mathbb{Z}$.

Finally, the distribution of factors for uniformly random monic polynomials is
exactly equal to the distribution of cycles in a deck of cards after a
$q$-shuffle (a generalization of a riffle shuffle) [10], and this has been
extended to other Coxeter groups [18, 19]. It’s unclear how to interpret non-
uniform random polynomials via card shuffling, but it would be interesting if
a connection could be made. It would also be interesting to see if
$a$-shuffles had some universal behavior.

###  1.6. Outline

The rest of the paper is structured as follows. In Section 2, we set some
notation and recall basic facts about Mahler measure and the Hasse derivative.
In Section 3, we establish similar bounds when $q$ is small, and also
establish a Halász-type bound for the probability that a given polynomial
divides $f$. In Section 4, we establish bounds on Fourier coefficients
effective when $q=p$ is prime and large, adapting an argument originally due
to Konyagin [26]. In Section 5, we prove Proposition 1.18 and give moment
bounds for the uniform model. In Section 6, we show that the joint moments of
the $N_{i}$ and $N_{i}^{\prime}$ for $f$ and $\overline{f}$ are close. In
Section 7, we state and prove our strongest results, and prove the corollaries
stated in the introduction. Finally, in Section 8, we present some numerical
simulations which support our results and suggest some interesting directions
for further study.

##  2\. Preliminaries

In this section, we set notation and review some basic facts about Mahler
measure and Hasse derivatives. The reader may safely skip this section and
refer back when needed.

###  2.1. Notation

Throughout, $\operatorname{Tr}$ will denote the field trace of a finite
extension $\mathbb{F}_{q^{e}}/\mathbb{F}_{q}$, with the extension clear from
context. We define $e_{p}(x)=\exp\left(\frac{2\pi ix}{p}\right)$. We will let
$C$ and $c$ denote a large and small positive constant respectively, that may
change from line to line. We use $f\ll g$ or $f=O(g)$ to denote that there
exists a positive constant $C$ such that $f\leq Cg$.

###  2.2. Assumptions on parameters

Throughout this paper, we will let $f$ denote a random polynomial with
coefficients drawn independently from a distribution $\mu$. We define
parameters $n$, $N$, $H$, $K$. We will let $n$ denote the degree of $f$, $N$
the degree of the largest degree roots we wish to study, $H$ the largest
number of distinct roots we wish to study, and $K$ the highest order Hasse
derivative we wish to study. We will eventually assume that

(2.1) $N=n^{c},\qquad H=N\log n,\qquad K=N\log^{2}n,\qquad p\leq e^{n^{c}}$

with $c>0$ some explicit constants that will depend on whether we count
irreducible factors with or without multiplicity. We will only need to take
$K>0$ when we study irreducible factors with multiplicity.

###  2.3. Mahler measure

The _Mahler measure_ of a polynomial $f(x)\in\mathbb{C}[x]$ with
$f(x)=c_{d}\prod_{i=1}^{d}(x-\alpha_{i})$, denoted $M(f)$, is defined by

$M(f)=|c_{d}|\prod_{i=1}^{d}\max(1,|\alpha_{i}|)=\exp\left(\frac{1}{2\pi}\int_{0}^{2\pi}\log|f(e^{i\theta})|d\theta\right).$

It was previously used by Breuillard and Varjú in their study of certain
random walks over finite fields [6, 7] and we borrow their ideas heavily. See
Section 1.6 of [5] for some further background.

Mahler measure is multiplicative, $M(fg)=M(f)M(g)$, and if
$f(x)=\sum_{i=0}^{d}c_{i}x^{i}$, there is also an upper bound

$M(f)\leq\sqrt{\sum_{0\leq i\leq d}c_{i}^{2}}.$

The key property of Mahler measure we exploit is that it provides a way to
detect if $f$ is a cyclotomic polynomial (or $f(x)=x$) when $f$ is a monic
irreducible integer polynomial. Specifically, if $f\in\mathbb{Z}[x]$ is monic
and irreducible of degree $d$, then by Dobrowolski’s bound [12], either

$M(f)\geq 1+c\left(\frac{\log\log d}{\log d}\right)^{3},$

or $f(x)$ is either a cyclotomic polynomial, or $f(x)=x$. If $f$ is a
cyclotomic polynomial, then we can obtain useful bounds on its multiplicative
order.

###  2.4. The Hasse derivative

We would like to study the multiplicity of roots of a polynomial $f$ through
studying the roots of $f$ and its derivatives. However, since the $p$th
derivative of any polynomial with coefficients in $\mathbb{F}_{p}$ is $0$, we
use the following alternative. See Section 5.10 of [21] for further details.

######  Definition 2.1 (Hasse derivative).

Let $f(x)=\sum c_{i}x^{i}\in R[x]$ be a polynomial over a ring $R$ (for us,
$R=\mathbb{Z}$ or $R=\mathbb{F}_{q}$). We define the $k$th _Hasse derivative_
of $f$, denoted $D^{(k)}f(x)$, by

$D^{(k)}f(x)=\sum c_{i}{i\choose k}x^{i-k},$

with the understanding that if $k>i$ then ${i\choose k}=0$.

We will only need the following basic but useful properties.

  * •

$D^{(k)}(fg)(x)=\sum_{i+j=k}D^{(i)}f(x)D^{(j)}g(x)$.

  * •

$f(x)=\sum_{k=0}^{\deg(f)}D^{(k)}f(\alpha)(x-\alpha)^{k}$.

  * •

$f(x)$ has a root $\alpha$ of multiplicity $r$ if and only if
$D^{(k)}f(\alpha)=0$ for all $k\leq r$.

If $\alpha$ generates an extension $\mathbb{F}_{p^{e}}$ of $\mathbb{F}_{p}$,
then $1,\dotsc,\alpha^{e-1}$ forms a basis. The following lemma extends this
to multiple roots $\alpha_{j}$, along with derivatives of the monomials.

######  Lemma 2.2.

Let $\alpha_{j}\in\mathbb{F}_{q^{e_{j}}}$ for $j=1,\dotsc,n$, so that each
$\alpha_{j}$ does not lie in any smaller subfield, and none of the
$\alpha_{j}$ are Galois conjugates. For each $j$, let $k_{j}\in\mathbb{N}$.
Let $d=\sum_{1\leq j\leq n}e_{j}(k_{j}+1)$. Let $m\geq 0$.

The vectors $(\alpha_{j}^{i-k}{i\choose k})\in\prod_{j}\prod_{k\leq
k_{j}}\mathbb{F}_{q^{e_{j}}}$ for $i=m,\dotsc,m+d-1$ form a basis.

###### Proof.

Suppose that $\sum_{i=m}^{m+d-1}c_{i}\alpha_{j}^{i-k}{i\choose k}=0$ for all
$k\leq k_{j}$ and $j\leq n$. Then we have that the polynomial
$f(x)=\sum_{i=m}^{m+d-1}c_{i}x^{i}$ satisfies $D^{(k)}f(\alpha_{j})=0$ for all
$k\leq k_{j}$ and $j\leq n$. This implies in particular that each $\alpha_{j}$
is a root of $f$ of multiplicity at least $k_{j}+1$. As the $\alpha_{j}$ are
not Galois conjugates, we show this forces $f(x)=0$. Since any non-zero
polynomial having all the $\alpha_{j}$ roots of multiplicity $k_{j}+1$
respectively must be divisible by the minimal polynomials of the $\alpha_{j}$
at least $k_{j}+1$ times, such a polynomial must have a factor of degree at
least $\sum e_{j}(k_{j}+1)=d$ corresponding to these roots. Note that $f$ has
degree at most $m+d-1$, and is divisible by $x^{m}$, which implies that
$f(x)=0$, and so $c_{i}=0$ for all $i$. ∎

##  3\. Uniform estimates

###  3.1. General setup

Throughout the next few sections, we fix the following notation and general
setup. Fix some prime $p$, $q=p^{e}$ for some positive integer $e$. Let
$H\in\mathbb{N}$ and $\alpha_{i}\in\mathbb{F}_{q^{e_{i}}}$ for $i\leq H$, with
the $\alpha_{i}$ not lying in a smaller subfield, and none a Galois conjugate
of another. These will be the roots we will consider. Let
$\mathcal{K}_{i}\subseteq\mathbb{N}$ for $i\leq H$, which will be the set of
derivatives we consider for $\alpha_{i}$, let $K_{i}=\max\mathcal{K}_{i}$, and
let $k^{*}=\max_{i}K_{i}+1$ denote the largest derivative considered. Let
$d=\sum_{1\leq i\leq H}e_{i}(K_{i}+1)$. Let
$\beta_{i,k}\in\mathbb{F}_{q^{e_{i}}}$ for $k\in\mathcal{K}_{i}$ and $i\leq
H$, with all $\beta_{i,k}$ non-zero. Let
$V=\prod_{i}\left(\mathbb{F}_{q^{e_{i}}}\right)^{\mathcal{K}_{i}}$.

Let $X_{i}$ be a sequence of independent and identically distributed
$\mathbb{F}_{q}$-valued random variables, and let $\mu$ denote its
distribution. Let $\eta=1-\max_{V\subseteq\mathbb{F}_{q}}\mu(V)$, where $V$ is
taken over all affine $\mathbb{F}_{p}$ subspaces. We wish to study the
distribution of $\sum_{i=0}^{n}X_{i}D^{(k)}(\alpha_{j}^{i})$ for $j\leq H$ and
$k\in\mathcal{K}_{j}$ as a random variable in $V$, and we let $\nu_{n}$ denote
its distribution.

In this section, we obtain some uniform estimates that hold for any roots
$\alpha$. While these are not strong enough when $p$ is large, they are
necessary to handle certain low-order roots that cannot be handled in any
other way.

###  3.2. Fourier bounds

We first obtain uniform bounds on the Fourier coefficients of $\nu_{n}$.

######  Lemma 3.1.

Let $d_{1},d_{2}\in\mathbb{N}$, and let
$T:\mathbb{F}_{q}^{d_{1}}\to\mathbb{F}_{q}^{d_{2}}$ be a surjective linear
map. Let $\mu$ be a probability measure on $\mathbb{F}_{q}$ whose support
generates $\mathbb{F}_{q}$. Suppose that for each $\beta\in\mathbb{F}_{q}$,
the fraction of $i\in[d_{1}]$ such that $\beta\cdot Tv_{i}=0$ is at most
$1-\gamma$ if $\beta\neq 0$, where $v_{i}$ is the standard basis for
$\mathbb{F}_{q}^{d_{1}}$. Define $\eta$ to be the minimum probability of $\mu$
in the complement of a proper $\mathbb{F}_{p}$ affine subspace of
$\mathbb{F}_{q}$. Then for $\beta\neq 0$,

$\widehat{T_{*}\mu^{\otimes d_{1}}}(\beta)\leq(1-\eta/p^{2})^{\gamma d_{1}},$

where $T_{*}\mu^{\otimes d_{1}}$ denotes the pushforward under $T$ of the
$d_{1}$-fold product measure of $\mu$ on $\mathbb{F}_{q}^{d_{1}}$.

###### Proof.

We have

$\begin{split}\widehat{T_{*}\mu^{\otimes
d_{1}}}(\beta)&=\sum_{x\in\mathbb{F}_{p}^{d_{1}}}\left(\prod_{i=1}^{d_{1}}\mu(x_{i})\right)e_{p}(\operatorname{Tr}(\beta\cdot
T(x)))\\\
&=\sum_{x\in\mathbb{F}_{p}^{d_{1}}}\prod_{i=1}^{d_{1}}\mu(x_{i})e_{p}(\operatorname{Tr}(x_{i}\beta\cdot
T(v_{i})))\\\ &=\prod_{i=1}^{d_{1}}\widehat{\mu}(\beta\cdot
Tv_{i}).\end{split}$

By the definition of $\eta$, $|\widehat{\mu}(\beta\cdot
Tv_{i})|\leq|1-\eta+\eta e^{2\pi i/p}|\leq 1-\eta/p^{2}$ if $\beta\cdot
Tv_{i}\neq 0$. By assumption, this happens at least $\gamma d_{1}$ times. ∎

Combining Lemma 2.2 and Lemma 3.1, we obtain the following bounds.

######  Proposition 3.2.

With the notation of Section 3.1, we have

$|\widehat{\nu_{n}}(\beta)|\leq e^{-\frac{\eta n}{dp^{2}}}$

where $\eta=1-\max_{V\subsetneq\mathbb{F}_{q}}\mu(V)$.

###### Proof.

We let $T:\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}^{d^{\prime}}$ (where
$d^{\prime}=\sum e_{i}|\mathcal{K}_{i}|$) be the map taking
$(x_{0},\dotsc,x_{n})$ to the vector $(D^{(k)}f(\alpha_{i}))_{i\leq
H,k\in\mathcal{K}_{i}}$, where $f(\alpha)=\sum x_{i}\alpha^{i}$. By Lemma 2.2,
this map is surjective, and moreover, $Tv_{i}$ for $i=j,j+1,\dotsc,j+d-1$
spans $\mathbb{F}_{p}^{d^{\prime}}$. Thus for each non-zero $\beta$, there is
at least one $i$ for which $\beta\cdot Tv_{i}\neq 0$, and so Lemma 3.1 gives
the desired bound. ∎

###  3.3. Halász-type bounds

Next, we establish the following Halász-type bound for the probability that a
random polynomial $f(x)$ has some collection of roots with given
multiplicities. While we only need the case of a single root without
multiplicity, we believe the stronger result may be of some independent
interest. We remark that there is an extensive literature on anti-
concentration type bounds, and we refer readers to the survey [31]. In the
setting of torsion abelian groups, Halász-type bounds and Littlewood-Offord
inverse results are obtained in [25]. In our case, we take direct advantage of
properties of the power sequence to obtain the desired bound in Proposition
3.3. We remark that one can also follow proof of typical Littlewood-Offord
results [31] combined with inverse results of Freiman-type in general abelian
groups [20] to obtain an upper bound in Proposition 3.3 of the form
$p^{-d}+O_{\eta}(n^{-\lambda_{d}})$ where $\lambda_{d}\to\infty$. For us, the
bound provided in Proposition 3.3 with an exponential decay in $d$ is more
convenient to use and leads to better quantitative bounds in our settings.

######  Proposition 3.3.

Let $f(x)=\sum_{1\leq i\leq n}\varepsilon_{i}x^{i}$ be a random polynomial of
degree $n$ in $\mathbb{F}_{p}[x]$, with $\varepsilon_{i}$ independent and
distributed according to $\mu$. Let $\alpha_{1},\dots,\alpha_{H}$ be so that
$\alpha_{j}$ in $\mathbb{F}_{p^{e_{j}}}$ and $\alpha_{j}$ does not lie in any
proper subfield of $\mathbb{F}_{p^{e_{j}}}$. Let $d=\sum_{j\leq
H}e_{j}(K_{j}+1)$. Then

$\operatorname{\mathbb{P}}\left[(x-\alpha_{i})^{K_{i}}|f(x)\text{ }\forall
i\right]\leq\left(\frac{1}{p}+C\eta^{-\frac{1}{2}}\left\lfloor\frac{n}{d}\right\rfloor^{-\frac{1}{2}}\right)^{d}.$

for some absolute constant $C$.

###### Proof.

For simplicity, we assume $n$ is a multiple of $d$. We have

$\begin{split}\operatorname{\mathbb{P}}\left[(x-\alpha_{i})^{K_{i}}|f(x)\text{
}\forall
i\right]&=\frac{1}{p^{d}}\sum_{\beta}\prod_{i}\operatorname{\mathbb{E}}\left[e_{p}\left(\sum_{j\leq
H,k_{j}\leq
K_{j}}\operatorname{Tr}(\beta_{j,k_{j}}\varepsilon_{i}D^{(k_{j})}(\alpha_{j}^{i}))\right)\right].\end{split}$

By Hölder’s inequality,

$\begin{split}&\sum_{\beta}\prod_{i}\left|\operatorname{\mathbb{E}}\left[e_{p}\left(\sum_{j\leq
H,k_{j}\leq
K_{j}}\operatorname{Tr}(\beta_{j,k_{j}}\varepsilon_{i}D^{(k_{j})}(\alpha_{j}^{i}))\right)\right]\right|\\\
&\leq\prod_{i=1}^{n/d}\left(\sum_{\beta}\prod_{h=0}^{d-1}\left|\operatorname{\mathbb{E}}\left[e_{p}\left(\sum_{j\leq
H,k_{j}\leq
K_{j}}\operatorname{Tr}(\beta_{j,k_{j}}\varepsilon_{di+h}D^{(k_{j})}(\alpha_{j}^{di+h}))\right)\right]\right|^{\frac{n}{d}}\right)^{\frac{d}{n}}\\\
&\leq\max_{i}\sum_{\beta}\prod_{h=0}^{d-1}\left|\operatorname{\mathbb{E}}\left[e_{p}\left(\varepsilon_{di+h}\operatorname{Tr}\left(\sum_{j\leq
H,k_{j}\leq
K_{j}}\beta_{j,k_{j}}D^{(k_{j})}(\alpha_{j}^{di+h})\right)\right)\right]\right|^{\frac{n}{d}}.\end{split}$

By Lemma 2.2, the $d$ vectors $(D^{(k_{j})}(\alpha_{j}^{di+h}))_{j\leq
H,k_{j}\leq K_{j}}$ for $0\leq h\leq d-1$ (whose components are indexed by $j$
and $k_{j}$) form a basis. Let $\gamma_{h}$ be a dual basis with respect to
the non-degenerate pairing

$(x,y)\mapsto\operatorname{Tr}\left(\sum_{j\leq H,k_{j}\leq
K_{j}}x_{j,k_{j}}y_{j,k_{j}}\right)$

for this basis. Then writing $\beta=\sum c_{j}\gamma_{j}$, we have

$\begin{split}&\frac{1}{p^{d}}\sum_{\beta}\prod_{h=0}^{d-1}\left|\operatorname{\mathbb{E}}\left[e_{p}\left(\sum_{j\leq
H,k_{j}\leq
K_{j}}\operatorname{Tr}(\beta_{j,k_{j}}\varepsilon_{di+h}D^{(k_{j})}(\alpha_{j}^{di+h}))\right)\right]\right|^{\frac{n}{d}}\\\
=&\prod_{h=0}^{d-1}\left(\frac{1}{p}\sum_{c_{h}\in\mathbb{F}_{p}}\left|\operatorname{\mathbb{E}}\left[e_{p}\left(c_{h}\varepsilon_{di+h}\right)\right]\right|^{\frac{n}{d}}\right).\end{split}$

But each factor can be bounded by $p^{-1}+C\left(\frac{\eta
n}{d}\right)^{-\frac{1}{2}}$ (the proof can be found in Lemma 2.4 of [28] for
example), giving the desired bound. ∎

##  4\. Konyagin’s argument for derivatives

Recall the assumptions and notation of Section 3.1. In this section, we assume
that $q=p$ is prime. We will sometimes need to treat the $X_{i}$ as
$\mathbb{Z}$-valued random variables, and so we may lift $\mu$ to a measure on
$\mathbb{Z}$ supported on $[0,p-1]$ in the obvious way.

The goal of this section is to prove the following bound for the Fourier
coefficients of $\nu_{n}$.

######  Theorem 4.1.

Let $\nu_{n}$ and $\alpha_{i}$ be defined as in Section 3.1. There exists
$C>0$ such that if $n\geq Cd\log p\log(d\log p)$, then either

$|\widehat{\nu_{n}}(\beta)|\leq e^{\frac{\eta n}{Cd\log p\log^{5}(d\log p)}},$

for all $\beta$ whose components are all non-zero, or all $\alpha_{i}$ have
multiplicative order at most $Cd\log p\log(d\log p)$.

###  4.1. Bounds on Fourier coefficients

Our proof of Theorem 4.1 closely follows the proof of Proposition 25 in [6],
using an argument due to Konyagin [26].

Define

$S_{n}:=\sum_{i\leq
H}\sum_{k\in\mathcal{K}_{j}}\operatorname{Tr}\left(\beta_{i,k}\alpha_{i}^{n-k}{n\choose
k}\right).$

Recall that we have assumed $\beta_{j,k}\neq 0$ for all $j\leq H$ and
$k\in\mathcal{K}_{j}$.

######  Lemma 4.2.

Suppose that $f(x)=\sum_{i=0}^{n}a_{i}x^{i}\in\mathbb{F}_{p}[x]$ is of degree
$n$, and that $a_{0}S_{i}+\dotsc+a_{n}S_{i+n}=0$ for all
$i=i_{0},i_{0}+1,\dotsc,i_{0}+d-1$. Then $D^{(k)}f(\alpha_{j})=0$ for all $j$
and $k\leq K_{j}$. In particular, $a_{0}S_{i}+\dotsc+a_{n}S_{i+n}=0$ holds for
all $i$.

###### Proof.

The hypothesis is equivalent to the statement that

$\sum_{j}\sum_{k}\operatorname{Tr}\left(\beta_{j,k}D^{(k)}(f(x)x^{i})(\alpha_{j})\right)=0$

for $i=i_{0},\dotsc,i_{0}+d-1$. Expanding out the derivatives, we obtain

$\sum_{j}\sum_{k}\sum_{l_{1}+l_{2}=k}\operatorname{Tr}\left(\beta_{j,k}D^{(l_{1})}f(\alpha_{j})\alpha_{j}^{i-l_{2}}{i\choose
l_{2}}\right)=0.$

The vectors $(\alpha_{j}^{m-k}{m\choose k})\in\prod_{j}\prod_{k\leq
K_{j}}\mathbb{F}_{p^{e_{j}}}$ for $m=i_{0},\dotsc,i_{0}+d-1$ form a basis by
Lemma 2.2.

But the expression above can be written as

$\begin{split}&\sum_{j}\sum_{k}\sum_{l_{1}+l_{2}=k}\operatorname{Tr}\left(\beta_{j,k}D^{(l_{1})}f(\alpha_{j})\alpha_{j}^{i-l_{2}}{i\choose
l_{2}}\right)\\\
=&\sum_{j}\sum_{l_{2}}\operatorname{Tr}\left(\left(\sum_{k\geq
l_{2}}\beta_{j,k}D^{(k-l_{2})}f(\alpha_{j})\right)\alpha_{j}^{i-l_{2}}{i\choose
l_{2}}\right).\end{split}$

This implies that

$\sum_{k\geq l_{2}}\beta_{j,k}D^{(k-l_{2})}f(\alpha_{j})=0$

for all $j$ and $l_{2}$. This is a system of $K_{j}+1$ many variables (the
$D^{(k)}f(\alpha_{j})$), and it can be solved by back substitution since
starting from $l_{2}=K_{j}$, there is at most one new variable in each new
equation. It follows that $D^{(k)}f(\alpha_{j})=0$ for all $j\leq H$ and
$k\leq K_{j}$. ∎

For $X=(x_{0},\dotsc,x_{N})\in\mathbb{Z}^{N+1}$, we write $\Lambda_{E}(X)$ for
the set of polynomials $f(x)=\sum_{0\leq i\leq n}c_{i}x^{i}\in\mathbb{Z}[x]$,
such that $c_{0}x_{j}+\dotsc+c_{n}x_{j+n}=0$ holds for all $j\leq N-E$. When
$E=N$, we write $\Lambda(X)=\Lambda_{N}(X)$ denote the set of polynomials
$f(x)\in\Lambda_{deg(f)}(X)$. We now recall two results from [6] which we will
need to use.

######  Lemma 4.3 ([6, Lemma 27]).

With the same notations as above, if $f_{1},f_{2}\in\Lambda(X)$ and $\deg
f_{1}+\deg f_{2}\leq N$, then $\gcd(f_{1},f_{2})\in\Lambda(X)$.

######  Corollary 4.4 ([6, Corollary 28]).

Suppose that $\Lambda(X)$ contains a polynomial of degree at most $N/2$. Then
there exists a unique up to $\pm$ polynomial $f_{0}\in\Lambda(X)$ of minimal
degree with coprime coefficients, and $P\in\Lambda(X)$ if and only if
$f_{0}|P$ for $P$ such that $\deg(P)\leq N-\deg(f_{0})$.

We can now prove the key tool in the proof of Theorem 4.1.

######  Proposition 4.5.

Let $\widehat{S}_{n}$ denote the representative of $S_{n}$ in $[-p/2,p/2]$.

Let $L\geq 200d\log p\log(d\log p)$ Suppose that

$\sum_{n=n_{0}}^{n_{0}+L}(\widehat{S}_{n})^{2}\leq\frac{p^{2}}{8\log(4L)}.$

Then for each $j$, there is a polynomial $f_{j}$ of degree at most $3d\log p$
and Mahler measure at most $(d\log p)^{30d\log p/L}$ such that
$f_{j}(\alpha_{j})=0$.

###### Proof.

Set $E=3\lceil d\log p\rceil$. We first show that there is a polynomial
$f_{1}\neq 0$ of degree at most $E$ such that
$f_{1}\in\Lambda_{E}(\\{\widehat{S}_{n}\\}_{n=n_{0}}^{n_{0}+L})$.

Let $X_{0},\dotsc,X_{E}$ be a sequence of independent random variables uniform
on $\\{-1,1\\}$. By Hoeffding’s inequality,

$\operatorname{\mathbb{P}}\left[\left|\sum_{0\leq i\leq
E}X_{i}\widehat{S}_{i+n}\right|\geq\frac{p}{2}\right]\leq\frac{1}{2L}$

for any $n=n_{0},\dotsc,n_{0}+L-E$. By a union bound,

$\operatorname{\mathbb{P}}\left[\left|\sum_{0\leq i\leq
E}X_{i}\widehat{S}_{i+n}\right|\geq\frac{p}{2}\text{ for some
$n$}\right]\leq\frac{1}{2},$

and so the set $\Omega$ of $x=(x_{0},\dotsc,x_{E})\in\\{-1,1\\}^{E+1}$ such
that $\left|\sum x_{i}\widehat{S}_{i+n}\right|<\frac{p}{2}$ for all $n$ has
size at least $2^{E}\geq p^{d}$. Then by the pigeonhole principle, there
exists $x,y\in\Omega$, $x\neq y$, such that

$\sum x_{i}\widehat{S}_{i+n}=\sum y_{i}\widehat{S}_{i+n}\pmod{p}$

for $n=n_{0},\dotsc,n_{0}+d-1$.

Let $a_{i}=(x_{i}-y_{i})/2$. By Lemma 4.2, we have $\sum
a_{i}\widehat{S}_{i+n}=0$ for all $n$. Then $f_{1}(x)=\sum
a_{i}x^{i}\in\Lambda_{E}(\\{\widehat{S}_{n}\\}_{n=0}^{L})\subseteq\Lambda(\\{\widehat{S}_{n}\\}_{n=0}^{\lceil
2L/3\rceil})$. Since $\deg f_{1}\leq\lceil 2L/3\rceil/2$, by Corollary 4.4, we
have a polynomial $f_{0}\in\Lambda(\\{\widehat{S}_{n}\\}_{n=0}^{\lceil
2L/3\rceil})$ with relatively prime coefficients and of minimal degree, unique
up to a sign.

By Lemma 4.2, we have $f_{0}(\alpha_{j})=0$ for all $j$, and so for each
$\alpha_{j}$, there is some $f_{j}$ an irreducible (over $\mathbb{Z}$) factor
of $f_{0}$ such that $f_{j}(\alpha_{j})=0$.

Now fix $j$, and note that $\deg f_{j}\leq E$, so what remains is to show
$M(f_{j})\leq(d\log p)^{30d\log p/L}$. Let $\gamma_{i}$ denote the roots of
$f_{j}$. Let $s=L/6E$. Then by Lemma 4.6, there exists a prime $q\in(s,2s]$
such that $\gamma_{k}/\gamma_{l}$ is not a $q$th root of unity for all $k\neq
l$. This implies that the $\beta_{i}^{q}$ are distinct.

By the same argument as above, we can find a polynomial
$f_{2}(x)=g_{2}(x^{q})$ with $g_{2}=\sum b_{i}x^{i}$ of degree at most $E$
having coefficients in $\\{-1,0,1\\}$, and such that $\sum
b_{i}\widehat{S}_{iq+n}=0$ for all $n=0,\dotsc,L-Eq$. This implies that
$f_{2}\in\Lambda_{Eq}(\\{\widehat{S_{n}}\\}_{n=0}^{L}\subseteq\Lambda(\\{\widehat{S}_{n}\\}_{n=0}^{\lceil
2L/3\rceil})$ as $Eq\leq L/3$. By Corollary 4.4, as $\lceil 2L/3\rceil\geq
2Eq$, we have $f_{0}$ divides $f_{2}$. Then the $\beta_{i}^{q}$ are all roots
of $g_{2}$, and so $M(f_{j})\leq
M(g_{2})^{\frac{1}{q}}\leq(E+1)^{\frac{1}{2q}}$ using $M(g_{2})\leq\sqrt{\sum
b_{i}^{2}}$. Since $q\geq L/6E$, we have $M(f_{j})\leq(d\log p)^{30d\log
p/L}$. ∎

Finally, we need the following lemma to prove Theorem 4.1.

######  Lemma 4.6 ([6, Lemma 26]).

Let $a_{1},\dotsc,a_{n}$ be the roots of an irreducible polynomial
$f\in\mathbb{Z}[x]$. Let $s\geq 4\log n$. If $n$ is larger than some absolute
constant, then there exists a prime $q\in(s,2s]$ such that $a_{i}/a_{j}$ is
not a $q$-th root of unity for any $i\neq j$.

###### Proof of Theorem 4.1.

Take $L=Cd\log p\log^{4}(d\log p)$. First, suppose that

(4.1) $\sum_{n=n_{0}}^{n_{0}+L}(\widehat{S}_{n})^{2}>\frac{p^{2}}{8\log(4L)}$

for all $n_{0}$. Then we claim that

(4.2)
$|\widehat{\nu_{n}}(\beta)|\leq\exp\left(\frac{n(1-\|\mu\|_{2}^{2})}{Cd\log
p\log^{5}(d\log p)}\right)$

for some absolute constant $C>0$. The result follows upon noticing that
$1-\|\mu\|_{2}^{2}\geq 1-\sum_{x}\mu(x)(1-\eta)=\eta$.

To see that (4.2) holds, note that

$|\widehat{\nu_{n}}(\beta)|=\prod_{m=1}^{\frac{n}{L+1}}|\widehat{\mu_{m}}(\beta)|,$

where $\mu_{m}$ is the distribution of the random variable

$\left(X_{m}D^{(k)}(\alpha_{j}^{m})\right)_{j\leq H,k\in\mathcal{K}_{j}}\in
V.$

First, note that $\cos(2\pi x)\leq 1-8\|x\|^{2}$ for all $x$, where $\|x\|$
denotes the distance to the closest integer. Then if
$\varepsilon_{1},\varepsilon_{2}$ are independently drawn from $\mu$,

$\begin{split}1-|\widehat{\mu_{m}}(\beta)|^{2}&=1-\operatorname{\mathbb{E}}\left[e_{p}\left(\sum_{j}\sum_{k\in\mathcal{K}_{j}}\operatorname{Tr}\left(\beta_{j,k}(\varepsilon_{1}-\varepsilon_{2})\alpha_{j}^{m-k}{m\choose
k}\right)\right)\right]\\\
&=1-\sum_{x}\operatorname{\mathbb{P}}[\varepsilon_{1}-\varepsilon_{2}=x]\cos\left(\frac{2\pi}{p}\sum_{j}\sum_{k\in\mathcal{K}_{j}}\operatorname{Tr}\left(\beta_{j,k}x\alpha_{j}^{m-k}{m\choose
k}\right)\right)\\\ &\geq 8\sum_{x\neq
0}\operatorname{\mathbb{P}}[\varepsilon_{1}-\varepsilon_{2}=x]\left\|\frac{1}{p}\sum_{j}\sum_{k\in\mathcal{K}_{j}}\operatorname{Tr}\left(\beta_{j,k}x\alpha_{j}^{m-k}{m\choose
k}\right)\right\|^{2}\end{split}$

and so (after replacing the $\beta_{j,k}$ with $x\beta_{j,k}$),

$|\widehat{\mu_{m}}(\beta)|\leq\exp\left(-4\sum_{x\neq
0}\operatorname{\mathbb{P}}[\varepsilon_{1}-\varepsilon_{2}=x]\frac{\widehat{S}_{m}^{2}}{p^{2}}\right)\leq\exp\left(-4\frac{(1-\|\mu\|_{2}^{2})\widehat{S}_{m}^{2}}{p^{2}}\right).$

But (4.1) gives a uniform bound, and so by grouping the
$|\widehat{\mu_{m}}(\beta)|$ into blocks of length $L$, we obtain

$|\widehat{\mu_{n}}(\beta)|\leq\exp\left(\frac{n(1-\|\mu\|_{2}^{2})}{L\log
L}\right)\leq\exp\left(\frac{n(1-\|\mu\|_{2}^{2})}{Cd\log p\log^{5}(d\log
p)}\right)$

as required.

Otherwise, if there is an $n_{0}$ such that $\eqref{eq: large S_n}$ does not
hold, by Proposition 4.5, for each $\alpha_{j}$, there exists a polynomial
$f_{j}\in\mathbb{Z}[x]$ of degree at most $3d\log p$ with
$f_{j}(\alpha_{j})=0$ and

$M(f_{j})\leq(d\log p)^{\frac{30d\log p}{L}}\leq e^{\frac{1}{Cd\log
p\log^{3}(d\log p)}}.$

But by Dobrowolski’s bound [12], either

$M(f_{j})\geq e^{c\frac{\log^{3}\log\deg f_{j}}{\log^{3}\deg f_{j}}}\geq
e^{c\frac{1}{\log^{3}(d\log p)}}$

for some absolute constant $c>0$, or $f_{j}$ is a product of cyclotomic
polynomials. By taking $C$ large enough, we ensure the latter, and so
$\alpha_{j}$ is the root of a cyclotomic polynomial of degree at most $3d\log
p$. Since a cyclotomic polynomial of order $n$ has degree
$\phi(n)\geq\frac{cn}{\log\log n}$ for some $c>0$, this implies $\alpha_{j}$
has order at most $Cd\log p\log(d\log p)$ for some constant $C>0$. ∎

##  5\. A total variation bound in terms of moments

We begin by proving Proposition 1.18.

###### Proof of Proposition 1.18.

By Fourier inversion,

$\begin{split}&|\operatorname{\mathbb{P}}[Z=a]-\operatorname{\mathbb{P}}[Z^{\prime}=a]|\\\
=&\left|\frac{1}{(2\pi)^{N}}\int_{[-\pi,\pi]^{N}}(\operatorname{\mathbb{E}}[e^{i\theta\cdot
Z}]-\operatorname{\mathbb{E}}[e^{i\theta\cdot Z^{\prime}})]e^{-i\theta\cdot
a}d\theta\right|\\\
\leq&\frac{1}{(2\pi)^{N}}\int_{[-\pi,\pi]^{N}}\sum_{k=0}^{H-1}\frac{|\operatorname{\mathbb{E}}(i\theta\cdot
Z)^{k}-\operatorname{\mathbb{E}}(i\theta\cdot Z^{\prime})^{k}|}{k!}\\\
&\qquad\qquad+\operatorname{\mathbb{E}}\left|\sum_{k=H+1}^{\infty}\frac{(i\theta\cdot
Z)^{k}}{k!}\right|+\operatorname{\mathbb{E}}\left|\sum_{k=H+1}^{\infty}\frac{(i\theta\cdot
Z^{\prime})^{k}}{k!}\right|d\theta\end{split}$

The first term is bounded by $N^{H-1}e^{\pi}\varepsilon$ by expanding the
powers and using (1.1). The second and third terms are bounded by
$\frac{C\pi^{H}}{H!}$ by Taylor’s theorem and (1.2). ∎

To apply Proposition 1.18, we will need an estimate for the moments of
$\sum_{i\leq N}N_{i}(\overline{f})$ under the uniform model to bound $C$.

######  Lemma 5.1.

Let $\overline{f}$ be a uniformly random monic polynomial of degree $n$ in
$\mathbb{F}_{q}[x]$. Then for all $H$ and $N$ with $H>\log(N+1)$,

$\operatorname{\mathbb{E}}\left(\left(\sum_{i\leq
N}N_{i}(\overline{f})\right)^{H}\right)\leq\left(\frac{H}{\log
H-\log\log(N+1)}\right)^{H}.$

###### Proof.

Note that it suffices to study the same problem for $\overline{f}$ a uniform
monic random polynomial, since the bound is uniform in $n$. Let $X=\sum_{i\leq
N}N_{i}(\overline{f})$ be the total number of distinct irreducible factors of
a uniformly random monic polynomial up to degree $N$. The number of distinct
irreducible factors of degree $i$ has the generating function (see [24] for
example)

$D(y;z)=\sum_{g}y^{\deg(g)}\prod
z_{i}^{N_{i}(g)}=\prod\left(1+\frac{z_{i}y^{i}}{1-y^{i}}\right)^{\pi(i)},$

where $\pi(i)$ denotes the number of monic irreducible polynomials of degree
$i$ in $\mathbb{F}_{q}[x]$. Then

$\operatorname{\mathbb{E}}[X^{H}]=H![t^{H}][y^{n}]D(y/q;e^{t},\dotsc,1,\dotsc),$

where $z_{i}=e^{t}$ for all $i\leq N$, and $1$ otherwise, and $[z^{n}]F(z)$
denotes the coefficient of $z^{n}$ in the power series $F(z)$.

Given two formal power series $F$ and $G$, write $F\preceq G$ if all
coefficients of $F$ are at most the corresponding coefficients in $G$. It can
be seen that this is a partial order which respects the ring structure on
formal power series, and respects composition when the coefficients are non-
negative. Also, we have

$\left(1+\frac{x}{n}\right)^{n}\preceq e^{x}.$

Now as

$D(y/q;1,\dotsc)=\prod_{i}\left(\frac{1}{1-(y/q)^{i}}\right)^{\pi(i)}=\frac{1}{1-y},$

we have

$\begin{split}D(y/q;e^{t},\dotsc,1,\dotsc)&=\frac{1}{1-y}\prod_{i=1}^{N}\left(1+(e^{t}-1)(y/q)^{i}\right)^{\pi(i)}\\\
&\preceq\frac{1}{1-y}\exp\left((e^{t}-1)\sum_{i\leq
N}\frac{y^{i}}{q^{i}}\pi(i)\right)\\\
&\preceq\frac{1}{1-y}\exp\left((e^{t}-1)\sum_{i\leq
N}\frac{y^{i}}{i}\right)\end{split}$

since $\pi(i)\leq q^{i}/i$. Then

$\begin{split}[t^{H}][y^{N}]\frac{1}{1-y}\exp\left((e^{t}-1)\sum_{i\leq
N}\frac{y^{i}}{i}\right)&=\sum_{i=0}^{N}[y^{i}][t^{H}]\exp\left((e^{t}-1)\sum_{i\leq
N}\frac{y^{i}}{i}\right)\\\
&\leq\sum_{i=0}^{\infty}[y^{i}][t^{H}]\exp\left((e^{t}-1)\sum_{i\leq
N}\frac{y^{i}}{i}\right)\\\ &=[t^{H}]\exp\left({(e^{t}-1)\sum_{i\leq
N}\frac{1}{i}}\right).\end{split}$

But this is just the moment generating function of a Poisson random variable
of mean $\sum_{1\leq i\leq N}\frac{1}{i}\leq\log(N+1)$, and the result follows
from the bound

$\operatorname{\mathbb{E}}[Z^{H}]\leq\left(\frac{H}{\log\left(\frac{H}{\operatorname{\mathbb{E}}[Z]}+1\right)}\right)^{H}$

for the moments of a Poisson random variable $Z$ (see [1]). ∎

##  6\. Moments of $N_{i}(f)$ and $N_{i}^{\prime}(f)$

Recall the general setup of Section 3.1. We begin with the following bounds on
the difference in probabilities between the uniform and non-uniform model that
the $\alpha_{i}$ are roots of $f$ of multiplicity $k_{i}$.

We define the following notion of high order elements and low order elements
$\alpha\in\mathbb{F}_{p^{e}}$ which will be used repeatedly.

######  Definition 6.1 (High and low order roots).

Recall that we have parameters $H$ controlling the number of roots considered
at a time, and $K$ controlling the number of derivatives we consider. We say
that $\alpha\in\mathbb{F}_{p^{e}}$ has _high order_ if $\alpha$ has
multiplicative order at least $m_{e}=CH(K+1)e\log p\log(H(K+1)e\log p)$ for
some large constant $C$. Otherwise, we say that $\alpha$ has _low order_. We
say that an irreducible polynomial $g\in\mathbb{F}_{p}[x]$ is high or low
order if all its roots are high or low order.

The utility of this definition is that for any collection of at most $H$ high
order roots, the second case of Theorem 4.1 cannot hold, and so we obtain
strong bounds on the Fourier coefficients.

######  Proposition 6.2.

We use the same notation as in previous sections.

  1. (1)

Suppose that $d\leq n$. Then

$\left|\operatorname{\mathbb{P}}\left[(x-\alpha_{i})^{k_{i}+1}|f(x)\text{
}\forall
i\right]-\operatorname{\mathbb{P}}\left[(x-\alpha_{i})^{k_{i}+1}|\overline{f}(x)\text{
}\forall i\right]\right|\leq\exp\left(-\frac{cn}{dp^{2}}\right).$

  2. (2)

If in addition, all $\alpha_{i}\in\mathbb{F}_{p^{e_{i}}}$ have high order,
then

$\left|\operatorname{\mathbb{P}}\left[(x-\alpha_{i})^{k_{i}+1}|f(x)\text{
}\forall
i\right]-\operatorname{\mathbb{P}}\left[(x-\alpha_{i})^{k_{i}+1}|\overline{f}(x)\text{
}\forall i\right]\right|\leq\exp\left(-\frac{\eta n}{Cd\log p\log^{5}(d\log
p)}\right).$

###### Proof.

We note that if $d\leq n$, then
$\operatorname{\mathbb{P}}\left[(x-\alpha_{i})^{k_{i}}|\overline{f}(x)\text{
}\forall i\right]=p^{-d}$. Now

$\left|\operatorname{\mathbb{P}}\left[(x-\alpha_{i})^{k_{i}+1}|f(x)\text{
}\forall i\right]-p^{-d}\right|\leq\frac{1}{p^{d}}\sum_{\beta\neq
0}|\widehat{\nu_{n}}(\beta)|\leq\exp\left(-\frac{cn}{dp^{2}}\right)$

by Proposition 3.2. This proves the first part of the proposition.

Now suppose in addition that each $\alpha_{i}$ has high order. We then proceed
as above, but use Theorem 4.1 instead. If all entries in $\beta$ are non-zero,
this is immediate, since $H(K+1)\max e_{i}\geq d$. If $\beta$ has entries
which are $0$, we simply apply Theorem 4.1, forgetting about those entries
which are $0$. Note that the parameter $d$ will change, and the definition of
high order for the $\alpha_{i}$ ensures that

$H(K+1)\max_{\beta_{i,k}\neq 0\text{ for some $k$}}e_{i}\geq d^{\prime},$

where $d^{\prime}$ has the same definition as $d$, except we restrict to the
$\alpha_{i}$ and $K_{i}$ for which $\beta_{i,k}\neq 0$ for all
$k_{i}\in\mathcal{K}_{i}$. Thus, we always have at least one $\alpha_{i}$ with
higher order than in the second case of Theorem 4.1, which ensures

$|\widehat{\nu}_{n}(\beta)|\leq\exp\left(-\frac{\eta n}{Cd\log p\log^{5}(d\log
p)}\right).$

The second part of the proposition is now immediate. ∎

###  6.1. Moments of $N_{i}(f)$

We are now in a position to approximate the moments of $N_{i}(f)$, by
expanding into events that can be controlled by Proposition 6.2.

######  Proposition 6.3.

Let $\sum h_{i}\leq H$ and assume that $NH\leq n$. Then we have

$\left|\operatorname{\mathbb{E}}\left[\prod_{i\leq
N}N_{i}(f)^{h_{i}}\right]-\operatorname{\mathbb{E}}\left[\prod_{i\leq
N}N_{i}(\overline{f})^{h_{i}}\right]\right|\leq
p^{HN}\exp\left(-\frac{cn}{NHp^{2}}\right).$

If we define $\overline{N}_{i}(f)$ to be the number of high order factors of
$f$ of degree $i$, then

$\left|\operatorname{\mathbb{E}}\left[\prod_{i\leq
N}\overline{N}_{i}(f)^{h_{i}}\right]-\operatorname{\mathbb{E}}\left[\prod_{i\leq
N}\overline{N}_{i}(\overline{f})^{h_{i}}\right]\right|\leq
p^{HN}\exp\left(-\frac{\eta n}{CNH\log p\log^{5}(NH\log p)}\right).$

###### Proof.

We write $N_{i}(f)=\sum_{\alpha}I_{\alpha}(f)$, where $I_{\alpha}(f)$ is the
indicator for the event that $\alpha$ is a root of $f$, and the sum is over a
choice of representative root for the irreducible polynomials of degree $i$.
Expanding the product, we have a sum of at most $p^{HN}$ terms, and the
discrepancy for each term can be bounded by the first part of Proposition 6.2
(with $K=0$), where we note that $d\leq NH$.

For the second part, we simply sum the above to a sum over $\alpha$ of high
order, and use the second part of Proposition 6.2. ∎

###  6.2. Moments of $N_{i}^{\prime}(f)$

We use a similar argument to control the moments of $N_{i}^{\prime}(f)$. The
only complication is our lack of control on the tail, for which we simply use
the crude bound $N_{i}^{\prime}(f)\leq n$.

######  Proposition 6.4.

Let $\sum h_{i}\leq H$ and assume that $NH(K+1)\leq n$. Then we have

$\begin{split}&\left|\operatorname{\mathbb{E}}\left[\prod_{i\leq
N}N^{\prime}_{i}(f)^{h_{i}}\right]-\operatorname{\mathbb{E}}\left[\prod_{i\leq
N}N^{\prime}_{i}(\overline{f})^{h_{i}}\right]\right|\\\
&\leq(K+1)^{H}p^{HN}\exp\left(-\frac{cn}{NHKp^{2}}\right)+n^{H}\left(\frac{2}{p^{K+1}}+p^{N}\exp\left(-\frac{cn}{NKp^{2}}\right)\right).\end{split}$

If we define $\overline{N}^{\prime}_{i}(f)$ to be the number of high order
factors of $f$ of degree $i$, counted with multiplicity, then

$\begin{split}&\left|\operatorname{\mathbb{E}}\left[\prod_{i\leq
N}\overline{N}^{\prime}_{i}(f)^{h_{i}}\right]-\operatorname{\mathbb{E}}\left[\prod_{i\leq
N}\overline{N}^{\prime}_{i}(\overline{f})^{h_{i}}\right]\right|\\\
&\leq(K+1)^{H}p^{HN}\exp\left(-\frac{\eta n}{CNHK\log p\log^{5}(NHK\log
p)}\right)\\\ &\qquad+n^{H}\left(\frac{2}{p^{K+1}}+p^{N}\exp\left(-\frac{\eta
n}{CNK\log p\log^{5}(NK\log p)}\right)\right).\end{split}$

###### Proof.

On the event that all roots have multiplicity at most $K+1$, we may write
$N^{\prime}(f)=\sum_{\alpha}\sum_{k\leq K}I_{\alpha,k}(f)$ where
$I_{\alpha,k}(f)$ is the event that $f$ has $\alpha$ as a root of multiplicity
at least $k+1$. Then conditional on this event, the proof of Proposition 6.3
gives the same bounds, although the number of terms is now bounded by
$(K+1)^{H}p^{NH}$ and $d\leq NH(K+1)$

To obtain the desired result, we simply show that the probability of obtaining
even a single root of degree at most $N$ of multiplicity greater than $K+1$ is
very small. For the uniform model, if $\alpha\in\mathbb{F}_{p^{e}}$, then we
have

$\operatorname{\mathbb{P}}\left[(x-\alpha)^{K+2}|\overline{f}(x)\right]=\frac{1}{p^{(K+2)e}}.$

By Proposition 6.2,

$\operatorname{\mathbb{P}}\left[(x-\alpha)^{K+2}|f(x)\right]\leq\frac{1}{p^{(K+2)e}}+\exp\left(-\frac{cn}{eKp^{2}}\right).$

By a union bound, the probability that $f$ has even one root of degree at most
$N$ and multiplicity at least $K+2$ is at most

$\sum_{e\leq
N}\left(\frac{1}{p^{(K+2)e}}+\exp\left(-\frac{cn}{eKp^{2}}\right)\right)\pi(e)\leq\frac{2}{p^{K+1}}+p^{N}\exp\left(-\frac{cn}{NKp^{2}}\right),$

where $\pi(e)\leq p^{e}$ denotes the number of irreducible polynomials of
degree $i$.

Since $N_{i}^{\prime}(f)\leq n$, this means

$\begin{split}&\left|\operatorname{\mathbb{E}}\left[\prod_{i\leq
N}N^{\prime}_{i}(f)^{h_{i}}\right]-\operatorname{\mathbb{E}}\left[\prod_{i\leq
N}N^{\prime}_{i}(\overline{f})^{h_{i}}\right]\right|\\\
\leq&(K+1)^{H}p^{HN}\exp\left(-\frac{cn}{NHKp^{2}}\right)+n^{H}\left(\frac{2}{p^{K+1}}+p^{N}\exp\left(-\frac{cn}{NKp^{2}}\right)\right).\end{split}$

The second part of the proposition is completely analogous. ∎

######  Remark 6.5.

In fact, the first parts of Propositions 6.2, 6.3 and 6.4 hold even for finite
fields $\mathbb{F}_{q}$ for $q$ a prime power, since the key input is
Proposition 3.2 which does not require working over $\mathbb{F}_{p}$.

##  7\. Proof of Main Results

In this section, we state and prove the main theorems, and then prove some
corollaries which were stated in the introduction.

###  7.1. Statements of main results

Recall that $\mu$ is a probability distribution on $\mathbb{F}_{q}$, where
$q=p^{e}$, and $\eta=1-\max_{V\subseteq\mathbb{F}_{q}}\mu(V)$, where the
maximum is taken over all proper $\mathbb{F}_{p}$ affine subspaces of
$\mathbb{F}_{q}$. When $q=p$ is a prime,
$\eta=1-\max_{x\in\mathbb{F}_{p}}\mu(x)$. All constants in what follows can
depend on $\eta$.

We let $f(x)=\sum_{i=0}^{n}\varepsilon_{i}x^{i}$, where $\varepsilon_{i}$ are
drawn independently from $\mu$. We let $\overline{f}$ denote a uniformly
random monic polynomial of degree $n$. For a polynomial $g$, let $N_{i}(g)$
denote the number of distinct irreducible factors of degree $i$, and let
$N^{\prime}_{i}(g)$ denote the number of irreducible factors of degree $i$,
counted with multiplicity, where we do not count the factor $x$ in $N_{1}(g)$
and $N^{\prime}_{1}(g)$.

The first two theorems give quantitative bounds between $N_{i}(f)$ and
$N_{i}(\overline{f})$ for the regimes where $p$ is small and where $p$ is
large.

######  Theorem 7.1.

Suppose that $\eta>0$ and $n\geq CN^{4}(\log n)^{2}p^{2}\log q$ for some large
constant $C$ depending only on $\eta$. Then

$d_{TV}((N_{i}(f))_{i\leq N},(N_{i}(\overline{f}))_{i\leq
N})=O\left(\exp\left(-cn^{\frac{1}{4}}p^{-\frac{1}{2}}\log^{-\frac{1}{4}}q\right)\right)$

for some constant $c>0$ depending only on $\eta$.

######  Theorem 7.2.

Suppose that $\mu$ is a distribution on $\mathbb{F}_{p}$ and $\eta>0$. Then

$d_{TV}((N_{i}(f))_{i\leq N},(N_{i}(\overline{f}))_{i\leq
N})=O\left(\left(p^{-1}+n^{-\frac{1}{2}}\right)N^{2}\log^{4}n\log^{2}p\right),$

where the implicit constant depends only on $\eta$.

The next two theorems give quantitative bounds between $N_{i}^{\prime}(f)$ and
$N_{i}^{\prime}(\overline{f})$ in the regimes where $p$ is small and where $p$
is large.

######  Theorem 7.3.

Suppose that $\eta>0$ and $n\geq CN^{5}(\log n)^{4}p^{2}\log q$ for some large
constant $C$ depending only on $\eta$. Then

$d_{TV}((N^{\prime}_{i}(f))_{i\leq N},(N^{\prime}_{i}(\overline{f}))_{i\leq
N})=O\left(\exp\left(-cn^{\frac{1}{5}}p^{-\frac{2}{5}}\log^{-\frac{1}{5}}q\right)\right)$

for some constant $c>0$ depending only on $\eta$.

######  Theorem 7.4.

Suppose that $\mu$ is a distribution on $\mathbb{F}_{p}$ and $\eta>0$. Then

$d_{TV}((N_{i}(f))_{i\leq N},(N_{i}(\overline{f}))_{i\leq
N})=O\left(\left(p^{-1}+n^{-\frac{1}{2}}\right)N^{4}\log^{8}n\log^{2}p\right),$

where the implicit constant depends only on $\eta$.

######  Remark 7.5.

The polynomial error in Theorems 7.2 and 7.4 should be necessary, at least for
large enough $p$. To see this, note that the probability that $1$ is a root
should be of order $n^{-\frac{1}{2}}$ by comparing to a normal using a local
central limit theorem as long as $p>n^{2}$. Since the number of low order
roots in $\mathbb{F}_{p}$ is roughly $\log p$ if we only consider roots in
$\mathbb{F}_{p}$, we would expect $\operatorname{\mathbb{E}}(N_{1}(f))\geq
1+O(n^{-\frac{1}{2}})$ with a polynomial rather than exponential error. Some
numerical simulations given in Section 8 also support this.

###  7.2. Proof of main results

###### Proof of Theorem 7.1.

We apply Proposition 1.18 to the random variables $N_{i}(f)$ for $i\leq N$,
taking $H=N\log n$. We first note that by the first part of Proposition 6.3
(and Remark 6.5), we may take
$\varepsilon=q^{NH}\exp\left(-\frac{cn}{HNp^{2}}\right)$. Then using Lemma 5.1
to bound $C$, and summing over the support of the $N_{i}(f)$, which has size
at most $(n+1)^{N}$ since $N_{i}(f)\leq n$, we obtain a bound for
$d_{TV}((N_{i}(f))_{i\leq N},(N_{i}(\overline{f}))_{i\leq N})$ up to a
constant of the form

$\begin{split}&\exp\left(N\log(n+1)+H\log N+HN\log
q-\frac{cn}{HNp^{2}}\right)\\\ &\qquad+\exp\left(N\log(n+1)+CH-H\log\log
H\right).\end{split}$

Since $H=N\log n$, the second term is $O(e^{-cN\log n})$, and since $n\gg
N^{4}(\log n)^{2}p^{2}\log p$, the first term is
$O\left(\exp\left(-\frac{cn}{HNp^{2}}\right)\right)=O(e^{-cN\log n})$.
Finally, there’s no harm in assuming that $N$ is as large as possible, since
total variation distance cannot increase under projection, and so taking
$N=cn^{\frac{1}{4}}\log^{-1}np^{-\frac{1}{2}}\log^{-\frac{1}{4}}q$ gives the
desired bound. ∎

The proof of Theorem 7.2 relies on the fact that when $p$ is large, with high
probability, there are no low order roots. The following lemma allows us to
use this to obtain total variation bounds by conditioning on this event.

######  Lemma 7.6.

Let $X,X^{\prime}:\Omega_{X}\to S$ and $Y,Y^{\prime}:\Omega_{Y}\to S$ be
random variables into some set $S$. Then

$d_{TV}(X,Y)\leq
d_{TV}(X^{\prime},Y^{\prime})+2\operatorname{\mathbb{P}}(X\neq
X^{\prime})+2\operatorname{\mathbb{P}}(Y\neq Y^{\prime}).$

###### Proof.

We have for any event $A\subseteq S$,

$\begin{split}&|\operatorname{\mathbb{P}}(X\in
A)-\operatorname{\mathbb{P}}(Y\in A)|\\\ \leq&|\operatorname{\mathbb{P}}(X\in
A,X=X^{\prime})-\operatorname{\mathbb{P}}(Y\in
A,Y=Y^{\prime})|+\operatorname{\mathbb{P}}(X\neq
X^{\prime})+\operatorname{\mathbb{P}}(Y\neq Y^{\prime})\\\
=&|\operatorname{\mathbb{P}}(X^{\prime}\in
A,X=X^{\prime})-\operatorname{\mathbb{P}}(Y^{\prime}\in
A,Y=Y^{\prime})|+\operatorname{\mathbb{P}}(X\neq
X^{\prime})+\operatorname{\mathbb{P}}(Y\neq Y^{\prime})\\\
\leq&|\operatorname{\mathbb{P}}(X^{\prime}\in
A)-\operatorname{\mathbb{P}}(Y^{\prime}\in
A)|+2\operatorname{\mathbb{P}}(X\neq
X^{\prime})+2\operatorname{\mathbb{P}}(Y\neq Y^{\prime}).\end{split}$

The desired inequality follows by taking the supremum over $A$ on both sides.
∎

The next lemma shows that when $p$ is large, with high probability, there are
no low order roots.

######  Lemma 7.7.

Let $f(x)=\sum_{i=0}^{n}\varepsilon_{i}x^{i}$, and suppose that $N=o(n)$. The
probability that $f$ has a low order root (in the sense of Definition 6.1) of
degree at most $N$ is bounded by

$C\left(p^{-1}+\eta^{-\frac{1}{2}}n^{-\frac{1}{2}}\right)H^{2}K^{2}\log^{2}p\log^{2}(HK\log
p).$

###### Proof.

We see that by Proposition 3.3, if $\alpha\in\mathbb{F}_{p^{i}}$ is low order,
then

$\operatorname{\mathbb{P}}(f(\alpha)=0)\leq\left(p^{-1}+C\eta^{-\frac{1}{2}}\left(\frac{n}{i}\right)^{-1/2}\right)^{i}.$

Since the number of low order roots in $\mathbb{F}_{p^{i}}$ is bounded by

$m_{i}^{2}\leq CH^{2}K^{2}i^{2}\log^{2}p\log^{2}(HKi\log p),$

a union bound gives that the probability that $f$ has a low order root is
bounded by

$\sum_{i=1}^{N}m_{i}^{2}\left(p^{-1}+C\eta^{-\frac{1}{2}}\left(\frac{n}{i}\right)^{-1/2}\right)^{i}.$

Note that

$m_{i}^{2}/m_{1}^{2}=i^{2}\log^{2}(HKi\log p)/\log^{2}(HK\log p)\leq
Ci^{2.5},$

while

$\left(p^{-1}+C\eta^{-\frac{1}{2}}\left(\frac{n}{i}\right)^{-\frac{1}{2}}\right)^{i}\leq\left(p^{-1}+C\eta^{-\frac{1}{2}}n^{-\frac{1}{2}}\right)\cdot
i^{1/2}3^{-i+1}$

for large enough $n$, since $i=o(n)$. Thus

$\begin{split}&\sum_{i}m_{i}^{2}\left(p^{-1}+C\eta^{-\frac{1}{2}}\left(\frac{n}{i}\right)^{-\frac{1}{2}}\right)^{i}\\\
&\leq
C\sum_{i}i^{3}3^{-i+1}m_{1}^{2}\left(p^{-1}+C\eta^{-\frac{1}{2}}n^{-\frac{1}{2}}\right)\\\
&\leq
C\left(p^{-1}+\eta^{-\frac{1}{2}}n^{-\frac{1}{2}}\right)H^{2}K^{2}\log^{2}p\log^{2}(HK\log
p).\end{split}$

∎

With these lemmas, we can now prove Theorem 7.2 in exactly the same way as we
did 7.1, but counting only the high order roots.

###### Proof of Theorem 7.2.

We proceed as in the proof of Theorem 7.1, taking $H=N\log n$, except we
consider the random variables $\overline{N}_{i}(f)$ and
$\overline{N}_{i}(\overline{f})$, the number high order roots of degree $i$.
Then after using the second part of Proposition 6.3, we obtain a bound for
$d_{TV}((\overline{N}_{i}(f))_{i\leq
N},(\overline{N}_{i}(\overline{f}))_{i\leq N})$ up to a constant by

$\begin{split}&\exp\left(N\log(n+1)+H\log N+HN\log
p-\frac{c(1-\|\mu\|_{2}^{2})n}{NH\log p\log^{5}(NH\log p)}\right)\\\
&\qquad+\exp\left(N\log(n+1)+CH-H\log\log H\right).\end{split}$

We may assume that $n\geq CN^{4}\log^{7}n\log^{2}p$ and
$p=O(\exp(n^{\frac{1}{4}}))$ as otherwise the claimed upper bound is vacuous,
and so the first term is

$O\left(\exp\left(-\frac{c(1-\|\mu\|_{2}^{2})n}{N^{2}\log n\log
p\log^{5}(N^{2}\log n\log p)}\right)\right)=O(e^{-cN\log n}),$

and as $H=N\log n$, the second term is $O(e^{-cN\log n})$ as before. Thus,

$d_{TV}((\overline{N}_{i}(f))_{i\leq
N},(\overline{N}_{i}(\overline{f}))_{i\leq N})=O(e^{-cN\log n}).$

Again, there’s no harm in taking $N$ larger as long as the assumed inequality
holds, and choosing
$N=n^{\frac{1}{4}}\log^{-\frac{7}{4}}n\log^{-\frac{1}{2}}p$ gives an error of
$\exp\left(-cn^{\frac{1}{4}}\log^{-\frac{3}{4}}n\log^{-\frac{1}{2}}p\right)$.
Finally, we note that $p=O(\exp(n^{\frac{1}{4}}))$ and then this error is
dominated by the claimed upper bound.

Finally, as $N_{i}(f)=\overline{N}_{i}(f)$ if we have no low order roots (and
similarly for $\overline{f}$), by Lemmas 7.6 and 7.7 (applied to both $f$ and
$\overline{f}$) and the bound just obtained, the result follows, again using
that we may assume $p\leq e^{n}$ to simplify the upper bound. ∎

###### Proof of Theorem 7.3.

Take $H=N\log n$ and $K=N\log^{2}n$. Then the proof is analogous to the proof
of Theorem 7.1. We use Proposition 1.18 together with the moment bounds of
Proposition 6.4, where the upper bound simplifies to an $O(e^{-cN\log n})$
bound from the assumption on $n$ and the choice of $H$ and $K$, and again we
can take $N$ as large as possible without issue. ∎

###### Proof of Theorem 7.4.

Take $H=N\log n$ and $K=N\log^{2}n$. The proof is then analogous to that of
Theorem 7.2. We first assume $n\geq CN^{5}\log^{9}n\log^{2}p$ and
$p=O(\exp(n^{\frac{1}{4}}))$ as otherwise the claimed upper bound is vacuous.
We use Proposition 1.18, together with Proposition 6.4, where the upper bound
simplifies to an $O(e^{-cN\log n})$ bound by the assumption on $n$ and the
choice of $H$ and $K$. We may then choose $N$ to be large as long as the above
inequality holds, so we take $N=n^{\frac{1}{4}}$, at which point this error is
dominated by the claimed upper bound.

Finally, we proceed as in the proof of Theorem 7.2, using Lemmas 7.7 and 7.6
to restrict to the event that there are no low order roots, and again use
$p=O(\exp(n^{\frac{1}{4}}))$ to obtain the desired bound. ∎

###  7.3. Unconditional bounds

We showed two different bounds for the total variation distance between
$N_{i}(f)$ and $N_{i}^{\prime}(\overline{f})$ that work well in different
regimes. As a corollary, we can derive total variation bounds for a very large
range of $p$. Here, we prove Corollaries 1.6, 1.7 and 1.13. We present results
maximizing $N$, the maximum degree of the irreducible factors we can control.
One could take $p$ as large as $e^{n^{\frac{1}{4}-\delta}}$ by taking smaller
$N$.

###### Proof of Corollary 1.6.

First, suppose that $p\leq n^{\frac{1}{4}}$. Then taking
$N=n^{\frac{1}{8}-\delta}$, for large enough $n$ the condition of Theorem 7.1
is satisfied and the result follows.

If $n^{\frac{1}{4}}\leq p\leq e^{n^{\frac{1}{8}}}$, then taking
$N=n^{\frac{1}{8}-\delta}$, the condition of Theorem 7.2 holds, and the error
bound obtained is bounded by $O(n^{-\delta})$. ∎

###### Proof of Corollary 1.7.

First, suppose that $p\leq n^{\frac{4}{13}}$. Then taking
$N=n^{\frac{1}{13}-\delta}$, for large enough $n$ the condition of Theorem 7.3
is satisfied and the result follows.

Otherwise, if $n^{\frac{4}{13}}\leq p\leq e^{n^{\frac{1}{13}}}$, then taking
$N=n^{\frac{1}{13}-\delta}$, the conditions of Theorem 7.4 hold, and the error
bound obtained is bounded by $O(n^{-3\delta})$. ∎

We can also obtain stronger results if $p$ is fixed, and in fact this even
works over $\mathbb{F}_{q}$.

###### Proof of Corollary 1.13.

This result immediately follows from Theorems 7.1 and 7.3. ∎

###  7.4. Number of irreducible factors of fixed degree

######  Theorem 7.8.

The following statements hold for positive absolute constants $c,C>0$.

  1. (1)

Suppose $(\log p)^{2}\log^{10}(n\log p)i^{2}\leq n$, and $i>10(\log n)/(\log
p)$. Then

$d_{TV}(N_{i}(f),N_{i}(\overline{f}))\leq\exp\left(-\frac{\eta}{C}\left(\frac{n}{i^{2}(\log
p)^{2}(\log n)^{5}}\right)^{1/2}\right)+\left(\frac{1}{p}+C\eta^{-1/2}\lfloor
n/i\rfloor^{-1/2}\right)^{i/2}.$

  2. (2)

Suppose $1\leq i\leq 10(\log n)/(\log p)$ and $p>(\log n)^{100}$. Then

$\displaystyle d_{TV}(N_{i}(f),N_{i}(\overline{f}))$
$\displaystyle\leq\exp(-c\log n\log\log
n)+\left(\frac{1}{p}+C\eta^{-1/2}\lfloor n/i\rfloor^{-1/2}\right)^{i/2}.$

  3. (3)

Suppose $n\geq Ci^{2}p^{2}\log p(\log n)^{2}$. Then

$d_{TV}(N_{i}(f),N_{i}(\overline{f}))\leq\exp\left(-\frac{\eta}{C}\cdot\frac{n^{1/2}}{pi\sqrt{\log
p}}\right).$

###### Proof.

Throughout the argument we denote by $C$ absolute constants independent of all
other parameters.

We have from Proposition 6.3 that for $h\leq H$,

$\left|\operatorname{\mathbb{E}}\left[\overline{N}_{i}(f)^{h}\right]-\operatorname{\mathbb{E}}\left[\overline{N}_{i}(\overline{f})^{h}\right]\right|\leq
p^{Hi}\exp\left(-\frac{\eta n}{CHi\log p\log^{5}(Hi\log p)}\right).$

Thus, by using Proposition 1.18, we have

$\displaystyle d_{TV}(\overline{N}_{i}(f),\overline{N}_{i}(\overline{f}))$
$\displaystyle\leq Cnp^{Hi}\exp\left(-\frac{\eta n}{CHi\log p\log^{5}(Hi\log
p)}\right)+Cn\left(\frac{H}{\log H}\right)^{H}\frac{\pi^{H}}{H!}.$

Recall $m_{i}=CHi\log p\log(Hi\log p)$. The probability that
$N_{i}(f)-\overline{N}_{i}(f)\neq 0$ is at most

$m_{i}^{2}\left(\frac{1}{p}+C\eta^{-1/2}\lfloor n/i\rfloor^{-1/2}\right)^{i},$

and the same bound holds for $\overline{f}$. Then we have

$\displaystyle d_{TV}(\overline{N}_{i}(f),\overline{N}_{i}(\overline{f}))$
$\displaystyle\leq Cnp^{Hi}\exp\left(-\frac{\eta n}{CHi\log p\log^{5}(Hi\log
p)}\right)+n(\log H)^{-H/2}+m_{i}^{2}\left(\frac{1}{p}+C\eta^{-1/2}\lfloor
n/i\rfloor^{-1/2}\right)^{i}.$

By choosing $H=c\left(\frac{n}{i^{2}(\log p)^{2}\log^{5}(n\log
p)}\right)^{1/2}$, we obtain

$\displaystyle d_{TV}(\overline{N}_{i}(f),\overline{N}_{i}(\overline{f}))$
$\displaystyle\leq Cn\exp\left(-\frac{\eta}{C}\left(\frac{n}{\log^{5}(n\log
p)}\right)^{1/2}\right)+n(\log H)^{-H/2}+\frac{Cn}{(\log
n)^{3}}\left(\frac{1}{p}+C\eta^{-1/2}\lfloor n/i\rfloor^{-1/2}\right)^{i}$
$\displaystyle\leq C\exp\left(-\frac{\eta}{C}\left(\frac{n}{i^{2}(\log
p)^{2}(\log n)^{5}}\right)^{1/2}\right)+\frac{Cn}{(\log
n)^{3}}\left(\frac{1}{p}+C\eta^{-1/2}\lfloor n/i\rfloor^{-1/2}\right)^{i}.$

On the other hand, we can choose $H=i\log n$ and obtain

$\displaystyle d_{TV}(\overline{N}_{i}(f),\overline{N}_{i}(\overline{f}))$
$\displaystyle\leq Cn\exp\left(-\frac{\eta}{C}\cdot\frac{n}{i^{2}(\log n)(\log
p)\log^{5}(n\log p)}\right)+\exp(-ci\log n\log\log n)$
$\displaystyle\qquad\qquad+(i^{2}\log n\log
p)^{3}\left(\frac{1}{p}+C\eta^{-1/2}\lfloor n/i\rfloor^{-1/2}\right)^{i}$
$\displaystyle\leq Cn\exp\left(-\frac{\eta}{C}\cdot\frac{n}{i^{2}(\log
n)^{6}(\log p)}\right)+n^{-ci}+(i\log n\log
p)^{6}\left(\frac{1}{p}+C\eta^{-1/2}\lfloor n/i\rfloor^{-1/2}\right)^{i}.$

If $i>10\log_{p}(n)$, the first bound yields

$\displaystyle d_{TV}(\overline{N}_{i}(f),\overline{N}_{i}(\overline{f}))$
$\displaystyle\leq\exp\left(-\frac{\eta}{C}\left(\frac{n}{i^{2}(\log
p)^{2}(\log n)^{5}}\right)^{1/2}\right)+\left(\frac{1}{p}+C\eta^{-1/2}\lfloor
n/i\rfloor^{-1/2}\right)^{i/2}.$

Otherwise, if $i\leq 10\log_{p}(n)$ and $p>(\log n)^{100}$, the second bound
yields

$\displaystyle d_{TV}(\overline{N}_{i}(f),\overline{N}_{i}(\overline{f}))$
$\displaystyle\leq\exp\left(-\frac{\eta}{C}\cdot\frac{n}{i(\log n)^{6}(\log
p)}\right)+n^{-ci}+\left(\frac{1}{p}+C\eta^{-1/2}\lfloor
n/i\rfloor^{-1/2}\right)^{i/2}.$

Furthermore, we always have

$\left|\operatorname{\mathbb{E}}\left[{N}_{i}(f)^{h}\right]-\operatorname{\mathbb{E}}\left[\overline{N}_{i}({f})^{h}\right]\right|\leq
p^{hi}\exp\left(-\frac{\eta n}{Chip^{2}}\right),$

so

$\displaystyle d_{TV}({N}_{i}(f),{N}_{i}(\overline{f}))$ $\displaystyle\leq
Cnp^{Hi}\exp\left(-\frac{\eta n}{CHip^{2}}\right)+Cn\left(\frac{H}{\log
H}\right)^{H}\frac{\pi^{H}}{H!}.$

Choose $H=\left(\frac{n}{Ci^{2}p^{2}\log p}\right)^{1/2}$. Assuming that
$H\geq\log n$, then

$d_{TV}({N}_{i}(f),{N}_{i}(\overline{f}))\leq\exp\left(-\frac{\eta}{C}\left(\frac{n^{1/2}}{p/\sqrt{\log
p}}\right)\right)+\exp(-H/2),$

from which we obtain

$d_{TV}(N_{i}(f),N_{i}(\overline{f}))\leq\exp\left(-\frac{\eta}{C}\cdot\frac{n^{1/2}}{pi\sqrt{\log
p}}\right).$

∎

The proof of Corollary 1.12 follows from the following result.

######  Corollary 7.9.

For $\epsilon>0$, we have the following for $c$ a positive absolute constant
independent of $\epsilon$ and $\eta$. Assume that
$p<\exp(cn^{1/2-\epsilon}/i)$. Then

  1. (1)

For $(\log n)^{2}\leq i\leq n^{1/2-2\epsilon}$,

$d_{TV}(N_{i}(f),N_{i}(\overline{f}))=O_{\eta,\epsilon}(\exp(-c\eta
n^{1/2}/(i^{2}(\log p)^{2}(\log n)^{5})^{1/2})+\exp(-ci)).$

  2. (2)

For $i<(\log n)^{2}$,

$d_{TV}(N_{i}(f),N_{i}(\overline{f}))=O_{\eta,\epsilon}(\exp(-c\eta
n^{1/2}/(i^{2}(\log p)^{2}(\log n)^{5})^{1/2})+\exp(-n^{c})+n^{-ci}).$

###### Proof.

If $(\log n)^{2}\leq i\leq n^{1/2-2\epsilon}$, then we have by the first claim
in Theorem 7.8 that

$d_{TV}(N_{i}(f),N_{i}(\overline{f}))=O_{\eta,\epsilon}(\exp(-c\eta
n^{1/2}/(i^{2}(\log p)^{2}(\log n)^{5})^{1/2})+\exp(-ci)).$

If $i<(\log n)^{2}$, $p<n^{1/8}$, we can use the third claim in Theorem 7.8 to
obtain

$d_{TV}(N_{i}(f),N_{i}(\overline{f}))=\exp(-n^{c}).$

If $i<(\log n)^{2}$, $p>n^{1/8}$ and $p<\exp(cn^{1/2-\epsilon}/i)$, we can use
the first two claims in Theorem 7.8 to obtain

$d_{TV}(N_{i}(f),N_{i}(\overline{f}))=O_{\eta,\epsilon}(\exp(-c\eta
n^{1/2}/(i^{2}(\log p)^{2}(\log n)^{5})^{1/2})+\exp(-n^{1/2-o(1)})+n^{-ci}).$

∎

With an identical proof, we can also obtain similar conclusions for other
linear statistics of the number of roots of each degree, such as the total
number of roots of degree bounded by $N\leq n^{1/2-o(1)}$.

######  Corollary 7.10.

Let $T(f)=\sum_{i\leq N}N_{i}(f)$. Then we have for $N\leq n^{1/2-\epsilon}$,
we have that

$d_{TV}(T(f),T(\overline{f}))=O_{\eta,\epsilon}(\exp(-n^{c\epsilon})+\exp(-cN)).$

##  8\. Numerical simulations

In this section, we provide some numerical simulations which both support the
main results and also suggest some directions for further investigation.

###  8.1. Low degree factors

We begin with some simulations supporting our results on the low degree
factors.

(a) $i=1$, small $p$

(b) $i=1$, large $p$

(c) $i=2$, small $p$

(d) $i=2$, large $p$

(e) $i=3$, small $p$

(f) $i=3$, large $p$

Figure 8.1. Empirical means of $N^{\prime}_{i}(f)$ with 10,000 trials when
$\mu$ is the uniform measure on $\\{-1,0,1\\}$ on $\mathbb{F}_{p}$ for primes
$p$ between $10$ and $1,000$ as well as between $10^{7}$ and $10^{7}+1000$.
Here $f$ is a random polynomial of degree $n=5,10,20$, with $n=5$ in red,
$n=10$ in blue, and $n=20$ in brown. The black line indicates $\frac{1}{i}$,
which is a good approximation for the expected value under the uniform model
for large $p$.

Figure 8.1 shows the empirical means of $N^{\prime}_{i}(f)$ computed with
10,000 trials, for $i=1,2,3$ and primes $10\leq p\leq 1000$ as well as
$10^{7}\leq p\leq 10^{7}+1000$. We show data for $f$ a random polynomial of
degree $5$, $10$ or $20$, and with coefficients drawn uniformly from
$\\{-1,0,1\\}$.

This data shows that even when the degree $n$ is relatively small, the
expectations are quite close to the true values, except for $i=1$, and that
the error does not seem to deteriorate with $p$. Admittedly, our results
indicate that any such deterioration should occur when $p\gg e^{n}$, and so it
is possible that the behaviour changes for extremely large $p$.

The fact that the error is larger for small $i$ also makes sense because in
the regime $p\gg n$, the error should be dominated by the error coming from
the low order roots, which is of order $n^{-i/2}$.

(a) $n=20$, $i=1$

(b) $n=20$, $i=2$

(c) $n=20$, $i=5$

(d) $n=50$, $i=1$

(e) $n=50$, $i=2$

(f) $n=50$, $i=5$

Figure 8.2. Histograms of $N^{\prime}_{i}(f)$ with 10,000 trials when $f$ is a
degree $20$ and $50$ random polynomial with coefficients drawn from the
uniform measure on $\\{-1,0,1\\}$ on $\mathbb{F}_{p}$ for $p=10,000,079$. The
expected counts for $\operatorname{Pois}(i^{-1})$ random variables, close
approximations to the counts for the uniform model, are shown in red.

Figure 8.2 shows histograms for $N^{\prime}_{i}(f)$ with 10,000 trials, when
$f$ is a random polynomial of degree $20$ or $50$ with coefficients uniform on
$\\{-1,0,1\\}$. Here, $p\approx 10^{7}$ and we show data for $i=1,2,5$. Again,
the error for $i=1$ seems significantly larger than for larger $i$.

(a) $i=1$

(b) $i=2$

(c) $i=5$

Figure 8.3. Empirical means of $N^{\prime}_{i}(f)$ with 10,000 trials when
$\mu$ is the uniform measure on $\\{-1,0,1\\}$ on $\mathbb{F}_{p}$ for $f$ a
random polynomial of degree $n=5,10,\dotsc,200$. Here $p=101$ is shown in red
and $p=10007$ is shown in blue. The black line indicates $\frac{1}{i}$, which
is a good approximation for the expected value under the uniform model for
large $p$.

Figure 8.3 shows the empirical means of $N_{i}^{\prime}(f)$ computed with
10,000 trials, for $i=1,2,5$, for $p=101$ and $p=10007$. Again, it seems like
the error is large for $i=1$ and quickly improves for moderate values of $i$.

This data seems to support the idea that at least for low degree factors, most
of the error seems to come from roots of low order. It also seems like the
error should note really deteriorate for large $p$, which warrants further
study since our methods are unsuited for this.

###  8.2. High degree factors

We now turn to simulations which suggest that even the high degree factors
should also exhibit universal behaviour.

(a) $p=11$

(b) $p=10,000,079$

(c) Poisson-Dirichlet

Figure 8.4. Histograms of the normalized degree of the largest irreducible
factor against the maximum of a Poisson-Dirichlet process. Data is shown for
10,000 trials when $\mu$ is the uniform measure on $\\{-1,0,1\\}$ on
$\mathbb{F}_{p}$ for $f$ a random polynomial of degree $n=500$, and for $p=11$
and $p=10,000,079$.

Figure 8.4 shows histograms for the maximal degree of an irreducible factor
(normalized by the total degree) against the values for the maximum of a
Poisson-Dirichlet process, which is what the uniform model converges to. Based
on the data, it seems like at least the maximal degree exhibits universality.
While it is harder to check for the joint distribution of all normalized
degrees using simulations, it seems plausible that they also exhibit
universality.

## Acknowledgments

The authors thank Nicholas Cook, Persi Diaconis, Sean Eberhard, Ofir
Gorodetsky and Péter Varjú for their help and comments on earlier drafts.

## References

  * [1] T. D. Ahle.  Sharp and simple bounds for the raw moments of the binomial and Poisson distributions, 2021, 2103.17027.
  * [2] R. Arratia, A. D. Barbour, and S. Tavaré.  On random polynomials over finite fields.  Math. Proc. Cambridge Philos. Soc., 114(2):347–368, 1993.
  * [3] R. Arratia, A. D. Barbour, and S. Tavaré.  Logarithmic combinatorial structures: a probabilistic approach.  EMS Monographs in Mathematics. European Mathematical Society (EMS), Zürich, 2003.
  * [4] L. Bary-Soroker and O. Gorodetsky.  Roots of polynomials and the derangement problem.  Amer. Math. Monthly, 125(10):934–938, 2018.
  * [5] E. Bombieri and W. Gubler.  Heights in Diophantine geometry, volume 4 of New Mathematical Monographs.  Cambridge University Press, Cambridge, 2006.
  * [6] E. Breuillard and P. P. Varjú.  Irreducibility of random polynomials of large degree.  Acta Math., 223(2):195–249, 2019.
  * [7] E. Breuillard and P. P. Varjú.  Cut-off phenomenon for the ax+b markov chain over a finite field, 2019, 1909.09053.
  * [8] N. A. Cook and H. Nguyen.  Universality of the minimum modulus for random trigonometric polynomials.  Discrete Anal., pages Paper No. 20, 46, 2021.
  * [9] N. A. Cook, H. H. Nguyen, O. Yakir, and O. Zeitouni.  Universality of Poisson limits for moduli of roots of Kac polynomials, 2021, 2105.08592.
  * [10] P. Diaconis, M. McGrath, and J. Pitman.  Riffle shuffles, cycles, and descents.  Combinatorica, 15(1):11–29, 1995.
  * [11] Y. Do, O. Nguyen, and V. Vu.  Roots of random polynomials with coefficients of polynomial growth.  Ann. Probab., 46(5):2407–2494, 2018.
  * [12] E. Dobrowolski.  On a question of Lehmer and the number of irreducible factors of a polynomial.  Acta Arith., 34(4):391–401, 1979.
  * [13] B. Dubail and L. Massoulié.  Accelerating abelian random walks with hyperbolic dynamics, 2021, 2106.10079.
  * [14] S. Eberhard.  The characteristic polynomial of a random matrix, 2021, 2008.01223.
  * [15] S. Eberhard and P. P. Varjú.  Mixing time of the Chung-Diaconis-Graham random process.  Probab. Theory Related Fields, 179(1-2):317–344, 2021.
  * [16] D. Elboim and O. Gorodetsky.  Uniform estimates for almost primes over finite fields, 2020, 2008.05778.  To appear in Proc. Amer. Math. Soc.
  * [17] A. Ferber, V. Jain, A. Sah, and M. Sawhney.  Random symmetric matrices: rank distribution and irreducibility of the characteristic polynomial, 2021, 2106.04049.
  * [18] J. Fulman.  Semisimple orbits of Lie algebras and card-shuffling measures on Coxeter groups.  J. Algebra, 224(1):151–165, 2000.
  * [19] J. Fulman.  Applications of the Brauer complex: card shuffling, permutation statistics, and dynamical systems.  J. Algebra, 243(1):96–122, 2001.
  * [20] B. Green and I. Ruzsa.  Freiman’s theorem in an arbitrary abelian group.  Journal of the London Mathematical Society, pages 163–175, 2007\.
  * [21] J. W. P. Hirschfeld, G. Korchmáros, and F. Torres.  Algebraic curves over a finite field.  Princeton Series in Applied Mathematics. Princeton University Press, Princeton, NJ, 2008.
  * [22] I. Ibragimov and O. Zeitouni.  On roots of random polynomials.  Trans. Amer. Math. Soc., 349(6):2427–2441, 1997.
  * [23] K. Johansson.  On random matrices from the compact classical groups.  Ann. of Math. (2), 145(3):519–545, 1997.
  * [24] A. Knopfmacher and J. Knopfmacher.  Counting irreducible factors of polynomials over a finite field.  Discrete Math., 112(1-3):103–118, 1993.
  * [25] J. Koenig, H. H. Nguyen, and A. Pan.  A note on inverse results of random walks in abelian groups, 2021, 2108.07334.
  * [26] S. V. Konyagin.  Estimates for Gaussian sums and Waring’s problem modulo a prime.  Trudy Mat. Inst. Steklov., 198:111–124, 1992.
  * [27] K. Luh, S. Meehan, and H. H. Nguyen.  Some new results in random matrices over finite fields.  J. Lond. Math. Soc. (2), 103(4):1209–1252, 2021.
  * [28] K. Maples.  Singularity of random matrices over finite fields, 2013, 1012.2372.
  * [29] M. Michelen and J. Sahasrabudhe.  Random polynomials: the closest roots to the unit circle, 2020, 2010.10869.
  * [30] P. M. Neumann and C. E. Praeger.  Derangements and eigenvalue-free elements in finite classical groups.  J. London Math. Soc. (2), 58(3):564–586, 1998.
  * [31] H. Nguyen and V. Vu.  Small Ball Probability, Inverse Theorems, and Applications.  Number 1-2. Springer Berlin Heidelberg, 2013.
  * [32] R. Shmueli.  The expected number of roots over the field of $p$-adic numbers.  International Mathematics Research Notices, 2021.
  * [33] R. Stong.  Some asymptotic results on finite vector spaces.  Adv. in Appl. Math., 9(2):167–199, 1988.
  * [34] T. Tao and V. Vu.  Local universality of zeroes of random polynomials.  Int. Math. Res. Not. IMRN, (13):5053–5139, 2015.