Given $W \subset \mathbb C$, let $S\_W$ be the set of polynomials in $\mathbb R[x]$ that vanish on $W$ and have *only nonnegative coefficients*.



> 
> **Warm-up question:** It's clear that if $W$ contains a positive real number, then $S\_W = \{0\}$. Is the converse true?
> 
> 
> 


I'm pretty sure the answer is "yes" but I don't know if I'd quite call what I have a proof.


More generally, how do the combinatorics of $W$ affect what you can say about $S\_W$? In particular, I'd like a handle on the following problem.



> 
> **Problem:** Find (bounds on) the smallest number of nonzero terms in a polynomial belonging to $S\_W$.
> 
> 
> 


What conditions on $W$ would allow us to do this? As I alluded to above, I'm especially interested in combinatorial conditions, e.g., on where the numbers in $W$ lie on the complex plane.


Maybe the following special case is more tractable. Actually, it's the only one that really matters to me anyway.



> 
> **Special case:** What if $W$ is a set of complex $n$th roots of unity?
> 
> 
> 


In this case, we'll want to assume $1 \not\in W$. Then the polynomial $x^{n-1}+x^{n-2}+\cdots+x+1$ gives an upper bound of $n$. If every number in $W$ lies in the left half-plane and $W$ is a self-conjugate set, then an upper bound of $|W|+1$ can be obtained by taking the product of the corresponding quadratic factors.


Meanwhile, I'm not sure I know how to derive a *lower* bound better than $2$ under any conditions!


Any thoughts or theory out there that might help shed light on these questions?



How few terms may appear in a polynomial with given (cyclotomic) roots and nonnegative coefficients?
$\def\ZZ{\mathbb{Z}}$ $\def\RR{\mathbb{R}}$ $\def\QQ{\mathbb{Q}}$ $\def\Re{\mathrm{Re}}$ $\def\Im{\mathrm{Im}}$Let $|W|=n$. I will show that $2n+1$ monomials are always sufficient, and are generically necessary. (Noam Elkies has already shown that $2n+1$ is generically sufficient.) If $W$ is closed under complex conjugation and has no real points, then this argument shows that $n+1$ is enough, since we could replace $W$ by $W' := \{ \omega \in W : \Im(\omega) > 0 \}$ and any real polynomial which vanishes on $W'$ will also vanish on $W$.


Let the elements of $W$ be $\omega\_j = x\_j + i y\_j = r\_j e^{i \theta\_j}$. For any nonnegative integer $m$, let $v\_m$ be the vector
$$v\_m := (\Re(\omega\_1^m), \Im(\omega\_1^m), \ldots, \Re(\omega\_n^{m}), \Im(\omega\_n^{m}))$$
So the $v\_i$ are vectors in $\RR^{2n}$, and our goal is to find a positive linear relation between them.


**Generic necessity:** Suppose that we had a linear relation $\sum a\_i v\_{m\_i}=0$ using only $2n$ terms. Then the vectors $v\_{m\_1}$, ..., $v\_{m\_{2n}}$ would be linearly dependent, so the $2n \times 2n$ matrix they form would have determinant zero. This is a nontrivial polynomial relation between the $x\_j$ and $y\_j$ with integer coefficients. If the $\omega\_j$ are chosen generically then the $x\_j$ and $y\_j$ will be algebraically independent over $\QQ$, and no such relation will exist.


**Sufficiency:** This is essentially Noam's proof when the $\theta\_j$'s are linearly independent over $\mathbb{Q}$, but with a lot more checking of degenerate cases. 
Suppose, for the sake of contradiction, that we cannot write $0$ as $\sum\_{i=1}^{2n+1} a\_i v\_{m\_i}$ with the $a\_i \geq 0$ and not all $0$. 
Equivalently, assume that, for any $(2n+1)$-tuple of vectors of the form $v\_m$, the origin is not in the convex hull of the tuple.


By the contrapositive of [Carathéodory's theorem](http://en.wikipedia.org/wiki/Carath%C3%A9odory%27s_theorem_%28convex_hull%29), we conclude that $0$ is not in the convex hull of the vectors $v\_m$. Let $K$ be the closure of the convex hull of the $v$'s. 
We conclude that $0$ is not in the interior of $K$. 
By [Farkas's lemma](http://en.wikipedia.org/wiki/Farkas%27_lemma), there is a linear function $\lambda : \RR^{2n} \to \RR$ with is $\geq 0$ on $K$ and not identically $0$ on $K$.
Equivalently, $\lambda(v\_m)$ is nonnegative for all $m$ and is positive for some $m$.


We can write $\lambda$ in the form 
$$(f\_1, g\_1, f\_2, g\_2, \ldots, f\_n, g\_n) \mapsto \Re \left( \sum (a\_j+i b\_j) (f\_j+i g\_j) \right)$$
for some $a\_j$ and $b\_j$. Set $\zeta\_j = a\_j+i b\_j$. Our hypothesis now is that
$$\phi(m) : = \Re \left( \sum\_j \zeta\_j \omega\_j^m \right)$$
is nonnegative for all $m$ and positive for some $m$; our goal is to deduce a contradiction.


Let $R$ be the set of distinct values of $|\omega\_j|$, and let the elements of $R$ be $r\_1 > r\_2 > \cdots > r\_p$. 
Let the elements of $R$ with norm $r\_j$ be $r\_j \exp(i \theta^j\_1)$, $r\_j \exp(i \theta^j\_2)$, ..., $r\_j \exp(i \theta^j\_{k(j)})$.
Reindex the $\zeta$'s accordingly as $\zeta^1\_1$, $\zeta^1\_2$, ...., $\zeta^1\_{k(1)}$, .... $\zeta^p\_1$, ...., $\zeta^p\_{k(p)}$.
Put
$$\phi\_j(m) := \Re \left( \sum\_{\ell=1}^{k(j)} \zeta^j\_{\ell} \exp(i m \theta^j\_{\ell}) \right)$$
so
$$\phi(m) = \sum\_j r\_j^m \phi\_j(m). \quad (\ast)$$ 
Since $\phi(m)$ is not identically zero, not all of the $\phi\_j(m)$ are identically zero. Let $j\_0$ be minimal such that $\phi\_{j\_0}(m)$ takes nonzero values. 


**Lemma** There is $c>0$ so that $\phi\_{j\_0}(m)$ is infinitely often less than $-c$.


**Proof** By assumption, $\phi\_{j\_0}$ is not identically zero. Since none of the $\theta$'s are $0 \bmod 2 \pi \ZZ$, the Cesaro limit $\lim\_{M \to \infty} \frac{1}{M} \sum\_{1 \leq m \leq M} \phi\_{j\_0}(m)$ is $0$. (This is where we use that the $\omega$'s are not positive reals. Note that this is true even if some of the $\theta$'s are in $2 \pi \QQ$.) So $\phi\_{j\_0}$ is negative for some $m$, say $m\_0$. Let $\phi\_{j\_0}(m\_0)=-2c$. 


Consider any $\delta>0$. By a basic pigeonhole argument, we can find infinitely many $N$ such that $| N \theta^{j\_0}\_{\ell} \bmod 2 \pi \ZZ| < \delta$. (Note that this is true even if the $\theta$'s are not linearly independent over $\QQ$.) Choosing $\delta$ small enough, for such $N$'s, we have $\phi\_{j\_0}(m\_0+N) < -c$. $\square$.


Therefore, there are infinitely many $m$ for which the leading term of $(\ast)$ is as negative as $-c r\_{j\_0}^m$, and all the other terms are exponentially less. Thus, we have found an $m$ for which $\phi(m)<0$. This is a contradiction and the theorem follows.


**Remark:** Carathéodory + Farkas + (something clever) is a general proof technique. 
Chapter 2 of Barvinok's *A Course in Convexity* has many nontrivial exercises of this form.


