20080107, 05:14  #1 
Tribal Bullet
Oct 2004
DD9_{16} Posts 
A surprising result on QS/NFS matrix size
This paper, if I read it correctly, claims that for the quadratic sieve with a factor base containing L primes, collecting L^x relations is enough to produce a nontrivial linear dependency with high probability, for x > 1/e.
I didn't think this was possible; the above says you only need a number of relations equal to about the cube root of the factor base size before expecting a dependency. The model doesn't assume handling large primes, and maybe that spoils everything in the real world, but it still sounds too good to be true. The paper says it's an inappropriate model for the quadratic sieve, but I can't see why... This apparently started out as some kind of undergrad research project, which noticed something resembling the above via computational experiment. 
20080107, 08:44  #2  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
11,299 Posts 
Quote:
The ROT works extremely well, but 0.8 is substantially larger than 1/e. If the claim was for 11/e for the exponent (about 0.63) the claim would be quite plausible, IMO. The ROT allows leeway for discarding excessively heavy relationsets. Pauil 

20080107, 14:20  #3  
Tribal Bullet
Oct 2004
5·709 Posts 
Quote:
Last fiddled with by jasonp on 20080107 at 14:22 

20080107, 20:23  #4 
Mar 2003
79 Posts 
If I correctly understand the paper in the first link, it seems to say that if a matrix is built using the probability function that they list then it is likely to have a significant number of nonzero columns.
The function they chose gives the nth prime a 1/p chance of appearing in the nth column. So as a concrete example, bits in column 78498 have only a oneinamillion chance of being set. As a result it is not surprising that the resulting matrices have an extraordinary number of columns that are all zero and can be eliminated, thereby reducing the number of rows required. This almost feels like complicated route arriving at the Prime Number Theorem ("the chance of a number N being prime is about 1 / ln(N), where ln(N) denotes the natural logarithm of N"). Don Last fiddled with by dleclair on 20080107 at 20:25 Reason: tpyo 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A surprising case of a new shiny thing being stepfunction better  fivemack  Astronomy  12  20170124 17:49 
Xyzzy, the man, the myth, the surprising but not disappointing reality  jasong  jasong  6  20160426 22:41 
Interesting but not surprising pointintime stats  petrw1  PrimeNet  3  20150901 19:35 
A bug or... a surprising result???...  lycorn  PrimeNet  20  20110626 19:52 
Surprising news headlines  dsouza123  Soap Box  2  20070626 21:41 