Pentagonal number theorem

Last updated

In mathematics, Euler's pentagonal number theorem relates the product and series representations of the Euler function. It states that

Contents

In other words,

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 .) This holds as an identity of convergent power series for , 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.

Relation with partitions

The identity implies a recurrence for calculating , the number of partitions of n:

or more formally,

where the summation is over all nonzero integers k (positive and negative) and is the kth generalized pentagonal number. Since for all , 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 two ways to split 5 into an even number of distinct parts (4 + 1 and 3 + 2), but only one way to do so for an odd number of distinct parts (the one-part partition 5). However, the coefficient of x12 is −1 because there are seven ways to partition 12 into an even number of distinct parts, but there are eight ways to partition 12 into an odd number of distinct parts, and 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.

GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg RedDot.svg
GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg RedDot.svg
GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg
GrayDot.svg GrayDot.svg GrayDot.svg

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.

GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg
GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg
GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg
GrayDot.svg GrayDot.svg GrayDot.svg
RedDot.svg RedDot.svg

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,

GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg
GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg
RedDot.svg RedDot.svg RedDot.svg

Attempting to perform the operation would lead us to:

GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg RedDot.svg
GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg RedDot.svg
RedDot.svg

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

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,

GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg RedDot.svg
GrayDot.svg GrayDot.svg GrayDot.svg GrayDot.svg RedDot.svg
GrayDot.svg GrayDot.svg GrayDot.svg RedDot.svg

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

where we take k = 1m (a negative integer). 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 , 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 integer partitions, which we denote as: , where . The number of partitions of n is the partition function p(n) having generating function:

Note that is the reciprocal of the product on the left hand side of our identity:

Let us denote the expansion of our product by so that

Multiplying out the left hand side and equating coefficients on the two sides, we obtain a0p(0) = 1 and for all . 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:

for is equivalent to the identity where and i ranges over all integers such that (this range includes both positive and negative i, so as to use both kinds of generalized pentagonal numbers). This in turn means:

In terms of sets of partitions, this is equivalent to saying that the following sets are of equal cardinality:

        and        

where denotes the set of all partitions of . 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 to the partition defined by:

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.

Related Research Articles

In number theory, an arithmetic, arithmetical, or number-theoretic function is generally any function f(n) whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n". There is a larger class of number-theoretic functions that do not fit this definition, for example, the prime-counting functions. This article provides links to functions of both classes.

<span class="mw-page-title-main">Discrete Fourier transform</span> Type of Fourier transform in discrete mathematics

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence. An inverse DFT (IDFT) is a Fourier series, using the DTFT samples as coefficients of complex sinusoids at the corresponding DTFT frequencies. It has the same sample-values as the original input sequence. The DFT is therefore said to be a frequency domain representation of the original input sequence. If the original sequence spans all the non-zero values of a function, its DTFT is continuous, and the DFT provides discrete samples of one cycle. If the original sequence is one cycle of a periodic function, the DFT provides all the non-zero values of one DTFT cycle.

In measure theory, a branch of mathematics, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of higher dimensional Euclidean n-spaces. For lower dimensions n = 1, 2, or 3, it coincides with the standard measure of length, area, or volume. In general, it is also called n-dimensional volume, n-volume, hypervolume, or simply volume. It is used throughout real analysis, in particular to define Lebesgue integration. Sets that can be assigned a Lebesgue measure are called Lebesgue-measurable; the measure of the Lebesgue-measurable set A is here denoted by λ(A).

<span class="mw-page-title-main">Integer partition</span> Decomposition of an integer as a sum of positive integers

In number theory and combinatorics, a partition of a non-negative integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. For example, 4 can be partitioned in five distinct ways:

<span class="mw-page-title-main">Partition function (number theory)</span> The number of partitions of an integer

In number theory, the partition functionp(n) represents the number of possible partitions of a non-negative integer n. For instance, p(4) = 5 because the integer 4 has the five partitions 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, and 4.

In mathematics, the spectral radius of a square matrix is the maximum of the absolute values of its eigenvalues. More generally, the spectral radius of a bounded linear operator is the supremum of the absolute values of the elements of its spectrum. The spectral radius is often denoted by ρ(·).

In mathematics, the Poisson summation formula is an equation that relates the Fourier series coefficients of the periodic summation of a function to values of the function's continuous Fourier transform. Consequently, the periodic summation of a function is completely defined by discrete samples of the original function's Fourier transform. And conversely, the periodic summation of a function's Fourier transform is completely defined by discrete samples of the original function. The Poisson summation formula was discovered by Siméon Denis Poisson and is sometimes called Poisson resummation.

In mathematics, a Young tableau is a combinatorial object useful in representation theory and Schubert calculus. It provides a convenient way to describe the group representations of the symmetric and general linear groups and to study their properties. Young tableaux were introduced by Alfred Young, a mathematician at Cambridge University, in 1900. They were then applied to the study of the symmetric group by Georg Frobenius in 1903. Their theory was further developed by many mathematicians, including Percy MacMahon, W. V. D. Hodge, G. de B. Robinson, Gian-Carlo Rota, Alain Lascoux, Marcel-Paul Schützenberger and Richard P. Stanley.

<span class="mw-page-title-main">Lambert series</span> Mathematical term

In mathematics, a Lambert series, named for Johann Heinrich Lambert, is a series taking the form

In mathematics, Schur polynomials, named after Issai Schur, are certain symmetric polynomials in n variables, indexed by partitions, that generalize the elementary symmetric polynomials and the complete homogeneous symmetric polynomials. In representation theory they are the characters of polynomial irreducible representations of the general linear groups. The Schur polynomials form a linear basis for the space of all symmetric polynomials. Any product of Schur polynomials can be written as a linear combination of Schur polynomials with non-negative integral coefficients; the values of these coefficients is given combinatorially by the Littlewood–Richardson rule. More generally, skew Schur polynomials are associated with pairs of partitions and have similar properties to Schur polynomials.

In queueing theory, a discipline within the mathematical theory of probability, a Jackson network is a class of queueing network where the equilibrium distribution is particularly simple to compute as the network has a product-form solution. It was the first significant development in the theory of networks of queues, and generalising and applying the ideas of the theorem to search for similar product-form solutions in other networks has been the subject of much research, including ideas used in the development of the Internet. The networks were first identified by James R. Jackson and his paper was re-printed in the journal Management Science’s ‘Ten Most Influential Titles of Management Sciences First Fifty Years.’

In mathematics, a Brauer algebra is an associative algebra introduced by Richard Brauer in the context of the representation theory of the orthogonal group. It plays the same role that the symmetric group does for the representation theory of the general linear group in Schur–Weyl duality.

The Minakshisundaram–Pleijel zeta function is a zeta function encoding the eigenvalues of the Laplacian of a compact Riemannian manifold. It was introduced by Subbaramiah Minakshisundaram and Åke Pleijel. The case of a compact region of the plane was treated earlier by Torsten Carleman.

<span class="mw-page-title-main">Vertex model</span>

A vertex model is a type of statistical mechanics model in which the Boltzmann weights are associated with a vertex in the model. This contrasts with a nearest-neighbour model, such as the Ising model, in which the energy, and thus the Boltzmann weight of a statistical microstate is attributed to the bonds connecting two neighbouring particles. The energy associated with a vertex in the lattice of particles is thus dependent on the state of the bonds which connect it to adjacent vertices. It turns out that every solution of the Yang–Baxter equation with spectral parameters in a tensor product of vector spaces yields an exactly-solvable vertex model.

In mathematics, especially in the field of representation theory, Schur functors are certain functors from the category of modules over a fixed commutative ring to itself. They generalize the constructions of exterior powers and symmetric powers of a vector space. Schur functors are indexed by Young diagrams in such a way that the horizontal diagram with n cells corresponds to the nth symmetric power functor, and the vertical diagram with n cells corresponds to the nth exterior power functor. If a vector space V is a representation of a group G, then also has a natural action of G for any Schur functor .

In mathematics, the multiple zeta functions are generalizations of the Riemann zeta function, defined by

<span class="mw-page-title-main">Rank of a partition</span>

In mathematics, particularly in the fields of number theory and combinatorics, the rank of an integer partition is a certain number associated with the partition. In fact at least two different definitions of rank appear in the literature. The first definition, with which most of this article is concerned, is that the rank of a partition is the number obtained by subtracting the number of parts in the partition from the largest part in the partition. The concept was introduced by Freeman Dyson in a paper published in the journal Eureka. It was presented in the context of a study of certain congruence properties of the partition function discovered by the Indian mathematical genius Srinivasa Ramanujan. A different concept, sharing the same name, is used in combinatorics, where the rank is taken to be the size of the Durfee square of the partition.

In combinatorial mathematics, the hook length formula is a formula for the number of standard Young tableaux whose shape is a given Young diagram. It has applications in diverse areas such as representation theory, probability, and algorithm analysis; for example, the problem of longest increasing subsequences. A related formula gives the number of semi-standard Young tableaux, which is a specialization of a Schur polynomial.

Tau functions are an important ingredient in the modern mathematical theory of integrable systems, and have numerous applications in a variety of other domains. They were originally introduced by Ryogo Hirota in his direct method approach to soliton equations, based on expressing them in an equivalent bilinear form.

The partition algebra is an associative algebra with a basis of set-partition diagrams and multiplication given by diagram concatenation. Its subalgebras include diagram algebras such as the Brauer algebra, the Temperley–Lieb algebra, or the group algebra of the symmetric group. Representations of the partition algebra are built from sets of diagrams and from representations of the symmetric group.

References

  1. Franklin, F. (1881). "Sur le developpement du produit (1  x)(1  x2)(1  x3) ...". Comtes Rendues Acad. Paris Ser A. 92: 448–450.