MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer
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.)

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.