UCLA Mathnet Login

Terry Tao Solves Erdős Discrepancy Problem

Terry Tao

"Terence Tao of the University of California, Los Angeles, has published a proof of the Erdős discrepancy problem, a puzzle about the properties of an infinite, random sequence of +1s and -1s. In the 1930s, Hungarian mathematician Paul Erdős wondered whether such a sequence would always contain patterns and structure within the randomness.

One way to measure this is by calculating a value known as the discrepancy. This involves adding up all the +1s and -1s within every possible sub-sequence. You might think the pluses and minuses would cancel out to make zero, but Erdős said that as your sub-sequences got longer, this sum would have to go up, revealing an unavoidable structure. In fact, he said the discrepancy would be infinite, meaning you would have to add forever, so mathematicians started by looking at smaller cases in the hopes of finding clues to attack the problem in a different way.

Tao has used more traditional mathematics to prove that Erdős was right, and the discrepancy is infinite no matter the sequence you choose. He did it by combining recent results in number theory with some earlier, crowdsourced work."

Continue to the full article here.

Additional coverage:

Nature

http://www.nature.com/news/maths-whizz-solves-a-master-s-riddle-1.18441

Scientific American:

http://www.scientificamerican.com/article/math-whiz-solves-a-master-s-riddle/

USA Today:

http://www.usatoday.com/story/news/2015/09/28/newser-famous-math-problem-solved-crowdsourcing/72973338/

Prensa Latina:

http://www.plenglish.com/index.php?option=com_content&task=view&id=4195721&Itemid=1

Quanta magazine:

https://www.quantamagazine.org/20151001-tao-erdos-discrepancy-problem/