2
$\begingroup$

So this one's been bothering me for a while and I can't figure it out

Define $^kb$ as $b^{b^{b^{...}}}$ as the power tower of $b$ of height $k$

What I want to do is understand the behavior of $\lim_{k \to \infty} {}^kb$ mod $n$, ideally to find a closed form.

Obviously for integers $b \geq 2$, $\lim_{k \to \infty} {}^kb = \infty$, but there's no reason why $^kb$ can't converge mod $n$. In fact, if $b$ is relatively prime to $n$, $\lambda(n)$, $\lambda(\lambda(n))$, etc. then it definitely will converge because eventually some iteration of $\lambda^i(n) = 1$ and so $b \equiv_{\lambda^i(n)} 0$. Then, for all $k \geq i$, ${}^kb = {}^ib$. ($\lambda(n)$ here referes to carmichael's totient function, and $\lambda^i(n)$ refers to the iteration of the function $i$ times: $\lambda(\lambda(\dots\lambda(n)))$)

I'm pretty sure that it converges for arbitrary $b$, $n$ but I haven't been able to prove that

Trying some small cases seems surprisingly unhelpful:

$2^{2^{2^{...}}} \equiv_2 0$

$2^{2^{2^{...}}} \equiv_3 1$

$2^{2^{2^{...}}} \equiv_4 0$

$2^{2^{2^{...}}} \equiv_5 1$

$2^{2^{2^{...}}} \equiv_6 4$

$2^{2^{2^{...}}} \equiv_7 2$

$2^{2^{2^{...}}} \equiv_8 0$

$2^{2^{2^{...}}} \equiv_9 7$

$\endgroup$
2
  • 2
    $\begingroup$ This is covered well in this article. (I've referenced it in this answer, but you're asking for more.) $\endgroup$
    – metamorphy
    Apr 13, 2021 at 5:19
  • $\begingroup$ @metamorphy oh, cool! looks like my $\omega$ and $\phi$ is Shapiro's $\omicron$ and $\rho$, respectively. nice to know I was on a shared path! :) $\endgroup$
    – thorimur
    Apr 13, 2021 at 5:56

1 Answer 1

5
$\begingroup$

Very interesting question! Here's at least a proof that it converges for any $b, n$, though the question of characterizing these numbers is unanswered here.

First, some definitions. Consider $b\in\mathbb{N}$. Define $\omega(b,n),\phi(b,n)$ to be the least nonnegative integers such that $b^{\omega(b,n)}b^{\phi(b,n)}\equiv_nb^{\phi(b,n)}$, with $\omega(b,n)>0$.

To see what these numbers are intuitively, consider the sequence $(b^0,b^1,b^2,\cdots)$; eventually this will start repeating. $\omega(b,n)$ is the period of that repetition, and $\phi(b,n)$ is the length until we enter that period for the first time. For example, with $n=6$, $b=2$, we have $(1,2,4,2,4,\cdots)$. $\phi(b,n)=1$, and $\omega(b,n)=2$. See the end of the post for a graphical depiction.

Define the function $\text{mod}:\mathbb{Z}\times\mathbb{Z}\times\mathbb{Z}\to \mathbb{Z}$ to take in a number, a modulus, and an offset, Mathematica-style. $\text{mod}(x,n,d)$ is defined to be the least $a\in \mathbb{Z}$ such that $a \equiv_n x$ and $a\geq d$. Note for later that if $x\equiv_n y$, then $\text{mod}(x,n,d)=\text{mod}(y,n,d)$. Also define $\text{mod}(x,n):=\text{mod}(x,n,0)$, and note that $\text{mod}(\text{mod}(x,n),n,d)=\text{mod}(x,n,d)$.

Define $\sigma(b,n)\in\mathbb{Z}$ to be the value we're looking for, if it exists: the least nonnegative integer $s$ such that for some $k_0$, we have that for all $k\geq 0$, $\ ^kb\equiv_ns $.

Let me also introduce the notation $\text{exp}_b(x):=b^x$ for clarity.


Now, note that for $x\geq\phi(b,n)$, we have $\text{exp}_b(x)\equiv_n \text{exp}_b(\text{mod}(x, \omega(b,n), \phi(b,n))$. (To see this, simply expand $x$ as $x=\text{mod}(x, \omega(b,n), \phi(b,n)) + k\omega(b,n)$ for some $k$, and note that we may write $\text{mod}(x, \omega(b,n), \phi(b,n))=\phi(b,n)+x_0$ where $x_0\geq 0$. Use the definition of $\omega$ and $\phi$ to get rid of $k\omega(b,n)$, and recombine.)

Note that for all $b,n$ with $b>1$, there is some height $k$ such that $^kb\geq \phi(b,n)$. Hence we may make use of the note above.

In particular, if and only if it exists, we must have that for some sufficiently high $k_0$, $^kb\equiv_n \sigma(b,n)$ for all $k\geq k_0$. Therefore $$\sigma(b,n)\equiv_n \text{exp}_b(\ ^{k-1}b)\equiv_n\text{exp}_b(\text{mod}(\ ^{k-1}b,\omega(b,n),\phi(b,n)))$$

Induction step (we'll get to the base case later): suppose that $\sigma(b,m)$ exists for all $m<n$. Then using the fact that $$\text{mod}(\ ^{k-1}b,\omega(b,n),\phi(b,n))=\text{mod}(\text{mod}(\ ^{k-1}b,\omega(b,n)),\omega(b,n),\phi(b,n))$$

We may choose $k$ sufficiently high such that $\text{mod}(\ ^{k-1}b,\omega(b,n))\equiv_n \sigma(b,\omega(b,n))$. Therefore $\text{mod}(\ ^{k-1}b,\omega(b,n),\phi(b,n)) = \text{mod}(\sigma(b,\omega(b,n)),\omega(b,n),\phi(b,n))$.

Note that we always have $\omega(b,n)\leq n-1$, since $b$ can never be both a multiplicative generator of the group and a zero divisor, so the periodic orbit is always missing either $1$ or $0$.

Then, we can use the induction step, and conclude that $\sigma(b,\omega(b,n))$ exists, and that therefore $\sigma(b,n)$ does.

(It is easy to check that anything satisfying the equation for $\sigma(b,n)$ above must be the limit of $\ ^kb$ mod $n$, just by unpacking and repacking the definition of $\sigma$.)

The base case, that $\sigma(b,1)$ exists for any $b>1$, is immediate: anything mod $1$ is $0$, and so all sequences are constant and equal to 0!


Here's some Mathematica code to calculate these numbers. LogRemainder[b, n] is what I've called the function that returns $\omega$ and $\phi$ in a 2-element list, {ω[b,n], φ[b,n]}. It calls $\sigma$ stablepower. It includes a brute-force check for the non-overflow cases.

Still totally mysterious to me, though, is any closed form or deep insight on $\sigma(b,n)$; that would be really interesting to see.

(* Brute force: *)

brute[nmax_, bmax_] :=
  Table[
    Mod[FixedPoint[b^# &, 1, SameTest -> (Mod[#1, n] == Mod[#2, n] &)], n],
    {n, 2, nmax}, {b, 2, bmax}]

(* By the above: *)

(* Note that the following definitions are memoized for faster computation,
   hence the f[x_] := (f[x] = ...) idiom. *)

LogRemainder[a_, n_] := (LogRemainder[a, n] = LogRemainder0[a, n, Mod[1, n]])

LogRemainder0[a_, n_, acc0_, acc___] := 
 If[MemberQ[{acc}, acc0], {First@FirstPosition[{acc}, acc0, {1}], 
    Length[{acc}] - First@FirstPosition[{acc}, acc0, {1}]}, 
    LogRemainder0[a, n, Mod[a*acc0, n], acc0, acc]]

stablepower[b_, 1] := 0

stablepower[b_, n_] := (stablepower[b, n] = 
   Mod[b^(Mod[stablepower[b, #1], #1, #2] & @@ LogRemainder[b, n]), n])

(* Check up to 10: *)

Table[stablepower[b, n], {n, 2, 10}, {b, 2, 8}] == brute[10, 8]

(* Out: True *)

(* Print up to 20: *)

Table[stablepower[b, n], {n, 2, 20}, {b, 2, 20}] // Grid

(* Out (note your calculations appearing along the left column,
   and the diagonal of 0s when b == n): 

                                                                    
0   1   0   1   0   1   0   1   0   1   0   1   0   1   0   1   0   1   0
1   0   1   2   0   1   1   0   1   2   0   1   1   0   1   2   0   1   1
0   3   0   1   0   3   0   1   0   3   0   1   0   3   0   1   0   3   0
1   2   1   0   1   3   1   4   0   1   1   3   1   0   1   2   1   4   0
4   3   4   5   0   1   4   3   4   5   0   1   4   3   4   5   0   1   4
2   6   4   3   1   0   1   1   4   2   1   6   0   1   2   5   1   5   1
0   3   0   5   0   7   0   1   0   3   0   5   0   7   0   1   0   3   0
7   0   4   2   0   7   1   0   1   5   0   4   4   0   7   8   0   1   7
6   7   6   5   6   3   6   9   0   1   6   3   6   5   6   7   6   9   0
9   9   4   1   5   2   3   5   1   0   1   8   3   1   5   8   4   7   1
4   3   4   5   0   7   4   9   4   11  0   1   4   3   4   5   0   7   4
3   1   9   5   1   6   1   1   3   6   1   0   1   8   3   10  1   7   9
2   13  4   3   8   7   8   1   4   9   8   13  0   1   2   5   8   5   8
1   12  1   5   6   13  1   9   10  11  6   13  1   0   1   2   6   4   10
0   11  0   5   0   7   0   9   0   3   0   13  0   15  0   1   0   11  0
1   7   1   14  1   12  1   9   1   5   1   13  1   8   1   0   1   8   1
16  9   4   11  0   7   10  9   10  5   0   13  4   9   16  17  0   1   16
5   18  9   6   1   7   11  1   9   7   1   15  17  18  17  9   1   0   1
16  7   16  5   16  3   16  9   0   11  16  13  16  15  16  17  16  19  0

*)

Just for fun, here's a depiction of the multiplicative action of $2$ in $\mathbb{Z}\ /\ 20\mathbb{Z}$. Each arrow denotes multiplication by $2$, and here we have $\omega(2,20)=4,\phi(2,20)=2$. The sequence $(2^0,2^1,2^2,\cdots)$ is highlighted; one can see the $1,2$ entry into the cycle, and then the $4,8,16,12$ cycle. The code to produce it is below.

The graph described above.

Maction[a_, n_] := Table[i -> Mod[i*a, n], {i, 0, n - 1}]

Orbit[b_, n_] := NestList[Mod[2*#, n] &, 1, Total[LogRemainder[b, n]]]

GraphOrbit[b_, n_] := 
 Graph[Maction[b, n], VertexLabels -> Automatic, 
  GraphLayout -> {"PackingLayout" -> "NestedGrid"}, 
  GraphHighlight -> Most[Orbit[b, n]]~Join~BlockMap[Rule @@ # &, Orbit[b, n], 2, 1]]

GraphOrbit[2, 20]
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .