Abstract
In 1930s Paul Erdős 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 \(\mid \sum_{i=1}^k x_{id} \mid >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 Erdős 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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Beck, J., Chen, W.W.L.: Irregularities of Distribution. Cambridge University Press (1987)
Chazelle, B.: The Discrepancy Method: Randomness and Complexity. Cambridge University Press, New York (2000)
Matousek, J.: Geometric Discrepancy: An Illustrated Guide. Algorithms and combinatorics, vol. 18. Springer (1999)
Beck, J., Sós, V.T.: Discrepancy theory. In: Graham, R.L., Grötschel, M., Lovász, L. (eds.) Handbook of Combinatorics, vol. 2, pp. 1405–1446. Elsivier (1995)
Alon, N.: Transmitting in the n-dimensional cube. Discrete Applied Mathematics 37/38, 9–11 (1992)
Muthukrishnan, S., Nikolov, A.: Optimal private halfspace counting via discrepancy. In: Proceedings of the 44th Symposium on Theory of Computing, STOC 2012, pp. 1285–1292. ACM, New York (2012)
Matousek, J., Spencer, J.: Discrepancy in arithmetic progressions. Journal of the American Mathematical Society 9, 195–204 (1996)
Roth, K.F.: Remark concerning integer sequence. Acta Arithmetica 9, 257–260 (1964)
Erdős, P.: Some unsolved problems. The Michigan Mathematical Journal 4(3), 291–300 (1957)
Nikolov, A., Talwar, K.: On the hereditary discrepancy of homogeneous arithmetic progressions. CoRR abs/1309.6034v1 (2013)
Gowers, T.: Erdős and arithmetic progressoins. In: Erdős Centennial Conference (2013), http://www.renyi.hu/conferences/erdos100/program.html , (accessed January 29, 2014)
Borwein, P., Choi, S.K.K., Coons, M.: Completely multiplicative functions taking values in { 1, − 1 }. Transactions of the American Mathematical Society 362(12), 6279–6291 (2010)
Mathias, A.R.D.: On a conjecture of Erdős and Čudakov. In: Combinatorics, Geometry and Probability (1993)
Erdős discrepancy problem: Polymath wiki, http://michaelnielsen.org/polymath1/index.php?title=The_Erd (accessed January 29, 2014)
Gowers, T.: Is massively collaborative mathematics possible, http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ (accessed January 29 , 2014)
Konev, B., Lisitsa, A.: Addendum to: A SAT attack on the Erdős discrepancy conjecture, http://www.csc.liv.ac.uk/~konev/SAT14
Biere, A.: Bounded model checking. In: Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185, pp. 457–481. IOS Press (2009)
Biere, A.: Lingeling, Plingeling and Treengeling entering the SAT Competition 2013. In: Proceedings of SAT Competition 2013, pp. 51–52. University of Helsinki (2013)
Balint, A., Belov, A., Heule, M.J.H., Järvisalo, M. (eds.): Proceedings of SAT competition 2013. University of Helsinki (2013)
Audemard, G., Simon, L.: Glucose 2.3 in the SAT 2013 Competition. In: Proceedings of SAT Competition 2013, pp. 42–43. University of Helsinki (2013)
Goldberg, E.I., Novikov, Y.: Verification of proofs of unsatisfiability for CNF formulas. In: Proceedings of Design, Automation and Test in Europe Conference and Exposition (DATE 2003), Munich, Germany, March 3-7, pp. 10886–10891 (2003)
Heule, M.J.H.: DRUP checker, http://www.cs.utexas.edu/~marijn/drup/ (accessed January 29 , 2014)
Konev, B., Lisitsa, A.: A sat attack on the erdos discrepancy conjecture. CoRR abs/1402.2184 (2014)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Konev, B., Lisitsa, A. (2014). A SAT Attack on the Erdős Discrepancy Conjecture. In: Sinz, C., Egly, U. (eds) Theory and Applications of Satisfiability Testing – SAT 2014. SAT 2014. Lecture Notes in Computer Science, vol 8561. Springer, Cham. https://doi.org/10.1007/978-3-319-09284-3_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-09284-3_17
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09283-6
Online ISBN: 978-3-319-09284-3
eBook Packages: Computer ScienceComputer Science (R0)