# 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 $$.

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

can be rewritten as

$${h}_{1}{h}^{{r}_{1}}\mathrm{\cdots}{h}_{n}{h}^{{r}_{n}}={h}_{1}^{\prime}{h}^{{s}_{1}}\mathrm{\cdots}{h}_{m}^{\prime}{h}^{{s}_{m}},{h}_{1},\mathrm{\dots},{h}_{n},{h}_{1}^{\prime},\mathrm{\dots},{h}_{m}^{\prime}\in H\setminus \{h\},$$ |

with ${k}_{i}={h}_{i}{h}^{{r}_{i}}$, ${k}_{i}^{\prime}={h}_{i}^{\prime}{h}^{{s}_{i}}$:
this is an equation over $H$,
and as such, has only the trivial solution $n=m$,
${h}_{i}={h}_{i}^{\prime}$, ${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 |
---|---|

Canonical name | DefectTheorem |

Date of creation | 2013-03-22 18:21:43 |

Last modified on | 2013-03-22 18:21:43 |

Owner | Ziosilvio (18733) |

Last modified by | Ziosilvio (18733) |

Numerical id | 6 |

Author | Ziosilvio (18733) |

Entry type | Theorem^{} |

Classification | msc 20M10 |

Classification | msc 20M05 |

Defines | ${x}^{m}={y}^{n}$ has only trivial solutions over ${A}^{\ast}$ |