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$ – Wadim Zudilin Jun 9 '10 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$ – José Hdz. Stgo. Jun 10 '10 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$ – Wadim Zudilin Jun 10 '10 at 1:37
  • $\begingroup$ Thanks for taking the time to leave your comments, Professor Zudilin. $\endgroup$ – José Hdz. Stgo. Jun 10 '10 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$ – Dror Speiser Jun 10 '10 at 6:45

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$ – Wadim Zudilin Jun 10 '10 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$ – José Hdz. Stgo. Jun 10 '10 at 1:48
  • $\begingroup$ @Gerry: Are you sure you did not mean to write $2^{p}-1$? $\endgroup$ – José Hdz. Stgo. Jun 10 '10 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$ – Gerry Myerson Jun 10 '10 at 2:05
  • $\begingroup$ Mainly because I don't know how it that those primes $p$ are called. $\endgroup$ – José Hdz. Stgo. Jun 10 '10 at 2:07

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.