From: Bob Silverman Subject: Re: Goldbach's Conjecture Date: Wed, 19 Jul 2000 18:19:41 GMT Newsgroups: sci.math Summary: [missing] In article , "Gary Shannon" wrote: > Given the probabilisitc argument that it is highly unlikely that an amateur > would have found a proof to to Goldbach's conjecture on his first try, I > must assume that my supposed proof of the conjecture is flawed. > > However, the proof I think I may have found is very short and very simple, > (a page of high school level algebra) and I can't seem to find what the flaw > is. I would deeply appreciate help in finding the assumed flaw. > > In brief outline, the proof begins by contructing pairs of numbers which sum > to 2N; > > (1, 2N-1), (2, 2N-2), ... (N,N). > > I then apply the sieve of Eratosthenes, modified in such a way as to sieve > for both members of each pair. Excellent so far. It is very refreshing to see a truly interested amateur apply excellent judgment in approaching the problem, as opposed to the many cranks we see. Applause. However, there are two problems. (1) The sieve of Eratosthene's is too weak a sieve to produce a full proof. You need to look up a paper by DeBruijn entitled something like "On the Number of Cancelled Elements in the Sieve of Eratosthenes". (2) Chen, in proving that 2N = p1 + p2 where p1 is prime and p2 is the product of at most two primes used a weighted, modified form of the sieve of Eratosthenes known as the "large sieve". The difficulty with proof by sieve methods is known as the "parity problem". With respect to Chen's result, the parity problem means that after conducting the sieve you are left with one prime plus a number which has either one or two prime factors and you can't tell which because of uncertainty/error in the sieve. An elementary explanation follows: How many integers less than N are divisible by 3? The answer is you can't tell! The answer depends on N mod 3. Now ask the same for 5,7,11, ... e.g. there are 33 numbers divisible by 3 less than 100, but the same is true for N = 101. If one asks how many integers less than N are divisible by all primes up to say N^epsilon for epsilon bounded away from 0, there is a fair amount of error in the estimate. This is known as the fundamental lemma of the sieve. > I then show that after enough sievings have been performed to insure that > all surviving pairs consist of only primes, that there have not been > sufficient sievings to strike out all pairs, that that at least one pair > must survive. There must be an error in your argument, because this has not been possible. There is too much uncertainty in knowing how many numbers have been struck out You have run into something really DEEP. For more info see: Halberstam & Richert, "Sieve Methods" Let me show this problem from another perspective. The probability that a large integer N is prime is the probability that it is not divisible by 2,3,5,7,11...sqrt(N). This probability is (1-1/2) * (1-1/3) * (1-1/5) .... which, by Merten's theorem is very close to exp(-gamma)/log( sqrt(n)) ~ 2 exp(-gamma)/log(n). But 2 exp(-gamma) isn't 1 while the prime number *theorem* says this must be 1. What is wrong? The problem is that once you have enough primes so that their product exceeds N, the probability that the next prime does or doesn't divide is no longer independent of the probability that the previous primes did or did not divide N. They "get in each other's way". Now a weighted sieve can correct for this for PNT; but so far noone has found a way to remove the "inter-dependence" in applying sieves to Goldbach. This is imprecise, but it conveys the ideas. -- Bob Silverman "You can lead a horse's ass to knowledge, but you can't make him think" Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: Bob Silverman Subject: Re: OK - then has Brun's (double) sieve been proved to work? Date: Tue, 17 Oct 2000 01:56:30 GMT Newsgroups: sci.math In article <8sg7e6$fpi$1@nnrp1.deja.com>, freelancefabulous@my-deja.com wrote: > There seems to be unanimity about Eratosthenes' Sieve working if you > can stand the boredom of using it and are not trrying to find the > world's largest prime except theoretically. What about Brun's "double" > sieve? Same story? No flame intended, but you seem confused. (1) The Eratosthenes sieve does indeed work and can be easily proved correct when using it to find prime numbers. The complexity of the sieve computations is a *separate* issue from whether the sieve works. But the sieve may be used for purposes OTHER than just finding primes. One such is identifying all integers lying in a interval that are divisible by a prime that lies in some fixed set. And it works very well for such a purpose. There is another context, however, in which this sieve does NOT work; that is the general context of using combinatorial sieves to estimate arithmetic counting functions. See a book on "Sieve Methods"; Halberstam & Richert's, for example. This sieve does not work in this context because it is too weak to make useful estimates. DeBruijn wrote a paper "On the number of uncalled elements in the sieve of Eratosthenes" which explains why. (2) There are sieves other than Eratosthenes which do work in estimating arithmetic counting functions; Brun's sieve was used to proved that the density of twin primes is sufficiently rare that their sum converges. It was too weak, however, to prove whether there are infinitely many twin primes. Brun's sieve and Eratosthene's sieve really have nothing to do with one another; they are used for different purposes. There are other sieves; Bombieri's, Montgomery's "Large Sieve", etc. etc. Your confusion seems to be the assumption that Brun's sieve and the Eratosthenes sieve are similar in purpose. Example of a "counting function": Estimate the number of integers less than x, for suitably large x that are the sum of an integer with exactly 3 prime factors and an integer that is the sum of exactly 4 prime factors. (3) Note that there is still another class of sieves: Sieve Algorithms. These are used for yet another purpose: identifying smooth numbers for the purpose of factoring large integers or computing discrete logs. The one common feature of all of these is that each takes "steps" along fixed or variable length "strides" within a set of integers in a way that identifies some particular property of the numbers that are "hit" by the sieve. Sometimes the hits are "weighted". -- Bob Silverman "You can lead a horse's ass to knowledge, but you can't make him think" Sent via Deja.com http://www.deja.com/ Before you buy.