Difference between revisions of "Brun's constant"

Latest revision as of 17:48, 12 October 2006

Definition

Brun's constant is the (possibly infinite) sum of reciprocals of the twin primes $\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$ . It turns out that this sum is actually convergent. Brun's constant is equal to approximately $1.90216058$ .

Proof of convergence

Everywhere below, $p$ will stand for an odd prime number. Let $\pi_2(x)=\#\{p\le x:p+2\mathrm{\ is\ also\ prime\,}\}$ . We shall prove that $\pi_2(x)\le C\frac{x}{(\ln x)^2}(\ln\ln x)^2$ for large $x$ with some absolute constant $C<+\infty$ . 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 $a_1,\dots,a_n\in[0,1]$ . Let $\sigma_k=\sum_{1\le i_1<\dots<i_k\le n}a_{i_1}\dots a_{i_k}$ be the $k$ -th symmetric sum of the numbers $a_1,\dots, a_n$ . Then $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$ for every odd $k$ and even $\ell$ .

Proof of Lemma

Induction on $n$ .

Now, take a very big $x$ and fix some $y\le x$ to be chosen later. For each odd prime $p\le y$ , let

$A_p=\{n\le x:p\mid n\mathrm{\ or\ }p\mid n+2\}$ .

Clearly, if $n>y$ , and $n\in A_p$ for some $p\le y$ , then either $n$ or $n+2$ is not prime. Thus, the number of primes $q\le x$ such that $q+2$ is also prime does not exceed $y+\left(x-\left|\bigcup_{p\le y}A_p\right|\right)$ .

Let now $\ell$ be an even number. By the inclusion-exclusion principle,

$\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}|$

Let us now estimate $|A_{p_1}\cap\dots\cap A_{p_j}|$ . Note that the condition $n\in A_{p_1}\cap\dots\cap A_{p_j}$ depends only on the remainder of $n$ modulo $p_1\cdot\dots\cdot p_j$ and that, by the Chinese Remainder Theorem, there are exactly $2^j$ remainders that satisfy this condition (for each $p_i\,$ , we must have $n\equiv 0\mod p_i$ or $n\equiv -2\mod p_i$ and the remainders for different $p_i\,$ can be chosen independently). Therefore

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

where $|R(p_1,\dots,p_j)|\le 2^j$ . It follows that

$x-\left|\bigcup_{p\le y}A_p\right|\le x(1-\sigma_1+\sigma_2-\dots+\sigma_\ell)+y^{\ell}$

where $\sigma_k$ is the $k$ -th symmetric sum of the set $\left\{\frac 2p:p\le y\right\}$ . Indeed, we have not more than $\left(\frac y2\right)^\ell$ terms in the inclusion-exclusion formula above and each term is estimated with an error not greater than $2^\ell$ .

Now notice that $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$ by the lemma. The product does not exceed $\prod_{p\le y}\left(1-\frac 1p\right)^2\le\frac {C}{(\ln y)^2}$ (see the prime number article), so it remains to estimate $\sigma_\ell$ . But we have

$\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$ .

This estimate yields the final inequality

$\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$ .

It remains to minimize the right hand side over all possible choices of $y$ and $\ell$ . We shall choose $\ell\approx 4e^2\ln\ln x$ and $y=x^{\frac 1{100\ln\ln x}}$ . With this choice, every term on the right does not exceed $C\frac{x}{(\ln x)^2}(\ln\ln x)^2$ and we are done.

@@ Line 5: / Line 5: @@
 ==Proof of convergence==
-Everywhere below <math>p</math> will stand for an odd [[prime number]]. Let
+Everywhere below, <math>p</math> will stand for an [[odd integer | odd]] [[prime number]]. Let
-<math>\pi_2(x)=\#\{p: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>.
+<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 [[PIE|inclusion-exclusion principle]] and is known nowadays as '''Brun's simple pure sieve'''.
+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====
+===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 <math>\ell</math>.
+<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
+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|n\mathrm{\ or\ }p|n+2\}</math>
+<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
@@ Line 57: / Line 57: @@
 <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>
+</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>
++\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.

Page

Toolbox

Search