Directions from anywhere: maths problem solved

Original story

A 63 year old former security guard appears to have solved an esoteric mystery that has baffled the top minds in an arcane field of mathematics for almost four decades .

Avraham Trakhtman, a mathematician who worked as a labourer after immigrating to Israel from Russia, has succeeded where dozens have failed and cracked the elusive “Road Colouring Problem.”

The conjecture essentially assumes that it is possible to create a “universal map” that would direct people to arrive at a certain destination, at the same time, regardless of their original location.

Experts say this proposition, which seems to defy logic, could actually have real-life applications in fields such as mapping and computer science.

“In math circles, we talk about beautiful results — this is beautiful and it is unexpected. Even in layman’s terms it is completely counterintuitive, but somehow it works,” says Stuart Margolis, a colleague who recruited Mr Trakhtman to Bar Ilan University near Tel Aviv.

“It’s God-given gray matter in his brain. He is shy reserved and very modest. He intentionally offered his paper to an Israeli journal even though any mathematics journal in the world would be overjoyed to get it.”

The solution about to appear in the Israel Journal of Mathematics could have many applications, says Margolis, citing one real world formulation of the problem.

Assume that an email is lost on the internet. The systems operator wants to get it sent to the right place says Margolis. “But he doesn’t know where it is. Synchronizing instructions could get it there like a mouse through a maze. Avraham’s work proves that it’s always possible to find one’s way with such instructions.”

He says the discovery was especially remarkable for two reasons. “Math is usually a younger person’s game, like sports,” he says. “Usually you do your better work in your mid 20s and early 30s. He certainly came up with a good one at age 63.”

Secondly, Trakhtman has an unlikely background.

“The first time I met him he was wearing a night watchman’s uniform.”

Originally from Yekaterinburg, Russia, Trakhtman was already an accomplished mathematician before he came to Israel in 1992, at the age of 48.

But like many immigrants in the wave that followed the breakup of the former Soviet Union, he struggled to find work in the Jewish state and was forced into stints working maintenance and security before landing a teaching position at Bar Ilan in 1995.

“The heartwarming part of it is here is a guy who had a good reputation for his work in the Soviet Union and couldn’t get work,”says Margolis.

The soft-spoken Trakhtman says he was “lucky” to be recognized, but played down his recent achievement as a “matter for mathematicians” and says it hasn’t changed him.

“The solution is not that complicated. It’s hard, but it is not that complicated,” he says. “Some people think they need to be complicated. I think they need to be nice and simple.”

The “Road Colouring Problem” was first posed in 1970 by Benjamin Weiss, an Israeli-American mathematician, and a colleague, Roy Adler, who worked at IBM at the time.

In his online paper, http://arxiv.org/abs/0709.0099, Trakhtman, sums up the problem like this:

“The task is to find a labelling of the edges that turns the graph into a deterministic finite automaton possessing a synchronizing word. So the road colouring problem is connected with the problem of existence of synchronizing word for deterministic complete finite automaton.”

A commonly used and more comprehensible formulation for the hoi polloi goes as follows: A man reaches a town he has never visited before and drives around trying to find the home of his friend even though there are no street names.

The friend says not to worry and that he will provide instructions (left, right, left...) on how to get there.

This is called synchronising instruction. The problem is whether by using such instructions, the driver could reach his destination no matter where he was lost.

Weiss says he believed that given a finite number of roads, one should be able to draw up a map, coded in various colours, that would lead to a certain destination regardless of the point of origin.

For eight years, he tried to prove his theory.

Over the next 30 years, some 100 other scientists attempted to as well.

All failed, until Trakhtman came along and, in eight short pages, jotted the solution down in pencil last year.

Directions from anywhere: maths problem solved 3-22-08

Original story A 63 year old former security guard appears to have solved an esoteric mystery that has baffled the top minds in an arcane field of mathematics for almost four decades . Avraham Trakhtman, a mathematician who worked as a labourer after immigrating to Israel from Russia, has succeeded where dozens have failed and cracked the elusive “Road Colouring Problem.” The conjecture essentially assumes that it is possible to create a “universal map” that would direct people to arrive at a certain destination, at the same time, regardless of their original location. Experts say this proposition, which seems to defy logic, could actually have real-life applications in fields such as mapping and computer science. “In math circles, we talk about beautiful results — this is beautiful and it is unexpected. Even in layman’s terms it is completely counterintuitive, but somehow it works,” says Stuart Margolis, a colleague who recruited Mr Trakhtman to Bar Ilan University near Tel Aviv. “It’s God-given gray matter in his brain. He is shy reserved and very modest. He intentionally offered his paper to an Israeli journal even though any mathematics journal in the world would be overjoyed to get it.” The solution about to appear in the Israel Journal of Mathematics could have many applications, says Margolis, citing one real world formulation of the problem. Assume that an email is lost on the internet. The systems operator wants to get it sent to the right place says Margolis. “But he doesn’t know where it is. Synchronizing instructions could get it there like a mouse through a maze. Avraham’s work proves that it’s always possible to find one’s way with such instructions.” He says the discovery was especially remarkable for two reasons. “Math is usually a younger person’s game, like sports,” he says. “Usually you do your better work in your mid 20s and early 30s. He certainly came up with a good one at age 63.” Secondly, Trakhtman has an unlikely background. “The first time I met him he was wearing a night watchman’s uniform.” Originally from Yekaterinburg, Russia, Trakhtman was already an accomplished mathematician before he came to Israel in 1992, at the age of 48. But like many immigrants in the wave that followed the breakup of the former Soviet Union, he struggled to find work in the Jewish state and was forced into stints working maintenance and security before landing a teaching position at Bar Ilan in 1995. “The heartwarming part of it is here is a guy who had a good reputation for his work in the Soviet Union and couldn’t get work,”says Margolis. The soft-spoken Trakhtman says he was “lucky” to be recognized, but played down his recent achievement as a “matter for mathematicians” and says it hasn’t changed him. “The solution is not that complicated. It’s hard, but it is not that complicated,” he says. “Some people think they need to be complicated. I think they need to be nice and simple.” The “Road Colouring Problem” was first posed in 1970 by Benjamin Weiss, an Israeli-American mathematician, and a colleague, Roy Adler, who worked at IBM at the time. In his online paper, http://arxiv.org/abs/0709.0099, Trakhtman, sums up the problem like this: “The task is to find a labelling of the edges that turns the graph into a deterministic finite automaton possessing a synchronizing word. So the road colouring problem is connected with the problem of existence of synchronizing word for deterministic complete finite automaton.” A commonly used and more comprehensible formulation for the hoi polloi goes as follows: A man reaches a town he has never visited before and drives around trying to find the home of his friend even though there are no street names. The friend says not to worry and that he will provide instructions (left, right, left...) on how to get there. This is called synchronising instruction. The problem is whether by using such instructions, the driver could reach his destination no matter where he was lost. Weiss says he believed that given a finite number of roads, one should be able to draw up a map, coded in various colours, that would lead to a certain destination regardless of the point of origin. For eight years, he tried to prove his theory. Over the next 30 years, some 100 other scientists attempted to as well. All failed, until Trakhtman came along and, in eight short pages, jotted the solution down in pencil last year.