User:Richard Pinch/sandbox-7

Cocyclic group

A cogenerator of a group $G$ is an element $c$ such that for any homomorphism $\phi : G \rightarrow H$, then $c \not\in \ker\phi$ implies that $\phi$ is a monomorphism (injective as a map). A cocyclic group is a group with a cogenerator. An equivalent definition is that a cocyclic group has a non-trivial minimal subgroup $M$, or that the intersection $M$ of all non-trivial subgroups of $G$ is non-trivial. The elements of $M$ other than the identity are the cogenerators,

The cocyclic groups are the cyclic groups of prime power order and the quasi-cyclic groups.

The definition is dual to one characterisation of a generator $g$ of a cyclic group, that for every $\phi : H \rightarrow G$, if $g$ is in the image of $\phi$ then $\phi$ is an epimorphism (surjective as a map).

References

• László Fuchs, "Abelian groups" Springer (2015) ISBN 978-3-319-19421-9 Zbl 06457087

Wolstenholme theorem

Let $p$ be a prime number greater than 3. The numerator of the fraction $$ \frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{p-1} $$ is divisible by $p^2$.

An equivalent form of the theorem is that if $x^*$ denotes the solution to the equation $x x^* \equiv 1 \pmod {p^2}$ then $$ 1^* + 2^* + \cdots + (p-1)^* \equiv 0 \pmod{p^2} \ . $$

References

• G. H. Hardy, E. M. Wright,(with R. Heath-Brown, J. Silverman) "An Introduction to the Theory of Numbers" (6th ed.) Oxford University Press (2008) ISBN 0-19-921986-9 Zbl 1159.11001
• N. Rama Rao, "Some congruences modulo $m$" Bull. Calcutta math. Soc. 29 (1938) 167-170 Zbl 64.0097.02
• J. Wolstenholme, "On certain properties of prime numbers", Quart. J. Math. 5 (1862), 35-99

Baer ring

A Baer ring is a ring $R$ in which every left annihilator is generated by an idempotent element $e$. The analogous definitionin terms of right annihilators is equivalent . A Baer ring is necessarily a left and a right Rickart ring.

Examples of Baer rings include integral domains, and matrix rings over a field.

References

• Tsit-Yuen Lam, "Lectures on Modules and Rings" Graduate Texts in Mathematics 189 Springer (2012) ISBN 1461205255 Zbl 0911.16001

Polar body

Let $V$ be a real vector space with inner product $\langle , \rangle$. The polar set $X^\circ$ of a subset $X$ of $V$ is $$ X^\circ = \{ y \in V : \langle x,y \rangle \le 1 \ \text{for all}\ x \in X \} \ . $$

If $K$ is a convex set containing the zero element in its interior then $K^\circ$ is called the polar body of $K$ and is again a convex neighbourhood of the origin.

The support function of $X$ may be defined in terms of the polar set by $H_X(u)=\inf\left\{\rho > 0\colon u\in \rho X^\circ \right\}$, and similarly the distance function is given by $D_X(x)=\sup\left\{\langle x,u \rangle \colon u\in X^\circ \right\}$. Given a distance function $D(x)$, the corresponding closed convex set is defined by $X=\left\{x\in E^n\colon D(x)\leq 1\right\}$.

See also: Blaschke–Santaló inequality.

References

• Rolf Schneider, "Convex Bodies: The Brunn–Minkowski Theory" (2 ed.) Encyclopedia of Mathematics and its Applications 151 Cambridge University Press (2014} ISBN 1-107-60101-0 Zbl 1287.52001

Equaliser

An equaliser of two morphisms $f,g$ between the objects $X, Y$ of a category $\mathfrak{K}$ is a morphism $e : W \rightarrow X$ such that $ef = eh$ and any morphism $d : A \rightarrow X$ such that $df = dg$ factors through $e$, that is, there exists $c : A \rightarrow W$ such that $cd = e$. A coequaliser is the dual notion.

An equaliser in the category of sets exists: it is the inclusion map on $\{ x \in X : f(x) = g(x) \}$. Similarly, a co-equaliser exists: it is the quotient map on $X$ determined by the equivalence relation $\sim$ generated by $f(x) \sim g(x),\ x \in X$.

If $\mathfrak{J}$ is the category ${\downarrow}{\downarrow}$, and $F$ is a functor from $\mathfrak{J}$ to $\mathfrak{K}$, then a limit of $F$ is an equaliser and a colimit of $F$ is a coequaliser.

Every equaliser in a category $\mathfrak{K}$ is a monomorphism and every coequaliser is an epimorphism. A monomorphism (resp. epimorphism) which is an equaliser (resp. coequaliser) is termed regular.

References

• Saunders MacLane, "Categories for the working mathematician" Graduate Texts in Mathematics 5 Springer (1988) ISBN 0-387-98403-8 Zbl 0705.18001}

Developable space

A development in a topological space $X$ is a sequence of open covers $G_n$ such that for all points $x \in X$ the stars $$ \mathrm{St}(x,G_n) = \cup \{ U \in G_n : x \in U \} $$ form a local base for $x$. A developable space is a space with a development. A metric space is a developable space: the sequence of collections of open balls of radius $1/n$ forming a development. A Moore space is a regular space with a development. A collection-wise normal Moore space is metrizable.

A regular development has the further property that if $U,V \in G_{n+1}$ with $U \cap V \neq \emptyset$, then there is $W \in G_n$ with $U \cup V \subset W$. Alexandroff and Urysohn proved that a space is merizable if and only if it has a regular development.

References

• Alexandroff, P.; Urysohn, P. "Une condition nécessaire et suffisante pour qu’une classe $(\mathcal{L})$ doit une classe $(\mathcal{B})$", Comptes Rendus 177 (1923) 1274-1276. [1] Zbl 49.0702.06 Zbl 50.0696.01
• Bing, R.H. "Metrization of topological spaces", Canad. J. Math. 3 (1951) 175-186 DOI 10.4153/CJM-1951-022-3 Zbl 0042.41301

Triple system

In algebra, a triple system is a vector space $V$ over a field $K$ with a $k$-trilinear form $V \times V \times V \rightarrow V$. Examples include Jordan triple systems, Lie triple systems, Anti-Lie triple systems and Allison-Hein triple systems.

In combinatorics, a triple system is a type of Steiner system.

Cogalois extension

Let $L/K$ be an extension of fields and write $T(L/K) = \{ x \in L^* : \exists n\,\ x^n \in K \}$. The cogalois group of $K/L$ is $\mathrm{Cog}(L/K) = T(L/K) / K^*$. The extension $L/K$ is cogalois if $L$ is generated over $K$ by some linearly independent set of elements of $\mathrm{Cog}(L/K)$.

References

• Albu, Toma "Cogalois theory" Marcel Dekker (2003) ISBN 0-8247-0949-7 Zbl 1039.12001

Group presentation

A specification of a group by generators and relations among them.

Comments

Every group can be presented by means of generators and relations. A presentation is finitely generated, respectively finitely related, if the number of generators, respectively relations, is finite. A finite presentation is one with both a finite number of relations and a finite number of generators. A presentation of the symmetric group $S_n$ of permutations on $n$ letters is as follows: there are $n-1$ generators $\sigma_2,\ldots,\sigma_n$, and the relations are $\sigma_i^2 = e$, $\sigma_i\sigma_j = \sigma_j\sigma_i$ if $|i-j| \ge 2$, $\sigma_i \sigma_{i+1} \sigma_i = \sigma_{i+1} \sigma_i \sigma_{i+1}$. If the relations $\sigma_i^2 = e$ are removed, one obtains a presentation of the braid group $B_n$.

If $G$ is presented by generators $G_i,$, $i \in I$, and relations $R_j$, $j \in J$, one writes $G = \langle G_i | R_j \rangle$. In that case $G$ is the quotient group of the free group on the generators $G_i,$ by the normal subgroup generated by the relations $R_j$. For details cf. [a1], Sect. 1.2. Given a presentation of a group, there are systematic ways for obtaining presentations of subgroups and quotient groups.

References

[a1]	W. Magnus, A. Karrass, B. Solitar, "Combinatorial group theory: presentations of groups in terms of generators and relations" , Wiley (Interscience) (1966)
[a2]	H.S.M. Coxeter, W.O.J. Moser, "Generators and relations for discrete groups" , Springer (1965)

Comments

A presentation of a group $G$ is a pair $\langle X | R \rangle$ where $R$ is a subset of $F(X)$, the free group on the set $X$, and $G$ is isomorphic (cf. also Isomorphism) to the quotient group $F(X)/N(R)$, where $N(R)$ is the intersection of all normal subgroups of $F(X)$ containing $R$. The subgroup $N(R)$ is called the normal closure of $R$ in $F(X)$.

Given an arbitrary group $G$, there is an obvious homomorphism $\tau_G : F(G) \rightarrow G$ such that $\tau_G(g) = g$ for all $g \in G$. Clearly, $\langle G | \ker \tau_G \rangle$ is a presentation for $G$.

Partial recursive function

All known examples of algorithms may be reduced to the problem of computing the values of a suitable function. Taking this feature as the fundamental property, Church, Gödel and Kleene defined a wide class of functions, which they named partial recursive. Let $F$ be the class of partial functions, with domains of definition and ranges of values in the set of natural numbers. The following operations are defined on the set $F$:

a) superposition (composition) of functions: If $f,\alpha_1,\ldots,a_m \in F$, then one says that the function $$ \phi(x_1,\ldots,x_n) = f(\alpha_1(x_1,\ldots,x_n),\ldots,\alpha_m(x_1,\ldots,x_n)) $$ is obtained from $f,\alpha_1,\ldots,a_m$ by composition;

b) the $\mu$ or least-number operator: Let $f_1,f_2 \in F$; one says that a function $\psi$ is obtained from $f_1$ and $f_2$ with the aid of the $\mu$-operator, written as $$ \psi(x_1,\ldots,x_n) = \mu y [f_1,f_2,(x_1,\ldots,x_n),y] $$ if $f_1(x_1,\ldots,x_n,z)$ and $f_2(x_1,\ldots,x_n,z)$ are defined and are unequal for $z<y$ and if $$ f_1(x_1,\ldots,x_n,y) = f_2(x_1,\ldots,x_n,y) $$ and then $$ \psi(x_1,\ldots,x_n) = y \ . $$

Clearly, if these operations are applied to functions the values of which one can compute, then there exist algorithms for computing the values of the functions $\phi$ and $\psi$. The following functions are considered to be the simplest: ${+},{\times}$, $\mathrm{pr}_i : ( x_1,\ldots,x_n) \mapsto x_i$, and $$ k(x,y) = \begin{cases} 1 & \ \text{if}\ x < y \\ 0 & \ \text{otherwise} \end{cases} \ . $$

There exist easy algorithms which serve to compute the values of the simplest functions.

A function $f$ is called partial recursive if it can be obtained by a finite number of steps from the simplest functions using the composition and the $\mu$-operator. A partial recursive function which is everywhere defined is called general recursive. The value of any partial recursive function may be effectively computed in the intuitive sense. The converse of this statement is known as Church's thesis: Any function the value of which can be effectively computed is partial recursive. Thus, according to Church's thesis, computable functions are partial recursive.

Regressive function

A one-one function $t$ on the natural numbers is regressive if there is a partial recursive function $p$ defined on the range of $t$ such that $p(t(n+1)) = t(n)$ for $n \ge 0$ and $p(t(0)) = t(0)$. The function $p$ is a regressing function for $t$ if in addition $p\circ p$ is defined and for each $x$ in the domain of $p$ there is $k = k(x)$ such that $p^{(k+1)}(x) = p^{(k)}(x)$. It is known that if $t$ is regressive then there is a regressing function for $t$. It is known that a function recursively equivalent to a regressive function is again regressive.

A regressive set is one which is finite or the range of a regressive function; a retraceable set is one which is finite or the range of a strictly increasing regressive function. It is known that a retraceable set is either recursive or immune.

References

• Barback, J. "Two notes on regressive isols" Pac. J. Math. 16 (1966) 407-420 DOI 10.2140/pjm.1966.16.407 Zbl 0199.02503
• H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967)

Augmentation

An augmentation map for an algebra $A$ over a ring $R$ is a map $\epsilon : A \to R$. The term is also used for the co-unit of a co-algebra. An augmented algebra is an algebra with an specified augmentation. The corresponding augmentation ideal of $A$ is the kernel of $\epsilon$.

There are natural augmentation maps for certain classes of algebra. For group rings $R[G]$ the augmentation map is $\epsilon : g \mapsto 1$ for each element $g \in G$.

References

• Mac Lane, Saunders, "Homology" Reprint of the 3rd corr. print. Classics in Mathematics. Berlin: Springer (1995)[1975] ISBN 3-540-58662-8 Zbl 0818.18001

Algebraically closed group

A group $G$ for which every finite system of equations soluble over $G$ is already soluble in $G$. Every group can be embedded in in an algebraically closed group. Such groups are simple and not finitely generated. Every group with soluble word problem can be embedded in every algebraic group and conversely. An algebraically closed group cannot have a recursive presentation.

Scott initially defined a group to be algebraically closed if it has the defining property for systems of equations and inequations and called a group "weakly algebraically closed" if this holds for systems of equations; it was proved by B.H. Neumann that the two properties are equivalent. The term existentially closed group is now used.

References

• Scott, W.R. "Algebraically closed groups" Proc. Am. Math. Soc. 2 (1951) 118-121 DOI 10.1090/S0002-9939-1951-0040299-6 Zbl 0043.02302
• Neumann, B.H. A note on algebraically closed groups J. Lond. Math. Soc. 27 (1952) 247-249 DOI 10.1112/jlms/s1-27.2.247 Zbl 0046.24802
• Higman, Graham; Scott, Elizabeth "Existentially closed groups" London Mathematical Society Monographs, New Series, 3 . Clarendon Press (1988) Zbl 0646.20001
• Ol’shanskij, A.Yu.; Shmel’kin, A.L. Infinite groups in "Algebra. IV: Infinite groups, linear groups", Kostrikin, A.I. (ed.); Shafarevich, I.R. (ed.); Gamkrelidze, R.V. (ed.) Encyclopaedia of Mathematical Sciences 37 Springer (1993) Zbl 0782.00033 Zbl 0787.20001

Baire metric

A metric on a countably infinite $X^{\mathbf{N}}$ product of copies of a set $X$. Regarding the elements of $X^{\mathbf{N}}$ as sequences $(x_n)$ of elements of $X$, define $d((x_n),(y_n)$ as $1/m$ where $m$ is the least index $i$ such that $x_i \ne y_i$; the distance $d(x_n),(x_n))$ is taken to be zero. The Baire metric is complete, since each component of the elements of a Cauchy sequence is ultimately constant.

When $X$ is a countably infinite set with the discrete topology, the Baire metric defines the product topology on $X^{\mathbf{N}}$. The space is separable and zero-dimensional, totally disconnected and with no isolated points.

When $X$ is $\mathbf{R}$ with the usual topology, then the Baire metric defines a topology strictly finer than the product.

Observe that the Baire space is the topological product of countably many copies of the natural numbers $\mathbb N$ endowed with the discrete topology. Moreover it is homeomorphic to the irrational numbers endowed with the topology of subset of $\mathbb R$. Any zero-dimensional separable metric space of dimension zero can be embedded in the Baire space. Moreover, for every Polish space $\mathcal{M}$ there is a continuous surjection from the Baire space onto $\mathcal{M}$ (see Theorem 1A.1 of [Mo]).

Comments

By the Baire category theorem the latter space is a Baire space in the sense of the first definition.

References

[SS]	Steen, Lynn Arthur; Seebach, J.Arthur jun. Counterexamples in topology (2nd ed.) Springer (1978) ISBN 0-387-90312-7 Zbl 0386.54001
[Mo]	Y. Moschovakis, "Descriptive set theory". Studies in Logic and the Foundations of Mathematics, 100. North-Holland Publishing Co., Amsterdam-New York, 1980. MR0561709 Zbl 0433.03025

Sierpinski metric

A metric on a countably infinite set $X = \{x_1,x_2,\ldots\}$. For $i \ne j$ define $d(x_i,x_j) = 1 + 1/(i+j)$, and $d(x_i,x_i) = 0$. The Sierpinski metric is complete, since every Cauchy sequence is ultimately constant. The induced topology is the discrete topology.

References

• Steen, Lynn Arthur; Seebach, J.Arthur jun. Counterexamples in topology (2nd ed.) Springer (1978) ISBN 0-387-90312-7 Zbl 0386.54001

Tightness

Tightness or tight has several meanings.

A bound or inequality may be described as tight if no stronger inequality is valid.

A tight measure.

A property of an immersion of a manifold into Euclidean space: see Tight and taut immersions.

A cardinal characteristic of a topological space.

One-pair matrix

single-pair matrix

A square $n \times n$ matrix $A$ over a field $K$ of special form: there exist scalars $u_i,v_i$, $i=1,\ldots,n$ such that $$ A_{ij} = \begin{cases} u_i v_j & \text{if}\ i \ge j \\ u_j v_i &\ \text{if}\ i \le j \end{cases} \ . $$

The inverse of a one-pair matrix is a symmetric tridiagonal matrix and vice versa.

References

• Gantmacher, F.R.; Krein, M.G. "Oscillation matrices and kernels and small vibrations of mechanical systems". Translation based on the 1941 Russian original. Edited and with a preface by Alex Eremenko. AMS Chelsea Publishing (2002) ISBN 0-8218-3171-2 Zbl 1002.74002

Fréchet metric

A metric which can be placed on a countable product of metric spaces . If $(X_i,d_i)$ is a countable sequence of metric spaces with uniformly bounded metrics then the function on the product space defined by $$ d((x_i),(y_i)) = \sum_i 2^{-i} d_i(x_i,y_i) $$ is a metric on the product space $\prod_i X_i$: the corresponding topology is just the product topology. If the metrics $d_i$ are not uniformly bounded then they may be replaced by equivalent bounded metrics $d_i'$ such as $\max\{d_i,1\}$ or $d_i/(1+d_i)$ in this definition.

References

• Steen, Lynn Arthur; Seebach, J.Arthur jun. Counterexamples in topology (2nd ed.) Springer (1978) ISBN 0-387-90312-7 Zbl 0386.54001

Pre-topological space

Let $X$ be a set and $\mathcal{P}X$ the set of subsets of $X$. A pre-topological space structure on $X$ is defined by a Čech closure operator, a mapping $C : \mathcal{P}X \rightarrow \mathcal{P}X$ such that

C1) $C(\emptyset) = \emptyset$;

C2) $A \subseteq C(A)$;

C3) $C(A \cup B) = C(A) \cup C(B)$.

A set $A$ in $X$ is closed if $A = C(A)$.

A mapping between pre-topological spaces $f : X \rightarrow Y$ is continuous if $f(C_X(B)) \subseteq C_Y(f(B))$ for any $B \subseteq C$.

If the operator $C$ also satisfies (C4) $C(C(A)) = C(A)$, then $S$ is a topological space with $C$ as the Kuratowski closure operator.

References

[1]	N.M. Martin, S. Pollard, "Closure spaces and logic" , Kluwer Acad. Publ. (1996)
[2]	J.L. Kelley, "General topology" , Graduate Texts in Mathematics 27 Springer (1975) ISBN 0-387-90125-6 Zbl 0306.54002
[3]	D. Dikranjan, W. Tholin, "Categorical structures of closure operators" , Kluwer Acad. Publ. (1996)
[4]	Jürgen Jost, "Mathematical Concepts", Springer (2015) ISBN 331920436X

Quadratic number field

An extension $K$ of the field of rational numbers of degree 2. Any such extension is of the form $K = \mathbf{Q}(\sqrt d)$ where $d$ is a square-free integer, $d \neq 0,1$. If $d>0$ then $K$ is a real quadratic field, and there are two embeddings of $K$ into the field of real numbers; if $d < 0$ then $K$ is an imaginary quadratic field and has no embeddings into $\mathbf{R}$.

A quadratic number field is a Galois extension of $\mathbf{Q}$ with Galois group cyclic of order 2 generated by $\sigma : x + y\sqrt{d} \mapsto x - y\sqrt{d}$.

The discriminant $D_K$ is given by $D = d$ if $d \equiv 1 \pmod 4$, otherwise $D = 4d$.

The ring of integers $\mathcal{O}_K$ is $\mathbf{Z}[(1+\sqrt{d})/2]$ if $d \equiv 1 \pmod 4$, otherwise $\mathbf{Z}[\sqrt{d}]$.

Automatic sequence

The Thue–Morse sequence is a typical example of a $k$-automatic sequence. Actually, like every fixed point of a substitution of constant length, it can be generated by a finite machine, called a finite automaton (cf. Automaton, finite), as follows. A $k$-automaton is given by a finite set of states $S$, one state being called the initial state, by $k$ mappings from $S$ into itself (denoted by $0,\dots,k-1$) and by an output mapping $\phi$ from $S$ into a given set $Y$. Such an automaton generates a sequence with values in $Y$ as follows: Feed the automaton with the digits of the base-$k$ expansion of $n$, starting with the initial state; then define $u_n$ as the image under $\phi$ of the reached state. In the Thue–Morse case, the automaton has two states, say $\{A,B\}$, the mapping $0$ maps each state to itself whereas the mapping $1$ exchanges both states $A \leftrightarrow B$, the output mapping is the identity mapping and the state $A$ is the initial state.

Automatic sequences have many nice characterizations (see, for instance, [a8]). Automatic sequences are exactly the letter-to-letter images of fixed points of constant-length substitutions. Furthermore, this is equivalent to the fact that the following subset of subsequences (called the $k$-kernel) $$ \left\lbrace{ \left({ u_{k^ t n+r} }\right)_n : t \ge 0\,,\ 0 \le r \le t^k-1 }\right\rbrace $$ is finite or, in the case $k$ is a prime power, to the fact that the series $\sum u_n Z^n$ is algebraic over $\mathbf{F}_k(Z)$. Note that, on the other hand, the real number that has, as dyadic expansion, the Thue–Morse sequence is transcendental. For more references and connections with physics, see [a3].

Define the Rudin–Shapiro sequence $v = (v_n)$ that counts modulo $2$ the number of $11$s (possibly with overlap) in the base-$2$ expansion of $n$. The sequence $v$ is easily seen to have a finite $2$-kernel and hence to be $2$-automatic. This sequence was introduced independently by W. Rudin and H.S. Shapiro (see the references in [a6]) in order to minimize uniformly $\left|{ \sum_{n=0}^{N-1} a_n e^{int} }\right|$, for a sequence $a_n$ defined over $\{ \pm 1 \}$. The Rudin–Shapiro sequence achieves $$ \sup_{t} \left|{ \sum_{n=0}^{N-1} v_n e^{int} }\right| \le (2+\sqrt 2)\sqrt{N} \ . $$

References

[a1]	P. Borwein, C. Ingalls, "The Prouhet–Tarry–Escott problem revisited" Enseign. Math. , 40 (1994) pp. 3–27
[a2]	F.M. Dekking, "What is the long range order in the Kolakoski sequence" , The Mathematics Of Long-Range Aperiodic Order (Waterloo, ON, 1995) , NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. , 489 , Kluwer Acad. Publ. (1997) pp. 115–125
[a3]	"Beyond Quasicrystals: Actes de l'École de Physique Théorique des Houches" F. Axel (ed.) et al. (ed.) , Springer (1995)
[a4]	M. Lothaire, Combinatorics on Words (2nd ed.) Encyclopedia of Mathematics and Its Applications 17' Cambridge University Press (1997) ISBN 0-521-59924-5 Zbl 0874.20040
[a5]	M. Morse, "Recurrent geodesics on a surface of negative curvature" Trans. Amer. Math. Soc. , 22 (1921) pp. 84–100
[a6]	M. Queffélec, "Substitution dynamical systems. Spectral analysis" , Lecture Notes Math. , 1294 , Springer (1987)
[a7]	A. Thue, "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen" , Selected Math. Papers of Axel Thue , Universiteitsforlaget (1977) (Published in 1912)
[a8]	J.-P. Allouche, "Automates finis en théorie des nombres" Experim. Math. , 5 (1987) pp. 239–266

• Allouche, Jean-Paul; Shallit, Jeffrey Automatic Sequences: Theory, Applications, Generalizations Cambridge University Press (2003) ISBN 978-0-521-82332-6 Zbl 1086.11015
• Lothaire, M. Algebraic Combinatorics on Words Encyclopedia of Mathematics and Its Applications 90 Cambridge University Press (2011 [2002]) ISBN 978-0-521-18071-9 Zbl 1221.68183
• Pytheas Fogg, N. (ed.) Substitutions in dynamics, arithmetics and combinatorics Lecture Notes in Mathematics 1794 Springer (2002) ISBN 978-3-540-44141-0 Zbl 1014.11015
• Berlekamp, E., Conway, J.H., Guy R.K. Winning Ways, for Your Mathematical Plays Academic Press (1982) Zbl 0485.00025

Rudin–Shapiro sequence

The sequence $v = (v_n)$ that counts modulo $2$ the number of $11$s (possibly with overlap) in the base-$2$ expansion of $n$. The sequence $v$ is easily seen to have a finite $2$-kernel and hence to be $2$-automatic. This sequence was introduced independently by W. Rudin and H.S. Shapiro (see the references in [a6]) in order to minimize uniformly $\left|{ \sum_{n=0}^{N-1} a_n e^{int} }\right|$, for a sequence $a_n$ defined over $\{ \pm 1 \}$. The Rudin–Shapiro sequence achieves $$ \sup_{t} \left|{ \sum_{n=0}^{N-1} v_n e^{int} }\right| \le (2+\sqrt 2)\sqrt{N} \ . $$

The dynamical system generated by the Rudin–Shapiro sequence $v$ is strictly ergodic (cf. also Ergodic theory), since the underlying substitution are primitive (see, for instance, [a6]). It provides an example of a system with finite spectral multiplicity and a Lebesgue component in the spectrum. For more references on the ergodic, spectral and harmonic properties of substitutive sequences, see [a6].

References

[a1]	P. Borwein, C. Ingalls, "The Prouhet–Tarry–Escott problem revisited" Enseign. Math. , 40 (1994) pp. 3–27
[a2]	F.M. Dekking, "What is the long range order in the Kolakoski sequence" , The Mathematics Of Long-Range Aperiodic Order (Waterloo, ON, 1995) , NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. , 489 , Kluwer Acad. Publ. (1997) pp. 115–125
[a3]	"Beyond Quasicrystals: Actes de l'École de Physique Théorique des Houches" F. Axel (ed.) et al. (ed.) , Springer (1995)
[a4]	M. Lothaire, Combinatorics on Words (2nd ed.) Encyclopedia of Mathematics and Its Applications 17' Cambridge University Press (1997) ISBN 0-521-59924-5 Zbl 0874.20040
[a5]	M. Morse, "Recurrent geodesics on a surface of negative curvature" Trans. Amer. Math. Soc. , 22 (1921) pp. 84–100
[a6]	M. Queffélec, "Substitution dynamical systems. Spectral analysis" , Lecture Notes Math. , 1294 , Springer (1987)
[a7]	A. Thue, "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen" , Selected Math. Papers of Axel Thue , Universiteitsforlaget (1977) (Published in 1912)
[a8]	J.-P. Allouche, "Automates finis en théorie des nombres" Experim. Math. , 5 (1987) pp. 239–266

• Allouche, Jean-Paul; Shallit, Jeffrey Automatic Sequences: Theory, Applications, Generalizations Cambridge University Press (2003) ISBN 978-0-521-82332-6 Zbl 1086.11015
• Lothaire, M. Algebraic Combinatorics on Words Encyclopedia of Mathematics and Its Applications 90 Cambridge University Press (2011 [2002]) ISBN 978-0-521-18071-9 Zbl 1221.68183
• Pytheas Fogg, N. (ed.) Substitutions in dynamics, arithmetics and combinatorics Lecture Notes in Mathematics 1794 Springer (2002) ISBN 978-3-540-44141-0 Zbl 1014.11015
• Berlekamp, E., Conway, J.H., Guy R.K. Winning Ways, for Your Mathematical Plays Academic Press (1982) Zbl 0485.00025

Ordered magma

ordered groupoid

A magma $H$ whose elements are partially ordered by a relation $\le$ satisfying the axioms $$ a \le b \Rightarrow ac \le bc\ ,\ \ ca \le cb\ \ \ \text{for all}\ c \in H \ . $$

If an ordered magma $H$ satisfies the stronger axiom $$ a < b \Rightarrow ac < bc\ ,\ \ ca < cb\ \ \ \text{for all}\ c \in H \ . $$ then the order on $H$ is called strict, and $H$ is a strictly (partially) ordered groupoid. A partially ordered groupoid $H$ is said to be strong if $$ ac \le bc \ \text{and}\ ca \le cb \Rightarrow a \le b \ . $$

A strongly partially ordered groupoid is always strict, and for totally ordered groupoids the two concepts coincide.

An element $a$ of an ordered groupoid $H$ is called positive (strictly positive) if the inequalities $ax \ge x$ and $xa \ge x$ (respectively, $ax > x$ and $xa > x$) hold for all $x \in H$. Negative and strictly negative elements are defined by the opposite inequalities. An ordered groupoid is called positively (negatively) ordered if all its elements are positive (negative). Some special types of ordered groupoids are of particular interest (cf. Naturally ordered groupoid; Ordered semi-group; Ordered group).

Comments

The terminology "ordered groupoid" refers to the use of the word "groupoid" as a synomym for magma. Groupoids in the alternative sense also occur naturally with orderings in various contexts: for example, the groupoid of all partial automorphisms of an algebraic or topological structure (that is, isomorphisms between its substructures — e.g. the groupoid of diffeomorphisms between open subsets of a smooth manifold) is naturally ordered by the relation: $f \le g$ if $f$ is the restriction of $g$ to a subset of its domain. Ordered groupoids of this type are of importance in differential geometry (see [a1]). More generally, any inverse semi-group (cf. Inversion semi-group) $S$ can be regarded as a groupoid, whose objects are the idempotent elements of $S$, and where the domain and codomain of an element $s$ are $s^{-1}s$ and $s s^{-1}$, respectively; here the objects have a natural meet semi-lattice ordering, and the order can also be defined on morphisms in a natural way (see [a2]).

A naturally ordered magma is a partially ordered magma $H$ in which all elements are positive (that is, $a\leq ab$ and $b\leq ab$ for any $a,b\in H$) and the larger of two elements is always divisible (on both the left and the right) by the smaller, that is, $a<b$ implies that $ax=ya=b$ for some $x,y\in H$. The positive cone of any partially ordered group (cf. Ordered group) is a naturally ordered semi-group.

References

[a1]	Ch. Ehresmann, "Structures locales et catégories ordonnés" , Oeuvres complètes et commentées , Supplément aux Cahiers de Topologie et Géométrie Différentielle Catégoriques , Partie II (1980)
[a2]	J.M. Howie, "An introduction to semigroup theory" , Acad. Press (1976)
[b1]	L. Fuchs, "Partially ordered algebraic systems" , Pergamon (1963)

Cycle notation

A way of expressing a permutation $\pi$ of a finite set $A$ by displaying it as a product of cyclic permutations on its orbits. The notation $(a_1\,a_2\,\ldots\,a_k)$, for some $k \ge 1$ expresses that $\pi$ maps $a_1 \mapsto a_2$, $a_2 \mapsto a_3$ and so on, and $a_k \mapsto a_1$. If $k=1$, the cycle $(a)$ denotes that $a$ is a fixed point of $\pi$; if $k=2$ the notation $(a\,b)$ denotes that $\pi$ acts as a transposition: $a \mapsto b$ and $b \mapsto a$. The cycle notation for $\pi$ contains every element of $A$ just once. The cycle shape of $\pi$ is the sequence $1^{n_1} 2^{n_2} \cdots$ where $n_i$ denotes the number of cycles of length $i$.

The cycle notation is not unique, since a cycle $(a_1\,a_2\,\ldots\,a_k)$ is equal to the cycle $(a_2\,\ldots\,a_k\,a_1)$ and so on, and disjoint cycles can be written in any order. A standard form in the case $A = \{1,\ldots,n\}$ can be obtained by prescribing that the first (leading) element in each cycle should be the largest element and that cycles should be listed in increasing order of their leading element.

References

• Riordan, John "Introduction to Combinatorial Analysis", Wiley [1958] Dover (2002) ISBN 0-486-42536-3 Zbl 0078.00805

Difference ring

A difference ring is a ring $R$ with an automorphism $\alpha$. The elements of $R$ fixed pointwise by $\alpha$ form the subring of "constants". A difference ideal is an ideal $I$ of $R$ invariant under $\alpha$. More generally one may consider a system $\sigma$ of commuting automorphisms.

References

• Marius van der Put, Michael F. Singer. "Galois theory of difference equations" Lecture Notes in Mathematics 1666 Springer (1997) ISBN 3-540-63243-3 Zbl 0930.12006

Identity

An equality that holds true for all values of the variables involved within some domain of valididy.

A condition that holds true for all elements of some algebraic structures.

A neutral element for a binary operation.

A map from a set to itself which maps each element to itself.

Baer radical

of a ring $R$

The intersection of the prime ideals of the ring $R$. It is an instance of a radical: it is the lower radical determined by the class of all nilpotent rings; and the upper radical determined by the class of all primary rings.

References

• Sapir, Mark V. "Combinatorial algebra: syntax and semantics" with contributions by Victor S. Guba and Mikhail V. Volkov. Springer Monographs in Mathematics. Springer (2014) ISBN 978-3-319-08030-7 Zbl 1319.05001

Krawtchouk polynomials

Polynomials orthogonal on the finite system of $N+1$ integer points whose distribution function $\sigma(z)$ is a step function with discontinuities: $$ \sigma(x+) - \sigma(x-) = \binom{N}{x} p^x q^{N-x} \,,\ \ \ x=0,\ldots,N $$ where $\binom{\cdot}{\cdot}$ is the binomial coefficient, $p,q > 0$ and $p+q = 1$. The Krawtchouk polynomials are given by the formulas $$ P_n(x) = \left[ \binom{N}{x} \right]^{-1/2} (pq)^{-n/2} \sum_{k=0}^n (-1)^{n-k} \binom{N-x}{n-k} \binom{x}{k} p^{n-k} q^k \ . $$ Here $\binom{x}{k}$ denotes the polynomial $$ \binom{x}{k} = \frac{x(x-1)\cdots(x-k+1)}{k!} $$ of degree $k$ in $x$

The concept is due to M.F. Krawtchouk [1].

References

[1]	M.F. Krawtchouk, "Sur une généralisation des polynômes d'Hermite" C.R. Acad. Sci. Paris , 189 (1929) pp. 620–622
[2]	G. Szegö, "Orthogonal polynomials" , Amer. Math. Soc. (1975)

Comments

Krawtchouk polynomials can be written as hypergeometric functions of type ${}_2F_1$. The unitarity relations for the matrix elements of the irreducible unitary representations of the group $SU(2)$ can be rewritten as the orthogonality relations for the Krawtchouk polynomials, cf. [a2], [a3]. These polynomials have also an interpretation as spherical functions on wreath products of symmetric groups, cf. [a4], where $q$-Krawtchouk polynomials are also treated. Coding theorists rather (but equivalently) relate them to Hamming schemes, where Krawtchouk polynomials are used for dealing with problems about perfect codes, cf. [a1].

References

[a1]	J.H. van Lint, "Introduction to coding theory" , Springer (1982)
[a2]	T.H. Koornwinder, "Krawtchouk polynomials, a unification of two different group theoretic interpretations" SIAM J. Math. Anal. , 13 (1982) pp. 1011–1023
[a3]	V.B. Uvarov, "Special functions of mathematical physics" , Birkhäuser (1988) (Translated from Russian)
[a4]	D. Stanton, "Orthogonal polynomials and Chevalley groups" R.A. Askey (ed.) T.H. Koornwinder (ed.) W. Schempp (ed.) , Special functions: group theoretical aspects and applications , Reidel (1984) pp. 87–128

Comments

A simpler version of the polynomials may be written as $$ K_n(x) = \sum_{k=0}^n (-1)^{n-k} \binom{N-x}{n-k} \binom{x}{k} p^{n-k} q^k \ . $$ The orthogonality relation is then $$ \sum_{i=0}^n \binom{n}{i} (q-1)^i K_r(i)K_s(i) = \delta_{rs} \binom{n}{r} (q-1)^r q^n \ . $$

There is a generating function $$ \sum_{k=0}^\infty K_r(x) z^k = (1-z)^x (1 + (q-1)z)^{n-x} \ . $$

Distance enumerator

The distribution of Hamming distances between elements of a code, expressed as a polynomial. Let $C$ be a code of length $n$ over an alphabet $F$ and let $A_k$ be the number of pairs $x,y$ of words of $C$ of at Hamming distance $d(x,y) = k$. The weight enumerator $$ W_C(z) = \sum_{k=0}^n A_k z^k = \sum_{x,y \in C} z^{d(x,y)} \ . $$ It is also common to express the weight enumerator as a homogeneous binary form $$ W_C(x,y) = \sum_{k=0}^n A_k x^k y^{n-k} \ . $$

We have $W_C(0) = |C|$ and $W_C(1) = |C|^2$, where $|C|$ is the number of words in $C$.

The weight enumerator similarly expresses the distribution of Hamming weights of elements of a code, expressed as a polynomial. Let $C$ be a code of length $n$ over an alphabet $F$ and let $A_k$ be the number of of words of $C$ of weight $k$. The weight enumerator $$ W_C(z) = \sum_{k=0}^n A_k z^k = \sum_{x \in C} z^{w(x)} $$ where $w(x)$ is the weight of the word $x$. It is also common to express the weight enumerator as a homogeneous binary form $$ W_C(x,y) = \sum_{k=0}^n A_k x^k y^{n-k} \ . $$

We have $W_C(0) = 1$ or $0$, depending on whether the zero word is in $C$ or not, and $W_C(1) = |C|$, the number of words in $C$.

The MacWilliams identities relate the weight enumerator of a linear code over a finite field $\mathbf{F}_q$ to the enumerator of the dual code $C^\perp$: $$ W_{C^\perp}(x,y) = \frac{1}{|C|} W_C(x + (q-1)y, x-y) \ . $$

References

• Goldie, Charles M.; Pinch, Richard G.E. Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) iSBN 0-521-40456-8 Zbl 0746.94001
• van Lint, J.H., "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics 86 Springer (1992) ISBN 3-540-54894-7 Zbl 0747.94018