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:

“I conceive that the leading characteristic of the nineteenth century has been the rapid growth of the scientific spirit, the consequent application of scientific methods of investigation to all the problems with which the human mind is occupied, and the correlative rejection of traditional beliefs which have proved their incompetence to bear such investigation.”
—Thomas Henry Huxley (1825–95)

“The wind of change is blowing through the continent. Whether we like it or not, this growth of national consciousness is a political fact.”
—Harold MacMillan (1894–1986)

“Cities force growth and make men talkative and entertaining, but they make them artificial. What possesses interest for us is the natural of each, his constitutional excellence. This is forever a surprise, engaging and lovely; we cannot be satiated with knowing it, and about it; and it is this which the conversation with Nature cherishes and guards.”
—Ralph Waldo Emerson (1803–1882)

“My function in life is not to be a politician in Parliament: it is to get something done.”
—Bernadette Devlin (b. 1947)