Efficiency of Groebner basis for constraints of the form $(a_i x_i+b_i)(a_j x_j+b_j)$

Question

This is based on numerical experiments in sage.

Let $K$ be a ring and define the ideal where each polynomial is of the form $(a_i x_i+b_i)(a_j x_j+b_j)$ for constant $a_i,b_i,a_j,b_j$.

Q1 Is it true that for constraints of this form the groebner basis is efficiently computable?

By "efficiently" we mean polynomial in the number of variables and wall clock time of seconds for say 100 variables and if we a add single constraint of other form the running time degrades.

For $K=\mathbb{F}_2$ this is equivalent to 2-SAT, which is efficiently solvable.

We believe that adding one more linear factor, $(a_k x_k+b_k)$ will be NP-complete.

Q2 Why adding the factor brings hardness?

---

I asked on the sage-devel mailing list and Dima Pasechnik solved it.

Adding a single linear equation break the efficiency, so this solution appear to show that incremental groebner basis might be large.

Answer 1

Let $I\subset\mathbb{Q}[x_1,\dots,x_n]$ be an ideal generated by polynomials of the form $x_i x_j + a_{ij}x_i + b_{ij}x_j + c_{ij}$, with $i<j$. (We don't require that all of these are present).

Equip our ring with a degree-lexicographic order (or a similar order - all we need is that monomials are ordered 1st of all by degree).

We claim that a Groebner basis of $I$ doesn't have elements of degree bigger than 2.

With such a set of generators one associates a graph $\Gamma$ on the nodes $1,\dots,n$, two nodes $i$, $j$ adjacent if there is a generator with the leading monomial $x_i x_j$. Recalling that the S-polynomial of two polynomials with relatively prime leading terms reduces to 0, we can assume w.l.o.g. that $\Gamma$ is connected. Thus there is a pair of generators $xy+ax+by+c$ and $yz+dy+ez+f$, with $x,y,z\in\{x_1,\dots,x_n\}$. Their S-polynomial is $z(xy+ax+by+c)-x(yz+dy+ez+f)=axz+byz+cz-dxy-exz-fx= (a-e)xz-b(dy+ez+f)+d(ax+by+c)+cz-fx=(a-e)xz+(ad-f)x+(c-be)z+cd-bf$. Thus, it gives, by dividing by $a-e$, another generator of the form $xz+Ax+Bz+C$, or, if either $a=e$, or if there is a generator with the leading monomial $xz$, a linear generator $A'x+B'z+C'$. This argument shows that S-polynomials involving quadratic generators only give quadratic generators, or linear generators (each having at most two variables).

Now we should deal with the case of the S-polynomial of generators of the shape $xy+ax+by+c$ and $y+ez+f$, which is $-exz+(a-f)x+by+c=-exz+(a-f)x-bez-bf+c$ - again the shape as before.

Finally, if we have two linear generators with at most 2 variables each, their S-polynomial is again linear and with at most two variables. QED.

---

Probably all this is well-known, but I have not seen this in the literature.