# 83-year-old math problem solved: proposal by Erdos involving number sequences validated.

It took more than 80 years, but a problem posed by a mathematician who delighted in concocting tricky challenges has finally been solved.

UCLA mathematician Terence Tao has produced a solution to the Erdos discrepancy problem, named after the enigmatic Hungarian numbers wizard Paul Erdos. Tao's proof, posted online September 17 at arXiv.org, shows that the difference (or discrepancy) between the quantities of two elements within certain sequences can grow without bound, even if someone does the best possible job of minimizing the discrepancy.

"Based on Tao's stature, I would trust it straightaway," even though the proof hasn't yet been peer-reviewed, says Alexei Lisitsa, a computer scientist at the University of Liverpool in England.

While the problem probably doesn't have real-world applications, Tao says, "the act of solving a problem like this often gives a trick for solving more complicated things."

The Erdos discrepancy problem involves a sequence of numbers, 1s and -1s. To visualize, think of a line of puppies and kittens.

The goal is to line them up so that as you go down the queue, the discrepancy between the number of dogs and cats stays as small as possible. It's easy at first: Just alternate the animals and the difference will never exceed one. The real challenge is to also minimize the discrepancy when considering only every other animal (the second, fourth, sixth and so on). Then do the same for similar subsets of the line: every third, every fourth and so on.

In 1932, Erdos proposed that with enough numbers in a sequence, there is no limit to how high the discrepancy can get. But Erdos, who died in 1996, left it up to his fellow mathematicians to validate his hypothesis.

The problem didn't attract much attention until about five years ago, when Tao and collaborators made some progress (SN Online: 12/8/09). Tao says he all but forgot about the problem until this year, when he started working with mathematicians who had achieved a major insight into what are called multiplicative functions. Understanding those functions turned out to be essential for sorting through some thorny sequences that minimize discrepancies. (Tao didn't make the connection at first--a commenter on his blog did.) Tao devised a full solution proving that Erdos was right: The discrepancy can grow infinitely large.

Lisitsa says Tao's solution is even more impressive because of its brevity. Tao's paper is 20 pages. Lisitsa and a colleague recently designed a computer algorithm that required hundreds of megabytes' worth of text just to prove that a line of 1,161 Is and-Is always yields a discrepancy of at least three in one of the subsequences. "It's a kind of confirmation of human power over computers," Lisitsa says.

Caption: Furry math The Erdos discrepancy problem examines sequences of 1s and-1s or, in this case, puppies and kittens. The goal is to see how effectively one can minimize the difference between the number of cats and dogs in various subsequences. Here, the difference in each row doesn't exceed one.

----------