Finding Radical Ideals

Question

Sandbox

Finding radicals of arbitrary ideals in rings is hard! However, it's a doable task in polynomial rings, since they are Noetherian (all ideals are finitely generated)

Background

A quick introduction to radical ideals

A ring is a set, paired with two binary operations + and * such that 0 is a additive identity, 1 is a multiplicative identity, addition is commutative, every element has an additive inverse, and multiplication distributes over addition. For a more proper introduction, see Wikipedia. In this challenge, we'll be dealing with rings of polynomials over the complex numbers (for example, C[x,y,z]), so multiplication will also be commutative.

An ideal is a non-empty set closed under addition that contains additive inverses for all elements, and such that for any r in the ring and i in the ideal, r*i is in the ideal.

Given some polynomials p1,...,pn, the ideal generated by the polynomials is the set of all polynomials p such that there exists polynomials q1,...,qn such that p = p1q1+p2q2+...+pnqn.

In other words, the ideal generated by a set of polynomials is the smallest ideal containing the set.

Given ideal I of R, the radical ideal of I, or root I, √I, is the ideal of elements r in R such that there is some natural n, r^n is in I.

code-golf challenge:

Given an ideal generated by polynomials in any number of variables in the complex numbers, you need to return a set of polynomials that generate the radical ideal.

Important Notes:

• While the polynomials all will belong to the space of complex coefficients, I'll only give you inputs of polynomials with integer coefficients.

• Variables will always be single letters.

• The output must be algebraically independent (there is no non-zero linear combination of the polynomials that sums to 0). The input will be algebraically independent.

• Obviously, the output is non-unique.

Hints

A less algebraic way of thinking about radical ideals is: given that the input polynomials all evaluate to 0, what is the set of all polynomials we know that evaluate to 0. That set is the radical ideal.

Another nice characterization of the radical ideal is the intersection of all prime ideals containing the original generators.

There are no good known ways to find radicals in infinite fields, like the complex numbers. However, there are several algorithms that have reasonable average case times (many of which are listed here)

Singular has all of these algorithms implemented, if you want to experiment before building your own.

Of course, this is code golf, so inefficient solutions are permitted.

Input/Output

I/O should be pretty flexible. Possible forms of input/output:

Ideal: (x^2y-z^3, 2xy^2-2w^3, xy-zw)

I/O 0: "x^2y-z^3, 2xy^2-2w^3, xy-zw"

I/O 1: "x2y-z3,2xy2-2w3,xy-zw"

I/O 2: ["x2y-z3","2xy2-2w3","xy-zw"]

I/O 3: [[[1,2,1,0,0],[-1,0,0,3,0]],[[2,1,2,0,0],[-2,0,0,0,3]],[[1,1,1,0,0],[-1,0,0,1,1]]]

If there's some other more convenient I/O, let me know.

Test Cases

As I said earlier, these are not the only valid outputs for these inputs.

x^3 → x

2x^4y^2z^3 → xyz

xy-z^2, x-y → x-y, x^2-z^2

x^2, xz^2-x, y-z → x, y-z

y^2+z, yz → y, z

x^2+y^2-1, w^2+z^2-1, xw+yz, xz-yw-1 → y+w, x-z, y^2+z^2-1

xy, (x-y)z → xy, yz, xz

xy, x-yz → x, yz

x^2y-z^3, 2xy^2-2w^3, xy-zw → z^2-xw, yz-w^2, xy-zw

Explained Examples

Upon request in the comments, I'll work a few examples out:

Example 1: 2x^4y^2z^3 → xyz

Note that (xyz)^4 = x^4y^4z^4, while 0.5*y^2z*(2x^4y^2z^3)=x^4y^4z^4, so this tells us that xyz is in the radical of 2x^4y^2z^3. Now, consider some polynomial p with a term that doesn't have x as a factor. Then, p^n will also have such a term, so it can't be in the ideal generated by 2x^4y^2z^3. So, every polynomial in the radical ideal has x as a divisor, and by symmetry, has y and z as divisors, so has xyz as a divisor.

Example 2: x^2, xz^2-x, y-z → x, y-z

Note that x^2 is in the ideal, so x is in the radical ideal. So, x*(z^2-1)=xz^2-x will be in the radical ideal since it is a multiple of x. Clearly, x and y-z are independent, and since they are terms of degree 1, they generate the radical ideal.