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.