Posted by: holdenlee | November 30, 2012

## Putnam 2011/A5

It’s that time of year again! The Putnam math competition is this Saturday, 12/1. Here’s a hard calculus problem from last year’s Putnam. As always, I’ll try and justify my thinking processes that led me to the solution (even though they are indirect).

Putnam 2011/A5:

Let $F:\mathbb R^2\to \mathbb R$ and $g:\mathbb{R}^2\to \mathbb{R}$ be twice continuously differentiable functions with the following properties:

• $F(u,u)=0$ for every $u\in \mathbb R$;
• for every $x\in \mathbb{R}$, $g(x)\ge 0$ and $x^2g(x)\le 1$;
• for every $(u,v)\in \mathbb{R}^2$, the vector $\nabla F(u,v)$ is either 0 or parallel to the vector $\langle g(u),-g(v) \rangle$.

Prove that there exists a constant $C$ such that for every $n\ge 2$ and any $x_1,\ldots, x_{n+1}\in \mathbb R$, we have

$\min_{i\ne j}|F(x_i,x_j)|\le \frac{C}{n}.$

Gut reaction: Yikes!

This problem looks very intimidating. I never got beyond this point on the Putnam. Decided to work on the other problems instead.

But let’s solve it.

Our first step is to justify to ourselves why such a convoluted statement might be true.

We’ll do this by looking at a specific example of a $F$ that satisfies the conditions. Why is each condition essential? Why would $F$ satisfy the conclusion? Could we generalize from our example?

Let’s find a F.

The simplest thing to do would be to take $g(x)=\frac{1}{x^2}$. (Technically we have to take something else around $x=0$ but let’s not worry about this; we’re just trying to get some intuition.) Then $\nabla F(u,v)$ is parallel to $\langle \frac{1}{u^2},-\frac{1}{v^2}\rangle$. Integrating against $u$ and $v$, we find that one possibility for $F$ is $F(u,v)=\frac{1}{v}-\frac{1}{u}$. The problem claims that $\min_{i\ne j} |\frac{1}{x_j}-\frac{1}{x_i}|\le \frac{C}{n}$. Is this true? Let’s suppose all the $x_i$ are at least 1 (we didn’t define $g$ very well around $x=0$). Suppose $x_1\le x_2\le\cdots \le x_{n+1}$. Then $|\frac{1}{x_{i}}-\frac{1}{x_{i+1}}|$ add up to $|\frac{1}{x_1}-\frac{1}{x_{n+1}}|<1$ by telescoping. So one of the differences must be at most $\frac{1}{n}$. We can just take $C=1$.

What was essential here?

The fact that the integral of $\frac{1}{x^2}$ is $-\frac{1}{x}$, which converges as $x\to \infty$. In general, the condition $x^2g(x)\le 1$, or $g(x)\le \frac{1}{x^2}$, forces the antiderivative $G(t):=\int_0^{t} g(x)\,dx\le\int_0^{\pm 1} g(x)\,dx + \int_{\pm 1}^{t} \frac{1}{x^2}\,dx$ to converge as $t\to \pm \infty$. One possibility for $F$ is $G(u)-G(v)$. Then our argument would go through as above: again, we have by telescoping

$\sum_{i=1}^{n} |G(x_i)-G(x_{i+1})|=|G(x_1)-G(x_{n+1})|<|G(\infty)-G(-\infty)|$

where $G(\pm \infty ):=\lim_{t\to \pm\infty} G(t)$. Thus letting $C=G(\infty)-G(-\infty)$ we find that $\min_{i\ne j}|F(x_i,x_j)|\le \frac{C}{n}$.

But we’re just getting started…

We now have some idea why the statement would be true. However, we have not solved the problem at all! We took a $F$ such that $\nabla F(u,v)=\langle g(v),-g(u)\rangle$. We need to prove it for all $F$ such that $\nabla F(u,v)\parallel \langle g(v),-g(u)\rangle$. This means the gradient could be scaled by an arbitrary number depending on $u,v$:

$\nabla F(u,v)=\langle g(v)h(u,v),-g(u)h(u,v)\rangle$.

This $h$ would mess up any way to write $F$ as a difference of a function in $u$ and $v$ as above. What do we do?

(Thus we see that to solve our problem, we have to give at least a partial answer to the question: given only that the gradient field of a function is parallel to a given vector field, rather than the gradient field itself, how do we recover the function?)

A condition on gradient fields gives a condition on h

It’s clear that we need to understand what $h$ could be. Let’s find some condition on $h$. We know that in order for  some vector field $\langle a(u,v),b(u,v)\rangle$ to be a gradient field, we must have

$\frac{\partial a}{\partial v}=\frac{\partial b}{\partial u}.$

(This fact comes from the fact that for a twice continuously differentiable function $F$, $\frac{\partial F}{\partial u\partial v}=\frac{\partial F}{\partial v\partial u}$.)

Applying this to $\nabla F(u,v)=\langle g(v)h(u,v),-g(u)h(u,v)\rangle$ gives

$g(v)\frac{\partial h}{\partial v}=-g(u)\frac{\partial h}{\partial u},$

$g(v)\frac{\partial h}{\partial v}+g(u)\frac{\partial h}{\partial u}=0.\qquad (1)$

We can’t “solve” this PDE… or can we?

I got stuck here for a very long time. The basic problem is that it seems like “too many” functions $h$ solve this equation. After all, we have a PDE in two variables, but we only have 1 equation relating them. How can we hope to say anything about $h$?

The idea is that $h$ would have a very general form. We take as inspiration the wave equation

$u_{xx}-c^2u_{yy}=0$

which has as a general solution the traveling wave $u(x,y)=g(x-ct)$ where $g$ is any “nice” function. The equation is not enough for us to give a very explicit solution, but we’ve still managed to describe all solutions: they must be functions in terms of the quantity $x-ct$!

Can we do the same here? Is $h$ a function in some expression? What would be a natural choice? The equation for $h$ looks actually a lot like the gradient equation for $F$. Of course, $h=1$ is a solution. Playing around a bit, we find $h(u,v)=G(u)-G(v)$ is a solution—look familiar? Let’s guess that $h$ a function in $G(u)-G(v)$, i.e., we’ll try to prove $h(u,v)=w(G(u)-G(v))$ for some function $w$.

This is the key observation for the problem.

h is a function in G(u)-G(v) because G(u)-G(v)=k are the level lines

Saying that $h(u,v)=w(G(u)-G(v))$ for some function $w$ is the same as saying that the value of $h$ depends only on the value of $G(u)-G(v)$. Why would this be the case? (If the above ideas were kind of unmotivated, hopefully our proof now will be enlightening!) Another way of saying this is that $h$ doesn’t change if we move along the curve $G(u)-G(v)=k$ for $k$ constant.

In fact, (1) is exactly telling us that $h$ doesn’t change along a certain direction: it says that

$\langle g(v),g(u)\rangle \cdot \nabla h=0,\qquad (2)$

i.e., the directional derivative of $h$ in the direction $\langle g(v),g(u)\rangle$ is 0. Now $G(u)-G(v)=k$ are exactly the integral curves of $\langle g(v),g(u)\rangle$!*** Indeed, implicitly differentiating $G(u)-G(v)=k$ gives $\frac{\partial v}{\partial u}=\frac{g(u)}{g(v)}$.

Suppose we move along $G(u)-G(v)=k$ from $u_0$ to $u_1$ with unit speed in the $u$ direction. Let this path be $s$. How does $h$ change? Using (2),

$h(u_1,v_1)-h(u_0,v_0)=\int_{u_0}^{u_1} \nabla h\cdot ds=\int_{u_0}^{u_1} \nabla h \cdot \langle 1,\frac{g(u)}{g(v)}\rangle=0$.

Since $G(u)-G(v)=k$ is connected (see below), this shows $h$ is a function of $G(u)-G(v)$. We can write

$h(u,v)=w(G(u)-G(v))$

for some function $w$.

***(We should really check some things here. Note $G(u)-G(v)=k$ is an at most single-valued function of $v$. Indeed, fixing a $v$, $G(u)-G(v)$ is a strictly increasing function of $u$ because $G$ is the integral of $g>0$. There is at most one value of $u$ that works. Moreover, the curve $G(u)-G(v)=k$ is connected. Indeed, if $(u_1,v_1)$ and $(u_2,v_2)$ are points on the curve, then for any $u_1 we have $G(u)-G(v_1)>G(u_1)-G(v_1)=k=G(u_2)-G(v_2)>G(u)-G(v_2)$, so by the Intermediate Value Theorem, there is a solution to $G(u)-G(v)=k$. Moreover, continuity considerations show that $v$ depends on $u$ continuously. Or you can probably just argue by taking the derivative.)

Now finish.

We’ve gotten through the hard part: we know what form $h$ has to take. We know

$\nabla F(u,v)=w(G(u)-G(v))\langle g(u),-g(v)\rangle.$

Since we have an expression for the gradient field, we can now find $F$ up to a constant, in terms of this function $w$. Let $W(t)=\int_0^t w(x)\,dx$ be the antiderivative of $w$. Then

$F(u,v)=W(G(u)-G(v))+K$

for some $K$. But the condition $F(u,u)=0$ actually gives $K=0$ (we have $W(0)=0$ by choice of antiderivative).

Now suppose $x_1\le \cdots \le x_{n+1}$. Again, we note $G$ is increasing and

$\sum_{i=1}^n G(x_{i+1})-G(x_i)

This means that $G(x_{i+1})-G(x_i)<\frac{G(\infty)-G(-\infty)}{n}$ for some $i$. Then

$|F(x_i,x_{i+1})|=|W(G(x_{i+1})-G(x_i))|<\max_{|x|<\frac{G(\infty)-G(-\infty)}{n}}|W(x)|.$

Because $W$ has continuous derivative, on $|x|<\frac{G(\infty)-G(-\infty)}{n}$ this derivative has a maximum, say $M$. Then $|W(x)|=|W(x)-W(0)|\le xM$. Hence

$|F(x_i,x_{i+1})|\le \frac{[G(\infty)-G(-\infty)]M}{n}.$

We let $C=[G(\infty)-G(-\infty)]M$ and we are done.