3
$\begingroup$

I'm working on a proof in number theory, and have encountered a proof. If I include the proof, I can show that as some numbers tends to infinity, they follow a certain rule. Unfortunately, this is not precise enough, so I have set up an inequality. This is the limit:

$$\lim \limits_{n \to \infty} g \cdot \left(1-(1-\prod_{i=1}^n (1-\frac{1}{p_i}))\right)$$

and know that it tends to $0$. In this case, $p_i$ are the prime numbers, and $g$ is any number in-between $p_{n}+1 $ and $p_{n+1} -1$. I would like to know at which n the expression is less than $1$. In other words/symbols:

$$\lim_{n \to \infty} g \cdot \left(1-(1-\prod_{i=1}^n (1-\frac{1}{p_i}))\right) < 1.$$ I've written a short bit of code in Python and had it reviewed on Code Review. Since I've tried numbers up to 100 million and did not reach a number less than $1$, I would like to know whether there is some mathematical of arriving at the result, or whether my limit is just wrong. Thanks!

$\endgroup$
12
  • $\begingroup$ And $p_i$ is prime numbers? $\endgroup$ Commented Dec 21, 2016 at 22:50
  • $\begingroup$ @SimpleArt Yes, thanks for recommending the clarification. $\endgroup$ Commented Dec 21, 2016 at 22:51
  • 1
    $\begingroup$ Well, Mertens proved that $$\lim_{x\to \infty} (\log x)\prod_{p \leqslant x}\biggl(1 - \frac{1}{p}\biggr) = e^{-\gamma}.$$ And $\dfrac{n}{\log p_n} \to +\infty$. $\endgroup$ Commented Dec 21, 2016 at 23:13
  • 1
    $\begingroup$ @Momo "The first $n$ prime numbers" are "the primes not exceeding the $n$-th prime number". Hence we have the product $\prod\limits_{p \leqslant p_n} \bigl(1 - \frac{1}{p}\bigr)$. $\endgroup$ Commented Dec 21, 2016 at 23:20
  • 2
    $\begingroup$ @LinusRastegar It does. And Mertens' third theorem says how fast. You get a finite nonzero limit if $g \sim \log p_n$. $\endgroup$ Commented Dec 21, 2016 at 23:37

1 Answer 1

1
$\begingroup$

A counter proof ... I feel like stealing the answer from Daniel Fischer, but here is evidence I knew about Mertens' theorem before. To avoid any further doubts:

$$ g \cdot \left(1-\left(1-\prod_{i=1}^n \left(1-\frac{1}{p_i}\right)\right)\right) \geq (p_{n}+1)\cdot \prod_{i=1}^n \left(1-\frac{1}{p_i}\right)=$$ $$=\frac{p_{n}+1}{\ln{(p_n+1)}}\cdot \ln{(p_n+1)} \cdot \prod_{i=1}^n \left(1-\frac{1}{p_i}\right)=$$ $$=\frac{p_{n}+1}{\ln{(p_n+1)}}\cdot e^{-\gamma} \cdot \frac{\ln{(p_n+1)} \cdot \prod_{i < p_n+1} \left(1-\frac{1}{p_i}\right)}{e^{-\gamma}}>$$ $$>\frac{p_{n}+1}{\ln{(p_n+1)}}\cdot e^{-\gamma} \cdot (1-\varepsilon)$$ starting with some $n$ for some $\varepsilon$ (from the definition of limit). The latter goes to $\infty$.

Another way (to add some creativity from me) is to exploit this result: $$\liminf_{n \rightarrow \infty} \varphi(n)\cdot \frac{\ln{\ln{n}}}{n}=e^{-\gamma}$$ where $$\prod_{i=1}^n \left(1-\frac{1}{p_i}\right)=\frac{\varphi\left(\prod_{i=1}^n p_i\right)}{\prod_{i=1}^n p_i}$$ so that $$g \cdot \left(1-\left(1-\prod_{i=1}^n \left(1-\frac{1}{p_i}\right)\right)\right) \geq (p_{n}+1)\cdot \prod_{i=1}^n \left(1-\frac{1}{p_i}\right)=(p_{n}+1)\cdot \frac{\varphi\left(\prod_{i=1}^n p_i\right)}{\prod_{i=1}^n p_i}=$$ $$=\frac{p_{n}+1}{\ln{\ln{\left(\prod_{i=1}^n p_i\right)}}}\cdot \varphi\left(\prod_{i=1}^n p_i\right) \cdot \frac{\ln{\ln{\left(\prod_{i=1}^n p_i\right)}}}{\prod_{i=1}^n p_i}>$$ considering the definition of $\liminf$ $$>\frac{p_{n}+1}{\ln{\ln{\left(\prod_{i=1}^n p_i\right)}}} \cdot (1-\varepsilon) \cdot e^{-\gamma}=$$ (from some $n$ onwards of course) $$=\frac{p_{n}+1}{\ln{\left(\sum_{i=1}^n \ln{p_i}\right)}} \cdot (1-\varepsilon) \cdot e^{-\gamma} > \frac{p_{n}+1}{\ln{\left(n\cdot \ln{p_n}\right)}} \cdot (1-\varepsilon) \cdot e^{-\gamma}=\frac{p_{n}+1}{\ln{n} + \ln{\ln{p_n}}} \cdot (1-\varepsilon) \cdot e^{-\gamma}$$ which again is easy to see it goes to $\infty$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .