New polynomial ring categories

PolyRings.md

Basic problem

Classes for univariate polynomial (elements) need refactoring. Some reasons are:

1. Some classes are missing, such as for instance a generic class for polynomials over finite fields (only specialized class for some given implementation are provided).
2. We need more abstract classes. To date, many classes directly inherit from the generic class Polynomial since (for instance) the class Polynomial_generic_dense is concrete and thus fixes some data structure. Polynomials based on (say) Flint cannot use this data structure.
3. Based on the above, it seems useful for a polynomial class to support multiple inheritance. For instance, a class for sparse polynomials over ZZ should inherit both from a class for sparse polynomials, and a class for ZZ. This is impossible with Cython (which does not support multiple inheritance).
4. A consequence is also that many classes are directly in the class Polynomial with long spaghetti code made of tons of if ...: ... else: ... constructions to test the base rings.
5. A workaround has been introduced by introducing methods _xxx_univariate_polynomial in the base rings (currently with xxx in [gcd, roots, factor]). This is (in my and others' view) a bad way of cheating the object oriented paradigm of Python.

Possible solutions

1. Add "all" the missing classes, and separate more the dense and sparse implementations, to avoid multiple inheritance. The problem is that probably quite a lot of methods would be duplicated.
2. Introduce categories for polynomial rings. This is to my mind the most robust solution. Following is a skeleton of code to build this hierarchy (written by Nicolas Thiéry).

class UnivariatePolynomialsCategory(CovariantConstructionCategory, Category_over_base_ring):
    def __init__(self, base_category):
        """
        ...
        """
        super(UnivariatePolynomialsCategory, self).__init__(base_category, base_category.base_ring())

    _functor_category = "UnivariatePolynomials"

    def _repr_object_names(self):
        """
        ...
        """
        return "Univariate polynomials over a ".format(self.base_category()._repr_object_names())

from sage.categories.category_with_axiom import CategoryWithAxiom, all_axioms
all_axioms += ("Dense", "Sparse")


class SemiRings(Category):
    class SubcategoryMethods:
        def UnivariatePolynomials(self):
            """

                sage: SemiRings().UnivariatePolynomials()
                The category of univariate polynomials over a semiring
            """
            return ... # As in CartesianProducts

    class UnivariatePolynomials(UnivariatePolynomialsCategory):

        def extra_super_categories(self):
            return [Modules(self.base_ring()).WithBasis()]

        class SubcategoryMethods:
            def Sparse(self):
                return self._with_axiom("Sparse")
            def Dense(self):
                return self._with_axiom("Dense")

        class ParentMethods:
            def is_commutative(self):
                return self.base_ring().is_commutative()

        class Dense(CategoryWithAxiom):
            class ParentMethods:
                def is_dense(self):
                    return True

    class Commutative(CategoryWithAxiom):
        class UnivariatePolynomials(UnivariatePolynomialsCategory):
            def extra_super_categories(self):
                return [Magmas().Commutatif()]



class Fields(...):
    UnivariatePolynomials = LazyImport('sage.categories.univariate_polynomials_over_field', 'UnivariatePolynomialsOverField')

    class Finite(CategoryWithAxiom):
        class UnivariatePolynomials(...):
            class Dense(CategoryWithAxiom):
                class ElementMethods:
                    def factor(self):
                        ...


class MyConcretePolynomials(...):
    def __init__(self):
        Parent.__init__(self, category=self.base_ring().category().UnivariatePolynomials().Dense())