Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers

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|improve this answer
2  
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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.