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?
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.
