System of quadratic equations over field of size 2

Question

I am working on system of quadratic equations.

\begin{cases} (\alpha_1^1x_1+\ldots+\alpha_n^1x_n)(\beta_1^1y_1+\ldots+\beta_m^1y_m)=0\\ \ldots \\ (\alpha_1^kx_1+\ldots+\alpha_n^kx_n)(\beta_1^ky_1+\ldots+\beta_m^ky_m)=0\\ \end{cases}

where $\alpha_i^j$ and $\beta_i^j$ are constants in $\mathbb F_2=\{0,1\}$ and $x_i,y_j$ are unknowns in $\mathbb F_2$.

I need help on these problems:

1) If I get another equation of same form $(\alpha_1^0x_1+\ldots+\alpha_n^0x_n)(\beta_1^0y_1+\ldots+\beta_m^0y_m)=0$, how can I check that if I add it to the system it will change number of solutions. If the equations were linear I can check if it is linearly dependent from vectors in the system. But for quadratic case I have no idea how to do it.

2) What is minimal number of equations one must choose so that the solution of system is trivial. By trivial solution I mean all vectors that first $n$ or last $m$ coordinates are 0. For linear case again it is well known that if number of variables is $n$, one should choose at lease $n$ equations to get only trivial solution.

Update:

I understood that in order to have only trivial solution one must choose at least $n+m-1$ equations and for $n=m=2$ I found a system with $3$ equation which doesn't have nontrivial solutions.

\begin{cases} x_1y_1=0\\ x_2y_2=0\\ (x_1+x_2)(y_1+y_2)=0\\ \end{cases}

But $n+m-1$ bound is not tight. For $n=3$ and $m=2$ I have found only $5$ equation system. Solution with $4$ equations doesn't exist.

Finding exact number of equations for general case is hard problem so I am trying to find it only for the case $m=2$.

Looks like a system with $\lceil \frac{3n}{2}\rceil$ equation is enough but I can's show that solution with lower number of equations doesn't exist. I am giving bounty to anyone who can help on that problem.

Answer 1

Let $K=\mathbb{F}_2$. There are $2^n+2^m-1$ trivial solutions ($(X,0)$ or $(0,Y)$). We consider the non-trivial solutions. Let $f:K^n\rightarrow K$ be random linear and $f_1$ be its restriction to $K^n\setminus\{0\}$. We assume that $X,Y$ are random. Then $prob(f(X)=1)=\dfrac{2^{n-1}}{2^n-1}\approx 1/2$ when $n$ is great enough. Note that each of our $k$ equation has the form $f_1(X)g_1(Y)=0$; thus $prob(f_1(X)g_1(Y)=0)\approx 3/4$. Here the total equation is $F=0$ where $F:K^{n}\setminus\{0\}\times K^{m}\setminus\{0\}\rightarrow K^k$. If $Z$ is the random variable "number of non-trivial solutions", then the average of $Z$ is $E(Z)\approx(\dfrac{3}{4})^k2^{n+m}$. Finally $E(Z)=1$ when $k=\dfrac{\ln(2)}{\ln(4/3)}(n+m)\approx 2.4094(n+m)$.

There are several methods for solving $F(X,Y)=0$.

1 The brute force one. Test all possible value of $X,Y$; its complexity is $2^{m+n}(m+n)k$.

2. The decomposition in subsets of $S=\{1,\cdots,k\}$; if $T\subset S$, then assume $ f_i(X)=0$ when $i\in T$ and $g_j(X)=0$ when $j\notin T$. Its complexity is in $O(2^k (\inf(k^3,n^3)+kn)(\inf(k^3,m^3)+km))$.

3. Calculate a Grobner basis. Let $k=\lambda (n+m)$. When $\lambda \approx 2.4094$, the complexity is in $O(2^{n+m})$; when $k$ increases, the complexity quickly decreases.

Conclusion: when $\lambda<1$ use 2. When $1<\lambda<3$ use 1. When $\lambda>3$ use 3.

Anyway it seems that this problem is NP. It is known that to solve a system of equations of degree $2$ in $K$ is a NP problem (in the numbers of equations and unknowns).

Answer 2

It helps to think geometrically. Each of your quadratic equations is a product of two linear factors. The set of solutions to a linear equation is a hyperplane (a subspace of dimension one less than the entire vector space). So the solution to each of your quadratic equations is a union of two hyperplanes, and the solution to your system of equations is the intersection of all of these. Digging a little deeper, your vector space $V = U \oplus W$, where $U = \langle x_{1}, \ldots, x_{n}\rangle$ and $W = \langle y_{1}, \ldots, y_{m} \rangle$. The solution to each of your quadratic equations is a union of two hyperplanes, one containing $U$ and the other containing $W$.

In general, for systems of quadratic equations, there is not really a nice way to determine if adding a new equation will decrease the number of solutions (such as testing linear independence). If you know the solution set for the previous equations, then test if this solution set is completely contained in the solution set for the new equation. Once you are no longer dealing with linear equations, things become much less nice. But there might be something that takes advantage of the fact that all of your equations are decomposable into linear factors that makes this easier.

The minimum number of equations you will need to guarantee there are no solutions is $m+n-1$. You can represent any vector $v \in V$ as $v = u+w$, where $u \in U$ and $w \in W$. Then if $u$ satisfies the first part of every equation or if $w$ satisfies the second part of every equation (note these are all linear), then $v$ satisfies every equation. So if you have for example $m+n-2$ equations, you can be guaranteed to find a nonzero $u$ satisfying the first $m-1$ left hand linear equations, and a nonzero $w$ satisfying the remaining $n-1$ right hand linear equations. Then $v = u+w$ will satisfy all of the quadratics. However, with $m+n-1$ equations it should be possible to have every subset of $m$ equations having no nontrivial solution in the left hand side, and every subset of $n$ equations having no nontrivial solution in the right hand side. Then there will be a non nontrivial solution to the system of quadratics.