MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 13 down vote accepted

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.

share|cite|improve this answer
Thanks ! It's amusing that the same constant $\frac{q^2}{2q-1}$ appears here and also as the limit of the polynomial method in the Kakeya problem. – user25235 Jul 20 '12 at 13:04

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.