Sistema steiner

El avión Fano es un sistema triple Steiner S(2,3,7). Los bloques son las 7 líneas, cada una con 3 puntos. Cada par de puntos pertenece a una línea única.

En matemáticas combinatorias, un sistema de Steiner (llamado así por Jakob Steiner) es un tipo de diseño de bloques, específicamente un diseño en 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 elementos n S junto con un conjunto de k Subconjuntos de elementos de S (llamados bloques) con la propiedad de que cada subconjunto de elementos t de S está contenido exactamente en una cuadra. En una notación alternativa para diseños de bloques, una S(t,k,n) sería una t- (n,k,1) diseño.

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) era (y sigue siendo) llamado un sistema triple de Steiner (o tríada), mientras que un S(3,4,n) es llamado sistema cuádruple de Steiner, y así sucesivamente. Con la generalización de la definición, este sistema de nombres ya no se cumple estrictamente.

Los problemas de larga data en la teoría del diseño eran si existía algún sistema Steiner no trivial (significado no trivial t < k < n) con t ≥ 6; también si infinitamente muchos tienen t = 4 o 5. 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.

Tipos de sistemas Steiner

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 < span class="texhtml">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²). 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 isomórficos.

An S(3,4,4)n) se llama un Sistema de cuádruple Steiner. Una condición necesaria y suficiente para la existencia de un S(3,4,n) es que n ${displaystyle equiv }$ 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)s y 1.054.163 SQS(16)s.

An S(4,5,n) se llama un Steiner quintuple system. Una condición necesaria para la existencia de ese sistema es que n ${displaystyle equiv }$ 3 o 5 (mod 6) que proviene de consideraciones que se aplican a todos los sistemas clásicos Steiner. Una condición adicional necesaria es que n ${displaystyle not equiv }$ 4 (mod 5), que proviene del hecho de que el número de bloques debe ser un entero. No se conocen las condiciones adecuadas. Hay un sistema único de quintuple Steiner del orden 11, pero ninguno de los pedidos 15 o orden 17. Los sistemas son conocidos por ó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 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 de 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 alguna k. El hecho de que esta condición en n es suficiente para la existencia de un S(2,3,n) fue probado por Raj Chandra Bose y T. Skolem. 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). Salvo isomorfismo, STS(7) y STS(9) son únicos, hay dos STS(13), 80 STS(15) y 11 084 874 829 STS(19).

Podemos definir una multiplicación en el conjunto S usando el sistema triple de Steiner estableciendo aa = a para todo a< /i> 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. 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.

Sistemas Steiner resolubles

Algunos de los sistemas S(2,3,n) pueden dividir sus ternas en (n-1)/2 conjuntos, cada uno de los cuales tiene (n/3) ternas separadas por pares. Esto se llama resolvible 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 de 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 isomórficas 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 que se repita ningún triplete de niñas durante todo el período. La pregunta fue resuelta por RHF Denniston en 1974, quien construyó la Semana 1 de la siguiente manera:

Día 1 ABJ CEM FKL HIN DGO
Día 2 ACH DEI FGM JLN BKO
Día 3 ADL BHM GIK CFN EJO
Día 4 AEG BIL CJK DMN FHO
Día 5 AFI BCD GHJ EKN LMO
Día 6 AKM DFJ EHL BGN CIO
Día 7 BEF CGL DHK IJM ANO

para niñas etiquetadas de la A a la O, y construyeron cada solución de la 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 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 isomórficas al problema de Sylvester sigue siendo desconocido a partir de 2021.

Propiedades

Está claro desde la definición de S(t, k, n) que ${displaystyle 1 No se hizo realidad$. (Las desigualdades, si bien técnicamente es posible, conducen a sistemas triviales.)

Si S(t, k, n) existe, tomando todos 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 t-element subsets in S es ${displaystyle {tbinom {} {}} {fn}} {fn}} {fn}}} {fn}} {fn}}$, mientras que el número de t-Element subsets en cada bloque es ${fnMicrosoft}}$. Desde todos t-element subset está contenido en exactamente un bloque, tenemos ${displaystyle {tbinom} {n}=b{tbinom} {k}{t}}$, o

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

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

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

Donde r es el número de bloques que contienen cualquier elemento dado. De estas definiciones sigue la ecuación ${displaystyle bk=rn}$. Es una condición necesaria para la existencia de S(t, k, n) que b y r son enteros. Como con cualquier diseño de bloques, la desigualdad de Fisher ${displaystyle bgeq n}$ es cierto en los sistemas Steiner.

Dados los parámetros de un sistema Steiner S(t, k, n) y un subconjunto de tamaño ${displaystyle t'leq t}$, contenido en al menos un bloque, se puede calcular el número de bloques que intersectan ese subconjunto en un número fijo de elementos mediante la construcción de un triángulo Pascal. En particular, el número de bloques que intersectan 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:

${displaystyle lambda ¿Qué? {n-i} {t-i}right/{binom} {k-i}{text{ for }i=0,1,ldotst,}$

Se puede demostrar que si hay un sistema Steiner S(2, k, n), donde k es un poder primario superior a 1, entonces n ${displaystyle equiv }$ 1 o 1 k (modelo) k()k−1)). En particular, un sistema triple Steiner S(2, 3, n) Debe haber n = 6m + 1 ó 6m + 3. Y como ya hemos mencionado, esta es la única restricción a los sistemas triples Steiner, es decir, para cada número natural m, sistemas S(2, 3, 6m + 1) y S(2, 3, 6m + 3) existen.

Historia

Los sistemas triples de Steiner fueron definidos por primera vez por Wesley S. B. Woolhouse en 1844 en la pregunta del premio n.º 1733 de Lady's and Gentlemen's Diary. El problema planteado fue resuelto por Thomas Kirkman (1847). En 1850, Kirkman planteó una variación del problema conocido como el problema de la colegiala de Kirkman, que pide que los sistemas triples tengan una propiedad adicional (resolubilidad). Ignorando el 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 Mathieu

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

• El grupo Mathieu M11 es el grupo de automorfismo de un S(4,5,11) Sistema Steiner
• El grupo Mathieu M12 es el grupo de automorfismo de un S(5,6,12) Sistema Steiner
• El grupo Mathieu M22 es el subgrupo índice 2 único del grupo de automorfismo de un S(3,6,22) Sistema Steiner
• El grupo Mathieu M23 es el grupo de automorfismo de un S(4,7,23) Sistema Steiner
• El grupo Mathieu M24 es el grupo de automorfismo de un S(5,8,24) Sistema Steiner.

El sistema Steiner S(5, 6, 12)

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

Construcción de línea proyectiva

Esta construcción se debe a Carmichael (1937).

Agregue un nuevo elemento, llámelo ∞, a los 11 elementos del campo finito F₁₁ (es decir, los números enteros mod 11). Este conjunto, S, de 12 elementos se puede identificar formalmente con los puntos de la línea proyectiva sobre F₁₁. Llame al siguiente subconjunto específico de tamaño 6,

${displaystyle {infty1,3,4,5,9},}$

un "bloque" (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 habituales de definir f (−d/c) = ∞ y < span class="texhtml">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 por conjuntos, a saber, aquellos tales que b=c=0 y < i>ad=1 de modo que f(z) = a² 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< /span> 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₁₂ mediante el uso de la función 'kitten' de R. T. Curtis, que fue concebida como una "calculadora manual" escribir los 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₃, una S(2,3, 9) sistema.

Construcción a partir de la factorización del gráfico K6

Las relaciones entre los factores gráficos del gráfico completo K6 generan un S(5,6,12). A K₆ El gráfico tiene 6 vértices, 15 bordes, 15 emparejamientos perfectos, y 6 diferentes 1-factorizaciones (siempre para dividir los bordes en emparejamientos perfectos disjoint). El conjunto de vértices (marcado 123456) y el conjunto de factorizaciones (marcado ABCDEF) proporcionar un bloque cada uno. Cada par de factorizaciones tiene exactamente una combinación perfecta en común. Suppose factorizations A y B tienen la coincidencia común con los bordes 12, 34 y 56. Añadir tres bloques nuevos AB3456, 12AB56, y 1234AB, reemplazando cada borde en la combinación común con las etiquetas de factorización a su vez. Análogamente añadir tres bloques más 12CDEF, 34CDEF, y 56CDEF, reemplazando las etiquetas de factorización por las etiquetas de borde correspondientes de la coincidencia común. Haga esto para las 15 pares de factorizaciones para añadir 90 nuevos bloques. Por último, tome el conjunto completo de ${fnK}=924}$ combinaciones 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 ahora. Quedan exactamente 40 bloques, resultando en 2 + 90 + 40 = 132 bloques del S(5,6,12). Este método funciona porque hay un automorfismo externo en el grupo simétrico S6, que mapea los vértices a las factorizaciones y los bordes a las particiones. Permutar los vértices hace que las factorizaciones permuten de manera diferente, de acuerdo con el automorfismo exterior.

El sistema Steiner S(5, 8, 24)

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 red excepcional de 24 dimensiones conocida como red Leech. El grupo de automorfismos de S(5, 8, 24) es el grupo Mathieu M24, y en ese contexto el diseño se denota W₂₄ ("W" por "Witt& #34;)

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 05 06 07 08

01 02 03 04 09 10 11 12

01 02 03 04 13 14 15 16

.

. (Anexo 753 octads omitidos)

.

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 una octava. Cada par ocurre 77 veces. Cada triple ocurre 21 veces. Cada cuádruple (tétrada) ocurre 5 veces. Cada quíntuple (pentad) ocurre una vez. No ocurre cada hexágono, heptada u octada.

Construcción a partir del código binario de Golay

Se generan las 4096 palabras clave del código Golay binario de 24 bits, y las 759 palabras clave con peso Hamming de 8 corresponden al sistema S(5,8,24).

El código Golay se puede construir por 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í:

 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000111111111111
0000000001111000011111111
.
. (Anexo de 4090 cuerdas de 24 bits omitidas)
.
111111111111000011110000
11111111111111111100000000
11111111111111111111111111111111

Las palabras clave forman un grupo bajo la operación XOR.

Construcción de líneas proyectivas

Esta construcción se debe a Carmichael (1931).

Agregue un nuevo elemento, llámelo ∞, a los 23 elementos del campo finito F₂₃ (es decir, los números enteros mod 23). Este conjunto, S, de 24 elementos se puede identificar formalmente con los puntos de la línea proyectiva sobre F₂₃. Llame al siguiente subconjunto específico de tamaño 8,

${displaystyle {infty0,1,3,12,15,21,22},}$

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 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 habituales de definir f (−d/c) = ∞ y < span class="texhtml">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 fijo el bloque inicial por conjuntos. Entonces habrá 6072/8 = 759 imágenes de ese bloque. Estos forman las octadas de S(5,8,24).

Construcción a partir del Generador Miracle Octad

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 octava 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. Tercero, 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 multiplicación y suma utilizando las definiciones aritméticas de campos finitos. 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< /i> también son del campo finito de orden 4. Si la columna suma' las paridades no coinciden con la paridad de la suma de las filas, o entre sí, o si no existen a, b, c de modo que las sumas de las columnas formen una hexacodeword válida, entonces ese subconjunto de 8 es no una octada 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 4 diferentes -sets, y las 35 líneas del Fano 3-space PG(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 de 4x4 en 4 grupos diferentes de 4 celdas cada una, de modo que si la matriz de 4x4 representa un espacio afín finito de cuatro dimensiones, los grupos forman un conjunto de subespacios paralelos.

Referencias

• Assmus, E. F. Jr.; Key, J. D. (1994), "8. Steiner Systems", Diseños y sus códigos, Cambridge University Press, pp. 295–316, ISBN 978-0-521-45839-9.
• Assmus, E.F.; Key, J.D. (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 de diseño, Cambridge: Cambridge University Press2a edición (1999) ISBN 978-0-521-44432-3.
• Carmichael, Robert (1931), "Configuraciones tácticas de Rank 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 los grupos de orden finito, Dover, ISBN 978-0-486-60300-1
• Colbourn, Charles J.; Dinitz, Jeffrey H. (1996), Handbook of Combinatorial Designs, Boca Raton: Chapman " Hall/ CRC, ISBN 978-0-8493-8948-1, Zbl 0836.00010
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2a ed.), Boca Raton: Chapman " Hall/ CRC, ISBN 978-1-58488-506-1, Zbl 1101.05001
• Curtis, R.T. (1984), "El sistema Steiner S(5,6,12), el grupo Mathieu M₁₂ y el "kitten"", en Atkinson, Michael D. (ed.), Teoría de grupo computacional (Durham, 1982), Londres: Academic Press, pp. 353–358, ISBN 978-0-12-066270-8, MR 0760669
• Hughes, D. R.; Piper, F. C. (1985), Teoría de diseño, Cambridge University Press, pp. 173–176, ISBN 978-0-521-35872-9.
• Kirkman, Thomas P. (1847), "Sobre un problema en las combinaciones", The Cambridge and Dublin Mathematical Journal, II: 191-204.
• Lindner, C.C.; Rodger, C.A. (1997), Teoría de diseño, Boca Raton: CRC Press, ISBN 978-0-8493-3986-8
• Östergard, Patric R.J.; Pottonen, Olli (2008), "No existe un sistema Steiner S(4,5,17)", Journal of Combinatorial Teoría, 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. Math. Sem. Univ. Hamburg, 12: 256–264, doi:10.1007/BF02948947, S2CID 123658601