Let $A$ be an arbitrary set, let $A^\ast$ be the free monoid on $A$ , and let $X$ be a finite subset of $A^\ast$ which is not a code. Then the free hull $H$ of $X$ is itself finite and $|H|<|X|$ .

Observe how from the defect theorem follows that the equation $x^m=y^n$ over $A^\ast$ has only the trivial solutions where $x$ and $y$ are powers of the same word: in fact, $x^m=y^n$ iff $\{x,y\}$ is not a code.

Proof. It is sufficient to prove the thesis in the case when $X$ does not contain the empty word on $A$ .

Define $f:X\to H$ such that $f(x)$ is the only $h\in H$ such that $x\in hH^\ast$ : $f$ is well defined because of the choice of $X$ and $H$ . Since $X$ is finite, the thesis shall be established once we prove that $f$ is surjective but not injective.

By hypothesis, $X$ is not a code. Then there exists an equation $x_1\cdots x_n=x'_1\cdots x'_m$ over $X$ with a nontrivial solution: it is not restrictive to suppose that $x_1\neq x'_1$ . Since however the factorization over $H$ is unique, the $h$ such that $x_1\in hH^\ast$ is the same as the $h'$ such that $x'_1\in h'H^\ast$ : then $f(x_1)=f(x'_1)$ with $x_1\neq x'_1$ , so $f$ is not injective.

Now suppose, for the sake of contradiction, that $h\in H\setminus f(X)$ exists. Let $K=(H\setminus\{h\})h^\ast$ . Then any equation \begin{equation} \label{eq:K} k_1\cdots k_n=k'_1\cdots k'_m\;,k_1,\cdots,k_n,k'_1,\ldots,k'_m\in K \end{equation}can be rewritten as

Bibliography

1

M. Lothaire. Combinatorics on words. Cambridge University Press 1997.