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 or ). 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 . What if we restricted our to be prime? I.e., are prime ratios dense in (say) ?
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 , and correspondingly that the nth prime . So then we might hope that if is dense in , prime ratios would be dense too. Fortunately, showing that is dense is straightforward. For the rest, we use this proposition:
If , then is dense iff is dense.
Proof : Since , for any there is some s.t. for all , we have that . Thus . Similarly, we can say that .
Putting these together, we see that
If is dense, then in particular for any real number , we can choose some s.t. . Putting this together again, we see that
And so is dense as well. The proof of the converse is identical.
Now that we have that, we ask: is it true that 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 , there is always a prime in the interval . 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 . Then consider pairs of intervals for large enough that . We know there are primes in each pair of intervals.
Then our result follows from the fact that 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 , there exists some number s.t. for all , there is a prime in the interval .
Proof: Directly use the prime number theorem to show that
Prime ratios are dense in the positive reals.
Proof: For any real and , we want primes s.t. , or equivalently . Then let $\latex \epsilon’ = \epsilon/r$. Let be the bound from the last lemma, and let be any prime with . Then since there’s a prime in , let to complete the proof.
To end, I wanted to note a related, cool result. If is the set of primes, then is dense in . 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.