Recent news concerning the Erdos discrepancy problem

I’ve just learnt from a reshare by Kevin O’Bryant of a post by Andrew Sutherland on Google Plus that a paper appeared on the arXiv today with an interesting result about the Erdős discrepancy problem, which was the subject of a Polymath project hosted on this blog four years ago.

The problem is to show that if (\epsilon_n) is an infinite sequence of \pm 1s, then for every C there exist d and m such that \sum_{i=1}^m\epsilon_{id} has modulus at least C. This result is straightforward to prove by an exhaustive search when C=2. One thing that the Polymath project did was to discover several sequences of length 1124 such that no sum has modulus greater than 2, and despite some effort nobody managed to find a longer one. That was enough to convince me that 1124 was the correct bound.

However, the new result shows the danger of this kind of empirical evidence. The authors used state of the art SAT solvers to find a sequence of length 1160 with no sum having modulus greater than 2, and also showed that this bound is best possible. Of this second statement, they write the following: “The negative witness, that is, the DRUP unsatisfiability certificate, is probably one of longest proofs of a non-trivial mathematical result ever produced. Its gigantic size is comparable, for example, with the size of the whole Wikipedia, so one may have doubts about to which degree this can be accepted as a proof of a mathematical statement.”

I personally am relaxed about huge computer proofs like this. It is conceivable that the authors made a mistake somewhere, but that is true of conventional proofs as well. The paper is by Boris Konev and Alexei Lisitsa and appears here.

About these ads

29 Responses to “Recent news concerning the Erdos discrepancy problem”

  1. Gil Kalai Says:

    This is very nice! In my view a primary scientific achievement here is the ability to prove such a statement using a computer, and it is also good to know that the answer is at least 3.

  2. Polymath5 – Is 2 logarithmic in 1124? | Combinatorics and more Says:

    […] Update (February 2013): Boris Konev and Alexei Lisitsa found a sequence of length 1160 of discrepancy 2 and proved that no such sequence of length 1161 exists. A SAT Attack on the Erdos Discrepancy Conjecture The abstract reads: “We show that by encoding the problem into Boolean satisfiability and applying the state of the art SAT solvers, one can obtain a sequence of length 1160 with discrepancy 2 and a proof of the Erdos discrepancy conjecture for C=2, claiming that no sequence of length 1161 and discrepancy 2 exists. We also present our partial results for the case of C=3. See also this post. […]

  3. vznvzn Says:

    this is really way cool!!! … a gamechanger! cybersynchronicity…. was just citing some similar empirical SAT results recently on RJLs blog (who has written interesting stuff on EDP). a very big & bridge-theorem-like result that is likely to make people from both fields TCS/math really take some notice. inspires me to finally write up a blog on TCS empirical research. my big question is how they seemed to narrow down infinitary type assertions into a finite SAT proof. like the idea a lot but hope the authors will provide auxillary details/files somewhere on a web page to assist with 3rd party verification/replication/advancement efforts. will be interested to chat further with anyone with this on math.se or tcs.se ….

  4. Alec Edgington Says:

    Nice.

    A couple of observations about the example sequence x of length 1160:

    The initial sequence x_1, \ldots, x_{11} is a maximal sequence of discrepancy 1.
    The sequence (or rather its negation, so that x_1 = 1) seems very multiplicative, at least on non-multiples of 3. In fact, the smallest ab (not a multiple of 3) such that x_{ab} \neq x_a x_b is 259 = 7 \times 37.

    • gowers Says:

      That’s interesting. I was looking forward to doing the kind of analysis on this sequence that we did on the sequences of length 1124. It would be great if someone could produce a nice visual version of it, arranged in rows of 24 with blue and green squares, as we did with the other ones. But maybe that would involve typing in a sequence of 1160 pluses and minuses, which wouldn’t be much fun.

  5. Polymath 5 | Euclidean Ramsey Theory Says:

    […] It finds an example of size 1160 that has value 2 and proves that that example is maximal. The polymath 5 project found an example of size 1124. The proof that 1160 is maximal required a large computer proof. For more information see this post: http://gowers.wordpress.com/2014/02/11/recent-news-concerning-the-erdos-discrepancy-problem/ […]

  6. Alexei Lisitsa Says:

    Dear all, thank you for good words on our work.
    I would like to just let you know that all related materials are available at

    http://cgi.csc.liv.ac.uk/~konev/SAT14/

    Than includes a program which generates SAT encoding of the problem for any given length and discrepancy; all mentioned in the paper and ready to use encodings; all mentioned in the paper sequences, in particular 1160 discrepancy 2 sequence – so no need to type it in.

  7. great moments in empirical/experimental math/TCS research, breakthough SAT induction idea | Turing Machine Says:

    […] 1. Recent news concerning the Erdos discrepancy problem | Gowers’s Weblog […]

  8. vznvzn Says:

    oh WTG as stated your announcement & this paper was so inspiring, wrote up an entire blog in its honor on great moments in empirical/experimental math/TCS research, breakthough SAT induction idea with many refs, links, Stackexch Q/A & no less than 12 emoticons so am sure your readers will be very much impressed. oh and it has an entire research program outline at the end based on SAT induction that frankly is a revolutionary idea if you ask me. (but nobody did oh well). & would make a great polymath proj. just sayin. :grin:

  9. AlexB Says:

    Neat. Finally an application for Levin’s Holographic proofs:

    http://www.cs.bu.edu/fac/lnd/expo/holo.htm

  10. Ewart Shaw Says:

    Here’s a graphical representation – hope you’ll forgive its being a facebook profile picture!

  11. Jason Dyer Says:

    I suppose now is as good a time as any to mention my unpublished work from a few years ago working on this after Polymath 5 folded; unpublished because I didn’t think it was significant enough.

    Still, I did present at a number theory seminar, so I’ve got slides at least:

    https://dl.dropboxusercontent.com/u/5948483/erdosfinal.pdf

    Probably the most interesting part is how I use a subgraph to get that a discrepancy of 1 is broken when you have positive integer triples a < b < c such that (b-a)/a, (c-a)/a and (c-b)/b are all odd integers. Since the first triplet where this is true is {9, 10, 12} that's why the break happens at 12. Page 36 has a graph of all the triples. I was able to find no relation between them and the C=2 problem. I was possibly foiled by not working with an optimal sequence; I was assuming 1124 and working with what we had from Polymath the entire time.

    I also tried very hard to find an equivalent subgraph for a discrepancy of 2 but I couldn't find anything that would also be present in the integers.

  12. vznvzn Says:

    hi all fyi there were two mainstream articles published on this breakthru in New Scientist & the Independent, one quoting Kalai & the other Budd. (& it was further way cool to scoop them :cool: )
    am thinking it might just be the beginning of major innovation in this area (applying SAT solvers to very difficult math/TCS problems). again links/more info in my latest blog

  13. vznvzn Says:

    oh, also this following question got booted from MO with -3, and another -3 on tcs.se, but its coming back from the dead in a dramatic turnaround with some key endorsements by SN/JE… connections between EDP & TCS tcs.se

  14. Erdős’s discrepancy problem now less of a problem | The Aperiodical Says:

    […] Recent news concerning the Erdos discrepancy problem on Tim Gowers’s blog […]

  15. Mark Bennet Says:

    I’m as much interested in the assertion that discrepancy 3 takes us at least to 13,000. Also 1160 has highest prime factor 29. Is there any prospect of an asymptotic f(n) for discrepancy n, or any bounds on the prime numbers involved? Analysing the prime factors also gives scope for more efficient analysis. If we could identify key bottlenecks in advance (for 2, these include 1124 and 1160) it would be possible to detect sequences destined to fail much earlier, by analysing the subsequences converging on the bottlenecks. Are there bottleneck numbers for discrepancy 3?

  16. Anonymous Says:

    A simple pattern:

    11 = 2^2 * 4 – 1
    1160 = 3^3 * 43 – 1

    So perhaps the next term will be 4^4 * (something) – 1.

  17. Practically P=NP? | Gödel's Lost Letter and P=NP Says:

    […] is obvious: just consider any odd-length sub-sequence. For consider , as noted here: no sequence of length 12 has discrepancy […]

  18. Daniel Bundala Says:

    Already last year, we also used a SAT-based approach to attack a different combinatorial problem. In http://arxiv.org/abs/1310.6271 we resolved a 40-years-old problem by Don Knuth on optimality of certain sorting networks.

  19. Enrique Zeleny Says:

    Reblogged this on Enrique Zeleny's Blog.

  20. Connections between the Erdos Discrepancy Problem and (Theoretical) CS? | Question and Answer Says:

    […] attack on EDP by Konev and Lisitsa, and reaction by Gowers; also, other connections to empirical/experimental TCS (e.g. SAT automated theorem […]

  21. Vandenabeele Thomas Says:

    Can’t one just prove the conjecture like this?

    In an *infinite* sequence of +-1′s, you can find a subsequence which contains any combination of +-1′s you like.
    Thus, for every C, it will be possible to find a subsequence which contains at least C+1 (positive) 1′s.

    Q.E.D?

    • gowers Says:

      The subsequence has to be of the particular form where you pick d and n and choose the terms of the sequence in places d, 2d, \dots, md. As you say, if you were allowed to choose arbitrary subsequences, the problem would be trivial.

    • Vandenabeele Thomas Says:

      Okay, that will be harder indeed :-)
      Do U think, given a certain C, it could ever be possible predicting the minimum value of n, i.e. the minimum length of a subsequence, to go above C? Like I could calculate that for C = 2, n must be at least 1161?

      Thanks for your help.

    • gowers Says:

      I think it is very unlikely indeed that an exact formula for the dependence of n on C will ever be discovered. The best it seems reasonable to hope for is upper and lower bounds that differ by a constant factor, and even that is very ambitious.

  22. Thomas Bloom Says:

    Inspired by this, Cynthia Kop and I have been trying a SAT attack on the completely multiplicative case of the EDP for discrepancy 3.

    We have been able to generate a completely multiplicative sequence of length 18025 with discrepancy no more than 3. (In particular, of course, the regular EDP also needs a sequence of length at least 18025).

    Given that the 2-discrepancy case has a 267 cutoff for the multiplicative case but 1161 for the general case this suggests that the regular EDP can go quite far with discrepancy 3!

    Interestingly also, the 18025 sequence seems to heavily favour -1 on primes 1 mod 3 and 1 on primes 2 mod 3. This does seem to suggest that to construct long sequences one should at least start from a character.

    • Thomas Bloom Says:

      Had I thought to check http://cgi.csc.liv.ac.uk/~konev/edp/ before I posted the above comment I would have seen, however, that Konev and Lisitsa have dramatically extended their calculations and found a completely multiplicative sequence of length 127645 and discrepancy 3, which makes our 18025 look rather pitiful!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 1,619 other followers

%d bloggers like this: