Deciding embeddability of finite codes into finite maximal codes, and the open instance of Shor's counterexample code

A finite (variable-length) code is a set of words over a finite alphabet in which every concatenation factors uniquely; a maximal code is one that cannot be enlarged within the class of codes over the same alphabet. The inclusion problem, open since Restivo (1977) exhibited finite codes that lie in no finite maximal code, asks to decide whether a given finite code can be embedded in (completed by) a finite maximal code. Its most famous open instance is Shor's 16-word binary code of 1985, the counterexample to the triangle conjecture and the only long-standing example of a finite code not commutatively equivalent to any prefix code: whether it is contained in a finite maximal code is unknown, and an affirmative answer would refute both the commutative equivalence conjecture and the factorization conjecture for finite maximal codes. Both the general decision problem and the Shor-code instance remain open as of 2026; decidability is known only for special bayonet-code families (uniform bayonet codes, and complete bayonet codes whose order is a cbc Hajós number, i.e. a product of at most three primes or of the form $p^{k}q$).

Background

Fix a finite alphabet $A$ and write $A^{*}$ for the free monoid of all finite words over $A$, with concatenation and empty word $1$. A subset $C\subseteq A^{*}$ is a (variable-length) code if every word of the submonoid $C^{*}$ obtained by concatenating codewords factors uniquely into codewords; equivalently, $C$ is the base of a free submonoid of $A^{*}$. A prefix code is a code in which no word is a proper left factor of another. A code over $A$ is maximal if no further word can be added while remaining a code over $A$; by a classical criterion, a finite code over $A$ is maximal exactly when it is complete, i.e. every word of $A^{*}$ occurs as a factor of some word of $C^{*}$. Finite maximal codes are the central objects of the algebraic theory of codes initiated by Schützenberger, and three conjectures about their structure have stood since the late 1970s (as recounted in the surveys of De Felice, arXiv:1611.04580 and arXiv:2202.09675): the factorization conjecture (for every finite maximal code $C$ there exist finite sets $P,S\subseteq A^{*}$ with $\underline{C}-1=\underline{P}(\underline{A}-1)\underline{S}$, where $\underline{X}$ denotes the formal sum of the elements of $X$); the commutative equivalence conjecture (every finite maximal code is commutatively equivalent to a prefix code, where two finite sets are commutatively equivalent if some bijection matches words having the same number of occurrences of each letter); and the triangle conjecture for bayonet codes — codes whose words all have the form $a^{i}ba^{j}$ — stating that such a code $X$ satisfies $|X\cap A^{\le n}|\le n$ for every $n$, which for bayonet codes is equivalent to being commutatively equivalent to a prefix code.

Shor (1985) refuted the unrestricted conjectures with a single 16-word bayonet code over $\{a,b\}$, all of whose words have length at most 15, so that $|X\cap A^{\le 15}|=16>15$; this code is therefore not commutatively equivalent to any prefix code, and the conjectures were then restricted to the class of codes embeddable in finite maximal codes: the modern triangle conjecture says that a bayonet code that is not commutatively prefix (that is, not commutatively equivalent to any prefix code) cannot be included in any finite maximal code.

The embeddability question itself, however, predates this: Restivo (1977) constructed a finite code that is contained in no finite maximal code at all, so having a finite maximal completion is a genuine, non-universal property of finite codes, and deciding it — the inclusion problem, whose positive resolution is called the inclusion conjecture in De Felice's surveys — is open.

The question is sharp because of a classical link between finite maximal codes and factorizations of cyclic groups: if a finite maximal code contains a word $b$ and a power $a^{n}$ of another letter, the residue classes of the exponents of the words $a^{k}b$ and $ba^{k}$ it contains form a factorization of $\mathbb{Z}/n\mathbb{Z}$. Building on this, Zhang and Shum (2017) proved that for a finite maximal code containing $a^{n}$, the words of the sets $X_{w}$ of suitable elements $a^{i}wa^{j}$ can be arranged in matrices whose row and column index sets factor $\mathbb{Z}/n\mathbb{Z}$, and proposed a stronger form of the triangle conjecture. The key structural interplay is: if a finite maximal code $M$ is commutatively equivalent to a prefix code, then $|M\cap a^{*}ba^{*}\cap A^{\le n}|\le n$ for all $n$; hence any finite maximal code containing Shor's code — whose 16 words all lie in $a^{*}ba^{*}\cap A^{\le 15}$ — would fail to be commutatively prefix, refuting the commutative equivalence conjecture, and would also refute the factorization conjecture since every code satisfying the factorization identity is commutatively prefix.

Partial results known: De Felice (arXiv:2202.09675) gave a simpler proof of the Zhang–Shum structural theorem, proved the triangle conjecture for finite maximal codes containing $a^{pq}$ with $p,q$ prime, and proved that the inclusion question is decidable for uniform bayonet codes of the form $Y\cup\{a^{n}\}$ with $n$ a product of at most two primes (uniform meaning that every letter of the code other than the single powers of $a$ occurs in equally many codewords); Cordero (arXiv:2301.13566) developed the theory of complete bayonet codes — bayonet codes $X\cup\{a^{n}\}$ that are already complete in the sense above — verified the triangle conjecture for all orders that are products of at most three primes or of the form $p^{k}q$, and used computer exploration to certify explicit small codes as non-embeddable. None of this touches the general inclusion problem or the Shor instance.

Problem Statement

The problem has two facets sharing one objective — determining exactly when a finite code admits a finite maximal completion. Facet (1) concerns an arbitrary finite code; facet (2) is the instance of Shor's code, so a resolution of (1) settles (2), whereas a resolution of (2) alone does not decide (1).

(1) Inclusion problem (general). Given an arbitrary finite code $X$ over a finite alphabet $A$, decide whether there exists a finite maximal code $M$ over the same alphabet $A$ such that $X\subseteq M$.

(2) Flagship instance (Shor's code). Decide facet (1) for the specific code

$$C_{\mathrm{Shor}}=\{ba^{i}\mid i\in\{0,1,7,13,14\}\}\cup\{a^{i}ba^{j}\mid i\in\{3,8\},\ j\in\{0,2,4,6\}\}\cup\{a^{11}ba^{j}\mid j\in\{0,1,2\}\}$$

over the binary alphabet $\{a,b\}$: either exhibit a finite maximal code over $\{a,b\}$ containing $C_{\mathrm{Shor}}$, or prove that none exists. Known necessary conditions on any completion — the order of the letter $a$ in the completion (the least $k$ with $a^{k}$ in the code) must be a multiple of $330$, and the associated cyclic-group factorization constraints must be satisfiable — are established facts about this instance, not restrictions on the sought answer.

An affirmative algorithmic answer to (1) settles (2) mechanically, whereas a proof that (1) is undecidable does not settle the specific instance (2); the instance (2) may also be settled alone, e.g. by an explicit finite witness. No restriction on alphabet size, code size, word length, or code class is part of the problem: the input of facet (1) is an arbitrary finite code.

References

1. Antonio Restivo. On codes having no finite completions. Discrete Mathematics 17(3) (1977) 309–316. doi:10.1016/0012-365X(77)90164-9, https://doi.org/10.1016/0012-365X(77)90164-9
2. Peter W. Shor. A counterexample to the triangle conjecture. Journal of Combinatorial Theory, Series A 38(1) (1985) 110–112. doi:10.1016/0097-3165(85)90032-9, https://doi.org/10.1016/0097-3165(85)90032-9
3. 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
4. Clelia De Felice. Some conjectures on codes. arXiv:1611.04580 (2016). https://arxiv.org/abs/1611.04580
5. Christophe Cordero. A Note with Computer Exploration on the Triangle Conjecture. Language and Automata Theory and Applications (LATA 2019), Lecture Notes in Computer Science, Springer (2019) 409–420. doi:10.1007/978-3-030-13435-8_30, https://doi.org/10.1007/978-3-030-13435-8_30 (full text at https://hal.science/hal-03682699)
6. Clelia De Felice. Finite maximal codes and factorizations of cyclic groups. arXiv:2202.09675 (2022); 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. https://arxiv.org/abs/2202.09675
7. Christophe Cordero. Factorizations of Cyclic Groups and Bayonet Codes. arXiv:2301.13566 (2023); 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. https://arxiv.org/abs/2301.13566
8. Dean Kraizberg. A Weak Structural Form of Commutative Equivalence in Finite Codes. arXiv:2603.27656 (2026). https://arxiv.org/abs/2603.27656
9. 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) 116024. doi:10.1016/j.tcs.2026.116024, https://doi.org/10.1016/j.tcs.2026.116024