je peux déjà te suggerer de parcourir le livre de Jean Pierre Escofier théorie de Galois qui contient plein d'exemples de calculs de groupe de galois en exercices
un des derniers chapitre donne des algorithmes pour les equations de degre 4 notamment

Salut apaugam

Merci pour la référence, j'essaierai de l'emprunter pour voir ce que ça donne. Sinon, mes livres de références pour l'instant pour la théorie sont Modern Computer Algebra et Field Arithmetic, des gros pavés pas super accueillants quoi.

la bible en anglais c'est
Galois Theory par Ian Stewart et Aan N. Stewart

en français il y a aussi
Théorie de Galois par Yvan Gozard
ss doute plus theorique que JPE
Jean Pierre Escofier théorie de Galois est centré sur les extensions de Q et contient de nombreuses references à l'histoire, en particulier la vie de Galois fait l'objet d'un chapitre

et un autre livre de josette Calais que je ne connais pas mais je connais le livre sur les groupes du meme auteur qui est aussi une reference

J'en prends note.

_{Je viens de parcourir vite fait ton site. Algébriste dans l'âme et qui de plus a fait de la géométrie algébrique... kro la classe}

Bonjour,

Tu peux consulter le livre de Henri Cohen : A course in computational algebraic number theory (Springer).
La section 6.3 est consacrée à ce problème et donne des algorithmes jusqu'au degré 7.

Cordialement
Frenicle

Bonsoir frenicle

Tu l'as lu? Il est bien? Ca devrait pas être trop compliqué de le trouver lui non plus.

Salut !


à ma connaissance ce problème n'est pas résolu en degré quelconque (mais seulement jusqu'au degrée 33 ou 34...). J'essaierai de te trouver des références dessus.

Salut Ksilver

Oui, tu as raison mais c'est pour des raisons de complexité évidente. Quasiment aucun algorithme de calcul effectif de groupe de Galois n'est déterministe (je connais aucun logiciel qui d'ailleurs en possède un). Et pour les probabilistes (type celui de Maple), ils évaluent la probabilité d'être tel ou tel sous-groupe de S_n. A degré fixé, cela revient à connaître tous les sous-groupes transitifs de S_n, de réduire modulo un grand nombre de nombre premier et puis de conclure par arguments plus ou moins convaincants de cardinalité ou de truc du même genre. Et vu qu'on ne connaît tous les sous groupes transitifs que S_n que jusqu'à n=31...

Mais dans le cas déterministe c'est toutafé différent.
Par exemple, quand j'ai démontré en exo que le problème du calcul d'un groupe de Galois était algorithmique (ie, décidable) on a exhibé un algorithme théorique qui répondait parfaitement au problème.
Le seul souci c'était qu'il était de complexité O(n!) pour l'une seulement des étapes... et c'était loin d'être la plus grosse...

Oui aprés quelque recherche je suis d'accord avec toi...

ceci dit,  c'est normale de trouver une compléxiter "dans le pire des cas" en O(n!) vu que dans le pire ton groupe de Galois à n! element, et que à moins de connaitre une liste des groupes finit possible (ce qui n'existe pas encore, sauf si on ce limite au polynome de degrée <n fixé... ) on ne peut pas espérer un algorithme dont la compléxité soit meilleur que O(la taille du groupe de Galois)

Voui voui, toutafé; du moins tant qu'on interprète (et donc cherche) le groupe de Galois comme sous-groupe de S_n on pourra difficilement se passer de cette étape en O(n!).

C'est pour cela entre autres que j'essaie de voir si on ne peut pas décomplexifier les autres parties de l'algorithme, ce qui n'est pas gagné d'avance (notamment la vilaine partie sur le décomposition en produit de facteurs irréductibles sur Q[X_1,...,X_n], pas zoli du tout celle-là...).

Dans le meilleur des cas, j'adopterai un autre point de vue qui m'enlèvera définitivement cette tare de S_n et me permettra de m'en sortir à moindre coût. Dans le pire (ie, si on ne peut vraiment pas faire sans ce foutu S_n), bah j'essaierai de "minorer" la complexité d'un algorithme déterministe a priori, ce qui justifiera mon algo...

Plus j'y pense et plus je me dit que ça va être une gageure ce tipe...

Une 'tite question. J'en profite vu qu'il y a des spécialistes de la théorie de Galois sur le topic

J'ai remarqué () que lorsqu'on cherche des résultats "déterministes" lors de calcul général de groupe de Galois, on utilisait presque toujours des résolvantes. Je m'explique: en exo, le peu de fois où on se proposait d'établir des résultats un tant soit peu généraux, l'auteur faisait intervenir à un moment ou a un autre une résolvante...

C'est une simple coincidence ou y a t-il là quelque chose d'important à savoir? D'ailleurs, dans aucun de mes cours d'algèbre je n'ai entendu parler de résolvantes et google ne m'aide pas trop sur ce sujet. Donc d'abord qu'est ce que vraiment et puis pourquoi cette utilisation systématique des résolvantes? Que nous apportent-elles quand on fait du déterministe?

J'espère avoir été un peu clair, c'est pas gagné avec moi.

le terme résolvante s'emploie pour désigner le polynome irreductible dont une racine x engendre le corps de décomposition du polynome
c'est à dire que toutes les racines du polynome peuvent s'exprimer comme polynome en  x a coeff ds Q
ce x s"appelle élément primitif
je ne suis pas sure qu'il y ait des methodes effectives pour trouver un élément primitif pour resoudre des polynomes de n'importe quel degré
pour le degré 4 il y a des algorithmes (voir JPE page226) qui consistent à travailler ds le groupe S_4 qui est resoluble
à partir du degre 5 cela se complique

on trouve aussi dans JPE page 156
Jean Pierre Escofier théorie de Galois
un paragraphe sur les resolvantes de Lagrange

c'est le cas d'un groupe de galois cyclique

Merci apaugam.

je pense qu'il y a encore moyen de faire secher les logiciels de calcul formel sur la factorisation en etant un peu astucieux pour choisir son polynome

Oui mais c'était peu prévisible que ce problème soit algorithmique... du moins j'ai trouvé ça assez surprenant la première fois. J'ai pas encore lu la preuve donc ca reste assez magique ce truc pour moi. Mais t'as raison: ça doit pas être très compliqué de le faire chercher pendant un moment avant qu'il te ressorte "irréductible"...

avant qu'il te ressorte "irréductible".
meme pour un polynome qui ne l'est pas !

Oui enfin dans ce cas, reste plus qu'à le jeter ton algo...

les algorithmes de facorisation utilise souvent un peu de proba pour compenser le manque de capacité des ordi

Ok. D'où la necessité d'avoir un performant déterministe, je vais y remédier avec mon tipe...

_{Le mec à peine prétentieux... qui va déchanter dans moins de temps qu'il faut pour le dire...}