Maze Proof Establishes a ‘Backbone’ for Statistical Mechanics
Introduction
Imagine that a grid of hexagons, honeycomb-like, stretches before you. Some hexagons are empty; others are filled by a 6-foot tall column of solid concrete. The result is a maze of sorts. For over half a century, mathematicians have posed questions about such randomly generated mazes. How big is the largest web of cleared paths? What are the chances that there is a path from one edge to the center of the grid and back out again? How do those chances change as the grid swells in size, adding more and more hexagons to its edges?
These questions are easy to answer if there is either a lot of empty space or a lot of concrete. Say every hexagon is assigned its state at random, independent of all the other hexagons, with a probability that is constant across the entire grid. There could be, say, a 1% chance that each hexagon is empty. Concrete crowds the grid, leaving only small pockets of air in between, making the chance of finding a path to the edge effectively zero. On the other hand, if there is a 99% chance that each hexagon is empty, there is just a thin sprinkling of concrete walls, punctuating swaths of open space — not much of a maze. Finding a path from the center to the edge in this case is a near-certainty.
For large grids, there is a remarkably sudden change when the probability hits 1/2. Just as ice melts into liquid water at exactly zero degrees Celsius, the character of the maze changes drastically at this transition point, called the critical probability. Below the critical probability, most of the grid will lie underneath concrete, while empty paths invariably come to dead ends. Above the critical probability, massive tracts are left empty, and it’s the concrete walls that are sure to peter out. If you stop exactly at the critical probability, concrete and emptiness will balance one another, with neither able to dominate the maze.
“At the critical point, what emerges is a higher degree of symmetry,” said Michael Aizenman, a mathematical physicist at Princeton University. “That opens the door to a huge body of mathematics.” It also has practical applications to everything from the design of gas masks to analyses of how infectious diseases spread or how oil seeps through rocks.
In a paper posted last fall, four researchers have finally calculated the chance of finding a path for mazes at the critical probability of 1/2.
An Arms Race
As a doctoral student in France in the mid-2000s, Pierre Nolin studied the critical probability scenario in great detail. The random maze, he thinks, is “a really beautiful model, maybe one of the simplest models you can invent.” Near the end of his doctoral studies, which he finished in 2008, Nolin became captivated by a particularly challenging question about how a hexagonal grid at the critical probability behaves. Say you build a grid around a central point, so that it approximates a circle, and you randomly build your maze from there. Nolin wanted to explore the chance that you’ll be able to find an open path that reaches from the edge to the center and back out, without retracing itself. Mathematicians calls this a monochromatic two-armed path, because both the inward and outward “arms” are on open paths. (Sometimes such grids are equivalently thought of as made of two different colors, say light blue and dark blue, rather than of open and closed cells.) If you increase the size of the maze, the length of the needed path will grow as well, and the chance of finding such a path will get smaller and smaller. But how quickly do the odds diminish, as the maze grows arbitrarily large?
Simpler related questions were answered decades ago. Calculations from 1979 by Marcel den Nijs estimated the chance that you can find one path, or arm, from the edge to the center. (Contrast this with Nolin’s requirement that there be one arm in and a separate one out.) Den Nijs’ work predicted that the chance of finding one arm in a hexagonal grid is proportional to $latex 1/n^{5/48}$, where n is the number of tiles from the center to the edge, or the radius of the grid. In 2002, Gregory Lawler, Oded Schramm and Wendelin Werner finally proved that the one-arm prediction was correct. To succinctly quantify the diminishing probability as the size of the grid grows, researchers use the exponent from the denominator, 5/48, which is known as the one-arm exponent.
Merrill Sherman/Quanta Magazine
Nolin wanted to compute the more elusive monochromatic two-arm exponent. Numerical simulations in 1999 showed that it was very close to 0.3568, but mathematicians failed to pin down its exact value.
It was much easier to compute what’s known as the polychromatic two-arm exponent, which characterizes the chance that, starting in the center, you can find not only an “open” path to the perimeter, but also a separate “closed” path. (Think of the closed path as one that traverses the tops of the concrete walls of the maze.) In 2001, Stanislav Smirnov and Werner proved that this exponent was 1/4. (Because 1/4 is substantially larger than 5/48, $latex 1/n^{1/4}$ shrinks more quickly than $latex 1/n^{5/48}$ as n grows. The chance, then, of a polychromatic two-arm structure is a lot lower than the chance of one arm, as one might expect.)
That computation had leaned heavily on knowledge about the shape of clusters in the graph. Imagine that a maze at the critical probability is extremely large — made up of millions and millions of hexagons. Now find a cluster of empty hexagons and trace the edge of the cluster with a thick black Sharpie. This probably won’t result in a simple, round blob. From miles in the air, you’d see a wriggling curve that constantly doubles back, often seeming as if it’s about to cross itself but never quite committing.
This is a type of curve called an SLE curve, introduced by Schramm in a 2000 paper that redefined the field. A mathematician studying the chances of finding one open path and one closed path knows that those paths must sit inside larger clusters of open and closed sites, which eventually meet along an SLE curve. The mathematical properties of SLE curves then translate to invaluable information about paths within the maze. But if mathematicians are searching for multiple paths of the same type, SLE curves lose much of their effectiveness.
By 2007, Nolin and his collaborator Vincent Beffara had created numerical simulations showing that the monochromatic two-arm exponent was about 0.35. This was suspiciously close to 17/48 — the sum of the one-arm exponent, 5/48, and the polychromatic two-arm exponent, 1/4 (or 12/48). “17/48 is really striking,” Nolin said. He began to suspect that 17/48 was the true answer — meaning there was a simple link between the different kinds of exponents. You could just add them together. “We said, OK, it’s too good to be false; it has to be true.”
Wei Qian studies continuous random structures, while Pierre Nolin studies discrete ones. The married couple worked together to ascertain the backbone exponent.
Courtesy of Pierre Nolin and Wei Qian
For a while, nothing came of Nolin and Beffara’s conjecture, though Nolin posted it on his website for others to work from. He moved to Hong Kong in 2017 to take up a professorship at the City University of Hong Kong, and kept working on the problem. In 2018, he brought up the exponent in conversation with Wei Qian, who was then a postdoc at the University of Cambridge in England. Qian was studying random geometry in the continuous rather than discrete context, with a special focus on SLE curves. She was in the midst of a project that used SLE to calculate exponents in a different type of random model, and Nolin began to suspect that her expertise was relevant to the monochromatic two-arm exponent as well. The pair soon found a simple-seeming equation whose solution would give the exponent, but that equation relied on an intermediate quantity having to do with the space enclosed by an SLE curve at the edge of the grid. Nolin and Qian couldn’t pin that number down.
“I did a lot of computations, but I was still not able to compute this property,” Qian said. “I didn’t succeed, so I just stopped for some time.”
“We never mentioned it to anyone because we were not sure whether it would be useful or not,” Nolin added.
The Backbone Exponent
The monochromatic two-arm exponent is particularly interesting because it also describes the “backbone” of a grid: the collection of hexagons that are connected to two distinct arms extending to two non-overlapping arms: one to the edge of the maze and one to its center. When these sites are colored in, they form a web that reaches across the entire grid and is called the backbone. When researchers model the spread of disease or porous rock formations, the backbone is a highway along which microbes or oil can flow. The exponent Nolin and Qian sought reveals the size of the backbone and is referred to as the backbone exponent.
Merrill Sherman/Quanta Magazine
Nolin and Qian were not the only ones after the backbone. Xin Sun, then at the University of Pennsylvania, had also been trying to calculate the backbone exponent. Over the preceding years, Sun and collaborators, including Nina Holden of New York University, had figured out a way to study SLE curves using random fractal surfaces. These sprawling, curved surfaces have scalloped edges that extend into long tendrils. Some points are a short hop from their neighbors, while others are a months-long journey. In certain places, these effects are too extreme to be visualized. “It’s not actually possible to draw it” completely accurately, Holden said. “You’d have to sort of stretch the surface a lot.”
In the summer of 2022, Sun enlisted Zijie Zhuang, a second-year graduate student, to join the study of the random maze at the critical probability. They considered random mazes where the hexagons lay on a random fractal surface, instead of on a flat plane. Because chance determines where and by how much the surface is stretched and compressed, the surface has unique properties. (These properties also make such surfaces useful to physicists who study models of quantum gravity in a two-dimensional universe, giving them their name: Liouville quantum gravity surfaces.) For instance, if you take scissors to such a surface, the shapes of the two halves don’t depend on one another. “That kind of independence really simplifies things tremendously,” said Scott Sheffield of the Massachusetts Institute of Technology. When things are random, you know less about them, but that might mean less information to tediously account for.
Sun and Zhuang first tried to determine the probability that there was an open path connecting a small circle around the grid’s center to a larger, surrounding circle. After they answered that question, Sun suggested a step up in ambition: calculating the chance that there were two paths connecting the nested circles, which would have given them a way to compute the backbone exponent. Soon, however, they ran into difficulties. “We tried this approach for several months, but the calculation seems not to be very tractable,” Zhuang wrote in an email.
Zijie Zhuang, a graduate student at the University of Pennsylvania, worked with Xin Sun, at the time a professor there, to study the backbone exponent using random fractal surfaces.
Shengjing Xu
Meanwhile, though Nolin and Qian hadn’t succeeded in finding the value of the exponent, they made progress in other ways. Qian took a leave of absence from her position at the French National Center for Scientific Research and joined Nolin as a professor at City University of Hong Kong. (They also got married.) In the summer of 2021, she came across a few papers by Sun and his collaborators that intrigued her, so as pandemic travel restrictions lifted, she planned a visit in December 2022 to the Institute for Advanced Study in Princeton, New Jersey, where Sun was spending the year.
It proved a profitable visit. As Qian described the equation she and Nolin had found, Sun began to think it might be amenable to his and Zhuang’s technique of overlaying the mazes on Liouville quantum gravity surfaces. “It’s kind of a coincidence,” Sun said. “One guy has a lock, one guy has a key.”
Zhuang was a bit skeptical. “We have no predictions, and we don’t even know if the formula will have a nice solution,” he said, describing the state of affairs at the time. Sun and Zhuang spent the next several months using their Liouville quantum gravity techniques — the key — to unlock the elusive quantity in Nolin and Qian’s equation from years earlier — the lock.
After four months of work, Sun and Zhuang had opened the metaphorical lock. Sun sent an email to Zhuang, Qian and Nolin, proclaiming: “Great News: Exact Formula for Backbone Exponent.” The answer, he found, was a moderately complicated expression of square roots and the trigonometric sine function. It was in accord with the earlier estimates, an endless stream of digits beginning with 0.3566668.
The four turned their work into a written paper, refining the argument until the ideas from Nolin and Qian on one side, and Sun and Zhuang on the other, combined to create a proof that Sheffield, who was Sun’s doctoral adviser, called “a beautiful gem.” “The proof strategy is definitely surprising and very original, but then when you see it, it’s also something that feels sort of natural,” Holden said.
Nolin laments his 2011 suspicion that the exponent was exactly 17/48. “We misled the field for quite some time. I’m not very proud of it.” The backbone exponent is strikingly different from its polychromatic cousins. Not only is it irrational, but it is also transcendental, meaning that like $latex \pi$ and e, it cannot be written as the solution to a simple polynomial equation.
“The proof doesn’t really explain where this formula is coming from,” he said. “We’ve been showing it to physicists, and we are really looking forward to their insight.”
The transcendental nature of the backbone exponent caught the attention of others in the field. Gregory Huber of the Chan Zuckerberg Biohub, who co-authored a follow-up article about the backbone exponent, said he thinks the result is the “first glimpse of a new continent” in statistical mechanics. Though combining SLE curves and Liouville quantum gravity is extremely technical, the clear and simple numerical answer that emerged, he wrote, is “amazingly simple and elegant.”
