6
$\begingroup$

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<j\le n}\frac{1}{dist(p_i,p_j)}$ 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.

$\endgroup$
6
  • 1
    $\begingroup$ 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$. $\endgroup$
    – user44143
    Jul 12, 2019 at 9:43
  • 1
    $\begingroup$ It seems strange: Deterministically, $\operatorname{dist}(p_i, p_j)\leq \sqrt{2}$ which implies roughly $D\geq n^2/3$. $\endgroup$ Jul 12, 2019 at 17:27
  • 2
    $\begingroup$ @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})$. $\endgroup$ Jul 12, 2019 at 17:30
  • $\begingroup$ 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. $\endgroup$ Jul 12, 2019 at 19:55
  • 1
    $\begingroup$ @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|}$. $\endgroup$
    – fedja
    Jul 13, 2019 at 1:25

1 Answer 1

4
$\begingroup$

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 <d_{H}(A),$ 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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.