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 the, growth and/or function:

“There are enough fagots and waste wood of all kinds in the forests of most of our towns to support many fires, but which at present warm none, and, some think, hinder the growth of the young wood.”
—Henry David Thoreau (1817–1862)

“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)

“Every boy was supposed to come into the world equipped with a father whose prime function was to be our father and show us how to be men. He can escape us, but we can never escape him. Present or absent, dead or alive, real or imagined, our father is the main man in our masculinity.”
—Frank Pittman (20th century)