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.”
Provided by Stevens Institute of Technology