Namespaces
Variants
Actions

Difference between revisions of "User:Richard Pinch/sandbox-CZ"

From Encyclopedia of Mathematics
Jump to: navigation, search
 
(68 intermediate revisions by the same user not shown)
Line 1: Line 1:
  
  
−
=Modulus (algebraic number theory)=
+
=Selberg sieve=
 +
A technique for estimating the size of "sifted sets" of [[positive integer]]s which satisfy a set of conditions which are expressed by [[Congruence relation#Modular arithmetic|congruence]]s.  It was developed by [[Atle Selberg]] in the 1940s.
  
−
Also an '''extended ideal''', a formal product of [[place]]s of an [[algebraic number field]].  It is used to encode [[ramification]] data for [[abelian extension]]s of a number field.  
+
==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 $K$ be an algebraic number field with ring of integers $R$.  A ''modulus'' is a formal product
+
Let ''A'' be a set of positive integers &le; ''x'' and let ''P'' be a set of primes.  For each ''p'' in ''P'', let ''A''<sub>''p''</sub> denote the set of elements of ''A'' divisible by ''p'' and extend this to let ''A''<sub>''d''</sub> the intersection of the ''A''<sub>''p''</sub> for ''p'' dividing ''d'', when ''d'' is a product of distinct primes from ''P''.  Further let A<sub>1</sub> denote ''A'' itself.  Let ''z'' be a positive real number and ''P''(''z'') denote the product of the primes in ''P'' which are &le; ''z''. The object of the sieve is to estimate
−
$$
 
−
\mathfrak{m} = \prod_{\mathfrak{p}} \mathfrak{p}^{\nu(\mathfrak{p})}
 
−
$$
 
−
where $\mathfrak{p}$ runs over all places of $K$, finite or infinite, the exponents $\nu$ are zero except for finitely many $\mathfrak{p}$, for real places $\mathfrak{r}$ we have $\nu(\mathfrak{r})=0$ or $1$ and for complex places $\nu=0$.
 
  
−
We extend the notion of [[congruence]] to this setting.  Let $x$ and $y$ be elements of ''K''.  For a finite place $\mathfrak{p}$, that is, a prime ideal of the ring of integers, we define $x$ and $y$ to be congruent modulo $\mathfrak{p}^n$ if ''x''/''y'' is in the [[valuation ring]] $R_{\mathfrak{p}}$ of ${\mathfrak{p}}$ and congruent to 1 modulo $\mathfrak{p}^n$ in $R_{\mathfrak{p}}$ in the usual sense of ring theory.  For a real place $\mathfrak{r}$ we define $x$ and $y$ to be congruent modulo $\mathfrak{r}$ if $x/y$ is positive in the real embedding of $K$ associated to the place $\mathfrak{r}$.  Finally, we define $x$ and $y$ to be congruent modulo $\mathfrak{m}$ if they are congruent modulo $\mathfrak{p}^{\nu(\mathfrak{p})}$ whenever $\nu(\mathfrak{p}) > 0$.
+
:<math>S(A,P,z) = \left\vert A \setminus \bigcup_{p \in P(z)} A_p \right\vert . </math>
  
−
==Ray class group==
+
We assume that |''A''<sub>''d''</sub>| may be estimated by
−
We split the modulus $\mathfrak{m}$ into $\mathfrak{m}_\text{fin}$ and $\mathfrak{m}_\text{inf}$, the product over the finite and infinite places respectively.  Define
 
−
$$
 
−
K_{\mathfrak{m}} = \left\lbrace a/b \in K \mid a,b \in R,~ ab ~\mbox{coprime to}~ \mathfrak{m}_\mbox{fin} \right\rbrace \,,
 
−
$$
 
−
$$
 
−
K_{\mathfrak{m},1} = \left\lbrace x \in K_{\mathfrak{m}} \mid x \equiv 1 \pmod \mathfrak{m} \right\rbrace \ .
 
−
$$
 
  
−
We call the group $K_{\mathfrak{m},1}$ the ''ray modulo'' $\mathfrak{m}$.
+
:<math> \left\vert A_d \right\vert = \frac{1}{f(d)} X + R_d . </math>
  
−
Further define the subgroup of the ideal group $I^{\mathfrak{m}}$ to be the subgroup generated by ideals coprime to $\mathfrak{m}_\text{fin}$.  The ''ray class group'' modulo $\mathfrak{m}$ is the quotient $I^{\mathfrak{m}} / i(K_{\mathfrak{m},1})$, where $i$ is the map from $K$ to principal ideals in the ideal group.  A coset of $i(K_{\mathfrak{m},1})$ is a ''ray class''.
+
where ''f'' is a [[multiplicative function]] and ''X'' &nbsp; = &nbsp; |''A''|.  Let the function ''g'' be obtained from ''f'' by [[Möbius inversion formula|Möbius inversion]], that is
  
−
Hecke's original definition of [[Hecke character]]s may be interpreted in terms of [[Character|character]]s of the ray class group with respect to some modulus $\mathfrak{m}$.
+
:<math> g(n) = \sum_{d \mid n} \mu(d) f(n/d) </math>
 +
:<math> f(n) = \sum_{d \mid n} g(d) </math>
  
−
===Properties===
+
where &mu; is the [[Möbius function]]. 
−
* When $\mathfrak{m} = 1$, the ray class group is just the [[ideal class group]].
+
Put
−
* The ray class group is finite.  Its order is the ''ray class number''.
+
 
−
* The ray class number divides the [[Class number (number theory)|class number]] of $K$.
+
:<math> V(z) = \sum_{\begin{smallmatrix}d < z \\ d \mid P(z)\end{smallmatrix}} \frac{\mu^2(d)}{g(d)} . </math>
 +
 
 +
Then
 +
 
 +
:<math> 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) .</math>
 +
 
 +
It is often useful to estimate ''V''(''z'') by the bound
 +
 
 +
:<math> V(z) \ge \sum_{d \le z} \frac{1}{f(d)} . \, </math>
 +
 
 +
==Applications==
 +
* The [[Brun-Titchmarsh theorem]] on the number of primes in an arithmetic progression;
 +
* The number of ''n'' &le; ''x'' such that ''n'' is coprime to &phi;(''n'') is asymptotic to e<sup>-&gamma;</sup> ''x'' / log log log (''x'') .
  
 
==References==
 
==References==
−
* Harvey Cohn. "A classical invitation to algebraic numbers and class fields" (Springer-Verlag, 1978) ISBN 0-387-90345-3. pp.163-187
+
* {{User:Richard Pinch/sandbox/Ref | author=Alina Carmen Cojocaru | coauthors=M. Ram Murty | title=An introduction to sieve methods and their applications | series=London Mathematical Society Student Texts | volume=66 | publisher=[[Cambridge University Press]] | isbn=0-521-61275-6 | pages=113-134 }}
−
* Harvey Cohn. "Introduction to the construction of class fields". Cambridge studies in advanced mathematics '''6''' (Cambridge University Press, 1985) ISBN 0-521-24762-4.  
+
* {{User:Richard Pinch/sandbox/Ref | author=George Greaves | title=Sieves in number theory | publisher=[[Springer-Verlag]] | date=2001 | isbn=3-540-41647-1}}
−
* Gerald J. Janusz.  "Algebraic Number Fields".  Pure and Applied Mathematics '''55''' (Academic Press, 1973) ISBN 0-12-380250. pp.107-113.
+
* {{User:Richard Pinch/sandbox/Ref | author=Heini Halberstam | coauthors=H.E. Richert | title=Sieve Methods | publisher=[[Academic Press]] | date=1974 | isbn=0-12-318250-6}}
 +
* {{User:Richard Pinch/sandbox/Ref | author= Christopher Hooley | authorlink=Christopher Hooley | title=Applications of sieve methods to the theory of numbers | publisher=Cambridge University Press | date=1976 | isbn=0-521-20915-3| pages=7-12}}
 +
* {{User:Richard Pinch/sandbox/Ref | author=Atle Selberg | authorlink=Atle Selberg | title=On an elementary method in the theory of primes | journal=Norske Vid. Selsk. Forh. Trondheim | volume=19 | year=1947 | pages=64-67 }}
 +
 
 +
=Separation axioms=
 +
In [[topology]], '''separation axioms''' describe classes of [[topological space]] according to how well the [[open set]]s 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 <math>x \in U \subseteq N</math>.
 +
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 <math>A \subseteq U \subseteq N</math>.
 +
 
 +
Subsets ''U'' and ''V'' are ''separated'' in ''X'' if ''U'' is disjoint from the [[Closure (topology)|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''.
  
−
=Continuant=
+
==Axioms==
−
An  algebraic function of a sequence of variables which has applications in [[generalized continued fraction]]s and as the determinant of a [[tridiagonal matrix]].
+
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
  
−
The $n$-th ''continuant'', $K(n)$, of a sequence $\mathbf{a} = a_1,\ldots,a_n,\ldots$  defined recursively by
+
* '''Hausdorff''' is a synonym for T2
−
$$
+
* '''completely Hausdorff''' is a synonym for T2½
−
K(0) = 1 ;
 
−
$$
 
−
$$
 
−
K(1) = a_1 ;
 
−
$$
 
−
$$
 
−
K(n) = a_n K(n-1) + K(n-2) \ .
 
−
$$
 
−
It  may also be obtained by taking the sum of all possible products of  $a_1,\ldots,a_n$ in which any pairs of consecutive terms are deleted.
 
  
−
An  extended definition takes the continuant with respect to three  sequences $\mathbf a$, $\mathbf b$, $\mathbf c$, so that $K(n)$ is a  function of $a_1,\ldots,a_n$, $b_1,\ldots,b_{n-1}$,  $c_1,\ldots,c_{n-1}$.  In this case the [[recurrence relation]] becomes
+
* '''regular''' if T0 and T3
−
$$
+
* '''completely regular''' if T0 and T3½
−
K(0) = 1 ; 
+
* '''Tychonoff''' is completely regular and T1
−
$$
 
−
$$
 
−
K(1) = a_1 ;
 
−
$$
 
−
$$
 
−
K(n) = a_n K(n-1) - b_{n-1}c_{n-1} K(n-2) \ .
 
−
$$
 
−
Since  $b_r$ and $c_r$ enter into $K$ only as the product $b_r c_r$ there is  no loss of generality in assuming that the $b_r$ are all equal to 1.
 
  
−
The simple continuant gives the value of a [[continued fraction]] of the form $[a_0;a_1,a_2,\ldots]$.  The $n$-th convergent is
+
* '''normal''' if T0 and T4
−
$$
+
* '''completely normal''' if T1 and T5
−
\frac{K(n+1,(a_0,\ldots,a_n))}{K(n,(a_1,\ldots,a_n))} \ .
+
* '''perfectly normal''' if normal and every closed set is a [[G-delta set|G<sub>δ</sub>]]
−
$$
 
  
−
The extended continuant is the determinant of the tridiagonal matrix
+
==Properties==
−
$$
+
* A space is T1 if and only if each point ([[singleton]]) forms a closed set.
−
\begin{pmatrix}
+
* ''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'''.
−
a_1 & b_1 &  0  &  0  & \ldots & 0 & 0 \\
 
−
c_1 & a_2 & b_2 &  0  & \ldots & 0 & 0 \\
 
−
0  & c_2 & a_3 & b_3 & \ldots & 0 & 0 \\
 
−
\vdots & \ddots & \ddots & \ddots & & \vdots & \vdots \\
 
−
0 & 0 & 0 & 0 & \ldots & c_{n-1} & a_n
 
−
\end{pmatrix} \ .
 
−
$$
 
  
 
==References==
 
==References==
−
* Thomas Muir. ''A treatise on the theory of determinants''. (Dover Publications, 1960 [1933]), pp.  516-525.
+
* {{User:Richard Pinch/sandbox/Ref | last1=Steen | first1=Lynn Arthur | last2=Seebach | first2=J. Arthur Jr. | title=Counterexamples in Topology | year=1978 | publisher=[[Springer-Verlag]] | location=Berlin, New York | 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 integer]]s which satisfy a set of conditions which are expressed by [[Congruence relation#Modular arithmetic|congruence]]s.  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.
  
−
=ABC conjecture=
+
Let ''A'' be a set of positive integers &le; ''x'' and let ''P'' be a set of primes.  For each ''p'' in ''P'', let ''A''<sub>''p''</sub> denote the set of elements of ''A'' divisible by ''p'' and extend this to let ''A''<sub>''d''</sub> the intersection of the ''A''<sub>''p''</sub> for ''p'' dividing ''d'', when ''d'' is a product of distinct primes from ''P''.  Further let A<sub>1</sub> denote ''A'' itself.  Let ''z'' be a positive real number and ''P''(''z'') denote the product of the primes in ''P'' which are &le; ''z''.  The object of the sieve is to estimate
  
−
In mathematics, the '''ABC conjecture''' relates the prime factors of two integers to those of their sum.  It was proposed by [[David Masser]] and [[Joseph Oesterlé]] in 1985.  It is connected with other problems of [[number theory]]: for example, the truth of the ABC conjecture would provide a new proof of [[Fermat's Last Theorem]].
+
:<math>S(A,P,z) = \left\vert A \setminus \bigcup_{p \in P(z)} A_p \right\vert . </math>
  
−
==Statement==
+
We assume that |''A''<sub>''d''</sub>| may be estimated, when ''d'' is a prime ''p'' by
−
Define the ''radical'' of an integer to be the product of its distinct prime factors
 
  
−
:<math> r(n) = \prod_{p|n} p \ . </math>
+
:<math> \left\vert A_p \right\vert = \frac{1}{f(p)} X + R_p  </math>
  
−
Suppose now that the equation <math>A + B + C = 0</math> holds for coprime integers <math>A,B,C</math>.  The conjecture asserts that for every <math>\epsilon > 0</math> there exists <math>\kappa(\epsilon) > 0</math> such that
+
and when ''d'' is a product of two distinct primes ''d'' = ''p'' ''q'' by
  
−
:<math> |A|, |B|, |C| < \kappa(\epsilon) r(ABC)^{1+\epsilon} \ . </math>
+
:<math> \left\vert A_{pq} \right\vert = \frac{1}{f(p)f(q)} X + R_{p,q} </math>
  
−
A weaker form of the conjecture states that
+
where ''X'' &nbsp; = &nbsp; |''A''| and ''f'' is a function with the property that 0 &le; ''f''(''d'') &le; 1.  Put
  
−
:<math> (|A| \cdot |B| \cdot |C|)^{1/3} < \kappa(\epsilon) r(ABC)^{1+\epsilon} \ . </math>
+
:<math> U(z) = \sum_{p \mid P(z)} f(p) . </math>
  
−
If we define
+
Then
  
−
:<math> \kappa(\epsilon) = \inf_{A+B+C=0,\ (A,B)=1} \frac{\max\{|A|,|B|,|C|\}}{N^{1+\epsilon}} \ , </math>
+
:<math> 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 . </math>
  
−
then it is known that <math>\kappa \rightarrow \infty</math> as <math>\epsilon \rightarrow 0</math>.
+
==Applications==
 +
* The [[Hardy–Ramanujan theorem]] that the [[normal order of an arithmetic function|normal order]] of &omega;(''n''), the number of distinct [[prime factor]]s of a number ''n'', is log(log(''n''));
 +
* Almost all integer polynomials (taken in order of height) are irreducible.
  
−
Baker introduced a more refined version of the conjecture in 1998. Assume as before that <math>A + B + C = 0</math> holds for coprime integers <math>A,B,C</math>.  Let <math>N</math> be the radical of <math>ABC</math> and <math>\omega</math> the number of distinct prime factors of <math>ABC</math>. Then there is an absolute constant <math>c</math> such that
+
==References==
 +
* {{cite book | author=Alina Carmen Cojocaru | coauthors=M. Ram Murty | title=An introduction to sieve methods and their applications | series=London Mathematical Society Student Texts | volume=66 | publisher=[[Cambridge University Press]] | isbn=0-521-61275-6 | pages=47-62 }}
 +
=Weierstrass preparation theorem=
 +
In [[algebra]], the '''Weierstrass preparation theorem''' describes a canonical form for [[formal power series]] over a [[complete local ring]].
  
−
:<math> |A|, |B|, |C| < c (\epsilon^{-\omega} N)^{1+\epsilon} \ . </math>
+
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
  
−
This form of the conjecture would give very strong bounds in the [[method of linear forms in logarithms]].
+
:<math>f = (X^n + b_{n-1}X^{n-1} + \cdots + b_0) u(x) , \,</math>
  
−
==Results==
+
where the ''b''<sub>''i''</sub> are in the maximal ideal ''m'' of ''O'' and ''u'' is a unit of ''O''[[''X'']].
−
It is known that there is an effectively computable <math>\kappa(\epsilon)</math> such that
 
  
−
:<math> |A|, |B|, |C| < \exp\left({ \kappa(\epsilon) N^{1/3} (\log N)^3 }\right) \ . </math>
+
The integer ''n'' defined by the theorem is the '''Weierstrass degree''' of ''f''.
  
 
==References==
 
==References==
−
* {{cite book | zbl=1046.11035 | last=Goldfeld | first=Dorian | authorlink=Dorian Goldfeld | chapter=Modular forms, elliptic curves and the abc-conjecture | editor=Wüstholz, Gisbert | title=A panorama in number theory or The view from Baker's garden. | location=Cambridge | publisher=Cambridge University Press | pages=128-147 | year=2002 | isbn=0-521-80799-9 }}
+
* {{User:Richard Pinch/sandbox/Ref | author=Serge Lang | authorlink=Serge Lang | title=Algebra | edition=3rd ed | publisher=[[Addison-Wesley]] | year=1993 | isbn=0-201-55540-9 | pages=208-209 }}
−
* {{cite book | last=Baker | first=Alan | authorlink=Alan Baker | chapter=Logarithmic forms and the $abc$-conjecture | pages=37-44 | editor=Győry, Kálmán (ed.) et al. | title=Number theory. Diophantine, computational and algebraic aspects. Proceedings of the international conference, Eger, Hungary, July 29-August 2, 1996 | location=Berlin | publisher=de Gruyter | year=1998 | isbn=3-11-015364-5 | zbl=0973.11047 }}
 
−
* {{cite journal | last=Stewart | first=C. L. | coauthors=Yu Kunrui | title=On the ''abc'' conjecture. II | journal=Duke Math. J. | volume=108 | number=1 | pages=169-181 | year=2001 | issn=0012-7094 | zbl=1036.11032 }}
 
  
−
=Szpiro's conjecture=
 
−
A conjectural relationship between the [[conductor of an elliptic curve|conductor]] and the [[discriminant of an elliptic curve|discriminant]] of an [[elliptic curve]].  In a general form, it is equivalent to the well-known [[ABC conjecture]].  It is named for [[Lucien Szpiro]] who formulated it in the 1980s.
 
  
−
The conjecture states that: given &epsilon; &gt; 0, there exists a constant ''C''(&epsilon;) such that for any elliptic curve ''E'' defined over '''Q''' with minimal discriminant &Delta; and conductor ''f'', we have
+
=Zipf distribution=
 +
In [[probability theory]] and [[statistics]], the '''Zipf distribution''' and '''zeta distribution''' refer to a class of [[discrete probability distribution]]s.  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.
  
−
:<math> \vert\Delta\vert \leq C(\varepsilon ) \cdot f^{6+\varepsilon }. \, </math>
+
The Zipf distribution with parameter ''n'' assigns probability proportional to 1/''r'' to an integer ''r'' &le; ''n'' and zero otherwise, with [[normalization]] factor ''H''<sub>''n''</sub>, the ''n''-th [[harmonic number]].
  
−
The '''modified Szpiro conjecture''' states that: given &epsilon; &gt; 0, there exists a constant ''C''(&epsilon;) such that for any elliptic curve ''E'' defined over '''Q''' with invariants ''c''<sub>4</sub>, ''c''<sub>6</sub> and conductor ''f'', we have
+
A Zipf-like distribution with parameters ''n'' and ''s'' assigns probability proportional to 1/''r''<sup>''s''</sup> to an integer ''r'' &le; ''n'' and zero otherwise, with normalization factor <math>\sum_{r=1}^n 1/r^s</math>.
  
−
:<math> \max\{\vert c_4\vert^3,\vert c_6\vert^2\} \leq C(\varepsilon )\cdot f^{6+\varepsilon }. \, </math>
+
The zeta distribution with parameter ''s'' assigns probability proportional to 1/''r''<sup>''s''</sup> to all integers ''r'' with normalization factor given by the [[Riemann zeta function]] 1/ζ(''s'').
  
 
==References==
 
==References==
−
 
+
* {{cite book | author=Michael Woodroofe | coauthors=Bruce Hill | title=On Zipf's law | journal=J. Appl. Probab. | volume=12 | pages=425-434 | year=1975 | id=Zbl 0343.60012 }}
−
* {{cite book | first=Serge | last=Lang | authorlink=Serge Lang | title=Survey of Diophantine geometry | publisher=[[Springer-Verlag]] | year=1997 | isbn=3-540-61223-8 | page=51 | zbl=0869.11051 | edition=Corrected 2nd printing }}
 
−
* {{cite journal | author=L. Szpiro | title=Seminaire sur les pinceaux des courbes de genre au moins deux | journal=Astérisque | volume=86 | issue=3 | year=1981 | pages=44-78 | zbl=0463.00009 }}
 
−
* {{cite journal | author=L. Szpiro | title=Présentation de la théorie d'Arakelov | journal=Contemp. Math. | volume=67 | year=1987 | pages=279-293 | zbl=0634.14012  }}
 

Latest revision as of 19:14, 2 May 2020


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 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 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 . \]

Applications

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 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 r ≤ n 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 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/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=30301
Retrieved from "https://encyclopediaofmath.org/index.php?title=User:Richard_Pinch/sandbox-CZ&oldid=45660"