Re: primes as far as the eye can see, discrete continua
copied under fair use only because Roy put in the research... NUMBER THEORY: Proof Promises Progress in Prime Progressions Barry Cipra The theorem that Ben Green and Terence Tao set out to prove would have been impressive enough. Instead, the two mathematicians wound up with a stunning breakthrough in the theory of prime numbers. At least that's the preliminary assessment of experts who are looking at their complicated 50-page proof. Green, who is currently at the Pacific Institute for the Mathematical Sciences in Vancouver, British Columbia, and Tao of the University of California (UC), Los Angeles, began working 2 years ago on the problem of arithmetic progressions of primes: sequences of primes (numbers divisible only by themselves and 1) that differ by a constant amount. One such sequence is 13, 43, 73, and 103, which differ by 30. In 1939, Dutch mathematician Johannes van der Corput proved that there are an infinite number of arithmetic progressions of primes with three terms, such as 3, 5, 7 or 31, 37, 43. Green and Tao hoped to prove the same result for four-term progressions. The theorem they got, though, proved the result for prime progressions of all lengths. "It's a very, very spectacular achievement," says Green's former adviser, Timothy Gowers of the University of Cambridge, who received the 1998 Fields Medal, the mathematics equivalent of the Nobel Prize, for work on related problems. Ronald Graham, a combinatorialist at UC San Diego, agrees. "It's just amazing," he says. "It's such a big jump from what came before." Green and Tao started with a 1975 theorem by Endre Szemeridi of the Hungarian Academy of Sciences. Szemeridi proved that arithmetic progressions of all lengths crop up in any positive fraction of the integers--basically, any subset of integers whose ratio to the whole set doesn't dwindle away to zero as the numbers get larger and larger. The primes don't qualify, because they thin out too rapidly with increasing size. So Green and Tao set out to show that Szemeridi's theorem still holds when the integers are replaced with a smaller set of numbers with special properties, and then to prove that the primes constitute a positive fraction of that set. Prime suspect. Arithmetic progressions such as this 10-prime sequence are infinitely abundant, if a new proof holds up. To build their set, they applied a branch of mathematics known as ergodic theory (loosely speaking, a theory of mixing or averaging) to mathematical objects called pseudorandom numbers. Pseudorandom numbers are not truly random, because they are generated by rules, but they behave as random numbers do for certain mathematical purposes. Using these tools, Green and Tao constructed a pseudorandom set of primes and "almost primes," numbers with relatively few prime factors compared to their size. The last step, establishing the primes as a positive fraction of their pseudorandom set, proved elusive. Then Andrew Granville, a number theorist at the University of Montreal, pointed Green to some results by Dan Goldston of San Jose State University in California and Cem Yildirim of Bo_gazigi University in Istanbul, Turkey. Goldston and Yildirim had developed techniques for studying the size of gaps between primes, work that culminated last year in a dramatic breakthrough in the subject--or so they thought. Closer inspection, by Granville among others, undercut their main result (Science, 4 April 2003, p. 32; 16 May 2003, p. 1066), although Goldston and Yildirim have since salvaged a less far-ranging finding. But some of the mathematical machinery that these two had set up proved to be tailor-made for Green and Tao's research. "They had actually proven exactly what we needed," Tao says. The paper, which has been submitted to the Annals of Mathematics, is many months from acceptance. "The problem with a quick assessment of it is that it straddles two areas," Granville says. "All of the number theorists who've looked at it feel that the number-theory half is pretty simple and the ergodic theory is daunting, and the ergodic theorists who've looked at it have thought that the ergodic theory is pretty simple and the number theory is daunting." Even if a mistake does show up, Granville says, "they've certainly succeeded in bringing in new ideas of real import into the subject." And if the proof holds up? "This could be a turning point for analytic number theory," he says.
So the obvious question is, does this speed up the cracking capabilities of computers? On the surface, I'd say no, but then again I'm no computational science expert. (I say no because any of the primes used in X-bitlength encryption are already known, and these strings of primes aren't going to be used any more frequently than any random batch of primes.) -TD
From: "Major Variola (ret)" <mv@cdc.gov> To: "cypherpunks@al-qaeda.net" <cypherpunks@al-qaeda.net> Subject: Re: primes as far as the eye can see, discrete continua Date: Wed, 08 Dec 2004 21:37:52 -0800
copied under fair use only because Roy put in the research...
NUMBER THEORY: Proof Promises Progress in Prime Progressions
Barry Cipra
The theorem that Ben Green and Terence Tao set out to prove would have been impressive enough. Instead, the two mathematicians wound up with a stunning breakthrough in the theory of prime numbers. At least that's the preliminary assessment of experts who are looking at their complicated 50-page proof.
Green, who is currently at the Pacific Institute for the Mathematical Sciences in Vancouver, British Columbia, and Tao of the University of California (UC), Los Angeles, began working 2 years ago on the problem of arithmetic progressions of primes: sequences of primes (numbers divisible only by themselves and 1) that differ by a constant amount. One such sequence is 13, 43, 73, and 103, which differ by 30.
In 1939, Dutch mathematician Johannes van der Corput proved that there are an infinite number of arithmetic progressions of primes with three terms, such as 3, 5, 7 or 31, 37, 43. Green and Tao hoped to prove the same result for four-term progressions. The theorem they got, though, proved the result for prime progressions of all lengths.
"It's a very, very spectacular achievement," says Green's former adviser, Timothy Gowers of the University of Cambridge, who received the 1998 Fields Medal, the mathematics equivalent of the Nobel Prize, for work on related problems. Ronald Graham, a combinatorialist at UC San Diego, agrees. "It's just amazing," he says. "It's such a big jump from what came before."
Green and Tao started with a 1975 theorem by Endre Szemeridi of the Hungarian Academy of Sciences. Szemeridi proved that arithmetic progressions of all lengths crop up in any positive fraction of the integers--basically, any subset of integers whose ratio to the whole set doesn't dwindle away to zero as the numbers get larger and larger. The primes don't qualify, because they thin out too rapidly with increasing size. So Green and Tao set out to show that Szemeridi's theorem still holds when the integers are replaced with a smaller set of numbers with special properties, and then to prove that the primes constitute a positive fraction of that set.
Prime suspect. Arithmetic progressions such as this 10-prime sequence are infinitely abundant, if a new proof holds up.
To build their set, they applied a branch of mathematics known as ergodic theory (loosely speaking, a theory of mixing or averaging) to mathematical objects called pseudorandom numbers. Pseudorandom numbers are not truly random, because they are generated by rules, but they behave as random numbers do for certain mathematical purposes. Using these tools, Green and Tao constructed a pseudorandom set of primes and "almost primes," numbers with relatively few prime factors compared to their size.
The last step, establishing the primes as a positive fraction of their pseudorandom set, proved elusive. Then Andrew Granville, a number theorist at the University of Montreal, pointed Green to some results by Dan Goldston of San Jose State University in California and Cem Yildirim of Bo_gazigi University in Istanbul, Turkey.
Goldston and Yildirim had developed techniques for studying the size of gaps between primes, work that culminated last year in a dramatic breakthrough in the subject--or so they thought. Closer inspection, by Granville among others, undercut their main result (Science, 4 April 2003, p. 32; 16 May 2003, p. 1066), although Goldston and Yildirim have since salvaged a less far-ranging finding. But some of the mathematical machinery that these two had set up proved to be tailor-made for Green and Tao's research. "They had actually proven exactly what we needed," Tao says.
The paper, which has been submitted to the Annals of Mathematics, is many months from acceptance. "The problem with a quick assessment of it is that it straddles two areas," Granville says. "All of the number theorists who've looked at it feel that the number-theory half is pretty simple and the ergodic theory is daunting, and the ergodic theorists who've looked at it have thought that the ergodic theory is pretty simple and the number theory is daunting."
Even if a mistake does show up, Granville says, "they've certainly succeeded in bringing in new ideas of real import into the subject." And if the proof holds up? "This could be a turning point for analytic number theory," he says.
participants (2)
-
Major Variola (ret) -
Tyler Durden