There is a certain pattern to learning mathematics that I got used to in primary and secondary school. It starts like this: first, there are only positive numbers. We have 3 apples, or 2 apples, or maybe 0 apples, and that’s that. Sometime after realizing that 100 apples is a lot of apples (I’m sure that’s how my 6 year old self would have thought of it), we learn that we might have a negative number. That’s how I learned that they don’t always tell us everything, and that sometimes the things that they do tell us have silly names.

We know how the story goes – for a while, there aren’t remainders in division. Imaginary numbers don’t exist. Under no circumstance can we divide or multiply by infinity, or divide by zero. And this doesn’t go away: in my calculus courses (and the ones I’ve helped instruct), almost every function is continuous (at least mostly) and continuity is equivalent to ‘being able to draw it without lifting a pencil.’ It would be absolutely impossible to conceive of a function that’s continuous precisely at the irrationals, for instance (and let’s not talk about G_\delta or F_\sigma). And so the pattern goes on.

So when I hit my first class where I learned and used the pigeon-hole principle regularly (which I think was my combinatorics class? Michelle – if you’re reading this, perhaps you remember), I thought the name “pigeon-hole” was another one of those names that will get tossed. And I was wrong.

I was in a seminar today, listening to someone talk about improving results related to equidistribution theorems, approximating reals by rationals, and… the Dirichlet Box Principle. And there was much talking of pigeons and their holes (albeit a bit stranger, and far more ergodic-sounding than what I first learned on).

Not knowing much ergodic theory (or any at all, really), I began to think about a related problem. A standard application of pigeonholing is to show that any real number can be approximated to arbitrary accuracy by a rational \frac{p}{q}. What if we restricted our p,q to be prime? I.e., are prime ratios dense in (say) \mathbb{R}^+?

More after the fold –

So I seek to answer that question in a few different ways. It’s nice to come across problems that can be done, but that I haven’t done before. We’ll do three (somewhat) independent proofs.

First Method: Brute Force

The Prime Number Theorem (wiki) asserts that \pi(n) \sim \frac{n}{\log n}, and correspondingly that the nth prime p_n \approx n \log n. So then we might hope that if \frac{n \log n}{m \log m} is dense in \mathbb{R}^+, prime ratios would be dense too. Fortunately, showing that \frac{n \log n}{m \log m} is dense is straightforward. For the rest, we use this proposition:

If p_n \sim q_n, then \frac{p_n}{p_m} is dense iff \frac{q_n}{q_m} is dense.

Proof : Since p_n \sim q_n, for any \epsilon > 0 there is some N s.t. for all n,m > N, we have that |1 - \frac{p_n}{q_n}| < \epsilon. Thus 1 - \epsilon < \frac{p_n}{q_n} < 1 + \epsilon. Similarly, we can say that 1 - \epsilon < \frac{q_m}{p_m} < 1 + \epsilon.

Putting these together, we see that

 (1 - \epsilon)^2 < \frac{p_n}{p_m} \frac{q_m}{q_n} < (1 + \epsilon)^2

\frac{p_m}{p_n}(1-\epsilon) ^2< \frac{q_m}{q_n} < \frac{p_m}{p_n} (1 + \epsilon)^2

If \frac{p_m}{p_n} is dense, then in particular for any real number r, we can choose some n,m > N s.t. r (1 - \epsilon) < \frac{p_m}{p_n} < r(1 + \epsilon). Putting this together again, we see that

r(1-\epsilon)^3 < \frac{q_m}{q_n} < r(1 - \epsilon)^3

And so q_n/q_m is dense as well. The proof of the converse is identical. \diamondsuit

Now that we have that, we ask: is it true that \frac{n \log n}{m \log m} is dense? In short, yes. Now that we’ve gotten rid of the prime number restriction, this is far simpler. So I leave it out – but leave a comment if it’s unclear.

Method 2: Closer to Proper Pigeonholing

In a paper by Dusart (link to arxiv), Estimates of Some Functions over Primes without R.H., it is proved that for x > 400 000, there is always a prime in the interval [x, x(1 + \frac{1}{25 \log^2 x}]. We can use this to show the density of prime ratios as well. In fact, let’s be a little slick. If prime ratios are dense in the rationals, then since the rationals are dense in the reals we’ll be set. So suppose we wanted to get really close to some rational \frac{a}{b}. Then consider pairs of intervals [an, an(1 + \frac{1}{25 \log ^2 an}], [bn, bn(1 + \frac{1}{25 log ^2 bn}] for n large enough that an, bn > 400 000. We know there are primes p_n, q_n in each pair of intervals.

Then our result follows from the fact that \displaystyle \lim \frac{an}{bn} = \frac{a}{b} = \lim \frac{an(1 + \frac{1}{25 \log ^2 an})}{bn(1 + \frac{1}{25 \log ^2 bn})} and the sandwich theorem.

We pause for an aside: a friend of mine today, after the colloqium, was asking about why the pigeonhole principle was called the pigeonhole principle. Why not the balls in baskets lemma? Or the sock lemma or the box principle (which it is also called, but with far less regularity as far as I can tell)? So we considered calling it the sandwich theorem: if I have 4 different meats, but only enough bread for 3 sandwiches, then one sandwich will get at least 2 meats. What if we simply called every theorem the sandwich theorem, and came up with some equally unenlightening metaphorical explanation? Oof – deliberate obfuscation.

Method 3: First Principles

We do not actually need the extreme power of Dusart’s bound (which is not to say it’s not a great result – it is). In fact, we need nothing other than the prime number theorem itself.

For any \epsilon > 0, there exists some number N s.t. for all x > N, there is a prime in the interval [x, x(1+\epsilon)].

Proof: Directly use the prime number theorem to show that \lim \frac{\pi(n(1 + \epsilon)}{\pi(n)} = 1+\epsilon > 1

Prime ratios are dense in the positive reals.

Proof: For any real r and \epsilon > 0, we want primes p,q s.t. |p/q - r| < \epsilon, or equivalently qr - q\epsilon < p < qr + q\epsilon. Then let $\latex \epsilon’ = \epsilon/r$. Let N = N(\epsilon') be the bound from the last lemma, and let q be any prime with qr > N. Then since there’s a prime in [x, x(1 + \epsilon')], let x = qr to complete the proof. \diamondsuit

To end, I wanted to note a related, cool result. If P is the set of primes, then \sin P is dense in [-1,1]. This is less trivial, but it follows from a result from Vinogradov saying that the sequence of prime multiples of a fixed irrational number is equidistributed modulo 1. And this not at all immediately obvious to me.