Assume the Carmichael's Totient Function Conjecture.

Consider the totient chain

$$n_0=\phi(3^2)\rightarrow n_1=\phi((\phi^{-1}(n_0))^2)\rightarrow n_2=\phi((\phi^{-1}(n_1))^2)\rightarrow\dots$$

where $\phi^{-1}(\phi(x))$ is the smallest second integer $y\neq x$ such that $\phi(x)=\phi(y)$.

(1) Does this chain grow doubly exponentially? (Shown below by Greg Martin)

(2) At every $i$ is there a prime $p_{i+1}$ with $p_{i+1}|n_{i+1}$ and $gcd(p_{i+1},\prod_{j=1}^in_j)=1$? What is the size of this prime?

What if $3^2$ is replaced by $a^k$ where $a,k+1\geq3$ and exponent in $\phi$ is $k$?


The suggested dynamic is more clearly written (using $\phi(m^2)=m\phi(m)$) as $$n_{j+1}= n_j\phi^{-1}(n_j) \gt (n_j)^2,$$

which clearly shows superexponential growth in $j$. Using $k$ in place of $2$ gets an inequality like $n_{j+1} \gt n_j^k$. Since it is unclear how $\phi^{-1}$ acts as a map, it should be tantamount to the Carmichael conjecture to ask for a primitive prime factor for each $n_j$.

Gerhard "Remember Jacobi Says 'Always Invert!'" Paseman, 2016.06.07.

  • $\begingroup$ Further, it is unclear that the sequence $n_j$ has infinitely many terms, so the growth may stop. Gerhard "But Let Us Be Hopeful" Paseman, 2016.06.07. $\endgroup$ Jun 7 '16 at 22:57

The answer to (1) is yes. Using the increasing lower bound $$ \phi(n) > \frac n{4\log\log n} \quad\text{for }n\ge7 $$ (which follows from known bounds), we get $$ n_{j+1} = \phi(\phi^{-1}(n_j)^2) > \frac{\phi^{-1}(n_j)^2}{4\log\log \phi^{-1}(n_j)^2} > \frac{n_j^2}{4\log\log n_j^2}, $$ which certainly implies $n_j \gg \exp((2-\varepsilon)^j)$ for any $\varepsilon>0$.

  • $\begingroup$ I think $2$ is also true. $\endgroup$
    – user76479
    Jun 7 '16 at 20:16
  • $\begingroup$ If $k\neq2$ should be $2^{2^{i\log k}}$? $\endgroup$
    – user76479
    Jun 7 '16 at 20:18
  • $\begingroup$ You should note for clarity that the $n$'s you are using are different from those in the post. Gerhard "I Would Use M's Instead" Paseman, 2016.06.07. $\endgroup$ Jun 7 '16 at 20:48
  • $\begingroup$ clarity shmarity, I just messed up! fixed now $\endgroup$ Jun 7 '16 at 21:43
  • $\begingroup$ Uh, I don't think so Greg. You have an extra exponent. However, phi(m^2)=m*phi(m), so you can still show super exponential growth independent of Carmichael's conjecture. Gerhard "Since We Are Being Frank" Paseman, 2016.06.07. $\endgroup$ Jun 7 '16 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy