The values that are their own negatives

Every position has a negative: swap the two players all the way down the tree, and the sum of a game with its mirror image is worth zero, because the second player answers each move with its reflection. That is what makes values a group, and it is what lets one position be subtracted from another.

A group invites one obvious question that this site has never asked. Which games are their own negatives?

The question is not idle. If $G = -G$ then $G + G = G + (-G) = 0$, so $G$ has order two — and a group in which most elements have infinite order can still hide a large collection of them. Counting is the only way to find out how large.

The guess, and why it is wrong #

The nimbers are the obvious candidates and they do qualify. $\ast n + \ast n = 0$ for every $n$, and the reason is the reason for everything impartial: a position where both players have the same moves is unchanged when the players are exchanged, so $-\ast n$ is $\ast n$ written out identically.

If impartiality were the only route to $G = -G$ the answer would be a small tidy set. It is not, and the counterexample is the plainest hot game there is.

$$\pm 1 = \{1 \mid -1\}, \qquad -\{1 \mid -1\} = \{-(-1) \mid -(1)\} = \{1 \mid -1\}$$

Negation reverses the two option sets and negates every option in them. For $\pm 1$ both operations undo each other and the form comes back character for character the same — which is worth doing slowly, because it is the whole mechanism: the Left option $1$ becomes the Right option $-1$, the Right option $-1$ becomes the Left option $1$, and the position that results is the position that started. So $\pm 1$ is its own negative, and $\pm 1 + \pm 1 = 0$ — a fact worth checking by hand rather than believing. Left moves in one copy to $1$; Right answers in the other copy with $-1$; the board is $1 + (-1) = 0$ and Left has to move again. The mirror strategy is doing the work, and here it happens to mirror one copy of a game onto another copy of the same game.

Why a group can have elements of order two at all #

A reader who has met the group of short games as “like the integers, with extra” will find $G + G = 0$ startling, and it is worth saying why the analogy breaks.

The values do form an abelian group: addition is associative and commutative, zero is the second-player wins, and every game has a negative obtained by exchanging the players. What they do not form is an ordered group in which every element is comparable to zero — the order is partial, and confusion is a fourth possibility beside greater, less and equal.

That is exactly the room the two-torsion lives in. If $G > 0$ then $-G < 0$ and the two cannot be equal; the same for $G < 0$. So a self-negative game has to be zero or confused with zero, and confusion is available here in a way it is not in the integers.

Put the other way round: the integers have no two-torsion because they are totally ordered, and the games do because they are not. The census reporting 29 fuzzy positions and one zero is that argument, checked.

Thirty, of which four #

The census runs the equality test over a whole day at once, which turns “are there others?” into a count.

Day nought has one value and it qualifies: $0$. Day one adds $\ast$, so the count is 2. Day two brings $\ast 2$ and $\pm 1$, making 4. Day three brings 26 more, and not one of them is a nimber: the count goes 1, 2, 4, 30.

The 26 include $\pm\tfrac12$ and $\pm 2$, which are $\pm 1$ with the stakes moved; $\{1\ast \mid -1\ast\}$, which is the same shape with a star hung on each option; and forms like $\{\uparrow\!\ast, \uparrow \mid \downarrow\!\ast, \downarrow\}$ where the two sides are visibly reflections of each other. Seven of the thirty are all-small; the rest are not, so this is not a phenomenon confined to the infinitesimals.

What the 26 look like #

The list is worth reading rather than counting, because the shapes repeat.

Symmetric switches. $\pm 1$, $\pm 2$, $\pm \tfrac12$ — any $\{x \mid -x\}$. Negating swaps the options and negates them, and a switch symmetric about zero comes back unchanged. These are hot: they have a temperature, they are worth fighting over, and they are their own negatives.

Switches with stars. $\{1\ast \mid -1\ast\}$ and its relatives, the same shape with an infinitesimal hung on each option.

All-small symmetric forms. $\{\uparrow\!\ast, \uparrow \mid \downarrow\!\ast, \downarrow\}$ and $\{0, \uparrow\!\ast \mid 0, \downarrow\!\ast\}$, where each Left option’s negative appears among the Right options. Seven of the thirty are all-small.

And mixed forms with no short name at all, such as $\{1, \{1 \mid 0\} \mid -1, \{0 \mid -1\}\}$, where the symmetry is visible only when the two option sets are written out side by side.

What none of them are is confined to a corner of the theory. Hot and cold, all-small and not, named and unnamed — the two-torsion runs right through the day, which is the sense in which it is a structural feature rather than a curiosity.

The shape they all have #

Reading the list is enough to suggest what is going on, and the suggestion turns into a test that can be checked without any search at all.

Negation swaps the option sets and negates each option, so $G = -G$ asks for the canonical form’s Left options to be, as a set, the negatives of its Right options. That is a property of the written form: put the form beside its mirror image and see whether the two coincide. No difference game, no comparison, no recursion.

The census computes both — the equality by playing $G - (-G)$ out, the symmetry by matching interned keys — for all 1,474 values. They agree on every one, with no disagreement in either direction. That is what makes the symmetry a characterisation rather than a pattern: a value is its own negative exactly when its canonical form is self-conjugate, and the canonical form is unique, so the test is decisive.

A characterisation that only ever confirms is not one, so it is worth running against a value that fails it. $\uparrow$ is $\{0 \mid \ast\}$: its Left option is $0$ and its Right option is $\ast$. Reverse the two and negate them and the result has Left option $\ast$ and Right option $0$, which is $\downarrow$ and not $\uparrow$ — so the symmetry test rejects it by looking. The equality test rejects it by playing: $\uparrow + \uparrow$ is $\Uparrow$, which Left wins whoever moves, and a value Left wins outright cannot be nought. Both tests reject it, and they agree in the same way on the 1,444 values of the day that are not on the list as they do on the thirty that are.

Zero or fuzzy, and nothing else #

The outcomes in the hero figure are not a coincidence and they are not a finding either; they are forced, and the argument is one line. If $G > 0$ then $-G < 0$, so $G \neq -G$. Likewise for $G < 0$. That leaves $G = 0$ and $G \parallel 0$, and the census duly reports one of the first and 29 of the second.

Put in playing terms: a game that is its own negative is either worth nothing at all, or is a first-player win. Neither player can have an advantage in a position which is unchanged when the players are exchanged, and the only ways to have no advantage are to have nothing at stake or to have everything at stake for whoever moves.

They form a group of their own #

The last structural fact falls out for free and is worth checking anyway. If $G$ and $H$ are both their own negatives then

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

so the sum is too. The self-negative values are closed under addition — a subgroup, and since every element is its own inverse, one in which every element has order two.

Checked rather than quoted: all 900 sums of two of the thirty come back self-negative, with no exception. That includes sums that leave day three entirely, which is the point of running it as a census rather than as an argument: the closure claim is about the whole group and the exhaustion tests it wherever the sums happen to land.

A subgroup of order two is a vector space #

The closure argument gives a subgroup and stops there, and one more step is available for nothing, because a group in which every element has order two is a very particular object.

An abelian group whose elements all satisfy $G + G = 0$ is a vector space over the field of two elements. There is nothing to check: the field has only $0$ and $1$, multiplying by $0$ gives zero, multiplying by $1$ gives the element back, and the axioms are the group axioms already established. The disjunctive sum is vector addition.

That changes what kind of questions can be asked about the thirty. A vector space has a dimension, a basis, and a notion of independence: some of the thirty are sums of others, and a smaller set generates all of them. It also means the subgroup’s size is a power of two, whatever it turns out to be — never thirty, never any other number.

The thirty are therefore not the subgroup. Twenty-nine of them are non-zero and distinct, and a space over two elements with at least twenty-nine non-zero vectors has dimension at least five, so the subgroup they generate has at least thirty-two members. The extras are the sums that leave day three, which the closure sweep already found and reported. What the day-three census counts is which vectors are born early, and being born early is not an algebraic property at all.

Where the nim-sum was hiding #

The vector-space reading also explains something the site has been using since its first essay without naming it.

The nimbers are inside this subgroup, and restricted to them, vector addition over two elements is $\ast a + \ast b = \ast(a \oplus b)$. Exclusive or is not a coincidence of binary arithmetic. It is what addition looks like on a vector space over the field of two elements, written in the basis $\ast 1, \ast 2, \ast 4, \ast 8, \ldots$ — one basis vector per bit, which is why a nimber’s binary expansion is exactly its coordinates.

Read that way, the nim-sum stops being a rule about columns that happen not to carry. It is a coordinate calculation in a space where every vector is its own negative, and “no carrying” is the statement that $1 + 1 = 0$ in the field.

The four nimbers of the day carry a good deal more structure than that basis needs, and it is worth knowing before deciding how much of the answer they are. They also multiply: the nimbers below four are a field, with an inverse for every non-zero element, which is as much algebra as any four values in this subject carry. All of it accounts for four of the thirty.

And the census says how much of the space that basis misses. The nimbers born by day three are four vectors; the self-negative values born by day three are thirty. The nimbers are a subspace, not the space — the impartial theory works inside a proper subspace of the two-torsion and the theory’s completeness is completeness relative to that subspace. Positions like $\pm 1$ live in the space, satisfy every identity the nimbers satisfy, and are not nimbers, which is exactly why self-negation cannot be used to prove Sprague–Grundy.

One more thing that follows for free #

Two other quantities are pinned by the symmetry alone and are worth reading off before any search.

Every self-negative value has mean value zero. The mean of $-G$ is $-\text{mean}(G)$, and $G = -G$, so the mean is its own negative — and the mean is a number, where the only such number is zero. So the switches on the list, hot as some of them are, all settle at nothing in the long run: $\pm 2$ is a fight over four points whose mean is zero, which is what makes it a fight rather than an advantage.

And the temperature is untouched by negation, since negating reflects the thermograph rather than reshaping it. So a self-negative value’s thermograph is symmetric about a mast at zero — the picture a reader would draw for such a position without being told, now derived rather than assumed.

What the subgroup is good for #

A subgroup is a structural fact and structural facts earn their place by deciding something. This one decides a class of positions at sight.

If a position is its own negative, it is not a win for either player. No search required: the value is zero or fuzzy, so either the second player wins or the first does, and which of the two is the only question left. That is a genuine shortcut, and this site has already used it — End-Nim’s palindromic rows are their own negatives, because reversing a row exchanges the two players, so all 168 of them in that census are second-player or first-player wins and none is a win for Left or Right.

And a sum of self-negative positions is self-negative, so the shortcut survives addition. A board made entirely of palindromic End-Nim rows is decided by the same argument, however many rows it has.

That is what closure buys. A property that held for one position at a time would be a curiosity; a property closed under the operation the whole subject is built on is a tool.

What the solver computed, and how #

Three sweeps, all of them over the same enumeration.

The 1,474 values born by day three come from the antichain argument described elsewhere on this site: a canonical form has no dominated option, so each side is an antichain of the 22 day-two values, there are 98 of those, and $98 \times 98$ forms canonicalise to 1,474 distinct values in about a quarter of a second.

The equality sweep tests $G = -G$ by building $-G$ from the tree and comparing, which is a difference game solved by the recursion. The symmetry sweep compares interned keys: for each value, the multiset of Left option keys against the multiset of negated Right option keys. The closure sweep builds all 900 sums of the thirty and re-runs the equality test on each.

Nothing here is asserted from the group axioms. $G + (-G) = 0$ is a theorem this site proves by playing the sum; every count above is a count of positions that passed a search.

Where the model stops #

The count is a count for a day, not for the subject. Thirty is the number of self-negative values born by day three; day four has more and this site cannot enumerate it. The pattern 1, 2, 4, 30 is four terms of a sequence, and four terms are not a formula — quoting a rate of growth from them would be exactly the kind of extrapolation this site refuses elsewhere.

The characterisation is also about the canonical form and nothing weaker. A form that happens to look symmetric need not carry a self-negative value, and a self-negative value can be written in forms that look nothing like their own mirror images — any number of gift horses can be handed to one side and not the other. The symmetry test is decisive because canonical forms are unique; applied to an arbitrary drawing it decides nothing.

And the whole question dissolves under misère play, where $G + G$ is not zero for anything at all. There is no group there, no negation, and so no two-torsion to count.

Order two, and what it is not #

Two clarifications, because the phrase “order two” invites both mistakes.

It is not “small”. $\pm 2$ has order two and a temperature of 2 — it is one of the hottest values born by day three, a fight over four points. Order is an algebraic property and has nothing to do with size.

And it is not “equal to zero”. A game with $G + G = 0$ is not zero unless it is zero: 29 of the 30 are confused with zero, which means whoever moves in them wins, which is as far from “nothing there” as a position can be. What $G + G = 0$ says is that two copies cancel, and one copy is a live position with a winner.

The distinction matters in play. A board carrying two copies of $\pm 1$ can be ignored entirely — the second player mirrors between the copies and the pair contributes nothing. A board carrying one copy is a fight over two points that whoever moves first will win.

Where the ladder goes next #

The subgroup found here is the two-torsion of the group of short games, and its existence is the sharpest available statement that this group is not the integers with extra decoration. Two directions lead on: what the 30 look like under temperature — several are switches, so they are hot, and a hot game that is its own negative has a mean value of exactly zero — and whether anything of the same kind survives when the sum is one of the other ways of adding.