Intermediate Algebra MATH 101
Popular in Course
Popular in Mathematics (M)
This 31 page Class Notes was uploaded by Zechariah Hilpert on Thursday September 17, 2015. The Class Notes belongs to MATH 101 at University of Wisconsin - Madison taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/205296/math-101-university-of-wisconsin-madison in Mathematics (M) at University of Wisconsin - Madison.
Reviews for Intermediate Algebra
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/17/15
DISTRIBUTION OF THE PARTITION FUNCTION MODULO m KEN ONO Annals of Mathematics 151 2000 pages 203 307 1 INTRODUCTION AND STATEMENT OF RESULTS A partition of a positive integer n is any non increasing sequence of positive integers whose sum is ii Let pn denote the number of partitions of n as usual we adopt the convention that 190 1 and pa 0 if oz Z N Ramanujan proved for every non negative integer n that p5n 4 E 0 mod 5 p7n 5 E 0 mod 7 p11n 6 E 0 mod 11 and he conjectured further such congruences modulo arbitrary powers of 5 7 and 11 Although the work of A O L Atkin and G N Watson settled these conjectures many years ago the congruences have continued to attract much attention For example subsequent works by G Andrews A OL Atkin F Garvan D Kim D Stanton and H P F Swinnerton Dyer An G G G K S At Sw in the spirit of F Dyson have gone a long way towards providing combinatorial and physical explanations for their existence Ramanujan Ra p xix already observed that his congruences were quite special For instance he proclaimed that It appears that there are no equally simple properties for any moduli involving primes other than these three ie m 5 7 11 1991 Mathematics Subject Classi cation Primary 111383 Secondary 05A17 Key words and phrases partition function The Erd s7 Conjecture Newman s Conjecture The author is supported by NSF grants DMS9508976 DMS9874947 and NSA grant MSPR 97Y012 Typeset by AMS TEX 2 KEN ONO Although there is no question that congruences of the form pan b E 0 mod m are rare see recent works by the author K Ol Ol 02 the question of whether there are many such congruences has been the subject of debate In the 19607s Atkin and O7Brien Atl At2 At Ob uncovered further congruences such as 1 p11313n 237 E 0 mod 13 However no further congruences have been found and proven since In a related direction P Erdos and A lvic conjectured that there are infinitely many primes m which divide some value of the partition function E l and Erdos made the following stronger conjecture G0 I Conjecture Erdos Ifm is prime then there is at least one non negative integer nm for which pnm E 0 mod A Schinzel see E l for the proof proved the Erdos lvic conjecture using the Hardy Ramanujan Rademacher asymptotic formula for pn and more recently Schinzel and E Wirsing Sc W have obtained a quantitative result in the direction of Erdos7 stronger con jecture They have shown that the number of primes m lt X for which Erdos7 Conjecture is true is gtgt log log X Here we present a uniform and systematic approach which settles the debate regarding the existence of further congruences and yields Erdos7 Conjecture as an immediate corollary Theorem 1 Let m 2 5 be prime and let k be a positive integer A positive proportion of the primes i have the property that mk gn l p E 0 mod m 24 for every non negative integer n coprime to E In view of work of S Ahlgren A J L Nicolas I Z Ruzsa A sarkozy and J P Serre Ni R Sa for m 2 the fact that p3 3 and Theorem 1 we obtain Corollary 2 Erdo39s Conjecture is true for every prime m Moreover ifm 31 3 is prime then if m 2 ognngpWEO mOdmgtgtmX ifm25 Surprisingly it is not known whether there are infinitely many n for which pn E 0 mod 3 THE PARTITION FUNCTION MODULO m 3 As an example we shall see that X 59 satis es the conclusion of Theorem 1 when m l3 and k I In this case by considering integers in the arithmetic progression r E 1 mod 24 59 we find for every non negative integer n that 2 M594 1371 111247 E 0 mod 13 Our results are also useful in attacking a famous conjecture of M Newman N1 Conjecture Newman Ifm is an integer then for every residue class r mod m there are in nitely many non negative integers n for which pn E r mod Works by Atkin Newman and O Kolberg At N1 K have veri ed the conjecture for m 2 5 7 11 and 13 in fact the case where m 11 is not proved in these papers but one may easily modify the arguments to obtain this case Here we present a result which in principle may be used to verify Newman7s Conjecture for every remaining prime m 31 3 We shall call a prime m 2 5 g if for every r mod m there is a non negative integer nr for which mnr E 71 mod 24 and mnrl p 7 24 2 modm Theorem 3 Ifm 2 5 is a good prime then Newman s conjecture is true for m Moreover for each residue class r mod m we have OSngX pnEr modmgtgtrmXIOgX lflgrngL X if r 0 Although it appears likely that every prime m 2 13 is good proving that a prime m is good involves a substantial computation and this computation becomes rapidly infeasible as the size of m grows The author is indebted to J Haglund and C Haynal who wrote ef cient computer code to attack this problem As a result we have the following Corollary 4 Newman s conjecture is true for every prime m lt 1000 with the possible edception ofm 3 We also uncover surprising periodic relations for certain values of the partition function mod m In particular we prove that if m 2 5 is prime then the sequence of generating functions k m n l 3 Fm k z 2 2 p q mod m n20 mknEil mod 24 q 2 e27 throughout is eventually periodic in k We call these periods Ramanujan cycles Their existence implies the next result 4 KEN ONO Theorem 5 Ifm 2 5 is prime then there are integers 0 S Nm S 48m3 7 2m 7 l and l S Pm S 48m3 7 2m 7 1 such that for everyt gt Nm we have L 1 7 mpmi 1 mod m p 24 p 24 for every non negative integer rt For each class r mod m one obtains explicit sequences of integers nk such that pnk E r mod m for all k This is the subject of Corollaries 9 through 12 below For example taking rt 0 in Corollary 12 shows that for every non negative integer k 232k1 1 232k3 1 4 p E 5 mod 23 and p E 5k1 mod 23 24 24 Similarly it is easy to show that 1367 232 2 1 1297 23 1 5 p E 0 mod 23 and p E 0 mod 23 Congruences of this sort mod 13 were previously discovered by Ramanujan and found by M Newman N2 In fact this paper was inspired by such entries in Ramanujan7s lost manuscript on prt and 701 see B Ol A priori one knows that the generating functions Fmkz are the reductions mod m of weight 712 non holomorphic modular forms and as such lie in infinite dimensional Fm vector spaces This infinitude has been the main obstacle in obtaining results for the partition function mod m In 3 we shall prove a theorem see Theorem 8 which establishes that the Fm k z are the reductions mod m of half integral weight cusp forms lying in one of two spaces with Nebentypus Hence there are only finitely many possibilities for each Fm k This is the main observation which underlies all of the results in this paper We then prove Theorems 1 and 3 by employing the Shimura correspondence and a theorem of Serre about Galois representations In 4 we present detailed examples for 5 S m S 23 2 PRELIMINARIES We begin by defining operators U and V which act on formal power series If M and j are positive integers then 6 2 WW l WM 1 Z 1MHW 7120 7120 7 2 WW l V0 1 Z anqj 7120 7120 THE PARTITION FUNCTION MODULO m 5 We recall that Dedekind7s eta function is de ned by 8 712 1 1124 Hlt17 a 711 and that Rainanujan7s Delta function is 9 NZ 1 71242 the unique normalized weight 12 cusp form for SL2 If m 2 5 is prime and k is a positive integer then de ne 1m k n by 0 W 397 AMWMQ l lV24 10 gainamt 7 W Inod m Where 607111 2 7712 7 124 Recall the definition 3 of Fm kz Theorem 6 Ifm 2 5 is prime and k is 1 positive integer then Fm k z E Z amknq Inod 710 Proof We begin by recalling that Euler7s generating function for 1901 is given by the infinite product 0 0 1 WW I 7 go ll 1 W 7 711 Using this fact one easily finds that 771k k 0 0 k k Z l Ultmkgt 7 Zpltngtqi5ltmykgt Hlt17 qm gt7 l Ultmkgt 710 711 Emma mm awfme Hlt17 an 710 711 Where 1 S Mink S m 7 1 satisfies 24 mk E 1 mod Since 17 ka mk E 17 Xm2k Inod m we find that f pltmkn mm kgtgtqi quot Jfltquot E Mquot ltZgt Wk 710 11117 qwmk mod m 6 KEN ONO Replacing 1 by 124 and multiplying through by q mk one obtains 0 my 7 0 Zpltmkn Mm kq24 245 mkk 1 E Z am knq Inod 710 7 0 It is easy to see that 00 k 24n7u ltm kgt 1 mk t 1 n k mk 203 pm n mm m 2 3 p 24 q 7120 mknEil mod 24 QED We conclude this section with the following elementary result which establishes that the Fm k 2 form an inductive sequence generated by the action of the Um operator Proposition 7 Ifm 2 5 is prime and k is a positive integer then Fmk lz E Fmkz l Um Inod Proof Using definition of the Fmk z and the convention that Ma 0 for 04 Z Z one finds that Fmkz l Um mkn l W Z P 724 q WW 7120 mknEil mod 24 Z 7an 1 W P 24 q 7120 mk1n271 mod 24 E Fm k l 2 mod 3 PROOF OF THE RESULTS First we recall some notation Suppose that w E Z and that N is a positive integer with 4 l N if in Z Z Let SwP0NX denote the space of weight w cusp forms with respect to the congruence subgroup P0N and with Nebentypus character x Moreover if X is prime then let SwP0NXl denote the Fl Vector space of the reductions Inod X of the q expansions of forms in SwP0N x with rational integer coe icients THE PARTITION FUNCTION MODULO m 7 Theorem 8 Ifm 2 5 is prime then for every positive integer k we have FUR k 2 E Smtma Po576m7gtltgtlt 1m7 2 where X is the hon trivial quadratic character with conductor 12 and Xm is the usual Kro hecher character for Proof The Um operator de nes a map see Lemma 1 S Stl Um SAP04Nm1 SAP04Nm1Xm Therefore in view of Proposition 7 it su ices to prove that Fm 12 6 Sm27m71 P0676771 xm 2 If d E 0 mod 4 then it is well known that the space of cusp forrns SdP0l has a basis of the form d mamc aj 1g 3 Since the Hecke operator Tm is the same as the Um operator on 5125m71l 01m we know that V V Mung Um E Z ajAz3E4235m71 33 mod m 121 where the a E Fm However since A5m1z 150ml 7 7 it is easy to see that A SWJW l UW Z WW1 712710 where no 2 6m However since 6m I E Z one can easin deduce that no gt m24 The only basis forms in A W hl l Um Inod m are those Aj 2E4 235m71 3j where j gt m24 This implies that A25m 1 l U070 l V24 nm24z is a cusp forrn Since Az5m71 l l V24 is the reduction rnod m of a weight quot12271 cusp form with respect to P024 and 71242 is a weight 12 cusp form with respect to P0676 with character x the result follows QED Now we recall an important result due to Serre 648 8 KEN ONO Theorem Serre The set of primes X E 71 mod N for which f l T120 modm for every fz E SkP0NVm has positive density Here Tl denotes the usual Hecke operator of indea acting on SkP0N 1 Proof of Theorem 1 If Fmkz E 0 mod m then the conclusion of Theorem 1 holds for every prime Hence we may assume that Fmkz i 0 mod By Theorem 8 we know that each Fmk 2 belongs to SmLml F0576mxxfn 1m Therefore each 2 Fm k z is the reduction mod m of a half integral weight cusp form Now we brie y recall essential facts about the Shimura correspondence Sh a family of maps which send modular of forms of half integral weight to those of integer weight Although Shimura7s original theorem was stated for half integral weight eigenforms the generalization we describe here follows from subsequent works by Cipra and Niwa Ci Ni Suppose that fz 221 bnq E SAP04N11 is a cusp form where A 2 2 If t is any square free integer then define Atn by M btn2 715 n5 i I L8 7 111X51Xt 2 1 711 n Here X4 resp Xt is the Kronecker character for resp These numbers Atn define the Fourier expansion of Stfz a cusp form stltfltzgtgt 2 Z Atltngtqi 711 in 52AP04N112 Moreover the Shimura correspondence 5 commutes with the Hecke algebra In other words if pl 4N is prime then SM W192 SM l Tp Here Tp resp Tp2 denotes the usual Hecke operator acting on the space 52AP0 4N 1amp2 resp sngroaw Therefore for every square free integer t we have that the image StFm k under the t th Shimura correspondence is the reduction mod m of an integer weight form in SW2W2P0576mXtMU Now let Sm denote the set of primes X E 71 mod 576m for which G l T120 modm for every G E Sm27m2l 0576mXtrium By Serre7s theorem the set Sm contains a positive proportion of the primes THE PARTITION FUNCTION MODULO m 9 By the commutativity of the correspondence if X E Sm then we find that Fmkz l T 2 E 0 mod m where T 2 is the Hecke operator of index 2 on Sm2m1P0576mXxfn 1 In particular 2 see Sh if f Zafnq E SA NXf is a half integral weight form then 00 7 An lt11 f l m2 2 Z awn W Wafltngt Xflte2gtz2k1afltnw2gtgt q 710 Therefore if X E Sm and n is a positive integer which is coprime to E then by replacing n by n we have 7112777172 2 7112777174 1071 167153 X36551 2 am km E 0 mod Since 0 by Theorem 6 we find that mk gn 1 p 3 24 amk n 7 0 mod QED Remark Although Theorem 1 is a general result guaranteeing the existence of congruences there are other congruences which follow from other similar arguments based on 11 For example suppose that X is a prime for which Fmkz l T 2 E A Fmkz mod m for some AM 6 If n is a non negative integer for which 2 in then 11 becomes m27m72 am k H MD 7 xxfn 1 ltil mt2mi4 E am k 1M2 mod Hence if it turns out that m27m74 AM E if 2 mod m then there are arithmetic progressions of integers n for which W2 1 amkn 2 Ep E 0 mod 10 KEN ONO Although we have not conducted a thorough search it is almost certain that many such congruences exist Proof of Theorem 5 By the proof of Theorem 6 recall that mn 1 7 Fm12 2 p 24 q E Sm272m711 o576m7gtltm 7120 77171271 mod 24 Since m is good for each 0 S 7 S m 7 1 let n be a xed non negative integer for Which mnr E 71 mod 24 and mm l p 7 24 2 modm Let Mm be the set of primes p for which 1 l n for some 7 and de ne 6m by GM H p pEMm Obviously the form Fm 12 also lies in SmLMl P0576m6m gt07 Therefore by Serre7s 2 theorem and the commutativity of the Shimura correspondence a positive proportion of the primes X E 71 mod 5767716 have the property that Fm 12 l T 2 E 0 mod By 11 for all but finitely many such X we have for each 7 that 7112777172 mnr 2 l 71 2 n 7112771174 mm l X 7 E 0 d p 24 X g 2 p 24 m0 m However since X E 71 mod m this implies that 12 p E W 71W mod m If n pi Where the pi are prime then 1 U 1 THE PARTITION FUNCTION MODULO m 11 Since HT is odd X E 3 mod 4 and X E 71 mod 19 we find by quadratic reciprocity that pi W1 5 Pi Pi I 1 7 7 1 Pi Pi Therefore for all but nitely many such congruence 12 reduces to m2 13 p E W 71quot 2 2m 2r mod m Hence for every suf ciently large such E the m values 1 mg are distinct and represent each residue class mod m To complete the proof it suf ces to notice that the number of such primes lt X by Serre7s theorem again is gt X log X In view of 13 this immediately yields the log X estimate The estimate when 7 0 follows easily from Theorem I QED Proof of Theorem 5 Since Fmkz is in Sm2m1P0576mxxfn 1m it follows that 2 each Fmkz lies in one of two finite dimensional Fm vector spaces The result now follows immediately from 3 Theorem 6 Proposition 7 and well known upper bounds for the dimensions of spaces of cusp forms see C Ol QED 4 EXAMPLES In this section we list the Ramanujan cycles for the generating functions Fm k 2 when 5 S m S 23 Although we have proven that each Fm k z E Sm2m1 P0576mxxfn 1m 2 in these examples it turns out that they all are congruent mod m to forms of smaller weight Cases Where m 57 and 11 In view of the Ramanujan congruences mod 5 7 and 11 it is immediate that for every positive integer k we have F5kz E 0 mod 5 F7kz E 0 mod 7 Fllkz E 0 mod 11 12 KEN ONO Therefore these Ramanujan cycles are degenerate Case Where m 13 By Prop 4 Gr O it is known that A7z U13 E 11Az mod 13 Therefore by 10 and Theorem 6 it turns out that F13 12 2 11 11 9q35 E11n1124z mod 13 Using a theorem of Sturm Th 1 St one easily veri es with a finite computation that F13 12 T592 E 0 mod 13 By the proof of Theorem 1 we find that every non negative integer n E 1 mod 24 that is coprime to 59 has the property that 13593nl p 24 E 0 mod 13 Congruence 2 follows immediately Using Sturm7s Theorem again one readily veri es that 11 7 23 n 242 l Ul3 87 242 mod 13 7123242 U13 E 4n1124z mod 13 By Proposition 7 this implies that F132z E 10n23242 mod 13 and more generally implies that for every non negative integer k 14 F132k122 116kn11242 mod 13 15 F132k 22 2 10 6kn23242 mod 13 These two congruences appear in Ramanujan7s unpublished manuscript on Tn and pn and their presence in large part inspired this entire work From 14 and 15 we obtain the following easy corollary THE PARTITION FUNCTION MODULO m Corollary 9 De ne integers 1101 and bn by 2 WW I Hlt17 an 710 711 2 WW 1 a 23 710 711 Ifk and n are non negative integers then 2k1 p E 11 61 an mod 13 132 2 24 23 1 p 2106kbn mod 13 Case Where m 17 By Prop 4 Gr O it is known that A12z i Ul7 E 7E42A2 mod 17 Where E4 l 240 221 03 nq is the usual weight 4 Eisenstein series Therefore by 10 it turns out that F171z 2 7q7 16q31 E 7717242E424z mod 17 Again using Sturm7s theorem one easily veri es that 717242E4242 U17 E 7n23242E4242 mod 17 7123242E4242 U17 E l3n7242E424z mod 17 By Proposition 7 this implies that for every non negative integer k F17 2k 1 z E 7 6kn724zE4242 mod 17 F17 2k 2 z E 15 6kn23242E4242 mod 17 As an immediate corollary we obtain 14 KEN ONO Corollary 10 De ne integers C71 and dn by 20mm 2 E4ltzgt Hlt1i W77 710 711 2 dnq E4zH17 q 23 710 711 Ifk and n are non negative integers then 2k1 W E 75k 001 mod 17 p 24 172 2 24 23 1 p E156kdn mod 17 Case Where m 19 Using Prop 4 Gr O and arguing as above it turns out that for every non negative integer k F19 2k 1z2 5 10kn524zE624z mod 19 F192k 2z E 11 10kn2324zE624z mod 19 Here E6 17 504 221 7571an is the usual weight 6 Eisenstein series As an immediate corollary we obtain Corollary 11 De ne integers en 1nd n by Z eltngtqi E6ltzgt H lt1 e W 710 711 2 ing E6ltzgtHlt1e W23 710 711 Ifk and n are non negative integers then p 192k124n 5 1 24 p 192k224n 23 1 E 5 10 en mod 19 24 21110kfn mod 19 Case Where m 23 Using Prop 4 Gr O and arguing as above we have for every non negative integer k F23 2k 1 1 z E 5k724zE424zE624z mod 23 F23 2k 2 z E 5k1n23242E4242E624z mod 23 THE PARTITION FUNCTION MODULO m 15 Corollary 12 De ne integers gn and by 2 901W 2 E4lt2gtE6lt2 Hlt1e q n0 711 2 hnq E42E6z H 1 7 W23 3 H o 3 H H Ifk and n are non negative integers then k 24 7 5 gn mod 23 232k224n 23 1 p 24 232k124n 1 1 p E 5k1 mod 23 REFERENCES S Ahlgren Distribution of parity of the partition function in arithmetic progressions Indaga tiones Math to appear G E Andrews and F Garvan Dyson s crank of a partition Bull Amer Math Soc 18 1988 167171 A O L Atkin Multiplicative congruence properties and density problems for pn Proc London Math Soc 3 18 1968 563576 A O L Atkin and H P F SWinnertonDyer Modular forms on noncongruence subgroups Combinatorics Proc Sympos Pure Math Amer Math Soc XIX 1968 125 A O L Atkin and J N O Brien Some properties of pn and Cn modulo powers of 13 Trans Amer Math Soc 126 1967 442459 A O L Atkin and H P F SWinnertonDyer Some properties ofpartitions Proc Lond Math Soc 4 1954 84106 B C Berndt and K Ono Ramanujan s unpublished manuscript on the partition and tau functions with commentary Seminaire Lotharingien de Combinatoire 42 B Cipra On the NiwaShintani theta kernel lifting of modular forms Nagoya Math J 91 1983 49117 H Cohen and J Oesterl Dimensions des espaces de formes modulaires Modular functions of one variable VI Proc Second Int Conf Univ Bonn 1976 Springer Lect Notes 627 1977 6978 P Erdos and A Ivi The distribution of certain arithmetical functions at consecutive integers Proc Budapest Conf Number Th Coll Math Soc J Bolyai NorthHolland Amsterdam 51 1989 45 91 F Garvan New combinatorial interpretations of Ramanujan s partition congruences mod 5 7 and 11 Trans Amer Math Soc 305 1988 4777 F Garvan D Kim and D Stanton Cranks and tcores Invent Math 101 1990 117 B Gordon private communication A Granville and K Ono Defect zero pblocks for nite simple groups Trans Amer Math Soc 348 No 1 1996 331347 KEN ONO AI Ivi private communication II Kiming and JI Olsson Congruences like Ramanujan s for powers of the partition function Archi Mathi Basel 59 1992 825855 OI Kolberg Note on the parity of the partition function Mathi Scandi 7 1959 377378 MI Newman Periodicity modulo m and divisibility properties of the partition function Trans Ameri Math Soc 97 1960 225236 MI Newman Congruences for the coe icients of modular forms and some new congruences for the partition function Canadi J Math 9 1957 549552 JILI Nicolas II ZI Ruzsa and AI Sarkozy On the parity of additive representation functions with an appendix by JP Serre JI Number Thi to appear Niwa Modular forms of half integral weight and the integral of certain theta functions Nagoya Math J 56 1974 147161 KI Ono Parity of the partition function J reine angeWI mathi 472 1996 115 KI Ono The partition function in arithmetic progressions Mathi Annalen 312 1998 251 260 S Ramanujan Congruence properties of partitions Proci London Math Soc 2 19 1919 207210 A Schinzel and EI Wirsing Multiplicative properties of the partition function Proci Indian Acadi SCiI Mathi Sci 97 1987 297303 1 Serre Divisibilit de certaines fonctions arithm tiques L EnseinI Math 22 1976 227 260i 1 Serre and HI Stark Modular forms of weight 12 Springer Lect Notes 627 1971 2767 GI Shimura On modular forms of halfintegral weight Ann Math 97 1973 440481 J Sturm On the congruence of modular forms Springer Lect Notes 1240 1984 Springer Verlag 275280 DEPTI OF MATHI PENN STATE UNIVERSITY UNIVERSITY PARK PENNSYLVANIA 16802 USA E mail address ononathpsuedu Math Ann 312 2517260 1998 m Ann n 9 SpringerVerlag 1998 The partition function in arithmetic progressions Ken Ono Department of Mathematics Penn State University University Park PA 16802 USA email ono mathpsu e u Received 3 March 1998 Revised version 30 March 1998 In celebration ofGE Andrews 60 h birthday Mathematics Subject Classi cation 1991 05A17 11P83 1 Introduction and statement of results A partition of a nonnegative integer n is a nonincreasing sequence of positive integers Whose sum is n Euler gave the following generating function for pn the number of partitions of an integer n oo oo 1 pnqquot 1 lq2q23q35q47q5llq6 1 q n0 n1 Ramanujan observed various surprising congruences for pn when n is in certain very special arithmetic progressions For instance in Ra p xix Ramanujan proclaims I have proved a number ofarithmetic properties ofpnin particular that p5n 4 E 0 mod 5 and p7n 5 E 0 mod 7 I have since found another method which enables me to prove all of these properties and a variety ofothers ofwhich the most striking is pl 1n 6 E 0 mod 11 There are corresponding properties in which the moduli are powers of 5 7 or 11 It appears that there are no equally simple propertiesfor any moduli involving primes other than these three The author is supported by NSF grant DMS9508976 and NSA grant MSPR97Y012 252 K Ono There are now many proofs of these congruences and their generalizations in the literature for instance see Ar AnG At G GKiSt HHu W often involving modular equations and various combinatorial constructions Although subsequent works show that there are indeed congruences where the modulus contains prime divisors other than 5 7 and ll it is still widely believed as Ramanujan suggested that simple congruence properties are rare The quanti cation of this expectation has remained as one of the open problems in t e area For instance there do not seem to be any such congruences modulo 2 or 3 The parity of pn seems to be quite random A widely believed Folklore Conjecture asserts that pn is equally often even and odd39 that is that pn is even for N X positive integers n g X Parkin and Shanks PS conducted the rst extensive numerical study and their evidence strongly supports the Folklore Conjecture In the direction of this conjecture Nicolas Ruzsa and sark39ozy N R S Se have proved that N gX lpN is even gtgt xf lo X 2 M gX l pM is odd gtgt V exp lt7log2egt Subbarao Su made the following conjecture on the parity of pn for those integers n belonging to any given arithmetic progression Conjecture 1 In every progression r mod t there are in nitely many M E r mod t for which pM is add and in nitely many N E r mod t for which pN is even This conjecture had been proved for every arithmetic progression with mod ulus t see 0 for precise references where r e 12345681012162040 using a variety of elegant combinatorial methods from the works of Garvan Kolberg Hirschhorn Stanton and Subbarao Note This corrects the list of such t that appears in O The author carelessly omitted t 6 8 and 20 In 0 the author went a step further by proving that in any progression r mod t there are in nitely many N E r mod t for which pN is even and that there are in nitely many M E r mod t for which pM is odd provided there is one such M Furthermore if there is such an M then the rst one is less than an explicit constant C lt 101 t7 Hence the even case of Conjecture 1 has now been veri ed for every pro gression but the odd case remains open However we have a simple algorithm to determine the truth of the odd case for any given progression r mod t Compute pM mod 2 forM rr t r 2t for all suchM up to C As soon as we nd one odd number we have veri ed the conjecture If all these numbers are even then we have proved that the conjecture is false Using an ef cient version of this algorithm K Burrell Universal Analytics Inc veri ed the odd case of Conjecture l for every progression r mod t with t g 105 The partition function in arithmetic progressions 253 Recently Ahlgren A and Serre N R SSe have quanti ed the author s results on Conjecture l by obtaining estimates for the number of even resp odd values of pN for integers N lying in an arithmetic progression Both Ahlgren and Serre have proved that in every progression r mod I N gX l N E r mod I andpN is even gtgt and Ahlgren proved that M gX lM E r mod I andpM is odd gt W logX provided there is at least one such M Returning to Ram anuj an s claim that simple congruence properties are rare we rst make the well known observation that his congruences maybe described in a convenient way If E 57 7 or ll then for every nonnegative integer n 3 p n r E 0 mod K where 71 E 24 1 mod Z In this paper we rst consider a re nement of the odd case of Conjecture 1 In view of 3 it is natural to attack the following conjecture Conjecture 2 IfI is prime Ihen in every ariIhmeIic progression 24 1 r mod I Ihere are in niIely many M E r mod I for which pM is odd In view of the author s earlier work Conjecture 2 was known to be true for every prime I g 105 but not for any other primes As a consequence of a general theorem that is proved in Sect 3 see Theorem 4 we obtain the following result Theorem 1 ConjecIure 2 is Irue for a seI of primes wiIh densin exceeding 7 10150039 In Sect 4 we shall prove a general result see Theorem 5 which goes some way towards quantifying Ramanujan s assertion that simple congruence prop erties are rare We consider the following generalization of Conjecture 2 Conjecture 3 LeI E be prime IfI is prime Ihen in every progression 24 1 r mod I Ihere are in niIely manyM E r mod Ifor whichpM 0 mod Z As an immediate corollary to Theorem 5 we obtain Theorem 2 IfZ is an odd prime Ihen Conjecture 3 is Irue for a seI ofprimes I wiIh densin exceeding 1 7 W In Sect2 we develop essential preliminaries that are important to the se quel In particular we prove Theorem 3 the main vehicle for obtaining non congruences In Sect 3 we rst consider the parity of the partition function and in Sect 4 we consider the more general case of its reduction modulo odd primes 254 K Ono 2 Preliminaries In this section we develop the essential preliminaries regarding modular forms see K for background As usual if k is a positive integer then let SkF1N denote the space of weight k cusp forms with respect to the congruence subgroup H N Similarly if 11 is a Dirichlet character modulo N then let Sk N 11 denote the space of weight k cusp forms with respect to the congruence subgroup F0 N with Nebentypus character 11 As usual we shall identify all such modular forms f z by their Fourier expansions oo fz 2mgquot quot0 Here q e27m is the uniformizing variable for the point at in nity We begin with the following well known Lemma Lemma 1 11 Sect3 Prop 17 b IQ Iffz 21 anq E SkN7 11 and X is a Dirichlet character modulo t then 1342 Zxnanqquot e skavmxzi Now we recall the Hecke operators Iffz 21 anq E SkN7 11 and p 1N is prime then the Hecke operator T077 k7 11 acts on f z and returns the cusp form 4 TOLkWMTz Z anppk 1 panp qquot 6 WNW Here anp 0ifp1n Lemma 2 Letfz 21 anq E SkN11 and X a Dirichlet character modulo t pr 1Nt2 isprime then Tp7 k7 11X2D Xz E SkNt27 112 and is given by Tp7k7 3ifxz ZXW nppk 1 panp qquot Proof That Tk XZVXz E SkNt211X2 is immediate from Lemma 1 and 4 The claim follows immediately by 4 and the de nition of fXz since 00 Tp7k xzifxz i Z Xnpanppk l pp Xnpanp qquot quot1 Using Dirichlet orthogonality we shall obtain the following result The partition function in arithmetic progressions 255 Lemma 3 Suppose thatfz 21 anq E SkN1 and let 1 g r lt t be integersfar which gcdr7 t l pr thZ is prime then Frzpz Z anpqquotpk1 ltp 2 wow 6 show nErp mod nEr mod Proof Recall Dirichlet s theorem that for every integer n 5 2 WM 350 1fn E r mod t7 Xmod 2 otherwise lfp th2 then de ne Frtpz by l Frzpz Z xltm2TltpkWvXzA 151 Xmodz It is easy to see that Frtpz E SkF1Nt2 since eacth E SkF1Nt2 By Lemma 2 and 5 we nd that Frzpz L Z XrP2ZXnpanppk 1 panpqquot Xmodz quot1 Z Z Xrpzxnpanppk 1 anpqquot quot1 Xmodz Z anppk 1 panp q anrpz mod Z anpqquotpk1 ltp Z awnquot nErp mod 2 nEr mod 2 D Using a theorem of Sturm and Lemma 3 we obtain the following general theorem guaranteeing the existence of nonzero coef cients in arithmetic pro gressions Theorem 3 Let E be prime Iffz 21 anq E SkN has integer coef cients and l g r lt t are coprime integersfar which there is an no E r mod t with an0 0 mod Z then for every su iciently large prime p l ZNt2 there is an integer n for which n E rp mod t and anp 0 mod Z 256 K Ono Proof Sturm Theorem 1 Stu proved that if gz 21 bnq E SkF1Ng has integer coef cients and has the property that bn E 0 mod Z for every k 1 6 n CkNgENgZH 1717 MM then 9 E 0 mod I ie bn E 0 mod I for every n Suppose that p i NI2 is a prime for which p gt CkNt2 and suppose that there are no integers n E rp mod I for which anp 0 mod Z Then by Lemma 3 we nd that Frtp39z E SkF1Nt2 and FVylypz Epk lwp 2 MW mod 0 nEr mod Hence F rt7 p39z 0 mod I but has the property that the rst exponent with nonzero coef cient modulo Z is a positive multiple of p By hypothesis this is larger than C kNt2 and therefore contradicts Sturm s theorem 6 This proves that if p is suf ciently large then there are integers n E rp mod I for which anp 0 mod Z This completes the proof D 3 Application to the parity of the partition function Now we apply the results of Sect 2 to the parity of pn The Dedekind eta function is the principal modular form of interest in this paper39 it is de ned by the in nite product 00 L 772 1 q H1 7 qquot quot1 As usual let Az denote the unique normalized weight 12 cusp form with respect to SLZ In terms of 772 it is given by M 77242 q H1 7 W3 The following fundamental fact will be very important see 0 for details Lemma 4 Proposition 1 O For a given positive integer t letj be a positive integerfor which 2 gt 2 7 De neftlz by 122 M24 Emmott Thenfwz is in S2121152t7 X2 and its Fourier expansion satis es 7mm Zaimqquot 2 Zpnq 1gt 2 mod 2 The partition function in arithmetic progressions 257 Here X2 denotes the usual Kronecker character for 1905 In view of this Lemma we obtain the following easy Lemma Lemma 5 Ift is a positive integer then letj be any nonnegative integerfor which 2 gt t24 There is an integer n E r mod t for which pn is odd if and only ifthere exists an integer n E 24r 7 1 mod 24t for which alln is odd Proof By 7 it is easy to see that 7172 24t2k121 allW E Zp mod 2 k 0 The result now follows easily D In view of these preliminary lemmas and Theorem 3 we obtain the following general theorem Theorem 4 Let 0 g r lt t be integersfor which gcd24r 7 17 t l Ifthere exists an integer n E r mod t for which pn is odd then for every integer s coprime to 24t there are in nitely many integers M E s2r 7 24 1 24 1 mod tfor which pM is odd Proof Letj be a positive integer for which 2 gt t24 and letfw 2 be as de ned in Lemma 4 By Lemma 5 there is an integer n0 E 24r7l mod 24t for which alln0 is odd By Theorem 3 for every suf ciently large prime p there is an integer m E 24r 7 lp mod 24t for which LIAmp is odd In particular for every residue class s mod 24t with gcds24t l we nd an integer m E 24r 7 ls2 mod 24t for which LING is odd Therefore by Lemma 5 again for each such s there are integers M E s2r 7 24 1 24 1 mod t for which pM is odd Hence by Main Theorem 2 0 there are in nitely many such M for which pM is odd D Corollary 1 Ift gt 3 is prime and there are two integers no and n1 for which i 1010 E 1011 E 1 mod 27 11 247271 24711171 717 then in every progression 24 1 r mod t there are in nitely many M E r mod tfor which pM is odd Proof Since t is prime the only r mod t for which gcd24r 7 17 t 7 l is the residue class r E 24 1 mod t Since t is prime it is easy to see that Theorem 4 will cover all the residue classes 24 1 r mod t We now have an algorithm for proving Conjecture 2 for almost every prime Given any nite set of integers n17 n27 n5 for which pnl are odd simply nd 258 K Ono 2 any 1 g i 7j g s A MAPLE calculation that computed pn mod 2 for every n 15000 yields Theorem 1 all the arithmetic progressions of primes for which WWI 71 for 4 The partition function modulo 2 In this section we consider the reduction of pn modulo odd primes Z for those n belonging to an arithmetic progression We begin with the following important lemma Lemma 6 Let be an oddprime andt apositive integer Ifj is apositive integer for which If gt 24t then n1 576tz n 3 men gaalmnh 242 ES2417X21 where XMJ is the usual Kronecker characterfor Q V il i1 6t Moreover the Fourier expansion offt7 Zquotzfactors modulo E as fem2 Zaam39miqquot 2 n1 8 E Zpnq24nilgt lt Z 71kq242 5k11gt mod n4 16700 Proof Gordon Hughes Ligozat and Newman proved the following well known fact about etaproducts If N is a positive integer and f z Hm 77 6z is an etaproduct for which N gcdd 52r5 gt o gcdd gm N l Eon E 0mod 247 2 En E 0mod 247 and a 6W 6W am for every integer d l N then fz E SkNX where k E6 N r5 s Hm 6 and X is the Kronecker character for Q 7lks Thatft j39z E S4r1243t7 X2 is now immediate By combining Euler s Pentagonal Number Theorem Corollary 17 An that 00 oo Hawquot Zoom quot1 700 with the fact that l 7X E 1 7X2 mod Z we obtain 8 from 1 D The partition function in arithmetic progressions 259 Lemma 7 Let be an oddprime t apositive integer andj an integerfor which If gt 24t There is an integern E r mod tfor whichpn 0 mod I ifand only ifthere is an integer n E 24r 71 mod 24tfor which at j39n 0 mod Z Proof This follows immediately from 8 since 00 2 7 k n 724tZ6k1 1 storm Zeo f k7oltgt mod Z In view of Theorem 3 and Lemmas 6 and 7 we prove Theorem 5 Let 0 g r lt t be integersfor which gcd24r 7 lt l and let E be an odd prime Ifthere is an integer n E r mod t for which pn 0 mod K then for every integer s coprime to 24t there are in nitely many M E s2r 7 24 1 24 1 mod tfor which pM 0 mod Z Proof Letj be a positive integer for which If gt 24t and letft j39z be as in Lemma 6 By Theorem 3 and Lemma 7 if gcds7 24t l andp E s mod 24t is a suf ciently large prime then there is an n for which n E 24r 7 1 mod 24t and at j39np 0 mod E For such an n we see that np E 24r 7 ls2 mod 24t lfFz is the cusp form see Lemma 20 de ned by FZ i Z Clown n24r71sl mod 24 then Fz 0 mod Z Suppose that there are only nitely many integers say mhmzp i imc for which i m E s2r 7 24 1 24 1 mod t7 ii pm 0 mod K It then follows from Lemma 6 and the proof of Lemma 7 that 0 2 aOJo mM nE24r71sz mod 24 c 00 2 9 E Z Z 71kpmlq24M6kl 24m71 mod Z 11 17700 By a simple generalization of the proof of Lemma lO one easily shows that there are no modular forms whose qseries expansions satisfy 9 Therefore there must indeed be in nitely many integers m E s2r7 24 124 1 mod t for which pm 0 mod K D As an immediate corollary we obtain 260 K Ono Corollary 2 IfZ andt gt 3 are addprimes and there are two integers no and n1 for which 139 Pno17n10 modZL ii 247271 24711171 717 then in every arithmetic progression 24 1 r mod t there are in nitely many integersM E r mod tf0r which pM 0 mod Z Remark 1 Let E be prime By Corollaries l and 2 since 70 71 1 0 mod Z for any prime t gt 3 with L1 71 every arithmetic progression 24 1 r mod t has the property that there are in nitely many M E r mod t withpM 0 mod Z This holds for every prime t for which A MAPLE calculation that computed pn for every n g 750 yields Theorem 2 Almost certainly one can obtain a better density by computing many more values ofpn mod Z Acknowledgements The author thanks the referee and K Ribet for making many suggestions that improved and clari ed the exposition of this paper References A S Ahlgren The Distribution ofparity of the partition mction in arithmetic progressions preprint An G E Andrews The Theory of Partitions AddisonWesley 197 6 AnG G E Andrews F Garvan Dyson s crank of a partition Bull Amer Math Soc 18 1988 1677171 At AOL Atkin Proof of a conjecture of Ramanujan Glasgow J Math 8 1967 14732 G F Garvan New combinatorial interpretations of Ramanujan s partition congruences mod 5 7 and 11 Trans Amer Math Soc 305 1988 47777 GKiSt F Garvan D Kim D Stanton Cranks and tcores Invent Math 101 1990 1717 HHu M Hirschhom D Hunt A simple proof of the Ramanujan conjecture for powers of 5 J Reine Ange Math 336 1981 1717 K N Koblitz Introduction to elliptic curves and modular forms SpringerVerlag 1984 NRSSe JL Nicolas I Z Ruzsa A Sarkozy Appendix by JP Serre On the parity of the additive representation functions preprint O K Ono Parity of the partition function in arithmetic progressions J reine angew Math 472 1996 1715 PS T R Parkin D Shanks On the distribution of parity in the partition mction Math Comp 21 1967 466480 Ra S Ramanujan Congruence properties of partitions Proc London Math Soc 2 19 1919 2077210 Stu J Sturm On the congruence of modular forms Springer Lect Notes 1240 Springer 1984 Su M Subbarao Some remarks on the partition mction Amer Math Monthly 73 1966 85 7 54 W GN Watson Ramanujan s vermutung ber zerfallungsanzahlen J reine angew Math 179 1938 977128 H H H H to 03 F U a T 00 to Publications Embedding property of somewhere injectiue J holomorphic curves in Calabi Yau three folds jointed with K Zhu submitted arXiv08053581 Lagrangian Floer theory on compact toric manifolds I jointed With Fukaya Ohta and Ono submitted arXiv08021703 Floer trajectories with immersed nodes and scale dependent gluing submitted preprint 2007 arXiv07114187 Lagrangian intersection Floer theory anomaly and obstruction research mono graph jointed with K Fukaya H Ohta and K Ono to be published in 2 volumes of AMSlnternational Press monograph series in International Press This is the nal version of the 2000 preprint which is now about 1385 pages TT u 39 L 139 TT u The group 0 phisins and flows sub mitted for the Proceedings for the Snowbird Summer Research Conference 2007 Canonical models of ltered AGO algebras and Morse complexes jointed With K Fukaya H Ohta and K Ono Proceedings for Yasha Fest CRM Proceedings and Lecture Notes vol 49 2009 in press Floer mini mar theory the C erf diagram and the spectral inuariants J Korean Math Soc 46 2009 3637447 Locality of continuous Hamiltonian flows and Lagrangian intersection with conormals J Gokova Geom Topol GGT 1 2007 1732 u 1 I 139 The group of quot phisum and 00 S Muller J Symplectic Geom 5 2007 no 2 1677219 topology jointed With Floer cohomology and disc instantons of Lagrangian torus bers in Fano toric mani folds jointed with Cheol Hyun Cho Asian J Math 10 2006 773 814 Floer homology in symplectic geometry and mirror symmetry Proceedings of lCM 2006 pp 879 905 Madrid 2006 EMS jointed with K Fukaya Lectures on Floer theory and spectral inuariants of Hamiltonian flows the proceedings of the Morse theoretic methods in non linear analysis and symplectic topology Seminaire de Mathematique Superieure Summer School University of Montreal pp 321416 2005 03 q 01 a 00 to 0 H to DJ F U a Spectral invariants analysis of the Floer moduli spaces and geometry of the Hamilto nian di eomorphism group Duke Math J 130 2005 199 295 Deformation of coisotropic submanifolds and strongly homotopy Lie algebroids jointed with JaeSuk Park Invent Math 161 2005 287 360 Spectral invariants and length minimizing property of Hamiltonian paths Asian J Math 9 2005 1 18 Construction of spectral invariants of Hamiltonian di eomorphisms on general sym plectic manifolds in The Breadth of Symplectic and Poisson Geometry Prog Math 232 525 570 Birkhauser Boston 2005 Normalization of the Hamiltonian and the action spectrum J Korean Math Soc 42 2005 65 83 Holomorphic volume preserving maps and special Lagrangian submanifolds Proceed ings for SlSTAG conference 2001 AMS Contemp Math 314 2002 pp 199 207 C hain level Floer theory and Hofer s geometry of the Hamiltonian di eomorphism group Asian J Math 6 2002 799 830 Lagrangian intersection Floer theory anomaly and obstruction research mono graph jointed with K Fukaya H Ohta and K Ono monograph preprint 2001 about 300 pages Floer homology and its 39 39t for u a pa t g L f 1 Proceeding y of the 7th Gokova Geometry Topology conference Turk J Math 25 2001 103 124 Quantization of Eilenberg Steenrod axioms via Fary functors With Rajesh Kasturi rangan RIMS preprint 2000 Floer homology of open subsets and a re nement of Arnol d s conjecture With Rajesh Kasturirangan Math Z 236 2001 151 189 Structure of the image of pseudo holomorphic discs with totally real boundary con dition with Daesung Kwon Comm Anal Geom 8 2000 31 82 Naturality of Floer homology of open subsets in Lagrangian intersection theory Pro ceedings of Paci c Rim Geometry Conference 1996 pp 261 280 eds by J G Choe International Press 1998 Symplectic topology as the geometry of action functional H Pants product and coho mological invariants Comm Anal Geom 7 1999 1755 1 00 to 0 H to 03 F U a T 00 to Generating functions uersus action functional with D Milinkovic CRM Proceedings and Lecture Notes V01 15 pp 107 125 edsby F Lalonde 1998 AMS On the structure of pseudo holomorphic discs with totally real boundary conditions J Geom Anal 7 1997 3057327 Gromou Floer theory and disjunction energy of Lagrangian embeddings Math Rec Lett 4 1997 8957905 Floer homology as the stable Morse homology with Darko Milinkovic Jour Korean Math Soc 34 1997 106571087 Symplectic topology as the geometry of action functional I Relatiue Floer theory on the cotangent bundlei Jour Diff Geom 46 1997 4997577 Zero loop open strings in the cotangent bundle and Morse homotopy With Kenji Fukaya Asian J Math 1 1997 967180 Fredholm regularity of Floer s pseudo holomorphic trajectories on Ka39hler manifolds Kyungpook Math J 37 1997 1537164 Floer cohomology spectral sequences and the Maslou class of Lagrangian embeddings Intern Math Res Notices No 7 1996 3057346 Relatiue Floer and quantum cohomology and the symplectic topology of Lagrangian submanifolds Proceedings for the 1994 Symplectic Topology program 7Contact and Symplectic Geometryi Publ of the Newton Institute eds by C B Thomas pp 2017267 Cambridge University Press 1996 Cambridge England Fredholm theory of holomorphic discs under the perturbation of boundary conditions Math Z 222 1996 5057520 Recent aduances in the Floer theory of r 39 L quotr J and its Hquot 39 Proceedings for the 1995 TGRC Geometry Workshop V01 6 1995 1217161 eds by C Y Park TGRC KOSEF Taegu Korea Uncertainty principle non sqeezing theorem and the symplectic rigidity Proceedings for the 1995 Daewoo Workshop iTopology and Geometryi V01 15 part III 1995 947113 eds by D Lee and J S Lee GARC Addendum to Floer cohomology of Lagrangian intersections and pseudo holomorphic discs Iquot Comm Pure Appl Math 48 1995 12997 1302 4 O 4 H 42 4 OJ 4 q 45 4 a 4 1 4 00 4 to 5 O 51 52 5 OJ 5 q Riemann Hilbert problem and application to the perturbation theory of analytic discs Kyungpook Math J 35 1995 39 76 Floer cohomology of Lagrangian intersections and pseudo holomorphic disks 1 Arnol d Giuental conjecture Floer Memorial Volume ed by H Hofer C Taubes A Weinstein and E Zehnder Birkh39aiuser 1995 5557573 Mean curvature and symplectic topology of Lagrangian submanifolds in Einstein Kahler manifolds Math Z 216 1994 471 482 Floer cohomology of Lagrangian intersections and pseudo holomorphic disks H 39 the case CPn RP Comm Pure Appl Math 46 1993 99571012 Floer cohomology of Lagrangian intersections and pseudo holomorphic disks 1 Comm Pure Appl Math 46 1993 9497994 i r L I J Volume of g g Math Z 212 1993 1757192 TT u under deformations Floer cohomology and Arnol d Giuental s conjecture of Lagrangian intersections C R Acad Sci Paris t315 1992 3097314 Remoual of boundary singularities ofpseudo holomorphic curves with Lagrangian bound ary conditions Comm Pure Appl Math 45 1992 1217139 Tight lagrangian submanifolds in CF Math Z 207 1991 4097416 Second uariation and stabilities of minimal lagrangian submanifolds in Kahler mani folds Invent Math 101 1990 5017519 On positiue multi lump bound states of nonlinear Schrodinger equations under multiple well potentials construction and instability Commun Math Phys 131 1990 2237 253 A symplectic xed point theorem on CP X TZk Math Z 203 1990 5357552 The dynamics of coupled planar rigid bodies part II J Dynamics and Diff Eq 13 1989 269 298 with P Krishnaprasad J Marsden and N Sreenath Cauchy problem and Ehrenfest s law of nonlinear Schrodinger equations with poten tials J Diff Eq 812 1989 2557274 Lyapunou stability of semiclassical bound states for nonlinear Scho39dinger equations with potentials Commun Math Phys 121 1989 11733 5 U 56 5 1 58 Existence of semiclassical bound states for nonlinear Scho39dinger equations with poten tials of the class Va7 Commun Part Diff Eq 1312 1988 149971519 The dynamics of coupled planar rigid bodies part I7 Dynamics and Stability of Systems 3 1988 257497 with P Krishnaprasad7 J Marsden and N Sreenath A stability criterion for Hamiltonian systems with symmetry7 J Geom Phys 4 1987 1637182 Some remarks on the transuerse Poisson structure of coadjoint orbits7 Lett Math Phys 12 1986 87791
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'