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.



Finding regions where multi-variate polynomials are positive
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.


