Descomponer polinomios

12

Dado un polinomio integral de grado estrictamente mayor que uno, descomponerlo completamente en una composición de polinomios integrales de grado estrictamente mayor que uno.

Detalles

  • Un polinomio integral es un polinomio con solo enteros como coeficientes.
  • Dados dos polinomios py qla composición se define por (p∘q)(x):=p(q(x)).
  • La descomposición de un polinomio integral pes una secuencia ordenada finita de polinomios integrales q1,q2,...,qndonde deg qi > 1for all 1 ≤ i ≤ nand p(x) = q1(q2(...qn(x)...)), y todos qino son más descomponibles. La descomposición no es necesariamente única.
  • Puede usar, por ejemplo, listas de coeficientes o tipos de polinomios incorporados como entrada y salida.
  • Tenga en cuenta que muchas de las funciones integradas para esta tarea realmente descomponen los polinomios sobre un campo determinado y no necesariamente enteros, mientras que este desafío requiere una descomposición de polinomios enteros. (Algunos polinomios enteros pueden admitir la descomposición en polinomios enteros, así como la descomposición que contiene polinomios racionales).

Ejemplos

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]

Use Maxima para generar ejemplos: ¡ Pruébelo en línea!

Algunos algoritmos de descomposición se pueden encontrar aquí y aquí .

code-golf math number abstract-algebra polynomials falla
fuente

Respuestas:

4

Pari / GP , 84 bytes

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

Basado en el algoritmo descrito aquí .

Pruébalo en línea!

alephalpha
fuente
1
¿Comprueba (o filtra) si realmente obtiene una descomposición en polinomios integrales? (Lo digo porque los algoritmos en el documento vinculado describen la factorización sobre algún campo, y yo no conozco a ningún Pari / GP.)
flawr
1
@flawr Estoy usando el segundo algoritmo en el documento, que siempre devuelve polinomios integrales cuando la entrada es integral. De hecho, la divisorsfunción en Pari / GP siempre devuelve polinomios primitivos cuando toma un polinomio integral. Se puede demostrar que si p=q∘r, donde py rson integrales, y res primitivo con r(0)=0, entonces qtambién debe ser integral. Aquí p, q, rcorresponden a f, g, hen el papel.
alephalpha
2

Wolfram Language (Mathematica) , 29 bytes

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

Pruébalo en línea!

Tengo el ejemplo configurado aquí para componer un polinomio aleatorio a partir de cuadráticos aleatorios (o menos), expandirlo y luego tratar de descomponerlo.

Es necesario complicar el polinomio con la variable ficticia (a) ya que el incorporado no intentará descomponer un monomio.

Noto que la respuesta a menudo tiene coeficientes mucho más grandes que en la composición original, pero de hecho siempre son enteros.

Kelly Lowder
fuente
¿Dónde encontró la información que Decompose[]siempre devolverá polinomios integrales (si se alimenta con polinomios enteros)? Cuando discutimos en el chat recientemente, no pudimos encontrar nada al respecto.
flawr
1
Hazlo Options@Decomposey te lo dirá {Modulus->0}. Ahora busque Modulus y verá "La configuración Modulus-> 0 especifica el anillo completo [DoubleStruckCapitalZ] de enteros".
Kelly Lowder
Ah, eso es bueno, gracias por elaborar!
flawr