Membusuk Polinomial

12

Diberikan polinomial tak terpisahkan dari derajat yang benar-benar lebih besar dari satu, sepenuhnya terurai menjadi komposisi polinomial tak terpisahkan dari tingkat yang lebih besar dari satu.

Detail

  • Sebuah polinomial terpisahkan adalah polinomial dengan hanya bilangan bulat sebagai koefisien.
  • Mengingat dua polinomial pdan qyang komposisi didefinisikan oleh (p∘q)(x):=p(q(x)).
  • The dekomposisi dari polinomial terpisahkan padalah urutan memerintahkan terbatas polinomial terpisahkan q1,q2,...,qnmana deg qi > 1untuk semua 1 ≤ i ≤ ndan p(x) = q1(q2(...qn(x)...)), dan semua qiyang tidak terurai lebih lanjut. Dekomposisi tidak harus unik.
  • Anda dapat menggunakan daftar koefisien misalnya atau dibangun dalam tipe polinomial sebagai input dan output.
  • Perhatikan bahwa banyak bawaan untuk tugas ini sebenarnya menguraikan polinomial pada bidang yang diberikan dan tidak harus bilangan bulat, sementara tantangan ini membutuhkan polinomial bilangan bulat dekomposisi. (Beberapa polinomial integer mungkin mengakui dekomposisi menjadi polinomial integer serta dekomposisi yang mengandung polinomial rasional.)

Contohnya

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]

Gunakan Maxima untuk menghasilkan contoh: Coba online!

Beberapa algoritma penguraian dapat ditemukan di sini dan di sini .

code-golf math number abstract-algebra polynomials cacat
sumber

Jawaban:

4

Pari / GP , 84 byte

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

Berdasarkan algoritma yang dijelaskan di sini .

Cobalah online!

alephalpha
sumber
1
Apakah Anda memeriksa (atau menyaring) apakah Anda benar-benar mendapatkan dekomposisi menjadi polinomial integral? (Saya bertanya karena algoritma dalam makalah yang ditautkan menggambarkan faktorisasi pada beberapa bidang, dan saya tidak tahu Pari / GP.)
flawr
1
@ flawr Saya menggunakan algoritma kedua di kertas, yang selalu mengembalikan polinomial integral ketika input integral. Bahkan, divisorsfungsi dalam Pari / GP selalu mengembalikan polinomial primitif ketika mengambil polinomial integral. Dapat dibuktikan bahwa jika p=q∘r, di mana pdan rintegral, dan rprimitif dengan r(0)=0, maka qjuga harus integral. Di sini p, q, rsesuai dengan f, g, hdi koran.
alephalpha
2

Bahasa Wolfram (Mathematica) , 29 byte

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

Cobalah online!

Saya memiliki contoh yang diatur di sini untuk menyusun polinomial acak dari kuadrat acak (atau kurang), memperluasnya, dan kemudian mencoba menguraikannya.

Ini perlu untuk menyulitkan polinomial dengan variabel dummy (a) karena built-in tidak akan mencoba untuk menguraikan monomial.

Saya perhatikan bahwa jawabannya sering memiliki koefisien yang jauh lebih besar daripada di komposisi aslinya, tetapi mereka memang selalu bilangan bulat.

Kelly Lowder
sumber
Di mana Anda menemukan informasi yang Decompose[]akan selalu mengembalikan polinomial integral (jika diumpankan dengan polinomial integer)? Ketika membahas dalam obrolan baru-baru ini kami tidak dapat menemukan apa pun tentang itu.
flawr
1
Lakukan Options@Decomposedan itu akan memberi tahu Anda {Modulus->0}. Sekarang lihat Modulus dan Anda akan melihat "Pengaturan Modulus-> 0 menentukan cincin penuh [DoubleStruckCapitalZ] dari bilangan bulat."
Kelly Lowder
Ah itu bagus, terima kasih sudah menjelaskan!
flawr