# User:Richard Pinch/sandbox-CZ

## Contents

# 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 *A*_{p} denote the set of elements of *A* divisible by *p* and extend this to let *A*_{d} the intersection of the *A*_{p} for *p* dividing *d*, when *d* is a product of distinct primes from *P*. Further let A_{1} 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 |*A*_{d}| 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
*n*≤*x*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 *A*_{p} denote the set of elements of *A* divisible by *p* and extend this to let *A*_{d} the intersection of the *A*_{p} for *p* dividing *d*, when *d* is a product of distinct primes from *P*. Further let A_{1} 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 |*A*_{d}| 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 . \]

## Applications

- The Hardy–Ramanujan theorem that the normal order of ω(
*n*), the number of distinct prime factors of a number*n*, is log(log(*n*)); - Almost all integer polynomials (taken in order of height) are irreducible.

## References

# 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 *b*_{i} 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 *r* ≤ *n* and zero otherwise, with normalization factor *H*_{n}, the *n*-th harmonic number.

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

The zeta distribution with parameter *s* assigns probability proportional to 1/*r*^{s} 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