NTIC Sums of Squares, Once More

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 .

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

| f (x) | \leq C g (x) for all x > x_{0} .

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 $π,$ 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},$ or $O (x^{- 1 / 2}) .$

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 = π .$

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});$ see [E.7.25] for much more information at an accessible level.

🔗

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

τ

and

σ

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

τ

for

σ_{0}

and

σ

for

σ_{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

τ

in Section 20.2, and address

σ

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.