On the Erdoes Discrepancy Problem

摘要

According to the Erdos discrepancy conjecture, for any infinite ±1 sequence, there exists a homogeneous arithmetic progression of unbounded discrepancy. In other words, for any ±1 sequence (x_1, x_2, ...) and a discrepancy C, there exist integers m and d such that | ∑_(i=1)~m x_(i·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 Erdos also conjectured that this property of unbounded discrepancy even holds for the restricted case of completely multiplicative sequences, namely sequences (x_1,x_2,...) where x_ (a·b)= x_a · x_b for any a,b ≥ 1. The longest such sequence of 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 ErdSs discrepancy conjecture for discrepancy 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.