Cookies   I display ads to cover the expenses. See the privacy policy for more information. You can keep or reject the ads.

Video thumbnail
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.