6
$\begingroup$

Within the context of mathematical biology, a sphere packing problem occurred to me. I must note that unlike the typical sphere packing problems, the variant I consider involves minimising the average distance between spheres rather than maximising the density of spheres. Furthermore, the spheres I consider are compressible rather than hard.

I have attempted to solve this problem numerically for a finite number of spheres but I'd also like to learn more about exact solutions in the finite regime as well as the asymptotic regime. The mathematical problem is introduced in a self-contained manner but for those who are curious I decided to share some motivation below.

Motivation:

enter image description here

A number of excellent scientists including Alan Turing[2] and D'Arcy Wentworth Thompson[3] have turned to mathematical modelling in order to understand morphogenesis. Though I may be slightly biased due to my training in mathematics, it recently occurred to me that early organogenesis may be modelled as a sphere packing process. I think this might partially explain the highly symmetric forms of amphibian eggs.

Consider a mass of spherical cells contained in a small region of space undergoing processes of division and specialisation in order to develop a specific geometrical structure. Now, let's suppose that vascularisation hasn't started so inter-cellular signalling via chemical signals is diffusion-constrained.

Furthermore, let's make the reasonable assumption that the strength of a chemical signal diminishes as $\sim \frac{1}{r^2}$ where $r$ is the euclidean distance from the source cell. We may then conjecture that in order for growth to be coordinated the average pair-wise distance between cells must be minimised at this stage of development.

Allow me to clarify the details of this mathematical problem.

Finite sphere-packing with soft constraints:

Let us suppose that there are $N$ compressible balls whose centres,$\{r_i\}_{i=1}^N$, are initialised by sampling uniformly from $[-l,l]^3$. Our challenge is to find $\{r^*_i\}_{i=1}^N \in \mathbb{R}^3$ that minimises:

\begin{equation} U_{\text{net}} = \sum_{i=1}^N \sum_{j \neq i} U(r_i,r_j) \tag{1} \end{equation}

where

\begin{equation} U(r_i,r_j)=(\lVert r_i-r_j \rVert^2 - 2l^2)^2 \tag{2} \end{equation}

is the form of each local potential function. Furthermore, my intuition for introducing the constant $2l^2$ is that this would allow cells to synchronise their chemical signalling activity.

As pointed out below, I managed to solve this problem approximately but I am also interested in exact solutions that may be found analytically. Might the general solution for all $N \in \mathbb{N}^*$ be known to pure mathematicians?

I am particularly curious about the geometry and topology of the optimal shape as $N$ increases. Does this geometry become unique as $N\to \infty$?

Note: I must add that while the constants $l$ and $2l^2$ may be important in a numerical setting, I don't see how they affect the topology or the number of symmetries of the optimal shape in an analytical setting. To a pure mathematician these constants are probably irrelevant.

 Approximate solutions:

I managed to find approximate solutions in the case where $l=5$ and $4 \leq N \leq 20$ by solving this optimisation problem using gradient descent with the hyperopt library: https://github.com/hyperopt/hyperopt. For a sanity check I found that when $N=4$ I obtain a tetrahedron as expected.

The python code I used is also available on Github: https://gist.github.com/AidanRocke/f48cea76eeaae5c25e11e9e47c9315c7

References:

  1. Weisstein, Eric W. "Sphere Packing." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/SpherePacking.html
  2. Turing, A. M. (1952). "The Chemical Basis of Morphogenesis" (PDF). Philosophical Transactions of the Royal Society of London B.
  3. Thompson, D. W., 1992. On Growth and Form. Dover reprint of 1942 2nd ed. (1st ed., 1917)
  4. Bergstra, J., Yamins, D., Cox, D. D. (2013) Making a Science of Model Search: Hyperparameter Optimization in Hundreds of Dimensions for Vision Architectures. To appear in Proc. of the 30th International Conference on Machine Learning (ICML 2013).
$\endgroup$
  • 1
    $\begingroup$ I suppose that the link to hyperopt next to Alan Turing in your original post was a mistake, so I have edited the link away. (That version of the question said: "...including Alan Turing2...") I have also removed the (geometry) tag, since it is deprecated on this site. I tried to choose suitable tags, but please do edit them further if there is some better choice. $\endgroup$ – Martin Sleziak Nov 30 '19 at 16:20
  • $\begingroup$ @MartinSleziak Thank you very much for removing the link to hyperopt. :) I was trying to figure out how to do that myself. $\endgroup$ – Aidan Rocke Nov 30 '19 at 17:34
  • 1
    $\begingroup$ I left a short explanation in chat - I did not want to add here more comments that are related more to the formatting than to the actual content of the post. $\endgroup$ – Martin Sleziak Nov 30 '19 at 17:41
  • 2
    $\begingroup$ With a Lennard-Jones potential instead of your potential form, this problem is associated with the study of clusters of rare gas atoms. David Wales's group has a lot of data and references on these clusters and for other model potentials (see www-wales.ch.cam.ac.uk/CCD.html). Not sure if they have anything about your potential though. $\endgroup$ – Yoav Kallus Nov 30 '19 at 18:26
  • 1
    $\begingroup$ You may have more luck in 8 or 24 dimensions. Optimal sphere arrangements are more uniform there. $\endgroup$ – Geoffrey Irving Dec 2 '19 at 12:34
5
$\begingroup$

It is unlikely that the solution is known generally (for all $N$), but there are partial results known for similar kernels, or for these kernels with additional constraints.

At first approximation your kernels are known as power-law attractive-repulsive kernels, meaning that potential energy between two points is decreasing at first as a function of the distance but then increasing for large distances. A closer look shows that the potentials you are interested in fit in the framework of a number of recent papers.

When you take $l=1/\sqrt{2}$ for instance, the potential function $U(x)$ may be written as a function of distance $f(x)=f(|x|)$, with $f(x)=\frac{|x|^\alpha}{\alpha}-\frac{|x|^\beta}{\beta}$, and where $(\alpha,\beta)=(4,2)$ (the constant term does not play into the minimization problem, so it can be subtracted off from the potential function). These potentials are the main object of an increasing number of papers, and take the name of power-law mildly repulsive kernels, whenever $\alpha>\beta>2$ ([BCLR1, BCLR2, CFP]). In many of these papers the problem of minimizing over measures is considered instead of the discrete problem. Since the minimizing probability measures still are often supported on discrete sets, this still proves to be fruitful for understanding discrete energy minimizers.

With $\beta=2$, the kernel in question is outside the mildy repulsive case, and this case appears more subtle (since many results that apply for $\beta>2$ cannot generally apply to $\beta=2$). A quantitative version of Theorem 1.4 in [LM] might explain why the regular simplex (tetrahedron) shows up as a minimizer for $ N=4$, but the result which appears there does not establish this. It only establishes that there exists a value of $\beta\geq\alpha$ for which the (repeated) regular simplex minimizes the discrete energy for all power-law potentials of this form and all $N$ divisible by $4$.

Incidentally, if you add the constraint that all the minimizing configuration 'particles' lie on a sphere (as happens for the regular simplex) one can use a linear programming approach, as appears in our recent pre-print [BGMPV], to show optimality of the regular octahedron, regular simplex, and the icosahedron for similar potentials (those whose derivatives, as a function of the inner product $\langle x,y \rangle$, are positive up to some order) when $3,4,6$, or $12$ divides the number of particles $N$. The approach here is similar to that in [CK], relying on Hermite interpolation at certain nodes, but the continuous setting introduces an extra interpolation point (due to the probability measure constraint).

[BCLR1] D. Balague, J. Carrillo, T. Laurent, and G. Raoul. Nonlocal interactions by repulsive–attractive potentials: radial ins/stability. Phys. D 260 (2013), 5–25. arXiv:1109.5258 MR3143991

[BCLR2] D. Balague, J. A. Carrillo, T. Laurent, and G. Raoul. Dimensionality of local minimizers of the interaction energy. Arch. Ration. Mech. Anal., 209 (2013) 1055–1088.

[BGMPV] D. Bilyk, A. Glazyrin, R. Matzke, J. Park, and O. Vlasiuk. Optimal measures for p-frame energies on spheres. pre-print. arXiv:1908.00885

[CFP] J. Carrillo, A. Figalli, and F. S. Patacchini. Geometry of minimizers for the interaction energy with mildly repulsive potentials. Ann. Inst. H. Poincar´e Anal. Non Lin´eaire 34 (2017), 1299–1308. arXiv:1607.08660 MR3742525

[CK] H. Cohn and A. Kumar. Universally optimal distribution of points on spheres. J. Amer. Math. Soc. 20 (2007), 99–149. arXiv:math/0607446 MR2257398

[LM] T. Lim and R. J. McCann. Isodiametry, variance, and regular simplices from particle interactions. pre-print. arXiv:1907.13593

$\endgroup$

Your Answer

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.