AngouriMath

Symbolics for .NET


Table of contents

AngouriMath

Navigation
Home Quick start Wiki Almanac Research What's new Try Use Angouri.org GitHub Report a bug Donate Contacts

KroneckerFactorization

← Back to list of classes

Description

Summary

Factorisation of a polynomial in any number of variables, by reducing it to one variable
and putting the answer back.

Remarks

Kronecker's substitution, in mixed radix. A factor of a polynomial has degree at
most d_i in each variable v_i, because a factor divides it. So with radices
d_i + 1 and place values s_0 = 1, s_(i+1) = s_i * (d_i + 1), the map
v_0^e_0 · … · v_(k-1)^e_(k-1) -> t^(Σ e_i · s_i) writes each exponent as one digit
of a numeral and is therefore injective on every monomial that can appear in the
polynomial or in any of its factors. A factorisation of the one-variable image can be read
back digit by digit, and each subset of its irreducible factors names a candidate.
A candidate is a guess and is checked by division. The image can factor further
than the polynomial does — the substitution is injective on monomials, not on
factorisations — so a subset whose product reads back as a polynomial need not divide the
original. Every one is tested with exact division before it is kept, which is why this
cannot answer wrongly: the worst it does is fail to find a factorisation that exists and
say so.
What it will not do. The image has degree Π (d_i + 1) - 1, a *product* and
not a sum, and the one-variable factoriser stops at
MaxDegree — so the ceiling closes quickly as variables are
added. Two variables reach bidegrees like (2, 10), (3, 7) and (5, 4); three variables of
degree 2 fit (27 ≤ 32) and four do not (81); and a quadratic in eight variables is far
past it. The recombination is over subsets, so the number of irreducible factors of the
image is capped as well. Both limits are refusals, never wrong answers.
Raising the degree ceiling is not what would lift them, and that was measured rather
than assumed.MaxDegree is 32 while the machinery
underneath affords 64 (MaxDegree), which looks like
a free doubling of the exponent budget — a whole variable's worth of reach, since the
budget is a product. Doubled, nothing new factors: x^7 - y^7,
x^6 - y^6, x^3 - (y + z)^3, (x^8 + y)(x^8 + 3y) and
(x^2 + y^5)(x^2 - y^5) all still refuse, at images of degree 34 to 56 that are
inside the raised ceiling.
 The reason is the method rather than the bound: the substitution's images over-factor
badly. A two-factor bivariate maps to a one-variable polynomial that splits into many
irreducibles — x^7 - y^7 becomes t^7 (1 - t^49), whose factors are
cyclotomic — so the recombination is exponential in a factor count the substitution itself
inflates. That is exactly the cost MaxDegree is set to
bound, and moving it only moves where the refusal comes from. Lifting these limits means
not inflating the factor count in the first place, which is Hensel lifting with an
evaluation homomorphism — a different algorithm, not a larger number
(#746 item 43).

Members

























Angouri © 2019-2023 · Project's repo · Site's repo · Octicons · Transparency · 4378 pages online