# Is it always possible to find polynomials $p(x)$, where the sign of $p(x)$ matches $f(x)$ for every $x$?

Given a function $f:\mathbb{R^n}\to \mathbb{R}$ that can be expressed as sum of roots of polynomials, i.e. $f = \sum_{i=0}^k (p_i)^{1/n_i}$ for some polynomials $p_i$ and integers $n_i$. Can one find a polynomial $p:\mathbb{R}^n \to \mathbb{R}$ such that in the domain where both function are defined, we have $p(x_1,\ldots,x_n) \geq 0 \Longleftrightarrow f(x_1,\ldots,x_n)\geq 0$?

For example, $f(x) = \sqrt{x}$, then $p(x) = x$. $f(x,y) = \sqrt{x^2+y^2}+\sqrt{y}$, then $p(x,y) = x^2+y^2+y$.

However I wasn't able to find one for $f(x,y,z) = \sqrt{x}+\sqrt{y}-z$. It could be I just lack the algebraic skills.

-

Your first two examples are always positive, so $p(x)=1$ works as well for the first and $p(x,y)=1$ for the second. The last has the problem that it goes negative. Even $\sqrt{x}-z$ fails. You would like to have $p(x,z)=x-z^2$ which works fine for $z \ge 0$ but not when $z \lt 0$. $x-z|z|$ does work, but is not a polynomial.

-
Good observation. When I was doing inequalities, I never realized $\sqrt{x}\geq z$ is not equivalent to $x\geq z^2$... –  Chao Xu Nov 16 '11 at 7:31

You can decompose the region where $f \geq 0$ as a finite union of regions (with disjoint interiors) such that each region is the intersection of a finite number of sets, each set defined by an inequality $p(x_1, \dots, x_n) \geq 0$. A finite number of polynomials is enough to describe the locus where $f \geq 0$, but more than one polynomial could be necessary.

This is a consequence of Tarski's theorem on quantifier elimination for real-closed fields.

In the comments there was a request to solve the example $f(x,y,z) = \sqrt{x} + \sqrt{y} - z \geq 0$.
The domain is divided into four regions based on the sign of $x$ and $y$. In three of the regions $x$ or $y$ is negative and $f$ is undefined. The region where $f$ exists is the intersection of $x \geq 0$ and $y \geq 0$ and can be divided into two pieces, one with $z \leq 0$ and the second with $z \geq 0$. In the first piece $f \geq 0$ everywhere. In the second piece, $f \geq 0$ is equivalent to $z^2 \leq x + y + 2 \sqrt{xy}$ and one can subdivide again according to the sign of $q(x,y,z) = z^2 - x - y$. Where $q \leq 0$, then $f \geq 0$. Where $q \geq 0$, the condition is $4xy - q^2 \geq 0$.

The condition that $f$ is defined and non-negative can always be expressed as a decision tree in which each decision is a test of the sign of a polynomial.

-
I don't see an example where this could happen, but potentially you might need both $p$ and $(-p)$ to be non-negative, to force a polynomial condition $p=0$. For quantifier elimination in the general case this is necessary. –  zyx Nov 16 '11 at 3:21
Can you do the example $\sqrt x+\sqrt y-z$? –  Gerry Myerson Nov 16 '11 at 5:57
I like this, when I was originally asking this problem, I was trying to capture the information of the inequality with a polynomial. I'm satisfied that I can still maintain this goal, although use a few more polynomials. –  Chao Xu Nov 16 '11 at 7:35