progress on native module for polynomial factoring

[Sherm Ostrowsky]

It's interesting how all kinds of different things in mathematics have a way of coming together.

I have been working on factoring univariate polynomials using only mathpiper functions.  The YACAS function BinaryFactors() can correctly find all the LINEAR polynomial factors, but leaves  behind a residual polynomial which is a product of one or more quadratic irreducible polynomials.  If there is only one such quadratic factor, then BinaryFactors() gets it by just eliminating all the linear factors.

So, the only remaining problem is to find the irreducible quadratic factors.  This is what I have been experimenting with.

Since the residual must be a polynomial of at least 4th degree (because if it were quadratic it would already be solved!), we can assume it is of the following form:

resid = Product(ai*x^2+bi*x+ci) for i = 1 .. N, N being the number of such polynomials.  Now, by making the polynomial  resid  Monic, we can be sure that all of the ai coefficients are 1.  The price for this simplification is that the residual polynomial may be in QQ, even if the original polynomial was over the integers.  But I think that is no real hindrance for what follows.

resid is a monic polynomial of degree 2*N, where N > 1.  Since all the ai = 1, there are exactly 2*N unknown coefficients (in QQ) to be found.  But by expanding the above product ansatz, and equating coefficients of like powers of x, we are left with a set of 2*N nonlinear algebraic simultaneous equations in 2*N.  In principle, therefore, purely ala set of simultaneous NONLINEAR equations gebraic techniques should allow us to determine the coefficients!

So it seems to come down to this:  How does one efficiently solve n nonlinear algebraic equations in n unknowns?

Which, of course, is the subject matter of Groebner Bases in particular, and Algebraic Geometry in general.

I am looking into it.

Fun.  fun.  fun!

Sherm

[Sherm Ostrowsky]

LATER.

Good news and bad news.  The bad first -- it's not so bad.  The MathPiper algorithm in BinaryFactors() becomes VERY slow if more than one irreducible quadratic factor is present in the presented polynomial.  We'll have to try to improve that later.

The good news is this:  starting with the "residual" polynomial after running BinaryFactors() and removing all linear factors, we can assume it is of the form  x^2n +a1 x^(2n-1)+a2 x^(2n-2)+...+a2n , where there are n irreducible quadratic polynomial factors in the residual.  Since we know that all the interesting solutions of the resulting set of 2n equations in 2n variables must be rational numbers (and probably with "small" numerators and denominators), the Variety represented by this solution set is "of dimension zero".  It turns out that knowing this fact should make it much easier to find a solution set by efficient means, described in the literature.  I am pursuing this attack.

Sherm