Mathématiques discrètes, combinatoire arithmétique et codes (MAT 562)

En bref

Résumé |  Calendrier |  Approfondissements | Organisation |  Bibliographie | Commentaires et Liens Utiles

Résumé

Le but de ce cours est de développer les résultats fondamentaux de la combinatoire arithmétique, et de montrer l'interaction entre cette discipline très à la mode et l'informatique théorique.

Les méthodes de la combinatoire arithmétique sont très souvent utilisées pour s'attaquer aux problèmes en théorie des nombres. Par exemple, elles ont joué un rôle crucial dans la preuve du célèbre théorème de Green et Tao, qui ont démontré il y a quelques années que les nombres premiers contiennent des progressions arithmétiques de toute longueur.

En informatique, ces techniques ont trouvé de nombreuses applications, par exemple dans le contexte des testeurs de propriété, utilisés pour décider efficacement si un objet donné possède une propriété fixée, ou des générateurs pseudo-aléatoires, indispensables pour assurer la sécurité des transferts d'information au quotidien. Outre des méthodes combinatoires, nous utilisons quelques inégalités provenants des probabilité ainsi que la transformation de Fourier discrète, mais dans un contexte fini où les problèmes de convergence disparaissent.

La plupart des résultats présentés dans ce cours remontent à peine à quelques années, d'où l'avantage de pouvoir entrer de plain-pied dans certaines des recherches les plus pointues du domaine.

Parmi les sujets abordés on trouvera:

• lemmes de regularité et suppression, ensembles et graphes
• étude de la structure des ensembles sommes, cas particulier du théorème de Freiman
• analyse de Fourier d'ordre supérieur, notamment le théorème inverse quadratique
• applications en informatique, par exemple testeurs de propriété
• générateurs pseudo-aléatoires et le théorème de Goldreich-Levin
• amplification de difficulté en utilisant des codes correcteurs

Prérequis: notions très élémentaires d'algèbre linéaire, de probabilité et de transformation de Fourier

N'hesitez pas à me contacter à l'adresse mail suivante julia.wolf at math.polytechnique.fr au cas ou vous auriez des questions sur ce cours.

Retour en haut de page

Calendrier

Le cours n'aura pas lieu le 24 fevrier 2012.

Retour en haut de page

Approfondissements

Les thèmes d'approfondissement peuvent donner lieu à des développements aussi bien de nature théorique que plus tournés vers la programmation.

• Les meilleures bornes inférieures et supérieures pour les lemmes de suppression, qui sont très récentes mais tout à fait abordables.
• Le théorème de Freiman dans un groupe abélien, résultat central en combinatoire additive qui nous renseigne sur la structure de tout ensemble dont l'ensemble somme est petit.
• Les sous-groupes approximatifs dans les groupes cycliques d'ordre premier, qui jouent un rôle important dans le transfert des méthodes combinatoires, développées dans ce cours pour un espace vectoriel de dimension finie, au cas général des groupes abéliens.
• Le théorème de Roth, qui donne une borne supérieure pour la densité d'un ensemble ne contenant pas de progression arithmétique de longeur 3.
• La dérandomisation d'algorithmes aléatoires, en particulier la construction de Nisan et Wigderson, résultat récent et étonnant en informatique qui permet de transformer les algorithmes aléatoires sous forme déterministe.

Retour en haut de page

Organisation

Votre note finale se compose du contrôle ecrit (70 pour cent), votre participation en cours et en PC (25 pour cent), ainsi que les corrections que vous apportez aux notes de cours (5 pour cent).

Le contrôle aura lieu le vendredi 16 mars 2012, 13:30h-16:30h. Seul le polycopié annoté sera autorisé. Il y aura une tâche de rédaction, et on insistera moins sur les deux derniers amphis du cours. Je serai disponible le mardi 13 mars 2012, 15h-17h pour répondre à vos questions.

Les corrections des notes de cours sont à rendre le mardi 28 février 2012. Une enveloppe est disponible à cet effet sur la porte de mon bureau au CMLS. Un poly imprimé sera mis à votre disposition pour le début mars.

Les oraux pour les projets d'approfondissement auront probablement lieu le jeudi 29 mars 2012. Le mémoire est à rendre impérativement avant cette date.

Retour en haut de page

Bibliographie

Pour se faire une idée générale de ce domaine de recherche, consultez ma page A Personal Roadmap (en anglais).

Retour en haut de page

Commentaires et Liens Utiles

* The concentration inequalities on Tao's blog are useful, for example, for Exercise 1.8. You can also consult [TV] above for a condensed treatment.

* For a conjecture as to the best bounds in Freiman's theorem, see section 10 of [Gr1] above.

* A note on an elliptic curves approach to showing that there are no four squares in arithmetic progressionby K. Conrad.

Retour en haut de page