What’s new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

# Monthly Archive

You are currently browsing the monthly archive for September 2009.

## Two quick updates

30 September, 2009 in non-technical, update | Tags: google wave, mathematical blogging | by Terence Tao | 14 comments

1. In a previous post, I noted John Baez’s thread discussing his incipient article for the Notices of the AMS, entitled “What do mathematicians need to know about blogging?”.  John has now completed an initial draft of his article and is welcoming comments on it here. [Update, Oct 2: the article has now been submitted, incorporating much of the feedback.]
2. In another previous post, I talked about the forthcoming Google Wave platform being developed currently by Google, and its potential usefulness for online mathematical collaborative projects, such as the polymath projects.  My brother, who is one of the developers for this project, has just informed me that there are now a limited number of invites available to others who would like to develop specific Wave extensions or other projects (see for instance his own blog post, aimed at the GNOME community).  As I understand it, the Wave platform is not yet ready for general use, so these invites would be intended for technical developers (or preferably, a group of developers) who would be working on specific projects.  (For instance, I understand that there is already a preliminary extension for encoding LaTeX in a Wave, but it could be developed further.)  If any readers are interested, one can request an invite directly from the Google Wave page, or I can forward requests to my brother.  [At some point, I may ask for help in trying to build a Wave platform for the next generation of Polymath projects, but this will probably not occur for several months yet, due to a large number of other things on my plate (including existing Polymath projects).]

## The prime number theorem in arithmetic progressions, and dueling conspiracies

24 September, 2009 in expository, math.NT | Tags: Dirichlet characters, prime number theorem, Siegel's theorem | by Terence Tao | 26 comments

A fundamental problem in analytic number theory is to understand the distribution of the prime numbers ${\{2,3,5,\ldots\}}$. For technical reasons, it is convenient not to study the primes directly, but a proxy for the primes known as the von Mangoldt function ${\Lambda: {\mathbb N} \rightarrow {\mathbb R}}$, defined by setting ${\Lambda(n)}$ to equal ${\log p}$ when ${n}$ is a prime ${p}$ (or a power of that prime) and zero otherwise. The basic reason why the von Mangoldt function is useful is that it encodes the fundamental theorem of arithmetic (which in turn can be viewed as the defining property of the primes) very neatly via the identity

$\displaystyle \log n = \sum_{d|n} \Lambda(d) \ \ \ \ \ (1)$

for every natural number ${n}$.

The most important result in this subject is the prime number theorem, which asserts that the number of prime numbers less than a large number ${x}$ is equal to ${(1+o(1)) \frac{x}{\log x}}$:

$\displaystyle \sum_{p \leq x} 1 = (1+o(1)) \frac{x}{\log x}.$

Here, of course, ${o(1)}$ denotes a quantity that goes to zero as ${x \rightarrow \infty}$.

It is not hard to see (e.g. by summation by parts) that this is equivalent to the asymptotic

$\displaystyle \sum_{n \leq x} \Lambda(n) = (1+o(1)) x \ \ \ \ \ (2)$

for the von Mangoldt function (the key point being that the squares, cubes, etc. of primes give a negligible contribution, so ${\sum_{n \leq x} \Lambda(n)}$ is essentially the same quantity as ${\sum_{p \leq x} \log p}$). Understanding the nature of the ${o(1)}$ term is a very important problem, with the conjectured optimal decay rate of ${O(\sqrt{x} \log x)}$ being equivalent to the Riemann hypothesis, but this will not be our concern here.

The prime number theorem has several important generalisations (for instance, there are analogues for other number fields such as the Chebotarev density theorem). One of the more elementary such generalisations is the prime number theorem in arithmetic progressions, which asserts that for fixed ${a}$ and ${q}$ with ${a}$ coprime to ${q}$ (thus ${(a,q)=1}$), the number of primes less than ${x}$ equal to ${a}$ mod ${q}$ is equal to ${(1+o_q(1)) \frac{1}{\phi(q)} \frac{x}{\log x}}$, where ${\phi(q) := \# \{ 1 \leq a \leq q: (a,q)=1 \}}$ is the Euler totient function:

$\displaystyle \sum_{p \leq x: p = a \hbox{ mod } q} 1 = (1+o_q(1)) \frac{1}{\phi(q)} \frac{x}{\log x}.$

(Of course, if ${a}$ is not coprime to ${q}$, the number of primes less than ${x}$ equal to ${a}$ mod ${q}$ is ${O(1)}$. The subscript ${q}$ in the ${o()}$ and ${O()}$ notation denotes that the implied constants in that notation is allowed to depend on ${q}$.) This is a more quantitative version of Dirichlet’s theorem, which asserts the weaker statement that the number of primes equal to ${a}$ mod ${q}$ is infinite. This theorem is important in many applications in analytic number theory, for instance in Vinogradov’s theorem that every sufficiently large odd number is the sum of three odd primes. (Imagine for instance if almost all of the primes were clustered in the residue class ${2}$ mod ${3}$, rather than ${1}$ mod ${3}$. Then almost all sums of three odd primes would be divisible by ${3}$, leaving dangerously few sums left to cover the remaining two residue classes. Similarly for other moduli than ${3}$. This does not fully rule out the possibility that Vinogradov’s theorem could still be true, but it does indicate why the prime number theorem in arithmetic progressions is a relevant tool in the proof of that theorem.)

As before, one can rewrite the prime number theorem in arithmetic progressions in terms of the von Mangoldt function as the equivalent form

$\displaystyle \sum_{n \leq x: n = a \hbox{ mod } q} \Lambda(n) = (1+o_q(1)) \frac{1}{\phi(q)} x.$

Philosophically, one of the main reasons why it is so hard to control the distribution of the primes is that we do not currently have too many tools with which one can rule out “conspiracies” between the primes, in which the primes (or the von Mangoldt function) decide to correlate with some structured object (and in particular, with a totally multiplicative function) which then visibly distorts the distribution of the primes. For instance, one could imagine a scenario in which the probability that a randomly chosen large integer ${n}$ is prime is not asymptotic to ${\frac{1}{\log n}}$ (as is given by the prime number theorem), but instead to fluctuate depending on the phase of the complex number ${n^{it}}$ for some fixed real number ${t}$, thus for instance the probability might be significantly less than ${1/\log n}$ when ${t \log n}$ is close to an integer, and significantly more than ${1/\log n}$ when ${t \log n}$ is close to a half-integer. This would contradict the prime number theorem, and so this scenario would have to be somehow eradicated in the course of proving that theorem. In the language of Dirichlet series, this conspiracy is more commonly known as a zero of the Riemann zeta function at ${1+it}$.

In the above scenario, the primality of a large integer ${n}$ was somehow sensitive to asymptotic or “Archimedean” information about ${n}$, namely the approximate value of its logarithm. In modern terminology, this information reflects the local behaviour of ${n}$ at the infinite place ${\infty}$. There are also potential consipracies in which the primality of ${n}$ is sensitive to the local behaviour of ${n}$ at finite places, and in particular to the residue class of ${n}$ mod ${q}$ for some fixed modulus ${q}$. For instance, given a Dirichlet character ${\chi: {\mathbb Z} \rightarrow {\mathbb C}}$ of modulus ${q}$, i.e. a completely multiplicative function on the integers which is periodic of period ${q}$ (and vanishes on those integers not coprime to ${q}$), one could imagine a scenario in which the probability that a randomly chosen large integer ${n}$ is prime is large when ${\chi(n)}$ is close to ${+1}$, and small when ${\chi(n)}$ is close to ${-1}$, which would contradict the prime number theorem in arithmetic progressions. (Note the similarity between this scenario at ${q}$ and the previous scenario at ${\infty}$; in particular, observe that the functions ${n \rightarrow \chi(n)}$ and ${n \rightarrow n^{it}}$ are both totally multiplicative.) In the language of Dirichlet series, this conspiracy is more commonly known as a zero of the ${L}$-function of ${\chi}$ at ${1}$.

An especially difficult scenario to eliminate is that of real characters, such as the Kronecker symbol ${\chi(n) = \left( \frac{n}{q} \right)}$, in which numbers ${n}$ which are quadratic nonresidues mod ${q}$ are very likely to be prime, and quadratic residues mod ${q}$ are unlikely to be prime. Indeed, there is a scenario of this form – the Siegel zero scenario – which we are still not able to eradicate (without assuming powerful conjectures such as GRH), though fortunately Siegel zeroes are not quite strong enough to destroy the prime number theorem in arithmetic progressions.

It is difficult to prove that no conspiracy between the primes exist. However, it is not entirely impossible, because we have been able to exploit two important phenomena. The first is that there is often a “all or nothing dichotomy” (somewhat resembling the zero-one laws in probability) regarding conspiracies: in the asymptotic limit, the primes can either conspire totally (or more precisely, anti-conspire totally) with a multiplicative function, or fail to conspire at all, but there is no middle ground. (In the language of Dirichlet series, this is reflected in the fact that zeroes of a meromorphic function can have order ${1}$, or order ${0}$ (i.e. are not zeroes after all), but cannot have an intermediate order between ${0}$ and ${1}$.) As a corollary of this fact, the prime numbers cannot conspire with two distinct multiplicative functions at once (by having a partial correlation with one and another partial correlation with another); thus one can use the existence of one conspiracy to exclude all the others. In other words, there is at most one conspiracy that can significantly distort the distribution of the primes. Unfortunately, this argument is ineffective, because it doesn’t give any control at all on what that conspiracy is, or even if it exists in the first place!

But now one can use the second important phenomenon, which is that because of symmetries, one type of conspiracy can lead to another. For instance, because the von Mangoldt function is real-valued rather than complex-valued, we have conjugation symmetry; if the primes correlate with, say, ${n^{it}}$, then they must also correlate with ${n^{-it}}$. (In the language of Dirichlet series, this reflects the fact that the zeta function and ${L}$-functions enjoy symmetries with respect to reflection across the real axis (i.e. complex conjugation).) Combining this observation with the all-or-nothing dichotomy, we conclude that the primes cannot correlate with ${n^{it}}$ for any non-zero ${t}$, which in fact leads directly to the prime number theorem (2), as we shall discuss below. Similarly, if the primes correlated with a Dirichlet character ${\chi(n)}$, then they would also correlate with the conjugate ${\overline{\chi}(n)}$, which also is inconsistent with the all-or-nothing dichotomy, except in the exceptional case when ${\chi}$ is real – which essentially means that ${\chi}$ is a quadratic character. In this one case (which is the only scenario which comes close to threatening the truth of the prime number theorem in arithmetic progressions), the above tricks fail and one has to instead exploit the algebraic number theory properties of these characters instead, which has so far led to weaker results than in the non-real case.

As mentioned previously in passing, these phenomena are usually presented using the language of Dirichlet series and complex analysis. This is a very slick and powerful way to do things, but I would like here to present the elementary approach to the same topics, which is slightly weaker but which I find to also be very instructive. (However, I will not be too dogmatic about keeping things elementary, if this comes at the expense of obscuring the key ideas; in particular, I will rely on multiplicative Fourier analysis (both at ${\infty}$ and at finite places) as a substitute for complex analysis in order to expedite various parts of the argument. Also, the emphasis here will be more on heuristics and intuition than on rigour.)

The material here is closely related to the theory of pretentious characters developed by Granville and Soundararajan, as well as an earlier paper of Granville on elementary proofs of the prime number theorem in arithmetic progressions.

Read the rest of this entry »

## A speech for the American Academy of Arts and Sciences

17 September, 2009 in non-technical, opinion, talk, travel | Tags: american academy of arts and sciences | by Terence Tao | 56 comments

Next month, I am scheduled to give a short speech (three to five minutes in length) at the annual induction ceremony of the American Academy of Arts and Sciences in Boston.  This is a bit different from the usual scientific talks that I am used to giving; there are no projectors, blackboards, or other visual aids available, and the audience of Academy members is split evenly between the humanities and the sciences (as well as people in industry and politics), so this will be an interesting new experience for me.  (The last time I gave a speech was in 1985.)

My chosen topic is on the future impact of internet-based technologies on academia (somewhat similar in theme to my recent talk on this topic).  I have a draft text below the fold, though it is currently too long and my actual speech is likely to be a significantly abridged version of the one below [Update, Oct 12: The abridged speech is now at the bottom of the post.]  In the spirit of the theme of the talk, I would of course welcome any comments and suggestions.

For comparison, the talks from last year’s ceremony, by Jim Simons, Peter Kim, Susan Athey, Earl Lewis, and Indra Nooyi, can be found here.  Jim’s chosen topic, incidentally, was what mathematics is, and why mathematicians do it.

[Update, Nov 3: Video of the various talks by myself and the other speakers (Emmylou Harris, James Earl Jones, Elizabeth Nabel, Ronald Marc George, and Edward Villela) is now available on the Academy web site here.]

Read the rest of this entry »

## Structure and randomness in the prime numbers (IMO Festschrift submission)

14 September, 2009 in math.NT, paper | Tags: international mathematical olympiad | by Terence Tao | 9 comments

A few months ago, I gave a talk at the IMO in Bremen on “Structure and randomness in the prime numbers”.  I have now converted the slides from that talk into a more traditional paper (7 pages in length), for submission to a Festschrift for the Bremen Olympiad.  The content is much the same as the slides, but some references have been added.

## Two more Clay-Mahler lectures

6 September, 2009 in math.AP, math.MG, math.NT, talk, travel | Tags: Clay-Mahler lectures | by Terence Tao | 8 comments

I am posting the last two talks in my Clay-Mahler lecture series here:

• “Structure and randomness in the prime numbers“.  This public lecture is slightly updated from a previous talk of the same name given last year, but is largely the same material.
• “Perelman’s proof of the Poincaré conjecture“.  Here I try (perhaps ambitiously) to give an overview of Perelman’s proof of the Poincaré conjecture into an hour-length talk for a general mathematical audience.  It is a little unpolished, as I have not given any version of this talk before, but I hope to update it a bit in the future.

[Update, Sep 14: Poincaré conjecture slides revised.]

[Update, Sep 18: Prime slides revised also.]

## The cosmic distance ladder

3 September, 2009 in math.GM, non-technical, talk, travel | Tags: Clay-Mahler lectures, cosmic distance ladder | by Terence Tao | 18 comments

I am uploading another of my Clay-Mahler lectures here, namely my public talk on the cosmic distance ladder (4.3MB, PDF).  These slides are based on my previous talks of the same name, but I have updated and reorganised the graphics significantly as I was not fully satisfied with the previous arrangement.

[Update, Sep 4: slides updated.  The Powerpoint version of the slides (8MB) are available here.]

[Update, Oct 26: slides updated again.]
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 100, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9365893602371216, "perplexity_flag": "head"}