Symmetric functions: Kronecker product over any ring; Kronecker coproduct; antipode over any ring; forgotten basis over any ring; Witt basis; Frobenius and Verschiebung; doc fixes

[darijgr]

This ticket does the following:

1. The current version of itensor (the Kronecker product on the ring of symmetric function) only works when the ground ring is an algebra over the rationals. This is not a mathematically reasonable restriction. Fix this.

2. The Kronecker coproduct on the ring of symmetric function has to be implemented. Implement it.

3. The antipode on the ring of symmetric functions uses coercion into the powersum basis. This means it, too, is not getting computed over arbitrary base rings. Fix this.

4. The forgotten basis of Symm is defined by duality rather than by explicit formulas. Our duality methods use the powersum basis, again leading to errors for ground rings not being QQ-algebras.

5. The Witt symmetric functions form another basis of Symm. Implement them.

6. Implement Frobenius and Verschiebung operations on Symm without recourse to plethysm.

Apply:

• attachment: trac_14775-the_big_crunch.patch

CC: @zabrocki @anneschilling @tscrim @nthiery @hivert @sagetrac-sage-combinat @mwhansen

Component: combinatorics

Keywords: symmetric function, combinat, kronecker product, days49

Author: Darij Grinberg

Reviewer: Travis Scrimshaw, Mike Zabrocki

Merged: sage-5.12.beta4

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

[darijgr]

Description changed:

--- 
+++ 
@@ -1 +1,3 @@
 Will supply description in half an hour.
+
+"extend" == The current version only works when the ground ring is an algebra over the rationals, whereas mathematically this is not necessary.

[darijgr]

Changed keywords from none to symmetric function, combinat, kronecker product

[darijgr]

Author: Darij Grinberg

[darijgr]

Description changed:

--- 
+++ 
@@ -1,3 +1,5 @@
 Will supply description in half an hour.
 
 "extend" == The current version only works when the ground ring is an algebra over the rationals, whereas mathematically this is not necessary.
+
+I'd love someone to check the hacks used in the current file (even if it's far from complete -- it only attempts to implement the Kronecker product over any base ring) and tell me which of them are bad before I spread them into other functions.

[darijgr]

Changed keywords from symmetric function, combinat, kronecker product to symmetric function, combinat, kronecker product, days49

[darijgr]

Description changed:

--- 
+++ 
@@ -1,5 +1,11 @@
-Will supply description in half an hour.
+Goals for this ticket:
 
-"extend" == The current version only works when the ground ring is an algebra over the rationals, whereas mathematically this is not necessary.
+- The current version of itensor (the Kronecker product on the ring of symmetric function) only works when the ground ring is an algebra over the rationals. This is not a mathematically reasonable restriction. Fix this.
 
-I'd love someone to check the hacks used in the current file (even if it's far from complete -- it only attempts to implement the Kronecker product over any base ring) and tell me which of them are bad before I spread them into other functions.
+- The Kronecker coproduct on the ring of symmetric function has to be implemented. Implement it.
+
+- The forgotten basis of Symm is defined by duality rather than by explicit formulas. As a consequence, it cannot be computed when the ground ring is not a field. This might be easily fixable or not depending on how smart our dual basis methods are; either way, fix it.
+
+- The Witt symmetric functions form another basis of Symm. Implement them.
+
+The current file has the first goal achieved, but it uses some sly hacks. Can anyone tell me which of them are bad before I spread them into other functions (particularly for the second goal)?

[darijgr]

Description changed:

--- 
+++ 
@@ -1,11 +1,13 @@
 Goals for this ticket:
 
-- The current version of itensor (the Kronecker product on the ring of symmetric function) only works when the ground ring is an algebra over the rationals. This is not a mathematically reasonable restriction. Fix this.
+1. The current version of itensor (the Kronecker product on the ring of symmetric function) only works when the ground ring is an algebra over the rationals. This is not a mathematically reasonable restriction. Fix this.
 
-- The Kronecker coproduct on the ring of symmetric function has to be implemented. Implement it.
+2. The Kronecker coproduct on the ring of symmetric function has to be implemented. Implement it.
 
-- The forgotten basis of Symm is defined by duality rather than by explicit formulas. As a consequence, it cannot be computed when the ground ring is not a field. This might be easily fixable or not depending on how smart our dual basis methods are; either way, fix it.
+3. The antipode on the ring of symmetric functions uses coercion into the powersum basis. This means it, too, is not getting computed over arbitrary base rings. Fix this.
 
-- The Witt symmetric functions form another basis of Symm. Implement them.
+4. The forgotten basis of Symm is defined by duality rather than by explicit formulas. As a consequence, it cannot be computed when the ground ring is not a field. This might be easily fixable or not depending on how smart our dual basis methods are; either way, fix it.
+
+5. The Witt symmetric functions form another basis of Symm. Implement them.
 
 The current file has the first goal achieved, but it uses some sly hacks. Can anyone tell me which of them are bad before I spread them into other functions (particularly for the second goal)?

[darijgr]

comment:5

3 is done. Anyone has a better name than degree_negation for the algebra automorphism of SymmetricFunctions which acts as 1 in even degrees and 0 in odd ones?

The changes in the antipode method not only made it work over any rings, but also sped it up on each basis except for the powersum one (and the monomial one, but I improved that with a trivial fix):

Test suite:

def testall():
    Sym = SymmetricFunctions(QQ)
    print "m"
    timeit("SymmetricFunctions(QQ).m()([4,3,2]).antipode()")
    print "h"
    timeit("SymmetricFunctions(QQ).h()([4,3,2]).antipode()")
    print "e"
    timeit("SymmetricFunctions(QQ).e()([4,3,2]).antipode()")
    print "s"
    timeit("SymmetricFunctions(QQ).s()([4,3,2]).antipode()")
    print "p"
    timeit("SymmetricFunctions(QQ).p()([4,3,2]).antipode()")

Results:

original version:

sage: testall()
m
125 loops, best of 3: 1.86 ms per loop
h
25 loops, best of 3: 10.8 ms per loop
e
25 loops, best of 3: 10.8 ms per loop
s
25 loops, best of 3: 30.6 ms per loop
p
625 loops, best of 3: 146 µs per loop

after change of generic antipode to go via omega rather than via coercion to powersum basis:

sage: testall()
m
125 loops, best of 3: 2.16 ms per loop
h
125 loops, best of 3: 2.92 ms per loop
e
125 loops, best of 3: 2.92 ms per loop
s
625 loops, best of 3: 250 µs per loop
p
625 loops, best of 3: 148 µs per loop

after microoptimization in the antipode of powersum (replacing (-1)**blah by case distinction):

sage: testall()             
m
125 loops, best of 3: 1.79 ms per loop
h
125 loops, best of 3: 2.88 ms per loop
e
125 loops, best of 3: 2.95 ms per loop
s
625 loops, best of 3: 252 µs per loop
p
625 loops, best of 3: 113 µs per loop

[darijgr]

Description changed:

--- 
+++ 
@@ -6,7 +6,7 @@
 
 3. The antipode on the ring of symmetric functions uses coercion into the powersum basis. This means it, too, is not getting computed over arbitrary base rings. Fix this.
 
-4. The forgotten basis of Symm is defined by duality rather than by explicit formulas. As a consequence, it cannot be computed when the ground ring is not a field. This might be easily fixable or not depending on how smart our dual basis methods are; either way, fix it.
+4. The forgotten basis of Symm is defined by duality rather than by explicit formulas. Our duality methods use the powersum basis, again leading to errors for ground rings not being QQ-algebras.
 
 5. The Witt symmetric functions form another basis of Symm. Implement them.