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

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

1. $\langle x,y,y \rangle = y$
2. $\langle x,y,z \rangle = \langle z,x,y \rangle$
3. $\langle x,y,z \rangle = \langle x,z,y \rangle$
4. $\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

• Birkhoff, Garrett; Kiss, ; A ternary operation in distributive lattices, Bull. Amer. Math. Soc., 53 , pp. 749-752
• Isbell, John R.; Median algebra, Trans. Amer. Math. Soc., 260 , pp. 319-362
• Knuth, Donald E.; Introduction to combinatorial algorithms and Boolean functions, ser. The Art of Computer Programming 4.0 , pp. 64-74 ISBN: 0-321-53496-4

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 field discriminant of $K$ is equal to the discriminant of the minimal polynomial of $\alpha$.

Examples of monogenic fields include:

• Quadratic fields: 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 fields: 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

• Narkiewicz, Władysław; Elementary and Analytic Theory of Algebraic Numbers, (2004), pp. 64, Springer-Verlag 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

• 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]

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 numbers. 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 and monotone.

Examples

• The Hardy–Ramanujan theorem: the normal order of $\omega(n)$, the number of distinct prime factors of $n$, is $\log\log n$;
• The normal order of $\log d(n))$, where $d(n)$ is the number of divisors of $n$, is $\log 2 \log\log n$.

References

• G.H. Hardy; S. Ramanujan; The normal number of prime factors of a number, Quart. J. Math., 48 (1917), pp. 76–92
• G.H. Hardy; E.M. Wright; An Introduction to the Theory of Numbers, (2008), pp. 473, Oxford University Press ISBN: 0-19-921986-5
• Gérald Tenenbaum; Introduction to Analytic and Probabilistic Number Theory, ser. Cambridge studies in advanced mathematics 46 (1995), pp. 299-324, Cambridge University Press ISBN: 0-521-41261-7

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

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

• 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