# Walsh spectrum of a function defined over Galois rings

Let $GR(p^2,m)$ be the Galois ring with $p^{2m}$ elements and characteristic $p^2$. Let $Z^m_{p^2}$ be the cross product of $m$ copies of $Z_{p^2}$ which is the set of integers from zero up to $p^2-1$.

Let $f:GR(p^2,m)→GR(p^2,1)=Z_{p^2}$ be a function. Consider the Walsh spectrum of $f$, namely the set $\left\{\sum_{x \in GR(p^2,m)} w^{f(x)−Tr(ax)}: a \in GR(p^2,m)\right\}$ where $w=e^{2\pi i/p^2}$ and $Tr:GR(p^2,m)\rightarrow GR(p^2,1)$ is the trace function.

As the additive group of $GR(p^2,m)$ is isomorphic to $Z^m_{p^2}$, identifying $f$ from $Z^m_{p^2}$ to $Z_{p^2}$, can we prove that the Walsh spectrum of $f$ equals to $\left\{\sum_{x \in Z^m_{p^2}} w^{f(x)−a\cdot x}: a \in Z^m_{p^2}\right\}$ where $w=e^{2\pi i/p^2}$, $a \cdot x$ is the classical dot product of $a$ and $x$?

-

This depends on certain facts about the characters of finite abelian groups and also about some properties of the trace function. The details vary a bit according to how the Galois rings were defined in your course material.

A character of a finite abelian group $A$ is simply a homomorphism $\chi$ from $A$ to $\mathbb{C}^*$ (I think of $A$ as an additive group and $\mathbb{C}^*$ as a multiplicative group). If $A$ is cyclic, say generated by an element $g$ of order $n$, then we must have $$1=\chi(0_A)=\chi(ng)=\chi(g)^n,$$ so $\chi(g)$ has to be equal to $e^{2\pi i j/n}$ for some $j=0,1,2,\ldots,n-1$. Each and every choice of $j$ works, so the cyclic group of order $n$ has exactly $n$ characters. If $A=B\oplus C$ is a direct sum of two abelian groups, we see that any character $\chi_A$ of $A$ is uniquely determined by its restrictions $\chi_B$ (resp. $\chi_C$) to the subgroups $B$ and $C$ respectively. Furthermore, any pair of characters $(\chi_B,\chi_C)$ of $B$ and $C$ gives rise to a unique character $\chi_A$ of $A$ with the property $\chi_A(b,c)=\chi_B(b)\chi_C(c)$. The stucture theory of finite abelian groups and an induction on the number of cyclic summands then shows that the group $A$ has exactly $|A|$ distinct characters.

For the purposes of this answer I construct the Galois rings as quotients of rings of integers of unramified extensions of the $p$-adic field $\mathbb{Q}_p$, because a lot more material can be found about these as opposed to, say rings of Witt vectors, so I get the needed facts about the trace map free of charge. I only use this to prove the surjectivity of the trace map $Tr:GR(p^2,m)\to GR(p^2,1)$, so if you done this in class, you can skip the following part, and continue reading about characters.

So let $p$ be a prime, $\mathbb{Z}_p$ the ring of $p$-adic integers, and let $\zeta$ a root of unity of order $p^m-1$. Then the ring $\mathbb{Z}_p[\zeta]$ is the integral closure of $\mathbb{Z}_p$ in the unramified extension $\mathbb{Q}_p[\zeta]/\mathbb{Q}_p$. The Galois group of this extension is generated by the Frobenius automorphism $F$ sending $\zeta$ to $\zeta^p$. The trace mapping is defined as follows $$Tr:\mathbb{Q}_p[\zeta]\to\mathbb{Q}_p, x\mapsto\sum_{j=0}^{m-1}F^j(x),$$ and it maps the elements of the ring $\mathbb{Z}_p[\zeta]$ to $\mathbb{Z}_p$. As the field extension was unramified, we actually have $Tr(\mathbb{Z}_p[\zeta])=\mathbb{Z}_p$.

The trace is a homomorphism of additive groups as a sum of such beasts. Therefore $Tr(p^2\mathbb{Z}_p[\zeta])\subseteq p^2\mathbb{Z}_p$ (actually there is an equality here as well), and it gives us a well defined surjective homomorphism $$Tr:\mathbb{Z}_p[\zeta]/p^2\mathbb{Z}_p[\zeta]\to\mathbb{Z}_p/p^2\mathbb{Z}_p.$$ I defined $GR(p^2,m)=\mathbb{Z}_p[\zeta]/p^2\mathbb{Z}_p[\zeta]$, so this is the trace mapping $Tr:GR(p^2,m)\to GR(p^2,1)=\mathbb{Z}/p^2\mathbb{Z}$. Furthermore, the above properties make it clear that $Tr$ also has the property that $Tr(pGR(p^2,m))=p Tr(GR(p^2,m))=p \mathbb{Z}/p^2\mathbb{Z}$, the subgroup of $\mathbb{Z}/p^2\mathbb{Z}$ generated by the coset of $p$.

Another thing we extract from the above is that as $\zeta$ is algebraic of degree $m$, then $$\mathbb{Z}_p[\zeta]=\bigoplus_{j=0}^{m-1}\mathbb{Z}_p \zeta^j$$ as an additive group. Consequently (demotimg the coset of $\zeta$ by $\zeta$ as well) $$GR(p^2,m)=\bigoplus_{j=0}^{m-1}\zeta^j(\mathbb{Z}/p^2\mathbb{Z}),\qquad(*)$$ i.e. as an additive group $GR(p^2,m)$ is a direct sum of $m$ copies of $\mathbb{Z}/p^2\mathbb{Z}$.

Skip/jump ends, continue here!

Let $a\in GR(p^2,m)$ be arbitrary. We get a homomorphism $f_a: GR(p^2,m)\to\mathbb{Z}/p^2\mathbb{Z}$ by the recipe $f_a(x)=Tr(ax)$. I claim that all this homomorphisms are distinct. Assume contrariwise that for some $a,b\in GR(p^2,m)$ we have $f_a(x)=f_b(x)$ for all $x\in GR(p^2,m)$. This means that $Tr((a-b)x)=0$ for all $x$. But this can only happen, when $a-b=0$. For if $a-b\not\equiv0 \pmod {p GR(p^2,m)}$, then $a-b$ is a unit, and the set of elements $(a-b)x$ consists of all of $GR(p^2,m)$. If $a\neq b$, but $a-b\in p GR(p^2,m)$, then the set of elements $(a-b)x$ consists of the non-trivial ideal $p GR(p^2,m)$. Earlier we saw that the trace does not vanish identically on either of these sets, so the claim follows.

Let $e:\mathbb{Z}/p^2\mathbb{Z}\to\mathbb{C}^*$ be the character $e(x)=w^x=e^{2\pi i x/p^2}$. As this is an injective mapping, the results of the previous paragraph imply that the characters $\chi_a=e\circ f_a:GR(p^2,m)\to \mathbb{C}^*$ sending $x\in GR(p^2,m)$ to $\chi_a(x)=e(f_a(x))=w^{Tr(ax)}$ are all distinct. Therefore we have found all the $p^{2m}$ characters of the additive group of $GR(p^2,m)$.

But the description $(*)$ of the additive group of $GR(p^2,m)$ as a direct sum of $m$ copies of $\mathbb{Z}/p^2\mathbb{Z}$ affors a different description of characters. Let $\vec{b}=(b_0,b_1,\ldots,b_{m-1})$ be an arbitrary element of $(\mathbb{Z}/p^2\mathbb{Z})^m$. Then the general recipe for constructing the characters of a direct sum tells us that all the characters of $GR(p^2,m)$ are given by the recipe $$\psi_{\vec{b}}: \sum_{j=0}^{m-1} x_j \zeta^j\mapsto \prod_{j=0}^{m-1}e(b_ja_j)=w^{\vec{b}\cdot\vec{x}},$$ where $\vec{x}=(x_0,x_1,\ldots,x_{m-1})$ is the coordinate vector ($\in(\mathbb{Z}/p^2\mathbb{Z})^m$).

Both these recipes describe the complete set of characters of the additive group of $GR(p^2,m)$. Therefore to each vector $\vec{b}$ there exists a unique $a\in GR(p^2,m)$ such that $\psi_{vec{b}}=\chi_a$ and vice versa. Your claim follows from this, as the Walsh transform simply computes inner products of a given function with the characters of the additive group.

-
Sorry, this is a bit long. It would probably be better to split this into many parts and refer you to textbooks for the theory of characters of abelian groups instead of giving an inadequate sketch here. – Jyrki Lahtonen Mar 30 '13 at 13:22
Thank you for the helpful, detailed answer. I have some questions actually but maybe it would be better if one can suggest me to understand the part where the surjectivity of the trace function is proved and (*). – Math_D Apr 3 '13 at 20:03
@ Jyrki Lahtonen: Actually, I have problems about p-adic integers and unramified extension. Is $\mathbb Z_p$ the ring of p-adic integers, equivalent to the set of integers from zero to $p-1$? Can you explain it more, or could you give me some references to understand the part where (*) is proven and the surjectivity of the trace function is shown? Thank you. – Math_D Apr 9 '13 at 13:49
@DilekÇelik: The $p$-adics something else. If you haven't seen them, it is probably easier to use something else. You may have instead seen the construction $GR(p^2,m)=R[x]/\langle f(x)\rangle$, where $R$ is the ring $\mathbb{Z}/p^2\mathbb{Z}$, and $f(x)$ is the Hensel lift of a primitive polynomial $\phi(x)$ of degree $m$ over $\mathbb{F}_p$. Here Hensel lift means that $f(x)\mid x^{p^m-1}-1$ in $R[x]$ and that $f(x)\equiv\phi(x)\pmod{p}$. Anyway, surjectivity of the trace follows from the surjectivity of the trace at level of finite fields. – Jyrki Lahtonen Apr 15 '13 at 5:07
Could you suggest any referances to understand (*) please? Thank you. – Math_D Apr 15 '13 at 9:07