1 Introduction

Substitution boxes, known as S-boxes for short, are crucial nonlinear building blocks in modern block ciphers. In accordance with known attacks in the literature, S-boxes used in block ciphers are required to satisfy various cryptographic criteria, including high nonlinearity [6], low differential uniformity [17] and bijectivity. In Eurocrypt’18, Cid, Huang, Peyrin, Sasaki and Song [7] introduced a new tool of S-boxes, so-called the boomerang connectivity table (BCT), which analyzes the dependency between the upper part and lower part of a block cipher in a boomerang attack. This new tool quickly attracted researchers’ interest in studying properties and bounds of BCT of cryptographic functions. Boura and Canteaut in [1] investigated the relation between entries in BCT and the difference distribution table (DDT), and introduced the notion of the boomerang uniformity, which is the maximum value in BCT among all nonzero differences of inputs and outputs. They completely characterized the BCTs of 4-bit S-boxes with differential uniformity 4 classified in [10], and also determined the boomerang uniformities of the inverse function and the Gold function. Later, Li, Qu, Sun and Li in [12] provided an equivalent formula to compute the boomerang uniformity of a cryptographic function. Using the new formula, they characterized the boomerang uniformity by means of the Walsh transform, and computed the boomerang uniformities of some permutations with low differential uniformity. Mesnager, Tang and Xiong considered the boomerang uniformity of quadratic permutations in [16], where they presented a characterization of quadratic permutations with boomerang uniformity 4 and showed that the boomerang uniformity of certain quadratic permutations is preserved under extended affine (EA) equivalence. Recently, Calderini and Villa [3] also investigated the boomerang uniformities of some non-quadratic permutations with differential uniformity 4. Very recently, Tian, Boura and Perrin [20] studied the boomerang uniformity of some popular constructions used for building large S-boxes, e.g. for eight variables from smaller ones.

It is shown that the boomerang uniformity of a cryptographic function is greater than or equal to its differential uniformity, and that the lowest possible boomerang uniformity 2 is achieved by almost perfect nonlinear (APN) functions [1, 7]. Clearly, APN permutations operating on even number of variables are most interesting. The problem of existence of APN permutations of \({{\mathbb {F}}}_{2^{2n}}\) is referred to as the BIG APN problem in the community. Nonetheless, by far no other instance for this problem, except for the Dillon APN permutation of \({\mathbb {F}}_{2^6}\), has been found. Hence it is of great interest to construct permutations of \({\mathbb {F}}_{2^{2n}}\) that have high nonlinearity, differential and boomerang uniformity 4. Up to now, there are only three infinite and inequivalent families of permutations over \({{\mathbb {F}}}_{2^{2n}}\) that have boomerang uniformity 4 for odd integers \(n\ge 1\):

  1. (1)

    \(f(x)=x^{-1}\) over \({{\mathbb {F}}}_{2^{2n}}\) [1];

  2. (2)

    \(f(x)=x^{2^{2i}+1}\) over \({{\mathbb {F}}}_{2^n}\), where \(\gcd (i,n)=1\) [1];

  3. (3)

    \( f(x) = \alpha x^{2^{2s}+1}+\alpha ^{2^{2k}}x^{2^{-{2k}}+2^{2k+2s}}\) over \({{\mathbb {F}}}_{2^{2n}}\), where \(n=3k\), \(3\not \mid {k}\), \(3 \mid {(k+s)}\), \(\gcd (3k,s)=1\), and \(\alpha \) is a primitive element of \({{\mathbb {F}}}_{2^{2n}}\) [16].

In Crypto’16, Perrin, Udovenko and Biryukov [19] investigated the only APN permutation over \({{\mathbb {F}}}_{2^6}\) [2] by means of reverse-engineering and proposed the open butterfly and the closed butterfly structures. A generalized butterfly structure was later proposed in [4]. The butterfly structures represent functions over \({{\mathbb {F}}}_{2^n}^2\) in terms of bivariate form. It is shown that the open butterfly structure produces permutations of \({{\mathbb {F}}}_{2^n}^2\), which are CCZ-equivalent to the functions that are derived from the closed structure and are in simpler forms [19]. Since differential uniformity is an invariant under CCZ-equivalence, one may consider to combine open and closed butterfly structures to construct permutations with low differential uniformity. As a matter of fact, by investigating differential uniformity of functions from the closed butterfly structure, researchers constructed several infinite families of differentially 4-uniform permutations over \({{\mathbb {F}}}_{2^n}^2\) with the open butterfly structure [4, 5, 8, 14].

Motivated by recent works on the butterfly structure, this paper aims to construct infinite families of permutations with boomerang uniformity 4 from generalized butterfly structures. The main result of this paper is given as follows.

Theorem 1

Let \(q=2^n\) with n odd, \(\gcd (i,n)=1\) and \(R_i(x,y)=(x+\alpha y)^{2^i+1}+\beta y^{2^i+1}\) with \(\alpha , \beta \in {\mathbb {F}}_q^*\), where \({\mathbb {F}}_q^* = {\mathbb {F}}_q{\setminus } \{0\}\). Then the function

$$\begin{aligned} V_i(x,y) := (R_i(x,y), R_i(y,x)) \end{aligned}$$

from the closed butterfly structure permutes \({{\mathbb {F}}}_q^2\) and has boomerang uniformity 4 if \((\alpha , \beta )\) is taken from the following set

$$\begin{aligned} \varGamma = \left\{ (\alpha ,\beta )\in {{\mathbb {F}}}_{q}^*\times {{\mathbb {F}}}_{q}^*: ~~ \varphi _2^{2^i}=\varphi _1\varphi _3^{2^i-1} ~\text {and}~\varphi _3\ne 0 \right\} , \end{aligned}$$
(1)

where \(\varphi _1, \varphi _2, \varphi _3\) are given by

$$\begin{aligned} \left\{ \begin{array}{lr} \varphi _1= (\alpha +1)^{2^{i+1}+2}+\alpha ^{2^i+2}+\alpha ^{2^i}+\alpha \beta + \beta ^2 \\ \varphi _2= (\alpha +1)^{2^{i+1}+2}+ \alpha ^{2^{i+1}+1}+\alpha +\alpha ^{2^i}\beta + \beta ^2\\ \varphi _3= (\alpha +1)^{2^{i+1}+2}+ \beta ^2. \end{array} \right. \end{aligned}$$
(2)

For the statement in Theorem 1, we will compute the boomerang uniformity by directly investigating the bivariate form \(V_i(x,y)\), and prove the permutation property of \(V_i(x,y)\) by examining its univariate polynomial representation over \({{\mathbb {F}}}_{q^2}\).

The rest of this paper is organized as follows. Section 2 firstly recalls the definitions of differential uniformity, boomerang uniformity, butterfly structure and introduces some auxiliary results. Sections 3 and 4 are devoted to proving the permutation property and the boomerang uniformity in Theorem 1, respectively. Finally, Sect. 5 draws a conclusion of our work.

2 Preliminaries

In this section, we assume n is an arbitrary positive integer and \(q=2^n\). Let \(\mathrm{Tr}_q(\cdot )\) denote the absolute trace function over \({{\mathbb {F}}}_q\), i.e., \(\mathrm{Tr}_q(x) = x+x^2+\cdots +x^{2^{n-1}}\) for any \(x\in {{\mathbb {F}}}_q\). For any set E, the nonzero elements of E is denoted by \(E\backslash \{0\}\) or \(E^{*}\).

2.1 Differential uniformity and Boomerang uniformity

The concept of differential uniformity was introduced to reveal the subtleties of differential attacks.

Definition 2

[17] Let f(x) be a function from \({{\mathbb {F}}}_q\) to itself and \(a,b\in {{\mathbb {F}}}_q\). The difference distribution table (DDT) of f(x) is given by a \(q \times q\) table D, in which the entry for the (a, b) position is given by

$$\begin{aligned} DDT(a,b)=\#\{x\in {{\mathbb {F}}}_q:~~ f(x+a)+f(x) =b \}. \end{aligned}$$

The differential uniformity of f(x) is given by

$$\begin{aligned} \varDelta _f = \max \limits _{a\in {\mathbb {F}}_q^*, b\in {{\mathbb {F}}}_{q}} DDT(a,b). \end{aligned}$$

It is straightforward for any function from \({\mathbb {F}}_q\) to itself, each entry in its DDT takes an even value and its differential uniformity is no less than 2. A function with the minimum possible differential uniformity 2 is called an almost perfect nonlinear (APN) function.

The concept of boomerang connectivity table of a permutation f from \({{\mathbb {F}}}_{2}^n\) to itself was introduced in [7], which clearly is also suitable for the case \({{\mathbb {F}}}_{2^n}\). Later, Boura and Canteaut introduced the concept of the boomerang uniformity, which is defined by the maximum value in BCT excluding the first row and column.

Definition 3

[1, 7] Let f be an invertible function from \({{\mathbb {F}}}_q\) to itself and \(a,b\in {{\mathbb {F}}}_q\). The boomerang connectivity table (BCT) of f is given by a \(q\times q\) table, in which the entry for the (a, b) position is given by

$$\begin{aligned} BCT(a,b)=\#\left\{ x\in {{\mathbb {F}}}_q: ~ f^{-1}(f(x)+b)+f^{-1}(f(x+a)+b) = a \right\} . \end{aligned}$$
(3)

The boomerang uniformity of f is defined by

$$\begin{aligned} \delta _f = \max \limits _{a,b\in {{\mathbb {F}}}_q^*} BCT(a,b). \end{aligned}$$

It is shown in [1, 7] that \(BCT(a, b) \ge DDT(a, b)\) for any a, b in \({\mathbb {F}}_q\). In [12], Li et al. presented an equivalent formula to compute BCT and the boomerang uniformity without knowing \(f^{-1}(x)\) and f(x) simultaneously as follows.

Proposition 4

[12] Let \(q=2^n\) and \(f(x)\in {{\mathbb {F}}}_q[x]\) be a permutation polynomial over \({{\mathbb {F}}}_q\). Then the BCT of f(x) can be given by a \(q\times q\) table BCT, in which the entry BCT(a, b) for the (a, b) position is given by the number of solutions (x, y) in \({{\mathbb {F}}}_q\times {{\mathbb {F}}}_q\) of the following equation system.

$$\begin{aligned} \left\{ \begin{array}{lr} f(x+a) + f(y+a) = b, \\ f(x) + f(y) = b. \end{array} \right. \end{aligned}$$
(4)

Equivalently, the boomerang uniformity of f(x), given by \(\delta _f\), is the maximum number of solutions in \({{\mathbb {F}}}_q\times {{\mathbb {F}}}_q\) of (4) as \(a,\,b\) run through \({{\mathbb {F}}}_{q}^{*}\).

Let f be a quadratic function from \({{\mathbb {F}}}_q\) to itself with \(f(0)=0\). The associated symmetric bilinear mapping is given by \(S_f(x,y)=f(x+y)+f(x)+f(y)\), where \(x,\, y\in {{\mathbb {F}}}_q.\) For any \(a\in {{\mathbb {F}}}_{q}\), define

$$\begin{aligned} \mathrm {Im}_{f,a} = \{S_f(a,x): x \in {{\mathbb {F}}}_{q} \}. \end{aligned}$$

Very recently, Mesnager et al. [16] presented a characterization about quadratic permutations with boomerang uniformity 4 using the new formula (4).

Lemma 5

[16] Let \(q=2^n\) and f be a quadratic permutation of \({{\mathbb {F}}}_{q}\) with differential uniformity 4. Then the boomerang uniformity of f equals 4 if and only if \(\mathrm {Im}_{f,a}=\mathrm {Im}_{f,b}\) for any \(a,b\in {{\mathbb {F}}}_{q}^{*}\) satisfying \(S_f(a,b)=0\).

2.2 The butterfly structure

In Crypto’16, Perrin, Udovenko and Biryukov [19] analyzed the only known APN permutation over \({{\mathbb {F}}}_{2^6}\) [2] and discovered that the APN permutation over \({{\mathbb {F}}}_{2^6}\) has a simple decomposition relying on \(x^3\) over \({{\mathbb {F}}}_{2^3}\). Based on the power permutation \(x^e\) over \({{\mathbb {F}}}_{2^n}\), they presented the open butterfly structure and the closed butterfly structure, which were later generalized in [4].

Definition 6

[19] Let \(q=2^n\) and \(\alpha \in {{\mathbb {F}}}_{q}\), e be an integer such that \(x^e\) is a permutation over \({{\mathbb {F}}}_{q}\) and \(R_k[e,\alpha ]\) be the keyed permutation

$$\begin{aligned} R_{k}[e,\alpha ](x) = (x+\alpha k)^e+k^e. \end{aligned}$$

The following functions

$$\begin{aligned} H_e^{\alpha }(x,y)= & {} \left( R_{R_y[e,\alpha ](x)}^{-1}(y), R_y[e,\alpha ](x) \right) , \\ V_e^{\alpha }(x,y)= & {} \left( R_y[e,\alpha ](x), R_x[e,\alpha ](y) \right) \end{aligned}$$

are called the open butterfly structure and closed butterfly structure respectively.

Definition 7

[4] Let \(q=2^n\) and R(x, y) be a bivariate polynomial of \({{\mathbb {F}}}_{q}\) such that \(R_y: x\rightarrow R(x,y)\) is a permutation of \({{\mathbb {F}}}_{q}\) for all y in \({{\mathbb {F}}}_{q}\). The closed butterfly \(V_R\) is the function of \({{\mathbb {F}}}_{q}^2\) defined by

$$\begin{aligned} V_R(x,y)=(R(x,y),R(y,x)), \end{aligned}$$

and the open butterfly \(H_R\) is the permutation of \({{\mathbb {F}}}_{q}^2\) defined by

$$\begin{aligned} H_R(x,y)= \left( R_{R_y^{-1}(x)}(y), R_y^{-1}(x) \right) , \end{aligned}$$

where \(R_y(x)=R(x,y)\) and \(R_{y}^{-1}(R_y(x))=x\) for any x, y.

Define a bivariate polynomial

$$\begin{aligned} R_i(x,y)=(x+\alpha y)^{2^i+1}+\beta y^{2^i+1}, \quad \gcd (i,n)=1, \,\alpha ,\beta \in {{\mathbb {F}}}_{q}. \end{aligned}$$

Since n is odd, it is clear that the mapping \(x\mapsto R_i(x,y)\) is a permutation of \({\mathbb {F}}_q\) for any fixed \(y\in {\mathbb {F}}_q\). According to experimental results, the permutation \(H_{R_i}(x,y)\) from \(R_i(x,y)\) and the open butterfly structure seems not to have boomerang uniformity 4 of \({{\mathbb {F}}}_{2^3}^2\). Hence this paper concentrates on the closed butterfly structure.

Lemma 8

[14] Let n be odd, \(q=2^n\), i be an integer with \(\gcd (i,n)=1,\) \( \alpha ,\beta \in {{\mathbb {F}}}_{q}^{*}\) and \(\beta \ne (\alpha +1)^{2^i+1}\). Then the function

$$\begin{aligned} V_i := (R_i(x,y), R_i(y,x)) \text { with } R_i(x,y)=(x+\alpha y)^{2^i+1}+\beta y^{2^i+1} \end{aligned}$$

has differential uniformity at most 4.

Recall that the boomerang uniformity of a function is no less than its differential uniformity. The result about \(V_i(x,y)\) in Lemma 8 motivates our study on the coefficients \(\alpha , \beta \) in \({{\mathbb {F}}}_q^*\) that can further result in permutations \(V_i(x,y)\) with boomerang uniformity 4.

2.3 Useful Lemmas

This subsection summarizes some lemmas that will be used for proving the permutation property of the function in Theorem 1.

Lemma 9

[18, 21, 22] Pick \(d,r > 0\) with \(d\mid (q-1)\), and let \(h(x)\in {{\mathbb {F}}}_q[x]\). Then \(f(x)=x^rh\left( x^{\left. (q-1)/d\right. }\right) \) permutes \({\mathbb {F}}_q\) if and only if both

  1. (1)

    \(\gcd (r,\left. (q-1)/d\right. )=1\) and

  2. (2)

    \(g(x)=x^rh(x)^{\left. (q-1)/d\right. }\) permutes \(\mu _d\), where \(\mu _d :=\{x\in {{\mathbb {F}}}_q : x^d=1\}\).

Let the unit circle of \({{\mathbb {F}}}_{q^2}\) be defined by

$$\begin{aligned} \mu _{q+1}:= \{ x\in {{\mathbb {F}}}_{q^2} : x^{q+1}=1 \}. \end{aligned}$$

The unit circle of \({{\mathbb {F}}}_{q^2}\) has the following relation with the finite field \({{\mathbb {F}}}_{q}\).

Lemma 10

[9] Let \(\gamma \) be any fixed element in \({{\mathbb {F}}}_{q^2}\backslash {{\mathbb {F}}}_{q}\). Then we have

$$\begin{aligned} \mu _{q+1}\backslash \{1\} = \left\{ \frac{x+\gamma }{x+\gamma ^q}: x \in {{\mathbb {F}}}_{q} \right\} . \end{aligned}$$

The following lemma is about the solutions of a linear equation. The proof is easy and we omit it.

Lemma 11

Let \(q=2^n\) and \(\gcd (i,n)=1\). Then for any \(a\in {{\mathbb {F}}}_{q}\), the equation \(x^{2^i}+x=a\) has solutions in \({{\mathbb {F}}}_{q}\) if and only if \(\mathrm{Tr}_q(a)=0\). Moreover, when \(\mathrm{Tr}_q(a)=0\), the equation \(x^{2^i}+x=a\) has exactly two solutions \(x=x_0, x_0+1\) in \({{\mathbb {F}}}_{q}\).

Lemma 12

[15] Let \({\mathbb {R}}\) be a commutative ring with identity. The Dickson polynomial \(D_k(x,a)\) of the first kind of degree k

$$\begin{aligned} D_k(x,a)=\sum _{j=0}^{\lfloor \frac{k}{2} \rfloor }\frac{k}{k-j}\begin{pmatrix} k-j \\ j \end{pmatrix}(-a)^jx^{k-2j} \end{aligned}$$

has the following properties:

  1. (1)

    \(D_k(x_1+x_2,x_1x_2)=x_1^k+x_2^k\), where \(x_1,\,x_2\) are two indeterminates;

  2. (2)

    \(D_{k+2}(x,a)=xD_{k+1}(x,a)-aD_k(x,a)\);

  3. (3)

    \(D_{k\ell }(x,a)=D_{k}\left( D_{\ell }(x,a), a^{\ell } \right) \);

  4. (4)

    if \({\mathbb {R}}={{\mathbb {F}}}_{2^n}\), then \(D_{2^i}(x,a)=x^{2^i}\).

By the above lemma, the Dickson polynomial of degree \(k=2^i-1\) over \({{\mathbb {F}}}_{2^n}\) can be explicitly given.

Lemma 13

For any positive integer i and element \(a\in {{\mathbb {F}}}_{2^n}\),

$$\begin{aligned} D_{2^i-1}(x,a)=\sum _{j=0}^{i-1}a^{2^{j}-1}x^{2^i-2^{j+1}+1}. \end{aligned}$$
(5)

Proof

We prove the statement by induction. It is clear that (5) holds for \(i=1\) since \(D_1(x,a)= x\). Suppose that (5) holds for \(i-1\), namely,

$$\begin{aligned} D_{2^{i-1}-1}(x,a)=\sum _{j=0}^{i-2}a^{2^{j}-1}x^{2^{i-1}-2^{j+1}+1}. \end{aligned}$$
(6)

By Lemma 12 (3) and (4), we have

$$\begin{aligned} D_{2^i-2}(x,a)= & {} D_{{2^{i-1}-1}} \left( D_2(x,a) ,a^2\right) \\= & {} D_{{2^{i-1}-1}} \left( x^2 ,a^2\right) \\= & {} \sum _{j=0}^{i-2}a^{2(2^{j}-1)}x^{2(2^{i-1}-2^{j+1}+1)}\\= & {} \sum _{j=1}^{i-1}a^{2^{j}-2}x^{2^{i}-2^{j+1}+2}. \end{aligned}$$

In addition, according to Lemma 12 (2),

$$\begin{aligned} D_{2^i}(x,a) = xD_{2^i-1}(x,a)+aD_{2^i-2}(x,a). \end{aligned}$$

Thus,

$$\begin{aligned} D_{2^i-1}(x,a)= & {} x^{-1}\left( x^{2^i} + aD_{2^i-2}(x,a) \right) \\= & {} x^{-1}\left( x^{2^i} + a\sum _{j=1}^{i-1}a^{2^{j}-2}x^{2^{i}-2^{j+1}+2} \right) \\= & {} \sum _{j=0}^{i-1}a^{2^{j}-1}x^{2^i-2^{j+1}+1}, \end{aligned}$$

which implies that (5) holds for the i case. Therefore, the desired conclusion follows. \(\square \)

Let \(\gamma \) be a primitive element of \({\mathbb {F}}_{2^2}\), i.e, \(\gamma ^2=\gamma + 1\). Let n be a positive odd integer and \(q=2^n\). The finite field \({{\mathbb {F}}}_{q^2}={{\mathbb {F}}}_q(\gamma )\) and the basis \(1, \gamma \) of \({\mathbb {F}}_{q^2}\) over \({\mathbb {F}}_q\) induces a one-to-one correspondence between \({\mathbb {F}}_q^2\) and \({\mathbb {F}}_{q^2}\) as follows:

$$\begin{aligned} z = x+\gamma y \leftrightarrow (x, y) = (\gamma ^2z+\gamma z^q, z^q+z). \end{aligned}$$

According to the one-to-one correspondence between \({\mathbb {F}}_q^2\) and \({\mathbb {F}}_{q^2}\), the closed butterfly structure \(V_i(x,y) = (R_i(x,y), R_i(y,x))\) over \({\mathbb {F}}_q^2\) can be expressed in a univariate \(z=x+\gamma y\) as

$$\begin{aligned} V_i(z):=R_i(x,y) + \gamma R_i(y,x) \text { with } x=\gamma ^2z+\gamma z^q, \, y=z^q+z. \end{aligned}$$

By substituting z with \(\gamma z\) when i is odd (resp. \(\gamma ^2 z\) when i is even), the above univariate polynomial can be transformed into

$$\begin{aligned} f_i(z)=\epsilon _1z^{q\cdot (2^i+1)}+ \epsilon _2 z^{q\cdot 2^i+1} + \epsilon _3z^{2^i+q} + \epsilon _4 z^{2^i+1}, \end{aligned}$$
(7)

where the coefficients

$$\begin{aligned} (\epsilon _1, \epsilon _2, \epsilon _3, \epsilon _4) = {\left\{ \begin{array}{ll} (\varepsilon _1, \varepsilon _2, \varepsilon _3, \varepsilon _4), &{} \text { for even } i \\ (\varepsilon _3, \varepsilon _4, \varepsilon _1, \varepsilon _2), &{} \text { for odd } i, \\ \end{array}\right. } \end{aligned}$$
(8)

with

$$\begin{aligned} \left\{ \begin{array}{lr} \varepsilon _1 = \alpha ^{2^i}+\alpha +1\\ \varepsilon _2=\alpha ^{2^i+1}+\alpha +\beta +1 \\ \varepsilon _3=\alpha ^{2^i+1}+\alpha ^{2^i}+\beta +1\\ \varepsilon _4=\alpha ^{2^i+1}+\alpha ^{2^i}+\alpha +\beta . \end{array} \right. \end{aligned}$$
(9)

Further, we define

$$\begin{aligned} \left\{ \begin{array}{lr} \varphi _1=\epsilon _1\epsilon _3+\epsilon _2\epsilon _4 \\ \varphi _2=\epsilon _1\epsilon _2+\epsilon _3\epsilon _4 \\ \varphi _3=\epsilon _1^2+\epsilon _2^2+\epsilon _3^2+\epsilon _4^2 \\ \varphi _4=\epsilon _1^2+\epsilon _4^2. \end{array} \right. \end{aligned}$$
(10)

It’s easy to check that \(\varphi _i\)’s, \(i=1,2,3\), match the ones defined in (2).

At the end of this section, we provide a lemma about some properties of the elements \(\varphi _i\)’s which are characterized in Theorem 1.

This result will be heavily used in the proof of the main theorem.

Lemma 14

Let \(q=2^n\) with n odd and \(\gcd (i,n)=1\). Let \(\varphi _1, \varphi _2, \varphi _3, \varphi _4\) be defined by (10) satisfying \(\varphi _{2}^{2^i}=\varphi _{1}\varphi _{3}^{2^i-1}\) and \(\varphi _{3}\ne 0\). For \(\alpha ,\,\beta \ \in {{\mathbb {F}}}_{q}^*\), they have the following properties:

  1. (1)

    \((\varphi _1+\varphi _3)(\varphi _2+\varphi _3)(\varphi _3+\varphi _4)\varphi _4\ne 0\) and \(\left( \frac{\varphi _3}{\varphi _2+\varphi _3}\right) ^{2^i} = \frac{\varphi _3}{\varphi _1+\varphi _3} \) ;

  2. (2)

    when i is even, \(\mathrm{Tr}_q\left( \frac{\varphi _4}{\varphi _3}\right) =1\); moreover, the equation

    $$\begin{aligned} x^{2^i}+x+\frac{\varphi _3+\varphi _4}{\varphi _3}=0 \end{aligned}$$

    has two solutions \(\frac{\varphi _2+\varphi _3}{\varphi _3}\alpha \) and \(\frac{\varphi _2+\varphi _3}{\varphi _3}\alpha +1\) in \({{\mathbb {F}}}_q\);

  3. (3)

    when i is odd, \(\mathrm{Tr}_q\left( \frac{\varphi _4}{\varphi _3}\right) =0\);

  4. (4)

    \(\mathrm{Tr}_q\left( \frac{\varphi _2}{\varphi _3}\right) =0\).

Proof

Since

$$\begin{aligned} \left\{ \begin{array}{lr} \varphi _1= \alpha ^{2^{i+1}+2} + \alpha ^{2^{i+1}}+\alpha ^{2^i+2}+\alpha ^{2^i}+\alpha ^2 +\alpha \beta + \beta ^2+1 \\ \varphi _2= \alpha ^{2^{i+1}+2} + \alpha ^{2^{i+1}+1}+\alpha ^{2^{i+1}}+\alpha ^{2}+\alpha +\alpha ^{2^i}\beta + \beta ^2+1 \\ \varphi _3= \alpha ^{2^{i+1}+2} + \alpha ^{2^{i+1}}+ \alpha ^2 + \beta ^2+1 \end{array} \right. \end{aligned}$$
(11)

and

$$\begin{aligned} \varphi _4 ={\left\{ \begin{array}{ll} \alpha ^{2^{i+1}+2} + \beta ^2+1 &{}\text { for even } i \\ \alpha ^{2^{i+1}} + \alpha ^2 &{} \text { for odd } i, \end{array}\right. } \end{aligned}$$
(12)

it is clear that

$$\begin{aligned} \varphi _1+\varphi _2 = \alpha ^{2^i+2}+\alpha ^{2^i}+\alpha \beta + \alpha ^{2^{i+1}+1}+\alpha ^{2^i}\beta +\alpha =(\alpha ^{2^i}+\alpha )( \alpha ^{2^i+1}+\beta +1) \end{aligned}$$
(13)

and

$$\begin{aligned} \Big \{\varphi _4, \varphi _3+\varphi _4\Big \} = \left\{ (\alpha ^{2^i}+\alpha )^2, ( \alpha ^{2^i+1}+\beta +1 )^2\right\} . \end{aligned}$$
(14)

(1) It follows from (13) and (14) that

$$\begin{aligned} \varphi _4(\varphi _3+\varphi _4) = (\varphi _1+\varphi _2 )^2= (\alpha ^{2^i}+\alpha )^2( \alpha ^{2^i+1}+\beta +1)^2. \end{aligned}$$

By the equality \(\varphi _2^{2^i}=\varphi _1\varphi _3^{2^i-1}\), if either \(\varphi _4(\varphi _3+\varphi _4)=0\) or \((\varphi _1+\varphi _3)(\varphi _2+\varphi _3)=0\), then \(\varphi _1+\varphi _2=0\) and \(\varphi _1=\varphi _2=\varphi _3\). The equation \(\varphi _1+\varphi _2=(\alpha ^{2^i}+\alpha )( \alpha ^{2^i+1}+\beta +1)=0\) implies \(\beta =\alpha ^{2^i+1}+1\) or \(\alpha ^{2^i}+\alpha =0\). In fact, if \(\beta =\alpha ^{2^i+1}+1\), then \(\varphi _1+\varphi _3=\alpha ^{2^i+2}+\alpha ^{2^i}+\alpha \beta =\alpha ^{2^i}+\alpha =0\). Thus we always have \(\alpha ^{2^i}+\alpha =0\), equivalently \(\alpha =0, 1\). This implies \(\varphi _1+\varphi _3=\alpha ^{2^i+2}+\alpha ^{2^i}+\alpha \beta = \alpha \beta = 0\), which is in contradiction with the assumption \(\alpha \beta \ne 0\).

In addition, it is clear that the equality \(\varphi _2^{2^i}=\varphi _1\varphi _3^{2^i-1}\) implies

$$\begin{aligned} \left( \frac{\varphi _3}{\varphi _2+\varphi _3}\right) ^{2^i} = \frac{\varphi _3}{\varphi _1+\varphi _3}. \end{aligned}$$

(2) From (11) and (12), we have

figure a

It is easy to verify that

$$\begin{aligned} \alpha \left( \varphi _2+\varphi _3\right) + \alpha ^{2^i}\left( \varphi _1+\varphi _3 \right) =\varphi _3+\varphi _4. \end{aligned}$$
(16)

Moreover, using \(\left( \frac{\varphi _3}{ \varphi _2+\varphi _3}\right) ^{2^i} = \frac{\varphi _3}{\varphi _1+\varphi _3} \), we have

$$\begin{aligned} \frac{\varphi _3+\varphi _4}{\varphi _3}=\frac{\varphi _2+\varphi _3}{\varphi _3}\alpha + \frac{\varphi _1+\varphi _3}{\varphi _3}\alpha ^{2^i}= \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha + \left( \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha \right) ^{2^i}. \end{aligned}$$
(17)

Thus,

$$\begin{aligned} \mathrm{Tr}_q\left( \frac{\varphi _3+\varphi _4}{\varphi _3}\right) =\mathrm{Tr}_q\left( \frac{\varphi _4}{\varphi _3}\right) +\mathrm{Tr}_q(1)=0. \end{aligned}$$

Furthermore, from Lemma 11, the solutions in \({{\mathbb {F}}}_{q}\) of \(x^{2^i}+x=\frac{\varphi _3+\varphi _4}{\varphi _3}\) are \(\frac{\varphi _2+\varphi _3}{\varphi _3}\alpha \) and \(\frac{\varphi _2+\varphi _3}{\varphi _3}\alpha +1\).

(3) From the expressions of \(\varphi _3, \varphi _4\) in (11), (12), it is clear that the values of \(\varphi _4\) for even i and odd i add up to \(\varphi _3\). The fact that \(\mathrm{Tr}_q(1) = 1\) for odd integer n implies that the values of \(\mathrm{Tr}_q\left( \frac{\varphi _{4}}{\varphi _3}\right) \) for even i and odd i add up to 1. The desired assertion directly follows from (2) of this lemma.

(4) From (13) and (14), it is easily seen that

$$\begin{aligned} \left( \frac{\varphi _1}{\varphi _3}\right) ^2+\left( \frac{\varphi _2}{\varphi _3}\right) ^2=\left( \frac{\varphi _4}{\varphi _3}\right) ^2+\frac{\varphi _4}{\varphi _3}. \end{aligned}$$
(18)

Plugging \(\frac{\varphi _1}{\varphi _3} = \left( \frac{\varphi _2}{\varphi _3}\right) ^{2^i}\) into Eq. (18), we get

$$\begin{aligned} \left( \frac{\varphi _2}{\varphi _3}\right) ^{2^{i+1}} + \left( \frac{\varphi _2}{\varphi _3}\right) ^2=\left( \frac{\varphi _4}{\varphi _3}\right) ^2+\frac{\varphi _4}{\varphi _3}=\left( \frac{\varphi _3+\varphi _4}{\varphi _3}\right) ^2+\frac{\varphi _3+\varphi _4}{\varphi _3}. \end{aligned}$$

By the relation between \(\varphi _3\) and \(\varphi _4\) for even and odd i, it is clear that the expression on the right side of the above equation is independent of the parity of the integer i. W.L.O.G., we can assume that i is even, since the case i odd can be proved by just replacing \(\varphi _4\) by \(\varphi _3+\varphi _4\). Together with (17), we have

$$\begin{aligned} \left( \frac{\varphi _2}{\varphi _3}\right) ^{2^{i+1}} + \left( \frac{\varphi _2}{\varphi _3}\right) ^2=\left( \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha +\left( \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha \right) ^2 \right) ^{2^i} + \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha +\left( \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha \right) ^2 . \end{aligned}$$

Therefore,

$$\begin{aligned} \left( \frac{\varphi _2}{\varphi _3}\right) ^2 = \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha +\left( \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha \right) ^2 \end{aligned}$$

or

$$\begin{aligned} \left( \frac{\varphi _2}{\varphi _3}\right) ^2 = \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha +\left( \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha \right) ^2+1. \end{aligned}$$
(19)

If Eq. (19) holds, then

$$\begin{aligned} \left( 1+\alpha ^2\right) \left( \frac{\varphi _2}{\varphi _3} \right) ^2 + \alpha \left( \frac{\varphi _2}{\varphi _3} \right) + \alpha ^2+\alpha +1=0. \end{aligned}$$
(20)

If \(\alpha =1\), it is easy to obtain that \(\beta =1\) from the definition of \(\varGamma \). Moreover, \(\varphi _2=0\) and thus \(\mathrm{Tr}_q\left( \frac{\varphi _2}{\varphi _3}\right) =0.\) In the following, we assume that \(\alpha \ne 1\). Then after multiplying Eq. (20) by \(\frac{\alpha ^2+1}{\alpha ^2}\) and simplifying, we get

$$\begin{aligned} \left( \frac{\alpha ^2+1}{\alpha } \cdot \frac{\varphi _2}{\varphi _3} \right) ^2+ \frac{\alpha ^2+1}{\alpha } \cdot \frac{\varphi _2}{\varphi _3} = \left( \frac{\alpha ^2+1}{\alpha } \right) ^2+\frac{\alpha ^2+1}{\alpha } \end{aligned}$$

and thus

$$\begin{aligned} \frac{\varphi _2}{\varphi _3}=1 ~~\text {or}~~ \frac{\alpha ^2+\alpha +1}{\alpha ^2+1}. \end{aligned}$$

It is clear that \(\varphi _2+\varphi _3\ne 0\). By \( \left( \frac{\varphi _3}{\varphi _2+\varphi _3}\right) ^{2^i} = \frac{\varphi _3}{\varphi _1+\varphi _3}\), one has

$$\begin{aligned} \left( \frac{\varphi _2+\varphi _3}{\varphi _3}\right) ^{2^i-1}= \frac{\varphi _1+\varphi _3}{\varphi _3} \cdot \frac{\varphi _3}{\varphi _2+\varphi _3} = \frac{\varphi _1+\varphi _3}{\varphi _2+\varphi _3}=\frac{\alpha ^{2^i+2}+\alpha ^{2^i}+\alpha \beta }{\alpha ^{2^{i+1}+1}+\alpha ^{2^i}\beta +\alpha }=\frac{1}{\alpha ^{2^i-1}}. \end{aligned}$$

Since \(\gcd (i,n)=1\), one has \(\frac{\varphi _2+\varphi _3}{\varphi _3}=\frac{1}{\alpha }\) and \(\frac{\varphi _2+\varphi _3}{\varphi _3}=\frac{1}{\alpha }+1\ne \frac{\alpha ^2+\alpha +1}{\alpha ^2+1}\).

Therefore, Eq. (19) does not hold and thus

$$\begin{aligned} \left( \frac{\varphi _2}{\varphi _3}\right) ^2 = \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha +\left( \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha \right) ^2, \end{aligned}$$
(21)

which implies \(\mathrm{Tr}_q\left( \frac{\varphi _2}{\varphi _3}\right) =0.\) \(\square \)

3 The permutation property of \(V_i(x,y)\)

In this section, we firstly give a general necessary and sufficient condition on the permutation property of the function \(V_i\) from the closed butterfly. Throughout what follows, we always assume n is an odd integer.

Recall that the univariate representation of \(V_i\) have the following form

$$\begin{aligned} f(x)=\epsilon _1x^{q\cdot (2^i+1)}+ \epsilon _2 x^{q\cdot 2^i+1} + \epsilon _3x^{2^i+q} + \epsilon _4 x^{2^i+1}, \quad \epsilon _j\in {\mathbb {F}}_q. \end{aligned}$$
(22)

Below we first present a necessary and sufficient conditions for f(x) to be a permutation of \({\mathbb {F}}_{q^2}\) without imposing any additional restrictions on \(\epsilon _j\).

The following proposition investigates the permutation property of f(x) defined by (22) over \({{\mathbb {F}}}_{q^2}\).

Proposition 15

Let \(q=2^n\), f(x) be defined by (22), \(h(x)=\epsilon _1x^{2^i+1}+\epsilon _2x^{2^i}+\epsilon _3x+\epsilon _4\) and \(g(x)=x^{2^i+1}h(x)^{q-1}\). Define \(\mu _{q+1} = \{ x\in {{\mathbb {F}}}_{q^2} : x^{q+1}=1 \}\) and

$$\begin{aligned} T = \left\{ \left( \frac{xy+1}{x+y}, \frac{xy}{x^2+y^2} \right) ~~:~~ x,y\in \mu _{q+1}\backslash \{1\}, y\ne x, x^q \right\} \subset {{\mathbb {F}}}_{q}^2. \end{aligned}$$

Then f(x) permutes \({{\mathbb {F}}}_{q^2}\) if and only if

  1. (1)

    \(\gcd \left( 2^i+1, q-1 \right) =1\);

  2. (2)

    \(h(x)=0\) has no solution in \(\mu _{q+1}\);

  3. (3)

    \(g(x)=1\) if and only if \(x=1\);

  4. (4)

    there does not exist some \((X,Y)\in T\) such that the following equation holds:

    $$\begin{aligned} \varphi _1X^{2^i}+\varphi _2 X + \varphi _3 \left( \sum _{j=0}^{i-1} Y^{2^j} \right) + \varphi _4 =0, \end{aligned}$$
    (23)

    where \(\varphi _j\) for \(j=1,2,3,4\) are defined by (10).

Proof

It is clear that \(f(x)=x^{2^i+1}h\left( x^{q-1} \right) \). According to Lemma 9, f(x) permutes \({{\mathbb {F}}}_{q^2}\) if and only if \(\gcd \left( 2^i+1, q-1 \right) =1\) and

$$\begin{aligned} g(x)=x^{2^i+1}h(x)^{q-1}=\frac{\epsilon _4x^{2^i+1}+\epsilon _3x^{2^i}+\epsilon _2x+\epsilon _1}{\epsilon _1x^{2^i+1}+\epsilon _2x^{2^i}+\epsilon _3x+\epsilon _4} \end{aligned}$$

permutes \(\mu _{q+1}\), which obviously implies that \(h(x)=0\) has no solution in \(\mu _{q+1}\) and \(g(x)=1\) if and only if \(x=1\). In the following, we assume that the conditions (1),(2) and (3) hold. Therefore, g(x) permutes \(\mu _{q+1}\) if and only if \(g(x)+g(y)=0\) has no solution for \(x,y\in \mu _{q+1}\backslash \{1\}\) with \(x\ne y\). In fact, if \(g(x)+g(y)=0\) for some \(y=x^q\), then we have \(g(x)=g(y)=g(x^q)=g(x)^q=g(x)^{-1}\) and thus \(g(x)=1\), which means that \(x=1\). Thus we can only consider the conditions such that \(g(x)+g(y)=0\) has no solution for \(x,y\in \mu _{q+1}\backslash \{1\}\) with \(y\ne x,x^q\). Next, we prove the necessity and sufficiency of the condition (4).

The sufficiency of (4). Suppose \(g(x)+g(y)=0\), i.e.,

$$\begin{aligned} \frac{\epsilon _4x^{2^i+1}+\epsilon _3x^{2^i}+\epsilon _2x+\epsilon _1}{\epsilon _1x^{2^i+1}+\epsilon _2x^{2^i}+\epsilon _3x+\epsilon _4} = \frac{\epsilon _4y^{2^i+1}+\epsilon _3y^{2^i}+\epsilon _2y+\epsilon _1}{\epsilon _1y^{2^i+1}+\epsilon _2y^{2^i}+\epsilon _3y+\epsilon _4}. \end{aligned}$$

After a routine calculation, we obtain

$$\begin{aligned} \varphi _1(x+y)(xy+1)^{2^i} + \varphi _2 (x+y)^{2^i}(xy+1) + \varphi _4(x+y)^{2^i+1}+ \varphi _3 \left( x^{2^i}y+xy^{2^i}\right) =0, \end{aligned}$$

where \(\varphi _j\)’s for \(j=1,2,3,4\) are defined as in (10). By the previous discussion, we now only need to consider the case that \((x+y)(xy+1)\ne 0\). Therefore, the above equation is equivalent to

$$\begin{aligned} \varphi _1\left( \frac{xy+1}{x+y}\right) ^{2^i} + \varphi _2 \left( \frac{xy+1}{x+y}\right) + \varphi _4+ \varphi _3 \left( \frac{x^{2^i}y+xy^{2^i}}{(x+y)^{2^i+1}}\right) =0. \end{aligned}$$
(24)

Note that

$$\begin{aligned} \frac{x^{2^i}y+xy^{2^i}}{(x+y)^{2^i+1}} = \frac{x^{2^i+1}+y^{2^i+1}}{(x+y)^{2^i+1}} + 1 = \left( \frac{x}{x+y}\right) ^{2^i+1} + \left( \frac{y}{x+y}\right) ^{2^i+1} + 1. \end{aligned}$$

It follows from Lemma 12 (1) that the coefficient of \(\varphi _3\) can be expressed in terms of Dickson polynomial as

$$\begin{aligned} \frac{x^{2^i}y+xy^{2^i}}{(x+y)^{2^i+1}} = D_{2^i+1}\left( 1, \frac{xy}{(x+y)^2}\right) + 1. \end{aligned}$$

In addition, by Lemma 12 (2), (4) and Lemma 13,

$$\begin{aligned} \begin{aligned} D_{2^i+1}(x, a) = D_{2^i}(x, a) + aD_{2^i-1}(x, a)&= x^{2^i} + \sum \limits _{j=0}^{i-1}a^{2^j}x^{2^i-2^{j+1}+1}. \end{aligned} \end{aligned}$$
(25)

Denote \(X=\frac{xy+1}{x+y}\) and \(Y=\frac{xy}{(x+y)^2}\). Then the coefficient of \(\varphi _{3}\) can be written as

$$\begin{aligned} D_{2^i+1}\left( 1, Y\right) + 1= 1 + \sum \limits _{j=0}^{i-1}Y^{2^j}+ 1 = \sum \limits _{j=0}^{i-1}Y^{2^j}. \end{aligned}$$

It is straightforward that \(g(x) = g(y)\) can be rewritten as

$$\begin{aligned} \varphi _1X^{2^i}+\varphi _2 X + \varphi _3 \left( \sum _{j=0}^{i-1} Y^{2^j} \right) + \varphi _4 =0. \end{aligned}$$
(26)

Thus, if there exist some \(x,y\in \mu _{q+1}\) with \(y\ne x,x^q\) such that \(g(x)+g(y)=0\) holds, there must exist some \((X,Y)\in T\) such that Eq. (26) holds. Thus if the condition (4) holds, g(x) permutes \(\mu _{q+1}\).

The necessity of (4). On the contrary, if the condition (4) does not hold, which means that there exist some \((X,Y)\in T\) such that Eq. (26) holds, then there must exist some \(x,y\in \mu _{q+1}\backslash \{1\}\) with \(y\ne x,x^q\) such that \(g(x)+g(y)=0\), which implies that g(x) does not permute \(\mu _{q+1}\).

On combining the sufficiency and necessity, we have proved the desired conclusion. \(\square \)

Proof of the permutation part in Theorem  1.

In the following, we will prove the permutation part in Theorem 1 by verifying the conditions in Proposition 15.

First of all, if \(\alpha =1\), it is easy to obtain that \(\beta =1\) from the definition of \(\varGamma \). In this case, the function

$$\begin{aligned} f_i(x) = \left\{ \begin{array}{lr} x^{q\cdot (2^i+1)}, ~\text {when}~ i ~\text {is even} \\ x^{2^i+q}, ~\text {when}~ i ~\text {is odd}, \end{array} \right. \end{aligned}$$

clearly permutes \({{\mathbb {F}}}_{q^2}\). In the following, we assume \(\alpha \ne 1\) and will show the four items of Proposition 15.

(1) Since n is odd and \(\gcd (i,n)=1\), we have \(\gcd (2^i+1,2^n-1)=1\) due to the fact \(\gcd (2^i+1,2^n-1) \mid \gcd (2^{2i}-1,2^n-1) = 2^{\gcd (2i,n)}-1=1\).

(2) Next we show that \(h(x)=0\) has no solution in \(\mu _{q+1}\backslash \{1\}\) (\(h(1)=\sqrt{\varphi _3}\ne 0\) according to the definition). Suppose that there exists some \(x_0\in \mu _{q+1}\backslash \{1\}\) satisfying

$$\begin{aligned} \epsilon _1x_0^{2^i+1}+\epsilon _2x_0^{2^i}+\epsilon _3x_0+\epsilon _4 =0. \end{aligned}$$
(27)

Raising Eq. (27) to the q-th power and re-arranging it according to \(x_0^q=x_0^{-1}\), we obtain

$$\begin{aligned} \epsilon _4x_0^{2^i+1}+\epsilon _3x_0^{2^i}+\epsilon _2x_0+\epsilon _1 =0. \end{aligned}$$
(28)

Summing \(\epsilon _4 \times (27)\) and \(\epsilon _1 \times (28)\) gives

$$\begin{aligned} \varphi _1x_0^{2^i}+\varphi _2x_0+\varphi _4=0. \end{aligned}$$
(29)

Computing \(\varphi _4 \times (29) + \varphi _1 \times (29)^q\times x_0^{2^i} \) yields

$$\begin{aligned} \varphi _1\varphi _2x_0^{2^i-1}+\varphi _2\varphi _4x_0+\varphi _1^2+\varphi _4^2=0. \end{aligned}$$
(30)

Furthermore, by computing \((30)\times x_0 + (29) \times \varphi _2\), we obtain

$$\begin{aligned} \varphi _2\varphi _4 x_0^2+\left( \varphi _1^2+\varphi _2^2+\varphi _4^2 \right) x_0 + \varphi _2\varphi _4=0. \end{aligned}$$
(31)

Note that in the above equation \(\varphi _2\varphi _4\ne 0\). Otherwise, we have \(\varphi _1^2+\varphi _2^2=\varphi _4^2\). Recall that \(\varphi _1^2+\varphi _2^2=\varphi _4(\varphi _3+\varphi _4)\) from (13) and (14). Thus we obtain \(\varphi _3\varphi _4=0\), which is in contradiction with \(\varphi _3\ne 0\) in the definition of \(\varGamma \) and \(\varphi _4\ne 0\) in Lemma 14 (1). Thus Eq. (31) becomes

$$\begin{aligned} x_0^2+\frac{\varphi _1^2+\varphi _2^2+\varphi _4^2}{\varphi _2\varphi _4} x_0 + 1 =0. \end{aligned}$$
(32)

Note that

$$\begin{aligned} \mathrm{Tr}_q\left( \frac{\varphi _2\varphi _4}{\varphi _1^2+\varphi _2^2+\varphi _4^2}\right) =\mathrm{Tr}_q\left( \frac{\varphi _2\varphi _4}{\varphi _4 \varphi _3} \right) =\mathrm{Tr}_q\left( \frac{\varphi _2}{\varphi _3} \right) =0. \end{aligned}$$

This implies that Eq. (32) has a solution \(x_0\in {{\mathbb {F}}}_{q}\), which contradicts \(\mu _{q+1}\backslash \{1\}\). Therefore, \(h(x)=0\) has no solution in \(\mu _{q+1}\).

(3) If there exists some \(x_0\in \mu _{q+1}\backslash \{1\}\) such that \(g(x_0)=1\), then we have

$$\begin{aligned} \left( \epsilon _1+\epsilon _4\right) x_0^{2^i+1}+\left( \epsilon _2+\epsilon _3\right) x_0^{2^i}+\left( \epsilon _2+\epsilon _3\right) x_0+\epsilon _1+\epsilon _4=0. \end{aligned}$$
(33)

According to Lemma 10, we know that for any \(x_0\in \mu _{q+1}\backslash \{1\}\), there exists a unique element \(y_0\in {{\mathbb {F}}}_{q}\) such that \(x_0=\frac{y_0+\gamma }{y_0+\gamma ^2}\), where \(\gamma \in {{\mathbb {F}}}_{2^2}\backslash {{\mathbb {F}}}_2\). By plugging \(x_0=\frac{y_0+\gamma }{y_0+\gamma ^2}\) into Eq. (33) and a routine rearrangement, we obtain

$$\begin{aligned} y_0^{2^i}+y_0+\frac{\varepsilon _1+\varepsilon _4}{\epsilon _1+\epsilon _2+\epsilon _3+\epsilon _4}=0, \end{aligned}$$
(34)

where \(\varepsilon _1, \varepsilon _4\) are defined as in (9) satisfying that \(\varepsilon _1+\varepsilon _4=\epsilon _1+\epsilon _4\) for even i and \(\varepsilon _1+\varepsilon _4=\epsilon _2+\epsilon _3\) for odd i. In other words, \(\varepsilon _1+\varepsilon _4\) corresponds to \(\sqrt{\varphi _4}\) for even i and \(\sqrt{\varphi _3+\varphi _4}\) for odd i. By Lemma 14 (2) and (3), we have

$$\begin{aligned} \mathrm{Tr}_q\left( \frac{\varepsilon _1+\varepsilon _4}{\epsilon _1+\epsilon _2+\epsilon _3+\epsilon _4} \right) = 1. \end{aligned}$$

This implies (34) has no solution in \({\mathbb {F}}_q\). Hence \(g(x)=1\) if and only if \(x=1\).

(4) Recall that \(Y=\frac{xy}{x^2+y^2}\) for some \(x,y\in \mu _{q+1}\backslash \{1\}\) with \(x\ne y\). Note that \(\frac{y}{x+y}\in {{\mathbb {F}}}_{q^2}\backslash {{\mathbb {F}}}_{q}\) is a solution to the equation \(z^2+z+Y=0\). This implies \(\mathrm{Tr}_q\left( Y\right) = 1\). It is clear that Eq. (26) required in Proposition 15 is equivalent to

$$\begin{aligned} \sum _{j=0}^{i-1} Y^{2^j} =\frac{\varphi _1}{\varphi _3}X^{2^i}+\frac{\varphi _2}{\varphi _3}X+\frac{\varphi _4}{\varphi _3} = \left( \frac{\varphi _2}{\varphi _3}X\right) ^{2^i}+\frac{\varphi _2}{\varphi _3}X+\frac{\varphi _4}{\varphi _3}. \end{aligned}$$

By \(\mathrm{Tr}_q(Y)=1\) we have

$$\begin{aligned} \mathrm{Tr}_q\left( \sum _{j=0}^{i-1} Y^{2^j} \right) = \left\{ \begin{array}{lr} 0, ~\text {when}~ i ~\text {is even} \\ 1, ~\text {when}~ i ~\text {is odd}, \end{array} \right. \end{aligned}$$
(35)

on the other hand, the expression on the right hand side satisfies

$$\begin{aligned} \mathrm{Tr}_q\left( \left( \frac{\varphi _2}{\varphi _3}X\right) ^{2^i}+\frac{\varphi _2}{\varphi _3}X+\frac{\varphi _4}{\varphi _3} \right) = \left\{ \begin{array}{lr} 1, ~\text {when}~ i ~\text {is even} \\ 0, ~\text {when}~ i ~\text {is odd}, \end{array} \right. \end{aligned}$$

according to Lemma 14. It is clear that Eq. (26) does not hold for any \(X,Y\in {{\mathbb {F}}}_q\).

Up to now, all the four items in Proposition  15 are confirmed. Hence the function \(V_i(x,y)\) in Theorem 1 permutes \({{\mathbb {F}}}_{q}^2\).

4 The boomerang uniformity of \(V_i(x,y)\)

In this section, we will prove that the function

$$\begin{aligned} V_i := (R_i(x,y), R_i(y,x)) \end{aligned}$$

with \(R_i(x,y)=(x+\alpha y)^{2^i+1}+\beta y^{2^i+1}\) has boomerang uniformity 4 when the pair \((\alpha , \beta )\) is taken from the set \(\varGamma \) as in given in Theorem 1. Here and hereafter, we assume that n is odd, \(q=2^n\) and \((\alpha ,\beta )\in \varGamma \).

First of all, the condition \(\beta \ne (\alpha +1)^{2^i+1}\) in Lemma 8 corresponds to the condition \(\varphi _3\ne 0\) in \(\varGamma \). Hence the differential uniformity of \(V_i\) with \(R_i(x,y)=(x+\alpha y)^{2^i+1}+\beta y^{2^i+1}\) is at most 4 for any \((\alpha ,\beta )\in \varGamma \). Furthermore, Canteaut, Perrin and Tian [5] showed that if \(V_i\) is APN then it operates on 6 bits. Therefore, the differential uniformity of \(V_i\) is equal to 4 in other cases. Since \(V_i\) in Theorem 1 permutes \({{\mathbb {F}}}_{q}^2\) and has differential uniformity 4, we can use Lemma 5 to show the boomerang uniformity of \(V_i\). For any \((a,b)\in {{\mathbb {F}}}_{q}^2\), denote

$$\begin{aligned} S_{V_i,(a,b)}(x,y) = V_i(x+a,y+b)+V_i(x,y)+V_i(a,b) \end{aligned}$$

and

$$\begin{aligned} \mathrm {Im}_{V_i,(a,b)} = \left\{ S_{V_i,(a,b)}(x,y): ~ (x,y)\in {{\mathbb {F}}}_{q}^2 \right\} . \end{aligned}$$

According to Lemma 5, we need to determine \((a_1,b_1), (a_2,b_2)\in {{\mathbb {F}}}_{q}^2\backslash \{(0,0)\}\) satisfying \(S_{V_i,(a_1,b_1)}(a_2,b_2)=(0,0)\), and then to prove that for any such pairs the equation \(\mathrm {Im}_{V_i,(a_1,b_1)}=\mathrm {Im}_{V_i,(a_2,b_2)}\) holds.

4.1 The solutions of \(S_{V_i,(a_1,b_1)}(a_2,b_2)=(0,0)\)

The solution of the equation \(S_{V_i,(a_1,b_1)}(a_2,b_2)=(0,0)\) is studied in the following proposition.

Proposition 16

Let \(V_i\) be defined as in Theorem 1 with \((\alpha ,\beta ) \in \varGamma \) and \(\varphi _j\)’s for \(j=1,2,3,4\) be defined as in (10). Then the elements \((a_1,b_1), (a_2,b_2) \in {{\mathbb {F}}}_{q}^2\backslash \{ (0,0) \}\)such that

$$\begin{aligned} V_i(a_1+a_2, b_1+b_2)+V_i(a_1,b_1)+V_i(a_2,b_2)=(0,0) \end{aligned}$$

satisfy \((a_2,b_2)=X\cdot (a_1,b_1)\), where X is a \(2\times 2\) matrix taken from the following set

$$\begin{aligned} \left\{ \begin{bmatrix} 1 &{} 0 \\ 0 &{} 1 \end{bmatrix}, \begin{bmatrix} \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha +1 &{} \frac{\varphi _2+\varphi _3}{\varphi _3} \\ \frac{\varphi _2+\varphi _3}{\varphi _3} &{} \frac{\varphi _2+\varphi _3}{\varphi _3} \alpha \end{bmatrix}, \begin{bmatrix} \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha &{} \frac{\varphi _2+\varphi _3}{\varphi _3} \\ \frac{\varphi _2+\varphi _3}{\varphi _3} &{} \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha +1 \end{bmatrix} \right\} . \end{aligned}$$
(36)

Proof

Note that the equation

$$\begin{aligned} S_{V_i,(a_1,b_1)}(a_2,b_2)=V_i(a_1+a_2, b_1+b_2)+V_i(a_1,b_1)+V_i(a_2,b_2)=(0,0) \end{aligned}$$

can be rewritten as

figure b

Let \(\varphi _j\)’s for \(j=1,2,3,4\) be defined as in (10). Eliminating the terms \(a_2^{2^i}\) in the above equations by computing \((37.1)\times \left( \left( \alpha ^{2^i+1}+\beta \right) a_1+\alpha ^{2^i}b_1 \right) + (37.2) \times \left( a_1+\alpha b_1 \right) \), we obtain

$$\begin{aligned} \lambda _1 a_2+\lambda _2 b_2^{2^i}+\lambda _3 b_2=0, \end{aligned}$$
(38)

where the coefficients are given by

$$\begin{aligned} \left\{ \begin{array}{lr} \lambda _1 = \left( \varphi _1+\varphi _3 \right) a_1^{2^i}b_1+\left( \varphi _2+\varphi _3 \right) a_1b_1^{2^i} + (\varphi _{3}+\varphi _4)b_1^{2^i+1} \\ \lambda _2 = \left( \varphi _2+\varphi _3 \right) a_1^2 + \varphi _3a_1b_1 + \left( \varphi _2+\varphi _3 \right) b_1^2 \\ \lambda _3 = \left( \varphi _1+\varphi _3\right) a_1^{2^i+1} + \varphi _{4} a_1b_1^{2^i} + \left( \varphi _2+\varphi _3 \right) b_1^{2^i+1}, \end{array} \right. \end{aligned}$$

\(\varphi _1, \varphi _2, \varphi _3\) are defined as in (10) and \(\varphi _{4}\) corresponds to the case that i is even. Hereafter, we assume \(\varphi _4\) is restricted to the case of even i, i.e, \(\varphi _4=(\alpha ^{2^i+1}+\beta + 1)^2\).

When \(b_1=0\), we have \(a_1\ne 0\), \(\lambda _1=0, \lambda _2 = \left( \varphi _2+\varphi _3 \right) a_1^2 \) and \( \lambda _3 = \left( \varphi _1+\varphi _3\right) a_1^{2^i+1}\). Moreover, Eq. (38) becomes \(\lambda _2 b_2^{2^i} = \lambda _3 b_2\). This together with Lemma 14 (1) implies

$$\begin{aligned} b_2=0 \text { or } b_2=\left( \frac{\varphi _1+\varphi _3}{\varphi _2+\varphi _3} \right) ^{\frac{1}{2^i-1}}a_1 = \frac{\varphi _2+\varphi _3}{\varphi _3} a_1. \end{aligned}$$

Note that in the case of \(b_1=0\), Eq. (37.1) becomes

$$\begin{aligned} \left( \frac{a_2}{a_1}\right) ^{2^i}+\frac{a_2}{a_1} = \left( \frac{\alpha b_2}{a_1} \right) ^{2^i} + \frac{\alpha b_2}{a_1}. \end{aligned}$$

Therefore, if \(b_2=0\), then \(a_2=a_1\); if \(b_2=\frac{\varphi _2+\varphi _3}{\varphi _3} a_1\), then \(a_2=\frac{\varphi _2+\varphi _3}{\varphi _3}\alpha a_1\) or \(a_2=\frac{\varphi _2+\varphi _3}{\varphi _3}\alpha a_1+a_1\).

When \(b_1\ne 0\), after eliminating the terms \(b_2^{2^i}\) by computing \((37.1)\times \left( (\alpha ^{2^i+1}+\beta ) a_1^{2^i}+ \alpha b_1^{2^i} \right) + (37.2) \times \left( a_1^{2^i}+\alpha ^{2^i}b_1^{2^i} \right) \), we obtain

$$\begin{aligned} \eta _1 a_2^{2^i} + \eta _2 b_2^{2^i}+\eta _3 b_2=0, \end{aligned}$$
(39)

where

$$\begin{aligned} \left\{ \begin{array}{lr} \eta _1 = \lambda _1 \\ \eta _2 = \left( \varphi _2+\varphi _3 \right) a_1^{2^i+1} + \varphi _4a_1^{2^i}b_1 + \left( \varphi _1+\varphi _3 \right) b_1^{2^i+1}\\ \eta _3 = \left( \varphi _1+\varphi _3 \right) a_1^{2^{i+1}} + \varphi _3 a_1^{2^i}b_1^{2^i} + \left( \varphi _1+\varphi _3 \right) b_1^{2^{i+1}}. \end{array} \right. \end{aligned}$$

Furthermore, computing \((38)^{2^i}+\lambda _1^{2^i-1}\times (39)\), we eliminate the term \(a_2^{2^i}\) and obtain

$$\begin{aligned} \lambda _2^{2^i}b_2^{2^{2i}-1}+\left( \lambda _1^{2^i-1}\eta _2 + \lambda _3^{2^i} \right) b_2^{2^i-1} + \lambda _1^{2^i-1} \eta _3 =0. \end{aligned}$$
(40)

Here we note that \(\lambda _2\ne 0\). Otherwise one has \(\left( \varphi _2+\varphi _3 \right) a_1^2 + \varphi _3a_1b_1 + \left( \varphi _2+\varphi _3 \right) b_1^2=0,\) i.e.,

$$\begin{aligned} \left( \frac{\varphi _2+\varphi _3}{\varphi _3}\cdot \frac{a_1}{b_1}\right) ^2+\frac{\varphi _2+\varphi _3}{\varphi _3}\cdot \frac{a_1}{b_1}+\left( \frac{\varphi _2+\varphi _3}{\varphi _3} \right) ^2=0, \end{aligned}$$

which is in contradiction with the fact \(\mathrm{Tr}_q\left( \frac{\varphi _2}{\varphi _3}\right) =0\) by Lemma 14 (4).

In addition, since the differential uniformity of \(V_i\) is 4, Eq. (40) has three nonzero solutions \(b_2=b_1, {\bar{b}} \) and \({\bar{b}}+b_1\) and we only need to obtain the expression of \({\bar{b}}\). Clearly, \({\tilde{b}}_2=b_1^{2^i-1}\) is a solution of

$$\begin{aligned} \lambda _2^{2^i}{\tilde{b}}_2^{2^i+1}+\left( \lambda _1^{2^i-1}\eta _2 + \lambda _3^{2^i} \right) {\tilde{b}}_2 + \lambda _1^{2^i-1} \eta _3 =0. \end{aligned}$$
(41)

Hence, Eq. (41) can be written as

$$\begin{aligned} \lambda _2^{2^i}\left( {\tilde{b}}_2 + b_1^{2^i-1}\right) \left( {\tilde{b}}_2^{2^i}+ b_1^{2^i-1} {\tilde{b}}_2^{2^i-1} + b_1^{2\cdot \left( 2^i-1\right) } {\tilde{b}}_2^{2^i-2}+ \cdots + b_1^{\left( 2^i-1\right) \cdot \left( 2^i-1\right) } {\tilde{b}}_2 +c \right) =0, \end{aligned}$$

where \(c=\frac{\lambda _1^{2^i-1}\eta _3}{\lambda _2^{2^i}b_1^{2^i-1}}\). Now we consider the equation

$$\begin{aligned} {\tilde{b}}_2^{2^i}+ b_1^{2^i-1} {\tilde{b}}_2^{2^i-1} + b_1^{2\cdot \left( 2^i-1\right) } {\tilde{b}}_2^{2^i-2}+ \cdots + b_1^{\left( 2^i-1\right) \cdot \left( 2^i-1\right) } {\tilde{b}}_2 +c =0. \end{aligned}$$
(42)

Let \({\hat{b}}_2=\frac{1}{{\tilde{b}}_2+b_1^{2^i-1}}\). Then Eq. (42) becomes

$$\begin{aligned} {\hat{b}}_2^{2^i}+\frac{b_1^{2^i-1}}{c}{\hat{b}}_2+\frac{1}{c}=0, \end{aligned}$$

i.e.,

$$\begin{aligned} \left( \frac{c^{\frac{1}{2^i-1}}}{b_1} {\hat{b}}_2 \right) ^{2^i} + \frac{c^{\frac{1}{2^i-1}}}{b_1} {\hat{b}}_2 + \frac{c^{\frac{1}{2^i-1}}}{b_1^{2^i}} =0. \end{aligned}$$
(43)

In addition, we have

$$\begin{aligned} c^{\frac{1}{2^i-1}}= & {} \left( \frac{\lambda _1^{2^i-1}\eta _3}{\lambda _2^{2^i}b_1^{2^i-1}} \right) ^{\frac{1}{2^i-1}} \\= & {} \frac{\lambda _1}{b_1}\left( \frac{ \left( \varphi _1+\varphi _3 \right) \left( a_1^{2^{i+1}} + \frac{\varphi _3}{\varphi _1+\varphi _3} a_1^{2^i}b_1^{2^i} + b_1^{2^{i+1}} \right) }{\left( \varphi _2+\varphi _3 \right) ^{2^i} \left( a_1^{2^{i+1}} + \frac{\varphi _3^{2^i}}{\left( \varphi _2+\varphi _3\right) ^{2^i}} a_1^{2^i}b_1^{2^i} + b_1^{2^{i+1}} \right) } \right) ^{\frac{1}{{2^i}-1}} \\= & {} \frac{\lambda _1}{b_1}\left( \frac{ \varphi _1+\varphi _3}{\left( \varphi _2+\varphi _3\right) ^{2^i}} \right) ^{\frac{1}{{2^i}-1}} \\= & {} \frac{\lambda _1}{b_1\varphi _3}, \end{aligned}$$

where the last two equalities follow from Lemma 14 (1). Moreover,

$$\begin{aligned} \frac{c^{\frac{1}{{2^i}-1}}}{b_1^{2^i}}= & {} \frac{\lambda _1}{\varphi _3b_1^{2^i+1}} \\= & {} \frac{\left( \varphi _1+\varphi _3 \right) a_1^{2^i}+\left( \varphi _2+\varphi _3 \right) a_1b_1^{2^i-1} +\left( \varphi _3+\varphi _4 \right) b_1^{2^i}}{\varphi _3b_1^{2^i}} \\= & {} \left( \frac{\left( \varphi _2+\varphi _3\right) a_1}{\varphi _3b_1} \right) ^{2^i} + \frac{\left( \varphi _2+\varphi _3\right) a_1}{\varphi _3b_1} + \frac{\varphi _3+\varphi _4}{\varphi _3} \\= & {} \left( \frac{\left( \varphi _2+\varphi _3\right) a_1}{\varphi _3b_1} + u \right) ^{2^i} + \frac{\left( \varphi _2+\varphi _3\right) a_1}{\varphi _3b_1} +u, \end{aligned}$$

where \(u=\frac{\varphi _2+\varphi _3}{\varphi _3}\alpha \) due to Lemma 14 (2). Hence, from Eq. (43), we have

$$\begin{aligned} \frac{c^{\frac{1}{{2^i}-1}}}{b_1} {\hat{b}}_2 \in \left\{ \frac{\left( \varphi _2+\varphi _3\right) a_1}{\varphi _3b_1} + u, \frac{\left( \varphi _2+\varphi _3\right) a_1}{\varphi _3b_1} + u+1\right\} , \end{aligned}$$

which means that there are exactly two solutions in \({{\mathbb {F}}}_{q}\) for Eq. (42). W.L.O.G., we only consider the first expression here. Namely, we get

$$\begin{aligned} {\hat{b}}_2 = \frac{b_1}{c^{\frac{1}{{2^i}-1}}}\left( \frac{\left( \varphi _2+\varphi _3\right) a_1}{\varphi _3b_1} + u\right) = \frac{\left( \varphi _2+\varphi _3\right) a_1b_1+\varphi _3ub_1^2}{\lambda _1}. \end{aligned}$$

Thus,

$$\begin{aligned} {\tilde{b}}_2=\frac{1}{{\hat{b}}_2}+b_1^{2^i-1} = \frac{\lambda _1}{\left( \varphi _2+\varphi _3\right) a_1b_1+\varphi _3ub_1^2}+b_1^{2^i-1} \end{aligned}$$

is one solution of Eq. (42). Furthermore, one solution of Eq. (40) is

$$\begin{aligned} b_2= & {} \left( {\tilde{b}}_2\right) ^{\frac{1}{{2^i-1}}} \\= & {} \left( \frac{\left( \varphi _1+\varphi _3 \right) a_1^{2^i}+\varphi _3u^{2^i}b_1^{2^i}}{\left( \varphi _2+\varphi _3 \right) a_1+\varphi _3 u b_1} \right) ^{\frac{1}{{2^i}-1}}\\= & {} \left( \frac{\varphi _1+\varphi _3}{\varphi _2+\varphi _3}\right) ^{\frac{1}{{2^i}-1}}\cdot \left( \frac{a_1^{2^i}+\frac{\varphi _3}{\varphi _1+\varphi _3}u^{2^i}b_1^{2^i}}{a_1+\frac{\varphi _3}{\varphi _2+\varphi _3}ub_1}\right) ^{\frac{1}{{2^i}-1}} \\= & {} \frac{\varphi _2+\varphi _3}{\varphi _3}\left( a_1+\frac{\varphi _3}{\varphi _2+\varphi _3}ub_1\right) ~(\text {by Lemma }14 \text {(1)})\\= & {} \frac{\varphi _2+\varphi _3}{\varphi _3} a_1+ \frac{\varphi _2+\varphi _3}{\varphi _3} \alpha b_1 (\text {recall that } u=\frac{\varphi _2+\varphi _3}{\varphi _3}\alpha ). \end{aligned}$$

It follows directly from Eq. (38) that

$$\begin{aligned} a_2 = \frac{\lambda _2}{\lambda _1} b_2^{2^i}+\frac{\lambda _3}{\lambda _1}b_2 =\left( \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha +1\right) a_1+\frac{\varphi _2+\varphi _3}{\varphi _3}b_1. \end{aligned}$$

\(\square \)

4.2 The proof of \(\mathrm {Im}_{V_i,(a_1,b_1)}=\mathrm {Im}_{V_i,(a_2,b_2)}\)

In this subsection, we prove that for any \((a_1,b_1), (a_2,b_2)\in {{\mathbb {F}}}_{q}^2\backslash \{(0,0)\}\) satisfying \(S_{V_i,(a_1,b_1)}(a_2,b_2)=(0,0)\), \(\mathrm {Im}_{V_i,(a_1,b_1)}=\mathrm {Im}_{V_i,(a_2,b_2)}\).

According to Eq. (37.1), we know that for any \((a_1,b_1)\in {{\mathbb {F}}}_{q}^2\), \(S_{V_i,(a_1,b_1)}(x,y)\) can be represented as

$$\begin{aligned} S_{V_i,(a_1,b_1)}(x,y) = A_1 \begin{bmatrix} x^{2^i} \\ x \end{bmatrix}+B_1\begin{bmatrix} y^{2^i} \\ y \end{bmatrix}, \end{aligned}$$

where

$$\begin{aligned} A_1 = \begin{bmatrix} a_1+\alpha b_1, &{} a_1^{2^i}+\alpha ^{2^i}b_1^{2^i} \\ (\alpha ^{2^i+1}+\beta )a_1+\alpha ^{2^i}b_1, &{} (\alpha ^{2^i+1}+\beta )a_1^{2^i}+\alpha b_1^{2^i} \end{bmatrix} \triangleq \begin{bmatrix} a_{11}, &{} a_{12} \\ a_{13}, &{} a_{14} \end{bmatrix} \end{aligned}$$

and

$$\begin{aligned} B_1 = \begin{bmatrix} \alpha ^{2^i}a_1+(\alpha ^{2^i+1}+\beta )b_1, &{} \alpha a_1^{2^i}+(\alpha ^{2^i+1}+\beta )b_1^{2^i} \\ \alpha a_1+ b_1, &{} \alpha ^{2^i}a_1^{2^i}+b_1^{2^i} \end{bmatrix} \triangleq \begin{bmatrix} b_{11}, &{} b_{12} \\ b_{13}, &{} b_{14} \end{bmatrix}. \end{aligned}$$

For the three relations between \((a_1,b_1), (a_2,b_2)\in {{\mathbb {F}}}_{q}^2\backslash \{ (0,0) \}\) presented in Proposition 16 such that \(S_{V_i,(a_1,b_1)(a_2,b_2)}=(0,0)\), it is clear that if \(a_2=a_1\) and \(b_2=b_1\), we have \(\mathrm {Im}_{V_i,(a_1,b_1)}=\mathrm {Im}_{V_i,(a_2,b_2)}\). In addition, if we have proved that \(\mathrm {Im}_{V_i,(a_1,b_1)}=\mathrm {Im}_{V_i,(a_2,b_2)}\) holds for the second relation in Proposition 16, then so does it for the third relation since the sum of two same subspace equals to the subspace. Therefore, it suffices to show that \(\mathrm {Im}_{V_i,(a_1,b_1)}=\mathrm {Im}_{V_i,(a_2,b_2)}\) holds for the second relation in Proposition 16. Below we will again restrict \(\varphi _4\) to the case of even i.

Let \(u=\frac{\varphi _2+\varphi _3}{\varphi _3}\alpha \). Then \(u^{2^i}=u+\frac{\varphi _3+\varphi _4}{\varphi _3}\). Moreover, \(a_2= (u+1) a_1+ \frac{\varphi _2+\varphi _3}{\varphi _3} b_1\) and \(b_2= \frac{\varphi _2+\varphi _3}{\varphi _3} a_1+ub_1\). Furthermore, we get

$$\begin{aligned} a_2^{2^i} = \left( u^{2^i}+1\right) a_1^{2^i}+\left( \frac{\varphi _2+\varphi _3}{\varphi _3}\right) ^{2^i}b_1^{2^i} = \left( u + \frac{\varphi _4}{\varphi _3} \right) a_1^{2^i} + \frac{\varphi _1+\varphi _3}{\varphi _3} b_1^{2^i} \end{aligned}$$

and

$$\begin{aligned} b_2^{2^i} =\left( \frac{\varphi _2+\varphi _3}{\varphi _3}\right) ^{2^i}a_1^{2^i} + u^{2^i} b_1^{2^i} =\frac{\varphi _1+\varphi _3}{\varphi _3} a_1^{2^i} + \left( u + \frac{\varphi _3+\varphi _4}{\varphi _3} \right) b_1^{2^i}. \end{aligned}$$

Therefore, in \(S_{V_i,(a_2,b_2)}(x,y)\), we have

$$\begin{aligned} A_2 = \begin{bmatrix} a_2+\alpha b_2, &{} a_2^{2^i}+\alpha ^{2^i}b_2^{2^i} \\ (\alpha ^{2^i+1}+\beta )a_2+\alpha ^{2^i}b_2, &{} (\alpha ^{2^i+1}+\beta )a_2^{2^i}+\alpha b_2^{2^i} \end{bmatrix} \triangleq \begin{bmatrix} a_{21}, &{} a_{22} \\ a_{23}, &{} a_{24} \end{bmatrix}, \end{aligned}$$

and

$$\begin{aligned} B_2 = \begin{bmatrix} \alpha ^{2^i}a_2+(\alpha ^{2^i+1}+\beta )b_2, &{} \alpha a_2^{2^i}+(\alpha ^{2^i+1}+\beta )b_2^{2^i} \\ \alpha a_2+ b_2, &{} \alpha ^{2^i}a_2^{2^i}+b_2^{2^i} \end{bmatrix} \triangleq \begin{bmatrix} b_{21}, &{} b_{22} \\ b_{23}, &{} b_{24} \end{bmatrix}, \end{aligned}$$

where the explicit expressions of entries in \(A_2\) and \(B_2\) in terms of \(a_1, b_1\) are given as follows:

$$\begin{aligned} \begin{array}{rcl} a_{21} &{}=&{} a_2+\alpha b_2 \\ &{}=&{} (u+1) a_1+ \frac{\varphi _2+\varphi _3}{\varphi _3} b_1 + \frac{\varphi _2+\varphi _3}{\varphi _3} \alpha a_1+u \alpha b_1 \\ &{}=&{} \left( u+1+\frac{\varphi _2+\varphi _3}{\varphi _3} \alpha \right) a_1 + \left( \frac{\varphi _2+\varphi _3}{\varphi _3} + u \alpha \right) b_1 \\ &{}=&{}a_1 + \left( \alpha ^2+1\right) \frac{\varphi _2+\varphi _3}{\varphi _3} b_1 ~(\text {recall that}~~u=\frac{\varphi _2+\varphi _3}{\varphi _3}\alpha ), \\ \\ a_{22} &{}=&{} a_2^{2^i}+\alpha ^{2^i}b_2^{2^i} \\ &{}=&{} a_1^{2^i} + \left( \alpha ^{2^{i+1}}+1\right) \frac{\varphi _1+\varphi _3}{\varphi _3} b_1^{2^i} ~(\text {due to Lemma }14 \text {(1)}), \\ \\ a_{23} &{} =&{} (\alpha ^{2^i+1}+\beta )a_2+\alpha ^{2^i}b_2 \\ &{}=&{}\left( \left( \alpha ^{2^{i}+1} +\beta \right) (u+1) + \alpha ^{2^i} \frac{\varphi _2+\varphi _3}{\varphi _3} \right) a_1 + \left( \left( \alpha ^{2^{i}+1}+\beta \right) \frac{\varphi _2+\varphi _3}{\varphi _3} + \alpha ^{2^i}u \right) b_1\\ &{}=&{}\left( \frac{\left( \varphi _2+\varphi _3\right) \left( \varphi _1+\varphi _3\right) }{\varphi _3} + \alpha ^{2^i+1}+\beta \right) a_1 + \frac{\varphi _2+\varphi _3}{\varphi _3} \beta b_1, \\ \\ a_{24} &{}=&{} (\alpha ^{2^i+1}+\beta )a_2^{2^i}+\alpha b_2^{2^i} \\ &{}=&{}\left( \left( \alpha ^{2^i+1}+\beta \right) \left( u + \frac{\varphi _4}{\varphi _3}\right) + \alpha \frac{\varphi _1+\varphi _3}{\varphi _3} \right) a_1^{2^i} \\ &{} &{} + \left( \left( \alpha ^{2^i+1}+\beta \right) \frac{\varphi _1+\varphi _3}{\varphi _3} + \alpha \left( u+\frac{\varphi _3+\varphi _4}{\varphi _3}\right) \right) b_1^{2^i} \\ &{}=&{}\left( \frac{\left( \varphi _2+\varphi _3\right) \left( \varphi _1+\varphi _3\right) }{\varphi _3} + \alpha ^{2^i+1}+\beta \right) a_1^{2^i} + \frac{\varphi _1+\varphi _3}{\varphi _3} \beta b_1^{2^i} ~(\text {due to} (15) \text {and} (16)), \\ \\ b_{21} &{}=&{} \alpha ^{2^i}a_2+(\alpha ^{2^i+1}+\beta )b_2 = \left( \alpha ^{2^i}+ \frac{\varphi _2+\varphi _3}{\varphi _3} \beta \right) a_1 + \frac{\left( \varphi _2+\varphi _3\right) \left( \varphi _1+\varphi _3\right) }{\varphi _3} b_1, \\ b_{22} &{}=&{} \alpha a_2^{2^i}+(\alpha ^{2^i+1}+\beta )b_2^{2^i} =\left( \alpha +\frac{\varphi _1+\varphi _3}{\varphi _3}\beta \right) a_1^{2^i} + \frac{\left( \varphi _2+\varphi _3\right) \left( \varphi _1+\varphi _3\right) }{\varphi _3} b_1^{2^i}, \\ b_{23} &{}=&{} \alpha a_2+ b_2 = \left( \frac{\varphi _2+\varphi _3}{\varphi _3}(\alpha ^2+1)+ \alpha \right) a_1, \\ b_{24} &{}=&{} \alpha ^{2^i}a_2^{2^i}+b_2^{2^i} = \left( \frac{\varphi _1+\varphi _3}{\varphi _3}(\alpha ^{2^{i+1}}+1)+ \alpha ^{2^i} \right) a_1^{2^i}. \end{array} \end{aligned}$$

Note that the determinants of \(A_1\) and \(B_1\) are

$$\begin{aligned} \mathrm {Det}(A_1)= & {} a_{11}a_{14}+a_{12}a_{13} \\= & {} \left( \varphi _1+\varphi _3\right) a_1^{2^i}b_1 + \left( \varphi _2+\varphi _3\right) a_1b_1^{2^i}+\left( \varphi _3+\varphi _4\right) b_1^{2^i+1}, \end{aligned}$$

and

$$\begin{aligned} \mathrm {Det}(B_1)= & {} b_{11}b_{14}+b_{12}b_{13} \\= & {} \left( \varphi _3+\varphi _4\right) a_1^{2^i+1} + \left( \varphi _2+\varphi _3\right) a_1^{2^i}b_1 + \left( \varphi _1+\varphi _3\right) a_1b_1^{2^i}. \end{aligned}$$

Now we consider the necessary and sufficient conditions such that \( \mathrm {Det}(A_1)=0\). Clearly, from \( \mathrm {Det}(A_1)=0\), we have \(b_1=0\) or

$$\begin{aligned} \left( \varphi _1+\varphi _3\right) \left( \frac{a_1}{b_1}\right) ^{2^i} + \left( \varphi _2+\varphi _3\right) \frac{a_1}{b_1}+\varphi _3+\varphi _4=0, \end{aligned}$$

namely,

$$\begin{aligned} \left( \frac{\varphi _2+\varphi _3}{\varphi _3}\cdot \frac{a_1}{b_1} \right) ^{2^i}+\frac{\varphi _2+\varphi _3}{\varphi _3}\cdot \frac{a_1}{b_1}=\frac{\varphi _3+\varphi _4}{\varphi _3} \end{aligned}$$

and thus \(a_1=\alpha b_1\) or \( \left( \alpha +\frac{\varphi _3}{\varphi _2+\varphi _3} \right) b_1\) due to Lemma 14. Therefore, \( \mathrm {Det}(A_1)=0 \) if and only if \(b_1=0\) or \(a_1=\alpha b_1\) or \( \left( \alpha +\frac{\varphi _3}{\varphi _2+\varphi _3} \right) b_1\). Similarly, \( \mathrm {Det}(B_1)=0 \) if and only if \(a_1=0\) or \(b_1=\alpha a_1\) or \( \left( \alpha +\frac{\varphi _3}{\varphi _2+\varphi _3} \right) a_1\).

It is easy to verify that \(\mathrm {Det}(A_1)=0 \) and \( \mathrm {Det}(B_1)=0 \) holds at the same time if and only if

  1. (i)

    \( \alpha = 1, a_1= b_1\);

  2. (ii)

    \(\alpha +\frac{\varphi _3}{\varphi _2+\varphi _3} = 1, a_1=b_1\);

  3. (iii)

    \(\alpha \left( \alpha +\frac{\varphi _3}{\varphi _2+\varphi _3} \right) = 1, a_1=\alpha b_1\).

If \(\alpha +\frac{\varphi _3}{\varphi _2+\varphi _3} = 1\), then \( \frac{\varphi _2}{\varphi _3} = \frac{\alpha }{\alpha +1}.\) Recall that (21) holds, namely,

$$\begin{aligned} \left( \frac{\varphi _2}{\varphi _3}\right) ^2 = \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha +\left( \frac{\varphi _2+\varphi _3}{\varphi _3}\alpha \right) ^2. \end{aligned}$$

Plugging \( \frac{\varphi _2}{\varphi _3} = \frac{\alpha }{\alpha +1}\) into the above equation and simplifying, we obtain \(\alpha =1\), implying \(\frac{\varphi _3}{\varphi _2+\varphi _3}=0\), which is impossible. If \(\alpha \left( \alpha +\frac{\varphi _3}{\varphi _2+\varphi _3} \right) = 1,\) then \(\frac{\varphi _2}{\varphi _3}=\frac{\alpha ^2+\alpha +1}{\alpha ^2+1}=\frac{1}{\alpha +1}+\frac{1}{\alpha ^2+1}+1,\) which is also impossible since \(\mathrm{Tr}_q\left( \frac{\varphi _2}{\varphi _3}\right) =0.\) Therefore, \(\mathrm {Det}(A_1)=0 \) and \( \mathrm {Det}(B_1)=0 \) holds at the same time if and only if \( \alpha = 1, a_1= b_1\), under which it is clear that \(\mathrm {Im}_{V_i,(a_1,b_1)}=\mathrm {Im}_{V_i,(a_2,b_2)}\).

Next, we consider the following two cases:

  1. (I)

    \(\mathrm {Det}(B_1)\ne 0\);

  2. (II)

    \(\mathrm {Det}(A_1)\ne 0\).

It is clear that \(\mathrm {Im}_{V_i,(a_1,b_1)}=\mathrm {Im}_{V_i,(a_2,b_2)}\) if there exists some invertible matrix P such that \(PA_1=A_2\) and \(PB_1=B_2\).

As for (i), it suffices to show that

$$\begin{aligned} B_2B_1^{-1}A_1=A_2. \end{aligned}$$
(44)

After computing, we know that (44) is

$$\begin{aligned}&\begin{bmatrix} b_{21}b_{14}a_{11}+b_{21}b_{12}a_{13}+b_{22}b_{13}a_{11}+b_{22}b_{11}a_{13}, &{} b_{21}b_{14}a_{12}+b_{21}b_{12}a_{14}+b_{22}b_{13}a_{12}+b_{22}b_{11}a_{14} \\ b_{23}b_{14}a_{11}+b_{23}b_{12}a_{13}+b_{24}b_{13}a_{11}+b_{24}b_{11}a_{13}, &{} b_{23}b_{14}a_{12}+b_{23}b_{12}a_{14}+b_{24}b_{13}a_{12}+b_{24}b_{11}a_{14} \end{bmatrix} \\&\qquad = \mathrm {Det}(B_1) \begin{bmatrix} a_{21}, &{} a_{22} \\ a_{23}, &{} a_{24} \end{bmatrix}. \end{aligned}$$

By plugging the expression of \(B_1\) into the above equation and simplifying, we get

$$\begin{aligned} \left\{ \begin{array}{lr} b_{14}a_{11}+b_{12}a_{13}=\left( \varphi _1+\varphi _3\right) a_1^{2^i+1}+\varphi _4 a_1b_1^{2^i}+\left( \varphi _2+\varphi _3 \right) b_1^{2^i+1} \\ b_{14}a_{12}+b_{12}a_{14}= \left( \varphi _1+\varphi _3\right) a_1^{2^{i+1}} + \varphi _3 a_1^{2^i}b_1^{2^i} + \left( \varphi _1+\varphi _3\right) b_1^{2^{i+1}} \\ b_{13}a_{11}+b_{11}a_{13}= \left( \varphi _2+\varphi _3\right) a_1^{2} + \varphi _3 a_1b_1 + \left( \varphi _2+\varphi _3\right) b_1^{2} \\ b_{13}a_{12}+b_{11}a_{14}= \left( \varphi _2+\varphi _3\right) a_1^{2^i+1}+\varphi _4 a_1^{2^i}b_1+\left( \varphi _1+\varphi _3 \right) b_1^{2^i+1}. \end{array} \right. \end{aligned}$$

Moreover, we have

  1. 1.
    $$\begin{aligned} \tiny&b_{21}b_{14}a_{11}+b_{21}b_{12}a_{13}+b_{22}b_{13}a_{11}+b_{22}b_{11}a_{13}\\&\quad = \left( \varphi _3+\varphi _4\right) a_1^{2^i+2} + \left( \varphi _4\alpha ^{2^i} + \frac{\varphi _4\left( \varphi _2+\varphi _3\right) }{\varphi _3}\beta +\frac{\left( \varphi _2+\varphi _3\right) ^2\left( \varphi _1+\varphi _3\right) }{\varphi _3} \right) a_1^2b_1^{2^i} \\&\qquad + \left( \left( \varphi _2+\varphi _3\right) \alpha ^{2^i}+\frac{\left( \varphi _2+\varphi _3\right) ^2}{\varphi _3}\beta +\frac{\left( \varphi _3+\varphi _4\right) \left( \varphi _2+\varphi _3\right) \left( \varphi _1+\varphi _3\right) }{\varphi _3} \right) a_1b_1^{2^i+1}\\&\qquad +\left( \varphi _3\alpha + \left( \varphi _1+\varphi _3 \right) \beta + \frac{\left( \varphi _2+\varphi _3\right) \left( \varphi _1+\varphi _3\right) ^2}{\varphi _3} \right) a_1^{2^i+1}b_1\\&\qquad +\left( \left( \varphi _2+\varphi _3\right) \alpha +\frac{\left( \varphi _2+\varphi _3\right) \left( \varphi _1+\varphi _3\right) }{\varphi _3}\beta \right) a_1^{2^i}b_1^2\\&\quad =\left( \varphi _3+\varphi _4\right) a_1^{2^i+2}+\left( \varphi _1+\varphi _3\right) a_1^2b_1^{2^i}+\frac{\left( \alpha ^2+1\right) \left( \varphi _2+\varphi _3\right) \left( \varphi _1+\varphi _3\right) }{\varphi _3} a_1b_1^{2^i+1} \\&\qquad +\frac{(\alpha ^4+\beta ^2+1)\left( \varphi _2+\varphi _3 \right) }{\varphi _3}a_1^{2^i+1}b_1 + \frac{\left( \alpha ^2+1\right) \left( \varphi _2+\varphi _3\right) ^2}{\varphi _3}a_1^{2^i}b_1^2, \end{aligned}$$
  2. 2.
    $$\begin{aligned} \tiny&b_{23}b_{14}a_{11}+b_{23}b_{12}a_{13}+b_{24}b_{13}a_{11}+b_{24}b_{11}a_{13}\\&\quad = \frac{\left( \varphi _1+\varphi _2\right) ^2\beta }{\varphi _3}a_1^{2^i+2}+\frac{\varphi _4\left( \varphi _1+\varphi _3\right) \beta }{\varphi _3}a_1^2b_1^{2^i} +\frac{\left( \varphi _1+\varphi _3\right) \left( \varphi _2+\varphi _3\right) \beta }{\varphi _3}a_1b_1^{2^i+1} \\&\qquad + \left( \varphi _2+\varphi _3\right) \beta a_1^{2^i+1}b_1 + \frac{\left( \varphi _2+\varphi _3\right) ^2\beta }{\varphi _3} a_1^{2^i}b_1^2 \end{aligned}$$
  3. 3.
    $$\begin{aligned} \tiny&b_{23}b_{14}a_{12}+b_{23}b_{12}a_{14}+b_{24}b_{13}a_{12}+b_{24}b_{11}a_{14} \\&\quad = \frac{\left( \varphi _1+\varphi _2\right) ^2\beta }{\varphi _3}a_1^{2^{i+1}+1}+\left( \varphi _1+\varphi _3\right) \beta a_1^{2^i+1}b_1^{2^i} +\frac{\left( \varphi _1+\varphi _3\right) ^2\beta }{\varphi _3}a_1b_1^{2^{i+1}} \\&\qquad + \frac{\varphi _4\left( \varphi _2+\varphi _3\right) \beta }{\varphi _3} a_1^{2^{i+1}}b_1 + \frac{\left( \varphi _1+\varphi _3\right) \left( \varphi _2+\varphi _3\right) \beta }{\varphi _3} a_1^{2^i}b_1^{2^i+1}. \end{aligned}$$
  4. 4.
    $$\begin{aligned} \tiny&b_{21}b_{14}a_{12}+b_{21}b_{12}a_{14}+b_{22}b_{13}a_{12}+b_{22}b_{11}a_{14} \\&\quad = \left( \varphi _3+\varphi _4\right) a_1^{2^{i+1}+1} + \left( \varphi _3\alpha ^{2^i} + \left( \varphi _2+\varphi _3\right) \beta +\frac{\left( \varphi _2+\varphi _3\right) ^2\left( \varphi _1+\varphi _3\right) }{\varphi _3} \right) a_1^{2^i+1}b_1^{2^i}\\&\qquad + \left( (\varphi _1+\varphi _3)\alpha ^{2^i} + \frac{\left( \varphi _2+\varphi _3\right) \left( \varphi _1+\varphi _3\right) }{\varphi _3}\beta \right) a_1b_1^{2^{i+1}} \\&\qquad + \left( \frac{\left( \varphi _2+\varphi _3\right) \left( \varphi _1+\varphi _3\right) ^2}{\varphi _3} + \varphi _4\alpha +\,\frac{\varphi _4(\varphi _1+\varphi _3)}{\varphi _3}\beta \right) a_1^{2^{i+1}}b_1\\&\qquad +\left( \left( \varphi _2+\varphi _3\right) \left( \varphi _1+\varphi _3\right) +\left( \varphi _1+\varphi _3\right) \alpha +\frac{(\varphi _1+\varphi _3)^2}{\varphi _3}\beta \right. \\&\qquad \left. + \frac{\varphi _4\left( \varphi _2+\varphi _3\right) \left( \varphi _1+\varphi _3\right) }{\varphi _3} \right) a_1^{2^i}b_1^{2^{i}+1} \\&\quad = \left( \varphi _3+\varphi _4\right) a_1^{2^{i+1}+1} + \frac{ \left( \alpha ^{2^{i+2}}+\beta ^2+1\right) \left( \varphi _1+\varphi _3\right) }{\varphi _3}a_1^{2^i+1}b_1^{2^i}\\&\qquad +\frac{\left( \alpha ^{2^{i+1}}+1\right) \left( \varphi _1+\varphi _3\right) ^2}{\varphi _3}a_1b_1^{2^{i+1}}\\&\qquad +\left( \varphi _2+\varphi _3\right) a_1^{2^{i+1}}b_1+\frac{\left( \alpha ^{2^{i+1}}+1\right) \left( \varphi _1+\varphi _3\right) \left( \varphi _2+\varphi _3\right) }{\varphi _3}a_1b_1^{2^{i+1}}, \end{aligned}$$

Furthermore, after computing and simplifying, we have

  1. 1.
    $$\begin{aligned}&\mathrm {Det}(B_1) a_{21} \\&\quad = \left( \varphi _3+\varphi _4\right) a_1^{2^i+2}+\left( \varphi _1+\varphi _3\right) a_1^2b_1^{2^i}\\&\qquad +\frac{\left( \alpha ^2+1\right) \left( \varphi _2+\varphi _3\right) \left( \varphi _1+\varphi _3\right) }{\varphi _3} a_1b_1^{2^i+1} \\&\qquad +\frac{(\alpha ^4+\beta ^2+1)\left( \varphi _2+\varphi _3 \right) }{\varphi _3}a_1^{2^i+1}b_1 + \frac{\left( \alpha ^2+1\right) \left( \varphi _2+\varphi _3\right) ^2}{\varphi _3}a_1^{2^i}b_1^2, \end{aligned}$$
  2. 2.
    $$\begin{aligned}&\mathrm {Det}(B_1) a_{22} \\&\quad = \left( \varphi _3+\varphi _4\right) a_1^{2^{i+1}+1} + \frac{ \left( \alpha ^{2^{i+2}}+\beta ^2+1\right) \left( \varphi _1+\varphi _3\right) }{\varphi _3}a_1^{2^i+1}b_1^{2^i}\\&\qquad + \frac{\left( \alpha ^{2^{i+1}}+1\right) \left( \varphi _1+\varphi _3\right) ^2}{\varphi _3}a_1b_1^{2^{i+1}}\\&\qquad +\left( \varphi _2+\varphi _3\right) a_1^{2^{i+1}}b_1+\frac{\left( \alpha ^{2^{i+1}}+1\right) \left( \varphi _1+\varphi _3\right) \left( \varphi _2+\varphi _3\right) }{\varphi _3}a_1b_1^{2^{i+1}}, \end{aligned}$$
  3. 3.
    $$\begin{aligned}&\mathrm {Det}(B_1) a_{23} \\&\quad = \frac{\left( \varphi _1+\varphi _2\right) ^2\beta }{\varphi _3}a_1^{2^i+2}+\frac{\varphi _4\left( \varphi _1+\varphi _3\right) \beta }{\varphi _3}a_1^2b_1^{2^i} +\frac{\left( \varphi _1+\varphi _3\right) \left( \varphi _2+\varphi _3\right) \beta }{\varphi _3}a_1b_1^{2^i+1} \\&\qquad + \left( \varphi _2+\varphi _3\right) \beta a_1^{2^i+1}b_1 + \frac{\left( \varphi _2+\varphi _3\right) ^2\beta }{\varphi _3} a_1^{2^i}b_1^2 \end{aligned}$$
  4. 4.
    $$\begin{aligned}&\mathrm {Det}(B_1) a_{24} \\&\quad = \frac{\left( \varphi _1+\varphi _2\right) ^2\beta }{\varphi _3}a_1^{2^{i+1}+1}+\left( \varphi _1+\varphi _3\right) \beta a_1^{2^i+1}b_1^{2^i} +\frac{\left( \varphi _1+\varphi _3\right) ^2\beta }{\varphi _3}a_1b_1^{2^{i+1}} \\&\qquad + \frac{\varphi _4\left( \varphi _2+\varphi _3\right) \beta }{\varphi _3} a_1^{2^{i+1}}b_1 + \frac{\left( \varphi _1+\varphi _3\right) \left( \varphi _2+\varphi _3\right) \beta }{\varphi _3} a_1^{2^i}b_1^{2^i+1}. \end{aligned}$$

Hence, it follows that

$$\begin{aligned}&\begin{bmatrix} b_{21}b_{14}a_{11}+b_{21}b_{12}a_{13}+b_{22}b_{13}a_{11}+b_{22}b_{11}a_{13}, &{} b_{21}b_{14}a_{12}+b_{21}b_{12}a_{14}+b_{22}b_{13}a_{12}+b_{22}b_{11}a_{14} \\ b_{23}b_{14}a_{11}+b_{23}b_{12}a_{13}+b_{24}b_{13}a_{11}+b_{24}b_{11}a_{13}, &{} b_{23}b_{14}a_{12}+b_{23}b_{12}a_{14}+b_{24}b_{13}a_{12}+b_{24}b_{11}a_{14} \end{bmatrix} \\&\qquad = \mathrm {Det}(B_1) \begin{bmatrix} a_{21}, &{} a_{22} \\ a_{23}, &{} a_{24} \end{bmatrix}. \end{aligned}$$

and Eq. (44) holds.

As for (ii), we need to show that

$$\begin{aligned} A_2A_1^{-1}B_1=B_2, \end{aligned}$$
(45)

whose proof can be obtained through just changing \(a_1\) and \(b_1\) in the proof of (44).

Therefore, for any \((a_1,b_1), (a_2,b_2)\in {{\mathbb {F}}}_{q}^2\backslash \{(0,0)\}\) satisfying \(B_{V_i,(a_1,b_1)}(a_2,b_2)=(0,0)\), \(\mathrm {Im}_{V_i,(a_1,b_1)}=\mathrm {Im}_{V_i,(a_2,b_2)}\) holds and by Lemma 5, we know that the boomerang uniformity of \(V_i\) is 4.

Remark 17

we are aware that Li, Hu, Xiong and Zeng in [13] are independently working on the same problem as in this paper. Their techniques in the proof are different from ours in the early version [11] of this paper.

Remark 18

It’s worth pointing out that from the experimental results by MAGMA for \(q=2^3, 2^5\), the set \(\varGamma \) in Theorem 1 covers all the coefficients \(\alpha , \beta \in {\mathbb {F}}_q^*\) that yield permutations \(V_i(x,y)\) with boomerang uniformity 4. We therefore propose the following conjecture and invite interested readers to attack it.

Conjecture 19

Let \(q=2^n\) with n odd, \(\gcd (i,n)=1\) and \(V_i := (R_i(x,y), R_i(y,x))\) with \(R_i(x,y)=(x+\alpha y)^{2^i+1}+\beta y^{2^i+1}\). If \(V_i\) is a permutation over \({{\mathbb {F}}}_q^2\) with boomerang uniformity 4, then the coefficients \(\alpha , \beta \) are taken from the set \(\varGamma \) defined as in (1).

5 Conclusions

In this paper, we applied the butterfly structure in constructing cryptographically strong permuations. The open butterfly does not seem to generate permutations with boomerang uniformity 4 according to numerical results. Based on an intensive study on the coefficients of \(R_i(x,y)=(x+\alpha y)^{2^i+1}+\beta y^{2^i+1}\), \(\gcd (i,n)=1\), over \({{\mathbb {F}}}_{2^n}\), we provided a sufficient condition on \(\alpha , \beta \) such that \(V_i(x,y)= (R_i(x,y),R_i(y,x))\) is a permutation over \({{\mathbb {F}}}_{2^{2n}}\) with boomerang uniformity 4. The proposed condition seems to be also necessary according to numeric results and a conjecture on the observation was given.