27
$\begingroup$

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)$?

$\endgroup$
3
  • 2
    $\begingroup$ Could you clarify when exactly you count two rational expressions as the same? For example, some people would say that $1-x+x^2$ is not the same as $(1+x^3)/(1+x)$, since the former is defined at $x=-1$ and the latter is not; but you want to count these as the same (and that is fine). A similar issue is slightly more complicated in several variables. $\endgroup$ – Joel David Hamkins May 24 '18 at 13:46
  • $\begingroup$ @JoelDavidHamkins I clarified what I mean, let me know if there are still ambiguities. $\endgroup$ – Christian Gaetz May 24 '18 at 13:57
  • $\begingroup$ Do you have an example showing that the positive-values on positive input condition is not also sufficient for subtraction-free representation? If it were a characterization, then we would get decidability, since you search either for a subtraction-free representation or for a negative output, and (if it were a characterization) you'll eventually find one or the other. $\endgroup$ – Joel David Hamkins May 24 '18 at 14:08
16
$\begingroup$

$\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$

$\endgroup$
1
  • 2
    $\begingroup$ Does this answer the question for rational functions or just for polynomials? $\endgroup$ – Sam Hopkins May 29 '18 at 17:51
15
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ By positive roots, do you mean roots with positive real part or roots which are positive real numbers? $\endgroup$ – Christian Gaetz May 24 '18 at 14:33
  • $\begingroup$ "Positive root " means "a root which is a positive real number". $\endgroup$ – Alexandre Eremenko May 24 '18 at 14:40
  • $\begingroup$ What if $F$ is a polynomial with no positive roots, but whose value is negative when $x$ is positive? Then I don't see how it can have a subtraction free expression. $\endgroup$ – Christian Gaetz May 24 '18 at 14:47
  • $\begingroup$ Poincare is speaking of the "sign changes" in the coefficients. Let me correct the statement. $\endgroup$ – Alexandre Eremenko May 24 '18 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.