Franklin’s argument proves an identity of Zagier

Robin Chapman

School of Mathematical Sciences, University of Exeter, Exeter, EX4 4QE, UK

                              rjc@maths.ex.ac.uk

Submitted: September 28, 2000; Accepted: November 9, 2000

Abstract Recently Zagier proved a remarkable q-series identity. We show that this identity can also be proved by modifying Franklin’s classical proof of Euler’s pentagonal number theorem.

Mathematics Subject Classification (2000): 05A17 11P81

1 Introduction

We use the standard q-series notation:

(a)_{n} = ∏_{k=1}^{n}(1 − aq^{k−1})

where n is a nonnegative integer or n = ∞. Euler’s pentagonal number theorem states that

(q)_{∞} = 1 + ∑_{r=1}^{∞}(−1)^{r}(q^{r(3r−1)/2} + q^{r(3r+1)/2}).  (1)

Recently Zagier proved the following remarkable identity

Theorem 1

∑_{n=0}^{∞}[(q)_{∞} − (q)_{n}] = (q)_{∞} ∑_{k=1}^{∞} \frac{q^{k}}{1 − q^{k}} + ∑_{r=1}^{∞}(−1)^{r}[(3r − 1)q^{r(3r−1)/2} + 3rq^{r(3r+1)/2}]. (2)

This is [8, Theorem 2] slightly rephrased.

Equation (1) has a combinatorial interpretation. The coefficient of q^{N} in (q)_{∞} equals d_{e}(N) − d_{o}(N) where d_{e}(N) (respectively d_{o}(N)) is the number of partitions of N into an even (respectively odd) number of distinct parts. Franklin [4] showed that

d_{e}(N) − d_{o}(N) = \{ \begin{matrix}(−1)^{r} & if N = \frac{1}{2}r(3r ± 1) for a positive integer r, \\ 0 & otherwise. \end{matrix}

His proof was combinatorial. He set up what was almost an involution on the set of partitions of N into distinct parts. This “involution” reverses the parity of the number of parts. However there are certain partitions for which his map is not defined. These exceptional partitions occur precisely when N = \frac{1}{2}r(3r ± 1), and so account for the nonzero terms on the right of (1). Franklin’s argument has appeared in numerous textbooks, notably [1, §1.3] and [5, §19.11].

We show that Zagier’s identity has a similar combinatorial interpretation, which, miraculously, Franklin’s argument proves at once.

The author wishes to thank George Andrews and Don Zagier for supplying him with copies of [3] and [8], and also an anonymous referee for helpful comments.

2 Proof of Theorem 1

We begin by recalling Franklin’s “involution”. Let D_{N} denote the set of partitions of N into distinct parts and let D = ⋃_{N=0}^{∞} D_{N}. For λ ∈ D_{N} let N_{λ} = N, n_{λ} be the number of parts in λ and m_{λ} be the largest part of λ (if λ is the empty partition of 0 let m_{λ} = 0). Then

(q)_{∞} = ∑_{λ∈D}(−1)^{n_{λ}}q^{N_{λ}}.  (3)

Let λ be a non-empty partition in D. Denote its smallest part by a_{λ}. If the parts of λ are λ_{1} > λ_{2} > λ_{3} > ⋯ let b = b_{λ} denote the largest b such that λ_{b} = λ_{1} + 1 − b (so that λ_{k} = λ_{1} + 1 − k if and only if 1 ≤ k ≤ b). If λ ∈ D is not exceptional (we shall explain this term shortly), then we define a new partition λ′ as follows. If a_{λ} ≤ b_{λ} we obtain λ′ by removing the smallest part from λ and then adding 1 to the largest a_{λ} parts of this new partition. If a_{λ} > b_{λ} we obtain λ′ by subtracting 1 from the b_{λ} largest parts of λ and then appending a new part b_{λ} to this new partition.

For example take the partition λ illustrated in Figure 1.

[figure]

Figure 1: the partition λ

Then a_{λ} = 2 and b_{λ} = 3. As a_{λ} ≤ b_{λ} then λ′ is obtained by removing the smallest part of λ and adding 1 to its largest two parts. We get the partition λ′ illustrated in Figure 2. This time a_{λ′} = 3 and b_{λ′} = 2, and we obtain λ′′ by subtracting 1 from the

[figure]

Figure 2: the partition λ′

two largest parts of λ′, and creating a new smallest part of 2. This operation reverses the construction of λ′ from λ, and so λ′′ = λ.

The exceptional partitions are those for which this procedure breaks down. We regard the empty partition as exceptional, also we regard those for which n_{λ} = b_{λ} and a_{λ} = b_{λ} or b_{λ}+1. If λ is not exceptional, then neither is λ′ and λ′′ = λ and (−1)^{n_{λ′}} = −(−1)^{n_{λ}}. Thus on the right side of (3) the contributions from non-exceptional partitions cancel. The non-empty exceptional partitions are of two forms: for each positive integer r we have λ = (2r − 1, 2r − 2, …, r + 1, r) for which n_{λ} = r, m_{λ} = 2r − 1 and N_{λ} = \frac{1}{2}r(3r − 1), and we have λ = (2r, 2r −1, …, r +2, r +1) for which n_{λ} = r, m_{λ} = 2r and N_{λ} = \frac{1}{2}r(3r +1). Thus from (3) we deduce (1).

If λ ∈ D is non-exceptional, then either n_{λ′} = n_{λ} − 1, in which case m_{λ′} = m_{λ} + 1, or n_{λ} = n_{λ} + 1, in which case m_{λ′} = m_{λ} − 1. In each case m_{λ′} + n_{λ′} = m_{λ} + n_{λ}. It follows that in the sum

∑_{λ∈D}(−1)^{n_{λ}}(m_{λ} + n_{λ})q^{N_{λ}}

the terms corresponding to non-exceptional λ cancel and so we get only the contribution from exceptional λ. Thus

∑_{λ∈D}(−1)^{n_{λ}}(m_{λ} + n_{λ})q^{N_{λ}} = ∑_{r=1}^{∞}(−1)^{r}[(3r − 1)q^{r(3r−1)/2} + 3rq^{r(3r+1)/2}].  (4)

This sum occurs in (2), which will follow by analysing the left side of (4).

We break this into two sums. The first

∑_{λ∈D}(−1)^{n_{λ}}m_{λ}q^{N_{λ}}

is dealt with in [3, Theorem 5.2]. We repeat their argument. The coefficient of q^{N} in (q)_{∞} − (q)_{n} is the sum of (−1)^{n_{λ}} over all λ ∈ D_{N} having a part strictly greater than n. Such a λ is counted for exactly m_{λ} different n so that

∑_{n=0}^{∞}[(q)_{∞} − (q)_{n}] = ∑_{λ∈D}(−1)^{n_{λ}}m_{λ}q^{N_{λ}}.  (5)

For each positive integer k,

\frac{−q^{k}}{1 − q^{k}} (q)_{∞} = (1 − q)(1 − q^{2}) ⋯ (1 − q^{k−1})(−q^{k})(1 − q^{k+1}) · · · .

The coefficient of q^{N} in this product is the sum of (−1)^{n_{λ}} over all λ ∈ D_{N} having k as a part. Such a λ occurs for n_{λ} distinct k, and summing we conclude that

−(q)_{∞} ∑_{k=1}^{∞} \frac{q^{k}}{1 − q^{k}} = ∑_{λ∈D}(−1)^{n_{λ}}n_{λ}q^{N_{λ}}.  (6)

Combining (4), (5) and (6) gives (2).

3 Another identity

Subbararo [7] (see also [2, 6]) has used essentially the above argument to prove a related identity. As before Franklin’s involution proves that

∑_{λ∈D}(−1)^{n_{λ}}x^{m_{λ}+n_{λ}}q^{N_{λ}} = 1 + ∑_{r=1}^{∞}(−1)^{r}[x^{3r−1}q^{r(3r−1)/2} + x^{3r}q^{r(3r+1)/2}].  (7)

By elementary combinatorial considerations the left side of (7) can be shown to equal

∑_{r=0}^{∞}(x)_{r+1}x^{r}

and so

∑_{r=0}^{∞}(x)_{r+1}x^{r} = 1 + ∑_{r=1}^{∞}(−1)^{r}[x^{3r−1}q^{r(3r−1)/2} + x^{3r}q^{r(3r+1)/2}].  (8)

For details see [2, 6, 7]. An alternative method of proving (8) is outlined in [1] and presented in more detail in [8]. Zagier [8] deduces (2) from (8), essentially by carefully differentiating with respect to x and setting x = 1.

References

[1] G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976 (reprinted Cambridge University Press, 1998).

[2] G. E. Andrews, ‘Two theorems of Gauss and allied identities proved arithmetically’, Pacific J. Math., 41 (1972), 563–578.

[3] G. E. Andrews, J. Jiménez-Urroz, & K. Ono. ‘Bizarre q-series identities and values of certain L-functions’, preprint.

[4] F. Franklin, ‘Sur le développement du produit infini (1−x)(1−x^{2})(1−x^{3})(1−x^{4}) …’, C. R. Acad. Sci. Paris, 92 (1881), 448–450.

[5] G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers (5th ed.), Oxford University Press, 1979.

[6] D. E. Knuth & M. S. Paterson, ‘Identities from partition involutions’, Fibonacci Quart, 16 (1978), 198–212.

[7] M. V. Subbarao, ‘Combinatorial proofs of some identities,’ Proceedings of the Washington State University Conference on Number Theory 80–91, Washington State Univ., 1971.

[8] D. Zagier, ‘Vassiliev invariants and a strange identity related to the Dedekind etafunction’, Topology, to appear.