Mfrhtyj

Let $x_1, cdots, x_n$ be distinct points in the $d$ dimensional cube $[-1,1]^d$. What is a lower bound on the quantity:
$$ sum_{1 le j < k le n} frac{1}{||x_k-x_j||}$$
where $|| cdot ||$ is the Euclidean norm.

An asymptotic answer for large $n$ is also fine and bounds on any quantity that looks similar, such as replacing the norm with norm squared, is also welcomed.

My motivation is a problem that appeared in the book The Cauchy-Schwarz Master Class which proved the following:

If $-1 le x_1 < x_2 < cdots < x_n le 1$ then $$ sum_{1 le j < k le n} frac{1}{x_k-x_j} ge frac{n^2 log n}8.$$

This is an answer only up to $n = exp(ad)$ for some $a in theta(1)$, but may be enough to get started: There are as many as $n = exp(ad)$ points $y_1,ldots, y_n$ in ${-1,1}^d$ that satisfy the following:
$||y_i-y_j||_1 in theta(d)$ for each $i not = j$, where $|| cdot ||_1$ denotes the Manhattan metric.
[Google error-correcting codes]

Then for each $i not = j$, the following holds:

$$frac{1}{||y_i-y_j||_2} leq frac{1}{csqrt{d}}$$

for some $c in Omega(1)$, which implies the following:

Inequality 1: $$sum_{1 le i < j le n} frac{1}{||y_i-y_j||_2} leq frac{n^2}{2csqrt{d}}$$

However. not that for any distinct $x,y$, the following holds:

Inequality 2: $$frac{1}{||x-y||_2} ge frac{1}{sqrt{d}} $$

So Inequalities 1 and 2 together imply that for $y_1,ldots, y_n$ as above,

$sum_{1 le i < j le n} frac{1}{||y_i-y_j||_2}$ is no more than a constant multiple larger than $sum_{1 le i < j le n} frac{1}{||x_i-x_j||_2}$ for any other $x_1,ldots, x_n in [-1,1]^d$.

The situation seems to be less interesting asymptotically for fixed $d geq 2$. We have
$$frac{1}{||x-y||_2} geq frac{1}{2sqrt{d}}$$ for any $x, y in [-1, 1]^d$, so there's an easy lower bound of
$$sum_{1 leq j < k leq n} frac{1}{||x_k - x_j||} geq frac{1}{2sqrt{d}} binom{n}{2} = Omega(n^2).$$ This lower bound is actually achieved (up to a constant) by letting the $x_j$ lie on a grid, say $Lambda^+ = {n^{-1/d}, 2n^{-1/d}, dots, 1}^d$.

First note that if we set
$$Lambda = {-1, dots, -2n^{-1/d}, -n^{-1/d}, 0, n^{-1/d}, 2n^{-1/d}, dots, 1}^d$$
we have
$$sum_{j neq k} frac{1}{||x_k - x_j||} < sum_{v in Lambda, v neq 0} frac{1}{||v||}$$
for each $k$.

Also, since $d geq 2$, the integral
$$int_{[-1, 1]^d} frac{dx}{||x||}$$
actually converges, say to some $I_d < infty$, meaning in particular that
$$frac{1}{n} sum_{v in Lambda, v neq 0} frac{1}{||v||} to I_d$$
(this is just a standard grid approximation).

Putting these together, we get
$$sum_{1 leq j < k leq n} frac{1}{||x_k - x_j||} = frac{1}{2} sum_k sum_{j neq k} frac{1}{||x_k - x_j||} < frac{n}{2} sum_{v in Lambda, v neq 0} frac{1}{||v||} sim frac{n^2}{2} I_d$$
so our sum is $O(n^2)$, matching the lower bound.