# Walsh functions II: Walsh functions in general base and Walsh functions over groups

In a previous post we introduced Walsh functions. We showed that this set of functions is orthogonal and complete. In this post we generalize the Walsh function system such that the orthonormality and completeness of the new Walsh function system still holds. A table of contents for the posts on Walsh functions can be found here.

The definition of the Walsh functions from the previous post

$\displaystyle \mathrm{wal}_k(x)=(-1)^{\kappa_0 x_1 + \cdots + \kappa_{a-1} x_a}$

is based on the dyadic expansion of $x=x_1 2^{-1} + x_2 2^{-2} + \cdots$ and $k=\kappa_0 + \kappa_1 2 + \cdots + \kappa_{a-1} 2^{a-1}.$ Using a $b$-adic expansion for some integer $b \ge 2$ then yields generalized Walsh functions.

1. Walsh functions in base $b$

Let now $b \ge 2$ be an integer and $\omega_b=\mathrm{e}^{2\pi\mathrm{i}/b}.$ The Walsh functions in base $b$ are functions

$\displaystyle _b\mathrm{wal}_k:[0,1)\to \mathbb{T},$

where $\mathbb{T}=\{z\in \mathbb{C}: |z|=1\}.$ We define

$\displaystyle _b\mathrm{wal}_0(x)=1.$

Let the base $b$ expansion of $k \in \mathbb{N}$ be given by

$k =\kappa_0 + \kappa_1 b + \cdots + \kappa_{a-1} b^{a-1},$

where $\kappa_0,\ldots, \kappa_{a-1} \in \{0,\ldots, b-1\}.$ Further, let the base $b$ expansion of $x \in [0,1)$ be given by

$\displaystyle x=\frac{x_1}{b}+\frac{x_2}{b^2} + \cdots,$

where $x_1, x_2, \ldots \in \{0,\ldots, b-1\}.$ Then the $k$th Walsh function in base $b$ is given by

$\displaystyle _b\mathrm{wal}_k(x)= \omega_b^{\kappa_0 x_1 + \cdots + \kappa_{a-1} x_a}.$

For any given base $b \ge 2,$ it can be shown that the system

$\displaystyle _b\mathrm{wal}_0, \;_b\mathrm{wal}_1, \;_b\mathrm{wal}_2,\ldots$

is a complete orthonormal system of $L_2([0,1]).$

Further generalizations of Walsh functions in base $b$ can be obtained by considering other representations of nonnegative integers and real numbers in $[0,1).$ We do not pursue this direction here.

There is another way of generalizing Walsh functions which is based on groups. Before we introduce Walsh functions over groups we consider group characters. For our purposes it is sufficient to consider only finite abelian groups. (The material below requires some knowledge of elementary abstract algebra.)

2. Group characters

Definition (Group character)
Let $(G, \circ)$ be a finite abelian group and let $\mathbb{T}=\{z\in \mathbb{C}: |z|=1\}.$ Then a function $\chi:G\to\mathbb{T}$ is called a group character if

$\displaystyle \chi(g_1 \circ g_2) = \chi(g_1) \chi(g_2) \quad \mbox{for all } g_1,g_2 \in G.$

Let $e\in G$ be the identity element in $G,$ i.e. we have $e\circ g = g$ for all $g\in G.$ Then for any $g\in G$ we have

$\displaystyle \chi(g) = \chi(e \circ g) = \chi(e) \chi(g).$

By dividing this equation by $\chi(g) \in \mathbb{T}$ we obtain $\chi(e) = 1.$

Example
Let $b \ge 2$ be an integer and let $G=\mathbb{Z}_b=\{0,1, \ldots, b-1\}$ be the cyclic group of order $b,$ where the operation is addition modulo $b.$ (Here we identify the element $a \in \mathbb{Z}_b$ with the nonnegative integer $a.$) Let $\omega_b= \mathrm{e}^{2\pi \mathrm{i}/b}.$ Then, for each $a\in \mathbb{Z}_b$ we can define a character $\chi_a$ by

$\displaystyle \chi_a(g)= \omega_b^{a g} \quad \mbox{for all } g \in \mathbb{Z}_b.$

(Here, by $a g$ we simply mean the product of the integers ${}a$ and ${}g.)$ For $a=0$ we obtain the trivial character $\chi_0(g) = 1$ for all $g \in \mathbb{Z}_b.$

The characters of the finite cyclic group $\mathbb{Z}_b$ defined above are also all possible characters. Assume that $\chi$ is a character on $\mathbb{Z}_b.$ Then $\chi(1)= \omega_b^x$ for some $x \in [0,b).$ This defines the character completely, since

$\displaystyle \chi(a) = \chi(1+\cdots + 1) = \chi(1)\cdots \chi(1) = \omega_b^x \cdots \omega_b^x = \omega_b^{x a}.$

Since $\chi(b) = \chi(0) = 1$ it follows that

$\displaystyle \omega_b^{x b} = 1.$

Therefore $x b \equiv 0 \pmod{b}$ and hence $x \in \mathbb{Z}.$ Let $a\in \mathbb{Z}_b$ such that $a \equiv x \pmod{b},$ i.e. $0 \le a = x - k b \textless b$ for some integer ${}k.$ Then it follows that

$\displaystyle \chi(g) = \omega_b^{xg} = \omega_b^{a g - k b g} = \omega_b^{a g} (\omega_b^{b})^{-kg} = \omega_b^{ag} (1)^{-kg} = \omega_b^{ag} = \chi_a(g).$

$\Box$

The function $\chi(g)=1$ for all $g\in G$ is a character. It is called the trivial character, which we denote by $\chi_0$ in the following. Another property of characters is the following. Let ${}G$ be a finite abelian group and let $\chi$ and $\eta$ be two characters on ${}G.$ Then the function

$\displaystyle (\chi\cdot \eta)(g) := \chi(g) \eta(g) \quad \mbox{for all } g \in G$

is again a character on ${}G.$ That is, the product of two characters is again a character. (The proof is left as exercise.)

Further, if $\chi$ is a character on ${}G,$ then the complex conjugate $\overline{\chi},$ i.e. the function $\eta(g)= \overline{\chi(g)}$ for all $g \in G,$ is also a character. Notice that $\chi \cdot \overline{\chi} = \chi_0,$ the trivial character. Hence it follows that the set of all characters of a finite abelian group $G,$ which we denote by $\widehat{G},$ is again a group. The group $\widehat{G}$ is called the dual group.

Example
The dual group $\widehat{\mathbb{Z}_b}$ of the finite cyclic group $\mathbb{Z}_b$ is the set of characters

$\displaystyle \chi_0, \chi_1,\ldots, \chi_{b-1}.$

For $x,y,z \in \mathbb{Z}_b$ with $z \equiv x+y \pmod{b}$ we have

$\displaystyle \chi_x \cdot \chi_y = \chi_z.$

Hence we can define a mapping

$\displaystyle \begin{array}{rcl} \Gamma:\mathbb{Z}_b & \to & \widehat{\mathbb{Z}_b} \\ && \\ a &;; \mapsto & \chi_a. \end{array}$

This defines a group isomorphism, since $\Gamma$ is bijective and

$\displaystyle \Gamma(x + y) = \Gamma(x) \Gamma(y) \quad \mbox{for all } x, y \in \mathbb{Z}_b.$

$\Box$

Let $G$ be a finite abelian group. By the fundamental theorem of finitely generated abelian groups it follows that ${}G$ is isomorphic to

$\displaystyle \prod_{i=1}^r \mathbb{Z}_{p_i^{\alpha_i}},$

where $p_1,\ldots, p_r$ are prime numbers (not necessarily distinct) and $\alpha_1,\ldots, \alpha_r \in \mathbb{N}.$

Example
Consider $\mathbb{Z}_6.$ This is a finite abelian group which is isomorphic to $\mathbb{Z}_2 \times \mathbb{Z}_3.$ We can identify the elements by

$\displaystyle \begin{array}{rcl} 0 & \leftrightarrow & (0,0) \\ 1 & \leftrightarrow & (1,1) \\ 2 & \leftrightarrow & (0,2) \\ 3 & \leftrightarrow & (1,0) \\ 4 & \leftrightarrow & (0, 1) \\ 5 & \leftrightarrow & (1,2) \end{array}$

That is, the rule here is $a \leftrightarrow (a \pmod{2}, a\pmod{3})$ and $(u,v) + (x,y) = (u+x \pmod{2}, v+y\pmod{3}).$ For instance $5+5\equiv 4\pmod{6}$ and $(1,2)+(1,2) \equiv (2 \pmod{2},4 \pmod{3}) \equiv (0,1)$ in $\mathbb{Z}_2\times \mathbb{Z}_3.$ See also the chinese remainder theorem.
$\Box$

Remark
Notice that the group $\mathbb{Z}_{p^\alpha}$ is different from the group $\mathbb{Z}_p^\alpha$. For instance, the group $\mathbb{Z}_4 = \{0,1,2,3\}$ is cyclic, since $1+1=2, 1+1+1=3, 1+1+1+1=0.$ On the other hand, the group $\mathbb{Z}_2^2=\mathbb{Z}_2\times \mathbb{Z}_2=\{(0,0), (1,0), (0,1), (1,1)\}$ is not cyclic. We have $(1,0)+(1,0)=(0,0), (0,1)+(0,1)=(0,0), (1,1)+(1,1)=(0,0).$ Further, the additive group of a finite field $\mathbb{F}_{p^r},$ where ${}p$ is a prime and $r \in \mathbb{N},$ is isomorphic to $\mathbb{Z}_p^r.$ This is the main reason for studying Walsh functions over groups in the context of digital nets over a finite field $\mathbb{F}_{p^r}.$
$\Box$

Since we have found all characters for the finite cyclic group $\mathbb{Z}_b$ already, we can now find all the characters for arbitrary finite abelian groups ${}G.$ Let the finite abelian group ${}G$ be isomorphic to $\prod_{i=1}^r \mathbb{Z}_{p_i^{\alpha_i}}.$ Then the functions

$\displaystyle \chi_{(a_1,\ldots, a_r)}(g_1,\ldots, g_r) := \prod_{i=1}^r \chi_{a_i}(g_i)$

are characters of $\prod_{i=1}^r \mathbb{Z}_{p_i^{\alpha_i}},$ where $a_i \in \mathbb{Z}_{p_i^{\alpha_i}}.$ As for cyclic groups, it can be shown that these are all characters. Hence the dual group of $\prod_{i=1}^r \mathbb{Z}_{p_i^{\alpha_i}}$ is the set of characters

$\displaystyle \chi_{(a_1,\ldots, a_r)} : a_i \in \mathbb{Z}_{p_i^{\alpha_i}} \quad \mbox{for } 1 \le i \le r.$

(The details are left as exercise.)

Let ${}G$ be a finite abelian group. Let $a,g\in G,$ then we write the characters of ${}G$ using the notation $\chi_a(g) = \omega_b^{ag}.$

The following property of characters is important.

Lemma
Let ${}G$ be a finite abelian group and let $\widehat{G}$ be the dual group of characters. Then

$\displaystyle \begin{array}{rl} \forall \chi \in \widehat{G}\setminus \{\chi_0\}: & \sum_{g \in G} \chi(g) = 0, \\ & \\ \forall g \in G\setminus\{0\}: & \sum_{\chi \in \widehat{G}} \chi(g) = 0. \end{array}$

To prove the result for the case that ${}G$ is a cyclic group, we just note that for any integer $0 we have

$\displaystyle \sum_{g=0}^{b-1} \omega_b^{a g} = \frac{1-\omega_b^{a b}}{1-\omega_b} = 0.$

The details for arbitrary finite abelian groups are left as exercise.

We need one more extension of the ideas above. Let $(G,+)$ be a finite abelian group and consider the infinite group

$\displaystyle G^{\mathbb{N}} = \{(g_1,g_2, \ldots): g_i \in G\}.$

Here, the operation is defined component-wise, that is, for $\boldsymbol{g} = (g_1,g_2,\ldots), \boldsymbol{h}=(h_1, h_2,\ldots) \in G,$ we write $\boldsymbol{g}+\boldsymbol{h} = (g_1+h_1, g_2+h_2,\ldots) \in G^{\mathbb{N}}.$ In this case, the functions

$\displaystyle \chi_{\boldsymbol{a}}= \prod_{i=1}^\infty \chi_{a_i} \quad \mbox{where } a_i \in G \mbox{ and } a_i = 0 \mbox{ for } i \ge K \mbox{ for some } K \in \mathbb{N}, \qquad (1)$

are characters of the group $G^{\mathbb{N}}.$ Notice that for any $K \in\mathbb{N}$ the groups $G^K$ are isomorphic to a subgroup of $G^{\mathbb{N}}$ and the functions $\prod_{i=1}^K \chi_{a_i},$ where $a_i \in G,$ are the characters of $G^K.$ Hence the functions $(1)$ are characters of $G^{\mathbb{N}}$ and therefore in the set $\widehat{G^{\mathbb{N}}}.$

3. Walsh functions over finite abelian groups

We can now introduce Walsh functions over finite abelian groups.

Let

$\displaystyle x=\frac{x_1}{b}+\frac{x_2}{b^2} + \cdots \in [0,1)$

and

$\displaystyle k= \kappa_0 + \kappa_1 b + \cdots + \kappa_{a-1} b^{a-1} \in \mathbb{N}.$

Let ${}G$ be a finite abelian group with ${}b$ elements. We now map ${}x$ and ${}k$ to $G^{\mathbb{N}}$ and $\widehat{G^{\mathbb{N}}},$ respectively. To do so, let $\phi:\mathbb{Z}_b \to G$ be a bijection such that $\phi(0) = e$ (here ${}0$ is the identity element in $\mathbb{Z}_b$ and ${}e$ is the identity element in ${}G.)$ Now let

$\displaystyle \psi(x) = (\phi(x_1), \phi(x_2),\ldots) \in G^{\mathbb{N}}$

and

$\displaystyle \eta(k) = (\phi(\kappa_0), \ldots, \phi(\kappa_{a-1}), e, e, \ldots ) \in G^{\mathbb{N}}.$

Then $\psi$ maps $x\in [0,1)$ to $\psi(x) \in G^{\mathbb{N}}$ and we can use $\eta$ to map $k\in \mathbb{N}_0$ to $\chi_{\eta(k)} \in \widehat{G^{\mathbb{N}}}.$

Definition (Walsh functions over a finite abelian group)
Let ${}G$ be a finite abelian group. Then, for $k\in\mathbb{N},$ the $k$th Walsh function $\mathrm{wal}_k^G$ over the group $G$ is defined by

$\displaystyle \begin{array}{rcl} \mathrm{wal}_k^G: [0,1) & \to & \mathbb{T} \\ && \\ x & \mapsto & \chi_{\eta(k)}(\psi(x)) \end{array}$

where $\psi$ and $\eta$ are as defined above. For $k=0$ we set $\mathrm{wal}_0^G(x) = 1$ for all $x \in [0,1).$

Let $G=\mathbb{Z}_b$ and $\phi:\mathbb{Z}_b\to G$ be given by $\phi(a) = a$ for all $a \in \mathbb{Z}_b.$ Then it can be shown that $\mathrm{wal}_k^{\mathbb{Z}_b} = \,_b\mathrm{wal}_k$ for all $k\in \mathbb{N}_0$ and all $b \in \mathbb{N}$ with $b \ge 2$ (the details are left as an exercise).

4. Explicit form of Walsh functions over groups for $G=\prod_{i=1}^r \mathbb{Z}_{p_i^{\alpha_i}}$

Let now $G=\prod_{i=1}^r \mathbb{Z}_{p_i^{\alpha_i}}$ be a finite abelian group with $b$ elements, that is, $b = \prod_{i=1}^r p_i^{\alpha_i}.$ We define the function $\phi$ by its components, that is, let $\phi:\mathbb{Z}_b\to G$ be given by $\phi(a)=(\phi_1(a),\ldots, \phi_r(a)),$ where

$\displaystyle \phi_i:\mathbb{Z}_b \to \mathbb{Z}_{p_i^{\alpha_i}} \quad \mbox{for } 1 \le i \le r$

with $\phi_i(0) = 0$ for $1 \le i \le r.$ Then we have

$\displaystyle \mathrm{wal}_k^G(x) = \prod_{j=1}^a \prod_{i=1}^r \omega_{p_i^{\alpha_i}}^{\phi_i(\kappa_{j-1}) \phi_i(x_j) },$

where $k = \kappa_0 + \kappa_1 b + \cdots + \kappa_{a-1} b^{a-1} \in \mathbb{N}$ and $x=\frac{x_1}{b} + \frac{x_2}{b^2} + \cdots \in [0,1).$

Example
Let $G=\mathbb{Z}_2 \times \mathbb{Z}_2.$ Then the mapping $\phi$ is given by

$\displaystyle \begin{array}{rcl} 0 & \mapsto & (0,0) \\ && \\ 1 & \mapsto & (1,0) \\ && \\ 2 & \mapsto & (0,1) \\ && \\ 3 & \mapsto & (1,1) \end{array}$

For instance, let $k=1$ and $x = 1/2.$ Then $\eta(1) = ((1,0),(0,0), \ldots)$ and $\psi(1/2) = \psi(2/4) = ((0,1),(0,0),\ldots).$ Then

$\displaystyle \mathrm{wal}_1^{G}(1/2) = (-1)^{1 \cdot 0 + 0 \cdot 1} = 1.$

For $x=3/4$ we obtain $\psi(3/4)= ((1,1), (0,0),\ldots)$ and therefore

$\displaystyle \mathrm{wal}_1^{G}(3/4) = (-1)^{1\cdot 1 + 0 \cdot 1} = -1.$

Notice that

$\displaystyle _2\mathrm{wal}_1(1/2) = (-1)^{1 \cdot 1} = -1$

and

$\displaystyle _4\mathrm{wal}_1(3/4)= \omega_4^{1 \cdot 3} = \omega_4^{3}.$

This illustrates that $\mathrm{wal}_k^{\mathbb{Z}_2\times \mathbb{Z}_2} \neq \,_2\mathrm{wal}_k$ and $\mathrm{wal}_k^{\mathbb{Z}_2 \times \mathbb{Z}_2} \neq \,_4\mathrm{wal}_k.$ In general $\mathrm{wal}_k^G \neq \,_b\mathrm{wal}_k$ unless $G$ is isomorphic $\mathbb{Z}_b$ and $\phi$ is chosen in a particular way (the details are left as exercise).
$\Box$

The following theorem can be shown using similar arguments as for Walsh functions in base $2$ (see the previous post on Walsh functions for a proof idea).

Theorem
Let ${}G$ be a finite abelian group. Then the Walsh function system

$\displaystyle \mathrm{wal}^G_0, \mathrm{wal}^G_1, \mathrm{wal}^G_2,\ldots$

is a complete orthonormal system of $L_2([0,1]).$

The details are left as exercise.