I looked more at the problem. It seems that Cohn claims
that there are finitely many factorizations, but he jumps
over few subtle points so I need to check his arguments
more carefuly.
AFAICS Caruso (after Davenport) gives correct proof that
factorization of homogeneous polynomials is unique and gives
correct algorithm for factoring homogeneous polynomials.
OTOH what he writes about noncommutative polynomials
is problematic. Namely, he tries to choose monomials
and that looks wrong. AFAICS one gets correct version
of algorithm looking at factorization of leading term,
treating it is sequence of primes. So left factor
coresponds to initial part of sequence, call it h, right
factor to the rest, call it g. If there is no overlap
between h and g, then one get complete factorizations
solving linear equations. Each overlap potentially leads
to non-uniqueness, introducing one parameter family
of solutions. So in general we may get solution depending
polynomially on k parameters when k is number of overlaps.
But linear system obtained are overdetermined and there
is good chance that we can quickly determine some parameters
from other equations. So we really get k parameters only
when there is very special structure (probably quite close
to commutative). Once we obtained candidate solution
from linear equations we can multiply candidate factors
and get system of nonlinear equations in at most k variables.
ATM in final step I do not know better method than
convertion to triangular system.
In a sense what I write above is equivalent to what xdpolyf1
is doing. However, xdpolyf1 will use _much_ larger number
of variables and hopes that code computing Groebner bases
can cope with them. Above we can use special structure of
systems and have essentially linear time solver. When we
have several parameters and high degree we may get many
linear systems so method above may get expensive. However
using Groebner bases for this looks much more expensive.
Let me say that when highest order term has nontrivial
commutative image, then we can use commutative factorization
and get combinatorial problem of matching commutative
factors to noncommutative ones. AFAICS any matching
uniquely determines parameters of linear systems, so
to find all factorization we need to check all matchings.
In principle there may be exponentially many matchings,
so this may be expensive. But we should be able to
find quickly low degree factors.
>From theoretical point of view in this case we
get direct proof that there are finitely many factorizations.
I hope that one can say more, but enough for today.
--
Waldek Hebisch
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To post to this group, send email to fricas-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
