Asymptotic and Algorithmic Invariants of Groups

群的渐近和算法不变量

• 批准号: 0072307
• 负责人: Alexander Olshanskiy
• 金额: $ 11.8万
• 依托单位: Vanderbilt University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-07-15 至 2003-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0072307&HistoricalAwards=false
• 关键词: Asymptotic; Algorithmic; Invariants; Groups

The investigators study asymptotic and algorithmic properties of groups. The area of research includes Dehn functions and relative Dehn functions of groups, the complexity of algorithmic problems of groups, Burnside problems for groups. Many papers published during the last forty years showed deep connection between asymptotic invariants of groups and topology, geometry, amenability, dynamical systems, etc. Quiterecently, the proposers (jointly with Rips and Birget) discovered a closerelationship between the asymptotics of isoperimetric functions, on the onehand, and the complexity of the word problem for groups, on the other hand.The investigators are developing their method, combining geometric andcomputational approaches. One of their goals is to obtain the solutionof other algorithmic problems using geometric group theory. In particularthe investigators believe they will be able to prove that every recursively presentedfinitely generated group can be embedded into a finitely presented groupwith the same degree of unsolvability of the conjugacy problem. This wouldsolve a problem formulated by Collins in 1976.The computational-geometric methods of the investigators also show promise of being able to be fruitfully applied to the Burnside-type problems.The investigators are close to constructing non-amenable finitely presentedgroups having no non-cyclic free subgroups. This will solve thecorresponding well-known problem which goes back to von Neumann's 1929paper. Since the group in question is a finitely presented extension of atorsion group of finite exponent by a cyclic group, this example will bea breakthrough in the search for a finitely presented torsiongroup (one of the main open problem in the theory of infinite groups). It is a well known point of view after Klein, Hilbert, Einstein and Weilthat fundamental laws describe symmetries occurring in the nature. Thesymmetry of an object can be measured by the group corresponding to theobject. Groups can be defined as groups of symmetries or abstractly by analgorithmic description (generators and relations). In the second approach,the investigators choose some basic symmetries (generators) so that all other symmetriesare compositions (words) of the basic symmetries, and describe certainrelations between the basic symmetries such that all other relations followfrom the chosen relations. One of the main problems about a group given bygenerators and relations and relations is the word problem: when are twocompositions of generators the same? In some exotic cases this problem canbe undecidable, that is there are groups for which there are no automaticprocedures to recognize if two words of generators are equal. but evenin cases when this problem is decidable, the automatic procedure can be verycomplicated. In recent years the investigators discovered a deeprelationship between the word problem of a group and the global geometry ofthe group. The geometry of a group is described in terms of certainasymptotic invariants. The invariants have been known since the pioneeringworks of M. Dehn at the beginning of the 20th century but the investigatorsdiscovered deep relationship between these invariants and algorithmicproblems. The investigators are developing their geometric method solvingold mathematical problems of algorithmic nature and corresponding algebraic problems about groups.

研究人员研究群的渐近特性和算法特性。研究领域包括群的Dehn函数和相关Dehn函数、群算法问题的复杂性、群的Burnside问题。 过去四十年发表的许多论文表明，群的渐近不变量与拓扑、几何、顺应性、动力系统等之间存在着深刻的联系。最近，提议者（与 Rips 和 Birget 一起）发现，一方面，等周函数的渐进性与群问题的复杂性之间存在密切关系。研究人员正在开发他们的方法，结合 几何和计算方法。他们的目标之一是使用几何群论获得其他算法问题的解决方案。特别是，研究人员相信他们将能够证明每个递归呈现的有限生成群都可以嵌入到具有相同程度的共轭问题不可解性的有限呈现群中。这将解决柯林斯在 1976 年提出的一个问题。研究人员的计算几何方法也显示出能够有效地应用于 Burnside 型问题的希望。研究人员即将构造出不具有非循环自由子群的非服从有限呈现群。这将解决相应的众所周知的问题，该问题可以追溯到冯·诺依曼 1929 年的论文。由于所讨论的群是循环群对有限指数扭转群的有限呈现扩展，因此这个例子将成为寻找有限呈现扭转群（无限群理论中主要开放问题之一）的突破。 继克莱因、希尔伯特、爱因斯坦和韦尔之后，众所周知的观点是基本定律描述了自然界中发生的对称性。物体的对称性可以通过该物体对应的群来测量。群可以被定义为对称群或通过算法描述（生成元和关系）抽象地定义。在第二种方法中，研究人员选择一些基本对称性（生成器），以便所有其他对称性都是基本对称性的组合（词），并描述基本对称性之间的某些关系，以便所有其他关系都遵循所选关系。关于由生成元、关系和关系给出的群的主要问题之一是文字问题：生成元的两个组成何时相同？ 在某些特殊情况下，这个问题可能是不可判定的，即存在一些组，没有自动程序来识别生成器的两个单词是否相等。但即使在这个问题是可判定的情况下，自动过程也可能非常复杂。 近年来，研究人员发现群的文字问题与群的整体几何形状之间存在着深刻的关系。群的几何形状是用某些渐近不变量来描述的。自 20 世纪初 M. Dehn 的开创性工作以来，这些不变量就为人所知，但研究人员发现了这些不变量与算法问题之间的深层关系。研究人员正在开发几何方法来解决算法性质的古老数学问题以及相应的群代数问题。