View source for 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<n} 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) < \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:
<pre>
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  +  -  -  +  +  -  -  +  -  +  +  -  -  +  +  -  +  -  -  +  +  -  -  +  -  +
</pre>

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 [http://gowers.wordpress.com/2010/02/19/edp8-what-next/#comment-6236 here] whether <math>\sigma_{D} < \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 < \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
<pre>
++---++-
</pre>
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:
<ul>
<li><math>f(0) = 1</math>
<li><math>f(4n+1) = 1</math>
<li><math>f(4n-1) = -1</math>
<li><math>f(2n) = -f(n) (n \geq 1)</math>
</ul>

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 < 4^k</math>:
<ul>
<li><math>(\forall N \geq 0) | \sum_{0 \leq r < N} f(dr \mod 4^k) | \leq k+1</math>
<li><math>\sum_{0 \leq r < 4^k} f(dr \mod 4^k) = 0</math>
</ul>
This follows from the facts that <math>f</math> is multiplicative, <math>\sum_{0 \leq r < 4^k} f(r) = 0</math> (for <math>k \geq 1</math>), and for <math>0 \leq m < 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.