31
$\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$
26
  • 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$ Jun 27, 2014 at 18:06
  • 5
    $\begingroup$ Is there any rationale for the size of the tower? Do you know the answer with fewer exponentiations? $\endgroup$ Jun 27, 2014 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, 2014 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, 2014 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$ Jul 6, 2014 at 15:08

3 Answers 3

21
$\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$
5
  • $\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$ Jul 4, 2014 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$ Jul 5, 2014 at 17:53
  • $\begingroup$ Here an estimates of $\endgroup$ Jul 8, 2014 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$ Jul 8, 2014 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$ Jul 8, 2014 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$
1
  • $\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$ Jul 6, 2014 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$
5
  • $\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, 2014 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$ Jul 4, 2014 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, 2014 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$ Jul 4, 2014 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$ Jul 5, 2014 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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