Let's begin by observing the following graphic of the average for \(\tau\).

The graphic shows how the average value of \(\tau\) up to \(n\) changes as we let \(n\) get bigger. This 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, but it's suggestive. Part of the unpredictability is from primes; every prime number contributes just 2 to the total (and so reduces the average value)!

Nonetheless, thinking about this might lead us to look a little deeper. For example, the ‘trend’ is concave down. So let's look at comparing it with various concave down functions. (The following interact supports multiplied constants with them as well.)

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

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 initial estimate in the interact.

We'll start with a heuristic, going right back to the sieve of Eratosthenes.

In that algorithm (6.2.2), 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 \begin{equation*}1=\frac{n}{n}<\frac{n}{d}<\frac{n}{\sqrt{n}}=\sqrt{n}\, .\end{equation*}

So the absolute most number of divisors possible (for a given \(n\)) 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 a silly idea beyond very small \(n\), but let's go with it.

Even if all the divisors were there, you would have \(\tau(n)\leq 2\sqrt{n}\) so that \(\tau(n)\) is \(O(\sqrt{n})\).

That estimate is very important! It means we can get a sense of a first bound on the average value of \(\tau\). At the very least we have that \begin{equation*}\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)}\end{equation*}

Let's rewrite this inequality in a more suggestive form. \begin{equation*}\frac{1}{n}\sum_{k=1}^n \tau(k)\leq \sum_{k=1}^n \frac{1}{n}2\sqrt{n(k/n)}\end{equation*} This form looks an awful lot like a Riemann sum with \(\Delta x=\frac{1}{n}\). To review, recall writing a Riemann sum for \(\int_0^1 x^2\; dx\) in the form \begin{equation*}\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\; .\end{equation*} (If you need a calculus refresher, there are several great free calculus texts in the American Institute of Mathematics list of approved textbooks.)

Doing the same type of summation for the function \(2\sqrt{nx}\) would give \begin{equation*}\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}\, .\end{equation*} That certainly suggests that the average of \(\tau\) might be \(O(\sqrt{n})\) with \(C=4/3\).

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 \begin{equation*}\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\end{equation*} This integral evaluates to \begin{equation*}\frac{4}{3}\sqrt{n}\left[\left(1+\frac{1}{n}\right)^{3/2}-\left(\frac{1}{n}\right)^{3/2}\right]\; .\end{equation*} The big extra factor on the right can be shown to be decreasing (using derivatives), and is always less than \(2\) for integers, so the entire expression will always be less than \(\frac{8}{3}\sqrt{n}\).

Thus one can write \begin{equation*}\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}\end{equation*} so that the average value is bounded by a constant times \(\sqrt{n}\) and is hence \(O(\sqrt{n})\). This implies, perhaps, that the average number of divisors goes steadily up! (If so, it guarantees it's concave down.)

However, we might also want to know what the average value of \(\tau\) is. The preceding subsections only tell 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 Exercise 20.6.8 (adapted from [C.3.5]):

• 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)\).