O-minimality and Putnam Competition

Question

Someone told me that, on a recent Putnam exam, there was an A6 or B6 problem that could be solved using a recent result from o-minimality. Apparently this was not the intended solution method, but it worked.

Does anyone know what problem or what o-minimality result they were referring to?

Answer 1

I think it is likely that, as @A. Rex suggested in his comment, the problem was A5 from the 2014 Putnam Competition.

The problem

The problem is stated as follows:

Let $$P_n(x) = 1 + 2x + 3x^2 + \dots + nx^{n-1}.$$ Prove that the polynomials $P_j(x)$ and $P_k(x)$ are relatively prime for all positive integers $j$ and $k$ with $j \neq k$.

The first solution in this file follows the following steps:

• Suppose towards a contradiction that there were some complex $z$ such that $P_i(z) = P_j(z) = 0$.
• Define a function $f : [0, + \infty) \to \mathbb{R}$ in terms of $z$.
• Construct $4$ solutions of $f$.
• Analyze the first, second, and third derivatives of $f$ to prove that $f$ has at most $3$ solutions, which is a contradiction.

Connection to o-minimality

The remark following this solution says:

By a similar reasoning, an equation of the form $e^x = P(x)$ in which $P$ is a real polynomial of degree $d$ has at most $d+1$ real solutions. This turns out to be closely related to a concept in mathematical logic known as o-minimality, which in turn has deep consequences for the solution of Diophantine equations.

In this remark, the phrase "similar reasoning'' refers to the fourth bullet point of the outline above, in which an analysis of derivatives is used to bound the number of solutions to an equation. A similar analysis can provide this bound on the number of solutions to $e^x - P(x)$.

As far as how this fact is related to o-minimality, I know the following things:

• $\mathbb{R}_{\mathsf{exp}} = (\mathbb{R}, +, \cdot, \mathsf{exp}, <)$ is an o-minimal expansion of the real field.
• The set of solutions to $e^x - P(x)$ is a definable subset of $\mathbb{R}_{\mathsf{exp}}$.
• Some results in o-minimality, such as the Pila-Wilkie Counting Theorem, bound the sizes of definable sets in o-minimal expansions of the real field.

If anyone can explicate this connection beyond the observations above, I would love to learn more about it.