Generalized Bent Functions and Their Gray Images

In this paper we prove that generalized bent (gbent) functions defined on \(\mathbb {F}_2^n\) with values in \(\mathbb {Z}_{2^k}\) are regular, and show connections between the (generalized) Walsh spectrum of these functions and their components. Moreover we analyze generalized bent and semibent functions with values in \(\mathbb {Z}_{16}\) in detail, extending earlier results on gbent functions with values in \(\mathbb {Z}_4\) and \(\mathbb {Z}_8\).

Work by P.S. started during a very enjoyable visit at RICAM. Both the second and third named author thank the institution for the excellent working conditions. The second author is supported by the Austrian Science Fund (FWF) Project no. M 1767-N26.

Authors and Affiliations

1. Department of Applied Mathematics, Naval Postgraduate School, Monterey, California, 93943–5216, USA

   Thor Martinsen & Pantelimon Stănică

2. Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenbergerstrasse 69, 4040, Linz, Austria

   Wilfried Meidl

Corresponding author

Correspondence to Pantelimon Stănică .

Editors and Affiliations

1. University of Rennes, Rennes, France

   Sylvain Duquesne

2. University of Leuven, Leuven, Belgium

   Svetla Petkova-Nikova

A Appendix

Proof of Theorem 4 : Let \(\mathbf{u}\in {\mathbb V}_n\). Eq. (2) for \(k=4\) implies

We denote by A, C, D, W the Walsh-Hadamard transforms \({\mathcal W}_{a_4}(\mathbf{u})\), \({\mathcal W}_{a_2\oplus a_4}(\mathbf{u})\), \({\mathcal W}_{a_3\oplus a_4}(\mathbf{u})\), \({\mathcal W}_{a_2\oplus a_3\oplus a_4}(\mathbf{u})\) (in that order). We denote by B, X, Y, Z the Walsh-Hadamard transforms \({\mathcal W}_{a_1\oplus a_4}(\mathbf{u})\), \({\mathcal W}_{a_1\oplus a_2\oplus a_4}(\mathbf{u})\), \({\mathcal W}_{a_1\oplus a_3\oplus a_4}(\mathbf{u})\), \({\mathcal W}_{a_1\oplus a_2\oplus a_3\oplus a_4}(\mathbf{u})\) (in that order). By [9, Lemma 17], we know that the generalized Walsh-Hadamard transform of any function in \(\mathcal {GB}_n^8\), say d and \(d+4a_1\) with \(d = a_2+2a_3+2^2a_4\), is of the form

where \(\alpha _0= 1+(1+\sqrt{2})i\), \(\alpha _1=1+(1-\sqrt{2})i\), \(\alpha _2=1+\sqrt{2}-i\), \(\alpha _3=1-\sqrt{2}-i\), and moreover that (see also [9, Corollary 18]),

Furthermore, with straightforward computations we get

Using (5) and (6) in Eq. (4) we obtain

If f is gbent in \(\mathcal {GB}_n^{16}\), i.e., \(|{\mathcal H}_f^{(16)}(\mathbf{u})|^2 = 2^n\), by the linear independence of \(\{1,\sqrt{2},\sqrt{2-\sqrt{2}},\sqrt{2+\sqrt{2}}\}\) (as easily shown, the set forms a basis of \({\mathbb Q}(\sqrt{2},\sqrt{2-\sqrt{2}})\)), we arrive at the following system of equations with solutions in \(\mathbb {Z}\),

Let \(2^t\) be the largest power of 2 which divides all, A, B, C, D, X, Y, Z and W, i.e., \(A=2^t A_1\), etc., with at least one of the \(A_1,B_1,\ldots \) being odd. First, if n is even and \(t>\frac{n}{2}\), then \(t=\frac{n}{2}+1\) only. Dividing by \(2^{2t}\), the first equation of (8) becomes \(A_1^2 + B_1^2 + C_1^2 + D_1^2 + W_1^2 + X_1^2 + Y_1^2 + Z_1^2=2\), which gives the solution \((\pm 1,\pm 1,0,0,0,0,0,0)\) (and permutations of these values). However, a simple computation reveals that none of these possibilities also satisfies the last three equations of (8). If n is odd and \(t>\frac{n+1}{2}\), then \(t=\frac{n+3}{2}\), but this implies that only one value out of \(A,B,\ldots \) is nonzero. Again, that is impossible to satisfy the last three equations of (8). Assume now that \(t<\frac{n}{2}\). The first equation of (8) becomes \(A_1^2 + B_1^2 + C_1^2 + D_1^2 + W_1^2 + X_1^2 + Y_1^2 + Z_1^2=2^{n+3-2t}\), which is divisible by \(2^5\) (when n is even, since \(t\le \frac{n-2}{2}\)), respectively \(2^4\) (when n is odd, since \(t\le \frac{n-1}{2}\)). If n is even, this can only happen if \(A_1,B_1,\ldots ,\) are all even, that is, \(\equiv 0,2,4,6\pmod 8\), but that contradicts our assumption that t is the largest power of 2 dividing \(A,B,\ldots \). If n is odd and \(t\le \frac{n-3}{2}\), the previous argument would work, and if \(t=\frac{n-1}{2}\), then \(A_1^2 + B_1^2 + C_1^2 + D_1^2 + W_1^2 + X_1^2 + Y_1^2 + Z_1^2=16\). By considering every residues for \(A_1,B_1,\ldots ,\) modulo 4 and imposing the condition that the 2nd, 3rd, 4th equations of our system also must be 0 modulo 16, we only get possibilities (0, 0, 2, 2, 0, 0, 2, 2), (0, 2, 0, 2, 0, 2, 0, 2), (0, 2, 2, 0, 0, 2, 2, 0), (2, 0, 0, 2, 2, 0, 0, 2), (2, 0, 2, 0, 2, 0, 2, 0), (2, 2, 0, 0, 2, 2, 0, 0) for \((A_1,B_1,\ldots )\) modulo 4, but that implies that all \(A_1,B_1,\ldots \) are even, contradicting our assumption on t. This shows that the only possibility is \(2^t = 2^{n/2}\) if n is even, and \(2^t = 2^{(n+1)/2}\) if n is odd.

Thus, one needs to find integer solutions for the equation \(A_1^2 + B_1^2 + C_1^2 + D_1^2 + {\mathcal W}_1^2 + X_1^2 + Y_1^2 + Z_1^2=8\), for n even, or \(A_1^2 + B_1^2 + C_1^2 + D_1^2 + {\mathcal W}_1^2 + X_1^2 + Y_1^2 + Z_1^2=4\) for n odd, which also satisfy the last three equations in (8). Mathematica renders the following: if n is even, then \(2^{-\frac{n}{2}}(A, C, D, W, B, X, Y, Z)\) (note the order) is one of

and, if n is odd, then \(2^{-\frac{n+1}{2}}(A, C, D, W, B, X, Y, Z)\) is one of

We see that in both cases, if f is gbent, then the conditions of the theorem are satisfied. The converse follows with straightforward calculations.    \(\Box \)

Proof of Theorem 5 : Assume that f is gsemibent in \(\mathcal {GB}_n^{16}\) when n is odd, respectively generalized 2-plateaued when n is even. Then \(|{\mathcal H}_f^{(16)}(\mathbf{u})|\in \{0,\pm 2^{(n+1)/2}\}\) for n odd, respectively, \(|{\mathcal H}_f^{(16)}(\mathbf{u})|\in \{0,\pm 2^{(n+2)/2}\}\) for n even. Using the notations of Theorem 4, from Eq. (7), we immediately get \(A=B=C=D=X=Y=W=Z=0\) if \({\mathcal H}_f^{(16)}(\mathbf{u})=0\). If \(|{\mathcal H}_f^{(16)}(\mathbf{u})|=2^{(n+1)/2}\) (for n odd), respectively, \(|{\mathcal H}_f^{(16)}(\mathbf{u})|=2^{(n+2)/2}\) (for n even), then (7) again yields the system of Eq. (8) with the one difference that in the first equation the power of 2 on the right side is \(2^{n+4}\), respectively, \(2^{n+5}\). With the same argument as in the proof of Theorem 4 we see that for such \(\mathbf{u}\), \(2^{-\frac{n+1}{2}} (A, C, D, W, B, X, Y, Z)\) (for n odd), respectively, \(2^{-\frac{n+2}{2}} (A, C, D, W, B, X, Y, Z)\) (for n even) can only take the values from Eq. (9).

Straightforwardly, one confirms that the converse is also true, and the theorem is shown.    \(\Box \)

Reprints and permissions

© 2016 Springer International Publishing AG

Policies and ethics