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

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

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

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