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²), 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)^[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

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

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^[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

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^[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

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^[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

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

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₁₁ est le groupe d'automorphismes d'un S(4,5,11) ;
Le groupe M₁₂ est le groupe d'automorphismes d'un S(5,6,12) ;
Le groupe M₂₂ est l'unique sous-groupe d'indice 2 du groupe d'automorphismes d'un S(3,6,22) ;
Le groupe M₂₃ est le groupe d'automorphismes d'un S(4,7,23) ;
Le groupe M₂₄ 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₁₂. Ce système est noté souvent W₁₂ dans ce contexte.

Constructions

Méthode de la droite projective

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

On adjoint un nouvel élément, noté $\infty$ , aux 11 éléments du corps fini $F$ ₁₁ (c'est-à-dire aux entiers modulo 11) ; cet ensemble de 12 éléments, $S$ , peut s'identifier à la droite projective sur $F$ ₁₁. 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) = \infty$ et $f (\infty) = 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

Une construction alternative de W₁₂ 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 F₃xF₃.

Construction à partir de la factorisation du graphe K₆

Les relations entre les facteurs (en) du graphe complet K₆ engendrent un S(5,6,12)^[16] : un graphe K₆ 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^[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 M₂₄ ; dans ce contexte, le système S(5, 8, 24) se note W₂₄.

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 :

    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

↑ Colbourn et Dinitz 2007, pg.60.
↑ Cette propriété est équivalente à ce que (xy)y = x pour tout x et y.
↑ Colbourn et Dinitz 2007, pg. 497, definition 28.12
↑ Colbourn et Dinitz 2007, pg.106
↑ Östergard et Pottonen 2008
↑ (en) « Encyclopaedia of Design Theory: t-Designs », Designtheory.org, 4 octobre 2004 (consulté le 17 août 2012)
↑ (en) Peter Keevash, « The existence of designs », 2014.
↑ ^{a et b} (en) « A Design Dilemma Solved, Minus Designs », Quanta Magazine, 9 juin 2015
↑ Assmus et Key 1994, p. 8.
↑ Lindner et Rodger 1997, pg.3
↑ Kirkman 1847
↑ Steiner 1853
↑ Carmichael 1956, p. 431
↑ Beth, Jungnickel et Lenz 1986, p. 196
↑ Curtis 1984
↑ EAGTS textbook
↑ Carmichael 1931
↑ Witt 1938

Voir aussi

Block design

Références

(en) E. F., Jr. Assmus et J. D. Key, Designs and Their Codes, Cambridge University Press, 1994 (ISBN 0-521-45839-0, lire en ligne), « 8. Steiner Systems », p. 295–316.
(en) Thomas Beth, Dieter Jungnickel et Hanfried Lenz, Design Theory, Cambridge, Cambridge University Press, 1986. 2nd ed. (1999) (ISBN 978-0-521-44432-3).
(en) Robert Carmichael, « Tactical Configurations of Rank Two », American Journal of Mathematics, vol. 53,‎ 1931, p. 217–240 (DOI 10.2307/2370885, lire en ligne)
(en) Robert D. Carmichael, Introduction to the theory of Groups of Finite Order, Dover, 1956 (1^re éd. 1937) (ISBN 0-486-60300-8)
(en) Charles J. Colbourn et Jeffrey H. Dinitz, Handbook of Combinatorial Designs, Boca Raton, Chapman & Hall/ CRC, 1996 (ISBN 0-8493-8948-8, zbMATH 0836.00010)
(en) Charles J. Colbourn et Jeffrey H. Dinitz, Handbook of Combinatorial Designs, Boca Raton, Chapman & Hall/ CRC, 2007, 2^e éd., 1016 p. (ISBN 978-1-58488-506-1 et 1-58488-506-8, zbMATH 1101.05001)
(en) R.T. Curtis, « The Steiner system S(5,6,12), the Mathieu group M₁₂ and the "kitten" », dans Michael D. Atkinson (éditeur), Computational group theory (Durham, 1982), Londres, Academic Press, 1984 (ISBN 0-12-066270-1, MR 0760669), p. 353–358
(en) D. R. Hughes et F. C. Piper, Design Theory, Cambridge University Press, 1985, 173–176 p. (ISBN 0-521-35872-8).
(en) Thomas P. Kirkman, « On a Problem in Combinations », Macmillan, Barclay, and Macmillan, vol. II,‎ 1847, p. 191–204
(en) C.C. Lindner et C.A. Rodger, Design Theory, Boca Raton, CRC Press, 1997, 198 p. (ISBN 0-8493-3986-3)
(en) Patric R.J. Östergard et Olli Pottonen, « There exists no Steiner system S(4,5,17) », Journal of Combinatorial Theory Series A, vol. 115, n^o 8,‎ 2008, p. 1570–1573 (DOI 10.1016/j.jcta.2008.04.005)
(en) Janne I. Kokkala et Patric R.J. Östergård, « Kirkman triple systems with subsystems », Discrete Mathematics, vol. 343, n^o 9,‎ 2020, article n^o 111960 (DOI 10.1016/j.disc.2020.111960)
(de) J. Steiner, « Combinatorische Aufgabe », Journal für die reine und angewandte Mathematik, vol. 45,‎ 1853, p. 181–182.
(de) Ernst Witt, « Die 5-Fach transitiven Gruppen von Mathieu », Abh. Math. Sem. Univ. Hamburg, vol. 12,‎ 1938, p. 256–264 (DOI 10.1007/BF02948947)

Liens externes

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Steiner system » (voir la liste des auteurs).

(en) Tord Rowland et Eric W. Weisstein, « Steiner System », sur MathWorld
(en) « Steiner system », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, 2002 (ISBN 978-1556080104, lire en ligne)
(en) Steiner systems par Andries E. Brouwer
(en) « Implementation of S(5,8,24) »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)} (consulté le 24 septembre 2017) par Dr. Alberto Delgado, Gabe Hart, et Michael Kolkebeck
(en) S(5, 8, 24) Software and Listing par Johan E. Mebius
(en) The Witt Design calculé par Ashay Dharwadker
(en) Designs exist! [PDF], exposé des résultats de Peter Keevash au séminaire Nicolas Bourbaki, en juin 2015.

Portail des mathématiques

[Handbook-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, 4 octobre 2004 (consulté le 17 août 2012)

[7] (en) Peter Keevash, « The existence of designs », 2014.

[tim-8] {a et b} (en) « A Design Dilemma Solved, Minus Designs », Quanta Magazine, 9 juin 2015

[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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

Exemples

Plans projectifs finis

Plans affines finis

Systèmes de Steiner classiques

Systèmes de Steiner de triplets

Systèmes de Steiner de quadruplets

Systèmes de Steiner de quintuplets

Systèmes pour t = 5

Existence de systèmes pour t > 5

Propriétés

Historique

Groupes de Mathieu

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

Constructions

Méthode de la droite projective

Méthode du chaton

Construction à partir de la factorisation du graphe K6

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

Constructions

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

À partir de chaînes de 24 bits

Notes

Voir aussi

Références

Liens externes

Construction à partir de la factorisation du graphe K₆