Décomposer les polynômes

12

Étant donné un polynôme intégral de degré strictement supérieur à un, le décomposer complètement en une composition de polynômes intégraux de degré strictement supérieur à un.

Détails

  • Un polynôme intégral est un polynôme avec uniquement des entiers comme coefficients.
  • Étant donné deux polynômes pet qla composition est définie par (p∘q)(x):=p(q(x)).
  • La décomposition d'un polynôme intégral pest une séquence ordonnée finie de polynômes intégraux q1,q2,...,qnoù deg qi > 1pour tous 1 ≤ i ≤ net p(x) = q1(q2(...qn(x)...)), et tous qine sont plus décomposables. La décomposition n'est pas nécessairement unique.
  • Vous pouvez par exemple utiliser des listes de coefficients ou des types polynomiaux intégrés comme entrée et sortie.
  • Notez que de nombreuses commandes internes pour cette tâche décomposent en fait les polynômes sur un champ donné et pas nécessairement des entiers, alors que ce défi nécessite un polynôme entier de décomposition. (Certains polynômes entiers peuvent admettre une décomposition en polynômes entiers ainsi qu'une décomposition contenant des polynômes rationnels.)

Exemples

x^2 + 1
[x^2 + 1] (all polynomials of degree 2 or less are not decomposable)
x^6 - 6x^5 + 15x^4 - 20x^3 + 15x^2 - 6 x - 1
[x^3 - 2, x^2 - 2x + 1]
x^4 - 8x^3 + 18x^2 - 8x + 2 
[x^2 + 1, x^2 - 4x + 1]
x^6 + x^2 + 1
[x^3 + x + 1, x^2]
x^6
[x^2, x^3]
x^8 + 4x^6 + 6x^4 + 4x^2 + 4 = (x^2 + 1)^4 + 3
[x^2 + 3, x^2, x^2 + 1]
x^6 + 6x^4 + x^3 + 9x^2 + 3x - 5
[x^2 + x - 5, x^3 + 3*x], [x^2 + 5*x + 1, x^3 + 3*x - 2]

Utilisez Maxima pour générer des exemples: essayez-le en ligne!

Quelques algorithmes de décomposition peuvent être trouvés ici et ici .

code-golf math number abstract-algebra polynomials flawr
la source

Réponses:

4

Pari / GP , 84 octets

f(p)=[if(q'',[f(q),r],p)|r<-x*divisors(p\x),r''&&p==subst(q=substpol(p,r,x),x,r)][1]

Basé sur l'algorithme décrit ici .

Essayez-le en ligne!

alephalpha
la source
1
Vérifiez-vous (ou filtrez-vous) si vous obtenez réellement une décomposition en polynômes intégraux? (Je demande parce que les algorithmes dans l'article lié décrivent la factorisation sur un certain champ, et je ne connais aucun Pari / GP.)
flawr
1
@flawr J'utilise le deuxième algorithme de l'article, qui renvoie toujours des polynômes intégraux lorsque l'entrée est intégrale. En fait, la divisorsfonction dans Pari / GP renvoie toujours des polynômes primitifs lorsqu'elle prend un polynôme intégral. On peut prouver que si p=q∘r, où pet rfont partie intégrante, et rest primitif avec r(0)=0, alors il qdoit aussi être intégral. Ici p, q, rcorrespondent à f, g, hdans le document.
alephalpha
2

Wolfram Language (Mathematica) , 29 octets

Decompose[#/.x->x+a,x]/.a->0&

Essayez-le en ligne!

J'ai l'exemple mis en place ici pour composer un polynôme aléatoire à partir de quadratiques aléatoires (ou moins), le développer, puis essayer de le décomposer.

Il est nécessaire de compliquer le polynôme avec la variable fictive (a) car la fonction intégrée ne tentera pas de décomposer un monôme.

Je remarque que la réponse a souvent des coefficients beaucoup plus importants que dans la composition d'origine, mais ce sont en effet toujours des entiers.

Kelly Lowder
la source
Où avez-vous trouvé les informations qui Decompose[]renverront toujours des polynômes intégraux (s'ils sont alimentés par des polynômes entiers)? Lors d'une discussion récente dans le chat, nous n'avons rien trouvé à ce sujet.
flawr
1
Faites-le Options@Decomposeet il vous le dira {Modulus->0}. Maintenant, recherchez Modulus et vous verrez "Le paramètre Modulus-> 0 spécifie l'anneau complet [DoubleStruckCapitalZ] d'entiers."
Kelly Lowder
Ah c'est bien, merci d'avoir élaboré!
flawr