factorization of symmetric functions

[mantepse]

We implement factor, gcd and _floordiv_ for symmetric functions, and thus make them a UniqueFactorizationDomain.

CC: @tscrim

Component: combinatorics

Author: Martin Rubey

Branch/Commit: 6e1f451

Reviewer: Travis Scrimshaw

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

[mantepse]

Branch: u/mantepse/factorization_of_symmetric_functions

[mantepse]

Author: Martin Rubey

[mantepse]

comment:2

I guess it would be good to tell the parent that it is a UFD whenever it is, but I don't know how.

---

New commits:

a81e4d5

implement factorization of symmetric functions

[mantepse]

Commit: a81e4d5

[mantepse]

comment:3

I think I like it:

sage: R.<t> = QQ[]
sage: Sym = SymmetricFunctions(FractionField(R))
sage: JP = Sym.jack(t).P(); JP
Symmetric Functions over Fraction Field of Univariate Polynomial Ring in t over Rational Field in the Jack P basis
sage: f = (JP[2,1]*t + JP[1,1,1])^2; f 
((20*t^3+60*t^2+40*t)/(t^3+12*t^2+47*t+60))*JackP[1, 1, 1, 1, 1, 1] + ((8*t^4+50*t^3+38*t^2+12*t)/(t^3+7*t^2+16*t+12))*JackP[2, 1, 1, 1, 1] +
((4*t^8+36*t^7+113*t^6+170*t^5+186*t^4+139*t^3+60*t^2+12*t)/(t^6+17/2*t^5+59/2*t^4+107/2*t^3+107/2*t^2+28*t+6))*JackP[2, 2, 1, 1] +
((6*t^6+21*t^5+10*t^4+6*t^3+13*t^2+12*t+4)/(t^4+6*t^3+13*t^2+12*t+4))*JackP[2, 2, 2] + ((22*t^5+40*t^4+34*t^3+12*t^2)/(t^4+6*t^3+13*t^2+12*t+4))*JackP[3, 1, 1, 1] +
((2*t^5+13*t^4+25/3*t^3+16/3*t^2+4/3*t)/(t^3+19/6*t^2+8/3*t+2/3))*JackP[3, 2, 1] + (2*t^3/(t+1))*JackP[3, 3] + (2*t^3/(t+1))*JackP[4, 1, 1] + t^2*JackP[4, 2]
sage: f.factor()
(1/(t^2 + 4*t + 4)) * ((-t-2)*JackP[1, 1, 1] + (-t^2-2*t)*JackP[2, 1])^2

[tscrim]

comment:4

To set the category, you need to do two things:

• Add it to the super_categories in SymmetricFunctionBasses in sfa.py.
• Add it to the cat in the class SymmetricFunctions in sf.py.

For the code, you can use M._from_dict because we know each index is unique because we are using the monomial basis for polynomials.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

c3ded27

add categories

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a81e4d5 to c3ded27

[mantepse]

comment:6

Ready!

[tscrim]

comment:7

Thank you. Green bot => positive review.

[tscrim]

Reviewer: Travis Scrimshaw

[mantepse]

comment:9

I don't quite understand where this error suddenly comes from.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c3ded27 to 5567eac

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

5567eac

Merge branch 'develop' of trac.sagemath.org:sage into t/34515/factorization_of_symmetric_functions

[tscrim]

comment:11

Random guess is something happened with the categories, but I need to investigate.

[mantepse]

comment:12

THe problem is that UniqueFactorizationDomains expects that also gcd is implemented. There should have been a TestSuite test that checks this, but apparently, there isn't.

gcd can be implemented along the same lines (i.e., converting to a polynomial and back), and I have already done this, but I need to polish first. I am not sure what the parent of gcd(self, other) should be, I am guessing self.parent()?

I don't know whether quo_rem also has to be implemented.

There is another glitch: when the union of all partitions in the symmetric functions has only a single part, then the polynomial ring is univariate, and the element constructor works differently. This is also easy to fix.

[mantepse]

comment:13

I "implemented" gcd and _floordiv_, but it seems that this is not quite sufficient:

sage -t --random-seed=47916933199520535698691498656724910757 src/sage/rings/lazy_series.py
**********************************************************************
File "src/sage/rings/lazy_series.py", line 150, in sage.rings.lazy_series
Failed example:
    check(L, L(p[1]))
Expected nothing
Got:
    unable to convert p[] to a rational in (1) / (3*p[])
    unable to convert p[] to a rational in (p[]) / (3*p[])
    unable to convert p[] to a rational in (p[1]) / (3*p[])
    unable to convert p[] to a rational in (p[] + p[1]) / (3*p[])
    cannot invert self (= -p[1]) in (p[] + p[1]) / (p[] + p[1])
    unable to convert p[] to a rational in (2*p[] + p[1] + (p[1,1])) / (3*p[])
    cannot invert self (= -p[1, 1]) in (2*p[] + p[1] + (p[1,1])) / (2*p[] + p[1] + (p[1,1]))
**********************************************************************
1 item had failures:
   1 of  55 in sage.rings.lazy_series
    [1464 tests, 1 failure, 11.78 s]

Very likely, these are true bugs. If so, there is another bug: these should also be detected by the doctests in the symmetric function code and the testsuite in lazy_series_ring.py, but aren't.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

dec76ef

implement `_floordiv_` and gcd

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5567eac to dec76ef

[mantepse]

comment:15

Help needed.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from dec76ef to ccc925f

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ccc925f

check whether we have a fraction field

[mantepse]

Description changed:

--- 
+++ 
@@ -1 +1 @@
-
+We implement `factor`, `gcd` and `_floordiv_` for symmetric functions, and thus make them a `UniqueFactorizationDomain`.

[mantepse]

comment:18

The implementation is ugly, and I would like to see more systematic testing, but I would need some hints for that.

[tscrim]

comment:19

I will try to take a look tomorrow.

[tscrim]

comment:20

Why are you testing if there is a fraction_field() method? Shouldn't it be more fundamental like being an integral domain (where the category provides a default)?

What else are you currently unsure about? The implementation looks okay to me modulo the above question.

One other small thing I might change is

         R = self.base().base_ring()
         cat = HopfAlgebras(R)
+        categories = [self.base().Realizations(),
+                      cat.Commutative().WithBasis(),
+                      cat.Graded().Realizations()]
         if R in PrincipalIdealDomains:
+            categories.append(UniqueFactorizationDomains())
+        return categories
-            return [self.base().Realizations(),
-                    cat.Commutative().WithBasis(),
-                    cat.Graded().Realizations(),
-                    UniqueFactorizationDomains()]
-
-        return [self.base().Realizations(),
-                cat.Commutative().WithBasis(),
-                cat.Graded().Realizations()]

[mantepse]

comment:21

Replying to Travis Scrimshaw:

Why are you testing if there is a fraction_field() method? Shouldn't it be more fundamental like being an integral domain (where the category provides a default)?

Unfortunately, this is not true - there is no default implementation of fraction_field, this would be #34347.

What else are you currently unsure about? The implementation looks okay to me modulo the above question.

There are two separate issues:

• it seems to me that the quality of our test suite should be improved in this ticket - and not postponed, because I only see it's lackingness here: we enhance the ring of symmetric functions, and a test in lazy_series.py fails, which is not even in the testsuite.

• in sfa.py, I am providing the very same not entirely trivial code to convert to and from a polynomial three times. Moreover, I think it might be better to put this code into SymmetricFunctionAlgebra_multiplicative, and thus separate factorization from conversion to a parent where we can do the factorization.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ccc925f to 40c82e8

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

40c82e8

polish categories

[tscrim]

comment:23

Replying to Martin Rubey:

Replying to Travis Scrimshaw:

Why are you testing if there is a fraction_field() method? Shouldn't it be more fundamental like being an integral domain (where the category provides a default)?

Unfortunately, this is not true - there is no default implementation of fraction_field, this would be #34347.

Ah, right, it is not required yet. However, my question still holds. It is conceivable that division still makes sense without going to the fraction field:

sage: R.<z> = LaurentPolynomialRing(QQ)
sage: (1 / z).parent()
Univariate Laurent Polynomial Ring in z over Rational Field

Admittedly that is a bit of a special case, but testing for a fraction field feels like slightly too strong of a restriction.

What else are you currently unsure about? The implementation looks okay to me modulo the above question.

There are two separate issues:

• it seems to me that the quality of our test suite should be improved in this ticket - and not postponed, because I only see it's lackingness here: we enhance the ring of symmetric functions, and a test in lazy_series.py fails, which is not even in the testsuite.

That is exactly what good doctests should do. Not everything needs to be, nor should be, jammed into the test suite. It has limitations of being a general purpose tool, part of which is based on the elements given to it to test. Of course, that should not be taken as we should not improve the test suite with general tests where appropriate. However, I don't think we should make broader changes on this ticket.

Am I correct in that ccc925f fixes the failures you were seeing?

• in sfa.py, I am providing the very same not entirely trivial code to convert to and from a polynomial three times. Moreover, I think it might be better to put this code into SymmetricFunctionAlgebra_multiplicative, and thus separate factorization from conversion to a parent where we can do the factorization.

I think that conversion (as a hidden _to_poly and _from_poly) could work. Although it is not quite isolated because you have two different elements (for two methods) that should be in the same polynomial ring when done. That kind of communication would be hard. At this point, we aren't scaling this, so it might not be worth the time and effort to find a solution to this right now.

Also _floordiv_ should have both its arguments are part of the same parent, hence the first part of that function should not be necessarily. For gcd, there is the decorator @coerce_binop that you can use to avoid the common parent finding too.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 40c82e8 to f58b8f5

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

f58b8f5

factor out conversion to and from polynomials

[mantepse]

comment:25

I simplified the code (before the commit, corner cases were failing). Is the following intentional?

sage: R.<q> = ZZ[]
sage: R(6).factor()
2 * 3
sage: R(6).factor().universe()
Integer Ring

[mantepse]

comment:26

Replying to Travis Scrimshaw:

Replying to Martin Rubey:

Replying to Travis Scrimshaw:

Why are you testing if there is a fraction_field() method? Shouldn't it be more fundamental like being an integral domain (where the category provides a default)?

Unfortunately, this is not true - there is no default implementation of fraction_field, this would be #34347.

Ah, right, it is not required yet. However, my question still holds. It is conceivable that division still makes sense without going to the fraction field:

sage: R.<z> = LaurentPolynomialRing(QQ)
sage: (1 / z).parent()
Univariate Laurent Polynomial Ring in z over Rational Field

Admittedly that is a bit of a special case, but testing for a fraction field feels like slightly too strong of a restriction.

The restriction is only in the case of exact series - but I don't quite understand your question: this R does have _fraction_field, and it coincides with R.

Oh, now I see. I think I want R.base_ring() to have a fraction field...

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

0493593

fix thinko

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f58b8f5 to 0493593

[mantepse]

comment:28

Can / should we do something about the unit in the factorization?

sage: n=6; [s(la).factor() for la in Partitions(n)]
[s[6],
 (-1) * (-s[5, 1]),
 s[4, 2],
 s[4, 1, 1],
 (-1) * (-s[3, 3]),
 s[3, 2, 1],
 (-1) * (-s[3, 1, 1, 1]),
 (-1) * (-s[2, 2, 2]),
 (-1) * (-s[2, 2, 1, 1]),
 s[2, 1, 1, 1, 1],
 (-1) * (-s[1, 1, 1, 1, 1, 1])]

[tscrim]

comment:29

Factorizations in a UFD are only defined up to a unit. So we cannot do anything about that. We would have no way to say which factor to bring the unit to in general, and it isn’t worth a special case for “simple” cases IMO.

[mantepse]

comment:30

D'accord !

[mantepse]

comment:31

I just noticed that there is a method for monomial symmetric functions doing the same, just less generally and with a bug:

    def from_polynomial_exp(self, p):
    ...
    assert self.base_ring() == p.parent().base_ring()
    return self.sum_of_terms((Partition(exp=monomial), coeff)
                             for monomial, coeff in p.dict().items())

shall I replace this with

    def from_polynomial_exp(self, p):
    ...
    assert self.base_ring() == p.parent().base_ring()
    from sage.combinat.sf.sfa import _from_polynomial
    return _from_polynomial(p, self)

?

[tscrim]

comment:32

Yes, we should replace it.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0493593 to 8e13942

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

8e13942

use new function also elsewhere, fix typo

[mantepse]

comment:34

anything else I should do?

[tscrim]

comment:35

Not that I can think of.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 8e13942 to a52bc66

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a52bc66

remove unused import

[tscrim]

comment:37

Morally green bot. So is it ready for a positive review?

[mantepse]

comment:38

Yes, please!

[vbraun]

comment:40

Merge failure on top of:

a372136c066 Trac #33941: Implement from_integer and to_integer for all finite fields, extending and replacing fetch_int and integer_representation

3b1c9de1201 Trac #33757: commutativity test

34266283ab5 Trac #29360: change_ring() should preserve sparsity of vectors and vector spaces

1f56ce0e9d7 Trac #27652: parent of plethysm

019537d9929 Trac #34693: Further support for matplotlib 3.6

59e9f7b4f01 Trac #34658: Update numpy to 1.23.5, scipy 1.9.3, networkx 2.8.8, meson_python 0.11.0

6d03a671290 Trac #34593: Document and manage temporary directories

454290087ec Trac #33842: Upgrade python to 3.11

f53f07a063f Trac #34766: GH Actions: Update actions

795383fbdc9 Trac #34728: change sorting for WeierstrassIsomorphism

2cec793d624 Trac #33562: Bad error message for weighted adjacency matrix

3670306d20f Trac #34740: dead hyperlinks in developer manual

9666ae7ced6 Trac #34722: some code cleanup in WeierstrassIsomorphism

f41abf6243d Trac #34759: some details in filtered simplicial complexes

dfc299ba564 Trac #34756: Documentation regarding setting up SageMath's Jupyter kernel in an existing installation points to wrong directory

513a7bc6a9c Trac #34753: fix all W391 in pyx files

7503e42cf2f Trac #34751: Update sage tutorial

623ea7446d3 Trac #34745: modernize super in algebras/ again

f2fa7597737 Trac #34741: OS X 13: filter out dylib warning

a4748c342ab Trac #34738: tiny details in symbolic min and max

fb213dfda77 Trac #34769: use libgap in simplicial_complex

01beb6a1069 Trac #34765: meson: Add spkg-configure.m4

d94c7334140 Trac #34762: Fix random chain complex doctest

b3398f0543d Trac #34761: Remove src/sage/libs/fes.pyx

3c42a395c22 Trac #34754: Remove module-level imports from sage.plot

0d120581338 Trac #34569: Fix some quasimodular forms rings methods for congruence subgroups

84f02afa5c8 Updated SageMath version to 9.8.beta4

merge was not clean: conflicts in src/sage/combinat/sf/sfa.py