# Definition of Bent functions over Galois rings using Fourier transform (walsh transform)

First, note that the following definition is true: Definition (Carlet): Let $R=GR(p^k,m)$. A function $f$ from $R^n$ to $R$ is bent if $$|\sum_{x \in R^n} w^{Tr(f(x)-ax)}|=|R|^{n/2}$$ where $a \in R^n$, $w=e^{2\pi i/p^k}$,Tr is the trace function from $GR(p^k,m)$ to $GR(p^k,1)=Z_{p^k}$ and $ax$ is the dot product of $a$ with $x$.

According to this definition can we answer the following question: Let f be a function from $GR(p^2,m)$ to $GR(p^2,1)=Z_{p^2}$ where $p$ is an odd prime and $m>1$ be a positive integer.

For $f$ to be a bent function, what property should its walsh transform satisfy? That is, is the following true? $f$ is bent if
$$|\sum_{x \in GR(p^2,m)} w^{Tr(f(x)-ax)}|=|GR(p^2,1)|^{m/2}$$ where $w=e^{2\pi i/p^2}$, $a \in GR(p^2,m)$, Tr is the trace function from $GR(p^2,m)$ to $GR(p^2,1)$ and $ax$ is the dot product of $a$ with $x$.

-
If $f(x)-a\cdot x$ is a scalar then what need is there for a trace to be applied to it? What do $f(x)$ and $a\cdot x$ mean when $x\in{\rm GR}(p^k,m)$ and $f:R^n\to R$? (I assume $R=Z_{p^k}\ni a$.) Perhaps you want this walsh transform (which I am not familiar with) of $f$ instead of $f$ in your conjectural condition. –  anon Mar 25 '13 at 11:53
If we call $R=Z_{p^2}$, I do not know we can say $R^m=GR(p^2,m)$ as you wrote.$f$ is defined from $GR(p^2,m)$ to $GR(p^2,1)=Z_{p^2}$. Hence, $f(x) \in GR(p^2,1)=Z_{p^2}$ and $a \cdot x$ is the classical dot product of $a$ and $x$, so it is also an element of $Z_{p^2}$. So, I think you are right, we do not need to have Trace function there. If we omit the trace, will it all be true then? –  Math_D Mar 25 '13 at 12:13
You said $f:R^n\to R$ in your question (look at the $x$s being summed over in your first equation versus your second equation) (presumably $k=n$). What is the "classical dot product" of an element of ${\rm GR}(p^k,m)$ against an element of ${\rm GR}(p^k,1)$? –  anon Mar 25 '13 at 12:18
Oops, I was half-way typing up an answer, when I noticed that your function $f$ takes values in the prime ring $GR(p^2,1)=\mathbb{Z}/p^2\mathbb{Z}$. Yes, I agree with anon. There is no need to take a trace of that (and doing so would screw up everything, when $p\mid m$). Also, there is no dot product - just the usual product of elements of $GR(p^2,m)$. I would apply the trace to that instead, because this gives you all the harmonic analysis (i.e. all the characters) on the additive group of the ring $GR(p^2,m)$. –  Jyrki Lahtonen Mar 25 '13 at 12:24
And I would also talk about Walsh transform (or Walsh-Hadamard transform, when $p=2$). I don't think that using lower case is common here, as it isn't common when talking about Fourier transform either. –  Jyrki Lahtonen Mar 25 '13 at 12:27

It seems to me that in your special case we have $R=GR(p^2,m)$, so $|R|=p^{2m}$. Furthermore, it appears that $n=1$ (a single variable ranging over $R$. The Walsh transform on functions with domain $R$ seeks to express them in terms of the characters of the additive group of $R$. In this case all the characters $\psi:R\to\mathbb{C}^*$ of $R$ are of the form $$\psi_a(x)=w^{Tr(ax)},$$ where $w=e^{2\pi i/p^2}$. So if $g:R\to\mathbb{C}^*$ is any complex-valued function on $R$, the components of its Walsh transform $\hat g$ are $$\hat{g}(a)=\sum_{x\in R}g(x)\overline{\psi_a(x)}.$$ (Some authors would use a scaling factor $1/|R|$ here.)
In your case of $f:GR(p^2,m)\to GR(p^2,1)$, so we most likely want to study the Walsh transform of the `exponential' version $x\mapsto w^{f(x)}$. The bent-property in all the contexts is to require that all the components of the Walsh transform have the same magnitude (bent = as far aways from linear, i.e. a character, as possible). Here that would translate to the requirement that for all $a\in R$ the sum $$\hat{f}(a)=\sum_{x\in R}w^{f(x)-Tr(ax)}$$ should have absolute value $\sqrt{|R|}=p^m$.
This seems true, many thanks in advance. Only one thing that is not so clear in my mind. You said the additive character of GR(p^2,m), is $\psi_a(x)=w^{Tr(ax)}$. Are you sure that is true? because I think it is $\psi_a(x)=w^{ax}$. –  Math_D Mar 25 '13 at 18:39
Yes. The product $ax$ is an element of $GR(p^2,m)$, and the power $w^{ax}$ is thus not defined. OTOH $Tr(ax)$ is an element of $GR(p^2,1)=\mathbb{Z}/p^2\mathbb{Z}$, i.e. an integer modulo $p^2$, which is just what we want as an exponent of $w$. –  Jyrki Lahtonen Mar 25 '13 at 18:48