Quotient of polynomial rings

[Florent Hivert]

Dear all,

I've juste created #13999 which deal with Ideal membership for univariate
polynomial.

sage: R.<x> = PolynomialRing(ZZ)
sage: p, q = 4 + 3*x + x^2, 1 + x^2
sage: I = R.ideal([p, q])
sage: S = R.quotient_ring(I)
sage: S(p) == S(0)
False

I can probably fix the problem when the coefficient ring is a field but I
don't know how to compute when it's a general ring (Hermite normal form,
grobner basis or no known algorithm ???). Does anyone with the necessary
mathematical and technical knowledge is willing to fix the problem, and fixing
by the way the trivial field case ?

Cheers,

Florent

[Maarten Derickx]

From the theoretical side it should at least be possible to use a groebner basis to solve this problem. The only problem is that sage doesn't do groebner basis for univariate polynomial rings. It does however do groebner basis for multivariate polynomial rings (even if the multivariate polynomial ring only has 1 variable). This explains why the following gives the correct answer:

sage: R.<x> = PolynomialRing(ZZ,1)

sage: type(R)

<type 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomialRing_libsingular'>

sage: p, q = 4 + 3*x + x^2, 1 + x^2 

sage: I = R.ideal([p, q]) 

sage: S = R.quotient_ring(I) 

sage: S(p) == S(0) 

True

I don't know wether something smarter then groebner basis can be done in the univariate over ZZ case. But at least this shows that the code to give the right answer is already in sage, but it's not getting called for some reason.

I don't know what you mean by the "trivial field case" but at least over fields your example seems to work:

sage: R.<x> = PolynomialRing(QQ)

sage: type(R)

<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_field_with_category'>

sage: p, q = 4 + 3*x + x^2, 1 + x^2 

sage: I = R.ideal([p, q]) 

sage: S = R.quotient_ring(I) 

sage: S(p) == S(0) 

True

I guess the above works because  in the above R is a euclidean domain, and hence gets dealt with differently then PolynomialRing(ZZ). 

[Volker Braun]

The weakness of the univariate polynomial ring implementation bugs me more often than not. IMHO we should make the default univariate polynomial ring just a libSingular polynomial ring that happens to have only one variable. In terms of end-user features and consistency with multivariate polynomial rings thats just much easier. There is definitely a place for alternate implementations (NTL, Flint, PolynomialRealDense) but anything that doesn't implement groebner_basis, say, shouldn't be presented as the default to the unsuspecting user.

[David Roe]

We should certainly add groebner basis facility for univariate polynomials, but there are good reasons that we use NTL and/or FLINT.  For example:
sage: R.<x> = ZZ[]
sage: S.<y> = PolynomialRing(ZZ,1)

sage: g1 = S.random_element(degree=5000,terms=5000)
sage: g2 = S.random_element(degree=5000,terms=5000)
sage: timeit("g = g1*g2",number=1,repeat=1)
1 loops, best of 1: 8.16 s per loop

sage: f1 = R.random_element(degree=5000)
sage: f2 = R.random_element(degree=5000)
sage: timeit("f = f1*f2")
125 loops, best of 3: 2.04 ms per loop

David

--