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

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

• The sequence $(a_n)$ in $\hat{\mathbf{Z}}$ converges iff for every $k\ge 1$ its image modulo $k$ is eventually constant (i.e., $k$ divides $a_n-a_{n+1}$ for every $n\ge m_k$ for some sequence $m_k$). – YCor Dec 26 '13 at 19:01

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

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!}$$.