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=gamma-m/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=gamma-m/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 98-07-26 00:20:48 EDT, you write: > > For example, let a=gamma-m/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 1-r 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 gamma-m/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 98-07-27 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 "N-th decimal of x", but as a result it requires more than just knowing x to N decimal places of accuracy. Keith Ramsay