Mini-cours
Tresses et cryptologie

Marc Girault est expert émérite à France Télécom, et Hervé Sibert doctorant au SDAD (Structures Discrètes et Analyse Diophantienne, CNRS et université de Caen).

Résumé. Il a été proposé récemment de fonder des systèmes cryptographiques sur les groupes de tresses, où le problème de conjugaison est difficile mais où existent de bons algorithmes pour le problème du mot. Le mini-cours Tresses et cryptologie donnera une introduction à ces questions, en présentant les différents problèmes cryptographiques considérés (chiffrement, authentification, signature), les solutions proposées en termes de tresses, ainsi que le type d'arguments utilisés dans l'analyse de sécurité ou l'attaque de tels systèmes cryptographiques.

Braids and cryptology: abstract. Cryptosystems based on braid groups were described in the recent years. They rely on the observation that the conjugacy problem in braid groups is difficult, while the word problem is easy. The minicourse will give an introduction to this area of research; it will include a description of the various considered problems (encryption, authentication, signature), a description of possible braid based solutions, as well as a survey of the arguments used in the cryptanalysis or the attack of such systems.

Mini-cours
Polynômes de Schubert et équation de Yang-Baxter

Alain Lascoux est directeur de recherche au CNRS, et membre de l'institut Gaspard Monge (CNRS et université de Marne la Vallée).

Résumé. Il y a de nombreuses manières de définir les polynômes de Schubert. Je donnerai trois approches différentes:

  1. Les polynômes de Schubert sont une base de l'anneau des polynômes en une infinité de variables x1, x2, etc. avec pour coefficients d'autres variables y1, y2, etc. Ils peuvent être caractérisés par des conditions d'annulation très simples, et, à ce titre, sont les coefficients universels dans la version discrète de la formule de Taylor, où l'on remplace les dérivées par les différences divisées. Un cas particulier en est la formule d'interpolation de Newton pour les fonctions d'une seule variable x.
  2. Les polynômes de Schubert correspondant aux permutations dans Sn sont une base de l'anneau de cohomologie de la variété de drapeaux sous le groupe linéaire GL ( Cn ). L'énoncé purement algébrique est qu'ils sont une base de l'anneau des polynômes en x1, ... , xn en tant que module libre sur l'anneau des polynômes symétriques en x1, ... , xn. Les techniques de calcul dans ce module étendent celles des fonctions symétriques. En fait les fonctions symétriques fontamentales que sont les fonctions de Schur se retrouvent comme cas particuliers de polynômes de Schubert.
  3. Les relations de Yang-Baxter fournissent une troisième approche, plus directement liée aux groupes de Coxeter. On a à développer des expressions du type

    ( 1 + ( x1 - x2 ) s1 ) ( 1 + ( x1 - x3 ) s2 ) ( 1 + ( x2 - x3 ) s1 )

    ( s1 , s2 transpositions simples consécutives). Les coefficients que l'on trouve peuvent être interprétés comme ceux d'un changement de base, entre la base de Yang-Baxter de l'algèbre du groupe symétrique, et celle des permutations, mais sont aussi les images des polynômes de Schubert lorsque l'on spécialise les xi en une permutation des yj.

Schubert polynomials and Yang-Baxter equation: abstract. There are several ways of defining Schubert polynomials. I shall give three different approaches.

  1. Schubert polynomials are a linear basis of the ring of polynomials in x1, x2, etc. with coefficients depending on other variables y1, y2, etc. They can be characterized by simple vanishing conditions, and occur as universal coefficients in the discrete version of Taylor formula, where divided differences replace derivatives. The case of functions of a single variable x1 coincides with the Newton interpolation formula.
  2. The Schubert polynomials corresponding to permutations in the symmetric group Sn are a basis of the cohomology ring of the flag variety. Algebraically speaking, they are a basis of the ring of polynomials in x1, ... , xn, as a module over the symmetric polynomials. Such an interpretation extends much of the combinatorics of symmetric functions. In particular, Schur functions occur as special Schubert polynomials.
  3. Yang-Baxter relations give a third approach, more directly related to Coxeter groups. Following Yang, one has to expand expressions of the type

    ( 1 + ( x1 - x2 ) s1 ) ( 1 + ( x1 - x3 ) s2 ) ( 1 + ( x2 - x3 ) s1 )

    ( s1 , s2 being simple consecutive transpositions). Coefficients can be intrepreted as describing the Yang-Baxter basis of the group algebra of the symmetric group (or as R-matrices), but they will be obtained by specializing the yi's to a permutation of the xi's in the Schubert polynomials.

Mini-cours
Tresses et cactus

Alexandre Zvonkine est professeur au LaBRI (Laboratoire Bordelais de Recherche Informatique, CNRS et université Bordeaux 1).

Le mini-cours Tresses et cactus porte sur la classification topologique des polynômes.

Braids and cacti: abstract. The study of the topological classification of complex polynomials began in the 19-th century with Lüroth (1871), Clebsch (1873) and Hurwitz (1891). The problem is equivalent to the study of an action of the braid group on sequences of permutations that generate the monodromy groups of polynomials. By a combination of combinatorial, algorithmic and group-theoretic techniques we achieved a complete classification of the polynomials up to degree 11. These new data change entirely the global view of the problem and permit to formulate some plausible conjectures that may eventually lead to a solution of the problem.