parent of plethysm

[mantepse]

Depends on #34470

CC: @zabrocki

Component: combinatorics

Keywords: conversion

Author: Martin Rubey

Branch/Commit: 0dcc0aa

Reviewer: Travis Scrimshaw

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

[mantepse]

Branch: u/mantepse/parent_of_plethysm

[mantepse]

Commit: 9280ad9

[mantepse]

Author: Martin Rubey

[mantepse]

New commits:

9280ad9

make plethysm with tensor return result as element of second parent

[zabrocki]

comment:4

Can you explain why you would do this? It seems wrong to me.

sage: s[2,1](p[1]+1)
s[1] + s[1, 1] + s[2] + s[2, 1]
sage: s[2,1](tensor([p[1],p[1]]))
1/3*p[1, 1, 1] # p[1, 1, 1] - 1/3*p[3] # p[3]

[mantepse]

comment:5

I have two reasons:

1.) the result of plethysm with a tensor is a tensor.

2.) I have a class that inherits from CombinatorialFreeModule_Tensor. Essentially, it is a parent for tensor products of symmetric functions, with some extra methods. I want that plethysm with an element from this class works. It almost does, except that the result is then a tensor product, and not an element from my class.

To elaborate on 2., here is my code. (The tensor_constructor method works around another thing, which I think is a bug.)

"""
sage: S = SymmetricFunctions(QQ)
sage: S.inject_shorthands()
sage: t = tensor([s[1,1], h[2]])
sage: P = TwoPositions(S.s(), S.h())
sage: x = P(t)
sage: 2*x
sage: h[2](x)
"""
def from_ch_characters(t):
    P = TwoPositions(*t.parent()._sets)
    return P(t)

class TwoPositionsElement(CombinatorialFreeModule_Tensor.Element):
    pass


from sage.combinat.free_module import CombinatorialFreeModule_Tensor, CartesianProductWithFlattening
class TwoPositions(CombinatorialFreeModule_Tensor):
    def __init__(self, *modules):
        cat = HopfAlgebrasWithBasis(QQ).TensorProducts()
        CombinatorialFreeModule_Tensor.__init__(self,
                                                modules,
                                                category = cat)

    @cached_method
    def tensor_constructor(self, modules):
        assert(module in ModulesWithBasis(self.base_ring()) for module in modules)
        # assert(tensor(modules) == self)
        # a list l such that l[i] is True if modules[i] is readily a tensor product
        is_tensor = [isinstance(module, CombinatorialFreeModule_Tensor) for module in modules]
        # the tensor_constructor, on basis elements
        result = self.monomial * CartesianProductWithFlattening(is_tensor) #.
        # TODO: make this into an element of Hom( A x B, C ) when those will exist
        for i in range(0, len(modules)):
            result = modules[i]._module_morphism(result, position = i, codomain = self)
        return result

    def __repr__(self):
        return "TwoPositions in %s"%(self._sets,)

    Element = TwoPositionsElement

[zabrocki]

comment:6

A change like this may make yours work but at the expense of breaking other's code.

This change is not consistent with other uses of plethysm. I don't think that your "1.) the result of plethysm with a tensor is a tensor" is a reason at all because the plethysm of a tensor is already a tensor. What you are doing is proposing changing the output basis. The choice of making the basis output of f(g) the basis that f is expressed in not arbitrary and should not be changed without fundamental reasons ("it doesn't work with my code" is not fundamental, find another way to make your code work, I am sure that there are a dozen ways of doing that without changing the behavoir of plethysm).

except that the result is then a tensor product, and not an element from my class.

But then you should cast the output into your class.

[mantepse]

comment:7

OK, no problem, although I do not understand your reasons.

Possibly I miscommunicated item 1: what I meant to say is that f(g) is more naturally an element of the parent of g than of the parent of f. The basis f is expressed in cannot possibly be a basis for g or f(g), except when f and g are both symmetric functions (in a single alphabet, so to say).

In other words, the change of basis plethysm currently does is much more drastic than what I am proposing.

I agree that item 2 is not a good reason. However, I do not know an easy workaround. In particular, I do not know how to cast the output into my class, because plethysm is a method of symmetric functions, not of my class.

[zabrocki]

comment:8

In my example I showed you that the plethysm of a Schur basis element and a power basis element outputs something in the Schur basis. That is the default behavior.

what I meant to say is that f(g) is more naturally an element of the parent of g than of the parent of f.

Maybe sometimes, but not in my uses of plethysm. I might be able to be convinced, but I would examples and even then I would hesitate to make a change like this because that is not what happens for f(g) currently and it is likely to break users' code.

In particular, I do not know how to cast the output into my class, because plethysm is a method of symmetric functions, not of my class.

I think that what you are proposing is a way to f(g) when g is not a symmetric function or a tensor of symmetric functions, but instead an element of your new class. That is, you are proposing adding another case into the computation of f(g) : if g is of new class then do yet a different computation. I don't think that this requires you to change the default behavior of the computation of f(g) when g is a tensor of symmetric functions.

[mantepse]

comment:9

Maybe sometimes, but not in my uses of plethysm.

I agree that other conventions may be more convenient for other uses. Of course, I know nothing about your uses of plethysm.

In my computations, it happens frequently that the basis of the tensor product is chosen for a reason, and the basis of f in f(g) is rather arbitrary. But this is very likely only by coincidence.

sage: s[2](tensor([s(h[2]), s(m[2])]))
s[2, 2] # s[2, 2] - s[2, 2] # s[3, 1] + s[2, 2] # s[4] + s[3, 1] # s[1, 1, 1, 1] - s[3, 1] # s[2, 1, 1] + s[3, 1] # s[2, 2] + s[4] # s[2, 2] - s[4] # s[3, 1] + s[4] # s[4]
sage: s[2](tensor([(h[2]), (m[2])]))
h[2, 2] # m[2, 2] + h[2, 2] # m[4] - h[3, 1] # m[4] + h[4] # m[4]

I guess that the only real reason I have to offer is that a basis for the symmetric functions cannot possibly be a basis for a tensor power of symmetric functions. Since the result is in tensor space, I really have to choose a basis for the tensor space, and taking a power of the basis of f seems more arbitrary than taking the basis of g.

Concerning the other question: no I do not want to add another case into the computation of f(g), my class for g is simply a tensor product of symmetric functions with some more methods. I guess it might be possible to define an action of symmetric functions on my class, but I don't know how to do that. I wonder how generic plethysm really is (I think Borger and Wieland studied that).

[embray]

comment:10

Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).

[embray]

comment:11

Ticket retargeted after milestone closed

[mkoeppe]

comment:12

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[mkoeppe]

comment:14

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:15

Setting a new milestone for this ticket based on a cursory review.

[tscrim]

comment:27

Replying to Martin Rubey:

Great!

Concerning the code: wouldn't it be better to do the easy change first, and speedup in another ticket?

You are already changing the code there anyways. It is simple enough to do if you know which parent you are summing over.

Hm, I just wanted to show off that the lazy code would be much faster, but it isn't on my branch right now. What happened?

The current branch here doesn't have the lazy series stuff (it is better that it doesn't IMO). You can create a new branch and merge the two together to test them simultaneously.

[mantepse]

comment:28

Travis, I tested it on my branch, not on this branch.

sage: N=5; f = sum(s(Partitions(n).random_element()) for n in range(N)); g = sum(s(Partitions(n).random_element()) for n in range(1, N)); f1 = L(f) + L(lambda n: 0) ; g1 = L(g) + L(lambda n: 0)
sage: %time r = f(g)
CPU times: user 705 ms, sys: 1 µs, total: 705 ms
Wall time: 705 ms
sage: %time r1 = f1(g1).truncate(f.degree()*g.degree()+1)
CPU times: user 1.09 s, sys: 1 µs, total: 1.09 s
Wall time: 1.09 s

[tscrim]

comment:29

The branch in this ticket is also your branch. So I thought that was what you were talking.

However, I am not sure what has changed with the lazy plethysm speed. I don't think we changed anything with that...

[mantepse]

comment:30

Can we be sure that our plethysm was faster?

[tscrim]

comment:31

You had an example of this in ticket:34383#comment5.

[mantepse]

comment:32

Wow, great, thank you!

Apparently I misremembered, because there we only compute a single degree of the plethysm, not all of them.

However, %prun shows something very strange, which might give us a hint for what we are doing wrong.

sage: N=5; f = sum(s(Partitions(n).random_element()) for n in range(N)); g = sum(s(Partitions(n).random_element()) for n in range(1, N)); f1 = L(f) + L(lambda n: 0) ; g1 = L(g) + L(lambda n: 0)

sage: %prun r1 = f1(g1).truncate(f.degree()*g.degree()+1)
         2373194 function calls (2371664 primitive calls) in 1.949 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1173    0.656    0.001    1.519    0.001 {sage.libs.symmetrica.symmetrica.t_POWSYM_SCHUR_symmetrica}
    ...
      719    0.138    0.000    1.893    0.003 {built-in method sage.data_structures.blas_dict.linear_combination}
    ...
     1124    0.002    0.000    0.015    0.000 partition.py:1060(stretch)
    ...

sage: %prun r = f(g)
         1413296 function calls (1409790 primitive calls) in 1.182 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
      512    0.309    0.001    0.797    0.002 {sage.libs.symmetrica.symmetrica.t_POWSYM_SCHUR_symmetrica}
    ...
     26/4    0.091    0.004    1.182    0.295 {built-in method sage.data_structures.blas_dict.linear_combination}
    ...
      220    0.000    0.000    0.003    0.000 partition.py:1060(stretch)

For some reason, t_POWSYM_SCHUR_symmetrica is called more than twice as often for our algorithm than for the one in sfa.py. I don't see why this should be the case. Same goes for stretch.

[tscrim]

comment:33

Indeed, that is interesting. I guess it depends on what things we want to actually compute.

Perhaps we can move this to a new ticket, both to keep the scope of this ticket to symmetric functions, and to not spam other cc-ed people. ;).

For this ticket, I rebased it on #34470 (strictly speaking, it should be #34413) as there was a conflict. I made an optimization with how the sums are computed. I also fixed a few things with how scalars are handled, which arose from making the output be in the input parent (or the base ring for scalars; I don't see an easy way to deal with doing pushouts).

Unfortunately I accidentally put my changes into the merge comment. >_< So it is hard to see the bulk of them commit-by-commit.

Anyways, if the patchbot comes back again green and you are happy with my changes, then I think we are at a positive review.

---

Last 10 new commits:

aa593b5	Merge branch 'u/mantepse/categories_of_lazy_series' of https://github.com/sagemath/sagetrac-mirror into u/tscrim/categories_lazy_series-34470
840539d	More tests, more bugs fixed.
fbccb39	normalize degree in Stream_exact for correct equality
b930f58	Merge branch 'u/mantepse/categories_of_lazy_series' of https://github.com/sagemath/sagetrac-mirror into u/tscrim/categories_lazy_series-34470
b47407b	Implementing `_floordiv_`, Stream._true_order to boolean, first fraction field, more tests, marking long tests.
e077b66	Using dynamic classes for FPS gcd.
ddc04a1	Fixing last pyflakes things.
d95f9ba	Merge branch 'u/tscrim/categories_lazy_series-34470' of https://github.com/sagemath/sagetrac-mirror into u/tscrim/parent_plethysm-27652
5b8a696	Merge branch 'u/mantepse/parent_of_plethysm' of https://github.com/sagemath/sagetrac-mirror into u/tscrim/parent_plethysm-27652
c501119	Making the result not depend on the input.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

Changed branch from u/mantepse/parent_of_plethysm to u/tscrim/parent_plethysm-27652

[tscrim]

Dependencies: #34470

[tscrim]

Changed commit from 9280ad9 to c501119

[mantepse]

comment:34

I agree to moving the performance discussion to a different ticket. I feel a bit uneasy with merging the lazy stuff into this ticket, but I guess it makes no difference.

[tscrim]

comment:35

We have to deal with the conflict somewhere, and better here because #34413 is already positively reviewed.

[mantepse]

comment:36

Do you understand these warnings?

========== deprecation_number ==========
git checkout patchbot/ticket_merged
+            deprecation(32367, 'the method coefficients now only returns the non-zero coefficients. Use __getitem__ instead.')
+        deprecation(32367, 'the method exponential is deprecated. Use exp instead.')
+        deprecation(32367, "the method compute_coefficients obsolete and has no effect.")
Wrong deprecation number inserted on 3 non-empty lines
deprecation_number -- 0 seconds
========== end deprecation_number ==========

[tscrim]

comment:37

It comes from the patchbot implementation being simple and not realizing it is coming from a dependency ticket. We can ignore it.

[mantepse]

comment:38

Should there be a doctest (and perhaps even specification) demonstrating that the parent is now the parent of the inner function?

Should there maybe even be a warning? I am somewhat afraid that some people may have private code like

sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: n = 5; f = p[2,2,1] + p[5]
sage: s[2](f)[Partition([2*n])]
3

who might be not amused about not being warned.

[tscrim]

comment:39

IMO, this is a bug (such as composing with a tensor product), so no warning/deprecation is necessary. I agree with you that we should add a doctest and documentation indicating this behavior.

[sagetrac-git]

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

bad6489

Adding some doctests and documentation on the plethysm output.

[sagetrac-git]

Changed commit from c501119 to bad6489

[tscrim]

comment:41

I've added it.

[mantepse]

Changed branch from u/tscrim/parent_plethysm-27652 to u/mantepse/parent_plethysm-27652

[mantepse]

Changed commit from bad6489 to 0dcc0aa

[mantepse]

comment:43

ping?

---

New commits:

0dcc0aa

Merge branch 'develop' of trac.sagemath.org:sage into t/27652/parent_plethysm-27652

[tscrim]

comment:44

I'm happy. If you are with my added tests, then positive review.

[vbraun]

Changed branch from u/mantepse/parent_plethysm-27652 to 0dcc0aa