Re: [Axiom-math] POLY INT =\\= UP(x, INT)

[William Sit]

Dylan Thurston wrote:
> 
> On Fri, Oct 10, 2003 at 12:15:22PM -0400, William Sit wrote:
> > > For instance, suppose I have an algorithm that only works
> > > if I can actually compare elements for equality (with the standard
> > > mathematical definition of equality, not equality of representations,
> > > which is only a vaguely useful heuristic approximation).  How can I tell
> > > if it's safe to apply it to a particular group?
> >
> > If the mathematical object has a (and it must have one if computation is to 
> > be
> > done) representation, then your mathematical equality algorithm should be
> > implementable in general based on that representation. In some cases, this 
> > may
> > be a lazy comparison if the representation is only approximate for some of 
> > the
> > elements: for example, for infinite precision reals using a decimal
> > representation or continued fraction.
> 
> I don't understand what you're getting at here.  Yes, your mathematical
> objects should have some well-defined notion of equality; but that
> notion of equality need not be computable.  In the case of computable
> reals, one can establish that two such reals are defintely not equal, or
> are equal to within some bounds, but proving that they are actually
> equal is undecideable.  Thus there is no useful function that fits the
> signature of "=":
> 
>       "=": (%,%) -> Boolean    ++ x=y tests if x and y are equal.
> 
> or, at least, such a function could never (or only rarely) return True.
> 
> Such objects can be useful, despite the lack of an equality algorithm.
Agreed. But since "equality" can be tested at different levels (for example a
mathematical object may be using a certain representation, but equality of the
mathematical object can be tested using only a portion of the representation
(the representation may carry additional information for efficiency); equality
of the entire data representation can be tested if each part of it can be tested
but this may not tell mathematical equality always because the representation
need not be unique; or equality of the mathematical object can only be tested
after rewriting to some canonical form that is not the data representation.

So perhaps a better signature would be:

     "=": (%,%)->Union(Boolean, "Failed")
  ++ x = y returns true if x and y are equal
  ++ or false if x and y are not equal
  ++ or "failed" if this cannot be decided

But such a change would require changing almost every source file extensively
because of type incompatibility. A possible solution may be to change the
Boolean domain to be tri-valued with true, false and "failed" even though some
logicians probably won't like it. Existing code will continue to work after
recompiling (lines involving testing of equality may have to be modified to
accommodate new domains that uses the new Boolean). I have not thought about the
ramification of this though. Another way would be for these domains to add the
above signature in its exports but leave the usual "=" unimplemented.

Referring to print (coerce: %->OUT):
> For really top-notch output, there probably has to be a more general
> mechanism for deciding when to terminate power series or continued
> fractions or such, which depends on the available space.

I doubt there is such a general mechanism. Even for the examples above, it
depends on the convergent rates which is not only algorithm dependent but data
dependent and may even be platform and hardware dependent. So leaving the
"precision" up to the user is probably the best solution: setting the default to
a small value to give a feel of the result and letting the user increase
precision whenever desirable. For particular packages or domains, one can use
the system default, include a package or domain default, and allow user to
override these.

William
-- 
William Sit
Department of Mathematics..............Email: address@hidden
City College of New York..........................Tel: 212-650-5179
Convent Ave at West 138th Street..................Fax: 212-862-0004
New York, NY 10031.....Asian Symposium on Computer Mathematics 2003
USA..........................http://www.mmrc.iss.ac.cn/~ascm/ascm03