STACKED LATTICE BOXES AND THEOREMS OF LIOUVILLE, BELL AND MACMAHON

by George E. Andrews

This is a brief summary of the work presented in [1] together with some comments about more recent work.

Arithmetically we are considering L_{k}(n), the number of solutions of

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

in positive integers x_{i}. In the mid-nineteenth century, Liouville developed a mysterious method for studying such problems. I say “mysterious” because he stated all his central theorems without proof. However numerous mathematicians (most notably Humbert, Pepin and Bell) managed to find proofs of the Liouville Theorems. The theorems apparently have their genesis in the theory of elliptic functions (as Humbert [6] observed); however, Pepin [9] was able to develop elementary methods to prove many of Liouville’s results.

According to Bell [4], the last result of Liouville [7] to be proved was equivalent to the assertion that

(2)  L_{4}(n) = D_{2}(n) − n D_{0}(n) − D_{0,0}(n) ,

where

(3)  D_{i_{1}i_{2}...i_{r}}(n) = ∑_{\begin{matrix}j_{1}+j_{2}+···+j_{r}=n \\ j_{1},...,j_{r}≧1 \end{matrix}} D_{i_{1}}(j_{1})D_{i_{2}}(j_{2}) ⋯ D_{i_{r}}(j_{r}) ,

Typeset by AMS-TEX

and

(4)  D_{i}(n) = ∑_{j|n} j^{i} .

The phrase “stacked lattice boxes” derives from the fact that a solution of (1) may be viewed as yielding n as the area of the following figure

Figure 1  x_{1}{ x_{3}{  x_{5}{ _{x_{2}}  _{x_{6}} _{x_{4}}

In addition to (2), Liouville’s “last” theorem, one can derive fairly easily (with a little help from MacMahon [8]), that

(5)  L_{1}(n) = D_{0}(n)
(6)  L_{2}(n) = D_{1}(n) − D_{0}(n)
(7)  L_{3}(n) = \frac{1}{2}D_{0,0}(n) + \frac{1}{2}D_{0}(n) − \frac{1}{2}D_{1}(n) .

Our approach to these questions is to use q-series extensively following the ideas of W. N. Bailey [3]. This allows us to prove

L_{5}(n) = \frac{1}{6}D_{0,0,0}(n) + D_{0,0}(n) + \frac{1}{2}D_{0,1}(n)

(2n − \frac{1}{6}) D_{0}(n) − \frac{11}{6}D_{2}(n) . (8)

These discoveries dovetail interestingly with the study (begin in [2]) of the qseries:

(9)  M_{k}(q) = ∑_{n=1}^{∞} \frac{(−1)^{n−1}q^{\binom{n+1}{2}}}{(1 − q)(1 − q^{2}) ⋯ (1 − q^{n−1})(1 − q^{n})^{k+1}} .

Let us denote the generating function for L_{k}(n) by L_{k}(q).

Using the methods of [2], we can show that

(10)  M_{1}(q) = L_{1}(q)
(11)  M_{2}(q) = L_{1}(q) + L_{2}(q) + L_{3}(q) ,

and

(12)  M_{3}(q) = L_{1}(q) + 2L_{2}(q) + 3L_{3}(q) + 2L_{4}(q) + L_{5}(q) .

The table of coefficients in these identities, namely

1 1 1 1 1 2 3 2 1

suggests the trinomial coefficients [5; p. 78]. However if we examine the next suggested identity we find instead

M_{4}(q) =L_{1}(q) + 3L_{2}(q) + 6L_{3}(q) + 7L_{4}(q)
+ 6L_{5}(q) + 3L_{6}(q) + L_{7}(q)

− (q^{7} + 2q^{8} + 6q^{9} + 11q^{10} + 22q^{11} + 33q^{12} + 57q^{13} + …) (13)

So having surveyed the world of the mysterious Liouville identities, we are led to a new “Liouville mystery.”

References

1. G. E. Andrews, Stacked lattice boxes, Annals of combinatorics, (to appear).

2. G. E. Andrews, D. Crippa, K. Simon, q-Series arising from the study of random graphs, S.I.A.M. J. Discr. Math. 10 (1997), 41–56.

3. W. N. Bailey, An algebraic identity, J. London Math. Soc. 11 (1936), 156–160.

4. E. T. Bell, The form wx + xy + yz + zu, Bull. Amer. Math. Soc. 42 (1936), 377–380.

5. L. Comtet, Advanced Combinatorics, Reidel, Dordrecht, 1974.

6. G. Humbert, Démonstration analytique d’une formule de Liouville, Bull. des Sc. Math (2) 34 (1910), 29–31.

7. J. Liouville, x_{1}x_{2} + x_{2}x_{3} + x_{3}x_{4} + x_{4}x_{5}, Comptes Rendus, 62 (1866), 714 and Journal de Math ematiques (2), 12 (1867), 47–48.

8. P. A. MacMahon, Divisors of numbers and their continuations in the theory of partitions, Proc. London Math. Soc., (1919), 75–113 (Reprinted: The Collected Papers of P. A. MacMahon, Vol. II, G. E. Andrews ed., M.I.T. Press, Cambridge, 198.

9. T. Pepin, Sur quelques formules d’Analyse utiles dans la The’orie des nombres, J. de Math. Pures et Appl. 4 (1888), 83–127.