Three bits of rule

A period is a proof establishes what a found period buys: a lemma turns a finite computation into a statement about every heap size there will ever be. The sequence nobody has settled is the other side — the codes where the computation has run to enormous heaps and found nothing.

Both are about particular games. The question this rung asks is about the rule tables themselves: given a code, before computing anything, what can be said about how big the answer is going to be?

An octal code is a very small object. 0.7 is three bits. 0.137 is nine. Every rule the subject has is a handful of digits, and each of them determines a Grundy sequence completely. So the question has a clean form: how much bigger is the answer than the question, and what in the question predicts it?

Sixty-three codes — every one- and two-digit code there is. Forty-four settle into a period by heap six hundred. Nineteen do not.

Four properties were tested against that split, and three of them fail. A move may take the whole heap holds on 13 of the 19 open codes. Two digits rather than one holds on 18 of 19 — close, and close is worthless for a necessary condition. A digit of 7, which is the digit everybody points at because it means “do anything”, holds on 5 of 19.

The fourth holds on all nineteen. It is the 4-bit: whether some digit permits a move that leaves two non-empty heaps rather than one.

What the bit actually is #

The octal digits are read as three flags. The 1-bit says a move may take the whole heap and leave nothing. The 2-bit says it may leave one heap. The 4-bit says it may leave two — that is, the heap may be split.

So the digits without the 4-bit are 0, 1, 2 and 3, and a code built only from those describes a game where a heap never becomes two heaps. It is a subtraction game with conditions on it: the heaps it starts with are the heaps it ends with, only smaller. A subtraction not a factor is about that family, and its sequences are well behaved for reasons that are understood.

Digits 4, 5, 6 and 7 all carry the bit. That includes 5 and 7, which is worth saying because 5 looks like a small digit and is not — 5 is 4 + 1, so a 5 permits both taking the whole heap and splitting it.

Once a heap can become two heaps, the Grundy value of a position is a nim-sum of the parts, the sum is the object applies, and the sequence at heap n depends on exclusive-ors of pairs from everything below it rather than on a fixed window. That is the structural reason the bit is where the difficulty starts, and it is not a new observation — what is new here is that it was tested against three rivals and is the only one that survived.

It is worth being exact about what “well behaved” means for that family, because it is not merely that they settle. A subtraction game’s Grundy sequence is purely periodic from a bounded point, the period divides something computable from the rule, and the block is short. None of those three survives the 4-bit. The period stops being predictable, the pre-period stops being bounded by anything anybody has found, and the block grows.

So the bit is not a difficulty knob. It is the point at which three separate guarantees fail together, and that is why one bit is doing the work of a whole classification.

Necessary, and nothing more #

The temptation with a condition that holds on all nineteen is to promote it. The measurement refuses.

Twenty-nine of the forty-four settled codes carry the bit too. So it is not a decision procedure; it is a fence, and both sides of the fence contain settled games.

Nine of them do better than settle. 0.51 and 0.55 have period 1 — six bits of rule, one bit of answer. 0.5, 0.7, 0.71, 0.75 have period 2. Every one of them may split a heap, and every one produces a Grundy sequence smaller than the rule that produced it.

And the other side of the fence holds. No code without the splitting bit ever produces an answer larger than its rule. Fifteen such codes, the largest of them exactly the size of its own rule, and the figure refuses to draw if a single one exceeds it.

That is a boundary in one direction and nothing at all in the other, and it is worth naming as such rather than rounding to “splitting games are hard”. Splitting games are where hard games are; most splitting games are not hard.

The nine are worth listing rather than counting, because the reader who wants a rule of thumb should have to look at them. 0.51, 0.55, 0.05, 0.24, 0.25, 0.5, 0.7, 0.71, 0.75. Every one may split a heap. Every one has a period of one or two. 0.5 is “take the whole heap, or split it into two” and its Grundy sequence alternates.

What that list rules out is the natural repair, which would be to find a second condition that, together with the bit, decides the question. Nothing here forbids such a condition existing; what the list shows is that it is not going to be about the digits, because 0.5 and 0.4 differ in one bit and sit at opposite ends of the range, and 0.7 carries strictly more permissions than 0.5 and behaves the same way.

How big the answer gets #

The measure is the honest one available: the rule costs three bits a digit; the answer costs the length of the periodic block times the bits its largest value needs. Both are counts of what has to be written down.

At the cheap end, 0.01 and 0.11 and 0.51 and 0.55 cost six bits of rule and one bit of answer — a ratio of 0.17. The rule is longer than what it determines.

At the dear end, 0.4 is a single digit, three bits, and its sequence has period 34 with values up to 9: 136 bits. A ratio of 45.3. The same handful of codes at 22.7 and 17.0 are the rest of the Dawson family, and 0.44 and 0.46 sit at 16.0 with a period of 24.

Two hundred and seventy-two, from one end to the other, across objects that differ by a digit.

A caution about the measure, since it is a choice and not the only one. Counting the periodic block in bits treats a period of 34 with values up to 9 as 136 bits, which assumes the block is stored as a flat table. A cleverer encoding would do better on some of these — a block that is nearly a repetition, or nearly arithmetic, compresses — and the ratios would shrink. What would not change is the ordering, or the fact that the range spans two orders of magnitude, because the periods themselves span 1 to 34 and the value alphabets span 1 to 9. The measure is crude and the conclusion does not rest on its crudeness.

And twenty-four of the forty-four settled codes — more than half — produce an answer no bigger than the rule. That is a formula in the only sense available here: the whole of what the game does fits in less space than the description of the game. Those are the codes where somebody looking at the sequence would say of course, and the reason they can is that there is nothing much to say.

The nineteen that did not settle #

Nothing above says what the nineteen open codes are doing, and the honest answer is that this sweep cannot tell.

A code counts as open here when no period is found within six hundred heaps. That is a statement about six hundred heaps and about the period-finding routine, and it is emphatically not a statement that no period exists. Several of the nineteen very likely settle at seven hundred, or nine thousand; a few are among the codes that have been pushed to enormous heaps by people with better machinery and have still found nothing. The sequence nobody has settled is about the second kind, and the distinction between the two kinds is invisible from inside this table.

That is a limitation and it does not weaken the result, because of which direction the claim runs. The claim is that every code failing to settle here carries the splitting bit — nineteen for nineteen. Raising the search limit can only move codes out of the open column, never into it, so a longer run can falsify the claim only by leaving a non-splitting code unsettled, and non-splitting codes settle for reasons that are proved rather than observed. The condition is safe against the thing that would otherwise undermine it.

What the limit does affect is the second half of the essay, the sizes. A code that settles at heap eight hundred with a period of two hundred would be an enormous answer and it is not in the ratio table, so the measured span of 272 is a lower bound on the span. Widening the search would widen it.

There is one more thing the nineteen have in common, and it is worth recording because it is nearly a second condition and is not one. Sixteen of them have two digits and one — 0.6 — has one. 0.6 is “take one counter and leave one heap or two”, which is about as small a splitting rule as exists, and it is the only single-digit code in the whole sweep that does not settle. Whatever makes these games hard, it is available in three bits.

Different rules, the same period #

There is one more measurement, and it settles whether the period could ever be read off the digits directly.

Six codes — 0.4, 0.07, 0.17, 0.41, 0.42, 0.43 — land on a period of exactly 34. Their pre-periods differ: 54, 53, 33, 34, 54, 34. Their maximum values differ: 9, 9, 7, 7, 9, 7. They agree on the one number a formula would have to produce.

Eleven codes give a period of 2, and ten give a period of 4.

That collapse is the argument against ever finding a shortcut. If the period were some arithmetic function of the digits, rules as different as 0.4 and 0.43 would not keep landing on the same value — and the agreement is not a coincidence anybody has explained. The period is computed from the rule and there is no other route to it, which is exactly what a period is a proof is doing work to make worthwhile: since the period cannot be predicted, it has to be found, and finding it has to be enough.

The three games that sort the other way #

A chess problem that was an octal game is about 0.137, which is the most famous of these codes and does not appear anywhere above, because it has three digits and this sweep is over one and two. It is worth naming because it is the shape the sweep predicts: a splitting bit, a long pre-period, a period of 34, and a sequence nobody would guess.

What the sweep adds to that reputation is the company 0.137 keeps. 0.4 — a single digit, “take one counter and leave two heaps” — produces a sequence just as awkward, at a third of the description length. 0.07 produces the same period from a rule that says something entirely different. 0.17 and 0.41 and 0.43 join them.

Six rules of two, three and six bits, all landing on the same 34.

Against that, 0.7 — which permits everything a one-digit code can permit, including splitting — has period 2. It is the code that ought to be hardest by every heuristic anybody uses and it is among the easiest, and it is in the “wrong way” table above for exactly that reason.

The pre-period deserves the same treatment and gets the same answer. It is not counted in the bit totals above — the ratio measures the block, not the run-up to it — and it should be, if the question is really how much has to be written down. Adding it changes the numbers and not the shape: the six period-34 codes have pre-periods between 33 and 54, so their true description costs are all roughly double what the table says, and the cheap end is untouched because a period-1 sequence settles almost immediately.

What it adds is a second quantity that different rules agree about for no visible reason. 0.17 and 0.41 and 0.43 share a period of 34 and pre-periods of 33, 34 and 34. 0.4, 0.07 and 0.42 share the same period and pre-periods of 54, 53 and 54. Two clusters, two rules apiece plus one, and no digit property that puts them in those clusters.

What a rule table is worth knowing in advance #

The practical residue is three lines, and each is a measurement rather than an intuition.

If the code has no digit of 4 or more, stop worrying: the sequence settles, and the answer is no larger than the rule. Fifteen for fifteen here, and there is a structural reason — the heaps never multiply, so nothing has to be nim-summed with anything.

If it does, that is the only thing the digits say. Twenty-nine such codes settle and nineteen do not, and no property of the table separates them. Where the impartial theory stops is the general shape of that situation; this is the sharpest small instance of it, because the objects are three bits long and there is nowhere for the difficulty to be hiding.

And do not read the pre-period off anything either. It is the second half of what has to be written down, it is bigger than the period on most of the hard codes, and the two clusters above show it agreeing across rules that agree about nothing else. A prediction about the size of an octal game’s answer has to predict two numbers, and the sweep finds no digit property that predicts either.

There is a fourth line that is not practical advice but is the reason the first three are worth having. Every number in this essay came out of a computation that anybody can rerun, over an object — a two-digit octal code — that is small enough to write on a stamp. The subject’s reputation for difficulty is usually explained by the size of the games, and these are not large games; they are three and six bits of rule producing sequences that either fit in a line or defeat everybody. Whatever is hard here is not hidden in the complexity of the description, because there is no complexity in the description. Splitting is a move is the whole of the mechanism, and one bit of the rule is the whole of the warning.

And when a code does settle, expect the answer to be either much smaller than the rule or very much larger, and not much in between. Twenty-four of the forty-four come in at or under the rule’s own size. Eight come in at sixteen times it or more. The middle of the range is thin, which is a distribution nobody would predict from a rule table and is the reason a bound instead of an answer is so rarely useful here — a bound covering both ends of that range covers everything and says nothing.

That thinness is the last thing worth carrying, because it is the one result in this essay that a reader could act on without computing anything. Faced with a new code and no time to run it, the useful prior is not a number in the middle. It is that the answer will almost certainly be either trivial or intractable, and that finding out which takes the same computation either way. A subject where the easy cases and the hard cases are separated by nothing observable is a subject where the only honest move is to run it, which is what everybody who has worked on these games has done and why the tables are the literature.