We’ve come to think of computers as remarkable tools of calculation which have contributed to major scientific advances, like helping astronauts reach the moon or determining more than 31 trillion digits of Pi. But computers are not infallible; there are some functions that are simply not “computable.” This perplexing aspect of mathematics is the topic of a new grant for University of Connecticut assistant professor of mathematics, Damir Dzhafarov.
Dzhafarov has received $379,450 from the National Science Foundation’s (NSF) Division of Mathematical Sciences to study and strengthen the connections between two prominent branches of theoretical mathematics: computability theory and combinatorics.
The grant Dzhafarov has received is a Focused Research Group (FRG) grant. These grants support collaborative groups that work to solve specific, major research challenges in the field of mathematics.
The NSF website defines a major research challenge as: “an outstanding problem of significant importance that requires the focused and synergistic efforts of a collaborative group to solve, and whose solution will have wide impacts in the mathematical sciences and potentially in other areas.” These grants are relatively rare and the competition is steep; there are only 34 current separate FRG projects.
Dzhafarov’s grant is part of a multi-institutional project that involves researchers from UC Berkeley, University of Chicago, Notre Dame, and Penn State.
The first focus of Dzhafarov’s part of the project is computability theory. This branch of mathematics is concerned with determining what it means for a function of natural numbers (the numbers we use for everyday counting) to be calculable by a computer using an algorithm. Something as simple as addition or multiplication represents a computable function. This gives rise to the idea that some mathematical problems (as opposed to functions) can be solved by a computer, while others cannot. Researchers like Dzhafarov are interested in the question of which are which.
Combinatorics deals with different ways we can count objects and make combinations or orderings. So, for example, how many ways you could match three shirts with four pairs of pants, or arrange six plants along a windowsill, or color a map so that no two countries that share a border get the same color. The operations at the core of combinatorics underlie a great deal of basic mathematical reasoning making it a prudent lens through which can consider the computability-theoretic approach.
There has been a recent surge in computability-theoretic research within combinatorics since the discovery that combinatorial notions tend to be computationally natural, meaning they can easily be combined into smaller, more manageable units that can be better approximated by a computer.
Dzhafarov’s project aims to strengthen the connections between these two fields by increasing the mathematical community’s understanding of the algorithmic content—the core of the computability-theoretic approach—of combinatorial principles.
“Through a concerted group effort to use what we have learned in recent years, we hope to systematize the area further, work toward solving a number of its outstanding questions, and explore its outward-facing aspects,” Dzhafarov says.
One of the key tasks the research team will tackle is the development of new tools for increasing the connections between these two fields. The team will address questions of methodology, exactly how mathematicians can use the insights of one branch to better understand the other.
“We can use these tools to compare the difficulty of different problems in math, which can in turn help us better understand these problems and their applications,” says Dzhafarov. A central example is Ramsey’s Theorem, which is a far-reaching result in combinatorics that says that in any configuration of objects, however chaotic it may seem, some amount of order can always be found. One of the grant’s main objectives is to understand this order better, and how it arises.
“This project is aimed at developing the study of the connections between computability theory and combinatorics along a large number of related directions, making use of the expertise of its PIs, senior personnel, and key collaborators,” Dzhafarov says.
Dzhafarov received his Ph.D. in mathematics from the University of Chicago in 2011. Dzhafarov is the associate director for the UConn Logic Group and a director of the Graduate Certificate Program in Logic at UConn. He is also an affiliate member of the Connecticut Institute for the Brain and Cognitive Sciences.
Dzhafarov’s research focuses on mathematical logic in computability theory, reverse mathematics, effective combinatorics, and computable analysis. He is also interested in the philosophy of mathematics and the application of logic to cognitive science.
This project is NSF Grant No.: 1854355.
