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.
This video is one hour long!!! Really great stuff, but who here has got what it takes?
wow is the mathologer drama gone?
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.
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
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
and
which as in the video defines a permutation of the integers 1 through 10. In our case, explicitly, the permutation is
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).