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)

    “Rights! There are no rights whatever without corresponding duties. Look at the history of the growth of our constitution, and you will see that our ancestors never upon any occasion stated, as a ground for claiming any of their privileges, an abstract right inherent in themselves; you will nowhere in our parliamentary records find the miserable sophism of the Rights of Man.”
    —Samuel Taylor Coleridge (1772–1834)

    “Rights! There are no rights whatever without corresponding duties. Look at the history of the growth of our constitution, and you will see that our ancestors never upon any occasion stated, as a ground for claiming any of their privileges, an abstract right inherent in themselves; you will nowhere in our parliamentary records find the miserable sophism of the Rights of Man.”
    —Samuel Taylor Coleridge (1772–1834)

    “The uses of travel are occasional, and short; but the best fruit it finds, when it finds it, is conversation; and this is a main function of life.”
    —Ralph Waldo Emerson (1803–1882)