An elementary polynomial sign-pattern bound

First establish an elementary zero-counting fact. If $D\ge 1$ and $r_i(x)=x_i^D+s_i(x)$ with $\mathrm{deg}{s}_i<D$ for $1\le i\le k$, then these $k$ polynomials have at most $D^k$ distinct common real zeros. In the quotient vector space $V=\mathbb{R}[x_1,\dots ,x_k]\mathrm{/}(r_1,\dots ,r_k)$, every monomial is a linear combination of the $D^k$ monomials $x_1^{a_1}\cdots x_k^{a_k}$ with $0\le a_i<D$. Indeed, if some exponent is at least $D$, replace its factor $x_i^D$ by $-s_i$ modulo the ideal. Every resulting monomial has strictly smaller total degree, so induction on total degree terminates and proves the spanning assertion. Thus $\dim V\le D^k$.

If no strict sign vector occurs, its bound is immediate. Otherwise choose one representative $a_{\sigma }$ for each attained strict vector $\sigma$. Only finitely many choices are involved, since there are at most $2^m$ vectors. Set $P={\prod }_{i=1}^m{p}_i$ and $D=2md+1$. Then $P(a_{\sigma })\mathrm{\ne }0$. Choose a single $\delta >0$ so small that $H(a_{\sigma })>0$ for every representative, where $H(x)=P(x{)}^2-\delta {\sum }_{i=1}^k{x}_i^{D+1}$. Such a choice exists: there are finitely many positive numbers $P(a_{\sigma }{)}^2$, and the other term has a fixed finite value at each representative. Since $D+1$ is even and greater than $2\mathrm{deg}P$, $H(x)\to -\mathrm{\infty }$ as $\mathrm{\parallel }x\mathrm{\parallel }\to \mathrm{\infty }$. Explicitly, $\mathrm{\mid }P(x){\mathrm{\mid }}^2\le C(1+\mathrm{\parallel }x{\mathrm{\parallel }}^{2md})$ and ${\sum }_i{x}_i^{D+1}\ge k^{-(D+1)\mathrm{/}2}\mathrm{\parallel }x{\mathrm{\parallel }}^{D+1}$.

For any finite list of distinct common zeros $z_1,\dots ,z_t$, evaluation defines a surjective linear map $V\to {\mathbb{R}}^t$. To see surjectivity, for every ordered pair $j\mathrm{\ne }h$ choose a coordinate $i(j,h)$ in which $z_j$ and $z_h$ differ, and set $h_j(x)={\prod }_{h\mathrm{\ne }j}(x_{i(j,h)}-(z_h{)}_{i(j,h)})\mathrm{/}((z_j{)}_{i(j,h)}-(z_h{)}_{i(j,h)})$. Then $h_j(z_h)$ is $1$ for $h=j$ and $0$ otherwise. Evaluation vanishes on the ideal because all its generators vanish at these zeros, so it is well defined on $V$ and the classes of $h_j$ map onto the standard coordinate vectors. The classes of $h_1,\dots ,h_t$ are linearly independent: applying evaluation to any relation gives the same relation among the standard coordinate vectors, so every coefficient is zero. A vector space spanned by $D^k$ vectors contains at most $D^k$ independent vectors. Explicitly, insert the independent vectors successively into the given spanning list: express the next one in the current spanning list, replace a listed vector with a nonzero coefficient outside the previously inserted independent vectors, and solve that expression for the replaced vector. The list still spans and has the same length. If there were no such outside coefficient, the new vector would lie in the span of the previously inserted ones, contradicting independence. Thus at most $D^k$ independent vectors can be inserted. This proves $t\le \dim V\le D^k$ using only finite linear algebra. If there were more than $D^k$ zeros, choosing a finite list of $D^k+1$ of them would contradict this inequality. This proves the zero-counting fact without a genericity or multiplicity assumption.

For an attained strict vector $\sigma$, put $S_{\sigma }=\{x:\mathrm{sgn}{p}_i(x)={\sigma }_i\text{ for all }i\}$. This is open. Its closure has a maximum of $H$: choose a closed ball containing $a_{\sigma }$ outside which $H<0$, and apply [F2] to its nonempty closed bounded intersection with $\overline{S_{\sigma }}$. The resulting maximum is positive, because $H(a_{\sigma })>0$, and it is also the maximum over the full closure. Any point in $\overline{S_{\sigma }}\setminus S_{\sigma }$ has $p_i=0$ for some $i$ by continuity, so there $H=-\delta {\sum }_i{x}_i^{D+1}\le 0$. Therefore the positive maximum is attained at a point $b_{\sigma }\in S_{\sigma }$, which is an interior local maximum of $H$. Distinct strict vectors give distinct such points.

By [F3] every $b_{\sigma }$ is a common zero of the $k$ polynomials ${\mathrm{\partial }}_{i}H=2P{\mathrm{\partial }}_{i}P-\delta (D+1)x_i^D$. After division by the nonzero coefficient $-\delta (D+1)$, each has the form $x_i^D+s_i(x)$ with $\mathrm{deg}{s}_i\le 2md-1<D$. The zero-counting fact therefore bounds their distinct common zeros, and hence the number of strict sign vectors, by $D^k=(2md+1{)}^k$.

For binary vectors with $>0$, choose one representative per attained vector. Choose $\epsilon >0$ smaller than every nonzero $\mathrm{\mid }{p}_i\mathrm{\mid }$ occurring at these finitely many representatives; if there are no such values, choose any positive $\epsilon$. The strict signs of $p_i-\epsilon$ at the representatives now encode their original binary vectors: positive values remain positive, and nonpositive values become negative. Applying the strict bound to the $m$ shifted polynomials gives the binary bound. For $\ge 0$, use $p_i+\epsilon$: nonnegative values become positive, and negative values remain negative. For ternary vectors choose representatives and $\epsilon$ in the same way, and use the $2m$ polynomials $p_i-\epsilon ,p_i+\epsilon$. Their strict sign pairs are $(-,-)$, $(-,+)$, and $(+,+)$ for the original negative, zero, and positive values, respectively, so distinct ternary vectors give distinct strict vectors. The strict bound with $2m$ polynomials gives $(4md+1{)}^k$. Restriction of the domain only removes vectors.