sequences of real numbers

Question

Let $\lbrace x_i\rbrace_{i=1}^\infty$ be a sequence of distinct numbers in $(0,1)$. For any $n$ after deleting $x_1,...,x_n$ from $[0,1]$ we get $n+1$ subintervals. Let $a_n$ be the maximum length of these subintervals. Is there any sharp lower bound for $\limsup_n na_n$ ?

Answer 1

Here is how to achieve $1/\ln 2$. It is a modification of Harald's construction. We take the sequence $1/2$, $1/4$, $3/4$, etc. and apply the transformation $x \to \ln (1+x)/\ln 2$.

So the sequence is $\ln(3/2)/\ln(2), \ln(5/4)/\ln (2),\ln(7/4)/\ln(2),\dots$

The general terms is $x_n$ for $n=2^a+b$ with $b<2^a$ is

$$\ln \left( \frac{2^{a+1} + 2 b+1}{2^{a+1}}\right)$$

or, equivalently

$$\frac{\ln( 2^{a+1}+2 b + 1)}{\ln(2)} - a-1$$

Then after $n = 2^a + b$ steps for $b<2^a$, we will have just added the cut $(2 b+1 ) /(2^{a+1})$, the largest interval will be

$$\left[\frac{\ln( 2^{a}+2 b + 1)}{\ln(2)} - a, \frac{\ln( 2^{a}+2 b + 2)}{\ln(2)} - a\right] $$

whose length is:

$$\frac{ \ln \left(1 + \frac{1}{2^{a}+b+1}\right)}{\ln 2}$$

If we multiply by $2^a+b+1$, the $\lim\sup$ is $1/\ln 2$.

To show this is optimal, form a binary tree where the vertices are intervals that appear at any point in a sequence. Each interval at some point splits into two intervals, which gives the tree structure. Label each vertex with the step at which it splits. For any $\beta>\lim\sup n a_n$, for all but finitely many vertices, the length of the interval labeled $n$ is at most $\beta/n$. The sum of the lengths of the intervals on each row is $1$, so the sum of the first $k$ rows is $k$.

Thus $k$ is at most the sum over $2^k-1$ distinct numbers $n$ of $\beta/n$ plus a constant coming from the finitely many vertices where the length is not at most $\beta/n$. So $k$ is at most the sum over the first $2^k-1$ numbers of $\beta/n$ plus a constant, which is at most $\beta k \ln 2$ plus a constant. So $\beta\geq 1/\ln 2$.

So $\lim\sup n a_n \geq 1/\ln 2$.

Answer 2

Added: As John Bentin mentions it is in fact known that the result I mentioned below for the dispersion and thus the $1/\log 2$ of OP (mentioned in now deleted comments) is optimal.

This appears originally in Niederreiter, On a measure of denseness for sequences. In: Topics in classical number theory, North-Holland, Amsterdam, 1984.

An easier accssible source is the book by Niederreiter 'Random Number Generation and Quasi Monte Carlo Methods' (SIAM, 1992). There it is Theorem 6.7.

That there cannot be a better sequence is due to Niederreiter, but the example given there showing it is optimal is attributed to Ruzsa. The example there is $x_1 = 1$ and then $$x_n = \left \{ \frac{\log (2n-3)}{ \log 2} \right \}.$$

The above mentioned book is available as a scan from Niederreiter's webspace (note is about 10Mb).

---

In a comment I mentioned the key-word low discrepancy sequence, which indeed is related, but the better key-word and really what is asked for is a low dispersion sequence.

The dispersion of a finite point $P=\{x_1, \dots , x_n\}$ set in some ambient space $S$ is defined as the supremum over all $x \in S$ of $\min_i d(x,x_i)$ where in the paper I quote the $d$ is the infinity-norm (but since be are in 1-d it does not matter so much).

And, then for a sequence one considers the dispersion of the intial segements. Thus the limes superior of $n$ times the dispersion of the first $n$ elements of the sequence is just half of what is asked here (actually, one one might have to be slightly careful to include 0 and 1 to be save and thus multiply by $n+2$, but asymptically this does not change anything).

This notion of disperson, it appears, was introduce by Niederreiter and in his paper 'Low-discrepancy and low-dispersion sequences' (J. Number Th., 1987), see at the very end, he reports that the then best construction of a low dispersion sequence yields a $1/\log 4$ which indeed is just half of the $1/\log 2$ that OP reports. (The construction is not in this paper of Niederreiter but he quotes it; I should add that the result is for arbitrary dimesion the 1-d case might or might not be older).

There seems to be various related work so one might find more with more extended searches.

Answer 3

Edit: here is a simple proof that $\alpha := \inf \limsup n a_n \geq 1/\ln 2$. Note that this edit is made after solutions have been given in other answers.

Let us consider the sequence of lengths of the subintervals at some step $n$, in decreasing order: $\ell_0\geq\ell_1\geq\dots\geq\ell_n$ so that $\ell_0=a_n$. Assume that we look at one of the worst steps, so that $k a_k\leq n a_n$ for all $k>n$. Then $j$ step later, there is at least one subinterval of length $\ell_j$, since not all longest one can have been subdivided. That implies $$ \ell_j \leq \ell_0\frac{n}{n+j} = a_n\frac{1}{1+j/n}$$

Moreover, the sum of the $\ell_\ast$ must be $1$, so that $$1=\sum \ell_j \leq a_n\sum_j \frac{1}{1+j/n} \sim a_n \cdot n\int_0^1\frac{\mathrm{d}t}{1+t}= na_n \ln 2$$ This proves $\limsup n a_n \geq 1/\ln 2$.

We also get a hint on how to realize it: at each step, divide the longest interval in a way that makes the distribution of length closest to the profile $t\mapsto \frac1{1+t}$ over $[0,1]$.

---

This is not a complete answer, but non-matching upper and lower bound for $\alpha := \inf \limsup n a_n$ (where the infimum is on $\{x_n\}$ and the supremum limit on $n$):

$$\frac12+\frac1{\sqrt{2}} \simeq 1,207 \leq \alpha \leq \frac{1+\sqrt{5}}2 \simeq 1,618$$

For the lower bound: let $\{x_n\}$ be fixed and assume that for big enough $n$, all pieces have length at most $a/n$ (where $a\geq1$). Let $\psi$ be a number less than $1$ to be optimized later on, let me ignore roundoff errors that are negligible, and look at the $n\psi$-th largest piece at step $n$. Denote its length by $\ell$: the total length of the pieces is $1$ and is also at most $a/n\cdot n\psi+\ell n(1-\psi)$, so that $$\ell \geq \frac{1-a\psi}{1-\psi}\cdot\frac1n.$$ Since there are at least $\psi n$ pieces of size at least $\ell$, at a step of the order of $n+\psi n$ there will be one such piece remaining. Therefore we have $$\frac a{n+\psi n} \geq \frac{1-a\psi}{1-\psi}\cdot\frac1n$$ from which it comes $$a\geq \frac{1+\psi}{1+\psi^2}.$$ Optimizing in $\psi$ gives the desired lower bound.

For the upper bound: we seek a way to achieve $\limsup n a_n=\phi$ where $\phi=\frac{1+\sqrt{5}}2$ is the golden ratio.

Fix $\lambda \leq 1/2$, and construct $\{x_n\}$ inductively so as to cut at each step the largest interval in two parts of lengths in the ratio $\lambda:1-\lambda$. To simplify the analysis, then choose $\lambda$ so that $(1-\lambda)^2=\lambda$ (i.e. take $\lambda=\frac{3-\sqrt{5}}2$). With this choice, we get that at each step $n$ all pieces are of lengths $\lambda^k$ or $\lambda^{k-1}(1-\lambda)$, for some $k$ that depends only on $n$.

Rather than express $k$ in function of $n$, let us consider the worse case: there are $n$ pieces of length $\lambda^k$ and only one of length $\lambda^{k-1}(1-\lambda)$. Then as the sum of the lengths is $1$, writing $\ell=\lambda^k$ and noticing $\phi=\frac{1-\lambda}{\lambda}$, we can compute $\ell=\frac{1}{n+\phi}$ so that (for those $n$ when we are in the worst-case scenario): $$n a_n = \frac{n\phi}{n+\phi}\to\phi.$$