Opened 8 years ago

Closed 3 months ago

# Uniformize the API to compute the inverse of an element

Reported by: Owned by: Nicolas M. Thiéry major sage-9.8 categories Franco Saliola, Vincent Delecroix, Simon King, Samuel Lelièvre, Travis Scrimshaw Frédéric Chapoton Travis Scrimshaw N/A 312a91d 312a91d4f327802ca1e6d48975cd1d221128833e

Some classes in Sage implement the inverse of an element through the inverse method:

```mistral-/opt/sage/src/sage>grep "def inverse(" **/*.py
algebras/finite_dimensional_algebras/finite_dimensional_algebra_element.py:    def inverse(self):
algebras/iwahori_hecke_algebra.py:            def inverse(self):
categories/coxeter_groups.py:        def inverse(self):
combinat/affine_permutation.py:    def inverse(self):
combinat/permutation.py:    def inverse(self):
combinat/tableau_tuple.py:    def inverse(self,k):
crypto/classical_cipher.py:    def inverse(self):
crypto/classical_cipher.py:    def inverse(self):
crypto/classical_cipher.py:    def inverse(self):
crypto/classical_cipher.py:    def inverse(self):
dynamics/interval_exchanges/iet.py:    def inverse(self):
groups/abelian_gps/element_base.py:    def inverse(self):
groups/abelian_gps/values.py:    def inverse(self):
groups/affine_gps/group_element.py:    def inverse(self):
modules/matrix_morphism.py:    def inverse(self):
rings/number_field/class_group.py:    def inverse(self):
rings/universal_cyclotomic_field/universal_cyclotomic_field.py:        def inverse(self):
schemes/elliptic_curves/formal_group.py:    def inverse(self, prec=20):
schemes/elliptic_curves/weierstrass_transform.py:    def inverse(self):
```

Some other through the `__invert__` method:

```mistral-/opt/sage/src/sage>grep "def __invert__(" **/*.py
categories/algebras_with_basis.py:        def __invert__(self):
categories/magmas.py:                def __invert__(self):
categories/modules_with_basis.py:    def __invert__(self):
categories/modules_with_basis.py:    def __invert__(self):
combinat/combinatorial_algebra.py:    def __invert__(self):
combinat/sf/dual.py:        def __invert__(self):
combinat/species/generating_series.py:    def __invert__(self):
groups/indexed_free_group.py:        def __invert__(self):
groups/indexed_free_group.py:        def __invert__(self):
groups/matrix_gps/group_element.py:    def __invert__(self):
groups/raag.py:        def __invert__(self):
libs/coxeter3/coxeter_group.py:        def __invert__(self):
logic/boolformula.py:    def __invert__(self):
misc/sage_input.py:    def __invert__(self):
modular/dirichlet.py:    def __invert__(self):
modular/local_comp/smoothchar.py:    def __invert__(self):
modules/matrix_morphism.py:    def __invert__(self):
rings/continued_fraction.py:    def __invert__(self):
rings/finite_rings/element_ext_pari.py:    def __invert__(self):
rings/function_field/function_field_ideal.py:    def __invert__(self):
rings/infinity.py:    def __invert__(self):
rings/multi_power_series_ring_element.py:    def __invert__(self):
rings/number_field/morphism.py:    def __invert__(self):
rings/number_field/number_field_ideal.py:    def __invert__(self):
rings/number_field/number_field_ideal_rel.py:    def __invert__(self):
rings/pari_ring.py:    def __invert__(self):
rings/polynomial/polynomial_quotient_ring_element.py:    def __invert__(self):
rings/qqbar.py:    def __invert__(self):
rings/quotient_ring_element.py:    def __invert__(self):
rings/universal_cyclotomic_field/universal_cyclotomic_field.py:        def __invert__(self):
sandpiles/sandpile.py:    def __invert__(self):
schemes/elliptic_curves/heegner.py:    def __invert__(self):
schemes/elliptic_curves/height.py:    def __invert__(self):
schemes/elliptic_curves/weierstrass_morphism.py:    def __invert__(self):
schemes/elliptic_curves/weierstrass_morphism.py:    def __invert__(self):
schemes/hyperelliptic_curves/monsky_washnitzer.py:    def __invert__(self):
structure/factorization.py:    def __invert__(self):
```

Usually they provide a crosslink so that `__invert__` and `inverse` are equivalent, but this is done on a case by case bases, so of course such links are missing here and there:

```sage: ~AA(sqrt(~2))
1.414213562373095?
sage: AA(sqrt(~2)).inverse()
...
AttributeError: 'AlgebraicReal' object has no attribute 'inverse'
```
```sage: R.<u,v,w> = QQ[]
sage: f = EllipticCurve_from_cubic(u^3 + v^3 + w^3, [1,-1,0], morphism=True)
sage: f.inverse()
Scheme morphism:
...
sage: ~f
...
TypeError: bad operand type for unary ~: 'WeierstrassTransformationWithInverse_class'
```

Shall we change the code to systematically implement `__invert__` as per Python's convention, and then implement the cross link `inverse` -> `__invert__` once for all high up in the class hierarchy, typically in `Magmas.ElementMethods`?

Caveat: this won't cover all cases since we have invertible elements that don't belong to a magma; e.g. a isomorphisms between two different parents; so it will still be necessary to handle a couple special cases by hand.

See also comment about `__inverse__` in sage.categories.coxeter_groups.py around line 699.

Note: the default implementation ~f = 1/f provided by Element should probably be implemented in `Monoids.ElementMethods`; see also #17692.

Note: the qqbar classes also implement an `invert` method, but that's for a slightly different use case. So we may, or not, want to make this uniform too. `invert` does not fit Sage's usual verb/noun convention since it's a verb while it is not inplace.

### comment:1 Changed 8 years ago by Nicolas M. Thiéry

Description: modified (diff)

### comment:2 Changed 2 years ago by Frédéric Chapoton

Authors: → Frédéric Chapoton → u/chapoton/17965 → 99d9b6cbb562c87e87ca0fc2a6465b387e486157 new → needs_review

Here is a first attempt. Opinions ?

New commits:

 ​99d9b6c `convert some .inverse to .__invert__ and make a global alias in magmas cat`

### comment:3 Changed 2 years ago by git

Commit: 99d9b6cbb562c87e87ca0fc2a6465b387e486157 → 1a1ec14fcae40bc98284b74ef3a2d3d5e55461a6

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

 ​1a1ec14 `fix some details`

### comment:4 Changed 2 years ago by Markus Wageringel

In general I think unifying this is a good idea. Something to keep in mind is that `__invert__` will not show up in the documentation, by default. If in some cases there are extensive examples, it could be added to the documentation using `automethod`, though. Probably this is not needed for most of the elements, but in #29723 (inverses of ring homomorphisms) this is the reason why I linked `__invert__` to `inverse`.

### comment:5 Changed 2 years ago by git

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

 ​9d5692d `fix some doctests in polynomial quotient rings`

### comment:6 Changed 2 years ago by Frédéric Chapoton

Milestone: sage-6.6 → sage-9.2

### comment:7 Changed 2 years ago by git

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

 ​fbc929e `some pycodestyle details (breaking some lines after : and ;)`

### comment:8 Changed 2 years ago by git

Commit: fbc929ef8a01b017641838c47287e141ea96f8f4 → 2962668d234c07498c652c66f8b2de44479dcd21

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

 ​2962668 `fix one wrong use of parent`

### comment:9 Changed 2 years ago by Frédéric Chapoton

oh, boy, now with an infinite loop in

```sage -t --long --warn-long 61.5 src/sage/monoids/free_monoid_element.py
```

### comment:10 Changed 2 years ago by Frédéric Chapoton

Status: needs_review → needs_work

### comment:11 Changed 2 years ago by git

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

 ​637f8bd `Merge branch 'u/chapoton/17965' of ssh://trac.sagemath.org:22/sage in 9.2.b8` ​5e7e19a `tentative fix, move inversion to monoids`

### comment:12 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.2 → sage-9.3

### comment:13 Changed 2 years ago by git

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

 ​dc2e65f `Merge branch 'u/chapoton/17965' in 9.3.b0`

### comment:14 Changed 2 years ago by git

Commit: dc2e65f80dbd67279f37e07f24b861c0cc7d7e27 → bc7fe1e67d9788991fdb5f1487d14c3ac44a4f68

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

 ​7ddf35e `Merge branch 'u/chapoton/17965' in 9.3.b1` ​bc7fe1e `add doctests in free_monoid_element`

### comment:15 Changed 2 years ago by Frédéric Chapoton

I am thinking to move the "Inverse" axioms from magmas to monoids.

Because the notion of inverse does not really make sense in magmas, where left and right inverses can be different.

```src/sage/categories/magmas.py:        class Inverse(CategoryWithAxiom):
```

### comment:16 Changed 2 years ago by Nicolas M. Thiéry

We may eventually need to have weaker axioms LeftInverses? and RightInverses?. But is there an inconvenient in having an axiom that states the existence of both a left and right inverse that coïncide?

### comment:17 Changed 2 years ago by Frédéric Chapoton

Hé, salut. J'essaye juste de démeler la situation, et j'ai une boucle infinie magma->monoid->magma etc etc

### comment:18 Changed 2 years ago by Nicolas M. Thiéry

Salut Frédéric :-)

Ah I see; things like this indeed happen, though hopefully there is a way out. If it can help, we could have a live chat about it, though not before Tuesday.

Amitiés,

### comment:19 Changed 22 months ago by Matthias Köppe

Milestone: sage-9.3 → sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

### comment:20 Changed 17 months ago by Matthias Köppe

Milestone: sage-9.4 → sage-9.5

Setting a new milestone for this ticket based on a cursory review.

### comment:21 Changed 12 months ago by Matthias Köppe

Milestone: sage-9.5 → sage-9.6

### comment:22 Changed 8 months ago by Matthias Köppe

Milestone: sage-9.6 → sage-9.7

### comment:23 Changed 7 months ago by git

Commit: bc7fe1e67d9788991fdb5f1487d14c3ac44a4f68 → a4f176d870fb79a8a82a7bfb7b5c24b6d302e947

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

 ​a4f176d `Merge branch 'u/chapoton/17965' in 9.7.b0`

### comment:24 Changed 7 months ago by git

Commit: a4f176d870fb79a8a82a7bfb7b5c24b6d302e947 → b5402d06f7a69f2580d7120cb760d199648046d6

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

 ​b5402d0 `fix typos in errors`

### comment:25 Changed 6 months ago by git

Commit: b5402d06f7a69f2580d7120cb760d199648046d6 → e092bef62df70a3dd3144318aa65e67db2da828a

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

 ​e092bef `Merge branch 'u/chapoton/17965' in 9.7.b1`

### comment:26 Changed 6 months ago by Samuel Lelièvre

Cc: Samuel Lelièvre added Uniformization of the API to compute the inverse of an element. → Uniformize the API to compute the inverse of an element

### comment:27 Changed 3 months ago by git

Commit: e092bef62df70a3dd3144318aa65e67db2da828a → de510a5732c108d8f916857d9e7af3f8b50754a5

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

 ​711913a `Merge branch 'u/chapoton/17965' in 9.7.rc0` ​de510a5 `trying to fix things in the categories`

### comment:28 Changed 3 months ago by git

Commit: de510a5732c108d8f916857d9e7af3f8b50754a5 → 0e19786c4715fa582ec87121592595626c4a56ec

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

 ​0e19786 `add doctest`

### comment:29 Changed 3 months ago by Frédéric Chapoton

almost ready to go. I hope that somebody will accept to review this long-awaited ticket.

### comment:30 Changed 3 months ago by git

Commit: 0e19786c4715fa582ec87121592595626c4a56ec → 24b88a5991a41d2bf9cf4fe9c2281b05f9fefcf6

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

 ​24b88a5 `fix doc`

### comment:31 Changed 3 months ago by Frédéric Chapoton

Cc: Travis Scrimshaw added needs_work → needs_review

and the patchbot is now green ! comments welcome

### comment:32 Changed 3 months ago by Matthias Köppe

```+        def inverse(self):
+            """
+            Return the inverse of ``self``.
+
+            This an alias for inversion, defined in ``__invert__``.
+
```

"is" is missing

### comment:33 Changed 3 months ago by Matthias Köppe

Do you want to address comment:4 and add some `automethod`?

### comment:34 Changed 3 months ago by git

Commit: 24b88a5991a41d2bf9cf4fe9c2281b05f9fefcf6 → b6a5773fc8c6b861150dc9e03d241ddf41741c24

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

 ​b6a5773 `fix typo`

### comment:35 Changed 3 months ago by Frédéric Chapoton

I am not so sure about this question about documentation. It is true that the doc inside `__invert__` will be hidden from view.

### comment:36 follow-up:  38 Changed 3 months ago by Travis Scrimshaw

I don't think too many people are going to be looking at the documentation of `__invert__` or `inverse()` as that is generally pretty clear.

That being said, I am not really a fan of putting technical implementation details in public documentation:

```-            This is an alias for inversion, defined in ``__invert__``.
+            This is an alias for inversion, which can be invoked by ``~x``
+            for an instance ``x``.
-
-            Element classes should implement ``__invert__`` only.
```

I would probably put the last part as a code comment. However, in this case, because it is specifications for implementors, it could be okay. The change in the first part is to indicate how a more casual user can use this.

I am not sure how I feel about removing the generic `1 / self` for inverse in `Element`. Is that implemented in one of the categories? Should we be worried about a slowdown with it no longer being Cython?

### comment:37 Changed 3 months ago by git

Commit: b6a5773fc8c6b861150dc9e03d241ddf41741c24 → e08cd7a4e9fb5d6492e8a611040dd562bdddf6cb

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

 ​9ec90c5 `Merge branch 'u/chapoton/17965' in 9.7.rc1` ​e08cd7a `tweak doc`

### comment:38 in reply to:  36 ; follow-up:  39 Changed 3 months ago by Frédéric Chapoton

I don't think too many people are going to be looking at the documentation of `__invert__` or `inverse()` as that is generally pretty clear.

I agree on that point.

That being said, I am not really a fan of putting technical implementation details in public documentation:

```-            This is an alias for inversion, defined in ``__invert__``.
+            This is an alias for inversion, which can be invoked by ``~x``
+            for an instance ``x``.
-
-            Element classes should implement ``__invert__`` only.
```

I would probably put the last part as a code comment. However, in this case, because it is specifications for implementors, it could be okay. The change in the first part is to indicate how a more casual user can use this.

I have changed that according to your suggestion. Implementation detail is now a comment in the code.

I have no idea. I thought that there was another category for additive monoids ?

I am not sure how I feel about removing the generic `1 / self` for inverse in `Element`. Is that implemented in one of the categories? Should we be worried about a slowdown with it no longer being Cython?

This is indeed a delicate point. Having both that and the division defined using product by the inverse easily leads to infinite loops. It seems safer to break the possibility of this kind of loop.

### comment:39 in reply to:  38 Changed 3 months ago by Travis Scrimshaw

That being said, I am not really a fan of putting technical implementation details in public documentation:

```-            This is an alias for inversion, defined in ``__invert__``.
+            This is an alias for inversion, which can be invoked by ``~x``
+            for an instance ``x``.
-
-            Element classes should implement ``__invert__`` only.
```

I would probably put the last part as a code comment. However, in this case, because it is specifications for implementors, it could be okay. The change in the first part is to indicate how a more casual user can use this.

I have changed that according to your suggestion. Implementation detail is now a comment in the code.

Thank you.

I have no idea. I thought that there was another category for additive monoids ?

There is, but we try to keep the two somewhat consistent. There is also the join category, where "inverse" becomes slightly vague.

I am not sure how I feel about removing the generic `1 / self` for inverse in `Element`. Is that implemented in one of the categories? Should we be worried about a slowdown with it no longer being Cython?

This is indeed a delicate point. Having both that and the division defined using product by the inverse easily leads to infinite loops. It seems safer to break the possibility of this kind of loop.

I would rather have the infinite loop (which there are protections against) and leave the choice of implementation to the developer. If it does go into an infinite loop, it is indicating that something needs to be implemented (unfortunately, I don't know a good mechanism for checking this). At the very least it is a backwards incompatible change.

Last edited 3 months ago by Travis Scrimshaw (previous) (diff)

### comment:40 Changed 3 months ago by git

Commit: e08cd7a4e9fb5d6492e8a611040dd562bdddf6cb → d0fbe93d4de3b38b40034b4c1743399f37393a59

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

 ​d0fbe93 `tweak doc again`

### comment:41 Changed 3 months ago by Frédéric Chapoton

I see no way out other than removing the invert in element.pyx. It is not a cdef method there, by the way. I agree that this is rather backward-incompatible..

### comment:42 Changed 3 months ago by Travis Scrimshaw

But basically you want to remove the `1 / self` default implementation to never have an infinite loop? In particular, if we had some sort of `@implement_this_or_that` type decorator, you would be fine with it? Or is there a technical issue with having it defined in the category?

I am particularly worried about someone could have implemented an algebraic structure just through `_div_`, and there are things in Sage that use `~x` that are subsequently being called with this algebraic structure. I could imagine something like this for polynomials (without going to the fraction field).

### comment:43 Changed 3 months ago by Frédéric Chapoton

Branch: u/chapoton/17965 → public/ticket-17965-experiment d0fbe93d4de3b38b40034b4c1743399f37393a59 → 312a91d4f327802ca1e6d48975cd1d221128833e

here is an experimental branch with the default inverse re-activated, let us see what happens.

New commits:

 ​312a91d `re-introduce default inversion`

### comment:44 Changed 3 months ago by Frédéric Chapoton

well, this seems to be almost green..

### comment:45 Changed 3 months ago by Travis Scrimshaw

It seems like that is unrelated. Have you tested locally?

### comment:46 Changed 3 months ago by Frédéric Chapoton

the failure is #33161 ; the tests in this file pass with other random seeds

### comment:47 Changed 3 months ago by Travis Scrimshaw

I am basically ready to flip the switch. The last thing I probably would like (although not fully convinced) is to have an alias `inverse = __invert__` in the classes that implemented an `inverse` in order to keep the documentation there visible.

### comment:48 Changed 3 months ago by Frédéric Chapoton

But this would basically contradict the fact that there is a unique global alias that maps `inverse` to `__invert__` ?

### comment:49 Changed 3 months ago by Travis Scrimshaw

It isn't an alias in the Python sense. However, I didn't think your proposal said there should be a unique such redirect.

I don't see any advantages of trying to impose that (it isn't really enforceable either). I think if we are consistent about using `__invert__`, then we won't get a user saying "I get to chose which one I want to do" (not to mention generic division would not work). On the other hand, I don't think this documentation is generally useful though, and not having it would mean that there is a near 0% chance of confusion.

### comment:50 Changed 3 months ago by Frédéric Chapoton

Sorry, I am now confused and not sure what you would like me to change.

### comment:51 Changed 3 months ago by Travis Scrimshaw

For example, in `algebras/hecke_algebras/ariki_koike_algebra.py`, you are removing the `inverse` function. So it will no longer appear in the documentation and `x.inverse?` will be the generic documentation. I am think is adding a

```inverse = __invert__
```

alias there so the documentation won't change.

Anyways, it sounds like you don't really like it and I wasn't convinced of how useful it would be, so we can move on.

### comment:52 Changed 3 months ago by Frédéric Chapoton

So, is this a positive review ?

### comment:53 Changed 3 months ago by Travis Scrimshaw

Reviewers: → Travis Scrimshaw needs_review → positive_review

Yes.

### comment:54 Changed 3 months ago by Matthias Köppe

After these changes, is ticket #17692 still relevant?

### comment:55 follow-up:  56 Changed 3 months ago by Travis Scrimshaw

#17692 is independent of these changes (and the main proposal has already been done somewhere else).

The issue of whether `__invert__` and the (very embedded) `~x` should not be bitwise inverse (compare `~int(5)` to `~Integer(5)`) is not impacted by this change (other than it might be slightly more work to make such a change, but it is now at least applied uniformly, so it is less likely we miss something IMO).

### comment:56 in reply to:  55 ; follow-up:  57 Changed 3 months ago by Matthias Köppe

#17692 is independent of these changes (and the main proposal has already been done somewhere else).

The issue of whether `__invert__` and the (very embedded) `~x` should not be bitwise inverse (compare `~int(5)` to `~Integer(5)`) is not impacted by this change

No, the bitwise complement question is not the topic of #17692 (it is only mentioned in the very last comment)

### comment:57 in reply to:  56 Changed 3 months ago by Travis Scrimshaw

#17692 is independent of these changes (and the main proposal has already been done somewhere else).

The issue of whether `__invert__` and the (very embedded) `~x` should not be bitwise inverse (compare `~int(5)` to `~Integer(5)`) is not impacted by this change

No, the bitwise complement question is not the topic of #17692 (it is only mentioned in the very last comment)

Either way, #17692 is independent of this ticket. (It probably should be closed (again, the main change has been implemented elsewhere) or converted into a bitwise issue ticket.)

### comment:58 Changed 3 months ago by Matthias Köppe

Milestone: sage-9.7 → sage-9.8

### comment:59 Changed 3 months ago by Volker Braun

Branch: public/ticket-17965-experiment → 312a91d4f327802ca1e6d48975cd1d221128833e → fixed positive_review → closed
Note: See TracTickets for help on using tickets.