Two players, two lists

A heap of counters and a rule saying how many may be taken. Take one, three or four is the impartial version and its whole theory fits on a strip: compute the Grundy value of each heap size, watch the sequence settle into a repeat, and every question about every heap of every size is answered by a table that fits on a card.

Change one thing. Give Left the list $\{1, 2\}$ and Right the list $\{1, 3\}$. Everything else is the same: one heap, alternate turns, a player who cannot move has lost.

The impartial table has become a sequence of game values, and the question is whether it still settles down. The answer is that half of it does.

The one question that still has an answer #

Ask only who wins, and the sequence is as well behaved as anybody could want.

That is not a fluke of this pair. Every pair of finite lists gives an eventually periodic outcome sequence, which is Fraenkel and Kotzig’s theorem from 1987, and it is the whole of what the partizan version inherits from the impartial one. The outcome of a heap of a hundred thousand counters is available from a table with a handful of entries in it, and the table is computed once.

The sweep below runs the period search on six pairs of lists, and the assertion in the code is that every one comes back with an answer. A pair whose outcomes had no period inside the window would contradict the theorem, and would mean the recursion was wrong rather than that something had been discovered.

The question that stops having one #

The value sequence is a different object and behaves differently. For $\{1,2\}$ against $\{1,3\}$ the search finds no repeat at all inside sixty heaps, and the reason is visible in the values themselves: they get older.

A value whose birthday is twenty-one is a form nested twenty-one levels deep, and no two such forms of different depths can be equal. So the curve climbing is not weak evidence that the sequence fails to repeat: it is a proof that it has not repeated yet, since a repeat requires two equal values and equal values have equal birthdays.

The two facts sit side by side and are worth stating together. From heap four onward, every heap is a win for Left. From heap four onward, every heap is worth something nobody has seen before.

Why the outcomes must repeat, and the values need not #

The theorem is quoted above; the reason behind it is short enough to give, and giving it is what makes the failure on the other side legible.

Let $m$ be the largest number in either list — three, for $\{1,2\}$ against $\{1,3\}$. Every option of a heap of $n$ counters is a heap of between $n-m$ and $n-1$, so the outcome of heap $n$ is decided entirely by the outcomes of the previous $m$ heaps. Slide a window of that width along the sequence and each position of it holds an $m$-tuple of outcome classes, and there are only four classes, so there are at most $4^m$ distinct windows in existence. The sequence is generated by a rule that reads the window and writes one more letter. Two equal windows must therefore be followed by equal letters for ever, and by the pigeonhole principle two equal windows must occur within the first $4^m + 1$ heaps.

That is the whole proof, and three things about it are worth pulling out. It is constructive: it does not merely assert a period, it says where to stop looking. It bounds the preperiod and the period together, so the certificate the sweep asks for — two full copies past the preperiod — is a finite check with a known ceiling. And it never mentions which games these are. Nothing in it uses subtraction; any rule whose options reach back a bounded distance and whose answers come from a finite alphabet has an eventually periodic answer sequence.

The last clause is where the value sequence falls out of the argument, and it falls out at the alphabet rather than at the window. The value of heap $n$ is also decided by the previous $m$ heaps — the recursion is the same recursion, the window is the same width. What has changed is that the entries are games rather than letters, and there are infinitely many games. The window can take infinitely many states, so no two of them need ever agree, and the pigeonhole has nothing to be applied to.

This is why the birthday curve is the right thing to have drawn. It is not a second, independent piece of evidence that the values do not repeat; it is a direct measurement of the quantity the proof needs and cannot get. A sequence of forms whose depths are unbounded is a sequence drawn from an infinite alphabet in the strongest sense — no finite set of values contains them all — and the climbing curve is that alphabet being exhausted in front of the reader, one heap at a time.

What the bound is worth here #

The proof gives $4^m$ as the place to stop looking, and for these lists $m = 3$, so sixty-four heaps certifies the outcome sequence of $\{1,2\}$ against $\{1,3\}$ completely. The sequence in fact has period one from heap four.

A factor of sixteen between the bound and the fact is not a defect in the proof, and it is the same gap the impartial side has been living with for fifty years. The period is small and the proof does not say so is that story on the Grundy sequences, where the gap runs to four orders of magnitude: a pigeonhole argument counts every window the alphabet allows, and the windows a real game actually visits are a vanishing fraction of them. The bound is honest about what it knows, which is nothing about the game beyond its arity.

What the gap costs in practice is nothing at all, because the search reports where it stopped. Sixty heaps swept against a sixty-four heap ceiling means the outcome answers here are not empirical at all — they are complete, and the sweep could have said so.

Why the impartial theory promised both at once #

The gap is strange because in the impartial case there is no gap. A Grundy value is an outcome — of the heap added to a Nim heap of each size — so the periodic table answers both questions with the same entries. Knowing $\ast 3$ is knowing who wins that heap and knowing who wins it beside anything else.

That is testable inside this game rather than by pointing at a different one. Hand the same solver two identical lists and nothing about the machinery changes — the same recursion, the same canonical forms, the same two period searches — but the game being solved is impartial again, and the split ought to close.

Nothing was assumed to make that happen. The solver does not know the lists are equal and has no impartial branch in it; the nimbers arrive because equal lists make every Left option a Right option, and a form whose two option sets agree reduces to a nimber.

The reason the partizan version loses this is that a partizan value carries information the outcome does not. Two positions with the same outcome can behave completely differently in a sum: outcomes do not add, and the value is precisely the object that does, since two positions are equal when they are equal in every company. So the value has to distinguish more positions than the outcome does, and here it distinguishes all of them.

That makes the partizan case an unusually clean illustration of a general point. A complete invariant for sums is a much stronger thing than a rule for who wins, and the price of the first is that it need not repeat.

The pair that does repeat, and why #

Two of the six pairs in the sweep have a periodic value sequence, and both are instructive.

That is the mechanism. Depth accumulates when a heap’s options are themselves deep, and a heap’s options are deep when there are several of them pointing at different places. With one move each, the tree is a path and the reduction flattens it. With two moves each and the lists overlapping in only one entry, every heap’s form has two Left options and two Right options that reduce to different things, and the depth ratchets upward.

The other periodic pair, $\{1,2,3\}$ against $\{2,4\}$, repeats with period five from heap five and its deepest value is four days old. It is the pair whose lists overlap most: Right’s moves are both available to Left, which means Left can always answer a Right move by imitating it, and the imitation collapses most of the tree.

What the values look like on the way up #

The forms in the climbing sequence are not arbitrary. The first few are $0$, $\ast$, $\uparrow$, $\uparrow\!\ast$, $\{\uparrow \mid \ast\}$, $2\!\cdot\!\uparrow\!\ast$, $\Uparrow$ — a walk through the small infinitesimals — and after that they become $\{0 \mid \{0 \mid \{0 \mid \dots\}\}\}$, a left-leaning stack that grows one level at a time.

Only one of the first sixty-one is worth a number, and that is heap zero. Every other heap in this pair is worth something no number reaches, which puts the whole family in the all-small neighbourhood and makes every heap confused with zero or better: a player has a move exactly when their opponent does, because both lists contain $1$ and a heap with a counter in it can always be reduced by one.

The contrast with the impartial side is a collapse rather than a shorter table, and it is worth saying in that form. Take one, three or four gives every heap a nimber, and a nimber is a closed form for the heap: the position is a Nim heap of that size, in every company, for ever, and the four symbols the sequence uses are the whole vocabulary the game will ever need. Here the two lists differ, so no heap equals a heap of anything, there is nothing simpler for a value to be equal to, and the form has to carry itself. That is why the sequence has sixty-one distinct entries in sixty-one heaps rather than four.

What the split costs a player #

The two halves of the answer are useful for different things, and the difference is not academic.

A player sitting in front of a single heap wants the outcome, and the outcome is cheap. That is the ordinary situation in a puzzle and the unusual one in a game: real boards break into parts, and a rule for a single part is a rule for a case that rarely arises. Four entries and a rule — from heap four onward, Left wins — settles every position of this game there will ever be, and the table fits on a card.

A player sitting in front of several heaps of the same game wants the value, and the value is what has no table. The outcome of a sum is not a function of the outcomes of its parts, so the card is useless the moment a second heap appears on the board; what is needed is the value of each heap, and those are all different and all deep.

So the theorem and the failure are not a good half and a bad half of the same result. They are answers to two questions, and the one with the periodic answer is the one that does not compose.

What the solver computed, and how #

The values are built upward rather than by recursion from the top. Every option of heap $n$ is a smaller heap, so one pass fills a table of sixty-one canonical forms and nothing is evaluated twice.

The two period searches run on genuinely different sequences. Outcomes are one of four letters and compare as letters. Values are compared by canonical key — the interned identity of the reduced form — rather than by their printed names, because the printer truncates below depth three and two different deep values print as the same string of dots. A period read off the printed forms would have reported repeats in every one of the four pairs that have none, which is exactly the mistake the key exists to prevent.

A period is only reported when two full copies of it fit inside the window past the preperiod, and the window is reported with the answer. “No period inside sixty-one heaps” is a statement about a search; “period one from heap four” is a statement about a sequence, on the strength of thirty-seven further heaps agreeing.

The three-move pairs, and where the depth comes from #

Setting the two lists side by side makes it possible to say roughly when the values will climb.

Depth is manufactured at a heap when the mover’s options reduce to several different things and none of them dominates the rest. If the two lists are equal the game is impartial and every heap collapses to a nimber — no depth at all, ever. If one list contains the other, the larger player can imitate and the tree flattens a great deal. If the lists are of size one, each heap has one option a side and there is nothing to dominate.

What is left is the case where the lists are different, both have more than one entry, and neither contains the other. That is the case in which the two players are genuinely playing different games on one board, and it is where every partizan complication on this site comes from. All four of the pairs with no value period in the sweep are of that shape, and both of the pairs that do repeat fail it.

That is a description rather than a theorem, and it is offered as one. What would make it a theorem is a bound on the birthday in terms of the two lists, and no such bound is computed here.

Who found it, and what they were after #

Fraenkel and Kotzig proved the outcome result in 1987, in a paper about partizan octal games rather than about subtraction specifically. The context matters: the impartial theory had by then produced periodicity results for whole families of games, and the natural question was how much of that machinery survived the move to partizan rules.

The answer they gave is the one drawn above and it is a careful answer. Outcomes are eventually periodic; values are not claimed to be. Later work — Fraenkel and Kotzig’s own, and then a line of papers through the 2000s — showed that for particular families the values do settle, and the shape of the condition is the one this sweep gestures at: the lists have to be related, by containment or by equality, for the depth to stop accumulating.

What has not appeared is a general theorem in the other direction. Nobody has a description of the values of $\{1,2\}$ against $\{1,3\}$, and nobody has shown there is none. That is an unusual position for a game this easy to state, and it is the same position Grundy sequences are in on the impartial side — a rule three words long whose behaviour resists description.

That reframes what the search should be looking for. Two full copies of the period is the certificate the sweep demands, and it is stricter than it needs to be in one direction and weaker in another. What actually certifies an outcome sequence for ever is a repeat of the window: if the last $m$ outcomes match $m$ consecutive outcomes seen earlier, the rule that generates the next letter is being fed exactly what it was fed then, and everything after must agree. A period of one from heap four is certified the moment heaps four, five and six match heaps five, six and seven — at heap seven, not at heap sixty.

Where the two rules diverge is on the pairs with a longer reach. $\{1,2,3\}$ against $\{2,4\}$ has $m = 4$, so its ceiling is two hundred and fifty-six heaps and the sweep ran sixty; its period of five from heap five is nonetheless certain, because five exceeds four and the window has demonstrably repeated. The ceiling is the worst case over all games with that reach, and a particular game reaches its own repeat whenever it happens to.

Where the model stops #

Sixty-one heaps and six pairs of lists. The theorem about outcomes covers every pair of finite lists and is quoted rather than proved here; what is computed is that six particular pairs obey it, which is a check on the recursion rather than evidence for the theorem.

The negative claim is weaker than it looks and is stated in its weak form throughout: four of the six pairs have no value period inside sixty-one heaps. A period beginning at heap two hundred would be invisible here. What makes the negative worth reporting anyway is the birthday curve, which is not a search: a sequence whose birthdays are unbounded cannot repeat at all, and the curve for $\{1,2\}$ against $\{1,3\}$ is rising steadily with no sign of levelling. Rising steadily is not unbounded, and the gap between those two statements is exactly what this site cannot close.

Where the ladder goes next #

This rung establishes the split: outcomes periodic, values not. The rung above is the question of what the values are — whether the climbing sequence has a description, since a sequence of forms that grows by one predictable level each time is a sequence with a pattern even if it has no period.

Two neighbours are worth the trip. The period is small and the proof does not say so is the impartial version of the periodicity question, where the fact and the bound are four orders of magnitude apart. And where the impartial theory stops is the general account of what a single number can and cannot carry.