All roads lead to Rome, a colorful problem

An adventurous mathematician

It was a quiet evening in Gaussville. Avraham, an intrepid maths enthusiast, had just got home after a long day at university. Mindlessly scrolling through his phone and seeing the umpteenth online advertisement about cryptocurrencies, half curious, half surrendered, Avraham decided he would give them a go.

He just knew he wasn't going to be keen on finance or trading. He was although excited about trying to mine some Bitcoins: he had heard great things about them, so he set himself to do that. Little did he know that he was taking mining a bit too literally... All geared up, hoping to squeeze in a little fitness in his search, he adventured into the "flatland mine".

Spanning only a single vertical plane, the harsh tunnels were going to be a challenge to scout.

To the reader, Avraham may seem impulsive, almost hasty, but he is surely not unwary. In fact, he had made sure to bring a map of the mine with him.

We all know how mathematicians are though... while looking for a bitcoin, still exploring, Avraham got caught up in his thoughts and switched to autopilot, thinking back to a conjecture he had stumbled upon the day before.

Returning to the $\R$eal world he understood he had gotten lost. A brief moment of panic followed, but soon enough, behind his glasses, his eyes flashed with a frenzied glee. He was suddenly a part of one of the problems he so loved to take on.

A quick glance at the map was enough to realise that he, unfortunately, could not pinpoint his location, the mine's corridors looked all the same and were too dark: it was impossible to find a reference point.

He took some deep breaths and tried to recollect himself, beginning to figure out a way to escape the labyrinth. Exploring a little, he found that he only needed to choose what to do at the crossroads: he could just go down straight tunnels and go back on his steps to the last crossroad if he were to find a dead end. He eventually stumbled into one. Turning left or right? Going up or down? He desperately needed a set of instructions that would lead him outside, no matter his location.

A bunch of questions naturally started popping into Avraham's mind:

• Does such a set even exist?
• Is there a way to find it quickly?
• How many instructions would the smallest one contain at best? and at worst?

Avraham sat down and began to ponder, scribbling on the mine's dusty walls. After a while — maybe hours, maybe days — he shouted in pure elation: EUREKA!!! I need to go ULUURU

He just needed to follow the instructions: U, L, R, D meaning either Up, Left, Right or Down.

An orientation problem fair and square

The year is 2122 and the world has changed so much: mankind has evolved past deadly diseases, metal straws have replaced plastic ones ‒ finally saving the environment ‒ and the Riemann hypothesis has been proven for a couple of years now. But above all of that, LEGO has, at last, decided to launch its first full-scale car model.

LEGO, being LEGO, had to build the factory of such cars entirely using legos... Must be something about brand identity.

Sadly, a new way of moving objects in a straight line has not been found yet and conveyor belts are still the state of the art as far as chain production comes. But it doesn’t end there: a series of poorly made life decisions (some of them regarding hibernation) has led you to be in charge of designing the contraptions for the LEGO car factory.

Today you are tackling a peculiar situation:

The last step to completing a car is attaching the roof. There are two conveyor belts positioned perpendicular to each other: one carries the almost-finished cars and the other one transports the roofs. The problem is that roofs can come in four different orientations but only one of them fits the car!

Your job is to design a setup to orient the pieces in the right way. Obviously, to assemble the mechanism you can use only lego bricks, so no sensors, no motors, nothing like that: only passive solutions are allowed. Studying the shape of the roof you arrive at the conclusion that placing a series of bricks in just one of two vertical positions should be enough to rotate the pieces from any orientation to every other.

The problem is just finding out the right series which positions the roof as needed. You get down and try to find the sequence manually but the task gets very frustrating really quickly: soon enough you end up giving up any hope. With a quick browser search – using your mind, obviously – you find an old paper that seems to give you all the answers. The name of the author strucks you as being quite unusual. You really can't think about anybody else named Avraham.

Anyways, using the suggested algorithm the sequence is soon found: GRGRGR . You place the barriers in the figured order: G meaning Green and R meaning Red.

What's behind the trick

The findings of Avraham and waken-from-cryostasis-future-you may seem some kind of obscure wizardry. Truth is, magicians use these findings in several of their tricks. The chance to follow a set of instructions which always end up in the same configuration, no matter the starting point, is not only mind-blowing but also hell of a lot useful.

You may be surprised to know that what we have introduced with the couple of tales above is a mathematical concept that has been studied for over half a century now. It even has some questions and problems which have gone unsolved so far. Let's dive a little deeper...

Time to abstract

As we have just seen, the "trick" works in a wide variety of situations. In a truly mathematical fashion, we’ll use the power of abstraction to factor out all the scenario-specific differences and focus on the common part.

First of all, we will call the crossroads/roofs orientations/configurations "States" and the instructions to move between them "Transitions".

In both the examples above it is clear that after reaching a state you are presented with a choice, you could either go Up, Down, Left or Right in the mine or choose the Green rather than the Red brick for the legos. Let’s identify transitions with symbols like U, D, L, R or G and R or 0, 1, 2, 3 and so on. Now, think of the last sequence of symbols you used to convey some sort of meaning: a Word . That's what we’ll call a sequence of instructions in our model.

If we associate every symbol with a colour, we can draw every state as an indexed circle and every transition as a coloured arrow between them.

Getting back to the scenarios we encountered:

• As for the conveyor belt, we’ll draw the four orientations as the nodes and we’ll use red/green arrows to represent a collision with a red/green brick;
• As for the mine, we’ll number the crossroads starting from the bottom left corner proceeding to the top right, row by row. Then we’ll use red, blue, green or orange arrows to represent the choice to go up, right, down or left. For reference, the numbering is also drawn on the mine’s map here.

Our setups are officially represented as a directed graph:

Now, given a starting state and a word we can easily compute the landing state. It's just a matter of following the correct arrows.

So let's recap, we have constructed a not-so-black box that can take in a set of instructions, a word, and spit out a result. Doesn't it sound even a little familiar? Careful because this time the answer is literally before your eyes: a Computer!

Well not quite, it's an abstract, way simpler and memoryless computer, a mathematical one. An automaton!

Now try and execute the same word from the same starting state twice, do you expect the results to change? It would be a problem if it did: when you ask your calculator what 2+2 is, you'd want the answer not to change every time, wouldn't you? These kinds of processes are called deterministic. Furthermore in this case the number of possible states has a limit, it's finite.

We have built a Deterministic Finite Automaton also known as a DFA.

It's a matter of synchronisation

Now let's focus on the actual magic trick, I think it's time we give a name to what we are looking for.

We have a bunch of different starting states and we want to bring them to just one. It's like we are a conductor and every member of the orchestra is playing out of sync. We need to find a sequence to realign them, something like a synchronising sequence... a synchronising word.

Okay cool, let's try not to follow Avraham's example though. Let's ensure that our goal really exists before we embark on our wonderful quest.

How can we know that for a given automaton a synchronising word exists? Or, equivalently, how can we tell if an automaton is synchronising?

This question, just like many others in maths, was also thought of in disguise, it had a different name and it was wearing glasses. We are really talking about a Superman-Clark Kent situation though. In the 70s Adler, Goodwyn and Weiss first conjured the "Road Colouring Problem".

We already established the strong bond between automata and directed graphs, well originally the investigations leaned more on the graph side. A colouring of a directed graph is simply the assignment of a colour to each edge exiting a node such that no two edges exiting from the same node have the same colour. Wow a lot of “edge”, “node” and “colour” in that sentence. Don't panic, it's basically what we did before assigning a symbol for each possible transition and then assigning a colour for every symbol.

The problem goes something like this: given a graph that satisfies some conditions (we'll get to those in a moment), does a colouring of the edges that admits a synchronising sequence exist?

The conditions mentioned are there mainly to avoid trivial cases where a synchronising word can't be found. Let's try and work our way up to those. As in all great legends, there are three:

1. A synchronising word needs to work starting from any vertex of the graph so, naturally, each symbol must be interpretable at each node. Let's say your symbols are A, B and C. If there was a node with just two edges coming out of it and we assigned to the edges the letters A and B, what would happen if at that node we asked for C? It wouldn’t make any sense, would it? The same goes for a node with four exiting edges. The number of edges coming out of a node is called out-degree, so for a synchronising word to even make sense the out-degree of every node needs to be constant.

2. A synchronising word leads every node to a single one. So, first of all, said node must be reachable, in one way or another, from every node of the graph. Remember that a graph is just a set of nodes and edges so there's nothing against building one with edgeless nodes or isolated parts. To protect ourselves from those, we need to be able to reach every node starting from every other node via a valid route, in other words, we need a strongly connected graph

3. Unfortunately, now it gets a little more complicated. Picture a graph with just three nodes with an out-degree of 1, a graph where each node points to the one which does not point to it. You get a cycle, which is not that big of a deal per se, but this cycle is special. You'll never be able to make two different nodes collapse into one using a word. It's impossible. We need to avoid these kinds of situations. Without going into the gory details, that are beyond the scope of this article, we need an aperiodic graph

Now that trivial cases are out of the way, what more can we say about the existence of a synchronising colouring? Well, the authors of the problem didn't arrive at a solution but they proposed a conjecture, the "Road Colouring conjecture".

Hold on tight because it's about to get crazy.

They simply conjectured that… you guessed it: as long as those conditions are met, you are guaranteed that a synchronising colouring exists, they are sufficient.

It can't be true, can it? Three simple checks are enough for something so oddly specific and powerful? It's almost unbelievable. Such sweet endings must live only in fairy tales. But indeed an ending was not. Until otherwise proven, it was just a conjecture, not a theorem. A still untouched heavenly city that can crumble at a single counter-example, hidden behind the seemingly insurmountable wall of a lack of rigorous proof.

Fourty years passed and the failed attempts of hundreds of mathematicians continued to stack up, one after the other. It is thanks to Avraham Trahtman that we can now talk about the end of this story. In 2007 he was finally able to prove the conjecture: the dream became reality and all maths-enthusiasts lived happily ever after. Maybe not all of them: for us this is just the beginning...

When words are sharper than bits

The "Road Colouring theorem", although amazing, doesn't tell us much about how to find the synchronising words. We’re a teeny-tiny step away from solving a never-ending variety of everyday problems.

Let's start by noticing that when a graph allows a synchronising word to exist, it automatically implies that there are infinitely many of them. That's because if we combine a synch word with any other possible combination of symbols we still get a synchronising word. So let's refine once more our target, we want to find the shortest synchronising word for a given automaton.

For these kinds of tasks, it may be useful to tackle the problem from more of a computer science perspective: we are looking for an algorithm.

The first step has to be checking whether the word can be found, and we can easily do that with the Road colouring theorem.

Then we need to find the word. A basic approach would be to methodically test increasingly longer words against random initial states to see if they are synchronising. The core idea is not bad, in fact, it's the one behind many synchronising word-finding algorithms. But it needs quite a bit of polish.

What if, instead of applying a transition singularly to each initial state, we applied it to the whole set of them, to then record where each of them landed? We would now be able to explore all the different possibilities starting from a set of all the possible states, gradually applying all the possible transitions. Finally, we would apply all the transitions to the resulting sets of the previous step iteratively, until we were to find a set with just one state, finally syncronised.

Mind that the order by which we check the transitions matters and we are not ensured to find the shortest sequence. The tables turn if we keep track of the sets we encounter along the way and keep going only when we are presented with a new set. Just by doing that, we automatically select the shortest words because sequences that loop back to previous states in vain are discarded.

If you think about it, we are building a new automaton/directed graph where each state is a set of states. Finding the shortest synchronising word has become a matter of finding the shortest path between two nodes of a graph. Pretty good solutions to this problems are already known: Algorithms like Dijkstra’s or A* do the job fairly well.

Reasoning about the unknown

Now that we have found a way to find them, let's talk about sizes. Even if a synch word exists and we can find it, it’s not very useful if it’s overwhelmingly long.

Naturally, something like the length of the synch word is heavily dependent on the topology of the automaton. It would be really difficult to figure the length without looking for the actual word.

We are nevertheless in the realm of mathematics: so, when we don’t know something, we estimate. In particular, we can focus on the search for an upper bound so as to have a grasp on the usability of the word.

The spirit of Giacomo Leopardi possesses us for a moment allowing us to see only the worst possible scenario. What’s the absolute longest shortest word we could potentially find?

Well, as we have discussed in the previous paragraphs, whenever a transition brings a set to a previously encountered one we get an unnecessary sequence of symbols. That’s not good: for the longest shortest word we can’t waste any precious symbols.

In fact, the worst scenario possible is that there are no useless loops,meaning that starting from the set containing all the states we need to pass exactly once for every other possible set with more than one element.

Computing how many subsets of a set containing $n$ elements there are is shockingly simple: $2^n$. That’s because every element of the set can either be in or out of a subset, essentially giving you two choices. Thus, choosing $n$ times between two options gives you $2^n$ different configurations. From those, we have to account for the empty set and all the sets containing one element (because they are the destination). Consequently an upper bound for the length of the shortest synchronising word is $2^n -n - 1$.

That’s what the young Ján Černý might have thought before formulating his conjecture:yup, another one. This time, the intrepid paladin of knowledge that will prove or disprove it may be reading this article right now. This time we are talking about an open problem.

Černý conjectured that the smallest upper bound for an automaton with $n$ states is $(n-1)^2$. And by now we are sure that it can’t get lower than that given we know of some automaton whose shortest synch word is exactly $(n-1)^2$ symbols long.

Currently the best upper bound known is $(n^3 - n)/6$ even though the Černý conjecture has been proven for some classes of automaton.

There's more than mines and lego bricks

We have reached the end of our journey. There is only a question left to answer:

So, first of all, let’s remember that the important part is not the destination but the friends you made along the way. Secondly let’s now substitute Avrahm with the embedded circuit of a vending machine or of a satellite, the mine with the harsh real word and the being spaced out by mathematical wondering with some generic error. We have found a way to make simple computational devices error-resistant. Now, whenever an error is detected, or the machine is switched on or we generally lose track of the current state, we have a simple, hopefully short, set of instructions to rest the situation. We can take a long breath and start again from there.

The world behind the keyboard

We are a team of 5 Engineering of Computing Systems students (names and roles are in alphabetical order):

• Dario CrosaCreative CodingFull Stack Web Development
• Federico GrandiFull Stack Web Development
• Francesco GenoveseFrontend Web DevelopmentWriting
• Matteo GarzoneCreative Coding
• Paolo GinefraCreative CodingPixel ArtProject ManagementWriting

Keep in mind that this structure wasn’t rigid at all and we made sure to help each other in any way possible. This was our first time making something like this, we hope you enjoyed! Any kind of feedback is highly appreciated :)

Particular thanks go to professor Emanuele Rodaro for sharing his knowledge on the topic and putting us on the right track.