Inserción y supresión de palabras al cubo $w^3$

Question

Evan Chen texto fundamental presenta lo siguiente como (picante) problema 11C:

Consideremos el conjunto de palabras binarias finitas. Demostrar que no se puede obtener de $01$ a $10$ utilizando únicamente la operación "insertar o suprimir cualquier palabra cúbica $www$ ."

Dada una palabra $w = a_1 a_2 \cdots a_n$ podemos definir un invariante $$f(w) := a_1 - a_2 + a_4 - a_5 + a_7 - a_8 + \cdots$$ y no es difícil demostrar que si $v$ y $w$ son equivalentes bajo la operación, entonces $f(v) \equiv f(w) \pmod{3}$ . Así, $1 = f(10) \not\equiv f(01) = 2 \pmod{3}$ nos dice $10$ y $01$ no son equivalentes.

Pero este problema aparece en la sección de Evan sobre acciones de grupo. ¿Existe una forma teórica de grupos de adelantarse al invariante definido anteriormente? (Se me ocurrió adivinando un montón de cosas)

Edita: He aquí una prueba de que lo anterior $f$ es invariable. Comience con la palabra binaria $v:= a_1 \cdots a_n$ e insertar la palabra al cubo $(b_1 \cdots b_m)^{3}$ entre $a_k$ y $a_{k+1}$ . Denotemos la nueva palabra por $w:= c_1 \cdots c_{n+3m}$ .

Sea $\chi: \mathbb{Z}/3 \to \{-1,0,1\}$ viene dada por $\chi(1) = 1$ , $\chi(2) = -1$ y $\chi(3) = 0$ .

Entonces tenemos $$f(w) = \sum_{j=1}^{n+3m} \chi(j) c_j = \sum_{j=1}^{k} \chi(j) c_j + \sum_{j=k+1}^{k+3m} \chi(j) c_j + \sum_{j = k+3m+1}^{n+3m} \chi(j) c_j$$ $$ = \sum_{j=1}^{k} \chi(j) a_j + \sum_{j=1}^{m} (\chi(k+j) + \chi(k+j+m) + \chi(k+j+2m)) b_j + \sum_{j=k+1}^{n} \chi(j) a_j$$ Desde $\chi(x) + \chi(x+a) + \chi(x+2a) \equiv 0 \pmod{3}$ para cualquier $x$ , $a$ vemos que $$f(w) \equiv \sum_{j=1}^{n} \chi(j) a_j = f(v) \pmod{3}$$ como desee.

Answer 1

Puedes expresar tu solución en el lenguaje de la teoría de grupos de la siguiente manera.

Sea $G$ sea el subgrupo verbal $w^3$ en dos generadores $x$ y $y$ . Esto significa que $G$ tiene una presentación con generadores $x$ y $y$ y definiendo las relaciones el conjunto de todas las palabras sobre $x$ y $y$ de la forma $w^3$ para alguna palabra $w$ en $x$ y $y$ .

Podemos representar cada cadena binaria a un elemento de $G$ enviando $0$ a $x$ y $1$ a $y$ y luego ampliando letra por letra. En particular, las dos cadenas de interés, $01$ y $10$ se asignan a $xy$ y $yx$ respectivamente.

Preguntar si dos cadenas binarias son equivalentes mediante inserciones y supresiones de palabras de la forma $w^3$ es lo mismo que preguntar si sus representantes son iguales en $G$ . Lo explicaré con más detalle a continuación.

Las cadenas binarias sometidas a la operación de concatenación/yuxtaposición corresponden a elementos del monoide libre sobre $\{x,y\}$ . Sus imágenes en $G$ por supuesto, tienen inversos; por ejemplo, $x(x^2) = (x^2)x = 1$ así que $x^{-1} = x^2$ . Dos palabras sobre una presentación definen el mismo elemento del grupo definido por la presentación si y sólo si existe una secuencia finita de movimientos consistentes en insertar o suprimir relatores triviales, es decir. $xx^{-1}$ o $x^{-1}x$ para un generador $x$ o insertar o suprimir relatores definitorios. En el grupo $G$ inserción o supresión de un relator trivial $xx^{-1}$ es lo mismo que la inserción o supresión de $x(x^2)$ un relator definitorio. Todo esto es para decir que decidir si dos cadenas binarias bajo concatenación modulo inserción/eliminación de palabras de la forma $w^3$ son equivalentes es lo mismo que determinar si sus imágenes en $G$ son equivalentes.

Ahora el problema de argumentar que $xy$ y $yx$ definen diferentes elementos de $G$ . Necesitamos un homomorfismo a un grupo no abeliano bien entendido con la propiedad de que todo elemento no trivial tiene orden 3. Afortunadamente, existe tal grupo: $3 \times 3$ matrices unitriangulares con coeficientes en un campo de tres elementos, $H= U(3, \mathbb{F}_3)$ .

En concreto, el mapa $x$ a la matriz $(a_{ij})$ con $a_{12} = 1$ y otras entradas no diagonales cero. Mapa $y$ a $(b_{ij})$ con $b_{23} = 1$ y otras entradas no diagonales cero. Puesto que cada elemento de $H$ tiene orden 3, este mapa define un homomorfismo $f:G \to H$ . Desde $xy$ y $yx$ tienen imágenes diferentes, representan elementos distintos en $G$ .

El argumento anterior también demuestra que $01$ y $10$ no son equivalentes bajo la inserción y supresión de palabras binarias de la forma $w^p$ para un primo fijo $p > 2$ .

El argumento no sirve para $p=2$ ya que en este caso el grupo verbal $G$ (con relaciones definitorias $w^p$ ) es abeliano y $xy$ y $yx$ tienen la misma imagen. En efecto, $xy \to xy(yxyx) \to xxyx \to yx$ inserta la palabra $(yx)^2$ y luego borra las palabras $y^2$ y $x^2$ .

Answer 2

Esto es no una nueva respuesta. Es un comentario a la respuesta de Robert Bell. Al final, es innecesario introducir el "grupo verbal" $G$ en absoluto. Sólo necesitas un grupo no conmutativo $H$ tal que cada elemento no identitario de $H$ tiene orden $3$ . Sea $M_2$ sea el monoide libre sobre dos letras $a, b$ . Sea $a', b'$ sean dos elementos no conmutativos de $H$ . Existe un único homomorfismo monoide de $M_2$ a $H$ enviando $a \to a'$ y $b \to b'$ . Denotemos este homomorfismo por $x \mapsto x'$ . Por hipótesis sobre $H$ , $(ab)' \ne (ba)'$ . Sin embargo, cualquier cubo $w^3$ sur $M_2$ satisface $(w^3)' = 1$ . Por lo tanto, si $ab$ y $ba$ eran equivalentes en $M_2$ por inserción y supresión de palabras al cubo, se seguiría que $(ab)' = (ba)'$ . Como esto es falso, $ab$ y $ba$ no son equivalentes en $M_2$ mediante la inserción y supresión de palabras al cubo.

Edita: Añadiré una descripción más "grupal" de la solución original de Sameer Kailasa. Tampoco aquí hay nada muy nuevo o diferente. La solución de Sameer implica una especie de transformada de Fourier con valores en $\mathbb Z_3$ . Sea $a : \mathbb Z \to \mathbb Z_3$ sea cualquier función con soporte finito; es decir $a(j) = 0$ excepto para un número finito de valores de $j$ . Sea $\chi: \mathbb Z \to \mathbb Z_3$ sea un carácter no trivial; por tanto $\chi(j) = j \,\chi(1)$ y $\chi(1) \ne 0$ . Podemos definir la transformada de Fourier $$\mathcal F a(\chi) = \sum_j a(j) \chi(j).$$ Si nos dan una secuencia finita con valores en $\mathbb Z_3$ , $a = (a_1, a_2, \dots, a_n)$ acolchado declarando $a_j = 0$ para $j \le 0$ o $j >n$ y calcular $\mathcal F a(\chi)$ por la misma regla. En particular, $\mathcal F{(1, 0)}(\chi) = \chi(1)$ y $\mathcal F{(0, 1)} = \chi(2) = 2 \chi(1)$ . (Son las transformadas de Fourier de las "funciones delta").

El cálculo de Sameer muestra que $\mathcal F a$ no se modifica si se inserta una palabra cúbica en $a$ . Para ello, la propiedad crucial es que $\chi(k) + \chi(k + r) + \chi(k + 2r) = 0$ para cualquier $k$ y $r$ y cualquier carácter $\chi$ .