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.

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.

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.

The gap between the two marks in that figure is the whole content of the word “simplest”. The midpoint is an arithmetic answer to the question and it is wrong; the earliest-born number in the gap is the right one, and the two agree only by coincidence.

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.

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.

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 build would stop. Every string up to six edges is checked on every build.

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.

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.

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.

Later rungs: the proof that day $n$ contains exactly the dyadic rationals with denominator $2^{n-1}$ in a bounded range, and nothing else. Canonical forms, and why a value’s birthday is the birthday of its canonical form. The theorem that says a number is never the right move, which turns birthdays from a classification into a piece of strategy. And the infinite days, where the same recursion stops being about games at all.

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.