Definition:Word Metric

From ProofWiki
Jump to navigation Jump to search


Let $\struct {G, \circ}$ 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$).

The word metric on $G$ with respect to $S$ is the metric $d_S$ defined as follows:

For any $g, h \in G$, let $\map {d_S} {g, h}$ be the minimum length among the finite sequences $\tuple {x_1, \dots, x_n}$ with each $x_i \in S$ such that $g \circ x_1 \circ \cdots \circ x_n = h$.

Informally, $\map {d_S} {g, h}$ is the smallest number of elements from $S$ that one needs to multiply by to get from $g$ to $h$.

Also see

  • Results about the word metric can be found here.