In mathematics, Ramanujan's congruences are the congruences for the partition function p(n) discovered by Srinivasa Ramanujan:
\begin{align} p(5k+4)&\equiv0\pmod5,\\ p(7k+5)&\equiv0\pmod7,\\ p(11k+6)&\equiv0\pmod{11}. \end{align}
In plain words, e.g., the first congruence means that If a number is 4 more than a multiple of 5, i.e. it is in the sequence
4, 9, 14, 19, 24, 29, . . .then the number of its partitions is a multiple of 5.
Later other congruences of this type were discovered, for numbers and for Tau-functions.
In his 1919 paper,[1] he proved the first two congruences using the following identities (using q-Pochhammer symbol notation):
\begin{align} &
| infty | |
| \sum | |
| k=0 |
| ||||||||||||||||
| p(5k+4)q |
,\\[4pt] &
| infty | |
| \sum | |
| k=0 |
| |||||||||||||||||
| p(7k+5)q | +49q |
| |||||||
|
. \end{align}
He then stated that "It appears there are no equally simple properties for any moduli involving primes other than these".
After Ramanujan died in 1920, G. H. Hardy extracted proofs of all three congruences from an unpublished manuscript of Ramanujan on p(n) (Ramanujan, 1921). The proof in this manuscript employs the Eisenstein series.
In 1944, Freeman Dyson defined the rank function for a partition and conjectured the existence of a "crank" function for partitions that would provide a combinatorial proof of Ramanujan's congruences modulo 11. Forty years later, George Andrews and Frank Garvan found such a function, and proved the celebrated result that the crank simultaneously "explains" the three Ramanujan congruences modulo 5, 7 and 11.
In the 1960s, A. O. L. Atkin of the University of Illinois at Chicago discovered additional congruences for small prime moduli. For example:
p(113 ⋅ 13k+237)\equiv0\pmod{13}.
Extending the results of A. Atkin, Ken Ono in 2000 proved that there are such Ramanujan congruences modulo every integer coprime to 6. For example, his results give
p(1074 ⋅ 31k+30064597)\equiv0\pmod{31}.
A conceptual explanation for Ramanujan's observation was finally discovered in January 2011 [3] by considering the Hausdorff dimension of the following
P
P\ell(b;z):=
| infty | ||
| \sum | p\left( | |
| n=0 |
| \ellbn+1 | |
| 24 |
\right)qn/24.
It is seen to have dimension 0 only in the cases where ℓ = 5, 7 or 11 and since the partition function can be written as a linear combination of these functions[4] this can be considered a formalization and proof of Ramanujan's observation.
In 2001, R.L. Weaver gave an effective algorithm for finding congruences of the partition function, and tabulated 76,065 congruences.[5] This was extended in 2012 by F. Johansson to 22,474,608,014 congruences,[6] one large example being
p(9999594 ⋅ 29k+28995221336976431135321047)\equiv0\pmod{29}.