Determine if a polynomial is a positive linear combination of a set of polynomials

Question

So I asked a basic version of this question here, and was asking the more general variation in the comments, but the general version is tough enough to warrant its on question.

There is a set of equations

$\{x_1,1−x_1,1−x_1−x_2−x_1x_2,x_1−x_1x_2,x_1x_2,$ $1−x_1−x_2−x_3+x_1x_2+x_1x_3+x_2x_3−x_1x_2x_3,x_1−x_1x_2−x_1x_3+$ $x_1x_2x_3,x_2x_3−x_1x_2x_3,x_1x_2x_3\}$

that is used to generate the main set of base equations $s$. The set of equations is generated by taking $n\geq 3$ variables, and substituting every combination without duplicates into the above equations. For example, here is what the $3$-variable case looks like for $x,y,z$

$ s=\{x,1−x,y,1−y,z,1−z,1−x−y+xy,1−x−z+xz,1−y−z+yz,y−xy,z−xz,$ $x−xy,z−yz,x−xz,y−yz,xy,xz,yz,1−x−y−z+xy$ $+xz+yz−xyz,z−xz−yz+xyz,y−xy−yz+xyz,x−xy−xz$ $+xyz,yz−xyz,xz−xyz,xy−xyz,xyz\} $

Now with the set $s$ I want to know if there exists a set of non-negative coeffients $c_1, c_2 ..., c_{m}$ so that for a given polynomial $p(x, y,z, ...)$ we can say that

$$ p = c_1s_1+c_2s_2+...+c_ms_m+1 $$

For the $2$ and $3$ variable case, there turned out to be a simple set of inequalities that made determining this very simple, as explained here, and I wanted to know if this property carried over as $n$ grew larger and larger.

Answer 1

Let

• $n \geq 1$ be an integer,
• $\hat{I} = \{1, \dots, n\} \subset \mathbb{N}$ be an index set with $|\hat{I}| = n$,
• $X = \{x_\hat{i} : \hat{i} \in \hat{I}\}$ be a set of $n$ variables,
• for $\hat{i} \in \hat{I}$, $s_\hat{i} = \{1, 1-x_\hat{i}, x_\hat{i}\}$ be an ordered set of polynomials in $x_\hat{i}$, with $s_\hat{i}(0) = 1$, $s_\hat{i}(1) = 1 - x_\hat{i}$, and $s_\hat{i}(2) = x_\hat{i}$ expressing the ordering,
• $I = \{0,1,2\}^n \smallsetminus (0,0,0,\dots 0)$ be an ordered set of multi-indices, in reverse lexicographic order, for example, for $n = 3$, $(1,0,0) < (2,0,0) < (0,1,0) < \cdots < (0,2,0) < {}$ $ (0,0,1) < \cdots < (0,0,2) < \cdots < (2,2,2)$,
• for $i = (i_1,i_2, \dots, i_n) \in I$, $s_{(i)} = \prod_{j=1}^n s_j(i_j)$,
• $s = \{s_{(i)} : i \in I\}$, be an ordered set of (non-constant) polynomials, inheriting the ordering of $I$
• $S = \left\{1+\sum_{i \in I} c_{i} s_{i} : c_i \in [0,\infty) \subset \mathbb{R}\right\}$ be nonnegtaive real linear combinations of elements of $s$.

Let $p = p(\overline{x}) \in \mathbb{R}[X]$ be a polynomial with real coefficients in the varables $X$. We wish to find an algorithm to determine whether $p \in S$. We will argue that $S$ is spanned by nonnegative linear combinations of the elements of $s$ containing the monomial $\prod_{\hat{i} \in \hat{I}} x_\hat{i}$ and that the coefficients exhibiting $p$ as an element of this span produce inequalities on the coefficients of $p$ which determine whether $p \in S$.

Please note that the ordering of the monomials in $s$ is very different from your ordering. It has the positive property that incrementing $n$ gives a new $s$ which is this $s$ with more terms added to the end. That is, the ordered sets $s$ are recursive in $n$.

Step 1

Since $S$ contains only polynomials in squarefree monomials over $X$, we reject any $p$ that contains any variable to a power other than $0$ or $1$.

Let $A = \{0,2\}^n \subset I$. Consequently, we need only further consider polynomials of the form $$p(X) = \sum_{i = (i_1, i_2, \dots, i_n) \in A} a_{i}s_{i} \text{,} $$ for each $a_{i} \in \mathbb{R}$, which is a somewhat indirect way of writing that in every term of $p$, each $x_j$ appears to the power $0$ or $1$.

Step 2

There are $2^n$ monomials in $p$ (including terms with coefficient zero), so $p$ gives us $2^n$ constants $\{a_i : i \in A\}$. There are $2^n$ elements of $I$ with multi-indices in $C = \{1,2\}^n \subset I$, where every index of the multi-index is a $1$ or a $2$. The elements $\{s_i : i \in C\}$ are exactly the elements of $s$ which contain the monomial $\prod_{\hat{i} \in \hat{I}} x_\hat{i} = x_1 x_2 \cdots x_n$. So temporarily ignoring the non-negativity constraint we may use linear algebra to solve for the $\{c_i : i \in C\}$ in terms of the $\{a_i : i \in A\}$. We justify this process with the observations:

• the coefficient, $a_{(2,2,\dots,2)}$ of $\prod_{\hat{i} \in \hat{I}}x_\hat{i}$ in a $1+\sum_{i \in I} c_{i} s_{i} \in S$ is specified completely by the $\{c_i : i \in C\}$. Thus, we find the subspace of choices of the coefficients $c_i$ which produce elements of $S$ have the correct coefficient of $\prod_{\hat{i} \in \hat{I}}x_\hat{i}$. If $p$ is in $S$, a set of coefficients $\{c_i : i \in C\}$ that realize this membership must be in this subset.
• $|\{c_i : i \in C\}| = 2^n = |\{a_i : i \in A\}|$, and by construction, the column and row spaces of the linear system are linearly independent, so there is a unique solution. (For the rows: First, all the coefficients are $\pm 1$. Each row's $a_i$ corresponds to a distinct monomial in the $X$. Were two rows to agree, then the two subsets of $s$ corresponding to those two distinct monomials are the same subsets. However, this contradicts our construction of $s$. A similar argument applies to the columns.)
• Our choice to construct elements of $s$ using our ordered outer product means the solutions have the same structure for each $c_i$ with $i \in C$ and for different choices of $n$. For instance, $$ c_{(2,2,\dots,2)} = -1 + \sum_{i \in A}a_i - \gamma \text{,} $$ where $\gamma$ is a sum of $c_i$ for $i \in A$ (!). In fact, the solution of the system is similar for each of the $c_i$ for $i \in C$, $c_i = -1 + \alpha - \gamma$ where $\alpha$ is a sum of $a_i$s and $\gamma $ is a sum of $c_i$s. These signs make the rest of the solution straightforward.

Step 3

Since every $c_i$ for $i \in I$ is non-negative, the solution from step 2 gives inequalities among the $a_i$ and $c_i$ for $i \in A$. For example $$ 0 \leq c_{(2,2,\dots,2)} = -1 + \sum_{i \in A}a_i - \gamma \text{.} $$ Since the $c_i$ in $\gamma$ are all non-negative, we must have $\sum_{i \in A}a_i \geq 1$ and $0 \leq \gamma \leq -1 + \sum_{i \in A}a_i$

Note that if all the inequalities from step 2 similar to $\sum_{i \in A}a_i \geq 1$ are satisfied, then a set of $\{c_i : i \in I\}$ exhibiting that $p \in S$ is given by $c_i = 0$ for$ i \in A \smallsetminus C$ and apply this reduction to the solution of step 2 to get the $c_i$ for $i \in C$.

---

In other words, the non-negative linear combinations of the $s_i$ for $i \in C$ span $S$ and taking zero coefficients for the $s_i$ with $i \not\in C$ reduces the problem to a linear system. The linear system gives exact non-negativity criteria for sums of the coefficients of $p$, which determine whether $p \in S$.

---

There is a more theoretical solution that rewrites all the $1$s in the $\{1,x_\hat{i}, 1 - x_\hat{i}\}$ in terms of $x_\hat{i}$ and $1-x_\hat{i}$ This can be done always compatibly with the non-negativity constraint because for $c \geq 0$, $c \cdot 1 = c \cdot x + c \cdot (1-x)$. Thus, we can always modify the coefficients whose multi-indices agree in all but one place so that the coefficient having $0$ in that place is added to the coefficients having $1$ and $2$ in that place and then setting the coefficient having $0$ in that place to zero. This is a relatively direct proof that the $\{s_i : i \in C\}$ non-negatively span $S$.

Altering the signs can change whether a useful subset of $s$ non-negatively spans $S$, so small modifications to the $s_\hat{i}$ can preclude that any simple solution like the above works.