We describe the functions for multivariate polynomial factorization and associated computations. These are available only for a restricted range of coefficient rings.

Subsections

• Factorization and Irreducibility

Given a polynomial f in P=R[x_1, ..., x_n], this function returns:

• A factorization sequence Q, that is, a sequence of pairs consisting of an irreducible polynomial q_i in P (the factor) and a positive integer k_i (the multiplicity);
• A unit u of R

such that f=u.prod_i q_i^(k_i). The unit u will be chosen in an appropriate way; over a field it will be such that q=prod_i q_i^(k_i) is monic, and for R = Z it will equal the sign of the leading coefficient of f.

The coefficient ring R must be one of the following: the ring of integers Z, the field of rationals Q, a finite field, an algebraic number field, or a rational function field over one of those.

Return the squarefree factorization of the multivariate polynomial f as a sequence of tuples of length 2, each consisting of a (not necessarily irreducible) factor and an integer indicating the multiplicity. The factors do not contain the square of any polynomial of degree greater than 0. The allowable coefficient rings are the same as those allowable for the function Factorization.

Given a multivariate polynomial f over a ring R, this function returns true if and only if f is irreducible over R. The allowable coefficient rings are the same as those allowable for the function Factorization.

> P<x, y, z> := PolynomialRing(IntegerRing(), 3);
> f := &*[x^i+y^j+z^k: i,j,k in [1..2]];
> #Terms(f);
461
> TotalDegree(f);
15
> time Factorization(f);
[
    <x + y + z, 1>,
    <x + y + z^2, 1>,
    <x + y^2 + z, 1>,
    <x + y^2 + z^2, 1>,
    <x^2 + y + z, 1>,
    <x^2 + y + z^2, 1>,
    <x^2 + y^2 + z, 1>,
    <x^2 + y^2 + z^2, 1>
]
Time: 2.000

> // Create polynomial ring over R of rank n
> PRing := function(R, n)
>     P := PolynomialRing(R, n);
>     AssignNames( P, ["x" cat IntegerToString(i): i in [1..n]]);
>     return P;
> end function;
>
> // Create Vandermonde matrix of rank n
> Vandermonde := function(n)
>     P := PRing(IntegerRing(), n);
>     return MatrixRing(P, n) ! [P.i^(j - 1): i, j in [1 .. n]];
> end function;
>
> V := Vandermonde(6);
> V;
[   1   x1 x1^2 x1^3 x1^4 x1^5]
[   1   x2 x2^2 x2^3 x2^4 x2^5]
[   1   x3 x3^2 x3^3 x3^4 x3^5]
[   1   x4 x4^2 x4^3 x4^4 x4^5]
[   1   x5 x5^2 x5^3 x5^4 x5^5]
[   1   x6 x6^2 x6^3 x6^4 x6^5]
> D := Determinant(V);
> #Terms(D);
720
> TotalDegree(D);
15
> time Factorization(D);
[
    <x5 - x6, 1>,
    <x4 - x6, 1>,
    <x4 - x5, 1>,
    <x3 - x6, 1>,
    <x3 - x5, 1>,
    <x3 - x4, 1>,
    <x2 - x6, 1>,
    <x2 - x5, 1>,
    <x2 - x4, 1>,
    <x2 - x3, 1>,
    <x1 - x6, 1>,
    <x1 - x5, 1>,
    <x1 - x4, 1>,
    <x1 - x3, 1>,
    <x1 - x2, 1>
]
Time: 0.920

> P<a, b, c> := PolynomialRing(RationalField(), 3);
> A2 := 1/16 * (4*a^2*b^2 - (a^2 + b^2 - c^2)^2);
> A2;
-1/16*a^4 + 1/8*a^2*b^2 + 1/8*a^2*c^2 - 1/16*b^4 + 1/8*b^2*c^2 - 1/16*c^4
> F, u := Factorization(A2);
> F;
[
    <a - b - c, 1>,
    <a - b + c, 1>,
    <a + b - c, 1>,
    <a + b + c, 1>
]
> u;
-1/16

> Frob := function(G)
>     n := #G;
>     I := {@ g: g in G @};
>     P := PolynomialRing(GF(2), n);
>     AssignNames( P, [CodeToString(96 + i): i in [1 .. n]]);
>     M := MatrixRing(P, n);
>     return M ! &cat[
>         [P.Index(I, I[i] * I[j]): j in [1 .. n]]: i in [1 .. n]
>     ];
> end function;
> A := Frob(Sym(3));
> A;
[a b c d e f]
[b c a f d e]
[c a b e f d]
[d e f a b c]
[e f d c a b]
[f d e b c a]
> Determinant(A);
a^6 + a^4*d^2 + a^4*e^2 + a^4*f^2 + a^2*b^2*c^2 + 
    a^2*b^2*d^2 + a^2*b^2*e^2 + a^2*b^2*f^2 + a^2*c^2*d^2 + 
    a^2*c^2*e^2 + a^2*c^2*f^2 + a^2*d^4 + a^2*d^2*e^2 + 
    a^2*d^2*f^2 + a^2*e^4 + a^2*e^2*f^2 + a^2*f^4 + b^6 + 
    b^4*d^2 + b^4*e^2 + b^4*f^2 + b^2*c^2*d^2 + b^2*c^2*e^2 
    + b^2*c^2*f^2 + b^2*d^4 + b^2*d^2*e^2 + b^2*d^2*f^2 + 
    b^2*e^4 + b^2*e^2*f^2 + b^2*f^4 + c^6 + c^4*d^2 + 
    c^4*e^2 + c^4*f^2 + c^2*d^4 + c^2*d^2*e^2 + c^2*d^2*f^2 
    + c^2*e^4 + c^2*e^2*f^2 + c^2*f^4 + d^6 + d^2*e^2*f^2 + 
    e^6 + f^6
> Factorization(Determinant(A));
[
    <a + b + c + d + e + f, 2>,
    <a^2 + a*b + a*c + b^2 + b*c + c^2 + d^2 + d*e + d*f + 
        e^2 + e*f + f^2, 2>
]