Difference between revisions of "Brun's constant"
Mysmartmouth (talk | contribs) |
m (→Proof of convergence) |
||
(6 intermediate revisions by 5 users not shown) | |||
Line 1: | Line 1: | ||
− | '''Brun's constant''' is the (possibly infinite) sum of [[reciprocal]]s of the [[twin prime]]s <math>\frac{1}{3}+\frac{1}{5}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+\frac{1}{13}+\frac{1}{17}+\frac{1}{19}+\cdots</math>. It turns out that this sum is actually [[convergent]]. Brun's constant is equal to approximately ''' | + | ==Definition== |
+ | |||
+ | '''Brun's constant''' is the (possibly infinite) sum of [[reciprocal]]s of the [[twin prime]]s <math>\frac{1}{3}+\frac{1}{5}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+\frac{1}{13}+\frac{1}{17}+\frac{1}{19}+\cdots</math>. It turns out that this sum is actually [[convergent]]. Brun's constant is equal to approximately '''<math>1.90216058</math>'''. | ||
+ | |||
+ | ==Proof of convergence== | ||
+ | |||
+ | Everywhere below, <math>p</math> will stand for an [[odd integer | odd]] [[prime number]]. Let | ||
+ | <math>\pi_2(x)=\#\{p\le x:p+2\mathrm{\ is\ also\ prime\,}\}</math>. We shall prove that <math>\pi_2(x)\le C\frac{x}{(\ln x)^2}(\ln\ln x)^2</math> for large <math>x</math> with some absolute constant <math>C<+\infty</math>. | ||
+ | The technique used in the proof is a version of the [[Principle of Inclusion-Exclusion]] and is known nowadays as '''Brun's simple pure sieve'''. | ||
+ | ===Lemma=== | ||
+ | Let <math>a_1,\dots,a_n\in[0,1]</math>. | ||
+ | Let <math>\sigma_k=\sum_{1\le i_1<\dots<i_k\le n}a_{i_1}\dots a_{i_k}</math> be the <math>k</math>-th [[symmetric sum]] of the numbers <math>a_1,\dots, a_n</math>. Then | ||
+ | <math>1-\sigma_1+\sigma_2-\dots-\sigma_k\le \prod_{j=1}^n(1-a_j)\le 1-\sigma_1+\sigma_2-\dots+\sigma_\ell</math> for every odd <math>k</math> and [[even integer | even]] <math>\ell</math>. | ||
+ | ====Proof of Lemma==== | ||
+ | Induction on <math>n</math>. | ||
+ | ---- | ||
+ | Now, take a very big <math>x</math> and fix some <math>y\le x</math> to be chosen later. For each odd prime <math>p\le y</math>, let | ||
+ | |||
+ | <math>A_p=\{n\le x:p\mid n\mathrm{\ or\ }p\mid n+2\}</math>. | ||
+ | |||
+ | Clearly, if <math>n>y</math>, and <math>n\in A_p</math> for some <math>p\le y</math>, then either <math>n</math> or <math>n+2</math> is | ||
+ | not prime. Thus, the number of primes <math>q\le x</math> such that <math>q+2</math> is also prime does not exceed | ||
+ | <math>y+\left(x-\left|\bigcup_{p\le y}A_p\right|\right)</math>. | ||
+ | |||
+ | Let now <math>\ell</math> be an even number. By the inclusion-exclusion principle, | ||
+ | |||
+ | <math> \left|\bigcup_{p\le y}A_p\right|\ge | ||
+ | \sum_{p\le y}|A_p|- | ||
+ | \sum_{p_1<p_2\le y}|A_{p_1}\cap A_{p_2}|+ | ||
+ | \sum_{p_1<p_2<p_3\le y}|A_{p_1}\cap A_{p_2}\cap A_{p_3}|- | ||
+ | \dots | ||
+ | - | ||
+ | \sum_{p_1<\dots<p_\ell\le y}|A_{p_1}\cap\dots\cap A_{p_\ell}| | ||
+ | </math> | ||
+ | |||
+ | Let us now estimate <math>|A_{p_1}\cap\dots\cap A_{p_j}|</math>. | ||
+ | Note that the condition <math>n\in A_{p_1}\cap\dots\cap A_{p_j} </math> | ||
+ | depends only on the [[remainder]] of <math>n</math> modulo <math>p_1\cdot\dots\cdot p_j</math> and that, by the [[Chinese Remainder Theorem]], there are exactly <math>2^j</math> | ||
+ | remainders that satisfy this condition (for each <math>p_i\,</math>, we must have <math>n\equiv 0\mod p_i</math> or <math>n\equiv -2\mod p_i</math> and the remainders for different <math>p_i\,</math> | ||
+ | can be chosen independently). Therefore | ||
+ | |||
+ | <math>|A_{p_1}\cap\dots\cap A_{p_j}|=\frac{2^j x}{p_1\cdot\dots\cdot p_j}+R(p_1,\dots,p_j)</math> | ||
+ | |||
+ | where <math>|R(p_1,\dots,p_j)|\le 2^j</math>. | ||
+ | It follows that | ||
+ | |||
+ | <math>x-\left|\bigcup_{p\le y}A_p\right|\le x(1-\sigma_1+\sigma_2-\dots+\sigma_\ell)+y^{\ell}</math> | ||
+ | |||
+ | where <math>\sigma_k</math> is the <math>k</math>-th symmetric sum of the set <math>\left\{\frac 2p:p\le y\right\}</math>. Indeed, we have not more than <math>\left(\frac y2\right)^\ell</math> terms in the inclusion-exclusion formula above and each term is estimated with an error not greater than <math>2^\ell</math>. | ||
+ | |||
+ | Now notice that <math>1-\sigma_1+\sigma_2-\dots+\sigma_\ell= | ||
+ | (1-\sigma_1+\sigma_2-\dots-\sigma_{\ell-1})+\sigma_\ell\le | ||
+ | \prod_{p\le y}\left(1-\frac 2p\right)+\sigma_\ell</math> | ||
+ | by the lemma. | ||
+ | The product does not exceed <math>\prod_{p\le y}\left(1-\frac 1p\right)^2\le\frac {C}{(\ln y)^2}</math> (see the [[prime number]] article), so it remains to estimate <math>\sigma_\ell</math>. But we have | ||
+ | |||
+ | <math>\sigma_\ell\le \frac{1}{\ell!}\left(\sum_{p\le y}\frac 2p\right)^\ell\le\frac 1{\ell!}(2e\ln\ln y)^\ell\le | ||
+ | \left(\frac{2e^2\ln\ln x}{\ell}\right)^\ell | ||
+ | </math>. | ||
+ | |||
+ | This estimate yields the final inequality | ||
+ | |||
+ | <math>\pi_2(x)\le y+ x\left[\frac C{(\ln y)^2} | ||
+ | +\left(\frac {2e^2\ln\ln x}{\ell}\right)^\ell\right]+y^\ell</math>. | ||
+ | |||
+ | It remains to minimize the right hand side over all possible choices of | ||
+ | <math>y</math> and <math>\ell</math>. We shall choose <math>\ell\approx 4e^2\ln\ln x</math> and <math>y=x^{\frac 1{100\ln\ln x}}</math>. With this choice, every term on the right does not exceed <math>C\frac{x}{(\ln x)^2}(\ln\ln x)^2</math> and we are done. |
Latest revision as of 18:48, 12 October 2006
Definition
Brun's constant is the (possibly infinite) sum of reciprocals of the twin primes . It turns out that this sum is actually convergent. Brun's constant is equal to approximately
.
Proof of convergence
Everywhere below, will stand for an odd prime number. Let
. We shall prove that
for large
with some absolute constant
.
The technique used in the proof is a version of the Principle of Inclusion-Exclusion and is known nowadays as Brun's simple pure sieve.
Lemma
Let .
Let
be the
-th symmetric sum of the numbers
. Then
for every odd
and even
.
Proof of Lemma
Induction on .
Now, take a very big and fix some
to be chosen later. For each odd prime
, let
.
Clearly, if , and
for some
, then either
or
is
not prime. Thus, the number of primes
such that
is also prime does not exceed
.
Let now be an even number. By the inclusion-exclusion principle,
Let us now estimate .
Note that the condition
depends only on the remainder of
modulo
and that, by the Chinese Remainder Theorem, there are exactly
remainders that satisfy this condition (for each
, we must have
or
and the remainders for different
can be chosen independently). Therefore
where .
It follows that
where is the
-th symmetric sum of the set
. Indeed, we have not more than
terms in the inclusion-exclusion formula above and each term is estimated with an error not greater than
.
Now notice that
by the lemma.
The product does not exceed
(see the prime number article), so it remains to estimate
. But we have
.
This estimate yields the final inequality
.
It remains to minimize the right hand side over all possible choices of
and
. We shall choose
and
. With this choice, every term on the right does not exceed
and we are done.