Brun sieve

Last updated March 15, 2023

In the field of number theory, the Brun sieve (also called Brun's pure sieve) is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences. It was developed by Viggo Brun in 1915 and later generalized to the fundamental lemma of sieve theory by others.

Description

In terms of sieve theory the Brun sieve is of combinatorial type; that is, it derives from a careful use of the inclusion–exclusion principle.

Let $A$ be a finite set of positive integers. Let $P$ be some set of prime numbers. For each prime $p$ in $P$ , let $A_{p}$ denote the set of elements of $A$ that are divisible by $p$ . This notation can be extended to other integers $d$ that are products of distinct primes in $P$ . In this case, define $A_{d}$ to be the intersection of the sets $A_{p}$ for the prime factors $p$ of $d$ . Finally, define $A_{1}$ to be $A$ itself. Let $z$ be an arbitrary positive real number. The object of the sieve is to estimate:

S(A,P,z)={\biggl \vert }A\setminus \bigcup _{p\in P \atop p\leq z}A_{p}{\biggr \vert },

where the notation $|X|$ denotes the cardinality of a set $X$ , which in this case is just its number of elements. Suppose in addition that $|A_{d}|$ may be estimated by

\left\vert A_{d}\right\vert ={\frac {w(d)}{d}}|A|+R_{d},

where $w$ is some multiplicative function, and $R_{d}$ is some error function. Let

W(z)=\prod _{p\in P \atop p\leq z}\left(1-{\frac {w(p)}{p}}\right).

Brun's pure sieve

This formulation is from Cojocaru & Murty, Theorem 6.1.2. With the notation as above, suppose that

$|R_{d}|\leq w(d)$ for any squarefree $d$ composed of primes in $P$ ;
$w(p)<C$ for all $p$ in $P$ ;
There exist constants $C,D,E$ such that, for any positive real number $z$ , $\sum _{p\in P \atop p\leq z}{\frac {w(p)}{p}}<D\log \log z+E.$

Then

S(A,P,z)=X\cdot W(z)\cdot \left({1+O\left((\log z)^{-b\log b}\right)}\right)+O\left(z^{b\log \log z}\right)

where $X$ is the cardinal of $A$ , $b$ is any positive integer and the $O$ invokes big O notation. In particular, letting $x$ denote the maximum element in $A$ , if $\log z<c\log x/\log \log x$ for a suitably small $c$ , then

S(A,P,z)=X\cdot W(z)(1+o(1)).

Applications

Brun's theorem: the sum of the reciprocals of the twin primes converges;
Schnirelmann's theorem: every even number is a sum of at most $C$ primes (where $C$ can be taken to be 6);
There are infinitely many pairs of integers differing by 2, where each of the member of the pair is the product of at most 9 primes;
Every even number is the sum of two numbers each of which is the product of at most 9 primes.

The last two results were superseded by Chen's theorem, and the second by Goldbach's weak conjecture ( $C=3$ ).

Related Research Articles

In mathematics, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs. The theorem was proved independently by Jacques Hadamard and Charles Jean de la Vallée Poussin in 1896 using ideas introduced by Bernhard Riemann.

In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no square number other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, 10 = 2 ⋅ 5 is square-free, but 18 = 2 ⋅ 3 ⋅ 3 is not, because 18 is divisible by 9 = 3². The smallest positive square-free numbers are

In mathematics, the $p$ -adic number system for any prime number $p$ extends the ordinary arithmetic of the rational numbers in a different way from the extension of the rational number system to the real and complex number systems. The extension is achieved by an alternative interpretation of the concept of "closeness" or absolute value. In particular, two $p$ -adic numbers are considered to be close when their difference is divisible by a high power of $p$ : the higher the power, the closer they are. This property enables $p$ -adic numbers to encode congruence information in a way that turns out to have powerful applications in number theory – including, for example, in the famous proof of Fermat's Last Theorem by Andrew Wiles.

<span class="mw-page-title-main">Euler's totient function</span> Number of integers coprime to and not exceeding n

In number theory, Euler's totient function counts the positive integers up to a given integer $n$ that are relatively prime to $n$ . It is written using the Greek letter phi as $or, and may also be called Euler's phi function . In other words, it is the number of integers k in the range 1 \leq k \leq n for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n .$

In mathematics and computer science, the floor function is the function that takes as input a real number $x$ , and gives as output the greatest integer less than or equal to $x$ , denoted $⌊ x ⌋$ or $floor(x)$ . Similarly, the ceiling function maps $x$ to the least integer greater than or equal to $x$ , denoted $⌈ x ⌉$ or $ceil(x)$ .

In additive number theory, the Schnirelmann density of a sequence of numbers is a way to measure how "dense" the sequence is. It is named after Russian mathematician Lev Schnirelmann, who was the first to study it.

<span class="mw-page-title-main">Divisor function</span> Arithmetic function related to the divisors of an integer

In mathematics, and specifically in number theory, a divisor function is an arithmetic function related to the divisors of an integer. When referred to as the divisor function, it counts the number of divisors of an integer. It appears in a number of remarkable identities, including relationships on the Riemann zeta function and the Eisenstein series of modular forms. Divisor functions were studied by Ramanujan, who gave a number of important congruences and identities; these are treated separately in the article Ramanujan's sum.

In number theory, an n-smooth (or n-friable) number is an integer whose prime factors are all less than or equal to n. For example, a 7-smooth number is a number whose every prime factor is at most 7, so 49 = 7² and 15750 = 2 × 3² × 5³ × 7 are both 7-smooth, while 11 and 702 = 2 × 3³ × 13 are not 7-smooth. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography, which relies on factorization of integers. The 2-smooth numbers are just the powers of 2, while 5-smooth numbers are known as regular numbers.

Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The prototypical example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the prototypical example of a sieve is the sieve of Eratosthenes, or the more general Legendre sieve. The direct attack on prime numbers using these methods soon reaches apparently insuperable obstacles, in the way of the accumulation of error terms. In one of the major strands of number theory in the twentieth century, ways were found of avoiding some of the difficulties of a frontal attack with a naive idea of what sieving should be.

In additive combinatorics, Freiman's theorem is a central result which indicates the approximate structure of sets whose sumset is small. It roughly states that if $is small, then can be contained in a small generalized arithmetic progression.$

<span class="mw-page-title-main">Brun's theorem</span> Theorem that the sum of the reciprocals of the twin primes converges

In number theory, Brun's theorem states that the sum of the reciprocals of the twin primes converges to a finite value known as Brun's constant, usually denoted by B₂. Brun's theorem was proved by Viggo Brun in 1919, and it has historical importance in the introduction of sieve methods.

Euclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. It was first proved by Euclid in his work Elements. There are several proofs of the theorem.

In number theory, Ostrowski's theorem, due to Alexander Ostrowski (1916), states that every non-trivial absolute value on the rational numbers $is equivalent to either the usual real absolute value or a p -adic absolute value.$

<span class="mw-page-title-main">Chebyshev function</span>

In mathematics, the Chebyshev function is either a scalarising function or one of two related functions. The first Chebyshev function $ϑ (x)$ or $θ (x)$ is given by

The Lambek–Moser theorem is a mathematical description of partitions of the natural numbers into two complementary sets. For instance, it applies to the partition of numbers into even and odd, or into prime and non-prime. There are two parts to the Lambek–Moser theorem. One part states that any two non-decreasing integer functions that are inverse, in a certain sense, can be used to split the natural numbers into two complementary subsets, and the other part states that every complementary partition can be constructed in this way. When a formula is known for the $th$ natural number in a set, the Lambek–Moser theorem can be used to obtain a formula for the $th$ number not in the set.

In analytic number theory, the Brun–Titchmarsh theorem, named after Viggo Brun and Edward Charles Titchmarsh, is an upper bound on the distribution of prime numbers in arithmetic progression.

<span class="mw-page-title-main">Selberg sieve</span>

In number theory, the Selberg sieve is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences. It was developed by Atle Selberg in the 1940s.

In number theory, the Turán sieve is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences. It was developed by Pál Turán in 1934.

In number theory, the fundamental lemma of sieve theory is any of several results that systematize the process of applying sieve methods to particular problems. Halberstam & Richert write:

A curious feature of sieve literature is that while there is frequent use of Brun's method there are only a few attempts to formulate a general Brun theorem ; as a result there are surprisingly many papers which repeat in considerable detail the steps of Brun's argument.

Anatoly Alexeyevich Karatsuba was a Russian mathematician working in the field of analytic number theory, p-adic numbers and Dirichlet series.

References

Viggo Brun (1915). "Über das Goldbachsche Gesetz und die Anzahl der Primzahlpaare". Archiv for Mathematik og Naturvidenskab. B34 (8).
Viggo Brun (1919). "La série ${\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+{\tfrac {1}{13}}+{\tfrac {1}{17}}+{\tfrac {1}{19}}+{\tfrac {1}{29}}+{\tfrac {1}{31}}+{\tfrac {1}{41}}+{\tfrac {1}{43}}+{\tfrac {1}{59}}+{\tfrac {1}{61}}+\cdots$ où les dénominateurs sont "nombres premiers jumeaux" est convergente ou finie". Bulletin des Sciences Mathématiques. 43: 100–104, 124–128. JFM 47.0163.01.
Alina Carmen Cojocaru; M. Ram Murty (2005). An introduction to sieve methods and their applications. London Mathematical Society Student Texts. Vol. 66. Cambridge University Press. pp. 80–112. ISBN 0-521-61275-6.
George Greaves (2001). Sieves in number theory. Ergebnisse der Mathematik und ihrer Grenzgebiete (3. Folge). Vol. 43. Springer-Verlag. pp. 71–101. ISBN 3-540-41647-1.
Heini Halberstam; H.E. Richert (1974). Sieve Methods. Academic Press. ISBN 0-12-318250-6.
Christopher Hooley (1976). Applications of sieve methods to the theory of numbers. Cambridge University Press. ISBN 0-521-20915-3..

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.