5
$\begingroup$

I need to compute the Groebner basis modulus a set of prime without normalizing the Groebner basis output. Is this possible?

Example:

ideal = {8 x^2 y^2 + 5 x y^3 + 3 x^3 z + x^2 y z, 
   x^5 + 2 y^3 z^2 + 13 y^2 z^3 + 5 y z^4,
   8 x^3 + 12 y^3 + x z^2 + 3,
   7 x^2 y^4 + 18 x y^3 z^2 + y^3 z^3};
monos = {x, y, z};
GroebnerBasis[ideal,monos,Modulus->7]

I get: {z^2, 2 + y^3, x}

But I need: {z^2, 1 + 4 y^3, x}

Which is the Groebner basis of the original system since 7 is a lucky prime.

$\endgroup$
  • $\begingroup$ (1) Both are Groebner bases. (2) The one returned is what is called the "reduced" GB. (3) The last line of the input should be GroebnerBasis[ideal, monos, Modulus -> 7] (4) The fact that 7 is a lucky prime does not mean the GB mod 7 will equal the GB over Q (check definition of "lucky" in this context). $\endgroup$ – Daniel Lichtblau Jul 28 '18 at 4:30
  • $\begingroup$ I am aware that 7 being lucky does not mean that the GB mod 7 will equal the GB over Q, and in this case it does. How do I stop GB from normalizing the first term? $\endgroup$ – VulcanEconomist Jul 28 '18 at 14:35
  • $\begingroup$ There is no way to influence the algorithm in terms of avoiding the reduced form. There are ways of using the Chinese Remainder Algorithm to get a GB over Q after the fact (maybe you knew that). In this (somewhat uncommon) case only one prime would be needed. The key is then to find the right normalization. Short summary: it takes a bit of work. $\endgroup$ – Daniel Lichtblau Jul 28 '18 at 14:44
  • $\begingroup$ I am using the Chinese Remainder Algorithm and multiple primes, but does the normalization not effect the result of the Chinese Remainder Algorithm? $\endgroup$ – VulcanEconomist Jul 28 '18 at 14:52
  • $\begingroup$ Re CRA, my recollection is that one first "lifts" (via CRA) and then normalizes as a separate step (and in your example that first step is a no-op). But I confess I do not recall the details of that second step. I know I have coded it at least once in past, but I'd have to dig that up, or figure it out anew, to give anything more specific. $\endgroup$ – Daniel Lichtblau Jul 28 '18 at 14:57
4
$\begingroup$

One cannot change the way the polynomial coefficients are normalized in GroebnerBasis. To do recovery over Q when working with modulo-prime bases one can use Chinese remaindering. I will illustrate with this example. We'll use some different moduli.

ideal = {8 x^2 y^2 + 5 x y^3 + 3 x^3 z + x^2 y z, 
   x^5 + 2 y^3 z^2 + 13 y^2 z^3 + 5 y z^4, 8 x^3 + 12 y^3 + x z^2 + 3,
    7 x^2 y^4 + 18 x y^3 z^2 + y^3 z^3};
monos = {x, y, z};
gb7 = GroebnerBasis[ideal, monos, Modulus -> 7]
gb17 = GroebnerBasis[ideal, monos, Modulus -> 17]

(* Out[91]= {z^2, 2 + y^3, x}

Out[92]= {z^2, 13 + y^3, x} *)

This is an easy example of course. Only one polynomial might need any modification and that is the middle one. For that, if we normalize over Q so that the lead coefficient is 1, then only the trailing coefficient (the constant term) needs to be recovered. We see it is 2 mod 7, and 13 mod 17. CRA then tells us the value mod 7*17.

ChineseRemainder[{2, 13}, {7, 17}]

(* Out[93]= 30 *)

So now we need to find a rational corresponding to 30 mod 119 (=7*17). To do this we solve the extended gcd problem 119*x+30*y==gcd(119,30).

ExtendedGCD[7*17, 30]

(* Out[94]= {1, {-1, 4}} *)

The multipliers are (-1,4) so we see that 30*4 == 1 mod 119, or 30 = 1/4 modulo 119. This is, in a sense I will not define, the "smallest" rational equivalent to 30 mod 119. Our trailing coefficient is (possibly) 1/4 over the rationals, and the polynomial becomes y^3+1/4 (or 4*y^3+1, on clearing denominators). One can get some confirmation by checking with one more mod-prime computation.

gb29 = GroebnerBasis[ideal, monos, Modulus -> 29]

(* Out[95]= {z^2, 22 + y^3, x} *)

ChineseRemainder[{2, 13, 22}, {7, 17, 29}]

(* Out[96]= 863 *)

ExtendedGCD[7*17*29, 863]

(* Out[97]= {1, {-1, 4}} *)

So it is also 1/4 mod 7*17*29=3451. This is not exactly proof that we have recovered the right coefficient but such stability after adding a new prime modulus does give good evidence for that. If one requires proof there are ways to go about that but that's outside the intended scope of this response.

I will remark that using mod 17 or mod 29 alone is sufficient in this example.

ExtendedGCD[17, 13]
ExtendedGCD[29, 22]

(* Out[100]= {1, {-3, 4}}

Out[101]= {1, {-3, 4}} *)

Mod 7 does not quite work because there is a smaller fractional equivalent: -1/3.

ExtendedGCD[7, 2]

(* Out[102]= {1, {1, -3}} *)

Clearly the multipliers could have been {-1,4} but that slightly violates the extended GCD guarantee on multiplier sizes in the case of two input, that neither exceeds half the size of the other value. (ExtendedGCD is not documented with such a guarantee, but the methods from the literature all provide this.) So my comment that only the prime 7 is required was slightly off.

$\endgroup$
  • 1
    $\begingroup$ Exactly what I was looking for. Thank you! $\endgroup$ – VulcanEconomist Jul 28 '18 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.