Discrepancy one among homogeneous arithmetic progressions. (English) Zbl 1421.11061
Summary: We investigate a restriction of Paul Erdős’ well-known problem from 1936 on the discrepancy of homogeneous arithmetic progressions. We restrict our attention to a finite set \(S\) of homogeneous arithmetic progressions, and ask when the discrepancy with respect to this set is exactly 1. We answer this question when \(S\) has size four or less, and prove that the problem for general \(S\) is NP-hard, even for discrepancy 1.
MSC:
| 11K38 | Irregularities of distribution, discrepancy |
| 11Y16 | Number-theoretic algorithms; complexity |
| 05C38 | Paths and cycles |
| 11B25 | Arithmetic progressions |
References:
| [1] | Cieliebak, M., Eidenbenz, S., Pagourtzis, A.T., Schlude, K.: On the complexity of variations of equal sum subsets. Nordic J. Comput. 14(3), 151-172 (2008) · Zbl 1187.68248 |
| [2] | Erdős, P.: Some unsolved problems. Mich. Math. J. 4, 291-300 (1957) · Zbl 0081.00102 |
| [3] | Konev, B., Lisitsa, A.: A SAT Attack on the Erdős Discrepancy Conjecture. In: Carsten, S., Uwe, E. (eds.) Theory and Applications of Satisfiability Testing—SAT 2014, vol. 8561, Lecture Notes in Computer Science, pp. 219-226. Springer International Publishing, Belin (2014) · Zbl 1343.68217 |
| [4] | Mathias, A.R.D.: On a Conjecture of Erdős and Čudakov. In: Combinatorics, Geometry and Probability, pp. 487-488. Cambridge University Press, Cambridge (1997) (Cambridge Books Online) · Zbl 0874.11010 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
