Glaisher's theorem

Short description: On the number of partitions of an integer into parts not divisible by another integer

In number theory, Glaisher's theorem is an identity useful to the study of integer partitions. Proved in 1883 by James Whitbread Lee Glaisher, it states that the number of partitions of an integer [math]\displaystyle{ n }[/math] into parts not divisible by [math]\displaystyle{ d }[/math] is equal to the number of partitions in which no part is repeated [math]\displaystyle{ d }[/math] or more times. This generalizes a result established in 1748 by Leonhard Euler for the case [math]\displaystyle{ d=2 }[/math].

Statement

It states that the number of partitions of an integer [math]\displaystyle{ n }[/math] into parts not divisible by [math]\displaystyle{ d }[/math] is equal to the number of partitions in which no part is repeated d or more times, which can be written formally as partitions of the form [math]\displaystyle{ n=\lambda_1+\cdots+\lambda_k }[/math] where [math]\displaystyle{ \lambda_i\geq \lambda_{i+1} }[/math] and [math]\displaystyle{ \lambda_i\geq \lambda_{i+d-1}+1 }[/math].

When [math]\displaystyle{ d=2 }[/math] this becomes the special case known as Euler's theorem, that the number of partitions of [math]\displaystyle{ n }[/math] into distinct parts is equal to the number of partitions of [math]\displaystyle{ n }[/math] into odd parts.

In the following examples, we use the multiplicity notation of partitions. For example, [math]\displaystyle{ 1^4 2^1 3^2 }[/math] is a notation for the partition 1 + 1 + 1 + 1 + 2 + 3 + 3.

Example for d=2 (Euler's theorem case)

Among the 15 partitions of the number 7, there are 5, shown in bold below, that contain only odd parts (i.e. only odd numbers):

[math]\displaystyle{ \mathbf{7}, 6^1 1^1, 5^1 2^1, \mathbf{5^1 1^2}, 4^1 3^1, 4^1 2^1 1^1, 4^1 1^3, \mathbf{3^2 1^1}, 3^1 2^2, 3^1 2^1 1^2, \mathbf{3^1 1^4}, 2^3 1^1, 2^2 1^3, 2^1 1^5, \mathbf{1^7} }[/math]

If we count now the partitions of 7 with distinct parts (i.e. where no number is repeated), we also obtain 5:

[math]\displaystyle{ \mathbf{7}, \mathbf{6^1 1^1}, \mathbf{5^1 2^1}, 5^1 1^2, \mathbf{4^1 3^1}, \mathbf{4^1 2^1 1^1}, 4^1 1^3, 3^2 1^1, 3^1 2^2, 3^1 2^1 1^2, 3^1 1^4, 2^3 1^1, 2^2 1^3, 2^1 1^5, 1^7 }[/math]

The partitions in bold in the first and second case are not the same, and it is not obvious why their number is the same.

Example for d=3

Among the 11 partitions of the number 6, there are 7, shown in bold below, that contain only parts not divisible by 3:

[math]\displaystyle{ 6, \mathbf{5^1 1^1}, \mathbf{4^1 2^1}, \mathbf{4^1 1^2}, 3^2, 3^1 2^1 1^1, 3^1 1^3, \mathbf{2^3}, \mathbf{2^2 1^2}, \mathbf{2^1 1^4}, \mathbf{1^6} }[/math]

And if we count the partitions of 6 with no part that repeats more than 2 times, we also obtain 7: [math]\displaystyle{ \mathbf{6}, \mathbf{5^1 1^1}, \mathbf{4^1 2^1}, \mathbf{4^1 1^2}, \mathbf{3^2}, \mathbf{3^1 2^1 1^1}, 3^1 1^3, 2^3, \mathbf{2^2 1^2}, 2^1 1^4, 1^6 }[/math]

Proof

A proof of the theorem can be obtained with generating functions. If we note [math]\displaystyle{ p_d(n) }[/math] the number of partitions with no parts divisible by d and [math]\displaystyle{ q_d(n) }[/math] the number of partitions with no parts repeated more than d-1 times, then the theorem means that for all n [math]\displaystyle{ p_d(n)=q_d(n) }[/math]. The uniqueness of ordinary generating functions implies that instead of proving that [math]\displaystyle{ p_d(n)=q_d(n) }[/math] for all n, it suffices to prove that the generating functions of [math]\displaystyle{ p_d(n) }[/math] and [math]\displaystyle{ q_d(n) }[/math] are equal, i.e. that [math]\displaystyle{ \sum_{n=0}^\infty p_d(n)x^n = \sum_{n=0}^\infty q_d(n)x^n }[/math].

Each generating function can be rewritten as infinite products (with a method similar to the infinite product of the partition function) :

[math]\displaystyle{ \sum_{n=0}^\infty p_d(n)x^n = \prod_{n=1, d \nmid n}^\infty\frac{1}{1-x^n} }[/math] (i.e. the product of terms where n is not divisible by d).

[math]\displaystyle{ \sum_{n=0}^\infty q_d(n)x^n = \prod_{n=1}^\infty\frac{1-x^{dn}}{1-x^n} }[/math]

If we expand the infinite product for [math]\displaystyle{ q_d(n) }[/math]:

[math]\displaystyle{ \prod_{n=1}^\infty\frac{1-x^{dn}}{1-x^n} =\frac{1-x^d}{1-x}\frac{1-x^{2d}}{1-x^2}\dots\frac{1-x^{kd}}{1-x^k}\dots }[/math]

we see that each term in the numerator cancels with the corresponding multiple of d in the denominator. What remains after canceling all the numerator terms is exactly the infinite product for [math]\displaystyle{ p_d(n) }[/math].

Hence the generating functions for [math]\displaystyle{ p_d(n) }[/math] and [math]\displaystyle{ q_d(n) }[/math] are equal.

Rogers-Ramanujan identities

If instead of counting the number of partitions with distinct parts we count the number of partitions with parts differing by at least 2, a further generalization is possible. It was first discovered by Leonard James Rogers in 1894, and then independently by Ramanujan in 1913 and Schur in 1917, in what are now known as the Rogers-Ramanujan identities. It states that:

1) The number of partitions whose parts differ by at least 2 is equal to the number of partitions involving only numbers congruent to 1 or 4 (mod 5).

2) The number of partitions whose parts differ by at least 2 and with the smallest part at least 2 is equal to the number of partitions involving only numbers congruent to 2 or 3 (mod 5).

Example 1

For example, there are only 3 partitions of 7, shown in bold below, into parts differing by at least 2 (note: if a number is repeated in a partition, it means a difference of 0 between two parts, hence the partition is not counted):

[math]\displaystyle{ \mathbf{7}, \mathbf{6^1 1^1}, \mathbf{5^1 2^1}, 5^1 1^2, 4^1 3^1, 4^1 2^1 1^1, 4^1 1^3, 3^2 1^1, 3^1 2^2, 3^1 2^1 1^2, 3^1 1^4, 2^3 1^1, 2^2 1^3, 2^1 1^5, 1^7 }[/math]

And there are also only 3 partitions of 7 involving only the parts 1, 4, 6:

[math]\displaystyle{ 7, \mathbf{6^1 1^1}, 5^1 2^1, 5^1 1^2, 4^1 3^1, 4^1 2^1 1^1, \mathbf{4^1 1^3}, 3^2 1^1, 3^1 2^2, 3^1 2^1 1^2, 3^1 1^4, 2^3 1^1, 2^2 1^3, 2^1 1^5, \mathbf{1^7} }[/math]

Example 2

For an example of the second statement of the Rogers-Ramanujan identities, we consider partitions of 7 with the further restriction of the smallest part at least 2, and there are only 2, shown in bold below:

[math]\displaystyle{ \mathbf{7}, 6^1 1^1, \mathbf{5^1 2^1}, 5^1 1^2, 4^1 3^1, 4^1 2^1 1^1, 4^1 1^3, 3^2 1^1, 3^1 2^2, 3^1 2^1 1^2, 3^1 1^4, 2^3 1^1, 2^2 1^3, 2^1 1^5, 1^7 }[/math]

And there are also only 2 partitions of 7 involving only the parts 2, 3, 7:

[math]\displaystyle{ \mathbf{7}, 6^1 1^1, 5^1 2^1, 5^1 1^2, 4^1 3^1, 4^1 2^1 1^1, 4^1 1^3, 3^2 1^1, \mathbf{3^1 2^2}, 3^1 2^1 1^2, 3^1 1^4, 2^3 1^1, 2^2 1^3, 2^1 1^5, 1^7 }[/math]

References

• D. H. Lehmer (1946). "Two nonexistence theorems on partitions". Bull. Amer. Math. Soc. 52 (6): 538–544. doi:10.1090/S0002-9904-1946-08605-X. http://projecteuclid.org/euclid.bams/1183509416.