Two things to hold at once, or three

The rule decides who has to remember sweeps every condition on which of three positions a never-ending play keeps returning to, and asks of each whether a winner can play from a table with one move against each position. Thirty-two of the 128 have a board where the table is not enough. Ninety-six produced no such board.

It ends on the obvious complaint. Needs memory is a yes and a no, and a condition that needs memory needs some amount of it — one bit repaired the hub, and nothing there says whether one bit repairs anything else. Turning that column into a scale, it suggests, would mean taking the product of an arena with a memory of each size and asking whether the winner comes back.

There is a shorter route, and the reason to prefer it is not that it is shorter. The amount can be read off the condition with no board consulted at all, and the construction that reads it also settles the ninety-six — which a sweep over boards cannot, because a sweep over boards can only ever report what its boards happen to hold.

A tree with no board in it #

The construction is a tree, and building it is a matter of alternating sides.

The root is the whole set of positions. A node is accepted if the condition would let Left win a play recurring at exactly that set, and rejected otherwise. The children of a node are the largest proper subsets judged the other way — the largest rejected subsets of an accepted node, the largest accepted subsets of a rejected one. Every child is a proper subset, so the recursion runs down and stops.

The number comes back up, and the two rules are not symmetric. A leaf is one state. At an accepted node the children’s numbers are added. At a rejected node the largest is taken.

The asymmetry is the whole content, and it is readable. At an accepted node, each child is a set Left is doing well to be circulating in, and the children are the ways Right can push the play out of it: Left has to be ready to pursue each of them and ready to come back to the others, so the states accumulate. At a rejected node the play is somewhere Left does not want to be, the children are the escapes, and Right chooses which one — Left need only be ready for the worst, so the numbers do not add.

Run on every position recurs, that gives three. The root is the only accepted set; its children are the three largest rejected sets, each a pair of positions; each of those is a leaf, because no accepted set is a proper subset of a pair. Three leaves, added at the root, and the three states are the record of which positions are still owed — which is what one bit of memory found by hand with two positions and a hub.

Sixty-one, fifty-eight and nine #

There are 128 conditions and 128 trees, and building all of them takes no measurable time.

Sixty-one conditions cost one state. Fifty-eight cost two. Nine cost three. Three is the most any condition on three positions costs, which is not an accident of the list: the tree’s number is bounded by the number of leaves, the leaves are sets of positions, and three positions do not leave room for more.

Two things about that table are worth separating, because they are different kinds of claim.

The first is that it is a scale and not a dichotomy. The rule decides who has to remember reports a column of yes and no, and under it there is a genuine ordering: a condition costing two states is asking a winner to hold two objectives and alternate between them, and one costing three is asking for three. What separates the nine from the fifty-eight is not that they are harder to satisfy but that they hold more things at once.

The second is that the number is not about any board. The same tree prices the condition whatever the board is, however many positions it has, however they are joined. That is the claim the arena sweep could not make about its own column, and it is the claim that settles its ninety-six.

The same tree read from the other side gives the number for Right, by swapping which nodes add and which take the largest. Right’s scale is the same three numbers in the same proportions — sixty-one, fifty-eight and nine — and the correspondence is exact rather than statistical: what the tree says Right needs of a condition is what it says Left needs of the complementary one, checked on all 128 rather than assumed from the symmetry of the construction.

The property that was nearly right #

The sweep tests two properties of a condition and finds one that tracks its column: whether a number can be put on each position so that Left wins exactly when the largest recurring number is even. Twenty-six conditions can be written that way, and none of them produced a board where a table failed.

That is sound and it is not the line. Twenty-six is sufficient and sixty-one is the truth.

The line is a closure property, and it is on the wrong half of the condition to be the one anybody reaches for. A condition costs one state exactly when the sets it rejects are closed under union — if two circulations both lose for Left, so does the circulation on their union. Computed as a closure test on a family of sets, with nothing about trees in it, that property holds of exactly sixty-one conditions, and they are exactly the sixty-one the trees price at one state. Two computations over different objects, agreeing on all 128 with nothing left over in either direction.

It also explains itself off the tree. A one-state winner is one whose tree never adds, which means no accepted node has two children, which means no accepted set has two largest rejected subsets — and two largest rejected subsets of a set are two rejected sets whose union is not rejected. The closure test and the tree are the same statement read at different distances.

Why closure of the accepted sets fails is then visible too, and the rule decides who has to remember says it in prose without the tree: every position recurs accepts one set, is closed under union for want of anything to violate it, and is the most expensive condition there is. Closure on the accepted side constrains what Left is allowed to want. Closure on the rejected side constrains what Right can offer, and a winner’s memory is for keeping track of an opponent’s offers.

What the nine have in common #

The top of the scale is a short list and reads as one idea.

Eight of the nine are every position recurs, alone or together with some of the three conditions the play settles on this one position. Adding those to the family changes what Left may also win with and changes nothing about the expensive part, because a set of one position is a leaf wherever it appears and contributes one state.

The ninth is at least two positions recur, which is a different sentence and gets the same number by the same route: it rejects exactly the three single positions, so its root is accepted with three leaves under it, and three leaves added is three.

So the nine are the conditions that ask a winner to keep three things going at once, and they are the only ones on three positions that can. The fifty-eight in the middle ask for two. Fifty-eight is a large share of 128 and the reason is arithmetic rather than deep: a condition that rejects two sets whose union it accepts has an accepted node with two children, and most families of sets contain such a pair somewhere.

The seventy, divided #

The sweep leaves a definite piece of unfinished business. Ninety-six conditions produced no board; twenty-six of them are settled for every board there is; and nothing was known about the other seventy.

The trees divide them, and the division is even. Sixty-one conditions need nothing on any board. Thirty-two need memory and a three-position board shows it, which is what the sweep found. Thirty-five need memory and no three-position board shows it.

The seventy split thirty-five and thirty-five, and the second thirty-five is the point. Those are conditions where a table of moves is provably not enough, on a board nobody has drawn, and the evidence is a tree with seven nodes in it. No amount of enlarging the arena sample would have found them, because the arenas were the wrong size rather than too few — which the sweep itself suspects, in the sentence about raising the sample from 257 to 1,033 and finding the same thirty-two.

It also retires the plan left for finding them. Four positions, it says, would test the seventy at the price of 32,768 conditions and an arena count in the tens of millions. It would; and the tree tests them at the price of nothing, because the question was never about arenas.

A price with nowhere to be paid #

Two positions are the case where the tree and the boards can both be exhausted, so it is where the arithmetic can be checked rather than believed.

Eight conditions, 81 boards, and every strategy of up to four states searched at every start Left wins. Nothing anywhere needs more states than its tree says. That is the check that matters, because a tree that under-priced a condition would be a tree that says a winner can get by on less than it can.

And exactly one condition is priced above what two positions attain: both positions recur, which the tree costs at two states and which is won with one on all 81 boards. That is the sentence the sweep writes as an observation and cannot explain — a condition can be unwritable and still need no memory, if the board is too small to make it bite. The tree says which conditions are in that position before any board is looked at, and both positions recur is the only one on two positions.

The reason there is nowhere to pay is geometric. A player who must visit both positions infinitely often needs somewhere to choose between them, and a two-position board where nobody is stuck has no such place: any play that does not stop at one position already alternates. Three positions and a hub have one, and that is the hub game exactly.

The board that makes a winner use them #

The top of the scale needs a board with room for three objectives, and the room is a position the condition says nothing about.

The boards in the sweep below have one position for each thing the condition talks about, and that is a restriction rather than a definition. A board may have positions the condition says nothing about, and a play’s verdict is then decided by which of the named positions recur. The hub is such a position, and it is exactly what a board needs before a condition on three names can ask a player to cycle through three things.

On that board, under every position recurs, every strategy of two states was enumerated — every way of updating a two-state memory on arrival at a position, against every choice the memory can drive — and none of them wins. One of three states does, and its three states are the obvious thing: which spoke is owed next.

So the top of the scale is reached, and the bound is tight there. It is not reached everywhere: on this one board, fourteen of the sixty-seven conditions demand exactly what their trees price them at and fifty-three are satisfied with less, because this board is not the board that makes each of them bite. What holds across all of them is the direction that matters — nothing on any board searched here needs more states than its tree says.

What the trees cannot say #

Three positions is a small alphabet, and the scale stops where it does because of that. Three is the largest number the construction can return over three names, so fifty-eight at two and nine at three is a statement about conditions on three positions and not about conditions. Four names would give conditions costing four states and 32,768 of them.

The bound is over all boards, and no board here reaches it for most conditions. Fourteen of the sixty-seven are attained on the hub and the rest are not, which says the hub is the wrong board for them rather than that their price is wrong. Building the board that makes a given condition bite is a construction from its own tree, and nothing here does it.

The search that checks the trees is over strategies whose memory reads the position just arrived at. On the hub that costs nothing — the unnamed position sits between every pair of named ones, so a memory reading it learns something it could have deduced — and that was checked rather than assumed, by running the two-state search both ways on every condition priced at two and getting the same answer. It is a restriction in general and the page does not pretend otherwise.

And the numbers say nothing about how hard a strategy is to find. A three-state strategy exists; the search that found one on the hub enumerated tens of thousands of candidates, and on a board with more positions that enumeration is hopeless. A strategy is not a certificate prices the object itself, and a small memory does not make it small.

The convention the trees are built under #

A player with no move loses, carried over to plays that need not end, which is why the boards swept have nobody ever stuck: with a dead end anywhere, some starts are settled before the condition is consulted.

And the winner of a never-ending play depends only on the set of positions recurring — not on the order, not on how often. That is what makes the 128 a finite list and it is what the whole construction is about: the tree’s nodes are sets, its children are sets, and a condition that asked for one position twice as often as another is not on the list and has no tree here. What the play keeps coming back to adopts the same restriction for the same reason.

A condition Left cannot lose and a condition Left cannot win are both on the list and both cost one state, which is a triviality the table carries rather than hides: there is nothing for a winner to remember when there is nothing to do.

The surprise: the sweep was measuring its own boards #

Every earlier account of a never-ending play here reads as a measurement of a game. The first theorem labels a position graph, the paper was about how long counts rounds in one, every play ends and no round settles enlarges one until the count runs away, and the gap between two answers is a difference between two solutions on one. The rule decides who has to remember breaks that pattern and says so: memory is a property of the sentence, not of the board.

What is visible from here is that it broke the pattern with an instrument that had not. The sweep over 257 arenas is a measurement of a game — of 257 games — and what it reported was a property of those games as much as of the conditions. Thirty-two is the count of conditions that three positions happen to embarrass. The number belonging to the conditions is sixty-seven, and the difference between the two figures is not error or sampling: every one of the thirty-two is real and the thirty-five are equally real, and no enlargement of the sample reaches them.

That is worth holding beside the other places difficulty gets measured here. Space is the resource and how hard is it are about position graphs, and growing the graph is how their questions get harder. A puzzle asks once, a game asks alternately moves the difficulty into the prefix of quantifiers that states the question, which is the same move one step earlier. Here the object with the number on it is a family of sets, the construction that reads the number is seven nodes and two arithmetic rules, and a board never appears. Enlarging the board cannot change the answer, and enlarging the sample of boards could only ever have found what the smallest boards already show.

Still open: the board each condition needs, built from its own tree #

The tree gives a number and does not give a witness, and thirty-five conditions on this page are priced with no board anywhere that pays.

The construction that would supply one is the tree itself read forwards rather than backwards. A node with several children is a place a winner has to cycle, and a board that forces the cycling is a hub whose spokes are those children — laid out recursively, so a tree of depth two gives a hub whose spokes are themselves hubs. The board so produced would have as many positions as the tree has nodes, and the measurement that settles the matter is whether an exhaustive search over strategies of one fewer state fails on it, condition by condition.

If it does, then the tree’s number is attained for every condition and the two halves of the claim — no more than this, and no less — are both established here rather than one of them. If some condition is priced at more than any board it names can demand, the construction is an upper bound that is not tight, and the interesting question becomes which conditions are loose and why.