Una mezcla de la propiedad para finitos campos de la característica $2$

Question

En relación con este MO post, aquí es una pregunta un poco implícitamente contenida en un documento común de S. Kopparty, S. Saraf, M. Sudán, y a mí mismo.

Deje ${\mathbb F}$ ser un campo finito, y supongamos que $\varphi_0\colon{\mathbb F}\mapsto{\mathbb F}$ es una función de ${\mathbb F}$ a sí mismo. Para cada una de las $a\in{\mathbb F}$, considere la función $\varphi_a\colon{\mathbb F}\mapsto{\mathbb F}$ definido por $\varphi_a(x)=\varphi_0(x)+ax$ ($x\in{\mathbb F}$).

Es cierto que si $q:=|{\mathbb F}|$ es incluso, entonces existe $a\in{\mathbb F}$ de manera tal que la imagen de $\varphi_a$ tiene un tamaño mayor que $2q/3$?

(Una respuesta negativa podría resultar en una mejora en los conocidos límites para el tamaño más pequeño de un conjunto de Kakeya en los espacios vectoriales ${\mathbb F}^n$.)

---

Puede ser que vale la pena explicar donde el coeficiente de $2/3$ proviene. En el mencionado documento, nos muestran que si $q$ es una potencia par de $2$, entonces para $\varphi_0(x)=x^3$ uno ha $\max_a |\varphi_a({\mathbb F})|\le(2q+1)/3$, mientras que si $q$ es un extraño poder de $2$, entonces para $\varphi_0(x)=x^{q-2}+x^2$ uno ha $\max_a |\varphi_a({\mathbb F})|\le2(q+\sqrt q+1)/3$. La pregunta es si uno puede conseguir el mejor de los límites para una elección adecuada de la función de $\varphi_0$.

Answer 1

La respuesta es no. Considere la posibilidad de $\phi_0(x)=x^4+x^3$ sobre el campo de $F$ del tamaño de la $q=2^7$. A continuación,$\text{max}_a\lvert\phi_a(F)\rvert=83<2q/3$.

(Inicialmente, de 83 años fue de 79, un error de cálculo como se ha señalado por Boris Bukh.)

En realidad, si $\gamma>5/8$, entonces si $F$ es un campo de orden de $q=2^r$ con $r$ impar y lo suficientemente grande, entonces $\text{max}_a\lvert\phi_a(F)\rvert\le\gamma q$.

Prueba: Deje $F$ a ser el campo de orden de $q=2^r$ donde $r$ es impar. Es fácil ver que $\lvert\phi_0(F)\rvert=q/2$. (Sobre la configuración de $x=u+uv$, $y=uv$, la ecuación de $\phi_0(x)=\phi_0(y)$ es equivalente a $u^3(v^2 + v + u + 1)$.)

Así, el caso de $a=0$ está bien. Si $a\ne 0$, y si $t$ es un trascendental, entonces el grupo de Galois de $\phi_a(X)-t=X^4+X^3+aX-t$ sobre $\bar F(t)$ es el grupo simétrico $S_4$. Aquí $\bar F$ es la clausura algebraica de $F$.

Dado que el grupo de Galois es como se ha dicho, una vieja resultado de Birch y Swinnerton-Dyer muestra que $\lvert\phi_a(F)\rvert=(1-1/2!+1/3!-1/4!)q+O(\sqrt{q})$ donde $O$ sólo depende de el grado, la cual se fija aquí de todos modos. De $1-1/2!+1/3!-1/4!=5/8<2/3$ la demanda de la siguiente manera.

Por lo que sigue siendo para verificar que el grupo de Galois: el Uso de la Berlekamp discriminante, se puede calcular que el $Gal(\phi_a(X)-t)$ contienen permutaciones impares siempre $a\ne0$. Además, un sencillo cálculo muestra que $\phi_a(X)$ es exponencialmente indecomposable más de $\bar F$, así que por Lüroth el grupo de Galois es primitivo. Así, el grado $4$, primitiva y no contenida en $A_4$ implica $S_4$.

(Referencia: Abedul, B. J.; Swinnerton-Dyer, H. P. F.: Nota sobre un problema de Chowla. Acta Arith. 5 1959 417-423 (1959))

Answer 2

$\def\FF{\mathbb{F}}$Hay un detalle que yo no puedo ir, pero tengo que pasar a otros proyectos. Sujeto a que puedo ser arbitrariamente cerca de $1/2$, para un los campos de la orden de $2^{\ell_k}$ donde $\ell_k \to \infty$. Más precisamente, vamos a $r=2^k$ y deje $\phi_0(x) = x^{r+1}$.

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

Tomando $k=1$, lo $r=2$, podemos recuperar Seva resultados en $x^3$. En en particular, para cada una de las $k$, se puede elegir $m_k$ suficientemente grande como para que $\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$ da de la conclusión.

El real Teorema vamos a estar probando que es un poco más precisa y trata los casos de $a=0$ e $a \neq 0$ por separado.

Teorema: Para cualquier $a$ e $b$ cero los elementos de la $\FF_q$, tenemos $|\phi_a(\FF_{q})|=|\phi_b(\mathbb{F}_q)|$, un valor que nos va a plazo $\phi_{\neq 0}(\FF_q)$. Tenemos $$\lim_{m \to \infty} \phi_{\neq 0}(\FF_{2^{km}})/2^{km} = \frac{r+2}{2r+2}.$$ Mientras tanto, $$\phi_0(\FF_{2^{km}})/2^{km} = \begin{cases} 1/(r+1) & m\ \mbox{even} \\ 1 & m\ \mbox{odd} \end{casos}$$

---

La clave será utilizar el Teorema 2 en el papel de Abedul y Swinnerton-Dyer , citado por Peter Mueller. Dado que este resultado es dijo de forma menos precisa de lo que necesitamos, y en un poco de modo incorrecto, podemos reformular. Deje $f \in \FF_q[x]$ ser un polinomio separable de grado $d$, y deje $G$ ser el grupo de Galois de la división de campo de la $f(x)-y$ sobre $F(y)$. Deje $\FF_{q^s}$ ser el algebraicas cierre de $\FF_q$ en esta división de campo. Entonces tenemos una natural surjection $\pi: G \to \mathrm{Gal}(\FF_{q^s} / \FF_q) \cong \mathbb{Z}/s$. Definir el núcleo de este surjection a ser $G^+$. Tenga en cuenta que $\mathrm{Gal}(\FF_{q^s} / \FF_q)$ tiene una canónica de generador, la Frobenius mapa de $\mathrm{Frob}$. Tenga en cuenta también que $G$ natural incrusta en $S_d$. Podemos por tanto decir que un elemento de $G$ no tiene puntos fijos, lo que significa que no tiene puntos fijos en virtud de esta incrustación.

Teorema (Birch y Swinnerton-Dyer) Hay constantes $\lambda_0$, $\lambda_1$, ..., $\lambda_{s-1}$ tal que $$|f(\FF_{q^{ms+i}})| = \lambda_i q^{ms+i} + O(q^{(ms+i)/2}).$$ Explícitamente, $\lambda_i$ es la probabilidad de que un elemento aleatorio de $\pi^{-1}(\mathrm{Frob}^i)$ tiene un punto fijo, y la constante en la gran $O$ sólo depende de $d$, $G$ y $G^+$.

El papel no da una explícita receta para $\lambda_i$, y no no se nota la necesidad del uso de $s$ diferentes lambdas, pero esto es lo que tengo cuando he trazado a través de su prueba. Como una comprobación de validez, deje que $q \equiv 2 \bmod 3$ and let $f(x)=x^3$. Then $G=S_3$, $G^{+}=A_3$ and $s=2$. Nosotros predecir que todos los elementos en $\FF_{q^{2m+1}}$ son cubos, pero sólo $1/3$ de los elementos en $\FF_{q^{2m}}$; esto es cierto.

Nuestro resultado real será la siguiente: Teorema Deje $\phi(x) = x^{r+1}$ como antes y trabajo a lo largo de la campo de tierra $\FF_r$. Al $f=\phi_a$ para $a \neq 0$, luego $G=G^{+}=PGL_2(\FF_r)$, actuando en $r+1$ elementos por la acción natural en $\mathbb{P}^1(\FF_r)$. Al $a=0$, tenemos $G=\mathbb{Z}/2 \ltimes \mathbb{Z}/(r+1)$, acting on $r+1$ de los elementos por el diedro acción, y $G^{+} = \mathbb{Z}/(r+1)$.

A continuación nos debe calcular la proporción de elementos en cada caso que tiene puntos fijos.

---

Así que, vamos a demostrar que el grupo de Galois es el indicado. En primer lugar, para que $a \neq 0$, the change of variables $x'=a^{1/r} x$ turns $\phi_a(x)$ en $a^{-(r+1)/r} \phi_1(x')$. (Ya que estamos trabajando en campos finitos, nos siempre se puede tomar $r$-th raíces.) Por lo que es suficiente para considerar las $\phi_0$ y $\phi_1$.

El grupo de Galois de $\phi_0$ Estamos interesados en la división de campo de junto a una $(r+1)$-st raíz de $y$ a $\FF_r(y)$. El $(r+1)$-st raíces de la unidad viven en $\FF_{r^2}$, y $\mathrm{Gal}(\FF_{r^2}/\FF_r)$ hechos en ellos por inversión. Así $G=\mathbb{Z}/2 \ltimes \mathbb{Z}/(r+1)$ e $G^{+} = \mathbb{Z}/(r+1)$ como se reivindica.

El grupo de Galois de $\phi_1$ primero vamos a explicar el bijection entre las raíces de $x^{r+1}+x=y$ e $\mathbb{P}^1(\FF_r)$. Considerar las raíces de la ecuación de $z^{r^2}+z^r=yz$. Claramente, forma una $\FF_{r}$ espacio vectorial bajo las operaciones ordinarias de la suma y la multiplicación; llamar a este espacio vectorial $V$. Se ha dimensión $2$. Para $z$ cualquier elemento distinto de cero de $V$, el elemento $x=z^{r-1}$ es una raíz de $x^{r+1} + x=y$. Por otra parte, si $z'$ es un escalar varios de $z$,, a continuación,$z^{r-1} = (z')^{r-1}$. Así que las raíces de $x^{r+1} + x=y$ etiqueta líneas en $V$.

Esta construcción es natural suficiente para probar que $G \subseteq PGL(V) \cong PGL_2(\FF_r)$. We now need to show $G^{+} = PGL_2$, and thus that $G=G^{+}$ así.

Aquí es la falta de detalle. Hay una muy similar resultado de la Serre, publicado como apéndice en un papel de Abhyankar, que la división de campo de la $z^{r+1} - wz+1$ es $PSL_2(\FF_r)$. Me siento como debería ser algo simple monomio cambio de variables que convierte a $(z,w)$ a $(x,y)$ y nos permite deducir nuestro resultado de de la Serre. (Tenga en cuenta que $PGL_2=PSL_2=SL_2$ en el carácter $2$.) Pero no dejo de no llegar a trabajar.

---

Así, ahora tenemos que contar el número de puntos fijos para el diedro y el $PGL_2$ acción.

El diedro de acción Desde $r+1$ es impar, cada reflexión que corrige un punto, explicando el $1$ para $m$ impar. Trivial rotaciones no tienen puntos fijos, explicando el $1/(r+1)$.

El $PGL_2$ acción utilizamos el isomorfismo $PGL_2 = PSL_2 = SL_2$.

Hay $r+1$ clases conjugacy en $SL_2$, es decir,

• La identidad.
• $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$. Esta clase tiene orden de $r^2-1$.
• $\begin{pmatrix} t & 0 \\ 0 & t^{-1} \end{pmatrix}$ para $t \neq 1$. Hay $r/2-1$ tal conjugacy clases, cada una de orden $r^2+r$.
• Las Matrices que se diagonalizable sobre $\FF_{r^2}$ con autovalores $(t, t^r)$, para $t$ un trivial $(r+1)$-st raíz de la unidad. Hay $r/2$ tal conjugacy clases, cada una de orden $r^2-r$.

Los tres primeros tienen puntos fijos, y la última no. Poniendo todo junto, la probabilidad de que un elemento en $PGL_2(\FF_r)$ tiene un punto fijo es $(r+2)/(2r+2)$.

Answer 3

El uso de Abedul/Swinnerton-Dyer en mi anterior y David Speyer respuesta es vaste overkill! En realidad, en el ejemplo de David, uno puede calcular exactamente el valor de los tamaños de los conjuntos. Sólo hago la pertinente caso de $m=1$. (Como el tamaño es exacto, no es necesario para la asintótica en consideración $m\to\infty$ sólo $r\to\infty$ es importante.)

Teorema. Conjunto $r=2^k$, $F=GF(r^2)$ y $\phi_0(x)=x^{r+1}$. A continuación, $\lvert\phi_a(F)\rvert=\frac{r(r+1)}{2}=\frac{r+1}{2r}\lvert F\rvert$ si $a\ne0$, e $\lvert\phi_0(F)\rvert=r$.

Prueba. La última afirmación es trivial, y en la anterior declaración es suficiente para asumir la $a=1$, para los si $b^r=a$,, a continuación,$\phi_a(bx)=b^{r+1}\phi_1(x)$. Deje $T(x)=x^r+x$ ser la huella mapa de $F$ a $GF(r)$. Tenga en cuenta que $x^{r+1}\in GF(r)$ para todos los $x\in F$. Por lo tanto si $\phi_1(x)=\phi_1(y)$ para$x,y\in F$,, a continuación,$\delta=y-x\in GF(r)$. Dado $x\in F$, podemos contar el número de $0\ne\delta\in GF(r)$ con $\phi_1(x)=\phi_1(x+\delta)$. Un corto de cálculo le da el equivalente de la relación de $\delta=T(x)+1$. La comparación de las dimensiones, podemos ver que $T$ es surjective como $GF(r)$ es el núcleo de $T$. Por lo tanto, hay exactamente $r$ elementos $x$ con $T(x)+1=0$. Por lo $\phi_1$ asume $(r^2-r)/2$ valores dos veces, y $r$ valores de una vez. De $(r^2-r)/2+r=r(r+1)/2$ la demanda de la siguiente manera.

Answer 4

Esta es una justificación de Peter Mueller adivinar. Escribir $n=|\mathbb{F}|$ y poner $m=\delta n$ donde $\delta>1-1/e$ es arbitrario. Deje $\phi_0$ ser una función aleatoria, elegido de manera uniforme entre todas las funciones de $\mathbb{F}\to\mathbb{F}$. Para cada una de las $a$, la función de $\phi_a$ es distribuido uniformemente. Deje $X$ ser el tamaño de la imagen de $\phi_0$. Deje $p=\Pr[X>m]$. Si $pn<1$, entonces no es una selección de $\phi_0$ tal la imagen de $\phi_a$ es en la mayoría de las $m$. El tamaño esperado de $X$ es $\bigl(1-1/e+o(1)\bigr)n$ ya que la probabilidad de que cualquier elemento en la imagen de $\phi$ es $1-(1-1/n)^n$. Furtermore, si pensamos en lanzar $n$ bolas en $n$ papeleras como una martingala de longitud $n$, Azuma la desigualdad implica que $\Pr\bigl[X-E[X]>C\sqrt{n\log n}\,\bigr]<n^{-C'}$. La elección de $C$ lo suficientemente grande, podemos obtener la conclusión deseada.