User:Richard Pinch/sandbox-CZ

Justesen code

A class of error-correcting codes which are derived from Reed-Solomon codes and have good error-control properties.

Let $R$ be a Reed-Solomon code of length $N = 2^m-1$, rank $K$ and minimum weight $N-K+1$. The symbols of $R$ are elements of $F=GF(2^m)$ and the codewords are obtained by taking every polynomial $f$ over $F$ of degree less than $K$ and listing the values of $f$ on the non-zero elements of $F$ in some predetermined order. Let $\alpha$ be a primitive element of $F$. For a codeword $\mathbf{a} = (a_1,\ldots,a_N)$ from $R$, let $\mathbf{b}$ be the vector of length $2N$ over $F$ given by $$ \mathbf{b} = \left( a_1, a_1, a_2, \alpha^1 a_2, \ldots, a_N, \alpha^{N-1} a_N \right) $$ and let $\mathbf{c}$ be the vector of length $2Nm$ obtained from $\mathbf{b}$ by expressing each element of $F$ as a binary vector of length $m$. The Justesen code is the linear code containing all such $\mathbf{c}$.

The parameters of this code are length $2mN$, dimension $mK$ and minimum distance at least $$ \sum_{i=1}^l i \binom{2m}{i} \ . $$ The Justesen codes are examples of concatenated codes.

References

• J. Justesen; A class of constructive asymptotically good algebraic codes, IEEE Trans. Info. Theory, 18 (1972), pp. 652-656
• F.J. MacWilliams; N.J.A. Sloane; The Theory of Error-Correcting Codes, , pp. 306-316, North-Holland ISBN: 0-444-85193-3

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

• David Goss; Basic Structures of Function Field Arithmetic, , Springer Verlag ISBN: 3-540-63541-6 Chapter 1.

Morita conjectures

The Morita conjectures in topology ask

1. If X × Y is normal for every normal space Y, is X discrete?
2. If X × Y is normal for every normal P-space Y, is X metrizable ?
3. If X × 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 M.E. Rudin proved conjecture (1) and showed that conjecture (2) is true if the axiom of constructibility V=L, holds.

Z. Balogh proved conjectures (2) and (3).

References

• A.V. Arhangelskii, K.R. Goodearl, B. Huisgen-Zimmermann, Kiiti Morita 1915-1995, Notices of the AMS, June 1997 [1]

Partition function (number theory)

The function $p(n)$ that counts the number of partitions 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

• Tom M. Apostol; Modular functions and Dirichlet Series in Number Theory, ser. Graduate Texts in Mathematics 41 (1990), pp. 94-112, Springer-Verlag ISBN: 0-387-97127-0
• G.H. Hardy; E. M. Wright; An Introduction to the Theory of Numbers, (2008), pp. 361-392, Oxford University Press ISBN: 0-19-921986-5

Preparata code

A class of non-linear double-error-correcting codes. They are named after Franco P. Preparata who first described them in 1968.

Let m be an odd number, and n = 2^m-1. We first describe the extended Preparata code of length 2n+2 = 2^m+1: the Preparata code is then derived by deleting one position. The words of the extended code are regarded as pairs (X,Y) of 2^m-tuples, each corresponding to subsets of the finite field GF(2^m) in some fixed way.

The extended code contains the words (X,Y) satisfying three conditions

1. X, Y each have even weight;
2. \(\sum_{x \in X} x = \sum_{y \in Y} y\);
3. \(\sum_{x \in x} x^3 + \left(\sum_{x \in X} x\right)^3 = \sum_{y \in Y} y^3\).

The Peparata code is obtained by deleting the position in X corresponding to 0 in GF(2^m).

The Preparata code is of length 2^m+1-1, size 2^k where k = 2^m+1 - 2m - 2, and minimum distance 5.

When m=3, the Preparata code of length 15 is also called the Nordstrom–Robinson code.

References

• F.P. Preparata; A class of optimum nonlinear double-error-correcting codes, Information and Control, 13 (1968), pp. 378-400, DOI: 10.1016/S0019-9958(68)90874-7
• J.H. van Lint; Introduction to Coding Theory, ser. GTM 86 , pp. 111-113, Springer-Verlag ISBN: 3-540-54894-7

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

• 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

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

• Serge Lang; Algebra, (1993), p. 840, Addison-Wesley ISBN: 0-201-55540-9

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

• 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

• Template:Cite book