Word Metric is Metric

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\left({G, \circ}\right)$ be a group.

Let $S$ be a generating set for $G$ which is closed under inverses (that is, $x^{-1} \in S \iff x\in S$).

Let $d_S$ be the associated word metric.


Then $d_S$ is a metric on $G$.


Proof

Let $g, h \in G$.

It is given that $S$ is a generating set for $G$.

It follows that there exist $s_1, \ldots, s_n \in S$ such that $g^{-1} \circ h = s_1 \circ \cdots \circ s_n$.

Therefore $d_S \left({g, h}\right) \le n$, establishing that $\R$ is a valid codomain for the mapping $d_S$ with domain $G \times G$.

This is the form a mapping must have to be able to be a metric.


Now checking the other defining properties for a metric in turn:


M1

Clearly the empty sequence can be formed with elements from $S$.

It also has length zero.

Therefore, we have for any $g \in G$ that $d_S \left({g, g}\right) = 0$.


M2

Let $g, h, k \in G$.

Let $d_S \left({g, h}\right) = n, d_S \left({h, k}\right) = m$.

Let $s_1, \ldots, s_n, r_1, \ldots, r_m \in S$ be such that:

$g^{-1} \circ h = s_1 \circ \cdots \circ s_n$
$h^{-1} \circ k = r_1 \circ \cdots \circ r_m$

From these equations, obtain:

\(\displaystyle g^{-1} \circ k\) \(=\) \(\displaystyle \left({g^{-1} \circ h}\right) \circ \left({h^{-1} \circ k}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \left({s_1 \circ \cdots \circ s_n}\right) \circ \left({r_1 \circ \cdots \circ r_m}\right)\)
\(\displaystyle \implies \ \ \) \(\displaystyle g \circ s_1 \circ \cdots s_n \circ r_1 \circ \cdots r_n\) \(=\) \(\displaystyle k\)

Therefore, $d_S \left({g, k}\right) \le m +n = d_S \left({g, h}\right) + d_S \left({h, k}\right)$.


M3

Let $g, h \in G$.

Let $d_S \left({g, h}\right) = n$.

Furthermore, let $s_1, \ldots, s_n \in S$ be such that:

$g^{-1} \circ h = s_1 \circ \cdots \circ s_n$

From Inverse of Group Product, obtain:

\(\displaystyle \left({g^{-1} \circ h}\right)^{-1}\) \(=\) \(\displaystyle \left({s_1 \circ \cdots \circ s_n}\right)^{-1}\)
\(\displaystyle h^{-1} \circ g\) \(=\) \(\displaystyle s_n^{-1} \circ \cdots \circ s_1^{-1}\)

By assumption $S$ is closed under taking inverses, and hence the latter expression yields a valid sequence for the metric $d_S$.

It follows that $d_S \left({h, g}\right) \le d_S \left({g, h}\right)$.

Switching the roles of $g$ and $h$ in the above, we obtain the converse inequality, and hence equality.


M4

There is only one word of length zero, namely the empty word.

However, the empty word sends an element $g$ to itself.

Hence $g, h \in G, g \ne h \implies d_S \left({g, h}\right) > 0$.


Thus $d_S$ is a metric.

$\blacksquare$