Patrick Dehornoy

Patrick Dehornoy

Articles de synthèse, notes de cours / Survey articles, lecture notes

From newer to older; research papers are on a different page.
Laver's results and low-dimensional topology, arXiv 1401.3302, Archive for Math. Logic, to appear (32 pages), pdf file

(MSC 57M25, 03E55, 03F30, 06F15, 20F10, 20F36) In connection with his interest in selfdistributive algebra, Richard Laver established two deep results with potential applications in low-dimensional topology, namely the existence of what is now known as the Laver tables and the well-foundedness of the standard ordering of positive braids. Here we present these results and discuss the way they could be used in topological applications.


The subword reversing method, Intern. J. Alg. Comput. 21 (2011) 71-118, pdf file

(MSC 20B30, 20F55, 20F36) We summarize the main known results involving subword reversing, a method of semigroup theory for constructing van Kampen diagrams by referring to a preferred direction. In good cases, the method provides a powerful tool for investigating presented (semi)groups. In particular, it leads to cancellativity and embeddability criteria for monoids and to efficient solutions for the word problem of monoids and groups of fractions. The text includes some new results about mixed reversing (combination of left- and right-reversings) and about the combinatorial distance of braids.


Braid Order, Sets, and Knots, Proceedings ICTP Conference on Knots, May 2009, pdf file

We survey two of the many aspects of the standard braid order, namely its set theoretical roots, and the known connections with knot theory, including results by Netsvetaev, Malyutin, and Ito, and very recent work in progress by Fromentin and Gebhardt.


Cantor et les infinis, Conférence "Un texte, un mathématicien", BnF (Paris, 18 mars 2009), Version longue : Gazette des mathématiciens, 121 (2009) 29-46, fichier pdf ; Version résumée : La Recherche, 428 (2009) 48-51, fichier pdf

En 1874, Georg Cantor publie dans le journal de Crelle un article où il démontre qu'il n'existe pas plus de nombres algébriques que de nombres entiers mais que, par contre, il existe strictement plus de nombres réels. Cet article est révolutionnaire car, pour la première fois, l'infini est considéré non plus comme une limite inatteignable mais comme un possible objet d'investigation. Sa descendance est extraordinaire: non seulement il marque la naissance de la théorie des ensembles - en fait une théorie de l'infini - mais il contient déjà en germe le problème du continu qui a occupé toute la fin de la vie de Cantor, et a été et continue d'être le moteur du développement d'une théorie qui a été un temps objet d'une fascination déraisonnable reposant sur un malentendu et est aujourd'hui largement méconnue.


The Braid Isotopy Problem, Lecture Notes (Caen 2008, Guangzhou 2009 and 2010), pdf file (71 pages, 800 Ko)

Various algebraic and topological solutions to the Braid Isotopy Problem are described, with complete self-contained proofs.
Chapter 1: Braids, Chapter 2: Presentation of braid groups, Chapter 3: Using monoids, Chapter 4: The Artin representation, Chapter 5: The Dynnikov formulas, Chapter 6: Handle reduction, Chapter 7: The greedy normal form.


Le problème d'isotopie des tresses, Leçons mathématiques de Bordeaux, vol. 4, pages 259-300, Cassini (2011), fichier pdf

Le problème d'isotopie des tresses est la question de reconnaître si deux diagrammes de tresse peuvent être déformés continûment l'un en l'autre. C'est un problème de difficultée moyenne : ni trop facile - aucune solution n'est triviale - ni trop difficile - des solutions explicites existent. On présente quelques-unes des (très) nombreuses solutions connues à ce jour, l'intérêt principal étant la multiplicité des approches possibles - algébriques, géométriques, topologiques, etc. - et la diversité des solutions qui en résultent.


Efficient solutions to the braid isotopy problem, Disc. Appl. Math. 156 (2008) 3094-3112, pdf file

We describe the most efficient solutions to the word problem of Artin's braid group known so far, i.e., in other words, the most efficient solutions to the braid isotopy problem, including the Dynnikov method, which could be especially suitable for cryptographical applications. Most results appear in literature; however, some results about the greedy normal form and the symmetric normal form and their connection with grid diagrams may have never been stated explicitly.


Convergence of handle reduction of braids, Lecture notes (12 pages), pdf file

We give a proof for the convergence of the handle reduction algorithm of braids that is both more simple and more precise than the ones available in literature. The prerequisites are Garside's theory of positive braids, and one technical result about Artin's representation of braids.


Théorie des ensembles, Encyclopedia Universalis, Corpus, fichier pdf

La théorie des ensembles est la branche des mathématiques qui étudie les ensembles, spécialement les ensembles infinis, à la façon dont l'arithmétique étudie les nombres entiers ou la géometrie les points, les droites et les cercles. Elle est apparue à la fin du XIXe siècle avec les travaux de Cantor, et a donné lieu depuis cette époque à un développement remarquable qui en fait aujourd'hui l'une des branches les plus sophistiquées. Placée un temps à la base de l'édifice mathématique en raison de la possibilité d'y représenter la plupart des objets usuels, la théorie des ensembles occupe aujourd'hui une position plus discrète, notamment parce que ses applications aux autres domaines demeurent relativement modestes. Pour autant, l'importance de ses enjeux intellectuels reste intacte, et les récentes avancées en direction d'une solution au problème du continu constituent des resultats fascinants tant pour le mathématicien que pour le philosophe.


Logique et théorie des ensembles, Notes de cours, FIMFA ENS, version 2006-2007

Chapitre 1 : Le type ensemble, Chapitre 2 : Les ordinaux, Chapitre 3 : Le système ZF, Chapitre 4 : L'axiome du choix, Chapitre 5 : Les cardinaux, Chapitre 6 : Logique propositionnelle, Chapitre 7 : Logique du premier ordre, Chapitre 8 : Théorèmes de limitation, Chapitre 9 : Modèles de ZFC, Chapitre 10 : Les ensembles constructibles ; Devoir, Examen 2005, Examen 2006, Examen 2007.


Artin-Tits groups, Lecture notes with exercises, Summer School in Combinatorics of Groups and Algebras, CIRM, July 2004 (18 pages), pdf file
Ensemble, infini, objet mathématique, objet universel, ordinaux et cardinaux, Notionnaire 1: Notions, Encyclopedia Universalis, 2005
Diagram colourings, Proc. First East Asian School of Knots, Links and related Topics, K.Y. Ko ed., Seoul (Korea), Feb. 2004, pp. 37-64, pdf file

This paper reviews some results involving arc colourings in a braid or a link diagram. The left self-distributivity idendity then appears as an algebraic counterpart to Reidemeister move of type III. Using classical and less classical self-distributive operations leads to a number of different results, as well as to many open questions.


Tresses, Encyclopedia Universalis, fichier pdf
Au-delà du forcing: la notion de vérité essentielle en théorie des ensembles, in: J.B.Joinet (ed.), Logique, dynamique et cognition, Public. Sorbonne (2007), pp 147-170, fichier pdf

Ce texte présente des développements récents de la théorie des ensembles, et en particulier des résultats de H. Woodin sur l'hypothèse du continu. On y introduit la notion de vérité essentielle d'une propriété, qui apparait comme une des possibilités les plus prometteuses pour dépasser les limitations induites par la méthode du forcing de Cohen. Par ailleurs, on discute brièvement le caractère de vérité d'un axiome tel que l'axiome de détermination projective.


Braid-based cryptography, Contemporary Mathematics, 360 (2004) 5-33, pdf file

We survey some of the recently developed cryptographic schemes involving Artin's braid groups, as well as the attacks against these schemes. We also point out some hints for future work.


Les travaux de Woodin sur l'hypothèse du continu, Encyclopedia Universalis, La science au présent 2004, 123-128
Progrès récents sur l'hypothèse du continu (d'après Woodin), Séminaire Bourbaki, exposé 915, mars 2003, fichier pdf

Les travaux récents de Woodin ont considérablement renouvelé la théorie des ensembles en lui apportant une intelligibilité globale et en restaurant son unité. Pour la première fois, ses résultats ouvrent une perspective réaliste de résoudre le problème du continu, et, à tout le moins, ils établissent le caractère irréfutablement signifiant et précis de celui-ci.

English version: Recent progress about the Continuum Hypothesis (after Woodin), pdf file

Woodin's recent work has considerably renewed set theory by restoring its unity and making the domain more globally intelligible. For the first time, his results open a realistic perspective to solve the Continuum Problem, and, at the very least, they show that the latter is an unquestionably meaningful and precise question.


Elementary embeddings and algebra, Handbook of Set Theory, edited by M. Foreman and A. Kanamori, Springer, to appear, pdf file

It has been observed for many years that computations with elementary embeddings entails some purely algebraic features (as opposed to the logical nature of the embeddings themselves). The key point is that the operation of applying an embedding to another one satisfies (when defined) the self-distributivity law $x(yz) = (xy)(xz)$. Using the specific properties of the elementary embeddings and their critical ordinals, hence under some large cardinal hypotheses, R. Laver established two purely algebraic results about sets equipped with a self-distributive operation (LD-systems), namely the decidability of the associated word problem (in 1989), and the unboundedness of the periods in some finite LD-systems (in 1993). The large cardinal assumption was eliminated from the first result by Dehornoy in 1992, using an alternative argument that directly led to unexpected results about Artin braid groups; as for the second of Laver's results, no proof in ZF has been discovered so far, and the only result known to date is that it cannot be proved in Primitive Recursive Arithmetic.


L'infini est un révélateur, Pour La Science 278 (2000) 138-142, fichier pdf
L'infini est-il nécessaire? Pour La Science 278 (2000) 102-106, fichier pdf
Action of braids on self-distributive systems, Low dimensional topology and combinatorial group theory, Chelyabinsk, July 31 - August 7, 1999; Proceedings of the International Conference, Kiev (2000), 87-111, pdf file

(AMS: 20F36, 20N02) This paper is a survey of recent work about the action of braids on self-distributive systems. We show how the braid word reversing technique allows one to use new self-distributive systems, leading in particular to a natural linear ordering of the braids.


L'art de tresser, Pour la Science HS15 (1997) 68-75, fichier pdf
Une autre application de la théorie des ensembles, Gazette des mathématiciens, 69 (1996) 3-20, fichier pdf

Les applications traditionnelles de la théorie concernent généralement des objets très grands et très compliqués. Le problème de la classification des tresses est d'un style très différent, puisqu'il ne met en jeu que des objets très simples et "concrets": les tresses, configurations finies formées de brins qui se croisent par dessus ou par dessous, et leurs transformations consistant à déplacer des brins sans qu'ils se traversent l'un l'autre. Pourtant, il se trouve que la solution la plus efficace connue à ce jour pour ce problème provient directement de travaux sur les grands cardinaux en théorie des ensembles. On décrit ici le passage d'une théorie à l'autre, en montrant comment les intuitions issues de l'étude des grands ensembles ont pu mener naturellement à des algorithmes de tresse spécialement performants en révélant une structure jusqu'alors cachée.


Another use of set theory, Bull. Symb. Logic 2-4 (1996) 379-391

From large cardinals to braids via distributive algebra, J. Knot Th. and Ramifications 4-1 (1995) 33-79

(AMS: 20F36, 20N02, 03E55, 57M25) This text presents some recent developments in left distributive algebra induced by set theory and their applications to the combinatorics of braids mainly in terms of order properties and existence of special decompositions.


La détermination projective d'après Martin, Steel et Woodin, Séminaire Bourbaki, Astérique 177-178 (1989) 261-276
Détermination Pi11 et Pi12, Publ. Math. Paris 7, 27 (1987) 89-102
L'échelle des grands cardinaux, Publ. Math. Paris 7, 19 (1985) 79-96
Codage des ordres dénombrables, Publ. Math. Paris 7, 19 (1985) 65-78
La conjecture de Borel, Publ. Math. Paris 7, 5 (1980) 119-142