When can a function be made positive by averaging?

Question

Let $f: {\bf Z} \to {\bf R}$ be a finitely supported function on the integers ${\bf Z}$. I am interested in knowing when there exists a finitely supported non-negative function $g: {\bf Z} \to [0,+\infty)$ (not identically zero) such that the convolution $f * g$ is also non-negative. In other words, is there a convex combination of translates of $f$ that is non-negative?

From the Laplace transform identity $$ \sum_n f*g(n) e^{nt} = (\sum_n f(n) e^{nt}) (\sum_n g(n) e^{nt})$$ there is the obvious necessary condition that the Laplace transform of $f$ must be everywhere positive: $$ \sum_n f(n) e^{nt} > 0 \hbox{ for all } t \in {\bf R}.$$ But is this condition also sufficient? That is, if a function $f$ has positive Laplace transform, can it always be averaged to be non-negative?

A possibly more general necessary condition is that for any positive function $h: {\bf Z} \to (0,+\infty)$, one has $$ \sum_n f(n) h(n-m) > 0$$ for at least one integer $m$, since if $\sum_n f(n) h(n-m) \leq 0$ for all $m$ then $\sum_n f*g(n) h(n) \leq 0$ for all non-negative $g$, and then one could not make $f*g$ non-negative. Duality suggests that this more general necessary condition is essentially sufficient. The Laplace transform condition corresponds to the special case when $h(n) = e^{nt}$, but I don't know if this case already is strong enough to cover all the others.

EDIT: an equivalent question is to ask when a polynomial of one variable can be written as the quotient of two other polynomials with non-negative coefficients. The obvious necessary condition is that the polynomial has to be positive on $(0,+\infty)$; is this also sufficient?

Answer 1

Here is the divisibility theorem for polynomials (and thus for Laurent polynomials in several variables), chapter 3 in Positive polynomials, convex integral polytopes, and a random walk problem SLN 1282 (1986 or so) [either this, or Positive polynomials and product type actions of compact groups in Memoirs AMS 320; I am out of town, so do not have access to the references]. This can of course be translated back via Fourier transforms, if you want.

Let $Q$ be a polynomial in $d$ variables, let $K$ be its Newton polytope (the convex hull of its exponents with nonzero coefficients). We can reduce to the case that $K$ contains interior in $R^d$ (by changing variables). For each face of $K$, $F$, define $Q_F$ to be the subpolynomial obtained from $Q$ by throwing away all the terms whose exponents don't belong to $F$. Then (assuming $Q$ has at least one positive value on the positive orthant) $Q$ can be multiplied by a polynomial (and additionally we can assume it has no negative coefficients) so that the product has no negative coefficients if and only if (a) $Q$ is strictly positive on the strictly positive orthant and (b) for every face $F$ of dimension one or more, $Q_F$ is strictly positive on the positive orthant.

From this there is an easy corollary, that if merely $Q$ is strictly positive on the positive orthant, then an arbitrarily small perturbation with Newton polytope equalling $K$ and with positive coefficients will render it of this form.

A fine variation is given in Deciding eventual positivity of polynomials, Ergodic theory and dynamical systems (1986) 6, 57-79, which determines, given $P$ with no negative coefficients, when there exists $n$ such that $P^nQ $ has no negative coefficients. This generalizes the results of Polya (simplex) and Meissner (cube).

A variation occurs in Iterated multiplication of characters of compact connected Lie groups Journal of Algebra (1995) 173, 67-96, which deals with random walks arising from characters of compact groups, rather than just characters of tori (Laurent polynomials). There are others, including convolution with general measures, etc (write to me, this answer is getting too long).

See also Reference request: one of Poincare's theorems about positive functions

Answer 2

While the actual question has been answered very quickly in the comments, there are some interesting results in the higher-dimensional case, concerned with finitely supported functions $f : \mathbb{Z}^n \to \mathbb{R}$. I will mainly address the case of nonnegative Laplace transform after discussing the strictly positive case. It may be possible to both of these cases via Pólya's Positivstellensatz, using a small perturbation in the case of nonnegative Laplace transform, but I'm not sure at this point.

In both cases, the question is secretly about Laurent polynomials, as I will explain now in more detail. Readers who understand this can skip to the headings below.

The finitely supported functions $f : \mathbb{Z}^n \to \mathbb{R}$ form a ring under pointwise addition and convolution as multiplication. Equivalently, it may be convenient to consider it as the ring of finitely supported signed measures on $\mathbb{Z}^n$ rather than functions. As pointed out by David Handelman in the comments, this ring is also isomorphic to the ring of Laurent polynomials $\mathbb{R}[X_1^\pm,\ldots,X_n^\pm]$, where the generator $X_i$ corresponds to the Dirac measure $\delta_{e_i}$. Upon equipping this ring with the coefficientwise order, or equivalently with the pointwise order on functions, we get an ordered commutative ring in the sense of a ring equipped with a subset of positive elements $P$ which is closed under addition and multiplication. Hence we are effectively dealing with a problem in real algebraic geometry.

The monotone ring homomorphisms $\mathbb{R}[X_1^\pm,\ldots,X_n^\pm]$ are precisely the evaluation maps at points $s\in\mathbb{R}^n_{> 0}$. Writing $s$ as a componentwise exponential, $s_i = e^{t_i}$ for $t\in\mathbb{R}^n$, makes the connection with the Laplace transform: the monotone homomorphisms from functions to the reals are parametrized by $t\in\mathbb{R}^n$, and are given by the values of the Laplace transform $$f \longmapsto \sum_{k\in\mathbb{Z}^n} f(k)\, e^{\langle t,k\rangle}.$$

---

Strictly positive Laplace transform

In this case, we have (see also discussion in the comments):

Theorem. If finitely supported $f : \mathbb{Z}^n \to \mathbb{R}$ has strictly normalized Laplace transform $$ \frac{\sum_k f(k) e^{\langle t,k\rangle}}{\sum_k |f(k)| e^{\langle t,k\rangle}},$$ for all nonzero $t\in(\mathbb{R}\cup\{-\infty\})^n$, then there is $m\in\mathbb{N}$ such that $\left(1 + \sum_i \delta_{e_i}\right) ^{\ast m}\ast f$ is nonnegative.

Proof: By suitable translation, we can assume that $f$ is supported on $\mathbb{Z}^n_+$. Then we can formulate it in terms of polynomials, in which case the homogenized form is the most natural: if $p$ is a homogeneous polynomial whihc is strictly positive on the closed simplex, then there is $k\in\mathbb{N}$ such that $\left(\sum_i X_i\right)^k f$ has nonnegative coefficients. This is Pólya's Positivstellensatz (which also exists in a version in which all coefficients are strictly positive).

As explained in David Handelman's answer, one can also formulate a version of this result which gives a necessary and sufficient condition.

---

Nonnegative Laplace transform

In this case, we can only expect a $g$ as in the OP to exist approximately. The following is Theorem 5.9(a)-(b) of this recent paper.

Theorem. For finitely supported $f : \mathbb{Z}^n\to\mathbb{R}$, the following are equivalent:

1. The Laplace transform of $f$ is nonnegative.
2. For every $\varepsilon > 0$ and $r\in\mathbb{R}_+$, there exist a finitely supported nonzero and nonnegative $g : \mathbb{Z}^n \to \mathbb{R}$ and a polynomial $p\in\mathbb{R}_+[X]$ such that $p(r) \leq \varepsilon$ and the function $$g \ast \left[f + p\left(1 + \sum_i (\delta_{e_i} + \delta_{-e_i}) \right)\right]$$ is nonnegative.

Here, the polynomial $p\left(1 + \sum_i (\delta_{e_i} + \delta_{-e_i}) \right)$ is to be understood with respect to convolution as multiplication. It represents a correction whose Laplace transform converges to zero pointwise in the limit $\varepsilon\to 0, \: r\to\infty$.

There are many other statements of a similar flavour, some of which can be deduced from the existing results of the above paper and some of which are part of work in progress.