Estimating a product over primes (brainfreeze)
 

What's a good way to estimate the product
[TEX]\prod_{p\le x}1-\frac1p[/TEX]?

This comes up all the time, but for some reason I can't think of how it's usually computed. I need this for x too large to calculate directly, probably 10^15 to 10^25.

Oh! what about abusing Mertens' Theorem? Can I approximate it as
[TEX]\prod_{p\le x}1-\frac1p\approx\frac{1}{e^\gamma\log x}[/TEX] for x large?

If this helps at all, Euler's totient function is bounded as such,
[TEX]\frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}} < \varphi(n) < n[/TEX].
Naively, since
[TEX]\frac{1}{n^2} \sum_{t=1}^n \varphi(t)= \frac{3}{\pi^2} + \mathcal{O}\left(\frac{\log n }{n}\right)[/TEX],
[TEX]\frac{1}{n^2} \int_{t=1}^n \varphi(t) \sim \frac{3}{\pi^2} + \mathcal{O}\left(\frac{\log n }{n}\right)[/TEX],
[TEX]\int_{t=1}^n \varphi(t) \sim \frac{3n^2}{\pi^2} + \mathcal{O}\left(n \cdot \log n\right)[/TEX],

[TEX]\varphi(n) \sim \frac{6n}{\pi^2} + \mathcal{O}\left(\log n+1\right) \sim \frac{6n}{\pi^2} + \mathcal{O}\left(\log n \right)[/TEX].
I think my derivation is useless though for practical purposes because [B]a)[/B] either it is false and/or [B]b)[/B] it requires n to be astronomically large for it to apply.

[QUOTE=CRGreathouse;177048]
Oh! what about abusing Mertens' Theorem? Can I approximate it as
[TEX]\prod_{p\le x}1-\frac1p\approx\frac{1}{e^\gamma\log x}[/TEX] for x large?[/QUOTE]

Yes, [URL="http://en.wikipedia.org/wiki/Mertens'_theorems"]Mertens' third theorem[/URL] looks like what you want, and the relative error for a finite sum drops reasonably quickly: for x=10[SUP]7[/SUP] I get 0.001%.

Alex

[QUOTE=flouran;177068]I think my derivation is useless though for practical purposes because [B]a)[/B] either it is false and/or [B]b)[/B] it requires n to be astronomically large for it to apply.[/QUOTE]

(a) is the right choice here, so the formula won't help me. (The quantity I'm looking for tends to 0 as [TEX]x\to\infty.[/TEX])

[QUOTE=akruppa;177075]Yes, [URL="http://en.wikipedia.org/wiki/Mertens'_theorems"]Merten's third theorem[/URL] looks like what you want, and the relative error for a finite sum drops reasonably quickly: for x=10[SUP]7[/SUP] I get 0.001%.[/QUOTE]

Excellent. I started the thread without any idea of how to compute it, but before finishing I came up with that thought. I agree, the error seems very low. Do you know of an asymptotic (or better, a nonasymptotic!) error term/bound?

Edit: [tex]O\left(\frac{1}{\log^2x}\right),[/tex] according to [url=http://projecteuclid.org/euclid.facm/1229624650]Some estimates for the average of the error term of the Mertens product for arithmetic progressions[/url].
Edit2: [tex]O\left(\frac{1}{\log x\,\exp((\log x)^{3/5}(\log\log x)^{-1/5})}\right)=o\left(\frac{1}{\log x\,\exp((\log x)^{3/5-\varepsilon})}\right),[/tex] according to [url=http://dx.doi.org/10.1016/j.jnt.2006.12.015]A note on Mertens' formula for arithmetic progressions[/url]

[QUOTE=CRGreathouse;177101](a) is the right choice here, so the formula won't help me. (The quantity I'm looking for tends to 0 as [TEX]x\to\infty.[/TEX])



Excellent. I started the thread without any idea of how to compute it, but before finishing I came up with that thought. I agree, the error seems very low. Do you know of an asymptotic (or better, a nonasymptotic!) error term/bound?

Edit: [tex]O\left(\frac{1}{\log^2x}\right),[/tex] according to [url=http://projecteuclid.org/euclid.facm/1229624650]Some estimates for the average of the error term of the Mertens product for arithmetic progressions[/url].[/QUOTE]

IIRC, Rosser & Schoenfeld published some explicit error bounds when
they published their estimates for p_n (based on calculation of Zeta
function zeros). Robin may have improved their estimates. The R&S
paper is a classic.

[QUOTE=R.D. Silverman;177104]IIRC, Rosser & Schoenfeld published some explicit error bounds when
they published their estimates for p_n (based on calculation of Zeta
function zeros). Robin may have improved their estimates. The R&S
paper is a classic.[/QUOTE]

I've read Rosser & Schoenfeld, but I don't recall seeing this. I'll look over it again. I'll also look at Robin's paper if I can find a version... though I assume that's in French? Maybe also glance at Dusart's thesis and/or paper, since they cover similar subject matter.

Thanks for the suggestions!

[QUOTE=CRGreathouse;177101](a) is the right choice here, so the formula won't help me. (The quantity I'm looking for tends to 0 as [TEX]x\to\infty.[/TEX])
[/QUOTE]
Yes, I am sorry about that. It was about 3:30 am when I realized I had given you the wrong formula, but I was too tired to post. I initially thought I was dealing with the totient, but I all too sudden realized that
[TEX]\varphi(n) = \prod_{p \mid n} (1-1/p) \ne \prod_{p \le x}(1-1/p)[/TEX]. So no, the formula is not necessarily incorrect for [TEX]\varphi(n)[/TEX], but it is most definitely incorrect for [TEX]\prod_{p \le x}(1-1/p)[/TEX].

CRGreathouse,

Some of the best (recent) work I've found on obtaining explicit bounds is in the papers of Pierre Dusart. For the quantity you are considering, check out page 19 of the article (which is page 21 of the .pdf) found at: [url]http://www.unilim.fr/laco/rapports/1998/R1998_06.pdf[/url]

As for an asymptotic for the error term: that is almost always impossible for the types of quantities under consideration, especially when the error term is already o(1). Even assuming the Riemann hypothesis. Although you might get lucky with Mertens' type products.

Final note: Dusart's bound gives an explicit error term of order [TEX]O\left(\frac{1}{\log(x)^3}\right)[/TEX]

Final note 2: Why did you state that a nonasymptotic bound would be better than an asymptotic? Did you just reverse the words?

Zeta-Flux: Thank you. Fortunately Bob had jarred my memory and I had thought to look up Dusart (who was kind enough, years ago, to send me his doctoral thesis). But I hadn't thought to look up his research report. Thanks for finding that!

[QUOTE=Zeta-Flux;177118]Why did you state that a nonasymptotic bound would be better than an asymptotic? Did you just reverse the words?[/QUOTE]

The meaning I intended was a preference for effective forms like
|f(x) - g(x)| < h(x)
rather than ineffective forms like
f(x) = g(x) + O(h(x)).`

[QUOTE=flouran;177115]Yes, I am sorry about that. It was about 3:30 am when I realized I had given you the wrong formula, but I was too tired to post. I initially thought I was dealing with the totient, but I all too sudden realized that
[TEX]\varphi(n) = \prod_{p \mid n} (1-1/p) \ne \prod_{p \le x}(1-1/p)[/TEX]. So no, the formula is not necessarily incorrect for [TEX]\varphi(n)[/TEX], but it is most definitely incorrect for [TEX]\prod_{p \le x}(1-1/p)[/TEX].[/QUOTE]

At first I couldn't tell why you posted what you did, but then I realized that it could be salvaged with the definition n = x#, whence
[tex]\prod_{p\le x}1-\frac1p=\frac{\varphi(n)}{n}.[/tex]
But the formula is incorrect:
[tex]\lim_{x\to\infty}\prod_{p\le x}1-\frac1p=0[/tex] but
[tex]\frac{6n}{\pi^2}/n=\frac{6}{\pi^2}>0.[/tex]

[QUOTE=Zeta-Flux;177118]Dusart's bound gives an explicit error term of order [TEX]O\left(\frac{1}{\log(x)^3}\right)[/TEX][/QUOTE]

I found the explicit bounds (thanks again!), but I didn't see that. All I saw of that form was Cipolla's classical asymptotic formula for pi(x) on p. 14 (16 in the pdf).