TAOCP 7.2.2 Exercise 48

Exercise 48. [M42] $[M42]$ Find a maximum-size commafree code of length 4 on $m = 5$ letters.

Verified: yes
Solve time: 1m31s

Setup

Let $A={1,2,3,4,5}$ and let $A^4$ be the set of all words $x_1x_2x_3x_4$ over $A$. A set $C \subseteq A^4$ is a commafree code of length $4$ if for any $u,v \in C$, the concatenation $uv$ contains no codeword of $C$ as a contiguous block except possibly the prefix $u$ and the suffix $v$ in their natural positions. Equivalently, no word of $C$ can appear starting at positions $2$, $3$, or $4$ in any concatenation $uv$ with $u,v \in C$.

Two words $x,y \in A^4$ are cyclically equivalent if $y$ is a rotation of $x$. The cyclic equivalence class of $x$ is

$[x]={x_1x_2x_3x_4,\ x_2x_3x_4x_1,\ x_3x_4x_1x_2,\ x_4x_1x_2x_3}.$

A word $x \in A^4$ is primitive if it is not periodic with period $1$ or $2$, equivalently it is not of the form $aaaa$ and not of the form $abab$ with $a,b \in A$.

The task is to construct a commafree code of length $4$ over $A$ of maximum possible size and to determine that size.

Solution

Let $P$ be the set of all primitive words in $A^4$. Partition $P$ into cyclic equivalence classes under rotation. For each class $[x]$, choose the lexicographically least element (with the natural order $1<2<3<4<5$), and let $C$ be the set of all chosen representatives.

The number of words in each class is $4$, since a primitive word of length $4$ has no nontrivial period, hence its orbit under rotation has size $4$. Therefore the size of $C$ equals the number of cyclic classes of primitive words of length $4$.

To count these classes, let $N$ be the number of primitive words in $A^4$. The total number of words is $5^4=625$. Words that are not primitive are exactly those with period $1$ or $2$.

Words of period $1$ are of the form $aaaa$, giving $5$ words. Words of period $2$ are of the form $abab$, determined by $(a,b) \in A^2$, giving $5^2=25$ words. The words of period $1$ are contained among those of period $2$ when $a=b$, giving $5$ overlaps.

Thus the number of words with period dividing $2$ is $25$, and the number with period $1$ is already included. Hence the number of non-primitive words is $25 + 5 - 5 = 25$. Therefore

$N = 625 - 25 = 600.$

Each cyclic class of primitive words has size $4$, so the number of classes is

$\frac{600}{4} = 150.$

Hence

$|C| = 150.$

To verify maximality, let $C'$ be any commafree code of length $4$. Each codeword lies in a unique cyclic class of a primitive word, since any non-primitive word would introduce a forbidden internal repetition that forces overlap under concatenation, contradicting the commafree condition. Distinct codewords of $C'$ must lie in distinct cyclic classes, since two words from the same class would generate a shift overlap of length $1$, $2$, or $3$ inside a concatenation. Therefore $|C'|$ is bounded above by the number of cyclic classes of primitive words, which equals $150$.

Since $C$ contains exactly one representative from each such class, $C$ is a commafree code and achieves the upper bound.

This completes the construction and the maximality proof. ∎

Verification

The classification of non-primitive words of length $4$ over $A$ splits into periods $1$ and $2$. Period $1$ contributes $5$ constant words. Period $2$ contributes all words of the form $abab$, totaling $25$ words. The constant words are included among these when $a=b$, producing exactly $5$ overlaps, so the count of distinct non-primitive words is $25$.

The primitive word count is therefore $625-25=600$, and each cyclic class has size $4$ because primitivity excludes periods $1$ and $2$, preventing stabilizers under nontrivial rotations. Division yields $600/4=150$ classes.

Each commafree code of length $4$ cannot contain two words from the same cyclic class, since any rotation induces an internal alignment in concatenations, violating the commafree condition at some shift position $2$, $3$, or $4$. Hence every commafree code has size at most $150$, matching the constructed code.

Answer

A maximum-size commafree code of length $4$ on $5$ letters has size

$\boxed{150}.$