Sage Days 20.5 demonstration -- Misc talks, demos, tutorials, ... using Sage v4.3.4
system:sage

<div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="genindex.html" title="General Index" accesskey="I">index</a></li>
        <li class="right">
          <a href="object_class_talk.html" title="Objects and Classes in Python and Sage" accesskey="N">next</a> |</li>
        <li class="right">
          <a href="2010-03-29-SLC64.html" title="SLC 64 demonstration" accesskey="P">previous</a> |</li>
  
    
      <a href="../index.html"><img src="_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
    
  
  
        <li><a href="index.html">Misc talks, demos, tutorials, ... using Sage v4.3.4</a> &raquo;</li>
 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body">
            
  <div class="section" id="sage-days-20-5-demonstration">
<h1>Sage Days 20.5 demonstration<a class="headerlink" href="#sage-days-20-5-demonstration" title="Permalink to this headline">¶</a></h1>
<div class="highlight-python">

{{{id=0|
%hide
pretty_print_default()
///
}}}

</div>
<div class="section" id="a-demonstration-of-sage-gap4-gap3-chevie-semigroupe">
<h2>A demonstration of Sage + GAP4 + GAP3 + Chevie + Semigroupe<a class="headerlink" href="#a-demonstration-of-sage-gap4-gap3-chevie-semigroupe" title="Permalink to this headline">¶</a></h2>
<p>Let us create the Coxeter group W:</p>
<div class="highlight-python">

{{{id=1|
W = CoxeterGroup([&quot;H&quot;,4]); W
///
}}}

</div>
<p>It is constructed as a group of permutations, from root data given by
GAP3+Chevie (thanks to Franco&#8217;s interface):</p>
<blockquote>
sage: W._gap_group
CoxeterGroup(&#8220;H&#8221;,4)
sage: (W._gap_group).parent()
Gap3</blockquote>
<p>with operations on permutations implemented in Sage:</p>
<div class="highlight-python">

{{{id=2|
W.an_element()^3
///
(1,5)(2,62)(3,7)(6,9)(8,12)(11,15)(13,17)(16,20)(18,22)(21,25)(26,29)(28,31)(30,33)(32,35)(34,37)(36,39)(38,41)(42,45)(46,48)(47,49)(50,52)(55,56)(57,58)(61,65)(63,67)(66,69)(68,72)(71,75)(73,77)(76,80)(78,82)(81,85)(86,89)(88,91)(90,93)(92,95)(94,97)(96,99)(98,101)(102,105)(106,108)(107,109)(110,112)(115,116)(117,118)
}}}

</div>
<p>and group operations implemented in GAP:</p>
<div class="highlight-python">

{{{id=3|
len(W.conjugacy_classes_representatives())
///
34
}}}

{{{id=4|
W.cardinality()
///
14400
}}}

</div>
<p>Now, assume we want to do intensive computations on this group,
requiring heavy access to the left and right Cayley graphs
(e.g. Bruhat interval calculations, representation theory, ...). Then
we can use Jean-Eric Pin&#8217;s Semigroupe, a software written in C:</p>
<div class="highlight-python">

{{{id=5|
S = semigroupe.AutomaticSemigroup(W.semigroup_generators(), W.one(), category = FiniteCoxeterGroups())
///
}}}

</div>
<p>The following triggers the full expansion of the group and its Cayley
graph in memory:</p>
<div class="highlight-python">

{{{id=6|
S.cardinality()
///
14400
}}}

</div>
<p>And we can now iterate through the elements, in length-lexicographic
order w.r.t. their reduced word:</p>
<div class="highlight-python">

{{{id=7|
sum( x^p.length() for p in S)
///
x^60 + 4*x^59 + 9*x^58 + 16*x^57 + 25*x^56 + 36*x^55 + 49*x^54 + 64*x^53 + 81*x^52 + 100*x^51 + 121*x^50 + 144*x^49 + 168*x^48 + 192*x^47 + 216*x^46 + 240*x^45 + 264*x^44 + 288*x^43 + 312*x^42 + 336*x^41 + 359*x^40 + 380*x^39 + 399*x^38 + 416*x^37 + 431*x^36 + 444*x^35 + 455*x^34 + 464*x^33 + 471*x^32 + 476*x^31 + 478*x^30 + 476*x^29 + 471*x^28 + 464*x^27 + 455*x^26 + 444*x^25 + 431*x^24 + 416*x^23 + 399*x^22 + 380*x^21 + 359*x^20 + 336*x^19 + 312*x^18 + 288*x^17 + 264*x^16 + 240*x^15 + 216*x^14 + 192*x^13 + 168*x^12 + 144*x^11 + 121*x^10 + 100*x^9 + 81*x^8 + 64*x^7 + 49*x^6 + 36*x^5 + 25*x^4 + 16*x^3 + 9*x^2 + 4*x + 1
}}}

{{{id=8|
S[0:10]
///
[[], [0], [1], [2], [3], [0, 1], [0, 2], [0, 3], [1, 0], [1, 2]]
}}}

{{{id=9|
S[-1]
///
[0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 2, 0, 1, 0, 2, 3, 2, 0, 1, 0, 1, 2, 0, 1, 0, 2, 3, 2, 0, 1, 0, 1, 2, 0, 1, 0, 2, 3, 2, 0, 1, 0, 1, 2, 0, 1, 0, 2, 3, 2, 0, 1, 0, 1, 2, 0, 1, 0, 2, 3]
}}}

</div>
<p>The elements of S are handles to C objects from <tt class="docutils literal"><span class="pre">Semigroupe</span></tt>:</p>
<div class="highlight-python">

{{{id=10|
x = S.an_element()
x
///
[0, 1, 2, 3]
}}}

</div>
<p>Products are calculated by <tt class="docutils literal"><span class="pre">Semigroupe</span></tt>:</p>
<div class="highlight-python">

{{{id=11|
x * x
///
[0, 1, 0, 2, 0, 1, 3, 2]
}}}

</div>
<p>Powering operations are handled by Sage:</p>
<div class="highlight-python">

{{{id=12|
x^3
///
[0, 1, 0, 2, 0, 1, 0, 2, 3, 2, 0, 1]
}}}

{{{id=13|
x^(10^10000)
///
}}}

</div>
<p>Altogether, S is a full fledged Sage Coxeter group, which passes all
the generic tests:</p>
<div class="highlight-python">

{{{id=14|
TestSuite(S).run(verbose = True, skip = &quot;_test_associativity&quot;)
///
}}}

</div>
<p>And of course it works for general semigroups too, and can further
compute much more information about those, like the (Knuth-Bendix
completion of the) relations between the generators:</p>
<div class="highlight-python">

{{{id=15|
S.print_relations()
///
aa = 1
bb = 1
cb = bc
cc = 1
da = ad
db = bd
dd = 1
cac = aca
dcd = cdc

dcababcabacdcababcabacdcababcabacdcababcabacdc = cdcababcabacdcababcabacdcababcabacdcababcabacd
}}}

</div>
<p>which contains the usual commutation + braid relations.</p>
<p>Let&#8217;s try now the 0-Hecke monoid:</p>
<div class="highlight-python">

{{{id=16|
from sage.combinat.j_trivial_monoids import *
S = semigroupe.AutomaticSemigroup(W.simple_projections(), W.one(), by_action = True)
S.cardinality()
///
48
}}}

{{{id=17|
S.print_relations()
///
aa = a
bb = b
ca = ac
cc = c
da = ad
db = bd
dd = d
cbc = bcb
dcd = cdc

ababacbabacbabcdcbabacbabcdcbabacbabcdcbabacbabcdcbabacbabcd = 0
}}}

</div>
<p>Let us throw in more mathematical information:</p>
<div class="highlight-python">

{{{id=18|
W = CoxeterGroup([&quot;A&quot;,3])
S = semigroupe.AutomaticSemigroup(W.simple_projections(), W.one(), by_action = True, category = FiniteJTrivialMonoids())
///
}}}

{{{id=19|
S.cardinality()
///
}}}

{{{id=20|
H = S.algebra(QQ)
H.orthogonal_idempotents()
///
}}}

</div>
<p>More about Jtrivial monoids:</p>
<div class="highlight-python">

{{{id=21|
from sage.combinat.j_trivial_monoids import *
def pij(j): return lambda i: i if i != j+1 else j
pi2 = pij(2)
///
}}}

</div>
<div class="highlight-python">

{{{id=22|
pi2(1), pi2(2), pi2(3), pi2(4)
///
(1, 2, 2, 4)
}}}

</div>
<div class="highlight-python">

{{{id=23|
class NDPFMonoid(AutomaticMonoid):
    def __init__(self, n):
        ambient_monoid = DiscreteFunctions(range(1,n+1), action=&quot;right&quot;)
        pi = Family(range(1, n), lambda j: ambient_monoid(pij(j)))
        AutomaticMonoid.__init__(self, pi, one = ambient_monoid.one(),
                                 category = (SubFiniteMonoidsOfFunctions(),
                                             FiniteJTrivialMonoids()))
Mon = NDPFMonoid(3)
Mon.cardinality()
///
5
}}}

</div>
<div class="highlight-python">

{{{id=24|
Mon.list()
///
[[], [1], [2], [1, 2], [2, 1]]
}}}

</div>
<div class="highlight-python">

{{{id=25|
[ NDPFMonoid(n).cardinality() for n in range(6)]
///
[1, 1, 2, 5, 14, 42]
}}}

</div>
<div class="highlight-python">

{{{id=26|
MuMon = mupad(Mon); MuMon
///
              / +-               -+ \
              | |  0, 1, 2, 3, 4  | |
              | |                 | |
              | |  1, 1, 4, 4, 4  | |
              | |                 | |
  Dom::MMonoid| |  2, 3, 2, 3, 4  | |
              | |                 | |
              | |  3, 3, 4, 4, 4  | |
              | |                 | |
              | |  4, 4, 4, 4, 4  | |
              \ +-               -+ /
}}}

{{{id=27|
MuMon.count()
///
   5
}}}

{{{id=28|
MuAlg = mupad.Dom.MonoidAlgebra(MuMon); MuAlg
///
}}}

{{{id=29|
MuCMat = MuAlg.cartanInvariantsMatrix(); MuCMat
///
  +-            -+
  |  1, 0, 0, 0  |
  |              |
  |  0, 1, 1, 0  |
  |              |
  |  0, 0, 1, 0  |
  |              |
  |  0, 0, 0, 1  |
  +-            -+
}}}

{{{id=30|
MuCMat.sage()
///
[1 0 0 0]
[0 1 1 0]
[0 0 1 0]
[0 0 0 1]
}}}

</div>
<div class="highlight-python">

{{{id=31|
M4 = NDPFMonoid(4)
var(&#39;q&#39;)
///
q
}}}

{{{id=32|
cartconj = M4.cartan_matrix(q); cartconj
///
[  1   0   0   0   0   0   0   0]
[  0   1   q q^2   0   0   0   0]
[  0   0   1   q   0   0   0   0]
[  0   0   0   1   0   0   0   0]
[  0   0   0   0   1   0   q   0]
[  0   0   0   0   q   1 q^2   0]
[  0   0   0   0   0   0   1   0]
[  0   0   0   0   0   0   0   1]
}}}

{{{id=33|
cart = M4.cartan_matrix_mupad(q); cart
///
[  1   0   0   0   0   0   0   0]
[  0   1   0   0   q   0   0   0]
[  0   q   1   0 q^2   0   0   0]
[  0   0   0   1   0 q^2   q   0]
[  0   0   0   0   1   0   0   0]
[  0   0   0   0   0   1   0   0]
[  0   0   0   0   0   q   1   0]
[  0   0   0   0   0   0   0   1]
}}}

{{{id=34|
def is_isomorphic_matrices(m1, m2):
    coeffs1 = set([ c for row in m1 for c in row ])
    coeffs2 = set([ c for row in m2 for c in row ])
    if coeffs1 != coeffs2:
        return False
    f = sage.combinat.ranker.rank_from_list(sorted(coeffs1))
    def graph(m):
        m = matrix([[f(m[i,j]) for j in range(m.ncols()) ] for i in range(m.nrows())])
        return DiGraph(m, multiple_edges = True)
    return graph(m1).is_isomorphic(graph(m2))
///
}}}

{{{id=35|
is_isomorphic_matrices(cart, cartconj)
///
True
}}}

{{{id=36|
P4 = Posets(4); P4
///
Posets containing 4 vertices
}}}

{{{id=37|
P4.cardinality()
///
16
}}}

{{{id=38|
Pos = P4[9]; Pos.cover_relations()
///
[[0, 2], [1, 2], [2, 3]]
}}}

{{{id=39|
#Pos.plot()
///
}}}

{{{id=40|
MP = NDPFMonoidPoset(Pos); MP
///
NDPF monoid of Poset ([[0, 2], [1, 2], [2, 3]])
}}}

{{{id=41|
is_isomorphic_matrices(MP.cartan_matrix(q), MP.cartan_matrix_mupad(q))
///
True
}}}

{{{id=42|
@parallel()
def check_conj_parallel(Pos):
    MP = NDPFMonoidPoset(Pos)
    return is_isomorphic_matrices(MP.cartan_matrix(q),
                                  MP.cartan_matrix_mupad(q))
///
}}}

{{{id=43|
for (((poset,), _), res) in check_conj_parallel(Posets(3).list()): print poset.cover_relations(), res
///
}}}

{{{id=44|
all(x[1] for x in check_conj_parallel(Posets(4).list()))
///
True
}}}

</div>
<p>We finish with some character ring calculations:</p>
<div class="highlight-python">

{{{id=45|
attach /home/nthiery/work/frg/Articles/Hivert_Schilling_Thiery_HeckeMonoid/main.sage
M = BiHeckeMonoid([&quot;A&quot;,3])
G = M.character_ring()
E = G.E(); T = G.T(); P = G.P()
///
}}}

{{{id=46|
M0 = M.fix_w0_monoid()
G0 = M0.character_ring()
S0 = G0.S(); P0 = G0.P()
///
}}}

{{{id=47|
for e in P0.basis():
    print &quot;Ind(&quot;,e, &quot;)=&quot;, P(G.induce_from_M0(S0(e))) # indirect doctest
///
Ind( P[1234] )= P[1234]
Ind( P[2134] )= P[2134] + P[2314] + P[2341] + P[2413] + P[4213]
Ind( P[2314] )= P[2314] + P[2341]
Ind( P[3214] )= P[3214] + P[3241] + P[3421]
Ind( P[2341] )= P[2341]
Ind( P[3241] )= P[3241] + P[3421]
Ind( P[3421] )= P[3421]
Ind( P[4321] )= P[4321]
Ind( P[2431] )= P[2431] + P[4231]
Ind( P[4231] )= P[4231]
Ind( P[1324] )= P[1324] + P[1342] + P[3124] + P[3142] + P[3241] + P[3412] + P[4132]
Ind( P[3124] )= P[3124] + P[3142] + P[3241] + P[3412]
Ind( P[1342] )= P[1342] + P[3142] + P[3412] + P[4132]
Ind( P[3142] )= P[3142] + P[3412]
Ind( P[3412] )= P[3412]
Ind( P[4312] )= P[4312]
Ind( P[1432] )= P[1432] + P[4132] + P[4312]
Ind( P[4132] )= P[4132] + P[4312]
Ind( P[1243] )= P[1243] + P[1423] + P[2413] + P[2431] + P[4123]
Ind( P[2143] )= P[2143] + P[2413] + P[2431] + P[4213] + P[4231]
Ind( P[2413] )= P[2413] + P[2431] + P[4213] + P[4231]
Ind( P[4213] )= P[4213] + P[4231]
Ind( P[1423] )= P[1423] + P[4123]
Ind( P[4123] )= P[4123]
}}}

</div>
<p>Behind the scene, it uses the cutting poset (to convert between
translation modules to simple modules), the character formula for
projective modules of J-Trivial monoids, the property that simple
modules for M0 are induced to translation modules for M, etc. Plus
inversion by matrix of linear morphism between finite dimensional
vector spaces. It also uses the expansion of the character of a
projective module for the BiHecke monoid in term of simple module, but
this one is hard-coded for type A3 (currently too expensive to
recalculate it). The framework supports q-characters; but few of the
rules above are implemented for them, since we do not know them yet</p>
</div>
</div>


          </div>
        </div>
      </div>
      <div class="sphinxsidebar">
        <div class="sphinxsidebarwrapper">
            <h3><a href="index.html">Table Of Contents</a></h3>
            <ul>
<li><a class="reference external" href="">Sage Days 20.5 demonstration</a><ul>
<li><a class="reference external" href="#a-demonstration-of-sage-gap4-gap3-chevie-semigroupe">A demonstration of Sage + GAP4 + GAP3 + Chevie + Semigroupe</a></li>
</ul>
</li>
</ul>

            <h4>Previous topic</h4>
            <p class="topless"><a href="2010-03-29-SLC64.html" title="previous chapter">SLC 64 demonstration</a></p>
            <h4>Next topic</h4>
            <p class="topless"><a href="object_class_talk.html" title="next chapter">Objects and Classes in Python and Sage</a></p>
            <h3>This Page</h3>
            <ul class="this-page-menu">
              <li><a href="_sources/2010-05-06-SageDays20.5.txt" rel="nofollow">Show Source</a></li>
            </ul>
          <div id="searchbox" style="display: none">
            <h3>Quick search</h3>
              <p class="searchtip" style="font-size: 90%">
              Enter search terms or a module, class or function name.
              </p>
          </div>
          <script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="genindex.html" title="General Index">index</a></li>
        <li class="right">
          <a href="object_class_talk.html" title="Objects and Classes in Python and Sage">next</a> |</li>
        <li class="right">
          <a href="2010-03-29-SLC64.html" title="SLC 64 demonstration">previous</a> |</li>
  
    
      <a href="../index.html"><img src="_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
    
  
  
        <li><a href="index.html">Misc talks, demos, tutorials, ... using Sage v4.3.4</a> &raquo;</li>
 
      </ul>
    </div>
    
    <div class="footer">
      &copy; Copyright Thiery et al.
      Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 0.6.3.
    </div>
    <script type="text/javascript">
/*global jQuery, window */
/* Sphinx sidebar toggle.  Putting this code at the end of the body
 * enables the toggle for the live, static, and offline docs.  Note:
 * sage.misc.html.math_parse() eats jQuery's dollar-sign shortcut. */
var jq = jQuery;  
jq(document).ready(function () {
    var bar, bod, bg, fg, key, tog, wid_old, wid_new, resize, get_state, set_state;
    bod = jq('div.bodywrapper');
    bar = jq('div.sphinxsidebar');
    tog = jq('<div class="sphinxsidebartoggle"></div>');
    
    /* Delayed resize helper.  Not perfect but good enough. */
    resize = function () {
        setTimeout(function () {
            tog.height(bod.height());
        }, 100);
    };
    jq(window).resize(function () {
        resize();
    });
    
    /* Setup and add the toggle. See Sphinx v0.5.1 default.css. */
    fg = jq('div.sphinxsidebar p a').css('color') || 'rgb(152, 219, 204)';
    bg = jq('div.document').css('background-color') || 'rgb(28, 78, 99)';
    wid_old = '230px';
    wid_new = '5px';
    tog.css('background-color', bg)
        .css('border-width', '0px')
        .css('border-right', wid_new + ' ridge ' + bg)
        .css('cursor', 'pointer')
        .css('position', 'absolute')
        .css('left', '-' + wid_new)
        .css('top', '0px')
        .css('width', wid_new);
    bod.css('position', 'relative');
    bod.prepend(tog);
    resize();
    
    /* Cookie helpers. */
    key = 'sphinxsidebar=';
    set_state = function (s) {
        var date = new Date();
        /* Expiry in 7 days. */
        date.setTime(date.getTime() + (7 * 24 * 3600 * 1000));
        document.cookie = key + encodeURIComponent(s) + '; expires=' +
            date.toUTCString() + '; path=/';
    };
    get_state = function () {
        var i, c, crumbs = document.cookie.split(';');
        for (i = 0; i < crumbs.length; i += 1) {
            c = crumbs[i].replace(/^\s+/, '');
            if (c.indexOf(key) === 0) {
                return decodeURIComponent(c.substring(key.length, c.length));
            }
        }
        return null;
    };
    
    /* Event handlers. */
    tog.mouseover(function (ev) {
        tog.css('border-right-color', fg);
    }).mouseout(function (ev) {
        tog.css('border-right-color', bg);
    }).click(function (ev) {
        if (bod.hasClass('wide')) {
            bod.removeClass('wide');
            bod.css('margin-left', wid_old);
            bar.css('width', wid_old);
            bar.show();
            set_state('visible');
        } else {
            set_state('hidden');
            bar.hide();
            bar.css('width', '0px');
            bod.css('margin-left', wid_new);
            bod.addClass('wide');
        }
        resize();
    });
    
    /* Hide the normally visible sidebar? */
    if (get_state() === 'hidden') {
        tog.trigger('click');
    } else {
        set_state('visible');
    }
});
    </script>