20090823, 21:29  #1 
(loop (#_fork))
Feb 2006
Cambridge, England
6,323 Posts 
Counting duplicates
I'm wondering what can sensibly be done to predict the number of duplicate relations that a large sieve run will produce.
My initial attempt ignores the fact that lattices are involved, and make the false assumption that sieving with some specialQ gives all the relations from some Platonic fixed set of relations which have that Q dividing the polynomial value. In which case, to estimate the number of unique relations that you'd get sieving from Q0 to Q1, sieve short intervals at q=Q0, q=(Q0+Q1)/2, q=Q1epsilon, measuring sieving time, and then either * count only relations containing no factor between q+1 and Q1. * count relations with one factor between Q0 and Q1 as having weight 1, relations with two factors as weight 1/2, with three as weight 1/3 ... This gets you a uniqueyieldperqrange figure at three points, and you integrate it by the trapezium rule; also integrate the rawyieldperq and the sievetimeperq that you have measured, because that's easy, and the sieve time gives some idea how long the full run will take. Measuring the timings means this does account for large Q taking longer than small Q; on the other hand, a large Q does sample a significantly larger space: I sieved ranges R1=25M..25M+10k and R2=75M..75M+10k, there was one relation Z in R1 with a factor in R2, and five relations in R2 with a factor in R1 (obviously including the relation Z). So this technique gives an underestimate of the number of unique relations, which isn't terribly helpful. I have enormous amounts of data from many large sieving jobs to play with; what should I do next? 
20090824, 02:26  #2 
Tribal Bullet
Oct 2004
3·1,163 Posts 
Maybe you should contact Arjen Lenstra or Joppe Bos; IIRC they are studying the prediction problem. Willemein Ekkelkamp published a paper at ANTS 8 that developed accurate estimates for line sieving to find enough relations, assuming no duplicates, but I don't know if she's still working in this area.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A counting problem  jasonp  Puzzles  1  20171224 19:38 
Path Counting  henryzz  Puzzles  13  20140917 11:21 
Counting ECM work twice  alpertron  PrimeNet  1  20091201 23:33 
Counting on Fingers  Orgasmic Troll  Lounge  3  20051231 22:22 
counting bricks  michael  Puzzles  8  20040114 16:27 