NTIC Heuristics for the Sum of Divisors

Section 20.4 Heuristics for the Sum of Divisors

Subsection 20.4.1 Numbers instead of points

Could this type of argument conceivably be used for

σ = σ_{1} ?

🔗

The answer is yes! Consider the following rewrite of the sum of sigmas, which are themselves the sum of divisors:

\sum_{n \leq x} σ (n) = \sum_{n \leq x} \sum_{q ∣ n} q = \sum_{q, d such that q d \leq x} q = \sum_{d \leq x} \sum_{q \leq \frac{x}{d}} q .

🔗

We have changed from a sum of sums of divisors (which might not be consecutive, and makes

σ

annoying to compute) to a sum of sums of consecutive integers⁵.

Most proofs of the ideas in this section are quite terse, which was inappropriate for my students; I have drawn from [E.4.5, Chapter 4.4], [E.2.9, Section 22], and [E.4.6, Theorem 3.4].

🔗

We can think about this graphically again. Instead of comparing points on a hyperbola with points in columns or rows, though, we will compare numbers at points on a hyperbola with numbers at points in rows. We can think of it as summing up a weighted set of points. Consider Figure 20.4.1.

Labeled lattice points for $\sigma$ — 🔗
Figure 20.4.1. Labeled lattice points for $σ$

🔗

Example 20.4.2.

In Figure 20.4.1 we see (by following hyperbolas $x y = n,$ up through the graphed one $x y = 6$ ) that

\sum_{k = 1}^{6} σ (k) = 1 + (1 + 2) + (1 + 3) + (1 + 2 + 4) + (1 + 5) + (1 + 2 + 3 + 6) .

Then we can rearrange this to go along rows instead as

(1 + 2 + 3 + 4 + 5 + 6) + (1 + 2 + 3) + (1 + 2) + 1 + 1 + 1,

which means we can think of it as a sum of sums from $1$ to the length of each row.

🔗

Use the following interact to confirm that each row is,

⌊ \frac{n}{k} ⌋

in length, as with

τ .

xxxxxxxxxx
 
@interact
def _(n=(6,list(range(2,50)))):
    viewsize=n+1
    g(x)=1/x
    P=Graphics()
    P += plot(n*g,(x,0,n+1))
    grid_pts = [[i,j] for i in [1..viewsize] for j in [1..viewsize]]
    P += points(grid_pts,rgbcolor=(0,0,0),pointsize=2)
    lattice_pts = [coords for coords in grid_pts if (coords[0]*coords[1]<=n)]
    for thing in lattice_pts:
        P += text(thing[0],thing,rgbcolor=(0,0,0))
    show(P,ymax=viewsize,aspect_ratio=1)

🔗

Let's take stock of the graphic and

σ .

Each row has $⌊ \frac{n}{k} ⌋$ integers.
Adding up the first $j$ integers (from one to $j$ ) has formula

$\frac{j (j + 1)}{2} = \frac{j^{2}}{2} + \frac{j}{2}$

(recall again Example 1.2.4).
The most wrong $\frac{⌊ j ⌋ (⌊ j ⌋ + 1)}{2}$ can be from $\frac{j (j + 1)}{2}$ is $j + 1 = O (j)$ (this is simple algebra).

🔗

If we combine all this information, we get

\sum_{n \leq x} σ (n) = \sum_{d \leq x} \sum_{q \leq \frac{x}{d}} q = \sum_{d \leq x} [\frac{1}{2} {⌊ \frac{x}{d} ⌋}^{2} + \frac{1}{2} ⌊ \frac{x}{d} ⌋]

= \sum_{d \leq x} [\frac{1}{2} {(\frac{x}{d})}^{2} + \frac{1}{2} (\frac{x}{d}) + O (\frac{x}{d})] .

🔗

Subsection 20.4.2 Order calculations and more

🔗

But this is actually possible to analyze! First, we perform some order calculations.

🔗

We already saw that

\sum_{d \leq x} \frac{1}{d} = \log (x) + O (1),

\sum_{d \leq x} \frac{1}{2} (\frac{x}{d}) = \frac{1}{2} O (x \log (x)) = O (x \log (x)) .

🔗

(See Exercise 20.6.15.) Also,

\sum_{d \leq x} O (\frac{x}{d})

must be

O (x \sum_{d \leq x} \frac{1}{d}) = O (x \log (x)) .

🔗

Next, let's get more information about

\sum_{d \leq x} [\frac{1}{2} {(\frac{x}{d})}^{2}] .

Recall that the (convergent) improper integral

\int_{x}^{\infty} \frac{d y}{y^{2}}

approximates

\sum_{d > x} \frac{1}{d^{2}} .

🔗

Since both converge, and by the same pictures as above, the error is certainly

O (1 / x^{2}) .

Then I can rewrite things as

\sum_{d \leq x} \frac{1}{d^{2}} = \sum_{d = 1}^{\infty} \frac{1}{d^{2}} - \sum_{d > x} \frac{1}{d^{2}}

= \sum_{d = 1}^{\infty} \frac{1}{d^{2}} - \int_{x}^{\infty} \frac{1}{y^{2}} d y + O (1 / x^{2}) = \sum_{d = 1}^{\infty} (\frac{1}{d^{2}}) - \frac{1}{x} + O (1 / x^{2}) .

🔗

Thus the whole crazy double sum can be approximated as follows, quite accurately:

\sum_{n \leq x} σ (n) = \frac{x^{2}}{2} \sum_{d \leq x} (\frac{1}{d^{2}}) + \frac{x}{2} \sum_{d \leq x} \frac{1}{d} + O (x \log (x))

= \frac{x^{2}}{2} (\sum_{d = 1}^{\infty} (\frac{1}{d^{2}}) - \frac{1}{x} + O (1 / x^{2})) + O (x \log (x))

= \frac{x^{2}}{2} \sum_{d = 1}^{\infty} (\frac{1}{d^{2}}) - \frac{x}{2} + O (x \log (x)) .

🔗

And the average value of

σ

must be this divided by

x,

namely

\frac{1}{x} \sum_{n \leq x} σ (n) is \frac{x}{2} \sum_{d = 1}^{\infty} \frac{1}{d^{2}} + O (\log (x)) .

🔗

Since we know that the series converges, this means the average value of

σ

increases quite linearly, with an error (at most) increasing logarithmically! This might be a shock – that one could actually get something fairly accurate like this relatively easily using calculus ideas like improper integrals and (implicitly) the integral test for infinite series. But check out the data!

Plotting average of $\sigma$ for $n=10,1000$ — 🔗
Figure 20.4.3. Plotting average of $σ$ for $n = 10, 1000$

🔗

Of course, one might ask what the slope of this line is! It would have to be

m = \frac{1}{2} \sum_{d = 1}^{\infty} \frac{1}{d^{2}} .

Have you seen this constant before? (In a calculus class, you should have proved that it does converge.)

Comparing average of $\sigma$ with a line — 🔗
Figure 20.4.4. Comparing average of $σ$ with a line

🔗

Finding a summation of this was the so-called Basel problem, which Euler solved and showed is

\frac{π^{2}}{6} .

So the slope is

\frac{π^{2}}{12} .

Amazing! (See also Section 24.4.)