Aller au contenu

Système de Steiner

Un article de Wikipédia, l'encyclopédie libre.
Le plan de Fano est un système de Steiner de triplets S(2,3,7). Les blocs sont les 7 lignes, chacune contenant 3 points. Chaque paire de points appartient à une ligne et une seule.

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

[modifier | modifier le code]

Plans projectifs finis

[modifier | modifier le code]

Un plan projectif fini d'ordre q, les blocs étant ses droites, est un , puisqu'il a points, que chaque droite contient points, et que chaque paire de points appartient à une droite et une seule.

Plans affines finis

[modifier | modifier le code]

Un plan affine d'ordre q est un S(2, q, q2), 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

[modifier | modifier le code]

Systèmes de Steiner de triplets

[modifier | modifier le code]

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 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)[1].

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[2]. 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[3].

Systèmes de Steiner de quadruplets

[modifier | modifier le code]

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 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)[4].

Systèmes de Steiner de quintuplets

[modifier | modifier le code]

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 3 ou 5 (mod 6). De plus, on doit avoir n 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[5]. 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

[modifier | modifier le code]

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

[modifier | modifier le code]

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[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[7],[8] ; la réussite de son approche, fondée sur des méthodes probabilistes, a été jugée comme « une énorme surprise » par Timothy Gowers[8].

Propriétés

[modifier | modifier le code]

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 , et le nombre de sous-ensembles de t éléments dans chaque bloc est . Comme chacun de ces sous-ensembles est contenu dans exactement un bloc, on a , et donc , 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é, , ou encore . On a donc la relation , 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[9]. 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

[modifier | modifier le code]

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[10], question qui fut résolue par Thomas Kirkman en 1847[11]. 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[12], qui fut plus largement diffusé.

Groupes de Mathieu

[modifier | modifier le code]

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 M11 est le groupe d'automorphismes d'un S(4,5,11) ;
  • le groupe M12 est le groupe d'automorphismes d'un S(5,6,12) ;
  • le groupe M22 est l'unique sous-groupe d'indice 2 du groupe d'automorphismes d'un S(3,6,22) ;
  • le groupe M23 est le groupe d'automorphismes d'un S(4,7,23) ;
  • le groupe M24 est le groupe d'automorphismes d'un S(5,8,24).

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

[modifier | modifier le code]

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

Constructions

[modifier | modifier le code]

Méthode de la droite projective

[modifier | modifier le code]

Cette construction est due à Carmichael (en 1937)[13].

On adjoint un nouvel élément, noté ∞, aux 11 éléments du corps fini F11 (c'est-à-dire aux entiers modulo 11) ; cet ensemble de 12 éléments, S, peut s'identifier à la droite projective sur F11. Partant du sous-ensemble , on obtient les autres blocs du système S(5,6,12) en répétant des homographies de la forme , où a, b, c, d sont dans et ad-bc est un carré non nul de , 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[14], 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

[modifier | modifier le code]

Une construction alternative de W12 utilise le « chaton » de R.T. Curtis[15], 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 F3xF3.

Construction à partir de la factorisation du graphe K6

[modifier | modifier le code]

Les relations entre les facteurs du graphe complet K6 engendrent un S(5,6,12)[16] : un graphe K6 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)

[modifier | modifier le code]

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[17] et redécouvert par Ernst Witt en 1938[18]. 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 M24 ; dans ce contexte, le système S(5, 8, 24) se note W24.

Constructions

[modifier | modifier le code]

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

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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 : 

    000000000000000000000000
    000000000000000011111111
    000000000000111100001111
    000000000000111111110000
    000000000011001100110011
    000000000011001111001100
    000000000011110000111100
    000000000011110011000011
    000000000101010101010101
    000000000101010110101010
    ... (4083 chaînes omises)
    111111111111000011110000
    111111111111111100000000
    111111111111111111111111

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

Notes

[modifier | modifier le code]
  1. ↑ Colbourn et Dinitz 2007, pg.60.
  2. ↑ Cette propriété est équivalente à ce que (xy)y = x pour tout x et y.
  3. ↑ Colbourn et Dinitz 2007, pg. 497, definition 28.12
  4. ↑ Colbourn et Dinitz 2007, pg.106
  5. ↑ Östergard et Pottonen 2008
  6. ↑ (en) « Encyclopaedia of Design Theory: t-Designs », Designtheory.org, (consulté le )
  7. ↑ (en) Peter Keevash, « The existence of designs », .
  8. ↑ a et b (en) « A Design Dilemma Solved, Minus Designs », Quanta Magazine,
  9. ↑ Assmus et Key 1994, p. 8.
  10. ↑ Lindner et Rodger 1997, pg.3
  11. ↑ Kirkman 1847
  12. ↑ Steiner 1853
  13. ↑ Carmichael 1956, p. 431
  14. ↑ Beth, Jungnickel et Lenz 1986, p. 196
  15. ↑ Curtis 1984
  16. ↑ EAGTS textbook
  17. ↑ Carmichael 1931
  18. ↑ Witt 1938

Voir aussi

[modifier | modifier le code]

Références

[modifier | modifier le code]

Liens externes

[modifier | modifier le code]
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Système_de_Steiner&oldid=213545375 ».