NTIC Sums of Squares, Once More

🔗

Section 20.1 Sums of Squares, Once More

🔗

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\text{.}$ Then we saw in Fact 18.2.9, more or less rigorously, that

$\begin{equation*} \lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^n r(k)=\pi\text{.} \end{equation*}$

🔗

Subsection 20.1.1 Errors, 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.

$\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\text{,}$ from the bounds, I can think of this in terms of an error. Using absolute values, we get, for large enough

$n\text{,}$

$\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}\text{,}$ 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. We include a static image at the end, but encourage you to explore.

xxxxxxxxxx
 
def r2(n):
    n = prime_to_m_part(n,2)
    F = factor(n)
    ret = 4
    for a,b in F:
        if a%4==3:
            if b%2==1:
                return 0
            else:
                n = prime_to_m_part(n,a)
        else:
            ret = ret * (b+1)
    return ret
​
def L(n):
    ls = []
    out = 0
    for i in range(1,n+1):
        out += r2(i)
        ls.append((i,out/i))
    return ls

xxxxxxxxxx
 
@interact
def _(n=100):
    P = line(L(n))
    P += plot(pi+pi*sqrt(2)/sqrt(x),x,3,n,color='red')
    P += plot(pi-pi*sqrt(2)/sqrt(x),x,3,n,color='red')
    P += plot(pi,x,3,n,color='red',linestyle='--')
    show(P)

Figure 20.1.1. Error bounds for average of sum of squares

🔗

Note that the actual number is well within the bounding curves given by the red lines, even for small

$n\text{.}$ This shows a general rule of thumb that, typically, the constant we prove will be a lot bigger than necessary. New research is about improving such bounds.

🔗

Subsection 20.1.2 Landau notation

🔗

It turns out there is a nice notation for how ‘big’ an error is.

🔗

Definition 20.1.2. Big Oh.

We say that $f(x)$ is $O(g(x))$ (“eff of eks is Big Oh of gee of eks”) if there is some positive constant $C$ and some positive number $x_0$ for which

$\begin{equation*} |f(x)|\leq Cg(x)\text{ for all }x>x_0\text{.} \end{equation*}$

This is known as Landau notation.

🔗

See Exercise Group 20.6.1–5 for some practice with this. In practice in this text, we will focus on

$C$ and elide details of

$x_0$ unless it is crucial to the narrative.

🔗

Example 20.1.3.

The average number of representations of an integer as a sum of squares is $\pi\text{,}$ and if you do the average up to $N\text{,}$ then the error will be no worse than some constant times $1/\sqrt{N}\text{.}$ So the sum's error is Big Oh of $1/\sqrt{N}\text{,}$ or $O(x^{-1/2})\text{.}$

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})$ (note that this is a more accurate statement, see Exercise 20.6.5). See Figure 20.1.4 for a visual representation, where $C=\pi\text{.}$

Figure 20.1.4. Better bound for average of sum of squares

It is also known that the error term is not as close as $O(x^{-3/4})\text{;}$ see [C.7.25] for much more information at an accessible level.

🔗

Now let's apply these ideas to the divisor summation functions

$\tau$ and

$\sigma$ from Definition 19.1.1 in the previous chapter. (We will use these common alternate notations –

$\tau$ for

$\sigma_0$ and

$\sigma$ for

$\sigma_1$ – from Remark 19.1.2 throughout this chapter.) Namely, consider the following interesting question.

🔗

Question 20.1.5.

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! We will start with

$\tau$ in Section 20.2, and address

$\sigma$ starting in Section 20.4. Finally, answering these questions will motivate us to ask the (much harder) similar questions one can ask about prime numbers, starting in Chapter 21.