A pigeon for every hole, and then one (sort of)

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 $latex G_\delta$ or $latex 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 $latex \frac{p}{q}$. What if we restricted our $latex p,q$ to be prime? I.e., are prime ratios dense in (say) $latex \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 $latex \pi(n) \sim \frac{n}{\log n}$, and correspondingly that the nth prime $latex p_n \approx n \log n$. So then we might hope that if $latex \frac{n \log n}{m \log m}$ is dense in $latex \mathbb{R}^+$, prime ratios would be dense too. Fortunately, showing that $latex \frac{n \log n}{m \log m}$ is dense is straightforward. For the rest, we use this proposition:

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

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

Putting these together, we see that

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

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

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

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

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

Now that we have that, we ask: is it true that $latex \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 $latex x > 400 000$, there is always a prime in the interval $latex [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 $latex \frac{a}{b}$. Then consider pairs of intervals $latex [an, an(1 + \frac{1}{25 \log ^2 an}], [bn, bn(1 + \frac{1}{25 log ^2 bn}]$ for $latex n$ large enough that $latex an, bn > 400 000$. We know there are primes $latex p_n, q_n$ in each pair of intervals.

Then our result follows from the fact that $latex \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.

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

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

Proposition
Prime ratios are dense in the positive reals.

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

To end, I wanted to note a related, cool result. If $latex P$ is the set of primes, then $latex \sin P$ is dense in $latex [-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.

This entry was posted in Expository, Math.NT, Mathematics and tagged , , , , , , , . Bookmark the permalink.

2 Responses to A pigeon for every hole, and then one (sort of)

  1. mixedmath says:

    And to put credit where it’s due – I chatted about this problem with Chan first, and we came up with the prime number theorem idea proof. I included the first because it’s nice, somehow. And if we wanted to do a Dirichlet-style bound for the necessary size of our primes, the second seems to be the way to go.

  2. Pingback: michelledelcourt

Leave a Reply