Opened 8 years ago

Last modified 7 days ago

#18849 needs_work defect

category of lazy family wrong if infinite combinatorial class used as index

Reported by: cnassau Owned by:
Priority: major Milestone: sage-9.9
Component: categories Keywords:
Cc: tscrim Merged in:
Authors: Christian Nassau Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: u/cnassau/18849 (Commits, GitHub, GitLab) Commit: 09f97fa45de98e4ede496f7f5401cdd84bdda05f
Dependencies: #19195 Stopgaps:

Status badges

Description

sage: from sage.sets.set_from_iterator import EnumeratedSetFromIterator
sage: C=CombinatorialFreeModule(ZZ,EnumeratedSetFromIterator(Integers)) ; C
Free module generated by {0, 1, -1, 2, -2, ...} over Integer Ring
sage: U = tensor((C,)) ; U
Free module generated by {0, 1, -1, 2, -2, ...} over Integer Ring
sage: C.basis().category()
Category of enumerated sets
sage: U.basis().category()
Category of finite enumerated sets

But clearly the basis of U is not finite.

Change History (15)

comment:1 Changed 8 years ago by cnassau

Authors: Christian Nassau
Branch: u/cnassau/18849
Commit: b5538846c0bf80c7ef462818afec1019216cab86
Status: newneeds_review

Source of this problem is that the tensor product uses a sage.combinat.combinat.MapCombinatorialClass for the cartesian product, and the LazyFamily constructor assumed all CombinatorialClass objects to be finite. An extra check for is_finite has been added in this case. The check is caught since is_finite might not be implemented.

Note that it's important not to treat the negative answer of is_finite as affirmation that the class is actually infinite; whether the set is finite or not might just not be known, or to expansive to check.


New commits:

b553884fix category detection for LazyFamily objects

comment:2 Changed 8 years ago by git

Commit: b5538846c0bf80c7ef462818afec1019216cab8682849a079752d3a392b2cbe959c3df8943bc06ac

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

82849a0fix category detection for LazyFamily objects

comment:3 Changed 8 years ago by git

Commit: 82849a079752d3a392b2cbe959c3df8943bc06ac09f97fa45de98e4ede496f7f5401cdd84bdda05f

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

09f97fafix category detection for LazyFamily objects

comment:4 Changed 8 years ago by cnassau

A first patchbot run gave this error:

**********************************************************************
File "src/sage/interfaces/expect.py", line 825, in sage.interfaces.expect.Expect._eval_line
Failed example:
    singular.interrupt(timeout=3)  # sometimes very slow (up to 60s on sage.math, 2012)
Expected:
    False
Got:
    True
**********************************************************************
1 item had failures:
   1 of  15 in sage.interfaces.expect.Expect._eval_line
    [89 tests, 1 failure, 9.38 s]
----------------------------------------------------------------------
sage -t --long --warn-long 69.5 src/sage/interfaces/expect.py  # 1 doctest failed
----------------------------------------------------------------------

I think this is completely unrelated and random; I have cleaned up an empty line in the commit, so a new run should be triggered soon.

comment:5 Changed 7 years ago by vdelecroix

Reviewers: Vincent Delecroix
Status: needs_reviewneeds_work

Hello,

  1. Why a special care for CombinatorialClass is even needed at all? The following would be much simpler
    category = EnumeratedSets()
    if set in Sets().Finite() or isinstance(set, (list,tuple)):
        category = category.Finite()
    elif set in Sets().Infinite():
        category = category.Infinite()
    
  1. Your documentation lines are too long.

Vincent

comment:6 Changed 2 years ago by mkoeppe

Cc: tscrim added
Milestone: sage-6.8sage-9.3

comment:7 Changed 2 years ago by mkoeppe

Milestone: sage-9.3sage-9.4

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

comment:8 Changed 19 months ago by mkoeppe

Milestone: sage-9.4sage-9.5

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

comment:9 Changed 14 months ago by mkoeppe

Milestone: sage-9.5sage-9.6

comment:10 Changed 10 months ago by mkoeppe

Milestone: sage-9.6sage-9.7

comment:11 Changed 6 months ago by mkoeppe

The bug illustrated by the example in the ticket description is still present in 9.7.beta8

The underlying implementation has changed. CombinatorialClass is no longer involved. The bug is now in sage.misc.mrange._is_finite (used by sage.combinat.cartesian_product):

sage: from sage.misc.mrange import _is_finite
sage: from sage.sets.set_from_iterator import EnumeratedSetFromIterator
sage: EnumeratedSetFromIterator(ZZ).category()
Category of facade enumerated sets
sage: _is_finite(EnumeratedSetFromIterator(ZZ))
True
Last edited 6 months ago by mkoeppe (previous) (diff)

comment:12 Changed 6 months ago by mkoeppe

A comment in _is_finite: "We usually assume L is finite for speed reasons"

comment:13 Changed 6 months ago by mkoeppe

Dependencies: #19195

This can be solved by #19195: getting rid of the ancient class sage.combinat.cartesian_product

comment:14 Changed 5 months ago by mkoeppe

Milestone: sage-9.7sage-9.8

comment:15 Changed 7 days ago by mkoeppe

Milestone: sage-9.8sage-9.9
Note: See TracTickets for help on using tickets.