Today, Charlie wrapped up several loose ends in his lectures, including the connection with the classical Whitney extension theorem, the role of convex bodies and Whitney convexity, and a glimpse as to how one obtains the remarkably fast (almost linear time) algorithms in which one actually computes interpolation of functions from finite amounts of data.

With all the notational machinery from the preceding lecture, the Whitney extension theorem can be stated rather cleanly in the language of bundles, sections, and Glaeser-stability as follows. Consider a bundle on a compact set in which every fibre is simply a point: . The Whitney extension problem is then to see whether such bundles have sections. The theorem is then:

Whitney extension theorem. Let be a bundle in which every fibre is a point. Then this bundle has sections if and only if it is Glaeser stable.

It is then clear that the main theorem of the previous lecture generalises the Whitney extension theorem (which represents the case of exactly one stratum, consisting entirely of zero-dimensional fibres). It is then unsurprising that the main tools used to prove the latter theorem (Whitney cubes, smooth partitions of unity, etc.) also come up in the proof of the former. It is also worth noting that Whitney’s proof shows that the map from the polynomials to the section F can be chosen to be linear. In particular, if the set E is finite, one can bound the norm of F by some linear combination of the magnitudes of the coefficients of the polynomials .

In the proof of the Whitney extension theorem, it was necessary to smoothly partition space into cubes, perform some sort of extension on each cube, and then sum everything up. In order to guarantee convergence, it is necessary that the bounds on the extension are (a) uniform in some sense over all cubes, and (b) are stable under multiplication by smooth cutoff functions. It turns out that we can abstract these properties by means of a quantitative generalisation of the notion of a bundle, namely that of a collection of *Whitney convex sets*. Recall that a bundle is a collection , where each is either empty, or takes the form for some and some ideal . Just to belabor the definitions, an ideal is a vector subspace with the property that whenever and .

We can generalise the notion of an ideal as follows. If and $A > 0$, we say that a set is Whitney convex with Whitney constant A if it is a closed convex symmetric set, and if for every we have the ideal-like property

whenever , , and we have the bounds , for .

The point if this rather technical definition is that if a jet is lying in $\sigma(x)$ and it has controlled behaviour at some small length scale , then one can smoothly localise to that scale without causing the jet to escape too much. This is the key property needed for Whitney-type arguments to work. (This is why Whitney-type extension problems are tractable, whereas general linear PDE problems are not; one can glue together local extensions to form a global extension via partitions of unity, whereas one cannot build, say, a globally harmonic function from unrelated locally harmonic pieces.)

There was also a slightly weaker notion of Whitney convexity relating to a modulus of continuity , called Whitney -convexity, which was the same except that the polynomial P had to now obey the bounds instead of .

Charlie then stated the main technical theorem that underpinned all of the results he presented in this lecture series:

Finiteness theorem, full version. Given n, m, a collection of Whitney -convex sets on a compact set with some Whitney constant A and modulus of continuity , and some polynomials , define to be the best constant M such that there exists with norm at most M such that for all . Then there exists a finite subset S of E of cardinality O(1) such that .

(As in the previous talks, all implied constants can depend on n and m.) This generalises the finiteness theorem mentioned in the first talk, by replacing the ideals with Whitney-convex bodies. As mentioned in the second talk, this generalisation turns out to be necessary in the proof, in order for the induction on the number of strata to work properly. The presence of the modulus of continuity prevents any compactness failures, and so E can be infinite here without difficulty.

Charlie didn’t want to discuss the proof of the above finiteness theorem in all of its gory detail. But he did identify the classical finiteness theorem which is in fact the key to the whole argument, namely Helly’s theorem. This theorem asserts that in order to verify the simultaneous satisfiability of an arbitrary number of compact convex constraints in , it suffices to verify satisfiability of n+1 of them at a time. Apparently, one can view the above finiteness theorem as a massively iterated version of Helly’s theorem, together with several other ingredients (such as partitions of unity adapted to Whitney cubes).

Charlie then finished up by briefly discussing the computer science aspects of his work, and in particular the nearly linear-time algorithms used to compute the near-optimal extensions. He did not attempt to discuss the full details of these algorithms, but instead focused on a very simplified model case (which had been extensively studied earlier in the computer science literature, in particular by Callahan-Kosaraju and Arya-Mount-Netanyahu-Silverman-Wu), namely that of efficiently computing the Lipschitz norm

of a function on a finite set of N points. Note that a brute force computation of this Lipschitz norm would take computations. Can one do better?

In one dimension, one can get by in just computations, by first using a sorting algorithm (such as quicksort) to arrange E in order, and then only compute the Lipschitz quotient for *adjacent* x, y, which clearly suffices. But what to do in higher dimensions?

If one is willing to give up a multiplicative error of , then it turns out that there is a technique, called the *well-separated pairs decomposition*, which can compute the Lipschitz norm up to this error in merely computations.

It works like this. By a divide-and-conquer algorithm, one can partition the off-diagonal set into product sets for , where we have the separation condition and the cardinality condition .

Even with this decomposition in hand, it is not entirely obvious how to quickly compute the Lipschitz norm approximately. But there is a neat trick to pull this off. For each product set , pick just one representative and one representative . Then the quantity

which can be computed in time, is certainly a lower bound for . It turns out that it is a pretty good upper bound too; in fact, cannot exceed (say). This can be demonstrated by a clever infinite descent argument. More precisely, suppose for contradiction that the Lipschitz norm was larger than this, then there exist distinct x, y such that

.

On the other hand, we know that there must be some product such that and . Then by definition of K we have

and also

.

Putting all this together using the triangle inequality, we soon see that either

or

,

thus leading to a pair or which also exhibits large Lipschitz norm but which has a smaller separation than . But if we keep iterating this we obtain an infinite descent, which is absurd. This explains how one obtains the nearly linear time computation of the Lipschitz norm; and apparently a similar method also computes higher extension norms.

## 3 comments

Comments feed for this article

17 November, 2007 at 8:22 pm

Michael VanValkenburghThank you for this blog–I am grateful for the summaries of

Professor Fefferman’s lectures, and I am glad that we have this

forum for further discussing them. I would like to take this

opportunity to reframe the question I asked at the end of the

third lecture.

Let me begin by recapping some of the other questions and answers

(forgive me if, in being brief, I misrepresent them–in that case,

please add comments):

Q1: Is the “Whitney convexity condition” a natural condition?

A1: Yes. That sort of thing comes up whenever you have a partition

of unity such that the derivatives of the cutoffs have scales

corresponding to the scales of the sets they are supported on.

This of course comes up in the classical picture for Whitney’s

extension theorem, e.g., on page 17 of Stein’s *Singular Integrals

and Differentiability Properties of Functions*.

Q2: Do the results have consequences for the study of partial

differential equations?

A2: Yes–and recall that *without* the Whitney convexity

condition, the main theorem (a generalized sharp Whitney Theorem

for Whitney $\omega$-convex sets) is false; it would, in

particular, imply that any linear partial differential equation

with any linear boundary conditions is solvable. (See the blog

entry for Professor Fefferman’s second lecture.)

These two questions caused me to think of the theorem of Beals and

Fefferman on the local solvability of linear partial differential

equations of principal type, with smooth coefficients, satisfying

the Nirenberg-Treves condition. The seminal method Beals and

Fefferman devised, which they subsequently generalized, as did

H\”{o}rmander (with the introduction of the Weyl calculus of

pseudodifferential operators), was to introduce “spatially

inhomogeneous” pseudodifferential operators–pseudodifferential

operators where the properties of the corresponding symbols vary

point-to-point in a way that is specialized for the operator at

hand.

This is presented in H\”{o}rmander’s massive book in the following

way: In chapter one, he constructs “partitions of unity

corresponding to a covering by convex symmetric neighborhoods

which may vary in both size and shape” (p.28); as he notes

(p.32), this is essentially due to Whitney. Then, in chapter two,

he uses a partition of unity of this type to prove Whitney’s

extension theorem (p.48); of course, this is also due to Whitney.

However, H\”{o}rmander’s main reason for studying the “spatially

inhomogeneous” partitions of unity is for use in sections 18.4

and 18.5, where he uses them to construct the Weyl

calculus–which, again, was inspired by Beals and Fefferman. The

Weyl calculus provides the framework for the recent work on

solvability, most notably, Dencker’s recent paper on the

resolution of the Nirenberg-Treves conjecture, which generalizes

the result of Beals and Fefferman to classical pseudodifferential

operators of principal type.

I meant for my question to be of a historical nature–for

instance, to ask if the Beals-Fefferman paper was in some way

inspired by the work of Whitney, or if there is some deep

connection between the two areas. But it appears that the answer

to my question is the same as the answer to question 1 above.

18 November, 2007 at 8:43 am

Terence TaoDear Michael,

Thanks for posting the discussion after Charlie’s last talk. As I recall, though, the answer to Q2 was “No” rather than “Yes”, because the Whitney convexity condition is almost never satisfied for a general linear PDE problem. For instance, trying to solve Poisson’s equation does not fall under this framework, basically because the space of harmonic polynomials is not an ideal (nor is it Whitney convex). But the space of polynomials which vanish to (say) third order at a point is an ideal (and hence Whitney convex), which is why the above theory can say something about how to solve for a function which is specified up to third order at various points.

It may be that the Whitney convexity condition is overkill; it requires, at every point, the constraint body to be well-behaved with respect to

everyscale . But from what I gather from the proof, one only needs to know this fact for very specific scales , namely the distance from x to various strata of E. So it could well be possible to proceed instead with a Hormander-type approach, in which one defines scale functions adapted to these strata, and requires that the constraint bodies obey estimates only at those scales (somewhat analogous to the Weyl calculus adapted to a given partition of unity).30 April, 2008 at 10:00 am

The Hahn-Banach theorem, Menger’s theorem, and Helly’s theorem « What’s new[…] 30 November, 2007 in expository, math.CO, math.FA, math.MG by Terence Tao Tags: Hahn-Banach theorem, Helly’s theorem, linear programming, Menger’s theorem, minimax theorem, separation theorem In the previous post, I discussed how an induction on dimension approach could establish Hilbert’s nullstellensatz, which we interpreted as a result describing all the obstructions to solving a system of polynomial equations and inequations over an algebraically closed field. Today, I want to point out that exactly the same approach also gives the Hahn-Banach theorem (at least in finite dimensions), which we interpret as a result describing all the obstructions to solving a system of linear inequalities over the reals (or in other words, a linear programming problem); this formulation of the Hahn-Banach theorem is sometimes known as Farkas’ lemma. Then I would like to discuss some standard applications of the Hahn-Banach theorem, such as the separation theorem of Dieudonné, the minimax theorem of von Neumann, Menger’s theorem, and Helly’s theorem (which was mentioned recently in an earlier post). […]