Monday, 28 October 2019

Lagrange's Four-Square Theorem

Today's number of \(25775\), corresponding to my diurnal age, brought me into contact with Lagrange's Four-Square Theorem, also known as Bachet's Conjecture. To quote from Wikipedia, the theorem states that every natural number can be represented as the sum of four integer squares: $$p = a_0^2 + a_1^2 + a_2^2 + a_3^2$$where the four numbers \(a_0, a_1, a_2, a_3\) are integers. For illustration, 3, 31 and 310 can be represented as the sum of four squares as follows:$$\begin{align}
3 & = 1^2+1^2+1^2+0^2 \\[3pt]
31 & = 5^2+2^2+1^2+1^2 \\[3pt]
310 & = 17^2+4^2+2^2+1^2.
\end{align}$$ This theorem was proven by Joseph Louis Lagrange in 1770."

Historically, Wikipedia goes on to say that:
From examples given in the ''Arithmetica'' it is clear that Diophantus was aware of the theorem. This book was translated in 1621 into Latin by Claude Gaspard Bachet de Méziriac, who stated the theorem in the notes of his translation. But the theorem was not proved until 1770 by Lagrange. 
Adrien-Marie Legendre completed the theorem in 1797–8 with his Legendre's three-square theorem, by proving that a positive integer can be expressed as the sum of three squares if and only if it is not of the form \(4^k(8m+7)\) for integers \(k\) and \(m\). Later, in 1834, Carl Gustav Jakob Jacobi discovered a simple formula for the number of representations of an integer as the sum of four squares with his own Jacobi's four-square theorem. 
The formula is also linked to Descartes' theorem of four "kissing circles", which involves the sum of the squares of the curvatures of four circles. This is also linked to Apollonian gaskets, which were more recently related to the Ramanujan–Petersson conjecture.
Getting back to \(25775\), it turns out to be a member of OEIS A243580: integers of the form \(8k + 7\) that can be written as a sum of four distinct squares of the form \(m, m + 1, m + 3, m + 5\), where \(m == 2 \text{ (mod } 4) \). The particular value of \(m\) here is \(78\) so that we have:$$25775=78^2 + 79^2 + 81^2 + 83^2$$There are many proofs of the theorem and two are described in the Wikipedia article. They seem complicated and I haven't delved into them. However, what's of particular interest in the article is the number of ways in which a number can be represented as a sum of four squares, based on the sum (rather than the number) of divisors. There is a rule for the number of ways that a number can be written as a sum of two squares but this is based on powers of its prime divisors. The rule for the four squares is that the number is:
  • \(8\) times the sum of the divisors of the number if it is odd and 
  • \(24\) times the sum of the odd divisors of the number if it is even 
These numbers count squares in different positions and also include negative numbers. Thus the odd number \(1\), that has a sum of divisors equal to \(1\), has eight possible representations:
  • \(1^2+0^2+0^2+0^2\) with the 1 in four possible positions
  • \((-1)^2+0^2+0^2+0^2\) with the -1 in four possible positions
The number \(25775\) with a sum of \(31992\) would have a staggering \(8 \times 31992 = 255936\) possible representations as a sum of four squares. None of these representations would involve zero because \(25775\) cannot be expressed as a sum of two or three squares. It's easier to work initially with smaller numbers to begin with so let's take \(15 = 3 \times 5\) with a sum of divisors of \(24\). I've chosen \(15\) because it's equal to \(8 \times 1+7\) and thus cannot be represented as a sum of three squares. Thus \(15\) should have \(8 \times 24 = 192\) representations. This is indeed the case. However, if we don't regard different positions as being different, then there are only twelve arrangements. If we exclude negative numbers, there is only one arrangement: \(1^2+1^2+2^2+3^2\).

Moving on to \(23 = 8 \times 2+7\), there is again only one positive arrangement and that is \(1^2+2^2+3^2+3^2 \). With \(31 = 8 \times 3+7\), there are two positive arrangements: \(1^2+1^2+2^2+5^2\) and \(2^2+3^2+3^2+3^2\). Being primes, the sums of divisors of \(23\) and \(31\) are \(24\) and \(32\) respectively and so by Jacobi's theorem there are \(8 \times 24 =192\) and \(8 \times 32 = 256\) possible arrangements. It would seem that the theorem is of little practical use but interesting to explore nonetheless.

Saturday, 26 October 2019

The Smallest Parts Partition Function

Today I turned 25773 days old and I felt it shouldn't pass without making mention of this number's connection to the Smallest Parts Partition Function. This function assigns to each natural number \(n\), another number which is the total of the smallest parts in all partitions of \(n\). Here is the mapping, from \(n=1\) up to \(n=30\):

1, 3, 5, 10, 14, 26, 35, 57, 80, 119, 161, 238, 315, 440, 589, 801, 1048, 1407, 1820, 2399, 3087, 3998, 5092, 6545, 8263, 10486, 13165, 16562, 20630, 25773, ...

Figure 1 shows the SageMath code that I wrote to generate this sequence, up to and including 25773. Here is the Permalink.

Figure 1: SageMath code to generate
Smallest Parts Partition Numbers

Here is the example given in the OEIS A092269 comments:
Partitions of 4 are [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]. 
1 appears four times in [1, 1, 1, 1]
1 appears two times in [1, 1, 2]
2 appears two times in [2, 2]
1 appears once in [1, 3]
4 appears once in [4]
Thus a(4)=4+2+2+1+1=10

Figure 2 shows a plot of the values up to 25773:

Figure 2: plot of the Smallest Parts Partition Function

Like the partition function, there is a generating function but it's rather complicated and I won't include it here. However, it can be viewed in the OEIS comments. I just wanted to mention it because the next member of the sequence is 31897 which is a long way off. There are a number of academic papers about this function so it is a topic of serious mathematical interest.

The number of partitions from 1 to 30 are shown in the list below:

[1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604]

It's interesting to look at the ratio between the total value of the number of smallest parts and the number of partitions for numbers between 1 and 30. The results and a plot of these values can be found in Figure 3.

Figure 3

Thursday, 10 October 2019

Totient and Sigma <--> Primes and Biprimes

Though it was obvious when I looked into it, I only recently realised that, for any prime number, the average of its totient and sum of divisors is equal to the number itself. This is because for a prime number \(p\), it's only divisors are itself and \(1\), thus the sum of divisors is \(p+1\). For the totient, the only number that is coprime with \(p\) is 1 and thus the totient is \(p-1\). Adding the sum of divisors and the totient together gives \(2p\) and the average is \(p\). Thus formally stated:


In a similar vein, it was only today that I discovered that for a number that is biprime, sometimes called semiprime, the average of its sum of divisors and totient is always one more than the number. Again, this was obvious once I looked into it. The reason is that a biprime number \(n\) has only two factors, let's say \(a\) and \(b\). Thus \(n=ab\). The sum of divisors is thus \(n+a+b+1\). For the totient, there are \(b-1\) multiples of \(a\) and \(a-1\) multiples of \(b\) that are coprime with \(n\). Thus the totient is \(n-a-b-1\), remembering that 1 is regarded as being coprime as well. Adding the sum of divisors and the totient together and averaging, we get:$$ \frac{(n+a+b+1)- (n-a-b-1)}{2}=\frac{2n+2}{2}=n+1$$This is all very simple stuff but I'd never seen this connection between the totients and sums of divisors of primes and biprimes formally stated before. Thus formally stated: