Ok

En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Ces derniers assurent le bon fonctionnement de nos services. En savoir plus.

La Recherche

  • Une méthode plus rapide pour multiplier de très grands nombres

    La multiplication des nombres entiers est un problème qui occupe les mathématiciens depuis l'Antiquité. La méthode « babylonienne », que l'on apprend à l'école, revient à multiplier chaque chiffre du premier nombre avec chaque chiffre du deuxième nombre. Pour deux nombres d'un milliard de chiffres chacun, cela nécessite un milliard de milliards d’opérations, ou une trentaine d'années pour un ordinateur qui effectue un milliard d'opérations par seconde. En 1971, les mathématiciens Schönhage et Strassen ont inventé une méthode plus rapide, permettant de réduire le temps de calcul à une trentaine de secondes sur un ordinateur portable d'aujourd'hui. Dans le même travail, ils présageaient l'existence d'un algorithme encore plus rapide. Dans un nouvel article, à disposition de la communauté scientifique sur la plateforme HAL, Joris van der Hoeven, chercheur du CNRS au Laboratoire d'informatique de l'École polytechnique (CNRS/École polytechnique) et David Harvey de l’Université de Nouvelle-Galles du Sud (Australie) viennent de relever le défi en trouvant une nouvelle méthode permettant de multiplier plus vite de grands nombres entiers. Un dernier problème soulevé par Schönhage et Strassen reste ouvert : démontrer qu’il est impossible de faire encore plus rapide. Un nouveau défi pour l’informatique théorique !  

    Bibliographie

    Integer multiplication in time O(n log n). David Harvey, Joris van der Hoeven.
    Disponible sur HAL : https://hal.archives-ouvertes.fr/hal-02070778  

  • Vincent Lafforgue lauréat du prix Breakthrough de mathématiques

    Vincent Lafforgue, actuellement directeur de recherche CNRS à l’Institut Fourier (CNRS/Université Grenoble Alpes), est lauréat du prix Breakthrough 2019 dans la catégorie des mathématiques. Recruté au CNRS en 1999, lauréat d’une médaille d’argent du CNRS en 2015, il est aujourd’hui distingué pour son parcours de mathématicien et plus particulièrement pour ses recherches sur le programme de Langlands. 

    Le prix Breakthrough a été créé en 2012 par des entrepreneurs de la Silicon Valley pour célébrer la recherche scientifique en mathématiques, physique fondamentale et sciences de la vie. C’est la cinquième fois qu’un prix Breakthrough est décerné à un Français.

     

     www.cnrs.fr/fr/cnrsinfo/vincent-lafforgue-laureat-du-prix-breakthrough-2019-de-mathematiques

  • Les abeilles comprennent le concept de zéro

    Les abeilles sont capables de se représenter et d'interpréter le zéro. C'est ce que viennent de démontrer une chercheuse du Centre de recherches sur la cognition animale (CNRS/Université Toulouse III – Paul Sabatier) et ses collègues australiens, prouvant pour la première fois que des insectes sont capables d'abstraction mathématique. Le zéro, qui symbolise le rien, le neutre ou l'absence, étant une construction humaine relativement récente, ces résultats, publiés dans Science le 8 juin 2018, interrogent l'importance symbolique du zéro dans l'histoire des mathématiques.

    Il avait déjà été démontré que certains vertébrés maîtrisaient des concepts numériques complexes, notamment l'addition ou la notion de zéro, mais rien n'avait été prouvé chez les insectes. Les abeilles sachant compter au moins jusqu'à 5, les chercheurs les ont formées au concept de « plus grand que » et « plus petit que ».

    Ils ont d'abord appris aux abeilles à venir boire de l'eau sucrée sur un dispositif expérimental associant une plateforme à une image. La règle est simple : « Choisis l'image où il y a le moins d'éléments ». La bonne réponse apporte de l'eau sucrée tandis que la mauvaise confronte les abeilles à une solution amère de quinine. Une fois que les abeilles ont intégré le principe du jeu, les chercheurs leur proposent une image vide et une image avec plusieurs points. En choisissant l'image vide comme étant celle comportant le moins d'éléments, les abeilles ont montré qu'elles étaient capables d'extrapoler en considérant que le zéro est inférieur à 5, 4, 3, 2 ou 1.

    Les abeilles n'ont qu'un million de neurones soit 100 000 fois moins que l'Homme, et pourtant tous deux sont capables d'utiliser le zéro. Invention majeure de l'humanité pour les mathématiques, la notion de zéro est particulièrement abstraite. Elle permet de représenter l'absence d'objet en inventant un nombre pour « le rien » tout en considérant qu'il est une quantité. Le cerveau, qui a évolué pour traiter des stimuli sensoriels, peut aussi concevoir l'absence de stimulus comme un objet concret. Cette découverte interroge l'importance symbolique du zéro, en suggérant une utilité de ce nombre pour un insecte pollinisateur.

    unnamed.jpg

    Après avoir appris que les images contenant le moins d'éléments sont associés à une récompense, les abeilles ont choisi l'image vide. L'expérience démontre qu'un ensemble vide, le zéro, est considéré par ces insectes comme un nombre inférieur aux autres.

    © Scarlett Howard/Aurore Avarguès-Weber

  • Il n'existe que 15 pavages pentagonaux possibles

    Recouvrir une surface plane avec un motif unique est un problème mathématique qui intéresse l'Homme depuis l'Antiquité, notamment pour la qualité esthétique des pavages, comme les mosaïques et les carrelages. L'un des problèmes encore ouvert dans ce domaine, qui questionne la communauté scientifique depuis 1918, est aujourd'hui définitivement clos grâce à Michaël Rao du Laboratoire d'informatique du parallélisme (CNRS/Inria/ENS de Lyon/Université Claude Bernard Lyon 1) : en utilisant des outils informatiques, il a démontré que pour des motifs à cinq côtés, seules 15 formes sont possibles pour recouvrir une surface plane. Ces travaux sont aujourd'hui disponibles sur le site Arxiv.org.

    Pour recouvrir un sol avec une seule et même forme, il existe de nombreuses solutions : triangles, carrés, rectangles, hexagones, etc. La recherche exhaustive de toutes les formes convexes pouvant paver un plan, c'est-à-dire une forme avec des angles inférieurs à 180° et qui permettent de recouvrir tout un mur sans chevauchement, fut initiée par Karl Reinhardt durant sa thèse en 1918. Il a montré que tous les triangles et quadrilatères pavent le plan, qu'il n'existe que 3 types d'hexagones qui permettent de réaliser un pavage et qu'un polygone à sept côtés ou plus ne permet pas de recouvrir un plan. Seule la question des pentagones restait ouverte. 

    De 1918 à 2015, 15 types de pentagones ont été découverts, lors de recherches plutôt singulières : initiée par Reinhardt en 1918, elle a subi plusieurs rebondissements, comme des nouvelles découvertes de mathématiciens amateurs, jusqu'à l'annonce médiatisée, en 2015, d'une nouvelle et 15e forme, 30 ans après la 14e, sans que la communauté scientifique ne parvienne à déterminer s'il existait encore d'autres formes de pentagones possibles pour paver un plan.

    Michaël Rao, chercheur du CNRS au Laboratoire d'informatique du parallélisme (CNRS/Inria/ENS Lyon/Université Claude Bernard Lyon 1) a aujourd'hui définitivement montré qu'il n'existe qu'un ensemble fini de familles1 de pentagones à considérer. En générant toutes les possibilités via un programme informatique2, Michaël Rao a montré que 371 familles de pentagones pouvaient potentiellement recouvrir un plan. Il a ensuite testé chacune de ces familles, à l'aide d'un autre programme informatique, et a montré que seuls 19 types de pentagones satisfaisaient les conditions nécessaires, à la fois pour les angles et la longueur des côtés, pour paver un plan. Parmi ces 19 types, 15 correspondent à des types déjà connus, et les quatre autres s'avèrent être des cas particuliers de ces 15 types. Seuls 15 types de tuiles sont donc possibles pour un recouvrir une surface plane.

    Avec sa méthodologie, Michael Rao clôt ainsi un problème vieux d'un siècle, mais pas seulement. Toutes les tuiles convexes pavent le plan de façon périodique (c'est-à-dire que le pavage se répète à l'infini). On ne sait pas encore s'il existe une tuile qui permet de réaliser un pavage non-périodique. Or, la plupart des techniques utilisées ici peuvent également être utilisées dans le cas des polygones non convexes et pourraient donc servir de base à la résolution de cet autre problème encore ouvert dans le domaine des pavages, plus connu sous le nom d' « Einstein Problem » (de l'allemand « ein stein »).

    Les 15 types de pavages pentagonaux et leurs 4 types particuliers.

    © Michaël Rao, Laboratoire d'informatique du parallélisme (CNRS/Inria/ENS de Lyon/Université Claude Bernard Lyon 1).

    1 Une "famille" est un ensemble de conditions portant uniquement sur les angles du pentagone. 
    2 L'exhaustivité de cette liste a également été revérifiée, de manière indépendante, par Thomas Hales qui a notamment prouvé la conjecture de Kepler par ordinateur.

    Exhaustive search of convex pentagons which tile the plane. Michaël Rao, disponible sur Arxiv.org, arXiv:1708.00274 (https://arxiv.org/abs/1708.00274)

    Deux, deux minutes pour classer les pavages

     

  • Faire entrer la terre dans une balle de ping-pong: une transformation "lisse et fractale"

    unnamed.jpg

    Un globe terrestre isométrique

    vignette_reverseColor_globalView2.png

    vignette_072_04.png

    vignette_rover6_fond3.png

    Capture.JPG

    Crédits des images et vidéos : E. Bartzos, V. Borrelli, R. Denis, F. Lazarus, D. Rohmer, B. Thibert

     

    Dans les années 1950, Nicolas Kuiper et le prix Nobel John Nash ont démontré l’existence d’une vaste classe d’objets mathématiques paradoxaux tels que des tores plats en 3D ou des sphères réduites, sans pouvoir toutefois les visualiser. Une équipe de mathématiciens et d’informaticiens du CNRS, de l’Université Grenoble Alpes et de l’Université Claude Bernard Lyon 11, a réussi à construire et représenter visuellement une sphère réduite, cinq ans après avoir obtenu la première image d’un tore plat en 3D2. Les sphères, connues pour être rigides, ne peuvent pas être déformées isométriquement3, c'est à dire en préservant les longueurs des courbes, avec une régularité de classe C2. En se basant sur la théorie mathématique de l’intégration convexe4, les chercheurs sont parvenus à placer une sphère à l'intérieur d'une boule de rayon arbitrairement petit. Si l'on assimile la surface de la Terre à une sphère ronde, cette théorie permet de réduire son diamètre à celui d'un modèle réduit de globe terrestre ou d'une balle ping-pong tout en préservant les distances géodésiques5. La surface obtenue, très déformée, se compose de deux calottes sphériques, parfaitement lisses, connectées par une bande équatoriale fortement déformée. Les chercheurs montrent que ce changement de structure géométrique est similaire à celui observé lorsqu'on relie une courbe de von Koch à un segment de droite (voir figure 3). Ces résultats ouvrent des perspectives inédites en mathématiques appliquées, notamment pour la résolution de certaines équations aux dérivées partielles. Les étonnantes propriétés des fractales lisses pourraient également jouer un rôle central dans l'analyse de la géométrie des formes. Leurs résultats ont été publiés dans la revue Foundations of Computational Mathematics, le 6 juillet 2017.

    Lire la suite