Polynomial products with term of even degree x being non-zero is in NP

[CGandC]

Homework Statement

Problem: Define language $L$ s.t. a sequence of natural numbers ( zero included ) $(t,a_1,b_1,k_1, \ldots , a_m ,b_m ,k_m )$ is in $L$ if and only if the coefficient of $x^{2t}$ in the expansion of $p(x)=\left(a_1+b_1 x^{k_1}\right)\left(a_2+b_2 x^{k_2}\right) \cdots\left(a_m+b_m x^{k_m}\right)$ is non-zero. ( in other words, $p(x)=\sum_{i=0}^d c_i x^i$ for integer coefficients $d \geq 2 t, c_0, \ldots, c_d$, and $c_{2 t} \neq 0$).

Prove $L \in NP$.

Relevant Equations

Every language in NP has polynomial verifier and vice-versa.

Attempt: We'll define a polynomial verifier such that for input $\left\langle\left(t, a_1, b_1, k_1, \ldots, a_m, b_m, k_m\right), I\right\rangle$ it accepts if and only if $I$ is an encoding of a set $I \subseteq \{ 1 , \ldots , m \}$ such that $\sum_{i \in I} k_i=2 t$ [ I don't know how to continue from here ]

How do I continue the verifier construction? I don't see what conditions ( which involve the coefficients $b_i , a_i , i\in I$ ) one can check on the witness $I$ in order to create a correct verifier, any ideas?

 

[pasmith]

Define $M = \{1, \dots, m\}$ for convenience. Do we not have $$\prod_{i \in M}(a_i + b_ix^{k_i}) = \sum_{I \in 2^{M}} \left(\prod_{i\in M \setminus I} a_i\right)\left( \prod_{i \in I}b_i\right) x^{\sum_{i \in I} k_i }$$ by taking the $a_i$ term from bracket $i$ if $i \in M \setminus I$ and the $b_ix^{k_i}$ term if $i \in I$?

 

[CGandC]

Define $M = \{1, \dots, m\}$ for convenience. Do we not have $$\prod_{i \in M}(a_i + b_ix^{k_i}) = \sum_{I \in 2^{M}} \left(\prod_{i\in M \setminus I} a_i\right)\left( \prod_{i \in I}b_i\right) x^{\sum_{i \in I} k_i }$$ by taking the $a_i$ term from bracket $i$ if $i \in M \setminus I$ and the $b_ix^{k_i}$ term if $i \in I$?

So we must have $\forall i\in I. b_i \neq 0$ and $\forall i \notin I. a_i \neq 0$ , thanks for your help!!

 

[CGandC]

By the way ( I'm curious ), how did you come up with this sum? at first I looked at the formula for multiplying two polynomials https://en.wikipedia.org/wiki/Polynomial_ring#Generalized_exponents but couldn't find any similarity for taking $m$ polynomial products

 

[pasmith]

The notation for more than two polynomial factors is less straightforward, but the product of $n$ polynomials of degrees $n_i \geq 0$ can be written as $$\begin{split} P(x) &= \prod_{i=1}^n \left(\sum_{j=0}^{n_i} a_{ij}x^{j}\right) \\ &= \left(\sum_{j_1=0}^{n_1} a_{1j_1}x^{j_1}\right) \cdots \left( \sum_{j_n=0}^{n_n} a_{nj_n} x^{j_n}\right) \\ &= \sum_{J \in S} a_{1j_1} \cdots a_{nj_n} x^{j_1+\cdots + j_n} \end{split}$$ on expanding the product, where $$\begin{split} J &= (j_1, j_2, \dots, j_n) \\ &\in \{0, 1, \dots, n_1 \} \times \{0, 1, \dots n_2\} \times \dots \times \{0, 1, \dots, n_n\} = S \subset \{0, 1, \dots, \max n_i\}^n. \end{split}$$ The coefficient of $x^k$ is then found by restricting the sum to $$S_k = \{ J \in S: j_1 + \dots + j_n = k \} \subset S.$$

 

[CGandC]

Thank you very much, very good info!