Subject: Number of integer partitions 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, ... Def: Let n be an integer >= 1. A partition of n is a representation of n as a sum of integers >= 1, not considering the order of term of this sum. These terms are called summands, or parts, of the partition. Example: list of partitions of 1 to 5 1 2, 1+1 3, 2+1, 1+1+1 4, 3+1, 2+2, 2+1+1, 1+1+1+1 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1. The generating function of the number p(n) of partitions of n equals: 1 + p(1) t + p(2) t^2 + p(3) t^3 + ... 1 = ------------------------------------ (1-t)(1-t^2)(1-t^3)(1-t^4)(1-t^5)... Theorem (Euler): Let q0(n) (or q1(n)) be the number of partitions of n into an even (or odd) number of inequal summands. Then: / (-1)^k if n = (3*k +- 1)*k/2 q0(n) - q1(n) = | \ 0 otherwise An involution proof was given be Franklin [1881]. From this theorem follows the celebrated 'pentagonal theorem'. Theorem (Euler 'pentagonal theorem'): p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + ... = Sum_{k>=1} (-1)^(k-1) * ( p(n - k*(3k-1)/2) + p(n - k*(3k+1)/2) ). (p(0) = 1 and p(k) = 0 for all k < 0) ----------------------------------------------------------------------------- Date: Fri, 19 Jul 1996 08:21:42 -0400 From: "A.O.L.Atkin 312-413-2155" Subject: p(n) Revisited To: Multiple recipients of list NMBRTHRY In a recent issue of Trans. Amer. Math. Soc., after a statement of Ramanujan's 5-7-11 congruences for p(n), I read: "It is now believed that, besides these very special congruences, there are no other moduli m for which p(n) behaves in a predictable way modulo m". I do not know how these beliefs are decided upon and ratified by the mathematical profession( except that I was not invited to cast my vote), nor do I know exactly what "predictable" means. It can be argued that p(n) is unpredictable even mod 5 (see the end of this note). However, I take it to mean the existence of some linear congruence p(Ak+B)=0(mod m) for all k. If it means the existence of such a congruence with A composed only of the primes which occur in m,then this should have been made plain. Otherwise I am forced to raise my lone voice in opposition to the new orthodoxy, and declare my own credo in this matter, which is: I think it is very likely that, given any m prime to 6, there exist a power c=c(m) and a modulus m' with m dividing m' dividing m**2, such that for all n with 24n-1 divisible by m' and 5**c, but not divisible by 5**(c+1), we have p(n) divisible by m. ***************************** I have, in my opinion, good reasons for this statement exactly as I have made it. I see no prospect of a general proof, and wish to be clear that I am not making a formal conjecture according to my own definition of that word. (Theorem= true and proved, Conjecture= true but not proved, Result= proved but not true). The English language (though not,apparently, the Hungarian) is rich in words to express all shades of belief. One word at least should be available for total conviction without formal proof. However, I do not need to rely on alternative creeds or unpublished allegations merely to refute the statement that nobody besides Ramanujan can find linear congruences. A large number of these involving primes up to 37, with relevant proofs, methods, and speculations, can be found in the following papers(by me except where stated): (1) Trans.Amer.Math.Soc.126(1967),442 (with J.N.O'Brien) (2) Proc. London Math. Soc.(3)18(1968)563 (3) Computers in Mathematical Research,North-Holland,(1968),8 (4) Proc. Symposia in Pure Math. XII,AMS,(1969),33 Chapter 6 of "Lectures on Modular Forms", by J. Lehner, contains the only published version of my proof of the conjectures in (1). (It was of course published with my consent and scrupulously acknowledged.) National Bureau of Standards, Applied Mathematics Series #61,December 1969. The general view expounded there, which I have found no reason to change in the last quarter-century,was roughly as follows. Let a(n) be the Fourier coefficient of a modular form of nonpositive weight which is zero at the cusp infinity. One expects this to be a linear combination modulo m of the coefficients of forms which are eigenfunctions of the Hecke operators T(p)(or T(p**2) if the form has halfintegral weight). There must clearly be a restriction on n in terms of m; with m a prime power q**a the fruitful restrictions appear to be n=0(mod q**b) or (n/q)=+/-1 when m=q. It was and is not clear to me how far this latter type of restriction can be extended to(mod q**a). This view was supported by a number of theorems and methods, and barring very unlikely numerical accidents it seemed that one could prove something for given small q and moderate a with comparative ease, and given small q and all a with a lot of work. I gave various examples up to and including q=37. I decided two weeks ago to revisit this topic, with a bigger machine,Fourier transform multiplication of series,and a better understanding of the supersingular equation, to compensate my waning brute force. The paper (2) above is mainly concerned with properties of p(n) mod q**a with ((1-24n)/q)=-1, for q.le.23. I wrote: " For q.gt.23 the inequality..ceases to be valid, & I have no evidence as to whether results analogous to .. exist. If they do an entirely different method of proof would be required." As it turns out, the evidence that analogous results do exist is overwhelming, and (armed with this knowledge) it is not too hard to see how to modify the proof. Having so often deprecated in others the habit of making rash predictions without reasonable evidence, I find it embarrassing to confess the beam in my own eye in 1968; but the inescapable fact is that "entirely different method" was wrong- it should have read "(a) somewhat different method". The transition from eigenfunctions to linear congruences for p(n) is not difficult, using the properties of linear recurrence relations mod q and some computed accidents. A few specimens follow( some of them based on 24n-1= 0 (mod q)). (Examples up to q=31 are given in (2)). All these specimens are to be taken as E&OE; I have taken reasonable care but the program could have some minor bugs. The case k=0 of the first congruence(p(18897974)) I checked with a 40"-run using Hardy-Ramanujan-Rademacher; the 4835-digit number was congruent to 55 both mod 125 and mod 529. We know it ought to be 0(mod 125), which gives reasonable confirmation mod 529, although a California jury might not convict on this evidence. p(43087380625*k + 18897974) = 0 (mod 529) , p(1190152249*k + 25315010) = 0 (mod 37) , p(304494911572931557660375*k + 63815247466378749) = 0 (mod 41) , p(786247213213708750375*k + 274036427607799) = 0 (mod 43) , p(2941074612320027*k + 557227073122) = 0 (mod 53) , p(24734199927692656375*k + 8194615134374) = 0 (mod 61) , p(8246643166425328356875*k + 670996159483474)= 0 (mod 73) , p(56893553114417795882733233887726622539837725796216043375*k + .. 603601919402946826194658925316161463324) = 0 (mod 101) , p(1140773130436436432134058026060201612619574856085125*k + .. 1278827052061576887278324769721420299) = 0 (mod 113) , It is possible to reduce the need for computed accidents, but at the cost of increasing the common difference of the A.P.,e.g.: p(n)=0 (mod 73) if ((24n-1)/73)=-1 and 24n-1 is divisible by 5**10655 but not by 5**10656. ****************** This is a convenient place to report a computation I did some years ago on the distribution of p(n) mod 5. I went to 30,000,000 using eta(25)/eta= sigma x**n sigma (d divides n) d. ((n/d)/5) (mod 5) and splitting the Eisenstein series into 25 parts. The value of p(n) mod 5 is predictable from other values if 24n-1=0(mod 5), or n is not squarefree and ((24n-1)/5)=-1. Accordingly I excluded these values from the counts. I found nothing interesting when ((24n-1)/5)=1, and suspect that there is nothing interesting. For squarefree n with ((24n-1)/5)=-1 there was a slight bias in favour of zero mod 5, which I am wholly unable to explain. Such things often happen "at the beginning" ,but this phenomenon persisted uniformly at about 3%; I cannot recall the exact figure ,but I do recall that the difference from the "expected" was 78 sigma, as the statisticians use that letter, which only a politician could regard as a coincidence.