Hopefully your appetite is whetted a bit by the previous section, and especially the discussion opportunities about what you think might be possible.
So let's start exploring these questions with new functions.
Example18.2.1
Let \(r(n)\) be the number of (all!) ways to write \(n\) as a sum of (two) squares. (This was called \(r_2(n)\) when first encountered in Exercise 13.7.7, but we will not consider other \(r_k\).)
For instance, \(r(25)=12\). Why?
Because you can write it using the pairs \begin{equation*}(\pm 3,\pm 4),\; \; (\pm 4,\pm 3),\;\; (\pm 5,0)\text{ and }(0,\pm 5)\; .\end{equation*} Remember, we count all solutions, positive or negative, and in any particular order possible, in determining the value of \(r(n)\).
In Exercise 13.7.7, we saw that \(r(2^m)=4\). But we didn't discuss it enough to question whether there might be a formula that was easier to compute than the process of counting all possible sums!
As an encouragement to our search for answers to our three questions, I will give you a (totally unmotivated!) formula. To see what it looks like, we use an extension of the Fundamental Theorem of Arithmetic.
Fact18.2.2
Write the prime factorization of \(n\) as \begin{equation*}n=2^dp_1^{e_1}\cdots p_k^{e_k}q_1^{f_1}\cdots q_\ell^{f_\ell}\end{equation*} where we write primes of the form \(4k+1\) as \(p\), and primes of the form \(4k+3\) as \(q\). Then \begin{equation*}r(n)=\begin{cases}0 & \text{ if any }f_j\text{ is odd}\\4\prod_{i=1}^k(e_i+1) & \text{ otherwise}\end{cases}\end{equation*}
Unfortunately, it turns out that every single proof of this is not very elementary. They all either go into some detail regarding factorization of Gaussian integers (recall our allusion to this in Fact 14.1.6), or they do some lengthy divisibility and congruence analysis. So we will skip the proof.
To use this, notice that the empty product (no primes of the form \(4k+1\)) is 1, just like a sum over zero elements is zero. To prove Exercise 13.7.7, we note that if \(r(2^m)\) then all \(e_i\) and \(f_j\) are zero, then we are in the second case and we just get \(4\cdot 1\) for the product.
We just saw an impressive relation among values of \(\phi(n)\). As an example of it, \(\phi(5)\phi(3)=\phi(15)\), since the inputs are coprime. Similarly, there are some relations with multiplying for \(r\), though it certainly isn't multiplicative.
Example18.2.4
Indeed, now that we have a formula, we can compute this.
For instance, \begin{equation*}r(3)r(5)=r(15)\end{equation*} because both sides are zero!
For the same reason, \(r(8)r(7)=r(56)\).
On the other hand, \begin{equation*}r(25)r(13)=12\cdot 8=96\neq 24=r(325)\end{equation*}
Similarly, \(r(25)r(4)=12\cdot 4=48\neq 12=r(100)\).
In these examples, the inputs are relatively prime but it doesn't multiply. What might still be true? See Exercise Group 18.3.1–18.3.2.
In Subsection 18.1.3 we saw that (for \(\phi\)) even though we couldn't yet address long term behavior, we could at least see some patterns, and could say something about summing values. In this subsection, we will try to directly address long-term, average behavior for \(r(n)\).
To be precise, we will talk about limits with functions. Yes, limits in number theory!
Observe the following graphic. It has as its basic content the circle with radius \(\sqrt{n}\) and blue lattice points representing all pairs \((x,y)\) such that \(x^2+y^2\leq n\). There is a little box of area one around each such lattice point.
As you might expect, the boxes roughly cover the circle, but certainly not exactly. So what does this have to do with \(r(n)\)?
Each unit box around each lattice point can be thought of as standing in for a representation (as a sum of squares) of a given integer less than or equal to \(n\). Adding up all the areas would thus give a number, as a summation: \begin{equation*}\sum_{k=0}^{n}r(k)\end{equation*} So the area of the boxes can give us information about \(r\).
Fact18.2.6
Observe that the boxes neither cover nor are covered by the circle in question. However, we can say two things about them.
These boxes will entirely cover a disk of radius \(\sqrt{n}\) minus half the diagonal length of the boxes, namely \(\frac{1}{\sqrt{2}}\), which is the inner circle above.
Likewise, they are completely contained in a disk of radius \(\sqrt{n}\) plus half the diagonal length of the boxes.
Let's use this fact to create a double inequality in terms of the area covered by two circles and the squares. \begin{equation*}\pi \left(\sqrt{n}-\frac{1}{\sqrt{2}}\right)^2\leq \sum_{k=0}^{n}r(k)\leq \pi \left(\sqrt{n}+\frac{1}{\sqrt{2}}\right)^2\, , \end{equation*} If we divide by \(n\) and simplify a bit, then factor, we obtain \begin{equation*}\pi \frac{n-\sqrt{2n}+1/2}{n}\leq \frac{1}{n}\sum_{k=0}^{n}r(k)\leq \pi \frac{n+\sqrt{2n}+1/2}{n}\, ,\end{equation*} \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*}
We're almost at something interesting.
First, the limit as \(n\) goes to \(\infty\) of the lower and upper bounds with each of these inequalities exists. In fact, the limit of the bounds in both cases is \(\pi\).
Then, the beloved squeeze theorem from calculus implies that \begin{equation*}\lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n}r(k)=\pi\, .\end{equation*}
Finally, note that \(r(0)=1\), so its presence or absence will not affect the average in the limit at all.
We can interpret this line of thought as proving and saying:
Fact18.2.7
The average number of representations of a positive integer as a sum of squares is \(\pi\).
WHAT?!
But it's true. And there's more to come.
