The geometry, topology and asymptotics of the word problem

文字问题的几何、拓扑和渐进

• 批准号: 0404767
• 负责人: Timothy Riley
• 金额: $ 3.55万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-08-01 至 2005-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0404767&HistoricalAwards=false
• 关键词: geometry; topology; asymptotics; word; problem

The proposed research is in Geometric Group Theory, specifically on problems pertaining to the geometry, topology and asymptotics of the word problem, particularly along avenues initiated by Gromov in his seminal book "Asymptotic Invariants of Infinite Groups." A first direction concerns isoperimetric and filling length functions, a meeting point of geometry and algorithmic complexity. Examples of problems for attack here are whether Cohen's Double Exponential Theorem is sharp, and to establish long standing claims of Thurston about isoperimetric functions of the Special Linear Groups. Also addressed in the proposal is a question of Gromov about the uniqueness of a limit of a group viewed from increasingly distant vantage points (an asymptotic cone); a line of attack is being pursued in collaboration with M.R. Bridson. Another area is the "grammar of the Word Problem", where geometry meets linguistic complexity. The P.I. proposes to investigate the combings of nilpotent groups as well as applications to the Andrews-Curtis Conjecture. The proposal includes collaborative work and it is anticipated that the inter-disciplinary nature of the work will enable additional collaborative efforts both in the United States and abroad.The Word Problem was posed by Max Dehn in 1912, who presciently described it as a "fundamental problem whose solution is very difficult and which will not be possible without a penetrating study of the subject." The Word Problem for a group (a fundamental algebraic object capturing symmetries) asks for a systematic method (in modern terms, an algorithm) which, given a finite list (a "word") of basic symmetries (distinguished group elements known as "generators"), declares whether or not their product is the identity (the trivial symmetry that moves nothing). One of the crowning achievements of 20th century mathematics was the construction by Boone and Novikov of groups for which no such algorithm can exist. However, that is by no means the end of the story. The Word Problem transcends its origins in algebra, decidability and complexity theory, and turns out to be a bridge to geometry and topology, as well as to linguistic complexity. To a group we can associate a topological space and vice versa. Recognising a word to be trivial amounts to spanning a loop with a disc in a corresponding space, and geometrical features of this disc (such as area) translate to algorithmic complexity measures (such as time) of the Word Problem. Moreover, words over a group form grammars whose linguistic features relate to the ease of navigating around the corresponding space. Thus there are tantalising links between minimal surfaces (soap films) and algorithmic complexity, and between geometry of spaces and grammars. These are the connections the P.I. proposes to develop and exploit.

拟议的研究是在几何群论，特别是有关的问题，几何，拓扑和渐近的字问题，特别是沿着途径发起的格罗莫夫在他的开创性著作"渐近不变量的无限群。第一个方向涉及等周函数和填充长度函数，这是几何和算法复杂性的交汇点。 例如，问题的攻击在这里是科恩的双指数定理是否尖锐，并建立长期索赔瑟斯顿等周函数的特殊线性群。 在提案中还提出了格罗莫夫的一个问题，即从越来越远的有利位置（渐近锥）观察一个群的极限的唯一性;正在与M.R.布莱森 另一个领域是“语法的文字问题”，几何满足语言的复杂性。 私家侦探提出研究幂零群的组合以及Andrews-Curtis猜想的应用。 该提案包括合作工作，预计这项工作的跨学科性质将使美国和国外的额外合作努力成为可能。单词问题由马克斯·德恩于1912年提出，他有先见之明地将其描述为"一个非常困难的基本问题，如果不深入研究这个问题，就不可能解决。群的字问题（一个基本的代数对象捕获对称性）要求一种系统的方法（在现代术语中，一种算法），给定一个有限的基本对称性列表（一个“字”）（被称为“生成元”的特殊群元素），声明它们的乘积是否是恒等式（不移动任何东西的平凡对称性）。 其中最辉煌的成就，20世纪数学是建设布恩和诺维科夫的群体，没有这样的算法可以存在。 然而，这绝不是故事的结局。 文字问题超越了它在代数、可判定性和复杂性理论中的起源，成为通向几何、拓扑和语言复杂性的桥梁。 我们可以把拓扑空间与群联系起来，反之亦然。 识别一个单词是微不足道的，相当于在相应的空间中用一个圆盘跨越一个循环，这个圆盘的几何特征（如面积）转化为单词问题的算法复杂性度量（如时间）。 此外，一组词形成语法，其语言特征与在相应空间中导航的容易程度有关。 因此，在最小曲面（肥皂剧）和算法复杂性之间，以及空间几何和语法之间，存在着诱人的联系。 这些是私家侦探.建议开发和利用。