Given an integral polynomial of degree strictly greater than one, completely decompose it into a composition of integral polynomials of degree strictly greater than one.
Details
- An integral polynomial is a polynomial with only integers as coefficients.
- Given two polynomials
p and q the composition is defined by (p∘q)(x):=p(q(x)).
- The decomposition of an integral polynomial
p is a finite ordered sequence of integral polynomials q1,q2,...,qn where deg qi > 1 for all 1 ≤ i ≤ n and p(x) = q1(q2(...qn(x)...)), and all qi are not further decomposable. The decomposition is not necessarily unique.
- You can use e.g. lists of coefficients or built in polynomial types as input and output.
- Note that many builtins for this task actually decompose the polynomials over a given field and not necessarily integers, while this challenge requires a decomposition integer polynomials. (Some integer polynomials might admit decomposition into integer polynomials as well as decomposition that contain rational polynomials.)
Examples
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 for generating examples: Try it online!
Some decomposition algorithms can be found here and here.
Decompose[]will always return integral polynomials (if fed with integer polynomials)? When discussing in chat recently we could not find anything about that. \$\endgroup\$Options@Decomposeand it will tell you{Modulus->0}. Now look up Modulus and you'll see "The setting Modulus->0 specifies the full ring [DoubleStruckCapitalZ] of integers. " \$\endgroup\$