Realizability of complete bayonet codes as slices $C_M(\omega)$ of finite maximal codes

For a finite maximal code $M$ containing the word $a^n$ and any word $\omega$, the Perrin–Schützenberger slice $C_M(\omega)$ (obtained by reducing the exponents of all $a^i\omega a^j\in M^*$ modulo $n$ and replacing $\omega$ by $b$) is an $n$-complete bayonet code: a set $X$ of exactly $n$ words $a^iba^j$, $0\le i,j<n$, such that $\{a^n\}\cup X$ is a code. Cordero's study of these objects (arXiv:2301.13566; J. Autom. Lang. Comb. 29(1):11–39, 2024) states as an explicit open gap that it is unknown whether this construction is surjective: does every $n$-complete bayonet code $X$ equal $C_M(\omega)$ for some finite maximal code $M$ containing $a^n$ and some word $\omega$? Only inclusion-type partial results (Hajós-type cases via Lam 1997 and Cordero's Theorem 6.2) are known, and none establishes exact realization. Prove that every $n$-cbc is realizable, or prove that some $n$-cbc is not.

Background

A code is a set $X$ of words over an alphabet $A$ in which every word admits at most one factorization into elements of $X$; codes are exactly the bases of free submonoids of the free monoid $A^*$, and they model uniquely decipherable encoding. A prefix code (resp. suffix code) is a set none of whose words is a prefix (resp. suffix) of another; prefix and suffix sets are automatically codes. A maximal code is a code not contained in any larger code, and most structural questions in the theory concern finite maximal codes. The central open problem of the field is Schützenberger's factorization conjecture (1965, documented in the Berstel–Perrin–Reutenauer monograph): every finite maximal code $M$ admits 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$; the best known approximation, due to Reutenauer, allows $P,S$ to be integer power series rather than finite sets.

Fix two letters $a,b\in A$. For a finite maximal code $M$, a classical result gives a unique integer $n\ge 1$, the order of the letter $a$, with $a^n\in M$. Perrin and Schützenberger associated to any code $M$ containing $a^n$ and any word $\omega\in A^*$ the slice $C_M(\omega)$: the set of words $a^iba^j$ with $0\le i,j<n$ for which some representative $a^{i+tn}\omega a^{j+un}$ ($t,u\ge 0$) lies in $M^*$, i.e. $a^i\omega a^j\in M^*$ with exponents reduced modulo $n$ and $\omega$ replaced by $b$. A finite code $M$ containing $a^n$ is maximal if and only if $|C_M(\omega)|=n$ for every word $\omega$ (see the monograph of Berstel, Perrin and Reutenauer). Thus every finite maximal code containing $a^n$ produces, for each $\omega$, a set of exactly $n$ words $a^iba^j$ with $0\le i,j<n$.

Codes contained in $a^*ba^*$ are called bayonet codes, and they are the subject of the triangle conjecture lineage: Perrin and Schützenberger conjectured that every bayonet code $Y$ satisfies the triangle inequality $|\{x\in Y:|x|\le k\}|\le k$ for all $k\ge 0$; Shor refuted this in 1985 with an explicit counterexample. The conjecture survives in a modern form — a bayonet code violating the inequalities cannot be included in any finite maximal code — which is likewise implied by the factorization conjecture. Zhang and Shum (2017) proved a structural precursor: the words $a^i\omega a^j\in M^*$ arrange into a matrix whose row and column index sets factor the cyclic group of order $n$; on this basis they proposed a stronger version of the triangle conjecture for finite maximal codes: for every finite maximal code $M$, word $\omega$, and $k\ge 0$, the set $\{a^i\omega a^j\in M^*:i+j<k\}$ has at most $k$ elements. This stronger inequality is proved only in special cases — Zhang and Shum for $n$ a prime, De Felice for $n$ a product of two primes, Cordero for cbc Hajós numbers — and remains open in general.

Cordero (2023/2024) introduced the class of $n$-complete bayonet codes: writing $[n]=\{0,\ldots,n-1\}$, an $n$-cbc is a set $X\subseteq a^{[n]}ba^{[n]}$ with $|X|=n$ such that $\{a^n\}\cup X$ is a code. Every slice $C_M(\omega)$ of a finite maximal code is an $n$-cbc, and the theory of factorizations of cyclic groups (pairs $(P,Q)$ of subsets of $\mathbb{Z}_n$ with each residue uniquely $p+q$; Krasner and Hajós factorizations are distinguished layered and constructible subclasses) extends to this setting. Known partial results are of inclusion type: Lam (1997) proved that a cbc of the form $a^Pba^Q$ with $(P,Q)$ a Hajós factorization is included in a finite maximal code, and Cordero's Theorem 6.2 shows that for cbc Hajós numbers $n$ (a product of at most three primes or of the form $p^kq$, which covers every $n<36$) the code $\{a^n\}\cup X$ is a composition of prefix and suffix codes, hence completable to a finite maximal code by the theorem of Restivo, Salemi and Sportelli; for other $n$ counterexamples to such composition exist. However, being included in a finite maximal code is weaker than being exactly a slice $C_M(\omega)$, and no construction or obstruction is known for the exact realization question in general.

Problem Statement

Let $A$ be an alphabet containing the letters $a$ and $b$, and write $[n]=\{0,1,\ldots,n-1\}$. An $n$-complete bayonet code ($n$-cbc) is a set $X\subseteq\{a^iba^j:i,j\in[n]\}$ with $|X|=n$ such that $\{a^n\}\cup X$ is a code. For a code $M$ containing $a^n$ and a word $\omega\in A^*$, define

$$C_M(\omega)=\{a^iba^j : i,j\in[n]\ \text{and}\ a^{i+tn}\,\omega\,a^{j+un}\in M^*\ \text{for some}\ t,u\ge 0\}.$$

For every finite maximal code $M$ containing $a^n$ and every $\omega\in A^*$, the slice $C_M(\omega)$ is an $n$-cbc. The question posed by Cordero (2024, Section 1): is the converse realization true — for every $n\ge 1$ and every $n$-cbc $X$, do there exist a finite maximal code $M$ containing $a^n$ and a word $\omega\in A^*$ such that $X=C_M(\omega)$? An $n$-cbc $X$ is non-realizable when no finite maximal code $M$ containing $a^n$ and no word $\omega\in A^*$ satisfy $X=C_M(\omega)$.

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, https://doi.org/10.25596/jalc-2024-011 (preprint arXiv:2301.13566, https://arxiv.org/abs/2301.13566)
2. Nguyen Huong Lam, Hajós factorizations and completion of codes, Theoretical Computer Science 182(1–2):245–256, 1997. DOI: 10.1016/S0304-3975(97)00032-7, https://doi.org/10.1016/S0304-3975(97)00032-7
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. Clelia De Felice, Finite maximal codes and factorizations of cyclic groups, arXiv:2202.09675, 2022, https://arxiv.org/abs/2202.09675 (published in Journal of Automata, Languages and Combinatorics 28, 2023)
6. Antonio Restivo, Sergio Salemi, and Tecla Sportelli, Completing codes, RAIRO – Theoretical Informatics and Applications 23(2):135–147, 1989. DOI: 10.1051/ita/1989230201351, https://doi.org/10.1051/ita/1989230201351
7. Jean Berstel, Dominique Perrin, and 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