Suppose we take a subset of the natural numbers and look at the sum of the reciprocals of its elements:
One question we can ask here is: for which subsets does this sum converge? Though there are many routes one can take to try to answer this question, we look towards density.
The natural density of is defined to be
We think of this essentially as the probability of choosing an element of from the natural numbers. Let’s do some examples!
- We certainly have
- If then
- Let There are elements of less than so
- Let Then we need to know how many squares there are less than . If , then , so there are squares less than . Therefore
Notice that (being the harmonic series) diverges and Also, (being the Riemann zeta function evaluated at ) converges to and we just showed Perhaps this is our connection!
(Wishful-Thinking “Theorem”) For any ,
As the name of the above “theorem” hints at, this statement is not true. Our counterexample is a prevalent character: the primes. Recall the prime number theorem, which states that the number of primes less than some number is asymptotically Then the natural density of the primes must be
But in 1737, Euler proved that diverges! So our wishful-thinking theorem is not true. We call a set bad if it doesn’t satisfying our wishful-thinking theorem.
To me, this failure means that the natural numbers are too “large” to detect all sets whose sum of reciprocals diverge. So what if we shrank it? For let’s define the relative density of in to be
Like the natural density, we think of the relative density of in to be the probability that we choose an element of out of In fact, notice that
As such, we get similar properties as the natural density, with some interesting twists!
- If then
- If then
- If , then
- If and , then
- Most generally, given any we have
As all other properties follow from 5, we will only prove that fact.
(Proof of 5) This is essentially just a reordering of multiplication:
We shift all denominators to the right (cycling at the end) and find
Our main purpose in studying relative density is the hope that it will lead to an indicator set. We call a set an indicator set if for all we have
So is an indicator set if our wishful-thinking “theorem” is true when is replaced by We call it this because while is “too large”, is “small enough” to indicate the convergence of the sum of reciprocals of elements of There are a lot of interesting properties that indicator sets must have if they exist, but it turns out we can prove their nonexistence with two simple propositions.
(Proposition 1) If is an indicator set, then
(Proof) If we must have implying But so by the definition of , we must have This is a contradiction, so
The second proposition is not even a statement on indicator sets, but on relative density in general.
(Proposition 2) Given any , we have
(Proof) We have
We swap the denominators to find
We can now prove our main theorem!
(Main Theorem) There does not exist an indicator set. That is, there does not exist a set such that for all , we have if and only if
(Proof) Suppose there exists an indicator set Let be any bad set (like the primes, for example). Then proposition 1 and 2 together tell us that Since is bad, we have and But since we also have Together, these give
which is clearly a contradiction. Therefore, cannot exist.
Note that a “left-indicator set” (as opposed to the “right-indicator set” discussed above) can quickly be shown to not exist as well. Suppose was a set such that for all
Then property 1 tells us that for any subset we have which would imply that for all subsets which certainly cannot be true.
While the proof of the nonexistence of these indicators sets ended up being fairly short, there are still interesting things going on here. There has been a lot of work relating natural density, sum of reciprocals, and the containment of arbitrarily long arithmetic progressions (ALAPs). These relate as follows.
If the text inside a box is green, it indicates that the row implies the column (with the text referencing the proof). If it is red, then it implies the row does not imply the column (with the text giving a counterexample). Blue text indicates that the implication is currently an open question.
- X – I have had trouble finding this in the literature, here is a stackexchange post with a proof.
- ST – Szemerédi’s theorem,
- P – Primes,
- E – Erdős’ conjecture,
- GT – Green-Tao theorem,
- Y – Take the set . This set contains arithmetic progressions of arbitrary length but its sum of reciprocals converges, since
Clearly there’s a lot to look at here, so hopefully this is not the last time you will read about relative densities on this blog!
Thanks for reading,