Loading...
Please wait, while we are loading the content...
Similar Documents
Variations on the Erdos Discrepancy Problem
| Content Provider | Semantic Scholar |
|---|---|
| Author | Leong, Alexander |
| Copyright Year | 2012 |
| Abstract | The Erdős discrepancy problem asks, “Does there exist a sequence t = {ti}i=1 with each ti ∈ {−1, 1} and a constant c such that | ∑n i=1 tid| ≤ c for all n, d ∈ N = {1, 2, 3, . . . }?” The discrepancy of t equals supn≥1 | ∑n i=1 tid|. Erdős conjectured in 1957 that no such sequence exists [4]. We examine versions of this problem with fixed values for c and where the values of d are restricted to particular subsets of N. 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 infinite {−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 22 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, b, . . . } 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 infinite 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, . . . } is not for b > 2. We conclude with some open questions and directions for future work. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://uwspace.uwaterloo.ca/bitstream/handle/10012/6432/Leong_Alexander.pdf?isAllowed=y&sequence=1 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
