Counting Sequences with Small Discrepancies

Abstract

The Erdős discrepancy problem asks, “Does there exist an infinite sequence (t_i ) _i⩾1 taking values in {−1, 1} and a constant c such that |∑_1⩽i⩽n t_id |⩽c for all ?” Erdős conjectured in the 1930s that no such sequence exists. We examine some variations of this problem with fixed values for c in which the values of d are restricted to particular subsets of . When the values of d are restricted to powers of 2, we show that there are exactly two infinite sequences with discrepancy bounded by 1 and an uncountable number of infinite sequences with discrepancy bounded by 2. When the values of d are restricted to the powers of b for b>2, we show that there is 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 odd numbers, we conjecture that there are exactly four infinite sequences with discrepancy bounded by 1 and give some experimental evidence for this conjecture.

2000 AMS Subject Classification:

• 11B85

Keywords:

• sequences
• Thue-Morse sequence
• discrepancy
• Mersenne primes

ACKNOWLEDGMENTS

We thank the referee for helpful comments, and Kevin Hare for allowing us to use his idea for the proof of Theorem 3.4.