Groupe de Galois - Complexité

Ayoub
Ayoub
dans Algèbre
Bonsoir à tous :)

Je me posais la question suivante il y a bien longtemps, et n'ayant pas trouvé de réponse je l'ai tout bonnement oublié jusqu'à il y a quelques jours:

Je m'intéresse au problème du calcul effectif de groupe de Galois sur Q. Plus précisemment, aux méthodes déterministes parce que je trouve ça plus charmant que les méthodes probabilistes. Peut-on minorer a priori la complexité d'un algorithme qui prend comme entrée un polynôme (irréductible) et qui renvoie son groupe de Galois?

Ca me paraît très peu probable mais si vous savez quelque chose concernant ceci, je suis prenant.

Merci.
:)

Réponses

  • Ksilver
    Ksilver
    Salut !

    Pour obtenir ce genre de borne, il faut définir très précisément ce qu'on attend en entré et en sortie.

    En entré tu as un polynôme à coefficients rationnels, ça ne pose pas de problème.

    En sortie en revanche on a "un groupe" : c'est nettement moins clair. Quelle genre de structure de données tu utiliseq pour définir un groupe ?
    Soit tu l'appelles par son nom (S3, D4, A7 etc...) mais là il faut connaitre, tous les sous-groupe fini de Sn (à n fixé) et on est dans ce que tu appelles les algo probabilistes.
    Soit tu listes ses éléments, et dans ce cas l'algo aura une complexité minorée par la taille de la sortie, soit le cardinal du groupe, qui est donc (dans le pire des cas) n!, et donc la complexité dans le pire des cas est toujours au moins n!...

    D'un autre coté, je ne pense pas qu'on puisse donner une borne pour une meilleur raison, car on ne peut pas exclure qu'un jour on connaisse tous les groupes finis et donc que les algorithmes 'probabilistes' puissent fonctionner pour tous n (réduisant énormément la difficulté de tels calculs)
  • Ayoub
    Ayoub
    Salut :)

    Par groupe, je sous-entendais la liste de ses éléments. Dommage, m'enfin, le contraire aurait été surprenant.

    5 you.
    :)
  • mt-i
    mt-i
    Une bonne façon de fournir la sortie d'un tel programme est lister un système générateur du groupe en tant que sous-groupe de S_n. Je soupçonne qu'on peut faire bien mieux que n!, quand même.

    Joyeux Noël.
  • Ksilver
    Ksilver
    à ma connaissance, les seuls algos qui ont des temps mieux que n!. utilisent en gros une liste de tous les sous groupes transitifs de Sn pour n inférieur à un certain N, et utilise des réductions modulo p et des résultats type chebotarev pour trouver le bon groupe par élimination, et ne fonctionne plus pour n>N... (et c'est ce genre de choses que Ayoub appellait "algo probabiliste" je pense.)

    le système de générateur bloque mon argument, mais je vois pas trop comment on peut faire la moindre opération sur un système génerateur avec des temps mieux que n! (rien que calculer le cardinal du groupe par exemple ? )
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Français