# Generalization of the equilateral triangle?

I consider points in the two-dimensional plane.

An equilateral triangle is a set of three points in the plane which are equidistant.

Suppose now I have $n$ points $x_1,...,x_n$. What is the configuration which minimizes: $$H(x):=\sum_{i,j} (a-\|x_i-x_j\|^2)^2$$ where $a$ is positive real number.

Clearly, if $n=3$, one recovers the equilateral triangle. Could you draw the solution for larger $n$ ? What is the value of $H_{min}$ as a function of $n$?

Thanks!

• This is the problem of determing where to place the explosives around the core of an atom bomb, to most efficiently trigger the reaction. It's a classical problem with a substantial literature. Have you looked into it? Generally the minima is not known but in dimension three there's certainly a lot known. In higher dimensions there's quite a bit known for low numbers of points, but again it gets difficult to large numbers of points. – Ryan Budney Mar 5 '13 at 19:08
• @Ryan Budney : Thanks a lot for this idea. Could you give me a reference ? – user16215 Mar 6 '13 at 7:38

First, let's assume $a=1$; for other values we can scale a solution with $\sqrt{a}$.

So we want to minimize $H=\sum_{i,j} (1-\|x_i-x_j\|^2)^2$.

I globally optimized the problem numerically for $n=4$ and $n=5$ and obtained as solutions

for $n=4$, the square with side length $\sqrt{\frac{2}{3}}\approx0.8165$, giving $H_4=\frac{2}{3}$ for $n=5$, the regular pentagon with side length $\sqrt{\frac{5-\sqrt{5}}{6}}\approx0.6787$, giving $H_5=\frac{5}{3}$ So in these cases the "generalizations of the equilateral triangle" are the regular polygons. This might be an indication that the regular polygons could be solutions to the optimization problem for other $n$. In any case the regular polygon yields an upper bound. To find the value of $H$ for the regular polygon one just has to find the optimal side length and then plug in the values. Perhaps surprisingly, $H^{C_n}$ takes a particular simple form: $$H^{C_n}=\frac{n(n-3)}{6}.$$ So we know $H^n_{min}\leq H^{C_n}$ and this bound is sharp for $n\in \{3,4,5\}$.

For larger $n$, there are different solutions that obtain the same minimum as the regular polygon. For example distributing the points evenly on the vertices of the equilateral triangle gives $$H=\left\lfloor\frac{\binom{n-1}{2}}{3}\right\rfloor,$$ which is the same as $H^{C_n}$ above if $n$ is a multiple of $3$.

Let me give you two pictures of solutions that are not the regular $n$-gons, but obtain the same minimum:

for $n=6$: for $n=7$: I think minimizing this function is interesting also in dimensions other than $d=2$, even $d=1$, but mainly $d>2$. Maybe one can exploit the symmetry in the polynomial $H$ in some way. I don't know the references and the connection to explosives that Ryan Budney mentions in his comment.

• Great, thank you for this nice work. Any idea about a sharp solution? – user16215 Sep 25 '14 at 12:07
• @user16215 not at the moment.. – Moritz Firsching Sep 25 '14 at 20:03
{"ft_lang_label":"__label__en","ft_lang_prob":0.85345083,"math_prob":0.9997109,"size":1745,"snap":"2019-51-2020-05","text_gpt3_token_len":503,"char_repetition_ratio":0.12808731,"word_repetition_ratio":0.0,"special_character_ratio":0.2991404,"punctuation_ratio":0.09497207,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999621,"pos_list":[0,1,2,3,4,5,6,7,8],"im_url_duplicate_count":[null,3,null,3,null,3,null,3,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-01-18T03:48:09Z\",\"WARC-Record-ID\":\"<urn:uuid:012dad2e-2502-49fe-b02e-d93782e4c7d4>\",\"Content-Length\":\"120626\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:ca5f73d1-3db8-4d94-8f10-49950e8168e5>\",\"WARC-Concurrent-To\":\"<urn:uuid:58324274-4d4f-4107-961d-de2f53bc43ba>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://mathoverflow.net/questions/123640/generalization-of-the-equilateral-triangle\",\"WARC-Payload-Digest\":\"sha1:SMGTYZKC34LM6AXQHQ53SLD6NVVILX2X\",\"WARC-Block-Digest\":\"sha1:GEHHPDM7D4OVZOPPPEBEB5X6W45HVSFW\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-05/CC-MAIN-2020-05_segments_1579250591763.20_warc_CC-MAIN-20200118023429-20200118051429-00326.warc.gz\"}"}