The dual was the value table

The losing positions are a code found that the rows a coin-turning player has already lost are closed under adding two of them together, which makes them a linear code — and that on eight coins Mock Turtles gives the extended Hamming code exactly. The code names the move then used it: a won row is a codeword with errors and a winning move is the correction.

That page closed on the one piece of coding theory the game seemed to have no use for:

What is left is the direction the coding theory points: the code’s dual, which for the extended Hamming code is itself, and what a self-dual code means for a game that produced it without being asked to. A game reads a codeword as a position to hand over; nothing in the game reads a dual codeword as anything.

Something does, and it is the most game-theoretic object on the site.

The dual is spanned by the bit-planes of the value table.

Why it has to be #

The identity is not a discovery so much as a translation, and seeing why makes the rest of the page readable.

A row of coins is lost exactly when its heads’ one-coin Grundy values exclusive-or to nought. That is a single condition on integers. Write those integers in binary and it becomes several conditions on bits: for each bit position $b$, the number of heads whose value has bit $b$ set must be even.

Each of those is a parity check, and a parity check is a row — the row holding the coins whose value has bit $b$ set. So the code’s parity-check matrix has one row per bit of the value table, and its rows are the value table read one column at a time.

The dual of a code is spanned by its parity-check matrix. So the dual is spanned by the value table’s bit-planes, by definition, and the only content in the identity is noticing that the parity checks were already a game object rather than an artefact of writing the condition down.

That is worth insisting on because the rung below’s sentence — nothing in the game reads a dual codeword as anything — is exactly wrong in an instructive way. The game reads nothing else. The one-coin values are what the mex produces, they are what every row’s value is assembled from, and a dual codeword is a slice of them.

What a dual codeword is, as a position #

The identity is worth translating back into coins, because a bit-plane of the value table is a row of the board and a reader should be able to point at it.

Take Turning Turtles on seven. Its one-coin values are $1, 2, 3, 4, 5, 6, 7$ — the $n$th coin is worth $n$, which is the whole of that game. The lowest bit is set on coins 1, 3, 5 and 7, so the first parity check is the row 1010101: heads on the odd coins. The second bit is set on 2, 3, 6 and 7, giving 0110011. The third on 4, 5, 6 and 7, giving 0001111.

So a dual codeword of Turning Turtles is one of those three rows, or the exclusive-or of two or three of them — eight rows in all, counting the empty one. Every one of them is a genuine position of the game, drawable on the board, and each is the set of coins that contribute a particular bit to any row’s value.

The reason the game never seemed to read them is that they answer a question nobody asks of a position. A player asks what is this row worth and gets a value; the parity checks are what that computation is made of, and a player has no more occasion to name one than an arithmetician has to name a column of a long addition. They were always there and there was no reason to draw them.

What makes them worth drawing is that coding theory has a use for them and the game does not, and the two uses are of the same object. That is the sense in which the family stops being about games: a coin-turning rule produces a parity-check matrix, and whether it produces a famous one depends on whether the values it computes happen to be the columns somebody wanted.

Five relations #

Once the dual is identified, how it sits against the code is a question about each game rather than about codes.

Turning Turtles on seven contains its own dual. Its code is the $[7,4]$ Hamming code and its dual the $[7,3]$ simplex code, and every parity check is itself a losing row — a game in which the conditions that decide the game are positions the game can reach. A player handed one of those eight rows has been handed a losing position and one of the three tests by which losing is decided, at the same time and without either fact being visible from the board.

Mogul on seven is the other way round. Its code has dimension three and its dual four, so the code sits inside the dual: every losing row is a parity check, and there are checks that are not lost.

Mock Turtles on eight is self-dual, and that is the case the rung below asked about.

What self-duality says about a game #

That the extended Hamming code is self-dual is a standard fact and is not the point. The point is that both halves of the statement are now game objects, so self-duality says something about Mock Turtles rather than about a code.

It says: a row is lost exactly when it is a sum of bit-planes of the value table. The set of positions the game has already decided against a player coincides with the span of the very table used to decide them. The condition and the objects it applies to are the same collection.

There is no reason a game should do that, and four of the five cases here do not.

It is also the sharpest available answer to a question this anchor has been circling since it opened: why does a coin-turning game produce a famous code? The losing positions are a code answered the first half — because the losing set is closed under exclusive-or, which follows from a row being the sum of its heads. This is the second half. A code is famous when its parity-check matrix is one somebody wanted, and a coin-turning game’s parity-check matrix is its value table. So the game produces a famous code exactly when its one-coin values, written in binary and read as columns, are a matrix a coding theorist had a use for — Turning Turtles’ being the integers 1 to 7, which is the Hamming matrix, and Ruler’s being the powers of two, which is nothing anyone needed.

That reduces a coincidence to a property of a sequence, which is as far as this ladder can take it. Why the mex over turn one, two or three coins produces the odious numbers is a fact about the rule, and it is the fact the code names the move is about.

Mogul on eight and Ruler on eight both have a code of dimension four and a dual of dimension four, and the two are different codes. So the equality of dimensions — which is forced, since a code and its dual have dimensions summing to the length, and eight is twice four — buys nothing at all. Self-duality is a genuine coincidence in one game of the five.

Mogul on eight also shows why. Its one-coin values are $1, 2, 4, 7, 8, 11, 13, 1$ — the eighth coin is worth one, exactly as the first is, because the seven-place window has moved past the start. A repeated value is a repeated column in the parity-check matrix, and a repeated column is what stops a code being anything with a name.

The signatures #

The weight enumerators say the same thing in the notation a coding theorist would use. Mock Turtles’ code and dual both come back $1 + 14x^4 + x^8$; Turning Turtles’ dual is $1 + 7x^4$, the simplex code, every non-empty word of exactly four heads.

The simplex code’s uniformity is worth a sentence, because it is the parity checks being uniform. Seven checks of four coins each, any two overlapping in exactly two coins — which is what makes the Hamming code correct one error, and which arrived here as the binary numerals from one to seven, stood on end.

Ruler’s enumerator is the useful contrast and it is worth quoting for the reason the rung below gave: not every coin-turning game gives a famous code. Its checks are 10101010, 01000100, 00010000 and 00000001 — four rows of wildly different sizes, one of them a single coin — and a code with a weight-one parity check is a code with a coin that is never allowed to be a head. That is a perfectly good linear code, it has a perfectly good dual, and no table of codes has a name for either.

What the containments are worth #

Three relations across five games, and none of them is a theorem, so it is worth being careful about what they are evidence for.

A code contains its own dual exactly when every parity check is itself a codeword — when every check row, read as a position, is a row the mover has lost. That is a strong property and Turning Turtles has it: all eight of its dual words sit inside its sixteen. Read in the game, it says that the seven conditions deciding whether a row is lost are themselves seven lost rows.

The reverse containment — the code inside the dual — is what Mogul on seven has, and it says that every lost row is a parity check. Since the checks are the value table’s bit-planes, that is a statement that the game’s losing positions are all built out of its own value bits and there are more such combinations than losing rows.

And the two of five with neither containment are the ones that make the other three readable. Without them the natural reading of the table would be that a coin-turning code always sits in some fixed relation to its dual, and that reading is available right up until Mogul and Ruler on eight coins refuse it. That is the standing use of a control on this site and it is doing real work here: three suggestive cases and no negative would have been three suggestive cases.

What decides which relation a game gets is the value table, and nothing on this page says how. Turning Turtles’ values are the integers, Mock Turtles’ are the odious numbers, Mogul’s are Mock Turtles’ truncated by a window and Ruler’s are the powers of two — and those four tables give four different answers. A rule connecting a table’s shape to the containment its code inherits is exactly the sort of thing this anchor should want and is not attempted here.

What the solver computed, and how #

Five game-and-length pairs: Turning Turtles on seven, Mock Turtles on eight, Mogul on seven and eight, and Ruler on eight.

For each, the one-coin Grundy values are built left to right by the mex over the moves available to a lone head, with no search over rows — turning a set whose rightmost member is $n$ leaves heads at the rest, whose value is their exclusive-or. The code is then every row whose heads’ values exclusive-or to nought, found by enumerating all $2^n$ rows rather than by generating from a basis, so nothing about linearity is assumed.

The dual is computed from the definition: every row orthogonal to every codeword, where orthogonal means an even overlap. That is $2^n$ rows tested against the code, again with nothing assumed.

The bit-planes are read off the value table — for each bit $b$, the row holding the coins whose value has that bit set — and their span is generated by closing under exclusive-or from the empty word. The claim is then the set equality between that span and the dual, checked word for word.

Two things are asserted rather than reported. The span must equal the dual on every case, since one agreement would be a coincidence. And exactly one case must be self-dual, with at least one where neither code contains the other, or the self-duality is not being told apart from anything.

Where the model stops #

Five cases, and short ones. Seven and eight coins, because the dual is computed by testing $2^n$ rows against every codeword and that is $2^{16}$ operations at eight coins and grows as $4^n$. The identity between the dual and the bit-plane span is a theorem — it follows from the parity checks being the bit-planes, in two lines — so the sweep is a check on the implementation rather than evidence for the claim. The containments are not a theorem, and five cases is a small number of them.

And the identity is about a code from a game, not about codes. Nothing here says a general linear code’s dual is anything in particular. What is shown is that when a code arises this way — as the kernel of a nim-sum condition on a table of values — its parity checks are that table, and the dual therefore has a reading the game already had.

The window matters and is not a parameter here. Mogul’s rule is Mock Turtles restricted to seven places, so its values agree with Mock Turtles’ up to the seventh coin and diverge after. The two games on eight coins are therefore a matched pair in the sense this site likes, and the pair has not been exploited: what a longer Mogul does to the containments as the window’s effect accumulates is a sweep this page did not run.

Normal play throughout, and the whole apparatus depends on it — the Grundy value of a row is the exclusive-or of its heads’ values because of the Sprague–Grundy theorem, which is a normal-play theorem, and turning turtles is where that decomposition is established for this family.

And the figures cannot show the thing that would make the self-duality vivid, which is the sixteen rows drawn twice — once as losing positions and once as sums of bit-planes — with the reader invited to match them up. That is one drawing of thirty-two rows and it belongs on the rung below, where the sixteen are already drawn in full; here they are counted.

Where the ladder goes next #

The codes anchor has three rungs: the losing positions are a code, the code names the move, and now the dual.

The rung above is the asymmetry the decoder inherits. The code names the move found each game’s decoder carrying an asymmetry — a radius the rules can reach and a radius they cannot — set by which sets of coins the rule offers rather than by how many it turns. The dual is the object that ought to explain it: a decoder’s difficulty is a statement about the syndrome map, the syndrome is the row’s Grundy value, and the value is computed against exactly the bit-planes this page has identified as the dual’s basis. So the question is whether a game’s decoding radius is a function of its dual’s weight enumerator — which is a coding-theory statement about a game-theoretic quantity, and is the first thing on this anchor that the two subjects would state the same way.

Two neighbours are worth the trip. Turning turtles is where a row of coins is shown to be a sum of its heads, which is the decomposition that makes the whole family linear and therefore makes a code available at all. And Sprague–Grundy is the theorem underneath that decomposition, and it is worth reading beside a page whose finding is that the values it produces are, read sideways, a parity-check matrix.