Overview

  • How can absolute irreducibility be expressed by equations in the coefficients?
  • Why must local factors be recombined?
  • How do derivatives and Newton polytopes help compute factors?

Noether forms

Fix a number of variables r≥2r\ge2 and a total degree d≥2d\ge2. Noether forms are finitely many polynomials with integer coefficients in the coefficients of a general polynomial FF of degree at most dd. Their simultaneous vanishing means that FF is reducible over the algebraic closure or has degree less than dd. Thus, for an input of exact degree dd, one nonzero form proves absolute irreducibility. Kaltofen gives effective degree and coefficient bounds valid in arbitrary characteristic.

In a family, substituting the parameter-dependent coefficients into these forms gives equations for the reducible members and degree drops. This explains why the exceptional set is algebraic.

References 1

Lifting and recombination

A common factorization method starts with F(0,y)F(0,y). When the relevant factors are coprime and the leading coefficient is suitable, Hensel lifting extends them to factors in K[[x]][y]K[[x]][y], to a chosen precision. Products of these local factors are then tested for being polynomial factors of FF. This second step is called recombination.

Example

Over C\mathbb C, the polynomial y2−(1+x)y^2-(1+x) is absolutely irreducible: it is linear in xx. In C[[x]][y]\mathbb C[[x]][y], however, it factors as

(y−1+x)(y+1+x),1+x=1+12x−18x2+⋯ .(y-\sqrt{1+x})(y+\sqrt{1+x}),\qquad \sqrt{1+x}=1+\tfrac12x-\tfrac18x^2+\cdots.

These formal factors are not polynomial factors.

References 1

Differential methods

If F=∏iFiF=\prod_iF_i, its logarithmic differential is dF/F=∑idFi/FidF/F=\sum_i dF_i/F_i. The form (G/F) dx+(H/F) dy(G/F)\,dx+(H/F)\,dy is closed precisely when

F(Gy−Hx)=GFy−HFx.F(G_y-H_x)=G F_y-H F_x.

Fix F∈K[x,y]F\in K[x,y] of bidegree (m,n)(m,n), with m,n≥1m,n\ge1 and gcd⁡(F,Fx)=1\gcd(F,F_x)=1. Let VV consist of the polynomials GG for which this equation has a solution HH satisfying

deg⁡xG≤m−1,deg⁡yG≤n,deg⁡xH≤m,deg⁡yH≤n−1.\deg_xG\le m-1,\quad\deg_yG\le n,\qquad\deg_xH\le m,\quad\deg_yH\le n-1.

Theorem (Gao)

If char⁡K=0\operatorname{char}K=0 or char⁡K>(2m−1)n\operatorname{char}K>(2m-1)n, then dim⁡KV\dim_KV equals the number of absolutely irreducible factors of FF. In particular, FF is absolutely irreducible if and only if dim⁡KV=1\dim_KV=1.

The equation is linear in the coefficients of G,HG,H. It therefore turns the factor-counting problem into exact linear algebra. The linear system counts absolute factors without first finding their coefficient field. Extracting those factors from a basis uses univariate factorization and gcd computations; an absolute factorization must also specify the extension containing their coefficients.

In smaller characteristic, the dimension can exceed the number of absolute factors. Hoppen–Rodrigues–Trevisan identify a subspace with the required dimension in every characteristic. Their result also shows that dim⁡KV=1\dim_KV=1 remains a sufficient certificate under gcd⁡(F,Fx)=1\gcd(F,F_x)=1, even when the converse fails.

References 2

Example

Take Fc=x2+y2+cF_c=x^2+y^2+c over Q\mathbb Q, with c=0c=0 or 11. Its bidegree is (2,2)(2,2), and gcd⁡(Fc,(Fc)x)=1\gcd(F_c,(F_c)_x)=1. The degree bounds allow six terms in each numerator:

G=a00+a01y+a02y2+a10x+a11xy+a12xy2,H=b00+b01y+b10x+b11xy+b20x2+b21x2y.\begin{aligned}G&=a_{00}+a_{01}y+a_{02}y^2+a_{10}x+a_{11}xy+a_{12}xy^2,\\H&=b_{00}+b_{01}y+b_{10}x+b_{11}xy+b_{20}x^2+b_{21}x^2y.\end{aligned}

Substitute these expressions into Fc(Gy−Hx)=2yG−2xHF_c(G_y-H_x)=2yG-2xH. Comparing the coefficients of x3y,xy3,x3,y3x^3y,xy^3,x^3,y^3 first gives a12=b21=a11=b11=0a_{12}=b_{21}=a_{11}=b_{11}=0. The remaining equations reduce to

a00=a02=b00=b20=0,a10=b01,a01=−b10,c a01=0.\begin{gathered}a_{00}=a_{02}=b_{00}=b_{20}=0,\\a_{10}=b_{01},\qquad a_{01}=-b_{10},\qquad c\,a_{01}=0.\end{gathered}

Thus every solution has the form

G=ux+vy,H=uy−vx,cv=0.G=ux+vy,\qquad H=uy-vx,\qquad cv=0.

For c=1c=1, this gives V=QxV=\mathbb Q x, of dimension one. Gao’s theorem proves that x2+y2+1x^2+y^2+1 is absolutely irreducible. For c=0c=0, it gives V=Qx+QyV=\mathbb Q x+\mathbb Q y, of dimension two. Accordingly,

x2+y2=(x+iy)(x−iy)x^2+y^2=(x+iy)(x-iy)

has two absolute factors, although it is irreducible over Q\mathbb Q. Their logarithmic differentials give the numerator pairs (x−iy, y+ix)(x-iy,\,y+ix) and (x+iy, y−ix)(x+iy,\,y-ix). These span the same two-dimensional solution space after extending the coefficient field to Q(i)\mathbb Q(i). The linear system counts absolute factors without first finding their coefficients.

References 1

Fields of factors

Over a perfect field KK, each irreducible factor over KK is, up to a scalar, the product of one Galois orbit of absolute factors. For example, x+iyx+iy and x−iyx-iy form one orbit over Q\mathbb Q; their product x2+y2x^2+y^2 is one irreducible rational factor. An absolute factorization must specify the extension containing the factor coefficients as well as the factors themselves.

References 1

Algorithms that use the support

A dense representation records every coefficient up to a degree bound. A sparse representation records only nonzero terms. A convex-dense representation records the lattice points of the Newton polytope, including zero coefficients. Complexity bounds for these representations measure different input sizes.

Weimann’s published 2025 algorithm factors bivariate polynomials using the area and lattice lengths of their Newton polygons. Its hypotheses include separability of the relevant edge polynomials. Theorem 1.2 gives separate bounds in characteristic zero or sufficiently large characteristic, and over finite fields of arbitrary characteristic. Its cost includes univariate factorizations in addition to arithmetic operations.

Demin–van der Hoeven’s 2025 paper develops randomized sparse factorization methods based on sparse interpolation, with bounds that also account for evaluation and the factor supports. These are results on factorization over the coefficient field; they are not unconditional support-only tests for absolute irreducibility.

References 2

What a computation proves

Exact multiplication verifies a proposed factorization. Irreducibility requires a further argument: for example, a one-dimensional differential solution space under the theorem’s hypotheses, a certified factorization algorithm, or an indecomposable Newton polytope after removal of monomial factors.

A numerical approximation to complex factors can suggest the answer, but does not by itself prove an exact factorization over an algebraic number field. Likewise, failure to find factors in a bounded search is not an irreducibility proof. The field, input representation, and exact certificate determine the conclusion.

References 2

Related topics

References

  1. Effective Noether irreducibility forms and applications

    Kaltofen, Erich. Journal of Computer and System Sciences, 50(2), 274–295, 1995.

    Read the source
  2. Factorisation des polynômes à plusieurs variables

    Lecerf, Grégoire. Journées Nationales de Calcul Formel (13–17 May 2013), CIRM, Les cours du CIRM, 1–85, 2013.

    Read the source
  3. Factoring multivariate polynomials via partial differential equations

    Gao, Shuhong. Mathematics of Computation, 72(242), 801–822, 2003.

    Read the source
  4. A note on Gao’s algorithm for polynomial factorization

    Hoppen, Carlos and Rodrigues, Virgínia M. and Trevisan, Vilmar. Theoretical Computer Science, 412(16), 1508–1522, 2011.

    Read the source
  5. Improvements of convex-dense factorization of bivariate polynomials

    Weimann, Martin. Polynesian Journal of Mathematics, 2(4), 1–34, 2025.

    Read the source
  6. Factoring sparse polynomials fast

    Demin, Alexander and van der Hoeven, Joris. Journal of Complexity, 88, 101934, 2025.

    Read the source