bibkey: ferenczizamboni2025clustering authors: Sébastien Ferenczi, Luca Q. Zamboni year: 2025 title: Clustering, order conditions, and languages of interval exchanges doi: null url: https://arxiv.org/abs/2507.17370v2 claim: ‘Conjecture 1: A language on k letters satisfying a symmetric order condition and with no connection has palindromic complexity 1 for n even, k for n odd.’ strata_touched:
- D5/S1/Words/SymmetricOrderPalindromicComplexityRefutation license: citation-only triage: anchor
Verified locator
DOI: null
Source: https://arxiv.org/abs/2507.17370v2
The pinned v2 PDF places the language axioms and bispecial words on page 4, symmetric pairs of orders on page 5, Definitions 6 and 7 on page 6, Proposition 14 on page 13, and Conjecture 1 in Section 4 on page 14.
Language axioms
Section 1, page 4: “By a language L over A we mean a factorial language: a collection of sets (Ln)n≥0 where the only element of L0 is the empty word ε, and where each Ln for n ≥ 1 consists of words of length n, such that each v ∈ Ln+1 can be written in the form v = au = u′b with a, b ∈ A and u, u′ ∈ Ln.”
“Except when otherwise mentioned, all our languages are tacitly assumed to be extendable: for each v ∈ Ln there exists a,b ∈ A with av,vb ∈ Ln+1.”
“A word w in L is right special (resp. left special) if it has more than one right extension wx (resp. left extension xw) in L, with x in A. If w is both right special and left special, then w is bispecial.”
The encoding uses Fin k for the alphabet, List (Fin k) for finite words, and a set of words for the language. IsFactorial expresses closure under every contiguous factor, IsExtendable expresses one-letter extension on each side, and UsesAllLetters requires every letter as a singleton. The counterexample includes the empty word.
Symmetric orders and connections
Section 2, page 5: “A pair of orders (<D, <A) is symmetric if <A is the reverse of <D, i.e. a <A b if and only if b <D a for all distinct letters a, b ∈ A.”
Definition 6, page 6: “A language L (extendable or not) satisfies the order condition for the pair of orders (<D,<A) if whenever axb, cxd ∈ L with a, b,c,d ∈ A, x ∈ A* (possibly empty), a ≠ c and b ≠ d, then a <A c if and only if b <D d. The order condition is called the symmetric order condition if the pair of orders (<D,<A) is symmetric.”
Definition 7, page 6: “If a language L on an alphabet A satisfies the order condition for (<D,<A), a bispecial word w has a connection if there are letters a <A a′, consecutive in the order <A, letters b <D b′, consecutive in the order <D, such that awb and a′wb′ are in L, and neither awb′ nor a′wb is in L.”
A permutation sigma : Equiv.Perm (Fin k) encodes departure comparison by sigma a < sigma b and arrival comparison by sigma b < sigma a. Consecutive letters have no intervening alphabet element. Recurrence and closure under reversal are separate source properties, not assumptions of Conjecture 1.
Palindromic complexity
Introduction, page 3: “We give also some estimates on the palindromic complexity of L, i.e., the number of palindromes in L of each given length n.” The encoding is Set.ncard {w | w ∈ K ∧ w.length = n ∧ w.reverse = w}. Length zero counts the empty word.
Proposition 14, Section 4, page 13: “Let L be a language on k letters satisfying a symmetric order condition. Then its palindromic complexity is at most 1 for n even, k for n odd.”
“Furthermore, if L is generated by an infinite or bi-infinite word, is closed under reversal and has no connections, its palindromic complexity is 1 for n even, k for n odd.”
These are source results. The four-letter refutation satisfies their upper bounds and does not satisfy the additional hypotheses of the equality assertion.
Conjecture
Section 4, Conjecture 1, page 14: “A language on k letters satisfying a symmetric order condition and with no connection has palindromic complexity 1 for n even, k for n odd.”
The settling module refutes this claim at k = 4, the identity permutation, and n = 3. Source vertices 1, 2, 3, 4 correspond to Fin 4 values 0, 1, 2, 3. The graph edges are 0 → 3, 1 → 3, 2 → j for every j, and 3 → 0. Its three palindromes of length three are [2,2,2], [0,3,0], and [3,0,3]. The general family and the cases with at most three letters are outside the formalized statement.