Namespaces
Variants
Actions

Difference between revisions of "Word metric"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
w1101201.png
 +
$#A+1 = 47 n = 0
 +
$#C+1 = 47 : ~/encyclopedia/old_files/data/W110/W.1100120 Word metric,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''length metric''
 
''length metric''
  
A [[Metric|metric]] on a [[Finitely-generated group|finitely-generated group]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w1101201.png" />, defined as follows. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w1101202.png" /> be a finite set of generators for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w1101203.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w1101204.png" /> be the set of inverses of elements in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w1101205.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w1101206.png" /> is not the identity element, then the length of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w1101207.png" /> is defined as the minimal number of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w1101208.png" />, counted with multiplicity, such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w1101209.png" /> can be written as a product of these elements. The length of the identity element is defined to be zero. The word metric <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012010.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012011.png" /> with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012012.png" /> is then defined by the following formula: for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012013.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012014.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012016.png" /> is equal to the length of the product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012017.png" />. The action of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012018.png" /> by left translations on the metric space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012019.png" /> is an action by isometries. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012020.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012021.png" /> are two finite generating sets for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012022.png" />, then the identity mapping between the metric spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012024.png" /> is a [[Quasi-isometry|quasi-isometry]].
+
A [[Metric|metric]] on a [[Finitely-generated group|finitely-generated group]] $  G $,  
 +
defined as follows. Let $  A $
 +
be a finite set of generators for $  G $.  
 +
Let $  A ^ {- 1 } $
 +
be the set of inverses of elements in $  A $.  
 +
If $  \gamma \in G $
 +
is not the identity element, then the length of $  \gamma $
 +
is defined as the minimal number of elements of $  A \cup A ^ {- 1 } $,  
 +
counted with multiplicity, such that $  \gamma $
 +
can be written as a product of these elements. The length of the identity element is defined to be zero. The word metric $  d _ {A} $
 +
on $  G $
 +
with respect to $  A $
 +
is then defined by the following formula: for all $  \gamma $
 +
and $  \gamma  ^  \prime  $
 +
in $  G $,
 +
$  d _ {A} ( \gamma, \gamma  ^  \prime  ) $
 +
is equal to the length of the product $  \gamma ^ {\prime - 1 } \gamma $.  
 +
The action of $  G $
 +
by left translations on the metric space $  ( G,d _ {A} ) $
 +
is an action by isometries. If $  A $
 +
and $  B $
 +
are two finite generating sets for $  G $,  
 +
then the identity mapping between the metric spaces $  ( G,d _ {A} ) $
 +
and $  ( G,d _ {B} ) $
 +
is a [[Quasi-isometry|quasi-isometry]].
  
An equivalent definition is the following: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012025.png" /> is the maximal metric on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012026.png" /> that is invariant by the left-action of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012027.png" /> on itself, and such that the distance of any element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012028.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012029.png" /> to the identity element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012030.png" /> is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012031.png" />.
+
An equivalent definition is the following: $  d _ {A} $
 +
is the maximal metric on $  G $
 +
that is invariant by the left-action of $  G $
 +
on itself, and such that the distance of any element of $  A $
 +
or $  A ^ {- 1 } $
 +
to the identity element of $  G $
 +
is equal to $  1 $.
  
The notion of word metric lies at the foundation of geometric group theory. A group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012032.png" /> (equipped with a finite generating set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012033.png" />) can be canonically imbedded, as the set of vertices, in the associated Cayley graph, which is a simplicial graph. This graph has a canonical metric, and the metric induced on the vertices is the word metric.
+
The notion of word metric lies at the foundation of geometric group theory. A group $  G $(
 +
equipped with a finite generating set $  A $)  
 +
can be canonically imbedded, as the set of vertices, in the associated Cayley graph, which is a simplicial graph. This graph has a canonical metric, and the metric induced on the vertices is the word metric.
  
 
The word metric on a group has much to do with the growth function of a finitely-generated group (cf. also [[Polynomial and exponential growth in groups and algebras|Polynomial and exponential growth in groups and algebras]]; [[#References|[a1]]], [[#References|[a2]]]; see also [[#References|[a3]]], especially Sect. 37, for other and related techniques in the study of groups).
 
The word metric on a group has much to do with the growth function of a finitely-generated group (cf. also [[Polynomial and exponential growth in groups and algebras|Polynomial and exponential growth in groups and algebras]]; [[#References|[a1]]], [[#References|[a2]]]; see also [[#References|[a3]]], especially Sect. 37, for other and related techniques in the study of groups).
Line 11: Line 55:
 
Using the word metric (or the length of words), one defines
 
Using the word metric (or the length of words), one defines
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012034.png" /></td> </tr></table>
+
$$
 +
( x \cdot y ) = {
 +
\frac{1}{2}
 +
} ( \left | x \right | + \left | y \right | - \left | {x ^ {- 1 } y } \right | ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012035.png" /> is the length of the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012036.png" />.
+
where $  | x | $
 +
is the length of the element $  x \in G $.
  
A group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012037.png" /> is hyperbolic (cf. also [[Hyperbolic group|Hyperbolic group]]) if there is a constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012038.png" /> such that for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012039.png" />,
+
A group $  G $
 +
is hyperbolic (cf. also [[Hyperbolic group|Hyperbolic group]]) if there is a constant $  \delta \geq  0 $
 +
such that for all $  x,y,z \in G $,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012040.png" /></td> </tr></table>
+
$$
 +
( x \cdot y ) \geq  \min  \{ ( x \cdot z ) , ( y \cdot z ) \} - \delta
 +
$$
  
(cf. also [[#References|[a1]]], [[#References|[a4]]]). Hyperbolic groups are always finitely presented (cf. also [[Finitely-presented group|Finitely-presented group]]), and as such realizable as the [[Fundamental group|fundamental group]] of a smooth bounded region <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012041.png" />. Hyperbolicity is then equivalent to the purely geometric property that there is a constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012042.png" /> such that for every smooth closed curve <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012043.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012044.png" />, contractible in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012045.png" /> and bounding a disc <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012046.png" />, one has
+
(cf. also [[#References|[a1]]], [[#References|[a4]]]). Hyperbolic groups are always finitely presented (cf. also [[Finitely-presented group|Finitely-presented group]]), and as such realizable as the [[Fundamental group|fundamental group]] of a smooth bounded region $  M $.  
 +
Hyperbolicity is then equivalent to the purely geometric property that there is a constant $  c $
 +
such that for every smooth closed curve $  C $
 +
in $  M $,  
 +
contractible in $  M $
 +
and bounding a disc $  D $,  
 +
one has
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110120/w11012047.png" /></td> </tr></table>
+
$$
 +
{ \mathop{\rm area} } ( D ) \leq  c { \mathop{\rm length} } ( C ) .
 +
$$
  
 
This gives (further) geometric methods for studying hyperbolic groups.
 
This gives (further) geometric methods for studying hyperbolic groups.

Latest revision as of 08:29, 6 June 2020


length metric

A metric on a finitely-generated group $ G $, defined as follows. Let $ A $ be a finite set of generators for $ G $. Let $ A ^ {- 1 } $ be the set of inverses of elements in $ A $. If $ \gamma \in G $ is not the identity element, then the length of $ \gamma $ is defined as the minimal number of elements of $ A \cup A ^ {- 1 } $, counted with multiplicity, such that $ \gamma $ can be written as a product of these elements. The length of the identity element is defined to be zero. The word metric $ d _ {A} $ on $ G $ with respect to $ A $ is then defined by the following formula: for all $ \gamma $ and $ \gamma ^ \prime $ in $ G $, $ d _ {A} ( \gamma, \gamma ^ \prime ) $ is equal to the length of the product $ \gamma ^ {\prime - 1 } \gamma $. The action of $ G $ by left translations on the metric space $ ( G,d _ {A} ) $ is an action by isometries. If $ A $ and $ B $ are two finite generating sets for $ G $, then the identity mapping between the metric spaces $ ( G,d _ {A} ) $ and $ ( G,d _ {B} ) $ is a quasi-isometry.

An equivalent definition is the following: $ d _ {A} $ is the maximal metric on $ G $ that is invariant by the left-action of $ G $ on itself, and such that the distance of any element of $ A $ or $ A ^ {- 1 } $ to the identity element of $ G $ is equal to $ 1 $.

The notion of word metric lies at the foundation of geometric group theory. A group $ G $( equipped with a finite generating set $ A $) can be canonically imbedded, as the set of vertices, in the associated Cayley graph, which is a simplicial graph. This graph has a canonical metric, and the metric induced on the vertices is the word metric.

The word metric on a group has much to do with the growth function of a finitely-generated group (cf. also Polynomial and exponential growth in groups and algebras; [a1], [a2]; see also [a3], especially Sect. 37, for other and related techniques in the study of groups).

Using the word metric (or the length of words), one defines

$$ ( x \cdot y ) = { \frac{1}{2} } ( \left | x \right | + \left | y \right | - \left | {x ^ {- 1 } y } \right | ) , $$

where $ | x | $ is the length of the element $ x \in G $.

A group $ G $ is hyperbolic (cf. also Hyperbolic group) if there is a constant $ \delta \geq 0 $ such that for all $ x,y,z \in G $,

$$ ( x \cdot y ) \geq \min \{ ( x \cdot z ) , ( y \cdot z ) \} - \delta $$

(cf. also [a1], [a4]). Hyperbolic groups are always finitely presented (cf. also Finitely-presented group), and as such realizable as the fundamental group of a smooth bounded region $ M $. Hyperbolicity is then equivalent to the purely geometric property that there is a constant $ c $ such that for every smooth closed curve $ C $ in $ M $, contractible in $ M $ and bounding a disc $ D $, one has

$$ { \mathop{\rm area} } ( D ) \leq c { \mathop{\rm length} } ( C ) . $$

This gives (further) geometric methods for studying hyperbolic groups.

References

[a1] V.A. Ufnarovskii, "Combinatorial and asymptotic methods in algebra" A.I. Kostrikin (ed.) I.R. Shafarevich (ed.) , Algebra , VI , Springer (1995) (In Russian)
[a2] R. Grigorchuk, T. Nagnibeda, "Operator growth functions of discrete groups" Invent. Math. (to appear)
[a3] A.Yu. Ol'shanskii, "Geometry of defining relations in groups" , Kluwer Acad. Publ. (1991) (In Russian)
[a4] M. Gromov, "Hyperboloic groups" , Essays in Group Theory , Springer (1987) pp. 75–263
How to Cite This Entry:
Word metric. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Word_metric&oldid=18555
This article was adapted from an original article by A. Papadopoulos (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article