# Selberg sieve

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.

## Description

In terms of sieve theory the Selberg sieve is of combinatorial type: that is, derives from a careful use of the inclusion-exclusion principle. Selberg replaced the values of the Möbius function which arise in this by a system of weights which are then optimised to fit the given problem. The result gives an upper bound for the size of the sifted set.

Let A be a set of positive integers ≤ x and let P be a set of primes. For each p in P, let Ap denote the set of elements of A divisible by p and extend this to let Ad the intersection of the Ap for p dividing d, when d is a product of distinct primes from P. Further let A1 denote A itself. Let z be a positive real number and P(z) denote the product of the primes in P which are ≤ z. The object of the sieve is to estimate

$S(A,P,z) = \left\vert A \setminus \bigcup_{p \in P(z)} A_p \right\vert .$

We assume that |Ad| may be estimated by

$\left\vert A_d \right\vert = \frac{1}{f(d)} X + R_d .$

where f is a multiplicative function and X   =   |A|. Let the function g be obtained from f by Möbius inversion, that is

$g(n) = \sum_{d \mid n} \mu(d) f(n/d)$ $f(n) = \sum_{d \mid n} g(d)$

where μ is the Möbius function. Put

$V(z) = \sum_{\begin{smallmatrix}d < z \\ d \mid P(z)\end{smallmatrix}} \frac{\mu^2(d)}{g(d)} .$

Then

$S(A,P,z) \le \frac{X}{V(z)} + O\left({\sum_{\begin{smallmatrix} d_1,d_2 < z \\ d_1,d_2 \mid P(z)\end{smallmatrix}} \left\vert R_{[d_1,d_2]} \right\vert} \right) .$

It is often useful to estimate V(z) by the bound

$V(z) \ge \sum_{d \le z} \frac{1}{f(d)} . \,$

## Applications

• The Brun-Titchmarsh theorem on the number of primes in an arithmetic progression;
• The number of nx such that n is coprime to φ(n) is asymptotic to e x / log log log (x) .

## References

• Alina Carmen Cojocaru; M. Ram Murty; An introduction to sieve methods and their applications, ser. London Mathematical Society Student Texts 66 , pp. 113-134, Cambridge University Press ISBN: 0-521-61275-6
• George Greaves; Sieves in number theory, , Springer-Verlag ISBN: 3-540-41647-1
• Heini Halberstam; H.E. Richert; Sieve Methods, , Academic Press ISBN: 0-12-318250-6
• Christopher Hooley; Applications of sieve methods to the theory of numbers, , pp. 7-12, Cambridge University Press ISBN: 0-521-20915-3
• Atle Selberg; On an elementary method in the theory of primes, Norske Vid. Selsk. Forh. Trondheim, 19 (1947), pp. 64-67

# Separation axioms

In topology, separation axioms describe classes of topological space according to how well the open sets of the topology distinguish between distinct points.

## Terminology

A neighbourhood of a point x in a topological space X is a set N such that x is in the interior of N; that is, there is an open set U such that $$x \in U \subseteq N$$. A neighbourhood of a set A in X is a set N such that A is contained in the interior of N; that is, there is an open set U such that $$A \subseteq U \subseteq N$$.

Subsets U and V are separated in X if U is disjoint from the closure of V and V is disjoint from the closure of U.

A Urysohn function for subsets A and B of X is a continuous function f from X to the real unit interval such that f is 0 on A and 1 on B.

## Axioms

A topological space X is

• T0 if for any two distinct points there is an open set which contains just one
• T1 if for any two points x, y there are open sets U and V such that U contains x but not y, and V contains y but not x
• T2 if any two distinct points have disjoint neighbourhoods
• T2½ if distinct points have disjoint closed neighbourhoods
• T3 if a closed set A and a point x not in A have disjoint neighbourhoods
• T3½ if for any closed set A and point x not in A there is a Urysohn function for A and {x}
• T4 if disjoint closed sets have disjoint neighbourhoods
• T5 if separated sets have disjoint neighbourhoods
• Hausdorff is a synonym for T2
• completely Hausdorff is a synonym for T2½
• regular if T0 and T3
• completely regular if T0 and T3½
• Tychonoff is completely regular and T1
• normal if T0 and T4
• completely normal if T1 and T5
• perfectly normal if normal and every closed set is a Gδ

## Properties

• A space is T1 if and only if each point (singleton) forms a closed set.
• Urysohn's Lemma: if A and B are disjoint closed subsets of a T4 space X, there is a Urysohn function for A and B'.

## References

• Steen, Lynn Arthur; Seebach, J. Arthur Jr.; Counterexamples in Topology, (1978), Springer-Verlag ISBN: 0-387-90312-7

# Turan sieve

In mathematics, in the field of 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.

## Description

In terms of sieve theory the Turán sieve is of combinatorial type: deriving from a rudimentary form of the inclusion-exclusion principle. The result gives an upper bound for the size of the sifted set.

Let A be a set of positive integers ≤ x and let P be a set of primes. For each p in P, let Ap denote the set of elements of A divisible by p and extend this to let Ad the intersection of the Ap for p dividing d, when d is a product of distinct primes from P. Further let A1 denote A itself. Let z be a positive real number and P(z) denote the product of the primes in P which are ≤ z. The object of the sieve is to estimate

$S(A,P,z) = \left\vert A \setminus \bigcup_{p \in P(z)} A_p \right\vert .$

We assume that |Ad| may be estimated, when d is a prime p by

$\left\vert A_p \right\vert = \frac{1}{f(p)} X + R_p$

and when d is a product of two distinct primes d = p q by

$\left\vert A_{pq} \right\vert = \frac{1}{f(p)f(q)} X + R_{p,q}$

where X   =   |A| and f is a function with the property that 0 ≤ f(d) ≤ 1. Put

$U(z) = \sum_{p \mid P(z)} f(p) .$

Then

$S(A,P,z) \le \frac{X}{U(z)} + \frac{2}{U(z)} \sum_{p \mid P(z)} \left\vert R_p \right\vert + \frac{1}{U(z)^2} \sum_{p,q \mid P(z)} \left\vert R_{p,q} \right\vert .$

# Weierstrass preparation theorem

In algebra, the Weierstrass preparation theorem describes a canonical form for formal power series over a complete local ring.

Let O be a complete local ring and f a formal power series in O''X''. Then f can be written uniquely in the form

$f = (X^n + b_{n-1}X^{n-1} + \cdots + b_0) u(x) , \,$

where the bi are in the maximal ideal m of O and u is a unit of O''X''.

The integer n defined by the theorem is the Weierstrass degree of f.

## References

• Serge Lang; Algebra, (1993), pp. 208-209, Addison-Wesley ISBN: 0-201-55540-9

# Zipf distribution

In probability theory and statistics, the Zipf distribution and zeta distribution refer to a class of discrete probability distributions. They have been used to model the distribution of words in words in a text , of text strings and keys in databases, and of the sizes of businesses and towns.

The Zipf distribution with parameter n assigns probability proportional to 1/r to an integer rn and zero otherwise, with normalization factor Hn, the n-th harmonic number.

A Zipf-like distribution with parameters n and s assigns probability proportional to 1/rs to an integer rn and zero otherwise, with normalization factor $$\sum_{r=1}^n 1/r^s$$.

The zeta distribution with parameter s assigns probability proportional to 1/rs to all integers r with normalization factor given by the Riemann zeta function 1/ζ(s).

## References

How to Cite This Entry:
Richard Pinch/sandbox-CZ. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-CZ&oldid=45660