# Checking presence of a specific term in product polynomial

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?

• I'm about 75% sure you can encode SAT in this and that this is therefore NP-hard. Commented Jun 8, 2022 at 19:40
• You can skip any terms that contain some $x_j$ with a power that exceeds $m_j$. Commented Jun 8, 2022 at 20:30
• More generally there's an obvious strategy where you expand but throw away terms that are too big as you go Commented Jun 8, 2022 at 20:35

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.