A mex with no impartial game in it

What identifies two subsets reduced the mirror construction $\{S \mid -S\}$ to the antichain of maximal elements of $S$, described the zero fibre exactly — nought exactly when no element of $S$ is at least nought — and closed on the one class left over:

The rung above is the fourteen. Star’s fibre is the only class left undescribed and it is small enough to read one at a time … The question is whether they share a property that the other 82 lack, and the shape to look for is the same as the zero rule’s: a condition on the elements against a fixed reference.

It is the same shape, the reference is star, and the two rules turn out to be one rule with a name.

Star’s fourteen #

The description is two clauses:

$\{S \mid -S\}$ is $\ast$ exactly when some element of $S$ is at least nought and none is at least $\ast$.

Right on all 1,793 subsets, which is the standard the zero rule was held to, and it picks out exactly the fourteen antichains and no others.

The two clauses are not decoration, and the first is free. Some element at least nought is the negation of the zero rule, so it says the position is not nought — a first-player win rather than a second-player one. That much follows from what identifies two subsets without any new work, and it is why the second clause is where the content is. None at least star is the new condition, and it says the position is not anything above star either.

Which makes it a mex #

Write $\ast 0$ for nought. Then the two rules say:

• no element is at least $\ast 0$ → the value is $\ast 0$;
• some element is at least $\ast 0$, none at least $\ast 1$ → the value is $\ast 1$.

Which is the beginning of a sequence, and the sequence continues. Let $m$ be the least $k$ such that no element of $S$ is at least $\ast k$. Then

$$\{S \mid -S\} = \ast m.$$

Three antichains give $\ast 2$ and one gives $\ast 3$, and the rule gets both. Over the whole census it fires on 66 of the 96 antichains and is right on every one, and it is right on all 1,793 subsets.

That expression is a mex — the least excluded value — with excluded meaning not reached from below in the partizan order. It is the operation the whole impartial theory is built on, and there is nothing impartial anywhere in this construction.

Four antichains is a thin base for the two steps past star, and it is worth saying so before the rule is enjoyed: the zero step rests on 48 antichains and 1,793 subsets, the star step on 14, and the two above them on three and one.

What it does not fire on #

Thirty antichains hold an element at least as large as every nimber in the reference, so no least $k$ exists and the rule proposes nothing.

Every one of those thirty has a value that is not a nimber. So the rule’s silence and the map’s leaving the nimbers are the same event: the sixty-six it speaks about are exactly the sixty-six whose value is a nimber.

That is an unusually clean shape for a rule on this site. There is no residue on either side — the rule is right whenever it speaks, and it speaks whenever there is a nimber to name — and the boundary between the two is a property of the set rather than a threshold fitted to the data.

The reason is visible in the thirty. An element at least as large as every nimber is an element at least as large as a positive number, so it is a number or something with a number inside it; a mirror built on one is a switch rather than a nimber, because Left can move to something strictly positive and Right to its negative. The nimbers are exactly the self-negative values with nothing positive in them, and the rule fires exactly when the set has nothing positive in it.

The mirror map, assembled #

Eight rungs in, the anchor has an account of the mirror construction that is worth putting in one place, because it was built in three pieces and no page has held all three.

A subset reduces to its antichain. An option of $\{S \mid -S\}$ is dominated exactly when another element of $S$ is at least as good, and the mirror makes the same elements survive on both sides — so 1,793 subsets of day two give 96 antichains. That is a theorem and what identifies two subsets proves it.

Sixty-six of the antichains give nimbers, and the mex names which. That is this page.

The other thirty give 28 values between them, very nearly one-to-one. So the map’s whole non-injectivity is domination plus the nimber collapse, and once past the nimbers it stops collapsing at all.

Read together that says something about where a mirror’s information goes. A set of $n$ elements is compressed to an antichain — which loses everything about the non-maximal elements — and the antichain is then compressed again, but only if it contains nothing positive. A set with a number in it keeps almost all of what distinguishes it; a set without one is thrown into a nimber and loses the rest.

The values that are their own negatives is the census this whole anchor exists to explain, and the account above is now most of the explanation: the self-negative values are the nimbers, plus a large family of switch-like things the mirror produces almost injectively.

Why the nimbers, and not something else #

A rule of the form the least $k$ such that no element is at least $X_k$ has a free choice of the sequence $X_0, X_1, \dots$, and a rule that fits with any sequence is a rule about the shape of the census rather than about the nimbers. So the same rule is run with two others.

The numbers — nought, one, two — fire on 95 antichains and are right on 48. The up-multiples — nought, up, up plus star — fire on 81 and are right on 48.

Both get exactly 48, and the 48 are the zero fibre, which every sequence beginning at nought describes correctly. Past the first step both collapse; only the nimbers continue.

The numbers firing on 95 of the 96 is worth a second look, because it shows what a bad reference sequence looks like from the inside. Almost every antichain fails to reach one, so almost every antichain gets an answer — and the answer is nought or one, which is right on the zero fibre and wrong on the fifty. A reference sequence that is too coarse produces a confident rule with a large residue, which is precisely the shape what can be struck out warns about on this anchor: a rule that fires everywhere has described its own domain rather than the map.

That is the control this finding needed, and it says the reference sequence is doing real work. The zero rule was compatible with any reference; the star rule is not.

Why a mex turns up here #

There is nothing impartial in the construction. $S$ is a set of partizan day-two values, the order on them is the partizan one — which is a partial order with genuinely incomparable pairs — and $\{S \mid -S\}$ is a partizan game written with two different option sets.

What makes the mex appear is self-negation. The construction gives Left and Right mirror options, so the position is its own negative, and a self-negative game is a second-player win exactly when neither player has a good first move. That is the zero case. If Left has a move to something at least nought but neither player has a move to something at least $\ast$, the position is a first-player win with nothing above star in it, which is what $\ast$ is. The thirty that cancel themselves is where the self-negative values were first counted on this site, and every nimber in that census is one of these.

Running the same argument up the nimbers is exactly the argument that defines the Grundy value of an impartial position, and the only difference is that reached means at least, in the partizan order rather than equal to. Sprague–Grundy is the theorem the operation belongs to, and it is a theorem about impartial games; what this page shows is that the operation survives in a place the theorem does not.

The reason it survives is that mirror options make the position behave impartially without being impartial. Left and Right have the same set of moves up to sign, so which player is to move never matters, and a game where it never matters is a game whose theory is the impartial one. Every game has a negative is where the mirror is constructed; what it constructs, on the nimber part of its range, is an impartial game wearing partizan options.

What the rule is worth #

A description of a fibre is a statement about how much a construction forgets, and it is worth pricing this one in those terms.

The mirror map takes a subset of a day and returns a value. Before this page, the map’s fibres were known for one value; now they are known for every nimber, which is 66 of 96 antichains and 1,565 of 1,793 subsets. That is not a small share of the map, and it is the share on which the construction is most lossy — forty-eight subsets into nought, fourteen into star.

The practical use is the one at least five hundred and seventy-one was reaching for. That page used the construction to put a floor under the count of self-negative values born on a day, and a floor is what a construction gives when it produces values and cannot say which are equal. With the nimber fibres described, the count on that part of the range stops being a floor and becomes a count — and what remains a floor is the other thirty antichains, where the map is nearly injective and the collapse is small.

So the rule converts a lower bound into an exact figure on the half of the range where the bound was weakest. That is the ordinary way a fibre description earns its place, and it is why the rung below asked for one.

Why a mex turns up here at all #

An operation from the impartial theory appearing in a construction with no impartial game in it is the sort of coincidence worth explaining rather than admiring, and there is an explanation.

The mex is not really about impartial games. It is the answer to a question about a set and an order: given a set of objects, what is the smallest object of some standard family that none of them reaches? Sprague–Grundy uses it because a position must not be equivalent to any of its options, so the value must avoid a set of values, and the natural choice is the smallest available.

The mirror map asks the same question in different clothing. $\\{S \\mid -S\\}$ is a game whose Left options are $S$ and whose Right options are their negatives, so it is symmetric under exchanging the players — and the values symmetric under that exchange are exactly the self-negative ones, among which the nimbers are the standard family, ordered by index. What the mirror has to be is the smallest nimber none of $S$’s elements reaches, for the same reason a Grundy value is: it must not be equal to anything the set already supplies.

So the two occurrences are one occurrence of a general fact. Wherever a construction has to produce an object that avoids a set, and there is a standard family to choose from, the answer is a mex — and the impartial theory’s claim on the operation is historical rather than mathematical.

That reading also predicts where else to look. Any operation on this site defined by the simplest thing not already reached is a mex in disguise, and the simplicity rule is the obvious candidate: the simplest number strictly between two numbers is a minimum excluded value over a different family and a different order.

What this does not say #

Day two only. Every subset here is drawn from the 22 values born by day two, which is the rung below’s population and the largest the construction can be enumerated over. The nimbers reached are $\ast 0$ to $\ast 3$, so the rule is checked at four steps of a sequence that is infinite.

The order is the partizan order, and it is partial. No element is at least $\ast k$ is not every element is less than $\ast k$: an element incomparable with $\ast k$ satisfies the first and not the second. That distinction is the whole reason the rule is a mex over a partial order rather than a count, and it is where an induction would have to be careful.

Nothing here is proved. The two rules are stated as descriptions checked on 1,793 subsets, and the argument in the section above is a reading of why they might hold rather than an induction. The zero rule has a one-line proof, which the rung below gives; the star rule does not have one here.

And the thirty are described only negatively. Not a nimber is what the rule says about them, and the rung below’s finding stands unchanged: outside the two big fibres the map is very nearly one-to-one, and those 34 antichains give 28 values between them. This page has not described any of them.

The convention, named #

Normal play throughout, and every value computed by the recursion and reduced to canonical form.

The mirror construction takes a set $S$ of games and builds $\{S \mid -S\}$: Left’s options are the members of $S$ and Right’s are their negatives. Every such position is its own negative.

An antichain is a set with no two comparable members. An option of $\{S \mid -S\}$ is dominated exactly when another element of $S$ is at least as good, so the form reduces to the antichain of maximal elements — which is the rung below’s first stage and the reason 1,793 subsets give 96 antichains.

$a$ is at least $b$ when $a \ge b$ in the partizan order, which quantifies over every game there is. Two games can be incomparable, and then neither is at least the other.

The nimbers are $\ast 0 = 0$, $\ast 1 = \ast$, $\ast 2$, and so on — the values of single Nim heaps. The mex of a set of nimbers is the least one not in it; the operation here is the least $k$ such that no element of $S$ is at least $\ast k$, which reduces to the ordinary mex when everything in sight is a nimber.

The population is every subset of at most three of the 22 day-two values — 1,793 subsets — which is the rung below’s sweep unchanged.

Where the ladder goes next #

The negation anchor has eight rungs: every game has a negative, the values that are their own negatives, what a self-negative value costs, the thirty that cancel themselves, what can be struck out, at least five hundred and seventy-one, what identifies two subsets, and now the rule that identifies them.

The rung above is the induction. The mex rule is a statement with a proof-shaped argument behind it and 1,793 confirmations, and turning it into a theorem means an induction on $k$: assume the rule at $k - 1$, and show that a set with an element at least $\ast j$ for every $j < k$ and none at least $\ast k$ has mirror value $\ast k$. The step that needs care is the partial order — no element at least $\ast k$ leaves incomparable elements in play, and an incomparable element is exactly the case a total order would not have to handle.

Two neighbours are worth the trip. Sprague–Grundy is where the mex belongs, and reading it beside this page is the clearest statement of what the operation is actually about — not impartiality, but a position where whose turn it is does not matter. And at least five hundred and seventy-one is where the construction became a counting tool, and the rule here is what would turn its floor into a count.