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.

New contributor
Zuo Ye is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • 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$ – Matt F. Jul 12 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 Jul 12 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 Jul 12 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 Jul 12 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 at 1:25
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$

Your Answer

Zuo Ye is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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