Sistema Steiner

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 de Steiner con parámetros t , k , n , escrito S( t , k , n ), es un conjunto de n elementos S junto con un conjunto de subconjuntos de k elementos de S (llamados bloques ) con la propiedad de que cada subconjunto de t elementos de S está contenido en exactamente un bloque. En una notación alternativa para diseños de bloques, un 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 de Steiner también requería que k = t + 1. Un S(2,3, n ) se denominaba (y todavía se denomina) sistema triple (o tríada ) de Steiner , mientras que un S(3,4, n ) se denomina 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 de Steiner no triviales (no trivial significa t < k < n ) con t ≥ 6; también si hay infinitos sistemas con 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 de Steiner reales para valores grandes de t . ^{[2] [3] [4]}

Un plano proyectivo finito de orden q , con las líneas como bloques, es un S(2, q + 1, q ² + q + 1) , ya que tiene q ² + q + 1 puntos, cada línea 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 ² ) . Un plano afín de orden q se puede obtener 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 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. Salvo isomorfismo, SQS(8) y SQS(10) son únicos, hay 4 SQS(14) y 1.054.163 SQS(16). ^[5]${\displaystyle \equiv}$

Un S(4,5, n ) se denomina sistema quíntuple de Steiner . Una condición necesaria para la existencia de dicho sistema es que n 3 o 5 (mod 6), lo que se desprende de consideraciones que se aplican a todos los sistemas clásicos de Steiner. Una condición necesaria adicional es que n 4 (mod 5), lo que se desprende del hecho de que el número de bloques debe ser un número entero. No se conocen condiciones suficientes. Existe un único sistema quíntuple de Steiner de orden 11, pero ninguno de orden 15 u orden 17. ^[6] Se conocen sistemas para los órdenes 23, 35, 47, 71, 83, 107, 131, 167 y 243. El orden más pequeño para el que no se conoce la existencia (a fecha de 2011) es 21.${\displaystyle \equiv}$ ${\displaystyle \no \equiv}$

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 de Steiner de orden n . El número total de pares es n(n-1)/2 , de los cuales tres aparecen en un triple, y por lo tanto el número total de triples es n ( n −1)/6. Esto muestra que n debe ser de la forma 6k+1 o 6k + 3 para algún 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, los STS(7) y 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 de triples de Steiner haciendo aa = a para todo a en S , y ab = c si { a , b , c } es una terna. Esto hace que S sea 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 de triples 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 triples particionados en (n-1)/2 conjuntos, cada uno con (n/3) triples disjuntos por pares. Esto se llama resoluble y dichos sistemas se llaman sistemas triples de Kirkman en honor a Thomas Kirkman , quien estudió dichos sistemas resolubles antes de Steiner. Dale Mesner, Earl Kramer y otros investigaron colecciones de sistemas triples de Steiner que son mutuamente disjuntos (es decir, no hay dos sistemas de Steiner en dicha colección 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 dichos 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) distintos y disjuntos fue planteada 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 que se repitiera ningún triplete de niñas durante todo el período. La pregunta 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 las niñas etiquetadas de A a O, y construyó la solución de cada semana subsiguiente a partir de su predecesora inmediata cambiando A por B, B por C, ... L por M y M de nuevo por A, todo mientras dejaba N y O sin cambios. La solución de la semana 13, al someterse a ese reetiquetado, regresa 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 , y finalizó inmediatamente la búsqueda al encontrar la solución anterior, sin buscar establecer unicidad. El número de soluciones no isomórficas al problema de Sylvester sigue siendo desconocido a partir de 2021.

De la definición de S( t , k , n ) se desprende claramente que . (Las igualdades, aunque técnicamente posibles, conducen a sistemas triviales).${\displaystyle 1<t<k<n}$

Si S( t , k , n ) existe, entonces al tomar todos los bloques que contienen un elemento específico y descartar ese elemento se obtiene 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 t elementos en S es , mientras que el número de subconjuntos de t elementos en cada bloque es . Como cada subconjunto de t elementos está contenido en exactamente un bloque, tenemos , o ${\displaystyle {\tbinom {n}{t}}}$${\displaystyle {\tbinom {k}{t}}}$${\displaystyle {\tbinom {n}{t}}=b{\tbinom {k}{t}}}$

${\displaystyle b={\frac {\tbinom {n}{t}}{\tbinom {k}{t}}}={\frac {n(n-1)\cdots (n-t+1)}{k(k-1)\cdots (k-t+1)}},}$

donde b es el número de bloques. Un razonamiento similar sobre los subconjuntos de t elementos que contienen un elemento particular nos da , o ${\displaystyle {\tbinom {n-1}{t-1}}=r{\tbinom {k-1}{t-1}}}$

${\displaystyle r={\frac {\tbinom {n-1}{t-1}}{\tbinom {k-1}{t-1}}}}$=${\displaystyle {\frac {(n-t+1)\cdots (n-2)(n-1)}{(k-t+1)\cdots (k-2)(k-1)}},}$

donde r es el número de bloques que contienen cualquier elemento dado. De estas definiciones se deduce 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 verdadera en los sistemas de Steiner.${\displaystyle bk=rn}$ ${\displaystyle b\geq n}$

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 intersecan ese subconjunto en un número fijo de elementos construyendo un triángulo de Pascal . ^[12] En particular, el número de bloques que intersecan un bloque fijo en cualquier número de elementos es independiente del bloque elegido.${\displaystyle t'\leq t}$

El número de bloques que contienen cualquier conjunto de puntos de i elementos es:

${\displaystyle \lambda _{i}=\left.{\binom {ni}{ti}}\right/{\binom {ki}{ti}}{\text{ para }}i=0,1,\ldots ,t,}$

Se puede demostrar que si existe un sistema de 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 de 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 sobre los sistemas triples de Steiner, es decir, para cada número natural m , existen los sistemas S(2, 3, 6 m + 1) y S(2, 3, 6 m + 3) .${\displaystyle \equiv}$

Los sistemas triples de Steiner fueron definidos por primera vez por Wesley SB Woolhouse en 1844 en la pregunta de 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 conocida como el problema de la colegiala de Kirkman , que pide sistemas triples que tengan una propiedad adicional (capacidad de resolución). 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 en su honor.

En 1910, Geoffrey Thomas Bennett proporcionó una representación gráfica de los sistemas triples de Steiner. ^{[14] [15] [16]}

Varios ejemplos de sistemas de 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 automorfismo de los sistemas de Steiner:

• El grupo de Mathieu M ₁₁ es el grupo de automorfismos de un sistema de Steiner S(4,5,11)
• El grupo de Mathieu M ₁₂ es el grupo de automorfismos de un sistema de Steiner S(5,6,12)
• El grupo Mathieu M ₂₂ es el único subgrupo de índice 2 del grupo de automorfismos de un sistema Steiner S(3,6,22)
• El grupo de Mathieu M ₂₃ es el grupo de automorfismos de un sistema de Steiner S(4,7,23)
• El grupo de Mathieu M ₂₄ es el grupo de automorfismo de un sistema Steiner S(5,8,24).

Existe un único sistema Steiner S(5,6,12); su grupo de automorfismo es el grupo de Mathieu M ₁₂ , y en ese contexto se denota por W ₁₂ .

Esta construcción se debe a Carmichael (1937). ^[17]

Agreguemos un nuevo elemento, llamémoslo ∞ , a los 11 elementos del cuerpo finito F ₁₁ (es decir, los enteros módulo 11). Este conjunto, S , de 12 elementos puede identificarse formalmente con los puntos de la línea proyectiva sobre F ₁₁ . Llamemos al siguiente subconjunto específico de tamaño 6,

${\displaystyle \{\infty,1,3,4,5,9\},}$

un "bloque" (que contiene ∞ junto con los 5 cuadrados distintos de cero en F ₁₁ ). A partir de este bloque, obtenemos los otros bloques del sistema S (5,6,12) aplicando repetidamente las transformaciones fraccionarias lineales :

${\displaystyle z'=f(z)={\frac {az+b}{cz+d}},}$

donde a,b,c,d están en F ₁₁ y ad − bc = 1 . Con las convenciones usuales de definición de f (− d / c ) = ∞ y f (∞) = a / c , estas funciones mapean el conjunto S sobre sí mismo. En lenguaje geométrico, son proyectividades de la recta 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 de partida fijo en conjunto, ^[18] a saber, aquellos tales que b=c=0 y ad =1 de modo que f(z) = a ² z . Por lo tanto, 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á en exactamente una de estas 132 imágenes de tamaño seis.

Una construcción alternativa de W ₁₂ se obtiene mediante el uso del "gatito" de RT Curtis, ^[19] que fue concebido 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 ₃ xF ₃ , un sistema S(2,3,9).

Las relaciones entre los factores del grafo completo K ₆ generan un S(5,6,12). ^[20] El grafo AK _{6 tiene 6 vértices, 15 aristas, 15} emparejamientos perfectos y 6 1-factorizaciones diferentes (formas de dividir los aristas 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 un emparejamiento perfecto en común. Supongamos que las factorizaciones A y B tienen el emparejamiento común con las aristas 12, 34 y 56. Agregue tres nuevos bloques AB 3456, 12 AB 56 y 1234 AB , reemplazando cada arista en el emparejamiento 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 arista correspondientes del emparejamiento común. Haga esto para los 15 pares de factorizaciones para agregar 90 bloques nuevos. Finalmente, tome el conjunto completo de combinaciones de 6 objetos de 12 y descarte cualquier combinación que tenga 5 o más objetos en común con cualquiera de los 92 bloques generados hasta ahora. 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 ₆ , 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.${\displaystyle {\tbinom {12}{6}}=924}$

El sistema de 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 de Leech . El grupo de automorfismos de S(5, 8, 24) es el grupo de Mathieu M ₂₄ , y en ese contexto el diseño se denota W ₂₄ ("W" por "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 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 individual aparece 253 veces en algún lugar de alguna octada. Cada par aparece 77 veces. Cada triple aparece 21 veces. Cada cuádruple (tétrada) aparece 5 veces. Cada quíntuple (péntada) aparece una vez. No aparecen todas las hexadas, heptadas u octadas.

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 0000000000000000011111111 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 .

Esta construcción se debe a Carmichael (1931). ^[21]

Agreguemos un nuevo elemento, llamémoslo ∞ , a los 23 elementos del cuerpo finito F ₂₃ (es decir, los enteros módulo 23). Este conjunto, S , de 24 elementos puede identificarse formalmente con los puntos de la línea proyectiva sobre F ₂₃ . Llamemos al siguiente subconjunto específico de tamaño 8,

${\displaystyle \{\infty,0,1,3,12,15,21,22\},}$

un "bloque". (Podemos tomar cualquier octada del código binario Golay extendido , visto como un código de residuo cuadrático). A partir de este bloque, obtenemos los otros bloques del sistema S (5,8,24) aplicando repetidamente las transformaciones fraccionarias lineales :

${\displaystyle z'=f(z)={\frac {az+b}{cz+d}},}$

donde a,b,c,d están en F ₂₃ y ad − bc = 1 . Con las convenciones usuales de definición de f (− d / c ) = ∞ y f (∞) = a / c , estas funciones mapean el conjunto S sobre sí mismo. En lenguaje geométrico, son proyectividades de la recta 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 salen del bloque inicial fijo por conjuntos. Por lo que habrá 6072/8 = 759 imágenes de ese bloque. Estas forman las óctadas de S(5,8,24).

El Miracle Octad Generator (MOG) es una herramienta para generar octadas, como las 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. Segundo, la fila superior debe tener la misma paridad que cada una de las columnas. Tercero, las filas se multiplican respectivamente por los pesos 0, 1, 2 y 3 sobre el campo finito de orden 4 , y se calculan las sumas de las columnas para las 6 columnas, con multiplicación y adición utilizando las definiciones aritméticas de campo finito. Las sumas de columnas resultantes deben formar una palabra 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 columnas no coinciden con la paridad de la suma de filas, o entre sí, o si no existen a, b, c tales que las sumas de columnas formen una palabra hexacódigo válida, entonces ese subconjunto de 8 no es una óctada de S(5,8,24).

El MOG se basa en la creación de una biyección (Conwell 1910, "El espacio tridimensional PG(3,2) y su grupo") entre las 35 formas de particionar un conjunto de 8 en dos conjuntos de 4 diferentes, y las 35 líneas del espacio tridimensional PG(3,2) de Fano. También está relacionado geométricamente (Cullinane, "Invariancia de simetría en un anillo de diamantes", Notices of the AMS, pp A193-194, febrero de 1979) con las 35 formas diferentes de particionar una matriz de 4x4 en 4 grupos diferentes de 4 celdas cada uno, de modo que si la matriz de 4x4 representa un espacio afín finito de cuatro dimensiones , entonces los grupos forman un conjunto de subespacios paralelos.

• Código de peso constante
• El problema de la colegiala de Kirkman
• Configuración de Sylvester-Gallai

• 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. 2da 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, Zbl0836.00010 ​
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Manual de diseños combinatorios (2.ª ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 978-1-58488-506-1, Zbl1101.05001 ​
• Curtis, RT (1984), "El sistema Steiner S(5,6,12), el grupo Mathieu M ₁₂ y el "gatito"", en Atkinson, Michael D. (ed.), Computational group theory (Durham, 1982) , Londres: Academic Press, págs. 353-358, ISBN 978-0-12-066270-8, Sr.  0760669
• Hughes, DR; Piper, FC (1985), Teoría del diseño , 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 de 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", Journal für die reine und angewandte Mathematik , 1853 (45): 181–182, doi :10.1515/crll.1853.45.181, S2CID  199547187.
• Witt, Ernst (1938), "Die 5-Fach transitiven Gruppen von Mathieu", Abh. Matemáticas. Sem. Univ. Hamburgo , 12 : 256–264, doi : 10.1007/BF02948947, S2CID  123658601

Wikimedia Commons tiene medios relacionados con Sistemas Steiner .

• Rowland, Todd y Weisstein, Eric W. "Sistema Steiner". MundoMatemático .
• 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
• S(5, 8, 24) Software y listado de Johan E. Mebius