(x^6+y^9)%(x^3-y^2-1) == x^12*y - 4*x^9*y + ...

[Georgi Guninski]

Is this a bug:

sage: K.<x,y>=QQ[]
sage: (x^6+y^9)%(x^3-y^2-1)
x^12*y - 4*x^9*y + 6*x^6*y + x^6 - 4*x^3*y + y

In pari:
? (x^6+y^9)%(x^3-y^2-1)
%1 = y^9 + y^4 + 2*y^2 + 1

[John Cremona]

Surely it is just a question of precedence of variables.   In Sage you are dividing by a quadratic in y and getting a remainder which is linear in y.  In pari you are dividing by a cubic in x and getting a remainder which is of degree <3 in x.

If you swap x and y in both polynomials, sage's remainder is x^9 + x^4 + 2*x^2 + 1 as you were expecting (in y).

John

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAGUWgD8y6MxLfERAoP2D4xyX4sHy%2B8_L_Mn92FnXzw3Ha40_Fg%40mail.gmail.com.

[G. M.-S.]

John is right.

Dividing a by b means finding q and r such that a = q*b + r and r is either 0 or "smaller" than b.

The question is the meaning of "smaller".

For univariate polynomials, one says that r is smaller than b if deg(r) < deg(b) (one can include r = 0 by defining deg(0) = –∞).

For multivariate polynomials, one says that r is smaller than b if the leading monomial of r is smaller than the leading monomial of b (the polynomial 0 is special and has no leading monomial).

To define the leading monomial one needs an admissible order.

One example of admissible ordering is lex(x,y), where

x^e1*y^f1 < x^e2*y^f2 ⇔ (e1 > e2 or (e1 = e2 and f1 > f2))

(one is saying that x is infinitely bigger than y).

In SageMath, lex(x,y) gives:

sage: R.<x,y> = PolynomialRing(QQ, 2, order='lex')

sage: a,b=x^6+y^9,x^3-y^2-1

sage: a,b

(x^6 + y^9, x^3 - y^2 - 1)

sage: I=R.ideal(b)

sage: I.reduce(a)

y^9 + y^4 + 2*y^2 + 1

while lex(y,x) gives:

sage: R.<y,x> = PolynomialRing(QQ, 2, order='lex')

sage: a,b=x^6+y^9,x^3-y^2-1

sage: a,b

(y^9 + x^6, -y^2 + x^3 - 1)

sage: I=R.ideal(b)

sage: I.reduce(a)

y*x^12 - 4*y*x^9 + 6*y*x^6 - 4*y*x^3 + y + x^6

The default order for multivariate polynomial rings is degrevlex:

sage: R.<x,y>=QQ[]

sage: R.term_order()

Degree reverse lexicographic term order

sage: a,b=x^6+y^9,x^3-y^2-1

sage: a,b

(y^9 + x^6, x^3 - y^2 - 1)

sage: I=R.ideal(b)

sage: I.reduce(a)

y^9 + y^4 + 2*y^2 + 1

sage: a % b

x^12*y - 4*x^9*y + 6*x^6*y + x^6 - 4*x^3*y + y

So I do not know why a % b returns this.

The advice would be to avoid quo_rem and % and use only reduce.

HTH,

Guillermo

[Dima Pasechnik]

It uses the defaut order, that's why.

HTH
Dima

> The advice would be to avoid quo_rem and % and use only reduce.
>
> HTH,
>
> Guillermo
>
> On Thu, 9 Mar 2023 at 13:14, John Cremona <john.c...@gmail.com> wrote:
>>
>> Surely it is just a question of precedence of variables. In Sage you are dividing by a quadratic in y and getting a remainder which is linear in y. In pari you are dividing by a cubic in x and getting a remainder which is of degree <3 in x.
>>
>> If you swap x and y in both polynomials, sage's remainder is x^9 + x^4 + 2*x^2 + 1 as you were expecting (in y).
>>
>> John
>>
>> On Thu, 9 Mar 2023 at 11:22, Georgi Guninski <ggun...@gmail.com> wrote:
>>>
>>> Is this a bug:
>>>
>>> sage: K.<x,y>=QQ[]
>>> sage: (x^6+y^9)%(x^3-y^2-1)
>>> x^12*y - 4*x^9*y + 6*x^6*y + x^6 - 4*x^3*y + y
>>>
>>> In pari:
>>> ? (x^6+y^9)%(x^3-y^2-1)
>>> %1 = y^9 + y^4 + 2*y^2 + 1
>
>
>

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CANnG18-AEg%2BVugx_RvwOPO%2Bxc87Qynu0KPBnPzV9S2SFG2G4JA%40mail.gmail.com.

[G. M.-S.]

Could you elaborate, Dima?

It seems to me that quo_rem ignores the ordering and always uses invlex.

Would this be a bug or a feature?

Guillermo

[Dima Pasechnik]

On Thu, Mar 9, 2023 at 5:29 PM G. M.-S. <list...@gmail.com> wrote:
>
>
> Could you elaborate, Dima?
>
> It seems to me that quo_rem ignores the ordering and always uses invlex.

Sorry, I was not thinking clearly.
In fact, I think, '%' shoud work for ideals on the right-hand side,
not just for polynomials (i.e. principal ideals they generate), and
use the
monomial order of the underlying ring.

Dima

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CANnG188Fyq34TmNr%2BbEs2kHRJJfBg%3DhiTxdRpuPuLWrHwhG%2BJg%40mail.gmail.com.

[Georgi Guninski]

Many thanks for all replies.

GMS suggested to use Ideal.reduce(), but from the documentation:
"Requires computation of a Groebner basis, which can be a very
expensive operation"

I suspected that polynomial division is significantly more
cheap than groebner basis.

[Dima Pasechnik]

The Groebner basis computation for a principal ideal is very cheap - it's just selecting the leading

monomial :-)

So, no, it's essentially the same complexity here.

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAGUWgD9p-Jd7vUacWddbatMNDB9aQRvYC%3DyQDKGA0mFwXhHExQ%40mail.gmail.com.

[G. M.-S.]

Hi Georgi.

In the case of a principal ideal, to get a Gröbner basis the only thing you may need is making the generator monic, so there is almost nothing to do.

Then you do an ordered division of the other polynomial by this one, which is straightforward.

HTH,

Guillermo