MATHÉMATIQUES
Un ordinateur pourra-t-il répondre à cette question ?

mathématiques - par Propos recueillis par Philippe Pajot dans mensuel n°449 daté février 2011 à la page 18 (632 mots) | Gratuit
Pour vérifier que des systèmes informatiques fonctionneront comme prévu, on ne peut pas tester leur nombre infini de configurations. Les informaticiens ont alors recours à la logique.

Pourquoi utilise-t-on la logique en informatique théorique ?

T.C. Il existe des questions auxquelles aucun ordinateur ne peut répondre, quelle que soit la manière dont il est programmé ou sa puissance. Partant de ce résultat fondamental, une partie de l'informatique théorique tente de déterminer quelles sont les questions que l'on peut résoudre, ce que l'on qualifie de décidable. La logique permet d'aborder ce problème. On se place dans un cadre d'un formalisme logique : un ensemble d'énoncés - des phrases mathématiques - qui peuvent être vrais ou non, et on cherche à programmer un ordinateur pour répondre aux énoncés.

Comment choisit-on ce formalisme logique ?

T.C. Il en existe beaucoup, élaborés dans le cadre d'autres questions mathématiques, mais la plupart de ces formalismes sont indécidables : aucun ordinateur ne peut dire si un énoncé donné du formalisme est vrai ou non. Cela oblige à utiliser des formalismes logiques assez simples. Je m'intéresse en particulier à la « logique monadique du second ordre », et ce qu'elle peut exprimer sur les suites de symboles par exemple des lettres, éventuellement de longueur infinie, ce que les informaticiens nomment des « mots », et possédant parfois des embranchements, les « arbres ».

Que peut-on montrer sur la logique monadique ?

T.C. Le résultat fondamental, établi en 1969, est que ce formalisme logique est décidable sur les mots et sur les arbres infinis. Cela signifie que, si on a un énoncé exprimé dans ce formalisme, un ordinateur est capable de dire s'il existe une séquence infinie de symboles pour laquelle l'énoncé est vrai. Par exemple, l'énoncé : un mot contient une infinité de lettres « a », une infinité de lettres « b », et entre deux lettres « a », il y a un nombre pair de lettres « b », est vrai sur le mot infini « abbabbabb »... De même, on saura dire s'il existe un arbre infini pour lequel un énoncé est vrai. Ce résultat a été démontré en établissant une équivalence entre logique et automates finis, des objets mathématiques conçus pour effectuer des calculs simples sur les mots ou sur les arbres. Il s'agit de machines abstraites dotées d'un nombre fini d'états. Un automate va commencer au début d'un mot, puis, lettre par lettre, va lire ce mot, son état évoluant à chaque étape. À la fin, l'automate répondra vrai ou faux. Sur les mots infinis, un automate pourra par exemple détecter l'apparition d'une infinité de lettres « a ». C'est en traduisant la logique monadique en automates équivalents que le résultat de décidabilité a été démontré.

Comment avez-vous étendu ce résultat ?

T.C. Ces questions sont à la frontière de ce qui est décidable. Ainsi, si on s'autorise une extension a priori mineure à la logique, on sort en général du domaine décidable : toute la théorie s'effondre. J'ai tenté d'étendre cette logique à un formalisme quantitatif. Au lieu de dire si un énoncé est vrai ou faux, ce formalisme permet de dire s'il est plus ou moins vrai. Cette logique permet de mesurer des choses, de compter. En montrant son équivalence avec de nouvelles formes d'automates, nous avons généralisé le résultat fondamental à cette nouvelle logique, sur les mots et sur les arbres les arbres finis pour l'instant [1] . Un aspect intéressant du cas des arbres finis est que sa démonstration utilise la théorie des jeux, une technique essentielle pour la démonstration du résultat de 1969 sur les arbres infinis voir encadré. Les jeux permettent de voir la vérité d'un énoncé logique comme un jeu au cours duquel l'un des joueurs va tenter de montrer que l'énoncé est vrai quand l'autre va essayer de le réfuter.

Par Propos recueillis par Philippe Pajot

DOCUMENT      larecherche.fr     LIEN

MATHÉMATIQUES
Une infinité de couples de nombres premiers « presque jumeaux »

mathématiques - par Philippe Pajot dans mensuel n°477 daté juillet 2013 à la page 18 (541 mots) | Gratuit
Vous avez démontré un théorème concernant les nombres premiers. Comment s'énonce-t-il ?

Yitang Zhang* Il s'agit d'un résultat sur la répartition des nombres premiers. J'ai en effet montré qu'il y a un ensemble infini de paires de nombres premiers dont l'écart est de moins de 70 millions [1]. C'est un cas particulier d'une conjecture proposée par Alphonse de Polignac en 1849 : pour tout nombre pair n, il y a une infinité de couples de nombres premiers dont la différence est égale à n. Le cas où n vaut 2 est nommé « conjecture des nombres premiers jumeaux », et bien des mathématiciens aimeraient la démontrer. Il y a encore du chemin pour passer d'un écart de 70 millions à un écart de 2, mais mon résultat est le premier sur les couples de nombres premiers qui ne dépend pas d'autres conjectures non encore démontrées.

Comment avez-vous abordé le problème ?

Y.Z. En 2006, un résultat de Daniel Goldston, de l'université d'État de San José, aux États-Unis, János Pintz, de l'institut Alfréd Rényi à Budapest en Hongrie, et Cem Yildirim, de l'université du Bosphore à Istanbul, en Turquie, a fait sensation dans le monde des théoriciens des nombres (il n'a été publié qu'en 2009 [2]). Ils ont notamment prouvé qu'il y a une infinité de paires de nombres premiers dont la différence est égale au plus à 16. Mais il y un hic : leur résultat n'est vrai que si la conjecture d'Elliott-Halberstam est vraie. Or cette conjecture, réputée très difficile, n'a pas été démontrée. Aiguillonné par cet article, j'ai passé trois ans à travailler sur leur méthode, tentant de me débarrasser de cette hypothèse gênante, mais sans succès.

Qu'est-ce qui vous a permis d'aboutir ?

Y.Z. La bonne idée m'est venue soudainement alors que je me reposais l'été dernier dans le jardin d'un ami, dans le Colorado. Le résultat de Daniel Goldston et de ses collègues utilisait une méthode de crible. Ce type de méthode permet de trouver parmi les entiers des listes de nombres premiers qui sont des candidats plausibles pour contenir des paires de premiers proches. Mais ils devaient aussi utiliser une fonction dont un paramètre, baptisé l'« exposant de répartition », mesure la vitesse à laquelle les nombres premiers commencent à présenter certaines irrégularités. Or ce paramètre est inconnu : c'est ce qui les a contraints à s'appuyer sur la conjecture non prouvée. À la place de leur méthode de crible, j'ai utilisé un crible modifié qui ne filtre pas tous les entiers. Même si ce crible est moins efficace, il donne la flexibilité suffisante pour se débarrasser de la fonction avec le paramètre inconnu. Le résultat est un écart entre nombres premiers consécutifs plus grand, mais sans recourir à une conjecture non prouvée !

Votre méthode peut-elle être améliorée ?

Y.Z. L'écart de 70 millions devrait être réductible sans trop de difficulté. J'avais besoin d'un nombre suffisamment grand pour qu'une condition dans ma preuve fonctionne. Peut-être pourrons-nous arriver à 16, comme Daniel Goldston et ses collègues. Peut-être moins. Difficile de faire une prédiction. Mon résultat était d'ailleurs assez inattendu (lire « La voie est ouverte », ci-dessus) J'ai eu la chance de trouver la bonne idée au bon moment. En science, la chose importante est de continuer à penser.

Par Philippe Pajot

DOCUMENT      larecherche.fr     LIEN

MATHÉMATIQUES
Géométrie sur des ensembles de points isolés

mathématiques - par Philippe Pajot dans mensuel n°474 daté mars 2013 à la page 18 (530 mots) | Gratuit
Qu'avez-vous montré sur les ensembles fractals discrets ?

D.E. Avec mon collègue Ben Lichtin, de l'université de Rochester, aux États-Unis, nous avons élaboré de nouveaux outils pour accéder de façon indirecte à la géométrie de ce type d'ensembles. Un objet fractal est tel que tout est semblable à une de ses parties. Le triangle de Sierpinski en est un exemple : on part d'un triangle équilatéral plein ; on le remplace par trois autres juxtaposés, dont le côté est deux fois plus petit ; on répète cette opération à l'infini. Cette propriété d'autosimilarité peut aussi concerner des ensembles discrets, c'est-à-dire constitués de points isolés. Le triangle de Pascal modulo 2 est un exemple élémentaire d'un tel ensemble : chaque point correspond à une valeur impaire du triangle de Pascal habituel (voir la figure). Bien qu'il ressemble au triangle de Sierpinski, ce triangle de Pascal modulo 2 est un objet fractal discret.

Comment sont apparus ces ensembles fractals discrets ?

D.E. Partons du développement en fraction continue d'un nombre. Par exemple √2 peut s'écrire comme une suite infinie de fractions où apparaît une périodicité (√2 = 1 + 1/(2 + 1/(2 + 1/(2+...)))). Au début du XXe siècle, des mathématiciens ont cherché à trouver l'équivalent de ces périodicités pour des nombres qui ne sont pas forcément la solution d'une équation algébrique de degré 2 à coefficients entiers (les nombres non quadratiques). La construction des premiers ensembles fractals discrets résulte de cette recherche.

Comment étudier ces objets ?

D.E. Nous avons utilisé des fonctions zêta associées naturellement à ces ensembles discrets. Ce sont des fonctions construites sur le modèle de la fonction historique, la fonction zêta de Riemann (ζ(s) est égale à la somme pour n variant de 1 à l'infini de ). Pour les ensembles fractals discrets, la somme porte sur les points de l'ensemble fractal discret, auquel est associé un groupe de transformations, et au dénominateur se trouve une norme (qui mesure la taille des points) compatible avec ces transformations. En soi, cela n'a rien de révolutionnaire, mais l'étude de ces fonctions zêta particulières était extrêmement délicate. Pour obtenir des informations géométriques sur ces objets, il faut en faire le prolongement analytique (lire « Des prolongements utiles », ci-dessus). Or en raison de la grande irrégularité de la disposition des points dans ces ensembles, les techniques classiques pour établir des prolongements analytiques ne fonctionnaient pas. Nous avons exploité l'autosimilarité de l'objet lui-même, c'est-à-dire les symétries qui pouvaient exister, pour trouver les prolongements analytiques des fonctions zêta associés à ces objets. Ensuite, nous avons étudié précisément les singularités de ces prolongements, les valeurs pour lesquelles la fonction n'est pas définie.

Qu'avez-vous trouvé sur ces objets ?

D.E. En géométrie classique, la fonction zêta permet via ses singularités d'obtenir toute une série d'informations géométriques sur les objets étudiés, comme la dimension, la courbure et ses dérivées, etc. Sur les ensembles fractals discrets, nous avons obtenu le pendant de ces caractéristiques géométriques en montrant notamment que la dimension fractale coïncide avec le premier pôle réel (la plus grande valeur pour laquelle le prolongement analytique s'annule). L'exploitation de l'information contenue dans les autres pôles devrait conduire à mieux comprendre l'archétype de l'ensemble fractal discret, baptisé voile d'Arnold.

Par Philippe Pajot

 DOCUMENT      larecherche.fr     LIEN

MATHÉMATIQUES
Retourner le hasard à son avantage

mathématiques - par Benoît Rittaud dans mensuel n°430 daté mai 2009 à la page 28 (515 mots) | Gratuit
Deux jeux de hasard désavantageux combinés peuvent donner un nouveau jeu qui, lui, est avantageux pour le joueur : c'est le « paradoxe de Parrondo ».

Au jeu de pile ou face, on gagne un euro chaque fois que la pièce tombe sur pile, et on en perd un chaque fois qu'elle tombe sur face. Si la pièce est équilibrée, à chaque lancer la pièce a une chance sur deux de tomber sur l'un ou l'autre des côtés. La probabilité p de gagner est donc de 1/2.

Mais si la pièce est déséquilibrée, la valeur de p est différente. Si p est plus grand que 1/2, le jeu est favorable au joueur, sinon, il lui est défavorable. On peut, bien sûr, modifier de diverses façons les règles du jeu.

Deux jeux défavorables étant donnés, peut-on les combiner pour en faire un jeu favorable ? En 1996, Juan Parrondo, de l'université de Madrid, a montré que oui en donnant un exemple explicite. Dans une prépublication [1] , Stewart Ethier, de l'université d'Utah, et Jiyeon Lee, de l'université Yeungnam, en Corée du Sud, viennent de préciser les caractéristiques probabilistes du jeu de Parrondo.

Pour jouer au jeu de Parrondo, il faut disposer de trois pièces dont les probabilités de tomber sur pile sont légèrement inférieures à, respectivement, 1/2, 1/10 et 3/4. Le « jeu A » consiste à jouer avec la première pièce, le « jeu B » consiste à jouer alternativement avec la seconde et la troisième, selon la règle suivante : on joue avec la seconde pièce si, et seulement si, le total des gains depuis le début du jeu total négatif en cas de pertes, et égal à 0 au départ est divisible par 3.

Un calcul permet de montrer que les jeux A et B sont tous deux défavorables au joueur : à long terme, en général, celui-ci est de plus en plus endetté. Le jeu de Parrondo consiste à prendre une quatrième pièce, équilibrée celle-là : chaque fois qu'elle tombe sur pile le joueur joue au jeu A, chaque fois qu'elle tombe sur face il joue au jeu B. Le paradoxe est que le jeu de Parrondo est favorable au joueur !

Ce paradoxe a initialement été introduit en physique, dans le cadre de l'étude du « mouvement brownien à cliquet » : un mouvement désordonné d'une particule qui, à certains intervalles de temps aléatoires, est contrainte dans ses mouvements.

Il existe diverses variantes du paradoxe, Stewart Ethier et Jiyeon Lee se sont intéressés à certaines d'entre elles, pour lesquelles ils ont démontré un « théorème limite central », c'est-à-dire une description explicite de la loi de probabilité du gain du joueur à long terme qui permet de quantifier les chances que la fortune du joueur au temps n se trouve dans un intervalle donné. Celle-ci implique la fameuse « courbe en cloche », ou courbe de Gauss, fondamentale en théorie des probabilités. La méthode employée consiste à montrer que le jeu de Parrondo fait partie d'une classe de situations probabilistes dans lesquelles on sait déjà comment s'opère le lien avec la courbe en cloche.

Par Benoît Rittaud

DOCUMENT       larecherche.fr       LIEN