In the form of a conjecture, the so-called Erdös discrepancy problem can be stated as follows: for any infinite sequence consisting of ones and minus ones, it is always possible to find a finite number of equidistant terms whose sum exceeds, in absolute value, any previously chosen number, no matter how large it is taken. The conjecture was proved by Terence Tao (UCLA) in September 2015.
There are several reasons that make this a relevant problem.
On the one hand, there is the mathematical difficulty of a problem with a very simple statement but which has required highly sophisticated techniques to solve; a measure of this difficulty is the fact that the problem has taken 80 years to solve.
On the other hand, there is the person who proposed the problem: Paul Erdös. Erdös was undoubtedly one of the most unique scientists in history, a sort of wandering mathematician who had no home other than mathematics itself. Erdös used to offer cash prizes for solving the numerous problems he proposed throughout his life; in the case of the discrepancy problem, the prize offered was 500 euros, one of the largest. And it also stands out because of who solved it: Terence Tao, Fields medal winner at the ICM-2006 in Madrid, is possibly the brightest diamond on the world mathematical scene. It so happens that Erdös wrote Tao a letter of recommendation for Princeton when Tao, aged just 17, went to study there on a Fullbright scholarship (in the photo: Erdös with Tao in 1985).
And, last but not least, the problem is relevant because of the role that the Polymath project has played in solving it. Polymath is an attempt to solve important and difficult mathematical problems collaboratively using the web, a kind of crowdfunding where, instead of money, collective ideas and initiatives are collected to solve a mathematical problem. Timothy Gowers (Cambridge; Fields Medal, 1998) put it into practice in 2009. Five years ago, the Erdös discrepancy problem was the focus of the fifth Polymath challenge. Collective efforts, in which Tao himself took part, did not succeed, although in February 2014, A. Lisitsa and B. Konev (U. Liverpool) developed a computer program that made it possible to solve the problem when the starting number is 2 (the simplest case). It so happens that this program generated a file (the proof, so to speak) of 13 gigabytes, which at the time was a record for the length of a mathematical proof.
The problem, however, remained stuck in Tao’s neurons, and he has acknowledged that he owes part of his solution to ideas generated by Polymath5.
References
The news of the resolution can be read on the Scientific American website: Math Whiz Solves a Mater’s Riddle
What Gowers wrote about Polymath5 and the Tao resolution in: https://gowers.wordpress.com/2015/09/20/edp28-problem-solved-by-terence-tao/
Tao’s own lengthy (and technical) exposition of his resolution in: https://terrytao.wordpress.com/2015/09/11/the-erdos-discrepancy-problem-via-the-elliott-conjecture/
This post participates in Edition 7.7 of the Carnaval de Matemáticas, organised this time by Los Matemáticos no son gente seria (Mathematicians are not serious people).
Leave a Reply