What the colon respects

The ordinal sum G : H is play in H while G is untouched; a move in G wipes H out. It is what a Hackenbush stalk is — the edge nearest the ground is G, everything above it is H, and cutting low removes the lot — and it is the one operation on this site that fails to respect equality.

When the nested sum only sees the value established the failure with the standard example. 0, {∗ | ∗} and { | ∗} are all worth zero; placed under a star they give ∗, ∗2 and ↓∗. It closed by asking the question the failure leaves:

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.

The answer is that it respects equality. On 636 of 640 values.

What is being enumerated #

The census builds forms rather than choosing them, and that is what makes the answer mean anything. Choosing three forms of zero designed to disagree proves that disagreement is possible; building every form in a range and counting the disagreements says how much of the range they occupy.

The range is every game {L | R} where L and R are antichains of day-two values — sets no two members of which are comparable. There are 98 such antichains, so 9,604 forms, and between them they reduce to 1,474 distinct values, which is exactly day three. A form whose option lists were not antichains would have a dominated option and would reduce; excluding those is not a restriction on the values reached, only on the ways of writing them.

Six hundred and forty of the 1,474 values have more than one such form, carrying 8,770 forms between them. Those are the values on which the question can be asked at all: a value with one form has nothing to disagree with.

Six hundred and thirty-six agree #

For each of the 640, the census takes every form of it, computes the ordinal sum with star, and counts how many distinct answers come out.

On 636 of them the answer is one. Every form of 1/2 — and there are 238 of them — gives exactly the same G : ∗. Every form of ⇑, of 2·↑∗, of {1 | 0, ∗}, of every switch, every infinitesimal and every number except three.

That is not what the standard warning prepares a reader for, and it sits oddly beside how many forms a value has — 238 ways of writing a half, all of which the colon treats identically.

The warning is that the colon is an operation on forms, which is true, and it is usually delivered with an example and no measure. It leaves the impression that substituting an equal game into an ordinal sum is a thing one simply may not do. The measure says it is a thing one may almost always do and cannot rely on — which is the same shape as every restricted-equality result on this site, where a relation that fails in general is asked how often it fails in practice.

The four are day one #

The values whose forms disagree are 0, 1, −1 and ∗.

Those four are the values born by day one, and nothing else in the census is born by day one. The correspondence is exact and the census asserts it: a fifth value whose forms disagreed would stop the build.

Zero is the extreme case by a long way. It has 2,401 forms in this range — a quarter of everything built — and they give 61 different ordinal sums with star. One is ∗, one is ∗2, one is ↓∗, and there are fifty-eight more.

The ratio is what makes zero the extreme rather than the raw count. Zero’s 2,401 forms produce 61 answers, which is one answer for every forty forms; star’s 196 produce 36, one for every five and a half. So star is the value the colon separates most finely and zero is the value it separates most widely, and those are different superlatives. A reader who wants the sharpest single demonstration that the operation reads the writing should take star, where fewer than six forms are needed on average to reach a new answer; a reader who wants the largest spread should take zero, where the answers run from a nimber to an infinitesimal.

∗ has 196 forms giving 36 answers. 1 and −1 have 328 forms each giving 14 answers each.

Star is worth looking at directly, because five of its forms are enough to reach five different answers.

Two of those answers are nimbers and three are not, and which is which is not an accident. Exactly two of the five forms are impartial positions — both players holding the same moves — and they are precisely the two whose answers come out ∗2 and ∗3. The other three are partizan games that happen to be worth star: {↑ | ↓} offers Left an up and Right a down, and no rearrangement of that is a Nim heap. An ordinal sum of two impartial games is impartial, so those three could not have produced a nimber whatever the arithmetic said.

The colon can therefore see the difference between an impartial position and a partizan one worth the same, and the value cannot. That is the whole of this page in five rows, and it is why the exception class is a statement about writing rather than about arithmetic.

Why day one and not something else #

The mechanism is in the recursion and it is worth working through, because it explains the shape of the exception rather than merely naming it.

G : H has as its options G’s own options, together with G : h for each option h of H. So the base enters twice: once as a list of options carried straight through, and once as the thing every follower option is nested under.

Now take two forms of the same value. Their options differ — that is what makes them two forms — and those differing options are carried straight into the ordinal sum. Whether the sums come out equal depends on whether those extra options are dominated or reversible in the sum, and that is decided by how they compare with G : h.

For a value born late, G : h is a substantial game and it dominates the loose ends. For a value born on day one, G : h is small — 0 : ∗ is ∗, and almost anything a form of zero carries around is comparable with it — so the loose ends survive and show up in the answer.

So the exception class is the values small enough that their forms’ differences are not swamped, and on day two and beyond they always are. That is an argument rather than a proof, and it is the argument the census is evidence for.

It is worth being careful about which quantity small refers to, because two are available and they come apart. It could be the birthday of the base — how many days of construction the value took — or the width of the form doing the swamping, which is how many options are there to compare the loose ends against. On this census the two are indistinguishable: the four exceptions are exactly the day-one values and those are also the values whose forms are narrowest. Separating them needs forms whose options are deeper without being wider, which is a sweep this page does not run and the rung above does.

That is the mechanism in the smallest case that shows it. The four answers agree about everything a number can record and differ by an up, a down or a star — which is to say they differ by exactly the part of a position that a value is designed to keep and a form is not.

The population that question is asked over is worth seeing before the answer is trusted, because the argument above is about how many forms a value has and how much they differ.

The same four, whatever goes on top #

A reader might reasonably suspect that star is doing the work — that the exception class is about the pair rather than about the base.

It is not. The census repeats with 1, −1 and ↑ as the follower, and each of them separates the forms of exactly four values, and they are the same four.

The follower zero is the exception that confirms the arithmetic. G : 0 is G itself, so two forms of one value must give the same answer, and the census reports 640 of 640 agreeing. It is worth including because a run in which zero separated something would mean the ordinal sum was implemented wrongly.

So the exception belongs to the base. That is the form a description of the operation needs: the ordinal sum is a function of its base’s value except when the base is worth 0, 1, −1 or ∗, which is a much more usable sentence than the ordinal sum is a function of the form.

What this does to the colon principle #

The colon principle is the theorem that lets a green Hackenbush tree be collapsed one branch at a time: replace a branch by a Nim heap of the same value and the whole is unchanged. It is stated for impartial games, and this site checks it over a census of substitutions.

The relationship between that theorem and this page’s census is worth stating carefully, because it is not that one generalises the other.

The colon principle is about the follower, and this page is about the base. The principle substitutes inside H, the game sitting on top, and says an equal-valued replacement is safe there. This census substitutes G, the base, and finds it safe except on four values. The two are different substitutions into the same operation and they have different answers, which is exactly why the ordinal sum’s rule is stated in terms of a trunk and not in terms of what the trunk is worth.

And the practical reading is a rule of thumb with a checkable side condition. Substituting an equal base into an ordinal sum is safe unless the base is worth nought, plus or minus one, or star — and those are four values a reader can recognise on sight. That is a licence, and the rung below could not give one.

Where a Hackenbush stalk sits in this #

The concrete case is worth naming because it is where anybody meets the operation first.

A Hackenbush stalk is a chain of coloured edges standing on the ground, and its value is an ordinal sum read from the ground up: L is 1, LR is 1 : (−1) which is ½, LRL is ¾. The bases in that reading are always 1 or −1 — two of the four exceptional values.

So the one place a reader routinely meets the ordinal sum is the place where the base’s form matters, and it matters constructively: the whole binary reading works because 1 : X depends on more than the fact that the bottom edge is worth one. Change the form of that bottom edge — make it a green edge, worth ∗ — and the reading changes completely, which is what happens when a stalk goes green.

So the exceptions are not an inconvenience at the edge of the theory; they are where the theory is used. That is an unusual shape for an exception class and it is the most surprising thing the census found.

What a coarser equivalence would have to be #

The rung below asked whether there is a coarser equivalence the operation is a function of, and the census answers it in a way worth spelling out because the answer is not yes and not no.

There is a partition the ordinal sum is a function of, trivially: group the forms by the answer they give. On day one that partition is finer than equality — zero’s 2,401 forms fall into 61 groups — and everywhere else it is exactly equality. So the equivalence exists and it is equality refined on four values.

The question underneath was whether that refinement has a description that does not mention the ordinal sum. On zero it would have to sort 2,401 forms into 61 classes, and the census has the classes and no description of them. The obvious candidates fail immediately: the classes are not by the number of options, nor by the option values as a set, since the operation carries the option games through as objects.

What it does have is a bound. Any equivalence the operation is a function of must be at least as fine as equality-refined-on-day-one, and at most as fine as identity of forms. The gap between those is four values wide, so the search for a description is a search over the forms of zero, one, minus one and star, and nothing else in the theory is in play.

That is a small enough object to attack. Two thousand four hundred and one forms of zero, sixty-one classes, and the question is what a class is. This page has not asked it, and it is the first thing the rung above should.

What the census does not say #

Four limits, and the second is the one that would change the sentence.

Antichains of day two. Every form here has its options drawn from the twenty-two values born by day two. That is enough to reach every value of day three, and it is not every form of those values — a form with a day-three option reducing to a day-two value is not built. So 636 of 640 is a statement about a large family of forms rather than about all of them.

And the four might not stay four. The exception class is values born by day one, checked over forms of depth two. A form of 1/2 with much deeper options might separate where a shallow one does not, and this census has no such forms in it. The honest statement is that on the forms built here the class is day one exactly.

One follower at a time. Each census fixes a follower and varies the base. Nothing here varies both, and an ordinal sum whose base and follower are both varied is a different and larger question.

And disagree is a coarse verdict. A value whose forms give two different answers and one whose forms give sixty-one are both counted as disagreeing. The counts are reported for the four, and the 636 are counted only as agreeing — a group in which every form agreed except one pair would look identical to a group in which they all agreed, and there are no such groups here because agreement is total.

The convention, named #

Normal play. G : H is defined by G : H = { G^L, G : H^L | G^R, G : H^R } — the base’s own options unchanged, and the follower’s options nested under the same base. Everything is reduced to canonical form before comparison, so two ordinal sums count as different when their canonical forms differ.

A form here is a game {L | R} with L and R antichains of day-two values; games are interned, so two forms are the same object exactly when they have the same options, and the comparison of ordinal sums is by identity of canonical forms rather than by printed name — the printed name elides deep forms and would merge answers that differ.

The value of a form is its canonical form, and two forms are forms of the same value when those agree.

Where the ladder goes next #

The ordinal-sum anchor has three rungs to here: the operation and its Hackenbush reading, that it does not respect equality, and now how much of equality it respects anyway.

The rung above runs the sweep this page names as its own missing piece, and the answer is the one that would have been reported as boring and is not. No fifth value builds the forms one day deeper — day-three gift horses added to day-three values, eighteen thousand forms — and finds no disagreement at all, while the same treatment still splits nought four ways.

That is the opposite of what this page’s closing paragraph expected in an instructive way. A fifth value would have meant the exception class is about size; no fifth value, on forms whose options are a whole day deeper, means it is not about the depth of the options either. What it is about is the width of the base’s form: a base with few enough options for two of its forms to differ in what the colon can see, and by day three every value has enough options that they cannot.

So the class is exactly the four values born by day one, and the reason is a fact about how small a form has to be for two of its writings to be distinguishable by an operation that reads the writing. That is a better answer than a birthday, because a birthday is a bound on how a value was built and a width is a statement about the object in hand.

Two neighbours are worth the trip. When the nested sum only sees the value is the rung below, where the failure is established and the colon principle’s own substitution is checked; reading the two together separates the two substitutions, which is the thing most accounts of the operation run together. And Hackenbush is a numeral is where the ordinal sum earns its keep, and where the bases are two of this page’s four exceptions from beginning to end.