V Bergelson

A Leibman
email: leibman@math.ohio-state.edu

E Lesigne

Intersective polynomials and polynomial Szemerédi theorem

Let P = {p 1 , . . . , p r } ⊂ Q[n 1 , . . . , n m ] be a family of polynomials such that p i (Z m ) ⊆ Z, i = 1, . . . , r. We say that the family P has PSZ property if for any set

> 0 there exist infinitely many n ∈ Z m such that E contains a polynomial progression of the form {a, a + p 1 (n), . . . , a + p r (n)}. We prove that a polynomial family P = {p 1 , . . . , p r } has PSZ property if and only if the polynomials p 1 , . . . , p r are jointly intersective, meaning that for any k ∈ N there exists n ∈ Z m such that the integers p 1 (n), . . . , p r (n) are all divisible by k. To obtain this result we give a new ergodic proof of the polynomial Szemerédi theorem, based on the fact that the key to the phenomenon of polynomial multiple recurrence lies with the dynamical systems defined by translations on nilmanifolds. We also obtain, as a corollary, the following generalization of the polynomial van der Waerden theorem: If p 1 , . . . , p r ∈ Q[n] are jointly intersective integral polynomials, then for any finite partition of Z, Z = k i=1 E i , there exist i ∈ {1, . . . , k} and a, n ∈ E i such that {a, a + p 1 (n), . . . , a + p r (n)} ⊂ E i .

Introduction

Let us call a polynomial p ∈ Q[n] integral if it takes on integer values on the integers. The polynomial Szemerédi theorem ( [BeL]) states that if a set E ⊆ Z has positive upper Banach density,

d * (E) = lim sup N -M →∞ |E∩[M,N -1]| N -M
> 0, then for any finite family of integral polynomials P = {p 1 , . . . , p r } with p i (0) = 0, i = 1, . . . , r, one can find an arbitrarily large n ∈ N such that, for some a ∈ E, {a, a + p 1 (n), . . . , a + p r (n)} ⊂ E. Moreover, the set N P (E) = n ∈ Z : for some a, {a, a + p 1 (n), . . . , a + p r (n)} ⊂ E is syndetic, that is, N P (E) has a nontrivial intersection with any long enough interval in Z (see [START_REF] Bergelson | Uniformity in polynomial Szemerédi theorem, Ergodic Theory of Z d -actions[END_REF]). The polynomial Szemerédi theorem is an extension of Szemerédi's theorem on arithmetic progressions, which corresponds to p i (n) = in, i = 1, . . . , r, (see [Sz] and [START_REF] Furstenberg | Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions[END_REF]) and of the Sàrközy-Furstenberg theorem, which corresponds to the case r = 1 (see [Sa], [START_REF] Furstenberg | Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions[END_REF], [START_REF] Furstenberg | Recurrence in Ergodic Theory and Combinatorial Number Theory[END_REF]).

It is not hard to see that the condition of homogeneity, p i (0) = 0, i = 1, . . . , r, in the polynomial Szemerédi theorem is not superfluous. (Consider, for example, r = 1, p(n) = 2n + 1, E = 2N, or r = 1, p(n) = n 2 + 1, E = 3N.) On the other hand, it is also clear that this condition is not a necessary one. For example, it is easy to see that it can be replaced by the condition p i (n 0 ) = 0, i = 1, . . . , r, for some n 0 ∈ Z. Actually, the latter condition still falls short of being necessary. Let us say that a family of integral polynomials P = {p 1 , . . . , p r } has PSZ property if for every set E ⊆ Z with d * (E) > 0 the introduced above set N P (E) is nonempty, and let us say that P has SPSZ property if for every set E ⊆ Z with d * (E) > 0 the set N P (E) is syndetic. Our goal in this paper is to establish necessary and sufficient conditions for a family of integral polynomials to have PSZ property. When r = 1, such a condition was obtained in [KM]. Namely, it was proved in [KM] that a family consisting of a single integral polynomial p has PSZ property if and only if p is intersective, meaning that for any k ∈ N the intersection {p(n), n ∈ Z} ∩ kZ is nonempty.

As we will see, our condition for a family P to have PSZ property is a natural generalization of the Kamae and Mendès-France condition. We will say that polynomials p 1 , . . . , p r are jointly intersective if for every k ∈ N there exists n ∈ Z such that p i (n) is divisible by k for all i = 1, . . . , r. Here is now the formulation of our main result.

Theorem 1.1. Let P = {p 1 , . . . , p r } be a system of integral polynomials. The following statements are equivalent: (i) P has PSZ property; (ii) P has SPSZ property; (iii) the polynomials p 1 , . . . , p r are jointly intersective.

Remark. One can easily show (see Section 6.1 below) that several integral polynomials of one variable are jointly intersective if and only if they are all divisible by a single intersective polynomial, and thus it follows from Theorem 1.1 that a family P of integral polynomials possesses the PSZ property iff it is of the form P = {q 1 p, q 2 p, . . . , q r p} where q 1 , . . . , q r ∈ Q[n] and p is an intersective polynomial. In particular, for any intersective polynomial p and any r ∈ N the family P = {p, 2p, . . . , rp} has PSZ property; this result was recently obtained by Frantzikinakis ([Fr]).

Theorem 1.1 tells us that the only obstacle for a family of integral polynomials to possess PSZ property is of arithmetic nature. The following direct corollary of Theorem 1.1 gives a precise meaning to this observation: Theorem 1.2. If p 1 , . . . , p r are integral polynomials such that any lattice kZ in Z contains a configuration of the form {a, a + p 1 (n), . . . , a + p r (n)} with a, n ∈ Z, then any set of positive upper Banach density in Z also contains such a configuration.

As a matter of fact, we will obtain a "multiparameter" version of Theorem 1.1, that is, we will prove this theorem for polynomials of several variables. (Passing from one to many variables does not make the proof longer, but essentially strengthens the theorem.) We say that a polynomial p of m ≥ 1 variables with rational coefficients is integral if p(Z m ) ⊆ Z. We will interpret any integral polynomial p of m variables as a mapping Z m -→ Z, and say that p is an integral polynomial on Z m . A set S in Z m is said to be syndetic if S + K = Z m for some finite K ⊂ Z m ; the rest of definitions do not change, and, starting from this moment, we will assume that the polynomials p 1 , . . . , p r in Theorem 1.1 are integral polynomials on Z m .

Clearly, (ii) in Theorem 1.1 implies (i); it is also clear that (i) implies (iii): if p 1 , . . . , p r are not jointly intersective and k ∈ N is such that for no n ∈ Z m the integers p 1 (n), . . . , p r (n) are all divisible by k, the lattice kZ does not contain configurations of the form {a, a + p 1 (n), . . . , a + p r (n)}. So, it is only the implication (iii) =⇒ (ii) which needs to be proven. We will actually get a stronger result: Theorem 1.3. Let p 1 , . . . , p r be jointly intersective integral polynomials on Z m and let E ⊆ Z, d * (E) > 0. Then there exists ε > 0 such that the set

n ∈ Z m : d * E ∩ (E -p 1 (n)) ∩ . . . ∩ (E -p r (n)) > ε is syndetic.
Like the proof of the polynomial Szemerédi theorem in [BeL], our proof of Theorem 1.3 relies on Furstenberg's correspondence principle. This principle, which plays instrumental role in [START_REF] Furstenberg | Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions[END_REF], can be found in the following form in [Be]: For any set E ⊆ Z with d * (E) > 0 there exists an invertible probability measure preserving system (X, B, µ, T ) and a set A ∈ B with µ(A) = d * (E) such that for any r ∈ N and n 1 , n 2 , . . . , n r ∈ Z one has

d * E ∩ (E -n 1 ) ∩ . . . ∩ (E -n r ) ≥ µ A ∩ T -n 1 A ∩ . . . ∩ T -nr A .
For a multiparameter sequence (a n ) n∈Z m of real numbers we define UC-lim n a n = lim N →∞

1 |Φ N |
n∈Φ N a n , if this limit exists for every Følner sequence (Φ N ) in Z m . (Note that if this limit exists for all Følner sequences, then it does not depend on the choice of the sequence.) In view of Furstenberg's correspondence principle, Theorem 1.3 is a corollary of the following ergodic result.

Theorem 1.4. Let integral polynomials p 1 , . . . , p r on Z m be jointly intersective. Then for any invertible probability measure preserving system (X, B, µ, T ) and any set A ∈ B with µ(A) > 0, UC-lim

n µ A ∩ T -p 1 (n) A ∩ . . . ∩ T -pr(n) A > 0. (1)
(We remark that the converse of this theorem is also true: if the polynomials p 1 , . . . , p r are not jointly intersective, one can construct a (finite) measure preserving system and a set A such that the limit in ( 1) is equal to 0. We also remark that having "lim inf" instead of "lim" in formula (1) would be quite sufficient to prove Theorem 1.3; but, anyway, it is known that the limit UC-lim

n µ A ∩ T -p 1 (n) A ∩ . . . ∩ T -pr(n) A exists, -see [L4].)
It is worth noticing that while, being ergodic in nature, our proof of Theorem 1.4 is quite different from the ergodic proofs of polynomial Szemerédi theorem in [BeL] and [START_REF] Bergelson | Uniformity in polynomial Szemerédi theorem, Ergodic Theory of Z d -actions[END_REF], and hence provides a new proof of the "homogeneous" polynomial Szemerédi theorem as well. The reason that we had to resort to a completely different approach lies with the fact that the main ingredients of the proofs in [BeL] and [START_REF] Bergelson | Uniformity in polynomial Szemerédi theorem, Ergodic Theory of Z d -actions[END_REF], namely the PET induction and combinatorial results such as the polynomial van der Waerden theorem (in [BeL]) and the polynomial Hales-Jewett theorem (in [START_REF] Bergelson | Uniformity in polynomial Szemerédi theorem, Ergodic Theory of Z d -actions[END_REF]), do not work when the polynomials involved may have a non-zero constant term. In particular, it is not clear how to obtain by purely combinatorial means (or with the help of topological dynamics but without using an invariant measure) the following corollary of Theorem 1.3. Theorem 1.5. For any finite partition of Z, Z = k i=1 E i , one of E i has the property that for any r, m, and any jointly intersective integral polynomials p 1 , . . . , p r on Z m there exists ε > 0 such that the set n ∈ Z m :

d * E i ∩ (E i -p 1 (n)) ∩ . . . ∩ (E i -p r (n)) > ε is syndetic.
Remarks. 1. One can also show that, given a partition Z = k i=1 E i of Z, for any collection p 1 , . . . , p r of integral polynomials on Z one of E i contains many configurations of the form {a, a + p 1 (n), . . . , a + p r (n)} with n ∈ E i ; see Theorem 5.2 below. 2. Note that if p 1 , . . . , p r are not jointly intersective and k ∈ N is such that for no n ∈ Z m the integers p 1 (n), . . . , p r (n) are all divisible by k, then no element of the partition Z = k-1 i=0 (kZ + i) of Z contains configurations of the form {a, a + p 1 (n), . . . , a + p r (n)}.

The proof of Theorem 1.4 is divided into several steps. The first one is a reduction to nilsystems via Host-Kra-Ziegler machinery. The second step is a differential geometry argument (Lemma 2.2) which allows us to reduce the recurrence problem to properties of the closure of an orbit in a nilsystem (Proposition 2.3). The last step is a description of polynomial orbits on tori (Section 3) and on nilmanifolds (Section 4). In Section 5 we finish the proof of Theorem 1.3 and obtain (the enhanced version of) Theorem 1.5. Section 6 is devoted to concluding remarks and conjectures.

Polynomial Szemerédi theorem and polynomial orbits in nilmanifolds

A nilsystem is a measure preserving system defined by a translation gΓ → agΓ on a compact nilmanifold X = G/Γ (where G is a nilpotent Lie group, Γ is a discrete uniform subgroup of G, and a ∈ G) equipped with the (normalized) Haar measure, which will be denoted by µ. A pro-nilsystem is the inverse limit of a sequence of nilsystems. Let p 1 , . . . , p r be integral polynomials on Z m , m ≥ 1. It was proved in [L4] (see also [START_REF] Host | Convergence of polynomial ergodic averages[END_REF]) that for any probability measure preserving system (X, T, µ), a certain pro-nilsystem ( X, T , µ) is a characteristic factor of (X, T, µ) with respect to the system of polynomial actions {T p 1 (n) , . . . , T pr(n) }, which means that ( X, T , µ) is a factor of (X, T, µ) such that for any f 0 , f 1 , . . . , f r ∈ L ∞ (X) one has UC-lim

n X f 0 • f 1 •T p 1 (n) • . . . • f r •T pr(n) dµ = UC-lim n X E(f 0 | X) • E(f 1 | X)• T p 1 (n) • . . . • E(f r | X)• T pr(n) d µ
(where E(•| X) stands for the conditional expectation with respect to X). The statement

UC-lim

n µ A ∩ T -p 1 (n) A ∩ . . . ∩ T -pr(n) A > 0 for any measurable A ⊆ X with µ(A) > 0 (2) is clearly equivalent to the statement UC-lim n X f • f •T p 1 (n) • . . . • f •T pr(n) dµ > 0 for all f ∈ L ∞ (X)
such that f ≥ 0 and X f dµ > 0.

Thus, in order to prove Theorem 1.4, we have to check (2) for pro-nilsystems only. The following lemma, which appears in [FK], shows that it is enough to check the result in the case where (X, T, µ) is a nilsystem.

Lemma 2.1. Let r ∈ N. Let (X, B, µ, T ) be a measure preserving dynamical system and (B α ) α≥1 be an increasing sequence of T -invariant sub-σ-algebras such that α≥1 B α = B.

Then, for any B ∈ B, there exists α ≥ 1 and

B ′ ∈ B α such that µ(B ′ ) ≥ µ(B)/2 and, for all n 1 , . . . , n r ∈ Z, µ B ∩ T -n 1 B ∩ . . . ∩ T -nr B ≥ 1 2 µ B ′ ∩ T -n 1 B ′ ∩ . . . ∩ T -nr B ′ .
Proof. We assume that µ(B) > 0. The sequence of conditional probabilities (µ (B | B α )) α≥1 converges in probability to the characteristic function 1 B . Hence there exists α such that the set

B ′ := µ (B | B α ) ≥ 1 -1 2(r+1) has measure ≥ 1 2 µ(B). For any n ∈ Z, we have T -n B ′ := µ (T -n B | B α ) ≥ 1 -1 2(r+1) . Using the fact that µ (B 0 ∩ B 1 ∩ . . . ∩ B r | B α ) ≥ 1 -(r + 1)η if µ (B i | B α ) ≥ 1 -η, 0 ≤ i ≤ r, we have µ B ∩ T -n 1 B ∩ . . . ∩ T -nr B = X µ B ∩ T -n 1 B ∩ . . . ∩ T -nr B | B α dµ ≥ B ′ ∩T -n 1 B ′ ∩...∩T -nr B ′ µ B ∩ T -n 1 B ∩ . . . ∩ T -nr B | B α dµ ≥ 1 2 µ B ′ ∩ T -n 1 B ′ ∩ . . . ∩ T -nr B ′ .
Thus we may and, from now on, will assume that (X, µ, T ) is a nilsystem.

A subnilmanifold of X is a closed subset of X of the form D = Kx, where K is a closed subgroup of G and x ∈ X. A subnilmanifold is a nilmanifold itself under the action of the nilpotent Lie group K, and supports a unique probability Haar measure which we will denote by µ D .

It is known (see [L2], or [Sh] for a much more general result

) that if H is a subgroup of G and x ∈ X, then D = Hx is a subnilmanifold of X. A (multiparameter) polynomial sequence in G is a mapping g : Z m -→ G of the form g(n) = a p 1 (n) 1 . . . a pr(n) r , n ∈ Z m , where a i ∈ G and p i are integral polynomials on Z m . It is proved in [L3] that if g is a polynomial sequence in G and D is a subnilmanifold of X, then the closure Y = Orb g (D) of the orbit Orb g (D) = n∈Z g(n)D of D is either a subnilmanifold or a finite disjoint union of subnilmanifolds of X. Moreover, the sequence {g(n)D} n∈Z has an asymptotic distribution in Y : we have UC-lim n g(n)µ D = µ ′ Y , where µ ′ Y is a convex combination of the Haar measures on the connected components of Y . In particular, if Y is connected, then Y is a subnilmanifold, and µ ′ Y = µ Y is the Haar measure on Y .
Let p 1 , . . . , p r be integral polynomials on Z m ; consider the polynomial sequence g

(n) = 1 G a p 1 (n) . . . a pr (n) , n ∈ Z m , in the group G r+1 . Let ∆ X r+1 be the diagonal , ∆ X r+1 = x = x . . . x :
x ∈ X in the nilmanifold X r+1 , and let Y = Orb g (∆ X r+1 ). Then for any continuous functions

f 0 , f 1 , . . . , f r on X, UC-lim n X f 0 • f 1 •T p 1 (n) • . . . • f r •T pr(n) dµ = UC-lim n ∆ X r+1 f 0 ⊗ f 1 •T p 1 (n) ⊗ . . . ⊗ f r •T pr(n) dµ ∆ X r+1 = UC-lim n ∆ X r+1 f 0 ⊗ f 1 ⊗ . . . ⊗ f r (g(n)x) dµ ∆ X r+1 (x) = UC-lim n g(n)∆ X r+1 f 0 ⊗ f 1 ⊗ . . . ⊗ f r dµ g(n)∆ X r+1 . = Y f 0 ⊗ f 1 ⊗ . . . ⊗ f r dµ ′ Y .
Since C(X) is dense in L r+1 (X, µ) and all the marginals of µ ′ Y are equal to µ, we obtain by the multilinearity of the above expressions that UC-lim

n X f 0 • f 1 •T p 1 (n) • . . . • f r •T pr(n) dµ = Y f 0 ⊗ f 1 ⊗ . . . ⊗ f r dµ ′ Y for any f 0 , f 1 , . . . , f r ∈ L ∞ (X).
In particular, for any measurable set A ⊆ X,

UC-lim

n µ A ∩ T -p 1 (n) A ∩ . . . ∩ T -pr(n) A = µ ′ Y (A r+1 ∩ Y ),
and in order to prove Theorem 1.4 we only need to show that

µ ′ Y (A r+1 ∩ Y ) > 0 whenever µ(A) > 0.
We claim that this is true as long as Y ⊇ ∆ X r+1 . Indeed, let us assume that this inclusion holds, and let A be a set of positive measure in X. Let x ∈ X be a Lebesgue point of A, and let x =

x . . .

x ∈ ∆ X r+1 . Using a system of Malcev coordinates in G (see Section 4), we identify a connected open neighborhood Ω of x with an open subset of R d , where d = dim X. Then, under this identification, r+1) , and the restriction on Y ′ of the measure µ ′ Y is equivalent to the Lebesgue measure (that is, the s-volume, where s = dim Y ) in Y ′ . Let S be the connected component of Y ′ that contains ∆ Ω r+1 . Our claim now follows from of the following lemma.

Y ′ = Y ∩ Ω r+1 is a smooth (polynomial) manifold in R d(
Lemma 2.2. Let Ω be an open subset of R d and let S be a connected C 1 -manifold in Ω k with S ⊇ ∆ Ω k . Let σ be the Lebesgue measure on S. Then for any subset A of Ω with positive Lebesgue measure one has σ(A k ∩ S) > 0.

Proof. Let x be a density point of A. For t > 0 let Q t be the cube in R d of size t centered at x, and let P t = Q k t (which is the cube in R dk of size t centered at x = x . . . x ). Let π i , i = 1, . . . , k, be the projection from R dk = (R d ) k onto the ith factor. Since S contains ∆ Ω k , for any i, π i projects S onto Ω and has full rank at all points of S.

Let s = dim S. Let L be the tangent space to S at the point x = x . . .

x and let λ be the Lebesgue measure (the s-volume

) on L. Let 1 ≤ i ≤ k. If t is small enough (so that, in particular, Q 2t ⊆ Ω), we have σ π -1 i (B) ∩ S ∩ P t ≤ 2λ π -1 i (B) ∩ L ∩ P 2t (3) and λ π -1 i (B) ∩ L ∩ P t ≤ 2σ π -1 i (B) ∩ S ∩ P 2t (4)
for any measurable set B ⊆ Ω. Let σ t and λ t be the normalized Lebesgue measures on S ∩ P t and on L ∩ P t respectively. Then for t small enough we have from (4) that σ (S ∩ P t ) ≥ 1 2 λ L ∩ P t/2 = 2 -2s-1 λ (L ∩ P 2t ), and thus from (3),

σ t (π -1 i (B) ∩ S ∩ P t ) ≤ 2 2s+2 λ 2t (π -1 i (B) ∩ L ∩ P 2t ) (5)
for any measurable B ⊆ Ω. For t > 0, let ν t be the normalized Lebesgue measure on the cube Q t ⊂ R d . Since L is an affine space passing through the center of Q t , and since, for each i, L projects by

π i onto R d , we have π i (λ t ) ≤ c i ν t with a constant c i independent on t. Let c = max{c 1 , . . . , c k }, then λ t (π -1 i (B) ∩ L) ≤ cν t (B)
for any measurable set B ⊆ R d and all i. Now choose t small enough so that (5) holds for all i and that ν

2t (Q 2t \ A) < 1/(2 2s+2 kc). Then σ t A k ∩ P t ∩ S ≥ 1 - k i=1 σ t π -1 i (Q t \ A) ∩ S ≥ 1 - k i=1 2 2s+2 λ 2t π -1 i (Q 2t \ A) ∩ L ≥ 1 - k i=1 2 2s+2 cν 2t (Q 2t \ A) > 0,
and so σ(A k ∩ S) > 0.

Hence, we are done if we prove that Orb(x) ∋ x for every x ∈ ∆ X r+1 . After considering the new nilmanifold X r+1 and changing notation, Theorem 1.4 is now reduced to the following proposition.

Proposition 2.3. Let X = G/Γ be a nilmanifold and let g

(n) = a p 1 (n) 1 . . . a pr(n) r
be a polynomial sequence in G such that the polynomials p 1 , . . . , p r are jointly intersective. Then Orb g (x) ∋ x for any x ∈ X.

We will prove Proposition 2.3 in Section 4 (see Proposition 4.3).

Intersective polynomials and polynomial orbits on tori

Given two integers b, k, we will write b . . . k if k divides b. We will use the term lattice for cosets of subgroups of finite index in Z m . If Λ is a lattice of Z m , then Λ is itself isomorphic to Z m , and the notion of an integral polynomial on Λ is well defined. (Clearly, integral polynomials on Λ are restrictions of polynomials on Z m taking on integer values on Λ.)

We will say that integral polynomials p 1 , . . . , p r on Λ are jointly intersective (on Λ) if for any k ∈ N there exists n ∈ Λ such that p 1 (n), . . . , p r (n) . . . k.

Lemma 3.1. If integral polynomials p 1 , . . . , p r on a lattice Λ are jointly intersective, then for any sublattice Λ ′ of Λ there exists l ∈ Λ such that the polynomials p 1 , . . . , p r are jointly intersective on Λ ′ + l.

Proof. Let L ⊂ Λ be a finite set such that Λ ′ + L = Λ. For any k ∈ N there exists l k ∈ L such that p i (n + l k ) . . . k, i = 1, . . . , r, for some n ∈ Λ ′ . Let l be such that l k! = l for infinitely many k. Then for any k ∈ N there exists k 0 > k such that l k 0 ! = l, and thus there exists n ∈ Λ ′ such that p i (n + l) . . . k 0 ! . . . k, i = 1, . . . , r.

Lemma 3.2. Let integral polynomials p 1 , . . . , p r on a lattice Λ be jointly intersective. For any k ∈ N there exists a lattice Λ ′ ⊆ Λ such that p 1 , . . . , p r are jointly intersective on Λ ′ and p 1 (n), . . . , p r (n) . . . k for all n ∈ Λ ′ .

Proof. Let d ∈ N be such that dp 1 , . . . , dp r have integer coefficients. By Lemma 3.1, there exists l ∈ Λ such that p 1 , . . . , p r are jointly intersective on Λ ′ = kdΛ + l. There exists n 0 ∈ Λ such that p i (kdn 0 + l) . . . k, i = 1, . . . , r. For any n ∈ Λ and every i we have p i (kdn + l) = p i (kdn 0 + l) + q i (kd(nn 0 )) where q i is an integral polynomial with coefficients in 1 d Z and zero constant term. Hence, q i (kd(nn 0 )) . . . k, i = 1, . . . , r, and so p i (kdn + l) . . . k, i = 1, . . . , r, for all n.

Let M be an (additive) torus. A polynomial sequence in M is a (multiparameter) sequence of the form t

(n) = r i=1 p i (n)v i , n ∈ Z m
, where p i are integral polynomials on Z m and v i ∈ M, i = 1, . . . , r. It is well known (see [W]) that if t is a polynomial sequence in M, then the closure S = {t(n)} n∈Λ of t is a connected component, or a union of several connected components, of a coset u + N for some closed subgroup N of M and an element u ∈ M. In particular, if S is connected, it is a subtorus of M. After choosing coordinates in M we identify M with a standard torus R s /Z s , s ∈ N. Then any polynomial sequence

t(n) = r i=1 p i (n)v i in M can be written in the form t(n) = q 0,1 (n)
. . .

q 0,s (n) 1 k + l i=1 q i,1 (n)
. . .

q i,s (n) α i mod Z s , (6)
where 1, α 1 , . . . , α l ∈ R are rationally independent, k ∈ N, and the polynomials q i,j are linear combinations, with integer coefficients, of the polynomials p 1 , . . . , p r . We first take care of the "irrational" part of t. For any polynomial q let q denote the polynomial qq(0).

Lemma 3.3. (i) Let t(n) = q 1 (n) . . . qs(n)
α mod Z s where α ∈ R is irrational and q 1 , . . . , q s are integral polynomials on a lattice Λ. Then {t(n)} n∈Λ is the (connected) subtorus q 1 (0) . . .

qs(0) α + span R q1 (n) . . . qs(n) , n ∈ Λ mod Z s of M. (ii) Let b i (n) = q i,1 (n)
. . .

q i,s (n)
mod Z s and t i = b i α i , i = 1, . . . , l, where 1, α 1 , . . . , α l ∈ R are rationally independent and q i,j are integral polynomials on a lattice Λ. Let t = l i=1 t i ; then {t(n)} n∈Λ = l i=1 {t i (n)} n∈Λ . In particular, {t(n)} n∈Λ is a (connected) subtorus of M.

Proof. (i) We may assume that q j (0) = 0, j = 1, . . . , s. Let S = span R q 1 (n) . . .

qs(n)

, n ∈ Λ ⊆ R s and S = S mod Z s ; since the vectors

q 1 (n) . . . qs(n)
are rational, S is closed in M. Hence S is a subtorus and we have {t(n)} n∈Λ ⊆ S. On the other hand, consider an additive

character χ on M, χ v 1 . . . vs = c 1 v 1 + . . . + c s v s mod 1 with c 1 , . . . , c s ∈ Z; if χ(t(n)) = 0 for all n ∈ Λ, then (c 1 q 1 (n) + . . . + c s q s (n))α ∈ Z for all n ∈ Λ, so c 1 q 1 (n) + . . . + c s q s (n) = 0
for all n ∈ Λ, so χ | S = 0. Hence, the sequence {t(n)} n∈Λ is not contained in any proper closed subgroup of S, and thus, is dense in S.

(ii) Again, we may assume that q i,j (0) = 0 for all i, j. By (i), {t i (n)} n∈Λ , i = 1, . . . , l, are connected subgroups of M, and such is N = l i=1 {t i (n)} n∈Λ . Let S = l i=1 {t i (n)} n∈Λ ; clearly, S ⊆ N. We have S ∋ 0 M , thus S a union of connected components of a closed subgroup of N.

Let χ be a character on M, χ

v 1 . . . vs = c 1 v 1 + . . . + c s v s mod 1 with c 1 , . . . , c s ∈ Z,
and let φ be the corresponding linear function on R s , φ

v 1 . . . vs = c 1 v 1 + . . . + c s v s . Then χ(t(n)) = 0, n ∈ Λ, iff l i=1 φ(b i (n))α i = 0 mod 1, n ∈ Λ,
which, because of the independence of α 1 , . . . , α l and 1, is equivalent to φ(b i (n)) = 0 and so, χ(t i (n)) = 0, n ∈ Λ, for all i = 1, . . . , l. Hence, any character vanishing on S also vanishes on N, and so, S is not contained in any proper closed subgroup of N. Thus, S = N.

Lemma 3.4. Let t(n) = q 1 (n) . . . qs(n)
α mod Z s where α ∈ R is irrational and q 1 , . . . , q s are integral polynomials on a lattice Λ. Then {t(n)} n∈Λ ∋ 0 M iff no linear combination of q 1 , . . . , q s is a nonzero constant.

Proof. By Lemma 3.3(i), {t(n)} n∈Λ ∋ 0 M iff q 1 (0) . . . qs(0) ∈ span R q1 (n) . . . qs(n)
, n ∈ Λ . This is so iff any linear function on R s vanishing on span R q1 (n) . . .

qs(n)

, n ∈ Λ vanishes at

q 1 (0) . . . qs(0)
as well. This is equivalent to saying that if s i=1 c i qi = 0, with c 1 , . . . , c s ∈ R, then also s i=1 c i q i = 0.

Corollary 3.5. Let t(n) = q 1 (n)

. . .

qs(n)

α mod Z s where α ∈ R is irrational and q 1 , . . . , q s are jointly intersective integral polynomials on a lattice Λ. Then {t(n)} n∈Λ ∋ 0 M .

Proof. If there exist c 1 , . . . , c s ∈ R and a nonzero c ∈ R such that s i=1 c i q i = c, then, since q i have rational coefficients, there exist c 1 , . . . , c s ∈ Z and a nonzero c ∈ Z such that s i=1 c i q i = c. But this is impossible if q i are jointly intersective. Let now t be a polynomial sequence in M, t(n

) = p 1 (n)v 1 + . . . + p r (n)v r , v i ∈ M,
where p 1 , . . . , p r are jointly intersective polynomials on Λ.

Proposition 3.6. There exists a sublattice Λ ′ of Λ such that p 1 , . . . , p r are jointly intersective on Λ ′ , S = {t(n)} n∈Λ ′ is a connected subtorus of M, and 0 M ∈ S.

Proof. We represent t in the form (6), where all polynomials q i,j are linear combinations of polynomials p i and so, are jointly intersective. If a nontrivial "rational" term q 0,1 . . .

q 0,s 1 k
is present, by Lemma 3.2 there exists a sublattice Λ ′ ⊂ Λ such that the polynomials q 0,1 , . . . , q 0,r are jointly intersective on Λ ′ and q 0,j (n) . . . k for all n ∈ Λ ′ and j = 1, . . . , s.

Then q 0,1 (n) . . . q 0,s (n) 1 k = 0 mod Z s for all n ∈ Λ ′ , and we may ignore this term. By Corollary 3.5, for each i = 1, . . . , l and t i (n) = q i,1 (n) . . .

q i,s (n) α i mod Z s , S i = {t i (n)} n∈Λ ′ is a (con- nected) subtorus of M with 0 M ∈ S i , and by Lemma 3.3(ii), S = {t(n)} n∈Λ ′ = l i=1 S i . Thus, S is a (connected) subtorus of M with 0 M ∈ S.

Intersective polynomials and polynomial orbits on nilmanifolds

Let P be a ring of integral polynomials on a lattice Λ. We will say that a mapping g from Λ to a nilpotent group G is a P -polynomial sequence if g has the form g(n) = a

p 1 (n) 1 . . . a pr(n) r
with r ∈ N, a i ∈ G and p i ∈ P , i = 1, . . . , r. The following facts are obvious and will be used repeatedly in the sequel.

(i) if g 1 , g 2 are P -polynomial sequences in G, then the sequence g 1 (n)g 2 (n) is P - polynomial; (ii) if η : G -→ G ′ is a homomorphism to a nilpotent group G ′ and g is a P -polynomial sequence in G, then η(g) is a P -polynomial sequence in G ′ ; (iii) if η : G -→ G ′ is
a homomorphism onto a nilpotent group G ′ and g ′ is a P -polynomial sequence in G ′ , then there exists a P -polynomial sequence g in G such that η(g) = g ′ .

Proposition 4.1. Let G be a connected nilpotent Lie group and H be a connected closed subgroup of G. If g is a P -polynomial sequence in G such that g(n) ∈ H for all n ∈ Λ, then g is a P -polynomial sequence in H.

Remark. Actually, the assertion of Proposition 4.1 holds for any (not necessarily topological) nilpotent group and any its subgroup (see [L1]).

Proof. Replacing G by its universal cover we may assume that G is simply-connected.

We then may choose a Malcev basis in G, that is, elements e 1 , . . . , e k ∈ G such that every element of G is uniquely representable in the form k j=1 e y j j with y 1 , . . . , y k ∈ R. (See [M]. Elements e i can be chosen to be of the form e i = exp(ǫ i ) where (ǫ 1 , . . . , ǫ k ) is a linear base of the Lie algebra of G.) Moreover, by an elementary linear algebra argument, the basis can be chosen compatible with H, so that for some j 1 , . . . , j l ∈ {1, . . . , k}, the elements e j 1 , . . . , e j l form a basis in H, and thus k j=1 e y j j ∈ H iff y j = 0 for all j ∈ {j 1 , . . . , j l }.

From the Campbell-Hausdorff formula we know that multiplication in G is polynomial in the Malcev basis, that is, where F j are polynomials vanishing at 0. If g takes values only in H, F j (p 1 (n), . . . , p r (n)) = 0 for all j ∈ {j 1 , . . . , j l }, and g(n) = j∈{j 1 ,...,j l } e F j (p 1 (n),...,pr(n)) j is a polynomial sequence in H. The last formula can be rewritten as g(n) = j∈{j 1 ,...,j l } k j i=1 (e α j,i j ) F j,i (p 1 (n),...,pr(n)) where α j,i ∈ R and F j,i are nonconstant monomials. Now, if all p i are in P , the polynomials q j,i (n) = F j,i (p 1 (n), . . . , p r (n)) are also in P , and so, g is a P -polynomial sequence in H.

We will also need the following fact:

Proposition 4.2. ([L2]) Let G be a connected nilpotent Lie group, let X = G/Γ be a nilmanifold, let π be the canonical projection G -→ X, let M be the torus [G, G] \X, and let ξ : X -→ M be the projection. If a polynomial sequence g in G is such that ξ(π(g(n))) is dense in M, then π(g(n)) is dense in X.
Now let G be a nilpotent group, Γ a closed uniform subgroup of G, and X = G/Γ. Let π be the projection G -→ X, and 1 X = π(1 G ) ∈ X. Let a 1 , . . . , a r ∈ G, let p 1 , . . . , p r be jointly intersective polynomials on a lattice Λ, and let P be the ring generated by the polynomials p 1 , . . . , p r . Proposition 2.3 is a consequence of the following proposition, applied to g(n) = a

p 1 (n) 1 . . . a pr(n) r : Proposition 4.3. If g is a P -polynomial sequence in G and x ∈ X, then {g(n)x} n∈Λ ∋ x.
Proof. It is enough to prove that, for any P -polynomial sequence g, we have {π(g(n

))} n∈Λ ∋ 1 X . Indeed, if x = g 0 Γ ∈ X then g -1 0 gg 0 is a P -polynomial sequence and {g(n)x} n∈Λ ∋ x iff {π(g -1 0 g(n)g 0 )} n∈Λ ∋ 1 X . If X is not connected, let Ĝ be a subgroup of finite index k in G such that X o = π( Ĝ)
is the identity component of X. By Lemma 3.2, there exists a sublattice Λ ′ of Λ such that the polynomials p 1 , . . . , p r are jointly intersective on Λ ′ and for any n ∈ Λ ′ , p 1 (n), . . . , p r (n) . . . k. The sequence g | Λ ′ takes values in Ĝ, and after replacing Λ by Λ ′ , G by Ĝ, and X by X o we may assume that X is connected.

Let G o be the identity component of G and let θ be the canonical homomorphism

G -→ G/G o . Since X is connected, θ(Γ) = G/G o ,
and thus there exists a P -polynomial sequence δ in Γ such that θ(δ) = θ(g). The sequence g

′ (n) = g(n)δ(n) -1 takes values in G o and satisfies π(g ′ ) = π(g), n ∈ Λ. By Proposition 4.1, g ′ (n) is a P -polynomial sequence in G o . After replacing g by g ′ and G by G o we may assume that G is connected. Let V = G/[G, G] = [G, G]\G with η : G -→ V being the canonical projection. V is a connected commutative Lie group. Let M be the torus V /η(Γ) = [G, G] \X with τ : V -→ M
being the projection; we will use multiplicative notation for V and M. Let

t(n) = g(n)1 M , n ∈ Λ; in other words, t = τ (η(g)) is the projection of g on M. G o ∋ g(n) H ↓η ↓ ↓ V = G o /[G o , G o ] ∋ η(g(n)) L ↓τ ↓ ↓ M = G o / ([G o , G o ](Γ ∩ G o )) ∋ t(n) = τ (η(g(n)) ∈ S
If t is dense in M, then by Proposition 4.2, g is dense in X and we are done. Assume that t is not dense in M. We know that t is a P -polynomial sequence in M. By Proposition 3.6, after replacing Λ by a suitable sublattice, the polynomials p 1 , . . . , p r remain jointly intersective and S = {t(n)} n∈Λ is a connected proper subtorus of M with 1 M ∈ S.

Note that τ -1 (S) is a proper subgroup of V . Let L ⊆ V be the identity component of τ -1 (S). We have τ (L) = S. Let u be a P -polynomial sequence in L such that

τ (u) = t. Then τ (η(g)) = τ (u), thus u(n) -1 η(g(n)) ∈ η(Γ), n ∈ Λ. The sequence λ(n) = u(n) -1 η(g(n)), n ∈ Λ, is P -polynomial in η(Γ); let γ be a P -polynomial sequence in Γ such that η(γ) = λ. Put h(n) = g(n)γ(n) -1 , n ∈ Λ; then π(h) = π(g) and η(h) = u.
Let H = η -1 (L); then H is a proper closed connected subgroup of G, and Y = π(H) is a subnilmanifold of X that contains the sequence π(h) = π(g). The sequence h takes values in H, thus by Proposition 4.1, h is a P -polynomial sequence in H. By induction on the dimension of H, {π(h(n))} n∈Λ ∋ 1 Y = 1 X .

Polynomial Szemerédi and van der Waerden theorems

Proof of Theorem 1.3. By Furstenberg's correspondence principle, there exists a probability measure preserving system (X, B, µ, T ) and a set A ∈ B with µ(A) = d * (E) such that for any n 1 , . . . , n l ∈ Z one has

d * E ∩ (E -n 1 ) ∩ . . . ∩ (E -n l ) ≥ µ A ∩ T -n 1 A ∩ . . . ∩ T -n l A . Let c n = µ A ∩ T -p 1 (n) A ∩ . . . ∩ T -pr(n) A , n ∈ Z m . By Theorem 1.4, lim N -M →∞ 1 (N -M ) m n∈[M,N -1] m c n = C > 0, and thus d * {n ∈ Z m : c n > C/2} > 0, where d * (F ) = lim inf N -M →∞ |F ∩[M,N -1] m | (N -M ) m
). This means that the set {n ∈ Z m : c n > C/2} is syndetic.

The polynomial van der Waerden theorem for jointly intersective polynomials, Theorem 1.5, is an immediate corollary of Theorem 1.3. However, using a "uniformity" in Theorem 1.4 (and following an idea which was utilized in [START_REF] Bergelson | Uniformity in polynomial Szemerédi theorem, Ergodic Theory of Z d -actions[END_REF]), we can get a stronger version of Theorem 1.5. We start with the following strengthening of the preceding theorem.

Proposition 5.1. Let p 1 , . . . , p r be jointly intersective integral polynomials on Z m and let sets E 1 , . . . , E s ⊆ Z be such that d * (E i ) > 0 for all i = 1, . . . , s. Then there exists ε > 0 such that the set

S = s i=1 n ∈ Z m : d * (E i ∩ (E i -p 1 (n)) ∩ . . . ∩ (E i -p r (n)) > ε (7)
is syndetic.

Proof. (Cf. the proof of Theorem 0.4 in [START_REF] Bergelson | Uniformity in polynomial Szemerédi theorem, Ergodic Theory of Z d -actions[END_REF].) Using Furstenberg's correspondence principle, for each i = 1, . . . , s find a probability measure preserving system (X i , B i , µ i , T i ) and a set

A i ∈ B i with µ(A i ) = d * (E i ) such that for any n 1 , . . . , n l ∈ Z one has d * E i ∩ (E i -n 1 ) ∩ . . . ∩ (E i -n l ) ≥ µ i A i ∩ T -n 1 i A i ∩ . . . ∩ T -n l i A i . Put X = X 1 × . . . × X s , T = T 1 × . . . × T s , and A = A 1 × . . . × A s . By Theorem 1.4, there exists ε > 0 such that the set n ∈ Z m : µ A ∩ T -p 1 (n) A ∩ . . . ∩ T -pr(n) A > ε = n ∈ Z m : s i=1 µ i A i ∩ T -p 1 (n) A i ∩ . . . ∩ T -pr(n) A i > ε
is syndetic, and this is a subset of

s i=1 n ∈ Z m : µ i A i ∩ T -p 1 (n) A i ∩ . . . ∩ T -pr(n) A i > ε .
We now confine ourselves to the one-parameter situation. A subset E of Z is said to be piecewise syndetic if there exists a sequence of intervals J 1 , J 2 , . . . with |J j | -→ ∞ and a syndetic set

E ′ ⊆ Z such that E = E ′ ∩ ∞ j=1 J j .
It is not hard to see that if a syndetic set is partitioned into finitely many subsets, then one of these subsets is piecewise syndetic.

Theorem 5.2. Let p 1 , . . . , p r be jointly intersective integral polynomials. For any finite partition of Z, Z = k i=1 E i , one of E i has the property that, for some ε > 0, the set

n ∈ E i : d * E i ∩ (E i -p 1 (n)) ∩ . . . ∩ (E i -p r (n)) > ε is piecewise syndetic.
Remark. As it was already mentioned above, the fact that for some E i (and indeed for any E i that has positive upper density) and some ε > 0 the set

n ∈ Z : d * E i ∩ (E i -p 1 (n)) ∩ . . . ∩ (E i -p r (n)) > ε
is syndetic is a direct corollary of Theorem 1.3. The delicate point in Theorem 5.2 is that the set of n satisfying the assertion of the theorem is a (large) subset of E i .

Proof. Re-index E 1 , . . . , E k so that d * (E i ) > 0 for i = 1, . . . , s and d * (E i ) = 0 for i = s + 1, . . . , k. Choose ε as in Proposition 5.1, and let S be the syndetic set defined by (7). Since the set Z \ s i=1 E i has zero upper Banach density, the set S ∩ s i=1 E i is also syndetic, and thus S ∩ E i is piecewise syndetic for some i ∈ {1, . . . , s}.

6 Concluding remarks

Intersective and jointly intersective polynomials

While every integral polynomial with an integer root is clearly intersective, there are also examples of intersective polynomials without rational roots. For example, one can show that if a 1 , a 2 are distinct prime integers such that a 1 ≡ a 2 ≡ 1 (mod 4) and a 1 is a square in Z/(a 2 Z), then the polynomial p(n) = (n 2 -a 1 )(n 2 -a 2 )(n 2 -a 1 a 2 ) is intersective. (Such is, for example, the polynomial p(n) = (n 2 -5)(n 2 -41)(n 2 -205).) There are also similar examples of intersective polynomials of degree 5 (for instance, p(n) = (n 3 -19)(n 2 +n+1)), and one can show (see [BBi]) that there exist no intersective polynomials in one variable of degree less than 5 without rational roots. A curious example of an intersective polynomial of several variables with no rational roots is p(n 1 , . . . , n 4 ) = n 2 1 + . . . + n 2 4 + b, where b is an arbitrary positive integer; this polynomial has the property that all its shifts p + c, c ∈ Z, are also intersective. (No intersective polynomials in one variable, except the polynomials ±n + b, b ∈ Z, have this property. Indeed, if an integral polynomial p(n) is not of the form ±n + b, then there exists n 0 ∈ Z such that k = |p(n 0 + 1)p(n 0 )| = 1. Then p is not one-to-one in Z/(kZ), so is not onto, and thus there exists d ∈ Z such that p(n)d = 0 mod k for any n ∈ Z.) Systems of jointly intersective polynomials in one variable can be easily described: Proposition 6.1. Integral polynomials p 1 , . . . , p r of one variable are jointly intersective iff they all are multiples of an intersective polynomial p.

(We say that a polynomial q is a multiple of a polynomial p if q is divisible by p in the ring Q The natural conjecture that integral polynomials are jointly intersective if any linear combination of these polynomials is intersective, fails to be true. For example, one can show that the polynomials p 1 (n) = n(n + 1)(2n + 1) and p 2 (n) = (n 3 + n 2 + 2)(2n + 1) satisfy the above condition, but are not jointly intersective (see Appendix in [BeLe]). Proposition 6.1 is no longer true for jointly intersective polynomials of several variables. If polynomials p 1 , . . . , p r in m variables are jointly intersective, then the whole ideal I in Q[n 1 , . . . , n m ] generated by these polynomials consists of jointly intersective polynomials. In the case m = 1, I is principal, from which Proposition 6.1 follows. If m ≥ 2, Q[n 1 , . . . , n m ] is not a principal ideal domain, and Proposition 6.1 fails. (Consider, for example, the pair of jointly intersective polynomials p i (n 1 , n 2 ) = n i , i = 1, 2.)

[n].) Proof. Clearly, if p ∈ Q[n]

Total ergodicity

If one deals with totally ergodic dynamical systems (this means that T k is ergodic for any nonzero integer k), it is not hard to verify (see Proposition 6.2 below) that any integral polynomial is "good" for single recurrence. This is no longer true for multiple recurrence, as the simple example following Proposition 6.2 shows. Proposition 6.2. Let (X, B, µ, T ) be a totally ergodic probability measure preserving dynamical system and let p be an integral polynomial on Z m . Then, for any set A ∈ B, UC-lim n µ A ∩ T -p(n) A = µ(A) 2 .

Proof. Total ergodicity of T is equivalent to the lack of discrete rational spectrum for the unitary operator f → f •T on L 2 (X). For any f ∈ L 2 (X) and any Følner sequence (Φ N ) ∞ N =1 in Z m , the convergence in L 2 of the sequence

1 |Φ N | n∈Φ N f •T p(n) ∞
N =1 to the limit f dµ is then a consequence of basic spectral theory and Weyl's equidistribution theorem. (Cf. [START_REF] Furstenberg | Recurrence in Ergodic Theory and Combinatorial Number Theory[END_REF], p. 70-71.)

Example. An example of a totally ergodic probability measure preserving dynamical system is the rotation of the one dimensional torus by an irrational number α. The simplest example of a non-intersective polynomial is 2n + 1. If we choose A to be a sufficiently small interval on the torus, then, for any n = 0, we will have

A ∩ T -n A ∩ T -(2n+1) A = ∅.
It is natural to ask what is a necessary and sufficient condition for a family P = {p 1 , . . . , p r } of integral polynomials to have "the multiple recurrence property" (namely, that for any A ⊆ X with µ(A) > 0 one has µ(A ∩ T -p 1 (n) A ∩ . . . ∩ T -pr(n) A) > 0 for a certain n) in the framework of totally ergodic dynamical systems. We conjecture that the condition that the ring generated by p 1 , . . . , p r does not contains nonzero constants is a sufficient one. However, this condition is far from being necessary; for example, if the polynomials p 1 , . . . , p r are linearly independent, it suffices that span Z {p 1 , . . . , p r } does not contain nonzero constants. In order to find a necessary and sufficient condition for a family P = {p 1 , . . . , p r } of polynomials to have the multiple recurrence property under the assumption of total ergodicity one has to take into consideration the complexity of the family {p 1 , . . . , p r } (see [BeLLe] and [L5]). Such a condition, however, would be too cumbersome to be either of practical or aesthetic value.

Multidimensional conjecture

The multidimensional polynomial Szemerédi theorem states that given a set E of positive upper Banach density in Z k and vector-valued polynomials p 1 , . . . , p r : Z m -→ Z k with zero constant term, the set N P (E) = n ∈ Z m : for some a ∈ Z k , {a, a + p 1 (n), . . . , a + p r (n)} ⊂ E is infinite, and, moreover, syndetic. (See [BeL] and [START_REF] Bergelson | An ergodic IP polynomial Szemerédi theorem[END_REF].) It is natural to try to generalize Theorem 1.1 to this multidimensional situation. Let us say that a family {p 1 , . . . , p r } of polynomial mappings Z m -→ Z k has SPSZ property if for any set E of positive upper Banach density in Z k the set N P (E) is syndetic in Z m ; let us say that p 1 , . . . , p r are jointly intersective if for any subgroup Λ of finite index in Z k there exists n ∈ Z m such that p 1 (n), . . . , p r (n) ∈ Λ. Conjecture 6.3. A set {p 1 , . . . , p r } of polynomial mappings Z m -→ Z k has SPSZ property iff the mappings p 1 , . . . , p r are jointly intersective.

F

  y 1 ,...,y k ,z 1 ,...,z k ) y 1 ,...,y k ,n) j where Q j and R j are polynomials vanishing at 0. Thus, any polynomial sequence g(n) j (p 1 (n),...,pr(n)) j

  is an intersective polynomial and p 1 , . . . , p r . . . p then p 1 , . . . , p r are jointly intersective. Let p 1 , . . . , p r ∈ Q[n] be jointly intersective. Let p ∈ Z[n] be the greatest common divisor of p 1 , . . . , p r in Q[n]. Then there exist h 1 , . . . , h r ∈ Q[n] such that r i=1 h i p i = p. Multiplying both parts by an integer d if necessary, we may assume that h 1 , . . . , h r have integer coefficients, and that r i=1 h i p i = dp. It is then clear that if p 1 , . . . , p r are jointly intersective, then dp is intersective, and thus p is intersective.

At this stage, we are unable to check this conjecture by methods developed above because of lack of theory of characteristic factors for Z k -actions, similar to that established in [HK1] and [Z] for Z-actions.

The first two authors were supported by NSF grant DMS-0600042


Ji Ma

Daniel Delahaye

Mohammed Sbihi

Paolo Scala
email: p.m.scala@hva.nl

ICRAT 2018 Integrated Optimization of Arrival, Departure, and Surface Operations

Keywords: Airport Operations, Terminal Maneuvering Area, Integrated Optimization, Simulated Annealing

Airports and surrounding airspaces are limited in terms of capacity and represent the major bottleneck in the air traffic management system. This paper proposes a twolevel model to tackle the integrated optimization problem of arrival, departure, and surface operations. The macroscopic level considers the terminal airspace management for arrivals and departures and airport capacity management, while the microscopic level optimizes surface operations and departure runway scheduling. An adapted simulated annealing heuristic combined with a time decomposition approach is proposed to solve the corresponding problem. Computational experiments performed on real-world case studies of Paris Charles De-Gaulle airport, show the benefits of this integrated approach.

I. INTRODUCTION

With the steady growth of air traffic, the current air network is facing capacity problems, leading to delays and congestions. One of the most critical parts is the airport and its surrounding airspaces. Increasing use of saturated airfield capacity will adversely impact predictability and punctuality. The current network traffic throughput need to be increased in order to accommodate the forecast demand with a sufficient margin. To achieve this goal, new operational concepts and techniques need to be developed to support the increased traffic density. Efficient planning and optimization approaches of airport operations and surrounding terminal airspaces are critical to alleviate traffic congestions.

In some previous works, segregated problems on arrival management (AMAN), departure management (DMAN) and surface management (SMAN) have been studied extensively. Bennell et al. [START_REF] Bennell | Airport runway scheduling[END_REF] gave a brief review about the techniques and tools for scheduling aircraft landings and take-offs. Atkin et al. [START_REF] Atkin | The airport ground movement problem: Past and current research and future directions[END_REF] provided an overview of the research for ground movement and the integration of various airport operations. Recently, more efforts are made on integrated optimization models for airside (runway, taxiway and terminal) and airspace (terminal airspace) operations.

Integrating terminal airspace management with existing route network is a more complicated, but more realistic problem than considering only the previous-mentioned segregated problems. Khadilkar and Balakrishnan [START_REF] Khadilkar | Integrated control of airport and terminal airspace operations[END_REF] modeled departure operations using a network abstraction, and combined published arrival routes, used dynamic programming to solve the integrated control problem. Bosson et al. [START_REF] Bosson | Optimizing integrated arrival, departure and surface operations under uncertainty[END_REF] formulated spatial and temporal separations in terminal airspace and extended with surface operations to integrate taxiway and runway operations. Frankovich [START_REF] Frankovich | Air traffic flow management at airports: A unified optimization approach[END_REF] proposed unified approaches on both strategic and tactical levels to optimize the traffic flowing through an airport. In general, combining the airside and airspace problem and optimize together can gain more benefit. However, the complexity of the integrated problem would grow significantly as well.

In this work, we propose a methodology to address the integrated problem of AMAN, DMAN, and SMAN. This optimization problem is divided into two levels: a macroscopic level and a microscopic level. At the macroscopic level, we consider the terminal airspace management for arrivals and departures and airport capacity management through the abstraction model of terminal, taxi network, and runway. At the microscopic level, the ground movement and the departure runway scheduling problem with a detailed description of the airport are considered.

The remaining parts of this paper are organized as follows. Section II presents the mathematical model of the macroscopic level optimization and the microscopic level optimization. A metaheuristic method combined with a time decomposition approach for solving the integrated problem is presented in Section III. Computational experiments with the proposed methodology are presented in Section IV. Conclusions and perspectives are discussed in Section V.

II. PROBLEM DESCRIPTION AND MATHEMATICAL FORMULATION

Coordination between the AMAN, DMAN, and SMAN is an important issue to improve the efficiency and the predictability of airports. Current AMAN systems are able to predict the landing times 30 minutes in advance with quite a good accuracy [START_REF] Durand | Metaheuristics for Air Traffic Management[END_REF], while SMAN and DMAN face more uncertainties of taxi time, start-up time, takeoff time etc. The complex interactions and different anticipation times between AMAN, DMAN and SMAN schedules motivate us to tackle the airport traffic management at two levels: First, at the macroscopic level, a Terminal Maneuvering Area (TMA) route graph for arrival and departure is used for conflict detection and resolution in the airspace. The airside is modeled as an abstraction network: terminal, taxi network, and runway are 1 ICRAT 2018 seen as specific resources with a defined maximum capacity. Optimization will be carried out from the entry of TMA until the exit of this TMA. Secondly, the optimized results from the macroscopic level will be put into the microscopic level, ground operations and departure runway scheduling with a detailed description of the airport are considered and optimized. Mathematical models of the two-level optimization problem are presented in the remaining parts of this section.

A. Macroscopic model of integrated airport and TMA traffic management

This subsection describes the integrated optimization problem of airport and TMA at the macroscopic level, in order to resolve airspace conflicts (which implicitly represents potential workload of air traffic controllers), to mitigate airport congestions and to reduce delays. We first describe the network model of TMA and airport surface. Then, we present an integrated global optimization model of TMA and airport, giving flight input data, defining decision variables, clarifying constraints, and introducing objective function. Fig. 1 displays an example model of a TMA route network of Paris Charles De-Gaulle (CDG) airport. CDG is one of the busiest passenger airports in Europe, composed of four parallel runways (two for landings and two for take-offs) and three terminals. The west configuration with runway 26L/26R and 27L/27R is illustrated in Fig. 1, arrival and departure procedures are represented by black and gray colors respectively. In the arrival procedure, four-corner routes fuse into one to each runway. Each of the starting nodes of these four routes is an IAF. The set of entering points here is N e = {MOPAR, LORNI, OKIPA, BANOX}. For the departure procedure, one route starts at the runway threshold and ends with one of the SID waypoints in the set N x = {OPALE, NURMO, NEPAR, BEKOS, DOPAP, RBT, LESGA}. Different components of airport are considered using a network abstraction. Runways and terminals are modeled as resources with a specific capacity. We only take into account the overall capacity of a terminal without considering its individual gates. Taxiway is seen as a network with a threshold of total allowed number of taxi-in and taxi-out aircraft. The network model of TMA and airport surface is illustrated in Fig 2.

2) Given data: Assume that we are given a set of flights (or aircraft), F = A ∪ D ∪ AD, where A is a set of arrivals, D is a set of departures and AD is a set of arrival-departures, i.e., aircraft that arrive at the airport and depart again after a turnaround duration.

For each flight f ∈ F, the following data is given: wake turbulence category for f ∈ F, assigned terminal for f ∈ F, entering waypoint at TMA for f ∈ A AD, exit waypoint at TMA for f ∈ D AD, taxi-in duration for f ∈ A AD, taxi-out duration for f ∈ D AD, initial landing runway number for f ∈ A AD, initial departure runway number for f ∈ D AD, initial off-block time for f ∈ D, turnaround duration for f ∈ AD and initial exit time at the exit SID waypoint for f ∈ D AD. Moreover, we know:

• T 0 f : initial RTA (Required Time of Arrival) at the entering waypoint of TMA (f ∈ A AD); • V 0 f : initial speed at the entering waypoint of TMA (f ∈ A AD); • P 0 f : initial off-block time (f ∈ D AD), it is the earliest time that an aircraft is ready to depart from its parking position.

Here are the assumptions and simplifications we make for our model:

• Flights are assumed to be able to park at any gates in their assigned terminal; • We use an average taxi-in and taxi-out duration with regard to terminal and runway for each flight, due to the fact that we don't have information about gates at the macroscopic level;

• Each aircraft has a constant deceleration or acceleration in TMA.

3) Decision variables:

The optimization model we are using has five types of decision variables. First, we have to decide entering time at TMA, entering speed at TMA, and landing runway for arrivals:

• Entering time at TMA for f ∈ A AD: We assume that we are given a maximum delay and a minimum advance, denoted respectively ∆T max and ∆T min , which define the range of possible entering times in TMA. We therefore define, for each flight f ∈ A AD, a time-slot decision variable t f ∈ T f , where

T f = {T 0 f +j∆T |∆T min /∆T j ∆T max /∆T, j ∈ Z},
where ∆T is a discretized time increment, whose value is to be set by the user. In this paper, we choose ∆T = 5 seconds, ∆T min = -5 minutes, ∆T max = 30 minutes.

• Entering speed in TMA for f ∈ A AD: We define an entering speed decision variable v f ∈ V f , where

V f = {V min f + j∆ v f | j ∈ Z, |j| (V max f -V min f )/∆ v f }, where ∆ v f is a (user-defined) speed increment, V min f and V max f
are given input data corresponding to the minimum and maximum allowable speeds for aircraft f . In this study, we set

V min f = 0.9V 0 f , V max f = 1.1V 0 f and ∆ v f = 0.01V 0 f . • Landing runway for f ∈ A AD: r l
f is the landing runway decision for arrivals. Runway aircraft assignment is used to balance the capacity when one runway gets overloaded while another is still able to accommodate more aircraft. It enables to increase overall throughput with less delay comparing with the case where aircraft have no options to change their landing runway. Secondly, we decide departure runway and pushback time for departures:

• Departure runway for f ∈ D AD: r d f is the departure runway decision for departures. Similarly, it's possible to yield flights to another departure runway when the current assigned one is busy.

• Pushback time for f ∈ D AD: We define a pushback time decision variable p f ∈ P f , where

P f = {P 0 f + j∆T |0 j ∆T p max /∆T, j ∈ N} In contrast
to the entering time decision at TMA for arrival flights, we can only delay departure with regard to its earliest initial off-block time. ∆T p max = 15 minutes in this study. To summarize, our decision vector is x = (t, v, l, d, p), where t is the vector whose f th component is the decision variable t f , v is the vector whose f th component is the decision variable v f , l is the vector whose f th component is the decision variable r l f , d is the vector whose f th component is the decision variable r d f ,and p is the vector whose f th component is the decision variable p f (all of which correspond to flight f ).

4) Constraints and Objectives:

We have three main constraints: wake turbulence separation as shown in Table I, single runway separation for arrivals and departures as shown in Table II and III respectively, and maximum capacities for terminal and for taxi network. In order to take into account these constraints, the model is designed to resolve conflicts in the air, to reduce airside capacity overload, and to reduce flight delays. The number of conflicts is evaluated by node and link conflicts detection. The airside capacity overload involves runways, terminals and taxiway network evaluation. The flight delays include total RTA delay and total pushback delay. We make a relaxation of these constraints into our objectives.

Our objective function, to be minimized is therefore a weighted sum of these functions:

γ a A(x) + γ s S(x) + γ d D(x)
where γ a , γ s , and γ d are weighting coefficients for the total number of conflicts in airspace, A(x), the airside capacity overload, S(x), and the flight delays D(x) respectively. D(x) are defined as the total time deviation between the optimized and initial values of RTA and pushback time. Next, we will introduce how to evaluate the airspace conflicts A(x) and the airport congestions S(x).

5) Conflicts detection in the TMA: In this paper, we make an assumption that arrival routes and departure routes are separated in altitude, which corresponds to real-world TMA operations. Therefore, we detect conflicts separately for arrivals and for departures. Considering the above-described TMA route network structure, two kinds of conflicts are defined:

• Link conflict: For each given link, we check twice whether a conflict occurs, i.e., the minimum wake turbulence separation (shown in Table I) is violated: at the entry and at the exit of the link. Moreover, we ensure that the order of aircraft sequence remains the same along the link. This enables to detect aircraft passing another one. • Node conflict: If no link conflict is detected, waketurbulence separation can be guaranteed. However, at the intersection of two successive links, violation of the horizontal separation requirement between any two consecutive aircraft (3 NM in TMA) may still occur. Therefore, we check that when an aircraft flies over a node, the horizontal separation with other aircraft is maintained. Note that once the decision variable values are set, we can calculate the corresponding times at which the aircraft passes each node and each link. Then, we use these time values to evaluate the number of link and node conflicts. The conflict detection methodology is described in detail in [START_REF] Ma | Merging flows in terminal maneuvering area using time decomposition approach[END_REF].

6) Congestion evaluation in the ground side: The ground side capacity congestion involves runways, terminals and taxi network evaluation. S(x) is evaluated by accumulating the sum of runway separation violation, terminal overload and taxi network overload. • Runway congestion evaluation: One runway can be modeled as a specific resource with capacity 1. During high traffic demand periods, the upcoming flights may violate the separation rules for arrivals (as shown in Table II), for departures and between departures and arrival crossings (shown in Table III) and cause runway congestions. Therefore, we note the sum of accumulated time of separation violation for all pairs of aircraft and the total number of conflicts as an indicator for our runway evaluation. • Terminal and taxiway congestion evaluation:

We have two metrics to measure the terminal congestion. First, the maximum overload number is calculated based on the difference between the actual total number of aircraft in the terminal and the given terminal capacity. This metric gives us an idea of the time at which severe congestion occurs. However, the maximal overload does not provide sufficient information on the level of congestion. Therefore, another important metric to consider is the average amount of time during which aircraft experience congestions in the terminal. Let us consider simple example to show how we propose to measure the terminal congestion level. As illustrated in Fig. 3, suppose that we have one terminal with three gates (i.e., the capacity is 3), and 5 flights turnaround in this terminal. The upward (respectively, down) arrow represents the inblock (off-block) time of one aircraft, linked by a dotted Here, the maximal terminal occupancy is 5, therefore the maximal overload is 2. We calculate the total congestion time as well, which is 47+8=55 minutes here (the red surface shown in Fig. 3). The taxiway network congestion can be measured in a similar way. We note as well the maximum overload and the total congestion time for taxi network evaluation.

More details about congestion evaluation can be found in our previous work [START_REF]Integrated optimization of terminal manoeuvring area and airport[END_REF]. After optimization at the macroscopic level, flight landing time, landing runway and departure runway assignment are fixed, and pushback time is an initial input. We then consider a detailed model of airport including runway holding points, taxiways, gates at the microscopic level to find optimized taxi route, start-up time at gate, runway waiting time, and takeoff time. In CDG, Ground controllers handle all intermediary taxiing routes. Local controllers and Apron controllers handle respectively the runway area and parking areas [START_REF] Chua | Simulating air traffic control ground operations: Preliminary results from project modern taxiing[END_REF]. Due to this different area classification and in order to simplify the problem, our model considers that taxiway starts with a defined meta-gate shown in Fig. 4, which is the exit point of the ramp area and the entry point of the taxiway area, and ends with runway entry point for departures. For arrivals, taxiing path starts with runway exit point, and ends in meta-gate. We model CDG airport with a node-link graph. Each node can be a runway entry/exit point, a holding point, an intersection or a meta-gate. Each link is composed of two nodes. We have in total 392 nodes and 617 links.

B. Microscopic Model of ground operations and runway scheduling

1) Input data: With a short planning horizon at the microscopic level, the previous mentioned arrival-departure is divided into two operations: arrival and departure. For each f ∈ F , the following input data are given: wake turbulence category, meta-gate, runway entry point for departure or runway exit point for arrival, initial holding point at runway threshold, and a set of alternate routes, R f , connecting the origin and the destination of f . Moreover, the optimized landing time, assigned landing runway for arrival and the optimized off-block time, assigned takeoff runway for departure at the macroscopic level become input data at the microscopic level.

We have some assumptions in order to simplify the problem while keeping some level of reliability.

• Aircraft taxi with a constant speed for a given link;

• Ramp area is beyond the scope of this work, instead we use the notion of meta-gate. 2) Decision variables: For each flight f ∈ F , the decision variables are defined as follows:

• r f ∈ R f : taxi-in or taxi-out route. More details about alternate taxiing routes generation can be found in [START_REF] Ma | A study of tradeoffs in airport coordinated surface operations[END_REF]; • t h f : holding time (waiting time at runway threshold for departures and time spent in runway crossing queues for arrivals). The maximum holding times for departures and arrivals are 10 minutes and 3 minutes respectively. It is discretized with a time slot of 5 seconds; • p f : pushback time. The maximum pushback delay is 15 minutes. Similarly, it is discretized with a time slot of 5 seconds; • Minimum taxi separation of s = 60 meters [START_REF] Deau | Airport surface management and runways scheduling[END_REF] between two taxiing aircraft. • Departure runway wake turbulence separations considering arrival crossings shown in Table III.

• Holding point capacity (the maximum number of flights waiting at holding point). For arrivals, it is usually one or two due to the fact that a landing flight can not hold too long time to vacate the position for the next landings. For departures, it's a parameter called runway pressure adjusted by controllers considering demand over the period. Based on the route network structure in Fig. 4, and in order to express the previous mentioned separation standards and capacity constraints, we define four types of conflicts: node conflict, link conflict, runway conflict, and holding conflict depending on the decision variables.

• Ground node-link conflict: We apply a conflict detection method similar to the macroscopic level with different separation standards. Moreover, we add the bi-directional link conflict detection on the ground, i.e., two aircraft using a link in opposite directions simultaneously. More details can be found in [START_REF] Ma | A study of tradeoffs in airport coordinated surface operations[END_REF]; • Runway conflict: For each runway and for two successive flights (departure or arrival crossing), same method is applied as in the macroscopic model to detect the separation violation.

• Holding conflict: For each holding point, we first make sure that the sequence of waiting flights remains the same. Then, by calculating the maximum number of aircraft simultaneously waiting in the queue, we compare it with the maximum holding capacity. If it exceeds the maximum holding capacity, we increase the total number of conflicts by the exceeded capacity. The total sum of these four types of conflicts is denoted as C. Then the previous separation and capacity constraint is transformed to C = 0 (conflict-free).

4) Objectives: The objective function that we want to minimize is:

C + α f ∈D (p f -P 0 f ) + β f ∈F h f ,
where

• C : Total number of conflicts;

• f ∈D (p f -P 0 f ): Total pushback delay; • f ∈F h f : Total holding time.
and α and β are weighting coefficients corresponding to pushback delays and holding time respectively. Even though we use relaxation on conflict constraints, small values of weighting coefficients are chosen in order to ensure that conflict-resolution is the first priority, and conflict-free solution is reached at last. Next, we present the solution approaches to solve this twolevel integrated optimization problem.

III. SOLUTION APPROACHES

It is known that even the sub-problem of this integrated optimization problem at the macroscopic level, aircraft landing scheduling, is NP-hard [START_REF] Beasley | Scheduling aircraft landings -The static case[END_REF]. Since the complexity of the ICRAT 2018 integrated problem would grow, when in practice the computational time is critical. Heuristics and hybrid methods may have more potential than exact approaches for tackling this problem [START_REF] Atkin | The airport ground movement problem: Past and current research and future directions[END_REF]. In this paper, we propose a time decomposition approach combined with a simulated annealing algorithm to address this problem. In the following of this section, the time decomposition approach and simulated annealing algorithm are introduced in detail.

A. Time sliding-window decomposition approach

This approach addresses the original problem by decomposition into several sub-problems using a sliding window in order to reduce the problem size and consequently the computational burden. This specific approach is generic and can be extended and applied to other real-time operation problems. Fig. 6. Overall optimization process summary Fig. 6 illustrates how sliding window approach works. Each aircraft is classified into four different status: completed, ongoing, active and planned, based on its operation time interval relative to the sliding window. Completed means that the aircraft has already finished its operations, before the start of the current sliding window. On-going means that a part of the flight trajectory is still in the sliding window, therefore it may impact the assignment of the following aircraft. We can change the decision variables of active aircraft to optimize the operations. Planned flights will be considered in the next sliding windows.

At each step, we take into account the active and ongoing aircraft in the sliding window interval to be optimized. The simulation process takes the decision proposed by the optimization algorithm and simulates the associated flight in order to produce the objective function and the vector of performance. The objective function and the performance indicators provided by the simulation process guide the optimization module to search for better solution. Then, the optimization window recedes in the future by a fixed time step. The status of aircraft are updated, a new set of flights waiting to be addressed are considered, and the optimization process is repeated. Detailed description can be found in [START_REF] Ma | Merging flows in terminal maneuvering area using time decomposition approach[END_REF].

Remind that the anticipation time for AMAN and for DMAN-SMAN are different, our sliding window approach are applied with two different time horizons, i.e., two hours of time window with a time shift of thirty minutes at the macroscopic level, and one hour of time window with a time shift of fifteen minutes at the microscopic level. In future work, more study is required on the choices of window length and time shift.

B. Simulated annealing

Simulated Annealing (SA) [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF] is a meta-heuristic that simulates the annealing of a metal, in which the metal is heated up and slowly cooled down to move towards an optimal energy state. It can easily be adapted to large-scale problems with continuous or discrete search spaces. In SA, the objective function to be minimized is analogous to the energy of the physical problem. A global parameter T is used to simulate the cooling process. A current solution may be replaced by a random "neighborhood" solution accepted with a probability e ∆E T , where ∆E is the difference between corresponding function values. We start the cooling process from a high initial temperature T 0 (which can be determined by a heating process or defined by user), the current solution changes almost randomly at a higher temperature, thus the algorithm is able to trap out of local minima. The decrease of temperature may follow different laws, such as linear law, geometric law, etc. At each temperature step, a number of iterations are executed. The probability to accept a degrading solution become smaller and smaller when T decreases. Therefore, at the final stages of the annealing process, the system will converge to a near-global or global optimum. In our problem, after several empirical tests, some user-defined parameters related to the SA method are listed in Table IV. To generate a neighborhood solution, instead of simply choosing randomly a flight in the active-flight set, we note for each aircraft the number of conflicts or the time of congestion as its air and ground performance respectively. Air performance involves link and node conflicts, and ground performance involves runway, taxiway network and terminals congestions at the macroscopic level, or taxiway node-link conflicts and runway holding point conflicts at the microscopic level. It is better to first change the decisions of aircraft which are mostly involved in conflicts than the ones with less impact in order to reduce conflicts. The performance metric can help us to better focus on the most charged and congested periods. The fact that our neighborhood definition is based on the air and ground flight performance increases the likelihood that a flight involving many conflicts, or experiencing severe congestions, will be chosen.

The SA terminates the execution either if the maximum number of transitions and the minimum temperature are achieved, or if an acceptable or optimal solution is obtained.

Next, we apply the simulated annealing algorithm combined with time decomposition approach to resolve the integrated optimization problem of arrival, departure, and surface operations.

IV. RESULTS

In this section we present some test problems and analyze the associated results. We test our methodology on a one-day real data case at Paris CDG Airport. Numerical results are presented and discussed. The overall process is run on a 2.50 GHz core i7 CPU, under Linux operating system PC based on a Java code.

A heavy day of traffic on July 11th, 2017 is selected. We select only the flights that have all information necessary for simulation. Thus, we obtained the flight set consisting of 1435 flights, including 719 departures and 716 arrivals. We have a total of 342 Heavy (24%) and 1093 Medium (76%) aircraft. In Fig. 7, red line represents the initial gate occupancy during the day, while blue curve shows the initial taxi network occupancy. The maximum gate occupancy and the maximum taxi network occupancy are 137 and 31 respectively. In order to test the performance of overload mitigation, we set the maximum capacity to be 130 for terminal, and 25 for taxi network. The optimization results show an improvement for mitigating congestions. Both the maximum gate occupancy and the maximum taxi network occupancy are smaller than their capacity limits without any overload compared to the initial situation. The proper adjustment of time decision variables can mitigate both single peak hour (for terminal) and multiple peak hours (for taxi network). The optimized terminal occupancy curve is shifted to the right compared to initial one because the main strategy is to delay arrivals.

A. Macroscopic level results

Remind that at the macroscopic level, we allow the possibility of runway assignments. In order to investigate how runway assignments can impact flight delays and conflict resolution, we compare the case of using initial landing and departure runway to the case of assigning runway. Fig. 8 gives an example of two sliding windows optimization evolution; it shows the value of two criteria (number of conflict and total delays) during the cooling process of SA. With both landing and departure runway assignments, we achieve a less conflict and less delay solution. When they both reach conflict-free solution as illustrated in the second sliding window, runway assignment case still has less delays. The converging speed of the two criteria is also faster. Landing runway throughput of 26L and 27R in the morning period is illustrated in Table V. The radar data shows that between 6 am and 7 am, both landing runways are in high traffic demand, while between 7 am and 8 am, runway throughput is largely decreased. Also, an imbalance of landing runway throughput can be observed from 8 am to 11 am. After optimization, the landing flow is more balanced with regard to both the time period and the two runways. Moreover, the traffic shifted to the next time period is also related to the congestion mitigation as shown in Fig. 7. Next, we extract the period between 9 am and 10 am to analyze the results at the microscopic level.

ICRAT 2018

B. Microscopic level results

In order to check the impact of new assigned runway on ground performances, we make a comparison test: First, we launch the optimization process using the initial landing and takeoff runways and the initial start-up time (landing time for arrivals and pushback time for departures) obtained from radar data as input. This case is denoted as "Initial Case". Then, we launch the process using the results from the macroscopic level with assigned runway and optimized start-up time. This case is denoted as "Assigned Case". Table VI depicts the total holding time of arrival crossings for landing runway 27R and 26L. One can observe a decrease by 21% of waiting time at runway threshold after landing from 695 seconds in Initial Case to 550 seconds in Assigned Case. For departures, in Table VII, a decrease of total holding time from 645 seconds to 75 seconds and a decrease of total pushback delay from 3050 seconds to 225 seconds are achieved for runway 26R. Because in Initial Case, we have 31 landing flights from runway 26L waiting to cross 26L, thus causes a heavy waiting time for departures, while in Assigned Case, we have 22 arrivals. The reduction of delay is of practical significance, because in CDG, runways 26L/26R are usually more charged than another side. Even when we have an increase of total pushback delay from 695 seconds to 1330 seconds for runway 27L, the total pushback delay for both departure runways decreases by 58% compared to Initial Case.

V. CONCLUSIONS

This paper addresses the integrated optimization problem of arrival, departure, and surface operations. A two-level approach is proposed: First, at the macroscopic level, a TMA route graph for arrival and departure is used for conflict detection and resolution in the airspace. The airside is modeled as an abstraction network: terminal, taxi network, and runway are seen as specific resources with a defined maximum capacity. Secondly, at the microscopic level, a detailed description of airport with runway holding points, taxiways, and gates is considered. The system gets the optimized flight information from the macroscopic level, and decides ground control parameters. This two-level problem is solved by decomposing into smaller sub-problems using two time sliding windows.

Results show that at the macroscopic level, proper adjustment of time decisions would efficiently mitigate airport congestion. Runway assignment in peak hour can reduce flight delays. At the microscopic level, we also observe a significant decrease of pushback delay and waiting time at runway threshold after runway assignment.

Future research will include uncertainty analysis with regard to arrival time, pushback time, taxi time etc. More scenarios need to be tested and analyzed with both levels. Moreover, an extension to several coordinated airports will be studied in order to minimize the overall congestion over this set of airports.

Fig. 1 .

 1 Fig. 1. Terminal route network of arrivals and departures in CDG in west configuration 1) Network model of TMA and airport surface: We model the TMA arrival and departure routes by a graph,G(N , L), in which the aircraft are allowed to fly in TMA airspace, where N is the node set and L is the link set. Each route is defined by a succession of nodes and links; the first link starts from an entering point, a so-called Initial Approach Fix (IAF) for arrivals and runway threshold for departures, and the last link ends at the exit point (runway threshold for arrivals and last SID waypoint for departures).Fig.1displays an example model of a TMA route network of Paris Charles De-Gaulle (CDG) airport. CDG is one of the busiest passenger airports in Europe, composed of four parallel runways (two for landings and two for take-offs) and three terminals. The west configuration with runway 26L/26R and 27L/27R is illustrated in Fig.1, arrival and departure procedures are represented by black and gray colors respectively. In the arrival procedure, four-corner routes fuse

Fig. 2 .

 2 Fig. 2. Network model of TMA and airport surface

Fig. 3 .

 3 Fig. 3. Example of terminal congestion evaluation

Fig. 4 .

 4 Fig. 4. CDG airport model in the west configuration at the microscopic level

Fig. 5 .

 5 Fig. 5. CDG south side runway layout • h f : holding point for arrival. CDG south-side runway layout shown in Fig. 5 motivates us to use arrival holding point as decision variable. In reality, simultaneous flight crossings can enhance departure runway throughput. 3) Constraints: Airport operational constraints are taken into account:

Fig. 7 .

 7 Fig. 7. Comparison of initial occupancy and optimized occupancy for terminal and taxi network

Fig. 8 .

 8 Fig. 8. Evolution of the two criteria for different runway decisions in two sliding windows

TABLE II SINGLE

 II -RUNWAY SEPARATION REQUIREMENTS FOR ARRIVALS (IN SECONDS).

	Category	Trailing Aircraft Heavy Medium Light
	Leading Aircraft	Heavy Medium Light	96 60 60	157 69 69	207 123 82

TABLE III SINGLE

 III -RUNWAY SEPARATION REQUIREMENTS FOR DEPARTURES AND ARRIVAL CROSSINGS (IN SECONDS).

	Category	Trailing Aircraft Heavy Medium Light	Crossing
		Heavy	90	120	120	60
	Leading	Medium	60	60	60	60
	Aircraft	Light	60	60	60	60
		Crossing	40	40	40	10

TABLE V COMPARISON

 V OF LANDING RUNWAY THROUGHPUT. 26L AND 27R ARE

		TWO LANDING RUNWAYS
		Runway throughput	Runway throughput
		from radar data	from optimized results
	Period	26L	27R	26L	27R
	06:00-07:00	32 (48%)	34 (52%)	28 (50%)	28 (50%)
	07:00-08:00	16 (53%)	14 (47%)	20 (45%)	24 (55%)
	08:00-09:00	25 (60%)	17 (40%)	19 (56%)	15 (44%)
	09:00-10:00	31 (62%)	19 (38%)	22 (54%)	19 (46%)
	10:00-11:00	20 (67%)	10 (33%)	19 (49%)	20 (51%)

TABLE VI TOTAL

 VI HOLDING TIME OF ARRIVAL CROSSINGS (IN SECONDS)

	Landing runway	27R	26L	Total
	Initial Case	210	485	695
	Assigned Case	425	125	550
	TABLE VII
	TOTAL HOLDING TIME AND PUSHBACK DELAY COMPARISON FOR
	DEPARTURES (IN SECONDS)
	Departure runway		27L	26R	Total
	Total holding time in Initial Case	645		645	1290
	Total holding time in Assigned Case	570		75	645
	Total pushback delay in Initial Case	695	3050	3745
	Total pushback delay in Assigned Case	1330	225	1555

ACKNOWLEDGMENTS

This work has been partially supported by CAUC, by China Scholarship Council (CSC) and by the Scientific Research Foundation of CAUC through grant number 2017QD02S. We would like to thank Serge Roux for his assistance with data, technical support and helpful discussions. We would like to thank SNA-RP/CDG-LB for providing the traffic data.