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:

“For the time of towns is tolled from the world by funereal chimes, but in nature the universal hours are counted by succeeding tribes of animals and plants, and by growth of joy on joy.”
—Ralph Waldo Emerson (1803–1882)

“Every child has an inner timetable for growth—a pattern unique to him. . . . Growth is not steady, forward, upward progression. It is instead a switchback trail; three steps forward, two back, one around the bushes, and a few simply standing, before another forward leap.”
—Dorothy Corkville Briggs (20th century)

“The intension of a proposition comprises whatever the proposition entails: and it includes nothing else.... The connotation or intension of a function comprises all that attribution of this predicate to anything entails as also predicable to that thing.”
—Clarence Lewis (1883–1964)