A sequence with a rule and no period

Two players, two lists evaluated the subtraction game in which Left may take one or two counters and Right may take one or three, and found a split: the outcomes settle after four heaps and never change again, while the values climb for ever and repeat nothing. It closed on the obvious question:

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.

There is a description. It is one line.

$$v(k + 3) = \{\,0 \mid v(k)\,\} \quad \text{for every } k \ge 2.$$

Three seeds — $v(2) = \uparrow$, $v(3) = \uparrow\!\ast$, $v(4) = \{\uparrow \mid \ast\}$ — and that recursion generate the entire sequence.

What the rule says #

Read out loud: the value of a heap three larger is the game with nothing on Left’s side and this value on Right’s.

$\{0 \mid v(k)\}$ is a position where Left’s only move is to nought and Right’s only move is to $v(k)$. That is a very lopsided little game, and it is the shape of every value in this sequence from heap five on.

The mechanism is visible in the two lists. Left may take one or two; Right may take one or three. From a heap of $k+3$, Right’s take of three lands exactly on $v(k)$ — the same value, three heaps down — and the recursion says that after the reduction, that is Right’s only surviving option and Left has nothing better than nought.

Everything else — Left’s two moves, Right’s move of one — is dominated or reversed away. So the rule is not a coincidence about the numbers: it says that in this game a large heap is decided by Right’s biggest take and by nothing else.

That is a surprisingly strong statement about a game whose two lists look nearly the same. Left and Right both have a take of one; the whole asymmetry is that Left’s second take is two and Right’s is three. One counter of difference, in one entry of one list, and the value of every large heap is a nested expression built out of Right’s larger move with Left’s options thrown away at every level.

Why there is no period #

A period would mean $v(k) = v(k + p)$ for some fixed $p$ and all large $k$. The rule rules it out immediately.

Each application of $\{0 \mid \cdot\}$ adds a level to the form. So the birthday of $v(k+3)$ is one more than the birthday of $v(k)$, and the birthdays climb: 3, 3, 3, 4, 4, 4, 5, 5, 5, and so on, reaching fifteen at heap forty.

A value with birthday nine cannot equal a value with birthday six, so the sequence cannot repeat. Both halves are asserted in the code rather than described — a heap born on the wrong day, or a value recurring anywhere in the sequence, stops the build.

That is the whole of the impossibility, and it is worth noticing how cheap it is. Establishing that a sequence has no period is normally a matter of computing very far and hoping — the octal codes nobody has settled have been computed to billions of terms without an answer. Here it takes a monotone quantity and one line.

The technique, and its weaker form #

The birthday argument is cheap in a way worth generalising, because the same move appears elsewhere on this site at a weaker strength and it is easier to recognise once named.

To rule out a period, exhibit a monotone invariant. Find a quantity attached to each term that never decreases along the sequence and is not eventually constant. Two terms with different values of it cannot be equal, so no term can recur, so there is no period — and none of that requires computing far.

Here the invariant is the birthday, and it is strictly increasing every three heaps. That is the strong form: strict monotonicity rules out repetition outright, at any length, with no search.

The weak form is on this site too. The alphabet of an octal game’s Grundy sequence — how many distinct values have appeared so far — is non-decreasing by construction, and it is not strictly increasing: it can sit still for a thousand heaps. So it cannot rule out a period. What it can do is bound one: every value that ever occurs occurs within the first preperiod-plus-period terms, so if the alphabet is still rising at heap $N$, then preperiod plus period exceeds $N$.

Same technique, two strengths, two conclusions. A strictly monotone invariant says no period exists. A merely non-decreasing one, still moving at the edge of the window, says any period is longer than the window. The first is a theorem about the sequence and the second is a theorem about the search.

Which is why the split in this game is one argument #

That framing closes the loop with the rung below, where the outcomes of this same game repeat and its values do not.

The two halves are the same pigeonhole run on two alphabets. Outcomes come from a four-letter alphabet, so a window of them is one of finitely many states and a repeat is forced — that is the theorem the rung below quotes. Values come from an alphabet with no finite bound, so nothing is forced, and the window argument has nothing to be applied to.

The birthday is what makes the second half sharp rather than merely unforced. Nothing forces a repeat is a statement about an argument failing; the birthdays climb is a statement about the sequence, and it converts an absence of proof into a proof of absence.

So the game’s famous split is not two phenomena. It is one counting argument, run twice, with the alphabet size deciding both answers — and the invariant that settles the harder half is the same kind of object that settles the easier one, measured on a quantity that happens to be unbounded.

That is worth carrying to the next game with a suspicious sequence in it. The question to ask is not does this repeat but what is the alphabet, and is anything about the terms monotone — and both are usually answerable without computing very far at all.

A pattern without a period #

The two properties together are the point, and they are not usually found together.

The sequence is completely described. Any heap’s value can be computed in $k/3$ steps from a seed, without evaluating anything: no game tree, no canonicalisation, no search. That is what a closed form buys.

And it never repeats. Thirty-one heaps, thirty-one distinct values, and the argument above says the same is true at any length.

An impartial subtraction game cannot behave like this. Grundy sequences are eventually periodic for every finite subtraction set — that is a theorem, and the reason is that a Grundy value is a bounded natural number, so a window of the sequence determines everything after it and the windows must eventually repeat.

Partizan values are not bounded. They are trees, they can be arbitrarily deep, and a sequence of them has no finiteness to force a repeat. So the partizan game is free to have exactly what this one has: a rule and no period.

The outcomes, which do settle #

The contrast inside one game is sharper than the contrast between two games.

The outcome sequence of this game is eventually periodic — it settles after four heaps and never changes. So the same position sequence has one quantity that repeats for ever and another that never repeats, and both are true of the same heaps.

The reason is the same boundedness argument run on a coarser object. An outcome is one of four letters, so the sequence of outcome-windows is finite and a repeat is forced. A value is a tree and no such argument applies.

That is a clean instance of a thing this subject does constantly: the answer to who wins has a completely different character from the answer to what is it worth. Knowing who wins, and knowing what it is worth prices the two computations against each other; this page is the same distinction showing up in the shape of an infinite sequence rather than in a running time.

Reading the values #

The forms the rule produces are worth reading, because they say what the game is doing and the names change character twice.

Heaps two to six are the familiar infinitesimals: $\uparrow$, $\uparrow\!\ast$, $\{\uparrow \mid \ast\}$, $2\!\cdot\!\uparrow\!\ast$, $\Uparrow$. A reader who has met the infinitesimals recognises every one, and the game looks like an ordinary source of small positive values.

Heaps seven to twelve are still nameable but no longer familiar: $\{0 \mid \{\uparrow \mid \ast\}\}$, $3\!\cdot\!\uparrow$, $3\!\cdot\!\uparrow\!\ast$, and so on. The multiples of up keep arriving on two heaps in three, and the third is a nested expression with nothing standard about it.

Past heap thirteen the names stop being names. $\{0 \mid \{0 \mid \{0 \mid \{\uparrow \mid \ast\}\}\}\}$ is a value written as its own construction, because there is no shorter way to say it, and by heap sixteen the printed form is truncated for want of room.

That is the sequence’s whole trajectory in one sentence: it starts in the vocabulary a reader has and leaves it, and the rule is what carries on when the vocabulary stops. A description that survives the point at which the names run out is worth more than the names were.

Whether the rule is a law #

The honest question is whether the description is a fact about this pair of lists or about partizan subtraction games in general, and it is the first.

$\{1\}$ against $\{2\}$ has values of period three — three distinct values in thirty-one heaps — and needs no rule. $\{1,2,3\}$ against $\{2,4\}$ has period five above a preperiod of five. Both are cases where the values are bounded after all, because the lists are small enough that nothing accumulates.

The other three pairs climb like the headline pair — thirty distinct values in thirty-one heaps — and no step size from one to six produces a rule for any of them. So a climbing sequence does not come with a description as a matter of course, and the one here was worth finding rather than assumed.

Thirty of thirty-one rather than thirty-one is worth a note: those sequences repeat exactly one value, at the bottom, where two small heaps happen to be worth the same thing. Past that they are as aperiodic as the headline pair and considerably less tractable, since neither a period nor a rule describes them and the only way to answer a question about heap forty is to build forty heaps.

What makes this pair special #

Looking at why $\{1,2\}$ against $\{1,3\}$ has a rule and $\{1,3\}$ against $\{2\}$ does not is the most useful thing on this page for anybody who wants the general statement.

The rule works because Right’s largest take, three, is exactly the step size, and because everything else reduces away. Right taking three from $k+3$ lands on $v(k)$; Left’s takes of one and two land on $v(k+2)$ and $v(k+1)$, which are deeper than $v(k)$ — and a deeper option on Left’s side of a lopsided game is dominated by nought.

In $\{1,3\}$ against $\{2\}$ the step that would work is two, and Left’s take of three interferes: it reaches back past the step and the reduction does not clear it. That is a difference in the arithmetic of the lists rather than in anything about games, which is what a general theorem here would have to be about.

What a player would do with it #

The values are exotic and the practical reading is not.

Every value in the sequence from heap two on is a positive infinitesimal or a lopsided game with nought as Left’s only option — which is to say Left is winning every one of these heaps, by a margin no number measures. That is the outcome result the rung below found, arrived at from the value side.

The positivity is immediate from the rule and is worth spelling out, because it is the one thing about the sequence a reader can verify without computing anything. If $v(k) > 0$ then $\{0 \mid v(k)\} > 0$ too: Left moving first plays to nought and Right, facing nothing, loses; Left moving second waits while Right plays to $v(k)$, which Left is already winning. So the rule preserves positivity, the three seeds are positive, and every value in the sequence is.

What the values add is the ordering. On a board of several heaps from this game the outcome is decided by the sum, and a sum of infinitesimals is decided by their relative sizes rather than by counting them. A heap of twelve is worth $4\!\cdot\!\uparrow$ and a heap of eight is worth $3\!\cdot\!\uparrow$, so two heaps of eight beat one of twelve — which no outcome table says and no periodicity would help with.

So the sequence’s aperiodicity has a cost a player pays. There is no window of the value table that determines the rest, which means a lookup table for this game is unbounded, and the rule above is the only way to answer a question about a large heap without evaluating it.

What the sweep does not settle #

Forty heaps is where this stops, and the rule is checked on every application inside that window. It is a check rather than a proof: the argument for why Left’s options reduce away is given above in words and is not carried out as an induction, so a heap at which the reduction behaved differently would falsify the rule and nothing here rules one out beyond forty.

The three pairs with no rule found were tried at step sizes one to six. A larger step would be a different search and might succeed; the negative result is about the steps tried and is stated that way in the figure.

And the description is of one sequence rather than of the game. A subtraction game is played on a heap, but a board of several heaps is a sum, and nothing here says how the values add. The sum of two of these values is a game whose birthday is bounded by the two together, which by the birthday of a sum is a bound and rarely much better — so a two-heap position in this game is already an object of some depth.

The convention, named #

Normal play throughout: the player unable to take loses, which for a subtraction game means the player facing a heap smaller than their smallest listed take. Left’s list is $\{1, 2\}$ and Right’s is $\{1, 3\}$; both may take from the same single heap, and there is nothing partizan about the board — only about the lists.

Every value was computed by building the heaps upward, since every option of a heap is a smaller heap, and reduced to canonical form. The period searches compare values by canonical key rather than by printed name, because the printed form truncates below a certain depth and two different values can print the same way. Reading a period off the printed names is the mistake the machinery here exists to avoid.

Where the ladder goes next #

partizan-subtraction has two rungs: the split between outcomes and values, and now a description for the climbing half of it.

The rung above is the induction. The rule is checked at forty heaps and argued in words; making it a theorem means showing that Left’s options are dominated at every heap, which is an induction on the reduction rather than a computation. It is the sort of statement that either falls out in a paragraph or needs a careful invariant, and either way it would turn a measurement into a fact.

Beyond that is the general question the three ruleless pairs pose: 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.

Two neighbours are worth the trip. Two players, two lists is the rung below, where the split between the two quantities is established. And the period is small and the proof does not say so is the impartial version of the periodicity question, where a period is guaranteed to exist and the bound on where it starts is four orders of magnitude out.