Bug in Magma's Groebner() command
Dave Rusin
This post is both a bug-report/request-for-workaround and a
mathematical query: what ring-theoretic conditions caused this error?
The problem arose when computing Groebner bases for ideals in mod-p polynomial
rings. I do this all the time and never noticed an error before. An error
of this type would make a terrible mess of the computations I do!
The computation I was doing involved a complicated ideal in
Z[x1, ..., x10]. (It's described in another post I'll make today.)
I did computations mod-p for well over 100 large primes p, and all the
results combined very nicely, until I went to test my results on a few
additional primes. They also worked as I expected except for one prime.
I managed to recreate the error in a long sequence of incrementally-simpler
problems, and now I can give a simple instance of it:
Consider the ideal in GF(35098201)[x,y] generated by
y + (1 + x^5 + x^10) and x^34 + 1 .
What is the intersection of this ideal with the subring GF(35098201)[y] ?
(Think algebro-geometrically: these equations define 34 points in a plane
over an algebraic closure of GF(p); I want the y-coordinates. Note that
for this prime, p-1 is a multiple of 68, so all the roots of x^34+1
are in the ground field, so the values of y should be as well.)
There are two useful ways to compute this in Magma. The way I have phrased
the problem, it is natural to use EliminationIdeal(). This gives an
answer which I believe is correct: the ideal is the principal ideal
generated by
y^34 + 34*y^33 + 561*y^32 + 5984*y^31 + 46376*y^30 + 278256*y^29 +
1344904*y^28 + 5379616*y^27 + 18156204*y^26 + 17353055*y^25 +
25833537*y^24 + 5312152*y^23 + 21881025*y^22 + 15430534*y^21 +
23145801*y^20 + 30861068*y^19 + 27872968*y^18 + 17124952*y^17 +
27873223*y^16 + 30858484*y^15 + 23140973*y^14 + 15452362*y^13 +
21951303*y^12 + 5362540*y^11 + 25762851*y^10 + 17183633*y^9 +
18014271*y^8 + 5332492*y^7 + 1357246*y^6 + 297330*y^5 + 54791*y^4 +
7854*y^3 + 748*y^2 + 34*y + 1
This does indeed split into linear factors over GF(p).
The other way I would compute this is to ask Magma for a Groebner Basis
for the ideal: Magma tells me the original ideal is generated by by two
elements:
x + 33784728*y^33 + 15744019*y^32 + 14466235*y^31 + 14937582*y^30 +
9988153*y^29 + 24849537*y^28 + 13827463*y^27 + 10851940*y^26 +
25333828*y^25 + 29238403*y^24 + 35087366*y^23 + 3185785*y^22 +
12125255*y^21 + 11305600*y^20 + 713800*y^19 + 11882241*y^18 +
23388419*y^17 + 12677392*y^16 + 20159861*y^15 + 31143912*y^14 +
33062327*y^13 + 11580434*y^12 + 10629964*y^11 + 14094725*y^10 +
30606411*y^9 + 20913610*y^8 + 23355486*y^7 + 32139384*y^6 + 35026862*y^5
+ 11038274*y^4 + 26690476*y^3 + 752845*y^2 + 9514380*y + 16409093,
y^34 + 34*y^33 + 561*y^32 + 5984*y^31 + 46376*y^30 + 278256*y^29 +
1344904*y^28 + 5379616*y^27 + 18156204*y^26 + 17353055*y^25 +
25833537*y^24 + 5312152*y^23 + 21881025*y^22 + 15430534*y^21 +
23145801*y^20 + 30861068*y^19 + 27872968*y^18 + 17124952*y^17 +
27873223*y^16 + 30858484*y^15 + 23140973*y^14 + 15452362*y^13 +
21951303*y^12 + 5362540*y^11 + 25762851*y^10 + 17184126*y^9 +
18014271*y^8 + 5332492*y^7 + 1358334*y^6 + 297330*y^5 + 54824*y^4 +
7259*y^3 + 714*y^2 + 34*y + 1
(That last polynomial exceeds the other polynomial-in-y by
493*y^9 + 1088*y^6 + 33*y^4 - 595*y^3 - 34*y^2 .)
This answer has the expected form, and the second generator is indeed in the
subring. But the answer is definitely wrong. These two polynomials vanish
when x = 6351916 and y = 2018917, but neither of the original polynomials
vanish there. And this polynomial in y doesn't even split into linear
factors over GF(p). (Indeed, 2018917 is its _only_ root in the base field.)
As I said, it's not hard to generate plenty of examples where Magma makes
errors. In keeping with how Groebner bases are computed, this usually
requires just changing some lower-order terms. For example if we replace
my two polynomials with y + (1+x^7+x^10) , x^34 + x^16 + 1 then the
different Magma commands give two polynomials-in-y which have almost no
coefficients in common. On the other hand, tinkering is only successful
after first stumbling on an ideal that Magma messes up in the first place.
A search for small examples as above (using pairs of trinomials in x )
takes a little while for some primes p and never gave me any examples
at all for other primes p.
So now here are my questions.
1. Has this problem been noticed before? More importantly, has it been
fixed? (I ran these examples with Magma V2.10-14 which I know is not
the most recent version.) In my tests it _seemed_ like EliminationIdeal()
is giving correct answers, but maybe this is also an illusion; has anyone
compared the algorithms and found this one to be more dependable than
Groebner() (or GroebnerBasis(), which appears to work the same here)?
It also seemed like Groebner() worked flawlessly in characteristic-0 rings;
well, has that also been found buggy?
Groebner bases are kind of an important ingredient in computational
commutative algebra; I really hope someone has been working on this code...
2. I began this exercise with an integral ideal in many variables
(hoping to compute its rational Groebner basis via the Chinese Remainder
Theorem). The GB computations I did for all other primes appeared to be
consistent with a rational Groebner Basis. So what is different about
this one prime? That is, what is a numerical invariant which can be computed
for a zero-dimensional ideal defined over Z (or Q ) with the property
that Magma's algorithm for mod-p Groebner basis computations will work for
all primes p except those dividing this invariant? In the example I
gave above, the cardinality of complex points divides p-1, but that
is not the case for other examples where the error occurs. Is there
another good candidate? If some modular results seem incompatible with
each other, how could one flag some primes as more likely to be suspect?
dave
ma...@mimosa.csv.warwick.ac.uk
ru...@vesuvius.math.niu.edu (Dave Rusin) writes:
>I would like to ask about an error I just encountered in Magma.
>This post is both a bug-report/request-for-workaround and a
>mathematical query: what ring-theoretic conditions caused this error?
I am a regular Magma user, but I don't know enough about Groebner bases
to be able to help with your problem. Wouldn't you do better to contact
the Magma development team about it? I believe that they devote a lot
of effort to Groebner bases, so they would certianly be interesed in
bugs. There is also a Magma users mailing list to which you could
subscribe. It might be wise to try your calculation with the latest
version, which is 2.12.
Derek Holt.
Dave Rusin
<ma...@mimosa.csv.warwick.ac.uk> wrote:
>In article <dmc1rp$3r$1...@news.math.niu.edu>,
> ru...@vesuvius.math.niu.edu (Dave Rusin) writes:
>>I would like to ask about an error I just encountered in Magma.
>>This post is both a bug-report/request-for-workaround and a
>>mathematical query: what ring-theoretic conditions caused this error?
>It might be wise to try your calculation with the latest
>version, which is 2.12.
I tried the online version of Magma at
http://modular.ucsd.edu/cgi-bin/calc/calc.py
They are running Magma V2.11-10 . Their output has the same error I found.
(Try it! Just enter these two lines:)
Q:=GaloisField(35098201); P<x,y>:=PolynomialRing(Q,2);
I:=ideal<P| y + (1+x^5+x^10), x^34 +1 >; Groebner(I); I;
I have also reported the error to the Magma folks. I just wondered if
anyone here knew of any similar problems or, better, solutions.
dave
Roman Pearce
the bug is in FGLM, and you can get around it by using the Groebner
walk instead. It's a bit slower, but still very good.
Instead of Groebner(I); use Groebner(I: Al:="Walk");
Keep in mind that you only want to do this when your ring has
lexicographic or an elimination order (the default is lexicographic).
If you are using grevlex order, ie: PolynomialRing(Q, 2, "grevlex");
then you should stick with the default F4 or Buchberger algorithm
(depending on the coefficient field).
Magma
repost:
In article <dmc1rp$3r$1...@news.math.niu.edu>,
Dave Rusin <ru...@vesuvius.math.niu.edu> wrote:
> I would like to ask about an error I just encountered in Magma.
> This post is both a bug-report/request-for-workaround and a
> mathematical query: what ring-theoretic conditions caused this error?
Thank you for reporting the problem encountered in Magma. Indeed, it
is a bug which only occurs when a Groebner Basis function is invoked
on an ideal in a polynomial ring with field of coefficients GF(p),
where p lies between 2^23.5 and 2^26.
The bug has now been fixed and a patch version (V2.12-17) containing
the fix is now available on the Magma download page.
Note that there is a mailing address for reporting bugs to Magma:
Directly reporting bugs frees up bandwidth on discussion groups and
ensures that they are seen by the people who fix them.
All bugs are assessed within 24 hours and the majority are fixed within
7 days.
--
Magma Computer Algebra System
Email: ma...@maths.usyd.edu.au
Web: http://magma.maths.usyd.edu.au/
Phone: +61 2 9351 3338 Fax: +61 2 9351 4534