Lagrange’s Four Squares Theorem

In this article, we will discus Lagrange’s four square theorem in detail with examples and an algorithm to verify it.

Table of contents:

• What is a Natural Number?
• Did You Know?
• Proof
• Algorithm
• Time complexity
• Real Life applications
• Question

Before we delve into the details. Here are some interesting mathamatical facts you might not have known which will help you understand Lagrange’s Four Squares Theorem better.

What is a Natural Number?
Natural numbers are positive integers (whole numbers) such as 1, 2, 3, etc.

Did You Know?
1. Not every natural number can be written as a sum of two squares. For example, 9 = 0² + 3². But, we cannot write the number 6 in this way.
2. Not every natural number can be written as a sum of three squares. For example, 11 = 3² + 1² + 1². But, we cannot write the number 7 in this way.
3. Interestingly, every natural number can be written as the sum of four integer squares. Keep reading and you will soon find out how!

Lagrange’s Four Squares Theorem

According to Lagrange’s Four Squares Theorem, every natural number no matter how large, can be written as the sum of at most four non-negative integer squares.

Here are a few examples:

1 = 1² + 0² + 0² + 0²
2 = 1² + 1² + 0² + 0²
3 = 1² + 1² + 1² + 0²
4 = 1² + 1² + 1² + 1²
5 = 2² + 1² + 0² + 0²
331 = 17² + 5² + 4² + 1²
967 = 31² + 2² + 1² + 1²
23159 = 151² + 18² + 5² + 3²
23160 = 152² + 6² + 4² + 2²
97,995,689 = 9876² + 678² + 25² + 2²
835,411,385,623 = 913469² + 31397² + 7² + 2²

The following code provided in Python finds the 4 numbers which satisfies the conditions of Lagrange’s Four Squares Theorem for a given number n.

Proof
(1) Let G be a finite group and let H be a subgroup of G. Then |H| divides |G|. The order of H divides the order of G. The order of H and G is how many elements are in H and G.
(2) Let a ∈ G (Let a be an element of g)
Let ∅ be a function such that ∅: H --> aH and ∅(h) = ah, for any h ∈ H.
I claim that ∅ is a bijection.
Suppose x, y ∈ H and ∅(x) = ∅(y).
Then, ax = ay and x = y, by left cancellation.
So ∅ is one-to-one.
Let z ∈ aH.
Then, z = ah, for some h ∈ H.
So ∅(h) = ah = z.
Thereforce, ∅ is onto.
So, ∅ is a bijection.
(3) Since there is a bijection between H and aH, they must have the same number of elements.
Hence, |H| = |aH|.
This means that every left coset of H in G has the same numbers of elements as H.
Since the cosets of H in G parition G, it follows that |G| = r|H|, where r is the number of left cosets of H in G.
Therefore |H| divides |G|.

Implementation of Lagrange’s Four Squares Theorem

Algorithm

# a is the number whose 4 squares we are trying to find.  
def fourSqaureAlgorithm(a): 
 
    # Step 1: i will start at 0. In the first while loop, the first i will be 0 and the second i will be 0. 
    # 0 * 0 will give us 0 which is less than the value of variable a which is 25. 
    i = 0
    while (i * i <= a
    # Step 2: j will start at 0. In the second while loop, the first j will start at 0. The second j will start at 0. 
    # 0 * 0 will give us 0 which is less than the value of variable a which is 25. 
        j = i
        while (j * j <= a) :
        # Step 3: k will start at 0. In the second while loop, the first k will start at 0. The second k will start at 0. 
        # 0 * 0 will give us 0 which is less than the value of variable a which is 25. 
            k = j
            while (k * k <= a) :
            # Step 4: l will start at 0. In the second while loop, the first l will start at 0. The second l will start at 0. 
            # 0 * 0 will give us 0 which is less than the value of variable a which is 25. 
                l = k
                while (l * l <= a) :
 
                    # Step 5: check if sum of four squares equals
                    # the given number 25. Here we get 0 == 25, which is false. 
                    if (i * i + j * j + k * k + l * l == a) :        
 
                        # printing the numbers
                        print ("{} = {}*{} + {}*{} +".
                                format(a,i,i,j,j), end = " ")
                        print ("{}*{} + {}*{}".
                    
                    # Step 6: We increment l by 1 to get 1. l = 1. Go back up the while loops. 1 * 1 <= 25. 
                    # We recheck the addition of the value and if they equal 25 through the if statement. They do
                    # not so we increment l by 1 again and try again. 
                    l = l + 1
                k = k + 1
            j = j + 1
        i = i + 1 

Time complexity

The time complexity of the above algorithm will be O(N^2), as there are 4 nested loop of O(N^0.5).

Real Life Application of Lagrange’s Four Squares Theorem

An example of Lagrange’s Four Squares Theorem being used in real life is with police equipment. One piece of equipment called the "safety tutor", can detect violations of speed limits by snapping 2 seperate images of passing cars that are several miles apart. If the time elapsed between the 2 cars is shorter than the time it would take you to travel the distance, you will be given a ticket. Because it would mean your average speed is higher than the required limit. Lagrange’s theorem states that there is a point in the distance of the road checked by the safety tutor where your instantaneous speed is equal to the average speed, which was determined to be over the required limit.