Jean-Christophe Aval
email: aval@math.u-bordeaux.fr

Monomial bases related to the n! conjecture

Keywords: n! conjecture, explicit monomial bases, hook partitions

The purpose of this paper is to find a new way to prove the n! conjecture for particular partitions. The idea is to construct a monomial and explicit basis for the space M µ . We succeed completely for hook-shaped partitions, i.e., µ = (K +1, 1 L ). We are able to exhibit a basis and to verify that its cardinality is indeed n!, that it is linearly independent and that it spans M µ . We derive from this study an explicit and simple basis for I µ , the annihilator ideal of ∆ µ . This method is also successful for giving directly a basis for the homogeneous subspace of M µ consisting of elements of 0 x-degree.

Introduction

Let µ = (µ 1 ≥ µ 2 ≥ • • • ≥ µ k > 0) be a partition of n. We shall identify µ with its Ferrers diagram (using the French notation). To each cell s of the Ferrers diagram, we associate its coordinates (i, j), where i is the height of s and j the position of s in its row. The pairs (i -1, j -1) occurring while s describes µ will be briefly referred to as the set of the biexponents of µ. Now let (p 1 , q 1 ), . . . , (p n , q n ) denote the set of biexponents arranged in lexicographic order and set ∆ µ (x, y) = ∆ µ (x 1 , . . . , x n ; y 1 , . . . , y n ) = det(x

p j i y q j i ) i,j=1...n .
Let M µ be the collection of polynomials in the variables x 1 , . . . , x n ; y 1 , . . . , y n obtained by taking the linear span of all the partial derivatives of ∆ µ . For- This conjecture, stated by A. Garsia and M. Haiman is central for their study of Macdonald polynomials (cf. [START_REF] Garsia | A graded representation model for Macdonald's polynomials[END_REF], [START_REF] Garsia | Some natural bigraded S n -modules and q, t-Kostka coefficients[END_REF]). To be more precise, Macdonald introduced in [START_REF] Macdonald | A new class of symmetric functions[END_REF] a new symmetric function basis and associated Macdonald-Kostka coefficients K λµ (q, t), which are a priori rational functions in q, t. Macdonald conjectured that: Conjecture 2 (MPK conjecture): The functions K λµ (q, t) are polynomials with non-negative integer coefficients.

Looking for a representation theoretical setting for the Macdonald basis, A. Garsia and M. Haiman made the following conjecture: Conjecture 3 (C = H conjecture): For the diagonal action of S n , M µ is a bigraded version of the left regular representation. Moreover, if C λµ (q, t) denotes the bigraded multiplicity of the character χ λ in the bigraded character of the module M µ then: C λµ (q, t) = K λµ (q, 1/t)t n(µ) , where n(µ) = k i=1 (i -1)µ i .

Conjecture 3 clearly implies Conjecture 1 and 2. M. Haiman [START_REF] Haiman | Macdonald polynomials and geometry[END_REF] using Hilbert schemes theory recently proved that the n! conjecture actually implies the C = H conjecture. A part of the MPK conjecture is that the K λµ (q, t) are polynomials, which is not obvious from their definition. This part has been recently proved in several independent papers (cf. [START_REF] Garsia | Plethystic formulas and positivity for q, t-Kostka polynomials[END_REF], [START_REF] Garsia | Plethystic formulas for Macdonald q, t-Kostka coefficients[END_REF], [START_REF] Kirillov | Affine Hecke algebras and raising operators for Macdonald polynomials[END_REF], [START_REF] Knop | Integrality of two variable Kostka functions[END_REF], [START_REF] Sahi | Interpolation, integrality, and a generalization of Macdonald's polynomials[END_REF]).

When µ = (1 n ) or µ = (n), ∆ µ reduces to the Vandermonde determinant in x and y respectively. In these cases, it is a classical result (see [START_REF] Bergeron | On certain spaces of harmonic polynomials[END_REF]) that dim M µ = n!. But although this conjecture has been verified by computer for small partitions up to n = 8 and proved for some special cases (cf. [START_REF] Allen | The decomposition of a bigraded left regular representation of the diagonal action of S n[END_REF], [START_REF] Garsia | Orbit harmonics and graded representation[END_REF], [START_REF] Garsia | Some natural bigraded S n -modules and q, t-Kostka coefficients[END_REF], [START_REF] Reiner | A Proof of the n! Conjecture for Generalized Hooks[END_REF]), it has not been established in full generality. Several methods have been developed to prove the n! conjecture but none of them has been able to give a proof in more than some special cases.

In this paper our goal is to propose a new method to prove the n! conjecture for some particular partitions. We want to construct explicit bases for the space M µ . These bases are made of monomial derivatives of ∆ µ . We present here how we are able to do it for hook-shaped partitions, i.e., µ = (K + 1, 1 L ) with K + L + 1 = n. In section 2 we describe the way to construct the basis and prove that its cardinality is n!. In the third section we show that our family spans M µ . Moreover, we derive from that proof an explicit and simple basis for I µ , the annihilator ideal of ∆ µ . In the fourth section we prove by a completely new method that the elements of our basis are linearly independent. In section 5 we explain how this method is also successful for the homogeneous subspace of M µ consisting of elements of 0 x-degree. We obtain in fact a direct way to construct a basis for this subspace.

Construction and enumeration

Let µ be a partition of n whose Ferrers diagram is a hook, i.e., µ = (K +1, 1 L ) with K + L + 1 = n.

Construction

Let us take an horizontal axis. A "shape" associated to µ is constructed the following way: suppose the line has room for K + L spaces. Choose K of these spaces to be y-columns and L to be x-columns. In the y-columns place stacks of boxes above the line of height K, K -1, . . . , 1 arranged in decreasing order. In the x-columns place stacks of boxes of decreasing depth L, L -1, . . . , 1 below the line.

Here is an example of shape: y x associated to the partition:

We shall now put crosses in the cells of the shape to obtain "drawings". As we shall not distinguish two drawings with the same number of crosses in each column, we put the crosses near the axis. The rules for putting crosses in a drawing are the following:

1. the number of crosses in the x-columns is any number (not greater than the depth of the column);

2. the number of crosses in the y-columns depends on the x-crosses. For a column which has no x-column to its right, the number of crosses is not greater than the height of the column. In the other case, we look at the first "plain" x-column on the right; i.e., the first column which has only crosses (full x-column) or only white cells (empty x-column).

There is always one, at least the x-column of depth one. Then:

• if it is all white, then we impose at least one cross in the y-column.

• if it is all crossed, then we impose at least one white cell in the y-column.

Remark 1: The family of drawings that we defined is invariant under the operator that inverts the white cells and the crosses. We call this operator flip (it is different from the flip introduced by A. Garsia and M. Haiman in [START_REF] Garsia | Some natural bigraded S n -modules and q, t-Kostka coefficients[END_REF], that we denote from now on by Flip).

Here we give an example of drawing with crosses: Once we have defined the drawings (with crosses), we define associated derivative operators. We give an index to the places of the drawing from left to right and from 1 to n -1. Then to each x-cross in place i, we derive once with respect to x i . We do the same thing for the y-crosses. For example, for the last drawing, the associated derivative operator is:

∂ D = ∂y 2
1 ∂x 2 ∂x 4 ∂x 2 5 ∂y 6 .

Enumeration

We shall denote by D the set of drawings that we defined in the previous subsection. We now verify that its cardinality is n!.

As the number of choices for the y-columns depends only on the shape of the drawing (and not on the x-crosses), we can write that the cardinality equals the following expression, where k 1 denotes the number of y-columns on the right of the last x-column:

k 1 +k 2 =K 2 • 3 • • • (k 1 + 1) • (k 1 + 1) • • • (k 1 + k 2 ) • (L + 1)! k 2 + L -1 k 2 = L(L + 1)K! K k 2 =0 (k 2 + L -1)! k 2 ! (K + 1 -k 2 ) = (L + 1)!K! K k 2 =0 L -1 + k 2 L -1 K + 1 -k 2 1 = (L + 1)!K! K + L + 1 L + 1 = (K + L + 1)!
by the Chu-Vandermonde formula ([3], p. 163).

3 Proof that the family spans M µ

We show here that {∂ D ∆ µ } D∈D spans M µ . We begin by studying I µ , the annihilator ideal of ∆ µ .

Study of I µ

For P, Q two polynomials, we write

P ≡ Q if P (∂)∆ µ = Q(∂)∆ µ , i.e., P -Q ∈ I µ (P (∂) corresponds to the substitution: x i → ∂x i , y i → ∂y i ).
We denote as usual by h k the k-th complete homogeneous symmetric function.

Let also X denote a subset of (x 1 , x 2 , . . . , x n ), Y a subset of (y 1 , y 2 , . . . , y n ), |X| and |Y | their cardinality. We also set X = x∈X x and Ȳ = y∈Y y.

We first notice that:

1. for all 1 ≤ i ≤ n, x i y i ≡ 0;

2. X ≡ 0 as soon as |X| > L;

3. Ȳ ≡ 0 as soon as |Y | > K;

4. for any symmetric homogeneous polynomial P of positive degree, P ≡ 0.

The fourth relation is well known (cf. [START_REF] Bergeron | On certain spaces of harmonic polynomials[END_REF]). The others are clear by observing the elements in the determinantal form of ∆ µ when µ = (K + 1, 1 L ).

Proposition 1: h k (Y ) ≡ 0 as soon as k > 0 and k + |Y | > n.
Proof. It is easily proved by an induction based on h k (y 1 , . . . , y n ) ≡ 0 for all k > 0. We have indeed h 1 (Y n ) ≡ 0, where Y n = (y 1 , . . . , y n ) and for any y ∈ Y :

h k (Y, y) = h k (Y ) + yh k-1 (Y, y). Proposition 2: Ȳ h k (Y ′ ) ≡ 0 as soon as k > 0, k + |Y | > K and Y ⊂ Y ′ .
Proof. Proposition 2 is proved by decreasing induction on |Y ′ |.

We observe that the result is true for |Y ′ | equal to K + 1 and K. Let Y and Y ′ satisfy the hypotheses and assume the result is true down to |Y ′ | + 1. We write for all y i ∈ Y ′ :

h k (Y ′ , y i ) ≡ h k (Y ′ ) + y i h k-1 (Y ′ , y i ),
thus, by induction if k > 1 we obtain the following relation; this relation is

obvious if k = 1 because this implies that |Y | ≥ K: Ȳ h k (Y ′ , y i ) ≡ Ȳ h k (Y ′ ).
Once we have this relation the conclusion easily follows by an increasing induction on |Y ′ | (for example up to n).

Proposition 3: h k (Y )h l (X) ≡ 0 as soon as k > 0, l > 0, k + l + |Y | + |X| ≥ 2n and X ⊂ Y or Y ⊂ X.
Proof. We only show the result when k + |Y | = n and l + |X| = n (the other cases are consequences of Proposition 1).

It is in fact proved as Proposition 1 by a simple induction based on:

h 1 (x 1 , . . . , x n-1 )h 1 (y 1 , . . . , y n-1 ) ≡ 0
which is a consequence of Proposition 1 and x n y n ≡ 0.

Proposition 4: h k (Y )h l (X) ≡ 0
as soon as k > 0, l > 0 and

• either Y ⊂ X and k + l + |Y | > n, • or X ⊂ Y and k + l + |X| > n.
Proof. This is proved by induction on α = 2n -

(k + |Y | + l + |X|).
The case α ≤ 0 reduces to Proposition 3. Suppose the result is true up to α-1 and 2n-(k

+ |Y | + l + |X|) = α > 0.
By symmetry, we shall assume that Y ⊂ X and k + l + |Y | > n. If l > 1, then for any x i ∈ X, we write:

h k (Y )h l (X) ≡ h k (Y )h l (X, x i ) -x i h k (Y )h l-1 (X, x i ) ≡ h k (Y )h l (X, x i ) -x i h k (Y, y i )h l-1 (X, x i ) ≡ 0 by induction.
If l = 1, then |Y | + k ≥ n and we write for any x i ∈ X:

h k (Y )h 1 (X) ≡ h k (Y, y i )h 1 (X) -y i h k-1 (Y )h 1 (X, x i ).
The first term is zero by Proposition 1. The second term is proved to be also zero by increasing induction on

|X| (up to n), since n -k ≤ |Y | ≤ |X| ⇒ n -|X| ≤ k.

Application

We shall show here that any monomial derivative of ∆ µ is a linear combination of the derivatives: {∂ D ∆ µ } D∈D (derivatives corresponding to drawings, i.e., the family defined in section 2).

Theorem 1: {∂ D ∆ µ } D∈D spans M µ .a
Proof. It is clear that any monomial can be associated to a diagram of crosses (by the same process as in paragraph 2.1), and let D be such a diagram which is not a drawing.

We look at the rightmost "anomaly", that is the rightmost place where the diagram D associated to the monomial can not be a drawing (we call this place "guilty").

-Case 1: the diagram D could not be put in a set of ordered columns (i.e., in the shape of a drawing). This case gives four subcases. Assume the guilty column is a y-column. We can not put another y-column on the right. Either because each y-column on the left has a cross (case 1a), or because there is no first plain and white x-column on the right (case 1b). If the guilty column is an x-column, we are led to cases 1c (each x-column on the left has a cross) and 1d (there is no first plain and white y-column on the right). Since the rules are not involved here the problems are symmetric for x or y.

-Case 2: the diagram D could be put in a set of ordered columns but the rules are broken. Either for the white cells (case 2a), or for the crosses (case 2b).

We shall prove, using the propositions of the last section, that the monomial associated to the diagram D can be written modulo I µ as a linear combination of monomials strictly smaller with respect to the lexicographic order (

x 1 < x 2 < • • • < x n < y 1 < • • • < y n ).
We look at each case that we have mentioned above.

• Case 1b with no x-column on the right is solved by Proposition 1, as well as case 1d with no y-column on the right.

• Cases 1a and 1c are symmetric and treated by Proposition 2: we note that the height of the h-th y-column is K -h+ 1. If it has k + 1 crosses, there is a problem if k + h > K. It then can be treated by Proposition 2: we take Y ′ = Y = {i 1 < . . . < i h }, to be the places of the first h y-columns, each of which has at least one cross. The monomial is a multiple of Ȳ

y k i h ≡ Ȳ (y k i h -h k (Y )
) and all monomials in the expansion of the right side are lexicographically smaller than the monomial on the left side.

• Case 2a is immediately settled by inverting the involved columns.

Therefore the only remaining cases are case 1b (resp. 1d) with a first full x-(resp. y-) column on the right and case 2b.

• Let us first study the case 2b.

l k k' y-col. l' x-col. k'' y-columns l'' x-columns
We observe that there is a problem if one has simultaneously:

-k = k ′ + k ′′ + 1, -l = l ′′ + 1,
-there is a cross in each of the l ′ x-columns between the two columns appearing on the figure.

Let:

-Y denote the places on the left of the y-column plus the place of the y-column plus the l ′ places of the x-columns between the yand the x-column on D plus the place of the x-column, -X denote the places on the left of the x-column plus the place of the x-column itself, -X ′ denote the places of the l ′ x-columns between the y-and the x-column of D.

We shall be able to express the monomial corresponding to this D as a linear combination of monomials stricly smaller with respect to the lexicographic order if we establish that

h k (Y )h l (X) ≡ 0.
Indeed the leading monomial of X′ h k (Y )h l (X) (for the lexicographic order), in which we delete the multiples of x i y i for any i, is a divisor of the monomial associated to D.

We want to apply Proposition 4 with

|Y | = n -(k ′ + k ′′ + l ′′ + 1) and |X| = n -(k ′′ + l ′′ + 1
). We have Y ⊂ X and we calculate:

k + l + |Y | -n = 1 > 0.
Hence we are done in this case.

• Let us now consider the case 1d with a first full y-column.

l k k' y-col. k'' y-columns l'' x-columns l' x-col.
Here a problem occurs if:

-k = k ′′ + 1, -l ≥ l ′ + l ′′ + 2,
-there is a cross in each of the k ′ y-columns between the two columns appearing on the figure.

We proceed as in the previous case. We want to use Proposition 4 to show that h k (Y )h l (X) ≡ 0 with Y corresponding to all the places strictly left of the y-column on the diagram D and X corresponding to all the places up to the xcolumn, plus the places of the k ′ y-columns between the x-column and the y-column.

We want to apply Proposition 4 with |X| = n -(l ′ + k ′′ + l ′′ + 2) and |Y | = n -(k ′′ + l ′′ + 1). We have X ⊂ Y and we compute:

k + l + |X| -n ≥ 1.
Thus this case is also settled.

• It remains to observe that the case 1b with a first full x-column is treated by case 2b.

The proof of Theorem 1 is now complete.

Conclusion

We can deduce from what precedes a basis for the ideal I µ when µ is a hook, since the first relations exposed at the beginning of the study of I µ were sufficient to prove that our family is a basis of M µ .

Theorem 2: If we denote by G the ideal generated by a set G, then for µ a hook partition of n, we have:

I µ = h i (X n ), 1 ≤ i ≤ n; h i (Y n ), 1 ≤ i ≤ n; x i y i , 1 ≤ i ≤ n; X, |X| = L + 1; Ȳ , |Y | = K + 1 .
Proof. To prove this we assume that the previous ideal (we denote it by I) is not equal to I µ , so that there is a polynomial P in I µ \I. According to the proof of Theorem 1, we can decompose it as P = A + Q, where A is a linear combination of monomials of our family and Q is an element of I. Taking the derivatives and applying it to ∆ µ , we obtain A(∂)∆ µ = 0. As we shall see in section 4, this implies A = 0, and P = Q ∈ I.

Proof of the independence 4.1 Exposition and reduction of the problem

We shall now prove that our family is an independent set.

Since the derivative operator associated to a drawing D depends only on the crosses and not on the shape of the drawing, we define S as the diagram consisting only of the crosses of D. We also define T as the diagram consisting of the white cells (a "complement" of S).

Let S denote the set of S when D varies in D, the set of drawings defined in section 2.

For example, for the drawing in section 2, we have:

S = T =

Let now ∂ S and ∂ T denote the derivative operators associated to S and T (after putting crosses in all the cells of T ).

Theorem 3:

The family {∂ S .∆ µ } S∈S is an independent set.

Lemma 1:

S or T determines the drawing from which it comes. Proof. Indeed, we can recontruct the shape of the drawing from S by proceeding from left to right. The method is the following: if there are crosses at the place we are looking at, we complete the column with respect to the size of the successive columns. If there is no cross, we look at the x-crosses on the right: if they can fit in with one x-column missing, then we put an x-column at the empty place, else we put a y-column.

The method is the same for T since the family is invariant under flip.

Let us now show that the family is linearly independent. Let us begin with some definitions. Let D = (S, T ) and D 1 = (S 1 , T 1 ) be two different drawings; we shall say that D 1 is a son of D if ∂ T • ∂ S 1 .∆ µ ∈ Z\{0}. We shall denote by T + S 1 the figure corresponding to the superposition (place by place) of the cells of T and S 1 (all these cells being crossed). If we repeat this process, we obtain the notion of descendant.

Lemma 2:

To show the independence, it is sufficient to prove that a drawing can not be its own descendant (i.e., there is no "loop").

Proof. We assume we have a relation of dependence: S c S ∂ S .∆ µ = 0, that the coefficients are not all zero, and that there is no loop. Then we take a S 0 for which c S 0 = 0. If S 0 has no son or if they have all c S equal to zero, we obtain a contradiction by applying ∂ T 0 to the relation and by looking at the constant term of the result. If S 0 has a son S 1 for which c S 1 = 0, we repeat with S 1 . As the set is finite and there is no loop, we certainly obtain a S ′ which gives a contradiction.

So we have to prove that there is no loop. It is sufficient to show that a drawing D = (S, T ) is different from all its descendants that have the same shape (i.e., the x-columns at the same places). Let D ′ = (S ′ , T ′ ) be a descendant of D that has the same shape. We want to show that D = D ′ .

Definition of completeness

To explain this notion, let D 1 denotes a drawing and D 2 one of its sons. We define on the places of D 2 a notion of "completeness" (relative to D 1 too) as follows: We say that the first k places of D 2 are complete if the heights of the y-columns of T 1 + S 2 in these k places and read from left to right are K, K -1, K -2, . . . and if we have the same for x-columns.

We want now to obtain a (more quantitative) characterization of the completeness. To do this we need to introduce some more definitions.

We look at the left parts (made of the first k -1 places) of D 1 and D 2 . We define d as the difference between the number of times where a y-column of D 1 has been replaced in D 2 by a white x-column and the number of times where an x-column of D 1 has been replaced in D 2 by a white y-column. We also define d ′ as the difference between the number of times where a crossed y-column of D 1 has been replaced in D 2 by an x-column and the number of times where a crossed x-column of D 1 has been replaced in D 2 by a y-column. We should note that d and d ′ are relative to k -1.

Since the problem is symmetric with respect to x and y (as long as we do not use the rules of construction), we shall only examine the case where we derive with respect to y k , i.e., where there is a y-column at the k-th place of T 1 + S 2 . The symmetric case has a similar characterization (with opposite signs for d and d ′ ). We now introduce the following notations: b 1 (resp. b 2 ) denotes the number of white cells at place k in D 1 (resp. D 2 ) and c 1 (resp. c 2 ) the number of crosses. The characterization can now be stated as follows:

Characterization :

If the first k -1 places are complete, the k-th is complete if one of the following conditions is verified: Proof. To prove this result, we begin by observing that we can not have x-and y-cells at the same place in T 1 + S 2 : when µ is a hook, we have ∂x i ∂y i ∆ µ = 0. There are in fact three possibilities for the columns at place k:

1. D 1 and D 2 have a y-column; 2. D 1 has a crossed x-column and D 2 a y-column;

3. D 1 has a y-column and D 2 a white x-column.

We deal with these three cases.

1. Case 1: if in T 1 + S 2 the heights of the y-columns in the first k -1 places are K, K -1, . . ., K -l + 1 and if our y-column is the h-th of D 2 , we observe that l = h -1 + d. The height of the y-column of T 1 + S 2 at place k is at most K -l. But if we observe that the height of the h-th y-column of D 2 is K -h + 1, we obtain:

b 1 + c 2 ≤ K -l = K -h + 1 -d = b 2 + c 2 -d. Hence b 2 ≥ b 1 + d and equality holds when it is complete. As b 2 + c 2 = b 1 + c 1 + d + d ′ , the equality c 2 = c 1 + d ′ holds too.
2. Case 2: this case is treated like Case 1.

3. Case 3: the reasoning is similar to Case 1. If our y-column is the h-th of D 1 and if in the first k -1 places of T 1 + S 2 the successive y-columns

have height K, K -1, . . ., K -l + 1, then l = h -1 -d ′ .
As the height of the y-column at place k of T 1 + S 2 is at most K -l, we deduce that c 1 ≥ -d ′ , with equality corresponding to completion.

Remark 2: If the first k -1 places are complete but not the k-th, we observe easily that it corresponds to an increasing of the number of white cells in D 2 . We have indeed seen in the proof that b 2 ≥ b 1 + d and c 2 ≤ c 1 + d ′ in Case 1 and similar inequalities in Cases 2 and 3.

Remark 3: We observe that the Cases 2 and 3 can not happen simultaneously since we can not have at the same place a crossed column in D 1 and a white column in D 2 (there is at least one cell at each place).

Once we have obtained this characterization of completeness, we shall use it to progress in the proof of Theorem 3.

Application Lemma 3:

If we have completeness on the first k places along the chain between two drawings D and D ′ with the same shape, then the sum of the d along the chain is equal to zero, as well as the sum of the d ′ (d and d ′ relative to the first k places).

We will first apply this result in the following lemma and prove it after Lemma 4.

Lemma 4:

If we have completeness on the first k places between D and D ′ , then these two drawings are identical on the first k places.

Proof. To prove this result we shall use Lemma 3. Indeed we notice that if we keep either an x-or a y-column at place k along the chain between D and D ′ , the result is obvious since (by Lemma 3) the sum of the d is equal to zero. With natural notations, we have: b ′ = b + d = b. Now, if the "shape" of the column at place k changes, let us observe the two following cases (by symmetry we look at the changes for a y-column):

1 :

:

1 :

:

(simple arrows mean single generation, broken arrows mean possibly several generations, but at fixed shape at place k).

In view of the characterization of completeness, we observe that we have in both cases: b 2 = b 1 + d, c 2 = c 1 + d ′ , as if we had not changed the shape (it is easily seen by looking at the d on the left and at the d ′ on the right).

By Lemma 3, we are now able to remove the condition that the shape does not change at the broken arrows. Indeed, we begin by reasoning about chains as above, then we can ignore the change of shape. By this method we obtain the general result (analogy with a Dick path for which we repeat the removing of sequences ∨ and ∧).

Proof of Lemma 3. This will be done by induction on k.

• If k = 1, the result is obvious.

• To prove the result for k, we have to show that along the chain between D and D ′ , the shape of the k-th column has changed as many times by appearance of a white x-column as by appearance of a white y-column (i.e., sum of d equal to zero) and as many times by disappearance of a crossed x-column as by disappearance of a crossed y-column (i.e., sum of d ′ equal to zero).

We suppose that our column (assume it is a y-column in D and D ′ ) changes more times by appearance of a white x-column than by appearance of a white y-column. Let us observe the subchain on the figure below: Let h 1 denote the height of the y-column of drawing 1 and h ′ 1 the depth of the first x-column on its right. We observe that b 4 = d 3 ≥ 0 (Case 2 of the Characterization) and that d

2 = h ′ 1 -d 1 -d ′ 1 since b 3 = 0 = b 2 -d 2 (Case 1). Thus: d 1 + d 2 = h ′ 1 -d ′ 1 .
We now visualize the changes of shape at place k between D and D ′ on the following representation. The even coordinates correspond to a y-column at place k, the odd ones to an x-column. A north-east line is either the appearance of a white x-column or disappearance of a crossed x-column (according to odd or even coordinate) and a south-east line is either the appearance of a white y-column or disappearance of a crossed y-column. The vertical dotted lines are defined as follows. The first is placed at the last point for which the coordinate is equal to zero. Then we have clearly two north-east lines and we put another dotted line. Then we restart with taking coordinate 2 as a new zero for the coordinates.

Let us suppose that between D and D ′ there is a single ascent (i.e., a subchain like 1-2-3-4). If we verify that • a y-column: we first show that in each x-column of T 1 + S 2 there is at least one cell coming from D 1 and one coming from D 2 . This is absurd since there are not enough x-columns.

d 0 + d 1 + d 2 > 0,

Enumeration

We verify that the number of drawings introduced in subsection 1 is n!/µ!.

We consider the drawing from the left to the right. The bar we are looking at corresponds to a corner of the Ferrers diagram of the partition from which we have removed the cells corresponding to the bars on the left. Number the cells of the partition µ by writing i in the cell associated to the bar at place n -i + 1 in the drawing. By the preceding paragraph, this gives a standard tableau.

We now look at the following figures:

i i x x
We observe that the number of choices for cell i is the length of the arrow that we denote by coarm * i (T i+1 ), where T i+1 is the (standard) tableau T from which we have removed the cells numbered from i + 1 to n.

We thus obtain that the cardinality is:

(1)

T standard 1 i=n coarm * i (T i+1 ).

We show that this number equals n!/µ ′ ! by induction on n. The result is obvious when n = 1. We write µ ′ = (c α 1 1 , . . . , c α h h ), where the c j 's are the height of columns of µ and α j their multiplicities. In particular, µ has h corners, µ ′ ! = h i=j (c j !) α j , n = h j=1 α j c j and α j is the contribution of corner j in the product of (1). We then rewrite this formula as:

h j=1 α j . T ′ 1 i=n-1 coarm * i (T ′i+1 )
where T ′ varies amongst every standard tableaux of the Ferrers diagram from which we have removed its j-th corner (let µ j denote the corresponding

1 mally

 1 we may writeM µ = L{∂ a x ∂ b y ∆ µ (x, y); a, b ∈ N n } where ∂ a x = ∂ a 1 x 1 . . . ∂ an xn and ∂ b y = ∂ b 1 y 1 . . . ∂ bn yn .Then the n! conjecture can be stated as follows. Conjecture 1 (n! conjecture): Let µ be a partition of n, then dim M µ = n!.

1 .

 1 at place k in D 1 and D 2 there is a y-column and b 2 = b 1 + d and c 2 = c 1 + d ′ (each of these equalities easily implies the other); 2. at place k, there is a crossed x-column in D 1 (i.e., b 1 = 0) and a y-column in D 2 , and b 2 = d; 3. at place k, there is a y-column in D 1 and a white x-column in D 2 (c 2 = 0), and c 1 = -d ′ .

a

  where d 0 is the sum of the d before the ascent, then since d = 0 between D and D ′ , we have necesseraly some d < 0 after this sequence, which is impossible without a disappearance of the crossed y-column. That is what we wanted to show. Let us prove that d 0 + d 1 + d 2 > 0. Let b denote the number of white cells at place k of D then b 1 = b + d 0 . The following remark allows us to divide by two the number of cases: Remark 4: D 2 is a son of D 1 if and only if flip(D 1 ) is a son of flip(D 2 ). This allows us to only consider cases 2 and 4. If at place "a"(corresponding to the first plain crossed x-column in D 2 ), there is • an x-column: we first verify that at each place on the left of "a" we have d = 0; then we show that the x-column in D 1 is smaller than the one in D 2 , which contradicts b 2 = b 1 -d = b 1 .

Acknowledgements

The author would like to express all his gratitude to the referees who have made significant efforts to improve this paper by their valuable advices and suggestions.

Hence:

It is easy to check that h 1 + h ′ 1 -b > 0. It remains to observe that when there are several ascents, the previous reasoning is still true, by looking at the last one. Indeed, it suffices to replace the equality b 1 = b + d 0 by b 1 ≤ b + d 0 (thanks to what precedes), which keeps the result unchanged.

The proof of Lemma 3 is almost complete. It remains to observe that the symmetries between x and y and between crossed and white cells allow us to deal with the other cases.

Lemma 5 :

If there is no total completeness along the chain between D and D ′ , then D = D ′ which implies Theorem 3.

Proof. This is an easy consequence of Lemmas 2 and 4 and Remark 2. It suffices to look at the leftmost place for which the completeness fails: D ′ has more white cells (and less crosses) than D at this place.

End of the proof

It is now sufficient to show that there is at least one generation between D and D ′ that is not complete. We shall in fact show that each generation is not complete.

Let again D 1 = (S 1 , T 1 ) and D 2 = (S 2 , T 2 ) denote two different drawings, father and son.

If D 1 and D 2 have the same shape, the result is obvious.

It then remains to study the case where D 1 and D 2 have different shape. We suppose that completeness holds and reduce it to the absurd. By looking at the place at most on the left where the shape changes, we can consider only the case where the shape changes at place 1. The only changes for which the non-completeness is not obvious are the following (remark that here d = d ′ = 0):

Case 4:

D2= D1=

In this case, if the first plain x-column of D 1 is the l-th x-column of D 1 , we begin by observing that the x-column on its left have at least one white cell, hence have a contribution to T 1 + S 2 . Thus on the left of this place there is already an x-column of depth L -l + 1 (there are at least l x-columns in T 1 + S 2 on the left). This is absurd.

5 Elements of 0 x-degree

Description

be any partition of n. The goal of this section is to give an explicit basis for M 0 µ , which denotes the homogeneous subspace of M µ of elements of 0 x-degree. We construct this basis with the same visual objects as in the case of hooks. We also obtain a basis for the subspace of n(µ) x-degree which we shall denote by M n(µ) µ . The space M 0 µ has already been studied in [START_REF] Bergeron | On certain spaces of harmonic polynomials[END_REF] and [START_REF] Garsia | Some natural bigraded S n -modules and q, t-Kostka coefficients[END_REF]. In particular it is proved that its dimension is n!/µ ′ !, where µ! = µ 1 ! . . . µ k ! and µ ′ is the conjugate of µ. In fact our basis is related to a family introduced in [START_REF] Bergeron | On certain spaces of harmonic polynomials[END_REF]. But we obtain here a direct (and not recursive) method of construction. Moreover we apply the monomial derivatives to ∆ µ itself and therefore obtain a simple and explicit basis for M 0 µ . partition). We are now able to conclude, since µ ′j ! = µ ′ !/c j :

Independence and conclusion

As in the case of the hook-shaped partitions, we denote by S (respectively T ) the diagram consisting only of the crosses (respectively of the white cells) of a given drawing. For example in the case of the drawing of subsection 5.1, we have:

S= T=

Let now ∂ S and ∂ T denote the derivative operators associated to S and T . Let also S and T denote the set of all S's and T 's constructed by this way. We also associate to S and T a monomial by the same way. For example, in the case of the previous figures, we have: M S = x 2 y 2 x 4 3 x 3 4 x 6 x 2 7 x 8 and M T = y 3 1 y 2 y 2 5 y 6 y 9 . Theorem 4:

The set {∂ S ∆ µ } S∈S is linearly independent and hence is a basis of M 0 µ . The set {∂ T ∆ µ } T ∈T is linearly independent and hence is a basis of M n(µ) µ .

The theorem is a consequence of the two following lemmas.

Lemma 6:

We can reconstruct the drawing from S or T .

Lemma 7:

For the lexicographic order (

Proof. The proof of Lemma 6 is easy: we reconstruct the drawing from the left to the right, as in the case of hooks, thanks to the rules.

The proof of Lemma 7 requires attention only in the case of T , so we develop this point. Once the crossed cells have been fixed, we have to show that the white cells are at most on the left. It suffices in fact to show that the x-white cells can not be moved to the left. We show it by looking at the drawing from the left to the right. Let k and l denote the number of x-cells and of y-crossed cells at place p. We have to prove that a bar with l ′ > l x-cells and k ′ ≥ k y-crossed cells is forbidden at place p. If the couple (k ′ , l ′ ) is not a biexponent of the partition or if it is present on the left, we are done. To conclude we observe that this couple can not be a biexponent of the partition appearing on the right of the initial drawing. Indeed, because of the rules we should have: k > k ′ . Remark 6: It is possible to show that our family of monomials {M S } S∈S is equal to the family B µ of [START_REF] Bergeron | On certain spaces of harmonic polynomials[END_REF], section 4. But whereas B µ was constructed recursively, our construction is direct. Moreover we apply it directly to ∆ µ and obtain simple and explicit bases for M 0 µ and M n(µ) µ , whereas N. Bergeron and A. Garsia were dealing in [START_REF] Bergeron | On certain spaces of harmonic polynomials[END_REF] with linear translates of Garnir polynomials.


Isabelle Santos
email: isabelle.santos@enac.fr

Stéphane Puechmorel
email: stephane.puechmorel@enac.fr

Guillaume Dufour
email: guillaume.dufour@onera.fr

First Order Hadamard Variation of the Harmonic Navigation Function on a Sphere World

Keywords: Navigation Function, Hadamard Formula, Trajectory Planning, Air Traffic Control

Planning conflict-free trajectories is a long-standing problem in Air Traffic Management.

Navigation functions designed specifically to produce flyable trajectories have been previously considered, but lack the robustness to uncertain weather conditions needed for use in an operational context. These uncertainties can be taken into account be modifying the boundary of the domain on which the navigation function is computed. In the following work, we present a method for efficiently taking into account boundary variations, using the Hadamard variation.

Introduction

The aviation industry currently faces meaningful challenges to overcome the increasing traffic across the world. Safety solutions are a demand in all flight phases in order to cope with traffic capacity, all-weather conditions and efficiency. In order to address the 5% per year increase in air traffic, the Single European Sky ATM Research (SESAR) program in Europe and the NextGen program in the USA have been initiated to design new rules and tools for future air traffic management (ATM).

Each flight phase has specific operational constraints. Of interest here is the en-route flight phase. This phase is comprised from completion of initial climb through cruise altitude and completion of controlled descent to the initial approach fix. En-route air traffic is currently managed by subdividing airspace into sectors and air routes. In each sector, a team of air traffic controllers supervises the transiting aircraft and prevents conflicts by deviating some aircraft from their planned route. Each team communicates with the teams responsible for neighbouring sectors to transfer aircraft flying through several sectors.

As traffic grows, the workload in a sector may exceed air traffic controller capabilities. In this case, the sector is subdivided into smaller sectors, thus lowering the number of aircraft under the responsibility of an air traffic controller at any given time. However, this increases the time spent transferring aircraft between sectors up to the point where coordinating between sectors takes precedence over separating aircraft and solving conflicts. The SESAR program overcomes this pitfall by delegating most of the separation task to the aircraft themselves, thus inducing a higher level of automation. In this context, fixed air routes will no longer be necessary and trajectories will be planned in 4D in such a way that conflicts are avoided by design.

A major challenge associated with aircraft trajectory planning, in addition to operational constraints and flight dynamics, is the influence of wind. Much research has been conducted to plan such routes several days in advance. However, no algorithm is known to produce planning such that the resulting aircraft trajectories be robust to uncertain head-or tailwind. Artificial potential fields, as first used by [START_REF] Khatib | Real-time obstacle avoidance for manipulators and mobile robots[END_REF], enable a mobile to reach a destination while avoiding obstacles in a complex environment. This method has been extended to dynamic environments, with multiple mobile trajectory planning as in [START_REF] Hun | Decentralized control of autonomous swarm systems using artificial potential functions: Analytical design guidelines[END_REF], coordinating between mobiles in [START_REF] Zeghal | Vers une théorie de la coordination d'actions. Application à la navigation aérienne[END_REF] and moving obstacles in [START_REF] Sam | Dynamic motion planning for mobile robots using potential field method[END_REF]. Navigation functions, a specific case of artificial potential fields, introduced originally for robots trajectory planning by [START_REF] Dimos V Dimarogonas | Totally distributed motion control of sphere world multi-agent systems using decentralized navigation functions[END_REF] and [START_REF] Rimon | Exact robot navigation using artificial potential functions[END_REF], were extended to generate aircraft trajectories. Such trajectories meet ATM restrictions on speed and curvature. Furthermore, a proof of conflict avoidance can be obtained. Navigation functions have also been used to plan trajectories under a wind constraint in [START_REF] Pêtrès | Reactive path planning for autonomous sailboat[END_REF] for sailboat navigation. Recent developments in navigation functions also include their application to the case of real-time spacecraft guidance [START_REF] Romano | Near-optimal real-time spacecraft guidance and control using harmonic potential functions and a modified rrt[END_REF], or in uncertain environments [START_REF] Shlomi Hacohen | Applying probability navigation function in dynamic uncertain environments[END_REF]. However, the navigation function works under the assumption that aircraft or other mobiles move in a deterministic way. We present in this paper a method to account for time uncertainty in aircraft trajectory planning. To account for this uncertainty, we consider the variation of the navigation function with respect to variations of the boundary of the configuration space. Of interest in this paper is the practical construction of Hadamard's variational formula, as presented in [START_REF] Hadamard | Leçons sur le calcul des variations[END_REF] for the Green's function of the Laplace equation on a 2-dimensional sphere world.

The purpose of this paper is to present a method for computing the Hadamard variational formula given a specific domain perturbation. This variational formula requires knowledge of the Green's function on the initial domain. Numerical evaluations of the Green's function for certain problems, such as the Helmholtz operator on periodic structures [START_REF] Kirk E Jordan | An efficient numerical evaluation of the green's function for the helmholtz operator on periodic structures[END_REF], heat diffusion in 1D [START_REF] Vere | Heat conduction using Green's functions[END_REF], the elliptic problem [START_REF] Bertoluzza | Local error estimates of the finite element method for an elliptic problem with a dirac source term[END_REF], or the exterior Neumann problem [START_REF] Ma Sadybekov | Representation of the green's function of the exterior neumann problem for the laplace operator[END_REF].

An analytical expression of the Green's function for Laplace's equation has also been obtained in multiply connected domaines [START_REF] Crowdy | Green's functions for laplace's equation in multiply connected domains[END_REF]. However, this formulation is difficult to implement in practice, as it relies on the Schottky-Klein prime function [START_REF] Dg Crowdy | The schottky-klein prime function: a theoretical and computational tool for applications[END_REF].

The motivation for this paper is from designing schemes to plan trajectories for multiple mobiles under uncertainty using harmonic navigation functions.

After a state of the art on navigation functions in section 2.1, section 2.2 presents a method for numerically computing the Green's function of the Laplacian operator, and section 2.3 applies this method to the computation of the variation of the navigation function with respect to the domain boundary variation. The methods are illustrated and the results for this method are exhibited in section 3. Finally, future work is outlined in section 4.

Materials and Methods

Navigation functions

Navigation functions on an arbitrary sphere world were introduced by Rimon and Koditschek [START_REF] Daniel | Robot navigation functions on manifolds with boundary[END_REF] in the context of robot navigation for generating trajectories that present a guarantee of obstacle avoidance. Navigation function are a family of potential functions, with their maximum on the boundary of the obstacles, their minimum at the destination and no interior local minimum or maximum. Formally, navigation functions are defined as follows:

Definition 1. A map ϕ : E n → [0, 1] is a navigation function on a compact connected smooth manifold F ⊂ E n if it is:
1. Analytic on the interior of F 2. Polar on F with a minimum at an interior point q d ∈ •F 3. Admissible on F

Morse on Ω

Once the navigation function is computed, robot trajectories are determined by following -∇ f at non critical points or the steepest descent given by the Hessian at critical points. The trajectories hereby obtained reach the destination while avoiding obstacles.

Navigation functions have been extended to aircraft trajectory planning [START_REF] Giannis P Roussos | 3d navigation and collision avoidance for a non-holonomic vehicle[END_REF], taking into account ATM considerations such as limits on speed and curvature, as aircraft can only fly at [-3%, +6%] of their nominal speed [START_REF] Delgado | Fuel consumption assessment for speed variation concepts during the cruise phase[END_REF].

Of present interest are harmonic navigation functions on a manifold of R 2 with non-overlapping spherical boundaries. Such a domain is referred to as a sphere world. Let D be a sphere world as described and z d the destination point in the interior of D.

Consider the Dirichlet problem ∆φ = 0 on the interior of D

φ(z) = c ∈ R * + , z ∈ ∂D φ(z d ) = 0 (1)
where

∆ = ∂ 2 ∂x 2 + ∂ 2 ∂y 2 (2)
is the Laplacian operator in 2 dimensions. As stated in [START_REF] Rimon | Exact robot navigation using cost functions: the case of distinct spherical boundaries in e/sup n[END_REF], the function φ on L 2 (D) defined by this problem is a navigation function. Indeed, no interior point can be a local extrema so that φ is polar. φ is admissible by construction and is Morse on D However, navigation functions work under the assumption that trajectories are deterministic.

The kind of trajectory obtained by this method is not robust against uncertainties, and thus phenomenon such as wind may cause the separation norms to be violated. This prevents navigation functions from being deployed in an operational context. The purpose of this work is to provide tools for extending navigation functions to the case of aircraft trajectories under a wind uncertainty.

In the following sections, we will introduce the Green's function and a numerical method to obtain it on sphere worlds, and its application to navigation function under a domain boundary uncertainty.

2.2.

Semi-analytical approximation of the Green's function for the Laplacian operator

Green's function

Let Ω ∈ R 2 be a planar bounded domain with the boundary ∂Ω = i C i such that C i be non intersecting circles and C 1 be exterior to all other circles, as illustrated in Figure 1. The centers of circles C i are noted c i and the radii r i . In this configuration, ∂Ω is Lipschitz-continuous and Ω is a Lipschitz domain.

Let us consider the equation

-∆u = f on Ω, u = 0 on ∂Ω (3)
where f ∈ L 2 (Ω) is a given function. If the domain boundary ∂Ω is sufficiently smooth, then Equation

3 admits a unique solution u ∈ H 1 0 (Ω). The Green's function, noted G : (x, y) ∈ Ω × Ω → R is the solution of -∆u = δ s on Ω, u = 0 on ∂Ω (4)
where δ s is the Dirac distribution centered in s ∈ Ω. Contrary to Equation 3, the right hand term in Equation 4 is not L 2 . However, the L p -integrability of the Green's function for elliptical equations on Lipschitz domains is given by [START_REF] Maeda | The integrability of superharmonic functions on lipschitz domains[END_REF]. Furthermore, as presented in [START_REF] Nevanlinna | Analytic functions[END_REF], it follows from Equation 4that the solution u to Equation 3 has the form

u(x) = ∂Ω u(y) ∂G ∂n (x, y) dy (5)

Green's function from conformal mappings

Definition 2. Let Ω ⊂ C be a domain. A fundamental solution of the Laplace equation is a mapping

G : : ω × Ω → R such that z → G(z, z 0 ) is harmonic in Ω -z 0 for any z 0 ∈ Ω and: lim z→z 0 G(z, z 0 ) = +∞
A representation theorem for such a G is given in [START_REF] Henrici | Applied and computational complex analysis[END_REF]:

Theorem 3.
Let G be a fundamental solution of Laplace equation in a domain Ω. Then it exists a function h : Ω × Ω → R, harmonic in its first argument, and a real constant λ > 0 such that for any (z,

z 0 ) ∈ Ω × Ω, z = z 0 : G(z, z 0 ) = λ log 1 |z -z 0 | + h(z, z 0 )
For a given λ, h, hence G, is uniquely defined by its values at the boundary ∂Ω. The special choice λ = 1/2π and vanishing boundary conditions yields the so-called Green's function of the Laplace equation. It can be obtained by solving for h the system:

∆ z h = δ z 0 (6) h(z, z 0 ) = -1 2π log 1 |z-z 0 | , z ∈ ∂Ω (7)
Theorem 4. Let G be Green's function for the Laplace equation in the domain Ω. The following relation holds in the distributional sense for any z 0 ∈ Ω:

∆ z G(., z 0 ) = δ z 0
Proof. Using the standard operators ∂, ∂, it comes: ∆ z G(., z 0 ) = 4∂∂G(., z 0 ). For an arbitrary function φ holomorphic in Ω, continuous on ∂Ω:

d (∂G(., z 0 )φ) = ∂∂G(., z 0 )dz ∧ dz + ∂G(., z 0 )∂φdz ∧ dz (8) = -∂∂G(., z 0 )dz ∧ dz = -1 4 ∆G(., z 0 )φ (9)
By Stokes theorem:

Ω ∆G(z, z 0 )φ(z)dz ∧ dz = -4 ∂Ω ∂G(z, z 0 )φ(z)dz (10)
Since dx ∧ dy = -2idz ∧ dz, the equation 10 yields:

Ω ∆G(z, z 0 )φ(z)dx ∧ dy = 2 i ∂Ω ∂G(z, z 0 )φ(z)dz (11)
and finally using the relation:

∂ log |z -z 0 | = 1 2(z -z 0 )
the right hand side term equals:

1 i2π ∂Ω φ(z) z -z 0 dz = φ(z 0 )
Using the system defining h to obtain an approximate solution is not an easy task from a numerical point of view as it requires solving a Laplace equation that becomes increasingly ill-conditioned as z 0 approaches the boundary of the domain. This is mainly due to the fact that the singularity lies within the domain of interest.

In order to transform this inconvenient geometry into a more convenient one, we choose a conformal mapping that eliminates the singularity at z 0 .

Consider the following conformal mapping

T z 0 : z → 1 z -z 0 (12)
Provided that z 0 is interior to Ω, the map of Ω by T z 0 noted Ω T , as illustrated in Figure 2, is the unbounded region exterior to a set of non-overlapping circles of center c T j and of radii r T j defined by

c T j = c j -z 0 |c j -z 0 | 2 -r 2 j (13) r T j = r j |c j -z 0 | 2 -r 2 j ( 14
) Let H = G(•, z 0 ) • T z 0 : z → G(T z 0 (z), z 0 )
. Given that T z 0 is a conformal mapping, H is the harmonic solution exterior to non-overlapping disks that vanishes on the disk boundaries and such that H(z) ∼ log |z| as |z| → ∞. Furthermore, contrary to G(•, z 0 ), function H has no singularity on its domain. Function G(•, z 0 ) can then be determined given the knowledge of function

H G(•, z 0 ) = H • T -1 z 0 (15)
In the following subsection we present a method for approximating H

Harmonic function exterior to non-overlapping disks

We seek a function H on domain Ω T as defined prior. We use the following Laurent expansion [START_REF] Steven | Handbook of complex variables[END_REF] for

H H : z → α + J ∑ j=1 β j log |z -c T j | + J ∑ j=1 ∞ ∑ k=1 (γ jk -iδ jk )(z -c T j ) -k (16) c 1 c 3 c 2 z 0 T z 0 c T 1 c T 3 c T 2 Ω Ω T Figure 2.
Mapping of the sphere world Ω by T z 0 . Ω T is the space exterior to three circles.

with

J ∑ j=1 β j = 1 ( 17
)
and where α, β j , γ jk and δ jk are scalars to be determined. This function is harmonic with H(z) ∼ log |z| as |z| → ∞ and vanishing values on the boundary of Ω T .

This series ∑ ∞ k=1 (γ jkiδ jk )(zc T j ) -k can be approximated by its N first terms. Thus we consider the approximation h of function

H h : z → α + J ∑ j=1 β j log |z -c T j | + J ∑ j=1 N-1 ∑ k=1 (γ jk -iδ jk )(z -c T j ) -k (18)
The Green's function G(•, z 0 ) can then be approximated by the function g = h • T -1 z 0 . This function g has the additional benefit of being easily derived to any order as it is the composition of standard functions. Given Equation 18 the derivatives of h are ∀z ∈ ΩT , ∂h ∂x

(z) = J ∑ j=1 β j x -x j |z -c T j | 2 - J ∑ j=1 N-1 ∑ k=1 k(γ jk -iδ jk )(z -c T j ) -k-1 ∂h ∂y (z) = J ∑ j=1 β j y -y j |z -c T j | 2 + J ∑ j=1 N-1 ∑ k=1 k(γ jk -iδ jk )(z -c T j ) -k-1 (19)
The derivatives of g are thus obtained by combining Equations 19, 15 and 12. Once the coefficients for h are determined, these derivatives come for free, as no additional coefficients need to be computed.

This property is of interest to us for the purpose of the Hadamard variation covered in section 2.3 as the normal derivatives on the domain boundary are required.

The values of coefficients of the expansion of h are obtained by a numerical method derived from that of [START_REF] Lloyd N Trefethen | Ten digit algorithms[END_REF], using collocation points equally spaced on the set of boundary circles, to approach the coefficients of 18 given a domain Ω. A least squares method can be used to set the boundary conditions. To ensure that the vanishing condition on the boundary is satisfied, a number n of collocation points denoted by z i , i ∈ [ [1, n]] are set on each circle. Values for the coefficients are chosen by minimizing the sum of squares of h(z i ). Finding the coefficients of h is then equivalent to solving the optimization problem min ||AX|| 2 s.t. v T X = 1 [START_REF] Needham | Visual complex analysis[END_REF] where X and v are two vectors of length (1

+ J + 2N J) X = α, β 1 , . . . β J , γ 11 , δ 11 , . . . δ JN (21) v = 0 1 . . . 1 ←---→ J 0 . . . . . . 0 ←---------→ 2N J ( 22
)
and A is an n by (1 + J + 2N J) matrix.

129

The problem set in Equation 20 can be turned into a set of linear equations by using Lagrange multipliers [START_REF] Louis | Mécanique analytique[END_REF]. Given enough collocation points, this problem has a unique solution X as defined in Equation 21, from which we obtain the approximation h from Equation 18of the harmonic function on Ω T and the approximation g of the Green's function, with function g defined for a fixed point z 0 as

g = h • T -1 z 0 (23)

First order variation of the harmonic solution

The purpose of this section is to present the main results relating the behavior of the solution of an elliptic problem with Dirichlet boundary conditions to the variation of its border. Let (M, g) be a connected orientable smooth Riemannian manifold of dimension d and let γ i , i = 1 . . . N be a finite set of disjoint embedded smooth submanifolds of dimension d -1 that partition M into two disjoint components M + , M -that are manifolds of dimension d with common boundary γ = ∪ i=1...N γ i . M + is assumed to be relatively compact. Finally, let X be a smooth vector field on M with flow φ(t, x) that is transversal to γ (except perhaps at a finite number of points). The flow of X will be denoted by φ : ] -, [×M → M, with as usual ∂ t φ(0, x) = X(x). For a fixed t, φ t will denote the function φ t : x → φ(t, x). The flow φ will model an admissible deformation of the manifold with boundary M + ∪ γ. Following [START_REF] Peetre | On Hadamard's variational formula[END_REF], the deformed boundary at t ∈] -, [ will be defined as γ t = φ (t, γ). and the perturbed problem as:

∆u t = 0 in φ( t, M + (24)
u t | γ t = f t (25)
Since the primary goal is to obtain a formula for the Green's function variation, the problem stated in Equation 24 will be reformulated to accommodate a distribution in the right hand term of Equation 24. Likewise, boundary condition 25 will be simplified later to u t | γ t = 0. The final problem in distributional form is then:

M + t ∆u t vω = T(v) u| γ t = f t (26)
where ω is the riemanian volume form and T is the right hand term distribution. Recalling that ∆u t = div∇u t , it comes:

M + t ∆u t vω = M + t vd(i ∇u t ω) = - M + t g (∇u t , ∇v) ω + γ t v∇u t | N σ (27)
where the subscript N denotes the component of the vector normal to γ and σ = i N ω, with N the normal vector to γ. Any test function v is the image by φ * t of a test function φ -1 * t v. The perturbed problem 27 can thus be rewritten so as to involve only integrals on M + :

- M + φ * t g (∇u t , ∇v) φ * t ω + γ φ * t vφ * t ∇u t | N φ * t σ = φ * t T(v) φ * t v ∈ D (M) (28)
Taking the derivative of the first integral in the left hand side of 28 with respect to t at t = 0 yields:

M + X (g (∇u, ∇v)) ω + M + g (∇ u, ∇v) ω + M + g (∇u, ∇v) div Xω v ∈ D (M) (29)
By Cartan's formula, div(X)ω = d(i X ω), thus:

M + g (∇u, ∇v) div Xω = M + d (g (∇u, ∇v) i X ω) - M + d (g (∇u, ∇v)) ∧ i X ω = γ g (∇u, ∇v) X N σ - M + X (g (∇u, ∇v)) ω (30)
Putting it in 29, the derivative becomes:

M + g (∇ u, ∇v) ω - γ g (∇u, ∇v) X N σ (31)
The derivative with respect to t at t = 0 of the boundary term:

γ t v∇u t | N σ = γ φ * t v∇φ * t |Nφ * t σ
can be expressed as:

γ v∇ u| N -X (v∇u| N ) σ (32)
with the boundary condition u| γ = 0, the first term vanishes. However, it will be kept in the sequel to obtain a more general variation formula. Gathering things together yields:

- M + g (∇ u, ∇v) ω + γ g (∇u, ∇v) X N σ + γ v∇ u| N - ∂v ∂N ∇u| N X N σ (33)
Considering the problem:

M + u∆ Gx ω = δ x ∇v| γ = 0 (34)
and putting back its solution as v in 33 and using:

M + u∆ω = - M + g (∇ u, ∇v) ω
gives for the derivative of the solution:

u = γ Gx ∇ u| N σ - γ ∂ Gx ∂N ∇u | NX N σ (35)
Finally, if u is taken to be the green function of the original problem, the well known Hadamard formula is obtained [START_REF] Suzuki | First and second hadamard variational formulae of the green function for general domain perturbations[END_REF]:

δG(x, y) = ∂Ω ∂G ∂n (w, x) ∂G ∂n (w, y)X N σ (36)

Results and Discussion

Numerical validation of the Green's function approximation

In this section, we discuss the results obtained by implementing the above method and verify that the resulting functions present certain expected properties. We also justify the decisions regarding the choice of parameters for Equation 18in the light of the relative error and the computation time. We finally discuss the relevance of this method for the application at hand, namely computing navigation functions.

Python 2.7 was used to implement the method described in section 2.2 on an office computer with an Intel Core i7-4710MQ CPU , 2.50GHz, 8 cores.

Convergence of the method

Reconstruction of the harmonic solution for constant boundary conditions

Given the Green's function G on a domain Ω × Ω, the harmonic solution can be found for any Dirichlet boundary conditions from Equation 5. In particular, one important property of the Green function is that if the function u in Equation 5 is constant and equal to 1, then we find that for any x ∈ Ω ∂Ω ∂G ∂n (x, y) dy = 1 (37)

We build function g to estimate the Green's function as defined in Equation 23 on a domain featuring two inner circle boundaries of centers 2i and -1 -2i and of radii 1. and 0.5 respectively, and bounded by an outer circle of radius 5. centered at the origin. We then evaluate the quality of the estimation by comparing the integral of its normal derivative to 1 :

ε = 1 - ∂Ω ∂g ∂n (x, y) dy ( 38
)
The integral is computed using the quad function from the scipy Python library [START_REF] Jones | SciPy: Open source scientific tools for Python[END_REF], and based on a technique from the Fortran library QUADPACK.

In Figure 3 is a measure of the quality of the estimation from Equation 37, given by the logarithm of ε, relative to the number of collocation points at a given point x = -2 interior to the domain and for a given number of terms in the Laurent expansion N = 2, N = 5 or N = 10. Overall, this value follows a decreasing curve, thus the distance decreases as the number of collocation points increases.

There is a steep increase of the curve for values of n c around 2N. For higher fixed values of N, the curve starts at a higher point, and converges for higher values of n c , but in either case, the distance from ∂Ω ∂g ∂n (x, y) dy to 1 plateau around 10 -14 for n c > 2N.

This indicates that the obtained values are constrained by round-off errors.

There is no improvement for n c > 2N, since the problem is over-constrained, as can be seen in the linear problem stated in Equation 20, where 1 + J + 2(N -1)J coefficients are to be determined from Jn c equations.

In the following section, we will further evaluate the quality of the approximation of the Green's function derived from our method by integrating over the domain boundary to find the harmonic solution for non-constant boundary conditions, similar to those of the foreseen application of our method.

Reconstruction for non-constant boundary conditions

On certain sphere worlds, an analytical solution can be found to Equation 3. Here, we consider the crown defined by the unit circle as an outer boundary, and the circle of center 2/5 and of radius 2/5 as an inner boundary as pictured in Figure 4.

For a domain bounded by two concentric circles, with constant Dirichlet conditions on each circle, the harmonic solution to this problem is a function of the form z → A + B log z with constants A and B chosen to fit the boundary condition. A Möbius mapping [START_REF] Needham | Visual complex analysis[END_REF] can be found that transforms this symmetrical problem into that described in Figure 4. From here, and given Dirichlet boundary conditions such that the value on the inner boundary be constant equal to scalar a ∈ R and the value on the outer boundary be constant equal to b ∈ R, then the harmonic potential on this domain is function

u e : z → b -a log 2 log 2z -1 z -2 + b (39)
We can thus compare the solution reconstructed with the Green's function as described in Equation 5, noted u g

1 = ||u e -u g || 1 ≈ 1 n n ∑ i=1 |u e (z i ) -u g (z i )| (40)
The z i in this equation are placed on a fine enough Cartesian grid, such that the result has converged.

In Figure 5a, the logarithm of the distance between both solutions is presented. As the number of terms used in the Laurent series increases, the difference 1 decreases for high numbers of collocation points. As discussed previously, the error converges for values of n c greater than 2N. As such, as the number of terms N in the Laurent expansion increases, the error 1 converges for larger numbers n c of collocation points, but converges towards a lower value.

In Figure 5b, log 1 is represented for the comparison between the analytical solution and that obtained with the finite elements method using Lagrange elements of order 2. Here, we observe that the error for the solution computed with the Green's function is comparable to that for the finite elements method.

Although we compare the results obtained using the reconstruction from the Green's function to those of the finite element method, it is to be noted that reconstructing the harmonic solution from the Green's function is more time-consuming than solving the finite elements problem, as the Green's function simultaneously gives the harmonic solution for all boundary conditions. As such, our method is not appropriate for solving single navigation functions. However, in the context of solving boundary variation problems, the hereby presented method computing the Green's function is superior. We further illustrate this in the following paragraphs by exhibiting the time complexity.

Time complexity

In this section, we consider the execution time to compute the approximation of the Green's function at one point, noted g in section 2.2. We normalize the resulting times relative to the execution time in the test case where N = 2 and n c = 2. The results are presented in Figure 6 for different values of N and of n c .

As can be seen in Figure 6, the time required to compute the Green's function rapidly increases as the number of terms in the Laurent expansion increases. However, as seen in sections 3.1.1 and 3.1.1, the solution rapidly converges and good results can be obtained with small values of N.

The order of magnitude for the base case in our configuration, with n c = 2 and N = 2, is a millisecond. This relatively small amount of time must be put in perspective with the fact that the approximation g of the Green's function may be computed hundreds of times for different points of the domain in order to estimate the value of the harmonic solution in one point.

In the following section, we will present a practical example of our method, relevant to the application at hand. In each of the Laurent expansion, ten terms are used. Thirty collocation points are set on the domain boundaries at regular intervals.

Sphere worlds with more obstacles can be tackled with no additional difficulty.

Computing navigation functions

In order to demonstrate the usability of our method in the context of aircraft trajectory planning, we have carried out the computation of navigation functions with the Green's function and traced some resulting trajectories. These are exhibited in Figure 8. The domain is defined with dimensions similar to those found in operational contexts. The outer boundary, figuring the limit of the airspace is 100NM in diameter ; the obstacle discs, representing the other aircraft are 5NM in diameter. The destination is near the center of the domain.

The trajectories are plotted using a gradient descent method [START_REF] Fletcher | Practical methods of optimization[END_REF] with a constant step. We find that the generated trajectories all converge towards the destination, while avoiding all obstacles with a wide margin, as is illustrated in Figure 8.

Numerical validation of the Hadamard variation of the Green's function

In the present section, we will exhibit the results obtained with the aforementioned method for variations of the domain boundary. We consider here a sphere world Ω bounded by one destination disc (c 0 , r 0 ), one obstacle disc (c 1 , r 1 ) and an outer boundary disc (c 2 , r 2 ), such as the one presented in Figure 7. We hereby study two manners of disturbing the domain boundary

• by varying the center of the obstacle disc,

• and by varying the radius of the obstacle disc. where n(w) is the normal vector to the domain boundary at point w ∈ ∂Ω. For a pure translation of the disc, the term δr is null. For a pure variation of the obstacle disc radius, the term δc is null.

In practice, for determining aircraft trajectories, only the center of the obstacle disc is submitted to uncertainty, since the radius obstacle disc is defined by the aircraft separation norms.

In the following paragraphs, we will consider the variation of the Green's function for small variations of the obstacle radius.

We first introduce notations. Let G : Ω × Ω be the Green's function computed at each η ∈ Ω from Equation 23. Given the study of parameters in section 3.1, the values of N and n c in computing the Green's function are set respectively to 10 and 30. δG denotes the variation of the Green's function as defined in Equation 36 and the Green's function estimated using the Hadamard variation is noted G = G + δG. The Green's function on the perturbed domain Ω * is noted G * : Ω * × Ω * and is similarly computed at each η ∈ Ω * from Equation 23. Finally, δG, the Hadamard variation of the Green's function is compared to G -G * , the actual variation of the Green's function on the entire domain Ω × Ω using the relative error for the variation as a metric

ε g = |(G * -G) -δG| |G * -G| + |δG| 1 ( 42
)
where the norm || • || 1 is computed on Ω × Ω by discretizing the domain along a Cartesian grid as was done for Equation 40. This error, which is expected to approach 0 for small values of δρ, is given in Figure 9 for perturbations of decreasing amplitudes, for a dilation of the radius of the inner disc.

Conclusion

In this article, a method for effectively computing the navigation function when the domain boundary is uncertain was presented. It is a two-fold method, where section 2.2 aims at determining the Green's function for the Laplacian operator and section 2.3 uses the resulting Green's function for determining the Hadamard variation. This promising method can be extended to the case of stochastic partial differential equations for aircraft trajectory planning.

c 1 c 4 c 2 c 3 Figure 1 .

 4231 Figure 1. A sphere world bounded by an outer circle of center c 1 and three non overlapping inner circles of centers c 2 , c 3 and c 4 respectively.

8 Figure 3 . 2 Figure 4 .

 8324 Figure 3. log 1 -

10 ( 1 N = 10 (

 10110 a) log 1 as a function of n c for a fixed number of terms in the Laurent expansion N = 2, N = 5 or N = b) log 1 as a function of the number of mesh vertices for the finite element method with Lagrangian elements of order 2.

Figure 5 . 10 Figure 6 .

 5106 Figure 5. log 1 with our method based on the Green's function compared to that obtained with the finite elements method

Figure 7

 7 Figure 7 depicts examples of sphere worlds with one obstacle and the singularity placed at different points in the domain. The resulting function vanishes except in the vicinity of the singularity.

( a )Figure 7 .

 a7 Figure 7. Approximation g of the Green's function on unit disc with obstacle of radius 0.1 centered at -0.2 -0.5i and destination disc of radius 0.2 centered at 0.5i

Figure 8 .Figure 9 .

 89 Figure 8. Navigation functions with trajectories from starting points 40 -40i, 35 -55i, 50 -25i, -80 -40i and -80 + 50i represented.

Acknowledgments: This work was funded by a grant from the French National Research Agency (ANR).

Bibliography