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}^+$?
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)]$.
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.
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 $\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.
Leave a comment
Info on how to comment
To make a comment, please send an email using the button below. Your email address won't be shared (unless you include it in the body of your comment). If you don't want your real name to be used next to your comment, please specify the name you would like to use. If you want your name to link to a particular url, include that as well.
bold, italics, and plain text are allowed in
comments. A reasonable subset of markdown is supported, including lists,
links, and fenced code blocks. In addition, math can be formatted using
$(inline math)$ or $$(your display equation)$$.
Please use plaintext email when commenting. See Plaintext Email and Comments on this site for more. Note also that comments are expected to be open, considerate, and respectful.
Comments (2)
2012-04-26 davidlowryduda
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.
2012-04-29 michelledelcourt
Pingbacks to this post [...]