What can be struck out

Every game has a negative proves that $G + (-G)$ is a second-player win, by the mirroring strategy, and names its own next rung in as many words: cancellation, and the fact that a component common to two positions can be struck out of a comparison. This is that rung.

The theorem is one line. From

$$G + X = H + X$$

add $-X$ to both sides. The $X$ and the $-X$ cancel on each side because each is a second-player win, and $G = H$ falls out.

It is the shortest thing on this site and it is the most used. Every decomposition here rests on it. Comparing a Domineering board against another differing in one region means comparing the two regions, because everything else subtracts away — and that is why a decomposition is worth making rather than merely possible.

The hypothesis has to fire #

A law checked by exhaustion is only checked on the cases that reach it, and a sweep in which the antecedent is almost never true has verified almost nothing.

Over the 22 values born by day two there are $22^3 = 10{,}648$ ordered triples. In 484 of them $G + X$ really does equal $H + X$; in the other 10,164 the hypothesis is false and the implication is vacuous.

Four hundred and eighty-four is $22^2$, which is not a coincidence: $G + X = H + X$ with the group law available holds exactly when $G = H$, and among 22 distinct values that means $G$ and $H$ are the same value, which is 22 choices, times 22 for $X$. So the sweep confirms the law and simultaneously explains its own count, which is the most one can ask of a check on a one-line theorem.

What it licenses #

The use is substitution, and it is worth seeing as a picture rather than as an identity.

Two boards differ in one region. Board A has region $P$ where board B has region $Q$; everything else is shared. Which board is better for Left?

Without cancellation the question is about the whole boards, and the whole boards are large. With it, the shared part subtracts away and the question is whether $P \ge Q$ — a comparison between two small things.

The same move underlies the substitution rule that lets a component be replaced by an equal one anywhere it appears, which is what “equal in every company” means — and the two are the same theorem read in opposite directions.

The proof needs the group, and three conventions have not got one #

Cancellation is a consequence of invertibility and of nothing else. Take away the negatives and the argument evaporates. Whether the conclusion goes with it is a separate question, and in all three directions this site has essays about, it does.

On absorbs everything #

A loopy position need not end, and the class of loopy games is where the first of the three failures lives.

A loopy game can go on for ever, and $\mathsf{on}$ — the single position from which either player’s only move is back to $\mathsf{on}$ again — absorbs whatever is added to it. For every short $G$,

$$\mathsf{on} + G = \mathsf{on}$$

so $\mathsf{on} + 1 = \mathsf{on} + 2$ while $1 \ne 2$. The hypothesis holds for every pair whatever, and the conclusion is false for almost all of them.

Nothing is wrong with the arithmetic. What is missing is the negative: $\mathsf{on} + (-\mathsf{on})$ never ends, so there is nothing to add to both sides, and there is no step of the proof that survives.

The second column is what keeps the failure honest. $\mathsf{off}$ is loopy as well — only Left may move in it, for ever — and it does not absorb: Right is stuck at once, so four of the five additions leave every position of the sum decided. The one that does not is the cycle of three, which never ends on its own account and drags whatever it is put beside into a draw. So the difference is between a component that absorbs and a component that merely fails to finish, and only $\mathsf{on}$ swallows a decided game whole.

A scoring game has no zero #

Under scoring play a position is worth a number of points rather than an outcome class, and the mirroring strategy is still available: answer every move with the mirror move, in the mirror component.

It no longer wins nothing.

The mover wins by four on $1, 2, 3$ against its mirror; by six on $3, 1, 2$; by eight on $2, 4, 1, 3$; by ten on $5, 1, 1$. Only $1, 1, 2, 2$ — a row already palindromic — comes out level, from both sides.

And the margin is symmetric: Left to move scores $+4$ and Right to move scores $-4$, so $G - G$ is not merely non-zero, it is a fight, with a stake of its own. Under normal play the sum of a position and its mirror is the most inert object there is; under scoring play it is a position both players want to move in.

So $G - G$ is not the identity, which means there is no identity to be an inverse relative to, which means the class is a monoid and not a group. It has an associative sum and a neutral element and no inverses at all. Cancellation is not a theorem about monoids, and there is no reason to expect it to hold.

Misère play took the negatives first #

Misère play has no negatives: $G + (-G)$ is a first-player win for every $G$ in the pool, because the mirroring player is the player who always has an answer and therefore the player who eventually has to make the last move.

So the one-line proof is unavailable, and the question has to be asked directly rather than inferred. It can be: fix a universe — Nim positions with at most three heaps of at most four counters — define two positions equal when they have the same misère outcome in company with every position of that universe, and search for a common heap that makes two distinguishable positions indistinguishable.

That is the strongest of the three failures, because it is not a structural observation about a missing axiom — it is an exhibited counterexample in the game the whole misère theory is built around. A shared component is not free under misère play, which is exactly why the theory there works with quotients rather than with values.

Why the mirror stops working #

The mirroring strategy is the same three sentences under every convention, and it is worth writing them out to see which one breaks.

Whatever the opponent does in one component, answer with the reflected move in the other. True everywhere; nothing about the convention affects the availability of the answer.

Therefore the answerer always has a move. True everywhere, for the same reason.

Therefore the answerer wins. This is the sentence that is about the convention, and it is the only one.

Under normal play, a player who always has a move never runs out, and running out is what loses. The strategy wins.

Under misère play, running out is what wins, so a player who always has a move is a player who is going to have to make the last one. The strategy loses, every time, on every position in the pool.

Under scoring play, running out decides nothing at all — the score does — and the mirroring player, having matched every move of the opponent’s, has taken exactly the coins the mirroring gave them. On a row that is not palindromic, matching is not the same as matching in value.

So one sentence out of three is convention-dependent, and it is the sentence that draws the conclusion. Every failure of cancellation on this page traces to it.

What the three failures have in common #

All three lose the same axiom and they lose it in three different ways, and the ways are worth separating.

Loopy play has inverses for its short games and not for $\mathsf{on}$. The failure is local: one element with no inverse, and it happens to be absorbing, which is the worst possible combination.

Scoring play has no inverses at all, because the ending condition rewards a player for the number of moves made rather than for making the last one, and a mirror strategy that answers every move makes as many moves as it answers.

Misère play has no inverses at all, for a related but different reason: the mirroring player is the one guaranteed a reply, and under misère having a reply is what loses.

The common thread is that the group structure is not a property of the positions. It is a property of the ending convention, and every one of the three changes the ending convention. That is worth stating plainly because the algebra is usually presented as though it belonged to the games.

Who stated it, and how quietly #

Cancellation appears in On Numbers and Games as a remark rather than as a theorem, which is the correct weight to give it: in a partially ordered abelian group cancellation is immediate, and Conway had already established that the short games form one. There is nothing to prove once the group is in hand.

The reason it deserves a rung of its own here is not that the proof is hard. It is that the use is everywhere and the dependence is invisible. A reader who analyses a Domineering board by evaluating its regions is using cancellation at every step and will not have noticed, because the step looks like arithmetic rather than like an appeal to a theorem.

The place the dependence becomes visible is exactly where it fails, which is why three quarters of this essay is about the failures. Confused is not the same as unknown makes the same observation about a different axiom: the object is a partially ordered abelian group, the single missing axiom is totality, and every technique on this site uses the group and the order and not one of them uses totality. Cancellation is the clearest example of a technique that uses the group specifically — not the order, not the comparison, just the existence of inverses — and it is the first thing to go when the inverses do.

What the sweep cannot say #

The positive half is a check over 22 values, and 22 values is a small pool for a law that is claimed universally. What makes the small pool acceptable is that the theorem has a proof, and the sweep’s job is to catch an error in the implementation — a comparison routine that gets equality wrong would show up here as a triple where the hypothesis holds and the conclusion fails.

The misère half is bounded much more seriously. Equivalence there is relative to a universe, and the universe swept is 35 positions judged in company with 35 more. Two positions equivalent in that universe may be distinguishable in a larger one, so what the search found is a failure relative to a stated universe, which is the only kind of statement misère equivalence supports and is worth flagging every time.

The scoring half is five rows of coins. Five is enough to exhibit the failure and nowhere near enough to characterise it, and what a characterisation would need is a description of the rows for which the mirror does score level — the count above says that is the symmetric ones and does not say what symmetric means.

Recognising a cancellation is harder than using one #

The licence here is worth a great deal and it is worth being clear about where its cost sits, because the cost is not where a reader expects.

Using the cancellation is free. Two components known to be negatives of each other come off the board with no computation at all: strike them out, evaluate what is left, and the answer is exact. The saving is whatever those two components would have cost to evaluate, which on a board of hot regions is most of the work.

Recognising it is not free, and there are two quite different recognitions with different prices. Spotting that one region is the mirror image of another is a glance — it is a fact about the drawing, and a player sees it without evaluating anything. Spotting that a region is worth a value equal to its own negative needs the evaluator, because self-negativity is a property of the value and no property of the picture implies it.

So the licence splits by how the pair was found. A mirrored pair is cheap to find and cheap to use; a self-negative region is dear to find and, once found, cancels against any other copy of itself — which is worth more, because copies of a shape are common on a real board and mirror images of it are not.

That asymmetry is why the self-negative values are worth cataloguing at all. A one-off evaluation establishes a fact about a shape that pays every time the shape recurs, which is the same economics a catalogue of regions runs on — and it is the only sense in which knowing the subgroup is practically useful rather than structurally interesting.

The one direction that still works #

Something survives all three failures and is worth naming, because a reader who has got this far may conclude that nothing does.

Substitution of a position by an identical one is always safe. Replacing a component by a literally identical component changes nothing under any convention, because the resulting game is the same game. What fails is replacing a component by an equal one — where equality means “indistinguishable in the relevant sense” — and the three failures are three ways for equality to stop being a congruence.

That distinction is the whole of what the misère quotient is for. The quotient is constructed by taking a stated universe of positions and quotienting by the finest congruence available in it, which is a way of manufacturing the property cancellation would have supplied. The construction is expensive, it depends on the universe, and it produces a monoid rather than a group — but within it, cancellation-style reasoning is legitimate again, by construction rather than by theorem.

So the honest summary is not that cancellation fails outside normal play. It is that outside normal play cancellation is a thing that has to be built, universe by universe, rather than a thing that follows from a mirror strategy in one line.

The shape of a failure worth keeping #

One more distinction, because the three failures are not equally bad and a reader deciding what to do about them needs to know which is which.

The loopy failure is local and identifiable. Short loopy games have inverses and behave; $\mathsf{on}$ and its relatives do not. A board with no infinite component in it is a board on which cancellation is available in full, and the theory’s practice is exactly that — isolate the loopy parts, handle them by a different method, and use ordinary arithmetic on the rest.

The scoring failure is total and structural. There is no sub-class of scoring games on which the mirror strategy scores zero, other than the positions that are already symmetric, so there is nothing to isolate. What replaces cancellation there is a bound — Milnor’s, on how far a sum’s score can be from the sum of its parts’ means — and a bound is a weaker instrument that is available everywhere.

The misère failure is total and repairable at a price. The quotient construction manufactures the missing property for a stated universe, at the cost of a computation that grows quickly and an answer that is not portable between universes.

So the three directions call for three different responses, and none of them is “give up on decomposition”. They are: isolate, bound, and rebuild.

Where the ladder goes next #

The negation anchor has three rungs to here: that every game has a negative, which values are their own, and what may be struck out because of it. Five rungs stand above, and they follow the two-torsion subgroup from a temperature scale to an unexpected arithmetic.

The thirty that cancel themselves puts the subgroup on the temperature scale and finds it spread across the whole of it rather than gathered at the cold end — fourteen of the thirty are hot, one of them the hottest value its day produces. A self-negative value costs a day then dates them: the earliest self-negative value of temperature $t$ is born the day after $t$ itself.

At least five hundred and seventy-one turns the counting round. A value is its own negative exactly when its form is a mirror, so the subgroup can be built from subsets of the day below rather than sifted out of the day above — a floor of 571 on day four against day three’s twenty-six, and a share that keeps falling.

The last two rungs describe the mirror map itself. What identifies two subsets finds the collapse from 1,793 subsets of day two to thirty values happening in two stages of quite different character, with almost all of the second landing on two values. And a mex with no impartial game in it describes both of those fibres with one rule: the mirror of a set is the least nimber no element of the set reaches — a mex, in a construction with no impartial game anywhere in it.