Fix $0 < \alpha < 1$ a real. Let $S_\alpha$ the set of integers $n \geq 1$ such that be $\phi(n)>\alpha n$. For $x>0$, let $S_\alpha(x)$ be the number of positive integers $n$ less han $x$ such that $n \in S_\alpha$.

Does $S_\alpha$ has a natural density (that is, does $\lim_{x \rightarrow \infty} S_\alpha(x)/x$ exist)? If so, is that density $0$, $1$ or in between? If not, same questions for $\liminf_{x \rightarrow \infty} S_\alpha(x)/x$ and $\limsup_{x \rightarrow \infty} S_\alpha(x)/x$.

Of course, $n \in S_\alpha$ if and only if $\prod_{p \mid n} (1-1/p) > \alpha$, where the product is over prime factors of $n$. But I am not sure where to go from here.


Yes -- look up the Erdos--Wintner theorem. (The special case you asked about was earlier proved by Schoenberg.) If we call the density $D(\alpha)$, then in fact $D$ is continuous and strictly decreasing on $[0,1]$, with $D(0)=1$ and $D(1)=0$.


Anonymous gave a perfect answer already. All I want to add to it is that you do not need to be Erdos or even Schoenberg to figure such things out. I'll just show how to establish the existence of density for $\alpha>0$, leaving the rest to you.

The starting point is that we know that for a pair of integers not exceeding $N$, to have a common divisor is a not very probable event and to have a large common divisor is a really rare event. Indeed, the number of pairs $(m,n)\in [1,N]\times [1,N]$ such that some fixed number $d$ divides both $m,n$ is at most $N^2/d^2$, so the number of pairs having a common divisor greater than $D$ is at most $N^2\sum_{d\ge D}d^{-2}\le N^2/(D-1)$.

Now, fix some $D$ and denote by $\Phi_D(n)$ the number of numbers $m\le n$ such that both $m,n$ are divisible by some prime $p>D$. What we just proved shows that $\frac 1N\sum_{n\le N}\Phi(n)\le \frac 1{D-1}$, so for every $\varepsilon>0$ we can be sure that the upper density of $n$ for which $\Phi_D(n)>\varepsilon n$ is less than $\varepsilon$ if $D$ is chosen large enough.

Let now $\varphi_D(n)$ be the number of $m\le n$ such that $m$ and $n$ have no common prime divisor less than $D$. Note that $\varphi_D(n)-\Phi_D(n)\le\varphi(n)\le\varphi_D(n)$ and $\Phi_D(n)$ is usually less than $\varepsilon n$. On the other hand, $\varphi_D(n)/n$ is completely determined by the remainder of $n$ modulo the product of primes less than $D$, so if we replace $\varphi$ by $\varphi_D$, the existence of density problem becomes trivial. Note that we can do it outside a set of arbitrarily small upper density with arbitrarily small error. So, the only problem may arise when the small error is not tolerable, i.e., when $\alpha$ is such that for all $\varepsilon>0$ the set of numbers $n$ with $\frac{\varphi(n)}n\in(\alpha-\varepsilon,\alpha+\varepsilon)$ has upper density bounded from below by some $c>0$ independently of $\varepsilon$.

The last step is to show that it is impossible. Let the upper density of the set $S_\varepsilon=\{n:|\frac{\varphi(n)}n-\alpha|<\varepsilon\}$ be greater than $c$ regardless of $\varepsilon$. Then the upper density of the set $S_D=\{n:|\frac{\varphi_D(n)}n-\alpha|<2\varepsilon\}$ is at least $c/2$ if $D$ is large enough. But $S_D$ has density, so, going back, we conclude that the lower density of $S_{3\varepsilon}$ is at least $c/4$. Now let $p$ be any prime greater than $8/c$. Let $S(p)=\{n\in S_{3\varepsilon}:p\not\mid n\}$. Then the lower density of $S(p)$ is at least $c/8$. Note now that $pS(p)$ has numbers with $\frac{\varphi(n)}n\approx \alpha(1-\frac 1p)$ up to $\pm 3\varepsilon$. If we take sufficiently large finite set $P$ of primes $p>8/\delta$ (the primes to choose depend on $c$ only), we'll get the disjoint sets $pS(p)$ (the disjointness will be guaranteed if $\varepsilon$ is so small that the $3\varepsilon$-intervals around the points $\alpha(1-\frac 1p)$ do not overlap) of lower density $\frac c{8p}$. However, we can choose $P$ so that $\frac c 8\sum_{p\in P}\frac 1p>1$, which is a clear contradiction.

Needless to say, the full Erdos-Wintner theorem is much deeper than this and is certainly worth learning if you like the elementary number theory.

  • $\begingroup$ Thanks fedja for writing this, that's very helpful. A small typo in the second line of the third paragraph: $\Phi$ should be $\Phi_D$ and $1/N$ should be $1/N^2$, isn't it ? $\endgroup$ – Joël Nov 6 '12 at 1:49
  • $\begingroup$ Yes :) Sorry for the typos. $\endgroup$ – fedja Nov 6 '12 at 12:42

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.