I would like to check if this limit :$$\liminf \frac{\sigma_{k}(({2}^{m-1})({2^m-1}))}{\phi_{k}(({2}^{m-1})({2^m-1}))}$$ finite for every $k$?

where :$\phi_{k}$ is iterating Euler - totient function and $\sigma_{k}$ is iterating sum divisor .

note(01) : Here :$\sigma_{k}(n)=\sigma(\sigma(\sigma(\dots n)))$ is the $k$-th iterate of the sum of divisors function. and :$\phi_{k}(n)=\phi(\phi(\phi(\dots n)))$ is the $k$-th iterate of the euler totiont function.

Note(02) :I tried to evaluate the recent limit I accrossed this problem :can I write :$${\phi_{k}(({2}^{m-1})({2^m-1}))}=({2}^{m-1-k})\phi_{k}({2^m-1})$$ ? I know only that is true iff gcd $({2}^{m-1},{2^m-1})=1$ for $m\geq 1$ and $k=1$ ?

Thank you for any help

  • 2
    $\begingroup$ For all $m\geq 1$ we have $gcd(2^{m-1},2^m-1)=1$. $\endgroup$ – Meysam Ghahramani Dec 29 '15 at 11:39
  • $\begingroup$ and it is the same for what i wrote but what about more iteration of k ? $\endgroup$ – zeraoulia rafik Dec 29 '15 at 11:40
  • $\begingroup$ The "proof theory" tag should be reserved to (certain) questions in mathematical logic, namely those which concern formal proofs and their theory. $\endgroup$ – GH from MO Dec 29 '15 at 16:36
  • $\begingroup$ Personally, I think this question is beyond current technology. $\endgroup$ – GH from MO Dec 29 '15 at 18:37
  • $\begingroup$ in note(02) , just i would like to write my limit in other form for using shinzel and sieve conjecture using simplification which montioned in note 2 " using property of multiplicative function and i asked also in this note if it is true for all m, and k ? $\endgroup$ – zeraoulia rafik Dec 29 '15 at 22:04

The problem is probably beyond current knowledge. It is well possible that $\liminf\omega(2^m-1)=\infty$, where $\omega(n)$ denotes the number of distinct prime divisors of $n$. If this was the case, one could expect that for each small prime $p$ there is some $m_0$, such that for $m>m_0$ we have that $2^m-1$ has a prime divisor $q\equiv 1\pmod{p}$. If this was the case, then $\frac{\varphi(\varphi(2^m-1))}{2^m-1}\rightarrow 0$, thus for $k=2$ the $\liminf$ in question would be infinite.

Excluding these possibilities is probably not much easier then proving that there are infinitely many Mersenne primes, which is certainly difficult.


For $k=1$ and $m$ a not too small prime, there are fewer than $f=m/(\log_2 m)$ prime factors of $2^m-1$, all of them at least as large as $m$, and your ratio is $O((m/(m-2))^f)$, which is bounded, so the answer is yes the lim inf is finite for $k=1$.

For $k \gt 1$ fixed, we have no nice estimates on the number or size of distinct prime factors of either numerator or denominator of your fraction, and at present we don't have a good understanding of the dynamics of the $\sigma$ or the $\phi$ functions to give a good guess. I am looking at a concept with the working title "factoral abundance" to address questions like this. Getting some help with the estimates raised in How to get a good upper bound on $\sum_{1 \lt d, d|n} \phi(d)/\log d$? would push us nearer to such answers.

Gerhard "And Help On Other Questions" Paseman, 2015.12.29

  • $\begingroup$ A good start would be analyzing the numerics for k=1: what is the shape of the point cloud for (m, ratio(m)) for the first million m? It is not clear to me that lim sup of the ratio is unbounded for arbitrary m. Similarly for k=2 and 3. Gerhard "See If WolframAlpha Eats It" Paseman, 2015.12.29 $\endgroup$ – Gerhard Paseman Dec 29 '15 at 21:30
  • $\begingroup$ @Gerahrd paseman, my point of starting to proof this problem in "note (02) in the question $\endgroup$ – zeraoulia rafik Dec 29 '15 at 21:43
  • $\begingroup$ I think the equation in that note fails for many values of m and k. Can you tell for k=2 or 3 some m for which it holds? Gerhard "Really, Try Some Small Examples" Paseman, 2015.12.29 $\endgroup$ – Gerhard Paseman Dec 29 '15 at 21:48
  • $\begingroup$ I don't know , it's seems to poste a new question here to know for which values it hold $\endgroup$ – zeraoulia rafik Dec 30 '15 at 16:25

Your Answer

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

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