Bounding the discrepancy in terms of the common difference

Many approaches to EDP proceed by considering HAPs contained in [math]\displaystyle{ \{1, 2, \ldots, n\} }[/math], proving something about that discrepancy problem, and then letting [math]\displaystyle{ n \to \infty }[/math]. This page is about an alternative approach: the idea is to consider HAPs with common difference in some set [math]\displaystyle{ D_n \subseteq \mathbb{N}^+ }[/math], where [math]\displaystyle{ \bigcup_n D_n = \mathbb{N}^+ }[/math], prove something about the [math]\displaystyle{ D_n }[/math]-discrepancy problem, and then let [math]\displaystyle{ n \to \infty }[/math].

Many of the natural examples turn out to be a bit nicer if our sequences (and our HAPs) start at zero. So, given an infinite sequence [math]\displaystyle{ x : \mathbb{N} \to \{\pm 1\} }[/math], let [math]\displaystyle{ \sigma (x) = \sup_n | \sum_{r\lt n} x_r | }[/math] (which may be finite or infinite), and [math]\displaystyle{ \sigma_d (x) = \sigma (T_d(x)) }[/math] (where [math]\displaystyle{ T_d(x) }[/math] is the sequence defined by [math]\displaystyle{ T_d(x)_n = x_{dn} }[/math]). Let's also write [math]\displaystyle{ \sigma_D (x) = \sup_{d \in D} \sigma_d(x) }[/math], for [math]\displaystyle{ D \subseteq \mathbb{N}^+ }[/math]. Ultimately we want to prove that [math]\displaystyle{ \sigma_{\mathbb{N}^+}(x) = \infty }[/math].

An obvious first question is whether there is a sequence [math]\displaystyle{ x }[/math] such that [math]\displaystyle{ \sigma_d(x) }[/math] is finite for all [math]\displaystyle{ d }[/math]. There is: we can take [math]\displaystyle{ x_n = (-1)^{\nu(n)} }[/math] where [math]\displaystyle{ \nu(n) = \sum_{k=0}^\infty \lfloor \frac{n}{2^k k!} \rfloor }[/math]. It is easy to check by induction that [math]\displaystyle{ \sigma_d(x) \lt \infty }[/math]: [math]\displaystyle{ x }[/math] is the pointwise limit of periodic sequences [math]\displaystyle{ x_k = \xi_k \xi_k \ldots }[/math] (concatenation of finite blocks) where the length of [math]\displaystyle{ \xi_k }[/math] is [math]\displaystyle{ 2^k k! }[/math] and [math]\displaystyle{ \sum_{\{n : d \mid n\}} (\xi_k)_n = 0 }[/math] for all [math]\displaystyle{ d \leq k }[/math]. The block [math]\displaystyle{ \xi_k }[/math] is formed by concatenating [math]\displaystyle{ 2k }[/math] copies of [math]\displaystyle{ \xi_{k-1} }[/math] with alternating signs. The sequence starts:

n    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 
x_n  +  -  -  +  +  -  -  +  -  +  +  -  -  +  +  -  +  -  -  +  +  -  -  +  -  +

This sequence turns out to have [math]\displaystyle{ \sigma_1 = 1 }[/math], [math]\displaystyle{ \sigma_2 = 1 }[/math], [math]\displaystyle{ \sigma_3 = 4 }[/math], [math]\displaystyle{ \sigma_4 = 2 }[/math], [math]\displaystyle{ \sigma_5 = 22 }[/math], [math]\displaystyle{ \sigma_6 = 3 }[/math], [math]\displaystyle{ \sigma_7 = 251 }[/math], [math]\displaystyle{ \sigma_8 = 1 }[/math], [math]\displaystyle{ \sigma_9 = 28 }[/math], [math]\displaystyle{ \sigma_{10} = 20 }[/math].

The construction of the above sequence is similar in spirit to that of the Thue-Morse sequence, which is given by the similar-looking formula [math]\displaystyle{ x_n = (-1)^{\nu(n)} }[/math] where [math]\displaystyle{ \nu(n) = \sum_{k=0}^\infty \lfloor \frac{n}{2^k} \rfloor }[/math], and which satisfies [math]\displaystyle{ \sigma_{2^k} = 1 }[/math] for all [math]\displaystyle{ k }[/math], but [math]\displaystyle{ \sigma_3 = \infty }[/math].

Sune asked here whether we could have [math]\displaystyle{ \sigma_{D}(x) \lt \infty }[/math] for [math]\displaystyle{ D = \{ 2^k : k \in \mathbb{N}\} \cup \{3\} }[/math]. He and Tim then both gave examples, based on the Thue-Morse sequence, which look as if they should generalize to [math]\displaystyle{ D = \{ 2^k : k \in \mathbb{N}\} \cup D_1 }[/math] for any finite set [math]\displaystyle{ D_1 }[/math].

That question was asked in the context of a harder question: whether [math]\displaystyle{ \sigma_d }[/math] could be uniformly bounded for [math]\displaystyle{ d }[/math] a power of 2 or a prime. This remains unanswered.

It seems quite easy to arrange for [math]\displaystyle{ \sigma_D (x) \lt \infty }[/math] where [math]\displaystyle{ D }[/math] is the set of [math]\displaystyle{ M }[/math]-smooth numbers (for example, [math]\displaystyle{ \{2^a 3^b 5^c : a, b, c \in \mathbb{N}\} }[/math]). This has been briefly discussed on the EDP blog [link?].

The character-like sequences, such as the Walters example, have [math]\displaystyle{ \sigma_D \lt \infty }[/math] where [math]\displaystyle{ D }[/math] is the set of non-multiples of a certain prime.

We have yet to find an example of a sequence where [math]\displaystyle{ \sigma_D \lt \infty }[/math] for a set [math]\displaystyle{ D }[/math] of density 1.

It could be interesting to think about how small we can make [math]\displaystyle{ \sigma_{\{1, 2, \ldots, n\}}(x) }[/math], as a function of [math]\displaystyle{ n }[/math].