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

EvaluationHomomorphism

← Back to list of classes

Description

Summary

Deciding that a polynomial in several variables does not factor, by evaluating
every variable but one at an integer point and asking the one-variable factoriser.

Remarks

Substituting integers for variables is a ring homomorphism, so a factorisation survives
it: if f = g·h then f(x, a) = g(x, a)·h(x, a). Degrees survive it too, as
long as the leading coefficient in x does not vanish at the point — and degrees in
x add, so if the total is preserved then neither part can have lost any. So an
image that is irreducible, of the same degree in x, is a proof that the polynomial
it came from is irreducible.
 The converse is not true and is not claimed. An image factors more readily than its
source — x^2 + y at y = 4 is x^2 + 4, still irreducible, but at
y = -4 it is (x-2)(x+2) — so a reducible image says nothing at all, and
several points are tried before giving up. This decides one direction and declines the
other, which is why it can be asked first and cheaply.
Why it is worth having next to KroneckerFactorization. The
substitution's image has degree Π (d_i + 1) - 1, a product, so it leaves the
one-variable factoriser's reach after very few variables and the answer is a refusal —
x^2 + y^2 + z^2 + w^2 + 1 is past it. An evaluation image has degree d_main and does not grow with the variable count at all, so the polynomials this settles are
exactly the ones the substitution cannot reach. It answers only "it does not factor", but
since #1059 that is
an answer rather than a refusal.
The precondition is checked and not assumed. The argument above is about factors
of positive degree in x; a factor that is free of x — the content — is
invisible to it, and y·(x + 1) would be certified irreducible on an image of
2x + 2 whose primitive part is x + 1. So the content in the main variable is
computed, and anything but a constant declines. The caller has a path that takes the
content out and asks again.
This is not Hensel lifting, and does not pretend to be the piece of
#746 tier 1 that is
still outstanding. It is the first step of that algorithm — choosing an evaluation point
whose image keeps the degree and stays square-free — used for the one conclusion that
needs no lifting. Lifting a *reducible* image back to a factorisation of the source is the
rest of it, and is a different piece of work.

Members

























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