2018 BSJ Blog Fall 2018

The Unsolvable Problem

by Meera Aravinth

Imagine working for years to prove that a problem can never be solved. A team of mathematicians did exactly that, proving the undecidability of the spectral gap. But what exactly does it mean for a problem to be unsolvable or undecidable?

Mathematician Gödel proved in the 20th century that certain mathematical claims cannot be decided with logic and can never be proven or disproven. An example might be a statement like “This sentence is a lie”– it is not possible to ascertain whether this is true or false. This idea was further expanded on by Alan Turing, who developed the concept of the Turing machine, which has a string of inputs on one side and outputs on the other. With this in mind, Turing asked a simple question: If the Turing machine is running on a string of inputs, will it ever stop running? This question is known as the halting problem, and was shown to be undecidable – there is no mathematical or rigorous process that can solve it.

The mathematicians Toby S. Cubitt, David Pérez-García, and Michael Wolf used the theory behind the halting problem and applied it to the question of the spectral gap in physics. The spectral gap is the difference in energy between the lowest or ground state and the first excited state in a material. In an atom, the spectral gap is described by electrons, which can jump from one energy level to another by absorbing or emitting energy. But in a material of infinitely large size, the spectral gap is sometimes non-existent- that is, any small amount of energy would move the material from its ground state to its first excited state. This phenomenon is observed in matter at absolute zero, which sometimes moves to higher energy states because of quantum effects despite there being no available energy in the environment. These types of materials are described as “gapless”, while those materials that do have a significant spectral gap are “gapped”.

The team of mathematicians considered whether there was a mathematical way to determine if a material is gapped or gapless. They theoretically constructed a material with certain properties which made it correlate with the halting problem and proved that there would be no way to determine whether this material was gapped or gapless. While this theoretical material is too complicated to construct in reality, the result can be applied to all materials to show that the question of the spectral gap is always unsolvable.

This discovery has important applications for physicists investigating the spectral gap. While one could always experimentally measure whether a material is gapped or gapless, there would be no way to mathematically predict the result. Also, the discovery shows that the addition of even one atom in a material of very large size could change it from gapped to gapless, making it very important that scientists are careful when projecting their results to very large or infinite sizes.

This significant mathematical proof shows us the importance of the questions we can’t answer. Recognizing the limits of our knowledge can help us guide our scientific questions and ideas towards a better understanding of our world.

References:

Cubitt, T. S., Pérez-García, D., & Wolf, M. (2018). The Un(solv)able Problem. Scientific American, 319(4), 28–37. Retrieved from http://search.ebscohost.com.libproxy.berkeley.edu/login.aspx?direct=true&db=a9h&AN=131738386&site=ehost-live

Cubitt, T., Perez-Garcia, D., & Wolf, M. (2018). The Undecidability of the Spectral Gap. Nature.