Palindromic length in free groups through reflection length and noncrossing matchings

Problem

Give an algorithm computing the palindromic length of an element of a finite-rank free group.

\operatorname{pl}(w)=\min\{k:w=p_1\cdots p_k,\ p_i\text{ palindromes}\}.

A palindrome equals its reversal as a reduced signed word. Multiplication is in the group, so cancellation between factors is allowed. The algorithm below also returns an optimal factorization.

Setup and result

Fix a free group $F_n$ with specified basis $X=\{x_1,\ldots,x_n\}$ , where $n\geq0$ . A signed letter is $x_i$ or $x_i^{-1}$ . An element is a palindrome if its freely reduced word reads the same in both directions, with the signs retained. The identity is a palindrome. Its palindromic length is

\mathop{\mathrm{pl}}(w)=\min\{k\geq0:w=p_1\cdots p_k, \ p_j\text{ is a palindrome for every }j\}.

The empty product is the identity, so $\mathop{\mathrm{pl}}(1)=0$ . The minimum exists because every signed letter is a palindrome. All products in this definition are group products, and cancellation between factors is allowed. The basis is part of the definition.

This last distinction is essential. For distinct basis elements $a,b,c$ , the word $abca$ has no contiguous palindromic subword of length greater than one, but

\tag{2} abca=(aba)\,a^{-2}\,(aca)

is a product of three group palindromes. This example appears in Saarela (7, Example 4); its optimality will also follow from the computation in Section “A worked factorization”.

Bardakov, Shpilrain, and Tolstykh proved that palindromic length is unbounded in every nonabelian free group and asked for an algorithm computing it (2, Problem 2). Their question is recorded as Problem 16.9 of the Kourovka Notebook (6). Computability already follows from the theorem on twisted equations of Dahmani and Guirardel (1, Theorem 4), as explained below. We give an explicit reflection-length formula and the following quantitative construction.

Theorem 1. There is a terminating algorithm which, given a word representing $w\in F_n$ , returns the integer $q=\mathop{\mathrm{pl}}(w)$ and freely reduced palindromes $p_1,\ldots,p_q$ with $p_1\cdots p_q=w$ . For a freely reduced input of positive length $L$ , the computation uses $O(L^3)$ arithmetic and symbol operations, $O(L^2)$ table entries, and $O(L^2)$ letters of written output. Table values and indices have $O(\log(L+1))$ bits. The empty reduced input returns zero and the empty list of factors.

The model charges constant time for equality of basis labels, table access, and arithmetic on integers of the stated size. These are operation counts, rather than bit-complexity bounds for arbitrary encodings of generator names. A raw input of $N$ signed letters can be freely reduced with a stack in $O(N)$ operations. Thus the complete bound is $O(N+L^3)$ when $L>0$ , and $O(N)$ when $L=0$ .

The algebraic step is particularly simple to state. Let

W=\langle t,s_1,\ldots,s_n\mid t^2=s_1^2=\cdots=s_n^2=1\rangle \cong\underbrace{C_2*\cdots*C_2}_{n+1\text{ factors}}, \qquad \iota(x_i)=s_i t.

A reflection of $W$ is a conjugate of one of its displayed generators, and $\mathop{\mathrm{\ell_{\mathcal R}}}(g)$ is the minimum number of reflections with product $g$ . The homomorphism $\iota$ identifies $F_n$ with the subgroup of even words in $W$ .

Theorem 2. For every $w\in F_n$ ,

\tag{4} \mathop{\mathrm{pl}}(w)=\min\{\mathop{\mathrm{\ell_{\mathcal R}}}(\iota(w)),\mathop{\mathrm{\ell_{\mathcal R}}}(\iota(w)t)\}.

An optimal reflection factorization for the smaller term can be converted explicitly into an optimal palindromic factorization of $w$ . The two reflection lengths in (4) differ by exactly one.

Relation to earlier work

Proposition 3. Theorem 4 of Dahmani and Guirardel (1) implies an algorithm computing $\mathop{\mathrm{pl}}(w)$ and an optimal palindromic factorization.

Proof. Let $\theta(x_i)=x_i^{-1}$ . Then $\theta^2=1$ and, by uniqueness of reduced words, $p$ is palindromic if and only if $\theta(p)p=1$ . For $1\leq k\leq L=|w|$ , consider the system

P_1\cdots P_k=w,\qquad \theta(P_j)P_j=1\quad(1\leq j\leq k).

Its twists generate a finite subgroup of $\operatorname{Out}(F_n)$ , so the cited theorem decides solvability. The first solvable system has $k=\mathop{\mathrm{pl}}(w)$ ; identities allow padding, and the individual signed letters give the upper bound $L$ . Enumerating tuples of reduced words then finds a solution for this least $k$ . The identity is handled separately. This deduction gives computability, without the explicit polynomial bound proved below. ◻

Reflection length and its computation have an established literature. Dyer (4) identifies reflection length in a Coxeter group with the fewest deletions from a fixed reduced expression that leave the identity. Brandenbursky, Gal, Kędra, and Marcinkowski (3) develop the cancellation norm and a cubic-time, quadratic-space interval algorithm for free groups. Their updated preprint includes a March 2023 erratum establishing the required word-independence statement for Coxeter groups and right-angled Artin groups. In the universal Coxeter group, inverse-letter pairing becomes equal-letter pairing. The matching recurrence used below is this cancellation-norm method specialized to the involutive alphabet.

The contribution developed here is the exact reduction (4), its use to compute group-palindromic length and recover optimal factors, and a formal verification of the assembled algorithm. The cancellation-norm recurrence is not claimed as a new algorithm. A direct proof of its specialization is included, in particular the cancellation argument in Appendix “Cancellation surgery for noncrossing matchings”.

Saarela (7) compares palindromic length in free monoids and free groups. Frid (5) gives structural characterizations for products of at most two or three palindromes and discusses the general algorithmic question. Those characterizations describe the reduced word itself as a concatenation of prescribed forms. The present algorithm allows arbitrary palindromic length and returns a group factorization; it does not assert analogous concatenation forms for all lengths.

The reflection-length reduction

Normal forms and involutions

Let $S=\{s_0,s_1,\ldots,s_n\}$ , put $t=s_0$ , and consider

\tag{6} W=\langle s_0,s_1,\ldots,s_n\mid s_i^2=1\ (0\leq i\leq n)\rangle.

We use capital letters such as $U,V,C$ for words on $S$ , and write $[U]$ for the element of $W$ represented by $U$ . The empty word is $\varnothing$ . A word on $S$ is reduced if adjacent letters are different. The elementary reduction is deletion of an adjacent pair $aa$ .

For completeness we establish the normal form used below directly. If $R$ is reduced and $a\in S$ , define the stack update

T_a(R)= \begin{cases} R',&R=R'a,\\ Ra,&R\text{ is empty or its last letter is different from }a. \end{cases}

Both outputs are reduced. Moreover, $T_a(T_a(R))=R$ : an appended letter is removed on the next update, while a removed letter is appended again because the preceding letter, if any, is different from $a$ .

Lemma 4. Every element of $W$ has exactly one reduced representative. Reading a word from left to right with the updates $T_a$ computes that representative. Two words represent the same element if and only if they are connected by insertions and deletions of adjacent equal pairs.

Proof. Let $N(U)$ be the stack output starting at the empty word. It is reduced. Induction on the number of letters read shows that the prefix already read can be reduced to the current stack: the next letter is either appended or cancels the last stack letter. Hence $U$ is equivalent, by adjacent-pair deletions, to $N(U)$ .

Insertion or deletion of $aa$ anywhere in the input leaves the stack output unchanged. Indeed, after the prefix preceding that pair has been read, the two intervening updates have composite $T_a^2$ , which is the identity. The suffix is then read from the same stack in both cases. Thus $N$ is constant on the equivalence relation generated by the defining insertions and deletions. A reduced word is its own stack output, so equivalent reduced words are literally equal.

The quotient of the word monoid by these insertions and deletions is a group: $\mathop{\mathrm{rev}}(U)$ is an inverse to $U$ , since $U\mathop{\mathrm{rev}}(U)$ and $\mathop{\mathrm{rev}}(U)U$ cancel from the middle outwards. This quotient has exactly the presentation (6). Consequently the preceding existence and uniqueness statements are statements about $W$ itself. ◻

In particular, the inverse of a reduced word on $S$ is its literal reversal. Each defining cancellation changes length by two. There is therefore a well-defined homomorphism

\tag{8} \epsilon:W\longrightarrow\mathbb Z/2\mathbb Z, \qquad \epsilon([U])=|U|\pmod 2.

Write $W^+=\ker\epsilon$ for its even subgroup.

Definition 5. A reflection of $W$ is an element $c s_i c^{-1}$ , where $c\in W$ and $0\leq i\leq n$ . Write $\mathcal R$ for the set of reflections and put

\mathop{\mathrm{\ell_{\mathcal R}}}(g)=\min\{q\geq 0:g=r_1\cdots r_q,\ r_j\in\mathcal R\}.

This is the reflection length of $g$ .

The minimum exists because the generators themselves are reflections. Every reflection has odd parity, so every reflection factorization of $g$ has the same parity of factor count:

\tag{10} \mathop{\mathrm{\ell_{\mathcal R}}}(g)\equiv\epsilon(g)\pmod 2.

Lemma 6. The reflections are exactly the nonidentity involutions of $W$ .

Proof. A conjugate of a generator is nonidentity and has square one. Conversely, let $g\ne 1$ have square one, and start with its nonempty reduced word. Whenever the first and last letters agree, remove them, recording the removal as a conjugation. The process terminates with

g=c[h]c^{-1},

where $h$ is reduced and either has one letter or has different first and last letters. The word $h$ cannot be empty: deleting matching end letters from a nonempty reduced word cannot pass through a reduced word of length two with equal letters. If $|h|\geq 2$ , the word $hh$ is reduced, since there is no cancellation at its central junction. It is nonempty, and hence $[h]^2\ne 1$ by Lemma 4. This contradicts $g^2=1$ . Therefore $h=s_i$ for some $i$ , and $g$ is a reflection. ◻

The even subgroup and palindromes

The assignment

\tag{12} \iota(x_i)=s_i t\qquad(1\leq i\leq n)

extends uniquely to a homomorphism $\iota:F_n\to W$ . Its image lies in $W^+$ . At the level of signed words, the two substitution rules are

\tag{13} x_i\longmapsto s_i t, \qquad x_i^{-1}\longmapsto t s_i.

Lemma 7. The map $\iota$ is an isomorphism from $F_n$ onto $W^+$ . Its inverse $\delta:W^+\to F_n$ can be computed by splitting any even representative into consecutive pairs and making the replacement

\tag{14} s_i s_j\longmapsto x_i x_j^{-1}, \qquad x_0=1.

Proof. We first show that pair decoding does not depend on the even representative. Consider deletion of an adjacent pair $s_a s_a$ . If the two letters form one decoding block, their contribution is $x_a x_a^{-1}=1$ . If they straddle two blocks, the affected substring has the form $(s_i s_a)(s_a s_j)$ . Before deletion its contribution is

x_i x_a^{-1}x_a x_j^{-1},

and after deletion it is $x_i x_j^{-1}$ . These are equal. In the second case both outside letters exist because the total length is even and the deleted letters straddle a block boundary. The convention $x_0=1$ makes the same argument valid when some indices are zero. All later block boundaries retain their parity. The decoded group element is consequently unchanged by every elementary deletion and, in reverse, by every insertion. Lemma 4 proves that $\delta$ is well-defined.

Concatenating even words preserves their block boundaries, so $\delta$ is a homomorphism. For $1\leq i\leq n$ we have $\delta(\iota(x_i))=\delta(s_i t)=x_i$ . In the other direction,

\iota(x_i x_j^{-1})=s_i t t s_j=s_i s_j.

This identity also holds for zero indices if one interprets $\iota(x_0)=1=s_0t$ . Applying it to every pair shows that $\iota\delta$ is the identity on $W^+$ . Hence the homomorphisms are mutually inverse. ◻

Let $\theta$ be the automorphism of $F_n$ defined on the basis by $\theta(x_i)=x_i^{-1}$ . Applying this substitution twice fixes every generator, so $\theta^2$ is the identity. Conjugation by $t$ realizes this automorphism in $W$ :

\tag{17} t\iota(g)t=\iota(\theta(g))\qquad(g\in F_n).

Indeed, on a generator the left side is $t(s_it)t=ts_i=\iota(x_i^{-1})$ , and both sides define homomorphisms in $g$ .

Lemma 8. For every $p\in F_n$ , the following statements are equivalent:

$p$ is a palindrome;
$\theta(p)=p^{-1}$ ;
$\iota(p)t$ is a reflection of $W$ .

These equivalences include $p=1$ .

Proof. Let $b_1\cdots b_k$ be the reduced representative of $p$ . The word $b_1^{-1}\cdots b_k^{-1}$ is reduced and represents $\theta(p)$ , whereas $b_k^{-1}\cdots b_1^{-1}$ is reduced and represents $p^{-1}$ . Uniqueness of free reduction makes their equality equivalent to $b_i=b_{k+1-i}$ for every $i$ . This proves the first equivalence.

By (17),

(\iota(p)t)^2 =\iota(p)\,t\iota(p)t =\iota(p\theta(p)).

Injectivity of $\iota$ shows that this square is one exactly when $\theta(p)=p^{-1}$ . The element $\iota(p)t$ has odd parity and so is never the identity. Lemma 6 now gives the second equivalence. For $p=1$ the corresponding reflection is $t$ . ◻

Transporting factorizations

The need for two reflection lengths is a parity issue: a product of an even number of palindromes and a product of an odd number lead to different elements of $W$ .

Proof of the identity in Theorem 2. Suppose first that $w=p_1\cdots p_k$ , where every $p_j$ is a palindrome. For $1\leq j\leq k$ , set

\tag{19} r_j=t^{j-1}\iota(p_j)t^j =t^{j-1}(\iota(p_j)t)t^{j-1}.

The second equality uses $t^2=1$ . By Lemma 8, each $r_j$ is a conjugate of a reflection and hence a reflection. In the product the powers $t^j t^j$ at successive junctions cancel, giving

r_1\cdots r_k=\iota(p_1\cdots p_k)t^k=\iota(w)t^k.

Thus one of the two reflection lengths in (4) is at most $k$ . Taking the minimum over palindromic factorizations proves that the right side is at most $\mathop{\mathrm{pl}}(w)$ . The argument also covers $k=0$ .

Conversely, fix $e\in\{0,1\}$ and take a shortest reflection factorization

\tag{21} \iota(w)t^e=r_1\cdots r_q, \qquad q=\mathop{\mathrm{\ell_{\mathcal R}}}(\iota(w)t^e).

Odd parity of reflections implies $q\equiv e\pmod 2$ . Define

\tag{22} P_j=t^{j-1}r_jt^j\in W^+, \qquad p_j=\delta(P_j).

The parity of $P_j$ is $(j-1)+1+j=2j$ , as required to apply $\delta$ . Further,

P_jt=t^{j-1}r_jt^{j-1}

is a reflection. Lemma 8 shows that $p_j$ is a palindrome. Multiplication again cancels all intervening even powers of $t$ , and gives

\iota(p_1\cdots p_q) =r_1\cdots r_qt^q =\iota(w)t^{e+q} =\iota(w).

Injectivity of $\iota$ proves that their product is $w$ . Consequently $\mathop{\mathrm{pl}}(w)\leq q$ for each choice of $e$ , which is the other inequality in (4). ◻

Corollary 9. The integers $\mathop{\mathrm{\ell_{\mathcal R}}}(\iota(w))$ and $\mathop{\mathrm{\ell_{\mathcal R}}}(\iota(w)t)$ differ by exactly one.

Proof. Since $t$ is a reflection, appending it to a factorization proves $\mathop{\mathrm{\ell_{\mathcal R}}}(gt)\leq\mathop{\mathrm{\ell_{\mathcal R}}}(g)+1$ . Applying this with $gt$ instead of $g$ gives the reverse inequality up to one. By (10), $g$ and $gt$ have reflection lengths of opposite parity. Their difference is therefore nonzero and has absolute value one. ◻

Remark 10. For later reconstruction, there is a convenient equivalent form of (22). Put $h_j=\delta(r_jt)$ . Then

\tag{25} p_j=\theta^{j-1}(h_j).

Indeed, $P_j=t^{j-1}(r_jt)t^{j-1}$ , and (17) applies. Thus one need only append a single $t$ to each reflection word, decode its consecutive pairs, freely reduce, and invert every signed letter when $j$ is even. The last operation retains the order of the letters. Formula (25) avoids writing long powers of $t$ .

Reflection length and noncrossing matchings

Definition 11. Let $v=a_0\cdots a_{m-1}$ be any word on $S$ , without a reduction assumption. An equal-letter noncrossing matching on $v$ is a set $M$ of pairs $(i,j)$ of positions such that

$0\leq i<j<m$ and $a_i=a_j$ ;
every position occurs in at most one pair; and
there are no pairs $(i,j),(k,l)$ with $i<k<j<l$ .

Positions in no pair are called unmatched. The cost of $M$ is the number of unmatched positions, and $D(v)$ is the minimum of these costs.

There are finitely many matchings on a finite set of positions, and the empty set of pairs is allowed. Hence this minimum is attained. Every matching cost is of the form $m-2|M|$ ; in particular,

\tag{26} 0\leq D(v)\leq m, \qquad D(v)\equiv m\pmod 2.

It is useful to record the recursive structure of these matchings. In a nonempty word, either the first position is unmatched, or it is paired to some later occurrence of the same letter. In the second case write the word as $aUaV$ , with the indicated two occurrences paired. No pair connects a position in $U$ to a position in $V$ , because it would cross the indicated pair. Thus every matching is obtained uniquely in one of the following ways, with the displayed costs:

\tag{27} \begin{array}{c|c|c} \text{word}&\text{construction}&\text{cost}\\ \hline \varnothing&\text{empty matching}&0\\ aU&\text{first position unmatched; a matching on }U&1+u\\ aUaV&\text{pair the displayed }a\text{'s; match }U\text{ and }V&u+v. \end{array}

Here $u$ and $v$ are the costs of the chosen matchings on the corresponding subwords, rather than necessarily their minimum costs. Conversely, each construction in (27) gives a noncrossing matching. Concatenation of matchings on consecutive subwords also preserves noncrossing and adds their costs.

The essential point is that $D$ respects group cancellation. We give a proof using the first-position decomposition, so that all changes to a matching are explicit.

Proposition 12. For all words $U,V$ on $S$ and every letter $a\in S$ ,

\tag{28} D(UaaV)=D(UV).

Proof. Adding an adjacent matched pair gives $D(UaaV)\leq D(UV)$ . For the converse, a matching can be carried through the deletion of $aa$ without increasing its unmatched count. The complete matching surgery, including the case where the two deleted positions have distinct partners, is proved in Appendix “Cancellation surgery for noncrossing matchings”. ◻

The matching formula

Lemma 13. The value $D(v)$ depends only on $[v]\in W$ . Regarded as a function on $W$ , it satisfies

\tag{29} \begin{gathered} D(gh)\leq D(g)+D(h),\\ D(cgc^{-1})=D(g),\qquad D(s_i)=1. \end{gathered}

Proof. Well-definedness follows from Proposition 12 and Lemma 4. Concatenation of optimal matchings proves subadditivity.

For a letter $a$ and a word $V$ , pair the outer letters of $aVa$ and retain an optimal matching inside. This gives $D(aVa)\leq D(V)$ . Apply the same inequality with $aVa$ in place of $V$ . Two adjacent cancellations then give

D(V)=D(aaVaa)\leq D(aVa).

Thus conjugation by a generator preserves $D$ . Iterating this identity proves invariance under conjugation by an arbitrary element of $W$ . Finally, a one-letter word has no possible pair, so its minimum unmatched count is one. ◻

Proposition 14. For every word $v$ on $S$ ,

\tag{31} D(v)=\mathop{\mathrm{\ell_{\mathcal R}}}([v]).

More precisely, every matching on $v$ with $q$ unmatched positions determines a factorization of $[v]$ into $q$ reflections.

Proof. By Lemma 13, each reflection has $D$ -value one. For a factorization $[v]=r_1\cdots r_q$ , subadditivity therefore gives

D(v)\leq D(r_1)+\cdots+D(r_q)=q.

Taking a shortest reflection factorization proves $D(v)\leq\mathop{\mathrm{\ell_{\mathcal R}}}([v])$ .

We prove the more precise statement by induction on $|v|$ , using the matching decomposition (27). The empty word requires the empty factorization. If $v=aU$ and its first position is unmatched, factor $[U]$ by induction and precede those factors by the reflection $a$ . This adds exactly one factor, corresponding to the unmatched first position.

If the first position is paired, write $v=aUaV$ . The restrictions of the matching to $U$ and $V$ have, say, $u$ and $v'$ unmatched positions. By induction choose reflection factorizations

[U]=r_1\cdots r_u, \qquad [V]=r_{u+1}\cdots r_{u+v'}.

Then

\tag{34} [aUaV] =(a r_1 a)\cdots(a r_u a) r_{u+1}\cdots r_{u+v'}.

Every displayed factor is a reflection. The number of factors is $u+v'$ , the cost of the given matching. The identities also hold when either factor list is empty. Applying this result to an optimal matching gives $\mathop{\mathrm{\ell_{\mathcal R}}}([v])\leq D(v)$ , proving (31). ◻

One can also formulate the same quantity as a deletion minimum. For reduced words this is Dyer’s characterization (4) in the universal Coxeter group; the statement here also permits unreduced representatives.

Corollary 15. For any word $v$ on $S$ , $D(v)$ is the least number of positions whose deletion leaves a word representing the identity in $W$ .

Proof. Delete the unmatched positions of a noncrossing matching. The remaining matching is perfect. Its word reduces to the empty word: by (27), a nonempty perfectly matched word is $aUaV$ with $U$ and $V$ perfectly matched; inductively reduce $U$ and $V$ and cancel the resulting $aa$ . Thus any matching of cost $q$ supplies $q$ deletions leaving the identity.

Conversely, suppose $q$ deletions leave a word representing the identity. By Lemma 4, the surviving word reduces to the empty word. Record the two original positions removed at each adjacent cancellation. These pairs form a perfect equal-letter noncrossing matching on the surviving positions. To see noncrossing directly, a pair removed later cannot have exactly one endpoint between the endpoints of an earlier pair: that endpoint would still separate the earlier pair at the time it was removed. Reinserting the deleted positions as unmatched positions preserves the order of all paired endpoints and hence preserves noncrossing. It produces a matching on $v$ of cost $q$ . Taking minima in both directions proves the claim. ◻

The interval dynamic program

Fix a word $v=a_0\cdots a_{m-1}$ on $S$ . For integers $0\leq i\leq j\leq m$ , write $v[i,j)=a_i\cdots a_{j-1}$ and set

d_{i,j}=D(v[i,j)).

The interval is half open: it includes $i$ and excludes $j$ . In particular, $d_{i,i}=0$ .

Proposition 16. For every $i<j$ ,

\tag{36} d_{i,j}= \min\left( \{1+d_{i+1,j}\}\, \cup\, \{d_{i+1,k}+d_{k+1,j}:i<k<j,\ a_i=a_k\} \right).

The minimum always has at least one candidate.

Proof. If the first position is unmatched, its cost is one plus the cost of a matching on $v[i+1,j)$ . The best such matching has cost $1+d_{i+1,j}$ , and adjoining the unmatched position attains this value.

If the first position is paired to $k$ , equality of labels requires $a_i=a_k$ . Noncrossing separates the remaining matching into one on $v[i+1,k)$ and one on $v[k+1,j)$ . Its cost is at least $d_{i+1,k}+d_{k+1,j}$ , and pairing $i$ to $k$ around optimal matchings on those two intervals attains that bound. These possibilities exhaust all matchings by (27). The unmatched alternative is available even when there is no equal-letter partner. ◻

Algorithm 17. Given $v=a_0\cdots a_{m-1}$ , construct a cost table $d$ and a choice table $c$ as follows.

Set $d_{i,i}=0$ for $0\leq i\leq m$ .
For $i=m-1,m-2,\ldots,0$ , and for each $j=i+1,i+2,\ldots,m$ , perform these steps:
1. initialize $d_{i,j}=1+d_{i+1,j}$ and $c_{i,j}=\mathsf{skip}$ ;
2. examine $k=i+1,i+2,\ldots,j-1$ in order; whenever $a_i=a_k$ and $d_{i+1,k}+d_{k+1,j}<d_{i,j}$ , replace $d_{i,j}$ by this sum and set $c_{i,j}=\mathsf{pair}(k)$ .

A tie retains the previously stored choice. No choice is required on an empty interval.

Every table entry on the right side of (36) has starting index strictly greater than $i$ . Thus every read in Algorithm 17 accesses an already computed row. All loops are finite. Increasing interval width is an equivalent valid evaluation order, but the decreasing-row order above agrees with the accompanying implementation.

Proposition 18. Algorithm 17 terminates and returns $d_{i,j}=D(v[i,j))$ for every interval. Each stored choice attains that minimum and, recursively, specifies an optimal noncrossing matching of the interval.

Proof. Induct downwards on the starting index $i$ . Empty intervals have the correct value zero. Every dependency of a positive-width interval starts strictly to the right of $i$ , and hence has already been computed correctly. The initialization supplies exactly the first candidate of (36); the finite scan compares it to every other permissible candidate. The final entry is therefore exactly the minimum in that equation. Its stored choice attains the entry because a choice is changed only together with the corresponding value. Combining the inductively optimal submatchings according to that choice gives an attaining matching, as in the proof of Proposition 16. ◻

Reconstructing reflections and palindromes

We give the reconstruction explicitly, including a form that avoids repeated copying of whole lists of reflection factors.

Use a word $C$ on $S$ as an accumulated conjugator. Define $\mathsf{Reflect}(i,j,C)$ to return a list of reflection words by the following recursion, in which the product of the returned list will be $[C]\,[v[i,j)]\,[C]^{-1}$ :

If $i=j$ , return the empty list.
If $c_{i,j}=\mathsf{skip}$ , emit the word $C a_i\mathop{\mathrm{rev}}(C)$ , and then return the list $\mathsf{Reflect}(i+1,j,C)$ after it.
If $c_{i,j}=\mathsf{pair}(k)$ , return, in this order, the list $\mathsf{Reflect}(i+1,k,Ca_i)$ followed by the list $\mathsf{Reflect}(k+1,j,C)$ .

The initial call is $\mathsf{Reflect}(0,m,\varnothing)$ . All subintervals in recursive calls have strictly smaller width. One may equivalently use an explicit stack; in the paired case, put the tail task on the stack before the interior task so that the interior is processed first.

Proposition 19. Fix an interval $[i,j)$ and a word $C$ . The call $\mathsf{Reflect}(i,j,C)$ terminates. It returns exactly $d_{i,j}$ reflections, and their ordered product is

[C]\,[v[i,j)]\,[C]^{-1}.

Proof. Induct on $j-i$ . The empty-interval claim is immediate. In the unmatched case the first emitted word represents a reflection, and induction gives the product of the remaining list. Their product is

([C]a_i[C]^{-1}) ([C]\,[v[i+1,j)]\,[C]^{-1}) =[C]\,[v[i,j)]\,[C]^{-1}.

The number of factors is $1+d_{i+1,j}=d_{i,j}$ by the stored choice.

In the paired case let $U=v[i+1,k)$ and $V=v[k+1,j)$ . Then $v[i,j)=a_iUa_iV$ . By induction the two returned lists have products

[C]a_i[U]a_i[C]^{-1} \quad\text{and}\quad [C][V][C]^{-1}.

Their product is the required conjugate of $a_iUa_iV$ . Their factor counts add to $d_{i+1,k}+d_{k+1,j}=d_{i,j}$ . Each factor is a reflection by the same induction, since every emission has the form of a conjugated generator. Strict decrease of widths proves termination in both cases. ◻

We can now state the complete algorithm in the original free group without leaving any minimization as an oracle.

Algorithm 20. Given a word on the signed basis $X^{\pm1}$ , perform the following operations.

Freely reduce the input to a word $w$ . If it is empty, return zero and the empty list.
Substitute the rules (13) and reduce adjacent equal pairs to obtain a word $v$ representing $\iota(w)$ .
Set $v_0=v$ and $v_1=vt$ . Use Algorithm 17 to compute the cost and choice tables for each of these two words. Write $q_e$ for the full-interval entry of the table for $v_e$ .
Choose $e\in\{0,1\}$ for which $q_e$ is smaller, and reconstruct the reflection words $R_1,\ldots,R_q$ for $v_e$ , where $q=q_e$ .
For $j=1,\ldots,q$ , decode the even word $R_jt$ using (14) and freely reduce the result to $h_j$ . If $j$ is odd, put $p_j=h_j$ ; if $j$ is even, put $p_j=\theta(h_j)$ by inverting every signed letter without changing its position.
Return $q$ and the list $p_1,\ldots,p_q$ .

The word $vt$ need not be reduced. Proposition 12 is the reason it may be used directly. By Corollary 9, the two full-interval values differ by one, so the choice in step 4 is unambiguous. If desired, one table for $vt$ supplies both costs and both sets of choices: the relevant root intervals are $[0,|v|)$ and $[0,|v|+1)$ . Using two tables makes no difference to the asymptotic bounds.

Theorem 21. Algorithm 20 terminates. Its output satisfies $q=\mathop{\mathrm{pl}}(w)$ , every $p_j$ is a freely reduced palindrome, and $p_1\cdots p_q=w$ in $F_n$ .

Proof. All reductions and substitutions scan finite words. Table construction terminates by Proposition 18, and reconstruction terminates by Proposition 19. There are finitely many output words, each finite, so the remaining decoding and free reduction also terminate.

For a nonempty reduced input, Propositions 18 and 14 identify the two costs as

q_0=\mathop{\mathrm{\ell_{\mathcal R}}}(\iota(w)),\qquad q_1=\mathop{\mathrm{\ell_{\mathcal R}}}(\iota(w)t).

Theorem 2 gives $q=\min(q_0,q_1)=\mathop{\mathrm{pl}}(w)$ . Reconstruction yields $q$ reflections $r_j=[R_j]$ with product $\iota(w)t^e$ . Every $R_j$ has odd length, since it is explicitly a word $C a\mathop{\mathrm{rev}}(C)$ . Therefore $R_jt$ is even and can be decoded. Remark 10 identifies the resulting $p_j$ with the factors (22). The proof of Theorem 2 establishes that they are palindromes and that their product is $w$ .

Step 5 explicitly freely reduces each $h_j$ . Inverting all signed letters preserves reducedness, so the returned $p_j$ are freely reduced as well. A returned identity factor, if there were one, could be omitted, contradicting $q=\mathop{\mathrm{pl}}(w)$ . Thus the optimal nonempty output contains no identity factors. The empty reduced input is handled directly and has all the asserted properties with $q=0$ . ◻

Time, storage, and output bounds

The bounds on the written factors require some care: the recursive identity (34) is a correct construction, but naively copying every intermediate factor list is unnecessary. The accumulated-conjugator recursion above gives the stated bounds directly.

Lemma 22. For an input word of length $m$ , the interval table has exactly

\tag{41} \frac{(m+1)(m+2)}{2}

entries, including empty intervals. Algorithm 17 examines exactly

\tag{42} \sum_{h=1}^{m}(m-h+1)(h-1) =\binom{m+1}{3}

possible partner positions. Table construction uses $O(m^3)$ operations and $O(m^2)$ entries. Costs and choice indices require $O(\log(m+1))$ bits for $m\geq1$ .

Proof. There are $m-h+1$ intervals of width $h$ for $0\leq h\leq m$ . Summing these counts gives (41). Each positive width- $h$ interval initializes one unmatched candidate and examines its $h-1$ possible partners, which gives the sum in (42). Equivalently, a partner examination is a triple $0\leq i<k<j\leq m$ ; the number of such triples is $\binom{m+1}{3}$ . At each examination there is one label test and, if the labels agree, a bounded number of accesses, additions, comparisons, and assignments. Initialization uses $O(m^2)$ operations, so the total is $O(m^3)$ for $m\geq1$ .

Every cost is at most its interval width by (26). The sum in a paired candidate is at most $(k-i-1)+(j-k-1)=j-i-2$ , and the unmatched candidate is at most $j-i$ . Thus intermediate candidate values also fit between zero and $m$ . Indices lie between zero and $m$ ; one additional tag distinguishes the unmatched choice. These quantities use $O(\log(m+1))$ bits. ◻

Lemma 23. Starting from a word of length $m$ , the reconstruction produces at most $m$ reflection words, each of length at most $m$ . Their total written length is at most $m^2$ , and reconstruction can be performed in $O(m^2)$ operations using an additional $O(m)$ working space besides the output.

Proof. One reflection is emitted for each unmatched position of the chosen matching. Hence the number of emitted words is $q=D(v)\leq m$ . For a particular emitted word $C a_i\mathop{\mathrm{rev}}(C)$ , let $d=|C|$ . Each letter of $C$ was appended on a descent into the interior of a matched pair. These $d$ pair descents involve $2d$ distinct positions of the original word, and the emitted unmatched position is distinct from all of them. Therefore $2d+1\leq m$ , and

|C a_i\mathop{\mathrm{rev}}(C)|=2d+1\leq m.

Summing over the $q$ emitted words gives total length at most $qm\leq m^2$ . Reducing any emitted word can only shorten it.

For the time bound, a skip node of the recursion consumes one position, and a pair node consumes two. The subintervals at a pair node are disjoint. Thus there are at most $m$ nonempty nodes; the number of empty children is also $O(m)$ . Maintain the conjugator by a linked stack, appending or removing one letter on descent or return. This takes constant time per change and at most $O(m)$ simultaneous storage. On each emission, traverse that stack to write the conjugator and its reversal around the central letter. The work per emission is linear in its written length. The node traversal uses $O(m)$ operations and the emissions use $O(m^2)$ . The task stack for a depth-first traversal has depth at most $m$ , with constant-size data in each frame. ◻

Proposition 24. For a freely reduced input of length $L>0$ , the work in Algorithm 20 after free reduction is $O(L^3)$ operations. It uses $O(L^2)$ table entries with $O(\log(L+1))$ bits per entry, and the total length of its returned free-group factors is $O(L^2)$ .

Proof. The letter substitutions (13) create $2L$ Coxeter letters. Stack reduction never increases that length. Hence the reduced encoding $v$ has length at most $2L$ , while $vt$ has length at most $2L+1$ . Lemma 22 applied to the two tables gives the time, entry-count, and integer-size bounds. Encoding and its reduction take $O(L)$ operations.

Let $m\leq2L+1$ be the length of the word chosen for reconstruction, and $q\leq m$ its minimum cost. By Lemma 23, each $R_j$ has length at most $m$ , and the sum of their lengths is at most $m^2$ . Appending $t$ adds one letter per factor. The decoder replaces each pair by at most two signed letters; occurrences of $x_0$ are omitted. Free reduction and the possible application of $\theta$ do not increase the resulting length. Consequently

\tag{44} \sum_{j=1}^q |p_j| \leq\sum_{j=1}^q (|R_j|+1) \leq m^2+m \leq(2L+1)(2L+2) \leq12L^2.

Decoding, free reduction, and inversion of signed letters are linear in the words processed. They therefore use $O(m^2)=O(L^2)$ operations. The additional working space and written output also fit within $O(L^2)$ words of storage. ◻

Proof of Theorem 1. Theorem 21 proves termination, validity of every output factor, equality of the product, and optimality of the factor count. Proposition 24 proves all resource bounds after free reduction. A stack computes free reduction in linear time: each raw input letter is pushed at most once and popped at most once. The empty reduced word is handled by the first step of the algorithm. These statements include the rank-zero group, where the only reduced word is empty. ◻

A worked factorization

Let $a=x_1$ , $b=x_2$ , and $c=x_3$ be distinct basis elements, and revisit Saarela’s example $w=abca$ (7, Example 4). The reduced Coxeter encoding and the reduced representative after multiplication by $t$ are

v=s_1t s_2t s_3t s_1t, \qquad u=s_1t s_2t s_3t s_1.

Since $vt=utt$ cancels to $u$ , Proposition 12 gives $D(vt)=D(u)$ . In $u$ choose pairs $(0,6)$ and $(1,5)$ . The remaining three positions, with letters $s_2,t,s_3$ , are unmatched.

The labels $s_2$ and $s_3$ occur only once, so their two positions must be unmatched in every matching of $u$ . Since $|u|=7$ is odd, every matching has an odd number of unmatched positions. Thus $D(u)\geq3$ , and the displayed matching proves $D(u)=3$ .

In the word $v$ , again the $s_2$ and $s_3$ positions must be unmatched. A matching of cost two would consequently pair the two occurrences of $s_1$ at positions $0$ and $6$ and would match all four occurrences of $t$ at positions $1,3,5,7$ . But position $7$ would then be paired to one of $1,3,5$ , crossing $(0,6)$ . Such a matching is impossible. The parity bound (26) now gives $D(v)\geq4$ . The pairs $(0,6),(1,5)$ in $v$ leave exactly four unmatched positions, so $D(v)=4$ . The reflection-length formula yields

\mathop{\mathrm{pl}}(abca)=\min\{4,3\}=3.

For the indicated matching of $u$ , reconstruction gives the three reflections

r_1=s_1t s_2t s_1,\qquad r_2=s_1t s_1,\qquad r_3=s_1t s_3t s_1.

They arise by conjugating the unmatched letters $s_2,t,s_3$ by $s_1t$ ; the middle conjugate has been reduced. Appending $t$ , pair decoding, and applying (25) give the optimal factorization

\tag{48} abca=(aba)\,a^{-2}\,(aca).

Each factor is a reduced palindrome, and multiplication reduces the right side to $abca$ . Another optimal factorization is

abca=a^2\,(a^{-1}ba^{-1})\,(aca).

There is no contiguous palindromic subword of $abca$ with length greater than one. Thus a partition of this particular reduced string into contiguous palindromes would need four pieces, even though its group palindromic length is three. The cancellations permitted in the definition are essential.

Explicit counting bounds

For the reduced input length $L>0$ , let $C$ denote the number of partner candidates inspected in the two tables, $E$ their total number of entries, and $p_1,\ldots,p_q$ the output. The companion proves

\tag{50} C\leq35L^3,\qquad E\leq25L^2,\qquad \sum_{j=1}^{q}|p_j|\leq12L^2.

These are bounds on combinatorial counters and written output. The operation-model analysis is given in Section “Time, storage, and output bounds”; the formal bounds do not assert a compiler-level running time.

Cancellation surgery for noncrossing matchings

This appendix proves the matching transformation used in Proposition 12. It works for arbitrary words on the involutive alphabet, including unreduced words. Throughout, the restriction of a matching to a block retains exactly those pairs whose two endpoints lie in that block.

Lemma 25. If $U$ and $V$ are words, every matching on $UV$ gives a matching of the same cost on $VU$ . Consequently $D(UV)=D(VU)$ .

Proof. It suffices first to move the initial letter to the end. If that letter is unmatched in $aU$ , retain the matching of $U$ and make the last position of $Ua$ unmatched. If it is matched, write the word as $aXaY$ using its partner. The existing matching restricts to matchings of $X$ and $Y$ . On the rotated word $XaYa$ , retain both restrictions and pair the two displayed $a$ ’s around $Y$ . This is the concatenation of a matching on $X$ with a matching on $aYa$ , so it is noncrossing. The cost is unchanged in both cases. Repeating this operation $|U|$ times takes $UV$ to $VU$ . It gives $D(VU)\leq D(UV)$ . Interchanging $U$ and $V$ gives the reverse inequality. ◻

Lemma 26. For every word $V$ and letter $a$ , a matching on $aaV$ can be changed into a matching on $V$ with no greater cost.

Proof. Call the two initial occurrences of $a$ the first and second positions. Apply (27) at these positions.

If the first position is unmatched, there are two cases. If the second is also unmatched, remove both; the cost decreases by two. If the second is paired, write $V=XaY$ where the displayed $a$ is its partner. The remaining matching consists of restrictions to $X$ and $Y$ . On $V=XaY$ retain these restrictions and make the displayed $a$ unmatched. The cost remains $1+\operatorname{cost}(X)+\operatorname{cost}(Y)$ .

If the first position is paired to the second, remove this pair and retain the matching on $V$ , with unchanged cost.

It remains to consider a first position paired farther to the right. Then the word is $a\,(aX)\,aY$ , and the matching splits into one on the interior $aX$ and one on $Y$ . If the initial position of $aX$ is unmatched, keep the restrictions on $X$ and $Y$ and make the intervening $a$ of $V=XaY$ unmatched. Again the cost is unchanged.

Finally, suppose that this initial position of $aX$ is paired within $aX$ . Write $X=UaB$ according to that partner. The whole word and its two indicated pairs have the form

a\,a\,U\,a\,B\,a\,Y,

with the first $a$ paired to the last displayed $a$ , and the second $a$ paired to the third displayed $a$ . The matching restricts separately to $U$ , $B$ , and $Y$ . After removing the two initial positions, the remaining word is $UaBaY$ . Retain the three restrictions and pair the two remaining displayed $a$ ’s around $B$ . This is a concatenation of a matching on $U$ , a matching on $aBa$ , and a matching on $Y$ , so it is noncrossing. Its cost, like the original cost, is the sum of the costs on $U$ , $B$ , and $Y$ . These cases exhaust the possibilities. ◻

Completion of the proof of Proposition 12. Insert an adjacent matched pair to obtain $D(UaaV)\leq D(UV)$ . For the other inequality, rotation and Lemma 26 give

D(UV)=D(VU)\leq D(aaVU)=D(UaaV).

Both inequalities hold when either $U$ or $V$ is empty. ◻

References

Preprint · Lean (GitHub)

F. Dahmani and V. Guirardel, Foliations for solving equations in groups: free, virtually free, and hyperbolic groups, J. Topol. 3 (2010), no. 2, 343–404. doi:10.1112/jtopol/jtq010.

V. G. Bardakov, V. Shpilrain, and V. Tolstykh, On the palindromic and primitive widths of a free group, J. Algebra 285 (2005), no. 2, 574–585. doi:10.1016/j.jalgebra.2004.11.003.

M. Brandenbursky, Ś. R. Gal, J. Kędra, and M. Marcinkowski, The cancellation norm and the geometry of bi-invariant word metrics, Glasgow Math. J. 58 (2016), no. 1, 153–176. doi:10.1017/S0017089515000129. Author version, including the March 2023 erratum: arXiv:1310.2921v3.

M. J. Dyer, On minimal lengths of expressions of Coxeter group elements as products of reflections, Proc. Amer. Math. Soc. 129 (2001), no. 9, 2591–2595. doi:10.1090/S0002-9939-01-05876-2.

A. E. Frid, Small palindromic lengths in free groups and word equations with antimorphisms, 2025. arXiv:2512.10024.

E. I. Khukhro and V. D. Mazurov (eds.), Unsolved problems in group theory: The Kourovka Notebook, 21st ed., version of 1 September 2026, Problem 16.9. arXiv:1401.0300v46.

A. Saarela, Palindromic length in free monoids and free groups, in Combinatorics on Words (WORDS 2017), Lecture Notes in Computer Science, vol. 10432, Springer, 2017, 203–213. doi:10.1007/978-3-319-66396-8_19.