When the nested sum only sees the value

The ordinal sum nests one game under another: play in the upper part, and a move in the lower part wipes the upper part out entirely. A Hackenbush stalk is exactly that — cut an edge and everything above it falls off — and the rung below this one establishes the awkward fact about it.

It is not an operation on values. Positions all worth zero, placed under the same star, do not all come out the same: the rung below takes three of them and gets $\ast$, $\ast 2$ and $\downarrow\!\ast$. Equal games are interchangeable inside every disjunctive sum there is; inside an ordinal sum they are not, because the operation reads the form.

So the ordinal sum sits outside the value theory. Except in one large and important case, where it does not.

It is worth being exact about what “outside the value theory” means, because the phrase is doing real work. A value is what survives when a position is put inside something larger: two games are equal when no disjunctive sum can tell them apart, and the whole apparatus of this site — canonical forms, comparison, the arithmetic — is built on that one substitution property. An operation that can tell equal games apart is an operation the values were not designed to describe.

The exception #

Restrict everything to impartial games — both players with the same moves, every position worth a single nimber — and the operation becomes a function of values after all.

The colon principle. If the upper part of an ordinal sum is replaced by any impartial game of the same Grundy value, the whole is unchanged.

That is a substitution theorem for an operation that has just been shown not to admit one, and the restriction to impartial games is doing all the work.

The census’s headline row is a substitution between two heaps worth $\ast$ or $\ast 2$, and it leaves out the rows that answer the partizan counterexample most directly: the pairs where both games are worth nothing.

That is the comparison the whole essay turns on, drawn twice on the same page. Zero written six ways partizan gives three answers; zero written every way an impartial family here supplies gives one.

The nesting, and what a move in the base does #

The ordinal sum is worth restating in the form a player would meet it, because the asymmetry is where all the strangeness comes from.

In $G : H$ — read “$G$ colon $H$” — both parts are on the board, and a player may move in either. A move in $H$, the upper part, leaves $G$ alone and the position becomes $G : H'$. A move in $G$, the lower part, deletes $H$ entirely: the position becomes whatever the move in $G$ produced, with nothing above it.

A Hackenbush stalk is exactly this. The edges above a given edge are the upper part; cutting the given edge drops everything above it into the sea. So a stalk of $n$ green edges is an ordinal sum of $n$ single edges, one on top of another, and the whole subject of green Hackenbush is what such a nest is worth.

The deletion is what makes the operation read the form. In a disjunctive sum, the only thing the rest of the board can learn about a component is which positions it can be moved to — which is exactly what its value records. In an ordinal sum the base can annihilate the upper part, so what matters about the upper part includes how long it survives and what it offers before it is deleted, and two equal games can differ in both.

Why the two cases differ #

The reason is visible in what the partizan counterexample uses.

$0$, $\{\ast \mid \ast\}$ and $\{\ \mid \ast\}$ are all worth zero, and they differ in what a player can do in them: the first offers nothing, the second offers both players a move to $\ast$, the third offers Right a move and Left none. Ordinal-summing keeps those moves — a move in the upper part is still a move — and the base is only wiped out when somebody moves below. So the sum can tell them apart even though nothing containing them as a disjunctive summand can.

For impartial games the same argument runs and stops. Two impartial games of the same Grundy value do differ in their move sets; but every impartial game of value $\ast k$ has, by the mex rule, moves to every smaller value and none to its own, and the ordinal sum’s behaviour depends only on that pattern. The extra moves that distinguish the partizan forms are moves to values one player can use and the other cannot, and impartiality removes exactly that distinction.

Which forms come apart, and why those, is the question the rung above measures over every form a whole day of the construction supplies. What matters here is only that some do, so that the impartial result has something to be surprising against.

Three games, three ways of being worth two #

The census substitutes across families deliberately, and the families are worth seeing.

A Nim heap of two is the game whose options are the heaps of one and nothing — two moves, one for each player, leading to a heap of one and to nothing. A subtraction heap of two under $\{1,2\}$ has options at $1$ and $0$, which happens to be the same shape: eight options over two levels, in both cases. A subtraction heap of five under $\{1,2\}$ is worth $\ast 2$ as well, and its option set is nothing like either — it has options at four and at three, its tree runs five levels deep, and there are 188 options in it.

All three are worth $\ast 2$, and “worth” here means what it always means on this site — the difference of any two of them is a second-player win, checked by playing it.

The census substitutes only across families, because two heaps of one game share a great deal of structure by construction and would be a weaker test. So of those three games it makes two pairs — the Nim heap against each of the two subtraction heaps — and runs each under the three bases, which is six of the seventy-two rows. The pair that carries the weight is the one with the heap of five in it: a Nim heap of two and a tree twenty-three times its size, interchangeable under the colon because they are worth the same and for no other reason.

What it buys a tree #

The principle is not an ornament: it is the entire reason green Hackenbush can be read off a picture instead of searched.

A tree standing on the ground is an ordinal sum of its branches over their stalks. Take the topmost branch, replace it by the Nim heap it is worth, and the tree is smaller by one branch; repeat. That is the colon principle applied recursively, and it is what turns a nine-vertex lattice from a 1,283-position search into a dozen steps.

The other half of green Hackenbush — fusing the vertices of a cycle — is a separate principle with a separate proof. The colon principle handles trees; fusion handles everything that is not a tree; together they read any green position without playing it.

The easiest case to see it on is a plain stalk. A green stalk of $n$ edges is worth $\ast n$, one stalk standing on another is the ordinal sum of the two, and the whole picture therefore reduces to a heap whose size is a count. The site’s check on those is the one that matters: the structural reading and the exhaustive search agree everywhere both are run.

Why impartiality rescues it, exactly #

The account above — that impartiality removes the distinction the partizan counterexample turns on — is true and is not the mechanism. The mechanism is a strategy, it is four lines long, and the place it needs impartiality is not where a reader would expect.

To show $G : H_1$ and $G : H_2$ are equal, this site’s definition of equality demands one thing: that their difference is a second-player win. So write the difference down.

$$-(G : H) = (-G) : (-H),$$

because negating a position swaps the players everywhere in it, base included. And for impartial games $-G = G$, so the ordinal sum is its own negative — one of the values with that property — and the difference to be played is

$$G : H_1 \;+\; G : H_2,$$

with the same base underneath both halves. That is the whole of what impartiality buys, and everything else follows from it.

Now play that sum as second player, given that $H_1 + H_2$ is already a second-player win.

If the opponent moves in an upper part, answer in the other upper part, following the strategy that makes $H_1 + H_2$ a second-player win. The two upper parts stay equal to one another and the two bases are untouched.

If the opponent moves in a base, that base’s upper part is wiped out and the position is $G' + G : H_2$. Answer by making the same move in the other base, which wipes out the other upper part and leaves $G' + G'$ — which is zero, because it is a position added to itself in a theory where every impartial position is its own negative.

Second player always has a reply, so the difference is a second-player win, so the two ordinal sums are equal.

Where the partizan case breaks #

Run the same argument without impartiality and it fails at the first line rather than at the last.

$-(G : H_2)$ is $(-G) : (-H_2)$, whose base is $-G$ and not $G$. So the difference $G : H_1 - G : H_2$ is a position with two different bases, and the answer-in-the-other-base move that carried the second half of the strategy has nothing to answer into: making the same move in a base that is the mirror of the first does not leave $G' + G'$, it leaves $G'$ beside the mirror of $G'$, which is zero only by accident.

That is a much more specific diagnosis than “the operation reads the form”. The operation reads the form because the strategy that would have made it read the value cannot be set up, and it cannot be set up because the base does not survive negation. Three forms of zero giving three different answers is the symptom; the base being unable to pair with its own mirror image is the cause.

And it says which restriction is really doing the work. Not “the upper parts are impartial” — the argument needs the base to equal its own negative, since that is what makes the two bases match. Impartial games are the obvious supply of such positions, and they are not the only one: the switches are their own negatives too. Whether the colon principle survives on a base like $\pm 1$ with partizan upper parts is a question this essay’s census cannot answer, because every game in it is impartial on both sides — and it is a sharper version of the open question the last section names.

Two operations that share a notation #

A last confusion worth heading off. The colon principle makes the ordinal sum look like the disjunctive sum on impartial games — both respect values, both allow substitution — and it is tempting to conclude that on impartial games the two operations coincide.

They do not, and the difference is easy to see. The disjunctive sum of two Nim heaps of one is worth zero: the second player copies, and the position is a second-player win. The ordinal sum of a heap of one under a heap of one is a stalk of two edges, worth $\ast 2$ — a first-player win with a move to $\ast$ and a move to nothing.

So the two operations agree about which substitutions are legal and disagree about everything else. What the colon principle buys is not that the ordinal sum has become a disjunctive sum; it is that the ordinal sum has become a function, on a domain where it previously was not one.

Put colours on the edges and the function is gone again. A blue-red stalk is an ordinal sum read from the ground up, and its value comes out of the sequence of colours in binary — a rule about the arrangement rather than about what any part of it is worth. Replacing the upper part by an equal-valued position changes the answer there, which is the opening figure’s failure happening in the game the operation was invented for.

What the solver computed, and how #

The census builds impartial games as game objects rather than as Grundy numbers, which is the only way the substitution can be performed rather than assumed.

A Nim heap of $n$ is the game whose options are the heaps below it, on both sides. A subtraction heap of $n$ under the set $\{1,2\}$ is the game whose options are $n-1$ and $n-2$, on both sides. These are different games — the subtraction heaps have Grundy values that repeat with period three, so a heap of 3 is worth nothing and a heap of 5 is worth $\ast 2$ — and pairs are selected by testing $a = b$ with a difference game, never by comparing the numbers used to build them.

Each selected pair is then substituted under three bases, and the two ordinal sums are compared the same way. 72 substitutions came through unchanged.

The partizan counterexample in the first figure is the same machinery run without the impartiality restriction, and it throws rather than draws if the three forms ever stop disagreeing — an assertion that has to be able to fail.

Where the principle is doing the work #

The reduction of a green graph has two halves and it is easy to attribute both to the wrong one.

Fusion handles cycles: every vertex on a cycle may be fused with its neighbours, turning the cycle into a single vertex with self-loops attached. That is a statement about cycles and it has nothing to do with ordinal sums.

The colon principle handles what is left, which is a tree, and it is the half this essay is about: a branch may be replaced by the Nim heap it is worth, because the branch sits above the edge that would delete it and is therefore the upper part of an ordinal sum.

Run them together and any green position collapses to a single heap without a search. The site’s own check is that the collapsed answer agrees with an exhaustive solution of the same graph — which is the form every claim on this site takes when a shortcut is being asserted, and the reason a nine-vertex lattice can be read in twelve steps instead of 1,283 positions.

The principle as a strategy statement #

Substitution theorems are usually read as licences for algebra, and this one has a reading a player can use.

Suppose a green Hackenbush position has a branch worth $\ast 3$ hanging above an edge. The colon principle says the whole position is worth the same as it would be with a Nim heap of three hanging there instead. So a player deciding what to do in the branch is deciding what to do in a Nim heap of three, and everything the impartial theory knows about Nim heaps applies: the winning move is the one that leaves the right nim-sum, and the branch’s internal shape is irrelevant to the choice.

That is why green Hackenbush is playable by a person and blue-red Hackenbush is not. The reduction does not merely compute a value at the end; it replaces the position, during play, by one small enough to think about.

The partizan case has no such reading. A blue-red stalk is an ordinal sum too, and its value is read off the colours in binary — a beautiful rule, and one that depends on the sequence of edges rather than on any value attached to the part above. Substituting an equal-valued branch there is exactly the operation the first figure shows failing.

Where the model stops #

The check is a check. Seventy-two substitutions with small heaps is evidence, not a proof. The pairs come from three families with heaps up to five, the bases are three, and the equal-valued pairs the census finds are the ones those families happen to supply — a family with a longer period would contribute different pairs and possibly harder ones. What the census establishes is that the principle survives every substitution the site can build from games it already has; the colon principle is a theorem and this essay tests instances of it. What the test does establish is that nothing in the site’s own machinery contradicts it, which is the form of confidence this site can actually produce.

Impartial is doing the work, not “green”. The word green names a colour of Hackenbush edge, and what matters is not the colour but that either player may cut it, which is impartiality by another name. The principle is about the values, and green Hackenbush is one game where it applies. Any impartial game nested under any impartial game behaves the same way; a coloured Hackenbush edge — blue or red — takes the whole question back to the partizan case, where the first figure applies.

And the two sums are still different objects. Nothing here makes the ordinal sum a second disjunctive sum. It is not commutative, it has no identity worth the name, and the substitution theorem it admits under impartiality is exactly one property, not a value theory.

Where the ladder goes next #

Two rungs lead out. One is fusion — the other half of the green reduction, which is a statement about cycles rather than about branches, and which has its own substitution to check. The other is the boundary this essay drew and did not cross: what a partizan ordinal sum does respect, given that it does not respect equality, and whether there is a coarser equivalence it is a function of.