×

A group theoretic approach to a famous partition formula. (English) Zbl 1138.11342

From the text: The purpose of this paper is to describe a new way of thinking about a famous partition formula. The formula in question is this one:
\[ np(n)= \sum_{i=0}^{n-1} \sigma(n-i)p(i), \tag{1} \]
where \(\sigma(n)\) denotes the sum of the divisors of \(n\). This recurrence relation is remarkable in combining functions from both multiplicative and additive number theory. It is also of some historical importance, since P. Erdős based his elementary proof of the asymptotic formula for \(p(n)\) on this result [Ann. Math. (2) 43, 437–450 (1942; Zbl 0061.07905)]. E. Grosswald gave two elegant classical proofs of formula (1) in his book on number theory [Topics from the theory of numbers. 2nd ed. Boston-Basel-Stuttgart: Birkhäuser (1984; Zbl 0532.10001), pp. 109–137]. One proof uses generating functions, and the other is combinatorial. We present a new proof that takes a group-theoretic approach. Instead of counting partitions, we count subgroups and permutation representations of the free abelian group \(\mathbb Z\times\mathbb Z\). This group is, of course, isomorphic to the Gaussian integers under addition. We see that the sum of divisors function appears when counting sublattices of the integer lattice, and the partition function enters when we count permutation representations.
We prove the following:
Lemma 1. The number of subgroups of \(\mathbb Z\times\mathbb Z\) having index \(n\) is \(\sigma(n)\).
Lemma 2. The number of permutation representations of \(\mathbb Z\times\mathbb Z\) on \(n\) symbols is \(n!\) \(p(n)\).
We are now prepared to prove the famous partition relation:
Theorem. Let \(p(n)\) denote the number of unrestricted partitions of \(n\), and let \(\sigma(n)\) denote the sum of the divisors of \(n\). Then \(np(n)= \sum_{i=1}^n p(n-i)\sigma(i)\).

MSC:

11P81 Elementary theory of partitions
20D60 Arithmetic and combinatorial problems involving abstract finite groups
05A17 Combinatorial aspects of partitions of integers
PDFBibTeX XMLCite
Full Text: DOI