Planet Musings

November 23, 2009

Michael Nielsen — Biweekly links for 11/23/2009

Local Bookstores, Social Hubs, and Mutualization « Clay Shirky
- Shirky on the future of bookstores.
Charlie Stross on reading and the book business
- A very short, interesting tidbit from Stross.
bit-player
- Brian Hayes’ excellent blog on computing and mathematics
An Unstoppable Force Meets…: INTERNETPOKERS: Poker Blog
- Great upheavals in the world of high-stakes online poker.
Corrupted Blood incident – Wikipedia, the free encyclopedia
- “The Corrupted Blood incident was a widely reported virtual plague outbreak and video game glitch found in the … game World of Warcraft… The plague began on September 13, 2005, when an area was introduced in a new update. One boss could cast a spell called Corrupted Blood, which would deal a certain amount of damage over a period of time, and which could be transferred from character to character. It was intended to be exclusive to this area, but players discovered ways to take it out, causing an epidemic across several servers. During the epidemic, some players would help combat the disease by volunteering healing services, while select others would maliciously spread the disease. These people have been compared to real-world disease spreaders, including early AIDS patient Gaëtan Dugas and Typhoid patient Mary Mallon… [World of Warcraft creator] Blizzard [was forced] to do a hard reset of all of its servers for the game.”
Access denied? : Article : Nature
- “Every weekday, thousands of researchers around the world access the Arabidopsis Information Resource (TAIR), which contains the most reliable and up-to-date genomic information available on the most widely used model organism in the plant kingdom. But now, to those users’ horror, TAIR faces collapse: the US National Science Foundation (NSF) is phasing out funding after 10 years as the data resource’s sole supporter (see page 258).
  
  TAIR’s plight is emblematic of a broader crisis facing many of the world’s biological databases and repositories. Research funding agencies recognize that such infrastructures are crucial to the ongoing conduct of science, yet few are willing to finance them indefinitely. Such agencies tend to support these resources during the development phase, but then expect them to find sustainable funding elsewhere.”

Click here for all of my del.icio.us bookmarks.

by Michael Nielsen at November 23, 2009 04:54 AM

n-Category Café Equipments

$MathML-enabled post (click for more details).$

I mentioned in my intro that as wonderful as $n$ -categories are, they’re really just one (important) part of the zoo of “higher categorical structures” out there. Today I want to tell you about another inhabitant of that zoo: a wonderful gadget that’s come out of Australia called a proarrow equipment (or just an equipment), which lets us do what I call “formal category theory.” Equipments don’t seem to be very well-known yet in the northern hemisphere, but there are some indications that they’re gaining ground, so I’m doing my best to help them along.

This post will be a lightning-fast introduction to formal category theory in equipments. But I’m going to present the definition in a nonstandard way, because it turns out that an equipment is basically the same as what I’ve called a framed bicategory, and I find that way of thinking about it more natural—and also easier to generalize (but that’s another post). Some of it may go by a little quickly, but I think it’s the sort of thing that’s really quite fun to work out yourself once you’ve been pointed in the right direction.

$MathML-enabled post (click for more details).$

What do I mean by formal category theory? This is an analogy to the way in which category theory can be called “formal mathematics.” That is, we see ourselves doing the same thing all the time in mathematics (limits, colimits, adjoints, universal constructions) and we write down category theory in order to do all those things formally, once and for all in abstract generality. But nowadays there are actually lots of kinds of category theory too: ordinary category theory, enriched category theory, internal category theory, fibered category theory, etc. After a while, one starts to get the feeling of “doing the same thing all the time” again: defining limits and colimits, proving adjoint functor and monadicity theorems, etc. So, can we “formalize” the essential aspects of category theory in an analogous way, and if so, how?

You might expect the answer to be “yes, with 2-categories.” Perhaps surprisingly, however, 2-categories don’t always suffice. We can do a lot of category theory in a 2-category: we can define adjunctions, construct Eilenberg-Moore and Kleisli objects for monads (the “formal theory of monads”), and talk about Kan extensions, comma objects, fibrations, and so on. But some things are missing, and some of the general notions are not always quite right. For instance, the most obvious 2-categorical analogue of a limit is a Kan extension, since in ordinary category theory limits can be identified with Kan extensions along functors to the terminal category. However, in enriched category theory this is insufficient; not all weighted limits arise in that way. Moreover, the “internal” notion of Kan extension in a 2-category gives the “weak” notion rather than the more important “pointwise” one.

The central observation is that what’s missing from the 2-category $Cat$ is hom-functors, and more generally profunctors. Recall that a profunctor (aka “distributor” or “(bi)module”) $C ↛ D$ is a functor $D^{op} \times C \to Set$ (or to $D^{op} \otimes C \to V$ , if $C$ and $D$ are $V$ -enriched). Including profunctors in our “structure for formal category theory” will allow us to talk about their representability, which is the essential ingredient for limits, pointwise Kan extensions, and all the other things that are missing from a 2-category.

So what kind of formal structure includes categories, functors, and profunctors? There are several different answers, but to me, the most obvious and natural-looking answer is a double category. Specifically, there’s a double category $\underset{̲}{Prof}$ whose objects are small categories, whose vertical arrows (which we’ll just call “arrows”) are functors, whose horizontal arrows (which we’ll call “proarrows”) are profunctors, and whose squares

\begin{matrix} A & \overset{H}{↛} & B \\ ^{f} ↓ & ⇓ & ↓^{g} \\ C & \underset{K}{↛} & D \end{matrix}

are transformations $H (b, a) \to K (g b, f a)$ natural in $a$ and $b$ . Composition of profunctors is by a coend:

(H ⊙ K) (c, a) = \int^{b \in B} H (b, a) \otimes K (c, b)

(note that I’m writing it in diagrammatic order) and the identity profunctor of $C$ is its hom-profunctor $U_{C} = {Hom}_{C} : C^{op} \times C \to Set$ . The 2-categories $Cat$ and $Prof$ can be recovered from $\underset{̲}{Prof}$ as its vertical and horizontal 2-categories, respectively, which I’ll write as $Cat = 𝒱 (\underset{̲}{Prof})$ and $Prof = ℋ (\underset{̲}{Prof})$ . (For $Prof$ , this is basically by definition; for $Cat$ , it’s a nice exercise in the Yoneda lemma.)

Similar double categories exist for all the other kinds of category theory (enriched, internal, fibered, etc.). Moreover, all these double categories have an additional very important property: given any “niche”

\begin{matrix} A & B \\ ^{f} ↓ & ↓^{g} \\ C & \underset{K}{↛} & D \end{matrix}

there exists a “universal” or “cartesian” filler square

\begin{matrix} A & \overset{K (g, f)}{\to} & B \\ ^{f} ↓ & ⇓ & ↓^{g} \\ C & \underset{K}{↛} & D \end{matrix}

with the property that any other square

\begin{matrix} X & ↛ & Y \\ ^{f h} ↓ & ⇓ & ↓^{g k} \\ C & \underset{K}{↛} & D \end{matrix}

factors through the universal one uniquely:

\begin{matrix} X & ↛ & Y \\ ^{h} ↓ & \exists! ⇓ & ↓^{k} \\ A & \overset{K (g, f)}{\to} & B \\ ^{f} ↓ & ⇓ & ↓^{g} \\ C & \underset{K}{↛} & D \end{matrix}

The profunctor $K (g, f)$ is of course just $K (g -, f -) : B^{op} \times A \to Set$ . We say that a double category $\underset{̲}{X}$ having this property equips the 2-category $𝒱 (\underset{̲}{X})$ with proarrows, and speak of the whole double category as a proarrow equipment, or just an equipment. (Yes, “equipment” is being used as a singular noun; it’s been (non)translated from Australian.)

Of particular importance in an equipment are the proarrows $B (1, f) = U_{B} ({id}_{B}, f)$ and $B (f,1) = U_{B} (f, {id}_{B})$ , which exist for any arrow $f : A \to B$ . By factoring the identity square

\begin{matrix} A & \overset{U_{A}}{\to} & A \\ ^{f} ↓ & ^{U_{f}} ⇓ & ↓^{f} \\ B & \underset{U_{B}}{\to} & B \end{matrix}

through the universal fillers

\begin{matrix} A & \overset{B (1, f)}{\to} & B \\ ^{f} ↓ & ⇓ & ↓^{id} \\ B & \underset{U_{B}}{\to} & B \end{matrix} and \begin{matrix} B & \overset{B (f,1)}{\to} & A \\ ^{id} ↓ & ⇓ & ↓^{f} \\ B & \underset{U_{B}}{\to} & B \end{matrix}

that define $B (1, f)$ and $B (f,1)$ , we obtain additional squares

\begin{matrix} A & \overset{U_{A}}{\to} & A \\ ^{f} ↓ & ⇓ & ↓^{id} \\ B & \underset{B (f,1)}{\to} & A \end{matrix} and \begin{matrix} A & \overset{U_{A}}{\to} & A \\ ^{id} ↓ & ⇓ & ↓^{f} \\ A & \underset{B (1, f)}{\to} & B \end{matrix}

such that the composites

\begin{matrix} A & \overset{U_{A}}{\to} & A \\ ^{id} ↓ & ⇓ & ↓^{f} \\ A & \overset{B (1, f)}{\to} & B \\ ^{f} ↓ & ⇓ & ↓^{id} \\ B & \underset{U_{B}}{\to} & B \end{matrix} and \begin{matrix} A & \overset{U_{A}}{\to} & A \\ ^{id} ↓ & ⇓ & ↓^{f} \\ A & \underset{B (1, f)}{\to} & B \\ ^{f} ↓ & ⇓ & ↓^{id} \\ B & \underset{U_{B}}{\to} & B \end{matrix}

are both equal to $U_{f}$ . And using the uniqueness of factorization through the universal squares, we can conclude moreover that the composites

\begin{matrix} A & \overset{U_{A}}{\to} & A & \overset{B (1, f)}{\to} & A \\ ^{id} ↓ & ⇓ & ↓^{f} & ⇓ & ↓^{id} \\ A & \underset{B (1, f)}{\to} & B & \underset{U_{B}}{\to} & B \end{matrix} and \begin{matrix} B & \overset{B (f,1)}{\to} & A & \overset{U_{A}}{\to} & A \\ ^{id} ↓ & ⇓ & ↓^{f} & ⇓ & ↓^{id} \\ B & \underset{U_{B}}{\to} & B & \underset{B (f,1)}{\to} & A \end{matrix}

are equal to the identity squares of $B (1, f)$ and $B (f,1)$ respectively. In double-category lingo which I adopted from Dawson, Paré, and Pronk, this says that $B (1, f)$ is a companion of $f$ and $B (f,1)$ is a conjoint of $f$ . It follows, in particular, that $B (1, f)$ and $B (f,1)$ are adjoint in $ℋ (\underset{̲}{X})$ .

Now the central lemma about these companions and conjoints is the following: there is a natural bijection between squares of the form

\begin{matrix} A_{0} & \overset{H}{\to} & B_{0} \\ ^{f_{1}} ↓ & ↓^{g_{1}} \\ A_{1} & B_{1} \\ ^{f_{2}} ↓ & ⇓ & ↓^{g_{2}} \\ A_{2} & B_{2} \\ ^{f_{3}} ↓ & ↓^{g_{3}} \\ A_{3} & \underset{K}{\to} & B_{3} \end{matrix}

and squares of the form

\begin{matrix} A_{1} & \overset{A_{1} (f_{1},1)}{\to} & A_{0} & \overset{H}{\to} & B_{0} & \overset{B_{1} (1, g_{1})}{\to} & B_{1} \\ ^{f_{2}} ↓ & ⇓ & ↓^{g_{2}} \\ A_{2} & \underset{A_{3} (1, f_{3})}{\to} & A_{3} & \underset{K}{\to} & B_{3} & \underset{B_{3} (g_{3},1)}{\to} & B_{2} . \end{matrix}

I like to think of this as saying that vertical arrows can be “slid around corners” to become horizontal arrows, turning them into the “representable proarrows” $B (1, f)$ or $B (f,1)$ (depending on whether you slid them “backwards” or “forwards” to get around the corner). The bijection is just given by composing with the four special squares defined above. In particular, by a Yoneda argument, for any $f : A \to C$ , $g : B \to D$ , and $K : C ↛ D$ we have

(1)

K (g, f) ≅ C (1, f) ⊙ K ⊙ D (g,1)

so the companions and conjoints determine the rest of the cartesian squares. Note that this is an equipment-version of Yoneda reduction, aka the co-Yoneda lemma. Also, we have a bijection between 2-cells $f \to g$ in $𝒱 (\underset{̲}{X})$ and 2-cells $B (1, f) \to B (1, g)$ in $ℋ (\underset{̲}{X})$ . It follows that the functor $𝒱 (\underset{̲}{X}) \to ℋ (\underset{̲}{X})$ sending $f$ to $B (1, f)$ is locally fully faithful.

Wood’s original definition of an equipment was a functor $K \to M$ between (weak) 2-categories which is bijective on objects, locally fully faithful, and such that the image of each arrow of $K$ has a right adjoint in $M$ . Thus, our definition implies his. The converse is not too hard either, so the two are equivalent. However, I find that the double-category way of thinking makes the structure look much more natural; Wood’s definition looks very ad-hoc to me. The double-categorical approach also (a) automatically gives you a good 2- or 3-category of equipments, which is tricky to do with Wood’s definition (I believe this was first realized by Verity in his thesis), and (b) generalizes better to situations in which the coends that define profunctor composition may not exist. But those are for another day.

Now let me try to convince you that we do formal category theory in an equipment. Let’s start with this: two (vertical) arrows $f : A \to B$ and $g : B \to A$ are adjoint (in $𝒱 (\underset{̲}{X})$ ) if and only if we have an isomorphism $B (f,1) ≅ A (1, g)$ . Why? Well, an adjunction $f ⊣ g$ comes with a unit and a counit, which (expressed in $\underset{̲}{X}$ ) are of the form

\begin{matrix} A & \overset{U_{A}}{\to} & A \\ ^{f} ↓ & ↓ \\ B & \overset{η}{\Leftarrow} & ↓^{id} \\ ^{g} ↓ & ↓ \\ A & \underset{U_{A}}{\to} & A \end{matrix} and \begin{matrix} B & \overset{U_{B}}{\to} & B \\ ↓ & ↓^{g} \\ ^{id} ↓ & \overset{ε}{\Leftarrow} & A \\ ↓ & ↓^{f} \\ B & \underset{U_{B}}{\to} & B . \end{matrix}

Applying the bijection of the central lemma, we see that $η$ corresponds to a map $B (f,1) \to A (1, g)$ , and likewise $ε$ corresponds to a map $A (1, g) \to B (f,1)$ . The triangle identities for $η$ and $ε$ are then equivalent to saying that these two maps are inverse isomorphisms. So we’ve recovered the classical equivalence between the “diagrammatic” and isomorphism-of-hom-sets definitions of an adjunction, in a purely formal way.

Now let’s define limits. I’m not sure who first realized that limits can be defined in the following way, but Ross Street is a good guess. The notion of limit we end up with is actually more general than what you’re probably used to, but this extra generality turns out to be useful. Let $d : D \to C$ be an arrow and let $J : D ↛ A$ be a proarrow; we’re going to define what it means for an arrow $ℓ : A \to C$ to be the $J$ -weighted limit of $d$ . In the equipment $\underset{̲}{V - Prof}$ of $V$ -enriched categories, if $A$ is the unit $V$ -category $I$ , then this will recover the usual notion of weighted limit. Of course, in a general equipment we may not have a “unit object,” so that extra generality is unavoidable; it’s like using generalized elements in ordinary category theory.

To make things easier, let’s assume that $\underset{̲}{X}$ is closed, in the sense that composition of proarrows has adjoints in each variable

ℋ (\underset{̲}{X}) (H ⊙ K, L) ≅ ℋ (\underset{̲}{X}) (H, K ⊳ L) ≅ ℋ (\underset{̲}{X}) (K, L ⊲ H) .

The central lemma implies that analogously to (1), we have

(2)

K (g, f) ≅ D (1, g) ⊳ K ⊲ C (f,1) .

In $V - Prof$ , the adjoints are given by the ends

(K ⊳ L) (b, a) = \int_{c \in C} [K (c, b), L (c, a)]

and

(L ⊲ H) (c, b) = \int_{a \in A} [H (b, a), L (c, a)] .

Therefore, (2) is an abstract form of the Yoneda lemma, just as (1) is an abstract form of the co-Yoneda lemma.

Now recall that for $V$ -categories $D$ and $C$ , an object $ℓ \in C$ is a $J$ -weighted limit of $d : D \to C$ if we have an isomorphism

\begin{aligned} C (-, ℓ) & ≅ [D, V] (J, C (-, x)) \\ = \int_{x \in D} [J (x), C (-, d (x))] . \end{aligned}

Thus it makes sense to define, in a closed equipment, an arrow $ℓ : A \to C$ to be the $J$ -weighted limit of $d$ if we have an isomorphism

C (1, ℓ) ≅ C (1, d) ⊲ J .

(If our equipment is not closed, we simply assert that $C (1, ℓ)$ has the universal property that $C (1, d) ⊲ J$ would have if it existed.) In particular, when $A$ is the unit $V$ -category, this recovers the classical notion. But even in $\underset{̲}{V - Prof}$ there are interesting examples for other values of $A$ . If we take $J = D (j,1)$ for some functor $j : A \to D$ , then (1) and (2) imply that

\begin{aligned} C (1, d) ⊲ J & = C (1, d) ⊲ D (j,1) \\ ≅ j^{*} C (1, d) \\ ≅ D (1, j) ⊙ C (1, d) \\ ≅ C (1, d j) \end{aligned}

so that $ℓ = d j$ is the $J$ -weighted limit of $d$ . That is, $D (j,1)$ -weighted limits are just given by composition with $j$ . But more interestingly, one can show that if $J = D (1, k)$ for some $k : D \to A$ , then $J$ -weighted limits specialize to pointwise right Kan extensions along $k$ . That is, the extra data in an equipment lets us define the good notion of Kan extension (even in the enriched case) as a special case of a general notion of limit.

Amazingly, a huge amount of category theory can be done at this level of generality. I’ll give just one more example (for now): the theorem that right adjoints preserve limits. Suppose that $ℓ : A \to C$ is a $J$ -weighted limit of $d : D \to C$ in the above sense, and let $g : C \to B$ be an arrow with a left adjoint $f : B \to C$ . We want to show that $g ℓ$ is a $J$ -weighted limit of $g d$ . But we have

\begin{aligned} B (1, g ℓ) & ≅ C (1, ℓ) ⊙ B (1, g) \\ ≅ (C (1, d) ⊲ J) ⊙ C (f,1) \\ ≅ C (1, f) ⊳ (C (1, d) ⊲ J) \\ ≅ (C (1, f) ⊳ C (1, d)) ⊲ J \\ ≅ (C (1, d) ⊙ C (f,1)) ⊲ J \\ ≅ (C (1, d) ⊙ B (1, g)) ⊲ J \\ ≅ B (1, g d) ⊲ J . \end{aligned}

which is what we want.

Finally, in the interests of full disclosure, I should say that equipments are not the only way to do formal category theory. A sort-of equivalent approach, due to Street and Walters, is a “Yoneda structure,” which equips a 2-category with “presheaf objects” so that profunctors can be recovered as functors $A \to P B$ . (It’s only “sort-of” equivalent due to differences in how size is dealt with.) Alternately, one can start from a well-behaved 2-category, such as a 2-topos, and construct an equipment or Yoneda structure, in one of several ways, and if one likes one can work only with those constructions without ever saying “equipment” or “Yoneda structure.” But I think that isolating the “proarrow structure” that enables us to do formal category theory is helpful, and can provide useful insights even if we only care about one particular kind of category theory—just like knowing some ordinary category theory can be helpful even if we only care about one particular category.

Steinn Sigurðsson — Qu'est-ce que c'est?

Fa fa fa fa fa fa fa fa fa

Read the rest of this post... | Read the comments on this post...

November 22, 2009

Steinn Sigurðsson — More MOND

It appears to be a MOND autumn in the science glossies, as Science publishes a review on our favourite alternative physics theory and the status of MOND like extensions to general relativity

Read the rest of this post... | Read the comments on this post...

Cosmic Variance — Wechsler’s Index

My last 10 days (posted after a recovery weekend), by the numbers:

Shuttle launches witnessed: 1
Shuttle launches since 1981: 129
Shuttle launches remaining: 5
“Shuttle Experience” rides experienced: 1

Cost of Space Shuttle Atlantis [dollars]: 1.7 billion
Total cost of the International Space Station [dollars]: 157 billion
Science publications resulting from research by the International Space Station: ~200
Total cost of the Hubble Space Telescope [dollars]: ~4-6 billion
Science publications resulting from Hubble Space Telescope data: >8500

Years between first trans-Atlantic air passenger and first man walking on Moon: 42
Years since last human walked on moon: 37
Moons of earth where water was found: 1

Cities visited, where snow was visible: 2
Cities visited, where it has never snowed: 2
Cities visited with a “Disney Land/World”: 2
Mickeys seen: 0
Alligators seen: 2
Geckos seen: 1
Astronauts met: 1
Space geeks met: ~ 40

Tweets sent at first “tweetup”: 24
Tweets sent in lifetime: 24
Number of distinct words heard starting with an extraneous “tw”: >15
Days after my first tweet that Palin decided to resume tweeting: 4
Books released by Sarah Palin: 1
Stewardesses I saw that were the spitting image of Sarah Palin: 1

Oceans swum in: 1
Oceans I was close enough to swim in: 2
Places visited that are the Holiest site of a religion: 1
People met that are writing a book about escaping that religion: 1
Points bowled: 67
Team place out of nine teams of bowling scientists: 1st

Flights taken: 7
Amount of carbon emitted by those flights [lbs]: 2240
Net amount of energy generated by my solar panels [kW/hrs]: ~100
Equivalent amount of carbon not emitted [lbs]: 100
Cost of offsetting that 2240 lbs of carbon [dollars]: 12.63

Talks given on completely different topics: 3
Talks listened to: 41
Talks listened to without my laptop open: 15
Non-astrophysics talks I heard that mentioned dark matter: 10

NSF proposals submitted (as Co-PI): 2
HST Multi-Cycle Treasury proposals submitted (as Co-I): 2
Total number of HST MCT proposals submitted by the community: 39
Total number of HST orbits requested by those 39 proposals: 26801
Interviews given: 3
Days with at least 3 nearly identical deadlines: 2

Emails received @ work address: 768
Emails sent: 253
Emails still in my inbox: 361

Average number of hours slept per night: 5
Brain cells lost by multi-tasking: Uncountable.

by Risa at November 22, 2009 09:56 PM

Chad Orzel — How to Teach Physics to Your Dog is a Real Book!

Look! How to Teach Physics to Your Dog is a real book:

Emmy says, very seriously, "You will buy a copy, won't you?"

Of course, like everything else in this house, SteelyKid had to grab a copy:

Read the rest of this post... | Read the comments on this post...

Cosmic Variance — IPMU in Tokyo Needs Support

Japan has had a long and distinguished tradition in modern physics. Just to pick one example, the amazing efforts of Shin’ichirō Tomonaga to understand quantum electrodynamics, anticipating the work of Schwinger and Feynman while remaining essentially isolated from the rest of the world during World War II. More recently, Japan has continued to do forefront experimental work, including the SuperKamiokande neutrino detector and the Belle particle physics experiment at KEK. Nevertheless, in my own areas of physics — theoretical particle physics and cosmology — Japan hasn’t had a relatively low institutional profile. There are great individual physicists, but not any one institution of theoretical physics that really rose to the level of other great international places — a place where scientists around the world would naturally think of to spend a sabbatical or send their students as postdocs.

That all changed rather dramatically in recent years, with the founding of the Institute for Physics and Mathematics of the Universe at the University of Tokyo. The IPMU was one of the World Premier International Research Centers that were founded in Japan in 2007, to foster excellence in research but especially to lower barriers between Japan and the rest of the world. The IPMU acted aggressively to hire scientists from outside Japan and host programs that would bring visitors from around the world. And the effort succeeded, with astonishing swiftness; I know that among people I talked to, IPMU was quickly recognized as an attractive place to go with top-notch scientists working there. You can see the results through one person’s eyes at the blog of Susanne Reffert, one of IPMU’s postdocs.

Now all of that success is in jeopardy. As detailed in this letter from Hitoshi Murayama, founding director of the IPMU, the new government in Japan “is actively trying to slash support for programs in science,” and the IPMU is one of the targets. New commissions (staffed by non-experts) have been tasked with reviewing a wide spectrum of programs, and recommending everything from 30% cuts to 50% cuts to outright termination. These cuts are extending throughout science, although new efforts like the World Premier centers are in particular danger.

Admittedly, we live in a time when budgets are tight, and nobody is going to completely escape the pain of the current global economic crisis. But this would be a very short-sighted move on the part of Japan, to undo the great strides they had made in connecting with the international effort in fundamental physics.

Fortunately, there’s something you can do! Hirosi Ooguri here at Caltech informs me that the Japanese Ministry of Education and Science is actually soliciting input from the worldwide scientific community. You can send an email to “nak-got [at] mext.go.jp”, with a subject line “No. 14, WPI.” That will reach people who matter, including Senior Vice Minister Masaharu Nakagawa and Vice Minister Hitoshi Goto.

It would mean a lot if the Japanese government understood how much the rest of the world appreciates the close connections with scientists in their country. Science is not a zero-sum game; when it’s succeeding somewhere, everyone benefits. Here’s hoping the IPMU makes it through this episode intact, and continues to flourish in the future.

by Sean at November 22, 2009 02:47 PM

US/LHC Blog — Waiting for Collisions

It has been a very exciting weekend with proton beams in the LHC day and night, but it was still only the warmup. Now we are eagerly awaiting the first collisions. Then we will really have begun the LHC era.

But we are not just sitting and waiting for collisions. I have spent most of the weekend looking at the data collected so far, and based on the email traffic so have many others. My conclusion is that the ATLAS detector is performing extremely well.

Besides the quality, what has impressed me is how quickly the data has been made available around the world, and how well all the software to analyze it has worked. This is not a big surprise to me since these are some of the things we have used the last year to improve, but it is nice to see it all work so well.

Just in case you haven’t seen them, teams have been scanning the data and making event displays.

Now that the LHC and the detectors have done everything that was done last year (and more), we can finally move on to what we have really been waiting for, collisions!

by Adam Yurkewicz at November 22, 2009 02:23 PM

Doug Natelson — Graphene, part II

One reason that graphene has comparatively remarkable conduction properties is its band structure, and in particular the idea that single-particle states carry a pseudospin. This sounds like jargon, and until I'd heard Philip Kim talk about this, I hadn't fully appreciated how this works. The idea is as follows. One way to think about the graphene lattice is that it consists of two triangular lattices offset from each other by one carbon-carbon bond length. If we had just one of those lattices, you could describe the single-particle electronic states as Bloch waves - these look like plane waves multiplied by functions that are spatially periodic with reference to that particular lattice. Since we have two such lattices, one way to describe each electronic state is as a linear combination of Bloch states from lattice A and lattice B. (The spatial periodicity associated with lattice A (B) is described by a set of reciprocal lattice vectors that are labeled K (K'))

Here is where things get tricky. The particular linear combinations that are the real single-particle eigenstates can be written using the same Pauli matrices that are used to describe the spin angular momentum of spin-1/2 particles. In fact, if you pick a single-particle eigenstate with a crystal momentum \hbar k, the correct combination of Pauli matrices to use would be the same as if you were describing a spin-1/2 particle oriented along the same direction as k. This property of the electronic states is called pseudospin. It does not correspond to a real spin in the sense of a real intrinsic angular momentum. It is, however, a compact way of keeping track of the role of the two sublattices in determining the properties of particular electronic states.

The consequences of this pseudospin description are very interesting. For example, this is related to why back-scattering is disfavored in clean graphene. In pseudospin language, a scattering event that flips the momentum of a particle from +k to -k would have to flip the pseudospin, too, and that's not easy. In non-pseudospin language, that kind of scattering would have to change the phase relationship between the A and B sublattice Bloch state components of the single-particle state. From that way of phrasing it, it's more clear (at least to me) why this is not easy - it requires rather deep changes to the whole extended wavefunction that distinguish between the different sublattices, and in a clean sample at T = 0, that shouldn't happen.

A good overview of this stuff can be found here (pdf) in this article from Physics Today, as well as this review article. Finally, Michael Fuhrer at the University of Maryland has a nice powerpoint slide show (here) that discusses how to think about the pseudospin. He does a much more thorough and informative job than I do here.

by Doug Natelson at November 22, 2009 01:46 PM

Clifford Johnson — Coming Around the Bend Again

It was in the news today, I’m told*. The LHC is circulating beams again!! This is exciting news indeed. Look out for a press conference on Monday, and here is a press release about the event that took place yesterday. Also, collisions are said to be going to happen next week! This is all very wonderful. I'm mid-travel, and should be sleeping for an early start tomorrow, and so I'll simply point over to [...]

by Clifford at November 21, 2009 07:44 PM

Clifford Johnson — Here, There, and Everywhere

Well, it has been quite the week so far. I've been mostly in England. First I spent Tuesday getting over the main effects of jetlag and a short but strong cold (both more or less gone now), and then Wednesday I went to King's College London to give a seminar to the three groups in the Triangle series of seminars - King's, Imperial, Queen Mary are the three places the participating research groups in theoretical high energy physics come from. It was excellent to see so many old friends and colleagues, meet some new ones, and chat physics at the pub and over dinner later on. The seminar seemed to be well received, although I know I was far from my best, given jetlag and cold. The next two days saw me saying hi to family and friends at coffee and dinner in the evenings and visiting at Queen Mary and Imperial for the day, and hiding in the British Library for most of Friday, writing. What am I writing? Four lectures on D-branes and string theory and M-theory, with a focus on some of the fun and instructive applications (and potential applications) of [...]

by Clifford at November 21, 2009 07:26 PM

Tim Gowers — Problems related to Littlewood’s conjecture

This is the third in a series of posts in which I discuss problems that could perhaps form Polymath projects. Again, I am elaborating on a brief discussion that appeared in an earlier post on possible future projects. [Not for the first time in my experience, WordPress's dates have gone funny and this was posted not on the 17th as it says above but on the 20th.]

An obvious objection to the Littlewood conjecture as a Polymath project is that it is notoriously hard. On its own that might not necessarily be a convincing argument, since part of the point of Polymath is to attempt to succeed where individual mathematicians have failed. However, a second objection is that the best results in the direction of the Littlewood conjecture, due to Einsiedler, Katok and Lindenstrauss, use methods that are far from elementary (and far from understood by me). I envisage this project as an elementary one, at least to begin with, so does that make it completely unrealistic? I shall try to argue in this post that there is plenty that could potentially be done by elementary methods, even if attempting to prove the conjecture itself is probably too ambitious.

Another advantage of tackling the conjecture by elementary means is that if we find ourselves forced to reintroduce the non-elementary methods that have led to the very interesting results of Einsiedler, Katok and Lindenstrauss, we will have a deeper understanding of those methods than if we had just passively learnt about them. I myself prefer to rediscover things than to learn them: it isn’t always practical, but it’s easier if you half bear in mind that they are there and have a vague idea about them.

Still on the topic of elementary versus non-elementary, one of the factors that contributed to the success of the DHJ project was that there was a non-elementary way of looking at the problem that we were trying to solve by elementary means. That meant that those participants who knew their ergodic theory could look at proposed proof strategies and make useful comments about whether they were likely to succeed. I think of it as like trying to find one’s way out of a jungle. The non-elementary methods give you something like a satellite picture of your surroundings, which enables you to plan your route instead of wandering around in the dense vegetation with no idea where you are. But there are things that the satellite picture won’t show, such as narrow but useful paths. So sometimes the person with the satellite picture knows that the person without it is wasting time, but sometimes there are important ideas that the person with the satellite picture will not spot. With a collaboration, one can of course have the best of both worlds.

For those who are interested, there is a very nice survey article by Akshay Venkatesh about the work of Einsiedler, Katok and Lindenstrauss, which explains how dynamics comes into the problem.

Before we discuss Littlewood’s conjecture, let us look at an easier question. Suppose that $\alpha$ is a real number. To what extent can the multiples of $\alpha$ stay away from integers? To make this question precise, let us write $\|x\|$ for the distance from $x$ to the nearest integer. Then we would like to examine the sequence $\|\alpha\|, \|2\alpha\|, \|3\alpha\|,\dots$ .

Before thinking about the right question to ask, let us quickly prove a simple and very well-known theorem. (Unless my history is letting me down, which is possible, it is due to Dirichlet.)

Theorem 1. For every real number $\alpha$ and every positive integer $n$ there exists a positive integer $m\leq n$ such that $\|m\alpha\|\leq n^{-1}$ .

Proof. Let $\beta$ be chosen uniformly at random from the interval $[0,1)$ . Then the expected number of numbers in the sequence $0,\alpha,2\alpha,\dots,n\alpha$ that lie in the interval $[\beta,\beta+n^{-1})$ mod 1 is $1+n^{-1}$ . Therefore, there must exist $\beta$ and $0\leq s<t\leq n$ such that both $s\alpha$ and $t\alpha$ lie in the interval $[\beta,\beta+n^{-1})$ mod 1, from which it follows that $\|\alpha(t-s)\|\leq n^{-1}$ . QED

Note (i) that Dirichlet used the pigeonhole principle rather than an averaging argument and (ii) that we could, if we had been bothered, have obtained a bound of $(n+1)^{-1}$ from the above argument. (This illustrates the point, which is often handy, that even if partitioning a set $X$ into subsets of a certain form is hard — not that it is here — finding subsets $Y_1,\dots Y_M$ of that form such that every element of $X$ is in the same number of $Y_i$ may well be easy. In that case, something very similar to the pigeonhole principle works. I should expand this parenthetical remark into a Tricki article.)

What this argument shows is that sometimes $\|\alpha m\|$ must be small. Since it clearly won’t stay small (at least if $\alpha\ne 0$ ), this suggests that we should be interested in the sequence $c(n,\alpha)=\min_{1\leq m\leq n}\|\alpha m\|$ . And the obvious question then is: how fast must (or how slowly can) $c(n,\alpha)$ tend to $0$ as $n$ tends to infinity?

The argument above shows that $c(n,\alpha)\leq n^{-1}$ , and this is asymptotically best possible, because it is not hard to show that if $\alpha$ has a continued fraction with bounded quotients then $c(n,\alpha)\geq an^{-1}$ for some positive constant $a$ (that depends on the upper bound of those terms). In particular, if $\alpha$ is a quadratic irrational, then $\|\alpha n\|$ is at least $an^{-1}$ for every positive integer $n$ .

This suggests that the slowest possible rate at which $c(n,\alpha)$ can tend to zero is achieved when $\alpha$ is the golden ratio, and that is indeed the case. So this problem is completely understood: basically, the continued fraction expansion of $\alpha$ tells you exactly how $c(n,\alpha)$ behaves.

Littlewood’s conjecture is about what at first seems to be an innocent generalization of the above result. Instead of looking at one real number $\alpha$ , let us look at two, $\alpha$ and $\beta$ . In broad terms, our goal is to understand to what extent it is possible for both $\|\alpha n\|$ and $\|\beta n\|$ to be reasonably large. The precise question that Littlewood asked is (equivalent to) the following.

Problem 2. Let $\alpha$ and $\beta$ be real numbers, and for each $n$ define $c(n,\alpha,\beta)$ to be $\min_{1\leq m\leq n}\|m\alpha\|\|m\beta\|$ . Must $c(n,\alpha,\beta)$ tend to zero faster than $n^{-1}$ ?

By “faster”, I mean at a rate $o(n^{-1})$ . Littlewood conjectured that the answer was yes. A more usual way of formulating the conjecture is as the statement that $\lim\inf_n n\|\alpha n\|\|\beta n\|=0$ , which is obviously equivalent to a positive answer to Problem 2.

Since $c(n,\alpha,\beta)\leq c(n,\alpha)$ , it is trivial that $c(n,\alpha,\beta)$ tends to zero at least as fast as $n^{-1}$ , and the only way that it could fail to tend to zero faster than that is if $\beta n$ magically stays away from an integer whenever $\alpha n$ threatens to get close, and vice versa.

One question that it is reasonable to ask is the following: why, when we are considering the question of whether $(\alpha n,\beta n)$ can remain far from a pair of integers, do we multiply together $\|\alpha n\|$ and $\|\beta n\|$ ? Is that really a natural thing to do? I shall come back to this question, but for now let me remark (slightly cryptically) that this formulation leads to symmetries that are critical to the work that has been done on it.

A more general question.

Theorem 1 leads to the following nice construction of a set $X$ of $n$ points in $[0,1]^2$ such that if $(x_1,y_1)$ and $(x_2,y_2)$ are distinct elements of $X$ , then $|x_1-x_2||y_1-y_2|\geq cn^{-1}$ . (Note that this is best possible, since just $|x_1-x_2|$ must sometimes be at most $(n-1)^{-1}$ .) One takes $(x_r,y_r)$ to be $(r/n,\alpha r)$ , where $\alpha r$ is reduced mod 1 and $\alpha$ is a number with bounded quotients in its continued-fraction expansion (or, if you prefer, $\alpha$ is something concrete like $\sqrt{2}$ ).

Why does this work? Well,

$\displaystyle |x_r-x_s||y_r-y_s|=n^{-1}|r-s|\Bigl|\|\alpha r\|-\|\alpha s\|\Bigr|$

$\displaystyle \geq n^{-1}|r-s|\|\alpha(r-s)\|\geq cn^{-1},$

by our choice of $\alpha$ .

This shows that we can use a quadratic irrational, or any “counterexample to the one-dimensional analogue of the Littlewood conjecture”, to produce a set of points with the desired property. Let us define the “distance” between two points $(x_1,y_1)$ and $(x_2,y_2)$ to be $|x_1-x_2||y_1-y_2|$ , noting that this is very definitely not a metric. Then what we have produced is $n$ points in the unit square such that any two have distance at least $cn^{-1}$ from each other.

Can we do this in three dimensions? This time, we define the “distance” between $(x_1,y_1,z_1)$ and $(x_2,y_2,z_2)$ to be $|x_1-x_2||y_1-y_2||z_1-z_2|$ . Let me ask this question as a serious problem.

Problem 3. Is there a constant $c>0$ such that for every $n$ it is possible to find $n$ points in $[0,1]^3$ such that the distance between any two of them (as defined above) is at least $cn^{-1}$ ?

The reason for asking this question is the following simple observation.

Observation 4. If there is a counterexample to Littlewood’s conjecture, then the answer to Problem 3 is yes.

Proof. We generalize the two-dimensional construction in the obvious way, by defining $(x_r,y_r,z_r)$ to be $(r/n,\alpha r,\beta r)$ . Again, $\alpha r$ and $\beta r$ are reduced mod 1, and $(\alpha,\beta)$ is a pair of real numbers such that $n\|\alpha n\|\|\beta n\|$ is bounded below by a positive constant $c$ . Checking that this works is straightforward. QED

What is the point of asking this question? Well, one reason is that it is clearly very closely related to Littlewood’s conjecture, but it is far more general. Therefore, if such a set of points does exist, then it should be easier to find it than to find a counterexample to Littlewood’s conjecture, whereas if it doesn’t exist, then proving that it doesn’t exist might also be easier (because now it would be a purely combinatorial problem rather than a number-theoretic one).

Unfortunately, there are objections to the above arguments. It seems to be very hard to find a set of well-separated points in three dimensions (I’ll discuss what one can do in a moment), and part of the reason is that there are $cn^2$ pairs of points to worry about. So it is tempting to introduce dependences, by which I mean to come up with a construction such that if one pair of points is separated it causes many other pairs to be separated as well. But that thought leads one inexorably to the idea that the best approach could be to start by finding a counterexample to the Littlewood conjecture … (This is an issue that I have discussed before on this blog. Sometimes combinatorial generalizations seem to be no easier to tackle than the problems they generalize.)

If finding an example of a collection of well-separated points turns out not to be easier to think about than finding a counterexample to Littlewood’s conjecture, what about trying to prove that such a collection cannot exist? Formally speaking, it is of course harder, but if such a collection cannot exist, then it could be that to prove it one is forced to think about the problem in the correct, more general way. I’m not sure how I feel about this. I have no decent idea about how to go about proving that a well-separated collection doesn’t exist, and if I attempt to do so there is always a little imaginary voice saying to me, “If you managed to prove this, then you’d have shown the highly non-trivial (indeed, not known) number-theoretic fact that $\lim\inf n\|n\sqrt{2}\|\|n\sqrt{3}\|=0$ .” Do I believe that such a fact might conceivably be provable by much more general combinatorial techniques? It seems like a long shot, but I can’t think of a good reason for its being impossible.

Incidentally, it is easy to find $n$ points that are separated by $c(n\log n)^{-1}$ . There are two (ultimately not all that different) ways of doing this. One is just to choose any old maximal separated set of points. The set of points at distance at most $\delta$ from any given point has volume at most $\delta\log(1/\delta)$ or thereabouts, so if $\delta$ is $(n\log n)^{-1}$ then this is about $1/n$ , so you can fit $n$ points in before there is any chance of the set being maximal. The other way of doing it is to choose the points randomly until the expected number of pairs that are too close exceeds half the number of points. You then throw away one point from each pair. This uses exactly the same volume calculation (since the volume of points close to $x$ is the probability that $y$ gets too close to $x$ ) and gives essentially the same bound.

But the weakness with those arguments is that they don’t exploit the fact that the “distance” is not in fact a metric and the “ball” around a point is far from convex. The greedy approach takes no account of the fact that the balls around the points could overlap considerably — all the more so if you try to choose the points in order to make this happen. However, I know of no better argument. (Of course, in the two-dimensional case I have just given a better argument, but that doesn’t help us.)

A variant of Problem 3.

One of the difficulties in thinking about Problem 3 is that we do not have a big supply of examples in the two-dimensional case. However, there is another construction that doesn’t quite work, but “morally” does work, which goes as follows. For convenience, let $n=2^k$ and take all points of the form $(a,b)\in[0,1)$ such that both $a$ and $b$ have binary expansions that terminate after exactly $k$ digits (if necessary, one should add zeros to achieve this) and the digit sequence for $a$ is the reverse of the digit sequence for $b$ . For example, if $n=16$ then one of the points is $(0.1101,0.1011)$ in binary.

Why should this work? Well, for two distinct points to have $x$ coordinates that are very close, they will have to differ in some late digit, which means that their $y$ coordinates will have to differ in an early digit. More precisely, if the $x$ coordinates first differ in the $(k+1-j)th$ digit, then the $y$ coordinates differ at or before the $j$ th digit, so the product of the differences should be at least $2^{-(k+1-j)}2^{-j}=n^{-1}/2$ .

So why doesn’t it work? Unfortunately, that argument makes the elementary blunder of assuming that if two numbers differ in an early digit, then they must be far apart. But the example of $0.1000000$ and $0.0111111$ shows that that is false. And if we take the numbers $0.10000001$ and $0.01111110$ then we have two numbers such that both they and their reversals are close.

I mentioned this to Nets Katz once, and he came up with the suggestion of changing the metric to a dyadic one. That is, we define the distance between two numbers in $[0,1)$ to be $2^{-j}$ if they first differ in the $j$ th digit. With this definition, which is in some ways more natural than the “real” metric on $[0,1)$ , the digit-reversal construction works.

That may feel a bit like cheating, but if that’s the way you feel, then have a go at the next question, and also read on to the end of the next section.

Problem 5. Is it possible to find $n$ points in $[0,1)^3$ such that if $(x,y,z)$ and $(x',y',z')$ are any two of them then $d(x,x')d(y,y')d(z,z')\geq c/n$ ?

Of course, one wants to do this for all $n$ and an absolute constant $c>0$ .

I have a hazy memory that Nets Katz and I managed to find such a set when we discussed this problem, but I’m not quite sure whether that memory is correct. In any case, I don’t have an example at my fingertips right now and it could be a good place to start. (It could be that what I am remembering is something else, namely a way of modifying the digit-reversal construction so that it works for the usual metric. Added later: I now think that that is indeed what I was remembering, since I have reconstructed the modification. See below.) Note that the dyadic distance between any two numbers is at least half the actual distance, so if one could prove that no dyadic-separated set existed, one would have proved Littlewood’s conjecture. (Added later still: I have now found a dyadic-separated set. See the sixth comment below. I don’t remember it from before, but neither am I certain that it is new. Added later still: on further reflection, it does feel faintly familiar. Nets, if you ever read this, does the example ring any bells with you?)

While I am at it, here is a general question.

Problem 6. Does the Littlewood conjecture, or indeed any of the related problems discussed here, become easy if the dimension is sufficiently high?

For example, if $\alpha_1,\dots,\alpha_{100}$ are real numbers, is it known that $\lim\inf n\|n\alpha_1\|\dots\|n\alpha_{100}\|=0$ ? I think it may be but I have not found it by Googling. Problem 6 is potentially important in the context of the dyadic problem: if the answer to Problem 5 turns out to be yes (as I vaguely remember), then we do not have a proof of Littlewood’s conjecture. But it could be that the answer to a sufficiently high-dimensional analogue of Problem 5 is no, in which case one would have a combinatorial proof of a high-dimensional version of Littlewood’s conjecture.

Are the two constructions related?

We now have two ways of producing well-separated subsets of $[0,1)^2$ (one of them by changing the metric): using a quadratic irrational, and the digit-reversal idea. However, these two methods may be less different than they at first appear. To see this, let us consider what happens if we try to produce an example using the golden ratio, except that to keep the discussion finite we shall use a good approximation to it of the form $F_{n-1}/F_n$ , where $F_{n-1}$ and $F_n$ are consecutive Fibonacci numbers. In fact, let us go further and take $8/13$ . What’s more, let us make our points live in the grid $\{0,1,\dots,12\}^2$ rather than in $[0,1)^2$ . Thus, we shall take the set of all multiples of $(1,8)$ mod 13. These are $(1,8), (2,3), (3,11),(4,6),(5,1),(6,9)$ , $(7,4),(8,12),(9,7),(10,2),(11,10),(12,5)$ . Note how beautifully these points behave themselves: when one of them is close to $0$ (mod 13) then the other one stays away.

How can we connect this with digit-reversal? Obviously we do not want to take base-ten representations. The natural base if we are thinking about Fibonacci numbers is … to write numbers as sums of Fibonacci numbers. To make the representation unique, we forbid the use of consecutive Fibonacci numbers (it is an easy exercise to check that this gives a unique representation). An easy algorithm for working out the representation is to keep subtracting the largest Fibonacci number that is less than what you have: for instance, 12=8+4=8+3+1 and there is our representation. There is a small issue that needs to be sorted out: the number 1 occurs twice, so are 1 and 2 consecutive Fibonacci numbers? I shall use the algorithm just described, so I shall never need the first 1. Thus, I regard 1 and 2 as consecutive.

Let us write our numbers as we would in base 10: with the largest term at the left. If we do that, and if we put zeros at the beginnings of numbers, then the points above work out to be $(00001,10000),(00010,00100),(00100,10100),$ $(00101,01001),(01000,00001),(01001,10001),$ $(01010,00101),(10000,10101),(10001,01010),$ $(10010,00010),(10100,10010),(10101,01000)$ .

The first thing to say is that we are clearly not reversing the digits here. And yet, if one looks more closely, then one starts to see patterns emerging: there seems to be a mixture of digit-reversal and moving “blocks” of numbers around. To see what I mean here, look at what happens if we take the multiples of 8 and reverse their Fibonacci digits. The resulting sequence is this: 1,3,4,10,8,9,11,12,7,5,6,2. Let us throw in 0 at the beginning of the sequence and imaginine it arranged in a cycle. Now we can partition this cycle into two chunks, one of length 5 and one of length 8. These chunks are (7,5,6,2,0,1,3,4) and (10,8,9,11,12). The first chunk naturally splits up as (7,5,6) and (2,0,1,3,4), which again consists of permutations of intervals of Fibonacci lengths. And the second does too: it splits up as (10,8,9) and (11,12). And we can keep doing this. For example, (7,5,6,2,0,1,3,4) splits up into (7,5,6) and (2,0,1,3,4), and so on.

It should be fairly easy to describe exactly what is going on here and prove that it always happens, but I have not got round to doing so. What I would like to see is this. First, there should be a simple algorithm that tells you how to unscramble the sequence of digit-reversed numbers by iterating the following process — take a sequence of numbers of Fibonacci length, divide it into two subintervals of Fibonacci length and possibly swap them round (but not always, so one would need to know when, and also when the longer interval comes first) — until you get down to singletons. The second thing should be a direct combinatorial proof that if you do this process in reverse, then you will get a sequence of numbers such that nearby terms in the sequence have reversals that are far away.

Note that it was obvious in advance that we would not get digit-reversal, because the Fibonacci base is subject to the same problem that the binary base was: it is possible for two numbers to be close and for their digit-reversals to be close. But this is interesting, as it suggests that if we understand what is going on combinatorially in the above patterns, then we might be able to come up with a flexible construction that uses digit reversal but cleverly modifies it to get round the nought-point-one-recurring difficulty. More generally, it suggests that thinking about the dyadic problem could give useful insights into the original problem.

Added later: after editing the above (to add the description of the interesting pattern that appears when you multiply by 8 and reverse the Fibonacci digits), I realized that it is indeed possible to mimic what is going on there and deal with the nought-point-one-recurring difficulty. This gives rise to a construction that is probably what Nets Katz and I came up with when we discussed the problem (about eight years ago), though it is certainly not how we came up with it.

What I want to do is construct a sequence of pairs of points $(a_i,b_i)$ such that both $a_i$ and $b_i$ live in $[0,1)$ and have $k$ binary digits. I also want $|a_i-a_j||b_i-b_j|$ to be at least $c2^{-k}$ whenever $i\ne j.$ Digit reversal doesn’t work, but what about a combination of digit reversal and “sometimes exchanging clumps”? The most obvious idea would be to organize the $a_i$ into a binary tree, and then go down the levels of this tree, alternately not swapping and swapping. That is, I let $a_i=i/2^k$ for every $0\leq i\leq 2^{k-1}$ . The first level of the tree is the partition into two intervals according to the first digit of $a_i$ . So I do that partition and then don’t swap the intervals. At the second level, I do swap the intervals, so now I have four intervals in the following order: numbers that start 01, numbers that start 00, numbers that start 11, numbers that start 10. I continue this process.

The resulting order will be what you get if you take each number, change every other binary digit, and then put the numbers in increasing order. Let $\phi$ be the map that changes every other binary digit of a number and let $\rho$ be the map that reverses the digits. Then the set of points I want to take is the set of all $(\phi(a),\rho(a))$ such that $a$ is of the form $i/2^k$ .

Why does this work? Well, if $a$ and $a'$ first differ in the $j$ th binary place, then $\rho(a)$ and $\rho(a')$ differ in the $k+1-j$ th place and are identical after that. Therefore, $|\rho(a)-\rho(a')|\geq 2^{-k}2^j/2.$ The only way that this can fail to help is if $\phi(a)$ and $\phi(a')$ are much closer than $2^{-j}$ . Now if $\phi(a)$ is greater than $\phi(a')$ , then this means that the $j$ th digit of $\phi(a)$ must be a 1 and several subsequent digits are 0, while the $j$ th digit of $\phi(a')$ is a 0 and several subsequent digits are 1. But then $a$ and $a'$ have alternating 0s and 1s after the $j$ th digit, and in different places. If the lengths of these strings of alternating digits are around $t$ , then it is not hard to see that $\rho(a)$ and $\rho(a')$ must differ by at least $c2^t2^{-k}2^j,$ basically because they now differ in the $k+1-j-t$ th place and are not followed by strings of 0s and 1s after they first differ.

Conclusion: digit reversal and shifting intervals can combine to give a second example of a well-separated subset of $[0,1)^2$ with respect to the Euclidean metric (in each coordinate) rather than the dyadic metric. The rough reason this works is that the digit-reversal $\rho$ almost works, but fails because of the nought-point-one-recurring problem, while $\phi$ takes numbers that are “close when they shouldn’t be” and pulls them apart. (Of course, $\phi$ then has to bring together numbers that used to be far apart, but this turns out not to matter because the images of those numbers under $\rho$ turn out to be sufficiently far apart to compensate for it.)

More variants.

Returning to Littlewood’s conjecture itself, there is a substantial weakening of it that I still do not know how to answer, though I think it has a good chance of being known and would be interested to hear from anyone if they do know the answer, though in an ideal world I would prefer to come up with an answer for myself (where “for myself” really means “by thinking about it in collaboration with other Polymath participants”). (Added later: I have now found a paper that makes it clear that the question I am about to ask is indeed a known result. I will give the reference at the end of this section.) As I have already mentioned, one of the difficulties of Littlewood’s conjecture is that the function $d(x,y)=|x_1-y_1||x_2-y_2|$ is not a metric. This is why the usual techniques for solving packing problems (up to a constant) fail for Problem 3. However, suppose we know that the ratio of $|x_1-y_1|$ to $|x_2-y_2|$ is roughly $C$ to $1$ . Then $|x_1-y_1||x_2-y_2|$ is roughly $C^{-1}|x_1-y_1|^2$ , which is roughly $C^{-1}\max\{|x_1-y_1|,C|x_2-y_2|\}^2$ , which equals $\max\{C^{-1/2}|x_1-y_1|,C^{1/2}|x_2-y_2|\}^2.$

Let $k\approx\log_2n$ and for each $j$ between $-k$ and $k$ let us write $d_j(x,y)=\max\{2^{-j/2}|x_1-y_1|,2^{j/2}|x_2-y_2|\}$ . Then it is not hard to check that $d(x,y)\approx\min_{-k\leq j\leq k}d_j(x,y)^2$ .

Therefore, if $(\alpha,\beta)$ were a counterexample to Littlewood’s conjecture and $n=2^k$ , it would have to be the case that for every $j$ between $-k$ and $k$ the numbers $m d_j(\|\alpha m\|,\|\beta m\|)^2$ were bounded below by some $c>0$ . In particular, this would need to be the case when $j=0$ , which would say that the numbers $m\max\{\|\alpha m\|,\|\beta m\|\}^2$ were bounded below. This motivates the following weak version of Littlewood’s conjecture.

Problem 7. Do there exist real numbers $\alpha$ and $\beta$ such that $\lim\inf m^{1/2}\max\{\|\alpha m\|,\|\beta m\|\}>0$ ?

Here is what this problem is asking geometrically. For each $n$ the points $(\alpha m,\beta m)$ (mod 1) with $1\leq m\leq n$ form a subset of $[0,1)^2$ of size $n$ . A trivial volume argument shows that there must be two of these points within a distance of $n^{-1/2}$ . Problem 7 asks whether there is some pair $(\alpha,\beta)$ such that this trivial upper bound is correct up to a constant for every $n$ . Thus, there is not much room to play around, but neither is there in the one-dimensional case and yet numerous examples exist. Here is a somewhat vaguer problem.

Problem 8. If the answer to Problem 7 is yes, then is there some general procedure, analogous to picking a continued fraction with bounded exponents, that yields a large family of examples?

One might think that if the answer to Problem 7 is yes, then the answer to Problem 8 is almost certainly yes as well. But it does not seem to be all that easy to generalize continued fractions in the appropriate way. (Of course, many people have tried to produce higher-dimensional generalizations of continued fractions, and it is possible that out there is just what would be needed.)

Another indication that the Littlewood conjecture is hard is that it is not known even in very concrete cases such as $\alpha=\sqrt{2}$ and $\beta=\sqrt{3}$ , as I have already mentioned. This means that a positive solution to the conjecture would have serious number-theoretic content. However, it might be worth thinking about whether a concrete pair of numbers like this could work for Problem 7. (Added later: this too seems to have been done.)

Here is another problem, which I think of as a “dual” version of Littlewood’s conjecture. I will try to justify this name in a moment. (Added later: it turns out that dual problems such as the ones I am about to mention have been considered in the literature as well, and they are dual in a much more direct, though closely related, sense than the one that I talk about.)

Problem 9. Do there exist real numbers $\alpha$ and $\beta$ such that $\lim\inf (r+1)(s+1)\|r\alpha+s\beta\|>0$ ?

The lim inf there is over all pairs of non-negative integers $r$ and $s$ of which at least one is positive. Again, if an example exists then it is best possible, since out of all the numbers $r\alpha+s\beta$ with $r,s\leq n^{1/2}$ there must be two, $r\alpha+s\beta$ and $t\alpha+u\beta$ , that differ by at most $n^{-1}$ . The difference between this and Littlewood’s conjecture is that we are taking a two-dimensional collection of points in $[0,1)$ rather than a one-dimensional collection of points in $[0,1)^2$ .

This problem also has a weak version.

Problem 10. Do there exist real numbers $\alpha$ and $\beta$ such that $\lim\inf \max\{r,s\}^2\|r\alpha+s\beta\|>0$ ?

What is “dual” about these problems? I’ll give an informal argument here: yet another aspect of this project would be the question of whether the argument can be turned into a formal argument for equivalences, or at least one-way implications, between these problems and some of the earlier ones.

Let us begin with the weak versions. Problem 7 asks for $\alpha$ and $\beta$ such that one of $\|r\alpha\|$ and $\|r\beta\|$ is always at least $cm^{-1/2}$ whenever $r$ is a positive integer less than $m$. Let us simplify things a bit by taking $n$ to be a prime number and trying to find $a$ and $b$ mod $n$ such that at least one of $ra$ and $rb$ lies outside the interval $[-cn/m,cn/m]$ whenever $0<r\leq m$ .

Now for any given $m$ there are two sets of interest here. One is the set of $r$ such that $ar\in [-cn/m,cn/m]$ , and the other is the set of $r$ such that $br\in [-cn/m,cn/m]$ . We would like the intersection of these two sets, which are equal to $a^{-1}[-n/m,n/m]$ and $b^{-1}[-n/m,n/m]$ , to be the trivial one, namely $\{0\}$ . If that happens, then we cannot find $r$ in $[1,m]$ with $ar$ and $br$ in the interval $[-cn/m,cn/m]$ .

Here is where I will get very informal. Heuristically speaking, the Fourier transform of a set such as $a^{-1}[-k,k]$ behaves like an arithmetic progression of common difference $a$ and length $n/k$ . (There are all sorts of tricks for making this heuristic better, such as convolving the set with itself so that it has non-negative Fourier coefficients. I won’t worry about such issues here,) Now the intersection of two sets corresponds to the pointwise product of their characteristic functions, and that transforms to the convolution of their Fourier transforms. And the size of the intersection is given by the square of the $\ell_2$ norm of this convolution. If we ensure that the Fourier transform is real and positive, then the $\ell_1$ norm of the convolution will not depend on $a$ and $b$ . Therefore, in order to make the $\ell_2$ norm as small as possible, we want the convolution to be as “spread out” as possible, which happens if there are as few linear relations amongst $a$ and $b$ with coefficients less than $k$ as possible. This suggests that we should look for $a$ and $b$ such that all the numbers $ar+bs$ with $r,s\in[-m/c,m/c]$ are as distinct as possible. And now we are getting close to Problem 10. I haven’t checked, but I think a slightly more complicated argument establishes a similar connection between Problems 2 and 9.

It’s quite possible that the answers to some of these questions are known, or at least that the questions would seem easy to experts in the area.

Added later: as I mentioned above, this is indeed the case. See for example this paper of Pollington and Vellani, which shows that the set of all pairs $(\alpha,\beta)$ such that $\alpha$ and $\beta$ are badly approximable and $\max\{\|m\alpha\|,\|m\beta\|\}\geq cm^{-1/2}$ for every $m$ , where $c=c(\alpha,\beta)>0$ , has Hausdorff dimension 2. (Their result is in fact more general than this.) Davenport proved in the early 1950s that the answer to Problem 7 is yes, and that there are uncountably many examples.

The paper where I found a mention of a dual problem is “Simultaneous Diophantine approximation” by Davenport, published in the Proceedings of the LMS, December 1952, pages 406-416.

Could one make a serious attempt to find a counterexample?

Let me return yet again to the question of whether elementary methods are appropriate for the Littlewood problem. As I have shown above, there are several problems that seem to be very closely related to it but that are in one way or another easier, and I don’t see any good reason for ruling out elementary approaches to those. That is particularly true of Problem 5 (the dyadic variant of the separated-points problem).

However, another reason I think that one should not rule out the use of elementary methods is that it is possible that Littlewood’s conjecture is false. I want in this section to outline a few thoughts about how one might go about disproving it.

The first thing to say is that if the conjecture is false, it is not false by very much. The headline result of Einsiedler, Katok and Lindenstrauss is that the set of counterexamples to the conjecture has Hausdorff dimension zero, and this result has a strong bearing on what kind of methods stand a chance of yielding a counterexample.

In order to elaborate on this remark, let me discuss a “combinatorial” way in which one might end up with a good real number $\alpha$ if you want $\lim\inf n\|\alpha n\|$ to be positive. We have already seen that any $\alpha$ with bounded convergents in its continued fraction expansion will do: what I am about to discuss is a way of seeing that without explicitly thinking about continued fractions.

The idea is to start with an attempt $\alpha_0$ and to make a series of adjustments to it. So let’s start with a truly stupid choice of $\alpha_0$ , namely $0$ . Instantly we are in trouble, because $\|\alpha_0\|$ is not large. So let us make it as large as we can by taking $\alpha_1=1/2$ . Now that sorts out $\|\alpha_1\|$ but we quickly run into trouble again, since $\|2\alpha_1\|=\|1\|=0.$ So let us adjust again, by moving $\alpha_1$ until $\|2\alpha_1\|$ becomes as large as possible. There are two minimal ways of doing that: we could take $\alpha_2=1/4$ or $\alpha_2=3/4$ . Let’s try increasing at every stage, so we take $\alpha_2$ to be $3/4$ . Now we run into problems only at $\|4\alpha_2\|$ , when we get $\|3\|=0.$ So let us adjust by taking $\alpha_3$ such that $4\alpha_3=3\frac 12,$ which gives us $\alpha_3=7/8.$

We are running into difficulties, because it appears that $\alpha_n=1-2^{-n}$ if we continue with this algorithm. But at this point we might pause to observe that if $m\alpha_n$ is an integer, we do not need to increase $\alpha_n$ to make $m\alpha_n$ as far from an integer as possible: all that really matters is that it should be further from an integer than $c/m.$ In retrospect, it makes sense if our successive adjustments are as small as possible, so that we don’t mess up the progress we have made previously.

With this thought in mind, let us try again. We take $\alpha_0=0$ . Since $1$ is very small, we had better take $\alpha_1$ to be as far from an integer as possible, so let us once again take $\alpha_1$ to be $1/2.$ But now, when we come to deal with the problem that $2\alpha_1$ is an integer, let us increase it from $1$ to $4/3$ instead of to $3/2$ . In other words, let us take $\alpha_2$ to be $2/3$ . Our next problem comes with $3\alpha_2$ , so let us change that from $2$ to $2\frac 14$ , which gives us $\alpha_3=3/4$ .

Unfortunately, we are in trouble again, because $\alpha_n$ works out to be $n/(n+1).$ So let us think slightly harder about what we have to do in order to ensure that we do not get into trouble. We are trying to build a sequence $\alpha_0,\alpha_1,\alpha_2,\dots$ that converges to a limit $\alpha$ in such a way that $\|n\alpha\|\geq c/n$ for every $n$ . This we can achieve if we ensure that $\|n\alpha_m\|\geq c/n$ for every $n\leq m$ , and this we can achieve if we make sure that $\|m\alpha_m\|\geq 2c/m$ and that $|m\alpha-m\alpha_m|\leq c/m$ .

Here is another approach. Let us again start with $\alpha_0=0$ and $\alpha_1=1/2$ . To define $\alpha_2$ , we shall use the following principle: we look for the “worst place” and the “second worst place” and share the badness equally between them. Here the “worst place” is where the disaster occurs that $2\alpha_1=1$ and the “second worst place” is where $\alpha_1=1/2$ . So we increase $\alpha_1$ to $\alpha_2=2/3$ , so that both $\|\alpha_2\|$ and $\|2\alpha_2\|$ are equal to $1/3$ .

The next disaster occurs when we notice that $3\alpha_2=2$ . The second worst place could be taken to be either $\alpha_2$ or $2\alpha_2$ . There is something to be said for alternately increasing and decreasing our $\alpha_n$ , since that will make the total change smaller than if we always increase, so let us focus on $2\alpha_2$ . To share out the badness equally, we would like to decrease $\alpha_2$ slightly so that $2\alpha_3-1=2-3\alpha_3$ . That tells us to take $\alpha_3=3/5.$

Probably you can guess by now what happens: we keep going like this and we end up producing the fractions $\frac 01, \frac 12, \frac 23, \frac 35, \frac 58, ...$ and in the limit we get the golden ratio.

But the method of making successive adjustments is much more general and flexible than this — we just happened to do things so efficiently that we got the best result. I confess that I haven’t quite nailed this explanation, but ultimately it should be possible to devise a successive-adjustment procedure that could in principle give any real for which the continued-fraction expansion has bounded quotients, and thereby present the continued-fraction solution as the outcome of a just-do-it proof.

Unfortunately, the main point I now want to make is that it is highly unlikely that any such approach could give rise (except perhaps very indirectly) to a counterexample to the Littlewood conjecture. The idea would be to start with a pair of real numbers $(\alpha_0,\beta_0)$ and make successive adjustments to it each time some multiple misbehaved. If you try this, you will soon find yourself running into difficulties, but the result of Einsiedler, Katok and Lindenstrauss tells you in advance to expect this, or at least I think it does.

My heuristic reasoning here is as follows: if you can use a reasonably flexible successive-adjustment argument, then you will tend to get a set that is somewhat Cantor-like: you start with an interval of possibilities, then from it you remove some subintervals, and from what remains you remove further subintervals, and so on. These kinds of ideas show that the Hausdorff dimension of the set of reals with bounded partial quotients is not small: I haven’t yet found a good reference and I don’t know what the precise results are. But turning this on its head, one would expect that for Littlewood’s conjecture, if any successive-adjustment technique worked, it would have to be incredibly non-robust and work almost miraculously: perhaps as one removed subintervals one would sometimes remove whole branches of the tree and it would be far from obvious that by the end of the process there would be any tree left.

It is thoughts such as these that make me interested in Problem 7 (the weak version of Littlewood’s conjecture). For this problem, $(\|m\alpha\|,\|m\beta\|)$ has to avoid a box of radius $m^{-1/2}$ , and therefore area $O(m^{-1})$ . This feels much more like what you have to do when you are trying to find $\alpha$ such that $\|m\alpha\|$ avoids an interval of length $O(m^{-1})$ , so it is tempting to try a successive-adjustment strategy. (Added later: This is indeed the type of argument that Pollington and Vellani use. At one point they use a very clever idea of Davenport.)

My belief is that such a pair $(\alpha,\beta)$ exists, but finding one using a successive-adjustment strategy seems not to be wholly straightforward, because there is not an obvious direction in which to take the adjustment. (What is clear is that this direction must vary enough to stop the set of multiples becoming “approximately one-dimensional”, but I don’t see how to do this systematically.) Anyhow, I very much like this problem, because it seems to be of intermediate difficulty, and if one did manage to find a good supply of examples, and perhaps even understand the Hausdorff dimension of the set of examples, then one might be able to understand how that set behaved when you intersect it with copies of that set that you obtain by stretching it in one direction and shrinking it in the other (which is supposed to help you avoid other rectangles of the same area and thereby attempt to give a counterexample to Littlewood’s conjecture). Perhaps the set is sufficiently non-symmetric under transformations of the kind $(x,y)\mapsto(2^kx,2^{-k}y)$ that images of it under such transformations are “independent” in some way and therefore have a non-empty, but very small, intersection.

(Added later: Given what I now know about results in the area, the goal here would have to be different. It would be to understand the set of examples well enough to be able to show that it has non-empty intersections with various transformations of itself. This, it seems, is a known hard problem: see Conjecture 1 of the paper of Pollington and Vellani.)

Computer-generated pictures.

I’m a hopeless programmer. If I weren’t, then I would have done the following very simple computer experiment, and I would love it if someone else could do it. It would be to generate a picture as follows. Choose a fairly large prime $p$ and take a square of $p\times p$ pixels. Choose also a small constant $c$ such as $1/10$ and an integer $M$ that’s much larger than 1 and (probably) quite a bit smaller than $p$ . (It would be interesting to do this with different constants.) Think of the square as $\{0,1,\dots,p-1\}^2$ . Now make the pixel $(x,y)$ black if there exists a positive integer $m\leq M$ such that $(mx,my)$ mod $p$ lies in the box $[-cp/m^{1/2},cp/m^{1/2}]^2.$ I would very much like to see what the resulting set looks like. In particular, I would like to know whether it is obvious from looking at it that the horizontal and vertical distance scales are the same. (One would have to look at just a small chunk of it since it would be symmetrical in $x$ and $y$ .) And I’d also like to know whether it has a Cantor-ish feel to it. If anyone is ready to spend the half hour it would need a competent programmer to generate a few pictures like this I would be extremely grateful to have my curiosity satisfied. This wouldn’t have to wait for an official project to start — it could be an interesting preliminary.

Needless to say, one could also generate images of sets related to Littlewood’s conjecture itself, rather than the weak version. One would simply colour a pixel $(x,y)$ black if $\|mx/p\|\|my/p\|\leq c/m$ . It would be interesting to try this for various values of $c$ , $p$ and (especially) $M$ . In particular, I am interested to know what the residual set looks like, and whether it gets smaller very quickly (as the dimension-zero result suggests that it should).

As well as generating pictures, one could try to test the conjecture in a crude experimental way, by searching for pairs of numbers $(\alpha,\beta)$ such that $m\|\alpha m\|\|\beta m\|$ does not get small (or at least does not get small unless $m$ is large. Indeed, we could define $f(M)$ to be the largest possible value of $\min_{1\leq m\leq M}m\|\alpha m\|\|\beta m\|$ . One can get good estimates of $f(M)$ if $M$ is not too large by simply trying all pairs $(\alpha,\beta)$ such that the decimal expansion terminates after $k$ digits for some manageable $k$ . Of course, if $m\|\alpha m\|\|\beta m\|$ is small for some smallish $m$ , then the same will be true for all pairs in some neighbourhood of $(\alpha,\beta)$ , so there may be good ways of speeding up this brute-force approach. (At the very least, one could eliminate all pairs that fail when $m=1$ , then all pairs that fail when $m=2$ , and so on, so that one would search through fewer pairs when one had got further with the search.)

Conclusion.

One of the things I like about this project is that there is quite a long list of subproblems of graded difficulty: it seems likely that at least something interesting could be proved, and the aim would be simply to get as far as we can. Even doing a few simple computer investigations would be quite interesting (though if it turns out that $f(M)$ tends to zero slowly with $M$ , then this might well not show up clearly in the data). The dyadic version of the packing problem looks to me as though it could have a reasonably easy solution, at least if a good packing exists. The “weak Littlewood problem” ought to be substantially easier than the main problem — I think there should be a reasonably large set of counterexamples — but hard enough to be interesting (unless the answer is already known, which is certainly possible). Likewise, the higher-dimensional problem should be easier to prove, this time with a positive answer (but again the answer may be known). And perhaps the “dual versions” are sufficiently different that they too have a chance of being of the right level of difficulty. (Added later: the fact that the weak version is indeed known changes my assessment of this project somewhat. I would be interested to understand the proof of that as well as possible, but given that it is known, the place to focus on first might be the dyadic packing problem in three dimensions.)

For the sake of commenters, here is a set of abbreviations that might be useful.

LP (Littlewood problem). PP (packing problem — the one where you want a large well-separated set with the distance that isn’t really a distance). DPP (dyadic packing problem). WLP (weak version of Littlewood problem). HDLP (high-dimensional Littlewood problem). HDDPP, HDWLP (obvious meanings). DLP (dual Littlewood problem). WDLP (weak dual Littlewood problem).

by gowers at November 21, 2009 06:00 PM

November 21, 2009

US/LHC Blog — Live from CMS CR at P5 (the BBC is in)…

Beam splash event from Beam 2 (beam onto collimator), CMS detector

Beam 1 circulated for several minutes and before that we were able to take a a few splash events. Then after they managed to circulate Beam 2 and they are ready to capture it…

The BBC was here for most of the Beam 2 episode.

-Edgar Carrera (Boston University)

by Edgar Carrera at November 21, 2009 05:26 PM

US/LHC Blog — Pushing the Red Button (Live from CMS CR at P5)

Beam splash event. CMS detector side view

It looks like tonight CMS will be the chosen experiment to press the red button. The LHC operators have told us that after they perform several tests with the captured beam 1, they will try to run for 20 min with an untouched captured beam 1 (probably meaning they won’t perform any tests) and then CMS will be asked to push the button to dump it!!!! As I understand, this is a test of this safety feature that each of the experiments has. After this, they will re-inject.

In all these exciting years of being an experimental particle physicist, whenever I talk about what I do, and in particular when I mention that I have worked in two of the biggest accelerators in the world, people tend to ask me about pushing the “red button”. I think no one is exactly sure what they mean when they ask, – oh, so you have to push the red button? -, but it always amuses me and triggers my imagination. I am pretty sure different people imagine different tasks for this big round red thing (the CMS beam abort button, however, is actually pretty small and green. At least this is what I have heard…)

When I was working in the D0 experiment at the Fermilab’s Tevatron in Chicago, I was aware of many red buttons, but none of them fit my “ideal” red one. As a data acquisition shifter (the operator who basically runs the data taking), I had to press many, but I don’t remember any being red (or round for that matter) and all of them were within computer graphical interfaces.

As a graduate student, however, a fellow senior graduate student inherited me a RED squared button for my desktop’s keyboard at work when he graduated. There were many times when I wished the button had a real effect on things (it was a dummy )….. I sometimes pushed it nevertheless. This button, which read “PANIC” in its legend, had been passed over for generations ….. I proudly continued the tradition when I graduated.

CMS is running fine, triggering on circulating beams.

Edgar Carrera (Boston University)

by Edgar Carrera at November 21, 2009 05:25 PM

Tommaso Dorigo — The Say Of The Week

Particle Physics had a short fling with Numerology in its young years, but the two have never met again since then.

TD

by dorigo at November 21, 2009 03:15 PM

US/LHC Blog — Holiday Gift?

There’s a decent amount of publicity out there about last night at CERN.

From the New York Times, Proton Beams Are on Track at Collider:

About 10 p.m. outside Geneva, scientists at CERN, the European Center for Nuclear Research, succeeded in sending beams of protons clockwise around the 17-mile underground magnetic racetrack known as the Large Hadron Collider, the world’s biggest and most expensive physics experiment…

If all goes well, CERN says, the protons will start colliding at low energies in about a week…

CERN is hoping to achieve that landmark as a symbolic Christmas present before a short holiday shutdown.

I’m looking forward to that – I’ll be on shift to watch CMS several times in the coming weeks. (As for Christmas gifts, I still also hope to get a fancy rice cooker.)

–Mike

by Mike Anderson at November 21, 2009 12:25 PM

Backreaction — Swedish Research Council requires Open Access

The Swedish Research Council decided some weeks ago that research supported by a grant from their agency has to be made publicly available within 6 months. From the press release:

"To obtain a research grant, the Swedish Research Council now requires researchers to publish their material so as to make it available to all. The public and other researchers should have free access to all material financed by public means.

The thought behind so-called Open Access is that everyone should have free and unrestricted access to scientifically assessed articles. The Research Council has now determined that researchers granted funds by the Authority should publish their scientifically assessed texts in journals and from conferences in this manner.... Researchers will have to guarantee that publications are available according to Open Access within a maximum period of six months."

This requirement is even stronger than that of the US National Institute of Health (NIH), which demands the public has access to the published results of NIH funded research no later than 12 months after publication.

Seems like the Open Access movement has a reason to celebrate :-)

by Bee at November 21, 2009 07:50 AM

Jonathan Shock — Orion setting over Santiago de Compostela

I don't post these pictures as great examples of astrophotography - that much is clear but I'm always keen to point out what is around us to be observed with very little effort and minimal cost.

I woke up around 3 in the morning a few days back and thought I'd take a look outside to see if the Leonids were in evidence. Sadly as I poked my head from the seventh story of the building to the West of Santiago there were no shooting stars in evidence but Orion was standing there clearer than I'd seen it for a long time - we've had terrible storms for the last week or so and this was the first chance to see the stars in a while.

I set up the tripod, mounted the 300mm lens onto my Canon and took a few snaps to see how clearly one can see the orion nebula from a small city. I'm pretty pleased with the results for a first serious try and with a body which deals better with low light I think one could get some spectacular results.

The point to make with such a shot is simply that although we think of the night sky as a simple distribution of points of light, really there is structure out there even at the grossest scales, from the giant gas clouds surrounding old supernova remnants to the galaxies observable with the naked eye on a truly dark night to the phases of Venus, the bands of Jupiter and the rings of Saturn - such things are not only there to be seen by those with research budgets and large inheritances. All you need is enthusiasm, some truly minimal equipment and a little time to explore.

by Jonathan Shock at November 21, 2009 06:23 AM

Alexey Petrov — It is back!

After a year of repairs LHC has circulated the beam once again. The first collisions are to follow soon – about a week from now.

It happened. We are eagerly awaiting the answer of the Higgs From the Future .

by apetrov at November 20, 2009 11:28 PM

November 20, 2009

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

After a one-week hiatus, we are resuming our reading seminar of the Hrushovski paper. This week, we are taking a break from the paper proper, and are instead focusing on the subject of stable theories (or more precisely, ${\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:

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

— 1. Stable theories —

Let ${L}$ be a countable language. Recall that if we have a structure ${M}$ for ${L}$ , and a set ${A}$ of constants in ${M}$ , we can define an ( ${n}$ -ary) type of ${M}$ over ${A}$ to be a maximal consistent family ${p}$ of formulae ${\phi(x_1,\ldots,x_n)}$ for an ${n}$ -tuple ${\vec x = (x_1,\ldots,x_n)}$ , where the formulae are allowed to use ${A}$ as constants. For instance, in the language of algebraically closed fields over some base field ${k}$ (all elements of which are constants in ${L}$ ), if ${M}$ is an algebraic closed field and ${A}$ is empty, the type associated to a “generic” element of an algebraic variety ${V \subset M^n}$ defined over ${k}$ (i.e. elements that obey the defining equations for ${k}$ , but do not obey any other algebraic relations over ${k}$ ) is a type. If one makes ${A}$ non-empty, then one now also needs to consider algebraic relations over ${k(A)}$ , the field formed by adjoining ${A}$ to ${k}$ . Note that in general, a type will not be realised in the structure ${M}$ (unless that structure is so huge as to be saturated over the cardinality of ${A}$ ), but can always be realised in some extension of ${M}$ , by the completeness theorem.

The set of all ${n}$ -ary types of ${M}$ over ${A}$ is denoted ${S_n^M(A)}$ . It has a natural topology, the Stone topology, whose basic open (in fact, clopen) sets are given by ${U_\phi := \{ p \in S_n^M(A): \phi \in p \}}$ for any formula ${\phi(x_1,\ldots,x_n)}$ defined over ${A}$ . This makes the space of types a Stone space (totally disconnected, Hausdorff, compact).

In general, the number of types in the world can be quite large: if ${A}$ has cardinality ${\kappa}$ for some infinite ${\kappa}$ , then the total number of formulae in ${L(A)}$ is also ${\kappa}$ , so the number of types could conceivably be as large as ${2^\kappa}$ . But for a special class of theories – the ${\kappa}$ -stable theories – the number is much smaller:

Definition 1 Let ${\kappa}$ be an infinite cardinal. A complete theory ${T}$ is ${\kappa}$ -stable if, for any structure ${M}$ satisfying ${T}$ , and any set ${A}$ of constants in ${M}$ of cardinality at most ${\kappa}$ , the set of ${n}$ -ary types of ${M}$ over ${A}$ is at most ${\kappa}$ for every ${n}$ .

The classic example of a ${\kappa}$ -stable theory (for any infinite ${\kappa}$ ) is the theory of algebraically closed fields with fixed characteristic (it is a classical theorem that this theory is complete, basically thanks to quantifier elimination). By quantifier elimination (or by many applications of the nullstellensatz), one can show that the ${n}$ -ary types in this theory over ${A}$ are in one-to-one correspondence with minimal ideals in ${F(x_1,\ldots,x_n)}$ , where ${F = k(A)}$ , where ${k}$ is the base field of given characteristic, with a type ${p}$ consisting of the “generic” points cut out by the ideal ${I := \{ f \in F(x_1,\ldots,x_n): (f(x_1,\ldots,x_n)=0) \in p \}}$ . More succinctly, ${S_n^M(A) \equiv Spec(F(x_1,\ldots,x_n))}$ . By Hilbert’s basis theorem, all ideals in ${F(x_1,\ldots,x_n)}$ are finitely generated, and so the cardinality of types is easily seen to be at most ${\kappa}$ .

When ${\kappa}$ is uncountable, a more general example of a ${\kappa}$ -stable theory is that of a ${\kappa}$ -categorical theory – a theory such that any two models of cardinality ${\kappa}$ are isomorphic. (Details can be found in Anush’s notes.)

The classic example of a theory which is not ${\kappa}$ -stable is the theory of dense linear orderings, i.e. the theory of the rationals ${{\mathbb Q}}$ with the order relation ${<}$ . Using Dedekind cuts, one can associate a type in ${S_1^{\mathbb Q}({\mathbb Q})}$ to every real number, and so there are uncountably many types here even though the number of constants is countable. Thus this theory is not ${\omega}$ -stable (though it is ${\omega}$ -categorical).

Now we look at alternate characterisations of stability, particularly ${\omega}$ -stability. If ${M}$ is a model of a theory ${T}$ in a language ${L}$ , define a binary tree in ${M}$ to be a collection ${\phi_s(x_1,\ldots,x_n)}$ of ${n}$ -ary formulas in ${L(M)}$ , where ${s}$ are indexed by finite strings of ${0}$ s and ${1}$ s, each of which are consistent with ${T}$ , and such that for any string ${s}$ and its two children ${s0}$ and ${s1}$ , the formulae ${\phi_{s0}}$ and ${\phi_{s1}}$ cut out disjoint subsets of the set cut out by ${\phi_s}$ relative to ${T}$ , or more precisely that ${\phi_{s0},\phi_{s1}}$ are mutually inconsistent in ${T}$ , but both imply ${\phi_s}$ .

Theorem 2 For a countable language ${L}$ and a complete theory ${T}$ , the following are equivalent:

(i) No binary tree of formulae exists for any model ${M}$ of ${T}$ .

(ii) ${T}$ is ${\kappa}$ -stable for every infinite ${\kappa}$ ;

(iii) ${T}$ is ${\omega}$ -stable.

Proof: (ii) trivially implies (iii). Now we show that (i) implies (ii), i.e. we take a theory which is not ${\kappa}$ -stable for some infinite ${\kappa}$ and use it to create a binary tree.

By hypothesis, we can find a model ${M}$ and a set ${A}$ of constants of cardinality at most ${\kappa}$ , and an ${n}$ such that the number of ${n}$ -ary types exceeds ${\kappa}$ . We can use this to create a binary tree as follows. Call a formula ${\phi(x_1,\ldots,x_n)}$ defined over ${A}$ large if it is contained in more than ${\kappa}$ types (i.e. if ${U_\phi}$ has cardinality more than ${\kappa}$ ), and small types; thus in particular any tautology is large. We set the root ${\phi_\emptyset}$ of the binary tree to be such a large formula. We then remove all the types associated to small formulae from ${U_{\phi_\emptyset}}$ , and still retain more than ${\kappa}$ types. Picking two such distinct types ${p,q}$ , one can find a formula ${\psi}$ separating ${p}$ from ${q}$ (since ${p \neq q}$ ), which allows one to find two formulae ${\phi_1, \phi_2}$ which are inconsistent with each other and imply ${\phi_\emptyset}$ (namely ${\phi \wedge \neg \psi}$ and ${\phi_\emptyset \wedge \neg \psi}$ ); by construction, these formulae are also large. Iterating this procedure gives the binary tree.

Finally, to show (iii) implies (i), we see from taking Dedekind cuts again that an infinite binary tree can be used to define an uncountable number of types (by including all the formulae to the left of a cut, excluding all the ones to the right, and then completing to a complete type), which violates ${\omega}$ -stability. $\Box$

The property of not having binary trees is also known as being totally transcendental, though it was unclear where this terminology came from (especially given that the theory of algebraically closed fields is the classic example of a totally transcendental theory).

We have seen that order theories tend to be unstable. Indeed, ${\omega}$ -stable theories is that they are unable to definably order infinite sets:

Theorem 3 Let ${T}$ be an ${\omega}$ -stable theory, let ${M}$ be a model of ${T}$ , and let ${X}$ be an infinite subset of ${M}$ . Then there is no definable relation ${<}$ in ${L}$ that is a total ordering on ${X}$ .

Proof: Suppose this is not the case. Using the compactness theorem, we can thus find a model of ${M}$ with a countably infinite subset ${X}$ for which ${<}$ endows ${X}$ with the order structure of the rationals. But then by Dedekind cuts one can then create an uncountable number of types over ${X}$ , contradicting ${\omega}$ -stability. $\Box$

It is easy to generalise ${\omega}$ -stability in the above theorem to ${\kappa}$ -stability for any infinite ${\kappa}$ , by developing analogues of the rational order structure for other cardinalities; see Anush’s notes.

There was some debate as to whether the theory of the Rado graph admitted any obvious definable total ordering on a countable set, but the discussion was inconclusive.

— 2. Stability and indiscernability —

Recall from previous notes that a sequence ${x_1,x_2,\ldots}$ of elements of a structure ${M}$ were order-indiscernible if all of the ${k}$ -tuples ${(x_{i_1},\ldots,x_{i_k})}$ with ${i_1<\ldots<i_k}$ were elementarily indistinguishable from each other (i.e. every formula obeyed by one tuple, is obeyed by all the other tuples). One can use Ramsey-theoretic methods to generate a plentiful supply of order-indiscernibles.

One would however like a stronger notion of indiscernability, which we will just call indiscernability, in which all ${k}$ -tuples ${(x_{i_1},\ldots,x_{i_k})}$ with ${i_1,\ldots,i_k}$ distinct (but not necessarily ordered) are indistinguishable. In general, order indiscernability does not imply indiscernability. But because stable theories cannot “see” order, one has equivalence in this case:

Theorem 4 In an ${\omega}$ -stable theory, every order-indiscernible sequence is indiscernible.

Proof: Let ${x_1,x_2,\ldots}$ be order-indiscernible in some model ${M}$ . To show indiscernibility, it suffices to show that permutations of ${(x_{i_1},\ldots,x_{i_k})}$ are indistinguishable from each other. As permutations are generated by adjacent transpositions, it suffices to do this for adjacent transpositions. For notational simplicity we will just show that ${(x_1,x_2)}$ and ${(x_2,x_1)}$ are indistinguishable; the general case is similar.

Suppose this is not the case, thus there is a formula ${\phi}$ such that ${\phi(x_1,x_2)}$ holds in ${M}$ but ${\phi(x_2,x_1)}$ fails. Then ${\phi(x_i,x_j)}$ holds precisely when ${i < j}$ , thus ${\phi}$ orders ${x_1,x_2,\ldots}$ , contradicting the previous theorem.

(In the general case, one cannot quite use Theorem 3 directly, but one can modify the proof to achieve a similar result; see Anush’s notes.) $\Box$

By the previous remarks, the argument can also be extended to ${\kappa}$ -stable theories for any infinite ${\kappa}$ .

— 3. Morley rank and degree —

Suppose one was working in the theory of algebraically closed fields of characteristic zero, and wanted to define the notion of the dimension of an algebraic set ${V}$ . Clearly, one would want finite sets to have dimension ${0}$ , and to be the only sets with this property. As for infinite sets, one could recursively define dimension by enforcing the following statement: an algebraic set has dimension at least ${\alpha+1}$ if and only if it contains infinitely many disjoint algebraic sets of dimension at least ${\alpha}$ .

One can do the same for any theory, assigning to each definable set in a structure ${M}$ a Morley rank, which is either ${-1}$ , an ordinal, or ${\infty}$ (which we consider to be larger than all the ordinals (!)) by the following rules:

The empty set has Morley rank ${-1}$ ; all other definable sets have Morley rank at least ${0}$ .
If ${\alpha}$ is an ordinal, then a definable set has Morley rank at least ${\alpha+1}$ if and only if it contains infinitely many disjoint definable sets of Morley rank at least ${\alpha}$ .

Note that for a limit ordinal ${\alpha}$ , a set will have Morley rank at least ${\alpha}$ iff it has Morley rank at least ${\beta}$ for all ${\beta < \alpha}$ , and a set will have Morley rank ${\infty}$ if it has Morley rank at least ${\alpha}$ for every ordinal ${\alpha}$ . Using this, one can show by transfinite induction that every definable set has a Morley rank.

The Morley rank of a formula ${\phi}$ cutting out a definable set in a structure ${M}$ may depend on the choice of structure ${M}$ . However, if we assume that the structure ${M}$ is countably saturated, i.e. that any finitely satisfiable collection of formulae involving at most countably many constants is fully satisfiable, then the dependence on ${M}$ largely disappears. To see this, we first need a preliminary lemma:

Lemma 5 Let ${M}$ be countably saturated, and let ${A_a}$ be a definable set depending on a parameter ${a}$ . Then the Morley rank of ${A_a}$ in ${M}$ depends only on the type of ${a}$ .

Proof: Let ${a, b}$ have the same type (i.e. they are elementarily indistinguishable). We need to show that ${A_a}$ , ${A_b}$ have the same Morley rank. Suppose not. If ${A_a}$ was empty, then ${A_b}$ would be also by indistinguishability, and the claim is obvious; so suppose that both sets are non-empty. Then, without loss of generality, we may assume that ${A_a}$ has Morley rank ${\alpha}$ but ${A_b}$ has Morley rank at least ${\alpha+1}$ , thus ${A_b}$ contains a countable family of disjoint definable sets ${B_{b,c_1}, B_{b,c_2}, \ldots}$ of Morley rank at least ${\alpha}$ defined using some constants ${c_1, c_2, \ldots}$ . Using countable saturation, one can find inductively constants ${d_1,d_2,\ldots}$ such that ${(a,d_1,\ldots,d_m)}$ has the same type as ${(b,c_1,\ldots,c_m)}$ for every ${m}$ . This creates a countable family of djsoint definable sets ${B_{a,d_1},B_{a,d_2},\ldots}$ of ${A_a}$ , which by an induction hypothesis on ${\alpha}$ can be assumed to have Morley rank at least ${\alpha}$ , which forces ${A_a}$ to have Morley rank at least ${\alpha+1}$ , a contradiction. $\Box$

Corollary 6 If ${M}$ is countably saturated, and ${\phi_a}$ is a formula defined using some constants ${a}$ in ${M}$ , then the Morley rank of ${\phi_a}$ in ${M}$ is equal to the Morley rank of ${\phi_a}$ in ${N}$ , for any elementary extension ${N}$ of ${M}$ .

Proof: It is easy to see by transfinite induction that the Morley rank in ${N}$ is at least as large as that of ${M}$ (there are more non-empty definable sets). Suppose for contradiction that the Morley rank in ${M}$ is ${\alpha}$ , but the Morley rank in ${N}$ is at least ${\alpha+1}$ . (The case when ${\phi_a}$ cuts out an empty set in ${M}$ or ${N}$ is trivial from elementary equivalence.) Then the set ${\phi_a(N)}$ cut out by ${\phi_a}$ in ${N}$ contains a countable family of disjoint definable sets ${\psi_{a,b_1}(N), \psi_{a,b_2}(N), \ldots}$ of Morley rank at least ${\alpha}$ , for some ${b_1, b_2, \ldots}$ in ${N}$ . By elementary equivalence and countable saturation, one can inductively find ${c_1,c_2,\ldots}$ in ${M}$ such that the type of ${(a,c_1,\ldots,c_m)}$ in ${M}$ equals the type of ${(a,b_1,\ldots,b_m)}$ in ${N}$ . Then ${\psi_{a,c_1}(M), \psi_{a,c_2}(M), \ldots}$ form a countable family of disjoint definable sets in ${\phi_a(M)}$ , which have Morley rank at least ${\alpha}$ by the previous lemma, giving the desired contradiction. $\Box$

Corollary 7 If ${N_0, N_1}$ are countably saturated elementary extensions of ${M}$ , and ${\phi_a}$ is a formula defined using some constants ${a}$ in ${M}$ , then the Morley rank of ${\phi_a}$ in ${N_0}$ is the same as that in ${N_1}$ .

Proof: Take a common countably saturated elementary extension ${N}$ of both ${N_0}$ and ${N_1}$ ; by the previous corollary, the rank in ${N_0}$ or in ${N_1}$ is equal to that in ${N}$ . $\Box$

We can thus define the (structure-independent) Morley rank of any formula ${\phi}$ in ${M}$ to be the rank of ${\phi}$ in any countably saturated elementary extension.

It is not hard to show that Morley rank obeys the basic properties of a dimension, e.g. the dimension of a union is the larger of the dimensions of the two summands (in particular, Morley rank is monotone with respect to set inclusion), and that the only sets of dimension zero are the finite sets.

To avoid technical issues, let us now assume that all models ${M}$ we work in are small elementary submodels of a universal model ${{\Bbb M}}$ (i.e. a model which is saturated with respect to all small models).

We know that any set of a given Morley rank ${\alpha}$ cannot be partitioned into infinitely many disjoint subsets of the same rank. Using this and König’s lemma, we in fact conclude

Proposition 8 If a definable set ${A}$ has an ordinal Morley rank ${\alpha}$ , then there exists a finite ${d}$ such that ${A}$ cannot be partitioned into more than ${d}$ definable subsets of Morley rank ${\alpha}$ .

Proof: We form a partial binary tree by taking ${A}$ and splitting it (if possible) into disjoint non-empty subsets of Morley rank ${\alpha}$ , then taking these subsets and splitting them further, continuing until no further splitting is possible. If this tree is infinite, then König’s lemma ensures an infinite path, which easily gives a decomposition of ${A}$ into infinitely many disjoint definable sets of Morley rank ${\alpha}$ , a contradiction. Thus this tree is finite, and decomposes ${A}$ into some finite number ${B_1,\ldots,B_d}$ of rank ${\alpha}$ definable sets which are “irreducible” in the sense that they cannot be partitioned into two subsets of rank ${\alpha}$ .

We now claim that any other partition ${A = C_1 \cup \ldots \cup C_m}$ of ${A}$ into rank ${\alpha}$ definable sets must have ${m \leq d}$ . Note that for each ${B_i}$ there is at most one ${C_j}$ for which ${B_i \cap C_j}$ has rank ${\alpha}$ , otherwise ${B_i}$ would not be irreducible. On the other hand, each ${C_j}$ has to have at least one ${B_i}$ for which ${B_i \cap C_j}$ had rank ${\alpha}$ , for if all the ${B_i \cap C_j}$ had rank less than ${\alpha}$ then ${C_j}$ would also. Thus we have an injection from ${\{1,\ldots,m\}}$ to ${\{1,\ldots,d\}}$ , and so ${m \leq d}$ . $\Box$

We thus define the Morley degree of ${A}$ to be the largest ${d}$ for which one can partition ${A}$ into disjoint definable sets of the same rank. Note that all such components necessarily have degree ${1}$ .

Posted in Logic reading seminar, math.LO

by Terence Tao at November 20, 2009 03:37 PM

Secret Blogging Seminar — The diamond lemma

A few results

1 (Bjorner, Eidelman and Ziegler) Suppose we have a finite collection of great circles on a sphere, none of them through the north or nouth pole. Let $R$ be the set of regions in the complement of these circles, and suppose that every region is a triangle. Put a partial order on $R$ by $x \leq y$ if $x$ is south of every circle that $y$ is south of. Show that, for $x$ and $y \in R$ , there is some $z \in R$ such that $w \leq z$ if and only if $w \leq x$ and $w \leq y$ .

2 (Mozes, see also IMO 1986.3) Let $G$ be a finite graph, and let $r$ be a real valued function on the vertices of $G$ . Consider the following (solitaire) game: find a vertex $i$ for which $r_i$ is negative. Replace $r_i$ by $- r_i$ and, for every vertex $j$ that neighbors $i$ , decrease $r_j$ by $-r_i$ . The game ends if all of the $r_i$ are nonnegative. You and I start playing with the same graph and the same $r$ . Show that, if my game ends in $N$ moves at position $z$ , then your game will end in the same position, in the same number of moves.

3 (Poincare, Birkhoff and Witt) Define $U$ to be the ring generated by $E$ , $F$ and $G$ , subject to the relations $FE=EF+G$ , $GE=EG+F$ and $GF=FG+E$ . Show that any element of $R$ can be expressed uniquely as a sum of elements of the form $E^i F^j G^k$ . (Uniqueness is up to rearranging the sum and combining like terms.)

4 (Jordan and Holder) Let $G$ be a finite group. Let $G = G_0 \supsetneq G_1 \supsetneq G_2 \supsetneq \cdots \supsetneq G_r = \{ e \}$
$G = H_0 \supsetneq H_1 \supsetneq H_2 \supsetneq \cdots \supsetneq H_s = \{ e \}$
by two sequences of subgroups such that $G_{i+1}$ is normal in $G_i$ , with $G_{i+1}/G_i$ simple, and the same is true for the $H$ ’s. Then $r=s$ and the quotients $H_{i+1}/H_i$ are a permutation of the quotients $G_{i+1}/G_i$ .

What do all of these have in common? You can remember all of their solutions by drawing the same figure — the diamond!

Solution 1

We say that $z$ is a meet of $x$ and $y$ if $z$ has the required properties.

For any region $r$ , let $\ell(r)$ be the number of circles below $r$ . We will prove the following statement by induction on $\ell(r)$ :

Inductive Claim Suppose that $r \geq x$ and $r \geq y$ . Then $x$ and $y$ have a meet.

This establishes the result, as we can take $r$ to be the region containing the north pole and the hypotheses on $r$ become trivial. In the other hand, the base case is trivial because, when $\ell(r)=0$ , then $r$ must be the region containing the north pole, we have $r=x=y$ , and $r$ is a meet of $x$ and $y$ .

Now for the inductive part. Let $r \to \cdots \to x$ and $r \to \cdots \to y$ be southward traveling paths from $r$ to $x$ and $y$ . Let the first steps on these paths be $r \to s$ and $r \to t$ , crossing lines $i$ and $j$ . If $s=t$ , or equivalently $i=j$ , then we can take $s$ as a new $r$ and we are done by induction. Otherwise, let $u$ be the region due south of the crossing of $i$ and $j$ . It is easy to see that $u$ is a meet of $s$ and $t$ .

Applying the inductive hypothesis to $(s, x, u)$ , let $z'$ be a meet of $x$ and $u$ . Applying the inductive hypothesis to $(t, u, y)$ , let $z''$ be a meet of $u$ and $y$ . Applying the inductive hypothesis to $(u, z', z'')$ , let $z$ be a meet of $z'$ and $z''$ . We leave it to the reader to check that $z$ is a meet of $x$ and $y$ .

Solution 2

The proof is by induction on $N$ . Say my game begins $r \to s \to \cdots \to z$ and your game begins $r \to t \to \cdots$ . (We don’t know yet that your game ends.) Let my first move be at vertex $i$ and yours at vertex $j$ . The case $i=j$ is an immediate induction, so let’s assume $i \neq j$ . We know that $r_i$ and $r_j <0$ .

My brother and your sister come to join us. Here is how they play. If $i$ and $j$ are not adjacent, my brother starts off playing at $i$ , then at $j$ and your sister starts of at $j$ and then at $i$ . So, after two moves, both he and she reach the same configuration $u$ . If, on the other hand, $i$ is adjacent to $j$ , then my brother starts with $iji$ and your sister starts $jij$ . In three moves, they have again reached the same configuration. (Exercise! Remember to check that all vertices which are played are in fact negative at the time.) Call this configuration $u$ .

After this, my brother plays in any manner he wishes. By induction, after he moves to $s$ , he will make $N-1$ more moves and end at $z$ . Your sister also plays in any manner she wishes. By induction between her and my brother, after she gets to $u$ , she will make either $N-2$ or $N-3$ more moves and end at $z$ , having made $N$ moves in total. Finally, we apply the induction hypothesis to you and your sister. After you both move to $t$ , you will make $N-1$ more moves, ending at $z$ . So we all get to $z$ in $N$ moves.

Generalizing

I hope it is clear that Solutions 1 and 2 have the same inductive structure, although the details differ. The general strategy goes as follows: suppose we have some process which goes from one state to another. We have two different paths, $r \to s \to \cdots \to x$ and $r \to t \to \cdots \to y$ that start at the same state, and we want to show that, in some sense, they come together again. In the figure above, we are presented with the black structure, and we need to show that the paths rejoin. We will do this by adding the blue structure.

First, make a careful analysis of the case where the two paths have length $1$ , and prove your result in this case.

Now, using your analysis from the first step, build paths $r \to s \to \cdots \to u$ and $r \to t \to \cdots \to u$ which come together in the required way. Inductively, bring the paths $s \to x$ and $s \to u$ together at some $z'$ ; bring the paths $t \to u$ and $t \to y$ together at some $z''$ ; finally, bring $u \to z'$ and $u \to z''$ together at some $z$ .

Often, as in Solution 1, the starting point $r$ is trivial in the most important application. But bringing it into the problem allows us to apply this inductive structure.

One of the main difficulties is figuring out what to induct on. Roughly, one wants to use the length of the paths, but this may not be precisely right.

There are many good papers on the diamond lemma, but they tend to focus on applications to one particular field, and call it by different names. Here are some examples of the Diamond Lemma in Grobner bases, noncommutative rings, braid groups (chapter 14, see figure 12!), lattices (lemma 2.1), anti-matroids (lemma 2.6).

Solution 3 (a sketch)

Let’s talk about Puzzle 3. This is typical of applications to ring theory, and there are many subtleties which are particular to this context. I would like to refer to Bergmann’s superb paper for the details but, sadly, it is not publicly available online. For those without academic access, the best reference I can find online is Wenfeng Ge’s masters thesis.

Let’s call $E^i F^j G^k$ a standard monomial, and a sum of standard monomials a standard polynomial. Let the states of our system be formal noncommutative polynomials in $E$ , $F$ and $G$ . Let our operations be finding a term of the form $FE$ , $GE$ or $GF$ , and replacing it by $EF+G$ , $EG-F$ or $FG+E$ respectively. So the states where we can perform no operations are precisely the standard polynomials. We want to show that, starting with any polynomial $r$ , this process will terminate and, if we perform the process in two different ways, $r \to \cdots \to x$ and $r \to \cdots \to y$ , then $x=y$ . I’ll ignore termination, which is the easier question, to focus on the latter issue.

A better way to phrase our claim is that if we have any two paths $r \to \cdots \to x$ and $r \to \cdots \to y$ , which may not end at standard polynomials, then we can join them together into two paths $r \to \cdots x \to \cdots \to z$ and
$r \to \cdots y \to \cdots \to z$ which have a common endpoint. This trick is frequently useful: by phrasing our claim to apply to more paths, we make induction easier.

We start with a careful analysis of the case of paths of length 1. Say we have $r \to s$ and $r \to t$ . If the two changes happen in different monomials, or if they happen in nonoverlapping parts of the same monomial, then we can just make both changes in the two possible orders to get to the same destination in two steps.

So the only interesting case is two overlapping changes. For example, $GFE \to (FG+E)E$ and $GFE \to G(EF+G)$ . In this case, we make the following moves

The reader familiar with Lie algebras might like to see how this computation works in a general universal enveloping algebra; it’s a bit more complicated because the quadratic terms may not be standard.

The structure of the proof is now the same. Of course, we have to figure out what to induct on, and that’s a little subtle. But the worse issue is the following: Suppose our starting state is $GFE + FGE$ and our first move was to $E^2$ on one path, and to $GEF + G^2 + FGE$ on the other. According to the rubric above, we should move $E^2 \to FEG - F^2 + E^2 - FGE$ . But, as we’ve defined things, this isn’t a legal move, because there is no $GE$ to replace in $E^2$ . This possibility of terms cancelling is a major nuisance; I leave it to Bergmann to explain how to fix it.

Solution 4

You do it!

by David Speyer at November 20, 2009 02:47 PM

US/LHC Blog — First Beam through ATLAS!

The first beam of 2009 has passed through ATLAS! Follow the events at http://twitter.com/cern.

by Adam Yurkewicz at November 20, 2009 02:37 PM

US/LHC Blog — Live from the CMS control room at P5….

I am the secondary on-call expert for the High Level Trigger system, therefore I am backing up the primary expert at P5.

Everyone is so excited around here. We are waiting for the beams to reach P5. They will eventually circulate around the LHC ring and that will allow their alignment, etc. The monitor that shows the beam status from the LHC machine reads “Injection Probe Beam”.

It is a great feeling to be here, to make history, to contribute a little bit to the improvement of our knowledge, to the improvement of our own humanity.

http://cmsdoc.cern.ch/cms/performance/FirstBeam/cms-e-commentary09.htm (I am the guy typing standing in one of the pics )

Edgar Carrera (Boston University)

by Edgar Carrera at November 20, 2009 11:47 AM

Cosmic Variance — Beam Circulating in LHC Again!

09:37 PST: Like many of my colleagues, I’ve been eagerly awaiting word that the LHC has successfully threaded the proton beam around the whole ring. In recent days they have gotten it half way around the 27 km circumference, and within hours, they should be able to circulate it and I assume “capture” it with the RF, which creates stable bunches in the synchrotron. Everything has gone very smoothly to this point, so I expect success shortly!

Once beam has circulated stably in both rings, some time next week the LHC team will attempt to collide protons at the injection energy of 450 GeV (a total center of mass energy of 900 GeV). While this is much less than the Tevatron is colliding presently, it could provide some sorely needed initial data for the detectors to do timing and calibration of the various subsystems. There will even hopefully be a few collision events recorded with clear “dijet” structure – collisions where quarks and/or gluons inside the protons hit head on and effectively bounce sideways into the detector, giving two back-to-back collimated sprays of particles. Pictures of such events will be great to see, at long last!

You can follow progress live on twitter: http://twitter.com/cern and I will update this post as I learn more.

10:32 PST: The LHC has gotten beam around clockwise, to Point 6! Woo hoo!

10:45 PST: Magnet quench – should be recovered soon…

11:25 PST: Beam has reached Point 7!

11:30 PST: Point 8! Next beam will be sent past Point 1 where ATLAS is…

11:39 PST Beam all the way around the ring! WOO HOO!! It’s baaaaaack! The LHC Page 1 display shows that the injection probe beam made it more than once around the machine:

lhc1-orbits

11:54 PST: Next goals: do the same with the counterclockwise beam. Will they attempt RF capture tonight? Trying to find out…

13:11 PST: Turns out (no pun intended) they decided to go for RF capture of the clockwise beam rather than probe counterclockwise. They are up to 10 million turns with the RF on! Fantastic!

13:30 PST: Having captured the beam for several minutes, the LHC will now switch to counterclockwise.

14:53 PST: About to go for a full orbit of the counterclockwise beam…done!! Now to RF capture!

15:30 PST: Counterclockwise beam is RF captured! The LHC is operational…colliding beams within a week? Stay tuned.

by John at November 20, 2009 11:43 AM

Chad Orzel — November Basketball: SU-Cal, UNC-OSU

Kate and I went to the two games of the "semifinals" of the 2K Sports Classic Supporting Coaches vs. Cancer, Your Name Here for a Prince pre-season "tournament" last night (the scare quotes are because the four teams playing last night were guaranteed to be playing last night, regardless of what happened in the earlier "rounds"). We were in section 329 of Madison Square Garden, which aren't great seats in an absolute sense, but are pretty darn good for a game-day impulse buy. Not that there was any trouble getting seats-- the lower levels were maybe 3/4 full.

The first game saw Syracuse beat Cal by 22 in a virtual home game for the Orange. At one point, the Cal band came out to do a T-shirt toss, and I have rarely seen a group of people that anxious to get the hell off the court at a major sporting event. One of them appeared to huck his shirt directly at Bob Knight, who was calling the game for ESPN.

The second game saw North Carolina outlast Ohio State, in a game that was sloppy and uninteresting most of the way-- hovering in that frustrating 12-15 point range where the outcome probably isn't in doubt, but it's not enough of a blow-out to write it off and go home early. Carolina made it interesting when we did decide to leave, with about a minute to go, and let Ohio State close to within two, needing some clutch free throws to secure the victory (which we watched from the gate closest to the exit, along with fifty other people who had also decided to leave early, but came back for the final plays).

You cant really take too much from November basketball, but some scatered observations are below the fold.

Read the rest of this post... | Read the comments on this post...

Clifford Johnson — Tape Noir

I had a lot of time to kill in Philadelphia's International Airport on Sunday (I was changing planes), and I must say that is not a bad airport in which to be in such a situation. I like the city a lot, and so am not surprised that its main airport is to my liking. First of all, who can not like an airport that supplies you with... (you're expecting free wireless, and they had that, sure, but no, I mean)... with... Rocking Chairs!!! I saw some excellent art as well. And lots of displays of various types. I'll share a couple more in a post or two, but look at some of the pieces I snapped pictures of for you. They are done with packing tape! Yes, packing tape. That brown thin stuff you know well... It was part of a series of scenes from noir films, rendered in this way. Very effective indeed, I felt. The series name is "Tape Noir".

[...]

by Clifford at November 20, 2009 05:24 AM

US/LHC Blog — Foggy Beginnings

CERN November 20, 2009

As you can see in the picture I took this morning, it is foggy here at CERN today as we await the first circulating beam of protons in the LHC since last year. When this will happen exactly is a little foggy as well. There will probably be protons put into the LHC sometime this evening, so perhaps overnight we will have a circulating beam.

At the ATLAS detector, we are excited for the first beam to ATLAS this year, which will happen first (the way the LHC is configured, the beam has to go almost all the way around the LHC’s ring from where it is injected to get to the ATLAS detector).

The beam will first be made to stop before ATLAS by moving the beam collimator in its way. This will cause a huge cascade of particles to hit the ATLAS detector (similar to what was done recently at the CMS detector ), and it will be quite useful for us at ATLAS to detect all these particles and check our timing.

After that the collimator is removed and beam will pass through the ATLAS detector, at which point is has just about made one revolution around the LHC. This will be repeated for the beam going in the other direction around the LHC. Then in the coming days or weeks we will have two beams of protons in the LHC at the same time…and finally collisions!

by Adam Yurkewicz at November 20, 2009 05:01 AM

Michael Nielsen — Biweekly links for 11/20/2009

Your Looks and Your Inbox « OkTrends
- Utterly fascinating data-driven look at the dating market from someone who helps run a dating site.
Google Scholar now lets you restrict your search to legal opinions and journals
- I use Scholar’s advanced search pretty often, and only just noticed this – I presume it was added recently. Should be very handy.
Damn Cool Pics: Best Hand Painting Art Ever
- The title appears hyperbolic, but this is remarkable. I often had no idea I was looking at hand.
Steven Pinker on technology
- “Many of the articles in printed encyclopedias stink — they are incomprehensible, incoherent, and instantly obsolete. The vaunted length of the news articles in our daily papers is generally plumped out by filler that is worse than useless: personal-interest anecdotes, commentary by ignoramuses, pointless interviews with bystanders (”My serial killer neighbor was always polite and quiet”). Precious real-estate in op-ed pages is franchised to a handful of pundits who repeatedly pound their agenda or indulge in innumerate riffing (such as interpreting a “trend” consisting of a single observation). The concept of “science” in many traditional literary-cultural-intellectual magazines… is personal reflections by belletristic doctors. And the policy that a serious book should be evaluated in a publication of record by a single reviewer (with idiosyncratic agendas, hobbyhorses, jealousies, tastes, and blind spots) would be risible if we hadn’t grown up with it.”
A Speculative Post on the Idea of Algorithmic Authority « Clay Shirky
- “when people become aware not just of their own trust but of the trust of others: “I use Wikipedia all the time, and other members of my group do as well.” Once everyone in the group has this realization, checking Wikipedia is tantamount to answering the kinds of questions Wikipedia purports to answer, for that group. This is the transition to algorithmic authority. “
Geo Hashing
- “Geohashing is a method for finding an effectively random location nearby and visiting it: a Spontaneous Adventure Generator. Every day, the algorithm generates a new set of coordinates for each 1°×1° latitude/longitude zone (known as a graticule) in the world. The coordinates can be anywhere — in the forest, in a city, on a mountain, or even in the middle of a lake! Everyone in a given region gets the same set of coordinates relative to their graticule.
  
  As such, these coordinates can be used as destinations for adventures, à la Geocaching, or for local meetups.”
Zeroth Order Approximation: Summary dismissal
- When is it appropriate to dismiss an idea out of hand? “So I am not opposed in principle to the “summary dismissal” of an idea – a rejection that precedes a full discussion of the factual merits. Such judgments are necessary and inevitable. They are a legitimate part of the practical art of reason. Yet I am uneasy, because this kind of preemptive action carries obvious risks. After all, the idea that I reject might be a good one. If I never grant it a real hearing, how will I ever find out?”

Click here for all of my del.icio.us bookmarks.

by Michael Nielsen at November 20, 2009 04:54 AM

Steinn Sigurðsson — Taxing the Hidden Economy

There is a radical proposal in Iceland to restore the economy and rescue the nation from bankruptcy: expand the tax base to recover revenue from the extensive underground economy.

Read the rest of this post... | Read the comments on this post...

Terence Tao — UCLA Math Seeks Exceptional Student for Undergraduate Merit Scholarship

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

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

Eligibility Requirements:

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

Posted in advertising Tagged: scholarship, UCLA, undergraduate study

by Terence Tao at November 19, 2009 07:16 PM

November 19, 2009

John Baez — This Week's Finds in Mathematical Physics (Week 283)

John Baez

We had a great AMS meeting this weekend at UCR, with far too many interesting talks going on simultaneously. For example, there were two sessions on math related to knot theory, one on operator algebras, one on noncommutative geometry, and one on homotopy theory and higher algebraic structures! If I could clone myself, I'd have gone to all of them.

I'd like to discuss some of the talks, and maybe even point you to some videos. But the videos aren't available yet, so for now I'll just summarize my own talk on "Who Discovered the Icosahedron", and some geometry related to that. I'll conclude with a puzzle.

But first - the astronomy pictures of the week!

Galaxies are beautiful things, and there are lots of ways to enjoy them. Here's the Milky Way in visible light - a detailed panorama created from over 3000 individual pictures, carefully calibrated to show large dust clouds:

1) Axel Mellinger, All-sky Milky Way panorama 2.0, http://home.arcor.de/axel.mellinger/

You can see even more structure in this infrared panorama of the Milky Way, created by the Spitzer Space Telescope:

2) Astronomy Picture of the Day, GLIMPSE the Milky Way, http://apod.nasa.gov/apod/ap051216.html

The bright white splotches are star-forming regions. The greenish wisps are hot interstellar gas. The red clouds are dust and organic molecules like polycyclic aromatic hydrocarbons (see "week258"). The darkest patches are regions of cool dust too thick for Spitzer to see through.

But here's my favorite: the Andromeda Galaxy in viewed in ultraviolet light:

3) Astronomy Picture of the Day, Ultraviolet Andromeda, http://apod.nasa.gov/apod/ap090917.html

This was taken by Swift, NASA's ultraviolet satellite telescope. At this frequency, young hot stars and dense star clusters dominate the view. It's sort of ghostly looking, no?

Now for my talk on the early history of the icosahedron.

This continues the tale begun in "week236" and "week241". Someday it'll get folded into a paper on special properties of the number 5, and 5-fold symmetry:

4) John Baez, Who discovered the icosahedron?, talk at the Special Session on History and Philosophy of Mathematics, 2009 Fall Western Section Meeting of the AMS, November 7, 2009. Available at http://math.ucr.edu/home/baez/icosahedron/

The dodecahedron and icosahedron are the most exotic of the Platonic solids, because they have 5-fold rotational symmetry - a possibility that only exists for regular polytopes in 2, 3 or 4 dimensions. The dodecahedron and icosahedron have the same symmetry group, because they are Poincaré duals: the vertices of one correspond to faces of the other. But the icosahedron was probably discovered later. As Benno Artmann wrote:

The original knowledge of the dodecahedron may have come from crystals of pyrite, but in contrast the icosahedron is a pure mathematical creation.... It is the first realization of an entity that existed before only in abstract thought. (Well, apart from the statues of gods!)

I'm not sure it's really anything close to the first "realization of an entity that existed before only in abstract thought". But it may have been the first "exceptional" object in mathematics - roughtly speaking, an entity that doesn't fit into any easy pattern, which is discovered as part of proving a classification theorem!

Other exceptional objects include the simple Lie group E₈, and the finite simple group M₁₂. Intriguingly, many of these exceptional objects" are related. For example, the icosahedron can be used to construct both E₈ and M₁₂. But the first interesting classification theorem was the classification of regular polyhedra: convex polyhedra with equilateral polygons as faces, and the same number of faces meeting at each vertex. This theorem appears almost at the end of the last book of Euclid's Elements - Book XIII. It shows that the only possibilities are the Platonic solids: the tetrahedron, the cube, the octahedron, the dodecahedron and the icosahedron. And according to traditional wisdom, the results in this book were proved by Theatetus, who also discovered the icosahedron!

Indeed, Artmann cites an "an ancient note written in the margins of the manuscript" of Book XIII, which says:

In this book, the 13th, are constructed the five so-called Platonic figures which, however, do not belong to Plato, three of the five being due to the Pythagoreans, namely the cube, the pyramid, and the dodecahedron, while the octahedron and the icosahedron are due to Theaetetus.

You may know Theaetetus through Plato's dialog of the same name, where he's described as a mathematical genius. He's also mentioned in Plato's dialogue called the Sophist. In the Republic, written around 380 BC, Plato complained that not enough is known about solid geometry:

... and for two reasons: in the first place, no government places value on it; this leads to a lack of energy in the pursuit of it, and it is difficult. In the second place, students cannot learn it unless they have a teacher. But then a teacher can hardly be found....

Theaetetus seems to have filled the gap: he worked on solid geometry between 380 and 370 BC, perhaps inspired by Plato's interest in the subject. He died from battle wounds and dysentery in 369 after Athens fought a battle with Corinth.

But how certain are we that Theatetus discovered - or at least studied - the icosahedron? The only hard evidence seems to be this "ancient note" in the margins of the Elements. But who wrote it, and when?

First of all, if you hope to see an ancient manuscript by Euclid with a scribbled note in the margin, prepare to be disappointed! All we have are copies of copies of copies. The oldest remaining fragments of the Elements date to centuries after Euclid's death: some from a library in Herculaneum roasted by the eruption of Mount Vesuvius in 79 AD, a couple from the Fayum region near the Nile, and some from a garbage dump in the Egyptian town of Oxyrhynchus.

There are various lines of copies of Euclid's Elements. Comparing these to guess the contents of the original Elements is a difficult and fascinating task. Unfortunately, in the fourth century AD, the Greek mathematician Theon of Alexandria - Hypatia's dad - made a copy that became extremely popular. So popular, in fact, that for many centuries European scholars knew no line of copies that hadn't passed through Theon! And Theon wasn't a faithful copyist: he added extra propositions, lengthened some proofs, and omitted a few things too. It seems he wanted to standardize the language and make it easier to follow. This may have helped people trying to learn geometry - but certainly not scholars trying to understand Euclid.

In 1808, Francois Peyrard made a marvelous discovery. He found that the Vatican library had a copy of Euclid's Elements that hadn't descended through Theon!

This copy is now called "P". It dates back to about 850 AD. I would love to know how Peyrard got his hands on it. One imagines him rooting around in a dusty basement and opening a trunk... but it seems that Napoleon somehow took this manuscript from the Vatican to Paris.

In the 1880s, the great Danish scholar Johan Heiberg used "P" together with various "Theonine" copies of the Elements to prepare what's still considered the definitive Greek edition of this book. The all-important English translation by Thomas Heath is based on this. As far as I can tell, "P" is the only known non-Theonine copy of Euclid except for the fragments I mentioned. Heath also used these fragments to prepare his translation.

This is just a quick overview of a complicated detective story. As always, the fractal texture of history reveals more complexity the more closely you look.

Anyway, Heath thinks that Geminus of Rhodes wrote the "ancient note" in the Elements crediting Theatetus. I'm not sure why Heath thinks this, but Geminus of Rhodes was a Greek astronomer and mathematician who worked during the 1st century BC.

In his charming article "The discovery of the regular solids", William Waterhouse writes:

Once upon a time there was no problem in the history of the regular solids. According to Proclus, the discoveries of Pythagoras include "the construction of the cosmic solids," and early historians could only assume that the subject sprang full-grown from his head. But a better-developed picture of the growth of Greek geometry made such an early date seem questionable, and evidence was uncovered suggesting a different attribution. A thorough study of the testimony was made by E. Sachs, and her conclusion is now generally accepted: the attribution to Pythagoras is a later misunderstanding and/or invention.
The history of the regular solids thus rests almost entirely on a scholium to Euclid which reads as follows:
"In this book, the 13th, are constructed the 5 figures called Platonic, which however do not belong to Plato. Three of these 5 figures, the cube, pyramid, and dodecahedron, belong to the Pythagoreans; while the octahedron and icosahedron belong to Theaetetus."
Theaetetus lived c. 415-369 B.C., so this version gives a moderately late date; and it has the considerable advantage of seeming unlikely. That is, the details in the scholium are not the sort of history one would naively conjecture, and hence it is probably not one of the stories invented in late antiquity. As van der Waerden says, the scholium is now widely accepted "precisely because [it] directly contradicts the tradition which used to ascribe to Pythagoras anything that came along."
But probability arguments can cut both ways, and those scholars who hesitate to accept the scholium do so primarily because it seems too unlikely. There have been two main sticking places: first, the earliness of the dodecahedron in comparison with the icosahedron; and second, the surprising lateness of the octahedron. The first objection, however, has been fairly well disposed of. The mineral pyrite (FeS₂) crystallizes most often in cubes and almost-regular dodecahedra; it is quite widespread, being the most common sulphide, and outstanding crystals are found at a number of spots in Italy. Moreover it regularly occurs mixed with the sulphide ores, and underlying the oxidized ores, of copper; these deposits have been worked since earliest antiquity. Thus natural dodecahedra were conspicuous, and in fact they did attract attention: artificial dodecahedra have been found in Italy dating from before 500 BC. Icosahedral crystals, in contrast, are much less common. Hence there is no real difficulty in supposing that early Pythagorean geometers in Italy were familiar with dodecahedra but had not yet thought of the icosahedron.

Indeed, while I've heard that iron pyrite forms "pseudoicosahedra":

I've never seen one, while the "pyritohedra" resembling regular dodecahedra are pretty common:

The puzzle of why the octahedron showed up so late seems to have this answer: it was known earlier, but it was no big deal until the concept of regular polyhedron was discovered! As Waterhouse says, the discovery of the octahedron would be like the discovery of the 4rd perfect number. Only the surrounding conceptual framework makes the discovery meaningful.

So far, so good. But maybe the Greeks were not the first to discover the icosahedron! In 2003, the famous mathematician Michael Atiyah and the chemist Paul Sutcliffe wrote:

Although they are termed Platonic solids there is convincing evidence that they were known to the Neolithic people of Scotland at least a thousand years before Plato, as demonstrated by the stone models pictured in Fig. 1 which date from this period and are kept in the Ashmolean Museum in Oxford.

Figure 1. Stone models of the cube, tetrahedron, dodecahedron, icosahedron and octahedron.
They date from about 2000 BC and are kept in the Ashmolean Museum in Oxford.

Various people including John McKay and myself spread this story without examining it very critically. I did read Dorothy Marshall's excellent paper "Carved stone balls", which catalogues 387 carved stone balls found in Scotland, dating from the Late Neolithic to Early Bronze Age. It has pictures showing a wide variety of interesting geometric patterns carved on them, and maps showing where people have found balls with various numbers of bumps on them. But it doesn't say anything about Platonic solids.

Maps by Dorothy Marshall.
Left: balls with 3 or 4 knobs. Right: balls with 6 knobs.

In March of 2009, Lieven le Bruyn posted a skeptical investigation of Atiyah and Sutcliffe's claim. For starters, he looked hard at the photo in their paper:

... where's the icosahedron? The fourth ball sure looks like one but only because someone added ribbons, connecting the centers of the different knobs. If this ribbon-figure is an icosahedron, the ball itself should be another dodecahedron and the ribbons illustrate the fact that icosa- and dodecahedron are dual polyhedra. Similarly for the last ball, if the ribbon-figure is an octahedron, the ball itself should be another cube, having exactly 6 knobs. Who did adorn these artifacts with ribbons, thereby multiplying the number of "found" regular solids by two (the tetrahedron is self-dual)?

Who put on the ribbons? Lieven le Bruyn traced back the photo to Robert Lawlor's 1982 book Sacred Geometry. In this book, Lawlor wrote:

The five regular polyhedra or Platonic solids were known and worked with well before Plato's time. Keith Critchlow in his book Time Stands Still presents convincing evidence that they were known to the Neolithic peoples of Britain at least 1000 years before Plato. This is founded on the existence of a number of spherical stones kept in the Ashmolean Museum at Oxford. Of a size one can carry in the hand, these stones were carved into the precise geometric spherical versions of the cube, tetrahedron, octahedron, icosahedron and dodecahedron, as well as some additional compound and semi-regular solids...

But is this really true? Le Bruyn discovered that the Ashmolean owns only 5 Scottish stone balls - and their webpage shows a photo of them, which looks quite different than the photo in Lawlor's book!

They have no ribbons on them. More importantly, they're different shapes! The Ashmolean lists their 5 balls as having 7, 6, 6, 4 and 14 knobs, respectively - nothing like an icosahedron.

And here is where I did a little research of my own. The library at UC Riverside has a copy of Keith Critchlow's 1979 book Time Stands Still. In this book, we see the same photo of stones with ribbons that appears in Lawlor's book - the photo that Atiyah and Suttcliffe use. In Critchlow's book, these stones are called "a full set of Neolithic 'Platonic solids'". He says they were photographed by one Graham Challifour - but he gives no information as to where they came from!

And Critchlow explicitly denies that the Ashmolean has an icosahedral stone! He writes:

... the author has, during the day, handled five of these remarkable objects in the Ashmolean museum.... I was rapt in admiration as I turned over these remarkable stone objects when another was handed to me which I took to be an icosahedron.... On careful scrutiny, after establishing apparent fivefold symmetry on a number of the axes, a count-up of the projections revealed 14! So it was not an icosahedron.

It seems the myth of Scottish balls shaped like Platonic solids gradually grew with each telling. Could there be any truth to it? Dorothy Marshall records Scottish stone balls with various numbers of knobs, from 3 to 135 - but just two with 20, one at the National Museum in Edinburgh, and one at the Kelvingrove Art Gallery and Museum in Glasgow. Do these look like icosahedra? I'd like to know. But even if they do, should we credit Scots with "discovering the icosahedron"? Perhaps not.

So, it seems the ball is in Theaetetus' court.

Here are some references:

The quote from Benno Artmann appeared in a copy of the AMS Bulletin where the cover illustrates a construction of the icosahedron:

5) Benno Artmann, About the cover: the mathematical conquest of the third dimension, Bulletin of the AMS, 43 (2006), 231-235. Also available at http://www.ams.org/bull/2006-43-02/S0273-0979-06-01111-6/

For more, try this wonderfully entertaining book:

6) Benno Artmann, Euclid - The Creation of Mathematics, Springer, New York, 2nd ed., 2001. (The material on the icosahedron is not in the first edition.)

It's not a scholarly tome: instead, it's a fun and intelligent introduction to Euclid's Elements with lots of interesting digressions. A great book for anyone interested in math!

I should also get ahold of this someday:

7) Benno Artmann, Antike Darstellungen des Ikosaeders, Mitt. DMV 13 (2005), 45-50.

Heath's translation of and commentary on Euclid's Elements is available online thanks to the Perseus Project. The scholium crediting Theatetus for the octahedron and icosahedron is discussed here:

8) Euclid, Elements, trans. Thomas L. Heath, Book XIII, Historical Note, p. 438. Also available at http://old.perseus.tufts.edu/cgi-bin/ptext?doc=Perseus%3Atext%3A1999.01.0086&query=head%3D%23566

while the textual history of the Elements is discussed here:

9) Euclid, Elements, trans. Thomas L. Heath, Chapter 5: The Text, p. 46. Also available at http://old.perseus.tufts.edu/cgi-bin/ptext?lookup=Euc.+5

Anyone interested in Greek mathematics also needs these books by Heath, now available cheap from Dover:

10) Thomas L. Heath, A History of Greek Mathematics. Vol. 1: From Thales to Euclid. Vol. 2: From Aristarchus to Diophantus. Dover Publications, 1981.

The long quote by Waterhouse comes from here:

11) William C. Waterhouse, The discovery of the regular solids, Arch. Hist. Exact Sci. 9 (1972-1973), 212-221.

I haven't yet gotten my hold on this "thorough study" mentioned by Waterhouse - but I will soon:

12) Eva Sachs, Die funf platonischen Koerper, zur Geschichte der Mathematik und der Elementenlehre Platons und der Pythagoreer, Berlin, Weidmann, 1917.

I also want to find this discussion of how Peyrard got ahold of the non-Theonine copy of Euclid's Elements:

13) N. M. Swerlow, The Recovery of the exact sciences of antiquity: mathematics, astronomy, geography, in Rome Reborn: The Vatican Library and Renaissance Culture, ed. Grafton, 1993.

Here is Atiyah and Sutcliffe's paper claiming that the Ashmolean has Scottish stone balls shaped like Platonic solids:

14) Michael Atiyah and Paul Sutcliffe, Polyhedra in physics, chemistry and geometry, available as arXiv:math-ph/0303071.

Here is le Bruyn's critical examination of that claim:

15) Lieven le Bruyn, The Scottish solids hoax, March 25, 2009, http://www.neverendingbooks.org/index.php/the-scottish-solids-hoax.html

Here are the books by Critchlow and Lawlor -speculative books from the "sacred geometry" tradition:

16) Keith Critchlow, Time Stands Still, Gordon Fraser, London, 1979.

17) Robert Lawlor, Sacred Geometry: Philosophy and Practice, Thames and Hudson, London, 1982. Available at http://www.scribd.com/doc/13155707/robert-lawlor-sacred-geometry-philosophy-and-practice-1982

Here's the Ashmolean website:

18) British Archaeology at the Ashmolean Museum, Highlights of the British collections: stone balls, http://ashweb2.ashmus.ox.ac.uk/ash/britarch/highlights/stone-balls.html

and here's Dorothy Marshall's paper on stone balls:

19) Dorothy N. Marshall, Carved stone balls, Proc. Soc. Antiq. Scotland, 108 (1976/77), 40-72. Available at http://www.tarbat-discovery.co.uk/Learning%20Files/Carved%20stone%20balls.pdf

Finally, a bit of math.

In the process of researching my talk, I learned a lot about Euclid's Elements, where the construction of the icosahedron - supposedly due to Theaetetus - is described. This construction is Proposition XIII.16, in the final book of the Elements, which is largely about the Platonic solids. This book also has some fascinating results about the golden ratio and polygons with 5-fold symmetry!

The coolest one is Proposition XIII.10. It goes like this.

Take a circle and inscribe a regular pentagon, a regular hexagon, and a regular decagon. Take the edges of these shapes, and use them as the sides of a triangle. Then this is a right triangle!

In other words, if

is the side of the pentagon,

is the side of the hexagon, and

is the side of the decagon, then

P² = H² + D²

We can prove this using algebra - but Euclid gave a much cooler proof, which actually find this right triangle hiding inside an icosahedron.

First let's give a completely uninspired algebraic proof.

Start with a unit circle. If we inscribe a regular hexagon in it, then obviously

H = 1

So we just need to compute P and D. If we think of the unit circle as living in the complex plane, then the solutions of

z⁵ = 1

are the corners of a regular pentagon. So let's solve this equation. We've got

0 = z⁵ - 1 = (z - 1)(z⁴ + z³ + z² + z + 1)

so ignoring the dull solution z = 1, we must solve

z⁴ + z³ + z² + z + 1 = 0

This says that the center of mass of the pentagon's corners lies right in the middle of the pentagon.

Now, quartic equations can always be solved using radicals, but it's a lot of work. Luckily, we can solve this one by repeatedly using the quadratic equation! And that's why the Greeks could construct the regular pentagon using a ruler and compass.

The trick is to rewrite our equation like this:

z² + z + 1 + z^-1 + z^-2 = 0

and then like this:

(z + z^-1)² + (z + z^-1) - 1 = 0

Now it's a quadratic equation in a new variable. So while I said this proof would be uninspired, it did require a tiny glimmer of inspiration. But that's all! Let's write

z + z^-1 = x

so our equation becomes

x² + x - 1 = 0

Solving this, we get two solutions. The one I like is the golden ratio:

x = φ = (-1 + √5)/2 ~ 0.6180339...

Next we need to solve

z + z^-1 = φ

This is another quadratic equation:

z² - φ z + 1 = 0

with two conjugate solutions, one being

z = (φ + (φ² - 4)^½)/2

I've sneakily chosen the solution that's my favorite 5th root of unity:

z = exp(2πi/5) = cos(2π/5) + i sin(2π/5)

So, we're getting

cos(2π/5) = φ/2

A fact we should have learned in high school, but probably never did.

Now we're ready to compute P, the length of the side of a pentagon inscribed in the unit circle:

P² = |1 - z|²

     = (1 - cos(2π/5))² + (sin(2π/5))²

     = 2 - 2 cos(2π/5)

     = 2 - φ

Next let's compute D, the length of the side of a decagon inscribed in the unit circle! We can mimic the last stage of the above calculation, but with an angle half as big:

D² = 2 - 2 cos(π/5)

To go further, we can use a half-angle formula:

cos(π/5) = ((1 + cos(2π/5))/2)^½

= (½ + φ/4)^½

This gives

D² = 2 - (2 + φ)^½

But we can simplify this a bit more. As any lover of the golden ratio should know,

2 + φ = 2.6180339...

is the square of

1 + φ = 1.6180339...

So we really have

D² = 1 - φ

Okay. Your eyes have glazed over by now - unless you've secretly been waiting all along for This Week's Finds to cover high-school algebra and trigonometry. But we're done. We see that

P² = H² + D²

simply says

2 - φ = 1 + (1 - φ)

That wasn't so bad, but imagine discovering it and proving it using axiomatic geometry back around 300 BC! How did they do it?

For this, let's turn to

20) Ian Mueller, Philosophy of Mathematics and Deductive Structure in Euclid's Elements, MIT Press, Cambridge Massachusetts, 1981.

This is reputed to be be the most thorough investigation of the logical structure of Euclid's Elements! And starting on page 257 he discusses how people could have discovered P² = H² + D² by staring at an icosahedron!

This should not be too surprising. After all, there are pentagons, hexagons and decagons visible in the icosahedron. But I was completely stuck until I cheated and read Mueller's explanation.

If you hold an icosahedron so that one vertex is on top and one is on bottom, you'll see that its vertices are arranged in 4 horizontal layers. From top to bottom, these are:

1 vertex on top
5 vertices forming a pentagon: the "upper pentagon"
5 vertices forming a pentagon: the "lower pentagon"
1 vertex on bottom

Pick a vertex from the upper pentagon: call this A. Pick a vertex as close as possible from the lower pentagon: call this B. A is not directly above B. Drop a vertical line down from A until it hits the horizontal plane on which B lies. Call the resulting point C. If you think about this, you'll see that ABC is a right triangle. Greg Egan drew a picture of it:

And if we apply the Pythagorean theorem to this triangle we'll get the equation

P² = H² + D²

To see this, we only need to check that:

the length AB equals the edge of a pentagon inscribed in a circle;

the length AC equals the edge of a hexagon inscribed in a circle;

the length BC equals the edge of a decagon inscribed in a circle.

Different circles, but of the same radius! What's this radius? The 5 vertices of the lower pentagon lie on the circle shown in blue. This circle has the right radius.

Using this idea, it's easy to see that the length AB equals the edge of a pentagon inscribed in a circle. It's also easy to see that BC equals the edge of a decagon inscribed in a circle of the same radius. The hard part, at least for me, is seeing that AC equals the edge of a hexagon inscribed in a circle of the same radius... or in other words, the radius of that circle! (The hexagon seems to be a red herring.)

To prove this, it would suffice to show the following marvelous fact: the distance between the "upper pentagon" and the "lower pentagon" equals the radius of the circle containing the vertices of the upper pentagon!

Can you prove this?

In Mueller's book, he suggests various ideas the Greeks could have had about this. Here's one:

The right triangle ABC is shown here. The trick is to construct another right triangle AB'C'. Here B' is the top vertex, and C' is where a line going straight down from B' hits the plane containing the upper pentagon.

Remember, we're trying to show the distance between the upper pentagon and lower pentagon equals the radius of the circle containing the vertices of the upper pentagon.

But that's equivalent to showing that AC' is congruent to AC.

To do this, it suffices to show that the right triangles ABC and AB'C' are congruent! Can you do it?

In the references to Mueller's book, he says the historians Dijksterhuis (in 1929) and Neuenschwander (in 1975) claimed this is "intuitively evident". But I don't know if that means it's easy to prove!

I thank Toby Bartels and Greg Egan for help with this stuff. I also thank Jim Stasheff for passing on an email from Joe Neisendorfer pointing out Mellinger's picture of the Milky Way.

Addendum: Kevin Buzzard explained some of the Galois theory behind why the pentagon can be constructed with ruler and compass - or in other words, why the quartic

z⁴ + z³ + z² + z + 1 = 0

can be solved by solving first one quadratic and then another.

He wrote:

Now, quartic equations can always be solved using radicals
That's because S₄ is a solvable group, and all Galois groups of quartics will live in S₄ (and will usually be S₄)...
Luckily, we can solve this one by repeatedly using the quadratic equation!

("this one" being z⁴ + z³ + z² + z + 1 = 0.)
...and that's because the Galois group of that specific irreducible polynomial is "only" cyclic of order 4. The splitting field is Q(ζ₅), which is a cyclotomic field, so has Galois group (Z/5Z)*. No Z/3Z factors so no messing around with cube roots, for example...

So while I said this proof would be uninspired, it did require a tiny glimmer of inspiration.

With this observation above, I'm trying to convince you that the proof really is completely uninspired To solve the quartic by solving two quadratics, you need to locate the degree 2 subfield of Q(z) (z=ζ₅) and aim towards it (because it's your route to the solution). This subfield is clearly the real numbers in Q(z), and the real numbers in Q(z) contains z+z*=z+z^-1. So that's sort of a completely conceptual explanation of why the trick works and why it's crucial to introduce z+z^-1.

Greg Egan gave a nice modern version of Euclid's original proof of Prop. XIII.10, which states that if you take take a circle and inscribe a regular pentagon, a regular hexagon, and a regular decagon, and make a triangle out of their sides, it's a right triangle!

Here's a version of the proof Euclid gave, adapted from the version JB cited. Rather than proving that various angles here are identical, I've just written in the (easily established) numerical values; there's nothing tricky here, so we might as well take them as given.

Triangle ABF is similar to triangle BFN. So AB/BF = BF/FN = BF/BN, with the last equality true because the triangles are isosceles with FN = BN. Thus BF ² = AB · BN

Triangle BAK is similar to triangle KAN. So BA/AK = KA/AN. Thus AK² = AB · AN.

Adding our two results, we have: BF² + AK² = AB · (AN + BN) = AB².

BF is our radius, AK is a decagon side, and AB is a pentagon side. Well done Euclid.

For more discussion visit the n-Category Café.

Geometry enlightens the intellect and sets one's mind right. All its proofs are very clear and orderly. It is hardly possible for errors to enter into geometric reasoning, because it is well arranged and orderly. Thus the mind that constantly applies itself to geometry is unlikely to fall into error. - Ibn Khaldun

_{-- Delivered by Feed43 service}

November 19, 2009 06:23 PM

Terence Tao — Nonstandard analogues of energy and density increment arguments

In the course of the ongoing logic reading seminar at UCLA, I learned about the property of countable saturation. A model ${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.

Posted in Logic reading seminar, math.CO, math.LO Tagged: countable saturation, nonstandard analysis

by Terence Tao at November 19, 2009 06:15 PM

Edinburgh Mathematical Physics Group — Samson Shatashvili’s EMPJ Talk

This week’s EMPJ talk was given by Samson Shatashvili, where he explained some relations between SYM theories and quantum integrable systems. In particular, we learned how every 2d SYM theory can be identified with a quantum integrable system. We began by looking at 4d SYM theories, and how these may be nicely reduced to two [...]

by joshua at November 19, 2009 03:57 PM

Resonaances — Fermi says "nothing"...like sure sure?

I wrote recently about a couple of theory groups who claim to have discovered intriguing signals in the gamma-ray data acquired by the Fermi satellite. The Fermi collaboration hastened to trash both these signals, visibly annoyed by pesky theorists meddling in their affairs. Therefore a status update is in order. Then I'll move to realizing the holy mission of yellow blogs, which is spreading wild rumors.

The first of the theorist's claims concerned the gamma-ray excess from the galactic center, allegedly consistent with a 30 GeV dark matter particle annihilating into b-quark pairs. The

relevant data are displayed on this plot released recently by Fermi, which shows the gamma-ray spectrum in the seven-by-seven degrees patch around the galactic center. There indeed seems to be an excess in the 2-4 GeV region. However, given the size of the error bars and of the systematic uncertainties, not to mention how badly we understand the astrophysical processes in the galactic center, one can safely say that there is nothing to be excited about for the moment.

The status of the Fermi haze is far less clear. Here is the story so far. In a recent paper, Doug Finkbeiner and collaborators looked into the Fermi gamma-ray data and found an evidence for a

population of very energetic electrons and positrons in the center of our galaxy. These electrons would emit gamma rays when colliding with starlight, in the process known as inverse Compton scattering. They would also emit microwave photons via synchrotron radiation, of which hints are present in the WMAP data. The high-energy electrons could plausibly be a sign of dark matter activity, and fit very well with the PAMELA positron excess, although one cannot exclude that they are produced by conventional astrophysical processes. But Fermi argues that there is no haze in their data. During the Fermi Symposium last week the collaboration was chanting anti-haze songs and tarred-and-feathered anyone humming Hazy shade of winter. Interestingly, it seems that each collaboration member has a slightly different reasons for doubts. Some say the haze is just heavy cosmic-ray elements faking gamma-ray photons. Some say the haze does exist but it can be easily explained by tuned-up galactic models without invoking an energetic population of electrons. Some say the haze is LOOP-1 - a nearby supernova remnant that happens to lie roughly in the direction of the galactic center. But none of the above explanations seems to be on a firm footing, and the jury is definitely out. In the worst case, the matter should be clarified by the Planck satellite (already up in the sky) who is going to make more accurate maps of photon emission at lower frequencies that will lead to a better understanding of astrophysical backgrounds.

And now wild rumors... which, let's make it clear, are likely due to daydreaming over-imagination of data-hungry theorists. The rumors concern Fermi's search for subhalos, which is one of the most promising methods of detecting dark matter in the sky. Subhalos are dwarf galaxies orbiting our Milky Way who are made almost entirely of dark matter. Two dozens of subhalos have been discovered so far (by observing small clumps of stars that they host) but simulations predict several hundreds of these objects. The darkest of the discovered subhalos has a mass-to-light ratio larger than a thousand, indicating large concentration of dark matter. Because of that, one expects dark matter particles to efficiently annihilate and emit gamma rays (typically, via final state radiation or inverse Compton scattering of the annihilation products). Although the resulting gamma-ray flux is expected to be smaller than that from the galactic center, the subhalos with its small visible matter content offer a much cleaner environment to search for a signal.

So, Fermi is searching for spatially extended object away from the galactic plane that steadily emit a lot of gamma rays but are not visible in other frequencies. The results based on 10-months data have been presented in this poster. Apparently, they found no less than four candidates at the 5-sigma level!!! However, according to the poster, these candidates do not fit the spectra of three random dark matter models. For this reason, the conclusion of the search is that no subhalos have been detected, even though it is not clear what astrophysical processes could produce the signal they have found.

Well, I bet an average theorist would need fifteen minutes to write down a dark matter model fitting whatever spectrum Fermi has measured. On the other hand, the collaboration must have better reasons, not revealed to us mortals, to ditch the candidates they have found. On yet another hand, the fact that Fermi is not revealing the positions and the measured spectra of these four candidates makes the matter very very intriguing. So, we need to wait for more data. Or for a snitch :-)

by Jester at November 19, 2009 03:37 PM

Cosmic Variance — A Conversation on the Existence of Time

You know, other people talk a lot about time, too — it’s not just me. Here’s a great video from Nature, featuring a conversation between David Gross and Itzhak Fouxon about the existence of time. (Via Sarah Kavassalis.) Itzhak plays the role of the starry-eyed young researcher — he opens the video by telling us how he originally went into physics to impress girls, although apparently he has stuck with it for other reasons. Gross, of course, shared a Nobel Prize for asymptotic freedom, and has become one of the most influential string theorists around. David plays the role of the avuncular elder statesman (I’ve seen him be somewhat more acerbic in his criticisms) — but he’s one of the smartest people in physics, and his admonitions are well worth listening to. He gives some practical advice, but also advises young people to think big.

Unfortunately the video doesn’t seem to be embeddable, but you can go to the video page and click on the “David Gross” entry. (The others are good, too!)

You all know my perspective here — time probably exists, and we should try to understand it rather than replace it. But I’ll agree with David — let’s not ignore more “practical” problems, but not be afraid to tackle the big ideas!

by Sean at November 19, 2009 03:27 PM

US/LHC Blog — CMS Detector Control Room

I’m getting word there will be circulating beams as early as tomorrow evening – another LHC milestone! (As mentioned on CERN twitter) First collisions are not too far away after that.

This image above is an almost-live updated image of the CMS control room – this is one of the two general-purpose detectors at CERN. (See image correctly at the US LHC blog site) Using some fancy CSS I overlaid some text of the different areas in the room.

I’ll be on shift in the Trigger area starting next week. There’s about 6 wide-screen monitors back there that I’ll be watching to keep track of (too) many things. (The Trigger decides what collision events to record or throw away.)

Feel free to spy on people in there. Geneva is +6 hours from New York and +9 hours from Seattle, so it might be late there compared to your time, but people are on shift 24 hours a day!

by Mike Anderson at November 19, 2009 03:11 PM

Chad Orzel — I Can Haz Books!

It's not often that I regret having a cell phone that is just a phone, but this is one of those occasions-- I stopped by my publisher today to talk about marketing and publicity, and record a video for the web, and got a stack of finished copies of the book, hot off the presses. If I had a cell phone camera, I'd post a picture, but I don't, so you'll have to settle for a plain-text "Woo-hoo!"

On an only vaguely related note, our cultural activities in NYC will include some college hoops, as there's a preseason "tournament" taking place at Madison Square garden tonight. Syracuse vs. Cal, and UNC vs. Ohio State. Not a bad double bill for November basketball.

Read the comments on this post...

Mark Chu-Carroll — The Balance of Screening Tests

As you've no doubt heard by now, there's been a new recommendation issues which proposes changing the breast-cancer screening protocol for women under 50, by eliminating mammograms for women who don't have significant risk factos. While Orac has done a terrific job of covering this here and here, I wanted to throw in a couple of notes and a personal perspective.

Read the rest of this post... | Read the comments on this post...

Tommaso Dorigo — New Tevatron Higgs Limits Got Worse, But The 115 GeV Excess Is Growing!

It happens in the best families, so they say. Two experiments work 24/7 to produce an improved result on the Higgs search, and the result is disappointing, to say the least.

I am talking about the Tevatron, of course. For a little while longer, CDF and D0 will have the exclusive on Higgs boson searches. Last March, we all rejoyced when we saw that the Tevatron was starting to become sensitive to a high-mass Higgs, and indeed it excluded its existence in a range of masses between 160 and 170 GeV. We were waiting for more exclusions for the winter conferences of 2010, when more data would be used to produce improved results. Instead, no improvement, but actually, a retractatio. How is that possible ??

by dorigo at November 19, 2009 02:44 PM

Dave Bacon — Mmmvelopes. Tasty Tasty Mmmvelopes.

Too often in life I am sending out a check to some charitable organization, or to resubscribe to Bacon magazine, and I think "damn this would be a lot better with Bacon." And now via the honest one, I find out that there is a solution to this vexing problem: Bacon flavored envelopes! From the "learn more" section of the webstie:

Technology has given us a lot lately. The car. TV. X-rays. The refrigerator. The Internet. Heck, we even cured polio. But what have our envelopes tasted like for the last 4,000 years? Armpit, that's what.

Really, people? If we can't overcome this kind of minor technical challenge, it's only a matter of time until some super-advanced race of aliens with lasers, spaceships and a delicious federal mail system comes down and colonizes the world. And nobody wants that (except for the aliens, of course).

So, after thousands of years and kajillions of horrible tasting envelopes licked, we're happy to report that J&D's Bacon-Flavored Mmmvelopes™ are here to save the day. No longer will envelopes taste like the underside of your car. You can enjoy the taste of delicious bacon instead.

That's right, bacon. It's not real bacon, mind you, so you won't have to start storing your envelopes in the refrigerator. But it really does taste like bacon. Which is what you really wanted in the first place, isn't it? And it only took us 4,000 years to get there. Eat that, alien invaders.

Cool, but I beg to differ. My armpit smells like....Bacon!

Read the comments on this post...

Backreaction — Causal Diagrams

I once witnessed a physicist explain the universe to an artist. The artist had approached the physicist to learn how to understand extra dimensions, a concept, so he explained, that would undoubtedly enhance the depth of his artwork, and be of great inspirational value for his quest to capture the contextuality of essence. Or maybe essence of contextuality. Or something like that. Either way, the physicist took a piece of chalk and drew a line on the blackboard. "That is our universe," he said. It took several minutes before the artist stopped laughing and said "Now THAT is what I'd call an abstraction."

You see, the fact that our universe is at least 4-dimensional and infinitely large (or damned close to that) creates some problem with visualization. The average blackboard is 2-dimensional, somewhat smaller than infinite, and my female brain already finds 3d plots messy and confusing. Add to this that most physicists aren't particularly great in drawing the universe.

Thus arises the need to picture 4 dimensions in an intuitive and illuminating way. Penrose-Carter diagrams, also called "causal diagrams," do exactly that. Though they do not work for the most general space-times, but only when additional symmetries simplify the scenario, they capture the essence of a 4-dimensional space-time. Or maybe the essence of 4-dimensional contextuality.

Understanding causal diagrams is one of the most basic skills you need if you want to work in General Relativity.

It works like this.

First, we have the problem of getting 4 dimensions down to 2, where one of the 4 dimensions is time. That's not so complicated. We will assume that space is spherically symmetric, such that when you sit in one point, all directions from that point look similar. This would be the case for example if you sat in the middle of a ball or, to reasonably good precision, if you sat in the middle of the Earth. The only interesting information is then in the change of scenery as a function of the distance from you, who you are sitting in the center of symmetry. We can thus capture the full 3 space dimensions by just considering what happens with the distance to the center of symmetry. This distance is of course just the radial coordinate r. Besides that, we will draw the time-coordinate t, which is usually depicted vertically, whereas r is horizontally. This is shown in the picture below, left. You've seen that before.

An infinitely flat 4-dimensional space-time is then just a half-plane. Note that a flat space is spherically symmetric around every point. (If you want to nitpick, what I mean with "flat" is that the curvature tensor identically vanishes.)

Next thing we do is to notice that if we had a particle moving towards the center of symmetry at r=0, passing through it, and moving away from it again, it would look on the half-plane like a reflection instead. Sometimes we thus mirror the half-plane to the other side, such that the curves of particles just go through. Keep in mind though that r increases in both directions. The world-lines of particles with a fixed velocity move on straight lines in that plane. Don't try to draw curves for particles that do not approach the center radially because the symmetry doesn't allow it. We now adopt the first convention for causal diagrams:

Light moves on 45° angles.

Curves on which light moves are called "lightlike," or, due to their property of having zero length in a Minkowski-metric, "null curves."

The next step is more tricky, because now we have to deal with the infinitely large space. How

do we get it to fit on a blackboard? If you have ever done perspective drawing, you know the answer already. The "horizon line" and the "vanishing points" depict the infinite distance on a finite sheet of paper. The price to pay is that what is equally spaced far away, moves closer and closer together on the 2-dimensional picture. An example is the photo with railroad tracks to the right.

To draw a picture of an infinite space-time, we do exactly the same: we make infinity finite by squeezing together what is far away. Since the space-time is infinite in more than one direction an additional assumption is that we

Squeeze infinity equally in all directions.

The resulting squeeze is also called a "conformal transformation," and has the merit of preserving angles, such that most importantly null curves still move on 45°, no matter which

such transformation you used. There are many different squeezes, though qualitatively they look all similar. An example for an often used squeeze is the tangent function in the interval [-π/2,π/2], shown to the left. If you take equal spaces on the vertical axis, the corresponding values on the horizontal axis produce a no longer evenly spaced representation of that infinite vertical axis.

If we now go and squeeze our flat space-time what we get is a diamond.

In this diagram, spacelike curves always have angles less than 45°, and timelike curves on which particles can move have angles more than 45° (in every point). All spacelike curves come from and end in the side corners, called "spacelike infinity," whereas timelike curves all come from the bottom corner and end in the upper corner, called "past timelime infinity" and "future timelike infinity," rspt. Light comes from the lower V-shaped boundary and end at the upper Λ-shaped boundary, called "past null infinity" and "future null infinity." The null infinities are usually denoted with an I in a script font, and are thus for short often called "scri minus" for past null infinity and "scri plus" for future null infinity.

So far so good, but flat Minkowski space is admittedly somewhat boring. Let us thus look at something more interesting. The causal diagram of the maximally analytically extended Schwarzschild-solution, describing a static black hole. You have seen it thousands of times in the header of this website.

It is futile trying to explain how to obtain the diagram without telling you what a metric is and what to do with it, but the big advantage of these diagrams is exactly that you can learn something about the space-time properties without bothering with tensor equations, so let's see.

The first thing you will notice is that the diagram contains regions (A and B) that cannot be connected by any lightlike or timelike curve. This means there is no way to send information from one to the other, and A and B are thus causally disconnected. You will also see that there are two spacelike boundaries on the bottom and top where time- and lightlike curves end without having reached infinity. The spacetime is thus geodesically incomplete or, equivalently, has singularities. The maybe most important property to identify is the boundary of the region from which lightlike curves can reach future null infinity. If not at an infinite distance, this boundary it is called a future event horizon. Similarly, the boundary of the region to which light can be send from past null infinity is a past event horizon. These horizons are always lightlike surfaces.

When you're done thinking, take time to see how pretty it is.

This Schwarzschild-metric does not only depict a black hole in the upper part, which contains a region where no information can ever come out to future infinity, but also a region in the lower part where no information can ever get in from past infinity. That second region is called a white hole. It is however a mathematical artifact since this diagram describes an unrealistic situation: a black hole that has been there since forever and will be there until eternity. In reality, black holes are formed from collapsing matter and later evaporate. We will discuss the more realistic diagram in another post, so stay tuned.

Finally, upon Googling for images I found that somebody else had used the same motivation from perspective drawing that I came up with. Well. If one thousand monkeys hit they keyboard for long enough, they will eventually type the complete Misner, Thorne, Wheeler. Not only once, but an infinite amount of time.

If you arrived here by just scrolling down, shame on you. The minimum amount of information you should take home is that Penrose-Carter diagrams, aka "causal diagrams," are used to depict the causal properties of 4-dimensional space-times with additional symmetries.

by Bee at November 19, 2009 12:28 PM

Clifford Johnson — Market Matters

As you may know from earlier posts, I love markets, a place where people come together with lots to see, talk about, interact over, and of course to taste. Community. One of my favourite things. Here's a lovely stall at Granville Island in Vancouver when I was there briefly a short while ago. (Click for larger view.)

I can't resist showing you this display: (Click for larger view.) [...]

by Clifford at November 19, 2009 11:33 AM

US/LHC Blog — New Higgs search results from the Tevatron

At this week’s Hadron Collider Physics Symposium, the CDF and D0 experiments at the Tevatron announced their newest results on the search for a standard-model Higgs boson. You can find documentation from the two experiments here, and this is what the “money plot” looks like:

tevcomb_nov6 The mass range 163-166 GeV is excluded at 95% confidence level. Now, for comparison, here is what this plot looked like in March:

fig4 At that time, the exclusion range was stated as 160-170 GeV. More data, but the excluded range got smaller? Indeed so. However, the real figure of merit for the reach of the search is indicated by the dotted line on both plots, which indicates how well you expect to do. This is what is used to design the data analyses — not what you get from the data themselves, as looking at the actual data can bias your results. As of March, we would have expected not to be able to exclude any Higgs production at all, and lucky (or unlucky?) fluctuations made the data look more background-like than Higgs-like, and thus the experiments were able to set a limit. But now the dotted line is lower on the plot, and below the standard-model line over a small region, so now it is expected that we set a limit, and the data are consistent with that…but the actual observed limit has gotten worse. As we like to say, you get what you get.

Fermilab will continue to take data and improve these limits — or, for all we know, discover a standard-model Higgs. The turn-on of the LHC, which is expected to continue this weekend, will bring more players into the game.

by Ken Bloom at November 19, 2009 11:32 AM

n-Category Café Cobordism and Topological Field Theories Week 3

$MathML-enabled post (click for more details).$

Welcome to week 3 of the cobordism and TFT seminar at UCR. The previous lecture by Julie Bergner can be found here. There she talked about categories of cobordisms.

In the present lecture, Julie introduces symmetric monoidal categories and defines a notion of topological field theory.

To keep everyone apprised of the state of this seminar, I should say that in “real time” we are about to hit week 9. In “blog time” we are still not caught up, but I am sure we will get there soon. The nice thing is that I can give you a preview of the weeks to come below the fold.

$MathML-enabled post (click for more details).$

Here is lecture 3. Enjoy and please keep the great comments coming. Although these notes are taking some time to hit the blog, they are coming to you with very little polishing. So it would be nice at some point to go back in and fill in details as well as add any relevant commentary from the blog.

A glimpse into the future: Weeks 4 and 5 (coming soon) are lectures by Chris Carlson and John Huerta, respectively. Chris talks about topological field theories in low dimensions and John gives a short history of the interaction between quantum field theory and topology.

Chad Orzel — Thursday Baby Blogging 111909

Actually, this ought to be "Wednesday Morning Baby Blogging," as that's when the picture was taken. Kate and I are going to New York City for the weekend, though, and SteelyKid is spending the weekend with Grandma and Grandpa in Scenic Whitney Point. So, you get an early picture, posted late:

This was taken just before we bundled her off to day care Wednesday. Kate's playing the "got your red dog" game-- for some reason, when you pop the pacifier out of SteelyKid's mouth, she finds it hilarious. Provided that you give it back pretty quickly, that is...

Read the comments on this post...

n-Category Café Mathematical Emotion

$MathML-enabled post (click for more details).$

Continuing the season of Collingwood on mathematics, here is an extract from The Principles of Art (1938):

A symbol is language and yet not language. A mathematical or logical or any other kind of symbol is invented to serve a purpose purely scientific; it is supposed to have no emotional expressiveness whatever. But when once a particular symbolism has been taken into use and mastered, it reacquires the emotional expressiveness of language proper. Every mathematician knows this. At the same time, the emotions which mathematicians find expressed in their symbols are not emotions in general, they are the peculiar emotions belonging to mathematical thinking. (p. 268)

[‘Symbol’ is used here to mean “something arrived at by agreement and accepted by the parties to the agreement as valid for a certain purpose” (p. 225).]

Anyone who doubts such ‘emotions belonging to mathematical thinking’ exist need only read an edition or two of This Week’s Finds. They are dripping with emotion, as the modern phrase has it.

$MathML-enabled post (click for more details).$

Collingwood continues:

The same applies to technical terms. These are invented solely to serve the purpose of a particular scientific theory; but as they begin to pass current in the scientist’s speech or writing they express to him and to those who understand him the peculiar emotions which that theory yields. Often, when invented by a man of literary ability, thay are chosen from the first with an eye to expressing these emotions as directly and obviously as possible. Thus, a logician may use a term like ‘atomic propositions’ as part of his technical vocabulary. The word ‘atomic’ is a technical term, that is a word borrowed from elsewhere and turned into a symbol by undergoing precise definition in terms of the theory. Sentences in which it occurs can be subjected to homolingual translation. But, as we find it occurring in the logician’s discourse, it is full of emotional expressiveness. It conveys to the reader, and is meant to convey, a warning and a threat, a hope and a promise. ‘Do not try to analyse these; renounce the dream of analysing to infinity; that way delusion lies, and the ridicule of people like myself. Walk boldy, trusting in the solida simplicitas of these propositions; if you use them confidently as bricks out of which to build your logical constructions, they will never betray you.’ (pp. 268-269)

Now who has the best example of a mathematical term for which we can construct a similarly intricate account of its emotional expressiveness? Candidates include imaginary numbers, sober spaces, pseudofunctor, and the fundamental theorem of algebra. But we shouldn’t overlook less obvious terms such as inhabited set which express a decidedly constructivist emotion. It is interesting also to see how the emotion may drain from a term as it ages. Perhaps people these days tend to play it safe to avoid their patently loaded name later looking ridiculous.

I have the next two paragraphs by Collingwood here, ending with

The progressive intellectualization of language, its progressive conversion by the work of grammar and logic into a scientific symbolism, thus represents not a progressive drying-up of emotion, but its progressive articulation and specialization. We are not getting away from an emotional atmosphere into a dry, rational atmosphere; we are acquiring new emotions and new means of expressing them. (p. 269)

If so, we could understand that commonly met thought that learning mathematics is good for the soul in terms of its capacity to shape the emotions for the better.

Edinburgh Mathematical Physics Group — In Japan too they cook beans

The title of this post comes from the Spanish proverb En todos sitios cuecen habas, which simply points out — as if it were needed — the universality of certain things, usually bad ones. An article in Nature News published two day ago reports on severe budget cuts to some scientific programmes in Japan and possibly [...]

by José at November 19, 2009 02:33 AM

John Terning — Adopt a Physicist

Every October the the American Physical Society and other physics organizations arrange for high school classes to adopt a physicist. Then for a few weeks the students get to ask their physicist questions directly, on topics ranging from what the current hot topics are, to what it is like to be a scientist. If you want to volunteer for next year, or have your class adopt a physicist, go to www.adoptaphysicist.org.

This year I was adopted by Terrill Middle School in Scotch Plains, New Jersey. Here are some of the Q&A sessions.

	What is the most interesting or unusual thing you have worked on?
	One very interesting thing that I worked on was an idea about the hypothetical particles known as axions. You may have heard that the expansion of the Universe is accelerating rather than slowing down as people used to think, and that the most likely explanation is that the Universe is full of “dark energy”. The evidence for this acceleration comes mostly from distant supernovae (very bright exploded stars) that seem to be more dim the further away they are than could be accounted for by the expansion of the Universe without dark energy. We studied whether photons (particles of light) could be converted to axions, which would then be invisible to us. We found that over very long distances about 1/3 of the light from a supernova could have been converted to axions. If this is true then we wouldn’t need something as strange as dark energy. You can read more at http://particle.physics.ucdavis.edu/axion.php
	Where do you find your inspiration? How do you think of original ideas?
	It’s hard to say where inspiration comes from, but when you have worked on something for a long time it gets easier to spot where there might be possible new connections of ideas. After the Large Hadron Collider starts running we will be getting new data and there will probably be some surprises that cannot be explained by things we know already.
	What sparked your interest in Physics?
	When I was in High School I read a lot of science fiction, and my ambition was to become a science fiction writer. I thought I should study science at University, so that I would have a good grounding for my stories. When I got to University I found out that science was more interesting than science fiction.
	How is your approach to science different from when you were in high school?
	I think in high school I mostly approached science as learning a bunch of discovered facts about the world, but what I’ve learned is that science is a process for finding out new things about the ourselves and the universe. It is a process that may never end. The process is definitely more exciting than memorizing facts.
	Is being a physicist hard at first and easy later, or hard all the time? Do you like your job as a physicist?
	It is always hard because you are always trying to learn new things. But as you do more of it the challenges are at a higher level, and it is not as frustrating as it can be at the beginning. I love my job as a physicist!
	I would like to know at what age did you show signs of interest at becoming a scientist and how much education you needed to succeed being a scientist.
	I was interested in science in high school, but I was more interested in science fiction. I did not decide to become a scientist until I went to university and learned more about it. I spent four years as an undergraduate and six years as a graduate (doctoral) student at university.
	I would like to know what projects are you currently working on.
	I have two main projects currently. One is on how to deal with quarks in high energy collisions. When quarks are close together they behave like ordinary electrons, except that in addition to emitting photons (particles of light) they can also emit gluons. Gluons are much more complicated that photons since two photons can pass right through each other without having any effect on each other (you can try it with two flashlights, the beams really do go right through each other) but two gluons have a big effect on each other. The effect is so big that one needs to run a gigantic computer simulation to find out what happens. The results of such simulations suggest that when quarks are far apart they behave like they are always attached to the end of a string (the string is made out of gluons in a very complicated way). That is why you never see just a single quark by itself, if you try to pull it away the string breaks and you end up with two strings that have a quark (or antimatter quark) on each end. We are working on how to do improved calculations just using the string picture directly. The other project involves monopoles. Every magnet has a North and a South pole, but a long time ago P.A.M. Dirac suggested that there could be particles that have just a North pole or just a South pole, which are called monopoles (mono means one; a magnet has two poles, so it is a dipole). We are exploring what would happen to massless monoples as the Universe cooled after the big bang. In some cases the monopoles would behave like electrons in a superconductor and not only give mass to themselves but all the other particles we know. This type of theory will be tested at the Large Hadron Collider which should start running next month.
	What is the most fun or interesting part about your job?
	The most fun part of the job is coming up with new models of how Nature works and then trying to test them against reality.
	What skills or personality traits are important for someone working in your field?
	As far a skills go the most important skill is imagination, after that a little math helps too. For personality traits, I think that, as in a lot of fields, the most important factor is determination, also known as dedication, stick-to-it-ness, or just plain stubbornness. You have to keep trying, and trying, and trying again until you find an answer to your question. Just as in sports or music the great players are people who practice, practice, practice because they are so determined to get better. That probably means that you if you want to be really good at something, you need to find something that you love doing.
	What is a typical day like?
	A typical day involves: 1) checking email and looking at the latest research papers which appear each day on the web at http://www.arxiv.org/ especially http://www.arxiv.org/list/hep-ph/new and http://www.arxiv.org/list/hep-th/new; 2) there are typically so many new papers that I can only read a few of these; 3) lecturing to either undergraduate or graduate students on bio-physics, quantum mechanics ,or quantum field theory, this also requires preparing the lectures; 4) having discussions with students either to help them with their courses or the research they are doing with me; 5) having discussions with colleagues (usually next to a white board or chalk board so that we can write some equations) trying to generate new ideas to solve research problems; 6) doing calculations on paper or on a computer to see if our ideas actually work the way we thought; 7) typing up the results for a research paper (we use free software called LaTeX that makes it easier to include equations); going to seminars where visitors from other universities present their latest research results; 9) occasionally I will attend a faculty meeting or committee meeting to discuss the operations of the physics department.

by terning at November 19, 2009 12:29 AM

Steinn Sigurðsson — lateral thinking on your toes

Ethan at Starts With A Bang did a nice post the other day on an old chestnut - why you can't touch your toes if you're backed against a wall.

Read the rest of this post... | Read the comments on this post...

Steinn Sigurðsson — proposal invariance

Hubble multicycle large proposals were due today...
Julianne tests the conjecture of proposal number invariance under simple scaling.

Looks to be annoyingly close to correct with about 40 proposals in by the deadline.

I still think we need to check the proposal success probability as a function of proposal rank number.

Read the comments on this post...

November 18, 2009

Doug Natelson — Not even wrong.

No, this is not a reference to Peter Woit's blog. Rather, it's my reaction to reading this and the other pages at that domain. Wow. Some audiophiles must really be gullible.

by Doug Natelson at November 18, 2009 08:35 PM

David Hogg — nothing

With getting ready for travel, nada.

by Hogg at November 18, 2009 08:04 PM

Chad Orzel — Poll: New York State of Mind

Kate has a court appearance in New York tomorrow, and we're making a long weekend of it. I'm typing this from my parents' house, where I'm dropping SteelyKid off for some quality time with Grandma and Grandpa, and tomorrow, I'm heading down to The City. I've got some meetings scheduled tomorrow afternoon, and Friday at lunch, and then we're going to kick back and enjoy New York.

Of course, one of the paralyzing things about NYC is the sheer variety of cultural options. There's the AMNH, with lots of geeky exhibits, the Met, where you can spend days and not see everything, and MOMA, for a different sort of art experience. I've looked at the web sites for all of them, and none of the current exhibits looked like can't-miss shows to me. And it's too late in the year for the Bronx Zoo or the Cloisters.

So, we'll throw this out to a poll: What should we go see during our free time in The City this weekend?

<a href="http://answers.polldaddy.com/poll/2273764/">What cultural activity should Kate and I do on our trip to NYC?</a><span style="font-size:9px;">(<a href="http://www.polldaddy.com">polls</a>)</span>

Please choose only one. We don't promise to abide by the results of the poll, but suggestions are welcome.

Read the comments on this post...

Cosmic Variance — Explaining Time, the Universe, and All That

Greetings from Down Under! Current at the CosPA conference in Melbourne, after spending a couple of days in Sydney — a brief fling through Adelaide up next.

It’s been a mixed bag so far; while I’ve had great fun interacting with people here in Australia, I’ve also been struggling with a nasty cold I picked up on the flight over. Spent yesterday mostly in bed, too fogged up to even work on my talk for Friday. But when I’ve had the strength to be up and about, it’s been a treat. Here’s an iPhone snap of the University of Sydney; that clocktower in the middle houses, appropriately enough, the Centre for Time.

usyd

One of the perks of civilization that hasn’t quite caught on in these parts is affordable internet access in hotel rooms, so don’t expect a lot of blogging over the next week or two. Instead, I can point you to a couple of recent videos. One is an extended interview for Edge, entitled Why Does the Universe Look the Way it Does? It is an interview (presented in text and video), not a carefully pre-planned document, so not all thoughts are arranged as elegantly as one might like. Here is some of the flavor:

We are in a very unusual situation in the history of science where physics has become slightly a victim of its own success. We have theories that fit the data, which is a terrible thing to have when you are a theoretical physicist. You want to be the one who invents those theories, but you don’t want to live in a world where those theories have already been invented because then it becomes harder to improve upon them when they just fit the data. What you want are anomalies given to us by the data that we don’t know how to explain.

The other one is a panel discussion on Time Since Einstein, from the World Science Festival. As the description there says, it features Roger Penrose, David Albert, and some other people it would be too exhausting to list individually. Here’s part 1 of 5:

World Science Festival 2009: Time Since Einstein, Part 1 of 5 from World Science Festival on Vimeo.

Now if only my immune system would finish off the little viral buggers inside me, I could get out and see a bit of this interesting country.

by Sean at November 18, 2009 03:09 PM

US/LHC Blog — LHC Schedule

Sorry I didn’t include this in my last entry. Literally as soon as I posted it, I got another email about the LHC Schedule… which said so far things are going well and that the restarting of the LHC is imminent. That means beams should be circulating soon. Things are changing very quickly and as things are happening we’ll try to keep you up-to-date.

For the public, there will be some quasi-live event displays will be posted here

Once there are events, you should be able to see them. So check it out

-Regina

by Regina at November 18, 2009 02:25 PM

US/LHC Blog — Jamboree at BNL

This week I’m attending an analysis Jamboree at Brookhaven National Lab. When I was little, the word Jamboree always conjured up images of country bears playing banjos (maybe that’s because my grandparents would take us to Disneyland…).

Country Bear Jamboree

Unfortunately this Jamboree doesn’t include singing bears, instead it’s a discussion of different analyses to do with the first data from the ATLAS. BNL is one of the major hubs in the US for ATLAS, so about twice a year they host analysis meetings. Different running conditions sometimes warrant different analyses and with data coming hopefully soon, we need unite our efforts and make sure all the things – like software – is standard.

A bit about calibration

I’m giving a presentation on a calibration study I’ve been doing. Calibration is one of the first things we’ll have to do with first data. Like any tool, we’ll need to make sure we understand what we’re getting out of the detector once the data starts rolling in. It’s not as glamorous as a search for an unknown particle, but it is definitely important. Particles like J/psi and Z have distinct mass peaks (at 3 GeV and 91 GeV respectively) when the energy from their decay products is reconstructed and combined. So we’ll take the reconstructed electrons, and look for a peak at around the Z mass and then tweak our algorithms so the peak lines up with the known peak. This type of calibration for example can be done using only one piece of the detector (like the calorimeter).

Another type is calibration between detector pieces. I’m looking at a study which compares what you read as the energy in the calorimeter and the momentum in the tracker. If you take the ratio, you should get about one, (since the mass of the electron is so small… you all remember E^2=(pc)^2+(mc^2)^2, right?)

But other than calibration

For lunch today we ventured off the BNL site to eat at a staple in American cuisine: Taco Bell. My friend and former roommate was back at BNL from CERN to participate in the Jamboree festivities, so we were celebrating America by getting refills on our super-sized drinks and cheesy Gorditas (sure I know what you’re thinking… Taco Bell is “Mexican” food… right). The culture shock is always a little surprising when going to CERN or coming back.

So now it’s after lunch, so back to work.

-Regina

by Regina at November 18, 2009 01:35 PM

Dave Bacon — Science Fiction Prototyping

Last Friday I went to at talk by Brian David Johnson from Intel. That sentence sounds like any other that an academic could write--always with the going to seminars we acahacks are. That is until you hear that Brian David Johnson is a "consumer experience architect" in the Digital Home - User Experience Group at Intel. Okay that is a bit odd for a typical seminar speaker, but still lies in the "reasonable" range. And then you find out the title of his talks is "Brain Machines: Robots, Free Will and Fictional Prototyping as a Tool for AI Design" and you say, whah? Which is exactly what a group of about forty of us said upon hearing about this seminar, and is exactly why we showed up to hear the talk!

Read the rest of this post... | Read the comments on this post...

Tommaso Dorigo — New Z Bosons That LHC Can Discover In Three Months

I recently discussed here the Tevatron results of searches for new Z bosons in electron-positron or dimuon samples collected by CDF and DZERO, pointing out that there seem to be a couple of intriguing upward fluctuations in the data. One of the dielectron fluctuations sits at a mass of 240 GeV, the other, also in the dielectron spectrum, is at about 720 GeV. Neither is compelling.

by dorigo at November 18, 2009 12:03 PM

US/LHC Blog — The EPR paradox and B-mesons

Several weeks ago it was brought to my attention that some of our readers via Facebook wanted to hear my take on the EPR paradox, so I figured I ought to get around to saying something. It turns out, further, that this is an appropriate thing to discuss since it has some applications to particle physics in how we are able to decipher what goes on inside our particle colliders.

epr

So let’s start with the basic idea. The Einstein-Podolsky-Rosen paradox is a thought experiment that was originally proposed to highlight the inadequacies of quantum mechanics. What ended up happening was that the phenomenon of quantum entanglement became the foundation for real-life applications of quantum mechanics, e.g. quantum cryptography.

A fair warning: I’m not going to give a proper, formal treatment of the paradox nor will I further discuss the original motivation. Instead, I’ll give a heuristic description and jump into an application to B mesons.

First, let’s start off by reminding ourselves that we assume that information cannot travel faster than the speed of light. This related to the fundamental principle of causality: if things could travel faster than the speed of light, then in some reference frame, it’s moving backwards in time.

Alright, now onto the EPR paradox. The idea is this:

You have a particle (the blue guy in the picture above) that decays into two other particles, A and B.
There is a conservation law that constraints some property of A and B relative to one another. For example, conservation of electric charge says that if the original particle has no charge and A has charge +1 (e.g. positron), then B must have charge -1 (e.g. electron).
Quantum uncertainty tells us that until we make an observation, the state of the particle is unknown. For example, we don’t know if A is an electron or a positron until we actually check. Further, quantum mechanics tells us that the particles must actually be in some “superposition” of states.
If, after A and B travel a long distance in this “superposition,” someone checks particle A, then the conservation law determines the state of particle B. In our example, if someone in Fermilab observes that A is an electron, then we can instantly deduce that someone at CERN (which is where B happens to be zooming past at the moment) will observe B to be a positron.
But the Fermilab scientist could just as likely have observed A to be the positron and thus B would be an electron; until the person at Fermilab actually measured A, it was in some intermediate state. Thus the moment A is measured, it instantly fixes what B must be.
To be clear: before A is measured, B really is a mixture of states and can be observed to be anything. After A is measured, B can only be observed to be the correct state to satisfy the conservation law.
So here’s the paradox: how the heck did B know how to behave if it’s so far away from A? (Instead of CERN, B could have been at a distant galaxy when A was measured.) It appears that information travels from A at the point of measurement at a speed faster than light to B. (In fact, at an infinite velocity.) Einstein called this “spooky action at a distance.”

First, let me say that the effect is real. Indeed, the particles A and B are said to be entangled. (This entangled state is actually rather fragile, since you can’t let the particles interact with any other matter that would allow them to disentangle.) Second, this is not really a paradox. The point is that there is no actual “information” being transmitted since there’s no way to impose a state on A, the initial observation is always random. You can try to think up clever ways around this, but they always fail. There is no paradox. Particles can be entangled and can have weird correlations across long distances, but that’s just a prediction of quantum mechanics that is fully consistent with causality.

Before anyone complains that I’ve oversimplified the problem, let me note that we’ve been very informal about a lot of details. First of all, we haven’t provided a rigorous definition of “information.” For our purposes it’s fine to take an intuitive definition, e.g. can I encode a simple binary message. We also haven’t talked about the specifics of what conservation law we’re using. The EPR paradox usually is described in terms of particle spins so that the conserved quantity is angular momentum. This allows one to think about subtleties regarding spins relative to different axes (x-direction vs. y-direction) that are important for a full discussion, but that we’ll gloss over here. Finally, we won’t say anything about why the related question of why A and B should exist in a superposition when they’re flying away undetected (i.e. what “eigenstate” is produced and detected).

What we’re described is the ‘essence’ of quantum entanglement; we’ve skipped the details, but as usual, the physics is more in the intuition rather than the details. A neat real-life application for this is quantum cryptography, which is a way for two parties to share a secure “key” while being able to check if a third party is eavesdropping. The idea is that information is sent via entangled particles, with one particle of each pair saved by the sender. If a third party tries to view the packets of information, then this would lead to an observable non-correlation of the would-be entangled particles. [Again, we omit the details.]

Someone trying to eavesdrop on a quantum cryptographic communication. No, just kidding. This is actually a photo of the BaBar detector at SLAC. Image via Interactions.org.

Application to B Physics. Now we get back to particle physics! Above is a picture of the BaBar detector at the Stanford Linear Accelerator Center (”SLAC National Laboratory”). It’s an experiment that finished data taking last year whose purpose was to examine the decays of B mesons and their antiparticles. The antiparticles are written with a line over the B so that people usually call them “B-bar,” hence the name of the experiment: “B, B-bar” became “BaBar.” They even got official permission to use BaBar the elephant as a mascot.

There are a few types of B meson. Like all mesons, they are made up of a quark and an antiquark. B-mesons are those which contain an (anti)-bottom quark. A neat thing about neutral mesons is that they have well defined, distinct anti-particles (e.g. a down/anti-bottom meson would have a bottom/anti-down anti-meson) even though these particles have the same charge. The charges of the constituent quarks change, but the total B meson system doesn’t change charge. This means, for reasons that I won’t go into, neutral mesons and their antiparticles can mix quantum mechanically. The B-meson, in particular, have the nice property of ‘oscillating’ on roughly the same time scale as they decay. This means that we can produce a B meson and it’ll wiggle between wanting to be a B and an anti-B about once before eventually annihilating into other stuff.

A B-meson... and a bee.

Now here’s the point: we’ve discussed in a previous post that matter and antimatter are related by CP symmetry. We know that this symmetry must be broken because our universe is made up of a whole lot of matter and practically no antimatter. So there’s something different about matter and antimatter, and it would be very interesting to see how these differences appear. Naively, if CP symmetry were exact (e.g. if matter and antimatter were truly mirror images) then whenever a neutral B meson decays into something (say, a muon, anti-muon pair) then we would expect the anti-meson to also decay into that something with the same probability. (See why this only works with neutral mesons? If the mesons were charged then the anti-meson could not decay into the same final state without violating conservation of charge.) It would be really great, then, if we could just look and see how often B mesons decayed into these states versus B-bar mesons.

Unfortunately life isn’t that simple. Because the B decays very quickly (i.e. before it reaches the detector instrumentation), all we actually see are the remnants of its decays. That means that we can observe a large sample of events that decayed into muon, anti-muon (and, realistically, some pions) that point to the center of the beam pipe where we expect the B’s to come from. There appears to be no way to figure out which of these events came form B’s and which came from B-bars!

Now this is where entanglement comes in. I should apologize in advanced to my experimental colleagues for my simplified explanation. What the clever physicists at BaBar (and its Japanese counterpart, Belle) do is to collide electrons and positrons at just the right energy to produce lots of a particle called the Upsilon-4S. This funny-named particle then decays to an entangled B and B-bar pair. Each of these particles will “oscillate” quantum mechanically between actually being a B and a B-bar, but once one of them is identified as a B (or B-bar), the other is uniquely identified as well. Most of the time both of the particles decay into things like the muon signal that we want to compare. As stated above, this is unhelpful because we can’t figure out how to count each event as coming from a B or a B-bar decay.

However, some of the time one of the particles will decay into something that only a B can decay into. We don’t care about the rate for those decays, but observing it means—via entanglement—that the other particle must be a B-bar (or vice versa). In the case where one particle undergoes such a “signature” decay and the other particle decays into the muon/anti-muon decay of interest, we can definitively count that muon/anti-muon as coming from the appropriate B or B-bar meson.

An example of a "golden event" at BaBar where the red lines represent the unique decay products of a B meson, which "tags" the yellow tracks as the remnants of a B-bar meson. Image from Interactions.org

In this way, the so-called B-factories (because they produce lots of B-mesons) were able to measure differences in the decay rates of B and B-bar mesons to these muon/anti-muon final states. In other words, they directly observed CP violation: a difference between the behavior of matter and antimatter. The information gleaned from these experiments help us constrain the source of matter/antimatter asymmetry that eventually allowed the universe to form things like galaxies and planets instead of annihilating into a big mess of photons. And we were able to do this using a strange property of quantum mechanics that Einstein originally dismissed as “spooky action at a distance.”

Before I sign-off, this whole question of information traveling at superluminal velocities reminds me of my favorite string theory joke:

These days there are so many string theory papers being written that one might be concerned that they are being written at a rate that is faster than the speed of light. One needn’t worry, however, since no information is actually being transmitted.

Zing! (I hope my string theory friends don’t read this blog.)

Cheers!
Flip

by Flip Tanedo at November 18, 2009 09:35 AM

Chad Orzel — Creepiness Is Contagious

It's always kind of distressing to find something you agree with being said by people who also espouse views you find nutty, repulsive, or reprehensible. It doesn't make them any less right, but it makes it a little more difficult to be associated with those views.

So, for instance, there's this broadside against ineffective math education, via Arts & Letters Daily. It's got some decent points about the failings of modern math education, which lead to many of our entering students being unable to do algebra. But along the way, you get frothiness like the following:

The educational trends that led to the NCTM's approach to math have a long pedigree. During the 1970s and 1980s, educators in reading, English, and history argued that the traditional curriculum needed to be more "engaging" and "relevant" to an increasingly alienated and unmotivated--or so it was claimed--student body. Some influential educators sought to dismiss the traditional curriculum altogether, viewing it as a white, Christian, heterosexual-male product that unjustly valorized rational, abstract, and categorical thinking over the associative, experience-based, and emotion-laden thinking supposedly more congenial to females and certain minorities.

This veers a little too much in the direction of "we must protect our precious bodily fluids!," and really undercuts the effectiveness of the rest of the argument. This is not to say that there weren't nutty things said by people on the other side of the math-education argument, but any time you start to sound like Jack D. Ripper, you're headed to a Bad Place.

Of course, that's only the lowest-order effect of nuttiness. The next highest order contribution comes when people are able to use the reprehensible views of your associates to construct seemingly devastating counterattacks, such as Malcom Gladwell's response to Steven Pinker (who wrote a fairly devastating review of Gladwell in the New York Times), which consists mostly of pointing out that Pinker's comments about NFL quarterbacks are based on arguments from a creepy racist. Which is superficially very effective-- after all, who wants to be associated with a creepy racist, even twice removed?-- but doesn't really address the substance of the critique. It also neatly dodges the whole "igon value" issue (namely, that Gladwell misuses technical terms in a way that suggests he has no idea what he's talking about), which I'm sure Gladwell is more than happy to pretend never happened, but which is much more central to Pinker's argument than the NFL business.

So, not only do nutty views end up making it difficult for people who generally agree with you to, well, agree with you, but they also provide aid and comfort to those who disagree with you, by giving them an easy rhetorical dodge past people who use your arguments. The moral here is clear: people with creepy political views need to stop agreeing with me about stuff.

Read the comments on this post...

Planet Musings

Subscriptions

Info

November 23, 2009

Michael Nielsen — Biweekly links for 11/23/2009

n-Category Café Equipments

Steinn Sigurðsson — Qu'est-ce que c'est?

November 22, 2009

Steinn Sigurðsson — More MOND

Cosmic Variance — Wechsler’s Index

Chad Orzel — How to Teach Physics to Your Dog is a Real Book!

Cosmic Variance — IPMU in Tokyo Needs Support

US/LHC Blog — Waiting for Collisions

Doug Natelson — Graphene, part II

Clifford Johnson — Coming Around the Bend Again

Clifford Johnson — Here, There, and Everywhere

Tim Gowers — Problems related to Littlewood’s conjecture

November 21, 2009

US/LHC Blog — Live from CMS CR at P5 (the BBC is in)…

US/LHC Blog — Pushing the Red Button (Live from CMS CR at P5)

Tommaso Dorigo — The Say Of The Week

US/LHC Blog — Holiday Gift?

Backreaction — Swedish Research Council requires Open Access

Jonathan Shock — Orion setting over Santiago de Compostela

Alexey Petrov — It is back!

November 20, 2009

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

Secret Blogging Seminar — The diamond lemma

A few results

Solution 1

Solution 2

Generalizing

Solution 3 (a sketch)

Solution 4

US/LHC Blog — First Beam through ATLAS!

US/LHC Blog — Live from the CMS control room at P5….

Cosmic Variance — Beam Circulating in LHC Again!

Chad Orzel — November Basketball: SU-Cal, UNC-OSU

Clifford Johnson — Tape Noir

US/LHC Blog — Foggy Beginnings

Michael Nielsen — Biweekly links for 11/20/2009

Steinn Sigurðsson — Taxing the Hidden Economy

Terence Tao — UCLA Math Seeks Exceptional Student for Undergraduate Merit Scholarship

Eligibility Requirements:

November 19, 2009

John Baez — This Week's Finds in Mathematical Physics (Week 283)

John Baez

Terence Tao — Nonstandard analogues of energy and density increment arguments

Edinburgh Mathematical Physics Group — Samson Shatashvili’s EMPJ Talk

Resonaances — Fermi says "nothing"...like sure sure?

Cosmic Variance — A Conversation on the Existence of Time

US/LHC Blog — CMS Detector Control Room

Chad Orzel — I Can Haz Books!

Mark Chu-Carroll — The Balance of Screening Tests

Tommaso Dorigo — New Tevatron Higgs Limits Got Worse, But The 115 GeV Excess Is Growing!

Dave Bacon — Mmmvelopes. Tasty Tasty Mmmvelopes.

Backreaction — Causal Diagrams

Clifford Johnson — Market Matters

US/LHC Blog — New Higgs search results from the Tevatron

n-Category Café Cobordism and Topological Field Theories Week 3

Chad Orzel — Thursday Baby Blogging 111909

n-Category Café Mathematical Emotion

Edinburgh Mathematical Physics Group — In Japan too they cook beans

John Terning — Adopt a Physicist

Steinn Sigurðsson — lateral thinking on your toes

Steinn Sigurðsson — proposal invariance

November 18, 2009

Doug Natelson — Not even wrong.

David Hogg — nothing

Chad Orzel — Poll: New York State of Mind

Cosmic Variance — Explaining Time, the Universe, and All That

US/LHC Blog — LHC Schedule

US/LHC Blog — Jamboree at BNL

Dave Bacon — Science Fiction Prototyping

Tommaso Dorigo — New Z Bosons That LHC Can Discover In Three Months

US/LHC Blog — The EPR paradox and B-mesons

Chad Orzel — Creepiness Is Contagious