analytic number theory In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Peter Gustav Lejeune Dirichlet's 1837 introduction of Diric ...

, the Siegel–Walfisz theorem was obtained by

Arnold Walfisz Arnold Walfisz (2 July 1892 – 29 May 1962) was a Jewish-Polish mathematician working in analytic number theory. Life After the ''Abitur'' in Warsaw (Poland), Arnold Walfisz studied (1909−14 and 1918−21) in Germany at Munich, Berlin, Heide ...

as an application of a

theorem In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of th ...

Carl Ludwig Siegel Carl Ludwig Siegel (31 December 1896 – 4 April 1981) was a German mathematician specialising in analytic number theory. He is known for, amongst other things, his contributions to the Thue–Siegel–Roth theorem in Diophantine approximation, ...

primes in arithmetic progression In number theory, primes in arithmetic progression are any sequence of at least three prime numbers that are consecutive terms in an arithmetic progression. An example is the sequence of primes (3, 7, 11), which is given by a_n = 3 + 4n for 0 \le n ...

s. It is a refinement both of the

prime number theorem 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 ...

and of

Dirichlet's theorem on primes in arithmetic progressions In number theory, Dirichlet's theorem, also called the Dirichlet prime number theorem, states that for any two positive coprime integers ''a'' and ''d'', there are infinitely many primes of the form ''a'' + ''nd'', where ''n'' is als ...

Statement

Define :

\psi(x;q,a) = \sum_\Lambda(n),

where

\Lambda

denotes the

von Mangoldt function In mathematics, the von Mangoldt function is an arithmetic function named after German mathematician Hans von Mangoldt. It is an example of an important arithmetic function that is neither multiplicative nor additive. Definition The von Mangold ...

, and let ''φ'' denote

Euler's totient function In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...

. Then the theorem states that given any

real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...

''N'' there exists a positive constant ''C''_''N'' depending only on ''N'' such that :

\psi(x;q,a)=\frac+O\left(x\exp\left(-C_N(\log x)^\frac\right)\right),

whenever (''a'', ''q'') = 1 and :

q\le(\log x)^N.

Remarks

The constant ''C''_''N'' is not

effectively computable Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can d ...

because Siegel's theorem is ineffective. From the theorem we can deduce the following bound regarding the

prime number theorem for arithmetic progressions 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 t ...

: If, for (''a'', ''q'') = 1, by

\pi(x;q,a)

we denote the number of primes less than or equal to ''x'' which are

congruent Congruence may refer to: Mathematics * Congruence (geometry), being the same size and shape * Congruence or congruence relation, in abstract algebra, an equivalence relation on an algebraic structure that is compatible with the structure * In mod ...

to ''a'' mod ''q'', then :

\pi(x;q,a) = \frac+O\left(x\exp\left(-\frac(\log x)^\frac\right)\right),

where ''N'', ''a'', ''q'', ''C''_''N'' and φ are as in the theorem, and Li denotes the

logarithmic integral In mathematics, the logarithmic integral function or integral logarithm li(''x'') is a special function. It is relevant in problems of physics and has number theoretic significance. In particular, according to the prime number theorem, it is a ...

References

{{DEFAULTSORT:Siegel-Walfisz theorem Theorems in analytic number theory Theorems about prime numbers