Parteibuch Aggregator Feed

gowers: Horizon 2020 to promote open access

gowers — Thu, 17 May 2012 08:34:39 +0000

If you read an earlier post of mine about Elsevier’s updated letter to the mathematical community then you may remember that towards the end of the post I claimed that Elsevier was lobbying heavily to have all mention of open access removed from the documents of Horizon 2020, Europe’s “Framework Programme for Research and Innovation”, a claim that was then denied by Alicia Wise, who is Elsevier’s “Director of Universal Access”.

Leaving aside who is right about this which may depend rather sensitively on the precise words used to describe what happened, not to mention the interpretation of those words , news has broken today in the THE of potentially important developments. It seems that whatever lobbying Elsevier might have gone in for has been to no avail, because open access will be a very significant aspect of Horizon 2020.

Why is this potentially big news? Well, first of all it comes hard on the heels of the Wellcome Trust’s announcement that it would insist on open access for the research it funds, Harvard University Library’s statement that the current system is unsustainable, the British Government’s announcement that it has plans to make all taxpayer-funded research available online, the decision by TU Munich’s mathematics department to cancel subscriptions to all its Elsevier journals, and an apparently serious suggestion that future rounds of Britain’s Research Excellence Framework will favour open access papers. There seems to be a definite trend here.

But what also makes it important is the sheer amount of money involved in Horizon 2020. Their budget for the years between 2014 and 2020 is 80 billion Euros. I don’t know what percentage of the world’s scientific papers will be affected by their open access policy or even what precisely the policy will be, but what some people are reported as saying in the THE article is very promising , but even if it is something small like 2%, there will still be increased pressure to provide the publishing models in which all that research can be published, which will help to speed up the abandonment of the current models that Harvard and TU Munich describe as unsustainable. It’s amusing that everybody describes what they like as sustainable and what they dislike as unsustainable. I think Elsevier’s prices are sustainable, but that we’d be much better off not sustaining them.

Could FRPAA be next?

Kowalski: Almost a mathematical Haiku

Kowalski — Thu, 17 May 2012 06:22:11 +0000

I noticed the following comment in today’s arXiv update of a paper of Kim and Lusztig:

A sign error is corrected; a conjecture is replaced by a theorem.

Isn’t that mathematical poetry of a kind? It’s unfortunately a bit too long to be a Haiku…

The n-Category Café: Integrating Against the Euler Characteristic

The n-Category Café — Thu, 17 May 2012 05:59:10 +0000

The Euler characteristic of topological spaces behaves something like a measure. For example, under suitable hypotheses,

$χ X \cup Y = χ X + χ Y - χ X \cap Y .$

One of the main things you can do with a measure is integrate with respect to it — or ‘against’ it, as they say.

So: what happens if you try to integrate against the Euler characteristic?

I don’t completely understand the answer myself, but I’ll explain as well as I can. Along the way, we’ll see:

how this train of thought helps us to define Euler characteristic
how it also leads to the notion of curvature.

Simple functions on the line

Let’s begin in one dimension. Our aim is to define the integral $\int f d χ$ for suitable functions $f : R \to R$ .

Whatever we think Euler characteristic is, the Euler characteristic of a compact, nonempty interval $A$ should be $1$ . So, writing $I_{A}$ for the indicator function or characteristic function of $A$ , we should have

$\int I_{A} d χ = 1 .$

Since integration is supposed to be linear, this tells us how we must integrate any finite linear combination of indicator functions of compact nonempy intervals. I’ll call these simple functions on $R$ . So, for a simple function

$f = \sum_{r = 1}^{k} c_{r} I_{A_{r}},$

where each $A_{r}$ is a compact nonempty interval, we should have

$\int f d χ = \sum_{r = 1}^{k} c_{r} .$

Do I hear you sigh? If you’ve seen this kind of thing before, you’ll recognize the standard problem: the definition isn’t obviously consistent, since $f$ can be expressed as a combination of indicator functions in multiple ways, and maybe these give multiple different values for the integral. In that case, you’ll also know that the standard solution, involving common refinements, is pretty tedious work.

Happily, we can avoid it. Here’s how. For a simple function $f$ , put

$J f = \sum_{x \in R} f x - f x -$

where $f x -$ means $\lim_{ε \to 0 +} f x - ε$ . This quantity $J f$ is well-defined, linear in $f$ , and takes value $1$ when $f$ is the indicator function of a compact nonempty interval. So, $J f = \sum c_{r}$ whenever $f = \sum c_{r} I_{A_{r}}$ . We therefore put

$\int f d χ = J f,$

and the consistency problem evaporates.

Let’s have some examples. What, for instance, is the integral against the Euler characteristic of this function?

The solid and empty circles indicate that $f a = f b = 0$ . So

$f = 3 I_{a, b} = 3 I_{[a, b]} - 3 I_{[a, a]} - 3 I_{[b, b]}$

and

$\int f d χ = 3 - 3 - 3 = - 3 .$

Since $f = 3 I_{a, b}$ , this tells us that we’re treating the Euler characteristic of the open interval $a, b$ as $- 1$ . That might strike you as wrong if you’re used to Euler characteristic being invariant under homotopy equivalence. But as James Propp pointed out long ago, there’s a tension between the requirement that Euler characteristic is homotopy-invariant and the requirement that it behaves like a finitely additive measure. You can’t have both at once. See also John Baez’s excellent talk on the mysteries of counting. Here we’re not worrying about homotopy invariance; we’re using what Propp would call ‘Euler measure’.

What about this function?

It’s not hard to see that $\int g d χ = 7$ , whatever the unlabelled values on the axes might happen to be. I chose the letter $J$ to stand for ‘jump’: $J f = \int f d χ$ is the total vertical jump occurring at jump discontinuities from the left.

One more example: what is the integral against the Euler characteristic of the following function?

Here

$h = 3 I_{[a, d]} + 5 I_{[a, b]} + I_{[c, d]},$

$\int h d χ = 3 + 5 + 1 = 9$

regardless of the values of $a$ , $b$ , $c$ and $d$ . Alternatively, you can calculate $\int h d χ$ via the formula for $J f$ , giving $8 + 4 - 3 = 9$ again.

More general functions on the line

Classical measure theory also involves things called ‘simple functions’ with a different but analogous meaning . There, defining integration for simple functions is just a prelude to defining integration for a larger class of functions. Can we do something similar here, extending our integral to a larger class of functions?

We can. Indeed, the formula

$\sum_{x \in R} f x - f x -$

for $\int f d χ$ immediately makes sense for more than just the simple functions.

But before we charge ahead and generalize, let’s correct the ugly asymmetry you see here. In everything so far, we could equally well have used the formula

$\sum_{x \in R} f x - f x + .$

It makes no difference: this is still equal to $\int f d χ$ for simple functions $f$ . Of course, it’s just as asymmetric. However, taking the average of the two formulas, we also have

$\int f d χ = \frac{1}{2} \sum_{x \in R} [- f x - + 2 f x - f x +] .$

This is now symmetric, and therefore more likely to give us a useful definition for more general functions $f$ .

Maybe you can see a hint of how curvature is going to enter the story: this looks like the expression $f ″ x = \lim_{ε \to 0} \frac{f x - ε - 2 f x + f x + ε}{ε^{2}}$ for a second derivative, and second derivatives have something to do with curvature.

So: let $f : R \to R$ be a function such that the limits $f x -$ and $f x +$ exist for all $x \in R$ , and are equal to $f x$ for all but finitely many $x \in R$ . In other words, $f$ is continuous except for a finite number of jump discontinuities. The integral against the Euler characteristic of such a function $f$ is defined by the formula above:

$\int f d χ = \frac{1}{2} \sum_{x \in R} [- f x - + 2 f x - f x +] .$

Be warned: this has some properties that you might not expect of an integral. For instance, the integral of any continuous function is $0$ , the integral of a function that is everywhere strictly positive can be strictly negative, and changing the value of a function at a single point can change the value of the integral. On the other hand, this integral has some interesting properties too, as we’ll see when we get to higher dimensions.

Simple functions in higher dimensions

Let’s now consider functions on $R^{n}$ , for $n \geq 1$ . The role of intervals will be played by convex sets. For brevity, I’ll use ‘convex’ to mean ‘compact, nonempty and convex’.

A function $f : R^{n} \to R$ is simple if it can be expressed as a finite linear combination of indicator functions of convex sets. Again, we want to ‘define’

$\int f d χ = \sum_{r = 1}^{k} c_{r}$

whenever $f = \sum_{r = 1}^{k} c_{r} I_{A_{r}}$ for some convex sets $A_{r}$ , and again we might groan at the prospect of having to do those tedious consistency checks.

But once more, the jump functional $J$ comes to the rescue. I’ll explain in the case $n = 2$ ; the strategy for higher dimensions should be clear. Let $f : R^{2} \to R$ be a simple function. For each $x \in R$ , the function

$f x, - : R \to R$

is simple, and so we can define a function $F : R \to R$ by $F x = J f x, -$ . This function $F$ , too, is simple, so we get a real number $J F$ . We define $J f$ to be this number: $J f = J F$ .

Thus, we have defined $J f$ for every simple function $f$ on $R^{2}$ . It is linear in $f$ , with $J 1_{A} = 1$ whenever $A$ is convex. So just as in the one-dimensional case, $J f = \sum c_{r}$ when $f = \sum c_{r} I_{A_{r}}$ . This solves the consistency problem, and $\int f d χ = J f$ .

I learned this from Chapter 5 of Klain and Rota’s Introduction to Geometric Probability source of so many wonderful things . It is remarkably little effort, and is even based on a very standard technique: reducing a multivariable integral to a sequence of single-variable integrals. But it has an immediate nontrivial consequence: the definition of Euler characteristic for a large class of subsets of $R^{n}$ .

Indeed, call a subset $S$ of $R^{n}$ polyconvex if it can be expressed as a finite union of convex sets. For example, any picture on a black and white television is polyconvex assuming that each pixel is convex . And quite simply, we define

$χ S = \int I_{S} d χ .$

You can prove, as Klain and Rota do, that this coincides with the usual definition.

More general functions in higher dimensions, and curvature

The rough idea now is that given a function $f : R^{n} \to R$ whose discontinuities are no worse than those of a simple function, we should be able to define $\int f d χ$ by repeating verbatim the definition for simple functions.

In the one-dimensional case, we first had to deal with the pesky problem that the formula

$J f = \sum_{x \in R} f x - f x -$

isn’t symmetric, so probably wouldn’t generalize well. To fix that, we considered the formula $\sum f x - f x +$ obtained by reversing the orientation of the line, and then we averaged over the two orientations to get something symmetric.

In higher dimensions, the asymmetry problem can no longer be brushed aside with this algebraic flick of the wrist. In fact, some interesting geometry comes in here. This asymmetry issue, which looked like a nuisance distracting us from the main business, turns out to be exactly the reason why integration against the Euler characteristic is closely related to curvature.

Again I’ll stick to $n = 2$ , leaving higher dimensions to your imagination.

In defining $J f$ for simple functions $f : R^{2} \to R$ , we used the standard coordinate system on $R^{2}$ . When $f$ is simple, the choice of basis does not affect the value of $J f$ which is always equal to $\sum c_{r}$ , if $f = \sum c_{r} I_{A_{r}}$ . But for more general functions $f$ , it certainly does make a difference. What we should do is consider all ordered orthonormal bases of $R^{2}$ , calculate $J f$ with respect to each basis, and define $\int f d χ$ to be the average.

You can see that this generalizes what we did for $R^{1}$ : there we took the average of two things, and there are two orthonormal bases of $R^{1}$ .

I don’t want to make this post any longer by explaining exactly what, for instance, ‘average’ means. Nor will I say much about which functions $f$ this will be a reasonable definition for. Instead, I’ll focus on the geometric interpretation of $\int f d χ$ .

Let’s think about a function $f : R^{2} \to R$ of the form $g \cdot I_{A}$ , where $g$ is continuous and $A$ is convex. Thus, $f$ is supported on $A$ and continuous everywhere except perhaps on the boundary of $A$ , where it might jump in value as it crosses the boundary. I’ve just been reading something that talks about functions `suffering a jump discontinuity’. The suffering of $f$ is limited to $\partial A$ .

What is $\int f d χ$ ? How can we understand it?

Well, $\int f d χ$ is the average over all orthonormal bases of the quantity “ $J f$ with respect to that basis”. So, take an orthonormal basis — a coordinate system — and let’s consider $J f$ .

Recall that the definition of $J f$ was slicewise. For each $x \in R$ , we take the function $f x, - : R \to R$ and put $F x = J f x, -$ . In the picture, the value of $x$ shown is in the vertical shadow of $A$ , so $F x$ is equal to $f x, y$ .

Now since $f$ is continuous, $F$ is too, except that $F$ has a jump discontinuity at each end of the shadow. So, $J F = f x_{0}, y_{0}$ . Finally, by definition, $J f = J F$ , and so $J f = f x_{0}, y_{0}$ .

So in the end, $J f$ is something really trivial:

$J f$ is the value of $f$ at the leftmost point of $A$

where ‘leftmost’ refers to the basis concerned. I’m assuming for simplicity that the boundary of $A$ is smooth and contains no line segments. This isn’t crucial.

But this isn’t the same as $\int f d χ$ . To get that, we have to average over all orthonormal bases of $R^{2}$ . That is, we slowly rotate our coordinate axes through $360^{\circ}$ , at each moment recording the value of $f$ at the ‘leftmost’ point of $A$ with respect to the current axes , then taking the mean. As we rotate, that leftmost point works itself around the whole boundary of $A$ , never backtracking. And here’s the important thing:

It spends more time at some boundary points than others.

To see why, consider a convex set like this:

For almost all choices of axes, the leftmost point of $A$ will be in one of the red parts of the boundary. Only rarely will it be elsewhere.

So as we rotate the axes, the leftmost point with respect to the axes moves quickly over parts of the boundary with low curvature, and lingers where the curvature is high. We’d therefore imagine that $\int f d χ$ would be the integral of $f$ over the boundary of $A$ with respect to some kind of curvature measure on $\partial A$ .

This turns out to be true. In fact,

$\int f d χ = \int_{\partial A} f d ϕ$

where $ϕ$ is the angle that the tangent makes with some fixed, arbitrarily chosen reference line:

This is good, but there’s another way to put it too. When we integrate along a curve, we usually do it with respect to the arclength measure, typically written as $d s$ . And the rate of change of the angle $ϕ$ per unit arclength is nothing but the classical curvature $κ$ . That is, $κ = d ϕ / d s$ . Putting this together with the last equation, we get

$\int f d χ = \int_{\partial A}$

David Speyer: Bizarre persecution of Russian mathematician

David Speyer — Wed, 16 May 2012 19:48:16 +0000 I don’t fully understand this story, but it is time sensitive. Misha Verbitsky is a complex geometer who is also an active Russian political blogger. Recently, he was arrested by the Russian government while attempting to board a flight out of the country. It turns out he was convicted in absentia of violating the trademark of a man named Igor Pugach, by using an image of Pugach to illustrate a blogpost criticizing Pugach. Verbitsky was fined 300,000 rubles approximately 9,700 dollars and will not be able to leave Russia until he pays the sum. Verbitsky’s blog is here; due to my inability to read Russian I have not located the post in question. A newspaper article on the issue is here. Obviously, this violates all sorts of legal norms. Under US trademark law, you simply can’t be convicted of a trademark violation if you are not selling something. You could be convicted of a copyright violation, but this case would likely be fair use. Moreover, you certainly can’t have a large judgment made against you in absentia, except after extraordinary efforts have been made to notify you of the proceedings. I don’t know Russian law, but I am quite willing to say this is immoral, and expect that it is also illegal. There is also a profoundly dumb statement by Pugach’s spokesperson that simply wearing a beard similar to Pugach’s is a trademark/copyright violation but, since that doesn’t appear to be the basis of the court ruling, I am going to lump that under “people say remarkably dumb things sometimes”. There is a petition to free Verbitsky here directed to Putin. I tend to be skeptical of the value of internet petitions, but it’s a start. I have also submitted this story to Boing Boing and the Volokh Conspiracy, in the name of boosting the signal. I’d be interested in suggestions as to what we should be doing to get this story off the internet and to the attention of people who care. My next thought is to contact the US State Dept, or ask my Senators to do so. Does anyone know whether Verbitsky is a US Citizen? I assume our government will care more if this is the case. Wikipedia reports that he lived in the US in the 90′s, and lives in Russia while travelling frequently now, but doesn’t give citizenship.

The n-Category Café: Postulated colimits and absolute colimits

The n-Category Café — Mon, 14 May 2012 07:10:36 +0000

So there’s this thing invented by Anders Kock called a postulated colimit. It seems like I’ve read his note about them numerous times without really understanding it. I felt like there ought to be some relationship with my theory of exact completions, but I didn’t nail it down precisely in time for the posting of that preprint. Now, however, I think I finally have a grasp on postulated colimits. They do turn out to be nicely related to exact completions, but to find out how, you’ll have to wait for me to update the exact completions paper or figure it out yourself . Today, I just want to tell you what postulated colimits are, and talk about how they’re related to something else I like: absolute colimits.

An absolute colimit is a colimit that’s preserved by any functor whatsoever. The term is used in two slightly different ways, which can be confusing if you don’t watch out for it. On the one hand, a particular colimit in a particular category

C

is absolute if it is preserved by any functor with domain

C

. On the other hand, if

V

is a nice category to enrich over, and

W

is a weight for colimits in

V

-categories, then

W

is absolute if all

W

-weighted colimits in all

V

-categories are preserved by all

V

-functors.

There is obviously a close relationship between the two meanings; the subtlest part is probably that an ordinary colimit can be preserved by all $V$ -functors without being preserved by all unenriched functors. For instance, initial objects are never absolute in the first, unenriched, sense — but the weight for initial objects is an absolute weight when $V =$ pointed sets or abelian groups.

In this post I’m interested in the first meaning of absolute colimit; no enrichments today.

I would guess that I’m fairly typical in that my first exposure to absolute colimits was through Beck’s monadicity theorem, in which one uses split coequalizers, and remarks that they are a special sort of absolute coequalizer. An obvious question to ask after you first meet these notions is “are there absolute coequalizers that aren’t split?” If you’ve never thought about this question, then I encourage you to go away and work on it for a little while. Go on, I’ll wait.

Back? So you might have realized that there is a very trivial sort of absolute coequalizer that is not split: if $f : A \to B$ is a morphism that is not a split epi, then $1_{B}$ is a coequalizer of $f$ and $f$ , which is not split. But there can also be other more interesting absolute coequalizers that are not split.

If you’re a seasoned category theorist who automatically reaches for the Yoneda lemma, then you might also have realized that there’s a very clever way to characterize all absolute coequalizers, and which is a generalization of the notion of split coequalizer. I believe this is originally a result of Bob Paré from 1969. The key is this: suppose we have an absolute coequalizer diagram

X ⇉_{f_{1}}^{f_{0}} Y \overset{e}{\to} Z .

Then this coequalizer must, in particular, be preserved by the representable functor $hom Z, -$ . Therefore, we have another coequalizer diagram

hom Z, X ⇉_{f_{1} \circ -}^{f_{0} \circ -} hom Z, Y \overset{e \circ -}{\to} hom Z, Z

But this is a coequalizer in $Set$ , and we know what coequalizers in $Set$ look like. In particular, coequalizers in $Set$ are surjective, and so $e \circ - : hom Z, Y \to hom Z, Z$ must be surjective. Thus, in even more particular, there must be something in $hom Z, Y$ which maps onto $1_{Z} \in hom Z, Z$ . That just says that $e$ is split epic just as it must be in a split coequalizer .

Now our coequalizer diagram must also be preserved by $hom Y, -$ , and from that and our knowledge of coequalizers in $Set$ , we can extract a generalization of the rest of the split coequalizer condition. See absolute coequalizer for details.

It turns out that this technique works in arbitrary generality. In fact, by abstract nonsense, a colimit is absolute if and only if it is preserved by the Yoneda embedding $C \to [C^{op}, Set]$ . And by looking at presenvation by particular hom-functors, we can extract a characterization of general absolute colimits. Bob Paré did this in 1971.

Specifically, let $μ : F \to Δ A$ be a cocone under a functor $F : I \to C$ . Then the following are equivalent:

$μ$ is an absolute colimiting cocone.
$μ$ is a colimiting cocone and is preserved by the Yoneda embedding $C \to [C^{op}, Set]$ .
There exists $i_{0} \in I$ and $d_{0} : A \to F i_{0}$ such that
1. For every $i \in I$ , $d_{0} \circ μ_{i}$ and $1_{F i}$ are in the same connected component of the comma category $F i / F$ .
2. $μ_{i_{0}} \circ d_{0} = 1_{A}$ .

In particular, there exists an $i_{0}$ such that $μ_{i_{0}}$ is split epic, generalizing our above observation that absolute coequalizers are split epis. The rest of the characterization is likewise a generalization of the part of the characterization of absolute coequalizers that I didn’t mention.

So far, so good. Now what is a postulated colimit? Anders Kock introduces the notion as follows:

To say that a diagram
$R ⇉_{b}^{a} X \overset{q}{\to} Q$
in the category of sets is a coequalizer may be expressed in elementary terms by saying that $q \circ a = q \circ b$ , and that the following two assertions hold

1.1 $q$ is surjective

1.2 for any $x$ and $y$ in $X$ with $q x = q y$ , there exists a finite chain $z_{1}, \dots, z_{m}$ of elements of $R$ with $x = a z_{1}$ , $b z_{1} = a z_{2}$ , … , $b z_{m} = y$ .

These assertions can be interpreted in any category where sheaf semantics is available; this means in any site…. If they hold for a given diagram in the site, we shall say that the diagram is a postulated coequalizer.

This already looks a bit familiar; those two characterizing facts about coequalizers in $Set$ are exactly the same properties that we used, after applying some representable functors, in order to characterize absolute coequalizers. But then Kock goes in a seemingly different direction: he takes these two statements and interprets them in the internal logic of a category.

Recall if you knew it that the internal logic of a category $C$ is a way of “interpreting” or “compiling” mathematical statements which look like they are talking about sets into statements which talk about objects of $C$ instead. For instance, given a function $q : X \to Q$ between two sets, the statement “for all $y \in Q$ , there exists an $x \in X$ with $q x = y$ ” expresses the surjectivity of $q$ . In the internal logic of a topos, however, our function would be replaced by a morphism $q : X \to Q$ between objects, and the same statement “for all $y \in Q$ , there exists an $x \in X$ with $q x = y$ ” would get compiled into one which turns out to express that $q$ is an epimorphism.

So Kock is saying that in a topos, we can take his conditions 1.1 and 1.2 and interpret them “internally”. As I said above, condition 1.1 will just become the assertion that $q$ is an epimorphism. Condition 1.2 will become something somewhat more mysterious. Regardless, a fork with these properties is called a postulated coequalizer — “postulated” I guess because the internal logic “postulates” that it is a colimit.

More generally, we can do something analogous for a cocone under any diagram and obtain a notion of postulated colimit. In that case the analogue of condition 1.1 will assert that the coprojections in the cocone are jointly epic.

Finally, generalizing in another direction, we have an “internal logic” in any site, which is basically just the restriction of the internal logic of its topos of sheaves. So we can define postulated colimits in any site. In that case, the analogue of condition 1.1 will assert that the coprojections of the cocone form a covering family.

Now a priori, it may not be obvious that a postulated colimit even is a colimit! We have these odd conditions about epimorphisms, but why should that imply a universal mapping property? However, Kock proves that if the site is subcanonical, then a postulated colimit is indeed a colimit.

You could say that this works because in a subcanonical site, the covering families themselves are already colimits namely, they are universally effective-epimorphic , so that that colimit-ness can be extended to the postulated colimits which are defined in terms of the covering families. Alternatively, you could say that it works because a subcanonical site embeds fully-faithfully in its topos of sheaves, and a topos is sufficiently set-like that the “internal” characterization of colimits works there for the same reason that it does in $Set$ .

This leads us to another of Kock’s characterizations of postulated colimits: a cocone in a site $C$ is a postulated colimit if and only if it becomes a colimit in the topos of sheaves $Sh C$ . In particular, a colimit in $C$ is a postulated colimit if and only if it is preserved by the sheafified Yoneda embedding $C \to Sh C$ .

Now we can draw the loop closed. Recall that a colimit in $C$ is absolute if and only if it is preserved by the ordinary Yoneda embedding $C \to [C^{op}, Set]$ . But every category $C$ can be made into a site with a “trivial topology”, for which $Sh C ≃ [C^{op}, Set]$ . Therefore, a colimit is absolute if and only if it is postulated by the trivial topology. Note that since the trivial topology is subcanonical, every postulated colimit in a trivial site is in fact a colimit.

The especially nice thing is that when we take the definition of postulated colimit and “ $β$ -reduce it” in the case of the trivial topology, we recover as we must Paré’s characterization of absolute colimits. The simple half of this is easy to see: in the trivial topology, the covering families are precisely those which contain a split epimorphism, so Kock’s condition 1.1 for the trivial topology reduces exactly to the part of Paré’s condition which says that some coprojection is split epi. The correspondence of the other two conditions is more tedious, but basically the same.

Let me end with the following suggestive remark. Since the notion of postulated colimit is defined entirely in terms of the topology of a site, it’s immediate that postulated colimits are preserved by any morphism of sites. And since the sheafified Yoneda embedding $C \to Sh C$ is a morphism of sites, this property also characterizes postulated colimits.

However, this is reminiscent of the second type of absolute colimit I mentioned back at the beginning: the weights whose colimits are preserved by every enriched functor. Perhaps a topology on a category is something akin to an enrichment of it, and postulated colimits are the “absolute weights” for such an “enrichment”. Moreover, then the topos of sheaves, which is essentially a cocompletion under postulated colimits, would be the “Cauchy completion” relative to this “enrichment”. If you’ve read sections 6–8 of my exact completions paper, you may be able to guess what’s going on.

Izabella Laba: The rainbow tree

Izabella Laba — Sun, 13 May 2012 20:43:01 +0000

This one was liked well enough on Google+, so I might as well post it here. I have been uploading more photos there, in case anyone is interested.

Teaching load, itemized: part 2

Teaching load, itemized — Sun, 13 May 2012 19:35:34 +0000

This is a continuation of my earlier post on teaching workload.

I must say that I got quite tired just from writing that post, reinforcing my feelings that this gig might not last. Academic teaching as it is now is awfully work-intensive, and this workload goes all but unnoticed by those who are benefitting from it. Some of this is of course complaining about the Romans who have not done anything for us lately, but the more important question is whether the service we are providing is really needed on that kind of scale. In 1900, half of American kids did not go to school at all, and only a very small fraction ever went to university. In the 1950s, the proportion of the U.S. population aged 25 or more with a Bachelor’s degree was less than 10%. It’s about 30% now. But every homework assignment still has to be marked by hand. We’re making hand-crocheted sweaters for one-third of the population.

Sweatshop wages is one way that could go. I get paid well enough, thank you for asking, but too many educational institutions depend increasingly on cheap adjunct labour with no job security. Or else, we could question whether everyone really needs a hand-crocheted sweater with pompons. Engineers, for instance, should have a pretty solid knowledge of math. I want to be able to walk into a building without worrying that it will collapse on me. But quantitative literacy for the general population might be taught using other models: online courses perhaps, or internet accounts with a point system a la Khan Academy. It’s not necessarily the kind of deep knowledge that I, personally, would love to be able to impart to everyone. But it might be enough, and all that people are willing to pay for, and all that we can do anyway.

More on that later. For now, I’ll finish what I started last time.

How my teaching practice has evolved. It’s been almost 20 years now. Obviously, technology has changed since then. When I started out, course syllabus and handouts were printed, xeroxed and handed out to students in class. We had email already, at least at universities, but course announcements were made in class rather than emailed to the course mailing list. There were no computer projectors or clickers in classrooms. I’m not sure that the technology has reduced our workload, really. We no longer have to print out 100 or 200 copies of each midterm solution set no, the secretaries don’t do that for us . We post the solutions on the course webpage instead. But the expectations have risen, too. We have to provide midterm solutions, homework solutions, lists of topics for midterms, practice midterms, solutions to practice midterms, and anything else that students might request. The more dedicated instructors post additional handouts, pencasts and Java applets.

It probably took me longer to prepare lectures when I started out. That does get easier with time. Even so, it does not quite go down to the proverbial 15 or 20 minutes per class. The technical term for that would be “winging it”. I might get away with it from time to time, in a class I’ve taught before and with material where examples are easy to come up with on the fly, but doing that several times in a row would not work so well.

I’ve found that more preparation time upfront can actually reduce the total workload quite a bit. If I prepare a lecture more carefully, I’ll have fewer questions to answer after class. If I spend more time on midterm preparation, proofreading several times, checking for complicated calculations or incorrect solutions with the right answer, I end up with fewer complaints and grading disasters. For homework assignments, I could pick a few questions from the textbook in a minute or two if I didn’t need to look at the solutions, but again, messy calculations and grading disasters.

Math departments at other research universities. The typical teaching load is 3-4 courses per year, for those universities on a semester schedule as opposed to quarters . The workload involved in teaching a course may vary quite a bit, though. My 4-course teaching load as an assistant professor at Princeton 1997-2000 was significantly lighter than a 3-course load at UBC. In fact, it was probably lighter than a 2-course load at UBC in 2 years out of 3, and about equivalent to 2 courses at UBC in the one year when I was in charge of a multisection course.

Here’s how this was possible. Each of the lower level courses calculus, linear algebra was divided into multiple sections of about 20-30 students. Junior faculty would normally be assigned to teach two parallel sections of the same course, often back to back. This meant that, aside from having to repeat the same lecture twice, it was really a 1-course per semester workload in terms of preparation. Midterms, quizzes and final exams were common for all sections, so that each instructor only had to prepare one quiz per semester and contribute a few exam problems. The instructor in charge was responsible for coordinating this. Midterms and final exams were scheduled for all sections together, outside of regular class hours. Quizzes were self-administered under the honour code, so again, it was possible to use the same problems for all sections. The small class sizes meant less grading, fewer office hours and requests for appointments, fewer emails to answer.

Clearly this would not happen here. Most lower level classes here range in size from about 60 to 200+; some have comparable size, about 20-30 students, but those would be single-section courses honours classes, for instance . I’m guessing that, were a math course to be discovered to have two parallel sections of 30 students each, they would be immediately merged into one, and one of the instructors would be reassigned to teach something else. The last time I taught two parallel sections of the same course Math 100: Calculus I, Fall 2007 , they had 118 and 105 students, respectively, and each section needed separate midterms.

Teaching institutions.. I’ve never worked at one and cannot speak to how the workload is structured. If anyone reading here would like to post about it, please do. I can say fairly confidently, though, that if a faculty member teaches 8-10 courses per year, there is absolutely no way that they could do that without working full time and then some.

Graduate courses. The workload is sometimes heavier, sometimes lighter, but mostly different. The logistics is easier: fewer students, usually no TA, less time spent on course administration. The preparation can take much longer, though: a single lecture can sometimes take a few hours to prepare, just like a research seminar. Assignments can take a very long time to grade.

Graduate supervision. This part is really hard to quantify. First of all, there are huge variations between cases. Some graduate students are so independent that they can just work completely on their own. You get monthly updates on their progress and occasional requests for professional advice. Others have to be guided, if not pulled, every step of the way. Second, this is the part of our work where the line between teaching and research is quite blurry. Writing a joint paper with a graduate student is more research than teaching. Before we got to that stage, though, chances are that the student had to read some literature with substantial guidance from me, that I had to explain the stuff and answer questions. That’s more teaching than research. Reading multiple drafts of essays and theses, commenting, re-reading, and back and forth, is teaching all the way through.

It helps when the department has a good system of graduate courses, so that the students can get to a reasonably advanced level before we have to start the individual tutoring. I did not have that luxury until recently. In my first 8 years at UBC, the department had a grand total of 4 advanced courses in areas related to my research. By “advanced”, I mean “not cross-listed”. Additional teaching credit used to be given for “reading courses” that provided a formal framework for such individual tutoring on an advanced level, but this was cancelled in 2002, before I’d had any graduate students. There is no additional teaching credit for graduating students, either.

Other university departments. Mathematicians, in terms of teaching loads and buy-outs, are probably closer to humanities professors than to their colleagues in the faculty of science. UBC has 9 departments in the faculty of science, but according to official departmental data the mathematics department does 20% of the teaching, as measured by counting the number of students enrolled in courses offered by each department. About 45% of these students are in first year service calculus courses.

For a reality check, I browsed a few other UBC departmental webpages and looked up the teaching loads of randomly selected by me research faculty. In the physics department, the usual teaching load seems to be 1 or 2 courses per year; in computer science, 2 courses. For comparison, I also looked up the English department: 4 courses per year.

Please take that with a large grain of salt. If anyone here knows the official teaching load there, please feel free to post in comments. It’s possible that some of the people I looked up had teaching buyouts or administrative reductions. Also, as I pointed out already, it’s far from true that a course equals a course equals a course. In physics courses, the lecturer often teaches a lab section as well. Many of the English courses meet only for 2 hours per week, not 3. Less work for the instructor? Not necessarily, if she goes home every week with a large pile of assignments to grade.

Buyouts. According to physicists on the internet, if you need more research time, you can use grant money to buy out your teaching. I guess that’s how it works in physics and possibly other sciences; in mathematics, not so much. For those of us in pure math, the only grants available to us on a regular basis are the NSERC Discovery Grants. The NSERC Use of Funds page does not list teaching buyouts as an eligible expense, and even if it did, the point would be moot in most cases anyway. The average DG in mathematics is less than 20K we don’t have this year’s statistics yet , and this has to pay for graduate students, postdocs, travel for the researcher and his or her group. Meanwhile, buyouts based on anecdotal evidence can run up to more than 20K per course. It can be less in some circumstances, e.g. if there is an agreement between a department and an institute to let a faculty member attend an institute program. Those of us fortunate enough to win external awards that come with substantial money e.g. Sloan, Steacie can and do use them to buy out teaching. These opportunities are only available to a select few, and generally not on an ongoing basis.

Gender. Research studies have suggested that female teachers have to be more supportive, caring, and generally work harder to get the same ratings on teaching evaluations at their male colleagues. I also have quite a lot of anecdotal evidence, from my own classes and those of my colleagues, to the effect that students are more likely to be disruptive when the class is being taught by a female instructor. If it is really typical for male instructors to spend less time on teaching preparation, as some commenters have claimed, then it might be true after all that they can count on getting away with the kind of improvising that would get female instructors trashed in class and then on teaching evaluations. Something to talk about later, perhaps.

Terence Tao: Cayley graphs and the algebra of groups

Terence Tao — Fri, 11 May 2012 22:03:10 +0000

This is a sequel to my previous blog post “Cayley graphs and the geometry of groups“. In that post, the concept of a Cayley graph of a group was used to place some geometry on that group . In this post, we explore a variant of that theme, in which fragments of a Cayley graph on is used to describe the basic algebraic structure of , and in particular on elementary word identities in . Readers who are familiar with either category theory or group homology/cohomology will recognise these concepts lurking not far beneath the surface; we wil remark briefly on these connections later in this post. However, no knowledge of categories or cohomology is needed for the main discussion, which is primarily focused on elementary group theory.

Throughout this post, we fix a single group , which is allowed to be non-abelian and/or infinite. All our graphs will be directed, with loops and multiple edges permitted.

In the previous post, we drew the entire Cayley graph of a group . Here, we will be working much more locally, and will only draw the portions of the Cayley graph that are relevant to the discussion. In this graph, the vertices are elements of the group , and one draws a directed edge from to labeled or “coloured” by the group element for any ; the graph consisting of all such vertices and edges will be denoted . Thus, a typical edge in looks like this:

Figure 1.

One usually does not work with the complete Cayley graph . It is customary to instead work with smaller Cayley graphs , in which the edge colours are restricted to a smaller subset of , such as a set of generators for . As we will be working locally, we will in fact work with even smaller fragments of at a time; in particular, we only use a handful of colours no more than nine, in fact, for any given diagram , and we will not require these colours to generate the entire group we do not care if the Cayley graph is connected or not, as this is a global property rather than a local one .

Cayley graphs are left-invariant: for any , the left translation map is a graph isomorphism. To emphasise this left invariance, we will usually omit the vertex labels, and leave only the coloured directed edge, like so:

Figure 2.

This is analogous to how, in undergraduate mathematics and physics, vectors in Euclidean space are often depicted as arrows of a given magnitude and direction, with the initial and final points of this arrow being of secondary importance only. Indeed, this depiction of vectors in a vector space can be viewed as an abelian special case of the more general depiction of group elements used in this post.

Let us define a diagram to be a finite directed graph , with edges coloured by elements of , which has at least one graph homomorphism into the complete Cayley graph of ; thus there exists a map not necessarily injective with the property that whenever is a directed edge in coloured by a group element . Informally, a diagram is a finite subgraph of a Cayley graph with the vertex labels omitted, and with distinct vertices permitted to represent the same group element. Thus, for instance, the single directed edge displayed in Figure 2 is a very simple example of a diagram. An even simpler example of a diagram would be a depiction of the identity element:

Figure 3.

We will however omit the identity loops in our diagrams in order to reduce clutter.

We make the obvious remark that any directed edge in a diagram can be coloured by at most one group element , since implies . This simple observation provides a way to prove group theoretic identities using diagrams: to show that two group elements are equal, it suffices to show that they connect together with the same orientation the same pair of vertices in a diagram.

Remark 1 One can also interpret these diagrams as commutative diagrams in a category in which all the objects are copies of , and the morphisms are right-translation maps. However, we will deviate somewhat from the category theoretic way of thinking here by focusing on the geometric arrangement and shape of these diagrams, rather than on their abstract combinatorial description. In particular, we view the arrows more as distorted analogues of vector arrows, than as the abstract arrows appearing in category theory.

Just as vector addition can be expressed via concatenation of arrows, group multiplication can be described by concatenation of directed edges. Indeed, for any , the vertices can be connected by the following triangular diagram:

Figure 4.

In a similar spirit, inversion is described by the following diagram:

Figure 5.

We make the pedantic remark though that we do not consider a edge to be the reversal of the edge, but rather as a distinct edge that just happens to have the same initial and final endpoints as the reversal of the edge. This will be of minor importance later, when we start integrating “-forms” on such edges.

A fundamental operation for us will be that of gluing two diagrams together.

Lemma 1 Labeled gluing Let be two diagrams of a given group . Suppose that the intersection of the two diagrams connects all of i.e. any two elements of are joined by a path in . Then the union is also a diagram of .

Proof: By hypothesis, we have graph homomorphisms , . If they agree on then one simply glues together the two homomorphisms to create a new graph homomorphism . If they do not agree, one can apply a left translation to either or to make the two diagrams agree on at least one vertex of ; then by the connected nature of we see that they now must agree on all vertices of , and then we can form the glued graph homomorphism as before.

The above lemma required one to specify the label the vertices of in order to form the intersection and union . However, if one is presented with two diagrams with unlabeled vertices, one can identify some partial set of vertices of with a partial set of vertices of of matching cardinality. Provided that the subdiagram common to and after this identification connects all of the common vertices together, we may use the above lemma to create a glued diagram .

For instance, if a diagram contains two of the three edges in the triangular diagram in Figure 4, one can “fill in” the triangle by gluing in the third edge:

Figure 6.

One can use glued diagrams to demonstrate various basic group-theoretic identities. For instance, by gluing together two copies of the triangular diagram in Figure 4 to create the glued diagram

Figure 7.

and then filling in two more triangles, we obtain a tetrahedral diagram that demonstrates the associative law :

Figure 8.

Similarly, by gluing together two copies of Figure 4 with three copies of Figure 5 in an appropriate order, we can demonstrate the Abel identity :

Figure 9.

In addition to gluing, we will also use the trivial operation of erasing: if is a diagram for a group , then any subgraph of formed by removing vertices and/or edges is also a diagram of . This operation is not strictly necessary for our applications, but serves to reduce clutter in the pictures.

If two group elements commute, then we obtain a parallelogram as a diagram, exactly as in the vector space case:

Figure 10.

In general, of course, two arbitrary group elements will fail to commute, and so this parallelogram is no longer available. However, various substitutes for this diagram exist. For instance, if we introduce the conjugate of one group element by another, then we have the following slightly distorted parallelogram:

Figure 11.

By appropriate gluing and filling, this can be used to demonstrate the homomorphism properties of a conjugation map :

Figure 12.

Figure 13.

Another way to replace the parallelogram in Figure 10 is to introduce the commutator of two elements, in which case we can perturb the parallelogram into a pentagon:

Figure 14.

We will tend to depict commutator edges as being somewhat shorter than the edges generating that commutator, reflecting a “perturbative” or “nilpotent” philosophy. Of course, to fully reflect a nilpotent perspective, one should orient commutator edges in a different dimension from their generating edges, but of course the diagrams drawn here do not have enough dimensions to display this perspective easily. We will also be adopting a “Lie” perspective of interpreting groups as behaving like perturbations of vector spaces, in particular by trying to draw all edges of the same colour as being approximately though not perfectly parallel to each other and with approximately the same length .

Gluing the above pentagon with the conjugation parallelogram and erasing some edges, we discover a “commutator-conjugate” triangle, describing the basic identity :

Figure 15.

Other gluings can also give the basic relations between commutators and conjugates. For instance, by gluing the pentagon in Figure 14 with its reflection, we see that . The following diagram, obtained by gluing together copies of Figures 11 and 15, demonstrates that ,

Figure 16.

while this figure demonstrates that :

Figure 17.

Now we turn to a more sophisticated identity, the Hall-Witt identity

which is the fully noncommutative version of the more well-known Jacobi identity for Lie algebras.

The full diagram for the Hall-Witt identity resembles a slightly truncated parallelopiped. Drawing this truncated paralleopiped in full would result in a rather complicated looking diagram, so I will instead display three components of this diagram separately, and leave it to the reader to mentally glue these three components back to form the full parallelopiped. The first component of the diagram is formed by gluing together three pentagons from Figure 14, and looks like this:

Figure 18.

This should be thought of as the “back” of the truncated parallelopiped needed to establish the Hall-Witt identity.

While it is not needed for proving the Hall-Witt identity, we also observe for future reference that we may also glue in some distorted parallelograms and obtain a slightly more complicated diagram:

Figure 19.

To form the second component, let us now erase all interior components of Figure 18 or Figure 19:

Figure 20.

Then we fill in three distorted parallelograms:

Figure 21.

This is the second component, and is the “front” of the truncated praallelopiped, minus the portions exposed by the truncation.

Finally, we turn to the third component. We begin by erasing the outer edges from the second component in Figure 21:

Figure 22.

We glue in three copies of the commutator-conjugate triangle from Figure 15:

Figure 23.

But now we observe that we can fill in three pentagons, and obtain a small triangle with edges :

Figure 24.

Erasing everything except this triangle gives the Hall-Witt identity. Alternatively, one can glue together Figures 18, 21, and 24 to obtain a truncated parallelopiped which one can view as a geometric representation of the proof of the Hall-Witt identity.

Among other things, I found these diagrams to be useful to visualise group cohomology; I give a simple example of this below, developing an analogue of the Hall-Witt identity for -cocycles.

— 1. A Hall-Witt identity for -cocycles —

It is instructive to start interpreting the basic building blocks of group homology and group cohomology in terms of these diagrams; among other things, this interpretation highlights the close relationship between group cohomology and other types of cohomology, such as simplicial cohomology and de Rham cohomology. We will not do so systematically here, but present just a small fragment of group cohomology in this setting, to give the flavour of things.

To warm up, let’s begin with the easy theory of -cohomology. Fix some coefficient ring e.g. the integers , the reals , or a cyclic group such as ; for the elementary cohomology topics we will be presenting here, the exact choice of the coefficient ring will not be important . A -cochain is just a map . Using our diagram perspective, we can interpret a -cochain in a “de Rham” way as a “-form” that assigns the element of to any oriented edge in a diagram that has colour . By definition, we also define the integral along the reversal of an oriented edge in a diagram by . Note though that the integral along a edge is not necessarily the negation of the integral along a edge, since we may have . This explains the previous remark that we do not view a edge as the reversal of a edge. Similarly, since need not equal , the integral of on a loop need not be non-zero. Thus one has to take a little bit of care with the analogy between group cohomology and de Rham cohomology. However, if the -chain is normalised in the sense that and which is for instance the case with the -cocycles discussed below , then the analogy becomes more accurate.

Given any oriented path in a diagram consisting of a sequence of edges which either are aligned with, or have the opposite orientation from, the edge in the diagram , we can then define the “ line integral” of a -cochain as the sum of the individual edge integrals . A key point here is that of translation invariance; if two paths are translates of each other, in the sense that they have the same length and the colours of their edges match, then they have the same line integral with respect to .

Remark 2 One can of course more generally integrate -cocycles against -chains, namely formal linear combinations of oriented edges with coefficients in , which is the starting point for the diagrammatic interpretation of group homology, but we will not use this formalism here.

A -cocycle is a -cochain which obeys the identity

for all . Of course, this equation is nothing more than the assertion that is a group homomorphism from to ; but let us pretend that we are unaware of this interpretation of -cocycles, and instead interpret the -cocycle condition diagramatically, as the fact that the line integral around any triangle Figure 4 vanishes. Because any closed loop in a diagram can be triangulated possibly after first filling in some more edges , we see more generally that a -cocycle is nothing more than a -cochain which is closed in the sense that its integral on any closed loop is zero. On the other hand, we also have translation invariance of the -cocycle, which leads to some additional cancellations. For instance, by integrating a -cocycle against the pentagon in Figure 14, the contribution of the edges of matching colour cancel each other out, leaving one with the conclusion that

for all and any -cocycle . Of course, this fact was already obvious from the group homomorphism interpretation, but the point is that it can also be observed “geometrically” by inspection of a relevant diagram. Similarly, from Figure 11 we have for any and any -cocycle .

Next, we define a -cochain to be a function . Just as -cochains can be viewed as “-forms” that can be integrated on oriented edges and thus oriented paths, we can view -cochains as “-forms” that can be integrated on oriented triangles and thus triangulated surfaces, though we make the technical restriction that our triangles must be of the form in Figure 4, i.e. not all arrows are oriented in the same direction. We can then interpret as the integral of on the triangle in Figure 4, endowed with the clockwise orientation; reversing the orientation of this triangle leads to a negation of the integral. One can then integrate on any oriented triangulated surface or, more generally, -chains, as mentioned previously in a diagram in the obvious fashion, provided that in each triangle, the arrows are not all oriented in the same direction.

A -cocycle is a -cochain which obeys the identity

for all . As we will recall later, -cocycles can be viewed as coordinatisations of central -extensions of , but we will again pretend that we are unaware of this interpretation of -cocycles, and instead take a diagrammatic interpretation which has the advantage over the central extension interpretation that it extends much more readily to higher orders of cohomology than -cohomology . The cocycle identity 2 is then asserting that the integral of on the tetrahedron in Figure 8 or, in fact, any other tetrahedron vanishes. Because any closed oriented triangulated -surface on a diagram can be broken up into tetrahedra again after filling in some edges if necessary , we conclude that a -cocycle is nothing more than a -cochain which is closed in the sense that its integral on any closed triangulated -surface vanishes. Among other things, this now allows one to define the integral of a -cocycle on any oriented surface not necessarily closed or triangulated which is bordered by some closed loop in a diagram, by replacing by some triangulated oriented surface with the same oriented boundary as . For instance, we can integrate a -cocycle

New bounds for Szemeredi’s theorem, Ia: Progressions of length 4 in finite field geometries revisited

New bounds for Szemeredi’s theorem, Ia — Fri, 11 May 2012 12:04:52 +0000

Ben Green and I have just uploaded to the arXiv our paper “New bounds for Szemeredi’s theorem, Ia: Progressions of length 4 in finite field geometries revisited“, submitted to Proc. Lond. Math. Soc.. This is both an erratum to, and a replacement for, our previous paper “New bounds for Szemeredi’s theorem. I. Progressions of length 4 in finite field geometries“. The main objective in both papers is to bound the quantity for a vector space over a finite field of characteristic greater than , where is defined as the cardinality of the largest subset of that does not contain an arithmetic progression of length . In our earlier paper, we gave two arguments that bounded in the regime when the field was fixed and was large. The first “cheap” argument gave the bound

and the more complicated “expensive” argument gave the improvement

for some constant 0}' title='{c>0}' class='latex' /> depending only on .

Unfortunately, while the cheap argument is correct, we discovered a subtle but serious gap in our expensive argument in the original paper. Roughly speaking, the strategy in that argument is to employ the density increment method: one begins with a large subset of that has no arithmetic progressions of length , and seeks to locate a subspace on which has a significantly increased density. Then, by using a “Koopman-von Neumann theorem”, ultimately based on an iteration of the inverse theorem of Ben and myself and also independently by Samorodnitsky , one approximates by a “quadratically structured” function , which is locally a combination of a bounded number of quadratic phase functions, which one can prepare to be in a certain “locally equidistributed” or “locally high rank” form. It is this reduction to the high rank case that distinguishes the “expensive” argument from the “cheap” one. Because has no progressions of length , the count of progressions of length weighted by will also be small; by combining this with the theory of equidistribution of quadratic phase functions, one can then conclude that there will be a subspace on which has increased density.

The error in the paper was to conclude from this that the original function also had increased density on the same subspace; it turns out that the manner in which approximates is not strong enough to deduce this latter conclusion from the former. One can strengthen the nature of approximation until one restores such a conclusion, but only at the price of deteriorating the quantitative bounds on one gets at the end of the day to be worse than the cheap argument.

After trying unsuccessfully to repair this error, we eventually found an alternate argument, based on earlier papers of ourselves and of Bergelson-Host-Kra, that avoided the density increment method entirely and ended up giving a simpler proof of a stronger result than 1 , and also gives the explicit value of for the exponent in 1 . In fact, it gives the following stronger result:

Theorem 1 Let be a subset of of density at least , and let 0}' title='{\epsilon>0}' class='latex' />. Then there is a subspace of of codimension such that the number of possibly degenerate progressions in is at least .

The bound 1 is an easy consequence of this theorem after choosing and removing the degenerate progressions from the conclusion of the theorem.

The main new idea is to work with a local Koopman-von Neumann theorem rather than a global one, trading a relatively weak global approximation to with a significantly stronger local approximation to on a subspace . This is somewhat analogous to how sometimes in graph theory it is more efficient from the point of view of quantative estimates to work with a local version of the Szemerédi regularity lemma which gives just a single regular pair of cells, rather than attempting to regularise almost all of the cells. This local approach is well adapted to the inverse theorem we use which also has this local aspect , and also makes the reduction to the high rank case much cleaner. At the end of the day, one ends up with a fairly large subspace on which is quite dense of density and which can be well approximated by a “pure quadratic” object, namely a function of a small number of quadratic phases obeying a high rank condition. One can then exploit a special positivity property of the count of length four progressions weighted by pure quadratic objects, essentially due to Bergelson-Host-Kra, which then gives the required lower bound.

Filed under: math.CO, paper Tagged: arithmetic progressions, Ben Green, finite fields, Szemeredi's theorem

gowers: A look at a few Tripos questions VI

gowers — Fri, 11 May 2012 10:40:43 +0000

I’m now going to turn to the Numbers and Sets questions from the same year, 2003. I’ve lost count of the number of times I’ve heard people say that the course is quite easy but the questions on the examples sheets and exams are very hard and “not very closely related to the course”. There is a grain of truth in that: the new concepts you have to grasp in Numbers and Sets are not as difficult as the new concepts you have to grasp in most of the other courses, so in order to give enough substance to Tripos questions the examiners are almost forced to put in a significant problem-solving element. However, certain styles of problem occur quite regularly, so it’s good to get a bit of practice. And perhaps a detailed discussion of the 2003 questions will be helpful as well. As I did with Analysis I, I’ll start with a post on the Section I questions and then I’ll have separate posts for each of the four Section II questions. The paper, by the way, is Paper 4.

1. i Prove by induction or otherwise that for every ,

ii Show that the sum of the first positive cubes is divisible by 4 if and only if or mod 4 .

Part i could be an A-level question I think . Is there a neat way to do it? I’ll think about the “or otherwise” possibility in a moment, but let’s go for the straightforward approach of using induction.

A non-neat approach would be to prove the well-known formula for the sum of the first positive integers and then prove by induction that the square of that, i.e., , is the sum of the first positive cubes. But let’s see what happens if we just take the statement as it stands and try to prove it by induction. Here’s what I would write to start with.

The statement is certainly true when , since both sides equal 1. Now suppose that it is true for . Then it will be true for if

Hmm, that looks sort of promising because it we have a difference of two squares. So next I’d write this.

The right-hand side is a difference of two squares, and therefore equals .

Now we don’t seem to have much alternative but to work out the sum of the first integers. We might as well use the standard trick.

But . Therefore, , which shows that the right-hand side is , as required.

I don’t know whether that was the best thing to do, but the point is that this question can be hacked out pretty quickly one way or another.

What about the second part? Well, the golden rule of Tripos questions applies, since it is related to the first part. Here goes.

By Part i , it is enough to prove that the sum of the first positive integers is even if and only if or 3 mod 4 . To see this, note that has the same parity as when is even and different parity when is odd. Therefore, mod 2 the sums are 1, 1, 0, 0, 1, 1, 0, 0, and so on.

That completes the question. A quick remark is that what I wrote in that last paragraph might look slightly sloppy, because I didn’t set out a formal inductive argument. However, what I wrote a got to the heart of the matter and b clearly could be turned into a formal inductive argument. If you feel tempted to leave out details, you should be very sure that you know how to fill in those details, and that the examiner knows that you know how to fill them in, and that the reason you’ve left them out is that they are quite long to write out and genuinely uninteresting. It’s a judgment call, and I’d suggest erring on the safe side.

What about the “or otherwise”? A fact like that must surely have some reason for being true. It feels like one of those things that is true because of some picture of balls arranged in a “right-angled isosceles tetrahedron”. Except that that’s not quite correct, because the picture looks as though it needs to be four-dimensional.

Is there something we can count in two different ways, getting the left-hand side if we count one way and the right-hand side if we count the other way?

To get the right-hand side we could take the Cartesian product of two discrete right-angled triangles. More formally, we could take the set of all quadruples of non-negative integers such that and . But how do we relate that to a bunch of cubes?

Let’s try to find a nice set of points that gives us the bunch of cubes. We could take the set of all quadruples of positive integers such that and and are all at most .

Is there a nice bijection between these two sets? I can’t see one. I think I’m going to cheat and use the internet.

Done that, and although I found a pictorial proof, it was basically just a pictorial version of the above analytic proof, and therefore not very interesting. On to the second question.

2C. What is an equivalence relation? For each of the following pairs , determine whether or not is an equivalence relation on .

i , iff is an even integer.

ii , iff .

iii , iff .

iv , iff is times a perfect square.

A first tip here is not to try to make guesses such as, “There’s bound to be at least one false statement.” Examiners have sometimes played evil tricks, but more importantly your aim here is to think about the mathematics. And since it’s a Section I question your starting assumption which occasionally has to be revised should be that the mathematics is pretty easy.

Let’s get started. First dilemma: how much can we assume when defining an equivalence relation? Is it enough to say, “An equivalence relation is a relation that is reflexive, symmetric and transitive?” Or do we need to define those three properties as well? And do we need to say what a relation is?

These questions don’t have very definite answers. The examiner was probably expecting candidates at least to define the three properties, but would probably have found it quite hard to remove marks for somebody who didn’t do so. Anyhow, since there are three options of increasing explicitness, I think I’ll compromise and go for the second.

An relation on a set is reflexive if for every . It is symmetric if for every . It is transitive if for every . It is an equivalence relation if it is reflexive, symmetric and transitive.

I felt free to use the shorthand , since its meaning was very clear. One thing that was important was to demonstrate that I knew how the quantifiers worked. For instance, I didn’t just write, “ is symmetric if ,” but I added the words “for every “.

Now to the more interesting part of the question. It’s pretty obvious that the first relation is an equivalence relation. Is there a quicker way of proving it than writing out some very obvious calculations? We might consider defining a partition, but perhaps, since the boring method isn’t too laborious, it’s better not to bother to think. Here’s the boring method.

i Let . Then , which is an even integer. If for some integer , then . And if and , then . Since were arbitrary, this shows that is reflexive, symmetric and transitive, so it is an equivalence relation.

Here’s how one might try to do it with partitions. Even if I don’t necessarily recommend this approach, I definitely recommend, as I’ve said before, at least considering using alternative definitions.

i For every real number in the interval , let be the set . Then the sets form a partition of and if and only if and belong to the same cell of this partition. Therefore, is an equivalence relation.

Hmm … I don’t really like that, because I feel an obligation to prove that distinct really are disjoint and that every real number belongs to some . These statements, though not hard to prove, are hard enough to make this approach longer than the boring approach.

Now let’s look at the second example. There are two possibilities here. If you can’t immediately see whether this is an equivalence relation, then just dive in and do the calculations. You’ll end up writing something like this.

ii Let . Then , which is a positive real number. If , then so is , since . And if and , then . Since is a non-zero real, . This shows that is an equivalence relation.

If you’re up on your complex numbers, you’ll recognise that the relation is saying that and belong to the same line through the origin. That would allow you to give a partitions proof.

ii Every non-zero complex number can be written uniquely in the form for some 0' title='r>0' class='latex' /> and some . It can also be written uniquely in the form with a non-zero real number positive or negative and . If and are written in the second form, then , which is real if and only if . Therefore, is an equivalence relation.

Annoyingly, that again wasn’t as quick as I’d hoped, but it feels like a better explanation of why is an equivalence relation.

I counselled against trying to second guess the examiner, but here it really does seem likely that iii is going to be false, given its similarity to ii . Why? Well, if the relation in part iii is an equivalence relation, then the proof that it is an equivalence relation will presumably be very similar to the proof in part ii , and it would be very odd for the examiner to ask you to do essentially the same thing twice. This isn’t a completely conclusive argument, but it does suggest that we begin by looking for a counterexample.

It’s almost always a good idea with a question of this flavour to try the simplest thing you possibly can and work upwards. What’s the simplest non-zero complex number? I’d go for 1. So let’s take 1 for . Now we need such that is real. The simplest example I can think of is 1. But that’s a problem, because we’re now not going to be able to find such that is an integer but is not. So a minimal requirement of our is that it should not equal .

Let us therefore backtrack to where we chose . We want the simplest non-zero complex number such that is an integer and . How about 2? What does that tell us we need of ? We need to be an integer, but not to be an integer. That’s easy enough. The simplest number that has that property is , and we’re done.

Here’s what one would actually write out after those thoughts.

iii Let , and . Then and , but . Therefore, is not transitive and so not an equivalence relation.

One thing not to do is a technique that many people seem to like, which is to write out a proof, get to a step that doesn’t seem to hold in general, and argue that that is a proof that the result fails. Here’s what it might look like in this case. Here I’m giving a model non-answer, so to speak.

Hmm, I was just about to set out on that when I realized that I’d done something a little foolish, which was to assume that if the relation failed to be an equivalence relation then the problem would lie with transitivity. But actually it’s not even reflexive. So a better answer would have been this.

iii Since , the relation is not reflexive and is therefore not an equivalence relation.

However, let me try to give a model non-answer to the question “Is the relation transitive?” The right approach is to give a simple counterexample. The wrong approach is to write something like this.

Let . If and , then . This shows that is an integer, but that doesn’t necessarily imply that is an integer. Therefore, is not transitive.

The trouble with what I’ve just written is that the failure of a proof attempt doesn’t prove that a result is false. It can, however, guide one to a proof. Here, for example, we see that we’re looking for an example where is an integer but not . So it’s pretty natural to think of taking and then , which isn’t the same example as before but it’s very similar.

On to the fourth part. Here one can profitably use the information that this is a Section I question. This relation is obviously reflexive and symmetric, but there doesn’t seem to be a trivial proof that it is transitive. Why not? Because if and , then , and that doesn’t have to be a perfect square. Again, that’s a useful thought to have, but it doesn’t constitute an answer to the question. For all we know, and have to be very special kinds of perfect squares because they are differences of squares , and perhaps if you add two of those very special squares together, you always get a perfect square.

This is where the fact that we’re doing a Tripos question comes in. If a statement like that were true, it would be a piece of serious number theory. This is a fraction of a Section I question, so we probably aren’t expected to come up with a piece of serious number theory unless it’s very obvious bookwork, which this isn’t . So the result is probably false. So we should try to find a counterexample.

Our example can’t be too trivial — in particular, we need all three of and to be distinct to have any hope of its being a counterexample. Help, that means we need some Pythagorean triples. I can only think of 3,4,5 and 5,12,13. Ah, but I see a potentially useful feature of those, which is that they both contain the number 5. Can that somehow be worked into an example? I probably want to set since will be common to my two assumptions. So how about and ? That gives me that , which is fine. And ? I might as well take 12 and see what happens? I get . Oops. OK, then. That’s better, . Now, what is ? It is , which, thankfully, is not plus or minus a perfect square.

Having thought of that, I can make it slightly neater by switching things round. Here’s what I’d write.

iv Let , and . Then and , but , which is not a perfect square. Therefore, is not transitive and so not an equivalence relation.

That part strikes me as medium hard for a Section I question — the kind of thing that many people would have spotted and many people would not have spotted. But maybe I’m wrong about that: you’re more or less forced to look for Pythagorean triples and then the first two such triples that we all know about from school do the job.

Update: It has subsequently occurred to me that my answer to iv was needlessly complicated. I could have used the same Pythagorean triple twice. For instance, setting and we get , , but , which is not a perfect square.

Scott: I was wrong about Joy Christian

Scott — Thu, 10 May 2012 16:07:57 +0000

Update: I decided to close comments on this post and the previous Joy Christian post, because they simply became too depressing for me.

I’ve further decided to impose a moratorium, on this blog, on all discussions about the validity of quantum mechanics in the microscopic realm, the reality of quantum entanglement, or the correctness of theorems such as Bell’s Theorem. I might lift the moratorium at some future time. For now, though, life simply feels too short to me, and the actually-interesting questions too numerous. Imagine, for example, that there existed a devoted band of crackpots who believed, for complicated, impossible-to-pin-down reasons of topology and geometric algebra, that triangles actually have five corners. These crackpots couldn’t be persuaded by rational argument—indeed, they didn’t even use words and sentences the same way you do, to convey definite meaning. And crucially, they had infinite energy: you could argue with them for weeks, and they would happily argue back, until you finally threw up your hands in despair for all humanity, at which point the crackpots would gleefully declare, “haha, we won! the silly ‘triangles have 3 corners’ establishment cabal has admitted defeat!” And, in a sense, they would have won: with one or two exceptions, the vast majority who know full well how many corners a triangle has simply never showed up to the debate, thereby conceding to the 5-cornerists by default.

What would you in such a situation? What would you do? If you figure it out, please let me know but by email, not by blog comment .

In response to my post criticizing his “disproof” of Bell’s Theorem, Joy Christian taunted me that “all I knew was words.” By this, he meant that my criticisms were entirely based on circumstantial evidence, for example that 1 Joy clearly didn’t understand what the word “theorem” even meant, 2 every other sentence he uttered contained howling misconceptions, 3 his papers were written in an obscure, “crackpot” way, and 4 several people had written very clear papers pointing out mathematical errors in his work, to which Joy had responded only with bluster. But I hadn’t actually studied Joy’s “work” at a technical level. Well, yesterday I finally did, and I confess that I was astonished by what I found. Before, I’d actually given Joy some tiny benefit of the doubt—possibly misled by the length and semi-respectful tone of the papers refuting his claims. I had assumed that Joy’s errors, though ultimately trivial how could they not be, when he’s claiming to contradict such a well-understood fact provable with a few lines of arithmetic? , would nevertheless be artfully concealed, and would require some expertise in geometric algebra to spot. I’d also assumed that of course Joy would have some well-defined hidden-variable model that reproduced the quantum-mechanical predictions for the Bell/CHSH experiment how could he not? , and that the “only” problem would be that, due to cleverly-hidden mistakes, his model would be subtly nonlocal.

What I actually found was a thousand times worse: closer to the stuff freshmen scrawl on an exam when they have no clue what they’re talking about but are hoping for a few pity points. It’s so bad that I don’t understand how even Joy’s fellow crackpots haven’t laughed this off the stage. Look, Joy has a hidden variable λ, which is either 1 or -1 uniformly at random. He also has a measurement choice a of Alice, and a measurement choice b of Bob. He then defines Alice and Bob’s measurement outcomes A and B via the following functions:

A a,λ = something complicated = as Joy correctly observes λ

B b,λ = something complicated = as Joy correctly observes -λ

I shit you not. A a,λ = λ, and B b,λ = -λ. Neither A nor B has any dependence on the choices of measurement a and b, and the complicated definitions that he gives for them turn out to be completely superfluous. No matter what measurements are made, A and B are always perfectly anticorrelated with each other.

You might wonder: what could lead anyone—no matter how deluded—even to think such a thing could violate the Bell/CHSH inequalities? Aha, Joy says you only ask such a naïve question because, lacking his deep topological insight, you make the rookie mistake of looking at the actual outcomes that his model actually predicts for the actual measurements that are actually made. What you should do, instead, is compute a “correlation function” E a,b that’s defined by dividing A a,λ B b,λ by a “normalizing factor” that’s a product of the quaternions a and b, with a divided on the left and b divided on the right. Joy seems to have obtained this “normalizing factor” via the technique of pulling it out of his rear end. Now, as Gill shows, Joy actually makes an algebra mistake while computing his nonsensical “correlation function.” The answer should be -a.b-a×b, not -a.b. But that’s truthfully beside the point. It’s as if someone announced his revolutionary discovery that P=NP implies N=1, and then critics soberly replied that, no, the equation P=NP can also be solved by P=0.

So, after 400+ comments on my previous thread—including heady speculations about M-theory, the topology of spacetime, the Copenhagen interpretation, continuity versus discreteness, etc., as well numerous comparisons to Einstein—this is what it boils down to. A a,λ = λ and B b,λ = -λ.

I call on FQXi, in the strongest possible terms, to stop lending its legitimacy to this now completely-unmasked charlatan. If it fails to do so, then I will resign from FQXi, and will encourage fellow FQXi members to do the same.

While I don’t know the exact nature of Joy’s relationship to Oxford University or to the Perimeter Institute, I also call on those institutions to sever any connections they still have with him.

Finally, with this post I’m going to try a new experiment. I will allow comments through the moderation filter if, and only if, they exceed a minimum threshold of sanity and comprehensibility, and do not randomly throw around terms like “M-theory” with no apparent understanding of what they mean. Comments below the sanity threshold can continue to appear freely in the previous Joy Christian thread which already has a record-setting number of comments… .

Update May 11 : A commenter pointed me to a beautiful preprint by James Owen Weatherall, which tries sympathetically to make as much sense as possible out of Joy Christian’s ideas, and then carefully explains why the attempt fails long story short: because of Bell’s theorem! . Notice the contrast between the precision and clarity of Weatherall’s prose—the way he defines and justifies each concept before using it—and the obscurity of Christian’s prose.

Another Update: Over on the previous Joy Christian thread, some commenters are now using an extremely amusing term for people who believe that theories in physics ought to say something comprehensible about the predicted outcomes of physics experiments. The term: “computer nerd.”

Third Update: Quite a few commenters seem to assume that I inappropriately used my blog to “pick a fight” with poor defenseless Joy Christian, who was minding his own business disproving and re-disproving Bell’s Theorem. So let me reiterate that I wasn’t looking for this confrontation, and in fact took great pains to avoid it for six years, even as Joy became more and more vocal. It was Joy, not me, who finally forced matters to a head through his absurd demand that I pay him $100,000 “with interest,” and then his subsequent attacks.

David Speyer: Fun with y^2=x^p-x

David Speyer — Thu, 10 May 2012 08:01:51 +0000

Here’s a basic example that comes up if you work with elliptic curves: Let be a prime which is . Let be the elliptic curve over a field of characteristic . Then has an endomorphism . It turns out that, in the group law on , we have . That is to say, plus copies of is trivial.

I remember when I learned this trying to check it by hand, and being astonished at how out of reach the computation was. There are nice proofs using higher theory, but shouldn’t you just be able to write down an equation which had a pole at and vanished to order at ?

There is a nice way to check the prime by hand. I’ll use for equivalence in the group law of . Remember that the group law on has and has whenever , and are collinear.

We first show that

Proof of : We want to show that , and add up to zero in the group law of . In other words, we want to show that these points are collinear. We just check:

as desired. .

Use of : Let be a point on . Applying twice, we get

.

Now, the horizontal line crosses at three points: , and . Of course, , since we are in characteristic three. So and we have

as desired. .

I was reminded of this last year when Jared Weinstein visited Michigan and told me a stronger statement: In the Jacobian of , we have , where is once again the automorphism .

Let me first note why this is related to the discussion of the elliptic curve above. Please don’t run away just because that sentence contained the word Jacobian! It’s really a very concrete thing. I’ll explain more below. Letting be the curve , and letting be , we have a map sending , and this map commutes with . I’m going to gloss over why checking on will also check it on , because I want to get on to playing with the curve , but it does.

So, after talking to Jared, I was really curious why acted so nicely on the Jacobian of . There are some nice conceptual proofs but, again, I wanted to actually see it. Now I do.

Let be any odd prime. Let be the curve , over a field of characteristic . We’ll be working in the Jacobian of . This is a group , generated by the points of , and subject to the relation that, if there is a polynomial vanishing precisely at the points , , …, , then . If you’ve seen this theory laid out for projective curves, then you use rational functions rather than polynomials, and you have to keep track of poles as well as zeroes. Because I’m using the affine curve , I get to just work with polynomials and their zeroes.

When we run this construction for a curve of the form , then the elements of the group are just the points on the curve, plus the additive identity. Let’s see why: , as these are the two points on the line , so we don’t need formal inverses. And for any two points and with , the line through these points will meet the curve once more, say at , so we have . We can repeatedly use this trick to reduce sums of many points to sums of fewer points.

I am now asking you to consider , which except when is not of the form
. This means that not every element of will be equivalent to a single point of the curve . Other than that, the theory really isn’t harder.

The curve has an endomorphism , just as before. And, just as before, what we are going to be showing is that as endomorphisms of the group . In particular, when , we have .

The key identity

We’re going to figure out how to generalize equation for all primes. The equation we want is

.

Here is the quadratic residue symbol: it equals if is a quadratic residue modulo ; it equals if is a non-QR and if .

Just as in the case, we’ll want to rewrite this to have fewer minus signs. For any on , the vertical line meets at two points: and . So . So we can rewrite our desired equation as

.

So we need to find a polynomial which passes through the points . Set

.

Since , the polynomial will pass through all of the points . Where else does meet ?

Well, if then . Plugging this into the equation for , we have

or

.

This is a degree polynomial in . We already know of the roots — they are at for a nonzero element of .

Equation has leading term , and constant term . So we can conclude that the product of the roots of is . We have . So the last root of is at . A little more thought shows that the intersection of with is at , not .

So we have found a polynomial which vanishes precisely at the points and , and we have proved equation .

Why we’ve won

Let be the automorphism of the curve . Clearly, . A little less obviously, I claim that in the endomorphism ring of the group . In other words, I am claiming that, for any on , we have

This is because the points are precisely the intersections of with the horizontal line .

So is a module for the ring . This is better known as the ring of cyclotomic integers. And identity tells us that

in the ring .

The right hand side of the above equation is a very famous element of : The Gauss sum. And it’s most famous property is that — exactly what we wanted to show.

Let’s review why the Gauss sum has the desired square.

.
Group together terms with the power of to get

.

If , then takes on every value in once, except that it misses . If , then takes on the value over and over, times in total. Using , our sum is

as desired.

What I want to emphasize is that every equality of this proof corresponds to writing down a rational function on with the corresponding poles and zeroes. For example, the second to last equality above replaced by . There is a corresponding rational function which has zeroes at and has a pole at : Namely, . It would be painful, but completely doable, to actually use this proof to write down a rational function on with a zero at , and a -fold pole at . In fact, I cheated a bit in the beginning of this post. I didn’t just cleverly guess the formula ; I instead wrote down and plugged in .

Descending the resulting rational function to the curve would probably leave an unmotivated mess. I understand how to do it: You need to look at the rational function of and rewrite it in the variables ; Galois theory guarantees that you will succeed. But I suspect the result would be unenlightening.

So, finally, I understand why without going through the theory of supersingular curves, or the Weil bounds, or anything deeper than Gauss sums. Hope you enjoyed!

Scott Morrison: Mathematicians take a stand

Scott Morrison — Thu, 10 May 2012 08:01:50 +0000

Douglas Arnold and Henry Cohn have just posted to the arXiv their article Mathematicians take a stand, which will also appear in the Notices of the AMS shortly.

In it they describe the background to the Elsevier boycott, and make a case for more people joining in. It might appear at this point that the boycott is losing steam, but I’m pretty sure this is not the case. A lot has been happening, although too much of it is “behind the scenes”. Elsevier has made some concessions, although these so far seem to mostly miss the point. There’s a rumour of more to come. Two weeks ago some representatives met with the Journal of Number Theory’s editorial board, to discuss their concerns. The meeting was inconclusive, but it seems the editorial board there remains unsatisfied with Elsevier. It appears that the minutes of that meeting are googleable…

I hope that the prestigious mathematics journals still with Elsevier particularly the three discussed in Arnold and Cohn’s article: Advances, the Journal of Algebra, and the Journal of Number Theory make sure they get what they need from Elsevier. Right now, they have the support of the mathematical community, and I hope they will not be timid about making demands. I’m not sure what’s already been discussed in private, but this would be my list:

Legal ownership of the journals to be transferred to the editorial board or their chosen representatives, with Elsevier kept on as the publisher on a contract basis.

Open access to the historical archives everything older than 5 years , with clear rules and ideally an open license, allowing access for indexing, preservation and analysis.

Prices reduced to no more than twice the per page cost of comparable journals published by professional societies, and a clear mechanism for libraries to achieve proportional reductions in bundle costs by dropping unwanted journals.

I don’t realistically expect that Elsevier will agree to any of these right away. But, nevertheless, I hope we demand this of them. At the moment their interests are simply diametrically opposed to ours — their commercial interest is to restrict access to our work, while our interest is to have the widest possible dissemination. Until they clearly see that we’re willing to take our toys and go home, I think there’s little hope of Elsevier taking meaningful steps.

Finally, it would be great to hear from editors at Elsevier journals about the impact of the boycott. Has Advances seen a decrease in quantity or quality of submissions? If so, what are they going to do about it?

David Speyer: Cheating on homework in a graduate course is staggeringly dumb

David Speyer — Thu, 10 May 2012 08:01:49 +0000

Bill Fulton informs me that there is a user on math.SE whose questions are almost entirely copies of homework questions from Math 592 Algebraic Topology and 597 Real Analysis here at Michigan. In the case of the analysis course, almost every question which had been assigned appeared on math.SE. These courses do not have their problem sets online, so it is extremely unlikely that this is someone self-studying the material at a different location. I am sure this is not the only case.

There is an interesting discussion to be had and which has been had before about how the math.SE community, and we professors, should deal with this new situation. But for tonight, I want to try persuasion. This is really extraordinarily dumb behavior on the student’s part.

I think it is safe to assume that someone who enrolls in graduate school at UMich is aiming to produce a thesis, and most likely to get a tenure track position at a research institution. Some of our students are aiming to teach at a Liberal Arts or Community College, but these positions require research too. Your future career success depends on your ability to understand the mathematics you are learning in your courses, and apply it to produce new results. There is no way to learn math without working tons of hard problems. Every bit of time you put into problem solving is a slight increase in the odds that you can get the job you are dreaming of. Why on earth would you waste that opportunity?

Moreover, you are planning to work in a closely-knit field, where personal recommendations from your senior colleagues are crucial to success. Why on earth would you take the risk of ruining your reputation in this way? And, yes, academics will view this sort of behavior very negatively — are you surprised?

Finally, you are dramatically harming the instructors ability to teach the class. When I teach advanced courses, I grade all the homework myself, and I use it to adjust my teaching. When no one solves a problem, or when the solutions all miss a basic insight, I add lectures on the relevant background. If the homework is actually being done by posters on math.SE, I lose all ability to calibrate my instruction.

ADDED: I have had a number of people raise the concern with me that I do not make clear enough that I do not know whether the student in question was a graduate student or an undergraduate. Indeed, I don’t. I believe that the professors of the effected courses know who the person is, but I don’t and I’d rather not. I assume that most students in such courses, either graduate or undergraduate, are dedicated and work tremendously hard. I’ve had several people assure me that, in particular, this is true for the students in the topology course, and I am glad to hear it.

Perhaps the student plans to work in some field very far from topology and real analysis, and thinks of the course as a waste of time. In this case, it is unfortunate that the student did not receive better advice especially because, at UMich, a student can only enroll in a limited number of courses. But, in fact, experience in any form of mathematical thinking strengthens ones overall mathematical ability. Moreover, learning fields outside one’s concentration is an excellent investment in the future. It makes you more able to participate in cross-disciplinary research which is more and more of research . It also makes you a more valuable teacher if you can cover more topics.

Perhaps the student wants to experience listening to excellent lectures on algebraic topology, but doesn’t want to do problem sets. Maybe because the student doesn’t have enough time, or maybe he believes himself to be one of the rare people who learns best by passively listening. I doubt that such people exist, but I’m willing to grant the possibility. Well, good news! This is exactly what auditing a course is for! I have never known a math professor to refuse to let someone sit in on his or her course. As a grad student, you are only required to enroll in one course a term; I encourage you to audit two or three more if that is your interest. But you should be able to find one course a term where it makes sense for you to do the homework.

Perhaps the student was having a personal crises and simply couldn’t work on some particular week? Well, in this case, that isn’t true — the questions appear at a steady rate over the last two months. But, if it were true, it would make much more sense to ask for an extension, or to simply omit a problem set. In my experience, professors at the graduate level are generally very flexible. I have some sympathy here. My senior year of undergrad, I had a major paper due the same week I started seeing an amazing lady, and I briefly considered buying a paper online to spend more time with her. What I did instead was to turn out some of the worst writing I have ever produced, collect a well deserved D+, and keep my integrity. Professor West, would you feel better to know that I married her?

Perhaps the student was badly over his head in the course? This could be a serious problem, or just a sign that the particular teaching style/subject matter was a bad fit for him. It’s an excellent issue to bring up with the professors, or with one’s advisor. Again, faculty at this level are usually extremely helpful and flexible.

Perhaps the student is an undergrad? Well, if the student plans to go on to graduate school, all of the same issues apply. In fact, the concern about recommendation letters would be extremely pressing in this case. It’s also especially unfortunate, as I know that I, and I expect most faculty, are rather sympathetic to undergrads who take graduate courses beyond their level.

Perhaps the student is an undergrad who plans to continue in some non-academic path? In that case, it may be a good strategy to get the transcript boost of some graduate courses and not worry about learning the material. Or it may not. I have a friend who, after majoring in Classics, went on to work at D.E. Shaw. When a job applicant mentioned ancient Greek fluency on her resume, he was called out to grill her. There are a lot of mathematicians working in hedge funds, so you might want to be careful what you claim to know. But, if that’s your plan, I’ll let you on to a poorly kept secret. Graduate courses are usually graded very leniently. If you just want that line on your transcript and never want to think about the course again, you could probably just do a bad job on the problem sets and get your line.

Cheating is always wrong. But I understand why my calculus students cheat — they think of the course as a formal hurdle in the way of their diploma. In a graduate course, this is the knowledge you need to begin your career. It makes no, no, no, no sense.

Scott Morrison: Onwards!

Scott Morrison — Thu, 10 May 2012 08:01:48 +0000

Although I wouldn’t want to a hit someone while they’re down, hitting a large faceless evil corporation, whose sole purpose is to extract rents from the academic community, while they’re down rather appeals to me.

Elsevier just sent out an email announcing amongst many other things, to be blogged about later, I guess they are withdrawing support for the Research Works Act.

Elsevier has announced today that we are withdrawing our support for the Research Works Act. In recent weeks, our support for the Act has caused some in the community to question our commitment to serving the global research community and ensuring the best possible access to research publications and data. We have heard concerns from some Elsevier journal authors, editors and reviewers that the Act would be seen as a step backwards for expanding options for free and low cost public access to scholarly literature. That was certainly not the intention of the legislation or our intention in supporting it. Please read our full statement online.

Good news—now let’s turn retreat into rout.

David Speyer: The recent difficulties with RSA

David Speyer — Thu, 10 May 2012 08:01:47 +0000

A team of six computer scientists Lenstra, Hughes, Augier, Bos, Kleinjung and Wachter are reporting a flaw in the way that certain SSL certificate issuers are generating RSA keys. This is getting significant online coverage at websites like NYTimes, Slashdot and BoingBoing, so I thought I’d try my hand at a low level explanation of the mathematical issues.

The goal of RSA is that you can publish a certain large number — called your public key — and anyone can then use that key to generate coded messages that only you can read. You can basically think of the RSA system like a mail drop box: Anyone can put messages into it, but only you can get them out. There many good explanations of how RSA works online, so I won’t get into the details. The essential point is that RSA keys are products of two large prime numbers. In order to make an RSA key, a computer finds two large primes and multiplies them together. The key’s owner then publishes the product, but keeps the individual primes secret. It is using these secret primes that the key’s owner can read the messages he receives. Of course, in practice, the key’s owner will have a computer program to do this all for him: I am not suggesting that Bruce Schneier actually hauls out a piece of paper with two 300 digit primes on it everytime he reads his mail!

If you want to read someone else’s mail, and it is protected by RSA, one method is to factor their key. Fortunately, factoring large numbers is believed to be very hard — much harder than multiplying them. So, what is the vulnerability?

The Euclidean algorithm

In elementary school, teachers may have assigned you to find the greatest common divisor of two numbers. For example, the greatest common divisor of and is because , , and there is no larger number which divides both and .

The way you would probably think of doing this is to find the prime factorizations of and : Namely, and . Then take the primes that they have in common namely and and discard the primes that only appear in one of the factorizations namely and . Then the GCD is the product of the overlapping primes: .

The most important thing to know about computing GCD’s is that this is the wrong way to do it. You can easily demonstrate this for yourself. Go over to Wolfram Alpha and type Factor followed by some 90 digit number. The computation will time out; this is too large to factor in the period of time that Wolfram allocates to an individual user. Now type GCD followed by two 90 digit numbers. You’ll get an answer almost instantly. Here’s mine. Clearly, Wolfram is doing something more clever than factoring those two numbers.

The right way to compute GCD’s is to use the Euclidean algorithm. This consists of repeatedly subtracting the smaller of your two numbers from the larger. For example, any common divisor of and would also divide . So . Similarly, any divisor of and would divide so . Keeping going in this way, the numbers get small very quickly: At the next step, we are looking at , and divides , so is our GCD.

The Wikipedia link has more details. Whether or not you follow them, the key point is that factoring is hard, while GCD’s are easy.

How factorization methods work

So, one way that you might try to factor some large number is to guess various numbers and compute . If you get an answer other than or , then you have found a factor. In particular, if is a product of two large primes, like in RSA, if you find one factor this way then it will be one of the primes, and dividing by that prime will give you the other factor.

If you just guess at random, you are very unlikely to find a nontrivial factor this way; you’ll just keep getting back “” from your computer. This method is no better than just directly guessing prime factors of . Modern factorization techniques are based on choosing in clever ways to increase the odds of a hit. For example, Pollard’s method is based on computing for certain carefully chosen and . The various methods that are out there increase the odds of finding a useful GCD to well above random chance, but they are still very long odds, which is why factorization is hard.

The attack

The point of the new paper is that, rather than using clever number theoretic methods to choose , a good choice of is someone else’s public RSA key. Remember, RSA keys are published, so you can just download millions of them and see whether there is a common factor.

When will this attack work? It will work if the RSA key manufacturers are reusing primes. For example, suppose that I have the key and you have the key . If a malicious person computed the GCD of 440747 and 269107 then they would discover the common prime , and a little division would give them the other factors. The problem is caused by our RSA issuer using the prime more than once.

Security experts have certainly known about this issue. But it’s a tricky one to avoid. RSA certificates are being generated continuously all around the globe, so there is no way to have a database of what primes have been used. Plus, such a database would be a huge prize for computer criminals; if you stole it, you would know exactly which prime divisors to try in a future attack!

So the approach which is used is simply to generated random primes from a very large space, and hope that the set of primes being used is large enough. If you and I are trying to go to New York City and not see each other, we don’t have to coordinate plans. We just have to each go to a random street corner and stay put, and we will almost surely succeed.

In this case, New York is the set of all 512 bit prime numbers. For 1024 bit RSA. There is also 2048 bit RSA, which uses even larger primes. These are primes that are roughly 154 digits long, and there are about of them. Considering that the number of people on earth is only around and that the number of seconds since recorded history began is around , this should be adequate. Comparing this to two tourists in New York trying to avoid each other wildly over states the difficulty. I was going to say that this is more like two atoms in New York but, in fact, there is no atom or subatomic particle small enough to indicate the hugeness of the space being used here. So this method should work and, indeed, huge portions of internet security are bet on the idea that it will.

Sidenote: Some clever readers might be remembering the game where your teacher bet you that two people in the class had the same birthday. Even though there were only of you, and days in the year, the odds were in her favor. When looking for coincidences between objects in a set of size , you should expect to start seeing them when is near , not all the way up at . But is still plenty big enough to be safe.

Theory versus practice

That’s how its supposed to work. Key generators choose random pairs of primes from a set of size , multiply them, and hand out the products. With such a large range of primes to choose from, they should never need to reuse.

But, apparently, they do. Some primes, it seems, are the Times Square of 300 digit primes. In a sampling of million RSA keys from around the internet, one particular prime turned up 12720 times! The researchers estimate that as many as in every RSA keys may be vulnerable in this way.

A few thoughts on solutions

What should the response be? Here I am hesitant to give ideas, because I am a mathematician, not a security expert. One approach is to figure out why these primes are getting reused. Another is to simply stay away from the key issuers which seem to have this problem most often; the paper reports that this issue is much rarer for some issuers than others. Or one could imagine testing each key against a few million preexisting keys, and regenerating it if a hit comes up.

I also wonder whether going to products of three primes might work, if these more basic methods don’t solve the problem. RSA works just fine with products of more than two primes, and it is believed, you need to find all the prime factors to break it. If we used products of three primes, then a single GCD hit would be survivable, just as long as not more than one of your primes was reused. Again, I hesitate to make suggestions, because this is an area where you should really rely on experts. But it sounds reasonable to me.

David Speyer: What would it take to make a noncorporate journal work from an editor’s perspective?

David Speyer — Thu, 10 May 2012 08:01:46 +0000

Let’s suppose, hypothetically, that the Elsevier boycott succeeds in decreasing the importance of many major mathematical journals. Let’s also assume that the basics of the journal system still remain unchanged — academics need to get their work certified by acceptance in journals, acceptance which demonstrates that their work is correct and reaches some particular level of importance.

Then we will need a lot of new journals, or new publishers for old journals if more editorial boards jump ship. And those journals will need editors.

I would love to hear from people with editorial experience what it would take make editing for those journals appealing and survivable. I think that many of us have been tentatively thinking of creating better journals, but are intimidated by our lack of knowledge of the effort required. I see that many leaders of the boycott movement are editors at nonprofit journals: Danny Calegari at Compositio, Henry Cohn at SIDMA, Matt Emerton at Selecta, Terry Tao at JAMS and so forth. By the way, it is incredibly intimidating digging through you folks’ CV’s! I think it would provide a wonderful anchor of reality to this conversation, to hear from experienced people about what it would take to get a journal going without a corporate owner.

This is the most obnoxious of all blogspots — the one that asks an already busy person to do more work. But, if any editors out there feel up to it, I think it would be a great help.

Scott Morrison: arXiv overlays at Scholastica

Scott Morrison — Thu, 10 May 2012 08:01:45 +0000

The guys at Scholastica some grad students at UChicago just added arXiv integration to their journal management software.

It’s pretty impressive, and it seems they’re very actively working on the software. I’m sure they’d be really excited if one upshot of the current debate about publishing was some journals switching to or new journals starting on their software. If journals are going to abandon the big commercial publishers, we need to make sure there are viable alternatives; and part of that is ensuring that the basic software for managing manuscripts and referee reports is up to par. Even if we’re not actually ready to move on any particular journals, it seems like it would be pretty useful to try out things like Scholastica, and their ‘competitors’ OJS, Annotum, and EditFlow. Explaining which features are needed to the developers, and being able to explain to editorial boards exactly what is available, will be really helpful.

I created a dummy journal on their site, called “Experiments in Mathematical Publishing“. If anyone would like to play around with the interface, try submitting a paper there. Submit one of your old arXiv papers, for example! Their interface has a feedback form, and we can discuss things here or, even better, over at the Math2.0 forum. If you submit something, I’ll ‘assign’ something to you to ‘referee’, for the sake of trying out the whole interface. If anyone would like to be an ‘editor’, just let me know. I’ll eventually delete the journal, of course.

Scott Morrison: A forum on mathematical publishing

Scott Morrison — Thu, 10 May 2012 08:01:44 +0000

There’s been lots of great discussion on the future of mathematical publishing in recent weeks, largely inspired by the boycott of Elsevier 1 2 3 . Mostly this has been happening on blogs, particularly Tim Gower’s, but also here and a number of other places. There’s a nice index of this discussion in a wiki page on Michael Nielsen’s site, to the extent that it’s possible to index a discussion happening all over the internet!

I think a lot of people find it somewhat frustrating that this discussion is predominantly happening in blog comment threads, however. It’s hard to maintain conversations, and almost impossible to coordinate people with similar interests and concerns. Andrew Stacey and I thought that it might be helpful to set up a forum like the nForum, associated the to nCafe, or meta.mathoverflow.net to alleviate this.

Thus, please check out Math 2.0! We’ll see what sticks. :-

Our hope is that this might provide a better home for more focused discussion, and a place for people who want to coordinate concrete next steps in reforming mathematical publishing. Come in and join us!

David Speyer: Some thoughts on teaching Michigan calculus

David Speyer — Thu, 10 May 2012 08:01:43 +0000

I just finished teaching two sections of first semester calculus at the University of Michigan. Michigan calculus is somewhat famous — it is very focused on conceptual and graphical understanding, spends a lot of time on “real world” data, and achieves very high scores in national measures of teaching effectiveness. Moreover, while the course coordinators are highly experienced professionals, almost all of the day-to-day instruction is done by a small army of grad students and postdocs; I was one of the very few tenured or tenure track people teaching calculus this term. I was very curious to see how this was made to work.

My intended audience here is others who are about to teach Calculus at Michigan, or people who are wondering what it would be like to set up a Michigan-style program in their own departments. A word to any of my students who find this post. Feel free to read, and feel free to call me David rather than Professor Speyer. But please don’t blast this all over your Facebook pages. I’ve said nothing that I would be unwilling to defend in public, but I’d rather that all my students not find this next time I teach the course. Let’s just keep this little moment of sharing between me and those of you who stumble upon it.

Self congratulation

My students’ median grade was a B-, almost exactly the same as the course median. Of course, I am a highly competitive person, and I wanted my sections to blow the others out of the water. But I’m going to repeat the same thing I told many of my students: Michigan is a very competitive school and everyone who gets in here is excellent. A median grade at Michigan should be a point of pride. In my case, I was competing with grad students who had taken calculus far more recently than I had; had taught it several times before; and who were often extraordinary competitors with a string of Olympiad medals and Putnam victories. Landing in the middle of that pack is an accomplishment, and I have decided to be proud of it.

I also had a lot of fun. It was more work than I expected, and it didn’t give me the same sort of stimulation that teaching an advanced research course does, but I found it really interesting thinking about how to present some of the oldest accomplishments of mathematical thought to my students. If you are at Michigan and are worried that you will be bored stiff teaching this course, I can tell you that I wasn’t.

Organization

I was assigned two sections of 32 students each, which dwindled to 30 each over the course of the term. I did the day-to-day teaching 3 times a week, 80 minutes per meeting . I also wrote and graded weekly quizzes, and graded the team homework assignments. The rest of the students’ homework, the basic decisions as to what I should cover, and the exams, were written by a small team of experienced instructors, known as the course coordinators. The coordinators also held weekly meetings to brief us on where the course was going.

The course coordinators were really hardworking and insightful people. I applaud Michigan for recognizing that it is worth paying full time staff to do this job, and finding ones who did it so well.

The course website including a secret section , was full of resources to help me plan my lessons. In Spring 2011 I often was unable to sleep for fear that I had misplanned my Hodge Theory lectures, so it was a major relief to be so well taken care of. I drifted from the given schedule by a day at times, but I basically followed it and found that it worked well.

I don’t think that this course could possibly work as well without the extensive guidance that we instructors received. If you are thinking of importing MI calculus into your school, you should think about how to take care of your teachers.

The applied and conceptual focus of the class

Calculus at Michigan focuses very heavily on working with data and on understanding what computation to do, rather than how to do it. It also focuses on getting students to be able to explain what they are doing to people with even less mathematical background than they have. I think these are very appropriate goals in theory. I feel that the former was achieved fairly well in practice, though I have some complaints, but the latter was not.

I enjoyed the real world examples. My students seemed to really get excited when I brought in data about a subject which interested them. The athletes really got a kick out of table 1 from this paper, showing how world class runners accelerate second by second; a lot of students enjoyed figuring out how long a runway a Ford Mustang needs to accelerate to 120 mph using the data here.

What was difficult about this was that it made grading very difficult to predict. We would ask questions asking people to give a “practical explanation” of such and such, or to read some data off a graph with no grid lines, and then had very specific grading policies as to what we would accept. It was hard to prepare the students for this, and the best way to do so was to have them memorize certain formulations of “practical explanations”, which were very far from any actual understanding.

The goal of teaching students to write well is a great one, but I don’t think I had the resources to actually do so, and I certainly didn’t succeed. Mathematical writing is a specialized skill. I don’t see how I could have taught it without spending far more class time on it than I had. I wound up grading the writing on the team homework much more leniently than I was told to, because I didn’t feel that I could take off points for expository errors I didn’t have time to explain.

The exams

You can see the exams here: Midterm 1 PDF , Midterm 2 PDF , Final. The exams are the major determiner of the course grade, and one feels a very strong pressure to focus one’s teaching on what the exams will cover. I have no problem with that, because I think the exams cover the right topics. If you don’t like the idea of “teaching to a test”, you might dislike teaching at Michigan.

The exams, especially the last two, were almost all challenging conceptual problems. It is strange for someone like me to say this, but I don’t think I approve of this. I would be happier if the exams had one or two more basic questions, with the rest staying as they are.

Consider a student who has learned the basic mechanical skills of numerically approximating a derivative from data, or of differentiating some complex expression. But he doesn’t understand what this really means or when to do it. This student has not learned nearly as much as we want him to. He should do poorly on the exam — a C minus or a D.

But he also has mastered a nontrivial skill. I think we should give him a question on the exam where he can display this mastery. The course’s approach is, instead, to give all difficult questions and then set a curve which will bring this student’s stammerings up to the C minus or D range.

Partly, I think this is important for maintaining student motivation. There are very few people who will enjoy an activity at which they regularly have no small successes. I am curious — the median score on the Putnam exam is a zero. How many of those competitors come back the next year? If some of my readers were among those who did, can you tell me how you stayed motivated? I feel that, psychologically, there is a big difference between having one or two questions that my hypothetical student can solidly get right, and having him pick up a smattering of partial credit on each of nine or ten questions that are too hard for him.

Also, I think that it is worth being able to detect the difference between the student I describe here, and one who has not even mastered those skills.

Team homework

My students were organized into groups of four who met weekly to work together on more challenging problems, which they wrote up as a group and received a single collective grade for. I was very concerned about this going into the course. It worked better than I expected, but I still have some concerns.

First of all, a note to any students in Michigan calculus. I highly encourage you to work hard on your team homework, and to talk in depth with your teammates about the problems. Over and over, I saw students who really committed to their teams get great benefits out of it. This happened even if none of the students on a team was strong — I had one team made up of four good friends, all of whom were in the bottom quarter of the class. Once they started working together, their performance on quizzes and in class improved dramatically.

So why the misgivings? Because, if I were a student in this class, I would have highly resented being forced to work with students not at my level. I spent a lot of time in high school and college helping my fellow students, and I learned a lot by doing so. But I wouldn’t have appreciated being forced to do it. I remember the first time — sometime in my Freshman spring — when I told my classmates “Look, it’s 3 AM and I finished this problem set yesterday. You’re welcome to keep looking at my notes, but I’m going to bed.” That was really hard. I felt guilty and awkward about it. If my grade had depended on staying awake until they understood the material, I can’t imagine how much harder that would have been.

I saw some hints of this kind of unpleasant dynamic in the teams, and I suspect there was a lot more trouble that I didn’t see. It wasn’t just the strong students who were stressed, either: I had two students who, when I asked them for teammate preferences, specifically asked not to be put with students in the top half of the class.

Working with people, no matter what, will be a source of tension. Working with people whom you don’t choose to work with, and being dependent on them for your grade — that may be how the real world works, and I see the benefits of it, but I don’t like it in my classroom.

The mathlab

Michigan has a large room called the mathlab it could probably hold 200 people or so filled with round tables and staffed 8 hours a day by tutors who can provide help with mathematics courses. It is open without appointment to anyone who wants to come ask a question. If you are taking an intro calculus course, you’ll find lots of help. If you are taking a complex analysis course, then helpers might be rarer — but sometimes you’ll find someone like me at the table, glad to see what I can do.

I think this is a great idea, and every university should set this up.

I had a lot of fun going to the mathlab. I expect that next semester, when I’m not officially teaching, I might drop in anyway to take a break. The mathlab is like a live-action version of math.SE and, while the questions are less exciting, the challenge of being face to face with the questioner makes up for it.

Some things I wish I’d known/would do differently

My more experienced colleagues told me I didn’t need to spend class time teaching mechanical differentiation skills at all. Just emphasize how crucial it was to pass the Gateway a computer administered exam testing this skill , and the students would teach themselves. I didn’t quite follow this advice; on one Friday, I dismissed class early for those who had passed the Gateway already and spent 40 minutes drilling differentiation for the remainder. But ‘s of the class had already passed the Gateway by themselves before I did this, and all but one of my students eventually did. So this advice really did turn out to work, despite my skepticism.

One of my fellow instructors offered to cook breakfast for his class if all of them passed the Gateway a week before the deadline. He wound up paying off and, not only did this make him hugely popular, but it probably relieved him of a lot of the stress I felt in the final days of the Gateway period. When I teach this class again, I will make a similar deal.

It was really hard to remember how bad my students are at systematic computation. For example, when counting boxes under a curve, they pointed at the squares in a random order, rather than sweeping from left to right, top to bottom. Every time they copied an expression from one part of the page to another, there is a high probability that a plus sign will change to a minus. If they multiplied , the terms will not appear in lexicographic order.

This has two consequences. 1 Except when I want to test/improve this skill, I should not assign problems that involve more than a few lines of computation. I missed this over and over. 2 I should think about how to directly teach this skill.

The course maintains a problem bank of suggested questions to use on quizzes and in class. There are a lot of trick questions in there! For example, one question asked students to numerically approximate at . Another geometric optimization problem asked students to construct a solid shaped like a cone on top of a cylinder to optimize some quantity, and the optimum was the degenerate case where the cone had height zero! Since there are no solutions provided, you have to really be on guard not to assign one of these without catching it.

The webhomework system assumes that 1 any graph which looks piecewise linear actually is piecewise linear and 2 the students will use that fact to make any computations with that graph precise. In my own nitpicky way, I don’t think that’s fair. I very much doubt you can visually perceive the difference between a straight line and two lines making an angle of with each other and this can make a substantial difference in an integral. This paradox demonstrates the point very vividly.

From a more practical perspective, almost none of my students naturally grasped this idea. I should have taught it explicitly.

There are a lot of problems in the webhomework mainly sections 5.2-5.4 which can only be reasonably done by typing integrals into a calculator. The intended focus of the problem is on how to set up the correct integral in the first place. I didn’t realize this was the intended method at first and spent a lot of time teaching students how to approximate them by Riemann sums or how to compute them exactly, while thinking to myself that this was way too hard for these students.

My students really got settled into their teams and didn’t like spending class time working with other students. I guess this shouldn’t have surprised me. However, when I did force them to, they often got a lot out of it. Next time, I should make sure that they spend a lot more time interacting outside their teams from the start of class.

The course coordinators really stressed how much the course focused on groupwork. I think I took these messages too strongly to heart. Especially in the first half of the term, I tried to spend almost the entire class period working with small groups. I think this is a reasonable interpretation of what I was being told, but it apparently wasn’t what they meant.

Ben Webster: “The Collapse of the Soviet Union and the Productivity of American Mathematicians”

Ben Webster — Thu, 10 May 2012 08:01:42 +0000

This is the title of a fairly interesting paper, the conclusions of which I would summarise as follows: after the collapse of the Soviet Union there was a sudden drop in the number of papers published by Americans working in fields which had been popular in the Soviet Union, which did not happen in fields which were unpopular there. Their papers were also less cited, and they moved to less prestigious institutions. Collaborating with Soviet immigrants afforded some but not total protection from this effect. Remarkably and not entirely irrelevantly for me; I’m actually a data point in the paper, and my advisor is actually mentioned by name this effect was transmitted to students: students after the fall of the Soviet Union wrote more and more cited papers if their advisor had immigrated to the US than if they had an American advisor who works topics popular among Soviets with students that had American advisors working in topics unpopular with Soviets were in between .

This is obviously a very crude analysis for example, “fields” means top level AMS Subject Class groups, which we all know are deeply flawed , but it’s still a very interesting, and to me at least slightly counter-intuitive conclusion. The authors suggest that the immigration of Soviet mathematicians to the US had a slightly negative effect on the number of papers written by all mathematicians in the US the immigrants didn’t write enough to make up for the drop amongst American authors , which is not at all what I would have expected.

The n-Category Café: What is homotopy type theory good for?

The n-Category Café — Thu, 10 May 2012 02:03:56 +0000

The current situation of homotopy type theory reminds me a bit of the dot-com bubble at the turn of the millenium.

Back then a technology had appeared which was as powerful as it was new: while everybody had a sure feeling that the technology would have dramatically valuable impact, because it was so new nobody had an actual idea of what that would be. As opposed to other bubbles, that one did not burst because overly optimistic hopes had been unjustifed as such, but because it took a while to understand just how these hopes would be materialized in detail for instance that today I would send a message as this here from a café via my webbook from my dropbox account .

With homotopy type theory the situation currently seems to be similar to me. On the one hand it is clear that some dramatic breakthrough right at the heart of mathematics has occured. One hears the sound of something big happening. But: what is the impact? It feels like after 1995 – when it was clear that the internet is going to be something big – but still before, say, 2003, when we started getting a good idea of how it changes our lives.

How will homotopy type theory change our lives?

Currently most research in homotopy type theory revolves around the fine-tuning of the formulation itself and completing the understanding of its relation to traditional homotopy theory. That’s necessary and good. It’s great, I am enthusiastic about it! But if the excitement about HoTT is not to be an illusion, then something will follow after that. The traditional homotopy theorist currently may complain and some do that much of what is happening is that facts already known are being re-formulated in a new language, not always yet to an effect a homotopy theorist would find noteworthy.

So I am wondering: how will the traditional homotopy theorist eventually benefit from homotopy type theory? How the researcher who uses homotopy theory for something else?

I am asking for personal reasons, too. Since, somewhat inadvertently, I have been investing some of my time into learning about it, I am naturally wondering: how will that time investment pay off for me? What does homotopy type theory do for my research?

I am not sure yet. But I have some first ideas. One of these I want to share here.

An example

My research, you may have noticed, is motivated from understanding basic structural phenomena in theoretical physics as incarnations of natural mathematical structures. What I will try to indicate in the following is a certain kind of problem that poses itself in the context of string theory, which – I think it is fair to say – was generally regarded to be among the more subtle problems in a field rich in subtle mathematical effects, and how it finds an elegant and simple solution once you regard it from the perspective of homotopy type theory.

What I say in the following I have said in different words before, together with my coauthors Domenico Fiorenza and Hisham Sati: in section 2 of an article titled The E8-moduli 3-stack of the C-field in M-theory. There we point out that the solution which we propose and study in the article, to some problem in string theory, can naturally be understood simply by reformulating a well-known equation – known as the flux quantization condition – first as a fiber product of sets of certain field configurations and then refining that to a homotopy fiber product of moduli ∞-stacks of certain field configurations.

Here I will just observe that if you come to this from homotopy type theory, then the solution looks even more elegant than this: one arrives there simply by taking verbatim the symbols denoting the solution set to the equation, but now interpreting these not in the ordinary logic of sets, but in the homotopy logic of homotopy types. It is then homotopy type theory which automatically produces the correct answer, the “ $E_{8}$ -moduli 3-stack of the supergravity C-field in M-theory”. A solution that looks subtle to the eye of classical logic becomes self-evident from the point of view of homotopy logic / homotopy type theory.

From these remarks everybody with just basic training in category theory and homotopy theory can already deduce what I will say below. And what I say next is not hard to see, once you see it. It is one of those cases where a simple change of perspective leads with great ease to a solution of what seemed to be a difficult technical problem. Nevertheless, or because of this, I thought I’d say this explicitly.

Formulation in ordinary logic

The situation studied in that article concerns a hypothetical physical system in which on spacetime $X$ three different species of fields propagate: 1. the field of gravity, 2. a gauge field for the gauge group E8, and 3. a higher gauge field called part of the supergravity C-field. It is not important for the following what exactly these fields are and why. Important are the following two aspects only.

Since all of them are gauge fields, there is no naive notion of equality between different field configurations. Instead, there is a sensible notion of equivalence of field configurations. In physics this is called gauge equivalence.

Moreover, since these are higher gauge fields, there is no naive notion of equality even between the gauge equivalences themselves. Instead there are higher order equialences between them. Physicists describe this state of affairs by saying that there are higher order ghosts.

In the problem under consideration in the above article, there is a constraint equation that is required to be satisfied by the gauge equivalence classes of the three fields, the “flux quantization condition”.

The question is then: what is the right collection of field configurations that satisfy the constraint equation? What are the gauge equivalences between these? What is the mathematical model for the supergravity $C$ -field?

Let’s formulate this a bit more in symbols. Naively, we would say that there is a set of configurations of the field of gravity. I’ll write that set “ $[X, B {Spin}_{conn}]$ ”, but this is just notation which you need not care about for the following, if you don’t want to. If you do, see the above article for details! Similarly there is a set $[X, B E_{8}]$ of configurations of the gauge field. And a set, to be denoted, $[X, B^{3} U 1_{conn}]$ , of configurations of part of the $C$ -field. So we’d write
$\begin{aligned} ϕ_{gr} & \in [X, B {Spin}_{conn}] \\ ϕ_{ga} & \in [X, B E_{8}] \\ ϕ_{hg} & \in [X, B^{3} U 1_{conn}] \end{aligned}$
to denote elements of these sets, representing configurations of each of these fields.

Now, each of these fields induces yet another field, much like the field of, say, electrons induces a magnetic field. We have functions that send the above field configurations to configurations of that induced field. These functions go by the following names but again, these are just names, here we only need that there are three such functions :
$\begin{aligned} \frac{1}{2} p_{1} & : [X, B {Spin}_{conn}] \to [X, B^{3} U 1] \\ 2 a & : [X, B E_{8}] \to [X, B^{3} U 1] \\ 2 G_{4} & : [X, B^{3} U 1_{conn}] \to [X, B^{3} U 1] \end{aligned} .$
In terms of this notation, that constraint equation to be satisfied by the three type of fields which I mentioned, the “flux quantization condition”, says that
$\frac{1}{2} p_{1} ϕ_{gr} + 2 a ϕ_{ga} = 2 G_{4} ϕ_{hg} .$
This is just some equation in the set $[X, B^{3} U 1]$ which happens to come equipped with the structure of an abelian group,with respect to which the addition in the above equation is formed , for the present discussion it is not important what this means, as long as you can imagine that it may happen that three gauge fields are related by some such equation.

Given all this now, one might naïvely think that the collection of fields that satisfy the flux quantization condition is the set that in traditional ZFC logic one denotes by the right hand side of
$CField X : = {ϕ_{gr}, ϕ_{ga}, ϕ_{hg} ∣ \frac{1}{2} p_{1} ϕ_{gr} + 2 a ϕ_{ga} = 2 G_{4} ϕ_{hg}} .$
However, this answer turns out to be physically wrong.

There are some evident deficiencies: this answer does not resolve the gauge transformations between fields and is hence unsuited for describing the actual quantum physics of the problem. But it is worse than that. In the correct answer there is yet one more field on $X$ .

Formulation in $∞$ -logic / homotopy type theory

Where is that extra field supposed to come from if we are imposing a constraint equation, thus seemingly reducing the degrees of freedom?

The answer is of course in the notion of homotopy or gauge transformation, which ordinary logic ignores. But this is precisely what homotopy type theory corrects. The same symbolic logical expressions are interpreted by homotopy type theory in a way that makes them correct for higher gauge theory. Automatically.

In that article we discuss how those “sets” of field configurations, $[X, B {Spin}_{conn}]$ etc., are in fact objects not of $Set$ , but of some ∞,1 -topos: they are smooth moduli ∞-stacks.

In the language of homotopy type theory the statement that there is a field configuration of, say, gravity
$ϕ_{gr} \in [X, B {Spin}_{conn}]$
becomes the statement that $ϕ_{gr}$ is a term of type $[X, B {Spin}_{conn}]$ . Of course that’s just terminology.

Now comes the key point: we form now the solution set to the flux quantization condition as we did before. But now we do so in homotopy type theory. This means we use precisely the same logical symbols as before, which I repeat for emphasis on the right of
$CField X ≔ {ϕ_{gr}, ϕ_{ga}, ϕ_{hg} ∣ \frac{1}{2} p_{1} ϕ_{gr} + 2 a ϕ_{ga} = 2 G_{4} ϕ_{hg}},$
where now the boldface on the left is to indicate that we take this expression no longer to evaluate to a set a subset of $[X, B {Spin}_{conn}] \times [X, B E_{8}] \times [X, B^{3} U 1_{conn}]$ , but now to a homotopy type. In fact, thus, to a smooth ∞-stack.

Taken apart, the above notation in homotopy type theory means

the dependent sum ${\cdot ∣ \dots}$

over the product type $[X, B {Spin}_{conn}] \times [X, B E_{8}] \times [X, B^{3} U 1_{conn}]$

of and that’s the key the dependent identity type ${Id}_{[X, B^{3} U 1]}$ .

Here is where homotopy type theory automatically does some work for us that is quite non-trivial from the classical point of view: this type $CField X$ automagically comes out as the homotopy pullback of $\frac{1}{2} p_{1} + 2 a$ along $2 G_{4}$ , the homotopy-universal way of completing the following diagram:
$\begin{matrix} CField X & \overset{}{\to} & [X, B^{3} U 1_{conn}] \\ ↓ & ⇙_{≃} & ↓^{2 G_{4}} \\ [X, B {Spin}_{conn} \times B E_{8}] & \underset{\frac{1}{2} p_{1} + 2 a}{\to} & [X, B^{3} U 1] \end{matrix}$
of smooth $∞$ -stacks, up to that gauge transformation indicated as the double arrow filling the diagram.

That this is so, hence that in type theory with identity types dependent sums over identity types express in fact homotopy pullbacks, is not entirely obvious, a priori, and is one of the hallmarks of what makes homotopy type theory interesting. For technical details see here.

In our example, the claim is that this homotopy type $CField X$ is the correct “type of $C$ -field configurations”, being the answer to a subtle question in string theory. So in conclusion, amplifying the argument of our section 2 just a bit more with an emphasis on the homotopy-logic we find: formulating a higher gauge theoretic problem as one would naively, but then reading the result in the logic of homotopy type theory, automatically takes care of otherwise subtle phenomena.

Outlook

What do we learn from the existence of homotopy type theory?

There is the explicit lesson, which drives the whole interest, it says: with just a tiny little adjustment allowing for identity types , traditional logic / type theory is a language that captures homotopy theory.

But inside this there might be another lesson of potentially more interest in common practice. That says: not only is there some formal language to capture homotopy theory. No, moreover: it’s a natural language, potentially more natural than the language you have been using so far, and speaking this language may help to make more transparent phenomena in homotopy theory that are less transparent otherwise.

Or so it feels. I would like to see this materialize in more detail. Therefore I close with a question:

Can you come up with more examples where thinking about situations in homotopy theory / in higher topos theory concretely profits from reformulating them from a homotopy-logical perspective? Some construction of natural interest involving various homotopies, homotopy pullbacks, homotopy pushouts, etc where you can step back and say: look, with homotopy type theory we can equivalently think of this as expressing the following logical formula, and this is much simpler than the original formulation?

Many of the basic definitions of Voevodsky’s in the foundation files of homotopy type theory are of the form that I am after here. For instance that the geometric procedure of giving a contracting homotopy of an $∞$ -stack $X$ is equivalent to the homotopy-logical procedure of proving $\exists_{x \in X} \forall_{y \in X} x = y$ see at contractible type for details might be taken as an example.

Or consider the notion of free loop space objects “derived loop spaces” $ℒ X$ of an $∞$ -stack $X$ . Often these are heuristically motivated as formalizing the idea that a point in them is given by “making two points in $X$ equal in two different ways” such as to yield a loop . In terms of homotopy type theory, this heuristics becomes a theorem, which reads:
$ℒ X = {x, y : X ∣ x = y and x = y} .$
These first simple examples seem to suggest that there is a whole universe of similar, but more interesting even more interesting, if you wish , homotopy-logical reformulations of familiar phenomena in homotopy theory… and hopefully eventually of unfamiliar and previously unknown phenomena. Eventually I want to collect such examples at a page like HoTT methods for homotopy theorists.

Scott: Waterman behind the scenes! Partying hard with the National Science Board

Scott — Wed, 09 May 2012 15:11:54 +0000

A few months ago, I got a surprise call from Subra Suresh, director of the National Science Foundation, who told me I was going to share this year’s Alan T. Waterman Award with Robert Wood of Harvard. At first I assumed it was a telemarketing call, since pretty much no one calls my office phone; I use my iPhone exclusively and have trouble even operating my desk phone. Dr. Suresh explained that this was the first time the Waterman would ever be awarded to two people the same year, but that the committee was unanimous in supporting both me and Rob. Looking up my co-winner, I quickly learned that Rob was a leader in the field of robot bees see here for video —and that his work, despite having obvious military applications, had been singled out by Sean Hannity as the latter’s #1 example of government waste ! . That fact, alone, made me deeply honored to share the award with Rob, and eager to meet him in person.

Happily, I finally got to do that this past Thursday, at the Waterman award ceremony in Washington DC. The festivities started in the morning, with talks by me and Rob to the National Science Board. I just performed my usual shtick. I was hoping Rob would bring some actual RoboBees, but he said he no longer does that due to an unfortunate run-in with airport security. Then, after lunch and meetings at the NSF, it was back to the hotel to change into a tux, an item I’d never worn before in my life not even at my wedding . Fortunately, my dad was there to help me insert the cufflinks and buttons, a task much more complicated than anything I was allegedly getting the award for. Then Dana and I were picked up by a limo, to begin the arduous mile-long journey from Dupont Circle to the State Department for the awards dinner.

Besides me and Rob, there were three other awardees that night:

Leon Lederman, the 89-year-old Nobel physicist whose popular book The God Particle I enjoyed as a kid, received the Vannevar Bush Award.

Lawrence Krauss, physicist and popular science writer, and National Public Radio’s science desk shared the National Science Board Public Service Award. Some readers of science blogs might recognize Lawrence Krauss from his recent brouhaha over literally nothing with the philosopher of science David Albert. For whatever it’s worth, I have little to add to Sean Carroll’s diplomatic yet magisterial summary of the issues over on Cosmic Variance.

Speaking of diplomacy, the awards dinner was held in the “diplomatic reception rooms” on the top floor of the State Department’s Harry S. Truman Building. These were pretty awesome rooms: full of original portraits of George Washington, Ben Franklin, etc., as well as antique furniture pieces like a desk that Thomas Jefferson allegedly used while writing the Declaration of Independence. I could easily eat dinner there on a regular basis.

Carl Wieman, the Nobel physicist and Associate Director for Science at the White House Office of Science and Technology Policy, read out a congratulatory message from President Obama. I feel certain the President remembered I was the same dude he shook hands with a while back.

Anyway, cutting past dinner and dessert, here was my short acceptance speech:

Thanks for this honor, and huge congratulations to my co-winners, wherever in the alphabet they might lie [a reference to my getting called up before Rob Wood, simply because Aaronson
The next day, I had the privilege of giving a quantum computing talk to more than 100 students at the Thomas Jefferson High School for Science and Technology in nearby Alexandria, VA. Visiting TJ had special meaning for me, since while I was suffering through high school, TJ was my “dream school”: I wished my parents lived in the DC area so that I could go there. I told the TJ students never to forget just how good they had it. To this day, when I meet fellow American-raised scientists, and they tell me they’re surprised I had such an unhappy time in high school, since they themselves had a great time, I always ask them which high school they went to. In a large fraction of cases, the answer turns out to be TJ—and when it isn’t, it’s often the Bronx High School of Science or another similar place. As should surprise no one, the students had vastly more detailed questions about my talk than did the National Science Board for example, they wanted to know whether I thought progress in group theory would lead to new quantum algorithms .

Without doubt, the most surreal aspect of this trip was the contrast between what was going on in my “real” and “virtual” lives. Again and again, I’d be shaking hands with the Undersecretary of Defense, Director of the National Institute of Prestigiousness, etc. etc., and warmly accepting these fine people’s congratulations. Then I’d sneak away for a minute to moderate my blog comments on my iPhone, where I’d invariably find a fresh round of insults about my “deeply ignorant lesser brain” from entanglement denier Joy Christian.

Perhaps the funniest contrast had to do with a MathOverflow question that I posted just before I left for DC, and which was quickly answered, just as I had hoped. During the limo ride back from the dinner, I got the following polite inquiry from a blog commenter calling himself “Mike”:

Hey Scott, I’m wondering how you got the courage to post that question on [MathOverflow]. In truth it wasn’t that hard of a question and if you have trouble solving it then…well, no offense, but you see what I mean. Reputation matters.

As I contemplated Mike’s question, a profound sense of peace came over me. Probably for the first time in my life, I realized just how lucky I really am. I’m lucky that I feel free to ask naïve, simpleminded questions, toss out speculations, and most importantly, admit when I don’t know something or made a mistake, without worrying too much about whether those actions will make me look foolish before the “Mikes” of the world. If I want to work on a problem myself, I can do that; if I prefer giving the problem out to others, I can do that as well. Let Mike, with his greater wisdom, sit in judgment of me for my failure to see all the answers that no doubt are obvious to him. I don’t mind. In science, like in everything else, I’ll continue being an unabashed doofus—partly because it seems to work OK, but mostly just because it’s the only way I know.

Thanks so much to all of you for your support.

Gil Kalai: The Quantum Fault-Tolerance Debate Updates

Gil Kalai — Wed, 09 May 2012 13:50:52 +0000

In a couple of days, we will resume the debate between Aram Harrow and me regarding the possibility of universal quantum computers and quantum fault tolerance. The debate takes place over GLL Godel’s Lost Letter and P=NP blog.

The Debate

Where were we?

My initial post “Perpetual Motion of The 21st Century?” presented my conjectures regarding how noisy quantum computers and noisy quantum evolutions really behave.

Aram’s first post was entitled “Flying Machines of the 21st Century?” It mainly dealt with the question “How is it possible that quantum fault-tolerance is impossible or really really hard while classical fault tolerance is possible and quite easy . Aram claimed that my conjectures, if true, exclude also classical computers.

Aram’s second post entitled “Nature does not conspire” dealt mainly with correlated errors. Aram claimed that it is unreasonable to assume strong correlation of errors as my conjectures imply and that the conjectured relation between the signal and noise is in tension with linearity of quantum mechanics.

Aram’s third post “The Quantum super-PAC” raised two interesting thought-experiments and discussed also intermediate models.

Each post ended with a small rejoinder, and included a short description of the ealier discussion. The discussion was quite extensive and very interesting.

What’s next

Aram and Steve Flammia wrote an interesting manuscript with appealing counterexamples to my Conjecture C. Our next planned post will discuss this matter.

Next, I will conclude with a post discussing Aram’s two main points from his first and second posts and some related issues which I find important.

These posts are mostly written but since Aram was busy with pressing deadlines we waited several weeks before posting them. I also enjoyed the break, as the extensive discussion period was quite tiring.

A very short introduction to my position/approach

1 The crux of matter is noise

Of course, this is the main issue raised by skeptical physicists from the early days of the quantum computers idea.

Here the question is: What is the correct error-model for quantum computers? Another way to put it is: What are the feasible approximations for pure quantum evolutions and quantum states.

This issue is related to other aspects of quantum physics. When we discuss quantum computers we would like to control a quantum evolution up to a small error, but very similar issues arise if we want to describe a quantum evolution. Any such description requires neglecting some ingredients and this is where we need to understand the nature of approximations in quantum mechanics. Indeed, the art of expressing the effect of the neglected parts is an important ingredient of various computations and theories in physics.

2 My conjectures are suppose to be strictly within Quantum Mechanics

Two disclaimers are in place: First, this point is challenged. Some people claim that it is simply impossible in principle to accept quantum mechanics and question the possibility of quantum computers. Others raise some specific points about tension between my conjectures and QM, especially QM linearity. Second, my conjectures may well be in conflict with some specific claims, insights, and computation methods in the quantum physics literature. In fact, this is what make them interesting.

3 Developing a theory for modeling “non fault-tolerance quantum evolutions” is a valuable goal, independently of the feasibility of quantum computers.

Here is a lovely and funny picture by Daniel Gottesman,

Daniel Gottesman’s picture

Non fault-tolerance quantum evolutions refer to understanding of Daniel’s “desert of decoherence.” This is important whether fortified island of quantum fault tolerance can or cannot be created or whether or not they are witnessed already in nature .

A taste of the discussion: Aram’s thought experiments.

I found the discussion really good. Of course, it is especially valuable for me, since it gives me an opportunity to test my conjectures against various technical and conceptual critique and it also gives me an opportunity to see what other people’s views are. I am very thankful to Aram and the other people involved for this opportunity. But I think that the discussion is also of value both to experts on quantum fault tolerance and to people interested in quantum information. Of course, I will be the first to remind people yet again that the overall stance of the quantum information community is that universal quantum computers based on quantum error correction can be built.

Let me give you a taste of two of the issues raised in the discussion that I do not plan to discuss further in my last post. Aram’s third post included two interesting thought-experiments. Aram’s first thought experiment offered to build a certain photonic quantum computer in a quiet intergalactic place. One of the difficulty with this suggestion is that as long as we do not understand what can go wrong with such an architecture on earth, moving it to outer space gives little help. This is also related to something Scott Aaronson wrote. Congratulations again, Scott, on the Waterman award! Scott said that we all agree that building a quantum computer is really really hard. Not so fast, Scott. Why is it really really hard? Without understand this hardness from first principles it will be difficult to build quantum computers or to tell if it is just “really really hard” or impossible.

Aram’s second thought experiment was thoroughly discussed in the comment thread. It relates to the fundamental question if we can have “protected” noiseless quantum process hidden in a noisy quantum process.” My conjecture 2 asserts that this is impossible. Aram’s idea was to somehow look at a huge environment around our noisy quantum process. This leads to a sort of “who will guard the guards” situation. At the end, I think we are in agreement that this will not work but some participants in the discussion had some thoughts on how to salvage it.

A manuscript by John Preskill, the Caltech visit and pairwise positive correlations

One pleasant surprise was to learn that, motivated in part by our discussions in Caltech a year earlier, John Preskill wrote an interesting manuscript which pushes further the boundaries of the threshold theorem. Caltech was a fun visit. I gave a lecture which went nicely and then we had a two hours discussion with the QI group on my stuff. At the end, John challenged my claim that pairwise positive correlations can lead to error synchronization. I got a bit confused and for some time I thought that John was right. So it gave me an opportunity to make some jokes about invoking my malpractice insurance, etc. On the way to my apartment which I shared with Keith Lee , I realized that my claim was ok. Actually, the distinction between 2-locality in terms of sums of 2-local Hamiltonians and between a description via 2-local constraints and the classical counterparts are quite important. It is related to fascinating issues in error correcting codes classic and quantum and in Hamiltonian complexity theory. A sort of related claim was raised by Aram on his second post.

An open problem by Tselil Schramm and me from the Caltech visit is if the name “Euro Pane Bakery” is meant as a pun which will immediately make it a double pun .

Miscellaneous

How the debate came about?

Last June, Aram wrote to me regarding my last arxived paper, raised a few interesting questions, and proposed discussing them either privately or publically. Actually one of Aram’s remarks required a more careful formulation of my Conjecture 1 . At that time, I preferred a private discussion so I wrote a detailed reply, and almost forgot about it. Later in November, Aram commented about my paper on GLL, and following it we decided to go ahead with a public discussion/debate on this matter that Dick and Ken kindly agreed to host on GLL.

Related posts new and old

During the debate there were several intermediate posts on GLL related directly or indirectly to the debate. My own blog involvement started in 2006 over the Quantum Pontiff – Dave Bacon’s blog. The Quantum Pontiff had at the time several nice discussions on related matters and my two-qubit and error-synchronization conjectures came up in one of these discussions. The first response to my conjecture came from John Sidles, see the second picture from the top of the post. At that time, I had the feeling that my skeptical view annoyed Dave so to cheer him up and to explain my philosophy I linked to my name the picture at the top of this post. But Dave did not notice it untill now. Beside that, on Shtetl-optimized, Scott Aaronson is quite interested in quantum computer skepticism and he discussed or referred to this issue in a large number of posts over the years. In some cases the discussion was quite interesting.

Touching base with Robert Alicki

One thing that I have learned as a byproduct from this debate is that Robert Alicki spend the year in Israel and it was great to meet Robert again.

A last piece of trivia

I never met Aram, Ken or Dick, and I am looking forward to.

Terence Tao: Lewis Carroll logic puzzles

Terence Tao — Wed, 09 May 2012 07:57:36 +0000

I had another long plane flight recently, so I decided to try making another game, to explore exactly what types of mathematical reasoning might be amenable to gamification. I decided to start with one of the simplest types of logical argument and one of the few that avoids the disjunction problem mentioned in the previous post , namely the Aristotelian logic of syllogistic reasoning, most famously exemplified by the classic syllogism:

Major premise: All men are mortal.

Minor premise: Socrates is a man.

Conclusion: Socrates is a mortal.

There is a classic collection of logic puzzles of Lewis Carroll from his book on symbolic logic , in which he presents a set of premises and asks to derive a conclusion using all of the premises. Here are four examples of such sets:

Babies are illogical;

Nobody is despised who can manage a crocodile;

Illogical persons are despised.

My saucepans are the only things that I have that are made of tin;

I find all your presents very useful;

None of my saucepans are of the slightest use.

No potatoes of mine, that are new, have been boiled;

All of my potatoes in this dish are fit to eat;

No unboiled potatoes of mine are fit to eat.

No ducks waltz;

No officers ever decline to waltz;

All my poultry are ducks.

After a certain amount of effort, I was able to gamify the solution process to these sort of puzzles in a Scratch game, although I am not fully satisfied with the results in part due to the inherent technical limitations of the Scratch software, but also because I have not yet found a smooth user interface for this process . In order to not have to build a natural language parser, I modified Lewis Carroll’s sentences somewhat in order to be machine-readable. Here is a typical screenshot:

Unfortunately, the gameplay is somewhat clunkier than in the algebra game, basically because one needs three or four clicks and a keyboard press in order to make a move, whereas in the algebra game each click corresponded to one move. This is in part due to Scratch not having an easy way to have drag-and-drop or right-click commands, but even with a fully featured GUI, I am unsure how to make an interface that would make the process of performing a deduction easy; one may need a “smart” interface that is able to guess some possible intended moves from a minimal amount of input from the user, and then suggest these choices somewhat similarly to the “auto-complete” feature in a search box . This would require more effort than I could expend on a plane trip, though as well as the use of a more powerful language than Scratch .

There are of course several existing proof assistants one could try to use as a model Coq, Isabelle, etc. , but my impression is that the syntax for such assistants would only be easily mastered by someone who already is quite experienced with computer languages as well as proof writing, which would defeat the purpose of the games I have in mind. But perhaps it is possible to create a proof assistant for a very restricted logic such as one without disjunction that can be easily used by non-experts…

Filed under: math.LO Tagged: computer games, logic puzzle

Parteibuch Aggregator Feed

gowers: Horizon 2020 to promote open access

Kowalski: Almost a mathematical Haiku

The n-Category Café: Integrating Against the Euler Characteristic

Simple functions on the line

More general functions on the line

Simple functions in higher dimensions

More general functions in higher dimensions, and curvature

David Speyer: Bizarre persecution of Russian mathematician

The n-Category Café: Postulated colimits and absolute colimits

Izabella Laba: The rainbow tree

Teaching load, itemized: part 2

Terence Tao: Cayley graphs and the algebra of groups

New bounds for Szemeredi’s theorem, Ia: Progressions of length 4 in finite field geometries revisited

gowers: A look at a few Tripos questions VI

Scott: I was wrong about Joy Christian

David Speyer: Fun with y^2=x^p-x

The key identity

Why we’ve won

Scott Morrison: Mathematicians take a stand

David Speyer: Cheating on homework in a graduate course is staggeringly dumb

Scott Morrison: Onwards!

David Speyer: The recent difficulties with RSA

The Euclidean algorithm

How factorization methods work

The attack

Theory versus practice

A few thoughts on solutions

David Speyer: What would it take to make a noncorporate journal work from an editor’s perspective?

Scott Morrison: arXiv overlays at Scholastica

Scott Morrison: A forum on mathematical publishing

David Speyer: Some thoughts on teaching Michigan calculus

Self congratulation

Organization

The applied and conceptual focus of the class

The exams

Team homework

The mathlab

Some things I wish I’d known/would do differently

Ben Webster: “The Collapse of the Soviet Union and the Productivity of American Mathematicians”

The n-Category Café: What is homotopy type theory good for?

An example

Formulation in ordinary logic

Formulation in ∞-logic / homotopy type theory

Outlook

Scott: Waterman behind the scenes! Partying hard with the National Science Board

Gil Kalai: The Quantum Fault-Tolerance Debate Updates

The Debate

Where were we?

What’s next

A very short introduction to my position/approach

A taste of the discussion: Aram’s thought experiments.

A manuscript by John Preskill, the Caltech visit and pairwise positive correlations

Miscellaneous

How the debate came about?

Related posts new and old

Touching base with Robert Alicki

A last piece of trivia

Terence Tao: Lewis Carroll logic puzzles

Formulation in $∞$ -logic / homotopy type theory