Determining if a rational function has a subtraction-free expression 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)$?
 A: $\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$
A: If $F$ is a real rational function of one variable, then the necessary and sufficient condition is that both the numerator and denominator (of an irreducible representation) are positive on the positive ray. This follows from a result of
Poincare, Sur les equations algebriques, CR 97 (1884) 1418-1419.
He also tells the degree of the common multiplier, in terms of the arguments of the roots.
