Tricks Wiki: Give yourself an epsilon of room

Today I’d like to discuss (in the Tricks Wiki format) a fundamental trick in “soft” analysis, sometimes known as the “limiting argument” or “epsilon regularisation argument”.

Title: Give yourself an epsilon of room.

Quick description: You want to prove some statement about some object (which could be a number, a point, a function, a set, etc.).  To do so, pick a small , and first prove a weaker statement (which allows for “losses” which go to zero as ) about some perturbed object .  Then, take limits .  Provided that the dependency and continuity of the weaker conclusion on are sufficiently controlled, and is converging to in an appropriately strong sense, you will recover the original statement.

One can of course play a similar game when proving a statement about some object , by first proving a weaker statement on some approximation to for some large parameter N, and then send at the end.

General discussion: Here are some typical examples of a target statement , and the approximating statements that would converge to :

	for some independent of
is finite	is bounded uniformly in
for all (i.e. maximises f)	for all (i.e. nearly maximises f)
converges as	fluctuates by at most o(1) for sufficiently large n
is a measurable function	is a measurable function converging pointwise to
is a continuous function	is an equicontinuous family of functions converging pointwise to OR is continuous and converges (locally) uniformly to
The event holds almost surely	The event holds with probability 1-o(1)
The statement holds for almost every x	The statement holds for x outside of a set of measure o(1)

Of course, to justify the convergence of to , it is necessary that converge to (or converge to , etc.) in a suitably strong sense. (But for the purposes of proving just upper bounds, such as , one can often get by with quite weak forms of convergence, thanks to tools such as Fatou’s lemma or the weak closure of the unit ball.)  Similarly, we need some continuity (or at least semi-continuity) hypotheses on the functions f, g appearing above.

It is also necessary in many cases that the control on the approximating object is somehow “uniform in “, although for “-closed” conclusions, such as measurability, this is not required. [It is important to note that it is only the final conclusion on that needs to have this uniformity in ; one is permitted to have some intermediate stages in the derivation of that depend on in a non-uniform manner, so long as these non-uniformities cancel out or otherwise disappear at the end of the argument.]

By giving oneself an epsilon of room, one can evade a lot of familiar issues in soft analysis.  For instance, by replacing “rough”, “infinite-complexity”, “continuous”,  “global”, or otherwise “infinitary” objects with “smooth”, “finite-complexity”, “discrete”, “local”, or otherwise “finitary” approximants , one can finesse most issues regarding the justification of various formal operations (e.g. exchanging limits, sums, derivatives, and integrals).  [It is important to be aware, though, that any quantitative measure on how smooth, discrete, finite, etc. should be expected to degrade in the limit , and so one should take extreme caution in using such quantitative measures to derive estimates that are uniform in .]  Similarly, issues such as whether the supremum of a function on a set is actually attained by some maximiser become moot if one is willing to settle instead for an almost-maximiser , e.g. one which comes within an epsilon of that supremum M (or which is larger than , if M turns out to be infinite).  Last, but not least, one can use the epsilon room to avoid degenerate solutions, for instance by perturbing a non-negative function to be strictly positive, perturbing a non-strictly monotone function to be strictly monotone, and so forth.

To summarise: one can view the epsilon regularisation argument as a “loan” in which one borrows an epsilon here and there in order to be able to ignore soft analysis difficulties, and can temporarily be able to utilise estimates which are non-uniform in epsilon, but at the end of the day one needs to “pay back” the loan by establishing a final “hard analysis” estimate which is uniform in epsilon (or whose error terms decay to zero as epsilon goes to zero).

A variant: It may seem that the epsilon regularisation trick is useless if one is already in “hard analysis” situations when all objects are already “finitary”, and all formal computations easily justified.  However, there is an important variant of this trick which applies in this case: namely, instead of sending the epsilon parameter to zero, choose epsilon to be a sufficiently small (but not infinitesimally small) quantity, depending on other parameters in the problem, so that one can eventually neglect various error terms and to obtain a useful bound at the end of the day.  (For instance, any result proven using the Szemerédi regularity lemma is likely to be of this type.)  Since one is not sending epsilon to zero, not every term in the final bound needs to be uniform in epsilon, though for quantitative applications one still would like the dependencies on such parameters to be as favourable as possible.

Prerequisites: Graduate real analysis.  (Actually, this isn’t so much a prerequisite as it is a corequisite: the limiting argument plays a central role in many fundamental results in real analysis.)  Some examples also require some exposure to PDE.

245B, Notes 11: The strong and weak topologies

A normed vector space automatically generates a topology, known as the norm topology or strong topology on , generated by the open balls . A sequence in such a space converges strongly (or converges in norm) to a limit if and only if as . This is the topology we have implicitly been using in our previous discussion of normed vector spaces.

However, in some cases it is useful to work in topologies on vector spaces that are weaker than a norm topology. One reason for this is that many important modes of convergence, such as pointwise convergence, convergence in measure, smooth convergence, or convergence on compact subsets, are not captured by a norm topology, and so it is useful to have a more general theory of topological vector spaces that contains these modes. Another reason (of particular importance in PDE) is that the norm topology on infinite-dimensional spaces is so strong that very few sets are compact or pre-compact in these topologies, making it difficult to apply compactness methods in these topologies. Instead, one often first works in a weaker topology, in which compactness is easier to establish, and then somehow upgrades any weakly convergent sequences obtained via compactness to stronger modes of convergence (or alternatively, one abandons strong convergence and exploits the weak convergence directly). Two basic weak topologies for this purpose are the weak topology on a normed vector space , and the weak* topology on a dual vector space . Compactness in the latter topology is usually obtained from the Banach-Alaoglu theorem (and its sequential counterpart), which will be a quick consequence of the Tychonoff theorem (and its sequential counterpart) from the previous lecture.

The strong and weak topologies on normed vector spaces also have analogues for the space of bounded linear operators from to , thus supplementing the operator norm topology on that space with two weaker topologies, which (somewhat confusingly) are named the strong operator topology and the weak operator topology.

Hardy’s uncertainty principle

[This post was typeset using a LaTeX to WordPress-HTML converter kindly provided to me by Luca Trevisan.]

Many properties of a (sufficiently nice) function are reflected in its Fourier transform , defined by the formula

For instance, decay properties of are reflected in smoothness properties of , as the following table shows:

If is…	then is…	and this relates to…
Square-integrable	square-integrable	Plancherel’s theorem
Absolutely integrable	continuous	Riemann-Lebesgue lemma
Rapidly decreasing	smooth	theory of Schwartz functions
Exponentially decreasing	analytic in a strip
Compactly supported	entire and at most exponential growth	Paley-Wiener theorem

Another important relationship between a function and its Fourier transform is the uncertainty principle, which roughly asserts that if a function is highly localised in space, then its Fourier transform must be widely dispersed in space, or to put it another way, and cannot both decay too strongly at infinity (except of course in the degenerate case ). There are many ways to make this intuition precise. One of them is the Heisenberg uncertainty principle, which asserts that if we normalise

then we must have

thus forcing at least one of or to not be too concentrated near the origin. This principle can be proven (for sufficiently nice , initially) by observing the integration by parts identity

and then using Cauchy-Schwarz and the Plancherel identity.

Another well known manifestation of the uncertainty principle is the fact that it is not possible for and to both be compactly supported (unless of course they vanish entirely). This can be in fact be seen from the above table: if is compactly supported, then is an entire function; but the zeroes of a non-zero entire function are isolated, yielding a contradiction unless vanishes. (Indeed, the table also shows that if one of and is compactly supported, then the other cannot have exponential decay.)

On the other hand, we have the example of the Gaussian functions , , which both decay faster than exponentially. The classical Hardy uncertainty principle asserts, roughly speaking, that this is the fastest that and can simultaneously decay:

Theorem 1 (Hardy uncertainty principle) Suppose that is a (measurable) function such that and for all and some . Then is a scalar multiple of the gaussian .

This theorem is proven by complex-analytic methods, in particular the Phragmén-Lindelöf principle; for sake of completeness we give that proof below. But I was curious to see if there was a real-variable proof of the same theorem, avoiding the use of complex analysis. I was able to find the proof of a slightly weaker theorem:

Theorem 2 (Weak Hardy uncertainty principle) Suppose that is a non-zero (measurable) function such that and for all and some . Then for some absolute constant .

Note that the correct value of should be , as is implied by the true Hardy uncertainty principle. Despite the weaker statement, I thought the proof might still might be of interest as it is a little less “magical” than the complex-variable one, and so I am giving it below.

A sharp inverse Littlewood-Offord theorem

Van Vu and I have just uploaded to the arXiv our preprint “A sharp inverse Littlewood-Offord theorem“, which we have submitted to Random Structures and Algorithms.  This paper gives a solution to the (inverse) Littlewood-Offord problem of understanding when random walks are concentrated in the case when the concentration is of polynomial size in the length of the walk; our description is sharp up to epsilon powers of .  The theory of inverse Littlewood-Offord problems and related topics has been of importance in recent developments in the spectral theory of discrete random matrices (e.g. a “robust” variant of these theorems was crucial in our work on the circular law).

For simplicity I will restrict attention to the Bernoulli random walk.  Given real numbers , one can form the random variable

where are iid random signs (with either sign +1, -1 chosen with probability 1/2).  This is a discrete random variable which typically takes values.  However, if there are various arithmetic relations between the step sizes , then many of the possible sums collide, and certain values may then arise with much higher probability.  To measure this, define the concentration probability by the formula

.

Intuitively, this probability measures the amount of additive structure present between the .  There are two (opposing) problems in the subject:

• (Forward Littlewood-Offord problem) Given some structural assumptions on , what bounds can one place on ?
• (Inverse Littlewood-Offord problem) Given some bounds on , what structural assumptions can one then conclude about ?

Ideally one would like answers to both of these problems which come close to inverting each other, and this is the guiding motivation for our paper.

Bounds for the first few density Hales-Jewett numbers, and related quantities

This thread is a continuation of the previous thread here on the polymath1 project.  Currently, activity is focusing on the following problems:

1.  Upper and lower bounds for for small n.

Let be the largest size of a set in without a combinatorial line.  Thanks to efforts from previous threads, we have the first five values of :

.

We also know that , and are working to narrow this further.  The arguments justifying these bounds can be found here.  The latest bounds for the next few values of can be found here.

2.  A hyper-optimistic conjecture

Consider a variant of the above problem in which each element of with a 1s, b 2s, and c 3s is weighted by the factor ; this gives a total weight of .  Let be the largest weight of a line-free set of , and let be the largest size of a subset of

which contains no upward-pointing equilateral triangles with .  It is known that ; the “hyper-optimistic conjecture” is that one in fact has .  This would imply density Hales-Jewett for k=3.

Currently, we know the following values for these sequences:

and

.

There are also some further upper and lower bounds known; see this spreadsheet for the latest bounds, and this page for proofs of the bounds.  The data so far is consistent with the conjecture, but more work would be needed to obtain a more convincing case for it.

3.  Asymptotics for Moser’s cube problem

Moser’s cube problem asks to compute the largest size of a subset of the cube without geometric lines.  The first few values of are known:

.

The best asymptotic lower bound known is .  Given that we have a significantly superior lower bound of for , one might hope to similarly improve the lower bound for Moser’s problem.  But there seems to be a technical snag, based on the observation that between two slices and with the , there are in fact quite a few combinatorial lines connecting them, and so it is not obvious how to create a geometric line-free set that involves more than one slice per value of c-a.

It is also of interest to work out what asymptotic lower bound for one can get for larger values of k than 3.

Comments on this thread should start at 700.  We will also try to record progress made at the polymath1 wiki and at the polymath1 spreadsheet, as appropriate.

A reading seminar on density Hales-Jewett

As part of the polymath1 project, I would like to set up a reading seminar on this blog for the following three papers and notes:

1. H. Furstenberg, Y. Katznelson, “A density version of the Hales-Jewett theorem for k=3“, Graph Theory and Combinatorics (Cambridge, 1988). Discrete Math. 75 (1989), no. 1-3, 227–241.
2. R. McCutcheon, “The conclusion of the proof of the density Hales-Jewett theorem for k=3“, unpublished.
3. H. Furstenberg, Y. Katznelson, “A density version of the Hales-Jewett theorem“, J. Anal. Math. 57 (1991), 64–119.

As I understand it, paper #1 begins the proof of DHJ(3) (the k=3 version of density Hales-Jewett), but the proof is not quite complete, and the notes in #2 completes the proof using ideas from both paper #1 and paper #3.  Paper #3, of course, does DHJ(k) for all k.  For the purposes of the polymath1 project, though, I think it would be best if we focus exclusively on k=3.

While this seminar is of course related in content to the main discussion threads in the polymath1 project, I envision this to be a more sedate affair, in which we go slowly through various sections of various papers, asking questions of each other along the way, and presenting various bits and pieces of the proof.  The papers require a certain technical background in ergodic theory in order to understand, but my hope is that if enough other people (in particular, combinatorialists) ask questions here (and “naive” or “silly” questions are strongly encouraged) then we should be able to make a fair amount of the arguments here accessible.  I also hope that some ergodic theorists who have been intending to read these papers already, but didn’t get around to it, will join with reading the papers with me.

This is the first time I am trying something like this, and so we shall be using the carefully thought out protocol known as “making things up as we go along”.  My initial plan is to start understanding the “big picture” (in particular, to outline the general strategy of proof), while also slowly going through the key stages of that proof in something resembling a linear order.  But I imagine that the focus may change as the seminar progresses.

I’ll start the ball rolling with some initial impressions of paper #1 in the comments below.  As with other threads in this project, I would like all comments to come with a number and title, starting with 600 and then incrementing (the numbers 1-599 being reserved by other threads in this project).

WordPress LaTeX bug collection drive

By and large, I am quite happy with the LaTeX support provided by wordpress, which hosts my blog (and many other maths blogs out there); it is certainly superior to the maths support of most other off-the-shelf blog formats I have looked at. But it does have some annoying bugs and quirks; a lot of perfectly good LaTeX gets converted into “Formula does not parse”.

It occurred to me that maybe one should start a page that collects all the known bugs so that they can be sent at some point to the wordpress programmers to fix. So, here is my initial list of known bugs: any other wordpress users out there are very welcome to contribute their own.

Convention: I will drop the “latex” when I want to show a fragment of LaTeX source code without making it compile, e.g.

$\int_{-\infty}^\infty e^{-\pi x^2}\ dx = 1$ becomes .

[Update, Feb 14: The bugs have now been fixed; see comments below.]

245B, Notes 10: Compactness in topological spaces

One of the most useful concepts for analysis that arise from topology and metric spaces is the concept of compactness; recall that a space is compact if every open cover of has a finite subcover, or equivalently if any collection of closed sets with the finite intersection property (i.e. every finite subcollection of these sets has non-empty intersection) has non-empty intersection. In these notes, we explore how compactness interacts with other key topological concepts: the Hausdorff property, bases and sub-bases, product spaces, and equicontinuity, in particular establishing the useful Tychonoff and Arzelá-Ascoli theorems that give criteria for compactness (or precompactness).

Exercise 1 (Basic properties of compact sets)

• Show that any finite set is compact.
• Show that any finite union of compact subsets of a topological space is still compact.
• Show that any image of a compact space under a continuous map is still compact.

Show that these three statements continue to hold if “compact” is replaced by “sequentially compact”.

Analysis & PDE conferences page

For the last ten years or so, I used to maintain a list of conferences in the area of analysis & PDE (see e.g. this page for a partial archive of this conference list).  However, due to many other demands on my time, I eventually ceased to maintain it, instead passing it over to the Harmonic Analysis and Related Problems (HARP) group that was supported by the European Mathematical Society.  Unfortunately, the EMS funding ran out a few years back, the HARP group dissolved, and so the page drifted for a while.

This week, I talked to my good friend Jim Colliander (who maintains the DispersiveWiki) and he agreed to host a new version of the conferences page on the Wiki, where it can be collaboratively updated.  It is rather sparse right now, but I hope people will contribute to it, either by adding new conferences and related content, or by cleaning up the organisation of existing content.  I have also migrated a list of lecture notes and courses in analysis and PDE which is badly in need of updating.

[One can presumably use the Wiki to also host other items of this nature than just a conference list; any suggestions for expanding the page would also be welcome.]

Proposed stimulus amendment eliminates $1.4 billion in NSF funding

I came across the following news item today which might be of interest to many of the readers of this blog: as part of a bipartisan effort (headed by Sen. Susan Collins (R-ME) and Sen. Ben Nelson (D-NE))  to reduce the size of the U.S. federal government stimulus package (currently at over $900 billion) by about $77 billion, the entire appropriation for the National Science Foundation (NSF) in the package ($1.4 billion – about 0.15% of the entire stimulus package) is being proposed to be eliminated, with significant cuts in related agencies (NASA, DOE office of science, NOAA, etc.).  The $1.4 billion for the NSF in the Senate version of the package is already a reduction from the $2.5 billion allocated in the House version.

For comparison, the entire 2009FY budget for the NSF is $6.9 billion, or about 0.5% of the discretionary federal budget of $1.21 trillion.

[Full disclosure: a majority of my own research funding comes from the NSF.]

[Update, Feb 8: It now appears that $1.2 billion of the funding for the NSF has been restored in a Senate compromise.]

[Update, Feb 12: After the House/Senate reconciliation process, the amount allocated to the NSF has been increased to $3 billion.  Thanks to Alex Iosevich for the link.  See also this Sciencedebate update.]