Good arrangements of the $a^*wa^*$-components of finite maximal codes and Krasner factorizations of cyclic groups

For a finite maximal variable-length code $X$ over an alphabet $A$, each letter $a\in A$ has an order $n$ (an integer with $a^n\in X$), and for every word $w$ not beginning or ending with $a$ one can single out the component $X_w$ of words of the form $a^iw a^j$ arising from $X^*$. De Felice (2016) and the Zhang–Shum theorem it builds on show that these components are organized by factorizations of the cyclic group $\mathbb{Z}_n$, and ask whether this organization always reaches the finest level: does every $X_w$ admit a 'good arrangement' — equivalently, by De Felice's 2023 characterization, does $X$ always admit a Krasner factorization as a companion factorization — and, in the Zhang–Shum formulation, does the system of factorizations of $\mathbb{Z}_n$ induced by $X$ always contain a Krasner factorization? A negative answer would refute Schützenberger's long-standing factorization conjecture. As of 2026 the question is open in general; it is settled affirmatively when $\Omega(n)\le 2$ (De Felice, 2023), while Cordero's 2024 framework of borders for complete bayonet codes proves the adjacent strong triangle conjecture for bayonet codes of further orders (products of at most three primes, or $p^kq$) and exhibits non-Hajós behavior beyond them.

Background

A variable-length code is a set $X$ of words over a finite alphabet $A$ such that every word of $X^*$ (the set of all concatenations of words of $X$, a free submonoid of the free monoid $A^*$ — the set of all words over $A$ — with basis $X$) factors into codewords in exactly one way. A code is maximal if it is contained in no strictly larger code over $A$; a classical result states that every letter $a\in A$ then has an order relative to $X$: an integer $n\ge 1$ with $a^n\in X$. The structure of finite maximal codes is governed by three famous conjectures going back to Schützenberger and Perrin: the factorization conjecture (every finite maximal code $X$ satisfies $\underline{X}-1=\underline{P}(\underline{A}-1)\underline{S}$ for finite sets $P,S$ of words, where underlining denotes the characteristic polynomial of a finite language, formally $\underline{Y}=\sum_{y\in Y}y$), the commutative equivalence conjecture (every finite maximal code is commutatively equivalent to a prefix code, i.e., its words can be replaced by permutations of their letters so that no word is a prefix of another), and the triangle conjecture for bayonet codes (codes whose words all have the form $a^i b a^j$), the original unrestricted form of which was refuted by a counterexample of Shor in 1985. The standard reference for this theory is the monograph of Berstel, Perrin, and Reutenauer.

A distinct line of research connects finite maximal codes with factorizations of cyclic groups. A factorization of $\mathbb{Z}_n$ is a pair $(I,J)$ of subsets such that every residue mod $n$ is uniquely $i+j$ with $i\in I$, $j\in J$. Krasner and Ranulac completely described a special class: $(I,J)$ is a Krasner factorization of $\mathbb{Z}_n$ when the generating functions satisfy $\sum_{i\in I}a^i\cdot\sum_{j\in J}a^j=(a^n-1)/(a-1)$, which amounts to a product decomposition along a chain of divisors $1=k_0\mid k_1\mid\cdots\mid k_s=n$ of $n$ (Example: $\{0,1\}$ with $\{0\}$ is a Krasner factorization of $\mathbb{Z}_2$). Hajós factorizations, introduced by Hajós in his study of group factorizations, form a wider class built recursively along such divisor chains. Zhang and Shum (Discrete Mathematics, 2017) proved a structural theorem linking the two worlds: fix a finite maximal code $X$, a letter $a$ of order $n$, let $B=A\setminus\{a\}$, and for $w\in B(a^*B)^*$ (words over $B\cup\{a\}$ that start and end with letters of $B$) define the component

$$X_w=(a^*wa^*\cap X^*)\setminus\bigl[a^n(a^*wa^*\cap X^*)\cap(a^*wa^*\cap X^*)a^n\bigr],$$

the words $a^iw a^j$ of $a^*wa^*\cap X^*$ that are not simultaneously reducible by a full period $a^n$ on the left and on the right. Zhang and Shum introduced left sets and right sets of $X$: a word $y$ is strongly right-completable for $X$ if every continuation can be repaired into $X^*$ — formally, for every $u\in A^*$ there exists $v\in A^*$ with $yuv\in X^*$ — and $a^P$ is a left set of $X$ if for some strongly right-completable generator $y$, $P=\{i\in\{0,\ldots,n-1\}\mid y\,a^{2n|X|+i}\in X^*\}$ (where $|X|=\max\{|x|\mid x\in X\}$ denotes the maximal word length of $X$), the powers of $a$ that can follow $y$ into $X^*$ at a fixed large offset; right sets are defined dually (the powers of $a$ that can precede a generator word into $X^*$, subject to an unambiguity condition on exponent differences). They proved that any left set $a^P$ and right set $a^Q$ give a factorization $(P,Q)$ of $\mathbb{Z}_n$, defined the system of factorizations of $\mathbb{Z}_n$ induced by $X$ as all such pairs, and showed: (i) each $X_w$ can be arranged in a matrix whose row sets and column sets factorize $\mathbb{Z}_n$, and (ii) if the induced system contains a Krasner factorization $(I,J)$, then each $X_w$ satisfies the triangle inequalities $\mathrm{Card}\{a^iw a^j\in X_w\mid i+j\le K\}\le K+1$ for all $K\ge 0$ — the strong (Zhang–Shum) form of the triangle conjecture.

De Felice (2016) strengthened this: her Theorem 5.1 shows that a Krasner factorization in the induced system yields more than the inequalities — it yields a good arrangement of every $X_w$, i.e., an arrangement of its words into a matrix that is recursively constructed in step with the recursive divisor-chain construction of the Hajós factorizations carried by its rows and columns (Definitions 3.2 and 3.4 of the source), with the given Krasner pair as 'Krasner associated pair'. She proved the existence of good arrangements when $a^p\in X$ for a prime $p$ (Corollary 5.1) and when the induced system contains a pair $(P,Q)$ with $P$ or $Q$ a singleton (Corollary 5.2), and posed the questions below. In subsequent work (Journal of Automata, Languages and Combinatorics, 2023) she reformulated the framework: a factorization $(T,R)$ of $\mathbb{Z}_n$ is a companion factorization of $X$ when the product $a^TX_wa^R$ is unambiguous and realizes every exponent pair $(h,m)\in\{0,\ldots,n-1\}^2$ for every $w$; her Proposition 7.2 proves that every $X_w$ has a good arrangement with one common Krasner pair $(I,J)$ Krasner-associated if and only if some Krasner factorization is a companion factorization of $X$, and her Proposition 7.3 proves that a Krasner companion always exists when $\Omega(n)\le 2$, where $\Omega(n)$ counts the prime factors of $n$ with multiplicity — the threshold at which, by a theorem of Hajós and de Bruijn, all factorizations of $\mathbb{Z}_n$ are Hajós. Because factorizing codes (codes satisfying the conclusion of the factorization conjecture) carry Krasner companions, a negative answer to the main question below would refute the factorization conjecture itself.

Problem Statement

Let $X$ be a finite maximal code over a finite alphabet $A$, let $a\in A$ be a letter of order $n$ relative to $X$ (i.e., $a^n\in X$), set $B=A\setminus\{a\}$, and for $w\in B(a^*B)^*$ (words that start and end with a letter different from $a$) let

$$X_w=(a^*wa^*\cap X^*)\setminus\bigl[a^n(a^*wa^*\cap X^*)\cap(a^*wa^*\cap X^*)a^n\bigr].$$

Main question: does there always exist a good arrangement of $X_w$ for every $w\in B(a^*B)^*$ — in the sense of Definitions 3.2 and 3.4 of the source: an arrangement of the words $a^iw a^j$ of $X_w$ into a matrix recursively constructed along the divisor chains of the Hajós factorizations of $\mathbb{Z}_n$ carried by its rows and columns — with one common Krasner factorization $(I,J)$ of $\mathbb{Z}_n$ as the associated pair for all $w$? By Proposition 7.2 of De Felice (2023), this uniform form holds if and only if $X$ admits a Krasner factorization $(T,R)$ of $\mathbb{Z}_n$ as a companion factorization: the product $a^TX_wa^R$ is unambiguous and realizes every exponent pair $(h,m)\in\{0,\ldots,n-1\}^2$, for every $w$. A stronger proposition is the formulation of Zhang and Shum followed by the source: does the system of factorizations of $\mathbb{Z}_n$ induced by $X$ — the pairs $(P,Q)$ with $a^P$ a left set and $a^Q$ a right set of $X$ — always contain a Krasner factorization? By Theorem 5.1 of the source, an affirmative answer in the induced-system form implies the main question (the uniform good-arrangement form); the converse is exactly sub-question (i) below, so the two forms are not known to be equivalent and the main question is the weaker of the two. An affirmative answer in any of these forms implies the strong (Zhang–Shum) triangle inequalities $\mathrm{Card}\{a^iw a^j\in X_w\mid i+j\le K\}\le K+1$ for all $K\ge 0$ and all $w$; a negative answer to the main question refutes the factorization conjecture, while a negative answer to the induced-system form does so only together with sub-question (i). Two sub-questions posed in the source remain open: (i) the converse of its Theorem 5.1 — if every $X_w$ has a good arrangement with $(I,J)$ as Krasner-associated pair, must $(I,J)$ belong to the induced system of factorizations (equivalently, by De Felice's Proposition 7.2, is every Krasner companion factorization of $X$ induced by a left set and a right set)? and (ii) does the source's Corollary 5.2 extend: if the induced system contains a pair $(P,Q)$ with $\mathrm{Card}(P)\le 2$ or $\mathrm{Card}(Q)\le 2$, must every $X_w$ have a good arrangement? The analogous extension of Corollary 5.1 from prime $p$ to $\Omega(n)\le 2$ has been answered affirmatively (De Felice, 2023, Propositions 7.2 and 7.3), so answers are required for the surviving general cases: arbitrary $n$ for the main question and for the stronger induced-system form, and the two sub-questions as stated.

References

1. Clelia De Felice, "Some conjectures on codes", arXiv preprint (2016), arXiv:1611.04580, DOI 10.48550/arXiv.1611.04580, https://arxiv.org/abs/1611.04580
2. Liang Zhang and 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
3. 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 (preprint arXiv:2202.09675, https://arxiv.org/abs/2202.09675)
4. 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 (preprint arXiv:2301.13566, https://arxiv.org/abs/2301.13566)
5. Christophe Cordero, "A Note with Computer Exploration on the Triangle Conjecture", in Language and Automata Theory and Applications (LATA 2019), Lecture Notes in Computer Science, pages 409–420 (2019), DOI 10.1007/978-3-030-13435-8_30, https://doi.org/10.1007/978-3-030-13435-8_30
6. P. W. Shor, "A counterexample to the triangle conjecture", Journal of Combinatorial Theory, Series A 38:110–112 (1985), DOI 10.1016/0097-3165(85)90032-9, https://doi.org/10.1016/0097-3165(85)90032-9
7. Jean Berstel, Dominique Perrin, and Christophe Reutenauer, "Codes and Automata", Encyclopedia of Mathematics and its Applications 129, Cambridge University Press (2009/2010), DOI 10.1017/cbo9781139195768, https://doi.org/10.1017/cbo9781139195768