PhysicsPreprintTheory4 min read

TRUE, BUT IMPOSSIBLE TO PROVE

Picture a crowd of neighbours, each pair with its own demand. If every demand can be met at the same time, everyone is content. If two demands clash, someone must give way. Physicists studying magnets made of quantum spins face exactly this question. Each pair of neighbouring spins has an energy rule, and the system tries to reach its lowest energy. When a single state can satisfy every pair at once, the model is called frustration-free.

Such models are prized. Famous examples include the AKLT model and Kitaev’s toric code, reference points for exotic phases of matter. Being frustration-free also places strong limits on how a material can behave at low energy. So a natural question arises: given the rules for one pair, is the model frustration-free on lattices of every size?

Naoto Shiraishi, of the University of Tokyo, studied this question on a square grid of spins, with the same rules repeated everywhere: one for horizontal neighbours, one for vertical ones. Each spin can take d different states. The answer comes in two parts that seem to contradict each other.

One lattice is enough

For any single lattice size, the question is ordinary linear algebra. The trouble is the infinity of sizes. Checking bigger and bigger grids can reveal a failure, but never proves success for all of them.

The first theorem removes that infinity. For each value of d, there is a finite cutoff size, the same for every possible rule. If a model is frustration-free on a grid of that size, it is frustration-free on all of them. So the problem is decidable: an algorithm exists that always gives the right yes-or-no answer, in a finite time.

The key is a classic of algebra, Hilbert’s basis theorem. The condition at each size can be written as a set of polynomial equations, always in the same 2d⁴ unknowns — the numbers that define the two rules, each written as a table (a matrix) of d² × d² entries. The theorem guarantees that an infinite list of such equations has the same solutions as some finite part of it. Since a frustration-free grid also stays frustration-free on any smaller grid cut out of it, a single size then suffices.

This is not a trivial result. On exactly the same kind of models, a related question — whether there is an energy gap above the lowest state — was shown to be undecidable, even for a fixed d.

A tile set that hunts for contradictions

The second theorem goes the other way. Assuming that the standard axioms of mathematics, known as ZFC, contain no contradiction, there is a frustration-free model whose frustration-freeness cannot be proved from those axioms.

The construction uses Wang tiles: squares with coloured edges, laid without rotation, where neighbours must match. For any computer program, one can design a finite set of tiles that can cover the entire infinite plane if and only if the program runs forever. Each tile becomes a state of a spin. Each forbidden pair of neighbouring tiles costs one unit of energy. The model is frustration-free exactly when the tiles can cover the plane.

Now choose the program that searches through all possible proofs for a contradiction in ZFC, and stops if it finds one. If ZFC is consistent, the program never stops, and the model is frustration-free. But if ZFC could prove that, it would prove its own consistency — which Gödel’s second incompleteness theorem forbids.

The model is explicit, though far too complicated to write out. Its rules are not even truly quantum: the energy terms all commute, like simple classical constraints.

A cutoff that exists but cannot be named

How can a problem be decidable and still contain a statement that cannot be proved? The answer lies in the cutoff. It is finite for every d, but no algorithm can compute it from d. For the value of d used by the unprovable model, the axioms prove that a finite cutoff exists — yet they cannot prove that any particular number is one.

The cutoff also grows absurdly fast: at least as fast as the busy beaver function — the largest number of marks that a very simple idealised computer, a Turing machine, can write on its memory tape before stopping, for a given number of internal states (unrelated to the d states of a spin) — which outgrows every function a computer can calculate. Its value for five-state machines was settled only in 2024, according to the paper; the six-state value is still unknown.

The gap between existing and knowing

Decidability only requires that a correct algorithm exists, not that anyone can build it. In most familiar cases the difference does not matter. Here, the author argues, it becomes the whole story — and it appears in an ordinary physics problem on a plain square grid. The author states that ChatGPT was used to establish the decidability result and to clarify how it fits with the unprovability result. Pinning down actual cutoffs, even for very small spins, is left as an open challenge.