Chercher à faire… ou chercher qui a fait ?

Dans le quotidien d’un chercheur en mathématique, il n’est pas si rare de se retrouver face à un petit problème concret et intéressant. Ce problème peut provenir de sa propre curiosité et inclination à analyser… ou bien de proches qui pensent – à tort ou à raison – qu’il sera le plus à même de s’y attaquer. Ainsi, j’avais fait part dans un ancien billet de ce problème de planification de matchs, que mon frère m’avait posé. Face à cela, plusieurs situations peuvent se présenter :

• Le problème est en fait évident et l’on peut y répondre immédiatement.
• Il s’agit d’un problème bien connu en mathématique, si bien que l’on peut tout de suite y répondre, ou bien donner de bonnes références expliquant sa solution.
• Le problème semble vraiment complexe, probablement sans réponse connue, ou sans réponse générale, peut-être jamais étudié. Dans ce cas il paraît raisonnable de ne pas s’y attarder plus. Après tout le chercheur n’est pas omniscient, et n’est nullement expert puisque le problème n’a a priori rien à voir avec son domaine de recherche.
• Le problème semble abordable mais d’une complexité juste suffisante pour demander un peu de réflexion et… être intéressant, tout simplement.

Dans ce dernier cas, essentiellement deux approches peuvent se proposer à notre chercheur.

• Chercher… à faire

À savoir, formaliser le problème, chercher à le résoudre, pourquoi pas l’inscrire dans un problème un peu plus général et chercher à rendre sa solution aussi naturelle et simple que possible. Autrement dit… faire soi-même. C’était là essentiellement l’approche que j’avais proposée dans mon précédent billet.

• Chercher… qui a fait

Après tout, le problème est souvent suffisamment simple pour avoir déjà été étudié. Cela semble du bon sens… mais trouver la bonne référence n’est pas toujours si facile lorsqu’il ne s’agit pas de notre domaine d’expertise, et qu’on ne sait pas non plus facilement quel collègue pourrait connaître cela.

Chercher à faire ?

Ainsi, dans le précédent billet, j’avais rapidement identifié qu’il s’agissait d’un problème de planification de championnat, et que cela était forcément bien connu. Pourtant, il m’avait été plus simple de refaire les choses moi-même dans mon cadre, avec la contrainte que je cherchais la solution la plus simple possible à mettre en place (ne nécessitant pas que les équipes doivent aller consulter un planning de matchs, notamment).

Mais récemment, je discutais avec Roland Diel, un collègue de l’université de Nice-Côte d’Azur, de ses travaux portant sur les graphes aléatoires et le modèle de Bradley-Terry en environnement aléatoire. Et voilà qu’en passant il mentionne une méthode de planification de matchs appelée la méthode du ruban ! Il ne fallut pas longtemps pour que je me rende compte que c’était ce que j’avais proposé ! La présentation dans cette page (en anglais), où elle est appelée « polygon method », est même remarquablement proche de ma présentation sur Image des mathématiques ! Et, comme c’est souvent le cas, ce sont sur les pages Wikipedia françaises et surtout anglaises que l’on trouve déjà le plus facilement du contenu, ainsi que des références pour aller plus loin…

Chercher qui a fait ?

Un deuxième exemple, toujours provenant du même frère. J’épargne sa motivation, professionnelle cette fois et concernant l’imagerie médicale, pour me concentrer sur une formulation déjà presque mathématique du problème. Il s’agit d’inscrire des symboles – \(0\) ou \(1\), disons – sur une roue circulaire, de telle sorte que, à partir d’une photo d’une petite partie de la roue sur laquelle on ne voit que n symboles consécutifs, l’on parvienne toujours à identifier où la photo a été prise sur la roue.
En voyant ce problème, on pense naturellement à un codage en binaire de la position… En particulier il y a \(2^n\) suites de \(n\) bits, et donc, au mieux, \(2^n\) positions différentes que l’on peut coder sur la roue. Il est alors naturel d’essayer – si cela est possible – de coder \(2^n\) positions différentes avec \(2^n\) bits placés sur la roue. Par exemple, si \(n=3\), on peut placer dans l’ordre \(00010111\) (bien sûr, dans la roue les trois \(1\) sont alors suivis des trois \(0\) par lesquels on a commencé). On peut aussi regarder, dans l’ordre, les nombres à \(n\) bits obtenus. Dans notre cas, cela donnerait :

\(000 \quad\) \(001\quad\) \(010\quad\) \(101\quad\) \(011\quad\) \(111\quad\) \(110\quad\) \(100\)

On a donc énuméré les 8 nombres à 3 bits, selon un ordre particulier pour lequel un nombre qui s’écrit \(abc\) est toujours suivi d’un nombre s’écrivant \(bcd\) (avec le même \(b\) et le même \(c\)). Si l’on parvient à faire de même avec \(n\) bits, alors le nombre \(x_1\),…, \(x_n\) sera toujours suivi d’un nombre de \(n\) chiffres commençant par \(x_2\),…, \(x_n\).

Avant de réfléchir plus au problème, j’ai alors eu une impression de déjà-vu. Cela m’a fait penser au code de Gray, qui est également une énumération des \(2^n\) nombres à \(n\) bits, mais avec une contrainte un peu différente. Dans un code de Gray, pour passer d’un nombre au suivant, on demande de ne changer qu’un seul bit. Après avoir rafraîchi mes connaissances sur le code de Gray, j’ai du me rendre à l’évidence : ce code ne répondait pas à mon problème (bien qu’il puisse également être utilisé dans des codages de position dans une roue), et je n’avais pas non plus trouvé de variante de ce code qui m’aiderait mieux.

Résultat, je me suis remis à chercher… jusqu’à aboutir à la conclusion que l’on peut effectivement toujours coder \(2^n\) positions différentes, et qu’il y a même beaucoup de façons de faire, mais plusieurs de mes questions restaient sans réponse, et en particulier je ne voyais pas de façon claire, canonique, d’en choisir une.

Si j’avais poussé ma recherche bibliographique un tout petit peu plus loin, j’aurais pu tomber d’abord sur cet article sur IdM, puis sur toute la littérature concernant les suites de de Bruijn. Avec une approche et une présentation remarquablement similaire à celle que j’avais trouvée… mais aussi plus de détails et une réponse plus complète à mes questions (notamment, des algorithmes explicites construisant sans ambigüité une suite de de Bruijn de \(2^n\) bits).

Et donc ?

Chercher à faire ou chercher qui a fait… On le voit, les deux approches s’opposent et se complètent. Le phénomène ne se restreint pas aux anecdotes que j’ai mentionnées, mais touche aussi la recherche actuelle… avec des différences. La principale est que le chercheur, spécialiste de son domaine de recherche, connaît déjà bien ce qui a été fait avant lui. Et c’est encore plus vrai de la communauté de recherche avec laquelle il interagit. Pourtant, il arrive que des travaux soient oubliés puis redécouverts. Pourtant, avec la spécialisation croissante de la recherche, il arrive que différentes communautés regardent des problèmes très proches, sans en avoir conscience !

Chercher à faire ou chercher qui a fait… c’est aussi quelque chose qui dépend de la sensibilité de chacun. Concernant la méthode du ruban ou les suites de de Bruijn par exemple, certains pourraient penser que j’ai perdu inutilement du temps à travailler sur ce qui était bien connu, et ils ont bien-sûr raison. Mais cela m’a également permis de faire ces méthodes miennes, et je les comprends et les maîtrise maintenant bien mieux – me semble-t-il – que si je n’avais eu qu’à aller consulter les réponses au bon endroit. Si l’on pousse le mécanisme à l’extrême, un mathématicien de génie comme Alexandre Grothendieck a pu, dans sa jeunesse, refuser de se renseigner sur la théorie de la mesure de Lebesgue, pour développer sa propre théorie… au final presque équivalente. Cela lui aura tout de même pris deux ans ! Mais peut-on parler de temps perdu ? …