A mixing property of linear map over finite fields

Question

Let $F$ be a finite field of odd size $q$, and $\phi_0 : F \mapsto F$ be any map from $F$ to itself. For each $a \in F$, set $\phi_a : x \in F \mapsto \phi_0 (x) + ax $.

When $\phi_0 : x \mapsto x^2 $ , each image $\phi_a (F)$ has size $\frac{q+1}{2}$. It turns out that for any $\phi_0$, there's always some $a \in F$ such that $| \phi_a(F) | \geq \frac{q+1}{2}$.

But the only proof I know is somewhat artificial : it relies on the observation that $ K =\bigcup_{a \in F} \phi_a(F)^n $ is a Kakeya set of dimension $n$ over the finite field $F$. By subsequent improvements of Dvir's work on such sets, it is known that $K$ must have $\geq \left( \frac{q^2}{2q-1} \right)^n $ elements. As $n$ is arbitrary and $\frac{q^2}{2q-1} > \frac{q+1}{2} -1 $, this yields the above claim.

I've found no direct proof so far. It seems MO might be the right place to ask for such a proof.

Answer 1

Consider the $q(q-1)$ quotients $\frac{\phi_0(x)-\phi_0(y)}{x-y}$ for all pairs of distinct elements $x,y\in F$. There is a value $a\in F$ which appears at most $\frac{q(q-1)}{q}=q-1$ times. Fix this $a$. So $\phi_a(x)=\phi_a(y)$ has at most $q-1$ solutions with distinct $x,y$.

Let $r$ be the size of $\phi_a(F)$, and let $m_1,m_2,\dots,m_r$ be the frequencies of the $r$ different values. Of course $m_1+m_2+\dots+m_r=q$.

On the other hand, $m_1(m_1-1)+\dots+m_r(m_r-1)\le q-1$, because the left hand side counts the solutions of $\phi_a(x)=\phi_a(y)$. We obtain $m_1^2+m_2^2+\dots+m_r^2\le 2q-1$.

The Cauchy-Schwarz inequality yields $m_1^2+m_2^2+\dots+m_r^2\ge\frac{1}{r} (m_1+m_2+\dots+m_r)^2=\frac{q^2}{r}$, hence $r\ge\frac{q^2}{2q-1}$.

So $2r\ge \frac{2q^2}{2q-1}=q+\frac{q}{2q-1}>q$, hence $2r\ge q+1$, which was asked for.

Answer 2

Lemma 21 from a joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself gives exactly what you are looking for: for any prime power $q$ (including the case of $q$ even), there exists $a\in F$ with $|\phi_a(F)|>q/2$. The proof for $q$ even is very similar to that given above by Peter Mueller, the proof for $q$ odd is slightly different.