Ask Your Question
2

Iterate over a finite quotient of a multivariate polynomial ring

asked 2025-01-25 18:14:32 +0100

tungnt gravatar image

updated 2025-02-06 10:28:06 +0100

FrédéricC gravatar image

Hi everyone

I am trying to work with finite rings. In Sagemath, I learned that we could create a finite quotient of a multivariate polynomial ring with the following syntax

S = PolynomialRing(GF(2), 'x, y')
x,y = S.gens()
I = S.ideal([x**2, y**2])
R = S.quotient(I, names=S.variable_names())
print(R)

This works fine. The problem is that I can't iterate through this ring (I guess Sagemath does not automatically know that the ring is finite). A similar question is posted here but only for quotients of univariate polynomial rings.

https://ask.sagemath.org/question/651...

I tried to imitate the method there but have not been able to figure it out. I would love to hear your expertise on this. Additionally, I would love to hear if there is a built-in library in Sagemath for finite rings.

Thank you.

Tung

edit retag flag offensive close merge delete

Comments

1

This could be an XY problem. Why do you want to iterate over the whole quotient ring? There could be a better way to do what you ultimately want to do.

rburing gravatar imagerburing ( 2025-01-26 09:57:04 +0100 )edit

1 Answer

Sort by » oldest newest most voted
2

answered 2025-01-26 09:49:04 +0100

rburing gravatar image

updated 2025-01-26 09:53:39 +0100

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).

edit flag offensive delete link more

Comments

1

Thank you very much. You always came to the rescue of my questions!

I am working on gcd-graphs. To define this graph, I need to work with a finite ring R and a subset S of R. The vertex set is R, and two vertices $x,y$ are adjacent iff $x-y \in S$. Naturally, I need to iterate over R. Additionally, S often comes from a generating set so I need to generate it from R as well. With the solution that you proposed, I modified my code accordingly. Now, I can work with any finite quotients of a polynomial ring!

tungnt gravatar imagetungnt ( 2025-01-26 22:30:48 +0100 )edit

I have a question related to this (and that is why I responded to this comment instead of creating a new thread).

My understanding is that we can check whether the quotient ring S/I, where S is a multivariate polynomial ring with coefficients in a finite field, is finite by calculating

I.dimension()

The ring is finite if the dimension is 0 (or -1 if we count the zero ring as a finite ring).

I wonder whether there is a built-in function to tell whether this ring is local? Thank you.

tungnt gravatar imagetungnt ( 2025-01-31 18:49:17 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2025-01-25 18:14:32 +0100

Seen: 76 times

Last updated: Jan 26