Return to Question

In connection with this MO post, here is a question somewhat implicitly contained in a joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself.

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, 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$.

In connection with this MO post, here is a question somewhat implicitly contained in a joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself.

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, 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$.

In connection with this MO post, here is a question somewhat implicitly contained in a joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself.

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, 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$.

Added July 28, 2012

With all the nice math involved in the answers below, and despite the fact that my original question, as stated, got answered, there is something which still prevents me from considering the problem closed. Namely, as shown by Peter Mueller and David Speyer, as $q$ runs over powers of $2$, one has $$ \liminf_{q\to\infty} \frac1q \min_{\varphi_0}\max_a|\varphi_a({\mathbb F}_q)|=\frac 12; $$ but isn't it true that, indeed, $$ \limsup_{q\to\infty} \frac1q \min_{\varphi_0}\max_a|\varphi_a({\mathbb F}_q)|=\frac 12 $$ holds? What is the value of the $\limsup$ in the left-hand side?

In connection with this MO post, here is a question somewhat implicitly contained in a joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself.

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, 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$.

In connection with this MO post, here is a question somewhat implicitly contained in a joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself.

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, 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$.

In connection with this MO post, here is a question somewhat implicitly contained in a joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself.

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, 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$.

Added July 28, 2012

With all the nice math involved in the answers below, and despite the fact that my original question, as stated, got answered, there is something which still prevents me from considering the problem closed. Namely, as shown by Peter Mueller and David Speyer, as $q$ runs over powers of $2$, one has $$ \liminf_{q\to\infty} \frac1q \min_{\varphi_0}\max_a|\varphi_a({\mathbb F}_q)|=\frac 12; $$ but isn't it true that, indeed, $$ \limsup_{q\to\infty} \frac1q \min_{\varphi_0}\max_a|\varphi_a({\mathbb F}_q)|=\frac 12 $$ holds? What is the value of the $\limsup$ in the left-hand side?