[omqzhxkn] Lagrange Four-Square Theorem examples

A listing of numbers and how to express them as a sum of 4 squares will probably provoke curiosity: There isn't an obvious pattern of how to express a given number as sum of 4 squares.  Can all natural numbers be expressed this way?  (Yes, by Lagrange.)  Which numbers can be expressed as the sum of just 3 squares (answer: Legendre Three-Square Theorem), or 2?  As numbers get larger, there seems to be a trend of more ways to express it as 4 or fewer squares, kind of reminiscent of Goldbach conjecture.  What is the rate of growth of the number of ways?  What about cubes and higher powers (Waring's problem)?  There's lots of deep mathematics lurking just beneath the surface.  It's just a short skip and a jump to Fermat's Last Theorem.

We generated 4-square decompositions up to 121=11^2 in order to include 112 = 7 * 4^2, the first instance where Legendre's 3-square theorem applies with an exponent (on 4) greater than 1.  The number which had the most number of ways to express it in the range was 90, with 9.

We also provide a more compact list which expresses each number in the fewest number of squares, but still listing all possibilities for that fewest number of squares.  The full version has 436 lines; the compact version has 188.  The compact version makes it more clear (perhaps inspiring more curiosity) which numbers require 4 squares and which ones can be done in less.

Similar lists could be made for Gauss's Eureka Theorem on sum of 3 triangular numbers and the Goldbach conjecture on the sum of 2 primes.

Haskell source code is here.  Here is a pedagogical excerpt of how to choose num decreasing numbers bounded by 0 and amax.  We use the list as a nondeterminism monad.

choose_n_of_max :: Integer -> Int -> [[Integer]];
choose_n_of_max amax num = case compare num 0 of {
LT -> error "negative choose_n_of_max";
EQ -> return [];
GT -> do {
  x <- [0..amax];
  y <- choose_n_of_max x (pred num);
  return (x:y);
}};

Below is a machine-readable listing of the numbers through 121 and all the ways to express each number as the sum of 4 or fewer squares.

(0,[[0,0,0,0]]) (1,[[1,0,0,0]]) (2,[[1,1,0,0]]) (3,[[1,1,1,0]]) (4,[[1,1,1,1],[2,0,0,0]]) (5,[[2,1,0,0]]) (6,[[2,1,1,0]]) (7,[[2,1,1,1]]) (8,[[2,2,0,0]]) (9,[[2,2,1,0],[3,0,0,0]]) (10,[[2,2,1,1],[3,1,0,0]]) (11,[[3,1,1,0]]) (12,[[2,2,2,0],[3,1,1,1]]) (13,[[2,2,2,1],[3,2,0,0]]) (14,[[3,2,1,0]]) (15,[[3,2,1,1]]) (16,[[2,2,2,2],[4,0,0,0]]) (17,[[3,2,2,0],[4,1,0,0]]) (18,[[3,2,2,1],[3,3,0,0],[4,1,1,0]]) (19,[[3,3,1,0],[4,1,1,1]]) (20,[[3,3,1,1],[4,2,0,0]]) (21,[[3,2,2,2],[4,2,1,0]]) (22,[[3,3,2,0],[4,2,1,1]]) (23,[[3,3,2,1]]) (24,[[4,2,2,0]]) (25,[[4,2,2,1],[4,3,0,0],[5,0,0,0]]) (26,[[3,3,2,2],[4,3,1,0],[5,1,0,0]]) (27,[[3,3,3,0],[4,3,1,1],[5,1,1,0]]) (28,[[3,3,3,1],[4,2,2,2],[5,1,1,1]]) (29,[[4,3,2,0],[5,2,0,0]]) (30,[[4,3,2,1],[5,2,1,0]]) (31,[[3,3,3,2],[5,2,1,1]]) (32,[[4,4,0,0]]) (33,[[4,3,2,2],[4,4,1,0],[5,2,2,0]]) (34,[[4,3,3,0],[4,4,1,1],[5,2,2,1],[5,3,0,0]]) (35,[[4,3,3,1],[5,3,1,0]]) (36,[[3,3,3,3],[4,4,2,0],[5,3,1,1],[6,0,0,0]]) (37,[[4,4,2,1],[5,2,2,2],[6,1,0,0]]) (38,[[4,3,3,2],[5,3,2,0],[6,1,1,0]]) (39,[[5,3,2,1],[6,1,1,1]]) (40,[[4,4,2,2],[6,2,0,0]]) (41,[[4,4,3,0],[5,4,0,0],[6,2,1,0]]) (42,[[4,4,3,1],[5,3,2,2],[5,4,1,0],[6,2,1,1]]) (43,[[4,3,3,3],[5,3,3,0],[5,4,1,1]]) (44,[[5,3,3,1],[6,2,2,0]]) (45,[[4,4,3,2],[5,4,2,0],[6,2,2,1],[6,3,0,0]]) (46,[[5,4,2,1],[6,3,1,0]]) (47,[[5,3,3,2],[6,3,1,1]]) (48,[[4,4,4,0],[6,2,2,2]]) (49,[[4,4,4,1],[5,4,2,2],[6,3,2,0],[7,0,0,0]]) (50,[[4,4,3,3],[5,4,3,0],[5,5,0,0],[6,3,2,1],[7,1,0,0]]) (51,[[5,4,3,1],[5,5,1,0],[7,1,1,0]]) (52,[[4,4,4,2],[5,3,3,3],[5,5,1,1],[6,4,0,0],[7,1,1,1]]) (53,[[6,3,2,2],[6,4,1,0],[7,2,0,0]]) (54,[[5,4,3,2],[5,5,2,0],[6,3,3,0],[6,4,1,1],[7,2,1,0]]) (55,[[5,5,2,1],[6,3,3,1],[7,2,1,1]]) (56,[[6,4,2,0]]) (57,[[4,4,4,3],[5,4,4,0],[6,4,2,1],[7,2,2,0]]) (58,[[5,4,4,1],[5,5,2,2],[6,3,3,2],[7,2,2,1],[7,3,0,0]]) (59,[[5,4,3,3],[5,5,3,0],[7,3,1,0]]) (60,[[5,5,3,1],[6,4,2,2],[7,3,1,1]]) (61,[[5,4,4,2],[6,4,3,0],[6,5,0,0],[7,2,2,2]]) (62,[[6,4,3,1],[6,5,1,0],[7,3,2,0]]) (63,[[5,5,3,2],[6,3,3,3],[6,5,1,1],[7,3,2,1]]) (64,[[4,4,4,4],[8,0,0,0]]) (65,[[6,4,3,2],[6,5,2,0],[7,4,0,0],[8,1,0,0]]) (66,[[5,4,4,3],[5,5,4,0],[6,5,2,1],[7,3,2,2],[7,4,1,0],[8,1,1,0]]) (67,[[5,5,4,1],[7,3,3,0],[7,4,1,1],[8,1,1,1]]) (68,[[5,5,3,3],[6,4,4,0],[7,3,3,1],[8,2,0,0]]) (69,[[6,4,4,1],[6,5,2,2],[7,4,2,0],[8,2,1,0]]) (70,[[5,5,4,2],[6,4,3,3],[6,5,3,0],[7,4,2,1],[8,2,1,1]]) (71,[[6,5,3,1],[7,3,3,2]]) (72,[[6,4,4,2],[6,6,0,0],[8,2,2,0]]) (73,[[5,4,4,4],[6,6,1,0],[7,4,2,2],[8,2,2,1],[8,3,0,0]]) (74,[[6,5,3,2],[6,6,1,1],[7,4,3,0],[7,5,0,0],[8,3,1,0]]) (75,[[5,5,4,3],[5,5,5,0],[7,4,3,1],[7,5,1,0],[8,3,1,1]]) (76,[[5,5,5,1],[6,6,2,0],[7,3,3,3],[7,5,1,1],[8,2,2,2]]) (77,[[6,4,4,3],[6,5,4,0],[6,6,2,1],[8,3,2,0]]) (78,[[6,5,4,1],[7,4,3,2],[7,5,2,0],[8,3,2,1]]) (79,[[5,5,5,2],[6,5,3,3],[7,5,2,1]]) (80,[[6,6,2,2],[8,4,0,0]]) (81,[[6,5,4,2],[6,6,3,0],[7,4,4,0],[8,3,2,2],[8,4,1,0],[9,0,0,0]]) (82,[[5,5,4,4],[6,6,3,1],[7,4,4,1],[7,5,2,2],[8,3,3,0],[8,4,1,1],[9,1,0,0]]) (83,[[7,4,3,3],[7,5,3,0],[8,3,3,1],[9,1,1,0]]) (84,[[5,5,5,3],[6,4,4,4],[7,5,3,1],[8,4,2,0],[9,1,1,1]]) (85,[[6,6,3,2],[7,4,4,2],[7,6,0,0],[8,4,2,1],[9,2,0,0]]) (86,[[6,5,4,3],[6,5,5,0],[7,6,1,0],[8,3,3,2],[9,2,1,0]]) (87,[[6,5,5,1],[7,5,3,2],[7,6,1,1],[9,2,1,1]]) (88,[[6,6,4,0],[8,4,2,2]]) (89,[[6,6,4,1],[7,6,2,0],[8,4,3,0],[8,5,0,0],[9,2,2,0]]) (90,[[6,5,5,2],[6,6,3,3],[7,4,4,3],[7,5,4,0],[7,6,2,1],[8,4,3,1],[8,5,1,0],[9,2,2,1],[9,3,0,0]]) (91,[[5,5,5,4],[7,5,4,1],[8,3,3,3],[8,5,1,1],[9,3,1,0]]) (92,[[6,6,4,2],[7,5,3,3],[9,3,1,1]]) (93,[[6,5,4,4],[7,6,2,2],[8,4,3,2],[8,5,2,0],[9,2,2,2]]) (94,[[7,5,4,2],[7,6,3,0],[8,5,2,1],[9,3,2,0]]) (95,[[6,5,5,3],[7,6,3,1],[9,3,2,1]]) (96,[[8,4,4,0]]) (97,[[6,6,4,3],[6,6,5,0],[7,4,4,4],[8,4,4,1],[8,5,2,2],[9,4,0,0]]) (98,[[6,6,5,1],[7,6,3,2],[7,7,0,0],[8,4,3,3],[8,5,3,0],[9,3,2,2],[9,4,1,0]]) (99,[[7,5,4,3],[7,5,5,0],[7,7,1,0],[8,5,3,1],[9,3,3,0],[9,4,1,1]]) (100,[[5,5,5,5],[7,5,5,1],[7,7,1,1],[8,4,4,2],[8,6,0,0],[9,3,3,1],[10,0,0,0]]) (101,[[6,6,5,2],[7,6,4,0],[8,6,1,0],[9,4,2,0],[10,1,0,0]]) (102,[[6,5,5,4],[7,6,4,1],[7,7,2,0],[8,5,3,2],[8,6,1,1],[9,4,2,1],[10,1,1,0]]) (103,[[7,5,5,2],[7,6,3,3],[7,7,2,1],[9,3,3,2],[10,1,1,1]]) (104,[[6,6,4,4],[8,6,2,0],[10,2,0,0]]) (105,[[7,6,4,2],[8,4,4,3],[8,5,4,0],[8,6,2,1],[9,4,2,2],[10,2,1,0]]) (106,[[6,6,5,3],[7,5,4,4],[7,7,2,2],[8,5,4,1],[9,4,3,0],[9,5,0,0],[10,2,1,1]]) (107,[[7,7,3,0],[8,5,3,3],[9,4,3,1],[9,5,1,0]]) (108,[[6,6,6,0],[7,5,5,3],[7,7,3,1],[8,6,2,2],[9,3,3,3],[9,5,1,1],[10,2,2,0]]) (109,[[6,6,6,1],[8,5,4,2],[8,6,3,0],[10,2,2,1],[10,3,0,0]]) (110,[[7,6,4,3],[7,6,5,0],[8,6,3,1],[9,4,3,2],[9,5,2,0],[10,3,1,0]]) (111,[[6,5,5,5],[7,6,5,1],[7,7,3,2],[9,5,2,1],[10,3,1,1]]) (112,[[6,6,6,2],[8,4,4,4],[10,2,2,2]]) (113,[[6,6,5,4],[8,6,3,2],[8,7,0,0],[9,4,4,0],[10,3,2,0]]) (114,[[7,6,5,2],[7,7,4,0],[8,5,4,3],[8,5,5,0],[8,7,1,0],[9,4,4,1],[9,5,2,2],[10,3,2,1]]) (115,[[7,5,5,4],[7,7,4,1],[8,5,5,1],[8,7,1,1],[9,4,3,3],[9,5,3,0]]) (116,[[7,7,3,3],[8,6,4,0],[9,5,3,1],[10,4,0,0]]) (117,[[6,6,6,3],[7,6,4,4],[8,6,4,1],[8,7,2,0],[9,4,4,2],[9,6,0,0],[10,3,2,2],[10,4,1,0]]) (118,[[7,7,4,2],[8,5,5,2],[8,6,3,3],[8,7,2,1],[9,6,1,0],[10,3,3,0],[10,4,1,1]]) (119,[[7,6,5,3],[9,5,3,2],[9,6,1,1],[10,3,3,1]]) (120,[[8,6,4,2],[10,4,2,0]]) (121,[[7,6,6,0],[8,5,4,4],[8,7,2,2],[9,6,2,0],[10,4,2,1],[11,0,0,0]])