Dans les années récentes un domaine très riche et dynamique a évolué à l'interface entre la théorie des nombres, la combinatoire et l'informatique théorique. Du côté théorie des nombres, le résultat le plus connu est le théorème de Green et Tao, qui ont démontré il y a quelques années que l'ensemble des nombres premiers contient des progressions arithmétiques de toute longueur. Il est peut-être moins connu que les méthodes utilisées dans cette preuve ont des applications profondes en informatique théorique, notamment en théorie de complexité et d'algorithmes ainsi qu'en cryptographie.

Bien que ces méthodes sont plutôt analytiques, un nouveau courant algébrique s'est fait jour récemment, concernant l'étude de la structure des "sous-groupes approchés" dans un contexte non-abélien. Les analogues abéliens de cette question, indispensables pour le développement des méthodes analytiques mentionnées ci-dessus, ont fait l'objet de nombreux travaux depuis les années 70, même si les aspects quantitatifs restent ouverts à ce jour.

Le cours MAT562 est fortement recommandé à ceux qui s'intéressent à ce stage (mais il n'est pas obligatoire).

Voici une liste des sujets proposés :

théorie additive des nombres : bases des entiers etc.

théorie analytique des nombres : structures arithmétiques dans l'ensemble des nombres premiers, et leurs asymptotiques

aspects ergodique de la théorie des nombres : démonstration du théorème de Szemerédi par Furstenberg, étude des facteurs caractéristiques

combinatoire additive : structure des ensembles dont l'ensemble somme est petit

méthodes analytiques en combinatoire : théorème de Roth et variations, structure du spectre d'une fonction

méthodes algébriques en combinatoire: familles de parties, fonctions génératrices

théorie des groupes approchés : théorèmes de Freiman non-abéliens

théorie de compexité : amplification de difficulté etc.

algorithmes : testeurs de proprietés pour les graphes et fonctions etc.

cryptographie : générateurs pseudo-aléatoires etc.

Dernière mise à jour : mardi 2 octobre 2012