Polynomial Set Membership Algorithms

Question

I am trying to write a program that takes in a polynomial $P(x,y)$ and determine if it is a member of the following set of polynomials. Given a set of polynomials $$ s = \{x, 1-x, y, 1-y, x-xy, y-xy, 1-x-y+xy, xy\} = \{p_1,p_2,...p_8\} $$ we define the set $S$ to be $$ S = \{c_1p_1+c_2p_2+...+c_8p_8+1 \mid c_1,c_2,...,c_8\geq0\} $$

Is there an algorithm or method to determine whether $P(x,y)\in S$ for any given polynomial? Important to note that this polynomial is simplified.

Answer 1

Any polynomial in $S$ must have terms in $\{1,x,y,xy\}$, so be of the form $$ a + b x + c y + d xy \text{,} \tag{I}$$ for $a,b,c,d$ in whatever set the $c_i$ live in (which is unspecified in your problem statement). If a polynomial has a term not in the list, it cannot be in $S$. From the forms given in $s$, we find \begin{align*} d &= -c_5 -c_6 +c_7 +c_8 \\ c &= c_3 -c_4 +c_6 -c_7 \\ b &= c_1 -c_2 +c_5 -c_7 \\ a &= c_2 +c_4 +c_7 +1 \tag{LP} \end{align*} From the condition on the $c_i$, one piece of low-hanging fruit is that $a \geq 1$ is necessary.

Solving this linear system for $c_5, \dots, c_8$, we have \begin{align*} c_5 &= -1 +a +b -c_1 -c_4 \\ c_6 &= -1 +a +c -c_2 -c_3 \\ c_7 &= -1 +a -c_2 -c_4 \\ c_8 &= -1+a+b+c+d-c_1-c_3 \end{align*} With this, the question is recast as: are there nonnegative $c_1, \dots, c_4$ making $c_5, \dots, c_8$ nonnegative. Again, we have low-hanging fruit. From each equation, in order from top to bottom, \begin{align*} a+b &\geq 1 & 0 &\leq c_1 + c_4 \leq a+b-1 \\ a+c &\geq 1 & 0 &\leq c_2 + c_3 \leq a+c-1 \\ a &\geq 1 & 0 &\leq c_2 + c_4 \leq a -1 \\ a+b+c+d &\geq 1 & 0 &\leq c_1 + c_3 \leq a+b+c+d-1 \tag{II} \end{align*} In each line, if the left column inequality is satisfied, the right column inequality is satisfiable (by, at the very least setting $c_1 = \cdots = c_4 = 0$), so the polynomial is in $S$. If any inequality in the left column is not satisfied, then the corresponding member of $c_5,\dots,c_8$ is negative, so the polynomial is not in $S$.

Summary of algorithm:

Check that the polynomial is in the span of {1, x, y, xy}, allowing any signs for coefficients.  
    If not, polynomial is not in S.
Assign a,b,c,d as in (I).
Check the inequalities in the left column of (II).  
    If all are satisfied, the polynomial is in S.  
    If any is/are not satisfied, the polynomial is not in S.

Although it is difficult in general to determine if a linear program has a nonempty feasible set, it is a happy accident that we can arrange for $c_5, \dots, c_8$ to depend only on the negatives of very simple combinations of $c_1, \dots c_4$ and that $c_1 = \cdots = c_4 = 0$ is a point in the feasible set of (II) if the polynomial is in $S$.