Section20.1Sums of squares, once more
Our motivational example will be the one we discussed in the introductory chapter for functions. Let \(r(n)\) denote the 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, more or less rigorously, that \[\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^n r(k)=\pi\, .\]
Subsection20.1.1Errors, not just limits
As it happens, we can say something far more specific than just this limit. Recall one of the intermediate steps in our proof. \[\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)\] 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\), \[\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}\] 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.
As often happens with such things, the constant we proved is a lot bigger than it needs to be.
Subsection20.1.2Landau notation
It turns out there is a nice notation for how “big” an error is.
Example20.1.2
So 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}\), or Big Oh of \(1/\sqrt{N}\).
It is unknown in this case, by the way, just how small that error term really is. In 1906 it was shown that you could make it \(O(x^{-2/3})\), but it is also known that you cannot make it \(O(x^{-3/4})\).)
Now we want to apply these same ideas to the \(\tau\) and \(\sigma\) functions.
Questions: 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.