User:Richard Pinch/sandbox-CZ

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₁ 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

• User:Richard Pinch/sandbox/ref
• User:Richard Pinch/sandbox/ref
• User:Richard Pinch/sandbox/ref
• User:Richard Pinch/sandbox/ref
• User:Richard Pinch/sandbox/ref

Sober space

A topological space in which every irreducible closed set has a unique generic point. Here a closed set is irreducible if it is not the union of two non-empty proper closed subsets of itself.

Any Hausdorff space is sober, since the only irreducible subsets are singletons. Any sober spaces is a T0 space. However, sobriety is not equivalent to the T1 space condition: an infinite set with the cofinite topology is T1 but not sober whereas a Sierpinski space is sober but not T1.

A sober space is characterised by its lattice of open sets. An open set in a sober space is again a sober space, as is a closed set.

References

• User:Richard Pinch/sandbox/ref
• User:Richard Pinch/sandbox/ref
• User:Richard Pinch/sandbox/ref

Srivastava code

A class of parameterised error-correcting codes. They are block linear codes which are a special case of alternant codes.

The original Srivastava code of length $n$ and parameter $s$ over $GF(q)$ isdefined by an $n \times s$ parity check matrix $H$ of alternant form $$ \begin{bmatrix} \frac{\alpha_1^\mu}{\alpha_1-w_1} & \cdots & \frac{\alpha_n^\mu}{\alpha_n-w_1} \\ \vdots & \ddots & \vdots \\ \frac{\alpha_1^\mu}{\alpha_1-w_s} & \cdots & \frac{\alpha_n^\mu}{\alpha_n-w_s} \\ \end{bmatrix} $$ where the $\alpha_i$ and $z_i$ are elements of $GF(q^m)$.

The parameters of this code are length $n$, dimension $\ge n - ms$ and minimum distance $\ge s+1$.

References

• User:Richard Pinch/sandbox/ref

Stably free module

In mathematics, a stably free module is a module which is close to being free.

Definition

A module M over a ring R is stably free if there exist free modules F and G over R such that

\[ M \oplus F = G . \, \]

Properties

• A module is stably free if and only if it possesses a finite free resolution.

See also

• Free object

References

• Template:Cite book

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

• Template:Cite book

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

\[q \prod_{n=1}^\infty \left(1-q^n\right)^{24} = \sum_n \tau(n) q^n .\,\]

Since Δ is a Hecke eigenform, the tau function is multiplicative, with formal Dirichlet series and Euler product

\[ \sum_n \tau(n) n^{-s} = \prod_p \left(1 - \tau(p) p^{-s} + p^{11-2s} \right)^{-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 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₁ 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

• Template:Cite book

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

• Template:Cite book
• Template:Cite book
• Template:Cite journal

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

• Template:Cite book

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

• Template:Cite book