Companion Hajós factorizations for finite maximal codes: extending De Felice's Ω(n)≤2 theorem, the existence of non-Hajós codes, and the Zhang–Shum pair correspondence

For a finite maximal code X containing the power a^n of a letter a, De Felice (2023) proved that when n has at most two prime factors, X admits a companion factorization of the cyclic group Z/nZ that is a Krasner (hence Hajós) factorization, which implies the triangle conjecture for the corresponding sets of words. Her paper leaves open whether such a Hajós companion factorization exists for every finite maximal code, whether the Hajós property of the associated factorizations implies the triangle property, whether any finite maximal code exists whose associated factorizations are not all Hajós (which would refute Schützenberger's factorization conjecture), whether all finite maximal completions of an includable code Y ∪ {a^n} with Ω(n)≤2 can be generated algorithmically, and how the Zhang–Shum pairs (P,Q) relate to the companion pairs (T,R).

Background

A (variable-length) code over a finite alphabet $A$ is the base of a free submonoid of the free monoid $A^*$ — equivalently, a set of words in which every concatenation of code words factors uniquely. A finite maximal code is a finite code that cannot be enlarged by adding another word without destroying unique decodability. The algebraic theory of such codes (see the monograph of Berstel, Perrin and Reutenauer, 2010) studies them through formal power series over the free monoid: with a finite language $X$ one associates its characteristic polynomial $\underline{X}$, and several central conjectures are statements about the identity $\underline{X}-1 = \underline{P}(\underline{A}-1)\underline{S}$. The oldest, the factorization conjecture of Schützenberger, asserts that every finite maximal code $X$ is positively factorizing, i.e. such an identity holds with the coefficients of $\underline{P},\underline{S}$ nonnegative. A landmark theorem of Reutenauer (1985) gives the weak form: for every finite maximal code the identity holds with $\underline{P},\underline{S}$ allowed arbitrary integer coefficients. A code is commutatively prefix if it is commutatively equivalent (word-for-word, up to permuting letters) to a prefix code, i.e. a code in which no word is a left factor of another; factorizing codes are commutatively prefix, so the factorization conjecture implies the commutative equivalence conjecture. A third conjecture, the triangle conjecture of Perrin and Schützenberger, concerns bayonet words $a^i b a^j$ (two powers of a letter $a$ around a single other letter $b$): after Shor's 1985 counterexample to the unrestricted version, it is conjectured that any finite bayonet code $X$ embeddable in a finite maximal code satisfies $\mathrm{Card}(X) \le \max\{|x| : x\in X\}$. All three conjectures remain open. A structural bridge to the theory of factorizations of cyclic groups was established by Zhang and Shum (2017): if $X$ is a finite maximal code with $a^n \in X$ (the order of the letter $a$ relative to $X$: every finite maximal code contains a unique power of each of its letters), $B = A\setminus\{a\}$, then for each $w \in B(a^*B)^*$ the set $X_w$ of words $a^i w a^j \in X^* \setminus [a^n(a^*wa^* \cap X^*) \cup (X^* \cap a^*wa^*)a^n]$ can be arranged in a matrix $(a^{r_{p,q}} w a^{v_{p,q}})$ whose rows $R_p$ and columns $T_q$ form factorizations of the cyclic group $\mathbb{Z}/n\mathbb{Z}$ of order $n$ — each element of $\mathbb{Z}/n\mathbb{Z}$ is uniquely $r+t$ with $r \in R$, $t \in T$. Here a pair $(T,R)$ of integer sets is a companion factorization of $X$ (De Felice 2023, Definition 4.1) when the product $\underline{a^T}\,\underline{X_w}\,\underline{a^R}$ is unambiguous and $\{\,a^{\overline{\ell_h}} w a^{\overline{\ell_m}} \mid a^{\ell_h} w a^{\ell_m} \in a^T X_w a^R\,\} = \{a^h w a^m : h,m \in \{0,\dots,n-1\}\}$ for every $w$ (here $a^{\ell_h} w a^{\ell_m}$ ranges over the words of $X_w$ that occur in $a^T X_w a^R$, and $\overline{\cdot}$ denotes reduction modulo $n$); every finite maximal code with $a^n \in X$ has one. The simplest factorizations of $\mathbb{Z}/n\mathbb{Z}$ are the Krasner factorizations, obtained as direct sums of interval sets along a chain of divisors of $n$; the Hajós factorizations, introduced via Hajós's (Sands-corrected) construction, are those built from a single chain of divisors $1=k_0 | k_1 | \cdots | k_s=n$ by alternately multiplying and composing interval factors, and they form a class strictly contained in the periodic factorizations. An integer $n$ is a Hajós number when $\mathbb{Z}/n\mathbb{Z}$ is a good cyclic group, i.e. all of its factorizations are periodic; the good cyclic groups are exactly $\mathbb{Z}/p^k q$, $\mathbb{Z}/p^2 q^2$, $\mathbb{Z}/p^2 qr$, $\mathbb{Z}/pqrs$ and their subgroups, so in particular — writing $\Omega(n)$ for the number of prime factors of $n$ counted with multiplicity — every $n$ with $\Omega(n) \le 2$ is a Hajós number. The Hajós–Sands construction produces a class of periodic factorizations of $\mathbb{Z}/n\mathbb{Z}$ that contains every factorization of a good group, so whenever $n$ is a Hajós number every factorization of $\mathbb{Z}/n\mathbb{Z}$ — and hence any companion factorization of $X$ — is automatically a Hajós factorization. De Felice (2023) re-proved the Zhang–Shum theorem via Reutenauer's weak factorization theorem and proved (Proposition 7.3) that for $\Omega(n) \le 2$ every finite maximal code $X$ with $a^n \in X$ has a companion factorization that is a Krasner factorization — which forces every $X_w$ to admit a good arrangement and to satisfy the triangle property (Corollary 7.1), and yields decidability of the inclusion problem for codes $Y \cup \{a^n\} \subseteq a^*Ba^* \cup a^*$ in this range. What fails beyond $\Omega(n) \le 2$, and what can be salvaged, is the subject of the present problem.

Problem Statement

Let $X$ be a finite maximal code over a finite alphabet $A$, let $a \in A$ with $a^n \in X$, let $B = A \setminus \{a\}$, and let $X_w$ and companion factorizations of $\mathbb{Z}/n\mathbb{Z}$ be as defined in the background. Determine the exact strength of the correspondence between finite maximal codes and factorizations of cyclic groups, by resolving the following linked questions posed in De Felice (2023) — Q2 in the Introduction, the others in Section 8: (Q1) Does every finite maximal code $X$ with $a^n \in X$ admit a companion factorization $(T,R)$ that is a Hajós factorization of $\mathbb{Z}/n\mathbb{Z}$? (For every Hajós number $n$ this is automatic — every factorization of $\mathbb{Z}/n\mathbb{Z}$ is then Hajós, in particular for $\Omega(n) \le 2$ — so the open content is the universal form for arbitrary $n$.) (Q2) If all the factorizations $(R_p,T_q)$ of $\mathbb{Z}/n\mathbb{Z}$ associated with the arrangements of a given $X_w$ are Hajós factorizations, does $X_w$ satisfy the triangle inequality — both the basic bound $\mathrm{Card}(X_w) \le \max\{|x| : x \in X_w\}$ and the strong (Zhang–Shum) cumulative bound $\forall k \ge 0\ \mathrm{Card}(\{a^r w a^v \in X_w : r+v \le k\}) \le k+1$? (Q3) Does there exist a finite maximal code $X$ such that for some $w \in B(a^*B)^*$ the factorizations of $\mathbb{Z}/n\mathbb{Z}$ associated with $X_w$ are not all Hajós factorizations? Exhibiting such a code would refute the factorization conjecture; proving none exists would show the Hajós obstruction is universal. (Q4) For $\Omega(n) \le 2$: given a finite code $Y \cup \{a^n\} \subseteq a^*Ba^* \cup a^*$ that is includable in some finite maximal code, is there an algorithm that produces every finite maximal code containing it — not merely one factorizing completion, as yielded by the current construction? (Q5) What is the precise structural relationship between the pairs of integer sets $(P,Q)$ of Zhang and Shum — where $a^P$ is a left set, $P = \{i \in \{0,\dots,n-1\} : y a^{2nL+i} \in X^*\}$ for some strongly right completable word $y$ (i.e. for every word $u$ there exists a word $v$ with $yuv \in X^*$), and $a^Q$ is a right set, $Q = \{k \in \{0,\dots,n-1\} : a^{k+2nL} x A^* \cap X^* \neq \emptyset\}$ for some generator word $x$ with $a^{j-i} \notin (X^*)^{-1}X^*$ for all $i < j$ in $Q$, where $L$ denotes the maximal length of a word of $X$ — and the companion pairs $(T,R)$ constructed via the Reutenauer-type decompositions used in De Felice's proof? The task is resolved by settling the central direction — the universality of Hajós companions, i.e. Q1 together with Q3, and its consequence for the triangle bounds Q2; the remaining directions Q4 and Q5 are related questions posed in the source, and a resolution of either of them is a partial result rather than a resolution of the task. Q2's basic and strong triangle inequalities are distinct, since a result for the basic version does not settle the strong version. These questions are separate open directions with a common objective: to establish (or break) the universality of Hajós companions, the main gate they open onto the factorization, commutative equivalence, and triangle conjectures.

References

1. 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:2202.09675, https://arxiv.org/abs/2202.09675
2. 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:2301.13566, https://arxiv.org/abs/2301.13566; publisher page: https://jalc.de/issues/2024/issue_29_1/jalc-2024-011-039.php
3. Liang Zhang, Kar-Ping 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
4. Jean Berstel, Dominique Perrin, Christophe Reutenauer, Codes and Automata, Encyclopedia of Mathematics and its Applications 129, Cambridge University Press (2010). DOI: 10.1017/CBO9781139195768, https://doi.org/10.1017/CBO9781139195768; ISBN 978-0-521-88831-8; zbMATH: https://zbmath.org/?q=an%3A5650750
5. Christophe Reutenauer, Noncommutative factorization of variable-length codes, Journal of Pure and Applied Algebra 36:167–186 (1985). DOI: 10.1016/0022-4049(85)90069-6, https://doi.org/10.1016/0022-4049(85)90069-6
6. 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