Euler's Totient Function - Growth of The Function

Growth of The Function

In the words of Hardy & Wright, φ(n) is "always ‘nearly n’."

First

$\lim\sup \frac{\varphi(n)}{n}= 1,$

but as n goes to infinity, for all δ > 0

$\frac{\varphi(n)}{n^{1-\delta}}\rightarrow\infty.$

These two formulae can be proved by using little more than the formulae for φ(n) and the divisor sum function σ(n).
In fact, during the proof of the second formula, the inequality

$\frac {6}{\pi^2} < \frac{\varphi(n) \sigma(n)}{n^2} < 1,$

true for n > 1, is proven.
We also have

$\lim\inf\frac{\varphi(n)}{n}\log\log n = e^{-\gamma}.$ Here γ is Euler's constant, γ = 0.577215665..., eγ = 1.7810724..., e−γ = 0.56145948... .

Proving this, however, requires the prime number theorem. Since log log (n) goes to infinity, this formula shows that

$\lim\inf\frac{\varphi(n)}{n}= 0.$

In fact, more is true.

$\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}$ for n > 2, and

$\varphi(n) < \frac {n} {e^{ \gamma}\log \log n}$ for infinitely many n.

Concerning the second inequality, Ribenboim says "The method of proof is interesting, in that the inequality is shown first under the assumption that the Riemann hypothesis is true, secondly under the contrary assumption."

For the average order we have

$\varphi(1)+\varphi(2)+\cdots+\varphi(n) = \frac{3n^2}{\pi^2}+\mathcal{O} (n\log n)$

The "Big O" stands for a quantity that is bounded by a constant times nlog n (which is small compared to n2).

This result can be used to prove that the probability of two randomly-chosen numbers being relatively prime is

Read more about this topic: Euler's Totient Function

Famous quotes containing the words growth of, growth and/or function:

“The reality is that zero defects in products plus zero pollution plus zero risk on the job is equivalent to maximum growth of government plus zero economic growth plus runaway inflation.”
—Dixie Lee Ray (b. 1924)

“The windy springs and the blazing summers, one after another, had enriched and mellowed that flat tableland; all the human effort that had gone into it was coming back in long, sweeping lines of fertility. The changes seemed beautiful and harmonious to me; it was like watching the growth of a great man or of a great idea. I recognized every tree and sandbank and rugged draw. I found that I remembered the conformation of the land as one remembers the modelling of human faces.”
—Willa Cather (1873–1947)

“... the function of art is to do more than tell it like it is—it’s to imagine what is possible.”
—bell hooks (b. c. 1955)