Estimating a product over primes (brainfreeze)

CRGreathouse · 2009-06-11, 04:50

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

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
$\prod_{p\le x}1-\frac1p\approx\frac{1}{e^\gamma\log x}$ for x large?

flouran · 2009-06-11, 08:20

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

$\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)$ .
I think my derivation is useless though for practical purposes because a) either it is false and/or b) it requires n to be astronomically large for it to apply.

akruppa · 2009-06-11, 09:18

Quote:

Originally Posted by CRGreathouse

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

Yes, Mertens' third theorem looks like what you want, and the relative error for a finite sum drops reasonably quickly: for x=10⁷ I get 0.001%.

Alex

CRGreathouse · 2009-06-11, 14:22

Quote:

Originally Posted by flouran

I think my derivation is useless though for practical purposes because a) either it is false and/or b) it requires n to be astronomically large for it to apply.

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

Quote:

Originally Posted by akruppa

Yes, Merten's third theorem looks like what you want, and the relative error for a finite sum drops reasonably quickly: for x=10⁷ I get 0.001%.

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: $O\left(\frac{1}{\log^2x}\right),$ according to Some estimates for the average of the error term of the Mertens product for arithmetic progressions.
Edit2: $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),$ according to A note on Mertens' formula for arithmetic progressions

R.D. Silverman · 2009-06-11, 14:41

Quote:

Originally Posted by CRGreathouse

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

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: $O\left(\frac{1}{\log^2x}\right),$ according to Some estimates for the average of the error term of the Mertens product for arithmetic progressions.

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.

CRGreathouse · 2009-06-11, 14:59

Quote:

Originally Posted by R.D. Silverman

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.

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!

flouran · 2009-06-11, 15:52

Quote:

Originally Posted by CRGreathouse

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

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
$\varphi(n) = \prod_{p \mid n} (1-1/p) \ne \prod_{p \le x}(1-1/p)$ . So no, the formula is not necessarily incorrect for $\varphi(n)$ , but it is most definitely incorrect for $\prod_{p \le x}(1-1/p)$ .

Zeta-Flux · 2009-06-11, 16:01

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: http://www.unilim.fr/laco/rapports/1998/R1998_06.pdf

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 $O\left(\frac{1}{\log(x)^3}\right)$

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

CRGreathouse · 2009-06-11, 17:44

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:

Originally Posted by Zeta-Flux

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

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)).`

CRGreathouse · 2009-06-11, 17:50

Quote:

Originally Posted by flouran

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
$\varphi(n) = \prod_{p \mid n} (1-1/p) \ne \prod_{p \le x}(1-1/p)$ . So no, the formula is not necessarily incorrect for $\varphi(n)$ , but it is most definitely incorrect for $\prod_{p \le x}(1-1/p)$ .

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
$\prod_{p\le x}1-\frac1p=\frac{\varphi(n)}{n}.$
But the formula is incorrect:
$\lim_{x\to\infty}\prod_{p\le x}1-\frac1p=0$ but
$\frac{6n}{\pi^2}/n=\frac{6}{\pi^2}>0.$

CRGreathouse · 2009-06-11, 18:11

Quote:

Originally Posted by Zeta-Flux

Dusart's bound gives an explicit error term of order $O\left(\frac{1}{\log(x)^3}\right)$

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).

2009-06-11, 04:50	#1
CRGreathouse Aug 2006 3×1,993 Posts	Estimating a product over primes (brainfreeze) What's a good way to estimate the product $\prod_{p\le x}1-\frac1p$ ? 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 $\prod_{p\le x}1-\frac1p\approx\frac{1}{e^\gamma\log x}$ for x large?

2009-06-11, 08:20	#2
flouran Dec 2008 1101000001₂ Posts	If this helps at all, Euler's totient function is bounded as such, $\frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}} < \varphi(n) < n$ . Naively, since $\frac{1}{n^2} \sum_{t=1}^n \varphi(t)= \frac{3}{\pi^2} + \mathcal{O}\left(\frac{\log n }{n}\right)$ , $\frac{1}{n^2} \int_{t=1}^n \varphi(t) \sim \frac{3}{\pi^2} + \mathcal{O}\left(\frac{\log n }{n}\right)$ , $\int_{t=1}^n \varphi(t) \sim \frac{3n^2}{\pi^2} + \mathcal{O}\left(n \cdot \log n\right)$ , $\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)$ . I think my derivation is useless though for practical purposes because a) either it is false and/or b) it requires n to be astronomically large for it to apply. Last fiddled with by flouran on 2009-06-11 at 09:12

2009-06-11, 16:01	#8
Zeta-Flux May 2003 60B₁₆ Posts	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: http://www.unilim.fr/laco/rapports/1998/R1998_06.pdf 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 $O\left(\frac{1}{\log(x)^3}\right)$ Final note 2: Why did you state that a nonasymptotic bound would be better than an asymptotic? Did you just reverse the words? Last fiddled with by Zeta-Flux on 2009-06-11 at 16:11

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Product of consecuative terms in subsets of primes is 1 (mod ab)	carpetpool	Miscellaneous Math	1	2017-02-25 16:08
Estimating the number of primes in a partially-factored number	CRGreathouse	Probability & Probabilistic Number Theory	15	2014-08-13 18:46
Estimating minimum relations	bchaffin	Factoring	24	2012-03-24 18:37
Estimating a sum over primes	brownkenny	Math	6	2010-08-25 01:28
Estimating an infinite product over primes	CRGreathouse	Math	10	2010-07-23 20:47