Notre but, dans la présente note, est d’analyser du point de vue méthodologique notre recherche sur les groupes symétriques, les groupes alternés et les chaînes minimales (cf. notre article en collaboration avec Robert Erra et Nigel Stewart : On minimal strings containing by decimation the elements of Sn).

L’origine de notre étude est liée au problème de la représentation d’images tridimensionnelles par ordinateur. Plus précisément, nous nous sommes intéressés aux chaînes qui contiennent par décimation d’une part tous les éléments du groupe symétrique (i.e. toutes les permutations d’un alphabet) et d’autre part tous les éléments du groupe alterné (i.e. toutes les permutations paires d’un alphabet). Dans cette approche les objets à représenter par ordinateur sont simplement codés par des lettres, et par décimation nous entendons que si nous enlevons des lettres de la chaîne considérée nous retrouvons les lettres de l’élément du groupe symétrique ou du groupe alterné, et ce, dans le même ordre. Notre étude concernait les chaînes minimales, au sens de la longueur, qui vérifient cette propriété. Une chaîne minimale n’est bien sûr pas unique puisque son inverse est aussi minimale. Par ailleurs comme nous pouvons renoter toute chaîne minimale nous n’étudions que les chaînes minima les normalisées.

La phase initiale de notre recherche a consisté d’une part à implanter en C++ un algorithme de recherche exhaustive de chaînes solutions et d’autre part à trouver une borne théorique sur la longueur suffisante de la chaîne. C’est cette première phase qui nous a permis de connaître les premières valeurs de la formule que nous cherchions, à savoir : 1,3,7,12 et 19. De plus nous avons remarqué qu’il était facile de remplacer la longueur triviale de la chaîne (n*n!) par (n*n) et surtout par (n*n-n+1). Ainsi nous étions dans le cadre des formules quadratiques. Cependant les valeurs trouvées par la recherche exhaustive montraient que même la dernière formule n’était pas optimale. Aussi nous avons décidé de générer systématiquement toutes les chaînes solutions pour une longueur donnée. Et là, comme cela se produit souvent dans les recherches où interviennent les ordinateurs, nous nous sommes retrouvés avec une multitude de solutions (plus d’une centaine). Alors, afin de mieux com prendre l’essentiel dans cette masse de résultats nous avons introduit des contraintes.

A ce niveau, il est nécessaire de faire une remarque sur l’introduction de contraintes dans la résolution d’un problème donné. Un exemple générique de l’application de cette méthode est le problème suivant. En utilisant des dominos qui recouvrent chacun deux cases, quel est le nombre de pavages différents d’un échiquier 8*8 auquel on a supprimé deux coins sur la même diagonale ? La résolution de ce problème qui peut sembler difficile au premier abord (surtout après une phase expérimentale) s’avère élémentaire avec l’introduction de contraintes. Dans ce cas en l’occurrence, les contraintes sont les couleurs ! En effet si l’on considère cette fois un échiquier comme un ensemble de cases noires et blanches alors il est évident qu’un domino, une fois posé, recouvre deux cases de couleurs différentes. Or les deux coins qui se trouvent sur la même diagonale sont de même couleur. c.q.f.d.

Ainsi nous avons résolu un problème en lui ajoutant des contraintes et ensuite nous les avons supprimées tout en conservant la résolution ! Afin de procéder de manière analogue nous avons choisi une famille particulière parmi toutes les solutions obtenues afin de reconnaître un motif. Il est, par contre, difficile d’expliquer notre choix si ce n’est que la famille était symétrique : en tout cas d’une certaine manière notre motif était intelligible et c’est sans doute cela le plus important. A partir de là nous avons exploré le domaine de recherche restreint à ce modèle ce qui nous a permis de pousser les calculs sur ordinateur beaucoup plus loin qu’auparavant. Voyant que notre modèle fournissait des chaînes solutions pour des valeurs de n beaucoup plus grandes, nous avons étudié ses degrés de liberté via l’utilisation de systèmes de calcul formel tels que Maple et MuPAD. Sur le plan heuristique cette phase a été longue à l’instar d’un test difficile où l’on doit sans cesse remettre en question ses hypothèses afin de trouver à un moment donné la solution. Dans ce problème précis l’apport du raisonnement non uniforme a été fondamental (cf. notre article : La suite de Douglas Hofstadter : un paradigme de raisonnement non uniforme). Quant à la dernière phase de notre recherche sur les groupes symétriques, à savoir la démonstration de l’optimalité de notre modèle, elle est essentiellement basée sur une approche algorithmique (cf. notre article : Sur les styles abstrait et algorithmique en mathématiques).

Par contre pour les groupes alternés, à défaut de trouver une formule optimale, nous avons développé une nouvelle approche heuristique avec l’utilisation d’un algorithme génétique (celui du MIT). Dans l’état actuel de nos connaissances théoriques sur la nature intrinsèque de ce procédé, l’approche démonstrative étant exclue il nous a semblé intéressant d’exploiter ce type d’algorithme en tant que cas extrême d’un raisonnement non uniforme mais développé par l’ordinateur cette fois. En outre notre problème était un cas typique d’applicabilité d’un algorithme génétique. En effet pour une longueur strictement inférieure à (l) il n’y a pas de solution et à partir de (l) il y a beaucoup de solutions aussi il est a priori facile pour l’ordinateur de trouver parmi celles-ci une solution minimale. Ainsi sans être démonstratif, l’algorithme génétique a confirmé du point de vue heuristique, l’ensemble de nos conjectures sur les groupes alternés.