The family with two witnesses

The parameter was the difference found the four conditions whose kernels are the losing sets of bounded Moore’s Nim, and found them indexed by $n - k$ — the number of heaps less the number a move may touch — rather than by the heap count everybody had been reading them against. Then it stopped, on purpose, and wrote down what that reading predicted for a heap count the sweep had never reached:

Six predictions are written down — two failures and four conditions, each with its equations — and the computation that settles all six is the same one that produced this table with a larger heap count in it … a prediction checked in the same session as it is made is indistinguishable from a fit.

The sweep has now been run. Five of the six predictions held, and the one that broke is the one that had the least evidence behind it when it was made.

That is a good rate and it is not the interesting number. The interesting number is which one failed, and the answer turns out to be legible from the rung below’s own table rather than from anything about Moore’s Nim.

What was predicted, and by whom #

Two readings were in play, and the whole point of the seven-heap sweep was that they disagree.

The older one belongs to the parities, in size order, which found that sorting the heaps largest first and reading their parities settles the game completely at five heaps and fails at six. Read that way, the boundary is the heap count, and seven heaps is past it: every width at seven heaps should fail.

The newer one belongs to the rung below. Read against $n - k$, the six-heap failure is not about six heaps at all — it is $n - k = 4$, the fourth family failing to exist — and the three smaller values of $n - k$ should keep working wherever they occur. Read that way, seven heaps should split: $k = 2$ and $k = 3$ fail, because they are $n - k = 5$ and $n - k = 4$; and $k = 4$, $k = 5$ and $k = 6$ settle, because they are $n - k = 3$, $2$ and $1$, with conditions already written down.

The two readings therefore differ on four of the six widths, which is as clean a separation as a ladder ever gets. One of them says all six fail; the other says three fail and three settle, with these three conditions. There is no way for both to be substantially right.

The heap-count reading is wrong on three of six widths, and wrong in the direction that matters: it forbids exactly the structure that turns out to be there. The difference reading is wrong on one.

The one that broke #

$n - k = 3$ was predicted to settle, with the condition the rung below wrote as the parities pair off from the smallest heap upward, each pair equal, and the pairs’ common values exclusive-or to nought. At seven heaps with $k = 4$ it does not settle.

The failure is worth stating precisely, because it is not the failure a wrong condition produces. A condition that is merely wrong picks out the wrong set of parity words, and the fix is a better condition. What happens here is one level worse: four of the 128 parity words contain both won and lost positions, so there is no condition on the word — right, wrong or yet to be discovered — that decides those positions. The word has stopped being a complete invariant, and a rule written on it cannot be repaired by being written better.

There is a second and smaller failure underneath the first. Of the 124 words that are uniform, the pairing condition gets six wrong — six words it declares losing that every position carrying them wins. So even restricted to the part of the space where the word still decides the game, the condition is not right. Both failures point the same way and neither is a near miss.

The control, which is the part that could have gone the other way #

The rung below did not believe its own six-heap failure until it had checked that the failure was about the game rather than about the sweep. Raising the heap cap from seven to eleven and then to thirteen left the six-heap failure unchanged, and that is what licensed reading it as a fact.

The same test applies here with more force, because a family failing at its third witness is exactly what a sweep too small to see the structure would produce.

It does not move. The same four words hold both outcomes with heaps capped at seven and capped at nine, and the same six uniform words are misread at both. Whatever is happening at $n - k = 3$ and seven heaps is a fact about the game.

One heap further out #

A condition with two witnesses that fails at its third is a coincidence caught. A condition with two witnesses that fails at its third and at its fourth, in the same shape, is a coincidence with a mechanism — and the mechanism is worth more than the refutation.

At eight heaps, $n - k = 1$ and $n - k = 2$ hold. They give exactly the kernels their conditions predict, as they have done at every heap count anybody has swept. And $n - k = 3$ fails again, with four mixed words, and the four are the seven-heap four with an extra leading one: 1111001 becomes 11111001, and so on down the list.

That correspondence is the surprising part of the page. The failure is not four arbitrary words that happen to be four again; it is the same four words, in a family indexed by how many leading odd heaps sit in front of a fixed four-bit tail. Whatever is defeating the parity word at $n - k = 3$ is a local phenomenon at the small end of the sorted heaps, and the large heaps in front of it are along for the ride.

The family with two witnesses #

Here is the reading the whole sweep was worth running for, and it is not about Moore’s Nim.

The rung below proposed four conditions. Each was computed from a measured losing set rather than guessed, and each was then checked against every case in the sweep where it applied — which is a real check and is the reason that page’s own findings stand. But the four conditions were not checked against the same number of cases, because the sweep reached only six heaps and the four families occur at different rates within it.

The condition on the number of odd heaps had four witnesses. Every parity equal had four. All but the smallest equal, and the smallest even had three. And the parities pair off from the smallest heap had two — the fewest of the four, and the only one of them that has since turned out to be a coincidence of the cases it was fitted to.

This is not hindsight dressed as a rule. The witness counts were printed on the rung below’s own families figure, in a column headed cases, next to each condition. The information that the pairing condition was the shakiest of the four was on the page that proposed it, in the figure that proposed it, and nobody read the column that way — including the page’s own closing section, which named the seven-heap sweep as the next rung and forecast that $k = 4$ would settle.

A condition checked against two cases is a curve through two points. The other three families are the same kind of object checked more often, and they have survived every heap count reached since. That is the whole content of the finding, and it transfers to every ladder on this site that has proposed a family from a sweep: the number in the cases column is a confidence, and it should be read as one.

All odd, but the last three #

The correspondence between the two heap counts is close enough to be a description, and writing it down turns the failure from a list into a predicate.

At seven heaps the four mixed words are 1111001, 1111010, 1111100 and 1111111. At eight they are 11111001, 11111010, 11111100 and 11111111. Strip the leading run of ones from each and what is left is 001, 010, 100 and 111 — the same four three-bit tails at both heap counts, and they are exactly the three-bit words with an odd number of ones in them.

So the mixed words are the words in which every heap is odd except possibly among the smallest three, together with an odd number of odd heaps among those three. The run of large odd heaps in front contributes nothing but its length — one more of them turns the seven-heap list into the eight-heap list and changes nothing else.

The companion class settles the matter. Take the same all-ones prefix and give it an even three-bit tail — 1111000, 1111011, 1111101, 1111110 — and every one of those words is uniform, and every one of them is a win for the mover. So it is not the long run of odd heaps that defeats the parity word: a word can be almost all ones and still decide the game perfectly well. What defeats it is the run of ones together with an odd tail, which is a condition on the interaction between the two ends of the sorted list rather than on either end alone.

That is worth setting against what the surviving families do. The parities, in size order established that the parity multiset is not enough and the parity sequence is, and the two conditions that survive to eight heaps are both statements anchored at the small end — all but the smallest equal, and the smallest even names the smallest heap explicitly. The condition that failed is the only one of the four that pairs the heaps up across the whole word, and it is defeated by precisely the words in which the pairing has to reach from one end to the other.

What the solver computed, and how #

Positions are heap lists of at most seven heaps with no heap above seven, unordered, which is 3,432 lists at seven heaps and 6,435 at eight. A position is losing under bounded Moore’s Nim at width $k$ when every move from it leads to a winning position, and a move takes at least one counter from between one and $k$ heaps; the recursion is memoised on the sorted heap list and the width, and it is the same evaluator the rung below used with the heap count raised.

Each position is then labelled with its parity word — the heaps sorted largest first, each replaced by its parity — and the words are grouped. A word is uniform when every position carrying it agrees; the sweep settles the game exactly when every word is uniform, and the losing words are then a set that can be tested for closure under exclusive-or and handed to the equation finder.

The equations are computed rather than fitted: for each of the $2^n - 1$ non-empty subsets of the parity positions, the sweep asks whether that functional vanishes on every losing word, and row-reduces the ones that do. Where the game settles, the kernel of the resulting system is compared against the family’s predicate word by word. A case is counted as having kept its prediction only if it settles and gives its family’s kernel — settling under some other rule would be a different result wearing the prediction’s clothes, and would be scored as a break.

Where the game does not settle there is no losing-word set to hand to the equation finder, and the sweep reports the mixed words instead. The counts in the figures are those two quantities and nothing else.

Where the model stops #

Seven heaps at a cap of seven and of nine, and eight heaps at a cap of seven. Nothing here reaches nine heaps, and nothing here reaches $n - k = 3$ at a tenth heap count, so the statement that the pairing condition holds at exactly two heap counts is a statement about the four that have been swept.

The convention is normal play throughout — the player unable to move loses — and every result on this anchor depends on it. Bounded Moore’s Nim under misère play is a different game and this ladder says nothing about it.

And the figures cannot show the thing a reader most wants to see, which is why those four tails defeat the word. The tables report that 1001, 1010, 1100 and 1111 are the four suffixes that go mixed at $n - k = 3$, and that the number of leading ones in front of them does not matter. They do not exhibit a pair of positions with the same word and different outcomes, because a witness pair is a fact about two specific heap lists and the finding is a fact about a class of words. The pair exists — every mixed word has one — and reading it off would be a different figure on a different rung.

Who found what, and when #

Moore’s rule is from 1910, and taking from several heaps at once is where it and its restriction to unbounded heaps live on this site. Everything about the bounded game — heaps with a cap, which is where the closed form stops applying — is this site’s own sweeping, and the ladder that produced it runs through the count of odd heaps, the rule a smaller move breaks and the patch that generalised before reaching the parity word.

The prediction scored here was made on this site on the rung below, in the knowledge that it could be run and with a stated reason for not running it. That reason was good and it is worth repeating: the value of a forecast is in the gap between when it is made and when it is checked, and a ladder that closes that gap inside one session has bought itself a fit rather than a test. The forecast came out at five of six, and the sixth is more informative than a clean sweep would have been.

Where the ladder goes next #

The moores-nim anchor has eight rungs: Moore’s rule, the count of residues, the patch that generalised, the wider move being the easier game, the count of odd heaps, the word the sizes make of them, the map that word is the kernel of, and now the heap count that map does not reach.

The rung above is the four tails. 1001, 1010, 1100 and 1111 defeat the parity word at $n - k = 3$ and the number of odd heaps stacked in front of them changes nothing, which is a much narrower question than the one this page answers and is completely specified: take the four suffixes, exhibit for each a pair of positions sharing the word and differing in outcome, and ask what the two positions differ in that the word threw away. The answer is a statistic of the sizes that the sorted parities do not carry, and the rung below already knows one candidate — the smallest heap’s actual size rather than its parity — because that is the quantity the $n - k = 2$ condition names and the $n - k = 3$ condition does not.

Two neighbours are worth the trip. A period is a proof is where a finite window is shown to settle an infinite claim, and it is the standing account on this site of what it takes for a pattern found in a sweep to become a theorem rather than a description — which is exactly the promotion the pairing condition failed to earn. And a pattern that has not started yet is the other page here about a sweep whose interesting behaviour was outside it, where the rarity turned out to be the ordinary case and the recorded defects turned out to be a tail.