Puntos fijos de$x\mapsto 2^{2^{2^{2^x}}} \mod p$

Question

Deje que$p$ sea primo. ¿Para cuántos elementos$x$ de$\{0,1,\dotsc,p-1\}$ puede ser el caso que$$2^{2^{2^{2^x}}} = x \mod p?$ $

En particular, ¿puede encontrar una prueba simple (o, mejor aún, varias pruebas simples) del hecho de que esto puede suceder solo para$< \epsilon\cdot p$ elements$x$ of$\{0,1,\dotsc,p-1\}$?

(Suponga, si es necesario, que$2$ es una raíz primitiva de$\mathbb{Z}/p\mathbb{Z}$).

Answer 1

El objetivo de esta respuesta es para dibujar una prueba del hecho de que existen en la mayoría de las $\epsilon p$ soluciones a $2^{2^{2^x}} = x \mod p$. La pregunta original, es decir, para mostrar la misma para $2^{2^{2^{2^x}}} = x \mod p$ -- permanece abierto por ahora.

Supongamos que hay $\gg p$ (es decir: $> \epsilon p$ para algunos fijos $\epsilon>0$) soluciones a $2^{2^{2^x}} = x \mod p$. Entonces no tendría que ser un almacén de constante $k$ tal que $x$ e $x+k$ son ambas soluciones para $\gg p$ valores de $x$. Para todos los $k$,

$$2^{2^{2^x}}+k = x+k = 2^{2^{2^{x+k}}} = 2^{2^{2^k 2^x}} = 2^{(2^{2^x})^{2^k}} \mod p.$$

Escrito $y$ para el entero en $\{0,1,...,p-2\}$ congruente a $2^{2^x} \mod p-1$, obtenemos que hay $\gg p$ elementos $y$ de % de $\{0,1,...p-2\}$ (o $\{0,1,...,p-1\}$) tal que

$$2^{y^{2^k}} = 2^y + k \mod p.\;\;\;\;\;\;\;\;\; (*)$$

Por el mismo razonamiento que antes, esto implica que, para cualquier $r$, hay un $(r+1)$-tupla de distintas constantes de $l_0=0,l_1, l_2,...,l_r$ tal que, por $\gg p$ elementos $y$ de % de$\{0,1,...p-1\}$, ( * ) es verdadera para cada $y+l_i$, $0\ll i \ll r$. Ahora, establezca $r = 2^k$. El $r+1$ polinomios

$$(y+l_i)^{r},\;\;\;\;\;\; 0\leq i\leq r$$

son linealmente independientes (porque esto es cierto sobre $\mathbb{Z}$ o $\mathbb{R}$: matriz de Vandermonde es no singular), pero, puesto que cada uno tiene r+1 coeficientes, ellos y cualquier otro polinomio en y, en particular, el polinomio y -- debe ser linealmente dependiente. Por lo tanto, hay (bounded constantes enteras) $c$ (no cero) y $c_i$, $0\leq i\leq r$, no todos cero, tales que $c y = \sum_{0\leq i\leq r} c_i (y+l_i)^{2^k} = 0$. Por lo tanto,

$$\prod_{0<=i<=r}. (2^{(y+l_i)^{2^k}})^{c_i} = 2^{\sum_{0<=i<=r} c_i (y+l_i)^{2^k}} = 2^{c, s} \mod p,$$

y así

$$\prod_{0<=i<=r} (2^y + k)^{c_i} = 2^{c y} \mod p.$$

Establecimiento $z = 2^y$, podemos ver, tenemos una ecuación

$$(z + k)^{\sum_{0<=i<=r} c_i} = z^c \mod p.\;\;\;\;\;\;\;\; (**)$$

supuestamente satisfecho por $\gg p$ elementos de $\{0,1,...p\}$. Vamos $C = \sum_{0<=i<=r} c_i$. Si $C\geq 0$, (**) es simplemente la ecuación

$$(z+k)^C = z^c \mod p;$$

si $C<0$, (**) es equivalente a la ecuación

$(z+k)^C z^c = 1 \mod p$.

En cualquier caso, tenemos una igualdad entre dos polinomios idénticos. Tal igualdad ($\mod p$) puede tener a lo más un acotado número de soluciones. Contradicción.

---

Se puede proporcionar una simple prueba de lo anterior? Se puede adaptar a $2^{2^{2^{2^x}}} = x \mod p$?

Answer 2

Su argumento para tres exponenciales se puede simplificar un poco por el uso de la multiplicación de la versión de van der Corput en lugar de la aditivo versión. Específicamente, si la ecuación $$2^{y^{2^k}} = 2^{y} + k \quad(\ast)$$ tiene muchas soluciones, a continuación, hay algunos delimitada $l>1$ tal, que hay muchos pares de soluciones de $y,ly$, y para cualquier par debemos tener $z=2^y$ problemas $$(z+k)^{l^{2^k}} = z^l + k,$$ que por supuesto tiene un acotado número de soluciones. (Equivalentemente, escriba la ecuación en términos de $y' = 2^x$ en lugar de $y=2^{2^x}$ y aplicar aditivo vdC.)

Si tenemos que ser más cuidadosa, a continuación, debemos definir a $f:\mathbf{Z}/p\mathbf{Z}\to\mathbf{Z}/p\mathbf{Z}$ por $f(x) = 2^{\bar{x}}$ donde $\bar{x}$ es el representante de la $x$ satisfacción $0\leq\bar{x}<p$. Realmente estamos interesados en soluciones a $fff(x)=x$, pero el uso de la "cocycle" de las relaciones $$f(x+y) = \begin{cases} f(x)f(y)&\text{or}\\f(x)f(y)/2,\end{cases}$$ y $$f(kx) = f(x)^k/c\text{ for some bounded }c=c_x,$$ se puede reducir el problema a contar soluciones a un acotado número de ecuaciones como $(\ast)$ a que el mismo argumento se aplica. (Estoy seguro de que usted, Helfgott, ya había algo parecido a esto en mente, pero otros quizás se ha preguntado cómo las discontinuidades pueden ser tratados.)

La ecuación de $ffff(x)=x$ es ciertamente desalentador. El análogo de $(\ast)$ aquí está, para $k=1$, $$2^{2^{y^2}} = 2^{2^y} + 1.\quad(\ast\ast)$$ Obviamente $y$ e $-y$ son nunca las dos soluciones de esta ecuación, pero esto no prueba una $1-\epsilon$ obligado porque realmente nos preocupamos por las soluciones de $y$ a $ff(y^2)=ff(y)+1$ o $ff(y^2/2)=ff(y)+1$, y podríamos tener $-y$ una solución a uno siempre $y$ es una solución para el otro. No veo cómo hacer ningún progreso real.

[Comentario de antes de comprender la intención de la pregunta, y yo pensé que nos estaban contando enteros $x$ en el rango $0\leq x<p$ cuyo cuádruple exponencial, evaluado en $\mathbf{Z}$, es equivalente a $x\pmod{p}$: Por medicamentos genéricos $p$, el número de $p-1$ va a tener muchos factores primos, lo que implica que $(\mathbf{Z}/(p-1)\mathbf{Z})^\times$ le surject en $(\mathbf{Z}/2\mathbf{Z})^m$ para algunos un gran $m$. Por lo tanto, no muchos de los elementos de $(\mathbf{Z}/(p-1)\mathbf{Z})^\times$ son de la forma $y^2$, por lo que no muchos de los elementos $x$ de % de $\mathbf{Z}/p\mathbf{Z}$ son incluso de la forma $2^{y^2}$, mucho menos de la forma $2^{2^{2^z}}$ para algunos entero $z \equiv x\pmod{p}$.]

Answer 3

(Nota posterior: Este argumento sólo funciona al $2$ ha multiplicativo orden de $p-1$ (mod $p$), pero puede dar una idea que otros para el caso general).

Esto no es realmente una respuesta, y yo estoy en dos mentes acerca de la publicación, pero ya que nadie más aparte de la OP ha contestado, aquí va: suponiendo que $2$ genera $A = (\mathbb{Z}/p\mathbb{Z})^{\times}$, el mapa de $f : x \to 2^{x}$ es un bijection de $A$ a sí mismo (en el que obviamente $2^{x}$ es leer (mod $p$) ). La pregunta parece cantidad a pedir que $f$ tiene menos de $\varepsilon p$ ciclos cortos cuando está escrito como una permutación ( donde el significado de corto depende de la altura de la torre de afirmar exponenciales que usted elija).

En el intento de solucionar esto, me resulta difícil saber cómo generalizar la cuestión general de la finitos grupo Abelian $G.$ Si tenemos una permutación arbitraria $f$ de los elementos de $G$, no hay ninguna razón a priori para esperar $f$ a que tienen pocos ciclos cortos, (aunque el trabajo de probabilísticamente, una permutación aleatoria es relativamente raro tiene ciclos cortos)por lo que la interacción entre el aditivo y multiplicativo estructura de $\mathbb{Z}/p\mathbb{Z}$ debe estar jugando un papel. Además, llega un punto en el que $f^{n}$ va a tener un montón de puntos fijos, por ejemplo, cuando se $n$ es el orden de la permutación $f$.

Entonces, ¿cuáles son las características distintivas del mapa de $f$? Tenga en cuenta que $f$ tiene la propiedad de que $f(x)f(-x) = 2.$ Más en general, $f(x+y) = f(x)f(y)$ si $0 < x \leq y < x+y < p$ e $2f(x+y) = f(x)f(y)$ al $0 < x \leq y < p < x+y$. Nota en particular de que $x^{p-1}-1$ es un factor de $f(x)f(-x) -2.$

La pregunta sugiere otra: ¿cuál es el menor valor de $m$ tal que $f$ tiene más de $\varepsilon p$ ciclos de longitud $m?$ Una forma de ataque que sería mostrar la existencia de un ciclo de casi la máxima longitud posible. No sé si siempre hay un ciclo.