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.

Improve this question
$\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
    Commented 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$
    – Dmitry Krachun
    Commented 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$
    – Dmitry Krachun
    Commented 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$
    – Sandeep Silwal
    Commented 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
    Commented Jul 13, 2019 at 1:25

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .