Section20.4Heuristics for the sum of divisors

Could this conceivably be used for \(\sigma=\sigma_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}\sigma(n)=\sum_{n\leq x}\sum_{q\mid n} q = \sum_{q,d\text{ such that }qd\leq x} q = \sum_{d\leq x}\sum_{q\leq \frac{x}{d}} q\, .\] So we have changed from a sum of sums of divisors (which might not be consecutive, and makes \(\sigma\) annoying to compute) to a sum of sums of consecutive integers.

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. The picture below tells it all.

In the first one that shows up, we see that \[\sum_{k=1}^6\sigma(k)=1+(1+2)+(1+3)+(1+2+4)+(1+5)+(1+2+3+6)=\] \[(1+2+3+4+5+6)+(1+2+3)+(1+2)+1\; ,\] which means we can think of it as a sum of sums from \(1\) to the length of each row. Now let's note three things.

  • Each row is, of course, \(\left\lfloor\frac{n}{k}\right\rfloor\) in length, as with \(\tau\).
  • Adding up the first \(j\) integers from one to \(j\) is of course \[\frac{j(j+1)}{2}=\frac{j^2}{2}+\frac{j}{2}\; ,\] which we used above.
  • The most wrong \(\frac{\lfloor x\rfloor(\lfloor x\rfloor +1)}{2}\) can be from \(\frac{x(x+1)}{2}\) is \(j+1=O(j)\) (this is simple algebra).

So if we combine the information above with the formula, we get \[\sum_{n\leq x}\sigma(n)=\sum_{d\leq x}\sum_{q\leq \frac{x}{d}}q= \sum_{d\leq x}\left[\frac{1}{2}\left\lfloor\frac{x}{d}\right\rfloor^2+\frac{1}{2}\left\lfloor\frac{x}{d}\right\rfloor\right]=\sum_{d\leq x}\left[\frac{1}{2}\left(\frac{x}{d}\right)^2+\frac{1}{2}\left(\frac{x}{d}\right)+O\left(\frac{x}{d}\right)\right]\, .\]

Subsection20.4.1Order calculations and more

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

We already saw that \(\sum_{d\leq x}\frac{1}{d}= \ln(x)+O(1)\), so \[\sum_{d\leq x}\frac{1}{2}\left(\frac{x}{d}\right)=\frac{1}{2}O(x\ln(x))=O(x\ln(x))\; .\] Also, \(\sum_{d\leq x}O\left(\frac{x}{d}\right)\) must be \[O\left(x\sum_{d\leq x}\frac{1}{d}\right)=O(x\ln(x))\; .\]

Next, let's get more information about \(\sum_{d\leq x}\left[\frac{1}{2}\left(\frac{x}{d}\right)^2\right]\). Recall that the (convergent) improper integral \(\int_x^{\infty}\frac{dy}{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}dy+O(1/x^2)=\sum_{d=1}^{\infty}\left(\frac{1}{d^2}\right)-\frac{1}{x}+O(1/x^2)\, .\]

Thus the whole crazy double sum can be approximated as follows, quite accurately: \[\sum_{n\leq x}\sigma(n)= \frac{x^2}{2}\sum_{d\leq x}\left(\frac{1}{d^2}\right)+\frac{x}{2}\sum_{d\leq x}\frac{1}{d}+O(x\ln(x))\] \[=\frac{x^2}{2}\left(\sum_{d=1}^{\infty}\left(\frac{1}{d^2}\right)-\frac{1}{x}+O(1/x^2)\right)+O(x\ln(x))=\frac{x^2}{2}\sum_{d=1}^{\infty}\left(\frac{1}{d^2}\right)-\frac{x}{2}+O(x\ln(x))\, .\]

And the average value of \(\sigma\) must be this divided by \(x\), namely \[\frac{1}{x}\sum_{n\leq x}\sigma(n)\text{ is }\frac{x}{2}\sum_{d=1}^{\infty}\frac{1}{d^2}+O(\ln(x))\, .\] Since we know that the series converges, this means the average value of \(\sigma\) 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!

Of course, one might ask what the slope of this line is! It would have to be \(m=\frac{1}{2}\sum_{k=1}^{\infty}\frac{1}{d^2}\). Have you seen this constant before? (In a calculus class, you should have proved that it does converge.)

This is Euler's solution to the Basel problem, which is \(\frac{\pi^2}{6}\), so the slope is \(\frac{\pi^2}{12}\). Amazing!