Soutenance mémoire
Combinatoire
La combinatoire est un vaste domaine. Il n’est pas simple d’en donner une définition. S’il nous fallait en énoncer une, nous dirions sans doute que la combinatoire est l’ensemble des techniques qui servent à dénombrer ou énumérer des ensembles paramétrés finis. Elle se scinde historiquement en plusieurs branches dont la combinatoire énumérative et la combinatoire algébrique. La combinatoire énumérative s’intéresse principalement au dénombrement. Un de ses objectifs est de proposer des formules pour compter des objets combinatoires. Évaluer la pertinence d’une de ces formules n’est en général pas automatique. Cela relève le plus souvent d’un art qui prend en compte divers paramètres tels que la complexité de la formule, ses liens avec d’autres objets combinatoires, sa concision, . . . Une de ses autres branches, la combinatoire algébrique, fait le pont entre la combinatoire et l’algèbre. Elle applique, entre autres, les techniques combinatoires aux structures algébriques et inversement dote les objets combinatoires de structures algébriques.
Un problème de communication
Nous souhaitons organiser la transmission de messages écrits dans une langue alphabétique à travers un canal (sans perte) n’acceptant que des suites binaires. Appelons S et JC 1 les deux personnages souhaitant communiquer à travers ce canal. Pour cela, ils peuvent se mettre d’accord, a priori, sur une table qui encode chaque caractère de leur alphabet en une suite binaire finie. Par exemple, si S et JC choisissent la table d’encodage Lettre Encodage a 0011b 01000c 1d 10(1.1) alors pour transmettre le message bac il leur faudra envoyer sur le canal la suite binaire 0100000111. De même, si S envoie cbcc à JC alors JC recevra la suite binaire 10100011. (1.2)
1. Les lettres a et b étant déjà utilisées dans cette introduction, nous avons tiré ces initiales au hasard.
Cependant, cette suite binaire est également l’encodage du message dda. La communication est de ce fait ambiguë ! Ils ne peuvent donc pas utiliser n’importe quelle table d’encodage. Nous appelons code un ensemble de suites binaires tel que chaque suite binaire admette au plus une décomposition en éléments de l’ensemble. L’ensemble {0011, 01000, 1, 10}, issu de la table (1.1), n’est donc pas un code puisque que nous savons que la suite (1.2) admet au moins deux décompositions différentes. En effet, 10100011 = (1)(01000)(1)(1) = (10)(10)(0011). La communication sera non-ambiguë si et seulement s’ils choisissent une table d’encodage dont l’ensemble des suites binaires d’encodage forme un code. Une façon simple de construire un code est d’utiliser la notion de préfixe. On dit qu’une suite binaire x est préfixe d’une autre suite binaire y s’il existe une suite binaire u telle que y = xu. Par exemple, la suite 01 est un préfixe de la suite 011101 mais pas de la suite 110. Par extension, on dit qu’un ensemble de suites binaires est préfixe si aucune de ses suites n’est le préfixe d’une autre suite de l’ensemble. Par exemple, l’ensemble infini {1, 01, 001, 0001, 00001, . . . } est un ensemble préfixe. En effet, aucun élément de la forme 0 · · · 0| {z }n1 (pour n ≥ 0) n’est le préfixe d’un autre élément de cette forme. Un ensemble préfixe est nécessairement un code car si une suite binaire a deux décodages différents alors le premier élément d’une des décompositions est le préfixe du premier élément de l’autre décomposition. Par exemple, dans la table (1.1), l’encodage de la lettre c est un préfixe de l’encodage de la lettre d.
Factorisations de Sands
Nous n’avons pas trouvé de factorisations de Sands associées à nos codes mais nous avons obtenu des contraintes sur leurs existences. Supposons le code Y2 inclus dans un code maximal fini et soit (L, R) une factorisation associée à ce code. Nous savons donc que L ⊇ {0, 3, 8} et R ⊇ {0, 1, 7, 13, 14}. Remarquons que (L, 8R), (L, 3R) et (L, 5R) ne sont pas des factorisations car 8 + 8 × 0 = 0 + 8 × 1, 8 + 3 × 0 = 0 + 3 × 1 et 8 + 5 × 0 = 3 + 5 × 1. Donc d’après la contraposée du théorème 2.2.3, nous savons que |R| est un multiple de 2 × 3 × 5. L’ordre de la lettre a est donc de la forme 30 × k, avec k ≥ 3. En suivant le même raisonnement nous avons calculé la table suivante. Remarque 2.2.4. Un couple (L, R) est une factorisation d’un groupe G si et seulement si (L, R − r) est une factorisation du même groupe, où r ∈ R. Donc si (L ⊇ {0, 5, 13}, R ⊇ {0, 2, 11, 12}) est une factorisation associée aux codes Z9 et Z10 alors (L, R − 11) est une factorisation de Sands. Nous savons donc que si un des codes cités dans la table (2.2.1) est un contre-exemple à la conjecture commutativement équivalent alors pour produire un de ces contre-exemples il nous faudra chercher un code maximal fini possédant des mots de longueurs supérieures ou égales à 90. Or ceci est hors de portée de nos programmes informatiques. Nonobstant ces résultats, le lien (et la condition qui en résulte) entre la théorie des codes et la théorie des factorisations des groupes cycliques, tel qu’énoncé dans le théorème 2.2.2, souffre selon nous d’au moins trois défauts lorsqu’il est appliqué aux codes baïonnettes. Premièrement, nous avons trouvé des codes non commutativement préfixes qui vérifient cette condition sans pour autant trouver de codes maximaux finis les contenant. Cette condition est donc trop faible. Deuxièmement, le lien ne concerne que les codes contenant le mot b ; le lien exclut de facto 43 des 70 codes. 4 Et pour finir, le lien ne prend en compte que les mots appartenant à l’ensemble ba∗ ∪ a∗ b. Nous introduisons dans la partie suivante un nouvel objet que nous appelons code baïonnette modulaire afin de pallier ces défauts.
Plus petits codes non inclus dans un code maximal fini
Le plus petit code (au sens de la longueur du plus long mot et du cardinal) connu à ce jour qui ne soit pas inclus dans un code maximal fini est le code {aaaaa, ab, b, baa} d’Antonio Restivo [Res77]. Il l’a trouvé grâce au lien entre les factorisations des groupes cycliques et la théorie de codes. Nous avons, par une exploration informatique, vérifié que tous les codes dont le plus long mot est de longueur inférieure ou égale à 3 sont inclus dans des codes maximaux finis. Par ailleurs, on ne sait toujours pas s’il existe des codes composés de seulement trois éléments qui ne sont pas inclus dans des codes maximaux finis. Nous proposons pour conclure ce chapitre la conjecture suivante.
Conjecture 2.2.12. Le code {aa, abab, baaa, b} (2.13) est un des plus petits codes, au sens de la longueur du plus long mot et du cardinal, non inclus dans un code maximal fini. Nous laissons le lecteur vérifier que ce code résiste aux outils que nous avons utilisés ou développés au cours de cette partie. En effet, on trouve facilement des factorisations de groupes cycliques qui lui sont associées mais également des codes baïonnettes 2-modulaires complets qui le contiennent.
Perspectives
Nous suggérons dans l’ordre des perspectives pour les trois principaux chapitres de ce manuscrit. Nous proposons deux perspectives pour le chapitre 2, portant sur l’exploration informatique de la théorie des codes. Premièrement, nous nous demandons quels sont les plus petits codes (au sens de la longueur du plus long mot) non commutativement préfixes. On ne sait toujours pas quelle est la longueur du plus long mot de ces codes. Cependant, nous avons montré qu’elle est comprise (bornes incluses) entre 7 et 12. La recherche exhaustive jusqu’à 6 a été effectuée en quelques minutes sur un ordinateur de bureau quadricœur. La recherche exhaustive jusqu’à 7, nous paraît envisageable sur des machines plus conséquentes. En ce qui concerne la borne supérieure, nous pourrions nous restreindre à la recherche de codes non commutativement préfixes dont les mots contiennent au plus deux b. La deuxième perspective est de savoir s’il existe un code modulaire baïonnette complet contenant un code non commutativement préfixe. Une réponse négative démontrerait la conjecture du triangle. Nous soumettons quatre perspectives pour le chapitre 3, portant sur la combinatoire des prographes. Premièrement, nous avons énuméré les prographes selon la nature de leurs générateurs, leurs nombres de générateurs, leurs nombres d’entrées et leurs nombres de sorties. Nous proposons d’y ajouter leurs hauteurs. La hauteur d’un prographe peut être informellement définie comme le plus grand nombre de générateurs traversés par un chemin d’une entrée à une sortie. L’intérêt d’un tel paramètre se manifeste quand, par exemple, les prographes modélisent des circuits électroniques. En effet, dans ce cas la hauteur correspond à la complexité du circuit. Deuxièmement, nous pensons que les prographes peuvent encoder et modéliser des structures qui ne peuvent pas être capturées par la combinatoire classique des arbres. Afin de mesurer cette expressivité, nous nous demandons à quelles classes (rationnelle, algébrique, holonome, D-algébrique,. . . [Sta97]) les séries génératrices (3.23) des prographes appartiennent. Nos recherches informatiques, basées sur le paquet GFun du logiciel Maple, nous laissent penser que ces séries sont pour la plupart non holonomes. Troisièmement, dans leur article [GHJMM03], les auteurs ont trouvé une formule close pour décrire la croissance asymptotique des coefficients (3.26). Nous proposons comme piste de réflexion de généraliser cette formule aux prographes engendrés par un seul type de générateur. Et pour finir, notre construction des prographes peut se généraliser aux prographes à générateurs typés. Informellement, chaque entrée et sortie d’un générateur typé a un type donné. Si p1 et p2 sont des prographes à générateurs typés alors le prographe p1 ◦ p2 n’est défini que si ↑(p1) = ↓(p2) et que la première entrée de p2 est du même type que la première sortie de p1 et ainsi de suite… Nous nous demandons lesquels de nos résultats énumératifs sur les prographes peuvent se généraliser aux prographes à générateurs typés. Nous exposons deux perspectives pour le chapitre 4 qui porte sur la réécriture dans des quotients de l’opérade Mag. Il existe une technique classique en réécriture sur les mots qui consiste à ajouter un nouveau générateur afin d’obtenir une présentation convergente. Nous nous demandons si cette technique appliquée aux opérades peut nous fournir des présentations convergentes de l’opérade Mag{2,3} et des opérades CAs(γ) , quand γ ≥ 4. Nous avons étudié les 10 quotients cubiques de l’opérade Mag. Nous avons observé ces quotients à l’ordinateur. Certains ont des séries de Hilbert qui nous semblent, en utilisant le paquet GFun, être non holonomes.
|
Table des matières
1 Introduction
1.1 Un problème de communication
1.1.1 L’inégalité de Kraft-Redheffer
1.1.2 Non commutativement préfixe
1.1.3 Code maximal
1.2 Combinatoire des circuits
1.2.1 Les arbres tandems de duplication
1.2.2 Chemins combinatoires
1.3 Relations arborescentes
1.3.1 Relation d’associativité
1.3.2 Espace quotient
1.3.3 Réécriture dans les quotients
Plan du manuscrit
2 Une exploration informatique de la théorie des codes
2.1 Codes non commutativement préfixes
2.1.1 Le cas général
2.1.2 Les codes baïonnettes
2.2 Inclusion dans un code maximal fini
2.2.1 Factorisations des groupes cycliques
2.2.2 Codes baïonnettes modulaires complets
2.2.3 Plus petits codes non inclus dans un code maximal fini
3 Combinatoire des prographes
3.1 Une construction des prographes
3.1.1 Intuition sur la construction
3.1.2 Présentation de la construction
3.1.3 Démonstration de la construction
3.2 Prographes et chemins combinatoires
3.2.1 Chemins combinatoires
3.2.2 Une bijection entre les prographes et des chemins
3.3 Conséquences combinatoires
3.3.1 Formules de récurrence
3.3.2 Équation fonctionnelle
3.3.3 Formules closes
4 Réécriture dans des quotients magmatiques
4.1 Opérades et réécriture
4.1.1 Opérade
4.1.2 Arbre binaire et opérade magmatique
4.1.3 Réécriture dans les arbres binaires
4.2 Opérades peignes
4.2.1 Le treillis des opérades peignes
4.2.2 Complétions des opérades peignes
4.3 Quotients cubiques
4.3.1 Classes anti-isomorphes
4.3.2 Réalisations combinatoires
4.3.3 Quotients aux présentations possiblement infinies
Perspectives
Annexes
Bibliographie
Télécharger le rapport complet
