Cartesian Products of additive groups

[ncohen]

With this branch, one can see the product of two fields (or the product of one field and an additive group) as an additive group.

sage: F8=GF(8,'x') 
sage: x = F8.primitive_element()
sage: F5=GF(5)
sage: F8xF5 = F8.cartesian_product(F5)
sage: F8xF5.an_element()
(0, 0)
sage: e=F8xF5((x,4))    
sage: e
(x, 4)
sage: e+e
(0, 3)
sage: 3*e
(x, 2)
sage: -e
(x, 1)

[git]

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

​3702315	trac #16269: _element_constructor_ in CartesianProduct
​220ce27	trac #16269: Finish the previous commits
​370abb8	trac #16269: Fixing doctests and implementing additional functions

[dimpase]

Hmm, do you mean to construct the Cartesian product of fields? Then it will be a ring, with two operations, addition and multiplication...

---

New commits:

​3702315	trac #16269: _element_constructor_ in CartesianProduct
​220ce27	trac #16269: Finish the previous commits
​370abb8	trac #16269: Fixing doctests and implementing additional functions

[ncohen]

Passes all tests ! The try/except in _element_constructor_ is because of this discussion ​https://groups.google.com/d/topic/sage-devel/tHallML3OYI/discussion

In the meantime, as it seems you cannot call FiniteEnumeratedSet(a_list)(something) then it is unavoidable

Nathann

[ncohen]

Yo !

Hmm, do you mean to construct the Cartesian product of fields? Then it will be a ring, with two operations, addition and multiplication...

Hmmmm.. Well, I guess it may not be very hard to do.

1) A ring is a additive group (so the + is already implemented) for the product of rings

2) It has a multiplicative operation, but perhaps the product of multiplicative associative magma is not detected as such. If you can just give Sage the right inheritances, perhaps you have no real code to implement.

Good luck,

Nathann

[ncohen]

Funny, there is no rings.<tab> thing...

Nathann

[vdelecroix]

Replying to ncohen:

Passes all tests ! The try/except in _element_constructor_ is because of this discussion ​https://groups.google.com/d/topic/sage-devel/tHallML3OYI/discussion

In the meantime, as it seems you cannot call FiniteEnumeratedSet(a_list)(something) then it is unavoidable

Nathann

Your _element_constructor_ is buggy

sage: S1 = FiniteEnumeratedSet(['a','b','c'])
sage: S2 = GF(5)
sage: C=cartesian_product([S1,S2])
sage: C(('a',1))
('a', 1)
sage: c = C(('a',1))
sage: c[1].parent()
Integer Ring

It would be better to clean the input of the cartesian product set by set.

[nthiery]

I'd say: don't worry about the Rings thing for now unless you critically need it. It will be a one line to add once #10963 is in. Just handle the additive and multiplicative side separately.

I'll have a look at this later today.

[ncohen]

Your _element_constructor_ is buggy

Hey man, if it comes to that I think that the design in which the elements of a Parent are not Element is the buggy thing.

Nathann

[git]

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

​aa07ba1

trac #16269: Working around "officially not a bug"

[dimpase]

Replying to ncohen:

Yo !

Hmm, do you mean to construct the Cartesian product of fields? Then it will be a ring, with two operations, addition and multiplication...

Hmmmm.. Well, I guess it may not be very hard to do.

1) A ring is a additive group (so the + is already implemented) for the product of rings

You can make any abelian group into a ring by defining multiplication by a non-zero element a to be identity operation, i.e. ax=x for all x in the group, and by 0 to be zero, i.e. 0x=0 for all x in the group. This should be easy to implement - no real code, just some abstract nonsense :-)

That is, as soon as you have cartesian product of rings, you have what you need in general...

2) It has a multiplicative operation, but perhaps the product of multiplicative associative magma is not detected as such.

but why? Is it because #10963 will take forever to merge, as it has apparently hit some kind of OSS unsolvability barrier? :)

If you can just give Sage the right inheritances, perhaps you have no real code to implement.

If I were a category theorist and a (C)Python guru by training, perhaps it will only take me 5 minutes ;-)

[ncohen]

Yo !

Is it because #10963 will take forever to merge, as it has apparently hit some kind of OSS unsolvability barrier? :)

I have no idea what #10963 contains, nor do I care to be honest. And about implementing rings, I would personally chose to behave as if #10963 were to never be merged, because you just can't count on stuff like this to happen :-P

If I were a category theorist and a (C)Python guru by training, perhaps it will only take me 5 minutes ;-)

Which is why I lived very hard the last 2 days, during which I tried to implement a ten-lines patch that would have taken any of the so-called "category theorist and a (C)Python guru by training" those 5 minutes. Besides, I don't consider the product of additive group to be such a weird notion that it could be left unimplemented for years :-P

But well. Now it is done in this patch. Stuff happens.

Nathann

[nthiery]

Replying to dimpase:

Is it because #10963 will take forever to merge, as it has apparently hit some kind of OSS unsolvability barrier? :)

The review process has restarted :-)

[git]

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

​d22e245

trac #16269: missing __iter__

[nthiery]

Hi!

I have just been through the changes. Overall, it looks good, thanks!

Remaining points:

• CartesianProduct?.iter should be in EnumeratedSets?.CartesianProducts?.ParentMethods?
• In _add_, self.parent(right) looks suspicious. Does it even work? If the purpose is to convert right into the same parent as self, then no need to worry about this: _add_ may assume that its two arguments belong to the same parent.
• I am uncomfortable with using iter and getitem for accessing the components of an element. For certain cartesian products (e.g. cartesian products of modules), iter may have a different meaning. Please use summand_split and summand_projection instead.
• In _element_constructor_: given the catch, if we feed completely unrelated crap to the constructor, is there an exception raised as one could desire?

      sage: GF(3)("a")
      Traceback (most recent call last)
      ...
      TypeError: unable to convert x (=a) to an integer
  
      sage: C = cartesian_product([GF(3), GF(3)])
      sage: C(["a","b"])
      ???
  

Please add this doctest. Btw, one might also want to raise a meaningful error if the length of x is incorrect.

Cheers,

Nicolas

[ncohen]

Yo !

• CartesianProduct?.iter should be in EnumeratedSets?.CartesianProducts?.ParentMethods?

Done

• In _add_, self.parent(right) looks suspicious. Does it even work? If the purpose is to convert right into the same parent as self, then no need to worry about this: _add_ may assume that its two arguments belong to the same parent.

That was the reason. Done.

• I am uncomfortable with using iter and getitem for accessing the components of an element. For certain cartesian products (e.g. cartesian products of modules), iter may have a different meaning. Please use summand_split and summand_projection instead.

Here I do not agree. This is the most natural definition of an "iter" for a cartesian product. Your application will overrule this anyway, so how can that be a problem ?

• In _element_constructor_: given the catch, if we feed completely unrelated crap to the constructor, is there an exception raised as one could desire?

      sage: GF(3)("a")
      Traceback (most recent call last)
      ...
      TypeError: unable to convert x (=a) to an integer
  
      sage: C = cartesian_product([GF(3), GF(3)])
      sage: C(["a","b"])
      ???
  

Okay, so here I am stuck and I can't sort this out. Here is the problem :

sage: FiniteEnumeratedSet(["a","b","c"])("a")
TypeError: Cannot convert str to sage.structure.element.Element
sage: FiniteEnumeratedSet(["a","b","c"])("d")
ValueError: d not in {'a', 'b', 'c'}

Because you cannot trust FiniteEnumeratedSet to have a sound __call__ method, I need this try/catch.

On the other hand, if I have this try/catch, then I cannot detect GF(3)("e") anymore. So what do we do ?

I personally see no problem in removing this catch, knowing that cartesian products of FiniteEnumeratedSet will fail. For me it is because of a bug in FiniteEnumeratedSet, not of what I implement.

Nathann

[nthiery]

Replying to ncohen:

Here I do not agree. This is the most natural definition of an "iter" for a cartesian product. Your application will overrule this anyway, so how can that be a problem ?

Ah shoot, in the mean time I answered your private e-mail about this :-) Shall I copy paste my answer here?

I personally see no problem in removing this catch, knowing that cartesian products of FiniteEnumeratedSet will fail. For me it is because of a bug in FiniteEnumeratedSet, not of what I implement.

I agree.

If this special situation is not used too much elsewhere (i.e. if all test pass), then I'd say let's go. And if not, I guess we will need to fix/workaround the problem in FiniteEnumeratedSet?.

Cheers,

Nicolas

[ncohen]

Yo !

Ah shoot, in the mean time I answered your private e-mail about this :-) Shall I copy paste my answer here?

For others: the answer was that I should just use the .summand_projection commands in the code and not iter on the elements for it could have a different meaning elsewhere.

I asked you how to guess the length of the vector though... Which I will need to call the projection commands.

I agree.

If this special situation is not used too much elsewhere (i.e. if all test pass), then I'd say let's go. And if not, I guess we will need to fix/workaround the problem in FiniteEnumeratedSet?.

Well, not all tests pass actually, I just noticed. The first examples in the doc of categories/cartesian_product use enumerated sets >_<

Nathann

[nthiery]

Replying to ncohen:

Well, not all tests pass actually, I just noticed. The first examples in the doc of categories/cartesian_product use enumerated sets >_<

No luck. I can have a shot at fixing/working around the problem in FiniteEnumeratedSets? later tonight if you want.

[ncohen]

Yo !

No luck. I can have a shot at fixing/working around the problem in FiniteEnumeratedSets? later tonight if you want.

Wow. Thanks.

Ahem. I don't know what happened to the old Nicolas, but I like this version of yourself :-P

Thanks for your help. I am testing that only the bug produced by the FiniteEnumeratedSet remains in my branch, and all your other remarks should be implemented. I also added an exception (and a test) for the case where the element given to _element_constructor_ has the wrong length.

Nathann

P.S. : Okay, the tests are done. It passes all tests in category/ and sets/ except for the category/cartesian_product.py file. The problem is the .an_element() call at the top of the file.

If it comes to that, we could even overwrite FiniteEnumeratedSet.CartesianProduct.ParentMethod._element_constructor_. Gosh. I almost speak the category slang, now. I am scared.

[git]

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

​f262faa	trac #16269: Merged with 6.2.rc1
​338cc5b	trac #16269: Reviewer's remarks

[nthiery]

I uploaded a potential fix to the FiniteEnumeratedSet problem on #16280, which I added here as light dependency.

[nthiery]

Replying to ncohen:

Ahem. I don't know what happened to the old Nicolas, but I like this version of yourself :-P

:-)

Well, currently no teaching, no big ongoing administrative task, and before #10963 is in, I am stuck for long term dev. But don't worry, it's the same me: in the mean time others are cursing me (loud or quietly) for not working on other stuff ... Sight, that's never ending ...

Thanks for your help. I am testing that only the bug produced by the FiniteEnumeratedSet remains in my branch, and all your other remarks should be implemented. I also added an exception (and a test) for the case where the element given to _element_constructor_ has the wrong length.

Sounds good. I'll check that tomorrow.

Gosh. I almost speak the category slang, now. I am scared.

:-)

Good night!

Nicolas

[git]

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

​8ac32c2	#16280: Fix call for FiniteEnumeratedSet's of plain Python objects
​4e27454	#16280: Trivial doctest fixes
​f67d82e	trac #16269: Merged with #16280

[ncohen]

Here it is ! ;-)

Nathann

[ncohen]

Okay, the problem being solved can I set this to positive_review ? It is the last unreviewed dependency of #16277.

Nathann

[git]

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

​0a54b68

Trac 16269: little improvements + line folding in the doctest output

[nthiery]

If my latest changes are fine with you, this is definitely a positive review on my side.

Running all long doctests now just to make sure.

---

New commits:

​0a54b68

Trac 16269: little improvements + line folding in the doctest output

[ncohen]

Well, the exception is nicer and I think you told me that iter belonged to this class (sorry I moved a lot of stuff around, I probably lost track) but I would like to know why you replaced this self() with _cartesian_product_of_elements.

Nathann

[nthiery]

This bypasses the constructor checks while being independent of the internal representation.

Oh, no, it does not bypass the constructor in the basic implementation! _cartesian_product_of_element should definitely call element_class directly.

Ok, I can't do it right now. But this can wait for a later ticket too.

[nthiery]

All long tests pass btw

[ncohen]

Okayokayokay, thennnnnnnnn ... :-)

Nathann

[nthiery]

New commits:

​b5ad803

Trac 16269 (or follow up): optimize CartesianProduct._cartesian_product_of_elements

[nthiery]

Hi,

I fixed _cartesian_product_of_elements to bypass _element_constructor and other checks, and documented it. Here is the timing difference:

sage: S1 = Sets().example()
sage: S2 = InfiniteEnumeratedSets().example()
sage: C = cartesian_product([S2, S1, S2])
sage: l = tuple([S2.an_element(), S1.an_element(), S2.an_element()])

Without the optimization:

sage: %timeit C._cartesian_product_of_elements(l)
10000 loops, best of 3: 22 µs per loop

With the optimization:

sage: %timeit C._cartesian_product_of_elements(lt)
1000000 loops, best of 3: 922 ns per loop

If you are fine including this in this ticket, please change the branch to u/nthiery/16269-optimized. Otherwise, I'll move this commit to a follow up ticket.

For the record: the tests pass on the cartesian_product.py file. Running all long tests now to be sure.

Cheers,

Nicolas

[nthiery]

The optimization is now #16288, as this was more practical for Nathann. Hence this ticket is ready to be merged as is.