Factorisation dans $\Q[X]$
dans Algèbre
Je crois que c'est un problème ouvert actuellement de savoir s'il existe un algorithme qui dit si une équation (à plusieurs inconnues) polynomiale à coefficients entiers à des solutions rationnelles ou pas.
Au détour d'un fil qui se voulait anecdotique: http://www.les-mathematiques.net/phorum/read.php?3,2054150,2056318#msg-2056318
Je viens d'apprendre que la résolution en rationnels de n'importe quel polynôme à une indéterminée est ultrasimple (Les solutions possibles sont parmi un petit nombre de fractions, celle dont le numérateur est diviseur du coef constant et dont le dénominateur est diviseur du coef dominant). Difficile de faire plus simple...
Du coup, je me demandais s'il y avait un algorithme rapide pour factoriser un polynôme dans $\Q[X]$ en produit d'irréductibles, puisque c'est la "petite"(?) généralisation de ce que j'ai écrit en bleu dans le lien?
Et question "d'histoire": quelqu'un sait-il pourquoi le théorème bleu n'est pas "médiatisé" chez les matheux (ou à moins que ce soit encore une de mes éclipses personnelle...)?
Au détour d'un fil qui se voulait anecdotique: http://www.les-mathematiques.net/phorum/read.php?3,2054150,2056318#msg-2056318
Je viens d'apprendre que la résolution en rationnels de n'importe quel polynôme à une indéterminée est ultrasimple (Les solutions possibles sont parmi un petit nombre de fractions, celle dont le numérateur est diviseur du coef constant et dont le dénominateur est diviseur du coef dominant). Difficile de faire plus simple...
Du coup, je me demandais s'il y avait un algorithme rapide pour factoriser un polynôme dans $\Q[X]$ en produit d'irréductibles, puisque c'est la "petite"(?) généralisation de ce que j'ai écrit en bleu dans le lien?
Et question "d'histoire": quelqu'un sait-il pourquoi le théorème bleu n'est pas "médiatisé" chez les matheux (ou à moins que ce soit encore une de mes éclipses personnelle...)?
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
$$ a_9(\frac{p}{q})^9 + a_8(\frac{p}{q})^8 + \dots + a_0 = 0$$
force $q$ à diviser $a^9p^9$ (il suffit de multiplier l'égalité ci-dessus par $q^9$ et constater qu'on a un truc de la forme $a_9p^9 + Truc\times q=0$)
Mais comme $q$ est premier avec $p^9$, il divise $a_9$.
De plus $\frac{q}{p}$ est racine de
$$ a_0X^9+\dots + a_8 X + a_9$$
donc, pour la même raison $p$ est un diviseur de $a_0$.
C'est en effet un théorème classique des mathématiques discrètes (un des outils conceptuels de la fabrication des logiciels de calcul formel), quasi-évident si on traite un exemple de recherche d'une solution rationnelle d'un polynôme à coefficients entiers. Et on a des algorithmes rapides, implémentés dans tous les logiciels de calcul formel (Voir "Calcul formel" de Davenport et al - Parisse connait bien cela). Maple factorise complétement 8*x^4+66*x^3-47*x^2-1056*x-1296 en quelques millières de secondes.
Cordialement.
C'est vachement utile le forum. Car j'ai toujours eu en tête le nom de Grete Hermann (1901-1984) et j'étais persuadé que c'était un homme. Eh bien, non, c'est une femme.
Cela serait bien compléter les quelques références figurant dans les deux pages de Joachim von zur Gathen. Par exemple, Kaltofen http://pdfs.semanticscholar.org/9df7/df8450b5f617a1c45bad468534cf4abc5622.pdf, http://math.univ-lyon1.fr/~roblot/resources/factor.pdf ..etc.. . Il y a des livres entiers consacrés à cette activité (sur des corps finis, sur $\Q$, sur des corps de nombres, sur ..., à plusieurs variables ...etc..). J'ai la flemme de chercher (c'est pas bien).
Je ne suis pas chez moi pour vérifier mais c'est peut-être fait dans le Mignotte, Mathématiques pour le calcul formel.
P.S. : J'ai appris l'algorithme de Hörner en 1ère. Je le trouve tellement épatant que j'en fais don à mes élèves chaque année !
Oui, en plein dans le mille : tu as raison et je n'ai aucune excuse car je le possède (ainsi qu'un certain nombre d'autres ouvrages sur le sujet).
Mignotte, dans le livre que tu cites, consacre le chap VI à la factorisation sur un corps fini (un peu près 30 pages) et le chap VII à la factorisation des polynômes à coefficients entiers (30 pages).
Aucune excuse ? En fait, si : il fallait que je monte au premier étage et j'avais la flemme. C'est pas une excuse ?
Cordialement.
Pour ceux qui ne possèdent pas le Mignotte et puisque gerard0 l'a évoqué, on peut également consulter le chapitre 18 de [ce document] de Bernard Parisse, le concepteur de XCas et accessoirement membre de notre cher forum.
1. Soit $f = gh$ une factorisation dans $\Z[X]$. Alors c'est une factorisation de $f$ dans $\Q[X]$. Dingue, non ?
2. Soit $f = gh$ une factorisation dans $\Q[X]$. Alors il existe $c \in \Q^*$ tel que $cg\in \Z[X]$ et $c^{-1}h \in \Z[X]$ si bien que $f = (cg)(c^{-1}h)$ est une factorisation de $f$ dans $\Z[X]$. De plus, $c$ est unique au signe près.
Rien à voir. Juste pour faire joujou et voir des temps de calculs. Allons-y
C'était "confirmé" par le fait que CQ me mettait un lien vers ... la vie de Kronecker et non vers un algorithme et que GR me renvoyait ou bien vers le chap 18 de Parisse (dont je n'ai pas compris l'algo à cause des somme indicée que mon handicap me gêne assez fortement pour lire) ou bien vers son signalement qu'on lui a appris ça en première.
De mon côté, je suis pourtant comme MrJ (avec une connaissance du théorème rappelé juste au dessus par CQ (qu'il suffit de savoir factoriser dans $\Z[X]$)), je ne vois que la recherche exhaustive (évidemment fini par interpolation).
Et bé, vous m'avez fait une bonne blague: je viens de fouiller plus de 30mn google, et je syuis tombé sur un pdf publié sur HAL de Mignotte qui raconte
https://www.researchgate.net/publication/281047626_La_Premiere_Methode_Generale_de_Factorisation_des_Polynomes
l'entièreté de l'histoire de cet exercice générique.
Et conclusion: [large]bin, il n'y a pas d'algo[/large] au sens "d'une nature qui impressionnerait"
(autres que ceux qui optimisent ce que MrJ a raconté ci-dessus + le théorème de CQ (dont le vrai auteur est Gauss sauf erreur, j'éditerai si erreur)
Pour les lecteurs intéressés, l'expression "algorithme de Horner" évoquée par GR renvoie vers le calcul rapide de ... f(a) :-D
Et pis bin googler "factoriser un polynôme" est un chemin de croix, avec agression immédiate des millions d'auto-profs qui vous rabâchent comment factoriser un polynôme de degré 2 en .. première.
Sinon, je donne pour éviter le chemin de croix évoqué, je raconte "ce que j'ai cru lire":
On connait entièrement un polynôme sur $\Z$ quand on connait les images de $1+ $ son degré nombres.
Ses facteurs cherchés sont de degrés $<$ son degré.
Moralité, on est ramené à factoriser ... une application d'un ensemble fini inclus dans $\Z$ à valeurs dans $\Z$. Ce qui nous ramène à la factorisation des entiers (connues comme difficile et difficulté utilisée dans RSA).
Toutes les méthodes semblent + ou - optimiser ce principe.
Remarque: GR m'a renvoyé vers un algo exposé par B.Parisse mais je ne l'ai pas compris. A tout le moins, il utilise LA DERIVEE (ce qui sent bon), mais peut-être n'est-ce que pour virer les facteurs carrés, je ne sais pas.
Gérard a raison, je me suis mal exprimé. Je ne doutais pas qu'en une variable les spécialistes modernes savent factoriser vite (et le passage que tu cites je l'avais lu).
Mais "au fond de moi", je me demandais s'il existait un critère "prouvable et simple", non réservé aux spécialistes (ou aux gens qui passeraient plusieurs dizaines d'heures) un peu à l'image du petit ensemble fini dans lequel on sait que les racines rationnel du polynôme se trouve.
J'avais été un peu "motivé" dans cet espoir à la suite des premières réponses, puisque je voyais surgir des expressions "j'ai appris l'algorithme de Horner en première", etc, par des intervenants dont on voit bien par ailleurs qu'ils n'étaient pas à LLG, etc.
Donc du coup pardon pour le côté un peu sarcastique de la phrase "vous m'avez bien eu". Evidemment, je me doute que vous aviez tous autre chose à faire que de m'avoir, c'est plus une blague contre moi-même d'avoir un peu vite rêvé.
Cela dit de toute façon, on ne peut guère s'attendre à ce qu'une factorisation dans $\Z[X]$ ou dans $\Q[X]$ contourne la factorisation des entiers qui est connue comme impraticable actuellement (même si c'est encore ouvert), donc c'était une question "toute de principe".
Un grand (et sincère!) merci à vous tous.
Il se trouve qu'on apprenait pas mal de choses sur les polynômes à la fin des années 80 (et pas seulement à LLG) dès la 1ère, et notamment une version effective de $a$ racine de $P\Leftrightarrow X-a\mid P$, à savoir l'algorithme de Hörner.
A propos de $(X-a)$ divise $P(X)-P(a)$, c'est de la classe de quatrième que ça relève "sur le principe": le changement de variable, comme je l'ai déjà dit, je crois d'ailleurs dans un fil où tu avais beaucoup participé,
$$ P(Y+a)-P(a) = YQ(Y)$$
donne
$$ P(X)-P(a) = (X-a)Q(X-a)$$
sans aucun algorithme. "Les algorithmes" (je sais que c'est à la mode), c'est "pour aller plus vite". C'est un sujet intéressant, mais qui aurait dû être vendu en lycée (et collège) avec modération.
C'est exactement comme $PGCD(a,b)$ qui vaut $PGCD(a,b-a)$.
Et "non pas" le snob et infligé en 3ième $PGCD(b,r)$ avec $r:=blabla$.
Bon, mais c'était la remarque HS du matin, je l'ai déjà faite plus de 100 fois je pense (en 40000 posts :-D )
J'ai un peu regardé le 2) de [ce message].
Je pense avoir réussi à prouver l'existence de $c$ en utilisant notamment le contenu de $f$.
En revanche, j'ai un souci avec l'unicité de $c$ au signe près.
Prenons $f=30,g=\dfrac 1 3,h=90$.
Alors $3$ et $6$ sont des valeurs de $c$ qui conviennent au problème posé.
Tu as raison. Le coup du $c$ unique au signe près, j'ai ajouté cela sans réfléchir au dernier moment. Je ne vais pas aller corriger car j'ai la flemme. En guise ce cadeau, je t'attache ma note (dans laquelle il n'est pas mentionné d'unicité au signe près pour $c$). Note : le nom de fichier choisi est un peu stupide.
Au fait, ici tu parles du point 2. Mais as tu fait le point 1 ?
Merci pour le doc, j'avais effectivement la quasi-unicité de $c$ quand le contenu de $f$ vaut $1$.
C'est en tout cas largement inspiré du Mignotte.
Je tombe sur cette discussion que je n'avais pas remarquée avant. A moins que j'aie raté quelque chose, personne n'a mentionné le fait que la factorisation dans $\Q[X]$ se fait en temps polynomial (contrairement aux entiers, pour le moment). Ce résultat est démontré dans un article légèrement célèbre, puisque c'est celui qui introduit le fameux algorithme dit LLL: "Factoring polynomials with rational coefficients" A.K. Lenstra, H.W. Lenstra, L. Lovacz.
Amicalement,
Aurel
Effectivement, c'est vachement important de le signaler. Et de ce point de vue $\Z[X]$ et $\Q[X]$, c'est pas pareil because le contenu et les ivnversibles.
[color=#000000]> ZX<X> := PolynomialRing(IntegerRing()) ; > QX<X> := PolynomialRing(RationalField()) ; > > a := Random(10^40,10^50) * Random(10^30,10^40) ; > a ; 599114521930449943975613722043228234275686349272955594351172162104044316403396783375009009 > > time F, c := Factorization(QX!a) ; Time: 0.000 > F ; [] > c ; 599114521930449943975613722043228234275686349272955594351172162104044316403396783375009009 > > time F, c := Factorization(ZX!a) ; Time: 3.830 > F ; [ <29, 1>, <113, 1>, <181, 1>, <29551433, 1>, <26106151937, 1>, <1488444174129365863, 1>, <401247740670978548267, 1>, <2192240885261696100348554077, 1> ] > c ; 1 [/color]Un post uniquement pour dire cela ? C'est pas mon genre. Tiens je vais parler des polynômes de Swinnerton - Dyer que tout ``factoriseur'' de polynômes doit connaitre. Mignotte en parle dans son livre page 339 (exercice 8). Il s'agit pour $n$ premiers distincts $p_1, \cdots, p_n$ du polynôme minimal sur $\Q$ de $\sqrt {p_1} + \cdots + \sqrt {p_n}$ i.e. du polynôme de degré $2^n$ :
$$
F = \prod (X - (\pm \sqrt {p_1} \pm \cdots \pm \sqrt{p_n}))
$$C'est un polynôme unitaire irréductible qui est méchant car, la première étape de factorisation (ou irréductibilité) passe par la factorisation modulo $p$ pour un certain premier $p$ ($p$ n'est pas l'un des $p_i$). Or pour n'importe quel premier $p$, ce polynôme admet une racine dans $\F_{p^2}$ si bien que $F$ est, sur $\F_p$, produit d'irréductibles de degré 1 ou 2. Pas question de tester l'irréductibilité de $F$ via un test modulo $p$.
Tout système de calcul formel est capable de calculer un tel polynôme. Si on n'a pas les moyens, on peut toujours utiliser la somme tensorielle des polynômes unitaires qui est l'opération $\oplus$ défini à l'aide du résultant
$$
P \oplus Q = \Res_Y(P(X), Q(X-Y))
$$Si on a quelque part $P(X) = \prod(X-x_i)$ et $Q = \prod_j (X - y_j)$, alors $P \oplus Q = \prod_{i,j} (X - (x_i + y_j))$. Pour quelque part, quand on travaille avec un anneau commutatif à la base, on peut prendre l'algèbre de décomposition universelle de $PQ$.
Exercice : $\oplus$ est commutative, associative, d'élément neutre $X$ si $X$ est le nom de l'indéterminée cette semaine.
Il se trouve que j'ai sous la main $\oplus$ (a deux opérandes) que je vais enchaîner :
$$
(X^2 - p_1) \oplus \cdots \oplus (X^2 - p_n)
$$ On reconnait bien le polynôme minimal de $\sqrt 2 + \sqrt 3$ sur $\Q$. Et en passant, on voit que le nom de l'indéterminée cette semaine n'est pas clair : $X$ versus $T$.
J'en viens au fait avec les $n=8$ premiers nombres premiers $p_i$. Polynôme de degré $2^8$ donc avec des coefficients assez gros Cela a fait chauffer ma machine. C'était ma minute (hum) polynômes de Swinnerton-Dier
Plus qu'imprudent, c'était même faux d'après la déclaration d'aurelpage (la factorisation des entiers n'est pas connue comme polynomiale et elle est même "espérée" difficile, puisque fonde RSA.
Ton exercice sur la somme tensorielle découle directement de la formule $P \oplus Q = \prod_{i,j} (X - (x_i + y_j))$ qui est classique.
En tout cas, tu fais jouer à fond l'associativité dans ton code.
Et 7s pour s'assurer que $\sqrt{p_1}+\cdots+\sqrt{p_8}$ est un élément primitif de $\Q\subset\Q(\sqrt{p_1},\ldots,\sqrt{p_8})$, c'est pas mal !
Tiens cela m'a donné une idée. Comme il fait froid ici, je vais refaire chauffer ma machine en fournissant non pas des premiers distincts mais en y insérant $\sqrt {p_i}, \sqrt {p_j}, \sqrt{p_ip_j}$ et en demandant cette fois la factorisation. Degré $2^9$. Et sans facteur carré, comme je le voulais. On voit que ma fonction TensorialSum n'est pas des plus efficaces.
Coefficients pas petits. Et tout cela pour se chauffer les mains. Note : la factorisation retournée est une liste $<F_1, e_1>$, $<F_2, e_2>$ ..etc.. avec la signification $F = F_1^{e_1} F_1^{e_2} \cdots$. Mais ici, tous les $e_i$ sont égaux à 1. PS : Swinnerton-Dyer (que parfois j'orthographie mal), c'est celui de BSD. Et ce n'est pas la page 339 de Mignotte mais la page 337.
Pour trouver le polynôme minimal d'un nombre algébrique, quel algorithme est le plus couramment utilisé ?
De mon côté, j'utilise Gröbner depuis que toi et GaBuZoMeu m'avez montré ce trick.
Je ne sais pas répondre à ta question (algorithme le plus utilisé pour le polynôme minimal). Je ne sais pas tout et cela dépend du contexte. A vrai dire, quand j'ai fabriqué mon truc, je n'avais pas tant réfléchi que cela. C'était juste le coup de factoriser, histoire d'être dans le thème du fil et ne pas me contenter d'un test d'irréductibilité.
Du coup, tu me forces à réfléchir (un peu) et je reprends le contexte. Cela veut dire quoi ce charabia ? Que $F$ est le polynôme caractéristique d'une certaine somme dans le produit tensoriel de 9 extensions quadratiques de $\Q$. Produit tensoriel que j'écris comme cela :
$$
\Q[x_1, y_1, z_1, \cdots] = {\Q[X_1,Y_1,Z_1,\ X_2,Y_2,Z_2,\ X_3,Y_3,Z_3] \over
\langle X_1^2 - 2, Y_1^2 - 3, Z_1^2 - 2.3,\ X_2^2 - 5, Y_2^2 - 7, Z_2^2 - 5.7\, \cdots \rangle}
$$Il faut penser à $x_1 = \sqrt {2}$, $x_2 = \sqrt {3}$, $x_3 = \sqrt {2\times 3}$ ...etc.. même si cela n'a pas trop de sens car le produit tensoriel ci-dessus (qui n'est pas un corps en passant) n'est pas ordonné. Je veux dire que la glace est mince entre $\sqrt {2}$ et $-\sqrt {2}$.
Et $F$ est le polynôme caractéristique de $x_1 + y_1 + z_1 + \cdots$. De degré égal au degré de cette $\Q$-algèbre, à savoir $2^9$.
Et ce que l'on a vu c'est que $F = F_1 F_2 \cdots F_8$ où les $F_i$ sont irréductibles sur $\Q$. Bien entendu, ces 8 polynômes, chacun de degré $2^6 = 64$, sont les polynômes minimaux des 8 éléments suivants (cette fois je mets des racines carrées pour faire joli)
$$
(\sqrt 2 + \sqrt 3 \pm \sqrt {2.3}) \ +\ (\sqrt 5 + \sqrt 7 \pm \sqrt {5.7}) \ +\ (\sqrt {11} + \sqrt {13} \pm \sqrt {11.13})
\qquad\qquad\qquad 2\times 2 \times 2 = 8
$$Comme c'est pas moi qui paye, je vais changer de catégories : corps de nombres $\Q(\sqrt 2, \sqrt 3, \sqrt 5, \sqrt 7, \sqrt {11}, \sqrt {13})$ au lieu de $\Q$-algèbres. Tu vois le temps de calcul. Et donc je ne vais pas me gêner à calculer les 8 polynômes minimaux vu que cela coûte que dalle. Par précaution, vaut mieux vérifier que leur produit est $F$, cela ne mange pas de pain.
[color=#000000]> time Ffactors := [MinimalPolynomial(r2+r3+sign1*r2*r3 + r5+r7+sign2*r5*r7 + r11+r13+sign3*r11*r13) : sign1, sign2, sign3 in {-1,1}] ; Time: 0.600 > time F eq &*Ffactors ; true Time: 0.050 [/color]Ok, cela ne répond pas à ta question mais c'est ma réponse.Je collecte depuis un certain temps des documents (dont certaines de tes notes !) sur Galois effectif.
Je pense qu'on parle dans au moins l'un d'eux de ce que j'ai évoqué sur les polynômes minimaux.
Je regarderai à mon retour de vacances.