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

    “You know that the nucleus of a time is not
    The poet but the poem, the growth of the mind
    Of the world, the heroic effort to live expressed
    As victory. The poet does not speak in ruins
    Nor stand there making orotund consolations.
    He shares the confusions of intelligence.”
    —Wallace Stevens (1879–1955)

    “Perhaps our national ambition to standardize ourselves has behind it the notion that democracy means standardization. But standardization is the surest way to destroy the initiative, to benumb the creative impulse above all else essential to the vitality and growth of democratic ideals.”
    —Ida M. Tarbell (1857–1944)

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

    “Any translation which intends to perform a transmitting function cannot transmit anything but information—hence, something inessential. This is the hallmark of bad translations.”
    —Walter Benjamin (1892–1940)