Namespaces
Variants
Actions

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

From Encyclopedia of Mathematics
Jump to: navigation, search
(Start article: Tutte matrix)
(Start article: Turan sieve)
Line 1: Line 1:
 +
=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.
 +
 +
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
 +
 +
:<math>S(A,P,z) = \left\vert A \setminus \bigcup_{p \in P(z)} A_p \right\vert . </math>
 +
 +
We assume that |''A''<sub>''d''</sub>| may be estimated, when ''d'' is a prime ''p'' by
 +
 +
:<math> \left\vert A_p \right\vert = \frac{1}{f(p)} X + R_p  </math>
 +
 +
and when ''d'' is a product of two distinct primes ''d'' = ''p'' ''q'' by
 +
 +
:<math> \left\vert A_{pq} \right\vert = \frac{1}{f(p)f(q)} X + R_{p,q}  </math>
 +
 +
where ''X'' &nbsp; = &nbsp; |''A''| and ''f'' is a function with the property that 0 &le; ''f''(''d'') &le; 1.  Put
 +
 +
:<math> U(z) = \sum_{p \mid P(z)} f(p) . </math>
 +
 +
Then
 +
 +
:<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>
 +
 +
==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.
 +
 +
==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 }}
 
=Tutte matrix=
 
=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.
 
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.

Revision as of 06:46, 8 September 2013

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

Tutte matrix

In graph theory, the Tutte matrix \(A\) of a 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 2n elements then the Tutte matrix is a 2n × 2n matrix A with entries

\[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}\]

where the xij are indeterminates. The determinant of this skew-symmetric matrix is then a polynomial (in the variables xij, 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


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


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