La « conception combinatoire » du mathématicien Thomas Kirkman recèle un problème de longue date que l’on croyait impossible à résoudre. Malgré l’existence de variables conformes aux exigences de divisibilité, certaines conceptions seraient impossibles et il n’existerait qu’un seul exemple concret de « conception de sous-espaces ». Dans une nouvelle étude, des chercheurs mettent peut-être fin au dilemme, en suggérant qu’il peut exister une infinité de possibilités de conceptions — entre autres des structures « cachées » —, du moment que le principe de « divisibilité » est respecté.
La conception (ou design) combinatoire remonte à 1850, lorsque Thomas Kirkman proposa une énigme en apparence ludique, mais qui s’avéra être un problème mathématique complexe. Il se pose comme suit : si 15 filles doivent se rendre chaque jour à l’école par rangées de trois pendant sept jours, peut-on les disposer de sorte que chaque paire ne se retrouve jamais plus d’une fois dans le même trio ?
En version plus généralisée : si on a n éléments (les 15 filles) dans un ensemble, peut-on les trier en groupes de taille k (les groupes de trois) de sorte que chaque sous-ensemble t plus petit (les pairs) n’apparaisse pas plus d’une fois dans k ? Surnommées conceptions (n,k,t), ces configurations sont largement utilisées dans le développement de codes de correction d’erreurs, dans le développement d’expériences de laboratoire, dans les tests de logiciels ou encore dans les jeux d’argent et les paris sportifs.
Pendant des décennies, les mathématiciens ont eu du mal à déterminer à quelle fréquence les conceptions peuvent exister. Par exemple, si n=6, il est impossible de faire des groupes de k=3 au sein desquels t=2 ne se répète jamais. Il a alors été conclu que pour pouvoir être réalisées, les combinaisons (n,k,t) doivent respecter des exigences de divisibilité.
D’un autre côté, les modèles de conceptions pour t supérieur à 2 sont extrêmement difficiles à construire et certains chercheurs pensaient que les possibilités se limitaient à t=5. « Il y avait des gens convaincus que ces conceptions existent, et d’autres qui étaient convaincus que c’était impossible », explique Charles Colbourn, informaticien à l’Arizona State University.
La nouvelle étude, en prépublication sur le serveur arXiv, suggère de mettre fin au dilemme en affirmant que de telles conceptions peuvent toujours exister tant que n est suffisamment grand et que les exigences de divisibilité sont respectées. « Ils ont prouvé la potentielle création d’objets dont l’existence n’est pas du tout évidente », estime David Conlon, mathématicien au California Institute of Technology (Caltech). Pour parvenir à leur découverte, les chercheurs ont transposé la conception combinatoire à la conception de sous-espaces, une technique couramment utilisée par les mathématiciens.
Un seul exemple concret précédemment découvert
Un espace vectoriel est composé d’un ensemble d’éléments liés entre eux par des ponts. La conception de sous-espaces « t » s’effectue par le biais d’espaces vectoriels à n dimensions et à k dimensions intermédiaires. Dans cette optique, le problème se pose comme suit : dans un espace vectoriel à n dimensions, peut-on trouver un ensemble de sous-espaces k pouvant contenir de plus petits sous-espaces t ? Le problème est plus ou moins similaire aux conceptions combinatoires ordinaires, mais implique des arrangements vectoriels avec des contraintes plus étroites.
Par exemple, dans un espace vectoriel à 13 dimensions, il est possible d’insérer exactement une fois des sous-espaces à deux dimensions à l’intérieur d’autres à trois dimensions. Il s’agissait auparavant du seul exemple explicite pouvant illustrer la conception de sous-espaces. Ce résultat a nécessité des millions de calculs informatiques, ce genre de modèle étant d’une extrême complexité.
Certains experts ont d’ailleurs estimé que de telles conceptions de sous-espaces sont possibles uniquement pour un nombre limité de dimensions k et t. Cependant, « cela peut être difficile à prouver, mais s’il n’y a pas de raison évidente pour qu’ils n’existent pas, alors ils devraient exister », affirme l’auteur principal de la nouvelle étude, Peter Keevash, chercheur à l’Université d’Oxford.
Une véritable « éponge » à erreurs
La stratégie de Keevash consiste à sélectionner un ensemble prédéfini de sous-espaces, appelé modèle. Ce modèle sert de structure de repère, dans un vaste ensemble de données de hasard. À première vue, ces sous-espaces semblent avoir une structure complètement aléatoire, dont l’arrangement ou l’assemblage semble impossible. Les chercheurs y ont ensuite appliqué une version modifiée d’un processus aléatoire fondamental, appelé « grignotage de Rödl ».
En effet, les scientifiques ont modifié le processus de Rödl de sorte à débuter le grignotage au niveau de ce modèle, comprenant des propriétés algébriques spécifiques. Toutefois, au terme de ce processus, il y a toujours des erreurs à corriger. Néanmoins, une fois que les erreurs se propagent à travers le modèle, elles peuvent toujours être corrigées selon un nombre fini d’étapes. Ce qui aboutit à une conception parfaite.
La prochaine étape consiste à diviser le modèle en plusieurs sous-espaces, qui sont combinés avec ceux de l’ensemble de hasard susmentionné. Ces combinaisons sont effectuées de sorte à pouvoir s’insérer dans de plus grands ensembles. Pour ce faire, chaque mouvement ou déplacement doit s’effectuer de manière très précise. Au final, le modèle obtenu peut être utilisé pour combler toutes les lacunes, que le grignotage de Rödl conventionnel n’aurait pas pu couvrir. Tels une véritable éponge ou un aspirateur, le modèle a ainsi absorbé toutes les erreurs de conception.
En fin de compte, les résultats obtenus par cette technique, dite « technique d’absorption », illustrent la façon dont une méthode contre-intuitive d’exploitation du hasard peut permettre de découvrir des structures inédites et inattendues. La stratégie de Keevash est compatible avec des conceptions beaucoup plus larges que celles précédemment établies et suggère que d’autres problèmes mathématiques pourraient être résolus en combinant le hasard et l’absorption.