Word metric

In group theory, a word metric on a discrete group formula_1 is a way to measure distance between any two elements of formula_1. As the name suggests, the word metric is a metric on formula_1, assigning to any two elements formula_4, formula_5 of formula_1 a distance formula_7 that measures how efficiently their difference formula_8 can be expressed as a word whose letters come from a generating set for the group. The word metric on "G" is very closely related to the Cayley graph of "G": the word metric measures the length of the shortest path in the Cayley graph between two elements of "G".
A generating set for formula_9 must first be chosen before a word metric on formula_9 is specified. Different choices of a generating set will typically yield different word metrics. While this seems at first to be a weakness in the concept of the word metric, it can be exploited to prove theorems about geometric properties of groups, as is done in geometric group theory.
Examples.
The group of integers Z.
The group of integers Z is generated by the set {-1,+1}. The integer -3 can be expressed as -1-1-1+1-1, a word of length 5 in these generators. But the word that expresses -3 most efficiently is -1-1-1, a word of length 3. The distance between 0 and -3 in the word metric is therefore equal to 3. More generally, the distance between two integers "m" and "n" in the word metric is equal to |"m"-"n"|, because the shortest word representing the difference "m"-"n" has length equal to |"m"-"n"|.
The group formula_11.
For a more illustrative example, the elements of the group formula_12 can be thought of as vectors in the Cartesian plane with integer coefficients. The group formula_12 is generated by the standard unit vectors formula_14, formula_15 and their inverses formula_16, formula_17. The Cayley graph of formula_12 is the so-called taxicab geometry. It can be pictured in the plane as an infinite square grid of city streets, where each horizontal and vertical line with integer coordinates is a street, and each point of formula_12 lies at the intersection of a horizontal and a vertical street. Each horizontal segment between two vertices represents the generating vector formula_20 or formula_21, depending on whether the segment is travelled in the forward or backward direction, and each vertical segment represents formula_22 or formula_23. A car starting from formula_24 and travelling along the streets to formula_25 can make the trip by many different routes. But no matter what route is taken, the car must travel at least |1 - (-2)| = 3 horizontal blocks and at least |2 - 4| = 2 vertical blocks, for a total trip distance of at least 3 + 2 = 5. If the car goes out of its way the trip may be longer, but the minimal distance travelled by the car, equal in value to the word metric between formula_24 and formula_25 is therefore equal to 5.
In general, given two elements formula_28 and formula_29 of formula_12, the distance between formula_31 and formula_32 in the word metric is equal to formula_33.
Definition.
Let "G" be a group, let "S" be a generating set for "G", and suppose that "S" is closed under the inverse operation on "G". A word over the set "S" is just a finite sequence formula_34 whose entries formula_35 are elements of "S". The integer "L" is called the length of the word formula_36. Using the group operation in "G", the entries of a word formula_34 can be multiplied in order, remembering that the entries are elements of "G". The result of this multiplication is an element formula_38 in the group "G", which is called the evaluation of the word "w". As a special case, the empty word formula_39 has length zero, and its evaluation is the identity element of "G".
Given an element "g" of "G", its word norm |"g"| with respect to the generating set "S" is defined to be the shortest length of a word formula_36 over "S" whose evaluation formula_38 is equal to "g". Given two elements "g","h" in "G", the distance d(g,h) in the word metric with respect to "S" is defined to be formula_42. Equivalently, d("g","h") is the shortest length of a word "w" over "S" such that formula_43.
The word metric on "G" satisfies the axioms for a metric, and it is not hard to prove this. The proof of the symmetry axiom d("g","h") = d("h","g") for a metric uses the assumption that the generating set "S" is closed under inverse.
Variations.
The word metric has an equivalent definition formulated in more geometric terms using the Cayley graph of "G" with respect to the generating set "S". When each edge of the Cayley graph is assigned a metric of length 1, the distance between two group elements "g","h" in "G" is equal to the shortest length of a path in the Cayley graph from the vertex "g" to the vertex "h".
The word metric on "G" can also be defined without assuming that the generating set "S" is closed under inverse. To do this, first symmetrize "S", replacing it by a larger generating set consisting of each formula_44 in "S" as well as its inverse formula_45. Then define the word metric with respect to "S" to be the word metric with respect to the symmetrization of "S".
Example in a free group.
Suppose that "F" is the free group on the two element set formula_46. A word "w" in the symmetric generating set formula_47 is said to be reduced if the letters formula_48 do not occur next to each other in "w", nor do the letters formula_49. Every element formula_50 is represented by a unique reduced word, and this reduced word is the shortest word representing "g". For example, since the word formula_51 is reduced and has length 2, the word norm of formula_36 equals 2, so the distance in the word norm between formula_53 and formula_54 equals 2. This can be visualized in terms of the Cayley graph, where the shortest path between "b" and "a" has length 2.
Theorems.
Isometry of the left action.
The group "G" acts on itself by left multiplication: the action of each formula_55 takes each formula_56 to formula_57. This action is an isometry of the word metric. The proof is simple: the distance between formula_57 and formula_59 equals formula_60, which equals the distance between formula_61 and formula_62.
Bilipschitz invariants of a group.
The word metric on a group "G" is not unique, because different symmetric generating sets give different word metrics. However, finitely generated word metrics are unique up to bilipschitz equivalence: if formula_63, formula_64 are two symmetric, finite generating sets for "G" with corresponding word metrics formula_65, formula_66, then there is a constant formula_67 such that for any formula_68, 
This constant "K" is just the maximum of the formula_65 word norms of elements of formula_64 and the formula_66 word norms of elements of formula_63. This proof is also easy: any word over "S" can be converted by substitution into a word over "T", expanding the length of the word by a factor of at most "K", and similarly for converting words over "T" into words over "S".
The bilipschitz equivalence of word metrics implies in turn that the growth rate of a finitely generated group is a well-defined isomorphism invariant of the group, independent of the choice of a finite generating set. This implies in turn that various properties of growth, such as polynomial growth, the degree of polynomial growth, and exponential growth, are isomorphism invariants of groups. This topic is discussed further in the article on the growth rate of a group.
Quasi-isometry invariants of a group.
In geometric group theory, groups are studied by their actions on metric spaces. A principle that generalizes the bilipschitz invariance of word metrics says that any finitely generated word metric on "G" is quasi-isometric to any proper, geodesic metric space on which "G" acts, properly discontinuously and cocompactly. Metric spaces on which "G" acts in this manner are called model spaces for "G".
It follows in turn that any quasi-isometrically invariant property satisfied by the word metric of "G" or by any model space of "G" is an isomorphism invariant of "G". Modern geometric group theory is in large part the study of quasi-isometry invariants.