Pascale Charpin
email: pascale.charpin@inria.fr

Jie Peng
email: jpeng@shnu.edu.cn

New links between nonlinearity and differential uniformity

Keywords: Vectorial Boolean function, quadratic function, nonlinearity, differential uniformity, differentially two-valued function

In this paper some new links between the nonlinearity and differential uniformity of some large classes of functions are established. Differentially two-valued functions and quadratic functions are mainly treated. A lower bound for the nonlinearity of monomial δ-uniform permutations is obtained, for any δ, as well as an upper bound for differentially two-valued functions. Concerning quadratic functions, significant relations between nonlinearity and differential uniformity are exhibited. In particular, we show that the quadratic differentially 4-uniform permutations should be differentially two-valued and possess the best known nonlinearity.

Introduction

The first statistical attack proposed for breaking iterated block ciphers, namely the differential cryptanalysis, was proposed by Biham and Shamir in [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF]. The security is quantified by the so-called differential uniformity of the substitution box (S-box), which can be represented by a function, say F , over the finite field of order 2 n denoted F 2 n . The Boolean functions used in block ciphers must have a high distance to the set of all affine functions to resist to the linear cryptanalysis [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF]. This criteria is called the nonlinearity. In this context, the knowledge of nonlinearity and differential uniformity of large families of functions is useful. On the other hand such a study allows to exhibit specific objects or can be replaced in a theoretical research in algebraic coding theory or combinatorics. It seems difficult to establish precise relations between the differential uniformity and the nonlinearity of any function. The aim of this work is to exhibit such property.

In this paper, based on a result on the sum-of-square indicators of the components of any function over F 2 n , we obtain a lower bound for the nonlinearity of monomial permutations and an upper bound for the nonlinearity of any differentially two-valued function, relating to their differential uniformity (Theorems 3 and 4). For quadratic functions, we put forward a new approach to establish links between the nonlinearity and differential uniformity by studying some relations between the subspaces related to these functions (Theorem 5). Some important results are then deduced. In particular, we show that the quadratic differentially 4-uniform permutations should be two-valued and possess the best known nonlinearity (Theorem 7).

The rest of the paper is organized as follows. The next section gives some definitions, notation, properties which will be used in all the paper. In Section 3, we establishes some new links between the nonlinearity and differential uniformity of power functions and differentially two-valued functions. In Section 4 we mainly concentrated on quadratic functions. Some interesting applications of the results for quadratic functions, based on previous results (notably [START_REF] Bracken | On the Walsh spectrum of a new APN function[END_REF][START_REF] Bracken | Fourier spectra of binomial APN functions[END_REF][START_REF] Bracken | Binomial differentially 4-uniform permutations with high nonlinearity[END_REF][START_REF] Bracken | On the fourier spectra of the infinite families of quadratic APN Functions[END_REF]), are given in Section 5. Finally, Section 6 concludes the paper.

Preliminaries

A mapping F : F 2 n → F 2 m is usually called an (n, m)-function or a vectorial Boolean function. There are two special and important cases with respect to m. One is m = 1, in this case we say F is an n-variable Boolean function and usually use small letter f instead, and let B n be the set of all n-variable Boolean functions. The other case is m = n, in which we say that F is a function over F 2 n . In this paper we are mainly concentrated on the latter case, but will use the representation of F by their components functions.

For any function F over F 2 n , all the nonzero linear combinations of its coordinate functions are called the components of F . They are n-variable Boolean functions, which are represented as follows in this paper:

f λ = T r(λF (x)), λ ∈ F * 2 n ,
where T r is the absolute trace function from F 2 n to F 2 . For any a ∈ F * 2 n , the function

D a F : F 2 n → F 2 n , x → F (x+a)+F (x)
is called the derivative of F in direction a. For any a ∈ F * 2 n and b ∈ F 2 n , we are interested by the cardinality of any set

(D a F ) -1 (b): set δ(a, b) = #{x ∈ F 2 n | D a F (x) = b} (1)
where #E denotes the cardinal of the set E. The differential uniformity δ of F is defined as δ = max

a∈F * 2 n , b∈F 2 n δ(a, b). (2)
We also say that F is differentially δ-uniform. It is clear that δ is a positive even integer. When δ = 2, the possible smallest value, F is said to be almost perfect nonlinear (APN for short).

A function F over F 2 n is said differentially two-valued if δ(a, b) takes two values only. These values are known to be {0, 2 s } for some positive integer s. Thus we will often say that F is differentially two-valued {0, 2 s }. A basic study of these functions has to be found in [START_REF] Blondeau | Differential properties of power functions[END_REF]. There are more general results in [START_REF] Charpin | Differential uniformity and the associated codes of cryptographic functions[END_REF] such as the following which we will use later.

Corollary 1 [START_REF] Charpin | Differential uniformity and the associated codes of cryptographic functions[END_REF]Corollary 6] Let F be a differentially two-valued {0, 2 s } function over F 2 n . If s is even then n must be even too. In particular, F cannot be differentially 4-uniform when n is odd.

Remark 1

We proved in [START_REF] Charpin | Differential uniformity and the associated codes of cryptographic functions[END_REF] that some properties of differentially twovalued functions hold for quadratic functions. These results reinforce [3, Conjecture 1], saying that differentially two-valued power functions are the quadratic and the so-called Kasami function. However note that APN functions and the inverse of differentially two-valued permutations are differentially two-valued too. Thus not all differentially two-valued functions are quadratic.

For any f ∈ B n , its Walsh coefficients are defined as

W f (a) = x∈F 2 n (-1) f (x)+ax , a ∈ F 2 n .
The nonlinearity of f is denoted nl(f ) and computed as

nl(f ) = 2 n-1 - L(f ) 2 where L(f ) = max a∈F 2 n |W f (a)|.
The function f is said to be bent when n is even and W f takes two values {±2 n/2 } only. It is said to be plateaued when either it is bent or W f takes three values {0, ±2 (n+s)/2 }, 1 ≤ s ≤ n, where s is an integer such that n + s is even. The value 2 (n+s)/2 is called the amplitude of f . A plateaued vectorial function is a vectorial function whose components are plateaued Boolean functions. It is said plateaued with single amplitude when all its components have the same amplitude.

The sum-of-square indicator of f ∈ B n is defined by

ν(f ) = a∈F 2 n W 2 Daf (0) = 2 -n b∈F 2 n W 4 f (b). (3)
Recall that ν(f

) ≤ 2 n L 2 (f ) with equality if and only if f is plateaued, that is L(f ) = 2 (n+s)/2 and ν(f ) = 2 n L 2 (f ) = 2 2n+s , 1 ≤ s ≤ n. (4)
We now consider any vectorial function F over F 2 n with components f λ . The Walsh transform of the function F is defined as

W F (λ, a) = W f λ (a) = x∈F 2 n (-1) T r(λF (x)+ax) , (λ, a) ∈ F * 2 n × F 2 n . (5)
The Walsh spectrum of F is the multiset consisting of integers W F (λ, a) with their multiplicities. The function F is said almost bent (AB) when W F (λ, a) takes only the three values {0, ±2 (n+1)/2 }, so that n must be odd. The nonlinearity N L(F ) of F is defined as

N L(F ) = 2 n-1 - L(F ) 2 where L(F ) = max (λ,a)∈F * 2 n ×F 2 n |W F (λ, a)|.
For odd integers n, it has been proved that N L(F ) ≤ 2 n-1 -2 n-1 2 [START_REF] Chabaud | Links between differential and linear cryptanalysis[END_REF], where the upper bound is achieved by the AB functions. While for even n, the known maximum nonlinearity is 2 n-1 -2 n 2 , which is conjectured to be an upper bound [START_REF] Dobbertin | One-to-one highly nonlinear power functions on GF (2 n )[END_REF].

In Table 1, we list the infinite families of differentially 4-uniform monomial permutations over F 2 n with the known maximum nonlinearity, which are currently known. It is conjectured that this table is complete [START_REF] Bracken | A highly nonlinearity differentially 4uniform power mapping that permutes fields of even degree[END_REF], up to equivalence and including the compositional inverse of the functions. For multinomial functions satisfying the same properties see [START_REF] Bracken | Binomial differentially 4-uniform permutations with high nonlinearity[END_REF][START_REF] Charpin | Sparse Permutations with Low Differential Uniformity[END_REF][START_REF] Qu | A negative answer to Bracken-Tan-Tan's problem on differentially 4-uniform permutations over F 2 n[END_REF]. Such functions are rare and generally quadratic or derived from APN functions. Note that a monomial functions F , i.e., F (x) = x d , is currently called a power function.

Functions Condition Ref. Gold x 2 i +1 n = 2k, k is odd [22] and gcd(n, i) = 2 Kasami x 2 2i -2 i +1 n = 2k, k is odd [23] and gcd(n, i) = 2 Inverse x -1 (0 -1 := 0) n is even [27] Bracken-Leander x 2 2m +2 m +1 n = 4m and m is odd [8]
Table 1: Known differentially 4-uniform power permutations over F 2 2k with best known nonlinearity

A general relation and some consequences

The following lemma gives some link between the differential uniformity of a function over F 2 n and the sum-of-square indicators of its components.

Lemma 1 Let F be differentially δ-uniform over F 2 n , with components f λ , λ ∈ F * 2 n . Then (2 n -1)2 2n+1 ≤ λ∈F * 2 n ν(f λ ) ≤ (2 n -1)2 2n δ,
where the lower bound is achieved if and only if F is APN, and the upper bound is achieved if and only if F is differentially two-valued.

Proof. The lower bound is obtained by [START_REF] Berger | On almost perfect nonlinear functions[END_REF]Corollary 1] as well as the case where equality holds. The upper bound is computed by using [START_REF] Blondeau | Differential properties of power functions[END_REF]. Recall the following formula due to Nyberg [28, p. 118](see formula [START_REF] Blondeau | Differential properties of power functions[END_REF] which is here rewritten in our context):

λ∈F 2 n W 2 Daf λ (0) = 2 n b∈F 2 n δ 2 (a, b).
Recall that b∈F 2 n δ(a, b) = 2 n . Thus we have

λ∈F * 2 n ν(f λ ) = λ∈F * 2 n a∈F 2 n W 2 Daf λ (0) = a∈F * 2 n λ∈F 2 n W 2 Daf λ (0) = a∈F * 2 n 2 n b∈F 2 n δ 2 (a, b) ≤ a∈F * 2 n 2 n δ b∈F 2 n δ(a, b) = (2 n -1)2 2n δ.
Now suppose that equality holds. Using the inequality above, this is equivalent to

a∈F * 2 n 2 n b∈F 2 n δ(a, b) (δ-δ(a, b)) = 0,
which is possible if and only if δ(a, b) ∈ {0, δ} for all a, b.

Suppose that F is plateaued with single amplitude 2 (n+s)/2 ; then ν(f λ ) = 2 2n+s for any λ (see Section 2). We deduce, from Lemma 1, that 2 2n+s ≤ 2 2n δ providing 2 s ≤ δ with equality when F is two-valued {0, 2 s }. Note that such functions F exist, which are two-valued and plateaued (see some quadratic functions later or [3, Theorem 2]).

Proposition 1 Let F be a function over F 2 n which is plateaued with single amplitude 2 (n+s)/2 for some integer s such that n + s is even. Then, the differential uniformity δ of F 2 n satisfies δ ≥ 2 s with equality if and only if F is differentially two-valued.

Thus we have, since δ is even,

λ∈F * 2 n ν(f λ ) = γ(2 n -1)2 2n+1 ( 6
)
where γ is a rational number such that 1 ≤ γ ≤ δ/2.

The number of bent components of vectorial functions over F 2 n , n even, is an interesting issue. A general approach is proposed by [START_REF] Pott | On the maximum number of bent component of vectorial functions[END_REF]Theorem 3]. For APN functions, this number has been characterized for plateaued such functions [1, Corollary 3]. For differentially 4-uniform functions, the following result gives part of the answer.

Theorem 1 Let n be even and let F be a differentially 4-uniform function over F 2 n such that all its components are plateaued. Let A be the number of bent components of F . Then there exists some rational number

1 < γ ≤ 2 depending on F , such that A ≥ (4-2γ)(2 n -1) 3 ,
providing that if F is not two-valued, i.e., γ = 2, then F has bent components. Consequently, if F is not two-valued, then F is not a permutation. Moreover, for any linear function L over F 2 n , F + L is not a permutation.

In particular, any differentially 4-uniform quadratic permutation is twovalued.

Proof.

Since F is differentially 4-uniform, the number γ defined by (6) satisfies 1 < γ ≤ 2. For any component f λ of F we have

ν(f λ ) = 2 2n if f λ is bent, ≥ 2 2n+2 otherwise,
since n is even and f λ is plateaued (see Section 2). Therefore, there exists some integer B such that

λ∈F * 2 n ν(f λ ) = γ(2 n -1)2 2n+1 = A2 2n +B2 2n+2 with A + B ≥ 2 n -1. We get 2γ(2 n -1) = A + 4B, and then 3A+2γ(2 n -1) = 4A+4B ≥ 4(2 n -1),
which leads to A ≥ (4 -2γ)(2 n -1)/3. In particular, if F is not differentially two-valued, then 1 < γ < 2, and thus A > 0.

It is well known that F is a permutation if and only if all its nonzero components are balanced. If F is not differentially two-valued, then F has a bent component, say f µ , which is not balanced. Hence F cannot be a permutation. Moreover, for any linear function L, the component (F +L) µ = f µ + T r(µL) is also bent, which implies that F + L is not a permutation.

To illustrate our previous result, we exhibit a function with bent components, by the next corollary. For our proof, we need a property of linear functions whose proof can be found in [START_REF] Bracken | Fourier spectra of binomial APN functions[END_REF]Corollary 3.2].

Lemma 2 Let L be a linear function over F 2 n as follows defined:

L(x) = d i=0 l i x 2 si , l i ∈ F 2 n and l d = 0, where gcd(n, s) = 1.
Then the kernel of L has dimension at most d.

Corollary 2 Let F (x) = x 2 2t +1 + βx 2 t +1
be a function over F 2 n where β is any nonzero element of F * 2 n and gcd(n, t) = 1. Then F is differentially 4-uniform and not two-valued. Consequently when n is even, F has bent components; thus F + L cannot be a permutation for any linear function L.

Proof.

Since F is quadratic, it is plateaued (see Section 4 later). We compute the derivatives of F . For any a ∈ F * 2 n :

D a F (x) = x 2 2t a+a 2 2t x+β(x 2 t a+a 2 t x)+F (a) = ax 2 t (x 2 2t -2 t +β)+x(a 2 2t +βa 2 t )+F (a) = x 2 2t a+x 2 t βa+x(a 2 2t +βa 2 t )+F (a) = L a (x)+F (a).
Applying Lemma 2 we see that the kernel of L a has dimension at most 2 implying that F is differentially 4-uniform, since it was proved in [1, Theorem 6]) that any function x → xL(x), where L is any linear function, cannot be APN.

There is a unique a such that a 2 2t + βa 2 t = 0, since 2 2t -2 t and 2 n -1 are coprime. For this a

D a F (x)+F (a) = ax 2 t (x 2 2t -2 t +β).
Thus, in this case D a F is 2-to-1 implying that F is not two-valued. Then the proof is completed by applying Theorem 1.

We now present other results that we obtain by applying Lemma 1. These relate in particular with the power functions and the differentially two-valued functions.

Let F (x) = x d be a power function over F 2 n . When F is a permutation all its components f λ have the same Walsh spectrum; moreover all ν(f λ ) are equal. It is well known that if F is APN, then gcd(d, 2 n -1) = 1 for odd n and gcd(d, 2 n -1) = 3 for even n. Consequently, F APN and n odd imply that ν( Proposition 5]. Then one can deduce an upper bound for power APN functions as

f λ ) = 2 2n+1 , λ ∈ F * 2 n [1,
N L(F ) ≤ 2 n-1 -2 n-1
2 , though it gives not any new information. While for even n, the situation is more complicated, the last result is due to Canteaut and is listed below. Note that some congruences allow to study the nonlinearity of Boolean functions [START_REF] Langevin | On the non-linearity of power Functions, Designs[END_REF] which are components of a power function.

Theorem 2 [15, Theorem 8.14] Let n = 2m and let the power function

F : F 2 n → F 2 n , F (x) = x d . Assume that gcd(d, 2 n -1) > 1. Then N L(F ) ≤ 2 n-1 -2 m . If N L(F ) = 2 n-1 -2 m then gcd(d, 2 n -1) = 3 and W F (λ, 0) equals (-1) m+1 2 m+1 , if λ ∈ {x 3 , x ∈ F * 2 n }, (-1) m 2 m , if λ ∈ {x 3 , x ∈ F * 2 n }.
Applying Lemma 1 to power permutations, we obtain a precise result. Since all ν(f λ ) are equal, we get (with notation of Lemma 1)

(2 n -1)ν(f λ ) ≤ (2 n -1)2 2n δ, for any λ ∈ F * 2 n . If F is differentially two-valued {0, 2 s } then ν(f λ ) = 2 2n+s ≤ 2 n L 2 (f λ ), for any λ ∈ F * 2 n . Further L(f λ ) ≥ 2 (n+s)/2
with equality if and only if f λ is plateaued and this property holds for F . Note the similarity of the next proposition and of Proposition 1.

Proposition 2 Let F (x) = x d with gcd(d, 2 n -1) = 1. Assume that F is differentially δ-uniform.
Then, for any λ, ν(f λ ) ≤ 2 2n δ with equality if and only if F is differentially two-valued {0, 2 s }. In this case, L(F ) ≥ 2 (n+s)/2 with equality if and only if F is a vectorial plateaued function.

Little is known on the lower bound of the nonlinearity of any differentially δ-uniform function, δ being fixed. It seems that the nonlinearity of all known APN functions is rather good. It would be of interest and importance to find the reason. Recently, Carlet proposed a nonzero lower bound for the nonlinearity of APN power functions F in [START_REF] Carlet | Characterizations of the differential uniformity of vectorial functions by the Walsh transform[END_REF]Theorem V.6], where he used the fourth moment of the Walsh transform to show that N L(F ) ≥ 2 n-1 -2 3n- 3 4 for n odd and

N L(F ) ≥ 2 n-1 -2 3n-2 4
for n even. Like the APN functions, the nonlinearity of most known differentially 4-uniform permutations on F 2 n for even n also seems to be not low (see Table 1, [START_REF] Peng | New secondary constructions of differentially 4-uniform permutations over F 2 2k[END_REF][START_REF] Qu | Constructing differentially 4uniform permutations over F 2 2k via the switching method[END_REF] and references therein). By the next theorem, we propose a lower bound which increases with differential uniformity for the nonlinearity of bijective power functions.

Theorem 3 Let F be a power permutation over F 2 n with differential uniformity δ. Then we have

N L(F ) ≥ 2 n-1 -2 3n-4 4 4 √ δ.
Proof. By Lemma 1, according to Proposition 2 it holds for any λ:

L 4 (f λ ) ≤ c∈F 2 n W 4 F (λ, c) = 2 n ν(f λ ) ≤ 2 3n δ.
Consequently,

N L(F ) ≥ 2 n-1 -2 3n-4 4 4 √ δ.
This completes the proof.

Example 1 For δ = 2 we get L(f λ ) ≤ 2 (3n+1)/4 for any λ; thus, we obtain the lower bound given in [START_REF] Carlet | Characterizations of the differential uniformity of vectorial functions by the Walsh transform[END_REF], i.e., N L(F ) ≥ 2 n-1 -2 (3n-3)/4 . Note that in this case n is odd because an APN power function cannot be bijective for n even..

When δ = 4 we get L(f λ ) ≤ 2 (3n+2)/4 and then N L(F ) ≥ 2 n-1 -2 (3n-2)/4 .
Remark 2 Note that many power functions wih a low differential uniformity are in fact permutations. Let F (x) = x d . For instance, it has been proved in [START_REF] Blondeau | Differential properties of power functions[END_REF] that (i) If n or n/2 is odd and F is differentially 4-uniform then F is a permutation;

(ii) If n or n/2 is odd, with gcd(3, n) = 1, and F is differentially 6-uniform then F is a permutation;

(iii) If n or n/2 is odd, gcd(3, n) = 3 and gcd(7, n) = 1, and F is differentially 6-uniform then F is a permutation.

When n is even and n/2 odd, Theorem 1 implies that if F is plateaued and differentially 4-uniform then it is two-valued. For instance, it is the case for Kasami functions F (x) = x 2 2t -2 t +1 with gcd(n, t) = 2, whose Walsh spectrum takes values {0, ±2 (n+2)/2 } (see [START_REF] Blondeau | Differential properties of power functions[END_REF]Theorem 2]).

Thanks to Lemma 1, we can also derive an upper bound for the nonlinearity of any differentially two-valued function.

Theorem 4 Let F be a differentially two-valued {0, 2 s } function over

F 2 n . Then it holds N L(F ) ≤ 2 n-1 -2 n+s 2 -1 .
where s should be odd when n is odd.

Proof. Recall that L 2 (F ) = max λ∈F * 2 n , b∈F 2 n W 2 F (λ, b). First it is clear that L 2 (F ) λ∈F * 2 n , b∈F 2 n W 2 F (λ, b) ≥ λ∈F * 2 n , b∈F 2 n W 4 F (λ, b)
By Parseval's relation one has

λ∈F * 2 n , b∈F 2 n W 2 F (λ, b) = (2 n -1)2 2n .
Moreover, by Lemma 1 and (3), it holds

λ∈F * 2 n , b∈F 2 n W 4 F (λ, b) = 2 n λ∈F * 2 n ν(f λ ) = (2 n -1)2 3n+s ,
since F is differentially two-valued {0, 2 s }. Consequently, we arrive at

L 2 (F ) ≥ (2 n -1)2 3n+s
(2 n -1)2 2n = 2 n+s , and hence

N L(F ) ≤ 2 n-1 -2 n+s 2 -1 .
According to Corollary 1, if n is odd then s is odd too.

Quadratic functions

We will now deal with quadratic functions and we begin by fixing notation and definitions. We assume that F over F 2 n is of the form

F (x) = i,j a i,j x 2 i +2 j , 0 ≤ i < j ≤ n-1, (7)
so that F (0) = 0. Then f λ (x) = T r(λF (x)) is a quadratic form for any λ ∈ F 2 n , and the function (x, a) → T r(λQ(x, a)), where Q(x, a) = F (x+a)+F (x)+F (a). ( 8)

is an alternative bilinear form.The corresponding radical of this quadratic form is

rad λ (F ) := {a ∈ F 2 n | T r(λQ(x, a)) = 0, ∀ x ∈ F 2 n }. (9)
Note that rad λ (F ) is actually the linear space of f λ , i.e., the set of a such that the derivative of f λ in point a is constant. Such a is called a linear structure of f λ . We will denote by (λ) the dimension of rad λ (F ). It is well known and easily checked that for any λ ∈ F * 2 n and for any b

∈ F 2 n W 2 F (λ, b) = a∈F 2 n
(-1) T r(ba+λF (a))

x∈F 2 n
(-1) T r(λQ(x,a)) ,

while it holds

x∈F 2 n
(-1) T r(λQ(x,a)) = 2 n , if a ∈ rad λ (F ), 0, otherwise Therefore, we arrive at

W 2 F (λ, b) = 2 n a∈rad λ (F ) (-1) T r(ba+λF (a)) = 2 n+ (λ) , if T r(ba+λF (a)) vanishes on rad λ (F ), 0, otherwise, (11)
since by definition the function a → T r(ba + λF (a)) is linear on rad λ (F ). Therefore, all quadratic functions are plateaued and their derivatives are either balanced or constant. Moreover, as W F (λ, b) is an integer, it follows from [START_REF] Bracken | On the fourier spectra of the infinite families of quadratic APN Functions[END_REF] that

n ≡ (λ) (mod 2), for any λ ∈ F * 2 n . (12)
Note also that for any λ ∈ F * 2 n the Walsh transform b → W F (λ, b) of f λ takes the values {0, ±2 (n+ (λ))/2 } if f λ is non-bent and the values {±2 n/2 } if f λ is bent. Therefore, the best nonlinearity of quadratic functions over

F 2 n is 2 n-1 -2 n-1 2
for odd n and 2 n-1 -2 n 2 for n, which is also called the quadratic bound. Now we define

ker a (F ) := {λ ∈ F 2 n | T r(λQ(x, a)) = 0, ∀ x ∈ F 2 n } (13)
and denote by d(a) the dimension of the vector space ker a (F ) for convenience.

The subspace ker a (F ) is related with the image set of D a F , which is an affine subspace since D a F is an affine function. Further, the image set of x → Q(x, a) is a subspace, since Q(0, a) = 0. Our main results are based on the following observation.

Lemma 3 Let F be quadratic and differentially δ-uniform. For any a ∈ F * 2 n , the function D a F is 2 d(a) -to-1, where d(a) is the dimension of the vector space ker a (F ) defined by [START_REF] Budaghyan | Constructing new APN functions from known ones[END_REF]. Hence δ = max a∈F * 2 n 2 d(a) . Proof. The hyperplanes in F 2 n can, as usual, be defined as follows:

H λ = {y ∈ F 2 n | T r(λy) = 0}, λ ∈ F * 2 n . (14)
Thus, ker a (F ) is the set of those λ such that H λ contains the image set of x → Q(x, a) . This implies that this image set is a subspace of dimension n -d(a) so that D a F is 2 d(a) -to-1. Therefore δ(a, b) ∈ {0, 2 d(a) } for any b, completing the proof.

In this paper we put forward a different approach for the study of those (λ) by studying some relations between the subspaces related to the function F . Our method applies to quadratic functions with any differential uniformity.

A relation between nonlinearity and differential uniformity

It appears that the quadratic functions can be classified by their differential uniformity as well as by their nonlinearity. The link between these two concepts is really not clear, as proves the next example due to Dillon and indicated in [START_REF] Bracken | Fourier spectra of binomial APN functions[END_REF]. It is an example of APN quadratic function whose nonlinearity is not the quadratic bound for n = 6. More such examples for n = 8 can be found in the list of [START_REF] Yu | A Matrix Approach for Constructing Quadratic APN Functions[END_REF].

Example 2 Let n = 6 and let α be a primitive element of F 6 . The following function is APN and its Walsh spectrum has five values:

F (x) = x 3 +α 11 x 5 +α 13 x 9 +x 17 +α 11 x 33 +x 48 .

By using the MAGMA package, we obtain that F has 46 bent components ( (λ) = 0), 16 components such that (λ) = 2 and one λ ∈

F * 2 n such that (λ) = 4. Therefore, N L(F ) = 2 n-1 -2 n+2 2 = 16.
Note that the number of bent components is greater than the lower bound which is 42 as we recall later in Remark 3.

Theorem 5 Let F be a quadratic function over F 2 n . Notation is as above, defined by ( 9) to ( 13). Then we have

λ∈F * 2 n 2 (λ) = a∈F * 2 n 2 d(a) . ( 15
)
Proof. It is simpy obtained by computing:

λ∈F * 2 n 2 (λ) = λ∈F * 2 n |{a ∈ F 2 n | T r(λQ(x, a)) = 0, ∀ x ∈ F 2 n }| = 2 n -1+ a∈F * 2 n |{λ ∈ F * 2 n | T r(λQ(x, a)) = 0, ∀ x ∈ F 2 n }| = a∈F * 2 n |{λ ∈ F 2 n | T r(λQ(x, a)) = 0, ∀ x ∈ F 2 n }| = a∈F * 2 n 2 d(a) .
This completes the proof.

Theorem 5 establishes a link between the values (λ) and the values d(a), where the former ones are related to the nonlinearity of F and the latter ones are related to the differential uniformity of F .

Corollary 3 Let F be a quadratic function over F 2 n , such that δ = 2 s and L(F ) = 2 (n+t)/2 . For any integers i and j such that 1 ≤ i ≤ s and j ∈ J where J = {j | 0 ≤ j ≤ t, n + j even}, we set

N i = #{a ∈ F * 2 n | D a F is 2 i -to-1} and n j = #{λ ∈ F * 2 n | (λ) = j}
Then it holds j∈J

2 j n j = s i=1 2 i N i , ( 16
)
where i N i = j n j = 2 n -1. In particular, if F is differentially two-valued {0, 2 s }, then we have λ∈F * 2 n 2 (λ) = 2 s (2 n -1) where t ≥ s, t = max λ { (λ)}. ( 17
)
If F has single amplitude 2 (n+t)/2 then

a∈F * 2 n 2 d(a) = 2 t (2 n -1) where 1 ≤ d(a), s ≥ t, s = max a {d(a)}. (18)
Proof. By Lemma 3, any function D a F is 2 i -to-1 if and only if d(a) = i. Further, (16) follows from Theorem 5. Now assume that F is two-valued {0, 2 s }. We get directly [START_REF] Carlet | Characterizations of the differential uniformity of vectorial functions by the Walsh transform[END_REF] because in this case N 1 = • • • = N s-1 = 0 so that N s = 2 n -1. In this case, t ≥ s since it is impossible to have (λ) < s for all λ.

Similarly, we prove (18) by noticing that d(a) cannot be zero. Indeed, any function x → D a F (x) + F (a) is linear and its image set is contained in at least one affine space of codimension 1, i.e., there is at least one λ such that T r(λQ(x, a)) = 0 for all x.

Remark 3 Well-known properties of any APN quadratic function F are directly derived from the previous results:

-If n is odd, then 2(n 1 + 2 2 A) = 2(2 n -1) from (17). But we must have n 1 +2 2 A = (2 n -1) which forces A = 0 and n 1 = 2 n -1, since i n i = (2 n -1). Then L(F ) = 2 (n+1)/2 , i.e., F is an AB function.
-Assume that n is even. Then n 0 + 22 A = 2(2 n -1). Thus n 0 > 0 and F has an even number of bent components. Now, since (2 n -1)i =0 n i = n 0 we get

3 t i=2 n i ≤ t i=2 (2 i -1)n i = (2 n -1)
, where i is even.

Hence the number of non bent components is less than or equal to (2 n -1)/3. The number of bent components equals 2(2 n -1)/3 if and only if L(F ) = 2 (n+2)/2 (t = 2).

Differentially two-valued quadratic functions

In this section we explore in some details the link between the nonlinearity and the two-valued property. We later focus on quadratic functions with low differential uniformity, that is δ ∈ {2, 4, 8}. First, we can be more precise, regarding Theorem 4.

Theorem 6 Let F be quadratic differentially two-valued {0, 2 s } over F 2 n . Then, for even n N L(F ) ≤ 2 n-1 -2 (n+s-1)/2 , if s is odd, 2 n-1 -2 (n+s-2)/2 , if s is even.
Moreover, for any n, with n + s even, N L(F ) = 2 n-1 -2 (n+s-2)/2 if and only if (λ) is constant for all λ ∈ F * 2 n , i.e. F is plateaued with single amplitude. For n even and s odd, equality cannot occur when F is plateaued with single amplitude.

Proof. First, assume that n is even. Thus (λ) should be even for any λ. According to [START_REF] Carlet | Characterizations of the differential uniformity of vectorial functions by the Walsh transform[END_REF] we deduce that max

λ∈F * 2 n (λ) ≥ s+1, if s is odd, s, if s is even.
Combining with [START_REF] Bracken | On the fourier spectra of the infinite families of quadratic APN Functions[END_REF] we get

L(F ) = max λ∈F *
Now we assume that n + s is even for any n. From [START_REF] Charpin | Sparse Permutations with Low Differential Uniformity[END_REF] and Theorem 4, we have L(F ) ≥ 2 (n+s)/2 where equality holds if and only if (λ) takes the same value for all

λ ∈ F * 2 n . It is because if max λ∈F * 2 n 2 (λ) = 2 s then 2 s (2 n -1) = i≤s n i 2 i ⇒ n s = 2 n -1, n 1 = . . . = n s-1 = 0.
We know that for n odd and s even then F cannot be two-valued {0, 2 s }.

Let n be even, s be odd and max λ∈F * 2 n 2 (λ) = 2 s+1 . Clearly, it is impossible to have 2 (λ) = 2 s+1 for all λ.

An application of Theorem 6 is given by Theorem 8 in Section 5. Now we treat differentially two-valued {0, 4} functions.

Lemma 4 Let F be a quadratic function over F 2 n which is differentially twovalued {0, 4}. Then n is even and N L(F ) = 2 n-1 -2 n/2 if and only if F does not have bent components. Moreover, in this case (λ) = 2 for any λ ∈ F * 2 n .

Proof. For δ = 2 s with s even, we know that n must be even (see Corollary 1). If F does not have any bent components, say there is not any λ ∈ F * 2 n such that (λ) = 0, then (λ) ≥ 2 for all λ ∈ F * 2 n . But from Corollary 3, we have

λ∈F * 2 n 2 (λ) = 2 2 (2 n -1).
which is possible if and only if (λ) = 2 for all λ. Now suppose that F has the best nonlinearity. Then F is plateaued with single amplitude, from Theorem 6. This amplitude is 2 (n+2)/2 providing that F has no bent component 1 .

Assume that F is a quadratic permutation over F 2 n , where n is even, such that δ = 4. We know from Theorem 1 that F is two-valued {0, 4}. Moreover L(F ) = 2 (n+2)/2 , from Lemma 4.

Theorem 7

Let n be even. Then any quadratic differentially 4-uniform permutation is two-valued {0, 4} and has the best nonlinearity, i.e., N L(F ) = 2 n-1 -2 n/2 , and such a function is with single amplitude.

When F is differentially 4-uniform, but not two-valued, there are surely a number of different Walsh spectrum. However specific properties appear.

Corollary 4 Let F be quadratic over F 2 n such that δ = 4, which is not two-valued. With notations as in Corollary 3. We have j∈J

2 j n j = λ∈F * 2 n 2 (λ) = 2N 1 +4N 2 .
In particular,

• If n is odd and L(F ) = 2 (n+3)/2 then n 1 = 0. Moreover N 2 = 3n 3 .

• If n is even and L(F ) = 2 (n+2)/2 then n 0 = 0. Moreover, the number n 0 of bent components satisfies n 0 = 2(2 n -1 -N 2 )/3.

In both cases, N 2 is divisible by 3.

Proof. The first formula is derived from Corollary 3. Note that N 1 = 0 since F is not two-valued. We assume that F satisfies L(F ) = 2 (n+s)/2 with s = 3 for n odd and s = 2 for n even.

When n is odd, we get 2N 1 + 4N 2 = 2n 1 + 8n 3 . Note that

N 1 = 2 n -1-N 2 and n 1 = 2 n -1-n 3 ,
so that (2 n -1) + N 2 = (2 n -1) + 3n 3 providing N 2 = 3n 3 . It is impossible to have n 1 = 0, which would imply

8(2 n -1) = 2(2 n -1)+2N 2 with N 2 < (2 n -1).
When n is even, we get 2N 1 + 4N 2 = n 0 + 4n 2 where n 0 = 0 from Theorem 1. Since n 2 = 2 n -1 -n 0 , we obtain 3n 0 = 2(2 n -1 -N 2 ). Note that this indicates that 2 n -1 -N 2 is not zero and is divisible by 3.

When n is even F can be two-valued {0, 4} with bent components (see Problem 5.1, Section 5). When n is odd there are permutations which are differentially 4-uniform but are not two-valued, as we show by the next example.

Example 3 It was proved in [START_REF] Bracken | On the Walsh spectrum of a new APN function[END_REF] that the APN quadratic function G(x) = x 3 + T r(x 9 ), introduced in [START_REF] Budaghyan | Constructing new APN functions from known ones[END_REF], has the best nonlinearity. Further, it was proved by [START_REF] Charpin | Sparse Permutations with Low Differential Uniformity[END_REF]Proposition 8] that the function F (x) = x 3 +T r(x 9 +x 3 ) over F 2 n , where n is odd, is a permutation such that δ(F ) = 4. Moreover D a F is 2-to-1 if and only if T r(a -3 ) = 1, implying N 2 = 2 n-1 -1. We are going to prove that F has the best possible nonlinearity amongst quadratic differentially 4-uniform functions (for odd n), say L(F ) = 2 (n+3)/2 . We have for any λ such that T r(λ) = 1:

T r (λ(D a F (x)+F (a))) = T r(λ(x 2 a+a 2 x)+(x 2 a+a 2 x+x 8 a+a 8 x)T r(λ)) = T r(µ(x 2 a+a 2 x)+x 8 a+a 8 x), µ = λ+1 = T r x 8 (a+a 2 6 +(µa) 2 2 +µ 2 3 a 2 4 ) = T r(x 8 L(a)).
The linear function L is of the form L(x) = e 0 x + e 1 x 2 2 + e 2 x 2 4 + e 3 x 2 6 where gcd(2, n) = 1. Then the kernel of L has dimension at most three, by applying Lemma 2. Clearly, if T r(λ) = 0 then (λ) = 1. Hence (λ) ≤ 3 for any λ and we conclude that L(F ) = 2 (n+3)/2 and, using Corollary 4,

n 3 = 2 n-1 -1 3 , n 1 = 5×2 n-1 -2 3
and N 1 = 2 n-1 .

On some special quadratic functions

In this section we want to show that our results lead to interesting tools to study quadratic functions. Notation is fixed in all this section. Throughout this section any quadratic function F over F 2 n is defined as follows

F (x) = r∈R ν r x r , where R ⊆ Q = {2 i +2 j | 0 ≤ i < j ≤ n-1}, (20)
where the ν r are nonzero elements of F 2 n . Hence, for any a ∈ F * 2 n , the derivative in point a is expressed as follows:

D a F (x) = r∈R,r=2 i +2 j ν r (a 2 i x 2 j +a 2 j x 2 i )+F (a). (21)
By using Theorem 6, we can prove the following property.

Theorem 8 Let F be any function given by [START_REF] Charpin | Differential uniformity and the associated codes of cryptographic functions[END_REF]. Assume that F has no bent component (when n is even). Let t be a nonzero integer which divides n and the nonzeros i and j, for all r ∈ R, r = 2 i + 2 j . Then F is differentially two-valued {0, 2 t } if and only if the component functions of F have all the same amplitude which is 2 (n+t)/2 with n + t even, i.e., the set of Walsh coefficients of F is {0, ±2 (n+t)/2 }.

Proof. We have to be more precise about the case where t = 1. When n is odd, we know that F is APN, and then AB, if and only if (λ) = 1 for all λ. Moreover n cannot be even when t = 1, since in this case F has bent components. Now, we assume that t ≥ 2. We compute the linear space of any component function f λ , λ ∈ F * 2 n :

D a f λ (x) = T r (λD a F (x)) = T r   λ   r∈R,r=2 i +2 j ν r (a 2 i x 2 j +a 2 j x 2 i )+F (a)     = T r x r=2 i +2 j (a 2 n-j+i (ν r λ) 2 n-j +a 2 n-i+j (ν r λ) 2 n-i ) +λF (a)
= T r (xL(a)+λF (a)) .

Since F has no bent component, the kernel of the linear application L has dimension at last 2 for even n and at least 1 for odd n. First, we fix λ. If L(a) = 0 then L(ξa) = 0 too, for all ξ ∈ F 2 t . Indeed, for any r ∈ R, r = 2 i + 2 j , t divides n and the nonzeros i and j so that (ξa) 2 n-j+i = ξa 2 n-j+i , for instance. Therefore, (λ) ≥ t. Assuming that F is two-valued {0, 2 t }, we apply Corollary 3:

λ∈F * 2 n 2 (λ) = 2 t (2 n -1), where max λ (λ) ≥ t,
implying that (λ) = t for all λ, which is possible for even n + t only. Conversely, if the Walsh spectrum of F is {0, ±2 (n+t)/2 }, we have Let α be a primitive element of F 2 n and v, w ∈ F 2 k with vw = 1. Define the function F on F 2 3k as

F (x) = αx 2 s +1 +α 2 k x 2 2k +2 k+s +vx 2 2k +1 +wα 2 k +1 x 2 s +2 k+s . ( 22
)
The authors propose to prove that F is bijective, two-valued {0, 2 t } and highly nonlinear.

It was proved later in [START_REF] Qu | A negative answer to Bracken-Tan-Tan's problem on differentially 4-uniform permutations over F 2 n[END_REF] that for t = 2, the function F is not always bijective and at the same time that δ = 4. Moreover the authors suggest that the proofs given in [START_REF] Bracken | A few more quadratic APN functions[END_REF][START_REF] Bracken | On the fourier spectra of the infinite families of quadratic APN Functions[END_REF], for the APN case (t = 1), can be slightly modified to solve Problem 5.1. Reading in this proofs the expressions of the functions D a F and D a f λ , it appears that for t > 1:

• The derivatives D a F are 2 i -to-1 with i ≥ t so that d(a) ≥ t for all a ∈ F * 2 n . From [33, Claim 2], we then deduce that for t = 2 the function F is two-valued {0, 4} for any even k.

• Whenever the component f λ is not bent, its linear space has dimension at last t so that (λ) ≥ t for all such λ ∈ F * 2 n .

We now indicate our contribution to solve Problem 5.1:

-If F has no bent component then Theorem 8 applies. It is especially the case for odd n. In this case, one has to prove either that δ = 2 t or (equivalently) that L(F ) = 2 (n+t)/2 . -When n is even, we know that F is not always bijective and then can have some bent components. In this case, comparing to the the odd case, it is necessary to know the number of bent components and then disprove the bijectivity.

Problem 1 Study the possible bent components of the function F , given by [START_REF] Gold | Maximal recursive sequences with 3-valued recursive crosscorrelation functions (corresp.)[END_REF], i.e., does it exist such component and in this case what is the cardinality of the set of such bent functions?

Conclusion

In this paper, our aim is to establish some relations beetween the differential uniformity and the nonlinearity of vectorial functions over F 2 n . We propose a lower bound for the nonlinearity of monomial permutations depending on their differential uniformity. More generally, we show that the functions which are differentially two-valued are somehow optimal objects and then we pay a special attention to the quadratic case. Our relation (Theorem 5) fully applies to particular classes of functions, such as permutation whose differential uniformity is 4 when n is even. It reveals also the complexity of this corpus, in general. Thus, we have adressed a number of problems which remain open although they are widely studied, especially for quadratic functions. We emphasize that the number of bent components is a key parameter to study these functions when n is even. We point out that almost all known quadratic APN functions have similar properties which allows to construct functions which are differentially two-valued {0, 2 s }, s > 1. These classes of functions correspond to specific polynomials and in this case F 2 n has special proper subfields.

  a) = 2 t (2 n -1), where max a d(a) ≥ t. Problem 5.1 [9] Let n = 3k, s, k be positive integers with k + s divisible by 3 and gcd(s, k) = t with t > 1, gcd(s, 3) = gcd(3, k) = 1, k t is odd.

n 2 (n+ (λ))/2 ≥ 2 (n+s+1)/2 , if s is odd, 2 (n+s)/2 , if s is even,(19)which gives the required upper bound for the nonlinearity.

The set of bent components cannot contain a subspace of dimension k such that k > n/2[START_REF] Nyberg | Perfect nonlinear S-boxes[END_REF].

Fixing a in the expression of D a f λ (x) above, we see that if there is λ such that D a f λ (x) is constant, it holds also for ξλ with ξ ∈ F 2 t .

The following theorem is actually [9, Theorem 1.2] that we are able to complete, as we explain in the proof below.

Theorem 9 Let n = 3k with gcd(3, k) = 1. Let t be a divisor of k such that k/t is odd. Let s be an integer such that gcd(n, s) = t and 3 divides k + s. Define the function

where α is a primitive element of F 2 n . Then

and all components of F have the same amplitude; the Walsh coefficients of F are {0, ±2 (n+t)/2 }.

Proof.

The properties (i) and (ii) are proved in [START_REF] Bracken | Binomial differentially 4-uniform permutations with high nonlinearity[END_REF]. The authors later proved that N L(F ) = 2 n-1 -2 n/2 , for t = 2 and n even, and that N L(F ) ≥ 2 n-1 -2 (n+t-e)/2-1 , for any t > 1 where t, e are such that e ≡ n + t (mod 2). The proof is specific and technical.

We are able to prove (iii) by using directly our previous results. First, if t = 2 we apply Theorem 7. More generally, we can apply Proposition 8. Indeed, F is a permutation and then cannot have a bent component. Further, t divides n, s, k and then it divides n -k and k + s too.

The binomials which are treated in the previous theorem were obtained in [START_REF] Bracken | Binomial differentially 4-uniform permutations with high nonlinearity[END_REF], by changing certain conditions, from the APN binomials constructed in [START_REF] Budaghyan | Two classes of quadratic APN binomials inequivalent to power functions[END_REF]. Looking at the list of known APN quadratic functions in [START_REF] Bracken | A few more quadratic APN functions[END_REF], it appears that those F which depend on a positive integer s share same properties. The field F 2 n has always subfields in these examples and almost all such F may be modified to satisfy the hypothesis of Theorem 8. Another quadratic function is discussed in several papers, which could be studied by using our tools. The problem of determining its properties is as follows.


F Cantalloube
email: cantalloube@mpia.de

E H Por

K Dohlen

J.-F Sauvage

A Vigan

M Kasper

N Bharmal

Th Henning

W Brandner

J Milli

C Correia

T Fusco

Origin of the asymmetry of the wind driven halo observed in high contrast images

Keywords: Instrumentation: adaptive optics, Instrumentation: high angular resolution, Atmospheric effects, Techniques: image processing, Methods: data analysis, Infrared: planetary systems

The latest generation of high contrast instruments dedicated to exoplanets and circumstellar disks imaging are equipped with extreme adaptive optics and coronagraphs to reach contrasts of up to 10 -4 at a few tenths of arc-seconds in the near infrared. The resulting image shows faint features, only revealed with this combination, such as the wind driven halo. The wind driven halo is due to the lag between the adaptive optics correction and the turbulence speed over the telescope pupil. However we observe an asymmetry of this wind driven halo that was not expected when the instrument was designed. In this letter, we describe and demonstrate the physical origin of this asymmetry and support our explanation by simulating the asymmetry with an end-to-end approach. From this work, we found out that the observed asymmetry is explained by the interference between the AO-lag error and scintillation effects, mainly originating from the fast jet stream layer located at about 12 km in altitude. Now identified and interpreted, this effect can be taken into account for further design of high contrast imaging simulators, next generation or upgrade of high contrast instruments, predictive control algorithms for adaptive optics or image post-processing techniques.

Introduction

With the wake of the new generation of high contrast imaging (HCI) instruments equipped with extreme adaptive optics (XAO) and advanced coronagraphs, dedicated to exoplanet and circumstellar disk imaging, we can now visualize optical effects that were expected but never revealed before. On 8-m class telescopes, instruments such as VLT/SPHERE [START_REF] Beuzit | A possible VLT-SPHERE XAO upgrade: going faster, going fainter, going deeper[END_REF], Gemini/GPI [START_REF] Macintosh | The Gemini Planet Imager Exoplanet Survey, NASA OSS Proposal Macintosh[END_REF], Clay/MagAO-X [START_REF] Close | Optical and mechanical design of the extreme AO coronagraphic instrument MagAO-X Close[END_REF]Males et al. 2014) and Subaru/SCExAO (Jovanovic et al. 2015) are equipped with XAO, providing a Strehl ratio up to 95% in the near infrared, and coronagraphs, providing a raw contrast of up to 10 -4 at a few hundred milliarcseconds (mas). Images obtained with these instruments show features such as the correction radius of the XAO, the deformable mirror actuator grid print-through, the bright central spot due to diffraction effects in the Lyot coronagraph (Poisson spot or Arago spot), and the wind driven halo due the temporal lag between the application of the XAO correction and the evolving turbulence. All these features were expected and taken into account when designing and simulating the instrument.

However, some unexpected features are also visible within HCI images: the wind driven halo often shows an asymmetry, one wing being brighter and broader than the other, and the point-spread function (PSF) sometimes breaks up, leading to catastrophic loss of performance. While the latter, known as the low wind effect, is described elsewhere (Milli et al. 2018), describing and understanding the asymmetric wind driven halo, which also limits the high contrast capabilities of the instrument, is the object of this letter.

In this letter, we first describe qualitatively the observed asymmetry of the wind driven halo (Sect. 2). Based on these observations we propose an explanation and derive its mathematical demonstration (Sect. 3). To prove our interpretation, we perform end-to-end simulations taking into account the optical effect that generates the asymmetry and checked that the asymmetry indeed varies as expected with the parameters upon which it depends (Sect. 4).

Description of the observed asymmetry

The wind driven halo (WDH) is the focal plane expression of the AO servolag error (also often referred to as temporal bandwidth error). The AO-lag temporal error appears when the turbulence equivalent velocity above the telescope pupil (defined via the coherence time τ 0 , up to a few tens of milliseconds under good conditions) is faster than the adaptive optics correction loop frequency (being about 1.4 kHz for SAXO, the XAO of SPHERE, [START_REF] Petit | Proc. SPIE[END_REF]. Using a coronagraph and a sufficiently long detector integration time (DIT) reveals, in the focal plane, the starlight diffracted by this specific error. As a consequence, the PSF is elongated along the projected wind direction, making a butterfly shaped halo appear on the images. By definition, this aberration being a phase shift in the pupil plane, it must be symmetric in the focal plane. In practice however, we observe an asymmetry of the WDH along its axis: one wing being smaller and fainter than the other.

Fig. 1 shows images obtained with SPHERE and GPI1 in which we can visualize the asymmetry of the WDH. To highlight the asymmetry, Fig. 2 shows the radial profile along the wind direction and the azimuthal profile at 6 λ/D of the SPHERE-IRDIS image presented on Fig. 1 (left).

By definition, the WDH is produced by high wind speed turbulent layers. It is now confirmed that it is mainly triggered by the high altitude jet stream layer, located in a narrow region of the upper troposphere, at about 12 km altitude above sea level (200 mbar) which has a wind speed from 20 m/s up to 50 m/s [START_REF] Tokovinin | [END_REF]Osborn & Sarazin 2018). [START_REF] Madurowicz | Characterization of lemniscate atmospheric aberrations in Gemini Planet Imager data Males[END_REF] demonstrated it by correlating the WDH direction with the wind direction at different altitude given by turbulence profiling data for the whole GPIES survey data (Macintosh 2013). A forthcoming paper will similarly analyze the WDH within SPHERE data and come to the same conclusion.

Focal plane asymmetries can only be created by combining phase and amplitude aberrations. As we observed that the asymmetry is pinned to the servolag signature (butterfly shape), we considered it may be caused by the interaction between servolag errors and amplitude errors created by scintillation, where the phase errors generated by high atmospheric layers propagate into amplitude errors following Fresnel's propagation laws.

Interference between scintillation and temporal error

In the following we provide an analytical demonstration that the combination of two well-known effects, the AO loop delay (servolag error) and scintillation (amplitude error), will indeed create the asymmetric starlight distribution observed in the high contrast images.

In the pupil plane, the electric field can be written as:

E = (1 -).e iφ , (1)
where is the amplitude aberration and φ the phase aberration. An adaptive optic system measures the phase φ(t) at a given time t via the wavefront sensor (WFS) and corrects it using a deformable mirror (DM). However, between the analysis of the WFS information taken at an instant t and the command sent to the DM at an instant t + ∆t, if the incoming turbulent phase has varied during ∆t, a temporal phase error will remain (the AO servolag error). As a general rule, this absolute time delay ∆t varies with both the AO-loop gain and the AO-loop speed and is intrinsic to any AO system. The remaining phase error ∆φ can be written as a function of this absolute time delay ∆t following (in a closed loop system):

∆φ = φ(t) -φ(t -∆t) ∼ ∆t φ , ( 2
)
where φ is the time derivative of the phase. This approximation is valid for spatial frequencies affected by the servolag error, that is to say much lower than 1/(v wind .∆t) under the frozen flow hypothesis (i. e. only the wind speed is responsible for the turbulent phase variation).

Thus, after the AO correction, the electric field becomes:

∆E = (1 -).e i(∆t φ ) . (3)
Which, under the small phase and small amplitude errors approximation, simplifies to:

∆E (1 -).(1 + i(∆t.φ )) ∼ 1 -+ i (∆t φ ). (4)
Seen through a perfect coronagraph (the patterns exclusively due to diffraction effects of a plane wavefront by the entrance pupil are entirely removed), the post-AO electric field ∆E c is transformed into:

∆E c ∼ -+ i ∆t φ .
(5)

The Earth's turbulent atmosphere is present to different degrees throughout the three dimensions of the atmosphere. Fresnel propagation translates phase variations in the upper atmosphere into amplitude variations via the Talbot effect, creating the so-called scintillation. By the formalism of Zhou & Burge (2010), the phase variations in an atmospheric layer located at altitude z produces an amplitude distribution at the telescope pupil of:

= sin(2π z z T ) φ (6)
where z T is the Talbot length, defined as the distance from which the phase error is fully converted into amplitude error:

z T = 1/(2 f 2 λ)
where f is the spatial frequency and λ the wavelength. For SPHERE, the highest imaging wavelength is 2.2 µm (K-band) and the highest corrected spatial frequency is 2.5m -1 , given by the DM inter-actuator spacing (40 × 40 actuators over the 8 m diameter telescope pupil), yielding a minimum Talbot length of about 36 km altitude, which is above the highest turbulence layers. This explains why, for both GPI and SPHERE, this effect was neglected when designing the instrument.

Adding the scintillation into the coronagraphic post-AO electric field of Eq. ( 5) gives:

∆E c ∼ -sin(2π z z T ) φ + i ∆t φ . (7)
The resulting intensity observed at the focal plane, I c , is, within the Fraunhofer framework, the squared modulus of the Fourier transform of the electric field ∆E c :

I c = |FT [∆E c ]| 2 = | -sin(2π z z T ) FT [φ] + i∆t FT [φ ]| 2 (8) With FT [φ ] = ∂FT [φ] ∂t = FT [φ]
being the time derivative of the Fourier transform of the phase. If we assume an arbitrary phase whose general expression can be written φ = exp(i2π f.r), f being the spatial frequency and r the position, then by making the change of variable r ← r +∆r where we define the beam shift factor ∆r = (v wind . ∆t) to account for the servolag shift (under the frozen flow hypothesis), Eq. ( 8) becomes:

I c = | -sin(2π z z T ) FT [φ] -2π f v wind ∆t FT [φ]| 2 = |FT [φ]| 2 sin(2π z z T ) + 2π f ∆r 2 , (9)
where |FT [φ]| 2 is by definition the power spectral density of the turbulent phase and ∆r represents the physical spatial shift between the turbulent layer and the AO correction. Developing Eq. ( 9) leads to an asymmetric function of the spatial frequency f : I c indeed shows an asymmetric distribution of light in the high contrast images with respect to the center, originating from interferences. Therefore, the intensity of each wing of the WDH can be written, for constructive and destructive interference I + and I -respectively:

I + = |FT [φ]| 2 sin(2π z z T ) + 2π f ∆r 2 ; ( 10
)
I -= |FT [φ]| 2 sin(2π z z T ) -2π f ∆r 2 . ( 11
)
We thus demonstrated that a temporal phase shift (from temporal delay of the AO loop) between phase error (from the atmospheric turbulence) and amplitude error (from the scintillation effect) creates an asymmetry pinned to the wind driven halo in the focal plane image. We can define the relative asymmetry factor, F asymmetry , as the normalized difference between these two intensities:

F asymmetry = I + -I - I + + I - (12) = 2 sin(2π z z T ) f ∆r sin(2π z z T ) 2 + ( f ∆r) 2 . ( 13
)
This factor is thus between 0 (no asymmetry) and 1 (all the light is spread in only one wing).2 With current HCI instruments, the WDH has a typical contrast of 10 -4 (see Fig. 2), whereas the scintillation has a typical contrast of 10 -6 (Tatarski 2016) so we can ignore the scintillation term in the denominator and simplify to sin( z z T ) ∼ z z T , which yields, after replacing the Talbot length by its expression, the following approximation:

F asymmetry = 4z f λ v wind ∆t + O        z f λ v wind ∆t 2        . ( 14
)
We consequently expect the asymmetry factor to grow linearly with the spatial frequency, and therefore with the angular separation to the star. From this demonstration we can already infer a few effects. First, as the interference is taking place between the turbulence residuals and the AO correction lag, any type of coronagraph will reveal the asymmetry of the WDH. Second, despite the fact that the Talbot length is 36 km while the jet stream layer is at 12 km altitude, the propagation distance is sufficient enough to convert a small fraction of the phase error into amplitude error and therefore produce the observed asymmetry. Consequently, the higher the altitude of the fast layer, the more asymmetry is produced and, on the contrary, the ground layer does not produce this asymmetry. Third, knowing that the amplitude errors are only due to the turbulence whereas the phase delayed error

A&A proofs: manuscript no. aanda is due to both the wind speed and the AO loop correction speed, the asymmetry varies with temporal parameters as follow: (i) if the AO loop delay ∆t increases (e. g. the AO loop is slower) we loose the correlation between the amplitude errors and the delayed phase errors, making the asymmetry smaller; (ii) if the wind speed v wind is higher, all the same the correlation between the amplitude error and the delayed phase error decreases, making the asymmetry smaller. In other word, if the beam shift ∆r between the turbulent layer and the AO correction increases, the correlation decreases and so does the asymmetry. Finally, we expect this asymmetry to increase with wavelength as the Talbot length is inversely proportional to wavelength while the other parameters are independent of wavelength.

As a consequence, an observation site such as Mauna Kea which suffers from less jet stream compared to observatories located at Paranal in Chile (e.g. [START_REF] Sarazin | Future Giant Telescopes[END_REF]) would be beneficial to avoid the wind driven halo 3 in the high contrast images, and the subsequent asymmetry which may arise depending on the AO correction setting and the speed of the high atmospheric turbulent layers.

Simulations of the effect

In the following, we describe a numerical simulation of an idealized AO system reacting to a simplified atmosphere with a single, high-altitude turbulence layer. The goal is to explore the connection between servolag, scintillation, and the occurrence (or absence) of an asymmetric WDH. The simulations are conducted using the HCIPy package [START_REF] Por | Proc. SPIE[END_REF], which is available as open-source software on GitHub 4 .

We simulated a single atmospheric layer at the altitude of the jet stream, which is then moved across the telescope aperture according to the frozen-flow hypothesis. The light is propagated from the layer to the ground using an angular-spectrum Fresnel propagation code. This light is sensed using a noiseless WFS, which in turn is used to drive a DM. An integral controller with a gain of 0.5 is assumed. The flattened wavefront is then propagated through a perfect coronagraph (Cavarroc et al. 2006) before being focused onto the science camera. We carry out 500 independent short-exposure simulations, whose images are stacked to form the final long-exposure image. A list of the nominal simulation parameters can be found in Table 1.

Fig. 3 shows the coronagraphic simulated images obtained with or without AO lag and with or without scintillation. As expected, only the combination of both amplitude error and AO servolag error leads to an asymmetric WDH.

Fig. 4 shows the radial profile of the simulated images along the wind direction (top) and the corresponding asymmetry factor as defined at Eq. ( 12) (bottom), as a function of the separation to the star, where we indeed observe that the asymmetry grows linearly with the separation. We also demonstrate that indeed the scintillation from the jet stream layer at 12 km altitude is enough to create the asymmetry of the wind driven halo and that lower altitude layers create less asymmetry. As expected from the approximation of Eq. ( 14), our simulations also show that the asymmetry is stronger when the wind speed decreases or when the AO loop frequency decreases (for a fixed AO loop gain). We 3 The Subaru/SCExAO high contrast images do not show the wind driven halo and its asymmetry. This might also be explained by the use of predictive control algorithm based on machine-learning techniques which intends in getting rid of the servolag error (Males & Guyon 2018;[START_REF] Guyon | [END_REF]). 4 https://github.com/ehpor/hcipy also checked that the asymmetry factor is indeed higher at longer wavelengths.

In a forthcoming paper, we will compare this analysis to onsky images obtained with SPHERE, which involves isolating the contribution of the WDH in the image since other error terms are hiding these trends.

Conclusions

In this letter we pointed out the presence of an asymmetry of the wind driven halo that is revealed in high contrast images. We described and demonstrated its origin to being due to interference between AO correction lag (delayed phase error) and scintillation (amplitude errors). We supported our demonstration by simulating this effect using an end-to-end simulator. From those simulations we confirmed the expected behavior of the asymme- 12) (bottom) for the simulated data sets. Solid black line is using the nominal parameters of Tab. 1 (image shown in the bottom right of Fig. 3). Other lines differ in one parameter playing a role in the asymmetry: shorter wavelength (H-band, λ = 1.6 µm, blue line), lower altitude (z = 8 km, green line), lower wind speed (v wind = 20 m/s, red line) and slower AO loop frequency ( f AO = 800 Hz, yellow line).

The DM cutoff frequency is at 20 λ/D (dotted gray line). In the bottom plot, solid lines indicate the asymmetry from the simulated images, and dashed lines show the prediction from Eq. ( 14).

try with different atmospheric turbulence conditions, XAO correction, and imaging wavelength. We further demonstrated, that the jet stream layer is the main culprit for this aberration since it is responsible for both servolag error (being a fast layer) and scintillation (being a high altitude layer). Therefore, an observing site with weak or no jet stream would get around this aberration.

While the current letter focuses on exploring the origin of the wind driven halo asymmetry so as to better understand our current observations and AO systems for future designs, a more quantitative analysis of its implication on high contrast imaging capabilities and potential mitigation strategies will be detailed in a separate paper. Indeed, the servolag error, when present, is now one of the major effect limiting the high contrast capabilities of the current instruments (along with the low wind effect, the noncommon path aberrations and residual tip-tilt errors). Knowing that this wind driven halo shows an asymmetry makes it more difficult to deal with in post-processing (as using for instance the residual phase structure functions yields a symmetric phase error or that most filters have a symmetric effect). Now that this effect is acknowledged and demonstrated, next step is to take it into account within end-to-end XAO simulators (e.g. COMPASS or SOAPY, Gratadour et al. 2014;[START_REF] Reeves | Adaptive Optics Systems V[END_REF] or analytical simulators (e.g. PAOLA, Jolissaint 2010) and more generally in XAO error budgets, when used in the HCI framework. This study gives insights into the instrument operations, essential to designing optimal post-processing techniques or AO predictive control tools that both aim to get rid of the servolag error signature (e.g. Males & Guyon 2018;[START_REF] Correia | Advanced control laws for the new generation of AO systems Gratadour[END_REF]). This effect is also important to design the next generation of high contrast instruments (e.g. MagAOX [START_REF] Close | Optical and mechanical design of the extreme AO coronagraphic instrument MagAO-X Close[END_REF], or giant segmented mirror telescopes instruments dedicated to HCI) or to lead the upgrades of existing high contrast instruments (e.g. GPI or SPHERE, [START_REF] Chilcote | Upgrading the Gemini planet imager[END_REF][START_REF] Beuzit | A possible VLT-SPHERE XAO upgrade: going faster, going fainter, going deeper[END_REF]) by, for instance, adding a second DM to correct for the scintillation.

Fig. 1 .

 1 Fig. 1. Coronagraphic focal plane images showing the asymmetry of the wind driven halo. Left: One exposure obtained with SPHERE-IRDIS (H2 band, 1.593 µm, ∆λ ≈ 53 nm). Middle-Left: One exposure obtained with SPHERE-IFS (second channel of YH mode, 0.991 µm, ∆λ ≈ 30 nm). Middle-Right: One exposure obtained with SPHERE-IRDIS in broadband (H band, 1.625 µm, ∆λ ≈ 291 nm). Right: One exposure obtained with GPI (second channel of YH mode, 1.503 µm, ∆λ ≈ 45 nm). The images are purposely stretched in intensity to highlight the asymmetry (log scale).

Fig. 2 .

 2 Fig. 2. Profiles of the wind driven halo showing the asymmetry in a SPHERE-IRDIS image: solid line is along the brighter and bigger wing, dashed line is along the fainter and smaller wing. Top: Radial profile along the WDH direction (black solid and red long-dashed lines) and its perpendicular direction (blue dashed lines). The DM cutoff frequency is at 20 λ/D (green dot-dashed line). Bottom: Azimuthal profile at 6 λ/D from the star.

Fig. 3 .

 3 Fig. 3. Simulated images using HCIPy for the parameters gathered on Tab. 1. The images with no time lag were produced with an infinite AO loop speed. Only a time-lagged WDH and scintillation yields an asymmetric coronagraphic PSF. The images are purposely stretched in intensity to highlight the asymmetry and scintillation (log scale).

Fig. 4 .

 4 Fig. 4. Radial profiles along the wind direction (top) and asymmetry factor as defined at Eq. (12) (bottom) for the simulated data sets. Solid black line is using the nominal parameters of Tab. 1 (image shown in the bottom right of Fig.3). Other lines differ in one parameter playing a role in the asymmetry: shorter wavelength (H-band, λ = 1.6 µm, blue line), lower altitude (z = 8 km, green line), lower wind speed (v wind = 20 m/s, red line) and slower AO loop frequency ( f AO = 800 Hz, yellow line). The DM cutoff frequency is at 20 λ/D (dotted gray line). In the bottom plot, solid lines indicate the asymmetry from the simulated images, and dashed lines show the prediction from Eq. (14).

Table 1 .

 1 Nominal set of parameters used for our simulations.

SPHERE images have been published in respectivelyBonnefoy et al. (2018);Wahhaj et al. (2015);[START_REF] Samland | [END_REF] and GPI data inRameau et al. (2016).

The asymmetry factor is maximum (F asymmetry = 1) when the numerator is equal to 1/2 (i. e. sin(2π z z T ). f ∆r = 1: the amplitude error is fully correlated with the phase error), and is minimum (F asymmetry = 0) when the numerator is null (null wind speed / no temporal lag: there is no wind driven halo) or equal to infinity (there is no correlation at all between amplitude error and phase error).

Acknowledgements. We would like to thank the anonymous referee for his/her comments which helped clarifying the letter. The authors also would like to thank J. Lozi and O. Guyon for the discussions about the wind driven halo in the Subaru/SCExAO images. EHP acknowledges funding by The Netherlands Organisation for Scientific Research (NWO) and the São Paulo Research Foundation (FAPESP). NAB acknowledges UK Research & Innovation Science and Technologies Facilities Council funding (ST/P000541/1).