TOPICS
Search

Partition Function P Congruences

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
PartitionsPOdd

The fraction of odd values of the partition function P(n) is roughly 50%, independent of n, whereas odd values of Q(n) occur with ever decreasing frequency as n becomes large. Kolberg (1959) proved that there are infinitely many even and odd values of P(n).

Leibniz noted that P(n) is prime for n=2, 3, 4, 5, 6, but not 7. In fact, values of n for which P(n) is prime are 2, 3, 4, 5, 6, 13, 36, 77, 132, 157, 168, 186, ... (OEIS A046063), corresponding to 2, 3, 5, 7, 11, 101, 17977, 10619863, ... (OEIS A049575). Numbers which cannot be written as a product of P(n) are 13, 17, 19, 23, 26, 29, 31, 34, 37, 38, 39, ... (OEIS A046064), corresponding to numbers of nonisomorphic Abelian groups which are not possible for any group order.

Ramanujan conjectured a number of amazing and unexpected congruences involving P(n). In particular, he proved

P(5m+4)=0 (mod 5)
(1)

using Ramanujan's identity (Darling 1919; Hardy and Wright 1979; Drost 1997; Hardy 1999, pp. 87-88; Hirschhorn 1999). Ramanujan (1919) also showed that

P(25m+24)=0 (mod 5^2),
(2)

and Krečmar (1933) proved that

P(125m+99)=0 (mod 5^3).
(3)

Watson (1938) then proved the general congruence

P(n)=0 (mod 5^a) if 24n=1 (mod 5^a)
(4)

(Gordon and Hughes 1981; Hardy 1999, p. 89). For a=1, 2, ..., the corresponding minimal values of n are 4, 24, 99, 599, 2474, 14974, 61849, ... (OEIS A052463). However, the even more general congruences

P(125m+74,99,124)=0 (mod 5^3)
(5)
P(3125m+1849,2474,3099)=0 (mod 5^5)
(6)

seem also to hold.

Ramanujan showed that

P(7m+5)=0 (mod 7)
(7)

(Darling 1919), which can be derived using the Euler identity and Jacobi triple product (Hardy 1999, pp. 87-88), and also that

P(49m+47)=0 (mod 7^2)
(8)

(Hardy 1999, p. 90). He conjectured that in general

P(n)=0 (mod 7^b) if 24n=1 (mod 7^b) [incorrect]
(9)

(Gordon and Hughes 1981, Hardy 1999), although Gupta (1936) showed that this is false when b=3. Watson (1938) subsequently formulated and proved the modified relation

P(n)=0 (mod 7^b) if 24n=1 (mod 7^(2b-2))
(10)

for b>=2. For b=1, 2, ..., the corresponding minimal values of n are 0, 47, 2301, 112747, ... (OEIS A052464). However, the even more general congruences

P(49m+19,33,40,47)=0 (mod 7^2)
(11)

appear to hold.

Ramanujan showed that

P(11m+6)=0 (mod 11)
(12)

holds (Gordon and Hughes 1981; Hardy 1999, pp. 87-88), and conjectured the general relation

P(n)=0 (mod 11^c) if 24n=1 (mod 11^c).
(13)

This was finally proved by Atkin (1967). For c=1, 2, ..., the corresponding minimal values of n are 6, 116, 721, 14031, ... (OEIS A052465).

Atkin and O'Brien (1967) proved

P(169n-7)=kappa_dP(n) (mod 13^d) if 24n=1 (mod 13^d),
(14)

where kappa_d is an integer depending only on d (Gordon and Hughes 1981). For d=1, 2, ..., the corresponding minimal values of n are 6, 162, 1007, 27371, ... (OEIS A052466).

Subbarao (1966) conjectured that in every arithmetic progression r (mod t), there are infinitely many integers N=r (mod t) for which P(N) is even, and infinitely many integer M=r (mod t) for which P(M) is odd.

Dyson (1944) explained congruences modulo 5 and 7 via a mathematical tool he termed a "rank" and conjectured that this approach could be extended to other moduli. The conjecture (sometimes known as the "crank conjecture") was extended to congruences modulo 11 (Andrews and Garvan 1988). Mahlburg (2005) subsequently completely resolved the conjecture with an elegant proof described by Dyson as "beautiful and totally unexpected."

In the Season 4 opening episode "Trust Metric" (2007) of the television crime drama NUMB3RS, math genius Charlie Eppes closes the opening scene by informing his class they will cover partition congruences in the next class (despite the strange fact that the current lesson was on Nash equilibria).

See also

Congruence, Erdős-Ivić Conjecture, Integer Sequence Primes, Newman's Conjecture, Partition Function P, Partition Function q, Partition Function Q, Partition Function Q Congruences

Related Wolfram sites

http://functions.wolfram.com/IntegerFunctions/PartitionsP/

Explore with Wolfram|Alpha

References

Andrews, G. E. and Garvan, F. G. "Dyson's Crank of a Partition." Bull. Amer. Math. Soc. 18, 167-171, 1988.Atkin, A. O. L. "Proof of a Conjecture of Ramanujan." Glasgow Math. J. 8, 14-32, 1967.Atkin, A. O. L. and O'Brien, J. N. "Some Properties of p(n) and c(n) Modulo Powers of 13." Trans. Amer. Math. Soc. 126, 442-459, 1967.Chowla, S. "Congruence Properties of Partitions." J. London Math. Soc. 9, 247, 1934.Darling, H. B. C. "On Mr. Ramanujan's Congruence Properties of p(n)." Proc. Cambridge Philos. Soc. 19, 217-218, 1919.Darling, H. B. C. "Proofs of Certain Identities and Congruences Enunciated by S. Ramanujan." Proc. London Math. Soc. 19, 350-372, 1921.Drost, J. L. "A Shorter Proof of the Ramanujan Congruence mod 5." Amer. Math. Monthly 104, 963-964, 1997.Dyson, F. J. Eureka 8, 10-15, 1944.Dyson, F. J. "Mappings and Symmetries of Partitions." J. Combin. Theory Ser. A 51, 169-180, 1989.Folsom, A.; Kent, Z. A.;and Ono, K. "l-adic Properties of the Partition Function." www.aimath.org/news/partition/folsom-kent-ono.pdf.Getz, J. "On Congruence Properties of the Partition Function." Internat. J. Math. Math. Sci. 23, 493-496, 2000.Gordon, B. and Hughes, K. "Ramanujan Congruences for q(n)." In Analytic Number Theory, Proceedings of the Conference Held at Temple University, Philadelphia, Pa., May 12-15, 1980 (Ed. M. I. Knopp). New York: Springer-Verlag, pp. 333-359, 1981.Gupta, H. "On a Conjecture of Ramanujan." Proc. Indian Acad. Sci. (A) 4, 625-629, 1936.Hardy, G. H. Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, 1999.Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, 1979.Hirschhorn, M. D. "Another Short Proof of Ramanujan's Mod 5 Partition Congruences, and More." Amer. Math. Monthly 106, 580-583, 1999.Kolberg, O. "Note on the Parity of the Partition Function." Math. Scand. 7, 377-378, 1959.Krečmar, W. "Sur les propriétés de la divisibilité d'une fonction additive." Bull. Acad. Sci. URSS 7, 763-800, 1933.Lehmer, D. H. "An Application of Schläfli's Modular Equation to a Conjecture of Ramanujan." Bull. Amer. Math. Soc. 44, 84-90, 1938.Lewis, R. "Relations Between the Rank and the Crank Modulo 9." J. London Math. Soc. 45, 222-231, 1992.Mahlburg, K. "Partition Congruences and the Andrews-Garvan-Dyson Crank." Proc. National Acad. Sci. USA 102, 15373-15376, 2005.McKee, M. "Classic Maths Puzzle Cracked at Last." Mar. 21, 2005. http://www.newscientist.com/article.ns?id=dn7180.Mordell, L. J. "Note on Certain Modular Relations Considered by Messrs Ramanujan, Darling and Rogers." Proc. London Math. Soc. 20, 408-416, 1922.Ono, K. "Parity of the Partition Function in Arithmetic Progressions." J. reine. angew. Math. 472, 1-15, 1996.Ono, K. "The Partition Function in Arithmetic Progressions." Math. Ann. 312, 251-260, 1998.Ono, K. "Distribution of the Partition Function Modulo m." Ann. Math. 151, 293-307, 2000.Ramanujan, S. "Some Properties of p(n), the Number of Partitions of n." Proc. Cambridge Philos. Soc. 19, 207-210, 1919.Ramanujan, S. "Congruence Properties of Partitions." Math. Z. 9, 147-153, 1921.Sloane, N. J. A. Sequences A046063, A046064, A049575, A052462, A052463, A052464, A052465, and A052466 in "The On-Line Encyclopedia of Integer Sequences."Subbarao, M. V. "Some Remarks on the Partition Function." Amer. Math. Monthly 73, 851-854, 1966.Watson, G. N. "Ramanujans Vermutung über Zerfällungsanzahlen." J. für Math. 179, 97-128, 1938.Winquist, L. "An Elementary Proof of p(11m+6)=0 (mod 11)." J. Combin. Th. 6, 56-59, 1969.

Referenced on Wolfram|Alpha

Partition Function P Congruences

Cite this as:

Weisstein, Eric W. "Partition Function P Congruences." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PartitionFunctionPCongruences.html

Subject classifications