A remark on the Kakeya needle problem

In 1917, Soichi Kakeya posed the following problem:

Kakeya needle problem. What is the least amount of area required to continuously rotate a unit line segment in the plane by a full rotation (i.e. by )?

In 1928, Besicovitch showed that given any , there exists a planar set of area at most within which a unit needle can be continuously rotated; the proof relies on the construction of what is now known as a Besicovitch set – a set of measure zero in the plane which contains a unit line segment in every direction.  So the answer to the Kakeya needle problem is “zero”.

I was recently asked (by Claus Dollinger) whether one can take ; in other words,

Question. Does there exist a set of measure zero within which a unit line segment can be continuously rotated by a full rotation?

This question does not seem to be explicitly answered in the literature.  In the papers of von Alphen and of Cunningham, it is shown that it is possible to continuously rotate a unit line segment inside a set of arbitrarily small measure and of uniformly bounded diameter; this result is of course implied by a positive answer to the above question (since continuous functions on compact sets are bounded), but the converse is not true.

Below the fold, I give the answer to the problem… but perhaps readers may wish to make a guess as to what the answer is first before proceeding, to see how good their real analysis intuition is.  (To partially prevent spoilers for those reading this post via RSS, I will be whitening the text; you will have to highlight the text in order to see it.  Unfortunately, I do not know how to white out the LaTeX in such a way that it is visible upon highlighting, so RSS readers may wish to stop reading right now; but I suppose one can view the LaTeX as supplying hints to the problem, without giving away the full solution.)

[Update, March 13: a non-whitened version of this article can be found as part of this book.]

Tricks Wiki: Use basic examples to calibrate exponents

Title: Use basic examples to calibrate exponents

Motivation: In the more quantitative areas of mathematics, such as analysis and combinatorics, one has to frequently keep track of a large number of exponents in one’s identities, inequalities, and estimates.  For instance, if one is studying a set of N elements, then many expressions that one is faced with will often involve some power of N; if one is instead studying a function f on a measure space X, then perhaps it is an norm which will appear instead.  The exponent involved will typically evolve slowly over the course of the argument, as various algebraic or analytic manipulations are applied.  In some cases, the exact value of this exponent is immaterial, but at other times it is crucial to have the correct value of at hand.   One can (and should) of course carefully go through one’s arguments line by line to work out the exponents correctly, but it is all too easy to make a sign error or other mis-step at one of the lines, causing all the exponents on subsequent lines to be incorrect.  However, one can guard against this (and avoid some tedious line-by-line exponent checking) by continually calibrating these exponents at key junctures of the arguments by using basic examples of the object of study (sets, functions, graphs, etc.) as test cases.  This is a simple trick, but it lets one avoid many unforced errors with exponents, and also lets one compute more rapidly.

Quick description: When trying to quickly work out what an exponent p in an estimate, identity, or inequality should be without deriving that statement line-by-line, test that statement with a simple example which has non-trivial behaviour with respect to that exponent p, but trivial behaviour with respect to as many other components of that statement as one is able to manage.   The “non-trivial” behaviour should be parametrised by some very large or very small parameter.  By matching the dependence on this parameter on both sides of the estimate, identity, or inequality, one should recover p (or at least a good prediction as to what p should be).

General discussion: The test examples should be as basic as possible; ideally they should have trivial behaviour in all aspects except for one feature that relates to the exponent p that one is trying to calibrate, thus being only “barely” non-trivial.   When the object of study is a function, then (appropriately rescaled, or otherwise modified) bump functions are very typical test objects, as are Dirac masses, constant functions, Gaussians, or other functions that are simple and easy to compute with.  In additive combinatorics, when the object of study is a subset of a group, then subgroups, arithmetic progressions, or random sets are typical test objects.  In graph theory, typical examples of test objects include complete graphs, complete bipartite graphs, and random graphs. And so forth.

This trick is closely related to that of using dimensional analysis to recover exponents; indeed, one can view dimensional analysis as the special case of exponent calibration when using test objects which are non-trivial in one dimensional aspect (e.g. they exist at a single very large or very small length scale) but are otherwise of a trivial or “featureless” nature.   But the calibration trick is more general, as it can involve parameters (such as probabilities, angles, or eccentricities) which are not commonly associated with the physical concept of a dimension.  And personally, I find example-based calibration to be a much more satisfying (and convincing) explanation of an exponent than a calibration arising from formal dimensional analysis.

When one is trying to calibrate an inequality or estimate, one should try to pick a basic example which one expects to saturate that inequality or estimate, i.e. an example for which the inequality is close to being an equality.  Otherwise, one would only expect to obtain some partial information on the desired exponent p (e.g. a lower bound or an upper bound only).  Knowing the examples that saturate an estimate that one is trying to prove is also useful for several other reasons – for instance, it strongly suggests that any technique which is not efficient when applied to the saturating example, is unlikely to be strong enough to prove the estimate in general, thus eliminating fruitless approaches to a problem and (hopefully) refocusing one’s attention on those strategies which actually have a chance of working.

Calibration is best used for the type of quick-and-dirty calculations one uses when trying to rapidly map out an argument that one has roughly worked out already, but without precise details; in particular, I find it particularly useful when writing up a rapid prototype.  When the time comes to write out the paper in full detail, then of course one should instead carefully work things out line by line, but if all goes well, the exponents obtained in that process should match up with the preliminary guesses for those exponents obtained by calibration, which adds confidence that there are no exponent errors have been committed.

Prerequisites: Undergraduate analysis and combinatorics.

Cohomology for dynamical systems

A dynamical system is a space X, together with an action of some group .  [In practice, one often places topological or measure-theoretic structure on X or G, but this will not be relevant for the current discussion.  In most applications, G is an abelian (additive) group such as the integers or the reals , but I prefer to use multiplicative notation here.]  A useful notion in the subject is that of an (abelian) cocycle; this is a function taking values in an abelian group that obeys the cocycle equation

(1)

for all and .  [Again, if one is placing topological or measure-theoretic structure on the system, one would want to be continuous or measurable, but we will ignore these issues.] The significance of cocycles in the subject is that they allow one to construct (abelian) extensions or skew products of the original dynamical system X, defined as the Cartesian product with the group action .  (The cocycle equation (1) is needed to ensure that one indeed has a group action, and in particular that .)  This turns out to be a useful means to build complex dynamical systems out of simpler ones.  (For instance, one can build nilsystems by starting with a point and taking a finite number of abelian extensions of that point by a certain type of cocycle.)

A special type of cocycle is a coboundary; this is a cocycle that takes the form for some function .  (Note that the cocycle equation (1) is automaticaly satisfied if is of this form.)  An extension of a dynamical system by a coboundary can be conjugated to the trivial extension by the change of variables .

While every coboundary is a cocycle, the converse is not always true.  (For instance, if X is a point, the only coboundary is the zero function, whereas a cocycle is essentially the same thing as a homomorphism from G to U, so in many cases there will be more cocycles than coboundaries.  For a contrasting example, if X and G are finite (for simplicity) and G acts freely on X, it is not difficult to see that every cocycle is a coboundary.)  One can measure the extent to which this converse fails by introducing the first cohomology group , where is the space of cocycles and is the space of coboundaries (note that both spaces are abelian groups).  In my forthcoming paper with Vitaly Bergelson and Tamar Ziegler on the ergodic inverse Gowers conjecture (which should be available shortly), we make substantial use of some basic facts about this cohomology group (in the category of measure-preserving systems) that were established in a paper of Host and Kra.

The above terminology of cocycles, coboundaries, and cohomology groups of course comes from the theory of cohomology in algebraic topology.  Comparing the formal definitions of cohomology groups in that theory with the ones given above, there is certainly quite a bit of similarity, but in the dynamical systems literature the precise connection does not seem to be heavily emphasised.   The purpose of this post is to record the precise fashion in which dynamical systems cohomology is a special case of cochain complex cohomology from algebraic topology, and more specifically is analogous to singular cohomology (and can also be viewed as the group cohomology of the space of scalar-valued functions on X, when viewed as a G-module); this is not particularly difficult, but I found it an instructive exercise (especially given that my algebraic topology is extremely rusty), though perhaps this post is more for my own benefit that for anyone else.

Math 245B: Real analysis (course announcement)

Starting on January 5th, the beginning of the winter quarter here at UCLA, I will be teaching Math 245B, a graduate course on real analysis.  As the name suggests, the course is a continuation of the Math 245A course that just concluded in this fall quarter, taught by Jim Ralston, who covered the basics of measure theory and spaces.  In this quarter, I plan to cover more of the foundational theory of graduate real analysis, specifically

• Signed measures, Radon measures and the Radon-Nikodym theorem;
• The general theory of spaces;
• Introduction to functional analysis, particularly the theory of Hilbert spaces and Banach spaces;
• Various aspects of point set topology of relevance to analysis, including Tychonoff’s theorem and the Stone-Weierstrass theorem.

I will be using Folland’s “Real analysis” as a primary text and Stein-Shakarachi’s “Real analysis” as a secondary text.  These two texts already do quite a good job of covering the above material, but it is likely that I will supplement them as the course progresses with my own lecture notes, which I will post here, though I do not intend to make these notes nearly as self-contained and structurally interlinked as my notes on ergodic theory or on the Poincaré conjecture, being supporting material for the main texts rather than a substitute for them.

On multiple choice questions in mathematics

Now that the project to upgrade my old multiple choice applet to a more modern and collaborative format is underway (see this server-side demo and this javascript/wiki demo, as well as the discussion here), I thought it would be a good time to collect my own personal opinions and thoughts regarding how multiple choice quizzes are currently used in teaching mathematics, and on the potential ways they could be used in the future.  The short version of my opinions is that multiple choice quizzes have significant limitations when used in the traditional classroom setting, but have a lot of interesting and underexplored potential when used as a self-assessment tool.

An airport-inspired puzzle

I was recently at an international airport, trying to get from one end of a very long terminal to another.  It inspired in me the following simple maths puzzle, which I thought I would share here:

Suppose you are trying to get from one end A of a terminal to the other end B.  (For simplicity, assume the terminal is a one-dimensional line segment.)  Some portions of the terminal have moving walkways (in both directions); other portions do not.  Your walking speed is a constant , but while on a walkway, it is boosted by the speed of the walkway for a net speed of .  (Obviously, given a choice, one would only take those walkways that are going in the direction one wishes to travel in.)  Your objective is to get from A to B in the shortest time possible.

1. Suppose you need to pause for some period of time, say to tie your shoe.  Is it more efficient to do so while on a walkway, or off the walkway?  Assume the period of time required is the same in both cases.
2. Suppose you have a limited amount of energy available to run and increase your speed to a higher quantity (or , if you are on a walkway).  Is it more efficient to run while on a walkway, or off the walkway?  Assume that the energy expenditure is the same in both cases.
3. Do the answers to the above questions change if one takes into account the various effects of special relativity?  (This is of course an academic question rather than a practical one.  But presumably it should be the time in the airport frame that one wants to minimise, not time in one’s personal frame.)

It is not too difficult to answer these questions on both a rigorous mathematical level and a physically intuitive level, but ideally one should be able to come up with a satisfying mathematical explanation that also corresponds well with one’s intuition.

[Update, Dec 11: Hints deleted, as they were based on an incorrect calculation of mine.]

The uniform uncertainty principle and compressed sensing

This week I am in Seville, Spain, for a conference in harmonic analysis and related topics.  My talk is titled “the uniform uncertainty principle and compressed sensing“.  The content of this talk overlaps substantially with my Ostrowski lecture on the same topic; the slides I prepared for the Seville lecture can be found here.

[Update, Dec 6: Some people have asked about my other lecture given in Seville, on structure and randomness in the prime numbers.  This lecture is largely equivalent to the one posted here.]

Upgrading old Java applets?

This post is going to be of a technological nature rather than a mathematical one.

Several years ago (long before the advent of “Web 2.0“), I wrote a number of Java applets (in Java 1.0!) to illustrate various mathematical operations (e.g. Mobius transforms or honeycombs, the latter being a joint project with Allen Knutson), or to help my undergraduate students self-test their mathematical knowledge (via my multiple choice applet that tested them on several prepared quizzes).  I had generally received quite positive feedback on these (the logic quiz on my multiple choice applet, in particular, seemed to be particularly good at identifying weaknesses in one’s mathematical reasoning skills).  However, being largely self-taught in my programming skills (beyond a handful of undergraduate CS classes), I did not manage to make my code easy to maintain or upgrade, and indeed I have not made any attempt to modernise these applets in any way for many years now.

And now it appears that these applets are slowly becoming incompatible with modern browsers.  (IE7 still seems to run these applets well enough, but my version of Firefox no longer does (in fact, I should warn you that it actually freezes up on some of these applets), and only certain versions of Sun Java Virtual Machine seem to run the applets properly.)  It also appears that the Java language itself has changed over the years; I have found that the most recent Java compilers have some minor issues with some of my old code.

But I would be interested in seeing some version of these applets (or at least the concepts behind these applets) to persist in some more stable and modern form (which presumably would mean using a different language than Java 1.0), as they seem to occupy a niche (viz., interactive demonstrations and testing of higher mathematical concepts) that does not appear to be well represented on the internet today.  Given that I have much less time to devote to these things nowadays, I would be more than happy to somehow donate these applets to some collaborative or open source project that might be able to develop them in some better (and more Web 2.0 compatible) format, but I do not have much experience with these things and am not sure how to proceed.  So I’m asking my technologically inclined readers if they have any suggestions for what to do with these old pieces of code. (I’m particularly interested in building up my multiple choice applet, as this seems well suited to some collaborative project in which multiple contributors can upload their own quizzes on various topics (which need not be restricted to mathematics) that could aid in students who wish to self-test their understanding of a given topic.  And there are various features I would have liked – e.g. support for mathematical symbols – that I simply did not have the time or expertise to put into the applet, but which would have been very nice to have.)  I would particularly prefer suggestions which might require some one-time work on my part, but not a continued obligation to maintain code indefinitely.

[Also, any suggestions for relatively quick fixes that would allow these applets to be runnable on most modern browsers without too much recoding on my part would be greatly appreciated.]