Let $c_0,\dots,c_k$ be some known nonnegative integers.

Consider the following system of equations in the unknown bits $a_i,b_i$, i.e. $a_i,b_i\in \{0,1\}$:

$$ \left\{\begin{array}{l} a_0b_0& =& c_0,\\ a_0b_1+a_1b_0& =& c_1,\\ a_0b_2+a_1b_1+a_2b_0& =& c_2,\\ \vdots && \\ \sum_{i+j=k}a_ib_j &=& c_k \\ \end{array}\right.$$

I am looking for an upper bound of the number of solutions of this equation. For instance, if $k=0$, there are at most $2$ solutions (achieved when $c_0\leq 1$).

In addition, I would like to restrict the solutions to a subspace and count the number of solutions there (for instance, restricting $\sum_{i=0}^ka_k=k/4$).

I know there are some nice interpretations with lattices, as in Coppersmith method, but I don't know if that applies here. Any reference or direction will be appreciated.

  • $\begingroup$ To solve the problem - it is always necessary to simplify it. In this case, exclude some linear equations, for example. If we solve this equation directly. We come to the need to solve an algebraic equation of degree $2^{2k}$. It is always better to consider the solution on some particular case. $\endgroup$ – individ Sep 14 '18 at 5:02
  • $\begingroup$ I don't understand. If $k=0$ and $c_0=0$, there are three solutions: $(a_0,b_0)\in \{(0,0),(1,0),(0,1)\}=0$. Am I right? $\endgroup$ – san Sep 20 '18 at 4:39
  • $\begingroup$ Let me get this straight, $c_i$ are all constants, and we do not know their value. We have to find the maximum number of possible solutions of {$a_i,b_i$} which can satisfy the equations. And could you explain your restriction? $\endgroup$ – Haran Sep 20 '18 at 9:44
  • $\begingroup$ @Haran As the first sentence reads, $c_i$ are known (constant) integers. This is a quadratic system on variables $a_i, b_j$, where each $a_i$ and $b_j$ are binary (i.e. $a_i\in \mathbb{F}_2$, or if you prefer, add the field equation $a_i^2=a_i$). I only want to have an estimate on the number of solutions (this estimate depends on the $c_i's$, of course. For instance if $c_0=2$ there is no solution. Also, if possible, I wanted to add an additional (linear) equation on the $a_i$'s and $b_j$'s. This problem is related to cryptography. $\endgroup$ – Tal-Botvinnik Sep 20 '18 at 19:44
  • $\begingroup$ Yes @san. Now, I would like to do the same for any $k$ and $c_0$. Note that if for any $i$ it holds that $c_i>i+1$, then there are no solutions. Also I do not want to compute the actual solutions, just know how many are there, or at least a reasonable bound. $\endgroup$ – Tal-Botvinnik Sep 20 '18 at 20:37

Your Answer

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

Browse other questions tagged or ask your own question.