Latest news with #QuantaMagazine
WIRED
4 days ago
- Science
- WIRED
A ‘Grand Unified Theory' of Math Just Got a Little Bit Closer
Jul 27, 2025 7:00 AM By extending the scope of a key insight behind Fermat's Last Theorem, four mathematicians have made great strides toward building a unifying theory of mathematics. Illustration: Nash Weerasekera for Quanta Magazine The original version of this story appeared in Quanta Magazine. In 1994, an earthquake of a proof shook up the mathematical world. The mathematician Andrew Wiles had finally settled Fermat's Last Theorem, a central problem in number theory that had remained open for over three centuries. The proof didn't just enthral mathematicians—it made the front page of The New York Times. But to accomplish it, Wiles (with help from the mathematician Richard Taylor) first had to prove a more subtle intermediate statement—one with implications that extended beyond Fermat's puzzle. This intermediate proof involved showing that an important kind of equation called an elliptic curve can always be tied to a completely different mathematical object called a modular form. Wiles and Taylor had essentially unlocked a portal between disparate mathematical realms, revealing that each looks like a distorted mirror image of the other. If mathematicians want to understand something about an elliptic curve, Wiles and Taylor showed, they can move into the world of modular forms, find and study their object's mirror image, then carry their conclusions back with them. This connection between worlds, called 'modularity,' didn't just enable Wiles to prove Fermat's Last Theorem. Mathematicians soon used it to make progress on all sorts of previously intractable problems. Modularity also forms the foundation of the Langlands program, a sweeping set of conjectures aimed at developing a 'grand unified theory' of mathematics. If the conjectures are true, then all sorts of equations beyond elliptic curves will be similarly tethered to objects in their mirror realm. Mathematicians will be able to jump between the worlds as they please to answer even more questions. But proving the correspondence between elliptic curves and modular forms has been incredibly difficult. Many researchers thought that establishing some of these more complicated correspondences would be impossible. Now, a team of four mathematicians has proved them wrong. In February, the quartet finally succeeded in extending the modularity connection from elliptic curves to more complicated equations called abelian surfaces. The team—Frank Calegari of the University of Chicago, George Boxer and Toby Gee of Imperial College London, and Vincent Pilloni of the French National Center for Scientific Research—proved that every abelian surface belonging to a certain major class can always be associated to a modular form. Toby Gee, Frank Calegari, and Vincent Pilloni, along with George Boxer (not pictured), spent nearly a decade on the proof. Photographs: Courtesy of Toby Gee; Jayne Ion; MC 'We mostly believe that all the conjectures are true, but it's so exciting to see it actually realized,' said Ana Caraiani, a mathematician at Imperial College London. 'And in a case that you really thought was going to be out of reach.' It's just the beginning of a hunt that will take years—mathematicians ultimately want to show modularity for every abelian surface. But the result can already help answer many open questions, just as proving modularity for elliptic curves opened up all sorts of new research directions. Through the Looking Glass The elliptic curve is a particularly fundamental type of equation that uses just two variables— x and y . If you graph its solutions, you'll see what appear to be simple curves. But these solutions are interrelated in rich and complicated ways, and they show up in many of number theory's most important questions. The Birch and Swinnerton-Dyer conjecture, for instance—one of the toughest open problems in math, with a $1 million reward for whoever proves it first—is about the nature of solutions to elliptic curves. Elliptic curves can be hard to study directly. So sometimes mathematicians prefer to approach them from a different angle. That's where modular forms come in. A modular form is a highly symmetric function that appears in an ostensibly separate area of mathematical study called analysis. Because they exhibit so many nice symmetries, modular forms can be easier to work with. At first, these objects seem as though they shouldn't be related. But Taylor and Wiles' proof revealed that every elliptic curve corresponds to a specific modular form. They have certain properties in common—for instance, a set of numbers that describes the solutions to an elliptic curve will also crop up in its associated modular form. Mathematicians can therefore use modular forms to gain new insights into elliptic curves. But mathematicians think Taylor and Wiles' modularity theorem is just one instance of a universal fact. There's a much more general class of objects beyond elliptic curves. And all of these objects should also have a partner in the broader world of symmetric functions like modular forms. This, in essence, is what the Langlands program is all about. An elliptic curve has only two variables— x and y —so it can be graphed on a flat sheet of paper. But if you add another variable, z , you get a curvy surface that lives in three-dimensional space. This more complicated object is called an abelian surface, and as with elliptic curves, its solutions have an ornate structure that mathematicians want to understand. It seemed natural that abelian surfaces should correspond to more complicated types of modular forms. But the extra variable makes them much harder to construct and their solutions much harder to find. Proving that they, too, satisfy a modularity theorem seemed completely out of reach. 'It was a known problem not to think about, because people have thought about it and got stuck,' Gee said. But Boxer, Calegari, Gee, and Pilloni wanted to try. Finding a Bridge All four mathematicians were involved in research on the Langlands program, and they wanted to prove one of these conjectures for 'an object that actually turns up in real life, rather than some weird thing,' Calegari said. Not only do abelian surfaces show up in real life—the real life of a mathematician, that is—but proving a modularity theorem about them would open new mathematical doors. 'There are lots of things you can do if you have this statement that you have no chance of doing otherwise,' Calegari said. 'After a coffee, we would always joke that we had to go back to the mine.' The mathematicians started working together in 2016, hoping to follow the same steps that Taylor and Wiles had in their proof about elliptic curves. But every one of those steps was much more complicated for abelian surfaces. So they focused on a particular type of abelian surface, called an ordinary abelian surface, that was easier to work with. For any such surface, there's a set of numbers that describes the structure of its solutions. If they could show that the same set of numbers could also be derived from a modular form, they'd be done. The numbers would serve as a unique tag, allowing them to pair each of their abelian surfaces with a modular form. The problem was that while these numbers are straightforward to compute for a given abelian surface, mathematicians don't know how to construct a modular form with the exact same tag. Modular forms are simply too difficult to build when the requirements are so constrained. 'The objects you're looking for, you don't really know they exist,' Pilloni said. Instead, the mathematicians showed that it would be enough to construct a modular form whose numbers matched those of the abelian surface in a weaker sense. The modular form's numbers only had to be equivalent in the realm of what's known as clock arithmetic. Imagine a clock: If the hour hand starts at 10 and four hours pass, the clock will point to 2. But clock arithmetic can be done with any number, not just (as in the case of real-world clocks) the number 12. Boxer, Calegari, Gee, and Pilloni only needed to show that their two sets of numbers matched when they used a clock that goes up to 3. This meant that, for a given abelian surface, the mathematicians had more flexibility when it came to building the associated modular form. But even this proved too difficult. Then they stumbled on a trove of modular forms whose corresponding numbers were easy to calculate—so long as they defined their numbers according to a clock that goes up to 2. But the abelian surface needed one that goes up to 3. The mathematicians had an idea of how to roughly bridge these two different clocks. But they didn't know how to make the connection airtight so they could find a true match for the abelian surface in the world of modular forms. Then a new piece of mathematics appeared that turned out to be just what they needed. Lue Pan's work in a seemingly disparate area of number theory turned out to be essential. Photograph: Will Crow/ Princeton University Surprise Help In 2020, a number theorist named Lue Pan posted a proof about modular forms that didn't initially seem connected to the quartet's problem. But they soon recognized that the techniques he'd developed were surprisingly relevant. 'I didn't expect that,' Pan said. After years of regular meetings, mostly on Zoom, the mathematicians started to make progress adapting Pan's techniques, but major hurdles remained. Then, in the summer of 2023, Boxer, Gee, and Pilloni saw a conference in Bonn, Germany, as the perfect opportunity to come together. The only problem was that Calegari was supposed to travel to China at the same time to give a talk. But a difficult visit to the Chinese consulate in Chicago made him reconsider. 'Eight hours later, my visa was rejected and my car was towed,' he said. He decided to scrap the China talk and join his collaborators in Germany. Gee secured the team a room in the basement of the Hausdorff Research Institute, where they were unlikely to be disturbed by itinerant mathematicians. There, they spent an entire week working on Pan's theorem, one 12-hour day after the next, only coming up to ground level occasionally for caffeine. 'After a coffee, we would always joke that we had to go back to the mine,' Pilloni said. The grind paid off. 'There were many twists to come later,' Calegari said, 'but at the end of that week I thought we more or less had it.' It took another year and a half to turn Calegari's conviction into a 230-page proof, which they posted online in February. Putting all the pieces together, they'd proved that any ordinary abelian surface has an associated modular form. Their new portal could one day be as powerful as Taylor and Wiles' result, revealing more about abelian surfaces than anyone thought possible. But first, the team will have to extend their result to non-ordinary abelian surfaces. They've teamed up with Pan to continue the hunt. 'Ten years from now, I'd be surprised if we haven't found almost all of them,' Gee said. The work has also allowed mathematicians to formulate new conjectures—such as an analogue of the Birch and Swinnerton-Dyer conjecture that involves abelian surfaces instead of elliptic curves. 'Now we at least know that the analogue makes sense' for these ordinary surfaces, said Andrew Sutherland, a mathematician at the Massachusetts Institute of Technology. 'Previously we did not know that.' 'Lots of things that I had dreamed we would be able to one day prove are now within reach because of this theorem,' he added. 'It changes things.' Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.
WIRED
20-07-2025
- Science
- WIRED
The Hunt for a Fundamental Theory of Quantum Gravity
Jul 20, 2025 7:00 AM Black hole and Big Bang singularities break our best theory of gravity. A trilogy of theorems hints that physicists must go to the ends of space and time to find a fix. ILLUSTRATION: MARK BELAN FOR QUANTA MAGAZINE The original version of this story appeared in Quanta Magazine . Two blind spots torture physicists: the birth of the universe and the center of a black hole. The former may feel like a moment in time and the latter a point in space, but in both cases the normally interwoven threads of space and time seem to stop short. These mysterious points are known as singularities. Singularities are predictions of Albert Einstein's general theory of relativity. According to this theory, clumps of matter or energy curve the space-time fabric toward themselves, and this curvature induces the force of gravity. Pack enough stuff into a small enough spot, and Einstein's equations seem to predict that space-time will curve infinitely steeply there, such that gravity grows infinitely strong. Most physicists don't believe, however, that Einstein's theory says much about what really happens at these points. Rather, singularities are widely seen as 'mathematical artifacts,' as Hong Liu, a physicist at the Massachusetts Institute of Technology, put it, not objects that 'occur in any physical universe.' They are where general relativity malfunctions. The singularities are expected to vanish in a more fundamental theory of gravity that Einstein's space-time picture merely approximates—a theory of quantum gravity. But as physicists take steps toward that truer and more complete theory by merging general relativity and quantum physics, singularities are proving hard to erase. The British mathematical physicist Roger Penrose won the Nobel Prize in Physics for proving in the 1960s that singularities would inevitably occur in an empty universe made up entirely of space-time. More recent research has extended this insight into more realistic circumstances. One paper established that a universe with quantum particles would also feature singularities, although it only considered the case where the particles don't bend the space-time fabric at all. Then, earlier this year, a physicist proved that these blemishes exist even in theoretical universes where quantum particles do slightly nudge space-time itself—that is, universes quite a bit like our own. This trilogy of proofs challenges physicists to confront the possibility that singularities may be more than mere mathematical mirages. They hint that our universe may in fact contain points where space-time frays so much that it becomes unrecognizable. No object can pass, and clocks tick to a halt. The singularity theorems invite researchers to grapple with the nature of these points and pursue a more fundamental theory that can clarify what might continue if time truly stops. Space-Time's Fatal Flaws Karl Schwarzschild first discovered an arrangement of space-time with a singularity in 1916, just months after Einstein published general relativity. The bizarre features of the 'Schwarzschild solution' took years for physicists to understand. Space-time assumes a shape analogous to a whirlpool with walls that swirl more and more steeply as you go farther in; at the bottom, the curvature of space-time is infinite. The vortex is inescapable; it has a spherical boundary that traps anything falling inside, even light rays. It took decades for physicists to accept that these inconceivable objects, eventually dubbed black holes, might actually exist. The British mathematical physicist Roger Penrose proved that given two simple assumptions, space-time must end at points called singularities. COURTESY OF PUBLIC DOMAIN J. Robert Oppenheimer and Hartland Snyder calculated in 1939 that if a perfectly spherical star gravitationally collapses to a point, its matter will become so dense that it will stretch space-time into a singularity. But real stars bubble and churn, especially while imploding, so physicists wondered whether their nonspherical shapes would stop them from forming singularities. Penrose eliminated the need for geometric perfection in 1965. His landmark proof relied on two assumptions. First, you need a 'trapped surface' inside of which light can never escape. If you cover this surface in light bulbs and switch them on, their light rays will fall inward faster than they can travel outward. Crucially, this shell of light will shrink regardless of whether it started out as a perfect sphere, a dimpled golf ball, or something more misshapen. Second, space-time should always curve in such a way that light rays bend toward each other but never diverge. In short, gravity should be attractive, which is the case so long as energy is never negative. With these two stipulations, Penrose proved the mortality of at least one of the trapped light rays. Its otherwise eternal journey through space and time must terminate in a singularity, a point where the space-time fabric ceases to exist, where there is no future for the light ray to travel into. This was a new definition of a singularity, distinct from the infinite curvature of the Schwarzschild solution. Its generality enabled Penrose to prove in three scant pages of math that, under his two assumptions, singularities will inevitably form. Caption: A hand-drawn figure in Penrose's 1965 paper proving the singularity theorem shows the collapse of space-time to form a singularity. The paper has been called 'the most important paper in general relativity' since Einstein's. ILLUSTRATION: Roger Penrose, Physical Review Letters, American Physical Society 'Penrose's paper was probably the most important paper in general relativity ever written, other than Einstein's original paper,' said Geoff Penington, a physicist at the University of California, Berkeley. Stephen Hawking soon extended Penrose's argument to the early universe, proving that a cosmos described by general relativity must have sprung from a singular point during the Big Bang. This cosmological singularity resembles a black hole in that, if you imagine rewinding the history of the universe, light rays will run into a wall at the beginning of time. Over the years, physicists have accumulated heaps of evidence that black holes exist, and that the universe began with an event that looks very much like a Big Bang. But do these phenomena truly represent space-time singularities? Many physicists find the actual existence of such points unthinkable. When you try to calculate the fate of a particle approaching the singularity, general relativity glitches and gives impossible, infinite answers. 'The singularity means a lack of predictability,' Liu said. 'Your theory just breaks down.' But the particle in the real world must have a fate of some sort. So a more universal theory that can predict that fate—very likely a quantum theory—must take over. General relativity is a classical theory, meaning that space-time takes on one, and only one, shape at every moment. In contrast, matter is quantum mechanical, meaning it can have multiple possible states at once—a feature known as superposition. Since space-time reacts to the matter in it, theorists expect that any matter particles in a superposition of occupying two different locations should force space-time into a superposition of two distortions. That is, space-time and gravity should also follow quantum rules. But physicists haven't yet worked out what those rules are. Into the Onion Theorists approach their quest for a quantum theory of gravity the way they might peel an onion: layer by layer. Each layer represents a theory of a universe that imperfectly approximates the real one. The deeper you go, the more of the interplay between quantum matter and space-time you can capture. The German physicist-soldier Karl Schwarzschild calculated the shape that space-time takes around a massive point. Years later, physicists realized that this geometry contains a singularity. COURTESY OF PUBLIC DOMAIN Penrose worked in the outermost layer of the onion. He used the general theory of relativity and ignored quantumness entirely. In effect, he proved that the space-time fabric has singularities when it is completely devoid of any quantum matter. Physicists aspire to someday reach the onion's core. In it, they'll find a theory describing both space-time and matter in all their quantum glory. This theory would have no blind spots—all calculations should yield meaningful results. But what about the middle layers? Could physicists resolve Penrose's singularities by moving to something a little more quantum, and therefore a little more realistic? 'It was the obvious speculation, that somehow quantum effects should fix the singularity,' Penington said. They first tried to do so in the late 2000s. The assumption that had confined Penrose's proof to the outermost layer was that energy is never negative. That's true in everyday, classical situations, but not in quantum mechanics. Energy goes negative, at least momentarily, in quantum phenomena such as the Casimir effect, where (experiments show) two metal plates attract each other in a vacuum. And negative energies play a role in the way black holes are thought to radiate particles, eventually 'evaporating' entirely. All the deeper, quantum layers of the onion would feature this exotic energetic behavior. The physicist who peeled the top layer was Aron Wall, then based at the University of Maryland and now at the University of Cambridge. To cut into the quantum realm and abandon Penrose's energy assumption, Wall latched on to a theoretical discovery made in the 1970s by Jacob Bekenstein. Bekenstein knew that for any given region of space, the contents of the region grow more mixed up as time goes on. In other words, entropy, a measure of this mixing, tends to increase, a rule known as the second law of thermodynamics. While considering a region that contains a black hole, the physicist realized that the entropy comes from two sources. There's the standard source—the number of ways that quantum particles in the space around the black hole could be arranged. But the black hole has entropy too, and the amount depends on the black hole's surface area. So the total entropy of the region is a sum: the surface area of the black hole plus the entropy of nearby quantum stuff. This observation became known as the 'generalized' second law. Wall 'made it his mission to understand the generalized second law,' said Raphael Bousso, a physicist at Berkeley. 'He was thinking about it in much clearer and much better ways than everybody else on the planet.' Reaching the quantum layers of the onion would mean accommodating negative energy and the presence of quantum particles. To do so, Wall reasoned that he could take any surface area in general relativity and add to it the entropy of those particles, as the generalized second law suggested. Penrose's proof of his singularity theorem had involved the trapped surface. So Wall upgraded it to a 'quantum trapped surface.' And when he reworked Penrose's singularity theorem in this way, it held. Singularities form even in the presence of quantum particles. Wall published his findings in 2010. In 2010, Aron Wall, now at the University of Cambridge, revamped Penrose's proof to show that singularities exist in a world where space-time has no quantum properties but is filled with particles that do. PHOTOGRAPH: NICOLE WALL 'Aron's paper was a seminal breakthrough in combining quantum mechanics and gravity in a more precise way,' Penington said. Having peeled back the classical outer layer of the onion, where energy is always positive, Wall reached a lightly quantum layer—a context physicists call semiclassical. In a semiclassical world, space-time guides the journeys of quantum particles, but it cannot react to their presence. A semiclassical black hole will radiate particles, for instance, since that's a consequence of how particles experience a space-time warped into a black hole shape. But the space-time—the black hole itself—will never actually shrink in size even as the radiation leaks energy into the void for all eternity. That's almost, but not exactly, what happens in the real universe. You could watch a black hole radiate particles for a century without seeing it shrink a single nanometer. But if you could watch for longer—many trillions upon trillions of years—you would see the black hole waste away to nothing. The next onion layer beckoned. Dialing Up the Quantumness Bousso recently revisited Wall's proof and found that he could cut a little deeper. What about the world where black holes shrink as they radiate? In this scenario, the space-time fabric can react to quantum particles. Using more refined mathematical machinery developed by Wall and others since 2010, Bousso found that, despite the intensified quantumness of his scenario, singularities continue to exist. He posted his paper, which has not yet been peer-reviewed, in January. The world of Bousso's new theorem still departs from our universe in notable ways. For mathematical convenience, he assumed that there's an unlimited variety of particles—an unrealistic assumption that makes some physicists wonder whether this third layer matches reality (with its 17 or so known particles) any better than the second layer does. 'We don't have an infinite number of quantum fields,' said Edgar Shaghoulian, a physicist at the University of California, Santa Cruz. Still, for some experts, Bousso's work delivers a satisfying denouement to the Penrose and Wall singularity story, despite its unrealistic abundance of particles. It establishes that singularities can't be avoided, even in space-times with mild reactions to quantum matter. 'Just by adding small quantum corrections, you can't prevent the singularity,' Penington said. Wall and Bousso's work 'answers that pretty definitively.' The Real Singularity But Bousso's theorem still doesn't guarantee that singularities must form in our universe. Some physicists hold out hope that the dead ends do somehow go away. What seems like a singularity could actually connect to somewhere else. In the case of a black hole, perhaps those light rays end up in another universe. And a lack of a Big Bang singularity might imply that our universe began with a 'Big Bounce.' The idea is that a previous universe, as it collapsed under the pull of gravity, somehow dodged the formation of a singularity and instead bounced into a period of expansion. Physicists who are developing bounce theories often work in the second layer of the onion, using semiclassical physics that exploits negative-energy quantum effects to get around the singularity required by the Penrose and Hawking theorems. In light of the newer theorems, they will now need to swallow the uncomfortable truth that their theories violate the generalized second law as well. One physicist pursuing bounces, Surjeet Rajendran of Johns Hopkins University, says he is undaunted. He points out that not even the generalized second law is gospel truth. Rejecting it would make singularities avoidable and continuations of space-time possible. Singularity skeptics can also appeal to the theory at the core of the onion, where space-time behaves in truly quantum ways, such as taking on superpositions. There, nothing can be taken for granted. It becomes hard to define the concept of area, for instance, so it's not clear what form the second law should take, and therefore the new theorems won't hold. Bousso and like-minded physicists, however, suspect that a highly quantum arena with no notion of area is tantamount to a dead-end for a light ray, and therefore that something Penrose would recognize as a singularity should persist in the core theory and in our universe. The beginning of the cosmos and the hearts of black holes would truly mark edges of the map where clocks can't tick and space stops. 'Inside of black holes, I am positive there is some notion of singularity,' said Netta Engelhardt, a physicist at MIT who has worked with Wall. In that case, the still-unknown fundamental theory of quantum gravity would not kill singularities but demystify them. This truer theory would allow physicists to ask questions and calculate meaningful answers, but the language of those questions and answers would change dramatically. Space-time quantities like position, curvature and duration might be useless for describing a singularity. There, where time ends, other quantities or concepts might have to take their place. 'If you had to make me guess,' Penington said, 'whatever quantum state describes the singularity itself does not have a notion of time.' Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.
WIRED
13-07-2025
- Science
- WIRED
For Algorithms, Memory Is a Far More Powerful Resource Than Time
Jul 13, 2025 7:00 AM One computer scientist's 'stunning' proof is the first progress in 50 years on one of the most famous questions in computer science. Illustration: Irene Pérez/Quanta Magazine The original version of this story appeared in Quanta Magazine . One July afternoon in 2024, Ryan Williams set out to prove himself wrong. Two months had passed since he'd hit upon a startling discovery about the relationship between time and memory in computing. It was a rough sketch of a mathematical proof that memory was more powerful than computer scientists believed: A small amount would be as helpful as a lot of time in all conceivable computations. That sounded so improbable that he assumed something had to be wrong, and he promptly set the proof aside to focus on less crazy ideas. Now, he'd finally carved out time to find the error. That's not what happened. After hours of poring over his argument, Williams couldn't find a single flaw. 'I just thought I was losing my mind,' said Williams, a theoretical computer scientist at the Massachusetts Institute of Technology. For the first time, he began to entertain the possibility that maybe, just maybe, memory really was as powerful as his work suggested. Over the months that followed, he fleshed out the details, scrutinized every step, and solicited feedback from a handful of other researchers. In February, he finally posted his proof online, to widespread acclaim. 'It's amazing. It's beautiful,' said Avi Wigderson, a theoretical computer scientist at the Institute for Advanced Study in Princeton, New Jersey. As soon as he heard the news, Wigderson sent Williams a congratulatory email. Its subject line: 'You blew my mind.' Time and memory (also called space) are the two most fundamental resources in computation: Every algorithm takes some time to run and requires some space to store data while it's running. Until now, the only known algorithms for accomplishing certain tasks required an amount of space roughly proportional to their run time, and researchers had long assumed there's no way to do better. Williams' proof established a mathematical procedure for transforming any algorithm—no matter what it does—into a form that uses much less space. Ryan Williams stunned his colleagues with a milestone proof about the relationship between time and space in computation. Photograph: Katherine Taylor for Quanta Magazine What's more, this result—a statement about what you can compute given a certain amount of space—also implies a second result, about what you cannot compute in a certain amount of time. This second result isn't surprising in itself: Researchers expected it to be true, but they had no idea how to prove it. Williams' solution, based on his sweeping first result, feels almost cartoonishly excessive, akin to proving a suspected murderer guilty by establishing an ironclad alibi for everyone else on the planet. It could also offer a new way to attack one of the oldest open problems in computer science. 'It's a pretty stunning result, and a massive advance,' said Paul Beame, a computer scientist at the University of Washington. 'It's a little bit less of a surprise that it's Ryan doing this.' Space to Roam Williams, 46, has an open, expressive face and a hint of gray in his hair. His office, which looks out over the colorful spires of MIT's Stata Center, is another illustration of the creative use of space. A pair of yoga mats have transformed a window ledge into a makeshift reading nook, and the desk is tucked into an oddly shaped corner, freeing up room for a couch facing a large whiteboard brimming with mathematical scribblings. MIT is a long way from Williams' childhood home in rural Alabama, where there was no shortage of space. He grew up on a 50-acre farm and first saw a computer at age 7, when his mother drove him across the county for a special academic enrichment class. He recalled being transfixed by a simple program for generating a digital fireworks display. 'It was taking a random color and sending it in a random direction from the middle of the monitor,' Williams said. 'You couldn't have predicted what picture you're going to get.' The world of computers seemed a wild and wonderful playground, full of infinite possibilities. Young Williams was hooked. 'I was writing programs to myself, on paper, to be run on a future computer,' he said. 'My parents didn't really know what to do with me.' Williams' office, like his new result, makes creative use of space. Photograph: Katherine Taylor for Quanta Magazine As he grew older, Williams advanced from imaginary computers to real ones. For his last two years of high school, he transferred to the Alabama School of Math and Science, a prestigious public boarding school, where he first encountered the theoretical side of computer science. 'I realized that there was a wider world of things out there, and that there was a way to think mathematically about computers,' he said. 'That's what I wanted to do.' Williams was especially drawn to a branch of theoretical computer science called computational complexity theory. It deals with the resources (such as time and space) that are needed to solve computational problems such as sorting lists or factoring numbers. Most problems can be solved by many different algorithms, each with its own demands on time and space. Complexity theorists sort problems into categories, called complexity classes, based on the resource demands of the best algorithms for solving them—that is, the algorithms that run fastest or use the least amount of space. But how do you make the study of computational resources mathematically rigorous? You won't get far if you try to analyze time and space by comparing minutes to megabytes. To make any progress, you need to start with the right definitions. Getting Resourceful Those definitions emerged from the work of Juris Hartmanis, a pioneering computer scientist who had experience making do with limited resources. He was born in 1928 into a prominent Latvian family, but his childhood was disrupted by the outbreak of World War II. Occupying Soviet forces arrested and executed his father, and after the war Hartmanis finished high school in a refugee camp. He went on to university, where he excelled even though he couldn't afford textbooks. 'I compensated by taking very detailed notes in lectures,' he recalled in a 2009 interview. 'There is a certain advantage to [having] to improvise and overcome difficulties.' Hartmanis immigrated to the United States in 1949, and worked a series of odd jobs—building agricultural machinery, manufacturing steel and even serving as a butler—while studying mathematics at the University of Kansas City. He went on to a spectacularly successful career in the young field of theoretical computer science. In 1960, while working at the General Electric research laboratory in Schenectady, New York, Hartmanis met Richard Stearns, a graduate student doing a summer internship. In a pair of groundbreaking papers they established precise mathematical definitions for time and space. These definitions gave researchers the language they needed to compare the two resources and sort problems into complexity classes. In the 1960s, Juris Hartmanis established the definitions that computer scientists use to analyze space and time. Courtesy of the Division of Rare and Manuscript Collections, Cornell University Library One of the most important classes goes by the humble name 'P.' Roughly speaking, it encompasses all problems that can be solved in a reasonable amount of time. An analogous complexity class for space is dubbed 'PSPACE.' The relationship between these two classes is one of the central questions of complexity theory. Every problem in P is also in PSPACE, because fast algorithms just don't have enough time to fill up much space in a computer's memory. If the reverse statement were also true, the two classes would be equivalent: Space and time would have comparable computational power. But complexity theorists suspect that PSPACE is a much larger class, containing many problems that aren't in P. In other words, they believe that space is a far more powerful computational resource than time. This belief stems from the fact that algorithms can use the same small chunk of memory over and over, while time isn't as forgiving—once it passes, you can't get it back. 'The intuition is just so simple,' Williams said. 'You can reuse space, but you can't reuse time.' But intuition isn't good enough for complexity theorists: They want rigorous proof. To prove that PSPACE is larger than P, researchers would have to show that for some problems in PSPACE, fast algorithms are categorically impossible. Where would they even start? A Space Odyssey As it happened, they started at Cornell University, where Hartmanis moved in 1965 to head the newly established computer science department. Under his leadership it quickly became a center of research in complexity theory, and in the early 1970s, a pair of researchers there, John Hopcroft and Wolfgang Paul, set out to establish a precise link between time and space. 'I thought about it, and I was like, 'Well, that just simply can't be true.'' Hopcroft and Paul knew that to resolve the P versus PSPACE problem, they'd have to prove that you can't do certain computations in a limited amount of time. But it's hard to prove a negative. Instead, they decided to flip the problem on its head and explore what you can do with limited space. They hoped to prove that algorithms given a certain space budget can solve all the same problems as algorithms with a slightly larger time budget. That would indicate that space is at least slightly more powerful than time—a small but necessary step toward showing that PSPACE is larger than P. With that goal in mind, they turned to a method that complexity theorists call simulation, which involves transforming existing algorithms into new ones that solve the same problems, but with different amounts of space and time. To understand the basic idea, imagine you're given a fast algorithm for alphabetizing your bookshelf, but it requires you to lay out your books in dozens of small piles. You might prefer an approach that takes up less space in your apartment, even if it takes longer. A simulation is a mathematical procedure you could use to get a more suitable algorithm: Feed it the original, and it'll give you a new algorithm that saves space at the expense of time. Algorithm designers have long studied these space-time trade-offs for specific tasks like sorting. But to establish a general relationship between time and space, Hopcroft and Paul needed something more comprehensive: a space-saving simulation procedure that works for every algorithm, no matter what problem it solves. They expected this generality to come at a cost. A universal simulation can't exploit the details of any specific problem, so it probably won't save as much space as a specialized simulation. But when Hopcroft and Paul started their work, there were no known universal methods for saving space at all. Even saving a small amount would be progress. The breakthrough came in 1975, after Hopcroft and Paul teamed up with a young researcher named Leslie Valiant. The trio devised a universal simulation procedure that always saves a bit of space. No matter what algorithm you give it, you'll get an equivalent one whose space budget is slightly smaller than the original algorithm's time budget. 'Anything you can do in so much time, you can also do in slightly less space,' Valiant said. It was the first major step in the quest to connect space and time. In 1975, Leslie Valiant helped prove that space is a slightly more powerful computational resource than time. Photograph: Katherine Taylor for Quanta Magazine But then progress stalled, and complexity theorists began to suspect that they'd hit a fundamental barrier. The problem was precisely the universal character of Hopcroft, Paul and Valiant's simulation. While many problems can be solved with much less space than time, some intuitively seemed like they'd need nearly as much space as time. If so, more space-efficient universal simulations would be impossible. Paul and two other researchers soon proved that they are indeed impossible, provided you make one seemingly obvious assumption: Different chunks of data can't occupy the same space in memory at the same time. 'Everybody took it for granted that you cannot do better,' Wigderson said. Paul's result suggested that resolving the P versus PSPACE problem would require abandoning simulation altogether in favor of a different approach, but nobody had any good ideas. That was where the problem stood for 50 years—until Williams finally broke the logjam. First, he had to get through college. Complexity Classes In 1996, the time came for Williams to apply to colleges. He knew that pursuing complexity theory would take him far from home, but his parents made it clear that the West Coast and Canada were out of the question. Among his remaining options, Cornell stood out to him for its prominent place in the history of his favorite discipline. 'This guy Hartmanis defined the time and space complexity classes,' he recalled thinking. 'That was important for me.' Williams was admitted to Cornell with generous financial aid and arrived in the fall of 1997, planning to do whatever it took to become a complexity theorist himself. His single-mindedness stuck out to his fellow students. 'He was just super-duper into complexity theory,' said Scott Aaronson, a computer scientist at the University of Texas, Austin, who overlapped with Williams at Cornell. Williams grew interested in the relationship between space and time as an undergraduate but never found an opportunity to work on it until last year. Photograph: Katherine Taylor for Quanta Magazine But by sophomore year, Williams was struggling to keep up in courses that emphasized mathematical rigor over intuition. After he got a middling grade in a class on the theory of computing, the teacher suggested he consider other careers. But Williams wouldn't give up his dream. He doubled down and enrolled in a graduate theory course, hoping that a stellar grade in the harder class would look impressive on his grad school applications. The professor teaching that graduate course was Hartmanis, by then an elder statesman in the field. Williams began attending Hartmanis' office hours every week, where he was almost always the only student who showed up. His tenacity paid off: he earned an A in the course, and Hartmanis agreed to advise him on an independent research project the following semester. Their weekly meetings continued throughout Williams' time in college. Hartmanis encouraged him to cultivate an individual approach to complexity research and gently steered him away from dead ends. 'I was deeply influenced by him then,' Williams said. 'I guess I still am now.' 'If you get any mathematical result which is the best thing in 50 years, you must be doing something right.' But despite earning a coveted graduate research fellowship from the National Science Foundation, Williams was rejected by every doctoral program he applied to. On hearing the news, Hartmanis phoned a colleague, then turned around and congratulated Williams on getting accepted into a yearlong master's program at Cornell. A year later Williams again applied to various doctoral programs, and with that extra research experience under his belt, he found success. Williams continued working in complexity theory in grad school and the years that followed. In 2010, four years after receiving his doctorate, he proved a milestone result—a small step, but the largest in decades, toward solving the most famous question in theoretical computer science, about the nature of hard problems. That result cemented Williams' reputation, and he went on to write dozens of other papers on different topics in complexity theory. P versus PSPACE wasn't one of them. Williams had been fascinated by the problem since he first encountered it in college. He'd even supplemented his computer science curriculum with courses in logic and philosophy, seeking inspiration from other perspectives on time and space, to no avail. 'It's always been in the back of my mind,' Williams said. 'I just couldn't think of anything interesting enough to say about it.' Last year, he finally found the opportunity he'd been waiting for. Squishy Pebbles The story of Williams' new result started with progress on a different question about memory in computation: What problems can be solved with extremely limited space? In 2010, the pioneering complexity theorist Stephen Cook and his collaborators invented a task, called the tree evaluation problem, that they proved would be impossible for any algorithm with a space budget below a specific threshold. But there was a loophole. The proof relied on the same commonsense assumption that Paul and his colleagues had made decades earlier: Algorithms can't store new data in space that's already full. For over a decade, complexity theorists tried to close that loophole. Then, in 2023, Cook's son James and a researcher named Ian Mertz blew it wide open, devising an algorithm that solved the tree evaluation problem using much less space than anyone thought possible. The elder Cook's proof had assumed that bits of data were like pebbles that have to occupy separate places in an algorithm's memory. But it turns out that's not the only way to store data. 'We can actually think about these pebbles as things that we can squish a little bit on top of each other,' Beame said. James Cook (left) and Ian Mertz recently devised a new algorithm that solved a specific problem using much less space than anyone thought possible. Photographs: Colin Morris; Michal Koucký Cook and Mertz's algorithm roused the curiosity of many researchers, but it wasn't clear that it had any applications beyond the tree evaluation problem. 'Nobody saw how central it is to time versus space itself,' Wigderson said. Ryan Williams was the exception. In spring 2024, a group of students gave a presentation about the Cook and Mertz paper as their final project in a class he was teaching. Their enthusiasm inspired him to take a closer look. As soon as he did, an idea jumped out at him. Cook and Mertz's method, he realized, was really a general-purpose tool for reducing space usage. Why not use it to power a new universal simulation linking time and space—like the one designed by Hopcroft, Paul and Valiant, but better? That classic result was a way to transform any algorithm with a given time budget into a new algorithm with a slightly smaller space budget. Williams saw that a simulation based on squishy pebbles would make the new algorithm's space usage much smaller—roughly equal to the square root of the original algorithm's time budget. That new space-efficient algorithm would also be much slower, so the simulation was not likely to have practical applications. But from a theoretical point of view, it was nothing short of revolutionary. For 50 years, researchers had assumed it was impossible to improve Hopcroft, Paul and Valiant's universal simulation. Williams' idea—if it worked—wouldn't just beat their record—it would demolish it. 'I thought about it, and I was like, 'Well, that just simply can't be true,'' Williams said. He set it aside and didn't come back to it until that fateful day in July, when he tried to find the flaw in the argument and failed. After he realized that there was no flaw, he spent months writing and rewriting the proof to make it as clear as possible. At the end of February, Williams finally put the finished paper online. Cook and Mertz were as surprised as everyone else. 'I had to go take a long walk before doing anything else,' Mertz said. Valiant got a sneak preview of Williams' improvement on his decades-old result during his morning commute. For years, he's taught at Harvard University, just down the road from Williams' office at MIT. They'd met before, but they didn't know they lived in the same neighborhood until they bumped into each other on the bus on a snowy February day, a few weeks before the result was public. Williams described his proof to the startled Valiant and promised to send along his paper. 'I was very, very impressed,' Valiant said. 'If you get any mathematical result which is the best thing in 50 years, you must be doing something right.' PSPACE: The Final Frontier With his new simulation, Williams had proved a positive result about the computational power of space: Algorithms that use relatively little space can solve all problems that require a somewhat larger amount of time. Then, using just a few lines of math, he flipped that around and proved a negative result about the computational power of time: At least a few problems can't be solved unless you use more time than space. That second, narrower result is in line with what researchers expected. The weird part is how Williams got there, by first proving a result that applies to all algorithms, no matter what problems they solve. 'I still have a hard time believing it,' Williams said. 'It just seems too good to be true.' Williams used Cook and Mertz's technique to establish a stronger link between space and time—the first progress on that problem in 50 years. Photograph: Katherine Taylor for Quanta Magazine Phrased in qualitative terms, Williams' second result may sound like the long-sought solution to the P versus PSPACE problem. The difference is a matter of scale. P and PSPACE are very broad complexity classes, while Williams' results work at a finer level. He established a quantitative gap between the power of space and the power of time, and to prove that PSPACE is larger than P, researchers will have to make that gap much, much wider. That's a daunting challenge, akin to prying apart a sidewalk crack with a crowbar until it's as wide as the Grand Canyon. But it might be possible to get there by using a modified version of Williams' simulation procedure that repeats the key step many times, saving a bit of space each time. It's like a way to repeatedly ratchet up the length of your crowbar—make it big enough, and you can pry open anything. That repeated improvement doesn't work with the current version of the algorithm, but researchers don't know whether that's a fundamental limitation. 'It could be an ultimate bottleneck, or it could be a 50-year bottleneck,' Valiant said. 'Or it could be something which maybe someone can solve next week.' If the problem is solved next week, Williams will be kicking himself. Before he wrote the paper, he spent months trying and failing to extend his result. But even if such an extension is not possible, Williams is confident that more space exploration is bound to lead somewhere interesting—perhaps progress on an entirely different problem. 'I can never prove precisely the things that I want to prove,' he said. 'But often, the thing I prove is way better than what I wanted.' Editor's note: Scott Aaronson is a member of Quanta Magazine's advisory board. Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.
Yahoo
11-07-2025
- Yahoo
Mathematicians Say There's a Number So Big, It's Literally the Edge of Human Knowledge
"Hearst Magazines and Yahoo may earn commission or revenue on some items through these links." Here's what you'll learn when you read this story: The Busy Beaver number, or BB(n), represents a mathematical problem that tries to calculate the longest possible run-time of a Turing machine recording 1s and 0s on an infinitely long tape for various sets of instructions called states. While the first three BB(n)s equal 1, 6, and 21, respectively, it takes 107 steps to get to BB(4), and BB(5) produces a staggering 17 trillion possible Turing machines with a 47,176,870 steps being the answer. Now, as mathematicians attempt to wrap their minds around answer BB(6), they're beginning to realize that even expressing the unfathomably large number, likely bigger than the number of atoms in the universe, is itself a problem. For most people, the term 'busy beaver' brings to mind a tireless worker or (for the biologists among us) an absolutely vital ecosystem engineer. However, for mathematicians, 'busy beaver' takes on a similar-yet-unique meaning. True to the moniker's original intent, the idea represents a lot of work, but it's work pointed at a question. As computer scientists Christopher Moore puts it in a video for Quanta Magazine, 'What's the longest, most-complicated thing [a computer] can do, and then stop?' In other words, what's the longest function a computer can run that does not just run forever, stuck in an infinite loop? The solution to this question is called the Busy Beaver number, or BB(n), where the n represents a number of instructions called 'states' that a set of computers—specifically, a type of simple computer called a Turing machine—has to follow. Each state produces a certain number of programs, and each program gets its own Turing machine, so things get complicated fast. BB(1), which has just 1 state, necessitates the use of 25 Turing machines. For decades, many mathematicians believed that solving the Busy Beaver number to four states was the upper limit, but a group of experts managed to confirmed the BB(5) solution in 2024 (on Discord, of all places). Now, participants in that same Busy Beaver Challenge are learning fascinating truths about the next frontier—BB(6)—and how it just might represent the very edge of mathematics, according to a new report by New Scientist. First, a brief explanation. The aforementioned BB(1), which is the simplest version of the BB(n) problem, uses just one set of rules and produces only two outcomes—infinitely moving across the tape, or stopping at the first number. Because 1 is the most amount of steps that any of the 25 Turing machines of BB(1) will complete before finishing its program (known as halting), the answer to BB(1) is 1. As the number of states increases, so do the steps and the number of Turing machines needed to run the programs, meaning that each subsequent BB(n) is exponentially more taxing to solve. BB(2) and BB(3) are 6 and 21 respectively, but BB(4) is 107 and takes seven billion different Turing machines to solve. Granted, many of these machines continue on indefinitely and can be discarded, but many do not. The Busy Beaver number was first formulated by the Hungarian mathematician Tiber Radó in 1962, and 12 years passed before computer scientist Allen Brady determined that BB(4) runs for 107 steps before halting. For decades, this seemed like the absolute limit of what was discernible, but then mathematicians solved BB(5) in 2024 after sifting through 17 trillion (with a t) possible Turing machines. The answer? An astounding 47,176,870 steps. Quanta Magazine has an excellent explainer about how this was achieved. But finally solving BB(5) presented the next obvious question: What about BB(6)? Of course, adding just one more rule makes the problem beyond super exponentially harder, as BB(6) is estimated to require 60 quadrillion Turing machines. 'The Busy Beaver problem gives you a very concrete scale for pondering the frontier of mathematical knowledge,' computer scientist Tristan Stérin, who helped start the Busy Beaver Challenge in 2022, told New Scientist. In a new post, anonymous user 'mxdys'—who was instrumental in finally confirming BB(5)—wrote that the answer to BB(6) is likely so unfathomably large that the number itself likely needs its own explanation, as it's likely too big to describe via exponentiation. Instead, it relies on tetration (written as, say, yx, as opposed to exponentiation's xy) in which where the exponent is also iterated, creating a tower of exponents. As Scott Aaronson, an American computer scientist who helped define BB(5), notes on his blog, that means 1510 can be thought of as '10 to the 10 to the 10 and so on 15 times.' As mxdys notes, BB(6) is at least 2 tetrated to the 2 tetrated to the 2 tetrated to the 9. One mathematician speaking with New Scientist said that it's likely that the number of all atoms in the universe would look 'puny' by comparison. While these large numbers boggle the mind, they also tell mathematicians about the limitations of the foundation of modern mathematics—known as Zermelo–Fraenkel set theory (ZFC)—as well slippery mathematical concepts like the Collatz conjecture. It's unlikely that mathematicians will ever solve BB(6), but if the Busy Beaver Challenge is any evidence, that fact likely won't stop them from trying. You Might Also Like The Do's and Don'ts of Using Painter's Tape The Best Portable BBQ Grills for Cooking Anywhere Can a Smart Watch Prolong Your Life?
Scientific American
11-07-2025
- Science
- Scientific American
Science Quiz: Gotta Go Fast
Allison Parshall is an associate editor at Scientific American covering mind and brain. She writes the magazine's Contributors column and weekly online Science Quizzes. As a multimedia journalist, she contributes to Scientific American 's podcast Science Quickly. Parshall's work has also appeared in Quanta Magazine and Inverse. She graduated from New York University's Arthur L. Carter Journalism Institute with a master's degree in science, health and environmental reporting. She has a bachelor's degree in psychology from Georgetown University.
