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.