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

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 }$