The birthday of a sum

A board that has broken into six independent fights is a sum of six games, and each of the six is small. What stops the total from being complicated out of all proportion to its parts?

The answer is a bound on birthdays. If $G$ is born on day $m$ and $H$ on day $n$, then $G + H$ is born by day $m + n$ — and since a day of construction is a bound on how much structure a value can carry, that sentence is what keeps a decomposed board tractable at all.

The bound was never in doubt — it is an induction, and one this site’s whole recursion rests on. What was not measured is how much room there is underneath it, and the answer turns out to be very little, except where something cancels.

Why the bound is true #

The argument is two lines and worth having, because it explains both the tightness and the slack.

A value born on day $m$ has a form whose options are all born by day $m - 1$. The disjunctive sum $G + H$ has options $G^L + H$ and $G + H^L$ on the left, and likewise on the right — a move in one part, with the other part unchanged. Each of those is a sum of something born by day $m-1$ with something born by day $n$, or the reverse.

So by induction the options of $G + H$ are born by day $m + n - 1$, and the sum itself is born by day $m + n$ at the latest. Nothing in the argument tries to be sharp; it is a bound got by counting levels, and the levels are the only thing it counts.

The numbers are the family where a day is completely informative, and they are also where the word day acquires its arithmetic: every number the construction reaches in finitely many days is a dyadic rational, a fraction with a power of two underneath, and the day it is born is the number of halvings its denominator records. Nothing in the recursion mentions halving.

The word at the latest is doing real work. The bound gives a form written $m + n$ levels deep, and the birthday is the depth of the canonical form, which may be shallower. Everything below is about the gap between those two.

How often it is exact #

Of the 231 pairs, 163 attain the bound. Restricting to the 171 pairs where both parts were themselves born on day two — the hardest case, and the one a reader would guess is the loosest — 119 of the sums are born on day four exactly.

That is the finding to sit with. A sum of two day-two values is usually as complicated as anything of that shape can be. Adding does not simplify; it compounds, and it compounds all the way to the bound in about seven cases out of ten.

It is worth noticing how strong that is as a statement about a bound. Most bounds in this subject are loose in the direction that matters — the birthday bounds the width of a canonical form and the bound is enormously slack, since every number has width two whatever day it was born on. This one is not. It is a bound obtained by counting levels in the crudest possible way, with no attempt at sharpness anywhere in the induction, and it lands on the nose more often than not.

The reason is that the two option lists of a sum are built by moving in one part and leaving the other alone, so almost every option of $G + H$ genuinely does carry the full structure of both. For the depth to fall, some option has to become dominated or reversible against an option it would not have met inside either part on its own — and that requires a coincidence between the two halves rather than anything either half does by itself.

Why the compounding matters is what a day costs in population rather than in levels. The values do not merely get more numerous with each day; they get more numerous much faster than the numbers do — 1, 4, 22 and then 1,474 by day three, against fifteen numbers — so a sum of two day-two values living on day four is living in a population nothing on this site can enumerate.

The practical reading is uncomfortable. The sum is the object argues that decomposition is what makes a board tractable, and it is — as a search, because six small trees are enormously cheaper to walk than one large one. But as a value, the total of six day-two components is an object with a birthday of up to twelve, and no evaluator here reaches day four.

Where the slack is #

Sixty-eight pairs come in under the bound, and they do not come in a little. The distribution is thirty-six at one day early, sixteen at two, six at three and ten at four — a long tail, not a taper.

Reading down the sum column is the whole of the explanation. $-2 + 2 = 0$. $\tfrac12 + \tfrac12 = 1$. $\uparrow + \downarrow = 0$. $\ast 2 + \ast 2 = 0$. $\{1 \mid \ast\} + \{\ast \mid -1\} = 0$.

Every one of them collapsed. Ten of the sixteen are exact negatives — every game has a negative, and adding one to a position gives a second-player win, which is born on day nought. Two more are fractions adding to a whole number: $\tfrac12 + \tfrac12 = 1$ and $-\tfrac12 + -\tfrac12 = -1$. Two are pairs of switches adding to a number, which is the mean value theorem appearing in miniature: $\{0 \mid -1\} + \{0 \mid -1\} = -1$ and $\{1 \mid 0\} + \{1 \mid 0\} = 1$, two copies of a fight settling at exactly twice its mean. The last two are the section below.

There is a count worth keeping apart from that ten. Twelve of the 231 pairs on the whole page add to nought, and only ten of them are in this table: $\ast + \ast$ and $-1 + 1$ also cancel outright, and their bound is two rather than four, so their slack is two and they fall outside it. Cancellation is what produces the widest slack and it is not the same set as the widest slack.

The two that are neither #

$\uparrow + \downarrow\!\ast = \ast$ and $\downarrow + \uparrow\!\ast = \ast$ are the pairs a description in terms of cancellation nearly misses, and they are worth a paragraph because they are the reason the assertion in the code says number or nimber rather than zero.

Neither pair cancels to nothing. The up and the down annihilate and a star is left standing, which is exactly what the arithmetic of the infinitesimals says should happen: $\downarrow\!\ast = \downarrow + \ast$, so the sum is $\uparrow + \downarrow + \ast$, and the first two are negatives of each other.

So the honest statement is not the slack measures cancellation but the slack measures how much of the two positions annihilated. Total annihilation gives four days; annihilation leaving a star gives three; annihilation leaving a number gives three.

The smallest case: adding a star #

The cheapest thing that can be added to a position is a star, which is born on day one. The bound therefore says that adding one costs at most a day, and running that over the twenty-two values of day two makes the whole pattern visible in twenty-two rows rather than 231.

Fifteen of the twenty-two go up by exactly a day, which is the bound attained. Four are unchanged. And three go down: $\ast + \ast = 0$, which falls from day one to day nought, and $1\ast + \ast = 1$ and $-1\ast + \ast = -1$, which fall from day two to day one.

The four unchanged rows are the interesting ones, because they are the class where the star is already inside. $\uparrow + \ast = \uparrow\!\ast$ stays on day two; so does $\downarrow\!\ast + \ast = \downarrow$. A star added to a position that already carries one either cancels it or is absorbed, and either way the level count does not grow.

That is worth carrying because a star is the most commonly added thing in the subject. Every impartial component contributes one, every position with a spare move in it carries one, and the arithmetic above says that the cost of carrying one is a day exactly when the position was not already carrying one.

What the bound does not determine #

The bound is a bound and nothing else, and the counts make that precise in a way a reader can use.

Given only the birthdays $m$ and $n$, the birthday of the sum can be anything from nought to $m+n$. On the 171 pairs with $m = n = 2$ the sums are born on days nought, one, two, three and four — every possibility occurs, with counts of ten, six, eight, twenty-eight and 119. So the birthday of a sum is not a function of the birthdays of its parts, and knowing them tells a reader the ceiling and nothing more.

That puts the birthday in the same class as the temperature and the outcome class rather than in the class of the value. Values add. Outcomes do not add, temperatures do not add, and birthdays do not add either — they are bounded by the total, which is one step better than an outcome class manages and one step short of being useful.

The birthday behaves like a size #

Putting the birthday beside the other quantities that “do not add” undersells it, because it fails to add in a completely different way from the others, and the difference has a name.

Collect what is true of it:

• $b(0) = 0$, and nothing else has birthday nought.
• $b(-G) = b(G)$, since negating mirrors a form and mirroring changes no depth.
• $b(G + H) \leq b(G) + b(H)$, which is this page’s bound.

Those three are the axioms of a norm. So the birthday makes the short games a normed group, and it is the only quantity on this site that does — a genuine measure of how big a value is, in the sense that a length is a measure of how big a thing is.

That has a consequence worth stating, because it gives the values a shape nothing else here provides. Define the distance between two values as the birthday of their difference, $d(G, H) = b(G - H)$. It is nought exactly when $G = H$, it is symmetric because negation preserves birthdays, and it satisfies the triangle inequality because

$$b(G - K) \;=\; b\bigl((G - H) + (H - K)\bigr) \;\leq\; b(G - H) + b(H - K).$$

So the short games are a metric space, with the distance being how many days of construction separate two values. The 231 measurements above are measurements in that metric: the bound being attained 163 times says the space is close to flat, and the sixteen wide-slack pairs are the places where two values are much nearer than their sizes suggest — which is exactly what cancellation is, seen geometrically.

None of that is an argument this page is entitled to make without running it, since the triangle inequality is derived from a bound whose whole interest is how often it is slack.

The distance table is worth a second look, because it says something the axioms do not. The space has a diameter of four and most of it sits at the far end: of the 484 ordered pairs, 234 are four days apart and only 26 are one. A metric in which almost every pair is at the maximum distance is a metric that discriminates badly, which is the geometric statement of this page’s finding — sums compound, so differences are large, and closeness is the exception that needs a cancellation to produce it.

Which is the opposite shape from the temperature #

Setting the two bounds side by side is the sharpest way to say what kind of quantity each is.

$$b(G + H) \;\leq\; b(G) + b(H) \qquad\qquad t(G + H) \;\leq\; \max\bigl(t(G),\, t(H)\bigr)$$

The first has a sum on the right and the second has a maximum. A sum on the right is the ordinary triangle inequality — the shape a length obeys, where quantities accumulate. A maximum on the right is the ultrametric inequality, the shape a valuation obeys, where the largest term swallows the rest and nothing accumulates.

And the two behave exactly as those shapes predict.

A subadditive quantity attains its bound generically, because accumulation is the default and a shortfall needs a coincidence — which is this page’s seven-in-ten, with the shortfalls being annihilations.

An ultrametric quantity attains its bound whenever its arguments differ, and can only fall short when they tie — which is what the temperature figures show, with the collapse happening between components of equal temperature.

So “birthdays do not add” and “temperatures do not add” are two sentences about two genuinely different failures, and lumping them together with “outcomes do not add” flattens the most informative thing about either. The birthday is a size that fails to be exactly additive. The temperature was never a size at all.

That also says which of the three quantities a reader should expect to be able to reason with. A norm supports approximation: two values a small distance apart behave similarly, sums are bounded by sums, and a board’s total is controlled by its parts. A valuation supports domination: the hottest part decides and the rest are invisible. An outcome class supports neither, which is why the value had to be invented.

What it costs a solver #

There is a practical consequence and it is the reason the bound is worth measuring rather than merely quoting.

A solver that decomposes a board is doing two different things with the parts, and the birthday bound prices them differently. Deciding who wins a sum needs only the outcome of the total, and the total’s tree is the product of the parts’ trees — expensive, but the decomposition is what makes it affordable, since six trees walked separately beat one tree of their product.

Computing the value of the sum is the other thing, and there the bound bites. The value of a six-part board is an object with a birthday of up to twelve, and its canonical form has to be written down before anything can be compared against it.

Knowing who wins, and knowing what it is worth prices those two computations against each other and finds a ratio running from 1.3 to 279. The birthday bound is where part of that ratio comes from: the winner of a sum is a bit, and the value of a sum is a tree whose depth is the sum of the parts’ depths.

The 163 pairs that attain the bound are therefore not a curiosity. They are the ordinary case, and the ordinary case is the expensive one.

What the census cannot reach #

The pool is the twenty-two values born by day two, which caps every bound in the census at four and every sum at day four. That is the limit and it is a hard one: a pair of day-three values has a sum on day six, and the recursion this site cannot run is the account of why day four is already out of reach as an enumeration.

So the sharp question — does the proportion attaining the bound rise as the parts get older? — is not answered here. There is an argument on each side. The bound gets harder to attain as the levels multiply, which suggests a fall; and the values get more numerous much faster than they get simpler, which suggests that a random pair has less and less chance of cancelling and so a rise. The census cannot decide between them.

What can be said, and is worth saying because it is the direction a reader will guess wrong, is that neither argument is about the bound. The bound is proved and it is not going to move. The open question is entirely about the proportion, which is a statement about how often two arbitrary values happen to interact, and that is the kind of quantity that has been surprising on this site before — how rare it is to be bigger found the proportions of the four comparison relations the wrong way round from what a reader expects, on the same population.

The second limit is that unordered pairs are not sums of three. A board in six parts is six-fold, the bound accumulates, and whether the slack accumulates with it is a different measurement. The one thing that transfers immediately is the negatives: a board carrying a component and its mirror image sheds both, whatever else is on it, which is what can be struck out.

The convention, named #

Normal play, and the sum is the disjunctive sum: a move is made in exactly one component, and the player unable to move anywhere loses. Under the conjunctive rule — move in every component at once — values do not add at all, so a birthday bound for a sum is a statement about one specific operation and does not survive being asked of another.

Every birthday above is the depth of a canonical form, computed by reducing and then measuring. The distinction between that and the depth of the form as written is exactly what makes the slack possible: the bound is a statement about a form, and the birthday is a statement about a value.

Where the ladder goes next #

The numbers anchor has run from the simplicity rule through the number tree, the strategy, the history and the boundary, to how old a value is and now to the sum.

The rung above is the third measurement that essay named and this one has not made: birthdays under a bounded pool. Every count here is over forms whose options come from a fixed day. Bounding instead the number of options, or the size of the written form, gives a different census and a different diagonal — and it is the version that would say something about positions a player might actually meet, where a board with forty pieces is routinely worth a value born on day two.

Two neighbours are worth the trip. How old a value is is where the birthday is established as a measure and shown not to bound the width; this page is the same measure taken through the one operation the subject cares about. And the values that are their own negatives is the family for which the collapse in the table above happens with a single copy rather than with two.