# User:Richard Pinch/sandbox-12

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} \ .$$

# 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)$.

# 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:

# Poisson ratio

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

#### 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.

#### 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$.

# 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.

# 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.

# Reed–Solomon code

A family of codes defined over finite fields. Let $k = \mathbf{F}_q$ and put $n = q-1$. Let $\beta$ be a primitive element of $k^*$. For an integer $k \le n$, let $L_q$ denote the vector space of polynomials over $k$ of degree $\le k-1$, and let $E$ be the evaluation map $e : L_k \rightarrow k^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 $k^n$ and is the Reed–Solomon code $\mathrm{RS}(q,k)$.

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 $k$. The Reed–Solomon code thus meets the singleton bound and is an MDS code.

# 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 puncturing a code $C$ by selecting all the words with the symbol $0$ in a specific location and then deleting that symbol 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$.

# 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
How to Cite This Entry:
Richard Pinch/sandbox-12. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-12&oldid=42957