17
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Can you, please, comment on the restriction "$q$ is even"? Is the answer known or expected to be different when $q$ is odd? $\endgroup$ Jul 20, 2012 at 23:11
  • 2
    $\begingroup$ @Victor: for $q$ odd, taking $\varphi_0(x)=x^2$ leads to all $\varphi_a({\mathbb F})$ being of size $(q+1)/2$. On the other hand, it is not difficult to see that for any choice of $\varphi_0$, there exists $a$ with $|\varphi_a({\mathbb F})|>q/2$. $\endgroup$
    – Seva
    Jul 21, 2012 at 6:04
  • $\begingroup$ What hypotheses are you requiring for $\varphi_0$? As you point out, there are functions $\varphi_0$ such that the image of $\varphi_a$ has cardinality $\ll 2q/3$, independent of the choice of $a$. But you could also take $\varphi_0(x) = x$ (or any permutation polynomial) and get the image to be all of $\mathbb{F}$. $\endgroup$ Jul 22, 2012 at 18:00
  • $\begingroup$ @Xander: no restrictions are imposed on $\varphi_0$. Taking $\varphi_0(x)=x$ is a bad choice, as in this case $\max_a|\varphi_a({\mathbb F})|$ is large. The question is, how small can one make this maximum choosing $\varphi_0$ appropriately. $\endgroup$
    – Seva
    Jul 22, 2012 at 18:28
  • $\begingroup$ Observation that might help someone else: If $\phi(x) = x^{-1}$ and $\phi(0)=0$, then $|\phi_a(\mathbb{F})| =(q-1)/2$ for all $a \neq 0$. So it's easy to get down to the tight bound for almost all $a$. $\endgroup$ Jul 23, 2012 at 20:04

4 Answers 4

10
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Fantastic! (Too short for a comment, so have to add more characters :-) $\endgroup$
    – Seva
    Jul 25, 2012 at 13:35
  • $\begingroup$ Gorgeous! I wanted a proof like this, but I couldn't find it. $\endgroup$ Jul 25, 2012 at 14:11
15
$\begingroup$

The answer is no. Consider $\phi_0(x)=x^4+x^3$ on the field $F$ of size $q=2^7$. Then $\text{max}_a\lvert\phi_a(F)\rvert=83<2q/3$.

(Initially, 83 was 79, a miscalculation as pointed out by Boris Bukh.)

Actually, if $\gamma>5/8$, then if $F$ is a field of order $q=2^r$ with $r$ odd and big enough, then $\text{max}_a\lvert\phi_a(F)\rvert\le\gamma q$.

Proof: Let $F$ be the field of order $q=2^r$, where $r$ is odd. It is easy to see that $\lvert\phi_0(F)\rvert=q/2$. (Upon setting $x=u+uv$, $y=uv$, the equation $\phi_0(x)=\phi_0(y)$ is equivalent to $u^3(v^2 + v + u + 1)$.)

Thus the case $a=0$ is fine. If $a\ne 0$, and if $t$ is a transcendental, then the Galois group of $\phi_a(X)-t=X^4+X^3+aX-t$ over $\bar F(t)$ is the symmetric group $S_4$. Here $\bar F$ is the algebraic closure of $F$.

Given that the Galois group is as claimed, an old result by Birch and Swinnerton-Dyer shows that $\lvert\phi_a(F)\rvert=(1-1/2!+1/3!-1/4!)q+O(\sqrt{q})$, where $O$ depends only on the degree, which is fixed here anyway. From $1-1/2!+1/3!-1/4!=5/8<2/3$ the claim follows.

So it remains to verify the Galois group: Using the Berlekamp discriminant, one can compute that $Gal(\phi_a(X)-t)$ contain odd permutations whenever $a\ne0$. Furthermore, an easy computation shows that $\phi_a(X)$ is polynomially indecomposable over $\bar F$, so by Lüroth the Galois group is primitive. Well, degree $4$, primitive and not contained in $A_4$ implies $S_4$.

(Reference: Birch, B. J.; Swinnerton-Dyer, H. P. F.: Note on a problem of Chowla. Acta Arith. 5 1959 417–423 (1959))

$\endgroup$
4
  • 1
    $\begingroup$ I get $83$ instead of $79$ from your example. It is still less than $2q/3$. No guarantees that my code is free of bugs though. Perhaps one can prove your hunch by taking a random function, and using a union bound together with a suitable deviation inequality. $\endgroup$
    – Boris Bukh
    Jul 23, 2012 at 14:24
  • $\begingroup$ @Peter - Is your guess based on computation, or do you have a random model in mind? $\endgroup$ Jul 23, 2012 at 17:34
  • $\begingroup$ Sounds interesting - will be happy to learn more about it. Keep in mind that results of this sort automatically yield an improvement in the finite field Kakeya problem (see the paper mentioned in my original post for the details). $\endgroup$
    – Seva
    Jul 23, 2012 at 18:35
  • $\begingroup$ Great answer! And now I see the mysterious $1 - 1/e$ showing up. $\endgroup$ Jul 24, 2012 at 7:53
10
$\begingroup$

$\def\FF{\mathbb{F}}$There is a detail that I can't get, but I need to move on to other projects. Subject to that, I can get arbitrarily close to $1/2$, for a fields of the order $2^{\ell_k}$ where $\ell_k \to \infty$. More precisely, let $r=2^k$ and let $\phi_0(x) = x^{r+1}$.

Theorem: $$\lim_{m \to \infty} \max_a |\phi_a(\FF_{2^{2km}})|/2^{2k m} = \frac{r+2}{2r+2}.$$

Taking $k=1$, so $r=2$, we recover Seva's results on $x^3$. In particular, for each $k$, we can choose $m_k$ large enough that $\max_a |\phi_a(\mathbb{F}_{2^{2 k m_k}})|/2^{2k m_k} \leq \frac{r+3}{2r+2}$, and letting $\ell_k = 2 m k$ gives the conclusion.

The actual Theorem we will be proving is slightly more precise and treats the cases of $a=0$ and $a \neq 0$ separately.

Theorem: For any $a$ and $b$ nonzero elements of $\FF_q$, we have $|\phi_a(\FF_{q})|=|\phi_b(\mathbb{F}_q)|$, a value we will term $\phi_{\neq 0}(\FF_q)$. We have $$\lim_{m \to \infty} \phi_{\neq 0}(\FF_{2^{km}})/2^{km} = \frac{r+2}{2r+2}.$$ Meanwhile, $$\phi_0(\FF_{2^{km}})/2^{km} = \begin{cases} 1/(r+1) & m\ \mbox{even} \\ 1 & m\ \mbox{odd} \end{cases}$$


The key will be to use Theorem 2 in the paper of Birch and Swinnerton-Dyer cited by Peter Mueller. Since this result is stated less precisely than we need, and in a slightly incorrect way, we rephrase. Let $f \in \FF_q[x]$ be a separable polynomial of degree $d$, and let $G$ be the Galois group of the splitting field of $f(x)-y$ over $F(y)$. Let $\FF_{q^s}$ be the algebraic closure of $\FF_q$ in this splitting field. Then we get a natural surjection $\pi: G \to \mathrm{Gal}(\FF_{q^s} / \FF_q) \cong \mathbb{Z}/s$. Define the kernel of this surjection to be $G^+$. Note that $\mathrm{Gal}(\FF_{q^s} / \FF_q)$ has a canonical generator, the Frobenius map $\mathrm{Frob}$. Note also that $G$ naturally embeds in $S_d$. We may thus say that an element of $G$ has no fixed points, meaning it has no fixed points under this embedding.

Theorem (Birch and Swinnerton-Dyer) There are constants $\lambda_0$, $\lambda_1$, ..., $\lambda_{s-1}$ such that $$|f(\FF_{q^{ms+i}})| = \lambda_i q^{ms+i} + O(q^{(ms+i)/2}).$$ Explicitly, $\lambda_i$ is the probability that a random element of $\pi^{-1}(\mathrm{Frob}^i)$ has a fixed point, and the constant in the big $O$ depends only on $d$, $G$ and $G^+$.

The paper does not give an explicit recipe for $\lambda_i$, and does not note the need to use $s$ different lambdas, but this is what I got when I traced through their proof. As a sanity check, let $q \equiv 2 \bmod 3$ and let $f(x)=x^3$. Then $G=S_3$, $G^{+}=A_3$ and $s=2$. We predict that all of the elements in $\FF_{q^{2m+1}}$ are cubes, but only $1/3$ of the elements in $\FF_{q^{2m}}$; this is true.

Our actual result will be the following: Theorem Let $\phi(x) = x^{r+1}$ as before and work over the ground field $\FF_r$. When $f=\phi_a$ for $a \neq 0$, then $G=G^{+}=PGL_2(\FF_r)$, acting on $r+1$ elements by the natural action on $\mathbb{P}^1(\FF_r)$. When $a=0$, we have $G=\mathbb{Z}/2 \ltimes \mathbb{Z}/(r+1)$, acting on $r+1$ elements by the dihedral action, and $G^{+} = \mathbb{Z}/(r+1)$.

We then must compute the proportion of elements in each case which have fixed points.


So, let's prove that the Galois group is as stated. First, for $a \neq 0$, the change of variables $x'=a^{1/r} x$ turns $\phi_a(x)$ into $a^{-(r+1)/r} \phi_1(x')$. (Since we are working in finite fields, we can always take $r$-th roots.) So it is enough to consider $\phi_0$ and $\phi_1$.

The Galois group of $\phi_0$ We are interested in the splitting field of adjoining an $(r+1)$-st root of $y$ to $\FF_r(y)$. The $(r+1)$-st roots of unity live in $\FF_{r^2}$, and $\mathrm{Gal}(\FF_{r^2}/\FF_r)$ acts on them by inversion. So $G=\mathbb{Z}/2 \ltimes \mathbb{Z}/(r+1)$ and $G^{+} = \mathbb{Z}/(r+1)$ as claimed.

The Galois group of $\phi_1$ We first explain the bijection between the roots of $x^{r+1}+x=y$ and $\mathbb{P}^1(\FF_r)$. Consider the roots of the equation $z^{r^2}+z^r=yz$. Clearly, they form an $\FF_{r}$ vector space under the ordinary operations of addition and multiplication; call this vector space $V$. It has dimension $2$. For $z$ any nonzero element of $V$, the element $x=z^{r-1}$ is a root of $x^{r+1} + x=y$. Moreover, if $z'$ is a scalar multiple of $z$, then $z^{r-1} = (z')^{r-1}$. So roots of $x^{r+1} + x=y$ label lines in $V$.

This construction is natural enough to prove that $G \subseteq PGL(V) \cong PGL_2(\FF_r)$. We now need to show $G^{+} = PGL_2$, and thus that $G=G^{+}$ as well.

Here is the missing detail. There is a very similar result of Serre, published as an appendix in a paper of Abhyankar, that the splitting field of $z^{r+1} - wz+1$ is $PSL_2(\FF_r)$. I feel like there should be some simple monomial change of variables that turns $(z,w)$ into $(x,y)$ and let's us deduce our result from Serre's. (Note that $PGL_2=PSL_2=SL_2$ in characteristic $2$.) But I keep not getting it to work.


So, we now need to count the number of fixed points for the dihedral and the $PGL_2$ action.

The dihedral action Since $r+1$ is odd, every reflection fixes a point, explaining the $1$ for $m$ odd. Nontrivial rotations do not have fixed points, explaining the $1/(r+1)$.

The $PGL_2$ action We use the isomorphism $PGL_2 = PSL_2 = SL_2$.

There are $r+1$ conjugacy classes in $SL_2$, namely

  • The identity.
  • $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$. This class has order $r^2-1$.
  • $\begin{pmatrix} t & 0 \\ 0 & t^{-1} \end{pmatrix}$ for $t \neq 1$. There are $r/2-1$ such conjugacy classes, each of order $r^2+r$.
  • Matrices that are diagonalizable over $\FF_{r^2}$ with eigenvalues $(t, t^r)$, for $t$ a nontrivial $(r+1)$-st root of unity. There are $r/2$ such conjugacy classes, each of order $r^2-r$.

The first three have fixed points, and the last doesn't. Putting it all together, the probability that an element in $PGL_2(\FF_r)$ has a fixed point is $(r+2)/(2r+2)$.

$\endgroup$
3
  • $\begingroup$ Wow! I will be traveling till mid September and will hardly be able to check the details in the future foreseen, but I impressed both by the result (modulo the missing detail) and the technique involved! $\endgroup$
    – Seva
    Jul 24, 2012 at 15:18
  • 2
    $\begingroup$ Beautiful argument! Two minor comments: Missing detail: I think this follows from looking at the ramification of the place $y\mapsto0$ in the splitting field of $x^{r+1}+x-y$: The factorization $x^{r+1}+x=x(x+1)^r$ tells us that the intertia group fixes a point and is transitive on the remaining $r$ points. So a Sylow $2$-subgroup of $G^+$ has order $r$. But this gives $G^+=PGL(2,r)$. Reference: Cohen, Stephen D.: The distribution of polynomials over finite fields. Acta Arith. 17 1970 255–271, contains the facts used by Speyer, which are not so clear in Birch/Swinnerton-Dyer. $\endgroup$ Jul 24, 2012 at 18:39
  • 1
    $\begingroup$ The connection of $x^{r+1}+x-y$ with the Serre polynomial $z^{r+1}-wz+1$ is provided by $y=v^{r+1}$, $x=vz$, $v^r=w$. Note that the translates with cyclic (or the purely insepable extension given by $v^r=w$) extensions doesn't change Galois groups. $\endgroup$ Jul 24, 2012 at 19:15
6
$\begingroup$

This is a justification of Peter Mueller's guess. Write $n=|\mathbb{F}|$ and put $m=\delta n$ where $\delta>1-1/e$ is arbitrary. Let $\phi_0$ be a random function, chosen uniformly from among all functions $\mathbb{F}\to\mathbb{F}$. For each $a$, the function $\phi_a$ is uniformly distributed. Let $X$ be the size of image of $\phi_0$. Let $p=\Pr[X>m]$. If $pn<1$, then there is a choice of $\phi_0$ such the image of $\phi_a$ is at most $m$. The expected size of $X$ is $\bigl(1-1/e+o(1)\bigr)n$ since the probability that any given element is in the image of $\phi$ is $1-(1-1/n)^n$. Furtermore, if we think of throwing $n$ balls into $n$ bins as a martingale of length $n$, Azuma's inequality implies that $\Pr\bigl[X-E[X]>C\sqrt{n\log n}\,\bigr]<n^{-C'}$. Choosing $C$ large enough, we get the desired conclusion.

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