On 4/27/07, Robert Bradshaw <[EMAIL PROTECTED]> wrote:
> > A couple of points on square root. First, sqrt() and square_root()
> > can have different behavior.
After getting extensive user feedback, especially from younger
people, I've decided that having square_root and sqrt do different
things is very very confusing.
>> I think there are three possible
> > behaviours one might want:
> > 1. Return a real approximation. The main plus on this option is
> > that this is what many users will want if they ask for sqrt(2).
It really depends. I would say that most "normal" users want
something symbolic when they type "sqrt(2)" and most engineers want
sqrt(2) as a floating point number.
> > 2. Return an element of a quadratic extension. We can then have
> > one of the completions (or one of the pair of complex embeddings)
> > be distinguished. This just means that there's an automatic
> > coercion from QQ[sqrt(2)] to RR given by choosing the positive
> > square root. While not really canonical mathematically, it's
> > sufficiently standard that we should put it in. Users who want the
> > other embedding will be able to get it fairly easily.
Good.
> > 3. Return an integer (or rational) if n is a perfect square or
> > throw and error otherwise. This kind of behavior currently exists
> > for finite fields for example.
>
> Exactly what we were thinking.
>
> > My inclination would be to have sqrt do the first, and square_root
> > the second.
The fact we are even having this discussion illustrates that
square_root versus sqrt being different is confusing. Instead
we should have something like:
sqrt --- does number 2 above, or whatever the analogue is in
general, i.e., it tries to compute the square root as
exactly as possible. For lazy p-adics, it would be lazy,
for integers it would probably start by giving something
symbolic, then two weeks later, when number fields
improve, it would return a number field element exactly
as you suggest.
sqrt_exact -- tries to compute sqrt and raises an exception on
failure
sqrt_approx -- always returns a floating point square root.
This should be pushed throughout the system, and there should
also be functional notation for calling the above three. What do
you think?
>> Since 2 makes sense for pretty much every integral
> > domain (return x in the ring R[x]/(x^2 - a) if a does not have a
> > square root in R), maybe have square_root do that, and sqrt()
> > return an element of an algebraic completion for fields, and have
> > behavior 3 for rings?
Yes to the first in most cases. I don't know what "algebraic
completion" means.
> In terms of square roots (or nth roots, though (2) gets a bit more
> complicated), sqrt != square_root is probably going away (I guess too
> many other users found this confusing).
Yes, it is definitely going away.
>I think the square_root
> function should take a parameter to distinguish between the three
> types (with default 2? One can always do sqrt(2.0) or RR(sqrt(2)),
> etc. and I don't think causal users would be confused by \sqrt{2} as
> an answer). One could have actual functions for the types too. E.g.
> sqrt_approx, sqrt_extend, sqrt_exact(?).
Yes. That's almost exactly what I proposed above. I prefer
different function names, since the return results are so
different, and since there are three options. If it were just
one could have
def sqrt(self, exact=True, extend=True):
...
but it gets complicated because if exact=False, you also need
to be able to pass in an optional precision parameter. I think
I prefer three separate functions:
sqrt_approx, sqrt, sqrt_exact.
> >> Essentially, what we came up with is that (extra) implicit coercion
> >> morphisms could be specified at ring (object) creation time, which
> >> would be extra data attached to that specific ring, and the coercion
> >> model would detect and use those.
> >
> > I think I like using commutative diagrams better.
>
> I think they're complimentary. For natural (or conventional)
> morphisms I prefer commutative diagrams, but I think this would be
> useful for creating, say, a number field with a specific embedding
> into C. The commutative diagram itself should be immutable (in the
> sense that adjacent edges are only added (deleted) as rings are
> created (garbage collected).
Our idea was more that this diagram gets created at
runtime as references between objects. Having a separate
object (derived from graph) is more powerful though, since you
can compute the transitive closure, etc., and ensure that
various axiom are satisfied.
> As a specific example, what should sqrt(2) return? If the result lies
> in a number field (or Z[\sqrt(2] or whatever) we would want to equip
> this field with the extra information that the returned generator, by
> convention, gets sent to the positive square root of two (for use if
> one coerces into the symbolic ring or reals). The generic quadratic
> extension should not come with this kind of a map.
sqrt(2) could be an element of the number field K=Q[x]/(x^2-2)
*equipped* with an embedding map K --> SR that sends x to
the symbolic ring element sqrt(2). We could also equip K with maps
to RR, CC, etc., by choosing a root to some precision (which would
choose a root to any bigger precision automatically). More generally,
at creation time one could equip any ParentWithGens object with
a list of embedding morphisms that should be used by the coercion
system automatically. This list is would be immutable. So there
would be a new number field class NumberField_with_embedding(s).
> >> Also, one could implement a
> >> ambient_parent() method who would (if possible) return a new parent
> >> together with injections from each of the original rings. The lattice
> >> of number fields stuff would be used here.
> >
> > Yeah: an ambient_parent method could make sense in a
> > CoercionEnvironment (the minimal element among things mapped to
> > from both, if such exists, or error if there this element doesn't
> > exist or is not unique).
>
> Possibly one could be created too (like your number field examples).
>
> >> I like the idea of being able to use python contexts. I don't know
> >> how efficient one could make it though.
> >
> > In terms of efficiency, for elements with the same parent, there
> > will be no performance hit. After that, I don't think a context
> > would slow stuff down much if you did it right.
>
> After looking into the python context stuff more, I think I agree.
> All the expensive stuff could be handled at context enter/exit. All
> the (cached) information in the enclosing environment should be
> merged into the current environment to avoid traveling up the tree
> (as most coercions will probably still be defined at the outermost
> level, and every hashtable lookup can be expensive compared to the
> arithmetic itself.)
>
> I think I understand your proposal below. What I'm not clear on is
> how the entry/exit points do more than connect each separate category
> graph into one large graph with edges for "each (natural(ish))
> homomorphism A -> B in some suitably refined (wrt A and B) category."
> This may not be well defined, but I think it is the best a computer
> algebra system can do without forcing the user to do explicit
> coercions all over.
>
> (There is one advantage I see, namely that it favors coercions that
> remain within the category, but I believe this could be done anyway
> if there are several paths.)
> One can always extract the subgraph
> corresponding to a specific category, but we're already mixing
> categories with our objects (e.g. there is one object QQ that is used
> for as an object in Rings and Fields and Groups and Q-bar/Q modules,
> etc.)
>
> - Robert
>
> > I'd like to center the discussion on categories for a bit. Since
> > implicit coercion maps are supposed to be morphisms, they properly
> > have a category attached to them. So really, we should be asking:
> > If R and S are objects of a category C, we want to pick a
> > distinguished element of $Hom_C(R, S)$. So, given two parents R
> > and S, we choose a category C with a forgetful functor to the
> > category of parents and return a morphism in $Hom_C(R, S)$. So how
> > do we implement CoercionEnvironments?
> >
> > Every parent object implements a function called
> > _coercion_categories() which returns a list of categories that
> > parent belongs to. It doesn't have to be all categories that that
> > parent belongs to (clearly), but these categories will be the only
> > ones considered by the coercion code. The default implementation
> > is to just return the category of Parents (is this the same
> > category as the category Sets? I'm not sure...), and every
> > implementation should return Parents as one of the members of the
> > list.
> >
> > By a descendant of a category C I mean a category D such that there
> > is a forgetful functor from D to C. By an entry point of a
> > commutative diagram L in a category D I mean a morphism f in Hom_C
> > (A, B) where B is an object in L and D is a descendant of C. Exit
> > point is defined analogously. By an extended commutative diagram I
> > mean a commutative diagram with a list of entry and exit points.
> >
> > Each CoercionEnvironment has the following fields:
> > * an enclosing environment "encl" (another CoercionEnvironment)
> > * a dictionary "diagrams", with keys some collection of
> > categories, and diagrams[cat] an extended commutative diagram in
> > the category cat.
> > * a dictionary "coerce_maps" so that we don't have to find
> > coercion maps more than once.
> > and a function find_coerce_map(R, S) that does the following:
> > (note that the code below doesn't correctly handle cycles in diagrams)
> > def find_coerce_map(self, R, S):
> > """
> > Returns a coercion morphism from R to S, or None if none exists
> > in the current environment.
> >
> > Tests first to see if R and S are already cached in the
> > dictionary of known maps.
> > Next, checks to see if R and S both belong to one of the
> > diagrams and there's a path between them. If this is true for only
> > one of the diagrams, returns that map. If true for more than one,
> > raises an error.
> > Next, checks to see if R belongs to a diagram with exit points
> > and S to a diagram with entry points. If so, recursively tries to
> > find a coercion map from the codomain of an exit point of a diagram
> > to which R belongs to the domain of an entry point of a diagram to
> > which S belongs.
> > Finally, checks to see if there is an enclosing environment,
> > and if there is a coercion map in the enclosing environment.
> > """
> > if self.coerce_maps.has_key((R, S)):
> > return self.coerce_maps [(R, S)]
> > f = None
> > for cat in intersection(R._coercion_categories(),
> > S._coercion_categories):
> > if self.diagrams.has_key(cat) and R in self.diagrams[cat]
> > and S in self.diagrams[cat]:
> > path = self.diagrams[cat].path(R, S)
> > if path is not None:
> > if f is None:
> > f = path.compose()
> > else:
> > raise ValueError, "more than one coercion map
> > found"
> > if f is None:
> > for diag1 in self.diagrams.values() if R in diag1:
> > for diag2 in self.diagrams.values() if S in diag2:
> > for g in diag1.exit_points() if g.domain() is not R:
> > pathR = diag1.path(R, g.domain())
> > if pathR is not None:
> > for h in diag2.entry_points() if h.codomain
> > () is not S:
> > pathS = diag2.path(h.codomain(), S)
> > if pathS is not None:
> > e = self.find_coerce_map(g.codomain
> > (), h.domain())
> > if e is not None:
> > if f is None:
> > f = pathS.compose() * h *
> > e * g * pathR.compose()
> > else:
> > raise ValueError, "more
> > than one coercion map found"
> > if f is None and self.encl is not None:
> > f = self.encl.find_coerce_map(R, S)
> > self.coerce_maps[(R, S)] = f
> > return f
> >
> > Suggestions are welcome (especially thoughts on the giant nested
> > for loops).
They strike fear into my heart.
> > As an example, in the default environment, the diagrams[Rings]
> > diagram would include the ring morphism from ZZ to QQ sending 1 to
> > 1. Whenever you create a polynomial ring over a ring R it would
> > add a morphism from R to the polynomial ring embedding R as
> > constant polynomials. Whenever you create a quotient ring it would
> > add a morphism to the default diagram. Etc.
> >
> > When you create a finite field of prime order, diagrams
> > [FiniteFields] will add an entry point from ZZ to the prime field.
> > diagrams[FiniteFields] will then build a lattice of compatibly
> > embedded fields as you create new extension fields of that prime
> > field. Note that the diagrams can be disjoint unions of other
> > diagrams (in practice one might use a list of diagrams
> > instead...). I don't know yet how to make weakrefs work with this
> > whole scheme.
> >
> > David
--
William Stein
Associate Professor of Mathematics
University of Washington
http://www.williamstein.org
--~--~---------~--~----~------------~-------~--~----~
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/
-~----------~----~----~----~------~----~------~--~---
