Opened 10 years ago

# Family over enumerated set has wrong category

Reported by: Owned by: Christian Nassau Nicolas M. Thiéry minor sage-duplicate/invalid/wontfix categories Family, Category of finite enumerated sets, CartesianProduct N/A u/ncohen/14541 fd3d6d51a3251999e327cf18c38f3389b2ee2a1b

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,x-y)).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
```

### comment:1 follow-up:  3 Changed 10 years ago by Nicolas M. Thiéry

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?

### comment:2 Changed 10 years ago by Christian Nassau

I actually don't care about `Permutations()` a lot - I just picked those to come up with an easily reproducable 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).

Version 0, edited 10 years ago by Christian Nassau (next)

### comment:3 in reply to:  1 Changed 10 years ago by Christian Nassau

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.

### comment:4 Changed 10 years ago by Christian Nassau

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 Christian Nassau

Authors: → Christian Nassau CartesianProduct added new → needs_review

### comment:6 Changed 10 years ago by Christian Nassau

Description: modified (diff)

### comment:7 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11 → sage-5.12

### comment:8 Changed 9 years ago by Nathann Cohen

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 Nathann Cohen

Branch: → u/ncohen/14541

### comment:10 Changed 9 years ago by Nathann Cohen

Authors: Christian Nassau → Christian Nassau, Nathann Cohen

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

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 For batch modifications

Milestone: sage-6.1 → sage-6.2

### comment:13 Changed 9 years ago by For batch modifications

Milestone: sage-6.2 → sage-6.3

### comment:14 Changed 9 years ago by Ralf Stephan

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 Nathann Cohen

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 For batch modifications

Milestone: sage-6.3 → sage-6.4

### comment:18 Changed 6 years ago by Travis Scrimshaw

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,x-y)).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:19 Changed 4 months ago by Matthias Köppe

The remaining issue is a dup of #18849

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

Milestone: sage-7.3 → sage-duplicate/invalid/wontfix needs_work → needs_review

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

Authors: Christian Nassau, Nathann Cohen
Note: See TracTickets for help on using tickets.