Bounding the discrepancy in terms of the common difference
Many approaches to EDP proceed by considering [math]\displaystyle{ \mathcal{A}_n }[/math], the set of HAPs contained in [math]\displaystyle{ \{1, 2, \ldots, n\} }[/math], and trying to proving a lower bound [math]\displaystyle{ \omega_n }[/math] for the [math]\displaystyle{ \mathcal{A}_n }[/math]-discrepancy problem, where [math]\displaystyle{ \omega_n \to \infty }[/math].
This page is about an alternative approach: instead of building up the set of HAPs by restricting the maximum and letting it tend to infinity, we build it up by restricting the difference and letting that tend to infinity.
That is, we consider [math]\displaystyle{ \mathcal{D}_n }[/math], the set of HAPs with common difference in some set [math]\displaystyle{ D_n \subseteq \mathbb{N}^+ }[/math], where [math]\displaystyle{ D_1 \subseteq D_2 \subseteq \ldots }[/math] and [math]\displaystyle{ \bigcup_n D_n = \mathbb{N}^+ }[/math], and try to prove a lower bound [math]\displaystyle{ \omega_n }[/math] for the [math]\displaystyle{ \mathcal{D}_n }[/math]-discrepancy problem, where [math]\displaystyle{ \omega_n \to \infty }[/math].
The hope is that some of the calculations will be easier in this perspective because we don't have so many 'cut-offs' to worry about. Furthermore, we are forced to work in a more infinitary way from the start. This may be a help or a hindrance.
Many of the natural examples turn out to be a bit nicer if our sequences (and our HAPs) start at zero. So we'll consider infinite sequences [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]. Finally, let [math]\displaystyle{ \sigma_D = \inf_x \sigma_D(x) }[/math]. Ultimately we want to prove that [math]\displaystyle{ \sigma_{\mathbb{N}^+} = \infty }[/math].
An obvious 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 + - - + + - - + - + + - - + + - + - - + + - - + - +
For this sequence we have [math]\displaystyle{ \sigma_d \leq 2^d d! }[/math]. In fact, [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 [math]\displaystyle{ \sigma_{D} \lt \infty }[/math] for [math]\displaystyle{ D = \{ 2^k : k \in \mathbb{N}\} \cup \{3\} }[/math]. He and Tim then both gave examples showing this, 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 show that [math]\displaystyle{ \sigma_D \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?].
Can we find a good lower bound for [math]\displaystyle{ \sigma_{\{1, 2, \ldots, n\}} }[/math]? We can probably do much better than [math]\displaystyle{ 2^n n! }[/math]. Can we achieve sub-exponential growth? It certainly looks that way from the numerical evidence: at any rate, one can (with a simple computer program) find a sequence [math]\displaystyle{ x }[/math] such that [math]\displaystyle{ \sigma_{\{1,2, \ldots, 15\}}(x) = 2 }[/math]. (The sequence found has period 720720, though there are almost certainly examples with smaller periods.) The gap between this and [math]\displaystyle{ 2^{15} 15! }[/math] is so huge that it must surely be possible to prove something here.
