Question

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.

Answer 1

The claim is true. A proof idea is as follows: we first pick sufficiently large numbers for S₁, then we pick sufficiently large numbers for S₂ given S₁, and continue this until we decide all of S₁, …, S_n.

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 d_j be the degree of P_j in x_n, and write P_j(x₁,…,x_n) = x_n^d_jQ_j(x₁,…,x_n−1) + R_j(x₁,…,x_n), where the degree of R_j in x_n is less than d_j. The induction hypothesis allows us to find the ranges S₁, …, S_n−1 and b₁,…,b_p∈{−1,1} for the (n−1)-variate polynomials Q₁, …, Q_p. Then for every (a₁,…,a_n−1)∈S₁×…×S_n−1, the sign of the leading term of P_j(a₁,…,a_n−1,x_n) is b_j. Therefore, S_n can be any sufficiently large numbers.

Answer 2

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.)