The Schützenberger factorization conjecture for finite maximal codes and the associated finite-completion decision problems

This task concerns the unresolved questions acknowledged in De Felice's paper On factorizing codes: Structural properties and related decision problems (Adv. in Appl. Math. 39, 2007). The core question is the Schützenberger factorization conjecture: every finite maximal variable-length code $C$ over a finite alphabet $A$ admits finite subsets $P, S \subseteq A^*$ with $\underline{C} - 1 = \underline{P}(\underline{A} - 1)\underline{S}$, where $\underline{X}$ denotes the characteristic polynomial of a finite language $X$. Reutenauer proved the weak form with integer-coefficient polynomials $P, S \in \mathbb{Z}\langle A \rangle$, but the passage to genuine finite sets (coefficients 0/1) has remained open since the conjecture was first quoted in print in 1980. The source paper further leaves open the decidability of embedding a finite code into a finite maximal code beyond the arithmetic restriction $\Omega(n) \le 2$ under which it proves decidability, and the intrinsic characterization of which members of its good arrangement class arise from actual codes.

Background

A variable-length code is a set $C$ of words over a finite alphabet $A$ in which every word of the free monoid $A^*$ (the set of all finite words over $A$, equipped with concatenation) admits at most one factorization as a product of elements of $C$; equivalently, $C$ is the basis of a free submonoid of $A^*$. Codes are exactly the combinatorial models of uniquely decipherable message encodings, and the algebraic theory of codes initiated by Schützenberger studies them through semigroups, automata, and noncommutative polynomials. A code is maximal if it is inclusion-maximal among codes over $A$; a finite code is maximal precisely when it is complete, that is, when every sufficiently long word has some factor in $C^*$. Maximal prefix codes — codes in which no word is a proper left factor of another — are the archetype: if $P$ is the set of proper prefixes of the words of such a code $C$, then $\underline{C} = \underline{P}(\underline{A} - 1) + 1$, where $\underline{X}$ is the characteristic polynomial of the finite language $X$, i.e. the formal sum of its elements in the noncommutative polynomial algebra, and $1$ denotes the empty word.

Schützenberger's factorization conjecture (never published by him; first quoted in print in Perrin's 1980 survey Polynôme d'un code, in D. Perrin (ed.), Théorie des Codes, Actes de la 7ème École de Printemps d'Informatique Théorique, LITP and ENSTA, Paris, 1980, 169–176, and standard in the monograph of Berstel, Perrin and Reutenauer) asserts that this algebraic identity survives in full generality: every finite maximal code $C$ should admit finite sets $P, S \subseteq A^*$ with

$\underline{C} - 1 = \underline{P}\,(\underline{A} - 1)\,\underline{S}.$

A code satisfying this identity is called (positively) factorizing. Reutenauer proved in 1985 the celebrated weak form: for every finite maximal code $C$ there always exist polynomials $P, S \in \mathbb{Z}\langle A \rangle$ with integer (possibly negative) coefficients satisfying the identity. The entire difficulty lies in upgrading integer coefficients to the 0/1 coefficients of genuine finite sets. The conjecture is tied to two neighboring open questions: the commutative equivalence conjecture (every finite maximal code is commutatively equivalent to a prefix code — the words of one code being obtained from the words of the other by permuting letters within each word — which would imply factorizability) and the triangle conjecture for bayonet codes (codes whose words have the form $a^i b a^j$), whose unrestricted form was refuted by a counterexample of Shor in 1985, after which all three conjectures were restricted to finite maximal codes and their subsets.

A distinctive strand, running from Hajós' and Krasner's theory of factorizations of cyclic groups to the work of De Felice, Zhang and Shum, connects the conjecture to arithmetic. A pair $(R, T)$ of subsets of integers is a factorization of the cyclic group $\mathbb{Z}_n$ if every residue class modulo $n$ is uniquely $r + t \pmod n$ with $r \in R, t \in T$. The structured types used here are: a Krasner factorization of $\mathbb{Z}_n$, which is the factorization $(I, J)$ obtained by choosing a chain $1 = k_0 \mid k_1 \mid \cdots \mid k_s = n$ of divisors of $n$ and letting $I$ (respectively $J$) be the set of all sums that pick one element from each of the arithmetic progressions $\{0, k_{j-1}, 2k_{j-1}, \ldots, k_j - k_{j-1}\}$ with $j$ even (respectively $j$ odd); and a Hajós factorization, a mild recursive extension of this construction over the same divisor chains in which elements of one side may be independently translated within each factor (the operation $S \circ T$ of this literature). For a finite maximal code $C$ containing a power $a^n$ of a letter (such a power always exists), writing $\Omega(n)$ for the number of prime factors of $n$ counted with multiplicity, De Felice's 2007 paper proved that one can decide whether a finite set $X \subseteq a^*(A \setminus a)a^*$ is embedded in a finite maximal — indeed factorizing — code whenever $\Omega(n) \le 2$, by organizing the words of $C \cap a^*ba^*$ into good arrangements: arrangements of the words $a^i b a^j$ of the set into matrices whose row and column index sets come from Hajós factorizations of $\mathbb{Z}_n$ sharing a common Krasner companion factorization, constructed by the recursive rules introduced in De Felice's An enhanced property of factorizing codes (Theoret. Comput. Sci. 340, 2005) and used there as the property P of the 2007 source paper. She also proved (Proposition 4.1 of the 2007 source paper) that some sets with a good arrangement are not the trace of any code, so her sufficient conditions are not yet a characterization. Restivo had shown in 1977 that finite codes with no finite completion at all exist, so the general embedding problem — deciding whether a given finite code embeds in some finite maximal code — is nontrivial and its decidability is a recognized open problem, which the 2007 paper settles only under the restriction $\Omega(n) \le 2$.

Problem Statement

The central question is the Schützenberger factorization conjecture in its standard form: does every finite maximal code $C$ over a finite alphabet $A$ admit finite subsets $P, S \subseteq A^*$ such that

$\underline{C} - 1 = \underline{P}\,(\underline{A} - 1)\,\underline{S},$

where $\underline{X}$ denotes the characteristic polynomial (formal sum of elements) of a finite language $X$ and $1$ is the empty word — that is, is every finite maximal code positively factorizing? Two decision problems from the source paper share the same framework and remain open in exactly the generality the paper could not reach: (a) is it decidable, for a finite set $X \subseteq a^*(A \setminus a)a^*$ and arbitrary $n$ (in particular with $\Omega(n) > 2$), whether $X \cup \{a^n\}$ can be embedded in some finite maximal code — a special case of the general question, stated in the source paper's abstract, of deciding whether an arbitrary given finite code can be embedded in a finite maximal one — the case $\Omega(n) \le 2$ being decidable by the source paper's algorithm; and (b) is there an intrinsic, checkable characterization of which subsets of $a^*ba^*$ admitting a good arrangement (in the sense defined above — the property P of the source paper, whose recursive definition was introduced in De Felice, An enhanced property of factorizing codes, Theoret. Comput. Sci. 340 (2005) 240–256: an arrangement of the words $a^i b a^j$ into matrices whose row and column index sets come from Hajós factorizations of $\mathbb{Z}_n$ sharing a common Krasner companion factorization — and whose Proposition 4.1 supplies the proved non-code example) arise as $C \cap a^*ba^*$ for an actual factorizing code $C$, given that non-code members of this class provably exist? These three cores — the central factorization conjecture and the two associated decision problems (a) and (b) — are jointly the objective of the task, and each is independently open. The conjecture is posed for every finite alphabet $A$ and every finite maximal code $C$, with no restriction on alphabets, cardinalities, or values of $n$.

References

1. Clelia De Felice, On factorizing codes: Structural properties and related decision problems, Advances in Applied Mathematics 39(2) (2007) 173–196. DOI: 10.1016/j.aam.2005.12.002, https://doi.org/10.1016/j.aam.2005.12.002
2. Jean Berstel, Dominique Perrin, Christophe Reutenauer, Codes and Automata, Encyclopedia of Mathematics and its Applications 129, Cambridge University Press (2009). DOI: 10.1017/cbo9781139195768, https://doi.org/10.1017/cbo9781139195768
3. Christophe Reutenauer, Noncommutative factorization of variable-length codes, Journal of Pure and Applied Algebra 36 (1985) 167–186. DOI: 10.1016/0022-4049(85)90069-6, https://doi.org/10.1016/0022-4049(85)90069-6
4. P. W. Shor, A counterexample to the triangle conjecture, Journal of Combinatorial Theory, Series A 38 (1985) 110–112. DOI: 10.1016/0097-3165(85)90032-9, https://doi.org/10.1016/0097-3165(85)90032-9
5. Antonio Restivo, On codes having no finite completions, Discrete Mathematics 17 (1977) 309–316. DOI: 10.1016/0012-365x(77)90164-9, https://doi.org/10.1016/0012-365x(77)90164-9
6. Clelia De Felice, Finite completions via factorizing codes, International Journal of Algebra and Computation 17 (2007) 715–760. DOI: 10.1142/S0218196707003871, https://doi.org/10.1142/S0218196707003871
7. Clelia De Felice, A note on the factorization conjecture, Acta Informatica 50 (2013) 381–402. DOI: 10.1007/s00236-013-0187-1, https://doi.org/10.1007/s00236-013-0187-1
8. Clelia De Felice, Some conjectures on codes, arXiv:1611.04580 [cs.FL] (2016). arXiv: 1611.04580, https://arxiv.org/abs/1611.04580
9. Liang Zhang, K. P. Shum, Finite maximal codes and triangle conjecture, Discrete Mathematics 340(3) (2017) 541–549. DOI: 10.1016/j.disc.2016.10.008, https://doi.org/10.1016/j.disc.2016.10.008
10. Clelia De Felice, Finite maximal codes and factorizations of cyclic groups, Journal of Automata, Languages and Combinatorics 28(4) (2023) 287–338. DOI: 10.25596/jalc-2023-287, https://doi.org/10.25596/jalc-2023-287
11. Christophe Cordero, Factorizations of cyclic groups and bayonet codes, Journal of Automata, Languages and Combinatorics 29(1) (2024) 11–39. DOI: 10.25596/jalc-2024-011, https://doi.org/10.25596/jalc-2024-011
12. 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 1080 (2026), article 116024. DOI: 10.1016/j.tcs.2026.116024, https://doi.org/10.1016/j.tcs.2026.116024
13. Clelia De Felice, An enhanced property of factorizing codes, Theoretical Computer Science 340 (2005) 240–256. DOI: 10.1016/j.tcs.2005.03.022, https://doi.org/10.1016/j.tcs.2005.03.022 (introduces the recursive definition of a good arrangement, used as property P in the source paper)