Skip to main content
MathOverflow

Return to Question

clarified definition
Source Link
Christian Gaetz
Christian Gaetz
  • 2.7k
  • 2
  • 19
  • 37

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

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.

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

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

Source Link
Christian Gaetz
Christian Gaetz
  • 2.7k
  • 2
  • 19
  • 37

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.

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