Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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.

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

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.

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

Your Answer

 
discard

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.