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<u<u_2 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)<G(\infty)-G(-\infty).

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: