Is the sum of minimum distances of a bounded sequence in $\mathbb{R}^d$ convergent?

Question

Let $d\in\mathbb{N};\ $ let $ x_n \in \mathbb{R^d}\ \forall\ n\in\mathbb{N},\ $ with $(x_n)_{n=1}^{\infty}$ bounded. Let $(t_n)_{n=1}^{\infty}$ be the sequence obtained from $\left(\displaystyle\min_{1\leq i<j \leq k} \vert x_i - x_j \vert \right)_{k=2}^{\infty} $ by deleting repetitions (and so $(t_n)_{n=1}^{\infty}$ is strictly decreasing). Does $\displaystyle\sum_{n=1}^{\infty} t_n$ converge?

I think it's true for $d=1,$ but even in this case, I'm having a hard time formulating a proof. Any ideas?

Answer 1

Claim. There exists a bounded sequence $(x_n)_{n=1}^{\infty}$ in $\mathbb{R}$ such that, if $t_n = \min_{1 \leq i < j \leq n} |x_j - x_i|$ for $n \geq 2$, then $$ t_2 > t_3 > t_4 > \ldots \qquad\text{but}\qquad \sum_{n=2}^{\infty} t_n = \infty. $$

Idea of Proof. We will construct such an $(x_n)_{n=1}^{\infty}$ via the following steps:

1. Construct $(y_n)_{n=1}^{\infty}$ so that the corresponding $\tilde{t}_n = \min_{1 \leq i < j \leq n} |y_j - t_i|$ is non-increasing and satisfies $\sum_{n=2}^{\infty} \tilde{t}_n = \infty$. (We will construct such an $(y_n)$ by enumerating dyadic rationals in $[0, 1]$ in the "lexicographic order".)

2. Slightly perturb $(y_n)_{n=1}^{\infty}$ to define $(x_n)_{n=1}^{\infty}$ so that the corresponding $t_n$ is strictly decreasing but not so different from $\tilde{t}_n$.

---

Construction.

1. Define $(y_n)_{n=1}^{\infty}$ by

   $$ (y_n)_{n=1}^{\infty} = \bigl(0, 1, \underbrace{\tfrac{1}{2}}, \underbrace{\tfrac{1}{4}, \tfrac{3}{4}}, \underbrace{\tfrac{1}{8}, \tfrac{3}{8}, \tfrac{5}{8}, \tfrac{7}{8}}, \ldots, \underbrace{\tfrac{1}{2^p}, \tfrac{3}{2^p}, \ldots, \tfrac{2^p-1}{2^p}}, \ldots \bigr). $$

2. Choose a concave increasing function $f : [0, 1] \to \mathbb{R}$ such that $\frac{1}{2} < f'(x) < 1$ for all $x \in (0, 1)$. For example, we may set $f(x) = x - \frac{1}{4}x^2$.

3. Set $x_n = f(y_n) $.

Now we verify that the resulting $(t_n)$ satisfies the desired conclusion. Let $p \geq 1$ and $1 \leq k \leq 2^{p-1}$ be such that $y_n = \frac{2k-1}{2^p}$. Then for any $1 \leq i < j \leq n$, we have:

• $|y_j - y_i| \geq \frac{1}{2^p}$.

• If $|y_j - y_i| > \frac{1}{2^p}$, then $|y_j - y_i| \geq \frac{1}{2^{p-1}}$. Hence, there exists $\xi$ between $y_i$ and $y_j$ such that \begin{align*} |x_j - x_i| &= |f(y_j) - f(y_i)| \geq f'(\xi)|y_j - y_i| > \frac{1}{2}|y_j - y_i| \geq \frac{1}{2^p}. \end{align*}

• $|y_j - y_i| = \frac{1}{2^p}$, then there exists $l \in \{1, 2, \ldots, 2k\}$ such that $\{y_i, y_j\} = \{\frac{l-1}{2^p}, \frac{l}{2^p} \}$. Then there exists $\xi_l$ between $y_i$ and $y_j$ so that $$ |x_j - x_i| = f'(\xi_l)|y_j - y_i| = \frac{f'(\xi_l)}{2^p} \in \left( \frac{1}{2^{p+1}}, \frac{1}{2^p}\right). $$ Since $f$ is concave, $f'$ is decreasing and hence the above quantity is minimized when $l = 2k$.

Combining altogether, we conclude:

• $ t_n = \left| f\left(\frac{2k}{2^p}\right) - f\left(\frac{2k-1}{2^p}\right) \right| $ for $p$ and $k$ as above,

• $(t_n)_{n=2}^{\infty}$ is strictly decreasing, and

• $\frac{1}{2^{p+1}} < t_n < \frac{1}{2^p}$.

Therefore

\begin{align*} \sum_{n=2}^{\infty} t_n &= t_2 + \sum_{p=1}^{\infty} \sum_{k=1}^{2^{p-1}} \left| f\left(\frac{2k}{2^p}\right) - f\left(\frac{2k-1}{2^p}\right) \right| \\ &\geq t_2 + \sum_{p=1}^{\infty} \sum_{k=1}^{2^{p-1}} \frac{1}{2^{p+1}} \\ &= t_2 + \sum_{p=1}^{\infty} \frac{2^{p-1}}{2^{p+1}} \\ &= \infty. \end{align*}