# 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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8775385618209839, "perplexity": 100.49865429607264}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-27/segments/1435375098808.88/warc/CC-MAIN-20150627031818-00101-ip-10-179-60-89.ec2.internal.warc.gz"}