The other sum, the one that nests

Every technique on this site is built on one operation. In the disjunctive sum, a move is a move in exactly one component and the others are untouched — which is what makes values add, and is the whole reason a board that falls apart is easier than one that does not.

Three ways to add the same games surveys the alternatives — move in every part at once, move in any set of parts — and finds that none of them has a value theory. There is a fourth operation, it is not in that survey, and it has one: the ordinal sum.

G : H is the game where a move in G wipes out H entirely, and a move in H leaves G standing.

The definition, and where it already was #

Written out, G : H = {G^L, (G : H^L) | G^R, (G : H^R)}. A player may move in G, which throws away everything H had, or in H, which leaves G in place.

That is not an invented operation. It is a description of a Hackenbush stalk, which has been on this site since the first essay about numerals: cutting an edge low down drops everything above it, and cutting high leaves the base intact.

So the picture came first and the operation is what the picture was doing. A stalk of n edges is n one-edge games nested rather than n games side by side, which is why the value of a stalk is a binary expansion rather than a sum of ±1s.

The contrast with the operation this site normally means is in the same picture, one line lower. Three stalks standing on three separate points of ground are a disjunctive sum: a move in one leaves the other two alone, and the values add. Three edges standing on one point of ground are an ordinal sum: a move low down takes the rest with it, and nothing adds. The ground is the whole of the difference, and it is a feature of the drawing rather than of any label in it.

Why a stalk is a numeral #

The binary reading of a blue-red stalk falls out of the definition rather than being a separate fact.

The bottom edge decides the integer part: a blue edge at the ground is worth 1 and everything above it can only modify what is left after it goes. Each subsequent edge is worth half as much as the one below, because it sits inside the interval the edge below left open, and the simplicity rule picks the simplest number in that interval at every level.

So 1 : (−1) is the simplest number strictly between 0 and 1, which is 1/2; and 1 : (−1) : 1 is the simplest between 1/2 and 1, which is 3/4. The halving is the nesting.

The values a stalk can reach are exactly the dyadic rationals, and the length of the stalk is the resolution: a stalk of $n$ edges lands on a multiple of $2^{1-n}$, a longer one fills the gaps between those, and no stalk of any finite length reaches a third. That is a fact about halving rather than about Hackenbush, and it is the reason the numeral reading terminates.

The colon principle, which is what it is for #

The reason the operation earns a name is a theorem about it, and the theorem is the one that makes green Hackenbush tractable.

The colon principle: G : H₁ ≥ G : H₂ exactly when H₁ ≥ H₂.

In words: what sits above a fixed base can be compared on its own, and the comparison survives being placed on the base. So a branch of a green graph may be replaced by any other branch of the same value without changing the value of the whole, which is exactly the licence fusion needs.

The principle is visible in three stalks that share a bottom edge. Take the base to be one blue edge, worth 1, and vary what stands on it: the two-edge top RL, the one-edge top R, and the two-edge top RR. Those three tops are worth −1/2, −1 and −2, in that order, and the principle predicts that the three whole stalks come out in the same order.

That is what the theorem buys and it is worth being precise about how little it says. It does not say the values are preserved — 1/4 is not −2 — nor that any arithmetic relates the two rows. It says the order survives, so a top may be replaced by anything at least as large without the whole getting smaller, and that licence is what lets green Hackenbush collapse a branch at a time.

The part that is not an operation on values #

Here is the finding, and it is the thing that separates this sum from the disjunctive one completely.

The ordinal sum reads the form of its left argument, not its value.

Take three positions all worth exactly zero: the empty game 0, the game {∗ | ∗}, and the game { | ∗}. Every pair of them is equal — the difference is a second-player win, checked by comparison, and either may be substituted for the other in any disjunctive sum whatever.

Stack a star on each and the results are ∗, ∗2 and ↓∗.

That is a genuine failure of substitution, and it is why the colon principle is stated for the argument on the right only. The base has to be a particular position, and replacing it by an equal one is not licensed by anything.

It is also why every textbook statement of the principle is phrased in terms of Hackenbush positions rather than Hackenbush values, and why this site’s fusion figure works on a graph rather than on a number. A reader who remembers the principle as “equal things may be swapped” has remembered it wrong in the one direction that matters.

Why it is the base and not the top #

The asymmetry is reported above as a fact to remember — substitute on the right, never on the left — and it has a reason visible in the definition, in one reading.

$$G : H = \{\, G^L,\; (G : H^L) \;\mid\; G^R,\; (G : H^R) \,\}$$

Look at where each argument appears. The base’s options are options of the whole, literally. $G^L$ and $G^R$ are copied straight across; the position $G : H$ offers them unchanged, and a player taking one gets exactly the position $G$ would have offered.

The top’s options never appear. What appears is $G : H^L$ and $G : H^R$ — the top’s options wrapped back inside the same construction. $H$ itself is not reachable from $G : H$; only things built from it are.

That is the whole explanation. Two forms of one value have, by definition, the same value and generally different option sets — that is what it means for a value to be a class of positions. So swapping the base swaps a set of options that the whole game hands directly to the players, and different options make a different game. Swapping the top swaps something the whole game only ever sees through one more application of the construction, and by induction that depends on the top’s value alone.

So the colon principle is one-sided because the definition is one-sided, and the three zeros are what exposure looks like: $0$ offers nothing, $\{\ast \mid \ast\}$ offers both players a move to $\ast$, $\{\ \mid \ast\}$ offers Right a move and Left none. Stack a star on each and those three option sets are still there, still available, still different — which is why the answers are $\ast$, $\ast 2$ and $\downarrow\!\ast$ rather than one value three times.

Which also explains the commutativity failure #

The same reading settles why $1 : \ast$ and $\ast : 1$ come out as different kinds of object rather than merely as different values.

$1 : \ast$ has the base $1$, whose single option is $0$, and that option is exposed: the whole game offers Left an immediate move to $0$. The result is $1\ast$ — a number with an infinitesimal on it, which is what a number’s option set produces.

$\ast : 1$ has the base $\ast$, whose options are moves to $0$ for both players, and both are exposed. The result is $\uparrow\!\ast$ — an infinitesimal, with no numeric part at all, because nothing in the exposed option set is a number.

The two pieces are the same and the arrangement decides which option set is on show. That is a stronger statement than “the operation is not commutative”: it says the operation is a way of choosing whose moves are immediate, and immediacy is the one thing a value cannot record.

The two arrangements are two stalks, and Hackenbush draws both. A green edge is one either player may cut, so it is the picture of ∗; a blue edge is 1. Put the blue one on the ground and the green one on top and the stalk is 1 : ∗; swap them and it is ∗ : 1.

Two edges, two orders, and the answers are not merely unequal but of different kinds. That is as sharp as the failure of commutativity gets, and it takes two edges to show it.

It is also the cleanest statement of what a Hackenbush stalk is doing. The bottom edge’s options are exposed and everything above it is nested, which is why the bottom edge decides the integer part and each edge above only halves what is left. A stalk is a numeral because the ordinal sum reads bases first, and the ordering of digits in a numeral is exactly an ordering of which options are immediate.

What it does to the rest of the arithmetic #

Setting the ordinal sum beside the disjunctive one, property by property, is the quickest way to see what kind of object it is.

Commutative? No. 1 : ∗ is 1∗ and ∗ : 1 is ↑∗ — a number with a star and an infinitesimal, from the same two pieces in the other order. The disjunctive sum is commutative and this is the first thing to go.

Associative? Yes, checked over 512 triples. So a stalk folds unambiguously, which is the property that lets a Hackenbush string be read at all.

An identity? Zero, on both sides. 0 : H is H because a base with no moves contributes none, and G : 0 is G because a top with no moves adds none — which is the one place the operation is as well behaved as addition.

Respects equality? On the right yes, on the left no — the finding above, and the reason the colon principle is stated one-sidedly.

Values add? Not remotely. There is no function taking the values of G and H to the value of G : H, which is the property the disjunctive sum has and every technique in this subject is built on.

So the ordinal sum is an associative, non-commutative operation on forms with a partial substitution rule. That is a much weaker object than the disjunctive sum, and it is why the subject has one general theory and one special principle rather than two theories.

What the operation is good for #

Three uses, in decreasing order of how much they are used.

It explains Hackenbush. Both the numeral reading of a blue-red stalk and the nimber of a green graph come out of it, and so does the awkward middle case where a green edge sits on a blue one and the value stops being either.

It builds values on demand. ∗ : ∗ is ∗2, and stacking stars gives the nimbers in order. Under the disjunctive sum, ∗ + ∗ is zero — so the two operations disagree about the same two objects as sharply as they can.

And it names the general shape of a game with a base. Any position where one move destroys the rest of the board is an ordinal sum in disguise: a stalk, a chain in a graph game, a stack of anything.

It is worth saying where the operation sits among the ones already surveyed. The three compounds — disjunctive, conjunctive and selective — are all ways of putting two independent games side by side and differ only in how many of them a move touches; of those three, only the disjunctive one has values that add. The ordinal sum is not on that list at all, and not because it is a fourth kind of side-by-side. Its two arguments are not independent: one of them can destroy the other, which is a relation no compound of independent games can express.

The general shape it names #

Once the operation has a name, positions that were awkward turn out to be instances of it, and that is most of what naming an operation buys.

A chain in a graph game. Any structure where one move at the base removes everything downstream — a branch hanging off a vertex, a stack of tokens, a column of anything — is an ordinal sum of the base with the rest.

A game with a “lock”. A position where one player must first spend a move opening something before the rest becomes available has the same shape from the other side: the base is the lock, and what is above it is unreachable until the lock is played.

And a Hackenbush graph, region by region. A graph is not a stalk, so it is not an ordinal sum overall — but every bridge in it separates the graph into a base and a remainder in exactly this way, which is why bridge-finding is the algorithm that fusion runs on.

What the name does not buy is a shortcut. Recognising a position as an ordinal sum tells a reader how the moves relate, and the value still has to be computed level by level, because there is no formula from the parts’ values. That is the honest summary of the whole operation: a structural description with one theorem attached, and the theorem is about the top rather than the bottom.

Where the model stops #

No general value theory. Given G and H and their values, there is no formula for the value of G : H. The definition is constructive, so the answer can always be computed, and the answer is not a function of the two values.

The principle is one-sided. H₁ ≥ H₂ implies G : H₁ ≥ G : H₂, and nothing of the kind holds in the other argument: replacing G by an equal game can change everything, as the three zeros show.

And nesting does not decompose a board. The disjunctive sum turns a search over a whole position into a search over its parts, which is the exponential saving decomposition is about. The ordinal sum saves nothing of the kind: G : H has to be built level by level, and the cost is the cost of the whole tree.

Reading a stalk two ways at once #

The two operations meet in one place, and the meeting is worth a section because it is where a reader is most likely to conflate them.

A Hackenbush picture usually has several stalks standing on the ground. Within a stalk the edges are combined with the colon; between stalks they are combined with a plus. So a picture of three stalks is a disjunctive sum of three ordinal sums, and both operations are in one drawing.

That is why a figure of separate sprigs adds its labels and a figure of one stalk does not. LR and LRL standing side by side are worth 1/2 + 3/4 = 5/4; the five edges rearranged into one stalk LRLRL are worth 11/16, and neither number is obtainable from the other.

The practical rule for reading a Hackenbush picture is therefore: the ground separates, and everything above one point of ground nests. A cut at the ground removes a whole stalk from the sum; a cut higher up changes one stalk into a shorter one.

Getting that backwards is the commonest way to misread the game, and it is invisible in the arithmetic, because both operations produce numbers on blue-red pictures and the wrong one produces plausible ones.

What the picture cannot show #

A stalk is drawn as a column of coloured edges, and the drawing shows the nesting perfectly — everything above a cut falls, and the picture makes that obvious.

What it cannot show is that the nesting is an operation. A reader sees one object; the claim is that the object is built from smaller ones by a rule, and the rule is invisible in the result. The ordinal reading printed under each stalk is the only place it appears, and it is text rather than picture.

The other thing not shown is the failure of substitution. Three positions worth zero cannot be drawn as three Hackenbush stalks — the games {∗ | ∗} and { | ∗} have no stalk — so the figure that demonstrates it prints brace expressions instead, in an essay whose subject is a picture. That is the honest way round: the finding is about forms, and a form is a written object.

What a second operation says about the first #

It is worth asking what is learned about the disjunctive sum by having something to compare it with, because for most of this site it has been the only operation in the room.

The answer is that its good behaviour is not automatic. Values add, equals may be substituted, components may be reordered, and a board may be broken into parts and solved separately — none of which is true of the ordinal sum, which is a perfectly reasonable operation on games defined in one line.

So the disjunctive sum is not “the way games combine”. It is one way among several, and it is the one with the theory because of specific properties: independence of the parts, and a move affecting exactly one of them. The compounds essay makes the same point from the direction of moving in several parts at once; this one makes it from the direction of moving in a part that destroys another.

The lesson for reading any new game is to ask which operation its structure is, before reaching for the arithmetic. A position that looks like two components and behaves like a stalk will give wrong answers to every technique on this site, and the wrongness will be quiet — the numbers will still be numbers.

The convention, named #

Normal play throughout, and one convention about the notation.

The colon needs no bracketing. G : H : K is unambiguous because the operation is associative — checked here over all 512 triples from a pool of eight values, with no failure — so a stalk of any length may be folded from either end and gives the same game. That is worth knowing precisely because the operation fails so many other expectations: it is not commutative, it does not respect equality on the left, and it still associates.

The other convention is the one that makes the operation well defined at all: a move in the base destroys the whole of the upper part, rather than leaving it floating. In Hackenbush that is the ground rule; in a general game it is a modelling decision, and any position claimed to be an ordinal sum has to have that property rather than merely resemble one.