# Asymptotic distributions of the number of zeros of random polynomials in
Hayes equivalence class over a finite field

Zhicheng Gao
School of Mathematics and Statistics
Carleton University
Ottawa, Ontario
Canada K1S5B6
Email<EMAIL_ADDRESS>
###### Abstract

Hayes equivalence is defined on monic polynomials over a finite field
${\mathbb{F}}_{q}$ in terms of the prescribed leading coefficients and the
residue classes modulo a given monic polynomial $Q$. We study the distribution
of the number of zeros in a random polynomial over finite fields in a given
Hayes equivalence class. It is well known that the number of distinct zeros of
a random polynomial over ${\mathbb{F}}_{q}$ is asymptotically Poisson with
mean 1. We show that this is also true for random polynomials in any given
Hayes equivalence class. Asymptotic formulas are also given for the number of
such polynomials when the degree of such polynomials is proportional to $q$
and the degree of $Q$ and the number of prescribed leading coefficients are
bounded by $\sqrt{q}$. When $Q=1$, the problem is equivalent to the study of
the distance distribution in Reed-Solomon codes. Our asymptotic formulas
extend some earlier results and imply that all words for a large family of
Reed-Solomon codes are ordinary, which further supports the well-known Deep-
Hole Conjecture.

##  1  Introduction

Let ${\mathbb{F}}_{q}$ be the finite field with $q$ elements of characteristic
$p$. In this paper, we study the distribution of the number of zeros in a
random polynomial over ${\mathbb{F}}_{q}$ in a given Hayes equivalence class
(the precise definition of Hayes equivalence will be given below). There are
two motivations for the current study. First, there has been considerable
interest in the study of distributions of parameters in general combinatorial
structures. See, e.g., [1, 9] for general combinatorial structures, and [13,
16, 17, 18, 19, 23] for polynomials over finite fields with respect to
factorization patterns. Second, there is a close connection between the
distance distribution over Reed-Solomon codes and the distribution of the
number of distinct zeros in a random polynomial over ${\mathbb{F}}_{q}$ in a
given equivalence class defined by leading coefficients; see [10, 12, 21, 23]
for related discussions.

Many interesting parameters of random combinatorial structures are known to be
asymptotically Poisson [1, 9]. Two well-known examples are the number of small
cycles in a random permutation and the number of zeros in a random polynomial
over ${\mathbb{F}}_{q}$. There are basically two approaches to the study of
such problems. One is based on analytic combinatorics [9] using generating
functions, and the other is probabilistic using the famous Chen-Stein method
[2, 3, 5]. The latter approach requires that the random variable under
consideration can be expressed as a sum of nearly independent indicator
variables.

In this paper, we apply the generating function approach to study the number
of distinct zeros in a random polynomial over ${\mathbb{F}}_{q}$ in a given
Hayes equivalence class. This includes polynomials with prescribed leading
and/or ending coefficients.

Before stating our main results, we introduce some notations, which will be
used throughout the paper.

  * •

${\cal M}$ denotes the set of monic polynomials over ${\mathbb{F}}_{q}$, and
${\cal M}_{d}$ denotes the set of polynomials in ${\cal M}$ of degree $d$.

  * •

$\deg(f)$ denotes the degree of the polynomial $f$, $[x^{j}]f$ denotes the
coefficient of $x^{j}$ in $f$, and ${\hat{f}}=x^{\deg(f)}f(1/x)$.

Fix a non-negative integer $\ell$ and a polynomial $Q\in{\cal M}$. Two
polynomials $f,g\in{\cal M}$ are said to be Hayes equivalent with respect to
$\ell$ and $Q$ if $\gcd(f,Q)=\gcd(g,Q)=1$ and

$\displaystyle{\hat{f}}(x)$
$\displaystyle\equiv{\hat{g}}(x)\pmod{x^{\ell+1}},$ (1) $\displaystyle f(x)$
$\displaystyle\equiv g(x)\pmod{Q}.$ (2)

The following two special cases are particularly interesting.

  * (a)

$Q=1$. In this case, condition (2) is null, and Hayes equivalence is defined
by the $\ell$ leading coefficients $[x^{\deg(f)-j}]f,1\leq j\leq\ell$.

  * (b)

$Q=x^{t}$ for some $t>0$. In this case, Hayes equivalence is defined by the
$\ell$ leading coefficients and $t$ ending coefficients $[x^{j}]f,0\leq j<t$.

Let ${\cal E}^{\ell,Q}$ denote the set of all Hayes equivalence classes with
respect to $\ell,Q$, and let $\langle f\rangle$ denote the equivalence class
represented by a polynomial $f\in{\cal M}$. It is known [8, 14, 15] that
${\cal E}^{\ell,Q}$ is a group under the operation $\langle f\rangle\langle
g\rangle=\langle fg\rangle$.

Given a set $D\subseteq{\mathbb{F}}_{q}$ and ${\varepsilon}\in{\cal
E}^{\ell,Q}$, let ${\cal M}_{k+t+\ell}({\varepsilon})$ denote the set of
polynomials in ${\cal M}_{k+t+\ell}$ which are equivalent to ${\varepsilon}$,
and $Y_{k}({\varepsilon})$ be the number of zeros in $D$ of a random
polynomial $f\in{\cal M}_{k+t+\ell}({\varepsilon})$ (under uniform
distribution).

Since $\gcd(f,Q)=1$, we will assume, without loss of generality, that $D$ does
not contain any zero of $Q$. In the rest of the paper, we will also set
$n:=|D|$.

The paper [10] focuses on obtaining exact expression of the distribution of
$Y_{k}({\varepsilon})$ with $Q=1$ and $\ell\leq 2$. The paper [12] focuses on
the problem whether ${\mathbb{P}}(Y_{k}({\varepsilon})=k+1)>0$ when $Q=1$ and
$k$ is large, which is motivated by the Deep-Hole Conjecture about Reed-
Solomon codes. In this paper we study the asymptotic distribution of
$Y_{k}({\varepsilon})$ for general $\ell$ and $Q$. Our main results are
summarized below.

###### Theorem 1

Let $Q\in{\cal M}_{t}$ and ${\varepsilon}\in{\cal E}^{\ell,Q}$.

  * (a)

As $k-r\to\infty$ we have

$\displaystyle{\mathbb{P}}(Y_{k}({\varepsilon})=r)$
$\displaystyle\sim{n\choose
r}\left(\frac{1}{q}\right)^{r}\left(1-\frac{1}{q}\right)^{n-r}.$

That is, $Y_{k}({\varepsilon})$ is asymptotically binomial.

  * (b)

As $n,k-r\to\infty$ and for $r=o(\sqrt{n})$, we have

$\displaystyle{\mathbb{P}}(Y_{k}({\varepsilon})=r)$ $\displaystyle\sim
e^{-n/q}\frac{1}{r!}\left(\frac{{n}}{q}\right)^{r}.$

That is, $Y_{k}({\varepsilon})$ is asymptotically Poisson with mean ${n}/q$.

Recall that $p$ is the characteristic of ${\mathbb{F}}_{q}$. Some applications
(see e.g. [12]) require asymptotic formulas of
${\mathbb{P}}(Y_{k}({\varepsilon})=r)$ when $r$ is close to $k$. Let $c:=k/q$,
${\gamma}:=(t+\ell-1)\sqrt{q}/n$, and ${\delta_{0}}$ denote any small positive
constant (independent of $k$). The next theorem provides a simple asymptotic
formula for ${\mathbb{P}}(Y_{k}({\varepsilon})=r)$ which is uniform over all
values of $r$ under either of the following two conditions.

Condition A:

$\quad\displaystyle\frac{p-1}{p}c\ln\frac{1}{c}+(1-c)\ln\frac{1}{1-c}-\frac{1+c}{p}\ln(1+c)\geq{\gamma}\ln(2p)+{\delta_{0}}$.

Condition B:

$\quad\displaystyle p\to\infty,~{}{\gamma}\geq\frac{c}{p}~{}\hbox{ and
}~{}c\ln\frac{1}{c}+(1-c)\ln\frac{1}{1-c}\geq{\gamma}+{\gamma}\ln\frac{c+{\gamma}}{{\gamma}}+{\delta_{0}}$.

Remark 1 Condition A and Condition B cover a wide range of $c$ and ${\gamma}$,
as illustrated below.

  * (A)

For each given prime $p$ and $c\leq\frac{p-1}{p+1}$, we have
$1-c\geq\frac{1+c}{p}$ and hence

$(1-c)\ln\frac{1}{1-c}>\frac{1+c}{p}\ln(1+c).$

Thus, Condition A holds for all $c,{\gamma}$ which satisfy

$\displaystyle 0<c\leq\frac{p-1}{p+1}\quad\hbox{ and
}~{}0\leq{\gamma}\leq\frac{p-1}{p\ln(2p)}c\ln\frac{1}{c}.$

  * (B)

Suppose $q=p^{a}$ for some constant $a$. For example, $a=1$ corresponds to the
prime field. Then $q\to\infty\Leftrightarrow p\to\infty$. It is easy to see
that Condition B holds for any constant $c\in(0,1)$ and all sufficiently small
positive ${\gamma}$.

Define

$\displaystyle\mu_{m}(r)=\sum_{j=0}^{m}(-1)^{j}{{n}-r\choose j}q^{-j}.$ (3)

###### Theorem 2

Let $Q\in{\cal M}_{t}$, $\displaystyle D:=\\{x\in{\mathbb{F}}_{q}:Q(x)\neq
0\\}$, $n:=|D|$ and $\ell\geq 1$. Suppose either Condition A or Condition B
holds. Then, as $k\to\infty$, we have, uniformly for $0\leq r\leq k+t+\ell$
and ${\varepsilon}\in{\cal E}^{\ell,Q}$,

$\displaystyle{\mathbb{P}}(Y_{k}({\varepsilon})=r)$
$\displaystyle\sim\mu_{k+t+\ell-r}(r){{n}\choose r}q^{-r}.$ (4)

Recall that the (standard) Reed-Solomon code ${\cal RS}_{q,k}$ consists of the
codewords $(g(x):x\in{\mathbb{F}}_{q})$ where $g$ is a polynomial over
${\mathbb{F}}_{q}$ of degree less than $k$. When $Q=1$, we recall [6, 21] that
$q-Y_{k}(\langle f\rangle)$ is the distance between a received word $f\in{\cal
M}_{k+\ell}$ and a random codeword in ${\cal RS}_{q,k}$. Let $N(f,r)$ be the
number of codewords in ${\cal RS}_{q,k}$ which are at distance $q-r$ from a
received word $f$. Thus, $N(f,r)=q^{k}{\mathbb{P}}(Y_{k}(\langle
f\rangle)=r)$. Setting $t=0$ in Theorem 2, we immediately obtain the following
result.

###### Corollary 1

Suppose either Condition A or Condition B holds. Then, as $k\to\infty$, we
have, uniformly for $0\leq r\leq k+\ell$ and $f\in{\cal M}_{k+\ell}$,

$N(f,r)\sim\mu_{k+\ell-r}(r){q\choose r}q^{k-r}.$

Remark 2 For the prime field (i.e. $q=p$), Li and Wan [21, Corollary 1.9]
derived an asymptotic expression of $N(f,r)$ when the parameters satisfy the
conditions: $k=cp$, $\ell=p^{\delta}$, $r=k+p^{\lambda}$, where $c\in(0,1)$,
$\delta\in(0,1/4)$ and $\lambda\in(0,\delta)$ are all independent of $p$. As
commented in Remark 1, Condition B is satisfied by any constant $c\in(0,1)$
and all sufficiently small positive ${\gamma}$. Thus, Corollary 1 covers
$\ell$ up to $\sqrt{q}$ and all $r$, which significantly extends the range of
$\ell$ and $r$ covered by [21, Corollary 1.9].

Recall that a received word represented by $f\in{\cal M}_{k+\ell}$ is called a
deep-hole if $N(f,r)=0$ for all $r\geq k+1$, and is ordinary if
$N(f,k+\ell)>0$ (see, e.g., [6, 12, 22]). The well-known Deep-Hole Conjecture
by Cheng and Murray [6] states that there is no deep-hole when $\ell\geq 1$.
Corollary 1 immediately implies the following result, which further supports
the Deep-Hole Conjecture.

###### Corollary 2

Suppose either Condition A or Condition B holds. Then for sufficiently large
$q$, every $f\in{\cal M}_{k+\ell}$ is ordinary. Thus, the Deep-Hole Conjecture
holds under either Condition A or Condition B.

The remaining paper is organized as follows. In Section 2 we recall some
preliminary results about Hayes equivalence, Weil bounds, and sieve formulas.
In Section 3 we extend the generating function approach from [10, 12] to
general Hayes equivalence classes and give a proof of Theorem 1. Section 4
provides detailed error estimates which are needed for the proof of Theorem 2.
Section 5 provides the proof of Theorem 2. Section 6 concludes the paper.

##  2 Preliminaries

In this section we recall some basic results needed to prove our main
theorems. Hayes’ theory of equivalence was first introduced in [14]. For
$Q\in{\cal M}_{t}$, define

$\displaystyle\Phi_{j}(Q)$ $\displaystyle=|\\{g\in{\cal
M}_{j}:\gcd(g,Q)=1\\}|.$

In the rest of the paper, we shall use Iverson’s bracket $\llbracket
P\rrbracket$ which has value 1 if the predicate $P$ is true and 0 otherwise.

It is easy to see [7, 8] that

$\displaystyle\left|{\cal M}_{k+t+\ell}({\varepsilon})\right|$
$\displaystyle=q^{k},$ (5) $\displaystyle\left|{\cal E}^{\ell,Q}\right|$
$\displaystyle=q^{\ell}\Phi_{t}(Q).$ (6)

Let $\\{P_{i}:i\in I\\}$ be the set of distinct irreducible factors of $Q$,
where $P_{i}\in{\cal M}_{d_{i}}$. Then the classical sieve formula gives

$\displaystyle\Phi_{j}(Q)=\sum_{S\subseteq
I}(-1)^{|S|}\left\llbracket\sum_{i\in S}d_{i}\leq j\right\rrbracket
q^{j-\sum_{i\in S}d_{i}},$

and consequently

$\displaystyle q^{j}\left(1-\sum_{i\in I}q^{-d_{i}}\right)\leq\Phi_{j}(Q)\leq
q^{j}.$ (7)

For example, if $I=\\{1\\}$ then

$\displaystyle\Phi_{j}(Q)$ $\displaystyle=q^{j}-\llbracket j\geq
d_{1}\rrbracket q^{j-d_{1}}.$

If $I=\emptyset$, that is, $Q=1$, then

$\displaystyle\Phi_{j}(Q)$ $\displaystyle=q^{j}.$

Noting $|I|\leq\sum_{i\in I}d_{i}\leq t$ and using (7), we obtain

$\displaystyle\Phi_{j}(Q)$ $\displaystyle=q^{j}\left(1+O(t/q)\right).$ (8)

For typographical convenience, we shall omit the superscripts and simply use
${\cal E}$ to denote the group ${\cal E}^{\ell,Q}$ when there is no danger of
confusion.

Let ${\hat{\cal E}}$ denote the group of characters over ${\cal E}$, and
$\chi\in{\hat{\cal E}}$ be a nontrivial character. Define
$\chi(f)=\chi(\langle f\rangle)$ if $f\in{\cal M}$ and $\gcd(f,Q)=1$. Also set
$\chi(f)=0$ if $f\in{\cal M}$ and $\gcd(f,Q)\neq 1$ (This is the so called
Dirichlet character). By [8, Ex. 5.2 #2] (see also [15, Theorem 1.3] and the
paragraph before [15, eq. (4)]), for each nontrivial character
$\chi\in{\hat{\cal E}}$, the associated $L$-function

$\displaystyle P(z,\chi):$ $\displaystyle=\sum_{f\in{\cal
M}}\chi(f)z^{\deg(f)}$

is a polynomial of degree at most $\ell+t-1$. The roots of $P(z,\chi)$ are
either 1 or have modulus $1/\sqrt{q}$. Moreover, there is at most one root
which is equal to 1. Thus we can write

$\displaystyle P(z,\chi)$
$\displaystyle=\prod_{j=1}^{\deg(P(z,\chi))}(1-z\rho_{j}),$
$\displaystyle\deg(P(z,\chi))$
$\displaystyle\leq\ell+t-1,~{}|\rho_{j}|\leq\sqrt{q}.$

It follows that

$\displaystyle\left|\sum_{f\in{\cal M}_{j}}\chi(f)\right|$
$\displaystyle\leq{t+\ell-1\choose j}q^{j/2}.$ (9)

Let ${\mathbb{E}}(Y)$ denote the expected value of a random variable $Y$. The
following well-known result expresses the probabilities in terms of the
factorial moments [4, Corollary 11].

###### Proposition 1

Let $Y$ be any random variable which takes values in $\\{0,1,\ldots,M\\}$. We
have

$\displaystyle{\mathbb{P}}(Y=r)$
$\displaystyle=\sum_{j=r}^{M}(-1)^{j-r}{j\choose r}{\mathbb{E}}\left({Y\choose
j}\right).$

Moreover, for each $r\leq m\leq M$, we have

$\displaystyle\left|{\mathbb{P}}(Y=r)-\sum_{j=r}^{m-1}(-1)^{j-r}{j\choose
r}{\mathbb{E}}\left({Y\choose j}\right)\right|\leq{m\choose
r}{\mathbb{E}}\left({Y\choose m}\right).$ (10)

The following inequality [4, (5)] will also be used to estimate binomial
numbers.

$\displaystyle{M\choose m}$ $\displaystyle\geq\left(\frac{M}{2\pi
m(M-m)}\right)^{1/2}\left(\frac{M}{m}\right)^{m}\left(\frac{M}{M-m}\right)^{M-m}e^{-1/6}.$
$\displaystyle(0<m<M)$ (11)

The following are some simple observations about $\mu_{m}(r)$ defined in (3).
Since

$\frac{{{n}-r\choose j+1}q^{-j-1}}{{{n}-r\choose
j}q^{-j}}=\frac{n-r-j}{q(j+1)}\leq\frac{1}{j+1},$

the terms in (3) are alternating and have strictly decreasing absolute values.
Thus, we have

$\displaystyle\mu_{m}(r)$ $\displaystyle\geq\mu_{1}(r)=\frac{q-n+r}{q}.$ (12)

Using the binomial expansion of $\left(1-\frac{1}{q}\right)^{n-r}$, we also
obtain

$\displaystyle\left|\mu_{m}(r)-\left(1-\frac{1}{q}\right)^{n-r}\right|$
$\displaystyle\leq{n-r\choose
m+1}\left(\frac{1}{q}\right)^{m+1}\leq\frac{1}{(m+1)!}\left(\frac{n-r}{q}\right)^{m+1}\leq\frac{1}{(m+1)!}.$
(13)

Finally we recall the “coordinate-sieve” formula by Li and Wan [20, 21]. Let
${\cal S}_{j}$ be the symmetric group on $\\{1,2,\ldots,j\\}$. Let $X$ denote
the set of all $j$-tuples of elements from the set $D$, ${\bar{X}}$ the set of
all $j$-tuples of distinct elements from $D$. For each $\tau\in{\cal S}_{j}$,
define

$\displaystyle X_{\tau}$ $\displaystyle=\\{(x_{1},\ldots,x_{j})\in
X,x_{i}=x_{k}\hbox{ if $i$ and $k$ belong to the same cycle of $\tau$}\\}.$

Let $h$ be a complex-valued function defined on $X$, and define

$\displaystyle{\bar{H}}=\sum_{(x_{1},\ldots,x_{j})\in{\bar{X}}}h(x_{1},\ldots,x_{j}),~{}~{}H(\tau)=\sum_{(x_{1},\ldots,x_{j})\in{X_{\tau}}}h(x_{1},\ldots,x_{j}).$

Theorem 3.1 in [21] states

$\displaystyle{\bar{H}}=\sum_{\tau\in{\cal S}_{j}}(-1)^{j-l(\tau)}H(\tau),$
(14)

where $l(\tau)$ denotes the number of cycles of $\tau$.

##  3 Generating functions and proof of Theorem 1

In this section, we use the generating function method developed in [11] to
study the distribution of $Y_{k}({\varepsilon})$. It is also convenient to
define $\langle f\rangle=0$ when $\gcd(f,Q)\neq 1$.

Define generating functions

$\displaystyle F(z)$ $\displaystyle=\sum_{f\in{\cal M}}\langle f\rangle
z^{\deg(f)},$ $\displaystyle G(z,u)$ $\displaystyle=\sum_{f\in{\cal M}}\langle
f\rangle z^{\deg(f)}u^{r(f)},$

where $r(f)$ is the number of distinct zeros of $f$ that are in $D$.

We first prove the following result which is an extension of [10, Prop. 2]:

###### Proposition 2

We have

$\displaystyle F(z)$ $\displaystyle=\sum_{d=0}^{t+\ell-1}\sum_{f\in{\cal
M}_{d}}\langle f\rangle
z^{d}+\frac{1}{1-qz}z^{t+\ell}\sum_{{\varepsilon}\in{\cal E}}{\varepsilon},$
(15) $\displaystyle G(z,u)$ $\displaystyle=F(z)\prod_{{\alpha}\in D}(\langle
1\rangle+(u-1)z\langle x-{\alpha}\rangle).$ (16)

Proof The proof is similar to that of [10, Prop. 2]; see also [10, p.27].
Using (5), we obtain

$\displaystyle F(z)$ $\displaystyle=\sum_{d=0}^{t+\ell-1}\sum_{f\in{\cal
M}_{d}}\langle f\rangle z^{d}+\sum_{k\geq
0}q^{k}z^{k+t+\ell}\sum_{{\varepsilon}\in{\cal E}}{\varepsilon}$
$\displaystyle=\sum_{d=0}^{t+\ell-1}\sum_{f\in{\cal M}_{d}}\langle f\rangle
z^{d}+\frac{1}{1-qz}z^{t+\ell}\sum_{{\varepsilon}\in{\cal E}}{\varepsilon},$

which gives (15). Let ${\cal M}^{\prime}$ denote the subset of ${\cal M}$
consisting of all polynomials with no zeros in $D$. Then we have

$\displaystyle F(z)$ $\displaystyle=\prod_{{\alpha}\in D}\frac{1}{\langle
1\rangle-z\langle x-{\alpha}\rangle}\sum_{g\in{\cal
M}^{\prime}}z^{\deg(g)}\langle g\rangle,$ $\displaystyle G(z,u)$
$\displaystyle=\prod_{{\alpha}\in D}\left(\langle 1\rangle+u\sum_{j\geq
1}z^{j}\langle x-{\alpha}\rangle^{j}\right)\sum_{g\in{\cal
M}^{\prime}}z^{\deg(g)}\langle g\rangle$
$\displaystyle=\left(\prod_{{\alpha}\in D}\left(\frac{u}{\langle
1\rangle-z\langle x-{\alpha}\rangle}+(1-u)\langle
1\rangle\right)\right)\left(F(z)\prod_{{\alpha}\in D}(\langle
1\rangle-z\langle x-{\alpha}\rangle)\right),$

which gives (16).

As in [12], let $D_{j}$ denote the set of all $j$-subsets of $D$. For $k+1\leq
j\leq k+t+\ell$, define

$\displaystyle W_{j}({\varepsilon})$ $\displaystyle=\sum_{g\in{\cal
M}_{k+t+\ell-j}}\sum_{S\in D_{j}}\left\llbracket\langle
g\rangle\prod_{{\alpha}\in S}\langle
x-{\alpha}\rangle={\varepsilon}\right\rrbracket.$ (17)

For ${\varepsilon}\in{\cal E}$, we use $[z^{d}{\varepsilon}]G(z,u)$ to denote
the coefficient of $z^{d}{\varepsilon}$ in $G(z,u)$. Our next result gives all
the factorial moments expressed in terms of $W_{j}({\varepsilon})$. This
extends the corresponding results for $Q=1$ in [12].

###### Theorem 3

For each $Q\in{\cal M}_{t}$ and ${\varepsilon}\in{\cal E}^{\ell,Q}$, we have

$\displaystyle{\mathbb{E}}\left({Y_{k}({\varepsilon})\choose j}\right)$
$\displaystyle=\llbracket j\leq k\rrbracket{n\choose j}q^{-j}+\llbracket
k+1\leq j\leq k+t+\ell\rrbracket q^{-k}W_{j}({\varepsilon}).$ (18)

Proof Using Proposition 2, we obtain

$\displaystyle G(z,u)$
$\displaystyle=\frac{1}{1-qz}z^{t+\ell}(1+(u-1)z)^{n}\sum_{{\varepsilon}\in{\cal
E}}{\varepsilon}$
$\displaystyle~{}~{}~{}~{}+\left(\sum_{j=0}^{t+\ell-1}z^{j}\sum_{g\in{\cal
M}_{j}}\langle g\rangle\right)\prod_{{\alpha}\in D}\left(\langle
1\rangle+(u-1)z\langle x-{\alpha}\rangle\right),$
$\displaystyle\left[z^{k+t+\ell}{\varepsilon}\right]G(z,u)$
$\displaystyle=\left[z^{k}\right]\frac{1}{1-qz}\left(1+(u-1)z\right)^{n}$
$\displaystyle~{}~{}~{}~{}+\sum_{j=k+1}^{k+t+\ell}(u-1)^{j}[{\varepsilon}]\sum_{g\in{\cal
M}_{k+t+\ell-j}}\sum_{S\in D_{j}}\langle g\rangle\prod_{{\alpha}\in S}\langle
x-{\alpha}\rangle$ $\displaystyle=\sum_{j=0}^{k}{n\choose
j}q^{k-j}(u-1)^{j}+\sum_{j=k+1}^{k+t+\ell}W_{j}({\varepsilon})(u-1)^{j}.$ (19)

Using (19), we obtain the following probability generating function of
$Y_{k}({\varepsilon})$:

$\displaystyle p_{k}(u,{\varepsilon})$
$\displaystyle=q^{-k}\left[z^{k+t+\ell}{\varepsilon}\right]G(z,u)$
$\displaystyle=\sum_{j=0}^{k}q^{-j}{n\choose
j}(u-1)^{j}+q^{-k}\sum_{j=k+1}^{k+t+\ell}W_{j}({\varepsilon})(u-1)^{j}.$

Hence

$\displaystyle{\mathbb{E}}\left({Y_{k}({\varepsilon})\choose j}\right)$
$\displaystyle=\frac{1}{j!}\frac{d^{j}}{(du)^{j}}p_{k}(u,{\varepsilon})\Bigr{|}_{u=1}$
$\displaystyle=\llbracket j\leq k\rrbracket{n\choose j}q^{-j}+\llbracket
k+1\leq j\leq k+t+\ell\rrbracket q^{-k}W_{j}({\varepsilon}),$

which is (18).

Proof of Theorem 1 Substituting $m=k$ into (12) and using (18), we obtain

$\displaystyle\left|{\mathbb{P}}(Y_{k}({\varepsilon})=r)-\sum_{j=r}^{k-1}(-1)^{j+r}{j\choose
r}{n\choose j}q^{-j}\right|$ $\displaystyle\leq{k\choose r}{n\choose
k}q^{-k}.$

Changing the summation index $j:=j+r$, and using (3) and

$\displaystyle{j\choose r}{n\choose j}$ $\displaystyle={n\choose r}{n-r\choose
j-r},$ (20)

we obtain

$\displaystyle\left|{\mathbb{P}}(Y_{k}({\varepsilon})=r)-{n\choose
r}q^{-r}\mu_{k-1-r}(r)\right|$ $\displaystyle\leq{n\choose r}{n-r\choose
k-r}q^{-k}\leq\frac{1}{(k-r)!}{n\choose r}q^{-r}.$

Using (13), we obtain

$\displaystyle\left|{\mathbb{P}}(Y_{k}({\varepsilon})=r)-{n\choose
r}\left(\frac{1}{q}\right)^{r}\left(1-\frac{1}{q}\right)^{n-r}\right|$
$\displaystyle\leq\frac{1}{(k-r)!}{n\choose r}q^{-r}+\frac{1}{(k-r)!}{n\choose
r}q^{-r}$ $\displaystyle\leq\frac{2}{(k-r)!}{n\choose
r}\left(\frac{1}{q}\right)^{r}.$

Part (a) follows by using the assumption $k-r\to\infty$ and noting

$\left(1-\frac{1}{q}\right)^{n-r}\geq\left(1-\frac{1}{q}\right)^{q}\geq\frac{1}{4}\quad(\hbox{
when }q\geq 2).$

Part (b) follows immediately from part (a) by noting

${n\choose r}\sim\frac{1}{r!}n^{r},$

when $r=o(\sqrt{n})$.

##  4 Estimates of $W_{j}({\varepsilon})$

In [12], we derived estimate for $W_{j}({\varepsilon})$ when $Q=1$ and
$D={\mathbb{F}}_{q}$. In this section we carry out more detailed estimate for
$W_{j}({\varepsilon})$ and for general $Q$. Throughout this section, we assume

$\displaystyle D=\\{\alpha\in{\mathbb{F}}_{q}:Q(\alpha)\neq 0\\}.$ (21)

Then we have

$\displaystyle q-t\leq n\leq q.$ (22)

As in [21], the sum in (17) can be estimated using the “coordinate-sieve”
formula (14). Recall that $S_{j}$ denotes the set of all permutations of
$1,2,\ldots,j$. For $\tau\in S_{j}$, $l(\tau)$ denotes the total number of
cycles of $\tau$. We shall also use $l^{\prime}(\tau)$ to denote the number of
cycles of $\tau$ which are not multiples of $p$. The standard generating
function argument [9, 10] gives

$\displaystyle\sum_{j\geq 0}\frac{1}{j!}\sum_{\tau\in
S_{j}}a^{l(\tau)}b^{l^{\prime}(\tau)}z^{j}$
$\displaystyle=\exp\left(a\sum_{i\geq 1,p\mid i}z^{i}/i+ab\sum_{i\geq 1,p\nmid
i}z^{i}/i\right)$ $\displaystyle=(1-z)^{-ab}(1-z^{p})^{-(a-ab)/p}.$

As in [10, 12], we define

$\displaystyle A_{j}(a,b)$ $\displaystyle=\frac{1}{j!}\sum_{\tau\in
S_{j}}a^{l(\tau)}b^{l^{\prime}(\tau)}$ (23)
$\displaystyle=[z^{j}]\left((1-z)^{-ab}(1-z^{p})^{-(a-ab)/p}\right)$ (24)
$\displaystyle=\sum_{0\leq i\leq j/p}{ab+j-ip-1\choose
j-ip}{(a-ab)/p+i-1\choose i}.$

We have the following estimate of $W_{j}({\varepsilon})$.

###### Proposition 3

Let ${\varepsilon}\in{\cal E}$, $k+1\leq j\leq k+t+\ell$. Suppose $\ell\geq 1$
and ${\gamma}:=(t+\ell-1)\sqrt{q}/n\leq 1$. Then

$\displaystyle\left|W_{j}({\varepsilon})-\frac{\Phi_{k+t+\ell-j}(Q)}{\Phi_{t}(Q)}{{n}\choose
j}q^{-\ell}\right|$ $\displaystyle\leq\frac{|{\cal E}|-1}{|{\cal
E}|}{t+\ell-1\choose t+\ell+k-j}q^{(t+\ell+k-j)/2}A_{j}({n},{\gamma}).$ (25)

Proof Let ${\hat{\cal E}}$ denote the set of characters over the group ${\cal
E}$. Using (17) and orthogonality of the characters, we obtain

$\displaystyle W_{j}({\varepsilon})$ $\displaystyle=\frac{1}{|{\cal
E}|}\sum_{g\in{\cal M}_{k+t+\ell-j}}\sum_{S\in D_{j}}\sum_{\chi\in{\hat{\cal
E}}}\chi\left({\varepsilon}^{-1}\langle g\rangle\prod_{\alpha\in S}\langle
x-\alpha\rangle\right)$ $\displaystyle=\frac{1}{|{\cal
E}|}\sum_{\chi\in{\hat{\cal E}}}\chi({\varepsilon}^{-1})\left(\sum_{g\in{\cal
M}_{k+t+\ell-j}}\chi(g)\right)\sum_{S\in D_{j}}\chi\left(\prod_{\alpha\in
S}\langle x-\alpha\rangle\right).$

For the trivial character $\chi$, we have $\chi({\varepsilon}^{-1})=1$ and

$\sum_{g\in{\cal M}_{k+t+\ell-j}}\chi(g)=\Phi_{k+t+\ell-j}(Q).$

It follows that

$\displaystyle W_{j}({\varepsilon})$
$\displaystyle=\frac{\Phi_{k+t+\ell-j}(Q)}{|{\cal E}|}{n\choose
j}+\frac{1}{|{\cal E}|}\sum_{\chi\neq
1}\chi({\varepsilon}^{-1})\left(\sum_{g\in{\cal
M}_{k+t+\ell-j}}\chi(g)\right)\sum_{S\in D_{j}}\chi\left(\prod_{\alpha\in
S}\langle x-\alpha\rangle\right).$ (26)

Applying (9), we obtain

$\displaystyle\left|\sum_{g\in{\cal M}_{k+t+\ell-j}}\chi(g)\right|$
$\displaystyle\leq{t+\ell-1\choose t+\ell+k-j}q^{(k+t+\ell-j)/2}.$ (27)

Next, we use (14) to estimate $\displaystyle\sum_{S\in
D_{j}}\chi\left(\prod_{\alpha\in S}\langle x-\alpha\rangle\right)$. For a
permutation $\tau\in{\cal S}_{j}$, let $c_{i}$ be the number of cycles of
length $i$ in $\tau$. Recall from the end of Section 2 that $X_{\tau}$ denotes
the set of $j$-tuples of elements from $D$ which is constant in each cycle of
$\tau$. As in [21], we set

$G_{\tau}:=\sum_{\vec{x}\in X_{\tau}}\prod_{i=1}^{j}\chi(x-x_{i}).$

Then (Noting that $D$ contains all elements of ${\mathbb{F}}_{q}$ which are
not zeros of $Q$ and $\chi(x-\alpha)=0$ if $\alpha$ is a zero of $Q$.)

$\displaystyle G_{\tau}$ $\displaystyle=\prod_{i}\left(\sum_{\alpha\in
D}\chi^{i}(x-\alpha)\right)^{c_{i}}$ $\displaystyle=\left(\prod_{i,p\nmid
i}\left(\sum_{\alpha\in{\mathbb{F}}_{q}}\chi^{i}(x-\alpha)\right)^{c_{i}}\right)\left(\prod_{i,p\mid
i}\left(\sum_{\alpha\in{\mathbb{F}}_{q}}\chi^{i}(x-\alpha)\right)^{c_{i}}\right).$

Since ${\cal E}^{\ell,1}$ is a $p$-group, $\chi^{i}$ is nontrivial when
$p\nmid i$. It follows from (9) that

$\displaystyle\left|G_{\tau}\right|$ $\displaystyle\leq\prod_{i,p\nmid
i}(\gamma n)^{c_{i}}\prod_{i,p\mid
i}{n}^{c_{i}}=({\gamma}n)^{l^{\prime}(\tau)}{n}^{l(\tau)-l^{\prime}(\tau)}={n}^{l(\tau)}{\gamma}^{l^{\prime}(\tau)}.$

It follows from (14) and (23) that

$\displaystyle\frac{1}{j!}\left|\sum_{\vec{x}\in\overline{X}}\prod_{i=1}^{j}\chi(x-x_{i})\right|$
$\displaystyle\leq\frac{1}{j!}\sum_{\tau\in
S_{j}}|G_{\tau}|\leq\frac{1}{j!}\sum_{\tau\in
S_{j}}{n}^{l(\tau)}{\gamma}^{l^{\prime}(\tau)}=A_{j}({n},{\gamma}).$ (28)

Substituting (27) and (28) into (26), and using (6) and

$\displaystyle\sum_{S\in D_{j}}\prod_{{\alpha}\in
S}\chi(x-{\alpha})=\frac{1}{j!}\sum_{\vec{x}\in\overline{X}}\prod_{i=1}^{j}\chi(x-x_{i}),$

we complete the proof.

###### Theorem 4

Let ${\varepsilon}\in{\cal E}^{\ell,Q}$ and assume $\ell\geq 1$. We have

$\displaystyle~{}~{}~{}\left|{\mathbb{P}}(Y_{k}({\varepsilon})=r)-\mu_{k-r}(r){{n}\choose
r}q^{-r}-{n\choose r}q^{-(k+\ell)}\sum_{j=k+1}^{k+t+\ell}(-1)^{j-r}{n-r\choose
j-r}\frac{\Phi_{k+t+\ell-j}(Q)}{\Phi_{t}(Q)}\right|$
$\displaystyle<q^{-k}\sum_{j=k+1}^{k+t+\ell}{j\choose r}{t+\ell-1\choose
k+t+\ell-j}q^{(k+t+\ell-j)/2}A_{j}({n},{\gamma}).$ (29)

Proof Using Theorem 4, inequalities (12) and (26), we obtain

$\displaystyle~{}~{}\left|{\mathbb{P}}(Y_{k}({\varepsilon})=r)-\sum_{j=r}^{k}(-1)^{j-r}{j\choose
r}{{n}\choose j}q^{-j}-q^{-(k+\ell)}\sum_{j=k+1}^{k+t+\ell}(-1)^{j-r}{j\choose
r}{{n}\choose j}\frac{\Phi_{k+t+\ell-j}(Q)}{\Phi_{t}(Q)}\right|$
$\displaystyle\leq\frac{|{\cal E}|-1}{|{\cal
E}|}q^{-k}\sum_{j=k+1}^{k+t+\ell}\llbracket j\leq n\rrbracket{j\choose
r}{t+\ell-1\choose k+t+\ell-j}q^{(k+t+\ell-j)/2}A_{j}({n},{\gamma}).$

Now (29) follows by using (20) and noting (as in the proof of Theorem 1)

$\sum_{j=r}^{k+t+\ell}(-1)^{j-r}{j\choose r}{{n}\choose
j}q^{-j}=\mu_{k+t+\ell-r}(r){{n}\choose r}q^{-r}.$

The following lemma provides the upper bounds for $A_{j}(n,{\gamma})$ which
will be used in the proof of Theorem 2. Part ($a$) is [12, Lemma 1].

###### Lemma 1

Let $n\geq 1$. Then

  * (a)

For all $1\leq j\leq n$ and $b\in[0,1]$, we have

$\displaystyle\ln A_{j}(n,{\gamma})$
$\displaystyle\leq\frac{j}{p}\ln\frac{n+j}{j}+\frac{n(1-{\gamma})}{p}\ln\frac{n+j}{n}+n{\gamma}\ln(2p).$
(30)

  * (b)

For all $1\leq j\leq 2pn{\gamma}$ and ${\gamma}\in(0,1]$, we have

$\displaystyle\ln A_{j}(n,{\gamma})$ $\displaystyle\leq
j\ln\frac{n{\gamma}+j}{j}+n{\gamma}\ln\frac{n{\gamma}+j}{n{\gamma}}+\frac{n(1-{\gamma})}{p}\ln
3.$ (31)

Proof From (24), we have

$\displaystyle\sum_{j\geq 0}A_{j}(n,{\gamma})z^{j}$
$\displaystyle=(1-z)^{-n{\gamma}}(1-z^{p})^{-n(1-{\gamma})/p}.$

It follows that, for $0<y<1$,

$\displaystyle A_{j}(n,{\gamma})$ $\displaystyle\leq
y^{-j}(1-y)^{-n{\gamma}}(1-y^{p})^{-n(1-{\gamma})/p},$ $\displaystyle\ln
A_{j}(n,{\gamma})$ $\displaystyle\leq j\ln
y^{-1}+n{\gamma}\ln(1-y)^{-1}+\frac{n(1-{\gamma})}{p}\ln\left(1-y^{p}\right)^{-1}.$
(32)

To minimize the above upper bound, we choose $y$ near the solution to the
following saddle point equation

$\displaystyle-\frac{j}{y}+n{\gamma}\frac{1}{1-y}+n(1-{\gamma})\frac{y^{p-1}}{1-y^{p}}=0,~{}~{}i.e.,~{}~{}~{}{\gamma}\frac{y}{1-y}+(1-{\gamma})\frac{y^{p}}{1-y^{p}}=\frac{j}{n}.$
(33)

Part (a) was proved in [12]. Since a similar argument will also be used for
part (b), we repeat it here. When ${\gamma}$ is near $0$, we may drop the term
${\gamma}\frac{y}{1-y}$ in (33) to obtain the following approximate solution :

$\displaystyle y=\left(\frac{j}{n+j}\right)^{1/p}.$

Substituting this into (32), we obtain

$\displaystyle\ln A_{j}(n,{\gamma})$
$\displaystyle\leq\frac{j}{p}\ln\frac{n+j}{j}+\frac{n(1-{\gamma})}{p}\ln\left(\frac{n+j}{n}\right)+n{\gamma}\ln\left(1-\left(\frac{j}{n+j}\right)^{1/p}\right)^{-1}.$
(34)

Since $(\ln 2)/p\leq(\ln 2)/2<0.5$, we have

$\displaystyle\left(\frac{1}{2}\right)^{1/p}=\exp\left(\frac{-\ln
2}{p}\right)\leq 1-\left(\frac{3}{4}\right)\left(\frac{\ln 2}{p}\right),$

and consequently

$\displaystyle\left(\frac{j}{n+j}\right)^{1/p}$
$\displaystyle\leq\left(\frac{1}{2}\right)^{1/p}\leq 1-\frac{3\ln 2}{4p},$
$\displaystyle\ln\left(1-\left(\frac{j}{n+j}\right)^{1/p}\right)^{-1}$
$\displaystyle\leq\ln\left(\frac{3\ln 2}{4p}\right)^{-1}\leq\ln(2p).$ (35)

Substituting (35) into (34), we obtain (30).

(b) When $p$ is large, $y^{p}$ is near zero and we drop the term
$\displaystyle(1-{\gamma})\frac{y^{p}}{1-y^{p}}$ in (33) to obtain the
following approximate solution:

$y=\frac{j}{n{\gamma}+j}.$

Substituting this into (32), we obtain

$\displaystyle\ln A_{j}(n,{\gamma})$ $\displaystyle\leq
j\ln\frac{n{\gamma}+j}{j}+n{\gamma}\ln\left(\frac{n{\gamma}+j}{n{\gamma}}\right)+\frac{n(1-{\gamma})}{p}\ln\left(1-\left(\frac{j}{n{\gamma}+j}\right)^{p}\right)^{-1}.$
(36)

Using the assumption $\displaystyle j\leq 2pn{\gamma}$, we obtain

$\displaystyle\left(\frac{j}{n{\gamma}+j}\right)^{p}$
$\displaystyle\leq\left(1+\frac{1}{2p}\right)^{-p}\leq\frac{2}{3},$
$\displaystyle\ln\left(1-\left(\frac{j}{n{\gamma}+j}\right)^{p}\right)^{-1}$
$\displaystyle\leq\ln 3.$

It follows from (36) that

$\displaystyle\ln A_{j}(n,{\gamma})$ $\displaystyle\leq
j\ln\frac{n{\gamma}+j}{j}+n{\gamma}\ln\left(\frac{n{\gamma}+j}{n{\gamma}}\right)+\frac{n(1-{\gamma})}{p}\ln
3.$

which is (31).

##  5 Proof of Theorem 2

Proof of Theorem 2: Since the case $k-r\to\infty$ has already been covered by
Theorem 1, we assume $r\geq k-\ln k$ below. Thus, we have

$\displaystyle t+\ell=O(\sqrt{n}),\quad q=n+O(\sqrt{n}),\quad\hbox{and
}~{}r-k$ $\displaystyle=O(\sqrt{n}).$ (37)

It follows from (12) that $\mu_{m}(r)\geq c+O(1/\sqrt{n}),$ which is bounded
away from 0. It follows from (8) that

$\displaystyle~{}~{}\left|q^{-k-\ell}\sum_{j=k+1}^{k+t+\ell}(-1)^{j-r}{n-r\choose
j-r}\frac{\Phi_{k+t+\ell-j}(Q)}{\Phi_{t}(Q)}-\sum_{j=k+1}^{k+t+\ell}(-1)^{j-r}{n-r\choose
j-r}q^{-j}\right|$
$\displaystyle=O\left(q^{-1/2}\right)\sum_{j=k+1}^{k+t+\ell}{n-r\choose
j-r}q^{-j}$ $\displaystyle=o\left(q^{-r}\left(1+q^{-1}\right)^{q}\right)$
$\displaystyle=o\left(q^{-r}\right).$

By Theorem 4, asymptotic formula (4) holds if

$\displaystyle\sum_{j=k+1}^{k+t+\ell}{j\choose r}{t+\ell-1\choose
k+t+\ell-j}q^{(t+\ell-k-j)/2}A_{j}(n,\gamma)=o\left({n\choose
r}q^{-r}\right).$

Since $t+\ell=O(\sqrt{q})$, the above condition is implied by

$\displaystyle\ln A_{j}(n,\gamma)+\ln{j\choose r}+\ln{t+\ell-1\choose
t+\ell+k-r}-\ln{n\choose r}+\frac{t+\ell-k-j+1+2r}{2}\ln q\to-\infty.$ (38)

Set

$\displaystyle\delta$
$\displaystyle:=\frac{j}{{n}}-c=\frac{j}{{n}}-\frac{k}{q},\quad(r\leq j\leq
k+t+\ell),$ $\displaystyle\delta^{\prime}$
$\displaystyle:=\frac{r}{{n}}-c=\frac{r}{{n}}-\frac{k}{q}.$

By (37), we see that both $\delta$ and $\delta^{\prime}$ are of the order
$O\left(1/\sqrt{n}\right)$. Using (11) and

$\ln(2\pi x(1-x))\leq\ln(\pi/2)<1,~{}~{}(0<x<1)$

we obtain

$\displaystyle\ln{{n}\choose r}$
$\displaystyle\geq{n}\left((c+\delta^{\prime})\ln\frac{1}{c+\delta^{\prime}}+(1-c-\delta^{\prime})\ln\frac{1}{1-c-\delta^{\prime}}\right)-\frac{1}{2}\ln{n}-\frac{2}{3}$
$\displaystyle\geq{n}\left(c\ln\frac{1}{c}+(1-c)\ln\frac{1}{1-c}\right)+O(\sqrt{n}).$
(39)

Noting

$\displaystyle\ln{j\choose r}$ $\displaystyle=\ln{j\choose j-r}\leq(j-r)\ln
j=O(\sqrt{n}\ln n),$ $\displaystyle\ln{t+\ell-1\choose t+\ell+k-r}$
$\displaystyle\leq\ln 2^{t+\ell-1}=O(\sqrt{n}),$

we obtain

$\displaystyle~{}~{}\ln{j\choose r}+\ln{t+\ell-1\choose
t+\ell+k-r}-\ln{n\choose r}+\frac{t+\ell-k-j+1+2r}{2}\ln q$
$\displaystyle\leq-{n}\left(c\ln\frac{1}{c}+(1-c)\ln\frac{1}{1-c}\right)+O(\sqrt{n}\ln
n).$ (40)

We first consider Condition A. Using (30), we obtain

$\displaystyle\ln A_{j}(n,\gamma)$
$\displaystyle\leq{n}\left(\frac{c+\delta}{p}\ln\frac{1+c+\delta}{c+\delta}+\frac{1}{p}\ln\left(1+c+\delta\right)+{\gamma}\ln(2p)\right)$
$\displaystyle\leq{n}\left(\frac{c}{p}\ln\frac{1+c}{c}+\frac{1}{p}\ln(1+c)+{\gamma}\ln(2p)\right)+O\left(\sqrt{n}\right).$

Thus

$\displaystyle~{}~{}~{}\ln A_{j}(n,\gamma)+\ln{j\choose r}+\ln{t+\ell-1\choose
t+\ell+k-r}-\ln{n\choose r}+\frac{t+\ell-k-j+1+2r}{2}\ln q$
$\displaystyle\leq-{n}\left(c\ln\frac{1}{c}+(1-c)\ln\frac{1}{1-c}-\frac{c}{p}\ln\frac{1+c}{c}-\frac{1}{p}\ln(1+c)-{\gamma}\ln(2p)+O\left(\frac{\ln
n}{\sqrt{n}}\right)\right),$

which implies (38) under Condition A.

Now we consider Condition B. Using (31) and

$c\ln\left(1+\frac{{\gamma}}{c}\right)\leq\gamma,$

we obtain

$\displaystyle\ln A_{j}(n,\gamma)$ $\displaystyle\leq j\ln\frac{\gamma
n+j}{j}+{\gamma}n\ln\frac{{\gamma}n+j}{{\gamma}n}+\frac{n(1-{\gamma})}{p}\ln
3$ $\displaystyle\leq
n\left((c+\delta)\ln\frac{c+\delta+{\gamma}}{c+\delta}+{\gamma}\ln\frac{c+\delta+{\gamma}}{{\gamma}}+\frac{1-{\gamma}}{p}\ln
3\right)$ $\displaystyle\leq
n\left({\gamma}+{\gamma}\ln\frac{c+{\gamma}}{{\gamma}}+\frac{1}{p}\ln
3+O\left(\frac{1}{\sqrt{n}}\right)\right).$

It follows from (40) that

$\displaystyle~{}~{}~{}\ln A_{j}(n,\gamma)+\ln{j\choose r}+\ln{t+\ell-1\choose
t+\ell+k-r}-\ln{n\choose r}+\frac{t+\ell-k-j+1+2r}{2}\ln q$
$\displaystyle\leq-{n}\left(c\ln\frac{1}{c}+(1-c)\ln\frac{1}{1-c}-{\gamma}-{\gamma}\ln\frac{c+{\gamma}}{{\gamma}}+O\left(\frac{\ln
n}{\sqrt{n}}+\frac{1}{p}\right)\right),$

which implies (38) under Condition B. This completes the proof of Theorem 2.

##  6 Conclusion

For any given $D\subseteq{\mathbb{F}}_{q}$, we proved that the number of zeros
in $D$ of a random monic polynomial over ${\mathbb{F}}_{q}$ in a given Hayes’s
equivalence class is asymptotically Poisson with mean $|D|/q$. We used the
generating functions defined on the group algebra of equivalence classes,
Weil’s bounds on the corresponding character sums, and Li-Wan’s coordinate-
sieve formula. It will be of considerable interest if the problem can be
expressed as the sum of nearly independent random variables so that the Chen-
Stein method can be applied to obtain the same results. Asymptotic formulas
are derived when the relevant parameters satisfy some simple inequalities. Our
asymptotic formulas extend those in [21, 12] about the distance distribution
in Reed-Solomon codes, and imply that all words for a large family of Reed-
Solomon codes are ordinary, which further supports the deep-hole conjecture.

## References

  * [1] R. Arratia, A.D. Barbour, and S. Tavaré, Random combinatorial structures and prime factorizations, Notices Amer. Math. Soc. 44 (8) (1997) 903–910.
  * [2] Arratia R, Goldstein L, Gordon L (1989) Two moments suffice for Poisson approximations: the Chen-Stein method. Ann Prob 17, 9–25.
  * [3] Barbour AD, Holst L, Janson S, Poisson Approximation, Oxford University Press, 1992.
  * [4] B. Bollobás, Random Graphs, Academic Press, 1985.
  * [5] S. Chatterjee, P. Diaconis and E. Meckes, Exchangeable pairs and Poisson approximation, Probability Surveys 2 (2005), 64–106.
  * [6] Qi Cheng and Elizabeth Murray, On deciding deep holes of Reed-Solomon codes, In Theory and applications of models of computation, volume 4484 of Lecture Notes in Comput. Sci., 296-305. Springer, Berlin, 2007.
  * [7] S. D. Cohen, Explicit theorems on generator polynomials, Finite Fields Appl. 11 (2005), 337-357.
  * [8] G. W. Effinger and D. R. Hayes, “Additive Number Theory of Polynomials over a Finite Field”, Oxford Mathematical Monographs, Oxford Univ. Press, Oxford, 1991.
  * [9] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.
  * [10] Z. Gao, Counting polynomials over finite fields with prescribed leading coefficients and linear factors, Finite Fields Appl. 82 (2022) 102052
  * [11] Z. Gao, S. Kuttner, and Q. Wang, Counting irreducible polynomials with prescribed coefficients over a finite field, Finite Fields Appl. 80 (2022), 102023, 27pp.
  * [12] Z. Gao and J. Li, Improved error bounds for the distance distribution of Reed-Solomon codes, IEEE Transactions on Information Theory, 69(6) (2023), 3590-3596.
  * [13] Z. C. Gao and D. Panario, Degree Distribution of the Greatest Common Divisor of Polynomials over $F_{q}$, Random Structure and Algorithms, 29 (2006), 26–37.
  * [14] D. R. Hayes, The distribution of irreducibles in $GF[q,x]$, Trans. Amer. Math. Soc. 117 (1965), 101-127.
  * [15] C. N. Hsu, The distribution of irreducible polynomials in $\mathbb{F}_{q}[t]$, J. Number Theory 61 (1) (1996) 85–96.
  * [16] A. Knopfmacher and J. Knopfmacher, Counting polynomials with a given number of zeros in a finite field, Linear Multilinear Algebra, 26 (1990), 287-292.
  * [17] A. Knopmacher, J. Knopmacher, Counting irreducible factors of polynomials over a finite field, Discrete Math. 112 (1993), 103–118.
  * [18] A. Knopfmacher and R. Warlimont, Distinct degree factorizations for polynomials over a finite field, Trans. Amer. Math. Soc. 347 (6) (1995) 2235–2243.
  * [19] S. Kuttner and S. Wang, On the enumeration of polynomials with prescribed factorization pattern, Finite Fields Appl. 81 (2022), 32pp.
  * [20] J. Li and D. Wan, A new sieve for distinct coordinate counting, Science in China Series A 53 (2010) 2351-2362.
  * [21] J. Li and D. Wan, Distance distribution in Reed-Solomon codes, IEEE Trans. Inform. Theory 66 (5) (2020), 2743–2750.
  * [22] X. Xu and S. Hong, On Ordinary Words of Standard Reed–Solomon Codes over Finite Fields, Algebra Colloquium 28(4) (2021), 569-580.
  * [23] H. Zhou, L. Wang, W. Wang, Counting polynomials with distinct zeros in finite fields, J. Number Theory 174 (2017), 118-135.