Advertisement
Published in:
2017 | OriginalPaper | Chapter
A Discrepancy Problem: Balancing Infinite Dimensional Vectors
Author : József Beck
Published in: Number Theory – Diophantine Problems, Uniform Distribution and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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: \mathbb{N} \rightarrow \{-1,1\}\) such that 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) \geq \sqrt{d}/20\) for every \(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).
$$\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 } }$$