There are five ways to write four as a sum of positive integers: 4, then
3+1, then 2+2, then 2+1+1, then 1+1+1+1. There are 190,569,292 ways to write
one hundred. Nobody has ever listed those and nobody ever will, and yet the
number is known exactly.
The counts start 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, and there is no rule in
them. The gaps run 1, 1, 2, 2, 4, 4 and then 7, which breaks the doubling the
first six suggest. The ratio of one count to the next falls and then climbs
back up: 42/30 is exactly 1.4, the next is 1.333, and the one after that is
1.375. Nothing in a longer list makes a rule appear.
The answer comes from somewhere else. A partition is an independent choice of
how many ones, how many twos, and how many of every size above them, and
independent choices multiply. The choices for part size k are recorded by
1 + x^k + x^2k + ... , which is 1/(1 - x^k), so multiplying one such fraction
for every size gives a single expression whose expansion contains a power of
x for every partition there is. The coefficient of x^n is p(n) exactly, not
approximately. That is Euler's identity, written down in 1748:
the product of 1/(1 - x^k) over all k, equals the sum of p(n) x^n over all n
It is an equality of formal power series. x is never given a value, nothing
is summed, and convergence is not a question.
The product is infinite and every single coefficient is a finite calculation,
because no partition of n uses a part larger than n. Take the first n factors
and the n-th coefficient is already final: the table of partial products in
this video shows the column at 4 reading 1, 3, 4, 5, 5 as the factors arrive,
stopping exactly when the fourth one lands.
Then the same product with minus signs almost completely cancels. What
survives is 1 - x - x^2 + x^5 + x^7 - x^12 - x^15 + ... , whose exponents are
the generalised pentagonal numbers j(3j-1)/2, only six of them below twenty.
Inverting that sparse series turns the product into a recurrence:
p(5) = p(4) + p(3) - p(0) = 5 + 3 - 1 = 7. It needs 4 terms at n = 10, 16 at
n = 100 and 22 at n = 200, growing like the square root of n.
That is fast and it is still not a formula, because reading p(100) means
building every row below it. Hardy and Ramanujan jumped straight to the value
in 1918 with exp(pi sqrt(2n/3)) / (4n sqrt 3). At n = 100 it gives
199,280,893 against the true 190,569,292: 4.57% high, with an error of
14.53% at n = 10 and 3.20% at n = 200. It falls and it never arrives.
Rademacher made the same idea exact in 1937, as a convergent series whose
partial sums round to the integer itself.
Everything checked on screen:
p(n) built by the Euler product for every n up to 200, and the same counts
found again by exhaustive listing for every n up to 12
the pentagonal recurrence run independently over the same range, agreeing
with the product at every single n
p(50) = 204,226, p(100) = 190,569,292, p(200) = 3,972,999,029,388
the first count above a million, at n = 61
the gaps and the ratios of the first counts, including the ratio that
rises again
the coefficients of the first five partial products, and the settling law:
the first k coefficients are final and the next one is not
the generalised pentagonal numbers from j(3j-1)/2, both families
the recurrence worked at 5, 6 and 7, and its term counts at 10, 100, 200
the Hardy-Ramanujan error at every n from 10 to 200, positive everywhere
Chapters
0:00 Five ways
0:16 Counting by eye
1:11 The first twelve
2:03 How fast it climbs
2:51 No rule in the numbers
4:04 One choice per size
5:16 What one factor holds
6:36 The product
7:47 Euler's identity
8:54 Unpacking it
10:03 Why it settles
11:17 The pentagonal numbers
12:36 The recurrence
13:51 Every row below
14:59 The estimate
16:07 How good is good
17:13 The exact version
18:24 Five again
Like and subscribe if you want the next one.
Music by Vincent Rubinetti
Download the music on Bandcamp:
https://vincerubinetti.bandcamp.com/a...
