On the Erdős discrepancy problem

DOI10.1007/978-3-319-10428-7_33MaRDI QIDQ5265097zbMATH OpenOpenAlexFDO

Authors Ronan Le Bras, Carla P. Gomes, Bart Selman

Publication date 21 July 2015

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

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)

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.

Recommendations

• Computer-aided proof of Erdős discrepancy properties
• Counting sequences with small discrepancies
• A SAT attack on the Erdős discrepancy conjecture
• Tao's resolution of the Erdős discrepancy problem
• The Erdös discrepancy problem

Cited in

(11)

• Computer-aided proof of Erdős discrepancy properties
• The Erdős discrepancy problem over the squarefree and cubefree integers
• scientific article; zbMATH DE number 3997928 (Why is no real title available?)
• Automated streamliner portfolios for constraint satisfaction problems
• On a problem of Erdős in the theory of irregularities of distribution
• Counting sequences with small discrepancies
• A SAT attack on the Erdős discrepancy conjecture
• Good weights for the Erdős discrepancy problem
• Discrepancy one among homogeneous arithmetic progressions
• Tao's resolution of the Erdős discrepancy problem
• The Erdös discrepancy problem

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)