Namespaces
Variants
Actions

Difference between revisions of "User:Richard Pinch/sandbox-7"

From Encyclopedia of Mathematics
Jump to: navigation, search
(copy article: Krawtchouk polynomials)
Line 1: Line 1:
 +
=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 coefficients|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 [[#References|[1]]].
 +
 +
====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>
 +
 +
 +
 +
====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]]].
 +
 +
====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>
 +
 +
====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=
 
=Distance enumerator=
  

Revision as of 11:26, 18 September 2016

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
How to Cite This Entry:
Richard Pinch/sandbox-7. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-7&oldid=39147