Les polynômes

Tout le monde se secoue ! 

J’ai commencé (dimanche 19 janvier 2020 à 12h09) la rédaction d’un tutoriel au doux nom de « Les polynômes » et j’ai pour objectif de proposer en validation un texte aux petits oignons. Je fais donc appel à votre bonté sans limites pour dénicher le moindre pépin, que ce soit à propos du fond ou de la forme. Vous pourrez consulter la bêta à votre guise à l’adresse suivante :

Merci !

Edit : Pour le moment, il n’y a que la première partie, mais c’est déjà velu. Mais je compte bien continuer à explorer les polynômes ! (du coup, durant cette phase de bêta de la première partie, je vais commencer le brouillon, mais n’y faites pas attention pour le moment) J’adore me faire critiquer, pour peu que ce soit constructif. Alors allez-y Néanmoins :

1. Je voulais faire un cours de mathématiques. J’ai donc conscience que c’est tout de même difficilement accessible par rapport à d’autres sujets de vulgarisation.
2. C’est pourquoi j’ai choisi de me mettre proche du lecteur pour le prendre par la main dans cet univers délicieux !

Tout d’abord, bravo à toi pour le travail effectué.

C’est qualitatif, bravo ! Vu les chapitres annoncés, tu te calques environ sur le programme de MPSI ? Et tu comptes faire quoi dans les « familles de polynômes » ?

T’as un point de vue très algébrique et tu as pris le parti de faire vraiment toutes les preuves en détail (c’est courageux), mais d’un autre côté je sais pas si c’est suivable en détail de bout en bout. Et perso je trouve ça un peu malhonnête de dire à quel point les maths c’est beau quand on vient de finir une récurrence de 4 pages avec des jeux de réécriture pour prouver des trucs d’arithmétique de polynômes, ce qui est un peu l’enfer sur terre en terme de pénibilité d’écriture.

Du coup, si je devais faire un reproche, je dirais que je trouve ça manque de peu d’exemples/d’applications/de perspective. Genre l’enchaînement arithmétique 1/2/3 et polynômes multivariés 1/2, ça parle tout le temps des mêmes objets, c’est toujours le même genre de preuves, etc. Je pense qu’il faudrait entrecouper d’autres choses (ne serait-ce que par des exos d’arithmétique).

À la limite tu pourrais même te permettre plus de digressions pour prendre un peu de recul, par exemple quand tu cites juste « courbe elliptique », alors qu’en fait voir que pour un certain machin de degré 3 c’est difficile de comprendre ce qui se passe (t’as même pas besoin de parler des formes projectives, juste écrire l’équation quoi), c’est assez éclairant. Pareil, dans le dernier chapitre tu construis pile les bons outils pour faire des bases de Gröbner (tu fais même toutes les preuves de relation d’ordre sur les monômes) et à la fin on a juste « ah non mais mais on sait pas faire d’arithmétique quand on a plusieurs variables », du coup c’est un peu frustrant. Bon après je reconnais que c’est assez ambitieux de faire de la géométrie algébrique juste après avoir introduit la valeur absolue.

Je sais pas si tu comptes en parler dans les chapitres qui suivent mais pour moi il manque la motivation des polynômes en tant que « machin pour transporter des suites de coefficients » (aspect série formelle en combinatoire ou fonction génératrice en probas), et aussi tous les trucs d’analyse sur les polynômes, par exemple les problèmes d’extrémalité. C’est plutôt complémentaire de toute la couche algébrique que tu présentes dans ta première partie (et ça motive mieux l’apparition de ce type d’objets, sinon on voit pas trop pourquoi on fait tout ça).

La troisième méthode nécessite de décomposer en facteurs premiers des nombres. Autant cela se fait très bien pour des petits nombres, autant, c’est un problème extrêmement compliquée, tellement compliqué que c’est cette complexité là qui assure que la cryptographie par chiffrement RSA (l’une des plus utilisées au monde) est sûr. C’est vous dire la complexité du machin.

C’est un peu fake news ça, nan ? Y a pas de réduction de la factorisation à RSA (bon et par ailleurs factoriser des entiers on sait faire ça en temps sous-exponentiel — le « tellement compliqué » est assez exagéré). Pour le coup l’info regorge de motivations pour étudier les polynômes : la crypto multivariée (aka on sait pas résoudre des systèmes polynomiaux), tous les problèmes de tenseurs en machine learning (maximiser un polynôme homogène sur la sphère), les problèmes de séparabilité en info quantique, une grande partie de la théorie de la complexité aujourd’hui (typiquement sum-of-squares), etc.

C’est qualitatif, bravo ! Vu les chapitres annoncés, tu te calques environ sur le programme de MPSI ? Et tu comptes faire quoi dans les « familles de polynômes » ?

C’est le programme que j’ai suivi, donc je me calque dessus, oui, en essaytn de le rendre accessible.

T’as un point de vue très algébrique et tu as pris le parti de faire vraiment toutes les preuves en détail (c’est courageux), mais d’un autre côté je sais pas si c’est suivable en détail de bout en bout. Et perso je trouve ça un peu malhonnête de dire à quel point les maths c’est beau quand on vient de finir une récurrence de 4 pages avec des jeux de réécriture pour prouver des trucs d’arithmétique de polynômes, ce qui est un peu l’enfer sur terre en terme de pénibilité d’écriture.

Hhhm, vu comment c’est fait, je ne vois pas de quoi tu parles, surtout pour l’arithmétique I. Les deux autres, peut⁻être. Malheureusement, il faut ça pour parvenir à la décompositionen facteurs irréductibles.

Du coup, si je devais faire un reproche, je dirais que je trouve ça manque de peu d’exemples/d’applications/de perspective. Genre l’enchaînement arithmétique 1/2/3 et polynômes multivariés 1/2, ça parle tout le temps des mêmes objets, c’est toujours le même genre de preuves, etc. Je pense qu’il faudrait entrecouper d’autres choses (ne serait-ce que par des exos d’arithmétique).

Sur ce coup-là, tu m’as fait réfléchir, et je pense que je vais le prendre en compte. Je comptais commencer les racines plus tard, mais je vais peut-être explique ce que c’est juste après arithmétique I, en faire deux chapitres qui du coup seraient assez light, puis finir arithmétique II et III, puis renvoyer les poylnômes multi-variés au chapitre 2.

À la limite tu pourrais même te permettre plus de digressions pour prendre un peu de recul, par exemple quand tu cites juste « courbe elliptique », alors qu’en fait voir que pour un certain machin de degré 3 c’est difficile de comprendre ce qui se passe (t’as même pas besoin de parler des formes projectives, juste écrire l’équation quoi), c’est assez éclairant. Pareil, dans le dernier chapitre tu construis pile les bons outils pour faire des bases de Gröbner (tu fais même toutes les preuves de relation d’ordre sur les monômes) et à la fin on a juste « ah non mais mais on sait pas faire d’arithmétique quand on a plusieurs variables », du coup c’est un peu frustrant. Bon après je reconnais que c’est assez ambitieux de faire de la géométrie algébrique juste après avoir introduit la valeur absolue.

1/ J’ai hésite pour les formes elliptiques. Mais si tu me dis que je peux en parler un peu plus, pourquoi pas, ça mettrait en perspective les polynômes homogènes qui sont vraimens pas utiles dans ce que j’imagine pour la suite.

2/ Je n’avais jamais entendu parler de "bases de Gröbner" auparavant. Cependant, pour être tout à fait honnête, je pense faire une annexe à ce cours, où je fais la théorie des polynômes sur un anneau intègre commutatif. D’une part, ça m’amuse, d’autre part, si des gens sont vraiment intéressés par ce cours après la théorie, ils y trouveront leur compte

Je sais pas si tu comptes en parler dans les chapitres qui suivent mais pour moi il manque la motivation des polynômes en tant que « machin pour transporter des suites de coefficients » (aspect série formelle en combinatoire ou fonction génératrice en probas), et aussi tous les trucs d’analyse sur les polynômes, par exemple les problèmes d’extrémalité. C’est plutôt complémentaire de toute la couche algébrique que tu présentes dans ta première partie (et ça motive mieux l’apparition de ce type d’objets, sinon on voit pas trop pourquoi on fait tout ça).

Toute la partie analyse, je la voyais dans le chapitre 4, où je comptais parler de l’approximation polynômiale des fonctions en long en large et en travers. Mais je vais peut être ramener ça au chapitre 3.

I mean ,je suis pas spécialiste en info, donc pourrais-tu préciser un chouïa quelles conneries j’ai dites dans mon apparté ?

1/ J’ai hésite pour les formes elliptiques. Mais si tu me dis que je peux en parler un peu plus, pourquoi pas, ça mettrait en perspective les polynômes homogènes qui sont vraimens pas utiles dans ce que j’imagine pour la suite.

Ah donc tu veux définir les courbes elliptiques avec le modèle projectif ? C’est une bonne idée, mais un peu plus avancée que ce que j’avais en tête. Dans mon esprit tu pouvais décrire une famille spécifique de polynômes remarquables $(P(x,y)=y^2+x^3+ax+b)_{a,b}$ (ultra « simples », 2 variables, degré 3), et sans même décrire la structure de groupe qu’il y a derrière, juste laisser entendre que la géométrie des racines sur un corps fini d’un de ces trucs-là est déjà très difficile à comprendre  — ne serait-ce que la cardinalité, après tout c’est une brique de base dans les équivalences avec les formes modulaires. Mais c’est vrai qu’il y a beaucoup de choses à dire sur les racines de polynômes et que ça rentrerait mieux dans ta partie 2.

Pour le coup, je pense que c’est assez difficile de motiver l’apparition des polynômes homogènes ; la question au fond c’est « pourquoi on préfère faire de la géométrie dans des espaces projectifs ? ». Pour reprendre un exemple que je connais mieux (l’info théorique), les polynômes homogènes « apparaissent » quand on considère la forme algébrique associée à un k-tenseur symétrique en complexité/quantique/ML $x\mapsto \sum_{i\in [n]^k} T_i x_i$ (la généralisation à k dimensions de la forme quadratique associée à une matrice symétrique $x\mapsto x^T M x$). Mais je ne crois pas que toute la théorie algébrique qu’il y a autour de ces objets ait vraiment trouvé une application là-dedans jusqu’à présent (en ce moment, la tendance est même à l’inverse de démontrer des résultats de maths fonda avec des outils de complexité développés initialement pour l’info — cf. la résolution de la conjecture de Connes sur les algèbres de von Neumann le mois dernier).

En fait, on pourrait dire la même chose pour la « famille de polynômes remarquables » dont tu parles juste en-dessous, les polynômes symétriques. Par exemple, toute la théorie des invariants consiste à remplacer l’action de $\mathfrak{S}_n$ par une action de groupe plus compliquée et d’établir un résultat analogue aux décomposition de polynômes symétriques en polynômes symétriques élémentaires (peut-être que tu vas en parler de celui-là, il me semble que c’est vaguement au programme de prépa ?). Mais là encore, difficile de vraiment motiver la raison profonde de l’étude de ce genre d’objets.

2/ Je n’avais jamais entendu parler de "bases de Gröbner" auparavant. Cependant, pour être tout à fait honnête, je pense faire une annexe à ce cours, où je fais la théorie des polynômes sur un anneau intègre commutatif. D’une part, ça m’amuse, d’autre part, si des gens sont vraiment intéressés par ce cours après la théorie, ils y trouveront leur compte

Juste pour préciser l’aspect des bases de Gröbner qui correspond à ce que tu dis dans ta partie sur l’arithmétique des polynômes à plusieurs variables : étant donné un ordre sur les monômes, on peut définir un algorithme de division de $p$ par $p_1,\ldots,p_k$ dans $\mathbf{K}[x_1,\ldots,x_n]$ comme $p=\sum_{i} q_i p_i+r$ où les $q_i$ sont des polynômes et pour tout $i$, aucun des monômes de $r$ n’est divisible par le monôme dominant de $p_i$. A priori le « reste » $r$ qu’on obtient à la fin n’est pas unique, mais il l’est si $p_1, \ldots, p_k$ forment une base de Gröbner de l’idéal qu’ils génèrent (en particulier pour $k=1$ on retrouve Euclide). Si ça t’intéresse la référence en géométrie algébrique appliquée c’est Ideals, Varieties and Algorithms (Cox, Little, O’Shea).

Toute la partie analyse, je la voyais dans le chapitre 4, où je comptais parler de l’approximation polynômiale des fonctions en long en large et en travers. Mais je vais peut être ramener ça au chapitre 3.

C’est quoi l’approximation polynomiale ? Si tu parles des histoires de densité en analyse fonctionnelle, moi je pensais tout bêtement à de l’analyse réelle (p.ex. en fonction du degré, trouver un polynôme stable par $[-1,1]$ qui maximise la dérivée en 0), qui sont des trucs qui apparaissent souvent en maths appliquées (voir ça en ML par exemple). Pour rester dans des souvenirs de prépa, un truc qui m’avait pas mal marqué c’était les histoires de continuité de racines de polynômes pour des topologies bien choisies (cf. exercice 3 ici).

I mean ,je suis pas spécialiste en info, donc pourrais-tu préciser un chouïa quelles conneries j’ai dites dans mon apparté ?

En vrai ce que tu dis n’est pas complètement faux, je dirais que c’est juste exagéré/pas clair pour les raisons suivantes :
(1) « Factoriser des entiers c’est extrêmement compliqué » : d’un point de vue complexité la factorisation d’entiers c’est un problème plus « facile » que n’importe quel problème d’optimisation un peu tordu que tu pourrais inventer (au sens où on pense très fortement que c’est pas un problème NP-complet), et on a des algorithmes « pratiques » en temps sous-exponentiel pour depuis longtemps (p.ex. ECM, QS, NFS, etc.). Et d’un point de vue purement pratique, on sait factoriser des clés RSA franchement gigantesques (le dernier résultat en date de décembre c’est $10^{240}$). Évidemment, les clés qu’on utilise en pratique sont encore plus grandes (typiquement 2048 bits), mais c’est un peu le jeu du chat et de la souris. Bon et vu que c’est redevenu à la mode l’année dernière, rappelons qu’on sait factoriser des entiers en temps polynomial sur un ordinateur quantique. Après, effectivement, sur un ordinateur classique, ça reste probablement plus difficile que Euclide !
(2) « RSA est sûr parce que factoriser des entiers c’est difficile » : on sait pas si RSA est équivalent à la factorisation (si on sait factoriser des entiers rapidement, alors on a cassé RSA, mais l’inverse n’est pas forcément vrai — il est possible qu’il y ait d’autres attaques, et d’ailleurs historiquement les principales sont de ce type). De manière générale RSA c’est bien car historique (sûr car « il a résisté à l’épreuve du temps ») mais mathématiquement assez peu satisfaisant.

Par ailleurs, dans la crypto post-quantique (qui consiste faire de la crypto à clé publique sûre contre des adversaires quantiques, en gros le but c’est de remplacer RSA), il y a beaucoup de polynômes (cf. par exemple les candidats à NIST).