Strong triangle conjecture for finite maximal codes and the embeddability of Shor's counterexample

A 2017 paper by Liang Zhang and K.P. Shum proved that every finite maximal code $X$ organizes the words of each set $X_w\subseteq a^*wa^*$ into matrices whose row and column index sets factor the cyclic group $\mathbb{Z}_n$, and proposed a strengthened form of the long-standing triangle conjecture of Perrin and Schützenberger: for every finite maximal code, every letter $a$ of order $n$, every $w$ over the remaining letters, and every $K\geq 0$, at most $K+1$ words $a^iwa^j$ of the associated set $X_w$ have $i+j\leq K$. They verified this when the system of factorizations induced by $X$ contains a Krasner factorization, when $n$ is prime, or when one factor is a singleton, but the general statement remains open, as does the related structural question of whether every finite maximal code induces a system containing a Krasner factorization (or, in De Felice's formulation, a good arrangement of each $X_w$) — a condition known to imply the counting inequalities — and the question of whether Shor's 1985 counterexample code, which violates the triangle inequality, can be embedded into any finite maximal code at all. This problem asks to prove or refute the strong triangle conjecture, to settle the corresponding structural existence question for Krasner factorizations and good arrangements, and, as a constituent question with decisive consequences, to decide the finite maximal embeddability of Shor's code; later work (De Felice 2022, Cordero 2019 and 2024) has confirmed the conjecture only for restricted orders such as primes, products of two primes, and all $n<36$, while the most recent specialist evidence leaves both a proof and a counterexample as live possibilities.

Background

A (variable-length) code over a finite alphabet $A$ is a set $X\subseteq A^*$ of words in which every word of the submonoid $X^*$ generated by $X$ factors uniquely as a product of words of $X$; equivalently, $X$ is a basis of a free submonoid of the free monoid $A^*$. A prefix code is a code in which no word is a left factor of another. Two finite sets of words are commutatively equivalent when they are in bijection via a map that only reorders the letters of each word; a code is commutatively prefix when it is commutatively equivalent to some prefix code. A finite maximal code is a code not properly contained in any larger code over the same alphabet; for a finite code this is equivalent to completeness, meaning every word of $A^*$ occurs as a factor of some word of $X^*$. A finite code is finitely completable when it is contained in some finite maximal code; Restivo showed in 1977 that not every finite code is finitely completable. In any finite maximal code and for any letter $a$, a unique power $a^n$ belongs to $X$; $n$ is the order of $a$. A bayonet code is a code all of whose words have the form $a^iba^j$. Perrin and Schützenberger conjectured around 1977–1981 (the triangle conjecture) that every finite bayonet code $X$ satisfies the triangle inequalities: for every $k\geq 0$, the number of words of $X$ of length at most $k$ is at most $k$; equivalently $\mathrm{Card}(X)\leq \max\{|x|:x\in X\}$, the name coming from viewing each word $a^rba^v$ as a lattice point in the triangle $r+v\leq k$. Shor refuted this in 1985 with the explicit finite bayonet code $b\{1,a,a^7,a^{13},a^{14}\}\cup\{a^3,a^8\}b\{1,a^2,a^4,a^6\}\cup a^{11}b\{1,a,a^2\}$, which is not commutatively equivalent to any prefix code; the conjecture was therefore restricted to bayonet codes that can be embedded in a finite maximal code, and it is implied by Schützenberger's factorization conjecture, which predicts that every finite maximal code admits a positive factorization $\underline{X}-1=\underline{P}(\underline{A}-1)\underline{S}$ of characteristic polynomials. A factorization of the cyclic group $\mathbb{Z}_n$ of order $n$ is a pair $(P,Q)$ of sets such that every residue class modulo $n$ is uniquely $p+q$ with $p\in P$, $q\in Q$; a Krasner factorization is the special case arising from a chain of divisors of $n$ via products of geometric polynomial quotients $(a^{k_j}-1)/(a^{k_{j-1}}-1)$, and a Hajós factorization is one built by Hajós's classical recursive construction, in which at each step one of the two factors is periodic; every Krasner factorization is a Hajós factorization. Zhang and Shum (2017) associated to each finite maximal code $X$, letter $a$ of order $n$, and word $w\in B(a^*B)^*$ with $B=A\setminus\{a\}$, the set $X_w=(a^*wa^*\cap X^*)\setminus[a^n(a^*wa^*\cap X^*)\cup(a^*wa^*\cap X^*)a^n]$, equivalently $X_w=a^*wa^*\cap(X^*\setminus(a^nX^*\cup X^*a^n))$, and proved that the left sets $a^P$ and right sets $a^Q$ of $X$ (defined via strong completability of generators) form a system $\mathcal{P}\times\mathcal{Q}$ of factorizations of $\mathbb{Z}_n$, that the words of each $X_w$ arrange into a matrix whose row and column index sets factor $\mathbb{Z}_n$, and that the counting inequalities $\mathrm{Card}(\{a^iwa^j\in X_w:i+j\leq K\})\leq K+1$ for all $K\geq 0$ hold whenever a Krasner factorization belongs to the induced system, in particular whenever $n$ is prime or one of the induced factors is a singleton. They conjectured the inequalities for all finite maximal codes — a strengthening of the surviving (restricted) triangle conjecture — and left open whether every induced system contains a Krasner factorization, or, in De Felice's formulation, whether each $X_w$ admits a good arrangement, that is, a recursively constructed matrix arrangement of the words of $X_w$ mirroring the recursive construction of Hajós factorizations. Later work sharpened but did not settle this: De Felice (2016 survey; 2022) recast the problem via good arrangements and Reutenauer's weak factorization theorem (a proven weak form of the factorization conjecture giving partial decompositions of $A^*$ through $X^*$), proved the triangle conjecture for $X\cap a^*Ba^*$ when $a^{pq}\in X$ with $p,q$ prime, and proved decidability of finite maximal completion for codes $Y\cup a^n$ with $n$ a product of at most two primes; Cordero (2019, 2024) verified the strong triangle conjecture whenever $n$ is a so-called cbc Hajós number (cbc abbreviating complete bayonet code, meaning a code $X\cup\{a^n\}$ with $X\subseteq a^*ba^*$ and $\mathrm{Card}(X)=n$) — $n$ a product of at most three primes or of the form $p^kq$, hence for all $n<36$ — exhibited failures of the prefix-suffix decomposition for other $n$, and proved divisibility lower bounds forcing any counterexample to be large (for his small test codes, $n$ divisible by 36); Kraizberg (2026) confirmed that the commutative equivalence conjecture for finite maximal codes is still open, proving only a weak structural surrogate.

Problem Statement

Settle the strong triangle conjecture of Zhang and Shum, in either direction, together with its structural counterpart and its embedding constituent, as follows. Let $A$ be a finite alphabet, $a\in A$, $B=A\setminus\{a\}$, let $X\subseteq A^*$ be a finite maximal code, let $n$ be the order of $a$ (the unique positive integer with $a^n\in X$), let $w\in B(a^*B)^*$, and let $X_w=(a^*wa^*\cap X^*)\setminus[a^n(a^*wa^*\cap X^*)\cup(a^*wa^*\cap X^*)a^n]$, equivalently $X_w=a^*wa^*\cap(X^*\setminus(a^nX^*\cup X^*a^n))$. (1) Prove, or refute by an explicit finite maximal code, the statement that for every such $X$, $a$, and $w$, and every $K\geq 0$, $\mathrm{Card}(\{a^iwa^j\in X_w:i+j\leq K\})\leq K+1$. (2) On the structural side, determine whether the system $\mathcal{P}\times\mathcal{Q}$ of factorizations of $\mathbb{Z}_n$ induced by $X$ (left sets times right sets, in the sense of Zhang–Shum) always contains a Krasner factorization, equivalently whether every $X_w$ admits a good arrangement. By Zhang–Shum's theorem, a Krasner factorization in the induced system implies the inequalities of (1), so a positive answer to (2) yields (1), and the task set for (2) is settled by deciding the structural question in either direction — reporting a counterexample, a finite maximal code whose induced system contains no Krasner factorization, refutes the structural counterpart just as a proof establishes it. Whether conversely the validity of the inequalities of (1) forces such a Krasner factorization (or forces a good arrangement) is a separate open question that (2) does not require, so (1) and (2) are distinct problems whose answers may diverge. (3) As the decisive constituent for the surviving restricted conjecture, decide whether Shor's counterexample code $b\{1,a,a^7,a^{13},a^{14}\}\cup\{a^3,a^8\}b\{1,a^2,a^4,a^6\}\cup a^{11}b\{1,a,a^2\}$ over the binary alphabet is contained in some finite maximal code: an explicit containing finite maximal code refutes the restricted triangle conjecture and the factorization conjecture for finite maximal codes, while a proof of (1) for all finite maximal codes rules such an embedding out. These three questions form one objective — determining the exact scope of the triangle inequality for finite maximal codes — and they are linked by the established implications: a positive answer to (2) yields (1), a proof of (1) settles (3) negatively, and a counterexample to (1) or an embedding in (3) settles the overarching question in the negative direction.

References

1. Liang Zhang, K.P. Shum. Finite maximal codes and triangle conjecture. Discrete Mathematics 340(3):541–549, 2017. DOI: 10.1016/j.disc.2016.10.008. https://doi.org/10.1016/j.disc.2016.10.008
2. P.W. Shor. A counterexample to the triangle conjecture. Journal of Combinatorial Theory, Series A 38(1):110–112, 1985. DOI: 10.1016/0097-3165(85)90032-9. https://doi.org/10.1016/0097-3165(85)90032-9
3. D. Perrin, M.P. Schützenberger. A conjecture on sets of differences of integer pairs. Journal of Combinatorial Theory, Series B 30(1):91–93, 1981. DOI: 10.1016/0095-8956(81)90096-4. https://doi.org/10.1016/0095-8956(81)90096-4
4. Clelia De Felice. Some conjectures on codes. arXiv:1611.04580, 2016. arXiv ID: 1611.04580. https://arxiv.org/abs/1611.04580
5. Clelia De Felice. Finite maximal codes and factorizations of cyclic groups. Journal of Automata, Languages and Combinatorics 28(4):287–338, 2023. DOI: 10.25596/jalc-2023-287. https://doi.org/10.25596/jalc-2023-287 arXiv ID: 2202.09675. https://arxiv.org/abs/2202.09675
6. Christophe Cordero. A Note with Computer Exploration on the Triangle Conjecture. Proceedings of the 13th International Conference on Language and Automata Theory and Applications (LATA 2019), pp. 409–420, 2019. DOI: 10.1007/978-3-030-13435-8_30. https://doi.org/10.1007/978-3-030-13435-8_30
7. Christophe Cordero. Factorizations of Cyclic Groups and Bayonet Codes. Journal of Automata, Languages and Combinatorics 29(1):11–39, 2024. DOI: 10.25596/jalc-2024-011. https://doi.org/10.25596/jalc-2024-011 arXiv ID: 2301.13566. https://arxiv.org/abs/2301.13566
8. Dean Kraizberg. A Weak Structural Form of Commutative Equivalence in Finite Codes. arXiv:2603.27656, 2026. arXiv ID: 2603.27656. https://arxiv.org/abs/2603.27656
9. Haiyan Liu, Rongdong Cui, Tianjie Zhang, Shuo Zhang. Bernoulli sets over ternary and multiletter alphabets: Algebraic characterizations, polynomial divisibility, and commutative prefix properties. Theoretical Computer Science, 2026. DOI: 10.1016/j.tcs.2026.116024. https://doi.org/10.1016/j.tcs.2026.116024