Almost every automaton can be reset with a short word

Picture a conveyor belt carrying identical parts, each lying at a different angle. Before they can be packed they all need to face the same way. One option is to fit sensors that read each part’s orientation and a mechanism that nudges each one individually. Another is to bolt a fixed series of obstacles along the belt, arranged so that whatever angle a part arrives at, after bumping through them it ends up in the same position as every other part. The second solution has no sensors and no decisions.

It works on everything that comes past.

That series of obstacles is what Perarnau calls a synchronizing word. “It’s a sequence that lets you regain control of a system, in much the same way we reset a computer when it freezes,” he says. The system in question is a deterministic finite automaton, one of the most basic models of computation, which he describes as a much simpler cousin of a Turing machine. It has a set of states and, for each letter of an alphabet (say a and b), a rule sending every state to another. Feed it a word such as abba and it hops from state to state, one letter at a time. A synchronizing word is one that, wherever the automaton starts, always ends in the same place.

Not every automaton has one, if each letter merely permutes the states, nothing ever collapses.

For those that do, the question is how long the shortest such word has to be. In the 1960s Černý conjectured that (n−1)² letters always suffice, where n is the number of states, and built a family of automata that need exactly that many. In 1982 Peter Frankl and Jean-Éric Pin proved that roughly n³/6 letters are always enough. “Despite being one of the central problems in automata theory, progress since then has been very modest,” Perarnau says.

Four decades on, the best known bound is still cubic.

Perarnau and Chapuy took a different route. Theoretical computer science distinguishes between what a problem costs on the worst possible input and what it costs on an average one. In many settings the inputs that make a problem expensive form an extremely small set: if you pick one at random, you are unlikely to hit them. Peter Cameron asked what this meant for synchronization: take an automaton uniformly at random among all n²ⁿ possible ones and see what happens. Mikhail Berlinkov and Cyril Nicaud, working independently, showed that such an automaton is almost always synchronizable, and Nicaud found a synchronizing word of length about n log³ n.

The new paper cuts that to the order of √n, up to a logarithmic factor. “Our work quantifies that result: they can be synchronised with a word of length roughly n^1/2, which is believed to be optimal,” Perarnau says. Numerical experiments had placed the exponent somewhere between 0.5 and 0.56 without being able to decide.

Trees, and one word to rule them all

The idea underneath the proof starts with a single letter. Fix one letter and follow it, every state is sent to exactly one other, so the letter defines a function from the set of states to itself. Draw an arrow from each state to its image and the picture that emerges is a collection of cycles with branches hanging off them. A function is a (rooted) tree if there is only one cycle, and it is a loop (one-point cycle). Cayley’s formula, from the nineteenth century, says there are nⁿ⁻¹ rooted labelled trees on n vertices. There are nⁿ possible functions from n states to themselves, so a random one is a tree with probability exactly 1/n.

“Trees play the role that synchronization needs, the only cycle ensures we can always reach the same point from everywhere, and the fact that it is a loop guarantees we won’t get trapped in orbits.”

Guillem Perarnau

With one letter that would already be the whole answer.

One letter, though, is not a very interesting alphabet, a tree turns up with probability 1/n, so almost never. With two letters the possibilities grow exponentially, and the question becomes whether some short word w, read as a single instruction, makes the automaton behave like a tree. Chapuy and Perarnau call these w-trees, and their main structural theorem says that a random automaton is, almost always, a w-tree for some word w of length log₂ n. The √n scale then comes from the typical height of random trees. The authors prove the corresponding height bound for the w-trees in question: repeat w enough times and every state is funnelled into the same root.

Turning the idea into a proof is where the 55 pages go, and the obstacle has a familiar name. “The birthday paradox is one of the most popular problems in probability, for being so simple and at the same time so counterintuitive,” Perarnau says. Having 23 people in a room, it’s more likely than not that two share their birthday; in a random automaton, following a path of length √n log n, it’s more likely than not that you pass through the same state twice. Those repeated visits make different paths interfere with one another and can generate extra cycles in the structure the proof is trying to turn into a tree. Each possible pattern of interference has to be controlled separately. “In our proof we use the ideas behind this paradox to control the probability of creating a w-tree.” The same ideas turned out to give a new and very short proof of Cayley’s formula itself, which the two authors published in the American Mathematical Monthly in 2024.

What the paper does not settle is the other side. The authors prove that, with high probability, no synchronizing word shorter than about n^1/3 exists, but they expect 1/2 to be the correct exponent. The exact logarithmic correction remains open. Shortly after the proof appeared, Anders Martinsson sharpened the upper bound to the order of √(n log n) by a different route, without w-trees.

Directed networks, and what comes next

The project began with a talk by Nicaud in February 2020, where he presented his quasilinear bound at the Journées Combinatoires de Bordeaux, and Chapuy was in the audience. “Guillaume and I have been good friends since we shared an office at McGill University for a year,” Perarnau says. “At the time I was working on random automata in another context, and he remembered that, so starting the project together was very natural.”

“Finding a hidden object in a directed network can be exponentially more costly than in an undirected one, if you know where to hide it!”

Guillem Perarnau

That other context is random directed graphs, which Perarnau describes as one of his main lines of research. A directed graph is one where each edge has a direction, and he points out that most interactions in the world are asymmetric: the internet, transport networks and most social networks are directed, and so are ecosystems and neural networks. In some problems the directed and undirected cases behave alike, but this is not the case for exploration problems like synchronization.

His current work stays with exploration problems in directed environments, now combined with questions from combinatorial statistical learning.