Pentagonal number theorem

Pentagonal number theorem In mathematics, the pentagonal number theorem, originally due to Euler, relates the product and series representations of the Euler function. It states that {displaystyle prod _{n=1}^{infty }left(1-x^{n}right)=sum _{k=-infty }^{infty }left(-1right)^{k}x^{kleft(3k-1right)/2}=1+sum _{k=1}^{infty }(-1)^{k}left(x^{k(3k+1)/2}+x^{k(3k-1)/2}right).} In other words, {displaystyle (1-x)(1-x^{2})(1-x^{3})cdots =1-x-x^{2}+x^{5}+x^{7}-x^{12}-x^{15}+x^{22}+x^{26}-cdots .} The exponents 1, 2, 5, 7, 12, ... on the right hand side are given by the formula gk = k(3k − 1)/2 for k = 1, −1, 2, −2, 3, ... and are called (generalized) pentagonal numbers (sequence A001318 in the OEIS). (The constant term 1 corresponds to {displaystyle k=0} .) This holds as an identity of convergent power series for {displaystyle |x|<1} , and also as an identity of formal power series. A striking feature of this formula is the amount of cancellation in the expansion of the product. Contents 1 Relation with partitions 2 Franklin's bijective proof 3 Partition recurrence 4 See also 5 References 6 External links Relation with partitions The identity implies a recurrence for calculating {displaystyle p(n)} , the number of partitions of n: {displaystyle p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+cdots } or more formally, {displaystyle p(n)=sum _{kneq 0}(-1)^{k-1}p(n-g_{k})} where the summation is over all nonzero integers k (positive and negative) and {displaystyle g_{k}} is the kth generalized pentagonal number. Since {displaystyle p(n)=0} for all {displaystyle n<0} , the apparently infinite series on the right has only finitely many non-zero terms, enabling an efficient calculation of p(n). Franklin's bijective proof The theorem can be interpreted combinatorially in terms of partitions. In particular, the left hand side is a generating function for the number of partitions of n into an even number of distinct parts minus the number of partitions of n into an odd number of distinct parts. Each partition of n into an even number of distinct parts contributes +1 to the coefficient of xn; each partition into an odd number of distinct parts contributes −1. (The article on unrestricted partition functions discusses this type of generating function.) For example, the coefficient of x5 is +1 because there are 2 ways to split 5 into an even number of distinct parts (4+1, 3+2), and 1 way into an odd number of distinct parts (the one-part partition 5), so +2–1 = +1. However, the coefficient of x12 is −1 because there are 7 ways to partition 12 into an even number of distinct parts, and 8 ways into an odd number of distinct parts, so 7–8 = –1. This interpretation leads to a proof of the identity by canceling pairs of matched terms (involution method).[1] Consider the Ferrers diagram of any partition of n into distinct parts. For example, the diagram below shows n = 20 and the partition 20 = 7 + 6 + 4 + 3. Let m be the number of elements in the smallest row of the diagram (m = 3 in the above example). Let s be the number of elements in the rightmost 45 degree line of the diagram (s = 2 dots in red above, since 7−1 = 6, but 6−1 > 4). If m > s, take the rightmost 45-degree line and move it to form a new row, as in the matching diagram below.

If m ≤ s (as in our newly formed diagram where m = 2, s = 5) we may reverse the process by moving the bottom row to form a new 45 degree line (adding 1 element to each of the first m rows), taking us back to the first diagram.

A bit of thought shows that this process always changes the parity of the number of rows, and applying the process twice brings us back to the original diagram. This enables us to pair off Ferrers diagrams contributing 1 and −1 to the xn term of the series, resulting in a net coefficient of 0 for xn. This holds for every term except when the process cannot be performed on every Ferrers diagram with n dots. There are two such cases: 1) m = s and the rightmost diagonal and bottom row meet. For example, Attempting to perform the operation would lead us to: which fails to change the parity of the number of rows, and is not reversible in the sense that performing the operation again does not take us back to the original diagram. If there are m elements in the last row of the original diagram, then {displaystyle n=m+(m+1)+(m+2)+cdots +(2m-1)={frac {m(3m-1)}{2}}={frac {k(3k-1)}{2}}} where the new index k is taken to equal m. Note that the sign associated with this partition is (−1)s, which by construction equals (−1)m and (−1)k.

2) m = s+1 and the rightmost diagonal and bottom row meet. For example, Our operation requires us to move the right diagonal to the bottom row, but that would lead to two rows of three elements, forbidden since we're counting partitions into distinct parts. This is the previous case but with one fewer row, so {displaystyle n=m+(m+1)+(m+2)+cdots +(2m-2)={frac {(m-1)(3m-2)}{2}}={frac {k(3k-1)}{2}},} where we take k = m−1. Here the associated sign is (−1)s with s = m−1 = k, therefore the sign is again (−1)k.

In summary, it has been shown that partitions into an even number of distinct parts and an odd number of distinct parts exactly cancel each other, producing null terms 0xn, except if n is a generalized pentagonal number {displaystyle n=g_{k}=k(3k-1)/2} , in which case there is exactly one Ferrers diagram left over, producing a term (−1)kxn. But this is precisely what the right side of the identity says should happen, so we are finished.

Partition recurrence We can rephrase the above proof, using partitions, which we denote as: {displaystyle n=lambda _{1}+lambda _{2}+dotsb +lambda _{ell }} , where {displaystyle lambda _{1}geq lambda _{2}geq ldots geq lambda _{ell }>0} . The number of partitions of n is the partition function p(n) having generating function: {displaystyle sum _{n=0}^{infty }p(n)x^{n}=prod _{k=1}^{infty }(1-x^{k})^{-1}} Note that is the reciprocal of the product on the left hand side of our identity: {displaystyle left(sum _{n=0}^{infty }p(n)x^{n}right)cdot left(prod _{n=1}^{infty }(1-x^{n})right)=1} Let us denote the expansion of our product by {displaystyle prod _{n=1}^{infty }(1-x^{n})=sum _{n=0}^{infty }a_{n}x^{n}} , so that {displaystyle left(sum _{n=0}^{infty }p(n)x^{n}right)cdot left(sum _{n=0}^{infty }a_{n}x^{n}right)=1} .

Multiplying out the left hand side and equating coefficients on the two sides, we obtain a0 p(0) = 1 and {displaystyle sum _{i=0}^{n}p(n{-}i)a_{i}=0} for all {displaystyle ngeq 1} . This gives a recurrence relation defining p(n) in terms of an, and vice versa a recurrence for an in terms of p(n). Thus, our desired result: {displaystyle a_{i}:={begin{cases}1&{mbox{ if }}i={frac {1}{2}}(3k^{2}pm k){mbox{ and }}k{mbox{ is even}}\-1&{mbox{ if }}i={frac {1}{2}}(3k^{2}pm k){mbox{ and }}k{mbox{ is odd }}\0&{mbox{ otherwise }}end{cases}}} for {displaystyle igeq 1} is equivalent to the identity {displaystyle sum _{i}(-1)^{i}p(n{-}g_{i})=0,} where {displaystyle g_{i}:=textstyle {frac {1}{2}}(3i^{2}-i)} and i ranges over all integers such that {displaystyle g_{i}leq n} (this range includes both positive and negative i, so as to use both kinds of generalized pentagonal numbers). This in turn means: {displaystyle sum _{imathrm { even} }p(n{-}g_{i})=sum _{imathrm { odd} }p(n{-}g_{i}),} .

In terms of sets of partitions, this is equivalent to saying that the following sets are of equal cardinality: {displaystyle {mathcal {X}}:=bigcup _{imathrm { even} }{mathcal {P}}(n-g_{i})}         and         {displaystyle {mathcal {Y}}:=bigcup _{imathrm { odd} }{mathcal {P}}(n-g_{i})} , where {displaystyle {mathcal {P}}(n)} denotes the set of all partitions of {displaystyle n} . All that remains is to give a bijection from one set to the other, which is accomplished by the function φ from X to Y which maps the partition {displaystyle {mathcal {P}}(n-g_{i})ni lambda :n-g_{i}=lambda _{1}+lambda _{2}+dotsb +lambda _{ell }} to the partition {displaystyle lambda '=varphi (lambda )} defined by: {displaystyle varphi (lambda ):={begin{cases}lambda ':n-g_{i-1}=(ell +3i-2)+(lambda _{1}-1)+dotsb +(lambda _{ell }-1)&{mbox{ if }}ell +3i>lambda _{1}\\lambda ':n-g_{i+1}=(lambda _{2}+1)+dotsb +(lambda _{ell }+1)+underbrace {1+dotsb +1} _{lambda _{1}-ell -3i}&{mbox{ if }}ell +3ileq lambda _{1}.end{cases}}} This is an involution (a self-inverse mapping), and thus in particular a bijection, which proves our claim and the identity.

See also The pentagonal number theorem occurs as a special case of the Jacobi triple product.

Q-series generalize Euler's function, which is closely related to the Dedekind eta function, and occurs in the study of modular forms. The modulus of the Euler function (see there for picture) shows the fractal modular group symmetry and occurs in the study of the interior of the Mandelbrot set.

References ^ Franklin, F. (1881). "Sur le developpement du produit (1-x)(1-x^2)(1-x^3) ...". Contes Rendues Acad. Paris Ser A. 92: 448–450. Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929, Zbl 0335.10001 Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001. External links Jordan Bell (2005). "Euler and the pentagonal number theorem". arXiv:math.HO/0510054. On Euler's Pentagonal Theorem at MathPages OEIS sequence A000041 (a(n) = number of partitions of n (the partition numbers)) De mirabilis proprietatibus numerorum pentagonalium at Scholarly Commons. Categories: Theorems in number theoryInteger partitions