For each positive integer n, S(n) is defined as the greatest integer such that for every positive integer k ≤ S(n), n2 can be written as the sum of k positive squares.
(a) Prove that S(n) <= n2 - 14 for each n ≥ 4.
(b) Find an integer n such that S(n) = n2 - 14.
(c) Prove that there are infinitely many integers n such that S(n) = n2 - 14.
Solution
(a) Let N = n2. Suppose we could express N as a sum of N - 13 squares. Let the number of 4s be a, the number of 9s be b and so on. Then we have 13 = 3a + 8b + 15c + ... . Hence c, d, ... must all be zero. But neither 13 nor 8 is a multiple of 3, so there are no solutions. Hence S(n) ≤ N - 14.
A little experimentation shows that the problem is getting started. Most squares cannot be expressed as a sum of two squares. For N = 132 = 169, we find: 169 = 9 + 4 + 4 + 152 1s, a sum of 155 = N - 14 squares. By grouping four 1s into a 4 repeatedly, we obtain all multiples of 3 plus 2 down to 41 (169 = 9 + 40 4s). Then grouping four 4s into a 16 gives us 38, 35, ... , 11 (169 = 10 16s + 9). Grouping four 16s into a 64 gives us 8 and 5. We obtain the last number congruent to 2 mod 3 by the decomposition: 169 = 122 + 52.
For the numbers congruent to 1 mod 3, we start with N - 15 = 154 squares: 169 = 5 4s + 149 1s. Grouping as before gives us all 3m + 1 down to 7: 169 = 64 + 64 + 16 + 16 + 4 + 4 + 1. We may use 169 = 102 + 82 + 22 + 12 for 4.
For multiples of 3, we start with N - 16 = 153 squares: 169 = 9 + 9 + 151 1s. Grouping as before gives us all multiples of 3 down to 9: 169 = 64 + 64 + 16 + 9 + 9 + 4 + 1 + 1 + 1. Finally, we may take 169 = 122 + 42 + 32 for 3 and split the 42 to get 169 = 122 + 32 + 22 + 22 + 22 + 22 for 6. That completes the demonstration that we can write 132 as a sum of k positive squares for all k <= S(13) = 132 - 14.
We now show how to use the expressions for 132 to derive further N. For any N, the grouping technique gives us the high k. Simply grouping 1s into 4s takes us down: from 9 + 4 + 4 + (N-17) 1s to (N-14)/4 + 6 < N/2 or below; from 4 + 4 + 4 + 4 + 4 + (N-20) 1s to (N-23)/4 + 8 < N/2 or below; from 9 + 9 + (N-18) 1s to (N-21)/4 + 5 < N/2 or below. So we can certainly get all k in the range (N/2 to N-14) by this approach. Now suppose that we already have a complete set of expressions for N1 and for N2 (where we may have N1 = N2). Consider N3 = N1N2. Writing N3 = N1( an expression for N2 as a sum of k squares) gives N3 as a sum of 1 thru k2 squares, where k2 = N2 - 14 squares (since N1 is a square). Now express N1 as a sum of two squares: n12 + n22. We have N3 = n12(a sum of k2 squares) + n22(a sum of k squares). This gives N3 as a sum of k2 + 1 thru 2k2 squares. Continuing in this way gives N3 as a sum of 1 thru k1k2 squares. But ki = Ni - 14 > 2/3 Ni, so k1k2 > N3/2. So when combined with the top down grouping we get a complete set of expressions for N3.
This shows that there are infinitely many squares N with a complete set of expressions, for example we may take N = the squares of 13, 132, 133, ... .
Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
21 Oct 1998