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.