The odd values keep coming

Some octal games have never been settled. Their Grundy sequences have been computed for millions of heaps without repeating, and nobody knows whether they ever will; Grundy sequences is where the family and its open cases are set out. The hope that has kept people computing is called sparse space: the values split into a common class that occurs everywhere and a rare class that thins out, and if the rare class thins out completely, what is left can be checked for a period by the finite argument that settles every game that does repeat.

The values that keep arriving tried the hope on ·007 and found nothing to hold: defined by rank, as everything outside the commonest values, its rare class was getting commoner, not rarer. That was a statement about ·007, and about a definition of rarity the argument cannot use.

A rare class exclusive-or respects asked the question in the only form the argument can use. A rare class has to be one that exclusive-or respects, which means a parity of bits, so that a sum of heaps is rare exactly when an odd number of its parts are. Over every parity of every bit, across all 79 growing octal codes of up to three digits, it found one code with a class that thins: ·354, whose odd values fall from 288 in the first two thousand heaps to 22, then 3, then 1, then none for six thousand heaps, and then seven between ten thousand and twenty thousand, the last at 18,908.

That left the argument waiting on one question. If the odd values stop — if 18,908 was the last — then the even part can be searched for a period and ·354 has a case to close. If they keep arriving, the useful thing to know is whether they arrive on a schedule. The computation that answers it grows as the square of the heap count, and a hundred thousand heaps takes four seconds.

They do not stop #

Heap 21,023 is worth 37. So are 23,621 and 25,107; 26,376 is worth 77; and from there to the end of the range the odd values arrive in every block. Between twenty thousand and a hundred thousand heaps there are 48 of them, and the last in range is at heap 99,600, worth 37 again. Counted in blocks of ten thousand after the first, the blocks hold 7, 4, 3, 6, 7, 4, 11, 10 and 3.

That is not a class thinning out. The first block holds 314 odd values, because that is where the small heaps are and where the sequence has not yet settled into its long-run behaviour, and after it the rate drops at once to about six per ten thousand heaps and then stays there. There is no decline across the last eighty thousand heaps: the two busiest blocks are the eighth and ninth, and the quietest are the fourth and the last.

The six thousand heaps with no odd value at all, from eight thousand to fourteen thousand, were what made the class look as if it were vanishing. On the longer run they are one of the gaps, and not the longest possible one. The longest gap between successive odd heaps past ten thousand is 6,682. At the rate the last eighty thousand heaps show, the stretch from a hundred thousand to a million would hold five or six hundred more — an extrapolation, and one a run a hundred times longer than this, some seven minutes of arithmetic, would test directly.

Ninety thousand heaps, drawn #

The counts per block say the class persists. A picture of where each odd value falls says how.

A class that was thinning towards nothing would crowd the left of the line and leave the right bare. This one does neither. The ticks are scattered from one end to the other, with clusters — seven between 76,000 and 79,000, two of them only five heaps apart at 78,449 and 78,454 — and long empty stretches, and the right-hand third holds more than the left-hand third.

What the picture does show is how narrow the class has become. Past ten thousand heaps nearly every odd value is 37.

Forty-one of the 55 are 37. Six are 49 and five are 47. The other three are single arrivals: 83 at 18,908, 77 at 26,376 and 35 at 83,055. In the first ten thousand heaps the odd values ran through forty-two different numbers from 1 to 113; past it, a sequence whose values reach 102 among its even ones produces odd values almost exclusively at one height. The rare class has not shrunk to nothing. It has shrunk to a single number that keeps being hit.

No schedule a remainder can see #

If the odd values kept coming on a schedule, that would be almost as good for the argument as their stopping. A schedule is a certificate: it predicts every future odd value, and a proof could carry it. What the arithmetic cost in 1956 prices certificates of exactly this kind for the games that did settle — ·137’s is 7,919 operations by hand — and a schedule for ·354’s odd values would be its first certificate of any size. The simplest schedule an octal game has is a period, and a period shows up as a pattern in the remainders of the heap sizes.

Sorted by remainder modulo every number from 2 to 16, the 55 late odd heaps leave no residue class empty. Modulo 2 they split 30 to 25; modulo 3, 25, 16 and 14; modulo 7, from 15 in the fullest class to 2 in the emptiest — the spread fifty-five numbers have when nothing is sorting them. Only at modulus 24, with 24 classes and fewer than three heaps expected in each, do empty classes appear, which is what chance does at that size.

And the whole sequence, odd and even values together, has no period of 40,000 or less that holds over the last 20,000 heaps. Every candidate fails at once, most of them within a few heaps of where the check starts. So the odd values are not riding on a short period of the sequence, and nothing about their positions is regular at any modulus a reader might try.

Gaps like arrivals #

There is one more kind of regularity worth testing, and it is the opposite of a schedule. Events that happen at a steady rate with no memory — the classic example is radioactive decay — have gaps with a particular spread: their standard deviation equals their mean, and short gaps are commoner than long ones.

The gaps between successive late odd heaps run from 5 to 6,682, with a mean of 1,576 and a standard deviation of 1,499. The ratio is 0.95, where a memoryless process has exactly one and a periodic one has nought. Binned, they sit close to what an exponential distribution with the same mean predicts: more short gaps than long, and a tail that runs out past four thousand. Fifty-four gaps is not many, and a test that could tell 0.95 from 1 would need far more; what it can tell apart is a schedule, which would have a ratio near nought, and this is nowhere near.

So the late odd values of ·354 behave, as far as every test here can see, like arrivals at a constant rate — one about every 1,600 heaps — independent of each other and of the heap size. That is the worst case for the argument that looked most promising. A class that stops can be handled; a class on a schedule can be handled; a class that arrives like decay is a class nothing short of computing every heap will predict.

An odd value is a miss #

Why a heap should be odd at all, so far out, has an answer, and it explains why the arrivals look random.

A heap’s value is the least number its options miss. For the value to be 37, every number from 0 to 36 has to be reached by some move and 37 has to be reached by none. The earlier essay found why the second condition is the hard one: an option’s value is odd only when exactly one part of the split is odd-valued, and the odd-valued heaps are the few hundred near the start, so a large heap has only a bounded few hundred odd options against thousands of even ones.

Counting how many of a heap’s moves reach 37 in particular turns that into a number. Across the 90,001 heaps from ten thousand to a hundred thousand the count averages 4.3 — a typical heap has four or five different splits that land on 37 — and it is nought on 171 heaps. On 41 of those 171, every smaller value is reached and the heap is worth 37. On the other 130 some smaller value is missed too and the heap is worth that instead. And there is no heap worth 37 on which any split reaches 37, which is simply what the mex means, checked on every heap.

So each late 37 is a coincidence of misses. A few hundred odd-valued heaps near the start each offer a chance of landing on 37, through a partner of the right even value, and a 37 appears where all of them fail at once. That is exactly the kind of event that arrives at a steady rate with no memory: the chances shift a little with every heap, nothing in them repeats, and the rate is set by how many chances there are, which stops growing once the heap has passed the block where the odd values live.

The count itself is not a sum of independent chances, and the last number in the figure says so. A count averaging 4.3 would fall on nought by chance about 1,169 times in 90,001 heaps; it falls there 171 times, seven times less often. The splits that reach 37 are not independent chances: the misses are rarer than independence would make them, so the count is more tightly bunched around its mean than a sum of separate coin-flips would be, and that bunching is part of what keeps the late 37s as rare as they are.

What the run cannot settle #

A hundred thousand heaps is a window. The odd values have not stopped by 99,600; they could stop at a million, or thin slowly on a scale this run cannot see. What the run excludes is the reading that they had already stopped at 18,908 — the reading the argument was waiting on.

Every test for a schedule is a particular test. Residues up to 24, a period up to 40,000, the spread of 54 gaps: each is a pattern a schedule would show, and none is shown. A schedule of some other kind — a rule in the heaps’ binary digits, or in the odd heaps that generate each 37 — is not excluded.

And the argument is not refuted. Sparse space is a hope about the long run, and a rare class arriving at a steady rate is compatible with an eventually periodic sequence whose period is long and contains a few odd values. What it is not compatible with is the short version of the hope, in which the rare class runs out and the rest is quick to check.

The mechanism is read off one value. The split counts are taken for 37 because 37 is 41 of the 55 late odd values; 47 and 49 are presumably misses of the same kind, and the count was not taken for them. A mechanism checked on three-quarters of the class is a strong reading of it, and it is not a reading of all of it.

How the values were computed #

Octal code ·354: a move takes one counter and may leave no heap or one, takes two and may leave none or split the rest into two, or takes three and must split the rest into two. Normal play, and each heap’s Grundy value is the least non-negative integer not among its options’ values, an option’s value being the exclusive-or of its parts. The sequence is computed heap by heap with a stamped array for the mex, which makes a hundred thousand heaps about four seconds — every heap looks at every split of itself, so the cost grows as the square. The split counts for 37 run over the odd-valued heaps as one part, since an odd exclusive-or needs exactly one odd part, and they are checked against the sequence itself: a heap worth 37 must have none. Octal games is where the codes and the computation are set out.

The surprise: rare and random are the same thing here #

The sparse-space picture treats rarity as a property that might end — a class of values that is thinning and will eventually be gone. What ·354 shows at a hundred thousand heaps is rarity of a different kind. The odd values are rare because each needs a coincidence, a few hundred small chances all missing at once, and a coincidence of that kind does not become impossible as the heaps grow. It becomes steadily unlikely, at a rate the heap size no longer changes, and a steadily unlikely event is one that keeps happening.

That is also why no schedule appears. The same mechanism that makes an odd value rare makes it unpredictable: whether a given heap’s few hundred chances all miss depends on the even values of partners scattered across the whole sequence, and those have no pattern either. The class the argument needed to vanish is instead the part of the sequence that most resembles noise, and the sequence nobody has settled is the survey in which that difference — between a pattern not yet found and a process with none to find — has not yet been drawn for any code.

There is a pleasing symmetry with the games that do settle. In a periodic octal game the mex is decided by a window of recent values, and the argument that proves it, set out in a period is a proof, works because the options that matter are the nearby ones. In ·354 the options that decide whether a heap is odd are the far ones — splits reaching back to the few hundred odd heaps at the very start — and every late odd value is a message from the first ten thousand heaps, delivered by a partner chosen by the heap’s size. A sequence governed by its distant past in that way is the opposite of the local recursion a period rests on. Three bits of rule found the same thing from the side of the rule: the one property every never-settling code shares is that a move may split a heap in two, and a split is exactly what lets a large heap’s options reach back to the start.

Still open: the heaps that make each 37 #

Every late 37 is a heap where the few hundred odd-valued heaps near the start all fail to supply 37, and each of those heaps fails through a particular partner. The measurement the mechanism points at is that ledger: for each odd-valued heap below five thousand, how often it is the one that would have supplied 37 and did not, and whether a handful of them account for most of the misses. If they do, the late 37s are governed by a small set of heaps and their partners, and a prediction of where the next one falls might be built from them — which would be the schedule the residues could not see. If the misses are spread over all of them, the arrivals are as random as they look, and a period is a proof describes a certificate that ·354 will not supply in any range a computation reaches.