The closure that picks the nimbers

Two positions are equal in a company when adding any member of that company leaves them with the same outcome. Equal in this company makes that computable, and the company that is closed asks which companies license a substitution — for which a company has to be closed under addition, since rewriting a part of a sum produces a new sum that has to stay inside.

Its answer was that none of the working companies is closed, and that every finite company which is consists of games equal to their own negatives, {0, ±1} among them — which is not a set of nimbers, and was the surprise. It closed by naming the other half of the licence:

The rung above is closure under forming options, which is the other half of the licence and the half this page has not touched. A company closed under addition lets a sum be rewritten; a company also closed under options lets a subposition be rewritten, which is what a recursive computation actually does.

The second closure behaves nothing like the first, and putting them side by side reverses the surprise.

Every working company has it #

The five companies this site computes in — nothing at all, the numbers from −2 to 2 in halves, the all-small values of day two, day one, and day two — have 76 options between them.

All 76 stay inside. Every one of the five is closed under forming options.

That is not an accident and it is worth saying why: a company built as the values born by day $n$ contains every option of every member by construction, since an option of a day-$n$ value is a day-$(n-1)$ value. The numbers in halves have the same property for the same reason — the options of a half are nought and one, and both are in the list.

So the closure the rung below went looking for and could not find anywhere is a property every company here has, and the one it did find is a property none of them has. The two are not merely different; on this collection of companies they are complementary.

That complementarity is worth stating carefully, because it is a fact about how the companies were built rather than a theorem. A day is closed downward and not under addition; a group is closed under addition and not downward. Nothing forbids a company from having both — four do — and the reason none of the five working ones does is that a company built to separate values wants to be wide and a company built to close wants to be narrow, and those pull in opposite directions.

Where they meet #

The interesting question is what happens to a company asked for both, and the seven finite addition-closed companies are where to ask it.

Four of them are groups of nimbers: nothing but nought, nought and star, nought with star and $\ast 2$, and the nimbers to $\ast 4$. All four keep every option — 70 options between them, none leaving.

Three of them contain $\pm 1$: nought with $\pm 1$, star with $\pm 1$, and star, $\ast 2$ and $\pm 1$. All three leak — two options, four and eight respectively.

The two columns agree on every row and in both directions, so on this collection being closed under options and being a group of nimbers are the same condition.

The reason is one line. $\pm 1$ has options $1$ and $-1$. A company containing $1$ and closed under addition contains $2$, and $3$, and every integer, so it is not finite — and a company containing $\pm 1$ and closed under options is not finite either. The finite companies with both closures cannot contain $\pm 1$, and once that is gone the two-torsion has nothing left in it but nimbers.

What one value generates #

The sharpest form of the same finding comes from asking what a single value generates when both closures are demanded at once.

Start with a value, add nought, and repeatedly throw in every sum of two members and every option of every member. Three of the twenty-two day-two values reach a fixed point:

• nought generates $\{0\}$;
• star generates $\{0, \ast\}$;
• $\ast 2$ generates $\{0, \ast, \ast 2, \ast 3\}$.

The other nineteen never stop. That includes $\pm 1$, which is closed under addition on its own and is undone by its options; it also includes $\uparrow$, which is closed under neither — $\uparrow + \uparrow$ is a new value and so is $\uparrow + \uparrow + \uparrow$, so an infinitesimal is no cheaper to close than an integer is.

That last point is worth pausing on. A reader who knew that the finite addition-closed companies are the two-torsion might expect the small infinitesimals to be nearly closed; they are not close to it. Being of order two is the whole of what makes a finite company possible, and $\uparrow$ has infinite order like everything else that is not a nimber or a switch.

What a leak looks like #

The three leaky companies leak in a specific and instructive way, and it is worth following one of them out.

$\{0, \pm 1\}$ is closed under addition: $\pm 1$ added to itself is nought, which is the whole of what being in the two-torsion means. Ask for its options and $\pm 1$ produces $1$ and $-1$.

Add those and the company is no longer closed under addition, because $1 + 1$ is $2$. Add $2$ and the options of $2$ are $1$ and nothing, which is fine, but $2 + 2$ is $4$ — and the chase never ends. A single option of a single member of a two-element company forces an infinite one.

The larger leaky companies leak worse rather than differently. Star and $\pm 1$ loses four options and star, $\ast 2$ and $\pm 1$ loses eight, and in each case the escapees are the same integers and their starred versions. Nothing new goes wrong; the same door is open more times.

That is the mechanism behind the equivalence in the table, and it also explains why there is no middle case. A company either contains a switch or it does not; if it does, its options are numbers and the addition closure explodes; if it does not, the two-torsion has nothing in it but nimbers and both closures hold.

The surprise, reversed #

The rung below’s finding was that the closed companies are the two-torsion rather than the nimbers, and that this is not what a reader expects. This page’s is that the expectation was right about a different question.

Ask only for the licence to rewrite a sum, and $\{0, \pm 1\}$ qualifies: it is a group of order two and adding its members never leaves it. Ask also for the licence to rewrite a subposition, and it does not, because rewriting a subposition means looking inside $\pm 1$ and what is inside it is the integers.

So the two-torsion answer and the nimber answer are answers to two different questions, and which one a reader expects depends on which licence they had in mind. A reader thinking of substitution in a sum gets the two-torsion. A reader thinking of substitution inside a recursive computation — which is what an evaluator actually does — gets the nimbers.

This site’s evaluator does the second. Every value on this site is computed by a recursion that rewrites options, so the companies that would license its shortcuts are the four nimber groups and nothing else.

Why this is the licence that matters #

There is a practical reason to care which of the two closures a company has, and it is about what a computation is allowed to do.

Closure under addition licenses the step this sum contains $G$; $G$ equals $H$ in this company; therefore the sum equals the sum with $H$ in it. That is the step equal in every company makes legitimate without any restriction, and the restricted version is what the whole universes anchor is about.

Closure under options licenses the step this position has an option $G$; $G$ equals $H$; therefore the position with $H$ as that option is the same position. That is induction over the position tree, and it is what every recursive computation on this site quietly assumes.

The second is the one a program needs and the first is the one a proof needs, which is why the literature states the first and an implementation relies on the second. Neither implies the other, and this census is the measurement of how far apart they are: five companies with the second and not the first, three with the first and not the second, four with both.

The nimber groups, as the answer #

It is worth naming what the four surviving companies actually are, because they are not an odd corner of the subject.

$\{0\}$, $\{0, \ast\}$, $\{0, \ast, \ast 2, \ast 3\}$ and the nimbers to $\ast 7$: sizes 1, 2, 4 and 8, and the next is the nimbers to $\ast 15$. They are the finite subgroups of the nimbers under nim-addition, which is a well-known object — the nim-sum of two numbers below a power of two is below that power of two, so the initial segments of that length are exactly the subgroups.

So the answer to the rung below’s question is a family a reader already knows, arrived at from a direction that has nothing to do with impartial play. The question was about which companies license a substitution; the answer is the impartial values, in the initial segments, and nothing else.

That is the sort of coincidence this site keeps finding and it is not a coincidence. Where the impartial theory stops is the general account: one number per position is a very strong restriction, and the things that survive strong restrictions tend to be the things the restriction was built around.

What this says about the misère quotient #

There is a place in this subject where restricted equality is not a curiosity but the whole theory, and it is worth reading this page against it.

Misère quotients are built by taking one game’s own positions as the company and quotienting by equality in it. That construction needs both closures for the same reasons this page has been separating: the positions of a game are closed under options by construction — an option of a position is a position — and the quotient is a monoid because sums of positions are positions.

So the misère quotient is the one place both closures come free, and it comes free because the company is a game rather than a set of values somebody chose. That is a better argument for the construction than the usual one, which is that it happens to work.

And it sharpens what nobody comes back is about. A dead-ending universe is a restriction chosen to make comparison behave, and the property it needs is the second closure — a subposition of a dead-ending position is dead-ending — rather than the first.

What each closure licenses, and why the second is the strong one #

The two closures are easy to run together and they license quite different things. It is worth setting out what each buys a solver, because that is what makes one of them rare.

Closure under addition says: if two games are in the company, so is their sum. That licenses rewriting a component — replacing one part of a board by an equivalent one — because the rest of the board is a sum of company members and the replacement is being compared against it.

Closure under forming options says: if a game is in the company, so is every position reachable from it. That licenses rewriting a subposition — replacing something deep inside a component — which is what a recursive evaluation does at every node, thousands of times per board.

The second is the one that matters to a recursion and the one almost nothing has. The reason is structural: options are where a game’s complexity lives, so demanding the company be closed under them demands it contain everything a member can turn into, at every depth. A company built from a few generators under addition stays small; the same company under options usually does not stay finite at all.

So the finding that the two coincide exactly on the nimber groups is a statement about how tight the second demand is. Four of seven addition-closed companies survive it, and among all twenty-two day-two values, nineteen generate nothing finite once both are required.

Which is why the impartial theory has the licence and the partizan theory does not. A Nim heap’s options are Nim heaps; a switch’s options are anything at all.

What the census does not say #

Four limits.

A cap of forty. A company that has not closed after forty members is reported infinite. Every one of the nineteen exceeds it quickly — $\uparrow$ produces a new value every time it is added to itself — so nothing here is near the boundary, but infinite means past the cap and the cap is stated.

Day two, for the generators. Twenty-two values is a small pool, and it is the pool the rung below used so that the two pages measure the same thing. A day-three generator that closed under both would be a fifth nimber group or a counterexample, and neither is checked.

The equivalence is on seven companies. Closed under options exactly when a group of nimbers is stated about the seven finite addition-closed companies this site has found, four of which are nimber groups. Seven rows is enough to be sure the two columns are not coincidentally aligned and is not a theorem, and the one-line argument above is a sketch of one.

The generators start from one value. The three that close are the three whose closure happens to be small; a company generated by two values could close where neither does alone, and no pair is tried. The search over pairs is 231 closures and is not run because the single-value result already answers the rung below’s question.

And the working companies were built to be option-closed without anybody intending it. They are days and intervals of numbers, and both shapes are closed under options for structural reasons — so the finding that all five have the property is a fact about how the companies were chosen as much as about companies.

The convention, named #

Normal play. A company is a finite set of values, and two games are equal in it when adding any member leaves the outcome unchanged.

Closed under addition means the sum of any two members is a member. Closed under forming options means every option of the canonical form of every member is a member — options of the canonical form rather than of some form, since a value’s options are only well defined once the form is.

A group of nimbers here means $\{0, \ast, \ldots, \ast(2^k - 1)\}$ for some $k$, which is closed under the nim-sum and is the only kind of finite nimber set that is.

Nought is a member of every company by construction, since a company that does not contain it is not closed under adding a game to its own negative and is not a company any theorem is about.

Where the ladder goes next #

The universes anchor has three rungs to here, and the three above price the licence this page characterises rather than characterising it further.

A product against a sum measures what a solver gains from being allowed to rewrite: on Cram boards, four to twenty-five times on two components and twenty-four to a hundred and sixty-one on three — and it is available to impartial games precisely because their class representative is a heap rather than a form, which is the property this page’s closure result identifies.

Half a licence is nearly all of it then splits the licence into its two halves and finds the cheap one doing nearly everything. Rewriting components takes a million and a half states to three thousand six hundred; rewriting subpositions takes those to eight hundred and eighty-four. So the option-closure this page shows to be the nimbers’ exclusive property is the half contributing least.

One half multiplies the other adds gives both halves closed forms and explains the split: the component licence saves $s^{k-1}/k$ and the subposition licence saves $k \cdot s$. One is exponential in the number of components and the other is linear, so the gap widens with every extra piece on the board — which is exactly the situation a restricted universe is invoked for.

Read together with this page they say something slightly awkward about the characterisation. The strong closure — the one that picks out the nimbers exactly, in both directions, with no exception — is the one worth least at the board.