2
$\begingroup$

I have software which stores information about algebraic numbers with absolute precision. If you build it up by creating instances of a Python representation of an integer, float, Decimal, or string, a binary tree in which each node is either a leaf node containing an integer, or a node storing an arithmetical operation and two order-significant children, the two numbers included in the operation. For the purposes of this discussion, I am ignoring the case of representing computable numbers like π and e, and assuming that all algebraic numbers are a binary tree boiling down to integers and floats.

There are two major liabilities which boil down to one: I don't see how to always know when there is rounding error at a particular node on the binary tree, and I don't know, in terms of math, how to tell if two algebraic numbers are equal. I can pull what is the standard operating procedure for floats, which is to never look for equality, just confirm that their equality is "good enough for government work" by calculating decimal representations to some perhaps configurable number of decimal places. One can of course increase the precision in the hopes of finding a difference, but that technique will perhaps eventually find the most minute inequality, but never prove an absolute inequality rather than a "looks at least close enough" claim of equality. The sets of "greater than" and "less than" are both recursively enumerable, but unless you can pull a theory-based test for algebraic equality / comparison, equal numbers are not even recursively enumerable.

My program is implemented in Python, as an "executable pseudocode" implementation implemented more than anything else reference implementation than anything else. But my question is not really a Python question; it is a question about an area of math I know little about. My question is this:

Given two representations of algebraic numbers built up by arithmetic on integers (which happens to be a binary tree, but that is not my question): Are there any algorithms that can compare / test for equality?

$\endgroup$
2
  • 1
    $\begingroup$ It seems a little odd that you are trying to do exact computation with algebraic numbers, but yet allow some quantities to be represented with inexact floating-point approximations.... $\endgroup$
    – user14972
    Commented Apr 12, 2013 at 13:10
  • $\begingroup$ @MJD: The same logic could be applied to any representation of numbers to say that they aren't really numbers. :P Algebraic numbers are definitely decidable, though; in fact, the first-order theory of real closed fields is even complete. $\endgroup$
    – user14972
    Commented Apr 12, 2013 at 13:11

1 Answer 1

Reset to default
6
$\begingroup$

There is a standard way to represent algebraic numbers that also directly suggests the methods to test things like equality: you represent them by specifying their minimal polynomial, and enough supplemental data to indicate which root of the minimal polynomial is intended.

Every algebraic number has a unique minimal polynomial. So with a suitable encoding of the supplemental data, you can even arrange things so that each algebraic number has a unique representation.

It may or may not be easier to use this scheme to represent just the real algebraic numbers, and then represent complexes in the usual way as pairs of real algebraic numbers. This would let you use make use of nice computational techniques like Sturm's theorem

$\endgroup$
1
  • $\begingroup$ To give particular examples to illustrate Hurkyl's point: Mathematica has Root[] objects, and Maple has RootOf() objects; both represent algebraic numbers in terms of the minimal polynomial and a particular index (though SFAICT the two environments have a different indexing scheme; see their docs for details). $\endgroup$
    – J. M. ain't a mathematician
    Commented Apr 12, 2013 at 13:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .