Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The Green-Tao Theorem states that for any natural number k, there exist k-term arithmetic progressions of primes. Suppose this were not true.

Then there must exist a minimum k such that there are no k-term arithmetic progressions of primes. So if a-(k-2)b,a-(k-3)b,...,a-2b,a-b,a is a (k-1)-term arithmetic progression of primes and a>(k-1)b, then c=a-(k-1)b cannot be prime. Notice that we have determined that c is not prime without knowing anything about the factors of c. This is impossible since the factors of c determine whether c is prime or not. Hence, the Green-Tao theorem must be true.

Where is the flaw in this proof?

share|improve this question

closed as off topic by Pete L. Clark, Jonas Meyer, Mariano Suárez-Alvarez, Akhil Mathew, J. M. Dec 23 '10 at 4:16

Questions on Mathematics Stack Exchange are expected to relate to math within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

"It is still impossible to determine whether or not an integer is prime without having any information about the factors of the integer": This is not mathematics. –  Nate Eldredge Dec 22 '10 at 20:22
Here's a reductio ad absurdum of the claim in dispute, which is quoted above by Nate Eldredge: [We use the claim to prove that every number >1 is prime. Suppose not, then there is a least number n>1 which is not prime. According to the claim, this cannot be the case without information about the factors of n, which we do not have. Thus, every number >1 is prime.] We know this is false, so there must be something wrong with the claim. –  Jonas Kibelbek Dec 22 '10 at 20:57
The statement I quoted is not even mathematically meaningful, so it cannot possibly be a valid proof. Specifically, you have not made precise what it means to "have information about" something. If you could do so, in a way that's traceable to the axioms of set theory, then we could discuss whether or not the quoted statement was true. However, it is probably a waste of time, because I think it is going to be false in any case. –  Nate Eldredge Dec 22 '10 at 21:04
@Craig: "we have determined that c is not prime without proving that there are other factors of c besides c and 1." Now you're just being ridiculous. You're making an assumption and then marveling at how you could possibly know the thing you assumed. I suppose you would also prove infinitude of twin primes as follows. Suppose there were only finitely many twin primes; say they're all less than 10^100. Take any two consecutive odd numbers bigger than 10^100, and we've proven that one of them is not prime without proving it has a proper factor. Impossible! –  Anton Geraschenko Dec 22 '10 at 23:34
@Craig Feinstein: Because you are still putting forward nonsense without taking into account the thoughtful replies that others have taken the time to write, I am the second vote to close as "off topic". –  Jonas Meyer Dec 23 '10 at 2:18

2 Answers 2

Use [false-proof] or whatever the tag is to ask about proofs whose flaws are the subject of discussion. This would help prevent the impression of claiming an easy 3-sentence proof of a result that took 40 pages and decades of prior work.

The logic is identical, but leads to a false conclusion, if you replace "prime" by "not divisible by $k$". Given a $(k-1)$-term arithmetic progression [with difference having no factor in common with $k$] of not-divisible-by-k integers, its extension to a $k$ term progression has to have the last term divisible by $k$, even though we were given no divisibility information in advance about that last term. The difference between this and the Green-Tao theorem is that sometimes a string of $(k-1)$ primes can be extended to a string of $k$, and sometimes not. There is a relationship between the first $(k-1)$ items and the $k$th one, but it is more statistical in nature.

The Green-Tao proof, loosely speaking, does use the logic you outlined, but in a statistical, on-average sense. A deterministic guarantee that any $k$ term progression can't have all terms primes (so e.g., if the first (k-1) are prime the last cannot be) would create too much correlation, too much "shared information" about the prime factorization of the different terms. There are theorems in analytic number theory saying that there is at least a certain amount of pseudorandomness in the primes and in the prime factorizations of integers, and knowing in advance that every string of $(k-1)$ primes in progression cannot be extended to $k$ would enforce too high a degree of structure. The reason 40 pages of cutting-edge analytic number theory and Fourier analysis are needed, is to convert the simple heuristics about "information" and "correlation" into provable and well-defined mathematical assertions, which is complicated because the primes themselves are deterministically defined, not a sequence of random numbers to which the probabilistic concepts most naturally apply.

share|improve this answer
-1: For the statement: "The Green-Tao proof, loosely speaking, does use the logic you outlined". No, the logic used by OP is something totally different. The problem OP has is: "We got a prime without getting any information about its factors. Impossible". +1 for information about Green-Tao proof and trying to address OP's flaw (albeit in just a few sentences as compared to the rest of the answer), so a net 0. –  Aryabhata Dec 23 '10 at 0:53
@Moron -- I thought the second paragraph had just addressed the OP's "something for nothing" issue. There's indirect information about the K'th thing in the previous (K-1) things. Or if I tell you the sum of 99 distinct integers between 1 and 100, you know the identity of the missing one, without having been told it directly. –  T.. Dec 23 '10 at 1:00
Dear T.., I very much like the example in the second paragraph, which brings home the flaw in the reasoning perfectly. Also, this is a nice philosophical summary of the Green-Tao argument as well. Regards, –  Matt E Dec 23 '10 at 1:13
@Matt E: if I and the other users were to itemize all the analogous "we very much like it" material in your postings it would jam the comment threads due to volume, but there is presumably an enormous appreciation of those expositions beyond what the votes and comments directly indicate. I especially liked the recent one explaining the view of adeles as a solenoidal, Fourier-analytic universal covering space. Thanks and I hope you continue here and on MO. –  T.. Dec 23 '10 at 1:47
I don't think the example "if you replace "prime" by "not divisible by $k$" contradicts the puzzle-proof above, because to make it work, you have to add the condition "with difference having no factor in common with $k$". This condition implies something about the factors of the $k$th item. The puzzle-proof above has no such condition. Sorry, but I don't think anyone has solved the puzzle. All people have done is make declarations that the puzzle is not "mathematical". –  Craig Feinstein Dec 23 '10 at 17:48

The problem is in the claim "Notice that we have determined that c is not prime without proving that there are other factors of c besides c and 1. This is impossible."

The absence of knowledge is not the knowledge of absence. If you actually show that c has no other factors than 1 and c, you would have a contradiction to c being composite. But I hope you will agree that you haven't shown that; you just note that you don't know anything specific about other factors.

By definition, "determining that c is not prime" = "determining that c has other factors than 1 and c." The definition of prime numbers is simple, but the study of prime numbers is a deep and active part of mathematics. It involves many long and (initially) mysterious arguments. One nice thing about theorems is that you don't have to think about all of the details of the proof to use the result-- if you cite any theorem about prime numbers, you know something about the factors or non-factors of the numbers involved.

In your example argument, you assume that no k-term arithmetic progression of primes exists. Then you automatically know that the terms preceding and following a k-1 term progression of primes are composite, because of your assumption. In other words, your attempted proof doesn't actually do anything-- you assume something and never get anything more than the assumption you started with.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.