RUI: Randomness, Computability, and Complexity in Groups

群是代数中的一类基本对象，更一般地说，是数学中的一类基本对象。它们起源于数学和自然中描述对称性的一种方式。事实证明，几乎所有的代数数学结构都可以被认为是一个具有某种额外结构的群。最近，群论也在密码学中得到了应用。其他领域的许多工具，如组合数学和几何学，在研究群时已经证明是有用的。此外，群论与逻辑的相互作用有着悠久的历史。在逻辑的早期发展中，群论是逻辑思想的重要试验场。另一方面，人们逐渐清楚地认识到，逻辑学中的许多思想在群体研究中也是有用的。这个项目旨在探索这种联系，并应用逻辑工具来促进我们对各种重要类别的群体的理解。本计画也提供机会与支援给加州州立大学北岭分校的学生从事逻辑与群论的研究，本计画的目的是了解群的模型论、可计算性与复杂性的性质，并利用此了解在有限生成群的分类上取得进展。该项目包括三个主要部分。第一部分分析了随机群的模型论性质，特别是Gromov随机群模型中一阶句子的0-1猜想。主要工具是由Sela开发的理论，以及由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.