From Bose-Einstein condensates to the nonlinear Schrodinger equation

The Schrödinger equation

is the fundamental equation of motion for (non-relativistic) quantum mechanics, modeling both one-particle systems and -particle systems for . Remarkably, despite being a linear equation, solutions to this equation can be governed by a non-linear equation in the large particle limit . In particular, when modeling a Bose-Einstein condensate with a suitably scaled interaction potential in the large particle limit, the solution can be governed by the cubic nonlinear Schrödinger equation

I recently attended a talk by Natasa Pavlovic on the rigorous derivation of this type of limiting behaviour, which was initiated by the pioneering work of Hepp and Spohn, and has now attracted a vast recent literature. The rigorous details here are rather sophisticated; but the heuristic explanation of the phenomenon is fairly simple, and actually rather pretty in my opinion, involving the foundational quantum mechanics of -particle systems. I am recording this heuristic derivation here, partly for my own benefit, but perhaps it will be of interest to some readers.

This discussion will be purely formal, in the sense that (important) analytic issues such as differentiability, existence and uniqueness, etc. will be largely ignored.

Reading seminar 5: “Stable group theory and approximate subgroups”, by Ehud Hrushovski

After a one-week hiatus, we are resuming our reading seminar of the Hrushovski paper. This week, we are taking a break from the paper proper, and are instead focusing on the subject of stable theories (or more precisely, -stable theories), which form an important component of the general model-theoretic machinery that the Hrushovski paper uses. (Actually, Hrushovski’s paper needs to work with more general theories than the stable ones, but apparently many of the tools used to study stable theories will generalise to the theories studied in this paper.)

Roughly speaking, stable theories are those in which there are “few” definable sets; a classic example is the theory of algebraically closed fields (of characteristic zero, say), in which the only definable sets are boolean combinations of algebraic varieties. Because of this paucity of definable sets, it becomes possible to define the notion of the Morley rank of a definable set (analogous to the dimension of an algebraic set), together with the more refined notion of Morley degree of such sets (analogous to the number of top-dimensional irreducible components of an algebraic set). Stable theories can also be characterised by their inability to order infinite collections of elements in a definable fashion.

The material here was presented by Anush Tserunyan; her notes on the subject can be found here. Let me also repeat the previous list of resources on this paper (updated slightly):

• Henry Towsner’s notes (which most of Notes 2-4 have been based on; updated to remove references to homogeneity, using only countable saturation);
• Alex Usvyatsov’s notes on the derivation of Corollary 1.2 (broadly parallel to the notes here);
• Lou van den Dries’ notes (covering most of what we have done so far, and also material on stable theories); and
• Anand Pillay’s sketch of a simplified proof of Theorem 1.1.

UCLA Math Seeks Exceptional Student for Undergraduate Merit Scholarship

[A little bit of advertising on behalf of my maths dept.  Unfortunately funding for this scholarship was secured only very recently, so the application deadline is extremely near, which is why I am publicising it here, in case someone here may know of a suitable applicant. – T.]

UCLA Mathematics has launched a new scholarship to be granted to an entering freshman who has an exceptional background and promise in mathematics. The UCLA Math Undergraduate Merit Scholarship provides for full tuition, and a room and board allowance. To be considered for fall 2010, candidates must apply on or before November 30, 2009. Details and online application for the scholarship are available here.

Eligibility Requirements:

• 12th grader applying to UCLA for admission in Fall of 2010.
• Outstanding academic record and standardized test scores.
• Evidence of exceptional background and promise in mathematics, such as: placing in the top 25% in the U.S.A. Mathematics Olympiad (USAMO) or comparable (International Mathematics Olympiad level) performance on a similar national competition.
• Strong preference will be given to International Mathematics Olympiad medalists.

Nonstandard analogues of energy and density increment arguments

In the course of the ongoing logic reading seminar at UCLA, I learned about the property of countable saturation. A model of a language is countably saturated if, every countable sequence of formulae in (involving countably many constants in ) which is finitely satisfiable in (i.e. any finite collection in the sequence has a solution in ), is automatically satisfiable in (i.e. there is a solution to all simultaneously). Equivalently, a model is countably saturated if the topology generated by the definable sets is countably compact.

Update, Nov 19: I have learned that the above terminology is not quite accurate; countable saturation allows for an uncountable sequence of formulae, as long as the constants used remain finite. So, the discussion here involves a weaker property than countable saturation, which I do not know the official term for. If one chooses a special type of ultrafilter, namely a “countably incomplete” ultrafilter, one can recover the full strength of countable saturation, though it is not needed for the remarks here. Most models are not countably saturated. Consider for instance the standard natural numbers as a model for arithmetic. Then the sequence of formulae “” for is finitely satisfiable in , but not satisfiable.

However, if one takes a model of and passes to an ultrapower , whose elements consist of sequences in , modulo equivalence with respect to some fixed non-principal ultrafilter , then it turns out that such models are automatically countably compact. Indeed, if are finitely satisfiable in , then they are also finitely satisfiable in (either by inspection, or by appeal to Los’s theorem and/or the transfer principle in non-standard analysis), so for each there exists which satisfies . Letting be the ultralimit of the , we see that satisfies all of the at once.

In particular, non-standard models of mathematics, such as the non-standard model of the natural numbers, are automatically countably saturated.

This has some cute consequences. For instance, suppose one has a non-standard metric space (an ultralimit of standard metric spaces), and suppose one has a standard sequence of elements of which are standard-Cauchy, in the sense that for any standard one has for all sufficiently large . Then there exists a non-standard element such that standard-converges to in the sense that for every standard one has for all sufficiently large . Indeed, from the standard-Cauchy hypothesis, one can find a standard for each standard that goes to zero (in the standard sense), such that the formulae “” are finitely satisfiable, and hence satisfiable by countable saturation. Thus we see that non-standard metric spaces are automatically “standardly complete” in some sense.

This leads to a non-standard structure theorem for Hilbert spaces, analogous to the orthogonal decomposition in Hilbert spaces:

Theorem 1 (Non-standard structure theorem for Hilbert spaces) Let be a non-standard Hilbert space, let be a bounded (external) subset of , and let . Then there exists a decomposition , where is “almost standard-generated by ” in the sense that for every standard , there exists a standard finite linear combination of elements of which is within of , and is “standard-orthogonal to ” in the sense that for all .

Proof: Let be the infimum of all the (standard) distances from to a standard linear combination of elements of , then for every standard one can find a standard linear combination of elements of which lie within of . From the parallelogram law we see that is standard-Cauchy, and thus standard-converges to some limit , which is then almost standard-generated by by construction. An application of Pythagoras then shows that is standard-orthogonal to every element of .

This is the non-standard analogue of a combinatorial structure theorem for Hilbert spaces (see e.g. Theorem 2.6 of my FOCS paper). There is an analogous non-standard structure theorem for -algebras (the counterpart of Theorem 3.6 from that paper) which I will not discuss here, but I will give just one sample corollary:

Theorem 2 (Non-standard arithmetic regularity lemma) Let be a non-standardly finite abelian group, and let be a function. Then one can split , where is standard-uniform in the sense that all Fourier coefficients are (uniformly) , and is standard-almost periodic in the sense that for every standard , one can approximate to error in norm by a standard linear combination of characters (which is also bounded).

This can be used for instance to give a non-standard proof of Roth’s theorem (which is not much different from the “finitary ergodic” proof of Roth’s theorem, given for instance in Section 10.5 of my book with Van Vu). There is also a non-standard version of the Szemerédi regularity lemma which can be used, among other things, to prove the hypergraph removal lemma (the proof then becomes rather close to the infinitary proof of this lemma in this paper of mine). More generally, the above structure theorem can be used as a substitute for various “energy increment arguments” in the combinatorial literature, though it does not seem that there is a significant saving in complexity in doing so unless one is performing quite a large number of these arguments.

One can also cast density increment arguments in a nonstandard framework. Here is a typical example. Call a non-standard subset of a non-standard finite set dense if one has for some standard .

Theorem 3 Suppose Szemerédi’s theorem (every set of integers of positive upper density contains an arithmetic progression of length ) fails for some . Then there exists an unbounded non-standard integer , a dense subset of with no progressions of length , and with the additional property that

for any subprogression of of unbounded size (thus there is no sizeable density increment on any large progression).

Proof: Let be a (standard) set of positive upper density which contains no progression of length . Let be the asymptotic maximal density of inside a long progression, thus . For any , one can then find a standard integer and a standard subset of of density at least such that can be embedded (after a linear transformation) inside , so in particular has no progressions of length . Applying the saturation property, one can then find an unbounded and a set of of density at least for every standard (i.e. of density at least ) with no progressions of length . By construction, we also see that for any subprogression of of unbounded size, hs density at most for any standard , thus has density at most , and the claim follows.

This can be used as the starting point for any density-increment based proof of Szemerédi’s theorem for a fixed , e.g. Roth’s proof for , Gowers’ proof for arbitrary , or Szemerédi’s proof for arbitrary . (It is likely that Szemerédi’s proof, in particular, simplifies a little bit when translated to the non-standard setting, though the savings are likely to be modest.)

I’m also hoping that the recent results of Hrushovski on the noncommutative Freiman problem require only countable saturation, as this makes it more likely that they can be translated to a non-standard setting and thence to a purely finitary framework.

An elementary non-commutative Freiman theorem

Let be a finite subset of a non-commutative group . As mentioned previously on this blog (as well as in the current logic reading seminar), there is some interest in classifying those which obey small doubling conditions such as or . A full classification here has still not been established. However, I wanted to record here an elementary argument (based on Exercise 2.6.5 of my book with Van Vu, which in turn is based on this paper of Izabella Laba) that handles the case when is very close to :

Proposition 1 If , then and are both finite groups, which are conjugate to each other. In particular, is contained in the right-coset (or left-coset) of a group of order less than .

Remark 1 The constant is completely sharp; consider the case when where is the identity and is an element of order larger than . This is a small example, but one can make it as large as one pleases by taking the direct product of and with any finite group. In the converse direction, we see that whenever is contained in the right-coset (resp. left-coset ) of a group of order less than , then (resp. ) is necessarily equal to all of , by the inclusion-exclusion principle (see the proof below for a related argument).

Proof: We begin by showing that is a group. As is symmetric and contains the identity, it suffices to show that this set is closed under addition.

Let . Then we can write and for . If were equal to , then and we would be done. Of course, there is no reason why should equal ; but we can use the hypothesis to boost this as follows. Observe that and both have cardinality and lie inside , which has cardinality strictly less than . By the inclusion-exclusion principle, this forces to have cardinality greater than . In other words, there exist more than pairs such that , which implies that . Thus there are more than elements such that for some (since is uniquely determined by ); similarly, there exists more than elements such that for some . Again by inclusion-exclusion, we can thus find in for which one has simultaneous representations and , and so , and the claim follows.

In the course of the above argument we showed that every element of the group has more than representations of the form for . But there are only pairs available, and thus .

Now let be any element of . Since , we have , and so . Conversely, every element of has exactly representations of the form where . Since occupies more than half of , we thus see from the inclusion-exclusion principle, there is thus at least one representation for which both lie in . In other words, , and the claim follows.

To relate this to the classical doubling constants , we first make an easy observation:

Lemma 2 If , then .

Again, this is sharp; consider equal to where generate a free group.

Proof: Suppose that is an element of for some . Then the sets and have cardinality and lie in , so by the inclusion-exclusion principle, the two sets intersect. Thus there exist such that , thus . This shows that is contained in . The converse inclusion is proven similarly.

Proposition 3 If , then is a finite group of order , and for some in the normaliser of .

The factor is sharp, by the same example used to show sharpness of Proposition 1. However, there seems to be some room for further improvement if one weakens the conclusion a bit; see below the fold.

Proof: Let (the two sets being equal by Lemma 2). By the argument used to prove Lemma 2, every element of has more than representations of the form for . By the argument used to prove Proposition 1, this shows that is a group; also, since there are only pairs , we also see that .

Pick any ; then , and so . Because every element of has representations of the form with , , and occupies more than half of and of , we conclude that each element of lies in , and so and .

The intersection of the groups and contains , which is more than half the size of , and so we must have , i.e. normalises , and the proposition follows.

Because the arguments here are so elementary, they extend easily to the infinitary setting in which is now an infinite set, but has finite measure with respect to some translation-invariant Kiesler measure . We omit the details. (I am hoping that this observation may help simplify some of the theory in that setting.)

Reading seminar 4: “Stable group theory and approximate subgroups”, by Ehud Hrushovski

This week, Henry Towsner concluded his portion of reading seminar of the Hrushovski paper, by discussing (a weaker, simplified version of) main model-theoretic theorem (Theorem 3.4 of Hrushovski), and described how this theorem implied the combinatorial application in Corollary 1.2 of Hrushovski. The presentation here differs slightly from that in Hrushovski’s paper, for instance by avoiding mention of the more general notions of S1 ideals and forking.

Here is a collection of resources so far on the Hrushovski paper:

• Henry Towsner’s notes (which most of Notes 2-4 have been based on);
• Alex Usvyatsov’s notes on the derivation of Corollary 1.2 (broadly parallel to the notes here);
• Lou van den Dries’ notes (covering most of what we have done so far, and also material on stable theories); and
• Anand Pillay’s sketch of a simplified proof of Theorem 1.1.

The “no self-defeating object” argument

A fundamental tool in any mathematician’s toolkit is that of reductio ad absurdum: showing that a statement is false by assuming first that is true, and showing that this leads to a logical contradiction. A particulary pure example of reductio ad absurdum occurs when establishing the non-existence of a hypothetically overpowered object or structure , by showing that ‘s powers are “self-defeating”: the very existence of and its powers can be used (by some clever trick) to construct a counterexample to that power. Perhaps the most well-known example of a self-defeating object comes from the omnipotence paradox in philosophy (“Can an omnipotent being create a rock so heavy that He cannot lift it?”); more generally, a large number of other paradoxes in logic or philosophy can be reinterpreted as a proof that a certain overpowered object or structure does not exist.

In mathematics, perhaps the first example of a self-defeating object one encounters is that of a largest natural number:

Proposition 1 (No largest natural number) There does not exist a natural number which is larger than all other natural numbers.

Proof: Suppose for contradiction that there was such a largest natural number . Then is also a natural number which is strictly larger than , contradicting the hypothesis that is the largest natural number.

Note the argument does not apply to the extended natural number system in which one adjoins an additional object beyond the natural numbers, because is defined equal to . However, the above argument does show that the existence of a largest number is not compatible with the Peano axioms.

This argument, by the way, is perhaps the only mathematical argument I know of which is routinely taught to primary school children by other primary school children, thanks to the schoolyard game of naming the largest number. It is arguably one’s first exposure to a mathematical non-existence result, which seems innocuous at first but can be surprisingly deep, as such results preclude in advance all future attempts to establish existence of that object, no matter how much effort or ingenuity is poured into this task. One sees this in a typical instance of the above schoolyard game; one player tries furiously to cleverly construct some impressively huge number , but no matter how much effort is expended in doing so, the player is defeated by the simple response “… plus one!” (unless, of course, is infinite, ill-defined, or otherwise not a natural number).

It is not only individual objects (such as natural numbers) which can be self-defeating; structures (such as orderings or enumerations) can also be self-defeating. (In modern set theory, one considers structures to themselves be a kind of object, and so the distinction between the two concepts is often blurred.) Here is one example (related to, but subtly different from, the previous one):

Proposition 2 (The natural numbers cannot be finitely enumerated) The natural numbers cannot be written as for any finite collection of natural numbers.

Proof: Suppose for contradiction that such an enumeration existed. Then consider the number ; this is a natural number, but is larger than (and hence not equal to) any of the natural numbers , contradicting the hypothesis that is enumerated by .

Here it is the enumeration which is self-defeating, rather than any individual natural number such as or . (For this post, we allow enumerations to contain repetitions.)

The above argument may seem trivial, but a slight modification of it already gives an important result, namely Euclid’s theorem:

Proposition 3 (The primes cannot be finitely enumerated) The prime numbers cannot be written as for any finite collection of prime numbers.

Proof: Suppose for contradiction that such an enumeration existed. Then consider the natural number ; this is a natural number larger than which is not divisible by any of the primes . But, by the fundamental theorem of arithmetic (or by the method of Infinite descent, which is another classic application of reductio ad absurdum), every natural number larger than must be divisible by some prime, contradicting the hypothesis that is enumerated by .

Remark 1 Continuing the number-theoretic theme, the “dueling conspiracies” arguments in a previous blog post can also be viewed as an instance of this type of “no-self-defeating-object”; for instance, a zero of the Riemann zeta function at implies that the primes anti-correlate almost completely with the multiplicative function , which is self-defeating because it also implies complete anti-correlation with , and the two are incompatible. Thus we see that the prime number theorem (a much stronger version of Proposition 3) also emerges from this type of argument.

In this post I would like to collect several other well-known examples of this type of “no self-defeating object” argument. Each of these is well studied, and probably quite familiar to many of you, but I feel that by collecting them all in one place, the commonality of theme between these arguments becomes more apparent. (For instance, as we shall see, many well-known “paradoxes” in logic and philosophy can be interpreted mathematically as a rigorous “no self-defeating object” argument.)

Displaying maths online, II

As the previous discussion on displaying mathematics on the web has become quite lengthy, I am opening a fresh post to continue the topic.  I’m leaving the previous thread open for those who wish to respond directly to some specific comments in that thread, but otherwise it would be preferable to start afresh on this thread to make it easier to follow the discussion.

It’s not easy to summarise the discussion so far, but the comments have identified several existing formats for displaying (and marking up) mathematics on the web (mathML, jsMath, MathJax, OpenMath), as well as a surprisingly large number of tools for converting mathematics into web friendly formats (e.g.  LaTeX2HTML, LaTeXMathML, LaTeX2WP, Windows 7 Math Input, itex2MML, Ritex, Gellmu, mathTeX, WP-LaTeX, TeX4ht, blahtex, plastex, TtH, WebEQ, techexplorer, etc.).  Some of the formats are not widely supported by current software, and by current browsers in particular, but it seems that the situation will improve with the next generation of these browsers.

It seems that the tools that already exist are enough to improvise a passable way of displaying mathematics in various formats online, though there are still significant issues with accessibility, browser support, and ease of use.  Even if all these issues are resolved, though, I still feel that something is still missing.    Currently, if I want to transfer some mathematical content from one location to another (e.g. from a LaTeX file to a blog, or from a wiki to a PDF, or from email to an online document, or whatever), or to input some new piece of mathematics, I have to think about exactly what format I need for the task at hand, and what conversion tool may be needed.  In contrast, if one looks at non-mathematical content such as text, links, fonts, non-Latin alphabets, colours, tables, images, or even video, the formats here have been standardised, and one can manipulate this type of content in both online and offline formats more or less seamlessly (in principle, at least – there is still room for improvement), without the need for any particularly advanced technical expertise.  It doesn’t look like we’re anywhere near that level currently with regards to mathematical content, though presumably things will improve when a single mathematics presentation standard, such as mathML, becomes universally adopted and supported in browsers, in operating systems, and in other various pieces of auxiliary software.

Anyway, it has been a very interesting and educational discussion for me, and hopefully for others also; I look forward to any further thoughts that readers have on these topics.  (Also, feel free to recapitulate some of the points from the previous thread; the discussion has been far too multifaceted for me to attempt a coherent summary by myself.)