If we take an infinite set $S$ of positive numbers with the property that the number of prime divisors of the elements is unbounded above, then can we make $\phi(n)/n$ arbitrarily small for infinitely many $n \in S$? Can we do this by simply taking the number of prime divisors sufficiently large? I ask this in light of the following little calculation: First it is equivalent to show we can make $n/\phi(n)$ arbitrarily large for infinitely many $n \in S$. Now $$ \dfrac{n}{\phi(n)} = \prod_{p \mid n} \left(\dfrac{1}{1 - \frac{1}{p}} \right) = \prod_{p \mid n}\left( 1 + p^{-1} + p^{-2} + \cdots \right) = \sum_{\substack{d = 1 \\ \operatorname{rad}(d) \mid n}}^{\infty} \dfrac{1}{d}, $$ where $\operatorname{rad}(d)$ denotes the product of all the distinct prime divisors of $d$. So as the number of prime divisors of $n$ goes to infinity we get the divergent harmonic series. What are your thoughts on this? Thanks.


By making the primes that occur in the factorizations of elements of $S$ grow sufficiently fast, we can force $\frac{\varphi(n)}{n}$ to be bounded away from $0$ on $S$.

For example, let $q_1,q_2,\dots$ be an infinite increasing sequence of primes such that $q_{k+1}\gt 2q_k$, and let $S$ be the set of all products $q_1q_2\cdots q_m$.

  • $\begingroup$ Thanks it makes sense. One question then would be, say you know the rate at which the size of the prime factors of the elements in $S$ increases. Say you know their asymptotic growth. How large, relative to this rate, would the number of prime factors of the elements in $S$ have to be in order to get divergence as the number of prime factors increases? Would any asymptotically higher growth suffice? $\endgroup$ – Lucas Aug 12 '14 at 18:35
  • $\begingroup$ These are I think hard questions. For the example, essentially the formula you wrote out guarantees that $\varphi(n)/n$ is bounded away from $0$. But to address the questions in your comment, one would have to first assign a meaning to the rate of increase. It is not clear how to do that. Because the harmonic series diverges reluctantly, the "growth rate" would not need to be large, my exponential growth was vast overkill. $\endgroup$ – André Nicolas Aug 12 '14 at 18:42
  • $\begingroup$ Thanks. For instance suppose we take an increasing sequence instead $S = \{a_n \}_{n=1}^{\infty}$ with the property that the size of the prime factors of $a_n$ grow linearly (instead of exponential!) with $n$. What now? $\endgroup$ – Lucas Aug 12 '14 at 18:49
  • $\begingroup$ Good question. It might be useful to ask it separately. Editing the current one would be much less noticeable. Ideally, the question would be precise, and specify precisely what you mean by the primes growing linearly, since it cannot be the ordinary meaning. I would also suggest asking not far from a "good" time. Latish evening in North America is not good. $\endgroup$ – André Nicolas Aug 12 '14 at 18:57
  • $\begingroup$ Cool. I'll do that soon. Thanks again! $\endgroup$ – Lucas Aug 12 '14 at 18:59

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.