What a value costs to write down

A canonical form is the simplest form of its value. The word is doing a job, and the job is narrower than it sounds: the reduction removes options, and what it leaves is the form with the fewest of them. Nothing in the theorem says anything about how long the resulting expression is.

At width four — where more of the day’s values sit than at any other width — the shortest expression is nine symbols and the longest is twenty-five. The same number of options, and nearly three times the writing.

The question the rung below left open #

How wide a form can get measured the width of every value of the day and asked whether a bypass could leave a form permanently wider than it found it. The answer was no, on all 64,515 forms swept. It closed by naming a second measurement it had not made:

Width counts options; depth counts levels, and a form can be narrow and deep or wide and shallow. The two together are what a printed expression costs, and neither has been measured against the other here.

Half of that turns out to be unavailable and the other half turns out not to be the point.

The unavailable half is depth. For a canonical form the depth is the birthday, exactly — that is what the day a value is born establishes, and it means depth is not an independent quantity to plot width against. Every value born on day three is written four levels deep, all 1,452 of them, and asking which of them is deeper than which is asking nothing.

That is why the depth column is spent before this page starts. It is not that depth is uninteresting; it is that for the only forms this page counts — the canonical ones — depth is a second name for the birthday, and the essay would be plotting a quantity against itself.

What is left once depth is spent is the quantity the sentence was reaching for and did not name: the size of the expression. How many positions have to be written down to write the value down at all.

Counting the symbols #

A brace expression is a tree. Writing $\{1, \{1 \mid 0\} \mid 0\}$ means writing the top position, then each of its three options, then each of their options, down to the empty game. The count of nodes in that tree is the count of symbols, and it is what a page, a screen or a printed table actually pays.

So: walk the canonical form and count. Nothing subtle, except one decision that turns out to be the whole essay — a subposition appearing in two places is counted twice, because writing it out writes it twice.

Day three’s answer is that the mean form takes 16.92 symbols and the largest takes thirty-seven:

$$\{\{1 \mid 0, \ast\},\; \uparrow,\; \uparrow\!\ast \;\mid\; \{0, \ast \mid -1\},\; \downarrow,\; \downarrow\!\ast\}$$

Six options, thirty-seven nodes. And the two widest values of the day, the ones with seven options each, take thirty-one. The widest value is not the longest. Whatever the reduction is minimising, it is not the length of the line.

Two values that cost exactly the same #

The clearest way to see that a total is a poor description of a piece of writing is to find two pieces of writing with the same total.

Seven of day three’s values are written at exactly thirty-one symbols, and their widths run from five to seven. The narrow one carries more of its bulk at the bottom; the wide one carries more at the top. A reader meeting the two on a page would not describe them as equally complicated, and no single number here separates them.

That is the honest end of the width-against-depth question. On a fixed day, depth is fixed and width is free, and the size still has two degrees of freedom left over — because the expression is a shape, not a pair of dimensions.

A tree of a thing that is a graph #

The decision to count a repeated subposition twice is not a convention. It is the fact the notation is built on, and the size of it is startling.

The mean value’s expression is 2.44 times larger than its own content. The worst case is the thirty-seven-symbol form above, which names eleven distinct positions and writes them out thirty-seven times.

And the values whose forms repeat nothing at all number seven. They are $-3, -2, -1, 0, 1, 2, 3$ — the integers, and nothing else on the day. An integer’s canonical form is a path: $3 = \{2 \mid \}$, $2 = \{1 \mid \}$, and so down. A path has no way to reach the same node twice.

Every other value born by day three — all 1,467 of them — names some position at least twice in its own canonical form.

The mean of 2.44 hides the shape, and the shape is the useful part. Sorting the day’s values by the ratio of symbols to positions gives 259 whose expression is less than twice its content, 959 between twice and three times, 237 between three and four, and nineteen at four or more. The bulk sits in the middle band, which is to say that a typical canonical form on this day names each of its positions between two and three times.

The nineteen worst are all values whose two option lists overlap heavily, which is what a value confused with a great many things looks like: the same subposition appears as a Left option and again as a Right one, and each copy drags its own sub-tree along. That is the structural reason a nimber is expensive to write and a number is cheap, and it has nothing to do with either one’s birthday.

What the notation cannot say, and a solver can #

The repetition is not an accident of writing style. It is the shape of the object. A position reached by two different move orders is one position, and a game tree that treats it as two is doing extra work for no reason.

A position reached eleven ways is one position is the essay about that, and it treats the gap as a saving to be captured — the transposition table, memoisation, the identification of positions a solver must make before a search of any size will finish. The ratio there is a number in the hundreds or thousands, because a search tree is much deeper than a canonical form.

What this page adds is that the same gap is sitting in the notation, uncaptured, where nobody thinks to look for it. A solver stores one node per position; a written form stores one node per route. The two are doing the same arithmetic in opposite directions, and only one of them is allowed to notice.

There is a fix, and it is not available. Writing the form as a graph — naming a repeated subposition once and referring to it — is exactly what the reduction does not produce, because the reduction is defined on option lists and an option list has no way to point at anything. Two hundred and fifty-six ways to write twenty-two things counts the forms of each value and finds the class sizes wildly uneven; every one of those forms, canonical or not, is a tree.

The numbers, where the expectation should hold and does not #

If any family should behave, it is the numbers. A number’s canonical form is $\{x' \mid x''\}$, one option each way at most, so its width is two whatever its birthday — the fact how wide a form can get used to show that birthday cannot bound width. Running the argument the other way, a reader would expect the birthday to fix the size, since there is nothing else left to vary.

It does not.

Day two carries four numbers and two sizes. Day three carries eight numbers and three sizes: four symbols for $\pm 3$, six for $\pm\tfrac32$ and $\pm\tfrac14$, seven for $\pm\tfrac34$.

The reason is visible in the tree. An integer is a chain hanging off zero, so its size is its own magnitude plus one. A fraction is a chain on each side, and the two chains are the two numbers the simplicity rule put it between — so $\tfrac34 = \{\tfrac12 \mid 1\}$ pays for a half and for a one, and the half pays for a nought and a one of its own.

What survives of the expectation is one clause, and it is asserted in the code rather than described: the integers are the cheapest numbers of their day. On every day where both occur, every integer is written at fewer symbols than every fraction. That is the whole of it. Birthday does not fix size even here; it only ever bounded it.

Which values are expensive, and it is not the complicated ones #

The right-hand tail of the size distribution has a definite membership, and it is worth naming because a reader would guess the opposite.

Nothing about a value’s name marks it as expensive. The cheapest non-number on the day is $\ast$ at three symbols and the dearest is a six-option form at thirty-seven, and both are ordinary members of the same population — a reader shown the two expressions side by side would guess correctly, and a reader shown the two names would have nothing to go on.

The dearest values are neither the widest nor the ones with the most exotic names. They are the ones whose options are themselves wide — a value with six options, each of which has four of its own, pays for twenty-four grandchildren before anything below them is counted. Size is multiplicative down the levels where width is additive across one of them, which is the whole arithmetic of the gap.

A day of construction therefore does something to the writing that it does not do to the width. The mean width rose by 1.79 from day two to day three; the mean size rose from 5.2 to 17.1, better than threefold. If that rate held, day four would have a mean expression somewhere near fifty symbols and a maximum in the low hundreds — and a table of day-four values would not be a table anybody could print.

What the width is good for anyway #

None of this makes the width the wrong thing to minimise. It makes it the wrong thing to read as complexity, which is a different complaint and a milder one.

A canonical form’s Left options are pairwise incomparable, so the width is the size of two antichains in the order of values, and that is a statement with content: a wide form is a value with many genuinely different best moves, none preferable to another without knowing what else is on the board. Comparing two positions means playing a third, so establishing that width takes $w(w-1)$ searches, and the width is therefore the price of checking the form as well as a description of it.

The size is the price of transmitting it. Two different costs, both real, and the reduction was built to pay down the first.

There is a case where they part company sharply, and it is worth stating because it is the case a reader is most likely to meet. Adding a star to a value costs one option — width two becomes width four — and costs the expression the whole of its own sub-tree again, because $G\ast = \{G, G^L \mid G, G^R\}$ has $G$ written into both lists. In symbols that is close to doubling. In options it is adding two.

Smallest in what #

The canonical form is the smallest form of its value, and the definite article hides a choice. It is worth making the choice visible, because the whole of this page is what happens when the currency changes.

The reduction removes dominated options and bypasses reversible ones, and both operations remove options. So the quantity it minimises is the option count, and the theorem that the result is unique and minimal is a theorem about that count and nothing else. Nobody chose it as the interesting measure; it is the measure the operations happen to spend.

Three other currencies are available and the reduction optimises none of them. Symbols is what a reader pays, and the widest form is not the longest. Depth is how many levels the expression nests, and a narrow deep form can cost more than a wide shallow one. Distinct subpositions is what a graph representation pays, and the reduction is indifferent to whether an option is repeated.

That is not a criticism of canonical form. A normal form has to be canonical before it can be small, and uniqueness is what makes equality decidable by comparison — which is the property everything else on this site depends on. Minimality in options is a bonus rather than the point, and reading it as a claim of overall economy is the error this page exists to correct.

The practical consequence is that a reader wanting a short expression and a solver wanting a small object want different things, and neither of them wants exactly what the reduction supplies. The reduction supplies the unique form, and the rest of this anchor is about what that costs in every other unit.

Where the counting stops #

Three limits, and the second is the one that matters.

The pool is the values born by day three, which are as far as this evaluator reaches — the recursion this site cannot run is the account of why day four is not a matter of waiting longer. So every statement above is a statement about a population whose members are all written four levels deep or fewer, and nothing here bounds what happens when the levels multiply.

The second limit is that “symbols” has been counted as nodes, and a real printed expression pays for braces, commas and the names of the values at the leaves as well. Those are proportional to the node count for any fixed way of writing things down, which is why the node count is the right abstraction — but the constant is not one, and a figure quoting “thirty-seven symbols” is quoting thirty-seven positions.

The third is that none of this measures what a reader finds hard. The claim is about the length of the writing, not about comprehension, and the notation was the argument makes the case that the two came apart the moment brace notation was invented. A short expression full of nested braces can be far harder to read than a long one made of numbers.

It is worth being exact about what was and was not claimed, because the theorem is a good one and this page is not an objection to it.

The canonical form is unique, and that uniqueness is what makes equality a string comparison instead of a search — the single most useful fact in the subject. It is minimal in options, which is minimal in the currency the reduction spends and the currency comparison charges in. Neither of those is a claim about symbols, and nobody stated one.

What is worth noticing is how easily a reader supplies the missing claim anyway. Simplest is a word that arrives carrying every meaning of simple at once, and the theorem hands over exactly one of them. The two widest values of day three are the tidiest possible way of writing what they are worth, and each takes a full printed line.

Where the ladder goes next #

The reversibility anchor has three rungs to here: that bypassing is not a contraction, that its growth does not survive, and now that the canonical form is smallest in options and in no other currency.

The rung above measures how much of the cost this page counts is repetition, and the answer comes out as an equality rather than a ratio. The same position written once writes out day three’s canonical forms three ways: as trees it is 24,940 nodes; naming each distinct subposition once inside each form it is 10,102; naming each distinct subposition once across the whole day it is exactly 1,474.

That last figure is not a compression result and it is the one worth carrying. It is one node per value of the day, and it is one node per value because nothing appears inside a canonical form that is not itself a value of the day — the day is closed under taking options, so the set of subpositions and the set of values are the same set.

Which reframes everything this page counts. The object being written is a graph on 1,474 nodes, and the braces write a tree because a linear notation can only write a tree. The 24,940 is the size of an unrolling, the 10,102 is a partial re-rolling, and the gap between them and 1,474 is not waste in the notation but the difference between a graph and its unrolling — the same difference routes and positions measures inside a search.