En matemáticas , la regla de Littlewood-Richardson es una descripción combinatoria de los coeficientes que surgen al descomponer un producto de dos funciones de Schur como una combinación lineal de otras funciones de Schur. Estos coeficientes son números naturales, que la regla de Littlewood-Richardson describe como contar ciertos cuadros sesgados . Ocurren en muchos otros contextos matemáticos, por ejemplo, como multiplicidad en la descomposición de productos tensoriales de representaciones de dimensiones finitas de grupos lineales generales , o en la descomposición de ciertas representaciones inducidas en la teoría de representación del grupo simétrico., o en el área de combinatoria algebraica que trata con cuadros de Young y polinomios simétricos .
Los coeficientes de Littlewood-Richardson dependen de tres particiones , digamos, de los cuales y describir las funciones de Schur que se multiplican, y da la función de Schur de la cual este es el coeficiente en la combinación lineal; en otras palabras son los coeficientes tal que
La regla de Littlewood-Richardson establece que es igual al número de cuadros de Littlewood-Richardson de forma sesgada y de peso .
Historia
Desafortunadamente, la regla de Littlewood-Richardson es mucho más difícil de probar de lo que se sospechaba al principio. Una vez le dijeron al autor que la regla Littlewood-Richardson ayudó a que los hombres llegaran a la luna, pero no se demostró hasta que llegaron allí.
Gordon James ( 1987 )
La regla de Littlewood-Richardson fue establecida por primera vez por DE Littlewood y AR Richardson ( 1934 , teorema III p. 119), pero aunque la afirmaron como un teorema, solo la demostraron en algunos casos especiales bastante simples. Robinson ( 1938 ) afirmó completar su prueba, pero su argumento tenía lagunas, aunque estaba escrito de manera tan oscura que estas lagunas no se notaron durante algún tiempo, y su argumento se reproduce en el libro ( Littlewood 1950 ). Macdonald (1995) llenó posteriormente algunas de las lagunas . Las primeras pruebas rigurosas de la regla se dieron cuatro décadas después de que fue encontrada, por Schützenberger ( 1977 ) y Thomas (1974) , después de que C. Schensted ( 1961 ), Schützenberger ( 1963 ) y Knuth ( 1974) desarrollaron la teoría combinatoria necesaria. 1970 ) en su trabajo sobre la correspondencia Robinson-Schensted . Ahora hay varias pruebas breves de la regla, como ( Gasharov 1998 ) y ( Stembridge 2002 ) que utilizan involuciones de Bender-Knuth . Littelmann (1994) utilizó el modelo de trayectoria de Littelmann para generalizar la regla de Littlewood-Richardson a otros grupos de Lie semisimplejos.
La regla Littlewood-Richardson es conocida por la cantidad de errores que aparecieron antes de su prueba completa y publicada. Varios intentos publicados para demostrarlo son incompletos, y es particularmente difícil evitar errores al hacer cálculos manuales con él: incluso el ejemplo original en DE Littlewood y AR Richardson ( 1934 ) contiene un error.
Cuadros de Littlewood-Richardson
Un cuadro de Littlewood-Richardson es un cuadro semiestándar sesgado con la propiedad adicional de que la secuencia obtenida al concatenar sus filas invertidas es una palabra de celosía (o permutación de celosía), lo que significa que en cada parte inicial de la secuencia cualquier número ocurre al menos tan a menudo como el número . Otra caracterización equivalente (aunque no del todo obvia) es que el cuadro en sí, y cualquier cuadro obtenido de él eliminando algunas de sus columnas más a la izquierda, tiene un peso ligeramente decreciente. Se han encontrado muchas otras nociones combinatorias que resultan estar en combinación con los cuadros de Littlewood-Richardson y, por lo tanto, también pueden usarse para definir los coeficientes de Littlewood-Richardson.
Ejemplo
Considere el caso de que , y . Entonces el hecho de que puede deducirse del hecho de que los dos cuadros que se muestran a la derecha son los únicos dos cuadros de formas de Littlewood-Richardson y el peso . De hecho, dado que el último cuadro de la primera línea no vacía del diagrama de sesgo solo puede contener una entrada 1, toda la primera línea debe llenarse con las entradas 1 (esto es cierto para cualquier cuadro de Littlewood-Richardson); en el último cuadro de la segunda fila solo podemos colocar un 2 por el rigor de la columna y el hecho de que nuestra palabra de celosía no puede contener una entrada más grande antes de que contenga un 2. Para el primer cuadro de la segunda fila ahora podemos usar un 1 o un 2. Una vez que se elige esa entrada, la tercera fila debe contener las entradas restantes para hacer el peso (3,2,1), en un orden ligeramente creciente, por lo que no nos queda más opción; en ambos casos resulta que sí encontramos un cuadro de Littlewood-Richardson.
Una descripción más geométrica
La condición de que la secuencia de entradas leídas del cuadro en un orden algo peculiar forme una palabra reticular puede ser reemplazada por una condición más local y geométrica. Dado que en un cuadro semiestándar las entradas iguales nunca ocurren en la misma columna, se pueden numerar las copias de cualquier valor de derecha a izquierda, que es su orden de aparición en la secuencia que debería ser una palabra de celosía. Llame al número asociado a cada entrada su índice y escriba una entrada i con el índice j como i [ j ]. Ahora bien, si algún cuadro de Littlewood-Richardson contiene una entradacon índice j , entonces esa entrada i [ j ] debería aparecer en una fila estrictamente debajo de la de(lo que ciertamente también ocurre, ya que la entrada i - 1 ocurre con la misma frecuencia que la entrada i ). De hecho, la entrada i [ j ] también debería aparecer en una columna no más a la derecha que esa misma entrada(que a primera vista parece ser una condición más estricta). Si el peso del cuadro de Littlewood-Richardson se fija de antemano, entonces se puede formar una colección fija de entradas indexadas, y si estas se colocan de manera que se respeten esas restricciones geométricas, además de las de los cuadros semiestándar y la condición de que las copias indexadas de las mismas entradas deben respetar el orden de derecha a izquierda de los índices, entonces se garantiza que los cuadros resultantes serán cuadros de Littlewood-Richardson.
Una forma algorítmica de la regla
El Littlewood-Richardson como se indicó anteriormente da una expresión combinatoria para los coeficientes individuales de Littlewood-Richardson, pero no da ninguna indicación de un método práctico para enumerar los cuadros de Littlewood-Richardson con el fin de encontrar los valores de estos coeficientes. De hecho, por dado No existe un criterio simple para determinar si algún cuadro de forma Littlewood-Richardson y de peso existen en absoluto (aunque hay una serie de condiciones necesarias, la más simple de las cuales es ); por lo tanto, parece inevitable que en algunos casos uno tenga que pasar por una búsqueda elaborada, solo para encontrar que no existen soluciones.
Sin embargo, la regla conduce a un procedimiento bastante eficiente para determinar la descomposición completa de un producto de funciones de Schur, en otras palabras para determinar todos los coeficientes para λ y μ fijos, pero variando ν. Esto fija el peso de los cuadros Littlewood-Richardson que se van a construir y la "parte interior" λ de su forma, pero deja libre la "parte exterior" ν. Dado que se conoce el peso, el conjunto de entradas indexadas en la descripción geométrica es fijo. Ahora, para las sucesivas entradas indexadas, todas las posiciones posibles permitidas por las restricciones geométricas se pueden probar en una búsqueda de retroceso . Las entradas se pueden probar en orden creciente, mientras que entre entradas iguales se pueden probar con un índice decreciente . El último punto es la clave para la eficiencia del procedimiento de búsqueda: la entrada i [ j ] se restringe entonces a estar en una columna a la derecha de, pero no más a la derecha que (si tales entradas están presentes). Esto restringe fuertemente el conjunto de posiciones posibles, pero siempre deja al menos una posición válida para; por lo tanto, cada ubicación de una entrada dará lugar a al menos un cuadro completo de Littlewood-Richardson, y el árbol de búsqueda no contiene callejones sin salida.
Se puede utilizar un método similar para encontrar todos los coeficientes para λ y ν fijos, pero variando μ.
Coeficientes de Littlewood-Richardson
Los coeficientes de Littlewood-Richardson cν
λμ aparecen de las siguientes formas interrelacionadas:
- Son las constantes de estructura para el producto en el anillo de funciones simétricas con respecto a la base de funciones de Schur.
- o equivalentemente cν
λμ es el producto interno de s ν y s λ s μ .
- Expresan funciones de Schur sesgadas en términos de funciones de Schur
- La cν
λμ aparecen como números de intersección en un Grassmannian :
- donde σ μ es la clase de la variedad Schubert de un Grassmanniano correspondiente a μ .
- Cν
λμ es el número de veces la representación irreducible V λ ⊗ V μ del producto de grupos simétricos S | λ | × S | μ | aparece en la restricción de la representación V ν de S | ν | a S | λ | × S | μ | . Por reciprocidad de Frobenius, este es también el número de veces que V ν aparece en la representación de S | ν | inducida por V λ ⊗ V μ . - La cν
λμ aparecen en la descomposición del producto tensorial ( Fulton 1997 ) de dos módulos de Schur (representaciones irreductibles de grupos lineales especiales)
- Cν
λμ es el número de cuadros de Young estándar de forma ν / μ que son jeu de taquin equivalente a algún cuadro de Young estándar fijo de forma λ . - Cν
λμ es el número de cuadros de Littlewood-Richardson de forma ν / λ y de peso μ . - Cν
λμ es el número de imágenes entre μ y ν / λ.
Casos especiales
La fórmula de Pieri
La fórmula de Pieri , que es el caso especial de la regla de Littlewood-Richardson en el caso en que una de las particiones tiene solo una parte , establece que
donde S n es la función de Schur de una partición con una fila y la suma es sobre todas las particiones λ obtenidas de μ al agregar n elementos a su diagrama de Ferrers , no hay dos en la misma columna.
Tabiques rectangulares
Si ambas particiones tienen forma rectangular , la suma también es libre de multiplicidad ( Okada 1998 ). Fijar un , b , p , y q números enteros positivos con p q . Denotamos porla partición con p partes de longitud a . Las particiones que indexan componentes no triviales de son esas particiones con longitud tal que
Por ejemplo,
.
Generalizaciones
Coeficientes de Kronecker reducidos del grupo simétrico
El coeficiente de Kronecker reducido del grupo simétrico es una generalización de a tres diagramas de Young arbitrarios , que es simétrico bajo permutaciones de los tres diagramas.
Funciones Skew Schur
Zelevinsky (1981) extendió la regla de Littlewood-Richardson para sesgar las funciones de Schur de la siguiente manera:
donde la suma es sobre todos los cuadros T en μ / ν tal que para todo j , la secuencia de enteros λ + ω ( T ≥ j ) no es creciente, y ω es el peso.
Números de Newell-Littlewood
Los números de Newell-Littlewood se definen a partir de los coeficientes de Littlewood-Richardson mediante la expresión cúbica [1]
Los números de Newell-Littlewood dan algunas de las multiplicidades del producto tensorial de las representaciones de dimensión finita de los grupos de Lie clásicos de los tipos.
La condición de no desaparecer en los tamaños de diagrama de Young lleva a
Los números de Newell-Littlewood son generalizaciones de los coeficientes de Littlewood-Richardson en el sentido de que
Los números de Newell-Littlewood que involucran un diagrama de Young con solo una fila obedecen una regla tipo Pieri: es la cantidad de formas de eliminar cajas de (de diferentes columnas), luego agregue cajas (a diferentes columnas) para hacer . [1]
Los números de Newell-Littlewood son las constantes de estructura de un álgebra asociativa y conmutativa cuyos elementos básicos son particiones, con el producto . Por ejemplo,
Ejemplos de
Los ejemplos de coeficientes de Littlewood-Richardson a continuación se dan en términos de productos de polinomios de Schur S π , indexados por particiones π, usando la fórmula
Todos los coeficientes con ν como máximo 4 vienen dados por:
- S 0 S π = S π para cualquier π. donde S 0 = 1 es el polinomio de Schur de la partición vacía
- S 1 S 1 = S 2 + S 11
- S 2 S 1 = S 3 + S 21
- S 11 S 1 = S 111 + S 21
- S 3 S 1 = S 4 + S 31
- S 21 S 1 = S 31 + S 22 + S 211
- S 2 S 2 = S 4 + S 31 + S 22
- S 2 S 11 = S 31 + S 211
- S 111 S 1 = S 1111 + S 211
- S 11 S 11 = S 1111 + S 211 + S 22
La mayoría de los coeficientes para particiones pequeñas son 0 o 1, lo que ocurre en particular cuando uno de los factores es de la forma S n o S 11 ... 1 , debido a la fórmula de Pieri y su contraparte transpuesta. El ejemplo más simple con un coeficiente mayor que 1 ocurre cuando ninguno de los factores tiene esta forma:
- S 21 S 21 = S 42 + S 411 + S 33 + 2 S 321 + S 3111 + S 222 + S 2211 .
Para particiones más grandes, los coeficientes se vuelven más complicados. Por ejemplo,
- S 321 S 321 = S 642 + S 6411 + S 633 +2 S 6321 + S 63111 + S 6222 + S 62211 + S 552 + S 5511 +2 S 543 +4 S 5421 +2 S 54111 +3 S 5331 +3 S 5322 +4 S 53211 + S 531111 +2 S 52221 + S 522111 + S 444 +3 S 4431 +2 S 4422 +3 S 44211 + S 441111 +3 S 4332 +3 S 43311 +4 S 43221 +2 S 432111 + S 42222 + S 422211 + S 3333 +2 S 33321 + S 333111 + S 33222 + S 332211 con 34 términos y multiplicidad total 62, y el coeficiente más grande es 4
- S 4321 S 4321 es una suma de 206 términos con la multiplicidad total es 930 y el coeficiente más grande es 18.
- S 54321 S 54321 es una suma de 1433 términos con multiplicidad total 26704, y el coeficiente más grande (el de S 86543211 ) es 176.
- S 654321 S 654321 es una suma de 10873 términos con la multiplicidad total es 1458444 (por lo que el valor promedio de los coeficientes es más de 100 y pueden ser tan grandes como 2064).
El ejemplo original dado por Littlewood & Richardson (1934 , p. 122-124) fue (después de corregir 3 cuadros que encontraron pero se olvidaron de incluir en la suma final)
- S 431 S 221 = S 652 + S 6511 + S 643 + 2 S 6421 + S 64111 + S 6331 + S 6322 + S 63211 + S 553 + 2 S 5521 + S 55111 + 2 S 5431 + 2 S 5422 + 3 S 54211 + S 541111 + S 5332 + S 53311 + 2 S 53221 + S 532111 + S 4432 + S 44311 + 2 S 44221 + S 442111 + S 43321 + S 43222 + S 432211
con 26 términos procedentes de los siguientes 34 cuadros:
.... 11 .... 11 .... 11 .... 11 .... 11 .... 11 .... 11 .... 11 .... 11 ... 22 ... 22 ... 2 ... 2 ... 2 ... 2 ... ... ....3. .23 .2 .3. .22 .2 .2 3 3 2 2 3 23 2 3 3.... 1 .... 1 .... 1 .... 1 .... 1 .... 1 .... 1 .... 1 .... 1 ... 12 ... 12 ... 12 ... 12 ... 1 ... 1 ... 1 ... 2 ... 1.23 .2 .3. .23 .22 .2 .1 .2 3 2 2 2 3 23 23 2 3 3.... 1 .... 1 .... 1 .... 1 .... 1 .... 1 .... 1 .... 1 ... 2 ... 2 ... 2 ... ... ... ... ... .1 .3. .12 .12 .1 .2 .2 2 1 1 23 2 22 13 13 2 2 3 3 2 2 3 3.... .... .... .... .... .... .... .... .... ... 1 ... 1 ... 1 ... 1 ... 1 ... ... ... .12 .12 .1 .2 .2 .11 .1 .1 23 2 22 13 1 22 12 12 3 3 2 2 3 23 2 3 3
El cálculo de funciones de Schur de sesgo es similar. Por ejemplo, los 15 cuadros de Littlewood-Richardson para ν = 5432 y λ = 331 son
... 11 ... 11 ... 11 ... 11 ... 11 ... 11 ... 11 ... 11 ... 11 ... 11 ... 11 ... 11 ... .11 ... 11 ... 11... 2 ... 2 ... 2 ... 2 ... 2 ... 2 ... 2 ... 2 ... 2 ... 2 ... 2 ... 2 .. .2 ... 2 ... 2.11 .11 .11 .12 .11 .12 .13 .13 .23 .13 .13 .12 .12 .23 .2312 13 22 12 23 13 12 24 14 14 22 23 33 13 34
entonces S 5432/331 = Σ cν
λμ S μ = S 52 + S 511 + S 4111 + S 2221 + 2 S 43 + 2 S 3211 + 2 S 322 + 2 S 331 + 3 S 421 ( Fulton 1997 , p. 64).
Notas
- ^ a b Gao, Shiliang; Orelowitz, Gidon; Yong, Alexander (18 de mayo de 2020). "Números de Newell-Littlewood". arXiv : 2005.09012v1 [ math.CO ].
Referencias
- Fulton, William (1997), Young tableaux , London Mathematical Society Student Texts, 35 , Cambridge University Press , pág. 121, ISBN 978-0-521-56144-0, Señor 1464693
- Gasharov, Vesselin (1998), "A short proof of the Littlewood-Richardson rule" , European Journal of Combinatorics , 19 (4): 451–453, doi : 10.1006 / eujc.1998.0212 , ISSN 0195-6698 , MR 1630540
- James, Gordon (1987), "La teoría de la representación de los grupos simétricos", The Arcata Conference on Representations of Finite Groups (Arcata, Calif., 1986) , Proc. Simpos. Pure Math., 47 , Providence, RI: American Mathematical Society , págs. 111-126, MR 0933355
- Knuth, Donald E. (1970), "Permutaciones, matrices y cuadros de Young generalizados" , Pacific Journal of Mathematics , 34 (3): 709–727, doi : 10.2140 / pjm.1970.34.709 , ISSN 0030-8730 , MR 0272654
- Littelmann, Peter (1994), "Una regla de Littlewood-Richardson para álgebras Kac-Moody simetrizables" (PDF) , Invent. Matemáticas. , 116 : 329–346, Bibcode : 1994InMat.116..329L , doi : 10.1007 / BF01231564 , S2CID 85546837
- Littlewood, Dudley E. (1950), La teoría de los caracteres grupales y las representaciones matriciales de grupos , AMS Chelsea Publishing, Providence, RI, ISBN 978-0-8218-4067-2, MR 0002127
- Littlewood, DE; Richardson, AR (1934), "Caracteres grupales y álgebra", Transacciones filosóficas de la Royal Society de Londres. Serie A, que contiene artículos de carácter matemático o físico , The Royal Society, 233 (721–730): 99–141, Bibcode : 1934RSPTA.233 ... 99L , doi : 10.1098 / rsta.1934.0015 , ISSN 0264-3952 , JSTOR 91293
- Macdonald, IG (1995), Funciones simétricas y polinomios de Hall , Oxford Mathematical Monographs (2a ed.), The Clarendon Press Oxford University Press, ISBN 978-0-19-853489-1, MR 1354144 , archivado desde el original el 11 de diciembre de 2012
- Okada, Soichi (1998), "Aplicaciones de fórmulas de suma menor a representaciones de forma rectangular de grupos clásicos", Journal of Algebra , 205 (2): 337–367, doi : 10.1006 / jabr.1997.7408 , ISSN 0021-8693 , MR 1632816
- Robinson, G. de B. (1938), "Sobre las representaciones del grupo simétrico", American Journal of Mathematics , The Johns Hopkins University Press, 60 (3): 745–760, doi : 10.2307 / 2371609 , ISSN 0002- 9327 , JSTOR 2371609 Zbl 0019.25102
- Schensted, C. (1961), "Las subsecuencias crecientes y decrecientes más largas" , Canadian Journal of Mathematics , 13 : 179-191, doi : 10.4153 / CJM-1961-015-3 , ISSN 0008-414X , MR 0121305
- Schützenberger, MP (1963), "Quelques remarques sur une construction de Schensted" , Mathematica Scandinavica , 12 : 117-128, doi : 10.7146 / math.scand.a-10676 , ISSN 0025-5521 , MR 0190017[ enlace muerto permanente ]
- Schützenberger, Marcel-Paul (1977), "La correspondance de Robinson" , Combinatoire et représentation du groupe symétrique (Actes Table Ronde CNRS, Univ. Louis-Pasteur Estrasburgo, Estrasburgo, 1976) , Lecture Notes in Mathematics, 579 , Berlín, Nueva York: Springer-Verlag , págs. 59-113 , doi : 10.1007 / BFb0090012 , ISBN 978-3-540-08143-2, MR 0498826
- Stembridge, John R. (2002), "Una prueba concisa de la regla de Littlewood-Richardson" (PDF) , Electronic Journal of Combinatorics , 9 (1): Nota 5, 4 págs. (Electrónico), doi : 10.37236 / 1666 , ISSN 1077-8926 , MR 1912814
- Thomas, Glânffrwd P. (1974), álgebras de Baxter y funciones de Schur , Ph.D. Tesis, Swansea: University College of Swansea
- van Leeuwen, Marc AA (2001), "La regla de Littlewood-Richardson y combinatoria relacionada" (PDF) , Interacción de la combinatoria y la teoría de la representación , MSJ Mem., 11 , Tokio: Matemáticas. Soc. Japón, págs. 95-145, MR 1862150
- Zelevinsky, AV (1981), "Una generalización de la regla Littlewood-Richardson y la correspondencia Robinson-Schensted-Knuth", Journal of Algebra , 69 (1): 82-94, doi : 10.1016 / 0021-8693 (81) 90128 -9 , ISSN 0.021 a 8693 , MR 0613858
enlaces externos
- Un programa en línea que descompone productos de funciones de Schur utilizando la regla de Littlewood-Richardson