32
$\begingroup$

Let $p$ be a prime. For how many elements $x$ of $\{0,1,\dotsc,p-1\}$ can it be the case that $$2^{2^{2^{2^x}}} = x \mod p?$$

In particular, can you find a simple proof (or, even better, several simple proofs!) of the fact that this can happen only for $< \epsilon\cdot p$ elements $x$ of $\{0,1,\dotsc,p-1\}$?

(Assume, if needed, that $2$ is a primitive root of $\mathbb{Z}/p\mathbb{Z}$.)

$\endgroup$
  • 7
    $\begingroup$ Do you mean to assume that $0\leq x<p$? Taking $x$ to $2^x$ does not give a well-defined function mod $p$. $\endgroup$ – Eric Wofsey Jun 27 '14 at 18:06
  • 4
    $\begingroup$ Is there any rationale for the size of the tower? Do you know the answer with fewer exponentiations? $\endgroup$ – Felipe Voloch Jun 27 '14 at 18:16
  • 3
    $\begingroup$ In fact, for one exponent, one can use quantitate Roth to improve the bound to p/\log\log p $\endgroup$ – Alvin Jun 29 '14 at 20:45
  • 2
    $\begingroup$ Indeed, for one exponent the bound may be improved up to $O(\sqrt{n})$, since we can have no two pairs of fixed points with the same difference. $\endgroup$ – Rodrigo Jul 4 '14 at 21:13
  • 2
    $\begingroup$ This question is related to the question whether Higman's group $G= \langle a,b,c,d \mid ab^2=ba, bc^2=ca, cd^2=dc, da^2=ad \rangle$ (which is known not to have any finite quotients) is sofic. $\endgroup$ – Andreas Thom Jul 6 '14 at 15:08
20
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Note that the argument above is in some sense "local", in that relies entirely on comparisons between the values of functions at $x$ and at $x+k$, where $k$ is bounded by a constant. Something tells me that this will not be so straightforward for the quadruple power. $\endgroup$ – H A Helfgott Jul 4 '14 at 20:43
  • $\begingroup$ The term $2^y + k$ in the displayed equation preceding (**) should be $2^y 2^{l_i} + k$, but I don't think that affects at all the validity of this nice proof. One thing I was worried about was the possibility of $2$ having small order modulo $p-1$, so that if you take $\gg p$ values $x$ and pass to $y= 2^{2^x}$ you don't necessarily have $\gg p$ values $y$. But in fact if $2$ doesn't have order $\gg p$ modulo $p-1$ then you're immediately done because $2^{2^{2^x}}$ would have small image. Similarly the assumption that $2$ is primitive mod $p$ is superfluous. $\endgroup$ – Sean Eberhard Jul 5 '14 at 17:53
  • $\begingroup$ Here an estimates of $\endgroup$ – Lev Glebsky Jul 8 '14 at 6:45
  • $\begingroup$ Here are an estimates (From above and, I think, very imprecise)of number of solutions of $q^{x^{x^x}}=x \mod p$ based on similar constructions. There are some annoying details due to $x+k (\mod p)= x+k (\mod p-1)$ or $x+k(\mod p-1) +1$. So, $2^{x+k}= 2^x2^k$ or $22^x2^k\mod p$. I don't think that there is an easy generalization for points of period 4. I think that the proof goes through due to the group $\langle a,b,w\;|\;b^{-1}ab=b^2,w^{-1}aw=b, w^3=1\rangle$ is finite. (We may define "almost action" of this group, with $xa=x+1$, $xb=2x$, $xw=2^x\mod p$) $\endgroup$ – Lev Glebsky Jul 8 '14 at 7:12
  • $\begingroup$ That's nice - yes, the question we are discussing is really about the cycles of $f_g(u)$, in the paper's notation. It looks like my (self-)answer improves on Theorem 6. Unfortunately, the paper contains no bounds on what it calls $N_g(4)$ (which is what we are trying to bound non-trivially here). $\endgroup$ – H A Helfgott Jul 8 '14 at 7:14
6
$\begingroup$

Your argument for three exponentials can be simplified a bit by using the multiplicative version of van der Corput instead of the additive version. Specifically, if your equation $$2^{y^{2^k}} = 2^{y} + k \quad(\ast)$$ has many solutions then there is some bounded $l>1$ such that there are many pairs of solutions $y,ly$, and for any such pair we must have $z=2^y$ solving $$(z+k)^{l^{2^k}} = z^l + k,$$ which of course has a bounded number of solutions. (Equivalently, write the equation in terms of $y' = 2^x$ instead of $y=2^{2^x}$ and apply additive vdC.)

If we're being more careful then we should define $f:\mathbf{Z}/p\mathbf{Z}\to\mathbf{Z}/p\mathbf{Z}$ by $f(x) = 2^{\bar{x}}$, where $\bar{x}$ is the representative of $x$ satisfying $0\leq\bar{x}<p$. We're really interested in solutions to $fff(x)=x$, but using the "cocycle" relations $$f(x+y) = \begin{cases} f(x)f(y)&\text{or}\\f(x)f(y)/2,\end{cases}$$ and $$f(kx) = f(x)^k/c\text{ for some bounded }c=c_x,$$ one can reduce the problem to counting solutions to a bounded number of equations like $(\ast)$ to which the same argument applies. (I'm sure you, Helfgott, already had something like this in mind, but others may have wondered how the discontinuities could be handled.)

The equation $ffff(x)=x$ is certainly daunting. The analogue of $(\ast)$ here is, for $k=1$, $$2^{2^{y^2}} = 2^{2^y} + 1.\quad(\ast\ast)$$ Obviously $y$ and $-y$ are never both solutions to this equation, but this does not prove a $1-\epsilon$ bound because really we care about solutions $y$ to either $ff(y^2)=ff(y)+1$ or $ff(y^2/2)=ff(y)+1$, and we could well have $-y$ a solution to one whenever $y$ is a solution to the other. I don't see how to make any real progress.

[Comment from before I understood the intended question, and I thought we were counting integers $x$ in the range $0\leq x<p$ whose quadruple exponential, evaluated in $\mathbf{Z}$, is equivalent to $x\pmod{p}$: For generic $p$, the number $p-1$ will have many prime factors, which implies that $(\mathbf{Z}/(p-1)\mathbf{Z})^\times$ will surject onto $(\mathbf{Z}/2\mathbf{Z})^m$ for some large $m$. Thus not many elements of $(\mathbf{Z}/(p-1)\mathbf{Z})^\times$ are of the form $y^2$, so not many elements $x$ of $\mathbf{Z}/p\mathbf{Z}$ are even of the form $2^{y^2}$, let alone of the form $2^{2^{2^z}}$ for some integer $z \equiv x\pmod{p}$.]

$\endgroup$
  • $\begingroup$ Well, let us stay away from $p$ that give such an easy negative answer. The interpretation some have given above (making $f$ into a bijection) is closer to what I had in mind. $\endgroup$ – H A Helfgott Jul 6 '14 at 12:17
5
+50
$\begingroup$

(Later note: This argument only works when $2$ has multiplicative order $p-1$ (mod $p$), but may give some insight to others for the general case).

This isn't really an answer, and I'm in two minds about posting it, but since no one else apart from the OP has answered, here goes: assuming that $2$ generates $A = (\mathbb{Z}/p\mathbb{Z})^{\times}$, the map $f : x \to 2^{x}$ is a bijection from $A$ to itself (where obviously $2^{x}$ is read (mod $p$) ). The question seems to amount to asking that $f$ has fewer than $\varepsilon p$ short cycles when written as a permutation ( where the meaning of short depends on the height of the tower of iterated exponentials you choose).

In trying to address this, I find it difficult to know how to generalise the question to a general finite Abelian group $G.$ If we have an arbitrary permutation $f$ of the elements of $G$, there is no a priori reason to expect $f$ to have few short cycles, (although working probabilistically, a random permutation is relatively unlikely to have short cycles)so the interaction between the additive and multiplicative structure of $\mathbb{Z}/p\mathbb{Z}$ must be playing a role. Furthermore, there does come a point at which $f^{n}$ will have plenty of fixed points, for example when $n$ is the order of the permutation $f$.

So what are the distinguishing features of the map $f$? Note that $f$ has the property that $f(x)f(-x) = 2.$ More generally, we have $f(x+y) = f(x)f(y)$ if $0 < x \leq y < x+y < p$ and $2f(x+y) = f(x)f(y)$ when $0 < x \leq y < p < x+y$. Note in particular that $x^{p-1}-1$ is a factor of $f(x)f(-x) -2.$

The question suggests another: what is the smallest value of $m$ such that $f$ has more than $\varepsilon p$ cycles of length $m?$ One way to attack that would be to show the existence of a cycle of almost maximal possible length. I don't know if there always is such a cycle.

$\endgroup$
  • $\begingroup$ I think the question (if interpreted exactly as stated) can't be solved by studying the map $f:x \rightarrow 2^x\, mod\, p$, since $x$ mod $p$ doesn't define $2^x$ mod $p$. Trying such approach would require us to study integers modulo $p\phi(p)\phi(\phi(p))$...etc. However this approach would probably give us some trouble in working with integers specifically in the interval $(0,p)$. $\endgroup$ – Rodrigo Jul 4 '14 at 18:01
  • $\begingroup$ You have to adopt the convention that you read $x$ as being between $1$ and $p-1$ when you calculate $2^{x},$ then it becomes well defined. The OP already stated that in comments below his question. that is why you get $f(x)f(-x) =2$, because you have to interpret $f(-x)$ as $2^{p-x}$ for $0 < x < p.$ $\endgroup$ – Geoff Robinson Jul 4 '14 at 18:08
  • 1
    $\begingroup$ My point is that, as defined, the cycles of length $3$ of $f$, for instance, don't say anything about the fixed points of $2^{2^{2^x}}$. In order to iterate $f$, we need to reduce the exponent modulo $p-1$, not $p$, and so on. $\endgroup$ – Rodrigo Jul 4 '14 at 18:16
  • $\begingroup$ Interpret the question as loosely or as strictly as you wish, as long as it helps to make it possible to say something meaningful. Want to define $f(x)=2^x$ for $x\in {0,1,\dotsc,p-2}$, $f(x) = 0$ for $x=p-1$, and $f(x) = f(\overline{x})$ elsewhere, where $\overline{x}$ is the element of $\{0,1,\dotsc,p-1\}$ congruent to $x$ modulo $p$? Be my guest. $\endgroup$ – H A Helfgott Jul 4 '14 at 20:40
  • 1
    $\begingroup$ Once you have agreed a convention that makes $f$ a bijection, it makes sense to iterate $f$ as often as you like. If $2$ generates the multiplicative group (mod $p$), then $x \to 2^{x}$ is a well defined bijection from $\{1,2, \ldots, p-1 \}$ to itself. $\endgroup$ – Geoff Robinson Jul 5 '14 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.