Fraction field of Symmetric Functions and other integral domains which do not inherit from Ring

[mantepse]

We currently have

sage: e = SymmetricFunctions(QQ).e()
sage: e in IntegralDomains()
True
sage: FractionField(e)
...
AttributeError: 'SymmetricFunctionAlgebra_elementary_with_category' object has no attribute 'fraction_field'

sage: P.<t> = PolynomialRing(e)
sage: f = (t*e[2] + 1)*(t + e[1])
sage: g = (t + 1)*(t + e[1])
sage: gcd(f, g)
...
NotImplementedError: Symmetric Functions over Rational Field in the elementary basis does not provide a gcd implementation for univariate polynomials

However, all integral domains should come with at least a generic implementation fraction_field.

Since the ring of symmetric functions is even a unique factorization domain, so at least we should have a gcd.

CC: @videlec @tscrim

Component: categories

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

[mantepse]

comment:1

Once this is done, we can remove the check hasattr(R, "_gcd_univariate_polynomial") in lazy_series.py.

[tscrim]

comment:3

Not every integral domain is a gcd domain. So I would guess there is no way to define a generic implementation. One might be possible that fails along the way, but more likely it would run forever by some infinite chain of ideals.

Sage also is not 100% careful when it comes to fraction fields either:

sage: R.<z> = PowerSeriesRing(ZZ)
sage: R.fraction_field()  # This is too big as it contains e^z
Laurent Series Ring in z over Rational Field

See, e.g., this MathSE post. Although here this is sufficient (and possibly better due to the simplicity of the implementation) for doing computations, but strictly speaking, its fraction field is a subfield.

That being said, in this case for gcd, we should directly implement a gcd() method on symmetric functions by using a freely generated basis (e.g., the e, h, or p basis) and move the computation to an appropriate polynomial ring.

For the fraction_field(), I think we could copy the implementation from CommutativeRing as

    @cached_method
    def fraction_field(self):
        """
        Return the fraction field of ``self``.
        """
        from sage.rings.fraction_field import FractionField_generic
        return FractionField_generic(self)

Now the FractionField_generic probably should inherit from UniqueRepresenation, which would also mean we should not cache the result (this creates a memory leak IIRC). Although I am slightly hesitant to change that because it can have far-reaching consequences to parts of Sage that people want to be very fast as the work over a range of parents (finite fields with many different prime powers as I understand it).

Yet, even with this change, it doesn't solve the problem for symmetric functions:

sage: e = SymmetricFunctions(QQ).e()
sage: IntegralDomains() in e.categories()
False

There are a few different fixes for this. The first two that come to mind are

1. Refine the category of symmetric functions by checking if the base ring is an integral domain at initialization.
2. Putting the fraction_field() in CommutativeRings() with the same is_integral_domain() test.

(1) involves more stuff during the creation of the parent (e.g., needs a prime check when working over Z/nZ). (2) means it only gets checked when needed, but it puts a method in a "too general" category. Personally, I don't think (1) will happen that much, so it would be the route I would go.

[mantepse]

comment:5

Replying to @tscrim:

Not every integral domain is a gcd domain. So I would guess there is no way to define a generic implementation. One might be possible that fails along the way, but more likely it would run forever by some infinite chain of ideals.

Sorry for that silly mistake. I modified the description of the ticket accordingly, but actually, this means we probably have two different tickets, one implementing factorization or at least gcd, and one for the category stuff.

[mantepse]

comment:6

For redemption, here is at least naive factorization code for symmetric functions.

def factor(self):
    """
    Return the factorization of this symmetric function.

    EXAMPLES::

        sage: e = SymmetricFunctions(QQ).e()
        sage: factor((e[3] + e[2,1])*(e[2] + e[4,1]))
        (e[2, 1] + e[3]) * (e[2] + e[4, 1])

    """
    P = self.parent()
    parts = sorted(set.union(*(set(la) for la in self.support())))
    R = PolynomialRing(self.base_ring(), ["v%s" % p for p in parts])
    gens = R.gens()    
    var_dict = {p: v for p, v in zip(parts, gens)}
    poly = sum(c * prod(var_dict[p] for p in part) for part, c in self)
    gen_dict = {v: P[p] for p, v in zip(parts, gens)}
    factored = [(factor.subs(gen_dict), c) for factor, c in poly.factor()]
    return Factorization(factored)

[videlec]

comment:7

I would rather go via some infinite polynomial ring which implements factorization

sage: R = InfinitePolynomialRing(QQ, 'x')
sage: x0 = R.gen()[0]
sage: x1 = R.gen()[1]
sage: x2 = R.gen()[2]
sage: p = (x0 + x1) * (x0 + x2)
sage: p
x_2*x_1 + x_2*x_0 + x_1*x_0 + x_0^2
sage: p.factor()
(x_1 + x_0) * (x_2 + x_0)

[mantepse]

comment:8

Is there an easy way to go from the polynomial to the symmetric function then?

[videlec]

comment:9

Hmm, I did not succeed. Looks a bit broken.

[tscrim]

comment:10

If you use a finite set of variables (which is what the InfinitePolynomialRing essentially does), then you can easily pull it back by using the exponents():

sage: R = PolynomialRing(QQ, 'x', 3)
sage: R.inject_variables()
Defining x0, x1, x2
sage: p = (x0 + x1) * (x0 + x2)
sage: p
x0^2 + x0*x1 + x0*x2 + x1*x2
sage: e = SymmetricFunctions(QQ).e()
sage: P = Partitions()
sage: e.sum_of_terms(((P.from_exp(ex), p.coefficient(ex))
....:                 for ex in p.exponents()), distinct=True)
e[1, 1] + e[2, 1] + e[3, 1] + e[3, 2]

This is not the most efficient way to do it, but it should be somewhat close.