Palindromic Length in Free Groups: Reflections, Noncrossing Matchings, and Catalan Forms
Abstract
Let F=F(X) be a free group of finite rank, with palindromic length taken with respect to the fixed basis X. We embed F as the index-two subgroup of the universal Coxeter group W=Frtimesθ⟨ t| t2=1⟩, where θ(x)=x−1 for x∈ X, and prove pl(g)=minℓT(g),ℓT(gt). Dyer's deletion theorem then identifies reflection length with the minimum number of unmatched positions in a noncrossing equal-label partial matching on a reduced Coxeter word. This gives an O(n3)-time, O(n2)-space algorithm for palindromic length, together with recovery of an optimal palindromic factorization. The matching model also gives a structural characterization. For every ordered full binary tree with k leaves we define a literal word template whose leaves are palindromes and whose internal vertices carry arbitrary words. A reduced word w represents an element of palindromic length at most k if and only if w is a literal instance of one of these templates. Hence the Ck−1 ordered binary-tree shapes give a complete finite family for each fixed k. For k=4 the five templates are exactly the five forms proposed by Frid, proving the completeness of that list. A companion Lean 4 development verifies the four-palindrome classification end to end for every finite rank, including the ordinary reduced-word formulation and the literal five-form conclusion.
Related
- A lower bound on the density of prefixes with maximal palindromic length
- Matchings and shape-Wilf-Equivalence of sets of patterns of length three I: Triples
- Matchings and shape-Wilf-Equivalence of sets of patterns of length three II: Quadruples and Quintuples
- The quasisymmetric flag variety: a toric complex on noncrossing partitions
- Categorifications of noncrossing partitions of type B and affine type A
BibTeX
@misc{liao2026palindromic,
title = {{Palindromic Length in Free Groups: Reflections, Noncrossing Matchings, and Catalan Forms}},
author = {Junjie Liao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17027},
eprint = {2609.17027},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17027},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Palindromic Length in Free Groups: Reflections, Noncrossing Matchings, and Catalan Forms
AU - Junjie Liao
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17027
UR - https://arxiv.org/abs/2609.17027
AB - Let F=F(X) be a free group of finite rank, with palindromic length taken with respect to the fixed basis X. We embed F as the index-two subgroup of the universal Coxeter group W=Frtimes_θ⟨ t| t^2=1⟩, where θ(x)=x^−1 for x∈ X, and prove pl(g)=minℓ_T(g),ℓ_T(gt). Dyer's deletion theorem then identifies reflection length with the minimum number of unmatched positions in a noncrossing equal-label partial matching on a reduced Coxeter word. This gives an O(n^3)-time, O(n^2)-space algorithm for palindromic length, together with recovery of an optimal palindromic factorization. The matching model also gives a structural characterization. For every ordered full binary tree with k leaves we define a literal word template whose leaves are palindromes and whose internal vertices carry arbitrary words. A reduced word w represents an element of palindromic length at most k if and only if w is a literal instance of one of these templates. Hence the C_k−1 ordered binary-tree shapes give a complete finite family for each fixed k. For k=4 the five templates are exactly the five forms proposed by Frid, proving the completeness of that list. A companion Lean 4 development verifies the four-palindrome classification end to end for every finite rank, including the ordinary reduced-word formulation and the literal five-form conclusion.
ER -