Complete bayonet codes and finite maximal codes: the strong triangle conjecture beyond Hajós numbers and the realization problem

The 2023/2024 paper 'Factorizations of Cyclic Groups and Bayonet Codes' by Christophe Cordero studies $n$-complete bayonet codes ($n$-cbc) — finite codes of the form $X \cup \{a^n\}$ with $X \subseteq a^{[n]}ba^{[n]}$ and $|X| = n$ — and connects them to factorizations of cyclic groups. It proves the strong triangle conjecture (every $n$-cbc satisfies the length inequality $|\{x \in X : |x| \le k\}| \le k$) when $n$ is a 'cbc Hajós number' (a product of at most three primes or of the form $p^kq$), but leaves the general case open and deliberately declines to conjecture it. Three linked questions remain open: the strong triangle conjecture for arbitrary $n$; whether every $n$-cbc arises as $C_M(\omega)$ for a finite maximal code $M$; and whether every finite maximal code bordered by a Krasner factorization satisfies Schützenberger's factorization conjecture (the converse of Proposition 4.5).

Background

A (variable-length) code over a finite alphabet $A$ is any set $X$ of words such that every word of the free monoid $A^*$ (the set of all words over $A$) admits at most one factorization into elements of $X$; codes are exactly the bases of the free submonoids of $A^*$. A prefix code (resp. suffix code) is a set none of whose words is a prefix (resp. suffix) of another. A finite code is maximal when it is not contained in a larger code, and the structure of finite maximal codes is governed by classical open conjectures. For a finite maximal code $M$ there is a unique integer $n \ge 1$ with $a^n \in M$, called the order of the letter $a$, and following Perrin–Schützenberger one attaches to each word $\omega$ the set $C_M(\omega) = \{a^{i \bmod n}ba^{j \bmod n} : a^i\omega a^j \in M^*\}$, where $M^*$ is the submonoid generated by $M$; Theorem 1.4 of the source paper recalls that maximality of a finite code $M$ containing $a^n$ is equivalent to $|C_M(\omega)| = n$ for every $\omega$. A bayonet code is a code contained in $a^*ba^*$ for two distinct letters $a$, $b$, and an $n$-complete bayonet code ($n$-cbc) is a set $X \subseteq a^{[n]}ba^{[n]}$ with $|X| = n$ such that $\{a^n\} \cup X$ is a code, where $[n] = \{0,\dots,n-1\}$; 'complete' reflects that such a set cannot be enlarged within $a^*ba^*$. By the maximality criterion, $C_M(\omega)$ is always an $n$-cbc. In 1977 Perrin and Schützenberger conjectured that every bayonet code $X$ satisfies $|\{x \in X : |x| \le k\}| \le k$ for all $k$ (the triangle property); Shor refuted this in 1985 with an explicit counterexample. The surviving forms are the modern triangle conjecture — a bayonet code violating the triangle property cannot be included in any finite maximal code — and the stronger 2017 conjecture of Zhang and Shum, that $|\{a^i\omega a^j \in M^* : i + j < k\}| \le k$ for every finite maximal code $M$, every word $\omega$, and every $k$. Both are implied by Schützenberger's factorization conjecture from the 1960s (recorded, e.g., in the survey of De Felice and in the source paper): for every finite maximal code $M$ there exist finite sets $P, S \subseteq A^*$ with $\underline{M} - 1 = \underline{P}(\underline{A} - 1)\underline{S}$, where $\underline{X}$ denotes the formal sum of the elements of $X$, so such identities live in the algebra of formal power series over $A^*$. Cordero's paper transfers tools from the theory of factorizations of cyclic groups — a factorization of $\mathbb{Z}/n\mathbb{Z}$ is a pair $(P,Q)$ of subsets such that every residue class is uniquely $p + q$; a set is periodic when it is a union of cosets of a nontrivial subgroup, and a Hajós factorization is defined recursively as one of size $1$ or one in which a factor is periodic and the corresponding reduced factorization (obtained by dividing that factor by its period) is again a Hajós factorization; a Krasner factorization of size $n = t_1\cdots t_k$ ($t_i > 1$) is one obtained by the alternating-block construction $U = \sum_{2 \mid i} t_1\cdots t_{i-1}[t_i]$ (even $i$), $V = \sum_{2 \nmid i} t_1\cdots t_{i-1}[t_i]$ (odd $i$) — to the cbc setting, via the notions of compatible and stable sets of $n$-cbc (sets of cbc closed under the paper's composition operation $X \circ_r Y$ on cbc, stable meaning closed under all such compositions and compatible meaning all such compositions of elements are again cbc) and of a factorization $(P,Q)$ bordering such a set (the formal-series identity $\underline{a^P}\,\underline{X}\,\underline{a^Q} \equiv_n \underline{a^{[n]}b}\,\underline{a^{[n]}}$ holding for each element $X$ of the set, where $\equiv_n$ sets $a^n$ equal to the empty word). The paper proves that the strong triangle conjecture — every $n$-cbc satisfies the triangle property — holds whenever $n$ is a cbc Hajós number (a product of at most three primes, or of the form $p^kq$ with $k \ge 0$ and $p$, $q$ prime; in particular for all $n < 36$), and that for other $n$ there exist $n$-cbc that are not of Hajós type, so the group-factorization route breaks down exactly beyond those $n$. Proposition 4.5 shows that a finite maximal code satisfying the factorization conjecture has its family $C_M$ bordered by a Krasner factorization, and Theorem 7.2 proves a multiplicative-residue invariance (Conjecture 7.1 of Cordero's 2019 LATA paper) yielding divisibility lower bounds: e.g., Example 7.3 shows that if the specific code $T$ displayed there — one of the four smallest known bayonet codes that are not commutatively prefix (a code is commutatively prefix if some permutation of the letters within each of its words turns it into a prefix code) — sits in an $n$-cbc, then $36$ divides $n$; a similar argument is noted for the other such codes but not carried out.

Problem Statement

Resolve the complete-bayonet-code frontier left open by Cordero (arXiv:2301.13566; Journal of Automata, Languages and Combinatorics 29(1):11–39, 2024). The common objective is to determine the exact relationship between the combinatorics of $n$-complete bayonet codes and finite maximal codes, which comprises three linked questions. Bayonet codes and $n$-cbc involve two distinguished letters $a$ and $b$ (they are contained in $a^*ba^*$), but the finite maximal codes $M$ occurring in questions (2) and (3) are not restricted to a binary alphabet: they range over any alphabet $A$ containing $a$ and $b$, and the factorization-conjecture identity in question (3) is over $M$'s own alphabet. Throughout, $[n] = \{0,\dots,n-1\}$, $A^*$ denotes the set of all words over the alphabet $A$, $M^*$ denotes the submonoid of all concatenations of words of $M$, a code is a set of words in which no word admits two different factorizations into elements of the set, and for a finite set of words $W$ the symbol $\underline{W}$ denotes the formal sum of its elements, so identities between such sums are identities of formal power series. A bayonet code is a code contained in $a^*ba^*$, and an $n$-complete bayonet code ($n$-cbc) is a set $X \subseteq a^{[n]}ba^{[n]}$ with $|X| = n$ such that $\{a^n\} \cup X$ is a code.

(1) Strong triangle conjecture, general $n$: decide whether every $n$-cbc $X$ satisfies the triangle property $|\{x \in X : |x| \le k\}| \le k$ for all $k \in [n]$. This is proved only when $n$ is a cbc Hajós number (a product of at most three primes or of the form $p^kq$ with $k \ge 0$ and $p$, $q$ prime, which covers every $n < 36$); settle the remaining $n$, either by a proof or by an explicit $n$-cbc counterexample.

(2) Realization: is every $n$-cbc $X$ of the form $X = C_M(\omega)$ for some finite maximal code $M$ containing $a^n$ and some word $\omega$, where $C_M(\omega) = \{a^{i \bmod n}ba^{j \bmod n} : a^i\omega a^j \in M^*\}$? (One direction is known: $C_M(\omega)$ is always an $n$-cbc; and cbc of the special form $a^Pba^Q$ with $(P,Q)$ a Hajós factorization of $\mathbb{Z}/n\mathbb{Z}$ are known to be included in a finite maximal code, by Lam.)

(3) Converse of Proposition 4.5: an ordered pair $(P,Q)$ of subsets of $\mathbb{Z}$ is a factorization of size $n$ when every $k \in [n]$ is uniquely $p + q$ in $\mathbb{Z}/n\mathbb{Z}$ (so $n = |P| \cdot |Q|$), and it borders an $n$-cbc $X$ when the formal-series identity $\underline{a^P}\,\underline{X}\,\underline{a^Q} \equiv_n \underline{a^{[n]}b}\,\underline{a^{[n]}}$ holds, where $\equiv_n$ sets $a^n$ equal to the empty word; a Krasner factorization of size $n = t_1\cdots t_k$ ($t_i > 1$) is the factorization $(U,V)$ or $(V,U)$ with $U = \sum_{2 \mid i} t_1\cdots t_{i-1}[t_i]$ (even $i$) and $V = \sum_{2 \nmid i} t_1\cdots t_{i-1}[t_i]$ (odd $i$). Proposition 4.5 of the source shows that a finite maximal code satisfying the factorization conjecture has its family $C_M = \{C_M(\omega)\}$ bordered by a Krasner factorization; the open question is the converse: does every finite maximal code whose family $C_M$ is bordered by a Krasner factorization satisfy the factorization conjecture, i.e., admit finite sets $P, S \subseteq A^*$ with $\underline{M} - 1 = \underline{P}(\underline{A} - 1)\underline{S}$?

References

1. 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; preprint arXiv:2301.13566. https://doi.org/10.25596/jalc-2024-011 (publisher page: https://jalc.de/issues/2024/issue_29_1/jalc-2024-011-039.php)
2. 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; preprint arXiv:2202.09675. https://doi.org/10.25596/jalc-2023-287
3. Peter 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
4. Liang Zhang and 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
5. Dominique Perrin and Marcel-Paul Schützenberger, Un problème élémentaire de la théorie de l'information, in Théorie de l'information, développements récents et applications, Colloque international CNRS 276, Cachan, 1977, pp. 249–260 (published 1978), zbMATH Zbl 0483.94028. https://zbmath.org/3760085
6. 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 11417, Springer, pp. 409–420, 2019, DOI 10.1007/978-3-030-13435-8_30; zbMATH record 7139938 (Zbl 1425.68328). https://doi.org/10.1007/978-3-030-13435-8_30