A hypothesis has to hold all the way down

Two rungs below, Milnor’s bound is checked twice and the second check is the point: the bound holds on all three thousand three hundred and twenty-one pairs of four-coin rows where the hypothesis holds, and breaks on three hundred pairs where it does not. Every violation is outside the hypothesis and none is inside it, which is the shape a load-bearing condition has.

The hypothesis being tested there is checked on the row. That is the natural place to check it, it is where the definition puts it, and it is not the condition the theorem needs.

Where the condition has to hold #

Milnor’s claim is about a sum: the score of one game beside another is within the sum of their temperatures of the sum of their means. A claim about a sum is proved by induction over the play — the first move goes into one component or the other, and the argument recurses on what is left.

So the condition the induction consumes is not a condition on the position it starts from. It is a condition on every position the play can reach, because the induction visits all of them and applies the hypothesis at each.

That distinction is invisible for most families of game, because most game families are closed under moving: a Nim position’s options are Nim positions, a Domineering board’s options are Domineering boards, and a property that holds of every member of the family holds of every subposition automatically.

The coin row is not closed in that sense. A row of four coins from {−2, 1, 3} has options that are rows of three, and those are rows over the same coins — so the family is closed. What is not closed is the condition: a row whose ends are harmless can perfectly well contain a row whose ends are not, because what is left after two moves is the middle, and the middle was never at an end before.

The three columns #

Take every row of three coins from {−2, 1, 3} — twenty-seven of them — and check the condition twice on each. Once at the root: is the score with Left to move at least the score with Right to move? And once hereditarily: is that true of every interval of the row, all six of them?

Fifteen pass at the root. The other twelve are rows a player would rather not be to move in, and they are the ones the rung two below is about.

Seven pass hereditarily. So eight of the fifteen that pass the outer test fail the inner one — a subposition somewhere inside them is a position where having the move is a disadvantage, and the outer test never looked at it.

Then take all three hundred and seventy-eight pairs and check the bound on each. Sorted by the two conditions, the counts are:

Pairs where a row fails even at its root: two hundred and fifty-eight, and the bound holds on nought of them. Every single one is broken. That is the column the rung two below already found, at full strength.

Pairs fine at the root with at least one broken underneath: ninety-two, and the bound holds on sixty-eight. Twenty-four break it.

Pairs fine everywhere: twenty-eight, and the bound holds on all twenty-eight.

The first and last columns are what a reader expects: outside the hypothesis it fails, inside it holds. The middle column is the one the definition does not name.

Which is the whole argument #

Twenty-four broken bounds, every one of them in the middle column. That is what makes the distinction a distinction rather than a pedantic reading of a definition.

A reader checking Milnor’s condition the way the definition states it — on the position — would have looked at all ninety-two of those pairs, found the incentive non-negative on both rows, and concluded the theorem applies. It does not, and on a quarter of them the conclusion is false.

The proportions are worth reading as well as the counts. Of the hundred and twenty pairs that pass the outer test, twenty-eight are genuinely covered and ninety-two are not, and the ninety-two are where three quarters of the pairs a careless reading would claim actually sit. The easy test is not slightly too generous. It admits four times as many pairs as the theorem covers.

Nothing about the failing pairs is visible from the outside. The rows have the same lengths as the ones that work, coins from the same set, ends that behave perfectly well. What separates them is a fact about a position two moves in.

Why the condition is not hereditary by itself #

It would be tidy if the condition propagated: if a row satisfying it were guaranteed to have subpositions satisfying it, the distinction would collapse and the definition would be fine as written.

It does not, and the reason is that the condition is about ends and the play changes which coins are ends.

A negative coin buried in the middle of a row hurts nobody. Nobody has to take it, because taking is from the ends, and while it sits in the middle it is invisible to the incentive question. Two moves later it may be at an end, and then it is exactly the coin nobody wants.

So the coin row hides its own zugzwangs, and hides them in the place a check on the position is least likely to look. That is not a property of coin rows in particular; it is what happens whenever a game’s condition is stated in terms of the available moves rather than in terms of the whole position, and available moves are the thing play changes.

The repair, and what it costs #

The repair is to state the condition hereditarily: a game is admissible when every position reachable from it satisfies the incentive condition.

That is what the modern literature on scoring games does when it restricts the class in order to recover structure — the several attempts since 2010 to get a group back are all of this shape, choosing a class closed under the operations the theory needs and then proving things about the class rather than about scoring games in general.

What it costs is coverage, and the count says how much. It is the same trade the universes field prices: a smaller class with more structure in it, chosen because the structure is what the theorems need. Seven of twenty-seven rows are hereditarily admissible. Under the root-only reading, fifteen are.

That is a class less than half the size, and the difference is not a technicality: it is the difference between a theory covering a bit over half the family and one covering a quarter of it. A reader who wants the bound has to accept the smaller class, and a reader who wants the larger class does not have the bound.

And there is a second cost that the counts do not show. The hereditary condition is not a property a reader can see. The root condition can be checked by playing the position out twice; the hereditary one requires playing out every interval, and on a game whose positions do not nest it requires playing out everything the position can reach. A restriction that cannot be recognised from the board is a restriction a player cannot use, however sound the theorem it supports.

Checking a condition on a position and checking it on a game #

There is a habit worth extracting, because this is not the first time the distinction has decided something on this site.

A property of a position and a property of a game are different objects. The first is a fact about what is on the board; the second is a fact about the whole tree beneath it. Most useful conditions in this subject are of the second kind, and most of them are stated in the first form because the first form is what a reader can check.

The pattern shows up everywhere once it is named. A universe of games has to be closed under the operations it is asked about, or a claim inside it is a claim about a set that the play leaves. A dead-ending game is defined by a property of every position it can reach, not of the one in hand. And the misère theory’s whole apparatus of quotients exists because outcomes of positions do not determine outcomes of sums, which is the same complaint one level further out. A bound with one number too many is the same habit applied to an inequality rather than to a hypothesis: state it, then find out what it is actually true of.

Each time, the position-level statement is the one people use and the tree-level statement is the one the theorem needs. Each time, they coincide on the examples that got somebody interested and diverge somewhere less obvious.

Nothing here is evidence against the theorem #

It is worth being explicit about what has been refuted, because “twenty-four pairs break Milnor’s bound” is a sentence that reads as an attack on a sixty-year-old result and is not one.

Milnor’s theorem is true. What the middle column refutes is a reading of it: the reading that checks the hypothesis where the definition is written and applies the conclusion anyway. The theorem’s own hypothesis is the hereditary one — a proof by induction cannot use anything weaker, because the induction visits the subpositions — and every pair the theorem actually covers is in the third column, where the bound holds on all twenty-eight.

That is the ordinary shape of this kind of finding and it is worth naming so it is not misread twice. A counterexample to a careless reading is not a counterexample to a theorem. What it establishes is that the careless reading is careless, which is a fact about how the condition is usually stated rather than about whether the mathematics is right.

The same distinction decides how to use the numbers. Twenty-four broken bounds is a measurement of how much slack the loose reading has, and it is large. Nought broken bounds in the clean column is a measurement of nothing at all, because the theorem forbids one — and a sweep that found one would be a bug report about this site rather than about Milnor.

What the two conditions look like on a real game #

The coin row is a laboratory and it is worth asking what the distinction does to a game somebody plays.

Go satisfies both conditions, for the reason the rung below gives: it has a pass, so the incentive is non-negative everywhere by construction, and everywhere includes every subposition. Milnor and Hanner were writing about Go and the hereditary reading costs them nothing.

Dots and Boxes satisfies neither, and fails them in the most emphatic way available: the entire subject of that game is a move played in order not to have to move again, so having the move is a disadvantage constantly and at every depth. The mean-value theory has nothing to say about it and never claimed to.

What has no examples on this page is the interesting class: a real game satisfying the root condition and failing it underneath. The coin row supplies eight of them out of twenty-seven, which is what a laboratory is for. Whether a played game does is a question this site cannot answer, and it is the question that decides whether the distinction is a curiosity or a trap.

What a hereditary check costs to run #

The condition is more expensive to check than it looks, and the expense is the reason the definition is stated the easy way.

A row of n coins has n(n+1)/2 intervals, and the incentive condition on each is a separate solve. The solves share work — the interval recursion is memoised, so a row of three costs six intervals and a row of ten costs fifty-five, all of them subproblems of the outer one — so in this family the hereditary check is free once the root check has been done.

That is a fact about coin rows and not about scoring games. A game whose positions do not nest — whose options are not subproblems of the position — pays the full price for each, and the hereditary check becomes a sweep over the whole reachable set. Which is to say: the honest condition is the expensive one, and it is expensive in exactly the games where a reader would most want a cheap test.

What the picture cannot show #

Nothing here proves the hereditary condition is sufficient. Twenty-eight pairs, all holding, is evidence and not a theorem, and a wider sweep could turn up a pair that satisfies the condition everywhere and breaks the bound anyway. What the counts establish is the necessity of the stronger reading — the middle column is a set of counterexamples to the weaker one, and a counterexample is a proof of something.

The bound under test is the sum of the temperatures. The rung two below records that the sharper form — the larger of the two temperatures — is what this site’s normal-play essays state for repeated copies of one game, and that it is false for a sum of two different ones, broken by five hundred and sixty of three thousand three hundred and twenty-one pairs. Everything here is about the correct, weaker bound.

Nor is the reachable set the same as the set of intervals. The check here sweeps intervals of the row, which for this game is exactly the set of reachable positions, since a coin row’s options are its subrows. A game where that coincidence fails needs the reachable set computed rather than enumerated, and the two can differ by a great deal — which is the whole difficulty of counting positions rather than routes.

And the coin values are small integers. The condition’s failure needs a coin nobody wants, and a negative coin is the crudest way to supply one. Whether a scoring game with all-positive plays can hide a zugzwang in a subposition is a real question and this family cannot ask it, since a row of positive coins satisfies the condition everywhere by inspection.

The convention, named #

Scoring throughout: the game ends when the row is empty and the higher total wins. No pass, which is the rung below’s subject and is deliberately absent here — a pass makes the incentive condition automatic at every position at once, which would make this entire measurement return nought and nought.

That is worth stating as a relation between the two rungs rather than as an omission. A pass makes the condition hereditary for free, because the one-line argument that gives it at the root gives it everywhere: every subposition of a passing game is itself a passing game. So the class this rung is measuring the size of is a class that a passing game belongs to automatically, and the whole distinction exists only for games without one.

Which is to say the two rungs are the same finding from two directions. Without a pass the condition is a real restriction and it has to be checked all the way down; with a pass it is not a restriction at all.

The surprise: the failure hides where the definition is not looking #

The expected shape of a result like this is a boundary — some rows satisfy the condition, some do not, the bound holds inside and breaks outside, and the definition draws the line correctly.

What the counts show is a third region the definition does not name. Rows that satisfy the condition where the definition says to look, and violate it where the theorem needs it, and break the bound. Ninety-two pairs sit there and twenty-four of them are counterexamples to a theorem nobody would have thought they were testing.

The reason that region exists is worth carrying past scoring games. A hypothesis is written down at the position, because that is where a reader stands; the proof consumes it along a path, because that is where an induction goes; and the two coincide only when the property is closed under moving. Nobody checks closure, because a property stated at a position does not look like it has a closure question attached to it.

The way to find out whether a condition has this defect is cheap and is the whole method here: state it at the position, state it at every reachable position, count the difference, and score the theorem against both. If the two counts agree the definition is fine as written. If they do not, the gap is a list of positions the theorem does not cover and everybody thinks it does.

Where the ladder goes next #

scoring has three rungs and each is about a piece of structure a scoring game does or does not have: the last-move convention it lacks, the pass that fixes one hypothesis and breaks another, and the closure a condition needs before an induction can eat it.

The rung above is the piece of structure whose absence costs the most. In normal play, comparison is a subtraction: one game is at least as good as another exactly when their difference is not worse than nothing, and that equivalence is what makes the whole apparatus computable. It is a theorem about groups. A scoring game has no inverses, so it has to be checked rather than carried over — and the sharpest case is a game against itself.