Système de Steiner
# Système de Steiner

En mathématiques, et plus particulièrement en combinatoire, un système de Steiner (nommé ainsi d'après Jakob Steiner) est un type de design combinatoire.

Plus précisément, un système de Steiner de paramètres t, k, n, noté S(t,k,n), est constitué d'un ensemble S à n éléments, et d'un ensemble de sous-ensembles de S à k éléments (appelés blocs), ayant la propriété que tout sous-ensemble de S à t éléments est contenu dans un bloc et un seul (cette définition moderne généralise celle de Steiner, demandant en plus que k = t + 1). Un S(2,3,n) est appelé un système de Steiner de triplets , un S(3,4,n) est un système de Steiner de quadruplets, et ainsi de suite.

Jusqu’en 2014, on ne connaissait aucun système de Steiner pour t > 5, mais leur existence a été alors démontrée, bien que de manière non constructive.

## Exemples

### Plans projectifs finis

Un plan projectif fini d'ordre q, les blocs étant ses droites, est un $S(2,q+1,q^{2}+q+1)$, puisqu'il a $q^{2}+q+1$ points, que chaque droite contient $q+1$ points, et que chaque paire de points appartient à une droite et une seule.

### Plans affines finis

Un plan affine d'ordre q est un S(2, q, $q^2),$ les droites étant les blocs. Un plan affine d'ordre q peut être obtenu à partir d'un plan projectif de même ordre en en retirant un bloc et tous les points de ce bloc (autrement dit, en choisissant et en supprimant une droite à l'infini). Des choix de blocs différents peuvent amener à des plans affines non isomorphes.

## Systèmes de Steiner classiques

### Systèmes de Steiner de triplets

Un S(2,3,n) s'appelle un système de Steiner de triplets (les blocs étant appelés des triplets) ; on voit souvent l'abréviation STS(n).

Le nombre de triplets est n(n−1)/6. Une condition nécessaire et suffisante d'existence d'un S(2,3,n) est que n $\equiv$ 1 ou 3 (mod 6). Le plan projectif d'ordre 2 (le plan de Fano) est un STS(7), et le plan affine d'ordre 3 est un STS(9).

À isomorphisme près, il n'y a qu'un STS(7) et un STS(9), mais il y a deux STS(13), 80 STS(15), et 11 084 874 829 STS(19).

Partant d'un système de Steiner de triplets, on peut définir une multiplication sur l'ensemble S en posant aa = a pour tous les a de S, et ab = c si {a,b,c} est un triplet. Cette multiplication fait de S un quasigroupe commutatif idempotent, ayant la propriété additionnelle que ab = c entraîne bc = a et ca = b. Réciproquement, tout quasigroupe (fini) ayant ces propriétés provient d'un système de Steiner de triplets ; ces quasigroupes s'appellent des quasigroupes de Steiner.

### Systèmes de Steiner de quadruplets

Un S(3,4,n) s'appelle un système de Steiner de quadruplets. Une condition nécessaire et suffisante pour l'existence d'un S(3,4,n) est que n $\equiv$ 2 ou 4 (mod 6) ; ces systèmes sont souvent notés SQS(n).

À isomorphisme près, SQS(8) et SQS(10) sont uniques, il y a 4 SQS(14) et 1 054 163 SQS(16).

### Systèmes de Steiner de quintuplets

Un S(4,5,n) s'appelle un système de Steiner de quintuplets. Une condition nécessaire d'existence d'un tel système est que n $\equiv$ 3 ou 5 (mod 6). De plus, on doit avoir n $\not \equiv$ 4 (mod 5) (car le nombre de blocs doit être entier). On ne connait pas de conditions suffisantes.

Il y a un unique système de Steiner de quintuplets d'ordre 11, mais aucun d'ordre 15 ou d'ordre 17. On connait des systèmes pour les ordres 23, 35, 47, 71, 83, 107, 131, 167 et 243 (dérivés des systèmes S(5,6,v) mentionnés ci-dessous). En 2011, le plus petit ordre pour lequel on ignorait s'il existait un système était 21

### Systèmes pour t = 5

Outre le système S(5,6,12) et le système de Witt S(5,8,24) décrits plus loin, on connaît des S(5,6,v) pour v = 24, 36, 48, 72, 84, 108, 132, 168 et 244, ainsi que des systèmes S(5,7,28).

### Existence de systèmes pour t > 5

En théorie des plans d'expérience, un problème ouvert depuis longtemps était de déterminer s'il existait des systèmes de Steiner non triviaux (c'est-à-dire avec t < k < n) pour t ≥ 6 (les constructions précédentes échouant faute d'existence de groupes simples 6-fois transitifs non triviaux) ; en 2014, Peter Keevash a montré (de manière non constructive) qu'il existait des systèmes de Steiner pour tout t et k, et pour tout n assez grand satisfaisant les conditions de divisibilité données plus $haut^,$ ; la réussite de son approche, fondée sur des méthodes probabilistes, a été jugée comme « une énorme surprise » par Timothy Gowers.

## Propriétés

La définition de S(t,k,n) implique 1 < t < k < n (les égalités amenant à des systèmes triviaux).

Si S(t,k,n) existe, retirer tous les blocs contenant un élément donné (et retirer cet élément de S) donne un système dérivé S(t−1,k−1,n−1). Aussi, l'existence de S(t−1,k−1,n−1) est une condition nécessaire d'existence de S(t,k,n).

Le nombre de sous-ensembles de t éléments de S est ${\tbinom {n}{t}}$, et le nombre de sous-ensembles de t éléments dans chaque bloc est ${\tbinom {k}{t}}$. Comme chacun de ces sous-ensembles est contenu dans exactement un bloc, on a ${\tbinom {n}{t}}=b{\tbinom {k}{t}}$, et donc $b={\frac {\tbinom {n}{t}}{\tbinom {k}{t}}}$, où b est le nombre de blocs. On voit de même que si r est le nombre de blocs contenant un élément donné, ${\tbinom {n-1}{t-1}}=r{\tbinom {k-1}{t-1}}$, ou encore $r={\frac {\tbinom {n-1}{t-1}}{\tbinom {k-1}{t-1}}}$. On a donc la relation $bk=rn$, avec b et r entiers, qui est une condition nécessaire d'existence de S(t,k,n). De plus, comme pour tout système de bloc, l'inégalité de Fisher b ≥ n est vraie pour les systèmes de Steiner.

Étant donné un système de Steiner S(t,k,n) et un sous-ensemble S' de taille t' ≤ t contenu dans au moins un bloc, on peut calculer le nombre de blocs contenant un nombre fixé d'éléments de S' en construisant un triangle de Pascal. En particulier, le nombre de blocs ayant une intersection de p éléments avec un bloc fixé B ne dépend pas du choix de B.

On peut montrer que s'il existe un système de Steiner S(2,k,n), où k est une puissance d'un nombre premier, alors n ≡ 1 ou k (mod k(k−1)). En particulier, un système de Steiner de triplets S(2,3,n) doit vérifier n = 6m+1 ou 6m+3 ; dans ce cas, la réciproque est vraie, c'est-à-dire que pour tout m, des S(2,3,6m+1) et S(2,3,6m+3) existent.

## Historique

Les systèmes de Steiner de triplets furent définis par Wesley S. B. Woolhouse (en) en 1844 dans la question #1733 du Lady's and Gentlemen's Diary, question qui fut résolue par Thomas Kirkman en 1847. En 1850, Kirkman proposa une variante de ce problème connue sous le nom de problème des 15 écolières, demandant de construire des systèmes de triplets ayant une propriété supplémentaire (la résolvabilité). Ignorant les travaux de Kirkman, Jakob Steiner réintroduisit ces systèmes en 1853, dans son propre travail, qui fut plus largement diffusé.

## Groupes de Mathieu

Plusieurs exemples de systèmes de Steiner ont des relations étroites avec la théorie des groupes. En particulier, les groupes de Mathieu sont des groupes d'automorphismes de systèmes de Steiner :

* Le groupe $M_{11}$ est le groupe d'automorphismes d'un S(4,5,11) ;
* Le groupe $M_{12}$ est le groupe d'automorphismes d'un S(5,6,12) ;
* Le groupe $M_{22}$ est l'unique sous-groupe d'indice 2 du groupe d'automorphismes d'un S(3,6,22) ;
* Le groupe $M_{23}$ est le groupe d'automorphismes d'un S(4,7,23) ;
* Le groupe $M_{24}$ est le groupe d'automorphismes d'un S(5,8,24).

## Le système S(5, 6, 12)

Il existe un unique système de Steiner S(5,6,12) ; son groupe d'automorphismes est le groupe de Mathieu $M_{12}.$ Ce système est noté souvent $W_{12}$ dans ce contexte.

### Constructions

**Méthode de la droite projective**

Cette construction est due à Carmichael (en 1937).

On adjoint un nouvel élément, noté ∞, aux 11 éléments du corps fini $F_{11}$ (c'est-à-dire aux entiers modulo 11) ; cet ensemble de 12 éléments, S, peut s'identifier à la droite projective sur $F_{11}.$ Partant du sous-ensemble

$\{\infty ,1,3,4,5,9\},$, on obtient les autres blocs du système S(5,6,12) en répétant des homographies de la forme $z'=f(z)={\frac {az+b}{cz+d}}$, où a, b, c, d sont dans $F_{11}$ et ad-bc est un carré non nul de $F_{11}$, avec la convention usuelle définissant f (−d/c) = ∞ et f (∞) = a/c. Ces fonctions sont des bijections de S sur lui-même ; elles forment un groupe pour la composition, le groupe linéaire projectif spécial PSL(2,11), d'ordre 660. Cinq éléments de ce groupe fixent le bloc de départ, et ce bloc a donc 132 images. Ce groupe étant 5-transitif, on en déduit que tout sous-ensemble de 5 éléments de S apparaît dans une et une seule des 132 images.

**Méthode du chaton**

Une construction alternative de $W_{12}$ utilise le « chaton » de R.T. Curtis, une technique développée pour calculer « à la main » les blocs successifs, en complétant ceux d'un S(2,3,9) provenant de l'espace vectoriel $F_3xF_3.$

**Construction à partir de la factorisation du graphe $K_6**$

Les relations entre les facteurs du graphe complet $K_6$ engendrent un S(5,6,12) : un graphe $K_6$ a 6 différentes 1-factorisations (des partitions des arêtes en couplages parfaits disjoints). L'ensemble des 6 sommets et celui des factorisations correspondent chacun à un bloc. Pour chaque couple de factorisations, il existe exactement un couplage parfait ; il est possible de lui associer 6 blocs. Une simple élimination des blocs possibles restants ayant plus de 4 objets en commun avec les 92 déjà formés laisse exactement 40 blocs, qui forment le S(5,6,12) cherché.

## Le système S(5, 8, 24)

Le système de Steiner S(5, 8, 24), aussi connu sous le nom de système de Witt ou de géométrie de Witt, fut décrit par Robert Daniel Carmichael en 1931 et redécouvert par Ernst Witt en 1938. Ce système a des liens avec plusieurs groupes sporadiques et avec le réseau exceptionnel connu sous le nom de réseau de Leech.

Le groupe d'automorphismes de S(5, 8, 24) est le groupe de Mathieu $M_{24}$ ; dans ce contexte, le système S(5, 8, 24) se note $W_{24}.$

### Constructions

Il existe de nombreuses constructions de S(5,8,24), par exemple les deux suivantes :

**À partir des combinaisons de 8 éléments parmi 24**

Partant de la liste des sous-ensembles de 8 éléments parmi les entiers de 1 à 24, classée par ordre lexicographique, un algorithme glouton éliminant les blocs ayant plus de 4 éléments communs avec un des blocs déjà retenus construit une liste de 759 blocs définissant un S(5, 8, 24) ; cette liste est :

       01 02 03 04 05 06 07 08
       01 02 03 04 09 10 11 12
       01 02 03 04 13 14 15 16
       ... (753 octades omises)
       13 14 15 16 17 18 19 20
       13 14 15 16 21 22 23 24
       17 18 19 20 21 22 23 24

**À partir de chaînes de 24 bits**

En appliquant le même type d'algorithme à la liste de toutes les chaînes de 24 bits (en ne gardant cette fois que celles différant des précédentes en au moins 8 places), on obtient la liste de 4096 chaînes suivante :

Ces chaînes sont les mots du code binaire étendu de Golay. Elles forment un groupe pour l'opération XOR. 759 d'entre elles ont exactement huit bits valant 1, et elles correspondent aux blocs du système S(5,8,24).

