subfactors - Pimsner-Popa Bases

Let $Nsubset M$ be a finite index $II_1$-subfactor. Let $B={b_i}$ be a finite orthonormal (Pimsner-Popa) basis for $M$ over $N$. Let $d=[Mcolon N]^{1/2}$. It is well known that $B_1={d b_{i_1} e_1 b_{i_2}}$ is a (not necessarily orthonormal) basis for $M_1$ over $N$, where $M_1=langle M, e_1rangle$ is the basic construction of $Nsubset M$ (for example, see Bisch, Bimodules and higher relative commutants, page 31). Under what conditions are we assured $B_1$ is orthonormal? orthogonal?

Integer index always works (see the Pimsner-Popa paper), and a variation always works in infinite index (with a definition of orthonormal basis due to Burns).

at.algebraic topology - Torsion in homology or fundamental group of subsets of Euclidean 3-space

I don't think that

torsion in the homology has been ruled out

Certainly, torsion in Cech cohomology has been ruled out for a compact subset. The "usual" universal coefficient formula, relating Cech cohomology to $operatorname{Hom}$ and $operatorname{Ext}$ of Steenrod homology, is not valid for arbitrary compact subsets of $Bbb R^3$ (although it is valid for ANRs, possibly non-compact). The "reversed" universal coefficient formula, relating Steenrod homology to $operatorname{Hom}$ and $operatorname{Ext}$ of Cech cohomology is valid for compact metric spaces, but it does not help, because $operatorname{Ext}(Bbb Z[frac1p],Bbb Z)simeqBbb Z_p/Bbb ZsupsetBbb Z_{(p)}/Bbb Z$, which contains $q$-torsion for all primes $qne p$. (Here $Bbb Z_{(p)}$ denotes the localization at the prime $p$, and $Bbb Z_p$ denotes the $p$-adic integers.
The two UCFs can be found in Bredon's Sheaf Theory, 2nd edition, equation (9) on p.292
in Section V.3 and Theorem V.12.8.)

The remark on $operatorname{Ext}$ can be made into an actual example. The $p$-adic solenoid $Sigma$ is a subset of $Bbb R^3$. The zeroth Steenrod homology $H_0(Sigma)$ is isomorphic by the Alexander duality to $H^2(Bbb R^3setminusSigma)$. This is a cohomology group of an open $3$-manifold contained in $Bbb R^3$, yet it is isomorphic to $Bbb Zoplus(Bbb Z_p/Bbb Z)$ (using the UCF, or the Milnor short exact sequence with $lim^1$), which contains torsion. Of course, every cocycle representing torsion is "vanishing", i.e. its restriction to each compact submanifold is null-cohomologous within that submanifold.

By similar arguments, $H_i(X)$ (Steenrod homology) contains no torsion for $i>0$ for every compact subset $X$ of $Bbb R^3$.

It is obvious that "Cech homology" contains no torsion (even for a noncompact subset $X$ of $Bbb R^3$), because it is the inverse limit of the homology groups of polyhedral neighborhoods of $X$ in $Bbb R^3$. But I don't think this is to be taken seriously, because "Cech homology" is not a homology theory (it does not satisfy the exact sequence of pair). The homology theory corresponding to Cech cohomology is Steenrod homology (which consists of "Cech homology" plus a $lim^1$-correction term). Some references for Steenrod homology are Steenrod's original paper in Ann. Math. (1940), Milnor's 1961 preprint (published in http://www.maths.ed.ac.uk/~aar/books/novikov1.pdf), Massey's book Homology and Cohomology Theory. An Approach Based on Alexander-Spanier Cochains, Bredon's book Sheaf Theory (as long as the sheaf is constant and has finitely generated stalks) and this paper http://front.math.ucdavis.edu/math/0812.1407

As for torsion in singular $4$-homology of the Barratt-Milnor example, this is really a question about framed surface links in $S^4$ (see the proof of theorem 1.1 in the linked paper).

at.algebraic topology - Difference between represented and singular cohomology?

This is a good question because it really hits on a subtle issue. It turns out that Johannes and Ben are both correct and incorrect at the same time unless we settle some very subtle issues. Let me explain.

There are really two things at issue here. The first is what is meant by the notation [X,Y] when X is not a CW-complex. Is it homotopy classes of maps? Or is it weak homotopy classes of maps? The other thing at issue is what is meant by a cohomology theory? Is it a functor which sends just homotopy equivalences to isomorphisms? or is it also required to send weak homotopy equivalences to isomorphisms?

These decisions determine who is right or wrong. Let X be the cantor set as in Ben's answer. As Ben rightfully points out the homotopy class of maps from X into the discrete space $mathbb{Z}$ must factor through a finite quotient, while the singular cohomology is much larger. So Ben is interpreting [X, Y] to mean homotopy classes of maps. Weak homotopy classes of maps are more subtle. They are the morphisms in the derived category of spaces and are defined by taking equivalence classes of spans:

$$ X stackrel{sim}{leftarrow} X' rightarrow Y $$

where $X'$ ranges over spaces weakly homotopy equivalent to X. Equivalently you can replace X with any cofibrant replacement, like a CW-approximation. In the case of X= the Cantor set, the CW-replacement is a disjoint union of uncountably many points, and so the weak homotopy equivalence classes of maps does in fact agree with singular cohomology.

More generally if [X,Y] denotes weak homotopy classes of maps, then Johannes' statement is correct. The functor $[-, K(mathbb{Z}, n)]$ always agrees with singular cohomology.

This brings us to the issue of what exactly a cohomology theory is supposed to be? If you ask an algebraic topologist they will usually tell you that a cohomology theory is defined so that it sends weak equivalences to isomorphisms (The Axiom of Weak Equivalence). If this is our definition, and [X,Y] denotes homotopy classes of maps and not weak homotopy classes of maps, then $[-, K(mathbb{Z}, n)]$ fails to be a cohomology theory. But it is in good company Cech cohomology and sheaf cohomology also fail this litmus test, so many people outside of algebraic topology feel uncomfortable with this axiom.

However it is necessary for the uniqueness result of the Eilenberg-Steenrod axioms. The Axiom of Weak Equivalence implies that the cohomology theory is determined by its value on CW-complexes, and the rest of the axioms lock this down. Without the Axiom of Weak Equivalence there is very little control on what the theory assigns to spaces which do not have the homotopy type of CW-complexes.

tag removed - Estimating the flow when we know the vector field

Let $X=sum_{1le jle n}a_j(x)partial_{x_j}$ be a Lipschitz-continuous vector field on some open subset of $mathbb R^n$. The flow is then Lipschitz-continuous: it is a consequence of Gronwall's inequality. In fact, with
$$
dot Phi(t,y)=X(Phi(t,y)),quad Phi(0,y)=y,
$$
we have
$
Phi(t,y_1)-Phi(t,y_2)=y_1-y_2+int_0^tBigl(X(Phi(s,y_1))-X(Phi(s,y_2))Bigr) ds
$
and consequently for $tge 0$
$$
vert Phi(t,y_1)-Phi(t,y_2)vertle vert y_1-y_2 vert+
int_0^t Lvert Phi(s,y_1))-Phi(s,y_2)vert ds=R(t).
$$
As a result, we get
$
dot R(t)le L R(t),quad R(0)=vert y_1-y_2 vert
$
so that
$$vert Phi(t,y_1)-Phi(t,y_2)vertle
R(t)le vert y_1-y_2 vert e^{tL}.
$$
When the vector field is $C^1$, the flow is also $C^1$ with respect to $x$, but the proof is not so simple (the previous argument is somehow a first step). The Birkhoff-Rota book on ODE provides a nice proof.

Bazin.

set theory - How to think like a set (or a model) theorist.

Kenneth Kunen in his “The Foundations of Mathematics” writes:

1. ‘Set theory is the study of models of ZFC’ (p. 7)


2. ‘Set theory is the theory of everything’ (p. 14)

With (1) Kunen is pointing to a change in the intended use of the axioms of ZFC: ‘there are two different uses of the word “axioms”: as “statements of faith” and as “definitional axioms”.’ (p. 6).

With (2) he means ‘set theory is all-important. That is

• All abstract mathematical concepts are set-theoretic.


• All concrete mathematical objects are specific sets.’ (p. 14)

According to (1), to be a set is to be any of the individuals of the universe of a particular model of ZFC, just like being a numeral (standard or not) is being any of the individuals of the universe of a particular model of PA (here I am using Shoenfield’s terminology in “Mathematical Logic”, p. 18).

But, according to (2), models are sets too, as any other objects dealt with in the metatheory.

What's more, models of set theory are defined in terms of relative interpretations of set theory into itself, a syntactical concept. (See Kunen’s “Set Theory. An Introduction to Independence Proofs”, p. 141), which makes the whole thing a bit more confusing.

The view of the axioms of set theory as "definitional axioms" is appealing. And more in regard of (2) since then they pretend to define all that there is. The study of models of set theory has an intrinsic interest, but why reduce the study of set theory to it? Or stated another way, why abandoning the old view?

I would like to know if set theorists do stick to one view or another or shift comfortably between both at need, and the reasons they have to do so.

It is well-known that hyperbolic space is delta-hyperbolic, but what is delta?

Let $T$ be a triangle in $mathbb{H}^2$. Its area is $pi - alpha - beta - gamma$, where $alpha$, $beta$, and $gamma$ are the interior angles. You can find how slim this triangle is by considering an inscribed circle in $T$. The radius of this triangle, thus $delta$, are bounded above by the area, so to find the $delta$ that works for all triangles, you take the limit and consider an ideal triangle $T_infty$. You can explicitly compute that the inscribed circle minimizing distance between the sides has length $4 log phi$, where $phi$ is the golden ratio. (See here and here.)

ag.algebraic geometry - Vector bundles on $mathbb{P}^1timesmathbb{P}^1$

It may be a bit unfair to compare $X=mathbb P^1 times mathbb P^1$ to $mathbb P^1$. EDIT: I removed a too optimistic statement about restricting vector bundles on $mathbb P^3$ to a smooth hypersurface, which works for $mathbb P^4$ but not always for $mathbb P^3$.

On the other hand, if we compare $X$ with the smooth surface $mathbb P^2$, then there is this famous result by Horrocks, which says that a vector bundle $E$ on $mathbb P^2$ splits if

$$oplus_{iin mathbb Z} H^1(mathbb P^2,E(i)) =0 $$

Interestingly, over $X$, the same result works. In other words, $E$ on $X$ splits if:
$$oplus_{iin mathbb Z} H^1(X,E(i)) =0 $$

the reason is such $E$ corresponds to a (graded) maximal Cohen-Macaulay (MCM) module over the cone of $X$, namely the hypersurface $R=k[x,y,u,v]/(xu-yv)$. But $R$ has finite MCM type and all the indecomposables have rank one (but note that they will not always be twists of the trivial line bundle). A lot more details and references are available in this paper by Buchweitz, Greuel and Schreyer.

Reference needed for: every idempotent in a C*-algebra is similar to a hermitian one

The result stated in the title is thoroughly standard - or that's the impression I got.
I seem to remember seeing it stated somewhere in a book I was reading in the library, and then reverse-engineering a proof from the hints given.

For a preprint I'm working on, it would be preferable to give a precise citation from a "standard text", rather than spend time giving the proof "for the reader's convenience". Any suggestions?

---

If anyone's interested, an outline of a proof is as follows: consider an idempotent P in B(H), with H a Hilbert space, and note that we can always decompose H as an orthogonal sum with respect to which P has the block matrix form

$$ P= left(begin{matrix} I & R \\ 0 & 0 end{matrix}right) $$

Then it's not hard to see that conjugating $P$ by the invertible operator

$$ S= left( begin{matrix} I & R \\ 0 & I end{matrix} right) $$

will give

$$ E = left(begin{matrix} I & 0 \\ 0 & 0 end{matrix} right) $$

Since $S= I+P-E$, it suffices to show that $E$ is in the C*-algebra generated by I and P (for then S will also lie in that algebra, and then we're done). This follows by messing around with various combinations of P, its adjoint, and their products.

latex - Beamer printout

documentclass[handout]{beamer}

achieves what you want. I also write

mode<handout>{
  usetheme{default}
  setbeamercolor{background canvas}{bg=black!5}
  pgfpagesuselayout{4 on 1}[letterpaper,landscape,border shrink=2.5mm]
}

which in particular gives you 4 slides per page, and some nicer formatting (shaded backgrounds, for example).

You can also use

documentclass[trans]{beamer}

which disables all the uncovering, but otherwise leaves things very much like in usual beamer mode.

set theory - Tractability of forcing-invariant statements under large cardinals

Typically, generic absoluteness is a consequence of a stronger property, that in many cases is really the goal one is after. To explain this stronger property, let me begin by reviewing two important absoluteness results.

1) The first is Mostowski's Absoluteness. Suppose $phi$ is $Sigma^1_1(a)$, where $ainomega^omega$. This means that $phi(x)$ for $xinomega^omega$, asserts

$∃yinomega^omegaforall nin omega R(xupharpoonright n, yupharpoonright n,aupharpoonright n)$,

where $R$ is a predicate recursive in $a$. These statements are very absolute: Suppose that $M$ is a well-founded model of a decent fragment of ZF, and that $a,xin M$. Then $phi(x)$ holds iff $Mmodels phi(x)$.

In particular, whether or not $phi(x)$ holds cannot be changed by forcing, or by passing to an inner or outer model. Note that $M$ could be countable. In fact, only needs to be an $omega$-model; well-foundedness is not necessary.

This is how the result is usually stated. What is going on is the following:

Suppose that $T$ is a tree (in the descriptive set theoretic sense) and that $Tin M$. Then $T$ is ill-founded iff $Mmodels T$ is ill-founded.

In particular, $T$ could be the tree associated to $phi$. This is the tree of all $(s,t)$ such that $s,t$ are finite sequences of the same length $l$, and $forall nle l$ $ R(supharpoonright l,tupharpoonright n,aupharpoonright n)$. So $T$ is the tree of attempts to verify $phi$: $phi(x)$ holds iff (there is a $y$ such that for all $n$, $(xupharpoonright n,yupharpoonright n)in T$) iff the tree $T_x$ is ill-founded. Recall that $T_x$ consists of all $t$ such that, if $l$ is the length of $t$, then $(xupharpoonright n,tupharpoonright n)in T$ for all $nle l$.

The point is that $T$ is a very simple object. As soon as $T,x$ are present, $T_x$ can be built, and the result of the construction of $T_x$ is the same whether it is performed in $V$ or in $M$. Since well-foundedness is absolute, whether or not $T_x$ is ill-founded is the same whether we check this in $M$ or in $V$. Of course, $T_x$ is ill-founded iff $phi(x)$ holds.

The moral is that the truth of $Sigma^1_1$ statements is certified by trees. And I think that this is saying that in a strong sense, $Sigma^1_1$ statements are very tractable. All we need to check their validity is a very easy to build tree and, once we have it, the tree is our certificate of truth or falsehood, this cannot be altered.

Recall that proofs in first-order logic can be described by means of certain finite trees. If something is provable, the tree is a very robust certificate. This is a natural weakening of that idea.

Of course one could argue that, if a $Sigma^1_1$ statement is not provable, then in fact it may be very hard to establish its truth value, so tractability is not clear. Sure. But, independently of whether or not one can prove something or other, the certificate establishing this truth value is present from the beginning. One does not need to worry that this truth value may change by changing the model one is investigating.

2) The second, and best known, absoluteness result, is Shoenfield's absoluteness. Suppose $phi$ is $Sigma^1_2(a)$. This means that $phi(x)$ holds iff

$exists yforall zexists n$ $R(yupharpoonright n,zupharpoonright n,xupharpoonright n,aupharpoonright n)$,

where $R$ is recursive in $a$. Let $M$ be any transitive model of a decent fragment of ZFC, and suppose that $omega_1subset M$ and $a,xin M$. Then $phi(x)$ holds iff $Mmodelsphi(x)$.

This is again a very strong absoluteness statement. Again, if one manages to show the consistency of $phi(x)$ by, for example, passing to an inner model or a forcing extension, then in fact one has proved its truth.

Again, one could say that if $phi$ is not provable, then it is in fact not very tractable at all. But the point is that to investigate $phi$, one can use any tools whatsoever. One only needs to worry about its consistency, for example, and one can make use of any combinatorial statements that one could add to the universe by forcing.

Just as in the previous case, $Sigma^1_2$ statements can be certified by trees. The tree associated to $phi$ is more complicated than in the previous case, and it is now a tree of $omegatimesomega_1$. (Jech's and Kanamori's books explain carefully its construction.) Again, the tree is very absolute: As soon as we have $a$ and all the countable ordinals at our disposal, the tree can be constructed. (One comparing two models $Msubset V$, we mean all the countable ordinals of $V$, even if $M$'s version of $omega_1$ is smaller.)

3) Generic absoluteness of a statement $phi$ is typically a consequence of the existence of absolutely complemented trees associated to $phi$. In fact, all generic absoluteness results I'm aware of are established by proving that there are such trees ("conditional" generic absoluteness results, such as only for proper forcings, or only in the presence of additional axioms, are somewhat different). This is a direct generalization of the situations above.

To define the key concept, recall that if $A$ is a tree of $omegatimes X$, then the projection $p[A]$ of $A$ is the set of all $xinomega^omega$ such that $exists fin X^omegaforall ninomega,(xupharpoonright n,fupharpoonright n)in A$.

Two (proper class) trees $A$ and $B$ on $omegatimes ORD$ are absolutely complemented iff:

1. $p[A]cap p[B]=emptyset$ and $p[A]cup p[B]=omega^omega$.


2. Item 1 holds in all generic extensions.

A statement $phi$ admits such a pair iff, in addition,

1. In any forcing extension, $phi(x)$ iff $xin p[A]$.

The idea is that this is a precise, formal, definable approximation to the intuitive statement one would actually like, namely, that there are such trees describing $phi$ that have this ``complementary'' behavior in all outer models. First-order logic limits ourselves to considering forcing extensions.

Let me point out that $Sigma^1_1$ and $Sigma^1_2$ statements admit absolutely complemented pairs, so the existence of such a pair is a natural (far reaching) generalization of the two cases above.

Once we accept large cardinals, we can show that much larger classes than $Sigma^1_2$ admit absolutely complemented trees. For example, any projective statement does. Once again, the point is that as soon as we have the large cardinals and real parameters in our universe, we have the trees, and the trees certify in unambiguous forcing-unchangeable terms, whether the statements hold at any given real. It is in this sense that we consider these statements more tractable.

Here is a rough sketch of an example I particularly like, due to Martin-Solovay (for measurables) and Woodin (in its optimal form). For details, see my paper with Ralf Schindler, ``projective well-orderings of the reals,'' Arch. Math. Logic (2006) 45:783–793:

$V$ is closed under sharps iff $V$ is $Sigma^1_3$-absolute. $(*)$

The right hand side means that for any $Sigma^1_3$ statement $phi$ (so now we have three alternations of quantifiers) and any two step forcing ${mathbb P}∗dot{mathbb Q}$, for any $G$, ${mathbb P}$-generic over $V$, any $H$, ${mathbb Q}$-generic over $V[G]$, and for any real $x$ in $V[G]$, we have
$$ V[G]modelsphi(x)Longleftrightarrow V[G][H]modelsphi(x). $$

The left hand side of $(*)$ is a weakening of "there is a proper class of measurable cardinals", which is how the statement is usually presented.

The proof of the implication from left to right in $(*)$ goes by building a tree of attempts to find a witness to the negation of a $Sigma^1_2$ statement. The goal is that if such a witness can be added by forcing, then in fact we can find one in the ground model. If there is a forcing adding a witness, there is a countable transitive model where this is the case. Essentially, the tree gives the construction of such a model, bit by bit, and if we have a branch, then we have such a model.

So: If there is a witness added in a forcing extension, the tree will have there a branch. So it is illfounded. By absoluteness of well-foundedness, the tree has a branch in $V$. The sharps are used to ``stretch'' the model so that we can use Shoenfield absoluteness, and conclude that there must be a witness in $V$.

4) Projective absoluteness, a consequence of large cardinals, is established by showing the existence of absolutely complemented trees for any projective statement. The theory of universally Baire sets originates with this concept, and the closely related notion of homogeneously Suslin trees. All of this is also connected to determinacy. Once again, to drive the point home: Generic absoluteness is not the goal. The goal is the existence of the pair of trees. Once we have them, we have a strong certificate of truth or falsehood of a statement. I do not know if one is to accept the search for such trees as a more tractable problem than the original statement whose pair of trees we are now searching for. But it certainly says that consistency of the statement, using large cardinals or any combinatorial tools whatsoever, is enough to have a proof of the statement. This seems much more hopeful and generous an approach than if only proofs in the usual sense are allowed. The existence of these trees for projective statements is what I meant in a comment by ``large cardinals settle second order arithmetic.'' Put yet another way: If you show, for example, that a projective statement is not 'decidable' (in the presence of large cardinals), meaning that it is consistent and so is its negation, then you have either actually showed that certain large cardinals are inconsistent, or you have found a way of changing the truth of arithmetic statements, and both of these options are much more significant events than the proof of whatever the projective statement you were interested in was. More likely than not, the truth value of the statement will be uncovered at some point, and you know there is no ambiguity as of what it would be, since the witnessing trees are already present in the universe.

(In spite of its length, I am not completely happy with this answer, but I would need to get much more technical to expand on the many interesting points that your question raises. Hopefully there is some food for thought here. For nice references to some of the issues I mention here, Woodin's article in the Notices is a good place to start, and Steel's paper on the derived model theorem has much of the details.)

mp.mathematical physics - A reading list for topological quantum field theory?

I think it might be worth pointing out that there are two kinds of topological quantum field theory, (Albert) Schwarz-type theories and Witten-type theories. In Schwarz type theories (like Chern-Simons theory and BF-theory), you have an action which is explicitly independent of the metric and you expect that the correlation functions computed by the path integral will also be independent of the metric. In Witten-type theories (Donaldson theory, Gromov-Witten theory), metric independence is a little bit more subtle. In these theories, you do have to choose a metric to get started. But you have some extra structure that allows you to compute some quantities which are metric independent.

(Slightly) more precisely: In a Witten-type theory, you have some operator Q which squares to zero, which you think of as a differential. (Witten type theories are also called cohomological field theories.) You also have an operator T, taking values in (2,0)-tensors, which a) is Q-exact ( T = [Q,G] for some G), and b) generates changes in the metric g. The latter means that if we compute the expectation value < epsilon(T)A > as a function of g, we find that it's equal to the expectation value of A computed with respect to g + epsilon. Here epsilon is a "small" (0,2) tensor we pair with T to get a scalar. In these theories, you can show that the correlation functions of operators which are Q-exact must vanish, which implies that small deformations of g don't change the correlation functions of Q-closed operators A. If you choose A so that its expectation value behaves like a function on the space of metrics, this tells you it's constant on the space of metrics. If you choose some fancier A so that the correlation functions behave like differential forms on the space of metrics, cohomological complications can arise.

Most of the references here are for Schwarz-type theories. For a physics treatment of Witten-type theories, it's worth looking at Witten's "Introduction to cohomological field theory". There's also a long set of lecture notes by Cordes, Moore, & Ramgoolam. The mathematical treatments of the idea are less complete. Hopkins, Lurie, & Costello's stuff is about the most comprehensive, but it's pretty far removed from actions and path integrals. For a starter, you might enjoy Teleman's classification of 2d semi-simple "families topological field theories".

at.algebraic topology - Thom's seminal cobordism paper in English?

An English translation of this paper is included in the first volume of the "Topological Library", edited by Novikov and Taimanov. See the following website : http://www.worldscibooks.com/mathematics/6379.html

By the way, Thom's paper is rather hard to read. There are alternative expositions (often with somewhat easier proofs) of various pieces of it in various places. What portion in particular is giving you trouble?

na.numerical analysis - Why does randomness work in numerical algorithms?

If one had infinite computing capacity, then you would be right that randomness would not be useful (unless an adversary also had access to randomness - see below), and it would always be better to maintain full control of one's parameters. ("God does not need to play dice".) However, our computing capacity is limited, and randomness offers a way to stretch that capacity further (though it is an important open problem to quantify exactly how much randomness actually stretches our capacity; see the discussion on P=BPP in other comments).

Let's give a simple example. Suppose one is playing the following game with a computer. This computer uses some (deterministic) algorithm to generate 1000 "bad" numbers from 1 to 1 million. Meanwhile, you pick your own number from 1 to 1 million. If you pick one of the bad numbers, you lose; otherwise, you win. You get to see the computer's algorithm in advance.

With infinite computing capacity, you have a strategy which is 100% guaranteed to succeed: you run the computer's algorithm, find all the bad numbers, and pick a number not chosen by the computer.

But there is a much lazier strategy that requires no computing power: just pick a number randomly, and one has a 99.9% chance of winning.

[Note also that if the computer used a randomised algorithm instead of a deterministic one, then there is no longer any 100% winning strategy for you, even with infinite computing power, though the random strategy works just fine. This is another indication of the power of randomness.]

Many randomised algorithms work, roughly speaking, by reducing the given problem to some version of the above game. For instance, Monte Carlo integration using a set of points to sample the function might give satisfactory levels of accuracy for all but a tiny fraction of the possible choices of sample points. With infinite computing capacity, one could locate all the bad configurations of sample points and then find a configuration which is guaranteed to give a good level of accuracy, but this is a lot of work - more work, in fact, than just doing classical numerical integration. Instead, one takes the lazy way out and picks the sample points randomly. (Well, in practice, one picks the points pseudorandomly instead of randomly, because true randomness is very hard to capture by a computer; this is a subtle issue - again related to P=BPP - that I don't want to get into here.)

examples - Experimental Mathematics

A new look

Now as the question is five years old and there are certainly more examples of mathematical advances via computer experimentation of various kinds, I propose to consider contributing new answers to the question.

Motivation

I am aware about a few such cases and I think it will be useful to gather such examples together. I am partially motivated by the recent polymath5 which, at this stage, have become an interesting experimental mathematics project. So I am especially interested in examples of successful "mathematical data mining"; and cases which are close in spirit to the experimental nature of polymath5. My experience is that it can be, at times, very difficult to draw useful insights from computer data.

Summary of answers according to categories

(Added Oct. 12, 2015)

To make the question a useful resource (and to allow additional answers), here is a quick summery of the answers according to categories. (Links are to the answers, and occasionally to an external link from the answer itself.)

1) Mathematical conjectures or large body of work arrived at by examining experimental data - Classic

The Prime Number Theorem; Birch and Swinnerton-Dyer conjectures; Shimura-Taniyama-Weil conjecture; Zagier's conjectures on polylogarithms; Mandelbrot set; Gosper Glider Gun (answer), Lorenz attractor; Chebychev's bias (asnwer) ; the Riemann hypothesis; the discovery of the Feigenbaum constant; (related) Feigenbaum-Coullet-Tresser universality and Milnor's Hairiness conjecture (NEW); Solving numerically the so-called Fermi--Pasta--Ulam chain and then of its continuous limit, the Korteweg--de Vries equation

2) Mathematical conjectures or large body of work arrived at by examining experimental data - Current

"Maeda conjecture"; the work of Candès and Tao on compressed sensing; Certain Hankel determinants; Weari-Phelan structure; the connection of multiple zeta values to renormalized Feynman integrals; Thistlethwaite's discovery of links with trivial Jones polynomial; The Monstrous Moonshine; (NEW:) McKay's account on experimentation leading to mysterious "numerology" regarding the monster. (link to the answer); Haiman conjectures on the quotient ring by diagonal invariants

3) Computer-assisted proofs of mathematical theorems

Kepler's conjecture ; a new way to tile the plane with a pentagon: advances regarding bounded gaps between primes following Zhang's proof; Cartwright and Steger's work on fake projective planes; the Seifert-Weber dodecahedral space is not Haken; the four color theorem, the proof of the nonexistence of a projective plane of order 10; Knuth's work on a class of projective planes; The search for Mersenne primes; Rich Schwartz's work; The computations done by the 'Atlas of Lie groups' software of Adams, Vogan, du Cloux and many other; Cohn-Kumar proof for the densest lattice pacing in 24-dim; Kelvin's conjecture;

4) Computer programs that interactively or automatically lead to mathematical conjectures.

Graffiti

5) Various computer programs which allow proving automatically theorems or generating automatically proofs in a specialized field.

Wilf-Zeilberger formalism and software; FLAGTOOLS

6) Computer programs (both general purpose and special purpose) for verification of mathematical proofs.

The verification of a proof of Kepler's conjecture.

7) Large databases and other tools

Sloane's online encyclopedia for integers sequences; the inverse symbolic calculator.

8) Resources:

Journal of experimental mathematics; Herb Wilf's article: Mathematics, an experimental science in the Princeton Companion to Mathematics, genetic programming applications a fairly comprehensive website experimentalmath.info
; discovery and experimentation in number theory; Doron Zeilberger's classes called "experimental mathematics":math.rutgers.edu/~zeilberg/teaching.html;
V.I. Arnol'd's two books on the subject of experimental mathematics in Russian, Experimental mathematics, Fazis, Moscow, 2005, and Experimental observation of mathematical facts, MCCME, Moscow, 2006

Answers with general look on experimental mathematics:

Computer experiments allow new avenues for productive strengthening of a problem (A category of experimental mathematics).

---

Bounty:

There were many excellent answers so let's give the bounty to Gauss...

Related question: Where have you used computer programming in your career as an (applied/pure) mathematician?, What could be some potentially useful mathematical databases?; Results that are easy to prove with a computer, but hard to prove by hand ; What advantage humans have over computers in mathematics?

fa.functional analysis - Is the Fourier-Transform a bounded operator on Lorentz spaces L(2,q)?

It is well known that the Fourier transform $mathcal{F}$ maps $L^1(mathbb{R}^n)$ continuously into $L^infty(mathbb{R}^n)$ and $L^2(mathbb{R}^n)$ continuously into $L^2(mathbb{R}^n)$.

Then, by interpolation theorems such as Marcinkiewicz' Theorem one can deduce that $mathcal{F}$ maps as well the Lorentz spaces $L^{p,q}(mathbb{R}^n)$ into $L^{p',q}(mathbb{R}^n)$ if $1 < p < 2$, $1 leq q leq infty$. (Here, $p' = frac{p}{p-1}$ is the Hölder-conjugate of $p$).

On the other hand, for $p > 2$ it can be shown that the Fourier Transform $mathcal{F}$ is defined on $L^p(mathbb{R}^n)$ only in the sense of distributions, and does not map $L^p$ into $L^{p'}$, and in particular it does not map Lorentz spaces $L^{p,q}$ continuously into $L^{p',q}$ for $p > 2$, $1 leq q leq infty$.

So my question is, what happens in the in-between spaces $L^{2,q}$? Is still an isomorphism as in the case $L^{2,2} = L^2$?

math philosophy - Is no proof based on "tertium non datur" sufficient any more after Gödel?

I accidentally ran into this old question and thought to give an example whose (humble!) intention is to permanently deconfuse anyone who knows just a little bit of undergraduate mathematics.

Consider group theory. In a typical introductory course, you will learn the simple axioms and immediately encounter sentences like

$$forall y forall x forall z( (xy=e) wedge (zy=e ) Rightarrow x=z);$$

or slightly more complicated ones like

$$(forall x(x^2=e ))Rightarrow (forall xforall y(xy=yx)).$$

You also learn how to deduce them rather easily from the axioms of the theory.

How about the sentence

$$S: forall x forall y( xy=yx)$$

?

Can it be deduced from the axioms? Obviously not, but it requires at least a bit of thoughtfulness to
prove that it can't. You see, we can just write down a structure like $S_3$ that satisfies the axioms of group theory,
a model of group theory, and produce two elements in it for which the sentence is not true. Obviously we couldn't produce
such a model if the sentence was a logical consequence of the axioms.

How then about $neg S$? Can it be deduced from the axioms? Again obviously not. Consider the integers $Z$.

So we see that group theory is incomplete: We've written down a sentence $S$ such that neither $S$ nor $neg S$ can be
deduced from the axioms.

But here is an important point: If the context of the discussion was the group $Z$, is the sentence $S$ true? Yes, of course, and I can prove it for you. (Using more than the axioms of group theory, of course.)

For a complete theory, every true assertion $S$ (in the language of the theory) about a given model $G$ can be deduced from the axioms. This is because $S$ or $neg S$ can be deduced,
but if $neg S$ could be deduced, then it would have to be true in any model of the theory, in particular, $G$. So $S$ would be
false in $G$. But $S$ is true. Therefore, it must be the one that can be deduced. The upshot is that whenever you have a theory (like group theory) with a model that admits a true sentence that can't be deduced from the axioms, then the theory is incomplete. The point of boring you with this discussion
is to illustrate that an incomplete theory is a very mundane object.

In case this suggests (as it should) that a complete theory, on the other hand, is bound to be very exotic, you might like this
simple list of a few complete theories.
For example, the theory of algebraically closed fields of characteristic zero is complete. This implies, in particular,
a logical incarnation of the 'Lefschetz principle': A field-theoretic sentence true in $C $ is true in every algebraically
closed field of characteristic zero. In fact, as noted above, a sentence true in any given model, since it can be deduced from the axioms,
is true in any other model. I found this fact quite mind-boggling when I first encountered it. A good exercise is to see why a sentence like 'every element of $bar{Q}$ is algebraic' doesn't cause a problem. (You need to get a bit more precise to do this, especially about the language of the theory.)

There is a complete theory of the natural numbers, by the way. Add to your favorite axioms of
arithmetic all the sentences that are true in the natural numbers. This is a perfectly respectable complete theory, sometimes referred to as the theory of natural numbers. Goedel's first incompleteness theorem can be
interpreted as saying this theory doesn't admit a recursively enumerable set of axioms. (Which should be at least
intuitively plausible if you consider difficult unresolved problems like, say, Goldbach's conjecture.)

Added:

In my opinion, it's not such a good idea to emphasize the 'string of formal symbols and rules' point of view when explaining the incompleteness theorem. It's true that to prove the theorem, you need to set up such background formalities. But the statement itself can plausibly be interpreted as something about everyday reasoning in mathematics. We are usually interested in some structure, a rather specific one like $Z/2$, a somewhat more general one like 2-groups, or more general yet like all groups. The question concerns which properties (or axioms satisfied by the structure, if you prefer) we use to prove certain assertions. The everyday nature of this question was the reason for bringing up the commutativity of $Z$, which I can certainly prove in the course of a normal discussion on the chalkboard, but anyone can see requires more than group theory.

This question also comes up rather frequently as one of great interest to practicing mathematicians. An advanced example that I can remember off the top of my head is 'Can one prove the Kodaira vanishing theorem using only algebraic geometry?,' which was resolved first by Faltings (although there is room for interpretation of the phrase 'only algebraic geometry').

In some sense, the rationale for the abstract formalism surrounding the incompleteness theorem is also pretty commonsensical. To prove that something can be done, you just need to do it. For example, I think it is uncontroversial that the proof of the Kodaira vanishing theorem by Deligne and Illusie uses 'only algebraic geometry.' And then, there are the famous elementary proofs of the prime number theorem. To prove that something can't be done, on the other hand, often requires more careful foundations.

Added again:

After some conversations, I decided to put in a few final words of clarification. I hope I didn't slight anyone with the joke about 'permanent deconfusion.' I don't claim to have any serious understanding of philosophical ramifications, for example. However, I tried to articulate what seems to me a sensible view of the matter for practicing mathematicians. Starting from the one given, you can yourself quickly make up examples illustrating the (uninteresting) incompleteness of a large majority of the theories we usually work with, rings, fields, topological spaces, etc. After that process, and thinking through just the few implications of completeness already mentioned, if someone came up to you and claimed that Peano Arithmetic was complete, I suspect your eyes would pop out.

Someone once told me that a good way to sound sophisticated as an amateur logician is to proclaim that the completeness theorem* is much more important than the incompleteness theorem. That's perhaps too sweeping a statement, but it seems to be the one that's useful for usual mathematics. For people interested in pursuing this line of thought, I recommend the nice lectures delivered by Angus Macintyre at the Arizona Winter School in 2003:

http://math.arizona.edu/~swc/aws/03/03Notes.html

One intriguing observation there I sometimes think about is how number-theoretic completions (reals and $p$-adics) correlate to logically complete theories.

*The completeness theorem essentially says that a sentence is a logical consequence of the axioms if and only if it's true in all models of the axioms. The idea for the non-trivial direction is to show how to construct, given any sentence that can't be deduced, a model for the axioms in which it is false.

at.algebraic topology - Why do Delta-sets not allow quotients?

The basic issue is that not every function that we would like to describe between $Delta$-complexes can be realized by a natural transformation between functors. The lack of degeneracy maps means that no map $X to Y$ of $Delta$-complexes that sends any simplex down to a degenerate simplex can be realized by a natural transformation of functors. For example, if $X$ is a $Delta$-complex interval realizing $[0,1]$ and $Y$ is a $Delta$-complex realizing $[0,1]^2$, then there is no natural transformation of functors realizing the projection maps $p_i:[0,1]^2 to [0,1]$.

As a consequence, the category of $Delta$-complexes does not have enough immediately-available maps between objects to construct the kinds of colimit diagrams one would like to realize.

Is the Fourier transform of $exp(-|x|)$ non-negative?

These questions are closely related to the so-called stable distributions. In particular,
the cauchy distribution on the real line has the characteristic function e^{-|x|}.

Go to the wikipedia page, and in the definition section set:
mu=0 (this is the drift parameter)
alpha=0 (this is the skewness parameter)

To get the same thing in higher dimensions, take independent copies in each coordinate.

Take note: These distributions are not square integrable--otherwise the 'universal' Central
Limit Theorem would hold. The cauchy distribution is only weakly integrable.

linear algebra - Surjectivity of bilinear forms.

The answer to Question B is no, as I'll show below.

Let $U=V=mathbf{Q}^3$ and $W=mathbf{Q}^4$. Define
$$beta((u_1,u_2,u_3),(v_1,v_2,v_3))=(u_1 v_1,u_2 v_2,u_3 v_3, (u_1+u_2+u_3)(v_1+v_2+v_3)).$$

Claim 1: $beta$ is not surjective.

Proof: In fact, we will show that $(1,1,1,-1)$ is not in the image. If it were, then we would have a solution to
$$(u_1+u_2+u_3)(u_1^{-1}+u_2^{-1}+u_3^{-1})=-1.$$
Clearing denominators leads to an elliptic curve in $mathbf{P}^2$, but MAGMA shows that all its rational points lie in the lines where some coordinate vanishes.

Claim 2: After base extension to any completion $k$ of $mathbf{Q}$, the bilinear map $beta$ becomes surjective.

Proof: Given $(a_1,a_2,a_3,b) in k^4$, we need to show that it is in the image. If $a_1=0$, then set $u_1=0$, $u_2=1$, $u_3=1$, $v_2=a_2$, $v_3=a_3$, and then solve for $v_1$ in the remaining constraint. The same argument works if $a_2=0$ or $a_3=0$. If $a_1,a_2,a_3$ are all nonzero, then we must find a solution to
$$(u_1+u_2+u_3)(a_1 u_1^{-1}+a_2 u_2^{-1}+a_3 u_3^{-1})=b.$$
Clearing denominators leads to the equation of a projective plane curve
with a smooth $k$-point $(1:-1:0)$, so by the implicit function theorem
there exist nearby $k$-points with $u_1,u_2,u_3$ all nonzero,
which gives us the solution we needed. $square$

If you want a reasonable answer to Question A, I'd suggest that you try to make it more focused.

soft question - Slightly weakened / altered concepts of a field

The meadow (as defined in the question, and in the paper linked) is an "equational theory".

A meadow is a set $A$ together with operations $0,1,+,-,cdot,{}^{-1}$ such that $(A,0,1,+,-,cdot)$ is a commutative ring with unit, and identities
$$
(x^{-1})^{-1} = x
\
xcdot(xcdot x^{-1}) = x
$$
hold for all $x in A$.

As with all equational theories, this tells us what are the morphisms, subalgebras, ideals, products, quotients, and so on. So: if $A, B$ are meadows, then a map $f : A to B$ is a homomorphism iff
$$
f(0)=0\
f(1)=1\
f(x+y)=f(x)+f(y)
\
f(-x)=-f(x)\
f(xy) = f(x)f(y)
\
f(x^{-1})=f(x)^{-1}
$$
(Some of these follow from the others, but abstractly you just say it preserves all the operations.)

A submeadow of a meadow $A$ is a subset $B subseteq A$ such that
if $x,y in B$, then
$$
0, 1, x+y, -x, xcdot y, x^{-1} in B
$$

An important example of a meadow is a field, with the usual partial operation $x^{-1}$ enhanced to a total operation by defining $0^{-1}=0$. This is called a zero totalized field.

More interesting examples are products of fields. For example $mathbb{Md}_6 = mathbb F_2 times mathbb F_3$.
Theorem: Any meadow is (up to isomorphism) a submeadow of a product of zero totalized fields.

As Robin Chapman noted (quoted in the paper mentioned): Take a meadow and forget the inverse operation, and you have a von Neumann regular ring; start with a von Neumann regular ring with unit, there is a unique way to define the inverse making it a meadow.

dg.differential geometry - Exponential map and covariant derivative

I think what the questioner is getting at here is the relation between a connection (or covariant derivative) on the tangent bundle of a manifold and what is called a "geodesic spray" (which is a more convenient way of representing the "exponential map"). This is the subject of a very old paper by Ambrose, Singer, and myself (in 1960). Here is Kuranishi's Math Reviews article for that paper.

MR0126234 (23 #A3530) 53.45 (53.55)
Ambrose,W.; Palais, R. S.; Singer, I. M.
Sprays.
An. Acad. Brasil. Ci. 32 1960 163–178

Let M be a $C^1$ manifold. When an affine connection of M is given, we can associate, for each
tangent vector x at a point m in M, the geodesic $alpha_x$ with tangent x at m. Conversely, we define a spray on M by saying that it is an assignment which gives, for each tangent vector x of M,
a $C^1$ curve $alpha_x$ in M satisfying certain conditions which are satisfied by the geodesics. A spray obtained by an affine connection is called a geodesic spray. The first theorem says that any spray is a geodesic spray and, moreover, we can prescribe the torsion form of the affine connection which gives the spray.

Let $M_m^k$ be the space of kth order tangent vectors of M at m. $M_m^k$ contains $M_m^1$. By an dissectionof M, we mean an assignment which gives, for each point m in M, a linear complementary
space $M_m^c$ of $M_m^1$ in $M_m^2$ such that the assignment is of class $C^infty$. Elements in $M_m^c$ are called pure. Clearly a dissection gives rise to a spray. Namely, we demand that the second-order tangent vectors of $alpha_x$ are pure. The second theorem says that this correspondence of dissections and sprays is injective as well as surjective.

Reviewed by M. Kuranishi

Copyright American Mathematical Society 1962, 2010

linear algebra - Matroids with prescribed independent sets

Let $A$ be a finite set. Let $B$ be a family of subsets of $A$. We are interested in a matroid with a minimum rank such that every element of $B$ is independent. The answer is obvious - a uniform matroid $U_{|A|,max_{C in B} |C|}$. But what if we restrict ourselves to, say, binary or even graphic matroids.

Can we characterize $B$'s that have a 'covering' binary (graphic) matroid with rank $r$? Does the problem of finding such a minimum $r$ lies in $mathbf{P}$ or $mathbf{coNP}$? Maybe there is a kind of min-max formula.

The case of graphic matroids can be reformulated as follows: suppose we have $m$ 'invisible' edges. We know that some subsets are acyclic. What is the minimum possible value of $n - c$, where $n$ stands for a number of vertices, and $c$ - for a number of connected components?

Any related results are interesting too.

banach spaces - Closed, complemented subspaces of $l^1(X)$ when $X$ is uncountable

A proof in English (modulo some details involving the Pelczynski decomposition method) can be found in the article 'On relatively disjoint families of measures' (Studia Math, 37, p.28-29) by Haskell Rosenthal.

Regarding the analogous result for $ell_p (X)$ ($pin (1,infty)$) and $c_0 (X)$, I seem to recall reading somewhere that it was solved by Joram Lindenstrauss, but now I can't seem to find any reference to it. I seem to think that I saw something about it in the Appendix to the English translation of Banach's book on linear operations (the appendix is by Bessaga and Pelczynski), but it would take me a while to sift through it to find it, and family dinner is being dished up very shortly. I wonder anyhow how much can be gleaned from Matthew Daws' classification of the closed, two-sided ideals in $mathcal{B}(ell_p (X))$, the Banach algebra of all bounded linear operators on $ell_p (X)$? The relevant paper can be downloaded at http://www.amsta.leeds.ac.uk/~mdaws/pubs/ideals.pdf . The paper 'The lattice of closed ideals in the Banach algebra of operators on a certain dual Banach space' by Laustsen, Schlumprecht and Zsak illustrates how classification of the complemented subspaces of a Banach space $E$ can follow from the classification of closed, two-sided ideals in $mathcal{B}(E)$ if all the closed, two-sided ideals are generated by projections onto complemented subspaces having certain nice properties. How much of this can be done using Matt's results I haven't checked, but I think that at the very least some partial results could be obtained. Matt might comment of this if he passes by, or if no one else does I might try to look into it in the next day or so and edit this answer accordingly.

The analogous result for $ell_infty (X)$ does not hold for uncountable $X$ in general. Indeed, every $ell_infty (X)$ is the dual of $ell_1 (X)$, every Banach space embeds isomorphically into some $ell_infty (X)$, but there are injective Banach spaces that are not isomorphic to any dual Banach space; the first such example seems to have been found by Haskell Rosenthal in his paper 'On injective Banach spaces and the spaces $L^infty (mu)$ for finite measure $mu$' (Acta Mathematica, 124, Corollary 4.4), and the existence of such a space provides the desired counterexample.

ca.analysis and odes - Distribution of zeros

Just some hints. The functions $f^{\,(k)}$ have the same zeros of the polynomials $P_k:=f^{\,(k)}exp(-Q)$, that satisfy $P_0:=P$ and $P_{k+1}=P_k'+P_kQ'$. In particular $P_k$ has degree $deg(P)+kleft(deg(Q)-1right)$, and this is also the total number of zeros of $f^{\,(k)}$. They may be all real: for instance if $Q:=-x^2$ and $P:=1$ one finds the Hermite polynomials, that are orthogonal, hence have all zeros real and simple.

Simple inequality in C*-algebras

Theorem 1.5 of this 1987 paper by J. Phillips says that if $f:[0,infty)to [0,infty)$ is a continuous operator monotone function and $a$ and $b$ are positive operators on a Hilbert space, then $|f(a)-f(b)|leq f(|a-b|)-f(0)$. I think that the proof is nice. Corollary 1.6 says that $|a^{1/n}-b^{1/n}|leq|a-b|^{1/n}$, $ngeq1.$ Of course your inequality follows from taking $a=x^2$, $b=y^2$, and $n=2$.

Apparently Kittaneh and Kosaki have a similar approach in "Inequalities for the Schatten p-norm. V." Publ. Res. Inst. Math. Sci. 23 (1987), no. 2, 433--443 (MR link). I haven't read any of this article.

Perhaps I should add the following for a more general audience. A continuous function $f:[0,infty)to [0,infty)$ is operator monotone if whenever $x$ and $y$ are positive operators such that $y-x$ is positive, it follows that $f(y)-f(x)$ is positive. The functions $tmapsto t^alpha$ are operator monotone for $0<alphaleq1$ (but not for $alpha>1$).

discrete geometry - Random walk is to diffusion as self-avoiding random walk is to ...?

One can view a random walk as a discrete process whose continuous
analog is diffusion.
For example, discretizing the heat diffusion equation
(in both time and space) leads to random walks.
Is there a natural continuous analog of discrete self-avoiding walks?
I am particularly interested in self-avoiding polygons,
i.e., closed self-avoiding walks.

I've only found reference
(in Madras and Slade,
The Self-Avoiding Walk, p.365ff)
to continuous analogs of "weakly self-avoiding walks"
(or "self-repellent walks") which discourage but
do not forbid self-intersection.

I realize this is a vague question,
reflecting my ignorance of the topic.
But perhaps those knowledgeable could point me to the
the right concepts. Thanks!

Addendum.
Schramm–Loewner evolution is the answer. It is the conjectured scaling limit of the self-avoiding walk and several other related stochastic processes. Conjectured in low dimensions,
proved in high dimensions, as pointed out by Yuri and Yvan. Many thanks for your help!

career - What to look for in applicants to graduate programs (in mathematics)?

Let me take a crack at the question, since I am currently on the graduate committee at UGA. [The University of Georgia is about the 50th best department in the country, so just a little shy of being a research 1 university. We are strongest in algebra, number theory, and algebraic geometry and are able to attract some excellent students in these areas.]

The two most important things for us are:

1) Very good to excellent grades, in courses which go beyond the minimum necessary for a math major and include, if possible, at least one graduate course. We are looking for all grades B or higher and at least as many A's as B's (which implies a GPA of at least 3.5). One or two poor grades will not concern us too much if they are in lower level courses, are followed by several years of better grades, or some explanation is given in the personal statement and/or the letters of recommmendation. A successful applicant will probably have taken real analysis, abstract algebra and topology. We certainly do take into consideration the student's school: e.g. a student from a liberal arts college may not have any graduate courses available.

2) High GRE scores. We like to see at least 700 on the GRE quantitative. It is not as criticial, but I would like to (and often do not!) see at least 600 on the GRE verbal; both scores are kept in mind by the university when it makes decisions about who will get prestigious fellowships. As for the GRE math subject exam: I am sorry to say that as of this year we do not require it. After looking at other universities of equal and greater status, we have decided to start requiring this exam next year (i.e., for students who are applying to start in Fall 2011), although we recognize that this may shrink our applicant pool. A score in the top 50% on the math subject exam looks good to us.

Next come the recommendation letters, which we use to gauge the student's enthusiasm, ability and preparedness for graduate school as compared to other aspiring graduate students. It is much better for us if the letters come from someone that we have heard of, or whom we can verify is a successful research mathematician (I have looked some recommenders up on MathSciNet). Good things to see in such letters are comparisons to other students who have gone on to be successful at research 1 graduate programs.

REU experience looks good, especially if accompanied by a recommendation letter from the REU supervisor who can be specific about what is accomplished. Sometimes students do enclose papers or preprints that are the result of REU work. Again we like this in general (more if the paper looks interesting, less if it looks rather trivial) and may forward this along to other faculty members to see if they are especially interested in the student.

I would say that the personal statement is in fact not very important, except perhaps to address/explain weaknesses in other parts of the application. [I accept that it might be more useful at a different institution. I have also advised graduate students and postdocs applying for academic jobs that their cover letter is not very important, and I know that some people -- especially at liberal arts colleges -- have said exactly the opposite.] It is useful as a writing sample, and a lack of spelling, grammatical and punctutation errors is evidence that the student is serious about their application.

In fact it is probably more likely that you will lose points in your personal statement than gain them. When I was a college senior, we had a Q&A session about applying to grad school. The head of the computer science department (Lance Fortnow, I think) told us the following story: he once had an application from a candidate who had very strong grades, GRE scores and recommendation letters. But in his personal statement he was asked "Why do you want to go to graduate school in computer science?" The candidate's response "Because I am trying to avoid working very hard" was exactly the opposite of what the department head wanted to hear. The rest of the application was so strong that, albeit with some misgivings, this candidate was admitted. The result was disastrous: the candidate really didn't want to do any work so was (of course!) a most unsuccessful graduate student, eventually getting kicked out of the program. The CS department head concluded that after this experience, he would never admit a candidate who said something like that on their personal statement. (And neither would I.)

soft question - Least collaborative mathematician

Here is what Zentralblatt (which now includes Jahrbuch der Mathematik) says about
Godeaux, Lucien.

https://zbmath.org/authors/?s=0&c=100&q=Godeaux%2C+L
Author-ID: godeaux.lucien
Published as: Godeaux, L.; Godeaux, Lucien
Documents indexed: 1213 Publications since 1906, including 28 Books
Co-Authors
1 Brocard, H.
1 Errera, Alfred
1 Mineur, Adolphe
1 Plakhowo, N.
1 Rozet, Octave

And about
Vietoris, Leopold

Author-ID: vietoris.leopold
Published as: Vietoris, Leopold; Vietoris, L.
Documents indexed: 80 Publications since 1916, including 1 Book
Co-Authors
1 Tietze, Heinrich

Reference request: representation theory of the hyperoctahedral group

I was wondering if someone knows a good reference for the representation theory of the hyper-octahedral group $G$. The hyper-octahedral group $G$ is defined as the wreath product of $C_2$ (cyclic group order $2$) with $S_n$ (symmetric group on $n$ letters).

I understand that the representations of $G$ are in bijection with bi-partitions of $n$. I am looking for a reference which explains the details of why the representations of $G$ are in bijection with bi-partitions of $n$, and constructs the irreducible representations of $G$ (I imagine this is vaguely similar to the construction of Specht modules for $S_n$).

So far, the only reference I have is an Appendix of MacDonald's "Symmetric functions and Hall polynomials" (2nd version), which deals with the representation theory of the wreath product of $H$ with $S_n$ (for $H$ being an arbitrary group, not $C_2$).

mp.mathematical physics - Are there any known quantum algorithms that clearly fall outside a few narrow classes?

While most famous quantum algorithms fall into your categories (2)-(4) ("linear algebra" isn't especially informative, as all of quantum computation can be understood as an application of linear algebra...), there are some others that don't.

First, there's an algorithm of Childs et al that uses a quantum walk to traverse a graph in polynomial time, for which any classical algorithm requires exponential time. This relies on the fact that quantum walks can hit exponentially faster than classical random walks. There are a number of other algorithms based around quantum walks; I guess you could characterise these as "quantum search", but some have a different feel to them.

Second, there are quantum algorithms for approximating the Jones polynomial and other graph invariants (see, for example, the paper of Aharonov, Jones and Landau, or Section X of the paper by Childs and van Dam you linked to). These algorithms essentially work by encoding the problem instance to be solved directly into a quantum circuit.

Third, there is an algorithm of Harrow, Hassidim and Lloyd which calculates properties of solutions to large systems of linear equations exponentially more efficiently. The main ingredient that goes into this (phase estimation) is also used in algorithms for factoring etc, but the application seems very different.

There are also some algorithms which may not achieve especially large speed-ups, but which demonstrate different design techniques. For example, there's a nice algorithm of Hoyer, Neerbek and Shi that solves the task of search in an ordered list somewhat faster than classical binary search. The algorithm is based on searching a number of subtrees of a binary tree in quantum parallel. I should also mention a nice algorithm of van Dam (quant-ph/9805006) which demonstrates that an n bit string can be read from an oracle using just over n/2 quantum queries.

Finally, there are algorithms for purely quantum information theoretic tasks, which are by their nature different again. In particular, the algorithm of Bacon, Chuang and Harrow for the Schur transform has a number of applications in quantum information theory (eg. state estimation, entanglement concentration and communication without a shared reference frame).

ag.algebraic geometry - References for equivariant K-theory

I spent the last few days¹ reading references on equivariant K-theory. I just pulled together the following bibliography for my collaborators and I can't see a reason not to make it public. This list tilts heavily towards combinatorics and classical algebraic geometry.

My general conclusion is that there are several good references on equivariant K-theory localization, but they are all too dense for someone who has never seen this stuff before. Fortunately, there are good, slow, introductions to equivariant cohomology, and the two fields are similar enough that you can get the motivation and examples from the cohomology papers and then dive into the K-theory tomes.

This post is Community Wiki, so feel free to add your own favorites.

Short papers with lots of nice examples

1: Julianna Tymoczko's introduction to equivariant cohomology

2: Early parts of Knutson-Tao's paper on the equivariant cohomology of the Grassmannian

More detailed references on equivariant cohomology:

3: Fulton's notes. See lectures 4 and 5 for localization, lectures 6 - 10 for special features of homogeneous spaces.

4: Section 2 of Guillemin and Zara's first paper, explaining which parts of the story are pure combinatorics.

References specifically for K-theory

5: Chapters 5 and 6 of Complex Geometry and Representation Theory, by Chriss and Ginzburg. Lots and lots of detail, and focuses on flag varieties in particular. One of the only places I've found that describes how to pushforward to something other than a point.

6: Guillemin and Zara's K-theory paper. This is similar to the previous paper of theirs that I cite, but terser and for K-theory.

7: A paper of Nielsen, which seems to have anticipated a lot of the results in this field, and has some nice examples at the end. (Note: The MathSciNet review is in French, but the paper is in English.)

8: Knutson and Rosu's paper, establishing localization in equivariant K-theory and explaining equivariant Grothendieck-Riemann-Roch.

William Fulton also tells me that he and Graham are working on an expository article, which I expect will be excellent.

¹ For those who are curious, I am not learning this material for the first time. Rather, I originally learned it by skimming a lot of papers, going to talks and asking Allen Knutson about anything that confused me. I am now playing the role of Allen to others, so I need to learn the subject better.

algorithms - Checking whether given binary operation is a group operation

Given a binary function $f: [1..n] times [1..n] to [1..n]$ how to check that this operation is a group operation on $[1..n]$?

It's obvious that this can be done in $O(n^3)$ time just by checking all group properties. The most time-expensive property is associativity. Also it's clear that it could not be done faster than $O(n^2)$ time since you should at least examine all values $f(i,j)$.

The question is if there is any algorithm to solve this problem in time faster than $O(n^3)$?

modular forms - What is a TMF in topology?

If you know about classical modular forms, and you want to understand what they have to do with tmf, it is good to contemplate something more classical: the "derived functors of modular forms".

Modular forms of weight $n$ are $H^0(M, omega^n)$, where $omega$ is a certain line bundle over $M=$compactified moduli stack of elliptic curves. There is non-trivial cohomology in

$H^s(M,omega^n)$

for $s>0$. This comes in two flavors:

* free abelian group summands in $H^1(M,omega^n)$ for $nleq-10$. These correspond by a kind of "Serre duality" to the usual modular forms in $H^0(M,omega^{-n-10})$.

* finite abelian groups (killed by multiplication by $24$) in $H^s(M,omega^n)$ for arbitrarily large $s$.

There is a spectral sequence

$H^s(M,omega^{t/2}) Rightarrow pi_{t-s} Tmf$,

and the edge of the spectral sequence gives a map $pi_{2n}Tmf rightarrow H^0(M,omega^n)$. This is essentially the map Chris describes in his answer.

Slightly confusingly, the gadget I've called Tmf (which is the global sections of a sheaf of spectra over $M$) is not the same as TMF (the $576$-periodic guy, which is sections on $M'=$stack of smooth elliptic curves), or tmf (the connective cover of Tmf, which I don't believe is known to be sections on anything).

I recommend Goerss's Bourbaki talk for learning more about this, especially section 4.6.

reference request - English translation of Riemann's Habilitation Thesis

After some googling, I couldn't find an English translation, but I found (cf Chapter 38
of "Landmark writings in Western mathematics 1640-1940" (eds. Grattan-Guinness, Cook)) a
reference to a French translation:

Bulletin des sciences math'ematiques, (1) 5 (1873), 20-48, 79-96

Reprinted in Riemann's Oeuvres math'ematiques (ed. Laugel), Paris: Gauthier-Villars, 1898, 227-279.

(Also that chapter 38 I mentioned seems to have a detailed explanation, in English, of the contents of the paper.)

big picture - Defining variable, symbol, indeterminate and parameter

In written English (and of course other languages), we have linguistic constructs which tell the reader how to approach the ideas that are about to be presented. For example, if I begin a sentence with "However, . . .", the reader expects a caution about a previously stated proposition, but if I begin the sentence with "Indeed, . . . ", the reader expects supporting evidence for a position. Of course we could completely discard such language and the same ideas would be communicated, but at much greater effort. I regard the words "variable", "constant", "parameter", and so on, in much the same way I regard "however", "indeed", and "of course"; these words are informing me about potential ways to envision the objects I am learning about. For example, when I read that "$x$ is a variable", I regard $x$ as able to engage in movement; it can float about the set it is defined upon. But if $c$ is an element of the same set, I regard it as nailed down; "for each" is the appropriate quantifier for the letter $c$. And when (say) $xi$ is a parameter, then I envision an uncountable set of objects generated by $xi$, but $xi$ itself cannot engage in movement. Finally, when an object is referred to as a symbol, then I regard its ontological status as in doubt until further proof is given. Such as: "Let the symbol '$Lv$' denote the limit of the sequence $lbrace L_{n}v rbrace_{n=1}^{infty}$ for each $v in V$. With this definition, we can regard $L$ as a function defined on $V$. . . "

So in short, I regard constructing precise mathematical definitions for these terms as equivalent to getting everyone to have the same mental visions of abstract objects.

ag.algebraic geometry - Why and how are moduli spaces of (semi)stable vector bundles well-behaved?

From a topological viewpoint, I believe the idea is that one wants to have a Hausdorff quotient space. In other words, consider the space of all holomorphic structures on a fixed (topological) vector bundle on a curve. Holomorphic structures can be viewed as differential operators on sections of the bundle, such that a section is holomorphic if and only if this operator evaluates to zero on the section. (See, for example, sections 5 and 7 of Atiyah and Bott's "The Yang-Mills equations over Riemann surfaces.") This makes the space of holomorphic structures (i.e. the space of bundles with a fixed topological type) into an affine space. The group of complex automorphisms of the bundle acts on this space, and the quotient is the moduli space of holomorphic bundles. If you don't restrict to stable bundles, this quotient space fails to be Hausdorff. Atiyah and Bott reference this to Mumford's 1965 GIT book. Actually, they just say that the moduli space of stable bundles is Hausdorff, due to the fact that the orbits of stable bundles are closed. (Hmmm... that really just says points are closed in the quotient...) I don't know how much of this is spelled out in Mumford; in particular, I don't know whether there's a proof in the literature that the full quotient space fails to be Hausdorff.

gn.general topology - profinite spaces are the pro-completion of finite sets

Let $f:X to Z$ be a map to a finite discrete space. Note that each fiber, $f^{-1}(z)$, is both open and closed in $X$. Let $p_i: X to X_i$ be the projection maps.

Fix some $z in Z$. Since $f^{-1}(z)$ is open, and the fibers of the maps are a basis, there is an open cover of $f^{-1}(z)$ by sets of the form $p_i^{-1}(x)$, for $x$ in various $X_i$.
Since $f^{-1}(z)$ is closed in a compact space, it is compact. So we can take a finite subcover of this cover. Thus, there is some single index $i$ for which $f^{-1}(z)$ is covered by sets of the form $p_i^{-1}(x)$, $x in X_i$.

Since $Z$ is finite, there is a single $i$ such that, for every $z in Z$, the fiber $f^{-1}(z)$ is covered by sets of the form $p_i^{-1}(x)$, $x in X_i$. The map $f$ factors through $X_i$.

ag.algebraic geometry - Is there a reason for defining the differential forms before the vector fields ?

Dear Nicojo, since you mention philosophical reasons let me remark that, since a scheme $(X,mathcal O_ X)$ is a locally ringed space, the most primitive concepts should be as close as possible to the data, the (generalized) functions encapsulated in the sheaf $mathcal O_X$ .

At a point $xin X$ , what could be more natural to consider as the COtangent Zariski space $mathcal M/mathcal M^2$ ? It just consists of the functions vanishing at $x$ modulo those vanishing at higher order. And the dimension $d$ of this space will already tell you if the (locally noetherian) scheme $X$ is regular or not at $x$, according as $d=dimmathcal O_{X,x}$ or $d> dimmathcal O_{X,x}$

In the relative case $X/S$ the sheaf $Omega_{X/S}$ will give you a lot of information. Just its nullity at a point already tells you (under a mild finiteness condition) everything about nonramification:

$Omega_{X/S,x}=0 iff $ $f:Xto S$ is unramified at $x$

And this is only the beginning: by taking the top exterior product of $Omega_{X/k}$ you get (in the smooth projective case over an algebraically closed field $k$) the canonical sheaf $omega_{X/k}$ which is a key concept for Serre duality. This canonical sheaf also plays a fundamental role in the classification of curves, surfaces and higher dimensional varieties, arguably the very heart of classical algebraic geometry . For example to $X$ you associate its canonical ring $R$, a graded ring whose degree $m$ component is $R_m=Gamma(X,omega^m)$.
The Kodaira dimension of $X$ is $kappa(X)=trdeg_k (R)-1$ and general varieties are defined as those with $kappa(x)=dim(X)$. They are supposed to be generic in some sense and have been intensively studied, in particular by the Japanese school (Kodaira, Iitaka, Kawamata, Ueno, Mori, ... )

big list - Different ways of thinking about the derivative

The derivative of a Regular Type is its Type of One-Hole Context

This is a surprising computational application related to Qiaochu's example, but different enough to warrant some explanation. Apologies for some of my hand-waveyness.

In a suitably pure programming language (like Haskell) we can think of data types as being objects of a category and functions (suitably qualified) as arrows. We often want to build one type from another. For example, given a type $X$ we can form the type $Xtimes X$, the type of pairs of $X$'s. Similarly we can form coproducts which correspond to objects that can be of one type or another. Eg. if $Y=X+X^2$ then $Y$ is a type which contains either an $X$ or a pair of $X$'s. The functions that construct one type from another, call them type constructors, can naturally be thought of as functors. So $P$ defined by $P(X)=X^2$ is a functor. If $(x,y)$ is in $X^2$ then $Pf(x,y)=(f(x),f(y))$. Types form a semiring.

Sometimes we want to make a 'hole' in a type constructors. If $F$ is a type constructor, then $F(A)$ can be thought of as a container of elements of type $A$. An "$F$ with a hole in it" is one of these containers but with one of its elements removed, but still keeping information about where the element was removed from. For example consider $F(X)=X^3$. $F$ makes triples of $X$'s. A triple with a hole in it consists of just two $X$'s as well as enough information to tell where the third element was removed from. There are just three places it could have come from, so we can describe the removal site using a type with just three elements. Call it $3$. So a triple with a hole in it is a pair consisting of an element of type $3$ and an element of type $X^2$. Ie. $3X^2$. This is $F'(X)$.

This works more generally. We make holes in type constructors by differentiating them.

It even works with recursive types. For example, a list of $X$'s is, by definition, either the empty list, or a pair consisting of an $X$ and a list. We have an equation

$L(X)=1+XL(X)$.

We can differentiate this to get

$L'(X)=L(X)+XL'(X)$

This gives a recursive equation for a type of a list with a hole in it. This is in fact an example of a type called a zipper. Used in many places such as this application. In the particular case of lists $L'(X)$ defines a pair of lists of $X$'s.

(Much of this applies in the category $Set$ but the recursive equations can introduce some issues of well-foundedness if taken too literally.)

Many of the usual properties of derivatives acquire straightforward computational interpretations: linearity, the product rule, the chain rule, even the Faà di Bruno formula.

Anyway, check out the papers which have none of the errors I've probably introduced. There's also a close relationship with combinatorial species.

(Curiously, you can also make sense of finite differences of types even though we only have a semiring and don't have subtraction of types.)

ag.algebraic geometry - Is a universally closed morphism of schemes quasi-compact ?

A morphism of schemes $f:Xto S$ is said to be quasi-compact if for every OPEN quasi-compact subset $K subset S$ the subset $f^{-1}(K) subset X$ is also quasi-compact (and open, of course!). The morphism $f:Xto S$ is said to be universally closed if for every morphism $Tto S$ the resulting base-changed morphism $X_T to T$ is closed. The title question (inspired by topology) is then:

Question 1: If $f:Xto S$ is universally closed, does it follow that $f$ is quasi-compact?

Here is a variant of this question, asking for a stronger conclusion :

Question 2: If $f:Xto S$ is universally closed, does it follow that for every quasi-compact subset $Ksubset S$, open or not,
$f^{-1}(K)$ is quasi-compact ?

REMARK 1 The converse of Question 1 is false: any morphism between affine schemes is quasi-compact but is not universally closed in general.

REMARK 2 One might wonder whether $f$ proper implies $f$ quasi-compact. The answer is "yes" but for an irrelevant reason: proper is defined as separated, universally closed and of finite type. Since finite type already implies quasi-compact, proper obviously implies quasi-compact.

REMARK 3 In topology "proper" is (or should be !) defined as universally closed; equivalently, closed with quasi-compact fibres. Topologically proper implies that every quasi-compact subset (open or not) of the codomain has quasi-compact inverse image. The converse is not true in general, but it is for locally compact spaces.

REMARK 4 (edited).As BCnrd remarks in his comment below, it is not at all clear that the two questions are equivalent (I had stated they were in the previous version of this post, but I retract that claim ). Also, beware that in topology the notion of quasi-compact continuous map is so weak as to be essentially useless since decent topological spaces, the ones algebraic geometers never use :) , have so few open quasi-compact subsets.

topos theory - Is there a "Grothendieckification" functor from elementary toposes to Grothendieck toposes?

No, it doesn't. If it did, then it would preserve limits. But the category of Grothendieck toposes and geometric morphisms has a terminal object, namely the category of sets, while there are elementary toposes not admitting any geometric morphism to Set (for instance, any small elementary topos).

gr.group theory - Does every finitely generated group have a maximal normal subgroup?

If you mean nontrivial maximal normal subgroup (not 1 or the whole group), then the answer is no.

Higman constructed a finitely generated infinite group G with no subgroups of finite index. You then get a finitely generated group with no nontrivial normal subgroups by taking the quotient by a maximal normal subgroup.

Higman's group G is < a,b,c,d | a^-1 b a = b^2, b^-1cb = c^2, c^-1dc=d^2, d^-1ad=a^2 >

See Higman, Graham. A finitely generated infinite simple group. J. London Math. Soc. 26, (1951). 61--64.

Edit:

If you mean does it have a proper maximal normal subgroup, then the answer is yes:

Finitely generated groups have a (possibly trivial) maximal normal subgroup. Higman's reference for this is B.H. Neumann, "Some remarks on infinite groups ", Journal London Math. Soc, 12 (1937), 120-127.