Opened 5 months ago

Last modified 3 months ago

#30092 new enhancement

Categories of normed additive monoids/groups, normed modules/rings/fields, add FreeQuadraticModule to normed vector spaces

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-9.3
Component: linear algebra Keywords:
Cc: tscrim, sbrandhorst, gourgoulhon, gh-mjungmath Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: public/categories/normed_monoids-30092 (Commits) Commit: 656612e56a585f70da156db3ccd35ff74e2bfa63
Dependencies: #30062 Stopgaps:

Description (last modified by mkoeppe)

sage: VectorSpace(QQ, 5, inner_product_matrix=matrix.identity(5)).category()
Category of finite dimensional vector spaces with basis over (number fields and quotient fields and metric spaces)

As noted in #30061, it is not in the category MetricSpaces, and thus the element methods dist and abs (?!) are missing...

The methods __abs__, norm, and dot_product are unrelated to the inner product matrix; only inner_product uses inner_product_matrix.

We define a category NormedVectorSpaces with element method abs.

We deprecate the MetricSpaces element method abs.

Follow-up: #30218: Category InnerProductSpaces


Random references:

Change History (52)

comment:1 Changed 5 months ago by mkoeppe

Also, the classes in sage.modules do not make it possible to pass a category argument at initialization.

comment:2 Changed 5 months ago by mkoeppe

  • Description modified (diff)

comment:3 Changed 5 months ago by mkoeppe

  • Dependencies set to #30062

comment:4 Changed 5 months ago by mkoeppe

  • Cc gourgoulhon gh-mjungmath added
  • Description modified (diff)

comment:5 Changed 5 months ago by mkoeppe

  • Branch set to u/mkoeppe/category_inner_product_spaces

comment:6 Changed 5 months ago by mkoeppe

  • Commit set to 26e9c8fe08f75c52ed79c43e5ead09320e6485b6

I have here a preliminary implementation (trying to learn from FilteredModules and MetricSpaces) of NormedSpacesCategory and NormedVectorSpaces.

Travis, if you could take a quick look to see if this seems to be going in the right direction...


New commits:

1f4f942Provide EuclideanSpace with dist() method and add it to category of metric space
7a92b60sage.categories.metric_spaces.MetricSpaces: Rename metric to metric_function with deprecation
3ee003aMerge branch 't/30062/public/manifolds/euclidean_metric_space' into t/30092/category_inner_product_spaces
26e9c8fNormedVectorSpaces: New
Last edited 5 months ago by mkoeppe (previous) (diff)

comment:7 Changed 5 months ago by tscrim

Why is this a functorial construction and not an axiom? I don't see why this wouldn't commute with other axioms, such as WithBasis.

comment:8 Changed 5 months ago by mkoeppe

Thanks. I'll look into this.

comment:9 Changed 5 months ago by tscrim

Ah, no, this is good. I thought I implemented metric spaces as an axiom, but it is a functorial construction. So please keep the current approach.

comment:10 Changed 5 months ago by mkoeppe

Thanks. I am still quite confused about many basic things in the category system, thanks for your patience. I am getting this:

sage: VectorSpaces(QQ).Filtered().Normed()
Join of Category of filtered vector spaces over Rational Field and Category of metric spaces

What am I missing for "normed spaces" to show up?

comment:11 Changed 5 months ago by tscrim

Try

-class NormedSpacesCategory(RegressiveCovariantConstructionCategory, Category_over_base_ring):
+class NormedSpacesCategory(RegressiveCovariantConstructionCategory):

comment:12 Changed 5 months ago by tscrim

Also remove the __init__.

comment:13 Changed 5 months ago by git

  • Commit changed from 26e9c8fe08f75c52ed79c43e5ead09320e6485b6 to 5eee4c108479901439003f8061cc09b6df77d605

Branch pushed to git repo; I updated commit sha1. New commits:

8651b8bFix syntax
5eee4c1Add doc

comment:14 Changed 5 months ago by tscrim

I also have a question. Do we need this to be be a subcategory for vector spaces? I would think it would be sufficient for a module structure for the definition to make sense. For example, Z is naturally a normed Z-module that is not a vector space.

Addendum - Well, we actually need normed fields and rings as well for this to make sense. In fact, any additive monoid with a metric (function) becomes naturally normed. So we should also set that additional category link. I am not sure how to do that off-hand.

Last edited 5 months ago by tscrim (previous) (diff)

comment:15 Changed 5 months ago by mkoeppe

Well, I wanted NormedSpacesCategory to actually work also for modules, but I did not want to introduce the word "normed module" -- because this does not seem to be in widespread use.

comment:16 Changed 5 months ago by tscrim

However, moving it up one category level higher is a no-cost operation. Plus it means you don't have to deal with distinguishing the two categories (which can be slightly annoying at times).

comment:17 Changed 5 months ago by mkoeppe

Still getting

sage: VectorSpaces(QQ).Filtered().Normed()
Join of Category of filtered vector spaces over Rational Field and Category of metric spaces

after the changes from your comments 11/12

comment:18 Changed 5 months ago by git

  • Commit changed from 5eee4c108479901439003f8061cc09b6df77d605 to c06735c5c380254f4d332981e60d3f74c6568e79

Branch pushed to git repo; I updated commit sha1. New commits:

70aed56simplify NormedSpacesCategory as suggested by Travis
c06735cDraft of parent methods

comment:19 Changed 5 months ago by mkoeppe

Of course, there's always more generality. Here's one: https://mathworld.wolfram.com/NormedBanachModule.html

comment:20 Changed 5 months ago by mkoeppe

and we could do https://en.wikipedia.org/wiki/Normed_algebra (which places a restriction on the norm wrt multiplication)

... but I was hoping to first implement things that would be useful in a first course in linear algebra.

comment:21 Changed 5 months ago by mkoeppe

Another direction of generalization is, of course, through valuations on the field; instead of just informally using the absolute value function...

comment:22 follow-up: Changed 5 months ago by tscrim

I am not really sure at this point why it is not working from looking at the code. The only thing I can think of at this point is that default_super_categories is not picking up the vector spaces category somehow. Perhaps something to look at is what is happening here

        return Category.join([getattr(cat, cls._functor_category)(*args)
                              for cat in category._super_categories
                              if hasattr(cat, cls._functor_category)])

in CovariantConstructionCategory.default_super_categories. I can do some experimentation when I get back to my office on Monday.

I generally prefer to implement things in the first category where they make sense, which then follows up to the category that I really want it.

The other issue here is that you need the other normed categories in order for the definition of a norm to make sense. So they kind of have to come along for the ride. However, it should be easy enough to use the same functorial construction, the meaning of the word "normed" changes slightly, but everything is compatible, so there is no issue (and it is something we regularly do in the math).

comment:23 Changed 5 months ago by mkoeppe

Thanks a lot already!

comment:24 Changed 5 months ago by git

  • Commit changed from c06735c5c380254f4d332981e60d3f74c6568e79 to 5fe03807ec7eb95f9363cad6e9462ffad3eed228

Branch pushed to git repo; I updated commit sha1. New commits:

5fe0380Draft of _test_norm_function

comment:25 in reply to: ↑ 22 Changed 5 months ago by mkoeppe

Replying to tscrim:

I generally prefer to implement things in the first category where they make sense, which then follows up to the category that I really want it.

Right. It looks it's best to start with normed additive groups (https://ncatlab.org/nlab/show/normed+group) - which use slightly weaker conditions.

The other issue here is that you need the other normed categories in order for the definition of a norm to make sense. So they kind of have to come along for the ride. However, it should be easy enough to use the same functorial construction, the meaning of the word "normed" changes slightly, but everything is compatible, so there is no issue (and it is something we regularly do in the math).

I agree, this type of overloading seems unproblematic in this case.

comment:26 follow-up: Changed 5 months ago by sbrandhorst

I didn't have time to look at this. Just in case: Please be aware that there are no restrictions whatsoever on the inner product. It is just a bilinear form. For instance it could be zero.

comment:27 in reply to: ↑ 26 Changed 5 months ago by mkoeppe

Replying to sbrandhorst:

Please be aware that there are no restrictions whatsoever on the inner product. It is just a bilinear form. For instance it could be zero.

Thanks. This is important to keep it mind.

comment:28 Changed 5 months ago by tscrim

I figured out the problem: There is no link to the NormedVectorSpaces. So you need to add this to VectorSpaces:

    Normed = LazyImport('sage.categories.normed_vector_spaces', 'NormedVectorSpaces',
                        'Normed')

However, as we discussed, we wanted to lift this up. Are you currently working on this or would you like me to do it?

comment:29 Changed 5 months ago by mkoeppe

Please go ahead, I can't work on this until mid next week.

comment:30 Changed 5 months ago by mkoeppe

(Mid this week in your timezone)

comment:31 Changed 5 months ago by tscrim

  • Branch changed from u/mkoeppe/category_inner_product_spaces to public/categories/normed_monoids-30092
  • Commit changed from 5fe03807ec7eb95f9363cad6e9462ffad3eed228 to cc9d23417d643ff095537ade7d5a8bdb171be2ba

It is still lacking a bit in implementation, but here is a proof-of-concept for the normed (additive) monoids and various other subcategories with concrete implementations for ZZ and QQ (which likely require more trivial doctest changes throughout Sage, but we should get all of the categories that we want done first in case it causes the output to change).


New commits:

cc9d234Creating category for normed (additive) monoids, groups, modules, and rings.

comment:32 Changed 5 months ago by mkoeppe

Thanks very much! Looks great on a quick glance -- I'll take a closer look soon

comment:33 follow-up: Changed 5 months ago by mkoeppe

Some quick thoughts on the test functions.

  • _test_norm_additive in AdditiveSemigroups ... perhaps change to _test_norm_on_additive_monoid
  • the one in additive groups - perhaps just have _test_norm_symmetric and use the inherited _test_norm_on_additive_monoid - if that makes sense
  • _test_norm_multiplication ... likewise change to test_norm_on_multiplicative_monoid
Last edited 5 months ago by mkoeppe (previous) (diff)

comment:34 Changed 5 months ago by git

  • Commit changed from cc9d23417d643ff095537ade7d5a8bdb171be2ba to 6bc0264f49583f232fcb778e456a52508673b6bd

Branch pushed to git repo; I updated commit sha1. New commits:

6bc0264Separating the inverse norm tests into a separate test method.

comment:35 in reply to: ↑ 33 ; follow-up: Changed 5 months ago by tscrim

Replying to mkoeppe:

Some quick thoughts on the test functions.

  • _test_norm_additive in AdditiveSemigroups ... perhaps change to _test_norm_on_additive_monoid
  • _test_norm_multiplication ... likewise change to test_norm_on_multiplicative_monoid

I don't want to do that for the multiplicative test because a ring, which is a monoid, does not satisfy the normed monoid properties because the norm of the multiplicative identity is not 0. I guess that actually means this is not a regressive functorial construction. We only get a semigroup with a "weak norm," a function S -> R that satisfies |ab| <= |a| + |b| (do you know if something like this has a name?). Or we just have to acknowledge the abuse somewhere.

  • the one in additive groups - perhaps just have _test_norm_symmetric and use the inherited _test_norm_on_additive_monoid - if that makes sense

That is a good idea. Done.

comment:36 in reply to: ↑ 35 Changed 5 months ago by mkoeppe

Replying to tscrim:

Replying to mkoeppe:

Some quick thoughts on the test functions.

  • _test_norm_additive in AdditiveSemigroups ... perhaps change to _test_norm_on_additive_monoid
  • _test_norm_multiplication ... likewise change to test_norm_on_multiplicative_monoid

I don't want to do that for the multiplicative test because a ring, which is a monoid, does not satisfy the normed monoid properties because the norm of the multiplicative identity is not 0. I guess that actually means this is not a regressive functorial construction. We only get a semigroup with a "weak norm," a function S -> R that satisfies |ab| <= |a| + |b| (do you know if something like this has a name?). Or we just have to acknowledge the abuse somewhere.

Let's see. I think this just means that there should be a separate category/functor for normed multiplicatively written monoids - satisfying |ab| <= |a| + |b| (and then multiplicative identities necessarily have norm 0). Call it MultiplicativeNormed. Just like AdditiveCommutative and Commutative are distinguished.

This has nothing to do with the positive homogeneity property of norms on modules.

comment:37 Changed 5 months ago by mkoeppe

... OK, I forgot about rings.

Yes, there needs to be a _test_norm_submultiplicative that tests the ring multiplication. (That's in the category Normed - not MultiplicativeNormed.)

Last edited 5 months ago by mkoeppe (previous) (diff)

comment:38 Changed 5 months ago by mkoeppe

I'll make a few quick edits

comment:39 Changed 5 months ago by git

  • Commit changed from 6bc0264f49583f232fcb778e456a52508673b6bd to 8b9ba0bafba2fa7f687dae16d1e9c14d0a5a356f

Branch pushed to git repo; I updated commit sha1. New commits:

8b9ba0bRename/split some test methods

comment:40 Changed 5 months ago by mkoeppe

more on another day

comment:41 follow-up: Changed 4 months ago by tscrim

I am -1 on calling the test norm_symmetric since I think that is too vague of a name. Are there objects that satisfy both the multiplicative and additive inverse norm properties? If so, then there will be a name clash too.

I think splitting the tests into finer pieces with finer categories is the right way to do things. The submultiplicative can then go into a new normed semigroups (maybe magmas?) category, etc.

comment:42 in reply to: ↑ 41 ; follow-up: Changed 4 months ago by mkoeppe

Replying to tscrim:

I am -1 on calling the test norm_symmetric since I think that is too vague of a name.

OK, I agree.

Are there objects that satisfy both the multiplicative and additive inverse norm properties? If so, then there will be a name clash too.

Haven't seen and I don't think it would be useful.

I think splitting the tests into finer pieces with finer categories is the right way to do things. The submultiplicative can then go into a new normed semigroups (maybe magmas?) category, etc.

We could also make norm a map and then go through #30193...

comment:43 in reply to: ↑ 42 ; follow-ups: Changed 4 months ago by tscrim

Replying to mkoeppe:

Replying to tscrim:

Are there objects that satisfy both the multiplicative and additive inverse norm properties? If so, then there will be a name clash too.

Haven't seen and I don't think it would be useful.

I agree, but sometimes you never know...

I think splitting the tests into finer pieces with finer categories is the right way to do things. The submultiplicative can then go into a new normed semigroups (maybe magmas?) category, etc.

We could also make norm a map and then go through #30193...

Possibly. Although at least for now we can implement everything here in the respective categories and refine it later on (well, just moving the respective methods around).

comment:44 in reply to: ↑ 43 ; follow-up: Changed 4 months ago by mkoeppe

Replying to tscrim:

Although at least for now we can implement everything here in the respective categories and refine it later on (well, just moving the respective methods around).

OK, sounds like a plan. I'll work on it a little bit now

comment:45 in reply to: ↑ 44 ; follow-up: Changed 4 months ago by tscrim

Replying to mkoeppe:

Replying to tscrim:

Although at least for now we can implement everything here in the respective categories and refine it later on (well, just moving the respective methods around).

OK, sounds like a plan. I'll work on it a little bit now

Thank you. I can probably do it today too if you want.

comment:46 Changed 4 months ago by git

  • Commit changed from 8b9ba0bafba2fa7f687dae16d1e9c14d0a5a356f to 656612e56a585f70da156db3ccd35ff74e2bfa63

Branch pushed to git repo; I updated commit sha1. New commits:

656612eRename test functions, avoid 'symmetric'

comment:47 in reply to: ↑ 43 Changed 4 months ago by mkoeppe

Replying to tscrim:

Replying to mkoeppe:

Replying to tscrim:

Are there objects that satisfy both the multiplicative and additive inverse norm properties? If so, then there will be a name clash too.

I would suggest that we just ignore norms on multiplicative monoids on this ticket.

Then we can decide later whether we want the shared code to go through axioms on functionals, or through other means.

Also, norms on multiplicative monoids have a close connection to valuations on fields -- and getting all of that right on one ticket is too large a scope.

comment:48 in reply to: ↑ 45 Changed 4 months ago by mkoeppe

Replying to tscrim:

I can probably do it today too if you want.

Feel free to take over -- I have to take a break for dinner now anyway

comment:49 Changed 4 months ago by mkoeppe

  • Description modified (diff)
  • Summary changed from FreeQuadraticModule needs richer categories to Categories of normed additive monoids/groups, normed modules/rings/fields, add FreeQuadraticModule to normed vector spaces

comment:50 Changed 4 months ago by mkoeppe

Narrowed the ticket description

comment:51 Changed 4 months ago by mkoeppe

  • Description modified (diff)

comment:52 Changed 3 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3
Note: See TracTickets for help on using tickets.