Reduction over Ideal

[Santanu Sarkar]

Dear all,

    Consider ideal I=<x0*x1+x2> over the binary field GF(2). 

Then (x2).reduce(I) gives x2. I want it to be x0*x1. 

In fact , I want this kind of reduction always should give quadratic polynomial 

(I know that this is possible for my problems).

[Nils Bruin]

That means you should try and put a monomial order on your ring that gives x2 a higher weight than x0*x1. "lex" would do that. It may be that you need to order your variables as [x2,x0,x1] instead (i.e., that the first variable has the highest weight)

I don't know what you mean by "should always give a quadratic polynomial". With your ideal, x2^3 is not reducible to a quadratic polynomial. Do you want to work with a Boolean ring instead, where the relations x0^2-x0=1^2-x1=x2^2-x2=0 are implied as well?

 

[john_perry_usm]

Dear Santanu

Aside from Nils' answer, you may want to read up on Sage's term orderings:

rings.polynomial.term_order?

It's possible that you want a local term ordering. Unlike global term orderings, in a local ordering 1>t for any monomial t.

TO = TermOrder("negdegrevlex",3)

R = PolynomialRing(GF(2),'x',3,order=TO)

R.inject_variables()

>>>> Defining x0, x1, x2

I = R.ideal([x0*x1+x2])

x2.reduce(I)
>>>> x0*x1

Another possibility is a weighted (global) term ordering. For example, if I set the weight vector to (1,2,4), then x2>x0*x1, but I can still have x0^4>x2.

TO = TermOrder('wdegrevlex',(1,2,4))

R = PolynomialRing(GF(2),'x',3,order=TO)

R.inject_variables()
>>>> Defining x0, x1, x2

I = R.ideal([x0*x1+x2])

x2.reduce(I)
>>>> x0*x1

[Nils Bruin]

On Wednesday, August 5, 2020 at 10:19:57 AM UTC-7, john_perry_usm wrote:

It's possible that you want a local term ordering. Unlike global term orderings, in a local ordering 1>t for any monomial t.

TO = TermOrder("negdegrevlex",3)

R = PolynomialRing(GF(2),'x',3,order=TO)

R.inject_variables()

>>>> Defining x0, x1, x2

I = R.ideal([x0*x1+x2])

x2.reduce(I)
>>>> x0*x1

In which case you need to realize that you're not working in a polynomial ring but in its localization! This has been the source of many bug reports already, and is currently not sufficiently documented.