# Walsh functions

Functions in a complete orthonormal system (cf. also Complete system) on the interval $[0,1)$. The values of the first four are: $w_0\equiv1$; $w_1\equiv1$ on $[0,1/2)$ and $w_1\equiv-1$ on $[1/2,1)$; $w_2\equiv1$ on $[0,1/4)\cup[1/2,3/4)$ and $w_2\equiv-1$ on $[1/4,1/2)\cup[3/4,1)$; $w_3\equiv1$ on $[0,1/4)\cup[3/4,1)$ and $w_3\equiv-1$ on $[1/4,3/4)$.

They were introduced by J.L. Walsh (a student of G.D. Birkhoff at Harvard University) in 1923, as linear combinations of Haar functions (cf. Haar system). R.E.A.C. Paley, who noticed that they could also be defined using products of Rademacher functions, showed that the Walsh system is the completion of the Rademacher system in 1932. (This connection has had ramifications both for the study of Walsh functions and for probability theory.) N.J. Fine (a student of A. Zygmund at Chicago University) in 1949 and N.Ya. Vilenkin in 1947 showed independently that the Walsh system is essentially the character group of the dyadic group. (This connection made the theory of Walsh functions a special case of the general study of harmonic analysis on compact groups.) For details and general references, see [a3].

The Walsh system satisfies the following properties:

1) each Walsh function $w_k$, $k>0$, has range $\{+1,-1\}$;

2) each Walsh function $w_k$ is piecewise constant on $[0,1)$;

3) if $k$ and $n$ are integers which satisfy $2^n\leq k<2^{n+1}$, then $w_k$ changes sign once on intervals of the form $I(j,n)=[j2^{-n},(j+1)2^{-n})$, for each $0\leq j<2^n$;

4) the Walsh–Dirichlet kernels of order $2^n$, $D_{2^n}(x)=\sum_{k=0}^{2^n-1}w_k(x)$, are non-negative on $[0,1)$.

These properties characterize the Walsh system: J.J. Price [a2] proved that among orthonormal systems whose functions $f_n$ alternate sign on finer and finer partitions of $[0,1)$, as $n\to\infty$, the Walsh system is the only one whose Dirichlet kernels of order $2^n$ are non-negative. S.V. Levizov [a1] proved that any orthonormal system whose functions $f_n$ have exactly $n$ sign changes on $[0,1)$, have range $\{1,-1\}$, and satisfy $f_n(0)=1$ is (a re-ordering of) the Walsh system.