Let $F(x,y)$ be a real polynomial in two variables of degree $d$. How many roots can $F(x,e^x)$ have? In other words, is there a bound one can place on the number of intersection points of $F(x,y)=0$ and $y=e^x$?



Roots of $F(x,e^x)$
Such a function has at most $\frac{d(d + 3)}{2}$ roots. In fact, let us show by induction on $k$ the following general statement:


Let $p\_0, p\_1, \dots, p\_k$ be polynomials of degree at most $n\_0, n\_1, \dots, n\_k$ respectively, not all of which are 0. Then, the function $f(x) = \sum\_{j = 0}^{k} p\_j (x) e^{j x}$ has at most $n\_0 + n\_1 + \cdots + n\_k + k$ zeroes. In the case where $p\_i$ is 0 we take $n\_i = -1$.


For $k = 0$ the claim is obvious. Suppose we have shown the claim for $k - 1$. Say that $f$ has $n$ zeroes. Notice that $f'(x) = p\_0 '(x) + \sum\_{j = 1}^{k} \left( p\_j '(x) + j p\_j (x) \right) e^{j x}$ satisfies the conditions of the claim, where the free coefficient has degree which is 1 smaller, and the degrees of the rest of the coefficients are the same. However, by Rolle's theorem, $f'(x)$ has at least $n - 1$ zeroes. Taking the $n\_0 + 1$-th derivative, dividing by $e^{x}$ and using the induction hypothesis we prove the claim.


In our case, we have $\mathrm{deg} (p\_i) \leq d - i$ and so our function has at most $\frac{d(d + 3)}{2}$ roots.


