How to prove that $\limsup_{n\to\infty}n M_n\geq 1/\ln 2$ for the following sequence?

Question

Let $(x_i)_i$ be a sequence of distinct numbers in $[0,1]$. Note that $[0, 1] \setminus \{x_1, \cdots, x_{n-1} \}$ can be written as a disjoint union of non-empty and non-singleton intervals $C_{n, k}$. Let $M_n \equiv \max_k |C_{n,k}|$.

How do I prove that $\limsup\limits_{n \to \infty} n M_n\geq 1/\ln 2$?

Answer 1

If the sequence is strictly increasing then the limit is always $\infty$.

So the sequence is convergent and Cauchy.

Let $|C_{n,0}|=s_1-0=s_1>0$.

Then there exist an integer $N$ such that for each $l,l-1>N$, then

$|C_{n,l}|=|s_l-s_{l-1}|<|C_{n,0}|$

So

$|M_n|=max\{|C_{n,k}|: k<N\}\geq |C_{n,0}|=s_1$ for each $n\in \mathbb{N}$

This means

$n|M_n|\geq ns_1\to \infty$

In general I think it is not true and a counter-example can be the following:

You consider the succession:

$\{1, \frac{1}{2},\frac{1}{4},\frac{3}{4}, \frac{1}{8},\frac{3}{8},\frac{5}{8}\dots\}$

You can observe that, fixed $k\in \mathbb{N}$ , for $n=k+2^k$ the set $[0,1]$ is divided into $2^k$ parts of diameter $\frac{1}{2^k}$, for example:

1. k=0:

Then $n=1$, that means

$[0,1]/ \{1,\frac{1}{2}\}=[0,\frac{1}{2})\cup(\frac{1}{2},1)$

2. k=1:

Then $n=3$, that means

$[0,1]/\{1,\frac{1}{2},\frac{1}{4},\frac{3}{3}\}=[0,\frac{1}{4})\cup (\frac{1}{4},\frac{1}{2})\cup (\frac{1}{2},\frac{3}{4})\cup (\frac{3}{4},1)$

Thus if you consider the subsequence

$\{s_{k+2^k}\}_{k\in\mathbb{N}\cup\{0\}}$

you have

$|C_{k+2^k, i}|=\frac{1}{2^k}$ for each $i$ so

$|M_{k+2^k}|=\frac{1}{2^k}$

By contradiction, if

$\lim sup_{n\to \infty}n|M_n|\geq \frac{1}{ln(2)}$

Then each subsequence verifies that inequality, but

$\lim sup_{k\to \infty}(k+2^k)|M_{k+2^k}|=$

$= \lim sup_{k\to \infty}\frac{(k+2^k)}{2^k}=0+1=1<\frac{1}{ln(2)}$

Answer 2

Shown by N. G. de Bruijn and P. Erdős in $1949$ (I've found it in TAoCP vol. $2$ exercise $3.5.20$).

Let $\ell_n^{(1)}\geqslant\ell_n^{(2)}\geqslant\dots\geqslant\ell_n^{(n)}$ be the lengths of the intervals (that form $[0,1]\setminus\{x_1,\dots,x_{n-1}\}$). Then (the crucial observation) for any $1<k\leqslant n$ we have $\ell_n^{(k)}\leqslant\ell_{n+1}^{(k-1)}$. By induction, for any $1\leqslant k\leqslant n$ we have $\ell_n^{(k)}\leqslant\ell_{n+k-1}^{(1)}=M_{n+k-1}$. Let $L_n=\max\{kM_k:n\leqslant k<2n\}$; then $$1=\sum_{k=1}^n\ell_n^{(k)}\leqslant\sum_{k=1}^n M_{n+k-1}\leqslant L_n\underbrace{\sum_{k=1}^n\frac1{n+k-1}}_{\to\,\ln2\text{ as }n\to\infty},$$ giving $\limsup\limits_{n\to\infty}L_n\geqslant1/\ln 2$, which implies the claimed $\limsup\limits_{n\to\infty}nM_n\geqslant1/\ln2$.