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

BivariateHenselFactorization

← Back to list of classes

Description

Summary

Factorisation in two variables by Hensel lifting along an evaluation
homomorphism: factor the polynomial at a point, then lift that factorisation back
one power of the auxiliary variable at a time.

Remarks

KroneckerFactorization reaches the same answers by a different route and
leaves a gap this fills. Its one-variable image has degree Π (d_i + 1) - 1, and —
worse than the size — the image over-factors: x^7 - y^7 maps to
t^7 (1 - t^49), whose factors are cyclotomic, so the recombination is exponential
in a count the substitution itself inflated. An evaluation image does not inflate
anything: x^7 - y^7 at y = 1 is x^7 - 1, which has the two factors
the answer has.
The lift. Write g(x, y) = f(x, y + a) so that the point is the origin.
g(x, 0) factors over the integers as u_1 · … · u_r, and a factorisation
modulo y^k is pushed to y^(k+1) by solving α·v + β·u = e for the
error e — which the Bezout pair of u and v answers immediately,
since a square-free image makes them coprime. Reducing α below the degree of
u and pushing the quotient into β keeps each side at the degree it started
at. Lifted as far as the degree of g in y, a true factor is reached
exactly rather than approximately, because it has no higher power to hide in.
What is restricted, and why it is the honest restriction rather than a convenient
one. The leading coefficient in the main variable must be constant. Where it is a
polynomial in y, the lifted factors' leading coefficients have to be *known in
advance* to keep them polynomials rather than power series — Wang's leading-coefficient
problem — and the usual answer is to factor that coefficient and distribute it, which is
a second algorithm on top of this one. Declining is a refusal, and refusing is something
this layer already does.
Nothing here is trusted. Every candidate is checked by exact division of the
original, so a mistake anywhere above — a bad point, a lift that drifted, a recombination
that is not a factor — costs a refusal and cannot cost a wrong answer.

Members

























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