01 sequence or east-north sequence for partitions

[pdehaye]

Adds a method to the partition class that returns the 01 sequence of the partition (the sequence of north or east steps taken along the boundary of the partition). Since this is really an biinfinite sequence starting with 0000000 and ending with 11111111, this should return a a finite list of 0s and 1s, starting for any (non-empty) partition with a 1 and ending with a 0.

Apply:

• attachment: trac_11410-zero_one_sequence_partitions-pod.v2.patch
• attachment: trac_11410-zero_one_sequence_partitions-review-ts.patch

Depends on #13605

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: partition

Author: Paul-Olivier Dehaye

Reviewer: Frédéric Chapoton, Nathann Cohen, Travis Scrimshaw

Merged: sage-5.8.beta4

Issue created by migration from https://trac.sagemath.org/ticket/11410

[pdehaye]

Attachment: trac_11410-zero_one_sequence_partitions-pod.patch.gz

[pdehaye]

comment:1

suggestions for the name welcome

[nathanncohen]

comment:2

Helloooooo !!!

Some remarks/questions :

• Is there really no name for this "0-1 sequence" in the litterature ? `:-/"
• We try to keep our lines to 80 characters at most
• The documentation of "from_zero_one" can not be found easily by the user : these informations should also be given in the documentation of the Partition class. If the user wants to build a partition this way, he/she first has to consult the help of Partition, then read the code, then load the from_zero_one" method manually, then consult its help :-P
• The "INPUT:" field is not a Sphinx field, so only one semicolumn is sufficient. Same thing for OUTPUT.
• I did not really understand of defining the 01 sequence as biinfinite to say just afterwards that it is equivalently defined by a finite sequence.
• I do not find the current definition "that clear". As it is easy to compute, would it be worth giving a formal definition of the transformation from partition to 0-1 sequence in the documentation ?

Nathann

[fchapoton]

comment:3

Apply trac_11410-zero_one_sequence_partitions-pod.v2.patch

Here is patch with some corrections.

[fchapoton]

Author: Paul-Olivier Dehaye

[fchapoton]

Reviewer: Frédéric Chapoton, Nathann Cohen

[fchapoton]

comment:6

Apply trac_11410-zero_one_sequence_partitions-pod.v2.patch

[tscrim]

comment:7

Could you add

sage: Partition(zero_one=[0,0,0,0,1,1,1,1,0,1,0,1,1,1,1,1])
[5, 4]

to from_zero_one() showing that it ignores leading 0's and trailing 1's? Also, I think this should be based on #13072 (it doesn't apply for me after #13072) and possibly #11476 too. I will see if I can find a reference too.

Thanks,

Travis

[AndrewMathas]

comment:8

When I have used these I have called them path sequences or Maya diagrams.

Andrew

[fchapoton]

comment:9

Here is a new patch, rebased on 5.7.beta3.

In my opinion, there remains one problem : the choice of the name.

If nobody comes with a better one, with references, then I think the ticket is good to go, if the light turns green.

[fchapoton]

comment:10

Apply trac_11410-zero_one_sequence_partitions-pod.v2.patch

[darijgr]

comment:11

@name: Richard Stanley (in "The Rank and Minimal Border Strip Decomposition of a Skew Partition", http://arxiv.org/pdf/math/0109092.pdf) calls this the "Comét code" of the partition, probably referring to one of the encodings in Stig Comét's http://www.ams.org/journals/mcom/1955-09-052/S0025-5718-1955-0074954-0/ .

May I suggest implementing a similar back-and-forth conversion for skew partitions and biwords of 0's and 1's? Of course, one could take the Comét code of the inner rim and the outer rim, but then one would have to fumble around with their offsets to make them match, so an implementation in the library would be preferred.

Curiosity question: What is a difference between a normal and an "indirect" doctest?

[tscrim]

comment:12

Replying to @darijgr:

Curiosity question: What is a difference between a normal and an "indirect" doctest?

It's for functions/methods that aren't explicitly called in the doctest. For example Foo._repr_() being called when you execute sage: Foo.

---

As for the patch, the INPUT: block in indented one too many times. Could you put some of the alternative names in the function's documentation? Also I feel like the formatting would be better in latex formatting `1-0`.

A math/documentation note, these also arise from affine permutations and have connections to k-Schur functions (see k-Schur Functions and Affine Schubert Calculus, pages 24-25, http://arxiv.org/abs/1301.3569 and from this you could also justify calling these plus-minus sequences).

Finally could you rebase this on the (soon to be completed) #13605? I'll do the final review if you rebase it as soon as #13605 is done. Promise.

Thank you,

Travis

[fchapoton]

Dependencies: #13605

[tscrim]

comment:14

This fails to apply for me over #13605:

travis@travis-virtualbox:~/sage-5.7.beta3/devel/sage-combinat/sage/combinat$ sage -hg qpush
applying trac_11410-zero_one_sequence_partitions-pod.v2.patch
patching file sage/combinat/partition.py
Hunk #1 FAILED at 205
Hunk #4 FAILED at 292
Hunk #5 FAILED at 301
Hunk #6 succeeded at 442 with fuzz 2 (offset 41 lines).
Hunk #7 succeeded at 2744 with fuzz 1 (offset 531 lines).
3 out of 7 hunks FAILED -- saving rejects to file sage/combinat/partition.py.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac_11410-zero_one_sequence_partitions-pod.v2.patch

[fchapoton]

comment:15

Well, I have not yet rebased the patch, so the hunks are expected. I do not know when I will find time do do that.

[fchapoton]

Attachment: trac_11410-zero_one_sequence_partitions-pod.v2.patch.gz

[fchapoton]

comment:16

Here is a rebased. Still missing things about names..

Apply trac_11410-zero_one_sequence_partitions-pod.v2.patch

[tscrim]

comment:18

Hey Frederic,

I've uploaded a review patch which adds some more info to the documentation. Everything else looks good to me. If you agree with my changes, you can set this to positive review.

Thanks,

Travis

[tscrim]

Changed reviewer from Frédéric Chapoton, Nathann Cohen to Frédéric Chapoton, Nathann Cohen, Travis Scrimshaw

[tscrim]

comment:19

For patchbot:

Apply: trac_11410-zero_one_sequence_partitions-pod.v2.patch, trac_11410-zero_one_sequence_partitions-review-ts.patch

[fchapoton]

comment:20

maybe you could use the very new arxiv role

:arxiv:`1301.3569`

as introduced in #14011

Otherwise, things look good. I am just waiting for the green light from the bot.

[tscrim]

comment:21

Attachment: trac_11410-zero_one_sequence_partitions-review-ts.patch.gz

Done.

For patchbot:

Apply: trac_11410-zero_one_sequence_partitions-pod.v2.patch, trac_11410-zero_one_sequence_partitions-review-ts.patch

[tscrim]

comment:22

The patchbot was blue (due to #13605). I gave it a kick.

For patchbot:

Apply: trac_11410-zero_one_sequence_partitions-pod.v2.patch, trac_11410-zero_one_sequence_partitions-review-ts.patch

[tscrim]

comment:23

Replying to @fchapoton:

Otherwise, things look good. I am just waiting for the green light from the bot.

Since the patchbot gives the go-ahead (when it doesn't timeout), I'm setting this to positive review.

[jdemeyer]

Merged: sage-5.8.beta4