1 Introduction
The value set of a polynomial
$f(X) \in {\mathbb F}_{q}[X]$
over a finite field
${\mathbb F}_{q}$
of q elements is the set
${\mathcal V}(f) = \{ f(a):~a \in {\mathbb F}_{q} \}$
and we define
$V(f) = \# {\mathcal V}(f)$
.
In the case of binomials
$f(X) = X +aX^{n} \in {\mathbb F}_{p}[X]$
the bound of [Reference Shparlinski and VolochShVo18, Theorem 3.5] asserts that
$$ \begin{align*}V(f) \ge \max\{p/d, d, e, p/e\}, \end{align*} $$
where
$$ \begin{align} d=\gcd(n,p-1) \qquad \mbox{and} \qquad e=\gcd(n-1,p-1). \end{align} $$
Unfortunately, the proof contains some wrong calculations, and in particular, the bound
$V(f) \ge p/d$
is not correctly justified. In fact, it is easy to see that this bound is wrong. For example, for
$f(X) = X - X^{n}$
for
$d=1,$
this bound implies
$V(f) =p$
, while we have
$f(0) = f(1)=0$
and thus
$V(f) \le p-1$
.
Here, we formulate and prove a corrected version.
Theorem 1.1 Let
$f(X) = X +aX^{n} \in {\mathbb F}_{p}[X]$
,
$1 < n < p$
, and let d and e be as in (1.1). Then
$$ \begin{align*}V(f) \ge \max\{d, (p-1)/(e+1), e+1\}. \end{align*} $$
Proof Note, that for distinct dth roots of unity, that is, for u with
$u^{d} =1$
, the values
$f(u) = u+a$
are pairwise distinct. Thus
$V(f) \ge d$
.
We now consider only the values
$x \in {\mathbb F}_{p}^{*}$
. The equation
$$ \begin{align} f(x)=f(y), \qquad x,y \in {\mathbb F}_{p}^{*}, \end{align} $$
becomes, with
$y=tx$
,
$t \in {\mathbb F}_{p}^{*}$
, the same as
$$ \begin{align*}x + ax^{n} = tx + at^{n}x^{n}, \qquad t, x \in {\mathbb F}_{p}^{*}, \end{align*} $$
or
$$ \begin{align} 1 + ax^{n-1} = t + at^{n}x^{n-1}, \qquad t, x \in {\mathbb F}_{p}^{*}, \end{align} $$
If
$t=1,$
then there are
$p-1$
possible values of x satisfying (1.3).
For other
$p-2$
values of t, if
$t^{n}=1$
, the equation (1.3) has no solution whereas if
$t^{n} \ne 1$
, it defines a unique value of
$x^{n-1}$
, which leads to e possible value of x. Hence, the number of solutions to the equation (1.3), and thus equation (1.2) as well, is
${p-1+ e(p-2)}$
, which is bounded by
$(e+1)(p-1)$
.
By the Cauchy inequality,
$$ \begin{align*} (p-1)^{2} & =\left(\sum_{\lambda \in {\mathbb F}_{p}} \#\{x \in {\mathbb F}_{p}^{*}:~f(x) =\lambda\}\right)^{2} \\ & \le V^{*}(f) \sum_{\lambda \in {\mathbb F}_{p}} \left(\#\{x \in {\mathbb F}_{p}^{*}:~f(x) =\lambda\}\right)^{2}, \end{align*} $$
since the sum over
$\lambda $
is supported on
$V^{*}(f)$
terms, where
$ V^{*}(f) $
is the number of distinct values of
$f(x)$
with
$x \in {\mathbb F}_{p}^{*}$
. Hence,
$$ \begin{align*} (p-1)^{2} & \le V^{*}(f) \#\{(x,y)\in {\mathbb F}_{p}^{*} \times {\mathbb F}_{p}^{*}:~f(x) =f(y)\}\\ & \le V^{*}(f) (e+1)(p-1). \end{align*} $$
Therefore,
$$ \begin{align*}V(f) \ge V^{*}(f) \ge (p-1)/ (e+1). \end{align*} $$
Furthermore, we now fix a nonzero eth power c with
$1+ac \ne 0$
. Clearly for e distinct eth roots of c, that is, for u with
$u^{e} =c$
the values
$f(u) = u(1+ac)$
are pairwise distinct, and we can also add
$f(0) = 0$
. Thus
$V(f) \ge e+1$
.
The result now follows.▪
We now immediately obtain:
Corollary 1.2 If
$f(X) = X +aX^{n} \in {\mathbb F}_{p}[X]$
,
$1 < n < p$
, then
$V(f) \ge \sqrt {p-1}$
.
Acknowledgment
The authors would like to thank Michael Zieve for pointing out some gaps in the original version of [Reference Shparlinski and VolochShVo18, Theorem 3.5].
