The distribution of values of polynomials over a finite field (Q917600)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The distribution of values of polynomials over a finite field |
scientific article |
Statements
The distribution of values of polynomials over a finite field (English)
0 references
1990
0 references
For a given polynomial f(X) of \({\mathbb{F}}_ q[X]\), the polynomial ring in X over a finite field \({\mathbb{F}}_ q\) with q elements, let V(f) denote the number of distinct values assumed by f(X) in \({\mathbb{F}}_ q\). Denote by \(V_ n(t)\) the number of monic polynomials \(f\in {\mathbb{F}}_ q[X]\) of degree t with \(V(f)=n\), and by \(V^*_ n(t)\) the number of all polynomials \(f\in {\mathbb{F}}_ q[X]\) of degree \(\leq t\) with \(V(f)=n\). The authors prove that one has, for \(t\geq q\), \(1\leq n\leq q\), \[ V_ n(t)=\left( \begin{matrix} q\\ n\end{matrix} \right)n!\quad S(q,n)q^{t-q}, \] and, for \(t\geq q-1\), \(1\leq n\leq q\), \[ V^*_ n(t)=\left( \begin{matrix} q\\ n\end{matrix} \right)n!\quad S(q,n)q^{t-q+1}, \] where S(q,n) denotes a Stirling number of the second kind. The variance of V(f) for monic polynomials f of degree t about the mean is also determined explicitly.
0 references
polynomial ring
0 references
finite field
0 references
number of distinct values
0 references
number of monic polynomials
0 references
variance
0 references