Cuadrados latinos mutuamente ortogonales

Un problema similar al problema de las cartas mencionado anteriormente circulaba en San Petersburgo a finales del siglo XVIII y, según el folclore, Catalina la Grande le pidió a Euler que lo resolviera, ya que residía en su corte en ese momento. ^{[ 7 ]} Este problema se conoce como el problema de los treinta y seis oficiales , ^{[ 8 ]} y Euler lo presentó de la siguiente manera: ^{[ 9 ] [ 10 ]}

Una pregunta muy curiosa, que ha ejercitado durante algún tiempo el ingenio de muchas personas, me ha llevado a realizar los siguientes estudios, que parecen abrir un nuevo campo de análisis, en particular el estudio de las combinaciones. La pregunta gira en torno a cómo disponer a 36 oficiales de 6 regimientos diferentes formando un cuadrado, de manera que en cada fila (tanto horizontal como vertical) haya 6 oficiales de distintos rangos y regimientos.

Euler no pudo resolver el problema, pero en este trabajo demostró métodos para construir cuadrados grecolatinos donde n es impar o múltiplo de 4. Al observar que no existe ningún cuadrado de orden dos y al no poder construir un cuadrado de orden seis, conjeturó que no existen para ningún número par impar n ≡ 2 ( mod 4). La no existencia de cuadrados de orden seis fue confirmada en 1901 por Gaston Tarry mediante una demostración por agotamiento . ^{[ 11 ] [ 12 ]} Sin embargo, la conjetura de Euler resistió la solución hasta finales de la década de 1950, pero el problema ha dado lugar a importantes trabajos en combinatoria . ^{[ 13 ]}

En 1959, RC Bose y SS Shrikhande construyeron algunos contraejemplos (denominados los "desencadenantes de Euler ") de orden 22 utilizando conocimientos matemáticos. ^{[ 14 ]} Luego, ET Parker encontró un contraejemplo de orden 10 utilizando una búsqueda computarizada de una hora en una computadora militar UNIVAC 1206 mientras trabajaba en la división UNIVAC de Remington Rand (este fue uno de los primeros problemas de combinatoria resueltos en una computadora digital ).

En abril de 1959, Parker, Bose y Shrikhande presentaron su artículo que demostraba que la conjetura de Euler era falsa para todo n ≥ 7. ^{[ 15 ]} Por lo tanto, existen cuadrados grecolatinos para todos los órdenes n  >  1 excepto n = 2, 6. En la edición de noviembre de 1959 de Scientific American, Martin Gardner publicó este resultado. ^{[ 6 ]} La portada es la refutación de 10 × 10 de la conjetura de Euler.

Desde 2017 se han estudiado extensiones de cuadrados latinos mutuamente ortogonales al dominio cuántico. ^{[ 17 ]} En estos diseños, en lugar de la unicidad de los símbolos, los elementos de una matriz son estados cuánticos que deben ser ortogonales entre sí en filas y columnas. En 2021, un equipo de físicos indio-polacos (Rather, Burchardt, Bruzda, Rajchel-Mieldzioć, Lakshminarayan y Życzkowski ) encontró una matriz de estados cuánticos que proporciona un ejemplo de cuadrados latinos cuánticos mutuamente ortogonales de tamaño 6; o, equivalentemente, una disposición de 36 oficiales que están entrelazados. ^{[ 16 ] [ 18 ] [ 19 ]} Esta configuración resuelve una generalización del problema de los 36 oficiales de Euler, así como proporciona un nuevo código de detección de errores cuánticos , que permite codificar un sistema de 6 niveles en un sistema de tres niveles de 6 que certifica la ocurrencia de un error.

Lo que hace que la historia de los cuadrados latinos ortogonales sea particularmente notable es que el concepto no se descubrió una sola vez, sino dos: de forma independiente, con siglos de diferencia y en mundos muy distintos. Choi Seok-jeong (최석정; 崔錫鼎; 1646–1715) fue un destacado estadista de la dinastía Joseon de Corea, que ocupó el cargo de Yeonguijeong (영의정) en varias ocasiones, el puesto ministerial más alto del reino, equivalente al de Primer Ministro. Sin embargo, paralelamente a su carrera política, produjo un trabajo matemático de extraordinaria profundidad. En su tratado Gusuryak (구수략; 九數略), publicado alrededor de 1700, Choi construyó un par de cuadrados latinos ortogonales de orden 9, una hazaña que precede al trabajo de Leonhard Euler sobre el tema en al menos 67 años. ^{[ 20 ] [ 21 ] [ 22 ]} Choi llegó a esta estructura a través de una tradición intelectual completamente diferente —arraigada en el neoconfucianismo , la filosofía del I Ching y las matemáticas orientales clásicas— sin conexión conocida con la erudición europea contemporánea. Su construcción, llamada Gugumosubyon-gungyang-do (구구모수변궁양도; 九九母數變宮陽圖) en el Gusuryak, se aplicó para producir un cuadrado mágico de orden 9 en el que cada fila, columna y diagonal suma 369. Hoy en día, Choi es considerado por los eruditos como el matemático más grande del período Joseon —una figura excepcional que alcanzó las cimas tanto del poder político como del logro matemático.

Un conjunto de n − 1 MOLS( n ) es equivalente a un plano afín finito de orden n (véase Redes más adelante). ^{[ 10 ]} Como todo plano afín finito es unívocamente extensible a un plano proyectivo finito del mismo orden, esta equivalencia también puede expresarse en términos de la existencia de estos planos proyectivos. ^{[ 28 ]}

Como se mencionó anteriormente, existen conjuntos completos de MOLS( n ) si n es un número primo o una potencia de un número primo, por lo que existen planos proyectivos de tales órdenes. No se conoce la existencia de planos proyectivos finitos con un orden diferente a estos, y por lo tanto, conjuntos completos de MOLS de tales órdenes. ^{[ 10 ]}

El único resultado general sobre la no existencia de planos proyectivos finitos es el teorema de Bruck - Ryser , que establece que si existe un plano proyectivo de orden n y n ≡ 1 (mod 4) o n ≡ 2 (mod 4), entonces n debe ser la suma de dos cuadrados (enteros). ^{[ 29 ]} Esto excluye los planos proyectivos de órdenes 6 y 14, por ejemplo, pero no garantiza la existencia de un plano cuando n satisface la condición. En particular, n = 10 satisface las condiciones, pero no existe ningún plano proyectivo de orden 10, como se demostró mediante una búsqueda computacional muy larga, ^{[ 30 ]} lo que a su vez implica que no existen nueve MOLS de orden 10.

No se conocen otros resultados de existencia. A partir de 2020,El orden más pequeño para el cual la existencia de un conjunto completo de MOLS es indeterminada es 12. ^{[ 10 ]}

Se sabe que el número mínimo de MOLS( n ) es 2 para todo n excepto para n = 2 o 6, donde es 1. Sin embargo, se puede decir más, a saber, ^{[ 31 ]}

Teorema de MacNeish : Si${\displaystyle n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{r}^{\alpha _{r}}}$es la factorización del entero n en potencias de primos distintos${\displaystyle p_{1},p_{2},\cdots ,p_{r}}$entonces

el número mínimo de MOLS( n )${\displaystyle \geq {\underset {i}{\operatorname {min} }}\{p_{i}^{\alpha _{i}}-1\}.}$

El teorema de MacNeish no proporciona una cota inferior muy buena; por ejemplo, si n ≡ 2 (mod 4), es decir, si hay un solo 2 en la factorización prima, el teorema da una cota inferior de 1, que se supera si n > 6. Por otro lado, sí proporciona el valor correcto cuando n es una potencia de un número primo.

Para números compuestos generales, se desconoce el número de MOLS. Los primeros valores que comienzan con n = 2, 3, 4... son 1, 2, 3, 4, 1, 6, 7, 8, ... (secuencia A001438 en el OEIS ) .

El caso más pequeño para el cual se desconoce el número exacto de MOLS( n ) es n = 10. Según la construcción del cuadrado grecolatino, debe haber al menos dos, y debido a la inexistencia de un plano proyectivo de orden 10, hay menos de nueve. Sin embargo, nunca se ha encontrado un conjunto de tres MOLS(10), a pesar de que muchos investigadores han intentado descubrirlo. ^{[ 32 ]}

Para n suficientemente grande , el número de MOLS es mayor que${\displaystyle {\sqrt[{14.8}]{n}}}$, por lo tanto, para cada k , solo hay un número finito de n tales que el número de MOLS es k . ^{[ 33 ]} Además, el mínimo es 6 para todo n > 90.

Existe un conjunto completo de MOLS( q ) siempre que q sea un número primo o una potencia de un número primo. Esto se deduce de una construcción basada en un cuerpo finito GF ( q ), que solo existe si q es un número primo o una potencia de un número primo. ^{[ 34 ]} El grupo multiplicativo de GF ( q ) es un grupo cíclico y, por lo tanto, tiene un generador, λ, lo que significa que todos los elementos no nulos del cuerpo pueden expresarse como potencias distintas de λ. Nombramos los q elementos de GF ( q ) de la siguiente manera:

α ₀ = 0, α ₁ = 1, α ₂ = λ, α ₃ = λ ² , ..., α _{q -1} = λ ^{q -2} .

Ahora, λ ^{q -1} = 1 y la regla del producto en términos de los α es α _i α _j = α _t , donde t = i + j -1 (mod q -1). Los cuadrados latinos se construyen de la siguiente manera, la entrada ( i, j ) en el cuadrado latino L _r (con r ≠ 0) es L _r ( i,j ) = α _i + α _r α _j , donde todas las operaciones ocurren en GF ( q ). En el caso de que el campo sea un campo primo ( q = p un primo), donde los elementos del campo se representan de la manera usual, como los enteros módulo p , la convención de nombres anterior se puede omitir y la regla de construcción se puede simplificar a L _r ( i,j ) = i + rj , donde r ≠ 0 e i , j y r son elementos de GF ( p ) y todas las operaciones están en GF ( p ). Los ejemplos MOLS(4) y MOLS(5) anteriores surgieron de esta construcción, aunque con un cambio de alfabeto.

No todos los conjuntos completos de MOLS surgen de esta construcción. El plano proyectivo asociado al conjunto completo de MOLS obtenido a partir de esta construcción de cuerpos es de un tipo especial: un plano proyectivo desarguesiano . Existen planos proyectivos no desarguesianos y sus correspondientes conjuntos completos de MOLS no pueden obtenerse a partir de cuerpos finitos. ^{[ 35 ]}