On the Erdos Discrepancy Problem

According to the Erd\H{o}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,\mathrm{.}\mathrm{.}\mathrm{.})$ and a discrepancy $C$, there exist integers $m$ and $d$ such that $|\sum_{i=1}^m x_{i \cdot d}| > C$\mathrm{.}Thisisan$80$-year-old open problem and recent development proved that this conjecture is true for discrepancies up to $2$. Paul Erd\H{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{.}\mathrm{.}\mathrm{.})$ 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\H{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.