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.

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}$.

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