Fourier transforms and bent functions on finite groups

Abstract

Let G be a finite nonabelian group. Bent functions on G are defined by the Fourier transforms at irreducible representations of G. We introduce a dual basis ${\widehat{G}}$, consisting of functions on G determined by its unitary irreducible representations, that will play a role similar to the dual group of a finite abelian group. Then we define the Fourier transforms as functions on ${\widehat{G}}$, and obtain characterizations of a bent function by its Fourier transforms (as functions on ${\widehat{G}}$). For a function f from G to another finite group, we define a dual function ${\widetilde{f}}$ on ${\widehat{G}}$, and characterize the nonlinearity of f by its dual function ${\widetilde{f}}$. Some known results are direct consequences. Constructions of bent functions and perfect nonlinear functions are also presented.

1 Introduction

The notion of a Boolean bent function was first introduced by Rothaus [22] in 1976. Since then Boolean bent functions have been studied in numerous papers, and various generalizations of this notion have been developed. Applications of bent functions and their generalizations can be found in information theory, cryptography, coding theory, etc. Tokareva [25] presented a systematic survey of the recent development of the research in this field. Among the generalizations of Boolean bent functions, bent functions which are defined on the direct product of a finite number of identical cyclic groups and take values in this cyclic group were introduced by Chung et al. [5] and Kumar et al. [13]. As further generalizations, Logachev et al. [15] defined bent functions on finite abelian groups, and Poinsot [18] defined bent functions on finite non-abelian groups. Carlet and Ding [4] and Pott [21] studied perfect nonlinear functions between two finite abelian groups, which can be regarded as a generalization of bent functions on finite abelian groups introduced in [15]. Later, the notion of perfect nonlinear functions between two finite abelian groups in [4, 21] is generalized to perfect nonlinear functions between two arbitrary finite groups by Poinsot [19]. More research on bent functions and perfect nonlinear functions on finite (abelian or non-abelian) groups can be found in other papers (cf. [24, 26,27,28]). Other generalizations of bent functions on finite groups are also studied; for example, see [8, 9, 20].

Perfect nonlinear functions on finite groups can be used to construct DES-like cryptosystems that are resistant to differential attacks. An example of using the classical XOR as well as the addition in a cyclic group and the multiplication in the group of units of a finite field can be found in Lai and Massey [14]. Also see [23] for more examples of S-boxes that use addition in a cyclic group. Pott [21] mentioned that “It seems that in most applications (in particular in cryptography) people use nonlinear functions on finite fields. However, there is no technical reason why you should restrict yourselves to this case”.

For arbitrary finite groups, the connections between the perfect nonlinear functions and relative difference sets are studied by Pott [21]. Let G and H be arbitrary finite groups, and $f: G \rightarrow H$ a function. Pott [21] proved that f is a perfect nonlinear function if and only if the set $R_f := \{ (s, f(s)) \, : \, s \in G \} \subset G \times H$ is a semiregular $(|G |, |H |, |G |, |G |/|H |)$ relative difference set in $G \times H$ relative to $\{1_G \} \times H$, where $1_G$ is the identity element of G. Furthermore, the notion of a $(G, H)$-related difference family is introduced in [26]. It is proved in [26, Theorem 1.3] that f is perfect nonlinear if and only if $\{S_y \, : \, y \in H \}$ is a $(G, H)$-related difference family in G, where $S_y := f^{-1}(y)$. In particuar, if f is perfect nonlinear, then by [26, Corollary 1.4], $\{S_y \, : \, y \in f(G) \}$ is also a partitioned $(|G |, K, |G |/|H |)$ difference family in G, where $K := \{ |S_y | \, : \, y \in f(G) \}$.

Let G be a finite group, and let f be a complex valued function on G. If G is abelian, then there is the dual group $\widehat{G}$ of G consisting of its (irreducible) characters. The Fourier transform $\widehat{f}$ of f is defined as a function on the dual group $\widehat{G}$, and the bentness of f is defined by its Fourier transform. That is, if the values of f on G are on the unit circle, then f is said to be a bent function if the absolute value of $\widehat{f}(\chi )$ is $\sqrt{|G |}$, for any $\chi \in \widehat{G}$. If G is nonabelian, then the Fourier transform $\widehat{f}$ of f is defined as a function on the irreducible representations of G, and the bentness of f is also defined by its Fourier transform (see Sects. 2 and 3 below for some details).

Let G be a finite nonabelian group. We introduce a dual basis of G, also denoted by $\widehat{G}$, that consists of complex valued functions on G determined by its unitary irreducible representations (see Definition 2.3 in Sect. 2). The dual basis $\widehat{G}$ will play a role similar to the dual group of a finite abelian group in our discussions. That is, for a complex valued function f on G, we will define the Fourier transform $\widehat{f}$ as a function on $\widehat{G}$ (see Definition 2.5 in Sect. 2). Although our definition of the Fourier transform (as a function on $\widehat{G}$) is equivalent to the traditional definition of the Fourier transform (as a function on the irreducible representations of G), by this new definition we are able to obtain further characterizations of bent functions on finite nonabelian groups (see Theorems 3.3 and 3.4 in Sect. 3). Furthermore, if f is a function from G to another group H, then we define a dual function $\widetilde{f}$ of f as a function from $\widehat{G}$ to the vector space with basis $\widehat{H}$. We will characterize the nonlinearity of f by its dual function $\widetilde{f}$ (see Theorems 4.2 and 4.3 in Sect. 4). The method developed in this paper also provides conceptual proofs of some known results (see Corollaries 3.9 and 4.8).

The rest of the paper is organized as follows. In Sect. 2 we discuss properties of the Fourier transform as a function on the dual basis $\widehat{G}$. Then in Sect. 3, we study characterizations of bent functions. Characterizations of perfect nonlinear functions between two arbitrary finite groups are discussed in Sect. 4, and constructions of bent functions and perfect nonlinear functions are presented in Sect. 5.

2 Fourier transforms on finite groups

Let G be a finite group. The identity element of G is denoted by $1_G$, or simply by 1 when no ambiguity can occur. Let $GL(m, \mathbb C)$ be the group of all invertible $m \times m$ matrices over the complex numbers $\mathbb C$. Then a homomorphism $\Phi : G \rightarrow GL(m, \mathbb C)$ is called a (matrix) representation of G, and m is called the degree of $\Phi$. We say that a representation $\Phi : G \rightarrow GL(m, \mathbb C)$ is reducible if there is $P \in GL(m, \mathbb C)$ such that

$$\begin{aligned} P^{-1} \Phi (x) P = \begin{pmatrix} A(x) &{} O \\ O &{} C(x) \end{pmatrix}, \quad \hbox {for all } x \in G, \end{aligned}$$

where A(x) and C(x) are square matrices, and O are zero matrices. If a representation $\Phi$ is not reducible, then we say that $\Phi$ is irreducible. Two representations $\Phi$ and $\Psi$ of G are said to be equivalent if there is an invertible matrix P such that $\Psi (x) = P^{-1} \Phi (x) P$, for all $x \in G$. Let ${{\mathrm{Tr}}}(M)$ denote the trace of a square matrix M. Then the character $\varphi$ of G afforded by a representation $\Phi$ is the function $\varphi : G \rightarrow \mathbb C$ defined by $\varphi (x) = {{\mathrm{Tr}}}(\Phi (x))$, for all $x \in G$, and $\varphi$ is called an irreducible character if $\Phi$ is irreducible. The degree of $\Phi$ is also called the degree of $\varphi$, and denoted by $n_\varphi$. Two irreducible representations are equivalent if and only if they afford the same character. A representation $\Phi$ is called a unitary representation if $\Phi (x)$ is a unitary matrix, for any $x \in G$. Note that any irreducible representation of G is equivalent to a unitary irreducible representation (see [12, Theorem 4.17]).

The principal irreducible representation of G is $\Phi _1: G \rightarrow GL(1, \mathbb C)$, $x \mapsto 1$, and the principal irreducible character is $\varphi _1$ afforded by $\Phi _1$. Any other irreducible representation (character) is called a non-principal irreducible representation (character). Throughout the paper, let ${{\mathrm{Irr}}}(G)$ denote the set of irreducible characters of G. For the references of the representation and character theory of finite groups, the reader is referred to [1, 11, 12, 16].

Let $f: G \rightarrow \mathbb C$ be a function. Then for an irreducible representation $\Phi : G \rightarrow GL(m, \mathbb C)$, the Fourier transform of f at $\Phi$ is defined as

$$\begin{aligned} \widehat{f}(\Phi ) := \sum _{x \in G} f(x) \Phi (x) \in {{\mathrm{Mat}}}_m(\mathbb C), \end{aligned}$$

(2.1)

where ${{\mathrm{Mat}}}_m(\mathbb C)$ is the algebra of all $m \times m$ matrices over $\mathbb C$. The order of G is denoted by $|G |$. Let $\{ \Phi _1, \Phi _2, \cdots , \Phi _k \}$ be a complete set of representatives of inequivalent irreducible representations of G, where k is the number of conjugacy classes of G. It is known that the Fourier transforms of f at $\Phi _1, \Phi _2, \cdots , \Phi _k$ determine f through the inversion formula

$$\begin{aligned} f(x) = \frac{1}{|G |} \sum _{i=1}^k n_i {{\mathrm{Tr}}}\big ( \Phi _i(x^{-1}) \widehat{f}(\Phi _i) \big ), \quad \hbox {where}~n_i~\hbox {is the degree of } \Phi _i. \end{aligned}$$

(2.2)

For each $\psi \in {{\mathrm{Irr}}}(G)$, we fix a unitary irreducible representation $\Phi _\psi$ that affords $\psi$. Then for any $s \in G$, $\Phi _\psi (s)$ is an $n_\psi \times n_\psi$ unitary matrix, denoted by $\big ( \phi _{ij}^\psi (s) \big )_{i, j}$. Thus, for any $\psi \in {{\mathrm{Irr}}}(G)$, we have $n_\psi ^2$ functions on G defined by $\Phi _\psi$:

$$\begin{aligned} \phi _{ij}^\psi : \ G \rightarrow \mathbb C, \quad s \mapsto \phi _{ij}^\psi (s), \quad 1 \le i, j \le n_\psi . \end{aligned}$$

Throughout the paper, the following notation will be used.

Notation 2.1

For each $\psi \in {{\mathrm{Irr}}}(G)$, let $\Phi _\psi$ be a (fixed) unitary irreducible representation that affords $\psi$, and we also write

$$\begin{aligned} \Phi _\psi := \big ( \phi _{ij}^\psi \big )_{i, j}. \end{aligned}$$

Furthermore, let

$$\begin{aligned} \widehat{G} := \{ \phi _{ij}^\psi \, : \, \psi \in {{\mathrm{Irr}}}(G), 1 \le i, j \le n_\psi \}. \end{aligned}$$

The set $\mathbb C^G$ of complex functions on G is an $|G |$-dimensional complex space. It is also a G-module (or G-space) with the G-action defined by

$$\begin{aligned} sf: \ G \rightarrow \mathbb C, \quad t \mapsto f(s^{-1}t), \quad \hbox {for any } s \in G, f \in \mathbb C^G. \end{aligned}$$

(2.3)

The complex conjugate of any $z \in \mathbb C$ is denoted by $\overline{z}$. For any $f \in \mathbb C^G$, let $\overline{f}$ be the complex conjugate of f defined by $\overline{f}: G \rightarrow \mathbb C, s \mapsto \overline{f(s)}$. The next lemma collects some basic facts about $\widehat{G}$. These results are known and can be found in the references mentioned above.

Lemma 2.2

With Notation 2.1, the following hold.

(i):

$|\widehat{G}|=|G|$.

(ii):

$\psi =\sum \limits _{i=1}^{n_\psi }\phi ^\psi _{ii}$,  for all $\psi \in \mathrm{Irr}(G)$.

(iii):

$\overline{\phi ^\psi _{ij}}(s)=\phi ^\psi _{ji}(s^{-1})$,  for all $\phi ^\psi _{ij}\in \widehat{G}$ and $s\in G$.

(iv) :

$\phi ^\psi _{ij}(st) =\sum \limits _{k=1}^{n_\psi }\phi ^\psi _{ik}(s)\phi ^\psi _{kj}(t)$, for all $\phi ^\psi _{ij} \in \widehat{G}$ and $s,t\in G$. In particular,

$$\begin{aligned} s\phi ^\psi _{ij}=\sum _{k=1}^{n_\psi }\phi ^\psi _{ik} (s^{-1})\phi ^\psi _{kj}, \quad \hbox {for any } s \in G. \end{aligned}$$

(2.4)

From (2.2) and Lemma 2.2, $\widehat{G}$ is a basis of $\mathbb C^G$.

Definition 2.3

With Notation 2.1, we call $\widehat{G}$ a dual basis of G.

The dual basis $\widehat{G}$ will play a role similar to the dual group of a finite abelian group in our treatment of Fourier transforms on finite nonabelian groups.

Note that $\mathbb C^G$ is a unitary space with the inner product

$$\begin{aligned} \langle f, g \rangle _G= \sum _{ s \in G } f(s) \overline{g(s)},\qquad \hbox {for any } f, g \in \mathbb C^G. \end{aligned}$$

(2.5)

The next lemma is well known (cf. [16, p. 187, Theorem 2.2]). It says that $\widehat{G}$ is an orthogonal basis of $\mathbb C^G$.

Lemma 2.4

(Orthogonality Relations) For any $\phi ^\psi _{ij}, \phi ^\chi _{kl} \in \widehat{G}$,

$$\begin{aligned} \left\langle \phi ^\psi _{ij},\phi ^\chi _{kl}\right\rangle _G = {\left\{ \begin{array}{ll} \frac{\,|G |\,}{n_\psi }, &{} \hbox {if } \phi ^\psi _{ij} =\phi ^\chi _{kl};\\ 0, &{} \hbox {if } \phi ^\psi _{ij}\ne \phi ^\chi _{kl}. \end{array}\right. } \end{aligned}$$

(2.6)

For any $f \in \mathbb C^G$, in the next definition we define its Fourier transform $\widehat{f}$ as a function on $\widehat{G}$. Note that this definition is equivalent to the original definition of $\widehat{f}$ in (2.1) and the inversion formula (2.2). In this paper we will regard $\widehat{f}$ as a function on irreducible representations and also on $\widehat{G}$ as well. To simplify the notation, the summation over all $\phi _{ij}^\psi \in \widehat{G}$ is denoted by $\sum \limits _{(\psi , i, j)}$.

Definition 2.5

For any $f \in \mathbb C^G$, the Fourier transform $\widehat{f}$ of f on $\widehat{G}$ is defined by

$$\begin{aligned} \widehat{f}(\phi ^\psi _{ij})= \sum _{s\in G} f(s) \phi ^\psi _{ij}(s),\qquad \hbox {for any } \phi ^\psi _{ij} \in \widehat{G}. \end{aligned}$$

On the other hand, for any function $\tau : \widehat{G} \rightarrow \mathbb C$, we define the Fourier inversion $\widehat{\tau }\in \mathbb C^{G}$ as follows:

$$\begin{aligned} \widehat{\tau }(s)=\frac{1}{|G |}\sum _{ (\psi , i, j) } n_\psi \overline{\phi ^\psi _{ij}}(s)\tau (\phi ^\psi _{ij}), \qquad \hbox {for all } s \in G. \end{aligned}$$

Thus, from Definition 2.5 and (2.1), we have

$$\begin{aligned} \widehat{f}(\Phi _\psi ) = \left( \widehat{f} (\phi _{ij}^\psi ) \right) _{i, j}, \quad \hbox {for any } \psi \in {{\mathrm{Irr}}}(G). \end{aligned}$$

(2.7)

Remark 2.6

Since $\widehat{G}$ is a basis of $\mathbb C^G$, we have $\mathbb C^G = \mathbb C\widehat{G}$. Let $\sigma : \widehat{G} \rightarrow \mathbb C$ be a function. Then $\sigma$ can be linearly extended to a function (still denoted by $\sigma$) on $\mathbb C\widehat{G}$ as follows:

$$\begin{aligned} \sigma : \ \mathbb C\widehat{G} \rightarrow \mathbb C, \quad \sum _{(\psi , i, j)} \alpha _{ij}^\psi \phi _{ij}^\psi \mapsto \sum _{(\psi , i, j)} \alpha _{ij}^\psi \sigma \big ( \phi _{ij}^\psi \big ). \end{aligned}$$

In particular, for any function $f: G \rightarrow \mathbb C$, its Fourier transform $\widehat{f}$, a function on $\widehat{G}$, is also a function on $\mathbb C\widehat{G}$ by linear extension.

The next lemma is straightforward.

Lemma 2.7

$\widehat{\widehat{f}} = f$ for any $f \in \mathbb C^G$, and $\widehat{\widehat{\tau }} = \tau$ for any $\tau \in \mathbb C^{\widehat{G}}.$

The next lemma discusses the relation between a function and its Fourier transform on $\widehat{G}$. It can be regarded as a reformulation of the inversion formula (2.2).

Lemma 2.8

Let $f \in \mathbb C^G$, and $\overline{f}$ the complex conjugate of f. Then

$$\begin{aligned} \overline{f} = \frac{1}{|G |} \sum _{(\psi , i, j)} n_\psi \overline{\widehat{f}(\phi _{ij}^\psi )} \phi _{ij}^\psi . \end{aligned}$$

Proof

Since $\widehat{G}$ is a basis of $\mathbb C^G$, we may assume that $\overline{f} = \sum _{(\psi , i, j)} \alpha _{ij}^\psi \phi _{ij}^\psi$, where $\alpha _{ij}^\psi \in \mathbb C$. Therefore, $f = \sum _{(\psi , i, j)} \overline{\alpha _{ij}^\psi } \, \overline{\phi _{ij}^\psi }$, and hence $\widehat{f} = \sum _{(\psi , i, j)} \overline{\alpha _{ij}^\psi } \, \widehat{\overline{\phi _{ij}^\psi }}$. So by Lemma 2.4,

$$\begin{aligned} \widehat{f}(\phi _{kl}^\chi ) = \sum _{(\psi , i, j)} \overline{\alpha _{ij}^\psi } \, \widehat{\overline{\phi _{ij}^\psi }}(\phi _{kl}^\chi ) = \sum _{(\psi , i, j)} \overline{\alpha _{ij}^\psi } \, \left\langle \phi ^\chi _{kl}, \phi ^\psi _{ij} \right\rangle _G = \frac{|G |}{n_\chi }\, \overline{\alpha _{kl}^\chi }, \quad \hbox {for any } \phi _{kl}^\chi \in \widehat{G}. \end{aligned}$$

Hence, the lemma holds. $\square$

Remark 2.9

For any $s \in G$, we have the characteristic function ${{\mathbf {1}}}_s \in \mathbb C^G$ (i.e. ${{\mathbf {1}}}_s(t) = 0$ if $t \ne s$ and ${{\mathbf {1}}}_s(s) = 1$), whose Fourier transform is $\widehat{{\mathbf {1}}}_s(\phi _{ij}^\psi ) = \phi _{ij}^\psi (s)$, for any $\phi _{ij}^\psi \in \widehat{G}$. For any function $\sigma : \widehat{G} \rightarrow \mathbb C$, it is straightforward to check that $\sigma = \sum _{s \in G} \widehat{\sigma }(s) \widehat{{\mathbf {1}}}_s.$ So the Fourier transform and the Fourier inversion can be regarded as transformations between $\widehat{G}$ and $\{ \widehat{{\mathbf {1}}}_s \, : \, s \in G \}$.

Let V be a vector space of dimension $|G |$ with a basis $B := \{e_t \}_{t \in G}$ indexed by the elements of G. Then any $s \in G$ induces a linear transformation (an isomorphism) $\Omega _s : V \rightarrow V, e_t \mapsto e_{st}$, for any $t \in G$.

Definition 2.10

With the notation in the above paragraph, the (left) regular representation of G is

$$\begin{aligned} \Omega : \ G \rightarrow GL(|G |, \mathbb C), \quad s \mapsto {{\mathrm{Mat}}}_B(\Omega _s), \end{aligned}$$

where ${{\mathrm{Mat}}}_B(\Omega _s)$ is the matrix of $\Omega _s$ with respect to the basis B.

The regular character $\rho$ of G is the character afforded by the (left) regular representation of G. It is known that $\rho = \sum \nolimits _{\psi \in {{\mathrm{Irr}}}(G)} n_\psi \psi$ (see [12, Lemma 2.11]), $\rho (1_G) = |G |$, and $\rho (s) = 0$ for any $s \in G {\setminus } \{ 1_G \}$ (see [12, Lemma 2.10]). Let $I_n$ be the $n \times n$ identity matrix for any positive integer n. For any $g \in \mathbb C^G$, since $\widehat{G}$ is a basis of $\mathbb C^G$, and $\rho = \sum _{(\psi , i)} n_\psi \phi _{ii}^\psi$, the following are equivalent by Lemma 2.8 and (2.7):

(i):

$g(s) = 0$ for any $s \in G {\setminus } \{ 1_G \}$;

(ii):

$g = \frac{g(1)}{|G |} \rho$ (or $\overline{g} = \frac{\overline{g}(1)}{|G |} \rho$);

(iii):

$\widehat{g}(\Phi _\psi ) = g(1) I_{n_\psi }$, for any $\psi \in {{\mathrm{Irr}}}(G)$.

More generally, we have the next result.

Lemma 2.11

(Cf. [27, Lemma 2.1]) Let $f \in \mathbb C^G$ and $\lambda \in \mathbb C$. Then the following are equivalent.

(i):

For any $s \in G {\setminus } \{ 1_G \}$, $f(s) = \lambda$.

(ii):

For any non-principal irreducible character $\psi$ of G, $\widehat{f}(\Phi _\psi ) = (f(1) - \lambda ) I_{n_\psi }$.

Proof

Let $g = f - \lambda \psi _1$, where $\psi _1$ is the principal irreducible character of G. Note that for any non-principal irreducible character $\psi$ of G, $\sum _{x \in G} \Phi _\psi (x) = O$ (the zero matrix, cf. [12, Problem 2.1]). Hence,

$$\begin{aligned} \widehat{g}(\Phi _\psi ) = \widehat{f}(\Phi _\psi ), \quad \hbox {for any non-principal irreducible character} \ \ \psi \ \ \hbox {of}\ \ G. \end{aligned}$$

(2.8)

Assume (i). Then $g = \frac{g(1)}{|G |} \rho$, and hence for any $\psi \in {{\mathrm{Irr}}}(G)$, $\widehat{g}(\Phi _\psi ) = g(1) I_{n_\psi }$ by the remark before the lemma. So (ii) holds by (2.8).

Assume (ii). Then by Lemma 2.8 and (2.8),

$$\begin{aligned} \overline{g}= & {} \frac{1}{|G |} \sum _{(\psi , i, j)} n_\psi \overline{\widehat{g}(\phi _{ij}^\psi )} \phi _{ij}^\psi \ = \ \frac{1}{|G |}\overline{\widehat{g}(\psi _1)} \psi _1 + \frac{1}{|G |} \sum _{(\psi , i), \psi \ne \psi _1} n_\psi \left( \overline{f(1)} - \overline{\lambda } \right) \phi _{ii}^\psi \\= & {} \frac{\overline{g}(1)}{|G |} \rho + \frac{1}{|G |} \left( \overline{\widehat{g}(\psi _1)} - \overline{g}(1) \right) \psi _1. \end{aligned}$$

Thus, $\overline{g} (1) = \frac{\overline{g}(1)}{|G |} \rho (1) + \frac{1}{|G |} \left( \overline{\widehat{g}(\psi _1)} - \overline{g}(1) \right) \psi _1 (1)$, and hence $\overline{\widehat{g}(\psi _1))} - \overline{g}(1) = 0$. So $\overline{g} = \frac{\overline{g}(1)}{|G |} \rho$, and (i) holds. $\square$

The next corollary will be needed later.

Corollary 2.12

The following hold:

(i):

A function $f \in \mathbb C^G$ is constant on G if and only if for any non-principal irreducible character $\psi$ of G, $\widehat{f}(\Phi _\psi ) = O$, the zero matrix.

(ii):

For any $\sum _{s \in G} \alpha _s s \in \mathbb CG$, $\alpha _s$ are equal for all $s \in G$ if and only if for any non-principal irreducible character $\psi$ of G, $\Phi _\psi \left( \sum _{s \in G}\alpha _s s \right) = O$, the zero matrix.

Proof

• (i) follows directly from Lemma 2.11, with $f(1) = \lambda$.

• (ii) Let $f: G \rightarrow \mathbb C, s \mapsto \alpha _s$. Then $\widehat{f}(\Phi _\psi ) = \Phi _\psi \left( \sum _{s \in G}\alpha _s s \right)$. So (ii) follows from (i). $\square$

The set $\mathbb C^{\widehat{G}}$ of complex functions on $\widehat{G}$ is also a unitary complex space with the inner product:

$$\begin{aligned} \langle \xi ,\eta \rangle _{\widehat{G}} = \sum _{(\psi , i, j)} n_\psi \xi (\phi ^\psi _{ij}) \overline{\eta }(\phi ^\psi _{ij}),\qquad \hbox {for any } \xi ,\eta \in \mathbb C^{\widehat{G}}, \end{aligned}$$

(2.9)

where $\overline{\eta }: \widehat{G} \rightarrow \mathbb C$ is the complex conjugate of $\eta$ defined by $\overline{\eta }(\phi _{ij}^\psi ) = \overline{\eta (\phi _{ij}^\psi )}$, for any $\phi _{ij}^\psi \in \widehat{G}$.

Lemma 2.13

For any $f, g \in \mathbb C^G$,

$$\begin{aligned} \big \langle \widehat{f}, \widehat{g} \big \rangle _{\widehat{G}} = |G | \langle f, g \rangle _G. \end{aligned}$$

Proof

It follows from (2.9), (2.5), Definition 2.5, and Lemma 2.2(iii, iv) that

$$\begin{aligned} \big \langle \widehat{f}, \widehat{g} \big \rangle _{\widehat{G}}= & {} \sum _{(\psi , i, j)} n_\psi \widehat{f}(\phi _{ij}^\psi ) \overline{\widehat{g}(\phi _{ij}^\psi )} \ = \ \sum _{(\psi , i, j)} \sum _{s, t \in G} n_\psi f(s) \phi _{ij}^\psi (s) \overline{g(t)}\, \overline{\phi _{ij}^\psi (t)} \\= & {} \sum _{s, t \in G} f(s) \overline{g(t)} \sum _{(\psi , i, j)} n_\psi \phi _{ij}^\psi (s) \phi _{ji}^\psi (t^{-1}) \\= & {} \sum _{s, t \in G} f(s) \overline{g(t)} \rho (st^{-1}), \quad \hbox {where}~\rho ~\hbox {is the regular character of } G, \\= & {} |G | \langle f, g \rangle _G. \end{aligned}$$

So the lemma holds. $\square$

3 Bent functions

In this section we study characterizations of bent functions by their Fourier transforms on the dual basis $\widehat{G}$. The main results are Theorems 3.3 and 3.4 below.

In the following we always assume that G is an arbitrary finite group, $\Phi _\psi = \big ( \phi _{ij}^\psi \big )_{i, j}$ is a unitary irreducible representation of G that affords $\psi$, for any $\psi \in {{\mathrm{Irr}}}(G)$, and $\widehat{G} := \{ \phi _{ij}^\psi \, : \, \psi \in {{\mathrm{Irr}}}(G), 1 \le i, j \le n_\psi \}$ is a dual basis of G. For any matrix M, let $M^*$ denote the conjugate transpose of M. Let $T := \{ z \in \mathbb C\, : \, |z | = 1 \}$ be the unit circle in $\mathbb C$.

Definition 3.1

(Cf. [18, Definition 9]) A function $f: G \rightarrow T$ is called a bent function if

$$\begin{aligned} \widehat{f}(\Phi _\psi ) \big [\widehat{f}(\Phi _\psi )]^* = |G | I_{n_\psi }, \quad \hbox {for any } \psi \in {{\mathrm{Irr}}}(G). \end{aligned}$$

A function $g \in \mathbb C^G$ is said to be balanced on G if $\sum _{x \in G} g(x) = 0$.

Let $f: G \rightarrow \mathbb C$ be a function, and $a \in G$. Then the derivative of f in the direction a, $d_a f$, is defined by

$$\begin{aligned} d_a f: \ G \rightarrow \mathbb C, \quad x \mapsto f(ax) \overline{f(x)}. \end{aligned}$$

Poinsot [18, Theorem 3] characterizes a bent function by its derivatives (see Corollary 3.9 below).

Let $\sigma : \widehat{G} \rightarrow \mathbb C$ be a function. Then $\sigma$ is also a function on $\mathbb C\widehat{G}$ by linear extension. We can define the derivative of $\sigma$ in a similar way. That is, for any $a \in G$, the derivative of $\sigma$ in the direction a, $d_a \sigma$, is defined by

$$\begin{aligned} d_a \sigma : \ \widehat{G} \rightarrow \mathbb C, \quad \phi _{ij}^\psi \mapsto \sigma (a \phi _{ij}^\psi ) \overline{\sigma (\phi _{ij}^\psi )}. \end{aligned}$$

Recall that the G-action on $\widehat{G}$ is given by (2.4); i.e. $a\phi ^\psi _{ij}=\sum _{k=1}^{n_\psi }\phi ^\psi _{ik}(a^{-1})\phi ^\psi _{kj}$, for any $a \in G$ and $\phi _{ij}^\psi \in \widehat{G}.$

Definition 3.2

A function $\sigma : \widehat{G} \rightarrow \mathbb C$ is said to be balanced on $\widehat{G}$ if

$$\begin{aligned} \sum _{(\psi , i, j)} n_\psi \sigma (\phi _{ij}^\psi ) = 0. \end{aligned}$$

The next theorem is our first main result of this section. It characterizes a bent function f by the derivatives of its Fourier transform $\widehat{f}$.

Theorem 3.3

Let $f: G \rightarrow T$ be a function. Then the following are equivalent.

(i):

f is a bent function.

(ii):

For any $a \in G {\setminus } \{ 1_G \}$, $d_a \widehat{f}$ is balanced on $\widehat{G}$. That is,

$$\begin{aligned} \sum _{(\psi , i, j)} n_\psi \widehat{f}(a \phi _{ij}^\psi )\, \overline{\widehat{f}(\phi _{ij}^\psi )} = 0, \quad \hbox {for any } a \in G {\setminus } \{ 1_G \}. \end{aligned}$$

The kernel of $\psi \in {{\mathrm{Irr}}}(G)$ is $\ker \psi := \{ s \in G \, : \, \psi (s) = n_\psi \}$. It is well known that $\ker \psi$ is a normal subgroup of G. To simply the notation, for a normal subgroup N of G, let

$$\begin{aligned} N^\perp := \{ \psi \, : \, \psi \in {{\mathrm{Irr}}}(G) \hbox { and } \ker \psi \supseteq N \}. \end{aligned}$$

(3.1)

Such a notation is used for subgroups of an abelian group in the literature (cf. [15], etc.), with slightly different definitions.

In the case that $f \in \mathbb C^G$ is not bent, the conditions under which the set $\{ a \in G \, : \, d_a f$ is balanced on $G \}$ contains $Q {\setminus } \{ 1_G \}$ for some subgroup Q of G (when G is abelian) have been studied in the literature (cf. [15], etc.). Our second main result of this section characterizes functions f that have balanced derivatives $d_a f$ for $a \ (\ne 1_G)$ in a normal subgroup. Note that Theorem 3.4 below is not a generalization of the results of Logachev et al. (cf. [15, Theorems 4 and 5]).

Theorem 3.4

Let $f: G \rightarrow T$ be a function, and $N \ (\ne \{ 1_G \})$ a normal subgroup of G. Then the following are equivalent.

(i):

For any $a \in N {\setminus } \{ 1_G \}$, $d_a f$ is balanced on G, i.e. $\sum _{s \in G} \big ( d_a f \big ) (s) = 0.$

(ii):

For any $a \in N {\setminus } \{ 1_G \}$, $d_a \widehat{f}$ is balanced on $\widehat{G}$, i.e. $\sum _{(\psi , i, j)} n_\psi \big ( d_a \widehat{f}\, \big ) (\phi _{ij}^\psi ) = 0.$

(iii):

For any $a \in N {\setminus } \{ 1_G \}$,

$$\begin{aligned} \sum _{(\psi , i, j), \psi \notin N^\perp } n_\psi \big ( d_a \widehat{f}\, \big ) (\phi _{ij}^\psi ) = - \frac{|G |^2}{|N |}. \end{aligned}$$

The rest of this section is devoted to the proofs of Theorems 3.3 and 3.4. Let us start with the following definition.

Definition 3.5

Let $f \in \mathbb C^G$. If $f = \sum \limits _{(\psi , i, j)} \alpha _{ij}^\psi \phi _{ij}^\psi$, where $\alpha _{ij}^\psi \in \mathbb C$, then for any $\psi \in {{\mathrm{Irr}}}(G)$, $f_\psi := \sum \limits _{i, j = 1}^{n_\psi } \alpha _{ij}^\psi \phi _{ij}^\psi$ is called the $\psi$ -component of f, and the $n_\psi \times n_\psi$ matrix $M(f)_\psi := \big ( \alpha _{ij}^\psi \big )_{i, j}$ is called the $\psi$ -matrix of f.

For a matrix $M = (\alpha _{ij})_{i, j}$, let $\overline{M} = (\overline{\alpha _{ij}})_{i, j}$. Then for any $f \in \mathbb C^G$, it follows from Lemma 2.8 and (2.7) that

$$\begin{aligned} M \!\left( \overline{f} \right) _\psi = \frac{n_\psi }{|G |} \overline{ \widehat{f}(\Phi _\psi )}, \quad \hbox {for any } \psi \in {{\mathrm{Irr}}}(G). \end{aligned}$$

(3.2)

Hence, the following are equivalent by the remark before Lemma 2.11: (i) $f(s) = 0$ for any $s \in G {\setminus } \{ 1_G \}$; (ii) $M(f)_\psi = f(1) \frac{n_\psi }{|G |} I_{n_\psi }$, for any $\psi \in {{\mathrm{Irr}}}(G)$; and (iii) $\widehat{f}(\Phi _\psi ) = f(1) I_{n_\psi }$, for any $\psi \in {{\mathrm{Irr}}}(G)$.

The convolutions of functions on G play an important role in the study of bent functions when G is abelian. For any two functions $\sigma , \tau \in \mathbb C^G$, the convolution of $\sigma$ and $\tau$, $\sigma * \tau$, is defined by

$$\begin{aligned} \sigma * \tau : \ G \rightarrow \mathbb C, \quad a \mapsto \sum _{s \in G} \sigma (s) \tau (s^{-1} a). \end{aligned}$$

(3.3)

If G is abelian and $\tau \in \widehat{G}$, then $\tau (s^{-1}) = \overline{\tau (s)}$ for any $s \in G$. But if G is nonabelian, then for any $\phi _{ij}^\psi \in \widehat{G}$ and $s \in G$, $\phi _{ij}^\psi (s^{-1}) \ne \overline{\phi _{ij}^\psi (s)}$ in general (see Lemma 2.2(iii)). So for nonabelian finite groups, we need a modified convolution.

Definition 3.6

Let $f, g \in \mathbb C^G$. Then the quasi-convolution of f and g, $f \!\circledast \!g$, is defined by

$$\begin{aligned} f \!\circledast \!g: \ G \rightarrow \mathbb C, \quad a \mapsto \sum _{x \in G} f(ax) \overline{g(x)}. \end{aligned}$$

Lemma 3.7

Let $f, g \in \mathbb C^G$. Then the following hold.

(i):

For any $\psi \in {{\mathrm{Irr}}}(G)$, $M(f \!\circledast \!g)_\psi = \frac{|G |}{n_\psi } M(f)_\psi \big [ M(g)_\psi \big ]^*$.

(ii):

For any $\psi , \chi \in {{\mathrm{Irr}}}(G)$, $(f \!\circledast \!g)_\psi = f_\psi \!\circledast \!g_\psi$, and $f_\psi \!\circledast \!g_\chi = 0$ if $\psi \ne \chi$.

Proof

(i) Assume that $f = \sum \nolimits _{(\psi , i, j)} \alpha _{ij}^\psi \phi _{ij}^\psi$, and $g = \sum \nolimits _{(\chi , k, l)} \beta _{kl}^\chi \phi _{kl}^\chi$. Then for any $a \in G$, it follows from Lemma 2.2(iv) and Lemma 2.4 that

$$\begin{aligned} (f \!\circledast \!g)(a)= & {} \sum _{x \in G} \sum _{(\psi , i, j)} \alpha _{ij}^\psi \phi _{ij}^\psi (ax) \sum _{(\chi , k, l)} \overline{\beta _{kl}^\chi } \, \overline{ \phi _{kl}^\chi (x)} \\= & {} \sum _{(\psi , i, j)} \sum _{(\chi , k, l)} \alpha _{ij}^\psi \overline{\beta _{kl}^\chi } \sum _{x \in G} \sum _{m = 1}^{n_\psi } \phi _{im}^\psi (a) \phi _{mj}^\psi (x) \overline{ \phi _{kl}^\chi (x)} \\= & {} \sum _{(\psi , i, j)} \sum _{(\chi , k, l)} \alpha _{ij}^\psi \overline{\beta _{kl}^\chi } \sum _{m = 1}^{n_\psi } \phi _{im}^\psi (a) \left\langle \phi _{mj}^\psi , \phi _{kl}^\chi \right\rangle _G \\= & {} \sum _{(\psi , i, j)} \sum _{k = 1}^{n_\psi } \frac{|G |}{n_\psi } \alpha _{ij}^\psi \overline{\beta _{kj}^\psi } \phi _{ik}^\psi (a) \ = \ \sum _{(\psi , i, k)} \frac{|G |}{n_\psi } \sum _{j = 1}^{n_\psi } \alpha _{ij}^\psi \overline{\beta _{kj}^\psi } \phi _{ik}^\psi (a). \end{aligned}$$

So (i) holds.

(ii) follows directly from (i) and its proof. $\square$

The next lemma characterizes a function with balanced derivatives in terms of its $\psi$-matrices, for all $\psi \in {{\mathrm{Irr}}}(G)$.

Lemma 3.8

Let $f: G \rightarrow \mathbb C$ be a function. Then the following are equivalent.

(i):

For any $a \in G {\setminus } \{ 1_G \}$, $d_a f$ is balanced.

(ii):

$f \!\circledast \!f = \frac{\beta }{|G |} \rho$, where $\beta = \sum _{x \in G} |f(x) |^2$, and $\rho$ is the regular character.

(iii):

For any $\psi \in {{\mathrm{Irr}}}(G)$,

$$\begin{aligned} M(f)_\psi \big [ M(f)_\psi \big ]^* = \frac{n^2_\psi }{|G |^2} \beta I_{n_\psi }, \quad \hbox {where } \beta \hbox { is the same as in (ii)}. \end{aligned}$$

Proof

Since for any $a \in G$, $\sum _{x \in G} d_a f(x) = \sum _{x \in G} f(ax) \overline{f(x)} = ( f \!\circledast \!f )(a)$, (i) and (ii) are equivalent. From the remark after Definition 3.5, (ii) holds if and only if for any $\psi \in {{\mathrm{Irr}}}(G)$, $M(f \!\circledast \!f)_\psi = \frac{n_\psi }{|G |} \beta I_{n_\psi }$. Hence, (ii) and (iii) are equivalent by Lemma 3.7. $\square$

Since for a function $f: G \rightarrow T$, $f \!\circledast \!f = \rho$ if and only if $\overline{f} \!\circledast \!\overline{f} = \rho$, as a direct consequence of Lemma 3.8 and (3.2), we have the next result.

Corollary 3.9

(Cf. [18, Theorem 3]) A function $f: G \rightarrow T$ is bent if and only if for any $a \in G {\setminus } \{ 1_G \}$, $d_a f$ is balanced.

Remark 3.10

Theorem 3.3 can also be obtained as a consequence of Theorem 3.4 (with $N = G$) and Corollary 3.9. But our approach to the proof of Theorem 3.3 yields Corollary 3.9 as a direct consequence, and provides a clear explanation why Theorem 3.3 and Corollary 3.9 are true.

Similar to Definition 3.6, we can define the quasi-convolution of two functions on the dual basis $\widehat{G}$ as a function on G.

Definition 3.11

Let $\sigma , \tau$ be functions on the dual basis $\widehat{G}$. Then the quasi-convolution of $\sigma$ and $\tau$, $\sigma \!\circledast \!\tau$, is a function on G defined by

$$\begin{aligned} \sigma \!\circledast \!\tau : \ G \rightarrow \mathbb C, \quad a \mapsto \sum _{(\psi , i, j)} n_\psi \sigma (a \phi _{ij}^\psi )\, \overline{\tau (\phi _{ij}^\psi )}. \end{aligned}$$

Therefore, for any $\sigma , \tau \in \mathbb C^{\widehat{G}}$,

$$\begin{aligned} (\sigma \!\circledast \!\tau )(1_G) = \langle \sigma , \tau \rangle _{\widehat{G}} \quad \hbox {and} \quad \sum _{(\psi , i, j)} n_\psi \, d_a \sigma (\phi _{ij}^\psi ) = (\sigma \!\circledast \!\sigma ) (a), \ \hbox { for any } a \in G. \end{aligned}$$

(3.4)

For any function $\sigma : \widehat{G} \rightarrow \mathbb C$ and any $\psi \in {{\mathrm{Irr}}}(G)$, let $\sigma (\Phi _\psi )$ be the $n_\psi \times n_\psi$ matrix $\big ( \sigma (\phi _{ij}^\psi ) \big )_{i, j}$, and let $\overline{\sigma (\Phi _\psi )}$ be the conjugate of $\sigma (\Phi _\psi )$, i.e. $\overline{\sigma (\Phi _\psi )} := \Big (\, \overline{\sigma (\phi _{ij}^\psi )}\, \Big )_{i, j}$. The transpose of a matrix M is denoted by $M^\top$.

Lemma 3.12

For any functions $\sigma$ and $\tau$ on $\widehat{G}$ and any $\psi \in {{\mathrm{Irr}}}(G)$, the $\psi$-matrix of $\overline{\sigma \!\circledast \!\tau }$ is

$$\begin{aligned} M \big ( \overline{\sigma \!\circledast \!\tau } \big )_\psi = n_\psi \,\overline{\sigma (\Phi _\psi )}\, \tau (\Phi _\psi )^\top . \end{aligned}$$

Proof

Since for any $a \in G$ and $\phi _{ij}^\psi \in \widehat{G}$, $a \phi _{ij}^\psi = \sum _{k=1}^{n_\psi } \phi _{ik}^\psi (a^{-1}) \phi _{kj}^\psi$ by (2.4), it follows that

$$\begin{aligned} \sum _{(\psi , i, j)} n_\psi \sigma (a \phi _{ij}^\psi )\, \overline{\tau (\phi _{ij}^\psi )}= & {} \sum _{(\psi , i, j)} n_\psi \sum _{k=1}^{n_\psi } \phi _{ik}^\psi (a^{-1}) \sigma (\phi _{kj}^\psi )\, \overline{\tau (\phi _{ij}^\psi )} \\= & {} \sum _{\psi \in {{\mathrm{Irr}}}(G)} n_\psi \sum _{k, i =1}^{n_\psi } \left( \sum _{j=1}^{n_\psi } \sigma (\phi _{kj}^\psi )\, \overline{\tau (\phi _{ij}^\psi )} \right) \overline{\phi _{ki}^\psi (a)}. \end{aligned}$$

Let $\beta _{ki}^\psi$ be the (k, i)-entry of $\sigma (\Phi _\psi ) \big [ \tau (\Phi _\psi ) \big ]^*$. Then $\beta _{ki}^\psi = \sum _{j=1}^{n_\psi } \sigma (\phi _{kj}^\psi )\, \overline{\tau (\phi _{ij}^\psi )}$. Hence,

$$\begin{aligned} (\sigma \!\circledast \!\tau )(a) = \sum _{(\psi , k, i)} n_\psi \beta _{ki}^\psi \overline{\phi _{ki}^\psi (a)}, \quad \hbox { for any } a \in G. \end{aligned}$$

So the lemma holds. $\square$

Now we are ready to prove Theorem 3.3.

Proof of Theorem 3.3

Since $\langle \widehat{f}, \widehat{f} \rangle _{\widehat{G}} = |G | \langle f, f \rangle _G = |G |^2$ by Lemma 2.13, it follows from (3.4) that

$$\begin{aligned} \hbox {(ii) holds} \quad \Leftrightarrow \quad \widehat{f} \!\circledast \!\widehat{f} = |G | \rho \quad \Leftrightarrow \quad \overline{\widehat{f} \!\circledast \!\widehat{f}} = |G | \rho , \end{aligned}$$

where $\rho$ is the regular character. But by Lemma 3.12,

$$\begin{aligned} \overline{\widehat{f} \!\circledast \!\widehat{f}} = |G | \rho\Leftrightarrow & {} M \Big (\,\overline{\widehat{f} \!\circledast \!\widehat{f}}\, \Big )_\psi = n_\psi |G | I_{n_\psi }, \ \hbox { for any } \psi \in {{\mathrm{Irr}}}(G) \\\Leftrightarrow & {} \overline{\widehat{f}(\Phi _\psi )} \left[ \widehat{f}(\Phi _\psi ) \right] ^\top = |G | I_{n_\psi }, \ \hbox { for any } \psi \in {{\mathrm{Irr}}}(G). \end{aligned}$$

Since $\overline{\widehat{f}(\Phi _\psi )} \left[ \widehat{f}(\Phi _\psi ) \right] ^\top = |G | I_{n_\psi }$ if and only if $\widehat{f}(\Phi _\psi ) \left[ \widehat{f}(\Phi _\psi ) \right] ^* = |G | I_{n_\psi }$, the theorem holds. $\square$

In order to prove Theorem 3.4, we need the next two lemmas. Lemma 3.13 is also needed for the proof of Theorem 4.3 in Sect. 4.

Lemma 3.13

Let N be a normal subgroup of G. Then the following hold.

(i):

For any $s \in G$,

$$\begin{aligned} \sum _{(\psi , i),\psi \in N^\perp } n_\psi \phi _{ii}^\psi (s) = {\left\{ \begin{array}{ll} |G/N |, &{} \hbox { if } s \in N; \\ 0, &{} \hbox { if } s \notin N. \end{array}\right. } \end{aligned}$$

(3.5)

(ii):

For any $a \in N {\setminus } \{ 1_G \}$ and $b \in G$,

$$\begin{aligned} \sum _{(\psi , i), \psi \notin N^\perp } n_\psi \phi _{ii}^\psi (a^{-1} b) = {\left\{ \begin{array}{ll} |G | - |G/N |, &{} \hbox { if } b = a; \\ - |G/N |, &{} \hbox { if } b \in N {\setminus } \{ a \}; \\ 0, &{} \hbox { otherwise}. \end{array}\right. } \end{aligned}$$

(3.6)

Proof

(i) For any $\psi \in {{\mathrm{Irr}}}(G)$ such that $\ker \psi \supseteq N$, $\Phi _\psi$ is also an irreducible representation of the quotient group G / N with $\Phi _\psi (sN) = \Phi _\psi (s)$, for any $s \in G$, and $\psi$ is also an irreducible character of G / N with $\psi (sN) = \psi (s)$, for any $s \in G$. Furthermore, ${{\mathrm{Irr}}}(G/N) = \{ \psi \, : \, \psi \in {{\mathrm{Irr}}}(G) \hbox { and } \ker \psi \supseteq N \}$, i.e. ${{\mathrm{Irr}}}(G/N) = N^\perp$. Hence, $\sum \nolimits _{ \psi \in N^\perp } \sum \nolimits _{1 \le i \le n_\psi } n_\psi \phi _{ii}^\psi$ is the regular character of G / N, and (i) holds.

(ii) Since

$$\begin{aligned} \sum _{(\psi , i), \psi \notin N^\perp } n_\psi \phi _{ii}^\psi (a^{-1} b)= & {} \sum _{(\psi , i)} n_\psi \phi _{ii}^\psi (a^{-1} b) - \sum _{(\psi , i), \psi \in N^\perp } n_\psi \phi _{ii}^\psi (a^{-1} b) \\= & {} \rho (a^{-1} b) - \sum _{(\psi , i), \psi \in N^\perp } n_\psi \phi _{ii}^\psi (a^{-1} b), \end{aligned}$$

where $\rho$ is the regular character of G, (ii) follows directly from (3.5). $\square$

Lemma 3.14

Let $f \in \mathbb C^G$. Then for any $a \in G$,

$$\begin{aligned} \sum _{(\psi , i, j)} n_\psi \big ( d_a \widehat{f}\, \big ) (\phi _{ij}^\psi ) = |G | \sum _{t \in G} \big ( d_a f \big ) (t). \end{aligned}$$

Proof

For any $a, s \in G$ and $\phi _{ij}^\psi \in \widehat{G}$, $\left( a \phi _{ij}^\psi \right) (s) = \phi _{ij}^\psi (a^{-1} s)$ by (2.3). Thus,

$$\begin{aligned} \sum _{j=1}^{n_\psi } \big ( d_a \widehat{f}\, \big ) (\phi _{ij}^\psi )= & {} \sum _{j=1}^{n_\psi } \widehat{f}(a \phi _{ij}^\psi ) \overline{\widehat{f}(\phi _{ij}^\psi )} \ = \ \sum _{j=1}^{n_\psi } \sum _{s, t \in G} f(s) \left( a \phi _{ij}^\psi \right) (s)\, \overline{f(t)}\, \overline{\phi _{ij}^\psi (t)} \\= & {} \sum _{s, t \in G} \sum _{j=1}^{n_\psi } \phi _{ij}^\psi (a^{-1} s) \overline{\phi _{ij}^\psi (t)} \, f(s) \overline{f(t)} \\= & {} \sum _{s, t \in G} \phi _{ii}^\psi (a^{-1} s t^{-1}) f(s) \overline{f(t)}. \quad \hbox {(by Lemma } 2.2\hbox {(iii, iv))} \\= & {} \sum _{b, t \in G} \phi _{ii}^\psi (a^{-1} b) f(bt) \overline{f(t)}. \quad (\hbox {where } b = s t^{-1}) \end{aligned}$$

That is,

$$\begin{aligned} \sum _{j=1}^{n_\psi } \big ( d_a \widehat{f}\, \big ) (\phi _{ij}^\psi ) = \sum _{b, t \in G} \phi _{ii}^\psi (a^{-1} b) f(bt) \overline{f(t)}. \end{aligned}$$

(3.7)

Hence,

$$\begin{aligned} \sum _{(\psi , i, j)} n_\psi \big ( d_a \widehat{f}\, \big ) (\phi _{ij}^\psi )= & {} \sum _{(\psi , i)} \sum _{b, t \in G} n_\psi \phi _{ii}^\psi (a^{-1} b) f(bt) \overline{f(t)} \\= & {} \sum _{b, t \in G} \rho (a^{-1} b) f(bt) \overline{f(t)} \quad \hbox {(where} \ \rho \ \hbox {is the regular character of G)} \\= & {} |G | \sum _{t \in G} f(at)\overline{f(t)}. \end{aligned}$$

So the lemma holds. $\square$

Now we are ready to prove Theorem 3.4.

Proof of Theorem 3.4

The equivalence of (i) and (ii) follows directly from Lemma 3.14. In the following we prove that (ii) implies (iii) and that (iii) implies (i).

Assume (ii). Then for any $a \in N {\setminus } \{ 1_G \}$,

$$\begin{aligned}&{\sum _{(\psi , i, j), \psi \notin N^\perp } n_\psi \big ( d_a \widehat{f}\, \big ) (\phi _{ij}^\psi ) } \\&\quad = \sum _{(\psi , i, j)} n_\psi \big ( d_a \widehat{f}\, \big ) (\phi _{ij}^\psi ) - \sum _{(\psi , i, j), \psi \in N^\perp } n_\psi \big ( d_a \widehat{f}\, \big ) (\phi _{ij}^\psi ) \\&\quad = 0 - \sum _{(\psi , i), \psi \in N^\perp } \sum _{b, t \in G} n_\psi \phi _{ii}^\psi (a^{-1} b) f(bt) \overline{f(t)} \quad \hbox {(by (ii) and }(3.7) \\&\quad = -|G/N | \sum _{b \in N, t \in G} f(bt) \overline{f(t)} \quad \hbox {(by }(3.5), \hbox {because }a \in N) \\&\quad = - \frac{|G |}{|N |} \sum _{t \in G} f(t) \overline{f(t)} \quad \hbox {(from the equivalence of (i) and (ii))} \\&\quad = - \frac{|G |^2}{|N |}. \end{aligned}$$

This proves that (ii) implies (iii).

Now assume (iii). For any $a \in N {\setminus } \{ 1_G \}$,

$$\begin{aligned}&{\sum _{(\psi , i, j), \psi \notin N^\perp } n_\psi \big ( d_a \widehat{f}\, \big ) (\phi _{ij}^\psi ) } \\&\quad = \sum _{(\psi , i), \psi \notin N^\perp } \sum _{b, t \in G} n_\psi \phi _{ii}^\psi (a^{-1} b) f(bt) \overline{f(t)} \quad (\hbox {by } (3.7) \\&\quad = (|G | - |G/N |) \sum _{t \in G} f(at) \overline{f(t)} - |G/N | \sum _{b \in N {\setminus } \{ a \}} \sum _{t \in G} f(bt) \overline{f(t)} \quad \hbox {(by } (3.6) \\&\quad = |G | \sum _{t \in G} f(at) \overline{f(t)} - |G/N | \sum _{b \in N} \sum _{t \in G} f(bt) \overline{f(t)} \\&\quad = |G | \sum _{t \in G} f(at) \overline{f(t)} - |G/N | \sum _{\begin{array}{c} b \in N \\ b \ne 1_G \end{array}} \sum _{t \in G} f(bt) \overline{f(t)} - \frac{|G |^2}{|N |}. \end{aligned}$$

Thus, (iii) implies that

$$\begin{aligned} |G | \sum _{t \in G} f(at) \overline{f(t)} - |G/N | \sum _{\begin{array}{c} b \in N \\ b \ne 1_G \end{array}} \sum _{t \in G} f(bt) \overline{f(t)} = 0, \quad \hbox {for any } a \in N {\setminus } \{ 1_G \}. \end{aligned}$$

That is,

$$\begin{aligned} |N | \sum _{t \in G} f(at) \overline{f(t)} = \sum _{\begin{array}{c} b \in N \\ b \ne 1_G \end{array}} \sum _{t \in G} f(bt) \overline{f(t)}, \quad \hbox {for any } a \in N {\setminus } \{ 1_G \}. \end{aligned}$$

The above equality says that $\sum _{t \in G} f(at) \overline{f(t)}$ are equal for all $a \in N {\setminus } \{ 1_G \}$, and hence

$$\begin{aligned} |N | \sum _{t \in G} f(at) \overline{f(t)} = (|N | - 1) \sum _{t \in G} f(at) \overline{f(t)}, \quad \hbox { for all } a \in N {\setminus } \{ 1_G \}. \end{aligned}$$

So we must have that $\sum _{t \in G} f(at) \overline{f(t)} = 0$, for all $a \in N {\setminus } \{ 1_G \}$. This proves that (iii) implies (i). $\square$

4 Perfect nonlinear functions

In this section we always assume that G and H are arbitrary finite groups, and study characterizations of perfect nonlinear functions from G to H. Our main results are Theorems 4.2, 4.3, and 4.7.

Let $f: G \rightarrow H$ be a function. For any $h \in H$, let $f^{-1}(h) := \{ s \in G \, : \, f(s) = h \}$ be the inverse image of h under f. If $|H |$ divides $|G |$, and for any $h \in H$, $|f^{-1}(h) | = |G | / |H |$, then we say that f is evenly-balanced (cf [26]). An evenly-balanced function is also called a balanced function in the literature (cf. [4, 19]).

The (left) derivative of a function $f: G \rightarrow H$ in direction $a \in G$ is defined by (cf. [19])

$$\begin{aligned} D_a f: \ G \rightarrow H, \quad x \mapsto f(ax) f(x)^{-1}. \end{aligned}$$

Definition 4.1

(Cf. [19, Definition 1.1])  Let G, H be finite groups. Then a function $f: G \rightarrow H$ is said to be perfect nonlinear if for any $a \in G {\setminus } \{ 1_G \}$, $D_a f$ is evenly-balanced.

For any two functions $\sigma , \tau \in \mathbb C^G$, the convolution of $\sigma$ and $\tau$, $\sigma * \tau$, is defined by (3.3). It is clear that for any $a \in G$, $(\sigma * \tau )(a) = \sum _{s \in G} \sigma (as) \tau (s^{-1})$. For any $\sigma \in \mathbb C^G$, we define a function $\overline{\sigma }^{(-)} \in \mathbb C^G$ by

$$\begin{aligned} \overline{\sigma }^{(-)}: \ G \rightarrow \mathbb C, \quad a \mapsto \overline{\sigma (a^{-1})}. \end{aligned}$$

Since $\{ {\mathbf {1}}_s \, : \, s \in G \}$ is a basis of $\mathbb C^G$, where ${\mathbf {1}}_s$ is the characteristic function (i.e. ${{\mathbf {1}}}_s(t) = 0$ if $t \ne s$ and ${{\mathbf {1}}}_s(s) = 1$), for any function $f: G \rightarrow H$, we can define the dual function $\widetilde{f}$ of f as follows:

$$\begin{aligned} \widetilde{f}: \ \mathbb C^G \rightarrow \mathbb C^H, \quad \sum _{s \in G} \alpha _s {\mathbf {1}}_s \mapsto \sum _{s \in G} \alpha _s {\mathbf {1}}_{f(s)}. \end{aligned}$$

In particular, $\widetilde{f}$ is also a function on $\widehat{G}$.

The next theorem characterizes a perfect nonlinear function in terms of its dual function and the dual basis $\widehat{G}$.

Theorem 4.2

Let G, H be finite groups, and $f: G \rightarrow H$ a function. Then the following are equivalent.

(i):

f is a perfect nonlinear function.

(ii):

For any $a \in G {\setminus } \{ 1_G \}$,

$$\begin{aligned} \sum _{(\psi , i, j)} n_\psi \left( \widetilde{f}(a \phi _{ij}^\psi ) * \overline{\big [ \widetilde{f}(\phi _{ij}^\psi ) \big ] }^{(-)} \right) = \frac{|G |^2}{|H |} \zeta _1, \end{aligned}$$

where $\zeta _1$ is the principal irreducible character of H.

Let $f: G \rightarrow H$ be a function. In the case that f is not perfect nonlinear, the set $\{ a \in G | D_a f: G \rightarrow H$ is evenly-balanced} describes how close f is to being perfect nonlinear. Let N be a normal subgroup of G. The next theorem discusses the sufficient and necessary conditions under which $D_a f: G \rightarrow H$ is evenly-balanced for any $a \in N {\setminus } \{ 1_G \}$. Recall that $N^\perp := \{ \psi \, : \, \psi \in {{\mathrm{Irr}}}(G)$ and $\ker \psi \supseteq N \}$ (see (3.1)).

Theorem 4.3

Let G, H be finite groups, $f: G \rightarrow H$ a function, and $N \ (\ne \{ 1_G \})$ a normal subgroup of G. Let $\rho _H$ and $\zeta _1$ be the regular character and principal irreducible character of H, respectively. Then the following are equivalent.

(i):

For any $a \in N {\setminus } \{ 1_G \}$, $D_a f: G \rightarrow H$ is evenly-balanced.

(ii):

For any $a \in N {\setminus } \{ 1_G \}$,

$$\begin{aligned} \sum _{(\psi , i, j)} n_\psi \left( \widetilde{f}(a \phi _{ij}^\psi ) * \overline{\big [ \widetilde{f}(\phi _{ij}^\psi ) \big ]}^{(-)} \right) = \frac{|G |^2}{|H |} \zeta _1. \end{aligned}$$

(iii):

For any $a \in N {\setminus } \{ 1_G \}$,

$$\begin{aligned} \sum _{(\psi , i, j), \psi \notin N^\perp } n_\psi \left( \widetilde{f}(a \phi _{ij}^\psi ) * \overline{\big [ \widetilde{f}(\phi _{ij}^\psi ) \big ]}^{(-)} \right) = \frac{|G |^2}{|H | \cdot |N |} (\zeta _1 - \rho _H). \end{aligned}$$

Note that Theorem 4.2 is a special case of Theorem 4.3 with $N = G$. So we only need to prove Theorem 4.3. We need the next two lemmas first.

Lemma 4.4

Let G, H be finite groups, and $f: G \rightarrow H$ a function. Then f is evenly-balanced if and only if

$$\begin{aligned} \sum _{s \in G} {\mathbf {1}}_{f(s)} = \frac{|G |}{|H |} \zeta _1, \quad \hbox {where}~\zeta _1 \ \hbox {is the principal irreducible character\ of } H. \end{aligned}$$

Proof

If f is evenly-balanced, then in the group algebra $\mathbb CH$,

$$\begin{aligned} \sum _{s \in G} f(s) = \frac{|G |}{|H |} \sum _{h \in H} h. \end{aligned}$$

(4.1)

On the other hand, if (4.1) holds, then for any $h \in H$, by comparing the coefficients of h in both sides of (4.1), we see that $|H |$ divides $|G |$, and $|f^{-1}(h) | = |G |/|H |$. Thus, f is evenly-balanced if and only if (4.1) holds. Since $\{ {\mathbf {1}}_h \, : \, h \in H \}$ is a basis of $\mathbb C^H$, it follows that (4.1) holds if and only if

$$\begin{aligned} \sum _{s \in G} {\mathbf {1}}_{f(s)} = \frac{|G |}{|H |} \sum _{h \in H} {\mathbf {1}}_h = \frac{|G |}{|H |} \zeta _1. \end{aligned}$$

So the lemma holds. $\square$

Lemma 4.5

Let G, H be finite groups, $a \in G {\setminus } \{ 1_G \}$, and $f: G \rightarrow H$ a function. Then $D_a f$ is evenly-balanced if and only if

$$\begin{aligned} \sum _{(\psi , i, j)} n_\psi \left( \widetilde{f}(a \phi _{ij}^\psi ) * \overline{\big [ \widetilde{f}(\phi _{ij}^\psi ) \big ]}^{(-)} \right) = \frac{|G |^2}{|H |} \zeta _1, \end{aligned}$$

where   $\zeta _{1}$   is the principal irreducible character of H.

Proof

Since $\phi _{ij}^\psi = \sum _{s \in G} \phi _{ij}^\psi (s) {\mathbf {1}}_s$, and $\overline{\left( {\mathbf {1}}_{f(s)} \right) }^{(-)} = {\mathbf {1}}_{f(s)^{-1}}$, we see that

$$\begin{aligned} \widetilde{f}(\phi _{ij}^\psi ) = \sum _{s \in G} \phi _{ij}^\psi (s) {\mathbf {1}}_{f(s)} \quad \hbox {and} \quad \overline{\left[ \widetilde{f}(\phi _{ij}^\psi ) \right] }^{(-)} = \sum _{s \in G} \overline{\phi _{ij}^\psi (s)} {\mathbf {1}}_{f(s)^{-1}}, \quad \hbox { for any } \phi _{ij}^\psi \in \widehat{G}. \end{aligned}$$

Furthermore, it follows from $a \phi _{ij}^\psi = \sum _{k=1}^{n_\psi } \phi _{ik}^\psi (a^{-1}) \phi _{kj}^\psi$ that

$$\begin{aligned} \widetilde{f}(a \phi _{ij}^\psi ) = \sum _{k=1}^{n_\psi } \phi _{ik}^\psi (a^{-1}) \widetilde{f}(\phi _{kj}^\psi ) = \sum _{k=1}^{n_\psi } \sum _{t \in G} \phi _{ik}^\psi (a^{-1}) \phi _{kj}^\psi (t) {\mathbf {1}}_{f(t)}. \end{aligned}$$

Since ${\mathbf {1}}_{f(t)} * {\mathbf {1}}_{f(s)^{-1}} = {\mathbf {1}}_{f(t) f(s)^{-1}}$, Lemma 2.2(iii, iv) yields that

$$\begin{aligned} \sum _{j = 1}^{n_\psi } \left( \widetilde{f}(a \phi _{ij}^\psi ) * \overline{\big [ \widetilde{f}(\phi _{ij}^\psi ) \big ]}^{(-)} \right)= & {} \sum _{s, t \in G} \sum _{j,k=1}^{n_\psi } \phi _{ik}^\psi (a^{-1}) \phi _{kj}^\psi (t) \overline{\phi _{ij}^\psi (s)} \big ( {\mathbf {1}}_{f(t)} * {\mathbf {1}}_{f(s)^{-1}} \big ) \\= & {} \sum _{s, t \in G} \phi _{ii}^\psi (a^{-1}t s^{-1}) {\mathbf {1}}_{f(t) f(s)^{-1}} \\= & {} \sum _{b, s \in G} \phi _{ii}^\psi (a^{-1} b) {\mathbf {1}}_{f(bs) f(s)^{-1}}. \quad (\hbox {where } b = t s^{-1}) \end{aligned}$$

That is,

$$\begin{aligned} \sum _{j = 1}^{n_\psi } \left( \widetilde{f}(a \phi _{ij}^\psi ) * \overline{\big [ \widetilde{f}(\phi _{ij}^\psi ) \big ]}^{(-)} \right) = \sum _{b, s \in G} \phi _{ii}^\psi (a^{-1} b) {\mathbf {1}}_{f(bs) f(s)^{-1}}. \end{aligned}$$

(4.2)

Therefore,

$$\begin{aligned} \sum _{(\psi , i, j)} n_\psi \left( \widetilde{f}(a \phi _{ij}^\psi ) * \overline{\big [ \widetilde{f}(\phi _{ij}^\psi ) \big ]}^{(-)} \right)= & {} \sum _{b, s \in G} \sum _{(\psi , i)} n_\psi \phi _{ii}^\psi (a^{-1} b) {\mathbf {1}}_{f(bs) f(s)^{-1}} \\= & {} |G | \sum _{s \in G} {\mathbf {1}}_{f(as) f(s)^{-1}}. \end{aligned}$$

Hence, the lemma holds by Lemma 4.4. $\square$

Now we are ready to prove Theorem 4.3.

Proof of Theorem 4.3

The equivalence of (i) and (ii) follows directly from Lemma 4.5. In the following we prove that (ii) implies (iii) and that (iii) implies (i).

Assume (ii). Then

$$\begin{aligned}&{\sum _{(\psi , i, j), \psi \notin N^\perp } n_\psi \left( \widetilde{f}(a \phi _{ij}^\psi ) * \overline{\big [ \widetilde{f}(\phi _{ij}^\psi ) \big ]}^{(-)} \right) } \\&\quad = \sum _{(\psi , i, j)} n_\psi \left( \widetilde{f}(a \phi _{ij}^\psi ) * \overline{\big [ \widetilde{f}(\phi _{ij}^\psi ) \big ]}^{(-)} \right) - \sum _{(\psi , i, j), \psi \in N^\perp } n_\psi \left( \widetilde{f}(a \phi _{ij}^\psi ) * \overline{\big [ \widetilde{f}(\phi _{ij}^\psi ) \big ]}^{(-)} \right) \\&\quad = \frac{|G |^2}{|H |} \zeta _1 - \sum _{b, s \in G} \sum _{(\psi , i), \psi \in N^\perp } n_\psi \phi _{ii}^\psi (a^{-1} b) {\mathbf {1}}_{f(bs) f(s)^{-1}} \quad \hbox {(by (ii) and} \ (4.2))\\&\quad = \frac{|G |^2}{|H |} \zeta _1 - |G/N | \sum _{b \in N} \sum _{s \in G} {\mathbf {1}}_{f(bs) f(s)^{-1}}, \quad \hbox {(by }(3.5)) \end{aligned}$$

Since (i) and (ii) are equivalent, i.e. $D_b f: G \rightarrow H$ is evenly-balanced for any $b \in N {\setminus } \{ 1_G \}$, by Lemma 4.4 we see that

$$\begin{aligned} \sum _{b \in N} \sum _{s \in G} {\mathbf {1}}_{f(bs) f(s)^{-1}} = \frac{|G |}{|H |} \rho _H + (|N | - 1) \frac{|G |}{|H |} \zeta _1. \end{aligned}$$

Thus, (iii) holds.

Now assume (iii). Note that

$$\begin{aligned}&{\sum _{(\psi , i, j), \psi \notin N^\perp } n_\psi \left( \widetilde{f}(a \phi _{ij}^\psi ) * \overline{\big [ \widetilde{f}(\phi _{ij}^\psi ) \big ]}^{(-)} \right) } \\&\quad = \sum _{b, s \in G} \sum _{(\psi , i), \psi \notin N^\perp } n_\psi \phi _{ii}^\psi (a^{-1} b) {\mathbf {1}}_{f(bs) f(s)^{-1}} \quad \hbox {(by }(4.2))\\&\quad = (|G | - |G/N |)\sum _{s \in G} {\mathbf {1}}_{f(as) f(s)^{-1}} - |G/N | \sum _{b \in N {\setminus } \{ a \} } \sum _{s \in G} {\mathbf {1}}_{f(bs) f(s)^{-1}}, \ \quad (\hbox {by }(3.6))\\&\quad = |G | \sum _{s \in G} {\mathbf {1}}_{f(as) f(s)^{-1}} - |G/N | \sum _{b \in N} \sum _{s \in G} {\mathbf {1}}_{f(bs) f(s)^{-1}}. \end{aligned}$$

So (iii) implies that for any $a \in N {\setminus } \{ 1_G \}$,

$$\begin{aligned} |G | \sum _{s \in G} {\mathbf {1}}_{f(as) f(s)^{-1}} - |G/N | \sum _{\begin{array}{c} b \in N \\ b \ne 1_G \end{array} } \sum _{s \in G} {\mathbf {1}}_{f(bs) f(s)^{-1}} = \frac{|G |^2}{|N | \cdot |H |} \zeta _1. \end{aligned}$$

(4.3)

The above equality implies that $\sum _{s \in G} {\mathbf {1}}_{f(as) f(s)^{-1}}$ are equal for all $a \in N {\setminus } \{ 1_G \}$, and hence

$$\begin{aligned} \big ( |G | - |G/N | (|N | - 1) \big ) \sum _{s \in G} {\mathbf {1}}_{f(as) f(s)^{-1}} = \frac{|G |^2}{|N | \cdot |H |} \zeta _1, \quad \hbox {for any } a \in N {\setminus } \{ 1_G \}. \end{aligned}$$

Hence,

$$\begin{aligned} \sum _{s \in G} {\mathbf {1}}_{f(as) f(s)^{-1}} = \frac{|G |}{|H |} \zeta _1, \quad \hbox { for any } a \in N {\setminus } \{ 1_G \}. \end{aligned}$$

Thus, $D_a f$ is evenly-balanced for any $a \in N {\setminus } \{ 1_G \}$ by Lemma 4.4, and (i) holds. $\square$

For each $\zeta \in {{\mathrm{Irr}}}(H)$, let us fix a unitary irreducible representation $\Lambda _\zeta := \big ( \lambda _{ij}^\zeta \big )_{i, j}$ of H. Let $\widehat{H} := \{ \lambda _{ij}^\zeta \, : \, \zeta \in {{\mathrm{Irr}}}(H), 1\le i, j\le n _{\zeta } \}$ be a dual basis of H, and let ${{\mathrm{Irr}}}(H)^\sharp := {{\mathrm{Irr}}}(H) {\setminus } \{ \zeta _1 \}$, where $\zeta _1$ is the principal irreducible character of H. For any function $f: G \rightarrow H$ and any $\lambda _{ij}^\zeta \in \widehat{H}$, we define a function $f_{ij}^\zeta$ on G as follows:

$$\begin{aligned} f_{ij}^\zeta : \ G \rightarrow \mathbb C, \quad a \mapsto \sum _{s \in G} \big ( \lambda _{ij}^\zeta \circ D_a f \big ) (s). \end{aligned}$$

$f_{ij}^\zeta$ is called an autocorrelation function of f in [19].

Lemma 4.6

Let G, H be finite groups, and $f: G \rightarrow H$ a function. Then for any $\zeta \in {{\mathrm{Irr}}}(H)$,

$$\begin{aligned} f_{ij}^\zeta = \sum _{k = 1}^{n_\zeta } \big [ (\lambda _{ik}^\zeta \circ f) \!\circledast \!(\lambda _{jk}^\zeta \circ f) \big ]. \end{aligned}$$

Proof

For any $a \in G$, Lemma 2.2(iii, iv) implies that

$$\begin{aligned} f_{ij}^\zeta (a)= & {} \sum _{s \in G} \lambda _{ij}^\zeta \big ( f(as) f(s)^{-1} \big ) \ = \ \sum _{k = 1}^{n_\zeta } \sum _{s \in G} \lambda _{ik}^\zeta (f(as)) \overline{\lambda _{jk} (f(s))} \\= & {} \sum _{k = 1}^{n_\zeta } \big [ (\lambda _{ik}^\zeta \circ f) \!\circledast \!(\lambda _{jk}^\zeta \circ f) \big ] (a). \end{aligned}$$

So the lemma holds. $\square$

The next theorem characterizes a perfect nonlinear function $f : G \rightarrow H$ in terms of $f_{ij}^\zeta$. Let $\delta _{ij}$ be the Kronecker delta.

Theorem 4.7

Let G, H be finite groups, and $f: G \rightarrow H$ a function. Then the following are equivalent.

(i):

f is a perfect nonlinear function.

(ii):

For any $\zeta \in {{\mathrm{Irr}}}(H)^\sharp$, $f_{ij}^\zeta = \delta _{ij} \rho$, where $\rho$ is the regular character of G.

(iii):

For any $\zeta \in {{\mathrm{Irr}}}(H)^\sharp$,

$$\begin{aligned} \sum _{k=1}^{n_\zeta } M \big ( \lambda _{ik}^\zeta \circ f \big )_\psi \Big [ M \big ( \lambda _{jk}^\zeta \circ f \big )_\psi \Big ]^* = \delta _{ij} \frac{n^2_\psi }{|G |} I_{n_\psi }, \quad \hbox {for any } \psi \in {{\mathrm{Irr}}}(G). \end{aligned}$$

Proof

Let $g: G \rightarrow H$ be a function. Then by (4.1), g is evenly-balanced if and only if $\sum _{s \in G} g(s) = (|G |/|H |) \sum _{h \in H} h$. Hence by Corollary 2.12(ii), g is evenly-balanced if and only if for any $\zeta \in {{\mathrm{Irr}}}(H)^\sharp$, the function $\lambda _{ij}^\zeta \circ g: G \rightarrow \mathbb C$ is balanced. Therefore,

$$\begin{aligned} f \hbox { is perfect nonlinear}\Leftrightarrow & {} \lambda _{ij}^\zeta \circ D_a f \text{ is } \text{ balanced, } \text{ for } \text{ any } a \in G {\setminus } \{ 1_G \}\ \hbox {and} \ \zeta \in {{\mathrm{Irr}}}(H)^\sharp , \\\Leftrightarrow & {} f_{ij}^\zeta (a) = 0, \quad \hbox {for any } a \in G {\setminus } \{ 1_G \}\ \hbox {and} \ \zeta \in {{\mathrm{Irr}}}(H)^\sharp . \end{aligned}$$

But for any $\zeta \in {{\mathrm{Irr}}}(H)^\sharp$,

$$\begin{aligned} f_{ij}^\zeta (1_G) = \sum _{s \in G} \lambda _{ij}^\zeta \big (f(s) f(s)^{-1} \big ) = |G | \lambda _{ij}^\zeta (1_H) = \delta _{ij} |G |. \end{aligned}$$

So f is perfect nonlinear if and only if $f_{ij}^\zeta = \delta _{ij} \rho$, for any $\zeta \in {{\mathrm{Irr}}}(H)^\sharp$, and the equivalence of (i) and (ii) holds.

For any $\zeta \in {{\mathrm{Irr}}}(H)$, $f_{ij}^\zeta = \sum _{k = 1}^{n_\zeta } \big [ (\lambda _{ik}^\zeta \circ f) \!\circledast \!(\lambda _{jk}^\zeta \circ f) \big ]$ by Lemma 4.6. Therefore, for any $\psi \in {{\mathrm{Irr}}}(G)$, Lemma 3.7(i) implies that

$$\begin{aligned} M(f_{ij}^\zeta )_\psi = \frac{|G |}{n_\psi } \sum _{k=1}^{n_\zeta } M \big ( \lambda _{ik}^\zeta \circ f \big )_\psi \Big [ M \big ( \lambda _{jk}^\zeta \circ f \big )_\psi \Big ]^*. \end{aligned}$$

Note that $f_{ij}^\zeta = \delta _{ij} \rho$ if and only if $M(f_{ij}^\zeta )_\psi = \delta _{ij} n_\psi I_{n_\psi }$, for any $\psi \in {{\mathrm{Irr}}}(G)$. So the equivalence of (ii) and (iii) holds. $\square$

Since $f_{ij}^\zeta = \delta _{ij} \rho$ if and only if $\overline{f_{ij}^\zeta } = \delta _{ij} \rho$, as a direct consequence of Theorem 4.7 and (3.2), we have the following corollary. Our approach also provides a conceptual proof of Corollary 4.8.

Corollary 4.8

(Cf. [19, Theorem 4]) Let G, H be finite groups, and $f: G \rightarrow H$ a function. Then f is perfect nonlinear if and only if for any $\psi \in {{\mathrm{Irr}}}(G)$,

$$\begin{aligned} \sum _{k=1}^{n_\zeta } \widehat{\left( \lambda _{ik}^\zeta \circ f\right) }(\Phi _\psi ) \left[ \widehat{\left( \lambda _{jk}^\zeta \circ f\right) }(\Phi _\psi ) \right] ^* = \delta _{ij} |G | I_{n_\psi }, \quad \hbox {for any } \zeta \in {{\mathrm{Irr}}}(H)^\sharp . \end{aligned}$$

5 Constructions of bent functions

Let N, H be finite groups, and let $\mu : H \rightarrow {{\mathrm{Aut}}}(N), h \mapsto \mu _h$ be a group homomorphism, where ${{\mathrm{Aut}}}(N)$ is the automorphism group of N. Let $N \rtimes _\mu H$ be the semidirect product of N and H with respect to $\mu$. That is, as a set, $N \rtimes _\mu H$ is the Cartesian product $N \times H$, and the multiplication of elements in $N \rtimes _\mu H$ is defined by

$$\begin{aligned} (a_1, h_1) * (a_2, h_2) := (a_1 \mu _{h_1}(a_2), h_1 h_2), \quad \hbox {for any } (a_1, h_1), (a_2, h_2) \in N \rtimes _\mu H. \end{aligned}$$

Note that the identity element of $N \rtimes _\mu H$ is $(1_N, 1_H)$. Recall that T is the unit circle in the complex numbers.

Proposition 5.1

With the notation in the above paragraph, let $f: N \rightarrow T$ and $g: H \rightarrow T$ be bent functions. Then the following hold.

(i):

$f \times g: N \rtimes _\mu H \rightarrow T, (a, h) \mapsto f(a)g(h)$ is a bent function.

(ii):

$f \times _\mu g: N \rtimes _\mu H \rightarrow T, (a, h) \mapsto f \big ( \mu _{h^{-1}}(a) \big ) g(h)$ is a bent function.

Proof

(i) Let $(a, h) \in N \rtimes _\mu H {\setminus } \{ (1_N, 1_H) \}$. Then

$$\begin{aligned}&\sum _{ (b, k) \in N \rtimes _\mu H} (f \times g) \big ( (a, h) * (b, k) \big ) \overline{(f \times g) \big ( (b, k) \big )} \\&\quad = \sum _{(b, k) \in N \rtimes _\mu H} f(a \mu _h(b)) g(hk) \overline{f(b)} \overline{g(k)} \\&\quad = \sum _{b \in N} f(a \mu _h(b)) \overline{f(b)} \sum _{k \in H} g(hk) \overline{g(k)}. \end{aligned}$$

If $h \ne 1_H$, then $\sum _{k \in H} g(hk) \overline{g(k)} = 0$ (because g is bent). If $h = 1_H$, then $\mu _h$ is the identity map on N, and $a \ne 1_N$. Thus, $\sum _{b \in N} f(a \mu _h(b)) \overline{f(b)} = \sum _{b \in N} f(a b) \overline{f(b)} = 0$. So (i) holds.

(ii) Let $(a, h) \in N \rtimes _\mu H {\setminus } \{ (1_N, 1_H) \}$. Then

$$\begin{aligned}&{ \sum _{(b, k) \in N \rtimes _\mu H} (f \times _\mu g) \big ( (a, h) * (b, k) \big ) \overline{(f \times _\mu g) \big ( (b, k) \big )} } \\&\quad = \sum _{(b, k) \in N \rtimes _\mu H} f \big ( \mu _{(hk)^{-1}}(a \mu _h(b)) \big ) g(hk) \overline{f \big ( \mu _{k^{-1}}(b) \big )} \overline{g(k)} \\&\quad = \sum _{k \in H} \sum _{b \in N} f \big ( \mu _{k^{-1} h^{-1}}(a) \mu _{k^{-1}}(b) \big ) \overline{f \big ( \mu _{k^{-1}}(b) \big )} g(hk) \overline{g(k)}. \quad (\hbox {because } \mu _{(hk)^{-1}} \mu _h = \mu _{k^{-1}}) \end{aligned}$$

If $a \ne 1_N$, then $\mu _{k^{-1} h^{-1}}(a) \ne 1_N$, and hence f a bent function implies that

$$\begin{aligned}&\quad \sum _{b \in N} f \big ( \mu _{k^{-1} h^{-1}}(a) \mu _{k^{-1}}(b) \big ) \overline{f \big ( \mu _{k^{-1}}(b) \big )} = \sum _{b' \in N} f \big ( \mu _{k^{-1} h^{-1}}(a) b' \big ) \overline{f(b')} = 0, \\&\hbox {for all}~k \in H, \hbox {where } b' = \mu _{k^{-1}}(b). \end{aligned}$$

If $a = 1_N$, then $h \ne 1_H$, and $f \big ( \mu _{k^{-1} h^{-1}}(a) \mu _{k^{-1}}(b) \big ) \overline{f \big ( \mu _{k^{-1}}(b) \big )} = 1$ for all $b \in N$. Hence,

$$\begin{aligned} \sum _{k \in H} \sum _{b \in N} f \big ( \mu _{k^{-1} h^{-1}}(a) \mu _{k^{-1}}(b) \big ) \overline{f \big ( \mu _{k^{-1}}(b) \big )} g(hk) \overline{g(k)} = |N | \sum _{k \in H} g(hk) \overline{g(k)} = 0. \end{aligned}$$

So (ii) holds. $\square$

If the homomorphism $\mu : H \rightarrow {{\mathrm{Aut}}}(N)$ is trivial, i.e. $\mu _h$ is the identity map on N for any $h \in H$, then the semidirect product $N \rtimes _\mu H$ is the direct product of N and H. So Proposition 5.1(i) is also true for direct products of finite groups.

Note that many nonabelian finite groups are (isomorphic to) semidirect products of finite abelian groups. So we can obtain bent functions on many nonabelian finite groups by applying Proposition 5.1. Also the same nonabelian finite group can be the semidirect products of different (non-isomorphic) finite (abelian) groups. So by Proposition 5.1, we can construct different bent functions on the same group.

Similarly for perfect nonlinear functions, we have the following result.

Proposition 5.2

With the notation in the paragraph before Proposition 5.1, let Q be a finite group, and let $f: N \rightarrow Q$ and $g: H \rightarrow Q$ be perfect nonlinear functions. Then the following hold.

(i):

$f \times g: N \rtimes _\mu H \rightarrow Q, (a, h) \mapsto f(a)g(h)$ is a perfect nonlinear function.

(ii):

$f \times _\mu g: N \rtimes _\mu H \rightarrow Q, (a, h) \mapsto f \big ( \mu _{h^{-1}}(a) \big ) g(h)$ is a perfect nonlinear function.

Proof

(i) Let $(a, h) \in N \rtimes _\mu H {\setminus } \{ (1_N, 1_H) \}$. Then

$$\begin{aligned}&{ \sum _{ (b, k) \in N \rtimes _\mu H} (f \times g) \big ( (a, h) * (b, k) \big ) \left[ (f \times g) \big ( (b, k) \big ) \right] ^{-1} } \\&\quad = \sum _{b \in N} \left[ f(a \mu _h(b)) \Big ( \sum _{k \in H} g(hk) g(k)^{-1} \Big ) f(b)^{-1} \right] . \end{aligned}$$

If $h \ne 1_H$, then $\sum _{k \in H} g(hk) g(k)^{-1} = \frac{|H |}{|Q |} \sum _{x \in Q} x$ (because g is perfect nonlinear). Hence,

$$\begin{aligned} f(a \mu _h(b)) \Big ( \sum _{k \in H} g(hk) g(k)^{-1} \Big ) f(b)^{-1} = \frac{|H |}{|Q |} \sum _{x \in Q} x, \quad \hbox {for any } b \in N. \end{aligned}$$

Therefore,

$$\begin{aligned} \sum _{ (b, k) \in N \rtimes _\mu H} (f \times g) \big ( (a, h) * (b, k) \big ) \left[ (f \times g) \big ( (b, k) \big ) \right] ^{-1} = \frac{|N | \cdot |H |}{|Q |} \sum _{x \in Q} x. \end{aligned}$$

(5.1)

If $h = 1_H$, then $\mu _h$ is the identity map on N, and $a \ne 1_N$. Thus, $\sum _{b \in N} f(a \mu _h(b)) f(b)^{-1} = \sum _{b \in N} f(a b) f(b)^{-1} = \frac{|N |}{|Q |} \sum _{x \in Q} x$, and (5.1) is also true. So (i) holds.

The proof of (ii) is similar. $\square$

With the assumption in Proposition 5.2, it follows from [21, Theorem 1] that the set $R_f := \{ (a, f(a)) \, : \, a \in N \} \subset N \times Q$ is a semiregular $(|N |, |Q |, |N |, |N |/|Q |)$ relative difference set in $N \times Q$ relative to $\{1_N \} \times Q$, and $R_g := \{ (h, g(h)) \, : \, h \in H \} \subset H \times Q$ is a semiregular $(|H |, |Q |, |H |, |H |/|Q |)$ relative difference set in $H \times Q$ relative to $\{1_H \} \times Q$. From Proposition 5.2(i),

$$\begin{aligned} R_{f \times g} := \{ \big ((a, h), (f \times g)(a, h) \big ) \, : \, (a, h) \in N \rtimes _\mu H \} \subset (N \rtimes _\mu H) \times Q \end{aligned}$$

is a semiregular $(|N \rtimes _\mu H |, |Q |, |N \rtimes _\mu H |, |N \rtimes _\mu H |/|Q |)$ relative difference set in $(N \rtimes _\mu H) \times Q$ relative to $\{(1_N, 1_H) \} \times Q$. Let $G_1 := N \times Q$, $G_2 := H \times Q$, and $G := (N \rtimes _\mu H) \times Q$. Then we can regard G as $G_1 G_2$, and $R_{f \times g}$ as $R_f R_g$. So Proposition 5.2(i) also follows from [10, Theorem 4].

Let G be a finite group. Let N be a normal subgroup of G, $\{ b_i \, : \, 1 \le i \le m \}$ a complete set of representatives of (left) cosets of N in G, and $\varepsilon : \{ b_i \, : \, 1 \le i \le m \} \rightarrow T$ a function. Furthermore, let $\theta = (\theta _1, \cdots , \theta _m)$ and $\pi = (\pi _1, \cdots , \pi _m)$, where $\theta _i, 1 \le i \le m$, are automorphisms (not necessarily all distinct) of N, and $\pi _i: N \rightarrow T, 1 \le i \le m$, are group homomorphisms (not necessarily all distinct). The existence of $\theta _i$ and $\pi _i$ is clear. For example, $\theta _i$ can be the map

$$\begin{aligned} \theta _i: \ N \rightarrow N, \quad x \mapsto b_i^{-1} x b_i, \end{aligned}$$

and $\pi _i$ can be any linear irreducible character of N.

Proposition 5.3

With the notation in the above paragraph, let $f: N \rightarrow T$ be a bent function on N. Let

$$\begin{aligned} f_{\varepsilon , \pi , \theta }: \ G \rightarrow T, \quad b_i x \mapsto \varepsilon (b_i) \pi _i(x) f(\theta _i(x)), \qquad \hbox {for any } x \in N, 1 \le i \le m. \end{aligned}$$

Then for any $a \in N {\setminus } \{ 1_G \}$, $d_a (f_{\varepsilon , \pi , \theta })$ is balanced on G.

Proof

Let $a \in N {\setminus } \{ 1_G \}$. Then for any $x \in N$, $a b_i x = b_i (b_i^{-1} a b_i x) \in b_i N$ for all $b_i$. Hence,

$$\begin{aligned} \sum _{y \in G} d_a (f_{\varepsilon , \pi , \theta })(y)= & {} \sum _{i=1}^m \sum _{x \in N} f_{\varepsilon , \pi , \theta }(a b_i x) \overline{f_{\varepsilon , \pi , \theta }(b_i x)} \\= & {} \sum _{i=1}^m \sum _{x \in N} \varepsilon (b_i) \pi _i(b_i^{-1} a b_i x) f(\theta _i( b_i^{-1} a b_i x)) \overline{\varepsilon (b_i) \pi _i(x) f(\theta _i(x))} \\= & {} \sum _{i=1}^m \sum _{x \in N} \pi _i(b_i^{-1} a b_i) f(\theta _i( b_i^{-1} a b_i) \theta _i(x)) \overline{f(\theta _i(x))}. \end{aligned}$$

Since f is a bent function on N, $\theta _i \in {{\mathrm{Aut}}}(N)$, and $a \ne 1_G$, we see that $\theta _i(b_i^{-1} a b_i) \in N {\setminus } \{ 1_G \}$, and hence

$$\begin{aligned} \sum _{x \in N} f(\theta _i( b_i^{-1} a b_i) \theta _i(x)) \overline{f(\theta _i(x))} = 0, 1 \le i \le m. \end{aligned}$$

So the proposition holds. $\square$

For perfect nonlinear functions, we have the following result.

Proposition 5.4

With the notation in the paragraph before Proposition 5.3, let H be a finite group, and $f: N \rightarrow H$ a perfect nonlinear function. Let

$$\begin{aligned} f_{\theta }: \ G \rightarrow H, \quad b_i x \mapsto f(\theta _i(x)), \qquad \hbox {for any } x \in N, 1 \le i \le m. \end{aligned}$$

Then for any $a \in N {\setminus } \{ 1_G \}$, $D_a (f_{\theta }): G \rightarrow H$ is evenly-balanced.

Proof

Let $a \in N {\setminus } \{ 1_G \}$. Then for any $x \in N$, $a b_i x = b_i (b_i^{-1} a b_i x) \in b_i N$ for all $b_i$. Hence,

$$\begin{aligned} \sum _{y \in G} D_a (f_{\theta })(y)= & {} \sum _{i=1}^m \sum _{x \in N} f_{\theta }(a b_i x) f_{\theta } (b_i x)^{-1} \\= & {} \sum _{i=1}^m \sum _{x \in N} f(\theta _i(b_i^{-1}a b_i x)) f(\theta _i(x))^{-1} \\= & {} \sum _{i=1}^m \sum _{x \in N} f(\theta _i(b_i^{-1}a b_i) \theta _i(x)) f(\theta _i(x))^{-1}. \end{aligned}$$

Since f is perfect nonlinear on N, $\theta _i \in {{\mathrm{Aut}}}(N)$, and $a \ne 1_G$, we see that $\theta _i(b_i^{-1} a b_i) \in N {\setminus } \{ 1_G \}$, and hence

$$\begin{aligned} \sum _{x \in N} f(\theta _i( b_i^{-1} a b_i) \theta _i(x)) f(\theta _i(x))^{-1} = \frac{|N |}{|H |} \sum _{z \in H} z, 1 \le i \le m. \end{aligned}$$

So the proposition holds. $\square$

Davis and Poinset [7] studied perfect nonlinear functions and difference sets on group actions (called G-perfect nonlinear functions and G-difference sets, respectively). Similar to [7, Theorem 3.3] (also see [9, Corollary 2.11]), we have the next result.

Proposition 5.5

Let G be an arbitrary finite group, and $H := \{ 0, 1 \}$ an additive group of order 2. Let $f: G \rightarrow H$ be a function, and $S_i := f^{-1}(i)$, $i = 0, 1$. Then f is perfect nonlinear if and only if 4 divides $|G |$ and $S_0$ is a $(|G |, |S_0 |, |S_0 | - |G |/4)$ difference set in G.

The above proposition can be obtained as a consequence of [7, Theorem 3.3] (or [9, Corollary 2.11]). Here we include a proof for the convenience of the reader. For a nonempty subset C of G, let $C^+ := \sum _{s \in C} s$ and $C^{(-)} := \sum _{s \in C} s^{-1}$. For any $\sum _{s \in G} \gamma _s s$ in the group algebra $\mathbb CG$, let $\big ( \sum _{s \in G} \gamma _s s \big )^{(-)} := \sum _{s \in G} \gamma _s s^{-1}$.

Proof of Proposition 5.5

By [26, Theorem 1.3], f is perfect nonlinear if and only if $\{S_0, S_1 \}$ is a $(G, H)$-related difference family, i.e. $S_0^+ S_1^{(-)} + S_1^+ S_0^{(-)} = \frac{|G |}{|H |}\big ( G {\setminus } \{ 1_G \}\big )^+$. Since $S_0 \cap S_1 = \emptyset$ and $S_0 \cup S_1 = G$, we see that $S_0^+ S_1^{(-)} = S_0^+ \big ( G^+ - S_0^{(-)} \big ) = |S_0 | G^+ - S_0^+ S_0^{(-)}$, and $S_1^+ S_0^{(-)} = \big ( S_0^+ S_1^{(-)} \big )^{(-)} = S_0^+ S_1^{(-)}$. Thus,

$$\begin{aligned} f \ \hbox {is perfect nonlinear}\Leftrightarrow & {} |S_0 | G^+ - S_0^+ S_0^{(-)} = \frac{|G |}{4} \big (G^+ - 1_G \big ) \\\Leftrightarrow & {} S_0^+ S_0^{(-)} = |S_0 | \cdot 1_G + \left( |S_0 | - \frac{|G |}{4} \right) (G^+ - 1_G). \end{aligned}$$

Hence, the proposition holds. $\square$