Palindromic width of free groups

DefinitionAlmost palindromes#✓fully proved

For a natural number \(m\), a word \(w\) in the letters \(x^{\pm 1}\) and \(y^{\pm 1}\) is an almost \(m\)-palindrome if there is a palindrome \(p\) in the same letters with the same length as \(w\) such that \(w\) and \(p\) differ in at most \(m\) positions. The word \(w\) need not be reduced.

def IsAlmostPalindrome (m : ℕ) (w : List (Fin 2 × Bool)) : Prop :=
  ∃ p : List (Fin 2 × Bool), p.length = w.length ∧ p.reverse = p ∧
    (List.zip w p).countP (fun q => q.1 ≠ q.2) ≤ m

Used by 1

Used byFinite almost-palindromic width of \(F_2\) (Kourovka 19.8)

DefinitionFinite almost-palindromic width of \(F_2\) (Kourovka 19.8)#✓fully proved

The proposition that there are positive integers \(m\) and \(c\) such that every element of the free group \(F_2\) on generators \(x, y\) is a product of at most \(c\) elements, each represented by an almost \(m\)-palindrome, that is, by a word in \(x^{\pm 1}, y^{\pm 1}\) (not necessarily reduced) that differs from a palindrome of the same length in at most \(m\) positions.

This is the question posed by V. G. Bardakov as Kourovka Problem 19.8.

def almostPalindromicWidthFinite : Prop :=
  ∃ m c : ℕ, 0 < m ∧ 0 < c ∧ ∀ g : FreeGroup (Fin 2), ∃ ws : List (List (Fin 2 × Bool)),
    ws.length ≤ c ∧ (∀ w ∈ ws, IsAlmostPalindrome m w) ∧ (ws.map FreeGroup.mk).prod = g

Uses 1 · Used by 1

Statement usesAlmost palindromes

Used byThe almost-palindromic width of \(F_2\) is infinite (Kourovka 19.8)

TheoremThe almost-palindromic width of \(F_2\) is infinite (Kourovka 19.8)#●ready to prove

There are no positive integers \(m\) and \(c\) such that every element of the free group \(F_2\) on generators \(x, y\) is a product of at most \(c\) elements, each represented by an almost \(m\)-palindrome, that is, by a word in \(x^{\pm 1}, y^{\pm 1}\) (not necessarily reduced) that differs from a palindrome of the same length in at most \(m\) positions. So the question of Kourovka Problem 19.8 has a negative answer.

Staiger proved more: for every \(m \ge 0\), the \(m\)-almost-palindromic width of every non-abelian free group is infinite.

public theorem_wanted almostPalindromicWidthFinite_refuted : ¬ almostPalindromicWidthFinite

Sources

• E. I. Khukhro and V. D. Mazurov (eds.), Unsolved Problems in Group Theory: The Kourovka Notebook, 21st issue, arXiv:1401.0300v49 (2026), Problem 19.8 (V. G. Bardakov); resolution: M. Staiger, On the almost-palindromic width of free groups, J. Algebra 659 (2024), 475-481 (arXiv:2306.15752), Section 1: m-almost-palindromes are words of the free monoid on the letters x^{±1}, y^{±1} (not necessarily reduced) within Hamming distance m of a palindrome, and the width is taken for the group elements they represent; Theorem 1: for a non-abelian free group F and every m ≥ 0 the m-almost-palindromic width of F is infinite; the Kourovka Notebook (21st issue) marks 19.8 solved: No, there are no such integers, https://arxiv.org/abs/2306.15752.

Uses 1

Statement usesFinite almost-palindromic width of \(F_2\) (Kourovka 19.8)

2 fully proved1 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.