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

-
My answer assumes that P_j is from ℕ^n to ℤ (or ℕ^n to ℝ). After I posted my answer, I realized that it is written that P_j is from ℕ^n to ℕ. I guess that it is a typo because otherwise the existence of b_j does not make sense to me, but I may be missing something completely. –  Tsuyoshi Ito Aug 8 '10 at 12:33
Thank you for pointing this out. Sorry, yes, it was a typo. I meant P_j to map to $\mathbb Z$ and not just to $\mathbb N$. I changed it in the question above. –  Daniel Aug 8 '10 at 20:23

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.

-
THANK YOU! This looks like a correct proof to me. –  Daniel Aug 8 '10 at 19:09

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

-
Thank you for your answer! Unfortunately, my issue is not to test which polynomials are the same. I need the conjecture above in another proof, which would use the existence of the above S_i to show that some other polynomials are the same. Besides the probabilistic Schwartz-Zippel lemma, there is a decision procedure to test whether two multi-variate polynomials are the same. The procedure just extends the fact that a polynomial of degree n has at most n roots to the multi-variate case. [N. Alon and M. Tarsi. Colorings and orientations of graphs. Combinatorica, 12(2):125­134, 1992.] –  Daniel Aug 8 '10 at 6:28