Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

provide a class for partitions with bounded length and minimal part #38904

Open
wants to merge 7 commits into
base: develop
Choose a base branch
from
Open

provide a class for partitions with bounded length and minimal part #38904

wants to merge 7 commits into from

Conversation

mantepse
Copy link
Collaborator

@mantepse mantepse commented Nov 1, 2024

We provide a new class, PartitionsSmallestGE to handle subsets of the constraints length, min_length, max_length and min_part, to make cardinality computations with such constraints reasonable.

Fixes #38897

@github-actions GitHub Actions
Copy link

github-actions bot commented Nov 1, 2024 •
edited
Loading

Documentation preview for this PR (built with commit 4f42af7; changes) is ready! 🎉
This preview will update shortly after each push to this PR.

@fchapoton fchapoton self-assigned this Nov 5, 2024
@mantepse
Copy link
Collaborator Author

@fchapoton, could you please have a look so it doesn't rot away?

fchapoton
fchapoton approved these changes Nov 17, 2024
View reviewed changes
Copy link
Contributor

@fchapoton fchapoton left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ok. Please avoid doing a lot of cleanup work in this kind of ticket.

@mantepse
Copy link
Collaborator Author

mantepse commented Nov 17, 2024 •
edited
Loading

Thank you! Sorry, I couldn't resist.

@mantepse
Copy link
Collaborator Author

mantepse commented Nov 18, 2024 •
edited
Loading

Dear @fchapoton, I would like to put this back to "needs work", because it doesn't quite solve Max' issue, and it's not hard to do that, but I'd like to avoid deprecation of something I just introduced.

Is this OK with you or would you prefer if I open a new pull request?

Ideally, I think there should be a single class for partitions of n with parts in a given set or interval and length in a given interval, which computes the cardinality efficiently using a few case distinctions and a recurrence if necessary.

@mantepse
rename new class to Partitions_parts_length_restricted
5149cdc 
and generalize it to handle also max_part
@mantepse
Copy link
Collaborator Author

This is now much better. Almost all the time is now spent in IntegerListsLex.__init__, which is a pity, but can probably not be fixed in this pull request.

I'm open for a better name for the class Partitions_parts_length_restricted. I'm also open for deprecating PartitionsGreatestLE.

@mantepse
Copy link
Collaborator Author

I find it a bit frustrating that we do not need the IntegerListsLex.__init__ at all to compute the cardinality. It would be nice to have a pattern where such an expensive initialisation is postponed until it's needed.

Failing that, it seems that most of the time is spent in Envelope.__init__. Maybe this can be optimized.

@mantepse
Copy link
Collaborator Author

The solution was very simple, so I implemented it.

Max' problem is still much better solved without using Partitions (it seems to take roughly twice as long), because Partitions has UniqueRepresentation, which is expensive if we call it with very many different arguments - we are creating an entry in the cache not only for each size, but for each restriction.

@mantepse
Copy link
Collaborator Author

@tscrim, there seems to be a problem with FockSpace. In FockSpaceTruncated.F.__init__, the index set is set to be partitions of F._n, but that doesn't seem to be quite true. Could you please check?

sage/src/sage/algebras/quantum_groups/fock_space.py

Lines 1734 to 1759 in 39ebbe4

def __init__(self, F):
r"""
Initialize ``self``.
EXAMPLES::
sage: F = FockSpace(2, truncated=3).natural()
sage: TestSuite(F).run() # long time
"""
self._basis_name = "natural"
# If the cell x is above the cell y
if len(F._multicharge) == 1: # For partitions
self._above = lambda x,y: x[0] < y[0]
else: # For partition tuples
self._above = lambda x,y: x[0] < y[0] or (x[0] == y[0] and x[1] < y[1])
self._addable = lambda la,i: [x for x in la.outside_corners()
if la.content(*x, multicharge=F._multicharge) == i]
self._removable = lambda la,i: [x for x in la.corners()
if la.content(*x, multicharge=F._multicharge) == i]
indices = Partitions(F._n, max_length=F._k)
CombinatorialFreeModule.__init__(self, F.base_ring(), indices,
prefix='', bracket=['|', '>'],
latex_bracket=['\\lvert', '\\rangle'],
sorting_reverse=True,
category=FockSpaceBases(F))

@tscrim
Copy link
Collaborator

tscrim commented Nov 22, 2024

@tscrim, there seems to be a problem with FockSpace. In FockSpaceTruncated.F.__init__, the index set is set to be partitions of F._n, but that doesn't seem to be quite true. Could you please check?

Yes, that is not correct. It should be over all partitions of length \leq k (as per the doc of FockSpaceTruncated).

@mantepse mantepse closed this Nov 22, 2024
@mantepse mantepse reopened this Nov 22, 2024
@mantepse
Copy link
Collaborator Author

OK, I made a catch-all class for partitions which are not restricted by size. This can easily be improved, but I'd prefer to postpone this.

@mantepse
Copy link
Collaborator Author

@fchapoton, is the lint error in error?

Other than that, I think that the pull request should be ready to go.

@fchapoton
Copy link
Contributor

fchapoton commented Nov 22, 2024 •
edited
Loading

somebody should add PLC0206 to the ruff-minimal ignore list in another pull request

DONE; please review #39021

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@fchapoton fchapoton fchapoton approved these changes

@AndrewMathas AndrewMathas Awaiting requested review from AndrewMathas

Assignees

@fchapoton fchapoton

Labels
c: combinatorics s: needs review t: enhancement
Projects
None yet
Milestone
No milestone
3 participants
@mantepse @tscrim @fchapoton