Iterate over a finite quotient of a multivariate polynomial ring

savecancel

This is something that could be built in and made easier for users. For now, I think it needs slight manual work.

A vector space basis of the quotient $R = S/I$ where $S$ is a polynomial ring over a field is given by the normal basis of the ideal $I$ with respect to any term ordering (typically seen in the theory of Groebner bases), which is given in Sage by I.normal_basis() (the term ordering being taken from the polynomial ring, typically degrevlex if was not chosen explicitly by the user), and its size is I.vector_space_dimension() (slightly confusingly, it means the vector space dimension of $R/I$).

So to iterate over the quotient you can proceed as follows:

for C in cartesian_product([GF(2)]*I.vector_space_dimension()):
    f = sum(c*m for c,m in zip(C, I.normal_basis()))
    print(S(f))

Here I converted the polynomial into the quotient ring at the last step, which only changes the type of the polynomial.

When theoretically working with a quotient ring you can often do what you want computationally without ever really constructing the quotient ring (S here) as an object in itself, using e.g. the methods mentioned above as well as I.groebner_basis() and f.reduce(I) where f is an element of R and I is an ideal, or f.reduce(G) where G is a list of polynomials (e.g. a Groebner basis).