A set with three descriptions, and a function with none

A solved game usually means one thing. Somebody has a rule that says who wins, the rule is short, and it runs faster than playing. Wythoff’s game is solved in that sense three times over, which is unusual enough to be worth staring at, and it is unsolved in another sense entirely, which is the part nobody mentions when they call it solved.

The game has two heaps. A move takes any number of counters from one heap, or the same number from both. The positions worth handing over — the ones where whoever must move loses — are the pairs (⌊nφ⌋, ⌊nφ²⌋), and Wythoff found them in 1907 with no notion of a Grundy value available to him. That set can also be built greedily, one pair at a time, by a rule with no constant in it at all. It can also be recognised from the digits of the heap sizes written in Fibonacci base, which is the version that runs on a heap of a trillion.

Three descriptions. Now ask the same table a slightly different question — not is this position lost, but what is this position worth — and every one of the three goes silent.

Three routes to one set #

The four columns are worth separating carefully, because the fourth is not like the first three.

The first is analytic. φ is a specific irrational number, ⌊nφ⌋ and ⌊nφ²⌋ are two sequences of integers built by multiplying and rounding, and the claim is that the nth cold pair is the nth term of each. Nothing in that sentence mentions a game.

The second is combinatorial and mentions nothing at all. Start with no integers used. At step n, take the least integer not yet used, call it a, set b = a + n, mark both used, and that is the nth cold pair. The whole construction is greed plus a counter. It produces (1, 2), then (3, 5), then (4, 7), then (6, 10), and it never once needs to know what φ is.

The third is arithmetic in the wrong base. Every positive integer is a sum of non-consecutive Fibonacci numbers in exactly one way, which gives it a numeral, and in that numeral system a pair is cold when the smaller number’s numeral ends in an even number of zeros and the larger’s is the smaller’s with a zero appended. Two conditions on digits, no multiplication, no rounding, no φ.

The fourth column is not a description. It is a mex table — for each position, list the values of everything reachable in one move, take the least non-negative integer not on the list, and a position is cold when that value is zero. It knows nothing about golden ratios, greed or Fibonacci numerals. It knows the rules of the game and nothing else, and it is the thing the other three are claims about.

Over every pair of heaps up to 220 the four name the same eighty-five cold positions and disagree nowhere. That is not a coincidence anybody should find surprising by now — it is a theorem several times over — but it is worth having the four counts sitting in one column, because the rest of this essay is about what happens when the question changes slightly and three of those four columns cannot be written down at all.

The reason to trust the agreement rather than assume it is that the digit rule, when it was first written here, was wrong. The shift condition on its own — the larger numeral is the smaller one with a zero appended — is necessary and not sufficient, and it certifies (2, 3), (5, 8), (7, 11) and every other pair of consecutive Fibonacci numbers as cold, which they are not. It passed 3,572 of 3,600 positions before the disagreement showed up. A rule that is right in 99.2% of a square looks exactly like a rule that is right, and the only thing that separates them is the fourth column.

What the rest of the table does #

The cold positions are the level set where the Grundy value is zero. The Grundy value itself is defined everywhere, it is what the Sprague–Grundy theorem needs if this game is ever going to appear inside a sum with other games, and it is a perfectly concrete object: a number for each pair of heaps, computed by mex, no ambiguity anywhere.

Ask for it in closed form and nothing arrives. Not from φ, not from greed, not from the digits. The three descriptions describe a set, and a set is a two-valued function; the Grundy function takes every value there is, and none of the three has anything to say about which.

What it does have, and this took some computing to see, is one law per row.

Fix the smaller heap at a and walk the larger one out along the row. That sequence turns out to be arithmetically periodic: past some column, adding p to the column adds s to the value, for a fixed p and s. It is the same class the octal game survey sorts codes into, and the same distinction that separates a sequence that repeats from one that climbs while repeating its shape — a game with an arithmetic period is settled and is not periodic, so a search looking only for repetition looks straight past it.

Two things about the answer are worth more than the fact of it.

The saltus is always the period. Every row, without exception, has s = p: add 768 to the column and 768 to the value. So a row past its onset is not merely regular, it is the identity shifted — the values climb at exactly the rate the column does, which is the most degenerate arithmetic period a sequence can have while still not being periodic. Row 0 is the extreme case and gives the game away: G(0, b) = b, because with one heap empty this is one-heap Nim, and its period is 1.

And the period doubles. Row 3 needs six entries to state, row 13 needs ninety-six, rows 21 through 26 need seven hundred and sixty-eight apiece. Over the first twenty-seven rows it doubles nine times. It also, exactly once, gets smaller — row 6’s period is 12 where row 5’s is 24 — so it is not even monotone, and any story about the doubling that does not have room for that one step is a story about something else.

The onset walks out with it. Row 3’s law holds from column 8. Row 13’s from column 382. Row 26’s does not start until column 2,314, which means that seeing it at all takes computing the first several thousand entries of a row and then throw almost all of them away.

The row that had no law #

The first sweep for this essay computed rows out to column 700 and reported that row 13 had no arithmetic period. That looked like a finding. Rows 0 through 12 all had laws, row 13 did not, and the natural reading is that the pattern breaks at thirteen and everything below is the unstructured part.

It was not a finding. It was a window.

Row 13’s law is a period of 96 starting at column 382, and the interesting part is the arithmetic of why 700 columns could not see it. Two full copies of the period past the onset need 382 + 192 = 574 columns, and 700 is comfortably more than 574. By the condition everybody states, the narrow window had enough data.

The search has a second condition, and it is the stricter one here. It will not accept a law whose onset falls in the second half of the sequence it was handed — the onset must be under n/2, so a law starting at column 382 needs 765 columns before the search is willing to call it a law. The narrow window was sixty-five columns short. Not short of the evidence: short of the conservatism.

That condition is not a bug and taking it out would be a mistake. It exists because a pattern that starts three-quarters of the way through what has been read has, by construction, almost nothing after it to fail against, and a “period” confirmed by two copies at the very end of a window is the exact shape of a false positive. The octal survey’s oldest open problems are sequences that looked settled for a very long time, and the survey’s discipline is to demand more data than the pattern strictly needs. The cost of that discipline is a false negative like this one, and the false negative is cheap: read further and it evaporates. The false positive is not cheap, because nothing makes it evaporate.

So the honest version of the row result is not “every row has a law”. It is: every row out to 26 has a law that this search, given six thousand columns, was willing to certify — and the search’s willingness is a number that can be stated. This site’s habit is that a claim gets a test it could fail, and a window is the test’s own limit rather than an afterthought about it.

The direction the move preserves #

A row fixes the smaller heap. There is another obvious way to cut the same table, and it is arguably the more natural one for this game: fix the difference between the heaps and walk both.

That is the cut the game’s third move runs along. Taking the same number from each heap leaves the difference alone, so a diagonal of the table is closed under the move that makes Wythoff’s game more than two heaps of Nim. If any direction were going to be structured, this is the one to bet on.

Thirteen diagonals, sixteen hundred terms each, searched for an arithmetic period up to seven hundred: nothing. Not one of them. The main diagonal begins 0, 2, 1, 6, 7, 8, 3, 5, 4, then jumps to 16, and by term 1,600 it has reached 2,430 — it climbs, roughly linearly, and it climbs in an order nothing has explained.

The asymmetry is the finding, and it is genuinely odd. Rows and diagonals are two foliations of the same table by the same recurrence. The rows all submit. The diagonals, including the one the game’s own move preserves, do not.

What a null result is worth #

A search that finds nothing has said something only if it could have found something, and the previous section is exactly the place to insist on that, because the section before it is a worked example of a null result being wrong.

So the diagonal figure prices its own window rather than describing it. Every law the rows of that same table are known to have gets tested against what the diagonal search would accept — period within seven hundred, onset within the first half of sixteen hundred terms — and the count that survives is what the figure prints. Seventeen of the twenty-seven row laws would have been found by the diagonal search, the deepest being row 16’s, whose period is 192 and whose onset is column 771.

That is a real statement and a bounded one. Laws of the shape the first seventeen rows have would have shown up in the diagonals and did not. Laws of the shape rows 17 through 26 have — onsets from column 865 out to 2,314 — would not have shown up, and about those the diagonals say nothing whatever. The search is not evidence that no diagonal law exists. It is evidence that no diagonal law of the kind this table is known to produce exists in that window, which is a smaller claim and the only one the arithmetic supports.

The alternative was available and would have been worse: run the diagonals in a window too small to detect anything, find nothing, and report it as though it meant something. That version of the figure would draw identically.

What each half costs to say #

Both halves of the answer can be priced in the same unit, which is the only way to compare them honestly: how many table entries would a reader have to be handed before they could work out any position themselves.

The cold set costs one rule. Not one rule per row — one rule, full stop, covering every row of the quarter-plane at once, and it does not lengthen as the heaps grow. Handed the digit condition, a reader settles (1836311903, 2971215073) with two digit operations and no table at all. That is the flat line.

The value function costs one law per row and the laws add up. Twenty-seven rows come to 6,685 entries, an average of 248 a row, and the average is misleading in the usual way: the early rows are nearly free and the recent ones are 768 each with the doubling still going. Add row 27 and it is not 248 more entries, it is 768, or 1,536.

That is the whole comparison, and it is worth being precise about what it is not. It is not that the values are unknowable — they are computed here, exactly, out to six thousand columns, by a recurrence anybody can write in ten lines. It is not that they are irregular; twenty-seven consecutive rows submitting to arithmetic periodicity is a great deal of regularity. It is that the regularity has no finite description. What the cold set says once for all rows, the value function says again for each row, at a doubling price, and the sum of a doubling sequence is dominated by its last term for ever.

Why the zero set is the easy part #

Something is being got for free in the first half of this essay, and it is worth naming, because it explains why three closed forms for one set is less miraculous than it sounds and why zero closed forms for the function is less disappointing.

The cold set is defined by a closure property rather than a computation. A set of positions is the cold set exactly when no move goes from one member to another and every non-member has a move into it. Those two conditions are checkable locally, they do not mention any value, and — crucially — they are the kind of condition a guess can be verified against. Wythoff guessed the Beatty pairs and verified the two conditions. The greedy construction is those two conditions turned into an algorithm: take the least unused integer precisely so that nothing below has been skipped, and set the difference to n precisely so no two pairs share a difference. The digit rule is the same set recognised in a base where the Beatty structure becomes a shift.

All three, then, are descriptions of a set defined by a property that a candidate can be tested for. The Grundy value has no such property. G(a, b) = 7 is not a local condition; it is a statement about the entire set of values below the position, and mex is a genuinely global operation — it depends on which numbers are missing, and that depends on everything. There is no analogue of “guess it and check the closure” for a value, which is why guessing has produced three answers on one side of the line and none on the other. The same asymmetry shows up wherever this site looks: a set the theory can characterise sitting beside a function it cannot, a strip whose winners are known and whose values are not, a sequence with a perfectly good rule and no period at all.

And this matters practically the moment Wythoff’s game stops being alone on the board. Deciding a single Wythoff position needs only the cold set, and the digit rule settles it in the time it takes to read the numerals. Deciding a sum — this Wythoff position beside a Nim heap beside something else — needs the value, because the nim-sum of the values is the only thing that combines. So the closed forms answer the question about the game in isolation, completely and three times over, and are silent on the question that made anybody define Grundy values in the first place.

The shape of the whole answer #

Put the two halves beside each other and Wythoff’s game is a nearly perfect specimen of a distinction that is usually blurred.

Two-heap Nim, drawn here against Wythoff on the same board, has a closed form for everything: G(a, b) = a ⊕ b, one expression, zero set and values together, and the zero set falls out of it as the case a = b. There is no interesting gap between knowing who wins at Nim and knowing what a Nim position is worth, because one expression settles both. Adding a single move — take the same amount from both heaps — replaces the cold set entirely rather than trimming it, and it also does something the picture cannot show: it severs the two questions. The new cold set is still closed-form, three times over. The new value function is not closed-form at all.

One move, and the game keeps the first half of its solution and loses the second. That is worth more than the individual facts, because “solved” is used for both halves indiscriminately, and here is a game where one half is solved to an almost embarrassing degree and the other is not solved even a little — not by φ, not by greed, not by digits, and not, so far, by anybody.