The condition that survived the wider sweep

A partizan subtraction game gives each player their own list. Left may take any amount on Left’s list, Right any amount on Right’s, and the position is a heap of counters. Two players, two lists is where the game arrives and where the split appears: the outcomes settle into a repeating pattern and the values do not, and the two questions come apart completely.

A sequence with a rule and no period described the climbing half of one pair and closed on the general question:

Which pairs of lists give a describable value sequence? The answer here turns on the arithmetic of the two lists and not on anything about games, which makes it a question a reader could attack with no game theory at all.

Attacking it produces a lesson about sweeps before it produces one about games.

Two conditions that look the same #

Draw the lists from $\{1, 2, 3\}$ and there are 49 pairs. Nineteen of them have a value sequence that repeats, and two conditions pick out exactly those nineteen.

A translation. Right’s list is Left’s with a constant added to every entry — $\{1,2\}$ against $\{2,3\}$, or any singleton against any other, or the two lists equal, which is a shift of nought.

All odd. Every entry of both lists is odd: $\{1\}$, $\{3\}$, $\{1,3\}$ and the nine pairs among them.

On the small lists these two conditions are indistinguishable. Every pair satisfying one satisfies the other or is covered by it, they hold on nineteen pairs between them, and those are precisely the nineteen that repeat. Either could be stated as the answer and neither would be contradicted.

They are not the same condition. $\{1,3\}$ against $\{1\}$ is all odd and is not a translation; $\{1,2\}$ against $\{2,3\}$ is a translation and is not all odd. That the two coincide on the small lists is an accident of the range, and separating them means widening it.

Widening it #

Lists drawn from $\{1, \ldots, 5\}$ give 31 lists and 961 pairs. Each is evaluated to heap thirty and its sequence of canonical values searched for a period up to fourteen.

Two hundred and seventeen of the 961 repeat.

All 83 translations are among them. Not one translation fails, at any shift from nought to four, and the periods are small — nothing runs longer than ten.

Four all-odd pairs are not. $\{3\}$ against $\{3,5\}$, $\{5\}$ against $\{3,5\}$, and the two with the lists exchanged have no period at all.

Those four are not near misses. No period found is a statement about a window, so the census re-searches each of the four to heap ninety with a period as long as forty-two — three times as far in both directions — and finds nothing, and throws if it ever does. The all-odd condition is refuted rather than strained.

The asymmetry between the two failures matters. The translation condition is a claim about 83 pairs and every one of them holds; the all-odd condition is a claim about 49 and 45 hold. Forty-five out of forty-nine is the kind of score a condition can survive by being called nearly always — and calling it that would be the mistake, because the four failures are not marginal cases at the edge of the range. They involve the lists $\{3\}$, $\{5\}$ and $\{3,5\}$, which are as ordinary as anything in the sweep.

What the surviving condition says #

A shift of nought is the two lists being equal, which is the impartial subtraction game. Its Grundy sequence is eventually periodic, and that is a theorem rather than an observation — it has been known since the subject had a name, and it is the reason the impartial half of this subject is tractable at all.

So the surviving condition is best read as an extension of that theorem rather than as a new fact. Shift one player’s list by a constant and the sequence still repeats — 30 pairs at a shift of one, 14 at two, 6 at three, 2 at four, and every one of them.

Why a shift should be harmless is not obvious and is not settled here. The natural line of attack is that a shift of $c$ makes Right’s game Left’s game played $c$ heaps behind, so the two sequences are the same sequence read at an offset and whatever repetition one has the other inherits. That is a sketch and it has a visible weak point — the values are built from both players’ options at once, so the two sequences are not independent — and turning it into a proof is a rung rather than a remark.

The two pairs, drawn #

The difference between the two conditions is visible on one pair each.

$\{1,2\}$ against $\{2,3\}$ is a translation by one and is not all odd. Its values repeat with period four from the first heap, and they keep repeating for as far as the sweep runs.

$\{3\}$ against $\{3,5\}$ is all odd and is not a translation. Its values climb — deeper forms at bigger heaps, in the way the rung below measured for its own headline pair — and there is no repetition to find.

The contrast is one clause and it is the whole page: the sizes of the entries decide nothing and their arrangement decides everything. Both of Right’s entries here are odd and both are within one of Left’s, and the sequence still runs away; move Left’s single entry to make the two lists a translation and it stops.

Neither condition is necessary #

The two conditions between them cover 128 of the 961 pairs. Two hundred and seventeen repeat. A hundred and four pairs repeat that are neither translations nor all odd, and they are the majority of the periodic ones.

$\{1\}$ against $\{2,5\}$ repeats with period three from the first heap. $\{1,2\}$ against $\{1,2,4\}$ repeats with period three. $\{2,3\}$ against $\{1,4,5\}$ repeats with period seven. Nothing in the arithmetic of those lists resembles a shift, and each has an even entry.

Two features of that residue are worth recording for whoever attacks it next. The periods are small — three, three, seven, and nothing in the whole sweep past ten — so a sequence that repeats at all repeats quickly, and the census’s period bound of fourteen is generous rather than tight. And the preperiods are usually nought — 140 of the 217 — so a partizan subtraction sequence that settles has generally settled from the first heap, which is unlike the impartial case, where a long irregular prefix before a short period is the normal shape.

Both of those cut the same way, and it is the useful way. If a partizan pair repeats at all it repeats early and it repeats fast, so a sweep looking for the boundary does not need a long window: it needs a wider range of lists. The expensive dimension of this census is the one that costs nothing, and the cheap one is the one that is limited.

So what the sweep has produced is a sufficient condition and no necessary one. That is worth saying plainly rather than presenting a partial answer as an answer: the question the rung below asked was which pairs, and the honest reply is that one large family always works, several times as many pairs work for reasons this census cannot state, and the boundary is not in view.

Why the small sweep was bound to mislead #

It is worth being precise about how the 49-pair sweep failed, because the failure is not that it was wrong.

Everything it reported is true. Nineteen pairs repeat, the two conditions hold on exactly those nineteen, and the rung below drew the right conclusion from the evidence it had. What it could not do is distinguish the two conditions, because the range $\{1,2,3\}$ contains no pair on which they differ.

A condition separating them needs an all-odd pair that is not a translation and whose sequence runs away, and the smallest such pair uses a five. There is no five in $\{1,2,3\}$. So the small sweep did not fail to notice a counterexample; it did not contain one.

That is the ordinary way an exhaustive sweep goes wrong, and it is worth naming because exhaustive sounds like it should not be able to. A sweep exhausts a range, and a claim about all pairs is a claim about a range it does not exhaust. This collection has produced the same shape of finding once already — five hexadecimal codes all had a saltus that was a power of two, and the exception is one code in seventy-one — and the two together suggest the standing rule: a pattern that holds on every case is only as strong as the case a counterexample would have needed.

Here that number is nameable. It is five, the range was three, and nothing about the small sweep could have said so.

What the census had to avoid measuring #

One implementation note is worth recording because it is the difference between a sweep that runs and one that does not.

The first version of this census reported each pair’s largest birthday beside its period — how deep the values get, which is the quantity the rung below used to show the sequences climbing. Finding a birthday means walking a whole canonical form, and on a form born on day thirty that walk is the entire cost of the census: fifty-eight seconds with the column and under three without it.

The column was not needed. Whether a sequence repeats is a question about the keys of the canonical forms, and comparing keys is a string comparison. The measurement that was interesting on one pair was the measurement that made 961 of them unaffordable.

That is the same shape as the finding the rung below recorded about name(): a period read off printed names is wrong because names truncate below depth three, and a period read off keys is right and cheaper. The expensive thing and the wrong thing were the same thing twice over.

What the sweep does not say #

Four limits.

A period search is not a description. The rung below’s finding about its headline pair was not a period at all: the values there satisfy a three-term recursion and never repeat, which is a perfectly good description of a sequence that this census would report as having none. So repeats is a narrower question than is describable, and the 744 pairs reported here as not repeating include an unknown number that are describable in some other way.

That is the largest gap in this page and it is a gap in the question rather than in the answer. Widening it would mean testing a family of candidate descriptions rather than one, and the rung below’s recursion is the only one this site has.

Five is not many. The whole finding is that three was not enough to separate two conditions. Nothing says five is enough to separate the surviving one from a third condition nobody has thought of, and the right expectation, given how this page went, is that it is not.

Thirty heaps and a period of fourteen. A pair reported as not repeating has not repeated inside that rectangle. The four exceptions are re-checked three times as far; the other 740 are not, so some of them will repeat further out and the count of 217 is a floor.

The condition is checked, not proved. Eighty-three translations repeating is a strong sweep and it is not the theorem. The sketch above is where a proof would start and the sketch has a hole in it.

And the lists are sets, not multisets, and start at one. A subtraction list containing nought would let a player pass, which is a different game entirely, and lists with gaps beyond five — $\{1, 9\}$, say — are outside the sweep and are where a translation by a large constant would be tested.

What survives a widening and what it means #

A condition holding on a wider sweep is worth something, and it is worth being precise about how much, because the natural reading over-claims in a specific way.

Surviving a widening rules out one explanation. Before the sweep, a condition that fits could be a real regularity or an artefact of the pool; after it, the artefact explanation is much weaker, because an artefact of the first pool would have to be an artefact of the second too.

It does not rule out a shared artefact. If both pools are built by the same construction, drawn from the same day, or bounded by the same size cap, then they share whatever biases the construction has — and a condition tracking one of those survives every widening along an axis that does not touch it. The entry fee that was a cap is the standing example on this site: a quantity stable across rulesets and destroyed by looking at it against depth.

So the useful question after a survival is which axis was widened. More positions of the same kind is the weakest widening; a different construction is the strongest; and a widening along the axis the condition is stated in is nearly worthless, since the condition was fitted to it.

That gives the report a shape. Say what varied, not how much data there was — because a condition surviving ten times the positions along one axis has been tested once, and a condition surviving two pools built differently has been tested twice.

What a reader should take from it #

Two things, and the second is the one that generalises past this game.

A translation is safe. If the two lists are the same list with a constant between them, the values repeat, the period is under ten, and it usually starts at the first heap. That covers the impartial game and 52 partizan pairs besides, and it is the only part of this question anybody currently has an answer to.

And a condition that fits every case in a small range has been tested against that range and not against the claim. Both conditions here were exactly right on 49 pairs. One of them stays right on 961 and the other does not, and no amount of care applied to the 49 could have told them apart — the evidence that separates them is simply not in the range. The remedy is not more rigour; it is a wider sweep, and knowing in advance how wide it has to be.

The convention, named #

Normal play: the player who cannot move loses. A position is a heap of $n$ counters; Left’s options are $n - s$ for each $s$ in Left’s list with $s \le n$, Right’s likewise.

A value here is the canonical form, computed by the recursion and compared by its canonical key. Repeats means the sequence of values is eventually periodic: there is a preperiod and a period such that every value from the preperiod onward equals the one a period earlier, with at least two full periods inside the window.

A translation is Right’s list being Left’s with one constant added to every entry, which requires the lists to be the same length. A shift of nought is the two lists being equal and is the impartial game.

Where the ladder goes next #

The partizan-subtraction anchor has three rungs: the split between outcomes and values, a description for the climbing half of one pair, and now which pairs have a description at all.

The rung above is the proof of the translation result, and it is the best-posed open piece on this anchor. Eighty-three pairs repeat, the mechanism ought to be that a shifted list is the same game read at an offset, and the hole in that argument is nameable: the values are built from both players’ options simultaneously, so the two sequences are coupled and the offset argument has to say why the coupling does not matter.

Two neighbours are worth the trip. The period is small and the proof does not say so is the impartial version of this question, where the period exists by a theorem and the bound on where it starts is four orders of magnitude out — and it is a useful corrective, because a guaranteed period is not the same as a findable one. And naming a game with a number is where the same question is asked of the impartial family with a rule table instead of a pair of lists, and where the answer has been open since 1956.