jump to navigation

The easy parts of the prime number theorem September 30, 2009

Posted by David Speyer in Number theory.
5 comments

The prime number theorem states that the number of primes less than x is approximately \int_{t \leq x} dt/\log t. Proofs of the PNT tend to be easy to follow step by step, but I can never remember them once I step away from the page. I think I finally got the outline of the standard analytic proof to stick, so I’m going to record it here before I lose it:

1. Play around with \zeta(s).

Define the zeta function by

\zeta(s) = \sum_{n=1}^{\infty} n^{-s}.

Notice that \zeta(s) = \int_{t=1}^{\infty} \frac{dt}{t^s} + O(1)=1/(s-1) + O(1) as s \to 1. We have Euler’s factorization:

\zeta(s) = \prod_{p=1}^{\infty} \frac{1}{1-p^{-s}}

so

-\frac{\zeta'(s)}{\zeta(s)} = \sum_p \frac{(\log p) p^{-s}}{1- p^{-s}} = \sum_{n=1}^{\infty} \frac{\Lambda(n)}{n^s}.

Here \Lambda(n) is the Von Mangoldt function: \Lambda(n) = \log p if n=p^k and \Lambda(n)=0 otherwise. Since \zeta(s) has a first order pole at 1, we have - \zeta'(s)/\zeta(s) = 1/(s-1) + O(1). So

\sum_{n=1}^{\infty} \frac{\Lambda(n)}{n^s} = \sum_{n=1}^{\infty} \frac{1}{n^s} + O(1).

With a little care, we can see that the O(1) is an analytic function of s. So

\lim_{s \to 1} \sum_{n=1}^{\infty} \frac{\lambda(n)-1}{n^s} exists.

2. Take the limit as s goes to 1

Use the limit above to deduce that

\sum \frac{\Lambda(n)-1}{n} converges.

This is in red because it is really hard. Maybe I’ll say something about it later. But, intuitively, it makes sense.

Added in response to a comment of E. Kowalski As I discuss a little below, the fear is that \Lambda(n)-1 might behave like \sin(r \log n), for some r. In this case, we could not take the limit. If this exact problem occurred, then -\zeta'(s)/\zeta(s)+\zeta(s) would have a pole at 1+ir. A very clever trick shows that this function has no poles with real part 1. The challenge is to show that the absence of poles means that the limit is permissible.

3. Add up the partial sums

Fix \epsilon > 0. So there is an M such that, for M < w,x, we have \left| \sum_{n=w}^x \frac{\Lambda(n)-1}{n} \right| < \epsilon. Also, there must be some absolute bound C for any sum of the form \sum_{n=w}^x \frac{\Lambda(n)-1}{n}.

So

\left| \sum_{n=1}^x (\Lambda(n)-1) \right| = \left| \sum_{w=1}^x \sum_{n=w}^x \frac{\Lambda(n)-1}{n} \right| < CM + \epsilon x.

Since \epsilon is arbitrary, this shows that \sum_{n=1}^x (\Lambda(n)-1) = o(x). You are more likely to see this quoted as \sum_{n=1}^x \Lambda(n) =x +o(x).

4. Clean up

Standard techniques turn \sum_{n=1}^x (\Lambda(n)-1) = o(x) into \sum_{n=1}^x (\Lambda(n)/\log n-1/\log n) = o(x/\log x). In other words,
\pi(x) + (1/2) \pi(x^{1/2}) + \cdots = \sum_{n=1}^x (1/\log n) + o(x/\log x).
The terms \pi(x^{1/k}) are negligible for k>1.

A few notes below the fold:

(more…)

A (partial) explanation of the fundamental lemma and Ngo’s proof September 24, 2009

Posted by Joel Kamnitzer in Algebraic Geometry, Number theory, geometric Langlands, representation theory, things I don't understand.
2 comments

I would like to take Ben up on his challenge (especially since he seems to have solved the problem that I’ve been working on for the past four years) and try to explain something about the Fundamental Lemma and Ngo’s proof.  In doing so, I am aided by a two expository talks I’ve been to on the subject — by Laumon last year and by Arthur this week.

Before I begin, I should say that I am not an expert in this subject, so please don’t take what I write here too seriously and feel free to correct me in the comments.  Fortunately for me, even though the Fundamental Lemma is a statement about p-adic harmonic analysis, its proof involves objects that are much more familiar to me (and to Ben).  As we shall see, it involves understanding the summands occurring in a particular application of the decomposition theorem in perverse sheaves and then applying trace of Frobenius (stay tuned until the end for that!).

First of all I should begin with the notion of “endoscopy”.  Let G, G' be two reductive groups and let \hat{G}, \hat{G}' be there Langlands duals.  Then G' is called an endoscopic group for G if \hat{G}' is the fixed point subgroup of an automorphism of \hat{G} .  A good example of this is to take G = GL_{2n} , G' = SO_{2n+1} .  At first glance these groups having nothing to do with each other, but you can see they are endoscopic since their dual groups are GL_{2n} and Sp_{2n} and we have Sp_{2n} \hookrightarrow GL_{2n} .

As part of a more general conjecture called Langlands functoriality, we would like to relate the automorphic representations of G to the automorphic representations of all possible endoscopic groups G' .  Ngo’s proof of the Fundamental Lemma completes the proof of this relationship.

(more…)

Topology that Algebra can’t see July 28, 2009

Posted by David Speyer in Algebraic Geometry, Number theory.
15 comments

Let X be an algebraic variety over \mathbb{C}; that is to say, the zero locus of a bunch of polynomials with complex coefficients. We will consider this zero locus as a topological space using the ordinary topology on \mathbb{C}. One of the main themes of algebraic geometry in the last century has been learning how to study the topology of X in terms of the algebraic properties of the defining equations.

In this post, I will explain that there are intrinsic limits to this approach; things that cannot be computed algebraically. In particular, I want to explain how from a categorical point of view, we can’t even compute the homology H_1( \ , \mathbb{Z}). And, even if you don’t believe in categories, you’ll still have to concede that we can’t compute \pi_1( \ ). This is a very pretty example and it should be more widely known.

Absolutely none of the ideas in this post are original; I think most of them are due to Serre. (Thanks to Attila Smith in comments for the reference.)

(more…)

Continued Fractions and Hyperelliptic Curves July 2, 2009

Posted by David Speyer in Algebraic Geometry, Number theory.
4 comments

I recently read a charming little paper: Quasi-elliptic integrals and periodic continued fractions, by van der Poorten and Tran. Most of us who have taken a number theory course of some kind learned how to solve Pell’s equation: x^2 - D y^2 =1 where D is a nonsquare positive integer. The usual method is to compute the continued fraction
\displaystyle{\sqrt{D} = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{\cdots}}}}.
One then defines the convergents of \sqrt{D} by
\displaystyle{x_0/y_0 = a_0}
\displaystyle{x_1/y_1 = a_0 + \frac{1}{a_1}}
\displaystyle{x_2/y_2 = a_0 + \frac{1}{a_1+\frac{1}{a_2}}} etcetera.

Then x_i^2 - D y_i^2 tends to be very small and, if you compute long enough, for some i you will have x_i^2 - D y_i^2=1.

What van der Poorten and Tran do is to ask what happens if D is not an integer, but a polynomial D(t) = t^{2g+2} + d_{2g+1} t^{2g+1} + \cdots + d_1 t + d_0. Before I get into details, I want to tell you about something gorgeous that I won’t explain at all. Using the methods in their paper, van der Poorten and Trap can discover identities like
\displaystyle{ \int \frac{3 x dx}{\sqrt{x^4+2x}} = \log \left( x^3+1+x \sqrt{x^4+2x} \right)}.
Isn’t that pretty?

It turns out that the continued fraction algorithm for \sqrt{D(t)} is actually much prettier than for integers. Everything should be understood in terms of the curve C cut out by y^2 = D(t). This is a curve of genus g, with two points at infinity. (One of these points is the limit of (t, \sqrt{D(t)}) and the other is the limit of (t, -\sqrt{D(t)}).) I’ll call these two points \infty_{+} and \infty_{-}. The theory is controlled by the line bundles \mathcal{O}(k \infty_+ + \ell \infty_-). In particular, there are nontrivial solutions to x(t)^2 - D(t) y(t)^2 =1 if and only if the continued fraction is periodic, if and only if \mathcal{O}(k \infty_+) = \mathcal{O}(k \infty_-) for some a >0.

Below the fold, I’ll explain what is meant by the continued fraction algorithm for an algebraic function, and tell you some of the other nice results from the paper.

(more…)

Rabinoff on Witt Vectors May 6, 2009

Posted by David Speyer in Algebraic Geometry, Number theory.
4 comments

I have sometimes thought of writing a post on the ring of Witt vectors. But now I see that there is no need, because Joe Rabinoff has written a superb guide. Every time that I thought “this is pretty good, but it would be clearer if he pointed out X“, the next paragraph was an explanation of X!

There is one little thing that I could think to add, so I’ll do that here. I think you will get the most out of this paper if you approach each result as an exercise and try to give your own proof. However, right near the beginning is a theorem — Theorem 1.2, part 2 — which is too hard to be an exercise and where failure will be frustrating rather than illuminating. So I’m going to give you a hint.

Here is the result: Let K be a ring of characteristic p for which the map x \mapsto x^p is bijective. Let R be a ring in which p is not a zero divisor, which is complete and Hausdorff in the p-adic topology*, and such that R/pR \cong K. Theorem/Exercise There is a unique lift \tau: K \to R such that \tau(x) is congruent to x modulo p and such that \tau(x) \tau(y) = \tau(xy).

Here is the hint: \tau(x) can be characterized by the fact that it is the unique lift of x such that \tau(x)^{1/p^i} exists for every i.

That’s the only improvement I have. Go and enjoy!

* If the statement that R is complete and Hausdorff is weird for you, here is a restatement: The Hausdorff condition says that, for x \in R, if p^i divides x for every i, then x=0. The complete condition says this: Suppose we have a sequence x_n in R such that, for any i, the images of x_n in R/p^i are eventually constant. Then there is an element x \in R such that, for every i the image of x in R/p^i assumes the above-mentioned constant value.

I would advise, however, that you learn to think about these conditions topologically before attempting the Theorem/Exercise.

Generalized moonshine I: Genus zero functions January 8, 2009

Posted by Scott Carnahan in Number theory, Paper Advertisement, group theory, mathematical physics, representation theory.
21 comments

This is a plug for my first arXiv preprint, 0812.3440. It didn’t really exist as an independent entity until about a month ago, when I got a little frustrated writing a larger paper and decided to package some results separately. It is the first in a series of n (where n is about five right now), attacking the generalized moonshine conjecture. Perhaps the most significant result is that nontrivial replicable functions of finite order with algebraic integer coefficients are genus zero modular functions. This answers a question that has been floating around the moonshine community for about 30 years.

Moonshine originated in the 1970s, when some mathematicians noticed apparent numerical coincidences between the theory of modular functions and the theory of finite simple groups. Most notable was McKay’s observation that 196884=196883+1, where the number on the left is the first nontrivial Fourier coefficient of the modular function j, which classifies complex elliptic curves, and the numbers on the right are the dimensions of the smallest irreducible representations of the largest sporadic finite simple group, called the monster. Modular functions and finite group theory were two areas of mathematics that were not previously thought to be deeply related, so this came as a bit of a surprise. Conway and Norton encoded the above equation together with other calculations by Thompson and themselves in the Monstrous Moonshine Conjecture, which was proved by Borcherds around 1992.

I was curious about the use of the word “moonshine” here, so I looked it up in the Oxford English Dictionary. There are essentially four definitions:

  1. Light from the moon, presumably reflected from the sun (1425)
  2. Appearance without substance, foolish talk (1468 – originally “moonshine in the water”)
  3. A base of rosewater and sugar, or a sweet pudding (1558 cookbook!)
  4. Smuggled or illegally distilled alcoholic liquor (1782)

The fourth and most recent definition seems to be the most commonly used among people I know. The second definition is what gets applied to the monster, and as far as I can tell, its use is confined to English people over 60. It seems to be most popularly known among scientists through a quote by Rutherford concerning the viability of atomic power.

I’ll give a brief explanation of monstrous moonshine, generalized moonshine, and my paper below the fold. There is a question at the bottom, so if you get tired, you should skip to that.

(more…)

More F_un November 30, 2008

Posted by Ben Webster in Algebraic Geometry, Number theory, characteristic p, crazy ideas.
9 comments

Incidentally, I hope you’ve all been reading F_un mathematics. Even if you aren’t all that interested in the field with one element, it’s a beautifully designed site and might give you some ideas about pushing Web 2.0 in mathematics a bit further than just blogs. While I like our blog, with all its messy diversity (as my collaborators can tell you, messy diversity is a core component of my mathematical style), F_un mathematics has a much more organized focused feel, which I think maybe more promising for getting actual mathematics done. I also think the division of the posts into “outreach,” “undergraduate,” “graduate,” and “research” has some interesting potential and sort of makes me feel like we should be doing a better job of indicating the background level for our post.

Bleg: testing algebraic integrality by computer. October 13, 2008

Posted by Noah Snyder in Category Theory, Number theory, blegs, knot atlas, quantum algebra, subfactors, things I don't understand.
8 comments

Update 2: we’ve found a nice answer to our question. Maybe it will appear in the comments soon. –Scott M

Scott, Emily, and I have an ongoing project optimistically called “The Atlas of subfactors.” In the long run we’re hoping to have a site like Dror Bar-Natan and Scott’s Knot atlas with information about subfactors of small index and small fusion categories. In the short run we’re trying to automate known tests for eliminating possible fusion graphs for subfactors.

Right now we’re running into a computational bottleneck: given a number that is a ratio of two algebraic integers how can you quickly test whether it is an algebraic integer? Mathematica’s function AlgebraicIntegerQ is horribly slow, and we’re not sure if that’s because it’s poorly implemented or whether the problem is difficult. So, anyone have a good suggestion? After the jump I’ll explain what this question has to do with tensor categories (and hence subfactors which correspond to bi-oidal categories as I’ve discussed before).

To whet your appetite, here’s an example. Is a/b, where

a=-293 \lambda^{11}+4624 \lambda^9-23668 \lambda^7+50302 \lambda^5-44616\lambda^3+14017 \lambda

b=131\lambda^{10} - 2033 \lambda^8 + 9974\lambda^6-18951\lambda^4+12233 \lambda^2-1475

and where \lambda is the largest real root of

1 - 58 x^2 + 175 x^4 - 186 x^6 + 84 x^8 - 16 x^{10} + x^{12},

an algebraic integer? Mathematica running on Scott’s computer (using the builtin function AlgebraicIntegerQ) takes more than 5 minutes to decide that it is.

Update: Thanks to David Savitt for pointing out that both this example and an earlier one are answered instantly by MAGMA. Blegging is already working. But what’s the trick? Is it something we can teach Mathematica quickly? –Scott M

(more…)

The sign of the Gauss sum October 11, 2008

Posted by David Speyer in Number theory, Uncategorized.
4 comments

Let p be an odd prime. Let \left( \frac{a}{p} \right) be the Legendre symbol: \left( \frac{a}{p} \right)=1 if a is a quadratic residue modulo p, \left( \frac{a}{p} \right)=-1 if a is a quadratic nonresidue and \left( \frac{a}{p} \right)=0 if p divides a. Let \zeta denote e^{2 \pi i /p} and let

g(\zeta) = \sum_{j=0}^{p-1} \zeta^j \left( \frac{j}{p} \right).

As we’ll see below, it is not hard to show that g(\zeta)^2 = p^*, where p^* := (-1)^{(p-1)/2} p. Figuring out the sign of g(\zeta), on the other hand, is a famously hard problem; Gauss struggled with it for over a year before a sudden insight, at which point he wrote:

Finally, two days ago, I succeeded – not on account of my hard efforts, but by the grace of the Lord. Like a sudden flash of lightning, the riddle was solved. I am unable to say what was the conducting thread that connected what I previously knew with what made my success possible.

The answer is that g(\zeta) is a positive real number when p \equiv 1 \mod 4 and is a positive multiple of i when p is congruent to {3} modulo {4}. Gauss’s proof starts out by proving the following identity:

If \eta is any primitive pth root of unity, then

\sum_{j=0}^{p-1} \left( \frac{j}{p} \right) \eta^j = \prod_{k=1}^{(p-1)/2} \left( \eta^{-i/2} - \eta^{i/2} \right) \quad (*).

Here the exponents of \eta on the right hand side are to be considered modulo p. For example, if p=7, the identity is

\eta + \eta^2 - \eta^3 + \eta^4 - \eta^5 - \eta^6 = (\eta^3 - \eta^4) (\eta^1 - \eta^6) (\eta^2 - \eta^5).

I tried to prove this the other day and, to my surprise, found that mathematical notation had proceeded far enough that it was no longer hard! I’m sure this argument isn’t original, but it is nice enough to go in a blog post.
(more…)

This paper was written for our blog August 21, 2008

Posted by David Speyer in Algebraic Geometry, Number theory, Paper Advertisement, mathematical physics, papers, representation theory.
8 comments

I’ve recently been reading a paper which ties together a number of this blog’s themes: Canonical Quantization of Symplectic Vector Spaces over Finite Fields by Gurevich and Hadani. I’m going to try to write an introduction to this paper, in order to motivate you all to look at it. It really has something for everyone: symplectic vector spaces, analogies to physics, Fourier transforms, representation theory of finite groups, gauss sums, perverse sheaves and, yes, \theta functions. In a later paper, together with Roger Howe, the authors use these methods to prove the law of quadratic reciprocity and to compute the sign of the Gauss sum. For the experts, Gurevich and Hadani’s result can be summarized as follows: they provide a conceptual explanation of why there is no analgoue of the metaplectic group over a finite field. Not an expert? Keep reading!

(more…)