"Mod" out symmetry in ideal for a Groebner basis calculation (using a quotient ring?)

Question

Consider a set of polynomials $P$ in the polynomial ring $R$ of $n$ variables ($R = \mathbb{C}[x_1,...,x_n]$), and let $I$ be the ideal generated by the polynomials in $P$.

I have an ideal which is invariant to some permutations in the variables. These permutations are a non-trivial proper subgroup of $S_n$ (the full group of permutations of the n variables). I will denote this subgroup as $G$.

Furthermore, in my case of interest, not all of the polynomials in the generating set $P$ are invariant to the permutations in $G$, yet the full set is invariant (some permutations permute the polynomials with-in P, while the set itself remains invariant).

I would like to, in essence, calculate the "symmetry unique" pieces of the Groebner basis of this ideal.

My real over-arching question is:

1. What are some options to "remove" the symmetry to simplify the calculation?

And narrowing in a bit:

2. Is this what a "quotient ring" is for?

Or is that for modding out a different structure? Because here, the generating polynomials do not have a particular symmetry (so it's not like I'm restricting to "the ring of symmetric polynomials"), it is instead the ideal which has a particular symmetry.

If I could use a quotient ring, I imagine it would go something like this:

• somehow construct an ideal $J$ capturing the 'symmetry' in $G$
• form a quotient ring $R_2$ = $R/J$
• get $I_2$, the ideal $I$ "transferred" from the ring $R$ to the quotient ring $R_2$
• now calculate the Groebner basis of $I_2$ in the quotient ring $R_2$

The above worries that a "quotient ring" is not the right object to use here, make me unsure how to even go about the first step there. So this leads me to ask:

3. Is this outline correct? If so, how do I construct $J$ to correctly capture the symmetry from the permutations in $G$ ?

Answer 1

Partial answer.

"Groebner bases of symmetric ideals", Stefan Steidel
Journal of Symbolic Computation 54, 72-86 (2013)
https://arxiv.org/abs/1201.5792

It suggests an algorithm for the case where $G$ is a cyclic group.

It is also implemented in Singular, so I gave it a try with a small instance of the problems I am trying to solve, and supplied a cyclic subgroup of G. It is still running after 12 hours, where-as just calculating the Groebner basis in Singular the usual way (ignoring the symmetry) will only take 10 minutes. To be honest, I do not really understand from the paper why a speed up is expected, as they transform the problem into multiple groebner basis calculations that appear to be of the same size as the original problem. Regardless of my poor understanding of the algorithm internals, the test indicates the algorithm is not always able to use the symmetry efficiently.

Answer 2

Partial answer in the negative: Quotient rings will not be useful in the outlined approach.

Given a group of permutations of the variables, the action of these permutations on polynomials allows us to define an equivalence relation between polynomials, $$ (p_1 \sim p_2) \quad\text{if and only if}\quad \exists \sigma \in G, p_1 = \sigma(p_2). $$ However this equivalence relationship cannot always be captured in an ideal.

For example, consider the polynomial ring in the variables $x$, $y$, $z$. Then define an equivalence relation by considering polynomials related by a cyclic permutation in the variables to be equivalent. However this equivalence relation does not lead to a quotient ring, as that would require the equivalence relation to be related to an ideal $J$ as follows: $$ (p_1 \sim p_2) \quad\text{if and only if}\quad (p_1 - p_2) \in J $$ It is impossible to construct such an ideal, which can be seen as follows:

• the polynomials $x$ and $y$ are related by a cyclic permutation in variables, and so $x-y$ should be in $J$
• this means $z^2(x-y)$ is in $J$
• but the polynomials $z^2x$ and $z^2y$ are not equivalent (are not related by a cyclic permutation in variables), leading to a contradiction. So this equivalence relation cannot be related to an ideal, and so we cannot use a quotient ring to "mod out" this particular symmetry.

This can be generalized as follows, as long as there exists two distinct polynomials $p_1$ and $p_2$ which are equivalent, and a third polynomial $q$ which is not symmetric under any of the permutations relating $p_1$ to $p_2$, then $(p_1 - p_2)$ should be in $J$, but then $q(p_1-p_2)$ should be in $J$ as well, leading to a contradiction.

This then highlights a larger issue. A natural mathematical object for this problem appears to be the equivalence classes of polynomials from a permutation group. However, these do not form a ring. For example, using the three variable ring and cyclic permutations from the previous example: $x \sim y$, and so we'd like to define addition such that $[x] - [y] = [x] - [x] = [0]$. But $x - y \nsim 0$, and so we cannot get a well defined addition when $[x - y] \neq [x] - [y]$.

Therefore we cannot discuss an ideal over these equivalence classes, let alone treat the problem as calculating a Groebner basis over them.

In retrospect, this seems clear. The symmetry is in the ideal, not the polynomials, so it makes sense that we cannot push handling the symmetry into a modification of the ring.

There very well may be some better way to carry around the symmetry information. Unfortunately, this is a partial answer, and I do not have a suggestion for what that would look like.