Bill Page wrote:
>
> On Wed, Oct 24, 2018 at 5:05 PM Waldek Hebisch <[email protected]>
> wrote:
> >
> > If you could find solution _in the fraction field_ then
> > the method would be fine. However, in general finding
> > rational solutions to polynomial system of equations is
> > uncomputable.
>
> Can you suggest a reference? I could not find this result (well
> known?) after a quick search.
Matiasevicz theorem (solution to Hibert 10-th problem) says
that existence of integer solutions is uncomputable.
Concerning rationals I probably misrememberd things:
Wikipedia says that it is unknown if existence of
rational solutions is computable or not.
> > Groebner bases decide if there are solutions in
> > algebraic closure, but you may have algebraic
> > solutions without rational solutions. If you say that
> > you can find out if there is rational solution
> > (= factorization) you should better justify this and
> > explain what special properties of system you use.
> >
>
> Yes, that would be nice. Unfortunately SystemSolvePackage in FriCAS
> does not make any explicit claim about completeness. But it does refer
> to the method of triangular systems.
IIRC it uses either Groebner bases or triangular systems. In both
cases you can get algebraic solutions (irrational ones).
> The only special property that I can think of is that the equations in
> the system are at most quadratic. I do not know if that is sufficient.
No. There is old trick (Veronese embedding) which reduces general
systems to systems of degree 2.
> Another thing is that we are only interested in finding at least one
> explicit solution (if it exists). We do not need to know all
> solutions.
One useful thing is Davenport observation: one can get solutions
for highest order terms in combinatorial way. Given high order
terms the rest seem to reduce to sequence of linear systems.
Actually, I would like to know some hard examples: all that we
have now seem to be quite easy by ad-hoc methods.
--
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
