Le blog-notes mathématique du coyote

Le lemme de Burnside... Outre le fait qu'il n'est pas dû à Burnside et qu'on peut le considérer autrement qu'un lemme, ce résultat obscur de la théorie des groupes permet de faire des choses hallucinantes ! Si si ! Il permet par exemple de compter le nombre de colliers que l'on peut faire avec 3 perles rouges, 3 perles bleues et 5 perles vertes. Il permet aussi de compter le nombre de colliers que l'on peut faire avec 6 perles jaunes, 3 perles bleues, une perle verte et une perle rouge.
Il permet en fait de répondre à n'importe quel problème de dénombrement avec des perles ! (et certains problèmes sans perle : combien y a-t-il de façons de partager un paquet de Vache qui rit (aux isométries près) entre 3 personnes, combien existe-t-il de sudokus réellement différents, etc.). Le lemme de Burnside est l'exemple typique de l'énoncé abstrait d'un domaine abstrait qui trouve des applications concrètes dans des domaines concrets (pour peu que l'on aime fabriquer des colliers).

Lire l'article sur Choux Romanesco, vache qui rit et intégrales curvilignes.

L'association "Sesamath Suisse Romande" a été créé en 2009 pour favoriser en Suisse Romande la diffusion des principes et des ressources existantes de sa "grande soeur" Sesamath (France). Elle a comme objectif de diffuser les principes et les ressources de Sesamath (France), mais aussi d'adapter et/ou produire des ressources pédagogiques spécifiquement adaptées aux plans d'études officiels romands de mathématique, puis de les mettre gratuitement et sous licence libre à disposition des enseignants, élèves et parents de toute la Romandie.

Le si réputé algorithme de génération de clés de chiffrement RSA ne laisse pas une part assez grande au hasard pour être totalement fiable. Des chercheurs viennent ainsi de démontrer qu’il offre au mieux une sécurité de 99,8 % et, au pire, une sécurité nulle.

L’algorithme utilisé pour générer des certificats X.509 ou encore des clés de chiffrement PHP n’est pas aussi sûr que l’on pouvait l’imaginer jusqu’ici. La découverte en a été faite par des chercheurs en cryptographie de l'EFFL et publiée dans un article Ron was wrong, Whit is right. Ceux-ci indiquent avoir procédé à une «vérification de l’état sanitaire de clés publiques trouvées sur Internet», avec pour objectif de «tester la validité de l’assertion selon laquelle un choix aléatoire différent est fait à chaque fois que des clés sont générées ». Une opération qui a échoué : «la vaste majorité des clés publiques fonctionne comme prévu» mais «deux modulos RSA pour mille n’offrent aucune sécurité ». Pourquoi ? Notamment parce qu’il y a des duplicatas, bien involontaires, certes, mais dont l’existence même pose problème.
Concrètement, les chercheurs aboutissent à la conclusion «qu’il y a plus de duplicatas» que ce que les études précédentes avaient pu laisser penser : «sur 6,4 millions de modulos RSA distincts, 71504 (1,1 %) apparaissent plus d’une fois, et même des milliers de fois pour certains.» Pire, ils assurent avoir trouvé 12934 modulos RSA n’offrant aucune sécurité : «les clés privées [correspondantes] sont accessibles à n’importe qui prendrait la peine de reproduire notre travail », assurent-ils. Et d’estimer ainsi que, au mieux, l’algorithme RSA 1024 bits offre une sécurité de 99,8 %. Pour ces chercheurs, le chiffrement basé sur un secret unique - et non pas sur un couple clé privé/clé publique - et sur l’algorithme Diffie-Hellman serait finalement plus sûr. Pour l’expert Bruce Schneier, c’est un «excellent travail» qu’on fait là les chercheurs. Mais pour lui, l’algorithme RSA ou le principe du chiffrement asymétrique ne sont pas remis en cause par cette étude : le problème vient «presque certainement du générateur de nombres aléatoires» utilisé pour la création de ces clés publiques. Et «cela ne devrait surprendre personne. L’un des points les plus difficiles de la cryptographie est la génération de nombres aléatoires ». Et d’ajouter que «la capacité à produire quelque chose d’aléatoire n’est pas une exigence fonctionnelle et à moins que vous ne la testiez spécifiquement - et que vous sachiez comment la tester - vous penserez probablement que votre système cryptographique fonctionne correctement ».
En fait, pour les chercheurs, c’est environ 0,003 % des clés RSA publiques qui est potentiellement vulnérable, « ce qui ne semble pas inacceptable ». Pour Bruce Schneier, il y a effectivement un risque mais il est difficile à quantifier. Et la nature aléatoire - encore - de la menace fait «qu’il est difficile de savoir comment monétiser» la faille. Ce qui tend à réduire la menace concrète. Toutefois, il s’interroge sur l’éventualité de générateurs de nombres aléatoires «volontairement affaiblis. Les suspects les plus évidents sont les services de renseignement nationaux comme la NSA. Je n’ai aucune preuve mais si je devais affaiblir des systèmes de chiffrement, je commencerais par les générateurs de nombres aléatoires.»

Source : lemagIT.fr

En théorie de la complexité, les preuves interactives permettent, via un jeu de questions et réponses, de certifier, avec une très forte probabilité, la véracité d’un énoncé. En voilà un exemple, où il est question des chaussettes d’un daltonien.

Lire l'article sur Images des mathématiques.

Programmation en Python pour les mathématiques
Alexandre Casamayou-Boucau, Guillaume Connan, Pascal Chauvin
Dunod (8 février 2012)
304 pages

Présentation de l'éditeur
Python est un langage de programmation libre, multi-plateforme, offrant des outils de haut niveau et une syntaxe simple. Il est particulièrement apprécié des pédagogues qui y trouvent un langage où la syntaxe, séparée des mécanismes de bas niveau, permet une initiation aisée aux concepts de base de la programmation. C'est le langage le plus répandu dans le monde scientifique. Cet ouvrage présente tout ce que le mathématicien doit savoir sur ce langage : comment se le procurer, comment l'installer, l'utiliser, quelles sont ses fonctionnalités proprement mathématiques et quels problèmes sont susceptibles d'être résolus grâce à lui. Didactique et simple d'approche, il aborde donc conjointement la programmation, l'algorithmique et les applications mathématiques. Sans chercher une exhaustivité impossible, il montre comment la flexibilité et la versatilité du langage Python en font un très bon choix pour une utilisation scientifique. Des programmes d'accompagnement sont disponibles en téléchargement sur le site dunod.com.

Les solutions sont ici

Sur le Wolfram Blog hier : une (longue) annonce pour Wolfram|Alpha Pro.

Et si les secrets de la réussite des géants du Web, les Google, Facebook, Twitter ou autres Amazon trouvaient leur origine au XVIIIe siècle à Königsberg, en Allemagne ? A cette époque un mathématicien, Leonhard Euler, donna en effet naissance à une discipline devenue pilier de ces sites Internet : la théorie des graphes. Le problème d'Euler était de parcourir les quatre quartiers de sa ville sans emprunter deux fois l'un des sept ponts les reliant. Soit, sur un dessin, le fameux graphe, quatre sommets (ou noeuds) reliés par sept arêtes (ou liens). Les problèmes des vedettes du Web sont conceptuellement semblables, mais à une tout autre échelle : des milliards de "quartiers" (les pages Web, les profils, les clients...) et des milliards de "ponts" (les liens html, les "amis", les achats... reliant tout ce beau monde). La question est d'inventer les outils permettant de trouver la bonne information dans cette nuée, d'identifier des noeuds capitaux pour la bonne tenue de l'ensemble, de regrouper les gens par affinité, ou de recommander de nouveaux produits aux acheteurs. En outre, contrairement à Königsberg, cette "ville" possède des quartiers et des ponts qui bougent, naissent ou meurent...
Il y a une dizaine d'années, une nouvelle science est donc apparue, pour décrire et comprendre ces graphes ou réseaux de grandes tailles qui grossissaient sans plan préétabli : le Web et ses réseaux sociaux (Facebook, LinkedIn, Twitter, Viadeo...). Les mathématiciens et informaticiens y ont vu un terrain de jeu stimulant pour pousser leurs théories et calculs dans leurs retranchements. "Il y a de quoi attirer de jeunes talents qui, auparavant, se lançaient dans la finance", constate Henri Verdier, président du pôle de compétitivité Cap Digital. Il a justement cofondé une entreprise, MFG Labs, avec deux mathématiciens.
Les physiciens s'y sont intéressés, armés de leurs outils statistiques qui permettent de passer du microscopique (l'agitation des atomes d'un gaz, par exemple) au macroscopique (comme la température de ce gaz). Même les sciences humaines s'y sont mises, car pour un sociologue les réseaux sociaux existaient bien avant le Web. Certains d'entre eux avaient déjà dessiné des graphes, à la main, pour décrire les interactions entre différents membres de communautés familiales, religieuses, sportives... "Le Web est à la fois l'objet de la recherche et le moyen de la recherche", constate Dominique Cardon, sociologue au laboratoire Sense d'Orange Labs. Le mouvement est lancé. Des bases de données d'articles scientifiques, comme PubMed, recensent déjà plus de 200 articles ayant comme sujet Facebook, une centaine concernant Twitter, comme si ces sites étaient des gènes ou des particules. Des conférences et des revues spécialisées se créent.
En France, l'Institut Télécom vient de lancer une chaire "réseaux sociaux", soutenue par Danone ou La Poste. Une seconde sur la question des "données numériques" suivra très bientôt. Autour du médialab de Sciences Po sera développé un instrument à trois "bras", DIME-SHS (Données, infrastructure, méthodes d'enquêtes en sciences humaines et sociales), pour faire passer les sciences humaines à l'ère du numérique.

Jungle foisonnante

Outre des technologies pour effectuer des sondages via des tablettes, il y aura une plate-forme archivant et donnant accès à des études de terrain précédentes. Enfin, un service permettra aux chercheurs de construire et d'analyser leurs propres corpus issus de l'exploration des multiples "traces" laissées par les internautes sur le Web : billets de blogs, tweetts, liens hypertextes postés, statistiques d'usages... "Nous avons beaucoup de demandes de chercheurs pour de tels outils, mais d'autres sont encore réticents, notamment car la méthodologie n'est pas encore mûre, explique Paul Girard, l'un des ingénieurs de ce futur équipement au médialab de Sciences Po. Le Web ne dit pas tout."
Cette mode est affublée de plusieurs noms : science du Web, science des réseaux, humanités numériques... Peu importe, à peine née, ses résultats intéressent les fournisseurs commerciaux de services Web. Comment trier l'information au plus vite ? Comment identifier des communautés d'intérêts dans la jungle foisonnante du Web ? Comment se diffusent des informations ou des produits sur ces réseaux ?...
D'autres acteurs aimeraient aussi avoir ces réponses. Le secteur de la sécurité et de la défense rêve de surveiller les activités suspectes et de les anticiper. Les sondeurs (et hommes politiques) guettent toute percée sur la mesure de l'"état de l'opinion" sans recourir aux sondages. Le marketing s'y plonge pour repérer les profils influents et élaborer des campagnes efficaces... Le vieux rêve (ou cauchemar) d'une prédiction du futur refait surface. Où en est-on vraiment ? Le succès le plus évident de l'application de la théorie des graphes au Web est à chercher du côté du moteur de recherche Google. Alors que, dans les années 1990, des sites hiérarchisent à la main les informations dans de gigantesques annuaires reposant sur le contenu des sites et des pages référencées, Sergey Brin et Larry Page, les fondateurs de Google, innovent à partir de 1995. Leur méthode recense seulement les liens hypertextes qui permettent de passer d'une page à l'autre et en tire un classement, selon le "vieux" principe académique qui veut que plus une page est citée (via ces liens), plus elle est pertinente. C'est donc la structure même du réseau qui sert à son classement. Pas son contenu. "Cette rupture a périmé en un rien de temps les autres techniques", rappelle Dominique Cardon, qui constate également que cette suprématie est en passe d'être chamboulée.
Plus modestement que Google, d'autres sociétés utilisent la force de la structure sur le contenu pour se repérer dans la jungle des sites Web. Par exemple Linkfluence : cette start-up, dont Le Monde est partenaire, réalise ainsi des cartes de la blogosphère francophone. Plus de 13 500 sites sont regroupés en trois "continents", eux-mêmes sous-divisés en vingt territoires, etc. Le tout en analysant les liens entre eux et en vérifiant a posteriori les contenus.
Cette quête de "communautés" est une branche toujours très active de la recherche en mathématique et informatique pour l'automatiser. La méthode la plus efficace a été inventée par l'université de Louvain, en 2008, et appliquée avec succès sur de très grands graphes, comme les échanges téléphoniques belges et français (Le Monde du 17 décembre 2011) ou Twitter, LinkedIn... En quelques minutes, la masse informe de noeuds "explose" et devient une galaxie plus lisible avec des agrégats bien séparés. Reste à étudier les évolutions dans le temps de ces réseaux et à tenir compte des multi-appartenances des noeuds. Car, les sociologues le savent bien, un individu peut avoir plusieurs "identités".

Les nains et les géants

Cette structuration des graphes en communautés est l'une des propriétés remarquables mises en évidence par les pionniers américains de la fin des années 1990, tels Duncan Watts, Albert-Laszlo Barabasi, Jon Kleinberg... Il existe, dans ces grands réseaux, des régions denses avec beaucoup de liens et de grands espaces sans lien. Ils ont aussi réalisé que ces réseaux, malgré leur nombre important de noeuds et de liens, sont en fait de petite taille. Autrement dit qu'en quelques sauts, de lien en lien, on peut parcourir n'importe quel point du graphe. Selon Albert-Laszlo Barabasi, le Web tout entier aurait même un diamètre inférieur à vingt.
Plus récemment, les chercheurs de Facebook ont trouvé que le diamètre du réseau social était inférieur à cinq. Attention, petit diamètre ne signifie pas que nous soyons tous "amis". "Ce résultat sur Facebook n'a ni sens ni implication sociologique. En effet, une propriété caractéristique de ces réseaux dits petits-mondes est que le nombre de liens (comme le nombre d'amis sur Facebook) est réparti de manière aussi inéquitable entre les noeuds du réseau que le capital au sein d'une population : être à quatre poignées de main d'une personne qui a 3 000 amis déclarés ne la rend pas plus abordable que se trouver le nez devant sa porte close, explique Christophe Prieur, du laboratoire d'algorithmique du CNRS et de l'université Paris Diderot. Dans un monde (hypothétique) où la personne la plus éloignée de vous serait à six pas, ce six signifie l'infini."
L'une des lois du Web est en effet que la richesse va à la richesse et que, grosso modo, 20 % des noeuds possèdent 80 % des liens. Cette loi statistique que l'économiste italien Vilfredo Pareto a exhibée pour la richesse s'applique aussi à ces graphes. Dans ce cas, les notions de moyenne n'ont pas de sens. La "richesse" ne se répartit pas comme les notes d'une classe ou les tailles des individus le long d'une courbe en cloche. Au pays du Web, les nains et les géants ne sont pas rares.

David Larousserie - Le Monde.fr - 3.2.2012

Gary McGuire, mathématicien irlandais, a résolu une énigme datant de plus de dix ans, en découvrant le plus petit sudoku qui existe. Pour cela, il a fallu plus de 7 millions d'heures de calculs sur un superordinateur.
Il n'existe que trois types de sudokus : ceux n'ont qu'une unique solution, ceux qui ont plusieurs solutions et ceux qui n'ont aucune solution. Les premiers sont intéressants, et les autres sont terriblement décevants et ne méritent pas le nom de sudoku (étymologiquement, "chiffre unique").
En général, moins un soduku possède de cases pré-remplies, plus sa complétion sera difficile. De tous les sudokus connus, les plus dépouillés ne comportent que 17 chiffres révélés. Peut-on trouver un sudoku à 16 chiffres ? La question a longtemps été ouverte, jusqu'au 1er janvier 2012. Gary McGuire et deux collaborateurs ont regardé attentivement les 6.7 milliers de milliards de milliards de grilles complètes existantes afin de voir s'il était possible de leur retirer plus de 64 chiffres sans les dénaturer. Leur conclusion : il n'existe pas de sudoku à 16 chiffres.

Pour en savoir plus, lire l'article Pendant ce temps, chez les Sudokus sur l'excellent blog "Choux Romanesco, vache qui rit et intégrales curvilignes".

Les hommes se comportent le mieux qu'ils peuvent lorsque des femmes séduisantes sont susceptibles de les regarder. Les femmes ne modifient pas leur comportement (en moyenne) quand des hommes les regardent par contre. On a réalisé deux expériences. La première a fait jouer 65 hommes et 65 femmes d'âge moyen de 21 ans à un jeu anonyme de coopération : ce jeu permet de faire un don d'argent à une groupe via un ordinateur. Le don est un acte altruiste : les autres joueurs en bénéficient tandis que le donneur ne reçoit rien en retour.
Les participants ne savaient pas quels étaient les autres personnes avec qui ils jouaient. Ils pouvaient être vus par deux personne, l'une du même sexe et l'autre du sexe opposé, et qui étaient des complices des chercheurs : un « beau gosse » et un joli brin de fille. On a ainsi remarqué que les hommes accroissaient leurs bonnes actions s'ils se sentent observés par le sexe opposé et les femmes pas du tout, quel que fut l'observateur.
La deuxième expérience a consisté à réaliser des groupes d'hommes. On leur demandait de faire un certain nombre de donations. Ces donations s'accroissaient lors d'une observation par une jolie femme : il y avait clairement une « compétition » de donations. Le chercheur Dr Iredale responsable de l'étude affirme que cette recherche montre que les bonnes actions s'accroissent lorsqu'il y a une opportunité de copulation (sic). L'altruisme masculin serait un peu la queue du paon dans notre espèce.

Sources : Sur-la-Toile, Science Daily

Intéressant article sur le Wolfram Blog concernant les différentes façons d'écrire 2012 (et d'autres années) à l'aide des nombres de 1 à 10.

Lire l'article

Une boutique en ligne proposant T-shirts, mugs et autres accessoires en relation avec les maths : www.humour-mathematiques.com

Une camionnette roule à 100 km/h. Sur la plateforme arrière, un canon propulse un ballon à 100 km/h dans la direction opposée à celle de la camionnette. Que se passe-t-il ? Réponse sur cette vidéo.

Jusqu’à il y a encore quelques années, on pensait qu’il était techniquement impossible de plier une feuille de papier plus de sept fois.
La barre avait été dépassée en 2002, lorsqu’une étudiante américaine avait pu plier 12 fois l’équivalent d’un rouleau de papier-toilette.
Record battu, puisque des étudiants en mathématiques de l’école St. Mark de Southborough, dans le Massachusetts, ont réussi à plier 13 fois un rouleau de papier-toilette, rapporte le site du New Scientist.

Contrairement à ce qu’on pourrait penser de prime abord, le pliage de papier est un sujet d’étude on ne peut plus sérieux. Comme l’épaisseur de la feuille double à chaque pliage, il faut établir une formule mathématique qui prend en compte la nature du papier, son épaisseur et sa longueur (entre autres).
Pour parvenir à leurs fins, les étudiants ont utilisé plusieurs rouleaux. Mis bout à bout, ils ont formé une bande de 1,2 kilomètre de long, étendue dans un couloir du Massachusetts Institute Of Technology (MIT).
Après beaucoup de patience et des heures d’effort, les étudiants ont plié le tout 13 fois. Un empilement de 1,5 mètre de long, 76 centimètres de haut et composé de 8192 couches de papier.

Source : LeMatin.ch

Une réflexion intéressante sur le système décimal dans la série "scènes de ménage" (cela débute après 2.20).

"La période d'un pendule est proportionnelle à la racine carrée de la longueur de la ligne suspendant le poids. Ce qui signifie que plus long est le pendule, plus lentement il se balance." Les étudiants de Cambridge ont construit un dispositif avec une série de 15 pendules alignés, chacun légèrement plus long que son voisin, les ont ensuite mis en mouvement et ont filmé le résultat.

Merci à Jean-Pol pour m'avoir signalé cette vidéo.