JERUSALEM - A mathematical puzzle that baffled the top minds inthe esoteric field of symbolic dynamics for nearly four decades hasbeen cracked - by a 63-year-old immigrant who once had to work as asecurity guard.
Avraham Trahtman, a mathematician who also toiled as a laborerafter moving to Israel from Russia, succeeded where dozens failed,solving the elusive "Road Coloring Problem."
The conjecture essentially assumed it's possible to create a"universal map" that can direct people to arrive at a certaindestination, at the same time, regardless of starting point. Expertssay the proposition could have real-life applications in mapping andcomputer science.
The "Road Coloring Problem" was first posed in 1970 by BenjaminWeiss, an Israeli-American mathematician, and a colleague, RoyAdler, who worked at IBM at the time.
For eight years, Weiss tried to prove his theory. Over the next30 years, 100 other scientists attempted as well. All failed, untilTrahtman came along, and in eight short pages, jotted the solutiondown in pencil last year.
"The solution is not that complicated. It's hard, but it is notthat complicated," Trahtman said in heavily accented Hebrew. "Somepeople think they need to be complicated. I think they need to benice and simple."
Weiss said it gave him great joy to see someone solve hisproblem.
Stuart Margolis, a mathematician who recruited Trahtman to teachat Bar Ilan University near Tel Aviv, called the solution one of the"beautiful results." But he said what makes the result especiallyremarkable is Trahtman's age and background.
"Math is usually a younger person's game, like music and thearts," Margolis said. "Usually you do your better work in your mid20s and early 30s. He certainly came up with a good one at age 63."
Adding to the excitement is Trahtman's personal triumph infinally finding work as a mathematician after immigrating fromRussia. "The first time I met him he was wearing a night watchman'suniform," Margolis said.
Originally from Yekaterinburg, Russia, Trahtman was anaccomplished mathematician when he came to Israel in 1992, at age48. But like many immigrants in the wave that followed the breakupof the Soviet Union, he struggled to find work in the Jewish stateand was forced into stints working maintenance and security beforelanding a teaching position at Bar Ilan in 1995.
The soft-spoken Trahtman declined to talk about his odyssey,calling that the "old days." He said he felt "lucky" to berecognized for his solution, and played down the achievement as a"matter for mathematicians," saying it hasn't changed him a bit.
The puzzle tackled by Trahtman wasn't the longest-standing openproblem to be solved recently. In 1994, British mathematician AndrewWiles solved Fermat's last theorem, which had been open for morethan 300 years.
Trahtman's solution is available on the Internet and is to bepublished soon in the Israel Journal of Mathematics.
Joel Friedman, a math professor at the University of BritishColumbia, said probably everyone in the field of symbolic dynamicshad tried to solve the problem at some point, including himself. Hesaid people in the related disciplines of graph theory, discretemath and theoretical computer science also tried.
"The solution to this problem has definitely generated excitementin the mathematical community," he said in an e-mail.
Margolis said the solution could have many applications.
"Say you've lost an e-mail and you want to get it back - it wouldbe guaranteed," he said. "Let's say you are lost in a town you havenever been in before and you have to get to a friend's house andthere are no street signs - the directions will work no matterwhat."
---
On the Net:
Trahtman's solution: http://arxiv.org/abs/0709.0099
AP-ES-03-20-08 1534EDT
No comments:
Post a Comment