Is the partition count even half the time?

The number of ways to write $n$ as a sum of positive whole numbers, ignoring order, is the partition number $p(n)$: 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42 for $n$ from 0 to 10. The size of a number with no formula measured how fast these numbers grow, and every fifth one divides found a regularity in their divisibility: $p(5n + 4)$ is always a multiple of 5, $p(7n + 5)$ of 7 and $p(11n + 6)$ of 11. Those are Ramanujan’s congruences, and they say that for some classes of $n$ the partition number is forced to be divisible by a particular prime.

The simplest question of this kind is about 2, and it has no such answer. Is $p(n)$ even or odd? There is no congruence that forces either: Ramanujan’s three primes are the only ones with congruences of that simple shape, and 2 is not among them. The values look as though they choose at random, half even and half odd. That they really are even half the time was conjectured by Thomas Parkin and Daniel Shanks in 1967 from computations, and it is still not proved. This essay computes the parities of the first half million partition numbers and asks what the computation can and cannot see.

Parities without the numbers #

The partition numbers grow enormously — $p(500{,}000)$ has more than 750 digits — but their parities can be computed without ever forming them. Euler’s pentagonal number theorem, the subject of the terms that cancel almost everything, gives the recurrence

$$p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) - \cdots,$$

where the numbers subtracted from $n$ are the pentagonal numbers $k(3k \mp 1)/2$ and the signs repeat in pairs. Every operation in it is an addition or subtraction, so it can be carried out modulo 2, or modulo any number, keeping only residues. The parity of $p(n)$ is the parity of the number of odd values among the roughly $\sqrt{8n/3}$ earlier terms the sum involves. The first twenty-one values are checked against the exact partition counts, and the residues modulo 5 and 7 against Ramanujan’s congruences at every $n$ in their classes.

In this form the question becomes a question about a recurrence. Each new parity is an exclusive-or of a growing, sparse set of earlier parities — at $n = 500{,}000$ there are about 1,150 of them — chosen by the pentagonal numbers, which have nothing to do with parity. A rule of that kind is the sort that produces sequences looking random, and also the sort about which almost nothing can be proved.

A register whose taps keep moving #

The recurrence modulo 2 has a familiar shape. A sequence in which each new bit is the exclusive-or of earlier bits at fixed distances back is a linear feedback shift register, the machine of a memory of four bits, and every such register is periodic: with a fixed number of taps it has finitely many states and must eventually repeat. The generator inside nineteen thousand bits of state is a very large register of exactly that kind, with a period of about $2^{19937}$.

The partition parities differ in one way, and it is decisive. The taps are at the pentagonal numbers, and as $n$ grows the recurrence reaches further back and uses more of them: about 1,150 at half a million, and more without limit. No fixed register describes it, so no period is forced, and the sequence is free to be as irregular as the data suggest. That is the same freedom the centre column of rule 30 has on an infinite tape and loses on a ring; here it comes from a recurrence whose memory grows like the square root of its length.

The comparison also explains why linearity does not help. A register’s output is analysed through a single polynomial, whose factorisation decides its period and its statistics. The partition recurrence modulo 2 corresponds to the infinite product $\prod (1 - q^k)$ reduced modulo 2, and that product is not a polynomial; its structure is the subject of the theory of modular forms, which knows a great deal about it and has not yet produced the one fact needed here.

Half, as far as anyone can see #

Among the first half million partition numbers, 49.997% are even. The running share wanders near a half from the start and stays inside the band a coin’s tosses would keep to two-thirds of the time, at every scale from sixteen values to half a million. A sequence of parities produced by tossing a fair coin would look like this; a sequence produced by a rule with a hidden bias of one part in ten thousand would also look like this, which is why the computation supports the conjecture without approaching a proof.

The first 1,200 values in the opening figure contain 568 even ones, 47.3%, a little below a half — the sort of fluctuation that a sample of 1,200 coin tosses shows about six times in a hundred, and that disappears in the longer run. Small cases do not suggest a bias that large ones remove; they show noise of exactly the size noise should have.

Runs as long as a coin’s #

A share of a half is a weak property: the sequence 0101… has it. A sharper test is how the parities follow one another, and the simplest version counts runs — stretches of consecutive values with the same parity.

For a fair coin, half of all runs have length one, a quarter length two, an eighth length three, and so on. The partition parities match this length by length, to within a fraction of a percent for every length up to ten, and the longest run of one parity in the first half million is seventeen consecutive values — about the longest run that half a million coin tosses would typically contain, since a run of $k$ has chance about $2^{-k}$ at each position. The parities pass this test the way the centre column of rule 30 passes its block counts: completely, and without the passing meaning anything about the infinite sequence.

What is proved: about the square root #

The theorems known about the parity of $p(n)$ are dramatically weaker than the data. Oscar Kolberg proved in 1959 that $p(n)$ takes each parity infinitely often. Later work has bounded from below how often: among $p(0), \ldots, p(x)$ there are at least about $\sqrt x$ even values and at least about $\sqrt x$ odd ones, up to logarithmic factors, by results of Jean-Louis Nicolas, Imre Ruzsa and András Sárközy in 1998 and refinements since.

On logarithmic axes the gap is a difference of slopes. The counts of even and odd values both lie on the line of $x/2$, slope one; the proved bounds rise with slope a half. At half a million the counts are about 250,000 each and the bounds are about 700 — the theorems guarantee less than one value in three hundred of each parity, while the data show one in two. Every improvement so far has moved the bound by a factor smaller than any power of $x$, so the slope of the proved line has not moved off a half.

The reason is structural. The tools that prove congruences — modular forms and their coefficients modulo a prime — say a great deal about $p(n)$ modulo 5, 7 and 11 in particular classes, where the answer is that a whole class is zero. They are much weaker at the opposite task, showing that residues are spread out, and the square-root bounds are what they yield when pushed in that direction. To get a positive proportion of each parity, an argument would have to show that the parities are not merely non-zero often but balanced, and no method that sees the partition function through its generating function does that.

No progression is all one parity #

If the parity of $p(n)$ were governed by a hidden rule, the first place to look would be arithmetic progressions: perhaps $p(An + B)$ is always even for some $A$ and $B$, as $p(5n + 4)$ is always divisible by 5. Mehendra Subbarao conjectured in 1966 that this never happens — that every arithmetic progression contains infinitely many even and infinitely many odd partition numbers — and Cristian-Silviu Radu proved it in 2012. So no rule as simple as Ramanujan’s governs parity, and whatever balance the parities have, it is not produced by whole classes of $n$ being forced one way.

The contrast with a closely related count is striking. Count the partitions of $n$ into distinct parts instead, and the parity is not random at all. The generating function for distinct parts is $\prod (1 + q^k)$, and modulo 2 a plus sign and a minus sign are the same, so it equals $\prod (1 - q^k)$ — Euler’s product, whose expansion has nonzero coefficients only at the pentagonal numbers. The number of partitions of $n$ into distinct parts is therefore odd exactly when $n$ is a generalised pentagonal number $k(3k \pm 1)/2$, and even otherwise: odd 89 times among the first three thousand values, even for all the rest. Two counts that differ only in whether parts may repeat, and one has the most predictable parity imaginable while the other has none that anyone can find.

That pair is the cleanest statement of why the parity question is hard. The ordinary partition generating function is the reciprocal of Euler’s product, and taking a reciprocal is exactly the operation that turns a sparse, structured series into a dense, unstructured one. Every partition, hidden in a product drew the product; the parities of its reciprocal are what this essay counts, and nothing transfers the sparsity of the one to a balance in the other.

Parity as a count of fixed points #

There is a second way to see the parity of $p(n)$, and it turns the question into one about symmetric diagrams. A diagram turned on its side paired each partition with its conjugate, the partition whose Ferrers diagram is the original turned about its diagonal. Pairing is an involution: partitions come in pairs, except the self-conjugate ones, which are paired with themselves. So $p(n)$ has the same parity as the number of self-conjugate partitions of $n$, because every other partition is counted twice.

Self-conjugate partitions are much rarer than partitions — there are 2,574 of 100 against 190,569,292 partitions — and they have their own description: peel a self-conjugate diagram into hooks around its diagonal, and the hook lengths are distinct odd numbers adding up to $n$. So $p(n)$ is odd exactly when the number of partitions of $n$ into distinct odd parts is odd, a fact checked here for every $n$ up to two thousand. The question about a huge number becomes a question about a small one, and yet it does not get easier: the distinct-odd-part counts have parities that look just as random, with 50.6% odd among the first two thousand.

This is the typical fate of parity questions about counts. An involution with few fixed points reduces the count to a smaller one, sometimes repeatedly, and the reduction stops when no further symmetry is visible. For distinct parts it stops at the pentagonal numbers, and the parity is known; for all partitions it stops at distinct odd parts, and the parity is not.

Modulo 3, 5 and 7 #

The same computation runs modulo any number, and the residues modulo small primes split into two kinds.

Modulo 2 and 3 every residue is as common as every other, to within a fraction of a percent — the parity question and its mod-3 analogue, where Morris Newman conjectured in 1960 that every residue occurs infinitely often. Modulo 5 and 7 the residues are not equally common, for a reason that is known: the class $n \equiv 4 \pmod 5$ is all zeros, so zero takes a fifth of all $n$ outright, and if the remaining four-fifths were spread evenly zero would hold $1/5 + 4/25 = 36\%$ of all values. It holds 36.4%. Modulo 7 the same reckoning gives $1/7 + 6/49 \approx 26.5\%$, and the count is 27.2%, slightly more than the congruence accounts for.

An excess that follows a square #

The extra zeros modulo 7 are not spread over all classes of $n$. Taking the classes one at a time locates them.

Modulo 7, the classes $n \equiv 0, 2$ and $6$ have their fair share of zeros, 14.2% to 14.4%. The classes $n \equiv 1, 3$ and $4$ have 16.0% to 16.1%, steady across the whole million, block by block. The split is not arbitrary: the three classes with excess zeros are exactly those for which $1 - 24n$ is not a perfect square modulo 7, and the three with the fair share are those for which it is. Modulo 5 the same rule holds with a smaller excess: the classes $n \equiv 1$ and $2$, where $1 - 24n$ is not a square modulo 5, have 21.0% and 20.9% zeros against the fair 20%.

The number $24n - 1$ is not a stranger. It appears in every serious statement about the partition function: Ramanujan’s congruences are statements about $24n - 1$ being divisible by 5, 7 or 11, and the generating function of the partition numbers becomes a modular form exactly when it is written in the variable $q^{24}$, shifted by one. So a bias that depends on whether $24n - 1$ is a square modulo the prime is a bias the modular theory could plausibly account for. This essay does not account for it: the excess is measured, its pattern is checked class by class, and the reason is left to the theory that governs every other congruence the partition function has.

What the counts do not show #

Half a million parities and a million residues are finite samples of infinite sequences, and every statement about their limits — the share of even values, the residues modulo 3, the size of the excess modulo 7 — is outside what any finite count can establish. In the case of parity the data are so emphatic, and the proved bounds so weak, that the gap is itself the main finding.

The excess modulo 5 and 7 has the opposite status. It is a feature of the data that is too regular to be noise — steady across every block of a hundred thousand and splitting exactly along squares — and it may well be a known consequence of the theory of modular forms modulo a prime, but nothing here proves it, and its size is measured rather than derived.

Still open: parity, and the residues beyond #

The Parkin–Shanks conjecture, that $p(n)$ is even for exactly half of all $n$ in the limit, is open. It is not known that the even values have a positive proportion at all, or that the odd values do; the best lower bounds for both are of the order of $\sqrt x$, far below the $x/2$ that every computation shows. For modulo 3 the corresponding statement, that each residue has density one third, is open too, and Newman’s weaker conjecture that every residue modulo every number occurs infinitely often is known for many moduli and not in general.

The question that connects these is whether the partition numbers, outside the classes their congruences fix, behave like random residues. Ken Ono and others have shown that the partition function has infinitely many congruences for every prime beyond 3, of a much sparser kind than Ramanujan’s, so its residues are never entirely free of structure. How much structure there is — enough to bias the zeros along squares, as the last figure shows for 5 and 7, but not enough to bias the parity — is what a theory of the partition function modulo small primes would have to say, and it does not yet.