Carrés Latins - solution

Combiner 3 carrés latins de 4×4 pour former un carré "arabo-greco-latin" formé des combinaisons de chiffres arabes 1234, lettres grecques αβγδ et lettres latines abcd, chaque symbole une fois par ligne et par colonne, et chaque paire de symboles une fois et une seule.

Ceci revient donc à chercher trois carrés latins de 4×4 mutuellement orthogonaux
(MOLS = Mutually Orthogonal Latin Squares).

Il y a 576 carrés latins 4×4. De façon générale il y a

1, 2, 12, 576, 161280, 812851200, 61479419904000,...

OEIS A002860

Tout d'abord, par simple changement des symboles utilisés, on peut imposer la première ligne = abcd.
par échange des lignes on peut imposer la 1ère colonne = abcd
Des 576 carrés latins de 4×4 il ne reste plus que 4 carrés normalisés.

a b c d b a d c c d a b d c b a

a b c d b a d c c d b a d c a b

a b c d b d a c c a d b d c b a

a b c d b c d a c d a b d a b c

De façon générale, s'il y à N(n) carrés latins n×n et L(n) carrés latins normalisés

N(n) = n!(n-1)!L(n)

Le nombre de carrés latins de n×n normalisés est :

1, 1, 1, 4, 56, 9408, 16942080, ...

OEIS A000315

Les carrés latins mutuellement orthogonaux (MOLS) peuvent aussi être "normalisés", mais seulement en imposant la 1ère ligne de chacun : abcd, αβγδ et 1234 ce qui laisse 576/4! = 24 carrés latins candidats à examiner
Le premier peut être complètement normalisé (1ère colonne abcd) mais pas les autres.
La deuxième ligne grecque ne peut alors commencer que par γ ou δ et même la 1ère colonne grecque (!) ne peut être que αγδβ ou αδβγ.

Une recherche systématique des carrés orthogonaux aux 4 carrés latins normalisés donne :

a b c d b a d c c d a b d c b a

=>

α β γ δ γ δ α β δ γ β α β α δ γ

α β γ δ δ γ β α β α δ γ γ δ α β

et aucun carré orthogonal pour les trois autres carrés latins normalisés 4×4

On remarque que les deux carrés grecs orthogonaux au carré latin sont orthogonaux entre eux, c'est à dire que le deuxième peut s'écrire en chiffres arabes :

1 2 3 4 4 3 2 1 2 1 4 3 3 4 1 2

Pour donner le seul carré arabo-gréco-latin normalisé :

aα1   bβ2   cγ3   dδ4   bγ4   aδ3   dα2   cβ1   cδ2   dγ1   aβ4   bα3   dβ3   cα4   bδ1   aγ2

Tous les autres s'en déduisant par permutation des lignes, des colonnes et des alphabets.

Et après...

Comme on a obtenu la liste de tous les carrés orthogonaux 4×4, elle prouve qu'il ne peut y avoir un 4ème jeu de symboles orthogonal. Ceci est général :

Un ensemble de MOLS n×n ne peut comporter plus de n-1 carrés

Le nombre maximum M(n) de carrés d'un ensemble de MOLS n×n est :
1, 1, 2, 3, 4, 1, 6, 7, 8...
C'est à dire pour n < 10, M(n) = n - 1, sauf pour n = 6. On ne connaît pas M(10), on pense que M(10) = 2.

M(n) ≥ 2 pour tout n sauf {1, 2, 6}

C'est à dire qu'il y a un carré gréco-latin n×n pour tout n sauf 2 et 6.
On a aussi :

M(mn) ≥ min{M(m), M(n)}   M(n) = n - 1 si n = pa, p premier

Concernant cette dernière propriété on pense que c'est une condition nécessaire.
C'est à dire M(n) = n - 1 si et seulement si n = p^a, p premier

Quoi qu'il en soit, les n - 1 MOLS lorsque n est une puissance d'un nombre premier p se déduisent du Corps fini de n éléments.

Corps finis

C'est à dire un ensemble de n éléments, muni d'une "addition" et d'une "multiplication" ayant toutes les bonnes propriétés habituelles : commutatives, associatives, éléments neutres 0 et 1, distributives, tout élément sauf 0 a un inverse.
Un corps fini a n éléments si et seulement si n est une puissance d'un nombre premier p.
La caractéristique du corps fini est alors p. C'est à dire que 1+1+1... +1 p fois est = 0
Le corps fini est donc une extension du corps F_p de p éléments qui est tout simplement le corps des entiers modulo p.
Cette extension s'obtient en "ajoutant" les éléments générés par les racines de xⁿ - x = 0.
Par exemple GF₄ est obtenu en ajoutant à F₂ = {0,1} les racines de x⁴ - x = x(x - 1)(x² + x + 1) = 0, soit x tel que x² + x + 1 = 0 puisque 0 et 1 sont déjà dans F₂. Cet élément x n'est pas "réel" dans F₂, et F₂ est alors étendu en GF₄ = {0, 1, a, b} où a et b sont les racines de x² + x + 1 = (x - a)(x - b) = 0 dans une extension algébrique de F₂
On a bien sûr ab = 1 et a + b = -1 = 1 ce qui permet de complèter les tables d'addition et de multiplication de GF₄.

0  1  a  b 1  0  b  a a  b  0  1 b  a  1  0

0  0  0  0 0  1  a  b 0  a  b  1 0  b  1  a

La table d'addition est forcément un carré latin ! que l'on peut écrire [a_ij = i + j], i,j GF₄
L'ensemble des n - 1 MOLS est alors généré par [a_ij = u×i + j] où u = {1, a, b} = GF₄*

u = 1	u = a	u = b
0  1  a  b 1  0  b  a a  b  0  1 b  a  1  0	0  1  a  b a  b  0  1 b  a  1  0 1  0  b  a	0  1  a  b b  a  1  0 1  0  b  a a  b  0  1

Ce qui en changeant d'alphabets nous redonne notre carré arabo-gréco-latin.

On obtient de même "instantanément" les 10 MOLS 11×11 : [a_ij = u×i + j modulo 11], u = {1...10}
Ici c'est facile puisque GF₁₁ est en fait F₁₁ puisque 11 est premier.

Plus délicat serait GF₉, dérivé de F₃ en ajoutant les racines de x² + 1 = 0, soit :
GF₉ = F₃[i] = {0, 1, 2, i, i+1, i+2, 2i, 2i+1, 2i+2} où i est une racine de x² + 1 = 0.
Les tables d'addition et de multiplication s'obtiennent en calculant normalement, avec des coeficients dans F₃, c'est à dire modulo 3, et en tenant compte que i² = - 1 = 2.

Et un dernier exemple avec GF₈ = F₂[j] où j est racine de x³ + x + 1 = 0 soit GF₈ = { 0, 1, j, j+1, j², j²+1, j²+j, j²+j+1},
Les tables sont obtenues en simplifiant les coefficients dans F₂, soit modulo 2, et en simplifiant les j³ = j + 1.

On a là tout ce qu'il faut pour obtenir sans tâtonnement les ensembles de MOLS pour n = 3, 4, 5, 7, 8, 9, et 11.