The aim of this answer is to sketch a proof of the fact that there are at most $\epsilon p$ solutions to $2^{2^{2^x}} = x \mod p$. The original question -- namely, to show the same for $2^{2^{2^{2^x}}} = x \mod p$ -- remains open for now.

Suppose there were $\gg p$ (meaning: $> \epsilon p$ for some fixed $\epsilon>0$)
solutions to $2^{2^{2^x}} = x \mod p$. Then there would have to be a bounded
constant $k$ such that $x$ and $x+k$ are both solutions for $\gg p$ values of $x$.
For all such $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.$$

Writing $y$ for the integer in $\{0,1,...,p-2\}$ congruent to $2^{2^x} \mod p-1$,
we obtain that there are $\gg p$ elements $y$ of $\{0,1,...p-2\}$ (or $\{0,1,...,p-1\}$)
such that

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

By the same reasoning as before, this implies that, for any $r$,
there is an $(r+1)$-tuple of distinct constants $l_0=0,l_1, l_2,...,l_r$ such
that, for $\gg p$ elements $y$ of $\{0,1,...p-1\}$, (*) is true for every $y+l_i$,
$0\ll i \ll r$. Now, set $r = 2^k$. The $r+1$ polynomials

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

are linearly independent (because this is true over $\mathbb{Z}$ or $\mathbb{R}$: Vandermonde matrix is non-singular), but, since they each have r+1 coefficients,
they and any other polynomial in y -- in particular, the polynomial y --
must be linearly dependent. Hence, there are (bounded integer constants)
$c$ (not zero) and $c_i$, $0\leq i\leq r$, not all of them zero, such that
$c y = \sum_{0\leq i\leq r} c_i (y+l_i)^{2^k} = 0$. Therefore,

$$\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 y} \mod p,$$

and so

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

Setting $z = 2^y$, we see we have an equation

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

supposedly satisfied by $\gg p$ elements of $\{0,1,...p\}$. Let
$C = \sum_{0<=i<=r} c_i$. If $C\geq 0$, (**) is just the equation

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

if $C<0$, (**) is equivalent to the equation

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

In either case, we have an equality between two identical polynomials.
Such an equality ($\mod p$) can have at most a bounded number of solutions.
Contradiction.

Can you provide a simpler proof of the above? Can you adapt it to $2^{2^{2^{2^x}}} = x \mod p$?

21more comments