3
$\begingroup$

Given a word $w \in X^{\pm 1}$ representing an element of the free group $F(X)$ there is a (usually non-unique) sequence $w=w_0 \to w_1 \to \cdots \to w_r$ with $|w_i|>|w_{i+1}|$ where $w_r$ is the unique reduced form of $w$, i.e. there are no subwords of the form $xx^{-1}, x \in X^{\pm 1}$. I know of this fact, even have a proof of it in some notes I wrote. Does anybody know a reference for this?

Similarly let $\mathbb X$ be a graph of groups and let $w$ be some word in some symbols representing an element of the fundamental group $\pi_1(\mathbb X,v)$. Britton's lemma famously, and conveniently, describes what normal forms are in the case of HNN extensions. Does anybody know of a reference for the fact that given $w$ as above, there is a sequence $w=w_0 \to w_1 \to \cdots \to w_r$ of decreasing syllable length such that $w_r$ is reduced (i.e. has minimal syllable length among all words representing the same group element)?

Again, I can prove this myself, but a reference would be convenient.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ For your first reference, Magnus, Karrass and Solitary (or the paper of Kapovich and Myasnikov where they re-do Stallings foldings in precise detail). $\endgroup$
    – user1729
    Mar 21 at 20:01
  • 1
    $\begingroup$ Probably Bass's "Covering Theory for Graphs of Groups"? $\endgroup$
    – Rylee Lyman
    Mar 21 at 21:03
  • 3
    $\begingroup$ I don't think you need a reference that you can get to some reduced word since length is going down. Any text on complete rewriting systems will show the free group presentation is confluent and so the word is unique. You can just use Newman's lemma or the diamond lemma. To make the HNN presentation into a complete rewriting system you need to make some choices to get uniqueness. For example the free abelian group <a,t|tat^{-1}=a> you don't get to a unique minimum syllable length word. To get uniqueness you make a choice to do ta->at and similarly for inverses to get unique forms $\endgroup$
    – Benjamin Steinberg
    Mar 21 at 21:08
  • 2
    $\begingroup$ Like @BenjaminSteinberg all of this is exceedingly standard and appears in any textbook. If you want the first references, I suppose von Dyck (1889) proved the first part; and why not just use Britton’s own 1958 paper on the undecidability of the word problem for groups, where he proves his eponymous lemma for normal forms (Lemma 4)? Note that Novikov also independently proved this lemma in his 1958 paper on the word problem, but without the terminology of HNN-extensions. $\endgroup$
    – Carl-Fredrik Nyberg Brodda
    Mar 21 at 22:13
  • 2
    $\begingroup$ @NWMT: Nielsen transformations aren't relevant here: they're for finding a shortest representative in an automorphism orbit, which is a much more difficult problem. (And the answer is to use Whitehead automorphisms, under which lengths always do go down.) Anyway, I'll add an answer that addresses uniqueness. But I think you know everything it says! $\endgroup$
    – HJRW
    Mar 24 at 13:24

1 Answer 1

Reset to default
7
$\begingroup$

In comments, the OP indicates that what they really want is a uniqueness result for reduced words in arbitrary graphs of groups. (Indeed, what the question actually asks for, that any word can be transformed into a reduced word by successively cancelling, is obvious by induction on length.)

The desired uniqueness result exists, but people don't usually write it down in full generality, because it's a bit of a mess to state. Instead, they usually write down the following morally equivalent result, which can be thought of as uniqueness for the trivial element.

Theorem: Any word in the fundamental group of a graph of groups that represents the trivial element is not reduced.

For instance, this is Theorem 11 of Serre's classic Trees.

The appropriate uniqueness result follows immediately: given two reduced words $u,v$ both representing the same element $g$, we have that $uv^{-1}$ represents the trivial element, and so is not reduced. Since $u$ and $v$ are themselves reduced, the only possible cancellation occurs at the concatenation point of the words. Now apply this cancellation and induct on length. Following convention, I will leave it as an exercise to state the uniqueness result that this proves. ;)

Finally, I'll add an important philosophical remark, of which I'm sure the OP is well aware. The existence and uniqueness of normal forms for graphs of groups is equivalent to the statement that the Bass--Serre tree is a tree -- existence shows that the graph is connected, and uniqueness shows that it has no loops. So if you're content to prove that it's a tree via another technique (e.g. the topological approach of Scott--Wall) then you can also deduce existence and uniqueness.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ For the case of a free group itself, the topological approach to proving that the "Bass-Serre tree" (i.e. the universal cover of a rose) is indeed a tree is particularly simple. This yields my favorite proof of the fact that pairwise cancellation of generators of a word results in a unique reduced word, independent of choices. $\endgroup$
    – Lee Mosher
    Mar 24 at 15:57
  • $\begingroup$ Just for clarity/completeness for OP: "reduced" in Serre's Theorem 11 here of course does not mean "freely reduced", but defined locally via adjacent elements in the sequence of elements not being reducible to a single element (corresponding to a "pinch" or two elements of an amalgamated subgroup). This is what OP said they needed in the comments. $\endgroup$
    – Carl-Fredrik Nyberg Brodda
    Mar 24 at 16:00
  • $\begingroup$ @Carl-FredrikNybergBrodda: yes, it’s exactly the same sense of “reduced” that the OP used in the question and comments. $\endgroup$
    – HJRW
    Mar 24 at 16:45
  • $\begingroup$ @HJRW Yes, I agree they are the same -- but it's not the same definition as in the question, a priori (minimum syllable length). I suppose the fact that these are the same is basically the entire crux of the question...! :) $\endgroup$
    – Carl-Fredrik Nyberg Brodda
    Mar 24 at 16:48
  • $\begingroup$ @HJRW Thanks for taking the time to think about the question. Indirectly I've gleamed that there are no precise references for this kind of fact, so I'll have to write up some details. $\endgroup$
    – NWMT
    Mar 27 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.