Bug in category_singleton.__contains__ or in CombinatorialFreeModule

[Reimundo Heluani]

I am having trouble that my parents are being assigned in a category of finite
dimensional modules and the culprit seems to be this:

sage: M = CombinatorialFreeModule(QQ, DisjointUnionEnumeratedSets([Integers(), Family([])]))
sage: M.category()
Category of finite dimensional vector spaces with basis over Rational Field
sage: M.dimension()
+Infinity

And this is the bug that is biting me.

CombinatorialFreeModule.__init__ is setting the extra dressing to
FiniteDimensional() because of this

sage: NonNegativeIntegers() in Sets().Finite()
False
sage: E = DisjointUnionEnumeratedSets([NonNegativeIntegers(), Family(['x'])]); E
Disjoint union of Family (Non negative integers, Family ('x',))
sage: E in Sets().Finite()
True
sage: E.cardinality()
+Infinity

I suppose this is coming from sage.categories.category_singleton that has the
__contain__ method for Sets().Finite() but the problem is that I am not sure
what is the bug, as a set this is the disjoint union of two sets. So perhaps
the idea behind the above was that this is a finite set with two elements,
one of them being an infinite set. I can live with E in Sets().Finite() being
True (although I don't like it if that was intended)

But I certainly do not like M.category() being finite dimensional.

Since basis_keys in CombinatorialFreeModule is Enumerated, I have been using
this simple patch to get the right behaviour on the modules and it doesn't
seem to break anything.


$ git diff src/sage/combinat/free_module.py
diff --git a/src/sage/combinat/free_module.py b/src/sage/combinat/free_module.py
index 2fbe8b225e..a2bf2a53d6 100644
--- a/src/sage/combinat/free_module.py
+++ b/src/sage/combinat/free_module.py
@@ -449,7 +449,8 @@ class CombinatorialFreeModule(UniqueRepresentation, Module, IndexedGenerators):
category = ModulesWithBasis(R)
elif isinstance(category, tuple):
category = Category.join(category)
- if basis_keys in Sets().Finite():
+ from sage.rings.infinity import Infinity
+ if basis_keys.cardinality() != Infinity:
category = category.FiniteDimensional()

Parent.__init__(self, base=R, category=category, names=names)


Either way one of the two issues should be corrected I think.

Best,

R.

[Markus Wageringel]

I think the problem here is that enumerating over a disjoint union of an infinite set and a finite set will never reach the elements in the finite set. There is this comment in the documentation of DisjointUnionEnumeratedSets

   Possible extensions: the current enumeration order is not suitable
   for unions of infinite enumerated sets (except possibly for the
   last one). One could add options to specify alternative enumeration
   orders (anti-diagonal, round robin, ...) to handle this case.

so the workaround is to first enumerate over the finite set and then the infinite set, as the last enumerated set in the union will determine whether the disjoint union is finite or not:

sage: DisjointUnionEnumeratedSets([NonNegativeIntegers(), Family('x')]) in FiniteSets()
True
sage: DisjointUnionEnumeratedSets([Family('x'), NonNegativeIntegers()]) in FiniteSets()
False

[Reimundo Heluani]

Nice! I hadn't seen that. I do think however that the check in CombinatorialFreeModule should be changed or at least that taking the disjoint union should print a warning that that this set is considered to be finite.

Best,

R.

>--
>You received this message because you are subscribed to the Google Groups
>"sage-devel" group.
>To unsubscribe from this group and stop receiving emails from it, send an email
>to [1]sage-devel+...@googlegroups.com.
>To view this discussion on the web visit [2]https://groups.google.com/d/msgid/
>sage-devel/aeb3c3ba-c804-428d-9119-2629950be6cbo%40googlegroups.com.
>
>References:
>
>[1] mailto:sage-devel+...@googlegroups.com
>[2] https://groups.google.com/d/msgid/sage-devel/aeb3c3ba-c804-428d-9119-2629950be6cbo%40googlegroups.com?utm_medium=email&utm_source=footer

[Travis Scrimshaw]

That definitely is not a bug in CombinatorialFreeModule, so there shouldn't be anything changed there. It is doing what it is told: that its indexing set is in finite sets. I would say the bug is purely in the DisjointUnionEnumeratedSets not doing a full check of its member sets.

Best,

Travis

[Reimundo Heluani]

On Jun 20, 'Travis Scrimshaw' via sage-devel wrote:
>That definitely is not a bug in CombinatorialFreeModule, so there shouldn't be
>anything changed there. It is doing what it is told: that its indexing set is
>in finite sets. I would say the bug is purely in the
>DisjointUnionEnumeratedSets not doing a full check of its member sets.

I think so too, but I thought that the behaviour for the disjoint union was
intended as this.

Now looking at the code it seems that it wasn't. The checks are for a couple
of reasonable cases, but some corner cases make them fail on both ways.

An infinite union of empty sets is infinite:

sage: F = Family(ZZ, lambda i: Set())
sage: C = DisjointUnionEnumeratedSets(F)
sage: C.category()
Category of facade infinite enumerated sets

In the case of finite families the following simple change seems to check
correctly. But I suppose this can break something, there must've been a reason
to check only the last set.

sage: C = DisjointUnionEnumeratedSets([NonNegativeIntegers(), Family([1,2,3])])
sage: C.category()
Category of facade infinite enumerated sets

$ git diff src/sage/sets/disjoint_union_enumerated_sets.py
diff --git a/src/sage/sets/disjoint_union_enumerated_sets.py b/src/sage/sets/disjoint_union_enumerated_sets.py
index c6d35ea8bd..f5fdba7119 100644
--- a/src/sage/sets/disjoint_union_enumerated_sets.py
+++ b/src/sage/sets/disjoint_union_enumerated_sets.py
@@ -302,7 +302,7 @@ class DisjointUnionEnumeratedSets(UniqueRepresentation, Parent):
# try to guess if the result is infinite or not.
if self._family in InfiniteEnumeratedSets():
category = InfiniteEnumeratedSets()
- elif self._family.last().cardinality() == Infinity:
+ elif any(x.cardinality() == Infinity for x in self._family):
category = InfiniteEnumeratedSets()
else:
category = FiniteEnumeratedSets()

I can't think of a reasonable way of checking against the infinite union of
empty sets.

Best,

R.

> >To view this discussion on the web visit [2][1]https://groups.google.com/d
> /msgid/
> >sage-devel/aeb3c3ba-c804-428d-9119-2629950be6cbo%[2]40googlegroups.com.
> >
> >References:
> >
> >[1] mailto:sage-devel+...@googlegroups.com
> >[2] [3]https://groups.google.com/d/msgid/sage-devel/
> aeb3c3ba-c804-428d-9119-2629950be6cbo%40googlegroups.com?utm_medium=email&
> utm_source=footer

>
>
>--
>You received this message because you are subscribed to the Google Groups
>"sage-devel" group.
>To unsubscribe from this group and stop receiving emails from it, send an email

>to [4]sage-devel+...@googlegroups.com.
>To view this discussion on the web visit [5]https://groups.google.com/d/msgid/
>sage-devel/9460d061-39db-44b9-90e7-5d348e706bben%40googlegroups.com.
>
>References:
>
>[1] https://groups.google.com/d/msgid/
>[2] http://40googlegroups.com/
>[3] https://groups.google.com/d/msgid/sage-devel/aeb3c3ba-c804-428d-9119-2629950be6cbo%40googlegroups.com?utm_medium=email&utm_source=footer
>[4] mailto:sage-devel+...@googlegroups.com
>[5] https://groups.google.com/d/msgid/sage-devel/9460d061-39db-44b9-90e7-5d348e706bben%40googlegroups.com?utm_medium=email&utm_source=footer

[Travis Scrimshaw]

$ git diff src/sage/sets/disjoint_union_enumerated_sets.py
diff --git a/src/sage/sets/disjoint_union_enumerated_sets.py b/src/sage/sets/disjoint_union_enumerated_sets.py
index c6d35ea8bd..f5fdba7119 100644
--- a/src/sage/sets/disjoint_union_enumerated_sets.py
+++ b/src/sage/sets/disjoint_union_enumerated_sets.py
@@ -302,7 +302,7 @@ class DisjointUnionEnumeratedSets(UniqueRepresentation, Parent):
              # try to guess if the result is infinite or not.
              if self._family in InfiniteEnumeratedSets():
                  category = InfiniteEnumeratedSets()
-            elif self._family.last().cardinality() == Infinity:
+            elif any(x.cardinality() == Infinity for x in self._family):
                  category = InfiniteEnumeratedSets()
              else:
                  category = FiniteEnumeratedSets()

I can't think of a reasonable way of checking against the infinite union of
empty sets.

That is because it is an undecidable problem. I think it is a safe bet that if someone was passing an infinite union, then assume that an infinite number of sets have an element. This can be explicitly stated as a .. WARNING:: or .. NOTE:: in the documentation. However, you should be careful about iterating over anything you do not explicitly know is finite as it could run into an infinite loop, and we generally want to avoid that.

Best,

Travis