Implement the multiplicative bases of WQSym

[amypang]

Please implement the S and E bases from Novelli-Thibon (​https://arxiv.org/abs/math/0605061 section 2.6 and line 47). They are sums of monomials over the pseudo-permutohedron order:

Let p be an ordered set partition.

A pair i<j is a full inversion in p if the block containing i is strictly to the right of the block containing j.

A pair i<j is a half inversion in p if i and j are in the same block.

Two ordered set partitions satisfy u<=v if every full inversion in u is a full inversion in v, and every half inversion in u is a half or full inversion in v.

Then S_u = sum of M_v over v<=u; E_u = sum of M_v over v>=u.

CC: @darijgr @tscrim @saliola @zabrocki @alauve

Component: combinatorics

Keywords: IMA coding sprint, CHAs

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

[amypang]

comment:1

I'm moving the fundamental basis to #25151 since it uses the same order as the Q-basis.

[amypang]

comment:2

Judging from the FQSym monomial-basis code, we first need a function pseudopermutahedron_lequal, that returns whether u<=v. Then we should be able to analogously define pseudopermutahedron_greater, and the associated triangular change of basis.

I don't know how to generalise permutahedron_lequal to pseudopermutahedron_lequal, because permutahedron_lequal uses the composition of permutations, rather than simply comparing inversions as I wrote in the description. I suppose we could just code that comparison of inversions instead, and ignore what's in permutahedron_lequal. (I want to try to do this, but I can't connect to SageMathCloud / CoCalc at the moment)

[amypang]

comment:3

(fixed the inversion comparison in the description)

[amypang]

comment:4

I need to go to bed now, but here's what I have for coding pseudopermutahedron_lequal. Still lacking many many things. I might do more about 10 hours later, but this is pretty hard for me.

def is_inversion(self,i,j):
    r""" 
    Returns 1 if i is in a block strictly to the right of j; returns 1/2 if i is in the same block as j
    
    TODO:
    We should first check i<j , and if not return an error.
    """
    b=0
    while (i in self[b])+(j in self[b])==0:
        b=b+1
    if (i in self[b])+(j in self[b])==2:   
        return 0.5
    elif (j in self[b])==1:
        return 1
    else:
        return 0

def pseudopermutohedron_lequal(u,v):
    r"""     
    Return ``True`` if ``u`` is less than or equal to ``v`` in the pseudopermutohedron order. 
    """
    #let n be the common size of u and v - I think a method to get the size is not implemented in Ordered_Set_Partition yet.
    for j in range(1,n+1):
        for i in range (1,j):
            if is_inversion(u,i,j) <= if is_inversion(v,i,j)
            #break and return zero, otherwise continue, and at the end return 1.

[tscrim]

comment:5

Thanks for making progress on this. With how things are progressing so far today, I doubt we will work on this part. Darij is doing #25151, I am doing #25149, Aaron is doing #25155.

[amypang]

comment:6

Well, this is far less important than the tickets you listed so of course you guys should prioritise those. (My WQSym research project is on hold at the moment so I'm not in any rush to have this.) I am being greedy asking for so many things! Thanks for writing so much CHA code!

[darijgr]

comment:7

A few observations:

• I think the description of successors in arXiv:math/0605061v1 (between (45) and (46)) is wrong.

• In terms of packed words, the pseudo-permutohedron order can be defined as follows: Two packed words u and v of length n satisfy u <= v if and only if each i < j satisfies (if u_i > u_j, then v_i > v_j) and (if u_i >= u_j, then v_i >= v_j).

• For any packed word w, let comp(w) be the complement of w (that is, replace each letter k by L+1-k, where L is the number of distinct letters of w). Then, two packed words u and v satisfy u <= v if and only if comp(v) <= comp(u). Note that on ordered set partitions, "comp" corresponds to reversing the order of the blocks. Thus, two ordered set partitions P and Q satisfy P <= Q if and only if their reversals rev(P) and rev(Q) satisfy rev(Q) <= rev(P).

• If two ordered set partitions P and Q satisfy P <= Q in pseudo-permutohedron order, then they also satisfy P <= Q in lex order. Thus, unitriangularity can be used in constructing the bases.

• Given an ordered set partition P, how do we find all ordered set partitions Q satisfying P <= Q in pseudo-permutohedron order? Here is an algorithm: First, declare two successive blocks of P to be mergeable if and only if max(left block) < min(right block). There are several ways of merging mergeable pairs of successive blocks. Let R_1, R_2, ..., R_k be the resulting ordered set partitions (note that k is a power of 2). For each i, there are several ways of splitting each block of R_i into several (possibly 1) sub-blocks in such a way that each pair of these consecutive sub-blocks satisfies min(left sub-block) > max(right sub-block). Let Q_{i, 1}, Q_{i, 2}, ..., Q_{i, p_i} be the results (again, p_i is a power of 2). Then, the Q_{i, j} for various i and j are all distinct, and are all the ordered set partitions Q satisfying P <= Q.