Our motivational example will be the one we discussed in Section 18.1. Recall that \(r(n)\) denotes the (total) number of ways to represent \(n\) as a sum of squares, so that \(r(3)=0\) but \(r(9)=4\) and \(r(5)=8\). Then we saw in Fact 18.2.7, more or less rigorously, that \begin{equation*}\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^n r(k)=\pi\, .\end{equation*}
As it happens, we can say something far more specific than just this limit. Recall one of the intermediate steps in our proof. \begin{equation*}\pi \left(1-\sqrt{\frac{2}{n}}+\frac{1}{2n}\right)\leq \frac{1}{n}\sum_{k=0}^{n}r(k)\leq \pi \left(1+\sqrt{\frac{2}{n}}+\frac{1}{2n}\right)\end{equation*} Notice that if I subtract the limit, \(\pi\), from the bounds, I can think of this in terms of an error. Using absolute values, we get, for large enough \(n\), \begin{equation*}\left|\frac{1}{n}\sum_{k=0}^{n}r(k)-\pi\right|\leq \pi \left(\frac{\sqrt{2}}{\sqrt{n}}+\frac{1}{2n}\right)\leq Cn^{-1/2}\end{equation*} where the value of \(C\) is not just \(\pi\sqrt{2}\), but something a little bigger because of the \(\frac{1}{2n}\) term.
In the next two cells we set up some functions and then plot the actual number of representations compared with the upper and lower bound implied by this analysis.
Note that the actual number is well within the bounding curves given by the red lines. This shows a general rule that, as often happens, the constant we proved is a lot bigger than necessary. Often new research is about improving such bounds.
It turns out there is a nice notation for how ‘big’ an error is.
We say that \(f(x)\) is \(O(g(x))\) (“eff of eks is Big Oh of gee of eks”) if there is some constant \(C\) for which \begin{equation*}|f(x)|\leq Cg(x)\text{ for all large enough }x\, .\end{equation*} This is known as Landau notation.
See Exercise Group 20.6.1–20.6.5 for some practice with this.
The average number of representations of an integer as a sum of squares is \(\pi\), and if you do the average up to \(N\), then the error will be no worse than some constant times \(1/\sqrt{N}\). So the sum's error is Big Oh of \(1/\sqrt{N}\).
It is unknown in this case just how small the error term really is. In 1906 it was shown that it is \(O(x^{-2/3})\); see the following graphic.
It is also known that the error is not \(O(x^{-3/4})\).
Now let's apply these ideas to the \(\tau\) and \(\sigma\) functions.
What is the “average” number of divisors of a positive integer? What is the “average” sum of divisors of a positive integer?
It turns out that clever combinations of many ideas from the course as well as calculus ideas will help us solve these questions! And they will motivate us to ask the (much harder) similar questions one can ask about prime numbers, starting in Chapter 21.
