From: kramsay@aol.com (KRamsay)
Newsgroups: sci.math
Subject: Re: (Q) Solution of simultaneous equations
Lines: 28
In article <6p1bnt$pp2$1@gannett.math.niu.edu>, rusin@vesuvius.math.niu.edu
(Dave Rusin) writes:
>Is there an algorithm for determining
>if a set of simultaneous polynomial equations over the reals
>has a real solution ?

This is the import of Tarski's Elimination of Quantifiers. You may
think about this algebraically (use elimination to reduce to one
equation in several unknowns) or think about it geometrically (the
equations define a variety; you can check for points by looking for
points in the projection to a quotient space).
Tarski's algorithm suffices for the original problem, since the
polynomials had integer coefficients, but there remains an obstacle
in the case of a general set of polynomial equations with real
coefficients. Once all the quantifiers are gone, you still may need
to make comparisons among reals.
Consider x^2=a, where a is some given real. This has a real solution
iff a>=0. But there is no algorithm which determines whether an
arbitrarily given real is >=0. For example, let a=gammam/n where
gamma is Euler's constant gamma and m/n is rational. Presumedly
gamma is irrational and you will therefore be able to determine
whether it is >=m/n, but there is no guarantee of that yet.
Keith Ramsay "Thou Shalt not hunt statistical significance with
kramsay@aol.com a shotgun." Michael Driscoll's 1st commandment
==============================================================================
From: Dave Rusin
Date: Sat, 25 Jul 1998 23:20:44 0500 (CDT)
To: kramsay@aol.com
Subject: Re: (Q) Solution of simultaneous equations
Newsgroups: sci.math
In article <1998072320534500.QAA29820@ladder01.news.aol.com> you write:
>
>Tarski's algorithm suffices for the original problem, since the
>polynomials had integer coefficients, but there remains an obstacle
>in the case of a general set of polynomial equations with real
>coefficients. Once all the quantifiers are gone, you still may need
>to make comparisons among reals.
Point well taken. I very much had the original poster's framework in
mind in my response  Groebner basis calculations very definitely require
determining whether remainders in polynomial division are zero or not,
which is fine with coefficients in Z but really a chore with real
coefficients (symbolic and floating point both).
>Consider x^2=a, where a is some given real. This has a real solution
>iff a>=0. But there is no algorithm which determines whether an
>arbitrarily given real is >=0. For example, let a=gammam/n where
>gamma is Euler's constant gamma and m/n is rational. Presumedly
>gamma is irrational and you will therefore be able to determine
>whether it is >=m/n, but there is no guarantee of that yet.
Well, for _specific_ m and n we can determine sign(gamma  m/n),
since gamma may be determined to any number of digits in a finite
amount number of steps. You want one of those silly "gamma =
+1 if Goldbach conjecture is true, 1 if Goldbach conjecture is false"
examples.
dave
==============================================================================
From: KRamsay@aol.com
Date: Sun, 26 Jul 1998 21:05:20 EDT
To: rusin@math.niu.edu
Subject: Re: (Q) Solution of simultaneous equations
Yes, I figured you probably had seen that the coefficients
were to be integers, and answered accordingly.
In a message dated 980726 00:20:48 EDT, you write:
> > For example, let a=gammam/n where
> >gamma is Euler's constant gamma and m/n is rational. Presumedly
> >gamma is irrational and you will therefore be able to determine
> >whether it is >=m/n, but there is no guarantee of that yet.
>
> Well, for _specific_ m and n we can determine sign(gamma  m/n),
We don't know that. If we knew that gamma was irrational (which it
probably is) we could always determine the sign by computing it up
to the degree of accuracy needed to distinguish gamma from m/n. If
gamma were equal to m/n for some integers m and n, computing gamma
to ever increasing accuracy wouldn't ever necessarily let us know that
it was in fact >=m/n. Suspicions would rise that it was equal to m/n
as the number of places of accuracy grew, but there's no guarantee
that we would ever be able either to get rid of worries that it would
eventually turn out to be just under m/n instead.
> since gamma may be determined to any number of digits in a finite
> amount number of steps.
This isn't known either, to my knowledge, if by "may be determined"
we mean that "we now have an algorithm for determining".
I think I would have heard if someone proved gamma was irrational;
I'm just a little less sure I would have heard if someone proved it
was not a terminating decimal.
If we knew that gamma had a nonterminating decimal expansion, we could
compute it to any number of digits by computing it accurately enough.
If gamma were in fact a terminating decimal, we wouldn't necessarily
be able to know it didn't actually have a long string of 9's starting
there, but ending at some point beyond the precision of our
calculations. The final nonzero digit would be known to be either d
or d+1, and the successive ones would be known to be either 9 or 0
respectively, but resolving the ambiguity would require proving that
gamma was >= the terminating decimal that it was.
> You want one of those silly "gamma =
> +1 if Goldbach conjecture is true, 1 if Goldbach conjecture is false"
> examples.
I hoped for a more lifelike example.
There are a few "no go" theorems which are typically established
by one of these artificial examples, but once you get the point, the
examples don't play much of a further role.
A somewhat nicer example is r=1/n if n is the smallest counterexample
to Goldbach, r=0 if Goldbach is true. Determining whether r>=0 is the
same as determining whether Goldbach is true. Determining the first
decimal place of 1r is the same as deciding Goldbach as well. One way
in which it is nicer, is that r is computable in a certain standard
sense, without our needing to know more than we do now.
There's a kind of delicate trade off. The technical results, in
rigorous form (using Goedel's theorem or the unsolvability of the
halting problem to demonstrate uncomputability, etc.) can be
misleading in one direction, while a more informal approach can be
misleading another way. Using the artificial examples can perhaps lead
to an impression that this "recursive" numerical analysis is mainly
pertinent only to these "pathological" cases, while in essential
respects it's the same issue as shows up in everyday real analysis. On
the other hand, it is true that the typical instance of a question "is
r>=0?" is different from the typical instance of a question "does
there exist an n such that...?" where the property is decidable for
each n, in spite of their being the same logical class of problem.
This distinction between "knowing how to compute" a number and
"knowing how to compute the decimal expansion of" a number may seem
particularly arcane, but it is useful to know. I once saw a paper
in which the author had discovered essentially the same phenomenon
for continued fractions, and took it as an explanation for why it is
harder to compute using continued fractions. But adding together
numbers given as decimal expansions can have the same difficulty if
you get a long string of 9's and don't know whether there will be a
carry somewhere which converts them all into 0's. And probably the
author also didn't know about Gosper's algorithm for computing the sum
and product of two numbers given as continued fractions. So he wound
up "explaining" something which wasn't entirely true, using a fact
which happens to be true for more trivial reasons.
Keith Ramsay
==============================================================================
From: Dave Rusin
Date: Mon, 27 Jul 1998 08:58:30 0500 (CDT)
To: KRamsay@aol.com
Subject: Re: (Q) Solution of simultaneous equations
Thank you for your careful response. Yes, indeed, I goofed by _assuming_
gamma to be irrational, so that the sign of gammam/n could be eventually
be determined for specific m and n.
You must be a stickler when teaching calculus
classes about Newton's method and so on, since you have interpreted my
> since gamma may be determined to any number of digits in a finite
> amount number of steps.
to mean that for each N we may determine in advance a number of steps
of computation necessary to guarantee that gamma lies in a particular
interval (a/10^N, (a+1)/10^N), rather than the usual interpretation (that
for each N we may determine in advance a number of steps of computation
necessary to guarantee that gamma lies in a particular interval of
length 1/10^N). In the case of gamma itself, since gamma lies in
every interval (S_n  log(n+1), S_n  log(n) ) of length roughly 1/2n^2
(where S_n = 1 + 1/2 + ... + 1/n ), and log(n) is likewise computable
to lie in small intervals, the usual interpretaton makes "N digits of
accuracy" computable in O(sqrt(N)) steps, whereas if gamma happens to
be very near to a multiple of 1/N, more steps of computation  and
we don't even know how many  would be needed in the strict interpretation.
And again, should gamma happen to equal a/N for some a, and we
were unaware of this fact, then our algorithm to compute N digits
of accuracy in the strict sense would never terminate. This is the
nature of your clarification to me previous mail, right?
>So he wound
>up "explaining" something which wasn't entirely true, using a fact
>which happens to be true for more trivial reasons.
Ah yes, the proof which isn't really one. I've heard them called "poofs".
dave
==============================================================================
From: KRamsay@aol.com
Date: Mon, 27 Jul 1998 13:23:58 EDT
To: rusin@math.niu.edu
Subject: Re: (Q) Solution of simultaneous equations
In a message dated 980727 09:58:40 EDT, you write:
> You must be a stickler when teaching calculus
> classes about Newton's method and so on,
I don't teach calculus anymore. I got my PhD in 1991
and like a lot of us who got PhDs around then, I've
all but given up on teaching. I hear that the job
crunch in the academic math market has eased up
somewhat, but just for "fresh" PhDs.
In any case, I never did teach this kind of thing in class.
> And again, should gamma happen to equal a/N for some a, and we
a/10^N
> were unaware of this fact, then our algorithm to compute N digits
> of accuracy in the strict sense would never terminate. This is the
> nature of your clarification to me previous mail, right?
There's a distinction between N places of accuracy and "N decimal
digits". The "decimal expansion of x" is defined so that there is a
unique answer to "Nth decimal of x", but as a result it requires
more than just knowing x to N decimal places of accuracy.
Keith Ramsay