Walsh spectrum of a function defined over Galois rings

229 Views Asked by At

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$?

Many thanks in advance.

1

There are 1 best solutions below

5
On BEST ANSWER

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.