On Apr 27, 2007, at 12:50 AM, David Roe wrote:
> A couple of points on square root. First, sqrt() and square_root()
> can have different behavior. 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).
> 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.
> 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. 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?
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). 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(?).
>> 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).
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.
>> 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).
>
> 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
--~--~---------~--~----~------------~-------~--~----~
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/
-~----------~----~----~----~------~----~------~--~---
