¿Es el conjunto de todas las palabras primitivas un idioma principal?

Una palabra $w$ se llama primitiva , si no hay una palabra $v$ y $k > 1$ modo que $w = v^k$ . El conjunto $Q$ de todas las palabras primitivas sobre un alfabeto $\Sigma$ es un lenguaje bien conocido. WLOG podemos elegir $\Sigma = \{ a,b \}$ .

Un lenguaje $L$ es primo , si para cada idioma $A$ y $B$ con $L = A \cdot B$ tenemos $A = \{\epsilon\}$ o $B = \{ \epsilon \}$ .

¿Q es primo?

Con la ayuda de un solucionador SAT, podría demostrar que tenemos o ya que de lo contrario no se puede factorizar en$\{a,b\} \subseteq A$$\{a,b\} \subseteq B$$\{ ababa, babab \} \subset Q$$A$ y $B$ , pero han estado atrapados desde entonces.

La respuesta es sí. Supongamos que tenemos una factorización $Q = A\cdot B$ .

Una observación fácil es que $A$ y $B$ deben ser disjuntos (ya que para $w\in A\cap B$ obtenemos $w^2\in Q$ ). En particular, solo uno de $A,B$ puede contener $\epsilon$ . Podemos suponer sin pérdida de generalidad (desde el otro caso es completamente simétrica) que $\epsilon\in B$ . A continuación, desde $a$ y $b$ no se puede factorizar en factores que no estén vacíos, debemos tener $a,b\in A$ .

A continuación, obtenemos que $a^mb^n\in A$ (y, de forma completamente análoga, $b^ma^n\in A$ ) para todos $m,n>0$ por inducción en $m$ :

Para $m=1$ , ya que $ab^n\in Q$ , debemos tener $ab^n = uv$ con $u\in A, v\in B$ . Como $u\neq\epsilon$ , $v$ debe ser $b^k$ para algunos $k\le n$ . Pero si $k>0$ , entonces desde $b\in A$ obtenemos $b^{1+k}\in Q$ , contradicción. Entonces$v=\epsilon$ , y$ab^n\in A$ .

Para la etapa inductiva, ya que $a^{m+1}b^n\in Q$ tenemos $a^{m+1}b^n = uv$ con $u\in A, v\in B$ . Como nuevamente $u\neq\epsilon$ , tenemos $v = a^kb^n$ para algunos $0<k<m+1$ , o $v=b^k$ para algunos $k<n$ . Pero en el primer caso,$v$ ya está en$A$ por la hipótesis de inducción, entonces$v^2\in Q$ , contradicción. En este último caso, hay que tener$k=0$ (es decir,$v=\epsilon$ ) ya que desde$b\in A$ obtenemos$b^{1+k}\in Q$ . Así$u=a^{m+1}b^n\in A$ .

Consideremos ahora el caso general de palabras primitivas con $r$ alternancias entre $a$ y $b$ , es decir, $w$ es o bien $a^{m_1}b^{n_1}\ldots a^{m_s}b^{n_s}$ , $b^{m_1}a^{n_1}\ldots b^{m_s}a^{n_s}$ (para $r=2s-1$ ), $a^{m_1}b^{n_1}\ldots a^{m_{s+1}}$ , o$b^{m_1}a^{n_1}\ldots b^{m_{s+1}}$ (para$r=2s$); podemos demostrar que todos están en$A$usando la inducción en$r$. Lo que hicimos hasta ahora cubierto los casos base$r=0$y$r=1$.

Para $r>1$ , usamos otra inducción en $m_1$ , que funciona de manera muy similar a la de $r=1$ anterior:

Si $m_1=1$ , entonces $w=uv$ con $u\in A, v\in B$ , y como $u\neq\epsilon$ , $v$ tiene menos de $r$ alternancias. Entonces $v$ (o su raíz en caso de que $v$ no sea primitivo) está en $A$ por la hipótesis de inducción en $r$ para una contradicción como la anterior, a menos que $v=\epsilon$ . Así $w=u\in A$ .

Si $m_1>1$ , en cualquier factorización $w=uv$ con $u\neq\epsilon$ , $v$ tiene menos alternancias (y su raíz está en $A$ menos que $v=\epsilon$ por la hipótesis de inducción en $r$ ), o un primer bloque más corto (y su la raíz está en A a menos que $v=\epsilon$ por la hipótesis de inducción en $m_1$ ). En cualquiera de los casos que conseguir que debemos tener $v=\epsilon$ , es decir $w=u\in A$ .

El caso de $Q' := Q\cup\{\epsilon\}$ es bastante más complicado. Las cosas obvias a tener en cuenta son que en cualquier descomposición $Q = A\cdot B$ , tanto $A$ como $B$ deben ser subconjuntos de $Q'$ con $A\cap B = \{\epsilon\}$ . También, $a,b$ debe estar contenido en $A\cup B$ .

Con un poco de trabajo extra, se puede mostrar que $a$ y $b$ deben estar en el mismo subconjunto. De lo contrario, asumir sin pérdida de generalidad que $a\in A$ y $b\in B$ . Digamos que $w\in Q'$ tiene una factorización adecuada si $w=uv$ con $u\in A\setminus\{\epsilon\}$ y $v\in B\setminus\{\epsilon\}$ . Tenemos dos subcasas (simétricas) dependiendo de dónde va $ba$ (debe estar en$A$ or $B$ since it has no proper factorization).

• If $ba\in A$, then $aba$ has no proper factorization since $ba,a\notin B$. Since $aba\in A$ would imply $abab\in A\cdot B$, we get $aba\in B$. As a consequence, $bab$ is neither in $A$ (which would imply $bababa\in A\cdot B$) nor in $B$ (which would imply $abab\in A\cdot B$). Now consider the word $babab$. It has no proper factorization since $bab\notin A\cup B$ and $abab,baba$ are not primitive. If $babab\in A$, then since $aba\in B$ we get $(ba)^4\in A\cdot B$; if $babab\in B$, then since $a\in A$ we get $(ab)^3\in A\cdot B$. So there is no way to have $babab\in A\cdot B$, contradiction.
• The case $ba\in B$ is completely symmetric. In a nutshell: $bab$ has no proper factorization and cannot be in $B$, so it must be in $A$; therefore $aba$ cannot be in $A$ or $B$; therefore $ababa$ has no proper factorization but also cannot be in either $A$ or $B$, contradiction.

I am currently not sure how to proceed beyond this point; it would be interesting to see if the above argument can be systematically generalized.