The tartan theorem

The nimbers multiply closed with an algebraic fact and no use for it. The impartial values are not merely a group under nim-addition; they are a field, with a multiplication defined by a mex-style rule, satisfying every field axiom over the range checked.

A field is a strong structure and the argument for it was internal: the multiplication is the simplest one that could work, and it works. Nothing in that essay asked the multiplication to compute anything.

This one does.

Coins in a row are already a sum #

Turning Turtles is a row of coins. A move turns over one or two, with the condition that the rightmost coin turned goes from heads to tails — which guarantees the game ends, because the binary number whose digits are the heads strictly decreases.

What makes the family remarkable is where the sum lives. A row with heads at positions S is the disjunctive sum of the one-coin games at each element of S, so its Grundy value is the exclusive or of theirs. The decomposition is inside a single picture.

Three rules a sentence apart give three completely different tables. Turning Turtles gives 1, 2, 3, 4, … — the position’s own index, so a row of it is a Nim position with a heap for every head. Mock Turtles, where a move may turn one, two or three coins, gives 1, 2, 4, 7, 8, 11, 13, 14 — the odious numbers, those with an odd count of ones in binary, which is a strange answer for a rule that close. Ruler, where a move turns any consecutive run, gives 1, 2, 1, 4, 1, 2, 1, 8 — the largest power of two dividing the index, and nothing in that rule mentions powers of two.

Those tables are the raw material for everything below, and from here they are never drawn on their own again: each grid carries its two factors’ tables down its left edge and across its top, in the two colours, so the reader can always see what is being multiplied.

Lay one game across another #

Now put coins on a grid, and define a move as follows. Pick a legal turn X of the row game and a legal turn Y of the column game, and turn over every coin at a square of X × Y — with the coin at the bottom-right corner of that rectangle going from heads to tails.

That is the tartan construction, and the name is a good one: a move turns a rectangle, and the pattern of legal rectangles is the two games’ patterns crossed.

The position is again a sum of its heads, for the same reason as in one dimension, so again one table of single-coin values settles everything. The question is what that table looks like.

Every cell is the nimber product of its two coordinates’ one-dimensional values. That is the tartan theorem, and the computation here does not assume it: the grid is built the long way, by a mex over the product game’s own move list, and the multiplication table is computed separately and compared cell by cell.

The rules that do not work #

A verification that has never rejected anything proves nothing, so the theorem is run against the three combining rules anybody would reach for.

Exclusive or. The natural first guess, since the values combine that way within a row. Wrong on 61 of 64 cells, starting at the very first: the corner square has row value 1 and column value 1, exclusive or gives 0, and the answer is 1.

Ordinary multiplication. Wrong on 22 of 64. It agrees whenever one of the factors is 1 and diverges as soon as both are 2: 2 × 2 is 4 in the integers and 3 in the nimbers.

The smaller of the two. Wrong on 60 of 64.

That the nimber product survives while the ordinary product fails at 2 × 2 is the sharpest possible statement of what the nimber field is: it is not the integers with a different notation, and the multiplication is not a relabelling of anything.

The same holds for the addition, and the nim-sum essay makes that point at the start of the subject: adding without carrying is not ordinary addition, and every attempt to substitute ordinary addition fails at 1 + 1. What is new here is that the second operation is equally unlike its ordinary counterpart, and equally forced.

What the nimber product is #

The multiplication is worth stating, since the whole essay turns on it not being the obvious thing.

It is defined the same way the mex rule defines everything else in this subject: a·b is the least nimber that is not of the form a′·b + a·b′ + a′·b′, where a′ runs over the nimbers below a and b′ over those below b. That expression is the “simplest thing that could work” — it is exactly what distributivity forces once the products of smaller pairs are known — and taking a mex over it gives the smallest value consistent with the field axioms.

Run it out and the small cases are: 1·x = x, 2·2 = 3, 2·3 = 1, 3·3 = 2, 4·4 = 6. None of those is an exclusive or and none is an ordinary product. Two times two being three is the fact that kills every intuition a reader brings, and it is forced: 2·2 cannot be 0, 1 or 2 without breaking the axioms, so it is 3.

The table stops at sixteen for a reason worth stating, since it is the first sign that this multiplication has arithmetic of its own. The nimbers below four are a field, and so are those below sixteen, but those below eight are not: 2 · 4 is 8, which is outside the range, so closure fails on twenty-four of the sixty-four products. Only the ranges below 2, 4, 16, 256 — the Fermat powers of two — are closed, which is why a table of this kind can be drawn at some sizes and not at others.

That the same operation should describe a game about turning coins in a rectangle is not something the definition suggests, and it is the reason this essay exists. It is also checkable directly, because one choice of factors turns the grid into the table.

The multiplication table is itself a game #

Turning Turtles’ one-coin values are 1, 2, 3, 4, …, the position’s own index. So lay Turning Turtles across a grid of Turning Turtles and the edge values down the side and across the top are the counting numbers — which means the theorem predicts that the cell at (x, y) is the nimber product of x and y, and the grid is the multiplication table above, drawn a second time by a game.

This is the sharpest form of the claim available. Nothing about the grid was built from the multiplication: its cells come from a mex over rectangle turns, and the coincidence with a table computed from the field axioms is complete over all sixty-four cells. It is also where the failure of the obvious rules is starkest — exclusive or is wrong on 60 of the 64, ordinary multiplication on 41, and taking the smaller of the two coordinates on 63.

The factors can be anything #

One pair of games agreeing could be a coincidence of small numbers. Three more pairs are run for the same reason the alternatives are, and they are chosen to be as unlike each other as the family allows.

Those two factors have nothing to do with each other: the odious numbers come from a count of binary ones and the ruler values from a count of binary zeros at the bottom of a number, and neither sequence is defined in terms of the other. That is what makes their agreeing with a table of nimber products a claim rather than a restatement. The next pair removes even that much variety.

That was a game squared, and squaring is the least favourable case for a coincidence: a repeated table hands any rule with a symmetry in it the best chance of fitting, and the ruler values are the most symmetric table the family has. Mock Turtles against itself is the same experiment run on a table with no pattern to exploit.

The last pair shows that the theorem does not depend on the factor tables growing. Mogul is Mock Turtles with the three turned coins confined to a window of seven places, which is the restriction that makes it the game the Hamming code falls out of — and the restriction bounds the table. Mock Turtles’ values climb without limit through the odious numbers; Mogul’s are 1, 2, 4, 7, 8, 11, 13 and then those same seven again, for ever.

Why a product and not a sum #

The reason the answer is a multiplication is worth extracting, because it explains why nobody would have guessed exclusive or from the one-dimensional case.

Within a row, several heads are several independent games and the theorem for a disjunctive sum is that values add — with addition meaning exclusive or. Across the grid, a single head at (x, y) is one game, and its moves are pairs of moves from the two factors. That is not a sum; it is closer to a product of move structures, and the value that respects a product of move structures is a product of values.

What this stands on is the Sprague-Grundy theorem: every impartial position under normal play is equivalent to a single Nim heap, and the value of a sum is the nim-sum of the parts. Adding without carrying is a parity per binary column, and no amount of column arithmetic produces a multiplication — which is why the second operation had to arrive from somewhere else, and why it arrived from algebra rather than from the games.

Checked from the other end too #

The decomposition claim — that a grid of heads is the sum of its individual heads — is not assumed either.

Over every arrangement of a 3 × 4 grid, all 4,096 of them, the value is computed twice: once as the exclusive or of the one-coin values, and once by a brute-force search over the grid as a single game, deliberately ignorant of the decomposition. They agree on every arrangement.

That check matters because the whole apparatus rests on it. If a grid were not the sum of its heads, a table of one-coin values would settle nothing and the multiplication would be a fact about single coins rather than about the game.

The brute-force half is worth describing, because “ignorant of the decomposition” has to be true rather than intended. It takes the twelve-cell grid as a single impartial position, enumerates every legal rectangle turn from it, recurses, and takes a mex — the same routine that would be applied to any unfamiliar impartial game, with no reference to rows, columns or products anywhere in it. Four thousand and ninety-six arrangements, four thousand and ninety-six states in its table, and no disagreement with the exclusive or of the one-coin values on any of them.

That is the shape of every check on this site, and it is why the essays keep reporting counts. The same check in one dimension is what established the decomposition there, and the two-dimensional version is the same code with a rectangle where a run used to be.

A row is a sum of its heads; a grid is a sum of its heads; and both statements are verified rather than inherited. checkDecomposition runs the one-dimensional half over every row of a given length, and the grid half is the same code with a rectangle where a run used to be.

What this is an application of #

The essay sits in the impartial field rather than in out in the world, and the reason is worth stating since it borders on that field’s rule.

Nothing here had a life before the theory. Coin-turning games were constructed to display exactly this structure, and the tartan product is a construction rather than a discovery about anything anybody plays.

What is applied is the nimber multiplication, and it is applied to a question it was not built for. The multiplication was defined by a mex over products in a way that makes the field axioms come out; the tartan theorem says that the same operation is what a two-dimensional turning game computes, whatever pair of one-dimensional tables it is handed. Two independent reasons for one operation is the ordinary evidence that an operation is the right one, and it is the same shape of evidence as two people finding the mex rule four years apart.

The definition is a picture of a move #

The essay has so far presented the agreement as a surprise: an operation invented for algebraic reasons turns out to compute a game. It is worth going one step further, because the two are closer than that — the definition of the multiplication and the rule of the game are the same object seen from two sides.

Write the multiplication out again. $a \cdot b$ is the least nimber not of the form

$$a' \cdot b \;\oplus\; a \cdot b' \;\oplus\; a' \cdot b'$$

with $a'$ below $a$ and $b'$ below $b$. Three products, exclusive-ored, one for each way of taking a smaller value on one side, the other, or both.

Now take a grid with a single head at $(x, y)$ and play the two-coin turn in each factor: the row game’s move that turns coins $x'$ and $x$, and the column game’s that turns $y'$ and $y$. The rectangle $X \times Y$ has four corners, and the move turns all of them. The head at $(x, y)$ goes over to tails, as the rule requires. The other three squares were tails and become heads.

So the position after the move is three heads, at $(x', y)$, $(x, y')$ and $(x', y')$ — and a grid is the sum of its heads, so its value is

$$a' \cdot b \;\oplus\; a \cdot b' \;\oplus\; a' \cdot b'$$

which is the expression in the definition, arrived at by turning coins. The three terms are the three corners. Take a mex over every option, which is what a Grundy value is, and the mex over every option is the mex in the definition.

What that does to the surprise #

Once the correspondence is seen, the shape of the result changes, and it is worth being exact about what is left surprising and what is not.

The agreement is no longer a coincidence, and the essay’s alternatives column is no longer the only evidence. Exclusive or, ordinary multiplication and the minimum fail not merely because they disagree with sixty-four measured cells, but because none of them is a mex over corner-sums, and the game’s value is a mex over corner-sums by construction. Sixty-four agreements are a check on the implementation; the three corners are the reason.

What stays surprising is which construction came first. The nimbers multiply arrives at the mex expression from the field axioms: distributivity forces $a'b + ab' + a'b'$ to be a value the product must avoid, and taking the smallest available is the simplest choice consistent with the axioms. Nothing in that argument involves a rectangle. The tartan construction arrives at the same expression from the geometry of turning a rectangle of coins, and nothing in that involves a field.

Two routes, no shared step, one expression. That is the situation this site keeps reporting as the evidence that an operation is the right one — the same shape as two people finding the mex rule four years apart, with the difference that here the two derivations are not even about the same subject.

And it explains why the product is invisible everywhere else. The disjunctive sum is visible in any two positions side by side, because putting things beside one another is what the operation is. The product needs a construction in which one move acts on two factors at once and leaves exactly the three cross terms behind — and turning a rectangle of coins is such a construction because a rectangle has four corners and one of them is the mover’s. Games in which a single move touches two components in that precise way are not common, and the essay’s difficulty in pointing anywhere else is a fact about the operation rather than about the survey.

Where the same manoeuvre appears elsewhere #

Two operations on games, matching two operations on values, is a pattern this site has met once before in a different form.

The disjunctive sum is the first: put two positions side by side, and their values add. That is the operation everything is built on, and its generality is what makes the theory a theory rather than a catalogue.

Other ways to add is the qualification: conjunctive and selective compounds are also ways of putting two positions together, and neither has values that combine. So “positions can be combined” is not enough — the combination has to be the right one, and only the disjunctive sum is.

The tartan product is a third combination, and it is the second one whose values combine. That is worth noticing precisely because the middle essay establishes how rare the property is. Two out of three of the ways of putting games together that this site has examined have no value arithmetic at all; the tartan product does, and the arithmetic it has is the second operation of a field whose first operation is the sum’s.

What the picture cannot show #

The grids here are eight squares on a side, and the theorem is about arbitrary sizes.

Nothing in a picture of an 8 × 8 grid distinguishes a theorem from a coincidence, and the essay leans on the alternatives-killed column rather than on the agreement, because the agreement of a true rule and the agreement of a rule that happens to fit sixty-four cells look identical.

The second thing not shown is the move. Every cell reports a Grundy value and a Grundy value says whether a position is won, not what to play. Finding the winning move in a tartan position means finding a rectangle whose turn leaves the exclusive or at zero, and that is a search over rectangles which no figure here draws.

The third: larger factors. The nimber product is easy to compute for small values and genuinely awkward for large ones, since the definition is recursive and involves Fermat powers of two. A grid of 64 × 64 would need products of values up to 63, and the table for those is not something to read off a page.

The shape of the result #

There is a general statement lurking here that is worth pulling out, because it is a small piece of structure that the subject does not display often.

Impartial games under disjunctive sum form a group, and the group operation is the nim-sum. That much every essay in this field has used. What the tartan construction supplies is a second operation on games — a product of move structures — and the fact that it corresponds to the nimber multiplication makes the pair of operations a ring structure on games rather than merely a group.

That is a stronger statement than “the values happen to multiply”. It says the two constructions on games, sum and product, mirror the two operations on values exactly, which is the sort of correspondence that makes a theory rather than a collection of computations.

It is also, as far as this site is concerned, unusually well hidden. The sum is visible everywhere: two heaps on a table, two regions of a board, two components of a position. The product is visible in one family of games and nowhere else, which is why an essay about it has to be an essay about coins on a grid rather than about anything a reader has seen before.

The convention, named #

Normal play throughout, and here the convention is doing something specific.

Every coin-turning game ends because the binary number formed by the heads strictly decreases at each move, and the player who cannot move — the position with no heads — loses. Both halves are needed: the decrease gives termination, and the last-move rule is what makes the Grundy theory apply.

Under misère play none of this survives. The Sprague–Grundy theorem does not hold, the sum of two positions is not determined by their values, and neither the exclusive or nor the multiplication computes anything. The tartan theorem is a normal-play theorem twice over.

Where the ladder goes next #

nim reaches four rungs here: the game, the moves that give counters back, the field, and the product that uses it.

The rung above is Mogul and the Hamming code — a coin-turning game whose winning positions are the codewords of a perfect error-correcting code, which is the point at which this family stops being about games at all. That is a genuine application in the field’s own sense, and it is the one this anchor is heading for.