From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Function Estimation Date: 2 Jul 1998 20:18:48 GMT In article <6n8our$pkk$1@nnrp1.dejanews.com>, wrote: >I am looking for a good estimate to the following function. > >Let N be a real number greater than (say) 10. > >What is a good approximation to: > >Product over primes p < N of log_p(N)? > >Where log_p(N) is the log of N base p. > >Let y = II log_p(N) > p < N > p prime > >Then log(y) = sum log( log_p(N)) > p < N > p prime How good do you need it to be? Some rough heuristics suggest the value of log(y) is about C N / log(N)^2 where C is around 1. I guess I would break up the sum into parts, summing separately over those p in an interval [N^(1 - 1/k), N^(1 - 1/(k+1))], taking k from 1 to log(N) or so. In each interval there are about pi(N^...) - pi^(N^...) summands, each nearly equal: each term is, for some eps in (0, 1), equal to log(log_p(N)) = log(log(N)/log(N^(1 - 1/(k+eps)))) = -log(1-1/(k+eps)) which is about 1/k for large k. The last interval would need to sum over all the primes in [N^(1-1/log(N)), N], i.e., in [N/e, N]. There are about (N/log(N))*(1-1/e) primes in here, each contributing a sum at most equal to 1/log(N), so this interval contributes about (N/log(N)) * ((1-1/e)*log(N)). (Actually, breaking this interval down into more parts, e.g. the primes in [N/sqrt(e), N] and [N/e, N/sqrt(e)] separately, allows us to reduce that initial constant, but this last interval contributes a minimum of at least (1/9)N/(log(N))^2 Now we check the contributions of the primes in the other intervals. Using pi(x) ~ x/log(x) the number of summands for the k-th interval is about (N/log(N)) * {- N^(-1/k) * (k/(k-1)) + N^(-1/(k+1)) * (k+1)/k } So we may approximate the original sum by a sum from 1 to log(N) of a rather messy product of expressions involving k. (In what follows, I will remove the common factor of N/log(N) .) For large N, each of the first few terms is swamped by the succeeding ones. Since this is a heuristic argument anyway I'll therefore just ignore the behaviour of the first few intervals. Accord this the appropriate confidence. To check the size of the other summands, set m=log(N) and x=k/m; then we want to consider the size of the m summands for various x in [0,1], as functions of m. Using the taylor series around infinity, I find the size of the summand to be about exp(-1/x)/x^3 * (1/m^2) + exp(-1/x)(2x^2-1)/x^5 *(1/m^3) + ... so that the summand is largest for x=1/3 (k = log(M)/3) at about 1.34/m^2 and dies off slowly from there; even at x=m, it's still around (1/e)*(1/m^2). Thus the tail of my sum is roughly (1/m) times a Riemann sum (with m intervals) approximating integral_0^1 exp(-1/x)/x^3, which is 2/e. So these summands add together to give about (2/e)*(1/log(N)). Combining with the sum over primes greater than N/e as computed earlier gives an estimated sum of (1 + 1/e)*(1/log(N)) which, together with the common factor of N/log(N) we have been ignoring, gives log(y) ~ C * N/( log(N) )^2 . for some constant C which I estimate to be between 1/9 and 4/3. dave ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Function Estimation Date: 2 Jul 1998 22:07:07 GMT In article <6n8our$pkk$1@nnrp1.dejanews.com>, wrote: >I am looking for a good estimate to the following function. I posted a followup, but I think one can do this a little more cleanly, in the style of Montgomery's post. It certainly seems to be true that the function evaluates to very nearly N/( log(N) )^2. >We can turn this into a Stieltje's integral: > >Integral from 2 to N of log ( log(N)/log(x)) d [ pi(x)] > >where pi(x) counts primes from 2 to x. > >However, integrating this by parts and then substituting pi(x) ~ x/log(x) >leads to a mess. Can anyone suggest a way of estimating this integral as a >function of N (asymptotically)? Better to use d[pi(x)] = 1/log(x) * dx. I'll combine this with the effect of the substitutions I used in the post. Here are the Maple commands > f:=log(log(N)/log(x)); #function to be evaluated at primes > f/log(x); #integrand in Stieltje's integral using pi(x)=Li(x) > subs(N=exp(m),"); #avoid exponentiation, using exp instead > subs(x=exp(m-1/y),")*diff(exp(m-1/y),y); # A change of variable combining ideas in the post I made. # This is the new integrand, including the change from dx to dy. # to get x=2..N requires y=(something nearly 0)..(infinity) > "/(exp(m)/m^2); #Reduce the integrand by this factor, as we expect #the answer to be (roughly const)*N/log(N)^2 > f2:=simplify(",symbolic); 2 (ln(m) - ln(m y - 1) + ln(y)) m exp(- 1/y) f2 := ------------------------------------------- (m y - 1) y #Wish I could integrate this from 0 to infinity directly to get the #"constant", but it's not integrable in closed form. To get an asymptotic #expression converging for large m, get the Taylor series at infinity > subs(m=1/n,"); > f5:=ln(1/(1-n/y))*exp(-1/y)/n/y^2/(1-n/y); #Need to help Maple a bit... > simplify(""-",symbolic); 0 #phew! > taylor(f5,n,7); #Individual terms _are_ integrable in closed form. exp(- 1/y) exp(- 1/y) exp(- 1/y) 2 25 exp(- 1/y) 3 ---------- + 3/2 ---------- n + 11/6 ---------- n + -- ---------- n + [etc] 3 4 5 12 6 y y y y > int(",y=0..infinity): > subs(n=1/m,"); 11 50 274 1764 13068 1 1 + 3/m + ---- + ---- + --- + ---- + ----- + O(----) 2 3 4 5 6 7 m m m m m m [The coefficients are the Stirling numbers of the first kind. See entry A000254 in Sloane's tables.] So it looks like the sum in question is about N/(log(N))^2 + 3 N/(log(N))^3 + 11 N/(log(N))^4 + ... The first 5 terms give values for N=10^4 or N=2*10^4 which are accurate to 1%, but of course this is cheating a little since we have an infinite series with all terms positive and the numerators rising faster than geometrically, just as the expansion Li(x) = integral dx/log(x) = x/logx + x/(logx)^2 + ... + (n-1)! x/(logx)^n +... is "good but bogus". Indeed, by analogy with the development of that series, I suppose the integral \int_0^\infty f_5 dy can be done by parts any desired number of times leaving another, similar integral unevaluated, but which for specific values of m may be easily bounded, leaving only the first few terms of the series shown. dave