In mathematics, Ramanujan's congruences are the congruences for the partition function p(n) discovered by Srinivasa Ramanujan:
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
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):
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:
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
Later Ken Ono conjectured that the elusive crank also satisfies exactly the same types of general congruences. This was proved by his Ph.D. student Karl Mahlburg in his 2005 paper Partition Congruences and the Andrews–Garvan–Dyson Crank, linked below. This paper won the first Proceedings of the National Academy of Sciences Paper of the Year prize. [2]
A conceptual explanation for Ramanujan's observation was finally discovered in January 2011 [3] by considering the Hausdorff dimension of the following function in the l-adic topology:
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
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.
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.
In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo of an odd prime number p: its value at a (nonzero) quadratic residue mod p is 1 and at a non-quadratic residue (non-residue) is −1. Its value at zero is 0.
In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the "variable" remains an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem. One can generalize to formal power series in more than one indeterminate, to encode information about infinite multi-dimensional arrays of numbers.
In modular arithmetic, a number g is a primitive root modulo n if every number a coprime to n is congruent to a power of g modulo n. That is, g is a primitive root modulo n if for every integer a coprime to n, there is some integer k for which gk ≡ a. Such a value k is called the index or discrete logarithm of a to the base g modulo n. So g is a primitive root modulo n if and only if g is a generator of the multiplicative group of integers modulo n.
In theoretical computer science and cryptography, a trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction without special information, called the "trapdoor". Trapdoor functions are a special case of one-way functions and are widely used in public-key cryptography.
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 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 theory.
In mathematics, Wolstenholme's theorem states that for a prime number , the congruence
In number theory, a branch of mathematics, the Carmichael functionλ(n) of a positive integer n is the smallest member of the set of positive integers m having the property that
The Ramanujan tau function, studied by Ramanujan, is the function defined by the following identity:
In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:
In number theory, the law of quadratic reciprocity, like the Pythagorean theorem, has lent itself to an unusually large number of proofs. Several hundred proofs of the law of quadratic reciprocity have been published.
The Tonelli–Shanks algorithm is used in modular arithmetic to solve for r in a congruence of the form r2 ≡ n, where p is a prime: that is, to find a square root of n modulo p.
In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m. In the standard notation of modular arithmetic this congruence is written as
In number theory, the Fermat quotient of an integer a with respect to an odd prime p is defined as
The spt function is a function in number theory that counts the sum of the number of smallest parts in each integer partition of a positive integer. It is related to the partition function.
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 number theory, the crank of an integer partition is a certain number associated with the partition. It was first introduced without a definition by Freeman Dyson, who hypothesised its existence in a 1944 paper. Dyson gave a list of properties this yet-to-be-defined quantity should have. In 1988, George E. Andrews and Frank Garvan discovered a definition for the crank satisfying the properties hypothesized for it by Dyson.
In mathematics, specifically in number theory, Newman's conjecture is a conjecture about the behavior of the partition function modulo any integer. Specifically, it states that for any integers m and r such that , the value of the partition function satisfies the congruence for infinitely many non-negative integers n. It was formulated by mathematician Morris Newman in 1960. It is unsolved as of 2020.
