In connection with [this MO post](https://mathoverflow.net/questions/102725/a-mixing-property-of-linear-map-over-finite-fields), here is a question somewhat implicitly contained in a [joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself](http://arxiv.org/pdf/1003.3736.pdf).


Let ${\mathbb F}$ be a finite field, and suppose that $\varphi\_0\colon{\mathbb F}\mapsto{\mathbb F}$ is a function from ${\mathbb F}$ to itself. For each $a\in{\mathbb F}$, consider the function $\varphi\_a\colon{\mathbb F}\mapsto{\mathbb F}$ defined by $\varphi\_a(x)=\varphi\_0(x)+ax$ ($x\in{\mathbb F}$).



> 
> Is it true that if $q:=|{\mathbb F}|$ is *even*, then there exists $a\in{\mathbb F}$ such that the image of $\varphi\_a$ has size larger than $2q/3$?
> 
> 
> 


(A negative answer would yield an improvement on the known bounds for the smallest size of a Kakeya set in the vector spaces ${\mathbb F}^n$.)




---


It may be worth explaining where the coefficient $2/3$ comes from. In [the aforementioned paper](http://arxiv.org/pdf/1003.3736.pdf), we show that if $q$ is an even power of $2$, then for $\varphi\_0(x)=x^3$ one has $\max\_a |\varphi\_a({\mathbb F})|\le(2q+1)/3$, whereas if $q$ is an odd power of $2$, then for $\varphi\_0(x)=x^{q-2}+x^2$ one has $\max\_a |\varphi\_a({\mathbb F})|\le2(q+\sqrt q+1)/3$. The question is whether one can get better bounds for an appropriate choice of the function $\varphi\_0$.



A mixing property for finite fields of characteristic $2$
The use of Birch/Swinnerton-Dyer in my previous and David Speyer's answer is vaste overkill!
Actually in David's example one can compute exactly the value set sizes. I do only the relevant case $m=1$. (As the size is exact, there is no need for the asymptotic consideration $m\to\infty$, only $r\to\infty$ matters.)


*Theorem.* Set $r=2^k$, $F=GF(r^2)$ and $\phi\_0(x)=x^{r+1}$. Then $\lvert\phi\_a(F)\rvert=\frac{r(r+1)}{2}=\frac{r+1}{2r}\lvert F\rvert$ if $a\ne0$, and $\lvert\phi\_0(F)\rvert=r$.


*Proof.* The latter statement is trivial, and in the former statement it suffices to assume $a=1$, for if $b^r=a$, then $\phi\_a(bx)=b^{r+1}\phi\_1(x)$. Let $T(x)=x^r+x$ be the trace map from $F$ to $GF(r)$. Note that $x^{r+1}\in GF(r)$ for all $x\in F$. Thus if $\phi\_1(x)=\phi\_1(y)$ for $x,y\in F$, then $\delta=y-x\in GF(r)$. Given $x\in F$, we count the number of $0\ne\delta\in GF(r)$ with $\phi\_1(x)=\phi\_1(x+\delta)$. A short calculation gives the equivalent relation $\delta=T(x)+1$. Comparing dimensions, we see that $T$ is surjective as $GF(r)$ is the kernel of $T$. Thus there are exactly $r$ elements $x$ with $T(x)+1=0$. So $\phi\_1$ assumes $(r^2-r)/2$ values twice, and $r$ values once. From $(r^2-r)/2+r=r(r+1)/2$ the claim follows. 


