User:Richard Pinch/sandbox-7

Composition

A composition of a natural number $n$ is an expression of $n$ as an ordered sum of positive integers. Thus the compositions of $4$ are $4, 3+1, 1+3, 2+2, 2+1+1, 2+1+1, 1+1+2, 1+1+1+1$. The underlying partition of a compisition is the corresponding unordered sum.

A composition on $ns may be represented as a sequence of $n$ dots separated by bars with no two bars adjacent: thus $4 = 1+2+1$ is represented by $( \bullet \vert \bullet\bullet \vert \bullet )$. The number of compositions of $n$ into $k$ parts is thus $\left({ \begin{array}{cc} n-1 \\ k-1 \end{array} }\right)$ and the total number of compositions of $n$ is thus $2^{n-1}$ ===='"`UNIQ--h-1--QINU`"'References==== * Luoto, Kurt; Mykytiuk, Stefan; van Willigenburg, Stephanie, "An introduction to quasisymmetric Schur functions. Hopf algebras, quasisymmetric functions, and Young composition tableaux", Springer (2013) ISBN 978-1-4614-7299-5 [https://zbmath.org/?q=an%3A1277.16027 Zbl 1277.16027] ='"`UNIQ--h-2--QINU`"'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 ring]]s $R[G]$ the augmentation map is $\epsilon : g \mapsto 1$ for each element $g \in G$. ===='"`UNIQ--h-3--QINU`"'References==== * Mac Lane, Saunders, "Homology" Reprint of the 3rd corr. print. Classics in Mathematics. Berlin: Springer (1995)[1975] ISBN 3-540-58662-8 [https://zbmath.org/?q=an%3A0818.18001 Zbl 0818.18001] ='"`UNIQ--h-4--QINU`"'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. ===='"`UNIQ--h-5--QINU`"'References==== * Scott, W.R. "Algebraically closed groups" ''Proc. Am. Math. Soc.'' '''2''' (1951) 118-121 [https://doi.org/10.1090/S0002-9939-1951-0040299-6 DOI 10.1090/S0002-9939-1951-0040299-6 ] [https://zbmath.org/?q=an%3A0043.02302 Zbl 0043.02302] * Neumann, B.H. ''A note on algebraically closed groups'' ''J. Lond. Math. Soc.'' '''27''' (1952) 247-249 [https://doi.org/10.1112/jlms/s1-27.2.247 DOI 10.1112/jlms/s1-27.2.247] [https://zbmath.org/?q=an%3A0046.24802 Zbl 0046.24802] * Higman, Graham; Scott, Elizabeth "Existentially closed groups" London Mathematical Society Monographs, New Series, '''3''' . Clarendon Press (1988) [https://zbmath.org/?q=an%3A0646.20001 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) [https://zbmath.org/?q=an%3A0782.00033 Zbl 0782.00033] [https://zbmath.org/?q=an%3A0787.20001 Zbl 0787.20001] ='"`UNIQ--h-6--QINU`"'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 metric space|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}}$. When $X$ is $\mathbf{R}$ with the usual topology, then the Baire metric defines a topology strictly finer than the product. ===='"`UNIQ--h-7--QINU`"'References==== * Steen, Lynn Arthur; Seebach, J.Arthur jun. ''Counterexamples in topology'' (2nd ed.) Springer (1978) ISBN 0-387-90312-7 [https://zbmath.org/?q=an%3A0386.54001 Zbl 0386.54001] ='"`UNIQ--h-8--QINU`"'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 metric space|complete]], since every [[Cauchy sequence]] is ultimately constant. The induced topology is the [[discrete topology]]. ===='"`UNIQ--h-9--QINU`"'References==== * Steen, Lynn Arthur; Seebach, J.Arthur jun. ''Counterexamples in topology'' (2nd ed.) Springer (1978) ISBN 0-387-90312-7 [https://zbmath.org/?q=an%3A0386.54001 Zbl 0386.54001] ='"`UNIQ--h-10--QINU`"'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. ='"`UNIQ--h-11--QINU`"'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 '"`UNIQ-MathJax2-QINU`"' The inverse of a one-pair matrix is a symmetric [[tridiagonal matrix]] and vice versa. ===='"`UNIQ--h-12--QINU`"'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 [https://zbmath.org/?q=an%3A1002.74002 Zbl 1002.74002] ='"`UNIQ--h-13--QINU`"'Fréchet metric= A [[metric]] which can be placed on a countable product of [[metric space]]s . 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 '"`UNIQ-MathJax3-QINU`"' 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. ===='"`UNIQ--h-14--QINU`"'References==== * Steen, Lynn Arthur; Seebach, J.Arthur jun. ''Counterexamples in topology'' (2nd ed.) Springer (1978) ISBN 0-387-90312-7 [https://zbmath.org/?q=an%3A0386.54001 Zbl 0386.54001] ='"`UNIQ--h-15--QINU`"'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]]. ===='"`UNIQ--h-16--QINU`"'References==== <table> <tr><td valign="top">[1]</td> <td valign="top"> N.M. Martin, S. Pollard, "Closure spaces and logic" , Kluwer Acad. Publ. (1996)</td></tr> <tr><td valign="top">[2]</td> <td valign="top"> J.L. Kelley, "General topology" , Graduate Texts in Mathematics '''27''' Springer (1975) ISBN 0-387-90125-6 [https://zbmath.org/?q=an%3A0306.54002 Zbl 0306.54002]</td></tr> <tr><td valign="top">[3]</td> <td valign="top"> D. Dikranjan, W. Tholin, "Categorical structures of closure operators" , Kluwer Acad. Publ. (1996)</td></tr> <tr><td valign="top">[4]</td> <td valign="top"> Jürgen Jost, "Mathematical Concepts", Springer (2015) ISBN 331920436X</td></tr> </table> ='"`UNIQ--h-17--QINU`"'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}]$. ='"`UNIQ--h-18--QINU`"'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|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, [[#References|[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) '"`UNIQ-MathJax4-QINU`"' 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 [[#References|[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 [[#References|[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 '"`UNIQ-MathJax5-QINU`"' ===='"`UNIQ--h-19--QINU`"'References==== <table> <tr><td valign="top">[a1]</td> <td valign="top"> P. Borwein, C. Ingalls, "The Prouhet–Tarry–Escott problem revisited" ''Enseign. Math.'' , '''40''' (1994) pp. 3–27</td></tr> <tr><td valign="top">[a2]</td> <td valign="top"> 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</td></tr> <tr><td valign="top">[a3]</td> <td valign="top"> "Beyond Quasicrystals: Actes de l'École de Physique Théorique des Houches" F. Axel (ed.) et al. (ed.) , Springer (1995)</td></tr> <tr><td valign="top">[a4]</td> <td valign="top"> M. Lothaire, ''Combinatorics on Words'' (2nd ed.) Encyclopedia of Mathematics and Its Applications '''17'''' Cambridge University Press (1997) ISBN 0-521-59924-5 [https://zbmath.org/?q=an%3A0874.20040 Zbl 0874.20040]</td></tr> <tr><td valign="top">[a5]</td> <td valign="top"> M. Morse, "Recurrent geodesics on a surface of negative curvature" ''Trans. Amer. Math. Soc.'' , '''22''' (1921) pp. 84–100</td></tr> <tr><td valign="top">[a6]</td> <td valign="top"> M. Queffélec, "Substitution dynamical systems. Spectral analysis" , ''Lecture Notes Math.'' , '''1294''' , Springer (1987)</td></tr> <tr><td valign="top">[a7]</td> <td valign="top"> A. Thue, "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen" , ''Selected Math. Papers of Axel Thue'' , Universiteitsforlaget (1977) (Published in 1912)</td></tr> <tr><td valign="top">[a8]</td> <td valign="top"> J.-P. Allouche, "Automates finis en théorie des nombres" ''Experim. Math.'' , '''5''' (1987) pp. 239–266</td></tr> </table> * Allouche, Jean-Paul; Shallit, Jeffrey ''Automatic Sequences: Theory, Applications, Generalizations'' Cambridge University Press (2003) ISBN 978-0-521-82332-6 [https://zbmath.org/?q=an%3A1086.11015 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 [https://zbmath.org/?q=an%3A1221.68183 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 [https://zbmath.org/?q=an%3A1014.11015 Zbl 1014.11015] * Berlekamp, E., Conway, J.H., Guy R.K. ''Winning Ways, for Your Mathematical Plays'' Academic Press (1982) [https://zbmath.org/?q=an%3A0485.00025 Zbl 0485.00025] ='"`UNIQ--h-20--QINU`"'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 [[#References|[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 '"`UNIQ-MathJax6-QINU`"' 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, [[#References|[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 [[#References|[a6]]]. ===='"`UNIQ--h-21--QINU`"'References==== <table> <tr><td valign="top">[a1]</td> <td valign="top"> P. Borwein, C. Ingalls, "The Prouhet–Tarry–Escott problem revisited" ''Enseign. Math.'' , '''40''' (1994) pp. 3–27</td></tr> <tr><td valign="top">[a2]</td> <td valign="top"> 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</td></tr> <tr><td valign="top">[a3]</td> <td valign="top"> "Beyond Quasicrystals: Actes de l'École de Physique Théorique des Houches" F. Axel (ed.) et al. (ed.) , Springer (1995)</td></tr> <tr><td valign="top">[a4]</td> <td valign="top"> M. Lothaire, ''Combinatorics on Words'' (2nd ed.) Encyclopedia of Mathematics and Its Applications '''17'''' Cambridge University Press (1997) ISBN 0-521-59924-5 [https://zbmath.org/?q=an%3A0874.20040 Zbl 0874.20040]</td></tr> <tr><td valign="top">[a5]</td> <td valign="top"> M. Morse, "Recurrent geodesics on a surface of negative curvature" ''Trans. Amer. Math. Soc.'' , '''22''' (1921) pp. 84–100</td></tr> <tr><td valign="top">[a6]</td> <td valign="top"> M. Queffélec, "Substitution dynamical systems. Spectral analysis" , ''Lecture Notes Math.'' , '''1294''' , Springer (1987)</td></tr> <tr><td valign="top">[a7]</td> <td valign="top"> A. Thue, "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen" , ''Selected Math. Papers of Axel Thue'' , Universiteitsforlaget (1977) (Published in 1912)</td></tr> <tr><td valign="top">[a8]</td> <td valign="top"> J.-P. Allouche, "Automates finis en théorie des nombres" ''Experim. Math.'' , '''5''' (1987) pp. 239–266</td></tr> </table> * Allouche, Jean-Paul; Shallit, Jeffrey ''Automatic Sequences: Theory, Applications, Generalizations'' Cambridge University Press (2003) ISBN 978-0-521-82332-6 [https://zbmath.org/?q=an%3A1086.11015 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 [https://zbmath.org/?q=an%3A1221.68183 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 [https://zbmath.org/?q=an%3A1014.11015 Zbl 1014.11015] * Berlekamp, E., Conway, J.H., Guy R.K. ''Winning Ways, for Your Mathematical Plays'' Academic Press (1982) [https://zbmath.org/?q=an%3A0485.00025 Zbl 0485.00025] ='"`UNIQ--h-22--QINU`"'Ordered magma= ''ordered groupoid'' A [[magma]] $H$ whose elements are partially ordered by a relation $\le$ satisfying the axioms '"`UNIQ-MathJax7-QINU`"' If an ordered magma $H$ satisfies the stronger axiom '"`UNIQ-MathJax8-QINU`"' 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 '"`UNIQ-MathJax9-QINU`"' 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]]). ===='"`UNIQ--h-23--QINU`"'Comments==== The terminology "ordered groupoid" refers to the use of the word "groupoid" as a synomym for [[magma]]. [[Groupoid]]s 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 [[#References|[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 [[#References|[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. ===='"`UNIQ--h-24--QINU`"'References==== <table> <tr><td valign="top">[a1]</td> <td valign="top"> 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)</td></tr> <tr><td valign="top">[a2]</td> <td valign="top"> J.M. Howie, "An introduction to semigroup theory" , Acad. Press (1976)</td></tr> <tr><td valign="top">[b1]</td> <td valign="top"> L. Fuchs, "Partially ordered algebraic systems" , Pergamon (1963)</td></tr> </table> ='"`UNIQ--h-25--QINU`"'Cycle notation= A way of expressing a [[permutation]] $\pi$ of a finite set $A$ by displaying it as a product of [[cyclic permutation]]s on its [[orbit]]s. 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. ='"`UNIQ--h-26--QINU`"'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. ===='"`UNIQ--h-27--QINU`"'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 [https://zbmath.org/?q=an%3A0930.12006 Zbl 0930.12006] ='"`UNIQ--h-28--QINU`"'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. ===='"`UNIQ--h-29--QINU`"'References==== ='"`UNIQ--h-30--QINU`"'Baer radical= ''of a ring'' $R$ The intersection of the [[prime ideal]]s of the ring $R$. It is an instance of a [[Radical of rings and algebras|radical]]: it is the [[lower radical]] determined by the class of all [[Nilpotent algebra|nilpotent ring]]s; and the [[upper radical]] determined by the class of all [[primary ring]]s. ===='"`UNIQ--h-31--QINU`"'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 [https://zbmath.org/?q=an%3A1319.05001 Zbl 1319.05001] ='"`UNIQ--h-32--QINU`"'Krawtchouk polynomials= Polynomials orthogonal on the finite system of $N+1$ integer points whose distribution function $\sigma(z)$ is a step function with discontinuities: '"`UNIQ-MathJax10-QINU`"' where $\binom{\cdot}{\cdot}$ is the [[Binomial coefficients|binomial coefficient]], $p,q > 0$ and $p+q = 1$. The Krawtchouk polynomials are given by the formulas '"`UNIQ-MathJax11-QINU`"' Here $\binom{x}{k}$ denotes the polynomial '"`UNIQ-MathJax12-QINU`"' of degree $k$ in $x$ The concept is due to M.F. Krawtchouk [[#References|[1]]]. ===='"`UNIQ--h-33--QINU`"'References==== <table> <tr><td valign="top">[1]</td> <td valign="top"> M.F. Krawtchouk, "Sur une généralisation des polynômes d'Hermite" ''C.R. Acad. Sci. Paris'' , '''189''' (1929) pp. 620–622</td></tr> <tr><td valign="top">[2]</td> <td valign="top"> G. Szegö, "Orthogonal polynomials" , Amer. Math. Soc. (1975)</td></tr> </table> ===='"`UNIQ--h-34--QINU`"'Comments==== Krawtchouk polynomials can be written as [[hypergeometric function]]s 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. [[#References|[a2]]], [[#References|[a3]]]. These polynomials have also an interpretation as spherical functions on [[wreath product]]s of symmetric groups, cf. [[#References|[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. [[#References|[a1]]]. ===='"`UNIQ--h-35--QINU`"'References==== <table> <tr><td valign="top">[a1]</td> <td valign="top"> J.H. van Lint, "Introduction to coding theory" , Springer (1982)</td></tr> <tr><td valign="top">[a2]</td> <td valign="top"> T.H. Koornwinder, "Krawtchouk polynomials, a unification of two different group theoretic interpretations" ''SIAM J. Math. Anal.'' , '''13''' (1982) pp. 1011–1023</td></tr> <tr><td valign="top">[a3]</td> <td valign="top"> V.B. Uvarov, "Special functions of mathematical physics" , Birkhäuser (1988) (Translated from Russian)</td></tr> <tr><td valign="top">[a4]</td> <td valign="top"> 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</td></tr> </table> ===='"`UNIQ--h-36--QINU`"'Comments==== A simpler version of the polynomials may be written as '"`UNIQ-MathJax13-QINU`"' The orthogonality relation is then '"`UNIQ-MathJax14-QINU`"' There is a generating function '"`UNIQ-MathJax15-QINU`"' ='"`UNIQ--h-37--QINU`"'Distance enumerator= The distribution of [[Hamming distance]]s 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 '"`UNIQ-MathJax16-QINU`"' It is also common to express the weight enumerator as a homogeneous binary form '"`UNIQ-MathJax17-QINU`"' 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 weight]]s 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 '"`UNIQ-MathJax18-QINU`"' where $w(x)$ is the weight of the word $x$. It is also common to express the weight enumerator as a homogeneous binary form '"`UNIQ-MathJax19-QINU`"' 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