A Discrepancy Problem: Balancing Infinite Dimensional Vectors

József Beck ()
Additional contact information
József Beck: Rutgers University, Department of Mathematics

A chapter in Number Theory – Diophantine Problems, Uniform Distribution and Applications, 2017, pp 61-82 from Springer

Abstract: 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 : ℕ → { − 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).

Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-319-55357-3_3

Ordering information: This item can be ordered from
http://www.springer.com/9783319553573

DOI: 10.1007/978-3-319-55357-3_3

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().