Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
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

2 Answers 2

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

share|improve this answer

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 3 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\,\mathrm{mod}\,(11)!$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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