On the Erdős Discrepancy Problem

DOI10.1007/978-3-319-10428-7_33zbMATH Open1343.68221arXiv1407.2510OpenAlexW132237322MaRDI QIDQ5265097FDOQ5265097

Ronan Le Bras, Bart Selman, Carla P. Gomes

Publication date: 21 July 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: According to the ErdH{o}s discrepancy conjecture, for any infinite $pm1$ sequence, there exists a homogeneous arithmetic progression of unbounded discrepancy. In other words, for any $pm1$ sequence $(x_1,x_2,\mathrm{...})$ and a discrepancy $C$, there exist integers $m$ and $d$ such that $|su{m}_{i=1}^m{x}_{icdotd}|>C$. This is an $80$-year-old open problem and recent development proved that this conjecture is true for discrepancies up to $2$. Paul ErdH{o}s also conjectured that this property of unbounded discrepancy even holds for the restricted case of completely multiplicative sequences (CMSs), namely sequences $(x_1,x_2,\mathrm{...})$ where $x_{acdotb}=x_{a}cdot{x}_b$ for any $a,bgeq1$. The longest CMS with discrepancy $2$ has been proven to be of size $246$. In this paper, we prove that any completely multiplicative sequence of size $127,646$ or more has discrepancy at least $4$, proving the ErdH{o}s discrepancy conjecture for CMSs of discrepancies up to $3$. In addition, we prove that this bound is tight and increases the size of the longest known sequence of discrepancy $3$ from $17,000$ to $127,645$. Finally, we provide inductive construction rules as well as streamlining methods to improve the lower bounds for sequences of higher discrepancies.

Full work available at URL: https://arxiv.org/abs/1407.2510

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Irregularities of distribution, discrepancy (11K38) Arithmetic combinatorics; higher degree uniformity (11B30)

Cited In (5)

• The Erdös discrepancy problem
• Automated streamliner portfolios for constraint satisfaction problems
• Computer-aided proof of Erdős discrepancy properties
• The Erdős discrepancy problem over the squarefree and cubefree integers
• On a problem of Erdős in the theory of irregularities of distribution

This page was built for publication: On the Erdős Discrepancy Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5265097)