9
$\begingroup$

What is the best possible $\epsilon$ and sequence $(a_n)_{n = 1}^\infty \subset [0, 1]$ we can find such that $$ d_{N}:=\sup_{x\in [0,1]}\inf_{n=1}^N |x-a_n|\leq \frac{1+\epsilon}{N} $$ for all $N\in \mathbb{N}$? Note that dyadic decomposition provides $\epsilon=1$.

$\endgroup$
1
  • 2
    $\begingroup$ I think this is the same as asking for a sequence with lowest possible discrepancy, and a search on that term (or a look through the Kuipers & Niederreiter book on uniform distribution of sequences) should turn up some answers. $\endgroup$ Jun 6, 2016 at 22:52

1 Answer 1

8
$\begingroup$

Let me begin by reformulating the question a little bit, making it precise, and also avoiding what happens for the initial finite number of $N$. Given an infinite sequence $a_n$ in $[0,1]$, for every $N$ let $u_N$ denote the smallest gap between the numbers $a_1$, $\ldots$, $a_N$ (when arranged in ascending order between $0$ and $1$) and let $v_N$ denote the maximum gap. The problem is essentially interested in understanding $v_N/2$ (the point $x$ is halfway between the ends of the maximum gap). The problem as formulated above was studied by A. Ostrowski, de Bruijn and Erdos and also solved (somewhat later) by Toulmin. de Bruijn and Erdos (and Toulmin) showed that for any sequence one has $$ \limsup_{N\to \infty} Nv_N \ge\frac{1}{\log 2} = 1.4426\ldots, $$ and this value is attained for the sequence $$ a_n = \{ \log_2 (2n-1)\}, $$ where $\{ x\}$ stands for fractional part, and $\log_2$ denotes the logarithm to base $2$. They also show that $\liminf_{N\to \infty} Nu_N$ is always at most $1/\log 4$ and this too is attained in the example above. You might also find interesting this related recent paper of Chung and Graham.

My first thought on seeing the problem was sequences of the form $\{ n\theta\}$ for an irrational $\theta$. I think that in this class of examples, the golden ratio $\phi = (1+\sqrt{5})/2$ might be best and gives a normalized largest gap of $\phi^3/\sqrt{5} = 1.8944\ldots$ (if I calculated correctly). This is not as good as Toulmin's example. Nevertheless, you might also find interesting this survey of the three gaps theorem (which appeared in L'Enseignement).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.