Loading AI tools
Group theory function From Wikipedia, the free encyclopedia
In the mathematical subject of geometric group theory, a Dehn function, named after Max Dehn, is an optimal function associated to a finite group presentation which bounds the area of a relation in that group (that is a freely reduced word in the generators representing the identity element of the group) in terms of the length of that relation (see pp. 79–80 in [1]). The growth type of the Dehn function is a quasi-isometry invariant of a finitely presented group. The Dehn function of a finitely presented group is also closely connected with non-deterministic algorithmic complexity of the word problem in groups. In particular, a finitely presented group has solvable word problem if and only if the Dehn function for a finite presentation of this group is recursive (see Theorem 2.1 in [1]). The notion of a Dehn function is motivated by isoperimetric problems in geometry, such as the classic isoperimetric inequality for the Euclidean plane and, more generally, the notion of a filling area function that estimates the area of a minimal surface in a Riemannian manifold in terms of the length of the boundary curve of that surface.
The idea of an isoperimetric function for a finitely presented group goes back to the work of Max Dehn in 1910s. Dehn proved that the word problem for the standard presentation of the fundamental group of a closed oriented surface of genus at least two is solvable by what is now called Dehn's algorithm. A direct consequence of this fact is that for this presentation the Dehn function satisfies Dehn(n) ≤ n. This result was extended in 1960s by Martin Greendlinger to finitely presented groups satisfying the C'(1/6) small cancellation condition.[2] The formal notion of an isoperimetric function and a Dehn function as it is used today appeared in late 1980s – early 1990s together with the introduction and development of the theory of word-hyperbolic groups. In his 1987 monograph "Hyperbolic groups"[3] Gromov proved that a finitely presented group is word-hyperbolic if and only if it satisfies a linear isoperimetric inequality, that is, if and only if the Dehn function of this group is equivalent to the function f(n) = n. Gromov's proof was in large part informed by analogy with filling area functions for compact Riemannian manifolds where the area of a minimal surface bounding a null-homotopic closed curve is bounded in terms of the length of that curve.
The study of isoperimetric and Dehn functions quickly developed into a separate major theme in geometric group theory, especially since the growth types of these functions are natural quasi-isometry invariants of finitely presented groups. One of the major results in the subject was obtained by Sapir, Birget and Rips who showed[4] that most "reasonable" time complexity functions of Turing machines can be realized, up to natural equivalence, as Dehn functions of finitely presented groups.
Let
be a finite group presentation where the X is a finite alphabet and where R ⊆ F(X) is a finite set of cyclically reduced words.
Let w ∈ F(X) be a relation in G, that is, a freely reduced word such that w = 1 in G. Note that this is equivalent to saying that w belongs to the normal closure of R in F(X), that is, there exists a representation of w as
where m ≥ 0 and where ri ∈ R± 1 for i = 1, ..., m.
For w ∈ F(X) satisfying w = 1 in G, the area of w with respect to (∗), denoted Area(w), is the smallest m ≥ 0 such that there exists a representation (♠) for w as the product in F(X) of m conjugates of elements of R± 1.
A freely reduced word w ∈ F(X) satisfies w = 1 in G if and only if the loop labeled by w in the presentation complex for G corresponding to (∗) is null-homotopic. This fact can be used to show that Area(w) is the smallest number of 2-cells in a van Kampen diagram over (∗) with boundary cycle labelled by w.
An isoperimetric function for a finite presentation (∗) is a monotone non-decreasing function
such that whenever w ∈ F(X) is a freely reduced word satisfying w = 1 in G, then
where |w| is the length of the word w.
Then the Dehn function of a finite presentation (∗) is defined as
Equivalently, Dehn(n) is the smallest isoperimetric function for (∗), that is, Dehn(n) is an isoperimetric function for (∗) and for any other isoperimetric function f(n) we have
for every n ≥ 0.
Because the exact Dehn function usually depends on the presentation, one usually studies its asymptotic growth type as n tends to infinity, which only depends on the group.
For two monotone-nondecreasing functions
one says that f is dominated by g if there exists C ≥1 such that
for every integer n ≥ 0. Say that f ≈ g if f is dominated by g and g is dominated by f. Then ≈ is an equivalence relation and Dehn functions and isoperimetric functions are usually studied up to this equivalence relation. Thus for any a,b > 1 we have an ≈ bn. Similarly, if f(n) is a polynomial of degree d (where d ≥ 1 is a real number) with non-negative coefficients, then f(n) ≈ nd. Also, 1 ≈ n.
If a finite group presentation admits an isoperimetric function f(n) that is equivalent to a linear (respectively, quadratic, cubic, polynomial, exponential, etc.) function in n, the presentation is said to satisfy a linear (respectively, quadratic, cubic, polynomial, exponential, etc.) isoperimetric inequality.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.