In
number theory, the partition function represents the
number
A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words. More universally, individual number ...
of possible
partitions
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of ...
of a non-negative integer . For instance, because the integer 4 has the five partitions , , , , and .
No
closed-form expression
In mathematics, a closed-form expression is a mathematical expression that uses a finite number of standard operations. It may contain constants, variables, certain well-known operations (e.g., + − × ÷), and functions (e.g., ''n''th r ...
for the partition function is known, but it has both
asymptotic expansions In mathematics, an asymptotic expansion, asymptotic series or Poincaré expansion (after Henri Poincaré) is a formal series of functions which has the property that truncating the series after a finite number of terms provides an approximation t ...
that accurately approximate it and
recurrence relations by which it can be calculated exactly. It grows as an
exponential function
The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, ...
of the
square root
In mathematics, a square root of a number is a number such that ; in other words, a number whose '' square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
...
of its argument. The
multiplicative inverse
In mathematics, a multiplicative inverse or reciprocal for a number ''x'', denoted by 1/''x'' or ''x''−1, is a number which when multiplied by ''x'' yields the multiplicative identity, 1. The multiplicative inverse of a fraction ''a''/' ...
of its
generating function is the
Euler function; by Euler's
pentagonal number theorem this function is an alternating sum of
pentagonal number powers of its argument.
Srinivasa Ramanujan first discovered that the partition function has nontrivial patterns in
modular arithmetic, now known as
Ramanujan's congruences. For instance, whenever the decimal representation of ends in the digit 4 or 9, the number of partitions of will be divisible by 5.
Definition and examples
For a positive integer , is the number of distinct ways of representing as a
sum of positive integers. For the purposes of this definition, the order of the terms in the sum is irrelevant: two sums with the same terms in a different order are not considered to be distinct.
By convention , as there is one way (the
empty sum) of representing zero as a sum of positive integers. Furthermore when is negative.
The first few values of the partition function, starting with , are:
Some exact values of for larger values of include:
, the largest known
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
among the values of is , with 40,000 decimal digits. Until March 2022, this was also the largest prime that has been proved using
elliptic curve primality proving In mathematics, elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving. It is an idea put forward by Shafi Goldwasser and Joe Kilian in 198 ...
.
Generating function
The
generating function for ''p''(''n'') is given by
The equality between the products on the first and second lines of this formula
is obtained by expanding each factor
into the
geometric series
To see that the expanded product equals the sum on the first line,
apply the
distributive law to the product. This expands the product into a sum of
monomial
In mathematics, a monomial is, roughly speaking, a polynomial which has only one term. Two definitions of a monomial may be encountered:
# A monomial, also called power product, is a product of powers of variables with nonnegative integer expon ...
s of the form
for some sequence of coefficients
, only finitely many of which can be non-zero.
The exponent of the term is
, and this sum can be interpreted as a representation of
as a partition into
copies of each number
. Therefore, the number of terms of the product that have exponent
is exactly
, the same as the coefficient of
in the sum on the left.
Therefore, the sum equals the product.
The function that appears in the denominator in the third and fourth lines of the formula is the
Euler function. The equality between the product on the first line and the formulas in the third and fourth lines is Euler's
pentagonal number theorem.
The exponents of
in these lines are the
pentagonal numbers
for
(generalized somewhat from the usual pentagonal numbers, which come from the same formula for the positive values of
). The pattern of positive and negative signs in the third line comes from the term
in the fourth line: even choices of
produce positive terms, and odd choices produce negative terms.
More generally, the generating function for the partitions of
into numbers selected from a set
of positive integers can be found by taking only those terms in the first product for which
. This result is due to
Leonhard Euler
Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries ...
. The formulation of Euler's generating function is a special case of a
-Pochhammer symbol and is similar to the product formulation of many
modular forms, and specifically the
Dedekind eta function.
Recurrence relations
The same sequence of pentagonal numbers appears in a
recurrence relation for the partition function:
As base cases,
is taken to equal
, and
is taken to be zero for negative
. Although the sum on the right side appears infinite, it has only finitely many nonzero terms,
coming from the nonzero values of
in the range
Another recurrence relation for
can be given in terms of the
sum of divisors function :
If
denotes the number of partitions of
with no repeated parts then it follows by splitting each partition into its even parts and odd parts, and dividing the even parts by two, that
Congruences
Srinivasa Ramanujan is credited with discovering that the partition function has nontrivial patterns in
modular arithmetic.
For instance the number of partitions is divisible by five whenever the decimal representation of
ends in the digit 4 or 9, as expressed by the congruence
For instance, the number of partitions for the integer 4 is 5.
For the integer 9, the number of partitions is 30; for 14 there are 135 partitions. This congruence is implied by the more general identity
also by Ramanujan, where the notation
denotes the product defined by
A short proof of this result can be obtained from the partition function generating function.
Ramanujan also discovered congruences modulo 7 and 11:
The first one comes from Ramanujan's identity
Since 5, 7, and 11 are consecutive
primes, one might think that there would be an analogous congruence for the next prime 13,
for some . However, there is no congruence of the form
for any prime ''b'' other than 5, 7, or 11. Instead, to obtain a congruence, the argument of
should take the form
for some
. In the 1960s,
A. O. L. Atkin of the
University of Illinois at Chicago discovered additional congruences of this form for small prime moduli. For example:
proved that there are such congruences for every prime modulus greater than 3. Later, showed there are partition congruences modulo every integer
coprime to 6.
Approximation formulas
Approximation formulas exist that are faster to calculate than the exact formula given above.
An
asymptotic expression for ''p''(''n'') is given by
:
as
.
This
asymptotic formula was first obtained by
G. H. Hardy and
Ramanujan in 1918 and independently by
J. V. Uspensky in 1920. Considering
, the asymptotic formula gives about
, reasonably close to the exact answer given above (1.415% larger than the true value).
Hardy and Ramanujan obtained an
asymptotic expansion with this approximation as the first term:
where
Here, the notation
means that the sum is taken only over the values of
that are
relatively prime to
. The function
is a
Dedekind sum In mathematics, Dedekind sums are certain sums of products of a sawtooth function, and are given by a function ''D'' of three integer variables. Dedekind introduced them to express the functional equation of the Dedekind eta function. They ha ...
.
The error after
terms is of the order of the next term, and
may be taken to be of the order of
. As an example, Hardy and Ramanujan showed that
is the nearest integer to the sum of the first
terms of the series.
In 1937,
Hans Rademacher was able to improve on Hardy and Ramanujan's results by providing a
convergent series
In mathematics, a series is the sum of the terms of an infinite sequence of numbers. More precisely, an infinite sequence (a_0, a_1, a_2, \ldots) defines a series that is denoted
:S=a_0 +a_1+ a_2 + \cdots=\sum_^\infty a_k.
The th partial ...
expression for
. It is
The proof of Rademacher's formula involves
Ford circles,
Farey sequences,
modular symmetry and the
Dedekind eta function.
It may be shown that the
th term of Rademacher's series is of the order
so that the first term gives the Hardy–Ramanujan asymptotic approximation.
published an elementary proof of the asymptotic formula for
.
Techniques for implementing the Hardy–Ramanujan–Rademacher formula efficiently on a computer are discussed by , who shows that
can be computed in time
for any
. This is near-optimal in that it matches the number of digits of the result. The largest value of the partition function computed exactly is
, which has slightly more than 11 billion digits.
Strict partition function
Definition and properties
If no summand occurs repeatedly in the affected partition sums, then the so called strict partitions are present. The function Q(n) gives the number of these strict partitions in relation to the given sum n. Therefore the strict partition sequence Q(n) satisfies the criterion Q(n) ≤ P(n) for all
. The same result results if only odd summands
may appear in the partition sum, but these may also occur more than once.
Exemplary values of strict partition numbers
Representations of the partitions:
MacLaurin series
The corresponding generating function based on the
MacLaurin series
Maclaurin or MacLaurin is a surname. Notable people with the surname include:
* Colin Maclaurin (1698–1746), Scottish mathematician
* Normand MacLaurin (1835–1914), Australian politician and university administrator
* Henry Normand MacLaurin ...
with the numbers Q(n) as coefficients in front of x
n is as follows:
:
The following first addends are obtained:
:
In comparison, the generating function of the regular partition numbers P(n) has this identity with respect to the theta function:
:
Important calculation formulas for the
theta function:
:
: