Linear bounds on conjugator length in iterated free group constructions
Conjugator Length in Iterated Cyclic Amalgams of Free Groups
Discrete Mathematics
Summary
Certain groups built step-by-step from simple building blocks, called free groups, can have tricky elements that are related by 'conjugation.' This paper shows that the length needed to describe these relations grows only in a simple, predictable way (linearly) as the groups get more complex by joining along circles. The authors extend previous results to a broader family of groups and provide new proofs that reinforce an existing conjecture about one-relator groups. Their work clarifies how complicated it is to find these conjugations as group constructions become more layered.
What this means in practice
- •For computational group theorists: Provide precise guarantees on worst-case efforts to find conjugating elements in complex group constructions for algorithmic group theory software.
- •For cryptographers: Inform secure protocol design by ruling out certain group constructions as sources of conjugation problems with exponential complexity.
A theory result. No direct application yet.
Authors
Conan Gillis
Abstract
Let $\mathcal{A}_0$ be the set of finitely generated free groups on some countable alphabet and and define $\mathcal{A}_r$ inductively as the union of $\mathcal{A}_{r-1}$ with the set of amalgamated free products $G_1*_{\mathbb{Z}}G_2$, where $G_1,G_2\in \mathcal{A}_{r-1}$. We show, for all $r$, that every element of $\mathcal{A}_r$ has linear conjugator length, quantifying a result of Larsen and extending a result of Kharlampovich and Myasnikov. This is achieved by a linear conjugator length bound on a family of iterated HNN extensions of free groups. Also, in an appendix, we adapt a proof of A. Weiß to show that all Generalized Baumslag-Solitar Groups have linear conjugator length. As a consequence, we obtain that one-relator groups with non-trivial have linear conjugator length, giving evidence for a conjecture of Bridson, Riley, and Sale.