Palabra de pasillo

Construcción que proporciona un orden total sobre un monoide libre

En matemáticas , en las áreas de teoría de grupos y combinatoria , las palabras de Hall proporcionan una factorización monoide única del monoide libre . También están totalmente ordenadas y, por lo tanto, proporcionan un orden total en el monoide. Esto es análogo al caso más conocido de las palabras de Lyndon ; de hecho, las palabras de Lyndon son un caso especial y casi todas las propiedades que poseen las palabras de Lyndon se transfieren a las palabras de Hall. Las palabras de Hall están en correspondencia uno a uno con los árboles de Hall . Estos son árboles binarios ; tomados en conjunto, forman el conjunto de Hall . Este conjunto es un subconjunto totalmente ordenado particular de un álgebra no asociativa libre, es decir, un magma libre . En esta forma, los árboles de Hall proporcionan una base para las álgebras de Lie libres y se pueden usar para realizar las conmutaciones requeridas por el teorema de Poincaré-Birkhoff-Witt utilizado en la construcción de un álgebra envolvente universal . Como tal, esto generaliza el mismo proceso cuando se hace con las palabras de Lyndon. Los árboles de Hall también se pueden utilizar para dar un orden total a los elementos de un grupo, mediante el proceso de recolección de conmutadores , que es un caso especial de la construcción general que se muestra a continuación. Se puede demostrar que los conjuntos de Lazard coinciden con los conjuntos de Hall.

El desarrollo histórico se desarrolla en orden inverso a la descripción anterior. El proceso de recolección de conmutadores fue descrito por primera vez, en 1934, por Philip Hall y explorado en 1937 por Wilhelm Magnus . ^{[1] [2]} Los conjuntos de Hall fueron introducidos por Marshall Hall basándose en el trabajo de Philip Hall sobre grupos. ^[3] Posteriormente, Wilhelm Magnus demostró que surgen como el álgebra de Lie graduada asociada con la filtración en un grupo libre dado por la serie central inferior . Esta correspondencia fue motivada por las identidades de conmutadores en la teoría de grupos debido a Philip Hall y Ernst Witt .

Preliminares notacionales

El escenario de este artículo es el magma libre en generadores. Este es simplemente un conjunto que contiene elementos, junto con un operador binario que permite yuxtaponer dos elementos cualesquiera, uno al lado del otro. La yuxtaposición se considera no asociativa y no conmutativa , por lo que se deben usar necesariamente paréntesis cuando se yuxtaponen tres o más elementos. Así, por ejemplo, no es lo mismo que . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \bullet }$ ${\displaystyle (a\bullet b)\bullet c}$ ${\displaystyle a\bullet (b\bullet c)}$

De esta manera, el operador magma proporciona un sustituto conveniente para cualquier otro operador binario deseado que pueda tener propiedades adicionales, como conmutadores de grupo o de álgebra. Así, por ejemplo, la yuxtaposición de magma se puede mapear al conmutador de un álgebra no conmutativa: ${\displaystyle \bullet }$

${\displaystyle a\bullet b\mapsto [a,b]=ab-ba}$

o a un conmutador de grupo:

${\displaystyle a\bullet b\mapsto aba^{-1}b^{-1}}$

Los dos mapas anteriores son simplemente homomorfismos de magma, en el sentido convencional de un homomorfismo ; los objetos de la derecha tienen más estructura que un magma. Para evitar el incómodo lío tipográfico que es , es convencional escribir simplemente para . Sin embargo, el uso de paréntesis es obligatorio, ya que como ya se señaló. Si es un objeto compuesto, a veces se puede escribir como sea necesario, para desambiguar el uso. Por supuesto, también se puede escribir en lugar de , pero esto puede llevar a una proliferación de corchetes y comas. Teniendo esto en cuenta, uno puede ser fluido en la notación. ${\displaystyle \bullet }$ ${\displaystyle ab}$ ${\displaystyle (a\bullet b)}$ ${\displaystyle (ab)c\neq a(bc)}$ ${\displaystyle a}$ ${\displaystyle (a)}$ ${\displaystyle [a,b]}$ ${\displaystyle ab}$

Conjunto de salón

El conjunto de Hall es un subconjunto totalmente ordenado de un álgebra libre no asociativa, es decir, un magma libre . Sea un conjunto de generadores, y sea el magma libre sobre . El magma libre es simplemente el conjunto de cadenas no asociativas con las letras de , con los paréntesis conservados para mostrar la agrupación. Los paréntesis pueden escribirse con corchetes, de modo que los elementos del magma libre puedan verse como conmutadores formales. De manera equivalente, el magma libre es el conjunto de todos los árboles binarios con hojas marcadas por elementos de . ${\displaystyle A={a_{1},\ldots ,a_{n}}}$ ${\displaystyle M(A)}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$

El conjunto Hall se puede construir recursivamente (en orden creciente) de la siguiente manera: ${\displaystyle H\subseteq M(A)}$

• A los elementos de se les da un orden total arbitrario. ${\displaystyle A}$
• El conjunto Hall contiene los generadores: ${\displaystyle A\subseteq H.}$
• Un conmutador formal si y sólo si y y y: ${\displaystyle [x,y]\in H}$ ${\displaystyle x\in H}$ ${\displaystyle y\in H}$ ${\displaystyle x>y}$
  • O bien (y por lo tanto ), ${\displaystyle x\in A}$ ${\displaystyle y\in A}$
  • O con y y . ${\displaystyle x=[u,v]}$ ${\displaystyle u\in H}$ ${\displaystyle v\in H}$ ${\displaystyle v\leq y}$
• Los conmutadores se pueden ordenar arbitrariamente, siempre que esto se cumpla. ${\displaystyle y<[x,y]}$

La construcción y la notación utilizadas a continuación son casi idénticas a las utilizadas en el proceso de recolección de conmutadores , y por lo tanto se pueden comparar directamente; los pesos son las longitudes de las cadenas. La diferencia es que no se requiere mención de grupos. Todas estas definiciones coinciden con la de X. Viennot. ^[4] Nótese que algunos autores invierten el orden de la desigualdad. Nótese también que una de las condiciones, la , puede parecer "al revés"; este "atraso" es lo que proporciona el orden descendente requerido para la factorización. Invertir la desigualdad no revierte este "atraso". ${\displaystyle v\leq y}$

Ejemplo

Considere el conjunto generador con dos elementos. Defina y escriba para simplificar la notación, utilizando paréntesis solo cuando sea necesario. Los miembros iniciales del conjunto Hall son entonces (en orden) ${\displaystyle \{a,b\}.}$ ${\displaystyle a>b}$ ${\displaystyle xy}$ ${\displaystyle [x,y]}$

${\displaystyle {\begin{aligned}&b,a,\\&ab,\\&(ab)b,\;\;(ab)a,\\&((ab)b)b,\;\;((ab)b)a,\;\;((ab)a)a,\\&(((ab)b)b)b,\;(((ab)b)b)a,\;(((ab)b)a)a,\;(((ab)a)a)a,\;((ab)b)(ab),\;((ab)a)(ab),\\&\cdots \end{aligned}}}$

Observe que hay elementos de cada longitud distinta. Esta es la secuencia inicial del polinomio del collar en dos elementos (que se describe a continuación). ${\displaystyle 2,1,2,3,6,\ldots }$

Combinatoria

Un resultado básico es que el número de elementos de longitud en el conjunto Hall (sobre generadores) está dado por el polinomio de collar ${\displaystyle k}$ ${\displaystyle n}$

${\displaystyle M_{n}(k)\ =\ {1 \over k}\sum _{d\,|\,k}\mu \!\left({k \over d}\right)n^{d}={1 \over k}\sum _{d\,|\,k}\mu \!\left({d}\right)n^{k/d}}$

donde es la función clásica de Möbius . La suma es una convolución de Dirichlet . ${\displaystyle \mu }$

Definiciones y lemas

Algunas definiciones básicas son útiles. Dado un árbol , el elemento se denomina subárbol izquierdo inmediato y, del mismo modo, es el subárbol derecho inmediato . Un subárbol derecho es él mismo o un subárbol derecho de o . Un subárbol de extrema derecha es él mismo o un subárbol de extrema derecha de . ${\displaystyle t=[x,y]}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle y}$

Un lema básico es que si es un subárbol derecho de un árbol de Hall , entonces ${\displaystyle v}$ ${\displaystyle t=[x,y]}$ ${\displaystyle v\leq y.}$

Palabras del salón

Las palabras de Hall se obtienen del conjunto Hall "olvidando" los corchetes conmutadores, pero manteniendo por lo demás la noción de orden total. Resulta que este "olvido" es inofensivo, ya que el árbol Hall correspondiente se puede deducir de la palabra, y es único. Es decir, las palabras de Hall están en correspondencia uno a uno con los árboles Hall. El orden total en los árboles Hall pasa a un orden total en las palabras de Hall.

Esta correspondencia permite una factorización monoide : dado el monoide libre , cualquier elemento de puede factorizarse de forma única en una secuencia ascendente de palabras de Hall. Esto es análogo y generaliza el caso más conocido de factorización con palabras de Lyndon proporcionado por el teorema de Chen–Fox–Lyndon . ${\displaystyle A^{*}}$ ${\displaystyle A^{*}}$

Más precisamente, cada palabra puede escribirse como una concatenación de palabras de Hall. ${\displaystyle w\in A^{*}}$

${\displaystyle w=h_{1}h_{2}\cdots h_{k}}$

con cada palabra de Hall totalmente ordenada por el orden de Hall: ${\displaystyle h_{j}}$

${\displaystyle h_{1}\leq h_{2}\leq \cdots \leq h_{k}.}$

De esta manera, el ordenamiento de palabras de Hall se extiende a un orden total en el monoide. Los lemas y teoremas necesarios para proporcionar la correspondencia entre palabras y árboles y el ordenamiento único se esquematizan a continuación.

Follaje

El follaje de un magma es la aplicación canónica del magma al monoide libre , dada por for y else. El follaje es simplemente la cadena que consiste en las hojas del árbol, es decir, tomando el árbol escrito con corchetes conmutadores y borrando los corchetes conmutadores. ${\displaystyle M(A)}$ ${\displaystyle f:M(A)\to A^{*}}$ ${\displaystyle A^{*}}$ ${\displaystyle f:a\mapsto a}$ ${\displaystyle a\in A}$ ${\displaystyle f:[x,y]\mapsto f(x)f(y)}$

Factorización de palabras de Hall

Sea un árbol Hall, y sea la palabra Hall correspondiente. Dada cualquier factorización de una palabra Hall en dos cadenas no vacías y , entonces existe una factorización en árboles Hall tal que y con ${\displaystyle t=[x,y]\in H}$ ${\displaystyle w=f([x,y])}$ ${\displaystyle w=uv}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u=f(x_{1})\cdots f(x_{m})}$ ${\displaystyle v=f(y_{1})\cdots f(y_{n})}$

${\displaystyle x_{1},\ldots ,x_{m}>y_{1}}$

y

${\displaystyle y_{1}\leq y_{2}\leq \cdots \leq y_{n}\leq y.}$

Este desarrollo y el desarrollo posterior a continuación están dados por Guy Melançon. ^[5]

Correspondencia

La inversa de la factorización anterior establece la correspondencia entre las palabras de Hall y los árboles de Hall. Esto se puede expresar de la siguiente forma interesante: si es un árbol de Hall, y la palabra de Hall correspondiente se factoriza como ${\displaystyle t}$ ${\displaystyle f(t)}$

${\displaystyle f(t)=f(t_{1})\cdots f(t_{n})}$

con

${\displaystyle f(t_{1})\leq \cdots \leq f(t_{n})}$

entonces . En otras palabras, las palabras de Hall no se pueden factorizar en una secuencia descendente de otras palabras de Hall. ^[5] Esto implica que, dada una palabra de Hall, el árbol correspondiente se puede identificar de forma única. ${\displaystyle n=1}$

Factorización estándar

El orden total de los árboles Hall pasa a las palabras Hall. Por lo tanto, dada una palabra Hall , se puede factorizar como con . Esto se denomina factorización estándar . ${\displaystyle w=f([x,y])}$ ${\displaystyle w=f(x)f(y)}$ ${\displaystyle f(x)>f(y)}$

Secuencia estándar

Se dice que una secuencia de palabras de Hall es una secuencia estándar si cada una es una letra o una factorización estándar con Nótese que las secuencias crecientes de palabras de Hall son estándar. ${\displaystyle (w_{1},w_{2},\ldots ,w_{n})}$ ${\displaystyle w_{i}}$ ${\displaystyle w_{i}=u_{i}v_{i}}$ ${\displaystyle v_{i}\leq w_{i+1},\cdots ,w_{n}.}$

Reescritura de términos

La factorización única de cualquier palabra en una concatenación de una secuencia ascendente de palabras Hall con se puede lograr definiendo y aplicando recursivamente un sistema simple de reescritura de términos . La unicidad de la factorización se desprende de las propiedades de confluencia del sistema. ^[5] La reescritura se realiza mediante el intercambio de ciertos pares de palabras Hall consecutivas en una secuencia; se proporciona después de estas definiciones. ${\displaystyle w\in A^{*}}$ ${\displaystyle w=h_{1}h_{2}\cdots h_{k}}$ ${\displaystyle h_{1}\leq h_{2}\leq \cdots \leq h_{k}}$

Una caída en una secuencia de palabras de Hall es un par tal que si la secuencia es una secuencia estándar, entonces la caída se denomina caída legal si uno también tiene esa ${\displaystyle (h_{1},h_{2},\ldots ,h_{n})}$ ${\displaystyle (h_{i},h_{i+1})}$ ${\displaystyle h_{i}>h_{i+1}.}$ ${\displaystyle h_{i+1}\leq h_{i+2},\ldots ,h_{n}.}$

Dada una secuencia estándar con una eliminación legal, existen dos reglas de reescritura distintas que crean nuevas secuencias estándar. Una concatena las dos palabras en la eliminación:

${\displaystyle (h_{1},h_{2},\ldots ,h_{n})\to (h_{1},h_{2},\ldots ,h_{i}h_{i+1},\ldots ,h_{n})}$

mientras que el otro permuta los dos elementos en la gota:

${\displaystyle (h_{1},h_{2},\ldots ,h_{n})\to (h_{1},h_{2},\ldots ,h_{i-1},h_{i+1},h_{i},h_{i+2},\ldots ,h_{n})}$

No es difícil demostrar que ambas reescrituras dan como resultado una nueva secuencia estándar. En general, es más conveniente aplicar la reescritura al punto legal más a la derecha; sin embargo, se puede demostrar que la reescritura es confluente y, por lo tanto, se obtienen los mismos resultados sin importar el orden.

Pedido total

Se puede proporcionar un orden total de las palabras. Esto es similar al orden lexicográfico estándar , pero a nivel de palabras de Hall. Dadas dos palabras factorizadas en orden ascendente de palabras de Hall, es decir , que ${\displaystyle w\in A^{*}.}$ ${\displaystyle u,v}$

${\displaystyle u=u_{1}u_{2}\cdots u_{m}\quad }$y ${\displaystyle \quad v=v_{1}v_{2}\cdots v_{n}}$

con cada palabra de Hall, se tiene un ordenamiento que si ${\displaystyle u_{i},v_{j}}$ ${\displaystyle u<v}$

${\displaystyle m<n\quad }$y ${\displaystyle \quad u_{1}=v_{1},\,u_{2}=v_{2},\,\cdots ,u_{m}=v_{m}}$

o si

${\displaystyle u_{1}=v_{1},\,u_{2}=v_{2},\,\ldots ,u_{k}=v_{k}\quad }$y ${\displaystyle \quad u_{k+1}<v_{k+1}.}$

Propiedades

Las palabras de Hall tienen varias propiedades curiosas, muchas de ellas casi idénticas a las de las palabras de Lyndon . La primera y más importante propiedad es que las palabras de Lyndon son un caso especial de las palabras de Hall. Es decir, la definición de una palabra de Lyndon satisface la definición de la palabra de Hall. Esto se puede verificar fácilmente mediante una comparación directa; observe que la dirección de la desigualdad utilizada en las definiciones anteriores es exactamente la inversa de la utilizada en la definición habitual de las palabras de Lyndon. El conjunto de árboles de Lyndon (que se derivan de la factorización estándar) es un conjunto de Hall.

Otras propiedades incluyen:

• Las palabras de Hall son acíclicas , también conocidas como primitivas . Es decir, no se pueden escribir en la forma para alguna palabra y . ${\displaystyle w=x^{n}}$ ${\displaystyle x\in A^{*}}$ ${\displaystyle n>1}$
• Una palabra es una palabra Hall si y solo si para cualquier factorización de en palabras no vacías obedece . En particular, esto implica que ninguna palabra Hall es un conjugado de otra palabra Hall. Nótese nuevamente que esto es exactamente como es para una palabra Lyndon: las palabras Lyndon son las menores de su clase de conjugación; las palabras Hall son las mayores. ${\displaystyle w\in A^{*}}$ ${\displaystyle w=uv}$ ${\displaystyle w>vu}$
• Una palabra es una palabra Hall si y sólo si es mayor que cualquiera de sus factores derechos propios. Esto se desprende de los dos puntos anteriores. ${\displaystyle w\in A^{*}}$
• Toda palabra primitiva es conjugada de una palabra Hall. Es decir, existe un desplazamiento circular de que es una palabra Hall. De manera equivalente, existe una factorización tal que es una palabra Hall. Este conjugado es único, ya que ninguna palabra Hall es conjugada de otra palabra Hall. ${\displaystyle w\in A^{*}}$ ${\displaystyle w}$ ${\displaystyle w=uv}$ ${\displaystyle vu}$
• Cada palabra es el conjugado de una potencia de una palabra única de Hall. ${\displaystyle w\in A^{*}}$

Trascendencia

Existe un sistema de reescritura de términos similar para las palabras de Lyndon , así es como se logra la factorización de un monoide con palabras de Lyndon.

Debido a que las palabras Hall se pueden colocar en árboles Hall, y cada árbol Hall se puede interpretar como un conmutador, el término reescritura se puede utilizar para realizar el proceso de recopilación de conmutadores en un grupo.

Otra aplicación muy importante de la regla de reescritura es la de realizar las conmutaciones que aparecen en el teorema de Poincaré–Birkhoff–Witt . En el artículo sobre álgebras envolventes universales se ofrece una explicación detallada de la conmutación . Nótese que la reescritura de términos con palabras de Lyndon también se puede utilizar para obtener la conmutación necesaria para el teorema PBW. ^[6]

Historia

Los conjuntos Hall fueron introducidos por Marshall Hall basándose en el trabajo de Philip Hall sobre grupos. ^[3] Posteriormente, Wilhelm Magnus demostró que surgen como el álgebra de Lie graduada asociada con la filtración en un grupo libre dado por la serie central inferior . Esta correspondencia fue motivada por las identidades de conmutadores en la teoría de grupos debido a Philip Hall y Ernst Witt .

Véase también

• Identidad Hall-Petresco
• Odómetro de Markov

Referencias

1. Hall, Philip (1934), "Una contribución a la teoría de grupos de orden de potencia primo", Actas de la Sociedad Matemática de Londres , 36 : 29–95, doi :10.1112/plms/s2-36.1.29
2. W. Magnus, (1937) "Über Beziehungen zwischen höheren Kommutatoren", J. Grelle 177 , 105-115.
3. Hall, Marshall (1950), "Una base para anillos de Lie libres y conmutadores superiores en grupos libres", Actas de la American Mathematical Society , 1 (5): 575–581, doi : 10.1090/S0002-9939-1950-0038336-7 , ISSN  0002-9939, MR  0038336
4. X. Viennot, (1978) "Algèbres de Lie libres et monoïdes libres", Lecture Notes in Mathematics , 691 , Springer – Verlag
5. Guy Melançon, (1992) "Combinatoria de árboles de Hall y palabras de Hall", Journal of Combinatorial Theory , 59A (2) págs. 285–308.
6. Guy Melançon y C. Reutenauer (1989), "Palabras de Lyndon, álgebras libres y barajadas", Canadian Journal of Mathematics . 41 , n.º 4, págs. 577-591.