Asymptotics.hpp File Reference

Plans regarding asymptotic estimations. More...

Go to the source code of this file.

Detailed Description

Plans regarding asymptotic estimations.

Estimating the factors in the infinite Grosswald-Hagis-product
  • An estimation for factor_C_gh_inf(k) is needed, so that for a given max_p it can be estimated, how large possibly the contribution of the remaining factors (with p > max_p) could be.
DONE (providing proven intervals containing the true value) Controlling the error of C_gh_hp(k,max_p,decimal_digits)
  • We assume that each rational number is correctly rounded to a bfloat, and that the result of a bfloat-product is correctly rounded.
  • Furthermore we assume the "machine-error", eps, is 10^(-fpprec+1).
  • It seems obvious that all multiplications stay within the normalised range (of bfloat).
  • Then a rather generous upper bound on the absolute value of the relative error is, that with each multiplication to the already established relative error we add 4*eps.
  • Thus, since for C_gh_inf_hp(k,max_p) we perform pi(max_p)-1 multiplications, the absolute value of the relative error for C_gh_inf_hp(k,max_p) is < eps + (pi(max_p)-1)*4*eps.
  • Altogether the relative error for C_gh_hp(k,max_p,decimal_digits) is then less than teps = 5*eps + (pi(max_p)-1)*4*eps = eps * (5 + 4*(pi(max_p)-1)).
  • So C_gh_hp(k,max_p,decimal_digits) should return a pair [r,int], where r is the bfloat-result, while int = [r*(1-teps), r*(1+teps)].
  • We can use pi(max_p) here, since we have available the number of primes <= max_p.
  • This pair-computation should be done by C_gh_inf_hp also.
Improving the Grosswald-Hagis estimation
  • Using the higher logarithmic integrals Lih(x,m) should result in more precise computation --- it should be possible to replace the log's in the denominator of the formula by such higher logarithmic integrals.
  • A first guess is that the factor n^2/log(n)^(k-2)) can be replaced by n * Lih(n,k-2).
  • This is implemented by
    ghLih_nhyp_arithprog_primes_hg(k,n,decimal_digits) :=
      if k-1 > length(C_gh_values) then unknown
      elseif k=3 then bfloat(C_gh_values[k-1])/2/(k-1)*n*Li_hp(n,decimal_digits)
      else bfloat(C_gh_values[k-1])/2/(k-1) * n * Lih_hp(n,k-2,decimal_digits))$
  • A little experiment:
    1. nhyp_arithprog_primes_hg(3,1000) = 40510.
    2. gh_nhyp_arithprog_primes_hg(3,1000) = 47784.1056309392.
    3. float(ghLih_nhyp_arithprog_primes_hg(3,1000,30)) = 58625.55716538247.
    4. Doesn't look encouraging.
    5. The values from the logarithmic integral are bigger than x/log(x)^(k-2), and since the approximation using log's is already too big, it only gets worse.
    6. nhyp_arithprog_primes_hg(5,1000) = 912.
    7. gh_nhyp_arithprog_primes_hg(5,1000) = 1574.23961989466.
    8. float(ghLih_nhyp_arithprog_primes_hg(5,1000,30)) = 4641.782914341983.
    9. So the first guess doesn't look correct.
  • Perhaps things would be different if considering the original formula, which uses parameter x instead of n, where x stands for all primes <= x (while n stands for the number of primes).
  • Using then
    ghorigLih_nhyp_arithprog_primes_hg(k,n,decimal_digits) :=
      if k-1 > length(C_gh_values) then unknown
      else block([p : unrank_primes(n)],
  • The little experiment repeated:
    1. ghorig_nhyp_arithprog_primes_hg(3,1000) = 28613.07161089571.
    2. float(ghorigLih_nhyp_arithprog_primes_hg(3,1000,30)) = 56190.661401401.
    3. ghorig_nhyp_arithprog_primes_hg(5,1000) = 558.1633788252357.
    4. float(ghorigLih_nhyp_arithprog_primes_hg(5,1000,30)) = 13317.17349502113.
    5. Doesn't look right, at least not for the small n we are considering.

Definition in file Asymptotics.hpp.