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 and a total degree . Noether forms are finitely many polynomials with integer coefficients in the coefficients of a general polynomial of degree at most . Their simultaneous vanishing means that is reducible over the algebraic closure or has degree less than . Thus, for an input of exact degree , 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
- Kaltofen1995 · §5, Theorem 7Source
Lifting and recombination
A common factorization method starts with . When the relevant factors are coprime and the leading coefficient is suitable, Hensel lifting extends them to factors in , to a chosen precision. Products of these local factors are then tested for being polynomial factors of . This second step is called recombination.
Example
Over , the polynomial is absolutely irreducible: it is linear in . In , however, it factors as
These formal factors are not polynomial factors.
References 1
- Lecerf2013 · §§5.1–5.3 and 5.7Source
Differential methods
If , its logarithmic differential is . The form is closed precisely when
Fix of bidegree , with and . Let consist of the polynomials for which this equation has a solution satisfying
Theorem (Gao)
If or , then equals the number of absolutely irreducible factors of . In particular, is absolutely irreducible if and only if .
The equation is linear in the coefficients of . 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 remains a sufficient certificate under , even when the converse fails.
References 2
- Gao2003PDE · §2, Theorem 2.3 and Corollary 2.5Source
- HoppenRodriguesTrevisan2011 · Theorems 1.1–1.3; §2Source
Example
Take over , with or . Its bidegree is , and . The degree bounds allow six terms in each numerator:
Substitute these expressions into . Comparing the coefficients of first gives . The remaining equations reduce to
Thus every solution has the form
For , this gives , of dimension one. Gao’s theorem proves that is absolutely irreducible. For , it gives , of dimension two. Accordingly,
has two absolute factors, although it is irreducible over . Their logarithmic differentials give the numerator pairs and . These span the same two-dimensional solution space after extending the coefficient field to . The linear system counts absolute factors without first finding their coefficients.
References 1
- Gao2003PDE · §2, Theorem 2.3; the two linear systems are computed hereSource
Fields of factors
Over a perfect field , each irreducible factor over is, up to a scalar, the product of one Galois orbit of absolute factors. For example, and form one orbit over ; their product is one irreducible rational factor. An absolute factorization must specify the extension containing the factor coefficients as well as the factors themselves.
References 1
- Gao2003PDE · §3, representation of absolute factorsSource
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
- Weimann2025ConvexDense · Definition 1.1 and Theorem 1.2Source
- DeminHoeven2025Sparse · Introduction and algorithmic complexity statementsSource
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
- Kaltofen1995 · §8, approximate absolute factorsSource
- Lecerf2013 · Chapters 5–6Source
Related topics
Connected diagrams
Browse all diagrams →Newton polytopes and irreducibility
Support constraints restrict candidate factors and guide algorithms.
Related toPolynomial factorization algorithms
Multivariate algorithms often reduce to univariate factorizations.
Related toPolynomial fibers and Bertini’s theorem
Noether forms describe reducible members of parameterized families.
Linked from 2 articles
References
- Effective Noether irreducibility forms and applications
Kaltofen, Erich. Journal of Computer and System Sciences, 50(2), 274–295, 1995.
Read the source - 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 - Factoring multivariate polynomials via partial differential equations
Gao, Shuhong. Mathematics of Computation, 72(242), 801–822, 2003.
Read the source - 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 - Improvements of convex-dense factorization of bivariate polynomials
Weimann, Martin. Polynesian Journal of Mathematics, 2(4), 1–34, 2025.
Read the source - Factoring sparse polynomials fast
Demin, Alexander and van der Hoeven, Joris. Journal of Complexity, 88, 101934, 2025.
Read the source
Comments
Any comments are welcome. Comments appear after the site owner approves them. Privacy policy.