David Madore's WebLog

This WebLog is bilingual, some entries are in English and others are in French. A few of them have a version in either language. Other than that, the French entries are not translations of the English ones or vice versa. Of course, if you understand only English, the English entries ought to be quite understandable without reading the French ones.

Ce WebLog est bilingue, certaines entrées sont en anglais et d'autres sont en français. Quelques-unes ont une version dans chaque langue. À part ça, les entrées en français ne sont pas des traductions de celles en anglais ou vice versa. Bien sûr, si vous ne comprenez que le français, les entrées en français devraient être assez compréhensibles sans lire celles en anglais.

Note that the first entry comes last! Notez que la première entrée vient en dernier !

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

(mercredi)

Quelques horreurs mathématiques (autour du 17e problème de Hilbert)

J'ai passé un certain nombre de jours en ermite à me reposer et à apprendre des maths amusantes. Je ne vais pas faire un compte-rendu (j'exposerai sans doute des bouts un peu au hasard d'entrées à venir), mais je viens de retomber sur les faits suivants, qui sont vraiment trop horribles pour ne pas les raconter.

(Attention, éloignez les enfants, c'est vraiment épouvantable.)

Commençons par ceci :

Il existe une fonction f qui est C sur ℝ, positive, ne s'annulant qu'en 0 où elle est infiniment plate (i.e., sa dérivée s'annule à tout ordre) et dont la racine carrée n'est même pas C2. Ou, comme il est facile de voir qu'il est équivalent : f ne peut pas s'écrire comme le carré d'une fonction C2.

Pourquoi c'est horrible ? Parce que la racine carrée d'une fonction C strictement positive est évidemment C (puisque la racine carrée est C sur les réels strictement positifs), et on se dit qu'une fonction positive présentant un unique point d'annulation devrait être gérable : si la fonction f est simplement supposée positive partout et nulle à l'origine, la dérivée doit y être nulle, donc f a un développement limité à tout ordre en 0 commençant par c·x², et il est possible d'extraire une racine carrée de ce développement, donc on imagine facilement qu'on devrait pouvoir mettre ensemble cette racine carrée du développement avec la racine carrée de la fonction hors de l'origine pour obtenir une racine carrée qui soit C. Et si la fonction est infiniment plate à l'origine, ça devrait être encore plus facile : le développement est nul, il n'y a donc aucune difficulté à prendre sa racine carrée, et on aimerait donc croire que cette fonction √f, qui a un développement limité à tout ordre en 0 et qui est C ailleurs qu'en 0, devrait bien être C partout !

Eh bien non. Non seulement la racine carré n'est pas forcément C, mais elle n'est même pas forcément C2, ce qui est tout de même très vexant. Le contre-exemple figure dans l'article Glaeser, Racine carrée d'une fonction différentiable, Ann. Inst. Fourier Grenoble 13 (1963) 203–210 (partie III ; le début montre que, quand même, la racine carrée est C1), et il n'est même pas difficile (il tient en deux petites pages, et c'est essentiellement des maths de classes préparatoires).

Bon, passons à la suite des horreurs. On se dit que quand même, à défaut de pouvoir écrire une fonction C positive comme carré d'une fonction bien régulière, on devrait au moins pouvoir l'écrire comme somme de carrés de fonctions bien régulières, ou quelque chose du genre. (Ce genre de questions consistant à écrire des choses positives comme somme de carrés s'appelle le 17e problème de Hilbert, sauf que normalement on s'intéresse plutôt à des fonctions rationnelles.)

Là, il y a au moins une bonne nouvelle partielle :

Si f est une fonction C sur ℝ et positive, alors pour tout m≥0 entier, on peut écrire f=g²+h² où g et h sont Cm.

Ce résultat (en fait,il suffit de supposer que f est C2m) est démontré par Jean-Michel Bony dans : Sommes de carrés de fonctions dérivables, Bull. Soc. Math. France 133 (2005) 619–639. Il y a une chose un peu effrayante dans l'histoire, c'est la date de l'article : un résultat pareil, on se dit qu'il aurait dû être démontré il y a cinquante ans, pas dix. Mais bon, au moins c'est positif (et, à une lecture en diagonale, les techniques employées n'ont pas l'air atrocement compliquées).

Par contre, toutes les tentatives naturelles pour renforcer l'énoncé ci-dessus ne marchent pas. On se dit, notamment, que si on passe en dimension supérieure à 1, peut-être que deux carrés ne suffiront plus, mais au moins un nombre fini de carré suffira. Eh bien non, nouvelle horreur :

Pour d≥4, il existe une fonction f qui est C sur ℝd et positive, et telle que f ne puisse pas s'écrire comme somme d'un nombre fini quelconque de carrés de fonctions C2. (Par ailleurs, si d≥5, on peut supposer f infiniment plate partout où elle s'annule. Et si on suppose seulement d≥3, on peut obtenir f qui ne puisse pas s'écrire comme somme d'un nombre fini quelconque de carrés de fonctions C3.)

La référence, cette fois, c'est Bony, Broglia, Colombini & Pernazza, Nonnegative functions as squares or sums of squares, J. Funct. Anal. 232 (2006) 137–147. Mais en fait, un exemple de fonction C positive en d=3 variables et qui ne peut pas s'écrire come somme d'un nombre fini de fonctions C3 est très facile à donner : on peut prendre le polynôme z6 + x4·y2 + x2·y4 − 3x2·y2·z2 trouvé par Motzkin en 1966 (on peut montrer qu'il est positif en utilisant l'inégalité entre moyenne arithmétique et moyenne géométrique, et il n'est pas très difficile, en raisonnant directement sur les coefficients, de montrer qu'il n'est pas somme de carrés de polynômes — dont le degré serait forcément au plus 3 ; mais du coup, en considérant les développements limités à l'origine, on peut voir qu'il n'est pas non plus somme de carrés de fonctions C3 ; voir aussi ici).

Par ailleurs, en revenant à la dimension d=1, on se dit que puisque Bony montre qu'une fonction C sur ℝ positive est somme de deux carrés de fonctions Cm pour m arbitraire, qu'on doit pouvoir échanger les quantificateurs et l'obtenir comme somme de deux carrés de fonctions C. Eh non, nouvelle horreur :

Il existe une fonction f qui est C sur ℝ et positive, ne s'annulant qu'à l'origine, et telle que f ne puisse pas s'écrire comme somme d'un nombre fini quelconque de carrés de fonctions C.

Cette fois, je n'ai pas de référence à fournir où ceci soit publié, parce qu'il semble que ça n'ait jamais été publié, ce qui est d'ailleurs profondément scandaleux (les gens qui savent faire pourraient bien faire l'effort de trouver un prétexte pour le mettre dans un article ou un livre quelconque, ou envoyer ça à un journal qui accepte les démonstrations de résultats « connus », ou faire une petite note sur l'arXiv quitte à ne jamais la soumettre !) ; en tout cas, Bony, dans l'article de cité ci-dessus, avoue qu'à sa connaissance ce n'est jamais paru nulle part, il référence deux livres qui marquent ça comme « communication privée » à l'auteur (de la part de P. Cohen et/ou D. Epstein). Voici ce qu'écrit Brumfiel dans l'introduction de Partially Ordered Rings and Semi-Algebraic Geometry (1979, CUP LMS Lecture Notes 37) :

As a final remark on the birational interpretation of Artin's solution of Hilbert's 17th problem, consider a different category, that of smooth manifolds and smooth real valued functions. Then Paul Cohen has shown me that (i) there exist nowhere negative smooth functions on any manifold which are not finite sums of squares of smooth functions (in fact, the zero set can be a single point) and (ii) given any nowhere negative smooth f, there are h, g, both smooth and h not a zero divisor, such that h²·f=g². The zero divisors are, of course, the smooth functions which vanish on some open set.

Bon, tout ça n'était peut-être qu'une façon insidieuse pour un algébriste de dire voyez, l'Analyse, c'est vraiment trop horrible : pour le côté algébrique, toute fonction rationnelle en d indéterminée sur les réels, qui est positive partout où elle est définie, est somme de carrés de fonctions rationnelles (Artin 1927 ; et grâce à la théorie des formes de Pfister, on sait en fait que 2d carrés suffisent ; pour une introduction à ce sujet, je renvoie à l'excellent livre de Lam, Introduction to Quadratic Forms over Fields (2005), où le contenu essentiel du résultat d'Artin apparaît comme théorème VIII.1.12, et celui de Pfister comme corollaire XI.4.11). Mais en fait, les questions autour du 17e problème de Hilbert sont sans doute véritablement subtiles. Ceci dit, ces variations autour d'un thème me suggèrent une question d'Analyse (énoncé précis ici), qui me paraît vraiment naturelle et dont je n'ai jamais vu nulle part la réponse (ou même une discussion quelconque) :

Soit f une fonction réelle admettant en tout point a de ℝ un développement limité à tout ordre et dont on suppose que, pour chaque i fixé, le coefficient ci(a) d'ordre i de ce développement varie continûment avec le point a (où on prend le développement). Peut-on conclure que f est C ?

(lundi)

Petit séjour à Rotterdam

Mon poussinet et moi avons passé quelques jours aux Pays-Bas. Pas spécialement pour pratiquer mon néerlandais (j'ai fait l'effort de commander une fois en néerlandais au restaurant, mais je pense que ça ressemblait plus à du petit-nègre, ou en l'occurrence du petit-allemand). Nous avons visité Amsterdam, mais surtout Rotterdam et La Haye (c'est-à-dire Den Haag, la capitale de facto des Pays-Bas, appelée aussi The Hague en anglais, à ne pas confondre avec La Hague en France, qui n'a rien à voir ; notons que la haie est à la fois traduction et cognat de de haag). Le Thalys nous a déposé à Amsterdam, mais notre hôtel était à Rotterdam (qui est à entre 40′ et 1h de train d'Amsterdam, selon le type de train qu'on prend) ; quant à La Haye, elle est accessible en métro depuis Rotterdam.

La plupart des gens à qui nous avons raconté vouloir visiter Rotterdam ont eu l'air de penser que c'était une idée saugrenue. Mais en vérité, comme mon poussinet et moi ne sommes pas trop férus de musées ou de vieilles pierres, ou en tout cas, que nous aimons visiter des villes modernes et dynamiques, nous n'avons pas regretté ce choix. Rotterdam donne un peu l'impression d'avoir été entièrement construite dans le cadre d'un concours architectural qui se serait déroulé vers 1995 (je ne sais pas bien pourquoi : même si la ville a été rasée en 1940, je suppose qu'on ne l'a pas laissée sous forme de ruines pendant cinquante ans). Du coup, il faut aimer l'architecture contemporaine, mais si on l'aime, au niveau urbanisme, c'est plutôt réussi, et il y a des bâtiments à la forme vraiment surprenante ou intéressante à regarder (je pense notamment à cet immeuble d'habitations que je n'ai pas pensé à prendre en photo et dont les photos sur Google images ne rendent pas vraiment justice).

À part ça, l'hôtel où nous avons dormi à Rotterdam (le Mainport Hotel) était à l'image de la ville : ultra-moderne, très confortable, et sans doute un peu froid. En fait, c'était la première fois que je séjournais dans une chambre d'hôtel qui avait à la fois une douche et une baignoire à bulles. Et une deuxième télé dans la salle de bain, pour pouvoir regarder pendant qu'on prend un bain-massage. Pour un prix pas du tout exorbitant, en tout cas, par rapport à ce qu'on aurait payé à Amsterdam (peut-être aussi parce qu'il était un petit peu éloigné du centre-ville). Le petit-déjeuner, lui, était assez cher, mais excellent, et ce n'est pas désagréable de prendre le brunch sur une terrasse au-dessus de la Meuse. Je peux aussi recommander, en matière alimentaire à Rotterdam, le restaurant indonésien Sari Koering sur Wijnhaven (commandez un nasi, c'est délicieux et pas cher). Nous avons aussi essayé le haut lieu bio-brancho-éco-bobo Spirit sur Mariniersweg, qui propose des plats végétariens au poids : c'est très bon, mais vraiment exorbitant (25€/kg).

Quant à La Haye, c'est un mélange assez éclectique : il y a des endroits d'immeubles modernes qui ressemblent un peu à Rotterdam (mais en légèrement moins réussi), il y a des petits canaux comme à Amsterdam, certains coins qui m'ont fait énormément penser à Londres, d'autres encore à une ville allemande non identifiée. La petite gare de Den Haag HS a un charme pittoresque complètement différent de l'architecture futuriste de Den Haag Centraal, mais les deux sont intéressantes. (En revanche, nous ne sommes pas allés voir le palais de la Paix, qui était un petit peu loin.)

Amsterdam, évidemment, est plus jolie avec ses célèbres petits canaux, mais le cœur en est tellement envahi de touristes (et c'est un parisien qui parle !) que j'avais un peu envie de fuir : la place juste devant la gare d'Amsterdam, un dimanche après-midi d'été, c'est un cauchemar d'agoraphobe. D'un autre côté, il y avait aussi une incroyable concentration de beaux jeunes gens athlétiques : je ne sais pas si c'est le résultat de toute la population estudiantine d'Europe qui vient chercher son THC aux Pays-Bas (probablement pas, en fait : ça parlait beaucoup néerlandais — mais pourquoi ce ne serait pas pareil à Rotterdam ?) ; mais si c'est le cas, je veux bien qu'on légalise le cannabis en France aussi (faudra juste mettre des règles un peu strictes sur l'aération, parce que là ça puait la beuh dans la rue).

Bref, voici quelques photos que j'ai prises (comme d'habitude, on se rend compte après coup qu'il y a plein de choses qu'on a oublié de photographier alors qu'on pensait l'avoir fait). J'utilise le même petit gadget JavaScript primitif que pour mes photos de Munich l'an dernier. J'ai tenté de veiller à ce que les photos soient correctement géolocalisées.

(mardi)

Pourquoi e et π paraissent-ils plus aléatoires que génériques ?

Je veux discuter ici non d'une question de maths mais d'une question de philosophie des maths (et qui, pour une fois, n'est pas de la logique mais plutôt la théorie des nombres !). Néanmoins, pour l'expliquer, il faut bien que je parle de maths.

Un fait empirique est le suivant : quand on fait des études statistiques sur les décimales, disons, du nombre e ou du nombre π, celles-ci se comportent empiriquement comme une suite aléatoire (comme si elles avaient été tirées au hasard par un grand dé cosmique). Par exemple, les décimales en base 10 semblent équidistribuées (il y a autant de 0 que de 1 que de 2… que de 9) ; mieux, les suites de 2 chiffres semblent équidistribuées (il y a autant de 00 que de 01… que de 99), et pareil pour les suites de 3 chiffres et plus, tant qu'on a assez de données pour faire des statistiques significatives (or, s'agissant des décimales de π, on en a beaucoup). Autrement dit, on conjecture que π est un nombre « normal », ce qui regroupe ces différentes affirmations sur la fréquence des décimales. Et ce n'est pas vrai qu'en base 10, qui n'a aucune raison d'être spéciale : on conjecture que π est normal en toute base (entre autres, écrit en base 2, on conjecture qu'il devrait contenir quelque part le contenu de ce blog jusqu'à sa fin, codé en binaire ; ceci n'a, évidemment, rien de remarquable : il faudrait aller si loin dans les décimales pour le trouver qu'indiquer l'endroit où on le trouve est essentiellement aussi long que donner le contenu lui-même).

Pour motiver cette conjecture on donne typiquement l'explication suivante : « presque tous » les nombres réels sont normaux en toute base. C'est-à-dire que si on tire un nombre réel aléatoirement (uniformément entre 0 et 1), la probabilité qu'il ait les propriétés que j'esquisse ci-dessus vaut exactement 1. Ceci est un énoncé mathématique clair et pas très difficile (pas du tout conjectural) : l'ensemble des nombres réels qui n'ont pas la propriété d'être normaux en toute base est un ensemble dit négligeable (=de mesure de Lebesgue nulle, ce qui signifie techniquement qu'on peut le recouvrir par une suite d'intervalles dont la somme des longueurs converge et a une somme arbitrairement petite, cf. ci-dessous), correspondant à un événement de probabilité 0. On reformule aussi ce fait en disant que presque tous les nombres réels sont normaux en toute base (presque tous veut dire précisément que l'ensemble de ceux qui ne le sont pas est négligeable). Dès lors (dit-on), il n'est pas surprenant, si presque tous les nombres réels ont la propriété d'être normaux en toute base, de conjecturer que π en particulier l'est. Je ne prétends pas que cette justification soit insensée, mais elle glisse de la poussière sous le tapis, à savoir la raison pour laquelle presque tous est une bonne notion.

Pour expliquer la poussière dont je me plains, il faut que je signale un autre fait mathématique : la dualité entre mesure [de Lebesgue] et catégorie [topologique]. (Je suis obligé ici de donner quelques précisions techniques, mais les détails ne sont pas extrêmement importants et peuvent être survolés.) En effet si la définition que j'ai donnée ci-dessus,

Un ensemble N⊆ℝ est dit négligeable (ou de mesure nulle) lorsque, donné ε>0 arbitrairement petit, on peut trouver une suite (Ii) (indicée par les entiers naturels) d'intervalles tels que (1) N⊆⋃iIi (c'est-à-dire, ces intervalles recouvrent N), et (2) ∑iℓ(Ii)<ε (c'est-à-dire, la somme des longueurs ℓ(Ii) des intervalles est inférieure au ε qu'on s'était donné).

Le complémentaire d'un ensemble négligeable est dit (conégligeable ou) de mesure pleine. On dit aussi que presque tous [au sens de la mesure] les nombres réels vérifient une propriété P lorsque l'ensemble de ceux qui la vérifient est de mesure pleine (i.e., l'ensemble de ceux qui ne la vérifient pas est négligeable).

— est une définition raisonnable d'un ensemble de réels « très petit », il y en a une autre, concurrente :

Un ensemble M⊆ℝ est dit maigre (ou parfois de première catégorie, mais c'est une terminologie épouvantable) lorsqu'il existe une suite (Fi) (indicée par les entiers naturels) de parties de ℝ tels que (1) M⊆⋃iFi (c'est-à-dire, ces parties recouvrent M) et (2) chaque Fi est fermé d'intérieur vide, ce qui signifie (2a) « fermé » : que si x n'appartient pas à Fi, alors il existe un ε>0 tel qu'aucun des nombres entre xε et x+ε n'appartienne à Fi et (2b) « d'intérieur vide » : que Fi ne contient aucun intervalle de longueur non-nulle.

Le complémentaire d'un ensemble maigre est dit comaigre (ou résiduel ; ceci signifie exactement que l'ensemble contient une intersection dénombrable d'ouverts denses). On pourrait dire que quasiment tous au sens de la catégorie les nombres réels vérifient une propriété P lorsque l'ensemble de ceux qui la vérifient est comaigre (i.e., l'ensemble de ceux qui ne la vérifient pas est maigre).

Il existe bien sûr des ensembles qui sont « très petits » dans les deux sens (à la fois négligeables et maigres) : l'ensemble ℚ des rationnels, ou plus généralement, tout ensemble dénombrable ou à plus forte raison fini, est négligeable et maigre ; l'ensemble de Cantor standard (obtenu en partant de [0;1] et en retirant de façon répétée le tiers du milieu de chaque intervalle restant), bien qu'indénombrable, est à la fois négligeable et maigre (en fait, c'est déjà un fermé d'intérieur vide, donc la maigreur est plus évidente que la négligeabilité). Les deux notions ont des propriétés communes, comme le fait que la réunion d'une suite (i.e., d'une famille dénombrable) d'ensembles négligeables, resp. maigres, et encore négligeable, resp. maigre. Ou encore, le fait que ni un ensemble négligeable ni un ensemble maigre ne peuvent contenir un intervalle de longueur non nulle (aussi petite soit-elle) : ceci est généralement reformulé en disant qu'un ensemble de mesure pleine ou un ensemble comaigre sont denses (i.e., rencontrent tout intervalle de longueur non nulle ; un cas résulte de l'additivité de la mesure de Lebesgue, l'autre du théorème de Baire).

Les parallèles entre ces deux notions classiques de « petitesse » sont assez nombreux et importants pour que quelqu'un ait consacré un livre essentiellement à cette question (il s'agit de Measure and Category de John Oxtoby, le numéro 2 dans la série des Graduate Texts in Mathematics de Springer). Je donne d'autres exemples de parallèle en petits caractères ci-dessous (le lecteur non intéressé par les détails mathématiques peut les sauter).

Voici un exemple : une partie de ℝ² est négligeable, resp. maigre (la notion de partie négligeable ou maigre de ℝ² se définit de façon essentiellement au cas de ℝ — il suffit en gros de remplacer les intervalles par des rectangles, et, pour la mesure, de prendre le produit de leurs côtés) si et seulement si son intersection avec les droites horizontales y=c est négligeable, resp. maigre, vue comme partie de ℝ, pour « presque toutes au sens de la mesure » (resp. « quasiment toutes au sens de la catégorie ») les valeurs de c, autrement dit, l'ensemble des c telle que l'intersection ne soit pas négligeable, resp. maigre, est un ensemble négligeable, resp. maigre. (Dans le cas de la mesure, ceci est une incarnation du théorème de Fubini.) ❦ Voici un autre exemple : supposons que A est une partie borélienne de ℝ (c'est-à-dire, qui peut s'obtenir à partir des intervalles en répétant de façon arbitraire des opérations de complémentaire, de réunion dénombrable et d'intersection dénombrable), et supposons que A est invariant par changement des premières décimales d'un nombre (en une base b fixée quelconque), c'est-à-dire que si xA et si x′ diffère de x par un rationnel de la forme N/brN, r sont entiers (i.e., les décimales de x′ coïncident avec celles de x à partir d'un certain rang r) alors x′∈A ; alors : A est soit de mesure nulle (=négligeable) soit de mesure pleine, et A est soit maigre soit comaigre (le cas de la mesure s'appelle loi du 0–1 de Kolmogorov). ❦ Un résultat de théorie descriptive des ensembles : la projection sur la première coordonnée d'un ensemble borélien de ℝ² n'est pas nécessairement borélienne, en revanche elle diffère d'un borélien (au sens de la différence symétrique) par un ensemble simultanément[#] négligeable et maigre. ❦ Je pourrais enfin citer un théorème classique d'Erdős, généralisant un résultat antérieur de Sierpiński, selon lequel, sous l'hypothèse du continu, il existe une involution ℝ→ℝ qui envoie ensembles négligeables sur ensembles maigres et vice versa.

[#] Note technique : on donne la définition suivante : un ensemble Lebesgue-mesurable est la différence symétrique d'un borélien et d'un négligeable, et un ensemble ayant la propriété de Baire est la différence symétrique d'un borélien et d'un maigre. Il est alors vrai qu'un ensemble à la fois Lebesgue-mesurable et ayant la propriété de Baire, est la différence symétrique d'un borélien et d'un ensemble à la fois négligeable et maigre. Comme je ne trouve de preuve nulle part, en voici une : on peut écrire (cf. ci-dessous) ℝ=MNM est maigre et N est négligeable, M et N sont disjoints (i.e., complémentaires l'un de l'autre), et tous les deux sont boréliens. Si X est mesurable et a la propriété de Baire, alors : XM est mesurable (puisque M est borélien), donc on peut écrire XM = AN′ où A est borélien et N′ négligeable ; et quitte à intersecter A et N′ avec M, on peut supposer qu'ils sont inclus dedans : du coup, N′ est simultanément maigre et négligeable ; or de même, XN peut s'écrire BM′ avec B borélien inclus dans N et M′ simultanément négligeable et maigre inclus dans N ; on a alors X = (AB)∆(M′∪N′) différence symétrique d'un borélien et d'un ensemble simultanément négligeable et maigre.

Néanmoins, pour parallèles qu'elles soient, ces deux notions de petitesse, être négligeable et être maigre, sont aussi souvent en opposition. En effet, l'ensemble ℝ de tous les réels est réunion d'un ensemble négligeable et d'un ensemble maigre. Comme ℝ n'est certainement pas un ensemble « très petit » de réels, s'il est réunion de deux ensembles, il faut croire que l'un de ces ensembles n'est pas si petit que ça. Ssi on préfère, il y a des ensembles négligeables qui sont comaigres, ou de façon encore équivalente, des ensembles de mesure pleine qui sont maigres. Et en fait, si on prend l'ensemble des nombres normaux en base b, ou bien normaux en toute base, c'est un exemple tout à fait explicite d'un ensemble de mesure pleine qui est maigre : c'est-à-dire : au sens de la mesure, presque tous les nombres réels sont normaux, mais au sens de la catégorie, quasiment aucun ne l'est !

L'argument heuristique présenté ci-dessus pour expliquer pourquoi il est raisonnable de conjecturer que e et π sont normaux, c'est que presque tous les nombres le sont (la probabilité qu'un nombre tiré au hasard ne soit pas normal vaut 0) ; mais c'est presque tout au sens de la mesure : or à l'inverse, comme je viens de le dire, au sens de la catégorie, quasiment aucun nombre n'est normal, donc on pourrait tout aussi bien conjecturer que e et π ne sont pas normaux.

Ainsi, si on doit faire une conjecture sur le comportement des décimales de π, Monsieur Eugsebel (avocat de la théorie de la mesure) va nous dire je conjecture que π est normal en toute base, parce que l'ensemble des nombres qui le sont est de mesure pleine, et on trouve ça raisonnable. Mais Monsieur Eriab (avocat de la catégorie topologique), au contraire, va dire et moi je conjecture que π n'est normal en aucune base, parce que l'ensemble des nombres normaux est maigre (en fait, Monsieur Eriab va faire des prévisions beaucoup plus précises que « ne pas être normal », j'en donnerai des exemples plus loin) ; et expérimentalement il semble que Monsieur Eugsebel ait raison dans sa conjecture alors que Monsieur Eriab aurait tort. Comment cela se fait-il ?

La question philosophique, c'est donc : étant donné que ces notions classiques et naturelles sont « duales », présentant un grand parallèle, comment se fait-il que la théorie de la mesure prédise apparemment mieux que la catégorie topologique le comportement d'un nombre « naturel » comme e ou π ?

Pour essayer d'éclaircir un peu pourquoi c'est une question naturelle à se poser, il faut que je mentionne encore les deux notions de nombre aléatoire et de nombre générique, qui correspondent respectivement aux prédictions faites par la mesure et par la catégorie. La question deviendra alors : comment se fait-il que des nombres naturels comme e et π ressemblent plus fortement à des nombres aléatoires qu'à des nombres génériques ? (alors qu'ils ne sont ni l'un ni l'autre).

La notion de nombre aléatoire peut être source de beaucoup de confusion. D'abord, il y a ce que les probabilistes appellent une variable aléatoire : un nombre réel aléatoire, dans ce sens, ce n'est pas un nombre réel, c'est techniquement une fonction à valeurs réelles sur un espace de possibles (espace probabilisé) ; on peut alors parler de toutes sortes de choses sur des nombres tirés aléatoirement selon telle ou telle distribution de probabilités : c'est là le sens usuel du mot aléatoire et ce n'est pas celui dont je veux parler, même si celui dont je veux parler (dû à Martin-Löf) est évidemment apparenté. Il s'agit ici d'un concept d'« aléatoire » absolu : en ce sens, un réel (qui peut sans problème être identifié à la suite de ses décimales) est ou n'est pas aléatoire, ce qui est différent de la notion d'aléatoire des probabilistes où il n'y a pas de sens à dire qu'un nombre dans l'absolu ait été tiré aléatoirement.

En fait, je n'ai pas l'intention de donner la définition formelle de nombre aléatoire : mais essentiellement, un nombre est aléatoire lorsqu'il n'appartient à aucun ensemble négligeable qui puisse être décrit de façon explicite ou calculable. Naïvement, on aimerait dire qu'un nombre aléatoire est un nombre qui n'appartient à aucun ensemble négligeable — cela, bien sûr, n'a pas de sens car x appartient toujours à {x}, et {x} est négligeable (puisque fini). Alors on fait le mieux qu'on puisse faire : on suppose donnée une notion de calculabilité (relativement à quoi la définition sera faite), et on appelle « aléatoire » un nombre qu'on n'arrive pas à mettre dans un ensemble négligeable qui puisse être décrit par une suite calculable (par exemple à partir des intervalles à extrémités rationnelles et au moyen des opérations de complémentaire, de réunion dénombrable et d'intersection dénombrable). Ceux qui veulent voir une définition précise peuvent se rapporter à cette vieille entrée où je traite essentiellement de la même question qu'ici mais sous un angle différent ; ou bien à l'article Wikipédia sur la question ; ou encore, par exemple au livre Computability de S. Barry Cooper (§15.7) ; voir aussi Jech, Set Theory, lemme 26.4 dans la Third Millennium Edition (ou 42.6 dans l'ancienne), même s'il s'agit là d'une définition beaucoup plus forte (car relativement à une notion de calculabilité elle-même beaucoup plus forte).

La notion de nombre générique est duale : un nombre est générique lorsqu'il n'appartient à aucun ensemble maigre qui puisse être décrit de façon explicite ou calculable (de nouveau, voir cette vieille entrée pour une définition précise, ou §13.3 dans le livre de Cooper, ou encore chapitre IV, §2, dans le livre Degrees of Unsolvability de Lerman).

Mesure (de Lebesgue)Catégorie (topologique)
négligeable
=de mesure nulle
maigre
=de première catégorie
conégligeable
=de mesure pleine
=de complémentaire négligeable
comaigre
=résiduel
=de complémentaire maigre
presque tous (pour la mesure)
=tous dans un ensemble de mesure pleine
quasiment tous pour la catégorie
[terme non standard]
=tous dans un ensemble comaigre
réel aléatoire
=dans aucun ensemble négligeable calculable
réel générique
=dans aucun ensemble maigre calculable

Autrement dit, un nombre aléatoire est un nombre sur lequel Monsieur Eugsebel fait des prévisions correctes, tandis qu'un nombre générique en est un sur lequel c'est Monsieur Eriab qui a raison. Cette dernière notion n'est pas évidente à visualiser intuitivement. La notion de nombre aléatoire se comprend assez bien, et correspond effectivement à l'image qu'on peut se faire d'un nombre obtenu par tirage aléatoire de la suite de ses décimales. En particulier, un nombre aléatoire est normal en toute base — justement puisque l'ensemble des nombres qui ne le sont pas est négligeable et que cet ensemble se décrit de façon calculable (je ne rentre pas dans les détails). Un nombre générique, en revanche, n'est pas normal, puisque l'ensemble des nombres normaux est maigre ; mais il est intéressant d'essayer de décrire de façon plus positive comment ses décimales se comportent.

Prenons la base 2 pour simplifier : si bn désigne le n-ième bit (valant 0 ou 1) d'un nombre réel x, considérons la suite 1nk=0n1bk (si le MathML est cassé dans votre navigateur, il s'agit de la moyenne des n premiers bk, i.e., (1/n)·somme(bk, k=0…n−1)) : autrement dit, il s'agit de la proportion de 1 parmi les n premiers bits du nombre considéré. Comment se comporte cette suite ? Si on suppose que x est aléatoire, alors elle tend vers ½ : en effet, l'ensemble des nombres x pour lesquels la suite ne tend pas vers ½ est un ensemble négligeable, ceci est une conséquence de la loi des grands nombres, et la normalité d'un nombre est un renforcement de cette affirmation. Et comme je l'ai souligné, c'est le cas, expérimentalement, pour des nombres comme e ou π. En revanche, si x est générique, il en va tout autrement : la suite n'a pas de limite, et en fait elle s'approche arbitrairement, et infiniment souvent, de toute valeur de l'intervalle [0;1] (notamment, sa limite inf. vaut 0 et sa limite sup. vaut 1). C'est-à-dire qu'alors que les bits d'un nombre aléatoire se répartissent bien en proportion, tendant vers moitié de 0 et moitié de 1, pour un nombre générique, la proportion de 1 ne converge jamais, elle ne cesse de changer. Donc, s'il est vrai pour un nombre générique aussi bien que pour un nombre aléatoire que toutes les suites de chiffres apparaissent dans les décimales du nombre, en revanche, s'agissant d'un nombre générique, elles ne le font pas avec une fréquence bien définie. Un autre phénomène du même genre (et qui implique le précédent) est que si x est générique, il existe des n arbitrairement grands tels que toutes les décimales bn à bn² soient des 0 (et de même avec des 1, ou une alternance de 0 et de 1, ou ce genre de motifs ; et de même en remplaçant n² par 2n ou, en fait, n'importe quelle fonction calculable de n) : ceci n'est pas le cas avec les nombres aléatoires (pour trouver n² bits 0 consécutifs dans une suite aléatoire, il faudra aller jusqu'au bit n² 2n² environ).

Pour montrer ce résultat, il s'agit simplement de remarquer que, lorsque m est fixé, l'ensemble des suites binaires qui, pour un certain nm, n'ont que des zéros entre les termes bn et bn², est un ouvert dense, ce qu'il est facile de vérifier. En prenant l'intersection de ces ensembles pour tous les m entiers naturels, on voit que l'ensemble des réels pour lesquels il existe des n arbitrairement grands tels que toutes les décimales bn à bn² soient des 0 est comaigre. On peut évidemment faire pareil pour des 1 ou des alternances de 0 et de 1 avec n'importe quelle période rationnelle fixée : ceci montre que la densité de 1 va s'approcher asymptotiquement de n'importe quel rationnel fixé.

Si j'essaie de donner une image intuitive des réels aléatoires et génériques, je dirai que les deux font « n'importe quoi » mais différemment : les aléatoires obéissent à des lois statistiques, donc leurs décimales se répartissent bien en proportion ; à l'inverse, les génériques font n'importe quoi en ce sens qu'ils s'amusent à obéir à tous les motifs réguliers qu'on peut imaginer, y compris pour très longtemps.

Une autre différence intéressante concerne l'approximation diophantienne : on dit qu'un réel ξ est approchable à l'ordre d par les rationnels lorsqu'il existe une infinité de rationnels p/q et une constante C>0 tels que |ξ−(p/q)| < C/qd : cette condition est d'autant plus forte que d est grand. L'algorithme d'Euclide montre que tout nombre irrationnel est approchable à l'ordre 2 par les rationnels (les rationnels eux-mêmes ne sont approchables qu'à l'ordre 1). Un nombre approchable à tous les ordres est appelé nombre de Liouville (ces nombres sont tous transcendants — et c'est d'ailleurs la raison pour laquelle Liouville les a introduits — car il est facile de montrer qu'un nombre algébrique de degré d ne peut pas être approchable à un ordre >d ; en fait, un théorème difficile montre qu'il ne l'est même pas à un ordre >2). Là aussi, la mesure et la catégorie diffèrent complètement dans leur jugement : l'ensemble des nombres de Liouville est comaigre alors que l'ensemble des nombres approchables à un ordre >2 quelconque est négligeable. Autrement dit, un nombre aléatoire est approchable par les rationnels à l'ordre 2 et pas mieux, alors qu'un nombre générique est approchable à tous les ordres. De nouveau, Monsieur Eugsebel prédira que e et π ne sont pas approchables par les rationnels à mieux que l'ordre 2 alors que Monsieur Eriab prédira qu'ils le sont à tous les ordres — et pour le coup, on sait que Monsieur Eriab a tort (s'agissant de e, on sait que Monsieur Eugsebel a raison : le meilleur ordre d'appproximation est 2, cela peut se montrer à partir de la fraction continuée habituelle pour ce nombre ; s'agissant de π, d'après ce papier, on sait qu'il n'est pas approchable à un ordre mieux que 8.02, et il me semble qu'on conjecture aussi que le meilleur ordre est 2). ❦ Voir aussi la discussion autour de la constante de Hinčin (Khintchine) pour une propriété amusante des nombres aléatoires que n'ont pas les nombres génériques : cette fois-ci, s'agissant de e, ni Monsieur Eugsebel ni Monsieur Eriab n'ont raison, la moyenne géométrique des coefficients de son écriture en fraction continuée tend vers +∞, donc ni la constante de Hinčin qu'avait prédite Monsieur Eugsebel ni l'absence de limite qu'avait prédite Monsieur Eriab (s'agissant de π, expérimentalement, Monsieur Eugsebel a raison).

Il faut que je souligne clairement ceci : ni e ni π ne sont ni aléatoire ni générique (en effet, un nombre aléatoire ou générique ne peut pas être calculable, et e et π sont de toute évidence calculables), ils font seulement semblant de l'être : j'ai envie de les appeler empiriquement aléatoires ou pseudoaléatoires. Et à la limite, la question n'est pas tant pourquoi ils sont pseudoaléatoires que pourquoi ils ne sont pas « empiriquement génériques » ou « pseudogénériques ».

En fait, je ne sais même pas si on pourrait construire un « générateur pseudogénérique » simple comme on peut construire un générateur pseudoaléatoire, ou à quoi ça ressemblerait. À plus forte raison, je ne connais aucun nombre « naturel » (i.e., apparu en mathématiques pour d'autres raisons) qui aurait ne serait-ce qu'expérimentalement l'air d'être pseudogénérique, alors que les nombres expérimentalement pseudoaléatoires abondent. (Et comme je l'avais déjà signalé dans une autre entrée, je me demande bien si on pourrait dire des choses en crypto relativement à un oracle générique alors que la crypto fait beaucoup de choses relativement à un oracle aléatoire.)

Je pense que c'est là une question philosophique subtile et profonde, et sur laquelle je suis surpris de trouver que personne ne semble avoir ne serait-ce que tenté de dire quoi que ce soit.

(lundi)

Une bizarrerie géographique parisienne enfin corrigée

Je m'étais plaint ici (et surtout pour plus de détails) de cette bizarrerie géographique parisienne : depuis le pont National (le plus en amont sur la Seine après celui du périphérique), il n'y avait aucun moyen d'aller à l'avenue des Terroirs de France (ou, disons, à Bercy-Village) sauf à contourner une énorme emprise SNCF. L'absurdité est surtout qu'il n'est pas possible, côté rive droite, de passer à pied sous le pont National (ou du moins, en principe interdit ; c'est possible si on veut bien se faufiler dans une glissière de sécurité avec une sorte d'autoroute à côté).

Cette bizarrie était devenue encore plus absurde avec l'arrivée du tramway à ce niveau : on a un arrêt de tramway (Baron le Roy, sur le boulevard Poniatowski, juste un peu après le pont National) et une station de métro (Cour Saint-Émilion, ligne 14, qui dessert Bercy-Village) distantes à vol d'oiseau de 550m, mais le plus court chemin à pied pour les relier faisait quelque chose comme 1.8km (passer rive gauche par le pont National, descendre la Seine jusqu'au pont de Tolbiac, et revenir jusqu'à Cour Saint-Émilion ; ou bien, en restant rive droite, continuer jusqu'à la rue de Charenton, passer sous les voies au niveau de la rue Proudhon, et revenir depuis la place Lachambeaudie jusqu'à Cour Saint-Émilion, ce qui est encore plus long).

[Liaison piétonne Bercy-Charenton, côté Bercy]La situation a enfin été corrigée : un passage piéton a été aménagé à travers l'emprise SNCF (traversant la Petite Ceinture désaffectée puis des espèces d'entrepots dont je ne sais pas s'ils servent encore mais dont certains sont visiblement squattés). Ce passage est d'ailleurs évidemment visible sur OpenStreetMap. J'imagine qu'il a fallu se battre contre beaucoup de moulins à vent pour avoir le droit de l'ouvrir.

Dans le même genre, mon poussinet et moi avons vérifié qu'il est possible (je ne sais pas si c'est nouveau) d'aller au centre commercial Bercy 2 à pied. Ce n'est pas complètement évident, et pas du tout agréable, mais c'est possible, sans franchir une glissière de sécurité. Il y a même (au moins) deux moyens pour ça : l'un, depuis le même arrêt Baron le Roy du tramway, consiste à passer par l'échangeur de Bercy et devant ce qui est je crois une préfourrière, il y a vaguement des indications. L'autre consiste à partir de la porte de Charenton, à rejoindre le quartier Valmy de Charenton-le-Pont, et à passer par la passerelle de Valmy, qui franchit une autre grosse emprise SNCF, ici sur OpenStreetMap, pour arriver au quartier Bercy de Charenton, où se trouve le centre commercial.

(dimanche)

Une remarque sur la TVA et les arrondis

La TVA normale en France est de 20%. Est-ce que la loi ou les règles de comptabilité imposent que le commerçant définisse un prix hors taxes (exact en centimes), ajoute la TVA avec une règle bien définie d'arrondi (j'imagine : l'arrondi au plus proche), et calcule ainsi le prix toutes taxes comprises qui sera affiché ?

Parce que si c'est le cas, indépendamment de la valeur de la TVA et de la règle de calcul de l'arrondi, il y a des prix TTC qui ne devraient pas être possibles. Pour s'en convaincre, il suffit de considérer les N prix hors taxes différents 0.01¤, 0.02¤, 0.03¤, etc., jusqu'à (N/100)¤ pour une valeur de N assez grande : en ajoutant la valeur de la taxe, on obtient N prix TTC (probablement différents, peut-être même pas si le mode d'arrondi est très bizarre, mais peu importe) jusqu'à (N′/100)¤ pour un N′>N (puisque la taxe augmente les prix, au moins s'ils ne sont pas très petits !). Or il y a N′ valeurs exactes au centime entre 0.01¤ et (N′/100)¤, donc les N valeurs considérées ne les prennent pas toutes. Il y a donc des prix TTC qu'on ne devrait jamais voir apparaître.

Et pour une valeur de TVA de 20% et l'arrondi au plus proche, il est vraiment facile de faire le cacul : ajouter la TVA revient à multiplier par 1.20 = 6/5, donc les pris hors taxes 0.01€, 0.02€, 0.03€, 0.04€ et 0.05€ deviennent les pris TTC 0.01€, 0.02€, 0.04€, 0.05€ et 0.06€ (ce dernier étant exact et sans arrondi), et ensuite tout est périodique de période six centimes sur le prix TTC (pour cinq centimes sur le prix HT). Autrement dit, si c'est l'arrondi au plus proche qui est pratiqué, on ne devrait jamais voir un prix TTC dont la valeur exprimée en centimes soit congrue à 3 modulo 6 (ou, ce qui revient au même d'après le théorème chinois : soit impaire et dont la somme des chiffres soit multiple de 3). Par exemple, un prix TTC de 2.25€ devrait être impossible : si le prix hors taxes est 1.87€, on arrondit à 2.24€, et s'il est de 1.88€, on arrondit à 2.26€, mais jamais à 2.25€. Si l'arrondi est fait à l'inférieur ou au supérieur, les valeurs impossibles seront différentes (pas de montants en centimes congrus à 5 modulo 6 dans le cas de l'arrondi à l'inférieur, et pas de montants en centimes congrus à 1 modulo 6 dans le cas de l'arrondi au supérieur), mais dans tous les cas, comme je l'ai montré ci-dessus, il devrait y avoir des valeurs impossibles.

Il se peut que je me trompe en pensant qu'on est tenu de définir un prix HT exact en centimes et appliquer la TVA seulement ensuite. Néanmoins, même si ce n'est pas une obligation, il est bien possible que certains commerçants procèdent ainsi : je devrais m'amuser à faire des statistiques sur les valeurs modulo 6 des prix en centimes des choses que j'achète au taux normal de TVA, pour voir si on trouve effectivement certaines valeurs moins souvent que d'autres.

J'ai commencé à regarder ma liste de courses d'aujourd'hui, mais je me suis rappelé que c'était de l'alimentaire, taxé à 5.5% ; or pour ça, vu que 1.055 = 211/200, il faut regarder les valeurs des prix modulo 211 : et, si je sais calculer modulo 6 de tête, je ne suis pas calculateur prodige, je ne calcule pas un reste de division euclidienne par 211 de tête pour voir s'il serait par hasard égal à 10, 29, 48, 67, 86, 105, 125, 144, 163, 182 ou 201 (valeurs impossibles si arrondi au plus proche). Néanmoins, on a inventé un truc appelé les ordinateurs, qui m'ont permis de trouver parmi mes achats taxés à 5.5% un prix de 2.01€ (un lot de yaourts) incompatible avec un arrondi au plus proche (1.90€ HT donne alors 2.00€ TTC tandis que 1.91€ HT donne 2.02€ TTC), un autre de 3.06€ (un lot de tiramisù) incompatible avec un arrondi à l'inférieur (dans ce cas, 2.90€ donne 3.05€ et 2.91€ donne 3.07€), et encore un de 2.50€ (un lot de carottes) incompatible avec un arrondi au supérieur (pour lequel 2.36€ donne 2.49€ et 2.37€ donne 2.51€). Maintenant, il est fort possible que la règle (définir un prix HT en centimes, appliquer la TVA et arrondir) ne soit pas juste, ou comporte des cas spéciaux par exemple pour les lots de plusieurs produits (de toute façon, il faudra bien décider, si on vend plusieurs articles identiques : comme le client s'attend à ce que les prix TTC s'ajoutent exactement, j'imagine que la TVA se calcule et s'arrondit ligne à ligne).

Bref, tout ceci mériterait d'être tiré au clair ! Si je peux faire un procès à Carrefour pour m'avoir arnaqué d'un centime sur le calcul de l'arrondi de la TVA dans 11 cas sur 211, je pourrais faire quelque chose comme 0.02% d'économies.

(dimanche)

Petite balade sur la Grande Terrasse

[La Grande Terrasse de Saint-Germain]Mon poussinet et moi avons profité hier du temps pas trop chaud pour aller visiter la Grande Terrasse de Saint-Germain-en-Laye, créée par André Le Nôtre pour permettre à Louis XIV d'observer une vue dégagée sur les gratte-ciel et tours de bureaux de La Défense, ce pour quoi il a parfaitement choisi son endroit. (Il a aussi eu la bonne idée de la mettre juste à côté d'un arrêt du RER A, comme quoi, Monsieur Le Nôtre calculait bien les choses.) Il faut dire qu'elle est assez impressionnante par sa simple longueur : environ 2km (selon d'où à où on compte) et apparemment c'est une longueur qui plaît aux joggueurs : il faut croire que Louis XIV devait aimer faire un petit footing le matin quand il résidait à Saint-Germain ; et pour les motiver, Le Nôtre a rendu la terrasse pas complètement plate (elle forme un léger V), provoquant un effet d'optique qui donne l'impression depuis l'extrémité sud qu'elle est moins longue qu'elle ne l'est vraiment (et surtout, quand on en est environ au quart, qu'on arrive à la moitié ; j'en déduis là aussi que Louis XIV devait avoir besoin de motivation dans ses séances de course à pied). La vue est beaucoup plus impressionnante que n'en donnent l'impression les photos suivantes qui montrent surtout que mon téléphone n'est pas terrible pour en prendre.

[Panorama depuis la Grande Terrasse de Saint-Germain]

(mercredi)

Je résous le bug le plus bizarre que j'aie jamais vu

Commençons par raconter un peu ma vie. Vendredi j'ai enfin, et avec immense soulagement, soumis pour publication un article sur lequel mon co-auteur et moi travaillions depuis maintenant environ un an et demi et qui fait finalement 80 pages (si j'ai le courage, j'essaierai de vulgariser un peu le contenu dans ce blog, mais en fait je crois que j'ai surtout envie de penser à autre chose jusqu'à ce que le relecteur nous envoie des zillions de corrections). Ce week-end je suis allé chez mes parents pour me détendre un peu avant d'attaquer la montagne de choses que j'ai mises de côté entre autres pour avoir le temps de finir cet article. Bref.

Les choses ne se sont pas tout à fait passées de façon aussi détendante(?) que je l'avais espéré. D'abord il a plu toute la journée comme les larmes d'une veuve, ce qui n'aide jamais. Ensuite, il y a eu l'affaire mystérieuse d'un dongle wifi qui a disparu corps et âme et au sujet duquel Hercule Poirot enquête sans doute encore (j'avoue que j'avais déjà eu plein de problèmes avec le wifi, mais le coup de l'antenne qui disparaît physiquement, je n'avais pas encore vu). Mais surtout, il y a eu un bug de Firefox, qui semblait déjà étrange au début et qui est finalement devenu le bug le plus bizarre que j'aie jamais rencontré.

Il faut savoir que j'ai un PC chez mes parents (que j'utilise principalement pour faire des backups) dont la config est presque exactement identique à celle de mon PC chez moi — justement pour tenter d'éviter les surprises de choses qui fonctionneraient différemment d'un côté et de l'autre. La principale différence est que celui chez mes parents a un système (GNU/Linux) 32-bits alors que celui chez moi est 64-bits (et encore le noyau est-il 64-bits des deux côtés). Mais à part ça, j'essaie d'installer presque toujours les mêmes packages, de faire les mises à jour en même temps, etc., et mon $HOME est synchronisé entre les deux machines (justement pour servir de sauvegarde). Je compile aussi des Firefox de la même manière sur les deux machines (juste l'un en 32-bits et l'autre en 64-bits), à partir des mêmes sources, et je m'attends donc à ce qu'ils fonctionnent de la même manière.

Et là voilà, j'arrive chez mes parents, je lance mon Firefox, je veux faire une recherche Google (à cause d'un petit problème sur mon mobile, une merdouille qui ne vaut même pas la peine d'être racontée), et je tombe sur un bug bizarre : la barre d'adresse ne marche pas. Plus exactement, je peux taper des choses dedans, il propose des complétions, mais la touche entrée ne fait rien, pas plus que la petite flèche censée aller à l'adresse indiquée, ou même le fait de cliquer sur une complétion — bref, la barre est essentiellement inactive. À part ça, tout semble marcher normalement : la touche entrée marche parfaitement ailleurs dans le navigateur, je peux cliquer sur des liens dans des pages Web, bref, il n'y a en gros que la barre d'adresse qui dysfonctionne.

Évidemment, c'est le genre de symptôme qui peut avoir un million de causes, rien de ce que je peux trouver en ligne n'est susceptible de me concerner. Autant dire que le docteur House voit son patient commencer à faire de la fièvre, il est loin de se douter jusqu'où le lapin blanc va le mener.

Commence donc mon enquête pour essayer de comprendre ce qui se passe. Est-ce peut-être mon profil Firefox qui est corrompu ou un problème avec une extension ou un plugin que j'aurais ? Non, le bug se reproduit encore avec un profil vierge. Mais de façon non complètement reproductible : parfois il cesse d'exister sur un profil donné, et il ne réapparaît alors pas, alors que sur mon profil normal, il persiste. J'explore une forêt de fausses pistes. Je vérifie que le problème se produit encore en lançant Firefox sur un affichage distant (en export DISPLAY, comme on dit en jargon Unix). Je constate un message d'erreur suspect dans la console du navigateur ayant à voir avec l'initialisation des moteurs de recherche (NS_ERROR_FAILURE: Failure'Failure' when calling method: [nsIBrowserSearchService::currentEngine] browser.js:11478) — mais pourquoi celle-ci échouerait-elle ?

Ma première hypothèse porte sur la compilation : on parle d'un Firefox que j'ai compilé moi-même, ce que je fais régulièrement, mais lorsque j'ai compilé celui-là, il y a eu une coupure de courant qui a éteint la machine ; j'ai bien sûr vérifié les systèmes de fichiers, effacé le sous-arbre de compilation et redémarré la compilation à zéro, mais il est possible que le plantage ait eu lieu au moment où la compilation générait un script Python qui sert par la suite, il est possible que celui-ci ait été corrompu par le plantage (typiquement, remplacé par des zéros, il semble que ça arrive sous le système de fichiers xfs), qu'il soit situé dans l'arbre de compilation « permanent » (avec les sources, plutôt que dans l'arbre des résultats de compilation que j'ai effacé pour recommencer à zéro : Firefox fait ça quand il s'agit de scripts qui servent à la compilation elle-même), qu'il soit utilisé pour générer un fichier décrivant les moteurs de recherche et qu'à cause de ça ceux-ci ne s'initialisent pas bien. L'hypothèse était raisonnable (je la mentionne pour montrer le genre de fausses pistes que j'ai pu explorer), mais j'ai vite vérifié qu'elle était fausse : un Firefox officiel compilé par Mozilla présente les mêmes symptômes (pour toute version entre la 30 « stable » et la 33 « nightly »).

Je me convaincs que le symptôme initial (la barre d'adresse qui ne marche pas) est bien lié à l'erreur signalée sur l'échec d'initialisation des moteurs de recherche, mais ça ne m'apprend toujours pas sa cause. Et surtout, pourquoi suis-je le seul à rencontrer ce problème ? (on se doute bien que, même en se limitant aux utilisateurs GNU/Linux avec un système 32-bits, l'ensemble des versions de Firefox entre 30 et 33 est pas mal testé : s'il y avait un bug qui le rendait quasi inutilisable, ça se saurait assez vite).

Dimanche soir, j'ai soumis un bug-report à Bugzilla (#1034984, mais n'allez pas voir tout de suite si vous ne voulez pas vous faire spoiler la fin de l'histoire !). Heureusement, ils sont assez réactifs et m'ont appris l'existence d'une préférence browser.search.log qui permet d'afficher des informations de debug sur ce que fait le mécanisme de recherche. Et là, je découvre qu'il essaye d'ouvrir un fichier /usr/local/opt/firefox-30.0.MOZ/browser/searchplugins/ing.xml qui n'existe pas : ce qui existe, c'est un fichier /usr/local/opt/firefox-30.0.MOZ/browser/searchplugins/bing.xml (décrivant à Firefox le fonctionnement du moteur de recherche Bing). Voici qui fait remonter la cause un peu plus loin dans le trou du lapin blanc, mais le mystère n'en est que plus épais : pourquoi diable mon Firefox aurait-il l'idée de chercher à ouvrir un fichier ing.xml quand il devrait aller prendre bing.xml, et toujours, pourquoi serais-je le seul à rencontrer ce problème ?

En allant fouiller un peu dans le code source du mécanisme de gestion des moteurs de recherche, je comprends un petit peu mieux pourquoi le bug n'était pas déterministe (il y a deux mécanismes d'initialisation, un « synchrone » et un « asynchrone », il est probable que l'utilisation de l'un ou de l'autre ne soit pas déterministe, et c'est l'« asynchrone » qui échoue). La cause est un peu mieux cernée : c'est l'objet OS.File.DirectoryIterator qui renvoie des noms tronqués d'un caractère (du coup, ça donne ce ing.xml, qui n'existe pas et que Firefox n'arrive pas à ouvrir). Je constate que c'est systématique — quel que soit le répertoire que je lui fais lister, il manque toujours le premier caractère des noms de fichier. Mais la raison profonde n'est pas plus claire pour un sou, ni pourquoi je suis le seul concerné.

J'ai passé un temps fou à lancer Firefox dans un nombre incroyable de combinaisons ordinateur×configuration, dans des machines virtuelles ou sur des vrais ordinateurs, et à m'arracher les cheveux : j'ai beau tenter d'utiliser une config absolument identique dans mes machines virtuelles (jusqu'au noyau 64-bits pour un userland 32-bits ; et en essayant de reprendre exactement les versions de toutes les bibliothèques listées dans le /proc/$PID/maps du Firefox en cours d'exécution), impossible de reproduire le bug. Il n'y a apparemment que sur mon PC chez mes parents qu'il se produit !

Une nouvelle option de debug (toolkit.osfile.log) me montre que le bug vient de bien profondément dans Firefox : les threads de travail voient bien passer des noms tronqués d'un caractère. J'en ai appris beaucoup sur la façon de débugguer du JavaScript (et comment débugguer le JavaScript de Firefox lui-même… ce qui n'est malheureusement pas possible dans les threads de travail), et sur la façon dont s'organise le source de ce machin (à ce stade-là, les bouts incriminés étaient principalement ici et ), mais toujours sans comprendre quelle pouvait être la cause profonde du problème, ou de sa rareté.

Et puis, en regardant un commentaire dans le source,

       // Structure |dirent|
       // Building this type is rather complicated, as its layout varies between
       // variants of Unix. For this reason, we rely on a number of constants
       // (computed in C from the C data structures) that give us the layout.
       // The structure we compute looks like
       //  { int8_t[...] before_d_type; // ignored content
       //    int8_t      d_type       ;
       //    int8_t[...] before_d_name; // ignored content
       //    char[...]   d_name;
       //    };

— j'ai eu une illumination (si le struct dirent n'est pas bien interprété, c'est qu'il y a une différence d'ABI quelque part, or quelle pourrait bien être la raison de cette différence d'ABI ?), et surtout, je me suis rendu compte que j'aurais dû bondir plus tôt en consultant la liste des bibliothèques chargées en mémoire par Firefox (/proc/$PID/maps) et en voyant /lib/libc.so.5.4.46 y apparaître.

Le problème, c'est la libc5. Ceux qui connaissent bien Linux auront compris de quoi je veux parler, mais pour les autres, une explication s'impose : la libc, ou bibliothèque C du système, c'est la bibliothèque qui contient les fonctions standard du langage C, et qui sert, de fait, sur un système Unix, d'interface entre le noyau et les programmes utilisateurs (même s'ils ne sont pas écrits en C, dans essentiellement tous les cas, ils s'appuient sur la bibliothèque C). La bibliothèque C de GNU/Linux a une histoire un peu compliquée, mais disons qu'entre environ 1995 et 1999, la version standard de la bibliothèque C de GNU/Linux était appelée libc5, et qu'entre 1997 et 2000 (ça a pris du temps !) s'est effectué une migration vers une nouvelle version, profondément incompatible, appelée libc6 — c'est celle qui est encore utilisée maintenant (il y a eu beaucoup d'évolutions depuis, mais aucune ne marquant un changement incompatible). La libc5 a continué à être un peu maintenue jusque vers 2003, et depuis 2003 on peut la considérer comme complètement obsolète (et elle n'existe carrément pas sur les systèmes 64-bits : il n'y a que sur les 32-bits qu'il y a même la possibilité d'avoir une libc5). Comme je suis du genre conservateur (pour ne pas dire dinosaure), j'ai encore une libc5 fonctionnelle sur mes systèmes GNU/Linux 32-bits, ce qui n'est évidemment pas le cas de tous les gens qui installent des Ubuntu ou autres distributions récentes (et a fortiori tous les systèmes 64-bits).

Et le bug, c'est que l'interface JavaScript de Firefox servant à charger directement des fonctions de la libc (qui n'est elle-même pas énormément utilisée, en fait : il y a toutes sortes d'autres mécanismes d'appel possibles) va chercher assez stupidement n'importe quelle bibliothèque qui s'appelle libc qu'elle trouve, et dans mon cas elle trouve et charge la libc5. Assez inexplicablement, ça ne plante pas tout le navigateur de se retrouver avec deux versions incompatibles de la libc (c'est bien sûr la version moderne, la libc6, qui sert pour presque tout, et avec laquelle Firefox a été compilé), mais dans l'appel à readdir exécuté depuis ce code JavaScript-là, c'est la version de la libc5 qui est utilisée. Or l'interface d'appel diffère de celle de la libc6 (prévue à la compilation) en ce que, dans la structure qui sert à retourner le résultat, l'emplacement du nom de fichier a été décalé d'un octet (j'imagine pour des raisons d'alignement) : du coup, tout était lu de travers par juste un octet.

Et vérification faite, si je retire le fichier /lib/libc.so.5.4.46 de mon système, mon Firefox se remet à marcher normalement.

[Une peluche de Mozilla]Tout de même, la chaîne de causalité est assez impressionnante : la présence de la libc5 et Firefox décidant stupidement de l'ouvrir fait qu'une certaine interface JavaScript vers la libc ne fonctionne pas tout à fait correctement, ce qui a comme conséquence que les noms de fichier sont tronqués d'un caractère, et le seul effet détectable est que le système de moteurs de recherche essaie d'ouvrir ing.xml au lieu du bing.xml qui se trouve dans le répertoire, échoue, et du coup la barre d'adresse ne fonctionne plus ! Et seul quelqu'un ayant encore une libc5 installée sur un système 32-bits pouvait détecter le problème (et encore, il y a peut-être des conditions supplémentaires pour que Firefox décide de la lire, et encore d'autres pour que l'initialisation des moteurs de recherche passe par le chemin asynchrone). Voilà le genre de bugs complètement bizarres et obscurs qui aurait pu rester indétecté pendant longtemps !

Il me semble que j'ai mérité une médaille (en chocolat).

(mardi)

Quelques questions de langue et de cohérence

Je dis souvent que s'agissant de conventions linguistiques et typographiques, le plus important est d'essayer d'être un peu cohérent et systématique. Et pour ça, il est important de se fixer des règles dont on trouve la logique satisfaisante, de manière à ne pas toujours changer d'avis. Mais ce n'est pas facile quand on se met à couper les cheveux en quatre.

Voici un exemple du genre de questions dont je veux parler : si je dois faire référence (alors que je parle français ou anglais) au premier président de la Chine communiste, dois-je l'appeler Mao Zedong ou Zedong Mao ? (Ou Máo Zédōng en écrivant les tons, mais pour une fois ce n'est pas ça qui me préoccupe.) Le fait est que le nom de famille est Mao (), et la question est de savoir comment l'ordonner par rapport au prénom (enfin, au nom personnel, qu'il vaut mieux ne pas appeler prénom quand on discute justement de l'ordre de placement). Les sinophiles me disent généralement que la question ne fait pas l'ombre d'un doute, en chinois le nom de famille précède le nom personnel : c'est incontestablement le cas quand on utilise un nom chinois en chinois, mais ici je parle d'utiliser un nom chinois en français, et il s'agit donc de se demander qui l'emporte, la convention chinoise ou la convention française — ou plus exactement, de savoir si l'ordre des parties d'un nom propre est relié au nom lui-même ou à la langue dans laquelle on s'exprime, et ce n'est pas évident du tout.

Il est sûr que la question ne peut pas admettre de réponse pleinement satisfaisante. Il y a trop de cas dictés par l'habitude pour qu'on puisse espérer être complètement cohérent : s'agissant de Mao Zedong, l'usage français s'est figé dans cet ordre, mais inversement, il y a un nombre non négligeable, par exemple, de Hongrois, pour lesquels on a pris l'habitude de retranscrire leur nom dans l'ordre prénom+nom (par exemple Erdős Pál → Paul Erdős), et de toute façon les célébrités ont souvent des bizarreries de nommage (pourquoi parle-t-on de Jules César mais de César Auguste ? — noter qu'aucune des deux parties, ici, n'est un prénom, le prénom de naissance serait Gaius pour les deux, mais Auguste a changé son prénom en Imperator en ~38 ; pourquoi Dante Alighieri, Michelangelo Buonarroti et Rembrandt Harmenszoon van Rijn sont-ils connus par leur prénom ? à la fin, il faut cesser de chercher une logique et reconnaître que l'usage fait loi). On peut néanmoins chercher à systématiser l'usage pour les personnes qui ne sont pas spécialement célèbres. Une solution est de choisir un ordre quelconque et de mettre le nom de famille en petites capitales ou de le souligner d'une manière ou d'une autre (quand il y en a un identifiable, ce qui n'est pas toujours le cas, notamment pour certains noms indiens ou les noms islandais), et d'écrire Máo Zédōng ; je ne suis pas fan de cette solution, que je trouve assez laide (quand on a un texte plein de noms propres, ça donne une impression vraiment trop didactique-pontifiante), mais il faut admettre que c'est ce qu'il y a de plus clair.

Voici un problème apparenté : supposons que je veuille parler de la personne élue à la tête d'une municipalité belge, disons, Namur : dois-je parler du maire de Namur ou du bourgmestre de Namur ? Là aussi, on me sort généralement une réponse un peu toute faite : en Belgique, on parle de bourgmestres — certes, c'est-à-dire que les Belges utilisent le terme bourgmestre pour désigner l'édile de leurs villes, mais moi je ne suis pas Belge, et je parle, si j'ose dire, dans une variante du fr-FR et non du fr-BE. Ce que je veux dire, c'est qu'il n'est pas du tout clair si le choix d'un titre comme maire ou bourgmestre doit être déterminé par la variante régionale du français qu'on parle ou par le pays qui attribue la fonction officielle. (Dans le genre, si je veux désigner l'adresse rue Rogier 70 à Namur, il semble raisonnable de penser que je doive mettre le numéro après le nom de la rue parce que c'est ainsi qu'on fait en Belgique, mais nettement moins raisonnable de penser que je doive obligatoirement prononcer septante parce que les Belges disent ça et que c'est une adresse en Belgique.)

En l'occurrence, je suis plutôt tenté de considérer l'usage du mot bourgmestre comme un régionalisme belge (qui, du coup, apparaît dans les textes légaux définissant la fonction) que comme une fonction spécifique dont le nom doit être préservé. Après tout, pour les villes néerlandaises, allemandes et autrichiennes, on a bien tendance à préférer en français (de France) le terme de maire même si ces gens devraient logiquement être tout autant bourgmestres que leurs homologues belges. Et je n'ai presque jamais entendu utiliser en français le mot alcade pour une ville espagnole ou syndic pour une ville italienne alors que ces mots existent. Mais surtout, je vois mal quelle différence fonctionnelle on peut trouver à l'usage d'un mot ou de l'autre : les anglais disent presque toujours mayor pour la personne à la tête d'une ville, ou qu'elle soit, même si la transcription burgomaster ou burghermaster existe en principe, et ça ne semble pas causer de problème. De toute manière, j'ai déjà souligné (sur l'exemple du président du Conseil et ses variantes) à quel point les titres officiels sont la province du Club Contexte. Bref, il me semble plus simple et finalement plus cohérent de parler de maire partout, y compris pour les villes belges, ou alors de parler de bourgmestre partout si on préfère ce mot, mais en tout cas de ne pas faire la distinction selon le pays ou le titre officiel.

Encore une question du même acabit : il est fréquent d'utiliser en français des guillemets « comme ceci », en anglais “comme ça” (ou ‘ça’) et en allemand „ainsi“ (ou »ainsi«), à tel point que certains considèrent que c'est une obligation de conformer le choix des guillemets au choix de la langue (à mon avis, c'est parfaitement stupide, cf. ci-dessous). Maintenant, en admettant qu'on fasse ces choix pour un texte entièrement écrit dans une langue, la question se pose encore de savoir ce qu'on doit faire quand on en mélange plusieurs : le choix des guillemets (et autres conventions typographiques apparentées) doit-il être dicté par la langue majoritaire du texte (pour avoir une même convention sur tout le texte), par la langue immédiatement autour, ou, dans le cas des guillemets, par la langue intérieure aux guillemets ? — et de nouveau, ce n'est pas du tout évident. Je fais personnellement le choix de régler les conventions selon la langue immédiatement autour (et donc, dans le cas des guillemets, extérieure aux guillemets), mais pour revenir à ce que je disais tout au début, le plus important me semble d'essayer d'être cohérent (et par exemple, quoi qu'en disent les maniaques du Lexique des règles typographiques en usage à l'Imprimerie Nationale — ouvrage d'ailleurs fort mal écrit et fort peu cohérent[#] — je trouve parfaitement raisonnable qu'on décide d'utiliser les mêmes conventions typographiques dans tout ce qu'on écrit, indépendamment de la langue, pour plus d'uniformité).

[#] Le plus ironique étant que ce Lexique préconise très clairement d'utiliser des accents sur les capitales alors que l'Imprimerie Nationale édite elle-même le Journal Officiel de la République française sans mettre ces accents ! Et je remarque aussi que selon les règles qu'ils donnent sur l'emploi des majuscules (ou du moins l'espèce de cafouillis qui tient lieu de règles dans ce Lexique) il serait plus logique d'écrire Imprimerie nationale et Journal officiel que Imprimerie Nationale et Journal Officiel. Bref, une chose est sûre, c'est qu'ils ne savent pas ce qu'ils veulent. Je ne comprends pas que ce livre ait malgré tout du succès auprès des maniaques ! Mais au sujet des majuscules à Imprimerie Nationale, voici une autre question du même genre : faut-il suivre l'usage défini par l'organisme qui porte le sigle ou bien uniformiser dans le texte ? (autrement dit, si moi je trouve plus cohérent d'écrire Imprimerie nationale parce que l'adjectif suit le nom, dois-je quand même mettre une majuscule à celui-ci parce que ce choix fait partie du nom ou dois-je considérer que ma convention l'emporte ?).

(vendredi)

Petit tour de magie 2-adique

Je me demande régulièrement s'il serait possible de trouver une application des nombres p-adiques ailleurs qu'en mathématiques ; par exemple, une application des 2-adiques en informatique (ce qui semble le plus plausible, parce que les ordinateurs, manipulant des nombres binaires, manipulent en fait des entiers 2-adiques approchés). Je n'ai pour l'instant rien trouvé de bien convaincant. Voici cependant un exemple qui pourrait servir avec un peu d'imagination, et qui en tout cas fait un « tour de magie » rigolo :

Soit a un entier impair écrit en binaire, disons, sur 64 bits, dont on suppose qu'il est le carré d'un entier : on cherche à retrouver cette racine carrée (exacte). Voici une façon de s'y prendre : (1) itérer, en partant de y=1, la fonction y ↦ 2ya·y², jusqu'à tomber sur un point fixe qu'on notera b (note : tous les calculs sont faits en binaire sur la même largeur, disons 64 bits ; comme il est habituel en informatique, on jette les bits supérieurs) ; (2) itérer, en partant de x=1, la fonction xx·(3−b·x²)/2. Autrement dit, en C :

unsigned long
exact_odd_square_root (unsigned long a) {
  unsigned long y = 1;
  for ( unsigned long yn = 0 ; y != (yn = 2*y - a*y*y) ; y = yn );
  unsigned long x = 1;
  for ( unsigned long xn = 0 ; x != (xn = x*((3-y*x*x)>>1)) ; x = xn );
  if ( x & ((((unsigned long)(-1))>>2)+1) )
    x = -x;
  return x & ((unsigned long)(-1))>>1;
}

(Les dernières lignes servent à corriger le nombre : il y a quatre valeurs de x sur vérifiant x²=a, différant par le bit de poids fort et/ou par un changement de signe global — la fonction renvoie donc celui dont les deux bits de poids fort valent 0. L'écriture ((((unsigned long)(-1))>>2)+1) sert à représenter le nombre ayant 1 juste au-dessous du poids fort sans avoir à faire d'hypothèse sur la taille des unsigned long.)

La fonction est évidemment limitée (on pourrait calculer une fonction exact_square_root() en décalant le nombre du nombre de bits adéquat — forcément pair — jusqu'à trouver un nombre impair, en appliquant la fonction exact_odd_square_root() ci-dessus, puis en refaisant le décalage vers la gauche de la moitié du nombre de bits, mais la gestion des bits de poids fort serait encore un peu plus pénible). Il y a cependant un truc rigolo, c'est qu'elle retrouve la racine carrée même si le calcul du carré a débordé (par exemple, sur 64 bits, si on fait 1000000000001*1000000000001, on trouve 2003766205206896641 et pas 1000000000002000000000001, mais la fonction ci-dessus retrouve bien 1000000000001 comme racine carrée pour cette valeur), du moins si les deux bits de poids fort valent 1 (on ne peut pas faire mieux). Par ailleurs, le nombre d'itérations est très petit (quelque chose comme 6 au pire dans chaque boucle pour un nombre de 64 bits), donc on pourrait dérouler les boucles.

L'explication 2-adique est vraiment facile : la première itération calcule l'inverse 2-adique b de a par une méthode de Newton, la seconde calcule la racine carrée par une méthode du même genre (on peut peut-être la présenter comme une méthode de Newton, en tout cas j'ai cherché un polynôme ayant un point fixe superattractif où on veut). J'imagine que je ne suis pas le premier à écrire un truc de ce genre, je n'ai pas cherché. Par contre, ce que j'aimerais bien, c'est trouver des exemples plus frappants ou plus utiles.

(jeudi)

Quelques petits jeux avec l'algèbre commutative

Alice et Bob jouent au jeu suivant : dans l'anneau k[t1,…,tn] des polynômes en n indéterminées sur un corps k, chacun choisit à tour de rôle un polynôme f, la règle étant qu'on n'a pas le droit de choisir un polynôme de la forme g1·f1 + ⋯ + gr·frf1,…,fr sont les polynômes qui ont déjà été joués (et notamment, le polynôme nul) ; ou, si on préfère, l'idéal (f1,…,fr) = {g1·f1 + ⋯ + gr·fr} doit grandir strictement à chaque étape ; lorsque le polynôme 1 (donc, n'importe quel polynôme) peut s'écrire sous la forme g1·f1 + ⋯ + gr·fr, le joueur qui vient de jouer a perdu (autrement dit, on joue à la variante « misère » du jeu : celui qui ne peut pas jouer a gagné ; l'autre variante n'est pas intéressante, parce que qu'on gagne immédiatement en jouant le polynôme 1). Question : qui a une stratégie gagnante ? (En fonction de n et, éventuellement, du corps k.)

J'avoue ne pas savoir dire grand-chose d'intelligent sur ce problème. Si n=1, dans k[x], Alice (le premier joueur) a une stratégie gagnante évidente, consistant à jouer x (l'unique indéterminée). Si n=2, dans k[x,y], il me semble que le premier joueur gagne encore en jouant y² (si Bob réplique par y, Alice gagne parce qu'on est ramené au cas n=1 ; dans tout autre cas, l'intersection entre la droite y=0 comptée avec multiplicité 2 et la courbe algébrique d'équation définie par ce que Bob aura joué sera un nombre fini de points avec des multiplicités paires, et Alice peut alors sans difficulté au coup suivant tuer tous ces points sauf un qu'elle garde avec multiplicité 1, ce qui gagne le jeu), mais je suis loin d'avoir vérifié les détails et il n'est pas du tout improbable que je me sois trompé. Ce papier montre cependant qu'Alice a bien une stratégie gagnante, soit avec des arguments du même genre en jouant y²−x³ (§6.2), soit avec un argument différent et peut-être plus rigolo en jouant y²−x³+x−1 (corollaires 6.4–6.5). J'ai vaguement tendance à croire qu'Alice gagne toujours quand on part d'un anneau de polynômes, mais je ne sais vraiment pas le prouver. (Ce qui ne veut pas dire que ce soit très dur : je n'ai pas réfléchi très fort.)

Géométriquement, le jeu consiste à partir de l'espace affine de dimension n et à intersecter avec des hypersurfaces f=0 de façon à fabriquer des « sous-schémas fermés » de plus en plus petits, celui qui aboutit sur le vide ayant perdu (dans la variante « misère »).

Le jeu sous une forme un peu plus générale s'écrit ainsi : si R est un anneau [commutatif] nœthérien (on prend R=k[t1,…,tn] dans l'exemple ci-dessus), chacun des deux joueurs à son tour remplace R par le quotient de celui-ci par un de ses éléments non nuls (i.e., par un idéal principal non nul), et le premier qui tombe sur l'anneau nul a perdu (dans la variante « misère »). Le jeu termine nécessairement en temps fini car on construit une suite strictement croissante d'idéaux de l'anneau nœthérien R de départ (ceux par quoi on a quotienté jusqu'à présent). Bien sûr, je ne suis pas le premier à y penser, c'est vraiment tout naturel une fois qu'on se rappelle que tout processus terminant conduit à un jeu impartial. On peut bien sûr jouer avec toutes sortes d'autres structures algébriques nœthériennes (je suppose mes anneaux commutatifs parce que je suis géomètre algébriste, mais on peut évidemment faire des choses avec les non commutatifs et des idéaux à gauche — ou bilatères). Par exemple, Alice et Bob pourraient jouer alternativement des éléments de ℤm définissant des sous-ℤ-modules (=sous-groupes abéliens) de celui-ci, avec une inclusion stricte à chaque fois, et cette fois-ci on peut jouer à la variante normale du jeu (i.e., celui qui ne peut plus jouer a perdu) : il n'est pas extrêmement difficile — mais pas trivial non plus — de trouver montrer que Bob (le second joueur) a une stratégie gagnante si et seulement si m est pair.

On pourrait imaginer d'autres variations : par exemple, en revenant aux polynômes dans k[t0,…,tn], changer un peu la règle en imposant de jouer des polynômes homogènes et sans doute en terminant quand il y a une puissance de chaque indéterminée dans l'idéal qu'on a engendré, ce qui a aussi un contenu géométrique naturel : cette fois on joue avec des sous-schémas fermés de l'espace projectif de dimension n. On pourrait aussi jouer avec des monômes, auquel cas les coefficients n'existent plus et on est simplement en train de jouer au jeu de chomp multidimensionnel. Je trouverais satisfaisant d'arriver à plonger le jeu de chomp dans le jeu d'un anneau nœthérien sans restriction, mais j'avoue ne pas voir de façon de faire ça. (Je trouverais aussi satisfaisant d'arriver à résoudre le jeu de départ sur les polynômes en le ramenant au jeu de chomp par une utilisation astucieuse de bases de Gröbner qui feraient qu'on peut toujours supposer qu'on joue avec des monômes, c'est sans doute une idée naïve.)

Toujours est-il que ce jeu conduit à un invariant rigolo (quoique pas très sérieux) d'un anneau nœthérien, c'est ce que j'ai envie d'appeler sa fonction de Grundy-Gulliksen (je vais expliquer pourquoi Gulliksen, mais pour Grundy, voir mon entrée sur les jeux combinatoires que j'ai déjà liée, spécialement sa deuxième partie). La définition est très simple et très jolie :

Si R est un anneau [commutatif] noethérien, la fonction de Grundy-Gulliksen de R est le plus petit ordinal qui n'est pas égal à la fonction de Grundy-Gulliksen d'un R/(f) pour un élément f≠0 dans R.

La définition est récursive (définir la fonction de Grundy-Gulliksen de R demande de connaître celle de tous les quotients R/(f) de R par un idéal principal non nul), mais elle a quand même un sens par nœthérianité : c'est toute la beauté de l'induction nœthérienne.

Noter qu'il s'agit là de la fonction de Grundy pour la variante normale du jeu, qui (sur tout anneau non nul) vaut 1 plus la fonction de Grundy pour la variante misère. Donc la stratégie gagnante pour au jeu (variante misère) consiste à toujours jouer vers un anneau dont la fonction de Grundy-Gulliksen vaut 1.

Bon, je ne sais essentiellement rien dire d'intelligent sur ce nombre. En revanche, si au lieu de considérer R comme un jeu je le considère comme un processus terminant dont il faut évaluer la longueur (voir la première partie de mon entrée sur les jeux), on obtient une quantité très intéressante :

Si R est un anneau [commutatif] noethérien, la longueur de Gulliksen de R est le plus petit ordinal strictement supérieur à la longueur de Gulliksen de tout R/(f) pour un élément f≠0 dans R. (De façon équivalente, c'est le plus petit ordinal strictement supérieur à la longueur de Gulliksen de tout R/I pour un idéal I≠(0) de R.)

(L'équivalence dans la parenthèse finale n'a évidemment pas d'analogue pour la fonction de Grundy-Gulliksen : cela reviendrait à donner aux joueurs la possibilité de quotienter l'anneau autant de fois qu'ils veulent, auquel cas le jeu perd évidemment tout intérêt.)

On peut évidemment généraliser ça à d'autres choses : notamment, la longueur de Gulliksen d'un module nœthérien M sur un anneau R est le plus petit ordinal strictement supérieur à la longueur de Gulliksen de tout quotient M/N de M par un sous-R-module N (et en fait, on n'a pas besoin de supposer R commutatif, et d'ailleurs Gulliksen ne le fait pas) ; la longueur de Gulliksen d'un schéma nœthérien est le plus petit ordinal strictement supérieur à la longueur de Gulliksen de n'importe quel sous-schéma fermé strict. Toutes ces définitions ont un sens bien que récursives, grâce à la magie de l'induction nœthérienne.

Par exemple, l'anneau nul, comme il n'a aucun quotient non-trivial, a une longueur nulle (0 est le plus petit ordinal strictement supérieur à tout élément de l'ensemble vide), et c'est manifestement le seul ; un corps a une longueur 1, et réciproquement tout anneau de longueur 1 est un corps. Un espace vectoriel de dimension finie sur un corps a une longueur (en tant que module sur ce corps) égale à sa dimension. L'anneau k[t]/(t²) a une longueur 2, tandis que k[t] a longueur ω (parce que k[t]/(f) a une longueur égale au degré de f pour tout f non nul).

J'appelle cette notion longueur de Gulliksen parce qu'elle a été étudiée dans un très bel article par Tor Gulliksen en 1973. Elle généralise la notion classique de longueur (définie pour les modules à la fois nœthériens et artiniens, et en particulier pour les anneaux artiniens), mais avec une définition bien plus agréable, et des propriétés presque aussi sympathiques dans le cas infini (notamment, si 0 → M′ → MM″ → 0 est une suite exacte courte de modules nœthériens, la longueur de Gulliksen ℓ(M) de M est encadrée par la valeur de deux additions entre celles de M′ et M″, à savoir ℓ(M′) + ℓ(M″) ≤ ℓ(M) ≤ ℓ(M′) ⊞ ℓ(M″) où + désigne la somme usuelle des ordinaux, et ⊞ la somme naturelle ou somme de Hessenberg). Mais en même temps, la longueur de Gulliksen permet de retrouver la dimension (de Krull) d'un anneau, généralisée aux ordinaux non nécessairement finis : si on écrit la longueur de Gulliksen de M en forme normale de Cantor (c'est-à-dire en « base ω », voir par exemple cette entrée sur les ordinaux), alors le plus grand exposant de ω qui intervient définit la dimension de M — par exemple, la longueur de Gulliksen de k[t1,…,tn] vaut ωn. Entre autres propriétés dignes d'intérêt (elle n'est pas écrite noir sur blanc dans l'article de Gulliksen, mais elle s'en déduit assez facilement en considérant la dimension de Krull), un anneau [commutatif] nœthérien est intègre si et seulement si sa longueur de Gulliksen est une puissance de ω, ce qui est fort sympathique. Mieux, l'écriture en forme normale de Cantor de la longueur de Gulliksen d'un anneau [commutatif] R se relie à la décomposition primaire de R.

Je trouve la longueur de Gulliksen — et son écriture en forme normale de Cantor — beaucoup plus naturelle et élégante que la fonction de Hilbert-Samuel, et que la définition classique de la dimension de Krull : à mon avis, il serait profitable de s'en servir dans toute introduction ou tout livre sur l'algèbre commutative. Le fait que le concept ait été peu développé est sans doute le signe que les algébristes n'aiment pas les ordinaux (ou l'infini qu'ils ne contrôlent pas bien), ce qui est vraiment dommage.

Une chose qui me chagrine, cependant, c'est qu'on manque d'exemples d'anneaux nœthériens de dimension de Krull arbitraire (infinie) : essentiellement, je connais une construction, due à Nagata, qui a été raffinée par le même Gulliksen pour fabriquer des anneaux de dimension de Krull un ordinal quelconque (et du coup, de façon facile, de longueur de Gulliksen un ordinal quelconque) — cette construction n'est sans doute pas aussi simple qu'on voudrait, et, en tout cas, on manque (ou du moins, je manque) de variété dans les exemples.

(mardi)

De la force de Coq et d'autres systèmes, et de l'utilité de mettre les résultats mathématiques en contexte

À cause de la combinaison entre l'écriture de l'entrée précédente et de mon interaction avec des (enfin, surtout un) mathématicien constructiviste à la Bishop/Richman, j'ai tenté de me faire une idée sur la force logique des systèmes admis par les constructivistes. (L'idée est que — pour une raison qu'on ne comprend pas vraiment, mais que je suis tenté de prendre pour un indice empirique de l'existence platonique des entiers — toutes les théories logiques introduites « naturellement » en mathématiques semblent s'arranger selon une échelle totalement ordonnée de « force » convenablement définie. Je voulais savoir où, sur cette échelle, se situent les différents cadres des mathématiques constructives. On m'a recommandé de lire le texte introductif de Martin-Löf The Hilbert-Brouwer controversy resolved? — mais au final il me suggère plus de questions qu'il n'en clôt.) Mauvaise idée : je me suis retrouvé dans un labyrinthe de petits énoncés tordus, tous semblables — et surtout, de gens qui ne communiquent pas assez entre eux, et qui ne présentent pas leurs résultats dans le contexte des autres résultats du même genre.

Certes, le problème n'est pas évident, pour plusieurs raisons :

Une des choses que j'aimerais comprendre, par exemple, c'est quelle est la force logique du calcul des constructions inductives (une extension du calcul des constructions qui se situe au coin le plus complexe du cube de Barendregt mentionné ci-dessus) et du système Coq qui se base dessus. Et aussi de savoir si on doit le considérer comme « constructif ». (La réponse à ces deux questions dépendra sans doute, et de façon subtile, de ce qu'on met dedans : il est certain que l'ajout du tiers exclu augmente énormément la force logique, par exemple, mais j'ai les idées beaucoup moins claires sur l'introduction du type Prop « imprédicatif » ou de l'irrelevance des preuves.) J'ai toutes sortes de réponses partielles à ces questions, mais surtout un grand mal à les relier les unes aux autres, de nouveau, parce que les gens qui ont écrit ces réponses ne se citent pas les uns les autres pour expliquer le lien entre ce qu'ils disent. Pour commencer, j'apprends dans un vieil article de B. Werner intitulé Sets in Types, Types in Sets que Coq avec ω univers est (co-interprétable, donc) équiconsistant avec ZFC avec ω univers (de Grothendieck, i.e., cardinaux inaccessibles) — sauf qu'en fait, en lisant bien, on voit que c'est après ajout de l'axiome du tiers exclu (et peut-être un autre axiome bizarre), donc ça ne m'apprend qu'une borne supérieure (très faible) sur la force de Coq sans le tiers exclu. Un article de Rathjen intitulé Constructive Zermelo-Fraenkel Set Theory, Power Set, and the Calculus of Constructions (publié dans un volume en l'honneur de Martin-Löf) m'apprend, si je lis bien !, qu'une certaine théorie basée sur le calcul des constructions (et/ou la théorie des types de Martin-Löf — comme je l'ai dit, je ne comprends pas bien le rapport entre elles), comportant une règle d'« irrelevance des preuves », a une force logique équivalente à la fois (1) à CZF + l'axiome d'existence de l'ensemble des parties [d'un singleton, cela suffit], (2) à la théorie classique Power-KP (essentiellement, Kripke-Platek si on ajoute la fonction « ensemble des parties » au langage), ou encore (3) à la théorie des ensembles classique de Zermelo à laquelle on ajoute un nombre d'univers égal à l'ordinal de Bachmann-Howard. La thèse d'Alexandre Miquel émet (conjecture 9.7.6) une supposition qui pourrait sembler contradictoire avec ça, mais peut-être pas parce qu'il y a toutes sortes de subtilités techniques qui diffèrent entre les théories comparées (en tout cas, les deux sont d'accord sur le fait que la force logique dépasse celle de la théorie des ensembles de Zermelo) — en revanche, je ne comprends pas si l'axiome d'irrelevance des preuves a dû être postulé pour obtenir la borne inférieure. En tout cas, il s'agit de théories assez « fortes » car elles dépassent l'arithmétique du second ordre (qualifiée de fossé infranchissable dans le texte de Martin-Löf cité tout au début). A contrario, j'ai trouvé un texte d'Aczel, On Relating Type Theories and Set Theories ainsi qu'un plus vieux texte de Rathjen, The strength of Some Martin-Löf Type Theories, qui arrivent à la conclusion que diverses théories des types entre lesquelles je m'embrouille complètement sont, pour leur part, d'une force logique très modeste (en-deçà du fossé infranchissable évoqué par Martin-Löf). La différence doit donc bien être dans l'existence de l'ensemble des parties [d'un singleton], dans le type Prop de Coq que différents auteurs qualifient d'« imprédicatif » même si j'avoue ne jamais avoir compris ce que ce mot veut dire, et/ou dans l'irrelevance des preuves.

Mais bon, trève de détails techniques (que j'avoue avoir écrits surtout pour m'en souvenir plus tard) : ce dont je veux surtout me plaindre et de la façon dont les gens ne communiquent pas assez. Par exemple, j'ai trouvé extrêmement peu d'arêtes pour la relation être cité par entre les équipes d'informaticiens qui gravitent autour de Coq (du genre, B. Werner) et les équipes de matheux qui font de la théorie ordinale de la démonstration (comme le M. Rathjen que j'ai cité plusieurs fois ci-dessus, et dont les articles répondent très souvent aux questions que je me pose en théorie de la démonstration) : pourtant, ces deux groupes de gens font de la logique parfois intuitionniste et notamment de la théorie de la démonstration ; et pourtant, il est essentiel pour bien faire comprendre ses résultats de les mettre en perspective par rapport à d'autres résultats du même genre. Ceci me rappelle cette citation de Giancarlo Rota :

A leader in the theory of pseudo-parabolic partial differential equations in quasi-convex domains will not stoop to being understood by specialists in quasi-parabolic partial differential equations in pseudo-convex domains.

— Indiscrete Thoughts (XXI. Book reviews: Professor Neanderthal's World)

Résultat, moi qui ne suis spécialiste ni des équations différentielles pseudo-paraboliques dans les domaines quasi-convexes ni des équations différentielles quasi-paraboliques dans les domaines pseudo-convexes, je dois m'arracher les cheveux à me demander quel est le rapport entre tel résultat de la première théorie et tel résultat apparemment très semblable de la seconde, sachant qu'aucun ne mentionne l'autre pour m'éclairer sur le sujet.

(dimanche)

Comment calculer un grand nombre

J'ai déjà exploré assez en détail le sujet des (très très) grands nombres. Je ne vais pas revenir sur tout ce que j'ai dit (et comme d'habitude, je tenterai de ne garder mes posts indépendants les uns des autres), mais je veux me servir de cette question pour illustrer quelques faits de logique rigolo.

Imaginons qu'un génie pervers nous mette devant un ordinateur et nous donne la tâche d'écrire — dans un langage de programmation idéalisé de notre choix — un programme qui calcule le nombre le plus grand possible avant de s'arrêter. (Le programme en question tournera sur l'Infinitiplex du génie, équivalent à une machine de Turing qui dispose de ressources de calcul illimitées : donc ni le temps de calcul ni la mémoire consommée ne sont à prendre en compte, seul importe le nombre renvoyé ; en revanche, évidemment, la taille du programme doit rester humainement gérable ; par ailleurs, le programme doit effectuer un calcul déterministe et s'arrêter de lui-même, sans intervention extérieure.)

La stratégie intelligente à utiliser serait quelque chose comme ceci :

Soit T une théorie logique raisonnablement puissante et contenant l'arithmétique ; par exemple : ZFC. [On verra plus bas qu'on devra supposer la Σ₁-véracité-arithmétique de T.]

Appelons F:NF(N) (ou plus exactement FT) la fonction ainsi calculée :

  • énumérer toutes les suites de symboles de longueur ≤N,
  • parmi celles-ci, rechercher toutes celles qui sont des démonstrations valides dans la théorie T (c'est-à-dire que chaque ligne est soit un axiome de T soit le résultat de lignes antérieures par application des règles de la logique, ce qui se teste algorithmiquement sans aucun problème),
  • parmi celles-ci, rechercher toutes celles dont la conclusion est de la forme l'exécution de la machine de Turing <M> termine (quand démarre à partir d'un ruban vierge) [on peut, bien sûr, remplacer les machines de Turing par toute autre langage de programmation idéalisé bien défini donc susceptible d'être formalisé dans l'arithmétique],
  • lancer (c'est-à-dire, simuler) l'exécution de toutes ces machines de Turing M, et attendre qu'elles s'arrêtent, en comptant le nombre de pas d'exécution,
  • renvoyer la somme de tous ces temps d'exécution.

Le programme effectue le calcul de F(101000) (disons).

D'ailleurs, je ne suis pas le seul à proposer cette idée : un concours de ce genre a été fait (écrire le programme en C idéalisé qui calcule le nombre le plus grand possible en 512 octets de code source), et le gagnant est celui qui a utilisé cette stratégie avec, pour T le calcul des constructions de Coquand-Huet, une logique d'ordre supérieur qui a l'avantage d'unifier le programme et sa preuve de terminaison. Je suis d'ailleurs très impressionné que quelqu'un ait réussi à implémenter la normalisation du calcul des constructions en 512 octets de C.

Dès que la théorie T est raisonnablement puissante, ceci calcule un nombre extraordinairement grand. Pour tout T non ridiculement faible, la valeur FT(10↑1000) va dépasser, par exemple, le nombre de Graham (et de très loin) : en effet, il est très facile de montrer que le programme évident qui calcule ce nombre, et le convertit en unaire, termine — ceci demande certainement moins de 10↑1000 symboles à démontrer, et ce, dans une théorie T passablement faible. Donc, au cours du calcul de F(10↑1000), on va énumérer cette démonstration, puis exécuter le programme correspondant, et du coup, F(10↑1000) dépasse largement le nombre de Graham. Ce même argument vaut — par définition même de la fonction F — pour toute valeur qui peut être calculée par un programme dont la terminaison peut être prouvée par une démonstration de longueur raisonnable (dans le système T choisi).

Plus le système T est puissant, plus il montrera la terminaison de machines de Turing compliquées, et plus le nombre FT(10↑1000) calculé sera grand. Par exemple, si T est l'arithmétique de Peano du premier ordre, comme expliqué ci-dessus, on peut facilement formaliser le fait que la machine qui calcule la fonction d'Ackermann termine (i.e., Peano sait que cette fonction est bien définie), donc F(10↑1000) va dépasser les quantités facilement construites à partir de la fonction d'Ackermann (ou ses variantes, ce qui inclut le nombre de Graham qui est essentiellement 64 itérations de la fonction d'Ackermann). Pour un système T capable de prouver la terminaison des suites de Goodstein (cette fois, Peano ne suffit plus, mais ZFC si), alors le nombre va dépasser tout ce qu'on peut raisonnablement décrire avec des opérations comme la longueur de la suite de Goodstein commençant par <tant> (cette fonction croissant considérablement plus vite que la fonction d'Ackermann).

En fait, comme je vais l'expliquer, si le but est de fabriquer le nombre le plus grand possible, il vaut mieux viser le système T le plus fort possible, plutôt qu'essayer d'améliorer d'autres aspects du programme (par exemple remplacer 10↑1000 par 10↑(10↑1000) ou quelque chose comme ça, ou même imbriquer 10↑1000 fois la fonction F).

Voici une première observation assez triviale : le système T lui-même ne peut pas prouver en moins de N symboles que F(N) est bien définie (i.e., que le programme qui le calcule termine) : en effet, si c'était le cas, le calcul de F(N) lui-même ferait partie des machines M dont il énumère une preuve de terminaison, et du coup F(N) se simulerait lui-même, or dans ce cas il ne termine certainement pas. Ou, si on préfère : comme F(N) est plus grand que le résultat de tout calcul M dont T prouve la terminaison en moins de N symbole, T ne peut évidemment pas prouver la terminaison de ce calcul-là.

Ceci peut ressembler à un paradoxe. La terminaison de F(N) n'est-elle pas évidente pour n'importe quel N ? Après tout, l'énumération des chaînes de longueur au plus N termine évidemment, et pour ce qui est de la seconde partie du calcul, on a une preuve (dans T) de la terminaison de chacune des machines M qui sont lancées, donc il faut bien qu'elles terminent. C'est, en effet, le cas, si on a fait l'hypothèse suivante sur la théorie T : que dès que celle-ci prouve la terminaison d'une machine de Turing M, alors cette machine termine effectivement ; cette hypothèse (T ne dit pas de bêtises, au moins s'agissant de la terminaison des machines de Turing), i.e., le fait que certaines conclusions de T soient vraies, s'appelle la Σ₁-véracité-arithmétique de la théorie T (on dit parfois : 1-consistance de T ; la définition n'est pas tout à fait la même, mais au final cela revient au même). Si on veut, il s'agit d'une affirmation plus forte que la consistance de T : la consistance de T demande que T ne démontre pas l'énoncé absurde 0=1, la Σ₁-véracité-arithmétique demande que tout ce que T démontre et qui peut se mettre sous la forme <telle> machine de Turing termine (à partir d'un ruban vierge) est vrai, ce qui est visiblement plus fort (si T démontre 0=1, elle démontre n'importe quoi, y compris que termine une machine de Turing qui fait une boucle infinie triviale). (La Σ₁-véracité-arithmétique de T est même assez trivialement équivalente à l'énoncé pour tout N, la valeur FT(N) est définie [i.e., le calcul termine].)

Digression : Un exemple de théorie consistante mais non Σ₁-arithmétiquement-vraie (=1-consistante) est la théorie PA♠ définie comme PA + ¬Consis(PA), i.e., l'arithmétique de Peano (PA) à laquelle on ajoute l'axiome l'arithmétique de Peano est inconsistante. D'après le théorème d'incomplétude de Gödel, cette théorie PAest consistante (puisque si PA+¬Consis(PA) démontrait 0=1, alors par pure application des règles de logique, PA démontrerait Consis(PA)), même si cela peut sembler étrange vu qu'elle prétend elle-même être inconsistante ! Et comme elle (PA♠) prétend que PA démontre 0=1, elle prétend que la machine de Turing qui énumère toutes les chaînes de caractère à la recherche d'une preuve de 0=1 dans PA termine — or cette machine, en vrai, ne termine pas, donc PA♠ n'est pas Σ₁-arithmétiquement-vraie.

Du coup, le fait que T (supposée consistante) ne puisse pas prouver que pour tout N le calcul de F(N) termine ne doit pas être une surprise : c'est un avatar du théorème de Gödel, selon lequel T ne peut même pas prouver que T ne prouve pas 0=1, donc a fortiori pas que ce qu'elle démontre est vrai, même pas pour quelque chose d'aussi trivial que 0=1 ou encore moins <telle> machine de Turing termine.

En revanche, si T♯ est une théorie contenant T et qui prouve (ou qui postule) que T est Σ₁-arithmétiquement-vraie (il n'y a pas de difficulté à formaliser cette notion), alors la fonction F♯:=FT associée à T♯ est considérablement plus grande que la fonction F:=FT associée à T : en effet, d'après l'hypothèse faite, on peut écrire dans T♯ toute démonstration qu'on pouvait déjà écrire dans T, mais aussi utiliser le principe si T montre qu'une machine de Turing s'arrête, alors elle s'arrête vraiment, et donc conclure (en un nombre raisonnable de symboles) que F est bien définie. Donc (pour peu que la preuve de la Σ₁-véracité-arithmétique de T dans T♯ ne soit pas d'une longueur délirante) F♯(10↑1000) va sans difficulté dépasser F(F(F(⋯(F(10↑1000))))) avec F(10↑1000) imbrications de la fonction F (puisque dès qu'on sait que la fonction F est bien définie, on n'a aucun mal à écrire des programmes qui terminent en l'utilisant de cette manière).

Le raisonnement du paragraphe précédent vaut, notamment, si T est PA (l'arithmétique de Peano du premier ordre) est T♯ est ZFC : en effet, ZFC montre sans difficulté que toute conséquence arithmétique de PA est vraie, et en particulier toute conséquence du type <telle> machine de Turing termine. Donc la fonction F associée à ZFC croît considérablement plus vite que celle associée à PA (euphémisme !). De façon peut-être plus surprenante, le raisonnement vaut aussi si T est ZFC et que T♯ s'obtient en rajoutant l'hypothèse (IC) de l'existence d'un cardinal inaccessible : en effet, ZFC+IC démontre l'existence de ce qu'on appelle un « modèle transitif » de ZFC, i.e., un ensemble qui se comporte comme un petit monde dans lequel tous les axiomes de ZFC sont vrais (pour la même relation d'appartenance), ce modèle ayant les mêmes entiers naturels que les vrais, donc ZFC+IC démontre que toute conséquence arithmétique de ZFC est vraie, et en particulier que toute machine de Turing dont ZFC démontre la terminaison termine effectivement. Ainsi, FZFC+IC croît beaucoup plus vite que FZFC. Et la même chose vaut essentiellement pour toute notion de grand cardinal par rapport à une moins forte : plus on ajoute des grands cardinaux en pertant de T=ZFC, plus on obtient des fonctions qui croissent vite (et donc, in fine, des valeurs plus grandes de F(10↑1000) : il y a quelque chose de satisfaisant à ce que les grands cardinaux aident à fabriquer des grands entiers naturels).

Bref, ZFC+IC prouve, de façon raisonnablement courte, que FZFC(N) est défini pour tout N, et notamment que FZFC(10↑1000) l'est. Comme je l'ai expliqué, par ailleurs, il est évident que ZFC seul ne peut pas prouver en moins de 10↑1000 symboles que FZFC(10↑1000) est défini. En fait ZFC prouve bien que FZFC(10↑1000) est défini, et la démonstration est certes longue, mais pas beaucoup plus longue que 10↑1000 symboles (disons à la louche que 10↑10000 devraient suffire : en tout cas, nettement moins que les nombres totalement colossaux produits par nos diverses fonctions F). Pourquoi ? Cela résulte de l'observation triviale suivante : une démonstration de longueur inférieure à N (disons 10↑1000) dans ZFC ne peut pas utiliser d'axiome de ZFC de longueur supérieure à ce nombre (rappelons que ZFC a un nombre infini d'axiomes, à cause du schéma de compréhension et surtout celui de remplacement) ; or un lemme de réflexion montre, dans ZFC, que tout sous-ensemble fini explicite donné des axiomes de ZFC a un « modèle transitif », et donc (ce qui nous intéresse ici) a des conséquences arithmétiques vraies. (On peut même, pour tout k explicite donné, que ZFC dont le schéma de remplacement a été limité aux prédicats ayant au plus k alternations de quantificateurs — voir aussi ici — a un modèle transitif ; et la démonstration se fait suivant un modèle simple en fonction de k.) Quand on analyse, cette démonstration écrite complètement dans ZFC, on voit qu'elle fait une longueur polynomiale en N (avec un degré sans doute assez petit et des coefficients raisonnables — je n'ai pas fait l'analyse complète). Notamment, ZFC prouve que FZFC(10↑1000) est bien défini en une longueur certes plus longue que 10↑1000 symboles, mais certainement moins longue que 10↑10000.

Pour récapituler, on est dans la situation un peu étonnante suivante :

Ceci illustre plusieurs phénomènes. D'une part, l'accélération des démonstrations : la longueur de la plus courte preuve dans ZFC de FZFC(10↑1000) existe est, disons, quelque part entre 10↑1000 et 10↑10000 symboles, alors que dans ZFC+IC, elle est nettement plus courte que 10↑1000 symboles. (Notons que l'énoncé FZFC(10↑1000) existe est même prouvable dans PA ou dans des systèmes extrêmement faibles de l'arithmétique : après tout, pour prouver qu'une machine de Turing termine, il suffit d'écrire sa trace d'exécution complète comme démonstration ! Mais ceci donne une démonstration de longueur vraiment colossale, puisque comparable au nombre dont elle affirme l'existence.)

Ensuite, c'est un cas très explicite d'incomplétude : pour chaque N on peut produire, selon un motif simple, une démonstration dans ZFC de FZFC(N) existe, mais on ne peut pas en produire une de pour tout N, FZFC(N) existe. Du coup, je trouve que ceci illustre la mauvaise foi de la position épistémologique je ne crois qu'à ce qui est démontré dans ZFC : personne ne va écrire séparément la démonstration de FZFC(N) existe pour un N donné (ça n'a aucun intérêt : elle se produit trivialement en fonction de N), mais cette position oblige à dire qu'on l'accepte que comme démonstration du fait que FZFC(N) existe pour n'importe quel N, mais pas du même énoncé quantifié par pour tout N ! Ceci vaut notamment pour les gens qui se cachent derrière leur petit doigt en disant je ne sais pas si ZFC est consistant (de fait, ZFC ne le démontre pas) : je rappelle que l'énoncé pour tout N, FZFC(N) existe implique notamment la consistance de ZFC (il est équivalent à sa Σ₁-véracité-arithmétique), or je viens d'expliquer qu'il faut être pas mal de mauvaise foi pour prétendre ne pas savoir que pour tout N, FZFC(N) existe alors qu'on sait pour tout N que FZFC(N) existe !

D'un autre côté, si on cherche à calculer le nombre le plus grand possible (pour répondre au défi du génie pervers), on est devant le problème insoluble suivant : quelle est la théorie la plus forte possible dont on soit « convaincu » qu'elle soit Σ₁-arithmétiquement-vraie. Après tout, ZFC n'est le cadre « orthodoxe » des mathématiques que par une sorte d'accident historique (le schéma de remplacement est déjà une sorte d'axiome de grand cardinal appliqué à la classe des ordinaux et revient plus ou moins à dire que celle-ci est un cardinal inaccessible), il n'est pas magiquement plus convaincant que ZFC+IC sous prétexte qu'on a plus travaillé dedans (ou même, fait semblant de travailler dedans). Les axiomes de grands cardinaux les plus forts connus au-dessus de ZFC et au sujet desquels on ne semble pas arriver à montrer d'inconsistance sont les axiomes de rank-into-rank (et spécifiquement l'axiome I0 de Woodin) ; il y en a peut-être d'encore plus forts si on supprime l'axiome du choix.

Je souligne que plus fort ici fait référence à la force arithmétique de ces théories, et même à la force arithmétique Σ₁, c'est-à-dire à la capacité à montrer que des machines de Turing s'arrêtent : on ne demande pas de croire que ces grands cardinaux « existent » en un sens platonique profond, juste de croire qu'ajouter à la théorie des ensembles le postulat de leur existence produit des conséquences exactes sur l'arrêt des machines de Turing ! (On pourrait même utiliser le théorème de Matiâsevič-Robinson-Davis-Putnam pour reformuler ces conséquences sous la forme d'existence de solutions d'équations diophantiennes.)

Il se trouve que les systèmes connus qui sont arithmétiquement les plus forts (i.e., qui au moins paraissent arithmétiquement vrais et qui produisent les conséquences les plus fortes, donc la fonction FT la plus grande) sont tous des théories des ensembles de type ZF(C) obtenues en ajoutant des axiomes de grands cardinaux. Il n'y a pas de raison évidente à ça : il pourrait très bien s'agir d'autres types de théories des ensembles (je pense aux théories des ensembles de type NF(U) ; d'ailleurs, certaines variantes se mesurent très bien contre ZF) ou encore de systèmes de typage (par exemple, le calcul des constructions inductives (CCI) se compare bien à ZFC et l'ajout d'univers de types à CCI à l'ajout de cardinaux inaccessibles à ZFC, donc on pourrait imaginer des extensions du calcul des constructions qui soient au niveau de force arithmétique de ZFC + tel ou tel grand cardinal ; mais je ne crois pas qu'on en ait défini), ou une tout autre chose. Je ne sais pas s'il faut y voir le signe qu'il est plus naturel de faire des théories fortes à partir de ZF(C) ou simplement que ZF a été plus étudié.

Addendum () : Je peux aussi faire la remarque rigolote suivante : dans le même ordre d'idées que ce que je décris ci-dessus, on pourrait écrire un programme de compression [sans perte] qui est en un certain sens optimal modulo la force d'une théorie logique T. Ce programme effectue le calcul suivant : donnée une donnée Y à comprimer, on énumère, dans l'ordre de longueur, toutes les démonstrations dans T (par exemple : ZFC) dont la conclusion est de la forme la machine de Turing M, quand on lui fournit l'entrée X, termine (noter que cette démonstration doit faire au moins la longueur de M plus celle de X, juste pour énoncer la conclusion) ; à chaque fois qu'on en trouve une, on simule l'exécution de la machine M sur l'entrée X, et dès qu'on en trouve une dont la sortie coïncide avec le Y à comprimer, on s'arrête, la compression étant alors donnée par le couple (M,X) (on pourrait d'ailleurs se passer de X complètement et produire seulement M, mais l'intérêt de mettre les deux est qu'on n'a pas à s'embêter à chercher comment encoder optimalement les machines de Turing). Bref, la compression de Y est le couple (M,X) pour lequel on a la plus courte démonstration dans T du fait que M termine sur X et pour lequel par ailleurs le résultat de ce calcul vaut Y (attention !, ce dernier fait est vérifié par le programme de compression mais n'est pas inscrit dans la démonstration faite dans T !). Ce programme de compression termine si la théorie T est Σ₁-arithmétiquement-vraie, car toutes les exécutions simulées de couples (M,X) termineront, et on finira bien par en trouver une qui produit la sortie Y voulue (au pire, et c'est ce qui se passera presque toujours si Y est « aléatoire », on tombera sur la démonstration du fait que la machine qui termine immédiatement sans rien faire — donc qui calcule la fonction identité — termine quand on la lance sur l'entrée Y elle-même). On peut décomprimer (retrouver Y) en simulant l'exécution de la machine M sur l'entrée X. Mon programme de compression sera, à une constante près, au moins aussi bon que, disons, gzip, parce qu'on peut facilement prouver dans ZFC que gunzip termine sur toute entrée, donc la démonstration du fait que gunzip termine sur l'entrée X (où X est la sortie de gzip(Y)) a une longueur comparable à celle de X plus une petite constante indépendante de X, et du coup borne la taille de la sortie de mon programme. On pourrait dire que mon programme calcule non pas la complexité de Kolmogorov de Y, mais son approximation vue par la théorie T.

(samedi)

Maleficent

Mon poussinet et moi sommes allés voir le dernier Disney, Maleficent (de, par, pour et avec Angelina Jolie ☺). J'ai vraiment beaucoup aimé. C'est mignon et rigolo, et c'est astucieux sans prétendre être profond. Certains disent que ce n'est pas un film pour enfants parce qu'il prend le point de vue de la « méchante », mais je pense justement que ce n'est pas mal que les enfants apprennent tôt que la morale est souvent un peu plus subtile que des gentils d'un côté et des méchants de l'autre : donc je dirais que c'est un film pour les enfants de 9 à 99 ans.

Inutile de dire que ce n'est pas très fidèle au conte de Perrault. Mais le retournement de point de vue est intéressant.

[Ajout () : Je devrais mentionner que non seulement le film passe le test de Bechdel, ce qui n'est pas aussi fréquent que ça devrait l'être, mais qu'il est même, sinon féministe, au moins pas trop stupidement patriarchal, ce qui pour une interprétation de la Belle au Bois Dormant n'était pas forcément évident, quoi que puisse en penser M. Bettelheim.]

(vendredi)

Lunettes cassées

J'ai fait un faux mouvement, mes lunettes sont tombées par terre, et le verre s'est fracturé. Pourtant elles ne tombaient pas de bien haut, et le parquet chez moi n'est pas ce qu'il y a de plus dur — mais c'est ça l'inconvénient des verres à indice de réfraction élevé que doivent porter les forts myopes comme moi, c'est aussi plus fragile.

Bref, j'ai commandé deux nouvelles paires chez mes opticiens hong-kongais préférés, mais en attendant, me revoilà avec mes lunettes précédentes, qui font une bonne dioptrie de moins à l'œil gauche, et je suis parti pour avoir droit à de sérieux maux de tête.

Je suis fatigué, mais fatigué, fatigué, fatigué…

(mercredi)

Pourquoi ne pas faire confiance à une calculatrice

On me demande de trouver un exemple pédagogique d'un calcul pour lequel une calculatrice donnerait un résultat faux mais qu'un mathématicien saurait faire (en un temps raisonnable). Le meilleur exemple que je voie est celui-ci : sin((1+√2)200×π). Une calculatrice (par exemple celle de Google) renvoie un résultat bidon, alors que n'importe quel mathématicien compétent voit que (1+√2)200 + (1−√2)200 est un entier pair, si bien que sin((1+√2)200×π) = −sin((1−√2)200×π) est extrêmement petit, et on peut même en faire une estimation de tête : sin((1−√2)200×π) est plus petit que ((1−√2)200×π), qui est lui-même plus petit que (½)200×π, or 210=1024 est supérieur à et environ égal à 1000=103, donc (½)20×10×π est inférieur à et environ égal à 10−60×π, bref, de tête j'aurais dit que sin((1+√2)200×π) est compris entre −4×10−60 et 0. La valeur correcte est environ −8.75×10−77, donc mon estimation n'est pas terrible (quoique, en évaluant un peu plus finement le rapport entre 0.41 et 0.5 j'aurais réussi à être plus précis), mais c'est tout de même mieux que les 0.97 retournés par Google.

Quelqu'un a-t-il un meilleur exemple ?

À part ça, aucun rapport (si ce n'est celui des calculs auxquels dont on doit se méfier), mais mon poussinet et moi avons déclaré nos impôts[#] : à cause de l'arrondi à l'euro le plus proche pratiqué par l'administration fiscale, nous perdons un euro à être PACSés (par rapport à la situation où nous payerions nos impôts séparément). Ça c'est de l'optimisation fiscale du tonnerre !

[#] Dédicace spéciale aux pédants pourfendeurs de métonymies qui trépignent en pensant on ne déclare pas ses impôts, on déclare ses revenus. Mais oui, moi aussi je vous aime.

(mercredi)

Je suis fatigué, fatigué, fatigué

Le fait que j'aie attrapé un nouveau gros rhume comme je les collectionne, juste quand je commençais à voir le bout de trois semaines très chargées, n'aide certainement pas. Les jours fériés n'aident pas non plus : l'arnaque avec les jours fériés, c'est que quand il y en a, j'ai exactement autant de choses à faire dans la semaine mais moins de temps pour les faire. Le week-end de la Pentecôte, j'ai une obligation sociale qui me fatigue rien que d'y penser. Et, bien sûr, les bruits divers et variés qui m'empêchent de dormir n'aident pas non plus à me reposer.

J'aurais surtout besoin de vacances (depuis septembre, je n'ai réussi à en prendre qu'une semaine entre Noël et le nouvel an). Mais comme je voudrais surtout prendre des vacances chez moi à Paris (parce que je trouve voyager tellement fatigant que ça annule tout effet bénéfique de la coupure), je suis victime du fait que personne ne prend ça au sérieux. Je veux dire, si quelqu'un vous demande de faire quelque chose un certain jour, répondre je ne pourrai pas, je serai en vacances à Saint-Trouduc-lès-Trèsloin est considéré comme une excuse valable, mais pas je ne pourrai pas, je serai en vacances ici (les gens vous disent : ben si tu es là, tu peux bien trouver le temps… — bon, peut-être que mon problème est que je ne sais pas assez dire merde aux gens, mais j'ai pourtant l'impression de le dire tout le temps).

(mercredi)

Quelques misères informatiques (et une upgrade d'Ubuntu)

Je vais raconter un peu mes petits malheurs informatiques, ça ne servira à rien sauf à me défouler.

D'abord, le rant général que j'ai déjà dû répéter mille fois : les deux distributions Linux que je connais bien sont Debian et Ubuntu. Le choix entre les deux s'apparente à un choix entre Charybde et Scylla :

Il y a évidemment d'autres distributions Linux que je pourrais essayer, et sans doute certaines qui résoudraient les différents problèmes mentionnés ci-dessus, mais je suis assez persuadé qu'en contrepartie elles en introduiraient d'autres (il y a une sorte de loi cosmique de conservation des emmerdes) : j'ai donc assez peu envie de vouloir perdre mon temps à tout réapprendre pour découvrir au final que je n'aurais pas gagné grand-chose.

Toujours est-il que, n'arrivant pas à choisir entre Charybde et Scylla, j'ai opté pour les deux à la fois. Ma machine au bureau (capella.enst.fr) et mon portable (alioth) sont sous Ubuntu, tandis que mes différents serveurs (comme achernar.gro-tsen.net et spica.gro-tsen.net, et aussi les routeurs que j'ai mis chez moi et chez mes parents) sont sous Debian stable, et mon PC fixe personnel est sous Debian testing (enfin, en ce moment il est sous la stable parce qu'elle est seulement totalement obsolète et pas encore ultra-archi-paléolithique, mais ça finira sans doute par changer).

Bref, mon PC de bureau était sous Ubuntu 12.10 Quantal Quetzal, et voilà que celui-ci m'avertit que cette version ne sera plus mise à jour et qu'il est donc temps de migrer (en sautant la 13.04 Raring Ringtail et en faisant escale par la 13.10 Saucy Salamander) vers la version 14.04 Trusty Tahr (pour ceux qui n'ont pas l'habitude, les numéros de version d'Ubuntu sont simplement de la forme année.mois, et le nom de code commence par une lettre qui tourne dans l'alphabet). Voilà, me suis-je dit, une journée de perdue.

Il y a eu des problèmes que je connaissais d'avance et que j'ai donc pu contourner (par exemple le fait que la mise à jour demande énormément de place dans /var et qu'il fallait donc que je prévoie de basculer temporairement vers un disque plus gros pour cette partition). Il y en a eu d'autres que je n'aurais pas imaginé mais qui étaient fort mineurs (essentiellement le fait que le package gforth fournit un mode Emacs qui casse avec la version plus récente d'Emacs apportée par la distribution, et par la magie du système de package fait avorter toute la mise à jour : heureusement, c'était trivial de retirer ce package et de redémarrer la mise à jour). Mais bon, comme d'habitude, la mise à jour proprement dite ne s'est pas trop mal passée : ce dont j'étais sûr, et qui n'a pas manqué d'arriver, c'est que j'avais gagné le droit de perdre tous mes petits réglages et de recomprendre ce qu'Ubuntu avait déclaré être le nouveau mécanisme de l'avenir.

Première constatation : je ne peux pas me logguer — si je tape mon mot de passe dans le gestionnaire graphique, je suis immédiatement renvoyé au point de départ. Un compte vierge fonctionne parfaitement, mais, justement, je n'ai pas envie de repartir d'un compte vierge. Je vous épargne les explications sur le mal que j'ai eu à comprendre ce qui se passait : le fin mot de l'histoire est que j'avais configuré mon PATH pour ne pas contenir les répertoires système /sbin et /usr/sbin (qui, dans la tradition Unix, sont censés être réservés aux binaires uniquement utiles à l'administrateur) alors que maintenant Ubuntu base tout son mécanisme de démarrage sur le démon Upstart (documenté ici — au moins, là, ils ont fait des efforts), appelé init parce qu'il sert aussi d'init du système, et ils l'appellent simplement init, pas /sbin/init, donc les scripts de démarrage de session ne le trouvaient pas. Bon, au passage, j'ai appris énormément de choses sur la manière dont une session démarre, ce qui est toujours bon à savoir (malheureusement tout sera probablement faux dans la version suivante quand ils auront décidé que leur Upstart tout neuf, finalement, ce n'est pas si bien que ça et qu'on va utiliser autre chose à la place, je sens bien le coup) ; après coup, j'ai vu que tout était fort bien expliqué ici (voilà exactement le genre de docs qui devraient être régulièrement maintenues, et placées à un endroit plus trouvable qu'un thread aléatoire de AskUbuntu). Bon, j'ai mis des liens symboliques vers certains programmes de /sbin dans un répertoire ad hoc mon PATH et j'ai pu me logguer.

Ensuite, évidemment, toute ma petite config clavier avait cassé. Alors oui, je sais que je suis casse-pied, mais il y a essentiellement un truc que je veux absolument pouvoir configurer finement sur mon système, c'est le réglage de mon clavier (et, sur mon portable, de mon touchpad). Je tiens notamment à ce que la touche marquée d'un symbole Windows à gauche de la barre d'espace (immédiatement à droite du Control de gauche) soit une touche Alt (et qu'elle me serve à configurer mes racourcis clavier liés au déplacement des fenêtres et les choses comme ça) et que la touche marquée Alt soit une touche Meta (et que ce soit celle-là qui serve à ouvrir des menus dans une application donnée, et bien sûr, serve de touche Meta sous Emacs) : je sais, c'est un peu tordu, mais c'est comme ça sur les claviers Sun, et je tiens vraiment à cette config — ça ne devrait quand même pas être la mort. Le souci c'est que Gnome, Ubuntu, et essentiellement tout le monde, a décidé de faire les choses autrement, donc des hypothèses contraires à mes choix sont faits à peu près à tous les niveaux, et il faut vraiment que je me batte pour avoir mes touches Alt et Meta comme je les veux. Rien que d'obtenir de charger une configuration clavier personnelle (je veux dire, vraiment personnelle, pas juste choisir si on veut un layout QWERTY ou AZERTY avec quelques options en plus ou en moins), sous Ubuntu, c'est la croix et la bannière : en principe il devrait suffire de lancer une commande du genre xkbcomp $HOME/.xkb/toplevel.xkm $DISPLAY au démarrage (si .xkb contient la config clavier personnelle compilée), sauf que (1) trouver où mettre une telle commande pour qu'elle soit lancée n'est déjà pas évident, et (2) même si on arrive à la faire exécuter, tout truc comme Gnome et Unity va faire tourner un million de démons qui décident aléatoirement oh, voyons ce que l'utilisateur veut utiliser comme type de clavier et installons-lui ce layout et donc effacent la configuration clavier qu'on a pu réussir à installer ; pire, Ubuntu a décidé de lancer automatiquement un serveur d'input methods qui ajoute une surcouche de complexité à toute l'histoire et qui, d'ailleurs, capturait le racouri Control-Espace absolument essentiel à Emacs (est-ce qu'Ubuntu a décidé qu'on n'avait plus le droit d'utiliser Emacs ? je l'ignore — on peut évidemment changer le racourci, mais de nouveau, encore faut-il comprendre comment tout ceci s'agence). Et même une fois que j'arrive à faire avaler au système ma configuration clavier personnelle, encore faut-il réussir à lui faire accepter que j'aie des racourcis clavier avec une touche Alt qui n'est pas la touche que lui a envie d'appeler Alt (à savoir Mod1 — c'est terriblement compliqué parce que les touches ont à la fois un keysym et un modificateur associé) : il faut lui faire accepter des racourcis clavier avec Alt-sous-le-nom-de-Mod2, ce que je n'ai réussi à faire qu'en allant taper directement dans la configuration de Gnome (qui s'appelait gconf jusqu'au jour où ils ont décidé que l'avenir, finalement, c'était dconf). À chaque version d'Ubuntu je dois me battre pour avoir mon clavier comme je veux.

Ce coup-ci j'ai dû laisser tomber. Le démon qui servait à gérer les racourcis clavier (un plugin du gnome-settings-daemon) a muté en deux descendants, un unity-settings-daemon et un ayant gardé le nom gnome-settings-daemon, je n'ai pas réussi à savoir lequel je devais utiliser et je n'ai pas réussi à faire avaler mes racourcis ni à l'un ni à l'autre. Alors j'ai jeté Gnome, Unity et compagnie par la fenêtre, j'ai jeté un coup d'œil rapide à Xfce, j'ai découvert qu'il était encore moins configurable, et j'ai fini par revenir à Fvwm comme je l'utilise sur ma machine personnelle. Au moins, Fvwm, j'arrive à lui faire comprendre exactement ce que je veux comme racourcis clavier, si je lui dis de prendre Mod2 pour les racourcis, il accepte ça et il ne fait pas de chichis à vouloir savoir mieux que moi si la touche doit s'appeler Alt ou autre chose.

Mais je ne suis pas content du tout. Parfois j'aime bien avoir une interface graphique un peu conviviale. Et il y a beaucoup de choses qui ont besoin, sinon de Gnome, d'au moins certains bouts de Gnome, pour fonctionner : par exemple, j'aime bien avoir une petite icône dans la barre en haut de mon écran qui m'affiche le temps qu'il fait — et je ne sais pas faire tourner ce gnome-weather sans Gnome. (De fait, j'ai bien réussi à lancer gnome-panel dans Fvwm, mais ma petite applet gnome-weather, je n'arrive décidément pas à la faire tourner.) Il n'est pas normal que j'aie seulement le choix entre Fvwm qui est complètement configurable mais où je dois tout faire à la main et je ne peux rien utiliser de Gnome, ou bien prendre tout Gnome (ou Unity, ou n'importe quoi du genre — la différence m'importe assez peu) mais devoir alors renoncer à toute configuration un peu avancée du clavier ! En abrégé : il n'est pas normal que j'aie à choisir entre l'affichage convivial de la météo et la configuration fine de mon clavier.

Je donne souvent l'exemple de Firefox pour montrer qu'un programme peut parfaitement réussir à être à la fois très hautement configurable (il suffit de regarder le nombre de paramètres réglables dans le about:config de Firefox pour s'en convaincre — et même si ça ne suffit pas, on peut écrire des extensions personnelles, et en plus, elles ne cassent pas tous les six mois) et très puissant et convivial pour l'utilisateur non expérimenté. Et en plus, abondamment documenté. Il n'y a aucune raison que Gnome et compagnie ne puissent pas suivre un modèle analogue.

Mais mes malheurs ne se sont pas arrêtés là. Prévoyant que je peinerais à retrouver une configuration vaguement utilisable sur ma machine de bureau, j'avais apporté au bureau mon portable (pas encore mis à jour) pour pouvoir quand même travailler même pendant que la machine fixe mouline à faire la mise à jour ou simplement pendant que j'en ai marre de toutes ces conneries. Seulement, j'ai constaté que le chargeur de mon portable ne chargeait plus (il doit y avoir un mauvais contact dedans, parce qu'il se remet parfois à marcher quelques secondes, mais c'est tout) : ce n'est pas surprenant, c'est une camelote chinoise achetée en remplacement de la moins-camelote chinoise d'origine qui venait avec le portable mais qui est sur prise anglaise vu que j'ai acheté le portable à Londres histoire d'avoir un clavier QWERTY — et les prises anglaises, c'est vraiment énorme à cause de toutes leurs histoires de fusibles obligatoires.

Fatigué, je suis retourné retrouver mon PC à la maison, et là celui-ci a décidé de perdre un disque dur (ça lui arrive de temps en temps — heureusement assez rarement — de perdre totalement la connexion avec un des disques SATA : je pense que c'est le chipset de la carte mère qui est moisi, mais je manque de ports SATA donc il faut que je consente à en utiliser un moisi). Comme mes disques sont totalement en RAID, et que de toute façon les disques ne sont pas défectueux (c'est la connexion qui l'est), je n'ai pas perdu de données, mais j'ai quand même perdu un temps invraisemblable à redémarrer la machine qui était dans un état très bizarre (quand on débranche un chaud un disque dur d'une machine qui tourne, elle n'aime souvent pas trop ça), puis à resynchroniser correctement les tableaux RAID.

Je finis par une petite anecdote qui cette fois-ci concerne un collègue : il a voulu modifier un fichier bashrc et a choisi, pour ça, de l'éditer avec un éditeur graphique interactif quelconque (je ne sais pas ce qu'Unity ou Gnome ouvrent quand on double-clique sur un fichier texte, mais c'est sans doute ça). Or cet éditeur a cru bon d'ajouter un byte-order mark au début du fichier (le caractère Unicode U+FEFF ZERO WIDTH NO-BREAK SPACE, qui est censé être ignoré et ne servir à rien sauf à permettre de détecter l'encodage, en l'occurrence enregistré en UTF-8 sous la forme des octets 0xef 0xbb 0xbf). Résultat : l'insertion de ce caractère invisible et quasiment indétectable faisait que le shell ne comprenait plus le fichier en question. Je ne sais pas bien qui a tort dans l'histoire (je suis tenté de dire les deux : l'éditeur ne devrait pas ajouter de byte-order mark sans raison, et surtout pas dans un fichier de type shell, il devrait savoir ça ; et le shell devrait être robuste à cette situation qui est tout de même bien connue), mais en tout cas, comme on aime dire quand on croise de telles singeries, il y a des bananes qui se perdent.

(lundi)

Faut-il communiquer sur l'intuition en mathématiques ? — ici : le corps de classes

Une question qui fait régulièrement débat en ce qui concerne la rédaction mathématique est de savoir si l'auteur d'un livre ou article mathématique doit se contenter de définir des concepts et démontrer leur propriété ou si (ou plutôt, dans quelle mesure) il doit tenter de proposer une façon de les visualiser intuitivement et guider le lecteur sur la manière d'y penser.

Il va de soi qu'avec une formulation aussi générale, la réponse est difficile à donner. Tout le monde sera sans doute d'accord sur le fait qu'une définition vraiment bizarre ou surprenante, une clause qui risque particulièrement de prêter à confusion, une subtilité dans une démonstration qui pourrait ne pas être remarquée, etc., méritent d'être signalées ou expliquées. À l'inverse, tenter de communiquer toute intuition vague n'est pas forcément bénéfique et peut même être néfaste à la compréhension (car l'intuition qu'on se forge soi-même peut être meilleure que celle qu'on reçoit d'un autre mathématicien), ou à la détection d'erreurs de raisonnement (si on fait confiance à l'intuition d'un autre, on risque de faire les mêmes erreurs que lui, et donc de ne pas détecter celles-ci). Quelque part entre les deux, je trouve toujours irritant, quand un objet mathématique est défini dans un texte, de ne pas trouver la réponse aux questions les plus naturelles qu'on peut se poser sur ses propriétés (ou simplement l'affirmation que l'auteur ne sait pas si telle ou telle propriété est vraie) : par exemple, si un auteur devait définir un concept appelé para-anneau, je trouve qu'il serait de son devoir d'expliquer le rapport entre ce concept et celui d'anneau (et même si c'est complètement évident, écrire qu'un anneau est un para-anneau, ou attirer l'attention sur le fait que ce n'est pas le cas, ou peut-être dire qu'on ne sait pas et que de toute façon on n'en aura pas besoin, ou ce genre de choses) ; et si on met plusieurs clauses dans une définition, je trouve qu'il est généralement de bon ton d'expliquer pourquoi chacune est nécessaire et ce qui se passerait si on omettait celle-ci ou celle-là.

Je vais maintenant me plaindre de la façon dont est présentée la théorie globale du corps de classes. [Je suis sûr qu'il devait y avoir un rapport entre ce qui suit et ce qui précède, mais plus j'écris moins ce rapport est clair… enfin, ce n'est pas bien grave.]

En bref : la théorie du corps de classes prétend « expliquer » (c'est-à-dire décrire, classifier, permettre de comprendre) les extensions abéliennes finies (extension abélienne = extension [de corps] galoisienne de groupe de Galois commutatif) de certains corps. « Certains corps », à savoir, les « corps locaux » (auquel cas on parle de théorie locale du corps de classes) et les « corps globaux » (auquel cas, on l'aura deviné, on parle de théorie globale du corps de classes, qui est beaucoup plus intéressante et profonde que la théorie globale locale). Les corps locaux sont des choses comme les corps des réels et des complexes (mais sur ceux-ci la théorie est vraiment triviale), les corps des nombres p-adiques (et les extensions finies de ceux-ci) et les corps de séries formelles sur un corps fini. Des exemples de corps globaux sont le corps des rationnels (ou plus généralement toute extension finie de celui-ci, dit « corps de nombres ») et le corps des fonctions rationnelles sur un corps fini (ou plus généralement le corps des fonctions d'une courbe algébrique sur un corps fini).

J'essaie de décrire un peu plus précisément de quoi cette théorie parle, en me plaçant pour simplifier sur le corps (global) ℚ des rationnels. (Pour ceux qui veulent un vrai cours sur le sujet, je recommande les notes de cours par J. S. Milne qui, comme d'habitude avec cet auteur, sont très bien écrites.)

D'abord, l'ensemble des complétés de ℚ est la famille suivante de corps (locaux) : le corps ℝ des réels, et le corps ℚp des p-adiques pour chaque nombre premier p (on dit aussi dans ce contexte que p est un nombre premier fini ou place finie, par opposition au symbole ∞ (place infinie ou place archimédienne) pour lequel on pose ℚ=ℝ).

Si je dois définir de façon très rapide ce que sont les p-adiques, ce sont des écritures en base p finies à droite et infinies à gauche (c'est-à-dire, n'ayant qu'un nombre fini de chiffres à droite de la virgule et un nombre infini à gauche), l'addition et la multiplication se faisant exactement de la même façon qu'on le fait pour les réels écrits en base p. Il se trouve que ces opérations forment un corps noté ℚp (et on note ℤp ceux des nombres p-adiques, appelés entiers p-adiques, qui n'ont aucun chiffre après la virgule) ; et ℚp contient tous les rationnels, au sens où il y a une façon naturelle d'écrire un rationnel quelconque sous cette forme en base p (par exemple, 1/3 s'écrit …0101010101010101010101011 comme 2-adique parce que quand on ajoute trois fois cette chaîne binaire on tombe sur 1) ; ℤp, lui, contient les rationnels dont le dénominateur réduit n'est pas divisible par p (en tant qu'entier usuel). La valuation vp(x) d'un p-adique x≠0 est l'emplacement du chiffre non-nul le plus à droite (strictement négatif s'il est après la virgule, positif ou nul si x est dans ℤp ; zéro si c'est le chiffre des unités, strictement positif si le nombre se finit par des zéros, c'est-à-dire s'il est divisible par une puissance non-triviale de p) ; et la valeur absolue p-adique de x est le nombre réel positif défini comme |x|p = pvp(x) (et |0|p=0), par exemple on a vp(pi)=i donc |pi|p = pi, et ℤp est l'ensemble des p-adiques de valeur absolue ≤1. On notera aussi |x| la valeur absolue usuelle d'un réel x.

Une idèle de ℚ est la donnée d'un élément non-nul xv de chacun des complétés ℚv (i.e., un nombre réel non nul, et un nombre p-adique non-nul pour chaque p : ici, v parcourt les « places » de ℚ, c'est-à-dire les nombres premiers p et le symbole ∞), avec la condition que presque tous (=tous sauf un nombre fini) des xv vérifient |xv|v = 1. La valeur absolue de l'idèle (xv) est définie comme le produit de tous les |xv|v. Les idèles forment un groupe sous la multiplication (dont l'élément neutre est l'idèle 1 qui vaut 1 en chaque place v) : on notera ce groupe J.

Un cas particulier d'idèles est celui des idèles diagonales : l'idèle diagonale définie par un rationnel x non nul est celle dont toutes les composantes xv valent x (i.e., on considère le même rationnel x vu comme un nombre réel et comme un p-adique pour chaque p). On peut se convaincre qu'une idèle diagonale est bien une idèle (car seul un nombre fini de nombres premiers divise le numérateur ou le dénominateur du rationnel considéré), et de plus, toujours de valeur absolue 1. Les idèles diagonales, bien sûr, forment un sous-groupe. On va être amené ci-dessous à évoquer certains sous-groupes du groupe J des idèles de ℚ qui contiennent le sous-groupe ℚ× des idèles diagonales : il revient au même de parler des sous-groupes du groupe quotient C := J/ℚ× des idèles modulo les idèles diagonales (c'est-à-dire dans lequel on identifie deux idèles dont le rapport est une idèle diagonale). Ce groupe C s'appelle aussi le groupe des classes d'idèles (une classe d'idèle est donc par définition une idèle modulo les idèles diagonales).

Un autre type d'idèles importantes est les idèles locales en la place v, c'est-à-dire celles dont toutes les composantes valent 1 sauf celle pour la place v (et pour chaque v fixé, elles forment aussi un sous-groupe.

Supposons maintenant qu'on considère une extension abélienne finie de ℚ : comme je n'ai pas trop envie d'entrer trop dans les détails, je vais juste prendre l'exemple du corps ℚ(√−1) des rationnels gaussiens (c'est-à-dire des nombres de la forme a+b√−1 avec a et b rationnels) ; à une telle extension est associée une norme, et dans le cas de ℚ(√−1) il s'agit de N(a+b√−1) = a²+b² (produit de a+b√−1 et de son conjugué complexe ab√−1), et cette norme est multiplicative. Je peux aussi définir les idèles de ℚ(√−1) comme des familles d'expressions de la forme av + bv·√−1 où v parcourt les places de ℚ, avec av et bv dans ℚv sujets à la condition que la norme locale av² + bv² ne vaille jamais 0, et vaille 1 pour tous les v sauf un nombre fini. (Normalement les choses seraient plutôt définies en termes des places de ℚ(√−1) plutôt que celles de ℚ comme je viens de le faire, mais ma définition est bien équivalente à la définition usuelle. En la place ∞, il va de soi que l'expression a + b·√−1 sera vue comme un nombre complexe.) La famille de ces valeurs av² + bv², du coup, définit bien une idèle de ℚ, qu'on appelle la norme idélique de l'idèle de ℚ(√−1) qu'on considérait (i.e., la norme idélique s'obtient en formant la norme place par place). Bien sûr, les différentes places n'interagissent pas, donc une idèle de ℚ est une norme idélique si et seulement si elle est une norme locale en chaque place (i.e., sur mon exemple, si et seulement si chaque xv est une somme de deux carrés : par exemple, en la place ∞, ceci signifie précisément que x est un nombre réel (strictement) positif) — je vais donner ci-dessous les conditions exactes pour les autres places ci-dessous.

Ce qui intéresse la théorie du corps de classes, c'est le sous-groupe des idèles de ℚ (ou du corps de base, mais je me suis limité à ℚ) engendré par (A) les idèles diagonales, et (B) celles qui sont des normes pour l'extension abélienne finie considérée (norme idélique, c'est-à-dire en chaque place comme je viens de le dire). Et le contenu essentiel des théorèmes centraux de la théorie globale du corps de classe est que (1) ce sous-groupe des idèles détermine complètement l'extension abélienne, et on sait décrire exactement les sous-groupes qu'on obtient (ce sont les sous-groupes ouverts d'indice fini du groupe des idèles contenant les idèles diagonales), et (2) mieux, le quotient du groupe des idèles par le sous-groupe en question s'identifie au groupe de Galois de l'extension considérée.

Plutôt que de considérer les sous-groupes des idèles contenant les idèles diagonales, on peut aussi considérer, cela revient au même, les sous-groupes des classes d'idèles (qui sont, rappelons-le, définies comme les idèles modulo les idèles diagonales) : dans ce cas, le résultat s'énonce en affirmant que (1) le sous-groupe des classes d'idèles qui sont des normes détermine complètement l'extension abélienne, et on sait décrire exactement les sous-groupes qu'on obtient (ce sont les sous-groupes ouverts d'indice fini du groupe des classes d'idèles), et (2) le quotient du groupe des classes d'idèles par le sous-groupe des normes s'identifie au groupe de Galois de l'extension considérée.

Sur mon exemple de l'extension abélienne ℚ(√−1) de ℚ, on considère donc les idèles de ℚ qui sont produit (A) d'une idèle diagonale (:=qui vaut le même rationnel non nul en chaque place) et (B) d'une norme idélique (=idèle qui, en chaque place séparément, est somme de deux carrés). Je commence par considérer (B). Or un élément xv du complété ℚv est une norme locale (=somme de deux carrés) si et seulement si :

Les idèles de ℚ qui sont une norme idélique sont donc par définition celles dont la composante xv vérifie la condition correspondante ci-dessus en chaque place v.

Il se trouve d'ailleurs que pour cette extension (et plus généralement pour toute extension cyclique, mais pas toute extension abélienne), on a, en marge de la théorie du corps de classes, un principe local-global qui affirme : un rationnel x≠0 est une norme globale (=somme de deux carrés de rationnels) si et seulement si il est une norme en chaque place (i.e., l'idèle diagonale qu'il définit est une norme idélique, i.e., elle est une norme locale en chaque place) : autrement dit, concrètement dans mon cas, les conditions ci-dessus caractérisent exactement les rationnels non nuls qui sont sommes de deux carrés de rationnels ; à savoir : un rationnel non nul est somme de deux carrés si et seulement si il est positif, que l'exposant vp dans la décomposition en facteurs premiers est paire pour chaque p≡3 (mod 4), et que son l'écriture 2-adique se termine par 01 (puis uniquement des 0). (Il se trouve d'ailleurs qu'on peut omettre une de cette infinité de conditions — par exemple celle peu commode en la place 2 — parce qu'une idèle diagonale qui est une norme en chaque place sauf au plus une est encore une norme en cette dernière place.) Mais ce résultat sur les normes globales n'est pas celui dont je voulais parler.

Maintenant qu'on sait à quoi ressemble le groupe N(Jℚ(√−1)) des idèles de ℚ qui sont une norme idélique pour l'extension, à quoi ressemble le sous-groupe ℚ×·N(Jℚ(√−1)) engendré par (A) le groupe ℚ× des idèles diagonales (quelconques) et (B) le groupe des normes idéliques (N(Jℚ(√−1)), qu'on vient de décrire) ? En considérant séparément le nombre −1 et les nombres premiers p, chacun vu comme un rationnel non nul donc une idèle diagonale, et en utilisant la décomposition en facteurs premiers, on peut se convaincre que les idèles du sous-groupe ℚ×·N(Jℚ(√−1)) engendré par (A) et (B) sont celles qui « commettent un nombre impair d'infraction » aux conditions locales listées ci-dessus, i.e., les idèles telles que le nombre de places v où l'idèle ne vérifie pas la condition ci-dessus (équivalente à être somme de deux carrés en cette place) est impair. Le quotient J/(ℚ×·N(Jℚ(√−1))) du groupe J des idèles de ℚ par ce sous-groupe est le groupe cyclique à deux éléments (il n'y a que la « parité du nombre d'infractions » qui survit), et s'identifie bien au groupe de Galois de ℚ(√−1) sur ℚ.

Bref, de façon générale, la théorie du corps de classe « explique » les extensions abéliennes d'un corps global, ici ℚ, au moyen des sous-groupes du groupe des idèles de ce corps global contenant les idèles diagonales (les extensions abéliennes finies correspondent aux sous-groupes ouverts d'indice fini ; on peut aussi dire des choses sur les extensions infinies). Ou de façon équivalente, si on préfère, au moyen des sous-groupes du quotient C = J/ℚ× des idèles par les idèles diagonales (dit groupe des classes d'idèles).

Ce dont je me plains, c'est que les textes sur la théorie du corps de classe prennent rarement la peine de traiter des exemples un peu en détail, ne serait-ce que comme je viens de le faire, et surtout ne se fatiguent pas à expliquer comment « sont faits » les sous-groupes du groupe des idèles contenant les idèles diagonales (ou du groupe des classes d'idèles).

Le problème, c'est que quand on lit les choses un peu rapidement, et comme personne n'attire l'attention sur une difficulté, on se dit certainement oh, le groupe des idèles, c'est une sorte de produit, les idèles diagonales elles ne doivent pas peser très lourd dans l'histoire, donc les sous-groupes du groupe d'idèles contenant les idèles diagonales (ou les sous-groupes du groupe de classes d'idèles) ils doivent ressembler à des sous-groupes d'un groupe produit. Or un sous-groupe d'un groupe produit (fût-il ouvert d'indice fini), en général, ce n'est pas forcément un produit de sous-groupes des différents facteurs. Mais ici, les normes idéliques elles se calculent composante par composante : donc, vu qu'un sous-groupe ouvert d'indice fini du groupe des classes d'idèles est forcément donné par la norme d'une extension abélienne, il se voit bien composante par composante ! De là une certaine confusion, qui m'a beaucoup tracassé.

S'agissant de ℚ, on peut pourtant décrire assez bien le groupe C = J/ℚ× des classes d'idèles (:=idèles modulo les idèles diagonales). En effet, toute idèle de ℚ s'écrit de façon unique comme le produit d'une idèle diagonale par une idèle dont la composante réelle est strictement positive et la composante p-adique est, pour tout p fini, de valuation p-adique nulle (i.e., appartient au groupe ℤp× des inversibles de ℤp). Il s'ensuit que le groupe C des classes d'idèles est vraiment isomorphe (en tant que groupe et en fait, même, en tant que groupe topologique) au produit du groupe des réels strictement positifs par chacun des groupes ℤp× des p-adiques de norme 1 (=valuation 0). La théorie du corps de classes global sur ℚ peut donc être vue comme mettant en correspondance les sous-groupes ouverts d'indice fini de ce groupe produit et les extensions abéliennes finies de ℚ. Sur mon exemple de ℚ(√−1) sur ℚ, le groupe des classes d'idèles qui sont des normes (pour cette extension) correspond (par cet isomorphisme) au sous-groupe de ce produit donné par le même produit mais où ℤ2× (=ensemble des 2-adiques congrus à 1 ou 3 modulo 4) a été remplacé par son sous-groupe (1+4ℤ2) des 2-adiques congrus à 1 modulo 4 (c'est un sous-groupe d'indice 2).

Bref, il y a deux façons assez différentes de voir un sous-groupe du groupe des classes d'idèles (ou, de façon équivalente, un sous-groupe du groupe d'idèles contenant les idèles diagonales) :

(La raison pour laquelle ces deux approches arrivent quand même à coïncider est que les idèles diagonales ne sont pas du tout innocentes dans l'histoire : à cause de résultats d'approximation, qui sont ici assez faciles à voir, les idèles diagonales permettent de « contrôler » simultanément n'importe quel nombre fini de places.)

Ainsi, sur mon exemple de l'extension ℚ(√−1) de ℚ, selon la deuxième approche il n'y a qu'une condition locale à la place 2 (être congru à 1 modulo 4), alors que selon la première approche, il y a des conditions locales aux places ∞, 2, et tous les p congrus à 3 modulo 4. Les choses sont compliquées par le fait que ce que j'ai appelé la « deuxième approche » n'est pas entièrement bien définie, il y a plusieurs façons de voir le groupe des classes d'idèles — déjà on peut le décrire comme les idèles vérifiant un certain nombre de conditions locales modulo les idèles diagonales vérifiant les mêmes conditions locales, et c'est dans cet ordre d'idées qu'on voit les groupes de classes de rayons comme des quotients du groupe de classes d'idèles : mais l'idée générale reste qu'il faut faire bien attention à ce qu'on appelle une « condition locale » définissant un sous-groupe des classes d'idèles, et en tout cas, qu'on ne peut pas prétendre avoir compris la théorie du corps de classes si on croit pouvoir faire l'économie d'une réflexion sur ce que sont les sous-groupes du groupe de classes d'idèles.

(vendredi)

Fatherland de Robert Harris

J'ai récemment fini de lire le roman Fatherland de Robert Harris (je n'arrive d'ailleurs pas à me rappeler qui me l'a conseillé : il traînait sur ma wishlist Amazon depuis un temps indéfini). Il s'agit d'un policier (ou d'un thriller, je ne sais pas bien ce qu'on doit dire) qui se déroule à Berlin, en 1964, dans une uchronie où la seconde guerre mondiale aurait été gagnée par l'Allemagne en Europe et aurait continué en guerre froide (entre l'Europe dominée par l'Allemagne et les États-Unis) dont amorce une détente. (C'est d'ailleurs intéressant que cette situation évoque la seconde moitié du livre Making History de Stephen Fry, dont on pourrait presque imaginer qu'elle se déroule dans le même univers, mais de l'autre côté de l'Atlantique. Enfin bon, je suppose qu'il y a des zilliards de livres qui ont été écrits sur cette prémisse, et sans doute même des gens qui ont entrepris de classifier ces uchronies et de les comparer les unes aux autres.)

Ceci étant, je n'arrive pas vraiment à décider si j'ai aimé ce livre. Il est vrai que j'ai été assez captivé au sens où j'étais assez intéressé à savoir la suite pour continuer à lire de façon plutôt frénétique. Il est vrai aussi que l'uchronie a l'air assez bien construite, le monde m'a semblé plutôt crédible et (du peu que je connais de l'histoire de l'Allemagne nazie) conforme à la réalité historique ou à son prolongement dans ce monde. Il y a quelques erreurs mineures (comme le fait que la carte que j'ai dans mon édition du livre semble montrer l'Alsace-Lorraine en France, ce qui est manifestement une erreur et d'ailleurs contredit explicitement dans le texte, mais il semble que d'autres éditions soient correctes de ce point de vue ; j'ai aussi repéré une faute idiote d'allemand, quelque chose comme das schwarzes Korps avec une ‘s’ en trop), mais rien d'important. En revanche, j'ai trouvé bien des passages un peu laborieux, ou faciles, ou prévisibles, ou tout ça à la fois. Mais ce qui est surtout bien fait, c'est la façon dont est rendue l'atmosphère étouffante dans le Berlin d'une allemagne nazie triomphante et dans l'Europe qu'elle dominerait : on se sent vraiment mal à l'aise — de ce point de vue, le livre est une réussite.

J'en profite, puisque je viens aussi de finir de les lire, pour signaler deux livres que je ne recommande pas du tout : Dirk Gently's Holistic Detective Agency et sa (plus ou moins) suite, The Long Dark Tea-Time of the Soul, de Douglas Adams. J'attendais beaucoup mieux de l'auteur du Hitchhiker's Guide to the Galaxy, mais franchement, le premier est médiocre et le second est carrément mauvais : l'idée d'un roman humoristique racontant les enquêtes surnaturelles d'un détective génial mais raté qui croit que tout est relié dans l'Univers n'était pas mauvaise, mais la réalisation est une accumulation de non sequitur beaucoup moins drôle qu'elle cherche à l'être, et qui se finit par une absence à peu près complète d'explications.

(jeudi)

Sur la réalité des quaternions, quasars, quarks et quaggas

J'ai une fois de plus commis l'erreur de commencer (il y a deux-trois semaines) l'écriture d'une entrée que je pensais pouvoir faire courte et qui a grandi, grandi, grandi, jusqu'à prendre des proportions totalement délirantes. Comme je vais être assez débordé ces prochaines semaines, elle risque de rester indéfiniment dans les limbes, là où j'ai déjà mis tout ce que j'ai écrit sur les octonions et tant d'autres choses. Tout ceci m'énerve prodigieusement, et je ne sais pas quoi faire pour réussir à éviter ce problème.

Pour me distraire un peu, je voudrais juste faire une remarque sur la philosophie des mathématiques. Comme il n'aura échappé à personne, je suis férocement platoniste (au moins en ce qui concerne l'arithmétique), où par platonisme (voir aussi cette entrée, et notamment cette petite section de celle-ci pour plus de détails) j'entends le point de vue selon lequel les concepts mathématiques, ou au moins les plus « naturels » d'entre eux, ont une existence autonome, indépendante de l'esprit humain, qui ne fait que les découvrir, et même indépendante de l'univers matériel. (Il y a, bien sûr, toutes sortes de variantes[#][#2] de cette position, et on peut être d'accord avec certaines sans être d'accord avec d'autres, on peut d'ailleurs aussi considérer qu'il ne s'agit pas vraiment d'une différence d'opinion philosophique mais simplement de façon de dire les choses. À ce sujet, voir aussi cette autre entrée.)

Je crois avoir lu quelque part (mais je ne sais plus si un sondage précis à été fait dans ce sens ou si cette affirmation sortait d'un grand chapeau de magicien) que la majorité des mathématiciens, et l'écrasante majorité des logiciens, adhère au moins à une forme modérée de platonisme. A contrario, les neurologues semblent généralement persuadés (là aussi, il s'agit d'une statistique qui, comme 83.28% des statistiques, est purement et simplement inventée) que les mathématiques sont uniquement le résultat de processus cognitifs dans le cerveau humain et n'ont rien de « réel » ou d'« universel » (pas plus que, disons, la beauté de la musique de Bach).

Les arguments les plus souvent invoqués contre le platonisme mathématique, c'est-à-dire, pour montrer que les mathématiques viennent de l'esprit humain et pas d'un « paradis platonique », sont typiquement d'observer que les mathématiques ne sont pratiquées que par les humains (le summum des facultés mathématiques des animaux se limitant à savoir compter sur de tout petits entiers naturels), et aussi que celles-ci ont changé au cours de l'histoire (ce qui est de mauvais augure pour la découverte d'un monde censément intemporel).

Mais une chose que je ne comprends pas est pourquoi ce genre d'arguments, invoqué pour dire chers mathématiciens, les quaternions n'existent que dans votre cerveau ne l'est pas aussi pour dire chers astrophysiciens, les quasars n'existent que dans votre cerveau ou chers physiciens des particules, les quarks n'existent que dans votre cerveau, voire, chers zoologistes, les quaggas n'existent que dans votre cerveau. Après tout, si le problème est qu'on ne peut pas toucher un quaternion, qu'on ne peut les détecter qu'indirectement par le truchement de théories qui prédisent leur existence, et que seuls les humains sur cette Terre ont le moindre concept de quaternions dans leur tête, et encore, seulement depuis quelques siècles, exactement la même chose vaut pour les quarks et les quasars : jamais je ne pourrai toucher un quark ou un quasar, aucun animal autre que l'homme n'a affaire à eux ou de représentation mentale de ces choses-là, il y a simplement des scientifiques qui nous disent mon accélérateur de particules a vu trois quarks dans chaque proton, mon radiotélescope a détecté un quasar dans telle direction, mes calculs ont exhibé une structure abstraite de dimension 4 sur les réels qui se comporte comme une algèbre à divisions. Même les quaggas, je n'en ai, après tout, jamais touché, et comme c'est une espèce éteinte ça ne risque pas de se produire, et j'ai beau avoir des témoignages de gens qui en ont dessiné ou de biologistes qui assurent que ces bestioles ont existé, je ne vois pas pourquoi ils seraient plus (ou moins) crédibles que les physiciens qui disent que les quarks et les quasars existent ou les mathématiciens qui disent que les quaternions existent.

Or j'ai rarement entendu des gens transposer à la physique ou à d'autres domaines la position anti-platoniste qu'ils peuvent avoir au sujet des mathématiques. Y a-t-il des neurologues qui disent aux physiciens ce que vous appelez étoile à neutron n'est que le fruit de vos processus cognitifs [remplacer étoile à neutron par n'importe quoi de difficile à imaginer] ? Voire, qui disent aux autres neurologues ce que vous appelez neurone n'est que le fruit de vos processus cognitifs (de nouveau, on ne peut pas toucher directement un neurone, il faut faire confiance à la théorie du microscope).

Les tenants du platonisme mathématique sont souvent décriés comme religieux, parce qu'ils croient en une sorte de perfection intangible et accessible uniquement par l'esprit (et c'est vrai que le choix d'un terme comme paradis platonique n'est certainement pas pour aider). Je ne sais pas pourquoi ce reproche n'est pas fait aux physiciens des particules[#3] qui prétendent que les quarks et atomes sont vraiment les composants de toute notre matière.

Au contraire, l'attitude consistant à dire je ne crois réel que ce que je peux toucher (et notamment sa variante ultrafinitiste, les grands nombres n'ont pas de sens parce que je ne peux pas les voir) me semble être exactement la même que ceux qui prétendent je ne peux pas croire que la Terre soit plus vieille que 6000 ans environ, parce que je n'ai que des preuves indirectes des millions d'années censées nous avoir précédées. À partir du moment où on accepte l'épistémologie des mathématiques, sa démarche scientifique pour arriver à une vérité (et il est difficile de la nier compte tenu de l'extrême utilité pratique des mathématiques, entre la construction des ponts et la cryptographie !), il faut bien reconnaître qu'elles nous renseignent sur quelque chose qui n'est pas sujet à notre bon vouloir comme la poésie ou la musique — et qu'elles sont, sur le même plan, que les autres sciences, une entreprise visant à découvrir systématiquement une réalité préexistante.

Bref, je comprends la position extrême je ne crois réel que ce que je peux directement toucher (donc je ne crois réels ni les quaternions, ni les quarks, ni les quasars, ni les quaggas, ni la planète Jupiter, ni les virus, ni Louis XIV), mais je ne comprends pas ceux qui l'appliquent uniquement pour les mathématiques et aucune autre science.

[#] Par exemple, je suis tenté de distinguer le platonisme structural, qui serait la position selon laquelle les structures que nous pensons discerner (les groupes, par exemple) sont « naturelles » et « découvertes », et le platonisme logique, orthogonal, qui serait la position selon laquelle les fondements mêmes des mathématiques (entiers naturels ou ensembles), sur lesquels on pose ces structures, ont une existence. Essentiellement, le platonisme structural affirmerait qu'on découvre les définitions tandis que le platonisme logique affirmerait qu'on découvre les axiomes. On peut parfaitement croire à l'un mais pas à l'autre (que la définition d'un groupe est naturelle, mais que les mathématiques n'aient pas de fondement logique immatériel) ou à l'autre mais pas à l'un (que les entiers naturels ou une forme quelconque de monde platonique préexistent à l'univers matériel, mais que la façon dont on le structure est profondément humaine), ou au deux, ou ni à l'un ni à l'autre.

[#2] Concernant ce que j'appelle le platonisme logique dans la note précédente, on peut aussi tenir toutes sortes de positions, par exemple l'idée que les entiers naturels (ou n'importe quoi qui permet d'encoder les structures finies) ont une position spéciale et sont le seul substrat ayant une réelle « existence platonique », ou bien étendre cette position à des objets plus complexes, comme les ensembles d'entiers naturels, ou tous les ensembles (un platoniste ensembliste doit croire que l'hypothèse du continu à une valeur de vérité bien définie, même si les axiomes de ZFC ne permettent pas de la trouver) ; à l'inverse, s'agissant des ensembles, on peut croire à un multivers platonique plutôt qu'un univers platonique.

[#3] Peut-être parce que les physiciens des particules ont des détecteurs expérimentaux ? Mais les mathématiques expérimentales existent aussi, et je ne vois pas de différence importante entre faire s'entrechoquer des protons à haute énergie pour chercher à trouver, peut-être, un compagnon supersymétrique, ou bien faire tourner des ordinateurs à calculer les valeurs de la fonction ζ pour chercher à trouver, peut-être, un zéro non-trivial qui ne soit pas sur l'axe critique.

Only the 20 most recent entries were included above. Continue to older entries.

Seules les 20 plus récentes entrées ont été incluses ici. Continuer à lire les entrées plus anciennes.