The simplest game above both

Comparing two positions is a search, and the search has three possible answers rather than two: one is at least the other, the other is at least the one, or neither. The third answer is what makes the values a partial order, and a partial order is an unruly object. Nothing in the definition promises that two incomparable things have anything above both of them, and nothing promises that if they do, there is a simplest such thing.

The values born by day two make both promises and keep them.

That picture is worth a minute before anything is claimed about it. It is not a list and not a chain: 52 of the 253 pairs are incomparable, so more than a fifth of the time the comparison comes back with neither answer. And yet the shape has no gaps in it.

Two things a partial order does not owe anyone #

Take two elements $a$ and $b$. An upper bound is anything above both. A least upper bound — a join, written $a \vee b$ — is an upper bound that is below every other upper bound.

Neither has to exist. A partial order can have two elements with no common upper bound at all, and it can have two elements with several minimal upper bounds, none of them least, because the minimal ones are incomparable with each other. That second failure is the common one, and it is exactly the shape an order full of incomparable pairs invites.

An order in which every pair has both a join and a meet is a lattice. It is a strong condition, it is not implied by anything said so far, and it is checkable by exhaustion on a set of 22.

The failure to worry about is the second one, so it is worth looking at a pair with every opportunity to exhibit it. $\ast$ and $\ast 2$ are incomparable — neither is above the other, and both are confused with zero — and six of the 22 values lie above both, which is as much room as any pair on this page gets.

Reading the diagram #

The hero figure repays a slow look, because almost everything the essay claims is visible in it.

It is nine levels deep and 22 wide in total, with at most four values on any level. The bottom is $-2$ and the top is $2$, and every other value sits somewhere between them — so the order has a least and a greatest element, which is already more than a partial order owes.

The lines are covering relations, not all the comparisons. $a$ is joined to $b$ when $a < b$ and nothing lies strictly between; the full order has many more comparable pairs than the 36 lines, and every one of them is a path up the diagram. Reading a comparison off the picture means finding a route, not finding an edge.

The levels are computed, as the length of the longest chain below each value, and the horizontal placement is a single bottom-up pass putting each value at the average position of what it covers. That is worth stating because a hand-arranged diagram of a 36-edge order would be a picture of somebody’s arrangement — the same order drawn twice by two people is two different pictures, and only one of them can be quoted.

Where the numbers sit is the surprise a reader is most likely to notice unaided: $\tfrac12$ is above $\uparrow$, $1$ is above $\{1 \mid 0\}$, and the numbers are threaded through the diagram rather than running up one side of it. The order on values is not the order on numbers with extra elements inserted; it is a different shape that contains the numbers.

Every pair, both ways #

The census builds the 22 values, forms all 253 unordered pairs including the pairs of a value with itself, and for each pair collects every upper bound and every lower bound by direct comparison. Then it asks whether the set of upper bounds has a least member — an element below all the others — and whether the lower bounds have a greatest.

They do, 253 times out of 253, in both directions. There is no pair with two minimal upper bounds and no pair with none. The list of exceptions the census returns is empty, and it is returned as a list precisely so that it can fail to be empty.

Distributivity is the next question and the answer is the same. A lattice is distributive when $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$ for every three of its elements, which rules out the two small non-distributive shapes — the diamond and the pentagon — that a reader can look for in the hero figure by eye. Checked on all $22^3 = 10{,}648$ triples: no failures.

So the order the values sit in is a distributive lattice, and it did not have to be one.

What a lattice is not #

Three things a reader might take from “the day-two values are a lattice” and should not.

Not a total order. 52 of the 253 pairs are incomparable, which is more than a fifth. A lattice can be as far from a chain as this one is; what it promises is that any two elements have a canonical thing above and below, not that they are comparable.

Not a chain of numbers. The join of two values is generally not a number, and the meet generally is not either. $0 \vee \ast 2 = \uparrow$ — an infinitesimal, not a number at all.

And not an operation the sum respects. The lattice operations and addition are two structures on one set. $0 \vee \ast = \tfrac12$, while $0 + \ast = \ast$; there is no rule taking the join of two values to anything about their sum, and a reader who reaches for one will produce nonsense at the first attempt.

What the lattice is is a statement about the order alone: it has no ragged edges, and any two values have a best common bound in both directions.

What the joins actually are #

The interesting joins are the ones between incomparable values, because those are the ones a chain could not have produced. There are 52 of them and their answers are not spread thinly: nine of the 52 join to $1\ast$, seven to $\ast 2$, five to the top value $2$.

The pattern worth staring at is what happens above zero.

$0 \vee \ast 2 = \uparrow$ is a sentence about infinitesimals that arrives from a direction with no infinitesimals in it. Nothing in the question mentions smallness; the question is “what is the simplest thing above both of these”, and the answer is the smallest positive value on the board. The comparison $\uparrow \geq \ast 2$ that makes it work is computed rather than recognised, and it is the sort of relation that is very hard to guess: $\uparrow$ is confused with $\ast$ and above $\ast 2$, which is not a distinction a reader carries around.

Meanwhile $0 \vee \ast = \tfrac12$, and this one is almost a joke. The simplest game above both nothing-at-all and the smallest game confused with nothing-at-all is one half — a number, born on day two, sitting above a pair of games that between them contain no numbers at all.

The reason any of these questions has a choice of answers at all is the fourth relation. Three of the four outcome classes are comparisons with zero — above, below, equal — and the fourth is not: a first-player win is confused with zero, neither greater nor smaller nor the same. That relation is what puts 52 incomparable pairs into a set of 22 values, and every pair marked on this page is one it created.

The join belongs to the day, not to the pair #

Here is the part that stops the lattice being a fact about the two values.

A least upper bound is least among the candidates available, and the candidates are whatever the universe contains. Day two contains 22 values. Day three contains 1,474 — and every one of the 22 is still there, so the same question can be asked again with more to choose from.

Nothing about the pair changed. Both values are still born by day two, both are still incomparable, and the answer to “what is the simplest game above both” is different — because day three supplies something above both and below what day two had to offer.

That is a much more interesting statement than it first sounds. The lattice is a property of each day and not of the values in it. The games born by day $n$ form a distributive lattice for every $n$; the collection of all short games does not, and the joins computed above are the evidence for how that fails — a sequence of ever-simpler upper bounds, one per day, with nothing at the bottom of it.

Why the join moving is the important half #

The day-two lattice is a pleasant fact. The join moving between days is the one that changes how a reader should think about the order, and it is worth pressing.

Ask “what is the simplest game above both $0$ and $\ast$?” and the question sounds like it has an answer. It has three so far — $\tfrac12$ inside day two, $\{0 \mid \{0, \ast \mid -1\}\}$ inside day three, and something else again inside day four — and the sequence has no reason to stop.

Each answer is a genuine least upper bound in its universe. Nothing is wrong with any of them; what is wrong is the question, which left out the universe. A least upper bound is least among candidates, and every day supplies more candidates.

That has a consequence for the whole collection of short games: the order on all short games is not a lattice. If it were, the sequence of day-by-day joins would have to stabilise at the true join, and it does not — each day produces something strictly below the last while staying above the pair. An infinite descending sequence of upper bounds with nothing at the bottom is precisely what “no least upper bound” looks like.

So the essay’s title is a question that needs a qualifier, and the qualifier is the day. That is the honest form of the result, and it is stronger than the tidy version would have been.

The days are lattices and the inclusions are not #

There is a precise way to say what goes wrong between the days, and it is sharper than “the lattice is a property of each day”.

Every day-two value is a day-three value: the days grow, and nothing born is ever unborn, so the 22 sit inside the 1,474 as a subset. The order agrees too — two day-two values compare the same way whichever universe the question is asked in, since a comparison is a difference game and the difference does not know what else exists.

So the inclusion preserves the order and it does not preserve the joins. $0 \vee \ast$ is $\tfrac12$ in the smaller universe and something else in the larger, and both answers are correct in their own. In the vocabulary this is exactly the statement that the day-two lattice is a sub-order of the day-three lattice and not a sublattice of it.

That is worth having because it explains why the property cannot accumulate. A chain of lattices, each sitting inside the next as a sub-order, need not have a lattice as its union — the joins have to agree along the chain for that, and here they demonstrably do not. Each day is a lattice; the limit of the days is the short games; and the limit is not one.

What the order is instead #

Losing the lattice sounds like losing the structure, and it is worth saying exactly what remains, because the remainder is everything the theory uses.

The order is directed, upwards and downwards. Any two short games have some common upper bound and some common lower bound — a value born on day $n$ lies between $-n$ and $n$, so a large enough integer is above any pair and its negative is below. What fails is leastness, not existence, and the day-by-day sequence of joins is a sequence of upper bounds getting steadily better with no best one.

The order respects addition. If $G \geq H$ then $G + X \geq H + X$ for every $X$, which is the property substitution depends on and the only order property any argument on this site actually invokes.

And the group structure is untouched. Addition, negation, cancellation and comparison-by-difference are all statements about the group and the order together, and none of them mentions a join.

So the honest classification is a directed partially ordered abelian group that happens to be a lattice on each finite stage and not in the limit. Nothing this site computes is affected, because nothing this site computes asks for a least upper bound — the joins in this essay are the only ones on the site, and they were computed to find out whether they exist.

Where the argument needs an assumption #

One caution, because the case against the limit being a lattice is made from two days.

The argument is that no upper bound of $0$ and $\ast$ can be least, because any upper bound born by day $n$ is at or above that day’s join, and the next day supplies a strictly smaller one. That is airtight provided the joins really do keep descending strictly, and what is measured here is one step: $\tfrac12$ at day two, something below it at day three.

Two days is one step of a sequence, and this site does not extrapolate from one step elsewhere. The conclusion is stated with more confidence than that here because it is a known result rather than a measurement — the short games are not a lattice — and what the census contributes is the mechanism made visible: not an abstract non-existence proof, but two computed answers to one question and the day between them.

What the solver computed, and how #

Everything above is one enumeration and three sweeps over it.

The 22 values come from building all 256 forms $\{L \mid R\}$ with $L, R \subseteq \{0, 1, -1, \ast\}$, reducing each to canonical form and deduplicating by interning key. Every comparison after that is a difference game solved by the recursion — $a \geq b$ is decided by asking who wins $a - b$, never by inspecting the two positions.

The order sweep computes, for each of the 253 pairs, the full set of upper bounds and lower bounds, then filters each for a member comparable-and-below all the rest. Both filters return exactly one element every time. Covering relations — the lines in the figure — are computed separately: $a$ is covered by $b$ when $a < b$ and no third value lies strictly between, which is $22^3$ comparisons and yields 36 lines.

The distributivity sweep is 10,648 triples, each needing three joins and three meets, all of them memoised on the pair.

The layout is computed too, and deliberately: the level of a value is the length of the longest chain strictly below it, which puts $-2$ at level 0 and $2$ at level 8, and within a level the values are placed at the average position of what they cover, in one bottom-up pass. A hand-arranged diagram of an order with 36 edges would be a picture of somebody’s arrangement rather than of the order.

Where the model stops #

Three limits, and the third is the one that matters.

The picture is of day two. Day three has 1,474 values and 1,086,275 pairs, and while the joins reported above were computed there, the whole order was not swept: the sweep is quadratic in the values and cubic for distributivity, and $1{,}474^3$ is not a build step. The claim proved here by exhaustion is proved for day two; the general theorem — that the games born by any day form a distributive lattice — is in the literature and is not proved here.

A join is not a sum. $0 \vee \ast = \tfrac12$ says nothing about $0 + \ast$, which is $\ast$. The lattice operations and the group operation are different structures on the same set, they interact weakly, and reading a join as any kind of addition will produce nonsense immediately.

And the join is not intrinsic. A reader who takes $0 \vee \ast = \tfrac12$ away from this page has taken away a fact about a 22-element set, not a fact about zero and star. The same two values joined inside day three give a different answer, and inside day four a different one again. Asking for “the simplest game above both” without saying among what is asking an incomplete question — which is the honest reading of a lattice that exists one day at a time.

Where the ladder goes next #

The order is what almost every argument in this subject is built out of: domination is a comparison between siblings, the gift horse principle is a comparison that has to fail, and the simplicity rule is a statement about which value sits between two others. The next rung is the one this essay kept touching and did not take: what the joins and meets do to sums, where the lattice and the group meet, and whether the 52 incomparable pairs stay incomparable when something is added to both.