NTIC Three Questions, Again

Section 18.2 Three Questions, Again

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.

🔗

Definition 18.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¹Although we briefly considered other $r_k$ in Example 14.2.3, and we will see another example in the remarkable Theorem 25.8.1, it is usually more convenient to simplify the notation. in Exercise 13.7.7.)

🔗

Example 18.2.2.

For instance, $r(25)=12\text{.}$ 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)\text{.} \end{equation*}$

Remember, we count all solutions, positive or negative, and in any particular order possible, in determining the value of $r(n)\text{.}$

🔗

Subsection 18.2.1 Formulas

🔗

In Exercise 13.7.7, we saw that

$r(2^m)=4\text{.}$ 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.

🔗

Fact 18.2.3.

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\text{,}$ and primes of the form $4k+3$ as $q\text{.}$ Then

$\begin{equation*} r(n)=\begin{cases}\hfill 0 & \text{ if any }f_j\text{ is odd}\\4\prod_{i=1}^k(e_i+1) & \text{ otherwise}\end{cases}\text{.} \end{equation*}$

🔗

Proof.

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.8), 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.

🔗

Sage note 18.2.4. Review quiz.

You can use various tools we've already seen to compute this with Sage, such as factoring and multiplication. Try it!

xxxxxxxxxx
 
​

🔗

Subsection 18.2.2 Relations

🔗

We just saw an impressive relation among values of

$\phi(n)\text{.}$ As an example of it,

$\phi(5)\phi(3)=\phi(15)\text{,}$ since the inputs are coprime. Similarly, there are some relations with multiplying for

$r\text{,}$ though it certainly isn't multiplicative.

🔗

Example 18.2.5.

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)\text{.}$
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)\text{.}$

In these examples, the inputs are relatively prime but it doesn't multiply. What might still be true? See Exercise Group 18.3.1–2.

🔗

Sage note 18.2.6. Explore here.

Feel free to explore here!

xxxxxxxxxx
 
​

🔗

Subsection 18.2.3 Limits (and summation)

🔗

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)\text{.}$

🔗

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\text{.}$ There is a little box of area one around each such lattice point.

Figure 18.2.7. Plotting sums of squares up to five

🔗

As you might expect, the boxes roughly cover the circle, but certainly not exactly. So what does this have to do with

$r(n)\text{?}$

🔗

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\text{.}$ Adding up all the areas would thus give a number, as a summation:

$\begin{equation*} \sum_{k=0}^{n}r(k)\text{.} \end{equation*}$

🔗

So the area of the boxes can give us information about

$r\text{.}$

🔗

Here, there are

$21$ boxes with a circle of radius

$\sqrt{5} \approx 2.24\text{,}$ giving a ratio of area of boxes to the square of the radius about

$4.2\text{.}$ Try it interactively below.

xxxxxxxxxx
 
@interact
def _(n=(5,[1..100])):
    viewsize=ceil(math.sqrt(n))+2
    a=(math.sqrt(n)+1/math.sqrt(2))^2
    b=(math.sqrt(n)-1/math.sqrt(2))^2
    g(x,y) = x^2+y^2
    P=Graphics()
    P += implicit_plot(g-n, (-viewsize,viewsize), (-viewsize,viewsize), plot_points = 200)
    P += implicit_plot(g-a, (-viewsize,viewsize), (-viewsize,viewsize), linestyle='--',plot_points = 200)
    P += implicit_plot(g-b, (-viewsize,viewsize), (-viewsize,viewsize), linestyle='--',plot_points = 300)
    grid_pts = [[i,j] for i in [-viewsize..viewsize] for j in [-viewsize..viewsize]]
    P += points(grid_pts,rgbcolor=(0,0,0),pointsize=2)
    lattice_pts = [coords for coords in grid_pts if (coords[1]^2+coords[0]^2<=n)]
    P += points(lattice_pts, rgbcolor = (0,0,1),pointsize=20)
    squares=[line([[k-1/2,l-1/2], [k+1/2,l-1/2],[k+1/2,l+1/2], [k-1/2,l+1/2],[k-1/2,l-1/2]], rgbcolor=(1,0,0)) for [k,l] in lattice_pts]
    for object in squares:
        P += object
    show(P, figsize = [5,5], xmin = -viewsize, xmax = viewsize, ymin = -viewsize, ymax = viewsize, aspect_ratio=1)
    pretty_print(html("There are $%s$ boxes with a circle of radius $%s$"%(len(squares),math.sqrt(n))))
    pretty_print(html("The ratio of the area of boxes to the square of the radius is $\\approx%s$"%(len(squares)/(math.sqrt(n)^2))))

🔗

Fact 18.2.8.

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}}\text{,}$ 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.

🔗

Proof.

Geometry.

🔗

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\text{.} \end{equation*}$

🔗

If we divide by

$n$ and simplify a bit, then factor, we obtain two more:

$\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}\text{,} \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)\text{.} \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\text{.}$
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\text{.} \end{equation*}$
Finally, note that $r(0)=1\text{,}$ 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:

🔗

Fact 18.2.9.

The average number of representations of a positive integer as a sum of squares is $\pi\text{.}$

WHAT?!

🔗

But it's true. And there's more to come.