# defect theorem

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^{\prime}_{1}\cdots x^{\prime}_{m}$ over $X$ with a nontrivial solution: it is not restrictive to suppose that $x_{1}\neq x^{\prime}_{1}$. Since however the factorization over $H$ is unique, the $h$ such that $x_{1}\in hH^{\ast}$ is the same as the $h^{\prime}$ such that $x^{\prime}_{1}\in h^{\prime}H^{\ast}$: then $f(x_{1})=f(x^{\prime}_{1})$ with $x_{1}\neq x^{\prime}_{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

 $k_{1}\cdots k_{n}=k^{\prime}_{1}\cdots k^{\prime}_{m}\;,k_{1},\cdots,k_{n},k^{% \prime}_{1},\ldots,k^{\prime}_{m}\in K$ (1)

can be rewritten as

 $h_{1}h^{r_{1}}\cdots h_{n}h^{r_{n}}=h^{\prime}_{1}h^{s_{1}}\cdots h^{\prime}_{% m}h^{s_{m}}\;,h_{1},\ldots,h_{n},h^{\prime}_{1},\ldots,h^{\prime}_{m}\in H% \setminus\{h\}\;,$

with $k_{i}=h_{i}h^{r_{i}}$, $k^{\prime}_{i}=h^{\prime}_{i}h^{s_{i}}$: this is an equation over $H$, and as such, has only the trivial solution $n=m$, $h_{i}=h^{\prime}_{i}$, $r_{i}=s_{i}$ for all $i$. This implies that (1) only has trivial solutions over $K$: by the characterization of free submonoids, $K$ is a code. However, $X\subseteq K^{\ast}$ because no element of $x$ “starts with $h$”, and $K^{\ast}$ is a proper subset of $H^{\ast}$ because the former does not contain $h$ and the latter does. Then $K^{\ast}$ is a free submonoid of $A^{\ast}$ which contains $X$ and is properly contained in $H^{\ast}$, against the definition of $H$ as the free hull of $X$.

## References

• 1 M. Lothaire. Combinatorics on words. Cambridge University Press 1997.
Title defect theorem DefectTheorem 2013-03-22 18:21:43 2013-03-22 18:21:43 Ziosilvio (18733) Ziosilvio (18733) 6 Ziosilvio (18733) Theorem msc 20M10 msc 20M05 $x^{m}=y^{n}$ has only trivial solutions over $A^{\ast}$