defect theorem

Let A be an arbitrary set, let A be the free monoid on A, and let X be a finite subset of A 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 xm=yn over A has only the trivial solutions where x and y are powers of the same word: in fact, xm=yn 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 wordPlanetmathPlanetmath on A.

Define f:XH such that f(x) is the only hH such that xhH: 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 surjectivePlanetmathPlanetmath but not injectivePlanetmathPlanetmath.

By hypothesisMathworldPlanetmathPlanetmath, X is not a code. Then there exists an equation x1xn=x1xm over X with a nontrivial solution: it is not restrictive to suppose that x1x1. Since however the factorization over H is unique, the h such that x1hH is the same as the h such that x1hH: then f(x1)=f(x1) with x1x1, so f is not injective.

Now suppose, for the sake of contradictionMathworldPlanetmathPlanetmath, that hHf(X) exists. Let K=(H{h})h. Then any equation

k1kn=k1km,k1,,kn,k1,,kmK (1)

can be rewritten as


with ki=hihri, ki=hihsi: this is an equation over H, and as such, has only the trivial solution n=m, hi=hi, ri=si for all i. This implies that (1) only has trivial solutions over K: by the characterization of free submonoids, K is a code. However, XK because no element of x “starts with h”, and K is a proper subsetMathworldPlanetmathPlanetmath of H because the former does not contain h and the latter does. Then K is a free submonoid of A which contains X and is properly contained in H, against the definition of H as the free hull of X.


  • 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 TheoremMathworldPlanetmath
Classification msc 20M10
Classification msc 20M05
Defines xm=yn has only trivial solutions over A