Opened 4 years ago

Closed 9 months ago

#7983 closed defect (fixed)

Notion of descent/major index in tableau.py is not mathematically standard

Reported by: jbandlow Owned by: sage-combinat
Priority: major Milestone: sage-5.12
Component: combinatorics Keywords: combinat, tableaux, days49
Cc: darij, sage-combinat, aschilling, tscrim Merged in: sage-5.12.beta0
Authors: arattan, Darij Grinberg Reviewers: Jason Bandlow, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #8392 Stopgaps:

Description (last modified by tscrim)

The 'descents' and 'major_index' methods of a Tableau return what are more properly known as 'i_descents' and the 'i_maj' statistic. These should be renamed accordingly, and the proper statistics put in their place. See, eg., Richard Stanley--Enumerative Combinatorics, Vol. 2 for a reference to the usual definition.

*EDIT* by Darij:

Apply:

Attachments (3)

Fix_Tableau_Major_Index_AR.patch (4.2 KB) - added by arattan 3 years ago.
patch to fix tableaux major index
trac_7983-major_index_and_other_tableau_fixes-dg.patch (39.7 KB) - added by darij 10 months ago.
implements the right notions of major index and descents for standard tableaux without changing the old ones; extends promotion_inverse to non-rectangular tableaux; fixes a couple minor issues and improves doc; version 8
trac_7983-review-ts.patch (13.7 KB) - added by tscrim 9 months ago.

Download all attachments as: .zip

Change History (27)

comment:1 Changed 3 years ago by arattan

  • Reviewers set to jbandlow
  • Status changed from new to needs_review

I have made a patch that resolves this issue.

What I have done is renamed the old methods 'major_index' and 'descents' to 'i_major_index' and 'i_descents'. From what I can tell, only one other method refers to either of these methods and that is 'inversion', and I have not changed that at all except to refer to the new 'i_descents' (in particular I have not changed the name of 'inversion').

I have then made new methods called 'major_index' and 'descents' which use a more standard definition (i.e. the one on pages 361 and 363 of Enumerative Combinatorics Vol 2 by R. Stanley).

Changed 3 years ago by arattan

patch to fix tableaux major index

comment:2 follow-up: Changed 3 years ago by jbandlow

  • Status changed from needs_review to needs_work

Thanks for the patch! While I don't have time for a full review now, the main issue with this patch is going to be backward compatibility. I'm pretty sure that the Macdonald polynomial code uses these functions, so sage --testall will probably fail after applying your patch. That part will not be too hard to fix, but the bigger problem is for people who have sage code on their own machine. When people upgrade sage and this change is included (without them necessarily knowing about it) this change could make their code behave in slightly wrong ways that are not obvious. We really try to avoid that.

So I think the thing to do is to deprecate 'descents' and 'major_index' (look up deprecation in the developers guide), use 'i_descents' and 'i_major_index' for the existing statistics (as you have done) and give the classical statistics some new name. (Suggestions welcome!)

comment:3 in reply to: ↑ 2 Changed 3 years ago by arattan

Replying to jbandlow:

Thanks for the patch! While I don't have time for a full review now, the main issue with this patch is going to be backward compatibility. I'm pretty sure that the Macdonald polynomial code uses these functions, so sage --testall will probably fail after applying your patch. That part will not be too hard to fix, but the bigger problem is for people who have sage code on their own machine. When people upgrade sage and this change is included (without them necessarily knowing about it) this change could make their code behave in slightly wrong ways that are not obvious. We really try to avoid that.

So I think the thing to do is to deprecate 'descents' and 'major_index' (look up deprecation in the developers guide), use 'i_descents' and 'i_major_index' for the existing statistics (as you have done) and give the classical statistics some new name. (Suggestions welcome!)

Yes, I thought this would be an issue. I actually made the patch a while ago but thought that precisely your objection would be raised. Anyways, I decided to send it in and see what would happen. It sounds like you have a good solution.

About a new name: is "Major_Index" a bad idea? I don't know about sage's naming conventions.

comment:4 Changed 10 months ago by darij

  • Cc darij added

comment:5 Changed 10 months ago by darij

  • Cc sage-combinat aschilling tscrim added
  • Description modified (diff)
  • Keywords combinat tableaux added
  • Status changed from needs_work to needs_review

comment:6 Changed 10 months ago by darij

3 years... not bad.

I've remade the patch from scratch (arattan's one didn't apply, unsurprisingly given its age) without renaming the existing descents, major_index etc. functions. While I agree with arattan that these functions should be deprecated and renamed, I think it's a top priority to get the correct ones out ASAP, under whatever name possible (I chose standard_descents and standard_major_index). I have taken the liberty to edit the docstrings of the old functions to explain that they are not what they seem to be; Jason and me are hardly the only people to trip over this. (To make things worse, the only two examples for the major_index function used to be cases where it happens to have the same values as the "correct" one!!)

The patch I attached does a few more things:

  • Various improvements in the documentation of tableaux.py. The doc of promotion now warns about its nonstandard definition (#14641). A doctest has been added to check the equivalence between two definitions of promotion (this takes a couple seconds; let me know if that's too much).
  • up and down methods are moved to StandardTableaux (look at what they do to see why) and now return the correct result for the empty tableau.
  • The empty tableau is now correctly recognized as being rectangular.

Here's stuff that has not been done (partly because I am not sure about them -- comments are welcome):

  • Copy/move attacking_pairs method to partitions.
  • Generalize promotion_inverse to non-rectangular tableaux (particularly important since I believe promotion_inverse is what many people just call promotion).
  • Tableau([[]]) is standard and distinct from Tableau([]). Is this bad?
  • Copy/move functionality to skew tableaux (this should be one separate huge ticket once other stuff is done, I guess).
  • Allow creating tableaux of various ilks without checking the tableau conditions. This should be mostly called internally, so as to avoid having lots of redundant checking at runtime.

I have been building this patch on sage-5.10rc1 with only #8392 applied.

Last edited 10 months ago by darij (previous) (diff)

comment:7 Changed 10 months ago by darij

  • Authors set to Jason Bandlow, Darij Grinberg
  • Dependencies set to #8392
  • Description modified (diff)

comment:8 Changed 10 months ago by darij

  • Authors changed from Jason Bandlow, Darij Grinberg to arattan, Darij Grinberg

comment:9 Changed 10 months ago by tscrim

Hey Darij,

Two things I notice from a quick lookthrough:

  1. up() and friends I think should remain where they are because there's no assumptions made on the initial tableau. However I do think there are some assumptions about standardness made in their implementation...
  2. The reference to Stanley is indented one too many times.

I'll do a more through look-through and we can talk about 1. once I get to Orsay tomorrow.

Best,
Travis

comment:10 follow-up: Changed 10 months ago by darij

Hi Travis,

thanks for looking into this! I've updated the reference; is it correct now?

As for up, is it possible that you meant standard_descents instead? I can't imagine how up and down would be used for anything other than standard tableaux; is it really useful to have a function to tell how many ways there are to add a square to a non-standard tableau to get a standard one? On the other hand, descents could indeed survive a generalization, though I don't know which choices are preferred here.

Best regards, Darij

comment:11 in reply to: ↑ 10 Changed 10 months ago by aschilling

Hi Darij,

Thanks for your work on this. I think it reads a little odd to write that promotion is contrary to the paper by Stanley without giving a reference to what it actually is. Stanley's paper defines promotion on posets, whereas what you touched I think is promotion on tableaux. So it would be good to give a reference, for example the paper by Haiman, Discrete Math 99 (1992) 79-113.

Best,

Anne

comment:12 follow-up: Changed 10 months ago by darij

Hi Anne,

good point, thanks -- I've added the reference to Haiman, and also a better reference (Sagan's cyclic sieving paper) for the conflicting notation. If you agree, the Stanley reference can be removed (he defines promotion for linear extensions of posets, then claiming that this obviously defines it for tableaux -- this isn't really central to the paper, though).

In other news, I've added documentation to insert_word, slightly improved that of catabolism and lambda_catabolism, and fixed a couple more typos. Since I don't know anything about catabolism, can you tell me if it's OK that catabolism_sequence(Tableau([])) does not terminate? I'm hesitating to call it a bug as long as I don't know if this should be defined at all for an empty tableau.

See you both this evening, dg

Last edited 10 months ago by darij (previous) (diff)

comment:13 in reply to: ↑ 12 Changed 10 months ago by aschilling

Hi Darij,

In other news, I've added documentation to insert_word, slightly improved that of catabolism and lambda_catabolism, and fixed a couple more typos. Since I don't know anything about catabolism, can you tell me if it's OK that catabolism_sequence(Tableau([])) does not terminate? I'm hesitating to call it a bug as long as I don't know if this should be defined at all for an empty tableau.

Yes, probably you want that catabolism_sequence on the empty tableau is the empty tableau. The code only checks if the tableau is of height 1, but catabolism on the empty tableau is itself and hence it goes into an infinite loop.

Best,

Anne

comment:14 Changed 10 months ago by darij

Hi Anne,

done!

I've made one more minor change right now: .up() now outputs standard tableaux, not tableaux (just a question of casting the right type; they were standard, of course).

Best regards, Darij (in Bures now)

PS, in case this was Travis's concern: I've grepped for appearances of .up(), .up_list(), .down() and .down_list() in the source code, and found only 2-3 files apart from tableau.py where these were used. They were used in a different context in those files, and my changes didn't break their doctests. Of course, someone's local code might get broken, but I don't know a good way to avoid that making any change at all. One minor issue that I did introduce is that execution of .up() and .down() now takes a tiny bit longer because of checking for standardness. I'll deal with it when I add a check_input parameter throughout tableaux.py.

comment:15 Changed 10 months ago by darij

Updated. promotion_inverse now works for non-rectangular tableaux as well (using a new _slide_down method). Moreover, it works fine for the empty tableau. Furthermore, promotion and promotion_inverse have been redefined on StandardTableau to automatically compute the n variable and to cast the result as a StandardTableau (not just a Tableau).

comment:16 Changed 10 months ago by darij

  • Keywords days49 added

Changed 10 months ago by darij

implements the right notions of major index and descents for standard tableaux without changing the old ones; extends promotion_inverse to non-rectangular tableaux; fixes a couple minor issues and improves doc; version 8

comment:17 Changed 10 months ago by darij

Typo in a docstring fixed.

comment:18 Changed 10 months ago by tscrim

  • Description modified (diff)
  • Reviewers changed from jbandlow to Jason Bandlow, Travis Scrimshaw

Hey Darij,

Here's the review patch.

Travis

comment:19 Changed 10 months ago by darij

  • Status changed from needs_review to positive_review

comment:20 Changed 9 months ago by darij

Let's see if I'm getting the syntax right... patchbot:

apply trac_7983-major_index_and_other_tableau_fixes-dg.patch trac_7983-review-ts.patch

Changed 9 months ago by tscrim

comment:21 Changed 9 months ago by tscrim

Hey Darij,

I noticed a duplicate reference of [St2009]. It's already defined in posets/poset.py. I just tweaked my review patch to remove it from tableau.py.

Best,
Travis

comment:22 Changed 9 months ago by tscrim

Forgot to give the patchbot info.

For patchbot:

Apply: trac_7983-major_index_and_other_tableau_fixes-dg.patch trac_7983-review-ts.patch

comment:23 Changed 9 months ago by jdemeyer

  • Milestone set to sage-5.12

comment:24 Changed 9 months ago by jdemeyer

  • Merged in set to sage-5.12.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.