Skip to main content
3 of 10
added 506 characters in body
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763

This post will prove an upper bound of $1/(4-2 \sqrt{2}) \approx 0.854$, improving slightly on Christian Remlings $0.87$.

Consider $M < N < 2M$. At time $M$, there are $M$ intervals, each of length $\geq \mu/M$. Let $S$ be the number of those intervals which are subdivided at time $N$, we have $S \leq N-M$. So $M-S$ intervals remain undivided. We have $$(M-S) \frac{\mu}{M} + (N-M+S) \frac{\mu}{N} \leq 1.$$ Letting $S$ go all the way up to $N-M$ makes $\mu$ as large as possible; in this case we have $$(2M-N)\frac{\mu}{M} + (2N-2M) \frac{\mu}{M} \leq 1.$$ Taking $N = \sqrt{2} M$, we get $$(4-2 \sqrt{2}) \mu \leq 1 \ \mbox{so} \ \mu \leq 1/(4-2 \sqrt{2}).$$


We can push further. Consider times $N_1$, $N_2=\sqrt[3]{2} N_1$ and $N_3= \sqrt[3]{4} N_1$. It turns out $\mu$ is as large as possible if we subdivide intervals from time $N_1$ at all opportunities, rather than further subdividing already subdivided intervals. This means that, at time $N_3$, there will be $N_1-(N_3-N_1)=2 N_1-N_3$ intervals of size at least $\mu/N_1$, $2 N_2-2 N_1$ of size at least $\mu/N_2$ and $2 N_3-2N_2$ of size at least $\mu/N_3$. This gives $(6-3 \sqrt[3]{4}) \mu \leq 1$ or $\mu \leq 0.808$.

I need to think a little more carefully to make sure that it is still always optimal to subdivide intervals from time $N_0$ rather than resubdivide, but the plausible generalization is to use $r$ time steps at $N_k = 2^{k/r} N_0$ (for $0 \leq k \leq r-1$) and get $$\mu \left( \frac{2 N_0 - N_{r-1}}{N_0} + \frac{2 N_1 - 2 N_0}{N_1} + \cdots + \frac{2 N_{r-1} - 2 N_{r-2}}{N_{r-1}} \right) \leq 1.$$ This gives $$(2r - r 2^{(r-1)/r}) \mu \leq 1$$ and $$\mu \leq \frac{1}{2r(1-2^{-1/r})} = \frac{1}{\log 4}.$$

David E Speyer
  • 156.2k
  • 14
  • 419
  • 763