Dynamically Defined Sequences with Small Discrepancy

Abstract

We study the problem of constructing sequences $(x_n{)}_{n=1}^{\infty }$ on $[0,1]$ in such a way that $$D_N^{\ast }=\underset{0\le x\le 1}{\sup }\left|\frac{\left\{1\le i\le N:x_i\le x\right\}}{N}-x\right|$$ is uniformly small. A result of Schmidt shows that necessarily $D_N^{\ast }\gtrsim (\log N)N^{-1}$ for infinitely many $N$ and there are several classical constructions attaining this growth. We describe a type of uniformly distributed sequence that seems to be completely novel: given $\left\{x_1,\dots ,x_{N-1}\right\}$, we construct $x_N$ in a greedy manner $$x_N=\arg \underset{{\min }_k|x-x_k|\ge N^{-10}}{\min }\sum _{k=1}^{N-1}1-\log (2\sin (\pi |x-x_k|)).$$ We prove that $D_N\lesssim (\log N)N^{-1/2}$ and conjecture that $D_N\lesssim (\log N)N^{-1}$. Numerical examples illustrate this conjecture in a very impressive manner. We also establish a discrepancy bound $D_N\lesssim (\log N{)}^d{N}^{-1/2}$ for an analogous construction in higher dimensions and conjecture it to be $D_N\lesssim (\log N{)}^d{N}^{-1}$.