One of four questions

Three essays below this one are sweeps of day two. The simplest game above both establishes that its 22 values form a lattice — every one of their 253 pairs has a least upper bound and a greatest lower bound. Where the order and the sum disagree establishes that the lattice identity fails on exactly the incomparable pairs. Fifty-two errors and seven sizes measures the fifty-two error terms and finds they collapse to seven pairs of stops, three means and three temperatures, with a rule that predicts the temperature from the pair.

Every one of those is a result about 253 pairs, and the last of them closes by naming what would test it: the same sweep at day three, where there are 1,474 values and 1,085,301 pairs — a population sixty-seven times larger in values and four thousand times larger in pairs.

This is that sweep, and the first thing to report is that three quarters of it could not be run.

The order question survives, and it survives with an answer worth having.

Day two: 52 of its 231 pairs are incomparable, which is 22.5 per cent. Day three, over a sample of 4,000 pairs drawn from the full 1,474 values: 1,606 incomparable, which is 40.2 per cent. Nearly twice the share.

And the lattice holds anyway. All 1,606 incomparable pairs have a least upper bound and a greatest lower bound inside day three — not one of them is ragged, and the function refuses to return a result if a single one is.

Those two facts are worth separating, because it is easy to read the first as evidence against the second. A partial order in which more pairs are incomparable is a wider order, and width is what makes a lattice hard to have: the more pairs sit side by side, the more chances there are for two of them to have several minimal upper bounds and no least one. Day three doubles the width and closes up perfectly anyway.

There is a third fact in that table and it is the one that makes the first two comparable at all. Day two’s row is every pair — all 231 of them, exhaustively — and day three’s is a sample of 4,000 out of 1,085,301. So the two rows are not the same kind of measurement, and the essay is careful to say which is which. What makes the comparison fair is that the quantity being compared is a proportion, and a proportion is exactly what a sample estimates well. Forty per cent against 22.5 per cent, on 4,000 draws, is not a result that a larger sample would move.

Why the sample is of pairs and not of values #

There is a methodological point here that decides whether any of the above means anything.

A join is not a property of a pair. It is a search over the whole population: the least of everything above both. So a sweep that sampled 200 values out of 1,474 and looked at their pairs would compute the join of each pair inside the sample, and that is not the join — the true least upper bound might be one of the 1,274 values left out, and the sampled answer would be some other value that happens to be above both.

Sampling pairs has no such problem. Every join and meet here is computed against all 1,474 values, and only the choice of which pairs to look at is sampled. So each answer is exact and the uncertainty is entirely about coverage, which is the kind of uncertainty a sample is allowed to have.

That distinction is what makes the lattice claim reportable at all. It is a claim about 1,606 pairs, every one of them settled exactly, out of 1,085,301 — and it can be falsified by one bad pair, which is why the sweep is written to stop rather than to average.

Bounds day two could not supply #

The second thing the order sweep found was not one of the questions asked, and it is the more interesting of the two.

An average day-three pair has 272 upper bounds and 255 lower ones — a couple of hundred values above it and a couple of hundred below, out of 1,474. Exactly one of each is least.

Not one of those least ones is a day-two value. Zero out of 1,606 joins, zero out of 1,606 meets.

That is not obvious and it is not an artefact. Day two’s twenty-two values are perfectly good upper bounds — a large enough number is above almost anything — and they turn up in those two hundred constantly. What they are never is the least upper bound, because being least requires sitting immediately above the pair, and day two’s values are spaced too coarsely to sit immediately above anything born a day later.

It is worth checking that this is not an artefact of how “day two value” is being tested. The test is by name — a join is a day-two value if its canonical form prints as one of the twenty-two — and canonical forms are unique, so the test is exact rather than approximate. A join that happened to equal ∗2 would be caught. None does.

The count of bounds is the other half of the reading and it is worth not skipping. Two hundred and seventy-two upper bounds per pair means the pair is very far from being near the top of the order: there is a large population above it, and the least element of that population is a specific value that has to be searched for. That is what makes the lattice property non-trivial. If a pair had three upper bounds, having a least one would be almost automatic; with two hundred and seventy-two, the chance that no single one is below all the others is where a lattice usually fails, and it never does here.

So the lattice day three has is one day three built for itself. The 22 older values are carried along inside it and none of them does any of the closing-up. That is a fact about how the construction proceeds — the birthday of a sum is about the other direction, how far a sum’s birthday can run ahead of its parts’ — and it says something specific about why each day is worth constructing: not because the old values were wrong, but because the gaps between them are where every new bound has to go.

The three questions that could not be asked #

The difference between the question that could be asked and the three that could not is exactly one word, and the word is sums.

Asking whether the order is a lattice means asking whether one day-three value is below another. That is a comparison of two games born on day three, and the site does 4,000 pairs’ worth of them in twenty seconds.

Asking whether the lattice identity holds means asking whether (a ∨ b) + (a ∧ b) equals a + b. Both sides are sums of two day-three values. A sum of two games born on day three is born on day six, its option sets are the unions of shifted copies of the originals’, and deciding whether two of them are equal is a search several orders larger than the comparisons above.

It did not merely take longer. It ran out of memory, at 220 sampled pairs and then at 60, with two optimisations applied in between: the sums left uncanonicalised, since a comparison is a question about a difference’s outcome and does not care about the form; and the least-upper-bound search reduced from quadratic in the candidates to two linear passes, which on two hundred and seventy candidates is a hundred-fold saving. Neither moved the wall, because neither touched the day-six comparison.

That is a measurement rather than an excuse, and it is worth recording as one. The obstacle is not the number of pairs, which a sample handles. It is not the number of values, which the join search handles. It is the birthday of the objects being compared, and it triples the moment addition enters.

What was tried before the wall was believed #

A report that a computation ran out of memory is worth exactly as much as the account of what was tried, so here is the account.

The first attempt was the obvious one: sample 220 pairs, compute the join and meet of each, form both sides of the identity, canonicalise them, and compare. It exhausted an eight-gigabyte heap after two minutes.

The second attempt fixed the bound search, which was written in the obvious quadratic form — collect every upper bound, then keep those below all the others. On a pair with 272 upper bounds that is 74,000 comparisons per bound and 148,000 per pair. Replacing it with a linear scan for the minimum plus one verification pass gives the same answer in 544 comparisons, a saving of two hundred and seventy-fold, and it is exactly as correct: a least element wins every comparison it takes part in, so the scan finds it if it exists, and the second pass is what distinguishes least from merely minimal. That is a real fix and it is now in the code the order sweep above uses. It did not move the wall.

The third attempt stopped canonicalising the sums. Testing (a ∨ b) + (a ∧ b) = a + b does not need either side reduced — equality of games is a question about the outcome of their difference and is indifferent to the form — so both sums were left as built and only the error terms of failing pairs were reduced. It did not move the wall either, and the sample was cut from 220 pairs to 60. Still eight gigabytes.

At that point the wall is identified rather than guessed at. Three separate costs were removed and the failure did not shift, which leaves the one cost that was never removed: deciding a comparison between two games born on day six. Everything above it in the computation is negligible by comparison, and no amount of reorganising the parts that are negligible changes an answer they do not determine.

What that says about the results below #

The three unaskable questions are the ones the rungs below answered, and this rung’s honest contribution is to say what their status now is.

They are results about day two. They were always results about day two, and the ladder said so. What day three would have added is the one thing a single population cannot supply: evidence that the collapse — fifty-two error terms into seven pairs of stops and three means — is a fact about the construction rather than about a small set. That evidence is not available, and this essay’s contribution is to establish that it is not available for a reason, rather than because nobody has run it yet.

The reason has a shape worth carrying. Every question about order among day-n values costs a day-n comparison. Every question about arithmetic among them costs a day-2n comparison. So the order half of this subject scales one day at a time and the arithmetic half scales two, and any sweep that mixes them will hit the wall on the arithmetic while the order is still cheap. That is exactly what happened here, and it will happen at day four to anybody who tries the order question there.

Comparison is a search is the essay about what a single comparison costs. This is what happens when the cost is multiplied by a million and the objects double their birthday.

A day is not a difficulty setting #

The general shape here is worth stating apart from the lattice, because it is the thing that transfers.

It is natural to read the days as a difficulty scale — day two easy, day three harder, day four harder still — and to expect a sweep that works at one day to work at the next with more patience. That reading is wrong in a specific way, and this rung is the demonstration.

A day is a doubling of the objects and a squaring of the population, and neither of those is what stops the sweep. The 1,474 values are a fine number of things to hold. The million pairs are handled by sampling, exactly, with each answer computed against the whole population. Both of the quantities anybody would worry about are affordable.

What is not affordable is a property that pushes the objects onto a later day. Addition does that: it takes two day-three games and returns a day-six one. So a question about sums is not a question about day three at a larger size; it is a question about day six at a smaller one, and day six is where the enumeration became impossible three days earlier.

That is why the four questions split the way the figure above shows, and why the split is by what each compares rather than by how many comparisons each makes. Where the braces stop measures the same explosion from the notation’s side — the length of the expression roughly squares each day — and the two are the same fact seen from two places: a game’s description and a game’s comparison both grow with the birthday, and addition raises the birthday.

What is worth doing instead #

Three things follow, and none of them is “get a bigger machine”.

The order question can be pushed further and cheaply. Day four cannot be enumerated at all — there are over 10³⁸ values — so the order question stops for a different reason there, but within day three the sample can be made much larger than 4,000 pairs at linear cost, and the lattice claim would firm up accordingly. Nothing here suggests it would fail.

There is also a cheaper question next door that this sweep did not ask and could. The lattice property is about every pair having bounds; the width of the order — the size of its largest antichain — is about how many values can sit mutually incomparable at once. Day two’s incomparable share is 22.5 per cent and day three’s is 40.2, and neither number is the width. Computing the width exactly is a maximum-independent-set problem and is genuinely hard, but bounding it below is a greedy scan and costs no more than the sweep above. It would say something the share cannot: whether the order is getting wider everywhere or growing a few large flat regions.

The two halves of the subject scale differently, and the general form of that is what knowing who wins and knowing what it is worth prices: an outcome is a bit and a value is a construction, and the second grows the way the birthdays do. The sum is the object is why the arithmetic half is the one anybody wanted swept.

The arithmetic questions need a different method rather than more of this one. Comparing sums of day-three games by brute force is the wrong approach; the right one is to compute the error term’s invariants — stops, mean, temperature — directly from the pair without forming the sum, which is what the temperature rule in the rung below was reaching for. If that rule could be proved rather than observed, it would answer the question the sweep cannot.

And the collapse itself deserves a sharper statement than a count. Seven pairs of stops out of fifty-two error terms is a striking ratio and it is a ratio over one small population. What would make it a result is a reason — some argument that an error term’s stops are determined by something about the pair with only seven possibilities. A bound instead of an answer is the usual fallback when a quantity resists a formula, and here the quantity has already been bounded: the error is never larger than the span of the interval the pair straddles, which the rung below checks on all fifty-two. What is missing is not a bound. It is the reason the bound is nearly always attained in one of seven ways.