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)

Ma ligne téléphonique a été coupée

Avant-hier (lundi 15), assez brutalement à 16h03, notre connexion ADSL a commencé a avoir des vapeurs : déconnexions toutes les quelques minutes, avec au final environ 2/3 du temps connecté et un débit pourri. Je me suis dit que c'était notre fournisseur d'accès qui avait des problèmes techniques (ça lui arrive occasionnellement). Hier matin, les problèmes semblaient un peu atténués, mais ils sont revenus dans l'après-midi : j'ai commencé à soupçonner que le modem ADSL était mourant ce qui m'a déjà causé des problèmes semblables. Mon poussinet a appelé le support technique du fournisseur d'accès, qui a convenu que le bruit était anormalement élevé sur la ligne et a dit qu'il faudrait essayer de faire un test sans filtre (on ne pouvait pas immédiatement puisque personne n'était à la maison), et en attendant il a dit qu'il allait rebooter la « carte » (je ne sais pas ce que c'est) pour voir si ça améliorait les choses. Ça ne les a pas améliorées et, en fait, nous avons totalement perdu la connexion à ce moment.

Je suis rentré à la maison (hier mardi 16 après-midi, donc) et j'ai constaté que non seulement nous n'avions plus du tout l'ADSL (pas de synchro), mais, en fait, nous n'avions même plus la tonalité téléphonique. Notre ligne est complètment morte.

J'ai appelé le service des dérangements au 1013, je suis tombé sur un répondeur vocal qui m'a appris que le service était connu et affectait plusieurs clients, que des techniciens travaillaient dessus, et que je pourrais en savoir plus sur leur site Web, rubrique infos incidents. Celui-ci me dit :

Vos services sont interrompus suite à un incident sur le réseau Orange. Nous prévoyons un rétablissement complet au plus tard le 17/09/2014 fin de matinée. Nous vous prions de nous excuser pour la gêne occasionnée.

Bon, pourquoi pas. Ce matin (mercredi 17), au réveil (vers 7h), la synchro ADSL était revenue, certes avec un débit complètement pourri (environ 1/6 de ce que nous avions normalement, dans les deux sens), mais c'est déjà mieux que rien et c'est possible qu'un équipement ait décidé de baisser la qualité de la ligne par sécurité — d'ailleurs, rien que rebooter le modem a amélioré les choses d'un facteur 2 (ce qui restait à environ 1/3 de ce que nous avions normalement).

Là où ça devient moins drôle, c'est que la ligne a été de nouveau coupée dans l'après-midi (mercredi 17). De nouveau plus de synchro ADSL et plus de tonalité. Et surtout, là où je trouve que France Télécom Orange se fout de moi, c'est que le message sur leur site est toujours exactement le même et promet un rétablissement pour au plus tard un instant dans le passé. Et pas un mot sur la cause technique du problème : des travaux auraient-ils coupé les fils de cuivre ? un incendie dans le central aurait-il endommagé des équipements ? autre chose ? j'aimerais bien le savoir, moi, au lieu qu'on me laisse comme un con avec la phrase qui ne veut rien dire un incident sur le réseau Orange. Même si ça doit prendre un peu de temps des techniciens chargés de s'occuper du problème, et donc en retarder de quelques minutes la résolution, ça vaut la peine d'expliquer ce qui se passe (par exemple, si on nous dit qu'il s'agit des travaux en cours rue Chéreau qui auraient endommagé les lignes, une meute d'usagers en colère peut aller engueuler les gens qui ont fait ça, au moins ça nous défoulera). En l'état actuel, je sais juste que je n'ai plus le téléphone ni accès à Internet (de chez moi — et comme mon mobile n'y capte rien, je ne peux même pas m'en servir comme secours), et je ne sais ni pourquoi ni pour combien de temps ni qui est responsable.

Et je me rends surtout compte de combien je ne peux rien faire sans cet accès Internet. Dès que je veux noter quelque chose sur mon agenda, par exemple, je me rends compte que mon agenda est sur mon ordinateur à la maison, auquel je n'ai plus accès depuis mon bureau : bien sûr, ce n'est pas très difficile d'aller le chercher (surtout que je travaille à 10 min à pied de chez moi), mais dès que je reviens, je me rends compte que j'ai besoin d'un autre fichier (un article de maths au format électronique), puis d'un autre (un livre idem), puis d'un autre (mon fichier de numéros de téléphone), et c'est un peu technique de prendre mes quatre disques durs pour aller au bureau. J'ai donc passé trois jours complètement improductifs à essayer de guetter les quelques minutes où la connexion fonctionnait miraculeusement pour en faire usage.

Inutile de dire que ma fatigue colossale a augmenté d'un bon cran dans l'histoire.

Suite : (70 heures après le début des problèmes) : toujours pas de résolution en vue, ni la moindre explication du problème ; le site orange.fr continue d'afficher mensongèrement qu'ils prévoient un rétablissement complet pour hier matin. • J'ai envoyé un fax à l'Unité d'Intervention de Paris d'Orange (en googlant un peu, on trouve leurs coordonnées…), on va voir si quelqu'un a la décence d'y répondre.

(lundi)

La fonction de Fabius

[Graphe de la fonction de Fabius sur [0;24]]

J'ai déjà raconté trente-douze fois sur ce blog, et je continuerai à radoter à ce sujet, qu'une de mes motivations à être mathématicien, c'est de pouvoir visiter le petit musée des objets mathématiques remarquables, admirables, ou simplement curieux. L'objet dont je veux parler ici est plus amusant que fascinant, ce qui ne l'empêche pas d'être élégant. Il s'agit d'une fonction réelle définie par un certain J. Fabius (j'ignore le prénom ou s'il y a un lien de parenté avec l'actuel ministre français des affaires étrangères) dans une publication de 1966.

[Graphe de la fonction de Fabius sur [0;1]]Voici une première définition possible : on appelle Un (pour n≥1 entier) une suite de variables aléatoires indépendantes et uniformément réparties dans [0;1], et on pose Z = ∑n Un/2n (remarquer que Z est aussi une variable aléatoire à valeurs dans [0;1]). Alors la fonction de Fabius f sur [0;1] est la distribution de probabilité de la variable Z (c'est-à-dire que f(t), pour t∈[0;1], est la probabilité que Zt). (Le graphe en est tracé ci-contre à gauche.) Pour souligner que cette loi de probabilité n'est pas complètement bizarre ou surgie de l'espace, on peut remarquer que si au lieu d'une variable Un uniformément répartie dans [0;1] on utilisait des variables Vn (toujours indépendantes et) uniformément réparties dans {0;1} (c'est-à-dire valant 0 avec probabilité ½ et 1 avec probabilité ½), alors ∑n Vn/2n serait uniforément répartie dans [0;1] puisque la construction revient à tirer chaque bit de cette variable à pile ou face indépendamment.

Pour compléter f aux réels positifs, on décrète alors que f(t+1) = 1−f(t) pour t∈[0;1], et que f(t+2k) = −f(t) pour t∈[0;2k] (lorsque k≥1 est entier). Le caractère naturel de ce prolongement va apparaître dans ce qui suit. (Le graphe de la fonction ainsi prolongée est tracé en haut de cette entrée.)

La fonction possède un lien très fort avec la suite de Morse-Thue, qui peut être définie comme la suite dont le n-ième terme vaut 0 ou 1 selon que le nombre de 1 dans l'écriture binaire de n (=le poids de Hamming H(n) de n) est pair ou impair ; si on préfère, la suite de Morse-Thue est celle qui s'obtient en partant d'un 0 et en effectuant un nombre infini de fois le remplacement simultané de 0 par 01 et de 1 par 10 (cf. l'article Wikipédia). Comme on peut le voir sur le graphe ci-dessus (et ce n'est pas difficile avec la définition que j'ai donnée), le signe de f sur l'intervalle [2n;2n+1] vaut + ou − selon que la valeur du n-ième terme de la suite de Morse-Thue est 0 ou 1.

[Construction de la fonction de Fabius]Voici une autre définition possible de la fonction de Fabius, dans cet esprit : on appelle d'abord f0 la fonction qui sur l'intervalle [2n;2(n+1)[ vaut +½ ou −½ selon que la valeur du n-ième terme de la suite de Morse-Thue est 0 ou 1 ; puis par récurrence sur k, on appelle fk+1(x) l'intégrale de fk(t) pour t allant de 0 à 2x. La suite de fonctions en question converge alors uniformément vers f. (Ci-contre, j'ai tracé f0 en vert, f1 en un vert subtilement différent, f2 en caca d'oie et f en bleu.)

[Graphe de la fonction de Fabius sur [0;24] et de sa dérivée]Qu'on utilise l'une ou l'autre construction, il n'est pas très difficile de voir que la fonction de Fabius vérifie l'équation fonctionnelle surprenante suivante : f′(t) = 2f(2t) pour tout t≥0. (Pour l'illustrer, j'ai tracé la fonction de Fabius accompagnée de sa dérivée f′.) Notons qu'il ne s'agit pas d'une équation différentielle, puisque la valeur de la dérivée est reliée à la valeur de la fonction en un autre point ; d'ailleurs, il n'y a pas unicité de la solution de cette équation : la fonction nulle la vérifie aussi (avec, d'ailleurs, la même « condition initiale » f(0)=0) ; néanmoins, l'équation en question et la connaissance de la fonction f sur [0;1] définit de façon unique sa valeur sur tous les réels positifs.

Puisque f(0)=0, l'équation fonctionnelle f′(t) = 2f(2t) implique de façon assez évidente que toutes les dérivées de f en 0 valent 0 : la fonction de Fabius est infiniment plate en 0. En fait, il aussi facile de voir qu'en n'importe quel rationnel dyadique, toutes ses dérivées s'annulent à partir d'un certain rang : par conséquent, f n'est pas égale à la somme de sa série de Taylor développée en un dyadique, et comme les dyadiques sont denses dans les réels, f est une fonction C mais nulle part analytique (c'était la motivation de son introduction). On peut aussi se persuader que, en une valeur comme 1/3, la série de Taylor de f a un rayon de convergence nul (parce que la dérivée r-ième de f est donnée par f(r)(t) = 2r(r+1)/2·f(2r·t)).

Mais il y a quantité de choses que j'ignore. Par exemple, expérimentalement, il semble que f(1/4) = 5/72, et je ne sais pas le prouver (pas que j'aie essayé, du reste). Il serait tentant de penser, pour l'expliquer, qu'il y ait une relation entre f(t) et f(t+½) comme il y en a entre f(t+2s) pour tout s≥0 entier, mais une telle relation ne peut pas, il me semble, être algébrique, donc je ne sais pas ce qu'on est en droit d'espérer. Je ne sais pas non plus si on peut dire quelque chose d'intelligent de la valeur f(1/3) ≈ 0.180165114801 (cette valeur n'évoque rien à Google, mais Google n'est pas très bon pour faire du calcul symbolique inverse ; elle n'évoque rien non plus à ce site ni à Wolfram Alpha). Pourtant, l'écriture binaire du nombre 1/3 est suffisamment remarquable pour qu'on soit en droit de penser que la fonction f devrait en faire quelque chose d'intéressant.

Enfin, je dois signaler que je ne sais pas vraiment calculer les valeurs de f de façon efficace. Le mieux que je connaisse est une expression de fk que j'écris en MathML pour ceux dont le navigateur le supporte :

f k ( x ) = 2 k(k+1)/2 k! 0j2k1x cj ( x j2k1 ) k c0 = 12 et cj = 12 ( (1) H(j) (1) H(j1) ) si j>0

(j'ai noté H(j) pour le poids de Hamming de j). Mais cette équation n'est pas vraiment satisfaisante parce qu'elle ne relie pas fk+1 à fk, par exemple par une sorte de dichotomie. Bref, la fonction de Fabius reste assez mystérieuse à mes yeux.

Ajout : dans un même esprit, voir aussi la fonction ‘?’ [point d'interrogation] de Minkowski dont j'avais déjà parlé autrefois.

(dimanche)

Comment m'éviter de dormir sur le dos ?

Je suis infiniment fatigué en ce moment. Nerveusement avant tout, parce que l'été n'a rien eu de reposant, j'ai l'impression de n'avoir fait que rattraper des affaires en regard et gérer des ennuis qui me tombaient dessus ; et les quelques jours où j'ai voyagé m'ont encore plus fatigué (je trouve les déplacements terriblement stressants, j'aurais besoin de temps pour décomprimer un peu après, mais je ne l'ai pas eu). Et surtout, j'attaque une rentrée compliquée — mon emploi du temps est désastreux, je dois faire avec des horaires irréguliers et malcommodes et pas la moindre possibilité de souffler un peu avant Noël (où je devrai de nouveau affronter un voyage fatigant). Un nombre terrifiant de gens comptent sur moi pour faire des choses diverses et variées, dont je n'aurai évidemment pas le temps de mener à bien le quart, (parfois j'ai presque l'impression d'être harcelé), et dès que c'est moi qui essaie de demander quelque chose à d'autres, soit je n'arrive pas à me décharger comme je le voudrais, soit je passe encore plus de temps à demander (ou à trouver à qui demander) que je n'en passerais à faire les choses moi-même. Bref, je suis débordé et épuisé, et bien seul avec mes tracas.

Mais je suis aussi fatigué physiquement, ce qui n'aide pas. Mon poussinet se contente de me dire si tu es fatigué, il faut te coucher à chaque fois que je me plains d'être à bout, ce en quoi il n'a peut-être pas tord, mais je dors déjà beaucoup (ce qui n'aide pas à faire des choses dans la journée et à être moins débordé, bien sûr).

Un aspect du problème est certainement que je respire mal pendant la nuit (j'ai probablement une forme mineure d'apnée du sommeil), dès que je me mets sur le dos. Mon poussinet — du moins s'il se trouve être réveillé — me pousse régulièrement pendant la nuit pour me mettre sur le côté, mais parfois je suis très entêté à dormir sur le dos et à ronfler voire m'étouffer. Il a aussi souvent essayé de me bloquer avec une peluche, mais je la repousse sans ménagement.

Je pourrais essayer, par exemple, de dormir avec un sac à dos (en essayant de mettre quelque chose dans le sac à dos pour que ce soit juste assez inconfortable pour que je ne sois pas tenté de dormir sur le dos, mais pas assez pour me faire mal), mais j'ai peur que ça m'empêche purement et simplement de dormir. L'ennui c'est que, si je dors bien sur le côté, j'éprouve régulièrement le besoin de changer de côté au cours de la nuit (selon la manière dont mes narines se bouchent), c'est probablement au cours de ces changements de côté pas bien achevés que je me retrouve sur le dos : il faut que j'invente une façon de m'empêcher de me mettre sur le dos qui ne m'empêche pas pour autant de passer du côté gauche au côté droit ou inversement, et là je manque d'idée. (Certes, on peut changer de côté en basculant sur le ventre plutôt que sur le dos, mais c'est beaucoup moins naturel vu que quand je suis allongé sur le côté gauche je suis aussi décalé vers la droite de l'oreiller et vice versa.)

(mercredi)

Je découvre encore un bug improbable

Ayant installé de nouveaux disques durs dans le PC chez mes parents, je fais ce que je fais régulièrement, à savoir compiler un Firefox. La compilation échoue sur quelque chose que je ne comprends pas du tout :

pleiades david /usr/local/src/mozilla/obj-i686-pc-linux-gnu/intl/icu/target/data $ LD_LIBRARY_PATH=../lib:../stubdata:../tools/ctestfw:$LD_LIBRARY_PATH ../bin/genrb -k -R -i ./out/build/icudt52l -s /hugetmp/mozilla/intl/icu/source/data/coll -d ./out/build/icudt52l/coll root.txt
/hugetmp/mozilla/intl/icu/source/data/coll/root.txt:15: Collation could not be built- U_FILE_ACCESS_ERROR. Make sure ICU's data has been built and is loading properly.
/hugetmp/mozilla/intl/icu/source/data/coll/root.txt:15: parse error. Stopped parsing resource with U_FILE_ACCESS_ERROR
couldn't parse the file root.txt. Error:U_FILE_ACCESS_ERROR

Comme tout bon Unixien confronté à un comportement bizarre d'un programme qu'il ne connaît même pas, j'ai le réflexe strace. Et là, les choses deviennent encore plus mystérieuses :

pleiades david /usr/local/src/mozilla/obj-i686-pc-linux-gnu/intl/icu/target/data $ strace -f -o /tmp/dump -E LD_LIBRARY_PATH=../lib:../stubdata:../tools/ctestfw:$LD_LIBRARY_PATH ../bin/genrb -k -R -i ./out/build/icudt52l -s /hugetmp/mozilla/intl/icu/source/data/coll -d ./out/build/icudt52l/coll root.txt
strace: ../bin/genrb: command not found

Comment ça, command not found ? Je n'ai aucune idée de ce que le programme ../bin/genrb est censé faire, mais je suis sûr qu'il existe et qu'il s'exécute correctement. Pourquoi strace prétend-il ne pas pouvoir le trouver ?

Et pourquoi le fait d'avoir changé les disques durs de ma machine ferait-il échouer la compilation de Firefox ?

Je vous épargne la manière dont j'ai résolu le mystère (j'ai commencé par strace strace lui-même, qui ne m'a montré aucune erreur, ce qui rendait les choses encore plus incompréhensible, et j'ai fini par patcher le truc pour afficher la valeur de errno). Le secret était que la partition /hugetmp sur laquelle je compilais faisait plus de 2To, et que j'y avais mis un système de fichier XFS. Or pour les gros systèmes de fichiers, XFS utilise des numéros d'inodes de plus que 32-bits. Mon noyau est 64-bits, donc lui n'a pas de problème avec ça, mais sur cette machine j'ai un userland de 32-bits : dans ces conditions, tout dépend de si le programme a été compilé avec -D_FILE_OFFSET_BITS=64 ou non : si ce n'est pas le cas (ce qui, apparemment, vaut pour le strace de ma Debian comme pour le programme qui échouait en premier lieu), lorsque stat() est appelé sur un fichier et qu'un des champs de la structure de retour (typiquement, la taille, ou le numéro d'inode) dépasse le type 32-bits que la structure prévoit, alors la libc produit l'erreur EOVERFLOW (qui n'apparaît pas dans le strace du strace parce que ce n'est pas le noyau qui la renvoie, c'est la libc) ; et si on se contente de regarder si stat() a réussi ou pas, on a l'impression que le fichier n'existe pas ou qu'il y a une erreur d'accès.

Moralité :

Noter que contrairement à ce que prétend la doc (if no inode size is given on the command line, mkfs.xfs will attempt to choose a size such that inode numbers will be < 32 bits. If an inode size is specified, or if a filesystem is sufficently large, mkfs.xfs will warn if this will create inode numbers > 32 significant bits), mkfs.xfs n'a, lorsque j'ai créé le système de fichiers, ni choisi une taille d'inode suffisante pour rester avec des numéros d'inode de 32-bits, ni affiché d'avertissement.

(lundi)

Les disques durs se cachent pour mourir

Je ne vais pas commencer à raconter tout le temps que j'ai perdu cet été avec mes ordinateurs : entre mon père qui a décidé de déménager plein de choses dans son sous-sol et qui a branché l'alimentation du disque dur externe de la machine servant de routeur sur un transformateur délivrant la mauvaise tension, et un ordinateur hébergé à l'ENS qui a été déconnecté sans aucun avertissement et qui m'a valu quantité de mails pour expliquer la situation aux utilisateurs, rien que raconter les choses prendrait plus de temps que je n'en ai.

La dernière péripétie est que deux des trois disques durs du PC que j'ai chez mes parents (et qui me sert notamment de stockage de sauvegardes) ont décidé de mourir simultanément, et, qui plus est, pendant que j'étais en vacances en Allemagne. L'un (un Maxtor DiamondMax® STM3750330AS de 750Go, acheté en avril 2008 et utilisé seulement depuis novembre 2011, nommé sdc ou ata2.01 dans les logs qui suivent) a brutalement cessé purement et simplement de répondre à la moindre commande :

Sep  1 22:37:43 pleiades kernel: [1749716.736036] ata2.01: exception Emask 0x0 SAct 0x0 SErr 0x0 action 0x6 frozen
Sep  1 22:37:43 pleiades kernel: [1749716.736044] ata2.01: failed command: SMART
Sep  1 22:37:43 pleiades kernel: [1749716.736050] ata2.01: cmd b0/da:00:00:4f:c2/00:00:00:00:00/10 tag 0
Sep  1 22:37:43 pleiades kernel: [1749716.736050]          res 40/00:01:01:4f:c2/00:00:00:00:00/10 Emask 0x4 (timeout)
Sep  1 22:37:43 pleiades kernel: [1749716.736054] ata2.01: status: { DRDY }
Sep  1 22:37:48 pleiades kernel: [1749721.785014] ata2: link is slow to respond, please be patient (ready=0)
Sep  1 22:39:47 pleiades kernel: [1749724.182021] ata2: soft resetting link
Sep  1 22:39:47 pleiades kernel: [1749731.416141] ata2.01: qc timeout (cmd 0xec)
Sep  1 22:39:47 pleiades kernel: [1749731.416149] ata2.01: failed to IDENTIFY (I/O error, err_mask=0x4)
Sep  1 22:39:47 pleiades kernel: [1749731.416153] ata2.01: revalidation failed (errno=-5)
Sep  1 22:39:47 pleiades kernel: [1749736.312020] ata2: soft resetting link
Sep  1 22:39:47 pleiades smartd[5643]: Device: /dev/sdc, not capable of SMART self-check 
Sep  1 22:39:47 pleiades kernel: [1749736.482563] ata2.01: configured for UDMA/133
Sep  1 22:39:47 pleiades kernel: [1749736.482584] ata2: EH complete
Sep  1 22:39:47 pleiades kernel: [1749746.720034] ata2.01: exception Emask 0x0 SAct 0x0 SErr 0x0 action 0x6 frozen
Sep  1 22:39:47 pleiades kernel: [1749746.720043] ata2.01: failed command: SMART
Sep  1 22:39:47 pleiades kernel: [1749746.720050] ata2.01: cmd b0/d0:01:00:4f:c2/00:00:00:00:00/10 tag 0 pio 512 in
Sep  1 22:39:47 pleiades kernel: [1749746.720050]          res 40/00:01:01:4f:c2/00:00:00:00:00/10 Emask 0x4 (timeout)
Sep  1 22:39:47 pleiades kernel: [1749746.720054] ata2.01: status: { DRDY }
Sep  1 22:39:47 pleiades kernel: [1749751.769022] ata2: link is slow to respond, please be patient (ready=0)
Sep  1 22:39:47 pleiades kernel: [1749756.767014] ata2: device not ready (errno=-16), forcing hardreset
Sep  1 22:39:47 pleiades kernel: [1749756.767023] ata2: soft resetting link
Sep  1 22:39:47 pleiades kernel: [1749764.011135] ata2.01: qc timeout (cmd 0xec)
Sep  1 22:39:47 pleiades kernel: [1749764.011140] ata2.01: failed to IDENTIFY (I/O error, err_mask=0x4)
Sep  1 22:39:47 pleiades kernel: [1749764.011144] ata2.01: revalidation failed (errno=-5)
Sep  1 22:39:47 pleiades kernel: [1749769.060013] ata2: link is slow to respond, please be patient (ready=0)
Sep  1 22:39:47 pleiades kernel: [1749774.058012] ata2: device not ready (errno=-16), forcing hardreset
Sep  1 22:39:47 pleiades kernel: [1749774.058019] ata2: soft resetting link
Sep  1 22:39:47 pleiades smartd[5643]: Device: /dev/sdc, failed to read SMART Attribute Data 
Sep  1 22:39:47 pleiades smartd[5643]: Device: /dev/sdc, Read SMART Self Test Log Failed 
Sep  1 22:39:47 pleiades kernel: [1749786.302021] ata2.01: qc timeout (cmd 0xec)
Sep  1 22:39:47 pleiades kernel: [1749786.302026] ata2.01: failed to IDENTIFY (I/O error, err_mask=0x4)
Sep  1 22:39:47 pleiades kernel: [1749786.302029] ata2.01: revalidation failed (errno=-5)
Sep  1 22:39:47 pleiades kernel: [1749791.351016] ata2: link is slow to respond, please be patient (ready=0)
Sep  1 22:39:47 pleiades kernel: [1749796.349013] ata2: device not ready (errno=-16), forcing hardreset
Sep  1 22:39:47 pleiades kernel: [1749796.349024] ata2: soft resetting link
Sep  1 22:39:47 pleiades kernel: [1749828.593026] ata2.01: qc timeout (cmd 0xec)
Sep  1 22:39:47 pleiades smartd[5643]: Device: /dev/sdc, Read Summary SMART Error Log failed 
Sep  1 22:39:47 pleiades kernel: [1749828.593035] ata2.01: failed to IDENTIFY (I/O error, err_mask=0x4)
Sep  1 22:39:47 pleiades kernel: [1749828.593039] ata2.01: revalidation failed (errno=-5)
Sep  1 22:39:47 pleiades kernel: [1749828.593042] ata2.01: disabled
Sep  1 22:39:47 pleiades kernel: [1749833.642016] ata2: link is slow to respond, please be patient (ready=0)
Sep  1 22:39:47 pleiades kernel: [1749838.640016] ata2: device not ready (errno=-16), forcing hardreset
Sep  1 22:39:47 pleiades kernel: [1749838.640028] ata2: soft resetting link
Sep  1 22:39:47 pleiades kernel: [1749840.841810] ata2: EH complete
Sep  1 22:39:47 pleiades kernel: [1749840.842031] end_request: I/O error, dev sdc, sector 15438448
Sep  1 22:39:47 pleiades kernel: [1749840.842036] md: super_written gets error=-5, uptodate=0
Sep  1 22:39:47 pleiades kernel: [1749840.842041] md/raid1:md2: Disk failure on sdc5, disabling device.
Sep  1 22:39:47 pleiades kernel: [1749840.842041] md/raid1:md2: Operation continuing on 2 devices.
Sep  1 22:39:47 pleiades kernel: [1749840.842206] sd 1:0:1:0: [sdc] Asking for cache data failed
Sep  1 22:39:47 pleiades kernel: [1749840.842213] sd 1:0:1:0: [sdc] Assuming drive cache: write through

— tandis que l'autre (un Western Digital Caviar Blue® WD10EALX-009BA0 de 1To, acheté en juin 2012, et nommé sdb ou ata1.01 dans les logs qui suivent) n'a pas tardé à se découvrir quantité de secteurs défectueux :

Sep  2 22:55:54 pleiades smartd[9342]: Device: /dev/sdb, FAILED SMART self-check. BACK UP DATA NOW! 
Sep  2 22:55:54 pleiades smartd[9342]: Device: /dev/sdb, SMART Prefailure Attribute: 3 Spin_Up_Time changed from 176 to 187 
Sep  2 22:55:54 pleiades smartd[9342]: Device: /dev/sdb, Failed SMART usage Attribute: 5 Reallocated_Sector_Ct. 
Sep  2 22:55:54 pleiades smartd[9342]: Device: /dev/sdb, SMART Prefailure Attribute: 5 Reallocated_Sector_Ct changed from 200 to 42 
Sep  2 22:55:54 pleiades smartd[9342]: Device: /dev/sdb, SMART Usage Attribute: 7 Seek_Error_Rate changed from 200 to 21 
Sep  2 22:55:54 pleiades smartd[9342]: Device: /dev/sdb, SMART Usage Attribute: 194 Temperature_Celsius changed from 107 to 108 
Sep  2 22:55:54 pleiades smartd[9342]: Device: /dev/sdb, SMART Usage Attribute: 196 Reallocated_Event_Count changed from 200 to 84 

(Qu'on se rassure, malgré le message trompeur, il n'était pas vraiment à 108°C : le 108 est une valeur normalisée SMART, qui pour ce fabricant semble correspondre à environ 40°C.) Ce disque a continué à plus ou moins fonctionner (mais lentement, en faisant des bruits bizarres, et de rares vraies erreurs), au moins le temps de me permettre d'en récupérer en catastrophe celles de mes données qui n'étaient protégées que contre l'échec d'un seul disque.

Je ne peux pas vraiment dire que je sois passé près de la catastrophe : en vérité, non seulement comme je viens de le dire le disque mourant a tenu le coup le temps que j'en extraie tout ce que je voulais extraire, mais de toute façon les données vraiment importantes étaient en redondance triple (RAID1 sur les trois disques), et même ces données étaient essentiellement des sauvegardes incrémentales de données qui sont en redondance au moins quintuple sur des ordinateurs à deux endroits physiquement séparés (sans compter des sauvegardes sur médias optiques) — bref, je suis passablement parano avec la perte d'information. Néanmoins, j'aurais pu perdre quelques choses qui m'auraient agacé, et beaucoup plus de temps que je n'en ai déjà passé à racheter des nouveaux disques et recopier tout ce que j'avais sur ceux-ci (ce qui, quand le disque dur mourant descend jusqu'à 3Mo/s et qu'on a 750Go à copier, prend… longtemps). J'ai donc augmenté ma paranoïa d'encore un cran et mis encore plus de partitions en redondance triple : après tout, ça ne sert à rien d'économiser vingt gigas par-ci par-là quand j'en ai des centaines dont je ne me sers pas vraiment.

Mais au-delà de cette non-catastrophe, la question demeure de savoir comment il se fait que deux disques durs aient pu mourir en même temps (et cette question a de l'importance, parce que si deux peuvent, alors trois peuvent aussi, et je ne serais vraiment vraiment pas content). J'avais déjà eu une expérience de ce genre qui s'était avérée n'être qu'une vapeur du contrôleur, mais cette fois les disques ont bien l'air d'être endomagés. Il n'y a pas eu d'orage à cette période qui expliquerait, par exemple, une surtension électrique. Je peux vaguement soupçonner soit une insuffisance de l'alimentation ou une chaleur excessive, mais aucune de ces hypothèses n'est corroborée par un indice tangible. Par ailleurs, les deux disques ont commencé à défaillir à presque exactement 24h d'intervalle, ce qui est peut-être significatif, mais je ne sais pas de quoi (il n'est rien censé se passer de particulier à ce moment-là).

J'ai racheté (à Hambourg) trois nouveaux disques durs, en essayant de trouver trois constructeurs différents, mais comme je le soupçonnais c'est une tâche impossible : je ne sais pas exactement combien existent de chaînes vraiment indépendantes de fabrication de disques durs, mais le nombre de marques semble être tombé à 2 (Seagate ayant, je crois, acquis Maxtor ; et Western Digital), comme par hasard ceux qui m'ont empiriquement posé le plus de problèmes par le passé (alors que Hitachi, Samsung et IBM, qui semblaient considérablement plus fiables, soient ne fabriquent plus de disques, soit au moins ont cessé de les revendre aux péquenots comme moi).

Je constate aussi de nouveau ce que j'avais déjà cru détecter, à savoir que (dans des mesures raisonnables) plus un disque dur est ancien, plus il est fiable : ce sont mes disques les plus récents qui ont lâché (pour référence, celui qui continuait à fonctionner était un Samsung SpinPoint® HD501LJ de 500Go, acheté en novembre 2007). Autrement dit, il me semble que sur un disque dur, le phénomène d'usure avec le temps est beaucoup moins important que le phénomène de défaut caché à la fabrication (appelé aussi mortalité infantile des disques durs) et que l'expérience permet de dévoiler : plus votre disque a tenu longtemps, plus il y a des chances qu'il soit de bonne qualité et continue à tenir longtemps. Il est vrai que les deux disques dont on parle étaient tous trop vieux pour vraiment entrer dans la case « mortalité infantile », donc c'est peut-être simplement une coïncidence.

Bien sûr, mes observations aussi bien sur la fiabilité relative des marques que sur la fiabilité avec le temps sont basées sur des données statistiquement insuffisantes, et même pas collectées de façon systématique. Ceux qui pourraient le mieux fournir des informations vraiment scientifiques sur la fiabilité des disques, c'est Google : malheureusement, une étude qu'ils ont publiée il y a quelque temps à ce sujet ne veut rien révéler sur les marques de disques durs plus ou moins fiables. À défaut, j'ai trouvé deux rapports de la compagnie de stockage Blackblaze, celle-ci sur la durée de vie des disques durs en général et celle-là sur les marques plus ou moins fiables, qui corroborent au moins partiellement mes impressions (les disques durs jeunes ont le plus tendance à mourir, le minimum du taux de mortalité se situant d'après eux vers 2 ans d'âge ; et Hitachi semble bien la marque la plus fiable — ou du moins semblait). Il faut néanmoins bien prendre note que les conditions d'utilisation (température, pourcentage du temps passé allumé, nombre de cycles de garage des têtes, etc.) peuvent changer du tout au tout les résultats de ce genre de mesures, donc on reste dans le domaine de la boule de cristal.

(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 ?

Mise à jour : On m'a donné quelques références répondant à cette question (voir le lien ci-dessus ainsi qu'ici sur MathOverflow), mais le plus important, en fait, est de connaître un mot-clé permettant de googler toutes sortes d'articles traitant de la question : si f(a+h) = f(a) + f1(ah + ⋯ + fn(ahn/n! + o(hn) (sans aucune hypothèse d'uniformité en a) alors on dit que le coefficient fk(a) (pour kn) de ce développement est la k-ième dérivée de Peano ou dérivée de de la Vallée-Poussin de f en a ; et entre autres théorèmes qui répondent à ma question, l'article The Exact Peano Derivative de H. William Oliver (Trans. Amer. Math. Soc. 76 (1954) 444–456) affirme entre autres que :

If fn(x) exists and is bounded above or below throughout [a,b], then fn(x) = f(n)(x), the ordinary n-th derivative, at every point x∈[a,b].

Il suffit donc de supposer que les coefficients du développement de Taylor varient de façon localement bornée pour avoir la conclusion que je voulais.

(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.

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.