# Show that $f(t)=\sum_{i=1}^n a_i e^{-(x_i-t)^2}-c$ has at most $2n$ zeros

Let \begin{align} f(t)=\sum_{i=1}^n a_i e^{-(x_i-t)^2}-c \end{align} where $$x_1 and $$a_i>0$$. For some positive constant $$c$$.

Can we show that $$f(t)$$ has at most $$2n$$ zeros?

The intuition here is that if $$n=1$$ we have a simple bell curve. Then, a horizontal line $$c$$ can cross it at most $$2$$ times. Now if $$n=2$$, then we have two mixed bell curves and we get at most $$4$$ crossings.

In proposition 7 (together with the proof in the appendix) of Efficiently Learning Mixtures of Two Gaussians, A.T. Kalai, A. Moitra, G. Valiant prove that the linear combination of $$n$$ Gaussians with distinct variances can have at most $$2(n-1)$$ zeros. Their argument is inductive adding the Gaussians in order of decreasing variance. Every new Gaussian is added as close to a delta function, which increases the number of zeros by at most 2, and then everything is convolved with a gaussian of appropriate width.

In order to use this in your problem, we have to slightly perturb $$f(t)=0$$ to $$e^{-t^2}\left(\sum_{i=1}^n a_i e^{-(1+\epsilon_i)(x_i-t)^2}-c\right)=0$$ for distinct $$\epsilon_i$$ of small absolute value. This is a linear combination of $$n+1$$ Gaussians of distinct variances, and therefore has at most $$2n$$ zeros, as desired.

• Very nice argument! A slightly more direct variant would be to write $f(t)$ as a convolution of the Gauss–Weierstrass kernel $g(t) = (\pi (1-\delta))^{-1/2} e^{-t^2/(1-\delta)}$ and $h(t) = \sum_{i=1}^n a_i \delta^{-1/2} e^{-(x_i-t)^2/\delta} - c$ for a $\delta$ small enough, so that $h$ has $2 n$ zeroes. Convolution with a Gaussian does not increase the number of zeroes (as a Pólya frequency function, it is a variation diminishing kernel; for more on this, see, for example, review sections written by Karlin here). Jan 21 '19 at 20:47
• I have a quick question. Is the function $e^{(-(1+\epsilon)(x_i-t)^2} \cdot e^{-\frac{t^2}{2}}$ still treated as Gaussian?
– Boby
Jan 21 '19 at 23:07
• Also, is it a problem if one of $x_i$'s equal to zero? We might not have a distinct number of zeros condition. Or am I wrong here
Let $$g_s(x) = (\pi s)^{-1/2} \exp(x^2 / s)$$ denote the Gauss–Weierstrass kernel. Note that $$g_s * g_t = g_{s + t}$$.
Choose $$\delta \in (0, 1)$$ sufficiently small, so that \begin{aligned} h(x) & = \sum_{i = 1}^n a_i \delta^{-1/2} \exp((x - x_i)^2 / \delta) - c \\ & = \pi^{1/2} \sum_{i = 1}^n a_i g_\delta(x - x_i) - c \end{aligned} has exactly $$2 n$$ zeroes; or, more precisely, it changes its sign exactly $$2 n$$ times. (Is is intuitively clear, and relatively straightforward to prove, that $$\delta > 0$$ small enough have this property, but the details are a bit messy.) Then $$f$$ can be written as a convolution of $$h$$ and $$g_{1 - \delta}$$: \begin{aligned} f(x) & = \sum_{i = 1}^n a_i \exp((x - x_i)^2) - c \\ & = \pi^{1/2} \sum_{i = 1}^n a_i g_1(x - x_i) - c \\ & = \biggl(\pi^{1/2} \sum_{i = 1}^n a_i g_\delta(\cdot - x_i) - c\biggr) * g_{1 - \delta}(x) . \end{aligned} However, convolution with the Gauss–Weierstrass kernel does not increase the number of sign-changes: $$g_s$$ is a Pólya frequency function, and hence a variation diminishing kernel. For more on this, see, for example, review sections written by Samuel Karlin in Selected works of I. J. Schoenberg. It follows that $$f$$ changes its sign at most $$2 n$$ times, as claimed.