A Discrepancy Problem: Balancing Infinite Dimensional Vectors

As a corollary of a general balancing result, we prove that there exists a balanced “2-coloring” g of the set of natural numbers ℕ $$\mathbb{N}$$ such that simultaneously for all integers d ≥ 1, every (finite) arithmetic progression of difference d has discrepancy D g (d) ≤ d 8+ɛ , independently of the starting point and the length of the arithmetic progression. Formally, for every ɛ > 0 there exists a function g : ℕ → { − 1 , 1 } $$g: \mathbb{N} \rightarrow \{-1,1\}$$ such that D g ( d ) = max a ≥ 1 , m ≥ 1 ∑ i = 0 m − 1 g ( a + i d ) ≤ d 8 + 𝜀 $$\displaystyle{ D_{g}(d) =\max _{a\geq 1,m\geq 1}\left \vert \sum _{i=0}^{m-1}g(a + id)\right \vert \leq d^{8+\varepsilon } }$$ for all sufficiently large d ≥ d 0(ɛ). This reduces an old superexponential upper bound ≤ d! of Cantor, Erdős, Schreiber, and Straus to a polynomial upper bound. Note that the polynomial range is the correct range, since a well known result of Roth implies the lower bound D g ( d ) ≥ d ∕ 20 $$D_{g}(d) \geq \sqrt{d}/20$$ for every g : ℕ → { − 1 , 1 } $$g: \mathbb{N} \rightarrow \{-1,1\}$$ .We derive this concrete number theoretic upper bound result about arithmetic progressions from a very general vector balancing result. It is about balancing infinite dimensional vectors in the maximum norm, and it is interesting in its own right (possibly, more interesting than the special case above).