Opened 10 years ago
Last modified 6 months ago
#14541 needs_review defect
Family over enumerated set has wrong category
Reported by:  cnassau  Owned by:  nthiery 

Priority:  minor  Milestone:  sageduplicate/invalid/wontfix 
Component:  categories  Keywords:  Family, Category of finite enumerated sets, CartesianProduct 
Cc:  Merged in:  
Authors:  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/ncohen/14541 (Commits, GitHub, GitLab)  Commit:  fd3d6d51a3251999e327cf18c38f3389b2ee2a1b 
Dependencies:  Stopgaps: 
Description (last modified by )
This happens with Sage 5.10beta3:
sage: P=Permutations() sage: print P.category() Category of sets sage: print P.cardinality() +Infinity sage: F=Family(Permutations(), lambda i:i) sage: print F.category() Category of finite enumerated sets
But clearly F
is not finite...
Another bug, (also fixed in the attached patch):
sage: Family(CartesianProduct(ZZ,ZZ),lambda (x,y) : (x+y,xy)).cardinality() ... TypeError: cardinality does not fit into a Python int.
update: following example is still wrong (see second comment)
sage: X=CombinatorialFreeModule(ZZ,ZZ) sage: print X Free module generated by Integer Ring over Integer Ring sage: print X.basis().category() Category of enumerated sets sage: TX = tensor((X,)) sage: print TX.basis().cardinality() +Infinity sage: print TX.basis().category() Category of finite enumerated sets
Attachments (1)
Change History (22)
comment:1 followup: 3 Changed 10 years ago by
comment:2 Changed 10 years ago by
I actually don't care about Permutations()
a lot  I just picked those to come up with an easily reproducible problem. I should have given this example:
sage: X=CombinatorialFreeModule(ZZ,ZZ) sage: print X Free module generated by Integer Ring over Integer Ring sage: print X.basis().category() Category of enumerated sets sage: TX = tensor((X,)) sage: print TX.basis().category() Category of finite enumerated sets
I believe I fixed this in #13979 for Sage 5.7.b4 (which was neither merged nor even considered).
comment:3 Changed 10 years ago by
Replying to nthiery:
As a workaround, line 832 of Family, when the input is a CombinatorialClass?, we could ask whether x.cardinality() != infinity. The risk is to trigger the enumeration of the elements of the combinatorial class which might take a while ... Or check if cardinality actually is implemented (i.e. is not the default _cardinality_from_iterator), and if yes call it.
This sounds like a solution that might fix the issue that I'm seeing with my (still nascent) Steenrod algebra module package. I'll try to prepare a patch along these lines.
Changed 10 years ago by
Attachment:  14541.patch added 

comment:4 Changed 10 years ago by
The attached patch changes the category initialization of LazyFamily
objects: if the keys K
are an instance of CombinatorialClass
the category choice now depends on "K.cardinality() < Infinity
" in the obvious way.
(I have not tried to inspect the keys K
further, because I could not find a CombinatorialClass
without custom cardinality
method.)
I have also added another exception to LazyFamily.cardinality()
: the code used to check for AttributeError
and NotImplementedError
, but CartesianProduct(...).__len__
raises a TypeError
instead. I've added a doctest that fails otherwise.
comment:5 Changed 10 years ago by
Authors:  → Christian Nassau 

Keywords:  CartesianProduct added 
Status:  new → needs_review 
comment:6 Changed 10 years ago by
Description:  modified (diff) 

comment:7 Changed 9 years ago by
Milestone:  sage5.11 → sage5.12 

comment:8 Changed 9 years ago by
The bug reported has been fixed in the meantime by #14772 : permutations do not use CombinatorialClass
anymore.
This does not fix the general problem however, and indeed one should not force the computation of the cardinality of this set unless this operations has been explicitly requested.
Thus, I upload a git branch which just removes CombinatorialClass
from the list of exceptions. There is apparently no reason why all instances of CombinatorialClass
should represent finite sets.
(and I personally don't even see why an uncountable set should be said to be "enumerable", but that's another problem)
Nathann
comment:9 Changed 9 years ago by
Branch:  → u/ncohen/14541 

comment:10 Changed 9 years ago by
Authors:  Christian Nassau → Christian Nassau, Nathann Cohen 

comment:11 Changed 9 years ago by
Commit:  → fd3d6d51a3251999e327cf18c38f3389b2ee2a1b 

Branch pushed to git repo; I updated commit sha1. New commits:
fd3d6d5  trac #14541: Family over enumerated set has wrong category

comment:12 Changed 9 years ago by
Milestone:  sage6.1 → sage6.2 

comment:13 Changed 9 years ago by
Milestone:  sage6.2 → sage6.3 

comment:14 Changed 9 years ago by
Status:  needs_review → needs_work 

patchbot:
sage t long src/sage/combinat/free_module.py # 1 doctest failed
comment:15 Changed 9 years ago by
Okay Ralf, I don't know how to fix that. I give up. If you understand category code please give it a try, I don't.
Nathann
comment:16 Changed 8 years ago by
Milestone:  sage6.3 → sage6.4 

comment:17 Changed 7 years ago by
Description:  modified (diff) 

Stopgaps:  → wrongAnswerMarker 
comment:18 Changed 7 years ago by
Milestone:  sage6.4 → sage7.3 

Stopgaps:  wrongAnswerMarker 
The first and second issues are fixed
sage: F = Family(Permutations(), lambda i: i) sage: F.category() Category of infinite enumerated sets sage: Family(cartesian_product([ZZ,ZZ]),lambda (x,y) : (x+y,xy)).cardinality() +Infinity
However, the last issue is still outstanding:
sage: X=CombinatorialFreeModule(ZZ,ZZ) sage: X.basis().category() Category of infinite enumerated sets sage: TX = tensor((X,)) sage: TX.basis().cardinality() +Infinity sage: TX.basis().category() Category of finite enumerated sets
This seems to be due to falling into a default of finite (enumerated) sets instead of just pulling the information from the category of the keys:
sage: TX.basis().keys() Image of Cartesian product of Integer Ring by <type 'tuple'> sage: TX.basis().keys().category() Category of sets
Also, the stopgap field is to be used for ticket(s) for the stopgaps.
comment:20 Changed 6 months ago by
Milestone:  sage7.3 → sageduplicate/invalid/wontfix 

Status:  needs_work → needs_review 
comment:21 Changed 6 months ago by
Authors:  Christian Nassau, Nathann Cohen 

Thanks for the report!
Hmm, that's annoying indeed. This stems from the fact that
Permutations
still uses the old CombinatorialClass?, and for those it's not so easy to detect easily whether they are known to be finite.As a workaround, line 832 of Family, when the input is a CombinatorialClass?, we could ask whether x.cardinality() != infinity. The risk is to trigger the enumeration of the elements of the combinatorial class which might take a while ... Or check if cardinality actually is implemented (i.e. is not the default _cardinality_from_iterator), and if yes call it.
Of course, the proper fix would be to revamp permutations to be an enumerated set like has been done recently for tableaux.
Would you be willing to handle any of the above?