Why did they prove this amazing theorem in 200 different ways? Quadratic Reciprocity MASTERCLASS

Video Statistics and Information

Video
Captions Word Cloud
Reddit Comments

This video is one hour long!!! Really great stuff, but who here has got what it takes?

👍︎︎ 13 👤︎︎ u/cfoefs 📅︎︎ Mar 14 2020 🗫︎ replies

wow is the mathologer drama gone?

👍︎︎ 6 👤︎︎ u/unsurestill 📅︎︎ Mar 15 2020 🗫︎ replies

Great video - some of it flew over my head, but that's probably because this is a really complicated topic and it can be difficult to explain such high-level concepts to us mere mortals.

👍︎︎ 3 👤︎︎ u/theyoungbard 📅︎︎ Mar 15 2020 🗫︎ replies

My current research involves Young Tableaux (ways of putting positive integers in boxes arranged in rows according to the terms of a partition, where a partition is a sequence of weakly decreasing positive integers). For example if your partition is (5,3,2) (in this case we say this is a partition of 5+3+2=10) then your diagram is

x x
x x x

where an x means that entry of the table is not part of the diagram. We can generalise one of the results from the Mathologer video as follows. As in the Mathologer video you can fill the table along rows or along columns like

1 2 3 4 5
6 7 8 x x
9 10 x x x

and

1 4 7 9 10
2 5 8 x x
3 6 x x x

which as in the video defines a permutation of the integers 1 through 10. In our case, explicitly, the permutation is

1 2 3 4 5 6 7 8 9 10
1 4 7 9 10 2 5 8 3 6

Then we can ask if we have an explicit formula for the sign of this permutation. I asked myself this exact question last month and ended up writing up some notes on the solution. My solution includes the Mathologer result as the special case where your partition consists of q entries each of which is p (where p,q are odd primes). In fact, you'll notice that the argument holds so long as p,q are any odd numbers (the primeness has no impact on the result). Here is a link to my notes if anyone is interested.

https://www.dropbox.com/s/gjktfrh24mdhuow/SignofPartition.pdf?dl=0

Disclaimer: these notes were not written with the intention of sharing publicly, so the style is quite informal. They have also not been checked by anyone so could contain a mistake (although the result works in all examples I have checked).

👍︎︎ 1 👤︎︎ u/AdamPeterHiggins 📅︎︎ Mar 16 2020 🗫︎ replies
Captions
Today I'd like to talk about one of, ... some say the most amazing formula in the whole of mathematics: the law of quadratic reciprocity. That formula over there. Which proves that mathematicians are crazy, right? I can tell what you're thinking. P over Q times Q over P equals some power of -1. So the fractions cancel out, making the left side equal to 1. But what if, say, P and Q are both 3, then the right side simplifies to ... what? okay okay okay okay -1. 1 is equal to - 1. Does this mean that the most amazing formula is plain wrong. Okay so you guessed it, mathematicians may be crazy but we're not that crazy. So whatever is going on, those aren't everyday fractions on the left side. I leave it as a mystery for now but of course all will be explained. First I want to get you really curious with a bit of history and some amazing facts. Then, once you're truly hooked and there's no turning back, we'll go together on a crazy journey. Trust me this Mathologer is an extra wild one. The law of quadratic reciprocity was discovered by mathematical hero Adrien-Marie Legendre and the superhero Leonhard Euler. They came upon it while pondering questions like Fermat's two-square theorem that great theorem which I talked about in my last video and with which so many of you also seem to have fallen in love. And who was the first to prove the theorem? The answer, of course as is so often the case was... NOT Euler!! Tricked you, Hard to believe isn't it, but we finally stumbled upon a theorem that vanquished the invincible Leonhard Euler. So who was the first to actually succeed in proving the law of quadratic reciprocity? It was none other then that other mathematical superhero Carl Friedrich Gauss. It's like a marvel movie, isn't it? If one superhero is beaten down, another comes to the rescue. Now throughout his life Gauss proved the law in eight different ways, amazing isn't it. Clearly, Gauss believed that the law of quadratic reciprocity is incredibly important. In fact, he called it the fundamental theorem of higher arithmetic or the golden theorem. And Gauss was not alone in his respect for this theorem. There are now over 200 published proofs of the law. Lots of them by other mathematical big hitters: Eisenstein, Kummer, Cauchy, Jacobi, Liouville, Lebesque. 200 is more proofs than just about any other theorem in math(s) apart from maybe Pythagoras theorem. So seemingly an incredibly important theorem. But then how come about 99.99999% of humanity will never have even heard of quadratic reciprocity. Well let's find out. My first mission today is to motivate and to explain quadratic reciprocity which will already induct you into a very select group. But my ultimate and completely insane mission in today's video is to take one of those crazily complicated proofs of quadratic reciprocity and to Mathologerise it to death, to get it within reach of Youtubing math(s) fans. Luckily I found a great starting point for this mission, a blog post by mathematician Matt Baker. Matt takes the 1830 proof by the Russian mathematician Egor Ivanovich Zolotarev and interprets solitaires proof in terms of permutations and dealing a deck of cards. Really great stuff to look forward to. Well I've also put a link to Matt's blog post in the descriptions for all you mathematicians. Okay, I first need to take you on a journey back to some school math(s). No, wait, come back. I promise it will be fun. I'm going to cast some familiar school mathematics in a new light. You all know what a ring is? No not a Lord of the Rings ring or a wedding ring. You're safe, I'm not about to propose :) A math(s) ring is a world of number like objects. So these objects can be added, subtracted and multiplied, maybe in some weird way, but they still obey the same simple algebraic rules that we've all internalized in school. A plus B = B plus A, etc. Not surprisingly the integers are a ring and so are the rational numbers and the real numbers and the complex numbers. Are there other rings? Well, as I hinted you already know some other rings from school. They were just never identified as such. There are actually infinitely many of these rings hiding inside the integers. There's one of these rings corresponding to each integer greater than one. Ok, let's start by having a close look at the ring corresponding to the number 5. In this video I'll call this ring Z/5 which is its official name. This cute mini ring has only 5 numbers: 0, 1, 2, 3 & 4. These numbers are the possible remainders when you divide integers by 5. To add and multiply these remainder numbers in Z/5 you add and multiply them as usual and then calculate the remainder on division by 5. Here are a couple of examples of how arithmetic works in our mini ring. Let's add 3 and 4 in our mini ring. So we add 3 and 4 as usual giving 7. Okay, now the sum in our mini ring is just the remainder when we divide 7 by 5 and of course this remainder is 2, right? 3 times 3? Well in Kansas of course this equals 9. But now in this particular corner of the magical land of Oz the product is the remainder after dividing by 5 which gives us 4, of course. Pretty easy, right, even if you've never heard of modular arithmetic which is the official name of what we're doing here, I'm sure you could all now fill out the addition and multiplication tables for our mini ring. There. And the same easy process works for any integer greater than 1. Here are the tables for the ring Z/4. Here's Z/3 and here's Z/2. So one ring for every integer greater than 1. Now each of these rings contains only finitely many numbers and the arithmetic of these numbers is a little warped. Nonetheless, as I already indicated, the addition, subtraction and multiplication in these rings works very much as usual: A plus B equals B plus A, you can expand brackets as usual, and so forth. So if you haven't seen these rings before, here's a small but very useful challenge for you. Take one of these rings, say Z/5 and prove that the two basic laws over there still hold true in that ring. Can you do it? Now it also turns out that if our mini ring is based on a prime number, and it has to be prime, no other number will work, then our mini ring is super nice. In a prime mini ring we can do addition, subtraction multiplication and ALSO division as usual. That is, the inverse of multiplication also makes sense in a prime mini ring. These special prime mini rings are known as fields and, yes, there are more familiar fields as well. The world of rational numbers is a field and so are the real numbers and the complex numbers. And then things get really interesting because a lot of the math(s) that builds on everybody's favourite field the real numbers have counterparts for these finite fields and rings: plane and spatial geometry, vector spaces and, believe it or not, even to some extent calculus and things like surfaces. In fact, there are whole branches of mathematics that deal with finite geometry. I used to be really into finite geometry. Actually my first book was about visualizing finite geometries. I'll say a lot more about this in future videos. Now, just quickly here are pictures that captures some of the abstract beauty of four geometries constructed with this mini field Z/2 whose tables you can see over there. There are just two numbers in this field and yet it gives birth to all this complex and beautiful stuff. There's one guy, another one, it's called the doily that's a hexagon believe it or not, and that's the smallest perfect universe. anyway the first thing I want to stress, to help motivate what's to come is that these little relatives of the real numbers are super beautiful and super important in higher mathematics. These are definitely worlds that we want to know about and one of the first things a mathematician will ask about these little worlds is how solving equation works in those worlds. Equations are how we ask and answer mathematical questions, right? And now Gauss's golden theorem appears. It turns out that quadratic reciprocity leads to a very unexpected, very simple and very beautiful connection between the solutions of quadratic equations in completely different mini fields. Crazy stuff but also very important stuff for understanding these worlds. That was a little side trip to peek at the very surprising geometry of finite rings. But let's get back on the road to the main attraction. We'll begin by looking at the algebra of these worlds it turns out that finite rings are incredibly useful for investigating the integers and in particular the prime numbers. Is that surprising? Here's an easy example which may also be very familiar. What happens if you divide an integer by 2. Yep you just get a remainder of 0 or 1, depending upon whether the number is even or odd. But this means that the Z/2 tables capture the algebra of even and odd numbers There, replace all the zeros by even and all the ones by odd, and voila... Those are all the familiar rules about adding and multiplying odd and even numbers. For example, an even number plus an odd number is odd. Odd times odd equals odd and so on. As you probably know this capturing of even an odd is incredibly useful and since splitting up the integers into two classes according to division by two is so useful, it would hardly be surprising if splitting according division by other integers also led to important insights, right? And that is indeed the case. Let's look at a few interesting quadratic insights,d a couple of roadside attractions along the way to quadratic reciprocity. Quadratic suggests squares, so let's have a look at squares in our mini rings and see what they can tell us about the integers. That means we're looking at multiplication and in particular at the diagonal of the multiplication table. So start with Z/2. And we have, even times even is even and odd times odd is odd, not much there. It just tells us that squares of integers can be either even odd. So let's go on. What does the table for Z/3 tell us. Now the possible remainders of integers are 0, 1 & 2 but now we see something interesting. The remainder of an integer square can only be 0 or 1. 2 is impossible. In other words, none of the integers of the form 3K+2 can possibly be the square of an integer. So 5, 8 and 11 cannot be integer squares which will hardly shock you but it keeps going. What about 1 lots of zeros and another 1. Now not many numbers are squares and so we'd probably guess that monster isn't a square. But can we be sure? Yes, can you see at a glance why? Cut, hmm? Did you know this. On to the tables for Z/4. Again very interesting isn't it? We can get similar but at the same time very different conclusions. When we divide by 4, we have 4 possible remainders. However, 0 & 1 are the only possible remainders of integer squares. 2 & 3 are not possible. Let's use that to go back and look at a fact that I mentioned in my last video. I briefly noted that such a sum (x^2+y^2) can never be of the form 4K+3, in other words cannot have a remainder of 3 after division by 4. So none of these numbers down there 3, 7, 11, 15, and so on, can be written as the sum of two integer squares. And the table tells us why this is so. Since the only remainders of squares are 0 & 1 the possible remainders of a sum of two squares are 0 plus 0 equals 0, 0 plus 1 equals 1, and 1 plus 1 equals 2. So definitely no 3. Cool, hmm? Let's have a look at a few more square facts hidden in the table for Z/7. Again we're focused on the diagonal and once again only some of the available remainders are actually possible for integers squares. But even more is true. Of course 0 squared equals 0 and so 0 will always be a square in any of the rings. But ignore the 0. Notice that every nonzero number on the diagonal occurs exactly twice. Coincidence? No. It's not hard to prove that the same doubling up occurs in the mini field associated with any odd prime. And what about the non-squares? Well because every square pops up exactly twice, exactly half of the non-zero numbers must be squares and the other half must be non-squares. Does this feel a little familiar? The situation is very much like that for the real numbers which are also split into two equal parts, the squares and the non squares, the positive and a negative numbers. And just like with the real numbers, in Z/7 a square times the square is a square, that one's easy. But also a non-square times a non-square is always a square and the square times a non-square is a non-square. Try multiplying some of those squares and non-squares to check for yourself that this really works In Z/7. And the same is true in any of our mini fields associated with an odd prime. So is everything that we are used to from the real numbers also true in these mini fields? Well, no it really could't be could it? For example, for the real numbers the negative of a square is a negative number so a non-square. How about for our mini fields? Well this also turns out to be true for Z/7 for example. In Z/7 the negative of 1 is 6, right, because 1 plus 6 is 0, and 1 is a square number and it's negative 6 is a non square. However, in other mini fields the negatives of squares can be squares themselves. For example, and a very easy challenge for you, check that the negatives of squares in Z/5 are also squares, weird. And now, after that very long introduction, we are finally ready to launch into quadratic reciprocity. First, I have to explain to you what Legendre symbols are. That's the official name of those weird fractionally looking things on the left. Here the A on top can be any integer whatsoever. On the other hand, the P at the bottom must be a prime number. Then the Legendre symbol will equal to 0, 1 or - 1 according to some squarish rules that I will now explain. First the 0. The Legendre symbol equals 0 if the integer A leaves a remainder of 0 after division by P. In other words, the Legendre symbol is 0 if P divides A , that's like the 0 case when we were looking at squares in Z/7. And what about the plus or minus 1? They correspond to the squares and non-squares in the mini field Z/p. In other words, the Legendre symbol summarizes the "quadraticness" of the integer A with respect to the prime number P. Here a few examples. Here A is 70 and the prime P is 7 and since 70 is divisible by 7 that results in remainder 0 and so the Legendre symbol is equal to 0. Now for integers that are not multiples of 7 we need to know the squares in non squares in Z/7 but remember we read those off from the multiplication table earlier, right? Here they are. So what happens for example if we replace 70 by 75. Then we'll get a remainder of 5 and since 5 is not a square in Z/7 the Legendre symbol equals minus 1. One more example. Replacing the 75 by 72 we get a remainder of 2 which is a square and so the Legendre symbol equals 1. All clear? Great. Then let's look again at the statement of quadratic reciprocity and see if we can make some sense of it. Ok, in the law of quadratic reciprocity P and Q stand for different odd primes. Then the law tells us that if we know that quadraticness of P with respect to Q then straight away we know the reciprocal, the quadraticness of Q with respect to P. Okay, what's the big deal wit that? Who cares. Well I definitely care, A LOT. I mean this is 100 hours later of doing this stuff. Quadratic reciprocity is a very powerful, amazingly simple and astonishing out-of-nowhere relationship between pairs of primes. It is one of the fundamental ways that mathematicians gain a deep understanding of the very very mysterious prime numbers. So let's see if I can make you care, too. Okay let's first look at a quick example with some little primes 23 and 7. Evaluating the right side gives -1 to an odd power so that's minus 1. Okay what about on the left? Well we're now experts when it comes to the field Z/7 right? So the first Legendre symbol is easy to calculate 23 divided by 7 has a remainder of 2 and we know that in Z/y 2 is a square and this means that our Legendre symbol is equal to 1 and this straightaway gives us the value of the second Legendre symbol there. And what does that mean? That tells us that 7 is not a square in Z/23 really but where did that come from we didn't do the multiplication table for Z/23 or anything but somehow we know something about squares in Z/23. So even if you suspect there is no deeper purpose to all the streak I hope you agree that it's a really really amazing trick. Now before we do some more exploring of quadratic reciprocity I want to do a simple fiddle of the reciprocity law to make its use a little clearer. Suppose we want to solve this Legendre symbol. Then instead of dividing by the second Legendre symbol we will multiply it by the second symbol. Okay like that. Why do that? Well the second symbol is either 1 or minus 1 since we have distinct primes. 0 isn't possible here, right? So the squared symbol must be 1 and disappears. There, neat. Now we have the first Legendre symbol directly in terms of the second and for the rest of this video that's how you should think of the law of quadratic reciprocity. That's how I'll be expressing it. Now we've got to get going with the amazing proof but before that there are few properties of the Legendre symbol and application of quadratic reciprocity worth mentioning. I won't go into details here just giving you a quick taste. Okay quadratic reciprocity is about odd primes so what about that one even prime. Well for the prime 2 and any odd prime Q there's also this formula here. Next, the Legendre symbol has this really nice multiplicative property. This last formula is really just a concise way of noting the fact that squares and non squares multiply as usual -- a square times a non-squares a non-square and so on. I mentioned this earlier, remember? Now, by combining these formulas it's easy to perform mathematical magic. For example, we can quickly calculate very complicated Legendre symbols such as this one. So the Legendre symbol of 412 on 389. that is, we are asking if the remainder of 412 on division by 389 is a square in the mini ring Z/389 and yes we could make the multiplication table but we're not crazy. Quadratic reciprocity comes to the rescue. Want to see? Well here we go. So this is the whole calculation here so we applying these things over and over and you see the numbers getting smaller and smaller very quickly. You can do this calculation really very quickly and the result is this monster thing is equal to -1. Pretty amazing isn't it and that's just a taste. And now are you ready to venture forth to where not many mortals have ventured before? Are you ready to embark upon a proof of this amazing theorem? Great! But now a problem which of those two hundred-plus proofs should we choose? Remember Euler couldn't prove quadratic reciprocity and it took Gauss a long time to do so. Now it's no surprise that all of the standard proofs are tricky and are embedded in research papers or serious textbooks, putting them way out of reach of anyone without a serious background in math(s). And, to be honest, I had pretty much given up although I had always wanted to Mathologerize quadratic reciprocity, I really didn't think it was possible. So that's why I got so excited when I learned about Matt Baker's reformulation of a proof in terms of a card trick. The whole thing is really quite magical. Ready for the magic. Okay are you ready for some card magic? Nothing up my sleeve :) Our ultimate goal is the quadratic reciprocity formula there and I'll get there by showing you how to reinterpret the two Legendre symbols and the -1 power in the formula in terms of strange ways to deal cards. Ready? Now the primes P and Q in the formula lead us to use a deck containing P times Q cards. In usual Mathologer style I will focus on a specific example and I will make the prime's P and Q equal to a 5 and 3 so we'll be working with a deck of 15 cards face-up numbered 1 at the top down to 15 at the bottom. And now as the first step let me show you how the complicated minus 1 power in quadratic reciprocity arises in card dealing. The starting position for our card trick are the cards laid out in a 5 x 3 array, like this. Okay now from this starting arrangement pick up the cards row by row. This is easy but there will be lots of cards flying around. There aere lots of cards flying around and the order we choose them in is critical, so pay attention. Okay, first pick up the 1. Now pick up the 2 and place it under the 1. There under. Next the 3 which again goes under keep on going there under under under under under under under under under under under. Great, the cards are now in descending order in your hand. Now we'll deal the cards back onto the grid but this time column by column from top to bottom and left to right okay first there there and then the next column and it keeps going automatically now. Third column, fourth column, fifth column. So by picking up the cards by row and then placing them back down by column we've changed the order of the cards. This amounts to a permutation, a reordering of the numbers 1 to 15. Now as many of you will know every permutation has a sign either plus 1 or minus 1. If you're not sure what that means don't worry just go with the flow and I'll explain later. And what is the sign of the permutation for our scrambled 5 times 3 deck. It turns out to be exactly that minus 1 to the PQ stuff in the reciprocity law. Got it? What I'm claiming is that the power in the reciprocity law is captured by picking up our cards row by row, followed by placing them down column by column. And what about the Legendre symbols? Well it turns out that they can also be captured by dealing and picking up our cards. Apart from dealing and picking up by rows and columns the new permutations also include a weird way of placing cards along diagonals which I'll show you shortly. Okay there's definitely lots of work to do. Showing that our three reciprocity quantities are captured by these three permutations. But once we've established those three identities the proof of quadratic reciprocity can then be finished in one magic step. Ready? Still nothing up my sleeves. Yep okay let's look at the three permutations. Focus on the second and the third permutations and let's perform them one after the other. First we pick up by rows. Now put them down by columns. Yeah okay three four five. Now the next permutation, pick up by columns again. Did you see the magic? You had to be looking carefully. The magic is that the last two moves, the laying down and picking up in columns cancel each other out. This means that at this point the deck is ordered exactly as if we had just performed the single step of picking up by rows. And that means we've got this equality. In other words, the first card permutation is the same as the second and the third permutations done in sequence. But now we can use a secret weapon, the multiplicative property of permutation signs. Again don't worry for now if you've never seen permutations before. Just accept it, our secret weapon gives us this equality. And now this equality of the signs translates, via the green pink and blue equalities, into the law of quadratic reciprocity. Ready? Pure magic. I hope you all agree that this is an amazing proof. But of course there are some itsy-bitsy details left to sort out. I have to explain to you what the diagonal dealing of the cards is and I have to prove to you that the signs of the three dealings equal to three parts of the reciprocity formula as indicated. So plenty to do. Well, actually there's a little less to do than it seems. The proofs for the green and blue equalities are the same because switching the roles of P and Q is the same as switching rows and columns and so there are really only these two equalities. I now get down to proving these two equalities give or take justifying our secret permutation weapons. As I've indicated the proof hinges on some properties of the signs of permutations and is a bit too much to also prove these as well in this video. So for this video I'll only state these properties and take them as given. Some of you will be very familiar with permutations but for those of you who aren't don't worry just run with it I promise my next video will be exclusively about permutations that video will include the details of what we're using here as well as plenty of other nifty applications. If you don't know this stuff already and even if you do you've definitely got something else to look forward to. Okay down to work. In this chapter I'll prove the pink identity. The key to doing this is to show how you can calculate the sign of this permutation. Well the sign of any permutation is simply -1 to a certain power. The minus one bit is already encouraging, right? We've got a minus one there ... And what is that power that gives the sign? It is the number of what I call the inversions of the permutation. An inversion is any pair of numbers in the permutation where the first number is higher than the second so in that permutation there the seven comes before the 2 that's an inversion. Here's another one and another one. But this one that's not inversion 2 and 11 are still in ascending order. Okay so it turns out our mathematical life depends upon counting those inversions. So let me show you an ingenious life-saving way to count inversions. For this particular kind of permutations that we're dealing with here place the cards back in the grid and keep an eye out for patterns. Let's focus on one of the cards say 5. Now locate all the cards that together with 5 make an inversion. Check the cards one at a time. 1 comes before 5 so no inversion. 4 comes before 5 no inversion either. AHA 7 comes after 5 so we've found an inversion. Next 10 after 5 another inversion, yep, another one, nope, 8 comes after 5 so no no no, 5 then 3 yep, another inversion. No, no no and finally no. Anything notable about the location of the other cards around five? Let me show you how this picture pans out for a few other starting numbers. So there's 8, 10 15. Got it now? The inversions for this particular type of permutation always correspond to a pair of cards that are placed positively sloped. If they are horizontally or vertically aligned or if they're placed negatively sloped then no inversion. So is that pair they're an inversion? Yep positively sloped so it's an inversion. And now for a very easy way to count the number of inversion pairs we introduce coordinates for the grid. Now here are two cards in inversion position with their coordinates (2,1) & (4,3). Hmm the first coordinate 2 is smaller than the 4 and the same with the second coordinate, the 1 is smaller than the 3. Ok but now it's easy to capture and count all the inversions. Can you see why? First choose any two different numbers from 1 to 5 say 1 and 5 those will be the first coordinates of our two cards, smallest to go in the first card. And then choose any two different numbers from 1 to 3, say 2 and 3. Those are second coordinates, with the smaller number again in the first card. There an inversion. Can you see we get all possible inversions this way? Easy right? And it's also really easy to count the number of ways of getting these inversions. It's just the number of ways of choosing the first coordinates times the number of ways of choosing the second coordinates. So how many ways of choosing the first two coordinates? 5 choices of numbers and we're choosing 2. So wave your magic wand and chant 5 choose 2 :) and there you are now the second two coordinates ... wave 3 choose 2. Do you know what these mean they're just mathematicians shorthand for the number of ways of choosing objects. We'll get to actually calculating these numbers in a minute. Whatever they are it means the total number of inversions is 5 choose 2 times 3 choose 2. And what if we start with a deck of P times Q cards? Then the number of inversions is P choose 2 times Q choose 2. And that means that the sign of our permutation is -1, remember -1? :) to that power there. Okay and from here it's basically algebra autopilot. The formulas for P choose 2 and Q choose 2 are these. You've all seen these, right? Great! And now we can have a little and well-deserved rest. We'll relax, switch on the algebra autopilot, let it show us how that power up there equals the power of -1 in the quadratic reciprocity law, that power there. So these two are supposed to be equal. So just remember, for quadratic reciprocity the numbers P and Q are odd primes. Okay ready, get set, relax. Tada, finished :) Really nice isn't it and we finally captured one of the quantities in our reciprocity law. Time for a short celebration, don't you think? Okay celebrations is over. Back to work. Here's a mini challenge for you. Take any random permutation of cards. Now change this permutation by shifting all but the last card one space to the right and bring the last card to the front like this. Your challenge is to determine how the cycling of the cards changes the sign of the permutation. Remember the sign is determined by whether the number of inversions is even or odd and specifically your challenge is to show that if we have an odd number of cards then the sign is the same after cycling but with an even number of cards the sign will change. Again odd number of cards, sign doesn't change. Even number, sign changes. We'll use this neat little insight twice at crucial junctions of the proof so don't forget. As always record your thoughts in the comments. Fresh and ready to go again? No? What about me? Anyway I know this is definitely a marathon Mathologer. But don't worry, we're already well up the mountain. The big task left is to prove that blue equality there. Then a little tidying and we're done. Of course, if we're going to prove that equality I first have to explain the D up there in our equation the mysterious diagonal card dealing. But before that our dealing instructions tell us to pick up the cards in columns. That's easy, so let's do it. So, there, things go under again as usual. Right, under, under, under, third column fourth column, fifth column. Cool. Okay now comes the diagonalizing. 1 is the top card and that goes in the upper left corner. 6 is next and goes on the diagonal below 1. Keep on going. hmm where does the 2 go. Easy just think of pac-man or asteroids or whatever your favorite loopy video game is and keep extending the diagonal. So if the grid continues at the bottom the 2 would go down there but since it doesn't we simply wrap around and the 2 goes up on top and now continue diagonally, there, continue diagonally. Off the right so wrap around to the left, continue diagonally, wrap around, and so on, diagonal there, diagonal there, wrap around.. Cool, it's actually a bit of a miracle that this works without the cards running into each other. So another challenge for you. Show that this works with the whole grid being filled because of the prime dimensions of the grid. It is because P and Q have no common factors. Now that is a very interesting permutation, right? Hmm maybe maybe maybe not so obvious> So let me show you a remarkable property of this permutation, let's compare it with the starting setup, there. You got it? Yep the numbers in the first row just got shuffled amongst themselves and the same is true for the second row and the third row. You see how that happened that's yet another challenge for you, not a hard one if you go back to how we got that permutation. Anyway what it means is that our column up diagonal down combo permutation can be thought of as three independent mini permutations, one for each row, like this. But now think about the sign of our big permutation. Remember that's the sign we're hunting, the sign comes from the number of inversions. So what about inversions. Well since the rows stay put the inversions of our big permutation can only come from the inversions within each row. But the sign of a permutation is -1 to the number of inversions and that tells us that the sign of our big permutation is just the product of the signs of the three row permutations. Got it? Cool, hmm? And now really clever insight. Those three row permutations are essentially identical. Can you see it? Nope, definitely not obvious. So let me explain. Take a look at that first and third row and cycle shift the first row a couple of times. One, two there see 2 aligned, 4 aligned, 1 aligned, so on so. After the cycling we have essentially the same permutation of each row just with different labeling and you can easily check that the same thing works for the middle row. But now remember your challenge from before. Since we have an odd number of cards in each row the cycling doesn't change the signs of the permutation and that means, and this is very cool, and really important, that all of the row permutations have the same sign. Now if the common sign of the row permutations is 1 then 1 times 1 times is 1. And so the big permutation also has sign 1. And if the common sign of the row permutations is -1 then because we are dealing with an odd number of rows the product of these -1 is also -1. Summarizing this means that the sign of our big permutation is the same as the sign of any one of the little permutations, say of the first one. That's pretty cool isn't it? Now this is definitely the time where you take a deep breath :) Now believe it or not we're getting very close and hats off to all of you hardcore Mathologerers who made it this far. I'm really really proud of you. And I'm proud of myself :) Okay recovered? Sort of? Good! Time to continue to track. What remains for us to show is that the sign of this row permutation is equal to Legendre symbol we're chasing and for that we first have to figure out how exactly this row got permuted around. Well, what we're seeing in front of us almost looks like the remainders in Z5, which is what the Legendre symbol is all about. And it would be exactly the remainders in Z/5 if we had labeled our cards beginning with 0 rather than 1, like this. Of course relabeling like this doesn't change the sign of our permutation. Now when you ponder the effect of the diagonal deal on this first row you quickly figure out what's going on. Let's do that together. So how exactly do we get from the cards in their starting position to the final arrangement? Well, when we pick up the cards by columns the cards in this row end up in the natural order in our hand. Now dealing diagonally the 0 goes straight back to where it came from. Now we move to the right and put down a card in the second row. Then we move right again and put a card in the third row. Move right again but now it's the turn of our first row again. Move right, second row, move right, well wraparound third row, move right and it's our turn again, and so on. One, two, our turn. One, two, our turn. In summary, to place each successive card, we move three spaces to the right and wrap around whenever necessary and the successive advancing by three turns out to be just multiplication by three in our mini field Z5. Let me show you how. Here's our beginning arrangement again. There. Now take this zero in the first spot and multiply by 3. 0 times 3 is 0 and so 0 stays in the zero spot. Next 1 times 3 is 3 and so 1 goes to the 3 spot. 2 times 3 is 6, 6 divided by 5 gives a remainder of 1 and so 2 goes to the 1 spot. 3 times 3 is 9 remainder 4 and so 3 goes all the way to the end. Just 4 left and it better go in the empty spot. So let's check: 4 times 3 is 12 remainder 2 and so 4 goes in the second spot. What a relief :) Okay so our row permutation is captured by multiplication by 3 in the world of Z/5. That definitely feels like we're getting close to capturing the Legendre symbol of 3 on 5. To complete the capture we have to show the sign of the row permutation is equal to the Legendre symbol. Last chapter, promise. okay we're just about set for the final - up to the peak before that I have to introduce you to one more final magical property of the sign of a permutation. For those of you in the know this is the fact that the sign of a permutation stays unchanged after conjugation. I know that doesn't help much if you don't know the jargon. What it means is that if you first shuffle to change the natural order of the cards to any other order, then the sign of the permutation will stay the same. I call this property the reordering property. Sounds pretty damn mysterious I know. Let me explain. First let's look at a random permutation of our cards this one here. So on top we've got the natural order of our cards and at the bottom the permutation. Now first think of what you see in front of you as five top and bottom pairs of numbers. Second do something weird: reshuffle things in pairs any way you like. Okay so things get stuck together like this. Finally think of what you see in the top row as the new natural order. So four is the new 0, 3 is the new number 1, 2 stays at 2, and so on. Okay, now drum roll here's the reordering property. The sign of our new permutation at the bottom is the same as the sign of the original permutation. Looks totally different but the sign is the same, guaranteed. And that works no matter how we shuffle things around. Again if all this permutation magic is new to you don't worry accept it for now and I'll explain everything in my next video. And now with this reordering property in our armory, we're ready to attack the summit and our path to the summit is called Zolotarev's lemma. Now Matt Baker's blog post is addressed to mathematicians and so Zolotarev's Lemma is dispensed with in just a few lines. Not very Mothologery is it? So for the mortals among us here is the Mathologerized version. Okay Matt starts like this. That's started well. What the hell is a primitive root I hear you ask. I'll explain. it's the final missing piece and then everything will click into place. Remember our final puzzle involves mucking around with the remainder after division by five. In other words, we're performing algebraic acrobatics in the mini field Z/5. Now, many fields contain special numbers called primitive roots and it turns out that the number 2 is one of those primitives roots in Z/5. So let me explain what that means. First write down the powers of 2, next calculate the remainders after division by 5, so we get 2 4 3 1, 2 4 3 1 with those remainders cycling around. It's pretty easy to see that the remainders have to cycle but the important point for us is that all nonzero remainders 1 2 3 & 4 appear in the cycle, all of them. And having this property is what it means to be a primitive root. But now with these power remainders in view let's take another look at the squares and non squares in our mini field. Remember those? You saw them maybe two hours ago :) Notice that the even powers of 2 give us the squares and the odd powers of 2 give us the non squares. So even powers are squares, odd powers are non-squares which also feels pretty natural isn't it? And this turns out to be true for any primitive root. And this is the second property of primitive roots that's really important to us. Now back to our permutation and to the Legendre symbol we are hunting there that Legendre symbol is supposed to be equal to the sign of this permutation. And it turns out that our primitive root is also the key to this puzzle. Notice that the zero stays put in the first spot so our permutation is really just a permutation of the four nonzero remainders and the sign we're chasing is the sign of this four card permutation. And as we've seen this permutation comes about by multiplying 1,2,3,4 by the prime number 3. But now think of those permuted remainders as remainders of powers of 2 there. 1 there's 2 and there's 3 and finally that's 4. Okay, again, the permutation comes about by multiplying two numbers at the top by 3 but in our Z/5 minifield two cubed has remainder 3 and so multiplying by 3is the same as multiplying by two to the power of three and, and here it comes, when we multiply all those (powers of two) by (two cubed) we do this by adding the exponent 3 to each of the other exponents, right? Multiplying powers of two amounts to adding their exponents. So hold on to this insight. The critical multiplication amounts to adding the green three to all the exponents. But now we can fire our new permutation reordering weapon. Let's make the order that the exponents are in into the new natural order, like this. There the exponents are now in natural order 1 2 3 4. So the reordering property tells us that the sign of the original permutation equals the sign of this new permutation of the exponents and this new permutation you just get by adding 3. And of course adding is a lot easier than multiplying so we've definitely made progress here. And also adding 3, when you have a really close look, is really the same as just shifting three times from natural order. There natural order, shift once, shift twice, shift three times. Super simple. All right, so we've got now a really really simple thing to look at. That's our permutation. And now everything is all ready in primed to come together in one big glorious bang. So let me just remind you of all the bits and pieces so that the punchline will deliver a big proper punch. This is what we want to show, that the sign of our column then diagonal permutation equals the Legendre symbol and we've just seen that the sign of this permutation equals the sign of that simple shift permutation. The crucial link was established by the powers of 2 the powers of a primitive root. In particular or prime multiplication number 3 corresponds to the shift exponent 3 now that these two numbers turn out to be the same in our example is really just a coincidence. Now remember how to check whether our pink prime 3 is a square in Z/5 the pink prime is a square if the green exponent is even and it's a non square if it is odd. In this case the green 3 is odd and so the pink prime 3 is not a square in Z5. Not being a square means the Legendre symbol is equal to - 1. On the other hand, the same green exponent 3 also tells us that the permutation on top comes about by shifting the cards in natural order three times. Here's the natural order. In natural order there are no inversions and so the sign begins as 1. Now we have an even number of cards. Remember that means every time we shift one space the sign of the permutation switches. But our green exponent is odd meaning three shifts and therefore the sign of the resulting permutation will be -1 as well. Have a look: shift once, shift twice, three times: -1. So the green exponent being odd or even simultaneously forced the sign of the permutation at the top and the Legendre symbol at the bottom to be both -1 one or both 1. And that finally, finally proves that the permutation sign up top and the Legendre symbol below are equal. Tada. I never do this again promise :) What an incredible argument. Real genius don't you agree. Of course, three and five are just placeholders for any two different odd primes. You can check through and see that the argument presented here is completely general except for some facts about our prime mini fields and a little background stuff on permutations which I'll cover in my next video it really is a complete proof of the law of quadratic reciprocity. And now two final challenges. Nope just kidding you've worked plenty hard enough, and so have I. No more homework but if you're perceptive and still alive you might notice there were two other places earlier in the video where I really need the reordering property of permutations to make proper sense of things. Second the fact that P and Q are different odd prime numbers really only strikes in this last chapter. You only get these special primitive roots if you are dealing with primes everything else I said before works for many more pairs of numbers P and Q. Also I note that this was another one of my master class videos. Maybe that has already occurred to you at some point :) It is obviously a super challenging video so don't expect to get absolutely everything in the first viewing unless you are the reincarnation of Gauss or Zolotarev. Now please let me know what worked for you and what didn't and, as always, please ask in the comments if there's anything that's not clear. And that's it for a very very long today. See you next time for a much easier video.
Info
Channel: Mathologer
Views: 211,298
Rating: 4.9233761 out of 5
Keywords:
Id: X63MWZIN3gM
Channel Id: undefined
Length: 56min 37sec (3397 seconds)
Published: Sat Mar 14 2020
Related Videos
Note
Please note that this website is currently a work in progress! Lots of interesting data and statistics to come.