Free modules

[Simon King]

Hi!

I thought that there already was a ticket for the topic discussed at
http://groups.google.com/group/sage-algebra/browse_thread/thread/1a1f78d89158fd56/5224e265ba5afc7?q=inner_product_matrix#05224e265ba5afc7

But apparently there isn't, and apparently I can't reply to the
original thread.

So, let's start a new thread.

Problem: Free modules are currently not using the coercion model
properly. For example, they do not define _coerce_map_from_.

Question 1:
Submodules do not define their embedding into the ambient module as
coercion.
sage: M = FreeModule(ZZ,3,inner_product_matrix=Matrix(3,3,range(9)))
sage: S = M.submodule([M.random_element(),M.random_element()])
sage: S.coerce_embedding() is None
True

Should this be changed?

Question 2:
When should there be a coercion from free (abstract, non-embedded)
modules M to N?

Certainly we need coercion from M.base_ring() to N.base_ring() and M.
Also, we need M.rank()==N.rank() and M.degree()==N.degree().

In the other thread, it seemed to be agreement that, if N has an inner
product matrix defined by the user (this can be tested with
is_FreeQuadraticModule), then a coercion from M to N requires that M
has the same inner product matrix (either by default or user-defined).
If N has no explicit inner product, then we may have the forgetful
coercion from M to N.

Question 2a):
Apparently there is a sparse and a dense implementation of free
modules. Should a coercion be allowed in both directions? Only from
sparse to dense (it seems that dense is default)? Only from dense to
sparse?

Question 2b):
What about sub-modules? I guess we don't want coercion from an
abstract free module into a sub-module. Presumably a sub-module M (of
an ambient module A) coerces into a sub_module N (of an ambient module
B) if and only if there is coercion from A to B that sends M to a
subset of N.

Question 3:
I guess it is straight forward that pushout(A,B) of two sub-modules A
of M and B of N (hence, the structure in which arithmetic between
elements of A and B is performed) will be the submodule of
pushout(M,N) that is generated by the images of A and B. Agreed?

Best regards,
Simon

[David R. Kohel]

Hi,

Below is a response that I began. The issues raised here made me
realise that I didn't and don't understand what the coercion model
is supposed to model. Is there an article available which sets
out the definitions, problems or issues, and solution provided
by the coercion model? Such a document would be helpful to avoid
reinventing for each category what the model is supposed to do and
ending up with incoherent decisions, based on what seems natural
in individual contexts. The "correct" behavior, even if at first
counterintuitive, should be determined by general principles.

I'll send the rest of the (incomplete) message as is.

Best,

David

> Problem: Free modules are currently not using the coercion model
> properly. For example, they do not define _coerce_map_from_.
>
> Question 1:
> Submodules do not define their embedding into the ambient module as
> coercion.
> sage: M = FreeModule(ZZ,3,inner_product_matrix=Matrix(3,3,range(9)))
> sage: S = M.submodule([M.random_element(),M.random_element()])
> sage: S.coerce_embedding() is None
> True
>
> Should this be changed?

Sure.

> Question 2:
> When should there be a coercion from free (abstract, non-embedded)
> modules M to N?

Clearly when:

M is N
M is created as a free submodule of N (as above), extended
to the lattice of submodules of some fixed ambient module.
N is created as a quotient of M (probably not implemented
in such a way that this can be determined).

> Certainly we need coercion from M.base_ring() to N.base_ring() and M.
> Also, we need M.rank()==N.rank() and M.degree()==N.degree().

This would effectively identify all free modules of the same rank
and degree. I would have a better understanding of the idea of
the coercion model (and where it is applied) to know whether
isomorphic-but-not-canonically-isomorphic objects are supposed
to have a coercion between them. This is analogous to the question
about distinct but isomorphic number fields with or without the
same defining polynomials (with the same polynomials they are
computationally, but not necessarily canonically isomorphic).

> In the other thread, it seemed to be agreement that, if N has an inner
> product matrix defined by the user (this can be tested with
> is_FreeQuadraticModule), then a coercion from M to N requires that M
> has the same inner product matrix (either by default or user-defined).
> If N has no explicit inner product, then we may have the forgetful
> coercion from M to N.

Comment (*):
This is essentially a question of different categories -- if the
category of the free module is that of inner product spaces, then
there are fewer (homo)morphisms. But I don't know if the coercion
model adopts such a strong categorical hierarchy. It seems to mix
canonical homomorphisms in a category with functors between categories.

> Question 2a):
> Apparently there is a sparse and a dense implementation of free
> modules. Should a coercion be allowed in both directions? Only from
> sparse to dense (it seems that dense is default)? Only from dense to
> sparse?

This concerns implementation or performance issues of writing out
sparse matrices as dense ones or expressing a dense matrix in a
form in which it would be more expensive. But both coercions seem
important to easily convert between types.

> Question 2b):
> What about sub-modules? I guess we don't want coercion from an
> abstract free module into a sub-module. Presumably a sub-module M (of
> an ambient module A) coerces into a sub_module N (of an ambient module
> B) if and only if there is coercion from A to B that sends M to a
> subset of N.
>
> Question 3:
> I guess it is straight forward that pushout(A,B) of two sub-modules A
> of M and B of N (hence, the structure in which arithmetic between
> elements of A and B is performed) will be the submodule of
> pushout(M,N) that is generated by the images of A and B. Agreed?

My comment (*) makes it clear (to me) that I don't know what the
coercion model is supposed to model (functors or homomorphisms).

[Simon King]

Hi David,

On 8 Dez., 11:49, "David R. Kohel" <ko...@iml.univ-mrs.fr> wrote:
> Is there an article available which sets
> out the definitions, problems or issues, and solution provided
> by the coercion model?

After a talk on coercion that I gave at some Sage Day in Hagenberg, it
was suggested to write such paper. While I think I understand how the
"pushout" construction is implemented, I would definitely not be
competent enough to write a paper on the whole coercion model without
someone else (Robert Bradshaw, e.g.).

> > Question 1:
> > Submodules do not define their embedding into the ambient module as
> > coercion.
> > sage: M = FreeModule(ZZ,3,inner_product_matrix=Matrix(3,3,range(9)))
> > sage: S = M.submodule([M.random_element(),M.random_element()])
> > sage: S.coerce_embedding() is None
> > True
>
> > Should this be changed?
>
> Sure.

Yep, seems really natural.

> > Question 2:
> > When should there be a coercion from free (abstract, non-embedded)
> > modules M to N?
>
> Clearly when:
>
>   M is N
>   M is created as a free submodule of N (as above), extended
>     to the lattice of submodules of some fixed ambient module.

I think the extension to the lattice of submodules is automatic.

>   N is created as a quotient of M (probably not implemented
>     in such a way that this can be determined).

No, that's easy. A quotient module V/W knows its quotient map V -> V/
W, hence, it knows V.

But I was talking here about *abstract* (i.e., not embedded and not
quotiented) modules.

> > Certainly we need coercion from M.base_ring() to  N.base_ring() and M.
> > Also, we need M.rank()==N.rank() and M.degree()==N.degree().
>
> This would effectively identify all free modules of the same rank
> and degree.  I would have a better understanding of the idea of
> the coercion model (and where it is applied) to know whether
> isomorphic-but-not-canonically-isomorphic objects are supposed
> to have a coercion between them.

Isn't it related with "unique parent structures"? Example:
sage: QQ^2 is QQ^2
True

Certainly there is no canonical isomorphism between two 2-dimensional
vector spaces over QQ. But the vector spaces in Sage all seem to come
with a fixed basis - and then, mapping basis vectors one-to-one seems
rather canonical to me. And in that situation, Sage tends to not only
have a coercion but actually an identification (QQ^2 *is* QQ^2).

>  This is analogous to the question
> about distinct but isomorphic number fields with or without the
> same defining polynomials (with the same polynomials they are
> computationally, but not necessarily canonically isomorphic).

Again, if there is no embedding, Sage would actually say that these
objects are not only canonically isomorphic (since there is a fixed
generator, it is canonical to map the fields by sending generator to
generator) but actually identical:

sage: K.<t> = NumberField(x^2+1)
sage: K is NumberField(x^2+1,name='t')
True

> Comment (*):
> This is essentially a question of different categories -- if the
> category of the free module is that of inner product spaces, then
> there are fewer (homo)morphisms.  But I don't know if the coercion
> model adopts such a strong categorical hierarchy.

To my understanding, the coercion model says that a coercion should be
a morphism in an *appropriate* category. A priori (hence, on the level
of the model) it is not defined what "appropriate" means -- that's
about the implementation of the model (not about the model itself) and
is the point where the developers need to make decisions, which are
also based on the expectations of the users.

So, the question is whether we want a coercion from an inner product
space to its underlying free module, of course in the category of free
modules. Sub-question: What would the user expect?
Restrictive answer:
If s/he defines an inner product then this structure apparently is
important and should be preserved by coercion.
Permissive answer:
If the user tries to add an element of an inner product space to
an element of its underlying free module, then s/he apparently does
not care much about the inner product, for otherwise s/he would not
use an element of the underlying free module. So, it is OK to let the
sum live in the underlying free module.

>  It seems to mix
> canonical homomorphisms in a category with functors between categories.

No, but it relies on *our* decision to what extent we are willing to
consider an object of a category as an object of a super-category.

> This concerns implementation or performance issues of writing out
> sparse matrices as dense ones or expressing a dense matrix in a
> form in which it would be more expensive.  But both coercions seem
> important to easily convert between types.

Agreed.

> > Question 3:
> > I guess it is straight forward that pushout(A,B) of two sub-modules A
> > of M and B of N (hence, the structure in which arithmetic between
> > elements of A and B is performed) will be the submodule of
> > pushout(M,N) that is generated by the images of A and B. Agreed?
>
> My comment (*) makes it clear (to me) that I don't know what the
> coercion model is supposed to model (functors or homomorphisms).

Let me try to rephrase:

Assume that we have two chains of sub-modules, S1 in S2 in M and T1 in
T2 in M.
In question 2 I asked if we agree that the pushout of S2 and T2 should
be the sub-module of M that is spanned by S2 and T2. I think that's
natural.

Now question 3 is: Do we want that the pushout of S1 and T1 is a sub-
module of pushout(S2,T2)? Or a sub-module of M? Or not defined at all
(No!)?

Cheers,
Simon