RUI: Randomness, Computability, and Complexity in Groups

群是代数中的一类基本对象，更广泛地说，是数学中的对象。它们起源于描述数学和自然中的对称性的一种方式。结果表明，几乎所有的代数数学结构都可以被认为是一个具有某种额外结构的群。最近，群论也在密码学中找到了用途。来自其他领域的许多工具，如组合学和几何学，已被证明在群的研究中很有用。此外，群论与逻辑互动的历史由来已久。在逻辑学的早期发展中，群论是逻辑思想的重要试验场。另一方面，人们逐渐清楚地认识到，逻辑中的许多观点在群体研究中也是有用的。这个项目旨在探索这种联系，并应用逻辑学中的工具来促进我们对各种重要类别群体的理解。该项目还为加州州立大学北岭分校的学生提供了从事逻辑和群论研究的机会和支持。本项目旨在了解群的模型理论、可计算性和复杂性属性，并利用这种理解在有限生成群的分类方面取得进展。该项目包括三个主要部分。第一部分分析了随机群的模型论性质，特别是Gromov的随机群模型中一阶句的0-1猜想。主要工具是塞拉发展的理论，并由Kharlampovich和Myasnikov独立提出，他们用来解决70岁的Tarski问题。第二部分旨在理解描述群的元素和乘法的复杂性。这包括使用形式语言理论的框架来分析词语问题和群体的代表系统。第三部分建立在研究者先前工作的基础上，旨在理解群的描述性复杂性，以及它们如何与有限生成群的各种重要类别相联系。更广泛地说，这部分的目的是在可计算性理论的背景下，理解群类的复杂性和它们之间的关系，特别是同构。总体而言，该项目有利于学生的研究，因为它包含了许多具体的和实验的例子，并将为加州州立大学北岭分校的不同学生提供培训和研究经验。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.