En matemáticas combinatorias , un sistema Steiner (llamado así por Jakob Steiner ) es un tipo de diseño de bloques , específicamente un diseño t con λ = 1 y t = 2 o (recientemente) t ≥ 2.
Un sistema Steiner con parámetros t , k , n , escrito S( t , k , n ), es un conjunto de n elementos S junto con un conjunto de k subconjuntos de elementos 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 triple (o tríada ) de Steiner , mientras que un S(3,4, n ) se llama sistema cuádruple de Steiner , y así sucesivamente. Con la generalización de la definición, este sistema de denominación ya no se respeta estrictamente.
Los problemas de larga data en la teoría del diseño fueron si existen sistemas Steiner no triviales (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]
Un plano proyectivo finito de orden q , con las rectas como bloques, es un S(2, q + 1, q 2 + q + 1) , como 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. Elegir diferentes bloques para eliminar de esta manera puede conducir a planos afines no isomorfos.
Un S(3,4, n ) se llama 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) y 1.054.163 SQS(16). [5]
Un S(4,5, n ) se llama sistema quíntuple de Steiner . Una condición necesaria para la existencia de tal sistema es que n 3 o 5 (mod 6) proviene de consideraciones que se aplican a todos los sistemas clásicos de Steiner. 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. Se desconocen las condiciones suficientes. Existe un sistema quíntuple de Steiner único de orden 11, pero ninguno de orden 15 o 17. [6] Se conocen sistemas de órdenes 23, 35, 47, 71, 83, 107, 131, 167 y 243. El orden más pequeño para cuya existencia se desconoce (a partir de 2011) es 21.
Un S(2,3, n ) se llama sistema triple de Steiner , y sus bloques se llaman 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 triplete, por lo que el número total de tripletes es n ( n −1)/6. Esto muestra que n debe ser de 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 un 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, el STS(7) y el STS(9) son únicos, hay dos STS(13), 80 STS(15) y 11.084.874.829 STS(19). [9]
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 convierte a S en un cuasigrupo conmutativo idempotente . Tiene la propiedad adicional de que ab = c implica bc = a y ca = b . [nota 1] Por el contrario, cualquier cuasigrupo (finito) con estas propiedades surge de un sistema triple de Steiner. Los cuasigrupos idempotentes conmutativos que satisfacen esta propiedad adicional se denominan cuasigrupos de Steiner . [10]
Algunos de los sistemas S(2,3,n) pueden tener sus tripletas divididas en (n-1)/2 conjuntos, cada uno de los cuales tiene (n/3) tripletas disjuntas por pares. Esto se llama resoluble y tales sistemas se llaman sistemas triples de Kirkman en honor a Thomas Kirkman , quien estudió tales sistemas resolubles antes que Steiner. Dale Mesner, Earl Kramer y otros investigaron colecciones de sistemas triples de Steiner que son mutuamente disjuntos (es decir, no hay dos sistemas Steiner en tal colección que compartan un triplete común). Se sabe (Bays 1917, Kramer y 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 S(2,3,15) disjuntos diferentes fue formulada por James Sylvester en 1860 como una extensión del problema de las colegialas de Kirkman , es decir, si las colegialas de Kirkman podían marchar durante un período completo de 13 semanas sin ningún triplete de las niñas se repiten durante todo el trimestre. La cuestión fue resuelta por RHF Denniston en 1974, [11] quien construyó la Semana 1 de la siguiente manera:
Día 1 ABJ CEM FKL HIN DGODía 2 ACH DEI FGM JLN BKODía 3 ADL BHM GIK CFN EJODía 4 AEG BIL CJK DMN FHODía 5 AFI BCD GHJ EKN LMODía 6 AKM DFJ EHL BGN CIODía 7 BEF CGL DHK IJM ANO
para niñas etiquetadas de A a O, y construyó la solución de cada semana subsiguiente a partir de su predecesor inmediato cambiando A por B, B por C, ... L por M y M nuevamente por A, todo ello dejando N y O sin cambios. La solución de la Semana 13, al someterse a ese reetiquetado, vuelve a la solución de la Semana 1. Denniston informó en su artículo que la búsqueda que empleó tomó 7 horas en una computadora Elliott 4130 en la Universidad de Leicester , e inmediatamente terminó la búsqueda al encontrar la solución anterior, sin buscar establecer la unicidad. El número de soluciones no isomorfas al problema de Sylvester sigue siendo desconocido en 2021.
De la definición de S( t , k , n ) se desprende claramente que . (Las igualdades, 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 lo 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 subconjuntos de elementos t que contienen un elemento particular nos da , o
donde r es el número de bloques que contienen cualquier elemento dado. De estas definiciones se sigue la ecuación . Es una condición necesaria para la existencia de S( t , k , n ) que b y r sean números enteros. Como ocurre con cualquier diseño de bloques, la desigualdad de Fisher es cierta 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 cruzan 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 i -elemento 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 de 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) existir.
Los sistemas triples Steiner fueron definidos por primera vez por Wesley SB Woolhouse en 1844 en la pregunta del premio n.° 1733 del Diario de damas y caballeros. [13] El problema planteado fue resuelto por Thomas Kirkman (1847). En 1850, Kirkman planteó una variación del problema conocido como problema de la colegiala de Kirkman , que solicita sistemas triples que tengan una propiedad adicional (resolvebilidad). Sin conocer el trabajo de Kirkman, Jakob Steiner (1853) reintrodujo los sistemas triples y, como este trabajo fue más conocido, los sistemas recibieron su nombre.
Varios ejemplos de sistemas Steiner están estrechamente relacionados con la teoría de grupos . En particular, los grupos finitos simples llamados grupos de Mathieu surgen como grupos de automorfismos de sistemas Steiner:
Existe 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 .
Esta construcción se debe a Carmichael (1937). [14]
Agrega un nuevo elemento, llámalo ∞ , a los 11 elementos del cuerpo finito F 11 (es decir, los enteros mod 11). Este conjunto, S , de 12 elementos puede identificarse 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 ). 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 asignan el conjunto S a 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 sentido establecido, [15] es decir, 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.
Se obtiene una construcción alternativa de W 12 mediante el uso del 'gatito' de RT Curtis, [16] que fue concebido como una "calculadora manual" 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).
Las relaciones entre los factores del gráfico completo K 6 generan una S(5,6,12). [17] El gráfico AK 6 tiene 6 vértices, 15 aristas, 15 coincidencias perfectas y 6 factorizaciones 1 diferentes (formas de dividir las aristas en coincidencias perfectas disjuntas). 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 coincidencia perfecta en común. Supongamos que las factorizaciones A y B tienen la coincidencia común con los bordes 12, 34 y 56. Agregue tres nuevos bloques AB 3456, 12 AB 56 y 1234 AB , reemplazando cada borde 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, toma el conjunto completo de combinaciones de 6 objetos de 12, y descarta 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 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 factorizaciones y las aristas a 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), 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 excepcional red de 24 dimensiones conocida como red 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")
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 que ya se encuentre en menos de cuatro posiciones se descarta.
La lista de octadas para los elementos 01, 02, 03, ..., 22, 23, 24 es entonces:
Cada elemento aparece 253 veces en algún lugar de una octada. Cada par ocurre 77 veces. Cada triple ocurre 21 veces. Cada cuádruple (tétrada) ocurre 5 veces. Cada quíntuple (pentada) ocurre una vez. No todas las hexadecimales, heptadas u octadas ocurren.
Se generan las 4096 palabras de código del código Golay binario 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í:
0000000000000000000000000 000000000000000011111111 000000000000111100001111 . . (se omiten las siguientes cadenas 4090 de 24 bits) . 111111111111000011110000 111111111111111100000000 111111111111111111111111
Las palabras de código forman un grupo bajo la operación XOR .
Esta construcción se debe a Carmichael (1931). [18]
Agrega un nuevo elemento, llámalo ∞ , a los 23 elementos del cuerpo finito F 23 (es decir, los enteros mod 23). Este conjunto, S , de 24 elementos puede identificarse 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 octada 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 asignan el conjunto S a 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 sentido establecido. Entonces habrá 6072/8 = 759 imágenes de ese bloque. Estos forman las octadas de S (5,8,24).
Miracle Octad Generator (MOG) es una herramienta para generar octadas, como aquellas que contienen subconjuntos específicos. 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 una octada 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 las columnas se calculan para las 6 columnas, con la multiplicación y la suma utilizando las definiciones aritméticas de campos finitos. Las sumas de las columnas resultantes deben formar una palabra en código hexacódigo 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 en código hexacódigo válida, entonces ese subconjunto de 8 no es una octada de S(5,8,24).
El MOG se basa en la creación de una biyección (Conwell 1910, "The three-space PG(3,2) and its group") 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, págs. A193-194, febrero de 1979) con las 35 formas diferentes de dividir una matriz de 4x4 en 4 grupos diferentes de 4 celdas cada uno, tales como que si la matriz 4x4 representa un espacio afín finito de cuatro dimensiones , entonces los grupos forman un conjunto de subespacios paralelos.
