Name
Abstract | ||
|---|---|---|
In 1930s Paul Erdos conjectured that for any positive integer C in any infinite +/- 1 sequence (x(n)) there exists a subsequence x(d), x(2d), x(3d),..., x(kd), for some positive integers k and d, such that vertical bar Sigma(k)(i=1) x(id) vertical bar> C. The conjecture has been referred to as one of the major open problems in combinatorial number theory and discrepancy theory. For the particular case of C = 1 a human proof of the conjecture exists; for C = 2 a bespoke computer program had generated sequences of length 1124 of discrepancy 2, but the status of the conjecture remained open even for such a small bound. We show that by encoding the problem into Boolean satisfiability and applying the state of the art SAT solver, one can obtain a discrepancy 2 sequence of length 1160 and a proof of the Erdos discrepancy conjecture for C = 2, claiming that no discrepancy 2 sequence of length 1161, or more, exists. We also present our partial results for the case of C = 3. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-09284-3_17 | Lecture Notes in Computer Science |
DocType | Volume | ISSN |
Journal | 8561 | 0302-9743 |
Citations | PageRank | References |
6 | 0.59 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Boris Konev | 1 | 569 | 42.08 |
| Alexei Lisitsa | 2 | 272 | 45.94 |