When can a function be made positive by averaging?

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?

• Unless I have misinterpreted this, you are asking, given a Laurent polynomial $F$ with real coefficients, when does there exist another Laurent polynomial $G$ (with real coefficients) such that the product (as polynomials) has no negative coefficients. The necessary condition, that $F|(0,\infty) >0$ is also sufficient. This is an 1883 theorem of Poincaré. – David Handelman Nov 2 '18 at 0:04
• And Poincaré takes as $G$ a sufficiently high power of $1+x$. – David Handelman Nov 2 '18 at 0:06
• H Poincaré, Sur les équations algébriques, CR Acad Sci Paris 97 (1883) 1418. – David Handelman Nov 2 '18 at 0:24
• This paper (Theorem 1.2) cites Poincare's result (also mentioning Meissner, and Polya for the explicit form of $G$). arxiv.org/abs/1210.6868 – literature-searcher Nov 2 '18 at 0:31
• – literature-searcher Nov 2 '18 at 0:35

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).

• – Gjergji Zaimi Nov 2 '18 at 20:29
• This is the better answer. A version of the statement on nonnegative Laplace transform in my answer is implied. – Tobias Fritz Nov 2 '18 at 20:58

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

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.

• Perhaps somebody else can say more about the relation to Pólya's Positivstellensatz and on whether the conjecture is true. – Tobias Fritz Nov 2 '18 at 1:37
• I think the conjecture needs modification in order to deal with the positivity issue at the boundary. I now think the right conjecture is the following. The normalised Laplace transform $\sum_k f(k) e^{\langle t, k \rangle} / \sum_k |f(k)| e^{\langle t, k \rangle}$ extends continuously to the boundary of the simplex (where the $s_i$ are allowed to vanish), and I think one needs positivity on this entire simplex, not just on the interior. – Terry Tao Nov 2 '18 at 17:23
• For instance, if $f = \delta_0 - 2 \delta_{e_1} + \delta_{2e_1} + \delta_{e_2}$, corresponding to the polynomial $(1-X_1)^2 + X_2$, then the Laplace transform is positive in the interior of the simplex but has a vanishing point on the boundary and so I don't think one can make this polynomial totally positive by multiplying by a totally positive polynomial. – Terry Tao Nov 2 '18 at 17:25
• To put it another way, I think every facet of the Newton polytope of $f$ has to have a positive Laplace transform, not just the top dimensional facet. – Terry Tao Nov 2 '18 at 17:29
• Hmm, actually depending on the shape of the Newton polytope, the right compactification of the interior may be something more complicated than a simplex (there is some sort of "blowup" that is happening at lower dimensional facets that I don't yet understand). Let me try to sort this out properly... – Terry Tao Nov 2 '18 at 19:21