Improving bounds for value sets of polynomials over finite fields

Abstract

Let ${\mathbb{F}}_q$ be a finite field of characteristic $p$, and let $f\in {\mathbb{F}}_q[x]$ be a polynomial of degree $d>0$. Denote the image set of this polynomial as $V_f=\{f(\hat{I}\pm )\mid \hat{I}\pm \in {\mathbb{F}}_q\}$ and denote the cardinality of this set as $N_f$. A much sharper bound for $N_f$ is established in this paper. In particular, for any $p\ne 2,3$, and for nearly every generic quartic polynomial $f\in {\mathbb{F}}_q[x]$, we obtain $$|N_f-\frac{5}{8}q|\le \frac{1}{2}\sqrt{q}+\frac{15}{4},$$ which holds as a simple corollary of the main result.

17 pages, 1 figure, corrected typos, added clarifications, result basically unchanged