Opened 8 years ago

Last modified 6 years ago

#12278 new defect

misleading (outdated) docstring in partitions_restricted

Reported by: AlexGhitza Owned by: sage-combinat
Priority: minor Milestone: sage-6.4
Component: combinatorics Keywords: partitions docstring
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by andrew.mathas)

The docstring for partitions_restricted says that the function is deprecated and one should instead use RestrictedPartitions. However, this also turns out to be deprecated. It would be good to fix this.

And here is a more serious problem: the way that is now recommended for obtaining the list of restricted partitions is Partitions(n, parts_in=S). However, Partitions cannot have both parts_in and length specified, so not all the functionality of the old partitions_restricted remains available.

Update: Following this discussion on sage-combinat, it has been agreed that the functionality of RestrictedPartitions? should be fully implemented in Partitions by allowing the combination of different keyword argument. The problem with the current implementation is already highlighted in the documentation for Partitions():

Right now, the "parts_in", "starting", and "ending" keyword
arguments are mutually exclusive, both of each other and of other
keyword arguments. If you specify, say, "parts_in", all other
keyword arguments will be ignored; "starting" and "ending" work the
same way.

The code should allow keywords to Partitions() to be used in any way that makes sense. In particular, it is not currently possible to combine the arguments parts_in and max_length, for example. For this reason RestrictedPartition?() has not been deprecated yet. Note, however, that RestrictedPartitions is essentially a wrapper to gap function call, which makes it quite slow. In contrast, the use of parts_in is quite quick.

Change History (13)

comment:1 Changed 8 years ago by AlexGhitza

  • Description modified (diff)

comment:2 Changed 8 years ago by andrew.mathas

  • Description modified (diff)

comment:3 Changed 8 years ago by nthiery

For the record, here is an example from John Palmieri showing that wrong answers can be output silently when mixing parts_in and other arguments:

sage: [len(p) for p in Partitions(10, length=6, parts_in=[1,2])]
[5, 6, 7, 8, 9, 10]
sage: Partitions(10, parts_in=[1,2]).cardinality() == Partitions(10, length=6, parts_in=[1,2]).cardinality()
True

comment:4 Changed 8 years ago by tscrim

Another example which breaks from Alejandro Morales:

Partitions(4,max_slope=-1,max_part=2).list()
[[2,2]]

However it should return [] (i.e. no partitions satisfying the constaints).

comment:5 Changed 8 years ago by andrew.mathas

Here is another related example which I think is incorrect:

sage: Partitions(4,min_slope=-2).list()
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]

In sage (and in mathematics)

sage: Partition([4]) == Partition([4,0])
True

so the partition [4] does not satisfy the constraint min_slope=-2.

In modular representation theory, a partition is said to be e-restricted if the difference of its successive parts is always strictly less than e, for an integer e>1. The partitions index the irreducible representations of the Iwahori-Hecke algebra of the symmetric group at a primitive eth root of unity, or the symmetric group in characteristic e when e is prime.

If min_slope worked the way that I expected it to then Partitions(n, min_slope=1-e) would construct the e-restricted partitions of n.

Last edited 8 years ago by andrew.mathas (previous) (diff)

comment:6 follow-up: Changed 8 years ago by tscrim

Under the constraint max_slope = -1, there would be no partition would satisfy this constraint if we included trailing 0's. Because of this, I feel that the notion of e-restricted should be a different constraint (perhaps include_trailing_zeros=True), and with a warning placed in the documentation about min_slope does not take into account trailing 0's. However I have no strong feelings on this.

Edit: You could use ending=[2], which is currently broken.

sage: Partitions(4,min_slope=-2, ending=[2]).list()
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
sage: Partitions(4, ending=[2]).list()
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
Last edited 8 years ago by tscrim (previous) (diff)

comment:7 in reply to: ↑ 6 Changed 8 years ago by andrew.mathas

Edit: You could use ending=[2] , which is currently broken. sage: Partitions(4, ending=[2] ).list() [[4] , [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]

I don't understand the manual entry for ending which says

If "ending=p" is passed, then the combinatorial class of partitions
at most p in lexicographic order is returned.

but in any case the set that I want when e=3 can currently be obtained using

sage: [mu for mu in Partitions(4, min_slope=-2) if mu[-1]<3]
[[3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]

Checking that the last part is strictly less than e is enough in general.

comment:8 follow-up: Changed 8 years ago by tscrim

It is saying the last entries in the partition are p or using lex ordering reading right-to-left. In an bug-free world:

sage: Partitions(4, ending=[2,2]).list()
[[2,2]]
sage: Partitions(4, ending=[1,1]).list()
[[2,1,1], [1,1,1,1]]

With regards to the lex ordering, I personally think of it as reverse lex ordering (reading right-to-left), but Stanley in ECII calls reading left-to-right rev lex (thus right-to-left would be lex ordering).

For example, what I think of as lex ordering (reading left-to-right):

[4,1,1] > [3,2,1]

and rev lex (reading right to left):

[3,2,1] > [4,1,1]

which is opposite from Stanley.

Could someone with more experience state what the general convention is in partitions, or it this something we just need to state in the documentation (such as using 0-indexing)?

comment:9 in reply to: ↑ 8 Changed 8 years ago by andrew.mathas

Regarding the lexicographic ordering, I disagree with Stanley and always call this the lexicographic ordering. By definition, the lexicographic ordering on partitions should be the "dictionary ordering" where the parts of the partitions are read from left to right and the "letters" are ordered naturally with 1<2<3<.... Hence, for partitions of 5 we have

(1,1,1,1,1)<(2,1,1,1)<(2,2,1)<(3,1,1)<(3,2)<(4,1)<(5)

I think that this is the more common usage. In any case, given Stanley, it seems that both definitions are used so it would be enough in the documentation to state clearly which convention sage uses and perhaps add a warning the sage convention disagrees with the other ordering.

comment:10 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:11 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:12 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:13 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.