Tonight it begins:

Stekkjastaur is headed for town.

Be good.

Believe!

In a secret "overwhelming force" project, Foreman-Mackey is resampling all the Kepler Objects of Interest, to produce a full probabilistic catalog. In many low signal-to-noise systems, there are fitting degeneracies (really near-degeneracies). In many of these, the posterior pdf does not accord with our intuitive views about what ought to be going on. We realized that this is because our "flat priors" didn't accord with our real, prior beliefs. That is, there was a disparity between our actual prior beliefs and our coded-up prior function. We knew this would be the case—we are using wrong but simple interim priors that we plan to replace with a hierarchical inference—but it was amusing to be reminded of the the simple point that ugly priors lead to ugly inferences. We made some small changes to the priors, resampled, and our inferences look much better.

If you’re the sort of person who reads this blog, you may have heard that 23andMe—the company that (until recently) let anyone spit into a capsule, send it away to a DNA lab, and then learn basic information about their ancestry, disease risks, etc.—has suspended much of its service, on orders from the US Food and Drug Administration.  As I understand it, on Nov. 25, the FDA ordered 23andMe to stop marketing to new customers (though it can still serve existing customers), and on Dec. 5, the company stopped offering new health-related information to any customers (though you can still access the health information you had before, and ancestry and other non-health information is unaffected).

Of course, the impact of these developments is broader: within a couple weeks, “do-it-yourself genomics” has gone from an industry whose explosive growth lots of commentators took as a given, to one whose future looks severely in doubt (at least in the US).

The FDA gave the reasons for its order in a letter to Ann Wojcicki, 23andMe’s CEO.  Excerpts:

For instance, if the BRCA-related risk assessment for breast or ovarian cancer reports a false positive, it could lead a patient to undergo prophylactic surgery, chemoprevention, intensive screening, or other morbidity-inducing actions, while a false negative could result in a failure to recognize an actual risk that may exist.  Assessments for drug responses carry the risks that patients relying on such tests may begin to self-manage their treatments through dose changes or even abandon certain therapies depending on the outcome of the assessment.  For example, false genotype results for your warfarin drug response test could have significant unreasonable risk of illness, injury, or death to the patient due to thrombosis or bleeding events that occur from treatment with a drug at a dose that does not provide the appropriately calibrated anticoagulant effect …  The risk of serious injury or death is known to be high when patients are either non-compliant or not properly dosed; combined with the risk that a direct-to-consumer test result may be used by a patient to self-manage, serious concerns are raised if test results are not adequately understood by patients or if incorrect test results are reported.

To clarify, the DNA labs that 23andMe uses are already government-regulated.  Thus, the question at issue here is not whether, if 23andMe claims (say) that you have CG instead of CC at some particular locus, the information is reliable.  Rather, the question is whether 23andMe should be allowed to tell you that fact, while also telling you that a recent research paper found that people with CG have a 10.4% probability of developing Alzheimer’s disease, as compared to a 7.2% base rate.  More bluntly, the question is whether ordinary schmoes ought to be trusted to learn such facts about themselves, without a doctor as an intermediary to interpret the results for them, or perhaps to decide that there’s no good reason for the patient to know at all.

Among medical experts, a common attitude seems to be something like this: sure, getting access to your own genetic data is harmless fun, as long as you’re an overeducated nerd who just wants to satisfy his or her intellectual curiosity (or perhaps narcissism).  But 23andMe crossed a crucial line when it started marketing its service to the hoi polloi, as something that could genuinely tell them about health risks.  Most people don’t understand probability, and are incapable of parsing “based on certain gene variants we found, your chances of developing diabetes are about 6 times higher than the baseline” as anything other than “you will develop diabetes.”  Nor, just as worryingly, are they able to parse “your chances are lower than the baseline” as anything other than “you won’t develop diabetes.”

I understand this argument.  Nevertheless, I find it completely inconsistent with a free society.  Moreover, I predict that in the future, the FDA’s current stance will be looked back upon as an outrage, with the subtleties in the FDA’s position mattering about as much as the subtleties in the Church’s position toward Galileo (“look, Mr. G., it’s fine to discuss heliocentrism among your fellow astronomers, as a hypothesis or a calculational tool—just don’t write books telling the general public that heliocentrism is literally true, and that they should change their worldviews as a result!”).  That’s why I signed this petition asking the FDA to reconsider its decision, and I encourage you to sign it too.

Here are some comments that might help clarify my views:

(1) I signed up for 23andMe a few years ago, as did the rest of my family.  The information I gained from it wasn’t exactly earth-shattering: I learned, for example, that my eyes are probably blue, that my ancestry is mostly Ashkenazi, that there’s a risk my eyesight will further deteriorate as I age (the same thing a succession of ophthalmologists told me), that I can’t taste the bitter flavor in brussels sprouts, and that I’m an “unlikely sprinter.”  On the other hand, seeing exactly which gene variants correlate with these things, and how they compare to the variants my parents and brother have, was … cool.  It felt like I imagine it must have felt to buy a personal computer in 1975.  In addition, I found nothing the slightest bit dishonest about the way the results were reported.  Each result was stated explicitly in terms of probabilities—giving both the baseline rate for each condition, and the rate conditioned on having such-and-such gene variant—and there were even links to the original research papers if I wanted to read them myself.  I only wish that I got half as much context and detail from conventional doctor visits—or for that matter, from most materials I’ve read from the FDA itself.  (When Dana was pregnant, I was pleasantly surprised when some of the tests she underwent came back with explicit probabilities and base rates.  I remember wishing doctors would give me that kind of information more often.)

(2) From my limited reading and experience, I think it’s entirely possible that do-it-yourself genetic testing is overhyped; that it won’t live up to its most fervent advocates’ promises; that for most interesting traits there are just too many genes involved, via too many labyrinthine pathways, to make terribly useful predictions about individuals, etc.  So it’s important to me that, in deciding whether what 23andMe does should be legal, we’re not being asked to decide any of these complicated questions!  We’re only being asked whether the FDA should get to decide the answers in advance.

(3) As regular readers will know, I’m far from a doctrinaire libertarian.  Thus, my opposition to shutting down 23andMe is not at all a corollary of reflexive opposition to any government regulation of anything.  In fact, I’d be fine if the FDA wanted to insert a warning message on 23andMe (in addition to the warnings 23andMe already provides), emphasizing that genetic tests only provide crude statistical information, that they need to be interpreted with care, consult your doctor before doing anything based on these results, etc.  But when it comes to banning access to the results, I have trouble with some of the obvious slippery slopes.  E.g., what happens when some Chinese or Russian company launches a competing service?  Do we ban Americans from mailing their saliva overseas?  What happens when individuals become able just to sequence their entire genomes, and store and analyze them on their laptops?  Do we ban the sequencing technology?  Or do we just ban software that makes it easy enough to analyze the results?  If the software is hard enough to use, so only professional biologists use it, does that make it OK again?  Also, if the FDA will be in the business of banning genomic data analysis tools, then what about medical books?  For that matter, what about any books or websites, of any kind, that might cause someone to make a poor medical decision?  What would such a policy, if applied consistently, do to the multibillion-dollar alternative medicine industry?

(4) I don’t understand the history of 23andMe’s interactions with the FDA.  From what I’ve read, though, they have been communicating for five years, with everything 23andMe has said in public sounding conciliatory rather than defiant (though the FDA has accused 23andMe of being tardy with its responses).  Apparently, the key problem is simply that the FDA hasn’t yet developed a regulatory policy specifically for direct-to-consumer genetic tests.  It’s been considering such a policy for years—but in the meantime, it believes no one should be marketing such tests for health purposes before a policy exists.  Alas, there are very few cases where I’d feel inclined to support a government in saying: “X is a new technology that lots of people are excited about.  However, our regulatory policies haven’t yet caught up to X.  Therefore, our decision is that X is banned, until and unless we figure out how to regulate it.”  Maybe I could support such a policy, if X had the potential to level cities and kill millions.  But when it comes to consumer DNA tests, this sort of preemptive banning seems purposefully designed to give wet dreams to Ayn Rand fans.

(5) I confess that, despite everything I’ve said, my moral intuitions might be different if dead bodies were piling up because of terrible 23andMe-inspired medical decisions.  But as far as I know, there’s no evidence so far that even a single person was harmed.  Which isn’t so surprising: after all, people might run to their doctor terrified about something they learned on 23onMe, but no sane doctor would ever make a decision solely on that basis, without ordering further tests.

Monarch butterfly handbag (src)

US biologist Randy Schekman, who shared this year’s physiology and medicine Nobel prize, has made prompt use of his new bully pulpit. In

How journals like Nature, Cell and Science are damaging science: The incentives offered by top journals distort science, just as big bonuses distort banking

he singled out these “luxury” journals as a particularly harmful part of the current milieu in which “the biggest rewards follow the flashiest work, not the best,” and he vowed no longer to publish in them. An accompanying Guardian article includes defensive quotes from representatives of Science and Nature, especially in response to Schekman’s assertions that the journals favor controversial articles over boring but scientifically more important ones like replication studies, and that they deliberately seek to boost their impact factors by restricting the number of articles published, “like fashion designers who create limited-edition handbags or suits.”  Focusing on journals, his main concrete suggestion is to increase the role of open-access online journals like his elife, supported by philanthropic foundations rather than subscriptions. But Schekman acknowledges that blame extends to funding organizations and universities, which use publication in high-impact-factor journals as a flawed proxy for quality, and to scientists who succumb to the perverse incentives to put career advancement ahead of good science.  Similar points were made last year in Serge Haroche’s thoughtful piece on why it’s harder to do good science now than in his youth.   This, and Nature‘s recent story on Brazilian journals’ manipulation of impact factor statistics, illustrate how prestige journals are part of the solution as well as the problem.

Weary of people and institutions competing for the moral high ground in a complex terrain, I sought a less value-laden approach,  in which scientists, universities, and journals would be viewed merely as interacting IGUSes (information gathering and utilizing systems), operating with incomplete information about one another. In such an environment, reliance on proxies is inevitable, and the evolution of false advertising is a phenomenon to be studied rather than disparaged.  A review article on biological mimicry introduced me to some of the refreshingly blunt standard terminology of that field.  Mimicry,  it said,  involves three roles:  a model,  i.e.,  a living or material agent emitting perceptible signals, a mimic that plagiarizes the model, and a dupe whose senses are receptive to the model’s signal and which is thus deceived by the mimic’s similar signals.  As in human affairs, it is not uncommon for a single player to perform several of these roles simultaneously.

(This is an extended blog post version of my talk “Ultraproducts as a Bridge Between Discrete and Continuous Analysis” that I gave at the Simons institute for the theory of computing at the workshop “Neo-Classical methods in discrete analysis“. Some of the material here is drawn from previous blog posts, notably “Ultraproducts as a bridge between hard analysis and soft analysis” and “Ultralimit analysis and quantitative algebraic geometry“‘. The text here has substantially more details than the talk; one may wish to skip all of the proofs given here to obtain a closer approximation to the original talk.)

Discrete analysis, of course, is primarily interested in the study of discrete (or “finitary”) mathematical objects: integers, rational numbers (which can be viewed as ratios of integers), finite sets, finite graphs, finite or discrete metric spaces, and so forth. However, many powerful tools in mathematics (e.g. ergodic theory, measure theory, topological group theory, algebraic geometry, spectral theory, etc.) work best when applied to continuous (or “infinitary”) mathematical objects: real or complex numbers, manifolds, algebraic varieties, continuous topological or metric spaces, etc. In order to apply results and ideas from continuous mathematics to discrete settings, there are basically two approaches. One is to directly discretise the arguments used in continuous mathematics, which often requires one to keep careful track of all the bounds on various quantities of interest, particularly with regard to various error terms arising from discretisation which would otherwise have been negligible in the continuous setting. The other is to construct continuous objects as limits of sequences of discrete objects of interest, so that results from continuous mathematics may be applied (often as a “black box”) to the continuous limit, which then can be used to deduce consequences for the original discrete objects which are quantitative (though often ineffectively so). The latter approach is the focus of this current talk.

The following table gives some examples of a discrete theory and its continuous counterpart, together with a limiting procedure that might be used to pass from the former to the latter:

As the above table illustrates, there are a variety of different ways to form a limiting continuous object. Roughly speaking, one can divide limits into three categories:

• Topological and metric limits. These notions of limits are commonly used by analysts. Here, one starts with a sequence (or perhaps a net) of objects in a common space , which one then endows with the structure of a topological space or a metric space, by defining a notion of distance between two points of the space, or a notion of open neighbourhoods or open sets in the space. Provided that the sequence or net is convergent, this produces a limit object , which remains in the same space, and is “close” to many of the original objects with respect to the given metric or topology.
• Categorical limits. These notions of limits are commonly used by algebraists. Here, one starts with a sequence (or more generally, a diagram) of objects in a category , which are connected to each other by various morphisms. If the ambient category is well-behaved, one can then form the direct limit or the inverse limit of these objects, which is another object in the same category , and is connected to the original objects by various morphisms.
• Logical limits. These notions of limits are commonly used by model theorists. Here, one starts with a sequence of objects or of spaces , each of which is (a component of) a model for given (first-order) mathematical language (e.g. if one is working in the language of groups, might be groups and might be elements of these groups). By using devices such as the ultraproduct construction, or the compactness theorem in logic, one can then create a new object or a new space , which is still a model of the same language (e.g. if the spaces were all groups, then the limiting space will also be a group), and is “close” to the original objects or spaces in the sense that any assertion (in the given language) that is true for the limiting object or space, will also be true for many of the original objects or spaces, and conversely. (For instance, if is an abelian group, then the will also be abelian groups for many .)

The purpose of this talk is to highlight the third type of limit, and specifically the ultraproduct construction, as being a “universal” limiting procedure that can be used to replace most of the limits previously mentioned. Unlike the topological or metric limits, one does not need the original objects to all lie in a common space in order to form an ultralimit ; they are permitted to lie in different spaces ; this is more natural in many discrete contexts, e.g. when considering graphs on vertices in the limit when goes to infinity. Also, no convergence properties on the are required in order for the ultralimit to exist. Similarly, ultraproduct limits differ from categorical limits in that no morphisms between the various spaces involved are required in order to construct the ultraproduct.

With so few requirements on the objects or spaces , the ultraproduct construction is necessarily a very “soft” one. Nevertheless, the construction has two very useful properties which make it particularly useful for the purpose of extracting good continuous limit objects out of a sequence of discrete objects. First of all, there is Łos’s theorem, which roughly speaking asserts that any first-order sentence which is asymptotically obeyed by the , will be exactly obeyed by the limit object ; in particular, one can often take a discrete sequence of “partial counterexamples” to some assertion, and produce a continuous “complete counterexample” that same assertion via an ultraproduct construction; taking the contrapositives, one can often then establish a rigorous equivalence between a quantitative discrete statement and its qualitative continuous counterpart. Secondly, there is the countable saturation property that ultraproducts automatically enjoy, which is a property closely analogous to that of compactness in topological spaces, and can often be used to ensure that the continuous objects produced by ultraproduct methods are “complete” or “compact” in various senses, which is particularly useful in being able to upgrade qualitative (or “pointwise”) bounds to quantitative (or “uniform”) bounds, more or less “for free”, thus reducing significantly the burden of “epsilon management” (although the price one pays for this is that one needs to pay attention to which mathematical objects of study are “standard” and which are “nonstandard”). To achieve this compactness or completeness, one sometimes has to restrict to the “bounded” portion of the ultraproduct, and it is often also convenient to quotient out the “infinitesimal” portion in order to complement these compactness properties with a matching “Hausdorff” property, thus creating familiar examples of continuous spaces, such as locally compact Hausdorff spaces.

Ultraproducts are not the only logical limit in the model theorist’s toolbox, but they are one of the simplest to set up and use, and already suffice for many of the applications of logical limits outside of model theory. In this post, I will set out the basic theory of these ultraproducts, and illustrate how they can be used to pass between discrete and continuous theories in each of the examples listed in the above table.

Apart from the initial “one-time cost” of setting up the ultraproduct machinery, the main loss one incurs when using ultraproduct methods is that it becomes very difficult to extract explicit quantitative bounds from results that are proven by transferring qualitative continuous results to the discrete setting via ultraproducts. However, in many cases (particularly those involving regularity-type lemmas) the bounds are already of tower-exponential type or worse, and there is arguably not much to be lost by abandoning the explicit quantitative bounds altogether.

— 1. Basic theory —

To set up the machinery of ultraproducts (and nonstandard analysis) we will need to pick a non-principal ultrafilter on the natural numbers . By definition, this is a collection of subsets of the natural numbers that obeys the following axioms:

• (i) contains , but does not contain .
• (ii) If is in , then any subset of containing is in .
• (iii) If lie in , then also lies in .
• (iv) If , then exactly one of and lies in .
• (v) No finite set lies in .

A collection that obeys axioms (i)-(iii) is a filter, a collection that obeys (i)-(iv) is an ultrafilter, and a collection that obeys (i)-(v) is a non-principal ultrafilter. (One can certainly build ultrafilters on other sets than the natural numbers , but for the type of applications we have in mind, ultrafilters on are generally sufficient, much as how one can largely rely on sequences instead of nets when using considering topological or metric notions of a limit in concrete applications.)

If is an ultrafilter, a subset of is said to be -large if it lies in , and -small otherwise. To emphasise the limit interpretation of ultrafilters, we will also use “for sufficiently close to ” as a synonym for “for an -large set of “. Note from the above axioms that if is partitioned into finitely many components, then exactly one of these components is -large. One can thus think of an ultrafilter as a voting protocol, which converts the preferences of a countably infinite number of voters (indexed by the natural numbers) amongst a finite number of candidates into a “winner”, namely the candidate who amasses an -large set of votes; this voting protocol obeys all the hypotheses of Arrow’s theorem (rationality, independence of irrelevant alternatives, etc.) but not its conclusion (there are no dictators), due to the infinite number of voters. One can also view an ultrafilter as a finitely additive, -valued probability measure on the natural numbers, in which every subset of is measurable.

Every natural number defines a principal ultrafilter (that is, an ultrafilter that does not obey axiom (v)), defined by setting if and only if . By abuse of notation, we may identify with , so that the set of principal ultrafilters is identified with . The set of all ultrafilters (principal and non-principal) is denoted , and may be identified with the Stone-Cech compactification of the natural numbers; this space has a number of interesting structures on it (for instance, it is a left-continuous topological semigroup, which is a useful fact in Ramsey theory and topological dynamics, as discussed in this previous post), but we will not discuss these structures further here. In particular, the use of ultrafilters in establishing correspondence principles between discrete and continuous structures is unrelated to the use of ultrafilters (particularly minimal or idempotent ultrafilters) in Ramsey theory and topological dynamics that is discussed in that previous post. (However, it is certainly possible to use both types of ultrafilters in separate places for a single application; see this paper of Bergelson and myself for an example.)

The existence of a non-principal ultrafilter can be guaranteed by an application of Zorn’s lemma (basically by running the transfinite version of a greedy algorithm to build the collection of -large and -small sets):

Lemma 1 There exists a non-principal ultrafilter .

Proof: Define the Frechet filter to be the collection of all the cofinite subsets of , that is to say those subsets of whose complement is finite. This is a filter. A routine application of Zorn’s lemma shows that this filter must be contained in at least one maximal filter . If is not an ultrafilter, then there is a set which is neither -large or -small; if we then let be the filter generated by and (that is, consists of those subsets of that either lie in , or contain the intersection of with an -large set), then one checks that is a filter that is strictly larger than , contradicting the maximality of . Thus is an ultrafilter; since it contains , it is non-principal as required.

Remark 1 The above argument relied upon the axiom of choice. One can construct ultrafilters using slightly weaker set-theoretic axioms than the axiom of choice (e.g. the Boolean prime ideal theorem), but if one has no choice-like axioms whatsoever (or more precisely, one uses just the axioms ZF of Zermelo-Fraenkel set theory) then the existence of ultrafilters is undecidable. However, there is a result of Gödel that asserts that if a result is finitary in the sense that it can be phrased as a first-order statement in Peano Arithmetic, and it can be proven using the axiom of choice (or more precisely in ZFC set theory), then it can also be proven without the axiom of choice (i.e. in ZF set theory). In practical terms, this means that one can ignore the reliance on the axiom of choice for any finitary application of ultraproduct methods. Alternatively, instead of using Zorn’s lemma to construct a genuine ultrafilter, it is often possible (though messy) to build some sort of “partial” or “incomplete” ultrafilter which is still close enough to an ultrafilter to prove a desired result, but which does not need the full strength of the axiom of choice to construct. We will not discuss such methods here, but see e.g. this paper of Palmgren. (See also this previous blog post for a “cheap” version of nonstandard analysis which uses the Frechet filter rather than an ultrafilter.) In any event, we will freely rely on the axiom of choice in the rest of this post.

Henceforth, we select a single non-principal ultrafilter to use in the rest of the post. The choice of this ultrafilter is highly non-unique ( is uncountable), but for the purposes of establishing a correspondence between discrete and continuous mathematics, the precise choice of ultrafilter will not be relevant, as long as it is kept fixed throughout the discussion.

We can use the ultrafilter to form limits of sequences , even if these sequences have no limit in the topological or metric senses. For instance, if takes values in a single finite space for all natural numbers , then we can define the ultralimit to be the unique element of such that for sufficiently close to ; this element exists and is unique by the ultrafilter axioms (i)-(iv). For instance, the ultralimit of the sequence is either or , with the former occurring if the even numbers are -large, and the latter occurring if the odd numbers are -large. So the ultralimit here depends on , but once is fixed, the ultralimit is well-defined. One can also view as the outcome of an “election” among candidates in , in which each “voter” has as a preferred candidate, and the ultrafilter is used as the election protocol. (See this previous post for further discussion of this viewpoint.)

Now we consider the more general situation in which the to not lie in a single finite space , but instead each lies in a space which may depend on , and may also be infinite. Here, there does not necessarily exist a single object that is equal to the for sufficiently close to . The situation here is similar to that in metric spaces, in that a Cauchy sequence in a metric space need not be convergent if the space is infinite. In the latter case, the problem can be resolved by constructing the metric completion of , which can be defined (slightly non-rigorously) as the space of formal limits of Cauchy sequences , with two formal limits , declared to be equal if converges to zero (in the classical sense) as . To construct this Cauchy completion rigorous within the framework of set theory, one can define to be the set of equivalence classes of tuples of Cauchy sequences in , with the equivalence relation holding if and only if converges to zero as . In order to view as a subset of its completion , one usually identifies each point with the equivalence class of the corresponding constant sequence . With this construction, one can for instance build the real numbers as the metric completion of the rationals (and this is indeed one of the most popular ways to construct the reals, which is often covered in undergraduate analysis classes). Note though while one can use this set-theoretic machinery of equivalence classes of Cauchy sequences of rationals to construct the reals, for the purposes of using the real numbers for mathematical applications, this set-theoretic construction is not relevant; the only thing one needs to retain is that Cauchy sequences of rationals (or of reals) will converge to a real, and conversely every real is the limit of a Cauchy sequence of rationals.

We can take a similar tack to construct ultralimits of sequences in different spaces . If one is willing to be slightly non-rigorous, the definition is almost the same: we can view these ultralimits as formal objects, with two ultralimits and declared to be equal if and only if for sufficiently close to . To do things rigorously within the framework of set theory, one has to take a little extra care to avoid the set-theoretic issues associated to Russell’s paradox (or more precisely, avoiding the uses of proper classes that are too large to be sets). One way to deal with this is as follows. One can postulate the existence of a standard universe that contains all the objects of interest for one’s particular mathematical problem: for instance, if one is interested in a sequence of groups , then might contain all the elements of all of the . The only requirements we make of this standard universe are that (a) it is a set (rather than a proper class), and (b) it is fixed throughout the mathematical discussion. The former requirement means that , in general, cannot contain all spaces of a particular type; for instance, one cannot make contain all groups, all vector spaces, all graphs, etc., as one would soon run into Russell-type paradoxes if this occurred. However, in practice, for any given mathematical problem (other than those arising within mathematical logic), one usually does not need to work simultaneously with all spaces; usually a much smaller number of spaces, e.g. a countable or uncountable family of such spaces, will suffice. Henceforth we will take the existence of a standard universe for granted. Elements of this universe will be referred to as standard objects, and subsets of the universe as standard spaces; for instance, we will usually place the classical number systems , etc. inside this standard universe, so elements of become standard natural numbers, elements of become standard reals, and so forth. We then have:

Definition 2 (Formal definition of ultralimits and ultraproducts) Let be a sequence of standard objects, defined for an -large set (thus for all ). The ultralimit is then defined to be the equivalence class of tuples of standard objects defined on an -large set , such that for sufficiently close to in the common domain of definition. Such an ultralimit is called a nonstandard object, and the set of all ultralimits is called the nonstandard universe . We identify every standard object with the nonstandard object , thus embedding in .

Given a sequence of standard spaces (i.e. subsets of ) defined for sufficiently close to , the ultraproduct is defined as the set of all ultralimits , where lies in for an -large set of . Such an ultraproduct (which is a subset of ) will be called a nonstandard space (also known as an internal space). Similarly, the ultraproduct of a sequence of standard groups will be called a nonstandard group (or internal group), the ultraproduct of a sequence of standard fields will be called a nonstandard field (or internal field), and so forth.

If is a standard space, the nonstandard space (that is, the space of ultralimits of sequences in ) will be called the ultrapower of and is denoted ; note that embeds as a subset of . The ultrapower of the standard natural numbers will be referred to as the nonstandard natural numbers, the ultrapower of the standard reals will be referred to as the nonstandard real numbers (also known as the umber), and so forth.

One can verify that when is finite, the ultrapower is equal to itself, and that the notion of an ultralimit in the case when all the lie in corresponds to the notion of an ultralimit defined previously.

The basic ontological Venn diagram is this: the standard universe embeds into the larger nonstandard universe , and both exist inside the even larger “external universe” of ZFC set theory, which we will not give a name to (it is not a set, but is instead a proper class). This allows us to study various mathematical objects on three different levels: standard, nonstandard, and external. For instance, we have standard groups (groups in ) and nonstandard groups (ultraproducts of groups in ); both are examples of external groups (groups that are somewhere in the external universe), but there are certainly examples of external groups that are neither standard groups nor nonstandard groups. It is also worth cautioning that while we identify standard objects with their nonstandard counterparts , we do not identify standard spaces with their nonstandard counterparts ; in particular, we do not view standard groups as examples of nonstandard groups (except in the finite case), nor do we view standard fields as examples of nonstandard fields, etc. Instead, one can view the nonstandard space as a “completion” of the standard space , analogous to metric completion; see this previous blog post for further discussion of this perspective. A related perspective is to view as a double-precision version of , so for instance can be viewed as the space of “double-precision real numbers” as opposed to the “single-precision” real numbers in , or similarly may be viewed as a space of “long integers“, with being a space of “short integers”.

The analogues of standard groups, nonstandard groups, and external groups in finitary mathematics would be “groups that do not depend on an asymptotic parameter “, “groups that may depend on an asymptotic parameter “, and “informal group-like objects (such as the “group” of all “bounded” integers ) that may require asymptotic notation to define” respectively. The latter concept is hard to pin down rigorously in finitary mathematics, even though the intuition it captures (e.g. that the “set” of “bounded” integers should be closed under addition) is fairly clear; but once one uses ultraproducts to separate the three levels of standard, nonstandard, and external objects, it is possible to make rigorous sense of these sorts of intuitions, as we shall see later.

Given a sequence of standard functions between standard sets for an -large set of , we define the ultralimit of this sequence to be the function from the nonstandard space to the nonstandard space defined by the formula

for all sequences that lie in for an -large set of . It is easy to see that this ultralimit is well-defined; we refer to such functions as nonstandard functions.

From the above construction, we may now transfer operations and relations on standard spaces to their nonstandard counterparts. For instance, if is a sequence of standard groups, then one can take the ultralimit of the multiplication operations to obtain a multiplication operation on the ultraproduct ; similarly, the inversion operation on gives rise to an inversion operation on . Similarly, the arithmetic operations on the standard natural numbers can be transferred to arithmetic operations on the nonstandard natural numbers , and properties and relations on the natural numbers can similarly be transferred. For instance, a nonstandard number can be said to be prime if the are prime for an -large set of (i.e. the ultralimit of the truth value of “ is prime” is true); one nonstandard number can be said to be larger than another if one has for an -large set of ; and so forth.

One can then check by hand that statements that are true for standard objects are also true for their nonstandard counterparts. For instance, because the group operations of the standard groups are associative, the group operation on the nonstandard group is also associative, and in fact will also be a group (as viewed externally). Similarly, addition and multiplication in the nonstandard natural numbers obey the usual commutative, associative, and distributive laws, because these transfer from the corresponding laws for the standard natural numbers . For a more topical example, it is now a theorem that given any standard natural number , there exist standard primes such that ; it is an instructive exercise to check that the same result then automatically holds in the nonstandard setting, thus for every nonstandard natural number there exist nonstandard primes such that .

These facts are special cases of the transfer principle, and can be formalised by Łos’s theorem. Informally, this theorem asserts that if an “elementary” sentence holds for (an -large subsequence of) a sequence of standard objects, then it also holds in the ultralimit, and conversely. To make this assertion rigorous, we need some of the notation from first-order logic; this is somewhat formal and the reader may wish to skim briefly over the definitions and proofs that follow. To simplify the discussion, we restrict attention to one-sorted languages, although in practice one often works with many-sorted languages instead.

Definition 3 (Languages and structures, formal definition) A signature is a collection of formal operation symbols and relation symbols , each of which is assigned an arity (a non-negative integer). (For instance, the signature of the language of groups would consist of the -ary operation , the -ary operation , and the -ary operation .) -ary operations are also known as constant symbols. Given a signature and an infinite supply of variable symbols , define a term to be a formal string generated by the following rules:

• Every variable symbol is a term.
• If is a -ary operation and are terms, then is a term.

By abuse of notation, we often move operation symbols to more traditional locations, for instance writing as , as , etc.. By further abuse of notation, parentheses are usually omitted when there is no loss of ambiguity, e.g. is often abbreviated as .

A formula involving some finite number of distinct variable symbols (known as the free variables of the formula) for some is then a formal string generated by the following rules:

• If is a -ary relation and are terms which only involve variables from , then is a formula of .
• If are terms only involving variables from , then is a formula with free variables .
• If are formulae with free variables , then , and are formulae with free variables .
• If is a formula with free variables (or some permutation thereof), then and are formulae with free variables .

A formula with no free variables is known as a sentence. As before, we abuse notation by moving relation symbols to more traditional locations, e.g. writing as , and by removing parentheses whenever there is no loss of ambiguity; we also permit concatenation of quantifiers, for instance abbreviating as . Thus, for instance, in the language of the natural numbers,

is a formula of one variable , and

is a sentence (which, in this case, encodes the even Goldbach conjecture).

We refer to the collection of such formulae as the first-order language (or language, for short) associated with the given signature (and to the supply of variable symbols).

A structure for a first-order language is a set , together with a map for every -ary operation , and a boolean relation for every -ary relation . (For instance, a group is a structure for the first-order language of groups.) Any term of variables may be interpreted as a function by viewing the variable symbols as ranging in , and replacing each operation or relation with their respective interpretations . Similarly, any formula may be interpreted as a function , and in particular any sentence is interpreted to be either true or false (and we write if the former occurs), by interpreting quantifiers such as and as quantification over . (For instance, is interpreted as true for if there exists such that is true.)

Given a sequence of standard structures for a given first-order language , we can form the ultraproduct in the obvious manner, with the nonstandard interpretations of the operator and relation symbols being the ultralimits of their standard counterparts. We refer to this ultraproduct as a nonstandard structure for the first-order language ; both standard structures and nonstandard structures are examples of external structures, but as remarked before we do not consider standard structures as examples of nonstandard structures (except when the structure is finite).

Theorem 4 (Łos’s theorem) Let be a sequence of standard structures for a first-order language , and let be the associated nonstandard structure.

• (i) If is a term involving the variables , then is the ultralimit of the .
• (ii) If is a formula with free variables , then is the ultralimit of .
• (iii) If is a sentence, then is true if and only if is true for sufficiently close to .

Informally, this theorem asserts that first-order logic is continuous with respect to ultralimits.

Proof: The claim (i) is obtained by a routine induction on the length of the term and the ultrafilter axioms, while the claim (iii) is a consequence of (ii). The claim (ii) is similarly obtained by a routine induction on the length of the formula and the ultrafilter axioms; the only non-trivial claim to verify is that if the formula is the ultralimit of the formulae , then the formula is the ultralimit of the formulae , and similarly for the universal quantifier .

We just prove the claim for the existential quantifier , as the claim for is similar (and can be deduced from the existential case by rewriting in the equivalent form . Suppose first that for are such that holds for sufficiently close to ; by the axiom of choice, we may thus find such that holds for sufficiently close to . Taking ultralimits and using the induction hypothesis, we conclude that where , so that is true. Conversely, suppose that fails for sufficiently close to ; then for any in , fails for sufficiently close to , and hence on taking ultralimits fails also, and the claim follows.

We now give a classic consequence of Łos’s theorem to logic, namely the countable case of the compactness theorem:

Corollary 5 (Compactness theorem, countable case) Let be a first-order language, and let be a sequence of sentences. Suppose that for each natural number , there exists a structure for such that are satisfied by this structure. Then there exists a structure such that are simultaneously satisfied by this structure.

The general case of the compactness theorem may be established by using ultraproducts on more general sets than the natural numbers; we leave the verification of this fact to the reader.

Proof: We select the standard universe to contain all of the , so that the are all standard structures. If we then set to be the nonstandard structure , the claim follows from Łos’s theorem.

— 2. Rank decompositions —

We can now give a simple example of how ultralimits may be used to connect quantitative finitary statements to qualitative infinitary statements, by giving an easy case of the polyomial regularity lemma, introduced by Ben Green and myself. Given a finite-dimensional vector space over a field and a natural number , we define a polynomial of degree at most on to be a function of the form

for any basis of and some coefficients ; it is easy to see that the choice of basis is irrelevant for this definition. If is infinite dimensional instead of finite dimensional, we say that is a polynomial of degree at most if its restriction to any finite subspace is still a polynomial of degree at most . The space of such polynomials will be denoted ; this is itself a vector space over .

If for some , we define the rank to be the least integer such that we can find such that is a function of the , that is to say there exists a function such that for all . When is finite-dimensional, the rank is necessarily finite (just take to be the coordinate functions), but the rank may be infinite when is infinite dimensional. This notion of rank is analogous to the notion of the rank of a quadratic form (which is essentially the case of the above notion).

We then have the following simple fact:

Lemma 6 (Polynomial regularity lemma) Let be a non-negative integer, and let be a function. Then there exists a constant with the following properties: for any , any vector space over a field , and any polynomials , there exists polynomials for some and a quantity with the following properties:

• (i) (Representation modulo low rank) For each , there exists a representation , where and .
• (ii) (Independence modulo low rank) For every , not all zero, we have .

The above quantitative lemma can be deduced instead from the following basic fact in linear algebra, a variant of the Steinitz exchange lemma:

Lemma 7 Let be a finite collection of vectors in a vector space . Then there exists a linearly independent set of vectors in for some such that each is a linear combination of the .

From Lemma 7 we immediately obtain a qualitative version of Lemma 6:

Corollary 8 (Qualitative polynomial regularity lemma) Let be a non-negative integer. Then for any , any vector space over a field , and any polynomials , there exists polynomials for some with the following properties:

• (i) (Representation modulo low rank) For each , there exists a representation , where and .
• (ii) (Independence modulo low rank) For every , not all zero, we have .

Proof: Let be the set of all polynomials in of finite rank; this is clearly a subspace of , so we may form the quotient space , which is still a vector space over . If we then apply Lemma 7 to the projection of the to this quotient space , we obtain the claim.

While Corollary 8 certainly looks very similar to Lemma 6, it appears at first glance that it cannot be used to prove Lemma 6, because the latter lemma has meaningful content when is finite-dimensional, whereas the former Corollary is trivial in that setting. However, this can be rectified by passing from the finitary setting to the infinitary setting. This can be done in a number of ways, but we will do this using the ultrafilter machinery just developed.

Proof: (Proof of Lemma 6 using Corollary 8.) We use the “compactness and contradiction” method. Suppose for contradiction that Lemma 6 failed. Carefully negating the quantifiers, and using the axiom of choice, this means that there exists and , with the property that for each , we can find a vector space over a field and polynomials , such that for any , there does NOT exist , , obeying the properties (i), (ii) of Lemma 6 with the given data.

We may place all of the objects just constructed in a standard universe . Taking ultralimits (and using Łos’s theorem repeatedly), we obtain a nonstandard field , a nonstandard vector space over that field, polynomials , with the property that for any standard integer , there does NOT exist , , obeying the properties (i), (ii) of Lemma 6 with the given data. However, if one applies Corollary 8, we can find obeying the conclusions (i), (ii) of Corollary 8. This implies the conclusions (i), (ii) of Lemma 6 if is chosen large enough, giving the required contradiction.

— 3. Saturation and colouring —

Ultraproducts enjoy a very useful compactness-type property, known as countable saturation (or more precisely, -saturation). This property may be phrased in many ways, but we will use the following version which emphasises the analogy with topological compactness.

Let be a nonstandard set, thus for some standard sets . We call an internal subset or nonstandard subset of to be any subset of of the form ; by Łos’s theorem we see that for sufficiently close to . For instance, in the nonstandard natural numbers , the nonstandard intervals are internal sets for any nonstandard natural number ; indeed, if , then is the ultraproduct of the standard intervals . More generally, from Łos’s theorem we see that any subset of that is defined by a first-order predicate is an internal set. On the other hand, as we shall see later, the standard natural numbers are not an internal subset of (and are thus merely an external subset of ).

From Łos’s theorem we see that the internal subsets of a nonstandard set form a boolean algebra. We then have the following compactness property:

Proposition 9 (Countable saturation) Every countable cover of by internal sets has a finite subcover. Equivalently, if are a countable sequence of internal sets such that is non-empty for each , then is also non-empty.

We remark that if we had used ultraproducts on larger index sets than the natural numbers, then we would be able to obtain stronger saturation properties than countable saturation, although it is never possible to get unlimited saturation (since every point in a nonstandard set is an internal set). In model theoretic applications it can be technically convenient to work with an extremely saturated model (e.g. a structure which is saturated up to an inaccessible cardinal), but for most applications outside of logic and set theory, such “monster models” are not necessary, and the more modest device of ultraproducts over countable index sets is often sufficient.

Proof: It suffices to prove the second claim, as the former follows by taking complements.

Write , then for each , is the ultraproduct of . In particular, is non-empty for all in an -large subset of the natural numbers. By shrinking the as necessary we may assume that they are monotone, thus , and such that does not contain any natural number less than ; in particular, . For any , let denote the largest natural number such that , and then let denote an element of . Then by construction, for each , we have for all , and thus the nonstandard object lies in for all , and thus is non-empty as required.

This shows for instance that (as claimed previously) is not an internal subset of , since it can be countably covered by the singleton sets for which are internal, but for which no finite cover exists. Among other things, this establishes the overspill principle: if a nonstandard formula holds for all standard natural numbers, then it must hold for at least one unbounded natural number (defined as a nonstandard natural number that is not a standard natural number).

Another immediate corollary of the above proposition is that if a nonstandard set is covered by a countable sequence of internal subsets, then the topology on generated by is compact (because it has a countable base of internal susbets, and Proposition 9 then gives countable compactness).

As an application of this compactness observation, we use ultraproducts to illustrate the topological dynamics version of the Furstenberg correspondence principle, that connects Ramsey theory to topological dynamics. More precisely, we consider the following results:

Theorem 10 (van der Waerden’s theorem) For any there exists such that whenever is partitioned into colour classes , one of the colour classes contains an arithmetic progression of length with some .

Theorem 11 (Topological multiple recurrence) Let be a non-empty compact topological space, and let be a homeomorphism. Then for any open cover of and any , there exists an open set in this cover, a point , and a positive integer such that .

It is not difficult to use Theorem 10 to establish Theorem 11. Conversely, we will use ultraproducts to show that Theorem 11 implies Theorem 10. (We will not prove either of these theorems here, but see e.g. this previous blog post for a proof.)

Again, we use compactness and contradiction. Suppose for contradiction that Theorem 10 failed. Then there exists such that for any standard , we may partition into colour classes , none of which contain any -term arithmetic progressions. Taking ultraproducts, we obtain a partition of the nonstandard interval associated to the unbounded natural number into internal colour classes , none of which contains a nonstandard -term arithmetic progression.

Now consider the shifted colour classes for and . These are a countable family of internal sets that cover , and so by countable saturation, this gives the structure of a compact topological space.

We would like to use the shift map on . Unfortunately, this map is not quite a bijection on . To get around this, we work in the slightly smaller space

A further application of countable saturation reveals that is still compact (with the induced topology from ). Furthermore, the shift map can be verified to be a homeomorphism on , and as is unbounded, we see from the overspill principle that is non-empty. It is covered by the open sets , so by Theorem 11, we can find and a (standard) positive integer such that lie in a single , thus contains a non-standard -term arithmetic progression, giving the required contradiction.

— 4. Algebraic geometry and ultraproducts —

Another use of ultraproducts is to provide a bridge between quantitative algebraic geometry and qualitative algebraic geometry. This topic is discussed in detail in this previous post; we will just give some key results here without proof.

Theorem 12 (Algebraic geometry is continuous with respect to ultralimits) Let be a sequence of algebraically closed fields, let be a natural number, and let be a (standard) affine algebraic set, that is to say the solution set of some finite number of polynomials . We define the complexity of an algebraic set to be the least such that is cut out by at most polynomials, each of degree at most .

Then the nonstandard set is an algebraic set if and only if the complexity of the are uniformly bounded for sufficiently close to . Furthermore, if is indeed an algebraic set, then:

• (Continuity of dimension) The dimension of is equal to the dimension of for sufficiently close to .
• (Continuity of irreducibility) is irreducible if and only if is irreducible for sufficiently close to .
• (Continuity of degree) The degree of is equal to the degree of for sufficiently close to .

A similar statement holds for constructive sets: an ultraproduct of constructive sets is constructive if and only if the original sets have uniformly bounded complexity for sufficiently close to . These claims are proven in the previous blog post; the basic idea is to express basic concepts such as dimension, irreducibility, and degree in first-order terms, so that Łos’s theorem may be applied.

Using this theorem and the compactness and contradiction method, one can easily convert a number of qualitative algebraic results into quantitative ones. For instance, it is a basic fact in qualitative algebraic geometry that every algebraic set decomposes into a finite number of irreducible sets. Using the above theorem (and a relationship between degree and complexity), one can then show that the number of such sets is bounded by a quantity depending only on the degree of the original set (and in particular, uniform in the choice of field); again, see the previous blog post for details. Such quantitative bounds can be obtained by other means (for instance, by using the machinery of schemes), but the ultrafilter approach, being so general in nature, requires almost no actual algebraic geometry to set up and use.

— 5. Metric completion and Gromov-Hausdorff limits —

We previously gave an analogy between ultraproducts and metric completion. It turns out that this analogy can be made substantially more precise. We first need some basic nonstandard analysis notation. Call a nonstandard real number bounded if one has for some standard , and infinitesimal if one has for all standard . For instance, if is an unbounded natural number, then is bounded (but not standard), and is infinitesimal. We write and to denote the assertions that is bounded and infinitesimal respectively.

Proposition 13 (Bolzano-Weierstrass theorem) If is a bounded nonstandard real, then there exists a unique standard real , called the standard part of , such that , i.e. is infinitesimal.

One can also prove this theorem by the usual Bolzano-Weierstrass argument, trapping in a nested sequence of dyadic standard intervals; we leave this argument to the interested reader.

One can view the standard part operation algebraically, as a homomorphism from the bounded nonstandard reals to the standard reals with kernel ; note that the sets are perfectly well-defined as an (external) set in the nonstandard analysis formalism, even though it does not quite make rigorous set-theoretic sense in finitary mathematics (one cannot use finitary asymptotic notation such as inside set-builder notation). Thus for instance we can say that is an ideal in the ring , which is an assertion which is intuitively obvious in the finitary setting, but a bit hard to formalise properly. Note that can then be interpreted as the image under the standard part map of the bounded nonstandard rationals . This can in fact be used to give an alternative definition of the real numbers, which is the nonstandard version of the Cauchy completion construction; we leave this construction to the reader.

We can perform similar constructions with other metric spaces. Actually, in order to have a reaonable notion of boundedness, it is convenient to work in the category of pointed metric spaces , that is to say a metric space with a preferred “origin” . If one has a sequence of standard pointed metric spaces, one can take ultralimits and create a nonstandard pointed metric space . Here, is the ultraproduct of the , is a point in , and is the ultralimit of the .

At present, is a nonstandard metric space, but not an external metric space, because the nonstandard distance between two points in is a nonstandard real, and not necessarily a bounded one. To create an external metric space, we cut down the size of in two different ways. Firstly, we restrict attention to the bounded portion of . Next, we place an equivalence relation on by declaring if . The quotient space , which we will denote suggestively as can then be checked to be a metric space with metric given by the formula

whenever , with corresponding equivalence classes . The quotient map will be called the standard part map, as it generalises the map in Proposition 13.

We refer to the pointed external metric spaces as the nonstandard hull of the standard pointed metric spaces ; it is also known as the ultralimit of these spaces, although we avoid this terminology here as we are using the term “ultralimit” for a slightly different (although certainly related) operation. These spaces are automatically complete, as can easily be verified using countable saturation. If the spaces are asymptotically uniformly locally totally bounded in the sense that for every there exists such that for sufficiently close to , one can cover the balls by at most balls of radius , then the nonstandard hull is also locally totally bounded by Łos’s theorem, and thus locally compact by the Heine-Borel theorem. Furthermore, it is not difficult to show in this case that the converge along to in the pointed Gromov-Hausdorff sense, thus for every , the Gromov-Hausdorff distance between and is less than for sufficiently close to . In particular, this demonstrates the basic fact that any sequence of asymptotically uniformly locally totally bounded pointed metric spaces has a convergent subsequence in the pointed Gromov-Hausdorff sense.

There are several interesting special cases of the nonstandard hull construction. For instance, if the spaces are equal to a single locally totally bounded space, then the nonstandard hull becomes a metric completion of , with every bounded sequence in giving rise to a limit point in . When the metric spaces are normed vector spaces, in which nonstandard analysis can be used as a framework to describe the theory of concentration compactness; see this previous blog post for further discussion. Finally, if one starts with a finitely generated group with a word metric , then by taking the nonstandard hull of with a rescaled word metric for a well-chosen set of radii , one can obtain a useful metric space known as the asymptotic cone of , which for instance can be used to establish Gromov’s theorem on groups of polynomial growth; see this paper of van den Dries and Wilkie for details. Related to this, one can take the non-standard hull of a sequence of approximate groups (and the groups generated by such approximate groups) to obtain open neighbourhoods of locally compact groups, allowing one to use the theory of Hilbert’s fifth problem (which classifies the latter) to study approximate groups; see this text of mine for more discussion.

— 6. Loeb measure and regularity —

Measure theory, with its emphasis on countable additivity, is not obviously a first-order theory, and so it is not a priori obvious that it interacts well with ultraproducts. Nevertheless, thanks primarily to the countable saturation property of ultraproducts, one can often obtain a good notion of measure on nonstandard spaces, by carefully taking the ultralimit of measures on standard spaces. We give a fundamental such construction here, namely the Loeb measure construction, although for simplicity we restrict attention to the setting of nonstandard finite sets (also known as hyperfinite sets) to avoid some technicalities. Loeb measures are a special case of the more general concept of a Kiesler measure in model theory, but we will not discuss this more general concept here.

Let be a sequence of standard non-empty finite sets, so that the ultraproduct is a nonstandard non-empty finite set. On each of the , we can define the uniform probability measure , which assigns the measure to each subset of . Of course, is a finitely additive probability measure. Taking ultraproducts and then taking standard parts, we can then define a finitely additive probability measure on the boolean algebra of internal subsets of , by the formula

One easily verifies that this is a finitely additive probability measure. Furthermore, thanks to the countable saturation property, we see that is a premeasure, that is to say that one has the countable additivity property

whenever are a family of disjoint internal subsets of whose union is also an internal subset. Applying the Caratheodory extension theorem (or more precisely, the Hahn-Kolmogorov theorem), we can then extend to a countably additive probability measure on the -algebra generated by ; we refer to as a Loeb space, with being the Loeb probability measure and being the Loeb -algebra.

The relationship between and is closely analogous to that between the elementary measure (or Jordan measure) of elementary subsets of (say) the unit cube, and that of Lebesgue measure of Borel subsets of that cube; see e.g. this text of mine for the basic theory here. For instance, it is not difficult to show that every Loeb measurable set is “almost internal” in the sense that for any standard , one can find an internal set which is -close to in the sense that the outer measure

of the symmetric difference is at most . Related to this, the Loeb measure and the outer measure agree on any Loeb measurable set, and the simple internal functions on (i.e. finite linear combinations of indicator functions of internal sets) will be dense in for any (standard) .

For instance, if is an unbounded natural number, then the set is not an internal subset of , but it is the intersection of the countable family of internal sets for . Each of the internal sets has measure , and so is a Loeb measurable set with Loeb measure zero. As another example, for any standard and , the residue class is an internal subset of of Loeb measure exactly (regardless of what the remainder of is modulo ).

As a quick application of Loeb measure, we give an instance of the Furstenberg correspondence principle, closely analogous to the topological dynamics example from a few sections earlier. Specifically, we connect the following two theorems:

Theorem 14 (Szemeredi’s theorem) For any and there exists such that whenever has density at least , contains an arithmetic progression of length with some .

Theorem 15 (Furstenberg multiple recurrence) Let be a probability space, and let be an almost everywhere defined bijection that is measure-preserving. Then for any set of positive measure and any , there exists a point , and a positive integer such that .

Again, it is not difficult to show that Theorem 14 implies Theorem 15. To show the converse, we again use the compactness and contradiction method. If Theorem 14 failed, then there exist and , and a sequence going to infinity, together with subsets of density at least which contain no -term arithmetic progressions. Taking ultralimits, we obtain an unbounded natural number and an internal subset of Loeb measure at least which contains no non-standard -term arithmetic progressions. The shift map is defined and bijective almost everywhere on , and is measure-preserving, and Theorem 15 then provides the required contradiction.

Remark 2 The ultralimit construction actually gives a lot more relevant structure on than just that of a measure-preserving system. For instance, one can view the space of parallelograms as a special subset of , which one can also endow with a Loeb measure, and these spaces (as well as higher-dimensional analogues) which can be used to analyse the further additive structure of (in a manner that closely parallels the structural theory of Host and Kra on measure-preserving systems); see this paper of Szegedy for some details of this approach.

The above example already shows the power of basic measure-theoretic tools (such as the Hahn-Kolmogorov theorem) in connecting discrete and continuous results together. Now we turn to some applications of other basic measure theory tools, such as product measure and conditional expectation. Specifically, we will use ultraproducts and measure theory to prove the following “strong” form of the Szemerédi regularity lemma:

Lemma 16 (Szemerédi regularity lemma) Let and be a function. Then there exists with the following property: whenever is a finite non-empty set and is a function, there exists and a decomposition

where

• (Structure) takes values in , and there exists a partition such that is constant on for all .
• (Smallness) takes values in , and .
• (Pseudorandomness) For any , one has .

The connection between the regularity lemma and nonstandard measure theory was first obtained by Elek and Szegedy, in which the extension of the arguments here to hypergraphs was also obtained.

We will deduce Lemma 16 from the following infinitary version:

Lemma 17 (Infinitary regularity lemma) Let be standard, and let be a nonstandard finite non-empty set. If is a Loeb measurable function on , then there exists a decomposition

where

• (Structure) takes values in , and there exists a partition into finitely many internal sets such that is constant on for all .
• (Smallness) takes values in , and .
• (Pseudorandomness) For any measurable , one has .

We will prove Lemma 17 shortly, but let us first see how it implies Lemma 16. We once again use the compactness and contradiction method. If Lemma 16 fails, then there exists and , and for each there exists a finite non-empty set and a function , such that for no does there exist a decomposition

obeying the conclusions of Lemma 16. We then take ultralimits to obtain a nonstandard finite non-empty set and an internal function . The standard part is then a Loeb measurable function on taking values in . We apply Lemma 17 to obtain a decomposition

with the stated properties for some finite . Note that is already a simple internal function. The function need not be simple internal, but may be approximated to arbitrary accuracy in by a simple internal function. Thus we may find a decomposition

where is simple internal and is such that

for all measurable , and is simple internal, takes values in , and is such that

By Łos’s theorem, an analogous decomposition then holds for for sufficiently close to , but this contradicts the construction of the .

Now we prove Lemma 17. The proof hinges on a comparison between two spaces, the Loeb space

on the product space , and the subtly different probability space

that is the product of the Loeb space with itself, thus is the -algebra on generated by rectangles with Loeb measurable in , and is the product measure, which is the unique probability measure on such that

for all Loeb measurable .

It is not difficult to show that the former probability space is a refinement of the latter, thus contains , and and agree on their common domain of definition. However, the former space is larger in general; the basic reason for this is for large finite spaces , it is possible to find subsets of that are not well approximable by bounded boolean combinations of rectangles (e.g. random subsets of will have this property with high probability in the asymptotic limit when goes to infinity). Despite this disparity, we may still form the conditional expectation of , which one can define as the orthogonal projection of in the Hilbert space to the closed subspace . We then have a decomposition

where is orthogonal to all -measurable functions; in particular, it is orthogonal to for any Loeb measurable , so that

for all such .

Next, we know that is generated (up to null sets) by products of internal sets, so we may approximate to arbitary error in by a simple function that is a finite linear combination of indicators of rectangles; as takes values in , we can ensure that and . This gives a decomposition

and one easily verifies that all the required properties of Lemma 17 are obeyed.

Remark 3 It is instructive to deconstruct this proof and compare it with the standard “energy increment” proof of the regularity lemma. The energy increment process is now concealed within the standard proof of the existence of orthogonal projections in Hilbert spaces (see e.g. Proposition 1 of this previous blog post), so on some level the two proofs of the regularity lemma are essentially equivalent. However, the ultrafilter proof allows one to hide many of the ingredients of the argument into existing Hilbert space theory.

Remark 4 Although it is not needed here, one convenient fact about Loeb spaces on products is that they obey the following Fubini-Tonelli type theorem: if are nonstandard finite spaces and is Loeb measurable on , then for all , the function is Loeb measurable on , the integral is Loeb measurable on , and we have the identity

Similarly if the roles of and are swapped; in particular we have the familiar identity

These identities are obvious when is an internal simple function (as it follows from the corresponding claim in the finite case), and the general case follows from a standard approximation argument (using the monotone convergence theorem repeatedly). One can also obtain an analogous claim in the absolutely integrable category, in the spirit of Fubini’s theorem; we leave this to the interested reader.

Filed under: expository, math.CA, math.CO, math.DS, math.LO, talk Tagged: correspondence principle, Loeb measure, nonstandard analysis, regularity lemma, ultrafilters, ultraproducts

This is awesome!

I am reliably informed that this was one of the all time great concerts.

Skálmöld and the Icelandic Symphony in concert at Harpa.

Mertens’ theorems are a set of classical estimates concerning the asymptotic distribution of the prime numbers:

Theorem 1 (Mertens’ theorems) In the asymptotic limit , we have

and

where is the Euler-Mascheroni constant, defined by requiring that

in the limit .

The third theorem (3) is usually stated in exponentiated form

but in the logarithmic form (3) we see that it is strictly stronger than (2), in view of the asymptotic .

Remarkably, these theorems can be proven without the assistance of the prime number theorem

which was proven about two decades after Mertens’ work. (But one can certainly use versions of the prime number theorem with good error term, together with summation by parts, to obtain good estimates on the various errors in Mertens’ theorems.) Roughly speaking, the reason for this is that Mertens’ theorems only require control on the Riemann zeta function in the neighbourhood of the pole at , whereas (as discussed in this previous post) the prime number theorem requires control on the zeta function on (a neighbourhood of) the line . Specifically, Mertens’ theorem is ultimately deduced from the Euler product formula

valid in the region (which is ultimately a Fourier-Dirichlet transform of the fundamental theorem of arithmetic), and following crude asymptotics:

Proposition 2 (Simple pole) For sufficiently close to with , we have

and

The first two of Mertens’ theorems (1), (2) are relatively easy to prove, and imply the third theorem (3) except with replaced by an unspecified absolute constant. To get the specific constant requires a little bit of additional effort. From (4), one might expect that the appearance of arises from the refinement

that one can obtain to (6). However, it turns out that the connection is not so much with the zeta function, but with the Gamma function, and specifically with the identity (which is of course related to (7) through the functional equation for zeta, but can be proven without any reference to zeta functions). More specifically, we have the following asymptotic for the exponential integral:

Proposition 3 (Exponential integral asymptotics) In the limit , we have

Below the fold I would like to record how Proposition 2 and Proposition 3 imply Theorem 1; the computations are utterly standard, and can be found in most analytic number theory texts, but I wanted to write them down for my own benefit (I always keep forgetting, in particular, how the third of Mertens’ theorems is proven).

— 1. Proof of Mertens’ theorems —

Let be as in Proposition 2. Taking logarithms of using (5), we obtain the asymptotic

using the standard branch of the logarithm; if we instead compute the logarithmic derivative , we obtain the closely related asymptotic

which by the approximation also gives

Proposition 4 Let be a compactly supported, Riemann integrable function independent of . Then as , we have

Proof: By approximating above and below by smooth functions, we may assume without loss of generality that is smooth. Applying the Fourier inversion formula to the function , we thus have a Fourier representation of the form

for some rapidly decreasing function . The left-hand side of (10) may then be rewritten as

The summation here may be crudely bounded in magnitude by

thanks to (9). From this and the rapid decrease of , we see that the contribution of the integrand for which (say) is . In the remaining region, we may apply (9) to estimate the left-hand side of (10) as

The contribution of the error is again , so from the rapid decrease of again we may rewrite this expression as

and the claim then follows by integrating (11) on .

Setting in the above proposition immediately gives the first Mertens’ theorem (1). We now skip to the third Mertens’ theorem (3), since as observed previously the second Mertens’ theorem (2) follows as a corollary. Let be a fixed quantity (independent of ). From (8) with we have

where the asymptotic notation refers to the limit . Let us first consider the contribution to this sum from those with :

By Taylor expansion we have , and hence the above sum is equal to

or equivalently

where . From Proposition 4 we have

for any fixed . One can bound the tail error from from the first Mertens’ theorem (1) and dyadic decomposition, and on taking limits as we conclude that

scaling by , we rewrite this as

Now we consider the contribution from those with :

From the mean value theorem we have

so from the first Mertens’ theorem (1), we can write this sum as

Putting all this together, we see that

Sending slowly to zero using Proposition 3, we obtain the third Mertens’ theorem (3) as required.

It’s been quite a while (for good reason, as you’ll see) since I gave you a status update on the search for supersymmetry, one of several speculative ideas for what might lie beyond the known particles and forces.  Specifically, supersymmetry is one option (the most popular and most reviled, perhaps, but hardly the only one) for what might resolve the so-called “naturalness” puzzle, closely related to the “hierarchy problem” — Why is gravity so vastly weaker than the other forces? Why is the Higgs particle‘s mass so small compared to the mass of the lightest possible black hole?

Click here to read more about the current situation…

Say you have many noisy inferences of some quantity (planet radius, say, for hundreds of planets), and you want to know the true distribution of that quantity (the planet-radius distribution you would observe with very high signal-to-noise data). How should you estimate the distribution? One option: Histogram your maximum-likelihood estimates. Another: Co-add (sum) your individual-object likelihood functions. Another: Co-add your individual-object posterior pdfs. These are all wrong, of course, but the odd thing is that the latter two—which seem so sensible, since they "make use of" uncertainty information in the inferences—are actually wronger than just histogramming your ML estimates. Why? Because your ML-estimate histogram is something like the truth convolved with your uncertainties, but a co-add of your likelihoods or posteriors is pretty-much the same as that but convolved again. The Right Thing To Do (tm) is hierarchical inference, which is like a deconvolution (by forward modeling, of course). I feel like a skipping record. Fadely, Foreman-Mackey, and I discussed all this over lunch, in the context of recent work on (wait for it) planet radii.

Updated on 11 Dec 2013: see end of post.

A letter from Chicago mathematician Sasha Beilinson in this month’s Notices of the American Mathematical Society calls for the AMS to sever all ties with the US National Security Agency, citing

the vast secret spying programs of the NSA that wildly exceed anything conspiracy theorists could imagine.

He lists some of the ways in which the AMS and NSA support each other, and issues a call for action:

What should be done is a question not only for US citizens but also for people all over the world: the NSA destroyed the security of the Internet and privacy of communications for the whole planet. But if any healing is possible, it would probably start with making the NSA and its ilk socially unacceptable — just as, in the days of my youth, working for the KGB was socially unacceptable for many in the Soviet Union.

I’m now wondering about the relationship between the LMS (London Mathematical Society, the British counterpart of the AMS) and GCHQ (Government Communications Headquarters, the British counterpart of the NSA). While GCHQ may employ fewer people, it has the inestimable advantage of not being constrained by that bothersome US constitution:

We have a light oversight regime compared with the US,

according to GCHQ lawyers, which is really saying something. Moreover, it is considered by some to be more extreme in its surveillance of the general population than even the NSA.

So, I’ve written to the president and vice-presidents of the LMS asking about its — or rather, “our”, as I’m a member — relationship with GCHQ. I’d like to know the facts. It may be that there’s no significant relationship, and that’s the answer I’d like to hear; but at present I simply don’t know.

What we do as mathematicians seldom has any contact with politics or human affairs. But this is one of those occasions. The NSA and GCHQ must be two of the largest employers of mathematicians in the world. Whatever you think of the ongoing mass surveillance, it can’t be denied that this is an issue that involves, and will continue to involve, our community.

Added later:

Since we don’t usually have this kind of discussion here, let me make explicit what kind of thing I’m going to allow:

1. Discussion of the NSA and GCHQ is fine. That’s what this is about. Both places employ large numbers of mathematicians, and mathematics is involved in the mass surveillance programs — especially in the breaking and circumvention of online encryption. This is the relevance to the mathematical community.

2. The closer the discussion sticks to those issues that concern mathematicians, the better. If it strays too far away, I may steer it back (possibly using the “delete” button).

3. Please try to keep the temperature down. Good ways of doing this are to provide linked references and not to appeal to emotions.

4. The obvious stuff: no insults etc. (but I hope I don’t need to say that here). I’ll simply delete objectionable comments.

In short, please write thoughtfully, and please focus on the central issue: cooperation between the NSA/GCHQ and mathematicians.

Added on 11 Dec 2013:

I have now heard back informally from someone who was at the latest LMS Council meeting. (The Council is made up of academics and “is responsible for determining the strategy and policy of the Society”.)

Apparently, there was unanimous agreement that the LMS should at least be transparent about this, and should state publicly what connections there are between the LMS and GCHQ. (For example, GCHQ part-funds LMS instructional courses for graduate students.) I don’t know whether there was agreement on anything else, as I haven’t had an official response yet.

Today was the Nobel Prize ceremony, including of course the Physics Prize to François Englert and Peter Higgs. Congratulations once again to them!

(Parenthetically, it’s sad that the Nobel is used to puff up national pride. In Belgium, Englert gets into the headline but not Higgs; in the UK, it’s the other way around.)

I of course had nothing to do with the physics behind this year’s Nobel, but I did write a book about it, so I’ve had a chance to do a little commentating here and there. I wrote a short piece for The Independent that tries to place the contribution in historical context. I’ve had a bit of practice by now in talking about this topic to general audiences, so consider this the distillation of the best I can do! (It’s a UK newspaper, so naturally only Higgs is mentioned in the headline.) I love how, at the bottom of the story, you can register your level of agreement, from “strongly agree” to “strongly disagree.” And if you prefer your words spoken aloud, here I am on the BBC talking about the book.

Meanwhile here at Caltech, we welcomed back favorite son Murray Gell-Mann (who spends his days at the Santa Fe Institute these days) for the 50th anniversary of quarks. One of the speakers, Geoffrey West, pointed out that no Nobel was awarded for the idea of quarks. Gell-Mann did of course win the Nobel in 1969, but that was “for his contributions and discoveries concerning the classification of elementary particles and their interactions”. In other words, strangeness, SU(3) flavor symmetry, the Eightfold Way, and the prediction of the Omega-minus particle. (Other things Gell-Mann helped invent: kaon mixing, the renormalization group, the sigma model for pions, color and quantum chromodynamics, the seesaw mechanism for neutrino masses, and the decoherent histories approach to quantum mechanics. He is kind of a big deal.)

But, while we now understand SU(3) flavor symmetry in terms of the quark model (the up/down/strange quarks are all light compared to the QCD scale, giving rise to an approximate symmetry), the idea of quarks itself wasn’t honored by the 1969 prize. If it had been, the prize certainly would have been shared by George Zweig, who proposed the idea independently. So there’s still time to give out the Nobel for the quark model! Perhaps Gell-Mann and Zweig could share it with Harald Fritzsch, who collaborated with Gell-Mann on the invention of color and QCD. (The fact that QCD is asymptotically free won a prize for Gross, Politzer and Wilczek in 2004, but there hasn’t been a prize for the invention of the theory itself.) Modern particle physics has such a rich and fascinating history, we should honor it as accurately as possible.

• Higgs doesn't think he would have gotten tenure in today's climate.  
• Elsevier is still evil, or at least, not nice.
• A higher capacity cathode for Li-ion batteries looks interesting.
• NIST has decided to award their big materials center to a consortium led by Northwestern. 

There were many interesting talks at the Interdisciplinary Climate Change Workshop last week—too many for me to describe them all in detail. But I really must describe the talks by Radoslav Dimitrov. They were full of important things I didn’t know. Some are quite promising.

Radoslav S. Dimitrov is a professor at the Department of Political Science at Western University. What’s interesting is that he’s also been a delegate for the European Union at the UN climate change negotiations since 1990! His work documents the history of climate negotiations from behind closed doors.

Here are some things he said:

• In international diplomacy, there is no questioning the reality and importance of human-caused climate change. The question is just what to do about it.

• Governments go through every line of the IPCC reports twice. They cannot add anything the scientists have written, but they can delete things. All governments have veto power. This makes the the IPCC reports more conservative than they otherwise would be: “considerably diluted”.

• The climate change negotiations have surprised political scientists in many ways:

1) There is substantial cooperation even without the USA taking the lead.

2) Developing countries are accepting obligations, with many overcomplying.

3) There has been action by many countries and subnational entities without any treaty obligations.

4) There have been repeated failures of negotiation despite policy readiness.

• In 2011, China and Saudi Arabia rejected the final agreement at Durban as inadequate. Only Canada, the United States and Australia had been resisting stronger action on climate change. Canada abandoned the Kyoto Protocol the day after the collapse of negotiations at Durban. They publicly blamed China, India and Brazil, even though Brazil had accepted dramatic emissions cuts and China had, for the first time, accepted limits on emissions. Only India had taken a “hardline” attitude. Publicly blaming some other country for the collapse of negotiations is a no-no in diplomacy, so the Chinese took this move by Canada as a slap in the face. In return, they blamed Canada and “the West” for the collapse of Durban.

• Dimitrov is studying the role of persuasion in diplomacy, recording and analyzing hundreds of hours of discussions. Countries try to change each other’s minds, not just behavior.

• The global elite do not see climate change negotiations as an environmental issue. Instead, they feel they are “negotiating the future economy”. They focus on the negative economic consequences of inaction, and the economic benefits of climate action.

• In particular, the EU has managed to persuade many countries that climate change is worth tackling now. They do this with economic, not environmental arguments. For example, they argue that countries who take the initiative will have an advantage in future employment, getting most of the “green jobs”. Results include China’s latest 5-year plan, which some have called “the most progressive legislation in history”, and also Japan’s plan for a 60-80% reduction of carbon emissions. The EU itself also expects big returns on investment in climate change.

I apologize for any oversimplifications or downright errors in my notes here.

References

You can see some slides for Dimitrov’s talks here:

• Radoslav S. Dimitrov, A climate of change.

For more, try reading this article, which is free online:

• Radoslav S. Dimitrov, Inside Copenhagen: the state of climate governance, Global Environmental Politics 10 (2010), 18–24.

and these more recent book chapters, which are apparently not as easy to get:

• Radoslav S. Dimitrov, Environmental diplomacy, in Handbook of Global Environmental Politics, edited by Paul Harris, Routledge, forthcoming as of 2013.

• Radoslav S. Dimitrov, International negotiations, in Handbook of Global Climate and Environmental Policy, edited by Robert Falkner, Wiley-Blackwell forthcoming as of 2013.

• Radoslav S. Dimitrov, Persuasion in world politics: The UN climate change negotiations, in Handbook of Global Environmental Politics, edited by Peter Dauvergne, Edward Elgar Publishing, Cheltenham, UK, 2012.

• Radoslav S. Dimitrov, American prosperity and the high politics of climate change, in Prospects for a Post-American World, edited by Sabrina Hoque and Sean Clark, University of Toronto Press, Toronto, 2012.

read more

In MCMC meeting today, Goodman brought up the difference between the fully marginalized posterior model probability and what you learn by cross-validation, for model selection. As my loyal reader knows, I have many thoughts about this and also a nascent paper with Vanderplas. However, Goodman has a different take from me: He sees cross-validation as producing the most predictive model (preventing over-fitting), but posterior probability as delivering the most probable model, given the universe of models. I think this is deeply (and obviously) correct. However, we haven't settled on words for Hou's paper yet, because he is still willing to use the T-word ("truth"), and I am not! (I also think, in the end, this is all related to the point that we want to deliver the most useful result for our purposes, and this necessarily involves utility.)

Here’s a new feature of the Café, thanks to our benevolent host Jacques Distler. If you ever want to see how someone has created some mathematical expression on this blog, there’s an easy way to do it.

With Firefox, you simply double-click on the expression. Try it: $A \times B^A \to B$ or $x_{m n}$ or

A window should pop up showing the TeX source.

With other browsers, I’m not so sure. Try double-clicking. If that doesn’t work, then, according to Jacques’s instructions, you “bring up the MathJax context-menu for the formula, and choose Show Math As $\to$ Annotation $\to$ TeX”. I don’t know how one brings up this menu. Does anyone else know?

Once you’ve made the TeX source appear, you can cut and paste to your heart’s content. Of course, most users here are fluent in LaTeX. But like most math-oriented websites, we use a variant of TeX that’s a little different from standard LaTeX, so this should turn out to be a helpful feature.

I try to focus on serious problems in this blog, mostly environmental issues and the attempt to develop ‘green mathematics’. But I seem unable to resist talking about random fun stuff now and then. For example, the Lebesgue universal covering problem. It’s not important, it’s just strange… but for some reason I feel a desire to talk about it.

For starters, let’s say the diameter of a region in the plane is the maximum distance between two points in this region. You all know what a circle of diameter 1 looks like. But an equilateral triangle with edges of length 1 also has diameter 1:

After all, two points in this triangle are farthest apart when they’re at two corners. And you’ll notice, if you think about it, that this triangle doesn’t fit inside a circle of diameter 1:

In 1914, the famous mathematician Henri Lebesgue sent a letter to a pal named Pál. And in this letter he asked: what’s the smallest possible region that contains every set in the plane with diameter 1?

He was actually more precise. The phrase “smallest possible” is vague, but Lebesgue wanted the set with the least possible area. The phrase “contains” is also vague, at least as I used it. I didn’t mean that our region should literally contain every set with diameter 1. Only the whole plane does that! I meant that we can rotate or translate any set with diameter 1 until it fits in our region. So a more precise statement is:

What is the smallest possible area of a region in the plane such that every set of diameter 1 in the plane can be rotated and translated to fit inside ?

You see why math gets a reputation of being dry: sometimes when you make a simple question precise it gets longer.

Even this second version of the question is a bit wrong, since it’s presuming there exists a region with smallest possible area that does the job. Maybe you can do it with regions whose area gets smaller and smaller, closer and closer to some number, but you can’t do it with a region whose area equals that number! Also, the word ‘region’ is a bit vague. So if I were talking to a nitpicky mathematician, I might pose the puzzle this way:

What is the greatest lower bound of the measures of closed sets such that every set of diameter 1 can be rotated and translated to fit inside ?

Anyway, the reason this puzzle is famous is not that it gets dry when you state it precisely. It’s that it’s hard to solve!

It’s called Lebesgue’s universal covering problem. A region in the plane is called a universal covering if it does the job: any set in the plane of diameter 1 can fit inside it, in the sense I made precise.

Pál set out to find universal coverings, and in 1920 he wrote a paper on his results. He found a very nice one: a regular hexagon circumscribed around a circle of diameter 1. Do you see why you can fit the equilateral triangle with side length 1 inside this?

This hexagon has area

But in the same paper, Pál showed you could safely cut off two corners of this hexagon and get a smaller universal covering! This one has area

He guessed this solution was optimal.

However, in 1936, a guy named Sprague sliced two tiny pieces off Pál’s proposed solution and found a universal covering with area

Here’s the idea:

The big hexagon is Pál's original solution. He then inscribed a regular 12-sided polygon inside this, and showed that you can remove two of the corners, say and and get a smaller universal covering. But Sprague noticed that near you can also remove the part outside the circle with radius 1 centered at , as well as the part outside the circle with radius 1 centered at

Sprague conjectured that this is the best you can do.

But in 1975, Hansen showed you could slice off very tiny corners off Sprague’s solution, each of which reduces the area by just

I think this microscopic advance, more than anything else, convinced people that Lebesgue’s universal covering problem was fiendishly difficult. Viktor Klee, in a parody of the usual optimistic prophecies people like to make, wrote that:

… progress on this question, which has been painfully slow in the past, may be even more painfully slow in the future.

Indeed, my whole interest in this problem is rather morbid. I don’t know any reason that it’s important. I don’t see it as connected to lots of other beautiful math. It just seems astoundingly hard compared to what you might initially think. I admire people who work on it in the same way I admire people who decide to ski across the Antarctic. It’s fun to read about—from the comfort of my living room, sitting by the fire—but I can’t imagine actually doing it!

In 1980, a guy named Duff did a lot better. All the universal coverings so far were convex subsets of the plane. But he considered nonconvex universal coverings and found one with area:

This changed the game a lot. If we only consider convex universal coverings, it’s possible to prove there’s one with the least possible area—though we don’t know what it is. But if we allow nonconvex ones, we don’t even know this. There could be solutions whose area gets smaller and smaller, approaching some nonzero value, but never reaching it.

So at this point, Lebesgue’s puzzle split in two: one for universal coverings, and one for convex universal coverings. I’ll only talk about the second one, since I don’t know of further progress on the first.

Remember how Hansen improved Sprague’s universal covering by chopping off two tiny pieces? In 1992 he went further. He again sliced two corners off Sprague’s solution. One, the same shape as before, reduced the area by just But the other was vastly larger: it reduced the area by a whopping

I believe this is the smallest convex universal covering known so far.

But there’s more to say. In 2005, Peter Brass and Mehrbod Sharifi came up with a nice lower bound. They showed any convex universal covering must have an area of least

They got this result by a rigorous computer-aided search for the convex set with the smallest area that contains a circle, equilateral triangle and pentagon of diameter 1.

If you only want your convex set to contain a circle and equilateral triangle of diameter 1, you can get away with this:

This gives a lower bound of

But the pentagon doesn’t fit in this set! Here is the least-area convex shape that also contains a pentagon of diameter 1, as found by Brass and Sharifi:

You’ll notice the triangle no longer has the same center as the circle!

To find this result, it was enough to keep the circle fixed, translate the triangle, and translate and rotate the pentagon. So, they searched through a 5-dimensional space, repeatedly computing the area of the convex hull of these three shapes to see how small they could make it. They considered 53,118,162 cases. Of these, 655,602 required further care—roughly speaking, they had to move the triangle and pentagon around slightly to see if they could make the area even smaller.

They say they could have done better if they’d also included a fourth shape, but this was computationally infeasible, since it would take them from a 5-dimensional search space to an 8-dimensional one. It’s possible that one could tackle this using a distributed computing project where a lot of people contribute computer time, like they do in the search for huge prime numbers.

If you hear of more progress on this issue, please let me know! I hope that sometime—perhaps tomorrow, perhaps decades hence—someone will report good news.

References

Hansen’s record-holding convex universal cover is here:

• H. Hansen, Small universal covers for sets of unit diameter, Geometriae Dedicata 42 (1992), 205–213.

It’s quite readable. This is where I got the picture of Pál’s solution and Sprague’s improvement.

The paper on the current best lower bound for convex universal coverings is also quite nice:

• Peter Brass and Mehrbod Sharifi, A lower bound for Lebesgue’s universal cover problem, International Journal of Computational Geometry & Applications 15 (2005), 537–544.

The picture of the equilateral triangle in the circle comes from an earlier paper, which got a lower bound of

by considering the circle and regular -gons of diameter 1 for all :

• Gy. Elekes, Generalized breadths, circular Cantor sets, and the least area UCC, Discrete & Computational Geometry 12 (1994), 439–449.

I have not yet managed to get ahold of Duff’s paper on the record-holding nonconvex universal covering:

• G. F. D. Duff, A smaller universal cover for sets of unit diameter, C. R. Math. Acad. Sci. 2 (1980), 37–42.

One interesting thing is that in 1963, Eggleston found a universal covering that’s minimal in the following sense: no subset of it is a universal covering. However, it doesn’t have the least possible area!

• H. G. Eggleston, Minimal universal covers in Israel J. Math. 1 (1963), 149–155.

Later, Kovalev showed that any ‘minimal’ universal covering in this sense is a star domain:

• M. D. Kovalev, A minimal Lebesgue covering exists (Russian), Mat. Zametki 40 (1986), 401–406, 430.

This means there’s a point inside the set such that for any other point in the set, the line segment connecting and is in the set. Any convex set is a star domain, but not conversely:

John Harte is an ecologist who uses maximum entropy methods to predict the distribution, abundance and energy usage of species. Marc Harper uses information theory in bioinformatics and evolutionary game theory. Harper, Harte and I are organizing a workshop on entropy and information in biological systems, and I’m really excited about it!

It’ll take place at the National Institute for Mathematical and Biological Synthesis in Knoxville Tennesee. We are scheduling it for Wednesday-Friday, April 8-10, 2015. When the date gets confirmed, I’ll post an advertisement so you can apply to attend.

Writing the proposal was fun, because we got to pull together lots of interesting people who are applying information theory and entropy to biology in quite different ways. So, here it is!

Proposal

Ever since Shannon initiated research on information theory in 1948, there have been hopes that the concept of information could serve as a tool to help systematize and unify work in biology. The link between information and entropy was noted very early on, and it suggested that a full thermodynamic understanding of biology would naturally involve the information processing and storage that are characteristic of living organisms. However, the subject is full of conceptual pitfalls for the unwary, and progress has been slower than initially expected. Premature attempts at ‘grand syntheses’ have often misfired. But applications of information theory and entropy to specific highly focused topics in biology have been increasingly successful, such as:

• the maximum entropy principle in ecology,
• Shannon and Rényi entropies as measures of biodiversity,
• information theory in evolutionary game theory,
• information and the thermodynamics of individual cells.

Because they work in diverse fields, researchers in these specific topics have had little opportunity to trade insights and take stock of the progress so far. The aim of the workshop is to do just this.

In what follows, participants’ names are in boldface, while the main goals of the workshop are in italics.

Roderick Dewar is a key advocate of the principle of Maximum Entropy Production, which says that biological systems—and indeed all open, non-equilibrium systems—act to produce entropy at the maximum rate. Along with others, he has applied this principle to make testable predictions in a wide range of biological systems, from ATP synthesis [DJZ2006] to respiration and photosynthesis of individual plants [D2010] and plant communities. He has also sought to derive this principle from ideas in statistical mechanics [D2004, D2009], but it remains controversial.

The first goal of this workshop is to study the validity of this principle.

While they may be related, the principle of Maximum Entropy Production should not be confused with the MaxEnt inference procedure, which says that we should choose the probabilistic hypothesis with the highest entropy subject to the constraints provided by our data. MaxEnt was first explicitly advocated by Jaynes. He noted that it is already implicit in the procedures of statistical mechanics, but convincingly argued that it can also be applied to situations where entropy is more ‘informational’ than ‘thermodynamic’ in character.

Recently John Harte has applied MaxEnt in this way to ecology, using it to make specific testable predictions for the distribution, abundance and energy usage of species across spatial scales and across habitats and taxonomic groups [Harte2008, Harte2009, Harte2011]. Annette Ostling is an expert on other theories that attempt to explain the same data, such as the ‘neutral model’ [AOE2008, ODLSG2009, O2005, O2012]. Dewar has also used MaxEnt in ecology [D2008], and he has argued that it underlies the principle of Maximum Entropy Production.

Thus, a second goal of this workshop is to familiarize all the participants with applications of the MaxEnt method to ecology, compare it with competing approaches, and study whether MaxEnt provides a sufficient justification for the principle of Maximum Entropy Production.

Entropy is not merely a predictive tool in ecology: it is also widely used as a measure of biodiversity. Here Shannon’s original concept of entropy naturally generalizes to ‘Rényi entropy’, which depends on a parameter . This equals

where is the fraction of organisms of the th type (which could mean species, some other taxon, etc.). In the limit this reduces to the Shannon entropy:

As increases, we give less weight to rare types of organisms. Christina Cobbold and Tom Leinster have described a systematic and highly flexible system of biodiversity measurement, with Rényi entropy at its heart [CL2012]. They consider both the case where all we have are the numbers , and the more subtle case where we take the distance between different types of organisms into account.

John Baez has explained the role of Rényi entropy in thermodynamics [B2011], and together with Tom Leinster and Tobias Fritz he has proved other theorems characterizing entropy which explain its importance for information processing [BFL2011]. However, these ideas have not yet been connected to the widespread use of entropy in biodiversity studies. More importantly, the use of entropy as a measure of biodiversity has not been clearly connected to MaxEnt methods in ecology. Does the success of MaxEnt methods imply a tendency for ecosystems to maximize biodiversity subject to the constraints of resource availability? This seems surprising, but a more nuanced statement along these general lines might be correct.

So, a third goal of this workshop is to clarify relations between known characterizations of entropy, the use of entropy as a measure of biodiversity, and the use of MaxEnt methods in ecology.

As the amount of data to analyze in genomics continues to surpass the ability of humans to analyze it, we can expect automated experiment design to become ever more important. In Chris Lee and Marc Harper’s RoboMendel program [LH2013], a mathematically precise concept of ‘potential information’—how much information is left to learn—plays a crucial role in deciding what experiment to do next, given the data obtained so far. It will be useful for them to interact with William Bialek, who has expertise in estimating entropy from empirical data and using it to constrain properties of models [BBS, BNS2001, BNS2002], and Susanne Still, who applies information theory to automated theory building and biology [CES2010, PS2012].

However, there is another link between biology and potential information. Harper has noted that in an ecosystem where the population of each type of organism grows at a rate proportional to its fitness (which may depend on the fraction of organisms of each type), the quantity

always decreases if there is an evolutionarily stable state [Harper2009]. Here is the fraction of organisms of the th genotype at a given time, while is this fraction in the evolutionarily stable state. This quantity is often called the Shannon information of ‘relative to’ . But in fact, it is precisely the same as Lee and Harper’s potential information! Indeed, there is a precise mathematical analogy between evolutionary games and processes where a probabilistic hypothesis is refined by repeated experiments.

Thus, a fourth goal of this workshop is to develop the concept of evolutionary games as ‘learning’ processes in which information is gained over time.

We shall try to synthesize this with Carl Bergstrom and Matina Donaldson-Matasci’s work on the ‘fitness value of information’: a measure of how much increase in fitness a population can obtain per bit of extra information [BL2004, DBL2010, DM2013]. Following Harper, we shall consider not only relative Shannon entropy, but also relative Rényi entropy, as a measure of information gain [Harper2011].

A fifth and final goal of this workshop is to study the interplay between information theory and the thermodynamics of individual cells and organelles.

Susanne Still has studied the thermodynamics of prediction in biological systems [BCSS2012]. And in a celebrated related piece of work, Jeremy England used thermodynamic arguments to a derive a lower bound for the amount of entropy generated during a process of self-replication of a bacterial cell [England2013]. Interestingly, he showed that E. coli comes within a factor of 3 of this lower bound.

In short, information theory and entropy methods are becoming powerful tools in biology, from the level of individual cells, to whole ecosystems, to experimental design, model-building, and the measurement of biodiversity. The time is ripe for an investigative workshop that brings together experts from different fields and lets them share insights and methods and begin to tackle some of the big remaining questions.

Bibliography

[AOE2008] D. Alonso, A. Ostling and R. Etienne, The assumption of symmetry and species abundance distributions, Ecology Letters 11 (2008), 93–105.

[TMMABB2012} D. Amodei, W. Bialek, M. J. Berry II, O. Marre, T. Mora, and G. Tkacik, The simplest maximum entropy model for collective behavior in a neural network, arXiv:1207.6319 (2012).

[B2011] J. Baez, Rényi entropy and free energy, arXiv:1102.2098 (2011).

[BFL2011] J. Baez, T. Fritz and T. Leinster, A characterization of entropy in terms of information loss, Entropy 13 (2011), 1945–1957.

[B2011] J. Baez and M. Stay, Algorithmic thermodynamics, Math. Struct. Comp. Sci. 22 (2012), 771–787.

[BCSS2012] A. J. Bell, G. E. Crooks, S. Still and D. A Sivak, The thermodynamics of prediction, Phys. Rev. Lett. 109 (2012), 120604.

[BL2004] C. T. Bergstrom and M. Lachmann, Shannon information and biological fitness, in IEEE Information Theory Workshop 2004, IEEE, 2004, pp. 50-54.

[BBS] M. J. Berry II, W. Bialek and E. Schneidman, An information theoretic approach to the functional classification of neurons, in Advances in Neural Information Processing Systems 15, MIT Press, 2005.

[BNS2001] W. Bialek, I. Nemenman and N. Tishby, Predictability, complexity and learning, Neural Computation 13 (2001), 2409–2463.

[BNS2002] W. Bialek, I. Nemenman and F. Shafee, Entropy and inference, revisited, in Advances in Neural Information Processing Systems 14, MIT Press, 2002.

[CL2012] C. Cobbold and T. Leinster, Measuring diversity: the importance of species similarity, Ecology 93 (2012), 477–489.

[CES2010] J. P. Crutchfield, S. Still and C. Ellison, Optimal causal inference: estimating stored information and approximating causal architecture, Chaos 20 (2010), 037111.

[D2004] R. C. Dewar, Maximum entropy production and non-equilibrium statistical mechanics, in Non-Equilibrium Thermodynamics and Entropy Production: Life, Earth and Beyond, eds. A. Kleidon and R. Lorenz, Springer, New York, 2004, 41–55.

[DJZ2006] R. C. Dewar, D. Juretíc, P. Zupanovíc, The functional design of the rotary enzyme ATP synthase is consistent with maximum entropy production, Chem. Phys. Lett. 430 (2006), 177–182.

[D2008] R. C. Dewar, A. Porté, Statistical mechanics unifies different ecological patterns, J. Theor. Bio. 251 (2008), 389–403.

[D2009] R. C. Dewar, Maximum entropy production as an inference algorithm that translates physical assumptions into macroscopic predictions: don’t shoot the messenger, Entropy 11 (2009), 931–944.

[D2010] R. C. Dewar, Maximum entropy production and plant optimization theories, Phil. Trans. Roy. Soc. B 365 (2010) 1429–1435.

[DBL2010} M. C. Donaldson-Matasci, C. T. Bergstrom, and
M. Lachmann, The fitness value of information, Oikos 119 (2010), 219-230.

[DM2013] M. C. Donaldson-Matasci, G. DeGrandi-Hoffman, and A. Dornhaus, Bigger is better: honey bee colonies as distributed information-gathering systems, Animal Behaviour 85 (2013), 585–592.

[England2013] J. L. England, Statistical physics of self-replication, J. Chem. Phys. 139 (2013), 121923.

[ODLSG2009} J. L. Green, J. K. Lake, J. P. O’Dwyer, A. Ostling and V. M. Savage, An integrative framework for stochastic, size-structured community assembly, PNAS 106 (2009), 6170--6175.

[Harper2009] M. Harper, Information geometry and evolutionary game theory, arXiv:0911.1383 (2009).

[Harper2011] M. Harper, Escort evolutionary game theory, Physica D 240 (2011), 1411–1415.

[Harte2008] J. Harte, T. Zillio, E. Conlisk and A. Smith, Maximum entropy and the state-variable approach to macroecology, Ecology 89 (2008), 2700–2711.

[Harte2009] J. Harte, A. Smith and D. Storch, Biodiversity scales from plots to biomes with a universal species-area curve, Ecology Letters 12 (2009), 789–797.

[Harte2011] J. Harte, Maximum Entropy and Ecology: A Theory of Abundance, Distribution, and Energetics, Oxford U. Press, Oxford, 2011.

[LH2013] M. Harper and C. Lee, Basic experiment planning via information metrics: the RoboMendel problem, arXiv:1210.4808 (2012).

[O2005] A. Ostling, Neutral theory tested by birds, Nature 436 (2005), 635.

[O2012] A. Ostling, Do fitness-equalizing tradeoffs lead to neutral communities?, Theoretical Ecology 5 (2012), 181–194.

[PS2012] D. Precup and S. Still, An information-theoretic approach to curiosity-driven reinforcement learning, Theory in Biosciences 131 (2012), 139–148.

This is the third thread for the Polymath8b project to obtain new bounds for the quantity

either for small values of (in particular ) or asymptotically as . The previous thread may be found here. The currently best known bounds on are:

• (Maynard) Assuming the Elliott-Halberstam conjecture, .
• (Polymath8b, tentative) . Assuming Elliott-Halberstam, .
• (Polymath8b, tentative) . Assuming Elliott-Halberstam, .
• (Polymath8b) for sufficiently large . Assuming Elliott-Halberstam, for sufficiently large .

Much of the current focus of the Polymath8b project is on the quantity

where ranges over square-integrable functions on the simplex

with being the quadratic forms

and

It was shown by Maynard that one has whenever , where is the narrowest diameter of an admissible -tuple. As discussed in the previous post, we have slight improvements to this implication, but they are currently difficult to implement, due to the need to perform high-dimensional integration. The quantity does seem however to be close to the theoretical limit of what the Selberg sieve method can achieve for implications of this type (at the Bombieri-Vinogradov level of distribution, at least); it seems of interest to explore more general sieves, although we have not yet made much progress in this direction.

The best asymptotic bounds for we have are

which we prove below the fold. The upper bound holds for all ; the lower bound is only valid for sufficiently large , and gives the upper bound on Elliott-Halberstam.

and so it is not yet clear whether (which would imply ). See this wiki page for some further upper and lower bounds on .

The best lower bounds are not obtained through the asymptotic analysis, but rather through quadratic programming (extending the original method of Maynard). This has given significant numerical improvements to our best bounds (in particular lowering the bound from to ), but we have not yet been able to combine this method with the other potential improvements (enlarging the simplex, using MPZ distributional estimates, and exploiting upper bounds on two-point correlations) due to the computational difficulty involved.

— 1. Upper bound —

We now prove the upper bound in (1). The key estimate is

giving the upper bound in (1).

It remains to prove (2). By Cauchy-Schwarz, it suffices to show that

But writing , the left-hand side evaluates to

as required.

This also suggests that extremal behave like for some function , and similarly for permutations. However, it is not possible to have exact equality in all variables simultaneously, which indicates that the upper bound (1) is not optimal, although in practice it does remarkably well for small .

— 2. Lower bound —

Using the notation of this previous post, we have the lower bound

whenever is supported on , , and are independent random variables on with density . We select the function

with , and for some to be chosen later. We have

and

and so

Observe that the random variables have mean

The variance may be bounded crudely by

Thus the random variable has mean at most and variance , with each variable bounded in magnitude by . By Hoeffding’s inequality, this implies that is at most with probability at most for some absolute constant . If we set for a sufficiently large absolute constant , we thus have

and thus

giving the lower bound in (1).

Hoeffding’s bound is proven by the exponential moment method, which more generally gives the bound

for any . However, this bound is inferior to the linear algebra method for small ; for instance, we can only obtain for by this method (compared to from quadratic programming), even if one uses the best available MPZ estimate.

Using , one can modify this lower bound, obtaining whenever we can find obeying

where

and

with

Details can be found at this comment.

— 3. Quadratic programming —

The expressions , are quadratic forms in , so one can (in principle, at least) obtain lower bounds for by restricting to a finite-dimensional space of and performing quadratic programming on the resulting finite-dimensional quadratic forms.

One can take to be symmetric without loss of generality. One can then look at functions that are linear combinations of symmetric polynomials

for various signatures ; actually it turns out numerically that one can get more efficient results by working with combinations of for up to a fixed degree, and for at that degree afterwords, where is the first symmetric polynomial. (Note that the GPY type sieves come from the case when is purely a function of .)

It may be that other choices of bases here are more efficient still (perhaps choosing bases that reflect the belief that should behave something like for some smallish ), but one numerical obstacle is that we are only able to accurately compute the required coefficients for in the case of polynomials.

Filed under: math.NA, math.NT, polymath Tagged: polymath8

My apologies for being far too busy to post. I’ll be much louder in couple of weeks once we release the Planck data — on March 21. Until then, I have to shut up and follow the Planck rules.

OK, back to editing. (I’ll try to update this post with any advance information as it becomes available.)

Update (on timing, not content): the main Planck press conference will be held on the morning of 21 March at 10am CET at ESA HQ in Paris. There will be a simultaneous UK event (9am GMT) held at the Royal Astronomical Society in London, where the Paris event will be streamed, followed by a local Q&A session. (There will also be a more technical afternoon session in Paris.)

Probably more important for my astrophysics colleagues: the Planck papers will be posted on the ESA website at noon on the 21st, after the press event, and will appear on the ArXiV the following day, 22 March. Be sure to set aside some time next weekend!

If you’re the kind of person who reads this blog, then you won’t have missed yesterday’s announcement of the first Planck cosmology results.

The most important is our picture of the cosmic microwave background itself:

But it takes a lot of work to go from the data coming off the Planck satellite to this picture. First, we have to make nine different maps, one at each of the frequencies in which Planck observes, from 30 GHz (with a wavelength of 1 cm) up to 850 GHz (0.350 mm) — note that the colour scales here are the same:

At low and high frequencies, these are dominated by the emission of our own galaxy, and there is at least some contamination over the whole range, so it takes hard work to separate the primordial CMB signal from the dirty (but interesting) astrophysics along the way. In fact, it’s sufficiently challenging that the team uses four different methods, each with different assumptions, to do so, and the results agree remarkably well.

In fact, we don’t use the above CMB image directly to do the main cosmological science. Instead, we build a Bayesian model of the data, combining our understanding of the foreground astrophysics and the cosmology, and marginalise over the astrophysical parameters in order to extract as much cosmological information as we can. (The formalism is described in the Planck likelihood paper, and the main results of the analysis are in the Planck cosmological parameters paper.)

The main tool for this is the power spectrum, a plot which shows us how the different hot and cold spots on our CMB map are distributed: In this plot, the left-hand side (low ℓ) corresponds to large angles on the sky and high ℓ to small angles. Planck’s results are remarkable for covering this whole range from ℓ=2 to ℓ=2500: the previous CMB satellite, WMAP, had a high-quality spectrum out to ℓ=750 or so; ground- and balloon-based experiments like SPT and ACT filled in some of the high-ℓ regime.

It’s worth marvelling at this for a moment, a triumph of modern cosmological theory and observation: our theoretical models fit our data from scales of 180° down to 0.1°, each of those bumps and wiggles a further sign of how well we understand the contents, history and evolution of the Universe. Our high-quality data has refined our knowledge of the cosmological parameters that describe the universe, decreasing the error bars by a factor of several on the six parameters that describe the simplest ΛCDM universe. Moreover, and maybe remarkably, the data don’t seem to require any additional parameters beyond those six: for example, despite previous evidence to the contrary, the Universe doesn’t need any additional neutrinos.

The quantity most well-measured by Planck is related to the typical size of spots in the CMB map; it’s about a degree, with an error of less than one part in 1,000. This quantity has changed a bit (by about the width of the error bar) since the previous WMAP results. This, in turn, causes us to revise our estimates of quantities like the expansion rate of the Universe (the Hubble constant), which has gone down, in fact by enough that it’s interestingly different from its best measurements using local (non-CMB) data, from more or less direct observations of galaxies moving away from us. Both methods have disadvantages: for the CMB, it’s a very indirect measurement, requiring imposing a model upon the directly measured spot size (known more technically as the “acoustic scale” since it comes from sound waves in the early Universe). For observations of local galaxies, it requires building up the famous cosmic distance ladder, calibrating our understanding of the distances to further and further objects, few of which we truly understand from first principles. So perhaps this discrepancy is due to messy and difficult astrophysics, or perhaps to interesting cosmological evolution.

This change in the expansion rate is also indirectly responsible for the results that have made the most headlines: it changes our best estimate of the age of the Universe (slower expansion means an older Universe) and of the relative amounts of its constituents (since the expansion rate is related to the geometry of the Universe, which, because of Einstein’s General Relativity, tells us the amount of matter).

But the cosmological parameters measured in this way are just Planck’s headlines: there is plenty more science. We’ve gone beyond the power spectrum above to put limits upon so-called non-Gaussianities which are signatures of the detailed way in which the seeds of large-scale structure in the Universe was initially laid down. We’ve observed clusters of galaxies which give us yet more insight into cosmology (and which seem to show an intriguing tension with some of the cosmological parameters). We’ve measured the deflection of light by gravitational lensing. And in work that I helped lead, we’ve used the CMB maps to put limits on some of the ways in which our simplest models of the Universe could be wrong, possibly having an interesting topology or rotation on the largest scales.

But because we’ve scrutinised our data so carefully, we have found some peculiarities which don’t quite fit the models. From the days of COBE and WMAP, there has been evidence that the largest angular scales in the map, a few degrees and larger, have some “anomalies” — some of the patterns show strange alignments, some show unexpected variation between two different hemispheres of the sky, and there are some areas of the sky that are larger and colder than is expected to occur in our theories. Individually, any of these might be a statistical fluke (and collectively they may still be) but perhaps they are giving us evidence of something exciting going on in the early Universe. Or perhaps, to use a bad analogy, the CMB map is like the Zapruder film: if you scrutinise anything carefully enough, you’ll find things that look a conspiracy, but turn out to have an innocent explanation.

I’ve mentioned eight different Planck papers so far, but in fact we’ve released 28 (and there will be a few more to come over the coming months, and many in the future). There’s an overall introduction to the Planck Mission, and papers on the data processing, observations of relatively nearby galaxies, and plenty more cosmology. The papers have been submitted to the journal A&A, they’re available on the ArXiV, and you can find a list of them at the ESA site.

Even more important for my cosmology colleagues, we’ve released the Planck data, as well, along with the necessary code and other information necessary to understand it: you can get it from the Planck Legacy Archive. I’m sure we’ve only just begun to get exciting and fun science out of the data from Planck. And this is only the beginning of Planck’s data: just the first 15 months of observations, and just the intensity of the CMB: in the coming years we’ll be analysing (and releasing) more than one more year of data, and starting to dig into Planck’s observations of the polarized sky.

This post is intended as a footnote to one that I wrote a couple of years ago about the meaning of “implies” in mathematics, which was part of a series of posts designed as an introduction to certain aspects of university mathematics.

If you are reasonably comfortable with the kind of basic logic needed in an undergraduate course, then you may enjoy trying to find the flaw in the following argument, which must have a flaw, since I’m going to prove a general statement and then give a counterexample to it. If you find the exercise extremely easy, then you may prefer to hold back so that others who find it harder will have a chance to think about it. Or perhaps I should just say that if you don’t find it easy, then I think it would be a good exercise to think about it for a while before looking at other people’s suggested solutions.

First up is the general statement. In fact, it’s a very general statement. Suppose you are trying to prove a statement and you have a hypothesis to work with. In other words, you are trying to prove the statement

Now if and are two statements, then is true if and only if either is false or is true. Hence what we are trying to prove can be rewritten as follows.

Now we can bring the inside the as long as we convert the into , so let’s do that. What we want to prove becomes this.

I’ll assume here that we haven’t done something foolish and given the name to one of the variables involved in the statement . So now I’m going to use the general rule that is equivalent to to rewrite what we want to prove as the following.

Finally, let’s rewrite what’s inside the brackets using the sign.

Every single step I took there was a logical equivalence, so the conclusion is that if you want to show that implies , your task is the same as that of finding a single such that .

Now let me give a counterexample to that useful logical principle. Let be a set of real numbers. Define the diameter of to be . I’ll write it .

Consider the following implication.

That is clearly correct: if every element of has modulus at most 1, then is contained in the interval , so clearly can’t have diameter greater than 2.

But then, by the logical principle just derived, there must be a single element of such that if that element has modulus at most 1, then the diameter of is at most 2. In other words,

But that is clearly nonsense. If all we know is that one particular element of has modulus at most 1, it can’t possibly imply that has diameter at most 2.

What has gone wrong here? If you can give a satisfactory answer, then you will have a good grasp of what mathematicians mean by “implies”.

[Note: If you missed Wednesday evening's discussion of particle physics involving me, Sean Carroll and Alan Boyle, you can listen to it here.]

I still have a lot of work to do before I can myself write intelligently about the Fukushima Daiichi nuclear plant, and the nuclear accident and cleanup that occurred there. (See here and here for a couple of previous posts about it.) But I did want to draw your attention to one of the better newspaper articles that I’ve seen written about it, by Ian Sample at the Guardian. I can’t vouch for everything that Sample says, but given what I’ve read and investigated myself, I think he finds the right balance. He’s neither scaring people unnecessarily, nor reassuring them that everything will surely be just fine and that there’s no reason to be worried about anything. From what I know and understand, the situation is more or less just as serious and worthy of concern as Sample says it is; but conversely, I don’t have any reason to think it is much worse than what he describes.

Meanwhile, just as I don’t particularly trust anything said by TEPCO, the apparently incompetent and corrupt Japanese power company that runs and is trying to clean up the Fukushima plant, I’m also continuing to see lots of scary articles — totally irresponsible — written by people who should know better but seem bent upon frightening the public. The more wild the misstatements and misleading statements, the better, it seems.

One example of this kind of fear-mongering is to be found here: http://truth-out.org/news/item/19547-fukushima-a-global-threat-that-requires-a-global-response, by Kevin Zeese and Margaret Flowers. It’s one piece of junk after the next: the strategy is to take a fact, take another unrelated fact, quote a non-expert (or quote an expert out of context), stick them all together, and wow! frightening!! But here’s the thing: An experienced and attentive reader will know, after a few paragraphs, to ignore this article. Why?

Because it never puts anything in context. “When contact with radioactive cesium occurs, which is highly unlikely, a person can experience cell damage due to radiation of the cesium particles. Due to this, effects such as nausea, vomiting, diarrhea and bleeding may occur. When the exposure lasts a long time, people may even lose consciousness. Coma or even death may then follow. How serious the effects are depends upon the resistance of individual persons and the duration of exposure and the concentration a person is exposed to, experts say.” Well, how much cesium are we talking about here? Lots or a little? Ah, they don’t tell you that. [The answer: enormous amounts. There's no chance of you getting anywhere near that amount of exposure unless you yourself go wandering around on the Fukushima grounds, and go some place you're really not supposed to go. This didn't even happened to the workers who were at the Fukushima plant when everything was at its worst in March 2011. Even if you ate a fish every week from just off Japan that had a small amount of cesium in it, this would not happen to you.]

Because it makes illogical statements. “Since the accident at Fukushima on March 11, 2011, three reactor cores have gone missing.” Really? Gone missing? Does that make sense? Well then, why is so much radioactive cooling water — which is mentioned later in the article — being stored up at the Fukushima site? Isn’t that water being used to keep those cores cool? And how could that happen if the cores were missing? [The cores melted; it's not known precisely what shape they are in or precisely how much of each is inside or outside the original containment vessel, but they're being successfully cooled by water, so it's clear roughly where they are. They're not "missing"; that's a wild over-statement.]

Because the authors quote people without being careful to explain clearly who they are. “Harvey Wasserman, who has been working on nuclear energy issues for over 40 years,…” Is Harvey Wasserman a scientist or engineer? No.  But he gets lots of press in this article (and elsewhere.) [Wikipedia says: "Harvey Franklin Wasserman (born December 31, 1945) is an American journalist, author, democracy activist, and advocate for renewable energy. He has been a strategist and organizer in the anti-nuclear movement in the United States for over 30 years." I have nothing against Mr. Wasserman and I personally support both renewable energy and the elimination of nuclear power. But as far as I know, Wasserman has no scientific training, and is not an expert on cleaning up a nuclear plant and the risks thereof... and he's an anti-nuclear activist, so you do have to worry he's going to make thing sound worse than they are. Always look up the people being quoted!]

Because the article never once provides balance or nuance: absolutely everything is awful, awful, awful. I’m sorry, but things are never that black and white, or rather, black and black. There are shades of gray in the real world, and it’s important to tease them out a little bit. There are eventualities that would be really terrible, others that would be unfortunate, still others that would merely be a little disruptive in the local area — and they’re not equally bad, nor are they equally likely. [I don't get any sense that the authors are trying to help their readers understand; they're just bashing the reader over the head with one terrifying-sounding thing after another. This kind of article just isn't credible.]

The lesson: one has to be a critical, careful reader, and read between the lines! In contrast to Sample’s article in the Guardian, the document by Zeese and Flowers is not intended to inform; it is intended to frighten, period. I urge you to avoid getting your information from sources like that one. Find reliable, sensible people — Ian Sample is in that category, I think — and stick with them. And I would ignore anything Zeese and Flowers have to say in the future; people who’d write an article like theirs have no credibility.

Oscar Chacaltana, Yuji Tachikawa and I are deep in the weeds of nilpotent orbits. One of the things we had to study were the nilpotent orbits of $\mathfrak{g}_2$, and how they sit in $\mathfrak{so}(8)$. Understanding the answer involves an explicit description of $Spin(8)$ triality, which I thought was kinda cute. Few people will care about the nilpotent orbits, but the bit about triality and $G_2$ might be of some independent interest. So here it is.

Under this decomposition, the action of triality is easy to describe: pick one of the $\mathfrak{sl}(2)$ subalgebras to hold fixed, and consider all permutations of the other three (supplemented by the obvious action on the $(2,2,2,2)$).

That’s triality. Looked at this way, it seems absurdly simple. The above description gives a perfectly concrete action of triality, as permutations of the generators. And we can push a little harder, and really understand $\mathfrak{g}_2$, this way.

The subalgebra, invariant under the $S_3$ permutations, is $\mathfrak{g}_2\subset \mathfrak{so}(8)$, under which

where $V$ is the 2-dimensional irreducible representation of $S_3$. In terms of our previous decomposition,

where the first $SU(2)$ is the one you kept fixed, and ${SU(2)}_D$ is the diagonal $SU(2)$ of the three which are permuted by triality. Under this embedding,

An explicit basis of antisymmetric $8\times 8$ matrices which give this $\mathfrak{g}_2$ subalgebra is as follows. First, we embed ${\mathfrak{sl}(2)}^4$, by taking the $8\times 8$ matrix to be block-diagonal, with $4\times 4$ blocks containing ${\mathfrak{sl}(2)}^2$, as

where we’ve chosen the normalization conventions

We pick one of these (the ${\mathfrak{sl}(2)}_L$ in the upper left-hand block) to hold fixed, and embed our second $\mathfrak{sl}(2)$ diagonally in the other three:

The highest weight of the $(2,4)$ is

The remaining ones, e.g., $S_{-1,3} = [Y_1, S_{1,3}]$, are obtained by acting with the lowering operators, $Y_{1,2}$. With this choice of Cartan, the simple roots of $\mathfrak{g}_2$ correspond to $X_2$ (short root) and $S_{1,-3}$ (long root).

This 8-dimensional representation of $G_2$, as it’s reducible, is not the most convenient one for studying the representation theory of $G_2$. But it’s tailor-made for our purpose, which is understanding the embedding in $Spin(8)$. With an explicit embedding in hand, we can manufacture a distinguished triple, $(H,X,Y)$ for each nilpotent orbit of $\mathfrak{g}_2$, and see how it sits in $\mathfrak{so}(8)$. But that, probably, holds little interest for the general reader, so I’ll end here.

I’ve been spending several weeks at the Simons Center for Geometry and Physics. Towards the end of my stay, I got into a discussion with Tim Nguyen, about Ricci flow and nonlinear $\sigma$-models. He’d been reading Friedan’s PhD thesis, alongside [Kevin Costello’s book](http://www.ams.org/bookstore-getitem/item=SURV-170). So I pointed him to some old notes of mine on the normal coordinate expansion, a key ingredient in renormalizing nonlinear $\sigma$-models, using the background-field method.

Then it occurred to me that the internet would be a much more useful place for those notes. So, since I have some time to kill, in JFK, here they are.

Exercise 1: Compute the next term in the expansion, $$\begin{split} \tfrac{1}{12}g(\nabla_v\xi,(\nabla R)(\xi,\xi,\nabla_v\xi)\xi) +\tfrac{2}{15}g(R(\xi,v)\xi,R(\xi,\nabla_v\xi)\xi) +\tfrac{1}{15}g(\nabla_v\xi,(\nabla\nabla R)(\xi,\xi,\xi,v)\xi)\\ +\tfrac{7}{60}g(R(\xi,v)\xi,(\nabla R)(\xi,\xi,v)\xi) +\tfrac{1}{120}g(v,(\nabla\nabla\nabla R)(\xi,\xi,\xi,\xi,v)\xi) \end{split}$$

Sonia was chatting with me about this PRL (arXiv version), which seems to have made a splash in the news media and in the blogosphere. She couldn’t make heads or tails of it and (as you will see), I didn’t do much better. But I thought that I would take the opportunity to lay out a few relevant remarks.

Since we’re going to be talking about the Uncertainty Principle, and measurements, it behoves us to formulate our discussion in terms of density matrices.

A quantum system is described in terms of a density matrix, $\rho$, which is a self-adjoint, positive-semidefinite trace-class operator, satisfying

In the Schrödinger picture (which we will use), it evolves unitarily in time

except when a measurement is made.

Consider a self-adjoint operator $A$ (an “observable”). We will assume that $A$ has a pure point spectrum, and let $P^{(A)}_i$ be the projection onto the $i^{\text{th}}$ eigenspace of $A$.

When we measure $A$, quantum mechanics computes for us

1. A classical probability distribution for the values on the readout panel of the measuring apparatus. The moments of this probability distribution are computed by taking traces. The $n^{\text{th}}$ moment is $${\langle A^n\rangle} = Tr(A^n\rho)$$ In particular, the variance is $${(\Delta A)}^2 = Tr(A^2\rho) - {\left(Tr(A\rho)\right)}^2$$
2. A change (which, under the assumptions stated, can be approximated as occurring instantaneously) in the density matrix,

Thereafter, the system, described by the new density matrix, $\hat{\rho}$, again evolves unitarily, according to (1).

The new density matrix, $\hat{\rho}$, after the measurement¹, can be completely characterized by two properties

1. All of the moments of $A$ are the same as before $$\langle A^n\rangle = Tr(A^n \hat{\rho}(\rho,A))= Tr(A^n \rho)$$ (In particular, $\Delta A$ is unchanged.) Moreover, for any observable, $C$, which commutes with $A$ ( $[C,A]=0$ ), $$\langle C^n\rangle = Tr(C^n \hat{\rho}(\rho,A))= Tr(C^n \rho)$$
2. However, the measurement has destroyed all interference between the different eigenspaces of $A$ $$Tr([A,B] \hat{\rho}(\rho,A)) = 0, \qquad \forall\, B$$

Note that it is really important that I have assumed a pure point spectrum. If $A$ has a continuous spectrum, then you have to deal with complications both physical and mathematical. Mathematically, you need to deal with the complications of the Spectral Theorem; physically, you have to put in finite detector resolutions, in order to make proper sense of what a “measurement” does. I’ll explain, later, how to deal with those complications

Now consider two such observables, $A$ and $B$. The Uncertainty Principle gives a lower bound on the product

in any state, $\rho$. (Exercise: Generalize the usual proof, presented for “pure states” to the case of density matrices.)

As stated, (3) is not a statement about the uncertainties in any actual sequence of measurements. After all, once you measure $A$, in state $\rho$, the density matrix changes, according to (2), to

so a subsequent measurement of $B$ is made in a different state from the initial one.

The obvious next thing to try is to note that, since the uncertainty of $A$ in the state $\hat{\rho}(\rho,A)$ is the *same* as in the state $\rho$, and since we are measuring $B$ in the state $\hat{\rho}(\rho,A)$, we can apply the Uncertainty Relation, (3) in the state $\hat{\rho}$, instead of in the state, $\rho$. Unfortunately, $Tr([A,B]\hat{\rho}(\rho,A))=0$, so this leads to an uninteresting lower bound on the product the uncertainties

for a measurement of $A$ immediately followed by a measurement of $B$.

It is, apparently, possible to derive a better lower bound on the product of the uncertainties of successive measurements (which is still, of course, weaker than the “naïve” $\tfrac{1}{2}\left|Tr(-i[A,B]\rho)\right|$, which is what you might have guessed for the lower bound, had you not thought about what (3) means). But I don’t know how to even state that result at the level of generality of the above discussion

Instead, I’d like to discuss how one treats measurements, when $A$ doesn’t have a pure point spectrum. When it’s discussed at all, it’s treated very poorly in the textbooks.

Measuring Unbounded Operators

Let’s go straight to the worst-case, of an unbounded operator, with $Spec(A)=\mathbb{R}$. Such an operator has no eigenvectors at all. What happens when we measure such an observable? Clearly, the two conditions which characterized the change in the density matrix, in the case of a pure point spectrum,

1. $Tr(A^n \hat{\rho}(\rho,A))= Tr(A^n \rho)$
2. $Tr([A,B] \hat{\rho}(\rho,A)) = 0, \qquad \forall\, B$

are going to have to be modified. The second condition clearly can’t hold for all choice of $B$, in the unbounded case (think $A=\mathbf{x}$ and $B=\mathbf{p}$). As to the first condition, we might *hope* that the moments of the classical probability distribution for the observed measurements of $A$ would be calculated by taking traces with the density matrix, $\hat{\rho}$. But that probability distribution *depends* on the resolution of the detector, something which the density matrix, $\rho$, knows nothing about.

To keep things simple, let’s specialize to $\mathcal{H}=\mathcal{L}^2(\mathbb{R})$ and $A=\mathbf{x}$. Let’s imagine a detector which can measure the particle’s position with a resolution, $\sigma$. Let’s define a projection operator

which reflects the notion that our detector has measured the position to be $x_0$, to within an accuracy $\sigma$. Here, I’ve chosen a Gaussian; but really any acceptance function peaked at $x=x_0$, and dying away sufficiently fast away from $x_0$ will do (and may more-accurately reflect the properties of your actual detector).

But I only know how to do Gaussian integrals, so this one is a convenient choice.

This is, indeed, a projection operator: $P_{x_0}P_{x_0} = P_{x_0}$. But integrating over $x_0$ doesn’t quite give the completeness relation one would want

Instead we find

Rather than getting $\psi(x)$ back, we get $\psi(x)$ smeared against a Gaussian.

To fix this, we need to consider a more general class of projection operators (here, again, the Gaussian acceptance function proves very convenient):

These are still projection operators,

But now they obey the completeness relation

so we can now assert that the density matrix after measuring $\mathbf{x}$ is

If $\rho$ is represented by the integral kernel, $K(x,y)$:

then the new density matrix, $\hat{\rho}$ is represented by the integral kernel

Here we see clearly that it has the desired properties:

1. The off-diagonal terms are suppressed; $\hat{K}(x,y)\to 0$ for $|x-y|\gg \sigma$.
2. The near-diagonal terms are smeared by a Gaussian, representing the finite resolution of the detector.

Moreover, the moments of the probability distribution for the measured value of $x$ are given by taking traces with $\hat{\rho}$: