Researchers chip away at Smale's 7th unsolved problem in mathematics

July 15, 2016 by Lisa Zyga feature
The disconnectivity graph for 147 charges on a sphere has a structure-seeking “palm tree” organization. The five lowest minimum energy configurations are shown. Credit: Mehta et al. ©2016 American Physical Society

(Phys.org)—How do you arrange a group of points on the surface of a sphere so that all the points are as far apart from each other as possible? With two points, the answer is easy: place them on opposite sides of the sphere, as if they are endpoints of the diameter. With three points, make them the vertices of an equilateral triangle, and so on. But as the number of points increases, so does the difficulty of the problem.

This puzzle is the essence of Thomson's problem, which asks how to arrange equal charges (such as electrons) on the surface of a sphere in a way that minimizes their electrostatic potential energy—the energy caused by all of the electrons repelling each other. According to Coulomb's law, the total energy is inversely related to the sum of the distances between all possible pairs of charges, so the goal is to spread the charges as far apart as possible.

This task is more difficult than it sounds—Thomson's problem has been rigorously solved only for numbers of 2, 3, 4, 6, and 12 charges. In 1998, mathematician Steven Smale identified the problem of how to choose starting points close to the lowest-energy state (which makes it easier to solve Thomson's problem) as the seventh problem on his list of 18 unsolved problems for the 21st century.

Part of the reason why Thomson's problem is so important is because its applications are so far-reaching. In 1904, J.J. Thomson originally proposed the model of charges on a sphere to describe the structure of an atom. Even though experiments disproved this "plum pudding model" long ago, the Thomson problem still has notable applications in chemistry (for understanding how electrons fill electron shells in atoms), biology (for determining the arrangements of proteins on the shells of spherical viruses), as well as in physics, computer science, and such practical applications as determining the optimal placement of communication satellites around the Earth.

Spheres on trees

Now in a new paper published in Physical Review Letters, a team of mathematicians, engineers, and scientists from the US, the UK, and Australia has taken a new approach to Thomson's problem that makes it much easier to determine the lowest-energy configuration. For seven numbers of charges (every third number from 132 to 150), they have constructed tree-shaped disconnectivity graphs, where the vertical axis or "trunk" corresponds to the energy of a particular charge arrangement. Each "branch" terminates at a local minimum, which are the states that have lower energies than all of their neighboring states, and so they are candidates for the ultimate lowest energy state, the global minimum.

By visualizing the problem in this way, the researchers noticed that these particular graphs don't have lots of branches extending from lots of other branches. Instead, every branch connects to only a few other branches and then to the trunk at regularly spaced energy thresholds, so that the graph resembles a palm tree or single funnel structure.

The researchers found that this "funneled potential energy landscape" is characteristic of a highly ordered structure and displays characteristics of a small-world network. As a result, it provides an important clue for finding the global minimum. It tells the researchers to start their optimization algorithms using the local minima because, in these networks, it turns out that every local minimum is always within 5-7 steps (branches) of the global minimum. This is true even for local minima that have much higher energies than the global minimum, and even when the total number of local minima is very large.

By visualizing the problem from a new perspective, the researchers found that lower-energy configurations have more connections than higher-energy configurations do. Credit: Mehta et al. ©2016 American Physical Society

The disconnectivity graph reveals other information, such as that lower-energy local minima have more connections to other states than do higher-energy local minima. The researchers also discovered that the global minimum is always the most highly connected node in the entire network, making it the network's central node.

Implications for Thomson's and Smale's problems

Using this insight from the network's single-funneled, small-world structure, finding the global minimum for Thomson's problem becomes much easier than before.

"Our work looks at Smale's seventh problem from a completely different perspective and sheds novel light on it," coauthor Dhagash Mehta, at the University of Notre Dame and the University of Adelaide, told Phys.org. "In this work, methods developed by the theoretical chemistry community have helped understand a deep . Often it is the other way around."

As the researchers explain, it's easier to solve Thomson's problem in these particular cases than it is to solve Smale's problem (of choosing good starting points). So although the results will likely be useful, they do not go very far toward solving Smale's seventh problem.

"I think 'chip away' is about right," said coauthor David Wales at University Chemical Laboratories in Cambridge, UK. "There is no rigorous mathematical progress on the problem from an analytic point of view."

In the future, the researchers plan to extend this approach to larger numbers of charges. From earlier work, they expect that landscapes with more than 400 charges will start to display multiple funnels, so the small-world structure may disappear.

"While we have only shown data for seven numbers, we have strong reasons to believe that the single funnel is a feature for numbers less than 150," said coauthor Halim Kusumaatmaja at Durham University in Durham, UK. "For larger numbers, there will likely be multiple funnels. Nonetheless, the network analysis could still be exploited to help us quickly identify candidates for the global minimum."

Other lines of work include exploiting the small-world properties discovered here to improve other optimization algorithms and develop novel algorithms, as well as to incorporate weight and direction into these networks, which may provide additional insight into the Thomson problem.

"The social network analogy for networks of minima of the Thomson problem will go further when we analyze other network properties of these networks of minima," Mehta said. "Our results will also help in constructing novel algorithms to find the global minimum more efficiently by exploiting these network properties."

Explore further: Spin glass physics with trapped ions

More information: Dhagash Mehta et al. "Kinetic Transition Networks for the Thomson Problem and Smale's Seventh Problem." Physical Review Letters. DOI: 10.1103/PhysRevLett.117.028301 , Also at arXiv:1605.08459 [cond-mat.soft]

Related Stories

Spin glass physics with trapped ions

May 27, 2016

One of the most striking discoveries of quantum information theory is the existence of problems that can be solved in a more efficient way with quantum resources than with any known classical algorithm.

Worldwide quantum web may be possible with help from graphs

June 8, 2016

(Phys.org)—One of the most ambitious endeavors in quantum physics right now is to build a large-scale quantum network that could one day span the entire globe. In a new study, physicists have shown that describing quantum ...

Physics Model Determines Dynamics of Friends and Enemies

December 2, 2009

(PhysOrg.com) -- Sometimes friends can become enemies and enemies become friends, and it’s difficult to understand exactly how or why the changes took place. A new study shows that when the shifting of alliances and rivalries ...

Recommended for you

Two teams independently test Tomonaga–Luttinger theory

October 20, 2017

(Phys.org)—Two teams of researchers working independently of one another have found ways to test aspects of the Tomonaga–Luttinger theory that describes interacting quantum particles in 1-D ensembles in a Tomonaga–Luttinger ...

Using optical chaos to control the momentum of light

October 19, 2017

Integrated photonic circuits, which rely on light rather than electrons to move information, promise to revolutionize communications, sensing and data processing. But controlling and moving light poses serious challenges. ...

Black butterfly wings offer a model for better solar cells

October 19, 2017

(Phys.org)—A team of researchers with California Institute of Technology and the Karlsruh Institute of Technology has improved the efficiency of thin film solar cells by mimicking the architecture of rose butterfly wings. ...

Terahertz spectroscopy goes nano

October 19, 2017

Brown University researchers have demonstrated a way to bring a powerful form of spectroscopy—a technique used to study a wide variety of materials—into the nano-world.

15 comments

Adjust slider to filter visible comments by rank

Display comments: newest first

ursiny33
1 / 5 (1) Jul 15, 2016
Its a problem that magnetics in electron orbits in nature solves by shell construction
ursiny33
1 / 5 (1) Jul 15, 2016
The sphere within sphere is how nature does it in construction in magnetics
artpletcher
3 / 5 (2) Jul 15, 2016
Why not consider a 3D polar coordinate system of (2π)^2 3D radians? You just need to divide by n points.
FainAvis
not rated yet Jul 16, 2016
May I suggest a way to construct all the periodic table, nucleus and electron shells. Oh yes I know you are going to laugh, nevertheless here are my pearls:
Every proton wants to connect to exactly one electron, via some sort of line, I will call it a charge line. The line can bend even within the confines of the nucleus. In neutrons the line is very short. Then, arrange the protons and neutron orbitals as toroids so that they rotate against each other like gears in mesh. A proton (generally) rotates in a particular direction, while neutrons rotate in the other. Protons (generally) send their line outward looking for an electron. Neutrons do not send out a charge line.
So for example a uranium nucleus may have roughly seven shells where some protons are at (positions on the sphere) corners of a cube, more are at the center of every face of the cube. The same in several shells.
Now use some neutrons as idlers to rotate between cube corner and cube face protons. (cont)
FainAvis
not rated yet Jul 16, 2016
(continuing)
Next, more neutrons as idlers centered on the diagonal between cube corners and cube centers. You may realize that if all the above nucleons are the same diameter they will not rotate, unless these on the diagonal are half the diameter of the others (in a shell).
Lets say, for the nucleus, starting with an outer filled shell and leaving a void at the nuclear center, you try to fill all the positions as I have described them. Actually, since we have far too many neutrons and not enough protons we need to make some adjustments.
With every shell taking the same positions from the atomic center outwards it is also convenient to say that at each corner position there is a proton axis carrying seven protons, at cube edges there are six or seven neutrons on an axis, and at cube face centers five or six protons. And between corner and face center several neutrons on each axis.
(cont)
FainAvis
not rated yet Jul 16, 2016
(continuing)
But we are still short of places for protons.
How do the innermost protons on an axis fine their paired electron? Simple, each proton orbital is like a torus, so a stack of protons will have a hole right through to find their electrons in the electron shells. Think of the proton and electron pair together with their shared charge line as taking the shape of a trumpet. The proton orbital is like the mouthpiece, the electron orbital is like the rime of the bell, and the charge line sweeps a trumpet tube between the electron and proton. Several trumpet shapes on an axis will be coaxial.
Now the inner end of some neutron axes can decay to a proton. The proton's charge line is pointing in toward the void. It will find a way out of the void via a cube face center axis. At the surface of the nucleus six trumpet tubes will emerge.
That may be quite stable for a long time, but sooner or later, a proton on the inner end of a cube face diagonal axis may be dislodged. (cont)
FainAvis
not rated yet Jul 16, 2016
(continuing)
That proton will cross the void, pulled by its charge line, toward the base of the cube face axis. That bump on the bottom of the axis will propagate up the axis and dislodge nucleons from the top of the cube face center axis and adjacent diagonal axes, to emit an alpha particle.
This scheme continues for nuclei of the entire periodic table, including all the isotopes of all elements.
Elements approx scandium to barium have corner and edge axes.
Elements approx beryllium to calcium have tetrahedral corner and edge axes.
Finally, sorting out the electron orbitals, lets consider neon. Ten protons. The trick is to realize that one nuclear axis is special and carries spare protons on the inner surface of the void, so that the outer shell is complete. The special axis starts a coaxis, four trumpet tubes emerge at the nuclear surface, the coaxis finds two electrons in the electron shells, turns more than 360 degrees to point inward at a tetrahedral edge
(cont)
FainAvis
not rated yet Jul 16, 2016
(continuing)
The tetrahedral edge is a neutron axis, exactly aligned with the incoming coaxis. The coaxis finds two electrons in the electron shells. And then the coaxis continues right into the nuclear void, crosses to a tetrahedral corner proton axis, picks up two electrons, turns back into the nucleus ... then finally, at the neutron axis where this coaxis started, pairs the last two protons and two neutrons. The coaxis has run out of protons and all possible electron orbitals are filled.

In organic chemistry one may find several coaxes traveling through many atoms to resolve at an atom a long distance away.
Protoplasmix
not rated yet Jul 16, 2016
Why not consider a 3D polar coordinate system of (2π)^2 3D radians? You just need to divide by n points
Good idea, but simply picking from a uniform distribution (dividing the domain by n or into n partitions) for θ ϵ [0,2π) and for φ ϵ [0,π] will cause a "bunching" of points near the poles. But there are some clever ways to remedy that, see Sphere Point Picking.
pixeldictator
5 / 5 (1) Jul 18, 2016
The article says we've rigorously solved this problem for 2, 3, 4, 6, and 12 points. I would imagine that the 4, 6, and 12 point solutions would have spacing corresponding to the faces of regular polyhedra, right? If that's the case, why aren't 8 and 20 included as well?
Protoplasmix
5 / 5 (1) Jul 18, 2016
I would imagine that the 4, 6, and 12 point solutions would have spacing corresponding to the faces of regular polyhedra, right?
Yes, they're Platonic solids (the tetrahedron, octahedron, and icosahedron, respectively) and they all have faces of congruent equilateral triangles.
If that's the case, why aren't 8 and 20 included as well?
There are numerical solutions for N=8 and 20 (see Wiki) but they're not the corresponding Platonic solids – I think the reason is because locating the points at their vertices (the faces are square for N=8 and pentagonal for N=20) is not the lowest possible energy configuration, e.g., for a square face the diagonal distances are greater than the edge distances, so the points on the same face aren't quite all equidistant from each other, meaning there must be another configuration that has less energy.
Protoplasmix
not rated yet Jul 18, 2016
Good questions.

It's easy enough to divide the domain by N. Placing the first point can be done blindfolded. After that it gets... difficult to be rigorous. Each number N is unique, which means each has a slightly different set of rules (different geometry) to follow to produce a correct solution.

For large N (>100) I was thinking of an algorithm that relies on ideal gas laws and the laws of thermodynamics – distribute the points (as gas molecules) randomly on the surface of the sphere, giving each the same speed but along a random geodesic. The collisions would be inelastic, and the radius of the molecules (with their centers on the sphere) would increase over time until their motions are sufficiently confined to calculate the exact solution. It shouldn't be too hard to render an animation of the solution's evolution using something like POV-Ray...
Protoplasmix
not rated yet Jul 18, 2016
late edit – maybe could've phrased that better: having the radius of the gas molecules increase isn't from the gas laws, it's done to confine (or freeze or crystallize or preserve) the equidistant distribution of the evolved thermodynamic equilibrium.
Protoplasmix
not rated yet Jul 20, 2016
oops, I meant elastic collisions, not inelastic.

Also looks like Blender might be better suited since it has features already built-in to handle the collisions and also some of the basic physics for the points (e.g., using particles having their own interacting force fields).

And after some more checking I found a very cool applet done in the java runtime environment that features a choice of random or spiral initial distribution and a dozen different algorithms to choose from. There are also quite a few ways to view the evolution including making changes as it progresses. Absolutely fascinating. See http://thomson.phy.syr.edu/ Way to go Orange!
Seeker2
not rated yet Aug 06, 2016
"Thomson's problem has been rigorously solved only for numbers of 2, 3, 4, 6, and 12 charges."

You might as well include 8 charges if we are looking for perfect symmetry to give us the lowest-energy state. For a unit sphere the coordinates are

azimuthal, polar angle =
45,45
45,135
45,225
45,315
225,45
225,135
225,215
225,315

or so it would appear.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.