Alan Turing tribute

The November issue of the Notices of the AMS is a tribute to our hero Alan Turing. The timing is odd because such things are typically done when there is a significant anniversary, which does not seem to be the case here. (70 years since the Turing machines paper?)

Unlike the case of the tributes to Grothendieck, not much is said about Turing's life, except in Barry Cooper's article.

Paper Dolls

Being back in San Francisco for a few days, I had a chance to catch Paper Doll, a documentary profiling a group of Filipino immigrants in Israel, working mostly as caregivers for the elderly.

The Philippines are, for some reason, great exporters of caregivers. Italy has a large such immigrant community, and so do many countries in East Asia. In Taiwan, for example, the exploitation of Filipino maids and caregivers made possible by immigration laws is a cause célèbre of leftist groups. The same legal problems arise in Israel, where a work visa is immediately voided if one is fired, resulting in illegal status and the possibility of deportation. Indeed, the same is true for software engineering on H1B visas in the US, but the difference in class, education, and type of employment (not to mention the possibility of permanent residency) does not quite create the same situation.

The main angle of the movie, however, is that the Filipinos profiled in the documentary are all transgender, and they have formed a group, called Paper Dolls, that performs drag shows at community events.

They are met with acceptance and prejudice in a way that is not always predictable. Their clients, including religious ones, are accepting (even though those working in ultra-orthodox neighborhoods are uncomfortable there). The relation between one of them and the elderly man that she cares for, in particular, is very touching. Their attempt to play their act at a big-name gay club in Tel-Aviv, however, ends in a disaster of cultural insensivity.

Eventually, the group disbands, partly because of the vagaries of the Israeli immigration laws, some of them going back to the Philippines, and some of them moving to London.

The movie does not quite have a point, and its own sensibility oscillates between exploitation and sympathy. If its point was to express this conflict, then it succeeds quite well.

The primes are random except when they are not

The next issue of the Bulletin of the AMS will have an article by Jaikumar Radhakrishnan and Madhu Sudan on Dinur's proof of the PCP theorem. The article introduces the notion of PCP and its applications, as well as Irit's proof.

There will also be an article on the work of Goldston-Pintz-Yildirim on small gaps between primes. Their main result is that for every eps>0 there are infinitely many pairs of consecutive primes whose difference is less than eps times the average distance between consecutive primes of that magnitude. That is, we can find infinitely many pairs of primes p,p', p' > p such that p'-p < eps log p. This is a step in the direction of proving that there are infinitely many pairs p,p' such that p'-p =2, the twin primes conjecture.

This result is fascinating in various ways. One is the way it was discovered: Goldston and Yildirim had been working on gaps between primes since 1999, and announced the above result in 2003. But then a gap was found in the proof, which seemed to doom the whole approach. They kept working on it for two more years, however, until they made their breakthrough. You can read about it in Daniel Goldston's amusing artcile my 30 minutes of fame.

Technically, their results improve on previous "sieve" techniques whose spirit is to show that the "primes are 'pseudo-random' except in the obvious ways in which they aren't," as Green and Tao more or less put it, a statement that is made precise in the Hardy-Littlewood conjecture. The idea is to start by thinking of the following probabilistic "model" for prime numbers: a number N is "prime" with probability 1/ln N, and to observe that certain properties of the primes (for example, the prime number theorem) hold in this model. Faced with a conjecture, one can check if it is true in the model, and then see if it is true for all sets of integers that have some "pseudorandomness" property and finally verify that the primes have such pseudorandomness property, usually via Fourier analysis. (This would be the "circle method" in number theory.)

The model, of course, has some major shortcomings. For example it predicts infinitely many even numbers to be primes, and infinitely many pairs of primes that differ only by one. We may correct the model by, more realistically, saying that if N>2 is even, then it is never prime, and if it is odd then it is prime with probability 2/ln N. This is already better, and it predicts some true asymptotic properties of the primes, but it still has problems. For example, it predicts inifinitely many triples of primes p,p+2,p+4, while 3,5,7 is the only such triple. (Why?) An even better model is that N>6 is prime with probability 3/ln N if N mod 6 is either 1 or 5, and N is never prime otherwise.

We see we can define a hierarchy of more and more accurate models: in general, for a fixed W, we can look at the distribution that picks a 1/ln N fraction of numbers from 1 to N and that only picks numbers N such that N and W share no common factor. As we pick W to be a product of more and more of the first few primes, we get a more and more accurate model. (This would be the issue of "major arcs" versus "minor arcs" in the circle method.)

Now look at a conjecture about primes, for example the twin primes conjecture, and see what these models predict. They all predict const*N/(ln N)² twin primes between 1 and N, with the constant depending on W; for larger W, the constant tends to a limit c_twin. It is conjectured that there are in fact about c_twinN/(ln N)² twin primes between 1 and N.

More or less, the Hardy-Littlewood conjecture implies that the prediction given by this model is always right for questions that involve "linear equations over primes."

Apparently (I haven't read the papers) Goldston-Pintz-Yildirim approach the pseudorandomness of primes by looking at "higher moments." Green and Tao have been working on a different program based on studying the "Gowers uniformity" of the primes. (Technically, they study the Gowers uniformity of the Mobius function rather than of the characteristic function of the primes, but it's close enough in spirit.)

In the paper Quadratic Uniformity of the Mobius Function they show that the primes have small dimension-3 Gowers uniformity, and, together with their earlier result on Gowers uniformity and polynomials, this is used in a new paper to prove that the predictions of the Hardy-Littlewood conjecture hold for every question about linear equations over primes of "bounded complexity." For example, if you write certain pairs of linear equations over four prime unknowns, then the fraction of solutions will be as predicted by the limit of the random model. This includes the case of length-4 arithmetic progressions over primes, where you look at solutions p1,p2,p3,p4 to the equations p4-p3=p3-p2 and p3-p2=p2-p1.

These results and conjectures are part of an even bigger set of results whose spirit is that "multiplicative structure is pseudorandom with respect to addition," that can be seen in various results that have applications to combinatorial constructions. This comes up most directly in sum-product results in finite fields and over the integers, used to construct extractors, in Weil's result on character sums, which is used to construct eps-biased generators, in certain expander constructions related to Ramanujan graphs, and so on.

It is hard to believe that, until recently, analytic number theory was considered an unfashionable area, what with its quantitative results and its lack of connections to algebraic geometry. For example, I understand that the Berkeley math department, which is quite large, has no analytic number theorist.