A recipe instead of a census

How long a row a value needs counted 1,047 distinct values in rows of seven dominoes and stopped where a count has to stop:

The count of 1,047 values in seven dominoes suggests that every short game is a row of some length, which is what universality would mean here — and proving it needs a construction rather than a census: a recipe that turns a canonical form into a row, with a bound on the length.

That is the right shape for the next rung and this page is what happens when it is attempted. The recipe is obvious, it is exact where it can be checked by hand, and it does not survive day three.

The recipe #

A move in Toppling Dominoes topples one domino and everything on one side of it, so every option of a row is a contiguous substring. That single fact is what makes a construction plausible: an option is a piece of the row, so building a row out of the rows for its options is at least the right kind of operation.

For $G = \{A \mid B\}$, lay the row for $A$, then a Left domino, then a Right domino, then the row for $B$. Left topples that Left domino rightwards, which carries away everything to its right, and is left with the row for $A$. Right topples the Right domino leftwards and is left with the row for $B$. For $\{A \mid \;\}$ the tail is a single Left domino, and $\{\;\mid B\}$ is its mirror.

It works on the smallest cases, and the smallest cases are the ones anybody checks. The empty row is $0$. A single Left domino is $1$. The row LR — the recipe applied to $\{0 \mid 0\}$ — has Left options $0$ and $-1$ and Right options $0$ and $1$, of which the extra ones are dominated, so it is $\ast$. All four day-one values come out right.

The domination in that last sentence is doing all the work and it is worth dwelling on, because it is the thing that later stops happening. The recipe intends two options: one for Left, one for Right. The row it produces has four, because each domino can be toppled in either direction. It comes out right because the two unintended ones are worse for the player who has them — Left’s extra option is $-1$, which is worse for her than the $0$ she meant to have, so it drops out of the canonical form and leaves no trace.

Nothing in the recipe arranges for that. It happens, on this row, because the row is two dominoes long and there is nowhere for an unintended option to hide.

What it does past day one #

Thirteen of the seventeen day-two values it applies to. Forty-three of the hundred and twenty-six at day three.

And the harder number is the middle column. It applies to a hundred and twenty-six of the 1,474 day-three values, because a row built by concatenating two rows around a fixed junction offers exactly one intended option to each player, and 1,348 of the day-three values want more than one. The recipe is not merely wrong on those; it has nothing to say about them.

That is the first thing worth taking from the attempt. The obvious construction is a construction for canonical forms with a single option a side — a fairly thin slice of the values, and one that shrinks as the days go on, since a form’s options multiply.

Where it does apply and fails, the failure is always the same shape. The row for $\{\{\ast \mid -1\} \mid -2\}$ comes out as LRLRRLRRR, which has Left options $0$, $\ast$ and $\{0, \ast \mid -1, \{0 \mid -1\}\}$ and several more — the intended one plus a crowd. Some of the crowd is dominated and some is not, and the ones that are not are exactly the substrings that straddle the join: pieces of the row for $A$ glued to the junction, or the junction glued to a piece of the row for $B$. The recipe controls what happens when the junction is toppled and nothing else.

The arithmetic behind that is unforgiving. A row of $n$ dominoes has $n(n+1)/2 + 1$ distinct substrings, so the number of positions under a row grows quadratically while the number of options the recipe is trying to install stays at two. Every extra domino the recursion lays down adds a linear number of new substrings, each of which is a candidate option for whoever owns its end dominoes, and each of which has to be dominated by something. At two dominoes there are four; at nine there are forty-six. The recipe is not managing that budget — it is not aware of it.

Whether a different junction helps #

The natural response is that the junction is wrong. LR is a guess; perhaps a green domino, or a pair of them, or some longer guard, produces a row whose stray substrings are dominated.

Thirty-nine junctions of up to three dominoes over the three colours, each substituted for the LR, each scored on the same hundred and twenty-six values. LR is the best of them. A single green domino is second at twenty-two, roughly half. Nothing is close to exact and nothing suggests a longer guard would be.

That is a negative result and it is the useful part of the page, because it rules out the whole family of repairs. If the construction failed for want of the right separator, some separator would show it — the search covers every one that fits in three dominoes, including every guarded and doubled variant anybody would try by hand. The failure is structural: a row’s options are its substrings, and a concatenation has no control over the substrings that cross the join.

Any construction that will work has to build the row as a whole rather than assembling it from the rows for its options. That is a much stronger requirement, and it is not one this page can meet.

There is one more variant the search covers that is worth naming, because it is the repair a reader would suggest next. Padding — putting extra dominoes of one colour on the far side of the junction, so that the straddling substrings become bad for whoever can reach them — is exactly what a three-domino junction is, and LLR, LRR, RLL and the rest are all in the sweep. None of them beats LR. Padding makes the straddling options worse for one player and better for the other, and a row has two players.

The third colour, and why it does not rescue this either #

It is worth being explicit that the recipe has the green domino available and does not benefit from it. A green domino may be toppled by either player, which is what widens the value set enough for universality to be plausible at all — the rung below measured the widening — and the junction search includes every gadget containing greens.

A green domino at the junction scores twenty-two of a hundred and twenty-six, half of what LR manages. The reason is visible in what it does: a green separator makes the same option available to both players, which is what star wants and is the opposite of what $\{A \mid B\}$ wants for $A \ne B$. It is the right gadget for a symmetric value and the wrong one for everything else, and the recipe needs one gadget for all of them.

The bound the birthday cannot supply #

The other half of what the rung below asked for was a length bound, and it named the reason the birthday will not do: the census showed values whose birthday is small and whose shortest row is long.

There is an obvious second bound and it is a theorem. A row of $n$ dominoes offers each player at most $n$ topples — one per domino of their colour, in one of two directions, and the two directions from the same domino give the two ends, so the count is bounded by $n$ either way. A canonical form whose Left option set has $k$ members therefore needs at least $k$ dominoes.

It holds on all three thousand values a row of eight reaches. It is attained at every width from one to eight — there is always a value whose canonical form is that wide and whose shortest row is exactly that long, so the bound is never vacuous.

And it is almost never the binding one. Of the three thousand values, the option count exceeds the birthday on ten. Taking the larger of the two bounds improves the number of values whose bound is tight from a hundred and forty-eight to a hundred and fifty.

The grouping shows why. At every width from one to eight the shortest rows run all the way from the bound up to eight dominoes. Knowing that a form has three options fixes the row at three long or more and leaves the rest of the range open, which for practical purposes is knowing nothing.

So the answer to what bound the birthday cannot supply is not the option count. Both bounds are true, both are attained, and the mean slack of the better of them is two and a half dominoes with a worst case of five. Whatever governs the length of the shortest row is a third quantity, and neither the depth of the form nor its width is it.

It is worth saying what a third quantity would have to look like, since two candidates have now failed the same way. Both of these bounds are read off the canonical form locally — the birthday counts levels, the width counts a single option set — and both are therefore blind to how the options interact. A row’s length has to pay for the whole form: for every option, for the options of those options, and for the domination that has to hold between substrings that no part of the form mentions. A measure of that would be a measure of the form’s total size rather than of any one dimension of it, and the natural candidate is the number of distinct positions in the form, which the cost of a canonical form is about on the neighbouring anchor.

That candidate is not tested here and the reason is honest rather than principled: the sweep reaches three thousand values, and a bound with the right shape would need to be checked against the values it fails on, which are the long ones the sweep does not reach.

What is actually left standing #

It is worth separating what this page refutes from what it leaves alone, because the refutation is narrower than the failure feels.

Universality itself is untouched. Nothing here is evidence against every short game being some row; the census below still reads the way it read, and the values keep arriving as the rows get longer. What has failed is one candidate proof.

And the census remains the only evidence. That is the uncomfortable part. A count of values at each length is consistent with universality and consistent with the values petering out at some length nobody has reached, and the two are not distinguishable by counting further — the counts would look the same for a long way. The values nobody’s game produces is the fleet-wide version of the same question, asked of every ruleset at once, and it has the same shape of answer: what is reached is measured and what is reachable is not.

What a construction would have to do, stated as precisely as this page can: produce, from a canonical form of width $k$ and birthday $d$, a row in which $k$ topples a side give the intended options and every other substring is dominated. The second clause is the whole difficulty. The recipe here satisfies the first for $k = 1$ and abandons the second entirely, and the junction search says the second cannot be repaired locally.

And a construction is worth having even though the census exists. That is not obvious and is worth a sentence. A census says which values appear; a construction says how to get one, which is the difference between knowing a value is reachable and being able to build a position worth it. Everything this site does with a sum of games needs the second: building a position worth a stated value beside another position requires being able to build it.

What a construction has that a census does not #

The distinction the whole essay turns on is easy to state and easy to lose, so it is worth stating twice.

A census answers which values appear. It is produced by enumerating positions, evaluating each, and collecting what comes out, and its answer is a set. A construction answers how to make one. It is produced by exhibiting a recipe and proving it lands where it says, and its answer is a procedure.

The two come apart precisely where this site needs them not to. Every argument that builds a position worth a stated value beside another position — every sum, every comparison, every counterexample assembled rather than found — needs the second. A census that says a value is reachable does not say by what, and searching for the position that realises it is the search the census was supposed to have replaced.

That is also why the failed obvious construction is worth a section rather than a footnote. Laying the two options either side of a single domino of each colour is the recipe anybody would try first, it is right about the shape of the answer, and it is wrong about the value often enough to be useless. Knowing exactly which step of it fails is what makes the repaired version a recipe rather than a guess that happened to work on the cases somebody checked.

There is a general habit in that, and it is the reason this ladder spends a rung on a construction the census had already made unnecessary in appearance. A census is cheap to extend and says less every time; a construction is expensive to get right and, once right, answers questions nobody asked it. The count of a thousand values in seven dominoes is a fact about seven dominoes. The recipe is a fact about the game.

Where the ladder goes next #

toppling-dominoes has three rungs: the game and its two-colour values, the third colour with the cost measure it makes possible, and now the construction that does not work.

The rung above is a construction that does. The one place this page can point at is the ordinal sum: a row is a sequence, an ordinal sum is a sequence of games, and the ordinal sum is the operation that builds a game whose options include the base’s options and nothing that straddles anything. If a row can be read as an ordinal sum of its dominoes — and the numeral rule on Hackenbush is exactly that reading for strings — then a construction would be a matter of writing a canonical form as an ordinal sum, which is a question about forms rather than about rows.

Two neighbours are worth the trip. What a value costs to write down is the same question asked of notation, where the birthday is again the measure that fails and the answer is again a third quantity. And how long a row a value needs is the census this page was meant to replace, worth rereading for the two values it names whose lengths the birthday cannot explain — they are the ten this page found the option count cannot explain either.