Lemme d'échange

On sait qu'il existe une infinité de mots sans carré sur un alphabet à 3 lettres. Pour démontrer que l'ensemble ${\displaystyle L_{3}}$ des mots sur 3 lettres contenant un carré n'est pas algébrique, on montre, dans la deuxième partie ci-dessous, que l'ensemble des mots ${\displaystyle L_{6}}$ sur 6 lettres contenant un carré n'est pas algébrique. Pour conclure, on utilise un morphisme sans carré (c'est-à-dire un morphisme qui préserve les mots sans carré) d'un alphabet à 3 lettres sur un alphabet à 6 lettres. Un tel morphisme envoie l'ensemble ${\displaystyle L_{3}}$ sur l'ensemble ${\displaystyle L_{6}}$. Si l'ensemble ${\displaystyle L_{3}}$ était algébrique, il en serait de même de ${\displaystyle L_{6}}$ puisqu'un morphisme préserve le caractère algébrique des langages.

On démontre que l’ensemble des mots

${\displaystyle L=L_{6}=\{xwwy\mid x,w,y\in A^{*}\}}$

contenant un carré sur un alphabet à 6 lettres ${\displaystyle A=\{\#,0,1,a,b,c\}}$ n’est pas algébrique. Pour cela, on choisit un entier ${\displaystyle N}$ assez grand et on considère un mot sans carré fixe de longueur ${\displaystyle N}$, soit

${\displaystyle v=c_{1}c_{2}\cdots c_{N}}$

sur l’alphabet ${\displaystyle B=\{a,b,c\}}$, avec ${\displaystyle c_{i}\in B}$. On considère l’ensemble

${\displaystyle Q=\{\#t\#t\mid t=d_{0}c_{1}d_{1}c_{2}\cdots c_{N}d_{N},~d_{i}\in \{0,1\}\}}$.

Chaque mot de ${\displaystyle Q}$ est un carré, et ne contient aucun autre carré. On pose ${\displaystyle M=N+1}$. Un mot de ${\displaystyle Q}$ est de longueur ${\displaystyle 4M}$, et il y a ${\displaystyle 2^{M}}$ mots dans ${\displaystyle Q}$.

On applique le lemme d’échange pour les paramètres ${\displaystyle n=4M}$ et ${\displaystyle m=n/2=2M}$. Il existe un ensemble d’échange ${\displaystyle R\subset Q}$ de taille

${\displaystyle |R|\geq {\frac {|Q|}{Cn^{2}}}={\frac {2^{M}}{16CM^{2}}}}$

où ${\displaystyle C}$ est une constante. De plus, la largeur ${\displaystyle q}$ de ${\displaystyle R}$ vérifie ${\displaystyle M<q\leq 2M}$.

On considère des mots

${\displaystyle u_{1}v_{1}w_{1},u_{2}v_{2}w_{2}\in R}$

avec ${\displaystyle |u_{1}|=|u_{2}|,|v_{1}|=|v_{2}|=q}$, et on a donc ${\displaystyle u_{1}v_{2}w_{1}\in L}$. Les facteurs centraux ${\displaystyle v_{1}}$ et ${\displaystyle v_{2}}$ ont les mêmes lettres dans ${\displaystyle B}$ aux mêmes positions. Mais comme le mot ${\displaystyle v}$ est sans carré, les deux mots ${\displaystyle u_{1}v_{1}w_{1}}$ et ${\displaystyle u_{1}v_{2}w_{1}}$ contiennent tous deux un carré seulement si ${\displaystyle v_{1}=v_{2}}$. Ceci montre que si ${\displaystyle u_{1}v_{1}w_{1}}$ et ${\displaystyle u_{2}v_{2}w_{2}}$ s’échangent, alors ${\displaystyle v_{1}=v_{2}}$. Il en résulte que le nombre d’éléments de ${\displaystyle R}$ est majoré par

${\displaystyle |R|\leq 2^{M-(1+q/2)}\leq 2^{M/2}}$

puisque ${\displaystyle |v_{1}|=q\geq M}$. Mais alors l’encadrement de ${\displaystyle |R]}$ devient

${\displaystyle {\frac {2^{M}}{16CM^{2}}}\leq |R|\leq 2^{M/2}}$

ce qui est une inégalité impossible si ${\displaystyle M=N+1}$ est assez grand.