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 :)
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.
3, 5, 17, 257, 65537, ??
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
8, 6, 7, 5, 3, 0, ?
Is it 13?
involutions are so cool. zagier's one line proof also depends on them!
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?
I always love Mathologer
mathologer is god