Decompor polinômios

12

Dado um polinômio integral de grau estritamente maior que um, decomponha-o completamente em uma composição de polinômios integrais de grau estritamente maiores que um.

Detalhes

  • Um polinômio integral é um polinômio com apenas números inteiros como coeficientes.
  • Dados dois polinômios pe qa composição é definida por (p∘q)(x):=p(q(x)).
  • A decomposição de um polinômio integral pé uma sequência ordenada finita de polinômios integrais, q1,q2,...,qnonde deg qi > 1para todos 1 ≤ i ≤ ne p(x) = q1(q2(...qn(x)...)), e todos, qinão são mais decompostos. A decomposição não é necessariamente única.
  • Você pode usar, por exemplo, listas de coeficientes ou tipos polinomiais incorporados como entrada e saída.
  • Observe que muitos componentes internos para esta tarefa realmente decompõem os polinômios em um determinado campo e não necessariamente números inteiros, enquanto esse desafio requer polinômios inteiros em decomposição. (Alguns polinômios inteiros podem admitir decomposição em polinômios inteiros, bem como decomposição que contém polinômios racionais.)

Exemplos

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 o Maxima para gerar exemplos: Experimente online!

Alguns algoritmos de decomposição podem ser encontrados aqui e aqui .

code-golf math number abstract-algebra polynomials flawr
fonte

Respostas:

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]

Com base no algoritmo descrito aqui .

Experimente online!

alefalpha
fonte
1
Você verifica (ou filtra) se realmente se decompõe em polinômios integrais? (Estou perguntando porque os algoritmos do papel ligado descrever a fatoração sobre algum campo, e eu não conheço nenhum Pari / GP.)
flawr
1
@ flawr Estou usando o segundo algoritmo no papel, que sempre retorna polinômios integrais quando a entrada é integral. De fato, a divisorsfunção em Pari / GP sempre retorna polinômios primitivos quando recebe um polinômio integral. Pode-se provar que p=q∘r, se , onde pe rsão integrais e rsão primitivos r(0)=0, qtambém devem ser integrais. Aqui p, q, rcorrespondem a f, g, hno papel.
alephalpha
2

Wolfram Language (Mathematica) , 29 bytes

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

Experimente online!

Eu tenho o exemplo configurado aqui para compor um polinômio aleatório a partir de quadráticos aleatórios (ou menos), expandi-lo e tentar decompô-lo.

É necessário complicar o polinômio com a variável dummy (a), pois o built-in não tentará decompor um monômio.

Percebo que a resposta geralmente tem coeficientes muito maiores do que na composição original, mas eles são sempre sempre números inteiros.

Kelly Lowder
fonte
Onde você encontrou a informação que Decompose[]sempre retornará polinômios integrais (se alimentados com polinômios inteiros)? Ao discutir no chat recentemente, não conseguimos encontrar nada sobre isso.
flawr
1
Faça Options@Decomposee isso lhe dirá {Modulus->0}. Agora, procure Modulus e você verá "A configuração Modulus-> 0 especifica o anel completo [DoubleStruckCapitalZ] de números inteiros."
Kelly Lowder
Ah, isso é legal, obrigado por elaborar!
flawr