P. Erdős and Leon Alaoglu proved in [1] that for every $\epsilon > 0$ the inequality $\phi(\sigma(n)) < \epsilon \cdot n$ holds for every $n \in \mathbb{N}$, except for a set of density $0$.

C. L. mentioned in [2] that as a consequence of the previous result one can ascertain that $\displaystyle \lim_{n \to \infty} \frac{\phi(\sigma(n)) }{n} = 0.$

Does anybody know how it is that C. L. proceeded in order to arrive at such a conclusion?

Clearly enough, the fact that an inequality of the type $a_{n} < \epsilon \cdot n$ holds for every $\epsilon > 0$ and a subset of $\mathbb{N}$ of density $1$ does not imply, in general, that the sequence $\displaystyle \frac{a_{n}}{n}$ goes to $0$ as $n \to \infty$.

Hope you guys can shed some light on this inquiry of mine. Let me thank you in advance for your continued support.


[1] L. Alaoglu, P. Erdős: A conjecture in elementary number theory, Bull. Amer. Math. Soc. 50 (1944), 881-882.

[2] Mathematical Reflections, Solutions Dept, Issue #3, 2009, page 23.

  • 1
    $\begingroup$ The 1st result does not imply the 2nd! As you mention yourself, it's not hard to construct an example of $f\colon\mathbb N\to\mathbb R$ such that: (1) for any $\epsilon>0$, $f(n)<\epsilon n$ for "almost" all $n$, and (2) $f(n)/n\not\to 0$ as $n\to\infty$. So, what's the problem: you believe that the limit is true (from numerical evidence) and wish to improve Alaoglu--Erdős? My own experience shows that if the latter can be strengthened, then there should be Erdős's conjecture already in that paper. $\endgroup$ Jun 9, 2010 at 23:45
  • $\begingroup$ It's not that I believe it to be true, Professor Zudilin. It's just that I wanted to know whether I was missing some properties of the arithmetical functions involved that yielded at once a "thorough" demonstration of the purported claim. $\endgroup$ Jun 10, 2010 at 0:14
  • 1
    $\begingroup$ Don't trust no-author books! You didn't miss an argument but the Mathematical Reflections did. I am happy to see that Gerry gives some clear evidence of why $\limsup_{n\to\infty}\phi(\sigma(n))/n>0$ (and most probably is $1/2$). $\endgroup$ Jun 10, 2010 at 1:37
  • $\begingroup$ Thanks for taking the time to leave your comments, Professor Zudilin. $\endgroup$ Jun 10, 2010 at 1:52
  • 2
    $\begingroup$ Why go so far in the proof? His second statement is already false, the set X contains all of the sequence, and is not bounded. The print is riddled with errors and typos, it is impossible to know what C.L. actually meant. $\endgroup$ Jun 10, 2010 at 6:45

1 Answer 1


Everyone knows (but no one can prove) that there are infinitely many primes $p$ such that $q=2p-1$ is also prime. $\sigma(q)=q+1=2p$, $\phi(\sigma(q))=\phi(2p)=p-1$, $\phi(\sigma(q))/q=(p-1)/(2p-1)\to1/2$ as $q\to\infty$.

Edit: I don't know why it didn't occur to me to look at Guy, Unsolved Problems In Number Theory. Under B42, he writes, "Makowski and Schinzel prove that $\limsup\phi(\sigma(n))/n=\infty$. The reference is A. Makowski, A. Schinzel, On the functions $\phi(n)$ and $\sigma(n)$, Colloq Math 13 (1964-65) 95-99, MR 30 #3870. I haven't found the paper on the web, but it's in Volume 2 of Schinzel's Selecta, 890-894. I don't have the energy to write out the proof in full, but here's the idea. Given $M$, choose $t$ such that $$\prod_{i=1}^t{p_i\over p_i-1}>M$$. Then given $p$ (and it's not clear to me whether $p$ is meant to be a prime), and letting $$n=\sigma\left(\prod_{i=1}^tp_i^{p-1}\right),$$ we get $$\sigma(n)=\prod_{i=1}^tN(p_i,p),$$ where $N(a,p)=(a^p-1)/(a-1)$. Now you prove $\limsup_{p\to\infty}\phi(\sigma(n))/n\gt M$, using along the way a lemma which says that $$\lim_{p\to\infty}{\phi(N(a,p))\over N(a,p)}=1.$$

  • $\begingroup$ That's a good point, Gerry! +1 $\endgroup$ Jun 10, 2010 at 1:09
  • $\begingroup$ How do you call those primes p such that 2p-1 is also a prime number? Certainly, they are not Sophie Germain primes, are they? $\endgroup$ Jun 10, 2010 at 1:48
  • $\begingroup$ @Gerry: Are you sure you did not mean to write $2^{p}-1$? $\endgroup$ Jun 10, 2010 at 1:53
  • $\begingroup$ @J. H. S., $2^p-1$ also works, but what I wrote is what I meant. Why do you ask? Is there a mistake in my calculations? Or is it that you are more convinced of the infinity of primes of form $2^p-1$ than you are of primes of form $2p-1$? $\endgroup$ Jun 10, 2010 at 2:05
  • $\begingroup$ Mainly because I don't know how it that those primes $p$ are called. $\endgroup$ Jun 10, 2010 at 2:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .