9
$\begingroup$

Given an n-dimensional electrically neutral, solid metal ball (a point for n=0; a rod, n=1; a disc, n=2; a solid ball, n=3; ...), place N=(n+1)! identical ions on the ball. As one of my favorite physics professors used to say, forget the mathematics, intuitively I expect the ions to equilibrate to the vertices of an n-D permutohedron inscribed in the n-ball (e.g., a hexagon inscribed in the circumference of a disc with 6 ions and a truncated octahedron for n=3 ). Similarly with N= [2(n+1)]! /[(n+1)! (n+2)!] (the Catalan numbers), I expect to see an associahedron (a Stasheff polytope, e.g., a pentagon for the disc with 5 ions).

Is my intuition correct? Has anyone seen this worked out mathematically, as an extremum problem? An electrostatics simulation for n=3 would be interesting also. (See OEIS A019538 for refined f-vectors of permutohedra / permutahedra and A133437 for associahedra.)

After reviewing the very interesting, proposed answers, I think I need to clarify and qualify my question: I initially was thinking of a real physical situation, a conductive metal ball in 3 dimensions or disc in 2 with Coulomb's inverse-square law applying. Then, if I remember my physics correctly, free charges must always reside on the suface with the potential vanishing in the interior of the ball and with the gradient of the potential at the surface being normal to the surface in the equilibrium state. The number of ions for the 3-D ball is constrained as stated above to either 4!=24 for the 3-D permutahedron or 8!/(4! 5!) = 14 for the 3-D associahedron. Given either number, how will the ions distribute themselves on the surface? Whether one should or can sensibly modify the repulsion for higher dimensions n and whether analogous surface (n-1) physics and equilibrium topology would occur are the next logical considerations; however, the number of "ions" would still be restricted to the number of vertices of either the n-D permutohedron or associahedron.

Improve this question
$\endgroup$
9
  • $\begingroup$ The potential to minimize is $\sum_{i < j } | x_i - x_j |^{2-n}$ in dimension $n$, right? $\endgroup$
    – Pietro Majer
    Commented Oct 23, 2011 at 10:18
  • $\begingroup$ That's part of the problem to be fleshed out from the math. Obviously, for n=0 it's inconsequential what the potential is. For n=1 and 2, the genuine 3-D electrostatic potential is sufficient, but even for n=3 I don't know if this is true, so the generalization to higher dimensions is certainly an open question to me. $\endgroup$
    – Tom Copeland
    Commented Oct 23, 2011 at 10:30
  • $\begingroup$ algebraic geometry? $\endgroup$
    – Mattia Talpo
    Commented Oct 23, 2011 at 11:53
  • $\begingroup$ Sorry, I was thinking of analytic geometry and geometric algebra. ag tag has been deleted. $\endgroup$
    – Tom Copeland
    Commented Oct 23, 2011 at 17:00
  • 1
    $\begingroup$ Actually, that calculation is a little unfair, since I used the standard embedding of the permutohedron (permutations of $(1,2,\dots,n)$). It's not surprising that that's not in equilibrium, but it will evolve to an equilibrium invariant under the same group. However, I am confident that this does not lead to a stable equilibrium that's a polytope combinatorially equivalent to the permutohedron. $\endgroup$
    – Henry Cohn
    Commented Oct 23, 2011 at 18:18

3 Answers 3

Reset to default
10
$\begingroup$

It turns out to pretty hard to guess the answers to these kinds of extremal problems. The permutohedron is almost certainly not the answer in $\mathbb{R}^n$ for $n \ge 3$, for any reasonable potential function (for example, an inverse power law). Specifically, the truncated octahedron is not good at minimizing things, because of the square and hexagonal facets, and it seems that you can always do better with the same number of particles, although I haven't carefully proved this for all potential functions. In $\mathbb{R}^4$ the situation is even worse, since the 120 vertices of a regular 600-cell always lead to lower energy than those of a permutohedron. I'm confident that the permutohedron will be suboptimal also for $n \ge 5$, and that the associahedron behaves similarly.

More generally, it's far from clear when one should expect symmetry in ground states of physical systems like this (see Link for an expository article on this issue). For small systems you often get symmetry, but in large systems defects can actually lower energy in surprising ways.

It's natural to guess that regular polytopes should lead to energy minima, and the ones with simplicial facets actually do. (By contrast, the cube does not, because one can lower energy by rotating one facet relative to the opposite one, to get a square antiprism.) These polytopes actually minimize a very wide class of energies, including all inverse power laws; specifically, they are optimal whenever the potential function is a completely monotonic function of squared Euclidean distance. (Recall that a completely monotonic function is a nonnegative $C^\infty$ function whose derivatives alternate in sign.) Abhinav Kumar and I called this phenomenon universal optimality.

In three dimensions there is no universal optimum larger than an icosahedron, but in higher dimensions there are more examples, such as the $E_8$ root system or the minimal vectors in the Leech lattice. Another interesting example is the Schläfli configuration of 27 points on a sphere in six dimensions, which correspond to the 27 lines on a cubic surface. See Link for details and proofs.

Universal optimality seems to be quite rare, and in most cases the optimal configuration will depend on the potential function being used. See Link for some large-scale numerical experiments, as well as references to many other papers in the literature.

Improve this answer
$\endgroup$
5
  • $\begingroup$ P.S. My answer deals with particles on a sphere, but the original question may allow them to be inside the ball as well. For an inverse power law potential $r \mapsto 1/r^s$ with $s \le n-2$, the maximum principle implies that these two variants of the question have the same answer. When $s > n-2$, the questions often have different answers, but it is easier to rule out permutohedra: when $s$ is large enough, one can lower energy by moving one particle to the center of the ball. $\endgroup$
    – Henry Cohn
    Commented Oct 23, 2011 at 15:16
  • $\begingroup$ I tried to clarify my question after reading your response. For n=4 the problem is restricted to two separate cases with either 5!=120 identical "ions" or 10!/(5!6!) = 42, i.e., I've constrained the problem to match the number of vertices of either of the two polytopes to be considered separately. Your approach seems to be a more general optimization problem. $\endgroup$
    – Tom Copeland
    Commented Oct 23, 2011 at 17:15
  • $\begingroup$ For $n=4$ and 120 particles the optimal configuration is a regular 600-cell, so you definitely do not get a permutahedron. For $n=4$ and 42 particles, you can find simulation results at aimath.org/data/paper/BBCGKS2006/4-42.txt. I haven't checked whether it is an associahedron, but I am pretty confident it won't be. You can also get the 3d data from aimath.org/data/paper/BBCGKS2006. $\endgroup$
    – Henry Cohn
    Commented Oct 23, 2011 at 17:42
  • $\begingroup$ I just realized my first paragraph was a little unclear on whether I was comparing cases with the same number of particles, so I've edited it to try to clarify. $\endgroup$
    – Henry Cohn
    Commented Oct 23, 2011 at 17:46
  • $\begingroup$ Of course the vertices of the permutohedron $P_n$ makes a minimum configuration for some (unreasonable) potential function of the form $V(x_1,\dots,x_{n!}):=\sum_{i<j}\phi(\|x_i-x_j\|)$ : we may choose a function $\phi\ge0$ vanishing exactly on the finite set of distances between all pairs of veritices of $P_n$. But this hasn't much to do with $P_n$, since it can be done as well for any set of points. $\endgroup$
    – Pietro Majer
    Commented Oct 23, 2011 at 21:09
2
$\begingroup$

I know two papers in the mathematical physics literature which might be relevant:

One paper on the two-dimensional Coulomb problem (i.e., with logarithmic potential and a charge at infinity) is by Kogan, Perelomov and Semenoff, titled Charge distribution in 2-D electrostatics: A Shell model, about which I first heard in a seminar in Bonn in 1992 if memory serves me. I thought the result quite striking and was left with the impression that the resulting configurations ought to be explained by representation theory of some algebraic structure.

There is a also a paper on three-dimensional central potentials by Battye, Gibbons and Sutcliffe Central configurations in three dimensions.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Very interesting, but from the abstract of the second paper, it seems to address a more general problem than I've presented. $\endgroup$
    – Tom Copeland
    Commented Oct 23, 2011 at 17:20
  • $\begingroup$ See also on arxiv "Polyhedra in physics, chemistry and geometry" by M. Atiyah and P. Sutcliffe. $\endgroup$
    – Tom Copeland
    Commented Mar 13, 2012 at 21:48
1
$\begingroup$

I am sure our own J. O'Rourke has a lot more to say about this, but see:

http://www.cgafaq.info/wiki/Evenly_distributed_points_on_sphere

Also google for Hardin + Sloane + Smith

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice introduction. $\endgroup$
    – Tom Copeland
    Commented Oct 23, 2011 at 19:03

You must log in to answer this question.

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