Jonathan Cerqueira’s senior research project aims to shed new light on the 50-year-old Gottschalk surjunctivity conjecture in the study of cellular automata
Everybody loves a good mystery – playing detective to solve a theft, a murder, a kidnapping, whether a cellular automaton defined on the Cayley graph of a group can be injective but not surjective…
What? You haven’t heard of that last one? Then you haven’t talked with Jonathan Cerqueira ’21, whose Stevens Institute of Technology senior research project is focused on deepening our understanding of the Gottschalk surjunctivity conjecture, an abstract mathematical concept first proposed in 1973.
“The surjunctivity conjecture is a major open problem at the intersection of abstract algebra, dynamical systems, and graph theory,” explained Jan Cannizzo, teaching assistant professor in the Department of Mathematical Sciences, and Cerqueira’s project advisor. “Jonathan’s work does not directly tackle this conjecture, but by changing the context of the problem, he’s allowing us to think about it in different ways.”
To infinite graphs, and beyond!
Cerqueira is studying cellular automata in a very general setting. These are discrete dynamical systems that can exhibit surprisingly complex behavior. Suppose you take an infinite, highly symmetric network of vertices and edges, assign every vertex one of a handful of colors, and then create a rule for changing the color of each vertex based on the colors of its neighbors. Now apply your rule over and over again. How will the initial coloring evolve?
“Imagine that you have two different colorings of a specific kind of graph known as a Cayley graph,” Cannizzo explained. “Over time, those two colorings evolve. If they always evolve to two distinct colorings and never merge into the same state, the system is injective. If there’s a particular coloring that can serve as the initial state but that never appears as a future state, the system is surjective. And there’s this big open question that asks whether it can be injective, but not surjective. In other words, can the dynamical system defined by such an automaton contain a copy of itself?”
“The answer is ‘yes,’ if we convert the Cayley graph in a particular way,” Cerqueira said. This involves thinking about the underlying graph not as the Cayley graph of a group, but as the so-called Schreier graph of a monoid. “Several infinite families of examples demonstrate this property and, given some assumptions, it can be shown such automata are abundant. Now I’m working on generalizing this idea.”
“Jonathan is modest, but I think he’s discovered a new, large family of automata that exhibits this phenomenon of injectivity but not surjectivity,” Cannizzo added. “It puts the surjunctivity conjecture in context allows us to think about it differently, and he’s trying to understand how large this class of examples that he’s been able to study actually is.”
‘It’s satisfying to come up with original ideas’
To address this complex problem, Cerqueira relied on a surprisingly simple tool.
“I did a lot of staring at whiteboards,” he said with a laugh. “You stare at the whiteboard for two hours trying to understand the problem. You don’t get anywhere. You walk away from it, and 20 minutes later, you get an idea, and then come back to work on it a bit more. And it’s typical to have what seems like a million ideas, and then most of them fall flat, and you have to try again. I think it’s how a lot of mathematical research works!”
Clearly, the rewards outweigh the challenges.
“It’s satisfying to come up with original ideas,” Cerqueira said. “It’s our hope to get these findings published in a journal. That would be exciting.”
That element of problem-solving is what initially drew Cerqueira to the field of mathematics.
“Math sparked my curiosity and made me want to seek answers,” he recalled. “I’d mess around on Desmos graphing calculators or try to teach myself some calculus. In high school I started to see math as something truly amazing when I discovered Numberphile and other math-related YouTube channels. That’s also when I found out about mathematicians, and the idea that math is an ongoing, evolving field that could be a career path for me.”
Cerqueira soon became attracted to the universality of math, as well as its relatively lower burden to deliver immediate research results.
“If some alien beings dropped down to Earth from a different universe, they might have a different sense of aesthetics, a different language, and a different set of scientific laws,” he explained. “Despite that, they might still have studied the math we have, or they’d be able to borrow from our mathematical works far more quickly than our scientific or cultural ones. I also love the lax nature of math studies. With science, medicine, or engineering, you face a fair amount of pressure to demonstrate immediate value for your research direction. With math, people often decide their research directions based on their interests or open questions they want to take a crack at. With pure math, people understand that over the span of a few hundred years, something can go from recreational math, to something studied for its own sake, to something with broad applications, as happened with topology, number theory, and, to a lesser degree, cellular automata.”
Stevens offered Cerqueira the opportunity to immerse himself in that supportive environment while also experiencing the broader range of scientific disciplines.
“I chose Stevens for its slightly smaller campus, as well as the atmosphere that comes along with an engineering school,” he said. “Everyone’s always doing something, working on a project, or involving themselves in some organization. I’ve been involved in seven clubs and organizations, and I’ve met so many people. I enjoy the liveliness, Hoboken, the history of the school, and most of all, I love the pace of it. The classes, clubs, and everything move fast. It feels like I was a freshman only yesterday.”
For now, Cerqueira’s research continues – both into surjunctivity, and also into which doctoral program he’ll attend this fall.
“Jonathan has made our department very proud, especially because he’s going to go on to pursue his Ph.D. in mathematics right out of his pure and applied mathematics bachelor’s degree, which he’s finishing in only three years,” Cannizzo said. “He was my student in a class I taught on mathematical proofs, and I was impressed with his mathematical skills. When he asked me about doing some research together the following summer, I was happy to agree, and it’s been a great pleasure working with him. By changing the context of the Gottschalk surjunctivity conjecture and pursuing this related, parallel question, he has helped put the conjecture into perspective.”
An exercise in pure mathematics has led to a wide-ranging theory of how the world comes together.
On a mild autumn day in 2016, the Hungarian mathematician Gábor Domokos arrived on the geophysicist Douglas Jerolmack’s doorstep in Philadelphia. Domokos carried with him his suitcases, a bad cold and a burning secret.
The two men walked across a gravel lot behind the house, where Jerolmack’s wife ran a taco cart. Their feet crunched over crushed limestone. Domokos pointed down.
“How many facets do each of these gravel pieces have?” he said. Then he grinned. “What if I told you that the number was always somewhere around six?” Then he asked a bigger question, one that he hoped would worm its way into his colleague’s brain. What if the world is made of cubes?
At first, Jerolmack objected. Houses can be built out of bricks, but Earth is made of rocks. Obviously, rocks vary. Mica flakes into sheets; crystals crack on sharply defined axes. But from mathematics alone, Domokos argued, any rocks that broke randomly would crack into shapes that have, on average, six faces and eight vertices. Considered together, they would all be shadowy approximations converging on a sort of ideal cube. Domokos had proved it mathematically, he said. Now he needed Jerolmack’s help to show that this is what nature does.
“It was geometry with an exact prediction that was borne out in the natural world, with essentially no physics involved,” said Jerolmack, a professor at the University of Pennsylvania. “How in the hell does nature let this happen?”
Over the next few years, the pair chased their geometric vision from microscopic fragments to rock outcrops to planetary surfaces and even to Plato’s Timaeus, suffusing the project with an additional air of mysticism. The foundational Greek philosopher, writing around 360 BCE, had matched his five Platonic solids with five supposed elements: earth, air, fire, water and star stuff. With either foresight or luck or a little of both, Plato paired cubes, the most stackable shape, with earth. “I was like, oh, OK, now we’re getting a little bit metaphysical,” Jerolmack said.
But they kept finding cuboid averages in nature, plus a few non-cubes that could be explained with the same theories. They ended up with a new mathematical framework: a descriptive language to express how all things fall apart. When their paper was published earlier this year, it came titled like a particularly esoteric Harry Potter novel: “Plato’s Cube and the Natural Geometry of Fragmentation.”
Several geophysicists contacted by Quanta say the same mathematical framework might also help with problems like understanding erosion from cracked cliff faces, or preventing hazardous rock slides. “That is really, really exciting,” said the University of Edinburgh geomorphologist Mikaël Attal, one of two scientists who reviewed the paper before publication. The other reviewer, the Vanderbilt geophysicist David Furbish, said, “A paper like this makes me think: Can I somehow make use of these ideas?”
All Possible Breaks
Long before he came to Philadelphia, Domokos had more innocuous mathematical questions.
Suppose you fracture something into many pieces. You now have a mosaic: a collection of shapes that could tile back together with no overlaps or gaps, like the floor of an ancient Roman bath. Further suppose those shapes are all convex, with no indentations.
First Domokos wanted to see if geometry alone could predict what shapes, on average, would make up that kind of mosaic. Then he wanted to be able to describe all other possible collections of shapes you could find.
In two dimensions, you can try this out without smashing anything. Take a sheet of paper. Make a random slice that divides the page into two pieces. Then make another random slice through each of those two polygons. Repeat this random process a few more times. Then count up and average the number of vertices on all the bits of paper.
For a geometry student, predicting the answer isn’t too hard. “I bet you a box of beer that I can make you derive that formula within two hours,” Domokos said. The pieces should average four vertices and four sides, averaging to a rectangle.
You could also consider the same problem in three dimensions. About 50 years ago, the Russian nuclear physicist, dissident and Nobel Peace Prize winner Andrei Dmitrievich Sakharov posed the same problem while chopping heads of cabbage with his wife. How many vertices should the cabbage pieces have, on average? Sakharov passed the problem on to the legendary Soviet mathematician Vladimir Igorevich Arnold and a student. But their efforts to solve it were incomplete and have largely been forgotten.
Unaware of this work, Domokos wrote a proof which pointed to cubes as the answer. He wanted to double-check, though, and he suspected that if an answer to the same problem already existed, it would be locked in an inscrutable volume by the German mathematicians Wolfgang Weil and Rolf Schneider, an 80-year-old titan in the field of geometry. Domokos is a professional mathematician, but even he found the text daunting.
“I found someone who was willing to read that part of the book for me and translate it back into human language,” Domokos said. He found the theorem for any number of dimensions. That confirmed that cubes were indeed the 3D answer.
Now Domokos had the average shapes produced by splitting a flat surface or a three-dimensional block. But then a larger quest emerged. Domokos realized that he could also develop a mathematical description not just of averages, but of potentiality: Which collections of shapes are even mathematically possible when something falls apart?
Remember, the shapes produced after something falls apart are a mosaic. They fit together with no overlap or gaps. Those cut-up rectangles, for example, can easily tile together to fill in a mosaic in two dimensions. So can hexagons, in an idealized case of what mathematicians would call a Voronoi pattern. But pentagons? Octagons? They don’t tile.
In order to properly classify mosaics, Domokos started describing them with two numbers. The first is the average number of vertices per cell. The second is the average number of different cells sharing each vertex. So in a mosaic of hexagonal bath tiles, for example, each cell is a hexagon, which has six vertices. And each vertex is shared by three hexagons.
In a mosaic, only certain combinations of these two parameters work, forming a narrow swath of shapes that could possibly result from something falling apart.
Once again, this full swath was fairly easy to find in two dimensions, but much harder in three. Cubes stack together well in 3D, of course, but so do other combinations of shapes, including those that form a 3D version of the Voronoi pattern. To keep the problem feasible, Domokos restricted himself to just mosaics with orderly, convex cells that share the same vertices. Eventually he and the mathematician Zsolt Lángi devised a new conjecture that sketched out the curve of all possible three-dimensional mosaics like this. They published it in Experimental Mathematics, and “then I sent the whole thing to Rolf Schneider, who is of course the god,” Domokos said.
“I asked him whether he wanted me to explain how I got this conjecture, but he reassured me that he knew,” Domokos said, laughing. “That meant like a hundred times more than being accepted in any journal.”
More importantly, Domokos now had a framework. Mathematics offered a way to classify all the patterns that surfaces and blocks could break into. Geometry also predicted that if you fragmented a flat surface randomly, it would break into rough rectangles, and if you did the same in three dimensions, it would produce rough cubes.
But for any of this to matter to anyone other than a few mathematicians, Domokos had to prove that these same rules manifest themselves in the real world.
From Geometry to Geology
By the time Domokos swung through Philadelphia in 2016, he had already made some progress on the real-world problem. He and his colleagues at the Budapest University of Technology and Economics had gathered shards of dolomite eroded from a cliff face on the Hármashatárhegy mountain in Budapest. Over several days, a lab tech with no presuppositions about a universal conspiracy toward cubes painstakingly counted faces and vertices on hundreds of grains. On average? Six faces, eight vertices. Working with János Török, a specialist in computer simulations, and Ferenc Kun, an expert on fragmentation physics, Domokos found that cuboid averages showed up in rock types like gypsum and limestone as well.
With the math and the early physical evidence, Domokos pitched his idea to a stunned Jerolmack. “Somehow he’s cast a spell, and everything else disappears for a moment,” Jerolmack said.
Their alliance was a familiar one. Years ago, Domokos had won renown by proving the existence of the Gömböc, a curious three-dimensional shape that swivels into an upright resting position no matter how you push it. To see if Gömböcs existed in the natural world, he had recruited Jerolmack, who helped apply the concept to explain the rounding of pebbles on Earth and Mars. Now Domokos was again asking for help in translating lofty mathematical concepts into literal stone.
The two men settled on a new plan. To prove Plato’s cubes actually appear in nature, they needed to show more than just a coincidental echo between geometry and a few handfuls of rock. They needed to consider all rocks and then sketch out a convincing theory of how abstract math could percolate down through messy geophysics and into even messier reality.
At first, “everything seemed to work,” Jerolmack said. Domokos’ mathematics had predicted that rock shards should average out to cubes. An increasing number of actual rock shards seemed happy to comply. But Jerolmack soon realized that proving the theory would require confronting rule-breaking cases, too.
After all, the same geometry offered a vocabulary to describe the many other mosaic patterns that could exist in both two and three dimensions. Off the top of his head, Jerolmack could picture a few real-world fractured rocks that didn’t look like rectangles or cubes at all but could still be classified into this larger space.
Perhaps these examples would sink the cube-world theory entirely. More promisingly, perhaps they would arise only in distinct circumstances and carry separate lessons for geologists. “I said I know that it doesn’t work everywhere, and I need to know why,” Jerolmack said.
Over the next few years, working on both sides of the Atlantic, Jerolmack and the rest of the team started plotting where real examples of broken rocks fell within Domokos’ framework. When the team investigated surface systems that are essentially two-dimensional — cracking permafrost in Alaska, a dolomite outcrop, and the exposed cracks of a granite block — they found polygons averaging four sides and four vertices, just like the sliced-up sheet of paper. Each of these geological cases seemed to appear where rocks had simply fractured. Here Domokos’ predictions held up.
Another type of fractured slab, meanwhile, proved to be what Jerolmack had hoped for: an exception with its own distinct story to tell. Mud flats that dry, crack, get wet, heal and then crack again have cells averaging six sides and six vertices, following the roughly hexagonal Voronoi pattern. Rock made from cooling lava, which solidifies downward from the surface, can take on a similar appearance.
Tellingly, these systems tended to form under a different type of stress — when forces pulled outward on a rock instead of pushing it in. The geometry revealed the geology. And Jerolmack and Domokos thought this Voronoi pattern, even if it was relatively rare, might also occur on scales far larger than they had previously considered.
Counting the Crust
Midway through the project, the team met in Budapest and spent three whirlwind days sprinting to incorporate more natural examples. Soon Jerolmack pulled up a new pattern on his computer: the mosaic of how Earth’s tectonic plates fit together. Plates are confined to the lithosphere, a nearly two-dimensional skin on the surface of the planet. The pattern looked familiar, and Jerolmack called the others over. “We were like, oh wow,” he said.
By eye, the plates looked as if they hewed to the Voronoi pattern, not the rectangular one. Then the team counted. In a perfect Voronoi mosaic of hexagons in a flat plane, each cell would have six vertices. The actual tectonic plates averaged 5.77 vertices.
For a geophysicist, that was close enough to celebrate. For a mathematician, not so much. “Doug was getting into a good mood. He was working like hell,” Domokos said. “I was getting in a depressed mood for the next day, because I was just thinking about the gap.”
Domokos went home for the night, the difference still gnawing at him. He wrote down the numbers again. And then it hit him. A mosaic of hexagons can tile a plane. But Earth isn’t a flat plane, at least outside certain corners of YouTube. Think of a soccer ball, covered in both hexagons and pentagons. Domokos crunched the numbers for the surface of a sphere and found that on a globe, Voronoi mosaic cells should average 5.77 vertices.
This insight might help researchers answer a major open question in geophysics: How did Earth’s tectonic plates form? One idea holds that plates are just a byproduct of burbling convection cells deep in the mantle. But an opposing camp holds that Earth’s crust is a separate system — one that expanded, grew brittle and cracked open. The observed Voronoi pattern of plates, reminiscent of much smaller mud flats, might support the second argument, Jerolmack said. “That’s also what made me realize how important that paper was,” Attal said. “It’s really phenomenal.”
A Revealing Break
In three dimensions, meanwhile, exceptions to the cuboid rule were rare enough. And they too could be produced by simulating unusual, outward-pulling forces. One distinctively non-cubic rock formation lies on the coast of Northern Ireland, where waves lap against tens of thousands of basalt columns. In Irish this is Clochán na bhFomhórach, the steppingstones of a race of supernatural beings; the English name is the Giant’s Causeway.
Crucially, those columns and other similar volcanic rock formations are six-sided. But Török’s simulations produced Giant’s Causeway-like mosaics as three-dimensional structures that had simply grown up from a two-dimensional Voronoi base, itself produced when volcanic rock cooled.
Zooming out, the team argues, you could classify most real fractured-rock mosaics using just Platonic rectangles, 2D Voronoi patterns, and then — overwhelmingly — Platonic cubes in three dimensions. Each of these patterns could tell a geological story. And yes, with the appropriate caveats, you really could say the world is made of cubes.
“They did their due diligence in vetting their modeled forms against reality,” said Martha-Cary Eppes, an earth scientist at the University of North Carolina, Charlotte. “My initial skepticism was allayed.”
“The math is telling us that when we begin to fracture rocks, however we do it, whether we do it randomly or deterministically, there is only a certain set of possibilities,” said Furbish. “How clever is that?”
Specifically, perhaps you could take a real fractured field site, count up things like vertices and faces, and then be able to infer something about the geological circumstances responsible.
“We have places where we have data we can think about in this way,” said Roman DiBiase, a geomorphologist at Pennsylvania State University. “That would be a really cool outcome, if you can discern things that are more subtle than the Giant’s Causeway, and hitting a rock with a hammer and seeing what the shards look like.”
As for Jerolmack, after first feeling uncomfortable over a possibly coincidental connection to Plato, he has come to embrace it. After all, the Greek philosopher proposed that ideal geometric forms are central to understanding the universe but always out of sight, visible only as distorted shadows.
“This is literally the most direct example we can think of. The statistical average of all these observations is the cube,” Jerolmack said.
“But the cube never exists.”
This article is originally written by Joshua Sokol and is republished here from quanta magazine under common creative licenses.