En matemática combinatoria , un sistema Steiner (llamado así por Jakob Steiner ) es un tipo de diseño de bloque , específicamente un diseño t con λ = 1 y t ≥ 2.
Sistema de A Steiner con los parámetros t , k , n S, escrito ( t , k , n ), es un n -elemento conjunto S junto con un conjunto de k -elemento subconjuntos de S (llamados bloques ) con la propiedad de que cada t - El subconjunto de elementos de S está contenido exactamente en un bloque. En una notación alternativa para diseños de bloques, un diseño S ( t , k , n ) sería un diseño t - ( n , k , 1).
Esta definición es relativamente nueva. La definición clásica de los sistemas Steiner también requería que k = t + 1. Un S (2,3, n ) se llamaba (y todavía se llama ) sistema Steiner triple (o tríada ) , mientras que un S (3,4, n ) se denomina sistema cuádruple Steiner , etc. Con la generalización de la definición, este sistema de nomenclatura ya no se cumple estrictamente.
Los problemas de larga data en la teoría del diseño fueron si existe algún sistema Steiner no trivial (significado no trivial t < k < n ) con t ≥ 6; también si infinitos tienen t = 4 o 5. [1] Peter Keevash demostró ambas existencias en 2014. Su prueba no es constructiva y, a partir de 2019, no se conocen sistemas Steiner reales para valores grandes de t . [2] [3] [4]
Tipos de sistemas Steiner
Un plano proyectivo finito de orden q , con las rectas como bloques, es un S (2, q + 1, q 2 + q + 1) , ya que tiene q 2 + q + 1 puntos, cada recta pasa por q + 1 puntos, y cada par de puntos distintos se encuentra exactamente en una línea.
Un plano afín finito de orden q , con las líneas como bloques, es un S (2, q , q 2 ) . Se puede obtener un plano afín de orden q a partir de un plano proyectivo del mismo orden eliminando un bloque y todos los puntos de ese bloque del plano proyectivo. La elección de diferentes bloques para eliminar de esta manera puede conducir a planos afines no isomórficos.
Un S (3,4, n ) se denomina sistema cuádruple de Steiner . Una condición necesaria y suficiente para la existencia de un S (3,4, n ) es que n 2 o 4 (mod 6). La abreviatura SQS ( n ) se utiliza a menudo para estos sistemas. Hasta el isomorfismo, SQS (8) y SQS (10) son únicos, hay 4 SQS (14) sy 1,054,163 SQS (16) s. [5]
Un S (4,5, n ) se denomina sistema quíntuple de Steiner . Una condición necesaria para la existencia de tal sistema es que n 3 o 5 (mod 6) que proviene de consideraciones que se aplican a todos los sistemas Steiner clásicos. Una condición adicional necesaria es que n 4 (mod 5), que proviene del hecho de que el número de bloques debe ser un número entero. No se conocen condiciones suficientes. Hay un sistema quíntuple de Steiner único de orden 11, pero ninguno de orden 15 ni de orden 17. [6] Se conocen sistemas para las órdenes 23, 35, 47, 71, 83, 107, 131, 167 y 243. La orden más pequeña para cuya existencia se desconoce (a partir de 2011) es 21.
Sistemas triples Steiner
Un S (2,3, n ) se denomina sistema triple de Steiner y sus bloques se denominan triples . Es común ver la abreviatura STS ( n ) para un sistema triple Steiner de orden n . El número total de pares es n (n-1) / 2 , de los cuales tres aparecen en un triple, por lo que el número total de triples es n ( n −1) / 6. Esto muestra que n debe tener la forma 6k + 1 o 6k + 3 para algunos k . El hecho de que esta condición en n es suficiente para la existencia de una S (2,3, n ) fue demostrado por Raj Chandra Bose [7] y T. Skolem. [8] El plano proyectivo de orden 2 (el plano de Fano ) es un STS (7) y el plano afín de orden 3 es un STS (9). Hasta el isomorfismo, STS (7) y STS (9) son únicos, hay dos STS (13) s, 80 STS (15) sy 11,084,874,829 STS (19) s. [9]
Algunos de los sistemas S (2,3, n) pueden tener sus bloques divididos en (n-1) / 2 conjuntos de (n / 3) triples cada uno. Esto se llama resolubles y tales sistemas se denominan sistemas triples de Kirkman en honor a Thomas Kirkman , quien estudió dichos sistemas resolubles antes que Steiner. Dale Mesner, Earl Kramer y otros investigaron colecciones de sistemas triples Steiner que son mutuamente inconexos (es decir, no hay dos sistemas Steiner en una colección de este tipo que compartan un triplete común). Se sabe (Bays 1917, Kramer & Mesner 1974) que se pueden generar siete sistemas S (2, 3, 9) diferentes para cubrir juntos los 84 tripletes en un conjunto de 9; También sabían que hay 15360 formas diferentes de encontrar tales 7 conjuntos de soluciones, que se reducen a dos soluciones no isomorfas bajo reetiquetado, con multiplicidades 6720 y 8640 respectivamente. La pregunta correspondiente para encontrar trece sistemas separados S (2,3,15) diferentes fue formulada por James Sylvester en 1860 y respondida por RHF Denniston en 1974. Existe al menos uno de esos 13 conjuntos de S (2,3,15) pero se desconoce su isomorfismo.
Podemos definir una multiplicación en el conjunto S usando el sistema triple de Steiner estableciendo aa = a para todo a en S , y ab = c si { a , b , c } es un triple. Esto hace que S un idempotente , conmutativa cuasigrupo . Tiene la propiedad adicional de que ab = c implica bc = una y ca = b . [10] Por el contrario, cualquier cuasigrupo (finito) con estas propiedades surge de un sistema triple de Steiner. Los cuasigrupos conmutativos idempotentes que satisfacen esta propiedad adicional se denominan cuasigrupos de Steiner . [11]
Propiedades
De la definición de S ( t , k , n ) se desprende claramente que. (Las igualdad, aunque técnicamente posibles, conducen a sistemas triviales).
Si S ( t , k , n ) existe, entonces tomar todos los bloques que contienen un elemento específico y descartar ese elemento da un sistema derivado S ( t −1, k −1, n −1) . Por tanto, la existencia de S ( t −1, k −1, n −1) es una condición necesaria para la existencia de S ( t , k , n ) .
El número de subconjuntos de elementos t en S es, mientras que el número de subconjuntos de elementos t en cada bloque es. Dado que cada subconjunto de elementos t está contenido exactamente en un bloque, tenemos, o
donde b es el número de bloques. Un razonamiento similar sobre los subconjuntos de elementos t que contienen un elemento en particular nos da, o
- =
donde r es el número de bloques que contienen cualquier elemento dado. De estas definiciones sigue la ecuación. Es una condición necesaria para la existencia de S ( t , k , n ) que b y r son números enteros. Como con cualquier diseño de bloque, la desigualdad de Fisher es cierto en los sistemas Steiner.
Dados los parámetros de un sistema Steiner S ( t, k, n ) y un subconjunto de tamaño, contenido en al menos un bloque, se puede calcular el número de bloques que cruzan ese subconjunto en un número fijo de elementos construyendo un triángulo de Pascal . [12] En particular, el número de bloques que se cruzan con un bloque fijo en cualquier número de elementos es independiente del bloque elegido.
El número de bloques que contienen cualquier conjunto de puntos de elementos i es:
Se puede demostrar que si existe un sistema Steiner S (2, k , n ) , donde k es una potencia prima mayor que 1, entonces n 1 o k (mod k ( k −1)) . En particular, un sistema triple Steiner S (2, 3, n ) debe tener n = 6 m + 1 o 6 m + 3 . Y como ya hemos mencionado, esta es la única restricción en los sistemas triples de Steiner, es decir, para cada número natural m , los sistemas S (2, 3, 6 m + 1) y S (2, 3, 6 m + 3) existe.
Historia
Los sistemas triples de Steiner fueron definidos por primera vez por Wesley SB Woolhouse en 1844 en la pregunta del premio n. ° 1733 de Lady's and Gentlemen's Diary. [13] El problema planteado fue resuelto por Thomas Kirkman ( 1847 ). En 1850, Kirkman planteó una variación del problema conocido como problema de colegiala de Kirkman , que pide que los sistemas triples tengan una propiedad adicional (resolubilidad). Sin darse cuenta del trabajo de Kirkman, Jakob Steiner ( 1853 ) reintrodujo los sistemas triples, y como este trabajo era más conocido, los sistemas fueron nombrados en su honor.
Grupos de Mathieu
Varios ejemplos de sistemas Steiner están estrechamente relacionados con la teoría de grupos . En particular, los grupos simples finitos llamados grupos de Mathieu surgen como grupos de automorfismo de los sistemas Steiner:
- El grupo de Mathieu M 11 es el grupo de automorfismo de un sistema Steiner S (4,5,11)
- El grupo de Mathieu M 12 es el grupo de automorfismo de un sistema Steiner S (5,6,12)
- El grupo Mathieu M 22 es el subgrupo de índice 2 único del grupo de automorfismo de un sistema Steiner S (3,6,22)
- El grupo Mathieu M 23 es el grupo de automorfismo de un sistema Steiner S (4,7,23)
- El grupo de Mathieu M 24 es el grupo de automorfismo de un sistema Steiner S (5,8,24).
El sistema Steiner S (5, 6, 12)
Hay un sistema Steiner S (5,6,12) único; su grupo de automorfismo es el grupo de Mathieu M 12 , y en ese contexto se denota por W 12 .
Construcción de línea proyectiva
Esta construcción se debe a Carmichael (1937). [14]
Agrega un nuevo elemento, llámalo ∞ , a los 11 elementos del campo finito F 11 (es decir, los enteros mod 11). Este conjunto, S , de 12 elementos se puede identificar formalmente con los puntos de la línea proyectiva sobre F 11 . Llame al siguiente subconjunto específico de tamaño 6,
un "bloque" (contiene ∞ junto con los 5 cuadrados distintos de cero en F 11 ). A partir de este bloque, obtenemos los otros bloques del sistema S (5,6,12) aplicando repetidamente las transformaciones fraccionarias lineales :
donde a, b, c, d están en F 11 y ad - bc = 1 . Con las convenciones habituales de definir f (- d / c ) = ∞ y f (∞) = a / c , estas funciones mapean el conjunto S sobre sí mismo. En lenguaje geométrico, son proyectividades de la línea proyectiva. Forman un grupo bajo composición que es el grupo lineal especial proyectivo PSL (2,11) de orden 660. Hay exactamente cinco elementos de este grupo que dejan el bloque inicial fijo en forma secuencial, [15] a saber, aquellos tales que b = c = 0 y ad = 1 de modo que f (z) = a 2 z . Entonces habrá 660/5 = 132 imágenes de ese bloque. Como consecuencia de la propiedad transitiva múltiple de este grupo que actúa sobre este conjunto, cualquier subconjunto de cinco elementos de S aparecerá exactamente en una de estas 132 imágenes de tamaño seis.
Construcción de gatitos
Se obtiene una construcción alternativa de W 12 mediante el uso del 'gatito' de RT Curtis, [16] que fue pensado como una "calculadora de mano" para escribir bloques de uno en uno. El método del gatito se basa en completar patrones en una cuadrícula de números de 3x3, que representan una geometría afín en el espacio vectorial F 3 xF 3 , un sistema S (2,3,9).
Construcción a partir de factorización de gráficos K 6
Las relaciones entre los factores del gráfico del gráfico completo K 6 generan un S (5,6,12). [17] El gráfico AK 6 tiene 6 vértices, 15 aristas, 15 emparejamientos perfectos y 6 factorizaciones 1 diferentes (formas de dividir los bordes en emparejamientos perfectos disjuntos). El conjunto de vértices (etiquetado 123456) y el conjunto de factorizaciones (etiquetado ABCDEF ) proporcionan un bloque cada uno. Cada par de factorizaciones tiene exactamente una combinación perfecta en común. Suponga que las factorizaciones A y B tienen la coincidencia común con las aristas 12, 34 y 56. Agregue tres bloques nuevos AB 3456, 12 AB 56 y 1234 AB , reemplazando cada arista en la coincidencia común con las etiquetas de factorización a su vez. De manera similar, agregue tres bloques más 12 CDEF , 34 CDEF y 56 CDEF , reemplazando las etiquetas de factorización por las etiquetas de borde correspondientes de la coincidencia común. Haga esto para los 15 pares de factorizaciones para agregar 90 bloques nuevos. Finalmente, tome el conjunto completo decombinaciones de 6 objetos de 12, y descartar cualquier combinación que tenga 5 o más objetos en común con cualquiera de los 92 bloques generados hasta el momento. Quedan exactamente 40 bloques, lo que da como resultado 2 + 90 + 40 = 132 bloques de la S (5,6,12). Este método funciona porque hay un automorfismo externo en el grupo simétrico S 6 , que asigna los vértices a las factorizaciones y los bordes a las particiones. Permutar los vértices hace que las factorizaciones se permuten de manera diferente, de acuerdo con el automorfismo externo.
El sistema Steiner S (5, 8, 24)
El sistema Steiner S (5, 8, 24), también conocido como diseño de Witt o geometría de Witt , fue descrito por primera vez por Carmichael ( 1931 ) y redescubierto por Witt ( 1938 ). Este sistema está conectado con muchos de los grupos simples esporádicos y con la celosía excepcional de 24 dimensiones conocida como celosía Leech . El grupo de automorfismo de S (5, 8, 24) es el grupo de Mathieu M 24 , y en ese contexto el diseño se denota W 24 ("W" para "Witt")
Generación lexicográfica directa
Todos los subconjuntos de 8 elementos de un conjunto de 24 elementos se generan en orden lexicográfico, y cualquier subconjunto que difiera de algún subconjunto ya encontrado en menos de cuatro posiciones se descarta.
La lista de octadas para los elementos 01, 02, 03, ..., 22, 23, 24 es entonces:
- 01 02 03 04 05 06 07 08
- 01 02 03 04 09 10 11 12
- 01 02 03 04 13 14 15 16
- .
- . (se omiten las siguientes 753 octadas)
- .
- 13 14 15 16 17 18 19 20
- 13 14 15 16 21 22 23 24
- 17 18 19 20 21 22 23 24
Cada elemento aparece 253 veces en algún lugar de algún octado. Cada par ocurre 77 veces. Cada triple ocurre 21 veces. Cada cuádruple (tétrada) ocurre 5 veces. Cada quintuplo (pentad) ocurre una vez. No todos los hexadas, heptadas u octadas ocurren.
Construcción a partir del código binario de Golay
Se generan las 4096 palabras de código del código binario Golay de 24 bits y las 759 palabras de código con un peso Hamming de 8 corresponden al sistema S (5,8,24).
El código Golay se puede construir mediante muchos métodos, como generar todas las cadenas binarias de 24 bits en orden lexicográfico y descartar aquellas que difieren de alguna anterior en menos de 8 posiciones . El resultado se ve así:
000000000000000000000000 000000000000000011111111 000000000000111100001111 . . (se omiten las siguientes 4090 cadenas de 24 bits) . 111111111111000011110000 111111111111111100000000 111111111111111111111111
Las palabras de código forman un grupo bajo la operación XOR .
Construcción de línea proyectiva
Esta construcción se debe a Carmichael (1931). [18]
Agrega un nuevo elemento, llámalo ∞ , a los 23 elementos del campo finito F 23 (es decir, los enteros mod 23). Este conjunto, S , de 24 elementos se puede identificar formalmente con los puntos de la línea proyectiva sobre F 23 . Llame al siguiente subconjunto específico de tamaño 8,
un bloque". (Podemos tomar cualquier octado del código Golay binario extendido , visto como un código de residuo cuadrático). De este bloque, obtenemos los otros bloques del sistema S (5,8,24) aplicando repetidamente las transformaciones fraccionarias lineales :
donde a, b, c, d están en F 23 y ad - bc = 1 . Con las convenciones habituales de definir f (- d / c ) = ∞ y f (∞) = a / c , estas funciones mapean el conjunto S sobre sí mismo. En lenguaje geométrico, son proyectividades de la línea proyectiva. Forman un grupo bajo composición que es el grupo lineal especial proyectivo PSL (2,23) de orden 6072. Hay exactamente 8 elementos de este grupo que dejan el bloque inicial fijo en forma. Entonces habrá 6072/8 = 759 imágenes de ese bloque. Estos forman las octadas de S (5,8,24).
Construcción del generador Miracle Octad
El Miracle Octad Generator (MOG) es una herramienta para generar octads, como los que contienen subconjuntos especificados. Consiste en una matriz de 4x6 con ciertos pesos asignados a las filas. En particular, un subconjunto de 8 debe obedecer tres reglas para ser un octado de S (5,8,24). Primero, cada una de las 6 columnas debe tener la misma paridad , es decir, todas deben tener un número impar de celdas o todas deben tener un número par de celdas. En segundo lugar, la fila superior debe tener la misma paridad que cada una de las columnas. En tercer lugar, las filas se multiplican respectivamente por los pesos 0, 1, 2 y 3 sobre el campo finito de orden 4 , y las sumas de columna se calculan para las 6 columnas, con multiplicación y suma utilizando las definiciones aritméticas de campo finito. Las sumas de columna resultantes deben formar una palabra hexacodificada válida de la forma ( a , b , c , a + b + c , 3a + 2b + c , 2a + 3b + c ) donde a, b, c también son del campo finito de orden 4. Si las paridades de las sumas de las columnas no coinciden con la paridad de las sumas de las filas, o entre sí, o si no existen a, b, c tales que las sumas de las columnas formen una palabra hexacódigo válida, entonces ese subconjunto de 8 no es un octado de S (5,8,24).
El MOG se basa en la creación de una biyección (Conwell 1910, "El PG de tres espacios (3,2) y su grupo") entre las 35 formas de dividir un conjunto de 8 en dos conjuntos de 4 diferentes, y las 35 líneas de el Fano PG de 3 espacios (3,2). También está relacionado geométricamente (Cullinane, "Symmetry Invariance in a Diamond Ring", Notices of the AMS, pp A193-194, febrero de 1979) con las 35 formas diferentes de dividir una matriz 4x4 en 4 grupos diferentes de 4 celdas cada uno, como que si la matriz de 4x4 representa un espacio afín finito de cuatro dimensiones , entonces los grupos forman un conjunto de subespacios paralelos.
Ver también
- Código de peso constante
- El problema de la colegiala de Kirkman
- Configuración de Sylvester-Gallai
Notas
- ^ "Enciclopedia de la teoría del diseño: t-Designs" . Designtheory.org. 2004-10-04 . Consultado el 17 de agosto de 2012 .
- ^ Keevash, Peter (2014). "La existencia de diseños". arXiv : 1401.3665 [ math.CO ].
- ^ "Un dilema de diseño resuelto, menos diseños" . Revista Quanta. 2015-06-09 . Consultado el 27 de junio de 2015 .
- ^ Kalai, Gil. "¡Los diseños existen!" (PDF) . S´eminaire BOURBAKI.
- ^ Colbourn y Dinitz 2007 , pág. 106
- ^ Östergard y Pottonen 2008
- ^ Bose, RC (1939). "Sobre la construcción de diseños de bloques incompletos equilibrados" . Anales de la eugenesia . 9 (4): 353–399. doi : 10.1111 / j.1469-1809.1939.tb02219.x .
- ^ T. Skolem. Algunas observaciones sobre los sistemas triples de Steiner. Matemáticas. Scand. 6 (1958), 273–280.
- ^ Colbourn y Dinitz 2007 , pág.60
- ^ Esta propiedad es equivalente a decir que (xy) y = x para todo xey en el cuasigrupo conmutativo idempotente.
- ^ Colbourn y Dinitz 2007 , pág. 497, definición 28.12
- ^ Assmus y Key 1994 , pág. 8
- ^ Lindner y Rodger 1997 , pág. 3
- ↑ Carmichael , 1956 , p. 431
- ^ Beth, Jungnickel y Lenz 1986 , p. 196
- ^ Curtis 1984
- ^ Libro de texto de EAGTS
- ^ Carmichael, 1931
Referencias
- Assmus, EF Jr .; Key, JD (1994), "8. Steiner Systems", Diseños y sus códigos , Cambridge University Press , págs. 295–316, ISBN 978-0-521-45839-9.
- Assmus, EF; Key, JD (1992), Diseños y sus códigos , Cambridge: Cambridge University Press, ISBN 978-0-521-41361-9
- Beth, Thomas; Jungnickel, Dieter ; Lenz, Hanfried (1986), Teoría del diseño , Cambridge: Cambridge University Press. 2ª ed. (1999) ISBN 978-0-521-44432-3 .
- Carmichael, Robert (1931), "Configuraciones tácticas de rango dos", American Journal of Mathematics , 53 (1): 217-240, doi : 10.2307 / 2370885 , JSTOR 2370885
- Carmichael, Robert D. (1956) [1937], Introducción a la teoría de grupos de orden finito , Dover, ISBN 978-0-486-60300-1
- Colbourn, Charles J .; Dinitz, Jeffrey H. (1996), Manual de diseños combinatorios , Boca Raton: Chapman & Hall / CRC, ISBN 978-0-8493-8948-1, Zbl 0836.00010
- Colbourn, Charles J .; Dinitz, Jeffrey H. (2007), Manual de diseños combinatorios (2a ed.), Boca Raton: Chapman & Hall / CRC, ISBN 978-1-58488-506-1, Zbl 1101.05001
- Curtis, RT (1984), "El sistema Steiner S (5,6,12), el grupo Mathieu M 12 y el" gatito " ", en Atkinson, Michael D. (ed.), Teoría de grupo computacional (Durham, 1982 ) , Londres: Academic Press, págs. 353–358, ISBN 978-0-12-066270-8, MR 0760669
- Hughes, DR; Piper, FC (1985), Design Theory , Cambridge University Press, págs. 173-176, ISBN 978-0-521-35872-9.
- Kirkman, Thomas P. (1847), "Sobre un problema de combinaciones", The Cambridge and Dublin Mathematical Journal , II : 191-204.
- Lindner, CC; Rodger, CA (1997), Teoría del diseño , Boca Raton: CRC Press, ISBN 978-0-8493-3986-8
- Östergard, Patric RJ; Pottonen, Olli (2008), "No existe ningún sistema Steiner S (4,5,17)", Journal of Combinatorial Theory, Serie A , 115 (8): 1570-1573, doi : 10.1016 / j.jcta.2008.04. 005
- Steiner, J. (1853), "Combinatorische Aufgabe" (PDF) , Journal für die Reine und Angewandte Mathematik , 1853 (45): 181-182, doi : 10.1515 / crll.1853.45.181.
- Witt, Ernst (1938), "Die 5-Fach transitiven Gruppen von Mathieu", Abh. Matemáticas. Sem. Univ. Hamburgo , 12 : 256–264, doi : 10.1007 / BF02948947
enlaces externos
- Rowland, Todd y Weisstein, Eric W. "Sistema Steiner" . MathWorld .
- Rumov, BT (2001) [1994], "Sistema Steiner" , Enciclopedia de Matemáticas , EMS Press
- Sistemas Steiner de Andries E. Brouwer
- Implementación de S (5,8,24) por el Dr. Alberto Delgado, Gabe Hart y Michael Kolkebeck
- Software y listado S (5, 8, 24) de Johan E. Mebius