Transcription
An Infinitely Large Napkinhttp://web.evanchen.cc/napkin.htmlEvan ChenVersion: v1.5.20220608
When introduced to a new idea, always ask why you should care.Do not expect an answer right away, but demand one eventually.— Ravi Vakil [Va17]If you like this book and want to support me,please consider buying me a coffee!http://ko-fi.com/evanchen/For Brian and Lisa, who finally got me to write it. 2021 Evan Chen.Text licensed under CC-by-SA-4.0. Source files licensed under GNU GPL v3.This is (still!) an incomplete draft. Please send corrections, comments, pictures of kittens, etc.to evan@evanchen.cc, or pull-request at https://github.com/vEnhance/napkin.Last updated June 8, 2022.
PrefaceThe origin of the name “Napkin” comes from the following quote of mine.I’ll be eating a quick lunch with some friends of mine who are still in high school.They’ll ask me what I’ve been up to the last few weeks, and I’ll tell them that I’ve beenlearning category theory. They’ll ask me what category theory is about. I tell themit’s about abstracting things by looking at just the structure-preserving morphismsbetween them, rather than the objects themselves. I’ll try to give them the standardexample Grp, but then I’ll realize that they don’t know what a homomorphism is.So then I’ll start trying to explain what a homomorphism is, but then I’ll rememberthat they haven’t learned what a group is. So then I’ll start trying to explain what agroup is, but by the time I finish writing the group axioms on my napkin, they’vealready forgotten why I was talking about groups in the first place. And then it’s1PM, people need to go places, and I can’t help but think:“Man, if I had forty hours instead of forty minutes, I bet I could actually have explainedthis all”.This book was initially my attempt at those forty hours, but has grown considerablysince then.About this bookThe Infinitely Large Napkin is a light but mostly self-contained introduction to a largeamount of higher math.I should say at once that this book is not intended as a replacement for dedicatedbooks or courses; the amount of depth is not comparable. On the flip side, the benefit ofthis “light” approach is that it becomes accessible to a larger audience, since the goal ismerely to give the reader a feeling for any particular topic rather than to emulate a fullsemester of lectures.I initially wrote this book with talented high-school students in mind, particularlythose with math-olympiad type backgrounds. Some remnants of that cultural bias canstill be felt throughout the book, particularly in assorted challenge problems which aretaken from mathematical competitions. However, in general I think this would be agood reference for anyone with some amount of mathematical maturity and curiosity.Examples include but certainly not limited to: math undergraduate majors, physics/CSmajors, math PhD students who want to hear a little bit about fields other than their own,advanced high schoolers who like math but not math contests, and unusually intelligentkittens fluent in English.Source codeThe project is hosted on GitHub at https://github.com/vEnhance/napkin. Pullrequests are quite welcome! I am also happy to receive suggestions and corrections byemail.Philosophy behind the Napkin approachAs far as I can tell, higher math for high-school students comes in two flavors:v
viNapkin, by Evan Chen (v1.5.20220608) Someone tells you about the hairy ball theorem in the form “you can’t comb thehair on a spherical cat” then doesn’t tell you anything about why it should be true,what it means to actually “comb the hair”, or any of the underlying theory, leavingyou with just some vague notion in your head. You take a class and prove every result in full detail, and at some point you stopcaring about what the professor is saying.Presumably you already know how unsatisfying the first approach is. So the secondapproach seems to be the default, but I really think there should be some sort of middleground here.Unlike university, it is not the purpose of this book to train you to solve exercises orwrite proofs1 , or prepare you for research in the field. Instead I just want to show yousome interesting math. The things that are presented should be memorable and worthcaring about. For that reason, proofs that would be included for completeness in anyordinary textbook are often omitted here, unless there is some idea in the proof whichI think is worth seeing. In particular, I place a strong emphasis over explaining why atheorem should be true rather than writing down its proof. This is a recurrent theme ofthis book:Natural explanations supersede proofs.My hope is that after reading any particular chapter in Napkin, one might get thefollowing out of it: Knowing what the precise definitions are of the main characters, Being acquainted with the few really major examples, Knowing the precise statements of famous theorems, and having a sense of whythey should be true.Understanding “why” something is true can have many forms. This is sometimesaccomplished with a complete rigorous proof; in other cases, it is given by the idea of theproof; in still other cases, it is just a few key examples with extensive cheerleading.Obviously this is nowhere near enough if you want to e.g. do research in a field; but ifyou are just a curious outsider, I hope that it’s more satisfying than the elevator pitch orWikipedia articles. Even if you do want to learn a topic with serious depth, I hope thatit can be a good zoomed-out overview before you really dive in, because in many sensesthe choice of material is “what I wish someone had told me before I started”.More pedagogical comments and referencesThe preface would become too long if I talked about some of my pedagogical decisionschapter by chapter, so Appendix A contains those comments instead.In particular, I often name specific references, and the end of that appendix has morereferences. So this is a good place to look if you want further reading.1Which is not to say problem-solving isn’t valuable; I myself am a math olympiad coach at heart. It’sjust not the point of this book.
PrefaceviiHistorical and personal notesI began writing this book in December of 2014, after having finished my first semester ofundergraduate at Harvard. It became my main focus for about 18 months after that,as I became immersed in higher math. I essentially took only math classes, (gleefullyignoring all my other graduation requirements) and merged as much of it as I could (aswell as lots of other math I learned on my own time) into the Napkin.Towards August of 2016, though, I finally lost steam. The first public drafts wentonline then, and I decided to step back. Having burnt out slightly, I then took a breakfrom higher math, and spent the remaining two undergraduate years2 working extensivelyas a coach for the American math olympiad team, and trying to spend as much timewith my friends as I could before they graduated and went their own ways.During those two years, readers sent me many kind words of gratitude, many reportsof errors, and many suggestions for additions. So in November of 2018, some weeks intomy first semester as a math PhD student, I decided I should finish what I had started.Some months later, here is what I have.Acknowledgementsadd moreacknowledgmentsI am indebted to countless people for this work. Here is a partial (surely incomplete)list. Thanks to all my teachers and professors for teaching me much of the materialcovered in these notes, as well as the authors of all the references I have cited here.A special call-out to [Ga14], [Le14], [Sj05], [Ga03], [Ll15], [Et11], [Ko14], [Va17], [Pu02],[Go18], which were especially influential. Thanks also to dozens of friends and strangers who read through preview copiesof my draft, and pointed out errors and gave other suggestions. Special mentionto Andrej Vuković and Alexander Chua for together catching over a thousanderrors. Thanks also to Brian Gu and Tom Tseng for many corrections. (If you findmistakes or have suggestions yourself, I would love to hear them!) I’d also like to express my gratitude for many, many kind words I received duringthe development of this project. These generous comments led me to keep workingon this, and were largely responsible for my decision in November 2018 to beginupdating the Napkin again.Finally, a huge thanks to the math olympiad community, from which the Napkin(and me) has its roots. All the enthusiasm, encouragement, and thank-you notes I havereceived over the years led me to begin writing this in the first place. I otherwise wouldnever have the arrogance to dream a project like this was at all possible. And of course Iwould be nowhere near where I am today were it not for the life-changing journey I tookin chasing my dreams to the IMO. Forever TWN2!2Alternatively: “ . . . and spent the next two years forgetting everything I had painstakingly learned”.Which made me grateful for all the past notes in the Napkin!
Advice for the reader§1 PrerequisitesAs explained in the preface, the main prerequisite is some amount of mathematicalmaturity. This means I expect the reader to know how to read and write a proof, followlogical arguments, and so on.I also assume the reader is familiar with basic terminology about sets and functions(e.g. “what is a bijection?”). If not, one should consult Appendix E.§2 Deciding what to readThere is no need to read this book in linear order: it covers all sorts of areas in mathematics,and there are many paths you can take. In Chapter 0, I give a short overview for eachpart explaining what you might expect to see in that part.For now, here is a brief chart showing how the chapters depend on each other; againsee Chapter 0 for details. Dependencies are indicated by arrows; dotted lines are optionaldependencies. I suggest that you simply pick a chapter you find interesting,and then find the shortest path. With that in mind, I hope the length of the entirePDF is not intimidating.(The text in the following diagram should be clickable and links to the relevant part.)Ch 81-87Ch 1,3-5Ch 9-15,18Set TheoryAbs AlgLin AlgCh 2,6-8Ch 23-25TopologyQuantumCh 26-30Ch 16Ch 19-22Grp ActRep ThCalcCh 31-33Cmplx AnaCh 60-63Ch 42-45Cat ThDiff GeoCh 17Grp ClassifCh 34-41Measure/PrCh 70-74Ch 57-59Ch 46-51Alg Geo 1Alg Top 1Alg NT 1Ch 75-80Ch 64-69Ch 52-56Alg Geo 2-3Alg Top 2Alg NT 2ix
xNapkin, by Evan Chen (v1.5.20220608)§3 Questions, exercises, and problemsIn this book, there are three hierarchies: An inline question is intended to be offensively easy, mostly a chance to help youinternalize definitions. If you find yourself unable to answer one or two of them, itprobably means I explained it badly and you should complain to me. But if youcan’t answer many, you likely missed something important: read back. An inline exercise is more meaty than a question, but shouldn’t have any “tricky”steps. Often I leave proofs of theorems and propositions as exercises if they areinstructive and at least somewhat interesting. Each chapter features several trickier problems at the end. Some are reasonable,but others are legitimately difficult olympiad-style problems. Harder problems aremarked with up to three chili peppers ( ), like this paragraph.In addition to difficulty annotations, the problems are also marked by how importantthey are to the big picture.– Normal problems, which are hopefully fun but non-central.– Daggered problems, which are (usually interesting) results that one shouldknow, but won’t be used directly later.– Starred problems, which are results which will be used later on in the book.1Several hints and solutions can be found in Appendices B and C.Image from [Go08]1This is to avoid the classic “we are done by PSet 4, Problem 8” that happens in college sometimes, asif I remembered what that was.
Advice for the readerxi§4 PaperAt the risk of being blunt,Read this book with pencil and paper.Here’s why:Image from [Or]You are not God. You cannot keep everything in your head.2 If you’ve printed out ahard copy, then write in the margins. If you’re trying to save paper, grab a notebook orsomething along with the ride. Somehow, some way, make sure you can write. Thanks.§5 On the importance of examplesI am pathologically obsessed with examples. In this book, I place all examples in largeboxes to draw emphasis to them, which leads to some pages of the book simply consistingof sequences of boxes one after another. I hope the reader doesn’t mind.I also often highlight a “prototypical example” for some sections, and reserve the colorred for such a note. The philosophy is that any time the reader sees a definition or atheorem about such an object, they should test it against the prototypical example. Ifthe example is a good prototype, it should be immediately clear why this definition isintuitive, or why the theorem should be true, or why the theorem is interesting, et cetera.Let me tell you a secret. Whenever I wrote a definition or a theorem in this book, Iwould have to recall the exact statement from my (quite poor) memory. So instead Ioften consider the prototypical example, and then only after that do I remember whatthe definition or the theorem is. Incidentally, this is also how I learned all the definitionsin the first place. I hope you’ll find it useful as well.2See also https://usamo.wordpress.com/2015/03/14/writing/ and the source above.
xiiNapkin, by Evan Chen (v1.5.20220608)§6 Conventions and notationsThis part describes some of the less familiar notations and definitions and settles foronce and for all some annoying issues (“is zero a natural number?”). Most of these are“remarks for experts”: if something doesn’t make sense, you probably don’t have to worryabout it for now.A full glossary of notation used can be found in the appendix.§6.i Natural numbers are positiveThe set N is the set of positive integers, not including 0. In the set theory chapters, weuse ω {0, 1, . . . } instead, for consistency with the rest of the book.§6.ii Sets and equivalence relationsThis is brief, intended as a reminder for experts. Consult Appendix E for full details.An equivalence relation on a set X is a relation which is symmetric, reflexive, andtransitive. An equivalence relation partitions X into several equivalence classes. Wewill denote this by X/ . An element of such an equivalence class is a representativeof that equivalence class.I always use for an “isomorphism”-style relation (formally: a relation which is anisomorphism in a reasonable category). The only time ' is used in the Napkin is forhomotopic paths.I generally use and ( since these are non-ambiguous, unlike . I only use onrare occasions in which equality obviously does not hold yet pointing it out would bedistracting. For example, I write Q R since “Q ( R” is distracting.I prefer S \ T to S T .The power set of S (i.e., the set of subsets of S), is denoted either by 2S or P(S).§6.iii FunctionsThis is brief, intended as a reminder for experts. Consult Appendix E for full details.fLet X Y be a function: By f pre (T ) I mean the pre-imagef pre (T ) : {x X f (x) T } .This is in contrast to the f 1 (T ) used in the rest of the world; I only use f 1 foran inverse function.By abuse of notation, we may abbreviate f pre ({y}) to f pre (y). We call f pre (y) afiber. By f img (S) I mean the imagef img (S) : {f (x) x S} .Almost everyone else in the world uses f (S) (though f [S] sees some use, and f “(S)is often used in logic) but this is abuse of notation, and I prefer f img (S) for emphasis.This image notation is not standard. If S X, then the restriction of f to S is denoted f S , i.e. it is the functionf S : S Y . Sometimes functions f : X Y are injective or surjective; I may emphasize thissometimes by writing f : X , Y or f : X Y , respectively.
Advice for the readerxiii§6.iv Cycle notation for permutationsAdditionally, a permutation on a finite set may be denoted in cycle notation, as describedin say https://en.wikipedia.org/wiki/Permutation#Cycle notation. For examplethe notation (1 2 3 4)(5 6 7) refers to the permutation with 1 7 2, 2 7 3, 3 7 4, 4 7 1,5 7 6, 6 7 7, 7 7 5. Usage of this notation will usually be obvious from context.§6.v RingsAll rings have a multiplicative identity 1 unless otherwise specified. We allow 0 1 ingeneral rings but not in integral domains.All rings are commutative unless otherwise specified. There is an elaboratescheme for naming rings which are not commutative, used only in the chapter oncohomology rings:1 not requiredAnticommutative, 1 not requiredHas 1Anticommutative with 1Commutative with 1Gradedgraded pseudo-ringanticommutative pseudo-ringgraded ringanticommutative ringcommutative graded ringNot Gradedpseudo-ringN/AN/AN/AringOn the other hand, an algebra always has 1, but it need not be commutative.§6.vi ChoiceWe accept the Axiom of Choice, and use it freely.§7 Further readingThe appendix Appendix A contains a list of resources I like, and explanations of pedagogical choices that I made for each chapter. I encourage you to check it out.In particular, this is where you should go for further reading! There are some topicsthat should be covered in the Napkin, but are not, due to my own ignorance or laziness.The references provided in this appendix should hopefully help partially atone for myomissions.
ContentsPrefacevAdvice for the reader1Prerequisites . . . . . . . . . . . . .2Deciding what to read . . . . . . .3Questions, exercises, and problems4Paper . . . . . . . . . . . . . . . . .5On the importance of examples . .6Conventions and notations . . . . .7Further reading . . . . . . . . . . .ix. ix. ix. x. xi. xi. xii. xiiiIStarting Out3300.10.20.30.40.50.60.7Sales pitchesThe basics . . . . . . . . .Abstract algebra . . . . . .Real and complex analysisAlgebraic number theory .Algebraic topology . . . .Algebraic geometry . . . .Set theory . . . . . . . . inition and examples of groups . . . . .Properties of groups . . . . . . . . . . . . .Isomorphisms . . . . . . . . . . . . . . . .Orders of groups, and Lagrange’s theoremSubgroups . . . . . . . . . . . . . . . . . .Groups of small orders . . . . . . . . . . .Unimportant long digression . . . . . . . .A few harder problems to think about . .4141444648495051512.12.22.32.42.52.62.72.8Metric spacesDefinition and examples of metric spaces . . .Convergence in metric spaces . . . . . . . . .Continuous maps . . . . . . . . . . . . . . . .Homeomorphisms . . . . . . . . . . . . . . . .Extended example/definition: product metricOpen sets . . . . . . . . . . . . . . . . . . . .Closed sets . . . . . . . . . . . . . . . . . . . .A few harder problems to think about . . . .53535556575859616312.IIBasic Abstract Algebra3Homomorphisms and quotient groups67Generators and group presentations . . . . . . . . . . . . . . . . . . . . . 673.16515
16Napkin, by Evan Chen (v1.5.20220608)3.23.33.43.53.63.74Homomorphisms . . . . . . . . . . . . . . . .Cosets and modding out . . . . . . . . . . .(Optional) Proof of Lagrange’s theorem . . .Eliminating the homomorphism . . . . . . .(Digression) The first isomorphism theoremA few harder problems to think about . . .Rings and ideals4.1Some motivational metaphors about rings vs4.2(Optional) Pedagogical notes on motivation4.3Definition and examples of rings . . . . . . .4.4Fields . . . . . . . . . . . . . . . . . . . . . .4.5Homomorphisms . . . . . . . . . . . . . . . .4.6Ideals . . . . . . . . . . . . . . . . . . . . . .4.7Generating ideals . . . . . . . . . . . . . . .4.8Principal ideal domains . . . . . . . . . . . .4.9Noetherian rings . . . . . . . . . . . . . . . .4.10 A few harder problems to think about . . .55.15.25.35.45.55.65.7IIIFlavors of ringsFields . . . . . . . . . . . . . . . . . . .Integral domains . . . . . . . . . . . . .Prime ideals . . . . . . . . . . . . . . .Maximal ideals . . . . . . . . . . . . .Field of fractions . . . . . . . . . . . .Unique factorization domains (UFD’s)A few harder problems to think about.687073737676groups. . . . . . . . . . . . . . . . . . . . . . . . . . . .7979797982828385878889.9191919293949596.Basic Topology6996.16.26.36.46.5Properties of metric spacesBoundedness . . . . . . . . . . . . . . . . . . . . .Completeness . . . . . . . . . . . . . . . . . . . .Let the buyer beware . . . . . . . . . . . . . . . .Subspaces, and (inb4) a confusing linguistic pointA few harder problems to think about . . . . . .7.17.27.37.47.57.67.77.87.9Topological spacesForgetting the metric . . . . . . . . . .Re-definitions . . . . . . . . . . . . . .Hausdorff spaces . . . . . . . . . . . . .Subspaces . . . . . . . . . . . . . . . .Connected spaces . . . . . . . . . . . .Path-connected spaces . . . . . . . . .Homotopy and simply connected spacesBases of spaces . . . . . . . . . . . . .A few harder problems to think about8.1Compactness117Definition of sequential compactness . . . . . . . . . . . . . . . . . . . . . 14115
Contents8.28.38.48.58.6IV917Criteria for compactness . . . . . . . . .Compactness using open covers . . . . .Applications of compactness . . . . . . .(Optional) Equivalence of formulations ofA few harder problems to think about . . . . . . . . . . . . . . . . . . . . . .compactness. . . . . . . .Linear Algebra127Vector spaces9.1The definitions of a ring and field . . . . .9.2Modules and vector spaces . . . . . . . . .9.3Direct sums . . . . . . . . . . . . . . . . .9.4Linear independence, spans, and basis . . .9.5Linear maps . . . . . . . . . . . . . . . . .9.6What is a matrix? . . . . . . . . . . . . . .9.7Subspaces and picking convenient bases . .9.8A cute application: Lagrange interpolation9.9(Digression) Arrays of numbers are evil . .9.10 A word on general modules . . . . . . . . .9.11 A few harder problems to think about . ngsWhy you should care . . . . . . . . . .Warning on assumptions . . . . . . . .Eigenvectors and eigenvalues . . . . . .The Jordan form . . . . . . . . . . . .Nilpotent maps . . . . . . . . . . . . .Reducing to the nilpotent case . . . . .(Optional) Proof of nilpotent Jordan .Algebraic and geometric multiplicity .A few harder problems to think .411.5Dual space and traceTensor product . . . . . . . . . . . . .Dual space . . . . . . . . . . . . . . . .V W gives matrices from V to W .The trace . . . . . . . . . . . . . . . . .A few harder problems to think tWedge product . . . . . . . . . . . . . . . . . . .The determinant . . . . . . . . . . . . . . . . . . .Characteristic polynomials, and Cayley-HamiltonA few harder problems to think about . . . . . .16516516716917113.113.213.313.4Inner product spacesThe inner product . .Norms . . . . . . . .Orthogonality . . . .Hilbert spaces . . . .173173176177178111213.
18Napkin, by Evan Chen (v1.5.20220608)13.5A few harder problems to think about . . . . . . . . . . . . . . . . . . . 18014.114.214.314.414.514.614.714.8Bonus: Fourier analysisSynopsis . . . . . . . . . . . . . . . . . . . .A reminder on Hilbert spaces . . . . . . . .Common examples . . . . . . . . . . . . . .Summary, and another teaser . . . . . . . .Parseval and friends . . . . . . . . . . . . . .Application: Basel problem . . . . . . . . . .Application: Arrow’s Impossibility TheoremA few harder problems to think about . . als, adjoint, and transposesDual of a map . . . . . . . . . . . . . .Identifying with the dual space . . . .The adjoint (conjugate transpose) . . .Eigenvalues of normal maps . . . . . .A few harder problems to think about.1911911921931951961415V.More on Groups1619916.116.216.316.416.5Group actions overkill AIME problemsDefinition of a group action . . . . . .Stabilizers and orbits . . . . . . . . . .Burnside’s lemma . . . . . . . . . . . .Conjugation of elements . . . . . . . .A few harder problems to think about.20120120120320420517.117.217.317.4Find all groupsSylow theorems . . . . . . . . . . . . . . . .(Optional) Proving Sylow’s theorem . . . . .(Optional) Simple groups and Jordan-HölderA few harder problems to think about . . .20720720821021118.118.218.318.418.518.6The PID structure theoremFinitely generated abelian groups . . .Some ring theory prerequisites . . . . .The structure theorem . . . . . . . . .Reduction to maps of free R-modules .Smith normal form . . . . . . . . . . .A few harder problems to think about.2132132142152162172191718VI.Representation Theory1919.119.219.319.419.5Representations of algebrasAlgebras . . . . . . . . . . . . . . . . . . . . . .Representations . . . . . . . . . . . . . . . . . .Direct sums . . . . . . . . . . . . . . . . . . . .Irreducible and indecomposable representationsMorphisms of representations . . . . . . . . . .221.223223224226227229
Contents1919.619.7The representations of Matd (k) . . . . . . . . . . . . . . . . . . . . . . . 230A few harder problems to think about . . . . . . . . . . . . . . . . . . . 23120.120.220.320.420.520.6Semisimple algebrasSchur’s lemma continued . . . . . . . .Density theorem . . . . . . . . . . . . .Semisimple algebras . . . . . . . . . . .Maschke’s theorem . . . . . . . . . . .Example: the representations of C[S3 ] .A few harder problems to think ractersDefinitions . . . . . . . . . . . . . . . . .The dual space modulo the commutatorOrthogonality of characters . . . . . . . .Examples of character tables . . . . . . .A few harder problems to think about .24124124224324524622.122.222.3Some applications249Frobenius divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249Burnside’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250Frobenius determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251202122VIIQuantum Algorithms2323.123.223.323.423.5Quantum states and measurementsBra-ket notation . . . . . . . . . . . . .The state space . . . . . . . . . . . . .Observations . . . . . . . . . . . . . . .Entanglement . . . . . . . . . . . . . .A few harder problems to think about24.124.224.324.424.5Quantum circuitsClassical logic gates . . . . . . . . . . .Reversible classical logic . . . . . . . .Quantum logic gates . . . . . . . . . .Deutsch-Jozsa algorithm . . . . . . . .A few harder problems to think s algorithm25.1 The classical (inverse) Fourier transform . . . . . . . . . . . . . . . . . .25.2 The quantum Fourier transform . . . . . . . . . . . . . . . . . . . . . . .25.3 Shor’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2712712722742425VIII26253.Calculus 101Limits and series26.1 Completeness and inf/sup . . . . . . . . . . . . . . . . . . . . . . . . . .26.2 Proofs of the two key completeness properties of R . . . . . . . . . . . .26.3 Monotonic sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . .277279279280282
20Nap
I initially wrote this book with talented high-school students in mind, particularly those with math-olympiad type backgrounds. Some remnants of that cultural bias can . PDF is not intimidating. (The text in the following diagram should be clickable and links to the relevant part.) Ch 1,3-5 Abs Alg Ch 2,6-8 Topology Ch 9-15,18 Lin Alg Ch 16
