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 \sigma=\sigma_1\text{?} The answer is yes! Consider the following rewrite of the sum of sigmas, which are themselves the sum of divisors:
\begin{equation*}
\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\text{.}
\end{equation*}
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 5 Most proofs of this are quite terse, which was inappropriate for my students; I have drawn from [C.4.5, Chapter 4.4 ], [C.2.9, Section 22], and [C.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.
Example 20.4.2.
In Figure 20.4.1 we see that
\begin{equation*}
\sum_{k=1}^6\sigma(k)=1+(1+2)+(1+3)+(1+2+4)+(1+5)+(1+2+3+6)=
\end{equation*}
\begin{equation*}
(1+2+3+4+5+6)+(1+2+3)+(1+2)+1\text{,}
\end{equation*}
which means we can think of it as a sum of sums from 1 to the length of each row.
xxxxxxxxxxdef _(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)Each row has \left\lfloor\frac{n}{k}\right\rfloor integers.
-
Adding up the first j integers (from one to j) has formula
\begin{equation*} \frac{j(j+1)}{2}=\frac{j^2}{2}+\frac{j}{2}\text{,} \end{equation*}which we used in Subsection 20.3.2 as well.
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).
\begin{equation*}
\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]
\end{equation*}
\begin{equation*}
=\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]\text{.}
\end{equation*}
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)\text{,} so
\begin{equation*}
\sum_{d\leq x}\frac{1}{2}\left(\frac{x}{d}\right)=\frac{1}{2}O(x\log(x))=O(x\log(x))\text{.}
\end{equation*}
(See Exercise 20.6.15.) Also, \sum_{d\leq x}O\left(\frac{x}{d}\right) must be
\begin{equation*}
O\left(x\sum_{d\leq x}\frac{1}{d}\right)=O(x\log(x))\text{.}
\end{equation*}
Next, let's get more information about \sum_{d\leq x}\left[\frac{1}{2}\left(\frac{x}{d}\right)^2\right]\text{.} Recall that the (convergent) improper integral \int_x^{\infty}\frac{dy}{y^2} approximates \sum_{d>x}\frac{1}{d^2}\text{.}
Since both converge, and by the same pictures as above, the error is certainly O(1/x^2)\text{.} Then I can rewrite things as
\begin{equation*}
\sum_{d\leq x}\frac{1}{d^2}=\sum_{d=1}^{\infty}\frac{1}{d^2}-\sum_{d>x}\frac{1}{d^2}
\end{equation*}
\begin{equation*}
= \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)\text{.}
\end{equation*}
Thus the whole crazy double sum can be approximated as follows, quite accurately:
\begin{equation*}
\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\log(x))
\end{equation*}
\begin{equation*}
=\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\log(x))
\end{equation*}
\begin{equation*}
=\frac{x^2}{2}\sum_{d=1}^{\infty}\left(\frac{1}{d^2}\right)-\frac{x}{2}+O(x\log(x))\text{.}
\end{equation*}
And the average value of \sigma must be this divided by x\text{,} namely
\begin{equation*}
\frac{1}{x}\sum_{n\leq x}\sigma(n)\text{ is }\frac{x}{2}\sum_{d=1}^{\infty}\frac{1}{d^2}+O(\log(x))\text{.}
\end{equation*}
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!
