How strict a rule can be

Euwe’s unending game answered a question about one rule: with two round trips and a ban on any block coming three times running, play can go on for ever. The rule was a particular one, though, and its number was not sacred. Three came from what an arbiter would count as obviously stuck, and nothing about the argument picks it out. So the natural question is how far the rule could have been tightened before the unending game disappeared. The answer turned out to depend on how many moves are available, in a way not finally settled until about eighty years after Euwe wrote, and the boundary falls at numbers that look arbitrary until it is seen how exactly they fit.

A rule of this kind needs a scale to be tightened along. The number of times a block may come running does the job, once it is allowed to be fractional. ABAB is the block AB twice, with exponent 2. ABABA is the same block two and a half times, with exponent 5/2. ABCAB is the block ABC once and two-thirds, with exponent 5/3. So a rule can forbid any stretch of play with exponent at least some number, and then lowering the number makes it stricter. The chess rule of 1929 sits at 3. Forbidding exponent 2 bans a block coming twice. Lower still and a rule starts to bite on blocks that only partly come round again.

Nobody would write a rule for players in fractions. The reason for looking at them is the same as the reason Zermelo’s paper is worth rereading for what it says about length: the boundary between “this rule ends every game” and “this rule allows a game to go for ever” is where the real structure is, and it does not fall on a whole number.

One table #

The experiment is cheap to run. Fix the number of available round trips, fix the exponent, and walk the tree of legal words, discarding any word whose last letter finishes a forbidden repeat. Either the tree dies at some length, which gives the longest legal game exactly, or it keeps growing until the search stops.

Reading across a row is reading the rule getting looser, and each row has a sharp edge in it. With two moves, every rule at exponent 2 or below ends the game by the third or fourth letter. The very next rule along, which bans only exponents strictly greater than 2, has words that do not stop, and these are the overlap-free words of Euwe’s construction. The boundary is at 2, and it falls between “exactly 2” and “more than 2”: a rule at the boundary kills everything, and a rule one infinitesimal notch looser leaves the words alive.

With three moves the same thing happens at 7/4. Forbid exponent 7/4 and above and the longest legal game is 38 letters. Forbid only exponents strictly greater than 7/4 and the words carry on. With four moves it happens at 7/5, where the longest legal game is 121 letters.

None of those numbers was available to anyone in 1929 or could have been guessed. The first is Thue’s. The second and the idea that a general pattern exists are Françoise Dejean’s, in a paper of 1972. Dejean conjectured that from five moves on, the boundary would fall at k/(k − 1), and Jean-Jacques Pansiot proved the four-letter case in 1984. The whole conjecture was finished only in the years around 2010, by a succession of authors treating larger and larger alphabets, with James Currie and Narad Rampersad and independently Michaël Rao closing the remaining cases. A statement about how strict a rule against repetition can be turned out to be a theorem it took thirty-eight years to prove.

That the boundary is sharp deserves some thought, and the distinction between a value and a process of finding it is close by, because a dash in that table and a number beside it are claims of very different kinds. The number is a fact that any reader could reproduce, and the computation is finished. The dash reports that the search stopped with words still alive, and by itself it establishes nothing about the next letter. What turns the marked dashes into results is a proof for each, since an infinite word with exactly that property has been constructed. A dash elsewhere in the table inherits its status from the marked one to its left, because any word obeying a stricter rule also obeys every looser one.

How the count dies #

A number at the end of a row suggests a tree that thins out steadily. That is not what happens, and the sharpest case is the three-letter rule at 7/4.

Nothing in the first thirty letters of that count suggests that the end is coming. It rises to the low hundreds and then oscillates in a narrow band, repeating the values 96, 102, 108, 114 over and over, which looks exactly like a population that has found a stable level. A person sampling the counts at lengths 15, 20, 25 and 30 would have concluded that the rule leaves about a hundred games at every length and that the words go on for ever. The count at length 37 is 60, at 38 it is 18 and at 39 it is nought.

That oscillation is itself evidence of how little freedom there is: with so few words alive at each length, most are extensions of a handful of rigid patterns. The band is not a sign of health. It is a small number of words all marching towards one wall, and they reach it together. The lesson for a search that has to stop somewhere is an uncomfortable one, since a run that stops at a length where a count has been flat for a long time has not learned anything about whether it will stay flat. The 4-letter rule is more extreme still: its count peaks at 3,360 and the words last to 121 letters before vanishing just as abruptly.

That also explains why a dash needs a proof. A rule whose count has held steady for a hundred letters, as the three-letter one did for twenty-five, has given no sign of its intentions.

From two moves to three #

The first entry in the row for three moves that is not a number is under the rule banning exponent 7/4 strictly, and everything to its right includes the most famous case, the rule banning a block twice running. Thue proved in 1906 that a word on three letters can go on for ever with no block twice in a row. The construction is a pleasant one because it is built directly out of the word that defeated the chess rule.

So the step from two moves to three, which looks like adding a new resource, is really a rereading of what was already there. Take the two-letter word and read off how many 1s lie between successive 0s. The three-letter word has no square, because a square in the counts would rebuild into a stretch of the two-letter word in which a block comes twice and then its first letter comes once more: an overlap, which the two-letter word does not contain. So the property a word has at exponent just above 2 on two letters pays for exponent 2 on three. This is a recurring trick in the subject, in which a stronger avoidance over a smaller alphabet is traded for a weaker one over a larger alphabet by a change of coding, and it has much the same flavour as the way every impartial game turns out to be a Nim heap in disguise: the rich object is found by reading a simple one correctly.

A square-free word on three letters would satisfy a rule stricter than any chess rule ever proposed. A game of three round trips can continue for ever with no sequence of moves ever repeated immediately, even once. If a rule committee had wanted to ban all immediate repetition of move sequences, Thue would have told it that the rule was still not enough. For a board with three independent shuffles, no rule of that kind ends a game.

A legal game can be a trap #

Existence of an unending word does not mean that a player who just avoids the forbidden repeats will find it. Some legal games have no legal continuation at all, and the very smallest case is on three moves.

ABACABA is a word mathematicians have met elsewhere. It is what is called a Zimin word, built by the recipe “wrap the previous word around a new letter”: A, then ABA, then ABACABA. Each stage has a centre that is a letter appearing nowhere else, and that structure means every prefix of the word is echoed by a suffix. It also means that each possible next letter closes off one of those echoes as a square, and with exactly three letters there are exactly three echoes to complete. The fact that the shortest trap has this tidy form on three letters is a piece of combinatorics. That it is the shortest trap in a game is what makes it useful later, because a player who wants the opponent to run out of moves needs to steer the play towards a word like this.

There are more traps as the words lengthen, and they are not rare.

The share in that table holds steady at around three per cent, and the count multiplies at about the rate of the words themselves. So the tree of square-free words is a tree in which a fixed fraction of the tips are dead at any given length, with others doomed but not yet dead, while unending paths thread through what is left. One way to see what this means for a player is to let one play without looking ahead.

The last line of that table is much the most interesting. With three moves and a ban on any immediate repetition the random player gets stuck after a median of 37 letters, and with one more move the same ban traps none of a thousand within a thousand letters. Adding one letter moves a rule from “a player needs a plan” to “a player scarcely needs to look”. There is a proof technique that speaks to this: Grytczuk, Kozik and Micek showed in 2013, by counting how much randomness a process can absorb, that a random word on four letters can be built by appending letters and erasing any square that appears, and that this gives a square-free word of any length. That process is allowed to erase and the player in the table is not, so the proof does not transfer, and the table should be read as a measurement of those runs and no more.

A wider search shows how much “none of a thousand” conceals. Four moves are not safe, and the trap is the next word of the same family.

The recipe has now produced the shortest trap twice, and the reason is the one given above: a word that echoes itself at lengths one, two, four and eight has one echo to complete for each letter available. In 4,000 further random games capped at 1,500 letters, five were stranded, at lengths 20, 221, 222, 574 and 730. So the safety in the table is a matter of rates. Dead ends on four moves are rare enough to miss in a thousand games and they do not go away.

A second boundary, in how much room there is #

The threshold in the first table is about whether any game goes on for ever. It is not the only boundary. Above the threshold, the rule leaves unending games, and it can leave few or many of them, and that changes as well.

Compare the first two rows with the third. Under the rule just past exponent 2 the count at length 80 is 724, and doubling the length from 40 to 80 multiplies it by about two and a half. That is what polynomial growth looks like, and it was proved polynomial by Restivo and Salemi in 1985: the overlap-free words are so constrained that each is essentially a copy of the Prouhet–Thue–Morse word with a little freedom at its two ends. The same is true at 7/3, with a larger polynomial. Just above 7/3 the counts multiply by seven or eight for every ten letters, and the growth is exponential. Karhumäki and Shallit proved in 2004 that this fraction is the exact point of transition, and also that the words below it are all built from the Prouhet–Thue–Morse word.

So on two moves a rule has three possible characters, with exact fractions between them. At exponent 2 and below no unending game exists. Between 2 and 7/3 there are unending games, but all of them are essentially Euwe’s word, and a player who wants to keep a game going has almost no choice at any stage. Above 7/3 the player has real choice, exponentially many games to pick from. The German rule at 3 is comfortably in the third region, so what Euwe found was not a lone exception. His word was the most rigid example of something that the rule leaves widely available.

This also reframes what the proof of the overlap property was doing. It looked like an argument that one word has a property. Seen from this table it describes a whole region: the region between 2 and 7/3 is a place where the descent argument controls everything, since every long word there breaks into blocks of the substitution all the way down. Above 7/3 the descent no longer controls anything, and that is presumably why it was harder for anybody to see the large families first. The rigid word, the one with a proof attached, is the one that was discovered four times over.

The conventions underneath #

A word here is a sequence of round trips, so it describes play in which the players alternate letters of a shared record rather than individual moves. Exponents are computed on the word as it stands, counted over every suffix when the last letter is added, which is enough because any earlier suffix was checked when its own last letter was. A rule “at” a fraction bans repeats reaching that fraction, and “over” a fraction bans only those going past it. The table’s two kinds of column differ only in that one word of the definition, and at the boundary the whole difference between ended and unending lies there.

The counts are exact for words of every length up to the point where each stopped: first letter fixed, multiplied by the number of letters, which the symmetry between letters allows. Where a row ends in a dash the search stopped at length 60 for two or three moves and at 130 for four, or at 50,000 live words, whichever came first. The theorems cited supply the rest.

What the table cannot show #

That any of this ends real chess games. Actual repetition rules count positions now, and the word’s letters are a schematic of two independent round trips. A board rarely offers that freedom for long, because a pawn move or a capture changes everything. The table shows what a rule on sequences of play could and could not achieve, as a matter of logic.

That a dash is a theorem. A dash records only that words were alive when the search stopped. Dejean’s conjecture and its proof supply the marked dashes, and the entries to their right follow from those. A reader should not take the search in the figure as evidence for the theorem any more than the plateau at length 30 was evidence of its opposite.

Why the fractions are those fractions. The value k/(k − 1) has a short explanation as a lower limit. Ban that exponent and two equal letters less than k apart are forbidden, so any k consecutive letters are all different, so each new letter is forced to be the one k places back, and the word becomes periodic, which the rule also bans. On two letters this gives exactly 2. The values at three and four moves, 7/4 and 7/5, sit above this limit, and nothing here explains by how much. They come out of the exhaustive search with no story attached, which is a common way of learning that a small case is special.

That this is the only scale. A rule can be stated in other ways, for instance by a limit on how long a repeated block must be before it counts. A variant of that kind has its own thresholds, and none of them appears here. The rule in the table also treats every round trip as equally available at every moment, which a real board with its irreversible moves does not.

Still open: what happens when somebody wants the rule to fire #

All of these words are cooperative. A dash says a word exists and nothing about whether a player can stay on it, and the existence of a trap like ABACABA suggests a player might not be able to. Nobody in the table has an opponent. Give the letters to two players in turn, each hoping that the other runs out of legal letters first, and the question is no longer about the tree of words at all but about who can steer it. The theorem about existence then says almost nothing. The rule that let Euwe’s game run for ever may not protect anyone who is playing against someone else.