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). 



On the maximum cardinality of the image of a non-onto polynomial function on finite fields
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)$:


1. $N \le q - \lceil \frac{q-1}d\rceil$
2. 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.
3. 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$.
4. If $\gcd(d,q)=1$ then $N\le \frac56q+c\_d\sqrt{q}$, with $c\_d$ as in item 3.
5. 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".


