Parity of the partition function (communicated by don zagier

Sujets

• Sciences et techniques

Informations

• Publié par: opakito
• Nombre de lectures: 212
• Langue: English

Extrait

ct. Abstra ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 1, Issue 1, 1995 PARITY OF THE PARTITION FUNCTION KEN ONO (Communicated by Don Zagier) Letp(n) denote the number of partitions of a non-negative integer n. A well-known conjecture asserts that every arithmetic progression contains in nitely many integers M for which p(M) is odd, as well as in nitely many integersN for whichp(N) is even (see Subbarao [22]). From the works of var- ious authors, this conjecture has been veri ed for every arithmetic progression with modulust whent =1;2;3;4;5;10; 12; 16; and 40: Here we announce that there indeed are in nitely many integers N in every arithmetic progression for which p(N) is even; and that there are in nitely many integers M in every arithmetic progression for which p(M) is odd so long as there is at least one 10 7such M. In fact if there is such an M, then the smallest such M 10 t . Using these results and a fair bit of machine computation, we have veri ed the conjecture for every arithmetic progression with modulus t 100; 000. 1. Introduction A partition of a non-negative integern is a non-increasing sequence of positive inte- gers whose sum isn. Euler’s generating function forp(n), the number of partitions of an integer n; is: 1 1 X Y 1n(1) p(n)q = : n1−q n=0 n=1 Ramanujan discovered various surprising congruences forp(n)whennis in certain special arithmetic progressions; for example: p(5n+4) 0mod5; p(7n+5) 0mod7; and p(11n+6) 0mod1: There are now many proofs of these congruences (and their generalizations) in the literature (see [1, 2, 3, 4, 5, 6, 7, 11, 12, 23 ] for instance). Surprisingly there do Received by the editors February 28, 1995, and, in revised form, May 3, 1995. 1991 Mathematics Subject Classi cation . Primary 05A17; Secondary 11P83. Key words and phrases. Parity conjecture, partitions, modular forms. The author is supported by NSF grant DMS-9508976. c 1995 American Mathematical Society 35 36 KEN ONO not seem to be any such congruences modulo 2 or 3. In fact the parity of p(n) seems to be quite random, and it is believed that the partition function is ‘equally 1often’ even and odd; that is, thatp(n)isevenfor xpositive integersn x (see2 Parkin and Shanks [19]). In [22] Subbarao made the following conjecture on the parity of p(n), for those integersn belonging to any given arithmetic progression: Conjecture. For any arithmetic progression r (mod t), there are in nitely many integers M r (mod t) for which p(M) is odd, and there are in nitely many integers N r (mod t) for which p(N) is even. From the works of Garvan, Kolberg, Hirschhorn, Stanton, and Subbarao (see [6, 9, 10, 13, 16, 22],), this conjecture has been proved for every arithmetic progression with modulus t whent=1;2;3;4;5;10; 12; 16 and 40. Using very di erent methods, we go some way towards a proof of the conjecture. Using the theory of modular forms, we announce: Main Theorem 1. For any arithmetic progression r (mod t), there are in nitely many integers N r (mod t) for which p(N) is even. Main Theorem 2. For any arithmetic progression r (mod t), there are in nitely many integers M r (mod t) for which p(M) is odd, provided there is one such M. Furthermore, if there does exist anM r (mod t) for whichp(M) is odd, then the smallest such M is less than C ,wherer;t 23 7 6 Y2 A 3 t 1 C := 1− −A;r;t 2 2d p pj6t twith d := gcd(24r− 1;t) andA> is a power of 2: 24 From the two theorems we obtain an algorithm to determine the truth of our parity conjecture for any given arithmetic progression r (mod t): Compute p(N) (mod 2) for N =r;r +t;r+2t;::: for all such N up to C . As soon as we ndr;t one odd number we have veri ed the conjecture. If all these numbers are even then we have proved that the conjecture is false. Ken Burrell (Universal Analytics, Inc.) ran an e cient version of this algorithm on a CRAY C-90, giving the following result: 5Main Corollary. For al l 0 r be a power of 2: De ne24 f (z) byt;A X (24z) A 24n−1f (z):= (24tz)= a(n)q :t;A t (48z) n 1 2Then f (z) isacuspforminS (1152t; ). Moreover the Fourier expansiont;A 12A d of f (z)mod2 can be factored as:t;A ! ! 1 1 1 X X X 224n−1 24n−1 24At(2n+1)(2) f (z)= a (n)q p(n)q q mod 2:t;A t n=0 n=0 n=0 Proof. Using the well known properties of the Dedekind eta-function, it is relatively straightforward to deduce that f (z) is a modular form of weight 12A: It is alsot;A straightforward to d that f (z) is a cusp form.t;A The essential feature of the cusp formf (z) is the convenient fact thatf (z)t;A t;A is essentially the product of the generating function for p(n) and a theta function mod 2: n n1 1+X 1−X Since =  mod 2; it follows that n 2n 2n1−X 1−X 1−X 1 1 n X Y 1−qnp(n)q mod 2: 2n1−q n=0 n=1 In terms of the eta-functions, we nd that 1 124n Y X(24z) 1 1−q 24n−1(3) = p(n)q mod 2: 48n(48z) q 1−q n=1 n=0 The following in nite product identity was proved by Jacobi: 1 12 16n 2 Y X(16z) (1−q ) 2(2n+1)=q = q : 8n(8z) (1−q ) n=1 n=0 2 2Therefore since (1−X) (1−X )mod2; we nd that (4) 1 1 1 1n 32 16n 2 Y Y Y X(1−q ) (1−q ) 2n 24 (2n+1) ( z)=q (1−q ) =q q q mod 2: n 8 8n(1−q ) (1−q ) n=1 n=1 n=1 n=0 The factorization off (z) now follows easily from (3) and (4).t;A Serre [20] proved the following remarkable theorem regarding the divisibility of Fourier coe cients of holomorphic integer weight modular forms. Theorem. (Serre) Let f (z) be a holomorphic modular form of positive integer weight k on some congruence subgroup of SL (Z) with Fourier expansion2 1 X nf(z)= a(n)q n=0 where a(n) are algebraic integers in some number eld. If m is a positive integer, then there exists a positive constant such that the set of integers n x for which xa(n) is not divisible by m has cardinality :log x With this theorem we obtain              

PARITY OF THE PARTITION FUNCTION 39 Main Theorem 1. For any arithmetic progression r (mod t), there are in nitely many integers N r (mod t) for which p(N) is even. Proof. Comparing coec ients in (2), it is easy to deduce that X 2 2 2 (5) a (Atk +n) p(At(k −i )+n)mod2:t i 1;iodd Now suppose every N n for which N r (mod t) has the property that0 p(N) is odd. If k 1mod4;then every integer n r (mod t)intheinterval 2 2[Atk +n ;At(k+2) +r−t] has the property that a (n) is odd since there are0 t k +1 many odd summands in (5): After combining all such intervals, we nd a set 2 of positive integers with positive density for which a (n)6 0mod2: This wouldt contradict Serre’s theorem.  Now we need to establish that there are in nitely many M r (mod t)wherep(M) is odd provided that there is at least oneM: To do this we rst deduce a technical lemma about the reduction modulo m of the Fourier expansions of holomorphic modular forms. Main Theorem 2 follows as a consequence, for if there were only nitely many M r (mod t)forwhichp(M) is odd, then the reduction mod 2 of the relevant modular form contradicts the lemma. P nFor a given positive integer m and formal power series f := a(n)q withn2Z algebraic integer coe cients, we de ne Ord (f) to be the smallest integer n form which a(n) is not divisible by m. A special case of a theorem of Sturm [21] allows us to computationally determine whether m divides a(n) for every integer n (that is, to determine whether Ord (f)=1 ).m P 1 nIf f(z)= a(n)q 2 M (N) for some positive integer N with algebraickn =0 integer Fourier coe cients from a xed number eld and m is a positive integer, then Sturm proved that if Yk 12Ord (f)> N (1− );m 212 p pjN then Ord (f)=1(i.e. a(n)