7
$\begingroup$

Maybe this is a well-know problem.

What do we know about distribution of the sequence $\bigl (\frac{\phi(n)}{n}\bigr )_{n=1}^{\infty}$ in $[0,1]$? (Where $\phi$ is the Euler's totient function).

In the other words does there exist a distribution like $\mu$ concentrated on $[0,1]$ that for every interval $[a,b]$ we have the following equation?

$$\lim_{n\to \infty} \frac{\# \ \{i \ |\ \frac{\phi(i)}{i} \in [a,b], \ 1\leq i \leq n \}}{n} = \mu([a,b]) $$

Is the sequence equidistributed in $[0,1]$?

$\endgroup$
  • 3
    $\begingroup$ The existence of a distribution is well known -- see old works of Schoenberg, and Erdos and Wintner. It is certainly not equidistribution: for example note that all even numbers, and all odd multiples of $105$ will have $\phi(n)/n <1/2$. $\endgroup$ – Lucia Apr 29 '15 at 20:32
  • 5
    $\begingroup$ Starting from $\frac{\phi(n)}{n} = \exp( \sum_p \log(1-\frac{1}{p}) 1_{p|n} )$, one can show (using the absolute convergence of $\sum_p \log(1-\frac{1}{p}) / p$) that the limiting distribution $\mu$ of $\frac{\phi(n)}{n}$ is the distribution of $\exp( \sum_p \log(1-\frac{1}{p}) I_p )$, where the $I_p$ are independent Bernoulli variables with expectation $1/p$. In other words, $\mu$ is the exponential of a certain Bernoulli convolution, which one would then typically expect to be rather singular in nature (as indicated by the references given in other answers here). $\endgroup$ – Terry Tao Apr 29 '15 at 22:24
  • 2
    $\begingroup$ If one were interested in the limiting distribution of $\frac{\phi(p-1)}{p-1}$ instead of $\frac{\phi(n)}{n}$, the only difference would be that the $I_p$ now have expectation $1/(p-1)$ rather than $1/p$. $\endgroup$ – Terry Tao Apr 29 '15 at 22:27
  • $\begingroup$ But would this approach lead to an explicit formula for the distribution or merely show its existence? $\endgroup$ – Captain Darling Apr 29 '15 at 23:05
  • 2
    $\begingroup$ Bernoulli convolutions are reasonably explicit (their characteristic function is a Riesz product, so their distribution is the inverse Fourier transform of a Riesz product), although the formula might not be terribly tractable in practice. $\endgroup$ – Terry Tao Apr 30 '15 at 5:32
7
$\begingroup$

As Lucia points out the existence of a limiting distribution for $\phi(n)/n$ is well-known. The most direct way to show that there is a limiting distribution is to compute the moment $$ \sum_{n \leq x} \Big ( \frac{\phi(n)}{n} \Big )^{k} $$ for all fixed positive integers $k$. The limiting distribution $G(t)$ is continuous but not differentiable. It is also known to be purely singular, so that $G'(t) = 0$ almost everywhere in $[0,1]$. In addition, for the modulus of continuity we know that $$ \sup_{0 \leq t \leq 1} |G(t) - G(t - \varepsilon t)| \ll \frac{1}{\log(1/\varepsilon)} $$ and that this is optimal. Finally the behavior as $t \rightarrow 0$ and $t \rightarrow 1$ is markedly different. As $t \rightarrow 0$ there is a doubly exponential decay in $1/t$, while the behavior at $t \rightarrow 1$ is such that $1 - G(1 - 1/\sigma) \sim c/\log \sigma$ as $\sigma \rightarrow \infty$.

For proofs and more informations a good starting point is

http://iecl.univ-lorraine.fr/~Gerald.Tenenbaum/PUBLIC/Prepublications_et_publications/EulerLocal.pdf

http://arxiv.org/pdf/1011.4262v1.pdf

and the references there-in.

$\endgroup$
  • $\begingroup$ The post of guestCLT is rather informative. I was wondering whether there is an explicit distribution for the sequence $\frac{\phi(p-1)}{p-1}$ as $p$ ranges over primes ? $\endgroup$ – Captain Darling Apr 29 '15 at 21:14

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.