A simpler “proof” (?) of the infinitude of prime twins and k-tuples

Consider the set of natural numbers, N. For any given natural number, n, every n-th natural number is a multiple of n, hence 1/n of N are multiples of n.

In the set of even numbers, E, every n-th number is also a multiple of n, hence 1/n of E are multiples of n.

We can generalize this statement that for the set of all multiples of any given prime number, Pn, and we will call this set Mn, every n-th member of this set is a multiple of n, hence 1/n of Mn are multiples of n.

If we remove E from N, and are left with with the set of odd numbers, O, then for any given n, 1/n of O are multiples of n.

Consider now the process of stepwise removal of all multiples of all primes, Pn, working from 2 toward infinity. Removal of the even numbers leaves 1/2 of N remaining under consideration as possible prime numbers.

Of the remaining half of N, 1/3 are multiples of 3, so further removal of composite numbers to eventually reveal the set of primes removes 1/3 of the remaining half of N, or 1/3 of 1/2, leaving a rational number, 1/3, of N remaining under consideration as possible primes.

When we next remove the remaining products of 5, we strip away 1/5 of what was left prior, or 1/5 of 1/3, or 1/15, leaving 8/30 of N.

In progressive steps of sieving with each successive prime, we strip away a fraction of the candidate primes remaining after the prior sieving step, where this fraction is in all cases a rational number, this leaving a rational number as the fraction of N remaining as possible primes.

As this process proceeds toward infinity, the fraction of N remaining with candidate primes gets ever smaller, approaching but never reaching zero, remaining always a rational number. Since N is an infinite set, any rational fraction of N is also infinite. Hence the set of prime numbers is infinite.

We can use similar logic to show that the sets of twin primes and larger prime k-tuples are also infinite.

Consider again stripping away all even numbers, leaving O. At this stage, every remaining number, which remains to this point under consideration as a possible prime, is separated from another candidate prime by two, hence every odd number is a candidate twin prime, and half of N remain as possible twin primes. Let’s call the set of candidate twins after n sieving steps as TWn.

Twin prime pairs (the “normal” definition) are groups of two consecutive primes separated by two. Consider that every twin pair, or every candidate pair remaining after the n-th sieving stage, has a lower prime and an upper prime. Define the set of lower primes within the n-th sieving stage set of candidate twins as T_L and the set of upper primes as T_U. Within the set of candidate twins, half are in T_L and half are in T_U, and T_L and T_U are offset by two, with all members of T_U being equal to the corresponding member of T_L plus 2. We can therefore deduce that within both T_L and T_U, 1/Pj of each set are multiples of Pj where Pj are primes higher than Pn.

When we remove all primes P(n+1) in the next stage of sieving, we remove 1/P(n+1) from T_L and 1/P(n+1) from T_U. Every member of T_L or T_U thus removed eliminates one candidate twin pair from further consideration, and since any single repetition of P(n+1) cannot eliminate both primes in a single pair, 1/P(n+1) of TWn are removed from both T_L and T_U, or 2/P(n+1) of TWn is eliminated.

Thus we see that, while 1/Pn of all remaining prime candidates are removed at each sieving stage, 2/Pn of all remaining twin prime pair candidates are removed. And yet, following a similar logic as demonstrated for the sequential elimination of prime candidates, the proportion of N remaining as candidate twin primes is always a rational number, no matter how arbitrarily large Pn becomes. Hence, there are infinitely many twin primes.

Following precisely the same logic, we can show that for Pn > k, where k is the size of a prime k-tuple, each sieving stage removes k/Pn of the set of candidate k-tuples remaining after the previous sieving stage, and hence the sets of all k-tuples for finite k, where feasible k-tuples exist, are infinite.

About petequinn

I'm a Canadian geotechnical engineer specializing in the study of landslides. I started this page to discuss some mathematical topics that interest me, initially this involved mostly prime numbers, but more recently I've diverted focus back to a number of topics of interest in geotechnique, geographic information systems and risk. I completed undergraduate training in engineering physics at Royal Military College (Kingston, Ontario), did a masters degree in civil (geotechnical) engineering at University of British Columbia (Vancouver), and doctorate in geological engineering at Queen's University (Kingston). I was a military engineer for several years at the beginning of my career, and did design and construction work across Canada and abroad. I've worked a few years for the federal government managing large environmental clean up projects in Canada's arctic, and I've worked across Canada, on both coasts and in the middle, as a consulting geotechnical engineer. My work has taken me everywhere in Canada's north, to most major Canadian cities and many small Canadian towns, and to Alaska, Chile, Bermuda, the Caribbean, Germany, Norway, Sweden, Bosnia, and Croatia. My main "hobby" is competitive distance running, which I may write about in future.
This entry was posted in Prime Numbers, Uncategorized. Bookmark the permalink.

5 Responses to A simpler “proof” (?) of the infinitude of prime twins and k-tuples

  1. Hugh says:

    This is my take on this one. For primes, you don’t need this level of complexity or to make a step from the finite to the infinite to prove they are an infinite set. Once you reach this step:

    “…we strip away a fraction of the candidate primes remaining after the prior sieving step, where this fraction is in all cases a rational number, this leaving a rational number as the fraction of N remaining as possible primes…”

    … the proof is done. Sieving by prime N will always leave (N-1)/N of the remaining candidates and, crucially, *the next remaining candidate must by definition be prime since it is not divisible by N or any smaller prime number*. That’s actually why this proof works, not because of the next step of reasoning from the finite set of candidates to the infinite set of primes.

    With twins and k-tuples however, the proof isn’t done at this stage. The fact that a set of candidates always remains doesn’t guarantee that any of those candidates are actual twins or k-tuples. The next candidate twin pair may be eliminated by a prime that comes between N and that twin and this might be a process that continues (we can intuitively see it is very unlikely, but still it falls short of being a proof).

    So with primes we can ignore the difference between candidates and primes because we do know that at least one of the remaining candidates must be prime. But for k-tuples it isn’t a proof to show that there will always be candidates, you’d have to show that at least one of those candidates will remain once we have sieved past them.

    • petequinn says:

      I think you’re glossing over the main thrust of the argument, which is that, regardless of how many primes you sieve with, you can never strip away all the twins. As n approaches infinity, there remains some extremely small but non-zero rational fraction of N remaining as twin prime pairs, and any rational number greater than zero multiplied by infinity is infinity.

  2. Hugh says:

    But candidates aren’t the same things as twins and that is why this isn’t a proof (whereas at least one prime candidate must be prime, which is why the same proof does work for primes).

    An infinity of candidates doesn’t imply an infinity of twins (same as with the proof I gave in the other thread – for any n we know that n+1 can’t be a K-number. As we go up through the sieve of n, an infinite number of K-number candidates always remains).

    I originally thought that the process you are describing was a proof of the infinitude of twin primes. Now I accept it is just a description of why there probably is an infinity of twin primes.

    • petequinn says:

      Hugh I’ve been mulling this over quite a bit. I’m not really convinced this is a valid objection, but honestly I’m not sure I’d know for sure one way or another. 🙂 I’ve been struggling like heck to come up with a way to rebut your objection. I think I’ve come up with something, and will post it shortly.


      Hmmmmmmmmmmmmm…. maybe not. The line I was following didn’t bear fruit😦

  3. Hi Pete,

    It’s a frustrating problem and I struggled for a long time with the idea that it isn’t a proof. I think the thing is that this way of looking at the progression makes it extremely obvious why there almost certainly is an infinitude of twin primes, so it feels like it must be a proof.

    But look at this sentence: “regardless of how many primes you sieve with, you can never strip away all the twins.” This implies that just because the sieve hasn’t reached a candidate yet, it might be a twin prime or it might not be. But it is a twin or not a twin regardless of the process by which we discover this. So this technique can’t yield a proof until we can prove that there will always be more twins in the region that has been sieved, not that there will always be more in the region that hasn’t.

    What an acceptable proof would need to do would be to absolutely rule out the possibility of future primes “conspiring” in such a way as to to rule out future twin prime candidates. (“Conspiring is a dodgy word as it implies intent, but the point is that one has to prove that this pattern continued up to prime P will always leave some actual twin primes under p^2, not that it will always leave an infinity of future “candidates”.)

    I’ve got a formulation which feels to me to be even stronger than this, based on how the actual twin prime pattern builds – if I get a chance I’ll put it up on my blog. But even though it also feels intuitively like a kind of proof, I don’t think it is mathematically rigorous as a proof either.

    Sorry I’m so verbose, I always seem to say the same thing three different ways.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s