The hardest "What comes next?" (Euler's pentagonal formula)

Video Statistics and Information

Video
Captions Word Cloud
Reddit Comments

Euler's pentagonal number formula was one of the first things at the crossroads of analysis, combinatorics, and number theory that really wowed me. It's pretty wacky that the pentagonal numbers end up relating to the partition function in such a convenient way.

👍︎︎ 91 👤︎︎ u/dxdydz_dV 📅︎︎ Oct 17 2020 🗫︎ replies

The hardest "What comes next?"

3, 5, 17, 257, 65537, ??

👍︎︎ 45 👤︎︎ u/TLDM 📅︎︎ Oct 17 2020 🗫︎ replies

Never knew there was a closed form for the partition function. What a beast of an equation that is yet so elegant.

https://i.imgur.com/4eXyEk8.png

👍︎︎ 30 👤︎︎ u/NitroXSC 📅︎︎ Oct 17 2020 🗫︎ replies

8, 6, 7, 5, 3, 0, ?

👍︎︎ 5 👤︎︎ u/eigenfood 📅︎︎ Oct 17 2020 🗫︎ replies

Is it 13?

👍︎︎ 5 👤︎︎ u/PapasConKetchup45 📅︎︎ Oct 17 2020 🗫︎ replies

involutions are so cool. zagier's one line proof also depends on them!

👍︎︎ 3 👤︎︎ u/_selfishPersonReborn 📅︎︎ Oct 18 2020 🗫︎ replies

I don't understand the bonus "what comes next" problem.... He shows exactly how to compute the next one. I mean if we follow the rules for the first 4 then we get a clear answer. Are we supposed to find an alternative rule that "breaks" for 5?

Or is he asking us to find a formula or "machine" to calculate the answers?

👍︎︎ 2 👤︎︎ u/mavaction 📅︎︎ Oct 17 2020 🗫︎ replies

I always love Mathologer

👍︎︎ 2 👤︎︎ u/KinaSho 📅︎︎ Oct 18 2020 🗫︎ replies

mathologer is god

👍︎︎ 2 👤︎︎ u/yaboytomsta 📅︎︎ Oct 18 2020 🗫︎ replies
Captions
Welcome to another Mathologer video okay  to begin, thank you very much Jesko Mathis   and Aaron Prince for your very funny comments on  my sun deprived complexion. Basically Nosferatu   right? It's these comments that inspired this  brand new Mathologer t-shirt that you all will   be looking at for the rest of this video. Like it?  Okay, so you've all been tortured with what's next   question since primary school right? 1 2 4 8 16  what comes next? Well of course the answer is   32. Right? Well, not necessarily. Since the  pattern doesn't have to be doubling it could   be something totally different. Have a look at  this. Put equally spaced dots around a circle.   First just one dot, then two, then three four  five and so on now connect these dots in all   possible ways. There and let's count the number  of regions that materialize. For the first circle   there is just one region. Next there are two  regions. 4 8 and 16. And now what comes next?   Well, just count and you'll find that the next  number of regions is 30 and not 32. Surprised,   well, maybe not, at least some of you will already  have seen this cute devilishly misleading pattern   previously. It's an absolute classic and an  absolute must-know of anybody interested in maths.   What this shows is that when it comes to  answering what next questions you should   never jump to conclusions. Anyway if the rule is  doubling then we know exactly where we're going,   and we can really kill this question by saying  that the general formula for the nth term of   this sequence is 2 to the power of n. If on the  other hand the rule is number of circle regions,   then the killing formula is surprisingly  complicated. It was actually only found in 1997   by the mathematicians Bjorn Poonen and Michael  Rubinstein. This killing formula looks like this.   Ooh, scary. If you're interested in the details,  check out the description of this video.   For hundreds of years another seemingly very  simple what's next question has provided   mathematical mega stars like Euler  and Ramanujan with many a sleepless   night and led to some of the absolute  highlights of their mathematical careers.   That insomnia-inducing question and some of those  highlights are the subject of today's video.   Well, that was pretty, right? But what actually  happened? Well, what you just witnessed was an   animation of the eight different ways of writing  four as a sum of positive integers. So there they   are again very nice. Now how many different  ways are there to partition an arbitrary   positive integer like this? Obviously not  enough information to venture a guess, right?   So let's list the different partitions for small  numbers and see whether a pattern jumps out at us.   There, that's the partitions for the  small numbers. Okay, let's count.   Obviously there's only one  way to express the number one.   For two there are two ways, just two and one  plus one. Okay for three, there are four ways   and as we've already seen there are exactly  eight ways to partition the number four.   Okay, one, two, four, eight so obviously the  next one is 16 right? Or am I trying to trick   you? Well, let me show you a very ingenious  way to answer this question once and for all.   At the bottom there are four blocks  which represent the number four   that we are chopping up. Notice that there  are three gaps between those four blocks   there let me show you what happens when we  open and close these gaps in various ways,   can you see it? Of course you can. The  different ways of splitting up the integer four   corresponds to the different ways of  opening and closing those three gaps.   But how many ways are there of doing that?  Well each gap is either open or closed so   two possibilities for each gap. And there  are three gaps which gives a total of two   times two times two is two to the power  of three is equal to eight different ways.   So I didn't trick you, unless I tricked  you by making you think I was tricking you.   Looks are not deceiving one two four,  eight and what's next? Well in this case   two times 2 times 2 times 2 is equal to 16  then 32 and so on. For a general integer n   there is 2 to the power of n minus 1 ways of  partitioning it. Easy and super pretty right? Now   did you enjoy this warm-up exercise?  Well then you're ready for the real deal.   Okay time for the killer question. Look  again at the lists of partitions over there.   Did it bother you that there's a  lot of repetition in those lists?   There two plus one and one plus two they're  basically the same right? And if we don't   count these two partitions as different, then the  number three has only three different partitions.   What about the partitions of four? Okay get rid  of the repetitions there and instead of eight   partitions we end up with only five really  different partitions of the number four.   There, so how to think about this refined list of  partitions? Well as you'll see it's not that easy.   But quick and dirty you can think of the  collection of all truly different partitions   are some sort of super duper self-similar fractal  thing something like the Mandelbrot set for   numbers. Well okay a bit click-baity but anyway.  Can you see it? Even a superficial look at sets of   partitions reveals some patterns that repeat over  and over and that's just the obvious tip of an   absolutely immense iceberg of complex patterns.  This structure has many important surprising   connections to other parts of mathematics computer  science and physics but for now let's focus on   capturing the hidden patterns in the numbers of  these partitions. Okay let's go. One two three   and five partitions what's next? Any guesses? You  can probably think of at least a couple of easy   patterns that fit so far but it's definitely  not enough information for an educated guess.   So let's throw in a couple more numbers. What's  next? Well there are seven ways to partition five.   The plot thickens. Still got your guess ready?  Well let's throw in the next number and it is   11. Aha can you see it now? Well 2 3 5 7 11 are  all prime numbers and that one at the beginning   is sort of an honorary prime. So what's the next  prime number? Well, 13 of course. Well that wasn't   so hard was it? Well, not so fast. I hate to break  the news to you but actually the next number is   15. Damn okay so there goes our prime numbers  conjecture. So what is going on here? What   if we add in more of the sequence? Anything  now? No okay time to send out the bat signal   there he is batman or superman or maths man.  Whatever all Mathologerers will recognise   the guy with the towel hat. Leonard Euler  one of the mega stars of maths. He was the   first to really investigate partitions  and these partition numbers up there   and Euler discovered some truly amazing  patterns in the sequence of partition numbers.   Want to see some of Euler’s genius again?  Well of course you do. Okay so let's go.   At first when only these four numbers were visible  did you perhaps think of another sequence. One   two three five that's also the start of that  other super famous sequence the Fibonacci sequence   right? One plus two is three two plus three  is five. Now let me ask you a weird question:   that one in front that's the partition number for  one right? Now if your life depended on assigning   a partition number to zero what partition number  would you assign to it. Make a choice now. What   did you decide on? My bet is that you chose well  either 0 or 1. Let's go for one which is also   the official choice and makes for an even longer  Fibonacci start to our partition number sequence.   Okay, let's intone the Fibonacci mantra:  one plus one is two, two plus one is three,   three plus two is five, five plus three is eight,  but we want seven. Hmm. Well, we are off by one,   but we can save things by subtracting the very  first one on the left: five plus three is eight   minus one is seven. So what i’m saying is that  maybe to get the next number in the sequence you   always have to add the last number and the  second last number just like with Fibonacci   but then you also have to always subtract the  fifth large number. Okay let's test this theory.   7 plus 5 that's 12 minus 1 is 11 works. Next 11  plus 7 is 18 minus 2 is 16 and not 15. Damn again.   Well, it's not all lost yet. Let's just adjust our  rule one more time and also minus the one at the   beginning. There now it works. 11 plus 7 minus 2  minus 1 that's 15. Next 15 plus 11 26 minus 3 23   minus 1 is 22 works. 22 plus 15 that's 37 minus 5  that's 32 minus 2 that's 30. Magic. Okay next. 30   22 yeah, that's 42 works again. We definitely seem  to be on to something. And next. Yes works again.   Is that it? Is that the real rule? What  do you think? Yeeee... Sorry but no :)   okay 56 plus 42 minus 15 minus 7 is 76, one  short. But by now you can probably guess   how we're going to fix things right? We simply  add the one in front. And then what? Well,   most likely we just keep shifting until we  encounter another mismatch, chuck in another   plus or minus to adjust at the end and repeat.  And believe it or not this crazy scheme actually   turns out to be exactly what happens. Overall you  have to keep adding pluses and minuses forever.   Also it's always two pluses followed by two  minuses, followed by two pluses and so on.   Well that's great but for this pattern  to actually be useful, for example for   calculating a partition number we don't know yet  based on the ones preceding it we have to know in   advance how exactly those pluses and minuses are  positioned. So let's continue our pattern hunt.   Okay so to calculate a partition number we add  the first last number, then the second last   number then we minus the fifth large number.  Okay then we minus the seventh last number,   then we add the twelfths last number and so on.  Okay so we end up with the sequence of position   numbers for the pluses and minuses that we have  to 'what's next' well when is this pattern hunt   going to end? Soon promise :) anyway here  are the first couple of position numbers.   At first glance the sequence of numbers looks just  as mysterious as the one we started with. However   after staring at this sequence for a minute or  two or three many people will notice something   remarkable. Actually maybe give this a go. Stop  the video at this point and try to spot the   pattern. I’ll wait. Want a hint? Yes? Well, ponder  the differences between consecutive numbers.   What are those differences? Well the  difference between two and one is one. Okay   here the difference is three. Okay  seven minus five that's two and so on.   Can you see the pattern? No? No problem? Let  me give you another hint. That's a big hint.   You can all see the pattern now right? There  in the orange one two three four five. Whoever   has trouble with this pattern should change  channels now. And in the green three five   seven nine and so on that's the odd numbers. How  super nice is that? But also how super bizarre.   How come these two intertwined primary school  patterns make an appearance here? Well we'll   get to that. Anyway using these two interleaved  patterns it's now easy to extend the sequence   of position numbers forever. For example the  difference between the next position number and 70   is 7 and so the next position number is 70 plus  7 is equal to 77. And what's next after that?   Well the next green odd number is 15 and so the  next number in the sequence is 77 plus 15 which is   92. Patterns within patterns within patterns.  How amazing is all this? And we have not even   started drilling into the why. To summarize here's  how we can build the partition number sequence   thanks to the genius of my  all-time favourite mathematician   Leonard Euler. Make up a row of squares  that continues forever to the right.   We'll write the partition numbers onto these  squares. We put in the first one straight away.   Then we make up a second row of squares that  extends forever to the left. There that row of   squares we label with the pluses and minuses.  Then we line up things at the ends like this   and then we calculate one partition number  after the other based on the ones that   we've already calculated. So the next one is  plus one so it's one. One plus one is two.   Two plus one is three. Three plus two is five  and five plus three is eight minus one is seven,   and so on. There it's like a machine  right calculating these numbers.   So challenge for the coding experts among you:  based only on what we've discovered so far   compute the 666th partition number.  Leave your answers in the comments.   As I already mentioned the theory of partitions  has many important and surprising connections   in and outside mathematics. Just as an example  here's a very unexpected maths connection which   is established by slightly tweaking Euler’s  incredible partition number machine up there.   Let me explain. The tweaked machine works exactly  like the original except that the first red   entry up there increases by one every time we  move the bottom row of squares. Have a look.   Okay line up again now plus 1 as usual. Now  this thing actually goes up like a counter.   Okay 2 plus 1 is 3. Okay counter goes up again  doesn't really matter but 1 plus 3 is four.   Okay three plus four is seven. Okay four  plus seven minus five is six and so on.   Have a look at the sequence produced: one three  four seven, now it plummets down to six then   twelve then down to eight again and so on. This  sequence jumps around like crazy, really insane.   But believe it or not there is a beautiful  pattern hiding there and the pattern is this:   take the value of the counter in this case 12  and list all its factors. One two three four   six and twelve that's all the factors of twelve.  Now add up these factors one plus two that's   three plus three is six plus four is ten plus  six is sixteen plus twelve is twenty eight.   There 28 in the output of the machine at this  point and that always works. The sequence up   there is the sequence of the factor sums of the  integers how absolutely mind-bogglingly crazy   is that. Why should writing a number as a sum of  integers have anything to do with the sum of its   factors. Marvellous. Also just think about it.  Which numbers are special in terms of having   the least number of factors? The least number  of factors? Yep the primes. A prime number p   has only two factors, the number itself and  one. Can you tell where i’m going with this?   Well what this means is that we can use this  modified machine as a prime detector, we can use   it to check whether a number is prime. How? Well,  just work the machine until the counter shows the   number we are interested in. Then our number is  prime if the output of the machine at this point   is one greater than our number. Here's an example.  Let's play dumb and pretend we don't know whether   or not seven is prime? So spool back to when the  counter was showing seven. Well the output is   eight so one greater than the counter and so seven  is a prime. How about that. Work the machine.   Okay eight in the counter is not prime because  the output 15 is more than one greater than 8.   9 it's not prime because of the  same reasons. 10 not prime but 11   is prime because the output is 12. One  greater now isn't this a magic machine   even Euler himself couldn't believe his eyes when  he first discovered this wonderful connection   between prime numbers and partitions. Just imagine  being the first person to discover something as   amazing as this. Can you imagine the aha moment?  Today i’ll be busy disassembling Euler’s original   machine for you and sadly won't have the time to  also delve into the guts of this modified machine   but as usual for the super keen among you i’ve  included some links in the description where you   can further explore this connection and some of  the other things i’ll only mention in passing.   Okay so we saw that it's easy to calculate the  position numbers of the pluses and minuses using   the simple orange green pattern and of course  Euler would have spotted that pattern straight   away. Even more so as a real maths pro he  would have recognized that this position   number sequence is just the sequence of the  so-called pentagonal numbers. Let me explain.   Pentagonal numbers. Well you may not realize  it but you already know the triangular numbers   and the square numbers. Here are the  first couple of triangular numbers.   So the triangular numbers are just the numbers of  dots in the different equivalent triangle arrays.   In fact we've already encountered these  numbers in many other mathematical videos   these numbers are just the different 1  plus 2 plus 3 plus et cetera sums. For   example the triangular number 15 is just  the sum 1 plus 2 plus 3 plus 4 plus 5   right? Just last video we had it. So let's  quickly again figure out the formula for   the nth triangular number. The number of  dots in the triangular array with side n   so the nth triangular number is just n times n  plus one divided by two. All regular Mathologerers   would probably already have committed this  formula to memory. Comes up all the time.   As I said triangular numbers, tick. What  about square numbers? Well pretty obvious 1   4 9 16 and so on. Finally pentagonal numbers.  Now quickly let's also derive the formula for   the nth pentgonal number. We're really on a roll  today. Now why are we doing this. Well because   that's what we're doing here on Mathologer.  We do real maths which means we prove things.   Okay that's the formula for the  pentagonal numbers. Spectacular isn't it?   But wait who forgot why we are interested in these  numbers. Confess you don't remember. Because...   Because they are supposed to be the key to the  position numbers for the pluses and minuses.   And sure enough there they are. Amazing right.   What do pentagons have to do with partitions?  Apart from both words starting with p?   And why do we get only half the numbers? What  about the other half? Ready for another surprise?   Well the other numbers is what you get when you  plug in the negative integers into the formula.   Okay let's check. Plug in minus one autopilot  okay shuffle shuffle shuffle shuffle   four divided by two, yep that's the two that fills  the first gap between the pentagonal numbers.   Now plugging in minus two we get seven. You can  check that and so on fantastic. Challenge for   the keen among you. Use this formula to prove that  the sequence of differences really always follows   the simple pattern that we discovered earlier.  As usual write up your proofs in the comment.   And a really easy fun challenge: calculate the  36th triangular number. Oh and for later i’ll   call the pink numbers the pentagonal numbers  and the blue ones the other pentagonal numbers.   So how are you enjoying this topic so far? In  the rest of the video i’ll explain why Euler’s   partition number machine works, why the pentagonal  numbers are the key to this mystery, etc. For this   we'll actually have to look into the nature of the  partitions themselves. But before I dive into the   guts of things let me quickly tell you a little  bit about what came after Euler’s discoveries.   I’ve mentioned Ramanujan at the very  beginning. Where does he enter the picture?   Well as we've seen there is a nice pentagonal  formula for the position numbers of the pluses   and minuses. So what about a nice formula for the  partition numbers themselves up there? Well that   turns out to be a real killer. And that it is  a killer is really not that surprising right?   Basically to get the growth rule for the partition  numbers we started with the simple growth rule for   the Fibonacci numbers. There the Fibonacci  numbers. And then we refined this Fibonacci   growth rule infinitely often. I already derived  the formula for the n Fibonacci number for you   in previous videos and it looks like this. Plug in  zero it spits out the first Fibonacci number one,   plug in one it spits out the  second one, then the two and so on.   That's already pretty complicated and amazing. Now  imagine infinitely more complicated and infinitely   more amazing and you get the formula  for the partition numbers.well actually   you don't have to imagine anything let me  just show you what this formula looks like.   Again plug in zero it spits out one plug in one  it spits out one then two and so on. But of course   this is a totally insane formula it's not even  clear at all how you would go about evaluating it.   Also it's swarming with pi's e's i's infinity  hyperbolic functions a derivative and so on.   And this formula is due to Ramanujan. Well not  quite he had the basic idea and then developed   it together with hardy when he was living in  England. The finishing touches were applied by   the mathematician Rademacher 20 years later.  I won't have the time to say much about this   amazing formula in this video. Hopefully another  time. But at least i’d like to give you a glimpse   of the incredible power of this formula by  showing you what even a really really really   tiny part of it can do. To get to this tiny  part throw away everything except for this.   Not much left right? Now differentiate and  express the hyperbolic functions that pop up   in terms of exponential functions. Don't worry  about the big words okay. And you get this.   Throw away the last three small terms and you're  left with this. The minus 1 over 24 doesn't do   much either so let's throw that away too. And so  eventually you get this. All right. After all this   throwing away and simplifying what's left is this  very famous approximation of the partition number   function that is still amazingly accurate. Let  me show you just how good this approximation is.   Okay on top is the actual function that spits  out the partition numbers and at the bottom   is our Ramanujan approximation. Actually come to  think of it since the partition numbers grow in a   way that is a refinement of the Fibonacci growth  process, our Fibonacci formula should also give   a fairly good approximation to p(n) right?  Okay well let's first compare red with blue.   Not a bad fit but see what happens when  we zoom out? Things really appear almost   indistinguishable at this magnification. Just to  put things into perspective to see just how good   Ramanujan's simple formula captures our partition  monster i’ll now add the Fibonacci approximation   there. There huge difference. Just for emphasis  here at n is equal to 26 Fibonacci is already 80   times as large as the partition function. So while  Fibonacci is really way off very quickly Ramanujan   tracks incredibly well forever and ever. Really  nice but also really really tricky to prove.   But if you think that this formula is the final  word on the partition function's 'what's next'   think again. Even today we still discover many new  incredible things about the sequence of numbers   and since the plan is to keep making  these videos until i’m 100 years old   i’m pretty sure i’ll talk about some of these  remarkable discoveries in future videos.   Now for the why. To understand why those  pentagonal numbers make an appearance we really   have to have a look at integer partitions. In fact  let's have a look at integer partitions in a very   visual way, in terms of dots. Okay here again is  our house shaped deformed array of dots for the   pentagonal number 35. Let's deform this array of  dots further like this. Then we can interpret this   array as a graphical representation of a special  partition of 35. There 9 dots in the first row,   8 in the second and so on. 35 is 9 plus 8 plus  7 plus 6 plus 5. Not bad huh? Very pretty. In   general we can represent any of the partitions  we are counting in this video in this way.   Since the order of the summands doesn't matter  we'll always order the corresponding rows of   dots from largest to smallest going from top  to bottom. These dot diagrams of partitions   are usually called Ferrers diagrams named  after the mathematician Norman Ferrers.   That him Norman Ferrers who apart from being  a mathematician was also one of the vice   chancellors of Cambridge university. Here are  a couple of other examples of Ferrers diagrams.   It may already have occurred to you that there  is a second way to interpret a Ferrers diagram   as a partition if we consider it made up of  columns instead of rows right? There are nine   dots in the first column 6 in the second and  so on which gives us a second partition of 35.   Very interesting isn't it. So there's  this hidden connection between different   partitions of a number established by these  diagrams. In fact there are lots and lots   of other beautiful relationships  hiding in partitions of integers.   Finding and exploiting these hidden relationships  leads to deep insights about partitions and their   applications in maths and elsewhere. I’ll now  show you one such hidden relationship which was   discovered by Euler and which is the key to our  recursion formula. For the partition numbers this   relationship is called Euler’s pentagonal number  theorem. So pentagonal finally. So in what follows   we'll focus on the default interpretation of  Ferrers diagrams in terms of rows. So at least   for the rest of this video forget about the  second interpretation in terms of columns.   Okay I’ll call a partition even if it contains an  even number of summands and I call it odd if it   contains an odd number of summands the example  over there contains nine summands and so it is   odd. The pentagonal number theorem focuses  on the distinct partitions, those partitions   of a number that consist of distinct summands. In  other words the pentagonal number theorem is about   Ferrers diagrams all of whose rows are of  different lengths. The example over there   is not distinct because the fives and the ones  repeat right? Okay let me show you an example   without repetitions a distinct one. There the  summands of this partition are all different   and of course the pentagonal partition  we started with is also of this type.   Okay now Euler proved that in general the  number of even distinct partitions of an   integer is equal to the number of odd distinct  partitions. Again in general the number of   even distinct partitions of an integer is  equal to the number of odd distinct partitions.   But there are exceptions to this rule. And those  exceptions occur exactly when the integer we are   partitioning is pentagonal. Let's have a closer  look how this pans out for the smallest integers.   Okay we are focusing on the partitions without  repeated summands. So let's throw away all the   partitions with repeated summands, which is  actually most of them. Gone. Okay now highlight   the odd partitions in red and the even ones in  green. There I said that in most cases there will   be the same number of odd distinct partitions as  there are even. Distinct partitions. And even in   the short list half the cases are of this type.  There the same number of odd as even partitions.   Let's throw these away and focus on the  exceptions. Supposedly these exceptions should be   pentagonal numbers and they are. So let's extend  this list of exceptions a bit. There. And this   really works out. The numbers of odd and evens  are different for all our pentagonal numbers.   And how exactly these differences pan out  also meshes in with the pluses and minuses   that go with the pentagonal numbers. Remember  those pluses and minuses? If there is one more   red then green there's a plus and if there  is one more green and red there's a minus.   Another way of expressing this is to say that for  every integer the difference between the number of   odd and even distinct partitions is zero. Right?  So if they're the same then the difference is   zero obviously. Unless the integer is one of the  pentagonal numbers in which case the difference   is one if the pentagonal number comes with a  plus and minus one if it comes with a minus.   Okay but now for the why. Well there's a  really beautiful visual proof of Euler’s   pentagonal number theorem that the American  mathematician fabian franklin published in   1881. It's been called the first serious  piece of mathematics that came out of America   by some very snobbish or  European mathematician of course.   Here's one of our distinct partitions.  There are two features we'll focus on.   First the bottom row. Then there is the diagonal.  The diagonal starts in the upper right corner   and then it continues at 45 degrees  until we run out of dots in a line.   So in this case the diagonal is  just two dots long and the bottom   is three dots long. Here two more examples.  In the second example the bottom is shorter   than the diagonal and in the third  example they are of equal lengths.   Now we'll transform these partitions according to  the following ingenious rule. If the diagonal is   shorter than the bottom as in the top diagram then  we make the diagonal the new bottom like this.   If the diagonal is not shorter  like in the other two example   then we make the bottom into  the new diagonal like this.   Three observations. First we only move dots so  before and after we're dealing with partitions   of the same number. Second the transformation  always either adds one row or removes one row.   So it turns even partitions into odd partitions  and vice versa. Third before and after we're   dealing with distinct partitions. Okay now let's  apply the transformation to the new partitions.   Notice that in the bottom example the diagonal and  the bottom have a dot in common. But it's fine the   rule still applies. Now let's transform. What was  the rule again? If the diagonal is shorter we move   the diagonal. Well the diagonal is now shorter  in the second and third examples. Here we go.   In the top example the diagonal is not shorter  than the bottom and so we move the bottom.   Can you see what happened. No? Well  we're back where we started from. So   starting with any distinct partition,  applying the transformation twice   gets us back to the partition we started with.  This means the transformation splits the distinct   partitions of a certain number into pairs. Every  pair consists of one even partition on the left   and one odd partition on the right and these two  partitions are swapped by the transformation.   And the existence of such a pairing implies that  if there are no exceptions, which is the case for   most integers, then there are exactly as many  odd distinct partitions as there are even ones.   And this is exactly what we wanted  to show. Now there happen to be two   types of exceptions. Where would you  expect those exceptions to be lurking?   Well there was this case where the diagonal  and the bottom had a point in common. Remember   if you think about it for a second that's really  the only case where something can go wrong.   Actually if as in this example there's a big  difference between the lengths of the bottom   and the diagonal having a point in common is  actually not a problem. But now let's shrink   this difference in lengths and see what happens.  Okay so as we've seen this works no problem.   There no problem. What about this? The diagonal is  still shorter so it still moves. Still no problem.   Shorten the bottom one more time okay.  At this point the diagonal is just one   shorter than the bottom. Anyway  it's still shorter. So it moves.   Aha there's the problem. The resulting  partition has a doubled up row at the bottom   and so is no longer distinct. This  is the first type of exception.   Shorten the bottom one more time. Now the diagonal  and bottom are equally long. Since the diagonal is   no longer shorter the bottom moves. Ooh that  doesn't work at all. So the bottom and the   diagonal being of equal lengths is the second time  of exception. In fact in terms of exceptions the   two types we've just encountered are all there is.  Shorten things further and things start working   again. And nice nice nice the second time of  exception are just the pentagonal partitions   and now it would be great if those other  exceptions correspond to those pentagonal   numbers of the second type. And they do. Let's  have a look to get the second type of exception.   We start with a pentagonal diagram and then  extend it by doubling up the diagonals like this.   Right this is going the other way as we did  before. And yes it works. There two points, seven   points, okay 15. Great now i’ll leave it as an  easy exercise for the keen ones among you to show   that the number of dots in these special Ferrers  diagrams are just these other pentagonal numbers.   And this completes the proof of the pentagonal  number theorem. Super pretty don't you think?   Again for numbers that are not pentagonal there  are no exceptions to the pairing and so there   are an equal amount of odd and even distinct  partitions. For any pentagonal number there's one   exception to the pairing the pentagonal partition  up there and so the difference between the amount   of odd and even distinct partitions is one or  minus one depending on whether the exception is   odd or even. Okay at this point you're probably  all pretty exhausted, eyes are glazing over,   brains are about to explode and you are just happy  to take my word for it that Euler’s pentagonal   number theorem now somehow translates into Euler’s  machine, that amazing recursion formula. But   for the super keen among you let me at least  quickly sketch how we get there by focusing   on one particular instance of the recursion  formula. If you really want to proceed maybe   now is a good time to steel yourself by taking  a bit of a break, grabbing a cup of coffee and   then rejoin me for the final dash up the serious  mathematical mountain that we're scaling today.   Or if you've seen enough for now, skip straight to  the end for another incredible what's next puzzle.   Okay, so you really want to find out  about the last piece of the puzzle.   Very good I'm proud of you. So let's focus  on this instance of the recursion formula.   There, in symbols the numbers that  actually do something here are these.   There, p(1), the first partition number,  p(6), the sixth partition number, and so   on. And these numbers are supposedly connected  like this: p(13) is equal to p(12) plus p(11)   minus minus plus. Okay so how does this identity  follow from the pentagonal number theorem?   Ready for our final mathematical magic trick for  today? Okay, p(13), this is about partitioning 13.   So let's take 13 dots, split those 13 dots into  two groups of any size. For example, a group of   size six and one of size seven. Six plus seven is  thirteen. Pick an arbitrary partition of six, say   two plus two plus one plus one doesn't have to  be distinct any partition whatsoever. There two   plus two plus one plus one and pick a distinct  partition of seven say four plus two plus one.   There that one on the right is  distinct. Now focus on the bottom rows.   Now we'll do some more ingenious transforming  of diagrams. In particular we'll move one of the   bottom rows to the respective other side. Can you  guess which bottom row will move in this example?   Right or left? What we want at the end of the  move is another arbitrary one on the left and   another distinct one on the right. So which  one moves? Well pretty obvious: the rule is   if the bottom row on the left is shorter it moves  otherwise the bottom row on the right moves.   In this example the bottom row on the left is  not shorter and so the one on the right moves.   And yes at the end of the transformation we are  again facing an arbitrary partition on the left   and a distinct one on the right. Plus the parity  of the one on the right will have changed. And   unleashing the transformation on the new pair will  get us back to the starting pair. It should all be   a bit familiar right. Now this new transformation  pairs up our pairs into super pairs.   Like that right. What's super nice about this  super pairing is that there are no exceptions.   This means that there are exactly as many pairs  with an odd distinct partition as there are pairs   with an even distinct partition. Always. Very  interesting isn't it? But how are we going to   use this fact? Well just follow our nose. How  many pairs are there with an odd distinct part?   Well for the split into six dots on the  left and seven dots on the right that   we've been focusing on so far there are p(6)  arbitrary partitions on the left to choose from   and the number of possible odd distinct partitions  of seven on the right is well let's call it 0(7).   And so there are a total of p(6) times o(7)  pairs with 6 on the left and 7 on the right.   Now we can also split our  13 dots into 5 and 8 dots   which gives this many extra pairs  with an odd distinct partition.   So to get the number we are really after  the number of all pairs with an odd distinct   partition we simply split 13 in all possible  ways and then add up the corresponding products.   And then the existence of our super  pairing of pairs says that this number   is equal to the corresponding number of  pairs with an even distinct partition.   Anyway don't be scared in a moment most of what  you see over there will vanish into thin air.   Anyway subtract everything on the right from the  stuff on the left. There. And this is where it   all comes together. Can you see it? Well  maybe pause the video again for a moment.   Okay well euler's pentagonal number theorem tells  us that the differences in the blue brackets   are usually equal to zero except if we're  dealing with one of those pentagonal exceptions   right. At the top 13 is not a pentagonal number  and so o(13) minus e(13) the difference between   the numbers of odd distinct partitions  and even distinct partitions of 13 is 0.   And the same is true for all those  other non-pentagonal numbers.   There. This means that all the highlighted  summamds are 0, vanish into thin air.   And now the pentagonal number theorem also tells  us that all those remaining differences in the   blue brackets are all either equal to one  or minus one. Looks very promising doesn't   it? So let's keep charging ahead. The bottom  row is a bit special. O(0) hmm well obviously   with zero being an even number there are no odd  distinct partitions of zero and so o(0) is zero.   On the other hand e(0) is 1, counting that one  way to have nothing on the distinct side and all   13 points on the arbitrary side. Okay the rest  of the differences follow the pattern that we   established earlier: two plus ones followed  by two minus ones etc as far as it goes.   And that's it. We just proved that euler's machine  really does calculate p(13) correctly. Well that   was quite a bit of work just for checking  p(13) but of course the argument that I   showed you is completely general and also shows  that euler's machine does the right thing for   all the infinitely many partition  numbers, not just p(13).   The power and magic of  math(s). Wonderful isn't it?   Well that last dash up the summit  was quite something wasn't it?   Just in case you couldn't quite  keep up with the insane pace I'd say   just give it another go at half speed and really  take it one step at a time. Absolutely worth it.   I hope you enjoyed this mathematical tour de  force. As usual let me know what worked and what   didn't work for you in the comments and ask for  clarification if you did not understand something.   Anyway that's it from me for today except, as  promised here's another super nice what comes   next problem for you to puzzle over. It will be  interesting how many of you figure this one out   and whether anybody will be  able to justify their guess.   What, you're still here? Amazing!   Okay i might as well show you something else that  i find really pretty. Ready? So as we've seen,   the partition numbers 1 2 5 7 12, and so on,  are just the numbers of dots in these special   ferrers diagrams there. Focusing on the shape  of these diagrams it's also really easy to see   where the bizarre pattern in the differences  between adjacent partition numbers comes from.   Remember that yellow - green pattern. There that  intertwining of the orange 1 2 3 4 5, and so on,   and the green odd numbers, 3 5 7 and so on. Here's  how you can see at a glance, actually two glances,   where this intertwined pattern comes from.  First the differences between these pairs are:   one two three four, and so on. Really  obvious that this will continue forever   when you look at it this way. Second,  the difference between these pairs are   3 5 7 9 dots, and so on. Also super pretty and  super obvious why we get the odd numbers here,   isn't it? If you'd like to tell me that you  really made it all the way here please just   leave the comment "i made it to the very end".  And this is really it for today until next time :)
Info
Channel: Mathologer
Views: 333,867
Rating: 4.9474344 out of 5
Keywords: Euler, Ramanujan, pentagonal number, triangular number
Id: iJ8pnCO0nTY
Channel Id: undefined
Length: 53min 33sec (3213 seconds)
Published: Sat Oct 17 2020
Related Videos
Note
Please note that this website is currently a work in progress! Lots of interesting data and statistics to come.