AoPSWiki

Trying to get to the USAMO in 2010? Our AIME Problem Series can help you get there! Click here to enroll today!

Personal tools

Search

Toolbox

Brun's constant

From AoPSWiki

Revision as of 22:48, 12 October 2006 by JBL (Talk | contribs)

(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)

Contents

1 Definition
2 Proof of convergence
- 2.1 Lemma
  - 2.1.1 Proof of Lemma

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

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

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.

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/Brun%27s_constant"

Looking for a challenging geometry text? Preparing for MATHCOUNTS or the AMC exams? Check out Art of Problem Solving's Introduction to Geometry by Richard Rusczyk.

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us