July 15, 2016 feature
Researchers chip away at Smale's 7th unsolved problem in mathematics
(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.
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 mathematical problem. 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."
© 2016 Phys.org