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$ ?



sequences of real numbers
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$.


