Finding regions where multi-variate polynomials are positive Given a constant $k \in \mathbb N$, and a set of $p$ multi-variate polynomials {$P_j:\mathbb N^n\to \mathbb Z$}$\_{j=1...p}$, with $P_j \not\equiv 0$. 
Is the following true:
There exists $n$ sets $S_1,\dots,S_n$, and $p$ constants $b_1,\dots,b_p$
with $S_i \subset \mathbb N$, $|S_i| = k$, $b_j \in${-1,1},
such that $\forall \bar{x} \in ${ $(x_1,\dots,x_n)| x_i \in S_i$} : $b_jP_j(\bar{x}) > 0$.

I am interested in this question since the existence of such a set will help me constructing 'witnesses' that I can then use to certify that some multivariate polynomials have to be identical since they agree on all of these witnesses $\bar{x}$. 
I have a proof idea, and I am wondering if my idea is correct; if there is a much easier insight showing my claim, and/or how to formalize my proof, since it is currently very vague ;)
I am a computer scientist, and unfortunately lack the necessary knowledge about ?manifolds? and that particular math-area to formalize my proof nicely. Please don't be too hard on me.

I think, the above is true according to "intuitive proof idea" that far away from the origin, we can find a region in space over which each polynomial is either all-positive or all negative and we can thus choose $b_i$ accordingly. (In fact there are many of these regions).
This idea with more details goes as follows: 
Consider the polynomials under polar coordinates, ie, $P'_i(\alpha_1,\dots, \alpha_{n-1},r$). Now, define the limits 'function' $Z_i(\bar{\alpha})$ as $\lim_{r\to \infty} Z_i(\bar{\alpha},r)$. Clearly, I want to have $+\infty$ and $-\infty$ be part of the range of the $Z_i$. Now, consider the geometry of the set if values $\bar\alpha$ for which $Z=0$. These cannot contain any (n-1)-dimensional manifolds, since we could thus easily find arbitrarily many points $\bar{x}$ for which $P_i(\bar{x}) = 0$, which contradicts the fact that $P_i \not\equiv 0$. Note, that since $P_i$ are polynomials, they only go to $0$ in a certain $\bar{\alpha}$ direction, if they actually are $0$ at some finite point toward this direction. Further, I think, $Z_i$ are 'some-what' smooth in the sense that if there are $\bar\alpha_1$ and $\bar\alpha_2$ for which $Z_i(\bar\alpha_1)$ and $Z_i(\bar\alpha_2)$ have different signs, then there has to be a point $\bar\alpha'$ on the 'straight' line connecting $\bar\alpha_1$ and $\bar\alpha_2$ for which $Z_i(\alpha')=0$. Soo, since all the zero-regions have at most dimension $n-2$, there has to be a region/manifold of dimension $n-1$ for which a $Z_i$ is strictly positive or strictly negative (all the stuff in between the network that is created by the zero-positions). We can thus find many values that are within that region of direction for which $Z_i$ is either always positive or always negative.
Further, let now point-wise multiply the $Z_i$ to one $Z$, ie, $Z(\bar{\alpha}):= \prod_i Z_i(\bar{\alpha})$. By the same reasoning, there is a region where $Z$ is all positive. Since there are no zero-values in that region, none of the $Z_i$ can have zeros in that region, and we can thus pick $b_i$ appropriately for each $Z_i$ to make it positive. Now, having the $\alpha$-region of dimension $n-1$, we just need to project this out (by choosing a large enough $r$) to get an $n$-dimensional cube that contains enough integers and is still within the captured $\alpha$ region.
 A: The claim is true.  A proof idea is as follows: we first pick sufficiently large numbers for S1, then we pick sufficiently large numbers for S2 given S1, and continue this until we decide all of S1, …, Sn.
Filling in a little more detail, the proof will be as follows.  We prove the claim by mathematical induction on n.  If n=1, we can just pick sufficiently large numbers.
Now let n≥2.  Let dj be the degree of Pj in xn, and write Pj(x1,…,xn) = xndjQj(x1,…,xn−1) + Rj(x1,…,xn), where the degree of Rj in xn is less than dj.  The induction hypothesis allows us to find the ranges S1, …, Sn−1 and b1,…,bp∈{−1,1} for the (n−1)-variate polynomials Q1, …, Qp.  Then for every (a1,…,an−1)∈S1×…×Sn−1, the sign of the leading term of Pj(a1,…,an−1,xn) is bj.  Therefore, Sn can be any sufficiently large numbers.
A: If your issue is to identify which polynomials are the same, your method sounds a bit complicated. Fortunately, this is a well studied problem in CS. The Schwartz-Zippel lemma should give you the witnesses you need. (Basically: choose enough points at random and you can't go wrong; what enough means is made precise in the lemma.)
