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

[Georgi Guninski]

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)=0$ 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?

[Dima Pasechnik]

On 31 January 2024 16:42:39 GMT, Georgi Guninski <ggun...@gmail.com> wrote:
>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)=0$ for constant $a_i,b_i,a_j,b_j$.

Do you have exactly one (or at most) relation for any pair of variables? Can one have i=j ?

Or it's the notation which should be improved?

[Georgi Guninski]

On Wed, Jan 31, 2024 at 10:54 PM Dima Pasechnik <dim...@gmail.com> wrote:
>
> Do you have exactly one (or at most) relation for any pair of variables? Can one have i=j ?
>
> Or it's the notation which should be improved?
>

The number of relations for a pair of variables can be arbitrary.
i=j appears irrelevant, choose it as you want.

[Dima Pasechnik]

On Thu, Feb 1, 2024 at 5:04 AM Georgi Guninski <ggun...@gmail.com> wrote:
>
> On Wed, Jan 31, 2024 at 10:54 PM Dima Pasechnik <dim...@gmail.com> wrote:
> >
> > Do you have exactly one (or at most) relation for any pair of variables? Can one have i=j ?
> >
> > Or it's the notation which should be improved?
> >
>
> The number of relations for a pair of variables can be arbitrary.

it's indeed easy to show that a degree-lex Groebner basis
will be very small, and only contain terns of degee at most 2.

Indeed, S-polynomials you'd get will get its cubic terms reduced.
Let us look at the pairs of variables present in your relation, and
the connected components of the graph specified by these pairs. For an
S-polynomial not to vanish, its leading terms must not be relatively
prime, and so at the 1st step you'll compute the S-polynomial of, say,
(Ax+B)(Cy+D)=ACxy+ADx+BCy+BD and (Ex+F)(Gz+H) - i.e. have 3 variables
involved: x,y,z.
(suppose we don't have a relation with yz term)

EGz(Ax+B)(Cy+D) - ACy(Ex+F)(Gz+H)=
EGADxz + EGBCyz + EGBDz - ACFGyz - ACEHxy - ACFHy = ayz + bx + cy +dz.
So we still get just one quadratic term (could be 0), and some more
linear terms after reductions.
(it's important that for each pair of variables in the linear term
there is a relation with a quadratic term
involving this pair).

It seems that this is basically all that's needed (probably it's
something well-known).

HTH
Dima

> i=j appears irrelevant, choose it as you want.
>

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAGUWgD9AtK43yGeasyiDkyBOvQ_%3DV1Yx930N3%3DPHZ7g723o42g%40mail.gmail.com.

[Georgi Guninski]

Thanks. This was asked on mathoverflow [1], you can win some points
if you paste it as an answer.

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

[1]: https://mathoverflow.net/questions/463159/efficiency-of-groebner-basis-for-constraints-of-the-form-a-i-x-ib-ia-j-x-j