Namespaces
Variants
Actions

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

From Encyclopedia of Mathematics
Jump to: navigation, search
(Start article: Kernel of a function)
 
(24 intermediate revisions by the same user not shown)
Line 1: Line 1:
  
=Kernel of a function=
 
The [[equivalence relation]] on the domain of the function expressing the property that equivalent elements have the same image under the function.
 
  
If $f : X \rightarrow Y$ then we define the relation $\stackrel{f}{\equiv}$ by
 
$$
 
x_1 \stackrel{f}{\equiv} x_2 \Leftrightarrow f(x_1) = f(x_2) \ .
 
$$
 
The [[equivalence class]]es of $\stackrel{f}{\equiv}$ are the '''fibres''' of ''f''.
 
 
Every function gives rise to an equivalence relation as kernel.  Conversely, every equivalence relation $\sim\,$ on a set $X$ gives rise to a function of which it is the kernel.  Consider the ''quotient set'' $X/\sim\,$ of equivalence classes under $\sim\,$ and consider the ''quotient map'' $q_\sim : X \rightarrow X/\sim$ defined by
 
$$
 
q_\sim : x \mapsto [x]_\sim \, ,
 
$$
 
where $[x]_\sim\,$ is the equivalence class of $c$ under $\sim\,$.  Then the kernel of the quotient map $q_\sim\,$ is just $\sim\,$.  This may be regarded as the set-theoretic version of the [[First Isomorphism Theorem]].
 
 
 
=Median algebra=
 
A set with a [[ternary operation]] $\langle x,y,z \rangle$ satisfying a set of axioms which generalise the notion of median, or majority vote, as a [[Boolean function]].
 
 
The axioms are
 
# $\langle x,y,y \rangle = y$                 
 
# $\langle x,y,z \rangle = \langle z,x,y \rangle$           
 
# $\langle x,y,z \rangle = \langle x,z,y \rangle$           
 
# $\langle \langle x,w,y \rangle ,w,z \rangle = \langle x,w, \langle y,w,z \rangle \rangle$
 
 
The second and third axioms imply commutativity: it is possible (but not easy) to show that in the presence of the other three, axiom (3) is redundant.  The fourth axiom implies associativity.
 
There are other possible axiom systems: for example the two
 
* $\langle x,y,y \rangle = y$ 
 
* $\langle u,v, \langle u,w,x \rangle \rangle = \langle u,x, \langle w,u,v \rangle \rangle$
 
also suffice.
 
 
In a [[Boolean algebra]] the median function $\langle x,y,z \rangle = (x \vee y) \wedge (y \vee z) \wedge (z \vee x)$ satisfies these axioms, so that every Boolean algebra is a median algebra.
 
 
Birkhoff and Kiss showed that a median algebra with elements 0 and 1 satisfying $\langle 0,x,1 \rangle = x$ is a [[distributive lattice]].
 
 
==References==
 
* {{User:Richard Pinch/sandbox/Ref  | last=Birkhoff | first=Garrett | authorlink=Garrett Birkhoff | last2=Kiss | fitst2=S.A. | title=A ternary operation in distributive lattices | journal=[[Bulletin of the American Mathematical Society|Bull. Amer. Math. Soc.]] | volume=53 | date=1947 | pages=749-752 }}
 
* {{User:Richard Pinch/sandbox/Ref  | last=Isbell | first=John R. | title=Median algebra | journal=[[Transactions of the American Mathematical Society|Trans. Amer. Math. Soc.]] | volume=260 | issue=2 | date=August 1980 | pages=319-362 }}
 
* {{ User:Richard Pinch/sandbox/Ref  | last=Knuth | first=Donald E. | authorlink=Donald Knuth | title=Introduction to combinatorial algorithms and Boolean functions | series=[[The Art of Computer Programming]] | volume=4.0 | date=2008 | isbn=0-321-53496-4 | pages=64-74 }}
 
 
=Monogenic field=
 
 
An [[algebraic number field]] for which there exists an element
 
$\alpha$ such that the [[ring of integers]] $O_K$ is a polynomial ring $\mathbb{Z}[\alpha]$.  The powers of such a element $\alpha$ constitute a '''power integral basis'''.
 
 
In a monogenic field $K$, the [[Discriminant of an algebraic number field|field discriminant]] of $K$ is equal to the [[discriminant of a polynomial|discriminant]] of the [[Minimal polynomial (field theory)|minimal polynomial]] of $\alpha$.
 
 
Examples of monogenic fields include:
 
* [[Quadratic field]]s: if $K = \mathbf{Q}(\sqrt d)$ with $d$ a [[square-free integer]] then $O_K = \mathbf{Z}[\alpha]$ where $\alpha = (1+\sqrt d)/2$ if $d \equiv 1 \pmod 4$ and $\alpha = \sqrt d$ otherwise.
 
* [[Cyclotomic field]]s: if $K = \mathbf{Q}(\zeta)$ with $\zeta$ a root of unity, then $O_K = \mathbf{Z}[\zeta]$.
 
 
Not all number fields are monogenic: Dirichlet gave the example of the [[cubic field]] generated by a root of the polynomial $X^3 - X^2 - 2X - 8$.
 
 
==References==
 
* {{User:Richard Pinch/sandbox/Ref | last = Narkiewicz | first = Władysław | title = Elementary and Analytic Theory of Algebraic Numbers | publisher = [[Springer-Verlag]] | year = 2004 | pages = 64 | isbn = 3540219021}}
 
 
=Moore determinant=
 
A [[determinant]], named after [[E. H. Moore]], defined over a [[finite field]] from a square '''Moore [[matrix]]'''.  A Moore matrix has successive powers of the [[Frobenius automorphism]] applied to the first column, i.e., an $m \times n$
 
$$
 
M=\begin{bmatrix}
 
\alpha_1 & \alpha_1^q & \dots & \alpha_1^{q^{n-1}}\\
 
\alpha_2 & \alpha_2^q & \dots & \alpha_2^{q^{n-1}}\\
 
\alpha_3 & \alpha_3^q & \dots & \alpha_3^{q^{n-1}}\\
 
\vdots & \vdots & \ddots &\vdots \\
 
\alpha_m & \alpha_m^q & \dots & \alpha_m^{q^{n-1}}\\
 
\end{bmatrix}
 
$$
 
or
 
$$
 
M_{i,j} = \alpha_i^{q^{j-1}}
 
$$
 
for all indices $i$ and $j$. (Some authors use the [[transpose]] of the above matrix.)
 
 
The Moore determinant of a square Moore matrix (so $m=n$) can be expressed as:
 
$$
 
\det(V) = \prod_{\mathbf{c}} \left( c_1\alpha_1 + \cdots c_n\alpha_n \right) \,,
 
$$
 
where $c$ runs over a complete set of direction vectors, made specific by having the last non-zero entry equal to 1.
 
 
==See also==
 
* [[Alternant matrix]]
 
* [[Vandermonde determinant]]
 
* [[List of matrices]]
 
 
==References==
 
* {{User:Richard Pinch/sandbox/Ref | author=David Goss | title=Basic Structures of Function Field Arithmetic | date=1996 | publisher=Springer Verlag | isbn=3-540-63541-6}}  Chapter 1.
 
 
 
 
=Morita conjectures=
 
The '''Morita conjectures''' in [[topology]] ask
 
 
# If ''X'' × ''Y'' is [[normal space|normal]] for every normal space ''Y'', is ''X'' [[discrete space|discrete]]?
 
# If ''X'' &times; ''Y'' is normal for every normal P-space ''Y'', is ''X'' [[metrizable]] <ref>K. Morita,  "Some problems on normality of products of spaces"  J. Novák (ed.) , Proc. Fourth Prague Topological Symp. (Prague, August 1976) , Soc. Czech. Math. and Physicists , Prague  (1977)  pp. 296–297</ref>?
 
# If ''X'' &times; ''Y'' is normal for every normal countably [[paracompact]] space ''Y'', is ''X'' metrizable and [[sigma-locally compact]]?
 
 
Here a '''normal P-space''' ''Y'' is characterised by the property that the product with every metrizable ''X'' is normal; it is thus conjectured that the converse holds.
 
 
K. Chiba, T.C. Przymusiński and [[Mary Ellen Rudin|M.E. Rudin]]
 
<ref>K. Chiba,  T.C. Przymusiński,  M.E. Rudin,  "Normality of products and Morita's conjectures"  ''Topol. Appl.'' '''22'''  (1986)  19–32</ref> proved conjecture (1) and showed that conjecture (2) is true if the [[axiom of constructibility]] ''V=L'', holds.
 
 
[[Zoltán Tibor Balogh|Z. Balogh]] proved conjectures (2) and (3)<ref>Z. Balogh, Non-shrinking open covers and K. Morita's duality conjectures, ''Topology Appl.'', '''115''' (2001) 333-341</ref>.
 
 
==References==
 
<references/>
 
* A.V. Arhangelskii, K.R. Goodearl, B. Huisgen-Zimmermann, ''Kiiti Morita 1915-1995'', Notices of the AMS, June 1997 [http://www.ams.org/notices/199706/morita.pdf]
 
 
 
=Normal order of an arithmetic function=
 
A function, perhaps simpler or better-understood, which "usually" takes the same or closely approximate values as a given [[arithmetic function]].
 
 
 
Let $f$ be a function on the [[natural number]]s.  We say that the ''normal order'' of $f$ is $g$ if for every $\epsilon > 0$, the inequalities
 
$$
 
(1-\epsilon) g(n) \le f(n) \le (1+\epsilon) g(n)
 
$$
 
hold for ''[[almost all]]'' $n$: that is, the proportion of $n < x$ for which this does not hold tends to 0 as $x$ tends to infinity.
 
 
It is conventional to assume that the approximating function $g$ is [[Continuous function|continuous]] and [[Monotonic function|monotone]].
 
 
==Examples==
 
* The [[Hardy–Ramanujan theorem]]: the normal order of $\omega(n)$, the number of distinct [[prime factor]]s of $n$, is $\log\log n$;
 
* The normal order of $\log d(n))$, where $d(n)$  is the [[number of divisors function|number of divisors]] of $n$, is $\log 2 \log\log n$.
 
 
==References==
 
* {{User:Richard Pinch/sandbox/Ref | author=G.H. Hardy| authorlink=G. H. Hardy| coauthors=S. Ramanujan|title=The normal number of prime factors of a number |journal= Quart. J. Math. |volume= 48  |year=1917|pages= 76–92}}
 
* {{User:Richard Pinch/sandbox/Ref | author=G.H. Hardy | authorlink=G. H. Hardy | coauthors=E.M. Wright | title=An Introduction to the Theory of Numbers | edition=6th ed. | publisher=[[Oxford University Press]] | pages=473 | year=2008 | isbn=0-19-921986-5 }}
 
* {{User:Richard Pinch/sandbox/Ref | title=Introduction to Analytic and Probabilistic Number Theory | author=Gérald Tenenbaum | series=Cambridge studies in advanced mathematics | volume=46 | publisher=[[Cambridge University Press]] | pages=299-324 | year=1995 | isbn=0-521-41261-7 }}
 
 
=Partition function (number theory)=
 
The function $p(n)$ that counts the number of [[partition]]s of a positive integer $n$, that is, the number of ways of expressing $n$ as a sum of positive integers (where order is not significant).
 
 
Thus ''p''(3) = 3, since the number 3 has 3 partitions:
 
* $3$
 
* $2+1$
 
* $1+1+1$
 
 
The partition function satisfies an asymptotic relation
 
$$
 
p(n) \sim \frac{\exp\left(\pi\sqrt{2/3}\sqrt n\right)}{4n\sqrt3} \ .
 
$$
 
 
==References==
 
* {{User:Richard Pinch/sandbox/Ref  | author=Tom M. Apostol | title=Modular functions and Dirichlet Series in Number Theory  | edition=2nd ed | series=[[Graduate Texts in Mathematics]] | volume=41 | publisher=[[Springer-Verlag]] | year=1990 | isbn=0-387-97127-0 | pages=94-112 }}
 
* {{User:Richard Pinch/sandbox/Ref  | author=G.H. Hardy | authorlink=G. H. Hardy | coauthors=[[E. M. Wright]] | title=An Introduction to the Theory of Numbers | edition=6th ed. | publisher=[[Oxford University Press]] | year=2008 | isbn=0-19-921986-5 | pages=361-392 }}
 
 
=Preparata code=
 
 
A class of non-linear double-[[error-correcting code]]s.  They are named after [[Franco P. Preparata]] who first described them in 1968.
 
 
Let ''m'' be an odd number,  and ''n'' = 2<sup>''m''</sup>-1.  We first describe the '''extended Preparata code''' of length 2''n''+2 = 2<sup>''m''+1</sup>: the Preparata code is then derived by deleting one position.  The words of the extended code are regarded as pairs (''X'',''Y'') of 2<sup>''m''</sup>-tuples, each corresponding to subsets of the [[finite field]] GF(2<sup>''m''</sup>) in some fixed way.
 
 
The extended code contains the words (''X'',''Y'') satisfying three conditions
 
 
# ''X'', ''Y'' each have even weight;
 
# <math>\sum_{x \in X} x = \sum_{y \in Y} y</math>;
 
# <math>\sum_{x \in x} x^3 + \left(\sum_{x \in X} x\right)^3 = \sum_{y \in Y} y^3</math>.
 
 
The Peparata code is obtained by deleting the position in ''X'' corresponding to 0 in GF(2<sup>''m''</sup>).
 
 
The Preparata code is of length 2<sup>''m''+1</sup>-1, size 2<sup>''k''</sup> where ''k'' = 2<sup>''m''+1</sup> - 2''m'' - 2, and minimum distance 5.
 
 
When ''m''=3, the Preparata code of length 15 is also called the '''Nordstrom–Robinson code'''.
 
 
== References ==
 
* {{User:Richard Pinch/sandbox/Ref | author=F.P. Preparata | authorlink=Franco P. Preparata | title=A class of optimum nonlinear double-error-correcting codes | journal=Information and Control | volume=13 | year=1968 | pages=378-400 | doi=10.1016/S0019-9958(68)90874-7 }}
 
* {{User:Richard Pinch/sandbox/Ref | author=J.H. van Lint | title=Introduction to Coding Theory | edition=2nd ed | publisher=Springer-Verlag | series=[[Graduate Texts in Mathematics|GTM]] | volume=86 | date=1992 | isbn=3-540-54894-7 | pages=111-113}}
 
 
=Selberg sieve=
 
=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.
 
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.
Line 211: Line 45:
  
 
=Separation axioms=
 
=Separation axioms=
 
{{subpages}}
 
 
In [[topology]], '''separation axioms''' describe classes of [[topological space]] according to how well the [[open set]]s of the topology distinguish between distinct points.
 
In [[topology]], '''separation axioms''' describe classes of [[topological space]] according to how well the [[open set]]s of the topology distinguish between distinct points.
  
Line 252: Line 84:
 
==References==
 
==References==
 
* {{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 }}
 
* {{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 }}
 
=Stably free module=
 
In [[mathematics]], a '''stably free module''' is a [[module (mathematics)|module]] which is close to being [[free module|free]].
 
 
==Definition==
 
A module ''M'' over a ring ''R'' is ''stably free'' if there exist free modules ''F'' and ''G'' over ''R'' such that
 
 
:<math> M \oplus F = G . \, </math>
 
 
==Properties==
 
* A module is stably free if and only if it possesses a finite [[free resolution]].
 
 
== See also ==
 
* [[Free object]]
 
 
==References==
 
* {{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 | page=840}}
 
 
 
=Stirling numbers=
 
 
In [[combinatorics]], the '''Stirling numbers''' count certain arrangements of objects into a given number of structures.  There are two kinds of Stirling number, depending on the nature of the structure being counted.
 
 
The Stirling number of the first kind ''S''(''n'',''k'') counts the number of ways ''n'' labelled objects can be arranged into ''k'' cycles: cycles are regarded as equivalent, and counted only once, if they differ by a [[cyclic permutation]], thus [ABC] = [BCA] = [CAB] but is counted as different from [CBA] = [BAC] = [ACB].  The order of the cycles in the list is irrelevant.
 
 
For example, 4 objects can be arranged into 2 cycles in eleven ways, so ''S''(4,2) = 11:
 
 
* [ABC],[D]
 
* [ACB],[D]
 
* [ABD],[C]
 
* [ADB],[C]
 
* [ACD],[B]
 
* [ADC],[B]
 
* [BCD],[A]
 
* [BDC],[A]
 
* [AB],[CD]
 
* [AC],[BD]
 
* [AD],[BC]
 
 
The Stirling number of the second kind ''s''(''n'',''k'') counts the number of ways ''n'' labelled objects can be arranged into ''k'' subsets: cycles are regarded as equivalent, and counted only once, if they have the same elements, thus {ABC} = {BCA} = {CAB} = {CBA} = {BAC} = {ACB}.  The order of the subsets in the list is irrelevant.
 
 
For example, 4 objects can be arranged into 2 subsets in seven ways, so ''s''(4,2) = 7:
 
 
* {ABC},{D}
 
* {ABD},{C}
 
* {ACD},{B}
 
* {BCD},{A}
 
* {AB},{CD}
 
* {AC},{BD}
 
* {AD},{BC}
 
 
==References==
 
* {{cite book | author=Ronald L. Graham | coauthors=Donald E. Knuth, Oren Patashnik | title=Concrete Mathematics | publisher=[[Addison Wesley]] | year=1989 | isbn=0-201-14236-8 | pages=243-253 }}
 
=Tau function=
 
In [[mathematics]], Ramanujan's '''tau function''' is an [[arithmetic function]] which may defined in terms of the [[Delta form]] by the formal infinite product
 
 
:<math>q \prod_{n=1}^\infty \left(1-q^n\right)^{24} = \sum_n \tau(n) q^n .\,</math>
 
 
Since Δ is a [[Hecke operator|Hecke]] [[eigenform]], the tau function is multiplicative, with [[formal Dirichlet series]] and Euler product
 
 
:<math> \sum_n \tau(n) n^{-s} = \prod_p \left(1 - \tau(p) p^{-s} + p^{11-2s} \right)^{-1} .\,</math>
 
 
  
 
=Turan sieve=
 
=Turan sieve=
Line 349: Line 119:
 
==References==
 
==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 }}
 
* {{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 }}
=Tutte matrix=
 
In [[graph theory]], the '''Tutte matrix''' <math>A</math> of a [[Graph (mathematics)|graph]] ''G'' = (''V'',''E'') is a matrix used to determine the existence of a [[perfect matching]]: that is, a set of edges which is incident with each vertex exactly once.
 
 
If the set of vertices ''V'' has 2''n'' elements then the Tutte matrix is a 2''n'' × 2''n'' matrix A with entries
 
 
::: <math>A_{ij} = \begin{cases} x_{ij}\;\;\mbox{if}\;(i,j) \in E \mbox{ and } i<j\\
 
-x_{ji}\;\;\mbox{if}\;(i,j) \in E \mbox{ and } i>j\\
 
0\;\;\;\;\mbox{otherwise} \end{cases}</math>
 
 
where the ''x''<sub>''ij''</sub> are indeterminates.  The [[determinant]] of this [[skew-symmetric]] matrix is then a polynomial (in the variables ''x<sub>ij</sub>'', ''i<j'' ): this coincides with the square of the [[pfaffian]] of the matrix ''A'' and is non-zero (as a polynomial) if and only if a perfect matching exists.  (It should be noted that this is not the [[Tutte polynomial]] of ''G''.)
 
 
The Tutte matrix is a generalisation of the [[Edmonds matrix]] for a balanced [[bipartite graph]].
 
 
==References==
 
*{{cite book|author=R. Motwani, P. Raghavan |title=Randomized Algorithms|publisher=Cambridge University Press|year=1995|page=167}}
 
*{{cite book|author=Allen B. Tucker|title=Computer Science Handbook|publisher=CRC Press|date=2004|isbn=158488360X|page=12.19}}
 
* {{cite journal|url= http://jlms.oxfordjournals.org/cgi/reprint/s1-22/2/107.pdf|title= The factorization of linear graphs.
 
|accessdate= 2008-06-15|author= W.T. Tutte|authorlink=W. T. Tutte|year= 1947|month= April|volume=22|journal=J. London Math. Soc.|pages=107-111|doi=10.1112/jlms/s1-22.2.107}}
 
 
 
 
=Weierstrass preparation theorem=
 
=Weierstrass preparation theorem=
 
In [[algebra]], the '''Weierstrass preparation theorem''' describes a canonical form for [[formal power series]] over a [[complete local ring]].
 
In [[algebra]], the '''Weierstrass preparation theorem''' describes a canonical form for [[formal power series]] over a [[complete local ring]].

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

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 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=30490