The Erdős discrepancy problem asks, ;;Does there exist a sequence t = {t_i}_{1≤i<∞} with each t_i ∈ {-1,1} and a constant c such that |∑_{1≤i≤n} t_{id}| ≤ c for all n,c ∈ ℕ = {1,2,3,...}?;;The discrepancy of t equals sup_{n≥1} |∑_{1≤i≤n} t_{id}|. Erdős conjectured in 1957 that no such sequence exists.We examine versions of this problem withfixed values for c and where the values of d are restricted to particular subsets of ℕ. By examining a wide variety of different subsets, we hope to learn more about the original problem.When the values of d are restricted to the set {1,2,4,8,...}, we show that there are exactly two infinite {-1,1} sequences with discrepancy bounded by 1 and an uncountable number of in nite {-1,1} sequences with discrepancy bounded by 2.We also show that the number of {-1,1} sequences of length n with discrepancy bounded by 1 is 2^{s2(n)} where s2(n) is the number of 1s in the binary representation of n.When the values of d are restricted to the set {1,b,b^2,b^3,...} for b > 2, we show there are an uncountable number of infinite sequences with discrepancy bounded by 1.We also give a recurrence for the number of sequences of length n with discrepancy bounded by 1. When the values of d are restricted to the set {1,3,5,7,..} we conjecture that there are exactly 4 in finite sequences with discrepancy bounded by 1 and give some experimental evidence for this conjecture.We give descriptions of the lexicographically least sequences with D-discrepancy c for certain values of D and c as fixed points of morphisms followed by codings.These descriptions demonstrate that these automatic sequences.We introduce the notion of discrepancy-1 maximality and prove that {1,2,4,8,...} and {1,3,5,7,...} are discrepancy-1 maximal while {1,b,b^2,...} is not for b > 2.We conclude with some open questions and directions for future work.
PDF
download
878987797
028-85220240
