On the Erdos Discrepancy Problem

Abstract

According to the Erdős discrepancy conjecture, for any infinite $\pm 1$ sequence, there exists a homogeneous arithmetic progression of unbounded discrepancy. In other words, for any $\pm 1$ sequence $(x_1,x_2,...)$ and a discrepancy $C$, there exist integers $m$ and $d$ such that $|{\sum }_{i=1}^m{x}_{i\cdot d}|>C$. This is an $80$-year-old open problem and recent development proved that this conjecture is true for discrepancies up to $2$. Paul Erdő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,...)$ where $x_{a\cdot b}=x_a\cdot x_b$ for any $a,b\ge 1$. 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 Erdő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.

8 pages; 0 figure; Submitted on April 14, 2014 to the 20th International Conference on Principles and Practice of Constraint Programming