Values of polynomials over finite fields
Joachim von zur Gathen · Bulletin of the Australian Mathematical Society · 1991
Let q be a prime power, F q a field with q elements, f ∈ F q [x] a polynomial of degree n ≥ 1, V ( f ) = # f (F q ) the number of different values f (α) of f , with α ∈ F q , and p = q – V ( f ). It is shown that either ρ = 0 or 4 n 4 > q or 2 pn > q . Hence, if q is “large” and f is not a permutation polynomial, then either n or ρ is “large”.