On Sep 25, 4:37 pm, Bill Hart <[EMAIL PROTECTED]> wrote: > Here is my second question (one looks doubly smart if one has two > difficult questions and still no clue): is it true that one can easily > tell if two algebraic numbers are *not* equal in this system, but to > check if they are equal, one *always* has to drop back to algebraic > techniques? Someone seemed to indicate that one could use root > refinement to *prove* equality. Note I am not assuming anything about > the construction of the polynomials of these algebraic numbers here, > nor anything about how these algebraic numbers were constructed. I > don't even think I can assume their polynomials have the same degree, > since it is hard to give a minimum polynomial without exact > coefficients being known.
My code always falls back on algebraic techniques to prove equality. Like I said before, though, there is another possibility. There is a sequence of theorems on "root separation bounds" that let you write an algorithm that recursively examines the derivation of an algebraic real and gives a lower bound on its absolute value, if it is nonzero. Wow, that was a long sentence...let me give an example. Suppose you have an algebraic number that was produced as a-b, where a is a root of a degree-4 integer polynomial with 17-bit coefficients and b is a root of a degree-5 integer polynomial with 13-bit coefficients. Given only this information, the algorithm might say "either a-b is zero, or its absolute value is at least 2^-137". (I just made up this number; I don't know what the algorithm would really say for this example.) Now you can refine the interval for a-b until it is of width at most 2^-138; if this refined interval includes zero, then a-b must be exactly equal to zero (so a is equal to b). (And I just realized this is not a very good example, since if the degree-4 and degree-5 polynomials are irreducible, then a must be different from b. But the root separation bounds approach works in interesting examples too.) I don't know of anybody who has benchmarked "fall back on algebraic techniques" versus "use root separation bounds" to see which performs better (but I bet the answer depends on what exactly you're doing with the library). Also, the papers I've seen discussing root separation bounds were looking only at real numbers; I don't know how hard it is to extend to the complex case (or if anybody has already done this). Carl --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
