Slashdot Mirror
Researcher Modifies Sieve of Eratosthenes To Work With Less Physical Memory Space (scientificamerican.com)
grcumb writes: Peruvian mathematician Harald Helfgott made his mark on the history of mathematics by solving Goldbach's weak conjecture, which states that every odd number greater than 7 can be expressed as the sum of three prime numbers. Now, according to Scientific American, he's found a better solution to the sieve of Eratosthenes: "In order to determine with this sieve all primes between 1 and 100, for example, one has to write down the list of numbers in numerical order and start crossing them out in a certain order: first, the multiples of 2 (except the 2); then, the multiples of 3, except the 3; and so on, starting by the next number that had not been crossed out. The numbers that survive this procedure will be the primes. The method can be formulated as an algorithm." But now, Helfgott has found a method to drastically reduce the amount of RAM required to run the algorithm: "Now, inspired by combined approaches to the analytical 100-year-old technique called the circle method, Helfgott was able to modify the sieve of Eratosthenes to work with less physical memory space. In mathematical terms: instead of needing a space N, now it is enough to have the cube root of N." So what will be the impact of this? Will we see cheaper, lower-power encryption devices? Or maybe quicker cracking times in brute force attacks? Mathematician Jean Carlos Cortissoz Iriarte of Cornell University and Los Andes University offers an analogy: "Let's pretend that you are a computer and that to store data in your memory you use sheets of paper. If to calculate the primes between 1 and 1,000,000, you need 200 reams of paper (10,000 sheets), and with the algorithm proposed by Helfgott you will only need one fifth of a ream (about 100 sheets)," he says.
I already read the link a few hours before it was posted. There was zero details on the algorithm and no link to the actual research that I could see.
Well, in case you are interested, after checking around, it appears that this "algorithm" was a minor result of Mr. Helfgott's work to prove the ternary Goldbach conjecture (every odd integer n greater than 5 is the sum of three primes). Here's the preprint of the paper, I should warn you that it appears to be a very theoretical paper, one targetted at the Goldbach conjecture (not practical prime sieving), so there is not a fully fleshed out algorithm that you can translate into a computer program. I haven't gone through the paper in detail, but it appears to rely heavily on technique from a Messr. Ramare.
We start by adapting ideas from Ramare’s version of the large sieve for primes to estimate l2 norms over parts of the circle. We are left with the task
of giving an explicit bound on the factor in Ramare’s work. As a side effect, this finally gives a fully explicit large sieve for primes that is asymptotically optimal, meaning a sieve that does not have a spurious factor of exp(gamma) in front; this was an arguably important gap in the literature.
I cannot find a definitive paper about this technique, but is appears to be related to this earlier paper. Mr. Helfgott apparently just tightening the bounds which theoretically should create a better sieve algorithm. My impression is that I think it will take some concerted effort to create a computer algorithm out of this algorithm.
However, your mileage may vary...
I was about to post something longer, but my computer deleted it at just the right moment. Summary: (a) The origin of this article was an interview given at an algebra colloquium in Buenos Aires a few weeks ago. Its appearance in Scientific American was a little unexpected (to me). I should be able to post a preprint soon. (b) In my colloquium talk, I made sure to mention that I had just come across a precedent in the literature: W. F. Galway, Dissecting a sieve to cut its need for space. In Algorithmic number theory (Leiden, 2000), vol 1838 of Lecture Notes in Comput. Sci., pages 297-312. Springer, Berlin, 2000. In both cases, we are talking about space essentially O(N^(1/3)) and time essentially O(N). Galway improves on the Atkin-Bernstein sieve, which is specifically about producing lists of primes. The sieve of Eratosthenes can be used for more general purposes, e.g., producing lists of factorizations or computing tables of values of arithmetic functions that depend on factorization. I actually got interested in the problem while using a sieve to produce successive values of mu(n), where mu is the Moebius function. As far as I can tell, there's a basic underlying idea being used in both cases, viz. Diophantine approximation. In brief, if you are finding primes (or what have you) in an interval [N,N+N^(1/3)], you do not have to sieve by every m=sqrt(N); you can tell in advance which integers m will have no multiples in that interval. This is all more or less orthogonal to [http://sweet.ua.pt/tos/software/prime_sieve.html]. Indeed what I do and what Oliveira e Silva does can very likely be combined. Best Harald Helfgott