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.

Claims and Proofs

It appears that many of the statements made in a recent linked post had little to no proof to back them up. Let’s try to give some extra details here…

The first couple sections don’t seem to have very many claims, or the claims present are either cited or reasonably-well shown.  Starting with section 3.3, there is the “single-function version” of the Twin Primes sieve, and there is very little in the way of proof for the statements made.

– Claim 1: x-1 and x+1 can represent a twin prime pair

  • proof: the twin primes are those pairs of primes having an absolute difference of 2, so p and p+2 or p and p-2 are common representations of these primes.  Adding 1 to each of p, p-2 or subtracting one from each of p, p+2 yields p-1, p+1, and changing the letter designation has no effect

– Claim 2: the smaller of two factors a, b of a number n can be no larger than the square root of n

  • proof: if a and b are factors of a number n such that a * b = n, then this is true, since if a and b are both larger than sqrt(n), then we have (sqrt(n)+q)*(sqrt(n)+r) = sqrt(n)*sqrt(n)+sqrt(n)(q+r)+q+r = n+sqrt(n)(q+r)+q+r.  So this claim would be true if it were clarified to apply only to when a*b=n

The rest of this section is hand-waving until we get to the end:

– Claim 3: all twin prime pairs get missed by the sieve represented by the function f(s,t)=(s+1)(s^2+s+t-1)

  • proof: let x-1, x+1 be given such that both are prime, and suppose that there exist an s and t such that x^2-1=(s+1)(s^2+s+t-1).  Then we have that s+1 must divide either x-1 or x+1.  Since s and t are positive integers, s+1 is never greater than s^2+s+t-1, which means that s+1 must divide x-1; since x-1 is prime and s+1 must be greater than 1, this forces that s+1=x-1, and that s+3 = x+1 and thus that s+3=s^2+s+t-1.  Continuing the algebra, we get s^2+t=4.  The only positive integer solutions here are s=1 and t=3, giving us the values x-1=2, x+1=4.  These are not a twin prime pair, contradicting our assumption that there are twin prime pairs which are picked up by the sieve.

– Claim 4: s+1 goes through every possible factor

  • proof: the not-clearly-stated claim here is that there are no pairs of integers with at least one composite which are different by 2 such that the sieve (s+1)(s^2+s+t-1) does not catch them, so assume that there is an x with either x-1 or x+1 non-prime such that for all positive integers s and t, (s+1)(s^2+s+t-1) does not equal x^2-1.  First, suppose that x-1 is non-prime with factors a,b where a*b = x-1 such that 1 is less than a is less than b.  Let s+1=a, then we have s^2+2s+1 = a^2 and s^2+s+t-1 = a^2-a+t-1.  But t can be any positive integer, and a^2-a-1 must be less than b*(x+1) since a is less than b and a is less than x+1, therefore s=a-1, t = b*(x+1)-a^2+a+1 is a solution and the sieve does catch this pair.  The same argument applies when x+1 is the composite number.

Section 3.4 appears to be hand-waving statements again, and does not appear to directly affect the primary claims in later sections.  Section 4.1 starts with a citation, and the algebra to change (2a+1)(2b+1) =/= 2k+1 into 2ab+a+b =/= k is very straightforward.  Then there is more hand-waving, and we are shown a related sieve for the twin primes.  There is another unspoken claim here:

– Claim 5: s^3+2s^2+st+t =/= 4x^2 if and only if 2s^3+2s^2+2st+t =/= x^2

  • proof: the given statement that (s+1)(s^2+s+t-1)=x^2-1 has the same odd-even parity as (s+1)(t-1)=x^2-1 is trivially true; it takes only a short leap to notice that x^2-1 has the same parity as x-1, giving us the form of the odd-even theorem

Section 4.2 has more hand-waving, and the side track of the so-called “modular images“.  It seems that these could be interesting, but all the details have been completely glossed over.  Section 5.1 begins with some more interesting things:

– Claim 6: when a_1 from a_1b_1+a_1+b_1 and a_2 from 2a_2b_2+a_2+b_2 are such that a_1+1=2a_2+1, then the count of numbers “sieved away” by a_1b_1+a_1+b_1 within a finite interval can be at most one different from the count of numbers “sieved away” by 2a_2b_2+a_2+b_2

  • proof: let a=a_1+1=2a_2+1, then we have arithmetic sequences ab_1+a-1 and ab_2+/-[(a+1)/2].  Then a-1 is greater than +/-[(a+1)/2] modulo a.  By the pigeonhole principle, among every a numbers a-1 is one of those numbers and [(a+1)/2] is another.  These are arithmetic sequences, so the a-1 value and the [(a+1)/2] value each always occur in the same location within each a consecutive integers.  Given finite interval [q,ra+s] for positive integers q,r,s, one of a-1, [(a+1)/2] occurs “first” within the interval, then the two congruence classes alternate in appearance until the end of the interval.  This alternating appearance causes there to never be more than a difference of 1 in the count of members of each congruence class appearing within a given interval

– Claim 7: there is no need to evaluate the count of results which are common to both sieves

  • proof: this claim should be self-evident given that the differences in the counts are being explicitly evaluated

– Claim 8: a_1+1=2 gives a naive result count of 2^(m-1)

  • proof: the interval length was identified (straightforward) as 2^m, and our sieve is currently limited to a_1=1 which “sieves away” every other number, either all the evens or all the odds.  Since the sieve offset is a_1, it is all the odds that are “sieved away”, and since an even number of consecutive integers contains an equal number of even and odd numbers, the number that we have “sieved away” is exactly half of the length of the interval, which is 2^(m-1) in this case

– Claim 9: the bound on the number of sequences which produce appropriate results is given by 2a_2+1<sqrt(2^(m+1))

  • proof: if we continue with the assumption that 2a_2+1 is the smaller of the factors of a hypothetical odd composite number, then we can consider that if q is the larger factor, then there was some a_2 such that (2a_2+1)q is the value of this composite number, and this number was already “sieved away” by this value of a_2.  In a prior claim it was established that the smaller factor is no larger than the square root of the original number, and in this case, the original number is even while the factor is odd, meaning that the factor cannot be the square root of the number, and therefore must be strictly less than the square root

Next there is a line about “determining whether this mapping is onto”, and right up until the end, it isn’t clear which sieve’s results provide the domain and which provide the range, up until the end of the paragraph where it appears that the (a_1+1) sieve’s results are mapping onto results from the (2a_2+1) sieve.

– Claim 10: the non-overlaps correspond to the set of primes from the previous interval multiplied by 2

  • proof: any composites from the previous interval must have at least one factor less than the square root of the endpoint of the current interval, meaning that such a factor would also be involved in a sieve arithmetic sequence that overlaps with some value in the a_1+1=2 arithmetic sequence.  The set of primes within the previous interval were missed by all arithmetic sequences, and therefore the multiples of two of each of these primes are now missed by these same sequences within the current interval

The number of primes within a given interval, while not necessarily accurate by the n/log n estimate, should be fairly close by the prime number theorem.  Then there is more hand-waving about having proven the infinity of primes by using a result that already shows there is an infinite number of primes.  This statement assumes that the claims highlighted here are plainly evident to the reader, and that the flow of an induction should be an understood part of the narrative.  If the induction were to be stated explicitly, we would need the “first element” bound prior to finding a first example, so this part makes sense why it would appear so long after many claims and statements.  The next piece would be the inductive step.  The text seems to imply that the inductive step relies on the “odd-even theorem” and the fact that a result in one sieve directly corresponds to a result in another sieve, then that the “onto” mapping implies that this same result implies the existence of a new result in the first sieve.  In short, “have a first one; if one is at hand, prove there is one after it.”

– Claim 11: s^2 == 1 mod s+1 and s^2 == +/-[(s+1)/2] mod 2s+1

  • proof: s == -1 mod s+1, and (-1)^2 == 1 mod k for all k > 0.  For the other result, consider whether s is odd or even with s=2t or s=2u-1: (2t)^2 == -t mod 4t+1, and (2u-1)^2 = 4u^2-4u+1 == u mod 4u-1

– Claim 12: by claim 11 we know that each sieve covers two numbers per consecutive p numbers when a_1+1=p and 2a_2+1=p

  • proof: this claim would be false unless p were taken as prime.  With prime p we know that there are at most two solutions to the congruence x^2 == a mod p, and as each congruence from the previous claim begins as a square, we know that there exist two solutions x in each of the congruences x^2 == 1 mod s+1 and x^2 == +/- [(s+1)/2] mod 2s+1, keeping in mind that the expression +/-[(s+1)/2] mod 2s+1 is only referring to a single congruence class, chosen based on the value of s^2 mod 2s+1

– Claim 13: claim 12 together with claim 11 means that the count of results per prime could be absolutely different by 2

  • proof: using the same logic as with a prior claim, there are a maximum of four results per consecutive p numbers in a single arithmetic sequence, and two are from each of the two sieves, showing that there can be a maximum difference in the result counts of 2

The arithmetic counting the number of squares in a given interval is straightforward.  The upper bound identified on s is also straightforward, having the same form as before.  The count of “extras”, being no more than the number of possible values of s multiplied by the maximum result count difference, is straightforward as well.  The formula for the count of non-overlaps in the s_1+1=2 arithmetic sequence is short on details, but really only needs to specify a few more primes to establish the pattern, as 2^(n-1) * (1-2/3)*(1-2/5)*(1-2/7)*…

– Claim 14: the count of non-overlapped values appearing in the arithmetic sequence identified by (s_1+1)(s_1^2+s_1+t_1-1)=x^2-1 where s_1+1=2 within the specified interval is given by 2^(n-1) * (1-2/3)*(1-2/5)*(1-2/7)*…

  • proof:  if 2^(n-1) is the count of results from s_1+1=2, then we can multiply by 1-2/3 to get the count that does not overlap with the results from s_1+1=3 since there are two results per p consecutive values for each prime p.  Then we can multiply by 1-2/5 to get the count that also does not overlap with the results from s_1+1=5, and we can continue through each prime in this way.  Since we only sieve over the prime numbers, we never need to consider whether there are extra solutions to our congruence x^2 == s^2 mod {s+1, 2s+1}

The “accounting for extras” bit seems like it is unnecessary due to the manner in which the overlaps are counted, but it makes the 4^((n+4)/3) term work out a bit more cleanly, and this term is not reduced by this accounting, so it should be okay.  The evaluation of the product should be straightforward given the citation, and we are only left needing to prove that the constants work out in the manner described.  Fortunately, said constants provide a near 4:1 ratio against the other numerator and denominator terms, making the bound 2^(n-1)/(n+1)^2 entirely appropriate.  With this done, the entire section is complete with the caveats listed above.

The rest of the content hand-waves through with a passing “the rest of the details are left as an exercise” and other similar statements.  We’ll save those for next time.