In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777â ...
, 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 numbers c ...
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 a ...
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 roo ...
for the partition function is known, but it has both
asymptotic expansions that accurately approximate it and
recurrence relation
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
s 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, a ...
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 .
E ...
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 Multiplication, multiplied by ''x'' yields the multiplicative identity, 1. The multiplicative inverse of a rat ...
of its
generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
is the
Euler function
In mathematics, the Euler function is given by
:\phi(q)=\prod_^\infty (1-q^k),\quad , q, A000203
On account of the identity \sum_ d = \sum_ \frac, this may also be written as
:\ln(\phi(q)) = -\sum_^\infty \frac \sum_ d.
Also if a,b\in\mathbb^ ...
; by Euler's
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
:\prod_^\left(1-x^\right)=\sum_^\left(-1\right)^x^=1+\sum_^\infty(-1)^k\left(x^+x^\right ...
this function is an alternating sum of
pentagonal number
A pentagonal number is a figurate number that extends the concept of triangular and square numbers to the pentagon, but, unlike the first two, the patterns involved in the construction of pentagonal numbers are not rotationally symmetrical. The ...
powers of its argument.
Srinivasa Ramanujan
Srinivasa Ramanujan (; born Srinivasa Ramanujan Aiyangar, ; 22 December 188726 April 1920) was an Indian mathematician. Though he had almost no formal training in pure mathematics, he made substantial contributions to mathematical analysis ...
first discovered that the partition function has nontrivial patterns in
modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book ...
, now known as
Ramanujan's congruences
In mathematics, Ramanujan's congruences are some remarkable congruences for the partition function ''p''(''n''). The mathematician Srinivasa Ramanujan
Srinivasa Ramanujan (; born Srinivasa Ramanujan Aiyangar, ; 22 December 188726 April 19 ...
. 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
In mathematics, an empty sum, or nullary sum, is a summation where the number of terms is zero.
The natural way to extend non-empty sums is to let the empty sum be the additive identity.
Let a_1, a_2, a_3, ... be a sequence of numbers, and let
...
) 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 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 because the only ways ...
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 1986 ...
.
Generating function
The
generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
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
In mathematics, a geometric series is the sum of an infinite number of terms that have a constant ratio between successive terms. For example, the series
:\frac \,+\, \frac \,+\, \frac \,+\, \frac \,+\, \cdots
is geometric, because each suc ...
To see that the expanded product equals the sum on the first line,
apply the
distributive law
In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality
x \cdot (y + z) = x \cdot y + x \cdot z
is always true in elementary algebra.
For example, in elementary arithmetic, ...
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 expone ...
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
In mathematics, the Euler function is given by
:\phi(q)=\prod_^\infty (1-q^k),\quad , q, A000203
On account of the identity \sum_ d = \sum_ \frac, this may also be written as
:\ln(\phi(q)) = -\sum_^\infty \frac \sum_ d.
Also if a,b\in\mathbb^ ...
. The equality between the product on the first line and the formulas in the third and fourth lines is Euler's
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
:\prod_^\left(1-x^\right)=\sum_^\left(-1\right)^x^=1+\sum_^\infty(-1)^k\left(x^+x^\right ...
.
The exponents of
in these lines are the
pentagonal number
A pentagonal number is a figurate number that extends the concept of triangular and square numbers to the pentagon, but, unlike the first two, the patterns involved in the construction of pentagonal numbers are not rotationally symmetrical. The ...
s
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 in ma ...
. 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 form
In mathematics, a modular form is a (complex) analytic function on the upper half-plane satisfying a certain kind of functional equation with respect to the Group action (mathematics), group action of the modular group, and also satisfying a grow ...
s, and specifically the
Dedekind eta function
In mathematics, the Dedekind eta function, named after Richard Dedekind, is a modular form of weight 1/2 and is a function defined on the upper half-plane of complex numbers, where the imaginary part is positive. It also occurs in bosonic string ...
.
Recurrence relations
The same sequence of pentagonal numbers appears in a
recurrence relation
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
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
Srinivasa Ramanujan (; born Srinivasa Ramanujan Aiyangar, ; 22 December 188726 April 1920) was an Indian mathematician. Though he had almost no formal training in pure mathematics, he made substantial contributions to mathematical analysis ...
is credited with discovering that the partition function has nontrivial patterns in
modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book ...
.
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
A prime number (or a prime) is a natural number greater than 1 that is not a 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 because the only ways ...
, 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
Arthur Oliver Lonsdale Atkin (31 July 1925 – 28 December 2008), who published under the name A. O. L. Atkin, was a British mathematician.
As an undergraduate during World War II, Atkin worked at Bletchley Park cracking German codes. He receiv ...
of the
University of Illinois at Chicago
The University of Illinois Chicago (UIC) is a Public university, public research university in Chicago, Illinois. Its campus is in the Near West Side, Chicago, Near West Side community area, adjacent to the Chicago Loop. The second campus esta ...
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
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
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
In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior.
As an illustration, suppose that we are interested in the properties of a function as becomes very large. If , then as bec ...
was first obtained by
G. H. Hardy
Godfrey Harold Hardy (7 February 1877 – 1 December 1947) was an English mathematician, known for his achievements in number theory and mathematical analysis. In biology, he is known for the Hardy–Weinberg principle, a basic principle of pop ...
and
Ramanujan in 1918 and independently by
J. V. Uspensky )
, birth_date =
, birth_place = Urga, Outer Mongolia
, death_date =
, death_place = San Francisco, United States
, nationality =
, work_institution = Stanford University, University of Minnesota
, alma_mater = University ...
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 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 to ...
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
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
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 have su ...
.
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
Hans Adolph Rademacher (; 3 April 1892, Wandsbeck, now Hamburg-Wandsbek – 7 February 1969, Haverford, Pennsylvania, USA) was a German-born American mathematician, known for work in mathematical analysis and number theory.
Biography
Rademacher r ...
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 sum ...
expression for
. It is
The proof of Rademacher's formula involves
Ford circle
In mathematics, a Ford circle is a circle with center at (p/q,1/(2q^2)) and radius 1/(2q^2), where p/q is an irreducible fraction, i.e. p and q are coprime integers. Each Ford circle is tangent to the horizontal axis y=0, and any two Ford circles ...
s,
Farey sequence
In mathematics, the Farey sequence of order ''n'' is the sequence of completely reduced fractions, either between 0 and 1, or without this restriction, which when in lowest terms have denominators less than or equal to ''n'', arranged in ord ...
s,
modular symmetry and the
Dedekind eta function
In mathematics, the Dedekind eta function, named after Richard Dedekind, is a modular form of weight 1/2 and is a function defined on the upper half-plane of complex numbers, where the imaginary part is positive. It also occurs in bosonic string ...
.
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
In mathematics, theta functions are special functions of several complex variables. They show up in many topics, including Abelian varieties, moduli spaces, quadratic forms, and solitons. As Grassmann algebras, they appear in quantum field ...
:
:
: