Intermediate Algebra MATH 101
Popular in Course
verified elite notetaker
Popular in Mathematics (M)
This 13 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 25 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
ADDITION AND COUNTING THE ARITHMETIC OF PARTITIONS SCOTT AHLGREN AND KEN ONO At first glance the stuff of partitions seems like child7s play 431222111111 Therefore there are 5 partitions of the number 4 But as happens in Number Theory the seemingly simple business of counting the ways to break a number into parts leads quickly to some dif cult and beautiful problems Partitions play important roles in such diverse areas of mathematics as Combinatorics Lie Theory Representation Theory Mathematical Physics and the theory of Special Functions but we shall concentrate here on their role in Number Theory for which A is the standard reference lN THE BEGINNING THERE WAS EULER A partition of the natural number n is any non increasing sequence of natural numbers whose sum is n by convention we agree that 190 l The number of partitions of n is denoted by Eighty years ago Percy Alexander MacMahon a major in the British Royal Artillery and a master calculator computed the values of 1901 for all 11 up to 200 He found that p200 3972999 029388 and he did not count the partitions one by one 20019911982198111973 lnstead MacMahon employed classical formal power series identities due to Euler To develop Euler7s recurrence we begin with the elementary fact that if lt 1 then 1 1 1xx2x3x4 1991 Mathematics Subject Classi cation Primary 11P83 Key words and phrases Partitions Ramanujan Congruences Both authors thank the National Science Foundation for its support The second author thanks the Alfred P Sloan Foundation the David and Lucile Packard Foundation and the Number Theory Foundation for their support Typeset by AMS TEX 2 SCOTT AHLGREN AND KEN ONO Using this Euler noticed that when we expand the in nite product 1336 1xx2x31x2x41x3x6 18 1 n the coef cient of at is equal to 1901 think of the first factor as counting the number of 1s in a partition the second as counting the number of 2s and so on In other words we have the generating function 0 0 1 W 71 22 33 54 EMMQE 7111171 x x x x 1 Moreover Euler observed that the reciprocal of this infinite product satisfies a beautiful identity also known as Euler7s Pentagonal Number Theorem 1715 271k3k2k2 1772x5x7712 7 1 k7ltxgt 18 71 These two identities show that 17x725x77x127 1 710 which in turn implies for positive integers n that pm pn 7 1 pn2 7190175 719017 7 1901 7 12 This recurrence enabled MacMahon to perform his massive calculation HARDY RAMANUJAN RADEMACHER ASYMPOTOTIC FORMULA FOR pn It is natural to ask about the size of The answer to this question is given by a remarkable asymptotic formula discovered by G H Hardy and Ramanujan in 1917 and perfected by Hans Rademacher two decades later This formula is so accurate that it can actually be used to compute individual values of Mn Hardy called it one of the rare formulae which are both asymptotic and exact77 It stands out further in importance since it marks the birth of the circle method which has grown into one of the most powerful tools in analytic number theory Here we introduce Rademacher7s result He defined explicit functions Tq such that for all n we have 00 1971 ETA q1 ADDITION AND COUNTING 3 The functions Tq are too complicated to write down here but we mention that T1 alone yields the asymptotic formula 1 7n 2713 11 N e plt Aimg In their original work Hardy and Ramanujan used slightly different functions in place of the Tq As a result their analogue of the series 231 Tq was divergent although still useful Moreover Rademacher computed precisely the error incurred by truncating this series after Q terms In particular there exist explicit constants A and B such that A B PM Z Tq lt m q1 Since 1901 is an integer this determines the exact value of 1901 for large n The rate at which Rademacher7s series converges is remarkable for example the first eight terms give the approximation p200 3 972 999 029 388004 compare with the exact value computed by MacMahon To implement the circle method requires a detailed study of the analytic behavior of the generating function for Recall that we have 0 n 1 Fx gum This is an analytic function on the domain lt l A natural starting point is Cauchy7s Theorem which gives p01 3 7m 0 at where O is any simple closed counter clockwise contour around the origin One would hope to adjust the contour in relation to the singularities of in order to obtain as much information as possible about the integral But consider for a moment these singularities they occur at every root of unity forming an impenetrable barrier on the unit circle In our favor however it can be shown that the size of near a primitive q th root of unity diminishes rapidly as 1 increases moreover the behavior of near each root of unity can be described with precision Indeed with an appropriate choice of O the contribution to the integral from all of the primitive q th roots of unity can be calculated quite precisely The main contribution is the function Tqn a detailed analysis of the errors involved yields the complete formula The circle method has been of extraordinary importance over the last eighty years It has played a fundamental role in additive number theory in Waring type problems for instance analysis and even the computation of black hole entropies dac 4 SCOTT AHLGREN AND KEN ONO RAMANUJAN7S CONGRUENCES After a moments re ection on the combinatorial de nition of the partition function we have no particular reason to believe that it possesses any interesting arithmetic prop erties the analytic formula of the last section certainly does nothing to change this opinion There is nothing for example which would lead us to think that pn should exhibit a preference to be even rather than odd A natural suspicion therefore might be that the values of pn are distributed evenly modulo 2 A quick computation of the first 10000 values confirms this suspicion of these 10000 values exactly 4996 are even and 5004 are odd This pattern continues with 2 replaced by 3 of the first 10000 values 3313 3325 and 3362 in each case almost exactly one third are congruent respectively to 0 1 and 2 modulo 3 When we replace 3 by 5 however something quite different happens we discover that 3611 many more than the expected one fifth of the first 10000 values of pn are divisible by 5 What is the explanation for this aberration The answer must have been clear to Ramanujan when he saw MacMahon7s table of values of The table listed these values starting with n 0 in five columns So Ramanujan would have seen something like the following 1 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 297 385 490 627 792 1002 1255 1575 1958 2436 3010 3718 4565 What is striking of course is that every entry in the last column is a multiple of 5 This phenomenon which persists explains the apparent aberration above and was the first of Ramanujan7s ground breaking discoveries on the arithmetic of Here is his own account I have proved a number of arithmetic properties of pnin particular that p5n 4 E 0 mod 5 p7n 5 E 0 mod 7 I have since found another method which enables me to prove all of these properties and a variety of others of which the most striking is p11n 6 E 0 mod 11 There are corresponding properties in which the moduli are powers of 57 or 11 It appears that there are no equally simple properties for any moduli inuoluing primes other than these three ADDITION AND COUNTING 5 Ramanujan proved these congruences in a series of papers the proofs of the congru ences modulo 5 and 7 are quite ingenious but are not terribly dif cult while the proof of the congruence modulo II is much harder In these same papers he sketched proofs of extensions of these congruences for example p25n 24 E 0 mod 25 p49n 47 E 0 mod 49 Ramanujan noticed the beginnings of other patterns in these first 200 values pll6 E 0 mod 121 p99 E 0 mod 125 From such scant evidence he made the following conjecture Ifd 5a7bllC and 24A El mod 6 then p6n x E 0 mod 6 When 6 125 for example we have A 99 So Ramanujan7s conjecture is that p125n 99 E 0 mod 125 We note that the general conjecture follows easily from the cases when the moduli are powers of 5 7 or 11 It is remarkable that Ramanujan was able to formulate a general conjecture based on such little evidence and therefore unsurprising that the conjecture was not quite correct in the 1930s Chowla and Gupta discovered the counterexample p243 i 0 mod 73 Much to Ramanujan7s credit however a slightly modified version of his conjecture is indeed true in particular we now know the following If6 5175110 and 24A 21 mod 6 then p5n A E 0 mod 5a7ll1116 The task of assigning credit for the proofs of these conjectures when the modulus is a power of 5 or 7 poses an interesting historical challenge Typically the proofs have been attributed to G N Watson Recently however the nature of Ramanujan7s own contributions R has been greatly clarified Indeed a complete outline of the proof modulo powers of 5 and a much rougher sketch for powers of 7 so rough that it did not yet reveal his error in the statement of the conjecture is given by Ramanujan in a long manuscript which he wrote in the three years preceding his death In typical fashion Ramanujan provides in neither case complete details for all of his assertions This manuscript was apparently in Watson7s possession from 1928 until his death in 1965 Indeed a copy of the manuscript in Watson7s handwriting the whereabouts of the original is unknown resides in the library of Oxford7s Mathematical Institute In any event it seems clear that Ramanujan deserves more credit than he has historically been granted for these cases By contrast the case of powers of II is much more dif cult the first published proof of Ramanujan7s conjectures in this case was given by AOL Atkin in 1967 6 SCOTT AHLGREN AND KEN ONO DYSON7S RANK AND CRANK The celebrated physicist Freeman Dyson when he was a college student in 1944 initiated an important subject in partition theory by discovering a delightfully simple phenomenon which appeared to explain why p5n 4 E 0 mod 5 and p7n 5 E 0 mod 7 Dyson defined the rank of a partition to be the largest summand minus the number of summands Here for example are the partitions of 4 and their ranks Partition Rank 4 4lE3mOd5 31 37221mod5 22 27220mod5 211 273E4mod5 1lll 174E2mod5 Notice that the ranks of these partitions represent each residue class modulo 5 exactly once After computing many more examples Dyson observed that without exception numbers of the form 511 4 respectively 711 5 have the property that their ranks modulo 5 respectively modulo 7 are equally distributed More precisely if 0 3 m lt M are integers and RN m M denotes the number of partitions of N with rank congruent to m mod M then Dyson conjectured that R5n4m5 p5n4 for 0377134 1 5 R7n5m7p7n5 for 0377136 The truth of these conjectures would provide a simple and elegant combinatorial expla nation for Ramanujan7s congruences Dyson7s speculation was confirmed ten years later by Atkin and H P F Swinnerton Dyer in a wonderful paper which combines classical combinatorial arguments with techniques from the theory of modular functions Unfortunately Dyson7s rank does not seem to enjoy such simple properties for primes other than 5 and 7 However he conjectured the existence of another natural statistic the crank which explains the congruence plln 6 E 0 mod 11 In the late 1980s George E Andrews and Frank Garvan found such a crank A G G Further work of Garvan Dongsu Kim and Dennis Stanton G K S has produced for the congruences with modulus 5 7 11 and 25 combinatorial interpretations which are rooted in the modular representation theory of the symmetric group ADDITION AND COUNTING 7 ATKIN7S EXAMPLES We return to Ramanujan7s intuition that there are no simple arithmetic properties for pn when the modulus involves primes greater than 11 Ramanujan seems to have been correct in this claim no new congruence as simple as the originals has ever been found although it has not been proved that none exists The 1960s however witnessed tantiliZing discoveries of further examples notably by Atkin Newman and O7Brien Atkin for example found elegant infinite families of congruences modulo 5 7 and 13 which are quite different from those previously known A simple example of these is the congruence p11313n 237 E 0 mod 13 Atkin also gave more examples though not so systematic with modulus 17 19 23 29 and 31 Atkin obtains these results via a detailed study of modular functions Since these lie at the heart of the proofs of the congruences we have seen so far we will give a brief description here Let SL2Z be the set of 2 gtlt 2 integer matrices with determinant one Then if N is an integer define the congruence subgroup P0N by P0N 2 ESL2Z ago mod N An element y 2 acts on the upper half plane H of complex numbers via the linear fractional transformation yz 12 By definition a modular function on P0N is a function f on H which satisfies f yz fz for all y E P0N and which in addition is meromorphic on H and at the cusps When N is small the field of these functions has relatively low degree over C therefore given several functions in such a field one can find non trivial relations among them If the right functions are involved then such a relation may give information about values of For Atkin7s examples when X 5 7 or 13 the relevant function fields have degree one this is responsible for the infinite families of congruences As increases however things rapidly become more complicated Atkin7s work is interesting for another reason it marks an early use of sophisticated computers in mathematics As he says it is often more dif cult to discover results in this subject than to prove them and an informed search on the machine may enable one to find out precisely what happens77 A PROBLEM OF ERDO S Even after all of the beautiful discoveries described above the general arithmetic properties of pn must seem rather mysterious Indeed we have said nothing for any prime modulus greater than 31 let alone for a general prime modulus In this context we mention a conjecture of Erdo39s from the 1980s If is a prime then there ezrz39sts on n such that pn E 0 mod K 8 SCOTT AHLGREN AND KEN ONO If we re ect on this conjecture for a moment we are struck by its weakness it asserts only that every prime divides at least one value of the partition function On the other hand until very recently the known results were even weaker the best was a theorem of Schinzel and Wirsing who proved the existence of a constant e such that for large X the number of primes i lt X for which Erdo39s7 conjecture is true is 2 clog log X RECENT DEVELOPMENTS In the past several years our understanding of the arithmetic of pn has increased dramatically All of the advances have arisen from a single source the fact that values of the partition function are intimately related to the arithmetic of modular forms Modular forms have historically played a large role in Number Theory their importance of course has been underscored by their central position in the proof of Fermat7s Last Theorem The crux of Wiles7 proof is to show that elliptic curves are modular in other words their arithmetic is dictated in part by certain modular forms to which they are related What has been learned recently is that the partition function does not escape the web of modularity its arithmetic too is intimately connected to the behavior of a certain family of modular forms This connection has allowed the application of deep methods of Deligne Serre and Shimura to the study of These theories some of the most powerful of the last half century have important ramifications for pn in particular properly applied they imply that pn satisfies linear congruences for every prime X 2 5 We shall discuss in more detail how modular forms enter the picture in the next section let us first indicate what they enable us to prove The second author inspired by some formulae of Ramanujan was the first to notice these connections as a result 0 he proved the following For any prime X 2 5 there e1ist in nitely many congruences of the form pAn B E 0 mod K We note that if the arithmetic progression An B gives rise to such a congruence then so do any of its infinitely many subprogressions we do not count these as new when we speak of infinitely many congruences Shortly thereafter the first author Ahl extended this result by showing that the prime X may in fact be replaced by an arbitrary prime power W from this it can be shown that X may in fact be replaced by any modulus M which is coprime to 6 An immediate consequence of these results is the following If 2 5 is prime then a positive proportion of natural numbers n have p01 0 mod K This provides a very convincing proof of the conjecture of Erdo39s mentioned above More recently the two authors Ahl O have shown that congruences for pn are even more widespread than these theorems indicate To explain this let us return to ADDITION AND COUNTING 9 Ramanujan7s original results p5n 4 E 0 mod 5 p7n 5 E 0 mod 7 p11n 6 E 0 mod 11 As Ramanujan7s conjectures indicate these results may be written in a uni ed way Namely let M denote the inverse of 24 modulo X in other words 24M E 1 mod Then they assume the following form If 5 7 07 11thenp n M E 0 mod K Now for any prime X 2 5 and any exponent k the results above guarantee the existence of infinitely many progressions An 1 B such that pAn B E 0 mod M An impor tant feature of the method used to prove the theorems above is that in every case the progression An 1 B which it produces is a sub progression of n M in other words X l A and B E M mod As an example one of the simplest congruences guaranteed by this theorem is p6 BnlHMUEO wdm in this case we have 111247 E 124 mod 13 What the authors have shown recently is that congruences are not confined to this single progression modulo X In fact we now know that if X 2 5 is prime and k is any exponent then infinitely many congruences pAn B E 0 mod N exist within each of K 12 progressions modulo X In other words for each prime slightly more than half of such progressions contain congruences When 11 for example the relevant progressions are HnL nnz Hnamp nna nna nnamp Of these only Ramanujan7s own 1171 6 had been distinguished by the previous theory The latest result provides a theoretical framework which explains every known partition function congruence MODULAR FORMS We will try to indicate brie y how the theory of modular forms can be applied to the study of 1901 in order to yield the results of the preceding section At the heart of the matter are the generating function 10 SCOTT AHLGREN AND KEN ONO and Dedekind7s eta function 712 124 Hl 7 at here at z 62quot 711 Combining the last two formulae gives 0 n1 ln24z 2 p 24 x x 1m23 7171 Loosely speaking a modular form of weight k on the subgroup F0N is a function f on the upper half plane H which satis es a transformation property of the form b f 02dkfz for all 3 e P0N In addition f is required to be Inerornorphic on H and at the cusps if also f is holo Inorphic on H and vanishes at the cusps then we call f a cusp form We allow k to be an integer or half an integer extra care must be taken in the latter case note that the modular functions introduced above are just modular forms of weight zero Every Inodular forrn fz has a Fourier expansion in powers of x 62quot if f is a cusp form then this expansion takes the form When the weight k of a cusp form is integral then the theory of Deligne and Serre is available for the study of the Fourier coef cients If In particular there is a natural family of operators the so called Hecke operators which act on spaces of modular forms If f is a normalized eigenforrn for this family then Serre conjectured and Deligne proved the existence of a representation pf Ga1Q a GL2ltKgt for some field K such that for all but finitely many prirnes Q we have TTacePfFfObQ afltQgt Here Fron denotes any conjugacy class of Frobenius elements at the prime Q This result is extraordinarily powerful it allows us to study the Fourier coef cients of modular forms using the structure of Galois groups If the weight k of a cusp form is half integral then we do not have the results of Deligne and Serre at our disposal There is however a correspondence due to Shimura ADDITION AND COUNTING 11 between cusp forms of half integral weight and certain forms of integral weight the Shimura correspondence is quite explicit and commutes in the best possible way with the action of the Hecke operators on the respective spaces We saw above that the expansion 1 lr24z Z pltn f1 9523 7171 contains every value of the partition function Now lr24z is a modular form on P0676 However it has two major deficiencies the weight is 712 and it has a pole at every cusp So none of the theories above seem to apply It turns out however that starting with this expansion one can construct half integral weight cusp forms which still preserve much information about the values of pn modulo powers of primes From these cusp forms the theory of Deligne and Serre filtered through Shimura7s correspondence yields the results of the last section L FUNCTIONS AND ARITHMETIC Since modular forms play such an important role in partition congruences it is natural to suspect that there may be deeper connections between partitions and modular objects As it turns out this is indeed the case To motivate the connection consider the following classical Diophantine question al ready of interest to ancient Greek and Arab scholars Which integers D are areas of right triangles with rational number sidelengths Such numbers D are known as congruent numbers Simple arguments show that a number D is congruent precisely when there are infinitely many rational points guy on the elliptic curve ED 242 3 7 D215 How does one determine whether such a curve has infinitely many points The Birch and Swinnerton Dyer Conjecture one of the main outstanding conjectures in Number Theory and a million dollar Clay Mathematics Insititute Problem provides the solution Let LEDs denote the Hasse Weil L function attached to ED this is an analytic function whose definition depends on the behavior of ED modulo primes p For the congruent number problem the conjecture implies that LED1 0 ltgt D is congruent In addition the conjecture gives a precise formula dictating the analytic behavior of LED s at s I For instance if LED I 31 0 then the conjecture asserts that LED71 QD LUED 12 SCOTT AHLGREN AND KEN ONO Here 9D is an explicit transcendental number and mltED is the Tate Shafarevich group of ED the Tate Shafarevich group is a certain Galois cohomology group which measures the extent to which the local global principle fails for ED In the early 1980s Jerrold Tunnell using the works of Shimura and Waldspurger see K for a good account constructed two modular forms of weight 32 whose coef cients interpolate the square roots of the LED 1 Together with the Birch and Swinnerton Dyer Conjecture these modular forms provide a complete solution to the congruent number problem Recently Li Guo and the second author G O have shown that if 13 S X S 31 is prime then certain half integral weight modular forms whose coef cients interpolate values of pn modulo behave in a manner somewhat similar to Tunnell7s modular forms In particular they show that there are modular motives M1371 these may be viewed as analogs of elliptic curves whose L functions LMDzs have the property that the square roots of LMD7Z K 7 32 are related in a predictable way to the coef cients of these modular forms The truth of the Bloch Kato Conjecture a vast generalization of the Birch and Swinnerton Dyer Conjecture then implies that LMD17 3V2 9Di LUMD2 Assuming the Bloch Kato Conjecture it can be shown for many 11 that p01 0 mod X gt MMD71 E 0 mod K where D depends on 11 These two conditions are probably equivalent and so it is likely that the divisibility of pn often dictates the presence of elements of order X in these Tate Shafarevich groups So perhaps surprisingly it seems that congruences like Ramanujan7s are connected to some highly abstract creations of modern Number Theory THE FUTURE The beginnings of the partition function are extraordinarily humble after all what could be simpler than addition and counting Despite its humble start the history of the partition function includes connections to many central areas of Number Theory from the work of Euler to the birth of the circle method to the modern theory of modular forms and L functions It will be quite interesting to see what further connections the future will reveal REFERENCES Ahl S Ahlgren The partition function modulo composite integers M Math Annalen 318 2000 795803 Ahl O S Ahlgren and K Ono Congruence properties for the partition function accepted for pub lication Proc Natl Acad Sci USA A G E Andrews The theory of partitions Cambridge Univ Press 1998 AG G E Andrews and F Garvan Dyson s crank of a partition Bull Amer Math Soc NS 18 1988 167171 ADDITION AND COUNTING 13 R B CI Berndt and KI Ono Ramanujan s unpublished manuscript on the partition and tau functions with commentary The Andrews Festschrift edI DI Foata and GI NI Han Springer Verlag 2001 39110 G F Garvan New combinatorial interpretations of Ramanujan s partition congruences mod 5 7 and 11 Trans Amer Math Soc 305 1988 4777 GKS FI Garvan DI Kim and DI Stanton Cranks and tcores InventI Math 101 1990 117I GO LI Guo and KI Ono The partitionfunction and the arithmetic of certain modular Lfunctions IntI MathI Res Notes 21 1999 11791197 K NI Koblitz Introduction to elliptic cur39ues and modular forms Springer Verlag 1993 O KI Ono Distribution of the partition function modulo m Annals of Math 151 2000 293 307 DEPARTMENT OF MATHEMATICS UNIVERSITY OF ILLINOIS URBANA ILLINOIS 61801 E mail address sahlgreanathuiucedu DEPARTMENT OF MATHEMATICS UNIVERSITY OF WISCONSIN MADISON WISCONSIN 53706 E mail address ononathwiscedu
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'