Add signed permutations

[csar]

Add support for signed permutations to Sage.

Statistics:

• Which entries are less than zero (done)
• Number of entries less than zero (done)
• Location of descents (keeping in mind there's a 'descent at zero' for signed permutations if the first entry is negative) (done)
• Number of descents (done)
• fdes and fmaj (done)
• Number of Inversions (done)

Most of these don't have proper docstrings yet.

Other things that should be easy:

• 'Absolute value map' (ie, remove all signs). (done)
• Reverse/complement
• Longest Element
• To_matrix (make it compatible with the existing Weyl group stuff?)

Things that might take some time to do the 'right' way:

• Pattern Avoidance
• Bruhat Order
• Signed RSK

[git]

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

​38864fb	Complete merge
​850a786	Add abs to SignedPermutation; probably doesn't work
​d7642e9	Import permutation, add descent and negative entry statistics
​248e197	Fixed lazy_attribute import

[tscrim]

Some other things that would be nice:

• Make this into a permutation group (similar to SymmetricGroup).
• Add methods to transform elements into a SymmetricGroup elements via the natural "diagram folding".
• Implement the even signed permutation group.
• Implement the natural coercions between the above.

I can also do (some of) the reviewing when this is ready too.

[csar]

I'm debating whether it makes sense to split the permutation group aspect off as a separate ticket that depends on this one. I don't suppose it really matters, aside from perhaps making the housekeeping and reviewing easier. I guess I need to think about how Permutations and SymmetricGroup connect first.

[tscrim]

Since this is the first implementation, it would actually make things harder to review IMO. In some ways Permutations and SymmetricGroup have duplication, but there is a good argument for having Permutations to be separate since we don't necessarily want to consider "standard" permutations (i.e. the base set {1, ..., n}).

[git]

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

​198ec1f

Add maj, fdes, fmaj, length, inv

[git]

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

​3ac8edb

Fixed the parent/element/category mess. Hopefully

[git]

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

​b625b66	Add docstring and fix length/sign mixup
​eaf942e	Add permutation statistics for the two choices of order.
​8129479	Add signed permutation option
​68c3427	Add metaclass, start working on cycles
​b3c4751	Finish to_cycles and cycle_string
​cf623c1	Add ability to create signed permutations from cycles

[tscrim]

See also #17411.

[csar]

Replying to tscrim:

See also #17411.

I'm finally in a position to work on this again. Should I work off what you have in #17411 to add the stuff here that doesn't overlap? (Looks like that's mostly the permutation statistics.)

[tscrim]

I would first start by running some timings to see which implementation does better (for signed permutations). (There might be certain situations where one beats the other too.) It might also be worthwhile moving some of the statistics over to #17411 if they work in greater generality.

However before you do timings, it would be a good idea to make sure everything is on equal footing. In particular, the first input to any Element subclass should be a parent object. This is the standard way to create element classes in Sage (this also means you don't have to "recreate" the parent object for every new element; while this is not much overhead, it does give some).

[stumpc5]

I wanted to check what the current status here is? I would like to add signed permutations to FindStat? and this implementation seems to provide everything I need for that...

[tscrim]

At this point, we have signed (and colored) permutations in Sage from #17411. However, I have not compared them to this implementation for efficiency. In the direction of combining the code here, we could add the statistics and come back to an efficiency comparison afterwards.

[stumpc5]

What about the element constructor, I didn't find SignedPermutation([2,-1,3])

[tscrim]

That one is a bit more debatable whether we want that or not. Of course, you can do this:

sage: SP = SignedPermutations(3)
sage: SP([2,-1,3])
[2, -1, 3]
sage: SP([2,-1,3])^2
[-1, -2, 3]

However, it is in line with everything else we do for similar things, so I don't have any real objections.

[kdilks]

I can try and look at this some, but won't have access to a "real" computer until around July 4th.

[csar]

Basically, this seemed to be superseded by #17411 and I wasn't sure what to do about it, so it's languished. I totally missed the notification for comment 15, so never did the work suggested there. I'm happy to go back and work on some of that.