Is this feature: (x+y+3).reduce(Ideal([x*(x-1),y*(y-1)])) == x+y+3

[Georgi Guninski]

sage: K.<x,y>=QQ[]
sage: I=[x*(x-1),y*(y-1)]
sage: a=x+y+3
sage: a.reduce(Ideal(I))
x + y + 3

In addition:
sage: Kq=K.quotient(I);Kq(a)
xbar + ybar + 3

sage: Ideal([a]+I).groebner_basis()
[1]

[Vincent Neiger]

Hello,

The output seems to be the expected one. Can you please clarify what your question/observation is?

For the first output, 'a' is already reduced w.r.t the DegRevLex Gröbner basis of the ideal (which happens to be the two provided polynomials in this case). The behaviour is clearly specified in the documentation.

For the second one I'm not sure what it is that we should observe.

For the third one, yes Ideal([a]+I) is indeed the whole polynomial ring (easily observed by considering the common roots of the three polynomials), hence the Gröbner basis [1] for any term order.

Thanks for clarifying the question!

[Georgi Guninski]

Hi, thanks for the answer.
I am trying algebraic approach to the NP-hard problem
independent set in graph.
For integer n, working over QQ['x',n] (probably another base field
will work too).
I have the following constraints:
1. x[i]*(x[i]-1)=0, i <=0 <n
2. For a set of integer pairs (u_i,v_i) add the constraints
x[u_i]*x[v_i]=0

So far groebner basis are easy to compute.
The additional hard constraint is
3. sum(x_i)=k
for integer k.

Are there special cases (u_i,v_i),k and base field for solving (1),(2),(3)?

Experimentally groebner basis work, but adding (3) makes
the computation slow.