Equal in this company

Equal in every company states the definition this site’s arithmetic rests on. Two positions are equal when

$$o(G + X) \;=\; o(H + X) \quad \text{for every game } X$$

and the quantifier is not decoration. It is what makes a value a value: a position may be replaced by an equal one anywhere, in any sum, without checking what else is on the board.

The quantifier can be made smaller. Fix a set $\mathcal{U}$ of games — call it a universe — and ask only that the outcomes agree for $X$ in $\mathcal{U}$. That is still an equivalence, it is coarser than equality, and the question worth asking is how much coarser.

This is not an exotic construction #

It is what several familiar objects already are, and naming the construction is mostly a way of seeing that they are the same object.

A misère quotient is a restricted equality: two positions of a game are identified when no position of that game can tell them apart, and the quotient is what that produces when the universe is a single game’s own positions rather than everything.

A Go player’s endgame vocabulary is a restricted equality. Two corner shapes are “the same” when they behave alike in the endgames that actually occur, which is a much smaller company than all games.

And the outcome class itself is the extreme case: take $\mathcal{U} = \{0\}$ and two positions are equivalent exactly when they have the same outcome. That is the coarsest useful equality there is, and it is where the ladder starts.

The ladder #

Five universes, against the twenty-two values born by day two.

Nothing at all, meaning $\mathcal{U} = \{0\}$: four classes. They are the four outcome classes, and one of them holds nine of the twenty-two.

Nine numbers, every half from $-2$ to $2$: seventeen classes. Adding numbers to a position moves its stops and can change its outcome, so numbers separate a good deal — but three classes still hold more than one value, and the largest holds four.

The seven all-small values born by day two: sixteen classes. Fewer than the numbers manage, from a company of seven rather than nine.

The four games born by day one — $0$, $1$, $-1$ and $\ast$: twenty-two. Everything separated.

All twenty-two values: twenty-two, as it must be, since a universe containing everything the pool contains can always use a position’s own negative.

What the numbers cannot see #

The company of nine numbers merges $\ast$, $\uparrow \ast$, $\downarrow \ast$ and $\ast 2$ into one class.

That is not a failure of the particular nine. Every one of those four values is an infinitesimal — smaller in absolute size than every positive number — so adding a number moves the stops and leaves the infinitesimal part untouched, and the outcome of the sum is decided by the number alone whenever the number is not zero. At exactly zero all four are first-player wins. So the nine numbers see one object where there are four, and a company of nine hundred numbers would see the same one.

The all-small company has the mirror problem, and a section below draws it: it separates the infinitesimals perfectly and merges the numbers, because adding something infinitesimal to a position whose stops are clear of zero cannot change the outcome.

Each company is blind exactly where its members are small.

The four classes at the bottom of the ladder #

The coarsest company is worth a moment, because it is the one every reader already knows and does not think of as a universe.

With $\mathcal{U} = \{0\}$, two positions are equivalent when they have the same outcome class, and the twenty-two values fall into four groups: six wins for Left, six for Right, one second-player win, and nine first-player wins. The nine are $\ast$, $\{0 \mid -1\}$, $\downarrow \ast$, $\{1 \mid 0\}$, $\{1 \mid -1\}$, $\{1 \mid 0, \ast\}$, $\uparrow \ast$, $\{0, \ast \mid -1\}$ and $\ast 2$ — every position in which whoever moves first wins.

That class holds nine values whose behaviour on a board could hardly be more different: two of them are switches worth a full point to take, four are infinitesimals, and one is a fight about nothing. Outcomes do not add is the reason the class is useless as an arithmetic, and the ladder above is a series of steps away from it.

Drawn as classes rather than as a count, the coarsest company shows what it is throwing away. Three of its four classes hold more than one value, and the merges are not near misses: the largest of them puts a whole point of switch on the same line as a star.

The reader who wants the standard these classes are being measured against should hold on to the full quantifier: two positions that are equal in every company may be swapped inside any larger position with nothing about the winner changing. Every company below buys some of that and none of them buys all of it.

A company that is not made of numbers #

The all-small company is the one that says something a reader would not guess.

Seven games — the all-small values born by day two, which are $0$, $\ast$, $\uparrow$, $\downarrow$, $\uparrow \ast$, $\downarrow \ast$ and $\ast 2$ — separate sixteen of the twenty-two. That is fewer than the numbers manage, and it is worth asking what each is good at rather than which wins.

The numbers separate the hot positions from each other, because adding a number moves the stops and the outcome follows. They cannot touch the infinitesimals.

The all-small games separate the infinitesimals from each other, because adding an up to a down gives zero and adding an up to a star does not. They cannot touch the numbers, and the blindness is symmetric: the two classes they merge are a quartet of negatives and a quartet of positives, four values apiece.

Those eight values are exactly the ones the numbers are best at, and the four the numbers merge are exactly the ones this company is best at. Neither company is a weakened version of the other. They are blind in complementary directions, and putting them together is what the four-game company does with a quarter of the members.

Four games, and why it is four #

The company $\{0, 1, -1, \ast\}$ separates all twenty-two, and no smaller company does.

Every single game manages four classes, which is the outcome classes again — unsurprising, since adding one fixed thing is a relabelling of the outcome map. Pairs reach eight or nine. Triples reach thirteen or fifteen. The four reach twenty-two.

The two triples that reach fifteen are the ones containing $\ast$; the two that reach thirteen are the ones containing $0$, $1$ and $-1$ — three numbers, and no better than three numbers ever are. So the necessary ingredient is visible in the table: the company has to contain a star, and a company of numbers, however large, cannot separate an infinitesimal from zero.

The pattern is that a day needs the day before it #

Run the same sweep against the 1,474 values born by day three and the numbers change in an informative way.

The four day-one games manage 22 classes out of 1,474 — they can see exactly as much of day three as there is of day two, which is what a company of that size can distinguish and no more. Nine numbers manage 47. The seven all-small values manage 69.

All twenty-two day-two values manage 1,474: every value of day three separated, by a company of twenty-two.

Two of those numbers are worth pausing over. The all-small company overtakes the numbers here, having lost to them on day two — a company’s rank is a fact about the pool and not about the company. And the four day-one games stop dead at 22 for a reason that has nothing to do with games: four witnesses give a position four outcomes, the outcomes have four values apiece, and no company of four can name more things than it has signatures.

So the company needed to separate a day is the day before it. That is a clean statement and it is the practical form of the whole idea: the witnesses that distinguish complicated positions do not themselves have to be complicated, they have to be one step simpler.

Why “it depends on the company” is the site’s most repeated finding #

Sente is a fact about the rest of the board. Independence is a claim about what else is present. The size of a move is a comparison with what else is available. Even the winner, in a sum, is a fact about the whole.

Equality looked like the exception. It is defined by a quantifier over everything, which is as context-free a definition as a subject can write, and it is the one relation on this site that appeared to be a property of a position on its own.

What the ladder shows is that the appearance comes from the quantifier and not from the relation. Equality is context-dependent like everything else here; the definition simply takes the largest possible context, and the price of doing so is that the relation is fine — 1,474 classes on day three where a working theory would want a few dozen.

So the choice of universe is a real choice, and it is being made whenever anybody says two positions are the same. The full quantifier is one setting of the dial, the outcome class is the other extreme, and the useful theories live in between.

A worked separation #

$\{0 \mid -1\}$ and $\{0, \ast \mid -1\}$ are two of the twenty-two, and the second is the first with a star added to Left’s option list. Every company of numbers merges them.

The witness that separates them is $\ast$. Add a star to each and the outcomes differ: $\{0 \mid -1\} + \ast$ is a win for Right whoever moves, and $\{0, \ast \mid -1\} + \ast$ is a win for whoever moves first — because Left’s extra option is a star, and a star answers a star. One position of the smallest possible size settles it.

Nothing about the pair suggests a star. They differ by a star in their options, which is a fact about the form, and the reader’s instinct is to look for a witness of similar size to the difference — which happens here to be right and is not a rule. What is a rule, and what the day-three sweep shows, is that the witness never has to be more complicated than the day below the positions being separated.

What a coarser equality buys #

A restricted equality is not a weakened one. It is a different and usually more useful object, for a reason worth stating plainly: the classes are bigger, so there are fewer of them, so a table of them fits in a head or a program.

The day-three values number 1,474. Under the company of nine numbers they collapse to 47, and 47 is a number a person can hold. If the positions a player will actually meet are the ones the company describes, then 47 classes is a complete theory of the situation and 1,474 is a distraction.

That is exactly the bargain a misère quotient strikes. The full misère theory of an impartial game is hopeless; the quotient — equality restricted to the positions of that game — is often a finite monoid with a dozen elements, and the reason it is finite is that the company is small.

What a restricted equality is not #

A coarser equality is easy to mistake for an approximation, and the two behave completely differently, so the distinction is worth drawing before the classes above are used for anything.

An approximation says these two positions are nearly the same and comes with an error. A restricted equality says these two positions are exactly the same, inside this company, and comes with no error at all — it comes with a boundary. Inside the company the two are interchangeable in every sum the company allows, with the full force the unrestricted relation has; outside it, they may be as different as any two games, and no amount of care about how they are used will help.

That difference decides how a solver may treat them. An approximation degrades: substitute it and the answer is a little wrong, and a chain of substitutions is more wrong. A restricted equality does not degrade at all — substitute it inside the company and the answer is exact, and substitute it once outside and the answer can be anything. There is no partial credit and there is no accumulation, which makes the licence far more valuable and far more fragile than an approximation of the same coarseness.

It also explains why closure is the property the next rung is about. A licence to substitute is only usable if the company is still the company after the substitution, and after the addition, and after taking an option — otherwise a legal rewrite carries the position out of the class that licensed it, and every rewrite after that is unlicensed while looking identical.

So the right reading of a coarser equality is not a cheaper answer but the same answer to a smaller question. What has been given up is the range of the claim, and what has been kept is its exactness — which is the opposite trade from every approximation elsewhere on this site.

What it costs #

The substitution property is what goes, and it goes quietly.

If $G$ and $H$ are equal in the full sense, then $G + K$ and $H + K$ are equal for every $K$ — the relation is a congruence, and that is what licenses replacing a component of a sum. If $G$ and $H$ are merely equivalent in a universe $\mathcal{U}$, the same substitution needs $\mathcal{U}$ to be closed under adding the things being substituted into, and none of the small companies above is.

Concretely: $\ast$ and $\ast 2$ are equivalent in the company of numbers. They are not interchangeable inside a sum that contains a star, and a company of numbers contains no star to notice. So the relation says these behave alike against this company and does not say these may be swapped, and the difference is the whole of what the full quantifier was buying.

That is the reason the substitution theorem is stated with the quantifier it has, and it is why a universe used for real work — a misère quotient, a class of endgame shapes — is chosen to be closed under the sums that will actually be formed.

The check that the machinery is measuring something #

Two degenerate universes are run deliberately.

With the empty company the relation compares nothing, so every position is equivalent to every other and the count of classes must be one. With the full company — the pool against itself — every distinct value must be separated, so the count must be twenty-two.

Both come out right. A sweep that returned anything else would be reporting a defect in the outcome function or in the enumeration rather than a fact about universes, and the two ends are where such a defect shows up first. It is the same discipline as feeding a reduction a formula it has to refuse: a measurement with no failing case is not a measurement.

What this cannot say #

Every universe above is a set of values, and every pool above is a day of the construction. Real universes are sets of positions of a game, and the two need not resemble each other: a game whose positions happen to realise only a few of the values will have a coarse induced equality for reasons that have nothing to do with the shape of the company.

Nothing here is a statement about which universes are closed under addition, which is the property that makes a restricted equality usable rather than merely definable. Deciding closure needs the sums to be formed and checked, and the companies above were chosen to be small rather than closed.

And nothing here touches the misère convention, where the relation has to be rebuilt from outcomes directly because subtraction is not available. That is the setting in which restricted equality was invented and it is the setting in which it is hardest to compute.

Where the ladder goes next #

universes opens here, and the rungs above it are all things this machinery could reach.

Closure. Which of the small companies is closed under addition, and what the smallest closed company containing a star is. That is the version of the question that licenses substitution, and it is a search rather than an argument.

The dead-ending universe. There is a class of games — those in which a player who runs out of moves stays out of moves — that behaves far better under restricted equality than games in general, and it is the setting several recent misère results live in. Whether the pool here contains any of it, and what its induced equality looks like, is a measurement.

And the trade. A coarser equality has fewer classes and less substitution. Plotting one against the other over a family of companies would say what the exchange rate is, and would turn choose a universe from a stipulation into a decision with a number attached.