User:Richard Pinch/sandbox-12

Radical-inverse function

A function which maps positive integers to real numbers in the unit interval by reversing the expansion in a given base $b$. Let $n$ have the base $b$ expansion $$ n = \sum_{i=0}^k d_i b^i $$ where $0 \le d_i < b$ and $d_k \ne 0$; then the radical inverse $$ \phi_b(n) = \sum_{i=0}^k d_i b^{-1-i} \ . $$

The radical inverse function is used to construct sequences with low discrepancy: these are of use in quasi-Monte-Carlo methods.

The van der Corput sequence is the sequence $\left({\phi_2(n)}\right)$. The discrepancy $D_N$ of this sequence satisfies $$ N D_N \le \frac{\log(N+1)}{\log 2} \ . $$

References

• L. Kuipers, H. Niederreiter, "Uniform distribution of sequences" , Wiley (1974) Zbl 0281.10001; repr. Dover (2006) ISBN 0-486-45019-8

Dispersion

The dispersion of a sequence $x_n$ in a metric space $(X,d)$ is defined as the function $$ D_N = \sup_{x \in X} \min_{n=1,\ldots,N} d(x,x_n) \ . $$ The associated dispersion constant is $\limsup_{N\rightarrow\infty} N d_N$.

If a sequence has low discrepancy then its dispersion must also be low, but the converse does not hold.

Sequences with low dispersion play a part in quasi-Monte-Carlo methods for global optimisation problems.

References

• Harald Niederreiter, "On a measure of denseness for sequences", Topics in classical number theory, Colloq. Budapest 1981, Vol. II, Colloq. Math. Soc. János Bolyai 34 (1984) 1163-1208 Zbl 0547.10045

Subnormal series

A subnormal series (or subinvariant series) of a group $G$ is a subgroup series $$ E = G_0 \le G_1 \le \cdots \le G_n = G $$ in which each subgroup $G_i$ is a normal subgroup of $G_{i+1}$. The quotient groups $G_{i+1}/G_i$ are called factors, and the number $n$ is called the length of the subnormal series. Infinite subnormal series have also been studied (see Subgroup system). A subnormal series that cannot be refined further is called a composition series, and its factors are called composition factors.

A subnormal subgroup (also subinvariant, attainable or accessible) of $G$ is a subgroup that appears in some subnormal series of $G$. To indicate the subnormality of a subgroup $H$ in a group $G$, the notation $H \lhd\!\lhd G$ is used.

The property of a subgroup to be subnormal is transitive. An intersection of subnormal subgroups is again a subnormal subgroup. The subgroup generated by two subnormal subgroups need not be subnormal. A group $G$ all subgroups of which are subnormal satisfies the normalizer condition, i.e. all subgroups differ from their normalizers (cf. Normalizer of a subset). Such a group is therefore locally nilpotent.

A subnormal subgroup of $G$ that coincides with its commutator subgroup and whose quotient by its centre is simple is called a component of $G$. The product of all components of $G$ is known as the layer of $G$. It is an important characteristic subgroup of $G$ in the theory of finite simple groups, see e.g. [6].

References

[1]	M.I. Kargapolov, J.I. [Yu.I. Merzlyakov] Merzljakov, "Fundamentals of the theory of groups" , Springer (1979) (Translated from Russian)
[2]	A.G. Kurosh, "The theory of groups" , 1–2 , Chelsea (1955–1956) (Translated from Russian)
[3]	M. Hall jr., "The theory of groups" , Macmillan (1959) pp. Sect. 8.4
[4]	J.C. Lennox, S.E. Stonehewer, "Subnormal subgroups of groups" , Clarendon Press (1987)
[5]	D.J.S. Robinson, "A course in the theory of groups" , Springer (1982)
[6]	M. Suzuki, "Group theory" , 1–2 , Springer (1986)

Regular graph

An unoriented graph in which each vertex has the same degree.

A strongly regular graph is a regular graph in which any twp adjacent vertices have the same number of neighbours in common, and any two non-adjacent vertices have the same number of neighbours in common. The complement of a strongly regular graph is again strongly regular.

A distance regular graph is one with the property that for any two vertices $x,y$ the number of vertices at distance $i$ from $x$ and $j$ from $y$ depends only on $i$, $j$ and the distance $d(x,y)$.

References

• Richard A Brualdi, Herbert J. Ryser, "Combinatorial matrix theory", Cambridge University Press (2014) ISBN 978-0-521-32265-2 Zbl 0746.05002 Zbl 1286.05001
• Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier, "Distance-regular graphs" Springer (1989) ISBN 3-642-74343-6 Zbl 0747.05073

Dyck path

A lattice path on the square lattice from the origin $(0,0)$ to some point $(n,n)$ consisting of $2n$ steps of the form $N : (x,y) \rightarrow (x,y+1)$ and $E : (x,y) \rightarrow (x+1,y)$ with the property that the path never passes below the line $y=x$.

The number of Dyck paths of length $2n$ is given by the $n$-th Catalan number $$ C_n = \frac{1}{n+1}\binom{2n}{n} \ . $$

Catalan number

The $n$-th Catalan number $$ C_n = \frac{1}{n+1}\binom{2n}{n} \ . $$ The generating function is given by $$ \sum_{n=1}^\infty C_n z^n = \frac{1-\sqrt{1-4z}}{2z} \ . $$ The Catalan numbers appear in the enumeration of a number of combinatorially defined object:

• Bernoulli excursion
• Dyck paths
• Parenthesised sequences; words of the Dyck language
• Complete binary rooted plane trees

Poisson ratio

The ratio of longitudinal extension to lateral compression when an elastic substance is put under tension.

See: Elasticity, mathematical theory of; Lamé constants.

References

• Horace Lamb, "Statics", Cambridge University Press (1960)

Elastic modulus

Young's modulus

The ratio of longitudinal extension to force applied per unit area when an elastic substance is put under tension.

See: Elasticity, mathematical theory of; Lamé constants.

References

• Horace Lamb, "Statics", Cambridge University Press (1960)

Partition symbol

A notation used to compactly express propositions of partition calculus. The symbol $$ \alpha \rightarrow (\beta)_\gamma^r $$ for cardinals $\alpha,\beta,\gamma$ and natural number $r$, denotes the following proposition.

Given a set $S$ and a colouring of $S^r$ into a set of $\gamma$ colours, there exists a subset $T$ of $S$ of cardinality $|T|=\beta$ such that the colouring restricted to $T^r$ is monochrome.

Here a colouring of a set $X$ by a set of colours $C$ is simply a partition of $X$ into parts indexed by the set $C$.

The symbol $$ \alpha \rightarrow (\beta_1,\ldots,\beta_j)^r $$ denotes the following proposition:

Given a set $S$ of cardinality $\alpha$ and a colouring of $S^r$ by $j$ colours, there exists an index $i$ subset $T$ of $S$ of cardinality $|T|=\beta_i$ such that the colouring restricted to $T^r$ is monochrome.

Examples.

• Ramsey's theorem: $\omega \rightarrow (\omega)_n^r$.
• Sierpinski's theorem: $c \not\rightarrow (\omega_1,\omega_2)^2$.

References

• M.E. Rudin, "Lectures on set theoretic topology", Amer. Math. Soc. (1975) ISBN 0-8218-1673-X Zbl 0318.54001

Isthmus

bridge, co-loop

An isthmus of a graph is an edge for which deletion increases the number of connected components of the graph.

An isthmus of a matroid $M$ on a set $E$ is an element of $E$ which is in every basis for $M$. An element of $E$ is a co-loop of $M$ if and only if it is a loop of the dual matroid $M^*$, that is, does not belong to any base of $M^*$. If $M$ is a graphic matroid, then the definitions coincide.

References

• J. G. Oxley, "Matroid Theory" (2 ed) Oxford University Press (2011) ISBN 978-0-19-856694-6 Zbl 1254.05002
• D. J. A. Welsh, "Matroid Theory", Dover (2010) [1976] ISBN 0486474399 Zbl 0343.05002

Ordered topological space

A topological space $X$ with a partial order ${\le}$ related to the topology by the condition that if $x < y$ then there are neighbourhoods $N_x$, $N_y$ such that $x < y'$ for all $y' \in N_y$ and $x' < y$ for all $x' \in N_x$. An ordered topological space is necessarily a Hausdorff space.

An ordered topological space is totally order-disconnected if whenever $x \not\le y$ there exists a clopen down-set $D$ such that $x \not\in D$ and $y \in D$.

A Priestley space is a compact totally order-disconnected space. An Ockham space is a Priestley space equipped with an order-reversing continuous mapping $g$: see also Ockham algebra.

References

• Samuel Eilenberg, "Ordered Topological Spaces", American Journal of Mathematics 63 (1941) 39-45 DOI 10.2307/2371274 Zbl 0024.19203
• T.S. Blyth, "Lattices and ordered algebraic structures", Springer (2005) ISBN 1-85233-905-5 Zbl 1073.06001

Reed–Solomon code

A family of linear codes defined over finite fields. Let $F = \mathbf{F}_q$ and put $n = q-1$. Let $\beta$ be a primitive element of $F^*$. For an integer $k \le n$, let $L_k$ denote the vector space of polynomials over $F$ of degree $\le k-1$, and let $E$ be the evaluation map $e : L_k \rightarrow F^n$ given by $$ E : f \mapsto \left({ f(\beta), f(\beta^2), \ldots, f(\beta^n) }\right) \ . $$

The image $E[L_k]$ is a subspace of $F^n$ and constitutes the Reed–Solomon code $\mathrm{RS}(q,k)$. It is a primitive BCH code.

The map $E$ is injective, as a non-zero polynomial of degree $k<n$ cannot be zero at $n$ distinct values. The rank of the code is thus $k$. The minimum weight is $n-k+1$, corresponding to a polynomial with $k-1$ zeroes all in $F$. The Reed–Solomon code thus meets the singleton bound and is an MDS code.

More generally, we may prescribe a set of $n$ evaluation points, $k \le n \le q-1$, distinct elements $\mathbf{x} = (x_1,\ldots,x_n)$ of $F$, and non-zero weights $ \mathbf{y} = (y_i)$. The generalised Reed–Solomon code is defined by the evaluation map $$ E : f \mapsto \left({ y_1 f(x_1), \ldots, y_n f(x_n) }\right) \ . $$ The image is of rank $n$ and minimum weight $n-k+1$: it is denoted $\mathrm{GRS}_k(\mathbf{x}, \mathbf{y})$. The dual code is $\mathrm{GRS}_{n-k}(\mathbf{x}, \mathbf{y'})$ for some $ \mathbf{y'}$.

References

• C.M. Goldie, R.G.E. Pinch, Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) ISBN 0-521-40456-8 Zbl 0746.94001
• J.H. van Lint, "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics 86 Springer (1992) ISBN 3-540-54894-7 Zbl 0747.94018
• F.J. MacWilliams, N.J.A. Sloane, "The Theory of Error Correcting Codes", (Elsevier, 1977). Zbl 0369.94008
• H. Stichtenoth, "Algebraic function fields and codes", Universitext, Springer (1993) ISBN 3-540-58469-6 Zbl 0816.14011

Singleton bound

A constraint on the parameters of a linear block code. If a code has length $n$, rank $k$ and minimum distance $d$, then $$ k+d \le n+1 \ . $$ The bound is obtained by shortening a code $C$ by selecting the subcode consisting of all words with the symbol $0$ in a specific position and then deleting that position from all words.

A code for which equality holds is a maximum distance separable or MDS code. Examples of MDS codes are the Reed–Solomon codes, which show that if $n \le q+1$ there are MDS codes over $\mathbf{F}_q$ of rank $k$ for all $k< n$. The dual code to a linear MDS code is again an MDS code.

The MDS conjecture states that an MDS code with rank $k$ over the field of $q$ elements has length $n \le q+1$, except in the case $q$ a power of 2 and $k = 3$ or $q-1$ when $n \le q+2$. These bounds are achieved by Reed--Solomon codes.

References

• C.M. Goldie, R.G.E. Pinch, Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) ISBN 0-521-40456-8 Zbl 0746.94001
• J.H. van Lint, "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics 86 Springer (1992) ISBN 3-540-54894-7 Zbl 0747.94018
• F.J. MacWilliams, N.J.A. Sloane, "The theory of error-correcting codes. Parts I, II" (3rd repr.) North-Holland Mathematical Library 16 Elsevier (1985) ISBN 0-444-85193-3 Zbl 0657.94010
• H. Stichtenoth, "Algebraic function fields and codes", Universitext, Springer (1993) ISBN 3-540-58469-6 Zbl 0816.14011

BCH code

A cyclic code over a finite field. Fix length $n$ and ground field $\mathbf{F}_q$ and a design distance parameter $\delta$. Let $\beta$ be a primitive $n$-th root of unity in a suitable extension of $\mathbf{F}_q$. The generator of the cyclic code is the least common multiple $g$ of the minimal polynomials (over $\mathbf{F}_q$) of the elements $\beta^1, \beta^2, \ldots, \beta^{\delta-1}$.

The minimum distance of the BCH code generated by $g$ is at least $\delta$: this is the BCH bound.

As an example, let $q=2$ and $\beta$ be a primitive $7$-th root of unity in $\mathrm{F}_{8}$: we may take $\beta$ to satisfy the polynomial $x^3 + x + 1$. Choose $\delta = 3$. The minimal polynomial for $\beta^2$ is the same as that of $\beta$, so that the cyclic code is generated by the word $1101000$. This is in fact the Hamming [7,4] code.

References

• C.M. Goldie, R.G.E. Pinch, Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) ISBN 0-521-40456-8 Zbl 0746.94001

Hamming code

A binary block code capable of error correction: see Error-correcting code.

The Hamming $[7,4]$ code has generator matrix with first row $1101000$ and the others being its three right shifts. It is a cyclic code, and indeed a BCH code with design distance $3$. It is perfect, because the balls of radius $1$ about the codewords have eight elements and the 16 balls precisely fill out the 7-dimensional space.

References

• C.M. Goldie, R.G.E. Pinch, Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) ISBN 0-521-40456-8 Zbl 0746.94001

Cyclic code

A block code over a finite field for which the code words have cyclic symmetric: any cyclic permutation of a code word is again a code word. A linear code of length $n$ over the field $k$ may be identified with polynomials of degree $< n$ over $k$ in an indeterminate $X$: the cyclic symmetry condition states that the code is invariant under multiplication by $X$ modulo $X^n-1$, so that the code may be identified with an ideal of the quotient ring $k[X]/\langle X^n-1 \rangle$. Since the polynomial ring $k[X]$ is a principal ideal domain, the codes are all principal ideals, and hence are determined by their generators, which must be factors of $X^n-1$.

References

• C.M. Goldie, R.G.E. Pinch, Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) ISBN 0-521-40456-8 Zbl 0746.94001