# Point distributions in unit square which minimize E[1 / distance]

Choose $$n$$ points $$p_1,\ldots,p_n$$ in the unit square $$[0,1]^2\subset\mathbb{R}^2$$ such that $$D:=\mathop{\sum}\limits_{1\le i is minimized, where $$dist(p_i,p_j)$$ is the Euclidean distance between $$p_i$$ and $$p_j$$. What is the magnitude of $$D$$ in $$n$$?

I have worked out that $$D\le\Omega(n\log(n))$$ by construction.

• Will you share the construction? I would expect there to be some limiting continuous distribution where $E[1/dist]=c$, and then to have $D_n$ of order $cn^2$. Jul 12, 2019 at 9:43
• It seems strange: Deterministically, $\operatorname{dist}(p_i, p_j)\leq \sqrt{2}$ which implies roughly $D\geq n^2/3$. Jul 12, 2019 at 17:27
• @MattF. If, say, the limiting density $\mu$ is continuous with respect to the Lebesgue measure, then the integral of $1/|x-y|$ against $\mu\times \mu$ is infinite. Also, the divergence is logarithmic, so my guess is that the answer is $\Omega(n^2\log{n})$. Jul 12, 2019 at 17:30
• I asked a similar question here: math.stackexchange.com/questions/3050869/…. For the $1$ dimensional case, you indeed have a $n^2\log(n)$ lower bound and it can be found in the book 'The Cauchy-Schwarz master class', exercise 8.9. However, the technique there does not generalize to even two dimensions. Jul 12, 2019 at 19:55
• @DmitryKrachun Why? We are on the plane, not on the line, so the critical power is now $2$, not $1$. The question essentially is what is the capacity of the unit square and what is the equilibrium measure with respect to the kernel $\frac 1{|x-y|}$. Jul 13, 2019 at 1:25

This is very classical (also known as "Thomson problem" usually on the sphere but the same asymptotic results hold for other sets as well - Hausdorff dimension is important).

Whenever

$$\inf_{\mu}\int \int_{A\times A}\frac{1}{|x-y|^{s}} d\mu(x) d\mu(y)<\infty,$$

where infimum is taken with respect to all probability measures supported on, say a compact set $$A \subset \mathbb{R}^{k}$$, (this usually happens when $$0\leq s here $$d_{H}(A)$$ is the Hausdorff dimension of the set $$A$$) then one has $$\frac{1}{N^{2}} \inf_{x_{1}, \ldots, x_{N} \in A} \sum_{1\leq i \neq j \leq N}\frac{1}{|x_{i}-x_{j}|^{s}} \to \inf_{\mu}\int_{A\times A}\frac{1}{|x-y|^{s}} d\mu(x) d\mu(y)$$ as $$N$$ goes to infinity. In other words $$s$$-Riesz energy $$E_{s}(A):=\inf_{x_{1}, \ldots, x_{N} \in A} \sum_{1\leq i \neq j \leq N}\frac{1}{|x_{i}-x_{j}|^{s}} \sim C N^{2}.$$

The standard references is potential theory

Landkof, N. S., Foundations of modern potential theory. Translated from the Russian by A. P. Doohovskoy, Die Grundlehren der mathematischen Wissenschaften. Band 180. Berlin-Heidelberg-New York: Springer-Verlag. X, 424 p. Cloth DM 88.00; \$ 27.90 (1972). ZBL0253.31001., Springer-Verlag

Mattila, Pertti, Geometry of sets and measures in Euclidean spaces. Fractals and rectifiability, Cambridge Studies in Advanced Mathematics. 44. Cambridge: Univ. Press. xii, 343 p. (1995). ZBL0819.28004.

In your case $$s=1$$ and $$d_{H}([0,1]^{d})=d$$.

Another interesting scenario is when $$s=d$$ (in this case $$E_{s}(A)\sim C n^{2} \ln n$$); and when $$s>d$$ (in this case $$E_{s}(A) \sim C N^{1+\frac{s}{d}}$$). You may look at

Hardin, D. P.; Saff, E. B., Discretizing manifolds via minimum energy points, Notices Am. Math. Soc. 51, No. 10, 1186-1194 (2004). ZBL1095.49031.

and references therein.