by Jonathan Kujawa
Last month at 3QD we discovered that Pascal's Triangle contains all sorts of surprises. Like most things in mathematics, there is no end to the things you can uncover if you keep digging and have a curious mind. If we revisit the Triangle with our eye open for curiosities we notice that the sequences of numbers which run parallel to the side of the triangle look a bit interesting [1]:
Okay, the first line is just a sequence of 1s and is pretty darn boring. The second sequence is the counting numbers and is only slightly better than the 1s since anyone over the age of five who knows the addition rule for the Triangle can see why they are there.
But the third row! They seem to follow some sort of pattern, but it's not quite so obvious what it might be. We already have the hint that they're called the Triangular Numbers. If you were a boring person devoid of curiosity, you could go on with your life never knowing what's going on. But you're not and you know the Triangle rewards the curious. The following image explains why they're called the Triangular Numbers:
Once you notice that the pattern, it's not too hard to see that the nth number in this sequence is the number of balls needed to make a triangle which has n balls along one side (to go from one triangle to the next you just add another row to one side and counting those additional balls amounts to the addition rule of Pascal's Triangle). It's also not too hard to see [2] that the nth Triangular Number is given by the formula n(n+1)/2.
Let's agree that the 0th triangular number is 0. Not only is it reasonable to say the triangle with no balls on each side is made from 0 balls, we'll see it also turns out to be a convenient convention.
If you remember from last month, Pascal's Triangle was invented by Pascal while he and Fermat were corresponding about problems in counting and probability. No doubt Fermat noticed the Triangular Numbers and wondered what could be said about them. In any case, in 1636 he wrote a letter to Mersenne and made the remarkable claim that he could prove that every counting number can be written as the sum of three Triangular numbers. For example, we have 2 = 1 + 1 + 0, 5 = 3 + 1 + 1, and 32 = 21 + 10 + 1.
Fermat being Fermat, he didn't include the proof of his result. It took 160 years until the great mathematician Gauss found a proof of Fermat's result. He found it on July 10, 1796, to be precise. How do we know the date? Check out the entry for that day in Gauss's diary [3]:
For obvious reasons this result is often called the Eureka Theorem.
Incidentally, this wasn't Gauss's first run-in with the Triangular Numbers. A probably apocryphal anecdote tells of a school teacher who required young Gauss and his classmates to sum up the numbers from 1 to 100. The teacher's plans for an hour of peace and quiet were quickly ruined when Gauss quickly found the sum using a clever trick [4]. Notice that adding one more number to the list is just like adding one more row to a triangle. Adding the first n numbers is just the same as asking for the nth Triangular Number.
Fermat knew that triangles weren't special here. You could instead consider the Square Numbers:
The Hexagonal Numbers:
Pick your favorite number and we can consider the sequence of numbers you get by counting how many balls are required to make polygons with that many sides. Tetracontakaihenagonal Numbers, anyone? For brevity, let's call these kinds of numbers Polygonal Numbers and, more specifically, the numbers you get from the polygons with n sides the n-gon Numbers. So the 3-gon Numbers are the Triangular Numbers and the 6-gon Numbers are the Hexagonal Numbers.
In Fermat's letter to Mersenne he actually made the bold claim that every counting number can be written as a sum of exactly n n-gon Numbers. That is, every number can be written as a sum of exactly three Triangular Numbers, a sum of exactly four Square numbers, a sum of exactly six Hexagonal Numbers, and a sum of exactly eighty Octacontagon Numbers (to name one other of the billions of possibilities). Note that, just like for Triangular Numbers, we allow repeated uses of a number and count zero as a n-gon Number for every n.
If it took the great Gauss and 160 years to verify Fermat's claim for the Triangular Numbers, then surely we must still be grinding away, right? In fact, in 1770 (16 years before Gauss!) Lagrange proved that every number can be written as the sum of four Square Numbers. Lest Fermat get too much credit here, let me point out that the problem of writing numbers as the sum of four Square Numbers goes back to the ancient Greek mathematician Diophantus and was stated explicitly in Bachet's 1621 translation of Diophantus's Arithmetica.
What about the rest of the n-gon Numbers? In 1813 Cauchy showed that you can use Gauss's result on the Triangular Numbers to verify for every n that the counting numbers can always be written using a sum of n n-gon Numbers. The result is now often called Cauchy's Polygonal Number Theorem. Just like with his Last Theorem, Fermat was right and it just took us a few hundred years to prove it. In 1987 Melvyn Nathanson gave a very short proof of the Polygonal Number Theorem which only ran to three pages. You can read it here.
Surprisingly, Nathanson showed that you can always do it using four n-gon Numbers along with a bunch of zeros and ones. I would have thought it gets more and more complicated to make sums as you have more and more sides to your polygon, but it just isn't so.
So is Cauchy's proof of the Polygonal Number Theorem the end of the story? It turns out to be only the beginning! Let's go back to the Triangular Numbers. Gauss showed us that every number can be written as a sum of three Triangular numbers, but how many ways can you do it? For example, 5 = 3 + 1 + 1 is the only way to write five using Triangular Numbers, but six can be written as 6 = 6 + 0 + 0 and as 6 = 3 + 3. This raises the very interesting, and much harder, problem of counting how many ways you can write each number as a sum of three Triangular Numbers.
How can we possibly count such things? If you give me any number, I can slog away by adding up all possible triples of Triangular Numbers and tally up those which work. Even with a powerful computer this quickly becomes a Sisyphean task. And, of course, there are infinitely many numbers. I'll never finish those damnable sums.
Fortunately pre-Computer Age mathematicians developed a powerful tool for counting which lets us find beautiful formulas. It is called a generating function and, like many great ideas, seems naive and useless at first glance. Warning: the algebra gets pretty heavy but keep in mind that in the end they are simply a tool for recording a list of numbers.
We introduce a symbol, q, and we allow ourselves to add and multiply q's according to the usual rules for addition and multiplication just like we would if q was the variable x in high school algebra. So, for example, we have q3q2=q5 and (2q2 + q)(q2 + q3) = 3q4 + 2q5 + q3.
Now given a list of numbers, say 2, 3, 1, and 4 we can record them using q by writing: 2q + 3q2 + q3+4q4. The rule is that the first number is in front of q = q1, the second number is in front of q2, and so on. Since this is just bookkeeping, we can do this even if there are infinitely many numbers. If we wanted to record the Fibonacci Sequence we'd write:
A variation on this technique is to use the exponent on the q to record the number from our list and the number in front of that power of q indicates how many of that number we wish to have in hand. So if we wanted one each of the Fibonacci numbers, then in this scheme we'd write
Or if we wanted to have one of each of the Triangular Numbers, then we'd write:
Now a minor miracle occurs. If you think about it carefully you realize that when you multiple out
according to the usual rules of high school algebra, then the number in front of qn is exactly the number of ways of writing n as a sum of three Triangular Numbers! The problem is then to find a nice formula which doesn't require brutal amounts of addition and multiplication but still gives you useful information.
In 1986 George Andrews gave us just such a formula:
On the left hand side the zig-zag S shape (the Greek Sigma) stands for an infinite sum, and the symbol which is the exponent on the q is exactly the Triangular Numbers. That is, the left hand side of this formula is exactly our formula. Dr. Andrews tells us that our formula can instead be given by the infinite sum on the right hand side. Now admittedly this formula looks rather unpleasant. But it's something we can work with and it's certainly better than we have any right to expect. For example, if you have some experience calculating with these things you can easily see from the right hand side that the number in front of every power of q is at least one. That is, that every number is the sum of three Triangular Numbers in at least one way. That is, Dr. Andrews's formula immediately gives us Gauss's Eureka Theorem!
This opens the way to all sorts of questions: If you replace the exponent 3 in our formula with a 4, then it calculates how many ways you can write a number as four Triangular Numbers. The same is true if you replace the 3 with a 5 or 17 or whatever you like. You can try to get a Dr. Andrews's style equation for those formulas. Or you could replace the generating function for the Triangular Numbers with the generating function for the Square Numbers, or the Pentagonal Numbers, or…. Before you know it you are in the midst of modular forms, Eisenstein series, and other fancy things at the cutting edge of modern Number Theory.
[1] Image borrowed from mathisfun.com.
[2] Putting two identical triangles side by side you can make a rectangle with n balls on one side and n+1 balls on the other side. Taking their product gives the number of balls in the rectangle and taking half of that gives the number of balls in one triangle.
[3] Photo taken from the 1917 edition of Gauss's collected works at the Institut Mittag-Leffler.
[4] If you sum 100 and 1, 99 and 2, 98 and 3, and so on you get 101 each time. There are exactly 50 such pairs, sot he total is 101 x 50 = 5050.