Of particular interest to me is the story of the problem of finding large gaps between primes; recently Maynard, Ford, Green, Konyagin, and Tao solved an Erdös $10,000 question in this direction. It is probably the Erdös open question with the highest associated reward ever solved (I don’t know where to look up this information — for comparison, Szemeredi’s theorem was a $1,000 question), and it is certainly the question whose statement involves the most occurrences of ““.
The Bulletin of the AMS is going to publish a 57-page survey on growth in groups, which is already online, and which touches several topics of interest to readers of in theory, including the recent work of Bourgain and Gamburd on expander Cayley graphs of and the work of Helfgott and Seress on the diameter of permutation groups.
Alexander Grothendieck died on Thursday at age 86 in Saint-Girons.
Grothendieck, who started his work in functional analysis, is known for his far-reaching (and still incomplete) program of creating new foundations for algebraic geometry, a work that he led at IHES in the 50s and 60s and that is documented in the thousands of pages of EGA and SGA. If modern algebraic geometry is built on schemes, has applications to number theory, has definitions given in a category-theoretic language, and is completely incomprehensible to the novice, it is all thanks to Grothendieck’s vision.
In his 40s, and the top of his game, Grothendieck left IHES over the issue of military funding, and progressively detached from the mathematical community, while embracing environmental and anti-war causes.
Grothendieck’s life story, from his escaping Nazi Germany, to his revolution in mathematics, to his radical politics and later hermit life, is spellbinding. Some of it is told in a great two-part article in the Notices of the AMS (part 1, part 2) and I would also recommend this more technical essay and this more philosophical one.
Grothendieck has a flair for effective naming, he had a way with words, and he liked elaborate metaphors. Here is his famous “how to break a nut” analogy describing his style of mathematical research
I can illustrate the second approach with the same image of a nut to be opened. The first analogy that came to my mind is of immersing the nut in some softening liquid, and why not simply water? From time to time you rub so the liquid penetrates better, and otherwise you let time pass. The shell becomes more flexible
through weeks and months—when the time is ripe, hand pressure is enough, the shell opens like a perfectly ripened avocado!
The Italian prime minister is in the United States for the UN general assembly meeting, and he was in the San Francisco bay area on Sunday and Monday. (No, this is not the one who paid money to an underage prostitute and had she released from custody by falsely claiming she was the niece of Mubarak, it’s the new one.)
Those two days were busy, and he met Italian start-up founders in the area, went to a dinner at Stanford hosted by John Hennessy, presided the inauguration of a new Italian-language school, went to Twitter, Google, Facebook and Yahoo, and he met the local Italian research community.
For the last event, a few colleagues and I were asked to give a short presentation. Being not sure what to say to a prime minister, I asked a colleague who is the department chair at an Italian computer science department for some data on state funding of university research in computer science, and if there was a way to turn this data into a recommendation, and his response could be summarized as “we cannot be saved, there is no hope.” This might have made a good theme for a presentation, but instead I talked about the importance of fundamental research, and of working on ideas for which the technology is not ready yet, so that when the technology is ready the ideas are mature. Politicians are good at feigning attention when their mind is elsewhere, and he feigned it well.
Yesterday I was “interviewed” as part of the process to naturalize as an American citizen. Part of the interview is a test of the knowledge that an American is supposed to have. I liked to think that the officer would bring up a map of the world and ask me to point to France, then I would point to Brazil, and he would say, “great, now you are ready to be an American!” (Instead he asked how many US senators there are, when was the constitution written, and things like that.) The vibe was very different from any other interaction I have had with the American immigration system before; now it’s not any more “who are you, why are you stealing our jobs, and how do we know you are not a terrorist,” but it’s all “yay, you are going to be one us.”
A conjectural approaches to the Riemann hypothesis is to find a correspondence between the zeroes of the zeta function and the eigenvalues of a linear operator. This was first conceived by Hilbert and by Pólya in the 1910s. (See this correspondence with Odlyzko.) In the subsequent century, there have been a number of rigorous results relating the zeroes of zeta functions in other settings to eigenvalues of linear operators. There is also a connection between the distribution of known zeroes of the Riemann zeta function, as derived from explicit calculations, and the distribution of eigenvalues of the Gaussian unitary ensemble.
In a previous post we talked about the definition of the Ihara zeta function of a graph, and Ihara’s explicit formula for it, in terms of a determinant that is closely related to the characteristic polynomial of the adjacency matrix of the graph, so that the zeroes of the zeta function determine the eigenvalue of the graph. And if the zeta function of the graph satisfies a “Riemann hypothesis,” meaning that, after a change of variable, all zeroes and poles of the zeta function are in absolute value, then the graph is Ramanujan. Conversely, if the graph is Ramnujan then its Ihara zeta function must satisfy the Riemann hypothesis.
As I learned from notes by Pete Clark, the zeta functions of curves and varieties in finite fields also involve a determinant, and the “Riemann hypothesis” for such curves is a theorem (proved by Weil for curves and by Deligne for varieties), which says that (after an analogous change of variable) all zeroes and poles of the zeta function must be in absolute value, where is the size of the finite field. This means that one way to prove that a family of -regular graphs is Ramanujan is to construct for each graph in the family a variety over such that the determinant that comes up in the zeta function of is the “same” (up to terms that don’t affect the roots, and to the fact that if is a root for one characteristic polynomial, then has to be a root for the other) as the determinant that comes up in the zeta function of the variety . Clark shows that one can constructs such families of varieties (in fact, curves are enough) for all the known algebraic constructions of Ramanujan graphs, and one can use families of varieties for which the corresponding determinant is well understood to give new constructions. For example, for every , if is the number of distinct prime divisors of (which would be one if is a prime power) Clark gets a family of graphs with second eigenvalue . (The notes call the number of distinct prime divisors of , but it must be a typo.)
So spectral techniques underlie fundamental results in number theory and algebraic geometry, which then give us expander graphs. Sounds like something that we (theoretical computer scientists) should know more about.
The purpose of these notes is to explore a bit more the statements of these results, although we will not even begin to discuss their proofs.
One more reason why I find this material very interesting is that all the several applications of polynomials in computer science (to constructing error-correcting codes, secret sharing schemes, -wise independent generators, expanders of polylogarithmic degree, giving the codes used in PCP constructions, self-reducibility of the permanent, proving combinatorial bounds via the polynomial method, and so on), always eventually rely on three things:
- A multivariate polynomial restricted to a line can be seen as a univariate polynomial (and restricting to a -dimensional subspace gives a -variate polynomial); this means that results about multivariate polynomials can often be proved via a “randomized reduction” to the univariate case;
- A univariate polynomial of degree has at most roots, which follows from unique factorization
- Given desired roots we can always find an univariate polynomial of degree which has those roots, by defining it as .
This is enough to explain the remarkable pseudo-randomness of constructions that we get out of polynomials, and it is the set of principles that underlie much of what is below, except that we are going to restrict polynomials to the set of zeroes of another polynomial, instead of a line, and this is where things get much more complicated, and interesting.
Before getting started, however, I would like to work out a toy example (which is closely related to what goes on with the Ihara zeta function) showing how an expression that looks like the one defining zeta functions can be expressed as a characteristic polynomial of a linear operator, and how its roots (which are then the eigenvalues of the operator) help give bound to a counting problem, and how one can get such bounds directly from the trace of the operator.
If we have quantities that we want to bound, then the “zeta function” of the sequence is
For example, and this will be discussed in more detail below, if if a bivariate polynomial over , we may be interested in the number of solutions of the equation over , as well as the number of solutions over the extension . In this case, the zeta function of the curve defined by is precisely
and Weil proved that is a rational function, and that if are the zeroes and poles of , that is, the roots of the numerator and the denominator, then they are all at most in absolute value, and one has
Here is our toy example: suppose that we have a graph and that is the number of cycles of the graph of length . Here by “cycle of length ” we mean a sequence of vertices such that and, for , . So, for example, in a graph in which the vertices form a triangle, and are two distinct cycles of length 3, and is a cycle of length 2.
We could define the function
and hope that its zeroes have to do with the computation of , and that can be defined in terms of the characteristic polynomial.
Indeed, we have (remember, is a complex number, not a matrix):
and, if are the zeroes and poles of , then
How did we get these bounds? Well, we cheated because we already knew that , where are the eigenvalues of . This means that
Where we used . Now we see that the poles of are precisely the inverses of the eigenvalues of .
Now we are ready to look more closely at various zeta functions.
I would like to thank Ken Ribet and Jared Weinstein for the time they spent answering questions. Part of this post will follow, almost word for word, this post of Terry Tao. All the errors and misconceptions below, however, are my own original creation.
After my lectures in the “boot camp” of the spectral graph theory program at the Simons Institute, I promised I would post some references, because I stated all results without attribution.
Here is a a first draft.
If you notice that work that you know of (for example, your work) is misrepresented or absent, please let me know and I will edit the document. (If possible, when you do so, do not compare me to Stalin and cc your message to half a dozen prominent people — true story.)
Suppose that we want to construct a very good family of -regular expander graphs. The Alon-Boppana theorem says that the best we can hope for, from the point of view of spectral expansion, is to have , and we would certainly be very happy with a family of graphs in which .
Known constructions of expanders produce Cayley graphs (or sometimes Schreier graphs, which is a related notion), because it is easier to analyze the spectra of such graphs. If is a group with operation and is the inverse of element , and is a symmetric set of generators, then the Cayley graph is the graph whose vertices are the elements of and whose edges are the pairs such that .
When the group is Abelian, there is good news and bad news. The good news is that the eigenvectors of the graphs are completely characterized (they are the characters of ) and the eigenvalues are given by a nice formula. (See here and here.) The bad news is that constant-degree Cayley graphs of Abelian groups cannot be expanders.
That’s very bad news, but it is still possible to get highly expanding graphs of polylogarithmic degree as Cayley graphs of Abelian groups.
Here we will look at the extreme case of a family of graphs of degree , where is the number of vertices. Even with such high degree, the weak version of the Alon-Boppana theorem still implies that we must have , and so we will be happy if we get a graph in which . Highly expanding graphs of degree are interesting because they have some of the properties of random graphs from the distribution. In turn, graphs from have all kind of interesting properties with high probabilities, including being essentially the best known Ramsey graphs and having the kind of discrepancy property that gives seedless extractors for two independent sources. Unfortunately, these properties cannot be certified by spectral methods. The graph that we will study today is believed to have such stronger properties, but there is no known promising approach to prove such conjectures, so we will content ourselves with proving strong spectral expansion.
The graph is the Paley graph. If is a prime, is the group of addition modulo , and is the set of elements of of the form , then the graph is just . That is, the graph has a vertex for each , and two vertices are adjacent if and only if there is an such that .
Let be a -regular graph, and let
be the eigenvalues of the adjacency matrix of counted with multiplicities and sorted in descending order.
How good can the spectral expansion of be?
1. Simple Bounds
The simplest bound comes from a trace method. We have
by using one definition of the trace and
using the other definition and observing that counts the paths that go from to in two steps, of which there are at least : follow an edge to a neighbor of , then follow the same edge back. (There could be more if has multiple edges or self-loops.)
So we have
The condition is necessary to get lower bounds of ; in the clique, for example, we have and .
A trace argument does not give us a lower bound on , and in fact it is possible to have and , for example in the bipartite complete graph.
If the diameter of is at least 4, it is easy to see that . Let be two vertices at distance 4. Define a vector as follows: , if is a neighbor of , and if is a neighbor of . Note that there cannot be any edge between a neighbor of and a neighbor of . Then we see that , that (because there are edges, each counted twice, that give a contribution of to ) and that is orthogonal to .
2. Nilli’s Proof of the Alon-Boppana Theorem
Nilli’s proof of the Alon-Boppana theorem gives
where is the diameter of . This means that if one has a family of (constant) degree- graphs, and every graph in the family satisfies , then one must have . This is why families of Ramanujan graphs, in which , are special, and so hard to construct, or even to prove existence of.
Friedman proves a stronger bound, in which the error term goes down with the square of the diameter. Friedman’s proof is the one presented in the Hoory-Linial-Wigderson survey. I like Nilli’s proof, even if it is a bit messier than Friedman’s, because it starts off with something that clearly is going to work, but the first two or three ways you try to establish the bound don’t work (believe me, I tried, because I didn’t see why some steps in the proof had to be that way), but eventually you find the right way to break up the estimate and it works.
So here is Nilli’s proof. Continue reading
Today, after a lecture in the spectral graph theory boot camp at the Simons institute, I was asked what the expander mixing lemma is like in graphs that are not regular.
I don’t know if I will have time to return to this tomorrow, so here is a quick answer.
First, for context, the expander mixing lemma in regular graph. Say that is a -regular undirected graph, and is its adjacency matrix. Then let the eigenvalues of the normalized matrix be
We are interested in graphs for which all the eigenvalues are small in absolute value, except , that is, if we define
we are interested in graphs for which is small. The expander mixing lemma is the fact that for every two disjoint sets and of vertices we have
The inequality (1) says that, if is small, then the number of edges between every two large sets of vertices is almost determined just by the size of the sets, and it is equal to the expected number of edges between the two sets in a random -regular graph, up to an error term that depends on .
For the proof, we observe that, if we call the matrix that has ones everywhere, then
and then we substitute and in the above expression and do the calculations.
In the case of an irregular undirected graph , we are going to consider the normalized adjacency matrix , where is the adjacency matrix of and is the diagonal matrix such that , where is the degree of . As in the regular case, the eigenvalues of the normalized adjacency matrix satisfy
Let us define
the second largest eigenvalue in absolute value of .
We will need two more definitions: for a set of vertices , its volume is defined as
the sum of the degrees and the average degree, so that . Now we have
So, once again, we have that the number of edges between and is what one would expect in a random graph in which the edge exists with probability , up to an error that depends on .