INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A09

A COMBINATORIAL PROOF OF A RESULT FROM NUMBER THEORY

Shaun Cooper

Institute of Information and Mathematical Sciences, Massey University – Albany, Private Bag 102904,

North Shore Mail Centre, Auckland, New Zealand

                          s.cooper@massey.ac.nz

Michael Hirschhorn

School of Mathematics, UNSW, Sydney 2052, Australia

                        m.hirschhorn@unsw.edu.au

Received: 11/11/03, Accepted: 6/8/04, Published: 6/10/04

Abstract

Let r_{k}(n) denote the number of representations of n as a sum of k squares and t_{k}(n) the number of representations of n as a sum of k triangular numbers. We give an elementary, combinatorial proof of the relations

r_{k}(8n + k) = c_{k}t_{k}(n), 1 ≤ k ≤ 7,

where c_{1} = 2, c_{2} = 4, c_{3} = 8, c_{4} = 24, c_{5} = 112, c_{6} = 544 and c_{7} = 2368.

1. Introduction

Let r_{k}(n) denote the number of solutions in integers of the equation

x_{1}^{2} + x_{2}^{2} + ⋯ + x_{k}^{2} = n,

and let t_{k}(n) denote the number of solutions in non-negative integers of the equation

\frac{x_{1}(x_{1} + 1)}{2} + \frac{x_{2}(x_{2} + 1)}{2} + ⋯ + \frac{x_{k}(x_{k} + 1)}{2} = n.

For example,

9 = (±3)^{2} + 0^{2} + 0^{2} = 0^{2} + (±3)^{2} + 0^{2} = 0^{2} + 0^{2} + (±3)^{2}
= (±2)^{2} + (±2)^{2} + (±1)^{2} = (±2)^{2} + (±1)^{2} + (±2)^{2} = (±1)^{2} + (±2)^{2} + (±2)^{2},

Key words: sum of squares, sum of triangular numbers, combinatorial proof, bijective proof. 2000 Mathematics Subject Classification: Primary–11E25; Secondary–05A15

and so r_{3}(9) = 30. On the other hand, r_{3}(7) = 0. Also, t_{3}(10) = 9, because the solutions

of \frac{x_{1}(x_{1} + 1)}{2} + \frac{x_{2}(x_{2} + 1)}{2} + \frac{x_{3}(x_{3} + 1)}{2} = 10 in non-negative integers are (x_{1}, x_{2}, x_{3}) =

(4, 0, 0) (three possible permutations), and (3, 2, 1) (six possible permutations), giving a total of nine solutions.

Geometrically, r_{k}(n) counts the number of points with integer coordinates on the kdimensional sphere x_{1}^{2} + x_{2}^{2} + ⋯ + x_{k}^{2} = n. Similarly, 2^{k}t_{k}(n) counts the number of points with integer coordinates on the k-dimensional sphere (x_{1}+ \frac{1}{2})^{2}+(x_{2}+ \frac{1}{2})^{2}+⋯+(x_{k}+ \frac{1}{2})^{2} = 2n + \frac{k}{4}.

A great deal is known about r_{k}(n) and t_{k}(n). For example, generating functions which yield explicit formulas for r_{k}(n) and t_{k}(n) for k = 2, 4, 6 and 8 in terms of the divisors of n, were given by Jacobi [7, pp. 159–170]. On the other hand, explicit formulas for odd values of k are much more complicated. For both even and odd values of k ≥ 9, explicit formulas become even more complicated. For more information, see [4], [5, Chs. 6–9], [6, Ch. 20] and [8].

In [1], a remarkable connection between t_{k}(n) and r_{k}(8n + k) for 1 ≤ k ≤ 7 was observed. These relations were independently rediscovered in [3].

Theorem [1, Lemma 2.7], [3]. For any non-negative integer n,

r_{k}(8n + k) = 2^{k} (1 + \frac{k(k − 1)(k − 2)(k − 3)}{48}) t_{k}(n), 1 ≤ k ≤ 7.

□

Thus for 1 ≤ k ≤ 7, in order to study the sequence {t_{k}(n)}_{n≥0}, it suffices to study the subsequence {r_{k}(8n + k)}_{n≥0} of {r_{k}(n)}_{n≥0}.

The proof in [1] relies on Jacobi’s explicit formula for r_{4}(n) in terms of divisors of n. The proof in [3] uses generating functions, and depends on properties of theta functions. The purpose of this article is to give an elementary, combinatorial proof of this theorem.

2. Proofs

Lemma. Let

A_{n} = {(i, j, k, l) ∈ ℤ^{4} : i + j + k + l ≡ 0 (mod 2),
(2i + 1)^{2} + (2j + 1)^{2} + (2k + 1)^{2} + (2l + 1)^{2} = 8n + 4} ,

B_{n} = {(i, j, k, l) ∈ ℤ^{4} : i + j + k + l ≡ 1 (mod 2),
(2i + 1)^{2} + (2j + 1)^{2} + (2k + 1)^{2} + (2l + 1)^{2} = 8n + 4} ,
C_{n} = {(i, j, k, l) ∈ ℤ^{4} : (2i)^{2} + (2j)^{2} + (2k)^{2} + (2l)^{2} = 8n + 4} .

Then the sets A_{n}, B_{n} and C_{n} are equinumerous. Note that for the set C_{n}, the condition i + j + k + l ≡ 1 (mod 2) also holds.

Proof. Define f : A_{n} → B_{n} by

f(i, j, k, l) = (i, j, k, −l − 1).

Then f is readily seen to be a bijection, and so A_{n} and B_{n} are equinumerous. Similarly, define g : B_{n} → C_{n} by

g(i, j, k, l) = \frac{1}{2}(i + j + k − l + 1, i + j − k + l + 1, i − j + k + l + 1, −i + j + k + l + 1).

Then it may be easily verified that

g^{−1}(i, j, k, l) = \frac{1}{2}(i + j + k − l − 1, i + j − k + l − 1, i − j + k + l − 1, −i + j + k + l − 1),

and g is a bijection. Thus B_{n} and C_{n} are equinumerous. □

Corollary. The number of representations of 8n + 4 as a sum of four odd squares equals twice the number of representations of 8n + 4 as a sum of four even squares.

Proof of the Theorem. We will show that each representation of n as a sum of k triangular numbers gives rise to 2^{k} (1 + \frac{k(k−1)(k−2)(k−3)}{48}) representations of 8n + k as a sum of k squares, and that every representation of 8n + k as a sum of k squares arises once and only once in this way.

Suppose

n = \frac{x_{1}(x_{1} + 1)}{2} + ⋯ + \frac{x_{k}(x_{k} + 1)}{2}  (1)

is a representation of n as a sum of k triangular numbers. Then multiplying by 8 and completing the square gives

8n + k = (±(2x_{1} + 1))^{2} + ⋯ + (±(2x_{k} + 1))^{2}.  (2)

This gives rise to 2^{k} representations of 8n + k as a sum of k odd squares, because there are 2^{k} possibilities for the signs. Conversely, each of the 2^{k} representations in (2) arises only from the corresponding representation (1).

If 1 ≤ k ≤ 3, then the only way 8n + k may be expressed as a sum of k squares is if all the squares are odd, and so we have r_{k}(8n + k) = 2^{k}t_{k}(n) in this case.

If 4 ≤ k ≤ 7 and 8n + k is a sum of k squares, then parity considerations show that either all k squares are odd, or k − 4 are odd and 4 are even. In the first case, equation (2) gives 2^{k} representations of 8n + k as a sum of k odd squares for each instance of (1), and this accounts for all representations of 8n + k as a sum of k odd squares. In the

latter case, there are \binom{k}{4} orderings of x_{1}, ⋯, x_{k} by parity, in which four of the squares

are even and the others odd. Consider the equation

x_{1}^{2} + ⋯ + x_{k}^{2} = 8n + k  (3)

where x_{1}, x_{2}, x_{3} and x_{4} are even and the other x_{i}s are odd. The number of such representations is half the number of representations of 8n+k as a sum of k odd squares. To see this, rewrite (3) in the form

x_{1}^{2} + ⋯ + x_{4}^{2} = 8n + k − ∑_{j=5}^{k} x_{j}^{2},

and apply the corollary. It follows that the number of representations of 8n + k as a sum

of k squares, 4 of which are even, arising from the single representation (1) is \frac{1}{2}\binom{k}{4}2^{k}.

Combining the two cases we complete the proof of the Theorem. □

Remark. It is clear from this proof of the Theorem that extra complications will arise if k ≥ 8. In fact, using modular forms it was shown in [2] that for each value of k ≥ 8, r_{k}(8n + k)/t_{k}(n) is not a constant function of n. Therefore the Theorem does not hold if k ≥ 8.

References

[1] P. T. Bateman and M. I. Knopp, Some new old-fashioned modular identities, The Ramanujan Journal, 2 (1998), 247–269.

[2] P. T. Bateman, B. A. Datskovsky and M. I. Knopp, Sums of squares and the preservation of modularity under congruence restrictions, Symbolic computation, number theory, special functions, physics and combinatorics (Gainesville, FL, 1999), 59–71, Dev. Math., 4 Kluwer Acad. Publ., Dordrecht, 2001.

[3] P. Barrucand, S. Cooper and M. Hirschhorn, Relations between squares and triangles, Discrete Math., 248 (2002), 245–247.

[4] S. Cooper and M. Hirschhorn, On the number of primitive representations of integers as sums of squares, The Ramanujan Journal, to appear.

[5] L. E. Dickson, History of the theory of numbers, Vol. 2, Chelsea, New York, 1952.

[6] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth edition, Oxford, reprinted 1989.

[7] C. G. J. Jacobi, Fundamenta Nova Theoriae Functionum Ellipticarum, 1829. Reprinted in C. G. J. Jacobi’s Gesammelte Werke, B. 1, 49–239, (ed. K. Weierstrass), 1881; Second edition published by Chelsea, New York, 1969.

[8] S. C. Milne, Infinite families of exact sums of squares formulas, Jacobi elliptic functions, continued fractions, and Schur functions, The Ramanujan Journal, 6 No. 1 (2002), 7–149.