Erdos Conjecture Proven
Written by Mike James   
Monday, 28 September 2015

This isn't big theory news like NP=P or anything similar, but it is a fascinating idea. About 80 years ago the remarkable and strange mathematician Paul Erdos formulated what seemed like a simple question about number sequences and it has only just been proved. 

The Erdos discrepancy conjecture is one of those nice ideas that is easy to state, but very difficult to prove. It concerns very simple sequences of numbers consisting of only -1 and 1. The sting in the tail is that the sequences are infinite and this is often where the difficulties in mathematics start. 

erdos

Paul Erdos 1913-1996

 

The conjecture is that if you pick a spacing d and a length n then you can make the sum as large as you like by picking d and a appropriately. 

For example, given the sequence with  the fairly obvious pattern:

1, -1,  1,1,  -1,-1,  1,1,1  -1,-1,-1,   1,1,1,1,  -1,-1,-1,-1,   and so on

then starting at the third element, a 1, and with a spacing d=2 and length 6, the discrepancy is 1 -1 +1+1-1+1+1 i.e. 3. 

Obviously the discrepancy of a subsequence measures the degree to which the elements 1 and -1 are unevenly distributed and the conjecture can be interpreted as saying no matter how hard you try to create a sequence that is evenly distributed you are doomed to failure as there will always be subsequences that have uneven distributions of 1 and -1 so as to give you any discrepancy you care to name.

Mathematically the conjecture is that given a sequence xn then for any integer C>0 there exists a subsequence xd, x2d, x3d,... xkd for some choice of positive integers k and d 

desequation

You can also give the original infinite series a discrepancy score as the maximum discrepancy of a subsequence it contains. In this case the conjecture says that every infinite sequence has an infinite discrepancy.

In 1993 it was proved that an infinite series cannot have a discrepancy of 1. This was done by showing that a series of length 12 always has a subsequence with discrepancy greater than 1. As this is true of any series of length 12 it has to be true of any infinite series which contain any number of subsequences of length 12.

Thus the theorem is proven for C=1. 

Last year a collaborative project on the Polymath wiki pushed this up to C=2 using a SAT solver. The problem was that the difficulty increased as C gets bigger and the proof for C=2 was so long it qualified as the longest math proof to date.  

It seemed  that this computer driven approach was getting bogged down. However the work did influence Terance Tao to look at the problem in different ways finally resulting in his publishing of a proof of the conjecture. His proof hasn't been peer reviewed as yet, but it is likely to be correct. 

Tao was a child prodigy and, when he was 10, studied for a time with Erodos. 

 

tao

Tao (10 years old) with Erdos

 

Erdos offered a prize of $500 for the solution. It doesn't look as if Tao will actually get a cheque from anyone, but he probably isn't worried. 

So now we know that you cannot build an infinite sequence of numbers that is uniform in the sense that there are always subsequences that sum to more than any given number you care to specify.

But math always moves on - the question now is how long does the subsequence have to be to get to C? For C=2 k<1161, what about C=3?

desequationicon

More Information

http://arxiv.org/abs/1509.05363

A SAT Attack on the Erdos Discrepancy Conjecture by Boris Konev & Alexei Lisitsa

Related Articles

The Machine In The Ghost       

Search For Twin Prime Proof Slows       

A Mathematical Proof Too Long To Check - The Erdos Discrepancy Conjecture       

Six Degrees Of Separation Is New

Finding Solutions To Diophantine Equations By Smell

48th Mersenne Prime Computed

What's a Sample of Size One Worth?

 

To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, FacebookGoogle+ or Linkedin,  or sign up for our weekly newsletter.

 

kotlin book

 

Comments




or email your comment to: comments@i-programmer.info

 

Banner


Ilya Sutskever Raise $1 Billion To Research Safe AI
11/09/2024

Safe Superintelligence, the company co-founded by Ilya Sutskever after he resigned from Open AI, has raised $1billion in cash funding, despite the fact that it intends not to release any products [ ... ]



Android Apps Can Block Being Sideloaded
17/09/2024

Android developers now have a way to prevent users sideloading their apps, and users are seeing the effects. Google Play Integrity API, which was released in June, blocks sideloading.


More News

 

 

 

Last Updated ( Monday, 28 September 2015 )