Nonsymmetric Macdonald Polynomials for all affine types

[dwbump]

This ticket implements nonsymmetric Macdonald polynomials for
arbitrary affine Cartan type (including twisted and BC, but not
Koornwinder) using the recursion formula in terms of Demazure-Lusztig
and Cherednik operators. It complements the type-A implementation
based on the HHL combinatorial formula of #2708.

This patch was written by Anne Schilling and Nicolas M. Thiéry during
the ICERM Semester Program on "Automorphic Forms, Combinatorial
Representation Theory and Multiple Dirichlet Series" (January 28,
2013 - May 3, 2013) with the help of Dan Bump, Ben Brubaker, Bogdan
Ion, Dan Orr, Arun Ram, Siddhartha Sahi, and Mark Shimozono. Special
thanks go to Bogdan Ion and Mark Shimozono for their patient
explanations and hand computations to check the code.

In a follow-up ticket #14847 Whittaker functions and other features will become available.

Depends on #4327
Depends on #14143
Depends on #13589
Depends on #10963
Depends on #14673
Depends on #14610
Depends on #14775
Depends on #15931

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: Nonsymmetric Macdonald polynomials, days40, days45, days49, days54, ICERM2013

Work Issues: doc-pdf

Author: Nicolas M. Thiéry, Anne Schilling

Branch/Commit: a0ceb91

Reviewer: Anne Schilling, Nicolas M. Thiéry, Mark Shimozono, Bogdan Ion

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

[anneschilling]

Changed keywords from Nonsymmetric Macdonald to Nonsymmetric Macdonald polynomials, days40, days45

[anneschilling]

Changed keywords from Nonsymmetric Macdonald polynomials, days40, days45 to Nonsymmetric Macdonald polynomials, days40, days45, days49

[anneschilling]

Author: Nicolas M. Thiery, Anne Schilling

[anneschilling]

Dependencies: #4327, #14143, #10963, #14673, #14610

[anneschilling]

Reviewer: Nicolas M. Thiery, Anne Schilling, Mark Shimozono, Bogdan Ion

[nthiery]

Changed reviewer from Nicolas M. Thiery, Anne Schilling, Mark Shimozono, Bogdan Ion to Anne Schilling, Nicolas M. Thiéry, Mark Shimozono, Bogdan Ion

[nthiery]

Changed author from Nicolas M. Thiery, Anne Schilling to Nicolas M. Thiéry, Anne Schilling

[sagetrac-mshimo]

comment:7

Anne and Nicolas,

The family returned by NonSymmetricMacdonaldPolynomials should possess a method
that gives direct access to the affine Hecke representation of which it is a basis.

I would like to add symmetric Macdonald polynomials to this patch.
It should be straightforward, especially if the AHA representation is at hand.

[anneschilling]

comment:8

Hi Mark,

The family returned by NonSymmetricMacdonaldPolynomials should possess a method
that gives direct access to the affine Hecke representation of which it is a basis.

Do you mean that you want the operators

        T   = KL.twisted_demazure_lusztig_operators     (   q1, q2, convention="dominant")
        T_Y = KL.demazure_lusztig_operators_on_classical(q, q1, q2, convention="dominant")

directly available? Or in which format do you want the Hecke algebra representation? You can get

sage: E = NonSymmetricMacdonaldPolynomials(["A",2,1])
sage: E._KL
Group algebra of the Ambient space of the Root system of type ['A', 2, 1] over Fraction Field of Multivariate Polynomial Ring in q, q1, q2 over Rational Field

Best,

Anne

[sagetrac-mshimo]

comment:9

Anne,

The methods I wanted were hidden in the _T and _T_Y attributes.

Why does twisted_demazure_lusztig_operators use classical().dual().affine().dual()?
I believe this is correct for untwisted root systems but why do
we know this is correct for twisted root systems? If this is a bug it only affects the
zero-th Hecke operator.

[nthiery]

comment:10

Replying to @sagetrac-mshimo:

The methods I wanted were hidden in the _T and _T_Y attributes.

Ok. Feel free to add whichever accessors you might think relevant.

Why does twisted_demazure_lusztig_operators use classical().dual().affine().dual()?
I believe this is correct for untwisted root systems but why do
we know this is correct for twisted root systems? If this is a bug it only affects the
zero-th Hecke operator.

Well, it's not a bug, since we get the correct results :-)

More seriously: The cartan type as specified here is actually not really used, except for testing for the relations. It indeed looks dubious and should at some point be rewritten using the "other_affinization" method and the like. We must have been lucky to specify a type
that gives the same Coxeter group.

So, if you have a short way to specify the cartan type which you believe is more correct, please go ahead. Otherwise I think this can wait until someone reimplements T0_check in a less ad-hock way.

Cheers,
Nicolas

[nthiery]

comment:11

Replying to @sagetrac-mshimo:

I would like to add symmetric Macdonald polynomials to this patch.
It should be straightforward, especially if the AHA representation is at hand.

Cool. Since this patch is quite big already, I guess that could go in a followup ticket like the whittaker function one.

[sagetrac-mshimo]

comment:12

Nicolas,

Well, it's not a bug, since we get the correct results :-)

Do you know of an independent way to compute the nonsymmetric Macdonald polynomial
for twisted root systems, not just the t=0 specialization?
How was this verified?

[anneschilling]

comment:13

Hi Mark,

Do you know of an independent way to compute the nonsymmetric Macdonald polynomial
for twisted root systems, not just the t=0 specialization?
How was this verified?

The code currently checks that the results (i.e. the nonsymmetric Macdonald polynomials) are indeed eigenvectors of the Y operators. These conditions are not easy to satisfy. For types A_n^{(1)}, B_n^{(1)}, BC_n^{(2)} and BC_n^{(2)}-dual the NSMs were carefully compared against Bogdan Ion's hand and maple computations. If you are worried, I can ask him to confirm type A_{2n-1}^{(2)} as well.

Best,

Anne

[sagetrac-mshimo]

comment:15

Nicolas,

I added symmetric macdonald polynomials, fixed the parabolic root system stuff,
and edited the docs for nonsymmetric macdonalds rather extensively.
I already folded my review patch onto the given patch.
Please have a look and if it is ok, replace the above exported patch (I don't have sufficient
permissions to do so).

--Mark

[anneschilling]

comment:16

Hi Mark,

Thank you for adding the parabolic root stuff and the symmetric Macdonald polynomials. Usually it is much better not to fold your patch straight in, so that the other people can review your changes first.

Best,

Anne

[nthiery]

comment:17

Mark's review patch can be retrieved from the queue history: http://combinat.sagemath.org/patches/rev/f9a14d979bb9

I am reviewing it now.

[tscrim]

comment:84

That's a good benchmark to know. Thanks Nicolas.

[sagetrac-git]

Changed commit from 7285efe to 0d766ab

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. Last 10 new commits:

8da7522	Trac 10963: degraded a bit a newly added cross-link to work around 'make doc-clean; make clean' failure
4ef8b27	Merge branch 'public/ticket/10963-doc-distributive' of git://trac.sagemath.org/sage into 10963new
afb911c	corrected conflict resolution
82c8ee0	Merge branch 'public/ticket/10963-doc-distributive' of trac.sagemath.org:sage into public/ticket/10963-doc-distributive
96c631f	Merge branch 'develop' into categories/axioms-10963
b1a2aed	Trac 10963: two typo fixes to let the pdf documentation compile
c16f18b	Merge branch 'public/ticket/10963-doc-distributive' of trac.sagemath.org:sage into categories/axioms-10963
a38b62c	Merge branch 'public/ticket/10963-doc-distributive' of trac.sagemath.org:sage into public/ticket/10963-doc-distributive
b162cfd	Merge branch 'develop' into public/ticket/10963-doc-distributive
0d766ab	Merge branch 'public/combinat/nonsymmetric_macdonald-14102' of trac.sagemath.org:sage into public/combinat/nonsymmetric_macdonald-14102

[tscrim]

comment:87

Trivial rebase over latest #10963.

[vbraun]

comment:88

pdf docs don't build

[vbraun]

Work Issues: doc-pdf

[anneschilling]

comment:89

Replying to @vbraun:

pdf docs don't build

Is this related to this patch? I get the following error:

Overfull \hbox (27.79457pt too wide) in paragraph at lines 54386--54386
\T1/ptm/m/it/10 bose=False\T1/pcr/m/n/10 ) 
[597] [598] [599] [600] [601] [602] [603] [604] [605] [606]
Chapter 6.
[607] [608]
Underfull \hbox (badness 6380) in paragraph at lines 55235--55239
[]\T1/ptm/m/n/10 Aric Hag-berg, Dan Schult and Pieter Swart. Net-workX doc-u-me
n-ta-tion. [On-line] Avail-able:

Underfull \hbox (badness 10000) in paragraph at lines 55291--55295
[]\T1/ptm/m/n/10 Stephen P Bor-gatti. (1995). Cen-tral-ity and AIDS. [On-line] 
Avail-able:

Underfull \hbox (badness 7558) in paragraph at lines 55296--55301
[]\T1/ptm/m/n/10 Coen Bron and Joep Ker-bosch. (1973). Al-go-rithm 457: Find-in
g All Cliques of an

Underfull \hbox (badness 5667) in paragraph at lines 55296--55301
\T1/ptm/m/n/10 Undi-rected Graph. Com-mun. ACM. v 16. n 9. pages 575-577. ACM P
ress. [On-line] Avail-able:
[609]
Underfull \hbox (badness 10000) in paragraph at lines 55416--55420
[]\T1/ptm/m/n/10 Fifth An-nual Graph Draw-ing Con-test P. Eaded, J. Marks, P.Mu
tzel, S. North
[610] [611] [612]
Underfull \hbox (badness 10000) in paragraph at lines 55704--55709
[]\T1/ptm/m/n/10 Computing Tutte Poly-no-mi-als. Gary Hag-gard, David J. Pearce
 and Gor-don Royle.

Underfull \hbox (badness 10000) in paragraph at lines 55704--55709
\T1/ptm/m/n/10 In ACM Trans-ac-tions on Math-e-mat-i-cal Soft-ware, Vol-ume 37(
3), ar-ti-cle 24, 2010. Preprint:
[613] [614] [615] (./graphs.ind [616] [617] [618] [619] [620] [621] [622]
[623] [624] [625] [626] [627] [628] [629] [630] [631] [632] [633] [634]
[635]) [636] (./graphs.aux) )
(see the transcript file for additional information){/usr/local/texlive/2008/te
xmf-dist/fonts/enc/dvips/base/8r.enc}</usr/local/texlive/2008/texmf-dist/fonts/
type1/bluesky/cm/cmex10.pfb></usr/local/texlive/2008/texmf-dist/fonts/type1/blu
esky/cm/cmmi10.pfb></usr/local/texlive/2008/texmf-dist/fonts/type1/bluesky/cm/c
mmi5.pfb></usr/local/texlive/2008/texmf-dist/fonts/type1/bluesky/cm/cmmi7.pfb><
/usr/local/texlive/2008/texmf-dist/fonts/type1/bluesky/cm/cmr10.pfb></usr/local
/texlive/2008/texmf-dist/fonts/type1/bluesky/cm/cmr5.pfb></usr/local/texlive/20
08/texmf-dist/fonts/type1/bluesky/cm/cmr7.pfb></usr/local/texlive/2008/texmf-di
st/fonts/type1/bluesky/cm/cmsy10.pfb></usr/local/texlive/2008/texmf-dist/fonts/
type1/bluesky/cm/cmsy5.pfb></usr/local/texlive/2008/texmf-dist/fonts/type1/blue
sky/cm/cmsy7.pfb></usr/local/texlive/2008/texmf-dist/fonts/type1/bluesky/ams/ms
am10.pfb></usr/local/texlive/2008/texmf-dist/fonts/type1/bluesky/ams/msbm10.pfb
></usr/local/texlive/2008/texmf-dist/fonts/type1/urw/courier/ucrb8a.pfb></usr/l
ocal/texlive/2008/texmf-dist/fonts/type1/urw/courier/ucrr8a.pfb></usr/local/tex
live/2008/texmf-dist/fonts/type1/urw/courier/ucrro8a.pfb></usr/local/texlive/20
08/texmf-dist/fonts/type1/urw/helvetic/uhvb8a.pfb></usr/local/texlive/2008/texm
f-dist/fonts/type1/urw/helvetic/uhvbo8a.pfb></usr/local/texlive/2008/texmf-dist
/fonts/type1/urw/helvetic/uhvr8a.pfb></usr/local/texlive/2008/texmf-dist/fonts/
type1/urw/times/utmb8a.pfb></usr/local/texlive/2008/texmf-dist/fonts/type1/urw/
times/utmr8a.pfb></usr/local/texlive/2008/texmf-dist/fonts/type1/urw/times/utmr
i8a.pfb>
Output written on graphs.pdf (640 pages, 2603829 bytes).
Transcript written on graphs.log.
make: *** [doc-pdf] Error 1

But as far as I know this branch does not touch graphs.

[vbraun]

comment:90

The actual error is higher up. The end of the log just shows that the graphs part did build successfully.

[sagetrac-git]

Changed commit from 0d766ab to a0ceb91

[sagetrac-git]

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

a0ceb91

14102: fixed pdf documentation compilation: citation keys shall not use '_'

[vbraun]

Changed branch from public/combinat/nonsymmetric_macdonald-14102 to a0ceb91