We have $n$ variables $x_1, ..., x_n$ and $m$ polynomials $f_1, ..., f_m$.
The maximum degree of each variable $x_i$ in each polynomial $f_j$ is $1$.
Moreover, each variable is present in at most two of the polynomials and each polynomial contains at most 3 of the variables.
We define $F$ as the product of all the polynomials: $F=f_1*f_2*...*f_m$ .
We are interested to know whether a particular term ($x_1 x_2...x_n$) appears in $F$ or not. In other words, whether or not the coefficient of $x_1 x_2...x_n$ would be nonzero if we fully expand $F$. Is there an efficient way to check that?
Here is an example:
$f_1 = (5 x + 3 x y - z)$
$f_2 = (- x y + 2 y )$
$f_3 = (z -3)$
$F = f_1 f_2 f_3 = (5 x + 3 x y - z)(- x y + 2 y)(z -3)$
$F = -30 x y+15 x^2 y-18 x y^2+9 x^2 y^2+6 y z+7 x y z-5 x^2 y z+6 x y^2 z-3 x^2 y^2 z-2 y z^2+x y z^2$
We are interested to know whether or not the coefficient of $xyz$ is zero. In the above example, it is not zero and is equal to $7$. Is there an efficient way to do that (at least for some non-trivial special cases) which is applicable to cases with for example $n=300$ variables and $m=200$ polynomials.
Edit: this is equivalent to check whether $\alpha = \frac{\partial^n }{\partial x_1 \partial x_2 ... \partial x_n} F \bigg|_{x_1=x_2=...=x_n=0}$ is zero or not. Is there a reasonable numerical approximation method to check the derivative at the origin?
Background: Here is some background information about the origins of this problem for the interested readers:
Given any boolean function in 3 variables, we could represent it with a binary vector in an 8 dimensional space with entities equal to 1 iff the the function returns TRUE for that combination of inputs. (i.e. standard sum of products form)
We could use the following matrix to linearly map the space of the boolean functions to a new space which can be represented with polynomials in 3 variable:
The above matrix defines a reversible transformation (from boolean domain to polynomial domain) with several interesting properties, some listed below:
i) Row $X$ only depends on $x$, and is $1$ in columns with $x$ and $-1$ in columns with $x'$ (complement of $x$).
ii) Row $XY$ is the element by element product of row $X$ and row $Y$. (and only depends on $X$ and $Y$, or more specifically $x \mathbin{\oplus} y$).
iii) The inner product of each pair of rows (or columns) is zero (orthogonal).
iv) All the elements are 1 and -1 (for normalized $w$, it is $\frac{1}{\sqrt{2^n}}$ and $\frac{-1}{\sqrt{2^n}}$ where $n$ is # of variables)
v) Matrix is symmetric, so $w’=w$ and for normalized $w$, we have $w^{-1}$=$w$. (The inverse transform and forward transform only differ in a constant factor $\frac{1}{2^n}$).
vi) Any boolean function on three (or in general $n$) variables, could be represented by binary vector $u$, where $u_i$ is 1 if and only if $f$ is TRUE for the corresponding combination of inputs.
vii) Moreover, if we have two functions $f_1$ and $f_2$, $f_{12}=f_1 \land f_2$ is represented by $u_{12}=u_1 * u_2$ where, $*$ is element by element product. Then $v_{12}=w.u_{12}=w(u_1 *u_2)$. (not equal to $w u_1 * w u_2$, however you can perform regular multiplication in polynomial domain you just need to replace any $x^2$ with $1$ at the end and it will be equivalent to $\land$ in boolean domain. Note that given (iv), square of any row will be equal to row $1$)
viii) Similarly with three functions $f_{123}=f_1 \land f_2 \land f_3$, we have $u_{123}=u_1*u_2*u_3$, $v_{123}=w(u_1*u_2*u_3)$
ix) If we multiply $F$ by $X$ in polynomial domain, in boolean domain all the terms with $x$ will be multiplied by $1$ and all the terms with $x'$ will be multiplied by $-1$.
x) $F(X=0)$ in polynomial domain gives the number of solutions ($1$ elements) in boolean domain. Similarly, the coefficient for $X$ in polynomial domain is the number of solutions with $x=TRUE$ minus number of solutions with $x=FALSE$. Similarly the coefficient for $XY$ is the number of solutions with $xy$ weighted by parity (i.e. $xy$ and $x'y'$ solutions are counted with positive sign and $xy'$ and $x'y$ solutions are counted with negative sign). This is also direct consequence of i and ii.
Is there any good references for this transformation? Is it known by any names so I can look it up? Any ideas for possible applications? My motivation was that using these orthogonal bases, one could simplify some computations in the transformed domain (e.g. develop faster algorithms for solving SAT or simplify logical circuits using algebraic and non-algebraic methods).
To test if a set of boolean equations are simultaneously satisfiable, one could transform them to polynomials, expand them, replace all $x_i^2$ with $1$ and check if the remainder is absolute zero or not. To do it more efficiently, one could set $x_i$ to zero to eliminate some intermediate terms as expanding.
For example suppose $x_i$ is only present in $f_1=a x_i +b$ and $f_2 = c x_i +d$, expanding for $x_i$ and eliminating $x_i$ using the above method would yeild:
$F = f_1 f_2 f_3 ... f_m = (a x_i +b)(c x_i +d)f_3 ... f_m =(ac x_i^2 +(bc+ad) x_i +bd)f_3 ... f_m \\ \equiv (ac+bd) f_3 ... f_m$
We can then continue with eliminating other variables. After eliminating all the variables, the remainder would give the total number of solutions that would satisfy all the equations simultaneously. Is there an efficient way to get the solution for some subset of cases without the need for exponential calculations ?
Here is the proof of the complexity. I am still interested in suggestions for different creative approaches to solve the problem (even partial solutions) and/or ideas or references for other possible applications.
To give a brief proof, I will reduce a problem that was previously posted here and answered by Yuval Filmus to this new problem.
The first step is a simple change of variable: $X' = 2X-1$ that is applied to all input variables. So that the inputs are now defined over $\left \{ -1,1 \right \}$ instead of $\left \{ 0,1 \right \}$. Hence now we have $X'^2=1$ instead of $X^2=X$. Alternatively one could directly use the transformation described in the problem to get the polynomials. For 3SAT problem, we only need the polynomial transformation for the following three functions:
\begin{matrix} \text{Gate Name} & \text{Boolean} & \text{Polynomial} \\ XOR (y=\neg{x})& xy'+x'y& 1-XY\\ AllOrNone (x=y=z)& xyz+x'y'z' &1+XY+XZ+YZ\\ atLeastOne (x\lor y \lor z)& (x'y'z')' &7+ X + Y + Z -XY-XZ-YZ+ XYZ \end{matrix}
The second step is multiplying $F$ by $X_1 X_2 ... X_n$. This will shift all the powers by one and convert $F = a X^2 + b X + c$ to $F = a X^3 + b X^2 + c X \equiv (a+c) X + b$. It would not be hard to show that $a+c$ is indeed the total number of solutions ($F(X=1)$ is number of solutions with $x$ and $F(X=-1)$ is number of solutions with $\neg{x}$) and would be zero if and only if the original set of equations are not satisfiable. Note that in practice, for each variable $X_i$, we pick one polynomial (clause) with $X_i$, multiply it by $X_i$ and convert $X_i^2$ to $1$ for that clause. This will reduce the 3SAT problem to the problem described in this question. In above calculations, I used multiplication by a constant for simplification, but that does not affect the results.
EDIT:
Here is a numerical approach:
Let $\alpha$ be the coefficient for $x_1 x_2 ... x_n$ in $F=f_1 f_2 ... f_m$. We have:
$\alpha = \frac{\partial^n }{\partial x_1 \partial x_2 ... \partial x_n} F \bigg|_{x_1=x_2=...=x_n=0}$
Is there a way to estimate $\alpha$ numerically (maybe using some random algorithm) and check if it is zero or not? For example if we assign small random values to $x_1,x_2, ..., x_n$ and calculate $F$, do we really need exponential different measurements to be able to approximate the derivative at origin ?
Another related approach would be to come up with a system of equations that could be numerically solved. For a subset of polynomial this seems to be feasible. (e.g. see here).