One half multiplies, the other adds

Half a licence is nearly all of it priced the two halves of a restricted universe’s substitution licence — rewrite a component, rewrite a subposition — on sums of two Cram boards, and closed by naming the variable it had held fixed:

The rung above is the number of components. Every measurement here is two boards, and the first half’s saving is the ratio of a product to a sum — so it should grow roughly like the state space of each board added, while the second half’s should not move. Three and four components would say whether that is right.

Three and four say it is right, and they say more: both halves have a closed form, and the two forms are different kinds of function.

Copies of one board #

Take $k$ copies of one board and count what a solver has to distinguish.

With no licence it must tell apart every state of the product — every combination of occupancies — which for $k$ copies of a board with $s$ states is $s^k$. Four copies of a $2 \times 3$ is 104,976, enumerated rather than multiplied. A product against a sum is the page that first drew that distinction, and every number here is a continuation of its table.

With the component licence it may replace a component by an equal game, so it evaluates each board separately and combines. That is $k \cdot s$ states — 72 for the same four copies.

With the subposition licence as well it may key its table on the shape of the free squares, and copies of one board have one set of shapes between them: seven, whether there are two copies or four.

So the three columns are $s^k$, $k \cdot s$ and a constant — a product, a sum and a fixed number, which is as clean a separation as this anchor is going to get.

Those three are worth reading as three different ideas about what a position is. With no licence a position is the whole board; with the component licence it is one board among several; with the subposition licence it is a shape, and a shape has forgotten which board it came from and where on it. Each licence is a further act of forgetting, and what it buys is what the forgetting saves.

Two closed forms #

The savings follow:

$$\text{component licence} = \frac{s^{k-1}}{k}, \qquad \text{subposition licence} = \frac{k \cdot s}{|\text{shapes}|}.$$

The first multiplies by roughly $s$ for every board added. The second adds a constant.

Both are checked against enumerated counts rather than derived and quoted: three copies of a $2 \times 3$ have 5,832 product states counted and $18^3$ predicted, four copies have 104,976 and $18^4$, and the savings agree to the last digit at every size.

That the second saving is linear is the whole content of the prediction. Adding a copy of a board adds $s$ states to what the component licence must hold and no shapes at all to what the subposition licence must hold, because the shapes are the board’s and the board is the same board.

What the comparison was a snapshot of #

At two components the component licence is worth 9 times and the subposition licence 5. That is a fair fight, and it is what made the rung below’s question — half the saving or almost none — a reasonable one to ask.

At three it is 108 against 7.7. At four, 1,458 against 10.3. At eight, 76 million against 20.6.

So the rung below’s answer, the two halves buy different orders of magnitude, was true and understated. They buy different orders of growth, and the comparison of two numbers was a snapshot taken at the one board count where the two are within a factor of two of each other.

That is the correction this page makes, and it is a correction to a reading rather than to a measurement. Every number the rung below reports is right; what it could not see is that the ratio between its two columns is not a ratio at all.

The control: boards that differ #

The reading above says the subposition saving is flat because the shapes are shared. If it were flat for some other reason, mixing the boards would not change it — so the sweep is run on sums of different boards as the control.

It does change, and in the predicted direction. Adding a different board adds its own shapes to the table as well as its own states, so both the numerator and the denominator grow and the saving stays near where it was: across six sums the subposition saving spans a factor of 1.82, from 4.24 to 7.71.

The component saving over the same six sums spans a factor of 62, from 9.0 to 560.3.

So the second half of the licence is the stable one and the first is a number about how many boards there happen to be. A solver reporting that its restricted universe saves five hundred times is reporting the size of its own sum.

There is a second reading of the same table and it is the one a builder wants. Because the subposition saving is stable, it can be budgeted: a solver knows before it starts that keying its table on shapes will buy it about five times, whatever board it is given and however many components the position has. The component saving cannot be budgeted at all — it is whatever the sum happens to be — and a saving that cannot be predicted is a saving a builder cannot plan around.

Why one is a product and the other is not #

The two growth rates come from two different arithmetics, and it is worth setting them out because the difference is the whole of the finding.

Components multiply. A sum of $k$ independent games has, as a state, one state from each — and the number of tuples is the product. That is the fact that makes a disjunctive sum expensive, and it is the whole reason the sum is the object is a hard problem rather than an easy one. Undoing a product is worth a product’s worth.

Shapes union. A table keyed on shapes holds one entry per shape a position can present, and the shapes a sum of $k$ boards can present are the shapes any one of them can present — a union rather than a product, because a solver looking up a position looks up one component at a time. Undoing a union is worth very little, because a union of $k$ copies of one set is that set.

So the asymmetry is between the two operations a sum performs on its parts. Adding components multiplies the state space and unions the shape space, and a licence that removes the multiplication grows like a product while a licence that removes the union does not grow at all.

That is a fact about sums rather than about Cram, and it should hold in any game whose components are drawn from a bounded family. What is specific to Cram is the size of the shape count — seven for a $2 imes 3$ — and that is where a different game would give different numbers and the same shape of answer.

What a solver should read off this #

The practical reading inverts the rung below’s, and it is worth stating plainly.

The component licence is what makes a sum tractable at all. Without it a solver faces a product, and a product of even three small state spaces is out of reach. It is not a shortcut; it is the difference between possible and impossible, and its size is a measure of how impossible the alternative was.

The subposition licence is what makes each board cheap. It is worth a steady four to eight times whatever the sum looks like, because it is a statement about one board’s positions and not about the sum.

So they are not two shortcuts to be compared. They act on different objects — one on the sum, one on the board — and comparing their sizes is comparing a fact about the sum with a fact about a board. The rung below did compare them and got a defensible answer for two components; the answer does not survive a third.

The tree and the graph is the other saving a solver makes, and the three now sort cleanly. Memoisation collapses positions the search reaches twice. The component licence collapses the sum into its parts. The subposition licence collapses each part’s positions onto shapes. Three different objects, three different growth rates, and only the middle one depends on how many components there are. The company that is closed is where the closures that grant the two licences are found, and it is the page that says which of these savings a given solver is entitled to.

The shape of the correction #

It is worth naming the kind of mistake this page repairs, because the ladder has now made it twice and the site has made it elsewhere.

The rung below measured two quantities at one value of a parameter and compared them. Both measurements were right. What was wrong was the comparison, because the two quantities were functions of the parameter and the parameter had been held fixed at the one place where they are close.

That is the same fault a threshold is a detection limit records on a different ladder — a number quoted without the population it was measured on — and it has the same fix: carry the parameter along. The component licence saves nine times is a fact about a two-board sum; the component licence saves $s^{k-1}/k$ is a fact about the licence.

The general form is that a ratio between two quantities is only a number when both are constants, and a measurement that reports one has to say what it is a ratio of. On this ladder the fix cost two more board counts and a derivation; the reason it was not done at the time is that two components looked like the natural case rather than like a value of a variable.

There is one thing the rung below did that made the repair cheap, and it is worth crediting. It measured both halves separately rather than reporting only their ratio, so the two columns were there to be extended. A page reporting the second half is worth about half the first would have left nothing to work with.

Why one saving compounds and the other does not #

The two closed forms are the finding, and the reason they have the shapes they do is worth stating, because it says which of the two licences to want without measuring anything.

The component licence collapses a product. A solver without it walks the states of $k$ components as a product; with it, each component is replaced by a class representative, so the product is over representatives rather than over positions. Replacing a factor in a product by a smaller one and doing it $k$ times gives a saving that is exponential in $k$ — which is where $s^{k-1}$ comes from, and why the benefit compounds with every extra piece on the board.

The subposition licence collapses within a component. It replaces the positions inside one part by their representatives, which shrinks each factor once and does nothing about how many factors there are. The saving is therefore a fixed amount per component, applied $k$ times additively — which is where $k \\cdot s$ comes from.

So the two are a product and a sum, and the shapes are forced rather than measured. The measurement’s job is to fix the constant $s$, and the prediction that one grows with $k$ and the other does not follows from what each licence is allowed to rewrite.

That gives a rule of thumb needing no arithmetic. On a board that has broken into many pieces, want the component licence; on a board that is one big piece, only the subposition licence has anything to do. And since a restricted universe is invoked precisely when a board has broken up, the cheap licence is the one that matters — which is the awkward conclusion this anchor keeps arriving at from different directions.

What this does not say #

Cram, and small boards. Every board here is at most nine squares, and the largest enumerated sum is four copies of a $2 \times 3$ — 104,976 product states. The closed forms are checked to four copies and quoted to eight, and the quotation is labelled as an extrapolation.

One game. Cram is impartial and symmetric under all eight symmetries of the square, which is what makes a shape-keyed table legitimate. Domineering is not, so its shape count would be larger and its subposition saving smaller — the direction is clear and the size is unmeasured.

Copies of one board are the easy case. The linear growth is exact when every component is the same board, because the shape count is then genuinely constant. On a mixed sum it is not constant, and what the mixed table shows is that it grows fast enough to keep the saving flat rather than that it does not grow. A sum of six genuinely different boards has not been measured, and it is the case where the two effects could come apart again.

And a licence has to exist before it can be priced. Everything here assumes a company closed under the relevant operation, which equal in this company establishes for three of the seven companies it finds and not for the rest. A solver in a company closed under neither has neither saving and faces the product. The closure that picks the nimbers is the extreme case, where closure is so strong that the company has almost nothing in it.

The convention, named #

Normal play throughout: a player who cannot place loses. Cram is the impartial game in which both players place dominoes either way up, so every position is a win or a loss outright.

A company is a set of games a solver stays inside, and two games are equal in a company when they are interchangeable in every sum with a member of it. Closure under addition licenses replacing a component of a sum; closure under options licenses replacing a subposition as well.

A state is what a solver must tell apart. With no licence that is a tuple of occupancies, one per board; with the component licence it is an occupancy on a named board; with the subposition licence it is a shape of free squares up to the eight symmetries of the square.

A board’s shape count is how many distinct free-square shapes its positions produce, which for a $2 \times 3$ is seven and for a $2 \times 2$ is three.

Every product state count here is enumerated, by walking the sum from the empty boards; the closed forms are checked against those counts and used past them only where the figure says so.

Where the ladder goes next #

The universes anchor has six rungs: restricted equality made computable, which restrictions license rewriting a sum, which license rewriting a subposition, what the second licence is worth, what the first is worth on its own, and now how the two grow.

The rung above is the third licence. The rung below found that decomposing each position into its connected regions and substituting for those collapses a whole sum to ten or fourteen shapes — a third step that was measured once and never priced against the board count. Its growth ought to be the flattest of the three, since a catalogue of regions does not grow with the sum or with the board, and if it is genuinely constant then the sequence of three licences is geometric, linear and constant. Equal in this company is where the apparatus that makes any of them legitimate is built, and the third licence is the one it has least to say about. That is a table with three rows and it would finish the anchor’s account of what a restricted universe buys.

Two neighbours are worth the trip. A product against a sum is where the first licence was priced, and it is the page whose number this one turns into a function. And the tree and the graph is the saving that is not a licence at all, and reading the three together is the site’s whole account of why a solver can do anything at all.