Alexander Grothendieck dies 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!

Terry Tao at the Colbert Report

[Update 10/24/14: there was a bug in the code I wrote yesterday night, apologies to the colleagues at Rutgers!]

[Update 10/24/14: a reaction to the authoritative study of MIT and the University of Maryland. Also, coincidentally, today Scott Adams comes down against reputation-based rankings]

Saeed Seddighin and MohammadTaghi Hajiaghayi have proposed a ranking methodology for theory groups based on the following desiderata: (1) the ranking should be objective, and based only on quantitative information and (2) the ranking should be transparent, and the methodology openly revealed.

Inspired by their work, I propose an alternative methodology that meets both criteria, but has some additional advantages, including having an easier implementation. Based on the same Brown University dataset, I count, for each theory group, the total number of letters in the name of each faculty member.

Here are the results (apologies for the poor formatting):

1 ( 201 ) Massachusetts Institute of Technology
2 ( 179 ) Georgia Institute of Technology
3 ( 146 ) Rutgers – State University of New Jersey – New Brunswick
4 ( 142 ) University of Illinois at Urbana-Champaign
5 ( 141 ) Princeton University
6 ( 139 ) Duke University
7 ( 128 ) Carnegie Mellon University
8 ( 126 ) University of Texas – Austin
9 ( 115 ) University of Maryland – College Park
10 ( 114 ) Texas A&M University
11 ( 111 ) Northwestern University
12 ( 110 ) Stanford University
13 ( 108 ) Columbia University
14 ( 106 ) University of Wisconsin – Madison
15 ( 105 ) University of Massachusetts – Amherst
16 ( 105 ) University of California – San Diego
17 ( 98 ) University of California – Irvine
18 ( 94 ) New York University
19 ( 94 ) State University of New York – Stony Brook
20 ( 93 ) University of Chicago
21 ( 91 ) Harvard University
22 ( 91 ) Cornell University
23 ( 87 ) University of Southern California
24 ( 87 ) University of Michigan
25 ( 85 ) University of Pennsylvania
26 ( 84 ) University of California – Los Angeles
27 ( 81 ) University of California – Berkeley
28 ( 78 ) Dartmouth College
29 ( 76 ) Purdue University
30 ( 71 ) California Institute of Technology
31 ( 67 ) Ohio State University
32 ( 63 ) Brown University
33 ( 61 ) Yale University
34 ( 54 ) University of Rochester
35 ( 53 ) University of California – Santa Barbara
36 ( 53 ) Johns Hopkins University
37 ( 52 ) University of Minnesota – Twin Cities
38 ( 49 ) Virginia Polytechnic Institute and State University
39 ( 48 ) North Carolina State University
40 ( 47 ) University of Florida
41 ( 45 ) Rensselaer Polytechnic Institute
42 ( 44 ) University of Washington
43 ( 44 ) University of California – Davis
44 ( 44 ) Pennsylvania State University
45 ( 40 ) University of Colorado Boulder
46 ( 38 ) University of Utah
47 ( 36 ) University of North Carolina – Chapel Hill
48 ( 33 ) Boston University
49 ( 31 ) University of Arizona
50 ( 30 ) Rice University
51 ( 14 ) University of Virginia
52 ( 12 ) Arizona State University
53 ( 12 ) University of Pittsburgh

I should acknowledge a couple of limitations of this methodology: (1) the Brown dataset is not current, but I believe that the results would not be substantially different even with current data, (2) it might be reasonable to only count the letters in the last name, or to weigh the letters in the last name by 1 and the letters in the first name by 1/2. If there is sufficient interest, I will post rankings according to these other methodologies.

wong1

When he was 14, Joshua Wong cofounded Scholarism, the Hong Kong student movement that successfully protested the introduction of a “patriotic” curriculum. Now he is one of the student leaders of the Hong Kong pro-democracy movement.

Despite facing continued violence from triad-affiliated gangsters, the occupation continues, always in a uniquely Hong Kong manner.

Today Joshua Wong turns 18, and he gains the right to vote. May he be able to use this right freely!

[Photo by Anthony Kwan, video by the New York Times]

When Hong Kong was “handed over” to China on July 1st, 1997, the plan was that the city, now a Special Administrative Region, would retain its independent laws and institutions for 50 years, and it would have elections with universal suffrage (one person one vote). In 2007, it was decided that universal suffrage would start in 2017.

Discussion on how to regulate the 2017 elections has been going on for the last several months. A coalition of pro-democracy groups ran an informal referendum on the preferred system of election, gathering about 800,000 votes, or a fifth of the registered electorate. All the options in the referendum assumed no vetting process for the candidate, contrary to Beijing’s stance that any system for the 2017 election would only allow candidates pre-approved by the mainland government.

Afterwards (this happened during the summer), the pro-democracy groups organized an enormous rally, which had hundreds of thousands of participants, and announced plans to “occupy Central with love and peace” (Central contains the financial district) on October 1st if the Hong Kong legislature passed an election law in which candidates could run only with Beijing’s approval.

This was followed by an anti-democracy rally, partly attended by people bused in from across the border, which is a rather surreal notion; it’s like people are saying “we want our voices heard about the fact that we do not want our voices heard.”

A few days in advance of October 1st, a group of university students, some of them associated with group scholarism started a sit-in at a government building. Scholarism made news three years ago, when it (successfully) fought the proposal to introduce a “patriotic education” curriculum in grade school.

central-umbrellas

People have been facing the police with umbrellas and goggles to protect themselves from pepper spray.

central-2

The plaza in front of the government building, where the sit-in started, has been cleared, but for the whole weekend both Central and the neighboring district of Admiralty have been filled by thousands of protesters, day and night.

central-people

There is a petition at whitehouse.gov that has already exceeded the threshold required to receive a response, but that people might want to sign on.

Considering how the Chinese government feels about students rallying for democracy, there is reason to be worried.

disperse-or

[photos taken from Facebook, credits unknown]

STOC 2015 will be in Portland (yay!), and part of FCRC (boo!). The call for papers is out.

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.”

This article is very good

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 {1/\sqrt {d-1}} 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 {\sqrt q} in absolute value, where {q} is the size of the finite field. This means that one way to prove that a family of {(q+1)}-regular graphs is Ramanujan is to construct for each graph {G_n} in the family a variety {V_n} over {{\mathbb F}_q} such that the determinant that comes up in the zeta function of {G_n} is the “same” (up to terms that don’t affect the roots, and to the fact that if {x} is a root for one characteristic polynomial, then {1/x} has to be a root for the other) as the determinant that comes up in the zeta function of the variety {V_n}. 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 {d}, if {k} is the number of distinct prime divisors of {d-1} (which would be one if {d-1} is a prime power) Clark gets a family of graphs with second eigenvalue {2^k \sqrt{d-1}}. (The notes call {k} the number of distinct prime divisors of {d}, 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, {k}-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 {k}-dimensional subspace gives a {k}-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 {d} has at most {d} roots, which follows from unique factorization

  • Given {d} desired roots {a_1,\ldots,a_d} we can always find an univariate polynomial of degree {d} which has those roots, by defining it as {\prod_i (x-a_i)}.

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 {C_n} that we want to bound, then the “zeta function” of the sequence is

\displaystyle  z(T) := \exp\left( \sum_n \frac {C_n}{n} T^n \right)

For example, and this will be discussed in more detail below, if {P(\cdot,\cdot)} if a bivariate polynomial over {{\mathbb F}_q}, we may be interested in the number {C_1} of solutions of the equation {P(x,y) = 0} over {{\mathbb F}_q}, as well as the number of solutions {C_n} over the extension {{\mathbb F}_{q^n}}. In this case, the zeta function of the curve defined by {P} is precisely

\displaystyle  z(T) = \exp\left( \sum_n \frac {C_n}{n} T^n \right)  \ \ \ \ \ (1)

and Weil proved that {z(\cdot)} is a rational function, and that if {\alpha_1,\ldots,\alpha_{2g}} are the zeroes and poles of {z()}, that is, the roots of the numerator and the denominator, then they are all at most {\sqrt q} in absolute value, and one has

\displaystyle  | C_n - q^n | \leq \sum_i |\alpha_i|^n \leq 2g q^{n/2}  \ \ \ \ \ (2)

How does one get an approximate formula for {C_n} as in (2) from the zeroes of a function like (1), and what do determinants and traces have got to do with it?

Here is our toy example: suppose that we have a graph {G=(V,E)} and that {c_\ell} is the number of cycles of the graph of length {\ell}. Here by “cycle of length {\ell}” we mean a sequence {v_0,\ldots,v_\ell} of vertices such that {v_0=v_\ell} and, for {i=0,\ldots,\ell-1}, {\{ v_i,v_{i-1} \} \in E}. So, for example, in a graph in which the vertices {a,b,c} form a triangle, {a,b,c,a} and {a,c,b,a} are two distinct cycles of length 3, and {a,b,a} is a cycle of length 2.

We could define the function

\displaystyle  z(T) := \exp\left( \sum_\ell \frac {c_\ell}{\ell} T^\ell \right)

and hope that its zeroes have to do with the computation of {c_\ell}, and that {z} can be defined in terms of the characteristic polynomial.

Indeed, we have (remember, {T} is a complex number, not a matrix):

\displaystyle  z(T) = \frac 1 {\det (I - TA) }

and, if {\alpha_1,\ldots,\alpha_n} are the zeroes and poles of {z(T)}, then

\displaystyle  c_\ell \leq \sum_i |\alpha_i|^{-\ell}

How did we get these bounds? Well, we cheated because we already knew that {c_\ell = {\rm Tr}(A^\ell) = \sum_i \lambda_i^\ell}, where {\lambda_i} are the eigenvalues of {A}. This means that

\displaystyle  z(T) = \exp \left( \sum_\ell \sum_i \frac {\lambda_i^\ell}{\ell} T^\ell \right)

\displaystyle  = \prod_i \exp \left( \sum_\ell \frac {\lambda_i^\ell}{\ell} T^\ell \right)

\displaystyle  = \prod_i \frac 1 {1- T\lambda_i }

\displaystyle  = \frac 1 { \det(I - TA) }

Where we used {\frac 1 {1-x} = \exp\left( \sum_n \frac { x^n}{n} \right)}. Now we see that the poles of {z} are precisely the inverses of the eigenvalues of {A}.

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.

Read the rest of this entry »

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.)

a

Follow

Get every new post delivered to your Inbox.

Join 286 other followers