Feature

If One at a Time is too Difficult, Try All at Once!

Leave a comment

In the past months, I spent was much time as I had on taking online courses at Coursera. One particularly interesting course, both from a mathematical and computational point of view, is Analytic Combinatorics which applies combinatorics (i.e., the art of counting) to the analysis of algorithms by finding formulae, exact or asymptotic, for their running time.

It is notoriously difficult to find exact formulae for general combinatorial constructs. Typically, we want to know how many objects, e.g., trees, permutations, sequences, with certain properties there are of a given size. Famously, the number of binary trees (and about a million other constructions) is governed by the Catalan numbers

C_n = \frac{1}{n+1}{2n\choose n}.

Continue reading →

Riemann's Paper

Applying the Explicit Formula

Leave a comment

It's quite some time since we arrived at Riemann's main result, the explicit formula

J(x)=\mathrm{Li}(x)-\sum_{\Im\varrho>0}\left(\mathrm{Li}(x^\varrho)+\mathrm{Li}(x^{1-\varrho})\right)+\int_x^\infty\frac{\mathrm{d}t}{t(t^2-1)\log t}-\log2,

where J(x) is the prime power counting function introduced even earlier. It's high time we applied this!

First, let's take a look at J(x) when calculating it exactly:

J(x) Continue reading →

Feature

How NOT to Earn a Million Dollars

Leave a comment

I recently spent some time on the formidable website Numberphile which explains mathematical ideas, some important, some recreational, in short and accessible videos. Definitely worth checking out. One of the videos that is most relevant to us explains the Riemann Hypothesis:

Continue reading →

Probability

Tossing the Prime Coin

1 Comment

One of the problems with explaining the Riemann Hypothesis is that its fascination comes from its deep connection to prime numbers, but its definition is in terms of complex analysis which requires a fair deal of undergraduate mathematics to understand -- and that is before you even got started to grasp what the heck the zeta-zeros have to do with the distribution of primes. My "cocktail party explanation" of the Riemann Hypothesis would usually be something like: "The prime numbers are as equally distributed as you could wish for." But there is actually a surprisingly easy interpretation of the Riemann Hypothesis: "Prime numbers behave like a random coin toss." Continue reading →

Riemann's Paper

Integral Madness

1 Comment

We've seen the calculus version

J(x)=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}\log\zeta(s)x^s\frac{\mathrm{d}s}{s},

of the Euler product, and we know how to express \xi(s) as a product over its roots

\xi(s)=\xi(0)\prod_\varrho\left(1-\frac{s}{\varrho}\right),

where

\begin{align}\xi(s)&=\frac{1}{2}\pi^{-s/2}s(s-1)\Pi(s/2-1)\zeta(s)\nonumber\\&=\pi^{-s/2}(s-1)\Pi(s/2)\zeta(s).\nonumber\end{align}

High time we put everything together -- the reward will be the long expected explicit formula for counting primes! Continue reading →

Euler product

From Zeta to J and Back (And Yet Again Back)

Leave a comment

We know a lot about the \zeta and \xi-functions, we've learnt all about the different prime counting functions, most notably J(x), so it's high time we found a connection between the two. Probably not too surprisingly, the crucial link is our good friend, the Euler product

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

What we want to develop now is a version of this product that will suit us to find a formula that magically can count primes. (Remember that the Euler product is an analytical version of the fundamental theorem of arithmetic, so this is a natural starting point for our search.) Continue reading →

Functional Equation

Infinity Is Worth No More Than -1/12

Leave a comment

On 16 January 1913, a confused manuscript reached the famous mathematician G. H. Hardy in Cambridge. Other researchers have received similar letters before, and rejected it due to the seemingly incoherent formulae mixed with trivial mathematical results. Professional mathematicians are used to receiving manuscripts by amateurs who believe to have solved famous problems, but this particularly odd scribble caught the eye:

1+2+3+4+5+6+\ldots+\infty=-\frac{1}{12}

Did this amateur mathematician really think that the sum of all natural numbers, a value that will exceed any given boundary at some point, will wind up being a negative fraction? M. J. M. Hill of the University College, London, simply responded that the author must have fallen victim to the pitfalls of divergent series and referred him to a standard textbook on the topic.

So, was this really just the work of a lunatic? Well, recently, the New York Times covered the topic, linking a video in which two physicists explain the importance of this result in modern string theory. While many physicists may not be too far from lunatics, these two make a pretty strong argument in this case: Continue reading →

Riemann's Paper

Counting Primes Functionally

2 Comments

After all this playing with the \zeta-function it is time to return to the overall objective of this whole exercise: counting prime numbers. The idea behind analytic number theory is that primes are unpredictable on the small scale, but actually surprising regular on the large scale. This is why we'll look at certain functions that behave pretty erratically when we look at every single value, but become smooth and "easy" to calculate once we "zoom out" and consider the global properties, the so-called asymptotic. Continue reading →

Riemann's Paper

More symmetry and Another Product

Leave a comment

We've seen that \zeta(s) satisfies the functional equation

\zeta(1-s)=2^{1-s}\pi^{-s}\cos(\pi s/2)\Pi(s-1)\zeta(s).

(Well, it still needs to be proved, but let's just assume it's correct for now.) The goal of this post is an even more symmetrical form that will yield the function \xi(s) which we can develop into an incredibly useful product expression.

On our wish list for \xi(s) we find three items:

  1. It's  an entire function, i.e., a function that's holomorphic everywhere in \mathbb{C} without any poles.
  2. It has zeros for all non-trivial zeros of the \zeta-function, and no others.
  3. It's perfectly symmetrical along the critical line, i.e., it satisfies \xi(1-s)=\xi(s).

Continue reading →

Probability

Are Primes Independent?

Leave a comment

The question may sound silly, but I hope it will become apparent that it's very reasonable to ask. What we will examine here is the probabilistic interpretation of the prime distribution. So, essentially we ask: "What's the probability that a randomly chosen number is prime?" Those familiar with some basic probability theory know the notion of independency in this context, so the question I'm basically interested in here is if the probability to find a prime is independent of the preceding or following numbers. This post is a little out of the regular narrative, but it's something I have been thinking about recently, and I think it makes a cute article.

But one step back. First consider the following problem: We pick a number X not exceeding some (large) n at random. What are the odds this number is prime? Well, this is a classic example of a discrete probability, so the answer is positive cases over all cases, i.e.,

P(X\in\mathbb{P})=\frac{\pi(n)}{n},

where \mathbb{P} denotes the set of all primes, and \pi(n) is the prime counting function, i.e., the number of primes not exceeding n. Now, the famous Prime Number Theorem states that we can approximate \pi(n) with the elementary function

\pi(n)\sim\frac{n}{\log n}.

Don't worry too much about the exact meaning of the tilde, we will have plenty of opportunity to examine it further. For now just read it as "the left-hand side behaves similarly to the right-hand side". Now we can substitute this approximation in the calculation of the probability above, and obtain

P(X\in\mathbb{P})\sim\frac{n/\log n}{n}=\frac{1}{\log n}.

Continue reading →

%d bloggers like this: