Does Shor's bayonet code have a finite completion? The triangle conjecture for finite maximal codes

In the algebraic theory of variable-length codes, a finite code has a finite completion when it is contained in some finite maximal code. Restivo (1977) showed that some finite codes have none, and Shor (1985) constructed a finite bayonet code (a code consisting of words $a^i b a^j$) with 16 words of length at most 15, so that its cardinality exceeds its maximum word length, refuting the unrestricted triangle conjecture of Perrin and Schützenberger. The surviving, still-open restricted conjecture states that every bayonet code embeddable in a finite maximal code satisfies the triangle inequalities; equivalently, no code on Shor's counterexample list — Shor's code in particular — is contained in any finite maximal code. The question sits at the junction of the theory of codes, the factorization theory of cyclic groups (Hajós, Krasner, Rédei properties), and Schützenberger's factorization conjecture: an explicit finite completion of a triangle-violating bayonet code would simultaneously refute the triangle conjecture and the factorization conjecture, while a proof of non-existence would establish the restricted triangle conjecture for this class.

Background

A (variable-length) code over a finite alphabet $A$ is a set $X\subseteq A^*$ of words such that every word admits at most one factorization into elements of $X$; equivalently, $X$ is the basis of a free submonoid of the free monoid $A^*$. A code is maximal when it is contained in no larger code over $A$. Every finite code is contained in some (generally infinite) maximal code, but Restivo (1977) exhibited finite codes that are contained in no finite maximal code; a finite code $X$ is said to have a finite completion when some finite maximal code $M$ satisfies $X\subseteq M$. A prefix code is one in which no word is a prefix of another (such sets are automatically codes), and suffix codes are defined symmetrically.

A bayonet code is a code $X\subseteq a^*ba^*$ for two distinct letters $a,b\in A$, i.e. all of its words have the form $a^i b a^j$. A finite set of words is commutatively prefix when it is commutatively equivalent to some prefix code, in the sense that letters may be reordered within words so that the resulting set of words is prefix. Perrin and Schützenberger proved that a bayonet code is commutatively prefix if and only if it satisfies the triangle inequalities

$\mathrm{Card}\{x\in X : |x|\le k\}\le k \quad\text{for all } k\ge 0,$

which express that the lattice points of the commutative image of $X$ in $\mathbb{N}^2$ lie under a staircase of slope $-1$, and they conjectured that every finite bayonet code is commutatively prefix. Shor (1985) refuted this unrestricted conjecture with the explicit bayonet code

$X=\{b, ba, ba^7, ba^{13}, ba^{14}, a^3b, a^3ba^2, a^3ba^4, a^3ba^6, a^8b, a^8ba^2, a^8ba^4, a^8ba^6, a^{11}b, a^{11}ba, a^{11}ba^2\}$

of 16 words, each of length at most 15, so that $\mathrm{Card}\{x\in X:|x|\le 15\}=16>15$; from 2019 on, Cordero generated further such non-commutatively-prefix bayonet codes by computer. The conjectures of Schützenberger's school were therefore restricted to finite maximal codes and their subsets: the (restricted) triangle conjecture asserts that every bayonet code which can be embedded in a finite maximal code satisfies the triangle inequalities. Since any triangle-violating bayonet code that is embedded in a finite maximal code would falsify this conjecture, and would also falsify Schützenberger's factorization conjecture (which asserts that the characteristic polynomial of every finite maximal code factors as $\underline{M}-1=P\,(\underline{A}-1)\,S$ with finite sets $P,S$ of words, and which implies the triangle conjecture), the restricted triangle conjecture is exactly the statement that codes on Shor's counterexample list have no finite completion.

The standard finite obstructions to completion come from factorizations of cyclic groups. A pair $(P,Q)$ of subsets of integers is a factorization of size $n$ of the cyclic group $\mathbb{Z}_n$ when every residue class modulo $n$ is uniquely $p+q$ with $p\in P$, $q\in Q$ (necessarily $|P|\cdot|Q|=n$). Restivo, Salemi and Sportelli (1989) proved that if a finite maximal code $M$ contains both $b$ and $a^n$, the pairs of exponent sets of the words $a^k b$ and $b a^k$ in $M$ form such a factorization; consequently, a code such as Restivo's $\{a^5,ab,b,baa\}$ can have no finite completion precisely because no factorization of size 5 contains the required small subsets. Szabó (2006) pursued this route systematically using group-factorization classification theory: a finite abelian group has the Hajós property when in every factorization at least one of the two factors is periodic (invariant under a nonzero translation), and has the Rédei property when in every factorization one of the factors contains a complete coset of some nontrivial subgroup; Szabó gave criteria of this type for deciding non-existence of finite completions of binary codes and posed the factorization non-existence 'Conjecture 1' ($\mathbb{Z}_n=A+B$ with $0,1\in A$ and $0,p,k\in B$ should not exist) together with the question of Shor's code. Sands (2007) then constructed factorizations of the shape forbidden by the Restivo–Salemi–Sportelli non-existence conjecture, showing that the finite-factorization obstruction program cannot decide the completion question in general: since factorizations with prescribed small subsets do exist, each candidate obstruction must be checked against the factorizations that actually exist. Modern work therefore attacks the problem through structural properties of finite maximal codes: for a finite maximal code $X$ of order $n$ of the letter $a$ (meaning $a^n\in X$ for the least such $n$), Zhang and Shum (2017) proved that the words $a^i w a^j\in X$ around any fixed word $w$ arrange into matrices whose row/column exponent sets factorize $\mathbb{Z}_n$, and proposed a stronger form of the triangle inequalities; De Felice (2022) re-proved this via Hajós factorizations (a recursively periodic class, generated by the classical Hajós–Krasner construction) and deduced decidability of the inclusion question for codes $Y\cup a^n$ when $n$ has at most two prime factors; Cordero (2023) verified the triangle conjecture for complete bayonet codes of Hajós-type orders (products of at most three primes or $p^k q$) and proved a conjectured divisibility constraint on the size of any potential counterexample. The general inclusion problem — given a finite code, decide whether it is contained in a finite maximal code — remains open, as do the factorization conjecture, the commutative equivalence conjecture, and the triangle conjecture itself.

Problem Statement

Determine whether a finite bayonet code that violates the triangle inequalities can be contained in a finite maximal code. Concretely: for Shor's 1985 counterexample code $X=\{b,ba,ba^7,ba^{13},ba^{14},a^3b,a^3ba^2,a^3ba^4,a^3ba^6,a^8b,a^8ba^2,a^8ba^4,a^8ba^6,a^{11}b,a^{11}ba,a^{11}ba^2\}\subset a^*ba^*$ (16 words of length at most 15), or for any explicit non-commutatively-prefix bayonet code (one with $\mathrm{Card}\{x\in X:|x|\le k\}>k$ for some $k$), decide whether there exists a finite maximal code $M$ over the same alphabet with $X\subseteq M$. The answer must resolve the alternative in full generality for this class: either (a) prove the restricted triangle conjecture — every bayonet code embedded in a finite maximal code satisfies the triangle inequalities, so that Shor-type codes have no finite completion; or (b) exhibit, for some explicit triangle-violating bayonet code $X$, a finite maximal code $M$ containing it, thereby refuting the triangle conjecture and, with it, Schützenberger's factorization conjecture.

References

1. Sándor Szabó, "Completing codes and the Rédei property of groups", Theoretical Computer Science 359, issues 1–3 (2006), pages 449–454. DOI: 10.1016/j.tcs.2006.02.002. URL: https://doi.org/10.1016/j.tcs.2006.02.002
2. Peter W. Shor, "A counterexample to the triangle conjecture", Journal of Combinatorial Theory, Series A 38, issue 1 (1985), pages 110–112. DOI: 10.1016/0097-3165(85)90032-9. URL: https://doi.org/10.1016/0097-3165(85)90032-9
3. Antonio Restivo, "On codes having no finite completions", Discrete Mathematics 17, issue 3 (1977), pages 309–316. DOI: 10.1016/0012-365X(77)90164-9. URL: https://doi.org/10.1016/0012-365X(77)90164-9
4. A. Restivo, S. Salemi, T. Sportelli, "Completing codes", RAIRO – Theoretical Informatics and Applications 23, issue 2 (1989), pages 135–147. DOI: 10.1051/ita/1989230201351. URL: https://doi.org/10.1051/ita/1989230201351
5. Nguyen Huong Lam, "Hajós factorizations and completion of codes", Theoretical Computer Science 182, issues 1–2 (1997), pages 245–256. DOI: 10.1016/S0304-3975(97)00032-7. URL: https://doi.org/10.1016/S0304-3975(97)00032-7
6. Clelia De Felice, "An application of Hajós factorizations to variable-length codes", Theoretical Computer Science 164, issues 1–2 (1996), pages 223–252. DOI: 10.1016/0304-3975(95)00223-5. URL: https://doi.org/10.1016/0304-3975(95)00223-5
7. A. D. Sands, "A question concerning the factorization of cyclic groups", International Journal of Algebra and Computation 17, issue 8 (2007), pages 1573–1575. DOI: 10.1142/S0218196707004293. URL: https://doi.org/10.1142/S0218196707004293
8. Patric R. J. Östergård, Sándor Szabó, "Elementary p-groups with the Rédei property", International Journal of Algebra and Computation 17, issue 1 (2007), pages 171–178. DOI: 10.1142/S0218196707003536. URL: https://doi.org/10.1142/S0218196707003536
9. Clelia De Felice, "Some conjectures on codes", arXiv:1611.04580 (2016). URL: https://arxiv.org/abs/1611.04580
10. Liang Zhang, K. P. Shum, "Finite maximal codes and triangle conjecture", Discrete Mathematics 340, issue 3 (2017), pages 541–549. DOI: 10.1016/j.disc.2016.10.008. URL: https://doi.org/10.1016/j.disc.2016.10.008
11. 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 (2019), pages 409–420. DOI: 10.1007/978-3-030-13435-8_30. URL: https://doi.org/10.1007/978-3-030-13435-8_30
12. Clelia De Felice, "Finite maximal codes and factorizations of cyclic groups", Journal of Automata, Languages and Combinatorics 28, issue 4 (2023), pages 287–338; preprint arXiv:2202.09675 (2022). DOI: 10.25596/jalc-2023-287. URL: https://doi.org/10.25596/jalc-2023-287 (preprint: https://arxiv.org/abs/2202.09675)
13. Christophe Cordero, "Factorizations of cyclic groups and bayonet codes", Journal of Automata, Languages and Combinatorics 29, issue 1 (2024), pages 11–39; preprint arXiv:2301.13566 (2023). DOI: 10.25596/jalc-2024-011. URL: https://doi.org/10.25596/jalc-2024-011 (preprint: https://arxiv.org/abs/2301.13566)