I have stumbled upon a question which naturally arises when trying to bin a set of $n$ points into equispaced bins such that they are sufficiently well separated from the bin edges.

Take $n$ points $x_1, ..., x_n$ in the unit interval $[0, 1]$. Define a uniform grid of size $L$ on $[0, 1]$ as the set of points $y_l = l/L$ for $l = 1, ..., L-1$ where the endpoints are not included. Can we show that there exists a constant $c > 0$ such that there are infinitely many grid sizes $L$ where
\begin{align*}
\min_{k = 1, ..., n}\min_{l = 1, ..., L}|x_k - y_l| \geq \frac{c}{L}.
\end{align*}

I have been attempting to prove this in many different ways and have failed. Except in the simple case where all $x_k$ are rational in which case they can all be reduced to a common denominator and L can be chosen coprime to it.

While attempting to solve this problem I have noticed several important facts. First it is clear that if c exists, it cannot be larger than $\frac{1}{2}$ since every $x_k$ is within $\frac{1}{2L}$ of a grid point. Using the simultaneous version of [Dirichlet's Theorem on Diophantine approximation][1] it is possible to show that the minimal distance to a grid point can be bounded below by $L^{-(n+1)}$ but this is very weak compared to the desired lower bound of $L^{-1}$. I believe the issue with applying Diophantine approximation theory to this problem is that it focuses on best approximations or attempts to construct sequences of rationals that converge as fast as possible to an irrational number.

Remarkably, this statement is hard to prove even for one number $n = 1$ in the unit interval. Namely, for any $x \in [0, 1]$ does there exist an infinite set of denominators $L$ such that for each $L$ the closest rational $\frac{p}{L}$ to x is at least $\frac{c}{L}$ away? This is related to but different from [badly approximable numbers][2] because these are defined to hold for all denominators $L$ and the desired lower bound is of order $L^{-2}$ instead of $L^{-1}$.

Forgetting entirely about Diophantine approximations, we can just study this simplified question for $n = 1$ by looking at some examples. It turns out (as mentioned in the answer to [this question][3]) that the "hardest" numbers x for which such a lower bound is difficult to derive, are those whose base $b$ representation only consist of $0$ and $b$ and whose terms alternate in larger and larger sequences of $0$'s and $b$'s. The intuition for this is that for a digit like $x = 0.090099000999...$, looking at its 2nd position, its closest rational multiple of $1/100$ from above is $0.1$ which is quite well separated from $x$. However, its closest rational multiple of $1/100$ from below is $0.09$ which is very close to $x$. The same issues arise if we look at decimal positions $k$ which contain zeros. Of course, a natural question is perhaps instead of approximating this unfortunate number $x$ in base $10$, there is another base $b$ which would have better approximation properties.

As you can see, I've thought too much about this problem. Intuitively this statement should be true, but I have had no success in developing a proof. Any help would be greatly appreciated!


  [1]: https://en.wikipedia.org/wiki/Dirichlet%27s_approximation_theorem
  [2]: https://en.wikipedia.org/wiki/Diophantine_approximation#Badly_approximable_numbers
  [3]: https://mathoverflow.net/questions/135887/approximation-by-binary-fractions?rq=1