You are currently browsing the monthly archive for November 2009.

$\displaystyle i \hbar \partial_t |\psi \rangle = H |\psi\rangle$

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

$\displaystyle i \partial_t \phi = \Delta \phi + \lambda |\phi|^2 \phi. \ \ \ \ \ (1)$

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 ${N}$-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.

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, ${\omega}$-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):

[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.

In the course of the ongoing logic reading seminar at UCLA, I learned about the property of countable saturation. A model ${M}$ of a language ${L}$ is countably saturated if, every countable sequence ${P_1(x), P_2(x), \ldots}$ of formulae in ${L}$ (involving countably many constants in ${M}$) which is finitely satisfiable in ${M}$ (i.e. any finite collection ${P_1(x),\ldots,P_n(x)}$ in the sequence has a solution ${x}$ in ${M}$), is automatically satisfiable in ${M}$ (i.e. there is a solution ${x}$ to all ${P_n(x)}$ 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 ${{\Bbb N}}$ as a model for arithmetic. Then the sequence of formulae “${x > n}$” for ${n=1,2,3,\ldots}$ is finitely satisfiable in ${{\Bbb N}}$, but not satisfiable.

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

In particular, non-standard models of mathematics, such as the non-standard model ${*{\Bbb N}}$ of the natural numbers, are automatically countably saturated.

This has some cute consequences. For instance, suppose one has a non-standard metric space ${*X}$ (an ultralimit of standard metric spaces), and suppose one has a standard sequence ${(x_n)_{n \in {\mathbb N}}}$ of elements of ${*X}$ which are standard-Cauchy, in the sense that for any standard ${\varepsilon > 0}$ one has ${d( x_n, x_m ) < \varepsilon}$ for all sufficiently large ${n,m}$. Then there exists a non-standard element ${x \in *X}$ such that ${x_n}$ standard-converges to ${x}$ in the sense that for every standard ${\varepsilon > 0}$ one has ${d(x_n, x) < \varepsilon}$ for all sufficiently large ${n}$. Indeed, from the standard-Cauchy hypothesis, one can find a standard ${\varepsilon(n) > 0}$ for each standard ${n}$ that goes to zero (in the standard sense), such that the formulae “${d(x_n,x) < \varepsilon(n)}$” 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 ${*H}$ be a non-standard Hilbert space, let ${S}$ be a bounded (external) subset of ${*H}$, and let ${x \in H}$. Then there exists a decomposition ${x = x_S + x_{S^\perp}}$, where ${x_S \in *H}$ is “almost standard-generated by ${S}$” in the sense that for every standard ${\varepsilon > 0}$, there exists a standard finite linear combination of elements of ${S}$ which is within ${\varepsilon}$ of ${S}$, and ${x_{S^\perp} \in *H}$ is “standard-orthogonal to ${S}$” in the sense that ${\langle x_{S^\perp}, s\rangle = o(1)}$ for all ${s \in S}$.

Proof: Let ${d}$ be the infimum of all the (standard) distances from ${x}$ to a standard linear combination of elements of ${S}$, then for every standard ${n}$ one can find a standard linear combination ${x_n}$ of elements of ${S}$ which lie within ${d+1/n}$ of ${x}$. From the parallelogram law we see that ${x_n}$ is standard-Cauchy, and thus standard-converges to some limit ${x_S \in *H}$, which is then almost standard-generated by ${S}$ by construction. An application of Pythagoras then shows that ${x_{S^\perp} := x-x_S}$ is standard-orthogonal to every element of ${S}$. $\Box$

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 ${\sigma}$-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 ${*G}$ be a non-standardly finite abelian group, and let ${f: *G \rightarrow [0,1]}$ be a function. Then one can split ${f = f_{U^\perp} + f_U}$, where ${f_U: *G \rightarrow [-1,1]}$ is standard-uniform in the sense that all Fourier coefficients are (uniformly) ${o(1)}$, and ${f_{U^\perp}: *G \rightarrow [0,1]}$ is standard-almost periodic in the sense that for every standard ${\varepsilon > 0}$, one can approximate ${f_{U^\perp}}$ to error ${\varepsilon}$ in ${L^1(*G)}$ 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 ${X}$ of a non-standard finite set ${Y}$ dense if one has ${|X| \geq \varepsilon |Y|}$ for some standard ${\varepsilon > 0}$.

Theorem 3 Suppose Szemerédi’s theorem (every set of integers of positive upper density contains an arithmetic progression of length ${k}$) fails for some ${k}$. Then there exists an unbounded non-standard integer ${N}$, a dense subset ${A}$ of ${[N] := \{1,\ldots,N\}}$ with no progressions of length ${k}$, and with the additional property that

$\displaystyle \frac{|A \cap P|}{|P|} \leq \frac{|A \cap [N]|}{N} + o(1)$

for any subprogression ${P}$ of ${[N]}$ of unbounded size (thus there is no sizeable density increment on any large progression).

Proof: Let ${B \subset {\Bbb N}}$ be a (standard) set of positive upper density which contains no progression of length ${k}$. Let ${\delta := \limsup_{|P| \rightarrow \infty} |B \cap P|/|P|}$ be the asymptotic maximal density of ${B}$ inside a long progression, thus ${\delta > 0}$. For any ${n > 0}$, one can then find a standard integer ${N_n \geq n}$ and a standard subset ${A_n}$ of ${[N_n]}$ of density at least ${\delta-1/n}$ such that ${A_n}$ can be embedded (after a linear transformation) inside ${B}$, so in particular ${A_n}$ has no progressions of length ${k}$. Applying the saturation property, one can then find an unbounded ${N}$ and a set ${A}$ of ${[N]}$ of density at least ${\delta-1/n}$ for every standard ${n}$ (i.e. of density at least ${\delta-o(1)}$) with no progressions of length ${k}$. By construction, we also see that for any subprogression ${P}$ of ${[N]}$ of unbounded size, ${A}$ hs density at most ${\delta+1/n}$ for any standard ${n}$, thus has density at most ${\delta+o(1)}$, and the claim follows. $\Box$

This can be used as the starting point for any density-increment based proof of Szemerédi’s theorem for a fixed ${k}$, e.g. Roth’s proof for ${k=3}$, Gowers’ proof for arbitrary ${k}$, or Szemerédi’s proof for arbitrary ${k}$. (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.

Let ${X}$ be a finite subset of a non-commutative group ${G}$. As mentioned previously on this blog (as well as in the current logic reading seminar), there is some interest in classifying those ${X}$ which obey small doubling conditions such as ${|X \cdot X| = O(|X|)}$ or ${|X \cdot X^{-1}| = O(|X|)}$. 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 ${|X \cdot X|}$ is very close to ${|X|}$:

Proposition 1 If ${|X^{-1} \cdot X| < \frac{3}{2} |X|}$, then ${X \cdot X^{-1}}$ and ${X^{-1} \cdot X}$ are both finite groups, which are conjugate to each other. In particular, ${X}$ is contained in the right-coset (or left-coset) of a group of order less than ${\frac{3}{2} |X|}$.

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

Proof: We begin by showing that ${S := X \cdot X^{-1}}$ is a group. As ${S}$ is symmetric and contains the identity, it suffices to show that this set is closed under addition.

Let ${a, b \in S}$. Then we can write ${a=xy^{-1}}$ and ${b=zw^{-1}}$ for ${x,y,z,w \in X}$. If ${y}$ were equal to ${z}$, then ${ab = xw^{-1} \in X \cdot X^{-1}}$ and we would be done. Of course, there is no reason why ${y}$ should equal ${z}$; but we can use the hypothesis ${|X^{-1} \cdot X| < \frac{3}{2}|X|}$ to boost this as follows. Observe that ${x^{-1} \cdot X}$ and ${y^{-1} \cdot X}$ both have cardinality ${|X|}$ and lie inside ${X^{-1} \cdot X}$, which has cardinality strictly less than ${\frac{3}{2} |X|}$. By the inclusion-exclusion principle, this forces ${x^{-1} \cdot X \cap y^{-1} \cdot X}$ to have cardinality greater than ${\frac{1}{2}|X|}$. In other words, there exist more than ${\frac{1}{2}|X|}$ pairs ${x',y' \in X}$ such that ${x^{-1} x' = y^{-1} y'}$, which implies that ${a = x' (y')^{-1}}$. Thus there are more than ${\frac{1}{2}|X|}$ elements ${y' \in X}$ such that ${a = x' (y')^{-1}}$ for some ${x'\in X}$ (since ${x'}$ is uniquely determined by ${y'}$); similarly, there exists more than ${\frac{1}{2}|X|}$ elements ${z' \in X}$ such that ${b = z' (w')^{-1}}$ for some ${w' \in X}$. Again by inclusion-exclusion, we can thus find ${y'=z'}$ in ${X}$ for which one has simultaneous representations ${a = x' (y')^{-1}}$ and ${b = y' (z')^{-1}}$, and so ${ab = x'(z')^{-1} \in X \cdot X^{-1}}$, and the claim follows.

In the course of the above argument we showed that every element of the group ${S}$ has more than ${\frac{1}{2}|X|}$ representations of the form ${xy^{-1}}$ for ${x,y \in X}$. But there are only ${|X|^2}$ pairs ${(x,y)}$ available, and thus ${|S| < 2|X|}$.

Now let ${x}$ be any element of ${X}$. Since ${X \cdot x^{-1} \subset S}$, we have ${X \subset S \cdot x}$, and so ${X^{-1} \cdot X \subset x^{-1} \cdot S \cdot x}$. Conversely, every element of ${x^{-1} \cdot S \cdot x}$ has exactly ${|S|}$ representations of the form ${z^{-1} w}$ where ${z, w \in S \cdot x}$. Since ${X}$ occupies more than half of ${S \cdot x}$, we thus see from the inclusion-exclusion principle, there is thus at least one representation ${z^{-1} w}$ for which ${z, w}$ both lie in ${X}$. In other words, ${x^{-1} \cdot S \cdot x = X^{-1} \cdot X}$, and the claim follows. $\Box$

To relate this to the classical doubling constants ${|X \cdot X|/|X|}$, we first make an easy observation:

Lemma 2 If ${|X \cdot X| < 2|X|}$, then ${X \cdot X^{-1} = X^{-1} \cdot X}$.

Again, this is sharp; consider ${X}$ equal to ${\{x,y\}}$ where ${x,y}$ generate a free group.

Proof: Suppose that ${xy^{-1}}$ is an element of ${X \cdot X^{-1}}$ for some ${x,y \in X}$. Then the sets ${X \cdot x}$ and ${X \cdot y}$ have cardinality ${|X|}$ and lie in ${X \cdot X}$, so by the inclusion-exclusion principle, the two sets intersect. Thus there exist ${z,w \in X}$ such that ${zx=wy}$, thus ${xy^{-1}=z^{-1}w \in X^{-1} \cdot X}$. This shows that ${X \cdot X^{-1}}$ is contained in ${X^{-1} \cdot X}$. The converse inclusion is proven similarly. $\Box$

Proposition 3 If ${|X \cdot X| < \frac{3}{2} |X|}$, then ${S := X \cdot X^{-1}}$ is a finite group of order ${|X \cdot X|}$, and ${X \subset S \cdot x = x \cdot S}$ for some ${x}$ in the normaliser of ${S}$.

The factor ${\frac{3}{2}}$ 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 ${S = X^{-1} \cdot X = X \cdot X^{-1}}$ (the two sets being equal by Lemma 2). By the argument used to prove Lemma 2, every element of ${S}$ has more than ${\frac{1}{2}|X|}$ representations of the form ${xy^{-1}}$ for ${x,y \in X}$. By the argument used to prove Proposition 1, this shows that ${S}$ is a group; also, since there are only ${|X|^2}$ pairs ${(x,y)}$, we also see that ${|S| < 2|X|}$.

Pick any ${x \in X}$; then ${x^{-1} \cdot X, X \cdot x^{-1} \subset S}$, and so ${X \subset x\cdot S, S \cdot x}$. Because every element of ${x \cdot S \cdot x}$ has ${|S|}$ representations of the form ${yz}$ with ${y \in x \cdot S}$, ${z \in S \cdot x}$, and ${X}$ occupies more than half of ${x \cdot S}$ and of ${S \cdot x}$, we conclude that each element of ${x \cdot S \cdot x}$ lies in ${X \cdot X}$, and so ${X \cdot X = x \cdot S \cdot x}$ and ${|S| = |X \cdot X|}$.

The intersection of the groups ${S}$ and ${x \cdot S \cdot x^{-1}}$ contains ${X \cdot x^{-1}}$, which is more than half the size of ${S}$, and so we must have ${S = x \cdot S \cdot x^{-1}}$, i.e. ${x}$ normalises ${S}$, and the proposition follows. $\Box$

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

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:

A fundamental tool in any mathematician’s toolkit is that of reductio ad absurdum: showing that a statement ${X}$ is false by assuming first that ${X}$ 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 ${X}$, by showing that ${X}$‘s powers are “self-defeating”: the very existence of ${X}$ 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 ${N}$ which is larger than all other natural numbers.

Proof: Suppose for contradiction that there was such a largest natural number ${N}$. Then ${N+1}$ is also a natural number which is strictly larger than ${N}$, contradicting the hypothesis that ${N}$ is the largest natural number. $\Box$

Note the argument does not apply to the extended natural number system in which one adjoins an additional object ${\infty}$ beyond the natural numbers, because ${\infty+1}$ is defined equal to ${\infty}$. 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 ${N}$, but no matter how much effort is expended in doing so, the player is defeated by the simple response “… plus one!” (unless, of course, ${N}$ 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 ${{\Bbb N} = \{0,1,2,3,\ldots\}}$ cannot be written as ${\{ a_1,\ldots,a_n\}}$ for any finite collection ${a_1,\ldots,a_n}$ of natural numbers.

Proof: Suppose for contradiction that such an enumeration ${{\Bbb N} = \{a_1,\ldots,a_n\}}$ existed. Then consider the number ${a_1+\ldots+a_n+1}$; this is a natural number, but is larger than (and hence not equal to) any of the natural numbers ${a_1,\ldots,a_n}$, contradicting the hypothesis that ${{\Bbb N}}$ is enumerated by ${a_1,\ldots,a_n}$. $\Box$

Here it is the enumeration which is self-defeating, rather than any individual natural number such as ${a_1}$ or ${a_n}$. (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 ${{\mathcal P} = \{2,3,5,7,\ldots\}}$ cannot be written as ${\{p_1,\ldots,p_n\}}$ for any finite collection of prime numbers.

Proof: Suppose for contradiction that such an enumeration ${{\mathcal P} = \{p_1,\ldots,p_n\}}$ existed. Then consider the natural number ${p_1 \times \ldots \times p_n + 1}$; this is a natural number larger than ${1}$ which is not divisible by any of the primes ${p_1,\ldots,p_n}$. 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 ${1}$ must be divisible by some prime, contradicting the hypothesis that ${{\mathcal P}}$ is enumerated by ${p_1,\ldots,p_n}$. $\Box$

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 ${1+it}$ implies that the primes anti-correlate almost completely with the multiplicative function ${n^{it}}$, which is self-defeating because it also implies complete anti-correlation with ${n^{-it}}$, 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.)

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 (mathMLjsMath, MathJaxOpenMath), as well as a surprisingly large number of tools for converting mathematics into web friendly formats (e.g.  LaTeX2HTMLLaTeXMathML, LaTeX2WPWindows 7 Math Inputitex2MMLRitexGellmumathTeXWP-LaTeXTeX4htblahtexplastexTtHWebEQtechexplorer, 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.)