# Bounding the discrepancy in terms of the common difference

Many approaches to EDP proceed by considering [math]\mathcal{A}_n[/math], the set of HAPs contained in [math]\{1, 2, \ldots, n\}[/math], and trying to proving a lower bound [math]\omega_n[/math] for the [math]\mathcal{A}_n[/math]-discrepancy problem, where [math]\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]\mathcal{D}_n[/math], the set of HAPs with common difference in some set [math]D_n \subseteq \mathbb{N}^+[/math], where [math]D_1 \subseteq D_2 \subseteq \ldots[/math] and [math]\bigcup_n D_n = \mathbb{N}^+[/math], and try to prove a lower bound [math]\omega_n[/math] for the [math]\mathcal{D}_n[/math]-discrepancy problem, where [math]\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]x : \mathbb{N} \to \{\pm 1\}[/math].

Let [math]\sigma (x) = \sup_n | \sum_{r\ltn} x_r |[/math] (which may be finite or infinite), and [math]\sigma_d (x) = \sigma (T_d(x))[/math] (where [math]T_d(x)[/math] is the sequence defined by [math]T_d(x)_n = x_{dn}[/math]). Let's also write [math]\sigma_D (x) = \sup_{d \in D} \sigma_d(x)[/math], for [math]D \subseteq \mathbb{N}^+[/math]. Finally, let [math]\sigma_D = \inf_x \sigma_D(x)[/math]. Ultimately we want to prove that [math]\sigma_{\mathbb{N}^+} = \infty[/math].

An obvious question is whether there is a sequence [math]x[/math] such that [math]\sigma_d(x)[/math] is finite for all [math]d[/math]. There is: we can take [math]x_n = (-1)^{\nu(n)}[/math] where [math]\nu(n) = \sum_{k=0}^\infty \lfloor \frac{n}{2^k k!} \rfloor[/math]. It is easy to check by induction that [math]\sigma_d(x) \lt \infty[/math]: [math]x[/math] is the pointwise limit of periodic sequences [math]x_k = \xi_k \xi_k \ldots[/math] (concatenation of finite blocks) where the length of [math]\xi_k[/math] is [math]2^k k![/math] and [math]\sum_{\{n : d \mid n\}} (\xi_k)_n = 0[/math] for all [math]d \leq k[/math]. The block [math]\xi_k[/math] is formed by concatenating [math]2k[/math] copies of [math]\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]\sigma_d \leq 2^d d![/math]. In fact, [math]\sigma_1 = 1[/math], [math]\sigma_2 = 1[/math], [math]\sigma_3 = 4[/math], [math]\sigma_4 = 2[/math], [math]\sigma_5 = 22[/math], [math]\sigma_6 = 3[/math], [math]\sigma_7 = 251[/math], [math]\sigma_8 = 1[/math], [math]\sigma_9 = 28[/math], [math]\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]x_n = (-1)^{\nu(n)}[/math] where [math]\nu(n) = \sum_{k=0}^\infty \lfloor \frac{n}{2^k} \rfloor[/math], and which satisfies [math]\sigma_{2^k} = 1[/math] for all [math]k[/math], but [math]\sigma_3 = \infty[/math].

Sune asked here whether [math]\sigma_{D} \lt \infty[/math] for [math]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]D = \{ 2^k : k \in \mathbb{N}\} \cup D_1[/math] for any finite set [math]D_1[/math].

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

It seems quite easy to show that [math]\sigma_D \lt \infty[/math] where [math]D[/math] is the set of [math]M[/math]-smooth numbers (for example, [math]\{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]\sigma_{\{1, 2, \ldots, n\}}[/math]? We can probably do much better than [math]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]x[/math] such that [math]\sigma_{\{1,2, \ldots, 16\}}(x) = 2[/math]. (The sequence found has period 720720, though there are almost certainly examples with smaller periods.) The gap between this and [math]2^{16} 16![/math] is so huge that it must surely be possible to prove *something* here.

It is interesting to look for sequences with small periods and small [math]\sigma_D[/math]. The period-8 sequence

++---++-

repeated indefinitely, has [math]\sigma_{\{1,2,3,4,5,6,7\}}(x) = 2[/math]. What is the sequence of shortest period with [math]\sigma_{\{1,2,3,4,5,6,7,8\}} = 2[/math]? Number-crunching shows that the minimal period must be at least 160, and at most 1680.

Define the function [math]f : \mathbb{N} \to \{\pm 1\}[/math] by:

- [math]f(0) = 1[/math]
- [math]f(4n+1) = 1[/math]
- [math]f(4n-1) = -1[/math]
- [math]f(2n) = -f(n) (n \geq 1)[/math]

This is somewhat similar to the definition of the Walters sequence. To find [math]f(n)[/math], we write [math]n[/math] in base 4 and look at its last nonzero digit. If it is a 1 then [math]f(n) = 1[/math]; if it is a 3 then [math]f(n) = -1[/math]. If it is a 2, look at the preceding digit. If that digit is even then [math]f(n) = -1[/math]; if it is odd then [math]f(n) = 1[/math].

The sequence [math]f(n)[/math] has slow-growing discrepancy (around [math]\log_4 n[/math]). It is completely multiplicative, with [math]f(2)=-1[/math], [math]f(p)=1[/math] if [math]p \equiv 1 (\mod 4)[/math] and [math]f(p)=-1[/math] if [math]p \equiv -1 (\mod 4)[/math]. It seems to allow us to generate sequences with small [math]\sigma_D[/math]. Let [math]f_k[/math] be the sequence defined by repeating the first [math]4^k[/math] terms of [math]f[/math] indefinitely: that is, [math]f_k(n) = f(n \mod 4^k)[/math]. Then [math]\sigma_{\{1, 2, \ldots, 4^k-1\}}(f_k) = k+1[/math]. To be precise, for all [math]k \geq 0, 1 \leq d \lt 4^k[/math]:

- [math](\forall N \geq 0) | \sum_{0 \leq r \lt N} f(dr \mod 4^k) | \leq k+1[/math]
- [math]\sum_{0 \leq r \lt 4^k} f(dr \mod 4^k) = 0[/math]

This follows from the facts that [math]f[/math] is multiplicative, [math]\sum_{0 \leq r \lt 4^k} f(r) = 0[/math] (for [math]k \geq 1[/math]), and for [math]0 \leq m \lt 4^k[/math], [math]f(4^k a + m)[/math] is equal to [math]f(a)[/math] if [math]m=0[/math], [math](-1)^{a+1}[/math] if [math]m = 4^k/2[/math], and [math]f(m)[/math] otherwise.