David Madore's WebLog: Mathematics

Ce billet s'adresse au grand public et se veut donc compréhensible par tous[#]. Je vais parler de maths, pour une fois il ne s'agit pas de faire de la vulgarisation mathématique[#2] au sens où je ne vais pas expliquer du contenu mathématique, mais plutôt tenter de parler de « ce que ça fait de faire des maths », i.e., essayer de dire un mot sur comment les mathématiciens « pensent » les maths et en quoi consiste notre métier. Et peut-être en profiter pour dissiper quelques malentendus ou quelques idées reçues sur les mathématiciens ou la recherche en mathématiques.

[#] À l'exception de quelques brefs passages essentiellement limités aux notes en bas de paragraphe (où je ferai parfois référence à un concept technique), passages que je pense qu'on n'aura aucune difficulté à identifier et à ignorer si on ne les comprend pas.

[#2] Ni même de la méta-vulgarisation comme j'ai pu le faire ici, mais ça va rejoindre un peu certaines choses que je raconte dans ce billet.

Il va de soi que ce but est trop ambitieux pour que je puisse le mener avec succès. D'abord parce que tenter de parler de comment on fait des maths sans parler de maths revient, forcément, à brasser de l'air en agitant les mains. Ensuite, parce qu'il n'y a pas vraiment de pratique « typique » du métier de mathématicien (comme il n'y a pas de pratique « typique » de celui d'écrivain), donc je peux au mieux parler de la mienne (donc celle d'un mathématicien possiblement médiocre) en essayant de faire remarquer ce que je crois être plus ou moins partagé par mes collègues. Enfin, parce que j'avais de toute façon trop de choses à dire et que j'ai arrêté un peu quand j'en avais marre d'écrire, donc je relègue plein de choses (sur la communauté mathématicienne, notamment) à un éventuel billet ultérieur.

[Lire la suite…]

Le Docteur No, célèbre[#] pour capturer des mathématiciens et les soumettre à diverses énigmes (précédemment sur ce blog : ici, là, là, là, là et peut-être là) est de retour ! Cette fois-ci il n'a capturé que deux mathématiciens, que nous allons appeler Alice et Bob, mais cela ne l'empêche pas de s'amuser à leur proposer une énigme particulièrement cruelle.

[#] Honnêtement, je ne me rappelle même plus si c'est moi qui ai commencé à appeler Docteur No (comme dans le film de James Bond) le grand méchant de ces énigmes ou si je tiens ça d'ailleurs.

Comme ça fait longtemps que nous n'avons pas eu affaire au Docteur No, je commence par une version jouet de l'énigme, histoire de s'échauffer :

Énigme facile : Le Docteur No a capturé deux mathématiciens, Alice et Bob. Après avoir permis à ceux-ci de se concerter sur leur stratégie, il va les soumettre à son épreuve dont il leur communique les termes. Il communiquera deux entiers naturels de son choix à Alice. Alice choisira un et un seul de ces nombres et ce nombre sera transmis à Bob (qui est l'allié d'Alice). Le but de Bob est de deviner le nombre qu'il n'aura pas reçu : pour ça, il aura droit de proposer un nombre fini quelconque d'essais ; autrement dit, il doit proposer au Docteur No un ensemble fini d'entiers naturels (on peut supposer, cela ne change rien, que le nombre transmis par Alice est aussi mis dedans). Si les nombres initialement choisis par le Docteur No sont dans cet ensemble proposé par Bob, alors les mathématiciens seront libérés ; dans le cas contraire, le Docteur No les tuera avec des tortures particulièrement raffinées.

Comment Alice et Bob font-ils pour être certains d'être libérés ?

La réponse est facile, mais je recommande de prendre le temps de résoudre ce problème avant de passer à la suite (cliquez ici pour la faire apparaître), ne serait-ce que pour vérifier qu'on a bien compris la nature du problème. La réponse est la suivante : Alice communique à Bob le plus grand des nombres qu'elle a reçus, et Bob, recevant ce nombre x, propose l'ensemble (fini) de tous les entiers naturels entre 0 et x ; comme x est le plus grand, l'autre nombre est forcément dans cet ensemble.

Il va de soi que cette solution fonctionne encore si, au lieu que les nombres proposés par le Docteur No soient des entiers naturels, ce sont des entiers relatifs ou des rationnels, car il suffit de coder ceux-ci par des entiers naturels (mais attention, dans la construction ci-dessus, on n'utilisera plus le plus grand nombre, mais le nombre ayant le plus grand code). Mais qu'en est-il pour des nombres réels ?

Contre-énigme : Le Docteur No a capturé deux mathématiciens, Alice et Bob. Il envisage de les soumettre à l'épreuve suivante. Après leur avoir permis de se concerter sur leur stratégie, il communiquerait deux réels de son choix à Alice. Alice devrait choisir un et un seul de ces nombres et ce nombre serait transmis à Bob (qui est l'allié d'Alice). Le but de Bob serait de deviner le nombre qu'il n'aura pas reçu : pour ça, il aurait droit de proposer un nombre fini quelconque d'essais ; autrement dit, il devrait proposer au Docteur No un ensemble fini de réels (on peut supposer, cela ne change rien, que le nombre transmis par Alice est aussi mis dedans). Si les nombres initialement choisis par le Docteur No sont dans cet ensemble proposé par Bob, alors les mathématiciens seraient libérés ; dans le cas contraire, le Docteur No les tuerait avec des tortures particulièrement raffinées.

Pourquoi le Docteur No, dont le code de l'honneur exige qu'il y ait toujours un moyen de résoudre les épreuves qu'il propose, décide-t-il de ne pas proposer cette épreuve ?

C'est que l'épreuve en question serait impossible : cliquez ici pour voir la preuve. En effet, supposons par l'absurde qu'Alice et Bob aient une stratégie, et considérons la réunion Z de toutes les réponses que ferait Bob si Alice lui transmet un entier naturel (y compris les entiers naturels eux-mêmes) : ce Z est dénombrable (comme réunion dénombrable d'ensembles finis), donc il existe un réel qui n'est pas dedans ; soit donc x un réel qui n'est pas dans Z. Maintenant, si y est un entier naturel quelconque, alors si le Docteur No propose {x,y} à Alice, elle doit forcément transmettre x à Bob, car (sinon) en réponse à y celui-ci répondrait avec une partie finie de Z, qui ne contient donc pas x, et ce serait un échec. Donc la réponse de Bob si Alice lui transmet x doit contenir y, et ce, quel que soit l'entier naturel y. Or aucun ensemble fini ne peut contenir tous les entiers naturels, ce qui est une contradiction.

Le Docteur No doit donc rendre son énigme un peu plus facile. Voici comment il envisage de le faire :

Énigme sur les réels : Le Docteur No a capturé deux mathématiciens, Alice et Bob. Il envisage de les soumettre à l'épreuve suivante. Après leur avoir permis de se concerter sur leur stratégie, il communiquerait trois réels de son choix à Alice. Alice devrait choisir deux de ces nombres et ces nombres seraient transmis (dans un ordre non spécifié) à Bob (qui est l'allié d'Alice). Le but de Bob serait de deviner le nombre qu'il n'aura pas reçu : pour ça, il aurait droit de proposer un nombre fini quelconque d'essais ; autrement dit, il devrait proposer au Docteur No un ensemble fini de réels (on peut supposer, cela ne change rien, que les nombres transmis par Alice sont aussi mis dedans). Si les nombres initialement choisis par le Docteur No sont dans cet ensemble proposé par Bob, alors les mathématiciens seraient libérés ; dans le cas contraire, le Docteur No les tuerait avec des tortures particulièrement raffinées.

Le Docteur No est perplexe quant à la difficulté de cette épreuve et demande conseil à Georg Cantor (qui est emprisonné dans son donjon). Que lui répond Cantor ?

[Lire la suite…]

Je continue ma série d'introduction aux mathématiques constructives en parlant d'entiers naturels, de suites et de « principes d'omniscience ». Ce billet est la continuation de celui-ci, qu'il n'est pas forcément nécessaire d'avoir intégralement lu mais auquel je renvoie au moins pour l'avant-propos expliquant de quoi il est question (je renvoie aussi à ce billet plus ancien pour une explication générale et historique à ce que sont les maths constructives).

[Lire la suite…]

[Lire la suite…]

Le théorème de Desargues, que je veux présenter ici, est à la fois un des plus simples et selon moi un des plus jolis et des plus importants de la géométrie plane. Simple, parce qu'il n'est question que de points et de droites (pas de distances, d'angles, de cercles ni de quoi que ce soit du genre, même pas de parallélisme ou de perpendicularité : on dit que c'est un théorème de « géométrie projective »), et parce qu'il n'y a qu'un petit nombre de points impliqués (c'est quasiment le plus simple possible). Joli pour les raisons que je vais essayer d'expliquer, qui tiennent largement à sa symétrie. Et important parce qu'il est un des axiomes de certaines présentations de la géométrie projective. Pourtant, il ne fait pas du tout partie de l'enseignement de la géométrie en France (certainement pas à l'école primaire, mais pas non plus au collège, ni au lycée, ni même dans les classes préparatoires aux grandes écoles). Je vais essayer de parler un peu[#] de ce théorème, et de la « configuration » de points et de droites qu'il définit, en faisant plus d'efforts que d'habitude pour rester compréhensible par le grand public, au moins au début de ce billet, quitte à reléguer des considérations plus techniques en appendice. (Vais-je pour autant arriver à être compréhensible ? à vous de me dire.) En plus, pour changer des billets de ce blog qui sont généralement du pur texte, vous aurez droit à des illustrations, qui, j'espère, rendent les choses plus compréhensibles ! (Que demande le peuple ?) Notez que vous pouvez cliquer sur n'importe laquelle de ces images pour l'agrandir (et comme elles sont quasiment toutes vectorielles, vous pouvez utiliser quelque chose comme control-+/control-− dans votre navigateur pour zoomer ou dézoomer).

[#] Enfin, un peu est une façon de parler, parce que j'ai passé un temps totalement déraisonnable à écrire ce billet (ce qui explique, comme souvent, que la fin soit sans doute un peu bâclée parce que j'en ai eu vraiment marre).

[Lire la suite…]

J'avais expliqué il y a quelques mois que je m'étais engagé à monter un nouveau cours d'informatique théorique (ou faut-il dire de maths de l'informatique ?) pour certains élèves de première année à Télécom PlusÀParis, intitulé Logique et Fondements de l'Informatique (nom de code interne : INF110). (J'avais d'ailleurs publié un premier jeu de transparents dans de billet.) L'occurrence 2023–2024 de ce cours a eu lieu de mi-novembre (2023) à mi-janvier (2024), le contrôle le 26 janvier, et maintenant (enfin, quelques mois après) que j'ai à la fois rendu les notes finales et reçu les retours (anonymes) des étudiants je suis en mesure d'en faire un premier bilan. L'idée de ce billet n'est pas tellement d'entrer dans le fond du sujet (même si je ne peux pas ne pas en parler du tout), à ce sujet voir plutôt les deux paragraphes ci-dessous, mais de parler au niveau méta : pourquoi ce cours, pourquoi ce sujet, comment je l'ai organisé et préparé, ce qui a bien marché et ce qui n'a pas bien marché. Le but est de me permettre à moi-même de faire le point, et donc de réfléchir à ce que je veux changer l'an prochain, et aussi de préparer un exposé où je dois raconter tout ça (cf. la fin du présent billet).

☞ Pour le fond du sujet, je renvoie notamment à ce billet sur la correspondance de Curry-Howard et à celui-ci sur la réalisabilité propositionnelle, qui sont largement adaptés de certains bouts de mon cours, même si la présentation est différente et qu'ils vont plus loin (surtout le second). Je peux aussi renvoyer à ce billet sur des sujets variés en vrac sur lesquels j'ai appris des choses en préparant ce cours. Enfin, je fais un lien vers ce billet sur les degrés de Turing et leur généralisation parce qu'il touche à des questions adjacentes, même si je n'ai pas fait plus qu'évoquer la définition de degré de Turing (ordinaire) dans mon cours.

☞ Pour ce qui est des documents pédagogiques accompagnant le cours, voici quelques liens (dont, malgré ma passion pour la stabilité des URL, je ne garantis pas qu'ils seront pérennes, parce que je ne sais pas comment je vais les réorganiser à l'avenir). D'abord le PDF des transparents (qui est la concaténation idiote de trois parties inégales : ① calculabilité, ② typage simple et calcul propositionnel et ③ introduction aux quantificateurs ; j'ai aussi fait une version « imprimable » des transparents : ①, ② et ③). Les exercices d'entraînement sont : ici sans corrigé et ici avec corrigé. Et le sujet du contrôle est ici sans corrigé et ici avec corrigé. Et si des gens sont intéressés par le source de tout ça, le dépôt Git est ici.

Avertissement usuel : même si j'évoque ici mon travail d'enseignant-chercheur à Télécom, je dois rappeler que, dans ce billet comme ailleurs sur ce blog, je m'exprime à titre purement personnel et que les avis et opinions que je peux exprimer ici (ou ailleurs) sont juste les miens et n'engagent en aucun cas mon employeur (ni qui que ce soit d'autre que moi, et d'ailleurs ils ne m'engagent même pas moi vu que que je me réserve le droit d'en changer à tout moment et sans prévenir). J'ajoute que si vous faites partie des personnes qui ont besoin d'un tel avertissement, il vous est interdit de lire la suite de ce billet.

[Lire la suite…]

Je veux ici de nouveau parler d'informatique théorique, dans son intersection avec les maths (logique, calculabilité, typage), et plus précisément d'un sujet appelé la réalisabilité propositionnelle. Je reconnais qu'il a un petit côté « opération de pub » de ma part : il s'agit d'un sujet qu'on peut qualifier d'obscur, voire ésotérique (largement confiné à une poignée de publications soviétiques des années 1960–1990, dont certaines n'ont même pas été traduites du russe en quoi que ce soit d'autre[#], ce qui le dessert cruellement), et pourtant il me semble que d'une part il a des choses à nous apprendre sur l'informatique, sur ce que peut ou ne peut pas faire un algorithme, et sur le rapport entre ça et le typage, et d'autre part il n'est techniquement pas très compliqué à exposer (j'en ai dit un mot — bien moins que ce qui va suivre, certes — dans mon cours à Télécom qui s'est récemment fini, et je ne crois pas avoir largué tout le monde). Donc je trouve qu'il mérite plus d'attention.

[#] Bon, le fait que ce soit en russe ne devrait pas être un obstacle sérieux, surtout maintenant qu'on a des OCR et des traducteurs automatiques, il n'y a vraiment plus de raison. Le problème, c'est que souvent, et en plus d'être en russe, l'article a le défaut d'être super mal écrit : extrêmement concis et pas toujours super rigoureux comme les mathématiciens soviétiques avaient tendance à l'être, références vagues, et fautes de frappe à foison. (Voyez par exemple cette question que j'ai posée sur MathOverflow en essayant de comprendre l'argument de Ânkov sur la non-réalisabilité de l'axiome de Scott que j'expose plus bas ici de façon, j'espère, nettement plus clair que le texte original : mon russe est enfoui au fond des oubliettes, mais ce n'est vraiment ce qui était le plus problématique en l'occurrence par rapport aux fautes de frappe et au style de rédaction vraiment minimaliste.)

Je ne sais pas si l'entrée de blog qui va suivre peut aider à convaincre qui que ce soit de s'y réintéresser, mais en tout cas, si on lit ce qui suit on pourra se dire qu'on sait une proportion significative de tout le savoir de l'Humanité sur la réalisabilité propositionnelle (i.e., pas grand-chose !), et il n'y a pas beaucoup de sujets techniques pour lesquels on puisse en dire autant.

Ajout (2024-02-14) : Pour les gens qui veulent savoir de quoi ce billet cause mais qui n'ont pas la patience de lire ce pavé (ni même l'introduction), j'ai écrit un résumé en seulement 13 tweets, ici sur Twitter et ici sur BlueSky [on peut lire le fil BlueSky sans avoir de compte dessus].

[Lire la suite…]

Précisions d'emblée que le but de ce billet, qui évoque le rapport entre (pour prendre un exemple célèbre) un chat vivant avec probabilité ½ et mort avec probabilité ½ (« mélange probabiliste ») et un chat dans un état quantique qui combine vivant et mort (« superposition quantique ») n'est pas vraiment de faire de la vulgarisation, encore moins de la physique. Je m'en sers, comme je fais parfois, surtout pour gribouiller rapidement ce que j'ai (moi matheux) réussi à comprendre de textes que je trouve souvent obscurs, et pour noter des questions que je (me) pose si je veux y réfléchir plus attentivement Un Jour™, mais ça ne signifie pas que d'autres trouveront mes explications plus claires que ce qu'on peut trouver ailleurs. Il s'agit essentiellement de choses très classiques, mais que je trouve généralement très mal expliquées (notamment par le fait qu'on prend rarement le soin d'essayer de décrire le parallèle entre mélanges probabilistes et superpositions quantiques séparément avant de dire comment ces deux choses se combinent), quoique certaines des questions que je soulève au passage n'ont pas l'air d'être beaucoup discutées, et c'est dommage.

Quoi qu'il en soit, ce qui suit s'adresse à des lecteurs qui savent au moins un peu d'algèbre linéaire (en gros, pour qui les mots espace de Hilbert ont un sens — je ne parlerai que de la dimension finie donc on peut préférer espace hermitien), et sont globalement familiers avec le fait qu'une matrice hermitienne est diagonalisable. Et encore une fois, mon point de vue va être celui d'un matheux, pas d'un physicien (témoin le fait que je vais à peine évoquer de lois de la physique) : la question est celle de la représentation mathématique d'états d'un système physique. (Et j'en profite pour pointer du doigts certains faits géométriques sur cette représentation.) Mais au passage, ça soulève des questions, qui me semblent intéressantes, sur la philosophie de la physique (notamment que signifient les probabilités, et dans quelle mesure elles font partie de la réalité du monde).

Je dois aussi préciser que j'ai changé plein de fois d'avis sur ce que je voulais raconter ici, que j'ai fait mon plan a posteriori et que j'ai réécrit plein de fois des passages sans vérifier la cohérence avec ce qui était déjà ailleurs, ce qui explique sans doute des virages un peu bizarres, des redites ou incohérences de propos et des digressions inutiles (comme d'habitude, j'essaie de rédiger de manière à ce qu'on puisse les sauter, mais je ne sais pas dans quelle mesure j'y arrive). Par ailleurs, comme ça m'arrive souvent, j'ai écrit ce texte jusqu'au point où j'en ai eu marre de l'écrire, ce qui explique qu'après être parti dans toutes les directions il s'arrête un peu brutalement et sans vraie conclusion — mais je pense que mes lecteurs (enfin, ceux qui sont assez patients pour lire mes billets jusqu'au bout) ont l'habitude de ça.

[Lire la suite…]

Je voudrais essayer de parler ici d'un concept de géométrie (euclidienne), notamment important pour son application en optique, que je trouve à la fois joli pourtant trop peu connu[#] : celui d'« étendue ». En gros, l'étendue est une façon de mesurer la taille d'un ensemble de droites (disons, dans l'espace) de la même manière que le volume est une façon de mesurer la taille d'un ensemble de points. Mais pour commencer, et pour expliquer une façon dont cette notion apparaît, je veux parler des unités et grandeurs lumineuses que sont le lumen, le lux, la candela et la candela par mètre carré, et le lien entre ces unités, et ce qu'elles nous disent. Parce que même le grand public commence à avoir entendu parler des lumens (c'est écrit sur toutes les boîtes d'ampoules, de nos jours), et peut-être de lux (pour le niveau d'éclairement d'une pièce), mais ne sait pas forcément la différence entre les deux (divulgâchis : un lux, c'est un lumen par mètre carré).

[#] À titre d'exemple, je n'en vois pas de trace dans les programmes de classes préparatoires scientifiques françaises, ce que je trouve un peu surprenant. Et ce n'est pas une évolution récente parce que je ne crois pas qu'on m'en ait parlé quand j'étais moi-même en prépa.

La difficulté de l'exercice, c'est que comme je veux parler de divers concepts (l'étendue en géométrie euclidienne, l'étendue en optique géométrique, les unités de mesure photométriques, et quelques conséquences de tout ça) et ce à différents niveaux de vulgarisation, je mais certainement faire de la bouillie. En plus de ça, je suis infoutu de faire le moindre dessin, ce qui n'aide pas pour expliquer un concept éminemment géométrique.

Mais voilà, essayons quand même (bear with me), parce cette histoire de conservation de l'étendue est quelque chose qui me semble important pour comprendre les bases de l'optique, et c'est aussi un concept mathématique pas compliqué mais néanmoins digne d'être noté. Et j'en ai marre de toujours oublier ces choses, alors ce billet de blog est surtout un aide-mémoire pour moi-même.

*

[Lire la suite…]

Les quelques derniers billets de ce blog qui avaient un contenu scientifique (notamment celui-ci et celui-ci) tournaient autour de l'informatique théorique. (Et je compte en écrire encore plusieurs.) Je ne sais pas si le lecteur non spécialiste aura vu la différence avec des maths. Je ne sais pas si je vois une différence avec des maths. Après tout, j'ai rangé ces billets dans la catégorique « maths » (pas que le mécanisme de catégories sur ce blog serve à quoi que ce soit, et c'est peut-être surtout que j'avais la flemme de créer une nouvelle catégorie, mais quand même, c'est une info) ; alors que par le passé, j'ai écrit des entrées sur la physique théorique (comme celle-ci ou celle-là) et je les ai rangées dans une catégorie différente. Peut-être même qu'avec assez de mauvaise foi on pourrait prétendre que la correspondance de Curry-Howard affirme qu'il n'y a pas de différence entre maths et info (mais soyons clairs, ça demande une bonne dose de mauvaise foi, justement).

Ce n'est pas la première fois que je médite sur cette question à laquelle je n'ai pas vraiment de réponse : qu'est-ce que c'est que l'informatique ? — et secondairement, quelle position a-t-elle par rapport aux maths ? et cette position est-elle analogue à celle de la physique ?

(Je précise que ce billet, qui est une méditation décousue et sans véritable point d'arrivée, se veut non-technique, i.e., lisible par tout le monde, mais que fatalement je vais être amené à faire des remarques techniques çà et là : si on ne sait pas de quoi je parle, on peut juste ignorer ces passages, ils ne sont là que pour appuyer ou illustrer mes propos, ils n'en sont pas le cœur. Si vous n'avez vraiment pas le temps de lire, regardez au moins le dernier paragraphe pour un résumé de ce que j'essaie de dire.)

[Lire la suite…]

Allez, en cadeau de Noël, un deuxième billet à deux jours d'intervalle, ce qui est devenu très rare sur ce blog : je vous propose une devinette dont je posterai la solution ultérieurement. Je la trouve très jolie et surprenante et je pense qu'elle aurait beaucoup plu à Raymond Smullyan.

Méta : Elle m'est venue en réfléchissant à des questions de maths (autour de la réalisabilité propositionnelle). La formulation est de moi, mais c'est en fait une réécriture d'un théorème (de Plisko, je donnerai la référence précise en même temps que la solution) dont j'ai lu l'énoncé et que j'ai reformulé comme une énigme pour y réfléchir parce que je ne voulais pas lire la preuve mais la retrouver moi-même. J'ai eu énormément de mal à la résoudre, donc je pense qu'elle est vraiment dure (d'un autre côté, je n'étais pas sûr d'avoir trouver la bonne formulation, donc je réfléchissais à la fois à la question et à la réponse), mais quand je l'ai présentée sur Twitter, au moins une personne a trouvé la solution, donc elle n'est certainement pas insoluble. Même si elle a un rapport distant avec mon très long billet tout récent sur Curry-Howard (et je compte écrire une autre entrée qui fait référence aux deux, et qui explique l'intérêt mathématique de cette énigme), il n'est pas nécessaire, ni même spécialement utile, d'avoir lu ce billet (ni aucun autre) pour réfléchir à cette énigme. En revanche, il est certainement pertinent d'avoir des notions de calculabilité pour espérer y arriver (même si je vais présenter l'énoncé pour qu'il soit compréhensible sans ça). J'éditerai ce billet d'ici quelques jours pour présenter la réponse ainsi que quelques commentaires : pour l'instant je me contente de l'énoncé de l'énigme, suivi de quelques commentaires.

[Lire la suite…]

Méta : Le présent billet, quoique indépendant, est une sorte de suite de celui-ci où j'exposais quelques points d'informatique théorique que j'ai appris, ou mieux/enfin compris, en enseignant un cours que je crée cette année à Télécom. En fait, j'étais parti pour écrire quelque chose sur un sujet plus spéculatif, mais je me suis dit que pour commencer il fallait que j'explique proprement la correspondance de Curry-Howard, et comme c'est justement une des choses que j'enseigne et que je trouve généralement très mal expliqué, autant en faire aussi une entrée de blog ; puis comme j'étais trop débordé par l'écriture des transparents du cours lui-même, j'ai laissé ça de côté. J'ai de nouveau un petit peu de temps avec les vacances, donc je publie et complète séparément ce bout sur Curry-Howard comme un texte autonome, dans l'espoir de faire ensuite un autre billet sur les questions qui, au-delà de mon enseignement du moment, m'avaient initialement motivé à en parler. Mais comme je tombe dans un trou de lapin dès que je me mets à écrire sur un sujet, j'ai quand même élargi le sujet à des questions connexes.

[Lire la suite…]

Ce que j'aime surtout dans le fait d'enseigner, c'est qu'on apprend souvent soi-même plein de choses sur le sujet qu'on enseigne, surtout la première fois, et surtout si on crée soi-même le programme du cours : on croyait bien savoir les choses de loin, mais être obligé de les regarder de près pour les enseigner oblige souvent à se rendre compte qu'il y avait une subtilité là où on ne le savait pas (ou qu'on avait oubliée) ; ça peut éventuellement conduire à une panique zut, l'approche que je croyais avoir tracée pour ce cours ne marche pas ! comment est-ce que je vais m'en sortir ?, mais souvent on en ressort bien plus compétent qu'avant : même si la subtilité qu'on a découverte, finalement, n'est pas enseignée, l'enseignant sera quand même meilleur (ceci étant, les personnes à qui on enseigne la première fois risquent de moins goûter l'expérience, et il faut parfois quelques années pour que la découverte de surprises se tarisse et que l'enseignant soit rôdé).

Pour prendre un exemple passé précis, en enseignant mon cours de théories des jeux (notez le pluriel à théories !) à Télécom — dont les notes sont ici si ça intéresse quelqu'un — je me suis rendu compte d'une subtilité importante dont je n'avais pas du tout pris conscience avant : quand on parle de stratégie dans un jeu (à information parfaite), on peut soit s'intéresser aux stratégies qui, pour prescrire un coup à jouer, dépendent seulement de la configuration actuelle du jeu (appelons-les stratégies positionnelles), soit de celles, plus générales, qui dépendent de tout l'historique de la confrontation jusqu'à ce point (appelons-les stratégies historiques) ; or, même si la règle du jeu ne dépend que de la configuration actuelle et pas de l'historique qui a mené à cette configuration, ce n'est pas du tout évident a priori qu'une stratégie gagnante dans le sens plus général (historique) soit forcément traduisible en une stratégie gagnante dans le sens plus restreint (positionnel) ; et j'avais un peu paniqué, parce que j'avais construit mon cours autour de la démonstration de l'existence d'une stratégie gagnante dans un sens via la théorie des jeux de Gale-Stewart (qui sont intrinsèquement « historiques »), alors que j'en avais besoin ensuite au sens plus fort (« positionnel ») pour la théorie de Sprague-Grundy. J'ai réussi à m'en sortir (j'ai écrit des notes expliquant correctement le lien, voir la section 3.5 du PDF lié ci-dessus), en cours je demande aux élèves d'admettre ce point en les renvoyant au poly s'ils ne veulent pas l'admettre, donc finalement je n'enseigne pas vraiment cette subtilité, mais j'ai été content d'en prendre conscience, et je suis étonné qu'il soit si peu évoqué, ou si mal expliqué, dans la littérature scientifique sur le sujet.

Même en donnant un cours d'analyse (dont je n'étais, cette fois, pas le responsable ni le créateur, mais simple intervenant) j'ai appris un certain nombre de choses sur le sujet, voyez par exemple ce billet passé pour quelque chose que j'ai appris au détour d'un exercice. Et en donnant un cours d'initiation à la géométrie algébrique, je me rends surtout compte… que c'est très difficile d'enseigner la géométrie algébrique et que je ne sais même pas produire une définition d'un morphisme entre variétés quasiprojectives (l'objet fondamental du domaine, quoi) qui ne soit pas abominable dans sa complication.

Bref. Cette année, comme je l'ai raconté ici et là, j'inaugure un cours intitulé Logique et Fondements de l'Informatique où je dois parler de calculabilité, λ-calcul, logique, typage, isomorphisme de Curry-Howard, ce genre de choses (un programme à vrai dire assez ambitieux, mais on m'a donné comme consigne de profiter de la création de la filière MPI en prépa pour viser quelque chose d'assez sérieux). Des choses, à cheval entre mathématiques et informatique théorique, qui me plaisent beaucoup (sur la calculabilité voyez par exemple ce long billet) et sur lesquelles je pensais ne pas avoir grand-chose à apprendre… Famous last words!

(La suite de ce billet est essentiellement un brain dump de quelques unes des choses que j'ai apprises, réapprises, ou mieux comprises en préparant ce cours jusqu'à présent. Noter que ça ne veut pas dire que je vais les enseigner ! Ou du moins pas forcément sous cette forme. Comme les petits bouts de ce billet, de longueur très inégales, sont assez indépendants, je les ai séparés par des fleurons : si on n'aime pas ce que je raconte à un endroit donné, on peut sauter jusqu'au fleuron suivant.)

❦

Il y a des choses que j'ai apprises en marge de la préparation de ce cours, sans que ça ait vraiment d'impact dessus. Par exemple, comment on fabrique des modèles du lambda-calcul non typé (pour ceux qui veulent en savoir plus là-dessus, j'ai bien aimé l'article From computation to foundations via functions and application: The λ-calculus and its webbed models de Chantal Berline, et notamment la partie sur les K-modèles, qui m'ont semblé les plus parlants de tout cette histoire : de façon très sommaire, on représente un terme par l'ensemble de tous les types qu'on peut lui attribuer dans un certain système de typage dont les types ne sont pas disjoints ; en plus ça semble avoir un rapport avec la réalisabilité, ce qui n'est pas déplaisant) : ce n'est pas spécialement une difficulté que j'ai rencontrée, juste quelque chose que j'ai appris au passage.

❦

Il y a aussi des choses que je pensais savoir sans vraiment y avoir suffisamment réfléchi. Notamment, comment fonctionne au juste le combinateur de point fixe Y de Curry. J'avais déjà appris il y a longtemps que dans un langage fonctionnel non typé on peut faire des appels récursifs sans faire d'appels récursifs, par exemple (en Scheme) :

(define proto-fibonacci
  (lambda (self)
    (lambda (n) 
      (if (<= n 1) n
	  (+ ((self self) (- n 1)) ((self self) (- n 2)))))))
(define fibonacci (proto-fibonacci proto-fibonacci))

— code la fonction définie récursivement[#] par F(n)=n si n≤1 et F(n) = F(n−1) + F(n−2) sinon, sans jamais que la fonction fasse appel à elle-même dans sa définition (c'est, en fait, l'astuce de Quine — qui n'est pas due à Quine, c'est Hofstadter qui lui a donné ce nom-là, mais à Cantor, Gödel, Turing et Kleene — et sur laquelle j'avais écrit une page alors que mes élèves actuels n'étaient même pas nés). L'astuce (de Quine qui n'est pas de Quine), donc, c'est qu'on passe la fonction proto-fibonacci en argument à la fonction proto-fibonacci, et quand elle a besoin de faire appel à elle-même, elle applique son argument (self) en prenant bien soin de lui passer une copie de lui-même, d'où le self self dans ce code.

[#] Oui, je sais que la suite de Fibonacci est un très mauvais exemple de récursion parce qu'en vrai il ne faut pas la coder de façon récursive, c'est épouvantable pour la complexité ; mais c'est un exemple facile à lire, donc je le reprends avec cet avertissement qu'il ne faut pas faire comme ça pour autre chose que pour illustrer les appels récursifs.

Vous noterez bien, donc, qu'il n'y a pas d'appels récursifs dans ce code. La même astuce de Quine permet de faire un programme qui s'écrit lui-même même si le langage ne permet pas de faire référence à lui-même (voyez ma vieille page liée ci-dessus pour tous les détails), à Gödel de fabriquer un énoncé qui dit je suis indémontrable, etc. Ici ça sert à ce qu'une fonction s'appelle elle-même même si le langage ne permettait pas les appels récursifs comme construction spéciale (par exemple en λ-calcul, il n'y a pas de construction récursive).

Ici on est dans un langage fonctionnel donc on peut juste appeler une fonction passé en argument, mais dans un langage non fonctionnel capable d'écrire un interpréteur de lui-même, on pourrait quand même simuler les appels récursifs en lançant l'interpréteur (sur une représentation du code de la fonction !) à chaque fois qu'il est écrit self self dans le code ci-dessus, ce qui est la façon la plus mind-blowing de faire de la récursion, et je ne m'étais pas rendu compte de ça avant de commencer à préparer ce cours.

[Lire la suite…]

La chaîne de télé Arte produit une série de petites vidéos de vulgarisation scientifique (à destination du grand public) sur les mathématiques appelée Voyages au pays des maths (on les trouve ici sur le site web d'Arte ou ici sur YouTube) : je n'en ai regardé qu'une partie (via leur site Web : je ne suis pas tombé dessus à l'antenne, mais c'est juste parce que je n'allume jamais la télé), mais celles que j'ai vues me semblent globalement correctes : il y a parfois des affirmations douteuses ou qui peuvent induire des idées fausses mais je n'ai rien entendu dans celles que j'ai regardées qui me fasse bondir au plafond ; la présentation est plutôt pas mal au sens où j'ai l'impression que tout le monde peut accrocher au moins un peu, et comme chacune dure 10 minutes, même si on n'aime pas, on n'a pas le temps de s'endormir et je pense que ça peut convaincre des gens d'essayer au moins de s'intéresser un minimum au genre de choses sur lesquelles les maths se penchent. (Je peux éventuellement reprocher au choix des sujets, même s'il est agréablement éclectique, de mélanger des choses qui sont des problèmes profonds et difficiles avec des petites curiosités qui ne font pas l'objet de recherches ; ce n'est pas grave en soi, mais il faudrait peut-être mieux expliquer au public ce qui tombe dans chaque catégorie.)

Comme je l'avais raconté dans cette entrée passée de ce blog, je suis moi-même intéressé par la vulgarisation mathématique, pas pour le contenu de ce que ça raconte, mais pour apprendre à améliorer ma propre présentation des choses, qu'il s'agisse de vulgarisation, d'enseignement (ou même d'exposition à des pairs), et à tous les niveaux (du grand public aux chercheurs).

Or il se trouve justement que dans cette série Voyages au pays des maths est paru un épisode intitulé L'Entscheidungsproblem ou la fin des mathématiques ? (visible ici sur le site web d'Arte ou ici sur YouTube) qui porte sur le même sujet — la calculabilité — sur lequel j'ai récemment publié les transparents d'un cours que j'inaugure cette année à Télécom Paris (et aussi un billet qui se veut grand public sur un thème apparenté).

Du coup je suis curieux de savoir comment ce genre de vulgarisation est jugé par le grand public : j'apprécierais si des personnes qui lisent mon blog, surtout celles qui ne sont pas mathématiciennes, idéalement même pas scientifiques, pouvaient regarder cette vidéo de 10 minutes et me dire ce qu'elles en pensent : ce qu'elles en retiennent, si elles ont l'impression de comprendre les enjeux évoqués, quels passages sont clairs, lesquels ne le sont pas, ce genre de choses, et si elles sont d'accord avec mes critiques qui vont suivre.

(Si possible, merci de regarder la vidéo avant de lire la suite pour ne pas se laisser influencer par mes propres remarques qui vont suivre ; et aussi tout bêtement parce qu'elles sont sans doute difficiles à lire si on n'a pas vu la vidéo avant.)

[Lire la suite…]

Comme je le disais il y a un mois, je me suis engagé à organiser à Télécom Paris(PlusÀParis) un cours de Logique et Fondements de l'Informatique où je dois parler de calculabilité, logique et typage. Je suis évidemment complètement à la bourre sur la préparation de ce cours, qui commence vendredi en huit, mais bon, j'ai au moins provisoirement fini d'écrire des transparents pour la partie « calculabilité » qui devrait occuper, je pense, bien 6h de cours (sur 22h au total pour le cours magistral ; il y a des TD/TP à côté). Autant que je rende ça public dès maintenant, des fois que des gens voudraient m'aider à corriger les fautes. Donc :

Ces transparents sont en ligne ici

(Je compte concaténer ceux de la suite du cours quand il seront écrits. Je ne sais pas encore comment je veux diviser ça donc ce n'est pas évident de choisir des adresses intelligemment.)

J'ai à peine commencé à les relire, donc c'est certainement bourré de typos et de fautes plus ou moins graves. J'espère quand même qu'il n'y a pas d'erreur tellement grave qu'elle m'obligerait à tout restructurer.

Si vous faites des commentaires, pensez à me donner l'identifiant Git (en bas du premier transparent) auxquels ils se rapportent. (Au moment où j'écris ce billet, c'est 31080ea Wed Nov 1 11:06:40 2023 +0100 ; l'arbre Git avec le source est ici.)

Il faut préciser que ça s'adresse à des élèves ayant déjà fait de l'informatique en prépa (filière MPI ou filière MP option info, plus quelques uns venus de licences d'info ; les programmes des classes prépa sont ici), donc d'une part ce n'est pas comme s'ils découvraient tout, d'autre part on peut les espérer motivés par le sujet.

Dans cette partie calculabilité, je présente les fonctions primitives récursives et surtout générales récursives, les machines de Turing et le λ-calcul non typé, l'esquisse de l'équivalence entre les trois présentations de la calculabilité (fonctions générales récursives, machines de Turing et λ-calcul non typé), ainsi que divers résultats classiques fondamentaux : théorème s-m-n, théorème de récursion de Kleene, existence d'une machine universelle, résultats élémentaires sur les ensembles décidables (= calculables) et semi-décidables (= calculablement énumérables), et bien sûr l'indécidabilité du problème de l'arrêt (et aussi l'incalculabilité de la fonction « castor affairé »). Dans la suite du cours, il est prévu de parler de λ-calcul simplement typé en lien avec le calcul propositionnel intuitionniste, puis de diverses extensions (logique classique, logique du premier ordre, et évoquer divers bouts du cube de Barendregt). Le fil conducteur du cours est censé être quelque chose comme ceci : L'indécidabilité du problème de l'arrêt signifie que tout langage informatique qui garantit la terminaison des programmes est nécessairement limité ; des systèmes de typage de plus en plus puissants cherchent à rendre cette limitation aussi faible que possible.

J'ai renoncé à parler, même allusivement, de machines avec oracle ou de degrés de Turing ; mais les gens qui veulent en savoir plus sur ce sujet peuvent se référer à ce billet interminable pour lequel les notes ci-dessus suffisent largement en matière de prérequis.

Ajout (2023-11-02) : Suivant ce qu'on m'a fait remarquer en commentaire, j'ai ajouté (Git 1cdc719 Thu Nov 2 17:08:48 2023 +0100) des choses sur le théorème de Rice et les réductions (many-to-one et de Turing). Il est cependant vraisemblable que j'en saute au moins une partie.

Le fait de me replonger dans le λ-calcul non typé, et de vouloir en savoir plus que le minimum que j'enseigne, m'a obligé à réapprendre plein de choses à son sujet[#], que j'avais complètement oublié ou jamais sues, et redécouvrir toutes les petites crottes de ragondin qui polluent un sujet qui a superficiellement l'air simple et élégant (comme : la différence entre β-réduction et βη-réduction, la différence entre termes normalisables et fortement normalisables, la différence entre stratégie de réduction extérieure gauche et intérieure gauche, la différence entre forme normale, forme normale de tête et forme normale de tête faible, etc.) ; le livre de Barendregt (The Lambda Calculus: Its Syntax and Semantics) est assez abominable en matière de dissection de crottes de ragondin, et celui de Krivine (Lambda-calcul : types et modèles — disponible en ligne en traduction anglaise) ne l'est pas moins. Un des problèmes est sans doute qu'on n'a pas vraiment idée de ce que sont les termes du λ-calcul non typé (prima facie, ce sont des fonctions qui prennent en entrée une autre fonction de même sorte et renvoient une autre fonction de même sorte : ce n'est pas du tout clair qu'on puisse fabriquer un objet qui soit aussi l'objet des morphismes de lui-même dans lui-même !) : divers gens (en commençant par Dana Scott à la fin des années 1960) ont réussi à en donner des modèles, ce qui éclaircit un peu la sémantique, mais là aussi on se perd entre les différentes manières de fabriquer des modèles du λ-calcul et les zillions de relations d'équivalence entre types que fournissent ces façons de fabriquer des modèles. (J'ai commencé à lire plein de choses sur le sujet, et surtout à me noyer dans les notations pourries. J'espère que l'article From computation to foundations via functions and application: The λ-calculus and its webbed models de Chantal Berline m'aidera à y voir plus clair.)

Je suis assez étonné, en revanche, de ne pas trouver d'implémentation (libre, flexible et largement disponible) du λ-calcul non typé, qui permettrait de tester un peu les choses (transformer les notations, réécrire les termes à la main ou de façon automatisée, comparer les stratégies de réduction, etc.). Est-ce que j'en ai raté une évidente ?

[#] La première fois que j'ai appris des choses sur le λ-calcul, ça devait être vers 1990 quand on m'a offert le livre de vulgarisation scientifique The Emperor's New Mind de Roger Penrose (j'en ai parlé dans une section d'une entrée récente), qui décrit un peu le λ-calcul et les entiers de Church, et ça m'a complètement fasciné que des règles typographiques aussi simples et élégantes (← mais bon, en fait, une bonne quantité de poussière avait été glissée sous le tapis) puissent donner quelque chose d'aussi puisant.

Ajout (2023-11-12) : Par pure coïncidence, la chaîne de télé Arte vient de produire, dans le cadre de sa série Voyages au pays des maths, un mini-documentaire de vulgarisation (10 minutes) intitulé L'Entscheidungsproblem ou la fin des mathématiques ? (ici sur YouTube, ici sur le site web d'Arte) et qui porte justement sur le sujet dont je parle ici. Je ne suis pas d'accord avec tous les choix de présentation, mais ça donne au moins une idée de ce dont il est question (et notamment, tenter de vulgariser l'équivalence entre fonctions générales récursives, machines de Turing et λ-calcul était un défi pas du tout évident, et je trouve qu'il s'en sort pas mal). Surajout : voir ce nouveau billet où je décortique un peu plus cette vidéo.

Ajout (2024-04-30) : j'ai fait un bilan de la première année de ce cours dans un billet ultérieur.

[Lire la suite…]

Le concept d'oracle dont il est question ici est vient de l'informatique théorique (le terme oracle apparaît dans la thèse d'Alan Turing en 1938). Je voudrais essayer d'expliquer de façon très informelle, très vague aussi malheureusement (mais, j'espère, du coup, assez grand public) ce dont il est question.

Une partie de l'informatique théorique (l'algorithmique) s'intéresse, de façon positive, à trouver des moyens de résoudre des problèmes (mathématiquement bien définis), c'est-à-dire à concevoir des algorithmes qui les résolvent : un algorithme est un programme, un plan d'opération susceptible d'être mené dans un ordinateur — mais aussi en principe par un humain particulièrement patient — qui effectue une tâche calculatoire donnée. Par exemple, la manière dont on apprend à faire des additions et des multiplications à l'école primaire sont des algorithmes, même si ce ne sont pas forcément les plus intéressants, ils ont le mérite de nous rappeler qu'un algorithme ne tourne pas forcément sur un ordinateur, on peut aussi l'exécuter à la main (ce sera juste quelques milliards de fois plus lent…) ; d'ailleurs, le mot algorithme fait référence au mathématicien persan (écrivant en langue arabe) Muḥammad ibn Mūsá al-H̱wārizmī parce qu'il a décrit toutes sortes de méthodes systématiques pour résoudre des problèmes mathématiques, qu'on peut donc légitimement qualifier d'algorithmes, et c'était plus de 1000 ans avant l'invention des ordinateurs.

(Petite digression sur le terme algorithme : il semble qu'un mélange entre l'incompréhension des journalistes face à tout ce qui est technique et l'approximation des termes utilisés dans le contexte de l'intelligence artificielle ait fait dévier le sens du mot, dans l'image qu'en a le grand public, vers une sorte de synonyme de système opaque auquel on ne comprend rien. Certainement beaucoup de programmes utilisés dans l'ingénierie informatique moderne (notamment tout ce qui relève de l'IA) comportent énormément d'heuristiques et de méthodes mal comprises, parfois même mal comprises de leurs programmeurs ou concepteurs, et dont la réponse est parfois fausse ou mal spécifiée. Mais le sens d'algorithme en algorithmique désigne au contraire un plan bien défini et bien compris qui arrive à un résultat bien spécifié.)

Mais d'autres parties de l'informatique théorique s'intéressent non pas à concevoir des algorithmes efficaces pour résoudre tel ou tel problème, mais à se pencher sur la notion même d'algorithme et les limites théoriques du concept : que peut-on faire avec un ordinateur ?

Spécifiquement, on s'intéresse alors plutôt à des résultats négatifs : plutôt que résoudre tel ou tel problème c'est-à-dire concevoir un algorithme qui le résout, on s'attache à montrer que tel ou tel problème est difficile (long et coûteux) voire impossible à résoudre par un algorithme, ou au moins, à étudier cette difficulté, à la classifier et à la jauger. Je reste délibérément vague sur ce qu'un problème peut recouvrir ici et ce que difficile veut dire, mais je peux délimiter ici trois grands domaines où ce que je veux dire s'applique, et j'en profite pour parler un peu plus longuement de chacun des trois, en gros du plus théorique vers le plus appliqué (il n'est pas nécessaire de lire tout ce que j'écris sur chacun ci-dessous pour passer à la suite, mais je cherche à donner un minimum de contexte) :

• La théorie de la calculabilité est la branche de l'informatique théorique (possiblement la plus proche des mathématiques pures, et notamment de la logique) qui étudie ce qu'on peut faire algorithmiquement avec des ressources illimitées, c'est-à-dire, en disposant d'un temps illimité et d'une mémoire illimitée. (Le mot illimité signifie ici fini mais arbitrairement grand, sans limite a priori : c'est-à-dire que les algorithmes en question doivent s'arrêter un jour en disant j'ai terminé, mais ils ont le droit de prendre autant de temps qu'ils veulent, tant que ce temps est fini ; idem pour la mémoire : ils ont le droit de stocker toutes les données qu'ils veulent tant que cet espace utilisé reste fini à tout moment. C'est donc la forme la plus abstraite et théorique de la question que peut-on faire avec un ordinateur ? qui est étudiée ici, et elle déborde sur des questions du type comment peut-on imaginer des types de machines fondamentalement et théoriquement plus puissantes qu'un ordinateur même si elles ne sont pas réalisables en pratique ? — mentionnons par exemple que même un ordinateur quantique, qui si on réussissait à en construire serait pour certains types de problèmes incroyablement plus efficace qu'un ordinateur tel que nous disposons actuellement, ne représente pas un saut qualitatif tel qu'il peut intéresser la calculabilité : pour la calculabilité, un ordinateur quantique, un ordinateur classique, un système d'engrenages mécaniques ou encore un humain extrêmement patient et systématique muni d'un stylo et d'un papier et exécutant mécaniquement des opérations prédéfinies valent exactement la même chose.)

  La calculabilité est un peu la mère de l'informatique, parce que c'est au travers de la recherche d'une formalisation de ce qu'est un algorithme, et ce qu'un algorithme peut faire, qu'Alonzo Church et son étudiant Alan Turing sont arrivés au concept de calculabilité ; la définition précise d'algorithme à laquelle Turing est arrivé, la machine de Turing, est considéré comme une préfiguration théorique de ce qu'est un ordinateur.

  Un des thèmes majeurs de la calculabilité, donc, c'est de montrer que, pour des raisons théoriques, certains types de problèmes (mathématiquement bien posés) ne sont pas résolubles algorithmiquement : même avec un temps illimité(-mais-fini) à votre disposition, et autant de mémoire, vous ne pourrez pas écrire un algorithme qui répond à coup sûr à certaines questions qui admettent pourtant une réponse bien définie.

  L'exemple archétypal à ce sujet est le problème de l'arrêt : très grossièrement, ce problème demande justement, donné un algorithme, i.e., une suite d'instructions à exécuter (qui peut, bien sûr, contenir des boucles, du type répéter les instructions suivantes tant qu'une certaine condition n'est pas vérifiée), et des valeurs à fournir en entrée à cet algorithme, si l'algorithme en question finit (i.e., si le calcul aboutit à un résultat). Le théorème majeur de Turing, qui est à la base de la théorie de la calculabilité (et donc, dans un certain sens, de l'informatique ; mais à l'origine il s'y intéressait pour des raisons liées à la logique mathématique et spécifiquement au théorème de Gödel), c'est qu'aucun algorithme ne peut résoudre le problème de l'arrêt : autrement dit, aucun algorithme ne peut dire à coup sûr si un autre algorithme s'arrête au bout d'un temps fini. (La seule façon de savoir est de l'exécuter, ce qu'on peut faire, mais quand on l'exécute, tant qu'il n'est pas fini, on n'est jamais sûr si le programme finira par terminer plus tard.) La raison de cette impossibilité est d'ailleurs étonnamment bête une fois qu'on a fait le travail de formalisation pour rendre rigoureuse la théorie : en gros, si un algorithme existait qui puisse dire à coup sûr si un algorithme donné s'arrête, on pourrait faire un algorithme qui l'interroge et fait le contraire de ce qu'il a prédit, ce qui le met en défaut. (C'est ce qu'on appelle un argument diagonal de Cantor.)

  La calculabilité ne se contente pas, en fait, de définir des problèmes résolubles ou non résolubles algorithmiquement, et de le montrer : il y a des problèmes plus ou moins impossibles à résoudre, et l'étude des degrés d'impossibilité (par exemple les degrés de Turing dont je dirai un mot plus bas, et que je définirai précisément dans le volet technique de ce billet) est un sujet de recherche qui court depuis Turing, mais l'outil de base pour ne serait-ce que formuler ce genre de questions est la notion d'oracle que je vais chercher à introduire ici.

• La théorie de la complexité [algorithmique], cherche à être plus fine que la calculabilité : alors que la calculabilité donne aux algorithmes l'accès à des ressources (temps, mémoire) illimitées-mais-finies, la complexité s'intéresse à des problèmes résolubles par un algorithme, mais cherche à mesurer combien de temps ou de mémoire (ou parfois d'autres ressources) un algorithme devra utiliser, en fonction de la taille du problème qu'on leur pose, lorsque cette taille devient très grande. (Par exemple, combien d'étapes faut-il pour multiplier deux nombres de 100 chiffres ? de 1000 chiffres ? de 10 000 chiffres ? Avec l'algorithme qu'on apprend à l'école primaire, la réponse est en gros 10 000, 1 000 000 et 100 000 000 respectivement, parce qu'il faut multiplier chaque chiffre du multiplicande par chaque chiffre du multiplicateur avant d'ajouter tout ça : en complexité on appelle ça un algorithme quadratique. En fait, on peut faire beaucoup plus efficacement, et d'ailleurs au moins un algorithme de multiplication plus efficace sur les grands nombres que l'algorithme appris à l'école primaire peut vraiment servir à la main — enfin, pourrait servir à la main si on était dans un monde où nous n'avions pas un ordinateur en permanence avec nous.)

  La complexité est donc une discipline un peu plus applicable au monde réel que la calculabilité : alors que la calculabilité va nous donner des réponses du type vous ne pouvez pas résoudre ce problème avec un ordinateur, quel que soit le temps que vous soyez prêt à attendre ou oui vous pouvez, mais je n'ai aucune idée du temps nécessaire parce que ce n'est pas mon sujet, la complexité va chercher à voir plus précisément dans la deuxième catégorie entre des problèmes théoriquement-résolubles-mais-absolument-pas-en-pratique (un peu comme si vous cherchiez à multiplier à la main deux nombres de 1 000 000 000 000 chiffres… oui, en principe c'est possible) et des problèmes un peu plus abordables en pratique. (La complexité va aussi faire la différence entre différents types d'ordinateurs qui, pour la calculabilité sont équivalents, par exemple un ordinateur quantique permet plus de choses du point de vue de la complexité parce qu'il peut en quelque sorte mener plein de calculs en parallèle ; alors qu'en calculabilité il ne change rien du tout par rapport à un ordinateur classique.)

  Néanmoins, la complexité reste une discipline assez théorique parce qu'elle se penche sur le temps (ou la mémoire, ou une autre ressource) utilisés asymptotiquement : ici, asymptotiquement veut dire quand la taille de l'entrée de notre problème (i.e. l'instance précise) devient extrêmement grande (tend vers l'infini). C'est-à-dire que le but de la complexité n'est pas de savoir si vous allez prendre exactement tel ou tel temps pour multiplier deux grands entiers (disons) mais comment ce temps grandit quand les entiers deviennent très grands (est-ce que doubler la taille des nombres double le temps qu'il faut pour faire la multiplication ? plus ? moins ?). Tout simplement parce que c'est un peu plus abordable comme type de question (et que c'est déjà utile dans la pratique).

  La complexité définit toutes sortes de catégories de problèmes en fonction de la difficulté à les résoudre, mesurée sous la forme des ressources qu'on accepte d'allouer à un algorithme qui les résout. (Par exemple, de façon approximative, un problème est dit EXPTIME ou EXPSPACE s'il existe un algorithme qui le résout et dont le temps d'exécution ou respectivement la mémoire utilisée croît au plus exponentiellement dans la taille de la donnée ; on peut faire énormément de choses avec un temps ou une mémoire exponentielle, donc énormément de problèmes sont dans ces classes, qui ne sont pas d'un grand intérêt pratique, mais c'est quand même plus restrictif que les problèmes tout simplement calculables en ressource illimitées que j'ai évoqués plus haut.)

  Deux classes particulièrement importantes en calculabilité sont les classes P et NP. La classe P est très grossièrement celle des problèmes faciles (un peu plus précisément, ce sont ceux qui sont résolubles par un algorithme qui utilise un temps au plus polynomial dans la taille de l'entrée : linéaire, quadratique, cubique, quelque chose comme ça, mais exponentiel n'est pas permis) ; la classe NP est plus subtile : très grossièrement, ce sont les problèmes faciles à vérifier (mais pas forcément faciles à résoudre ; c'est-à-dire que si vous avez la réponse, la vérification qu'elle est correcte se fait essentiellement selon la classe P, mais par contre, si vous ne connaissez pas la réponse, il est possible qu'elle soit très difficile à trouver ; j'insiste sur le fait que mes explications sont très grossières et que je passe sur plein de subtilités théoriques).

  Un exemple de problème NP très simple à décrire est le suivant : je vous donne un tas de nombres (entiers positifs, disons) et un nombre-cible, et votre but est d'exprimer le nombre-cible comme somme de certains des nombres donnés. (C'est une variante très simple des « chiffres et les lettres » où on n'a le droit qu'à l'addition ! Ou bien imaginez que ce sont des pièces de monnaie dans un système monétaire bizarre, et vous voulez réussir à payer exactement un certain montant cible en ayant dans votre poche des pièces de certains montants donnés. Par exemple, si je vous donne les nombres 1, 3, 8, 17, 32, 51, 82, 127, 216, 329, 611, 956 et 1849, et que je vous demande de faire la somme 2146 avec, ce n'est pas évident d'y arriver sauf à tester énormément de combinaisons ; par contre, vérifier que 1 + 8 + 32 + 82 + 127 + 329 + 611 + 956 = 2146 est un calcul facile.)

  Parmi les classes que j'ai pas-vraiment-définies-mais-un-peu-évoquées, on a P ⊆ NP ⊆ EXPTIME, le symbole ‘⊆’ signifiant ici est inclus dans, c'est-à-dire que tout problème P (facile à résoudre) est en particulier NP (facile à vérifier), et que tout problème NP est lui-même, en particulier, EXPTIME (résoluble en temps exponentiel). (Ce dernier est à son tour inclus dans EXPSPACE mais peu importe.) On sait par ailleurs montrer qu'il existe des problèmes qui sont dans EXPTIME mais qui ne sont pas dans P (et on sait en décrire explicitement), autrement dit, des problèmes résolubles en temps exponentiels mais pas faciles pour autant (pas résolubles en temps polynomial) : ce n'est pas très surprenant, parce qu'une exponentielle grandit vraiment très vite, donc il n'est pas surprenant que certains problèmes puissent se résoudre en un temps exponentiel mais pas en un temps beaucoup plus limité, mais encore fallait-il le prouver (ce n'est pas très difficile, mais ce n'est pas complètement évident non plus). Bref, si voit P ⊆ NP ⊆ EXPTIME comme trois boîtes imbriquées, la plus à gauche est effectivement strictement plus petite que la plus à droite. Mais la question se pose de savoir comment est celle du milieu. En fait, on ne sait pas la situer ni par rapport à celle de gauche ni par rapport à celle de droite.

  Spécifiquement, une question centrale de la théorie de la complexité est de savoir si P=NP (en gros, est-ce que tout problème facile à vérifier est, en fait, facile à résoudre ?). On pense très fortement que la réponse est non (i.e., qu'il existe des problèmes qui sont dans NP et qui ne sont pas dans P ; on en a même plein de candidats, d'ailleurs celui que j'ai donné plus haut en est un), mais on ne sait pas le prouver (l'enjeu, ici, est de prouver rigoureusement qu'un problème est difficile au sens où il ne peut pas exister d'algorithme qui le résout facilement). Cette question P≟NP est même mise à prix à 1 000 000 $ (et attire régulièrement des « solutions » incorrectes de toutes parts).

  Pour en savoir plus sur la situation en complexité, cet article récent de vulgarisation (costaud !) dans le magazine Quanta, quoique long, n'est pas mauvais pour donner un aperçu, et expliquer un peu mieux que ce que je l'ai fait ce que c'est que cette histoire de P≟NP, ce qu'on sait dire à son sujet et quelle est la difficulté. Ce n'est pas vraiment mon propos ici d'en dire plus ici.

• La cryptographie (enfin, peut-être que je devrais plutôt dire cryptologie ici) est l'étude scientifique de la sécurité de l'information : il s'agit de développer des techniques de chiffrement (comment transformer un message en un chiffré qui ne puisse être déchiffré qu'en ayant accès à une clé) ou ayant trait à d'autres questions de sécurité de l'information (signature électronique, authenticité, non-répudiation, partage de secrets, ce genre de choses). Mais plus précisément, ici, au sein de la cryptographie, j'ai à l'esprit la cryptographie à clés publiques (voir ce billet récent pour une explication de ce que ça signifie ; ce n'est pas très important ici).

  Une différence importante entre la calculabilité/complexité et la cryptographie est qu'en cryptographie il y a un adversaire (par exemple, s'agissant d'un chiffrement, l'adversaire est un attaquant hypothétique qui essaie d'obtenir des informations sur le message sans avoir la clé de déchiffrement, ou peut-être sur la clé en ayant connaissance du message et du chiffré, ou des variantes autour de ces questions). En calculabilité ou en complexité on s'intéresse à la difficulté de problèmes parce que ça mettra une borne sur ce que nous pourrons faire. En cryptographie, on s'intéresse à la difficulté plutôt parce que ça peut représenter un travail pour l'attaquant (donc la difficulté est souhaitable !). Spécifiquement, on voudrait concevoir des méthodes de chiffrement qui soient faciles à utiliser (c'est-à-dire, peu coûteuses algorithmiquement) quand on connaît la clé, mais extrêmement difficiles à casser, c'est-à-dire pour l'attaquant qui ne connaît pas la clé, et si possible, on voudrait prouver cette difficulté, ou au moins avoir des raisons un peu plus tangibles que je ne sais pas faire, donc c'est sans doute compliqué.

Bref, dans ces trois domaines (et il y en a sans doute d'autres dont j'ignore tout ou qui ne me viennent pas à l'esprit), pour des raisons un peu différentes et avec des notions de problème et de difficulté différentes, on peut chercher à montrer qu'un certain problème est difficile (voire, s'agissant de la calculabilité, impossible, mais je vais ranger ça sous l'étiquette vague difficile), ou étudier sa difficulté.

Bon, mais comment montre-t-on qu'un problème est difficile ?

[Lire la suite…]

[Lire la suite…]

❦

[Lire la suite…]

Métamotivations : [bon, sérieusement, je ne sais pas ce que sont des métamotivations, mais je trouve ce mot trop rigolo pour ne pas l'écrire]

J'ai commencé il y a quelques semaines à écrire une entrée de ce blog (je vais dire dans un instant à quel sujet, mais pour l'instant ce n'est pas important), et il est arrivé ce qui m'arrive trop souvent : je pars plein d'enthousiasme en me disant que je vais réussir à condenser à sa substantifique moëlle un sujet fort copieux, en même temps que le vulgariser, je me mets à taper, taper, taper, la condensation espérée n'a pas vraiment lieu, au contraire, je me rends compte qu'il faut que je parle de ceci, puis de cela, le texte que j'écris devient de plus en plus indigeste, et, pire, alors que je partais tout content de me dire que l'effort d'exposition me permettra d'y voir plus clair sur le sujet dont je parle, plus je l'écris plus je commence à en avoir marre de l'écrire, donc plus je traîne à m'y mettre, et en plus quand je m'y mets je mets tellement de temps à relire ce que j'ai déjà écrit que les progrès initialement rapides deviennent de plus en plus lent, et cette lente agonie ne prend fin que quand je décide de bouger le billet en cours d'écriture dans un fichier d'entrées inachevées qui prend de plus en plus la forme d'un cimetière, parce que sinon il bloque l'écriture de toute nouvelle entrée.

(Oui, mes phrases sont trop longues. Je sais.)

Que faire quand ce genre de choses se produit ? (C'est fréquent, et j'ai déjà dû en parler plein de fois.) Je n'ai toujours pas trouvé de réponse satisfaisante. Je peux jeter l'éponge et publier l'entrée dans son état inachevé, mais c'est un peu renoncer à toute possibilité de l'améliorer ultérieurement, ce qui me déplaît (il m'arrive bien sûr de modifier des entrées déjà publiées, mais c'est pour ajouter des petites précisions mineures : personne ne va tout relire pour ça). Je peux publier les parties qui sont à peu près présentables (ces entrées fort longues se découpant en parties et sous-parties, je peux publier, disons, le premier chapitre), mais je n'aime pas beaucoup non plus parce que je risque de vouloir quand même y faire des additions ultérieures, et aussi parce que ça rompt ma promesse implicite d'essayer autant que raisonnablement possible d'écrire des entrées indépendantes sur ce blog. (Promesse qui me semble nécessaire si je veux qu'on puisse lire l'entrée #2698 de ce blog sans avoir lu les 2697 qui ont précédé, ce que sans doute personne n'a fait, je ne suis même pas sûr de l'avoir fait moi-même.) Bon, je suis de mauvaise foi, je peux bien dire je suppose qu'on a lu <telle entrée passée>, d'ailleurs il a dû m'arriver quelques fois de le faire, mais si la partie 2 met des années à arriver, personne ne la lira parce que tout le monde aura oublié la partie 1 et que personne n'aura envie de la relire. Même vis-à-vis de moi-même, quand je publie quelque chose sur ce blog, qui est un peu l'espace de swap de mon cerveau, c'est pour me décharger mentalement en me disant que je peux l'oublier puisque je pourrai toujours me relire plus tard (et du coup je ne le fais généralement pas, justement), et ça ne marche plus vraiment si je continue à vouloir donner une suite.

Mais faute d'avoir décidé, je me dis que je peux au moins publier en avance (quitte à la recopier quand même plus tard, ce n'est pas long ce ne sera pas grave) la partie motivations de l'entrée en question. Ne serait-ce que parce que les motivations, c'est un peu comme les remerciements de thèse, c'est la seule chose que doit lire la majorité des gens ; et ici, ils ont, je crois, un intérêt autonome parce que c'est beaucoup moins technique que ce qui vient (enfin, est censé venir) après ; et je ne crois pas avoir envie de les changer plus tard, et elles ont toute leur place ici puisque, finalement, je suis en train de parler de ma motivation.

(En plus, là, j'ai été aspiré par d'autres préoccupations qui m'ont bouffé plein de temps, donc l'écriture de ce billet-ci a elle-même traîné en longueur !)

Voici donc les motivations de ce billet partiellement écrit :

❦

Motivations et introduction générales

Il y a un certain temps, j'avais publié un billet fort mal écrit sur la logique intuitionniste et les mathématiques constructives, pour essayer d'expliquer de quoi il s'agit. J'aimerais réessayer d'en parler, mais en prenant une approche différente : dans le billet précédent (que je ne vais pas supposer que le lecteur a lu, même si ça peut aider de l'avoir au moins parcouru), j'avais mis l'accent sur les règles de la logique intuitionniste (la syntaxe, si on veut), maintenant je voudrais mettre l'accent sur les « mondes » (j'utilise ce terme de façon délibérément vague et informelle, je vais revenir là-dessus) dans lesquels la logique intuitionniste s'applique — la sémantique si on veut. Je pense en effet qu'on comprend beaucoup mieux l'intérêt de cette logique (au-delà de se dire tiens, je vais m'interdire d'appliquer le tiers exclu et voyons ce qui se passe) si on commence par avoir à l'esprit quelques situations où elle s'applique.

Comme on n'a pas besoin de savoir d'avance ce qu'est la logique intuitionniste pour comprendre ces « mondes », cela peut aider, justement, à l'approcher : de l'« intérieur » ils sont régis par la logique intuitionniste, mais de l'« extérieur » ce sont des objets mathématiques classiques (d'ailleurs manipulés régulièrement par des mathématiciens qui n'ont aucune appétence particulière pour la logique, comme les faisceaux en topologie ou géométrie algébrique). Ils forment donc un pont par lequel un mathématicien classique peut comprendre ou visualiser les objets intuitionnistes.

Mais par ailleurs, ces « mondes » sont intéressants, au-delà de l'aspect logique, pour la source de contre-exemples qu'ils fournissent : un monde dans lequel toutes les fonctions ℝ→ℝ sont continues, par exemple, ou dans lequel toutes les fonctions ℕ→ℕ sont calculables, ou dans lequel le théorème des valeurs intermédiaires ne peut pas être affirmé, ou dans lequel on ne peut pas affirmer qu'une suite croissante bornée de réels converge, cela mérite qu'on s'y intéresse même si on n'a aucun intérêt particulier pour la logique : je pense, et c'est en fait ma principale motivation pour m'y intéresser, que cela permet une meilleure compréhension des objets basiques que sont les entiers naturels, les réels, les fonctions entre eux, de comment ils sont construits et de ce qui permet de démontrer ceci ou cela. (Et en comparaison au degré de technicité nécessaire pour construire des mondes dans lesquels l'axiome du choix ne vaut pas, les constructions ici sont raisonnablement peu élaborées bien que plus dépaysantes, ce qui augmente leur intérêt pédagogique.)

J'utilise ci-dessus le mot monde, délibérément vague : disons un mot à ce sujet. En logique classique, le terme correct pour désigner un monde dans lequel vaut une théorie est celui de modèle (pour montrer qu'une théorie T n'implique pas un énoncé φ, on va construire un modèle de T ne vérifiant pas φ). Il y a plusieurs notions de modèle permettant de donner une sémantique à la logique intuitionniste : modèles de Kripke, par exemple, modèles à valeurs dans une algèbre de Heyting, ou encore topoï. Les « mondes » dont je veux parler sont, en l'occurrence, des topoï, mais je ne compte pas expliquer ce qu'est un topos en général, uniquement en donner des exemples. Pourquoi ? Pas que ce soit immensément compliqué si on connaît un peu de théorie des catégories (encore qu'il y a la subtilité qu'il y a deux sens, apparentés mais distincts, du mot topos : topos de Grothendieck [dans ce cas le pluriel est un topos, des topos] ou topoï élémentaires [dans ce cas le pluriel est un topos, des topoï], ces derniers étant plus généraux que ces premiers), mais je pense que la notion de topos ne peut être correctement comprise qu'en ayant au préalable un stock d'exemples, et il s'agit donc de commencer par là. D'autre part, je ne prétends pas énoncer de résultat de complétude. Disons un mot à ce sujet.

[Le paragraphe suivant est une digression par rapport à mon propos général. On peut le sauter sans perdre le fil.]

Quand on a une théorie logique (ce mot étant pris ici, informellement, dans un sens excessivement vague et général), lui définir une sémantique, c'est définir un tas de mondes possibles (même remarque) qui valident certains énoncés (i.e., certaines choses sont vraies dans tel ou tel de ces mondes), et la moindre des choses est que la sémantique donne raison à la théorie, c'est la partie qu'on appelle la soundness en anglais, et je ne sais pas quel mot utiliser en français (cohérence ?) : dire que la sémantique Muf est sound (sensée ?) pour la théorie Truc, c'est dire que tout ce que la théorie Truc permet de démontrer sera vérifié dans chacun des « mondes » Muf. En général, ce n'est pas difficile, c'est même souvent une évidence tellement évidente qu'on ne se fatigue pas à le dire. (Mais remarquez que les « mondes » dont je veux parler, s'ils sont sound pour la logique intuitionniste, ne le sont pas pour la logique classique, et c'est bien pour ça qu'il y aura des théorèmes des mathématiques classiques qui ne seront pas valables dans certains d'entre eux, du genre le théorème des valeurs intermédiaires.) Mais l'autre chose qu'on veut souvent (mais pas forcément) avec une sémantique, c'est qu'elle soit complète, et là ça veut dire la réciproque : dire que la sémantique Muf est complète pour la théorie Truc, c'est dire que tout ce qui est vérifié dans chacun des « mondes » Muf pourra être démontré dans la théorie Truc. En logique classique du premier ordre avec la sémantique fournie par la notion habituelle de modèle, si vous savez ce que c'est, on a effectivement complétude, et le résultat en question s'appelle le théorème de complétude de Gödel (qui affirme que, dans le contexte du calcul des prédicats du premier ordre en logique classique, si φ est vrai dans tout modèle d'une théorie T alors φ est démontrable à partir de T). La question de la mesure dans laquelle les topoï définissent une sémantique complète par rapport à la logique intuitionniste dépend crucialement de ce qu'on appelle exactement la logique intuitionniste (le problème n'étant pas les règles de déduction mais ce sur quoi on s'autorise à quantifier), et essayer d'expliquer ça, sur quoi je n'ai d'ailleurs pas les idées aussi claires que je voudrais, m'entraînerait à parler de logique d'ordre supérieur, de théorie des types et de choses dont je ne veux pas parler. Donc je vais faire complètement l'impasse sur tout ce qui concerne la complétude, et du coup il n'est pas vraiment pertinent que j'explique ce qu'est un topos, ce qui m'importe ce sont les exemples que je veux exposer et le fait qu'ils soient sound.

[Fin de la digression.]

Ce qui est intéressant à comprendre, aussi, c'est le rapport entre le point de vue « interne » et le point de vue « externe » sur les « mondes » en question : on peut soit se plonger dans un de ces « mondes », le regarder avec les lunettes « internes », auquel cas on a affaire à des ensembles dans un monde de maths intuitionnistes, ou au contraire le regarder « de l'extérieur », auquel cas on a affaire à des objets un peu plus compliqués (faisceaux, par exemple, en tout cas des objets d'une catégorie et c'est cette dernière qu'on appelle topos) mais dans un monde plus familier puisque la logique classique s'applique. Les deux points de vue se traduisent l'un l'autre (du moins, tout énoncé « interne » peut se réécrire de façon « externe », la réciproque n'est pas forcément vraie), ils s'éclairent et se complètent. Ce que je voudrais faire c'est expliquer, sur quelques exemples, comment marche cet aller-retour.

[Lire la suite…]

Mon poussinet s'est acheté une nouvelle voiture. Ou plus exactement, a remplacé un joujou, rouge de chez Honda, thermique et bruyant, par un autre joujou, blanc de chez Tesla, électrique et beaucoup moins bruyant et beaucoup plus Internet of Shit ; mais ce n'est pas mon propos ici d'en parler : le point de départ de ce que je veux dire ici, c'est que le nouveau joujou est assez long et large, et que la descente du parking de notre immeuble est compliquée.

Nous avons trois véhicules et trois places de parking (une achetée avec l'appartement et deux louées à des voisins). Ma moto, bizarrement, ne pose aucun problème pour monter et descendre au parking. Pour la Tuture préférée (qui fait censément 1.74m de large, et 4.15m de long dont 2.51m entre les essieux), le poussinet s'en sort bien (le plus souvent sans marche arrière), mais moi je n'ose pas trop essayer, et c'est d'ailleurs mon principal obstacle à circuler en voiture. Et pour le nouveau joujou (qui fait censément 1.85m de large, et 4.69m de long dont 2.83m entre les essieux), c'est beaucoup plus compliqué : à ce stade, à chaque fois que nous voulons entrer ou sortir du parking, je descends de la voiture, je passe devant, et j'indique au poussinet par des signes de main la distance à gauche et à droite (certes, le joujou a plein de capteurs, mais ils sont essentiellement inutiles dans ces circonstances, parce qu'ils passent juste leur temps à faire bip, et ne détectent pas forcément la « bonne » distance) : il arrive à sortir en une seule fois, mais pour rentrer dans le parking il faut trois ou quatre marches arrière (et la question de pourquoi ce n'est pas symétrique est une de celles que je veux discuter ici).

Pourtant, la descente du parking n'est pas si étroite : elle fait 2.67m de large au point le plus resserré que j'aie mesuré ; cette largeur est un peu stupidement grignotée par le fait qu'il y a des garde-corps (je ne sais pas comment les appeler : une sorte de marche ou de micro trottoirs de part et d'autre de la descente, au niveau du sol, large d'environ 15cm et haute d'environ autant), qui réduit l'espace disponible au niveau des roues à 2.38m au point le plus étroit. Mais bien sûr, la descente est courbe : entre la porte côté rue et la base de la rampe, il y a un changement de cap de 90° (on entre perpendiculairement à la rue Simonet, et on finit parallèlement à elle).

Géométriquement, si j'en crois les plans d'architecte de l'immeuble que j'ai récupérés je ne sais plus comment, la forme est très simple (cf. figure ci-contre) : prenez un quart de cercle de rayon 6.50m et un autre de rayon 5.50m dont les centres sont décalés de 1.75m selon chacun des axes du quart de cercle (donc à distance 1.75m×√2 ≈ 2.47m l'un de l'autre), le centre du petit cercle étant évidemment plus éloigné des arcs eux-mêmes que celui du grand cercle, et ensuite prolongez tangentiellement chacune des deux extrémités de chacun des deux arcs. (En notation SVG et en exprimant les distances en mètres : M 0.00 0.00 L 9.37 0.00 A 6.50 6.50 0 0 1 15.87 6.50 L 15.87 18.38 pour le bord extérieur et M 0.00 2.75 L 7.62 2.75 A 5.50 5.50 0 0 1 13.12 8.25 L 13.12 18.38 pour le bord intérieur.) Ceci fait donc une rampe dont la largeur est de (6.50m−5.50m)+1.75m = 2.75m dans ses parties rectilignes, et de (6.50m−5.50m)+1.75m×√2 ≈ 3.47m dans sa partie courbe, à quoi il faut retirer environ 15cm de garde-corps de part et d'autre comme je l'ai expliqué ci-dessus. J'ai fait apparaître sur la figure des rectangles à l'échelle du joujou du poussinet, mais il n'est pas évident de le placer comme je viens de le montrer (cf. plus loin). L'épaisseur des traits sur la figure est de 30cm (le milieu du trait est au niveau du mur lui-même, le bord intérieur correspond à peu près au bord du garde-corps).

Bon, en plus, la rampe est bien sûr en pente (de 14.38% selon le plan d'architecte, l'hélice étant orientée à main gauche : sur le schéma ci-contre, la sortie côté rue est en bas de la figure, la base de la rampe côté parking est à gauche), mais je ne pense pas que ça joue énormément sur le problème géométrique que je vais évoquer. Par ailleurs, la construction de l'immeuble n'a pas respecté précisément les plans d'architecte et les arcs de cercle ont été approchés par des polygones, donc il y a trois ou quatre points anguleux sur le mur extérieur : je ne sais pas bien si ça joue dans l'explication de l'asymétrie ressentie entre montée et descente, je vais y revenir ; la largeur de la rampe, comme je l'ai dit plus haut, n'est, d'après mes mesures, pas tout à fait égale aux 2.75m contractuels de mur à mur, je l'ai déjà noté.

Mes lecteurs savent que j'aime faire des typologies, alors allons-y. Je peux distinguer trois niveaux au problème d'entrer ou sortir la voiture :

1. La question purement géométrique (entrer ou sortir la voiture, en supposant une connaissance parfaite de ses dimensions, sa position, la forme de la rampe, etc., donc toutes les distances impliquées), que je vais elle-même ci-dessous subdiviser en trois.
2. La complication supplémentaire que, assis à la place du conducteur, on voit mal ce qu'on fait, on évalue mal les distances, malgré les rétroviseurs et les diverses caméras de la Tesla, en tout cas, plus mal que quelqu'un qui se tient à distance et qui regarde la voiture de l'extérieur.
3. La complication supplémentaire qu'une voiture n'avance pas exactement comme on veut (je parle du point de vue de la traction : je mets la question du rayon de braquage sur le chapeau géométrique) : ceci ne concerne pas la Tesla, dont le moteur électrique permet d'avancer aussi lentement qu'on veut, presque millimètre par millimètre, aussi bien en montée qu'en descente, mais le problème se pose avec une voiture thermique si on ne veut pas vitrifier l'embrayage en patinant trop longtemps.

Je veux surtout parler ici du (A), même si (B) et (C) sont aussi problématiques en pratique. Maintenant, même si je le simplifie à outrance en traitant la voiture comme un simple rectangle et en ramenant tout le problème dans le plan, ce que je vais faire, le (A) se subdivise lui-même en trois niveaux de difficulté :

[Lire la suite…]

Je rassemble dans cette entrée quelques faits algorithmiques et informatiques qui sont généralement « bien connus » (et franchement assez basiques) mais souvent utiles, et qu'il est possiblement difficile de trouver rassemblés en un seul endroit. Le problème général est de tirer algorithmiquement des variables aléatoires selon différentes distributions, typiquement à partir d'un générateur aléatoire qui produit soit des bits aléatoires (indépendants et non biaisés) soit des variables aléatoires réelles (indépendantes) uniformément réparties sur [0;1]. Je parle d'algorithmique, mais ce n'est pas uniquement sur un ordinateur : ça peut être utile même dans la vie réelle, par exemple si on a une pièce avec laquelle on peut tirer à pile ou face et qu'on veut s'en servir pour jouer à un jeu qui réclame des dés à 6 faces, ou si on a des dés à 6 faces et qu'on veut jouer à un jeu d'aventure qui réclame des dés à 20 faces.

Comment tirer des nombres aléatoires en conditions adversariales ? Je commence par ce problème-ci qui n'a pas de rapport direct avec la suite, mais que je trouve quand même opportun de regrouper avec : Alice et Bob veulent jouer à pile ou face, ou plus généralement tirer un dé à n faces, mais ils n'ont pas de pièce ou de dé en lequel ils fassent tous les deux confiance. Par exemple, Alice a sa pièce fétiche que Bob soupçonne d'être truquée et symétriquement (ou peut-être même que chacun est persuadé de pouvoir tirer des nombres aléatoires dans sa tête mais ne fait évidemment pas confiance à l'autre). La solution est la suivante : chacun fait un tirage avec son propre moyen de son côté, sans connaître le résultat de l'autre, et on combine ensuite les résultats selon n'importe quelle opération (choisie à l'avance !) qui donne tous les n résultats possibles pour chaque valeur fixée d'une quelconque des entrées (un carré latin, par exemple une loi de groupe) ; par exemple, s'il s'agit de tirer à pile ou face, on peut décider (à l'avance !) que le résultat sera pile (0) si les deux pièces ont donné le même résultat et face (1) si elles ont donné un résultat différent ; s'il s'agit de dés à n faces donnant un résultat entre 0 et n−1, on fait la somme modulo n (c'est-à-dire qu'on fait la somme et qu'on soustrait n si elle vaut au moins n, pour se ramener à un résultat entre 0 et n−1). Bien sûr, il faut un protocole pratique pour faire en sorte que chacun fasse son tirage sans connaître le résultat de l'autre (sinon, s'il a moyen de tricher, il pourra adapter le résultat en conséquence) : physiquement, chacun peut faire son tirage en secret et écrire le résultat secrètement sur un papier placé dans une enveloppe scellée, qu'on ouvrira une fois les deux tirages effectués (en fait, il n'y a que le premier tirage qui a besoin d'être fait de la sorte) ; cryptographiquement, on procède à une mise en gage (typiquement au moyen d'une fonction de hachage, mais je ne veux pas entrer dans ces questions-là). On peut bien sûr généraliser à plus que deux joueurs (en faisant la somme modulo n de nombres tirés par chacun des participants). Le protocole garantit que le résultat sera un tirage uniforme honnête si l'un au moins des participants désire qu'il le soit (et a les moyens de réaliser un tirage honnête) : bien sûr, si aucun des participants ne le souhaite, c'est leur problème, donc on s'en fout. Même si on abandonne toute prétention à ce que les participants tirent leur valeur aléatoirement et qu'on s'imagine qu'ils la choisissent, tant qu'il s'agit d'un jeu à somme nulle, la stratégie optimale est bien de tirer au hasard (et encore une fois, s'ils veulent coopérer pour un autre résultat, tant qu'il n'y a pas d'autre partie impliquée, c'est leur problème, de même s'ils s'imaginent pouvoir faire mieux que le hasard en utilisant, par exemple, une prédiction psychologique).

Je ne sais plus où j'avais lu que ce protocole a été découvert (il l'a certainement été de nombreuses fois !) à la renaissance. Dans mon souvenir, le découvreur proposait même que, pour une question de la plus haute importance, on demande au pape de faire un des tirages en plus de tous les autres participants. Je ne sais d'ailleurs pas si ce protocole a un nom standard.

Comment tirer une variable de Bernoulli de paramètre p à partir de bits aléatoires ? Autrement dit, ici, on a fixé p, et on veut faire un tirage aléatoire qui renvoie oui avec probabilité p et non avec probabilité 1−p, et pour ça, on dispose simplement d'une pièce qui renvoie des bits aléatoires en tirant à pile (0) ou face (1), et on souhaite effectuer les tirages de façon économique. Par exemple, combien de tirages de pièce faut-il, en moyenne, pour générer un événement de probabilité 1/3 ? Il s'avère, en fait, que quel que soit p on peut s'en tirer avec deux (2) tirages en moyenne (je veux dire en espérance). Pour cela, on peut procéder ainsi : on effectue des tirages répétés et on interprète les bits aléatoires ainsi produits comme l'écriture binaire d'un nombre réel x uniformément réparti entre 0 et 1 : on compare x à 1−p en binaire, c'est-à-dire qu'on s'arrête dès qu'on dispose d'assez de bits pour pouvoir décider si x < 1−p ou x > 1−p (on peut considérer le cas x = 1−p comme s'il était impossible vu qu'il est de probabilité 0), en notant qu'on va avoir x < 1−p lorsque le k-ième bit tiré est 0 et que le k-ième bit de l'écriture binaire de p vaut 0, et x > 1−p lorsque le k-ième bit tiré est 1 et que le k-ième bit de p vaut 1 ; et si x < 1−p on renvoie non, sinon oui. Concrètement, donc, faire des tirages aléatoires jusqu'à ce que le k-ième bit tiré soit égal au k-ième bit de l'écriture de p, et alors s'arrêter et renvoyer ce bit-là. Il est clair que cet algorithme fonctionne, mais pour qu'il soit encore plus évident qu'il conduit à faire deux tirages en moyenne, on peut le reformuler de la façon encore plus élégante suivante (il suffit d'échanger les résultats 0 et 1 pour x, qui sont complètement symétriques, lorsque le bit correspondant de p vaut 0) : tirer des bits aléatoires jusqu'à tomber sur 1, et lorsque c'est le cas, s'arrêter et renvoyer le k-ième bit de p (où k est le nombre de bits aléatoires qui ont été tirés). Je trouve ça incroyablement élégant et astucieux (même si c'est très facile), et je ne sais pas d'où sort ce truc. (Cela revient encore à tirer une variable aléatoire k distribuée selon une loi géométrique d'espérance 1, comme je l'explique plus bas, c'est-à-dire valant k avec probabilité (½)^k+1, et renvoyer le (k+1)-ième bit b_k+1 de p, ce qui, quand on écrit p = ∑_k=0^+∞ b_k+1·(½)^k+1, est finalement assez évident.)

Comment tirer un entier aléatoire entre 0 et n−1 à partir de bits aléatoires ? (Ma première réaction en entendant ce problème a été de dire : considérer x uniforme dont l'écriture binaire est donnée par la suite des bits tirés, générer suffisamment de bits pour calculer la valeur de ⌊n·x⌋, où ⌊—⌋ désigne la partie entière, et renvoyer celle-ci. Ceci fonctionne, mais ce n'est pas le plus efficace. Un autre algorithme avec rejet consiste à générer r := ⌈log(n)/log(2)⌉ bits, qui, lus en binaire, donnent un entier aléatoire c entre 0 et 2^r−1, renvoyer c s'il est <n, et sinon tout recommencer. Mais ce n'est pas très efficace non plus, quoique dans des cas un peu différents.) Je décris ce problème plus en détails dans ce fil Twitter, mais donnons juste l'algorithme : on utilise deux variables internes à l'algorithme, notées v et c, qu'on initialise par v←1 et c←0 (il s'agit d'un réservoir d'entropie, et la garantie est que c est aléatoire uniformément réparti entre 0 et v−1) ; puis on effectue une boucle : à chaque étape, on génère un bit aléatoire b (valant 0 ou 1 avec probabilité ½ pour chacun, et indépendant de tous les autres, donc) et on remplace v ← 2v et c ← 2c+b ; puis on compare v avec n et c avec n : si v<n (ce qui implique forcément c<n) on continue simplement la boucle (il n'y a pas assez d'entropie) ; si v≥n et c<n, on termine l'algorithme en renvoyant la valeur c ; enfin, si c≥n, on effectue v ← v−n et c ← c−n et on continue la boucle. Le calcul du nombre moyen de tirages effectués est fastidieux (voir cette référence citée dans le fil Twitter référencée ci-dessus), mais c'est optimal.

L'algorithme que je viens de décrire s'adapte assez bien pour tirer un entier uniforme entre 0 et n−1 à partir d'une source de entiers uniformes entre 0 et m−1 (le cas que je viens de décrire est le cas m=2), autrement dit : comment fabriquer un dé à n faces à partir d'un dé à m faces ? Je n'ai pas vraiment envie de réfléchir à si c'est optimal (mise à jour : on l'a fait pour moi), mais c'est en tout cas assez élégant : on utilise deux variables internes à l'algorithme, notées v et c, qu'on initialise par v←1 et c←0 ; puis on effectue une boucle : à chaque étape, on génère un tirage aléatoire b entre 0 et m−1 à partir de la source dont on dispose et on remplace v ← m·v et c ← m·c+b ; puis on effectue la division euclidienne de v et de c par n : si les deux quotients calculés sont différents (⌊c/n⌋ < ⌊v/n⌋), on termine l'algorithme en renvoyant le reste c%n := c − n·⌊c/n⌋ de la division de c par n, tandis que si les deux quotients sont égaux, on remplace chacun par son reste, c'est-à-dire v ← v%n et c ← c%n et on continue la boucle.

Introduisons maintenant aussi des tirages continus.

[Lire la suite…]

Je parle souvent de maths un peu compliquées sur ce blog, alors pour changer (et pour me changer les idées) je vais parler de choses un peu plus simples : de géométrie plane, et plus précisément de points et de droites. Je voudrais évoquer un petit projet que j'ai — qui, comme beaucoup de projets que j'ai, risque de n'aboutir nulle part — et qui ferait intervenir les maths (pour le sujet de fond), la mécanique classique (pour l'animation), l'informatique (pour le calcul) et un côté artistique (parce que le but serait surtout de faire quelque chose de joli à regarder). Enfin, ça c'était l'idée initiale, sauf que, comme d'habitude quand j'écris une entrée dans ce blog (mais bon, c'est un peu l'idée, aussi), je suis tombé dans un terrier de lapin, je me suis perdu dans les méandres de ce que je dois raconter, et au final ça ne ressemble à rien.

J'ai expliqué par le passé (et souvent fait référence depuis au fait) que j'étais fasciné par la symétrie et par les objets mathématiques très symétriques. En même temps, il ne faut pas oublier que je suis géomètre, et au sein de la géométrie, j'aime beaucoup ce qui en est la forme la plus épurée, la géométrie projective (plane, disons) où il n'est question que de points et de droites. (Je faisais d'ailleurs souvent remarquer à mes élèves agrégatifs quand ils faisaient des développements sur les constructions à la règle et au compas qu'il pouvait être bienvenu de consacrer une certaine attention aux constructions à la règle seule, qui sont les constructions « pures » de la géométrie projective, où on ne peut que relier deux points à la règle et intersecter deux droites.)

À la croisée de ces deux intérêts, il y a la notion de configuration de points et de droites (dans le plan) : une configuration est simplement un ensemble fini de points et un ensemble fini de droites[#]. Les figures ci-contre à droite sont des exemples de configurations de neuf points et neuf droites telles que par chaque point de la configuration passent exactement trois droites et chaque droite passe par exactement trois points. Bien sûr, on peut voir sur cette figure d'autres points, à l'intersection de deux droites de la configuration, mais ceux qui sont des points de la configuration sont uniquement ceux que j'ai marqués en rouge, pas n'importe quel point que vous pouvez voir comme intersection de deux droites (et symétriquement, on peut considérer d'autres droites en reliant deux des points, mais ceux qui sont des droites de la configuration sont celles qui ont été tracées, pas n'importe quelle droite que vous pouvez faire apparaître en reliant deux points).

[#] Pour éviter de considérer des objets sans intérêt, on demandera que chaque point de la configuration soit situé sur au moins une des droites de la configuration (sinon c'est un point isolé qui ne sert à rien), voire deux (sinon c'est un point isolé sur sa droite), voire trois (sinon c'est juste le marqueur d'une intersection), et symétriquement, que chaque droite passe par au moins un des points, voire deux, voire trois. De toute façon, comme je le dis plus bas, on demande en général que la configuration soit régulière, c'est-à-dire que par chaque point passe le même nombre q de droites et que chaque droite passe par le même nombre k de points.

Je ne veux pas parler longuement des configurations de points et de droites, parce que ce n'est pas tellement mon sujet, mais disons-en quand même quelques mots. (Enfin, quelques mots qui, comme d'habitude, se sont multipliés en quelques pages.) Ceux qui veulent juste savoir ce qu'est mon projet peuvent sauter directement plus bas.

Généralement on s'intéresse aux configurations possédant un certain degré de régularité, au moins numérique, c'est-à-dire que par chaque point passe le même nombre de droites et chaque droite passe par le même nombre de points (voire que ces deux nombres sont égaux, ce qui est le cas sur mes exemples), voire un certain degré de symétrie. Spécifiquement, on dit qu'une configuration est de type (p_q,n_k), où p,q,n,k sont quatre entiers ≥2 (ou en fait plutôt ≥3), lorsqu'elle comporte p points et n droites, que par chaque point passent q droites et que chaque droite passe par k points (ces informations sont donc redondantes et on a pq = nk, ce qui se voit en comptant le nombre total d'incidences d'un point et d'une droite) ; la plupart des textes sur les configurations de points et droites utilisent le mot configuration pour désigner spécifiquement les configurations régulières, c'est-à-dire celles qui sont de type (p_q,n_k) pour certains paramètres p,q,n,k≥3. Lorsque de plus p=n (ou ce qui revient au même, q=k), on dit simplement qu'on a affaire à une configuration de type (n_k), c'est-à-dire n points, n droites, chaque droite passant par k points et par chaque point passant k droites : mes figures à droite sont donc des configurations de type (9₃).

Pour être plus précis, je dois distinguer la notion de configuration abstraite et de réalisation géométrique de la configuration : deux configurations géométriques ont la même configuration abstraite lorsqu'on peut étiqueter (i.e., donner des noms, ce que je n'ai volontairement pas fait sur les figures ci-contre) aux points et aux droites des deux configurations de manière à ce qu'elles se correspondent avec les mêmes incidences, c'est-à-dire que si la droite nommée ℓ passe par le point nommé P sur une figure, ça doit aussi être le cas sur l'autre. (Cela pourrait être le cas parce qu'on a déplacé juste un petit peu les points et les droites d'une des figures pour former l'autre, mais ce n'est pas forcément le cas qu'on puisse passer continûment de l'une à l'autre.) Une configuration abstraite est donc la manière de demander quelles droites doivent passer par quels points (par exemple, un triangle abstrait consisterait à dire trois points A,B,C et trois droites a,b,c de manière que a passe par B et C, que b passe par C et A et que c passe par A et B ; et une réalisation géométrique de cette configuration abstraite est simplement un triangle).

Bref, une configuration abstraite est simplement la donnée de deux ensembles finis d'objets, arbitrairement appelés points et droites, et d'une relation d'incidence entre points et droites (on peut dire qu'une droite [abstraite] passe par un point [abstrait] lorsque cette relation est satisfaite) ; si on veut, c'est un graphe bipartite ; et on demandera en outre qu'il existe au plus une droite incidente avec deux points distincts donnés et au plus un point incident avec deux droites distinctes données (ceci correspond au fait que, dans le plan, deux points distincts définissent une droite et que deux droites distinctes se coupent en au plus un point). Une réalisation géométrique d'une configuration abstraite est une façon de trouver des points distincts et des droites distincts dans le plan (encore qu'il faut préciser quel plan : plan euclidien, ou ce qui revient au même, affine réel, plan projectif réel, ou des plans affines ou projectifs différents), en correspondance avec la configuration abstraite à réaliser, de façon qu'une droite passe par un point exactement quand l'incidence a lieu dans la configuration abstraite.

Il y a donc plusieurs questions qui se posent naturellement : quelles sont les configurations abstraites possibles ? (peut-on, par exemple, les dénombrer ? les classifier ? a priori non, cela reviendrait en gros à classifier les graphes bipartites, ce qui n'a guère de sens, il y a juste trop de possibilités, mais on peut s'intéresser à celles qui vérifient certaines contraintes, par exemple ont beaucoup de symétries ; ou on peut simplement en chercher qui sont particulièrement remarquables et intéressantes, et je vais donner quelques exemples ci-dessous) ; parmi elles, quelles sont celles qui sont réalisables ? (peut-on tester ce fait efficacement sur tel ou tel corps ? je dois mentionner que cela revient en fait à tester si un système d'équations polynomiales tout à fait général a des solutions, ce qui est décidable mais très coûteux sur les complexes, décidable mais extraordinairement coûteux sur les réels, et possiblement indécidable sur les rationnels) ; puis on peut encore se poser des questions sur les réalisations d'une configuration donnée, par exemple peut-on passer continûment de l'une à l'autre ? Malheureusement, je doute qu'on puisse dire quoi que ce soit de vraiment intelligent sur aucune de ces questions à ce niveau de généralité (il faut se contenter de résultats du type : pour tout n≥9, il existe au moins une configuration géométrique de type (n₃) dans le plan euclidien).

Il n'est pas toujours évident, visuellement, de reconnaître quand une configuration abstraite est la même qu'une autre. Par exemple, les trois configurations (9₃) ci-dessus à droite sont distinctes non seulement géométriquement (c'est évident) mais même abstraitement ; et celle qui est ci-contre à gauche, est une réalisation géométrique (différente) d'une des trois configurations abstraites en question, et ce n'est pas forcément immédiat de reconnaître laquelle ! Le lecteur saura-t-il reconnaître laquelle, et saura-t-il montrer que les trois de départ sont bien distinctes ? Pour ça, on peut suggérer l'indication consistant à relier (d'une couleur différente, disons) les paires de points qui ne sont pas situées sur une même droite de la configuration, et regarder le graphe ainsi formé (par exemple, y a-t-il des triplets de points dont aucune paire n'est située sur une droite de la figure ? combien de tels « anti-triangles » y a-t-il ?).

Plus difficile, on peut chercher à montrer qu'il n'y a que trois configurations (9₃) abstraites possibles, et que je les ai donc toutes les trois réalisées géométriquement. (La plus en haut, (9₃)①, s'appelle la configuration de Pappus, parce qu'elle est celle qui intervient dans l'énoncé du théorème de Pappus.) Il y a une unique configuration (8₃) abstraite possible, la configuration de Möbius-Kantor, mais elle n'est pas réalisable géométriquement dans le plan réel même si elle l'est sur les complexes (on peut par exemple l'obtenir en retirant un point et les droites qui vont avec à une autre, de type (9₄,12₃) celle-là, la configuration de Hesse, elle aussi non réalisable sur les réels mais réalisable sur les complexes, qui est celle des neuf points d'inflection d'une courbe cubique lisse). Il y a aussi une unique configuration (7₃) abstraite possible, la configuration de Fano, mais celle-ci n'est réalisable que sur un corps de caractéristique 2.

[Lire la suite…]

Je continue dans ce billet de blog une série sur l'épidémiologie mathématique que j'avais commencée avec cette entrée sur le modèle SIR classique, celle-ci sur une variante de SIR où le rétablissement se fait en temps constant, accessoirement celle-ci sur la différence entre seuil d'immunité collective et taux d'attaque, et plus indirectement celle-ci sur des modèles d'hétérogénéité basés sur les graphes aléatoires ; je ne présuppose pas la lecture des billets en question, même si celle du premier a un intérêt, mais je vais en résumer rapidement le contenu.

Mon but aujourd'hui est d'expliquer un peu en détails, mathématiquement, comment on peut modifier le modèle SIR classique (dont le vais rappeler les grandes lignes dans un instant), lequel décrit l'évolution d'une épidémie dans laquelle tout le monde est également susceptible à l'infection, pour le cas d'une susceptibilité hétérogène, c'est-à-dire que certains individus sont plus ou moins susceptibles d'être infectés (= ont plus ou moins de chances d'être infectés dans des circonstances identiques), et on va voir que ces hétérogénéités de susceptibilité ont un impact important. (Je ne me prononce pas sur la cause de ces différences de susceptibilité : elles pourraient être dues à des différences biologiques — certaines personnes s'infectent plus facilement que d'autres — ou sociales — certaines personnes sont plus fréquemment exposées à des conditions infectieuses. Néanmoins, comme le modèle que je vais développer ici suppose que la variation de susceptibilité n'est pas corrélée à une variation d'infectiosité, c'est-à-dire que les personnes plus susceptibles ne sont pas spécialement plus infectieuses — si c'était le cas l'effet que je décris ici serait encore plus accentué — il vaut peut-être mieux imaginer le cas d'une origine biologique, parce qu'une hétérogénéité sociale a plus de chances d'être symétrique.)

Ce qui est assez surprenant, c'est que cette idée, qui peut paraître compliquée à traiter, complique en fait extrêmement peu le modèle SIR, et qu'on peut trouver des réponses exactes à essentiellement les mêmes questions que pour SIR classique (du genre quel est le nombre maximal d'infectés ?) dans ce cadre plus complexe, donnée la distribution (initiale) de susceptibilité dans la population. En général les réponses feront intervenir la transformée de Laplace de la distribution de susceptibilité (je vais expliquer ce que c'est plus bas), mais dans un cas particulier assez naturel (celui d'une distribution Γ, par exemple la distribution exponentielle), on peut tout traiter complètement.

[Un résumé de ce post de blog est contenu dans ce fil Twitter (17 tweets ; ici sur ThreadReaderApp), pour ceux qui préfèrent ce format ou qui veulent surtout les points importants (noter que tweet 11/17 il y a une typo, il faut lire φ′(0)=−1 et pas φ′(0)=1). ※ Une version anglaise (un petit peu plus longue) est contenu dans ce fil Twitter (25 tweets ; ici sur ThreadReaderApp).]

Ajout (2021-11-06) : Comme je commence à avoir écrit pas mal de choses au sujet d'épidémiologie sur Twitter, voici un méta-fil (ici sur ThreadReaderApp) rassemblant les plus importants fils que j'ai pondus.

❦

Je commence par rappeler les grandes lignes du modèle SIR classique.

Le modèle SIR classique, donc, étudie l'évolution d'une épidémie dans une population en distinguant trois classes d'individus : les Susceptibles, les Infectieux (qui dans ce modèle sont les mêmes que les infectés) et les Rétablis (qui sont immuns — ou, en fait, morts). Parmi les nombreuses hypothèses simplificatrices faites par ce modèle, il y a les suivantes (j'en oublie certainement) : l'immunité acquise par l'infection est parfaite et permanente, les individus sont infectieux dès qu'ils sont infectés, et ils vont donc soit rester dans l'état S, soit passer succesivement par les étapes S,I,R ; la population est homogène, c'est-à-dire que tous les individus sont également susceptibles et également infectieux une fois infectés, ils ont les mêmes probabilités de se faire infecter, la taille de la population est constante, et elle est assez grande pour être traitée de façon continue déterministe, et les contacts obéissent à une hypothèse de mélange parfait (au sens où tous les contacts sont également plausibles) ; le comportement de la population est constant dans le temps et notamment indépendant de l'évolution de l'épidémie ; les contaminations et le rétablissement obéissent à une cinétique du premier ordre I+S → I+I et I → R respectivement, avec des constantes β (d'infectiosité) et γ (de rétablissement) respectivement, c'est-à-dire le nombre de nouveau infectés par unité de temps est simplement proportionnel au produit du nombre d'infectieux par le nombre de susceptibles, et que le nombre de nouvellement rétablis est simplement proportionnel au nombre d'infectieux.

Bref, si on note s,i,r (quantités réelles entre 0 et 1, fonctions du temps) les proportions de la population formées d'individus susceptibles, infectieux et rétablis respectivement, alors les nouvelles infections par unités de temps se représentent par le terme β·i·s, et les rétablissements par γ·i, du coup le modèle SIR est décrit par le système d'équations différentielles ordinaires (autonomes) du premier ordre suivant :

• ds/dt = −β·i·s
• di/dt = β·i·s − γ·i
• dr/dt = γ·i
• (s+i+r=1)

où on impose en outre généralement les conditions initiales telles que s(−∞)=1, i(−∞)=0 et r(−∞)=0 (je parle bien sûr des limites en −∞), avec i croissant exponentiellement pour t assez proche de −∞ (cf. ci-dessous). La constante β d'infectiosité représente le nombre moyen de personnes qu'une personne infectieuse donnée infecte par unité de temps dans une population entièrement susceptible, tandis que la constante γ de rétablissement représente la proportion moyenne d'infectés qui se rétablissent par unité de temps (donc l'inverse du temps moyen de rétablissement, le temps de rétablissement suivant en fait une loi exponentielle). Notons que β peut aussi, symétriquement, se comprendre comme une constante de susceptibilité, c'est-à-dire comme le nombre moyen de personnes par lesquelles une personne susceptible donnée sera infectée par unité de temps dans une population entièrement infectieuse : c'est la raison pour laquelle je parlerai tantôt de β comme représentant une infectiosité et tantôt une susceptibilité (et comme ici on veut modéliser des variations de susceptibilité, c'est plutôt le deuxième qui va être mis en lumière).

Rappelons quelques uns des points saillants de ce modèle concernant le début, le pic et la fin de l'épidémie, résumé que je recopie de ce billet (plus exactement, comme je viens de le dire, on s'intéresse aux solutions pour lesquelles s→1 quand t→−∞) ; on notera κ := β/γ le nombre de reproduction, que je suppose >1 :

• tant que s reste très proche de 1 (si on veut, t→−∞), les proportions i et r croissent comme des exponentielles de pente logarithmique β−γ = β·((κ−1)/κ), avec un rapport 1/(κ−1) entre les deux, autrement dit comme i = c·exp((β−γ)·t) = c·exp(β·((κ−1)/κ)·t) et r = c·(γ/(β−γ))·exp((β−γ)·t) = c·(1/(κ−1))·exp(β·((κ−1)/κ)·t) (ergotage : dans l'entrée sur le sujet, j'avais mis un −1 aux exponentielles pour r, parce que je voulais partir de r=0, mais je me rends compte maintenant qu'il est plus logique de partir d'une solution où i/r tend vers une constante en −∞, cette constante étant κ−1) ;
• au moment du pic épidémique (maximum de la proportion i d'infectieux), on a s = 1/κ et i = (κ−log(κ)−1)/κ et r = log(κ)/κ ; notamment, le moment où l'épidémie commence à régresser correspond à i+r = 1 − 1/κ (seuil d'immunité collective) ;
• quand t→+∞, la proportion i tend vers 0 (bien sûr) et s tend vers Γ := −W(−κ·exp(−κ))/κ (en notant W la fonction de Lambert) l'unique solution strictement comprise entre 0 et 1 de l'équation Γ = exp(−κ·(1−Γ)) (qui vaut 1 − 2·(κ−1) + O((κ−1)²) pour κ proche de 1, et exp(−κ) + O(κ·exp(−2κ)) pour κ grand), tandis qu'évidemment r, lui, tend vers 1−Γ (taux d'attaque final).

J'ai parlé dans cette entrée de la différence entre seuil d'immunité collective et taux d'attaque final (qui sont les deux quantités essentielles que le modèle calcule) dans le modèle SIR.

*

[Lire la suite…]

Interrompons un petit peu la succession de rants au sujet du covid pour parler un peu de maths. Je déterre pour le terminer un vieux texte que j'avais commencé il y a environ deux ans et que j'avais abandonné, mais auquel je repense parce que j'ai reréfléchi à des questions adjacentes. Le but est ici de définir un concept à cheval entre la logique et la calculabilité qui s'appelle la réalisabilité de Kleene. Plus tard (un jour, si j'en trouve le temps et la patience) j'aimerais parler du topos effectif, et comme le topos effectif contient (généralise, donne un cadre catégorique à) la réalisabilité de Kleene, il sera utile que j'aie au moins écrit à ce sujet avant, même si en principe on n'a pas besoin de passer par cette étape intermédiaire. [Ajout : le billet sur le topos effectif est ici.]

Tout ceci a un rapport avec la logique intuitionniste : j'ai déjà écrit un post de blog à ce sujet, qu'il peut être utile d'avoir lu, mais il faut admettre qu'il est extrêmement brouillon et mal structuré [ajout : celui-ci, écrit ultérieurement, est sans doute bien plus clair]. En tout état de cause, il n'est pas nécessaire de savoir ce que c'est que la logique intuitionniste pour comprendre la définition de la réalisabilité de Kleene. (Le principal prérequis à ce qui va suivre est de savoir les bases de la calculabilité : ce qu'est une machine de Turing — ou toute autre représentation des fonctions partielles calculables —, et savoir qu'on peut les encoder par des entiers naturels ; donc comprendre une expression comme le résultat de l'exécution de la machine de Turing codée par l'entier e sur l'entier n en entrée. c'est-à-dire l'image de n par la e-ième fonction calculable partielle, qui sera noté e•n ci-dessous.) Néanmoins, comme la réalisabilité de Kleene est compatible avec les règles de la logique intuitionniste (elle réalise tous les théorèmes de l'arithmétique de Heyting), et est inspirée par (et rend rigoureux) les principes (informels) de Brouwer-Heyting-Kolmogorov, c'est bien d'en avoir au moins une idée ; cette connexion avec la logique intuitionniste sera encore plus forte dans le topos effectif : on peut dire sommairement qu'un topos est une sorte de « monde mathématique alternatif » régis par les lois de la logique intuitionniste (et le topos effectif est un tel monde où la calculabilité joue un rôle central et notamment toutes les fonctions ℕ→ℕ sont calculables).

Mais le but de cette entrée-ci n'est pas de décrire le topos effectif (pas qu'il soit très long à définir, mais ça devient long si on veut en dire le minimum pour que ce soit intéressant). C'est de présenter une notion plus ancienne, la réalisabilité de Kleene, qui sert de fondement ou de prolégomène à la construction du topos effectif. Je dois avouer que le sens profond de cette notion m'échappe encore, et j'ai vaguement l'impression que personne ne la comprend aussi profondément qu'il voudrait ; je ne sais même pas bien ce que Kleene cherchait à faire en introduisant cette notion. Mais superficiellement, l'idée est qu'on définit une notion que je vais noter n ⊪ φ, lire n réalise φ, entre un entier naturel n et une formule logique φ de l'arithmétique du premier ordre (je vais rappeler ce que c'est plus bas), et dont le sens intuitif est que n apporte une sorte de témoignage(?) algorithmique de la véracité de φ (néanmoins, on va voir que φ n'est pas forcément vraie dans le monde classique, et il va s'agir d'expliquer le rapport entre ces notions).

Le rapport avec le topos effectif sera notamment que les énoncés arithmétique du premier ordre qui sont réalisables (au sens où il existe un n qui les réalise) seront exactement ceux qui seront vrais dans le topos effectif. En particulier, la réalisabilité permet de faire un pont vers la logique intuitionniste, même en partant de la logique classique : on n'a pas besoin de savoir ce qu'est la logique intuitionniste ni comment elle fonctionne pour définir la relation n ⊪ φ, mais une fois qu'on l'a définie, on constate qu'elle fonctionne de façon fondamentalement intuitionniste en φ (et notamment, réaliser la double négation ¬¬φ n'est pas du tout pareil que réaliser φ). Par ailleurs, la relation n ⊪ φ est elle-même une formule logique (avec une variable n de plus que la formule de départ), on peut se demander sous quelle condition elle-même est réalisable, ou démontrable (ou démontrablement réalisable), etc., et les réponses sont assez satisfaisantes.

Ajout : ce billet ultérieur, sur la réalisabilité propositionnelle (qu'on peut lire avant, ou après, ou indépendamment) a aussi un rapport étroit avec celui-ci, puisque la réalisabilité propositionnelle est la logique propositionnelle interne du topos effectif de même que la réalisabilité de Kleene dont il est question ici est l'arithmétique du premier ordre dans le topos effectif.

Avant de donner la définition, je dois rappeler des choses sur la logique, qu'on peut sans doute se contenter de lire en diagonale parce que ce qui suit est vraiment standard et peu surprenant.

Pour être tout à fait exact, je définis par les mêmes clauses énumérées ci-dessus deux variantes de la réalisabilité : il y a une notion dans l'univers mathématique, si j'ose dire, ambiant (n étant un entier naturel et φ une formule de l'arithmétique du premier ordre, n ⊪ φ a le sens défini par les clauses ci-dessus), et il y a une réalisabilité formalisée qui consiste à voir les clauses ci-dessus elles-mêmes dans l'arithmétique du premier ordre, c'est-à-dire qu'on va définir, par exemple, n ⊪ (φ∧ψ) comme la formule ∃n.(n=⟨p,q⟩ ∧ (p⊪φ) ∧ (q⊪ψ)) et ainsi de suite. Il n'y a pas forcément besoin de distinguer ces deux notions, mais il est important de noter que la réalisabilité peut être formalisée, et donc que n ⊪ φ est elle-même une formule de l'arithmétique du premier ordre (pour n une variable libre n'apparaissant pas libre dans φ). (Ce n'est pas tellement différent de la formalisation de la notion de démonstration : l'affirmation φ est démontrable dans l'arithmétique de Peano, par exemple, est un énoncé arithmétique lorsque φ en est un : cf. ici pour plus d'explications.)

On lit n ⊪ φ en disant que n réalise φ ou que φ est réalisée par n, et ∃n.(n⊪φ) en disant que φ est réalisable.

[Lire la suite…]

Je veux écrire ici une petite note sur un point que je pense avoir mal expliqué par le passé, et autour duquel il existe une certaine confusion. Il s'agit du rapport entre le seuil d'immunité grégaire d'une part et le taux d'attaque final d'une épidémie d'autre part : quelle est la différence entre ces deux concepts, que penser de l'écart, ou overshoot entre ces deux quantités, et laquelle est la plus pertinente en pratique. Il faudra bien distinguer le cas du modèle théorique SIR et le cas d'une épidémie réelle (et pour faire la transition de l'un à l'autre, j'évoquerai rapidement un modèle SIR « en deux phases »).

Le seuil d'immunité grégaire (ou …collective, peut-être un meilleur terme parce qu'il évoque moins l'image déplaisante d'un troupeau, mais comme j'ai commencé avec grégaire je préfère maintenant rester dessus) est la proportion d'immuns qu'il faut atteindre dans la population pour que le nombre de reproduction effectif de l'épidémie devienne <1. Autrement dit :

• soit on considère une épidémie naissante, c'est-à-dire qu'il n'y a que très peu d'infectés, mais pour laquelle un certain nombre d'individus sont préalablement immunisés (par exemple par un vaccin) : alors le seuil d'immunité grégaire est le nombre d'immunisés nécessaires pour que l'épidémie ne démarre pas (son nombre de reproduction est <1 donc le petit nombre d'infectés disparaît simplement) ;
• soit on considère une épidémie déjà en cours, et dans ce cas le fait qu'on atteigne le seuil d'immunité grégaire se voit au fait que le nombre d'infectés commence à décroître, c'est-à-dire qu'il y en a de moins en moins (le nombre de reproduction est <1 donc ce nombre diminue progressivement).

Par contraste, le taux d'attaque final (qui n'a de sens qu'en considérant le cours d'une épidémie particulière) est la proportion d'individus qui seront atteints par l'épidémie pendant toute sa durée.

Même si on suppose que l'immunité est parfaitement stérilisante et dure indéfiniment (ce que je ferai pour simplifier, ce n'est pas le propos ici de discuter de ces questions), ces deux quantités sont différentes : la raison est simple, c'est que même une fois que le seuil d'immunité grégaire est atteint, le nombre d'infectés commence certes à diminuer, mais il n'est pas nul pour autant, donc il y a de l'inertie : ce nombre d'infectés en infecte un plus petit nombre, qui en infecte à son tour un encore plus petit nombre, et ainsi de suite, mais la somme de tout ça n'est pas nulle.

La différence entre ces deux quantités s'appelle l'overshoot de l'épidémie : i.e., l'overshoot est la proportion qu'elle attaque en plus du seuil d'immunité grégaire.

Dans le cas du modèle théorique (ultra-simpliste) SIR, on peut calculer explicitement ces deux quantités. Je l'ai fait dans l'entrée que j'ai écrite à ce sujet, mais je n'ai pas été clair parce que je n'avais pas la bonne terminologie (j'ai parlé de modèle extrêmement simpliste pour une description qui calcule, en fait, le seuil d'immunité grégaire, ce qui a pu augmenter la confusion), je redis donc les choses un peu autrement : en notant κ le nombre basique de reproduction (lettre que je préfère à R parce que le R de SIR a un sens différent), c'est-à-dire le nombre de reproduction pour une population immunologiquement (et sociologiquement) naïve :

• le seuil d'immunité grégaire r_herd dans le modèle SIR se calcule à partir du nombre basique de reproduction κ par la formule r_herd = 1 − 1/κ (la démonstration est facile : lorsqu'une proportion s des individus est susceptible, le nombre de reproduction effectif tombe de κ à κ·s simplement parce que chaque contact possiblement infectieux a cette probabilité de donner effectivement une infection, du coup pour avoir κ·s = 1 on doit avoir s = 1/κ et cela correspond à la proportion complémentaire r = 1 − 1/κ d'immuns au final) ;
• le taux d'attaque final r_∞ dans le modèle SIR se calcule à partir du nombre basique de reproduction κ par la formule r_∞ = 1 + W(−κ·exp(−κ))/κ où W désigne la fonction transcendante W de Lambert (j'ai déjà démontré cette formule dans mon entrée passée sur le sujet).

J'ai tracé ces deux courbes ci-contre en fonction du nombre de reproduction κ : en rouge le seuil d'immunité grégaire, et en bleu le taux d'attaque final. Rappelons en outre, pour ce qui est du comportement asymptotique que [encore une fois, tout ça je l'ai déjà dit, mais avec une terminologie qui n'était pas claire] :

• si le nombre basique de reproduction κ est juste un peu au-delà de 1, disons 1 + h avec h>0 petit, alors le seuil d'immunité grégaire r_herd vaut h − h² + O(h³) tandis que le taux d'attaque final r_∞ vaut 2·h − (8/3)·h² + O(h³), donc en gros le double (ce qui se conçoit grosso modo par le fait que les deux périodes de l'épidémie sont alors symétriques, celle où elle est croissante jusqu'au seuil d'immunité grégaire, et celle d'overshoot où elle est décroissante jusqu'à tendre vers son taux d'attaque final),
• si le nombre basique de reproduction κ est grand, alors le seuil d'immunité grégaire r_herd vaut 1 − 1/κ (il n'y a rien à simplifier) tandis que le taux d'attaque final r_∞ vaut 1 − exp(−κ) − κ·exp(−2κ) + O(κ²·exp(−3κ)), qui devient vite extrêmement proche de 1.

[Lire la suite…]

Pendant que j'étais occupé à ne pas écrire dans ce blog, les sujets sur lesquels j'aurais pu écrire quelque chose se sont accumulés. Je veux dire, les sujets sur lesquels soit j'ai appris quelque chose et j'aurais pu/dû le braindumper ici pour me simplifier la vie quand j'aurais plus tard oublié et voulu réapprendre, soit je me suis simplement dit que c'était quelque chose de potentiellement intéressant dans quoi je devrais me plonger si j'avais le temps. Bref, voici une liste de quelques choses sur lesquels je n'ai rien écrit, et il n'est pas impossible que j'y revienne, mais il ne faut pas compter dessus non plus. Pas un TODO, mais un MIGHTDO, si on veut.

(Les différentes parties qui suivent n'ont généralement aucun rapport entre elles. C'est bien le problème, si j'ose dire, de trop aimer l'éclectisme. Par ailleurs, elles mélangent des sujets où j'ai quelques trucs à expliquer (mais je ne le fais pas vraiment ici) et d'autres où j'ai simplement des questions à poser, ou encore où je n'ai rien à dire mais que j'utilise simplement comme memento pour me rappeler que c'est quelque chose d'intéressant à visiter ou revisiter un jour. Les explications, ou les absences d'explications, qui suivent, se placent aussi à des niveaux très variés de prérequis mathématiques.)

Liens vers les sous-parties de cette entrée : • Mandelbrot • inégalités de Bell • topologie sans points • axiome de Scott • topos effectif • complexité au-delà du calculable • algèbres de Jordan • problème du secrétaire • mécanique sphérique • surface de Bring • Cayley-Bacharach • le spectre des polynômes à valeurs entières

[Lire la suite…]

Même si mon moral est moins mauvais, je continue à avoir beaucoup de mal à faire autre chose que de l'épidémiologie. Du coup, je vais en parler encore une fois, pour présenter une approche différente du calcul du taux d'attaque, qui permet cette fois-ci d'illustrer (par des considérations théoriques plutôt que des simulations numériques) certains effets d'hétérogénéité. (Il s'agit d'une traduction+développement de ce que j'ai écrit dans ce fil Twitter [lien direct Twitter] ainsi que celui-ci [lien direct Twitter], et secondairement, de ce fil [lien direct Twitter] plus ancien.) Mais je commence par quelques remarques d'ordre méta sur ces effets d'hétérogénéité et les épidémiologistes de fauteuil (si ça ne vous intéresse pas, sautez après).

On (un des auteurs !) a enfin fini par me pointer du doigt un livre (et donc une référence citable !) où étaient traitées les probématiques épidémiologiques qui me préoccupaient : il s'agit de Mathematics of Epidemics on Networks (From Exact to Approximate Models) d'István Z. Kiss, Joel C. Miller et Péter L. Simon (Springer 2017). Non seulement il traite exactement tout ce que je voulais voir traité, mais la présentation est vraiment très agréable pour le mathématicien que je suis : les énoncés sont précis, les approximations sont expliquées avec soin, les notations ne sont pas trop pénibles, bref, je le recommande très vivement. (Quel dommage que toutes les bibliothèques soient fermées… Si seulement il y avait un site web — qui pourrait par exemple porter le nom en anglais d'une bibliothèque et du premier livre de la Bible — où on pourrait trouver les PDF de ce genre de choses. Ah non, zut, ce serait illégal, parce qu'on a des lois à la con qui empêchent la diffusion des connaissances. Mais pardon, je digresse.)

Il y aurait peut-être à analyser la raison pour laquelle j'ai réussi à passer à côté de cet excellent ouvrage jusqu'à tout récemment. (Il est possible qu'on me l'ait déjà suggéré et que je sois quand même passé à côté de la suggestion, parce que le mot networks ne m'inspirait pas : en fait, il s'agit de graphes, il y a apparemment des gens qui, parce qu'ils ont une approche un peu différente, parlent de réseaux pour parler de graphes, et notamment de graphes aléatoires, ce qui est leur droit mais ça ne facilite pas la communication. J'aimerais quand même bien comprendre, par exemple, pourquoi si on recherche Galton-Watson "attack rate" dans Google, les deux premières réponses sont de moi, alors que ça a quand même l'air d'être des termes très naturels à rechercher dans le contexte de la propagation des épidémies, et d'ailleurs le livre que je viens de mentionner devrait être dans les résultats, et beaucoup plus haut qu'un tweet à moi.) Mais je ne vais pas m'étendre là-dessus, en tout cas pas maintenant.

Bref, toujours est-il que j'ai été soulagé de voir que tout un tas de phénomènes que je voulais voir étudiés, et que j'avais au moins en partie redécouverts, comme ce que je vais décrire ci-dessous, étaient effectivement étudiés quelque part, et que j'aurai des références citables à montrer. J'ai l'habitude de redécouvrir des résultats connus, je dirais même que ça fait partie du fonctionnement normal de la science, et quand je l'apprends je suis plutôt content que mon intuition ne soit pas complètement à côté de la plaque.

En revanche, je demeure perplexe quant au fait que ces phénomènes soient bien connus ou non des épidémiologistes. Il y a deux prépublications qui sont sorties récemment, une sur l'arXiv (par des matheux) et une autre sur medRxiv (par des épidémiologistes plus médecins, ça se voit au fait qu'ils déposent sur medRxiv et n'utilisent pas TeX ), qui font tous les deux la même observation, évidemment formulée et argumentée de façon plus précise, que j'écrivais dans cette entrée de blog ou de façon concise dans ce tweet (en mars) : l'épidémie va atteindre, et donc immuniser, les personnes les plus connectées en premier, ce qui fait que l'hétérogénéité des contacts contribue à réduire le seuil d'immunité à partir duquel elle se met à régresser (le premier de ces documents calcule 43%, ce qu'il ne faut pas, à mon avis, prendre comme une prédiction mais comme un ordre de grandeur grossier de l'effet qu'on peut attendre). D'un côté, il semble que ce type d'effet ait été étudié depuis 1980 (au plus tard). Mais de l'autre, un épidémiologiste renommé (Marc Lipsitch) semble considérer que c'est intéressant et vaguement nouveau, et il y en a qui n'ont pas reçu le message (et ce n'est qu'un exemple parmi d'autres où j'ai vu affirmer, y compris de la part de personnes qui sont des épidémiologistes ou qui ont une formation proche, que puisque R₀~3 on doit atteindre ~70% d'immunisés pour que l'épidémie régresse). Donc il y a, au minimum, un problème de communication. Ce n'est pas très grave, maintenant j'ai au moins quelque chose d'un peu plus crédible (un PDF !) à citer pour contester cette idée (et le fait que Marc Lipsitch prenne ça au sérieux est bien puisque c'est lui qui est à l'origine, d'avoir popularisé le chiffre de 70% comme taux d'attaque, même s'il l'a immédiatement nuancé). Mais ça reste un peu pénible d'avoir l'impression d'être le crackpot qui vient contredire les experts qui ont dit que c'était 70%. (Un peu quand comme l'OMS a fait une communication un peu hâtive en affirmant qu'il n'y avait aucun signe que l'infection par le Covid-19 confère une quelconque forme d'immunité, alors que quand même, si, il y a des raisons de le penser : ce n'est vraiment pas une position confortable que de tenir le discours je ne suis pas du tout médecin, mais je vais quand même remettre l'OMS à sa place sur une question de médecine. Bon, je digresse encore.)

PS : D'ailleurs, on me souffle que j'ai peut-être contribué à diffuser ces idées. Tant mieux si c'est le cas.

❦

[Lire la suite…]

Il y a quatre éternités semaines, quand nous n'étions pas encore maintenus prisonniers chez nous, j'ai parlé ici du modèle épidémiologique SIR, le plus basique qui soit. Je rappelle brièvement les principes qui le définissent :

• l'immunité acquise est permanente, les individus sont successivement S (susceptibles, c'est-à-dire jamais infectés donc susceptibles de l'être), I (infectés et infectieux) et R (rétablis, c'est-à-dire guéris ou morts) (il existe toutes sortes de variantes, par exemple le modèle SEIR ajoutant un état E (exposé) pour les individus infectés mais non encore infectieux) ;
• la population est homogène (fongible) avec mélange parfait dans les contacts (j'ai parlé ici de l'effet de modifier cette hypothèse) ;
• la contamination et le rétablissement se font selon une cinétique d'ordre 1, c'est-à-dire que la contamination se fait proportionnellement aux proportions d'infectés et de susceptibles (avec une constante cinétique β), et que le rétablissement se fait proportionnellement à la proportion d'infectés (avec une constante cinétique γ).

Rappelons brièvement ce que j'ai exposé la dernière fois. Les équations de ce modèle SIR basique, que j'appellerai (*) pour m'y référer plus tard, sont les suivantes (il s'agit d'un système d'équations différentielles ordinaires non-linéaire, du premier ordre et autonomes) :

• s′ = −β·i·s
• i′ = β·i·s − γ·i
• r′ = γ·i
• (s+i+r=1)

où s,i,r≥0 sont les proportions de susceptibles, d'infectieux et de rétablis dans la population ; les solutions de ces équations ne semblent pas pouvoir s'exprimer en forme close, mais on peut exprimer s en fonction de r (à savoir s = exp(−κ·r) dans les conditions exposées ci-dessous).

Je rappelle les principales conclusions que j'avais exposées dans mon entrée sur ce modèle (*), en supposant qu'on parte d'une population presque entièrement susceptible avec une proportion infinitésimale d'infectés (plus exactement, on s'intéresse aux solutions pour lesquelles s→1 quand t→−∞) ; on notera κ := β/γ le nombre de reproduction, que je suppose >1 :

• tant que s reste très proche de 1 (si on veut, t→−∞), les proportions i et r croissent comme des exponentielles de pente logarithmique β−γ = β·((κ−1)/κ), avec un rapport 1/(κ−1) entre les deux, autrement dit comme i = c·exp((β−γ)·t) = c·exp(β·((κ−1)/κ)·t) et r = c·(γ/(β−γ))·exp((β−γ)·t) = c·(1/(κ−1))·exp(β·((κ−1)/κ)·t) (ergotage : dans l'entrée sur le sujet, j'avais mis un −1 aux exponentielles pour r, parce que je voulais partir de r=0, mais je me rends compte maintenant qu'il est plus logique de partir d'une solution où i/r tend vers une constante en −∞, cette constante étant κ−1) ;
• au moment du pic épidémique (maximum de la proportion i d'infectés), on a s = 1/κ et i = (κ−log(κ)−1)/κ et r = log(κ)/κ ;
• quand t→+∞, la proportion i tend vers 0 (bien sûr) et s tend vers Γ := −W(−κ·exp(−κ))/κ (en notant W la fonction de Lambert) l'unique solution strictement comprise entre 0 et 1 de l'équation Γ = exp(−κ·(1−Γ)) (qui vaut 1 − 2·(κ−1) + O((κ−1)²) pour κ proche de 1, et exp(−κ) + O(κ·exp(−2κ)) pour κ grand), tandis qu'évidemment r, lui, tend vers 1−Γ.

Je veux ici explorer la modification d'une hypothèse de ce modèle (*), celle qui concerne le rétablissement. Quand j'écris ci-dessus que le rétablissement se fait proportionnellement à la proportion d'infectés (avec une constante cinétique γ), au niveau individuel, cela signifie la chose suivante :

Pendant chaque intervalle de temps de longueur (durée) dt très courte, la probabilité qu'un individu infecté (I) se rétablisse (I→R) vaut γ·dt et ce, indépendamment d'un individu à l'autre et d'un instant à l'autre.

Autrement dit, le temps de rétablissement d'un individu infecté donné suit une distribution de probabilité exponentielle d'espérance 1/γ.

Autant l'hypothèse analogue sur la cinétique de la contamination est relativement plausible (si on admet le principe éminemment discutable d'une population homogène et du mélange parfait !), autant l'hypothèse sur le temps de rétablissement est médicalement insensé : on est en train de dire que si vous êtes malade, votre probabilité de guérir (ou d'ailleurs, de mourir) ne dépend pas de l'avancement de votre maladie mais est la même pendant la première heure que pendant la 1729e (si tant est que vous soyez encore malade à ce stade-là). Une maladie ne se comporte pas comme ça !

Cherchons donc à remplacer cette hypothèse par une autre, tout aussi simpliste, mais néanmoins un peu plus proche de la réalité médicale, celle du rétablissement en temps constant.

Un individu infecté (I) se rétablit toujours au bout du même temps T après son moment d'infection.

Autrement dit, le temps de rétablissement d'un individu infecté donné suit une distribution de Dirac concentrée en T (qui est, du coup, son espérance).

[Lire la suite…]

Je suis vraiment débordé (le temps que je passe à me documenter sur l'épidémie et à répondre aux présentations biaisées et autres conneries sur Twitter représente une surcharge de travail absolument énorme qui s'ajoute au fait que tout est devenu tellement plus long et compliqué dans ma vie, je ne vais pas pouvoir tenir longtemps comme ça), donc je me contente ici de reproduire en français ce que j'ai écrit dans un fil Twitter :

Il s'agit d'expériences numériques sur l'influence de la structure du graphe social sur le taux d'attaque des épidémies (taux d'attaque = le nombre de personnes infectées cumulé pendant l'épidémie).

Rappelons la situation basique : j'ai déjà écrit ici sur mon blog (et ici en anglais sur Twitter) sur ce que prédit le modèle épidémiologique SIR au sujet du taux d'attaque. En bref, il prédit un taux d'attaque énorme : 89% (de la population touchée) pour un nombre de reproduction de 2.5. (La formule, comme je l'ai expliqué, est 1 + W(−κ·exp(−κ))/κ = 1 − exp(−κ) + O(κ·exp(−2κ)) où κ est le nombre de reproduction. Par ailleurs, il faut bien différencier ce taux d'attaque du seuil d'immunité grégaire qui, lui, vaut, 1 − 1/κ, et qui est le taux d'infectés à partir duquel l'épidémie commence à régresser, c'est-à-dire le taux d'attaque au pic épidémiologique.)

Or les épidémies réelles ne semblent pas avoir des taux d'attaque aussi énormes, même avec des nombres de reproduction de l'ordre de ce que je viens de dire. Bien sûr, on connaît mal le taux d'attaque même a posteriori, mais (malgré une absence d'immunité préalable aux souches) il semble que les grippes de 1918 et 1957 aient infecté autour de 30% de la population à différents endroits, pas franchement autour de 90%.

Alors que se passe-t-il ? Mon explication est que SIR, étant un modèle basé sur des équations différentielles, ne connaît qu'une seule chose, c'est la proportion de la population qui est susceptible, infectée et rétablie, et pas où ces personnes sont ni comment elles interagissent socialement.

Autrement dit, un tel modèle suppose un « mélange parfait » : tout individu a la même probabilité d'infecter n'importe quel autre individu. Ce n'est bien sûr pas du tout le cas dans la réalité. En réalité, une bonne proportion des contaminations suit un graphe social (famille, amis, collègues).

Même les modèles plus sophistiqués qui stratifient la population par catégories d'âge (disons) supposent toujours un mélange parfait dans chaque catégorie. Je soupçonne que c'est la raison pour laquelle le papier d'Imperial obtient un taux d'attaque si élevé (j'en ai déjà parlé dans cette entrée, voir aussi ce fil Twitter).

Alors, comment peut-on prendre en compte le fait que les contaminations suivent des graphes sociaux, et que doit-on en attendre ? Je m'attendais, et je voulais tester, deux effets apparentés mais distincts :

Le premier effet est que si l'épidémie doit suivre les liens d'un graphe social de connectivité relativement modeste (chacun n'ayant qu'un petit nombre de parents/amis/collègues par rapport à toute la population), elle va s'étouffer plus rapidement, même pour un nombre de reproduction donné, par rapport au cas de mélange aléatoire : c'est ce que j'ai essayé de dire ici sur Twitter ainsi que dans cette entrée dans la phrase la première [sous-raison] c'est (a) que quand on retire une proportion suffisamment élevées de sommets d'un graphe (en l'occurrence celui des contacts humains), il cesse de « percoler », c'est-à-dire qu'on ne peut plus passer d'un sommet à un autre. Ce phénomène est, en effet, lié à des questions de seuil de percolation dans les graphes (qui est, en gros, la proportion des sommets, ou des arêtes selon la définition, qu'il faut retirer aléatoirement à un graphe pour qu'il cesse d'avoir une composante connexe géante) : l'idée est que quand suffisamment de personnes (=sommets, =nœuds) sont immunisées, l'épidémie ne peut plus se propager d'un point à un autre : même avec l'hypothèse de mélange parfait le nombre d'immunisés ralentit l'épidémie, mais le seuil de percolation suggère qu'une proportion plus faible d'immunisés peut arrêter complètement la propagation (et, probablement, on la ralentit plus vite avant de l'arrêter complètement).

Le second phénomène est différent : non seulement il doit suffire de retirer relativement peu de nœuds pour arrêter l'épidémie (comme je viens de l'expliquer), mais en plus l'épidémie va retirer (c'est-à-dire infecter et rendre immuns) en premier les nœuds les plus « précieux » à sa propre propagation, parce que ce sont les nœuds les plus connectés, les « célébrités ». C'est ce que j'ai essayé d'exprimer ici et là (+ tweet suivant) sur Twitter, ainsi que dans la même entrée que mentionée dans la phrase (b) les infections ont tendance à infecter en premier les personnes qui sont hautement connectées dans le graphe, et en les rendant immunes, elle neutralise en premier les liens qui lui permettaient le plus facilement de se propager.

Tout ça n'est que mon intuition ! Maintenant, voyons si je peux modéliser ces phénomènes, pour au moins montrer qu'ils existent. Je ne vais pas chercher à quantifier les effets (il y a tout simplement trop de paramètres avec lesquels jouer), seulement d'illustrer qu'ils peuvent exister et semblent jouer dans la direction que je pensais.

J'ai donc écrit un petit programme Perl qui simule un modèle épidémique SEIR stochastique. SEIR, ça signifie que les nœuds (les individus) passent entre quatre états, S = susceptible = non-infecté, puis E = exposé = en incubation, puis I = infectieux et enfin R = rétabli = immunisé ou mort. Stochastique, ça signifie que plutôt que modéliser les choses avec des équations différentielles, je prends un grand nombre de nœuds (300 000 dans mes expériences) et les contaminations ont lieu au hasard. Ça rend les calculs non-reproductibles, mais cela permet de gérer des situations bien plus complexes qu'avec des équations différentielles.

[Lire la suite…]

Dans l'entrée précédente, je soulevais entre autres la question de comment calculer (et de comment appeler !) le nombre, que j'y appelais r, de personnes qui sont finalement infectés par une épidémie (quelle que soit l'issue de cette infection) puisque c'est un des facteurs du produit f·r qui donnera le taux de mortalité due à l'infection (l'autre étant la proportion f des cas qui conduisent à un décès) ou de tout autre calcul analogue (comme g·r pour le nombre de cas graves où g est la proportion correspondante). Dans plusieurs mises à jour ultérieures de cette entrée, j'ai signalé que j'ai fini par apprendre que r s'appelle le taux d'attaque et un raisonnement simpliste pour l'estimer, que je reproduis ici parce que je vais vouloir le comparer à une estimation donnée par un modèle différent :

[Essentiellement recopié de ce fil Twitter :] Une amie m'a expliqué le rapport que je cherchais à comprendre entre le taux de reproduction de base R₀ (= nombre de personnes que chaque personne infectée infecte à son tour) et le taux d'attaque final r (= proportion de la population qui sera infectée à terme pendant l'épidémie) : dans le modèle le plus simpliste, c'est r = 1 − 1/R₀ ; en effet, tant que le taux de reproduction est >1, l'épidémie croît exponentiellement ; mais si une proportion r a déjà été infectée, le taux effectif de reproduction est ramené à R₀·(1−r) parce que, en supposant que les personnes déjà infectées sont immunisées et sont également réparties dans la population (j'ai bien dit, modèle simpliste !), seule une proportion 1−r est encore susceptible d'être contaminée ; donc l'épidémie cesse de progresser lorsque R₀·(1−r) redescend à 1, c'est-à-dire r = 1 − 1/R₀. C'est probablement la raison pour laquelle certains ont prédit r ~ 70% en l'absence de contre-mesures efficaces pour réduire R₀ qui a été initialement mesuré à R₀ ~ 3. Encore une fois, ceci est un modèle extrêmement simpliste.

Dans la suite, je vais noter plutôt κ que R₀ ce nombre de reproduction, parce que même si R₀ est la notation standard elle serait source de confusion dans le modèle SIR où la lettre R désigne les cas rétablis (guéris, recovered en anglais ; enfin, avec une drôle de définition de rétablis puisque dans le modèle qui va suivre on ne cherche pas à compter les décès et on les compte avec les guérisons). Par ailleurs, plutôt que le taux d'attaque final noté r ci-dessus (ce qui, par chance, colle bien, à la limite, avec l'usage de la lettre R que je viens d'évoquer), je vais m'intéresser plutôt à la proportion complémentaire s = 1−r, i.e., la proportion de la population qui échappe à l'épidémie, et dont le raisonnement simpliste que je viens de recopier prédit donc qu'il s'agit de 1/κ.

Maintenant, en suivant de près ce fil Twitter (ou ici sur Thread Reader), que je développe un peu un peu, je vais essayer d'expliquer la prédiction que fait un modèle basique en épidémiologie, le modèle SIR :

Le modèle SIR modélise une infection en traduisant l'évolution dans le temps de trois variables : s (susceptible) la proportion de la population qui n'a pas encore contracté l'infection (et qui est donc susceptible de l'attraper), i (infectée) la poportion de la population qui est actuellement infectée, et r (rétablie) la proportion de la population qui n'est plus infectée, que ce soit suite à une guérison ou un décès (cf. ci-dessus : on ne s'intéresse pas à la différence ici). On a s + i + r = 1 puisqu'il s'agit de trois parties exclusives et exhaustives : il y a donc seulement deux variables indépendantes. Le modèle fait toutes sortes d'hypothèses simplificatrices : notamment, que la population est constante (puisque les décès comptent parmi les guéris, ce n'est pas idiot), et surtout, que les personnes ayant contracté l'infection ne peuvent pas la contracter une seconde fois (soit parce qu'elles sont immunisées soit parce qu'elles sont décédées).

Il s'agit d'écrire une équation différentielle (non-linéaire, du premier ordre) portant sur ces variables. L'idée est d'écrire le type d'équations utilisées en cinétique chimique : imaginez qu'on aurait deux réactions chimiques, la réaction d'infection S + I → I + I (une personne infectée en infecte une autre) et la réaction de rétablissement, I → R (les personnes infectées se rétablissent toutes seules avec le temps, je rappelle une fois de plus que rétablir ici compte les décès, tout ce qui m'intéresse est que ces personnes ne puissent plus en contaminer d'autres). Ce qu'on fait en cinétique chimie (de façon ultra-simplifiée…) pour modéliser des réactions de type X + Y → Z est qu'on va écrire que l'occurrence d'une telle réaction, i.e., la variation de concentration due à cette réaction (qui va compter positivement dans la concentration de Z et négativement pour X et Y) est proportionnelle à une certaine constante cinétique (positive) fois le produit des concentrations de X et de Y à des puissances appelées l'ordre de la cinétique dans chacun de ces réactifs, typiquement 1. Dans le modèle épidémiologique SIR, les deux réactions d'infection et de rétablissement seront supposées d'ordre 1. On va appeler β et γ leurs constantes cinétiques respectives : les termes de vitesse de l'infection et du rétablissement seront donc β·i·s et γ·i respectivement. Autrement dit :

Si je note x′ la dérivée dx/dt par rapport au temps (t) de la variable x, les équations du modèle SIR seront :

• s′ = −β·i·s
• i′ = β·i·s − γ·i
• r′ = γ·i

(La somme de ces trois quantités fait évidemment zéro, comme il se doit puisqu'on doit conserver s+i+r=1 : comme en chimie, rien ne se crée, rien ne se perd, mais tout se transforme.) La première équation, donc, modélise le fait que la population non encore infectée décroît par la vitesse infection dans le temps β·i·s qui est proportionnelle à une constante β fois les proportions de personnes infectées i et susceptibles de l'être s : si l'on préfère, cela signifie qu'une personne susceptible a une probabilité β·i de devenir infectée par unité de temps (très petite) ; la troisième modélise le fait que les personnes infectées deviennent rétablies avec la vitesse γ·i : si l'on préfère, cela signifie qu'une personne infectée a une probabilité γ de devenir rétablie par unité de temps (très petite) ; et l'équation du milieu, donc, assure l'équilibre s+i+r=1.

La nouvelle (et énorme !) hypothèse simplificatice qu'on a faite en écrivant ces équations, c'est de supposer que le comportement « local » de l'épidémie et de la population ne change ni avec le temps ni avec le progrès de l'épidémie : la probabilité d'infection par rencontre S+I, ou de guérison, ne changent pas : ceci exclut, par exemple, le fait que la population changerait ses habitudes avec la progression de l'épidémie (prendrait des mesures prophylactique), que le système de santé soit débordé (ce qui jouerait possiblement sur le temps de guérison), que le pathogène mute pour devenir plus ou moins virulent, et toutes sortes d'autres scénarios sortant de notre modèle extrêmement basique.

Les constantes cinétiques β et γ ont pour grandeur l'inverse d'un temps : il s'agit essentiellement de l'inverse du temps espéré d'infection si toute la population est infectée et du temps espéré de guérison. Remarquons donc qu'en changeant l'échelle de temps on multiplie β et γ par la même constante : le seul paramètre sans dimension dans le modèle est le rapport κ := β/γ, qu'on interprète comme le nombre de personnes qu'une personne infectée infectera en moyenne dans une population entièrement susceptible avant d'être elle-même rétablie. Comme il s'agit du seul paramètre sans dimension, toute discussion doit se faire sur κ. C'est ce κ = β/γ qu'on appelle nombre de reproduction et qui est souvent noté R₀, mais que je préfère noter κ ici pour éviter la confusion avec la variable r.

[Lire la suite…]

Je m'étonne de ne pas trouver d'endroit où je me serais déjà plaint à ce sujet sur ce blog. Peut-être que je sais mal chercher et qu'un petit gnome serviable va me déterrer ça, mais même si j'ai déjà ranté à ce sujet, ça ne fait pas de mal de me répéter, après tout, radoter est un de mes super-pouvoirs :

Le théorème d'incomplétude de Gödel est sans doute le théorème mathématique le plus abusé par les non-mathématiciens. Cela tient certainement au fait qu'on peut en donner des versions dangereusement approximatives et alléchamment sensationnelles comme on ne pourra jamais tout prouver à partir desquelles il est tentant de faire un pas vers la métaphysique pour tirer des conclusions encore plus fantabuleuses. Je crois avoir vu passer des tentatives d'invoquer ce théorème pour prouver :

• l'inexistence de Dieu (sur l'air de Gödel assure qu'on ne peut jamais tout savoir, or Dieu est censé être omniscient, donc Dieu n'existe pas),
• l'existence de Dieu (sur l'air de Gödel assure que la logique et le raisonnement humains ne peuvent pas arriver à toute vérité, donc la vérité est au-delà de l'humain, et c'est qu'elle est divine ; ça me fait penser à cet extrait du film Ridicule)[#],
• la supériorité de l'humain sur la machine (sur l'air de Gödel montre qu'on ne peut pas mécaniquement arriver à la vérité, mais l'intuition humaine arrive à voir que l'énoncé de Gödel est vrai, c'est donc qu'elle est supérieure à la machine),
• l'existence de la conscience (je ne sais plus les détails, mais ça devait recouper le raisonnement précédent),
• l'inexistence de la conscience,
• que la vérité est inaccessible au seul raisonnement, ou inaccessible tout court,
• que la quête d'une théorie ultime de la physique est futile,
• etc.

[#] Une ironie supplémentaire dans l'invocation du théorème d'incomplétude de Gödel pour argumenter pour l'existence de Dieu, c'est que Gödel lui-même a inventé une « preuve » de l'existence de Dieu (ou plus exactement, une formalisation en logique modale de l'argument ontologique de Saint Anselme). Cette preuve ressemble plus à une blague qu'à un argument sérieux, en fait (Gödel introduit une série d'axiomes plus hasardeux les uns que les autres, et dont on sait maintenant qu'ils sont, en fait, sinon contradictoires, au moins amenant des conclusions complètement délirantes, et il en déduit l'existence d'un truc vérifiant la définition de Dieu), et il n'est pas clair si Gödel lui-même la prenait au sérieux. Enfin, bref.

Tous ces raisonnements sont bien sûr du pur pipo. Plus généralement, toute tentative pour donner un sens philosophique (au-delà de la philosophie des mathématiques, bien sûr : métaphysique, théologique, ou même épistémologique si on s'éloigne des mathématiques) au théorème d'incomplétude de Gödel doit être considérée comme hautement suspecte.

Ce que dit le théorème précisément, je ne vais pas le rappeler ici, je l'ai expliqué notamment ici et là, avec quel succès je ne sais pas, mais en tout cas ce n'est pas mon propos ici : mon propos est que ce théorème est un énoncé technique sur la logique du premier ordre, et que toute tentative pour le faire sortir de son cadre technique est certainement une arnaque.

Même si on ne comprend pas ce que ceci signifie, peu importe : le théorème d'incomplétude affirme que

• tout système formel en logique du premier ordre
• qui soit récursivement (= calculablement) axiomatisé
• et qui contient (un fragment suffisant de) l'arithmétique

ne peut pas être à la fois consistant [← anglicisme pratique pour cohérent] et complet, i.e., s'il ne prouve jamais simultanément P et ¬P (:= la négation de P), alors il y a un P pour lequel il ne prouve aucun des deux.

Ce que je veux souligner là, c'est qu'il y a des hypothèses techniques (essentiellement trois, celles que je viens de lister), et que si on omet ces hypothèses, on est probablement en train de dire des bêtises.

Plus exactement, ce que j'ai cité est plutôt le théorème d'incomplétude de Gödel-Rosser. Le théorème d'incomplétude de Gödel, ce serait que tout système formel en logique du premier ordre qui soit récursivement axiomatisé et qui contient (un fragment suffisant de) l'arithmétique ne peut pas être à la fois ω-consistant et complet, mais l'ω-consistance est une hypothèse pénible à expliquer (autant supposer le système arithmétiquement vrai, à ce compte-là) et je ne veux pas chercher des noises à ceux qui ne feraient pas la différence entre Gödel et Gödel-Rosser. (Enfin, si on veut ergoter, le théorème d'incomplétude de Gödel, il dit : Zu jeder ω-widerspruchsfreien rekursiven Klasse ϰ von Formeln gibt es rekursive Klassenzeichen r, so daß weder v Gen r noch Neg (v Gen r) zu Flg(ϰ) gehört (wobei v die freie Variable aus r ist) — et j'avoue que j'ai beau connaître l'allemand, avoir lu l'article par le passé, et avoir une bonne idée de ce que c'est censé vouloir dire, ce n'est pas super clair pour autant pour moi. Mais je pense qu'il est raisonnable de qualifier l'énoncé ci-dessus de théorème d'incomplétude de Gödel.)

L'absence de mention de ces trois hypothèses doit être un drapeau rouge à double titre. D'abord, que le raisonnement est suspect (si on invoque un théorème sans vérifier ses hypothèses, alors que celles-ci sont indispensables, c'est sans doute que le raisonnement est incorrect — bien sûr il peut arriver qu'on ne le dise pas explicitement parce que la satisfaction de telle ou telle hypothèse est évidente et se passe de commentaire, mais dans le cas présent, j'ai du mal à imaginer que ce soit possible). Ensuite, que la personne qui tient le raisonnement ne comprend probablement pas bien le théorème qu'elle prétend appliquer si elle n'en connaît pas les hypothèses exact et le sens de celles-ci. Un autre signe à cet égard est d'ailleurs quand on parle du théorème de Gödel comme s'il n'y en avait qu'un (alors que, sans aller chercher loin, Gödel a aussi pondu un théorème de complétude qui très superficiellement et mal interprété pourrait avoir l'air de dire exactement le contraire du théorème d'incomplétude) ; ceci dit, il ne faut pas non plus accorder trop de valeur à ce signe parce que beaucoup de mathématiciens tout à fait sérieux sont susceptibles de parler du théorème de Gödel (ou d'autres auteurs : je parle régulièrement du théorème d'Euler — pour l'affirmation que a^φ(m)≡1 (mod m) si a est premier à m — alors qu'Euler a démontré des milliers de théorèmes).

[Lire la suite…]

Je me livre ici à quelques réflexions (un peu décousues, je dis toujours ça), autour de la question à quoi servent les maths pures, et les sciences fondamentales en générales ?, sur la notion d'utilité et d'applications pratiques. Pas sûr que tout ce que je dise soit très cohérent (je passe sans véritable transition du rapport entre lettres et sciences au rapport entre enseignement et recherche sans développer adéquatement ni l'un ni l'autre), mais j'espère au moins arriver à faire passer l'idée qu'il ne faut pas accepter sans broncher les préjugés les plus banals à ce sujet.

J'ai l'impression que dans l'esprit de beaucoup de gens[#], il y a une dichotomie (assez claire même si elle n'est pas forcément clairement énoncée) entre : d'un côté les sciences et techniques, dont l'importance dans la société et notamment dans l'enseignement est justifiée par leur utilité pratique, et d'autre part les arts et aux lettres et autres humanités, dont l'importance est justifiée par leur rôle culturel. Si je reformule cette idée dans des termes qui sentent bon la fin du 19e siècle et que je mets quelques majuscules d'emphase : on aurait d'un côté ce qui meut l'Humanité sur le chemin du Progrès, et de l'autre ce qui Éclaire ce chemin en montrant la voie vers le Progrès et le distinguant des Ténèbres alentours. Ou quelque chose comme ça. Ce que je veux dire, c'est que dans cette vision des choses, on a d'un côté des domaines comme la médecine ou la physique qui apportent des bienfaits à l'Homme, et de l'autre, ceux comme la philosophie et l'Histoire qui doivent en quelque sorte alimenter son sens moral.

[#] J'accepte bien volontiers que j'énonce peut-être ici un métapréjugé (i.e., un préjugé sur les préjugés que peuvent avoir les gens) : mais ce n'est pas bien grave si je dénonce une idée qui, en fait, n'existe pas vraiment.

Peut-être que je caricature un peu, mais je pense au moins que l'idée est assez répandue que la raison pour laquelle on doit enseigner l'Histoire et la géographie au lycée est que ces disciplines feraient partie de la « culture générale » que tout bon citoyen doit avoir, tandis que la raison pour laquelle on doit enseigner les mathématiques est qu'elles seraient utiles pour toutes sortes de choses.

Bref, je pourrais m'appesantir à dénoncer le stéréotype du littéraire qui considère que la culture générale se limite aux choses qu'il connaît ; qui pense qu'il est indispensable que tous les lycéens français sachent que Le Cid est une pièce de Corneille, que la cinquième république a été établie en 1958 et que les Pyrénées sont à la frontière entre la France et l'Espagne ; mais qui ne sait pas citer une loi de Newton ou de la thermodynamique, ignore si les plantes sont des eucaryotes ainsi que la différence entre une bactérie et un virus, n'a absolument aucune idée du fonctionnement d'Internet ou du Web, et ne sait peut-être même pas dire combien il y a de millimètres cubes dans un mètre cube ; et si on lui montre du doigt ces incohérences, répondra qu'il a fait des études littéraires et que ces questions techniques sont bien plus pointues et d'ailleurs ne lui servent à rien puisqu'il n'est pas scientifique ; et consentira peut-être à donner comme exemple de culture générale scientifique à peu près la seule chose qu'il sait, disons, que la Terre tourne autour du Soleil et pas le contraire. Je caricature ? En fait, non : j'en ai rencontré plus d'un, comme ça, qui se plaignaient que les jeunes ne savaient plus rien de nos jours, et qui démontraient immédiatement après une ignorance crasse et assumée dans tout domaine scientifique (j'ai le souvenir, par exemple, de quelqu'un qui ne savait pas de quoi était fait un atome, et qui avait l'air de trouver totalement fantaisiste la suggestion que cela pouvait faire partie de la culture générale de le savoir). Mais j'ai déjà parlé de ça dans cette entrée passée, et je ne veux pas la répéter ici. J'écrirai Un Jour® une entrée sur la culture générale et l'effet de perspective dont tout le monde est victime — et je m'inclus dans le tout le monde — qui fait qu'on croit toujours indispensables les savoirs qu'on a soi-même et superflus ceux que l'on n'a pas[#2]. [Mise à jour : c'est ici.] Nous avons tous des trous énormes dans notre « culture générale », et c'est normal : ce qui me dérange plus, en fait, est qu'à une époque où nous avons tous tout le savoir du monde à la portée de nos doigts, l'attitude consistant à ne pas se précipiter sur Wikipédia quand on découvre l'existence d'un de ces trous. Mais tout ça est une digression par rapport au sujet général de cette entrée, est je la referme maintenant.

[#2] Ceci vaut d'ailleurs encore au sein d'un domaine : les mathématiciens, par exemple, croient toujours que les outils et théorèmes mathématiques qu'ils connaissent et manipulent sont centraux dans les mathématiques et qu'il est indispensable de les connaître, alors que tout ce qui sort de leur domaine de prédilection est quelque chose d'arcane.

Toujours est-il que cette attitude consistant à imaginer que les sciences doivent être jugées à l'aune de leur utilité déteint au sein des sciences elles-mêmes, et que les scientifiques se retrouvent à justifier leur travail, notamment leur recherche pour ceux qui sont chercheurs, en expliquant que ça peut servir à quelque chose (et disons-le franchement, la plupart de ces justifications sont bidon, ce qui est normal parce que quand on découvre des choses nouvelles, on ne peut pas encore savoir où elles nous mèneront). Et ce n'est pas tout : la notion d'utilité est elle-même insidieusement réduite à celle d'applications.

Dans ces conditions, les sciences pures sont dans une situation très inconfortable d'apparence paradoxale : puisqu'elles sont des sciences, elles sont censées servir à quelque chose, mais puisqu'elles sont pures, elles n'ont pas d'applications ; donc à force d'accepter les différentes idées stupides que j'ai énoncées plus haut, on en revient à devoir trouver des justifications comme ah, mais on ne peut pas encore savoir si ceci aura un jour des applications. Avec comme exemple représentatif la théorie des nombres, que Gauß ou je ne sais qui considérait comme la reine des mathématiques parce qu'elle n'avait pas d'applications et qui finit par en avoir, et d'importance économique absolument capitale, à travers la cryptographie. Cet exemple est juste mais il est trompeur : je veux dire qu'au lieu d'essayer de trouver des justifications dans des exemples pareils, on ferait mieux de rejeter les prémisses idiotes que les sciences sont justifiées par leur utilité et que la seule forme d'utilité est dans les applications pratiques.

Au lieu de ça, la comparaison que j'aime donner est la suivante : imaginer qu'on puisse se passer des sciences pures pour se focaliser sur les applications est comme imaginer qu'on puisse couper les racines d'un pommier parce qu'il n'y a pas de pommes qui poussent dessus. Ce que je veux dire par là est que les sciences, et le savoir humain en général, est comme un être vivant : les différentes parties s'irriguent conceptuellement les unes les autres ; certaines produisent des applications directes, d'autres non, mais s'imaginer qu'on peut amputer des parties sans ruiner la santé de l'ensemble est tout simplement stupide.

[Lire la suite…]

Le contenu de cette entrée est presque complètement inclus dans le très classique, et remarquablement bien écrit, livre de Leonard Gillman & Meyer Jerison, Rings of Continuous Functions (1960), qui contient d'ailleurs bien d'autres choses intéressantes. Mais j'en avais assez de perdre du temps à retrouver des choses contenues dans ce livre à chaque fois que je les oublie, donc je voulais me faire un aide-mémoire, et à ce moment-là autant le mettre en ligne sur mon blog, d'autant plus qu'il s'agit là de culture générale mathématique (que, selon moi, tout mathématicien devrait avoir, — au moins pour les grandes lignes de ce que je raconte, évidemment, disons les « spoilers » ci-dessous, pas les détails un peu arcanes sur les espaces d'Urysohn et les réelcompacts). Mais mon exposition est assez différente de celle de Gillman & Jerison, et pas seulement parce que le fait de ne pas donner de preuves permet de réorganiser les résultats dans un ordre parfois plus satisfaisant, mais aussi parce que j'ai cherché à développer autant que possible les parallèles entre les faits annoncés, et j'ai une approche un tout petit peu plus « catégorique ».

Comme j'ai écrit énormément de choses très rapidement, y compris des choses qui ne sont pas verbatim dans la littérature (je ne m'en éloigne guère, mais parfois je change un peu les hypothèses ou les conventions, et il faut donc adapter les énoncés : par exemple, Gillman & Jerison supposent les espaces complètement réguliers quand il s'agit de décrire le compactifié de Stone-Čech, ce qui me déplaît énormément ; parfois aussi, quand j'interpole des résultats, je fais une démonstration dans ma tête, mais je n'ai pas tout vérifié avec le soin le plus absolu), il est probable que j'aie fait un certain nombre d'erreurs. On va dire que le but du jeu est de les retrouver !

Je suppose que le lecteur sait déjà ce qu'est un espace topologique et une fonction continue entre espaces topologiques (ainsi que les autres termes de base de la topologie générale : ouverts, fermés, voisinages, intérieur, adhérence, homéomorphisme, sous-espace / topologie induite, topologie produit, espace compact [:= compact séparé], ce genre de choses — cf. par exemple ce glossaire ou différentes pages de ce wiki). Mais je ne suppose pas que le lecteur sait ce qu'est, par exemple, un espace complètement régulier. Je suppose aussi connues les notions d'anneau [sous-entendu : commutatif], ou plutôt de ℝ-algèbre [commutative], et d'idéal d'un tel anneau (et je rappelle qu'un idéal maximal d'un anneau est un idéal ≠(1) et maximal pour l'inclusion parmi les idéaux ≠(1), ou, ce qui revient au même, un idéal tel que quand on quotiente l'anneau par lui on obtient un corps).

❀

Remarque informatique : J'utilise dans ce qui suit les caractères ‘𝔪’, ‘𝔬’, ‘𝔭’, ‘ℱ’ et ‘𝒰’ pour, respectivement, un ‘m’ gothique minuscule, un ‘o’ gothique minuscule, un ‘p’ gothique minuscule, un ‘F’ cursif et un ‘U’ cursif. Comme ces caractères peuvent parfois manquer dans des polices j'ai prévu un peu de magie en JavaScript qui remplacera en un seul clic tous ces symboles par des lettres latines toutes bêtes : donc, si vous ne voyez pas les caractères que je viens de nommer, cliquez ici pour activer ce remplacement.

❀

✱ Si X est un espace topologique, on note C(X) l'ensemble des fonctions réelles continues X→ℝ, avec l'addition et la multiplication point à point (c'est-à-dire que f+g est la fonction x↦f(x)+g(x) et que f⁢g est la fonction x↦f(x)⁢g(x)) ; chaque réel c est identifié à la fonction constante x↦c dans C(X). (C'est donc un anneau commutatif et même une ℝ-algèbre commutative. On peut le munir d'autres structures, notamment un ordre partiel défini par f≤g lorsque f(x)≤g(x) pour tout x∈X, qui est d'ailleurs un treillis avec f∨g la fonction x ↦ f(x)∨g(x) := max(f(x),g(x)) et f∧g la fonction x ↦ f(x)∧g(x) := min(f(x),g(x)), et une valeur absolue |f| = f∨(−f). On peut éventuellement aussi introduire une ou plusieurs topologies sur C(X), mais ce n'est pas ce qui va m'intéresser ici ; en revanche, je souligne qu'on n'a pas de norme intéressante sur C(X).)

À côté de C(X), on a C*(X) qui est formé des fonctions réelles continues bornées c'est-à-dire les f∈C(X) telles qu'il existe un B∈ℝ tel que pour tout x∈X on ait |f(x)|≤B. Il est évident que la somme et le produit de deux fonctions bornées sont bornés, si bien que C*(X) est un sous-anneau de C(X).

On peut par ailleurs noter que C et C* sont des foncteurs contravariants des espaces topologiques vers les ℝ-algèbres commutatives, ce qui signifie que donnée une application continue h:X→Y on fabrique de façon évidente des morphismes C(Y)→C(X) et C*(Y)→C*(X) (remarquer le sens des flèches !), simplement par composition à droite par h, c'est-à-dire qu'elles envoient une fonction continue f:Y→ℝ [éventuellement bornée] sur la composée f∘h:X→ℝ. On peut noter C(h):C(Y)→C(X) et C*(h):C*(Y)→C*(X) pour ces deux morphismes de « composition à droite par h ». La « fonctorialité » signifie simplement que (i) si id:X→X est l'identité alors C(id) et C*(id) sont aussi l'identité, et (ii) si h:X→Y et k:Y→Z alors C(k∘h)=C(h)∘C(k) et C*(k∘h)=C*(h)∘C*(k).

✱ La problématique qui m'intéresse est de décrire le rapport entre l'espace X et son C(X) et son C*(X), comment on peut retrouver l'un à partir de l'autre, ce genre de choses.

Plus précisément, parmi les questions qu'il est naturel de se poser :

• La ℝ-algèbre C(X) caractérise-t-elle l'espace topologique X ? Permet-elle de le retrouver (autrement dit, si X₁ et X₂ ont « le même » C(X), c'est-à-dire que C(X₁) et C(X₂) sont isomorphes en tant que, disons, ℝ-algèbres, alors X₁ et X₂ sont-ils homéomorphes) ? Dans les cas où c'est possible, comment peut-on reconstruire X à partir de C(X) ? Par ailleurs, peut-on identifier les ℝ-algèbres qui apparaissent comme des C(X) ? Peut-on, d'ailleurs, retrouver la structure de ℝ-algèbre (i.e., les fonctions constantes et leur isomorphisme avec ℝ) à partir de celle d'anneau ?
• Mêmes questions pour C*(X).
• Quel est le rapport entre C(X) et C*(X) ? Peut-on identifier les fonctions bornées de façon purement algébrique ? Pour quel genre d'espace a-t-on C(X) = C*(X) (toutes les fonctions continues sont bornées) ? Comment les ℝ-algèbres qui apparaissent comme des C(X) se situent-elles parmi ceux qui apparaissent comme des C*(X) ? Peut-on notamment trouver un espace Xˆ (en fonction de X) pour lequel on aurait C(Xˆ) = C*(X) (ou le contraire) ?

(Digression : J'ai essayé d'écrire là les questions qu'il me semble qu'on « devrait » vraiment spontanément se poser — et donc chercher à résoudre — dès qu'on introduit ce genre de constructions, sans préjuger de celles qui ont une réponse plus ou moins intéressante. Je trouve toujours agaçants les livres qui traitent d'un sujet mathématique et qui omettent une question qui me semble « évidemment naturelle », ne serait-ce que pour dire qu'on ne connaît pas de réponse satisfaisante ou que les auteurs n'en connaissent pas.)

Quelques spoilers :

• La ℝ-algèbre C*(X) caractérise l'espace X pour les espaces compacts [séparés]. On pourra alors reconstruire X comme l'ensemble des idéaux maximaux de C*(X). Je crois qu'on ne sait pas caractériser de façon algébrique satisfaisante les ℝ-algèbres C*(X). En revanche, donné un espace topologique X, il y a un unique espace compact βX pour lequel C*(βX) = C*(X) (c'est donc un choix canonique d'espace X′ ayant ce C*(X)) : on l'appelle le « compactifié de Stone-Čech » de X. En général, dire que C*(X₁) et C*(X₂) sont isomorphes va signifier que les espaces ont le même compactifié de Stone-Čech.
• La ℝ-algèbre C(X) caractérise l'espace X pour tous les espaces dits « réelscompacts » (ce qui inclut énormément de choses, par exemple tous les espaces métriques). On pourra alors reconstruire X comme l'ensemble des idéaux maximaux de C(X) tel que le quotient soit ℝ. Je crois qu'on ne sait pas caractériser de façon algébrique satisfaisante les ℝ-algèbres C(X). En revanche, donné un espace topologique X, il y a un unique espace réelcompact υX pour lequel C(υX) = C(X) (c'est donc un choix canonique d'espace X′ ayant ce C(X)) : on l'appelle le « réelcompactifié [de Hewitt-Nachbin] » de X. En général, dire que C(X₁) et C(X₂) sont isomorphes va signifier que les espaces ont le même réelcompactifié.
• Les C*(X) sont des cas particuliers des C(X), par cela je veux dire que pour tout espace topologique X il existe un espace Xˆ pour lequel on a C(Xˆ) = C*(X), et (d'après ce qui précède) ceci caractérise complètement Xˆ si on lui impose de plus d'être compact : c'est là aussi le compactifié de Stone-Čech de X (noté βX). On peut caractériser algébriquement les fonctions bornées au sein de C(X) puisqu'on peut même caractériser l'image de f∈C(X), à savoir l'ensemble des c∈ℝ tels que f−c ne soit pas inversible dans C(X). Les espaces pour lesquels C(X) = C*(X), ou simplement pour lesquels C(X) est un C*(X′), sont les espaces dits « weierstrassiens » ou « pseudocompacts » (et c'est notamment le cas des espaces compacts).

[Lire la suite…]

Cela fait un certain temps que je me dis que je devrais écrire une ou plusieurs entrées sur ce blog sur des sujets tournant autour de la logique intuitionniste et des mathématiques constructives. La présente entrée est une sorte de TODO étendu où je mélange, de façon malheureusement confuse et désorganisée, des remarques introductives voire vulgarisatrices sur le sujet (et expliquant de quoi il est question), des remarques d'ordre méta (où je dis que je devrais parler de ceci ou de cela, ou bien me demande comment je pourrais le faire, ou encore me dis que je ne comprends pas bien telle ou telle chose) et des explications de fond assez disparates (et faites à des niveaux de prérequis, il faut bien le dire, complètement incohérents). Même l'ordre dans lequel je dis les choses est assez bizarre (à la limite, je me demande s'il ne vaut pas mieux lire cette entrée en commençant par la fin). Je pense que ça vaut quand même la peine de publier tout ça, en conseillant au lecteur de simplement sauter les passages qui lui semblent obscurs (puisque de toute façon il y a très peu de dépendances dans ce que je vais raconter).

★

En fait, au départ, je me suis surtout dit que ce serait intéressant d'écrire quelque chose sur le topos effectif et la réalisabilité de Kleene. Je peux au moins recopier l'introduction informelle que j'ai commencé à rédiger à ce sujet :

Pour dire très très très sommairement et très très très vaguement de quoi il est question,

• un topos est une sorte de « monde mathématique alternatif » régi par les lois de la logique intuitionniste (une logique plus faible que la logique usuelle, ou classique, dans laquelle on a essentiellement supprimé la loi du tiers exclu qui affirme que toute formule logique est soit vraie soit fausse, ou, de façon équivalente, que tout ce qui n'est pas faux est vrai) ; de façon un peu plus précise, un topos est une catégorie (peu importe ce qu'est exactement une « catégorie ») qui possède un certain nombre de propriétés communes avec la catégorie des ensembles, ce qui permet d'y mener un certain nombre de constructions mathématiques usuelles, mais dont le comportement va néanmoins être différent sur un certain nombre de choses, et notamment la logique ; et
• le topos effectif est un topos particulier qui présente un intérêt particulier en calculabilité : il présente un monde alternatif dans lequel toutes les fonctions ℕ→ℕ sont calculables, ce qui nous offre un regard neuf sur la calculabilité par rapport à sa présentation classique, où la logique intuitionniste éclaire ce que sont les raisonnements effectifs (voir à ce sujet cet article introductif d'Andrej Bauer, qui ne parle pas du topos effectif mais explique en quoi travailler en logique intuitionniste peut rendre plus facile ou plus naturelle la calculabilité).

Mais reculons d'un cran : pour parler du topos effectif, je me suis dit qu'il fallait d'abord que j'écrive quelque chose sur la réalisabilité de Kleene, qui en est en quelque sorte le prélude. (Si vous voulez savoir très très très sommairement et très très très vaguement de quoi il est question, S. C. Kleene a introduit dès 1945 une notion appelée « réalisabilité », en tentant de donner un sens précis à l'intuitionnisme, et — en très très très gros — le fait qu'une formule arithmétique φ soit « réalisable » [par un entier naturel n] signifie que n en apporte une sorte de « témoignage algorithmique », par exemple, si φ est une formule du type ∀x.ψ(x) affirmant que ψ(x) est vraie pour tout x, alors « réaliser » cette formule va se faire en apportant un programme qui prend en entrée un entier k et en sortie calcule un entier qui réalise ψ(k) ; pour un peu plus de détails, voir le début de cette question que j'ai posée sur MathOverflow, ou pour encore plus, voir le texte Realizability: An [sic] Historical Essay de Jaap van Oosten.) Le lien entre la réalisabilité de Kleene et le topos effectif est très fort : disons que le topos effectif est défini en cherchant une généralisation assez directe de la réalisabilité à des formules plus complexes que celles de l'arithmétique (et les formules arithmétiques qui sont réalisables sont exactement celles qui sont vraies dans le topos effectif).

Ajout : voir cette entrée ultérieure au sujet de la réalisabilité de Kleene, où je la définis proprement ; en voici depuis un sur la réalisabilité propositionnelle. Nouvel ajout : le billet sur le topos effectif est ici.

Bon, mais je me suis alors rendu compte que ce serait commencer in media res de parler du topos effectif ou même de réalisabilité si je ne commençais pas par parler d'intuitionnisme ou de mathématiques constructives. Et là, je suis embêté par le fait que j'ai à la fois trop de choses à dire et pas assez (trop, parce que ça touche à énormément de sujets ; pas assez, parce qu'en ce faisant ça touche aussi à trop de questions sur lesquelles je ne sais pas grand-chose).

Ajout : ce nouveau billet est une tentative de réécriture complète de celui qui suit, et il est peut-être plus clair (ou peut-être que les deux s'éclairent l'un l'autre, je ne sais pas).

★

La logique intuitionniste est une logique plus faible que la logique classique dans laquelle on s'interdit la loi du tiers exclu (qui dit que tout énoncé P est soit vrai soit faux ; c'est-à-dire : P∨¬P) ; cela revient essentiellement à s'interdire le raisonnement par l'absurde (ou plus exactement, le raisonnement par l'absurde de la forme je veux montrer P : supposons par l'absurde que P soit faux <…>, j'arrive à une contradiction, donc P ne peut pas être faux, c'est-à-dire qu'il est vrai — c'est la dernière partie qui coince en logique intuitionniste ; en revanche, on peut toujours dire je veux montrer que P est faux : supposons par l'absurde que P soit vrai <…>, j'arrive à une contradiction, c'est-à-dire que P est faux, parce que P est faux signifie précisément que la vérité de P est absurde). Faire des maths sans le tiers exclu peut ressembler à un exercice aussi futile qu'essayer de boxer avec les deux mains attachées derrière le dos, et dans une certaine mesure ça y ressemble effectivement, mais cela présente néanmoins un certain intérêt : non seulement c'est intéressant du point de vue de la pure logique de se demander ce qu'on peut faire sans cet axiome (et cette question a des connexions inattendue avec toutes sortes d'autres parties des mathématiques) ; mais par ailleurs, une démonstration en logique intuitionniste apporte véritablement plus de contenu qu'une démonstration classique : pour commencer, elle est valable de façon plus large (et notamment dans les topoï [pluriel de topos]), mais aussi, elle est constructive (au moins si on part de certains axiomes), c'est-à-dire qu'elle exhibe les objets dont elle affirme l'existence.

Une des idées centrales des maths constructives (qui sont à peu près, quoique pas forcément exactement, la même chose que les mathématiques exercées dans le cadre de la logique intuitionniste) est que si on veut prouver P ou Q (en symboles, P∨Q), il devrait être suffisant mais aussi nécessaire de prouver soit P, soit Q (et notamment, de savoir lequel des deux est vrai !) : ceci va manifestement complètement à l'encontre du tiers exclu qui postule que pour tout énoncé P, soit P est vrai soit ¬P l'est, sans qu'on puisse forcément trancher lequel (et parfois, effectivement, on ne peut prouver ni l'un ni l'autre). De même, si on veut prouver il existe un x tel que P(x) (en symboles, ∃x.P(x)), il devrait être suffisant mais aussi nécessaire d'exhiber un x pour lequel on peut prouver P(x) : de nouveau, ceci va à l'encontre des raisonnements par l'absurde qui ressemblent à supposons qu'aucun tel x n'existe <…>, j'arrive à une contradiction, donc un tel x doit exister (mais au final ne donnent aucune information pour en construire un).

Ajout (2019-04-15T23:37+02:00) : Juste après avoir publié cette entrée je me rends compte que j'ai oublié d'insérer un paragraphe que je comptais écrire sur l'interprétation de Brouwer-Heyting-Kolmogorov qui tente d'expliquer au moins informellement le sens des connecteurs de la logique intuitionniste. Spécifiquement, il s'agit de variations autour des explications suivantes :

• une preuve de P∧Q (conjonction) est un couple formé d'une preuve de P et d'une de Q,
• une preuve de P∨Q (disjonction) est la donnée d'une preuve de P ou d'une preuve de Q (avec, bien sûr, l'information de laquelle des deux),
• une preuve de P⇒Q (implication) est une manière de transformer une preuve de P en une preuve de Q,
• une preuve de ⊤ (le vrai) est triviale,
• une preuve de ⊥ (le faux) n'existe pas,
• une preuve de ∀x.P(x) est une manière de transformer un x en une preuve de P(x),
• une preuve de ∃x.P(x) est la donnée d'un t particulier et d'une preuve de P(t).

[Lire la suite…]

Méta : J'ai écrit un fil un peu long sur Twitter pour tenter d'expliquer le théorème de Gödel, qui reprend grosso modo des idées de cette entrée passée (au moins la partie sur Gödel de celle-ci) mais en mettant l'accent un peu différemment et donnant plus de détails sur les conditions de prouvabilité. Comme ça peut être un complément intéressant et que tout le monde n'aime pas le format Twitter, je reproduis ici ce que j'y ai dit, en reformatant un minimum (en revanche, mon style sur Twitter est sans doute un peu différent de mon style sur ce blog, et je n'ai pas le courage de reformuler plus qu'a minima) :

Je fais d'abord une tentative pour lever la confusion au sujet formalisme. Quand on formalise les [raisonnements] mathématiques, on les décrit sous forme de manipulations de suites de symboles (« syntaxe ») qui obéissent à des règles bien précises. Il est évident que si on demande que les règles de raisonnement elles-mêmes soient formalisées en mathématiques, on a une régression infinie : si quelqu'un prétend ne comprendre que ce qui est formel, c'est turtles all the way down, on ne peut rien démarrer… Pour que le bootstrap soit possible, il faut bien accepter l'idée de décrire les règles de manipulation de la logique en français, ou en faisant appel à des notions mathématiques elles-mêmes pas formalisées (mais néanmoins précises) ! (Refuser cette idée ce serait comme refuser qu'on puisse jouer aux échecs sous prétexte que les règles des échecs n'ont pas été formalisées dans ZFC. Or personne ne pense qu'on a besoin de ZFC pour jouer aux échecs !)

En revanche, ce qu'on peut faire, c'est une fois qu'on a accepté ces règles et construit un système formel avec, utiliser ce système formel pour revisiter (« refléter ») les règles, cette fois-ci formellement : autrement dit, on reconstruit tout le système qu'on a déjà construit, mais on le fait cette fois-ci à l'intérieur du système « externe » qui a été construit informellement. Il y a une mise en abyme. Je parlerai de système interne pour celui qu'on construit ainsi.

Typiquement, ça se fait avec un truc appelé codage de Gödel : si le système externe contient l'arithmétique, on dit qu'on peut refléter toutes les règles formelles comme des manipulations arithmétiques pour fabriquer le système informel. Le code de Gödel d'une formule, c'est l'entier qui représente cette formule (et qui devient, du coup, manipulable par le système externe). Du coup les énoncés comme P est prouvable (qui sont, à la base, informels, parlant du système externe) deviennent des énoncés formels du système externe et qui parlent du système interne. Des énoncés arithmétiques. (Je noterai □P plus bas pour P est prouvable.)

Et là, il y a une sorte de postulat épistémologique, qui est que ce que :

Les règles du système interne (formalisées dans le système externe) reflètent correctement les règles du système externe lui-même.

Donc si on croit que le système externe ne dit pas de conneries, et s'il dit que le système interne ne peut pas prouver <ceci-cela>, alors effectivement le système externe ne peut pas prouver <ceci-cela>. (Un ultra-formaliste pourrait rejeter ce postulat et dire : pour moi, les maths formelles sont juste un jeu typographique dénué de sens, le système externe ce sont les règles du jeu, le prétendu système interne n'a pas de sens, pas plus qu'aucun énoncé du jeu. Mais en vrai, les gens font des maths parce qu'ils croient qu'une preuve du fait que 2+2=4 apporte quelque information sur le monde réel, donc il y a bien une connexion entre le système externe, qui vit dans le monde réel, et le système interne, formalisé.)

Accessoirement, les systèmes externe et interne n'ont pas vraiment besoin d'être les mêmes : en fait on a besoin de très peu d'axiomes pour faire fonctionner Gödel. Mais je ne sais pas si ça aide de dire ça. Donc restons dans l'idée que ce sont « les mêmes ».

Maintenant, de quels ingrédients a-t-on besoin pour prouver Gödel ? On a besoin des trois « conditions de prouvabilité de Hilbert-Bernays » (que je noterai (A), (B), (C)), et de l'astuce de Quine. Expliquons ça successivement :

Les conditions de prouvabilité de Hilbert-Bernays remplacent le postulat épistémologique dont j'ai parlé plus haut par quelque chose de précis et de formel. En gros, elles font le lien entre les niveaux externe et interne (et interne², cf. plus bas).

Première chose : (A) si le système externe prouve un énoncé P, alors il prouve que le système interne prouve P [ou plutôt, le code de Gödel de P]. Pourquoi ? Parce que si on a une preuve de P, on peut « refléter » cette preuve : la réécrire comme une preuve formelle dans le système interne, et ceci fournit une preuve de son existence dans le système externe. Bien sûr, tout ce que je viens de dire est informel, puisque (A) est par essence informel ! Mais si on applique ça à un P bien précis et une preuve de P formelle explicite, la recette que je viens de dire donne une preuve tout à fait explicite et formelle (dans le système formel externe) de l'existence d'une preuve dans le système interne. Donc, si on veut, (A) est un métathéorème informel : en soi il n'est pas formel, mais il s'instancie en des théorèmes formels (du système externe) dont on a la recette de construction.

Maintenant on peut refaire tout ça avec un niveau de plus (on a alors trois systèmes : l'externe est informel, l'interne est formalisé dans le système externe, et l'interne² dans le système interne — ça s'arrêtera là) : Tout ce que j'ai dit sur le (A) vaut de nouveau et donne, cette fois, une preuve formelle (dans le système externe) du fait (B) suivant : si le système interne prouve P alors il prouve que le système interne² prouve P. Cette fois c'est un vrai théorème du système externe, pas juste un métathéorème informel.

Enfin, (C) dit que si le système interne prouve [le code de Gödel] de P⇒Q et [celui de] P, alors il prouve [celui de] Q. Ça c'est juste le fait qu'on a la règle de modus ponens dans le système interne (c'est presque une définition).

Bref, si je note □P l'énoncé (du système externe) qui dit qu'il existe une preuve de P dans le système interne, mes conditions de prouvabilité sont :

• (A) si P est un théorème alors □P en est un,
• (B) □P⇒□□P est un théorème,
• (C) □(P⇒Q)⇒□P⇒□Q est un théorème

(tous ces théorèmes dans le système externe ! et ce, quels que soient les énoncés P et Q).

Maintenant, l'astuce de Quine (en fait, le procédé diagonal), c'est quelque chose qui permet de fabriquer un énoncé G tel que G⇔¬□G (démontrablement dans le système externe !), autrement dit un énoncé qui dit je ne suis pas un théorème.

L'astuce fonctionne exactement comme la manière dont on écrit des programmes qui écrivent leur propre code, chose que j'explique en détails dans cette page web consacrée aux quines. On fabrique une formule R(x) (du système externe) qui dit si x est une formule du système interne ayant une variable libre, et qu'on remplace cette variable par le code de Gödel de x elle-même, alors le résultat n'est pas un théorème (du système interne), ou de façon encore plus informelle, R(x) signifie x(‘x’) n'est pas un théorème (soit ¬□x(‘x’)) en notant ‘x’ le code de Gödel de x. Mais du coup, R(‘R’) équivaut à R(‘R’) n'est pas un théorème (soit ¬□R(‘R’)), et c'est ça que je note G.

[Ajout par rapport au fil Twitter:] Dans la présentation informelle proposée par Hofstadter, G est en gros la phrase suivante : Si on prend le morceau de phrase suivant et qu'on le fait suivre (après deux points) de lui-même entre guillemets, on obtient quelque chose qui n'est pas un théorème : Si on prend le morceau de phrase suivant et qu'on le fait suivre (après deux points) de lui-même entre guillemets, on obtient quelque chose qui n'est pas un théorème — l'astuce est de dire cet énoncé n'est pas un théorème sans passer par une référence à cet énoncé que notre système formel ne permet pas de faire ; ceci est exactement parallèle au mécanisme des quines qui permettent de coder imprimer ce programme dans un langage qui ne permet pas une référence à ce programme.

Une fois qu'on a ces ingrédients, la preuve de Gödel est pure manipulation formelle. Tout le raisonnement est tenu dans le système externe (mais parle du système interne — voire interne² quand il y a des □□) :

Supposons □G. Alors □□G d'après (B). Mais la preuve (explicite !) de G⇒¬□G donne □(G⇒¬□G) d'après (A). Or □G et □(G⇒¬□G) donnent □¬□G par (C). Or □□G et □¬□G (i.e. □(□G⇒⊥)) donnent □⊥ d'après (C). Bref, on a prouvé □G⇒□⊥ soit ¬□⊥⇒¬□G. C'est-à-dire (qu'on a prouvé dans le système externe) que si le système interne prouve G alors il prouve ⊥ (c'est-à-dire 0=1). I.e., si le système interne est consistant (¬□⊥), il ne peut pas prouver G (soit : ¬□G)… …donc G, qui équivaut à ¬□G, est vrai ! (c'est-à-dire, est un théorème du système externe, prouvé sous l'hypothèse (¬□⊥) que le système interne est consistant. C'est le premier théorème d'incomplétude.

Maintenant, en appliquant (A) à cette preuve (explicite !) de ¬□⊥⇒¬□G, on obtient □(¬□⊥⇒¬□G) donc □¬□⊥⇒□¬□G (par (C)). Comme ¬□G⇒G donne □(¬□G⇒G) par (A) donc □¬□G⇒□G par (C), les implications □¬□⊥⇒□¬□G, □¬□G⇒□G et □G⇒□⊥ mises bout à bout donnent finalement □¬□⊥⇒□⊥, ou encore ¬□⊥⇒¬□¬□⊥. C'est le second théorème d'incomplétude : si le système (interne) est consistant (¬□⊥) alors il ne prouve pas la consistance du système interne² (¬□¬□⊥). Et comme en fait tous ces systèmes sont le même, le postulat épistémologique évoqué ci-dessus permet de lire ce théorème formel ¬□⊥⇒¬□¬□⊥ sous la forme si Peano est consistant, il ne prouve pas sa propre consistance (idem pour ZFC).

Évidemment, l'ultra-formaliste dont j'ai parlé plus haut objectera et dira que j'ai juste prouvé un énoncé cabalistique ¬□⊥⇒¬□¬□⊥ sans aucun sens dans le monde réel et qui ne dit rien sur mon système externe (lequel vit dans le monde réel). Mais si on croit que les « vrais » entiers naturels ont un sens et que Peano en dit des choses vraies, on est forcé de conclure que Peano est incomplet et ne sait pas prouver certaines choses vraies (essentiellement, il ne sait pas qu'il dit lui-même la vérité).

(Je n'ai pas de poisson d'avril à proposer cette année, mais je vous donne deux entrées pour le prix d'une.)

Même s'il a déjà été signalé hier en commentaire à cette vieille entrée, je ne peux pas ne pas écrire une petite entrée sur ce magnifique problème qui continue à narguer mon intuition — il s'agit d'un de ces cas où les mathématiques font quelque chose qui devrait être très sérieusement impossible, et j'ai beau arriver à prouver (et à comprendre la preuve intellectuellement) que c'est possible, je reste incapable de me faire intuitivement à l'idée que ça l'est. (Je sais, je sais : In mathematics you don't understand things. You just get used to them.)

Le problème est très simple (mais je l'écris de façon un peu longue pour qu'il n'y ait aucune ambiguïté sur les règles du jeu) :

Le cruel Docteur No a capturé deux mathématiciens, que nous appellerons Alice et Bob. Après avoir permis à ceux-ci de se concerter sur leur stratégie, il va les soumettre à son épreuve dont il leur communique les termes : chacun des deux pourra observer une suite binaire infinie aléatoire uniformément distribuée (c'est-à-dire une suite de 0 et 1 dont chaque terme vaut 0 ou 1 avec probabilité ½, indépendamment les uns des autres ; on peut imaginer une suite de résultats de tirages de pile ou face), les deux suites (celle qu'Alice observe et celle que Bob observe) étant indépendantes. Pour fixer les idées, mettons que les termes de chaque suite sont numérotés par les entiers naturels (0, 1, 2, 3, etc.) : appelons (A_n) la suite observée par Alice et (B_n) la suite observée par Bob. Alice et Bob ne peuvent pas communiquer entre eux (une fois finie la concertation initiale sur leur stratégie commune, mais celle-ci est antérieure à l'observation des suites). Alice, après avoir observé sa suite choisit un entier naturel a qui sera le numéro d'un terme dans la suite de Bob ; de même, Bob, après avoir observé sa suite, choisit un entier naturel b qui sera le numéro d'un terme dans la suite d'Alice. Alice et Bob gagnent (un gentil petit cadeau de la part du Docteur No) si chacun a choisi un terme valant 1 dans la suite de l'autre, c'est-à-dire, si la valeur A_b du terme de la suite d'Alice numéroté par l'entier b choisi par Bob et la valeur B_a du terme de la suite de Bob numéroté par l'entier a choisi par Alice valent tous les deux 1.

Quelle stratégie Alice et Bob peuvent-ils employer pour maximiser leur chance de gain ?

(Formellement : une stratégie d'Alice est une fonction borélienne α:{0,1}^ℕ→ℕ et une stratégie de Bob est une fonction borélienne β:{0,1}^ℕ→ℕ. La probabilité de succès est la mesure de l'ensemble des couples (A,B) ∈ {0,1}^ℕ × {0,1}^ℕ tels que A(β(B)) = B(α(A)) = 1, pour la mesure de probabilité uniforme sur {0,1}^ℕ × {0,1}^ℕ (les valeurs α(A) et β(B) sont les entiers noté a et b). Et on demande de maximiser cette probabilité.)

Remarque : Si on est gêné par les suites infinies (et c'est vrai que c'est agaçant de parler de l'observation d'une suite infinie), on peut ramener le problème à niveau fini : soit N un entier, Alice verra le résultat de N tirages de pile ou face uniformes et indépendant, Bob verra le résultat de N autres tels tirages (indépendants entre eux et indépendants de ceux d'Alice), et chacun devra choisir un entier entre 0 inclus et N exclu faisant référence à un tirage de l'autre, les deux gagnant s'ils ont choisi un tirage valant 1 chez l'autre. La situation paradoxale décrite ci-dessous est la même pour N fini que pour des suites infinies, c'est juste que les nombres sont moins ronds. (Formellement, dans le cas fini, une stratégie d'Alice est une fonction α:{0,1}^N→{0,…,N−1} et une stratégie de Bob est une fonction β:{0,1}^N→{0,…,N−1}. La probabilité de succès est la mesure de l'ensemble des couples (A,B) ∈ {0,1}^N × {0,1}^N tels que A(β(B)) = B(α(A)) = 1, pour la mesure de probabilité uniforme sur {0,1}^N × {0,1}^N.)

Une stratégie évidente consiste à ce qu'Alice et Bob choisissent tous les deux l'entier 0 (faisant référence au premier terme de la suite de l'autre). Dans ce cas, ils gagnent avec probabilité ¼, puisque chacun de A₀ et de B₀ vaut 1 avec probabilité ½, indépendamment l'un de l'autre. Choisir d'autres entiers constants (par exemple si Alice choisit 42 et Bob choisit 1729) donne toujours exactement la même chose.

L'idée intuitive qu'on a spontanément (en tout cas que j'ai eue, et dont je n'arrive toujours pas vraiment à me défaire) est qu'on ne peut pas faire mieux que ¼ :

Raisonnement incorrect : Alice et Bob ne peuvent pas communiquer, n'ont aucune information sur la suite de l'autre, et leurs deux suites sont indépendantes, donc il est impossible que l'observation de sa propre suite puisse aider Alice à faire quoi que ce soit d'utile sur la suite de Bob. Donc il n'y a rien de mieux à faire que de choisir des a et b constants (dont la valeur n'a pas d'importance).

Raisonnement incorrect (variante) : Quelle que soit la manière dont Alice choisit a, la valeur B_a vaudra 0 avec probabilité ½ et 1 avec probabilité ½ (puisque le choix de a ne peut dépendre que de A, qui est indépendant de B), et de même A_b vaudra 0 avec probabilité ½ et 1 avec probabilité ½. Puisque les suites A et B sont indépendantes et que (du coup) les variables a et b le sont, on a A_b = B_a = 1 avec probabilité ¼, et on ne peut pas faire mieux.

Et pourtant, c'est faux.

Et ce n'est même pas très compliqué de faire mieux que 1/4. Voici une stratégie simple qui donne une probabilité 1/3 de succès à Alice et Bob : Alice choisit pour a l'indice du premier 1 dans sa propre suite, et Bob choisit de même pour b l'indice du premier 1 dans la sienne. La probabilité d'avoir a=b est la somme de 1/4 (probabilité d'avoir a=b=0) plus 1/4² (probabilité d'avoir a=b=1) plus 1/4³ (probabilité d'avoir a=b=2), etc., c'est-à-dire la somme des 1/4^k, qui vaut 1/3 ; et lorsque c'est le cas, par construction, A_b = B_a = 1 ; par ailleurs, si a≠b, alors Alice et Bob perdent (par exemple, si a<b, on a B_a = 0 puisque b est l'indice du premier 1 dans la suite B). Donc la probabilité de succès de cette stratégie est exactement 1/3.

J'ai beau avoir écrit cette preuve. Je n'arrive vraiment pas à me faire une idée intuitive de comment il est possible que cette stratégie fonctionne.

Mais je peux quand même dire ceci : la raison pour laquelle les raisonnements ci-dessus (tendant à « prouver » l'impossibilité) sont incorrects, c'est que s'il est bien vrai que chacun de A_b et B_a vaut 0 ou 1 avec probabilité ½, ils ne sont pas indépendants (puisque a dépend de A et b de B), et plus exactement, Alice et Bob peuvent s'arranger (et c'est ce qu'ils font dans la stratégie ci-dessus) pour que les deux événements A_b = 1 et B_a = 1 soient corrélés. Autrement dit, si on ne peut pas améliorer la chance d'avoir A_b = 1, on peut au moins s'arranger pour que, lorsque c'est le cas, ceci apporte des informations sur a ou sur B qui font que B_a = 1 a plus de chances de se produire. Je continue à trouver ça peu clair intuitivement, mais c'est déjà ça.

Maintenant, ce qui est amusant (et presque un peu décevant ?), c'est que cette jolie stratégie donnant 1/3 n'est toujours pas optimale : comme il est expliqué sur le fil MathOverflow lié au début de cette entrée (dans la réponse de mihaild), on peut faire 7/20 (c'est-à-dire 35%). Mais on ne sait pas si c'est optimum, et on n'a pas (au moment où j'écris, d'après de fil de discussion) de borne supérieure autre que le ½ évident.

Référence croisée : ce fil Twitter.

Mise à jour (2019-04-04) : La borne supérieure a été améliorée à 3/8 dans le fil MathOverflow avec un argument très simple (quand j'aurai le temps, j'essaierai de mettre à jour ce paragraphe pour le donner). Par ailleurs, il apparaît que problème était déjà discuté (de façon un peu généralisée) dans ce papier, qui prouve une borne supérieure de 3/8, et annonce mais sans preuve une borne supérieure de 81/224.

Complément (2019-04-07) : Pour la complétude de cette entrée, je reproduis en la paraphrasant la preuve de la borne supérieure par 3/8 de la probabilité de succès. Si on note a l'entier choisi par Alice et a′ l'entier qu'elle choisirait avec la même stratégie si elle observait la suite (1−A_n) au lieu de (A_n) (i.e., si on échange les 0 et 1 dans ce qu'Alice observe), et de même b et b′ pour Bob, alors on peut remarquer que l'espérance E(A_b B_a) de A_b B_a (qui est la probabilité de succès p qu'on cherche à maximiser) est aussi égale à l'espérance de (1−A_b′) B_a (puisque 1−A est une variable distribuée comme A et toujours indépendante de B) ou de A_b (1−B_a′) ou encore de (1−A_b′) (1−B_a′). La somme de ces quatre espérances (qui est 4p) est donc l'espérance de (A_b+1−A_b′) (B_a+1−B_a′), soit 4p ≤ E((A_b+1−A_b′) (B_a+1−B_a′)) = 1 + E(A_b−A_b′) + E(B_a−B_a′) + E((A_b−A_b′) (B_a−B_a′)) soit encore 1 + E((A_b−A_b′) (B_a−B_a′)) puisque E(A_b) = E(A_b′) et E(B_a) = E(B_a′) (en fait, chacune de ces quatre espérances vaut ½). Enfin, comme A_b−A_b′ vaut +1 ou −1, l'espérance E((A_b−A_b′) (B_a−B_a′)) est majorée par E(|B_a−B_a′|), elle-même majorée par ½ (si i≠j alors E(|B_i−B_j|)=½). Au final, on a prouvé 4p≤1+½, soit p≤3/8 comme annoncé.

Je traîne depuis longtemps l'idée de vulgariser quelques notions de logique linéaire. Du point de vue de la vulgarisation, la logique linéaire a ceci de sympathique que c'est quelque chose mathématiquement à tellement « bas niveau » que je n'ai besoin de présupposer aucune sorte de connaissance mathématique préalable pour en parler : en principe, on peut la considérer comme un pur petit jeu syntactique dont les règles ne sont pas très compliquées — même si, présenté sous cette forme, il risque de ne pas apparaître comme très intéressant, et même s'il est bon d'avoir du recul pour avoir une idée de quelles règles appliquer à quel moment, la compréhension des règles elles-mêmes ne nécessite pas de savoir particulier. Du point de vue personnel, la logique linéaire est quelque chose qui me frustre beaucoup parce que, d'un côté, je la trouve extrêmement élégante et joliment symétrique, de l'autre, à chaque fois qu'elle semble avoir une application ou une interprétation quelque part, on se rend compte qu'il y a une note en bas de page qui fait que ce n'est pas vraiment la logique linéaire (il y a par exemple un axiome en plus, ou un connecteur en moins, ou seulement un fragment du système, ou quelque autre variation), et l'élégance est rompue ; et aussi, pour cette raison, l'intuition qu'on peut se former est brouillée.

De quoi s'agit-il ? D'un système formel inventé par le logicien français Jean-Yves Girard en 1987. J'avoue ne guère avoir d'idée de ce qu'il voulait faire avec, parce que les textes de Girard sont… un peu inhabituels… bourrés de mots qu'il ne définit pas, de références cryptiques, et de blagues dont on se demande si ce sont des blagues (comme l'intervention insistante du brocoli dans beaucoup de ses papiers). Mais depuis, elle a trouvé diverses applications et connexions : en logique, en informatique théorique ou plus appliquée, en algèbre et théorie des catégories, en théorie des jeux et même en physique quantique (sauf qu'à chaque fois, comme je le dis ci-dessus, il y a quelque chose en plus ou en moins) ; mais je ne compte pas essayer de décrire ces applications et connexions, qui sont pourtant sans doute ce qu'il y a de plus intéressant dans l'histoire, parce que je n'ai pas l'espace ni le temps pour ça.

Bref. Avant d'expliquer quelles sont les règles du jeu, il faut que j'essaye de donner une idée de ce dont il s'agit (en agitant les mains). On parle de logique linéaire, et il s'agit effectivement d'une généralisation de la logique classique, mais ce terme risque de donner une impression tout à fait fausse, et on devrait peut-être plutôt s'imaginer que ça s'appelle formalisme d'échanges ou synallagologie universelle ou quelque chose de ce genre (le seul problème du mot synallagologie est que personne ne sait ce qu'il veut dire puisque je viens de l'inventer… mais à part ça, il est parfait). La différence essentielle est la suivante : en logique usuelle, si on fait un raisonnement tendant à démontrer une conclusion X à partir d'hypothèses A, B et C, disons, on peut utiliser librement A, B et C dans le cours du raisonnement, chacune aussi souvent qu'on veut (on peut aussi, d'ailleurs, ne pas du tout utiliser une hypothèse) ; la logique linéaire, pour sa part, exige que chacune des « hypothèses » (qu'il vaut mieux, du coup, ne pas considérer comme des hypothèses) soit utilisée une et une seule fois : on ne peut ni les multiplier ni les faire disparaître (évidemment, il y aura des moyens de marquer des hypothèses spéciales qu'on peut multiplier et/ou faire disparaître, mais ce n'est pas le cas par défaut) ; dans ces conditions, il vaut mieux, donc, considérer qu'on n'a pas du tout à faire à une logique, à des raisonnements et à des hypothèses et conclusions, mais à des échanges (gestion de ressources abstraites, transactions économiques, réactions chimiques, que sais-je encore) qui ont des entrées (réactifs) et des sorties (produits), ou quelque chose comme ça. Par exemple, la logique linéaire pourrait concevablement servir à formaliser des contrats financiers (j'avais déjà évoqué quelque chose de ce genre), mais il ne faut pas s'imaginer que la logique linéaire elle-même dira grand-chose d'intéressant : de même que la logique classique ne fournit que le langage le plus basique au-dessus duquel on peut bâtir des raisonnements (il faut ajouter des axiomes intéressants pour obtenir quelque chose d'intéressant), la logique linéaire n'est qu'un cadre, en lui-même extrêmement primitif pour possiblement décrire des échanges.

[Lire la suite…]

Le Docteur No est de retour ! Il était plutôt occupé ces derniers temps à résoudre des problèmes informatiques, mais le voilà revenu et qui s'adonne à son passe-temps favori qui consiste à capturer des mathématiciens pour les soumettre à des énigmes idiotes (voir ici pour des épisodes précédents) :

Le cruel Docteur No a capturé 100 mathématiciens pour les soumettre à une épreuve démoniaque. Après avoir permis aux mathématiciens de se concerter initialement, il va placer sur la tête de chacun d'entre eux un chapeau portant un nombre entier entre 1 et 100 (inclus) de façon que chacun puisse voir le nombre porté par les chapeaux de tous les autres mais pas le sien. Les mathématiciens n'ont aucune information sur la manière dont les numéros seront attribués et il peut parfaitement y avoir des répétitions. Les mathématiciens n'auront plus le droit de communiquer à partir du moment où la distribution des chapeaux commence. Chacun devra émettre un avis sur le numéro qu'il pense que son propre chapeau porte : ces avis seront émis par pli secret et connus du seul Docteur No (i.e., les mathématiciens ne connaissent pas les réponses fournis les les autres). Le Docteur No est plutôt clément aujourd'hui : il libérera les mathématiciens si au moins l'un d'entre eux a fourni une réponse correcte (i.e., deviné le numéro que porte son chapeau) ; dans le cas contraire, il tuera tous les mathématiciens avec ses tortures particulièrement raffinées.

Les mathématiciens pourraient évidemment tous répondre au hasard (auquel cas ils auraient 63% de chances d'être libérés ; je laisse ça aussi en exercice mais ça n'a pas vraiment de rapport avec le problème). Mais en se concertant, ils peuvent s'arranger pour être certains d'être libérés : comment font-ils ?

La solution est simple, mais on peut perdre beaucoup de temps en cherchant dans la mauvaise direction. Je tire ça d'ici (la réponse est indiquée en rot13 dans un commentaire en-dessous) ; ce fil contient d'ailleurs un certain nombre d'autres devinettes rigolotes.

Ajout : voir ici, peut-être là, et encore là pour plus d'énigmes du Docteur No.

⁂

Sinon, voici un autre problème (pas vraiment une énigme), qui n'a absolument aucun rapport avec celui qui précède si ce n'est qu'il est venu à ma connaissance autour du même moment (il est inspiré de cette question mais c'est une variante assez différente du même genre d'idées) :

On considère n+1 objets et deux joueurs (Alice et Bob). Chacun des deux joueurs a un ordre de préférence (strict) sur les objets, et ces ordres de préférence sont connus de l'un comme de l'autre. Ils vont jouer au jeu suivant : chacun, tour à tour, va éliminer un objet, jusqu'à ce qu'il n'en reste plus qu'un (après n tours, donc). Ce dernier objet est gagné par les deux joueurs (i.e., ils se le partagent, ou si on préfère on peut dire qu'il y en a deux copies et que chacun en reçoit une, bref, chacun cherche à maximiser la valeur qu'il accorde à l'objet restant). Le jeu est à information parfaite (les deux joueurs savent tout : ce que l'autre joueur veut, et ce qu'il fait). Quelle stratégie vont-ils appliquer (en fonction des deux ordres de préférence) ? Et comment peut-on prédire efficacement l'objet final ?

On peut le formaliser plus précisément ainsi : soient 1,…,n les objets, triés dans l'ordre de préférence d'Alice (du moins préféré au plus préféré), et soient σ(1),…,σ(n) les valeurs de préférence de Bob pour les objets dans cet ordre, où σ est une permutation de {1,…,n} (c'est-à-dire qu'il aime le moins l'objet σ⁻¹(1) et qu'il préfère σ⁻¹(n)). Alice va jouer la stratégie qui cherche à maximiser la valeur i du dernier objet restant, tandis que Bob va jouer la stratégie qui cherche à maximiser σ(i) : on demande comment calculer i en fonction de σ et comment Alice doit calculer son premier coup. (On peut évidemment procéder de façon inductive : chaque coup possible d'Alice se ramène à un jeu de même nature avec un objet de moins et les rôles des joueurs échangés, mais ce que je demande c'est si on peut faire mieux ou plus simple.)

À titre d'exemple, si n=2 et que les préférences d'Alice sont 1<2<3, selon les valeurs (σ(1),σ(2),σ(3)) des préférences de Bob pour ces trois objets l'objet choisi est 3 (le préféré d'Alice) dans tous les cas sauf si (σ(1),σ(2),σ(3)) vaut (2,3,1) ou (3,2,1) (i.e., si l'objet préféré d'Alice est celui que Bob aime le moins), auquel cas l'objet choisi est 2 (le deuxième préféré d'Alice). C'est assez intuitif.

Il se peut que la réponse soit très facile : je n'ai pas pris le temps d'y réfléchir (trop occupé que j'étais à coudre des numéros sur des chapeaux).

On pourrait aussi demander ce qui se passe si l'un des joueurs joue la stratégie « gloutonne » (consistant à éliminer à chaque coup son objet le moins préféré), selon que l'autre joueur le sait ou selon que l'autre joueur croit toujours qu'il jouera désormais de façon rationnelle. On pourrait aussi jouer à changer l'alternance des coups entre Alice et Bob (plutôt que de les faire alterner mécaniquement) et chercher l'ordre le « plus équitable » dans un sens qu'il faudrait formaliser. Bon, bref, je trouve l'idée générale du jeu intéressante, mais je ne sais pas quelle est la bonne question à poser (c'est peut-être ça la question, en fait : trouver la question la plus intéressante à poser sur ce jeu).

L'an dernier, j'ai eu l'honneur de déjeuner avec Jean-Pierre Serre, et nous avons discuté entre autres de la rédaction des mathématiques. (Comme Serre est à mon avis — et je suis loin d'être le seul à le penser — un des mathématiciens dont le style de rédaction est le plus parfait qui soit, c'était évidemment très intéressant pour moi d'entendre ce qu'il avait à dire. Je recommande d'ailleurs de regarder cet exposé où il dénonce beaucoup de mauvaises habitudes dans ce domaine.)

Il a beaucoup insisté sur l'importance d'écrire des énoncés justes : c'est-à-dire notamment, si un énoncé P(n) est vrai pour tout n≥1, de bien écrire pour tout n≥1 et de ne pas laisser le lecteur penser que P(0) puisse être vrai lorsqu'il ne l'est pas (et c'est encore pire quand l'énoncé commence à être vrai à 2 ou 3, voire au-delà). Je savais déjà qu'il accordait beaucoup d'importance à ça[#]. Mais comme je mentionnais les codes correcteurs d'erreurs, il a fait cette autre remarque que je trouve tout à fait digne d'être érigée en maxime, à savoir qu'il essayait d'écrire les mathématiques comme un code correcteur d'erreurs (je n'ai malheureusement pas noté la phrase exact qu'il a employée, mais ça fait peut-être justement partie du phénomène souligné). Ce qu'il voulait dire est qu'inévitablement, dans une rédaction mathématiques, il y aura des choses qui seront mal lues : soit que l'auteur lui-même fasse un lapsus, soit que le manuscrit soit mal retapé, soit que l'imprimeur change certains symboles, soit que le lecteur lise mal ou ait une convention différente sur certaines choses : il faut essayer d'écrire de manière à rendre le texte relativement robuste par rapport à ces erreurs (pour qu'elles soient détectables ou, encore mieux, corrigeables).

[#] Plusieurs fois j'ai assisté à un séminaire où Serre était dans l'assistance[#2], où l'orateur commence énonce un théorème et où Serre s'exclame mais c'est complètement faux ! ce n'est pas possible, ça ! — alors là, l'orateur, visiblement paniqué, se demande si Serre vient de trouver en direct un contre-exemple au théorème principal, et au bout d'un moment de confusion on comprend que Serre protestait contre le fait que l'énoncé était trivialement faux pour n=0. Moment sans doute très désagréable pour l'orateur, mais je pense qu'après ça on apprend très vite à se demander si pour tout n veut vraiment dire tout n.

[#2] Tiens, puisque j'en suis à raconter des anecdotes à son sujet[#3], un jour j'ai assisté à un séminaire où l'orateur a commencé à parler du groupe de Serre comme si tout le monde savait évidemment de quoi il s'agissait (je sais que c'était dans un contexte de représentations galoisiennes, mais moi-même je n'avais aucune idée de ce que c'était censé être). L'éponyme a levé la main pour demander qu'est-ce que le groupe de Serre ?. La morale, là, et je pense aussi que l'orateur l'aura bien retenue, c'est que même quand on parle à une assistance de gens très distingués, il faut être très conservateur dans ce qu'on suppose que tout le monde connaît.

[#3] Allez, une troisième pour la route. Quand j'ai écrit cet article avec mon directeur de thèse, ce dernier l'a envoyé à Serre pour lui demander son avis avant publication. Entre autres remarques, il a relevé le bout de phrase par récurrence sur le naturel k et a commenté ce n'est sûrement pas vous [Colliot-Thélène] qui avez écrit ça : de fait, c'est moi qui l'avais rédigé ce passage. (L'objection est que Serre n'aime pas qu'on écrive un naturel pour un entier naturel. Je vous rassure, ses autres remarques sur l'article étaient beaucoup plus intéressantes.) Colliot-Thélène a regardé dans le petit Robert, qui recense bien quelque part naturel comme nom masculin dans le sens de entier naturel, et nous avons décidé de laisser la phrase comme ça. Mais depuis, je fais plus attention à écrire généralement un entier naturel plutôt que juste un naturel (sauf quand j'ai l'impression que le second allège vraiment la phrase).

[Lire la suite…]

Dans cette entrée, je vais commencer par parler de maths, mais ensuite je veux me servir de ce que j'aurai raconté pour soulever une question de philosophie (ou peut-être, de psychologie) des maths. Ces deux parties n'ont pas vraiment de rapport sauf que la première sert d'illustration pour la seconde : on doit pouvoir sauter la première partie (ou la lire en diagonale) et quand même comprendre quelque chose à la seconde, enfin, j'espère. (Mais bon, je ne suis pas content de ce que j'ai écrit dans la seconde partie, donc ça n'a peut-être pas d'intérêt.)

*

Je racontais récemment que le nombre 24 était particulièrement magique à cause de l'existence de certains objets exceptionnels, notamment le réseau de Leech en dimension 24 (défini dans l'entrée en question). Maintenant, considérons le fait suivant (problème des boulets de canon, conjecturé par Édouard Lucas autour de 1875 et démontré par George Watson en 1918) :

L'équation 0² + 1² + ⋯ + n² = m² a exactement trois solutions, à savoir quand (n,m) vaut (0,0), (1,1) ou (24,70). Autrement dit, à part les deux cas triviaux (0²=0² et 0²+1²=1²), la seule situation où la somme des carrés des premiers entiers naturels est encore un carré est donnée par 0² + 1² + ⋯ + 24² = 70².

(La somme 0²+1²+⋯+n² vaut encore n·(n+1)·(2n+1)/6, mais si on écrit l'équation comme n·(n+1)·(2n+1) = 6m², on ne voit pas vraiment pourquoi elle est intéressante.)

Ce n'est pas très facile à montrer, mais ce n'est pas ça qui m'intéresse.

On pourrait dire que le fait que la somme des carrés des entiers naturels jusqu'à 24 est un carré (et qu'à part les cas triviaux c'est le seul) est une propriété remarquable du nombre 24. Pas franchement passionnante, mais bon. Mais a priori, on se dit que cette propriété n'a aucun rapport particulier avec les propriétés magiques du nombre 24 que j'ai évoquées dans mon autre entrée.

Sauf qu'en fait, si.

[Lire la suite…]

S'il y a un nombre magique en mathématiques, c'est bien 24. (Je pense que Douglas Adams a juste inversé les chiffres.) Le nombre 8 vient presque à égalité, et 12, peut-être 6 et 16 ont aussi quelques propriétés magiques (qui, globalement, sont toujours liées à celles de 24), mais celui qui est vraiment farabuleux (pardonnez le néologisme), c'est 24.

Je voudrais dans cette entrée essayer de témoigner de la magie de 24 en définissant deux et en évoquant le troisième de trois objets exceptionnels qui font que 24 est si spécial. On pourrait aussi les appeler les trois générations de « magiciens » qui tirent leur pouvoir magique du nombre 24. Ces objets sont : le code de Golay binaire (première génération), le réseau de Leech (deuxième génération), et le module de Moonshine (troisième génération). Mon but est donc d'en parler un peu, en définissant proprement les deux premières générations, en essayant que ce que je dis sur la première soit accessible à un très large public, et en disant quelques mots de la troisième. Ou du moins, mon but était tout ça, parce que je me suis pas mal embourbé et je ne suis pas du tout content de ce que j'ai écrit : je donne certes une définition du code de Golay binaire et du réseau de Leech, mais je crois ne pas avoir du tout réussi à passer l'idée de pourquoi ils sont intéressants au fond. Et comme souvent, je crois que je me retrouve à présupposer de mon lecteur un niveau de connaissances mathématiques préalables qui varie de façon assez incohérente d'un endroit à l'autre (au début je m'efforce vraiment de ne rien supposer, et à la fin, il sera certainement nécessaire d'avoir au moins une intuition de ce qu'est un groupe). Néanmoins, maintenant que tout ça est écrit, je ne vais pas ne pas le publier, donc prenez-le pour ce que ça vaut.

Comme par ailleurs, le nombre 8 est aussi magique (quoiqu'un peu moins que 24), je peux aussi parler de deux des trois[#] générations de magiciens qui tirent leur pouvoir magique de celui-ci : le code de Hamming de longueur 8 et le réseau E₈, parce qu'ils sont utiles pour approcher leurs analogues du nombre 24.

[#] Je crois que le troisième qui complète la série serait l'algèbre d'opérateurs de sommets dont Griess parle dans son article A vertex operator algebra related to E₈ with automorphism group O⁺(10,2), mais je ne comprends décidément pas bien tout ça.

Bref, le tableau à garder en tête (juste pour le plan : je vais expliquer ce que tout ça veut dire) est quelque chose comme :

Le terme de génération évoque l'idée que les objets de la deuxième génération se définissent en termes de ceux de la première, et ceux de la troisième en termes de ceux de la deuxième, et qui plus est, il y a une certaine similarité entre la manière dont ces objets s'enfantent les uns les autres (je ne prétends pas que c'est rigoureusement la même, ni entre les colonnes, ni entre les lignes : notemment, il n'y a pas de « foncteur » dans l'affaire, juste une certaine analogie).

Je vais aussi évoquer, à chaque fois, les groupes de symétrie de ces différents objets, qui ressembleront à la numérologie suivante (là aussi, je dois expliquer ce que sont ces machins, mais à chaque fois, je donne le nom du groupe de symétrie et son ordre, c'est-à-dire le nombre de symétries) :

Plan de la suite :

• Le code de Hamming de longueur 8
• Le code de Golay binaire
  • L'hexacode
  • Le MOG et le code de Golay
  • Le groupe de Mathieu M₂₄
• Le réseau E₈ et le réseau de Leech
  • Définitions
  • Quelques propriétés de ces réseaux
  • Symétries de ces réseaux
• Quelques mots sur le module de Moonshine

[Lire la suite…]

Les chasseurs-prouveurs se rassemblaient comme chaque soir autour de l'équation de la chaleur et se racontaient les histoires de leurs aventures. Joueur-Atlas, qui était célèbre pour avoir autrefois attrapé un groupe parfait à 8 315 553 613 086 720 000 éléments évoqua le fils de « son » groupe, dont il avait aperçu la silhouette monstrueuse, à la lumière de la lune, en train de remuer près du nombre 196 883, et qu'il espérait voir un jour capturé. Mais ce soir, c'était au tour du vieux Bâtisseur-Alternatif de prendre la parole.

— Un jour, j'ai vu un corps comme je n'en avais jamais vu auparavant.

Il désigna une figure rupestre qu'il avait exécutée il y a longtemps, à la craie sur le tableau noir du Hilbertraum : un F pas tout à fait gras finissant par un 1 plutôt bas. Et il conclut théâtralement :

— Figurez-vous que ce corps n'avait qu'un seul élément.

Certains soupiraient d'entendre Bâtisseur-Atlernatif raconter toujours la même histoire à dormir debout, mais les jeunes chasseurs-prouveurs étaient fascinés :

— Un corps à un seul élément ? Mais ce n'est pas possible, grand-père !

— Pourtant je l'ai bien vu. Et attendez, ce n'est pas le plus incroyable… il était… sous l'anneau des entiers !

Cette révélation fit place à un silence choqué de la part de ceux qui n'avaient pas encore entendu cette légende. Un corps caché sous l'anneau des entiers ! Cela semblait si impossible — et en même temps si prometteur !

⁂

Bon, trêve d'humour à 1/1728 zorkmids.

Ce que j'appelle licorne mathématique, c'est un objet mathématique dont on aimerait croire à l'existence, un objet dont on a une certaine intuition et même des indices suggérant sa présence, qui, naïvement envisagé tel quel, n'existe pas, n'est pas possible, conduit à des paradoxes et des contradictions. On peut démontrer qu'il n'existe pas, que les propriétés qu'on lui attribue sont impossibles, et pourtant, on cherche quand même un moyen de le faire exister.

Ce qui fait que les licornes sont des licornes, c'est qu'on n'a pas trouvé la bonne définition ou la bonne théorie-cadre. Chasser la licorne, c'est donc chasser la définition ou la théorie qui lui permettra d'exister et de faire disparaître les paradoxes. Cela peut sembler bizarre : si on s'imagine qu'on donne naissance à un objet mathématique en le définissant, comment peut-il y avoir des objets qu'on poursuive sans parvenir à les définir ? Pourtant, cela se produit assez souvent (et je prends même ça pour un indice — certes pas terriblement concluant — dans le sens que les mathématiques existent indépendamment de l'homme).

*

L'exemple le plus simple est sans doute celui des nombres complexes. La manière dont je vais l'évoquer prend des libertés avec l'Histoire, qu'on m'en pardonne, mais mon but n'est past de raconter l'histoire des maths mais d'expliquer le concept d'une licorne. La racine carrée de −1, donc, était une licorne : un nombre qui, multiplié par lui-même, donne −1, c'est impossible a priori. Et on a une preuve de cette impossibilité : à savoir, que x soit positif ou négatif, son carré x² = x·x est forcément positif, donc ne peut jamais valoir −1. Bref, √(−1) est une licorne. Pourtant, quelqu'un prétend avoir vu des traces de la licorne : si on fait comme si elle existait, si on oublie cette impossibilité, si on mène les calculs comme si la racine carrée des nombres négatifs avait un sens, on arrive à résoudre des équations du troisième degré qu'on ne savait pas résoudre autrement (celles qui ont trois racines). Comment expliquer que quelque chose d'impossible conduise à une conclusion heureuse ? C'est cela qui fait soupçonner que la licorne existe vraiment, et qui donne envie de la capturer.

Maintenant on ne voit plus du tout que cette histoire a été une licorne : maintenant, √(−1) est un nombre complexe, quelque chose de tellement banal qu'on en oublie trop facilement que cela a pu représenter un paradoxe, une licorne. Pourtant, pour capturer cette licorne, il a fallu faire un saut conceptuel : abandonner l'idée que les nombres soient ordonnés, c'est un saut conceptuel gigantesque (les nombres ont été faits pour être ordonnés, pourrait-on dire ; les opérations algébriques sont une sophistication ajoutée sur le concept de comparaison). Mais une fois fait le saut conceptuel, une fois définie la notion de nombre complexe, la licorne est capturée, elle perd tout son mystère, on s'aperçoit que la définition antérieure de nombre était restrictive (ce qui ne signifie pas qu'elle n'ait pas de valeur !, il n'est pas question de remplacer systématiquement les nombres réels par des nombres complexes en mathématiques ou ailleurs).

Ce qui m'intéresse dans cette histoire, c'est la démarche où d'abord on aperçoit des traces de pas qui semblent paradoxales (cette bestiole marche comme un cheval, pourtant elle semble avoir une corne !), on traque le concept, et on finit par capturer la licorne, c'est-à-dire résoudre le paradoxe, rendre possible ce qu'on avait démontré impossible, en contournant l'impossibilité par une définition élargie. La licorne se capture par la définition. C'est inhabituel par rapport à la pratique générale des mathématiques qui consiste à chasser les preuves, pas les définitions (ni les licornes).

Méta : Dans la suite, je vais évoquer quelques autres licornes. Ne sachant pas à quel niveau de vulgarisation me placer, je n'ai pas vraiment pris de décision cohérente à ce sujet, et je suppose donc de la part de mon lecteur des connaissances variables de paragraphe en paragraphe : j'espère néanmoins avoir fait en sorte qu'on puisse comprendre un petit peu l'idée générale même si on ne comprend pas tel ou tel passage. D'autre part, comme mon but était de raconter une histoire plus que d'exposer des maths, il se peut que je dise des choses un peu abusées ici ou là (j'espère quand même avoir toujours été assez vague pour qu'on ne puisse pas m'accuser d'avoir écrit un énoncé indiscutablement faux, mais si c'est le cas, je mettrai la faute sur les licornes qui m'ont poussé).

[Lire la suite…]

À l'approche de la rentrée, je me dis qu'il peut être utile que je publie quelques conseils pour les étudiants en maths. Ceux-ci sont inspirés à la fois de ce que j'ai écrit dans ce fil Twitter et de ce que j'ai expliqué de vive voix à un élève de prépa qui me demandait de tels conseils : ayant ainsi un peu réfléchi à ce que j'avais à dire, autant le mettre sur ce blog.

Il s'agit là de conseils généraux (et sans doute d'une bonne dose de proverbial enfonçage de portes ouvertes à ma fidèle hache bénie +2 trempée dans la potion de banalités), s'adressant plutôt à des étudiants entre approximativement ce qui correspond, dans le système éducatif français, aux niveaux bac à bac+5 (disons) : grosso modo, avant ça, on ne fait pas tellement de maths au sens « raisonnement déductif » (ayant la démonstration comme méthode essentielle) ; et après, si vous en êtes arrivé là, vous avez assez de familiarité avec les mathématiques pour ne pas avoir besoin de mes conseils. Certaines des choses que je vais dire s'appliquent à d'autres disciplines adjacentes, comme la physique ou l'informatique (pour ce qui est de l'informatique théorique, mon avis est qu'il s'agit de toute façon d'une branche des mathématiques, même si elle ne s'assume pas toujours comme telle) ; quelques uns s'appliquent sans doute à n'importe quelle discipline, mais je me focalise quand même sur les maths.

On doit pouvoir tirer de ces conseils aux étudiants quelques conseils pour les enseignants (en appliquant la dualité étudiant-enseignant et le foncteur de réduction des platitudes), mais comme je n'aime pas donner des leçons à ce sujet, je vais laisser ça en exercice au lecteur.

✱ Conseil nº1 : aimer ce que l'on fait. C'est peut-être un peu idiot de dire ça, mais je suis persuadé qu'on ne peut correctement faire des maths que si on les trouve un minimum belles et intéressantes. Si on les conçoit comme une corvée, elles le resteront. Si on les conçoit comme (la métaphore que j'aime bien utiliser) l'exploration d'un palais magnifique et incompréhensiblement gigantesque, à la structure à la fois labyrinthique et élégante, on peut arriver à comprendre que ce soit à la fois excitant et séduisant, et en tirer la motivation nécessaire à leur étude.

Je ne peux évidemment pas donner de recette magique pour comprendre que les maths sont belles. C'est quelque chose que j'essaie de communiquer, mais il est évident que je ne vais pas transformer tout le monde en matheux. Mais, même si on a un a priori négatif (et certaines formes d'enseignement des mathématiques laissent hélas place à bien peu d'autre que la corvée rébarbative), il est au moins essentiel de garder l'esprit ouvert à cette possibilité, que les maths puissent être fascinantes. Je pense qu'il est au moins utile, même si on est réfractaire, de chercher les sous-domaines sur lesquels on accroche un peu plus, et de peut-être chercher à se renseigner sur l'allure générale du paysage mathématique, méditer sur la question de pourquoi certaines personnes y trouvent goût (est-ce qu'on a reçu une image déformée par un enseignement rébarbatif ou est-ce qu'on est véritablement hostile aux mathématiques ? dans ce dernier cas, il vaut certainement mieux arrêter de les étudier le plus rapidement possible et ne pas céder aux sirènes qui promettent une meilleure carrière ou quelque chose de ce genre). L'histoire des sciences peut aussi être une passerelle vers un intérêt pour les mathématiques elles-mêmes.

✱ Conseil nº1b : faire preuve de curiosité intellectuelle, et questionner ce que l'on fait. Apprendre le cours pour le cours est la meilleure garantie d'en rester là. Pour comprendre un cours de maths, il faut plutôt le questionner[#], le décortiquer, essayer de prendre du recul. Pour ça, le mieux est de garder à l'esprit toutes sortes de questions (pourquoi fait-on ça ?, où veut-on en venir ?, comment fonctionne cet objet ?) ; je vais donner des exemples plus précis de telles questions (à se poser à soi-même ou à poser à l'enseignant) dans les conseils suivants, mais le message plus général est que tout questionnement est bienvenu (voir aussi les conseils nº6 et 6b ci-dessous).

[#] Dans un cours de langue, si un étudiant demande pourquoi 95 en français de France se dit-il quatre-vingt-quinze ?, on ne peut pas vraiment lui donner de réponse sauf des choses comme c'est comme ça ou c'est un accident historique, peut-être accompagnées d'une histoire du phénomène (mais c'est déjà empiéter des langues sur la linguistique, et ça n'aidera pas tellement à l'apprentissage du français). L'enseignant en maths, lui, doit être prêt à se justifier de plus près que ça.

[Lire la suite…]

Il y a des des figures que je me retrouve à refaire encore et toujours, à chaque fois que je veux réfléchir à un certain sujet. Parmi ceux que je reproduis avec une fréquence qui finit par devenir vraiment pénible, il y a ceux qui apparaissent ci-contre à droite, et que je me suis enfin de sorti les doigts du c** pour produire en PDF avec TikZ (suivez le lien pour le PDF). Comme je ne suis certainement pas le seul trouver ces figures utiles pour réfléchir, je les mets en ligne. Et du coup, je peux en profiter pour faire un peu de vulgarisation sur ce qu'ils représentent.

Je vais essayer d'expliquer ça sous l'angle de la géométrie euclidienne élémentaire, à travers la question de classifier et de comprendre les kaléidoscopes (simpliciaux). L'intérêt, outre que c'est peut-être plus parlant, est ne pas supposer que qui que ce soit ait lu mon récent rant interminable sur les groupes de Lie (mais en même temps, essayer de dire les choses de manière à quand même éclairer le rant en question). En fait, après coup, je ne suis rendu compte que ce n'était pas forcément une très bonne approche, et que cette entrée ressemble beaucoup à une accumulation de faits qui partent dans tous les sens et qui ne reflètent pas bien (pun unintended) l'élégance du sujet. En plus de ça, comme c'est un sujet que j'ai l'habitude de voir abordé autrement que comme de la géométrie euclidienne, je ne suis pas très sûr de l'ordre dans lequel les faits s'agencent logiquement, et je n'ai pas toujours une idée très claire de la difficulté qu'il y aurait à les démontrer dans une telle approche. Et aussi à cause de ça, il faut que j'avertisse que je n'ai pas vérifié très soigneusement (je veux dire, encore moins que d'habitude…) tous les résultats que j'énonce dans cette entrée, et qu'il est fort possible que j'aie oublié une hypothèse ou une autre pour me raccrocher à là où je veux en venir ; notamment, j'ai failli complètement négliger la « condition supplémentaire » que j'ai finalement trouvé utile d'introduire plus bas dans la définition d'un kaléidoscope. Malgré tout ça, j'espère que ce que je raconte est au moins un peu intéressant.

[Lire la suite…]

Dans cette entrée, je voudrais évoquer la question des grandeurs physiques (longueur, durée, vitesse, masse, courant électrique…) et des unités de ces grandeurs. Je vais jeter un regard de matheux sur ce que ces choses sont, proposer quelques points de vue ou (esquisses de) définitions formelles possibles, et m'interroger sur l'utilité et la pertinence de ces points de vue, notamment pédagogiques, mais aussi du point de vue de la question de l'incertitude des mesures.

Je précise que cette entrée part un peu dans tous les sens, parce que j'ai commencé par écrire de la façon dont les idées me venaient (ou me revenaient, parce que ce sont des idées que je rumine depuis longtemps), et j'ai voulu raconter trop de choses à la fois, donc il y a plein de digressions. En plus de ça, j'ai un peu permuté les bouts que j'avais écrits (il en reste certainement des incohérences comme des je vais y revenir alors que les choses sont dans un autre ordre), puis repermuté, puis re-repermuté au fur et à mesure que j'ajoutais des digressions, et finalement je ne sais plus du tout dans quel ordre je dis les choses. Heureusement, il n'y a pas trop de lien logique clair ni de dépendance entre les différents morceaux ce que je raconte, donc on doit pouvoir lire cette entrée dans le désordre puisque c'est comme ça qu'elle a été écrite ! J'ai essayé de marquer par des triples accolades {{{…}}} (cf. ici) les digressions les plus identifiables, dans l'espoir que ça aide à s'y retrouver un peu.

À l'origine je voulais parler de la manière dont un mathématicien peut définir ce que sont les grandeurs physiques et leurs unités. Mais je n'ai pas résisté à parler d'autres choses, à faire un tableau de plein de grandeurs (ci-dessous) et à entrer dans des discussions sur ce que sont les grandeurs dans la pratique, sur les incertitudes et les échelles de masse. J'ai commencé à écrire des choses sur la réforme du SI qui doit avoir lieu d'ici quelques mois, puis je me suis dit que non, ça faisait vraiment trop, mais il en reste quand même des bouts… (Je garde donc pour une entrée ultérieure les explications précises sur la réforme du SI, même si j'y fais allusion à diverses reprises ici.) Bref, voilà pourquoi cette entrée est encore plus désordonnée que d'habitude. J'espère qu'il y a quand même des choses à en tirer !

⁂

Pour essayer de fixer la terminologie, j'appellerai grandeur (plutôt que dimension qui peut causer confusion) quelque chose comme « la masse » de façon abstraite ; et j'appellerai quantité [de cette grandeur] une masse particulière (par exemple 70kg), mesurée, donc, dans une unité. Si on veut parler comme un informaticien, donc, la grandeur sera, pour moi, le type (« la masse »), tandis que la quantité sera l'instance de ce type (70kg). Et l'unité est une quantité particulière (de la grandeur) qu'on a choisie pour exprimer toutes les autres. Comme n'importe quelle quantité non nulle (disons peut-être strictement positive) peut servir d'unité, la différence entre « quantité » et « unité » est juste une question de regard qu'on porte dessus.

Je ne sais pas si ce choix terminologique était le meilleur, je conviens que c'est un peu contre-intuitif de dire que la grandeur de [la quantité] 70kg est la masse, mais je ne suis pas certain qu'il existe de choix vraiment bon (et puis, maintenant que c'est fait, je n'ai plus envie de tout rééditer). J'ai essayé de m'y tenir systématiquement, de toujours utiliser le mot grandeur pour le type et quantité pour la valeur dans le type, mais je ne peux pas exclure quelques lapsus occasionnels.

Ajout (2018-08-16T14:15+02:00) : En fait, je ne distingue pas vraiment la grandeur et la dimensionnalité de cette grandeur (définie formellement ci-dessous), par exemple je ne distingue pas les grandeurs « énergie » et « moment d'une force » (tous les deux ayant l'unité SI de kg·m²/s², même si dans un cas on l'appelle plutôt le joule et dans un autre cas plutôt le newton·mètre, la distinction est plus mnémotechnique que fondamentale) ; de même, pour moi, le watt et le volt·ampère sont bien la même chose, nonobstant le fait qu'on ne les utilise pas exactement de la même manière ; je vais faire occasionnellement allusion à ce problème.

⁂

Bref, qu'est-ce que c'est que toute cette histoire ?

Pour commencer, une des propriétés des grandeurs et des unités est qu'on peut les multiplier et les inverser (donc, les diviser) ; alors qu'on ne peut ajouter ou soustraire que des quantités de même grandeur, mais ça j'y reviendrai plus loin. Par exemple, une unité de longueur divisée par une unité de durée (=temps) donne une unité de vitesse (mètre par seconde, kilomètre par heure) : et il s'agit bien d'une division des quantités correspondantes (1km=1000m, 1h=3600s donc 1km/h = 1000m/3600s = (1000/3600)m/s = 0.2777…m/s). On peut dire que, indépendamment des unités, la grandeur « vitesse » est le quotient de la grandeur « longueur » par la grandeur « durée ». De même, la grandeur « surface » est le carré de la grandeur « longueur » (son produit par elle-même). Et la grandeur « fréquence » est l'inverse de la grandeur « durée » (l'unité SI de fréquence, le hertz, est l'inverse de l'unité SI de temps, la seconde).

[Lire la suite…]

Méta : Régulièrement je tombe sur des problèmes mathématiques qui me paraissent tellement simples, tellement naturels et/ou tellement évidents (je veux dire évidents à poser, pas forcément évidents à résoudre !) que c'est inconcevable qu'il n'existe pas déjà une littérature abondante à leur sujet. Mais faute de connaître les bons mots-clés ou la bonne façon de formuler le problème (car souvent un même problème admet mille et une reformulations ou réinterprétations), je peux galérer pour mettre le doigt sur cette littérature. C'est extrêmement frustrant. Pour digresser sur ce problème en général, cf. par exemple cette vidéo où le YouTubeur Tom Scott passe la moitié du temps à raconter combien il a eu du mal à trouver le terme Inogon light pour en savoir plus sur un type de signal nautique utilisant intelligemment des effets de moiré pour montrer aux bateaux où aller en fonction de leur position. L'Internet a quelque chose de la Kabbale : quand on connaît le Vrai Nom de quelque chose, on acquiert du pouvoir sur cette chose — en l'occurrence, le pouvoir d'en savoir plus. Le problème que je veux évoquer ici fait partie de ces problèmes qui me semblent tellement « s'imposer » que je suis sûr qu'il a un nom et qu'il y a des chapitres entiers de bouquins d'algorithmiques qui lui sont consacrés ; mais comme je ne le formule pas forcément sous le bon angle, je ne trouve pas.

Il s'agit, donc, de quelque chose que je comprends raisonnablement bien du côté mathématique, mais dont l'algorithmique me laisse passablement perplexe. Ce qui veut dire que j'ai beaucoup de choses à raconter, dont beaucoup ne sont sans doute pas pertinentes pour le problème algorithmique, mais je ne sais pas au juste ce qui l'est et ce qui ne l'est pas.

Voici la première variante du problème algorithmique, qui est la plus simple et élémentaire à énoncer : je vais l'appeler la variante (AS), parce que je vais vouloir en formuler un certain nombre, ce sera plus commode si je leur donne des noms. (Le S signifie symétrique ; le A est là comme dans la classification de Killing-Cartan, mais pour l'instant peu importe.)

(AS) On se donne x et y deux vecteurs (de longueur, disons, n≥1), à coordonnées entières. Je suppose que la somme des coordonnées de x est nulle, et pareil pour y (je ne sais pas si ça sert vraiment à quelque chose).

Problème : trouver tous les produits scalaires possibles σ(x)·y entre y et un vecteur σ(x) obtenu en permutant les coordonnées de x, avec, pour chacun, son nombre d'occurrences, c'est-à-dire le nombre de permutations σ des coordonnées de x qui conduisent à ce produit scalaire.

Exemple : si x=(−2,−1,0,1,2) et y=(−2,0,0,1,1), la réponse attendue est {−7: 4 fois, −6: 4 fois, −5: 12 fois, −4: 8 fois, −3: 12 fois, −2: 4 fois, −1: 8 fois, 0: 16 fois, 1: 8 fois, 2: 4 fois, 3: 12 fois, 4: 8 fois, 5: 12 fois, 6: 4 fois, 7: 4 fois} (chaque produit scalaire possible σ(x)·y étant suivi de son nombre d'occurrences : notamment, il y a 16 permutations des coordonnées de x qui donnent un produit scalaire nul avec y). • Autre exemple : si x=y=(−2,−1,0,1,2), la réponse attendue est {−10: 1 fois, −9: 4 fois, −8: 3 fois, −7: 6 fois, −6: 7 fois, −5: 6 fois, −4: 4 fois, −3: 10 fois, −2: 6 fois, −1: 10 fois, 0: 6 fois, 1: 10 fois, 2: 6 fois, 3: 10 fois, 4: 4 fois, 5: 6 fois, 6: 7 fois, 7: 6 fois, 8: 3 fois, 9: 4 fois, 10: 1 fois}.

Il y a évidemment plein de façons de reformuler ça et plein de remarques évidentes à faire. Par exemple, je peux dire qu'il s'agit de considérer toutes les façons d'apparier (bijectivement) les coordonnées de x avec celles de y et de sommer les produits des coordonnées appariées entre elles : sous cette forme, il est évident que le résultat est symétrique entre x et y ; par ailleurs, il est clair que ça ne change rien de permuter les coordonnées de x ou celles de y, donc on peut les supposer triées au départ. Si on veut, je me donne deux paquets (deux « multiensembles ») x et y de nombres, de même taille, mais sans ordre, et je cherche toutes les façons de faire un produit scalaire.

[Lire la suite…]

En lien avec l'entrée précédente (que personne n'a lue mais c'est normal), j'ai produit ce petit gadget JavaScript qui (s'il n'est pas complètement cassé) représente une animation de l'équation des ondes sur un tore plat, en l'occurrence le tore plat E/L quotient du plan euclidien E=ℝ² par un réseau L triangulaire équilatéral (i.e., la fonction est périodique par L), à partir d'une condition initiale gaussienne assez piquée (censée donnée une idée d'approximation d'une distribution δ). Si on préfère, cela revient à faire l'équation des ondes dans le plan à partir d'une condition initiale qui est la somme d'une gaussienne centrée sur chaque point de L. Concrètement, il s'agit juste de calculer (la fonction du temps t et du point x∈E/L) :

${\displaystyle \sum _{\alpha \in L^{*}}{c}_{\alpha }\text{exp}\left(2i\pi \left(\alpha \cdot x\right)\right)\text{cos}\left(2\pi \left|\alpha \right|t\right)}$ où ${\displaystyle c_{\alpha }=\text{exp}\left(-{\left|\alpha \right|}^2/U^2\right)}$

— soit, en plus moche pour les navigateurs cassés qui ne gèrent pas le MathML —

∑_α∈L^* c_α·exp(2iπ(α·x))·cos(2π|α|·t)où c_α = exp(−|α|²/U²)

où U est un paramètre d'étroitesse de la condition initiale, et, histoire de faire le lien avec les notations de l'entrée précédente, Λ(α)=|α|² et m(α)=1 pour le paramétrage par tous les éléments α∈L^*. Ce que fait mon programme est uniquement de calculer cette somme (pour les α pas trop loin de l'origine dans L^* ; pour alléger les calculs, il précalcule les fonctions de α et x et se contente ensuite de les sommer).

Commentaire mathématique : Si la dimension d'espace était impaire, l'évolution de l'équation des ondes à partir d'un δ initial se ferait uniquement sur des fronts sphériques centrés sur les points du réseau (imaginez que vous superposez une sphère centrée en chaque point de L, dont le rayon croit linéairement avec le temps, et dont l'amplitude décroît proportionnellement à la surface de façon que la quantité totale reste constante), et l'évolution à partir d'une gaussienne donne la même chose avec des sphères un peu épaissies ; en dimension paire, ce qui est le cas ici, ce « principe de Huygens » ne vaut pas, la fonction de Green de l'équation des ondes n'est pas concentrée sur une sphère[#], il y a une « queue » (négative par rapport au front d'onde, et qui apparaît en bleu sur mon animation). • Par ailleurs, même si le réseau L^* ici est le réseau des poids de SU₃ et même si on a symétrie par le groupe de Weyl, il ne s'agit pas de l'équation des ondes sur SU₃ (pour ça il faudrait corriger Λ(α) et m(α)), c'est en gros ce qu'essaie d'expliquer l'interminable entrée qui précède.

[#] Ceci dit, ça doit être aussi assez joli comme dessin, une superposition de cercles de rayon croissant linéairement avec le temps et centrés sur chacun des points d'un réseau L triangulaire équilatéral.

Bon, tout ça fait des images pas trop moches, je dois l'avouer, et l'aspect « kaléidoscopique » apparaît assez clairement. Je pourrais mettre une animation de ce genre sur YouTube.

Ajout (2018-06-28T16:40+02:00) : Voici les vidéos YouTube : pour un réseau triangulaire équilatéral et pour un réseau carré (j'ai eu la folie, dans les deux cas, de calculer ça en 1920×1080, 25fps, pour une vidéo de 3′=180s ; ça m'a pris deux fois 40 minutes de calcul, mais il faut reconnaître que le résultat n'est pas mal).

Ajout 2 : Je recopie le lien fourni dans le commentaire de Benoit qui a écrit une version bien plus efficace de mon animation en utilisant WebGL.

Mais le calcul en direct est péniblement lent. Je pensais que sur un ordinateur moderne je n'aurais même pas besoin d'optimiser et je pouvais calculer la somme de quelques centaines de cosinus par pixel d'une image de taille raisonnable à une vitesse d'animation qui dépasse la perception de l'œil humain, mais apparemment calculer des centaines de millions de cosinus par seconde ça ne se fait pas sur un simple ordinateur de bureau, en tout cas pas en JavaScript.

Comme je déteste optimiser par-dessus tout, et que JavaScript commence à me sortir par les oreilles, je ne touche plus à ce code. Si quelqu'un veut l'améliorer (rendre le truc interactif en ajoutant un bouton pause ou quelque chose comme ça, permettre de bouger, zoomer, ou ce que vous voudrez, ou encore changer le réseau — il y a juste quelques lignes à commenter/décommenter pour faire un réseau carré), envoyez-moi des patchs, mon code est lisible et commenté, mais je ne veux pas de suggestions non codées. Parce que, là, pour le moment, les incantations propitiatoires du JavaScript servant à conjurer des petites crottes de ragondin, elles me gonflent prodigieusement.

Si vous voulez savoir ce que ça donne comme son, voici la conversion directe en onde sonore de la valeur mesurée au point central (l'origine de E/L, celle où est centrée la gaussienne initiale, i.e., mettre x=0 dans les formules ci-dessus), avec exactement les paramètres de l'animation, juste accélérée d'un facteur 8800 par rapport à l'animation affichée par le JavaScript. Mais ça donne juste un bruit strident atroce (moralité, une jolie image ne correspond pas forcément à un joli son, et si je veux transformer des spectres en sons un peu harmonieux, une dissipation dans le temps, dépendant de la fréquence, est indispensable).

Avant-propos : Cette entrée est une sorte de brain-dump, qui finit assez différemment de ce qu'elle commence. J'étais parti sur l'idée, sans avoir forcément pour but d'être compréhensible (en tout cas pas complètement, en tout cas pas par tout le monde), de jeter des réflexions surtout pour moi-même (comme une sorte de sauvegarde de mon état mental) sur des questions autour du spectre du laplacien. Sachant que je n'avais pas les idées complètement claires sur certaines des choses qui suivent, donc je ne peux pas expliquer tout ça parfaitement, encore moins le vulgariser au niveau où j'aimerais idéalement le faire : le but était plutôt de retrouver mes idées éventuellement plus tard, quitte à produire quelque chose d'un peu abscons et pas forcément bien correct mathématiquement ; et je me disais que ça ne ferait pas de mal de les mettre en ligne. Mais en pondant tout ça, je me suis laissé emporter par mon sujet, et la section sur les groupes de Lie compacts a pris une place démesurée, et s'est écartée du point de vue initial (finalement, pour ce que je raconte sur les groupes de Lie, on n'a pas vraiment besoin de savoir ce qu'est un laplacien ni de prononcer son nom, et d'ailleurs comme je prends l'exemple du groupe des rotations, on n'a pas vraiment non plus besoin de savoir ce qu'est un groupe de Lie compact) ; et j'en ai écrit des pages sur l'analyse de Fourier sur un groupe de Lie compact. Chose que je comprends quand même nettement mieux que le problème du spectre du laplacien en général, mais ça ne veut pas forcément dire que je l'explique mieux. Et finalement, je ne sais plus bien de quoi parle cette entrée, il y a plusieurs sujets assez indépendants, et le niveau auquel je place mes explications varie d'un endroit à l'autre. Bref, je ne sais pas ce que tout ça vaut, mais maintenant que c'est écrit, ce serait quand même idiot de ne pas le mettre en ligne. C'est dommage que, comme j'ai fait une énorme moussaka, tout le monde va être rebuté, mais tant pis, je n'ai plus le courage d'essayer de démêler les ingrédients de la moussaka.

Je commence en reprenant la ligne de pensées commencée dans l'entrée précédente (et inspirée par un roman de Connes, Chéreau et Dixmier, donc) : je cherche à produire des sons mathématiques intéressants (et pas déplaisants) à écouter, et une des façons d'y arriver semble être de considérer un spectre, notamment le spectre du laplacien (et donc en pratique, de l'équation des ondes) sur une variété riemannienne (compacte, parce que je ne suis pas analyste ni géomètre, moi, je ne sais pas gérer le cas non-compact[#]) ; plusieurs questions soulevées incidemment : quels objets choisir pour lesquels on sait calculer explicitement le spectre du laplacien (et qu'est-ce que ça signifie au juste) ?, quelles données sont associées au spectre en question ?, comment précisément convertir ce spectre en un son ?, d'ailleurs, comment mener le calcul sur ordinateur ? ; et aussi : comment vulgariser la notion de spectre du laplacien (notamment sur un groupe de Lie, espace riemannien symétrique, etc.) ? (Je ne compte pas tant essayer de faire cette vulgarisation ici et maintenant, mais peut-être donner les pistes par lesquelles je l'aborderais pour pouvoir les retrouver si je devais le faire plus tard.) Je vais évoquer le cas des tores plats (quotients de l'espace euclidien par un réseau) puis, comme expliqué au paragraphe précédent, je vais dévier sur la théorie de Weyl de l'analyse harmonique sur les groupes de Lie compacts, ce qui est largement indépendant de ce que je raconte au début. Et à la fin, je serai trop fatigué pour parler des espaces riemanniens symétriques autrement que pour dire que suis trop fatigué.

[#] Une blague, qui est d'ailleurs peut-être une histoire vraie, qu'on m'avait racontée il y a longtemps, concerne un mathématicien dont la femme… — non, ne soyons pas sexiste comme ceux qui m'ont raconté cette histoire, je vais plutôt dire : — une mathématicienne dont le mari ne connaît absolument rien aux maths ; mais elle lui a donné l'astuce suivante permettant presque à tous les coups de poser une question pertinente lors d'un échange entre matheux : il suffit d'attendre qu'il y ait une petite pause dans la conversation, de prendre un air pensif, et de demander et est-ce que vous avez considéré le cas non-compact ?.

[Lire la suite…]

(La première partie de cette entrée parle d'un roman qui parle de maths, la second parle de maths vaguement inspirées par le roman en question : à part cette proximité d'idées, il n'y a pas vraiment de rapport entre elles. Si les maths vous ennuient, à la fin, il y a des sons bizarres à écouter.)

Je viens de finir de lire le livre Le Spectre d'Atacama d'Alain Connes, Danye Chéreau et Jacques Dixmier, et j'avoue que je ne sais pas bien ce que j'en ai pensé. Pour commencer, c'est un livre assez difficilement classable : une sorte de mélange entre roman de science-fiction, fantaisie poétique, vulgarisation scientifique, plaidoyer sur l'intelligence artificielle, conte philosophique, récit picaresque et transposition en fiction de cet essai sur l'hypothèse de Riemann. Chacun des ingrédients me plaît a priori, et j'aime beaucoup l'idée de faire de la fiction à partir de la science, y compris de façon un peu poétique ; mais je trouve le mélange trop peu homogène… disons qu'il y a des grumeaux.

Le style est souvent un peu faible, mais ça ne me gêne pas tant que ça ; ce qui me gêne nettement plus, en revanche, c'est que l'intrigue part tellement dans tous les sens, accumule tellement d'invraisemblances et de rebondissements en apparence gratuits que ma suspension d'incrédulité, à force d'être tellement secouée, finit par lâcher complètement le coup. Parfois le roman devient didactique, parfois il est humoristique, parfois encore onirique, mais il y a trop de moments où on ne sait pas vraiment à quel degré le lire. L'idée de départ est bonne : un astrophysicien travaillant au réseau d'antennes de l'Atacama détecte un spectre d'absorption qui l'intrigue et fait appel à un ami mathématicien (de l'IHÉS…) pour essayer de le comprendre. Il y a aussi quelques tableaux du milieu académique qui sont plutôt réussis. Mais rapidement, et quitte à divulgâcher jusqu'à la fin de ce paragraphe, il est question d'une physicienne qui a volontairement passé son cerveau dans le rayon du LHC et qui a acquis la conscience quantique de vivre dans un espace de Hilbert et des capacités transhumaines mais seulement quand elle est à proximité d'un certain ordinateur : et là, je trouve que c'est vraiment un peu trop ; en plus de ça, le mathématicien part dans un périple dont on ne comprend pas vraiment le sens, qui l'emmène à Valparaiso puis sur une île perdue au milieu de nulle part puis à Sainte-Hélène, et tout ça ne sert pas vraiment l'intrigue. Et quand il est question d'ordinateurs, on sent que les auteurs ne sont pas du tout dans leur élément.

Ceci étant, je pense que c'est un ouvrage intéressant sur le plan de la communication scientifique : pas tellement d'idées scientifiques (il y a un peu de vulgarisation, mais ce n'est certainement pas l'objet principal du livre, et elle est plutôt light), mais de l'amour de la science et — et c'est important — des liens qui relient mathématiques, physique et informatique, et aussi du fait que la science « dure » peut avoir des aspects poétiques. Sur ce plan-là, je dirais que c'est plutôt une réussite. Peut-être finalement que ce roman, qui ne présuppose pas de connaissances scientifiques ou mathématiques, plaira plus à ceux qui justement l'abordent sans a priori.

⁂

J'en viens à des maths : la lecture du roman décrit ci-dessus m'a au moins convaincu (ou rappelé) que « les spectres » c'est important et intéressant. Je sais bien, pour avoir souvent entendu des gens le dire, que le spectre du laplacien (sur une variété riemannienne, disons), par exemple, c'est archi-super-important, mais j'avoue que je ne sais essentiellement rien de ce qu'il y a à dire, justement, sur ce spectre du laplacien, même dans des cas idiots (compacts, agréablement symétriques, tout ça tout ça).

En guise d'exercice, je me suis dit que j'allais calculer le spectre du laplacien pour des groupes de Lie compacts G (ou éventuellement des espaces homogènes G/H, par exemple des espaces riemanniens symétriques ou bien des R-espaces (variétés de drapeaux réelles), choses que je confonds d'ailleurs trop facilement[#]).

[#] Digression : Les espaces riemanniens symétriques irréductibles de type compact et simplement connexes sont (les groupes de Lie compacts simples simplement connexes eux-mêmes ainsi que) les quotients G/K où G est un groupe de Lie compact simple simplement connexe et K le sous-groupe compact connexe maximal d'une forme réelle G₀ de G (par exemple, la sphère de dimension n est Spin(n+1)/Spin(n) où Spin(n) est le compact connexe maximal de la forme Spin(n,1) de Spin(n+1)), et on peut aussi voir K comme les points fixes d'une involution de G qui correspond à l'involution de Cartan définissant G₀ ; j'ai certainement commis quelques erreurs en disant ça (notamment dans la connexité et la simple connexité), mais l'idée générale doit être à peu près ce que j'ai dit. Les R-espaces, eux, s'obtiennent sous la forme G₁/P où P est un parabolique d'un groupe de Lie réel semisimple G₁, qu'on peut aussi voir comme G/(G∩P) où G est un sous-groupe compact connexe maximal de G₁ et G∩P un sous-groupe compact maximal (du facteur de Levi) de P (par exemple, l'espace projectif réel dimension n est défini par le quotient de SL(n+1,ℝ) par son parabolique maximal associé à la première racine simple, i.e., les matrices dont la première colonne n'a que des zéros à partir de la deuxième ligne, et on peut le voir comme le quotient SO(n+1)/S(O(n)×O(1)) du sous-groupe compact connexe maximal SO(n+1) de SL(n+1,ℝ)) ; de nouveau, j'ai certainement commis quelques erreurs en disant ça, mais l'idée générale doit être ça. Je n'ai jamais vraiment compris « pourquoi » il y avait ces deux types de quotients très importants des groupes de Lie réels compacts, comment il faut y penser, par exemple du point de vue de l'analyse harmonique, et, de façon encore plus perturbante, pourquoi certains espaces peuvent se voir à la fois comme un espace riemannien symétrique et comme un R-espace (ou presque : cf. l'exemple que je viens de donner de la sphère et de l'espace projectif réel). Si quelqu'un a des éléments de réponse à m'apporter ou simplement des références où ces deux types de quotients sont discutés côte à côte de manière à me désembrouiller, ça m'intéresse ! (J'ai regardé l'article Geometry of Symmetric R-spaces de Tanaka, et j'ai eu l'impression de comprendre encore moins bien et de confondre encore plus après sa lecture.)

Mais aussi, j'avais (peut-être même que j'ai encore) vaguement l'espoir que des spectres intéressants, comme le spectre du laplacien sur tel ou tel espace bien sympathique, pourrait conduire à des sons harmonieux et donc répondre à ma question de trouver un objet mathématique qui s'« auditorise » de façon intéressante et agréable (plutôt que de se « visualiser ») ; dans cet ordre d'idées j'avais bien produit ceci, mais ce n'était pas du tout agréable à écouter et la construction de ces sons n'était pas franchement des plus naturelles.

L'idée générale, cette fois-ci, est qu'une fois connu le spectre du laplacien on peut s'en servir pour résoudre l'équation des ondes et obtenir les fréquences des vibrations propres de l'objet considéré (comme les racines carrées des opposées des valeurs propres du laplacien). Et donc produire des sons qui correspondraient à la manière dont « vibre » l'objet considéré — un groupe de Lie compact G ou un espace homogène G/H — quand, par exemple, on donne un coup dessus.

J'avoue que l'idée de taper un groupe de Lie pour voir comment il résonne me plaît énormément. (Et si j'en crois la lecture du Spectre d'Atacama, ça a aussi des chances de plaire à Connes et/ou Dixmier.)

Bref. Du peu que je sais de l'analyse harmonique sur les groupes de Lie et du théorème de Peter-Weyl, et si je comprends bien que le Casimir fournit la valeur du laplacien sur ce qui correspond à chaque représentation irréductible, le spectre du laplacien sur un groupe de Lie compact G est donné, à un facteur multiplicatif près (essentiellement arbitraire(?), mais négatif), par l'ensemble des valeurs C(v) := ⟨v,v+2ρ⟩ où v parcourt le réseau des poids dominants pour G. (Si tout ceci est du chinois pour vous, ce n'est pas très important, mais l'idée est qu'à G est associé un réseau euclidien appelé le « réseau des poids » et un cône polyédral de sommet l'origine dans cet espace euclidien appelé la « chambre de Weyl », auquel appartient le vecteur ρ dit « vecteur de Weyl », et les poids dominants sont les éléments de la chambre de Weyl ; chaque tel v, ou plus exactement le « caractère » χ_v associé, peut se concevoir comme un mode propre — un mode de vibration, si on veut — du groupe G, et la valeur du Casimir C(v) := ⟨v,v+2ρ⟩, est essentiellement l'opposé de la valeur propre du laplacien dont le vecteur propre est le caractère : Δχ_v = −C(v)·χ_v pour une certaine normalisation de Δ. S'il y a dans l'assistance des gens qui s'y connaissent en analyse harmonique et qui pourraient confirmer que j'ai bien compris, et peut-être même recommander un endroit où ce que je viens de dire serait écrit noir sur blanc sous cette forme y compris avec la valeur du Casimir, je leur serais reconnaissant.) Par exemple, pour les groupes de rang 2 : pour A₂ (i.e., SU₃), je trouve des valeurs (proportionnelles à) 8/3, 6, 20/3, 32/3, 12, 16, 50/3, 56/3, 68/3, 24, 80/3, 30… (où seules celles qui sont entières sont possibles pour la forme adjointe PSU₃) ; pour B₂ (i.e., Spin₅), je trouve 5/2, 4, 6, 15/2, 10, 21/2, 12, 29/2, 16, 35/2, 18, 20… (où seules celles que j'ai soulignées sont possibles pour la forme adjointe SO₅) ; et pour G₂, je trouve 12, 24, 28, 42, 48, 60, 64, 72, 84, 90, 100, 108… ; et sinon, pour F₄ : 12, 18, 24, 26, 32, 36, 39, 40, 42, 46, 48, 52… ; et vous devinez évidemment j'ai fait le calcul pour E₈ : 60, 96, 120, 124, 144, 160, 180, 186, 192, 196, 200, 210…

Et pour les espaces homogènes G/H, il doit s'agir de se limiter aux plus hauts poids v qui définissent des représentations de G dont la restriction à H a des points fixes (ou, ce qui revient au même par réciprocité de Frobenius, des représentations qui apparaissent dans l'induite à G de la représentation triviale de H, mais je ne suis pas si ça aide de le dire comme ça). J'arrive (mais laborieusement) à faire les calculs sur des cas particuliers en utilisant l'implémentation des règles de branchement dans Sage. Par exemple, le spectre de G₂/SO₄ (l'espace des sous-algèbres de quaternions dans les octonions) semble être : 28, 60, 72, 112, 132, 168, 180, 208, 244, 264, 300, 324… Mais je comprends trop mal les règles de branchement pour savoir s'il faut chercher une logique d'ensemble ou ce à quoi elle ressemblerait (sur les coordonnées de v dans la base des poids fondamentaux ; ce n'est même pas clair pour moi les v en question forment un sous-réseau du réseau des poids ou quel est son rang). Ajout (2018-06-18T18:50+02:00) : À la réflexion, pour les espaces riemanniens symétriques, je crois que je comprends au moins à peu près la situation (tout est dans la notion de système de racines restreintes) ; je crois même que tout est dit dans le chapitre V (par ex., théorème V.4.1) du livre de 1984 de Sigurður Helgason (Groups and Geometric Analysis), même si j'ai vraiment du mal à le lire ; je crois bien que le rang du réseau des poids v tels que la restriction à H ait des points fixes non triviaux coïncide avec le rang de l'espace symétrique G/H, même si j'aimerais bien voir ça écrit noir sur blanc.

Une chose qui m'étonne beaucoup est que ces suites ne semblent pas être dans l'OEIS. Tout le monde parle de l'importance du spectre du laplacien et personne n'a pris la peine de mettre le résultat, pour les cas les plus évidents que sont les groupes de Lie compacts, dans l'OEIS ‽ Comment est-ce possible ‽ J'hésite cependant à les soumettre moi-même parce que, à vrai dire, je ne suis pas très sûr de bien comprendre ce que je fais. (Et, entre autres choses, je ne sais pas du tout si les valeurs que j'ai listées ci-dessus ont un sens dans l'absolu ou seulement à proportionalité près. La valeur du Casimir semble dépendre d'une normalisation un peu arbitraire sur la longueur des racines ou quelque chose comme ça, et du coup je ne sais pas bien quoi prendre ou quoi soumettre.)

Pour ce qui est de produire des sons à partir de ça, il y a un autre truc sur lequel je n'ai pas des idées claires, c'est quelles amplitudes relatives il serait logique d'utiliser pour ces différentes harmoniques. Si on donne un coup de marteau sur le groupe de Lie G₂ (mais pas assez fort pour le casser !), il va peut-être résonner à des fréquences proportionnelles aux racines carrées de 12, 24, 28, 42, 48, 60, etc., mais avec quelles amplitudes ? Le problème se pose déjà sur une sphère de dimension 2 (SO₃/SO₂, si on veut) : les valeurs propres du laplacien sphérique sont (proportionnelles à) ℓ(ℓ+1), donc si on fait vibrer une sphère, elle produit des fréquences proportionnelles à 1, √3, √6, √10, etc., mais une fois ce spectre connu, ça ne donne pas pour autant un son (même si ça peut faire de jolies animations). Un bout de la réponse est fourni par la multiplicité des valeurs propres en question (sur la sphère, par exemple, ℓ(ℓ+1) a la multiplicité ℓ+1 parce qu'il y a ce nombre-là d'harmoniques sphériques de niveau ℓ indépendantes) ; s'agissant d'un groupe de Lie G, les multiplicités sont les carrés N(v)² des dimensions N(v) = χ_v(1) des représentations irréductibles correspondantes (par exemple, s'agisant de G₂, les valeurs propres avec multiplicité sont (12,7²), (24,14²), (28,27²), (42,64²), (48,77²), (60,77²), etc.). Mais ensuite ? Il me semble que, pour parler abusivement, les « coefficients » de la distribution δ (centrée en 1∈G) sur la base des caractères χ_v sont les N(v) = χ_v(1) et qu'il serait donc logique de donner à la fréquence √C(v) une amplitude proportionnelle à N(v)² (si on tape un coup sec et très localisé sur notre groupe de Lie), mais évidemment ceci diverge très méchamment. Je peux régulariser en remplaçant δ par une gaussienne, ce qui doit revenir à multiplier les coefficients par exp(−C(v)·σ²) avec σ une sorte d'écart-type de la gaussienne, mais le choix de σ est complètement arbitraire dans l'histoire. Bref, je peux produire des sons en superposant des fréquences proportionnelles aux √C(v) avec des amplitudes proportionnelles aux N(v)²·exp(−C(v)·σ²), mais le son en question dépend de façon énorme de σ. Une autre idée est de faire varier l'amplitude avec le temps pour donner une dissipation aux modes de vibration, par exemple en exp(−C(v)·t) (inspiré de l'équation de la chaleur).

Pour faire quand même des essais, de façon assez arbitraire, j'ai décidé de faire que l'intensité de la fréquence √C(v) décroisse en exp(−(C(v)/C(v₀))·(1+t/3s)) où v₀ est le poids qui correspond à la représentation adjointe de G (c'est-à-dire, la plus haute racine), et j'ai de même normalisé les fréquences pour que la fréquence de v₀ soit à 440Hz. C'est-à-dire que j'ai superposé des sin(2π·440Hz·(C(v)/C(v₀))·t) · N(v)² · exp(−(C(v)/C(v₀))·(1+t/3s)) où t est le temps et v parcourt les poids de G. Je n'aime pas le côté assez arbitraire de tout ça (et en particulier de mon 1+), donc je suis preneur d'idées plus naturelles, mais au moins les sons sont intéressants et, pour une fois, pas du tout désagréables à écouter.

Ceci n'est qu'une première expérience : j'en ferai sans doute d'autres quand j'aurai des idées plus claires sur ce que je veux faire et ce qui est intéressant, mais en attendant, voici quelques essais de ce que ça peut donner comme son de frapper différents groupes de Lie compacts (calibrés pour que leur représentation adjointe sonne le la à 440Hz) : en rang 1 : A₁ (c'est-à-dire SU₂, qui est vraiment une 3-sphère, je voulais vérifier que ça avait un son de cloche plausible et ça a effectivement un son de cloche vaguement plausible, c'est déjà ça) ; en rang 2 : A₂ (c'est-à-dire SU₃), B₂ (c'est-à-dire Spin₅) et G₂ ; en rang 4 : A₄ (c'est-à-dire SU₅), B₄ (c'est-à-dire Spin₉), C₄ (c'est-à-dire Sp₄), D₄ (c'est-à-dire Spin₈) et F₄ ; et bien sûr : E₆ et E₈. Tous ces fichiers sont du FLAC et chacun dure 6 secondes, si votre navigateur ne les ouvre pas spontanément, téléchargez-les et vous trouverez certainement un truc qui les lit. Tous les groupes que je viens de donner sont la forme simplement connexe, mais j'ai aussi produit des essais pour comparer le son de la forme simplement connexe avec la forme adjointe (laquelle a moins d'harmoniques) : Spin₅ versus SO₅ d'une part, et SU₃ versus PSU₃ de l'autre.

Ajout (2019-08-23) : voir ce fil Twitter et/ou cette version sur YouTube pour les sons de quelques grassmanniennes réelles, complexes et quaternioniques, ainsi que le plan projectif octonionique.

Je racontais ici que les « mathématiciens du dimanche » étaient souvent fascinés par les nombres premiers et capables de produire toutes sortes de conjectures fantaisistes à leur sujet ; et aussi, ils sont fascinés par l'écriture en base 10. Voici que je vois passer sur MathOverflow (et précédemment sur Math.StackExchange) la conjecture suivante, qui ressemble beaucoup à la caricature de la « conjecture du mathématicien du dimanche », à ceci près qu'elle conjecture que des nombres ne sont pas premiers :

Soit j≥1 un entier naturel, et N_j le nombre formé de la concaténation des écritures en base 10 des nombres (« de Mersenne » consécutifs) 2^j+1−1 et 2^j−1 ; c'est-à-dire : N_j = 10^m·(2^j+1−1) + (2^j−1) où m := ⌊log(2^j−1)/log(10)⌋+1 est le nombre de chiffres de l'écriture décimale de 2^j−1.

(Par exemple, N₁=31 (concaténation de 3 et 1), N₂=73 (concaténation de 7 et 3), N₃=157 (concaténation de 15 et 7), N₄=3115 (concaténation de 31 et 15), etc.)

Conjecture d'Enzo Creti : si N_j≡6 (mod 7), alors N_j n'est pas premier.

(Par exemple : pour j=9, on a N₉=1023511, qui est congru à 6 modulo 7, et il n'est pas premier : il vaut 19×103×523 ; pour j=10, on a N₁₀=20471023, qui est congru à 6 modulo 7, et il n'est pas premier : il vaut 479×42737.)

(Je ne sais pas si l'auteur de cette conjecture est un mathématicien « du dimanche », je ne sais rien sur lui, mais l'énoncé, en tout cas, ressemble exactement au type de spéculations sur les nombres premiers et les écritures en base 10 dont je voulais parler.)

Ce genre de problèmes est à la fois agaçant et passablement intéressant au niveau méta.

Expérimentalement, la conjecture est vérifiée jusqu'à des valeurs passablement grandes de j (l'auteur prétend être allé jusqu'à 4×10⁵ ; moi je me suis arrêté à 10⁴) ; et de plus, elle n'est pas vide, c'est-à-dire qu'il y a effectivement une densité significative (en fait, 1 sur 9) de j pour lesquels la prémisse N_j≡6 (mod 7) est vérifiée.

(On peut accessoirement remarquer que dans chacune des autres classes de congruence de N_j modulo 7, exceptée bien sûr la classe 0, on trouve des nombres premiers. C'est la classe 6 qui semble éviter les nombres premiers. À toutes fins utiles, en distinguant les cas de congruence de m modulo 6 et de j modulo 3, on peut remarquer que 10^m·(2^j+1−1) + (2^j−1) est congru à 6 modulo 7 lorsque soit (m≡3 (mod 6) et j≡0 (mod 3)) soit (m≡4 (mod 6) et j≡1 (mod 3)).)

Pourtant, je pense que n'importe quel théoricien des nombres sera d'accord avec moi pour dire qu'il ne croit pas une seule seconde à une telle conjecture. Pourquoi ?

D'abord, on se rappelle que le théorème des nombres premiers peut s'interpréter en disant que la « probabilité d'être premier » empirique d'un entier x tiré au hasard vaut environ 1/log(x) ; ou si le nombre est impair par construction, disons plutôt 2/log(x). En l'occurrence, on a log(N_j) = 2·log(2)·j + O(1), si bien que N_j a empiriquement une « probabilité d'être premier » qui décroît comme une fonction harmonique de j (quelque chose comme 1/(log(2)·j), en tenant compte du fait qu'il est forcément impair). Or la série harmonique diverge, donc il n'est pas vraisemblable que les N_j échouent tous à être premiers « par hasard ». En revanche, comme la série harmonique diverge très lentement (logarithmiquement), cela veut bien dire qu'il peut être nécessaire de pousser très très loin pour trouver un contre-exemple, donc avoir vérifié 10⁴ ou 10⁵ valeurs ne vaut pas grand-chose, et il n'est pas du tout invraisemblable que 10⁴ ou 10⁵ valeurs échouent toutes à être premières « par hasard » (expliquant ainsi la constatation expérimentale).

Il est donc invraisemblable que la conjecture soit vraie « par hasard », mais vraisemblable qu'elle le paraisse quand même jusqu'à 10⁴ ou 10⁵. Maintenant, se peut-il que la conjecture soit vraie autrement que « par hasard » ? Cela voudrait dire qu'il y aurait une « raison » expliquant une factorisation de 10^m·(2^j+1−1) + (2^j−1) à tous les coups (par exemple une identité algébrique, ou une conguence à 0 qui vaut à tous les coups, enfin, une « raison » qui fait qu'il n'est jamais premier). Or, si on met de côté la donnée que m est le nombre de chiffres décimaux de 2^j−1, ce n'est pas vrai que 10^m·(2^j+1−1) + (2^j−1) n'est jamais premier. En effet, en changeant un petit peu m, j'ai le contre-exemple de 10⁷⁰·(2²³⁰−1) + (2²²⁹−1) (où le nombre 2²²⁹−1 a 69 chiffres décimaux, j'ai inséré juste un 0 de plus dans la concaténation) : ce nombre est bien congru à 6 modulo 7, et il est premier (il a 140 chiffres, alors vous m'épargnerez de l'écrire complètement). Bref, si la conjecture était vraie autrement que par hasard, il faudrait avoir une factorisation de 10^m·(2^j+1−1) + (2^j−1) qui dépende du fait que m est précisément le nombre de chiffres décimaux de 2^j−1, et ça, ça semble complètement abracadabrant. (Tout ce que je raconte est complètement empirique, bien sûr, je n'ai pas de contre-exemple à la conjecture énoncée plus haut, mais j'explique pourquoi je n'y crois pas.)