Patterns of Proofs of Infinity

At the core, the concept of infinity relies on the fact that no matter how many numbers we have, there’s always at least one more. This is formally expressed in the principle of induction.

Induction is the first and most widely-used method of proving that there is an infinite amount of some thing. Strong induction is a sub-pattern, where all the things that we have so far are taken together to show that there must be one we don’t have yet. Strong induction is the method used by Euclid to show there are infinitely many primes: take all the primes we have, multiply them all together, and add one to the result. This number must be relatively prime to all of those we have, and therefore its prime factors are not among those we already had, so we add these prime factors to our list. Now we are at the beginning again, and this process can be repeated indefinitely.

Another pattern is to “acknowledge the properties of a set.” Consider the set of Fermat numbers, defined by F_n = 2^2^n+1.  Each member of this set of numbers (for non-negative n) is pairwise relatively prime with all the others, and this property is relatively easy to prove.  At once we can see that if we consider the set of prime factors of all of the Fermat numbers, these must also be pairwise relatively prime with each other, and therefore they are all distinct.  We can immediately follow up by noting that there are an infinite number of Fermat numbers (as many as there are non-negative integers), and therefore an infinite number of primes.

Still another pattern is to show that the set of numbers we are considering has a count that is bounded below by a given sum, and then follow by showing that this sum goes to infinity.  This is the pattern used by Dirichlet in the proof that every arithmetic progression ax+b with (a,b)=1 and a=/=0 contains an infinite number of primes.

The pattern used by the recent proof that there are infinitely many twin prime pairs is a complicated sub-pattern of induction.  It is possible to argue that all proofs of infinity are sub-patterns of induction, but some are more immediate descendants than others.  This pattern uses the following logic:

  • Two functions f,g:Z^2 to Z+ with f having range A and g having range B are given with the following properties:
    1. Given u in Z+, we have |A^[u+1, 2u]|>=|B^[u+1,2u]|
    2. there exist a,b in Z : f(a,b) = 2x if and only if there exist c,d in Z : g(c,d) = x
    3. there exists z in Z+ : for all a,b in Z, f(a,b) =/= z
  • Property (1) allows half of an induction.  Property (2) allows the other half, where we can jump from one interval to the next one that is doubled (and non-overlapping).  Property (3) says that we can start the induction.

Other patterns that were attempted in the making of the twin primes theorem proof include making an “arrangement” of the known primes and their congruence classes around certain numbers to prove that examples can exist; creating “lattices” of integer-valued polynomials to offer comparisons between similar polynomials; showing that for all polynomials of the same degree having the same number of polynomial factors and constant factors, there exists one example in the “positive-x” direction.

This last attempt may continue to be a viable option.  It uses standard induction, but instead of being given a starting point, the starting point is “continuously created.”  In particular, if f(x) is a given polynomial where for a value x_0 > 0, f(x_0) produces an “example”, then g(x)=f(x_0+x) is also a polynomial.  If we have proven that all polynomials “similar” to f(x) have “examples” in the positive-x direction, and if we prove that this g(x) is “similar” to f(x), then we know that there exists x_1 > x_0 such that g(x_1)=f(x_0+x_1) is an example.  This particular approach has not borne fruit as of yet, but continues to show promise.