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](http://arxiv.org/abs/0901.2529) 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.



A mixing property of linear map over finite fields
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.


