Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

Many thanks in advance.

share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer
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
That is clear now. Thank you, I appreciate your quick response. – Math_D Mar 25 '13 at 18:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.