Loading ...
Sorry, an error occurred while loading the content.

Re: GF density

Expand Messages
  • Andrey Kulsha
    Hello! There were more my messages about GF density some weeks ago. I try to show all ideas in this one. Let consider GF(n,b). Let N=2^n, q=2*k*N+1 is prime (k
    Message 1 of 6 , Jan 3, 2002
    • 0 Attachment
      Hello!

      There were more my messages about GF density some weeks ago.
      I try to show all ideas in this one.

      Let consider GF(n,b). Let N=2^n, q=2*k*N+1 is prime
      (k is natural), Euler=0.577215...

      It's known that, given n, exactly N/q GFs are divisible by q. Namely,
      exactly N GFs are divisible by q for every set of q consecutive even b's.

      It's known that the density of primes around x tends to 1/log(x) when
      x->+infinity.

      It's also known that
      lim(x->+infinity, product(p<x, 1-1/p)*log(x)) = 2/exp(Euler),
      where p runs over ODD primes, Euler = 0.577215...

      So, after few minutes of work with pencil, I conjectured that

      C(n) = lim(Q->+infinity, product(q<Q, 1-N/q)*log(Q)*exp(Euler)/2),

      where q runs over primes 2*k*N+1.

      For large n first such k is enough big, so we have
      C(n)~log(N)=n*log(2).

      But if first such k is small, e.g., k=1 for n=15 (there are no more known
      k=1 cases for n>15 because 2^16+1 is the largest known Fermat
      number), we have extremely small C(n): a very large amount of GF(b,n)
      is divisible by these small q's.

      I suggested to use A(n)=C(n)/log(N), so the number of GF primes for
      fixed n and b<B approximately equals to A(n)*li(B)*ln(N)/N.

      Taking about m=10^6 first q's gives good result, the relative error seems
      to be about O[sqrt(N/Q)].

      For example, C(1000)=621.9, A(1000)=0.8963 obtained quickly with
      Q=100000*2^1001.

      Best wishes,

      Andrey
    Your message has been successfully submitted and would be delivered to recipients shortly.