Breaking News!

You may remember that, in July, Italy won the football Word Cup. No? Best defense ever? Materazzi? Headbutt? 意大利万岁? Anybody?

Anyways, I was in Rome that night, I borrowed a friend’s camera, and I took some pictures on the street. I gave the camera back, and he told me he would email me the pictures “in a few days.” I got the pictures today, which is what he meant. I suppose anybody who has sent me a paper to referee, only to be assured I would send the review “in a few days,” is now nodding knowingly.

I did not know how the settings of the camera worked, it was night, we were never able to stop the car (except in traffic), so the pictures are dark and shaky, then the battery run out just when we got to the center, plus I ran out of gas, I had a flat tire, I didn’t have enough money for cab fare, my tux didn’t come back from the cleaners, an old friend came in from out of town, someone stole my car, there was an earthquake, a terrible flood, LOCUSTS!

Having dispensed with the excuses, in the interest of timely dissemination here are some of the pictures.

We start driving from Monte Sacro, a neighborhood in the North-East of the city, about 5 miles away from the center. It’s less than two hours since the game is over, and a newspaper kiosk is selling day-after newspapers with chronicles of the game.

In this much time they wrote the articles, printed the papers, and got them all over the city, which is, of course, completely gridlocked. This shows that when something is really important, Italians can be efficient. (No, I don’t know why there is advertising for Newsweek in a Monte Sacro newspaper kiosk.)

After more than an hour, we get to the Muro Torto, the wide road (with tunnels) that runs along historical walls and goes toward Piazza del Popolo.

Almost all the traffic is, of course, in the direction toward the center, which is where we are trying to go.


This gentleman has “W la fica” writeen on his chest. (Sorry, no translation.)

Since the traffic is not moving, one guy has the time to get out of his car and climb on top of a truck.


Then there is the group of guys running around in tighty whiteys.

This guy, instead, is jumping up and down on a Mercedes S-series. Note that he removed his shoes, so there is not risk of damaging the car.

The friend behind him, instead, his standing on the windshield. The Germans sure know how to make sturdy cars.


Then there is the Zidane coffin.

The lady in the red car is not showing a lot of enthusiasm. Seven people have fit into this small Citroen cabrio.

Note again the serious lady in the red car, and the fact that nobody is driving the Citroen. Carrying open alchoolic beverages in a car is actually legally in Italy. Driving this way, however, is allowed only on special occasions.

This is a Fiat 500, the car on which I learned how to drive. (No, I am not that old, it was a used car!)

This is the closest I got to taking a picture of Piazza del Popolo.

Catenaccio (heavy chain – the kind used to lock a gate) is the term used to define Italy’s defense.

Slaughtering the Cow to Get the Butter

Americans are fond of rankings and lists, and the end of the year is the time when you see top ten this and worst seven that wherever you look.

Media Matters has compiled a list of the 11 most outrageous comments of 2006 by right-wing commentators.

There is, for example, nationally syndacated obese radio host Rush Limbaugh pointing out that obesity is more prevalent in heavily Republican states and least prevalent in heavily Democratic ones, thus showing that obesity is caused by leftist liberal policies. But the best part is when he explains that, in dealing with the poor, the government is not teaching the poor how to slaughter the cow to get the butter, it just gives them the butter. Just listen to it.

Among the honorable mentions, nationally syndacated radio host Neal Boortz commented on the hairstyle of Representative Cynthia McKinney’s of Georgia as follows: “She looks like a ghetto slut.” Representative McKinney is black.

It is, however, the screen captions on Fox News which are the most hilarious.

Indonesia, Papua New Guinea, and Berkeley

This is were the notable earthquakes of the last few days have taken place, according to the US geological survey web site. And Berkeley had the distinction of three earthquakes in four days, as reported, among other sources, in the People’s Daily.

It must be especially annoying if you happen to be living on a tree.

An associated press article is so very reassuring:

But the minor earthquakes should not be interpreted as omens of a more destructive one to come, said Jessica Sigala, a geophysicist with the National Earthquake Information Center.

“It could mean there’s something coming, it could mean there’s nothing coming,” Sigala said.

Merry Christmas! Happy Holydays!

[Update 12/27: now that a real earthquake has hit Taiwan, this post sounds especially needless and petulant.]

Characters and Expansion

In which we look at the representation theory of Abelian groups and at the discrete Fourier transform, we completely understand the eigenvalues and eigenvectors of the Cayley graph of an Abelian group, and we apply this powerful theory to prove that the cycle is a connected graph.

When we talked about group representations, we saw how to map each element of a group into a matrix in such a way that group addition becomes matrix multiplication.

In general, if is a finite group, then an n-dimensional representation of is a map

such that is a group homomorphism between and the group of matrices . That is, we have that is an invertible matrix for every , , and .

(Scott will be delighted to know that the theory need not stop at finite matrices, and one may also look at representations mapping group elements into invertible linear transformations over an infinite-dimensional Hilbert space. To study finite groups, however, finite-dimensional representations are good enough.)

Note that need not be injective, and so, for every group, we can always define the 1-dimensional representation for every . Perhaps unsurprisingly, this is usually called the trivial representation. The precise statement of a theorem of Frobenius that we mentioned earlier is that every non-trivial representation of has dimension at least .

In an Abelian group, however, there are plenty of 1-dimensional representations, and, in fact, all the information about the group is “encoded” in the set of its 1-dimensional representations. We will call a 1-dimensional representation a character of the group. (This equivalence holds only for finite groups, otherwise we need an extra condition.) Hence a character of a group is a mapping

such that for every , , and . In a finite group , we always have the property that if we add an element to itself times we get 0; from this we can deduce that, if is a character, then must be a -th root of 1, that is, it must be a number of the form for some . In particular, for every .

(For general groups, we say that is a character if it is a 1-dimensional representation and it has the property that for every . While the latter property is a consequence of the former for finite groups and, more generally, for torsion groups, this is not the case for other groups. For example, is a 1-dimensional representation for but it is not a character.)

At first sight, it might look like a finite group might have an infinite number of characters (or at least that’s what I thought when I first saw the definition). There is however a simple argument that shows that a finite group cannot have more than characters.

Consider the set of all functions of the form ; we can think of it as a -dimensional vector space over . We have that the characters of are linearly independent, and so there cannot be more than of them. In fact, even more is true: the characters of are orthogonal to each other. For two functions , define their inner product as

Then, if and are two different characters, we have

The normalization in the definition of inner product is convenient because then we also have if is a character. (We will not prove these claims, but the proofs are very simple.)

We will now show that the cyclic group has indeed distinct characters . This means that this set of characters forms an orthonormal basis for the set of functions , and that each such function can be written as a linear combination

(*)
where the coefficients can be computed as the inner product

(The equation (*) is the Fourier expansion of , and the function is called the Fourier transform of .)

Here is how to define the characters : for each , define . It is immediate to verify that each such function is a character, and that, for we are, indeed, defining different functions. By the previously mentioned results, there is no other function.

Let’s see one more example: consider , that is, with the operation of bit-wise XOR. For each , define the function

We can again verify that all these functions are distinct, that each of them is a character, and so that they include all the characters of . The reader should be able to see the pattern and to reconstruct the characters of the group

thus having a complete understanding of the set of characters of any given finite Abelian group.

At long last, we can get to the subject of expansion.

Let be a finite Abelian group, and be a set of generators such that if then . Definite the Cayley graph where every element of is a vertex and where is an edge if . This is clearly an -regular undirected graph. Let be the set of characters of . Think of each character as an -dimensional vector. (The vector that has the value in the -th coordinate.) Then these vectors are orthogonal to each other. We claim that they are also eigenvectors for the adjacency matrix of .

Note a surprising fact here: the graph depends on the group and on the choice of generators . The eigenvectors of the adjacency matrix, however, depend on alone. (The eigenvalues, of course, will depend on .)

The proof of the claim is immediate. Let be the adjacency matrix of , then the -th entry of the vector is

We are done! The vector is indeed an eigenvector, of eigenvalue . Since we have eigenvectors, and they are linearly independent, we have found all eigenvalues, with multiplicities.

Let’s look at the cycle with vertices. It is the Cayley graph of with generators . We have eigenvalues, one for each , and we have

this may seem to contradict our earlier claim that all eigenvalues were going to be real. But two lines of trigonometry show that, in fact,

As expected in a 2-regular graph, the largest eigenvalue is . The second largest eigenvalue, however, is , which is . This means that the expansion of the cycle is at least and, in particular, the cycle is a connected graph!

(After we are done having a good laugh at the expense of algebraic graph theory, I should add that this calculation, plus some relatively easy facts, implies that a random walk on the cycle mixes in steps. Not only this is the right bound, but it is also something that does not have a completely straightforward alternative proof.)

We do a little better with the hypercube. The hypercube is the Cayley graph of the group with the generator set that contains all the vectors that have precisely one 1. Now we have one eigenvalue for each choice of , and the corresponding eigenvalue is
.

The largest eigenvalue, when all the are zero, is , as expected in an -regular graph. The second largest eigenvalue, however, is at most . This means that the expansion of the hypercube is at least 1. (As it happens, it is precisely 1, as shown by a dimension cut.)

Applied Philosophy

This weekend the New York Times magazine has an article by Princeton philosopher Peter Singer, on the subject of philantropy, poverty and ethics.

Singer is known for his position that all human lives have the same value, a position that sounds entirely uncontroversial until one starts to explore its ramifications. Consider for example the case of real estate investor Zell Kravinsky.

Kravinsky gave almost all of his \$45 million real estate fortune to health-related charities, retaining only his modest family home in Jenkintown, near Philadelphia, and enough to meet his family’s ordinary expenses. After learning that thousands of people with failing kidneys die each year while waiting for a transplant, he contacted a Philadelphia hospital and donated one of his kidneys to a complete stranger.

[...] Kravinsky has a mathematical mind — a talent that obviously helped him in deciding what investments would prove profitable — and he says that the chances of dying as a result of donating a kidney are about 1 in 4,000. For him this implies that to withhold a kidney from someone who would otherwise die means valuing one’s own life at 4,000 times that of a stranger, a ratio Kravinsky considers “obscene.”

I have to say that I have never found Utilitarianism convincing (and you don’t want to get an Utilitarian started with his mental experiments), even though I admit that there is hardly any known better premise on which to reason about Ethics.

The article has a lot of interesting information, including the following argument, which I had never seen before in these terms:

Thomas Pogge, a philosopher at Columbia University, has argued that at least some of our affluence comes at the expense of the poor. He bases this claim not simply on the usual critique of the barriers that Europe and the United States maintain against agricultural imports from developing countries but also on less familiar aspects of our trade with developing countries. For example, he points out that international corporations are willing to make deals to buy natural resources from any government, no matter how it has come to power. This provides a huge financial incentive for groups to try to overthrow the existing government. Successful rebels are rewarded by being able to sell off the nation’s oil, minerals or timber.

In their dealings with corrupt dictators in developing countries, Pogge asserts, international corporations are morally no better than someone who knowingly buys stolen goods [...]

Zeilberger on why P differs from NP

Scott Aaronson, Lance Fortnow and Bill Gasarch have discussed the reasons why they believe P differs from NP here, here and here.

Doron Zeilberger, motivated by Avi Wigderson’s talk in Madrid devotes his latest opinion to the subject. (Via Luca A.)

His dismissal of the creativity cannot be mechanized argument is based on his long-standing belief (which I share) that human creativity, especially human mathematical creativity can in fact be emulated by algorithms and that, in the long run, algorithms will end up being superior. I think this is a misunderstanding of the argument, whose point is rather that creating something good (by humans and by algorithms) seems to require much more effort than appreciating something good, and that there are levels of “genius” which we would be able to recognize if we saw them but that we are prepared to consider infeasible. In the end, this is the same as the a fool can ask more questions than a wise man can answer argument that Zeilberger himself proposes.

Then there is the issue of whether it is fair to say that “P $\neq$ NP is a statement that affirms its own intractability.” Indeed, the P versus NP question is a statement about asymptotics, while proving it is a problem of finite size.

I have two observations.

One is that the “natural proofs” results show that, assuming strong one-way functions exist (an assumption in the “ballpark” of P $\neq$ NP) there are boolean functions that are efficiently computable but have all the efficiently computable properties of random functions. This means that any circuit lower bound proof must work in a way that either would fail when applied to random functions (and there are reasons why it is difficult to come up with such proofs) or would rely on hard-to-compute properties of the function in question. So although the proof is a finite object, it does define an “algorithm” (the one that describes the properties of the function that are used in the proof) and such algorithm cannot be asymptotically efficient.

The other is that, however cleaner our theories are when formulated asymptotically, we should not lose sight of the fact that the ultimate goals of complexity theory are finite results. It will be a historic milestone when we prove that P $\neq$ NP by showing that SAT requires time at least $2^{-300} \cdot n^{(\log n) / 100 }$, but the real deal is to show that there is no circuit of size less than $2^{300}$ that solves SAT on all formulae having 10,000 clauses or fewer. The statements that we care about are indeed finite.

Russian humor

The January issue of the Notices of the AMS is out, and it contains an article by Anatoly Vershik on the Clay Millenium prize. You may remember a discussion we had on the wisdom of awards in general, in the context of the AMS idea of creating a fellows program and of the pros and cons of having a best paper award at STOC and FOCS.

Vershik returns to some of the standard points in this debate, and makes a few new ones. Although the tone of the article is completely serious, there are hints of deadpan humor (especially in the way he characterizes the opinions of others).

There is really no connection, but I was reminded of Closing the collapse gap, the hilarious presentation by Dmitry Orlov (found via the Peking Duck), in which he argues that when the U.S. economy will collapse, we will be much less prepared than the Russians were, and we will be in much deeper troubles. As stated in the comments at the Peking Duck, when Russians are deadly serious about something, they deal with it through dark humour.

Eigenvalues and expansion

Before trying to describe how one reasons about the eigenvalues of the adjacency matrix of a Cayley graph, I would like to describe the “easy direction” of the relationships between eigenvalues and expansion.

First, a one-minute summary of linear algebra. If is an matrix, then a (column) non-zero vector is an eigenvector of provided that, for some scalar , we have . If so, then is an eigenvalue of . A couple of immediate observations:

• The equation can be rewritten as , so if is an eigenvalue of then the columns of the matrix are not linearly independent, and so the determinant of is zero. But we can write as a degree- polynomial in the unknown , and a degree- polynomial cannot have more than roots.

  So, an matrix has at most eigenvalues.

• If is an eigenvalue of , then the set of vectors such that is a linear space. If and are different eigenvalues, then their respective spaces of eigenvectors are independent (they only intersect at 0).

If is a symmetric real-valued matrix, then a series of miracles (or obvious things, depending on whether you have studied this material or not) happen:

• All the roots of the polynomial are real; so, counting multiplicities, has real eigenvalues.
• If is an eigenvalue of , and it is a root of multiplicity of , then the space of vectors such that has dimension .
• If are two different eigenvalues, then their respective spaces of eigenvectors are orthogonal
  

From this fact, it is easy to conclude that starting from symmetric real matrix we can find a sequence of numbers

and a sequence of unit vectors such that the are orthogonal to each other and such that .

Now the claim is that these numbers and vectors completely describe . Indeed, suppose that we are given a vector and that we want to compute . First, we can write as a linear combination of the :

and since the are an orthonormal basis, we know what the coefficients are like: each is just the inner product of and .

Now, by linearity, we have

and, since the are eigenvectors,

So, once we express vectors in the basis defined by the , we see that multiplication by is just the effect of multiplying coordinate by the value .

But there is more. Recall that and so we can also write

and so, in particular, matrix is just

a sum of rank-1 matrices, with the coefficients of the sum being the eigenvalues.

Let now be the adjacency matrix of a -regular undirected graph (so is real-valued and symmetric), be its eigenvalues, and be a corresponding set of orthonormal eigenvectors.

It is not hard to see (no, really, it’s two lines, see the bottom of page 2 of these notes) that all eigenvalues are between and . Also, is always an eigenvalue, as shown by the eigenvector . This means that and we can take

and we have

Suppose now that all the other , are much smaller than in absolute value. Then, intuitively, the sum is going to be dominated by the first term, and behaves sort of like the matrix , that is, the matrix that has the value in each entry.

You may be skeptical that such an approximation makes sense, but see where this leads. If our graph is , and is a cut of the set of vertices into two subsets, let be the -dimensional vector that is 1 in coordinates corresponding to and 0 in the other coordinates, and define similarly. Then the number of edges crossing the cut is precisely

and if we replace by the matrix that has in each coordinate we get the approximation , which is the expected number of edges that would cross the cut if we had a random graph of degree . This is pretty much the right result: if are all much smaller than , and if and are at least a constant times , then the number of edges crossing the cut is indeed very close to . This result is known as the Expander Mixing Lemma, and the proof is just a matter of doing the “obvious” calculations. (Write and in the eigenvector basis, distribute the product, remember that the are orthogonal, use Cauchy-Schwarz …)

It is perhaps less intuitive that, provided that all other eigenvalues are at least a little bit smaller than , then a reasonably large number of edges crosses the cut. In particular, if and if , then at least edges cross the cut. That is, if all eigenvalues except the largest one are at most then the edge expansion of the graph is at least . (It takes about five lines to prove this, see the beginning of the proof of Thm 1 in these notes.)

To summarize: the adjacency matrix of an undirected graph is symmetric, and so all eigenvalues are real. If the graph is -regular, then is the largest eigenvalue, and all others are between and . If all the others are between and , then the graph has edge-expansion (or better).

Madonna and Letterman (1994)

As a break from expanders and groups, here is Madonna’s 1994 notorious appearence on Letterman’s show.

The incident has its own Wikipedia entry, one more piece of evidence that Wikipedia is superior to the Encyclopaedia Britannica.

Group representation

(As will become clear soon, I am totally out of my depth: Readers who find glaring mistakes, and even small ones, should note them in the comments.)

In the previous post on expanders we left off with the observation that if we want to construct an expanding Cayley graph, then we need to start from a group where all elements of the group can be obtained by a sum of terms chosen, with repetitions, from a set of generators; this means that a constant root of the ways of rearranging such sums must lead to different results. The group, then, has to be non-commutative in a very strong sense.

I will describe a way in which a group used to construct expanders is “very non-commutative.” This will not be a sufficient property for the expansion, but it is closely related and it will come up in the paper of Gowers that we will talk about later.

With this objective in mind, let’s see the notion of group representation. Let’s start from the simplest group, the cyclic group of elements with the operation of addition (or as mathematicians write). One can visualize this group as points equally spaced along a circle in the plane, with element forming an angle of with the axis. If we want to add an element that forms an angle to an element that forms an angle , that’s the same as putting the “two angles next to each other” and we get a point that forms an angle . More algebraically, we identify an element with the complex number and we realize group addition as multiplication of complex numbers. There is, however, another way of visualizing the cyclic group on a cycle. We can think of group element as the operation that takes a point on the cycle and moves it by an angle of . Addition of group elements now corresponds to “composition,” that is, corresponds to applying one rotation after the other.

In this view, element is now the function that maps complex number into complex number .

Suppose now that our group is a product of cyclic groups. This means that a group elements if a -tuple of the form , and that

It now makes sense to view a group element as a “high-dimensional rotation” operation that takes in input complex numbers and outputs the complex numbers

If we take this view, we have, again, the property that group addition becomes composition of functions. Note, also, that the function that we have associated to each group element is a very simple type of linear function: it is simply multiplication of times a diagonal matrix that has diagonal

Notice, also, that if is a function of the form , where is a matrix, and is a function of the form where is a matrix, then . That is, for linear functions, function composition is the same as matrix multiplication.

To summarize, we have started from the group , and we have found a way to associate a complex-valued diagonal matrix to each group element in such a way that group addition becomes matrix multiplication.

It is known that all finite Abelian groups can be written as , so this type of representation via diagonal matrices is possible for every finite Abelian group.

What about more general groups? If is an arbitrary finite group, it is possible to associate to each element a block-diagonal matrix in such a way that group addition becomes matrix multiplication.

(It is common to call a group operation “multiplication” when a group is not Abelian, but for consistency with the rest of the post I will keep calling it addition.)

(By the way, it is also possible to represent infinite groups by associating a linear operator to each group element, but we will only discuss finite groups here.)

If the group is Abelian, then the matrices are diagonal, that is, they are block-diagonal matrices with “block size one.” So one way of quantifying “how non-Abelian” is a group is to consider how small the blocks can be in such matrix representations. That’s the dimension of the representation.

Here is an example of a family of groups whose representations cannot be low-dimensional. Let be a prime (it could also be a prime power) and let us consider matrices whose entries are integers . Let us restrict ourselves to matrices whose determinant is 1 modulo , and consider the operation of matrix multiplication (where, also, all operations are mod ). This set of matrices forms a group, because the matrices are invertible (the determinant is non-zero) and the set contains the identity matrix and is closed under product. This group is called . The group contains the tiny subgroup of two elements ; in the representation of this shows up as a block of size 1. If we take the quotient of by then we get another group, which is called .

It is now a theorem of Frobenius that every representation of has dimension at least . This is really large compared to the size of : the group has elements, and so has elements. The dimension of the representation is thus approximately the cube root of the number of elements of the group.

Going back to representations of Abelian groups, we see that, in that case, not only each block had size one, but also that the entire matrix had size at most logarithmic in the number of elements of the group. This shows that and are, at least in this particular sense, “very non-Abelian,” and it is an encouraging sign that they may be useful in constructing expanders and other quasi-random objects.

On his way toward a question about subsets of groups not containing triples of the form , Gowers shows that every dense Cayley graph constructed on has constant edge expansion. (By dense, we mean that the degree is , where is the number of vertices.) This is a result that, assuming Frobenius theorem, has a simple proof, which I hope to understand and describe at a later point.

The celebrated Ramanujan graphs of Lubotzky, Phillips and Sarnak are constant-degree Cayley graphs constructed from , which is the same as except that we put no restriction on the determinant. Their relationship between degree and eigenvalue gap is best possible. The analysis of Lubotzky et al. is, unfortunately, completely out of reach.