On the maximum cardinality of the image of a non-onto polynomial function on finite fields Let $F$ be a finite field of cardinality $q$ and let $f \in F[x]$ be a non-constant polynomial of degree $d$ which is not onto (as a function from $F$ to $F$). Then how large the image of $f$ could be ?! I am looking for an answer in terms of $q$ and $d$ (if possible). 
 A: I assume that by $d$ you mean the degree of $f$.  Then the results are as follows, where I write $N$ for the size of the image $f(F)$:


*

*$N \le q - \lceil \frac{q-1}d\rceil$

* If $q$ is a power of a smaller positive integer $r$, then $f(x)=x^r+x^{r-1}$ satisfies $N=q-\frac q r$, and hence achieves equality in item 1.

* If $N\ne q(1-\frac1d)$ then $N\le q(1-\frac2d)+c_d\sqrt{q}$, where $c_d$ is a constant which depends only on $d$.

* If $\gcd(d,q)=1$ then $N\le \frac56q+c_d\sqrt{q}$, with $c_d$ as in item 3.

* Most degree-$d$ polynomials over $\mathbf{F}_q$ satisfy $\lvert N - q(1-\frac{1}{2!}+\frac{1}{3!}-\dots+(-1)^{d-1}\frac{1}{d!})\rvert < c_d \sqrt{q}$, with $c_d$ as above.  Note that this means $N$ is approximately $q(1-\frac1e)$. 


Item 1 was first proved by Kenneth Williams for prime $q$, then by Daqing Wan for arbitrary $q$.  An especially elegant proof was given by Gerhard Turnwald ("A new criterion for permutation polynomials").
Item 2 was proved by Thomas Cusick and Peter Mueller.
Item 3 is obtained by combining a result of Bob Guralnick and Daqing Wan (which depends on the classification of finite simple groups) with some results from John Flynn's thesis (Berkeley, 2001; the results were subsequently reproved by Bob Guralnick, "Rational maps and images of rational points...").
Item 4 is in the paper by Bob Guralnick and Daqing Wan, and again depends on the classification of finite simple groups.
Item 5 is obtained by combining an old result of Birch and Swinnerton-Dyer ("Note on a problem of Chowla") with a result of Kenneth Williams ("On general polynomials").
Possibly shameless plug: For more information about related questions, and details on the references, one can look into a recent 3-page survey on this topic that I wrote with Gary Mullen, which is available on my webpage and also in the book "Handbook of Finite Fields".
