Blog comment, collab help man attack old maths problem

Chris Cesare in Nature reported on Friday that Terence Tao successfully attacked the Erdős discrepancy problem by building on an online collaboration. Tao is a professor in the math department at UCLA. He works primarily in mathematical areas of harmonic analysis, PDE, geometric combinatorics, arithmetic combinatorics, analytic number theory, compressed sensing, and algebraic combinatorics.

Tao in attacking the problem proved something else—that little comments mean a lot. Cesare reported a blog comment as one stepping stone that led Tao to solve this longstanding problem. The article referred to a comment on his blog which alerted him to its potential relationship with the Erdős conjecture. "Tao realized that combining the fresh insight with previous results could lead to a solution, said Nature. Tao included an acknowledgment thanking the commenter, Uwe Stroinski, who received a PhD in mathematics from the University of Tübingen. New Scientist noted how that he combined recent results in number theory with some earlier crowdsourced work

Tao submitted his paper to the arXiv preprint server earlier this month, presenting a proof of the Erdős discrepancy problem, (a puzzle about the properties of an infinite, random sequence of +1s and -1s, said New Scientist).

The paper claims to prove what Paul Erdős posed in the 1930s, and offering $500 dollars for an answer.

Erdős, born in Budapest, is considered one of the most prolific mathematicians of the 20th century. Both of Erdős's parents were high school mathematics teachers. Much of his family, died in Budapest during the Holocaust. Cesare said the mathematical puzzle had resisted an answer for 80 years. Even computerized attempts failed. Then came Tao.

In 2006, he was one of four mathematicians to receive the Fields Medal which is a prize in mathematics and something like the Nobel Prize, at the International Congress of Mathematicians in Madrid.

Tao was one of the recipients because he developed techniques that can simplify equations describing general relativity, along with those describing the quantum mechanics governing the way light moves around in a .

As for the recent news, what exactly is the Erdős discrepancy problem? Jacob Aron provided a brief introduction last year in New Scientist.

"Imagine a random, infinite sequence of numbers containing nothing but +1s and -1s. Erdős was fascinated by the extent to which such sequences contain internal patterns. One way to measure that is to cut the infinite sequence off at a certain point, and then create finite sub-sequences within that part of the sequence, such as considering only every third number or every fourth. Adding up the numbers in a sub-sequence gives a figure called the discrepancy, which acts as a measure of the structure of the sub-sequence and in turn the infinite sequence, as compared with a uniform ideal. Erdős thought that for any infinite sequence, it would always be possible to find a finite sub-sequence summing to a number larger than any you choose – but couldn't prove it."

The article in Nature, too, discussed what Erdos had in mind. Erdős, said Cesar, "speculated that any infinite string of the numbers 1 and -1 could add up to an arbitrarily large (positive or negative) value by counting only the numbers at a fixed interval for a finite number of steps. The task is intuitively easy for some arrangements—tallying digits at any interval in a sequence that is all 1s will add up to a big number. And in an alternating sequence of 1s and -1s, choosing every second digit will do the job. But Erdős conjectured that it was true for any such sequence."

Tao proved him right.

Aside from the pleasure of seeing this proven, the take-home for New Scientist also appeared to be that this was a human win over computers in doing so. "Crowds beat computers in answer to Wikipedia-sized maths problem," said the headline on Friday. Tao was better at this than a computer.

New Scientist reminded readers that the maths problem previously tackled with the help of a computer produced "a proof the size of Wikipedia." (Last year, Alexei Lisitsa and Boris Konev used a computer to prove that the discrepancy will always be larger than two. The resulting proof was a 13 gigabyte file – around the size of the entire text of Wikipedia.).

Lisitsa praised Tao nonetheless. "It is typical example of high-class human mathematics," he said in New Scientist. Still, he added, while computers may not be required to solve this problem they may be useful in other problems."


Explore further

Computer generated math proof is too large for humans to check

More information: The Erdos discrepancy problem, arXiv:1509.05363 [math.CO] arxiv.org/abs/1509.05363
Journal information: Nature

© 2015 Phys.org

Citation: Blog comment, collab help man attack old maths problem (2015, September 26) retrieved 18 September 2019 from https://phys.org/news/2015-09-blog-comment-collab-maths-problem.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.
458 shares

Feedback to editors

User comments

Sep 27, 2015
Alexei Lisitsa and Boris Konev used a computer to prove that the discrepancy will always be larger than two.
Huh? It's trivial to construct a finite sequence of any length that sums to zero when the number of elements is even, or to one when the number of elements is odd.

Sep 27, 2015
This comment has been removed by a moderator.

Sep 28, 2015
Unfortunately to move any distance within our universe, the matter we are familiar with needs to occupy the space around it before it can move to the next position. Think of a wavelength, one needs to abide to this law, instead of just a straight line. This keeps matter apart, and the universe expanding.

Sep 28, 2015
Okay, so naivety is like a ±1 sequence x_n...
One way to measure that is to cut the infinite sequence off at a certain point, and then create finite sub-sequences within that part of the sequence, such as considering only every third number or every fourth. Adding up the numbers in a sub-sequence gives a figure called the discrepancy, which acts as a measure of the structure of the sub-sequence and in turn the infinite sequence, as compared with a uniform ideal.
um, the result for each sub-sequence goes into a set, and the discrepancy is the supremum (least upper bound) of that set. The discrepancy is the supremum of summed sub-sequences taken over _all_ homogeneous arithmetic progressions of which n (length of original ±1 sequence x_n) is an element. Fascinating measure for sure. Congrats to Tao, et al!

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more