The Academic Reader and RSS readers

In comments, Yue Li writes of the Academic Reader:

This seems very similar with a production of Google, the google reader, a quantum specific google reader:)

In the existing site, the main difference between the Academic Reader and RSS readers like the Google Reader is that we have a variety of ways of searching and browsing older papers. This means the Academic Reader allows you to both (1) keep abreast of your current reading, and (2) look back into the past, discovering older papers and so on. RSS readers typically focus on just the first of these problems.

This functionality will be greatly extended in coming months!

Introduction to Yang-Mills theories

Yang-Mills theories are a class of classical field theory generalizing Maxwell’s equations. When quantized, Yang-Mills theories form the basis for all successful modern quantum field theories, including the standard model of particle physics, and grand unified theories (GUTs) that attempt to go beyond the standard model.

This post contains working notes (32 pages, pdf only) that I wrote in an attempt to come to a satisfactory personal understanding of Yang-Mills theory. They are part of a larger project of understanding the standard models of particle physics and of cosmology – some related earlier notes are here.

Caveat: The current notes take a geometric approach to Yang-Mills theory, and include quite a bit of background on differential geometry. After completing a first draft, I realized that if I was to write either a pedagogical introduction or a review of Yang-Mills theory, this geometric approach is not the approach I’d prefer to take. Rather, I’d start with a bare statement of the Yang-Mills equations, considered as a generalization of Maxwell’s equations, and then work through a series of examples, only gradually mixing in the geometric approach. This would have the advantage of bringing readers up to speed much more quickly, without needing to absorb reams of differential geometry upfront.

Because of this, I haven’t polished these notes – they remain primarily my personal working notes, and there are various inaccuracies and shortcomings in the notes. I’m content to ignore these – why spend time polishing when you know a better approach is possible – but would appreciate advisement if you spot any serious misconceptions.

Despite these caveats, I believe the notes may be useful to some readers. In particular, if you’d like to understand the approach to Yang-Mills theory from differential geometry, these notes may serve as a useful first step, to be supplemented by additional reading such as the book by Baez and Muniain (“Knots, Gauge Fields and Gravity”, World Scientific 1994) on which the notes are primarily based.

Enjoy!

Update: If you’re reading the notes in detail, then you might want to take a look at the comments, esepcially those by David Speyer and Aaron Bergman, who provide some important corrections and extensions.

The Academic Reader V0.02

We’ve introduced an updated version. New features include 31 extra feeds (all of the mathematics feeds at www.arxiv.org), the ability to browse backwards in time through feeds, and an announcement blog. Many more things are still to come! The announcement blog is at:

http://academicreader.wordpress.com

We have had a few problems with feed continuity – some articles from the arxiv have failed to show up, or have showed up late. We’re working on this, and things seem to be smoothing out.

Thanks to everyone who signed up, especially those who provided feedback – we have nearly 250 registered users!

Published
Categorized as General

Introducing the Academic Reader

The Academic Reader is a new web site that makes it easier to keep track of your scientific reading. Rather than going to multiple websites every day to keep up, we pull all the sources together in a single location, so you can keep track easily. Sources include the preprint arXiv, the Physical Review, and Nature, and many new sources will be added in the months to come, including sources outside physics.

Visit version 0.01 of the site at http://www.academicreader.org.

Update: Last week the preprint ArXiv overhauled its paper numbering. A side effect, which became visible just as we announced (!), is that their back-end interface for extracting paper data is currently completely down. They promise it’ll be back soon. In the meantime, the ArXiv feeds on the Academic Reader will be bit dated. Our apologies for that.

Update 2: The ArXiv appears to be back to normal.

Update 3: We had some server downtime for about 15 mins (around 0700 UTC) due to a hastily scheduled memory upgrade needed to speed things up (thanks everyone for registering!) Sorry if you got booted off the server – we’ll try to make this more transparent in future.

Published
Categorized as General

What is the Universe made of? Part I

This post is, more than usual, a work in progress. It is the first draft of the first installment of a longer article on the subject “What is the Universe made of”. I intend to revise this draft and finish the longer article over the next few weeks, posting it to my blog as I make progress.

This first installment gives a bird’s-eye view of the subject, describing in very broad terms how ideas from particle physics, from cosmology, and from quantum gravity have contributed to our current understanding of what the Universe is made of. It’s really just a warm-up – subsequent installments will be meatier, describing in more detail each of these ideas, how they fit together, and some of the big questions that remain. The next installment will describe the standard model of particle physics in some detail.

The article is intended for a general audience, albeit one with a good grounding in basic science. Physicists hoping for a technical treatment will be disappointed. I certainly can’t claim any great expertise in the subject; while I’m a theoretical physicist, my work has been mostly on quantum information, not particle physics, cosmology, or quantum gravity, and I’m far from being expert on the topics discussed here. If you are an expert, and spot any errors, I’d appreciate hearing about them.

Here’s a link to the article. (PDF only, I’m afraid).

Fields Medal

Update: The four medallists are Perelman (declined), Tao, Russian Andrei Okounkov, and Wendelin Werner. There is a nice article about Tao’s work at the UCLA website. The Nevanlinna Prize went to John Kleinberg.

Tao’s Medal will cause a lot of of excitement in Australia, as he’s the first Autralian ever awarded the Fields Medal.

I’m particularly pleased, as I greatly admire some work Tao did with Allen Knutson on a problem of some interest in quantum information, known as Horn’s problem: given that A+B=C, where A, B and C are Hermitian, what can be said about the relationship between the eigenvalues of A, B and C? There is now a complete (and deep) solution to this problem, and Tao and Knutson played a central role in obtaining it.

This problem at first might not seem all that related to quantum mechanics. It turns out that there are a lot of connections between the techniques used, a fact you can see in some beautiful work by Hayden and Daftuar and by Klyachko, who made important independent contributions to the solution of Horn’s problem.

Of course, this is just one of many things Tao is known for – he’s probably better known for his proof (with Ben Green) that there exist arbitrarily long sequences of primes in arithmetic progression. His web page lists an amazing array of papers, books, expository notes, and other activities (he’s a vegemite fan); it’s a lot of fun to read through!

Published
Categorized as General

Lives of quiet desperation

Noted for posterity: a site to download quantum computing term papers.

(Addendum: After posting, I had some qualms about the wisdom of posting this link. However, upon a nanosecond’s reflection, I would guess that anyone desperate enought to be looking for quantum computing term papers is unlikely to be reading my blog. )

Published
Categorized as General

QIP 2007

For those with an interest in quantum information, the 10th Workshop on Quantum Information Processing (QIP) will be held in Brisbane January 30 – February 3 next year. This has been a terrific workshop in the past (I certainly try to attend every year), and we’re optimistic this one will be a great workshop, too.

All the details are at the workshop website.

Published
Categorized as General

Limits to collective decision making: Arrow’s theorem

What’s the best way for a group of people to make collective decisions? Democracy may be, as Churchill said, the worst system that’s better than anything else, but in practice there’s a lot of variation possible in democractic voting systems. How should we set up voting systems that result in effective collective decisions?

Designing a good voting system seems like a simple task, but it’s surprisingly complicated. A famous result known as Arrow’s theorem, proved by the economist Kenneth Arrow in 1950, vividly demonstrates just how difficult it is. Arrow picked out three properties that (arguably) you would like any good voting system to have – and then mathematically proved that no voting system with all three properties can possibly exist! What is especially remarkable about Arrow’s achievement is that there is no obvious a priori reason to suppose that these three requirements are incompatible. Arrow was a joint recipient of the 1972 Nobel Memorial Prize for economics, in part because of this work.

These notes explain what Arrow’s theorem says, why it’s true (i.e., I give a proof), and discuss briefly what it means for collective cognition. I’ve tried to keep the notes easy to read, favouring a relaxed and discursive discussion over the terse presentation favoured in most mathematical works. I have also tried to assume minimal mathematical background, no more than some facility with basic mathematical notation and mathematical argument. The main drawback of this approach is that the notes have become rather lengthy, clocking in at nearly [tex]3000[/tex] words. Hopefully, however, they’ll be a rewarding read.

My notes are based on a very nice paper by John Geanakoplos (Cowles Foundation discussion paper No.1123RRRR, available at http://cowles.econ.yale.edu, and reprinted in Economic Theory (2005), 26: 211-215), which gives three proofs of Arrow’s theorem. The proof I give is Geanakoplos’ first (and simplest) proof. Note that there are other (related) results in the literature which go by the name Arrow’s theorem. Understanding the version presented here should enable you to understand the variants with a minimum of fuss. Arrow’s original paper appeared as “A Difficulty in the Concept of Social Welfare” in The Journal of Political Economy, Volume 58, page 328 (1950).

Voting systems

To explain what Arrow’s theorem says, we need to define more precisely what we mean by a voting system. We imagine a population of [tex]n[/tex] “voters”, to whom we assign convenient labels , like [tex]1, \ldots, n[/tex]. This population might be, for example, all the mentally competent people over the age of [tex]18[/tex] in some country (e.g., Australia).

These voters are going to vote amongst [tex]m[/tex] alternative options, which we’ll label with capital letters, [tex]A, B, C, \ldots, Z[/tex], to keep distinct from the voters. These voting options might be the political parties running for control of the Federal Government, for example.

What each voter does is produce an ordered ranking of the options, with ties allowed. For example, voter number [tex]3[/tex] might rank [tex]B[/tex] as number [tex]1[/tex], [tex]A[/tex] and [tex]C[/tex] as a tie for number [tex]2[/tex], [tex]D[/tex] as number [tex]3[/tex], and so on.

(You might wonder whether [tex]D[/tex] shouldn’t really be ranked number [tex]4[/tex], in view of the tie between [tex]B[/tex] and [tex]C[/tex] for the ranking of [tex]2[/tex]. Below we’ll make an assumption about the voting system that means that only the relative ranking matters, not the exact value of the number assigned, and so we’re justified in ignoring this issue.)

A helpful shorthand is to write [tex]S >_v T[/tex] to indicate that voter [tex]v[/tex] ranked [tex]S[/tex] strictly ahead of [tex]T[/tex]. For example, maybe voter [tex]v[/tex] ranked [tex]S[/tex] as [tex]2[/tex] and [tex]T[/tex] as [tex]4[/tex]. It’s worth keeping in mind that this notation for ordering is the reverse of the conventional numerical order – politicians usually campaign to be “number [tex]1[/tex]” rather than “number [tex]10[/tex]”! Similarly, we’ll write [tex]S \geq_v T[/tex] to indicate that voter [tex]v[/tex] ranked [tex]S[/tex] at least as highly as [tex]T[/tex]; this allows that maybe [tex]S[/tex] and [tex]T[/tex] had the same rank. By the way, we’ve been using [tex]S[/tex] and [tex]T[/tex] here simply to indicate generic voting options; we’ll do this throughout, occasionally using [tex]U[/tex] as well.

As an example, imagine there are [tex]5[/tex] voters choosing among [tex]3[/tex] alternatives, [tex]A, B, C[/tex]. The overall voting profile might look something like this:

  • Voter [tex]1[/tex]: [tex]A \rightarrow 1[/tex]; [tex]B \rightarrow 1[/tex]; [tex]C \rightarrow 2[/tex].
  • Voter [tex]2[/tex]: [tex]A \rightarrow 3[/tex]; [tex]B \rightarrow 1[/tex]; [tex]C \rightarrow 2[/tex].
  • Voter [tex]3[/tex]: [tex]A \rightarrow 2[/tex]; [tex]B \rightarrow 1[/tex]; [tex]C \rightarrow 1[/tex].
  • Voter [tex]4[/tex]: [tex]A \rightarrow 1[/tex]; [tex]B \rightarrow 1[/tex]; [tex]C \rightarrow 1[/tex].
  • Voter [tex]5[/tex]: [tex]A \rightarrow 3[/tex]; [tex]B \rightarrow 2[/tex]; [tex]C \rightarrow 1[/tex].

A voting system is a function which takes the profile as input, and produces a single social ranking of the options as its output. For example, we might add up the numerical value of the votes associated to each voting option, and then order the options accordingly. So, for example, option [tex]A[/tex] above has a total vote [tex]1+3+2+1+3=10[/tex], option [tex]B[/tex] a total [tex]1+1+1+1+2=6[/tex] and option [tex]C[/tex] a total [tex]2+2+1+1+1=7[/tex]. As a result, in this voting system the social ranking has [tex]A[/tex] as [tex]3[/tex], [tex]B[/tex] as [tex]1[/tex], and [tex]C[/tex] as [tex]2[/tex].

Once a voting system has been fixed, we write [tex]S > T[/tex] to indicate that [tex]S[/tex] has a higher social rank than [tex]T[/tex]. Similarly, we write [tex]S \geq T[/tex] to indicate that [tex]S[/tex]’s social ranking is at least as high as [tex]T[/tex]’s.

What makes a good voting system?

What properties should a good voting system have?

Obviously, this is a potentially controversial question! Arrow’s theorem is based on several reasonable properties that, arguably, we should expect to be satisfied in any good voting system.

The first property is that the voting system should respect unaninmity, in the sense that if [tex]S >_v T[/tex] for all voters, then we should have [tex]S > T[/tex]. Restating this verbally instead of symbolically, if every voter prefers [tex]S[/tex] to [tex]T[/tex], then the social ranking should place [tex]S[/tex] ahead of [tex]T[/tex]. This is pretty obviously a highly desirable property for any voting system to have – imagine if the electoral commission announced that candidate [tex]A[/tex] had won, despite the fact that every single voter ranked [tex]B[/tex] ahead of [tex]A[/tex]!

The second property is that the voting system should respect the independence of irrelevant alternatives, meaning that the relative social ranking of [tex]S[/tex] and [tex]T[/tex] (higher, lower, or the same) depends only on the relative ranking of [tex]S[/tex] and [tex]T[/tex] by individual voters, and isn’t influenced by the position of other options (e.g., [tex]U[/tex]).

It’s rather less obvious that any good voting system will respect the independence of irrelevant alternatives. For example, the simple voting system I described above (where we summed the votes) turns out not to have this property, yet it’s not so obviously a bad voting system.

However, for the purposes of this discussion we’re going to assume that this property of respecting the independece of irrelevant alternatives is regarded as highly desirable. Can we design a voting system which respects both unanimity and the independence of irrelevant alternatives?

It turns out that if there are just two voting options, [tex]A[/tex] and [tex]B[/tex], then it’s possible to design a voting system with this property. We could, for example, just sum up the the respective votes of the two voting options, and declare the winner to be whichever option has the lower total.

What happens if there are three voting options, [tex]A, B[/tex] and [tex]C[/tex]? What Arrow’s theorem shows in this case is that in any voting system which respects unanimity and the independence of irrelevant alternatives there must automatically be a voter, [tex]d[/tex], who can act as a dictator for the voting system, in the sense that if [tex]S >_d T[/tex], then [tex]S > T[/tex], no matter how the other voters rank their options!

Stated another way, what Arrow’s theorem shows is that the requirements of respecting unanimity and the independence of irrelevant alternatives are incompatible with a third desirable requirement, namely that the voting system not be a dictatorship.

In full generality, what Arrow’s theorem shows is as follows:

Arrow’s theorem: Suppose we have a voting system to rank [tex]3[/tex] or more voting options. Suppose that system respects unanimity and the independence of independent alternatives. Then there must be a dictator for the voting system.

This theorem ought to shock you. How can the assumptions of unanimity and independence of irrelevant alternatives possibly imply the existence of a dictator?

I’ll now give a short proof of Arrow’s theorem, to give you some feeling for why the theorem is true. However, much of interest can be said about Arrow’s theorem even if you don’t understand the proof, so if you’re so inclined you should feel free to skim or skip the following proof. Of course, those who want to understand Arrow’s theorem deeply should spend some time trying to prove it themselves, before reading the proof in detail.

Proof of Arrow’s theorem: The first step of the proof is to argue that if every voter ranks [tex]S[/tex] either strictly first or strictly last, then [tex]S[/tex]’s social ranking must be either strictly first or strictly last. To see this, we use a proof by contradiction, supposing that in fact [tex]S[/tex]’s social ranking is neither strictly first nor strictly last. That is, we suppose that there exist [tex]T[/tex] and [tex]U[/tex] such that [tex]T \geq S \geq U[/tex]. Suppose we rearrange each voter’s rankings so that [tex]U >_v T[/tex], but without changing the relative ranking of [tex]S[/tex] and [tex]T[/tex], or of [tex]S[/tex] and [tex]U[/tex], so the rearrangement doesn’t affect the fact that [tex]T \geq S[/tex] and [tex]S \geq U[/tex]. (Understanding why such a rearrangement can always be done requires a little thought, and maybe some working out on a separate sheet of paper, which you should do.) Unanimity then requires that [tex]U > T[/tex], which is inconsistent with the fact that [tex]T \geq S \geq U[/tex]. This is the desired contradiction.

Suppose now that we start out with a profile in which [tex]S[/tex] is ranked strictly first by every voter, and thus by unanimity must be ranked strictly first in the social ranking. Suppose we move through the voting population, and for each voter in turn change their ranking for [tex]S[/tex] from strictly first to strictly last. When this has been done for all the voters, unanimity implies that [tex]S[/tex] must be ranked strictly last, and so at some point we see that there must be a voter (who will turn out to be the dictator, [tex]d[/tex]), whose vote change causes [tex]S[/tex] to move from first to last in the social ranking.

Consider the voting profile immediately before [tex]d[/tex] changes their vote. We will say that any profile which has the same rankings for [tex]S[/tex] as this profile is an [tex]S[/tex]-profile. Similarly, an [tex]S'[/tex]-profile is one which has the same rankings for [tex]S[/tex] as the profile just after [tex]d[/tex] changes their vote. It follows from the independence of irrelevant alternatives that the overall ranking of [tex]S[/tex] must be first in any [tex]S[/tex]-profile, and last in any [tex]S'[/tex]-profile.

Suppose now that [tex]T[/tex] and [tex]U[/tex] are voting options that are not equal to [tex]S[/tex]. Suppose [tex]d[/tex] ranks [tex]T[/tex] higher than [tex]U[/tex], i.e., [tex]T >_d U[/tex]. We will show that we must have [tex]T > U[/tex], no matter how the other voters rank [tex]T[/tex] and [tex]U[/tex]. That is, [tex]d[/tex]’s vote dictates that [tex]T[/tex] be ranked above [tex]U[/tex] in the social ranking. To see this, first we rearrange the profile so that it becomes an [tex]S[/tex]-profile, without changing the relative ordering of [tex]T[/tex] and [tex]U[/tex] anywhere, and so not affecting whether [tex]T > U[/tex] or not. We can do this simply by changing each voter’s ranking for [tex]S[/tex] in an appropriate way, placing it either at the top or the bottom of their ranking. Second, we change [tex]d[/tex]’s rankings so that [tex]T >_d S >_d U[/tex]. This can be done without changing the relative ranking of [tex]T[/tex] and [tex]U[/tex], and so does not affect whether [tex]T > U[/tex]. We call the resulting voting profile after these two rearrangements the final profile. Observe that in the final profile we have [tex]S > U[/tex], since if [tex]d[/tex] changes [tex]S[/tex] to be ranked strictly first then we have an [tex]S[/tex]-profile. Similarly, in the final profile we have [tex]T > S[/tex], since if [tex]d[/tex] changes [tex]S[/tex] to be strictly last, then we have an [tex]S'[/tex]-profile. As a result, we have [tex]T > S > U[/tex] in the final profile, and thus [tex]T > U[/tex]. But we constructed the final profile so that [tex]T > U[/tex] holds only if [tex]T > U[/tex] also in the actual voting profile, and so we must have had [tex]T > U[/tex] in the actual voting profile, as we desired to show.

The final step of the proof is to argue that [tex]d[/tex] can also dictate the order of [tex]S[/tex] and [tex]T[/tex], for an arbitrary [tex]T \neq S[/tex]. To see this, pick an element [tex]U[/tex] which is neither [tex]S[/tex] nor [tex]T[/tex], and consider an [tex]S[/tex]-profile in which [tex]U[/tex] is placed strictly last everywhere that [tex]S[/tex] is first, and vice versa. The results of the first and second paragraph of this proof imply that [tex]d[/tex] can change the rank of [tex]U[/tex] from last to first simply by changing their vote. We now apply the same argument as in the paragraph before this, but with [tex]U[/tex] taking the place of [tex]S[/tex], to argue that [tex]d[/tex] can dictate the relative ordering of [tex]S[/tex] and [tex]T[/tex]. QED

Arrow’s theorem is a striking result in the theory of collective decision making. It shows the great advantages that can come by formalizing ideas in a simple mathematical model – the fact that the model can lead to striking unforseen conclusions that entirely change our perception of the phenomenon. More prosaically, by thinking closely about our values and our desired social outcomes, we can try to formalize models of those properties, and then study which models of collective decision making best respect those properties (if, indeed, any such models exists).

What of the implications of Arrow’s theorem for voting? It is, of course, true that the restrictions in Arrow’s theorem can be relaxed, and there is a large literature studying other models of voting and the extent to which they can be made fair. I’m not an expert on this literature, and so won’t comment other than to point out that economists have, of course, not been silent on the matter in the 50 plus years since Arrow’s paper!

My own interest in the subject is due to a more general hobby interest in the problem of collective cognition. In particular, I’m interested in the question of how we can design institutions which result in good collective decision making. It seems that the subject of institutional design is still in its infancy, and I find it remarkable how small a fraction of “institution space” humans have explored. One of the most interesting things about the web, in my opinion, is that it has greatly cut the cost of developing new institutions, and as a result we’re seeing new institutional models, and new types of collective cognition, develop at an incredible rate.

Topological quantum computing

Steve Flammia from the University of New Mexico has been visiting, and has been giving us a great series of tutorial talks on topological quantum computing. Steve has prepared a webpage for his tutorials (to be expanded as the tutorials go on), which you may wish to look at if you’re interested in learning the subject.

Published
Categorized as General