Counting and Constructing Sequences of Bounded Discrepancy

Abstract

The Erdős Discrepancy Problem states that every infinite ±1 sequence must have unbounded discrepancy with respect to homogeneous arithmetic progressions. In other words, the discrepancy of a ±1 sequence eventually exceeds any constant C. While this conjecture was proved by Terence Tao in 2015, the finite behavior of these sequences remains a subject of computational interest. In 2014, Boris Konev and Alexei Lisitsa used a SAT solver to prove that the length of the longest sequence with discrepancy bounded by C = 2 is 1160. This thesis explores the complementary enumerative question of what its solution count curve might look like. I aim to quantify the number of ±1 sequences of length n ≤ 1160 that have discrepancy at most 2. We first compute exact solution counts for the Erdős C = 2 problem for sequence lengths n in [2, 103] via a bitwise backtracking algorithm. Analyzing this data yields a trajectory prediction model that uses the number of odd constraints at each n to predict the solution tree's branching factor at its corresponding depth n. We apply the stochastic enumeration method to attain estimated counts for n > 103, and use those results to motivate a refined model that predicts branching factors using a continuous 2-adic severity score and an odd prime multiplicity penalty. Calibrated using a weighted least squares regression on a reliable window of pooled actual and stochastic counts for n in [2 , 300], our model achieves a weighted R^2 of 0.74, predicts a solution curve peak of approximately 2^{45.7} sequences at n = 389, and projects sequence extinction between lengths n in [957, 1122], approaching the known extinction point of n = 1161.