Extended Affine Weyl Groups SD40

[dwbump]

The first version of this patch implementing Affine Weyl Groups was written during Sage Days 40. The original contributers were Daniel Bump, Dan Orr, Anne Schilling, Mark Shimozono, Nicolas Thiery. Subsequently Mark Shimozono added multiple realizations and twisted types.

Depends on #10963
Depends on #14102

CC: @sagetrac-sage-combinat @anneschilling @nthiery @sagetrac-mshimo @tscrim

Component: combinatorics

Keywords: days54, coxeter, days64, days65

Author: Daniel Bump, Dan Orr, Anne Schilling, Mark Shimozono, Nicolas M. Thiéry

Branch: f549344

Reviewer: Dan Bump, Anne Schilling

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

[dwbump]

Attachment: trac_15375-extended_affine_weyl_groups_sd40.patch.gz

Implements Extended Affine Iwahori Hecke Algebras

[anneschilling]

Branch: public/combinat/extended_affine_weyl_groups-15375

[anneschilling]

Commit: 6d9dd29

[anneschilling]

New commits:

0251a33	Trac #13394: Implement faster and safer WeakValueDictionary
9d9cae3	# Sat Oct 19 11:50:04 2013 +0200
b2914f3	# Sun Oct 27 13:58:49 2013 +0100
362fd5e	# Tue Oct 29 20:14:19 2013 +0100
dfc1fe8	#14102: Nonsymmetric Macdonald polynomials
4c44e62	imported patch extended_affine_weyl_groups_sd40.patch
6d9dd29	fixed extended affine Weyl groups

[sagetrac-git]

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

6e72564

added prefix support for extended affine Weyl groups

[sagetrac-git]

Changed commit from 6d9dd29 to 6e72564

[sagetrac-git]

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

e293db9

added dual form of translation lattices

[sagetrac-git]

Changed commit from 6e72564 to e293db9

[sagetrac-mshimo]

comment:11

Doctests now pass

[sagetrac-git]

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

69b9116

fixed bug in type BCdual

[sagetrac-git]

Changed commit from e293db9 to 69b9116

[sagetrac-git]

Changed commit from 69b9116 to 90ed1b1

[sagetrac-git]

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

90ed1b1

changed calling syntax

[fchapoton]

Changed keywords from days54 to days54, coxeter

[sagetrac-git]

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

fb8a6e0

fund gp special nodes returns tuple

[sagetrac-git]

Changed commit from 90ed1b1 to fb8a6e0

[anneschilling]

comment:118

Replying to @dwbump:

On my machine it builds and all tests pass. But two buildbots are failing to build with cython errors.

Surely this can have nothing to do with this patch.

I'm changing the status to needs_review. I hesitate to change it to positive_review until the patchbot is happy.

For me everything builds fine. I ran sage -testall and got the following failures

sage -t src/sage/groups/perm_gps/permgroup_named.py
**********************************************************************
File "src/sage/groups/perm_gps/permgroup_named.py", line 2609, in sage.groups.perm_gps.permgroup_named.PSL.ramification_module_decomposition_hurwitz_curve
Failed example:
    G.ramification_module_decomposition_hurwitz_curve() # random, optional - database_gap
Exception raised:
    Traceback (most recent call last):
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.groups.perm_gps.permgroup_named.PSL.ramification_module_decomposition_hurwitz_curve[1]>", line 1, in <module>
        G.ramification_module_decomposition_hurwitz_curve() # random, optional - database_gap
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/groups/perm_gps/permgroup_named.py", line 2630, in ramification_module_decomposition_hurwitz_curve
        mults = gap.eval("ram_module_hurwitz("+str(q)+")")
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/interfaces/gap.py", line 568, in eval
        result = Expect.eval(self, input_line, **kwds)
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/interfaces/expect.py", line 1239, in eval
        for L in code.split('\n') if L != ''])
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/interfaces/gap.py", line 766, in _eval_line
        raise RuntimeError(message)
    RuntimeError: Gap produced error output
    Error, sorry, the GAP Tables Of Marks Library is not installed

       executing ram_module_hurwitz(13);
**********************************************************************
File "src/sage/groups/perm_gps/permgroup_named.py", line 2657, in sage.groups.perm_gps.permgroup_named.PSL.ramification_module_decomposition_modular_curve
Failed example:
    G.ramification_module_decomposition_modular_curve() # random, optional - database_gap
Exception raised:
    Traceback (most recent call last):
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.groups.perm_gps.permgroup_named.PSL.ramification_module_decomposition_modular_curve[1]>", line 1, in <module>
        G.ramification_module_decomposition_modular_curve() # random, optional - database_gap
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/groups/perm_gps/permgroup_named.py", line 2674, in ramification_module_decomposition_modular_curve
        mults = gap.eval("ram_module_X("+str(q)+")")
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/interfaces/gap.py", line 568, in eval
        result = Expect.eval(self, input_line, **kwds)
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/interfaces/expect.py", line 1239, in eval
        for L in code.split('\n') if L != ''])
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/interfaces/gap.py", line 766, in _eval_line
        raise RuntimeError(message)
    RuntimeError: Gap produced error output
    Error, sorry, the GAP Tables Of Marks Library is not installed

       executing ram_module_X(7);
**********************************************************************
2 items had failures:
   1 of   3 in sage.groups.perm_gps.permgroup_named.PSL.ramification_module_decomposition_hurwitz_curve
   1 of   3 in sage.groups.perm_gps.permgroup_named.PSL.ramification_module_decomposition_modular_curve
    [439 tests, 2 failures, 3.16 s]
----------------------------------------------------------------------
sage -t src/sage/groups/perm_gps/permgroup_named.py  # 2 doctests failed
----------------------------------------------------------------------
Total time for all tests: 3.3 seconds
    cpu time: 2.3 seconds
    cumulative wall time: 3.2 seconds

sage -t src/sage/tests/gap_packages.py
**********************************************************************
File "src/sage/tests/gap_packages.py", line 15, in sage.tests.gap_packages
Failed example:
    test_packages(['atlasrep', 'tomlib'])    # optional - database_gap
Expected:
      Status   Package    GAP Output
    +--------+----------+------------+
               atlasrep   true
               tomlib     true
Got:
      Status    Package    GAP Output
    +---------+----------+------------+
      Failure   atlasrep   fail
      Failure   tomlib     fail
**********************************************************************
1 item had failures:
   1 of   4 in sage.tests.gap_packages
    [9 tests, 1 failure, 0.18 s]
----------------------------------------------------------------------
sage -t src/sage/tests/gap_packages.py  # 1 doctest failed
----------------------------------------------------------------------
Total time for all tests: 0.2 seconds
    cpu time: 0.2 seconds
    cumulative wall time: 0.2 seconds

I do not think they are related to this branch. So unless there is something else, I guess we can set positive review.

[tscrim]

comment:119

In decreasing probability, it looks like your database_gap optional spkg is out of date, mis-/not installed, or needs optional GAP packages installed directly into GAP. I'd try running sage -i database_gap and sage -i gap_packages and then running those tests again to see if they work.

[dwbump]

comment:120

Any conjectures about the patchbot?

I presume that the patchbot merges the patch on top of the develop tip then tries to build. Is that correct? It looks from the log as if it actually tries to merge it with a branch called patchbot/base. There doesn't actually seem to be such a branch in the repository.

[anneschilling]

comment:121

Thanks Travis, that did the trick. For me all tests pass now.

Replying to @dwbump:

Any conjectures about the patchbot?

I presume that the patchbot merges the patch on top of the develop tip then tries to build. Is that correct? It looks from the log as if it actually tries to merge it with a branch called patchbot/base. There doesn't actually seem to be such a branch in the repository.

On my local computer, I merged in the latest development version sage-6.8.beta6 and everything merged fine. So I think something is wrong with the patchbot.

I am going to set positive review, since we all seem happy with the patch.

[dwbump]

comment:122

Right, I ran all the tests yesterday after a distclean build and there were no failures.

I am going to set positive review, since we all seem happy with the patch.

[vbraun]

comment:124

l.165775 \end{gather}
                     \paragraph{Fundamental group of affine Dynkin automorph...

? 
! Emergency stop.
\math@cr@@@ ...@ \@ne \add@amps \maxfields@ \omit 
                                                  \kern -\alignsep@ \iftag@ ...
l.165775 \end{gather}
                     \paragraph{Fundamental group of affine Dynkin automorph...

!  ==> Fatal error occurred, no output PDF file produced!
Transcript written on combinat.log.
Makefile:55: recipe for target 'combinat.pdf' failed
make[2]: *** [combinat.pdf] Error 1

[sagetrac-mshimo]

comment:125

The build of pdf documentation fails. It outputs algebra.pdf and then seems to hang.
I have no idea what is going on. I didn't see a log file generated for this.

[jdemeyer]

comment:126

Now that this ticket needs_work anyway:

In the 4 files that you're adding in this ticket: please use the standard copyright statement as explained in http://doc.sagemath.org/html/en/developer/coding_basics.html#headings-of-sage-library-code-files

Currently, two of the files have no copyright statement and two do not state the GPL version.

[dwbump]

comment:127

Here is a log of the results of !sage --docbuild reference pdf

http://match.stanford.edu/pdflog

(Temporary URL)

[jhpalmieri]

comment:128

By default, a .. MATH:: block is automatically enclosed in a math environment, so you shouldn't use an environment like align* there: it gets turned into something like

\begin{gather}
\begin{align*}
...
\end{align*}
\end{gather}

which is not valid LaTeX. To avoid the default, you can add :nowrap: at the beginning of the math block, or you can use an environment like aligned instead. This will fix it, but I would instead choose only one of these two approaches (instead of switching between them, as I've done here):

diff --git a/src/sage/combinat/root_system/extended_affine_weyl_group.py b/src/sage/combinat/root_system/extended_affine_weyl_group.py
index 7d35cac..56d9e6d 100644
--- a/src/sage/combinat/root_system/extended_affine_weyl_group.py
+++ b/src/sage/combinat/root_system/extended_affine_weyl_group.py
@@ -155,6 +155,7 @@ def ExtendedAffineWeylGroup(cartan_type, general_linear=None, **print_options):
     There are isomorphisms
 
     .. MATH::
+       :nowrap:
 
         \begin{align*}
             W &\cong M \rtimes W_0 \cong W_0 \ltimes M \\
diff --git a/src/sage/groups/group_semidirect_product.py b/src/sage/groups/group_semidirect_product.py
index 627056f..63b8769 100644
--- a/src/sage/groups/group_semidirect_product.py
+++ b/src/sage/groups/group_semidirect_product.py
@@ -152,11 +152,11 @@ class GroupSemidirectProduct(CartesianProduct):
         
     .. MATH::
 
-        \begin{align*}
+        \begin{aligned}
         (g_1,h_1)(g_2,h_2) &= g_1 h_1 g_2 h_2 \\
         &= g_1 g_2 g_2^{-1} h_1 g_2 h_2 \\
         &= (g_1g_2, twist(g_2^{-1}, h_1) h_2)
-        \end{align*}
+        \end{aligned}
 
     If ``act_to_right`` is False, the group `G \rtimes H` is specified by a homomorphism `\psi\in \mathrm{Hom}(H,\mathrm{Aut}(G))`
     such that
@@ -175,11 +175,11 @@ class GroupSemidirectProduct(CartesianProduct):
 
     .. MATH::
 
-        \begin{align*}
+        \begin{aligned}
         (g_1,h_1)(g_2,h_2) &= g_1 h_1 g_2 h_2 \\
         &= g_1 h_1 g_2 h_1^{-1} h_1 h_2 \\
         &= (g_1 twist(h_1,g_2), h_1 h_2)
-        \end{align*}
+        \end{aligned}
 
     If ``prefix0`` (resp. ``prefixl``) is not None then it is used as a wrapper for
     printing elements of ``G`` (resp. ``H``). If ``print_tuple`` is True then elements are printed

[dwbump]

comment:129

There is a huge file called !doc/output/latex/en/reference/combinat/ and at line 165376 we have the following:

There are isomorphisms
\begin{gather}
\begin{split}\begin{align*}
    W &\cong M \rtimes W_0 \cong W_0 \ltimes M \\
    E &\cong L \rtimes W_0 \cong W_0 \ltimes L
\end{align*}\end{split}\notag
\end{gather}\paragraph{Fundamental group of affine Dynkin automorphisms}

At this point pdflatex barfs.

[sagetrac-mshimo]

comment:130

Thanks, Dan, that is very helpful. I will fix the doc.

[tscrim]

comment:131

As John had mentioned, you need to change:

-        \begin{align*}
+        \begin{aligned}
             W &\cong M \rtimes W_0 \cong W_0 \ltimes M \\
             E &\cong L \rtimes W_0 \cong W_0 \ltimes L
-        \end{align*}
+        \begin{aligned}

and

     .. MATH::
 
-        \begin{align*}
+        \begin{aligned}
         (g_1,h_1)(g_2,h_2) &= g_1 h_1 g_2 h_2 \\
         &= g_1 g_2 g_2^{-1} h_1 g_2 h_2 \\
         &= (g_1g_2, twist(g_2^{-1}, h_1) h_2)
-        \end{align*}
+        \end{aligned}

Also I believe this needs to be changed (there are 2 of theses):

     .. MATH::
 
-        g h g^{-1} &= \phi(g)(h).
+        g h g^{-1} = \phi(g)(h).

[sagetrac-git]

Changed commit from ee155e4 to f549344

[sagetrac-git]

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

f549344

fixed doc errors

[dwbump]

comment:133

Sage now builds, reference.pdf builds and all tests pass. I'm setting status back to positive review.

[vbraun]

Changed branch from public/15375 to f549344

[jdemeyer]

Changed commit from f549344 to none

[jdemeyer]

Changed author from Daniel Bump, Dan Orr, Anne Schilling, Mark Shimozono, Nicolas Thiery. to Daniel Bump, Dan Orr, Anne Schilling, Mark Shimozono, Nicolas M. Thiéry

[kcrisman]

Changed author from Daniel Bump, Dan Orr, Anne Schilling, Mark Shimozono, Nicolas M. Thiéry to Dan Bump, Dan Orr, Anne Schilling, Mark Shimozono, Nicolas M. Thiéry

[fchapoton]

Changed author from Dan Bump, Dan Orr, Anne Schilling, Mark Shimozono, Nicolas M. Thiéry to Daniel Bump, Dan Orr, Anne Schilling, Mark Shimozono, Nicolas M. Thiéry