NTIC Average of Tau

🔗

Section 20.2 Average of Tau

🔗

Subsection 20.2.1 Beginnings

🔗

Let's begin by observing Figure 20.2.1, which plots the average for

$\tau$ up to

$n=100\text{.}$

Average of $\tau\text{,}$ number of divisors

🔗

Sage note 20.2.2. Try to be efficient.

Observe the following two cells. The first cell records the successive sums of $\tau$ in a variable out (for ‘output’), so that we don't have to recalculate the entire sum each time we compute the average value for a different input value. We record the actual averages sequentially in a separate list ls.

Then the interactive cell is very simple indeed. Try being efficient in your programming!

xxxxxxxxxx
 
def L(n):
    ls = []
    out = 0
    for i in range(1,n+1):
        out += sigma(i,0)
        ls.append((i,out/i))
    return ls

xxxxxxxxxx
 
@interact
def _(n=100):
    P = line(L(n))
    show(P)

🔗

These graphics 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)\text{,}$ 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.)

xxxxxxxxxx
 
@interact
def _(n=100,C=.5,f=[x^(1/2), x, x^(1/3), x^(1/4), log(x), log(log(x)), x^(1.5), x^2]):
    f(x) = f
    P = line(L(n),legend_label=r'average of $\tau$')
    P += plot(C*f,(x,1,n), color='black', linestyle='--', legend_label='$%s%s$'%(RDF(C),latex(f(x))))
    show(P)

🔗

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

🔗

In Figure 20.2.3 we have our graph of averages of

$\tau(n)$ versus

$n\text{,}$ out to one million. Certainly this looks akin to some fractional exponent function. On the other hand, it seems to grow more slowly than

$\sqrt{x}=x^{1/2}\text{,}$ our initial estimate in the interact, so if it is, the exponent must be pretty small. (If you are familiar with semilog or log-log plots and are willing to look up how to do them in Sage, see Exercise 20.6.7 and then try to plot this on those axes.)

🔗

Subsection 20.2.2 Heuristics for tau

🔗

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}\text{.}$ 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}\text{.} \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.

🔗

This is a silly idea beyond such small

$n\text{,}$ but let's go with it anyway. Even if all those divisors were there, you would have

$\tau(n)=2\left\lfloor\sqrt{n}\right\rfloor\leq 2\sqrt{n}$ so that

$\tau(n)$ is

$O(\sqrt{n})\text{.}$

🔗

Example 20.2.4.

For $n=24$ this idea is actually true. We can line these up in pairs as $(1,24)\text{,}$ $(2,12)\text{,}$ $(3,8)\text{,}$ $(4,6)\text{,}$ and that gives $2\cdot \left\lfloor\sqrt{24}\right\rfloor=8$ total divisors.

🔗

That estimate is very important! It means we can get a sense of a first bound on the average value of

$\tau\text{.}$ 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}\text{.} \end{equation*}$

🔗

Subsection 20.2.3 Using sums to get closer

🔗

Let's rewrite this inequality in a more suggestive form by noting

$k=n(k/n)\text{:}$

$\begin{equation*} \frac{1}{n}\sum_{k=1}^n \tau(k)\leq \sum_{k=1}^n \frac{1}{n}2\sqrt{n(k/n)}\text{.} \end{equation*}$

🔗

This form looks an awful lot like a Riemann sum with

$x=k/n$ and

$\Delta x=\frac{1}{n}\text{.}$ 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\text{.} \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}\text{.} \end{equation*}$

🔗

That certainly suggests that the average of

$\tau$ might be

$O(\sqrt{n})$ with

$C=4/3\text{.}$

🔗

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]\text{.} \end{equation*}$

🔗

The big extra factor on the right can be shown to be decreasing as a function of

$n$ (using derivatives), and hence is always less than

$2$ for positive integers (plug in

$n=1$ to see), so the entire expression will always be less than

$\frac{8}{3}\sqrt{n}\text{.}$

🔗

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})\text{.}$ This implies, perhaps, that the average number of divisors goes steadily up! (If so, it guarantees that the trend is, on the whole, concave down.)

🔗

Subsection 20.2.4 But Big-Oh isn't enough

🔗

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! In the next interact, 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}\text{.}$

xxxxxxxxxx
 
def L(n):
    ls = []
    out = 0
    for i in range(1,n+1):
        out += sigma(i,0)
        ls.append((i,out/i))
    return ls
​
P = line(L(1000000))
​
@interact
def _(a=.02,n=2):
    show(P + plot(a*x^(1/n), (x,1,10^6), color='red',linestyle='--'))
    pretty_print(html(r"Blue is the average value of $\tau$"))
    pretty_print(html("Red is $%sx^{1/%s}$"%(a,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.10 (adapted from [C.4.5]):

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