If it isn't Euler it's Gauss. Remember folks, if a murderer comes into your house and asks who proved a theorem you never heard of the Best survival strategy is to say "Euler or Gauss"
I don't know if this story ever reached Finland, but in the US, there was a mathematical genius who had Euler-like talent, but became a Ludditic terrorist. If anybody would have done something that deranged, it would have been this guy: en.wikipedia.org/wiki/Ted_Kaczynski
OTOH it shows up on about page 20 of the first number theory book I ever saw, and the previous 20 pages largely deals with basic number theory (like unique prime factorization, greatest common divisor, etc.) and items interesting unto themselves whether or not quadratic reciprocity had ever been discovered, and each item typically takes under a paragraph to prove. Other books have briefer versions of the same proof than the 4 pages in that one, but that book covers the case for 2 and -1 all at the same time, and actually has two proofs of the more arduous section, the second one of which is a diagram that sums up what just took a couple of pages of algebra (provided you don't cafe about 2 or -1.) I didn't want people to think this was going to be one of the hard things if they wanted to pursue number theory.
(28 March) Really bizarre, this video was basically invisible for almost two weeks with hardly any recommendations going out to fans. Only now RU-vid has decided to actually show it to people. Who knows, maybe it was a mistake to mention cat videos in previous videos and the RU-vid AI is now under the impression that the target audience for these videos has changed :) The longest Mathologer video ever, just shy of an hour (eventually it's going to happen :) One video I've been meaning to make for a long, long time. A Mathologerization of the Law of Quadratic Reciprocity. This is another one of my MASTERCLASS videos. The slide show consists of 550 slides and the whole thing took forever to make. Just to give you an idea of the work involved in producing a video like this, preparing the subtitles for this video took me almost 4 hours. Why do anything as crazy as this? Well, just like many other mathematicians I consider the law of quadratic reciprocity as one of the most beautiful and surprising facts about prime numbers. While other mathematicians were inspired to come up with ingenious proofs of this theorem, over 200 different proofs so far and counting, I thought I contribute to it's illustrious history by actually trying me very best of getting one of those crazily complicated proofs within reach of non-mathematicians, to make the unaccessible accessible. Now let's see how many people are actually prepared to watch a (close to) one hour long math(s) video :). Have a look at the description for relevant links and more background info. The first teaching semester at the university where I teach just started last week and all my teaching and lots of other stuff will happen this semester. This means I won't have much time for any more crazily time-consuming projects like this. Galois theory will definitely has to wait until the second half of this year :( Still, quite a bit of beautiful doable stuff coming up. So stay tuned.
I can confirm that I've just watched the video for the first time today, even though I exclusively use subscriptions feed page and watch all of it thoroughly. It's very likely that it wasn't in the subscriptions feed at all at the moment of posting.
Was gauss not in the thumbnail at the time of this comment? Maybe he's only recognized that easily by the countrymen who paid with bills with his face on it for years?
Please add a COMMA: "Take that, Mathologer!". Here are some examples with/without a comma: Take that Mathologer and keep him locked away. Take that job and... shove it. Take that, Job, said God. "Ouch", said Job. Let's eat grandma [said the cannibal to his brothers]. Let's eat, grandma! Etc.
-He says something about rings -I think it will be another Mathologer analogy or something -He is actually talking about damn rings from abstract Algebra -I get excited
@@camerontankersley3184 if you mean field in the common way, I love topology, measure theory, functional analysis and differential geometry. If you mean THE field, then I'll go with the reals xd
@@jksmusicstudio1439 Omg su. But the reals do be poppin doe. Anyway, I'm in college and my parents freak out whenever I wanna take any math courses with big numbers in them. But they kinda be paying the bills doe, so I have to listen to them. So Anyway, since I can't take the juicy stuff in school I pretty much have to self-study. So my goal is to go through a textbook on Linear Alg this break. Since ur a math expert, do you think I'd be ready for Abby Alg after that? I took a foundations course this semester so I have a touch of set theory and I can prove some super basic stuff. I'm trying to sneak in a combinatorics course next semester with calculus three, so should I wait for that to finish? Like what's the verdict and what should I take after Linear and Abstract Alg?
I think this is it for me with one hour long videos for a while :) Just think about it. If a video like this takes one hour to watch how long does it take to make?
@@Mathologer Rest assured that your efforts are greatly appreciated. This is one of the (if not the) best mathematics channels on youtube and the reason is that people recognize quality and hard work when they see it. Happy π-day!
I watched this video 5 times and I have to watch 10 times more in order to really get it, but I just wanted to tell you how much I love your videos and the way you teach. Your are exceptional!
What makes Quadratic Reciprocity so special, and in particular, why was it so important to Gauss? Why is squaring integers so important in Number Theory? To understand the answers to these questions, you need to appreciate the work Gauss did in the theory of quadratic forms and their application to differential geometry. Gauss's "fundamental theorem" of differential geometry is about how the 2nd order partial derivates of a function that defines a "surface", e.g. `f(x,y)=height`, depends on a specified quadratic form called the "metric tensor" of the surface (and its first derivates), which gives a rule for how to measure distances "on the surface". This shows a profound and deep insight into the nature of the relationship between a large number of otherwise seemingly unrelated abstract concepts. Squaring numbers plays a fundamental role in both Number Theory and Geometry. After watching this video twice, going on a few wild goose chases, and not being able to stop thinking about it: I finally think I understand why Gauss placed such a high degree of importance on this particular theorem, and feel like I have a lot of reading to do now!
I think I read (wiki?) that Fermat gave specific examples of the "law". So lots of mathematicians were motivated in this direction to prove/generalize another example of something Fermat stated without proof. Very interesting video, far from anything I've ever been exposed to. (And a welcome distraction in these confusing times.)
I can't believe it's actually finally here. I've been waiting for this since the joke at the end of pi is transcendental proof. Thank you, Mathologer. You've somehow outdone yourself yet again!
There is actually a ring for each integer, but the negatives just copy their positive counterparts, 0 gives the integers itself, and 1 gives a very boring very mini ring that only has one element. :)
Three Rings for the Math-kings under the sky, Seven for the Physics-lords in their halls of stone, Nine for Computer Programmers doomed to die, One for The Professor on his dark throne In the Land of Ideas where the Colossus lies. One Ring to rule them all, One Ring to find them, One Ring to bring them all, and in the darkness bind them, In the World of Imagination where the Shadows lie
@Ron Maimon Great summary! I only know a little bit about abstract algebra, but you just summarized multiple hours of video lectures into one YT comment! 😄👍 Just one thing. You said, "There's only one integer divisible by 0, and that's zero." Wouldn't it be more accurate to say that, "There's only one integer that's a *multiple* of 0, and that's 0."? Even 0 is not divisible by 0, right?
@@robharwood3538 I think graphically you can see in the curve for 1/x there is often a vertical line at x=0 so you could ask, "if x=0, what is y?" (to which the answer is "it could be anything" or as others put, "undefined").
RU-vid's recommendation is, those days more than ever, under authority in order to broadcast only OMS approved informations about Coronavirus (or to censor any criticizing information on the situation or the behaviour of governmemts and their links to pharmaceutical lobbies or finance : it depends of your consideration of free speech)
I understand every word you say, but your sentences are mostly beyond my understanding! I am amazed at how you can explain these issues (I last studied Math over 50 years ago, but remain fascinated).
I'm reading a proof-writing book and it's covering modular arithmetic right now so I'm going to give a proof that the diagonal placement covers the whole board (or try to). Claim: If we're placing the cards down diagonally on a grid with prime dimensions, we will cover the entire board Proof: Call the top left square (0,0) and the bottom right square (p-1,q-1) where p and q are distinct primes. Then the nth card we place down (starting indexing at 0) will have dimensions (n mod p, n mod q). Assume we are not covering the entire board, so there is a card we place down at some point, say, the kth card, that ends up in the same position as a previous card, the nth card, where k < pq and n
It essentially follows from the Chinese remainder theorem: If x = n mod p and y = n mod q, then there is only one solution for n mod pq for a given pair (x, y), provided that p and q are coprime.
I cant believe I hadnt heard of Quadratic Reciprocity considering my honours dissertation was on finite fields. Granted, it was efficient computation of matrix opperations under GF2 on GPUs, but still, I cant believe I'd never come across any of this.
This approach is awesome! We covered the law of quadratic reciprocity in number theory class, but the proof was omitted, and it came down to uninspired manipulation and flipping of Legendre symbols. But now I'm 95% convinced that I understand why it all works :) I suppose something that could have been expanded upon for the benefit of other viewers is what the Legendre symbol is used for (which was briefly mentioned in the video), such as an example of solving a quadratic congruence over Z/pZ. Maybe that would make the whole LQR/Legendre business feel more motivated, but it's great as it is. And maybe another visualisation of the quadratic residues/non-residues mod a larger prime (like 17 maybe?) so we can get a feel for the numbers that appear along the diagonal, in particular what to expect (somehow it is easy to forget obvious things like (49/p) = 1 for any prime p, no need to find remainder first, as the symbol can lose attachment to its definition when purely evaluating by rule).
i love your channel and all of your videos, but this must be the most mind blowing one in a positive way. your passion for math and didactics is just so fun to watch. in german there is the expression of a spark jumping “over” when someone successfully communicated something. at least in my case you made many sparks jump over/through this medium and ignited interest and sparked fires but in a forest clearing sense, burning ignorance/not-knowing. the best thing watching and rewatching the videos is the feeling of being part of an experience you and your team obviously planned to be captivating and entertaining but not compromising (maybe impossible to compromise) complexity. i love that! whilst making it seem light and easy to lay out al kinds of layered/interconnected topics and parallel to that showing the struggle with the task/empathizing with an audience and our common attention spans/rivaling media fun/game et cetera. self-referential in a postmodern sense but by god not so heady and dead serious! Vielen Dank und Grüße aus Deutschland.
Cycling answer: if you have a permutation of cards, looking at the last one, we see that all the other numbers are behind it. In particular, the lower ones are behind. Putting the last card in the front means creating inversions and flipping the sign that amount of times. But also all the numbers bigger than it are already behind it, and so there are already inversions, but putting the card at the front undoes these inversions and flips the sign by the amount of cards. So we see that combining both cases means that we flip the sign by the amount of cards behind tge last card. So if there are n cards, we flip n-1. If n is odd, n-1 is even, so the sign doesn't change. If n is even, n-1 is odd, so the sign changes.
20:33 “Where did that come from?” The big “whoa” moment for me! Thanks for making it so much easier to understand why this equation is significant. I could never understand why when I was taking a course in number theory.
In C↑D↓, the reason it only mixes up the rows and not the columns is because both C↑ and D↓ use the same vertical sequence (i.e., top, middle, button, top middle, bottom...). Only the horizontal sequence changes.
Firstly, thanks. I'm looking forward to this. Before I get too far in and while I remember: Do you take requests? Can I suggest a Beginner's Guide to p-adic Numbers.
So glad I stumbled on some of your videos today. I remember when we both worked at The University of Adelaide. Your enthusiasm and humour have inspired many, many people for several decades. I am thrilled to see you are still actively exciting people about Mathematics. I will have to view all your videos when I can! Best Wishes, DB
@@ccarson I guess it was back in the ‘90s. Gosh, I feel really, really old now. Of course, in those days, it was still correctly referred to as “The University of Adelaide”, as it was formally named and incorporated in the 6th November, 1874 Act of South Australian Parliament. Yes, the name included “The” - with a capitol “T”. The age of the Internet saw variations informally introduced and eventually embraced, which can be evidenced on its own Web site. I am old enough to remember when the correct name was important … lol. Embracing the term Adelaide University was eventually accepted, if only because it elevated the university on alphabetically ordered lists.
@@Xubono For me, the usage of ”The” with a capital ”T”, in proper names seems quite natural. For example, the longer version of the name of my and my Best Friend’s micronation: ”The Forest”, includes ”The” - with a capital ”T”. 😅
1) RC can be proven to have the inversions on the positive diagonals. It should not be skipped. 2) Pi (xi-xj) for i=0, show that it is Abelian - commutative, i.e. a*b = b*a. The question was posed by professor David Chilag of blessed memory from the Technion, Haifa Israel. The problem does not require any deep knowledge about groups. It is easy to show that a^(k+1) * b^(k+2) = b^(k+2) *b^(k+1) and if k+1 and k+2 do not divide the number of elements in the group and the group is finite, the powers k+1 and k+2 are one-to-one maps and therefore the maps cover all the elements in the finite group and we are done (there are no elements of order k+1 or k+2). However, the original question does not have any condition on the order of the group and the group can be infinite. If k=0 then the second condition is a * a * b * b = a * b * a * b then multiplication by the inverse from right by b^-1 and left by a^-1 gets a * b = b * a and we are done. The question only requires to know the 4 axioms of a group.
37:25 Alternate proof from the one of eliya sne (for those who know more about permutations) : Let Sigma be a random permutation, and Tau the cycled one. We can get Tau by "multiplying" the permutation Sigma with a fixed cycle of length n, let us call it Epsilon = (1 n n-1 n-2 n-3 ... 3 2) So the sign of the cycled permutation Tau is equal to the sign of Sigma times the sign of Epsilon, so we want the sign of Epsilon. It is easy to see that Epsilon has n-1 inversions, so if n is odd, then sgn(Epsilon) = 1 and the sign of Sigma is unchanged, and if n is even, then sgn(Epsilon) = - 1 and the sign of Sigma is changed. End of proof. I know this is a little bit more technical, but I hope it's a good alternative :)
The story of how Euler got into formulating quadratic reciprocity is fascinating. It's contained in "Primes of the form x^2+n*y^2" by David A. Cox. HIGHLY RECOMMENDED because it's an historical recount.
You always explain things so clearly that I know exactly where I stop understanding the maths. I often don't quite understand the last section or two of your long videos, but they're still fascinating.
39:16 tile an (ab)x(ab) grid with (a)x(b) rectangles and draw the top-left to bottom-right diagonal. If it intersects the bottom-right corner of a rectangle then a square is formed by (n)x(m) lots of (a)x(b) so na=bm, n!=b, m!=a so a,b cannot be prime.
Finally, one of my favorite theorems! I want to leave you an exercise about this theorem that made me appreciate it even more: Let p be a prime such that p is either equal to 2 or 3 modulo 5. Prove that the sequence n!+n^p-n+5 has at most a finite number of squares
It was crystal clear for me. But I must admit I'm a french PhD in math, however not a specialist in Number Theory (in fact in Complex Geometry, Conformal Field Theory with a little extra knowledge in Non-Commutative Geometry, Intuitionist Logic and Measure Theory...what a conceited & pompous mess !). You've remembered me of my undergraduate years at the University and the wonderful mathematicians I had the chance to meet there. A pure joy !!!
Professor, I am looking forward to you aiming at presenting the Galois theory the Mathologer way in the future. I have always considered the inability to solve quintics by radicals mysterious, hopefully your video will shed some light on the concept to non-mathematicians like me. Thank you very much for all the stuff you create, it is unimaginable to comprehend the amount of thought, time and effort to get such things done, with the above video being an excellent example.
Meanwhile the following may interest you: Galois theory is not necessary for proving the existence of a polynomial of degree five whose roots cannot be expressed by radicals; the prior Abel-Rufini theorem already establishes that; But Galois theory is helpful in finding an example of such a polynomial.
The pink identity can also be demonstrated as follows. Looking at the position of the cards after the permutation, each card makes an inversion with all other cards that are either higher and to the right or lower and to the left of that card. Such cards form smaller rectangles of cards that go either up to the top right corner or down to the bottom left corner. Counting all cards in all these smaller rectangles, we would count every inversion twice, so we only consider say the top right rectangles. To get the total number of inversions we sum up the number of cards in all possible smaller top right rectangles, which is Sum{i=1..p-1; j=1..q-1} i.j = Sum{i=1..p-1} i.(q.(q-1)/2) = (p.(p-1)/2)(q.(q-1)/2).
I've never heard about quadratic reciprocity before … and I want to know more about this! Thank you for providing good-quality post-bachelor math popularization!
33:22 I just spotted another easy way to count the number of inversion-pairs, for this type of permutation: Notice that the top-left and bottom-right cards: 1 & 15, don’t feature in any inversion-pairs; while their ”opposites”, in a way, the top-right and bottom-left cards: 13 & 3, feature in the maximum number of inversion-pairs: 8; and all the other cards display a pretty nice pattern: The 1st row sees the number of inversion-pairs always incrementing by 2: 0, 2, 4, 6, 8; while the 2nd row features the constant number of inversion-pairs: 4. Finally; the 3rd row mirrors the pattern of the 1st row (not surprisingly). This means that the average number of inversion-pairs a single card features in, is 4. Then, multiplying 15 by 4 gives: 15*4 = 60; but that counts each inversion-pair twice; so, we need to divide by 2, to get: 15*2 = 30, which is also the number of inversion-pairs you get from multiplying the binomial coefficients: ”p choose 2” * ”q choose 2”. In general; the formula would be: (pq*((((p+1)/2)-1)*(q-1)))/2. 🙂
Well done with the video. I had to watch it a few times to understand it all! I was OK to the halfway point then started to struggle, but stayed until the end. Thank goodness for the chapters. Keep making them.
Damn, this was, I think, your toughest masterclass yet. Almost all of it worked for me, but I was really stuck at the point where you used the powers of two and got the fact that the new permutation will be obtained by adding 3 to the new natural permutation. I would have benifited from a little step-by-step at that point. This was a lot of fun, though. I'm looking forward to learning more about these fields and the inversions and other properties of permutations. Thanks for this!
This is the happiest classroom ever. Even though I don't practice mathematics (I'm Law and Philosophy student), I really appreciate your videos. You guys rock!
Wow, this is the first mathologer video that I wasn't able to finish in one sitting. The longest and possibly also one of the hardest. Still also one of the most useful I'd think. Prime number theorems are some of the hardest but most rewarding!
37:25 Proof: Let n be the number of cards, Let k be the number of cards bigger than the last one. By transferring the last card to the other side i eliminated k instances in which sometimes bigger than it is before it but also added (n-1)-k instances in which its bigger the other numbers (because the rest of the numbers are smaller then it). So eventually i just added n-1-2k . Since its a power of two i can ignore the -2k (its even). Now, i am left with just n-1 added to the power. If n is even then n-1 is odd and therefore the sine changes. If n is odd then n-1 is even and therefore the sine doesn't change. [|||]
Because this operation can be decomposed into (n-1) transpositions. And each transposition changes the sign. (-1)^(n-1) = 1 when n is odd and -1 when n is even.
I am teaching math my thirty-odd y-o daughter, who had forgotten much of what math she had learnt at school. And we just ended a long chapter on variations, permutations, and combinations (with or w/o repetition), their formulae, and their equivalences to certain functions. Now this video is coming to be the top cherry to that chapter! Many thanks, Mathologer.
I saw something very interesting about the diagonal dealing permutation. Let's say we have two distinct odd prime number p & q, what on earth does doing a diagonal dealing operation have to do with squaring numbers and taking remainders? The idea is, you draw a rectangle with sides p, q and area p*q and observe when you do the diagonal dealing operation you will be in this analogy drawing a line whose length is equal to the area of the rectangle p*q. Then since the length of this diagonal line is p*q, if it were possible to find two integers a,b such that (p*q)^2 = a^2 + b^2, we can draw a different rectangle of side lengths a & b whose diagonal is also a line with length p*q. To see where the remainder operation comes in to play in this analogy, cover the plane with fundamental rectangles of sides p,q and make the rules that any 2 points in the plane are equal if they are in the same position in the fundamental rectangle.
Just a note - you don't actually need the existence of primitive roots in Z/pZ for the proof! If we let x\equiv q^{-1} mod p, then to find the sign of {x, 2x, \dots, (p-1)x} we can first consider the cycle (and subgroup!) {1, x, \dots, x^{ord_p(x)-1}} and note that all the cycles induced are just the cosets for our original subgroup, of which there are (p-1)/(ord_p(x)) of by Lagrange's Theorem. Since the sign is -1 to the power of the sum of one less than each of the cycle lengths, in this case we get (-1)^{(p-1)/(ord_p(x))*(ord_p(x)-1)}=(-1)^{(p-1)/(ord_p(x))}. If x is a QR, then x^{(p-1)/2}=1 mod p, so ord_p(x)|(p-1)/2 (hence the sign evaluates to 1), and if for contradiction it was also 1 for some non QR x, then ord_p(x)|(p-1)/2 which contradicts the well-known fact that x^{(p-1)/2}=-1 mod p in this case. Then the sign is (x/p)=(x/p)^{-1}=(x^{-1}/p)=(q/p) :).
39:15 Proof that the diagonalisation always works for _distinct odd primes_ p and q. First, imagine a coordinate system such that the card in the ith row and jth column has coordinates (i,j). (Origin at top left, numbers increase as you go right and down.) Also, p is the number of rows while q is the number of columns. If it works R⬆D⬇surely it works for C⬆D⬇as well. Because of the way the numbers wrap around, you can easily see that the row number of the card n is the smallest positive integer that is congruent to n modulo p (or the remainder that n gives when divided by p, except we now call 0 as p). Let this number be a. So for n=13, p=3, the row number is 1, while for n=12, p=3, it is 3. Similarly, the column number is the smallest positive integer that is congruent to n modulo q. Let this number be b. For n=11, q=5, we have b=1. Now we have the coordinates (a,b) for n. For two cards to overlap, they must have the same coordinates, i.e. leave the same remainders when divided by p and q. Let it be assumed, for the sake of contradiction that there exist 2 distinct integers m and n, smaller than or equal to pq, such that the corresponding cards overlap. Now, if two numbers have the same remainder after division by a third number, their difference must be divisible by the third number. (Use Euclid's division lemma, it is easy algebra.) Thus, |m-n| is divisible by both p and q. Since p and q are distinct odd primes, it must be divisible by pq. But since at least one of them is than smaller pq, the only option is that their difference is 0, i.e. m=n. This is a contradiction, since m and n were supposed to be distinct. Thus, no two cards can overlap. Q.E.D.
I figured out that if you think of the grid as being on a torus, you can easily see why modular arithmetic and the rings apply here. The rows and columns are nothing but the two fundamental loops on the torus.
I liked your proof exercise near the beginning because it made me realize *why* 0 works the same in modular multiplication-it feels obvious to me now but it’s because multiplying by 0 here is like multiplying by the modulus in our familiar ring of integers, and when you multiply a number x by the modulus m, x * m is always going to be congruent to 0 (mod m).
My proof for the little thing: Let’s look at the following order of cards: 4/5/3/1/2 lets say that the number of inversions here is る We do the cycling thing: 2/4/5/3/1 Consider this section: (4/5/3/1): notice how the number of inversions between these 4 numbers’ orders doesn’t change, let’s say that number is X So the only thing that changes after the cycling is the number of inversions for the cycled number that takes the first place after the cycling (2) in this case, the number of inversions it had in the initial order being logically る-X. Let’s look at the second order now: it’s number of inversions now becomes [( (5) -1 ) - (る-X)] with (5) being the number of cards we are playing with and (る-X) being it’s number of initial inversions Explanation: when it comes to ( (5) - 1 ): this is the max number of inversions a single member ( (2) in our case) can do with the other members because a single member cannot have an inversion with itself. When it comes to the subtraction i did: that’s because when we did the cycling we took out member from last place to first place cancelling out all the inversions it initially had with other members (because they are in growing order now) AND the it now has an inversion with members it did not have inversions with initially, basically the number of inversions it has now has become the compliment of the initial number of inversions ( their sum is equal to (5) - 1) Knowing all this, We can now move on to a more general case with (n) number of cards placed horizontally which have る inversions and the section of cards that did not change order after the cycling has X inversions ( we can do this in a more general case because all the explanations i did apply there too): the number of inversions after the cycling is therefore X + [n-1 - (る-X)] = 2X + n -1 - る ( lets call it N ) Notice how 2X is ever therefore it does not determine the parity of N so the parity of N in comparison to る is only determined by the parity of n-1: N and る have the same parity if n-1 is even aka if n is odd and the opposite is true as well. So the sign of the permutation doesn’t change if n is odd but it changes if n is even. Tell me if i have a mistake because im not experienced with this type of math
This is a most amazing presentation of the most amazing theorem in Mathematics! A must see for all budding mathematicians. As an aside, you gave tantalizing glimpse of finite geometry. Why don't you make a video on these topics? Particularly, the prime power conjecture for finite projective planes is a sadly neglected topic in RU-vid. With its beautiful links with orthogonal Latin squares, this ought to be an eminently suitable candidate for a mathology video.
This fascinating proof put me in mind of a very impressive trick that one can do (if one has the time) with a normal pack of 52 playing cards. Put the cards in suit order and then deal the pack into four hands of 13 cards. Assuming, in bridge notation, you are South. Pick the piles of cards clockwise starting with west - hence WNES. Now deal the cards a second time (D2) and pick them up in the same way. Continue until after D13. Now examine the cards and you will find that they are back in the original order. My low grade graduate maths is not up to explaining this, and, of course, 4 is not prime, even though 13 is. But it is another of the wonders of theories of ordering things.
It's all about the last five minutes of the video. No, if you only watch them you will probably not understand anything at all, but these are really the time of the genius. You've done all the footwork and now you have to remember "why did I do this" and "how does all this - by now - easy stuff combine at all to help me in my original problem". More often than not also the question "what was the original question again?" pops up at this time. I remember how I in my thesis (in a completely different field, stochastics) was able to shorten a five page technical proof to a half page intuitive (and still correct) one and was immensely proud of myself. And then spent two weeks trying to remember how this achievement would help me at all.
37:25 this operation is the same as performing the permutation given by n 1 2 ... n-1 to the previous permutation Since this permutation clearly has n-1 inversions and signs of permutations multiply, when n is even it will change the sign and n is odd it will preserve the sign
Alternatively: The inversions in the cards that just moved over are obviously unaffected. The inversions involving the card that switched ends all get swapped. The parity of the number of swaps is therefore the parity of one less than the number of cards, so the sgn switches if the total is even and not if it is odd.
Thank you for making this AND taking the time to caption it! It made it so much easier for me to follow, I really liked this one and can't wait for permutations!
Answer to diagonal movement grid problem: I define our specific movement as, move 1 down and 1 right. When there's no room below, go to the top; when there's no room to right, go leftmost. The elements of the grid will be notated as (m,n) with the order being row,column. In square grids, it makes sense that both rows and columns will run out at exactly the same time. Then, once we've reached bottom-right, we'll go to top-left. But we started there; thus, there's an overlap. If there are common factors between the row and the column, it's basically a square grid times an integer to either the former or the latter, i.e their ratio is an integer (which I'll call "x"). In such cases, when the smaller one runs out, we'll teleport to either (0,n) or (m,0). After "x" number of teleportation, we will have reached the bottom-right all the same, and therefore get an overlap. If the ratio was non-integer, it would not reach the bottom right, and no overlap would've happened.
For a quick explanation of the sign of a permutation: You can represent each switch of two cards with an identity matrix with as many rows and columns as cards (15 cards means 15×15 matrix) EXCEPT that the corresponding rows are switched. This is an elementary matrix. The determinant of this matrix equals the sign of the switch. We know from linear algebra that switching two rows flips the sign of the determinant. The identity has a determinant of 1, so every switch flips its sign, and therefore the sigb of your permutation is either 1 or -1.
1:25 scares me. But it's indeed the only surviving "portrait" of Legendre, the mathematician (previous ones actually showed _Louis_ Legendre, a politician)
33:00 That ”Positively Sloped = Inversion” -trick really makes sense, for our Row-Up -> Column-Down -permutation; because, in any positively sloped pair, the upper card is the earlier one, in the row-wise order, and the later one, in the column-wise order (and vice versa, for the lower card); because the row-wise order is: ”Left -> Right; Top -> Bottom”, whereas the column-wise order is: ”Top -> Bottom; Left -> Right”. So, any card: A that’s up and right, comes before any other card: B that’s down and left, in the row-wise order; and vice versa, in the column-wise order: The down-&-left card: B comes before the up-&-right card: A. Also; in this Row-Up -> Column-Down -permutation, we’re essentially switching rows and columns, which means that the internal order of any such pair gets flipped. Then, because we started with the cards in natural (row-wise) order (meaning: No Inversions.), the flipping of the internal order of any such pair amounts to an inversion. Whereas; in any horizontally or vertically aligned, or negatively sloped pair, the card that comes earlier, in the row-wise order, also comes earlier, in the column-wise order; thus, no inversions would emerge. 😌
39:10 here is my wild geometric proof for the diagonal dealing problem. step 1 - cover the plane with an infinite grid of fundamental rectangles of area p*q where p & q are relatively prime. dont do the wrap around thing and instead draw diagonal lines and cover the plane with these rectangles and make a rule that any 2 points in the plane are "equal" if they are in the same part of the fundamental rectangle (if the diagonal line you are about to draw passes through one of the grid squares in this analogy you place a card in that grid square while diagonal dealing) step 2 - sit at the origin of the plane at coordinates 0,0 and find out how many "grid line intersection points" you can "see" (the rule is you can't see through a grid line intersection point, its an obstruction that will block your view; you can only see things if you draw lines connecting them to the origin without hitting one of the grid line intersection points, the theorem is you can only see the grid line intersection points of relatively prime coordinates when you are sitting at the origin, since otherwise your view will be blocked, this is an easy consequence of a result in a previous video about rational angles which is not hard to prove) step 3 - realize that if p & q were not relatively prime, your view would be blocked at least once by one of the grid points before you finished drawing the whole line. if you tried to draw the diagonal line just starting from the origin and going along the line with the required length you would have to overlap cards on each other corresponding to the number of times your view is blocked in this analogy
Most fantastic! It reminds me of the mysterious connection of quadratic reciprocity with the linking number of two knots (in 3-space), which Gauss found a formula for (in terms of an integral). The diagonal dealing certainly looks like a (p,q)-torus knot, and maybe the R and C dealings are just circle running inside (and "outside") the torus. I'm sure others have thought it all through.
What An hour? *hand hovers indecisively over play button* and it's a masterclass? *hand drifts away from the play button* and I need to do my flute practice *hand retreats to lap* (oh very funny, plz don't go there) OTOH it's a video with a funny bald German in it *hand approaches keyboard* but there are probably no cats in it being cute *hand falls to side* *crickets* *more crickets* reciprocity prime what the? wat IS dat? *Mathologer smiles impishly and wiggles the hook* Command voice:" Lock all targets and fire at will! All ahead Warp 6! Take us in Mr Sulu!" *Punches the big red button...*
Hi Burkard Polster. Thank you for this beautiful presentation of a very famous theorem. I'd like to point out that you look very similar of my all time favorite mathematician : Alexander Grothendieck. Grothendieck was a truly supreme mathematical genius of 20th century math whose contributions and influence are yet to be fully explored. I request you to bring out a video on any of his remarkable contributions.
16:26 the only squares mod 5 are 1 and 4. -1= 4(mod5) so the negative of the square 1 is also a square, and -4=1(mod5) so the negative of the square 4 is also a square, thus all the square on z/5z are squares. Q.E.D
This channel is what I needed in my life. I am an established (in the sense that I probably earn more than u, the hater) programmer, but I lack in basic math skills. I have watched a few more videos on this channel and they are absolutely treat! Thank you for doing this man, I wish you were my teacher (as in school days. You are, right now hehe). :D Subbed!
What a insight, it reignite my spirit to study the quadratic reciprocity again which I did not get it in my number theory course in my university study in 15 years ago.
At the begginig of the course I decided to make my final degree project about Basel's problem and Apery's theorem, and a few months later you posted your video about "power sums". Later on, I read Zagier's proof about Fermat's two square theorem, because I want an easy proof about the theorem and one month after that, you posted a video about it. Now, I'm taking a course on cryptography and two weeks ago I was studying quadratic residues and, of course, quadratic reciprocity law, and now I see your new video... I've started to believe that we are connected in some way... 😂😂😂 The video, as always, a truly wonderful present ❤️
Another gem 💎 of number theory! Only Mathologer could translate it into an accessible youtube video without compromising rigor! Gauss said of the proof, 'It tortured me'! Reading that I knew I wouldn't last one lemma before it, in my first encounter with it in Burton's Elementary Number Theory. Sure, the Preliminary Gauss's lemma and the main combinational argument of the proof was tough to understand, at the introductory level I first studied it an year ago😧. Now, most of that no longer dwells in my mind 😅 (forgotten! ), so imagine my ecstacy at this mathologer video😍! I'm sure it will help me comprehend it better than before, and I'll remember it longer (once I finish watching 😁)!
37:26 In cycling; only inversions, involving the right-most card, are affected; and, for n cards, the maximum number of them (let’s call it: I) is: I = n - 1; so, for odd n, I is even; and, for even n, I is odd. Furthermore; the cycling reverses the inversions (natural pairs become inversion-pairs, and inversion-pairs become natural pairs); hence, when the actual number of affected inversions before cycling is: i(1), the actual number of affected inversions after cycling is: i(2) = I - i(1). Thus; for an odd n, I is even; which means that i(1) and i(2) share their parity (both are even or both are odd); which, in turn, implies that the sign of the permutation doesn’t change: -1^i(1) = -1^i(2). On the other hand; for an even number of cards (n = 2k), the maximum number of affected inversions is odd: I = n - 1 = 2k - 1 = 2(k-1) + 1 = 2m + 1; and so, the actual numbers of inversions, before and after cycling, differ in parity (one is even, and the other one is odd: (i(1) = 2a ∧ i(2) = 2b + 1) ∨ (i(1) = 2a + 1 ∧ i(2) = 2b)); and thus, for even n, the sign of the permutation changes with cycling: -1^i(1) ≠ -1^i(2). *Q.E.D. 𑀩*
37:15 seeing a few solutions, mine is to use an alternative definition of the sign of a permutation as the number of "swaps of 2 elements" in the set its instantly clear from the definition why the number of elements in the set you are doing the permutation on will determine if the number of swaps is even or odd the trick is you have to see that a right shift is equal to starting all the way on the right and doing swaps for each pair of adjacent elements and working from right to left one card at a time
This video is quite the Magnum Opus! It makes a result from deep in the heart (bowels?) of mathematics accessible to mere mortals, and introduces a bunch of mathematical constructs (squares in Zn, rings, sign of a permutation) along the way. For me, watching this video felt like being a tourist on an eloquent expertly-guided tour of a hidden room inside a massive museum. I am left in awe of the inventiveness of the mathematical minds of yore and supremely appreciative of Mathologer's efforts to spread his enthusiasm for mathematics. In response to Mathologer's query of what worked for me, with the first viewing I felt I was on top of the material until maybe the last 10 minutes. I expect that a second viewing will fix that, so... Congratulations Mathologer! I think you achieved your goal.
The ordering property is not mysterious. Apply a reodering first, then your permutation, then the inverse of the reordering. The inverse of a reordering has the same parity as the reordering (inverse of a product of two-cycles is the same product but backwards), so the final result has the same parity as the original permutation.
Thank you so much for your effort in creating these enjoyable and accessible videos! As a technical writer who is entering the world of mathematics late, I find these really help me to internalize so much of what I need to go study. Cheers, Rick Lehtinen
These mini rings are what music theorists call modifications. Basically, you think of a clock with n values and you count around the clock face until you find the remainder
Since you asked in the video.... I think i grasped more than half of what you said and understood a fairly continuous thread of ideas from beginning to end. I think I could get it all with a few more viewings. My skill level is weak freshman, unused for 4 decades. Btw did you notice that the ideas presented have strong links to major unanswered questions in math?
7:22 Proof Commutative Law for any Z/n: Since Z/n is just Z mod n for any whole number, we just have to add a+b and divide by n, then take the remainder, and that's our answer. Let C be the sum of a and b. But no matter what order you add whole numbers a and b, you always get the same number C by the ordinary commutative law of addition. So you will divide the same number by n no matter what order you add a and b in. Distributive Law for Z/n: The argument is basically the same, except you use the ordinary Distributive Law. You get the same number, which we will now call D, on each side of that second equation, so you will always be doing the operation D/n. This completes my proof for any modular ring Z/n being valid for both equations. QED. Let me know of there is any error in this logic.
Or you could use the fact that a commutative ring quotient out an ideal is also a commutative ring. Z/n is the same as Z/(n), where (n) is the ideal generated by n.
37:30 one of the pairs (a,b) and (b,a) is an inversion. Cycling the permutation reverses each pair formed with n. There are n-1 pairs so the sign changes n-1 times, no change if odd, sign changes if even.