convergence in $\hat{\mathbb{Z}}$, modulo prime power

Question

The following problem appears in Lenstra's Galois Theory for Schemes (p 14, Ex 1.16).

Let $b\in\mathbb Z_{\ge0}$. Define the sequence $(a_n)_{n=0}^\infty$ by $a_0=b, a_{n+1}=2^{a_n}$. Prove that $(a_n)_{n=0}^\infty$ converges in $\hat{\mathbb Z}$, and that $a:=\lim_{n\to\infty}a_n$ is independent of $b$.

Then, write $a=\sum_{n=1}^\infty c_n n!$. Compute $c_n$ for $n=1,\cdots, 10$.

My first question is about finding $c_1, \cdots, c_{10}$. Noting the fact that $ \hat{\mathbb Z} \simeq\varprojlim\mathbb Z/n!\mathbb Z$, I have written down a bijection from $\varprojlim\mathbb Z/n!\mathbb Z$ onto the collection $\{\sum_{n=1}^\infty c_n n!: 0\leq c_n\leq n\}$ of formal series. According to the bijections I need to find out $a\text{ mod } n!$ for $n=2,\cdots, 11$. Thanks to the Chinese remainder theorem, the problem reduces to the computation of $a$ modulo prime-power factors in each $n!$. With the help of Euler's formula, $a\text{ mod }p$ can be computed for every odd prime $p$; and from the definition of $a$ we have $a\equiv 0\pmod{2^k}$. But I do not have any idea about calculating $a\text{ mod }p^k$. In particular, what I need are $a\text{ mod }3^2$, $a\text{ mod }3^4$ and $a\text{ mod }5^2$.

Then, we turn back to a more fundamental question: what does it mean by the sequence to converge? (Lenstra has not defined convergence in his notes.) Intuitively, $(a_n)_{n=1}^\infty$ converges if for every $M\in\mathbb N$, there is an $N\in\mathbb N$ such that for each $m\leq M$, the expression $a_n\text{ mod }m!$ is a constant for all $n\geq N$. Is this "definition" concise enough? And why do $a_n\text{ mod }{m!}$ become stable eventually? Finally, why the limit is independent of $b$?

Answer 1

Convergence follows from the following statement: if $n\geq N$, then $a_n\pmod{N}$ is independent of $b$. We can prove this by induction on $N$.

For $N=1$ the statement is trivial. Let $N>1$ and assume that the statement is true up to $N-1$. Let us look at $a_n\pmod{N}$. Writing $N=2^mN'$ where $N'$ is odd, it suffices to show that $a_n\pmod{2^m}$ and $a_n\pmod{N'}$ are independent of $b$, assuming of course $n\geq N$. The condition implies that $n\geq m$, whence $a_n\equiv 0\pmod{2^m}$. The condition also implies that $$n-1\geq N-1\geq\varphi(N)\geq\varphi(N'),$$ hence $a_{n-1}\pmod{\varphi(N')}$ is independent of $b$ by the induction hypothesis. By the Euler-Fermat theorem, this implies that $a_n\pmod{N'}$ is independent of $b$, and we are done.

Remark. The notion of convergence in $\hat{\mathbb{Z}}$ is given by the profinite topology of $\hat{\mathbb{Z}}$. That is, a sequence converges in $\hat{\mathbb{Z}}$ if and only if, for any $N$, the reduction of the sequence modulo $N$ converges in $\mathbb{Z}/N\mathbb{Z}$. The finite residue ring $\mathbb{Z}/N\mathbb{Z}$ is endowed with the discrete topology, so convergence really means stabilizing modulo $N$, for any given $N$.

Answer 2

There's a quite quick recursive algorithm to compute the stable value of $a_n$ modulo $k$.

If I do it for $a_{10}$ (i.e. $k=10!$) and put things upside down to be deductive, I get, successively (independently of the choice of $b$): $$n\ge 2\Rightarrow a_n\equiv 0 \;[2]$$ since the group $(\mathbf{Z}/3\mathbf{Z})^*$ has exponent 2 and 2 belongs to it, we deduce $$n\ge 2\Rightarrow 2^{a_n}\equiv 1\; [3]$$ $$n\ge 3\Rightarrow a_n\equiv 1 [3];\quad a_n\equiv 0\;[2]$$ $$n\ge 3\Rightarrow a_n\equiv 4 \;[6]$$ since the group $(\mathbf{Z}/9\mathbf{Z})^*$ has exponent 6 and 2 belongs to it, we deduce $$n\ge 3\Rightarrow 2^{a_n}\equiv 16 \;[9]$$ $$n\ge 4\Rightarrow a_n\equiv 16 [9];\quad 2^{a_n}\equiv 0\; [4]$$ $$n\ge 5\Rightarrow a_n\equiv 16\; [36]$$ since the group $(\mathbf{Z}/135\mathbf{Z})^*$ has exponent 36 (being isomorphic to $(\mathbf{Z}/27\mathbf{Z})^*\times (\mathbf{Z}/5\mathbf{Z})^*$ where the factors have cardinal 18 and 4, whose lcm is 36), we get $$n\ge 5\Rightarrow 2^{a_n}\equiv 2^{16} [135]=196\;[135]$$ $$n\ge 6\Rightarrow a_n\equiv 196 \;[135];\quad a_n\equiv 0\;[4]$$ $$n\ge 6\Rightarrow a_n\equiv 196 \;[4\times 135]$$ if $m=14175=3^4.5^2.7$, the group $(\mathbf{Z}/m\mathbf{Z})^*$ contains 2 and has exponent $4.135=540$, whence $$n\ge 6\Rightarrow 2^{a_n}\equiv 2^{196} \;[14175]= 1275136\; [14175],$$ where $1275136=2^8.17.293$; hence $$n\ge 7\Rightarrow a_n\equiv 1275136 \;[14175],\quad a_n\equiv 1275136 \;[2^8]$$ $$n\ge 7\Rightarrow a_n\equiv 1275136\; [10!]$$ since $10!=14175\times 2^8$.

Of course the algorithmic (deterministic) way to proceed goes reverse: if you want to compute the stable value of $a_n$ modulo a certain number $k$, write $k=k'k''$ with $k'$ power of 2 and $k''$ odd. In practice the case of $k'$ is rather trivial since the 2-valuation of $a_n$ grows very fastly. Then to know $a_n$ modulo $k''$, since $k''$ is odd, it is enough to know the exponent $m$ of the group $(\mathbf{Z}/k''\mathbf{Z})^*$, which is easy as soon as you can factor $k''$ into primes (write $k''$ as product of powers $k_i$ of distinct primes, and take the lcm of the orders of the $(\mathbf{Z}/k_i\mathbf{Z})^*$). Then you need to compute of the stable value of $a_n$ modulo $m$, and $m$ is usually much smaller than $k$ (above, for $k=10!$, 5 steps were needed). Thus if $a_n\equiv p_m$ for $n\ge C_m$ independently of $b$, you deduce that $a_n\equiv 2^{p_m}$ for all $n\ge C_m+1$ independently of $b$. Then compute $2^{p_m}$ modulo $k''$ (or modulo $k$) to make it reasonable, and deduce from the Chinese remainder theorem the value of $a_n$ modulo $k$ for $n\ge C_m+1$.

Added: the stable value of $a_n\,[k!]$ immediately entails the computation of $c_n$ for $n\le k-1$, namely $c_n=(a\,\mathrm{mod}\,(n+1)!-a\,\mathrm{mod}\,n!)/n!$. Thus $$(c_1,c_2,c_3,c_4,c_5,c_6,c_7,c_8,c_9)=(0,2,2,0,0,0,5,4,3).$$ To find $c_{10}$, you can run the same method to compute $a\pmod{11!}$.