The digits say which move wins

Wythoff’s game has two heaps. A move takes any number of counters from one heap, or the same number from both. The positions a player wants to hand over — the cold positions — are the pairs (⌊nφ⌋, ⌊nφ²⌋), which is the fact Wythoff found in 1907 by a partition argument on Beatty sequences.

That formula is exact and it is not a rule anybody can use at the board. Deciding whether (1836311903, 2971215073) is cold by computing ⌊nφ⌋ needs enough precision in φ to get the floor right, and getting a floor right near a boundary is exactly where floating-point arithmetic stops being a friend.

There is a third route, and it needs no φ, no table and no arithmetic beyond addition.

Every integer is a sum of Fibonacci numbers #

Zeckendorf’s theorem: every positive integer is a sum of non-consecutive Fibonacci numbers, in exactly one way.

Take 1, 2, 3, 5, 8, 13, 21 as the places of a numeral system — starting at 1 and 2 rather than at 1 and 1, so that each place has a distinct value — and every integer has one representation with no two adjacent ones. Twelve is 8 + 3 + 1, so it is written 10101. A hundred is 89 + 8 + 3, so it is 1000010100.

In that system the cold positions of Wythoff’s game are a statement about digits.

Two sentences, no φ:

• the smaller half’s numeral ends in an even number of zeros;
• the larger half is the smaller one shifted up one place.

Checked against the table #

The site’s usual answer to a question about Wythoff’s game is a Grundy table: compute the mex over every row, column and diagonal, and read off which cells are zero.

That is the answer Wythoff’s game draws: Grundy values computed by a mex over the moves, with the zeros falling along a line of slope φ that nothing in the computation has heard of. The digit rule and the mex table share no arithmetic at all. One reads a numeral; the other takes minimum excludants over rows, columns and diagonals. So running them against each other is a real check rather than a restatement.

Six thousand four hundred of six thousand four hundred. That is the claim, and it is worth saying what it cost to state correctly: the first version of the digit rule used only the shift condition, which is necessary and not sufficient. It passes 3,572 of 3,600 positions and fails on exactly the pairs whose smaller half ends in an odd number of zeros — two consecutive Fibonacci numbers being the smallest example, which is the pair a reader would try first.

That is a rule that would have looked right on every example anybody drew, and it was caught by running it against a computation that does not share its assumptions. It is worth scoring each half on its own, because the two fail in completely different ways.

The asymmetry is the reason the mistake survived. A condition with no false negatives passes every cold position anybody checks, and the cold positions are the ones a reader generates — from the formula, from the greedy listing, from the picture. The 28 counterexamples are all hot, and nothing about the derivation suggests looking at those.

Reading a cold pair #

It is worth working one pair by hand, because the rule is short enough to check and the checking is the point.

The fourth cold pair is (6, 10). Six is 5 + 1, so its numeral is 1001 — places 5, 3, 2, 1 with ones in the 5 and the 1. It ends in no zeros, and no zeros is an even number of them, so the first condition holds. Ten is 8 + 2, so its numeral is 10010, which is 1001 with a zero appended. The second condition holds. The pair is cold.

Now try (5, 8), two consecutive Fibonacci numbers. Five is 1000 and eight is 10000, which is five’s numeral with a zero appended — so the shift condition holds. But five’s numeral ends in three zeros, which is odd, so the parity condition fails and the pair is not cold. The mex table agrees: (5, 8) is a win for whoever moves.

That is the pair the first version of this rule got wrong, and it is not an obscure one. Two consecutive Fibonacci numbers are the most natural pair in the whole system to try, and a rule that mishandles them would have been believed by anybody who tested it on the pairs the formula produces — because those are all cold and all satisfy both conditions.

The general lesson is one this site keeps meeting: a rule tested only on the cases it was derived from is untested. The check that mattered was the one over a square containing thousands of positions that are not cold.

The third route, and the second #

Wythoff’s own argument is a third thing again, and worth keeping distinct.

A golden ratio thirty years early is that route drawn: the cold positions as a partition of the integers into two Beatty sequences, checked against the zeros of a Grundy table, with the golden ratio arriving as the solution of a quadratic that the partition condition forced. Wythoff had it thirty years before anybody had the mex.

So there are three descriptions of the same set:

The Beatty partition. Elegant, exact, and about real numbers. It says what the set is.

The mex table. Mechanical, general, and about this game only. It says how to compute the set, one row at a time.

The digits. Local, exact, and about integers. It says how to test membership, in a number of steps proportional to the length of the numeral.

Having three is unusual and worth noticing against the rest of the site. Grundy sequences generally have one description — the table — and nothing else; a subtraction game gets a second, because its sequence is eventually periodic and the period is a proof. Wythoff’s cold positions have three independent ones, which is as well-understood as a set in this subject gets.

The three descriptions are two #

Setting the three side by side invites the reading that they are independent discoveries about one set. Two of them are not independent at all, and seeing why is the best available answer to why the digit rule works — a question the sections above answer only by agreeing with a table.

Take the shift condition first. Write $a$ in Fibonacci base and push every digit up one place: the numeral $1001$ becomes $10010$, which is to say each Fibonacci number in the sum is replaced by the next one up. Call that $\mathrm{shift}(a)$.

For every cold pair drawn on this page, $\mathrm{shift}(a) = b$ exactly. Not approximately, and not up to a correction: the fourteen pairs computed from $(\lfloor n\varphi \rfloor, \lfloor n\varphi^2 \rfloor)$ have their larger half equal to the shift of their smaller half, on the nose. The shift condition is the Beatty relation, written in a base where multiplying by $\varphi$ has become moving a digit.

Now the parity condition. A numeral’s trailing zeros say which Fibonacci number is the smallest in the sum — $1001$ ends in no zeros, so its smallest term is the units place; $1000$ ends in three, so its smallest term is three places up. And the integers whose smallest term sits at an even place are exactly $1, 3, 4, 6, 8, 9, 11, 12, 14, \ldots$, which is exactly the lower Beatty sequence $\lfloor n\varphi \rfloor$. The ones at odd places are $2, 5, 7, 10, 13, \ldots$, the upper sequence.

So the parity condition says $a$ is a lower-sequence number, and the shift condition says $b$ is the upper-sequence number that goes with it. Those are the two clauses of the Beatty description, and the digit rule is that description read in the right base.

Which explains the bug, and the base #

That reframing makes both loose ends of this essay tighten.

The rule with the shift condition alone was wrong for a stateable reason. The shift pairs any integer with something; what it does not do is check that the integer is on the lower sequence. Drop the parity clause and the rule accepts $(5, 8)$ — the shift of five really is eight — while five is an upper-sequence number and belongs on the right of a cold pair, not the left. The failure was not a missing edge case. It was one of the two halves of the Beatty statement being left out, and the 28 positions it got wrong in a 60 × 60 square are the ones where that half is the one that matters.

And the choice of base stops being a happy accident. The section below says the right numeral system is the one in which a game’s moves are simple, which is true and is not what is happening here. What makes Fibonacci base right is narrower and sharper: multiplication by $\varphi$ is the shift in this base, so a description written in terms of $\varphi$ becomes a description written in terms of digits, and a floor function that needed unbounded precision becomes a comparison that needs none.

That is the whole of the trade the essay opens with. Deciding whether $\lfloor n\varphi\rfloor$ equals some large integer is hard because the boundary case needs $\varphi$ to more places than anybody has; deciding whether one numeral is another one shifted is exact, because a numeral is a finite object and no rounding happens anywhere.

So the honest count is two descriptions and not three. The Beatty partition and the digit rule are one statement in two coordinate systems, and the mex table is the genuinely independent second — which is exactly what makes the 6,400-position check worth running, and what makes it evidence rather than bookkeeping. Had the digit rule been derived from the mex table there would be nothing to check; had it been derived from the formula, as it effectively is, the check is against the one description that shares no arithmetic with it.

What each costs #

The reason the third route is worth having is not elegance.

A heap of a trillion has a 58-digit Fibonacci numeral. The corresponding table would have 10²⁴ cells. That is not a difference of degree.

It is worth being clear that the table is not merely slow. A Grundy table for Wythoff’s game cannot be computed row by row from a formula: every entry is a mex over an entire row, an entire column and an entire diagonal of earlier entries, so producing the value at (a, b) requires having produced every value below and to the left of it. The work is not just quadratic, it is unavoidably sequential in a way that rules out asking about one large position without answering every smaller one first.

The digit rule has none of that structure. It looks at two numerals, counts trailing zeros in one, compares the two, and stops. Nothing below the position is consulted, nothing is stored, and the answer for (10¹², 1.6 × 10¹²) costs the same as the answer for (6, 10).

And the digit rule gives the move, not merely the verdict: from a hot position it finds a cold one by looking for a numeral of the right shape below it, which is a search over numerals rather than over a table.

The same shape, one field over #

This is a claim about encoding, and the complexity field has an essay about exactly that.

How a position is written down makes the point for Nim: the nim-sum is linear in the digits of the heap sizes and the counters are exponentially many, so the game’s easiness is a fact about the input format. Wythoff’s game is the same observation with a different base — the digits that matter here are Fibonacci digits rather than binary ones, and the reason is that the game’s moves respect that base rather than the usual one.

Why Fibonacci base and not binary #

The question worth asking is why this game should have a numeral system attached at all, and the answer is in the moves.

A Wythoff move takes k from one heap, or k from both. The second kind is what makes the game more than two independent Nim heaps, and it is a move that changes both coordinates by the same amount — which is exactly the operation Fibonacci addition handles cleanly, because the recurrence F(n) = F(n−1) + F(n−2) is a statement about shifting.

Binary is the right base for Nim because Nim’s move changes one heap independently, and binary digits are independent. Fibonacci base is the right base for Wythoff because Wythoff’s extra move couples the heaps, and Fibonacci digits are coupled in the matching way.

That is a general principle worth naming: the right numeral system for a game is the one in which its moves are simple, and finding it is the same kind of work as finding a good coordinate system anywhere else in mathematics.

A closed form that is not a formula #

There is a distinction here that this site has not previously had a good example of.

A closed form is usually taken to mean a formula: an expression in the position’s parameters that evaluates to the answer. ⌊nφ⌋ is one. The digit rule is not — it is a test, applied to a representation, with no expression anywhere in it.

But it does the job a closed form is wanted for. It answers a question about an arbitrarily large position in time proportional to the length of its description, without a table and without iterating over anything the position does not mention. That is the property that matters, and “closed form” is the wrong name for it.

There is a third shape of answer again, and a period is a proof is where this site draws it: a Grundy sequence with a period found and certified, so that a finite check settles a claim about every heap. Three shapes — a formula, a digit test, a certified period — and a game is lucky to have any of them.

The three are not interchangeable. A formula gives the n-th cold pair; the digit test decides membership; the certified period settles a family. Which one a game hands over depends on the game and not on how hard anybody looked, which is why the sequence nobody has settled has none of the three after seventy years.

What the picture cannot show #

The square drawn above is 24 or 34 cells on a side, and the entire argument is about what happens when it is not.

Nothing in a picture of a small square distinguishes a method that grows quadratically from one that grows logarithmically. Both look like a table of coloured cells at this size, and the cost table beside it is where the difference lives — which is why the figure carries numbers a reader can check rather than a curve.

The second thing not shown: the Grundy values. The digit rule decides whether a position is cold and says nothing about the value of a hot one. The mex table gives every value, and the values matter as soon as a Wythoff position appears inside a sum with something else. So the cheap method answers a narrower question, and the narrower question is the one a player asks.

That is the honest limit of the trade. A logarithmic test for zero is not a logarithmic algorithm for the game.

Why this is an applied essay #

Wythoff’s game was invented in 1907 to be analysed, so it is not an old game found among people playing it, and a reader may reasonably ask what it is doing in this field.

The answer is the direction of the application. Everywhere else here, the theory is turned on an object that existed first. Here a number system is turned on a game — Zeckendorf’s theorem is a fact about integers, published for its own reasons, and it settles a question about play that the game’s own machinery answers only by tabulation.

That is the same shape as the game that is a number system, where a game turns out to be a question about numerical semigroups, and it is the shape the field’s rule was written to admit: questions outside game theory that a game answers, and questions inside game theory that something outside answers. Both directions cross the same boundary.

It is also the shape Wythoff’s own argument had in 1907. Beatty sequences were not game theory either. What is different here is only which piece of number theory does the work — a partition of the reals then, a numeral system for the integers now — and the fact that the second one still answers a question the game’s own theory has never answered.

The convention, named #

Everything here is normal play: the player who cannot move loses, and the player who cannot move is the one facing two empty heaps.

The cold positions are the P-positions under that convention, which is why “hand this over” and “value zero” mean the same thing. Under misère play the analysis would change at the very bottom, as it does for Nim, and neither the Beatty formula nor the digit rule would survive the change unmodified — both are characterisations of the set of P-positions, and that set is convention-dependent.

Where the ladder goes next #

wythoff now has three rungs: the game, the 1907 method, and the numerals.

The rung above them is the one the Grundy table refuses to give. Wythoff’s cold positions have a closed form in three separate senses; its Grundy values have none — no period, no formula, nothing anybody has found — and the contrast between a set with three descriptions and a function with none, in the same game, is the sharpest thing this anchor has to offer.