A mixing property for finite fields of characteristic $2$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T06:37:30Z http://mathoverflow.net/feeds/question/102751 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/102751/a-mixing-property-for-finite-fields-of-characteristic-2 A mixing property for finite fields of characteristic $2$ Seva 2012-07-20T16:54:08Z 2012-08-07T19:38:09Z <p>In connection with <a href="http://mathoverflow.net/questions/102725/a-mixing-property-of-linear-map-over-finite-fields" rel="nofollow">this MO post</a>, here is a question somewhat implicitly contained in a <a href="http://arxiv.org/pdf/1003.3736.pdf" rel="nofollow">joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself</a>.</p> <p>Let ${\mathbb F}$ be a finite field, and suppose that <code>$\varphi_0\colon{\mathbb F}\mapsto{\mathbb F}$</code> is a function from <code>${\mathbb F}$</code> to itself. For each <code>$a\in{\mathbb F}$</code>, consider the function <code>$\varphi_a\colon{\mathbb F}\mapsto{\mathbb F}$</code> defined by <code>$\varphi_a(x)=\varphi_0(x)+ax$</code> (<code>$x\in{\mathbb F}$</code>).</p> <blockquote> <p>Is it true that if <code>$q:=|{\mathbb F}|$</code> is <em>even</em>, then there exists <code>$a\in{\mathbb F}$</code> such that the image of $\varphi_a$ has size larger than $2q/3$?</p> </blockquote> <p>(A negative answer would yield an improvement on the known bounds for the smallest size of a Kakeya set in the vector spaces <code>${\mathbb F}^n$</code>.)</p> <hr> <p>It may be worth explaining where the coefficient $2/3$ comes from. In <a href="http://arxiv.org/pdf/1003.3736.pdf" rel="nofollow">the aforementioned paper</a>, we show that if $q$ is an even power of $2$, then for $\varphi_0(x)=x^3$ one has <code>$\max_a |\varphi_a({\mathbb F})|\le(2q+1)/3$</code>, whereas if $q$ is an odd power of $2$, then for $\varphi_0(x)=x^{q-2}+x^2$ one has <code>$\max_a |\varphi_a({\mathbb F})|\le2(q+\sqrt q+1)/3$</code>. The question is whether one can get better bounds for an appropriate choice of the function $\varphi_0$.</p> http://mathoverflow.net/questions/102751/a-mixing-property-for-finite-fields-of-characteristic-2/102925#102925 Answer by Peter Mueller for A mixing property for finite fields of characteristic $2$ Peter Mueller 2012-07-23T13:45:46Z 2012-07-23T22:33:47Z <p>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&lt;2q/3$.</p> <p>(Initially, 83 was 79, a miscalculation as pointed out by Boris Bukh.)</p> <p>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$.</p> <p><em>Proof:</em> 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)$.)</p> <p>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$.</p> <p>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&lt;2/3$ the claim follows.</p> <p>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$.</p> <p>(Reference: Birch, B. J.; Swinnerton-Dyer, H. P. F.: Note on a problem of Chowla. Acta Arith. 5 1959 417–423 (1959))</p> http://mathoverflow.net/questions/102751/a-mixing-property-for-finite-fields-of-characteristic-2/103008#103008 Answer by David Speyer for A mixing property for finite fields of characteristic $2$ David Speyer 2012-07-24T15:06:07Z 2012-07-24T15:06:07Z <p>$\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}$.</p> <p><b>Theorem:</b> <code>$$\lim_{m \to \infty} \max_a |\phi_a(\FF_{2^{2km}})|/2^{2k m} = \frac{r+2}{2r+2}.$$</code></p> <p>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.</p> <p>The actual Theorem we will be proving is slightly more precise and treats the cases of $a=0$ and $a \neq 0$ separately.</p> <p><b>Theorem:</b> For any $a$ and $b$ nonzero elements of <code>$\FF_q$</code>, we have <code>$|\phi_a(\FF_{q})|=|\phi_b(\mathbb{F}_q)|$</code>, a value we will term <code>$\phi_{\neq 0}(\FF_q)$</code>. We have <code>$$\lim_{m \to \infty} \phi_{\neq 0}(\FF_{2^{km}})/2^{km} = \frac{r+2}{2r+2}.$$</code> Meanwhile, <code>$$\phi_0(\FF_{2^{km}})/2^{km} = \begin{cases} 1/(r+1) &amp; m\ \mbox{even} \\ 1 &amp; m\ \mbox{odd} \end{cases}$$</code></p> <hr> <p>The key will be to use Theorem 2 in the paper of <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa5/aa545.pdf" rel="nofollow">Birch and Swinnerton-Dyer</a> 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.</p> <p><b>Theorem (Birch and Swinnerton-Dyer)</b> There are constants $\lambda_0$, $\lambda_1$, ..., $\lambda_{s-1}$ such that <code>$$|f(\FF_{q^{ms+i}})| = \lambda_i q^{ms+i} + O(q^{(ms+i)/2}).$$</code> 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^+$.</p> <p>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 <code>$\FF_{q^{2m+1}}$</code> are cubes, but only $1/3$ of the elements in <code>$\FF_{q^{2m}}$</code>; this is true.</p> <p>Our actual result will be the following: <b>Theorem</b> 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 <code>$\mathbb{P}^1(\FF_r)$</code>. When $a=0$, we have <code>$G=\mathbb{Z}/2 \ltimes \mathbb{Z}/(r+1)$</code>, acting on $r+1$ elements by the dihedral action, and $G^{+} = \mathbb{Z}/(r+1)$.</p> <p>We then must compute the proportion of elements in each case which have fixed points.</p> <hr> <p>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$.</p> <p><b>The Galois group of $\phi_0$</b> 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 <code>$G=\mathbb{Z}/2 \ltimes \mathbb{Z}/(r+1)$</code> and $G^{+} = \mathbb{Z}/(r+1)$ as claimed.</p> <p><b>The Galois group of $\phi_1$</b> We first explain the bijection between the roots of $x^{r+1}+x=y$ and <code>$\mathbb{P}^1(\FF_r)$</code>. 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$.</p> <p>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.</p> <p>Here is the <b>missing detail</b>. There is a very similar result of Serre, published as an <a href="http://www.ams.org/mathscinet-getitem?mr=1118002" rel="nofollow">appendix in a paper of Abhyankar</a>, 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.</p> <hr> <p>So, we now need to count the number of fixed points for the dihedral and the $PGL_2$ action.</p> <p><b>The dihedral action</b> 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)$.</p> <p><b>The $PGL_2$ action</b> We use the isomorphism $PGL_2 = PSL_2 = SL_2$. </p> <p>There are $r+1$ conjugacy classes in $SL_2$, namely</p> <ul> <li>The identity. </li> <li><code>$\begin{pmatrix} 1 &amp; 1 \\ 0 &amp; 1 \end{pmatrix}$</code>. This class has order $r^2-1$.</li> <li><code>$\begin{pmatrix} t &amp; 0 \\ 0 &amp; t^{-1} \end{pmatrix}$</code> for $t \neq 1$. There are $r/2-1$ such conjugacy classes, each of order $r^2+r$.</li> <li>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$.</li> </ul> <p>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)$.</p> http://mathoverflow.net/questions/102751/a-mixing-property-for-finite-fields-of-characteristic-2/103017#103017 Answer by Boris Bukh for A mixing property for finite fields of characteristic $2$ Boris Bukh 2012-07-24T16:08:11Z 2012-07-24T16:08:11Z <p>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&lt;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 <code>$\Pr\bigl[X-E[X]&gt;C\sqrt{n\log n}\,\bigr]&lt;n^{-C'}$</code>. Choosing $C$ large enough, we get the desired conclusion. </p> http://mathoverflow.net/questions/102751/a-mixing-property-for-finite-fields-of-characteristic-2/103095#103095 Answer by Peter Mueller for A mixing property for finite fields of characteristic $2$ Peter Mueller 2012-07-25T12:29:36Z 2012-07-25T12:29:36Z <p>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.)</p> <p><em>Theorem.</em> 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$.</p> <p><em>Proof.</em> 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. </p>