An asymptotic property of the divisor counting function

Let \tau(n) be the number of positive divisors of the positive integer n and let \phi(n) be Euler’s function. Then it is easily seen that

\phi(n)+\tau(n)\le n+1

for each n. So

\displaystyle\frac{\phi(n)}{n}+\frac{\tau(n)}{n}\le 1+\frac 1n

holds for all n.

Since there are infinitely many primes,

\displaystyle\limsup_{n\to\infty}\frac{\phi(n)}{n}=\lim_{n\to\infty}\frac{n-1}{n}=1.

So it follows that

\displaystyle\limsup_{n\to\infty}\frac{\tau(n)}{n}=0.

Therefore, by the sandwich theorem,

\displaystyle\lim_{n\to\infty}\frac{\tau(n)}{n}=0,

i.e., \tau(n)=o(n) as n\to\infty. In layman’s terms, this is saying that the number of divisors of n is small compared to n when n is large. The following plot of \tau(n)/n against n for 1\le n\le 500 captures this nicely.

Screenshot 2015-06-26 03.46.54

So this means, for example, that there are only finitely many positive integers n with more than n/2015 divisors, which I think is pretty neat!

Advertisements

Leave a comment

Filed under Number theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s