A mixing property for finite fields of characteristic $2$ - MathOverflow

A mixing property for finite fields of characteristic $2$

2012-07-20T16:54:08Z

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

Answer by Peter Mueller for A mixing property for finite fields of characteristic $2$

2012-07-23T13:45:46Z

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))

Answer by David Speyer for A mixing property for finite fields of characteristic $2$

2012-07-24T15:06:07Z

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

Answer by Boris Bukh for A mixing property for finite fields of characteristic $2$

2012-07-24T16:08:11Z

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.

Answer by Peter Mueller for A mixing property for finite fields of characteristic $2$

2012-07-25T12:29:36Z

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.