Conquering Inseparability

Primary Decomposition and Multivariate Factorization over Algebraic Function Fields of Positive Characteristic

By Allan Steel

This page demonstrates Magma's ability to factor multivariate polynomials over algebraic function fields with arbitrary numbers of algebraic and transcendental generators, and in small characteristic. (This involves difficult inseparable extensions.) Timings are for an Opteron 246 (2GHz).

Characteristic 2

We factor polynomials over the function field K = GF(2)(t,u)[a,b,c]/<a^2 + tb, b^4 + b^2 + c, c^2 + tu>. 
> p := 2;
> F<t,u> := FunctionField(GF(p), 2);
> F;
Multivariate rational function field of rank 2 over GF(2)
Variables: t, u
> K<a,b,c> := AffineAlgebra<F,a,b,c| a^2 + t*b, b^4 + b^2 + c, c^2 + t*u>;
> K;
Affine Algebra of rank 3 over Multivariate rational function field of rank 2 
    over GF(2)
Lexicographical Order
Variables: a, b, c
Quotient relations:
[
    a^2 + t*b,
    b^4 + b^2 + c,
    c^2 + t*u
]
> IsField(K);
true
> P<x,y,z> := PolynomialRing(K, 3);
Some simple factorizations first, showing how the relations of the field cause some polynomials to factor. 
> Factorization(x^2 + t);
[
    <x^2 + t, 1>
]
> Factorization(x^2 + t*b);
[
    <x + a, 2>
]
> Factorization(x^2 + t*u);  
[
    <x + c, 2>
]
> Factorization(x^2 + x + 1);
[
    <x^2 + x + 1, 1>
]
> Factorization(x^2 + x + c);
[
    <x + b^2, 1>,
    <x + b^2 + 1, 1>
]
> Factorization((x^2 + t*b)*(y^4 + y^2 + c));
[
    <y + b, 2>,
    <y + b + 1, 2>,
    <x + a, 2>
]
Now for some much bigger polynomials. 
> f := (x*y+a)^2*(x^2 + a)^2*(x*y*z + a)*(x^2 + t);

> f;
x^9*y^3*z + a*x^8*y^2 + t*x^7*y^3*z + t*b*x^7*y*z + t*a*x^6*y^2 + t*a*b*x^6 + 
    t*b*x^5*y^3*z + t^2*b*x^5*y*z + t*a*b*x^4*y^2 + t^2*a*b*x^4 + 
    t^2*b*x^3*y^3*z + t^2*b^2*x^3*y*z + t^2*a*b*x^2*y^2 + t^2*a*b^2*x^2 + 
    t^3*b^2*x*y*z + t^3*a*b^2

> g := (x*z^3 + t)^2*(x^2 + z + a)^2*(y^2*z + t)^2*(x^2*y + z)^3*
>      (x*z + 1)*((x*y)^4 + t);

> g := (x*z^3 + t)^2*(x^2 + z + a)^2*(y^2*z + t)^2*(x^2*y + z)^3*
>      (x*z + 1)*((x*y)^4 + t*u);

> g;
x^17*y^11*z^9 + t^2*x^17*y^7*z^7 + x^16*y^11*z^8 + t^2*x^16*y^7*z^6 + 
    t^2*x^15*y^11*z^3 + x^15*y^10*z^10 + t^4*x^15*y^7*z + t^2*x^15*y^6*z^8 + 
    t^2*x^14*y^11*z^2 + x^14*y^10*z^9 + t^4*x^14*y^7 + t^2*x^14*y^6*z^7 + 
    x^13*y^11*z^11 + t*b*x^13*y^11*z^9 + t^2*x^13*y^10*z^4 + x^13*y^9*z^11 + 
    (t^2 + t*u)*x^13*y^7*z^9 + t^3*b*x^13*y^7*z^7 + t^4*x^13*y^6*z^2 + 
    t^2*x^13*y^5*z^9 + t^3*u*x^13*y^3*z^7 + x^12*y^11*z^10 + t*b*x^12*y^11*z^8 +
    t^2*x^12*y^10*z^3 + x^12*y^9*z^10 + (t^2 + t*u)*x^12*y^7*z^8 + 
    t^3*b*x^12*y^7*z^6 + t^4*x^12*y^6*z + t^2*x^12*y^5*z^8 + t^3*u*x^12*y^3*z^6 
    + t^2*x^11*y^11*z^5 + t^3*b*x^11*y^11*z^3 + x^11*y^10*z^12 + 
    t*b*x^11*y^10*z^10 + t^2*x^11*y^9*z^5 + x^11*y^8*z^12 + (t^4 + 
    t^3*u)*x^11*y^7*z^3 + t^5*b*x^11*y^7*z + (t^2 + t*u)*x^11*y^6*z^10 + 
    t^3*b*x^11*y^6*z^8 + t^4*x^11*y^5*z^3 + t^2*x^11*y^4*z^10 + t^5*u*x^11*y^3*z
    + t^3*u*x^11*y^2*z^8 + t^2*x^10*y^11*z^4 + t^3*b*x^10*y^11*z^2 + 
    x^10*y^10*z^11 + t*b*x^10*y^10*z^9 + t^2*x^10*y^9*z^4 + x^10*y^8*z^11 + (t^4
    + t^3*u)*x^10*y^7*z^2 + t^5*b*x^10*y^7 + (t^2 + t*u)*x^10*y^6*z^9 + 
    t^3*b*x^10*y^6*z^7 + t^4*x^10*y^5*z^2 + t^2*x^10*y^4*z^9 + t^5*u*x^10*y^3 + 
    t^3*u*x^10*y^2*z^7 + t^2*x^9*y^10*z^6 + t^3*b*x^9*y^10*z^4 + x^9*y^9*z^13 + 
    t*b*x^9*y^9*z^11 + t^2*x^9*y^8*z^6 + t*u*x^9*y^7*z^11 + t^2*u*b*x^9*y^7*z^9 
    + (t^4 + t^3*u)*x^9*y^6*z^4 + t^5*b*x^9*y^6*z^2 + (t^2 + t*u)*x^9*y^5*z^11 +
    t^3*b*x^9*y^5*z^9 + t^4*x^9*y^4*z^4 + t^3*u*x^9*y^3*z^9 + 
    t^4*u*b*x^9*y^3*z^7 + t^5*u*x^9*y^2*z^2 + t^3*u*x^9*y*z^9 + t^2*x^8*y^10*z^5
    + t^3*b*x^8*y^10*z^3 + x^8*y^9*z^12 + t*b*x^8*y^9*z^10 + t^2*x^8*y^8*z^5 + 
    t*u*x^8*y^7*z^10 + t^2*u*b*x^8*y^7*z^8 + (t^4 + t^3*u)*x^8*y^6*z^3 + 
    t^5*b*x^8*y^6*z + (t^2 + t*u)*x^8*y^5*z^10 + t^3*b*x^8*y^5*z^8 + 
    t^4*x^8*y^4*z^3 + t^3*u*x^8*y^3*z^8 + t^4*u*b*x^8*y^3*z^6 + t^5*u*x^8*y^2*z 
    + t^3*u*x^8*y*z^8 + t^2*x^7*y^9*z^7 + t^3*b*x^7*y^9*z^5 + x^7*y^8*z^14 + 
    t*b*x^7*y^8*z^12 + t^3*u*x^7*y^7*z^5 + t^4*u*b*x^7*y^7*z^3 + 
    t*u*x^7*y^6*z^12 + t^2*u*b*x^7*y^6*z^10 + (t^4 + t^3*u)*x^7*y^5*z^5 + 
    t^5*b*x^7*y^5*z^3 + (t^2 + t*u)*x^7*y^4*z^12 + t^3*b*x^7*y^4*z^10 + 
    t^5*u*x^7*y^3*z^3 + t^6*u*b*x^7*y^3*z + t^3*u*x^7*y^2*z^10 + 
    t^4*u*b*x^7*y^2*z^8 + t^5*u*x^7*y*z^3 + t^3*u*x^7*z^10 + t^2*x^6*y^9*z^6 + 
    t^3*b*x^6*y^9*z^4 + x^6*y^8*z^13 + t*b*x^6*y^8*z^11 + t^3*u*x^6*y^7*z^4 + 
    t^4*u*b*x^6*y^7*z^2 + t*u*x^6*y^6*z^11 + t^2*u*b*x^6*y^6*z^9 + (t^4 + 
    t^3*u)*x^6*y^5*z^4 + t^5*b*x^6*y^5*z^2 + (t^2 + t*u)*x^6*y^4*z^11 + 
    t^3*b*x^6*y^4*z^9 + t^5*u*x^6*y^3*z^2 + t^6*u*b*x^6*y^3 + t^3*u*x^6*y^2*z^9 
    + t^4*u*b*x^6*y^2*z^7 + t^5*u*x^6*y*z^2 + t^3*u*x^6*z^9 + t^2*x^5*y^8*z^8 + 
    t^3*b*x^5*y^8*z^6 + t^3*u*x^5*y^6*z^6 + t^4*u*b*x^5*y^6*z^4 + 
    t*u*x^5*y^5*z^13 + t^2*u*b*x^5*y^5*z^11 + (t^4 + t^3*u)*x^5*y^4*z^6 + 
    t^5*b*x^5*y^4*z^4 + t^5*u*x^5*y^2*z^4 + t^6*u*b*x^5*y^2*z^2 + 
    t^3*u*x^5*y*z^11 + t^4*u*b*x^5*y*z^9 + t^5*u*x^5*z^4 + t^2*x^4*y^8*z^7 + 
    t^3*b*x^4*y^8*z^5 + t^3*u*x^4*y^6*z^5 + t^4*u*b*x^4*y^6*z^3 + 
    t*u*x^4*y^5*z^12 + t^2*u*b*x^4*y^5*z^10 + (t^4 + t^3*u)*x^4*y^4*z^5 + 
    t^5*b*x^4*y^4*z^3 + t^5*u*x^4*y^2*z^3 + t^6*u*b*x^4*y^2*z + t^3*u*x^4*y*z^10
    + t^4*u*b*x^4*y*z^8 + t^5*u*x^4*z^3 + t^3*u*x^3*y^5*z^7 + 
    t^4*u*b*x^3*y^5*z^5 + t*u*x^3*y^4*z^14 + t^2*u*b*x^3*y^4*z^12 + 
    t^5*u*x^3*y*z^5 + t^6*u*b*x^3*y*z^3 + t^3*u*x^3*z^12 + t^4*u*b*x^3*z^10 + 
    t^3*u*x^2*y^5*z^6 + t^4*u*b*x^2*y^5*z^4 + t*u*x^2*y^4*z^13 + 
    t^2*u*b*x^2*y^4*z^11 + t^5*u*x^2*y*z^4 + t^6*u*b*x^2*y*z^2 + t^3*u*x^2*z^11 
    + t^4*u*b*x^2*z^9 + t^3*u*x*y^4*z^8 + t^4*u*b*x*y^4*z^6 + t^5*u*x*z^6 + 
    t^6*u*b*x*z^4 + t^3*u*y^4*z^7 + t^4*u*b*y^4*z^5 + t^5*u*z^5 + t^6*u*b*z^3

> time Factorization(f);
[
    <x*y + a, 2>,
    <x*y*z + a, 1>,
    <x^2 + t, 1>,
    <x^2 + a, 2>
]
Time: 0.090
> time Factorization(g);
[
    <y^2*z + t, 2>,
    <x*z + 1, 1>,
    <x^2 + z + a, 2>,
    <x^2*z^6 + t^2, 1>,
    <x^2*y + z, 3>,
    <x^2*y^2 + c, 2>
]
Time: 0.080

> h := f*g;
> Degree(h, x);
26
> Degree(h, y);
14
> Degree(h, z);
15

> h;
x^26*y^14*z^10 + t^2*x^26*y^10*z^8 + x^25*y^14*z^9 + [4089 terms] +
    t^7*u*a*b^3*y^4*z^5 + t^8*u*a*b^2*z^5 + t^9*u*a*b^3*z^3

> time Factorization(h);
[
    <y^2*z + t, 2>,
    <x*z + 1, 1>,
    <x*y*z + a, 1>,
    <x^2 + t, 1>,
    <x^2 + a, 2>,
    <x^2 + z + a, 2>,
    <x^2*z^6 + t^2, 1>,
    <x^2*y + z, 3>,
    <x^2*y^2 + c, 2>,
    <x^2*y^2 + t*b, 1>
]
Time: 0.330

Characteristic 3

> p := 3;
> F<t,u,v> := FunctionField(GF(p), 3);
> K<a,b> := AffineAlgebra<F,a,b| a^3 + b^3 + t*u, b^6 + b^3 + u*v>;  
> IsField(K);
true
> P<x,y,z> := PolynomialRing(K, 3);
> Factorization(x^3 + t);
[
    <x^3 + t, 1>
]
> Factorization(x^3 + t*u);
[
    <x + 2*a + 2*b, 3>
]
> Factorization(x^2 + x + u*v);
[
    <x + b^3 + 1, 1>,
    <x + 2*b^3, 1>
]

> f := (x^2 + x + u*v)^3*(x^3 + t*u)*(y + t*u)^3;
> f;
x^9*y^3 + t^3*u^3*x^9 + (t*u + 1)*x^6*y^3 + (t^4*u^4 + t^3*u^3)*x^6 + (t*u + 
    u^3*v^3)*x^3*y^3 + (t^4*u^4 + t^3*u^6*v^3)*x^3 + t*u^4*v^3*y^3 + t^4*u^7*v^3
> time Factorization(f);  
[
    <y + t*u, 3>,
    <x + b^3 + 1, 3>,
    <x + 2*b^3, 3>,
    <x + 2*a + 2*b, 3>
]
Time: 0.050

> g := (y^2 + y + u*v)^6*(z^3 + t*u)*(y + t*u + 1)^3;
> g;
y^15*z^3 + t*u*y^15 + t^3*u^3*y^12*z^3 + t^4*u^4*y^12 + (2*t^3*u^3 + 
    2*u^3*v^3)*y^9*z^3 + (2*t^4*u^4 + 2*t*u^4*v^3)*y^9 + (2*t^3*u^6*v^3 + 
    t^3*u^3 + u^3*v^3 + 1)*y^6*z^3 + (2*t^4*u^7*v^3 + t^4*u^4 + t*u^4*v^3 + 
    t*u)*y^6 + (2*t^3*u^6*v^3 + u^6*v^6 + 2*u^3*v^3)*y^3*z^3 + (2*t^4*u^7*v^3 + 
    t*u^7*v^6 + 2*t*u^4*v^3)*y^3 + (t^3*u^9*v^6 + u^6*v^6)*z^3 + t^4*u^10*v^6 + 
    t*u^7*v^6
> time Factorization(g);
[
    <z + 2*a + 2*b, 3>,
    <y + t*u + 1, 3>,
    <y + b^3 + 1, 6>,
    <y + 2*b^3, 6>
]
Time: 0.060

> h := f*g;
> h;
x^9*y^18*z^3 + t*u*x^9*y^18 + 2*t^3*u^3*x^9*y^15*z^3 + 2*t^4*u^4*x^9*y^15 + 
    (t^6*u^6 + 2*t^3*u^3 + 2*u^3*v^3)*x^9*y^12*z^3 + (t^7*u^7 + 2*t^4*u^4 + 
    2*t*u^4*v^3)*x^9*y^12 + (2*t^6*u^6 + t^3*u^6*v^3 + t^3*u^3 + u^3*v^3 + 
    1)*x^9*y^9*z^3 + (2*t^7*u^7 + t^4*u^7*v^3 + t^4*u^4 + t*u^4*v^3 + 
    t*u)*x^9*y^9 + (2*t^6*u^9*v^3 + t^6*u^6 + t^3*u^3 + u^6*v^6 + 
    2*u^3*v^3)*x^9*y^6*z^3 + (2*t^7*u^10*v^3 + t^7*u^7 + t^4*u^4 + t*u^7*v^6 + 
    2*t*u^4*v^3)*x^9*y^6 + (2*t^6*u^9*v^3 + 2*t^3*u^9*v^6 + 2*t^3*u^6*v^3 + 
    u^6*v^6)*x^9*y^3*z^3 + (2*t^7*u^10*v^3 + 2*t^4*u^10*v^6 + 2*t^4*u^7*v^3 + 
    t*u^7*v^6)*x^9*y^3 + (t^6*u^12*v^6 + t^3*u^9*v^6)*x^9*z^3 + (t^7*u^13*v^6 + 
    t^4*u^10*v^6)*x^9 + (t*u + 1)*x^6*y^18*z^3 + (t^2*u^2 + t*u)*x^6*y^18 + 
    (2*t^4*u^4 + 2*t^3*u^3)*x^6*y^15*z^3 + (2*t^5*u^5 + 2*t^4*u^4)*x^6*y^15 + 
    (t^7*u^7 + t^6*u^6 + 2*t^4*u^4 + 2*t^3*u^3 + 2*t*u^4*v^3 + 
    2*u^3*v^3)*x^6*y^12*z^3 + (t^8*u^8 + t^7*u^7 + 2*t^5*u^5 + 2*t^4*u^4 + 
    2*t^2*u^5*v^3 + 2*t*u^4*v^3)*x^6*y^12 + (2*t^7*u^7 + 2*t^6*u^6 + t^4*u^7*v^3
    + t^4*u^4 + t^3*u^6*v^3 + t^3*u^3 + t*u^4*v^3 + t*u + u^3*v^3 + 
    1)*x^6*y^9*z^3 + (2*t^8*u^8 + 2*t^7*u^7 + t^5*u^8*v^3 + t^5*u^5 + 
    t^4*u^7*v^3 + t^4*u^4 + t^2*u^5*v^3 + t^2*u^2 + t*u^4*v^3 + t*u)*x^6*y^9 + 
    (2*t^7*u^10*v^3 + t^7*u^7 + 2*t^6*u^9*v^3 + t^6*u^6 + t^4*u^4 + t^3*u^3 + 
    t*u^7*v^6 + 2*t*u^4*v^3 + u^6*v^6 + 2*u^3*v^3)*x^6*y^6*z^3 + (2*t^8*u^11*v^3
    + t^8*u^8 + 2*t^7*u^10*v^3 + t^7*u^7 + t^5*u^5 + t^4*u^4 + t^2*u^8*v^6 + 
    2*t^2*u^5*v^3 + t*u^7*v^6 + 2*t*u^4*v^3)*x^6*y^6 + (2*t^7*u^10*v^3 + 
    2*t^6*u^9*v^3 + 2*t^4*u^10*v^6 + 2*t^4*u^7*v^3 + 2*t^3*u^9*v^6 + 
    2*t^3*u^6*v^3 + t*u^7*v^6 + u^6*v^6)*x^6*y^3*z^3 + (2*t^8*u^11*v^3 + 
    2*t^7*u^10*v^3 + 2*t^5*u^11*v^6 + 2*t^5*u^8*v^3 + 2*t^4*u^10*v^6 + 
    2*t^4*u^7*v^3 + t^2*u^8*v^6 + t*u^7*v^6)*x^6*y^3 + (t^7*u^13*v^6 + 
    t^6*u^12*v^6 + t^4*u^10*v^6 + t^3*u^9*v^6)*x^6*z^3 + (t^8*u^14*v^6 + 
    t^7*u^13*v^6 + t^5*u^11*v^6 + t^4*u^10*v^6)*x^6 + (t*u + 
    u^3*v^3)*x^3*y^18*z^3 + (t^2*u^2 + t*u^4*v^3)*x^3*y^18 + (2*t^4*u^4 + 
    2*t^3*u^6*v^3)*x^3*y^15*z^3 + (2*t^5*u^5 + 2*t^4*u^7*v^3)*x^3*y^15 + 
    (t^7*u^7 + t^6*u^9*v^3 + 2*t^4*u^4 + 2*t^3*u^6*v^3 + 2*t*u^4*v^3 + 
    2*u^6*v^6)*x^3*y^12*z^3 + (t^8*u^8 + t^7*u^10*v^3 + 2*t^5*u^5 + 
    2*t^4*u^7*v^3 + 2*t^2*u^5*v^3 + 2*t*u^7*v^6)*x^3*y^12 + (2*t^7*u^7 + 
    2*t^6*u^9*v^3 + t^4*u^7*v^3 + t^4*u^4 + t^3*u^9*v^6 + t^3*u^6*v^3 + 
    t*u^4*v^3 + t*u + u^6*v^6 + u^3*v^3)*x^3*y^9*z^3 + (2*t^8*u^8 + 
    2*t^7*u^10*v^3 + t^5*u^8*v^3 + t^5*u^5 + t^4*u^10*v^6 + t^4*u^7*v^3 + 
    t^2*u^5*v^3 + t^2*u^2 + t*u^7*v^6 + t*u^4*v^3)*x^3*y^9 + (2*t^7*u^10*v^3 + 
    t^7*u^7 + 2*t^6*u^12*v^6 + t^6*u^9*v^3 + t^4*u^4 + t^3*u^6*v^3 + t*u^7*v^6 +
    2*t*u^4*v^3 + u^9*v^9 + 2*u^6*v^6)*x^3*y^6*z^3 + (2*t^8*u^11*v^3 + t^8*u^8 +
    2*t^7*u^13*v^6 + t^7*u^10*v^3 + t^5*u^5 + t^4*u^7*v^3 + t^2*u^8*v^6 + 
    2*t^2*u^5*v^3 + t*u^10*v^9 + 2*t*u^7*v^6)*x^3*y^6 + (2*t^7*u^10*v^3 + 
    2*t^6*u^12*v^6 + 2*t^4*u^10*v^6 + 2*t^4*u^7*v^3 + 2*t^3*u^12*v^9 + 
    2*t^3*u^9*v^6 + t*u^7*v^6 + u^9*v^9)*x^3*y^3*z^3 + (2*t^8*u^11*v^3 + 
    2*t^7*u^13*v^6 + 2*t^5*u^11*v^6 + 2*t^5*u^8*v^3 + 2*t^4*u^13*v^9 + 
    2*t^4*u^10*v^6 + t^2*u^8*v^6 + t*u^10*v^9)*x^3*y^3 + (t^7*u^13*v^6 + 
    t^6*u^15*v^9 + t^4*u^10*v^6 + t^3*u^12*v^9)*x^3*z^3 + (t^8*u^14*v^6 + 
    t^7*u^16*v^9 + t^5*u^11*v^6 + t^4*u^13*v^9)*x^3 + t*u^4*v^3*y^18*z^3 + 
    t^2*u^5*v^3*y^18 + 2*t^4*u^7*v^3*y^15*z^3 + 2*t^5*u^8*v^3*y^15 + 
    (t^7*u^10*v^3 + 2*t^4*u^7*v^3 + 2*t*u^7*v^6)*y^12*z^3 + (t^8*u^11*v^3 + 
    2*t^5*u^8*v^3 + 2*t^2*u^8*v^6)*y^12 + (2*t^7*u^10*v^3 + t^4*u^10*v^6 + 
    t^4*u^7*v^3 + t*u^7*v^6 + t*u^4*v^3)*y^9*z^3 + (2*t^8*u^11*v^3 + 
    t^5*u^11*v^6 + t^5*u^8*v^3 + t^2*u^8*v^6 + t^2*u^5*v^3)*y^9 + 
    (2*t^7*u^13*v^6 + t^7*u^10*v^3 + t^4*u^7*v^3 + t*u^10*v^9 + 
    2*t*u^7*v^6)*y^6*z^3 + (2*t^8*u^14*v^6 + t^8*u^11*v^3 + t^5*u^8*v^3 + 
    t^2*u^11*v^9 + 2*t^2*u^8*v^6)*y^6 + (2*t^7*u^13*v^6 + 2*t^4*u^13*v^9 + 
    2*t^4*u^10*v^6 + t*u^10*v^9)*y^3*z^3 + (2*t^8*u^14*v^6 + 2*t^5*u^14*v^9 + 
    2*t^5*u^11*v^6 + t^2*u^11*v^9)*y^3 + (t^7*u^16*v^9 + t^4*u^13*v^9)*z^3 + 
    t^8*u^17*v^9 + t^5*u^14*v^9
> time Factorization(h);
[
    <z + 2*a + 2*b, 3>,
    <y + t*u, 3>,
    <y + t*u + 1, 3>,
    <y + b^3 + 1, 6>,
    <y + 2*b^3, 6>,
    <x + b^3 + 1, 3>,
    <x + 2*b^3, 3>,
    <x + 2*a + 2*b, 3>
]
Time: 0.130