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.

Functional Encoding of Images

Given a source of data in k-dimensional form, it is possible to construct a modular function which represents the data.

For example, let k=2.  It is possible to take any image with any color depth and write a function which generates the image by supplying coordinates as the parameters of the function.  Here is a simple “image”, shown as color values at coordinate locations:

x \ y | 0 1 2 3 4


0      | 1 1 1 1 1

1      | 1 0 0 0 1

2      | 1 0 0 0 1

3      | 1 0 0 0 1

4      | 1 1 1 1 1

Using a prime modulus is the only way to ensure that the entire image can be encoded correctly; this modulus applies both to the “color depth”, i.e., the range of values that can appear at each coordinate location, and to the “width” and “height” of the image created by the function.

The “image” shown above can be encoded to a function as follows:

For a 5×5 image with all “colors” having value <= 5, use 5 as the modulus.  To get zeroes in the center, use (x-1)(x-2)(x-3)(y-1)(y-2)(y-3).  The remaining challenge is to force the outer ring to be all ones.  If x=0 or x=4, then (x-1)(x-2)(x-3) is -6 or +6, which is -1 or +1 mod 5.  Similarly, if y=0 or y=4, then (y-1)(y-2)(y-3) is -1 or +1 mod 5.  So the simplest solution is to square our previous result, which will force all values to 1 mod 5:

f(x,y) = ((x-1)(x-2)(x-3)(y-1)(y-2)(y-3))^2 (mod 5) is the 5×5 square with boundary size 1.

Clearly this was a very simple image to create a function for, but it serves to demonstrate the basic principles in operation.  It is also probably obvious that expanding this polynomial to coefficient-exponent form will yield some terms with exponent > 4, which can be reduced modulo 5.

Non-prime moduli can be used, but it may be more difficult or in many cases impossible to generate arbitrary images.

One usage for this particular approach to images is as a tiling procedure; since the basic operation is “modulus” there is no need to “copy and paste” to create a tiling effect, the image will simply repeat naturally as a consequence of the function.