Implement NCSym

[tscrim]

Implement the Hopf algebra of symmetric functions in non-commuting variables in the following bases:

• monomial m
• elementary e
• homogeneous h
• power-sum p
• x
• q

as well as the dual basis w.

Apply: attachment: trac_15150-ncsym-ts.patch​

Depends on #15143 Depends on #15164

CC: @sagetrac-sage-combinat @zabrocki @saliola @darijgr

Component: combinatorics

Author: Travis Scrimshaw

Reviewer: Mike Zabrocki, Darij Grinberg

Merged: sage-5.13.rc0

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

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:48

Here are some doc changes, but a lot of methods need OUTPUT as well as INPUT. Remember how I said "I don't think I will suggest other functionality..."? I was wrong. One thing that I realized that was missing was a duality_pairing function. I have a patch to add this, but I need to add documentation yet. I'll try to do this shortly.

[tscrim]

comment:49

Attachment: trac_15150-duality_pairing-mz.patch.gz

New version with both of Mike's patches folded in and functions documented, along with refactoring the categories to a common super category to not duplicate code.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:50

Hi Travis, I was looking at the method from_symmetric_function and I want to make sure that I understand. It is just a linear map of one vector space to another, right? It does not preserve the product or the coproduct structure if I understand it.

[tscrim]

comment:51

Hey Mike.

Yes. It is more about it being a section of the natural projection and working with the map with NSym.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:52

Here is one that I can see needs to be fixed.

sage: Sp = SymmetricFunctions(QQ).p()
sage: Np = SymmetricFunctionsNonCommutingVariables(QQ).p()
sage: Nh = SymmetricFunctionsNonCommutingVariables(QQ).h()
sage: Sp(Nh(Np([[1,4],[2,3]])).to_symmetric_function())
45/2*p[1, 1, 1, 1] - p[2, 1, 1] + 1/2*p[2, 2]
sage: Np([[1,4],[2,3]]).to_symmetric_function()
p[2, 2]
sage: Ne = SymmetricFunctionsNonCommutingVariables(QQ).e()
sage: Sp(Ne(Np([[1,4],[2,3]])).to_symmetric_function())
45/2*p[1, 1, 1, 1] + p[2, 1, 1] + 1/2*p[2, 2]

With m, q, x the coercion is consistent.

I am fairly sure the problem is with the projection to_symmetric_function in the h and the e bases.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:53

more doc changes

[tscrim]

comment:54

Hey Mike,

I've folded in your latest review patch, fixed the projection in the h and e bases (I wasn't scaling by the correct constant), and added some exposition to the NCSym class.

For patchbot:

Apply: trac_15150-ncsym-ts.patch

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

Changed dependencies from #15143 to #15143, #15164

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:56

Sorry I had to put this aside for a while. I factored out product_on_basis and moved it to bases.py since the product is the same for all bases except the monomial basis. Added a few more doc changes. I think that there is more to do, but we are getting close.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:57

This version includes changes to dual.py. I deleted the function _set_par_to_par because it didn't make sense and the documentation was wrong and it could be replaced with lambda A: A.shape().

[darijgr]

comment:58

Hmm. Am I seeing it right that you defined the product to be piping on every basis unless overshadowed explicitly? A bit of an trap if you ask me.

Also:

    392                 The expansion of an element of the `\mathbf{w}` basis is 
    393                 given by equations (26) and (55) in [HNT06]_. 

The formula numbers refer to a version of the paper other than the one referenced (arXiv; by the way, please add a version number).

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:59

I created a category of multiplicative bases and put the product_on_basis there. In theory, calculations can be sped up by applying homomorphisms to irreducible components of basis elements.

[darijgr]

comment:60

But it's in class NCSymBases(Category_realization_of_parent), not in some hypothetical class MultiplicativeNCSymBases(NCSymBases) right? Oooh, I see, this nevertheless means the multiplicative bases only, while all the others go through the NCSymBasis_abstract class. But IMHO this is confusing, and could be clarified at least in the class docstrings if not in the names of the classes...

[tscrim]

comment:61

The method _set_par_to_par is needed because does a little bit more than just return the shape and is needed for the [inverse] coercion. The method _set_par_to_par() in effect takes a subset of set partitions which are in bijection with partitions and corresponds to leading terms in the coercion.

With Mike's patch we have:

sage: w = SymmetricFunctionsNonCommutingVariablesDual(QQ).w()
sage: h = SymmetricFunctions(QQ).h()
sage: h(w[[1,3],[2]])
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-3-5d0ec5476c79> in <module>()
----> 1 h(w[[Integer(1),Integer(3)],[Integer(2)]])

/home/travis/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:8372)()

/home/travis/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/categories/morphism.so in sage.categories.morphism.SetMorphism._call_ (sage/categories/morphism.c:4837)()

/home/travis/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/categories/modules_with_basis.pyc in preimage(self, f)
   1715                     raise ValueError, "%s is not in the image of %s"%(f, self)
   1716             s = map(j_preimage)
-> 1717             assert j == self._dominant_item(s)[0]
   1718 
   1719             if not self._unitriangular:

AssertionError:

While it shouldn't work, it is giving the wrong error.

I've folded in your latest patch Mike, but reinstated _set_par_to_par with some documentation changes and some doctests. Hopefully it is more clear what it does, but perhaps the method could be renamed.

But it's in class NCSymBases(Category_realization_of_parent), not in some hypothetical class MultiplicativeNCSymBases(NCSymBases) right? Oooh, I see, this nevertheless means the multiplicative bases only, while all the others go through the NCSymBasis_abstract class. But IMHO this is confusing, and could be clarified at least in the class docstrings if not in the names of the classes...

Not quite. We need the NCSymBasis_abstract class to overwrite the _element_constructor_ from Parent. This is not a category object, and all bases inherit from this (as classes). The different categories are used as a slightly different type of abstraction, which includes (in a sense) a mathematical organization.

I've also made the w basis inherit from NCSymBasis_abstract.

For patchbot:

Apply: trac_15150-ncsym-ts.patch

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:62

Hmm. I still don't get _set_par_to_par. Where does the \lambda_i \leq \lambda_{i+1} come in?

sage: w = SymmetricFunctionsNonCommutingVariables(QQ).dual().w()
sage: h = SymmetricFunctions(QQ).h() 
sage: w._set_par_to_par(SetPartition([[1],[2],[3,4,5]]))
[3, 1, 1]
sage: w._set_par_to_par(SetPartition([[1,2,3],[4],[5]]))
[3, 1, 1]
sage: w._set_par_to_par(SetPartition([[1],[2,3,4],[5]]))
[3, 1, 1]
sage: w._set_par_to_par(SetPartition([[1],[2,3,5],[4]]))
sage: h(w[[1,2],[3]])
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
...
AssertionError: 
sage: h(w[[1],[2,3]])
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
...
AssertionError: 
sage: h(w[[1,3],[2]])
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
...
ValueError: w{{1, 3}, {2}} is not in the image of Generic morphism:
  From: Symmetric Functions over Rational Field in the homogeneous basis
  To:   Dual symmetric functions in non-commuting variables over the Rational Field in the w basis
sage: 

Why is the last one a ValueError and the others are assertion errors?

[tscrim]

comment:63

There's two problems, the first is the morphism should be the other triangular and the second is the _set_par_to_par() is not restrictive enough. I'll be fixing this now.

[tscrim]

comment:64

Okay, fixed. They all return ValueErrors now and I'm now using the ordering on lambda_i in the method.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:65

There seems to be a problem with coercion for bases other than than h.

sage: w = SymmetricFunctionsNonCommutingVariablesDual(QQ).w()
sage: e = SymmetricFunctions(QQ).e()
sage: e(w(e[2,1]))
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-4-66ec535e7d35> in <module>()
----> 1 e(w(e[Integer(2),Integer(1)]))

/Applications/sage/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:8372)()

/Applications/sage/local/lib/python2.7/site-packages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3856)()

/Applications/sage/local/lib/python2.7/site-packages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3757)()

/Applications/sage/local/lib/python2.7/site-packages/sage/combinat/sf/classical.pyc in _element_constructor_(self, x)
    327                 return eclass(self, {sage.combinat.partition.Partition([]):R(x)})
    328             except StandardError:
--> 329                 raise TypeError, "do not know how to make x (= %s) an element of self"%(x)
    330 
    331     # This subclass is currently needed for the test above:

TypeError: do not know how to make x (= 6*w{{1}, {2}, {3}} - w{{1}, {2, 3}} - w{{1, 2}, {3}} - w{{1, 3}, {2}}) an element of self
sage: h = SymmetricFunctions(QQ).h()
sage: e(h(w(e[2,1])))
e[2, 1]

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:66

A few minor changes in whitespace and pyflakes warnings.

[darijgr]

comment:67

Mike, you're trying to coerce from a basis of dual NCSym to a basis of Sym? Should that really be a coercion? That would give a noncommutative coercion graph...

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:68

To my eye, the problem is the doc tests. I see examples of coercion through the h basis rather than the use of the to_symmetric_function method. Reading those doc-tests I suspected that the h basis is not the only portal and I was wrong.

sage: w = SymmetricFunctionsNonCommutingVariablesDual(QQ).w()
sage: e = SymmetricFunctions(QQ).e()
sage: w(e[2,1]).to_symmetric_function()
h[1, 1, 1] - h[2, 1]

[darijgr]

comment:69

OK, this thing is implemented as a conversion (rightly -- it can't be a coercion), whence there is no automatic path discovery. But the docstring is claiming it's a coercion, and could be more explicit about it only leading to h.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:70

I'm not sure if I should be too concerned because the doc tests are in a hidden function and they are there to test if that coercion doesn't work, not to demonstrate how to coerce between NCSym and Sym. I tried to make it slightly* clearer by changing the doc test.

I also changed the following because I don't think it is right:

    There is also a natural projection to the usual symmetric functions by
    letting the variables commute. This projection does *not* preserve the
    product nor coproduct stucture, but instead is just a module morphism.

I think the slice defined in from_symmetric_function does not preserve the Hopf structure, but the projection preserves both product and coproduct.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:71

I added a few doc tests that hopefully clarifies the purpose of from_symmetric_function.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:72

I believe that there is missing documentation due to #9107 (e.g. any methods in monomial.Element). This version includes some minor doc changes.

[tscrim]

comment:73

Replying to @zabrocki:

I think the slice defined in from_symmetric_function does not preserve the Hopf structure, but the projection preserves both product and coproduct.

If it doesn't preserve the Hopf structure, we can't have it be a coercion (including the w basis to the homogeneous sym funcs). Instead we have to make them all conversions. I'll also add in the natural conversions (ex. the p basis to the powersum sym funcs) on the next update.

Best,

Travis

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:74

from_symmetric_function is already not a coercion. It is just a method. Are you saying that you don't want to make the map from Sym -> NCSym^* a coercion? It preserves the Hopf structure.

For NSym/QSym I believe we have the following:

• NSym -> Sym is a method to_symmetric_function
• Sym -> QSym is a coercion and can be accessed by B( sfelement ) where B is a basis of QSym
• QSym -> Sym under the condition that the element in QSym is_symmetric by qsymelement.to_symmetric_function() or (and this is not preferred) m( qsymelement )

All of these maps preserve the Hopf algebra structure. Similarly for NCSym/NCSym^* we have

• NCSym -> Sym is a method to_symmetric_function
• Sym -> NCSym^* is a coercion and can be accessed by w( sfelement )
• NCSym -> Sym under the condition that the element in NCSym is_symmetric by ncsymdelement.to_symmetric_function() or (and this is not preferred) h( ncsymdelement )

The maps NCSym -> Sym and NSym -> Sym are not coercions since these maps are projections and hence not invertible. The inclusions of Sym -> NCSym^* and Sym -> QSym have an inverse (one sided) and so I think that they can be coercions. I am not too concerned that p( ncsymdelement ) doesn't work. The reason the portal through the h basis works is because of the connection with the w basis.

[tscrim]

comment:75

Ah, sorry, I confused myself.

However I coercions do not have to be invertible (ex. ZZ -> QQ), just are well-defined, preserve the structure, and make commutative diagrams. I think they typically are injections, but this is not a requirement.

The QSym -> Sym can't be a coercion because it is not well-defined (on all elements). Since NCSym -> Sym and NSym -> Sym preserve the Hopf structure and are well-defined. I don't think there's any danger of breaking coercion commutativity. So I think we should make these coercions. Your thoughts?

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:76

I am not comfortable making NCSym and NSym -> Sym coercions because when I say that they preserve the Hopf structure I mean that the Hopf structure of NCSym is mapped onto the Hopf structure of Sym but NCSym does not exist as a Hopf subalgebra of Sym. For Sym -> QSym it is the case that Sym exists as a subalgebra of QSym.

That is, let phi : NCSym -> Sym then sometimes we have, F != G but phi(F) = phi(G) (e.g. F = AB, G =BA)

That is, "equalities go to equalities, but sometimes inequalities also go to equalities." (to my eye, not something I want as a coercion). This isn't a hard fast rule, but it seems counter-intuitive to be able to coerce from NCSym to Sym rather than use the method to_symmetric_function to project onto that space.

For psi: Sym -> NCSym^* we have psi(F)=psi(G) iff F=G, that is, "equalities going to equalities and inequalities going to inequalities"

[tscrim]

comment:77

Since it's consistent with NSym, I'm fine with NCSym -> Sym not being a coercion. So what else needs to be done?

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:78

I want to be completely convinced everything works properly and haven't missed any details in the documentation. Give me another day or two to find minor tweaks. Otherwise I am extremely happy with it. Nantel asked just today to use it to compute m_A(x_0,x_1,...,x_n) and I sent him installation instructions.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:79

current version moves counit_on_basis to NCSymOrNCSymDualBases parent methods and implements antipode_on_basis in the w parent methods

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:80

Can you check if antipode_on_basis should be a cached method? I didn't do that, but it computes the antipode using the definition and it is a rather recursive formula.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:81

Attachment: trac_15150-docchanges-mz.patch.gz

My tests on the antipode seems to run pretty fast without caching, but please take a look. I just added a new version with some minor doc corrections.

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:82

All tests pass, and documentation looks good. please look over my last version of the patch, fold it with yours, make any last changes, and you have my blessing on a positive review. Nice work!

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:83

A couple of things left to change in the version you posted. Search on SEEALSO because it seems to be duplicated in three places. Also I think that occurrences of \kappa \circ \chi should be \chi \circ \kappa.

[tscrim]

comment:84

Good catch; merge issue. Fixed and same with the map composition order.

Since #10963 is finished (yay), I've added it as a dependency since it seems to affect the output of one of the doctests in bases.py. Mike, could you double-check to make sure the tests still pass for you? Thanks. And thanks Darij for fixing up the docstrings along the way.

Best,

Travis

For patchbot:

Apply: trac_15150-ncsym-ts.patch

[tscrim]

Reviewer: Mike Zabrocki, Darij Grinberg

[tscrim]

Changed dependencies from #15143, #15164 to #15143, #15164, #10963

[tscrim]

comment:85

Okay, now everything should be squared away wrt the dep on #10963.

For patchbot:

Apply: trac_15150-ncsym-ts.patch

[d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db]

comment:86

I used sage cloud and git to test this patch. All tests pass (even with #10963 applied). I think that we can be confident that once it has a positive review, that this will pass as well.

[darijgr]

comment:88

yay milestone tug of war!

Is there an easy way to commute this past #10963 or will that make code slower/buggier/whatever?

[tscrim]

Attachment: trac_15150-ncsym-ts.patch.gz

with fixes

[tscrim]

Changed dependencies from #15143, #15164, #10963 to #15143, #15164

[tscrim]

comment:89

Since #10963 is getting pushed back, I've changed the one doctest output to move this past.

For patchbot:

Apply: trac_15150-ncsym-ts.patch​

[jdemeyer]

comment:90

I cannot promise this will be merged in Sage 5.13 though. Did you test this well, that will increase the chances?

[tscrim]

comment:91

All tests on the file passed for me on 5.13.beta2, and once 5.13.beta5 is done compiling, I'll check on that as well.

[tscrim]

comment:92

Works for me on 5.13.beta5:

sage -t --long bases.py
    [148 tests, 14.09 s]
sage -t --long dual.py
    [74 tests, 6.73 s]
sage -t --long ncsym.py
    [197 tests, 26.14 s]
sage -t --long set_partition.py
    [266 tests, 45.62 s]
sage -t --long ncsf.py
    [381 tests, 15.40 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------

And the pdf documentation builds cleanly:

Transcript written on combinat.log.
Build finished.  The built documents can be found in /home/travis/sage-5.13.beta5/devel/sage/doc/output/pdf/en/reference/combinat

[jdemeyer]

Merged: sage-5.13.rc0