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


En bref

Codes

A partir du: 6 janvier 2012
Niveau: Master 1 en MAT (pourrait intéresser aussi aux élèves en MAP/INF)
Cours: vendredi 13:30h-15:30h, PC 23
Petites Classes: vendredi 15:45h-17:15h, PC 23
Option EA: inscrivez-vous au 581 (EA en maths) et signalez votre choix (562) dans votre lettre de motivation
Liens utiles: information du département
 

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

Date ContenuA préparer pour la séance suivante
Amphi 1 analyse de Fourier linéaire et applications en théorie des nombres (théorèmes de Meshulam, Roth et construction de Behrend)1.8, 1.26, 1.36
Amphi 2 structure des ensembles dont l'ensemble somme est petit (inégalité de Pluennecke, théorème de Freiman)1.40*, 2.3, 2.15, 2.23
Amphi 3 energie additive d'un ensemble (lemme de Bogolyubov, théorème de Balog-Szemerédi-Gowers)2.25, 2.28, 2.33*, 2.34
Amphi 4 introduction à l'analyse de Fourier d'ordre supérieur (normes d'uniformité, énoncé du théorème inverse pour U^3) 3.17, 3.30, relire la preuve de la Prop. 3.24
Amphi 5 démonstration du théorème inverse pour U^3, et application (théorème de Szemerédi pour les progressions de longueur 4)3.42, relire la preuve de la Prop. 3.38
Amphi 6 structure des graphes (lemme de régularité, lemme de suppression de triangles)
Amphi 7 applications en informatique théorique: testeurs de propriété5.18, lire la preuve du Th. 5.8
Amphi 8 informatique théorique: amplification de difficulté (théorème de Impagliazzo, lemme de Yao)6.24, 6.29, lire la preuve du Th. 6.23 et de la Prop. 6.26
Amphi 9 informatique théorique: générateurs pseudo-aléatoires (théorème de Goldreich-Levin)

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é. J'insisterai 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).

[BTW] B. Barak, L. Trevisan, A. Wigderson, Lecture notes on "Additive Combinatorics and Computer Science", 2007.website
[Gr1] B.J. Green, Finite fields models in additive combinatorics, 2005.pdf
[Gr2] B.J. Green, Montreal lecture notes on "Quadratic Fourier analysis", 2006.pdf
[N] M.B. Nathanson, Additive Number Theory: Inverse problems and the geometry of sumsets , Springer Graduate Texts in Mathematics, 1996.
[S] T. Sanders, Lecture notes on "Analysis of Boolean functions", 2010.pdf
[O'D] R. O'Donnell, Lecture notes on "Boolean analysis", 2007.pdf
[TV] T. Tao and V. Vu, Additive Combinatorics, Cambridge Univ. Press, 2006.
[Vi] E. Viola, Selected results in additive combinatorics: an exposition for computer scientists, 2007.pdf

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.

* Learn about Impagliazzo's intriguing Five Worlds of Average-Case Complexity.

Retour en haut de page

Mise à jour le 3 mars 2012.