mjhjmtu

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?

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 : mathbbZ^n to mathbbR$. I will mainly address the case of nonnegative Laplace transform after discussing the strictly positive case. There does not seem to be a way to get from either result to the other.

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 : mathbbZ^n to mathbbR$ 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 $mathbbZ^n$ rather than functions. As pointed out by David Handelman in the comments, this ring is also isomorphic to the ring of Laurent polynomials $mathbbR[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 $mathbbR[X_1^pm,ldots,X_n^pm]$ are precisely the evaluation maps at points $sinmathbbR^n_> 0$. Writing $s$ as a componentwise exponential, $s_i = e^t_i$ for $tinmathbbR^n$, makes the connection with the Laplace transform: the monotone homomorphisms from functions to the reals are parametrized by $tinmathbbR^n$, and are given by the values of the Laplace transform
$$f longmapsto sum_kinmathbbZ^n f(k), e^langle t,krangle.$$

Strictly positive Laplace transform

In this case, we would like to show:

Conjecture. If finitely supported $f : mathbbZ^n to mathbbR$ has strictly positive Laplace transform, then there is finitely supported nonzero and nonnegative $g : mathbbZ^ntomathbbR$ such that $gast f$ is nonnegative.

Per the above isomorphism, and upon multiplying by a suitably high power of the variables $X_i$, it would be enough to show that if $f$ is a multivariate polynomial which is positive on the positive orthant, then there is a $kinmathbbN$ such that $left(1 + sum_i X_iright)^k f$ has nonnegative coefficients. Upon homogenization, this is very close to Pólya's Positivstellensatz, but does not seem quite to follow, since it is not clear whether the homogenization is strictly positive on the boundary of the simplex.

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 : mathbbZ^ntomathbbR$, the following are equivalent:

1. The Laplace transform of $f$ is nonnegative.


2. For every $varepsilon > 0$ and $rinmathbbR_+$, there exist a finitely supported nonzero and nonnegative $g : mathbbZ^n to mathbbR$ and a polynomial $pinmathbbR_+[X]$ such that $p(r) leq varepsilon$ and the function
   $$g ast left[f + pleft(1 + sum_i (delta_e_i + delta_-e_i) right)right]$$
   is nonnegative.

Here, the polynomial $pleft(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 $varepsilonto 0, : rtoinfty$.

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.