# Using a Groebner Basis to show Bijectivity

I have a set of n polynomials over n variables, like

{a3 (a2 + a3) + a4,
a3 + a1 (a2 + 2 a3),
a1 + a1^2 + a2 + 2 a3,
1 + 2 a1}


Let's call them {c4, c3, c2, c1}.

I would like to show that the mapping P(a1,a2,...) = (..., c2, c1) : F^n -> F^n is a bijection over any field of characteristic big enough. In other words, if I vary the variables over the field, F, the set of polynomials should give each value of F^n exactly once.

In the example, this is indeed the case since I can recover a1=(c1-1)/2, a3 = c3 - a1 c2 + a1 + a1^2 and so on. (Though if the characteristic had been 2, we couldn't have been able to recover a1.)

I can do Reduce[{polys...} == {c1,c2,...}, {a1,a2,...}], which works in the small case above, but in general takes forever. I think I should be able to do faster, since I don't really care how to recover each ai from the cis, just that there is some unique way.

From what I've read, computing a GroebnerBasis should be useful for problems like this. If I compute it on the polynomials given, I get

{1 + 64 a4, -1 + 8 a3, a2, 1 + 2 a1}


which seems very nice. However, I have no idea what I'm doing and what this actually shows.

Is there a fast way to check whether a set of polynomials is a bijection in Mathematica? Possibly using a GroebnerBasis?

## 1 Answer

It's slightly more complicated I think. You have to be able to solve for c1...c4 but also you need to show the injectivity and surjectivity of these maps. I will ignore the possibility of finite fields though it does seem that all this will hold outside of characteristic 2.

polys = {c1, c2, c3, c4} - {a3 (a2 + a3) + a4, a3 + a1 (a2 + 2 a3),
a1 + a1^2 + a2 + 2 a3, 1 + 2 a1};
soln = {a1, a2, a3, a4} /. Solve[polys == 0, {a1, a2, a3, a4}]

(* Out[163]= {{1/2 (-1 + c4), 1/4 (-8 c2 + c4 + 4 c3 c4 - c4^3),
1/8 (1 + 8 c2 + 4 c3 - c4 - 4 c3 c4 - c4^2 + c4^3),
1/64 (-1 + 64 c1 + 64 c2^2 - 8 c3 - 16 c3^2 - 16 c2 c4 -
64 c2 c3 c4 + 3 c4^2 + 16 c3 c4^2 + 16 c3^2 c4^2 + 16 c2 c4^3 -
3 c4^4 - 8 c3 c4^4 + c4^6)}} *)


To show the solutions are generically unique, try finding different values that give the same solutions.

s2 = soln /. Thread[{c1, c2, c3, c4} -> {b1, b2, b3, b4}];
Solve[soln == s2, {c1, c2, c3, c4}]

(* {{c1 -> b1, c2 -> b2, c3 -> b3, c4 -> b4}} *)


Can there be special value for which a solution is repeated? In order for that to happen there would need to be a vanishing Jacobian determinant.

jac = Det@Grad[soln[[1]], {c1, c2, c3, c4}]

(* Out[170]= 1/2 *)


So we have injectivity. Reversing roles of the c variables with the a variables will give surjectivity.

• Solve is indeed a lot faster than Reduce? is that because it just has to find some solution, and not necessarily all of them? It's still not as fast as GroebnerBasis, and everywhere I look it seems like that should be used to understand polynomial systems? Apr 22 at 12:36
• Solve for nonlinear polynomial systems will use GroebnerBasis. I used Solve here because part of the question involved showing one can solve for each set of variables in terms of the other. Apr 22 at 16:33