This question was first asked by Mehtaab Sawhney in Alex Postnikov's combinatorics class. 


Given a rational function $F=P(x\_1,...,x\_n)/Q(x\_1,...,x\_n)$ with (say) integer coefficients, it is often of interest in combinatorics whether $F$ has a *subtraction-free expression*, that is, whether $F$ is formally equal to some rational function $G=R(x\_1,...,x\_n)/S(x\_1,...,x\_n)$ where $R,S$ have *nonnegative* coefficients. I consider $F$ to be equal to $G$ when $PS=QR$ as polynomials.


For example, although $1-x+x^2$ contains a minus sign, it has the subtraction-free expression $\frac{1+x^3}{1+x}$. It is clear that not all rational functions have such an expression, since for example any subtraction-free rational function takes positive values when all inputs are positive.


Is the problem of determining whether $F$ has a subtraction-free expression decidable? Is there a reasonably efficient algorithm in terms of $n$, $\deg(P)$, $\deg(Q)$?



Determining if a rational function has a subtraction-free expression
$\def\RR{\mathbb{R}}$I'm pretty sure I know what the answer is, but I found it surprisingly hard to find references for the facts I needed. So, here is what I think the truth is: Let $f(x\_1, \ldots, x\_n)$ be a polynomial with real coefficients; we write 
$$f(x\_1, \ldots, x\_n) = \sum\_{a \in A} f\_a x^a$$
for some finite subset $A$ of $\mathbb{Z}^n$. Let $N(f)$ be the convex hull of $A$, also known as the Newton polytope of $f$. For each face $F$ of $N(f)$, let $f\_F = \sum\_{a \in A \cap F} f\_a x^a$. Then I claim that $f$ has a subtraction free expression if, for all faces $F$ of $N(f)$, and all $(x\_1, \ldots, x\_n) \in \RR\_{>0}^n$, we have $f\_F(x\_1, \ldots, x\_n)>0$.


Furthermore, for any integer polytope $\Delta$, I claim we can find a polynomial $h$ with positive coefficients such that, if $N(f) = \Delta$ and $f$ obeys the above condition, then $f h^M$ has positive coefficients for all sufficiently large $M$.


**Claim 1: If $f$ has a subtraction free expression, then $f$ obeys this condition.** Write $f = \tfrac{p}{q}$ where $p$ and $q$ have positive coefficients. Suppose for the sake of contradiction that $f\_F$ is negative somewhere. Choose a linear functional $\lambda$ on $N(f)$ which is maximized on $F$. Let $P$ and $Q$ be the faces of $N(p)$ and $N(q)$ where $\lambda$ is maximized. Then $f\_F = \tfrac{p\_P}{q\_Q}$. Since $p$ and $q$ have positive coefficients, that's a contradiction. $\square$


**If $f$ obeys this condition, then $f$ has a subtraction free expression** This is the one I don't have a complete proof of. If $N(f)$ is a multiple of the standard simplex, meaning that $f$ is homogenous of degree $d$ and the coefficients of the monomials $x\_1^d$, $x\_2^d$, ... and $x\_n^d$ are nonzero, then this is a result of Polya, taking $h = x\_1 + x\_2 + \cdots + x\_n$.


It seems to me that the generalization to other Newton polytopes should be a matter of bookkeeping and saddlepoint approximations. (Specifically, I think we should take $h = \sum\_{a \in d N(f)} x^a$ for $d$ chosen large enough.) I thought this would be in the literature -- it seems to me like low hanging fruit on Polya's tree -- but I can't find it. 


**ADDED** Sam Hopkins points out that I only addressed the case of polynomials, not rational expressions. I claim that, if the above is right, this also resolves the rational function case. Specifically, I claim the test is the following:


Write your rational expression in lowest terms as $f/g$. Choose a point $x \in \mathbb{R}\_{>0}^n$ where $f$ and $g$ are both nonzero. If $f(x)/g(x)<0$, your function does not have a subtraction free expression. Otherwise, after replacing $f$ and $g$ by $-f$ and $-g$, we may assume that $f(x)$ and $g(x)>0$. After making this replacement, there is a positive expression for $f/g$ if and only if there is separately for $f$ and for $g$. 


Clearly, if $f/g$ passes this test, it has a positive expression. What we need to show is that, if there is a positive expression for $f/g$ then, after sign normalization, there is for $f$ and $g$ separately. IF there is such a positive expression, then there is some $h$ such that $fh$ and $gh$ have positive coefficients. We wish that we knew that $h$ also had positive coefficients. In other words we need:


**Lemma** Let $f$ be a polynomial which is positive somewhere in $\mathbb{R}\_{>0}^n$ and suppose there exists a polynomial $h$ such that $fh$ has positive coefficients. Then there is a polynomial $h'$ with positive coefficients such that this occurs.


**Proof** The condition that $h$ exists implies that $f$ has constant sign on $\mathbb{R}\_{>0}^n$, and this sign is by hypothesis positive. The same is true for each $f\_F$. Thus, by the unproven part of the above claims, there is an $h'$ with positive coefficients such that $f h'$ has positive coefficients. $\square$


