User:Richard Pinch/sandbox-7

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.

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) SBN 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 weightss 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