I have a multivariate polynomial $P$ which is a product of $M$ low degree polynomials $p\_i$


$$P(x\_1, x\_2, \dotsc, x\_n) = \prod\_{i=1}^M p\_i(x\_1, x\_2, \dotsc, x\_n)$$


where the maximum degree of each $p\_i$ can be $4$. For example:


$$P(x\_1, x\_2, x\_3) = (1+x\_1x\_2^2x\_3)(x\_3^3+x\_1x\_2^3).$$


I need to find out whether a specific term $x\_1^{m\_1}x\_2^{m\_2}\dotsm x\_n^{m\_n}$ appears in $P$ or not. Can I find the answer without expanding the products explicitly?



Checking presence of a specific term in product polynomial
You can solve the problem via integer linear programming as follows.
Let $a\_{ijk}$ be the power of $x\_j$ in term $k$ of $p\_i$, that is, $p\_i = \sum\_k \prod\_j x\_j^{a\_{ijk}}$. Let binary decision variable $y\_{ik}$ indicate whether term $k$ of $p\_i$ is used to form the target term $\prod\_j x\_j^{m\_j}$. The target is attainable if and only if the following linear system is feasible:
\begin{align}
\sum\_k y\_{ik} &= 1 &&\text{for $i\in\{1,\dotsc,M\}$} \tag1\label1 \\
\sum\_{i,k} a\_{ijk} y\_{ik} &= m\_j &&\text{for $j\in\{1,\dotsc,n\}$} \tag2\label2
\end{align}
Constraint \eqref{1} selects exactly one term in each $p\_i$.
Constraint \eqref{2} forces the product of the selected terms to match the desired powers.


Note that this formulation works even if the powers $a\_{ijk}$ and $m\_j$ are not nonnegative integers.


