An ON-RAMP to Proof: An Exploration of Interesting Proofs and the Authors Who Shared Them

DRAFT An ON-RAMP to Proof An Exploration of Interesting Proofs and the Authors Who Shared Them Edited by: Paul Christian Dawkins, Kristen Lew, Kathleen Melhuish, Kyeong Hah Roh, Norman Contreras, and Lino Guajardo DRAFT GENERATING A RESEARCH-INFORMED TRANSITION TO A MATHEMATICAL PROOF CURRICULUM Principle Investigators: Paul Christian Dawkins, Kristen Lew, Kathleen Melhuish, Kyeong Hah Roh This material is based upon work supported by the National Science Foundation under Grant No. DUE-2141925. HTTPS://RUME.TXST.EDU Draft 1, September 2023 DRAFT Contents Preface ....................................................... 11 Part I Proofs with Discrete Mathematics and Number Theoretic Topics ............................................................. 13 1Kostant’s Partition Funtion ...................................... 15 Author Story: Pamela E. Harris 15 1.1 Reading Prompts 18 1.1.1 PriortoProof .................................................... 18 1.1.2 TheTheorem .................................................... 18 1.1.3 TheProof ....................................................... 18 1.2 Kostant’s Partition Function 19 1.2.1 Acknowledgements .............................................. 19 1.2.2 Introduction ..................................................... 19 1.2.3 GoingtoMars ................................................... 19 2Permutations with No Peaks .................................... 21 2.1 Reading Prompts 21 2.1.1 PriortoProof .................................................... 21 2.1.2 TheTheorem .................................................... 22 2.1.3 TheProof ....................................................... 22 2.1.4 Aftertheproof ................................................... 22 DRAFT 2.2 Permutations with No Peaks 23 2.2.1 Introduction ..................................................... 23 2.2.2 Proposition ...................................................... 24 2.2.3 Acknowledgements .............................................. 24 3Infinitude of Primes ............................................ 27 Author Story: Dwight Anderson Williams II 27 3.1 Reading Prompts 30 3.1.1 PriortoProof .................................................... 30 3.1.2 TheTheorem .................................................... 30 3.1.3 TheProof ....................................................... 30 3.1.4 TheProofoftheClaim ............................................. 30 3.2 Infinitude of Primes 31 3.2.1 IntroductiontoPrimes ............................................. 31 3.2.2 Theorem........................................................ 32 4Gaps in Knowledge ............................................ 35 4.1 Reading Prompts 35 4.1.1 TheTheorem .................................................... 35 4.1.2 TheProof ....................................................... 35 4.2 Gaps in Knowledge 37 4.2.1 Introduction ..................................................... 37 4.2.2 Theorem........................................................ 37 5Tic Tac Toe Games ............................................. 39 Author Story: Alexander Diaz-Lopez 39 5.1 Reading Prompts 41 5.1.1 PriortoProof .................................................... 41 5.1.2 The Proof for Tic-Tac-Toe with 5 Marks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.1.3 The Proofs for Tic-Tac-Toe with 6, 7, 8, or 9 Marks . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.1.4 AftertheProofs .................................................. 41 5.2 Tic-Tac-Toe 42 5.2.1 Introduction ..................................................... 42 5.2.2 Counting the Tic-Tac-Toe games with 5 marks . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.2.3 Counting the Tic-Tac-Toe games with 6 marks . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2.4 Tic-Tac-Toe games with 7, 8, or 9 marks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 6Tower of Hanoi ................................................ 45 6.1 Instructor Notes 45 6.2 Reading Prompts 45 6.2.1 PriortoProof .................................................... 45 DRAFT 6.2.2 TheProof ....................................................... 45 6.2.3 AftertheProofs .................................................. 46 6.3 Tower of Hanoi 47 6.3.1 Introduction ..................................................... 47 6.3.2 Recursiveformula ................................................ 47 6.3.3 Closed formula for Tn.............................................. 48 7Infinitely Many Primitive Pythagorean Triples .................... 49 Author Story: Edna Jones 49 7.1 Reading Prompts 52 7.1.1 PriortoProof .................................................... 52 7.1.2 TheTheorem .................................................... 52 7.1.3 TheProof ....................................................... 52 7.1.4 AftertheProof ................................................... 52 7.2 Infinitely Many Primitive Pythagorean Triples 53 7.2.1 Introduction ..................................................... 53 7.2.2 TheoremandProof ............................................... 53 8Qis Countable ................................................ 55 Author Story: Priyam Patel 55 8.1 Reading Prompts 58 8.1.1 PriortoProof .................................................... 58 8.1.2 TheTheorem .................................................... 58 8.1.3 TheProofs....................................................... 58 8.2 Qis Countable 60 9When an Operation Commutes, must it be Associative? ......... 63 Author: Kate Melhuish 63 9.1 Reading Prompts 65 9.1.1 PriortoProof .................................................... 65 9.1.2 TheTheorem .................................................... 65 9.1.3 TheProof ....................................................... 65 9.2 Commutative implies Associative? 66 9.2.1 BacktotheDrawingBoard ......................................... 66 10 Closed Formula for the Fibonacci Sequence (by Induction) ...... 69 Author Story: Rebecca Garcia 69 10.1 Reading Prompts 72 10.1.1 PriortoProof .................................................... 72 10.1.2 TheTheorem .................................................... 72 DRAFT 10.1.3 TheProof ....................................................... 72 10.1.4 AftertheProof ................................................... 72 10.2 Closed Formula for the Fibonacci Sequence (by Induction) 73 10.2.1 Introduction ..................................................... 73 10.2.2 Proof that the Closed Formula Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 11 Closed Formula for the Fibonacci Sequence (Using Series) ....... 75 11.1 Reading Prompts 75 11.1.1 PriortoProof .................................................... 75 11.1.2 TheGrandFinale ................................................. 76 11.2 Closed Formula for the Fibonacci Sequence (Using Series) 77 11.2.1 A Refresher on Partial Fraction Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . 79 11.2.2 A Refresher on the Power of Geometric Series . . . . . . . . . . . . . . . . . . . . . . . . . . 79 11.2.3 TheGrandFinale ................................................. 80 12 The Golden Ratio .............................................. 83 12.1 Reading Prompts 83 12.1.1 TheTheorem .................................................... 83 12.1.2 TheProof ....................................................... 83 12.2 The Golden Ratio 84 Part II Proofs with Topology, Real Analysis, and Some More Advanced Discrete Topics ...................................... 85 13 The Cofinite Topology .......................................... 87 13.1 Reading Prompts 87 13.1.1 PriortoProof .................................................... 87 13.1.2 TheTheorem .................................................... 87 13.1.3 TheProof ....................................................... 87 13.1.4 AftertheProof ................................................... 88 13.2 The Cofinite Topology 89 14 Infinite Increasing Sequence of Numbers ....................... 91 Author Story: Aris Winger 91 14.1 Instructor Notes 94 14.2 Reading Prompts 94 14.2.1 PriortoProof .................................................... 94 14.2.2 TheTheorem .................................................... 94 14.2.3 TheProof ....................................................... 94 DRAFT 14.3 Infinite Increasing Sequence of Numbers 96 14.3.1 Introduction: Three Real Analysis Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 14.3.2 The First Real Analysis Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 15 Infinite Collapsing Sequence of Closed Intervals ............... 101 15.1 Reading Prompts 101 15.1.1 PriortoProof ................................................... 101 15.1.2 TheTheorem ................................................... 101 15.1.3 TheProof ...................................................... 101 15.2 Infinite Collapsing Sequence of Closed Intervals 103 15.2.1 Introduction .................................................... 103 15.2.2 The Second Real Analysis Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 16 Infinite Sequence of Numbers Crowding Around A Number . . . . . 105 16.1 Reading Prompts 105 16.1.1 PriortoProof ................................................... 105 16.1.2 TheTheorem ................................................... 105 16.1.3 TheProof ...................................................... 105 16.2 Infinite Sequence of Numbers Crowding Around A Number 107 16.2.1 Introduction .................................................... 107 16.2.2 The Third Real Analysis Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 17 Degrees of Connected Graphs ................................ 109 Author Story: Shanise Walker 109 17.1 Reading Prompts 112 17.1.1 PriortoProof ................................................... 112 17.1.2 TheTheorem ................................................... 112 17.1.3 TheProof ...................................................... 112 17.2 Degrees of Connected Graphs 113 17.2.1 IntroductiontoGraphTheory ...................................... 113 17.2.2 DegreesofConnectedGraphs..................................... 114 18 The Order of a Graph ......................................... 115 18.1 Reading Prompts 115 18.1.1 PriortoProof ................................................... 115 18.1.2 TheTheorem ................................................... 115 18.1.3 TheProof ...................................................... 115 18.2 The Order of a Graph 117 DRAFT 19 Prime-itive Search: Sieve of Sundaram ......................... 119 19.1 Reading Prompts 119 19.1.1 TheTheorem ................................................... 119 19.1.2 TheProof ...................................................... 119 19.2 Prime-itive Search 121 19.2.1 Introduction .................................................... 121 19.2.2 SieveofSundaram............................................... 121 19.3 Final First building blocks 123 20 Shidoku Boards ............................................... 125 20.1 Reading Prompts 125 20.1.1 PriortoProof ................................................... 125 20.1.2 TheProofs...................................................... 125 20.1.3 Aftertheproofs ................................................. 126 20.2 Shidoku Boards 127 20.2.1 FunctionsandBijections .......................................... 127 20.2.2 IntroducingShidoku.............................................. 128 20.2.3 CountingShidokuBoards ......................................... 128 21 Dirichlet’s Approximation Theorem ............................ 131 21.1 Reading Prompts 131 21.1.1 PriortoProof ................................................... 131 21.1.2 TheTheorem ................................................... 131 21.1.3 TheProof ...................................................... 132 21.2 Dirichlet’s Approximation Theorem 133 22 Fields and Cryptography ...................................... 137 22.1 Reading Prompts 137 22.1.1 PriortoProof ................................................... 137 22.1.2 TheTheorem ................................................... 137 22.1.3 TheProof ...................................................... 138 22.1.4 Followupandexample........................................... 138 22.2 Fields and Cryptography 139 23 That Futurama Theorem ....................................... 143 23.1 Instructor Notes 143 23.2 Reading Prompts 143 23.2.1 PriortoProof ................................................... 143 23.2.2 TheTheorem ................................................... 144 23.2.3 TheProof ...................................................... 144 DRAFT 23.3 That Futurama Theorem 145 Part III Proofs with More Challenging, yet Accessible Topics 149 24 Recursive Formula for Counting Parking Functions .............. 151 24.1 Reading Prompts 151 24.1.1 PriortoProof ................................................... 151 24.1.2 TheTheorem ................................................... 151 24.1.3 TheProof ...................................................... 151 24.1.4 AfterReadingtheProof........................................... 152 24.2 Recursive Formula for Counting Parking Functions 153 24.2.1 Introduction to parking functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 24.2.2 Counting parking functions recursively . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 25 Coloring Graphs .............................................. 157 25.1 Reading Prompts 157 25.1.1 PriortoProof ................................................... 157 25.1.2 TheTheorem ................................................... 157 25.1.3 TheProof ...................................................... 157 25.2 Coloring Graphs 159 26 Integral Apollonian Circle Packings ............................ 161 26.1 Suggested Homework Activities 161 26.2 Reading Prompts 161 26.2.1 PriortoProof ................................................... 161 26.2.2 TheTheorem ................................................... 162 26.2.3 TheProof ...................................................... 162 26.3 Integral Apollonian Circle Packing 163 27 Brouwer’s Fixed Point Theorem ................................. 169 27.1 Suggested Homework Activities 169 27.2 Reading Prompts 170 27.2.1 PriortoProof ................................................... 170 27.2.2 The Theorem Statement and an Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 27.2.3 TheProof ...................................................... 171 27.3 The Brouwer Fixed Point Theorem in 2-D using Algebraic Topology 172 27.3.1 TheSpaces .................................................... 172 27.3.2 PathsandLoops ................................................ 172 27.3.3 Brouwer’s Fixed Point Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 DRAFT 16 Chapter 1. Kostant’s Partition Funtion possible for me to continue to raise my daughter, while my husband lived away as a Marine, and work to complete my PhD. Once I finished my PhD I knew that I wanted a teaching career and I applied mostly to teaching institutions. I was very excited to end up getting a job offer to work at the United States Military Academy. I felt like I would be able to give back to my adoptive country (I am an immigrant and previously undocumented student). It was such an honor to be able to walk the halls of West Point and be part of the education mission to train leaders of character for the US Army. This job made me a better teacher, researcher, and human. Unfortunately, it was a temporary position and I had to look for other jobs, eventually landing a tenure-track job at Williams College in Massachusetts. Williams was rather isolated, and I struggled a lot with ever feeling like I belonged. I was really fortunate to be able to build very strong relationships with many students who felt the same way as I did being so far from home and being underrepresented in the STEM fields. We bonded and became a math family. We would spend time working on math and traveling to conferences, and would even cook pozole and make tacos. They made those years ones to remember! Now I have returned home, and I work at the university where I completed both my Masters and PhD; the University of Wisconsin - Milwaukee. A full circle moment I never envisioned. It is so great to be back and to see myself reflected back at me as I teach my courses! It is refreshing to be at an institution whose mission aligns well with my own value of making mathematics accessible to everyone. I am sure that there is some honeymoon period I am experiencing (as I write this I am in this new position only 8 months) yet I see how much I can help here. How the skills I built over the ten years since I completed my PhD can help serve a new community of students who deserve the opportunity to pursue higher education. I feel so humbled to be able to work with students who are from Milwaukee (the city I call home!), and to help them reach their career goals. As I mentioned, I really like working on math with students and one amazing benefit of being back at UW Milwaukee is that there is a graduate program. Now I am surrounded by not only undergraduates, but also graduate students. We have begun a research seminar where we collaborate on mathematics problems, and we have started traveling to conferences to present our results and findings. This feels like I am back in school myself, constantly thinking about new problems, constantly learning, and always laughing along the way. I feel so much joy in doing mathematics, maybe more now than ever before. In part this is because of the culture and climate of the department. Having a really collaborative department means we talk a lot about math, we are not scared to try new things, we all feel responsible for learning and helping each other learn and grow. Even when we are stuck on a problem, we can push each other to not give up, to try new ideas, and to keep persisting even if sometimes our results seem elusive. Because of this we have been able to have many mathematical breakthroughs and we have celebrated every result! I do not know what the future holds for me, but I know that research mathematics is my way to connect with people. It is my way to feel like I belong in math. The community we cultivate shapes my experience with mathematics and helps me see myself as a mathematician. In fact, the reason I picked the proofs I included was because of the memories I had working with my collaborators on those proofs. To me it was less about the math and more about how I felt doing the math. The proofs I shared hold special meaning in my own academic journey and I included some narrative about how those results and collaborations came to be. The proofs are just evidence of my friendships; they are the cherry on top of a beautiful cake. I hope you enjoy them as much DRAFT 17 as my friends and I did when we worked on those results. I end with one piece of unsolicited advice and a quote from Dr. Ana Marie Cauce, which I really try to internalize. I asked her if the impostor syndrome ever stopped and she replied: “The impostor syndrome has never stopped. . . but it also has never stopped me.” If you ever feel that impostor syndrome kicking in, just remember those words along with those of Cristina Saralegui “"Pa’lante, pa’lante, pa’trás ni pa’ coger impulso” translating to “Forward, forward, never backwards not even to gain momentum.” DRAFT 18 Chapter 1. Kostant’s Partition Funtion 1.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 1.1.1 Prior to Proof Start by reading the first page and the first paragraph on the second page. 1. Based on the vector definition, why can you not exchange α1and α2currencies? Note: All the tickets must be used. Now read the rest of this section stopping just before the statement of Lemma 1. 2. Do you have any questions about what you read before we read the statement to be proven? 3. What would be ℘(2α1+4α2)? What does it mean and what do you think is its value? 1.1.2 The Theorem Now read the statement of Lemma 1. 4. What does ℘(7α1+5α2) mean? According to the theorem, what is the value of ℘(7α1+5α2) ? 1.1.3 The Proof Read the proof. 5. Explain the meaning of the expression (m−ℓ)α1+ (n−ℓ)α2 in the proof. Why can this amount of currency be exchanged in only one way? 6. Why does the minimum term appear in the formula for ℘(mα1+nα2)? 7. Why is the count 1 larger than this minimum? 8. Can you summarize this proof’s argument in a couple of sentences? Feel free to take a minute to review the proof. 9. Why does the proof first focus on l , the number of solar system marble sets, rather than eclipse sunglasses or moon rocks? 10. Would the proof also work if we first focused on the number of moon rocks instead of the number of solar system marble sets? 11. How could you change the set-up of the problem (currencies, prizes) to create a new counting problem? Can you anticipate how that would change the formula or the proof? DRAFT 1.2 Kostant’s Partition Function 19 1.2 Kostant’s Partition Function 1.2.1 Acknowledgements This one is close to my heart. I first learned of Kostant’s partition function from my PhD adviser and I really liked learning about it. So much so that since about 2010 I have continued to work on problems related to this vector partition function! To best explain it I will follow the work I published with my students Alexander Pankhurst, Cielo Perez, and Aesha Siddiqui. 1 1.2.2 Introduction If you have gone to an arcade and exchanged tickets for prizes, you have encountered an integer partition function problem. For example, if you won 17 tickets and a piece of gum is 1 ticket, an eraser is 5 tickets, and a pencil is 10 tickets, then you could exchange all 17 of your tickets in the 6 ways depicted in Table 1.1. Pencils Erasers Gum 0 0 17 0 1 12 0 2 7 0 3 2 1 0 7 1 1 2 Table 1.1: Ticket exchanges. 1.2.3 Going to Mars The problem we consider here is a similar one, except we are at an arcade on Mars where the currency can be modeled by vectors, which are mathematical quantities with more than one piece of information. In particular, our initial Martian currency is modeled by the vectors α1=    1 −1 0 0     and α2=    0 1 −1 0     . These vectors can be added/subtracted together by adding/subtracting the entries in the same positions. We can also multiply the vectors by a number by multiplying each entry in the vector by that number. We say two vectors are equal only when all of their entries are equal. Lets illustrate these operations with an example 3α1+6α2=3    1 −1 0 0     +6    0 1 −1 0     =    3 −3 0 0     +    0 6 −6 0     =    3+0 −3+6 0−6 0     =    3 3 −6 0     . One very important thing to notice is that Martian currency is rather strange, as there is no number of α1 ’s that we can exchange for α2 . This is because no matter what number we multiply the vector α1 by, we will never be able to get the third entry (from top to bottom) to equal −1 , which is the bottom DRAFT 20 NOTES entry of the vector α2 . By considering the top entries of the vectors α1 and α2 , we can also deduce that there is no number of α2 ’s that we can exchange for α1 . This means that α1 and α2 cannot be exchanged for one another. But alas, that is how currency works on Mars! Now lets suppose that at the Martian arcade we won 3α1 and 6α2 worth of Martian currency, which we express as 3α1+6α2 . The arcade items that we can exchange our Martian currency for are as follows: • eclipse sunglasses at α1each, • moon rocks at α2each, and • solar system marble set at α1+α2each. Notice that when we write α1+α2 it means we must use one of each α1 and α2 in order to purchase a solar system marble set. Now that we understand Martian currency the question we want to answer is: In how many ways could we exchange 3α1+6α2 in Martian currency for the above arcade items? To do a correct count lets figure out how many solar system marble sets we could purchase. If we don’t buy any solar system marble set, then we can get 3 eclipse sunglasses and 6 moon rocks. If instead we purchase one solar system marble set, then with the remaining Martian currency (2α1+5α2) we can purchase 2 eclipse sunglasses and 5 moon rocks. We also could purchase two solar system marble sets and with the remaining Martian currency (α1+4α2) we could get a pair of eclipse sunglasses and 4 moon rocks. Lastly, we could purchase 3 solar system marble sets and with the remaining Martian currency (3α2) we could purchase 3 moon rocks. This gives a total of 4 different ways we could exchange 3α1+6α2for the arcade items. When dealing with these counting problems, we let ℘(mα1+nα2) indicate the number of ways we can exchange mα1+nα2 in Martian currency for eclipse sunglasses, moon rocks, and solar system marble sets (at the costs given above), and each way to do so is called a vector partition. In our example above, we have determined that ℘(3α1+6α2) = 4 . We now want to determine the total number of ways to exchange mα1+nα2 in Martian currency for the arcade prizes when m,n are nonnegative integers. This is then our main result. Lemma 1.2.1 If m,n∈N:={0,1,2,3,...}, then ℘(mα1+nα2) = min(m,n)+ 1. Proof. As we saw in the example, the answer to the problem depends only on counting the number of solar system marble sets we purchase. Suppose that we buy ℓ solar system marble sets. Then the remainder of the Martian currency is (m−ℓ)α1+(n−ℓ)α2 and can be exchanged in exactly one way: m−ℓ pairs of eclipse sunglasses and n−ℓ moon rocks. Notice that the smallest number of solar system marble sets we can purchase is zero, while the largest number of solar system marble sets we can purchase depends completely on which is smaller: m or n . So we have determined that 0≤ℓ≤min(m,n) . This then tells us that there are min(m,n)+1 many ways to exchange our Martian money for the arcade items. ■ Notes 1 Harris, P.E., Pankhurst, A., Perez, C., & Siddiqui, A. (2018). Partitions from mars, part 1 [http://www.girlsangle. org/page/bulletin-archive/GABv14n02E.pdf#page=15]. Girls’ Angle Bulletin, December 2017/January 2018 Volume 11 Number 2, p. 7-11. DRAFT 2. Permutations with No Peaks Author: Pamela Harris Click here for Dr. Pamela Harris’s story. 2.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 2.1.1 Prior to Proof Begin by reading the first page and the beginning of the second stopping after the definition of P(π) . Definition 2.1.1 — Bijection. A function is called a bijection if it is both one-to-one and onto. In the context of this proof, where the inputs and outputs are in the set [n] = {1,2,3...n} , this means that every element of the set must be the output for exactly one of the inputs. 1. Consider the function σ:[4]→[4] such that σ(1) = 2 , σ(2) = 4 , σ(3) = 3 , and σ(4) = 1 . Would σbe a permutation contained in S4? 2. Using the explanation of bijection above, create an example of a function from [3]→[3] that is not a bijection. 3. When the text says a permutation has a "peak at 2", is that referring to the location or the number in that location? 4. Can a permutation have a peak at 1? 5. Can a permutation have two consecutive peaks? 6. Create an example of a permutation in S5 that has one peak and a permutation in S5 that has no peaks. Now read the rest of the background information. 6. What questions do you have about what you read before we read the statement to be proven? DRAFT 22 Chapter 2. Permutations with No Peaks 2.1.2 The Theorem Now read the statement of Proposition 1. 7. Give an example of a set Swhen n=5. What does P(S;n)represent for the Syou chose? 8. What does P(/0;n)represent? What does |P(/0;n)|represent? 9. What does the proof need to accomplish to prove Proposition 1? 2.1.3 The Proof Start by reading the proof stopping after the seventh line on the second page (the sentence ending with the word “increasing”). 10. How is the first sentence of the proof using the definition of peak? 11. Explain what πLmeans in the equation π=πL1πR. 12. What does the proof claim about πLand πR? 13. Why does the proof divide the permutation around the output 1 and not some other number? 14. What does πlook like if πLis empty? 15. Summarize what the proof has said so far. Keep reading the proof down through the end, which is marked by the little box on the right. 16. If we define πL, why does the proof claim "we know exactly the numbers that make up πR?" 17. What does n−1 irepresent (using the definition of the notation on the side sheet)? Why does it count the number of πL’s we can construct? 18. Summarize this section of the proof in your own words. 2.1.4 After the proof 19. Now that we have read through the whole proof, can you summarize this proof’s argument in a couple of sentences? 20. How would you organize the proof into sections? What goal does each section accomplish in proving the theorem? DRAFT 2.2 Permutations with No Peaks 23 2.2 Permutations with No Peaks 2.2.1 Introduction Definition 2.2.1 — Symmetric group. Asymmetric group of degree n , denoted by Sn , is the set of all bijective mappings from the set [n]:={1,2,...,n} to itself. These mappings are also called permutations. In this note we represent the elements of Snin two ways: • one-line notation: S3={123,132,213,231,312,321} • or by plotting (and connecting the dots): Since π∈Sn is a bijective map π:[n]→[n] we can represent πby plotting the points (i,π(i)). Below we plot all of the permutations in S3: If π∈Sn and π=π1π2···πn denotes its one-line notation, we say π has a peak at i if πi−1<πi> πi+1 . So for example, π=231∈S3 has a peak at 2 and σ=23154∈S5 has a peak at 2 and a peak at 4, while the permutation τ=1234 has no peaks. Definition 2.2.2 — Peak set of a permutation. Now the peak set of a permutation π is the set of peaks in π: P(π) = {i∈[n]:iis a peak of π}. Given a subset S⊂[n], we denote the set of all permutations with peak set Sby P(S;n) = {π∈Sn:P(π) = S}. We then say that a set S is called n -admissible if P(S;n)=/0 . Here is an example: If S1=/0 and S2={2}, then P(S1;3) = P(/0;3) = {123,213,312,321} P(S2;3) = P({2};3) = {132,231}. DRAFT 24 Chapter 2. Permutations with No Peaks 2.2.2 Proposition One question worth asking is: How many permutations in Snhave a given peak set? Sara Billey, Krzysztof Burdzy, and Bruce Sagan answered this in full generality 1 . Here we now present the proof when S=/0, that is count the number of permutations with no peaks. Proposition 2.2.1 If n≥1, then |P(/0;n)|=2n−1. Proof. If π∈P(/0;n) then the plot of the figure either always increases, always decreases or decreases and then increases. See the examples we have in the figure on page 1 for the permutation 123 (always increases), 321 (always decreases), or 213 and 312 (which first decrease and then increase). So in general a permutation with no peaks can be written as π=πL1πR where πL,πR are the portions of π to the left and right of 1 , respectively. Notice that πL could be empty, which would mean the permutation π=123···n . Likewise πR could be empty, in which case the permutation π=n(n−1)···321 . This means that P(π) = /0 if and only if πL is decreasing and πR is increasing. So |P(/0;n)| depends on a choice of what numbers appear in πL . That is the number of choices of a subset of elements from the set {2,3,4,...,n} with which we can create πL , and once we know what numbers make up πL , then we know exactly the numbers that make up πR , as it is the remaining numbers we did not select. Note that the number of ways we can then create πL depends on how many elements we select. If i denotes the number of numbers in πL , then i can range from 0 to n−1 . For each i , the number of possible πL’s we can construct is given by n−1 i. Then we must sum over all possible values of i . This yields that the total number of permutations with no peaks is given by: n−1 ∑ i=0n−1 i. We can then verify that this is precisely 2n−1 . One could note that this is also the number of subsets of the set {2,3,...,n}.■ 2.2.3 Acknowledgements This short note and the ending result brought me to a very happy set of memories. Not because it is my favorite result but because it reminds me of how important it has been for me to find the right set of mathematicians to work with. Insert dramatic/sad music here... I do not remember when I completely lost desire to do research math, but that is what happened at the end of my PhD years. Luckily, I met Dr. Erik Insko, who since 2012 transformed the way I looked at research mathematics. It was Erik who introduced me to the work in 1 after he visited University of Washington (where Sara and Krzysztof work) and Sara shared her work with Erik pointing him to an open conjecture in their manuscript. Erik showed me this problem and told me we should work on it. I was quite unsure and doubtful that I could contribute anything to solving pen problems of very famous mathematicians. Yet Erik thought we might have new insights since we had not thought about it before and sometimes it took a new perspective to solve a problem. DRAFT NOTES 25 Well I was absolutely doubtful, but I trusted Erik and I knew that even if we could not solve the problem our meetings would be fun and we wold enjoy working on it. Lo and behold, with the right set of people (we added the brilliant Alexander Diaz-Lopez and Mohamed Omar to the team), we eventually did solve the conjecture 2 and even later got to collaborate with Bruce Sagan on a follow up paper 3. The lesson I take from this is: no matter how small and under prepared I may feel, the right set of mathematicians have helped me grow and develop. In community with them I do my best work. Notes 1 S. Billey, K. Burdzy, and B. E. Sagan. Permutations with given peak set. Journal of Integer Sequences, Vol. 16, Article 13.6.1, (2013). 2 A. Diaz-Lopez, P. E. Harris, E. Insko, and M. Omar. A proof of the peak polynomial positivity conjecture. Journal of Combinatorial Theory, Series A 149 21–29., 2017 3 A. Diaz-Lopez, P. E. Harris, E. Insko, M. Omar, and B. Sagan. Descent polynomials. Discrete Mathematics 342 1674–1686, 2019. DRAFT 32 Chapter 3. Infinitude of Primes Follow-up to the above fact: Fact 3.2.3 — Infinitude of natural numbers. There are infinitely many positive natural numbers, 1,2,3,..., continuing by adding 1. Fact 3.2.4 — Weak Fundamental Theorem of Arithmetic. If b is a positive natural number, then there are two (mutually exclusive) cases: 1. b=1 2. bis divisible by a prime number We have an infinite set of natural numbers. In fact, finding bigger natural numbers amounts to adding 1 . As a subset of the natural numbers, what can we say about the set of prime numbers? Unlike the naturals, the set of prime numbers is not characterized by being able to add 1 to a prime number to produce another. So... Question 3.2.5 How would we find bigger and bigger primes? Question 3.2.6 How do we know they exist before we go on a search for their values? We will address the last question first. Then we will revisit the idea of finding primes in a systematic way in later chapters! 3.2.2 Theorem Theorem 3.2.7 — Infinitude of primes. The set of prime numbers is infinite. Proof of Theorem 3.2.7. Fact 3.2.2 talks about infinite sets. It gives some motivation to pick up an arbitrary prime p and think on how we can find a prime q bigger than p . Let’s show we can always find a bigger prime! This proof will rely on the infinitude of the natural numbers (Fact 3.2.3) and the claim that for any natural number n, there is a prime number bigger than n(Claim 3.2.8). Natural Number nPrime number >n 0 2 1 2 2 3 3 5 Table 3.1: Verifying Claim 3.2.8 Now let’s suppose Claim 3.2.8 is true: Each natural number n will lead to the existence of at least one prime q greater n . Since prime numbers are natural numbers themselves, we would apply the claim by replacing the more general "each natural number" with the more specific "each prime number": Each prime number p will lead to the existence of at least one prime q greater p . This is a point where we could use Fact 3.2.2 to conclude that the set of primes is infinite. [In particular, let’s call the set of prime numbers S . Then S is nonempty and, if our claim is true, for each (prime number) x in S there is a bigger (prime number) y in S . So the set S of prime numbers is infinite by Fact 3.2.2.] DRAFT NOTES 33 Now we only need to show our claim is true! Here’s our claim again: Claim 3.2.8 — Always a bigger prime. For any positive integer n , there is a prime number bigger than n. Proof of claim 3.2.8. Note that this is a direct proof. We are not assuming a statement is true with the plan of reaching a contradiction caused by the assumption. We will use the definitions and facts above, along with their connections, to show that for any natural number n that there is a prime number pbigger than n. To start, we need a natural number n . Since every prime p is bigger than the natural numbers 0,1 , we will consider n to be at least 2 from here on. By Definition 3.2.2, n! is at least 1 . Hence n!+1 is at least 2. We just showed n!+1 is a natural number bigger than 1. Fact 3.2.4 shares information about natural numbers bigger than 1 : Since n!+1 is a natural number bigger than 1, a prime number pdivides n!+1. How big must the prime number pbe? At this point we have a prime number pthat divides n!+1. Subgoal: If we show that this prime number p is not equal to any of 2,3,...,n , then p would have to be a prime number bigger than n . We can use the condition that p divides n!+1 to show p is not equal to 2,3,...,n. Fact 3.2.1 deals with divisibility of a sum such as n!+1 . Now the numbers 2,3,...,n , all divide n!= (1)(2)(3)···(n) . At the same time, none of 2,3,...,n , divide 1 , which is a smaller positive number. By Fact 3.2.1, none of 2,3,...,n , can divide the sum n!+1 . We have achieved our subgoal: All primes are bigger than 1 , and the prime p is not equal to 2,3,...,n . Thus, p is bigger than n . ■ For every natural number n we showed that there is a prime p bigger than n . We did so by the following reasoning: i) There must be a prime pthat divides n!+1 (Fact 3.2.4) ii) The primality of pprevents it from being 0,1 (Definition 3.2.1) iii) That pdivides n!+1 prevents it from being 2,3,...,n, (Fact 3.2.1) So p is a prime bigger than n . We have proved Claim 3.2.8. The proof of Theorem 3.2.7 is now complete! ■ Notes 1At Nokomis I had Ms. B 2Sundaram was a graduate student when producing a sieve for primes DRAFT DRAFT 4. Gaps in Knowledge Author:Dwight Anderson Williams II Click here for Dr. Dwight Anderson Wiliams II’s story. 4.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 4.1.1 The Theorem Please read up to and including the statement of Theorem 4.2.1. •Explain in your own words what the theorem says. • Which of the facts introduced in the Introduction to Primes section might be useful for proving this? 4.1.2 The Proof Read the proof stopping after the sentence that begins “By Fact 4." •Explain how Fact 3.2.1 implies that kdivides n!+k. •How have we proven that n!+kis composite? • The proof says that n!+k has three distinct factors. Does this mean exactly three or at least three? • How does this section of the proof relate to the theorem statement? Please read the rest of the proof and the question at the end of the chapter. • Why do we need to argue that there is a prime less than and greater than this string of numbers? •How does the last line of the proof use Fact 3.2.3? • Why could the primes around this gap be as close as n!+1 and n!+n+1? • Why does this create a gap of at least n? • How do we know we could create such a gap for any natural number n? DRAFT 36 Chapter 4. Gaps in Knowledge • How would you answer the question at the end of the chapter? DRAFT 4.2 Gaps in Knowledge 37 4.2 Gaps in Knowledge 4.2.1 Introduction Note: The previous chapter included a section called Introduction to Primes with many relevant definitions and ideas. If you have not yet read that section or need a refresher, please do click here to go back and revisit the Introduction to Primes. Definition 4.2.1 — Prime gap. Aprime gap is the difference between two primes that have no other primes between them. Yes, the primes are infinite in number. And Fact 3.2.1 along with Definition 3.2.2 helps us see that there can be really big gaps between primes. 4.2.2 Theorem Theorem 4.2.1 There is no largest prime gap size. Proof of Theorem 4.2.1. This proof will rely heavily on Fact 3.2.1, where we consider factors of n!+k for positive k smaller than or equal to n . As such, let’s begin with positive natural numbers n and k with k less than or equal to n . Then k divides n!= (1)(2)···(k−1)(k)···(n−1)(n) , and k divides k. By Fact 3.2.1, kdivides the sum n!+k. So for n>2, 2 divides n!+2 3 divides n!+3 . . . ndivides n!+n In other words, 1,k,n!+k , all divide n!+k . So when k is not equal to 1 (therefore, bigger than 1 ), the number n!+k has three distinct factors. By Definition 3.2.1, n!+k is composite. Thus, the string of numbers n!+2,n!+3,...,n!+n are all composite. By Fact 3.2.4 there is a prime that divides n!+2 ; thus, there is a prime less than these string of numbers. By Theorem 3.2.7 (or the now-proved Claim 3.2.8), there is a prime bigger than these string of numbers. These primes could be as close as n!+1 and n!+n+1 , which is a gap of n . So the closet primes before and after this string of composites n!+2,n!+3,...,n!+n , have a gap of at least n between them. As desired, we showed that for each n there is a prime gap of at least size n . That is, with the infinitude of the naturals (Fact 3.2.3), there is no largest gap between primes. ■ Question 4.2.2 Can we use this observation to conclude that prime gaps can be any natural number? Notes 1At Nokomis I had Ms. B 2Sundaram was a graduate student when producing a sieve for primes DRAFT DRAFT 5. Tic Tac Toe Games Author Story: Alexander Diaz-Lopez School Years. When I was a kid, I spent a lot of time playing card games, puzzles, and board games with my cousins and sister in a small town called San Lorenzo in the archipelago that we call Puerto Rico. These games allowed me to connect with math and logic in a way that was different from school. Whether it was finding the logic to solve a puzzle or simply counting dominoes to record the score of a game, I really enjoyed it all. In school, the story was a little different. I always performed well in math classes but found them repetitive and not very interesting. It all changed when I joined an after-school math club called “El Triángulo de las Matemáticas", in which we were asked to solve complicated and challenging problems. The thrill I felt when solving a really difficult problem was something that hooked me. At the time, I decided I wanted to become a high school math teacher, just like the director of “El Triángulo de las Matemáticas”, Mr. Jorge Haddock. College Years. Not knowing better, during my senior year of high school, I only applied to one university, the local University of Puerto Rico and enrolled in their math program. As part of my education courses, I had to visit local high schools and interview teachers. After some challenging experiences doing so, I decided not to pursue a career as a high school teacher. At the time, one of my professor suggested that I should apply to summer research programs as I may enjoy research and could become a college professor. So, I did. My first summer research program was challenging. After the first couple of days, I told my advisor I was completely lost and ready to go back home. He insisted I stayed and he worked with me on a problem that eventually became part of a paper we wrote. Looking back into it, I gained a lot from the experience; however, during it, I always felt like I was not up to the task. The next DRAFT 40 Chapter 5. Tic Tac Toe Games summer I participated in a second summer research program, which I really enjoyed and helped me decide I wanted to pursue a career as a faculty and researcher. Graduate School. ... Fast forward some years and now I teach a course called Mathematics of Games. In it, we delve deep into the mathematics behind some popular games and puzzles like Sudoku, Rubik’s Cube, Monopoly, SET, BINGO, and others. This is at Villanova University, where I am a faculty in the Mathematics and Statistics department. For more details about my story, I recommend reading the Testimonios chapter 1. In what follow, you will see a small sample of the sort of questions I like to think about when I think of games. These three particular topics were carefully chosen to highlight some math techniques that are of wide use, particularly in a field of mathematics called Combinatorics. In the first topic, we will see the power of using symmetry to simplify arguments or counts. In the second topic, we will see how splitting a problem into subcases leads to a way to solve what might initially appears as an intractable problem. In the third case, we will use the power of recursions to solve our problem. I hope you read them with an open mind and willing to write your own notes, try your own examples, complete the missing cases we skip, and ultimately, enjoy developing math skills while thinking of games. DRAFT 5.1 Reading Prompts 41 5.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 5.1.1 Prior to Proof Start by reading the Introduction section. 1. What do you think the rest of the this text is going to prove? 5.1.2 The Proof for Tic-Tac-Toe with 5 Marks Start by reading the first paragraph of the Counting the Tic-Tac-Toe games with 5 marks section. 2. Consider the following 5 mark board. What are some sequences of moves that could have arrived at this board? X O O X X Read the rest of the Counting the Tic-Tac-Toe games with 5 marks section. 3. What are the 8 cases? 4. Why do these cases cover all possible games? 5. Which of the following boards would be captured in case 1? X O O X X X X X O O X X X X O O X X O X O 6. Provide an argument similar to the one in the proof to explain how many games can end with X’s down the diagonal from top left to bottom right. 7. Why do all cases have the same number of games? (i.e., why do we multiple the total by 8?) 8. Why do we not have to consider games that player 2 won in the 5 mark scenarios? 5.1.3 The Proofs for Tic-Tac-Toe with 6, 7, 8, or 9 Marks Read the first two paragraphs of the next section, Counting the Tic-Tac-Toe games with 6 marks. 9. Why do we end up with 6 · 3 · 5 · 2 · 4 · 1 games?) Next, read the next paragraph of the next section, Counting the Tic-Tac-Toe games with 6 marks. 10. Create a game board that has six marks that would not be possible. Next, read the rest of the section, Counting the Tic-Tac-Toe games with 6 marks. 11. Sketch a board to illustrate the concrete initial case “where player 2 is to place the O’s in row 1” and “player 1 is to place the three X’s in row 2”. Why do we “have 3 · 3 · 2 · 2 · 1 · 1 = 36 ways of doing this?” 12. The proof states, “Thus, we have counted 6·72 =432 .” What does the 6 count? What does the 72 count? Why do we multiply them? Finally, read the last section, Tic-Tac-Toe games with 7, 8, or 9 marks. 13. Why do we only need to consider up to 9 marks? 5.1.4 After the Proofs 14. Can you summarize this proof’s argument that there are 255,168 games in a couple of sentences? DRAFT 48 Chapter 6. Tower of Hanoi and in order to solve the puzzle, all other n−1 disks must be placed on top of the largest disk. Once again, this takes at least Tn−1 moves. Hence, any optimal solution must take at least 2·Tn−1+1 moves. Thus, our proposed method is optimal and Tn=2·Tn−1+1. Using this recursion, we can now compute some of the values of Tn: 1,3,7,15,31,63,127,... . Looking at this sequence, one may notice that these numbers are one less than powers of 2 and guess that Tn=2n−1. In the next section, we use induction to prove that this is indeed the case. 6.3.3 Closed formula for Tn We now proceed by induction to prove that Tn=2n−1 . For n=1 , we had established that T1=1 and this matches our formula 21−1 . Suppose the result is true for some Tk , that is, suppose that Tk=2k−1. Then, by our recursive formula, Tk+1=2·Tk+1=2·(2k−1)+ 1=2k+1−1. Hence, the result is true by induction. DRAFT 7. Infinitely Many Primitive Pythagorean Triples Author Story: Edna Jones When I was a little girl, I enjoyed problem solving and exploring mathematics. I remember having fun solving math problems and logic puzzles in books my parents bought for me. As a girl, I really enjoyed math. However, I wanted to keep math as a hobby and try to get a job related to math but not pure math. During the summer between second and third grade, I went to an engineering day camp in which us kids built a small bridge on which we could crawl across. During that summer, I decided I wanted to be a civil engineer; I wanted to design bridges and buildings. I still had this desire to become a civil engineer when I entered college at Rose-Hulman Institute of Technology. I started out as a civil engineering major, and I even had a civil engineering internship before I entered college. However, a number of things occurred during my freshman year of college that encouraged me to switch my major to mathematics during the spring of my freshman year. One of the things I realized is that I preferred proving theorems instead of merely applying them. One thing I liked about Rose-Hulman is that I could easily talk to multiple math professors about math. One of the proofs I chose for this project (the proof about infinitely many primitive Pythagorean triples) is one of the first proofs I came up with by myself. After I conceived of the proof, I was able discuss it with a few Rose-Hulman math professors. One of them (Dr. John Rickert) showed me and proved the following parameterization of essentially all primitive Pythagorean triples. DRAFT 50 Chapter 7. Infinitely Many Primitive Pythagorean Triples Theorem 7.0.1 The triple (a,b,c) , where a is odd and b is even, is a primitive Pythagorean triple if and only if there exist coprime integers s and t which are not both odd such that s>t>0 and a=s2−t2, b=2st,and c=s2+t2. These rich mathematical conversations encouraged me to do math. They also helped illustrate that I was capable of doing math, possibly at the graduate-school level. My undergraduate professors also helped me have the opportunities, experiences, and preparation so that I could be successful in graduate school. As an undergraduate student, I explored a variety of careers. I did a software engineering internship to check that I didn’t enjoy programming enough to create a career out of it. I also did two Research Experiences for Undergraduates (REUs) in mathematics. From my REUs, I confirmed that I like number theory. I also learned that math research could be fun, but I disliked doing research under pressure. Since receiving my bachelor’s degree in mathematics, I have taught a few college courses and participated in a number of math outreach organizations and events. Through my teaching and math outreach, I try to convey that everyone (not only white men) can do math, that math is more than computation and arithmetic, and that math can be fun. For example, in 2019, I co-organized the “Mathematical Games and Puzzles from Around the World!” booth at Rutgers Day, engaging the general public in mathematical games and puzzles (including some from China, Ghana, and New Zealand). Some people (including a group of women) were hesitant to approach our booth because of the word “mathematical.” However, once these people got engaged in the games, we could see that they were having fun with the mathematical problem-solving involved, showing these people that they could do math. Events like this work towards dispelling the stereotype that only certain people can do math. By dispelling this stereotype, we create a more inclusive culture for mathematics. I have had the fortune of having multiple supportive mentors throughout my life. These mentors definitely helped me get through some tough moments. Without these mentors, I am fairly certain that I would not be in the position that I am in now. I am currently (as of 2023) an assistant research professor at Duke University. My position allows me to do some teaching, research, mentoring, and outreach, enabling me to explore what I want to do in the long term. I would be remiss if I did not mention something about being a woman of color in a primarily white male profession. In mathematics, there are a bunch of stigmas associated with being a woman and a person of color. Some of these stigmas have directly impacted me. In addition to having several supportive mentors, a thing that has helped me through the years is having a sense of self with which I am comfortable. I believe that my identity and my upbringing helped me develop this sense of self. I grew up in Iowa, and my parents both immigrated to the U.S. (my father from the Caribbean, my mother from China). I’ve lived in multiple worlds for most of my life. Although I lived in Iowa, I spent several summers in China. I am often the odd one out racially and/or culturally wherever I go. I remember that I was one of the two kids with curly hair in my kindergarten class of about 20 DRAFT 51 students (and the other curly-haired kid was white). To the best of my knowledge, I am the first black woman to receive a Ph.D. in mathematics from Rutgers. Being somewhat alone racially and culturally from a young age pushed me to develop my own identity and to attempt to be comfortable with being the only one in a variety of settings. I am realizing that my unique identity has allowed me to mentor students in ways many other mathematicians do not. I have discovered that I enjoy helping others flourish as much as possible with whatever path they may choose, so I think my long-term career plans will involve mentoring in some form. My hope is that I will continue to do math and be a mentor for others as I obtain a more permanent job in the future. DRAFT 52 Chapter 7. Infinitely Many Primitive Pythagorean Triples 7.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 7.1.1 Prior to Proof First, read the introductory section, which introduces the concept of Pythagorean triples. 1. What questions have you had as you were reading? 2. What does it mean to be a primitive Pythagorean triple? 3. What does it mean to have a greatest common divisor of 1? 4. Is 6,8,10 a primitive Pythagorean triple? 7.1.2 The Theorem Now, read the theorem statement. 5. What will we need to prove? 6. Can you provide an example of a primitive Pythagorean triple in the form provided in the theorem? 7.1.3 The Proof First, read over the entire proof. Don’t worry about understanding every single detail, but rather get a feel for the overall idea. 7. How would you break this proof into parts? Can you explain what each part is doing? Read the proof, stopping after the statement, ’so the Tkare distinct.’ 8. Why does the string of inequalities (3) true? 9. Why do we know that each Tk is distinct? [Note, students may infer that the coordinates of the triples are distinct, but there is a need to make the argument that the different Tk ’s are distinct.] Continue reading the proof, stopping after the statement ’Therefore, Tkis a Pythagorean triple.’ 10. What theorem is being used to establish that the Tk’s are Pythagorean triples? Now read the rest of the proof and chapter. 11. What is this section of the proof accomplishing? 12. Why does any common divisor of 2k+1 , 2k2+2k , and 2k2+2k+1 divide (2k2+2k+1)− (2k2+2k) = 1? 7.1.4 After the Proof 13. Would this proof have worked if we used 3k+1,3k2+3k,and 3k2+3k+1 instead? 14. Can you summarize this proof’s argument in a couple of sentences? DRAFT 7.2 Infinitely Many Primitive Pythagorean Triples 53 7.2 Infinitely Many Primitive Pythagorean Triples 7.2.1 Introduction Definition 7.2.1 — Pythagorean triple. APythagorean triple (a,b,c) is a triple of positive integers a,b, and csuch that a2+b2=c2.(7.1) Definition 7.2.2 A Pythagorean triple describes the three side lengths of a right triangle, where c is the length of the hypotenuse of the triangle. (See Figure 7.1.) Definition 7.2.3 A Pythagorean triple (a,b,c) is primitive if the greatest common divisor of a , b , and cis 1. a b c Figure 7.1: A right triangle with side lengths a,b, and c. The length of the hypotenuse is c. In my freshman year of college, I had a physics professor say during a lecture that there are only finitely many primitive Pythagorean triples: I think he only knew of (3,4,5) , (4,3,5) , (5,12,13) , and (12,5,13) . Shortly after that lecture, I showed him a couple more primitive Pythagorean triples. Within a day or two, I came up with a proof showing that there were infinitely many primitive Pythagorean triples. The proof was inspired by the fact that each positive odd number appears as the difference of two consecutive perfect squares. Because there are infinitely many odd perfect squares, I reasoned that there had to be infinitely many primitive Pythagorean triples. My reasoning is more formally stated in the following theorem and proof. 7.2.2 Theorem and Proof Theorem 7.2.1 There are infinitely many primitive Pythagorean triples. Namely, for each positive integer k, the triple (2k+1,2k2+2k,2k2+2k+1)is a primitive Pythagorean triple. Proof. For a positive integer k, let Tkbe the triple Tk= (2k+1,2k2+2k,2k2+2k+1).(7.2) For a positive integer k, notice that 0<2k+1<2k2+2k<2k2+2k+1,(7.3) so the Tk are distinct. Therefore, to show that there are infinitely many primitive Pythagorean triples, it suffices to show that each Tkis a primitive Pythagorean triple. DRAFT 54 Chapter 7. Infinitely Many Primitive Pythagorean Triples Let kbe a positive integer. Then (2k+1)2+(2k2+2k)2=4k2+4k+1+4k4+8k3+4k2 =4k4+8k3+8k2+4k+1 = (2k2+2k+1)2. Therefore, Tk is a Pythagorean triple. Because any common divisor of 2k+1 , 2k2+2k , and 2k2+2k+1 would divide (2k2+2k+1)−(2k2+2k) = 1 , we know that the greatest common divisor of 2k+1, 2k2+2k, and 2k2+2k+1 is 1. Thus, Tkis a primitive Pythagorean triple. ■ This proof is important to me, because it was the first proof that I remember coming up with by myself. DRAFT 8. Qis Countable Author Story: Priyam Patel I was born and raised in Bayonne, NJ, a city across the Hudson River from Manhattan. The city has a long history of immigration embedded into its identity that has shaped both its culture and its residents. Growing up there also shaped me in many ways. As a child and teenager, I was diligent and shy at school, while being loud, goofy, and creative at home. Most of my weekends were spent gathering with our large extended family, celebrating our Indian heritage. I remember these times fondly. I felt, and still feel, at home with my cousins, in sharp contrast to how out of place I felt at school. There were only a handful of other Indian families in Bayonne at the time, and at the time I found it very difficult to “fit in”. Despite these challenges, I loved my schooling and education. I became fascinated with mathematics in high school while learning to do proofs in geometry class. I was fortunate to have excellent high school math teachers, who encouraged me to consider majoring in math in college. I went to a program called Governor’s School the summer after my junior year of high school, and for the first time, I felt like I could be my full self amongst my peers. I was surrounded by other teens who loved math and science, and this was the first time I felt that my academic self was not disjoint from who I am as a person. I came back from that program changed, and was much more outgoing and outspoken in my senior year of high school. I then attended New York University (NYU). There I had a couple of professors who really believed in me. My professor for multivariable calculus, Dr. Cliona Golden, spent a lot of time DRAFT 56 Chapter 8. Qis Countable with me in office hours and gave me challenging problems to work on. She was very encouraging and had a huge impact on me and my choice to continue doing mathematics. On the other hand, I often felt out of place in many of my classes at NYU as a woman of color. I remember constant signaling from my peers and other professors that I didn’t belong in math. I found refuge from these experiences through my hobbies and social life, and especially through my participation in a competitive collegiate dance team. Despite some challenges, I continued to excel in my coursework and was accepted into the math Ph.D. program at Rutgers University. Unfortunately, I started to deeply doubt myself as a graduate student. The continued signaling that I didn’t belong in math was exhausting, and it did break me eventually. Though I had solved my thesis problem quickly, I no longer wanted to do research mathematics. It was only through the unwavering encouragement of my advisor, Dr. Feng Luo, that I even applied to research postdoctoral positions. My self-doubt continued into my first postdoctoral position at Purdue University. Thankfully, things started to change towards the end of my position at Purdue and the start of my second postdoctoral position at UC Santa Barbara. I started many collaborative research projects with my mathematical peers and realized that working with other mathematicians was a huge source of joy for me. Most of my collaborators were at the same career stage as me, but at different universities. The weekly virtual meetings we had, slowly chipping away at our research projects, taught me a lot about perseverance and community in mathematics. I became more comfortable with the fact that mathematics is very hard and that challenges are ok. It was extremely helpful going through the tough parts of being a young academic with these peers. I also started learning to celebrate my successes more, focusing on the joy that mathematics brings to my life. The positive feedback I received about my papers and research talks made me start to feel like a math person. This feeling only grew when I was awarded an NSF Research Grant while at UCSB. In addition, I started mentoring undergraduate and graduate students. Interacting with students and teaching them about my research area became one of the most fulfilling aspects of my job. I also sought out mentors who believed in me and encouraged me through difficult times. I came to realize that I find the most meaning in mathematics through human connection and interaction. I continued to build upon my service to the mathematics community and specifically in supporting women and people of color in math during this time. Once again, I realized that I was allowed to bring my whole self to my mathematical experiences and I wanted others to know they are allowed to do the same. Most importantly, I worked to find a community of mathematicians where I do feel like I belong. The mathematicians I am closest to are not only my colleagues, but also my friends. We connect on shared values and views, and work together to promote equity and justice in the mathematical community. I have been fortunate to connect with many outstanding women of color both within geometry and topology and in other fields of math. These women, and future generations of women of color in math, are the reason that I have stayed in mathematics. This is not to say that I don’t experience struggles today. I am the only woman research faculty in pure math at the University of Utah and the only woman of color faculty in our entire math department. This does not come without its challenges. But I am able to overcome these struggles through support from my community and a lot of self-talk that I *do* belong in mathematics, that I am here for a reason, and that I won’t stop fighting to make mathematics a more diverse and inclusive practice. In addition, math is not my whole life! I also enjoy rock climbing, yoga, dancing, painting, music, and spending lots of time with family and friends. Without these other parts of my life, I would not feel fulfilled. DRAFT 57 I wrote the proofs I contributed to show students how fun math, and specifically geometry and topology, can be. There are certainly tough parts in every proof, and those tough parts are there to show students that struggling initially is ok. I specifically included the proof of the Brouwer Fixed Point Theorem to show students that exciting math is just around the corner. With a few assumptions, we are able to prove a very difficult and influential theorem, and I hope that this sparks a bit of inspiration in them. DRAFT 64 Chapter 9. When an Operation Commutes, must it be Associative? need to learn analysis. The tiny catholic college didn’t offer it, so he set me up with a book, and we met weekly so I could learn this new area. The fresh start of grad school opened up a whole new world for me in so many ways. I think it is impossible to de-entangle living my life as an out gay person and living my life in the joy of mathematics. I made friends with whom I would spend hours working out challenging problems from our classes, but also went to our on campus LGBT group with me. I had a wonderful advisor, Risto Atanasov, who introduced me to Galois Theory – a theory that connects together so much of mathematics and provides powerful insights – like the one in the Impossibility proof provided. My interest in abstract algebra from undergraduate became a passion as I finally got derive a new Theorem on my own. It was not the theorem that my advisor thought I would arrive at, and it took months of work. I can still picture when it became clear to me – sitting on an airplane and suddenly needed to jot it down. There is something about wrestling with ideas for long to finally arrive at something new that brings such a powerful sense of accomplishment. Mathematics is not about finding quick answers. Mathematics is about one million false starts and then finally having an insight. Seeing a new connection. Thinking of a new question to ask and explore. Eventually, I became increasingly curious as to why my experience in proof-based courses was not always the same as my friends. How were they thinking about things? What do students think about in general when creating proofs or doing abstract algebra? This led me to find a math department where I could keep doing math but also study math education for my Ph.D. I found one at Portland State where I learned math education is a big jumble of subjects: math, psychology, sociology, philosophy, and many more. It’s a subject where I just feel at home. After my Ph.D., I arrived here, at Texas State. I am a researcher at heart, and I feel like I get to study a little bit of everything. I am able explain how students think about many big ideas in proof-based courses. I got to write up some of these proofs that I find useful and fascinating and share them with you. Sometimes, I still think back to the blue collar town I grew up in – I had a deep work ethic instilled in me. My parents worked jobs ranging from hotel maid to factory floor jobs. In their thirties, they both got their degrees after piecing together coursework while also working full time. And now, I get to put Dr. in front of my name, an outcome that seemed impossible, and one that I still feels surreal to me. I still spend my free time watching Philly sports like my friends and family back home. I am still fundamentally part of this blue collar community. I live life as an out and happy queer person. I am also fundamentally part of the LGBT community. And I am still thinking about mathematics and mathematics education all the time. I bring all my experiences and communities with me to my academic home where I can walk over to the office next to me, and say to a colleague, “I was watching a baseball game and this new idea jumped into my head. What do you think?” And then all the joy in the work, and thinking, and learning, and stumbling blocks start anew. DRAFT 9.1 Reading Prompts 65 9.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 9.1.1 Prior to Proof Start by reading the first page stopping just before the statement labeled "conjecture". 1. The text gives multiple examples of binary operations. Explain how the example "real numbers under multiplication" fits the definition of a binary operation. [Elaborate if needed: In this case, what is S, what is the circle, and what are a and b?] 2. For the definition of the associative property, what is different about the two sides of the equation and what does it mean to say they are always equal? [Invite them to use an example if needed.] 3. What is an example of a binary operation that is not associative? Can you give an example where the defining equation is untrue? 4. How would you explain what it means to say that a binary operation is commutative? 9.1.2 The Theorem Now read the conjecture and what follows including the blue sentence. 5. What would we need to find to prove that the conjecture was false? 6. Why does the text suggest that we are stuck in showing that the binary operation is associative? Why are there no other manipulations of the expression that we can make? Now read the text stopping right before the statement labeled "subclaim". 7. What does the text mean when it says that many binary operations could serve as a counterexample? [Elaboration if needed: A counterexample to what? What properties should a counterexample have?] 8. Why does the floating point method of representing numbers create some rounding error? 9. How is FP addition different from normal addition of two real numbers? 9.1.3 The Proof Start by reading the subclaim and the proof, stopping at the box symbol on the right. 10. How does the proof prove that FP addition is commutative? 11. Why does the proof introduce zeros into one of the two numbers being added? 12. What does the proof mean when it says "without loss of generality, assume q≤r?" 13. Why does the proof introduce this notation with variables instead of using two example numbers? Now read the rest of the text. 14. What does it mean to say that one property "implies" another? 15. How does the proof prove that FP addition is not associative? 16. Why does this proof use specific numbers when the previous one used variables for the numbers? 17. How is this revised statement of the conjecture related to the statement of the conjecture earlier in the text? DRAFT 66 Chapter 9. When an Operation Commutes, must it be Associative? 9.2 Commutative implies Associative? Algebra is the study of structures formed by sets and operations. We can consider a set of elements S and a binary operation defined on that set of elements as ◦. Definition 9.2.1 — Binary Operation. Abinary operation is a function ( ◦ ) that takes all a,b∈S and produces an output that is also in S. That is, if a,b∈S, then: a◦b∈S. If we think back to all the mathematics we have done, we have seen lots of sets with binary operations. For example: • Integers under addition • Functions under function composition • Real numbers under multiplication • 2x2 matrices under matrix multiplication When we study sets and operations, we are often interested in what kinds of properties they have. In prior classes you might have talked about properties like the the identity property, commutative property, and associative property. In fact, all of the examples provided above have the associative property. Definition 9.2.2 — Associative Property. For all a,b,c∈S,(a◦b)◦c=a◦(b◦c). However, not all of them have the commutative property. Definition 9.2.3 — Commutative Property. For all a,b∈S,a◦b=b◦a. The 2x2 matrices under matrix multiplication and functions under function composition do not commute for all elements. We can also think of some operations that are not commutative and not associative such as the integers under subtraction. This leads to a pretty natural conjecture. If a binary operation is commutative, it is also associative. Take a second and think about some of the sets with binary operations you know. It seems like most of them fit this conjecture. If we are going turn this conjecture into a fact, we need to either prove it is true or find a counterexample. Proof. Let S,◦ be a set with a binary operation such that, a◦b=b◦a for all a,b∈S. Then let a,b,c∈S. Consider (a◦b)◦c. (a◦b)◦c= (b◦a)◦c=c◦(a◦b). Hm. My goal should be to get to a◦(b◦c) but commutativity does not seem to be helping me. Back to the drawing board. ■ 9.2.1 Back to the Drawing Board It doesn’t seem like we have enough information to prove this, so perhaps there is a binary operation we are not considering. In fact, there are many binary operations that could serve as counterexamples. Let’s explore a particular set and binary operation found frequently in how we store and compute numbers. Definition 9.2.4 — Floating Point Method. Floating point is a method of representing a noninteger number by storing the number as digit string of a given length (represented in a given base). This digit string is an integer referred to as a significand and is scaled by some a base to an integer exponent scale. A number that can be represented in this way is is called a floating DRAFT 9.2 Commutative implies Associative? 67 point number. Let’s stay in base 10 to make our lives easier. Suppose we want to work with a digit string of length 3. The number 2436 could be represented as 2.44 and the scale would be 103 . Notice that 2.44 ×103=2440 meaning there is some rounding error in this method. (You might recognize this looks like scientific notation.) Definition 9.2.5 — FP Addition. The FP addition binary operation, would take a two floating point numbers, represent them as string of set length multiplied by the scale, add them together, then convert the result into floating point representation with the same length. To FP-add 2436 and 352.679, we convert to 2.44 ×103and 3.53 ×102. 2.44 ×103+3.53 ×102=2.44 ×103+.353 ×103 =2.793 ×103 =2793 =2.79 ×103. This system is going to let us create a counterexample. This requires that the operation be commutative and not associative. FP Addition in base 10 on the set of FP numbers is commutative. Proof. Let a and b be FP numbers. Let the digit string be of length n and the scale be base 10. Then a=a1a2...an×10q and b=b1b2...bn×10r where q and r are integer powers. Without loss of generality, assume q≤r . Let d=r−q . Then a1a2...an×10q+b1b2...bn×10r implies a1a2...an×10q+b1b2...bn0...0 (dcopies of 0) ×10q. a1a2...an×10q+b1b2...bn0...0×10q= (a1a2...an+b1b2...bn0...0)×10q = (b1b2...bn0...0+a1a2...an)×10q =b1b2...bn×10r+a1a2...an×10q So a+b=b+a■ [Revised] A binary operation being commutative does not imply it is associative. Proof. By the prior argument, FP-addition is commutative. We can now provide a counter example to show that associativity does not always hold. We will use length 3. Let a=2436, b=352.679, and c=572.5, then (a+b)+c= (2.34 ×103+3.53 ×102)+5.73 ×102 = (2.69 ×103)+5.73 ×102 =3363 =3.36 ×103 and DRAFT 68 Chapter 9. When an Operation Commutes, must it be Associative? a+(b+c) = 2.34 ×103+(3.53 ×102+5.73 ×102) =2.34 ×102+9.26 ×102 =3266 =3.27 ×103 Since 3.36 ×103=3.27 ×103, associativity does not hold in general. ■ Since numbers are often stored using floating points in different systems (such as Excel which is accurate to 15 digits), there is a risk that our normal operations will break down when it comes to associativity due to the rounding process in the floating point method. This suggests, we certainly need way more than 3 digits. Any rounding introduces the risk that operations will not be associative, so be careful with your very large numbers! DRAFT 10. Closed Formula for the Fibonacci Sequence (by Induction) Author Story: Rebecca Garcia I was born and raised on the island of Guam, where my love for math began. Like many other mathematicians, I excelled in grade school mathematics, but the first time I truly began to enjoy mathematics was during my junior year in high school, when I took Algebra 2 and Trigonometry with the legendary Melvin Perry. I remember how Mr. Perry would howl in celebration when we found a different way of deriving some obscure trig identity. He always had a way of making each one of us feel special, like we had something important to offer the world. I fondly recall one hot afternoon, just as lunch was coming to an end, I was standing by the gym doors trying to catch a breeze when Mr. Perry stopped to ask how my college applications were going. We chatted a bit, and as he walked away, he told me that no matter what I do in college, I should take as many math classes as I can because “the more math you can do, the more problems you can solve and there will always be work for someone like that.” I took his words to heart. Since I was the family nerd, my parents had expectations that I would become a doctor, a medical doctor, that is. My mother would often say to me that my piano playing would help keep my hands steady as a surgeon. But, as you can plainly see, that was not exactly how things turned out for me. By my second year at Loyola Marymount University, I decided to switch majors from (Pre-Med) Chemistry to Mathematics after taking Calculus I with the late, great Dr. Michael Cullen. My parents were none too pleased about the change, since they did not know the career possibilities connected with a math degree, apart from being a math teacher. The summer DRAFT 70 Chapter 10. Closed Formula for the Fibonacci Sequence (by Induction) following my decision to change my degree plan, I had the privilege of working on a research project with Dr. Herbert A. Medina. Back then, I had no idea what it meant to do research in mathematics when he recruited me. I thought all the interesting questions had been answered and that being a professor meant knowing all the answers. (Spoiler alert: that previous sentence is not true.) That summer of research was a major turning point in my life. It was the experience that helped me discover exactly how I would like to dedicate my time: doing some very cool math with some very cool people. I finished my undergraduate degree, received two national fellowships, and accepted a spot in the Pre-Ph.D. Program at UC Berkeley. I definitely encountered a number of setbacks over the years – we all hit bumps in the road, don’t we? While in graduate school, for instance, I constantly questioned whether I had what it took to get a doctoral degree in mathematics. Sadly, I did not receive encouragement from my parents either. I struggled in many of my classes and there was very little support outside of the few friendly faces among the graduate students. At the start of my third year of graduate school, my father passed away from an unexpected complication during surgery, and my family and I were devastated. So that fall, I decided to take a semester-long leave of absence to mourn this enormous loss to our family. During that time, I questioned whether I should return to finish what I started. There was enormous pressure from my mom to “just quit school, and work at a bank.” No one from the math department reached out to me during the time I was away. My confidence was shattered, but this nagging little thought kept creeping in: I should at least finish my masters degree to have something to show for all that time and effort. So, I returned to do just that. While gearing up for my final year, Dr. Medina reached out and asked me to serve as a TA for a summer research program in Puerto Rico that he and his colleague Dr. Ivelisse Rubio co-founded and directed. I had no idea if he knew what I was going through when he asked me, but by doing that, he pulled me from the brink. Being a part of that program was what helped me stay motivated throughout graduate school. It gave me the vision to create a similar program in the Pacific that would bring mathematical research opportunities to underrepresented students, particularly those who identify as Native Hawai‘ians, Native Pacific Islanders, or other Indigenous Peoples. I finished my masters degree at UC Berkeley and then went on to New Mexico State University, where I completed my doctoral degree. I was on a mission. I also struggled in my first years as an assistant professor at Sam Houston State University. In particular, I found it very difficult to keep my research going since, at the time, I did not have collaborators. Fortunately, my experience working in undergraduate research programs prepared me to work with students at both the undergraduate and graduate levels. Working on research with my students helped me stay active in scholarship and gave me the experience I needed to realize my dream of directing an undergraduate research program. After a series of rejections and failed attempts, I founded and co-directed the Pacific Undergraduate Research Experience in Mathematics (PURE Math), a five-year undergraduate mathematics summer research program housed at the University of Hawai‘i at Hilo. This program has been one of my proudest accomplishments. It was one of my greatest joys in life to work alongside our awesome students and faculty for those five unforgettable summers in paradise. Over the years, I found ways to build collaborative research groups with my colleagues at SHSU and beyond, and it all boils down to sharing ideas and questions with people you enjoy working with. The first time I did this, I was giving a talk in a session organized by the amazing Dr. Pamela E. Harris and the brilliant Dr. Shannon Talbott. I decided to go off-script and talk about a delightful, yet unfinished research project. I ended the talk by inviting anyone listening DRAFT 71 to reach out to me if they were interested in collaborating. As luck would have it, Drs. Harris and Talbott did just that, and in the years that followed, we got together and had the best time cranking out some super neat results on posets and order dimension. It still brings tears of joy to my eyes when I think about those days in the basement of the math department at West Point with these phenomenal women because it was the first time I truly felt like an honest-to-goodness mathematician, working on some very cool math with some very cool people. Since then, I spend much of my time finding ways to recreate this collaborative and joyful research experience with others, particularly with women and people from marginalized groups who are working their way through the notoriously leaky academic pipeline. DRAFT 72 Chapter 10. Closed Formula for the Fibonacci Sequence (by Induction) 10.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 10.1.1 Prior to Proof Start by reading the Introduction Section. 1. What questions do you have about the Fibonacci Sequence? 2. Why is F0=0 and F1=1 , then Fn:=Fn−1+Fn−2 enough information to describe the entire sequence? 3. What is meant by recursively defined and closed formula? 10.1.2 The Theorem Now read up to (and including) Theorem 10.2.2 4. How would you find the 100th term using the closed formula? 5. Approximately what numbers are φand ¯ φ? 6. Pick one of the lemmas. Can you argue that it is true? 10.1.3 The Proof Read the proof of the "base case." 7. (framework) What is meant by “strong induction”? 8. (framework) Why must we prove the base case? 9. (warrant) Explain what is going on in the equation line. Read the induction step. 10. (framework) Why do we begin by assuming the formula holds for 0 ≤n≤k? 11. (warrant) How is the induction step and recursive formula used to arrive at Fk+1=1 √5hφk−¯ φki+1 √5hφk−1−¯ φk−1i? 12. (transfer) Create the “similar argument” that ¯ φk+¯ φk−1=¯ φk+1. 10.1.4 After the Proof 13. Why did each of the lemmas need to be established before proving the theorem? 14. Can you summarize this proof’s argument in a couple of sentences? DRAFT 10.2 Closed Formula for the Fibonacci Sequence (by Induction) 73 10.2 Closed Formula for the Fibonacci Sequence (by Induction) 10.2.1 Introduction Easily the most popular of all mathematical sequences of natural numbers is the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . . The sequence, sometimes called “Nature’s Universal Rule” or the “Numbers of Life,” makes a fantastical appearance in nearly every branch of science, in nature, in many fields of mathematics, and also in some celebrated works of art. The pattern describing this sequence is fairly straightforward: the next number in the sequence is the sum of the two numbers preceding it. In other “words,” if we set F0=0 and F1=1 , then Fn:=Fn−1+Fn−2 . This way of generating a Fibonacci number is known as a recursive algorithm. The lovely thing about this algorithm is its simplicity. Just add the previous two numbers and you get the next entry in the sequence. But, what would you do if I asked you, “What is F100 ?” This is where recursive formulas have their limitations. It seems like one would have to compute all the previous 99 Fibonacci numbers to get to F100 . Wouldn’t it be much nicer to simply plug 100 into some formula? Is it even possible to find one? Perhaps another interesting and more difficult question may have popped in your mind at this time: “Does every recursively defined sequence have a closed formula?” It turns out that there is a closed formula for the Fibonacci sequence and it seems to come out of the sky. Here it is: Fn=1 √5" 1+√5 2!n − 1−√5 2!n#. Yet another question may have entered your mind at this time: where in the world did 1+√5 2 come from? In what follows, we will prove that this formula works in two distinct ways. First, we will use induction to show that this formula holds. Then, we will derive the formula using a combinatorial technique that involves power series. We will end this chapter finding yet another exquisite fact involving Nature’s Universal Rule. 10.2.2 Proof that the Closed Formula Works To make notation for the proof a bit easier, let’s set φ=1+√5 2 and its conjugate by ¯ φ=1−√5 2 . The lemma below contains some useful facts about φ and ¯ φ that we will use later. You can prove them directly from the definitions. Lemma 10.2.1 Let φ=1+√5 2and ¯ φ=1−√5 2. Then the following statements hold: 1. φ+¯ φ=1. Alternatively, φ=1−¯ φand ¯ φ=1−φ. 2. φ−1=−¯ φ. Alternatively, ¯ φ=−φ−1. 3. ¯ φ−1=−φ. Alternatively, φ=−¯ φ−1. Theorem 10.2.2 For n=0,1,2,3,... , the nth Fibonacci number Fn is determined by the following formula: Fn:=1 √5φn−¯ φn. DRAFT 80 Chapter 11. Closed Formula for the Fibonacci Sequence (Using Series) which is valid whenever |r|<1 . With this, we can derive the power series representation for functions like 1 1−x. In this case, we have a=1 and r=xin the Equation (11.6): ∞ ∑ n=0 xn=1 1−x. Note that this equality of functions holds whenever |x|<1 , a.k.a. the interval of convergence. We can use this to derive the power series representation for a multitude of rational functions! Here’s how: First, compute a partial fraction decomposition of the given rational function p(x) q(x) . For the sake of this work, let’s suppose that the rational function has a partial decomposition of the form: A α−x+B β−x. Next, compute the power series representation for each term. Consider the first term A α−x . Factor out α in the denominator and we get A α(1−x α) . And, just as before, using Equation (11.6), we set a=A αand r=x αto obtain the power series: A α−x= ∞ ∑ n=0 A αx αn. Use this same technique for the other terms and we get: A α−x+B β−x= ∞ ∑ n=0 A αx αn+ ∞ ∑ n=0 B βx βn .(11.7) 11.2.3 The Grand Finale Next we compute the partial fraction decomposition for our rational function F(x) = x 1−x−x2 . The denominator can be factored as −1+√5 2−x! 1+√5 2+x! . As you may recall, we set φ=1+√5 2 . So, we can rewrite the denominator as (−¯ φ−x)(φ+x) . Thus the partial fraction decomposition comes to solving the coefficients Aand B: x 1−x−x2=A −¯ φ−x+B φ+x. Equating the numerators, we get x=A(φ+x)−B(¯ φ+x) . This gives the following system of equations: A−B=1 φA−¯ φB=0 DRAFT 11.2 Closed Formula for the Fibonacci Sequence (Using Series) 81 Solving this system, we get A=−1 √5 ¯ φ and B=−1 √5φ . This produces the partial fraction decomposition: x 1−x−x2=−1 √5¯ φ −¯ φ−x+−1 √5φ φ+x = 1 √5¯ φ ¯ φ+x− 1 √5φ φ+x. Using Equation (11.7) yields the following power series representation for x 1−x−x2: F(x) = ∞ ∑ n=0 1 √5¯ φ ¯ φ−x ¯ φn − ∞ ∑ n=0 1 √5φ φ−x φn = ∞ ∑ n=0 1 √5−x ¯ φn − ∞ ∑ n=0 1 √5−x φn . Applying Lemma 10.2.1, we see that −x ¯ φ= (φx) and −x φ=¯ φx . Using this in the expressions above, we obtain F(x) = ∞ ∑ n=0 1 √5(φx)n− ∞ ∑ n=0 1 √5(¯ φx)n= ∞ ∑ n=0 1 √5(φn−¯ φn)xn. By equating the coefficients of these two power series, we finally see that F(n) = 1 √5(φn−¯ φn). DRAFT DRAFT 12. The Golden Ratio Author: Rebecca Garcia Click here for Dr. Rebecca Garcia’s story. 12.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 12.1.1 The Theorem Start by reading up to (and including) the theorem statement. 1. (meaning) In your own words, what does this theorem state? 2. What is a limit? 12.1.2 The Proof Read the proof. 3. (warrant) How did the proof arrive at the L, 1, and L−1in L=1+L−1? 4. (warrant) Why must the limit Lsatisfy the quadratic expression L2−L−1=0.? 5. (warrant) How do we know Fn+1 Fn >0? 6. Can you summarize this proof’s argument in a couple of sentences? DRAFT 84 Chapter 12. The Golden Ratio 12.2 The Golden Ratio The number φ=1+√5 2 may have already been familiar to you. Yes, this is the famous Golden Ratio! Two numbers Aand Bwith A>Bare in the golden ratio if A B=A+B A. The previous sections demonstrated that the Golden Ratio and the Fibonacci sequece are inextricably linked to one another. We end this chapter with yet another way in which the Golden Ratio relates to the Fibonacci sequence: Theorem 12.2.1 Let Fn denote the nth number in the Fibonacci sequence and let φ=1+√5 2 . Then, lim n→∞ Fn+1 Fn =φ. Proof. By definition of the Fibonacci sequence, Fn+1=Fn+Fn−1 . Dividing both sides of this inequality by Fn, we get the following identity: Fn+1 Fn =Fn+Fn−1 Fn (12.1) =1+Fn−1 Fn .(12.2) Let L=lim n→∞ Fn+1 Fn . Then by taking limits of both sides in Equation (12.2), we get L=1+L−1. Multiplying the above equation by L yields the quadratic equation L2=L+1. In other words, the limit Lmust satisfy the quadratic expression L2−L−1=0. The quadratic formula produces two possibilities: L=φ or L=¯ φ . Since Fn+1 Fn >0 , then L>0 . Since ¯ φ<0, then L=φ, as desired. ■ DRAFT Part II: Proofs with Topology, Real Analysis, and Some More Advanced Discrete Topics DRAFT DRAFT 13. The Cofinite Topology Author: Priyam Patel Click here for Dr. Priyam Patel’s story. 13.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 13.1.1 Prior to Proof Start by reading the definition of a topology along with the explanation of open sets after it. 1. What questions have you had as you were reading? 2. Explain each of the axioms in your own words. 3. Could axiom 2 be rephrased as an “for all” statement? 4. What does it mean for a set to be open? Read the remainder of the background which unpacks an example of a topology. Don’t worry about reading all the details of the argument. Instead, think about the example and see if you can make sense of how each axiom is met. 5. Explain the X={a,b,c}example and how it meets each axiom. 13.1.2 The Theorem Now read the theorem statement. 6. Consider the set of integers. Provide examples of subsets in Tf. 7. What are subgoals we need to prove in order to prove this theorem? 13.1.3 The Proof Read the proof, focusing on how the author broke this proof into sections. Don’t worry about reading DRAFT 88 Chapter 13. The Cofinite Topology every detail right now. I will give you 3 minutes to think about this. Add some annotations if it is helpful. 8. What is the purpose of each of the parts of the proof? Now read the first section of the proof. 9. Why do we need to establish that ∅is in Tf? Now read the second section of the proof. 10. Why are we selecting an be an arbitrary collection of sets in Tfin part 2? 11. SαUαWhat does αrepresent? 12. Consider the set of natural numbers and the following subsets. Subset 1: non-zero numbers, Subset 2: numbers greater than 10, Subset 3: even numbers and numbers greater than six. Describe SαUα. Use these sets to illustrate SαUαc=TαUc α. Now read the section of the proof with two cases. 13. Why in part 3, do we Tn i=1Uiwith an index i=1 to nwhile in part 2 we used α? 14. Why do we need case 1? 15. Why do case 1 and case 2 cover all possible cases? 16. Consider the formal definition of De Morgan’s Law below. Where is De Morgan’s law used in each of the two cases? Definition 13.1.1 — De Morgan’s Law. Given sets Aand B. Then the following hold: (A∩B)c=Ac∪Bc (A∪B)c=Ac∩Bc. 13.1.4 After the Proof 17. Now that we have read through each of the sections, can you summarize this proof’s argument in a couple of sentences? DRAFT 13.2 The Cofinite Topology 89 13.2 The Cofinite Topology Definition 13.2.1 Atopology on a set X is a collection T of subsets of X having the following properties: (1) ∅and Xare in T, (2) the union of any elements in Tis again in T, and (3) the intersection of a finite collection of elements of Tis again in T. A set Xfor which a topology Thas been specified is called a topological space. If X is a topological space with the topology T , we say that a subset U of X is an open set of X if U belongs to the collection T . In this way, a topological space is a set X together with a collection of subsets of X called open sets, such that ∅ and X are both open, and such that arbitrary unions and finite intersections of open sets are open. ■ Example 13.1 In the following three examples, consider the set X={a,b,c} consisting of three elements. In the figure below, the blue circles represent the following collection of subsets of X : T1={∅,{a},{b},{a,b,c}} . Though axioms (1) and (3) hold for T1 , axiom (2) fails. To see this, consider the two set {a} and {b} , which are in T1 . Then, {a}∪{b}={a,b} , but {a,b} is not in the collection T1. Therefore, T1is not a topology on X. In the figure below, the blue circles represent the following collection of subsets of X : T2= {∅,{b,c}} . Unfortunately, axiom (1) does not hold for T2 since X={a,b,c} is not in the collection T2. Therefore, T2is not a topology on X. In the figure below, the blue circles represent the following collection of subsets of X : T3= {∅,{a,b},{a,b,c}}. We claim that T3 defines a topology on the set X . We verify the three axioms for a topology above. First note that ∅ and X={a,b,c} are both in the collection T3 , which shows that axiom (1) is satisfied. DRAFT 96 Chapter 14. Infinite Increasing Sequence of Numbers 14.3 Infinite Increasing Sequence of Numbers 14.3.1 Introduction: Three Real Analysis Statements Real Analysis deals with results from calculus and the impact infinity has on mathematics. The 3 statements and their proofs presented in this and the next two chapters reflect that. We will state them first with non-technical language. Do these make sense? 1. An infinite “increasing” list of numbers that is bounded (stuff on the list can’t get too positive or negative) must get “arbitrarily close” to one number. Another way to say this is that an increasing infinite list that has a bound has to level off. 2. A “collapsing” infinite collection of closed intervals will have exactly one number that is common to all of them. 3. Any infinite list that has a lower bound (bottom) and an upper bound (ceiling) must have “crowding” around at least one number. We will make the ideas in quotations clearer and more “mathematical” but this is a good time to play around with these ideas before jumping into the technical jargon. It must be noted that playing around like this IS mathematics and crucial to understanding. What do we mean by an infinite list of numbers? A sequence is an infinite and ordered list of numbers. Here is an example: 1 2,1 3,1 4,1 5,1 6, ... Note two things: 1. Order Matters. If you change the order of any of them, it’s a different sequence. 2. The three dots. The ellipses mean that the list continues on forever. Notation wise, we can write a formula for the sequence above according to the following formula: an=1 n+1 Note that according to this formula a1=1 1+1=1 2 a2=1 2+1=1 3 a3=1 3+1=1 4 and so on. Also note that we like to start at n=1. Definition 14.3.1 — Decreasing sequence. This sequence happens to be decreasing. This means that the next term is less than the previous term. This means that an+1≤anfor every n. Similarly, We can define increasing. DRAFT 14.3 Infinite Increasing Sequence of Numbers 97 Definition 14.3.2 — Increasing sequence. A sequence bn is increasing if a term on the list is larger than its previous term. This means that bn+1≥bnfor every n. What happens to our sequence when ngets large? ■Example 14.1 For example, what happens when nequals 1 thousand? a1000 =1 1001 This is close to zero. As a matter of fact, the elements on the list get as close to zero as we like by going far enough down the ordered list. You want elements on the list closer than .00001 to zero? Go past 100000 on the list and the elements of the list are closer than .00001 to zero. This might convince us that the elements of angets as close to zero as we like by making nlarge enough. This is what we call convergence. ■ The sequence an converges to L if for any positive amount p , there is a number N such that after the Nth element of the sequence , all of the elements on the list are within p of L . Note that N depends on p. In general mathematical language this is said as follows: Definition 14.3.3 — Convergent sequence.. The sequence an converges to L if for every positive ε, there is a Nsuch that whenever n>None has |an−L|<ε Think about this for an=1 n+1. What should Nbe depending on ε? Before we start on our first statement we need one more statement, which is one of the most important statements about numbers. It is a rule about numbers which we accept. Fact 14.3.1 — Big Deal mathematical fact. Every set of real numbers that has a lower bound and an upper bound has a highest lower bound and a least upper bound. Such a set is called bounded. Saying this another way: If S is a set that is bounded, then it has a least upper bound α and a greatest lower bound β . This means three things: 1. For any element xin S,β≤x≤α 2. For any other zfor which z≤xfor every xin S, then z≤β. 3. For any other wfor which x≤wfor every xin S, then w≥α. ■ Example 14.2 Here is an example: the set (5,15) . This is the set of all the numbers between 5 and 15 not including 5 and 15. 25 is an upper bound for this set because 25 is higher than all the elements of the set. There are infinitely many upper bounds. Is there a smallest one? Yes, the smallest one is 15. This is because 15 is larger than all the elements of the set making it an upper bound but of all DRAFT 98 Chapter 14. Infinite Increasing Sequence of Numbers the upper bounds it is smallest. Similarly, 2 is a lower bound for the set because 2 is less than all the elements of the set. There are infinitely many other lower bounds. Is there a greatest lower bound? The answer is yes. The greatest lower bound is 5 because 5 is a lower bound and of all the lower bounds it is the largest one. ■ Every bounded set of real numbers has a greatest lower bound and at least upper bound. This is an axiom: an accepted fact in mathematics. Now we have everything to prove our statement. 14.3.2 The First Real Analysis Statement An infinite “increasing” list of numbers that has an upper bound (a ceiling) must get “arbitrarily close” to one number. It should be noted that a sequence is bounded if its values on the list are bounded as a set. Let’s restate statement 1 with mathematical jargon. Theorem 14.3.2 If there is an m,M such that m≤an≤M for every n and an is an increasing sequence, then anconverges. Draw a picture of a sequence of dots going high and higher but don’t go above a fixed line a with you having to keep moving to the right. Doesn’t the list have to “level off?” This is what we are going to prove. Proof. Let an be an increasing sequence and suppose there is some number M that is larger than all the values in the sequence (an upper bound). We will find a number that we think the numbers on the list will get arbitrarily close to by going far enough down the list. Let’s look at the values on the list. Let S be the values on the list as a set. Since an is bounded, so is S . Since S is bounded, it has a least upper bound. Let’s call it x . THIS is what we claim an converges to. Let’s see why. We argue by contradiction. Suppose an does not converge to x . We will show a contradiction occurs, thus forcing us to conclude that anmust converge to x. IF an does not converge to x . Then an always stays some amount away from x . That is, every element on the list must be some positive distance away from x . Let’s call the minimum distance d . (How do we know there is a minimum distance?) All of the elements must be away from x by at least dunits. But the list of elements on an are increasing. So they are going up. Can you see why that if all the elements of the list are at least d elements away from x and the elements are increasing, then all the elements have to be less than the number x−d? DRAFT 14.3 Infinite Increasing Sequence of Numbers 99 This is because x is already larger than all of them and they are moving up towards x . But they can’t go higher than x−dbecause they can’t be within dof x. So all the elements on the list are less than x−d . This means that x−d is an upper bound. We should note that x−d is less than x . This is a problem ( a contradiction). We were pretty clear that x was the least upper bound. So there can’t be anything less than it that is also a bound. And yet x−d is staring us in the face. This contradiction must mean we assumed something wrong. The only thing we assumed was that andoes not converge to x. So andoes indeed converge to x.■ DRAFT DRAFT 15. Infinite Collapsing Sequence of Closed Intervals Author: Aris Winger Click here for Dr. Aris Wingers’s story. 15.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 15.1.1 Prior to Proof Note: This chapter borrows ideas and results from Chapter 14. Feel free to reflect on the Reading Prompts from that chapter prior to engaging with the present ones! 15.1.2 The Theorem Please read the text to just before the line that says ‘Proof.’ 1. Draw a diagram that shows what it looks like for a sequence of closed intervals to be collapsing. 2. What does it mean to say that these are “closed intervals?” 3. Explain in your own words what it means for a sequence of closed intervals to be collapsing. 4. Explain why the example sequence [−1 n+2,1 n+1] satisfies all three of the conditions given in the theorem. 5. Explain why the sequence [0,1+1 n]does not satisfy the three conditions. 15.1.3 The Proof Now read the first two parts of the proof up through the line that begins ‘We can conclude. . . ’. 6. Why must the sequence xnbe increasing and the sequence ynbe decreasing? 7. What upper bound does the proof identify for the xnsequence? 8. Why is it important that the xnsequence is bounded above? Now read the rest of the proof. DRAFT 102 Chapter 15. Infinite Collapsing Sequence of Closed Intervals 9. Use a number line or inequalities to show the relationship between xn,yn,a, and b. 10. Why must abe in each of the collapsing intervals? 11. What part of the theorem does the last line of the proof justify? 12. How would you summarize the proof? DRAFT 15.2 Infinite Collapsing Sequence of Closed Intervals 103 15.2 Infinite Collapsing Sequence of Closed Intervals 15.2.1 Introduction Note: The previous chapter included a section called Introduction: Three Real Analysis Statements with many relevant definitions and ideas. This chapter uses both these definitions and the resulting theorem from Chapter 14 If you have not yet read that section or need a refresher, please do click here to go back and revisit. The second idea discussed in Section 14.3.1 is: A “collapsing” infinite collection of closed intervals will have exactly one number that is common to all of them. Here is a collapsing sequence of intervals: −1 3,1 3,−1 4,1 4,−1 5,1 5,−1 6,1 6, ... We can write these sets in general as An=−1 n+2,1 n+2 So we can think of this is a sequence of sets. The question is: Is there a number in every single An ? Yes, 0 is. Moreover, 0 is the only number in ALL of the An. We intend to prove this in general. Let An= [xn,yn]. What does collapsing mean? It means the following two conditions must hold: Definition 15.2.1 — Collapsing sequence of sets. The sequence An= [xn,yn] is collapsing if the following two conditions hold: 1. All of the elements of An+1are in An. We write this as An+1⊆An 2. The width of the intervals goes to zero: yn−xnconverges to 0. 15.2.2 The Second Real Analysis Statement Here is the theorem: Theorem 15.2.1 If the following conditions hold: 1. An= [xn,yn] 2. An+1⊆Anfor every n=1,2,3,... 3. yn−xnconverges to zero. then there is one and only one number common to Anfor every n. Proof. Since An+1⊆An then xn≤xn+1≤yn+1≤yn . This means that xn and yn are increasing and decreasing respectfully. Note that xn≤y1for all nand yn≥x1for all n. DRAFT 104 Chapter 15. Infinite Collapsing Sequence of Closed Intervals Thus xnis increasing and bounded above and ynis decreasing and bounded below. We now use the Statement 1 that we proved earlier. We can conclude that xnconverges to some a. We also know that ynconverges to some b. Since yn−xn converges to zero then b−a=0 and thus a=b . Thus xn and yn converge to the same number. This is the number that we think is in every An. Indeed, xn was increasing up to a and yn is decreasing down to a . Thus xn≤a≤yn which is exactly what it means for ato be in An. Why is it the only element in all the An ? If there was another, call it z . Then z would also have xn and ynconverge to it but that’s impossible since a sequence can only converge to one number. ■ DRAFT 16. Infinite Sequence of Numbers Crowding Around A Number Author: Aris Winger Click here for Dr. Aris Wingers’s story. 16.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 16.1.1 Prior to Proof Note: This chapter borrows ideas and results from Chapters 14 and 15. Feel free to reflect on the Reading Prompts from Chapter 14 and Reading Prompts from Chapter 15 prior to engaging with the present ones! 16.1.2 The Theorem Start by reading the to just before the line that begins ‘Proof’. 1. Explain in your own words what it means for a sequence to have a cluster point. 2. Explain why the sequence 1,2,3,4... does not have a cluster point. Why does this example not disprove the theorem? 16.1.3 The Proof Now read the first two segments of the proof, through the section beginning ‘If S is finite. . . ’. 3. Draw a diagram or give an example of a sequence where the set of elements is finite. 4. Explain why this satisfies the meaning of cluster point given in the text. Now read the next two segments up through the sentence ‘You might note that these sets are collapsing!’. 5. Draw a diagram to show how the intervals are being chosen. DRAFT 112 Chapter 17. Degrees of Connected Graphs 17.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 17.1.1 Prior to Proof Start by reading up to and including Example 17.1. 1. In the example graph G , name two incident edges, two adjacent vertices, and an edge and vertex that are incident. 2. For the example graph G, what edges would you remove to create a simple graph? Now read the rest of the definitions (up to and including the Note before the start of the next section). 4. How would you explain the definition of a maximal connected subgraph in your own words? 5. Create a graph that has three components. 17.1.2 The Theorem Now read the theorem statement (in the box). 6. If d1≤d2≤···≤dn, what can we say about the vi’s? 7. What is n−dn−1? 8. What does it mean for dk≥kfor every k≤n−dn−1? 9. Using this disconnected graph H , modify the graph so that the assumptions of the theorem hold. Is it still disconnected? a b c d H 10. What will we need to show to prove this theorem? 17.1.3 The Proof Finally, read through the proof. 11. What is being assumed in the proof? 12. Draw a simple connected graph on 5 vertices. Label the vertices according to the theorem and verify that “d1≤d2≤···≤dnand dk≥kfor every k≤n−dn−1". 13. What is vn? Why focus on vn? 14. Where is it used in the proof that Gis simple? 15. Why does the proof focus on two components ( G′ and G′′ )? Would the proof still work if there were more than two components? 16. How do we know G′has at least dn+1 vertices? Why at least? 17. Can you summarize this proof’s argument in a couple of sentences? DRAFT 17.2 Degrees of Connected Graphs 113 17.2 Degrees of Connected Graphs 17.2.1 Introduction to Graph Theory Definition 17.2.1 — Graph. Agraph G consists of two sets: a nonempty set V(G) of vertices and a set E(G) of edges, where each edge is associated with a set consisting of either one or two vertices called its endpoints. Definition 17.2.2 — Vertex properties. Two vertices u,v are adjacent if {u,v} is an edge. A vertex u and an edge e are incident if u is an endpoint of e . We also say that two edges are incident if they share an endpoint (vertex). A vertex is isolated if there are no edges incident to it. Definition 17.2.3 — Order of a graph. The order of a graph is the cardinality of vertices, denoted |V(G)|. The size of a graph is the cardinality of edges, denoted |E(G)|. Definition 17.2.4 — Simple graph. Aloop is an edge whose endpoints are equal. Parallel edges are edges having the same pair of endpoints. A simple graph is a graph that does not have any loops or parallel edges. Definition 17.2.5 — Degree of a graph. Let G be a graph and v be a vertex of G . The degree of v , denoted deg(v) , equals the number of edges that are incident on v , with an edge that is a loop counted twice. The maximum degree of a graph G is the largest vertex degree of G, denoted ∆(G). The minimum degree of a graph Gis the smallest vertex degree of G, denoted δ(G). ■Example 17.1 Consider the graph Gbelow. a b c d e G Graph Ghas vertex set V(G) = {a,b,c,d,e}. Graph Ghas edge set E(G) = {{a,b},{a,d},{c,d},{c,d},{b,c},{b}}. The order of Gis |V(G)|=5, and the size of Gis |E(F)|=6. Graph Ghas two parallel edges and one loop. The degrees of the vertices of G are: deg(a) = 2 , deg(b) = 4 , deg(c) = 3 , deg(d) = 3 , and deg(e) = 0 . The maximum degree of Gis ∆(G) = 4 and the minimum degree is δ(G) = 0. ■ Definition 17.2.6 — Subgraph. A graph H is said to be a subgraph of a graph G if, and only if, every vertex in H is also a vertex in G , every edge in H is also an edge in G , and every edge in H has the same endpoints as it has in G. Definition 17.2.7 — Walks and paths. Let G be a graph and u and v be vertices in G . A walk from u to v is a finite alternating sequence of adjacent vertices and edges of G . A path is a walk that does not contain a repeated edge or vertex. DRAFT 114 Chapter 17. Degrees of Connected Graphs Definition 17.2.8 — Connected and disconnected graphs. A graph G is connected if there is a path between every pair of vertices; otherwise G is disconnected. A maximal connected subgraph of G is a subgraph that is connected and not contained in any other connected subgraph of G. The components of Gare its maximal connected subgraphs. Note: In the above example, the graph G is disconnected since there is no path between vertex e and any of the other vertices in the graph. In fact, Ghas two components. 17.2.2 Degrees of Connected Graphs Theorem 17.2.1 Let G be a simple graph with vertex set V(G) = {v1,v2,...,vn} and let deg(vi) = di for all vertices vi , where i=1,2,...,n . If d1≤d2≤···≤dn and dk≥k for every k≤n−dn−1 , then Gis connected. Proof. Suppose by way of contradiction that G is disconnected and let G′ be the component of G that contains vn . Since deg(vn) = dn and d1≤d2≤···≤dn , then G′ must have at least dn+1 vertices in its vertex set. Let G′′ be another component of G such that G′′ has k vertices. Note G′ has at least dn+1 vertices, then we obtain that k≤n−dn−1 . Since dk≥k and there is some vertex v of G′′ such that deg(v) = dk . Thus, G′′ has at least dk+1 vertices, which implies that G′′ has at least k+1 vertices and contradicts the assumption that G′′ had k vertices. Therefore, G must be connected. ■ DRAFT 18. The Order of a Graph Author: Shanise Walker Click here for Dr. Shanice Walker’s story. 18.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 18.1.1 Prior to Proof Start by reading the definitions of distance and diameter, as well as Theorem 18.2.1. 1. What is a path in a graph? 2. What is the diameter of the example graph G? 18.1.2 The Theorem Now read Theorem 18.2.2. 3. What does it mean for G to have a diameter dand a maximum degree k? 4. In your own words, what is the theorem stating? 5. What will we need to show to prove this theorem? 6. How do we anticipate using Theorem 18.2.1 in the proof of Theorem 18.2.2? 18.1.3 The Proof Read the first five sentences of the proof - up to ‘Thus there are at most k(k−1) vertices that are distance 2 away from v.’ 7. Why do we multiply kand k−1 here? Why is this an upper bound? Next, read the next three sentences of the proof - up to ‘Hence, there are at most k(k−1)d−1 vertices that are distance d from v.’. DRAFT 116 Chapter 18. The Order of a Graph 8. Why do we have the exponent in the expression k(k−1)i−1 ? Why specifically do we use i−1 as the exponent? 9. The proof argues that there are at most k(k−1)d−1 vertices that are distance d from v . How do we know this estimate has counted all the vertices in the graph? Next, read the rest of the proof.. 10. This part of the proof begins with the statement that |V(G)|≤1+k+k(k−1)+ ···+k(k− 1)d−1. Why is this true? 11. What does each term in the summation count? Why do we have dmany terms in the sum? 12. (modular) How would you break up the proof into different sections? 13. Can you summarize this proof’s argument in a couple of sentences? DRAFT 18.2 The Order of a Graph 117 18.2 The Order of a Graph Note: The previous chapter included a section called Introduction to Graph Theory with many relevant definitions and ideas. If you have not yet read that section or need a refresher, please do click here to go back and revisit the Introduction to Graph Theory. Definition 18.2.1 — Distance and diameter. The distance between two vertices in a graph G is the number of edges in a shortest path. The diameter of G is the maximum distance between any pair of vertices in G. If the graph is disconnected, we say the diameter is infinite. Theorem 18.2.1 — Sum of a Geometric Sequence. For any real number r except 1 , and any integer n≥0, n ∑ i=0 ri=rn+1−1 r−1. Theorem 18.2.2 Let Gbe a graph with diameter dand maximum degree k. Prove |V(G)|≤1+((k−1)d−1)k k−2. Proof. Let G be a graph with diameter d and maximum degree k . Let v∈V(G) , then deg(v)≤∆(G) . There are at most k vertices that are distance 1 away from v . Each vertex that is distance 1 away from v is adjacent to at most k−1 vertices that are not v , and these vertices are distance 2 away from v . Thus, there are at most k(k−1) vertices that are distance 2 away from v . Hence, for any given distance i , there are at most k(k−1)i−1 vertices that are distance i from v . The maximum distance any vertex can be from v is d , and cannot be more than d since d is the diameter of G . Hence, there are at most k(k−1)d−1vertices that are distance dfrom v. Therefore, the order of Gis |V(G)|≤1+k+k(k−1)+ ···+k(k−1)d−1 =1+k(1+(k−1)+···+(k−1)d−1) =1+k d−1 ∑ i=0 (k−1)i(by Theorem 18.2.1) =1+k((k−1)d−1) k−2 ■ DRAFT DRAFT 19. Prime-itive Search: Sieve of Sundaram Author: Dwight Anderson Williams II Click here for Dwight Anderson Williams II’s story. 19.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 19.1.1 The Theorem Start by reading the section up to the statement of Definition 19.2.1. 1. Let n=5. Use the Sieve of Sundaram to find all the primes less than 12. 2. What is the upper bound of the odd primes that could be found with the Sieve of Sundaram if n=15? Now read through Question19.2.3. 3. The proof says that “characterizing all primes (not equal to 2) amounts to finding the natural numbers ksuch that 2k+1 is prime." Why is that the case? 4. Why is 2(0)+1 not prime? 19.1.2 The Proof Read through the algebraic section of the proof. 5. What is the seed of the prime number 13? 6. If i=0, then what is the seed of the prime if 2k+1= (2i+1)(2j+1)? 7. It is noted in the proof that 2k+1= (2i+1)(2j+1) is prime if i and j are not both non-zero. What if both iand jare zero? Now read the rest of the proof DRAFT 120 Chapter 19. Prime-itive Search: Sieve of Sundaram 8. The proof concludes by saying “if we eliminate from the set {1,2,3,...,n} any k=i+j+2i j , both i and j positive natural numbers, then the remaining values are the seeds for the odd primes less than 2n+2." How is this claim justified? 9. Explain in your own words how we have proven Theorem 3. DRAFT 19.2 Prime-itive Search 121 19.2 Prime-itive Search 19.2.1 Introduction Note: Chapter 3 included a section called Introduction to Primes with many relevant definitions and ideas. If you have not yet read that section or need a refresher, please do click here to go back and revisit the Introduction to Primes. 19.2.2 Sieve of Sundaram Finally, it would be nice if we could find some primes. Thankfully, some results are algorithmic in nature and provide a process to find all the primes less than or equal to some number: Theorem 19.2.1 — Sieve of Sundaram. 1 Start with a natural number n . Then the following will result in a list of the prime numbers less than 2n+2, except for 2. 1. First write down the first npositive natural numbers. Figure 19.1: Sieve of Sundaram Step 1 Figure 19.2: Sieve of Sundaram Step 2 2. Cross out all numbers that are equal to i+j+2i j, with iand jnatural numbers. Figure 19.3: Sieve of Sundaram Step 3 3. Multiply each number that remains by 2 and add 1 . The resulting numbers are all the odd primes less than 2n+2. DRAFT 128 Chapter 20. Shidoku Boards 20.2.2 Introducing Shidoku In 1979, Dell Magazines started publishing a puzzle that later in the 2000’s became a worldwide phenomenon, Sudoku. It consists of a 9×9 grid split into nine 3×3 squares. To complete the puzzle. one must complete a partially filled grid using the numbers 1 through 9 such that no digit is repeated in each row, column, and 3 ×3 subsquare as shown in Figure 20.1. Figure 20.1: A Sudoku puzzle on the left with its completion on the right. A question that might come to mind is: how many complete Sudoku boards are there? This question turns out to be difficult to answer but in 2005, Felgenhauer and Jarvis published a 7 page paper 1 showing that the total number of Sudoku boards is 6,670,903,752,021,072,936,960. How could one prove such a result? The proof consisted of a few clever combinatorial tricks to reduce the count and the help of a computer to count some specific types of boards. In this chapter, we will showcase some of the ideas of Felgenhauer and Jarvis to answer the following question. Question 20.2.2 How many complete Shidoku boards are there? Wait, what is a Shidoku? It is the 4×4 analogue of a Sudoku. It consists of a 4×4 grid split into four 2×2 squares. Similar to Sudoku, the goal is to fill the grid using the numbers 1, 2, 3, 4 such that no digit is repeated in each row, column, and 2 ×2 subsquare. Before we proceed, can you take 5 minutes to start thinking how might we approach this problem? Perhaps try to estimate the number of Shidoku boards? Is it in the tens, hundreds, thousands, millions? 20.2.3 Counting Shidoku Boards We will split the count in two big cases. We will first count all Shidoku boards such that the top left square is filled with the numbers 1,2 in the first row (in that order) and 3,4 in the second row (in that order) as shown in Figure 20.2. Then, we will consider all other boards. To simplify notation, we will denote each 1×1 square in the grid by bi,j where i is the row number and j is the column number. Since b1,1=1 and b1,2=2 then the remaining entries in row 1, that is, entries b1,3 and b1,4 must be 3 and 4 (in some order). Similarly, the remaining entries in column 1, that is, entries b3,1 and b4,1 must be 2 and 4 (in some order). Let’s pick one of the choices, say b1,3=3 , b1,4=4 , b3,1=2 , and b4,1=4 , as shown in the left Shidoku of Figure 20.2. Now, let’s count in how many ways can we finish off this board. DRAFT 20.2 Shidoku Boards 129 → Figure 20.2: On the right are the three ways to complete the Shidoku board on the left. To complete the second column, we must have one of two choices: b2,3=1 and b2,4=3 or b2,3=3 and b2,4=1 . Using the first choice, you can check we can complete the board in two different ways, both shown in Figure 20.2. Using the second choice leads to a unique way to complete the board, also shown in Figure 20.2. Thus we get 3 different Shidoku boards with the condition that b1,3=3 , b1,4=4, b3,1=2, and b4,1=4. This condition was chosen arbitrarily as we could have chosen any of four possibilities: •b1,3=3, b1,4=4, b3,1=2, and b4,1=4 (the choice we made) •b1,3=3, b1,4=4, b3,1=4, and b4,1=2 •b1,3=4, b1,4=3, b3,1=2, and b4,1=4 •b1,3=4, b1,4=3, b3,1=4, and b4,1=2. For each of these, the same argument we ran before works and leads to three solutions. Thus, we have 4 ·3=12 Shidoku boards in which the top left box is b1,1=1,b1,2=2,b2,1=3,b2,2=4. If you recall back to the first sentence, we said we will split the proof in two big cases. The first case is now completed. We must now count boards in which the top left box is not b1,1=1,b1,2= 2,b2,1=3,b2,2=4 . For this, we use a clever combinatorial trick. It’s called relabeling (or using symmetries via permutations). We will show that regardless of how we start the top left box (as long as no digit is repeated in the box), there will be 12 Shidoku boards with that top left box. We do so by creating a bijection between the boards that satisfy b1,1=1,b1,2=2,b2,1=3,b2,2=4 and boards that start with any other choice. Let S be the set of Shidoku boards that start b1,1=a,b1,2=b,b2,1=c,b2,2=d in the top left box, where a , b , c , and d denote the numbers 1,2,3 and 4 in any order. Let T be the set of Shidoku boards that start b1,1=1,b1,2=2,b2,1=3,b2,2=4 in the top left box. Consider the map φ:S→T that takes a Shidoku board B in S and returns the board obtained by relabeling the entries such that a becomes 1, b becomes 2 , c becomes 3, and d becomes 4 . For example, when a=2 , b=4 , c=3 , d=1 the map φwould satisfy φ 7−→ One should check that this relabeling preserves the property that no digit is repeated in each row, column, and subsquare. Similarly, we can define the map ψ:T→S that takes a Shidoku board in T DRAFT 130 NOTES and relabels the entries such that 1 becomes a , 2 becomes b , 3 becomes c and 4 becomes d . A quick verification shows that these two maps are inverses of each other, that is, their composition is the identity map. Thus, each map is a bijection and the sets S and T have the same number of elements. This implies that there are 12 Shidoku boards for each way to complete the top left box. There are 24 ways to complete the top left box (can you write them all?), so there are a total of 24 ·12 =288 Shidoku boards. Notes 1Bertram Felgenhauer and Frazer Jarvis. Enumerating possible sudoku grids. 07 2005. DRAFT 21. Dirichlet’s Approximation Theorem Author: Edna Jones Click here for Dr. Edna Jones’ story. 21.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 21.1.1 Prior to Proof Start by reading the first paragraph and the beginning of the second up to (and including) the "the better approximation of α". 1. What questions do you have about what you read? 2. Explain how you would interpret the author’s descriptions with rational approximations of a real number. (a) 31/10 is not a very good rational approximation of π. (b) 31/10 is the best rational approximation of πwith a denominator of 10. (c) If two rational numbers are the same distance from the real number α , then the rational number with the smaller denominator is considered the better approximation of α. 21.1.2 The Theorem Now read the rest of the first page, which includes the background information and the statement of Theorem 21.2.1, which is the statement to be proven, and Principle 21.2.2 (Pigeonhole principle). 3. Interpret in your own words what Theorem 21.2.1 says. 4. Interpret in your own words what Principle 21.2.2 (Pigeonhole principle) says. 5. Interpret in your own words the meanings of the symbols, ⌊x⌋and {x}. (a) Explain each of the notations when x=π, when x=2π, etc. (b) Explain how we could say {x}in the interval [0,1)for any real number x. DRAFT 132 Chapter 21. Dirichlet’s Approximation Theorem 6. What does a proof need to accomplish to prove Theorem 21.2.1? 21.1.3 The Proof Read the proof. 7. Summarize what the proof-text said so far. 8. Explain the proof-text when α=πand N=10. To be specific, (a) What are the 11 fractional parts mentioned in the first sentence of the proof of Dirichlet’s approximation theorem when α=π and N=10 ? (Round your answers to the nearest thousandth.) (b) Because N=10, we divide the interval [0,1)into 10 subintervals: 0,1 10,1 10,2 10,2 10,3 10,...,9 10,1. Are there a pair of integers k and ℓ such that 0≤k< ℓ ≤N such that {kπ} and {ℓπ} are in the same subinterval? How many of such pairs of integers you could find? (c) For the k and ℓ found in Problem 1b, examine if the following inequality holds true? How can you tell? |{ℓπ}−{kπ}|<1 10. (d) For the k and ℓ found in Problem 1b, let p=⌊ℓπ⌋−⌊kπ⌋ and q=ℓ−k . Examine if the following inequalities hold true? How can you tell? |qπ−p|<1 10 and  π−p q <1 10q. 9. Why are fractional parts used in the proof of Dirichlet’s approximation theorem? 10. How is the pigeonhole principle used in the proof of Dirichlet’s approximation theorem? 11. Let α be a real number. Suppose that k and ℓ such that 0≤k< ℓ ≤N and {kα} and {ℓα} are in the interval m−1 N,m N for some integer m such that 1≤m≤N . Why must 21.3 be true? 12. Using the definition of the fractional part of a real number, how can we say 21.3 implies 21.4? 13. Suppose that kand ℓare integers such that 0 ≤k< ℓ ≤N. How can you tell 1 ≤ℓ−k≤N? 14. Let α be a real number. How may someone try to measure the goodness of a rational approximation of α ? You might want to consider |qα−p| for a rational approximation p/q of α. DRAFT 21.2 Dirichlet’s Approximation Theorem 133 21.2 Dirichlet’s Approximation Theorem Sometimes (especially if there is not a calculator readily accessible) we like to approximate real numbers by fractions with small denominators. For example, we could approximate the irrational number π by 31/10 , but we will see that this rational approximation (that is, an approximation by a rational number or fraction) of πis not very good, because  π−31 10 >0.04 >1 10 ·10.(21.1) However, this is the best rational approximation of π that we can obtain with a denominator of 10 . (By “best” here, we mean that 31/10 is the closest fraction to πthat has a denominator of 10.) In general, if we allow larger and larger denominators for our rational approximations, we should be able to more closely approximate a given number. Therefore, when deciding how good a rational approximation is, we should consider the size of the denominator of the rational approximation. We should do this in such a way that if two rational numbers are the same distance from the real number α , then the rational number with the smaller denominator is considered the better approximation of α. One such theorem that tells us how good a rational approximation can be is Dirichlet’s approximation theorem. This theorem is named after Johann Peter Gustav Lejeune Dirichlet. Theorem 21.2.1 — Dirichlet’s Approximation Theorem. Let α be a real number. Suppose N is a positive integer. Then there exist integers pand qsuch that 1 ≤q≤Nand  α−p q <1 qN .(21.2) Before we give a proof of Dirichlet’s approximation theorem, we first introduce some terminology that will be helpful in our proof. For a real number x , let ⌊x⌋ denote the floor of x , which is the greatest integer less than or equal to x . The fractional part of a real number x is x−⌊x⌋ and is denoted by {x}. That is, {x}=x−⌊x⌋. Note that {x}is in the interval [0,1)for any real number x. In addition to using fractional parts of real numbers, we will use the pigeonhole principle to prove Dirichlet’s approximation theorem. Principle 21.2.2 — Pigeonhole principle. Suppose n is a positive integer. If n+1 pigeons are placed into npigeonholes, then at least one pigeonhole will contain two or more pigeons. We now give a proof of Dirichlet’s approximation theorem using the pigeonhole principle. Proof of Dirichlet’s approximation theorem. Consider the N+1 fractional parts {0α} , {1α} , {2α} , ..., {Nα} . These fractional parts are in the interval [0,1) . The interval [0,1) can be written as the union of N subintervals, each of the form j−1 N,j N where j is an integer and 1≤j≤N . That is, [0,1) = 0,1 N∪1 N,2 N∪···∪N−1 N,1. DRAFT 134 Chapter 21. Dirichlet’s Approximation Theorem Because there are N+1 fractional parts and N subintervals, the pigeonhole principle implies that there are integers k and ℓ such that 0≤k< ℓ ≤N and {kα} and {ℓα} are in the same subinterval, say m−1 N,m Nfor some integer msuch that 1 ≤m≤N. Therefore, |{ℓα}−{kα}|<1 N.(21.3) By using the definition of the fractional part of a real number, we find that |(ℓ−k)α−(⌊ℓα⌋−⌊kα⌋)|<1 N.(21.4) Let p=⌊ℓα⌋−⌊kα⌋and q=ℓ−k. Then (21.4) becomes |qα−p|<1 N.(21.5) Because k and ℓ are integers such that 0≤k< ℓ ≤N , we have 1≤q=ℓ−k≤N . By dividing (21.5) by q, we obtain  α−p q <1 qN . ■ Let’s revisit rational approximations of πwith denominators at most 10. Dirichlet’s approximation theorem says that there are integers pand qsuch that 1 ≤q≤10 and  π−p q <1 10q.(21.6) Because of (21.1) and the comment after (21.1), we cannot have q=10 in (21.6). However,  π−22 7 <0.001265 <1 10 ·7, so 22/7 is considered a relatively good approximation of π. The subject of rational approximations (also called Diophantine approximations) is one of the various subjects that drew me to number theory. I found questions about rational approximations intriguing. For example, why do we obtain a better rational approximation of π by having a denominator of 7 instead of a denominator of 10 ? The answer to this question involves the concept of continued fractions. Questions related to Dirichlet’s approximation theorem 1. In this problem, we step through the proof of Dirichlet’s approximation theorem with an example in which α=πand N=10. (a) What are the 11 fractional parts mentioned in the first sentence of the proof of Dirichlet’s approximation theorem when α=π and N=10 ? (Round your answers to the nearest thousandth.) DRAFT 21.2 Dirichlet’s Approximation Theorem 135 (b) Because N=10, we divide the interval [0,1)into 10 subintervals: 0,1 10,1 10,2 10,2 10,3 10,...,9 10,1. Find integers k and ℓ such that 0≤k< ℓ ≤N such that {kπ} and {ℓπ} are in the same subinterval. (c) For the kand ℓfound in Problem 1b, show that |{ℓπ}−{kπ}|<1 10. (d) For the kand ℓfound in Problem 1b, let p=⌊ℓπ⌋−⌊kπ⌋and q=ℓ−k. Show that |qπ−p|<1 10 and  π−p q <1 10q. 2. Why are fractional parts used in the proof of Dirichlet’s approximation theorem? 3. How is the pigeonhole principle used in the proof of Dirichlet’s approximation theorem? 4. Let α be a real number. Suppose that k and ℓ such that 0≤k< ℓ ≤N and {kα} and {ℓα} are in the interval m−1 N,m N for some integer m such that 1≤m≤N . Why must (21.3) be true? 5. Using the definition of the fractional part of a real number, show that (21.3) implies (21.4). 6. Suppose that kand ℓare integers such that 0 ≤k< ℓ ≤N. Prove that 1 ≤ℓ−k≤N. 7. Let α be a real number. How may someone try to measure the goodness of a rational approximation of α ? You might want to consider |qα−p| for a rational approximation p/q of α. 8. For α=√2 and N=5, find all integers pand qthat satisfy (21.2) with 1 ≤q≤N. DRAFT DRAFT 22. Fields and Cryptography Author: Kate Melhuish Click here for Dr. Kate Melhuish’s story. 22.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 22.1.1 Prior to Proof Start by reading the first page ending with the sixth property of a field. 1. What is cryptography as described in the text? 2. Why does the text claim that encoding a word by shifting all the letters the same amount is not a fully safe way to encrypt message? 3. What questions do you have about the definition of a field? 4. What are some examples of fields that you know? [Interviewer: maybe point out why integers or matrices do not work if they suggest them. Rational numbers or reals are good examples.] Now read the next paragraph and the lemma, stopping before the theorem statement. 5. Do you have any questions about this part of the text? 6. Why might it be surprising that there are fields that have only finitely many elements? 22.1.2 The Theorem Now read the statement of the main Theorem. 7. If we let p=7 , what is the set F , and what are the values of 4+76 and 4∗76 ?[Interviewer: if they get these wrong, work through them together so they see how the remainder bit works. It may also help to look at 4+72and 4+73] 8. What does the proof need to do to prove this theorem? 9. Do you have any other questions about what the theorem says? DRAFT 144 Chapter 23. That Futurama Theorem 23.2.2 The Theorem Now read the next paragraph and the Theorem statement. 6. Explain what I means in the symmetry group. Why is this called the identity function? 7. Explain what the theorem says in terms of the Futurama episode. 8. What questions do you have before we start reading the proof? 23.2.3 The Proof Read the first paragraph. 9. What do the Cirepresent? It may be helpful to refer back at the example permutation above. 10. What do the kirepresent and why do they sum up to n? Read the next paragraph ending with the sentence that begins "we were able to rearrange. 11. Figure out what the σ1permutation would look like if C1= (356). 12. Why are all of the transpositions in σidistinct and not already in the permutation P? 13. Explain why C1σ1simplifies to (xy). 14. When are you allowed to reorder the composition of two permutations? Why does this apply to the composition in the proof? Read the final paragraph, ending with the box on the right. 15. Explain why there are two cases and why we can find the permutation we need in either case. 16. What do the two cases mean in terms of the Futurama characters all getting their brains back in their bodies? 17. Why was it important to represent the original permutation as a composition of disjoint cycles? DRAFT 23.3 That Futurama Theorem 145 23.3 That Futurama Theorem This proof comes from an episode of “Futurama.” In classic tv shenanigans, one of the characters (Professor Farnswarth) created a mind swap machine, but there was a catch! This machine could only swap minds between a particular pairing of bodies once. So if Bender (our friendly robot) swapped minds with the professor, they cannot swap back because Bender and the Professor have already swapped once. A series of brain swaps unfolds, and now characters’ brains are all in the wrong bodies. The natural question is, can we get everybody’s brain back in the right body given that we cannot directly swap brains between any two bodies that have already been paired. This is now an interesting mathematical problem that was solved via cartoon Globetrotters arriving at a new theorem. Let’s begin by introducing some symbols and definitions. So first, let’s think about what is going on here. We have a set of people: { Professor, Fry, Leela, Amy, Bender, Bucket, Zoidberg, Janitor }. Then through some working of the mind swaps, we have rearranged everyone’s brains and bodies. So we can think of this as a special kind of function, a permutation. Definition 23.3.1 — Permutation. A permutation is a bijective function that maps from a set of elements to the same set of elements. We can think about the set of switches as such functions and we combine them using function composition. Let’s consider the following switches: (Bucket Zoidberg)(Bucket Janitor)(Zoidberg Janitor)(Amy Fry)(Leela Fry)(Professor Bender) Pro tip: Don’t forget that function composition goes from right to left. Also, notice that you cannot always reorder these switches and end up with the same result. Let’s see where everyone’s brain ended up after the end of these swaps: Professor →Bender Bender →Professor Amy →Fry Leela →Fry →Amy Fry →Leela Zoidberg →Janitor →Bucket →Zoidberg Janitor →Zoidberg→Bucket Bucket →Janitor A single switch, we can refer to as a transposition . However, that is not the only kind of permutation available. We can write this overall permutation in a particular, nice way called disjoint cycles: (Professor Bender)(Amy Fry Leela)(Zoidberg)(Janitor Bucket) That is, overall, the professor goes to Bender and Bender goes to the Professor. And Amy goes to Fry, Fry goes to Leela, and Leela goes to Amy. Zoidberg has his brain in his own body. And Janitor and Bucket have switched brains. This gives us a pretty useful fact: Lemma 23.3.1 Any permutation can be written as disjoint cycles. Since disjoint cycles do not contain any common elements, the cycles can be written in any order. Of course, writing names is cumbersome. Let’s just pretend everyone is named after a number. We can consider the set {1,2,3,...,n} where each number represents a person. The above example could be encoded as (1 2)(1 3)(2 3)(4 5)(6 5)(7 8) by relabelling each of the eight characters as numbers. DRAFT 146 Chapter 23. That Futurama Theorem Rewriting: (1 2)(1 3)(2 3)(4 5)(6 5)(7 8) = (7 8)(4 5 6)(2)(3 1). The set of permutation functions on {1,2,3,...,n} with the operation function composition is a structure called a symmetry group Sn .This symmetry group will have some nice properties like the associative property, inverses, and an identity element. The identity in this case would be the permutation function that takes every element to itself. We can call this I . We are now ready to state the major theorem. The Globetrotters conjectured only two more people would be needed to get every brain in the right body. Theorem 23.3.2 — Keeler’s Theorem. Any permutation can be returned to the identity permutation, I, via the addition of one or two more elements (people) with no repeating transpositions. Proof. Let P be a permutation function on a set of n elements. Call these elements {1,2,...,n} . By the lemma, Pcan be represented as a series of disjoint cycles: P=C1C2...Cm. Let ki correspond to the length of each disjoint cycle Ci . Notice, that the sum of k′ is is equal to n. Let’s introduce two new elements: xand y. Suppose C1= (a1a2...ak1). Then introduce a series of k+2 transpositions: σ1= (xa1)(xa2)...(xak−1)(yak)(xak)(ya1). Note that all the transpositions in σ could not have been part of the original P set of transpositions because they all include an x or y , and these are the new elements. Also note that they are all different transpositions by construction. Now σ1C1simplifies to (xy). We can build such σifor each Cithat simplify as intended. Define σ=σ1σ2...σm.Therefore, Pσ=C1C2...Cmσ1σ2...σm =C1σ1C2σ2...Cm = (xy)m. We were able to rearrange the order because any σiis disjoint from Cjwhenever i=j. We consider two cases. If m is even, then Pσ=I and we are done since each identical transposition undoes each other. If m is odd, Pσ= (xy). Then Pσ(xy) = I . Since (xy) was not one of the original swaps, adding this transposition is valid, and we have found a series of swaps σ or σ(xy) that will undo all the swaps, never pairing the same people twice. ■ We can ask more things such as count how many swaps that happened or try and find a solution that involves less moves. Check out Evans, R., Huang, L., & Nguyen, T. (2014). Keeler’s theorem and products of distinct transpositions. The American Mathematical Monthly, 121(2), 136-144 for a version of this proof and more exploration. And of course, find a streaming service and watch the 10th episode of the sixth season of Futurama called “The Prisoner of Benda.” DRAFT 23.3 That Futurama Theorem 147 Figure 23.1: I am pretty sure we can get away with this via fair use educational purpose. DRAFT DRAFT Part III: Proofs with More Challenging, yet Accessible Topics DRAFT DRAFT 24. Recursive Formula for Counting Parking Functions Author: Pamela Harris Click here for Dr. Pamela Harris’ story. 24.1 Reading Prompts The following prompts are meant to be asked after reading each indicated section. The teal questions are the more important ones to ask, while the others are to be asked as helpful or if time permits. 24.1.1 Prior to Proof Start by reading the introduction section. 1. Explain the difference between {1,2,3,4,5} and (1,2,3,4,5). 2. Confirm that there are three parking functions of length 2. 3. Give one example and one non-example of a parking function of length 4. 4. In this context, why might 0 not be included in N? 24.1.2 The Theorem Now read up to (and including) Proposition 24.2.1 5. What does n−1 i−1mean? 6. What does the term PFi−1represent? What does the term |PFi−1|represent? 24.1.3 The Proof Read to the end of the paragraph ending right before the word "Observe.". 7. What does the variable irepresent in the proof? 8. Does the set S relate to the cars’ order in which they park or where the car parks on the street? 9. What does the term |PFn−i|count? 10. Summarize what the proof has said so far. DRAFT 152 Chapter 24. Recursive Formula for Counting Parking Functions Read the next two paragraphs beginning with ‘Observe that’ and ending just before the word "Assembling." 11. Why are there i-many preferences for car cn? 12. Summarize this section of the proof in your own words. Now read the last portion of the proof. 13. Why does the proof multiply the four terms in the summation? 14. Why do we sum the formula for all of the values of ifrom 1 to n? 24.1.4 After Reading the Proof Read over the entire proof again. 15. What does it mean that this formula is recursive? How does the proof use this to count the number of parking functions of length n? 16. How would you organize the proof into sections? What goal does each section accomplish in proving the theorem? DRAFT 24.2 Recursive Formula for Counting Parking Functions 153 24.2 Recursive Formula for Counting Parking Functions 24.2.1 Introduction to parking functions I want to start off by acknowledging that many people have taught me so much about parking functions. These include Dr. Ayo Adeniran as we met and collaborated on a parking function related project at the Graduate Research Workshop in Combinatorics; Dr. Alejandro Morales who taught me about parking functions as the related to volumes of certain polytopes; Alyson Baumgardner who generalized parking functions and gave me and students at the Mathematical Sciences Research Institute’s Undergraduate Program in 2019 the problems she created 1 . These works have fueled much research by numerous undergraduates and includes the work of Kimberly Hadaway, who is now a graduate student at Iowa State University, and whose work I present below as it appeared in part in 23. Let’s get to it. Let n∈N:={1,2,3,...} and consider a parking lot consisting of n consecutive parking spots along a one-way street. Suppose n cars want to park one at a time in the parking lot and each car has a preferred parking spot. Each car coming into the lot initially tries to park in its preferred spot. However, if a car’s preferred spot is already occupied, then it will park in the next available spot. Since the parking lot is along a one-way street, it is not guaranteed that every car will be able to park before driving past the parking lot. This dilemma leads to the idea of a parking function. c1 c2 cn ··· −→ 1 2 3 ... n Figure 24.1: Parking function illustration. Let us make this definition precise. Definition 24.2.1 — Parking Function. For n∈N={1,2,3,...} , let [n]:={1,...,n} . Formally, suppose the parking spots are labeled 1,2,...,n , in order, along the one-way street and the cars are labeled according to the order in which they try to park. In other words, for each i∈[n] , car ci is the ith car to try to park and prefers spot ai∈[n] . Note that more than one car can have the same preference. This is illustrated 4 in Figure 24.1. To park, cars first drive to their preferred spot and park in it if it is available. If their preferred spot is occupied then they drive forward and park in the next available spot. If all n cars can park in the parking lot under these conditions, then the preference list (a1,a2,...,an)is called a parking function (of length n). For example, (1,2,4,2,2) is a parking function 5 , but (1,2,2,5,5) is not 6 . Naturally, the first question that arises is: “For any n∈N , how many parking functions are there?” We let PFn denote the set of all parking functions of length n and we let |PFn| denote the cardinality of the set. We let PF0={()} , where “()” is often referred to as a 0-tuple. 24.2.2 Counting parking functions recursively In what follows, we prove a recursive formula for the number of parking functions. Proposition 24.2.1 The number of parking functions of length nfollows the recursive formula |PFn|= n ∑ i=1 in−1 i−1|PFi−1|·|PFn−i|.(24.1)