MathOverflow Meta
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
A limit involving the totient function
Active 10 years, 7 months ago
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.
nt.number-theory erdos
José Hdz. Stgo.
José Hdz. Stgo.José Hdz. Stgo.
$\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
$\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
$\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.$$
Gerry MyersonGerry Myerson
$\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
Thanks for contributing an answer to MathOverflow!
Not the answer you're looking for? Browse other questions tagged nt.number-theory erdos or ask your own question.
Inverting the totient function
How to calculate Euler Totient Function up to a limit?
On an estimation involving Euler totient function
On a sum involving Euler totient function
Euler's totient function relative function
Results regarding the relative-totient function
An inequality for the Euler totient function
A sum involving Euler totient function
Summation involving Euler's totient function