Thèse envuedel’obtentiondugradede Docteur de l’École Normale Supérieure de Lyon – Université de Lyon Spécialité : informatique Laboratoire de l’Informatique du Parallélisme École Doctorale Informatique et Mathématiques présentéeetsoutenuepubliquementle29novembre2012par renet Bruno G Représentations des polynômes, algorithmes et bornes inférieures oiran Directeur de thèse : Pascal K ortier Co-directrice : Natacha P axena Après avis de : Nitin S chost Éric S Devant la commision d’examen formée de : umas Jean-Guillaume D Membre urand Arnaud D Membre oiran Pascal K Directeur athieu Claire M Présidente ortier Natacha P Co-directrice axena Nitin S Rapporteur Titre : Représentations des polynômes, algorithmes et bornes inférieures Résumé : La complexité algorithmique est l’étude des ressources néces- saires — le temps, la mémoire, ... — pour résoudre un problème de manière algorithmique. Dans ce cadre, la théorie de la complexité algébrique est l’étude de la complexité algorithmique de problèmes de nature algébrique, concernantdespolynômes.Danscettethèse,nousétudionsdifférentsaspects de la complexité algébrique. D’une part, nous nous intéressons à l’expressivité des déterminants de matrices comme représentations des polynômes dans le modèle de com- plexité de Valiant. Nous montrons que les matrices symétriques ont la même expressivité que les matrices quelconques dès que la caractéristique du corps est différente de deux, mais que ce n’est plus le cas en caractéristique deux. Nous construisons également la représentation la plus compacte connue du permanent par un déterminant. D’autre part, nous étudions la complexité algorithmique de problèmes algébriques. Nous montrons que la détection de racines dans un système de n polynômes homogènes à n variables est NP-difficile. En lien avec la question «VP = VNP?», version algébrique de «P = NP?», nous obtenons uneborneinférieurepourlecalculdupermanentd’unematriceparuncircuit arithmétique, et nous exhibons des liens unissant ce problème et celui du test d’identité polynomiale. Enfin nous fournissons des algorithmes efficaces pour la factorisation des polynômes lacunaires à deux variables. Mots-clés:complexitéalgébrique,déterminant,permanent,théoriedeVa- liant, bornes inférieures, corps finis, test d’identité polynomiale, factorisation, circuits arithmétiques, systèmes polynomiaux. Title: Representations of polynomials, algorithms and lower bounds Abstract: Computational complexity is the study of the resources – time, memory, ... – needed to algorithmically solve a problem. Within these settings, algebraic complexity theory is the study of the computational com- plexity of problems of algebraic nature, concerning polynomials. In this thesis, we study several aspects of algebraic complexity. On the one hand, we are interested in the expressiveness of the deter- minants of matrices as representations of polynomials in Valiant’s model of complexity. We show that symmetric matrices have the same expressiveness as the ordinary matrices as soon as the characteristic of the underlying field in different from two, but that this is not the case anymore in characteristic two. We also build the smallest known representation of the permanent by a determinant. On the other hand, we study the computational complexity of algebraic problems. We show that the detection of roots in a system of n homogeneous polynomials in n variables in NP-hard. In line with the “VP = VNP?” ques- tion, which is the algebraic version of “P = NP?”, we obtain a lower bound for the computation of the permanent of a matrix by an arithmetic circuit, and we point out the links between this problem and the polynomial identity testing problem. Finally, we give efficient algorithms for the factorization of lacunary bivariate polynomials. Keywords: algebraic complexity, determinant, permanent, Valiant’s the- ory, lower bounds, finite fields, polynomial identity testing, factorization, arithmetic circuits, polynomial systems. emerciements R es deux rapporteurs M , Éric Schost et Nitin Saxena, ont accepté de lire en détail ce manuscrit. Leurs remarques m’ont apporté un éclairage nouveau sur mes propres travaux, et leurs conseils me guideront dans les années à venir. Je tiens à les en remercier chaleureusement. Je suis également reconnaissant envers Claire Mathieu pour avoir accepté de présider mon jury de soutenance, et Jean-Guillaume Dumas et Arnaud Durand pour y avoir pris part. Recueillir l’avis de spécialistes couvrant un large spectre de l’informatique théorique a été très enrichissant. Pascal et Natacha, merci infiniment d’avoir accepté d’encadrer ma thèse alors que votre départ au Canada ne facilitait pas les choses. Je souhaite à tous les thésards de pouvoir bénéficier d’un encadrement comme le vôtre. n trois années E passées au sein du LIP à l’École Normale Supérieure de Lyon et du Department of Computer Science de l’Université de Toronto, j’ai eu la chance de rencontrer de nombreuses personnes. Je pense en particulier à mes quelques co-bureaux, par ordre d’apparition : Irénée, Santiago, Marcelo, Carlos, Lee, Yu, Marek, Kévin, Mathilde, Adrien, Yann, Sébastien, Théophile, Pierre et Aurélie. Je tiens à remercier tous les membres 2 du LIP, et en particulier l’équipe MC , pour les discussions autour d’un café ou d’une bière. Many thanks are due to the members of the Theory Group of the Department of Computer Science at the University of Toronto, and in particular to Yuval, Kaveh and Dai, who made my stay in Toronto so enjoyable. Before I switch back to French, I remember how lucky I was to meet Avner, his smile and his pairs of shorts. Mes coauteurs m’ont apporté leur vision des sujets abordés et de la recherche en informatique théorique plus généralement. Merci donc à Erich Kaltofen, Stéphan Thomassé, Thierry Monteil, Yann Strozecki et Arkadev Chattopadhyay. égulièrement R , je me suis appuyé sur le service d’assistantes du LIP pour toute sorte de tâches administratives. Un immense merci à Marie pour les réponses aux innombrables questions que je lui ai posées et pour l’organisation de mes missions, à Damien pour avoir atténué autant qu’il le pouvait la lourdeur des procédures d’inscription et de réinscription en thèse, et à Catherine, Évelyne, Laetitia, Sèverine et Sylvie pour avoir toutes, à un moment donné, su répondre à mes demandes. Avant de commencer ma thèse, j’ai eu le plaisir de découvrir l’informatique, et plus particulièrement i ii Remerciements l’informatique théorique, au département informatique de l’ÉNS Lyon. Pour tout ce qu’ils m’ont appris, je souhaite remercier autant mes enseignants — Daniel, Anne, Florent, Éric (×2), Yves, Nicolas, Guillaume, Sylvain (×2), Damien, Victor, ... — que mes camarades — BoolS, Pascal, Mathilde, ... omme une thèse C ne se résume pas au temps passé au labo, je souhaite remercier tous ceux qui m’ont accompagné durant ces trois années. À l’ÉNS Lyon, j’ai toujours pu compter sur les Zébus. Merci à Pierre, Fifi, Anto, Tom, Ju, Bleue, AnSo, Olive, Marion, Adrien, Bapt, Marc, Fred pour les officiels, mais également à Charlène, Tamara et Lise. Merci en particulier à Pierre et Charlène de m’avoir permis d’éviter la visite des ponts lyonnais. Il m’est parfois arrivé de quitter Gerland. Merci à Théo, Delph, Maëlle, Nico, Antoine, Gaston, Soline, Margot, Beune, et tous les autres pour les moments passés ensemble. Et parce qu’ils ne m’ont pas demandé si souvent que cela à quoiservaitmathèse,jeremerciemesparents,mesfrangins,mesbelles-sœurs et bien sûr Arthur et Alice! l y aurait mille raisons I de te remercier, Laurie. Pour garder un rapport avec ma thèse, ta décision de venir passer six mois à Toronto a été le plus beau cadeau que tu pouvais me faire. able des matières T Remerciements i Table des matières iii Introduction vii 1 Prolégomènes 1 11 1 . Polynômes, déterminants et graphes . . . . . . . . . . . . . . . 111 1 . . Polynômes . . . . . . . . . . . . . . . . . . . . . . . . . . 112 2 . . Déterminants . . . . . . . . . . . . . . . . . . . . . . . . 113 3 . . Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4 . Représenter les polynômes . . . . . . . . . . . . . . . . . . . . 121 4 . . Représentations dense, creuse et lacunaire . . . . . . . 122 6 . . Les circuits arithmétiques . . . . . . . . . . . . . . . . . 123 10 . . Les programmes à branchements . . . . . . . . . . . . 13 11 . Modèles de calcul et complexité . . . . . . . . . . . . . . . . . 131 11 . . Le modèle booléen . . . . . . . . . . . . . . . . . . . . . 132 13 . . Le modèle de Valiant . . . . . . . . . . . . . . . . . . . . I Résolution des systèmes polynomiaux 17 2 Complexité du résultant multivarié 19 21 22 . Complexité du résultant en caractéristique nulle . . . . . . . . 211 22 . . Borne supérieure . . . . . . . . . . . . . . . . . . . . . . 212 23 . . Borne inférieure. . . . . . . . . . . . . . . . . . . . . . . 2.2 NP-difficulté en caractéristique quelconque . . . . . . . . . . . 26 221 27 . . Une réduction probabiliste . . . . . . . . . . . . . . . . 222 28 . . Deux réductions déterministes . . . . . . . . . . . . . . 23 33 . Matrices de Macaulay . . . . . . . . . . . . . . . . . . . . . . . 231 34 . . Représentation des matrices de Macaulay. . . . . . . . 232 36 . . Déterminant d’une matrice représentée par un circuit iii iv Table des matières II Représentations déterminantielles de polynômes 39 3 Complexité déterminantielle 41 31 42 . Taille réduite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 44 . Circuits et programmes à branchements . . . . . . . . . . . . . 321 44 . . Formules et programmes à branchements . . . . . . . 322 46 . . Circuits asymétriques . . . . . . . . . . . . . . . . . . . 33 52 . Complexité du déterminant . . . . . . . . . . . . . . . . . . . . 331 53 . . Expressivité du déterminant . . . . . . . . . . . . . . . 332 54 . . Un programme à branchements pour le déterminant . 34 60 . Complexité déterminantielle du permanent . . . . . . . . . . . 4 Représentations symétriques 63 41 64 . Représentation symétrique des programmes à branchements 42 68 . Comparaisons avec des résultats existants . . . . . . . . . . . . 5 Représentations symétriques en caractéristique deux 73 51 74 . Prérequis algébrique . . . . . . . . . . . . . . . . . . . . . . . . 511 74 . . Polynômes, déterminants et graphes en caractéristique 2 512 75 . . Anneaux quotient . . . . . . . . . . . . . . . . . . . . . 52 76 . Polynômes représentables . . . . . . . . . . . . . . . . . . . . . 53 80 . Obstructions aux représentations . . . . . . . . . . . . . . . . . 531 80 . . Condition nécessaire . . . . . . . . . . . . . . . . . . . . 532 86 . . Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 533 86 . . Polynômes multilinéaires . . . . . . . . . . . . . . . . . 534 87 . . Vers une caractérisation complète? . . . . . . . . . . . 54 89 . Représentation et factorisation des polynômes multilinéaires 541 89 . . Résultats préliminaires . . . . . . . . . . . . . . . . . . . 542 94 . . Test de factorisabilité . . . . . . . . . . . . . . . . . . . . 543 96 . . Algorithme de représentation . . . . . . . . . . . . . . . 55 98 . Représentations déterminantielles alternées . . . . . . . . . . . IIIPolynômes de type creux 101 6 Autour de la τ-conjecture réelle 103 6.1 La τ-conjecture réelle . . . . . . . . . . . . . . . . . . . . . . . . 103 611 106 . . Travaux existants . . . . . . . . . . . . . . . . . . . . . . 612 107 . . Notre approche . . . . . . . . . . . . . . . . . . . . . . . 62 109 . Racines réelles des sommes de produits de polynômes creux 621 109 . . Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . 622 111 . . Une généralisation de la règle de Descartes. . . . . . . 623 114 . . Affinement de l’analyse . . . . . . . . . . . . . . . . . . 63 116 . Borne inférieure pour le permanent . . . . . . . . . . . . . . . Table des matières v 64 118 . Tests d’identité polynomiale . . . . . . . . . . . . . . . . . . . . 65 121 . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Factorisation des polynômes lacunaires à deux variables 123 71 125 . Valuation et théorème de lacune . . . . . . . . . . . . . . . . . 711 71 126 . . Preuve du théorème . . . . . . . . . . . . . . . . . . . 712 130 . . Des améliorations possibles? . . . . . . . . . . . . . . . 713 133 . . Un théorème de lacune . . . . . . . . . . . . . . . . . . 72 134 . Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 138 . Généralisations . . . . . . . . . . . . . . . . . . . . . . . . . . . 731 138 . . Une borne générale sur la valuation . . . . . . . . . . . 732 141 . . Généralisations des algorithmes . . . . . . . . . . . . . 74 143 . Caractéristique positive . . . . . . . . . . . . . . . . . . . . . . Bibliographie 147