User:Richard Pinch/sandbox-7

Height, in Diophantine geometry

A certain numerical function on the set of solutions of a Diophantine equation (cf. Diophantine equations). In the simplest case of a solution in integers $(x_0,\ldots,x_n)$ of a Diophantine equation, the height is a function of the solution, and equals $\max\{|x_i|\}$. It is encountered in this form in Fermat's method of descent. Let $X$ be a projective algebraic variety defined over a global field $K$. The height is a class of real-valued functions $h_L(P)$ defined on the set $X(K)$ of rational points $P$ and depending on a morphism $L:X\rightarrow P^n$ of the variety $X$ into the projective space $P^n$. Each function in this class is also called a height. From the point of view of estimating the number of rational points there are no essential differences between the functions in this class: for any two functions $h'$ and $h''$ there exist constants $c',c'' > 0$, such that $c' h' \le h'' \le c''h'$. Such functions are called equivalent, and this equivalence is denoted (here) as $\cong$.

Fundamental properties of the height. The function $h_L(P)$ is functorial with respect to $P$, i.e. for any morphism $f:X \rightarrow Y$ and morphism $L : Y \rightarrow P^n$, $$ h_{f*L}(P) \cong h_L(f(P))\,\ \ P \in X(K) \ . $$

If the morphisms $L$, $L_1$ and $L_2$ are defined by invertible sheaves $\mathcal{L}$, $\mathcal{L}_1$ and $\mathcal{L}_2$, and if $\mathcal{L} = \mathcal{L}_1 \otimes \mathcal{L}_2$, then $h_L \cong h_{L_1} h_{L_2}$. The set of points $P \in X(K)$ of bounded height is finite in the following sense: If the basic field $K$ is an algebraic number field, the set is finite; if it is an algebraic function field with field of constants $k$, the elements of $X(K)$ depend on a finite number of parameters from the field $k$; in particular, $X(K)$ is finite if the field $k$ is finite. Let $|\cdot|_\nu$ run through the set of all norms of $K$. One may then define the height of a point $(x_0:\cdots:x_n)$ of the projective space $P^n$ with coordinates from $K$ as \begin{equation}\label{eq:1} \prod_\nu \max(|x_0|_\nu,\ldots,|x_n|_\nu) \ . \end{equation}

This is well defined because of the product formula $\prod_nu |x|_\nu = 1$ for $x \in K$. Let $X$ be an arbitrary projective variety over $K$ and let $L$ be a closed imbedding of $X$ into the projective space; the height $h_L$ may then be obtained by transferring the function \eqref{eq:1}, using the imbedding $L$, to the set $X(K)$. Various projective imbeddings, corresponding to the same sheaf $\mathcal{L}$, define equivalent functions on $X(K)$. A linear extension yields the desired function $h_L$. The function $h_L$ is occasionally replaced by its logarithm — the so-called logarithmic height.

The above estimates may sometimes follow from exact equations [3], [4], [5]. There is a variant of the height function — the Néron–Tate height — which is defined on Abelian varieties and behaves as a functor with respect to the morphisms of Abelian varieties preserving the zero point. For the local aspect see [6]. The local components of a height constructed there play the role of intersection indices in arithmetic.

References

[1]	A. Weil, "Number theory and algebraic geometry" , Proc. Internat. Congress Mathematicians (Cambridge, 1950) , 2 , Amer. Math. Soc. (1952) pp. 90–100 MR0045416 Zbl 0049.02802
[2]	S. Lang, "Diophantine geometry" , Interscience (1962) MR0142550 Zbl 0115.38701
[3]	D. Mumford, "Abelian varieties" , Oxford Univ. Press (1974) (Appendix in Russian translation: Yu.I. Manin; The Mordell–Weil theorem (in Russian)) MR2514037 MR1083353 MR0352106 MR0441983 MR0282985 MR0248146 MR0219542 MR0219541 MR0206003 MR0204427 Zbl 0326.14012
[4]	Yu.I. Manin, "Height of theta points on an Abelian manifold, their variants and applications" Izv. Akad. Nauk SSSR Ser. Mat. , 28 (1964) pp. 1363–1390 (In Russian)
[5]	D. Mumford, "A remark on Mordell's conjecture" Amer. J. Math. , 87 (1965) pp. 1007–1016 MR186624
[6]	A. Néron, "Quasi-fonctions et hauteurs sur les variétés abéliennes" Ann. of Math. (2) , 82 (1965) pp. 249–331 MR0179173 Zbl 0163.15205

Comments

The notion of height is a major tool in arithmetic algebraic geometry. It plays an important role in Faltings' proof of the Tate conjecture on endomorphisms of Abelian varieties over number fields, the Shafarevich conjecture that there are only finitely many isomorphism classes of Abelian varieties over a number field over $K$ of given dimension $g\ge1$ with good reduction outside a finite set of places $S$ of $K$, and the Mordell conjecture on the finiteness of the set of rational points $X(K)$ of a smooth curve of genus $g \ge 2$ over a number field $K$. Heights also play an important role in Arakelov intersection theory, which via moduli spaces of algebraic curves has also become important in string theory in mathematical physics.

References

[a1]	G. Faltings (ed.) G. Wüstholtz (ed.) , Rational points , Vieweg (1986) MR0863887 Zbl 0636.14019

Nottingham group

The subgroup of automorphisms of the field of formal power series $\mathbf{F_p}[[t]]$ consisting of those automorphisms of the form $f(t) \mapsto f(g(t))$ where $g(t) \in t + O(t^2)$.

It is a finitely generated, just infinite pro-$p$ group of finite width. However, every separable pro-$p$ group can be embedded in it as a closed subgroup.

References

• Rachel D. Camina, "Subgroups of the Nottingham group" J. Algebra 196 (1997) 101-113 Zbl 0883.20015

Triple

A collection of three objects, $x,y,z$. In an ordered triple the order of the elements is significant, so that $(x,y,z)$ is not in general equal to $(x,z,y)$, for example, unless $y=z$.

"Triple" can refer to Monad.

See also: Triple product, Triple system as instances of ternary operations in algebra; see also Triad in algebraic topology; Trio in formal language theory.

Cogalois extension

Let $L/K$ be a field extension 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

Solvable extension

A field extension $E/F$ which is separable, of finite degree and for which there is an extension $S/E$ such that $S/F$ is Galois with solvable Galois group.

Solvable extensions form a distinguished class of extensions.

References

• Serge Lang, "Algebra" (3 ed.) Graduate Texts in Mathematics 211 Springer (2005) ISBN 0-387-95385-X

Radical extension

A field extension $E/F$ which is generated by radicals.

Radical extensions form a distinguished class of extensions.

References

• Serge Lang, "Algebra" (3 ed.) Graduate Texts in Mathematics 211 Springer (2005) ISBN 0-387-95385-X
• Steven Roman, "Field Theory", Graduate Texts in Mathematics 158 Springer (2005) ISBN 0-387-27677-7

Pure extension

A field extension $E/F$ with the property that for any prime $p$, if the $p$-th roots of unity are in $E$, then they are already in $F$.

References

• Serge Lang, "Algebra" (3 ed.) Graduate Texts in Mathematics 211 Springer (2005) ISBN 0-387-95385-X
• Steven Roman, "Field Theory", Graduate Texts in Mathematics 158 Springer (2005) ISBN 0-387-27677-7

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$. The augmentation ideal is the kernel of this augmentation map.

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

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

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 endomorphism $\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$. If $\alpha$ is an automorphism then $R$ is inversive.

More generally one may consider a system $\sigma$ of commuting endomorphisms.

References

• Alexander Levin, "Difference Algebra", Algebra and Applications 8 Springer (2008) ISBN 1-4020-6947-2 Zbl 1209.12003
• 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 validity.

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