Skip to main content
We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.
Code Golf

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

Required fields*

Decompose Polynomials

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.

Answer*

Draft saved
Draft discarded
Cancel
2
  • 1
    \$\begingroup\$ Do you check (or filter out) whether you actually get a decomposition into integral polynomials? (I'm asking because the algorithms in the linked paper describe the factorization over some field, and I don't know any Pari/GP.) \$\endgroup\$ Commented Mar 12, 2018 at 12:10
  • 1
    \$\begingroup\$ @flawr I'm using the second algorithm in the paper, which always returns integral polynomials when the input is integral. In fact, the divisors function in Pari/GP always returns primitive polynomials when it takes an integral polynomial. It can be proved that if p=q∘r, where p and r are integral, and r is primitive with r(0)=0, then q must also be integral. Here p, q, r correspond to f, g, h in the paper. \$\endgroup\$ Commented Mar 12, 2018 at 14:26

AltStyle によって変換されたページ (->オリジナル) /