A rare class exclusive-or respects

The values that keep arriving measured the hope called sparse space and found no support for it. The hope is that the Grundy values of an unsettled octal game split into a common set, occurring with positive density, and a rare set that thins out as the heaps grow, so that a periodicity argument can be run on the common part with the rare values handled as exceptions. For ·007, the rare share rose from 32 per cent of the first thousand heaps to 85 per cent of the sixth; for ·6 it rose too.

That measurement defined the rare values by rank: everything outside the twenty-two commonest. Its closing section named what a real test would have to ask instead — what a proof would have to establish about the common values, and whether the common set is closed under the operation such a proof needs. The operation is exclusive-or, and asking the question properly changes what is being measured. It also finds a game where the answer is yes.

Why the split has to be a parity #

A take-and-break move can leave two heaps, and the value of two heaps is the exclusive-or of their values — that is the Sprague–Grundy theorem at work, and exclusive-or is the arithmetic Nim and the nim-sum introduces, and it is why an octal game’s sequence is computed by taking the mex over single heaps and exclusive-ors of pairs. So any argument that reasons about which values can appear among a heap’s options is reasoning about exclusive-ors.

For a split into common and rare to survive that, it has to behave predictably under the operation. The natural requirement is the one a subgroup and its coset satisfy: common with common is common, common with rare is rare, rare with rare is common. Then a split move lands in the rare class exactly when one of its two parts is rare, and if rare heaps are scarce, rare options are scarce too — which is the lever the argument pulls.

A split with that property is always a parity: pick a set of bit positions, and call a value rare when it has an odd number of ones among them. Exclusive-or adds parities, so the two rules follow. The single bit of lowest order gives the split into even and odd; bit six gives the values with the sixty-four’s bit set; bits zero and five together give a class no reader would name but exclusive-or respects equally. On a sequence whose values stay below 512 there are exactly 511 such splits, and every one of them can be checked.

The commonest values are closed under nothing #

The rank-defined common set can be tested against the requirement directly, and it fails completely.

For ·007 the twenty-two commonest values are 8 through 23, then 32 to 35, 38 and 128. Exclusive-or any two of them, a value with itself included, and the result is never one of the twenty-two: 8 with 9 is 1, 8 with 8 is 0, and neither nought nor one is common. Not one of the 484 exclusive-ors stays in the set, and the same is true of the twenty-two commonest values of ·6.

That already says the earlier measurement was measuring something other than sparse space. Its rare set grew; but its common set was never a set the argument could use, so the growth says nothing about whether a usable split exists. The third row of the table makes the point sharper. ·354 fails the closure test exactly as badly — none of 484 — and ·354, below, is the one game here that does have the structure. Ranking values by frequency is simply the wrong instrument: the commonest values of a game with a perfect parity split need not be closed, because the common class is closed and its most frequent members are a different set.

Every parity, on twenty thousand heaps #

The right instrument is the scan. For each parity, count the heaps whose value falls in its odd class, block by block, and ask whether that class thins: whether its share of the second half of the window is under a quarter of its share of the first tenth.

For ·007 no parity of any bits thins. There are 511 to try, since its values reach 392, and the class that falls furthest goes from 71.9 per cent of the first tenth to 34.6 per cent of the second half — it halves and stays at more than a third of all heaps. For ·6 the best is 78.1 per cent falling to 37.4. The two codes whose alphabets closed or nearly closed, ·127 and ·106, have nothing that thins either, which is what a settled-looking sequence with a small alphabet should show.

For ·354 fourteen classes thin. The one that falls furthest is the values with bit six set, from 11.6 per cent of the first tenth to four heaps in ten thousand. The plainest is the parity of the value itself: the odd values. Three simple classes thin — the odd values, the values with bit six set, and the values with an odd number of ones among bits one and three — and the other eleven are built from those three, with bit five allowed to ride along. Bit five on its own falls from a third of the first block’s heaps to under a tenth of the second half’s, and misses the threshold narrowly; it is a class that shrinks without becoming rare.

So the conclusion about ·007 can now be stated in the form the argument needs, and it is stronger than the earlier one. It was that the twenty-two commonest values are not taking over. It is now that there is no way of splitting ·007’s values that exclusive-or respects under which one side thins — over every such split the values can support, across twenty thousand heaps. The window is still a window; nothing here excludes a split appearing past it.

There is a plain reason to expect exactly this of a sequence like ·007’s, and it is visible in the grundy sequences of the settled codes by contrast. A parity class is half of the possible values — every nonzero parity puts exactly half of the numbers below any power of two above its highest bit on each side, and very nearly half of any long run of consecutive numbers. A sequence whose values keep climbing into new territory, as ·007’s do, reaching 392 by heap twenty thousand, spreads its heaps over more and more values, and each parity class then catches something close to half of them. The best class for ·007 ends at 34.6 per cent and the best for ·6 at 37.4, which is what a class looks like when the values it is sorting are spreading out. For a class to thin, the sequence has to stop visiting half of the values: ·354’s values stay below 114 and, after the first few thousand heaps, are almost all even. But the search is complete over the splits there are, not a sample of them.

One code in seventy-nine #

Two games failing does not say whether the structure is rare or merely absent from these two, so the scan was run across the whole family of small codes.

There are 224 distinct codes of up to three octal digits. Seventy-nine of them have values reaching 32 within four thousand heaps — the growing ones, where sparse space is a live question at all. Every parity class of each was scanned on four thousand heaps, and two codes have a class that thins: ·354 and ·377. Taken to twenty thousand heaps, ·377’s class stops falling: the class flagged on the short window — values with an odd number of ones among bits zero and five — falls from about forty per cent of the first four hundred heaps to about a tenth and then stays there, 2,522 heaps of twenty thousand, still arriving in the last fifty heaps of the window. A class that falls and levels is a common class with a smaller density, not a rare one. ·354’s keeps falling. One code in seventy-nine.

That is the finding that turns this from a negative into a map. The structure the argument needs is not a fantasy; it occurs, in a three-digit code whose rules are as plain as any: remove one counter and leave nothing or one heap, remove two and leave nothing or two heaps, remove three and leave exactly two. It is also rare, and the famous unsettled codes are not where it occurs.

What the odd values of ·354 do #

The start of ·354 gives no hint. Its first forty values are small and mixed, seventeen of them odd — a sequence a reader would expect to behave like any other. Over the first two thousand heaps 288 values are odd; in the next two thousand, 22; then 3, then 1; then none at all in six thousand heaps, from heap 8,000 to heap 14,000.

Then they come back. Heap 14,523 is worth 37; 15,113 is worth 47; 15,510, 15,522, 17,280 and 18,846 bring 37 and 47 again; heap 18,908 is worth 83. Seven odd values in ten thousand heaps, arriving singly, from a set of three.

Why a rare value can arrive at all, once rare values are scarce, is worth looking at in one heap, because the answer is not the one the sparse-space picture first suggests. Heap 14,523 has 14,522 options: the single heap one smaller, and every split of 14,521 or 14,520 counters into two heaps. 628 of those options are odd. Every one of them comes from a split that puts one part on an early heap whose value is odd — 1, 4, 7, 8, 10, 11 and so on, the heaps of the first block — and the other part on a heap whose value is even. So odd options are not absent from a large heap. They are a steady few hundred, about four per cent of the options, supplied by the three hundred odd heaps near the start.

What decides the value is the mex, and the mex is odd only when it stops at an odd number: every smaller value, even and odd, has to be among the options, and that odd number has to be missed. At heap 14,523 every value from 0 to 36 is present and 37 is not. That happens rarely because the few hundred odd options have to cover every odd number below the stopping point while missing the one at it, and the thousands of even options almost always leave an even gap first.

The count of odd options is the number to watch as the heaps grow, and it behaves exactly as the argument would want. At heap 1,000 there are 406 odd options of 998, forty per cent; at heap 2,000, 544 of 1,998; at 4,000, 614; at 8,000 and 12,000, 628; at 16,000, 632; at the last heap of the window, 642 of 19,997, three per cent. The odd options stop growing once the heap has passed the block where the odd values live, and the even options go on growing with the heap. A bounded number against a growing one is the whole shape of a sparse-space situation, and in ·354 it can be read off directly.

That is the exact sense in which the rare class is rare. The argument’s lever is not that rare options vanish; it is that they stay a bounded few hundred while the common options grow with the heap, so the rare class can only win the mex by an arrangement of a few hundred numbers that the growing common part keeps pre-empting. Heap 18,908, worth 83, has 636 odd options and the same story.

What a proof would still need #

A sparse-space proof of periodicity for ·354 would need two things this measurement does not give.

The first is that the rare heaps can be controlled: either they stop, after which the common part could be checked for a period by the finite argument a period is a proof describes, or they recur on a schedule the argument can predict. Twenty thousand heaps show seven late arrivals and no schedule. The gaps run 590, 397, 12, 1,758, 1,566 and 62.

The second is that the common part settles once the rare part is accounted for. Even values alone have not been checked for a period here, and the sequence as a whole has none within twenty thousand heaps. The scan establishes that the right kind of split exists and thins; it does not establish that the split is enough.

That is the honest position, and it is different from the position of ·007. For ·007 the argument has nothing to hold on to; for ·354 it has exactly what it asks for, and the question becomes a question about seven values.

How the scan was run #

Every sequence is the Grundy sequence of its octal code, computed by the mex over every take-and-break option, the same computation octal games describes. For each code the values’ bit length fixes the parities to try, all $2^b - 1$ of them. A class thins when its share of heaps in the second half of the window is under a quarter of its share in the first tenth; the threshold is a choice, and the codes it flags are far from the line on either side except ·377, which is why ·377 was re-examined over the longer window. The rank-defined common set is the twenty-two most frequent values in six thousand heaps, as in the earlier measurement, with ties broken toward the smaller value. Twenty thousand heaps of one code cost about two seconds, since every heap looks at every split of itself; the survey of 224 codes uses four thousand heaps each so that the whole family costs less than one long run, and only the codes it flags are taken further.

What the scan cannot show #

Every window is finite. A class that thins over twenty thousand heaps could thicken later, and a code with no thinning class here could develop one past the window. The scan is complete over splits and not over heaps.

Only splits of one kind are tested. A parity is the only split under which rare-with-common is always rare, which is what the argument as described needs. A proof could use a weaker property — a split that exclusive-or respects only most of the time, or one defined on the values that actually occur rather than on bits — and the scan does not reach it.

And the survey stops at three digits. Longer codes allow more moves, and three bits of rule found that the cost of a sequence depends sharply on whether a move may leave two heaps. Whether thinning classes are commoner among the four-digit codes is not measured.

Still open: whether the seven stop #

The next measurement is the one the late table asks for: ·354 taken far past twenty thousand heaps, with every odd value recorded. The computation grows as the square of the heap count, so a hundred thousand heaps is twenty-five times this one and within reach. If the odd values stop — no more after 18,908, over a long enough stretch that their generating splits have all been passed — then the even part can be searched for a period and the sparse-space argument has a case to close. If they keep arriving, the useful measurement becomes their schedule: whether the heaps carrying 37 and 47 are spaced by a rule, which is what what the arithmetic cost in 1956 would have called a certificate, and what the sequence nobody has settled has been waiting for from a different direction.