The day a number is born

The simplicity rule says a game whose options are numbers is worth the simplest number strictly between them. It is a complete answer and it leaves one word undefined.

Simplest does not mean smallest, and it does not mean the one with the smallest denominator, although that is a good approximation to it. It means born earliest, and birthdays are a construction rather than a convention: they come out of the same recursion as everything else here, and running the construction is the only way to find out what the word means.

So this essay runs the construction rather than describing it, and it starts where the construction does, which is with nothing.

Everything below is that picture continued. Nothing is added to the rule and nothing is chosen by hand; each figure is the previous one with one more row, and the row is filled by asking a single question in each gap.

The construction #

Day zero has one position: $\{\ |\ \}$, in which neither player can move. It is worth $0$, and nothing else exists yet.

Day one is everything that can be built with options drawn from day zero. There are four such games: $\{\ |\ \}$ again, $\{0 \mid\ \}$, $\{\ \mid 0\}$ and $\{0 \mid 0\}$. The first is $0$; the second is $1$ and the third is $-1$; the fourth is $\ast$, which is not a number at all and is set aside here.

Day two is everything buildable from day-one games, and so on. A game’s birthday is the first day on which something equal to it appears.

The numbers that arrive follow a pattern that is obvious once seen and is not obvious in advance. On each day, the new numbers are exactly the simplest numbers in the gaps left by the old ones — one strictly between each adjacent pair, one below everything and one above everything.

$$0 \;\to\; \pm 1 \;\to\; \pm\tfrac12, \pm 2 \;\to\; \pm\tfrac14, \pm\tfrac34, \pm 3 \;\to\; \ldots$$

Two things happen at once every day: the range doubles outward by one integer at each end, and every existing gap is halved.

One day of that is enough to see both motions, and it is worth looking at alone before the picture gets crowded. After day one the numbers are $-1$, $0$ and $1$; they leave four gaps — one below everything, one above everything, and one between each adjacent pair — so day two produces exactly four numbers.

Counting the gaps is what makes the growth predictable. Numbers on the line leave one more gap than there are numbers, so a day that starts with $k$ ends with $2k + 1$ — and starting from one, the totals are 1, 3, 7, 15, 31.

Only the dyadic rationals #

Follow the halving and the answer is forced. A gap between two numbers born by day $n$ is filled by the number in the middle of it, so every denominator that ever appears is a power of two.

That means $\tfrac13$ is never born. Not on day ten, not on day a thousand — it has no finite birthday at all, because at every stage it lies strictly inside a gap and the number that fills that gap is a dyadic rational nearer to one end.

This is worth pausing on. The construction was not designed to produce fractions with powers of two underneath; it was designed to answer “who wins”, and the dyadic rationals arrived as a consequence of positions being finite and options being lists.

One more day is enough to watch the denominators appear, and to see that they appear in a fixed order rather than all at once.

That ordering is what forces the powers of two. Each gap has dyadic ends by the time it is filled, the simplest number strictly inside a gap with dyadic ends is another dyadic, and there is never a step whose answer could be anything else. The rule that picks each arrival is the simplicity rule, and the whole content of the word simplest in it is that the earliest-born number in a gap wins rather than the average of the two ends.

Why the midpoint is the wrong answer #

The temptation to average is strong enough to be worth killing properly, because the two rules agree often enough to look interchangeable.

Consider $\{0 \mid 2\}$. Left can move to a position worth nothing, Right to one worth two, and Right’s option is better for Left than Left’s own — which is the signature of a position that settles down rather than one worth fighting over. The midpoint is $1$, and the value is $1$, and nothing has been learned.

Now consider $\{-5 \mid 5\}$. The midpoint is $0$ and the value is $0$, and again nothing has been learned. But the reason is different: $0$ is the earliest-born number in that interval, and it happens to sit in the middle. Shift the interval to $\{-5 \mid 7\}$ and the two rules part company. The midpoint is $1$; the value is still $0$, because zero is in the gap and zero was born first.

The general shape: whenever the interval contains an integer, the value is an integer, and it is the one closest to zero among those in the interval. Only when the interval contains no integer at all does the construction start halving, and then it takes the coarsest halving that lands inside.

$$\left\{ \tfrac{5}{16} \;\middle|\; \tfrac{11}{16} \right\} = \tfrac12, \qquad \left\{ \tfrac{9}{16} \;\middle|\; \tfrac{11}{16} \right\} = \tfrac58.$$

Both of those intervals have width $\tfrac18$, and their values have denominators $2$ and $8$. Width has nothing to do with it; position does. That is what an ordering by birthday looks like from the inside, and it is why “simplest” cannot be replaced by any measure of size.

There is a second half to what a birthday is a property of, and it is worth stating before the word is used any further. A position and the same position with an option no player would ever take removed are worth the same, so they have the same birthday — reducing a form to its canonical one never changes what it is worth. A birthday is therefore a fact about the value, not about any particular drawing of it, and asking when a position was born is a question with no answer until the position has been reduced.

What a birthday is worth knowing #

Birthdays are not decoration; they carry information no other measure of a position does.

A game of birthday $n$ can be written with options of birthday less than $n$, so it has a description of bounded depth. That bounds how far a recursion has to go, which is what makes an exact evaluator possible at all, and it bounds how many distinct values can exist by a given day. The bound is finite and it is finite in a way that makes the word almost useless: a game born by day $n$ has two option lists drawn from the games born by day $n-1$, so if there are $k$ of those there are at most $4^k$ of the next. Counting them by construction gives one game by day zero, four by day one and 256 by day two, and the day after that is $4^{256}$ — a number with 155 digits, describing the third day of a construction that started from nothing.

More usefully, birthday is a complexity of the value rather than of the position. A Hackenbush string of forty edges can be worth $\tfrac12$, and its birthday is two whatever the picture looks like. Two positions with the same value have the same birthday by definition, because birthday is a property of what a game is worth and not of how it is drawn.

Both of those are statements about depth, which is the quantity the picture measures and the only one it measures. So it is worth taking the construction as far as it can be drawn legibly and looking at what depth costs.

Read down that figure rather than across it and the second reading appears. A number sits at a definite depth, its ancestors are the numbers whose gaps it was born inside, and simplest is a statement about that depth. The line the marks sit on carries none of that information, which is the subject of a section below.

What the solver computed, and how #

The tree in the first figure is generated, not typed. Each day’s arrivals come from asking the simplicity rule for the value of every gap.

The day-zero list is $[0]$. To produce day $n$ from day $n-1$: sort what exists, then for each adjacent pair call simplestBetween on it, and separately call it on the gap below everything and the gap above everything. simplestBetween is the same function the essays about the simplicity rule and about canonical forms use, and it works by looking for an integer in the interval first and halving down from there only when there is none.

That last detail is the mechanism, and it is worth stating because it is what makes the rule an ordering rather than a computation on fractions. Between $\tfrac{5}{16}$ and $\tfrac{11}{16}$ the simplest number is $\tfrac12$, not $\tfrac{8}{16}$ — which is the same number, but the point is that the search finds it by asking for the coarsest halving that lands inside, not by averaging.

The independent check the site’s gate runs is on the other side of the same fact. Every blue-red Hackenbush string is evaluated twice: once by the game recursion, and once by reading the string as a binary expansion. The binary reading is a statement about dyadic rationals and nothing else, so if a string’s value ever came out as something with a denominator that was not a power of two, the two routes would disagree and the figure would refuse to draw. Every string up to six edges is checked, every time.

A picture with the birthdays in it #

Hackenbush is the place where the construction stops being abstract, because a blue-red string is a numeral and the numeral can be read off.

Read a string as follows. The leading run of one colour is an integer, one per edge, positive for blue. After the first colour change each edge contributes half as much as the one before it, signed by its colour. So LLR is $2 - \tfrac12 = \tfrac32$, and LRL is $1 - \tfrac12 + \tfrac14 = \tfrac34$.

The correspondence with birthdays is exact and it is the reason the picture is worth drawing. A number born on day $n$ is reachable by a string of $n$ edges and no shorter one. The integers, born early, are short strings of one colour; the fractions with large denominators, born late, need long alternating tails. The construction’s “each day halves every gap” and the string’s “each edge is worth half the last” are the same statement.

What the picture cannot show is why $\tfrac13$ is missing. Every position on the line is occupied by some string and the gaps look like they would fill in if the strings were allowed to be longer — and they do fill in, densely, and never at $\tfrac13$. Density and completeness are different properties, and a picture of a line shows the first and says nothing about the second.

Why the tree is a tree and not a line #

The construction is drawn as a tree and the objects it produces sit on a line, and the relation between those two pictures is worth stating, because it is the whole of what simplest is doing.

The dyadic rationals are densely ordered: between any two of them lie infinitely many others, so nothing about the line distinguishes one from its neighbours. The tree imposes an order the line does not have — each number has a definite parent, a definite pair of ancestors bracketing it, and a definite depth — and every use of the word simplest on this site is a use of that second structure rather than of the first.

That is why the simplicity rule can be stated at all. The simplest number strictly between two numbers has no meaning on the line, where there is no smallest, no first, and no canonical choice among infinitely many candidates. On the tree it names exactly one object: the unique number of least depth in the open interval, and it is unique because the two numbers of any given depth in an interval would have their common ancestor in the interval too, which is shallower.

So the tree is not an aid to drawing the numbers; it is the object the theory works in, and the line is a projection of it that loses the only property the rules use. A reader who thinks of a value as a point on a line will find every “simplest” in this subject arbitrary, and every one of them is forced.

It also says why the days are the right unit. A day is a level of the tree, so born by day $n$ is a statement about depth rather than about size — which is what lets the same word do duty for numbers, for nimbers, and for the switches and infinitesimals that sit nowhere on the line at all.

Where the model stops #

Finite birthdays are a restriction, and it is the whole restriction. Everything on this site has a finite birthday because every position drawn here has finitely many options and finite depth. Drop that and the construction keeps going — but into somewhere very different, and nothing here follows it.

Birthday is not depth of play. A game of birthday three can take a hundred moves to finish, and a game that ends in two moves can have a large birthday. The recursion that produces birthdays runs on values, and the number of moves left in a position is not a property of its value at all.

Not everything born is a number. Star is born on day one, alongside $1$ and $-1$. Up and down are born on day two. The construction produces games, and the numbers are the subset of them that happen to be totally ordered with each other — which is not most of them.

The convention is normal play. As everywhere here. Under misère play the base case flips, the simplicity rule has nothing to stand on, and none of this construction survives.

What the figures above leave out is everything born in the same days that is not a number. Up appears on day two, alongside a half, and it is not between any two numbers, not comparable with most of them, and not something a line has room for. The construction makes numbers and non-numbers indifferently, and the pictures here draw the numbers because those are the ones that fit on a line — which is a fact about the drawing rather than about the day.

Where a birthday actually gets used #

A construction that only explained a word would be worth a paragraph. Birthdays earn their place because two of the subject’s working results are statements about them, and neither can be phrased without the idea.

The first is the simplicity rule itself, which is not a definition but a theorem: the value of $\{a \mid b\}$ with $a < b$ both numbers is the earliest-born number strictly between them. The proof is a comparison. Let $x$ be that number; showing $\{a \mid b\} = x$ means showing the difference is a second-player win, and the argument turns on the fact that every option available in the difference leads to a number born earlier than $x$ and therefore outside the interval, where the inequality is already known. Without an ordering by birthday there is no induction to run.

The second is a fact about sums. Two games whose birthdays are $m$ and $n$ have a sum whose birthday is at most $m + n$, and that bound is what stops the value of a position built from many small parts from being unboundedly complicated. It is why a sum of a dozen small components is still something an evaluator can name.

Both statements are about which values are cheap and which are expensive, and cheapness here is exactly earliness. It is not a metaphor for anything about the position — a long, ugly, hard-to-draw game can be worth a number born on day one, and frequently is.

The generalisation, and where it goes #

The construction does not stop on day $n$ for any $n$, and the interesting thing is what happens if it is allowed to keep going.

Permit a game to have infinitely many options and run the same recursion past every finite day. On the first infinite day, the gap between all the integers and nothing above them is filled — producing an object greater than every integer. The gap between $0$ and every positive dyadic rational is filled too, producing something positive and smaller than all of them.

The result is a number system containing the reals, the ordinals, and a great deal besides, all built from the same two lines that produced $\tfrac12$ here. Conway called them the surreal numbers, and the fact that they and the theory of games are the same construction is not an analogy — it is one recursion with two readings.

That is why the restriction to finite birthdays matters and why it is stated rather than assumed. Everything on this site lives on the finite days. The construction is not finite, and the reason the essays stay where they do is that an exact evaluator can only visit positions it can enumerate.

Who found it, and when #

The construction is Conway’s, from around 1970, and it is the opening of On Numbers and Games — the first chapter creates zero from nothing and everything else follows from two rules.

The order of discovery was the reverse of the order of presentation. Conway arrived at the construction while analysing Go endgames with Elwyn Berlekamp, noticed that the values behaved like numbers, and found that the numbers he was getting were a construction of the real numbers he had not seen before. The book presents it the other way round because that is the shorter road.

Donald Knuth wrote Surreal Numbers in 1974, a novella in which two characters derive the construction from a stone tablet, and it remains the gentlest introduction to the day-by-day version described here.

The ladder from here #

This anchor began with the simplicity rule — a rule for evaluating a position whose options are numbers. This rung says what its central word means, and finds that the answer is a construction rather than a definition. Five rungs stand above it, in two directions.

Numbers avoid numbers turns birthdays from a classification into a piece of strategy: in a position with a number in it and anything else, the number is never the right move, and that is a theorem rather than advice. The numbers came out of the game then corrects the order everything above is presented in — the construction is always taught numbers first and games second, and Conway arrived at it from positions, which is why the definition quantifies over sets of previously built objects rather than over cuts, and why it produces a genuinely different collection at every finite stage.

The recursion this site cannot run removes the stopping condition and reaches the infinite days: $\omega$, its reciprocal, and one third — none of which this site’s evaluator can represent, because it interns a position from a finite list of options.

The other two rungs take the birthday as a measure and test it. How old a value is shows that a form’s depth bounds the birthday of the value inside it and that canonicalisation attains the bound on all 22 day-two values, with twenty-four of the 256 forms older than what they are worth — and it is the same reduction that brings day three within reach at all, taking the option sets a side from four million to 98. The birthday of a sum bounds the birthday of $G + H$ by $m + n$, finds it exact 163 times over 231 pairs, and finds the slack meaningful rather than noisy: every pair missing the bound by three days or more has a sum that is a number or a nimber, so the shortfall measures how much cancelled.

What this rung establishes is the vocabulary. Every later use of the word “simplest” on this site means born earliest, and that is a fact about a tree rather than about a fraction.