This graphic shows how the average value of \(\tau\) up to \(n\) changes as we let \(n\) get bigger. This just isn't enough data to tell whether there is a limiting value for the average value of \(\tau(n)\), even if you look out to the first 1000 integers. Remember, every prime number contributes just 2 to the total (and so reduces the average value)!

But thinking about this might lead us to look a little deeper. Can we try thinking about it in comparison with some other typical functions? Let's look comparing it with various concave down functions. Try a constant with them!

At the very least I can tell that the average value is Big Oh of a certain function. But how does it go up?

Here, out to one million, is once again our graph of averages of \(\tau(n)\) versus \(n\). Certainly this looks sort of like some kind of fractional exponent function, though a very slowly growing one – probably slower than \(\sqrt{x}\), our first estimate.

We'll start with a heuristic, and go right back to the sieve of Eratosthenes for this.

Recall that we proved that in order to test whether \(n\) is prime, you just have to check all numbers up through \(\sqrt{n}\). This is because any divisor \(\sqrt{n}<d<n\) implies the existence of a divisor \(\frac{n}{d}\) such that \[1=\frac{n}{n}<\frac{n}{d}<\frac{n}{\sqrt{n}}=\sqrt{n}\, .\]

So the absolute most number of divisors possible is if every number \(d\) less than \(\sqrt{n}\) was a divisor, and then all the \(\frac{n}{d}>\sqrt{n}\) you get were also divisors. That is is silly except for very small \(n\), but let's go with it.

Then you would have that \[\tau(n)\leq 2\sqrt{n}\] so that \[\tau(n)\text{ is }O(\sqrt{n}))\, .\]

But that is very important! This means we can get a sense of what the average value of \(\tau\) might be. We certainly have that \[\frac{1}{n}\sum_{k=1}^n \tau(k)\leq \frac{1}{n}\sum_{k=1}^n 2\sqrt{k}=\sum_{k=1}^n \frac{1}{n}2\sqrt{n(k/n)}\]

You might wonder why I wrote the sum in this way. The answer is that this looks an awful lot like a Riemann sum with \(\Delta x=\frac{1}{n}\). For instance, you may likely recall writing a Riemann sum for \(\int_0^1 x^2\; dx\) in the form \[\frac{1}{n}\left(\frac{1}{n}\right)^2+\frac{1}{n}\left(\frac{2}{n}\right)^2+\cdots+\frac{1}{n}\left(\frac{n}{n}\right)^2\; .\]

Doing the same thing for the function \(2\sqrt{nx}\) would give \[\sum_{k=1}^n \frac{1}{n}2\sqrt{n(k/n)}\approx \int_0^1 2\sqrt{nx}dx=2\sqrt{n}\int_0^1 \sqrt{x}\; dx=\frac{4}{3}\sqrt{n}\, .\] To make this rigorous, we will need to make a slight change of point of view in order to ensure it will be viewed as a left-hand sum of an increasing function (and hence the Riemann sum is less than the actual value of the integral).

Namely, consider that \[\frac{1}{n}\sum_{k=1}^n 2\sqrt{k}=\sum_{k=0}^{n-1}\left(\frac{1}{n}\right)2\sqrt{k+1}=\sum_{k=0}^{n-1}\left(\frac{1}{n}\right)2\sqrt{n(k/n)+1}\leq \int_0^1 2\sqrt{nx+1}\; dx\] And then, since this equals \[\frac{4}{3}\sqrt{n}\left[\left(1+\frac{1}{n}\right)^{3/2}-\left(\frac{1}{n}\right)^{3/2}\right]\] and since the big extra factor on the right can be shown to be decreasing using derivatives, and is always less than \(2\) for integers, the entire expression will always be less than \(\frac{8}{3}\sqrt{n}\).

Then one can write \[\frac{1}{n}\sum_{k=1}^n \tau(k)\leq \frac{1}{n}\sum_{k=1}^n 2\sqrt{k}\leq \frac{8}{3}\sqrt{n}\] and is hence \(O(\sqrt{n})\), so that the average value is also bounded by a constant time \(\sqrt{n}\). This implies, perhaps, that the average number of divisors goes steadily up!

However, we might also want to know what the average value of \(\tau\) is. This only tells us what it's less than! Here, it seems that it's hard to find the “right” value of \(C\) so that the average value would be the same order as \(\sqrt{n}\).

Try \(x^{1/3}\) in the interact; it doesn't seem to make matters any better.

In fact, one can show that \(\tau(n)=O(\sqrt[3]{n})\) as well. Here are the steps one might take. We make fleshing out the details an exercise.

• First, note that \(\tau\) is multiplicative.
• For a given prime \(p\), note that \(\tau\left(p^x\right)=x+1\) grows much more slowly than \(\left(p^x\right)^{1/3}=p^{x/3}\), which is exponential in \(x\).
  • What value do each of these have at \(x=0\)?
  • Take derivatives of both functions at \(x=0\) to show that the growth statement is definitely true for \(p\geq 23\).
  • Show that for each prime \(p\) less than \(23\) there is an \(x_p\) such that the growth statement is true after \(x_p\).
• Put these pieces of information together to show that \(\tau\) is \(O\left(x^{1/3}\right)\).