Generalized bent functions into $\mathbb {Z}_{p^{k}}$ from the partial spread and the Maiorana-McFarland class

Abstract

Functions f from ${\mathbb {F}_{p}^{n}}$, n = 2m, to $\mathbb {Z}_{{p}^{k}}$ for which the character sum $\mathcal {H}^{k}_{f}(p^{t},u)=\sum\limits _{x\in {\mathbb {F}_{p}^{n}}}\zeta _{p^{k}}^{p^{t}f(x)}\zeta _{p}^{u\cdot x}$ (where $\zeta _{q} = e^{2\pi i/q}$ is a q-th root of unity), has absolute value $p^{m}$ for all $u\in {\mathbb {F}_{p}^{n}}$ and $0\le t\le k-1$, induce relative difference sets in ${\mathbb {F}_{p}^{n}}\times \mathbb {Z}_{{p}^{k}}$ hence are called bent. Functions only necessarily satisfying $|\mathcal {H}^{k}_{f}(1,u)| = p^{m}$ are called generalized bent. We show that with spreads we not only can construct a variety of bent and generalized bent functions, but also can design functions from ${\mathbb {F}_{p}^{n}}$ to $\mathbb {Z}_{{p}^{m}}$ satisfying $|\mathcal {H}_{f}^{m}(p^{t},u)| = p^{m}$ if and only if $t\in T$ for any $T\subset \{0,1\ldots ,m-1\}$. A generalized bent function can also be seen as a Boolean (p-ary) bent function together with a partition of ${\mathbb {F}_{p}^{n}}$ with certain properties. We show that the functions from the completed Maiorana-McFarland class are bent functions, which allow the largest possible partitions.

1 Introduction

Let (A,+_A), (B,+_B) be finite abelian groups. A function f from A to B is called a bent function if

$$ |\sum\limits_{x\in A}\chi(x,f(x))| = \sqrt{|A|} $$

(1)

for every character χ of A × B which is nontrivial on B. Alternatively, f : A → B is bent if and only if for all nonzero a ∈ A the function D_af(x) = f(x +_Aa) −_Bf(x) is balanced, i.e. every value in B is taken on the same number |A|/|B| times. The graph G = {(x,f(x)) : x ∈ A} of f is then a relative difference set in A × B, see [15]. For background on relative difference sets we refer to [16].

In this article we are interested in generalized Boolean functions and in generalized p-ary functions. Let p be a prime, let $\mathbb {V}_{n}$ be an n-dimensional vector space over the finite field $\mathbb {F}_{p}$, and for an integer q, let $\mathbb {Z}_{q}$ be the ring of integers modulo q. By ‘ + ’ and ‘−’ we respectively denote addition and subtraction modulo q, whereas ‘⊕’ denotes the addition in a vector space over $\mathbb {F}_{2}$ (or $\mathbb {F}_{p}$). We call a function from $\mathbb {V}_{n}$ to $\mathbb {Z}_{p^{k}}$ a generalized p-ary function, and in the case p = 2 a generalized Boolean function in n variables. We denote the set of all generalized p-ary respectively Boolean functions by $\mathcal {G}\mathcal {B}_{n}^{p^{k}}$. For a function in $f\in \mathcal {G}\mathcal {B}_{n}^{p^{k}}$ the character sum (1) is of the form

$$ \mathcal{H}^{k}_{f}(\alpha,u)=\sum\limits_{x\in \mathbb{V}_{n}}\zeta_{p^{k}}^{\alpha f(x)}\zeta_{p}^{u\cdot x},\quad \zeta_{q} = e^{2\pi i/q}, $$

where u ⋅ x denotes a nondegenerate inner product on $\mathbb {V}_{n}$. Accordingly we call $f\in \mathcal {G}\mathcal {B}_{n}^{p^{k}}$ bent if $|\mathcal {H}^{k}_{f}(\alpha ,u)| = p^{n/2}$ for all $u\in \mathbb {V}_{n}$ and all nonzero $\alpha \in \mathbb {Z}_{p^{k}}$. For k = 1, the bent condition is then $|\mathcal {H}^{1}_{f}(\alpha ,u)| = |\mathcal {W}_{f}(-u)| = p^{n/2}$, where

$$ \mathcal{W}_{f}(u) = \sum\limits_{x\in \mathbb{V}_{n}}\zeta_{p}^{f(x)-u\cdot x} $$

is the Walsh transform of f. The function f from V_n to F_p is then a classical p-ary (Boolean) bent function. Note that when k = 1 it is sufficient to impose the condition for α = 1. Whereas many classes and constructions of Boolean and p-ary bent functions are known, when k ≥ 3 it seems not easy to find bent functions in np^k different from functions obtained via the standard construction from a spread, see Section 3.

In [18] a generalization of bent functions in $\mathcal {G}\mathcal {B}_{n}^{2^{k}}$ was defined satisfying a weaker condition. We give the definition more general for functions in $\mathcal {G}\mathcal {B}_{n}^{p^{k}}$, see [11]. A function $f\in \mathcal {G}\mathcal {B}_{n}^{p^{k}}$ is called a generalized bent function if the generalized Walsh transform

$$ \mathcal{H}^{k}_{f}(1,u)=\mathcal{H}^{k}_{f}(u)=\sum\limits_{x\in \mathbb{V}_{n}}\zeta_{p^{k}}^{f(x)}\zeta_{p}^{u\cdot x} $$

has absolute value p^n/2 for all $u\in \mathbb {V}_{n}$.

As shown in [8], a generalized bent function $f:\mathbb {V}_{n}\rightarrow \mathbb {Z}_{2^{k}}$ always satisfies $\mathcal {H}^{k}_{f}(u)=2^{n/2}\zeta _{2^{k}}^{f^{*}(u)}$ for some $f^{*}\in \mathcal {G}\mathcal {B}_{n}^{2^{k}}$, except for the case when k = 2 and n is odd. In accordance with the notation for Boolean bent functions we call f^∗ the dual of f. We remark that f^∗ is again a generalized bent function, see e.g. [9]. A similar result holds for a generalized bent function f from $\mathbb {V}_{n}$ to $\mathbb {Z}_{p^{k}}$, p odd, see [11, Lemma 3].

Similarly as for the Boolean case, bent functions from $\mathbb {V}_{n}$ to $\mathbb {Z}_{2^{k}}$ can only exist for even n. This is different for generalized bent functions, which also when p = 2 do exist for even and for odd n. In this article we will investigate two classes of generalized bent functions which are defined for even n, the partial spread class and generalized bent functions from the Maiorana-McFarland class. Hence if not stated otherwise, n = 2m will always be an even integer. Further we will mostly be interested in the case p = 2, but many results also apply for odd primes p, which then will be also included in this article.

Though generalized bent functions in general do not correspond to relative difference sets, they turned out to be very interesting functions with rich structural properties and interesting connections to Boolean respectively p-ary bent functions, see e.g. [4, 8, 11, 19]. In Section 2 we will summarize recent results on these connections. In Section 3, we study generalized bent functions obtained from spreads and Section 4 investigates generalized bent functions related to Maiorana-McFarland bent functions. As we will see both classes seem particularly interesting.

2 Preliminaries

To a function $f \in \mathcal {G}\mathcal {B}_{n}^{p^{k}}$ we can associate a unique sequence of Boolean respectively p-ary functions a_i (i = 0,1,…,k − 1) such that

$$ f(x) = a_{0}(x) + p a_{1}(x)+\cdots+p^{k-1} a_{k-1}(x), \text{ for all } x \in \mathbb{V}_{n}. $$

(2)

Further we associate to $f\in \mathcal {G}\mathcal {B}_{n}^{p^{k}}$ given as in (2) the affine space of Boolean respectively p-ary functions

$$ \mathcal{A} := a_{k-1} \oplus \langle a_{0},a_{1},\ldots,a_{k-2}\rangle. $$

(3)

Recall that “⊕” denotes the addition in the vector space over $\mathbb {F}_{p}$ of Boolean respectively p-ary functions from $\mathbb {V}_{n}$ to $\mathbb {F}_{p}$ (in contrast to the addition in $\mathbb {Z}_{p^{k}}$ in (2)). If the function $f\in \mathcal {G}\mathcal {B}_{n}^{p^{k}}$ is generalized bent, then all Boolean respectively p-ary functions in the corresponding affine space $\mathcal {A}$ are bent functions (see e.g. [4, 8, 19] for p = 2 and for the according result for odd p see [11]). For p = 2, more precisely, a function $f\in \mathcal {G}\mathcal {B}_{n}^{2^{k}}$ is generalized bent if and only if all functions in the corresponding affine space $\mathcal {A}$ are bent, such that for any $h_{0},h_{1},h_{2} \in \mathcal {A}$, $h_{3} = h_{0}\oplus h_{1}\oplus h_{2} \in \mathcal {A}$ we have $h_{3}^{*} = h_{0}^{*}\oplus h_{1}^{*}\oplus h_{2}^{*}$, where h^∗ denotes the dual of a bent function h, cf. [4]. By a secondary construction of Boolean bent functions proposed by Carlet in [2] (see also [12]), this is equivalent to the following statement: A function $f\in \mathcal {G}\mathcal {B}_{n}^{2^{k}}$ is generalized bent if and only if for any $h_{0},h_{1},h_{2} \in \mathcal {A}$ the function h₀h₁ ⊕ h₀h₂ ⊕ h₁h₂ is a bent function. Hence there is a strong relation between Carlet’s construction and generalized bent functions $f\in \mathcal {G}\mathcal {B}_{n}^{2^{k}}$. For details we refer to the treatment of octal generalized bent functions in [10] and to Corollaries 1 and 2 in [4].

The most comprehensive description of generalized bent functions which also works for functions $f\in \mathcal {G}\mathcal {B}_{n}^{p^{k}}$, p odd, has been given in [11]. There, a generalized bent function is described as

• a Boolean (p-ary) bent function a(x) from $\mathbb {V}_{n}$ to $\mathbb {F}_{2}$ ($\mathbb {F}_{p}$) with

• a partition $\mathcal {P}$ of $\mathbb {V}_{n}$

with the property that a(x) ⊕ C(x) is bent for every $C:\mathbb {V}_{n}\rightarrow \mathbb {F}_{2}$ ($C:\mathbb {V}_{n}\rightarrow \mathbb {F}_{p}$) which is constant on the elements of $\mathcal {P}$. This main result of [11] can be summarized more precisely as follows: Let $f:\mathbb {V}_{n}\rightarrow \mathbb {Z}_{p^{k}}$, n even, be given as in (2), and let $\mathcal {P}$ be the partition of $\mathbb {V}_{n}$ obtained by $\mathcal {P} = \{A(d) : 0\le d\le p^{k-1}-1\}$, where

$$ A(d) = \left\{x\in\mathbb{V}_{n} : \sum\limits_{i=0}^{k-2}a_{i}(x)p^{i} = d\right\}, $$

(4)

(some of the A(d) may be empty). Then we have the following theorem.

Theorem 1

Let$f:\mathbb {V}_{n}\rightarrow \mathbb {Z}_{p^{k}}$, n even, be given as in (2). Then f is generalized bent if and only ifa_k− 1(x) ⊕ C(x) is bent for every Boolean ( p-ary) functionC(x) which is constant on the elementsA(d) in (4) of the partition$\mathcal {P}$.

For some alternative forms of the statement of Theorem 1, we refer to [11].

Remark 1

For an octal generalized bent function $f:\mathbb {V}_{n}\rightarrow \mathbb {Z}_{8}$, the corresponding affine space $\mathcal {A}$ contains exactly four bent functions h₀,h₁,h₂ and h₃ = h₀ ⊕ h₁ ⊕ h₂ with the property that $h_{3}^{*}=h_{0}^{*}\oplus h_{1}^{*}\oplus h_{2}^{*}$. With straightforward calculations one sees that the bent functions h₀(x) ⊕ C(x) of Theorem 1 are exactly the functions {h₀,h₁,h₂,h₃,h₀h₁⊕h₀h₂⊕h₁h₂,h₀h₁⊕h₀h₃⊕h₁h₃,h₀h₂⊕h₀h₃⊕h₂h₃,h₁h₂⊕h₁h₃⊕h₂h₃}⊕{0,1}, which are all obtained from h₀,h₁,h₂,h₃ with Carlet’s secondary construction, [2].

Let $f:\mathbb {V}_{n}\rightarrow \mathbb {Z}_{p^{k}}$ be given as $f(x) = {\sum }_{i=0}^{k-1}a_{i}(x)p^{i}$ be a generalized bent function and let l ≥ k be an integer. As pointed out in [11], as an immediate consequence of Theorem 1 the function $g:\mathbb {V}_{n}\rightarrow \mathbb {Z}_{p^{l}}$

$$ \begin{array}{@{}rcl@{}} g(x) &= & c_{0}(a_{0}(x),\ldots,a_{k-2}(x)) + pc_{1}(a_{0}(x),\ldots,a_{k-2}(x)) + {\cdots} \\ & &+p^{k-2}c_{k-2}(a_{0}(x),\ldots,a_{k-2}(x)) + {\cdots} \\ & &+p^{l-2}c_{l-2}(a_{0}(x),\ldots,a_{k-2}(x)) + p^{l-1}a_{k-1}(x) \end{array} $$

(5)

is a generalized bent function for every choice of $c_{i}:\mathbb {F}_{p}^{k-1}\rightarrow \mathbb {F}_{p}$, 0 ≤ i ≤ l − 2. However this function, which formally maps into $\mathbb {Z}_{2^{l}}$, is only another instance of the same object, the bent function a_k− 1 with the partition already obtained from f above. One may say that g is obtained from f by ”lifting and playing with the partition”. In this connection it was already pointed out in [4], that only generalized bent functions given as in (2) for which a₀,…,a_k− 2 are linearly independent are relevant. Hence in [4] the dimension of a generalized bent function is defined as the dimension of the corresponding affine space (3), see [4] for the details. On the other hand, the partitions for two generalized bent functions represented by their affine spaces, $\mathcal {A}_{1} = a \oplus \langle a_{0},{\ldots } a_{r-1}\rangle$ and $\mathcal {A}_{2} = a \oplus \langle a_{0},{\ldots } a_{r-1}, a_{r}\rangle$ with a₀,…,a_r− 1,a_r linearly independent, may still be the same. Easy examples are obtained with constant a_r(x) = 1 and 1∉〈a₀,…a_r− 1〉. The condition 1∉〈a₀,…a_r− 1〉 is, for instance, satisfied for the nontrivial octal examples in Remark 1. In the light of Theorem 1 they are the same objects, hence we now modify the concept of the dimension of a generalized bent function accordingly.

Lemma 1

Let$g:\mathbb {V}_{n}\rightarrow \mathbb {Z}_{p^{l}}$,$g(x) = {\sum }_{i=0}^{l-1}b_{i}(x)p^{i}$bea generalized bent function, and suppose that the partition{A(d) : 0 ≤ d ≤ p^l− 1 − 1} of$\mathbb {V}_{n}$,defined as in (4), containsp^k− 2 < Ω ≤ p^k− 1nonempty sets. Then there exists a generalized bentfunction$f:\mathbb {V}_{n}\rightarrow \mathbb {Z}_{p^{k}}$givenas${\sum }_{i=0}^{k-2}a_{i}(x)p^{i} + p^{k-1}b_{l-1}(x)$withthe same partition {A(d) : 0 ≤ d ≤ p^k− 1 − 1} and necessarily linearly independenta₀,…,a_k− 2.

Proof

Pick Ω distinct elements δ₁,…,δ_Ω ∈{0,…,p^k− 1 − 1}, and denote the (nonempty) sets in the partition of $\mathbb {V}_{n}$ by {A(δ₁),…,A(δ_Ω)}. Then a₀(x) + pa₁(x) + ⋯ + p^k− 2a_k− 2(x) = δ_j if and only if x ∈ A(δ_j), uniquely defines the p-ary functions a_i, 0 ≤ i ≤ k − 2. Since Ω > p^k− 2, the functions a_i must be linearly independent. With Theorem 1, ${\sum }_{i=0}^{k-2}a_{i}(x)p^{i} + p^{k-1}b_{l-1}(x)$ is generalized bent. Moreover it can be transformed to g described as in (5). □

We now can modify the definition of the dimension of a generalized bent function as follows. We state three equivalent versions.

• The dimension of a generalized bent function is k − 1 if the corresponding partition $\mathcal {P}$ (defined as above) contains p^k− 2 + 1 ≤Ω≤ p^k− 1 (nonempty) sets.

• The dimension of a generalized bent function f is k − 1, if k is the smallest number for which there exists a generalized bent function $\tilde {f}(x) = {\sum }_{i=0}^{k-1}a_{i}(x)p^{i}$ from $\mathbb {V}_{n}$ to $\mathbb {Z}_{p^{k}}$, which induces the same partition of $\mathbb {V}_{n}$ as f. The coordinate functions a₀,a₁,…,a_k− 2 are then necessarily linearly independent, i.e., the affine space of bent functions a_k− 1 ⊕〈a₀,…,a_k− 2〉 has dimension k − 1.

• The dimension of a generalized bent function f is k − 1 if k is the smallest number for which there exists a generalized bent function $\tilde {f}:\mathbb {V}_{n}\rightarrow \mathbb {Z}_{p^{k}}$ from which f can be obtained by ”lifting and playing with the partition”.

3 Designing functions from the PS class

Let $\mathbb {V}_{2m}$ be a 2m-dimensional vector space over $\mathbb {F}_{p}$. As is well known, from a spread of $\mathbb {V}_{2m}$ one can construct bent functions from $\mathbb {V}_{2m}$ to $\mathbb {Z}_{p^{k}}$ respectively relative difference sets in $\mathbb {V}_{2m}\times \mathbb {Z}_{p^{k}}$ (relative to $\mathbb {Z}_{p^{k}}$). We recall the proof from which we then also will infer the conditions for obtaining generalized bent functions (which are weaker since generalized bentness is a more general concept).

Proposition 1

Let$U_{0},U_{1},\ldots ,U_{p^{m}}$be the elementsof a spread of$\mathbb {V}_{n}$,n = 2m, andk ≤ m. Define afunction$f:\mathbb {V}_{n}\rightarrow \mathbb {Z}_{2^{k}}$by

• (i) f(x) = 0 forx ∈ U₀,

• (ii) f is constant on the nonzero elements ofU_i,1 ≤ i ≤ p^m,such that for every$c\in \mathbb {Z}_{2^{k}}$thenonzero elements of exactlyp^m−kof theU_i’sare mapped to c.

Then f is a bent functionfrom$\mathbb {V}_{n}$to$\mathbb {Z}_{2^{k}}$.

Proof

Putting f(x) = c_i if $x\in U_{i}^{*}$, 1 ≤ i ≤ p^m, we have

$$ \begin{array}{@{}rcl@{}} \mathcal{H}^{k}_{f}(\alpha,u) & = & \sum\limits_{i=0}^{p^{m}}\sum\limits_{z\in U_{i}\setminus\{0\}}\epsilon_{p^{k}}^{\alpha f(z)}\epsilon_{p}^{u\cdot z} + \epsilon_{p^{k}}^{\alpha f(0)} = \sum\limits_{i=0}^{p^{m}}\sum\limits_{z\in U_{i}}\epsilon_{p^{k}}^{\alpha c_{i}}\epsilon_{p}^{u\cdot z} - \sum\limits_{i=1}^{p^{m}}\epsilon_{p^{k}}^{\alpha c_{i}} \\ & = & \sum\limits_{i=0}^{p^{m}}\epsilon_{p^{k}}^{\alpha c_{i}}\sum\limits_{z\in U_{i}}\epsilon_{p}^{u\cdot z} - \sum\limits_{i=1}^{p^{m}}\epsilon_{p^{k}}^{\alpha c_{i}}. \end{array} $$

Using that for all $u\in \mathbb {V}_{n}$, u≠ 0, the inner product u ⋅ z is trivial on exactly one spread element $U_{i_{u}}$, i.e. u ⋅ z = 0 for all $z\in U_{i_{u}}$, we obtain

$$ \begin{array}{@{}rcl@{}} \mathcal{H}^{k}_{f}(\alpha,u) & =& p^{m}\epsilon_{p^{k}}^{\alpha c_{i_{u}}} - \sum\limits_{i=1}^{p^{m}}\epsilon_{p^{k}}^{\alpha c_{i}} \quad\text{if} u\ne 0, \text{and} \\ \mathcal{H}^{k}_{f}(\alpha,0) & =& p^{m} + (p^{m}-1)\sum\limits_{i=1}^{p^{m}}\epsilon_{p^{k}}^{\alpha c_{i}}. \end{array} $$

With Condition (ii) we have ${\sum }_{i=1}^{p^{m}}\epsilon _{p^{k}}^{\alpha c_{i}} = 0$ for all nonzero $\alpha \in \mathbb {Z}_{p^{k}}$, which completes the proof. □

Remark 2

We note that Proposition 1 also holds if we replace $\mathbb {Z}_{p^{k}}$ by any abelian group of order p^k.

Generalized bent functions need to satisfy $|\mathcal {H}^{k}_{f}(\alpha ,u)| = p^{m}$ solely for α = 1, hence only the weaker condition ${\sum }_{i=1}^{p^{m}}\epsilon _{p^{k}}^{c_{i}} = 0$ has to hold. Observing that this condition is satisfied if and only if in the sum ${\sum }_{i=1}^{p^{m}}\epsilon _{p^{k}}^{c_{i}}$ for every 0 ≤ c ≤ p^k− 1 − 1 the elements $\epsilon _{p^{k}}^{c}, \epsilon _{p^{k}}^{c+p^{k-1}}, \epsilon _{p^{k}}^{c+2p^{k-1}},\ldots ,\epsilon _{p^{k}}^{c+(p-1)p^{k-1}}$ appear the same number of times, we immediately obtain

Corollary 1

Let$U_{0},U_{1},\ldots ,U_{p^{m}}$bea spread of$\mathbb {V}_{2m}$,and let$f:\mathbb {V}_{2m}\rightarrow \mathbb {Z}_{p^{k}}$bea function satisfyingf(x) = 0 forx ∈ U₀,and f is constant on the nonzero elements ofU_i,1 ≤ i ≤ p^m.Then f is generalized bent if and only if the number ofU_i,i≠ 0,mapped to an arbitrary element in {c,c + p^k− 1,c + 2p^k− 1,…,c + (p − 1)p^k− 1} is the same for every 0 ≤ c ≤ p^k− 1 − 1.

Remark 3

For the special case p = 2 the condition in Corollary 1 implies that the number of spread elements mapped to c and to c + 2^k− 1 has to be the same for every 0 ≤ c ≤ 2^k− 1 − 1. This condition can also be deduced from the description of partial spread generalized bent functions into $\mathbb {Z}_{2^{k}}$ given in [9].

The most interesting case, also giving generalized bent functions of largest dimension, is the case that k = m. We collect some obvious observations on generalized bent functions $f:\mathbb {V}_{2m}\rightarrow \mathbb {Z}_{2^{m}}$ obtained from a spread, and on their partitions $\mathcal {P}$ of $\mathbb {V}_{2m}$ defined as in (4). We restrict ourselves to p = 2, similar observations hold for arbitrary p.

• $|\mathcal {P}| \le 2^{m-1}$, (hence $\mathcal {P} = \{A(d) : 0\le d\le 2^{m-1}-1\}$), and $|\mathcal {P}| = 2^{m-1}$ if and only if $f:\mathbb {V}_{2m}\rightarrow \mathbb {Z}_{2^{m}}$ is bent.

• All A(d) but one (A(0) w.l.o.g.) contain an even number of spread elements (without $0\in \mathbb {V}_{2m}$). If f is bent, then A(d) is the union of 2 spread elements (without the 0), 1 ≤ d ≤ 2^m− 1 − 1, and A(0) (w.l.o.g) contains 3.

• All functions a_m− 1(x) ⊕ C(x) as defined in Theorem 1 are partial spread bent functions.

• Since the elements of the partition $\mathcal {P}$ of any (generalized) bent function obtained from a spread contains the (nonzero) elements of at least two spread elements, the spread is a finer partition than $\mathcal {P}$ for any (generalized) bent function obtained from a spread. From a spread one can obtain many (generalized) bent functions of (large) dimension m − 1 giving different partitions, hence are different in the light of Theorem 1.

The spread construction is thus very powerful, yielding bent functions in $\mathcal {G}\mathcal {B}_{2m}^{p^{m}}$ consequently relative difference sets in $\mathbb {V}_{2m}\times \mathbb {Z}_{p^{m}}$, and many more generalized bent functions for which the character sum $\mathcal {H}_{f}(\alpha ,u)$ must have absolute value p^m only for α = 1 (and all u). Next we investigate the question if there are functions $f\in \mathcal {G}\mathcal {B}_{2m}^{p^{m}}$ with $|\mathcal {H}_{f}(\alpha ,u)| = p^{m}$ for several α without necessarily being bent.

First observe that $|\mathcal {H}^{k}_{f}(2^{t},u)| = 2^{m}$ is equivalent to 2^tf being a generalized bent function, and $|\mathcal {H}^{k}_{f}(2^{t},u)| = 2^{m}$ implies $|\mathcal {H}^{k}_{f}(2^{t}r,u)| = 2^{m}$ for all odd r (i.e. only the order of the character matters), which is a consequence of the regularity of generalized bent functions defined as in [7] (see [8]). The according statement also holds for odd primes p (for the regularity of generalized bent functions when p is odd, we refer to [11, Lemma 3]). Accordingly, our objective is to construct functions $f\in \mathcal {G}\mathcal {B}_{2m}^{p^{m}}$ such that for a given subset T ⊂{0,1,…,m − 1} we have $|\mathcal {H}^{m}_{f}(p^{t},u)| = p^{m}$ for all $u\in \mathbb {V}_{2m}$ if and only if t ∈ T. We describe a procedure for p = 2, which can easily be adapted for any prime p.

Lemma 2

For aspread$U_{0},U_{1},\ldots ,U_{2^{m}}$of$\mathbb {V}_{2m}$,let f be a functionfrom$\mathbb {V}_{2m}$to$2^{t+1}\mathbb {Z}_{2^{m}}$withf(x) = 0 forallx ∈ U₀,and f is constant on the nonzero elements of everyU_j,1 ≤ j ≤ 2^m. Suppose thatfor every$c \in 2^{t+1}\mathbb {Z}_{2^{m}}$thenumber ofU_i,1 ≤ i ≤ 2^m,of which the (nonzero) elements are mapped to c is either zeroor$2^{l_{c}}$,l_c ≥ t + 1. Construct from f a function$g\in \mathcal {G}\mathcal {B}_{2m}^{2^{m}}$anda function$h\in \mathcal {G}\mathcal {B}_{2m}^{2^{m}}$, bothtaking values in$2^{t}\mathbb {Z}_{2^{m}}$,as follows.

• A For every$c\in 2^{t+1}\mathbb {Z}_{2^{m}}$thefunction g maps$2^{l_{c}-1}$ofthe$2^{l_{c}}$spreadelements which f maps to c to the elementc/2.The other$2^{l_{c}-1}$ofthese spread elements the function g maps toc/2 + 2^m− 1.

• B For every$c\in 2^{t+1}\mathbb {Z}_{2^{m}}$,the function h maps either

  • (i) $2^{l_{c}-1}$ofthe$2^{l_{c}}$spreadelements which f maps to c to the elementc/2,and the other$2^{l_{c}-1}$ofthese spread elements the function h maps toc/2 + 2^m− 1,or

  • (ii) all of the$2^{l_{c}}$spreadelements which f maps to c the function h maps to one ofc/2 andc/2 + 2^m− 1.

  For at least one$c\in 2^{t+1}\mathbb {Z}_{2^{m}}$thesecond situation occurs.

Then 2g = f,2h = f, thefunction g is a generalized bent function, the function h is not a generalized bentfunction.

Proof

Clearly both g and h take values in $2^{t}\mathbb {Z}_{2^{m}}$, and 2g = f, 2h = f obviously holds. The function g satisfies the conditions in Corollary 1, hence is generalized bent. Since for h, situation (ii) described in the lemma occurs at least once, h does not satisfy the conditions in Corollary 1, hence it is not generalized bent. □

Lemma 2 is the basis of the algorithm we sketch below to construct a function $f\in \mathcal {G}\mathcal {B}_{2m}^{2^{m}}$ obtained from a spread $U_{0},U_{1},\ldots ,U_{2^{m}}$ of $\mathbb {V}_{2m}$ for which $|\mathcal {H}_{f}(2^{t},u)| = 2^{m}$ if and only if t ∈ T for any prescribed subset T of {0,1,…,m − 1}.

Example

$f:\mathbb {V}_{10}\rightarrow \mathbb {Z}_{32}$, T = {0,2,4}

In this example c denotes the elements of $\mathbb {Z}_{32}$, the symbol # denotes the number of spread elements different from U₀ which are mapped by f to the element c above. W.l.o.g., U₀ is mapped to 0.

$$ \begin{array}{ccccccccccccccccccccccccccccccccc} c & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & \\ \#: & 1 & 0 & 2 & 2 & 1 & 0 & 1 & 2 & 1 & 0 & 0 & 2 & 1 & 0 & 1 & 2 \\ c: & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 \\ \#: & 1 & 0 & 2 & 2 & 1 & 0 & 1 & 2 & 1 & 0 & 0 & 2 & 1 & 0 & 1 & 2 \end{array} $$

From the distribution of the spread elements assigned to the elements of $\mathbb {Z}_{32}$, the distribution for 2f, 4f, 8f, 16f of course follows. It is given in the tables below.

$$ \begin{array}{ccccccccccccccccccccccccccccccccc} c: & 0 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 28 & 30 \\ \#: & 2 & 0 & \underline{4} & 4 & 2 & 0 & 2 & 4 &2 & 0 & \underline{0} & 4 & 2 & 0 & 2 & 4 \end{array} $$

$$ \begin{array}{ccccccccccccccccccccccccccccccccc} c: & 0 & 4 & 8 & 12 & 16 & 20 & 24 & 28 \\ \#: & 4 & 0 & 4 & 8 & 4 & 0 & 4 & 8 \end{array} $$

$$ \begin{array}{ccccccccccccccccccccccccccccccccc} c: & 0 & 8 & 16 & 24 \\ \#: & 8 & \underline{0} & 8 & \underline{16} \end{array} \quad \begin{array}{ccccccccccccccccccccccccccccccccc} c: & 0 & 16 \\ \#: & 17 & 16 \end{array}. $$

As we see, f, 4f, 16f are generalized bent, whereas 2f, 8f are not (the positions at which the condition in Corollary 1 is violated are underlined). Equivalently, $\mathcal {H}_{f}^{5}(1,u)$, $\mathcal {H}_{f}^{5}(4,u)$, $\mathcal {H}_{f}^{5}(16,u)$ have absolute value 2⁵ for all $u\in \mathbb {V}_{10}$, whereas this does not apply for $\mathcal {H}_{f}^{5}(2,u)$, $\mathcal {H}_{f}^{5}(8,u)$. For constructing the function f, one reads the tables from down to up. One first chooses 16f by assigning 17 spread elements (including U₀) to 0 and 16 spread elements to 16. As one wants 8f not to be generalized bent, for 8f all these 16 spread elements are assigned to 24 and none to 8. In the next step one can then “repair” the function and obtain the generalized bent function 4f. Observe that the value set of the function f has cardinality 22, the corresponding partition contains 11 nonempty sets. Hence the dimension of f is in fact m − 1 = 4. In this connection we remark that in the case of m − 1 ∈ T, we have two options in the first step of our algorithm. We either assign all spread elements to 0, or all but U₀ to 2^m− 1. In the fist case, the resulting function maps only into $2\mathbb {Z}_{2^{m}}\simeq \mathbb {Z}_{2^{m-1}}$, hence the second choice is to prefer.

Lemma 2 and Algorithm can easily be adapted for odd primes p. In the following ternary example, a function from $\mathbb {V}_{6}$ to $\mathbb {Z}_{27}$ is designed for which $|\mathcal {H}_{f}^{3}(3^{t},u)| = 3^{3}$ for all u, for t = 0,2 but not for t = 1.

Example

$f:\mathbb {V}_{6}\rightarrow \mathbb {Z}_{27}$

$$ \begin{array}{cccccccccccccccccccccccccc} c: & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \\ \#: & 1 & 2 & 1 & 1 & 1 & 1 & 1 & 0 & 1 \\[.5em] c: & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & \\ \#: & 1 & 2 & 1 & 1 & 1 & 1 & 1 & 0 & 1 \\[.5em] c: & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & \\ \#: & 1 & 2 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & \end{array} $$

With this choice the distribution for 3f, 9f is as follows:

$$ \begin{array}{ccccccccccc} c: & 0 & 3 & 6 & 9 & 12 & 15 & 18 & 21 & 24 \\ \#: & 3 & \underline{6} & 3 & 3 & \underline{3} & 3 & 3 & \underline{0} & 3 & \end{array} $$

$$ \begin{array}{ccccc} c: & 0 & 9 & 18 \\ \#: & 9 & 9 & 9 \end{array} $$

Summarizing, in this section we gave a constructive proof of

Theorem 2

For every integerm ≥ 2 and subset T of {0,1,…,m − 1} there exist functions from$\mathbb {V}_{2m}$to$\mathbb {Z}_{p^{m}}$suchthat$\mathcal {H}_{f}^{m}(p^{t},u)$hasabsolute valuep^mfor all$u\in \mathbb {V}_{2m}$ifand only ift ∈ T.

Remark 4

We note that it is in general difficult to find a function f if only the absolute values of the Walsh transform are known. Therefore, Theorem 2 is quite remarkable. The reason why we can construct a function given the absolute values of the Walsh transform heavily rely on the nice properties of the underlying spread.

4 The Maiorana-McFarland class and generalized bent functions of largest dimension

As seen in the previous section, from a spread of $\mathbb {V}_{2m}$ one can obtain various bent and generalized bent functions from $\mathbb {V}_{2m}$ to $\mathbb {Z}_{p^{m}}$ (with large dimension m − 1, i.e. the cardinality Ω of the corresponding partition $\mathcal {P}$ of $\mathbb {V}_{2m}$ satisfies p^m− 2 + 1 ≤Ω≤ p^m− 1). Note that when p = 2, for a bent function from $\mathbb {V}_{2m}$ to $\mathbb {Z}_{2^{k}}$, the largest value for k is m, cf. [13, 17]. In this section we will see that generalized bent functions can have an even finer partition. More precisely, we will show that there exist generalized bent functions from $\mathbb {V}_{2m}$ to $\mathbb {Z}_{p^{m+1}}$ for which the corresponding partition $\mathcal {P}$ of $\mathbb {V}_{2m}$ has cardinality larger than p^m. We show that the cardinality of the partition of a generalized bent function from $\mathbb {V}_{2m}$ into a cyclic group is upper bounded by p^m+ 1. This upper bound can be attained with functions obtained from the completed Maiorana-McFarland class.

We require some results from the literature. For a subset A of $\mathbb {V}_{n}$ we denote the indicator function of A by I(A), i.e.,

$$ I(A)(x) = \left\{\begin{array}{l@{\quad:\quad}l} 1 & x\in A, \\ 0 & \text{otherwise}. \end{array}\right. $$

In [3], Carlet presented the following secondary construction of Boolean bent functions which can easily be generalized to p-ary bent functions, see [14]:

Lemma 3

If g is a bent function from$\mathbb {V}_{n}$to$\mathbb {F}_{p}$whichis affine on ann/2-dimensionalaffine subspace A of$\mathbb {V}_{n}$,then for all$c\in \mathbb {F}_{p}$,the functiong ⊕ cI(A) is again a bent function.

In [5, 6], Kolomeec further analysed this observation and used it to investigate the graph of minimal distances of bent functions. We will use the following lemma, see [5] and Proposition 1 in [6], and for the p-ary version [14].

Lemma 4

Two bent functions from$\mathbb {V}_{n}$to$\mathbb {F}_{p}$differat least atp^n/2positions. Two bent functions with minimal distancep^n/2always differ on an affine subspace (of dimensionn/2),restricted to which they are affine functions.

With Lemma 4, we can show some properties of the partition $\mathcal {P}$ corresponding to a generalized bent function in $\mathcal {G}\mathcal {B}_{n}^{p^{k}}$.

Theorem 3

Let$f\in \mathcal {G}\mathcal {B}_{n}^{p^{k}}$,$f(x) = {\sum }_{i=0}^{k-1}a_{i}(x)p^{i}$,be a generalized bent function with thepartition$\mathcal {P} = \{A(d) : 0\le d\le p^{k-1}-1\}$of$\mathbb {V}_{n}$defined asin (4). Then

• (i) |A(d)|≥ p^n/2(orA(d) = ∅), and if |A(d)| = p^n/2,thenA(d) is an affine subspace of$\mathbb {V}_{n}$onwhicha_k− 1is affine,

• (ii) there are at mostp^n/2integers 0 ≤ d ≤ p^k− 1 − 1 such thatA(d)≠∅.

Proof

• (i) If f is generalized bent, then a_k− 1(x) ⊕ C(x) is bent for every Boolean (p-ary) function which is constant on A(d) for all 0 ≤ d ≤ p^k− 1 − 1. In particular this applies if C(x) = I(A(d)), where I(A(d)) is the indicator function of A(d) for a fixed 0 ≤ d ≤ p^k− 1 − 1. Since by Lemma 4 two bent functions differ at least at p^n/2 positions, we must have |A(d)|≥ p^n/2 for all 0 ≤ d ≤ p^k− 1 − 1 (or A(d) = ∅). Furthermore, by Lemma 4, two bent functions with minimal distance p^n/2 always differ on an affine subspace (of dimension n/2), restricted to which they are affine functions. This shows the second statement in (i).

• (ii) follows immediately from the fact that every nonempty set A(d) in the partition of $\mathbb {V}_{n}$ has cardinality at least p^n/2.

□

Bent functions in dimension n which are affine on many n/2-dimensional affine subspaces are the Maiorana-McFarland bent functions. The following characterization of the completed Maiorana-McFarland class is well known, see e.g. [6, Proposition 11]

Lemma 5

A bent function$f:\mathbb {V}_{n}\rightarrow \mathbb {F}_{p}$isin the completed Maiorana-McFarland class if and only if there exists ann/2-dimensionalaffine subspace Λ of$\mathbb {V}_{n}$suchthat f is affine on each coset of Λ.

With Lemmas 3 and 5 we obtain the following theorem.

Theorem 4

Let$f:\mathbb {V}_{2m}\rightarrow \mathbb {Z}_{p^{m+1}}$bea generalized bent function for which the correspondingpartition$\mathcal {P} = \{A(d) : 0\le d\le p^{m}-1\}$definedas in (4) attains the upper bound$|\mathcal {P}| = p^{m}$(hencefor all 0 ≤ d ≤ p^m − 1 the setA(d) is not empty and |A(d)| = p^m),and the affine subspaces in$\mathcal {P} = \{A(d) : 0\le d\le p^{m}-1\}$areparallel. Thenf(x) = a₀(x) + ⋯ + p^m− 1a_m− 1(x) + p^ma_m(x) for a bent functiona_min the completed Maiorana-McFarland class. Conversely, for every bentfunction in the completed Maiorana-McFarland class we have such an extremalgeneralized bent function.

Proof

If |A(d)| = p^m for all d, then by Theorem 3, $\mathbb {V}_{2m}$ is partitioned by $\mathcal {P} = \{A(d) : 0\le d\le p^{m}-1\}$ into affine subspaces. We assume that these are parallel. Consequently, $\mathcal {P}$ must be the set of all cosets of an n/2-dimensional subspace of $\mathbb {V}_{n}$. Again by Theorem 3, the bent function a_m(x) is then affine on all of these cosets. (Note that the dimension of f is m, and f has a representation as given in the theorem.) By Lemma 5, a_m is in the completed Maiorana-McFarland class.

Let now $a:\mathbb {V}_{2m}\rightarrow \mathbb {F}_{p}$ be in the completed Maiorana-McFarland class, i.e. a(x) is affine on the cosets of an m-dimensional linear subspace of $\mathbb {V}_{2m}$. These cosets form then a partition $\mathcal {P} = \{A(d) : 0\le d\le p^{m}-1\}$ of $\mathbb {V}_{2m}$. It remains to show that then a(x) ⊕ C(x) is bent for all $C:\mathbb {V}_{2m}\rightarrow \mathbb {F}_{p}$ which are constant on A(d) for all d. This follows by repeatedly applying Carlet’s construction of bent functions in Lemma 3 using the affine subspaces A(d). □

Remark 5

The fact that the sets in $\mathcal {P} = \{A(d) : 0\le d\le p^{m}-1\}$ are affine subspaces does not imply that they are parallel. As shown in [1], there even exist partitions of $\mathbb {V}_{n}$ into affine subspaces all of dimension r, 1 ≤ r ≤ n − 2, no two of which are parallel.

We close with a result for p = 2 which is related to vertices of maximum degree in the graph of minimal distances of bent functions, see [6]. It shows that for a Maiorana-McFarland bent function, we can have many such maximal partitions $\mathcal {P}$. Most of such partitions we have for the quadratic bent function.

Theorem 5

Let$q:\mathbb {V}_{n}\rightarrow \mathbb {F}_{2}$bea quadratic bent function. Then there are$K=(2^{1}+1)(2^{2}+1)\cdot \cdots \cdot (2^{\frac {n}{2}}+1)$distinctlinear subspaces of$\mathbb {V}_{n}$ofdimensionn/2 such that q is constant on any of the cosets. This yields K distinct partitionsof$\mathbb {V}_{n}$forgeneralized bent functions from$\mathbb {V}_{n}$to$\mathbb {Z}_{2^{n/2+1}}$,i.e. K different generalized bent functions from$\mathbb {V}_{n}$to$\mathbb {Z}_{2^{n/2+1}}$.This is the maximal number of such partitions a bent function can have.

Proof

The proof uses the following results of [6].

• (i) [6, Theorem 1]: The only bent function $f:\mathbb {V}_{n}\rightarrow \mathbb {F}_{2}$ with the properties

  • I f is affine on some n/2-dimensional affine subspace of $\mathbb {V}_{n}$,

  • II if f is affine on an n/2-dimensional affine subspace L of $\mathbb {V}_{n}$, then f is affine on every coset of L,

  is the quadratic bent function (invariant under EA-equivalence).

• (ii) The number of the m-dimensional affine subspaces, m = n/2, on which the quadratic bent function is affine is 2^m(2¹ + 1)(2² + 1) ⋅⋯ ⋅ (2^m + 1), [6, Theorem 2]. (In the language of [6] this is the maximum degree of a vertex in the graph of minimal distances of bent functions.)

• (iii) Every not quadratic bent function is affine on a smaller number of such affine subspaces, [6, Theorem 2].

By (ii) and (i) there are K distinct linear subspaces of $\mathbb {V}_{n}$ of dimension n/2 such that q is constant on any of the cosets, which by (i) yield K distinct partitions of $\mathbb {V}_{n}$ for generalized bent functions. With (iii), K is the maximal number of such partitions a bent function can have. □

5 Perspectives

A generalized bent function from $\mathbb {V}_{2m}$ to $\mathbb {Z}_{p^{k}}$ (of dimension k − 1), which satisfies $|\mathcal {H}_{f}^{k}(1,u)| = p^{m}$, can be also viewed as a bent function $a:\mathbb {V}_{2m}\rightarrow \mathbb {F}_{p}$, for which additionally there exists a partition $\mathcal {P}$ of $\mathbb {V}_{2m}$ of cardinality p^k− 2 + 1 ≤Ω≤ p^k− 1 such that a(x) ⊕ C(x) is also bent for every function C which is constant on the elements of $\mathcal {P}$. Generalized bent functions (for k ≥ 3) are harder to find than conventional bent functions since the image set is contained in a cyclic group rather than an elementary abelian group.

We first showed that with spreads we not only can construct bent functions f from $\mathbb {V}_{2m}$ to $\mathbb {Z}_{p^{m}}$ (satisfying $|\mathcal {H}_{f}^{m}(p^{t},u)| = p^{m}$ for all 0 ≤ t ≤ m − 1 (and all $u\in \mathbb {V}_{2m}$)), and a large variety of generalized bent functions, i.e. functions for which $|\mathcal {H}_{f}^{m}(1,u)| = p^{m}$, but we can also design functions $f\in \mathcal {G}\mathcal {B}_{2m}^{p^{m}}$ for which $|\mathcal {H}_{f}^{m}(p^{t},u)| = p^{m}$ if and only if t ∈ T for any subset T of {0,1,…,m − 1}.

For a bent function from $\mathbb {V}_{2m}$ to $\mathbb {Z}_{2^{k}}$, the value k = m, which is attained by spread bent functions, is maximal possible. We show that the weaker generalized bent functions can even have dimension m, i.e. there are Boolean (p-ary) bent functions which allow an even finer partition than the spread partition. Bent functions with the finest possible partition are the functions in the completed Maiorana-McFarland class. Note that by Remark 5, we cannot exclude the existence of other such bent functions.

There are many further interesting questions to investigate, some of which may be the following:

• Note that there are bent functions from $\mathbb {V}_{n}$ to $\mathbb {Z}_{2^{n/2}}$ and from $\mathbb {V}_{n}$ to $\mathbb {Z}_{p^{n/2}}$. As far as we know, the only examples of such bent functions rely on spreads in $\mathbb {V}_{n}$. Try to prove that this has to be the case, or find a counter example. Note that our Theorem 4 shows that there are other constructions in the generalized bent case.

• Find bent functions $\mathbb {V}_{n}\to \mathbb {Z}_{p^{k}}$ (p prime) which are not related to spreads. This problem is, of course, related to the problem of proving inequivalence of relative difference sets, which might be difficult. One potential example is the function in [10, Corollary 3] (based on Theorem 14 in [12]), of which one can show that it is a bent function from $\mathbb {V}_{n}$ to $\mathbb {Z}_{8}$ (obtained from Maiorana-McFarland functions), which is not obtained from a spread as described in Section 3 for some n ≥ 12. In fact, the concrete example obtained by choosing m = 6 and e = 5 in Table 1 in [12] yields a bent function in $\mathcal {G}\mathcal {B}_{12}^{8}$ for which the components have algebraic degree 3. The components of all generalized bent functions obtained from the spread construction have degree m.

• Find ”best partitions” $\mathcal {P}$ for classes of bent functions other than spread or Maiorana-McFarland bent functions. This, of course, means to construct, first, other examples of generalized bent functions.