9
$\begingroup$

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.

$\endgroup$

2 Answers 2

13
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – user25235
    Jul 20, 2012 at 13:04
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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