User:Richard Pinch/sandbox-7

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.

Sign of a permutation

The sign of a permutation of a finite set, which we can identify with $\{1,2,\ldots,n\}$ for some $n$, is a multiplicative map $\epsilon$ from the groups of permutations to $\pm 1$. Permutations with sign $+1$ are even and those with sign $-1$ are odd. The sign may be defined in a number of ways. A simple formula is $$ \epsilon(\pi) = \frac{\prod_{1 \le i < j \le n} (x^{\pi(i)}-x^{\pi(j)})}{\prod_{1 \le i < j \le n} (x^i-x^j)} \ .\label{1} $$

The sign of $\pi$ may also be defined by the parity of the number of transpositions which compose $\pi$: this is well-defined since an odd number of transpositions cannot give the identity. A related definition is that the sign is the parity of $n - c$ where $c = c(\pi)$ is the number of cycles (orbits) of $\pi$.

Since $\epsilon$ is a homomorphism from $S_n$ to $C_2 = \{\pm1\}$, the alternating group, or group of even permutations, $A_n$ is the kernel of $\epsilon$ and so a normal subgroup of the symmetric group.

The definition of $\epsilon$ may be extended to maps which are not permutations by defining it to be zero. This is consistent with (1) and also with the use of the Kronecker symbol in tensor notation.

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