FURRY MATH The Erdős 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.
Puppy: spxChrome/iStockphoto; Kitten: Tsekhmister/iStockphoto
It took more than 80 years, but a problem posed by a mathematician who delighted in concocting tricky ones has finally been solved.
UCLA mathematician Terence Tao has produced a solution to the Erdős discrepancy problem, named after the enigmatic Hungarian numbers wizard Paul Erdős. Tao’s proof, posted online September 18 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 Erdős discrepancy problem involves a sequence of numbers, 1s and –1s. To make it easier to visualize, think of a line of people (or, say, puppies and kittens in our example above). The goal is to line everyone up so that as you go down the queue, the discrepancy between the number of men and women stays as small as possible. It’s easy at first: Just alternate men and women and the difference will never exceed one. The real challenge is to also minimize the sex discrepancy when considering only every other person down the line (the second, fourth, sixth, and so on). Then do the same for similar subsets, known as homogeneous arithmetic progressions, of the line: every third person, every fourth person and so on.
In 1932, Erdős proposed that with enough people in line (or numbers in a sequence, as he framed it), there is no limit to how high the discrepancy can get, regardless of one’s efforts to curtail it. But Erdős, 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 other researchers collaborated over the Internet (SN Online: 12/8/09) and made some progress. Tao says he all but forgot about the problem until this year, when he started working with a pair of 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 arithmetic progressions that minimize discrepancies. (Tao didn’t make the connection at first — a commenter on his blog brought it to his attention.) Tao devised a full solution proving that Erdős 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 long (though he describes some of the problem-solving techniques he used in another paper). Lisitsa and Liverpool colleague Boris Konev recently designed a computer algorithm that required hundreds of megabytes’ worth of text just to prove that a line of 1,161 1s and –1s 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 of Tao’s work.
