Comp Sci 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 <br /> \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 <br /> \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}<br /> P(x) &amp;= \prod_{i=1}^n \left(\sum_{j=0}^{n_i} a_{ij}x^{j}\right) \\<br /> &amp;= \left(\sum_{j_1=0}^{n_1} a_{1j_1}x^{j_1}\right)<br /> \cdots \left( \sum_{j_n=0}^{n_n} a_{nj_n} x^{j_n}\right) \\<br /> &amp;= \sum_{J \in S} a_{1j_1} \cdots a_{nj_n} x^{j_1+\cdots + j_n}<br /> \end{split} on expanding the product, where \begin{split}<br /> J &amp;= (j_1, j_2, \dots, j_n) \\ &amp;\in <br /> \{0, 1, \dots, n_1 \} \times \{0, 1, \dots n_2\} \times \dots \times \{0, 1, \dots, n_n\}<br /> = S \subset \{0, 1, \dots, \max n_i\}^n. \end{split} The coefficient of x^k is then found by restricting the sum to <br /> S_k = \{ J \in S: j_1 + \dots + j_n = k \} \subset S.

 

[CGandC]

Thank you very much, very good info!