RUI: Randomness, Computability, and Complexity in Groups

Groups are a class of fundamental objects in algebra, and more generally, mathematics. They originated as a way to describe symmetries in both mathematics and nature. It turns out that almost all algebraic mathematical structures can be considered as a group with some extra structure.

More recently, group theory has also found uses in cryptography. Many tools from other fields, like combinatorics and geometry, have proven useful in the study of groups. Furthermore, group theory has a long history of interaction with logic.

In the early developments of logic, group theory was an important testing ground for ideas in logic. On the other hand, it became gradually clear that many ideas from logic were also useful in the study of groups. This project aims to explore this connection and applies tools from logic to advance our understanding of various important classes of groups.

This project also provides opportunities and support for students at California State University, Northridge to engage in research in logic and group theory.

This project aims to understand the model-theoretic, computability, and complexity properties of groups, and use this understanding to make progress in classifying the finitely-generated groups. The project contains three main parts. The first part aims to analyze the model-theoretic properties of random groups, especially the 0-1 conjecture of first-order sentences in Gromov's random group model.

The main tool is the theory developed by Sela, and independently by Kharlampovich and Myasnikov, which they used to solve the 70-year-old Tarski's problem. The second part aims to understand the complexity of describing the elements and multiplication of groups. This includes analyzing the word problem and representative systems of groups using the framework of formal language theory.

The third part builds on previous work of the investigator and aims to understand the descriptive complexity of groups, and how they connect to various important classes of finitely-generated groups. More broadly, this part aims to understand the complexity of classes of groups and the relations on them, especially isomorphism, within the context of computability theory.

Overall, the project is conducive for student research as it contains many concrete and experimental examples, and will provide training and research experience for the diverse students at California State University, Northridge.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.