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

[saliola]

comment:1

[Answered my own question.]

[tscrim]

comment:2

Here's what I currently have. The multiplication in the dual basis isn't working correctly yet. I know there's the hopf_algebra_of_supercharacters-fs.patch patch in the queue which seems like its targeted more for base rings of ZZ[q] (or like Hall-Littlewoods are to Sym), and I was hoping to link them together at some point (please correct me if I'm wrong). I'd be happy to work with you on this patch.

[saliola]

comment:3

The only problem is that I don't have much time these days to work on this. I've been meaning to implement NCSym. I'll try to take a look at what you have and see what I can offer, if anything.

As usual, thank you for your work, Travis!

[darijgr]

comment:4

Travis, what sources are you using for this? I'm asking because I haven't read anything about NCSym so far. I have a vague impression it has been introduced in one of Rota's Foundations papers, but not one that I have. A good introduction would simplify my job reviewing this by a lot.

[tscrim]

comment:5

Here's one of the references (Bergeron, Zabrocki): http://arxiv.org/pdf/math/0509265.pdf. I forget the other references off-hand (it's on my other computer tho), and I'll be adding all of the references to the doc as I finish it up.

[tscrim]

comment:6

Also I just fixed the w basis multiplication.

[tscrim]

comment:7

Okay, the patch is now ready for first review. It has full doctest coverage and all tests pass for me. I've removed some of the coercions in the old version since I was worried about possibly breaking coercion commutative diagrams.

Some of the things I'm not perfectly happy about (but can live with currently):

• A descriptive name of the q, x, and w bases.
• No antipode for the w basis.
• Creating the SymmetricFunctions base object when creating SymmetricFunctionNonCommutingVariables in order to set up the coercion.
• Is it safe to put the natural maps Sym -> NCSym and NSym -> NCSym as coercions?

The references I used are included in the documentation now too.

[zabrocki]

comment:8

Hi Travis, One initial comment about the NSym -> NCSym map. It is dangerous to call it "the natural" map from NSym to NCSym. It is one of many. There does not seem to be a reason to favor the map which sends the complete generators to the complete generators. If you were to send the elementary generators to the elementary generators you get a map which is equally compelling and (unfortunately) they are not the same map.

[tscrim]

comment:9

New version rebased over changes in #15143 and removes the word "natural" and instead states that it is the map which fixes Sym.

[zabrocki]

comment:10

Hi Travis,

What patches and version do you have applied? I get fuzz on the file sage/combinat/ncsf_qsym/ncsf.py and doc tests failing in ncsym.py (seemingly) because the output displays in a different order. We may need to put a dependency with other patches that touch ncsf.py. I am currently running on sage-5.12.beta5 and only #15143 applied.

[tscrim]

comment:11

Hey Mike,

I have 5.12.beta3 in the combinat queue, but the fuzz is likely due to #15164 (which I'm planning to review soon). What type of fuzz do you get? If it's 0 or 1, we don't need to put it down as a dependency.

I'll build 5.12.beta5 today and see if I also get doctest failing.

Best,

Travis

[zabrocki]

comment:12

You are right that the fuzz is disappears by applying #15164

I get 4 doctest failures on ncsym.py. They are minor, but I don't know why I see them and you don't (so it doesn't seem like a good idea to change them). They are on lines 248, 438, 633, 737 and for instance one is

File "sage/combinat/ncsym/ncsym.py", line 633, in sage.combinat.ncsym.ncsym.SymmetricFunctionsNonCommutingVariables.elementary.Element.omega
Failed example:
    elt = e[[1,3],[2]].omega(); elt
Expected:
    -e{{1, 3}, {2}} + 2*e{{1}, {2}, {3}}
Got:
    2*e{{1}, {2}, {3}} - e{{1, 3}, {2}}

[tscrim]

comment:13

I would have thought that the total ordering on set partitions in #15143 would have CombinatorialFreeModule give a unique sorting on the elements:

sage: SetPartition([[1,3],[2]]) < SetPartition([[1],[2],[3]])
False
sage: SetPartition([[1,3],[2]]) > SetPartition([[1],[2],[3]])
True
sage: SetPartition([[1],[2],[3]]) < SetPartition([[1,3],[2]])
True
sage: SetPartition([[1],[2],[3]]) > SetPartition([[1,3],[2]])
False

My guess as to why we're getting different output is a failure in the comparisons (I didn't see any tickets that seemed like would change the output of linear_comb()). Try running:

sage: e = SymmetricFunctionsNonCommutingVariables(QQ).e()
sage: e.print_options()
{'bracket': False,
 'latex_bracket': False,
 'latex_prefix': None,
 'latex_scalar_mult': None,
 'monomial_cmp': <function cmp>,
 'prefix': 'e',
 'scalar_mult': '*',
 'tensor_symbol': None}
sage: cmp(SetPartition([[1],[2],[3]]), SetPartition([[1,3],[2]]))
-1
sage: elt = 2*e[[1],[2],[3]] - e[[1,3],[2]]
sage: L = elt._monomial_coefficients.items()
sage: L.sort(cmp=cmp, key=lambda (x,y): x)
sage: L
[({{1, 3}, {2}}, -1), ({{1}, {2}, {3}}, 2)]

Do you get anything different, in particular the last one?

[zabrocki]

comment:14

I do get something different, but all of the comparisons are the same. For the last one I get:
[({{1}, {2}, {3}}, 2), ({{1, 3}, {2}}, -1)]

Any idea why?

[tscrim]

comment:15

This is why:

sage: A = SetPartition([[1],[2],[3]])
sage: B = SetPartition([[1,3],[2]])
sage: cmp(A, B)
-1
sage: cmp(B, A)
-1

The cmp is not correctly using the rich comparisons because ClonableArray has (in effect) a __cmp__ function which calls the underlying list (which contains Set objects which don't compare as intended)...

I'm fixing this right now.

[tscrim]

comment:16

Okay, now it should be consistent.

sage: A = SetPartition([[1],[2],[3]])
sage: B = SetPartition([[1,3],[2]])
sage: cmp(A, B)
-1
sage: cmp(B, A)
1

I added a __cmp__() method to SetPartition to override the behavior of ClonableArray.

[zabrocki]

comment:17

Attachment: trac_15150_product_on_basis_q-mz.patch.gz

OK. Thanks for fixing that. I'm looking over the patch and I have some initial changes where the multiplication uses the pipe function and the product is implemented in the q basis.

The change of basis from q to x or vice versa is slow and so ideally I would like to improve this.

I think that line 180 from ncsym.py is wrong. There should be no morphism from NCSym to Sym, but there is a projection. There is however a morphism from DNCSym to Sym.

DNCSym is similar to quasi-symmetric functions so that if you add the right elements together (say some linear combination of the w basis) then you have an element of Sym.

[zabrocki]

comment:18

Another thing that was bothering me was that x[[1,2],[3]] is ok, but x([[1,2],[3]]) is not. Both should be ok. I think that this should be an easy fix.

[darijgr]

comment:19

Some random comments on ncsym.py.

    The ring of symmetric functions in non-commutative variables,
    which is not to be confused with the :class:`non-commutative symmetric
    functions<NonCommutativeSymmetricFunctions>`, are polynomials in `n`
    non-commuting variables `{\bf k}[x_1, x_2, \ldots, x_n]` where the
    dimension of the subspace of elements of degree `k` is equal to
    the number of compositions of `k` (with less than `n` parts).

If the variables are non-commuting, use angular rather than square brackets. Also, I assume you want infinitely many variables? And do you really want compositions?

Typo:

Grothendeick

Old-style arXiv references like this:

:arxiv:`0208168`

should have a "math/" in front of them, I believe (also, I'd add a version number, in this case math/0208168v2).

What is the \wedge operation on set partitions? It is used but not defined. If it's the one from the Bergeron-Zabrocki paper, it is simply the meet of set partitions (aka __mul__) and should be explained as such.

On the right hand side of

                S(\mathbf{p}_A) = \sum_{\gamma} (-1)^{\ell(\gamma)} \gamma[A]

don't you mean to say p_{\gamma[A]} rather than \gamma[A] ? And on the next line, do you mean to say of `[\ell(A)]` instead of of length `\ell(A)`?

Similarly here:

                p(A) = \sum_{\gamma} (-1)^{\ell(\gamma)-1} \gamma[A]

I assume that "strictly coarser" in

        where we sum over all strictly coarser set partitions `B`.

refers to the relation of strict coarsening as defined in set_partition.py. If so, please say this explicitly, as the notation is slightly counterintuitive (one normally thinks "strictly coarser" means "coarser and not equal").

I'll eventually have a closer look at the patch if only to understand how exactly internal-coproduct-by-coercion works (for use in NSym); I cannot promise that I will ever give this an actual review. Nevertheless, great work here, Travis.

[tscrim]

comment:20

Here's the new version of the patch which (hopefully) takes care of all of Darij's comments. How the internal_coproduct* works is a trick with lazy_attribute which *_by_coercion() creates the correct morphism object if *_on_basis() is not implemented and so it behaves like a method.

I've removed the coercion from NCSym to Sym since it is not a Hopf morphism, which is a requirement for it to be a coercion. I've fixed the input to accept x([[1,3],[2]]) as well.

Currently to get from x to q (or vice versa) there's a few coercions going on, and I don't know of a way to go between them directly. (Data suggests that x(q[A]) is a sum over some subset of set partitions with all coefficients occurring (-1)^nest(A).)

For DNCSym, is there a way to express an element in the w basis as a polynomial? Currently I have a map from Sym to DNCSym which is at least (appears to me to be) an algebra morphism (see the sum_of_partitions() method). Is this a Hopf morphism and is the map from DNCSym to Sym the inverse of this map?

Thank you all for looking at this patch,

Travis

Edit - let's see if the patchbot catches it in an edited message:

For patchbot:

Apply: trac_15150-ncsym-ts.patch​

[zabrocki]

comment:21

Hi Travis,
Is it possible that this is the same patch as before?

[tscrim]

comment:22

I think I uploaded the patch from my beta3 install instead of my beta5. Sorry about that. Here's the new one.

For patchbot:

Apply: trac_15150-ncsym-ts.patch​

[zabrocki]

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?

[zabrocki]

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.

[zabrocki]

comment:79

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

[zabrocki]

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.

[zabrocki]

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.

[zabrocki]

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!

[zabrocki]

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

[zabrocki]

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