V Bergelson

A Leibman

E Lesigne

Complexities of finite families of polynomials, Weyl systems, and constructions in combinatorial number theory

We introduce two notions of complexity of a system of polynomials p 1 , . . . , p r ∈ Z [n] and apply them to characterize the limits of the expressions of the form

where T is a skew-product transformation of a torus T d and A i ⊆ T d are measurable sets. The dynamical results obtained allow us to construct subsets of integers with specific combinatorial properties related to the polynomial Szemerédi theorem.

The Szemerédi theorem on arithmetic progressions ( [Sz]) states that if a set E ⊆ Z has positive upper Banach density, then for any r ∈ N, there exist integers a and n = 0 such that {a, a + n, a + 2n, . . . , a + rn} ⊂ E. ( 1 been extended to multidimensional "polynomial" progressions ( [BL]). In particular, it was proven in [BL] that if p 1 , . . . , p r are integral polynomials (that is, polynomials with rational coefficients taking integer values on Z) with p i (0) = 0 for i = 1, . . . , r, then any set E ⊆ Z with d * (E) > 0 contains configurations of the form C(a, n) = {a, a+p 1 (n), a+p 2 (n), . . . , a+ p r (n)} with n ∈ Z \ {0}. Moreover, in the linear case as well as the polynomial case, the set n ∈ Z : C(a, n) ⊂ E for some a ∈ Z is syndetic, i.e., this set meets any sufficiently long interval in Z. (See [F1] and [BM].)

The homogeneity condition, p i (0) = 0, in the formulation is quite essential. Thus for p(n) = 2n + 1, a simple non-homogeneous polynomial, the 2-element configuration {a, a + p(n)} does not appear in E = 2Z or E = 2Z + 1. (By a change of variables q i (n) = p i (n -n 0 ) the homogeneity condition can be replaced by the condition that the polynomials vanish simultaneously for some n 0 ∈ Z.)

It is significant that the foregoing counterexample to existence of a non-homogeneous configuration is rooted in a "non-randomness" displayed by the set E. We will be giving a precise definition of "randomness" of a set of integers, and for sets E with this property and d * (E) > 0, every non-trivial polynomial progression type will occur in E. (A polynomial progression type is trivial if for some i = j, p ip j = const.) For sets with only the condition d * (E) > 0, the existence of a specific non-homogeneous configuration depends on the configuration in question. For example, as we will see, one can produce a set E with d u (E) > 0 so that all linear 2-term configuration occur (and moreover, do so in abundance) but some linear 3-term configurations do not occur.

The length of the configuration plays a role here and the foregoing example is generalized in the following. One can ask quite generally if for two kinds of configurations there exists a set of positive upper density containing configurations of one kind but not of the other kind. We will give a partial answer to this based on an appropriate notion of the "complexity" of a polynomial configuration, for which, given polynomial systems P = {p 1 , . . . , p r } and Q = {q 1 , . . . , q s } of different complexity, there exists a set E with d u (E) > 0 containing one configuration but not the other. To each system of homogeneous (vanishing at 0) polynomials, P = {p 1 , . . . , p r } we asign a complexity index and determine a particular set E P of positive density for which this complexity index will play a role. Namely, there will be a non-homogeneous version of a P -progression, specifically, C(a, n) = a, a + p 1 (mn + l), a + p 2 (mn + l), . . . , a + p r (mn + l) for some m, n = 0 so that no C(a, n) appears in E P with n = 0, while at the same time, for every polynomial system Q = {q 1 , . . . , q s } of complexity less than P , the analogous configurations C (a, n) = a, a + q 1 (mn + l), a + q 2 (mn + l), . . . , a + q s (mn + l) appear in E P for a syndetic set of n ∈ Z for every choice of m and l. The foregoing can be strengthened and we can speak of arbitrary "composite Q-configurations" a, a + q 1 (h(n)), a + q 2 (h(n)), . . . , a + q s (h(n)) for any nonconstant integral polynomial h, and these too will be found in E P , when the complexity of Q is less than that of P , for a syndetic set of n.

Remark. As a matter of fact, we will find it convenient to introduce not one but two complexity indices, W (P ) and V (P ) (Weyl complexity and Vandermonde complexity). The reason for doing so and the pertinent details will be clarified in the ensuing discussion.

B. Dynamically defined sets of integers

As in the ergodic theoretical proof of Szemerédi's theorem (as well as its extension to polynomial progressions), the analogy between sets of integers with positive upper Banach density and subsets of positive measure in the state space of a dynamical system plays a role in the present discussion, and the sets E P referred to in the foregoing section will be defined using certain dynamical systems called Weyl systems. We will not be using ergodic theoretic techniques explicitly, but some important ergodic theoretical ideas underly the construction that we will try to explain in this section.

We recall that an ergodic system (X, B, µ, T ) consists of a probabilty space (X, B, µ) and an (invertible) measure preserving transformation T : X -→ X having no nontrivial A ∈ B (0 < µ(A) < 1) invariant. Ergodic systems form a plentiful source of sets of integers of positive density. By the ergodic theorem, if A ∈ B has µ(A) > 0, then for almost every x ∈ X the visiting time set E(A, x) = {n : T n x ∈ A} has density equal to µ(A), and particularly d * (E(A, x)) > 0. A simple but crucial observation is that outside of a (fixed) set of measure 0 of points x ∈ X, a configuration C(a, n) = a, a + p 1 (n), a + p 2 (n), . . . , a + p r (n) will occur in E(A, x) if {p 1 (n), p 2 (n), . . . , p r (n)} n∈Z is a "recurrence pattern" for A, i.e., if for some n

µ A ∩ T -p 1 (n) A ∩ . . . ∩ T -p r (n) A > 0. (0.1)
The initial a is determined by the condition T a x ∈ A ∩ T -p 1 (n) A ∩ . . . ∩ T -p r (n) A and thus (for a.e. x) forms a set of positive density. A converse of the foregoing is also valid: if A ∩ T -p 1 (n) A ∩ . . . ∩ T -p r (n) A = ∅ (rather than just a set of measure 0) then clearly C(a, n) cannot occur in any E (A, x). This makes it plausible that sets of the form E(A, x) will play an important role for our purposes. The notion of recurrence patterns for ergodic systems has been studied extensively, and it is known ( [B]) that for the class of weakly mixing (WM) systems, these include all polynomial configurations (homogeneous or not) provided the p i have positive degree and do not differ by constants. We can now give a precise definition to the notion of randomness of a set E alluded to in §A. We call E a WM set if E = E(A, x) for an invertible WM system (X, B, µ, T ) where x is "generic" for (X, B A , µ, T ); that is, 1 (B) for every set B ∈ B A , the algebra of sets spanned by {T n A} n∈Z .

N N n=1 1 B (T n x) -→ µ
For general ergodic systems it has been shown ( [BL]) that any system of homogeneous polynomials forms a recurrence pattern, and this underlines the fact that homogeneous progressions occur for any E with d * (E) > 0. (Here E need not have the form E(A, x) exactly as above, but this will hold for an extended notion of genericity.)

In this paper we confine ourselves to the Weyl systems. A Weyl system is an ergodic system (X, B, µ, T ) where X is a compact commutative Lie group (which is either a torus or the product of a torus and of a finite commutative group) and T is a unipotent affine transformation thereof. To motivate the special role of Weyl systems in our discussion, it will be instructive to make reference to the notion of characteristic factors for nonconventional ergodic averages ( [START_REF] Host | Non-conventional ergodic averages and nilmanifolds[END_REF] and [Z]). Recall that a factor (Y, D, ν, S) of an ergodic system (X, B, µ, T ) is an ergodic system with a measurable, measure preserving map

π: X -→ Y satisfying π•T = S•π. One says that (Y, D, ν, S) is a characteristic factor of (X, B, µ, T ) for the pattern {p 1 (n), . . . , p r (n)} n∈Z if for any set of functions f 1 , . . . , f r ∈ L ∞ (X) and their "projections" f1 , . . . , fr ∈ L ∞ (Y ), lim N -M →∞ 1 N -M N n=M +1 f 1 (T p 1 (n) x) . . . f r (T p r (n) x) - 1 N -M N n=M +1 f1 (T p 1 (n) x) . . . fr (T p r (n) x) L 2 (X) = 0.
The consequence of this relevant for our purposes is that for a system (X, B, µ, T ) and a characteristic factor (Y, D, ν, S)

lim N -M →∞ 1 N -M N n=M +1 µ(A ∩ T -p 1 (n) A ∩ . . . ∩ T -p r (n) A) > 0 (0.2)
for every A ∈ B with µ(A) > 0 if and only if lim

N -M →∞ 1 N -M N n=M +1 µ(B ∩ S -p 1 (n) B ∩ . . . ∩ S -p r (n) B) > 0 (0.3) for every B ∈ D with ν(B) > 0.
A second fact relevant to us is the fundamental result in [START_REF] Host | Non-conventional ergodic averages and nilmanifolds[END_REF] and [Z] asserting that, for any linear pattern, every dynamical system has a characteristic factor which is a nilsystem or an inverse limit of such (a pro-nilsystem). A nilsystem is a system (Y, D, ν, S) where Y is a homogeneous space G/Γ of a nilpotent Lie group G and Γ is a co-compact subgroup of G, and there is an element g ∈ G so that

S(xΓ) = gxΓ for each x ∈ G. Let G 2 = [G, G] and G l = [G l-1 , G]
for l ≥ 2; we define the "level" of a nilpotent group G as the first l such that G l+1 = {1}. In [START_REF] Host | Non-conventional ergodic averages and nilmanifolds[END_REF] and [Z], for every system X and every k ∈ N a natural factor with the structure of a level k pro-nilsystem is constructed; we will call it the kth HKZ factor of X. It is proven in [START_REF] Host | Convergence of polynomial ergodic averages[END_REF] and [L1] that for any system X and any "polynomial pattern" P = {p 1 (n), . . . , p r (n)} a certain HKZ factor of X is characteristic. The minimal k such that for every system X the (k -1)st HKZ factor of X is characteristic with respect to P is called the complexity of P = {p 1 , . . . , p r } and is denoted by C(P ). The Weyl complexity of P , W (P ), is the complexity of P measured with respect to Weyl systems only; it is an open question whether W (P ) may differ from C(P ).

Suppose now that E(A, x) is a dynamically defined set corresponding to a system (X, B, µ, T ), and that A ∩ T -p 1 (n) A ∩ . . . ∩ T -p r (n) A = ∅ for all n. Then (0.2) does not hold and if (Y, D, ν, S) is a nilsystem which is a characteristic factor for {p 1 , . . . , p r }, we will have for some

B ∈ D with ν(B) > 0, 1 N -M N n=M +1 µ(B ∩ S -p 1 (n) B . . . S -p r (n) B) -→ N -M →∞ 0.
This implies that for most y ∈ Y , E (B, y) will be a set of positive density in which configurations {a, a + p 1 (n), . . . , a + p r (n)} are rare, and it makes it plausible that for some y they will be absent entirely from E (B, y). If this heuristic principle is valid then we can restrict to sets defined by nilsystems to obtain sets of positive density where certain polynomial progressions are absent. We remark now that Weyl systems can be viewed as a special class of nilsystems (see Section 3 below) and it will be shown in the sequel that these special systems will be adequate for our purposes. In the examples constructed from Weyl systems we will find a dichotomy: either a polynomial progression does not occur at all (nontrivially, i.e. not in the form (a, a, . . . , a)), or it occurs in "abundance". In the latter case the corresponding configurations C(a, n) occur in E with "positive density" of (a, n). This will accord with the dynamical property inherent in (0.2).

In a way, Weyl systems form a rather natural class of ergodic systems for the task at hand. Indeed, it follows from [B] that dynamically generated WM sets (namely, the visiting time sets coming from weakly mixing systems) contain all possible polynomial configurations of the form {a, a + p 1 (n), ..., a + p k (n)} provided the (not necessarily homogeneous) polynomials p i are not constant and do not differ by constants. Now, weak mixing is characterized by the absence of a Kronecker factor, namely the factor that is formed by a rotation on a compact monothetic commutative groups. It follows that dynamically generated sets of positive density with non-trivial combinatorial properties of the sort we are interested in should come from ergodic systems having nontrivial Kronecker factor. Since the Kronecker systems allow one to construct sets with rather restricted combinatorial properties (see the remark after Theorem 0.6 below), one is led to dealing with extensions of Kronecker systems, and Weyl systems form the simplest class of extensions which is sufficient for achieving the stated goals.

The actual calculation of W (P ) for a system P of polynomials will be carried out algebraically and we will find that a related calculation leads to another measure of complexity which we call Vandermonde complexity and denote by V (P ) (see Section 4). Our analysis will show that this parameter also plays a role in measuring the "size" of {(a, n) : C(a, n) ⊂ E}. The minimal complexity V = W = 1 is achieved by linearly independent systems of polynomials. Roughly speaking, the more linear relations are between polynomials p 1 , . . . , p r and their powers p k 1 , . . . , p k r , k ∈ N, the higher is the complexity of the system {p 1 , . . . , p r }, and the more difficult it will be to have associated configurations in a given set of integers.

Here are some values of complexities of polynomial systems:

1. V (p 1 , . . . , p r ) = W (p 1 , . . . , p r ) = 1 if the polynomials p i are linearly independent; 2. V (b 1 n, b 2 n, . . . , b r n) = W (b 1 n, b 2 n, . . . , b r n) = r, and V (b 1 p(n), b 2 p(n), . . . , b r p(n)) = W (b 1 p(n), b 2 p(n), . . . , b r p(n)) = r
for any nonconstant polynomial p and any nonzero distinct integers b 1 , . . . , b r ; 3. V (n, 2n, n 2 ) = 2 and W (n, 2n, n 2 ) = 3; 4. V (n, 2n, n 3 ) = W (n, 2n, n 3 ) = 2. (See Section 5 for details.)

C. Formulation of main results

Let (X, B, µ, T ) be a Weyl system. To make the discussion in this introduction more concrete, let us restrict ourselves to a standard Weyl system (X, T ):

X is the d-dimensional torus T d and T (x 1 , x 2 , . . . , x d ) = (x 1 + α, x 2 + x 1 , . . . , x d + x d-1 ), (x 1 , . . . , x d ) ∈ X, where α ∈ T is irrational. For k = 1, . . . , d+1, let L k = (0, . . . , 0, x k , . . . , x d ) ∈ X ,
and let X k-1 be the factor-torus X/L k (with the canonical projection X -→ X k-1 ). One can show (see Section 3) that the tori X 1 , X 2 , . . . are the HKZ factors of (X, T ). Let P = {p 1 , . . . , p r } be a system of (distinct) integral polynomials with zero constant term; then W (P ) = k iff X k-1 is a characteristic factor for P , and we have: Theorem 0.2. (See Proposition 6.2 below.) Let k = W (P ) and let A 0 , . . . , A r be measurable subsets of X independent of X k-1 . Then

lim N -M →∞ 1 N -M N n=M +1 µ A 0 ∩ T -p 1 (n) A 1 ∩ . . . ∩ T -p r (n) A r = r i=0 µ(A i ).
One can also show (see Lemma 6.3) that the (k -1)st factor X k-1 is "optimal" in this theorem and cannot be replaced by X k-2 .

The next, k-dimensional factor-torus X k = X/L k+1 of X is characteristic for P in a stronger sense: Theorem 0.3. (See Proposition 6.5 below.) Let k = W (P ) and let A 0 , . . . , A r be measurable subsets of X independent of X k . Then

lim n→∞ µ A 0 ∩ T -p 1 (n) A 1 ∩ . . . ∩ T -p r (n) A r = r i=0 µ(A i ).
Lemma 6.7 says that, again, X k cannot be replaced by X k-1 in this theorem.

Turning to the Vandermonde complexity, and interpreting X as the direct sum X k-1 ⊕ L k for any k, we have the following: Theorem 0.4. (See Proposition 6.9 below.) Let k = V (P ) and let A i = X k-1 × I i , i = 0, . . . , r, where I 0 , . . . , I r are subsets of L k of positive measure. Then lim

N -M →∞ 1 N -M N n=M +1 µ A 0 ∩ T -p 1 (n) A 1 ∩ . . . ∩ T -p r (n) A r > 0.
Again, X k-2 does not work for this theorem, at least for a nonconnected Weyl system; this follows from Proposition 7.5. The reader will find an example illustrating the above results at the beginning of Section 6.

The Weyl and Vandermonde complexities induce a hierarchy on the set of all systems of polynomials so that, applying the dynamical method to a suitable Weyl system, one can construct a set of integers which contains many configurations corresponding to systems of smaller complexities and no configuration of a certain form corresponding to a system of larger complexity. In order to give a more precise formulation of our results let us first introduce some notions describing the "largeness" and the "regularity" of occurrences of polynomial configurations in a set of integers.

For a set of integers E, we will say that E has uniform density α and write U D(E) = α if the limit lim = 0 for every n ∈ Z.) For a sequence of real numbers α n we will write U C-lim

n α n = α if lim N →∞ 1 |Φ N | n∈Φ N α n = α for any Følner sequence {Φ N } in Z.
Let E ⊆ Z have positive uniform density. Let P = {p 1 , . . . , p r } be a system of integral polynomials. We will say that E is UC-positive with respect to P ("UC" for

"Uniform Cesáro") if U D a ∈ Z : a, a + p 1 (n), . . . , a + p r (n) ∈ E exists for all n ∈ Z and U C-lim n U D a ∈ Z : a, a + p 1 (n), . . . , a + p r (n) ∈ E > 0,
that is, the U C-limit exists and is positive. (In particular, this implies that there exists δ > 0 such that the set of n for which

U D a ∈ Z : a, a + p 1 (n), . . . , a + p r (n) ∈ E > δ is syndetic in Z.)
We will say that E is UC-balanced with respect to P if

U C-lim n U D a ∈ Z : a, a + p 1 (n), . . . , a + p r (n) ∈ E = U D(E) r+1 .
(In particular, this implies that for any ε > 0 the set of n for which

U D a ∈ Z : a, a + p 1 (n), . . . , a + p r (n) ∈ E > U D(E) r+1 -ε is syndetic in Z.)
Finally, we will say that E is balanced with respect to P if

lim n→∞ U D a ∈ Z : a, a + p 1 (n), . . . , a + p r (n) ∈ E = U D(E) r+1
(this implies that for any ε > 0 one has

U D a ∈ Z : a, a + p 1 (n), . . . , a + p r (n) ∈ E > U D(E) r+1 -ε
for all but finitely many n ∈ Z).

Our main combinatorial result is that using Weyl systems one can construct a set E of integers with strong combinatorial properties: Theorem 0.5. (See Theorem 7.1 below.) Let {p 1 , . . . , p r } be a system of integral polynomials with zero constant term and let k = V (p 1 , . . . , p r ). There exists a set E ⊂ Z of positive uniform density such that (i) for any system {q 1 , . . . , q s } of integral polynomials with zero constant term and with V (q 1 , . . . , q s ) < k and any nonconstant integral polynomial h, E is UC-positive with respect to the system q 1 (h(n)), . . . , q s (h(n)) ; (ii) for any system {q 1 , . . . , q s } of integral polynomials with zero constant term and with W (q 1 , . . . , q s ) < k, any nonconstant integral polynomial h and any integers c 1 , . . . , c s , E is UC-balanced with respect to the system q 1 (h(n)) + c 1 , . . . , q s (h(n)) + c s ; (iii) for any system {q 1 , . . . , q s } of integral polynomials with zero constant term and with W (q 1 , . . . , q s ) < k -1, any nonconstant integral polynomial h and any integers c 1 , . . . , c s , E is balanced with respect to the system q 1 (h(n)) + c 1 , . . . , q s (h(n)) + c s ; (iv) there exist nonzero integers m and l such that E contains no configuration of the form a, a + p 1 (mn + l), . . . , a + p r (mn + l) , a, n ∈ Z.

Remark. The reader may notice that the assertion (i) of Theorem 0.5 is "weaker" than the assertions (ii) and (iii), since the "shifting" constants c i are absent in it. It is not clear whether a "shifted" version of (i) is true; the methods employed in this paper do not allow one to get such a result. (See the remark after Proposition 6.9 below.)

The integers m and l appearing in the formulation of Theorem 0.5 are not arbitrary (for instance, l cannot be divisible by m because in this case the polynomial Szemerédi theorem guarantees the existence of corresponding configurations). In general, these m and l depend on the system P = {p 1 , . . . , p r } (see Theorem 7.2). However, when the system P consists of linear polynomials p i (n) = b i n, i = 1, . . . , r, the foregoing nondivisibility restriction is the only restriction that cannot be avoided. This fact is reflected in the following theorem which, while similar in spirit to Theorem 0.5, has a different arrangement of quantifiers.

Theorem 0.6. (See Corollary 7.4 below.) For any r, m ≥ 2 there exists a set E ⊂ Z of positive uniform density such that (i) for any system {q 1 , . . . , q s } of integral polynomials with zero constant term and with V (q 1 , . . . , q s ) < r and any nonconstant integral polynomial h, E is UC-positive with respect to the system q 1 (h(n)), . . . , q s (h(n)) ; (ii) for any system {q 1 , . . . , q s } of integral polynomials with zero constant term and with W (q 1 , . . . , q s ) < r, any nonconstant integral polynomial h and any integers c 1 , . . . , c s , E is UC-balanced with respect to the system q 1 (h(n)) + c 1 , . . . , q s (h(n)) + c s ; (iii) for any system {q 1 , . . . , q s } of integral polynomials with zero constant term and with W (q 1 , . . . , q s ) < r -1, any nonconstant integral polynomial h and any integers c 1 , . . . , c s , E is balanced with respect to the system q 1 (h(n)) + c 1 , . . . , q s (h(n)) + c s ; (iv) E contains no arithmetic progressions of the form a, a + (mn + l), . . . , a + r(mn + l) , a, n, l ∈ Z, with l not divisible by m.

Remark. It is natural to inquire whether our examples can be constructed by utilizing Kronecker systems (rotations on compact commutative groups) which form a rather particular subclass of Weyl systems. It turns out that some special cases of the situation described in items (i) of Theorems 0.5 and 0.6 can indeed be obtained (albeit in a very cumbersome way) with the help of Kronecker systems. On the other hand the closer scrutiny reveals that Kronecker systems can not provide the more complicated examples which appear in the formulations of these theorems.

The paper is organized as follows. In Section 1 we give a detailed description of the dynamical method that will be used throughout this paper. In Section 2 we introduce some linear algebra notation related to a system of polynomials. In Section 3 we define Weyl dynamical systems and discuss their elementary properties. In Section 4 we introduce the Weyl and the Vandermonde complexities of a system of integral polynomials; in Section 5 we describe their properties and give examples. In Section 6 we obtain measure-theoretical results similar to Theorems 0.2, 0.3, and 0.4. In Section 7 we prove (somewhat more precise versions of) Theorems 0.5 and 0.6. Acknowledgement. We thank H. Furstenberg for constructive criticism and numerous useful suggestions.

Orbit of the diagonal

As we have already mentioned in the Introduction, the ergodic approach to combinatorics, which goes back to Furstenberg's seminal paper [F1], establishes a two-way connection between the family of sets of integers satisfying d * (S) > 0 and the family of visiting time sets E(A, x) in ergodic measure preserving systems. In one direction, this connection is manifested by Furstenberg's correspondence principle which is behind the derivation of Szemeredi's theorem from a corresponding multiple recurrence result. In the other direction, this connection provides a natural method of creating sets of integers with preassigned combinatorial properties. We will now describe this method in some detail.

Let (X, B, µ, T ) be an ergodic Borel measure preserving system on a compact space X, let A be a measurable set in X with µ(A) > 0, let x 0 ∈ X, and let P = {p 1 , . . . , p r } be a system of integer polynomials (or, at this stage, a system of integer valued sequences).

Define E = n ∈ N : T n x 0 ∈ A . Then for a, n ∈ N we have a ∈ E ∩ E -p 1 (n) ∩ . . . ∩ E -p r (n) iff a, a + p 1 (n), . . . , a + p r (n) ∈ E iff T a x 0 , T a+p 1 (n) x 0 , . . . , T a+p r (n) x 0 ∈ A iff T a x 0 ∈ A ∩ T -p 1 (n) A ∩ . . . ∩ T -p r (n) A. Thus, for any n ∈ N, the set E n = a : a, a + p 1 (n), . . . , a + p r (n) ∈ E is the same as a : T a x 0 ∈ A ∩ T -p 1 (n) A ∩ . . . ∩ T -p r (n) A . Let ∆ X r+1 = x x . . . x , x ∈ X be the diagonal in X r+1 . Consider the "polynomial action" g(n) x 0 x 1 . . . x r = x 0 T p 1 (n) x 1 . . . T p r (n) x r
, n ∈ N, on X r+1 corresponding to the system P = {0, p 1 , . . . , p r } and let O( P , ∆ X r+1 ) = n∈N g(n)∆ X r+1 be the "orbit" of ∆ X r+1 under this action. Then, for n ∈ N,

T a x 0 , T a+p 1 (n) x 0 , . . . , T a+p r (n) x 0 ∈ A iff x, T p 1 (n) x, . . . , T p r (n) x ∈ A for x = T a x 0 iff g(n) x x . . . x ∈ A r+1 only if g(n)∆ X r+1 ∩ A r+1 = ∅ only if O( P , ∆ X r+1 ) ∩ A r+1 = ∅. So, a configuration of the form a, a + p 1 (n), . . . , a + p r (n) is contained in E only if O( P , ∆ X r+1 ) ∩ A r+1 = ∅.
On the other hand, let µ ∆ X r+1 be the measure on ∆ X r+1 induced by the measure

µ on X, that is, µ ∆ X r+1 (A 0 × A 1 × . . . × A r ) = µ(A 0 ∩ A 1 ∩ . . . ∩ A r ), A i ⊆ X. Sup- pose that μP (A 0 × . . . × A r ) = lim N -M →∞ 1 N -M N n=M +1 g(n)µ ∆ X r+1 (A 0 × . . . × A r )
exists for any measurable A 0 , . . . , A r ⊆ X (it does if P is a system of polynomials -see [START_REF] Host | Convergence of polynomial ergodic averages[END_REF] and [L1]); then μP is a probability measure on X r+1 supported by the topological closure O( P , ∆ X r+1 ) of O( P , ∆ X r+1 ). Now assume that the set A r+1 "has substantial intersection with O( P , ∆ X r+1 )", namely, suppose that μP (B). (This is always possible when T is ergodic by the ergodic theorem.) Then for every

(A r+1 ) = δ > 0. This means that lim N -M →∞ 1 N -M N n=M +1 µ ∆ X r+1 g(n) -1 A r+1 = δ, or equivalently, lim N -M →∞ 1 N -M N n=M +1 µ A ∩ T -p 1 (n) A ∩ . . . ∩ T -p r (n) A = δ. For S ⊆ Z let d(S) denote, if it exists, the density of S, d(S) = lim N →∞ 1 N S ∩{1, . . . , N } . Choose our point x 0 so that for any set B of the form B = T c 1 A∩. . .∩T c l A, c 1 , . . . , c l ∈ Z, one has d a : T a x 0 ∈ B = µ
n ∈ N, d(E n ) = µ A ∩ T -p 1 (n) A ∩ . . . ∩ T -p r (n) A and hence lim N →∞ 1 N N n=1 d(E n ) = δ. So, not only E contains configurations of the form a, a + p 1 (n), . . . , a + p r (n) ,
but contains many such configurations, and they occur in E quite regularly.

This suggests how one can attempt to construct a set E ⊂ Z which contains no configurations a, a + p 1 (n), . . . , a + p r (n) and many configurations a, a + q 1 (n), . . . , a + q s (n) for another system Q = {q 1 , . . . , q s } of integral polynomials: it suffices to find a dynamical system (X, T ) and a set A ⊂ X such that μQ (A s+1 ) > 0 whereas μP (A r+1 ) > 0. Then one chooses a "typical" point x 0 of A and defines E to be the set of return times of x 0 to A, E = E(A, x 0 ).

Span and Rank of a system of polynomials

Let us first introduce some linear algebra notation. Given a system of vectors

a 1,1 . . . a r,1 , . . . , a 1,k . . . a r,k ∈ R r , we define span a 1,1 a 1,2 ... a 1,k . . . . . . . . . a r,1 a r,2 ... a r,k
to be the subspace of R r spanned by these vectors, and, as usual, rank

a 1,1 a 1,2 ... a 1,k . . . . . . . . . a r,1 a r,2 ... a r,k = dim span a 1,1 a 1,2 ... a 1,k . . . . . . . . . a r,1 a r,2 ... a r,k
.

Given r real-valued polynomials q 1 , . . . , q r with zero constant term, we will denote by Span q 1

. . . q r the subspace of R r spanned by the range of q 1

. . .

q r : Span q 1 . . . q r = span q 1 (x)
. . .

q r (x) , x ∈ R .
For polynomials q i,j , i = 1, . . . , r, j = 1, . . . , k, with zero constant term, we define Span

q 1,1 q 1,2 ... q 1,k . . . . . . . . . q r,1 q r,2 ... q r,k = Span q 1,1 . . . q r,1 + Span q 1,2 . . . q r,2 + . . . + Span q 1,k . . . q r,k and Rank q 1,1 q 1,2 ... q 1,k . . . . . . . . . q r,1 q r,2 ... q r,k = dim Span q 1,1 q 1,2 ... q 1,k . . . . . . . . . q r,1 q r,2 ... q r,k
.

Clearly, we have

Lemma 2.1. The Span and Rank of a polynomial matrix

q 1,1 q 1,2 ... q 1,k . . . . . . . . . q r,1 q r,2 ... q r,k
are invariant under column operations (that is, multiplying a column by a nonzero constant or a nonzero polynomial, and adding one column to another) on the matrix.

The following lemmas will be utilized below for finding the Span of a polynomial matrix:

Lemma 2.2. Let q i,j be polynomials with zero constant term and deg q i,j ≤ d for all i, j. Then

(i) Span q 1,1 q 1,2 ... q 1,k . . . . . . . . . q r,1 q r,2 ... q r,k
is spanned by the values of

q 1,1 (x) q 1,2 (x) ... q 1,k (x) . . . . . . . . . q r,1 (x) q r,2 (x) ... q r,k (x) at any distinct nonzero x 1 , . . . , x d ∈ R: Span q 1,1 q 1,2 ... q 1,k . . . . . . . . . q r,1 q r,2 ... q r,k = span q 1,1 (x 1 ) ... q 1,k (x 1 ) q 1,1 (x 2 ) ... q 1,k (x 2 ) ... q 1,1 (x d ) ... q 1,k (x d ) . . . . . . . . . . . . . . . .
. . q r,1 (x 1 ) ... q r,k (x 1 ) q r,1 (x 2 ) ... q r,k (x 2 ) ... q r,1 (x d ) ... q r,k (x d ) .

(ii) Span

q 1,1 q 1,2 ... q 1,k . . . . . . . . . q r,1 q r,2 ... q r,k
is spanned by the coefficients of q 1,1 q 1,2 ... q 1,k . . . . . . . . . q r,1 q r,2 ... q r,k k,d .

: if q i,j (x) = c i,j,1 x + . . . + c i,j,d x d , c i,j,l ∈ R, then Span q 1,1 q 1,2 ... q 1,k . . . . . . . . . q r,1 q r,2 ... q r,k = span c 1,1,1 ... c 1,1,d c 1,2,1 ... c 1,2,d ... c 1,k,1 ... c 1,k,d . . . . . . . . . . . . . . . . . . c r,1,1 ... c r,1,d c r,2,1 ... c r,2,d ... c r,k,1 ... c r,
(iii) More generally, let h 1 , . . . , h l be linearly independent polynomials without constant term such that q i,j are their linear combinations:

q i,j = b i,j,1 h 1 + . . . + b i,j,l h l , b i,j,t ∈ R. Then Span q 1,1 q 1,2 ... q 1,k . . . . . . . . . q r,1 q r,2 ... q r,k = span b 1,1,1 ... b 1,1,l b 1,2,1 ... b 1,2,l ... b 1,k,1 ... b 1,k,l . . . . . . . . . . . . . . . . . . b r,1,1 ... b r,1,l b r,2,1 ... b r,2,l ... b r,k,1 ... b r,k,l .
Proof. (i) follows from Lagrange's interpolation formula for polynomials of degree ≤ d.

(ii) is a special case of (iii).

Here is the proof of (iii):

for j = 1, . . . , k define B j = b 1,j,1 ... b 1,j,l . . . . . . b r,j,1 ... b r,j,l . Then Span q 1,j . . . q r,j = span q 1,j (x)
. . .

q r,j (x) , x ∈ R = span B j h 1 (x)
. . .

h l (x) , x ∈ R = B j span h 1 (x)
. . .

h l (x) , x ∈ R = B j R l = span B j . So, Span q 1,1 q 1,2 ... q 1,k . . . . . . . . . q r,1 q r,2 ... q r,k = k j=1 Span q 1,1 . . . q r,1 = k j=1 span B j .
As a corollary, we get:

Lemma 2.3. Let q i,j be polynomials with zero constant term, let h be a nonconstant polynomial, and let qi,j (x) = q i,j (h(x)) -q i,j (h(0)). Then Span

q1,1 ... q1,k . . . . . . qr,1 ... qr,k = Span q 1,1 ... q 1,k . . . . . . q r,1 ... q r,k
.

Proof. It is enough to check this for k = 1, that is, to show that, for integral polynomials

q i with zero constant term, Span q1 . . . qr = Span q 1 . . . q r . It follows from Lemma 2.2(i) that Span q1 . . . qr = span q 1 (x+h(0))-q 1 (h(0)) . . . q r (x+h(0))-q r (h(0))
, x ∈ R , and we have span

q 1 (x+h(0))-q 1 (h(0)) . . . q r (x+h(0))-q r (h(0)) , x ∈ R = span q 1 (x)-q 1 (h(0)) . . . q r (x)-q r (h(0)) , x ∈ R = span q 1 (x)-q 1 (0)
. . .

q r (x)-q r (0) , x ∈ R = span q 1 (x)
. . .

q r (x) , x ∈ R = Span q 1 . . . q r .
(We used the fact that for any system V of vectors and any v ∈ V , span(Vv) = span(Vv ) for any other v ∈ V .)

Weyl dynamical systems

A Weyl system is a dynamical system (X, T ) where X is a compact commutative Lie group and T is an affine unipotent transformation of X (that is, T x = ϕ(x) + α where α ∈ X and ϕ is an automorphism of X satisfying (ϕ -Id X ) d = 0 for some d). A natural example of a Weyl system is given by the system (X, T ) where X = T l × Z, T = R/Z and Z is a finite Abelian group, and

T (x 1 , . . . , x l , z) = x 1 + α 1 , x 2 + m 2,1 x 1 + α 2 , . . . , x l + l-1 i=1 m l,i x i + α l , z + w , α i ∈ T, m j,i ∈ Z and w ∈ Z.
When X is connected (and so, is a torus) we will say that (X, T ) is a connected Weyl system.

Any closed subgroup M of X is, topologically, either a torus or a union of finitely many tori, and is a single torus if connected. We will call a subtorus of X any translate x + M of a closed connected subgroup M of X.

Clearly, the product of several Weyl systems is a Weyl system. A Weyl system possesses a sequence of natural factors: , d -1, commute with the action of T . The natural factors X k , k = 1, . . . , d, are the HKZ factors for the system (X, T ). Indeed, a Weyl system (X, T ) can be viewed as a nilsystem: if we define a group G as the extension of the torus X by the group of automorphisms of X generated by ϕ, then G is a nilpotent (nonconnected) Lie group, and X is a homogeneous space of G with T = ϕ + α being a translation on X. Under this interpretation, the sequence [Z], Lemma 6.58 that the k-th natural factor X k = X/L k+1 is the characteristic factor of X for all systems of k linear integral polynomials, that is, the (k + 1)-st HKZ factor. (See [L2].)

for k = 1, . . . , d let L k = ker(ϕ -Id X ) d-k+1 and X k-1 = X/L k ; then the projection maps π k : X -→ X k , k = 0, . . .
G = L 1 , ϕ ⊇ L 2 ⊇ . . . ⊇ L d is the lower central series of G. It is proved in
A Weyl system (X, T ) has good ergodic properties: if T is ergodic, then the orbit of every point is uniformly distributed in X; if T is not ergodic, then the closure of the orbit of any point is a coset of a closed subgroup of X, and the orbit is uniformly distributed in this coset. Moreover, "polynomial orbits" of points, and even of subtori of X, also possess an analogous property.

Let us be more precise. Recall that for a set

E ⊆ Z we write U D(E) = α if the limit lim N →∞ |E∩Φ N | |Φ N |
exists and equals α for every Følner sequence {Φ N } in Z, and for a sequence {β n } n∈Z of real numbers we write U C-lim

n β n = β if the limit lim N →∞ 1 |Φ N |
n∈Φ N β n exists and equals β for every Følner sequence {Φ N } in Z. For a torus (or, more generally, a compact commutative Lie group) M we will denote by µ M the normalized Haar measure on M ; if M is a closed subgroup of X and x ∈ X, we will denote by µ x+M the image of µ M by the translation by x. We will say that a sequence {x n } n∈Z (in a, potentially, "larger" space Let P = {p 1 , . . . , p r } be a system of integral polynomials with zero constant term. For a point y ∈ X r we will denote by O(P, y) the orbit of y under the action of P , that is, O(P, y) = . . .

X ⊇ M ) is well distributed in M if x n ∈ M for all n,
T p 1 (n) . . . T p r (n)
T p r (n) D. O(P, D) will stand
for the topological closure of O(P, D). We will also denote by P the "extended system" {0, p 1 , . . . , p r } and by O( P , y) and O( P , D) the orbits

Id X T p 1 (n) . . . T p r (n) y n∈Z and, respectively, n∈Z Id X T p 1 (n) . . . T p r (n) D.
For a vector u ∈ R l we will denote by u mod 1 the image of u in T l = R l /Z l . If N is a rational subspace of R l (that is, a subspace defined by linear equations with rational coefficients), then N mod 1 is a subtorus of T l .

The following fundamental fact is a direct consequence of the classical Weyl's work on uniform distribution ( [We]) (modulo the easy modification that upgrades Weyl's results from uniform to well distribution).

Theorem 3.1. Let q 1 , . . . , q l be real-valued polynomials with zero constant term. The closure of the sequence

q 1 (n) . . . q l (n) mod 1
n∈Z is a disjoint union of finitely many subtori of T l . If this sequence is dense in a single subtorus (which may coincide with T l ), then it is well distributed in this subtorus.

Let (X, T ) be a connected Weyl system and let P = {p 1 , . . . , p r } be a system of integral polynomials. It is easy to see that the orbit O(P, y) of a point y ∈ X r under the action of P is described by a polynomial formula, that is, in coordinates on the torus

X r , T p 1 (n)
. . .

T p r (n) y = (q 1 (n), . . . , q l (n)), n ∈ Z,
where q i are polynomials and l = r dim X.

Hence, it follows from Theorem 3.1 that M = O(P, y) is a subtorus of X r or a disjoint union of finitely many subtori of X r , and when M is a single subtorus, the sequence

T p 1 (n)
. . .

T p r (n) y n∈Z is well distributed in M .
Assume now that (X, T ) is a disconnected Weyl system having c components. Replacing T by T c we arrive at a system which is a union of finitely many connected Weyl systems and our argument, applied to each of these systems, shows that M = O(P, y) is still a finite union of subtori of X r .

We will need the following more general fact:

Proposition 3.2. Let (X, T ) be a Weyl system and let P = {p 1 , . . . , p r } be a system of integral polynomials. For any subtorus D of X r the closure M = O(P, D) of the orbit of D under the action of P is a subtorus of X r or a union of finitely many subtori of X r . If

M is a single subtorus, the sequence

D n = T p 1 (n)
. . .

T p r (n) D n∈Z is well distributed in M .
Proposition 3.2 can be deduced from the multiparameter version of Theorem 3.1 (which is also essentially contained in [We]). Indeed, choose an element y ∈ D such that the sequence {my} m∈Z is dense (and so, well distributed) in D. Then M is equal to the closure of the two-parameter sequence y m,n =

T p 1 (n) . . . T p r (n)
my, n, m ∈ Z, which, by the twoparameter version of Theorem 3.1, is a finite union of subtori of X r . If M is a single torus, {y m,n } n,m∈Z is well distributed in M , that is, for any continuous function f on M and any Følner sequence

{Ψ N } in Z 2 one has lim N →∞ 1 |Ψ N | (m,n)∈Ψ N f (y m,n ) = M f dµ M .
On the other hand, for each fixed n the sequence {y m,n } m∈Z is well distributed in D n . Consider a Følner sequence {Φ N } in Z and a sequence {K N } of integers that increases fast enough. We then have lim

N →∞ 1 |Φ N |K N n∈Φ N 1≤m≤K N f (y m,n ) = lim N →∞ 1 |Φ N | n∈Φ N lim K→∞ 1 K K m=1 f (y m,n ) = lim N →∞ 1 |Φ N | n∈Φ N D n f dµ D n .
Since Φ N × {1, . . . , K N } is a Følner sequence in Z 2 , we obtain lim

N →∞ 1 |Φ N | n∈Φ N D n f dµ D n = M f dµ M .
Here is another corollary of Theorem 3.1:

Corollary 3.3. Let α 1 , . . . , α k be rationally independent elements of T and let q i,j , i = 1, . . . , k, j = 1, . . . , l, be integral polynomials with zero constant term. The sequence

q 1,1 (n)α 1 +...+q k,1 (n)α k . . . q 1,l (n)α 1 +...+q k,l (n)α k n∈Z is well distributed in the subtorus Span q 1,1 ... q k,1 . . . . . . q 1,l ... q k,l mod 1 of T l . Proof. Let L = Span q 1,1 ... q k,1 . . . . . . q 1,l ... q k,l
and let M = L mod 1. (Note that since L is a "rational" subspace of R l (that is, is spanned by vectors with rational coordinates), M is a subtorus.)

For any i and any n ∈ Z,

q i,1 (n)
. . .

q i,l (n) ∈ L, so q 1,1 (n)α 1 +...+q k,1 (n)α k . . . q 1,l (n)α 1 +...+q k,l (n)α k ∈ M for all n.
Assume that χ is a character on T l (with values in the additive torus T), χ(x 1 , . . . , x l ) = l j=1 a j x j with a 1 , . . . , a l ∈ Z, such that χ

q 1,1 (n)α 1 +...+q k,1 (n)α k . . . q 1,l (n)α 1 +...+q k,l (n)α k = 0 for all n. Then, in T, we have l j=1 a j q 1,j (n) α 1 + . . . + l j=1 a j q k,j (n) α k = 0
for all n, and since α 1 , . . . , α k are rationally independent in T, we deduce that l j=1 a j q i,j (n) = 0 for all n and for all i = 1, . . . , k. This implies that l j=1 a j q i,j = 0 for all i = 1, . . . , k, and thus χ | M = 0.

We have established that the sequence

q 1,1 (n)α 1 +...+q k,1 (n)α k . . . q 1,l (n)α 1 +...+q k,l (n)α k n∈Z
is not contained in a proper subgroup of M ; by Theorem 3.1, it is well distributed in M .

To achieve the goals formulated in the introduction, it will be sufficient to deal with Weyl systems of a special form. A standard Weyl system (of depth d) is the system (X, T ) with X = T d and

T (x 1 , x 2 , . . . , x d ) = x 1 + α, x 2 + x 1 , x 3 + x 2 , . . . , x d + x d-1 , x = (x 1 , . . . , x d ) ∈ X,
where α ∈ T is irrational. By [F2] Proposition 3.11, (X, T ) is ergodic. A quasi-standard Weyl system of depth d is a system (X, T ) where X = T d and

T (x 1 , . . . , x d ) = x 1 + α 1 , x 2 + m 2,1 x 1 + α 2 , . . . , x d + d-1 i=1 m d,i x i + α d ,
with α i ∈ T, m j,i ∈ Z, α 1 is irrational and m j,j-1 = 0 for all j = 2, . . . , d. A quasi-standard Weyl system is also ergodic. For a standard or a quasi-standard Weyl system the natural factors X k have form X k = X/L k+1 where L k+1 = (0, . . . , 0, x k+1 , . . . , x d ), x i ∈ T . Lemma 3.4. Any quasi-standard Weyl system is a factor, η: X -→ X, of a standard Weyl system ( X, T ) of the same depth; η has finite fibers and commutes with the projections π k , k = 0, . . . , d -1, onto the natural factors.

Rather than formally proving this lemma we illustrate it on a simple example, which indicates how the general result can be proved. Consider the quasi-standard Weyl system (T 3 , T ) where T (x, y, z) = (x + α 1 , y + 2x + α 2 , z + 4x + 3y + α 3 ).

This system is the factor of the standard Weyl system (T 3 , T )

T (x, y, z) = (x + α 1 , y + x, z + y) via the factor-map (x, y, z) → (x + a, 2y + x + b, 6z + 7y + x) with a, b ∈ T satisfying 2a = α 1 -α 2 and 3b = -α 1 + 2α 2 -α 3 .
We would like to remark that while we find it convenient to work with quasi-standard Weyl systems, all the combinatorial results in this paper could be obtained by employing the standard Weyl systems only. We would also like to mention the following fact, which demonstrates a universal property of standard Weyl systems: Theorem 3.5. ( [FrK]) Any ergodic connected Weyl system is a factor of a product of several standard Weyl systems.

Disconnected Weyl systems do not provide much novelty: any disconnected ergodic Weyl system (Y, R) is a union Y = X (1) ∪ . . . ∪ X (m) of m ≥ 2 isomorphic tori; R cyclically permutes these tori and, for each i = 1, . . . , m, (X (i) , R m | X (i) ) is a connected Weyl system.

Weyl and Vandermonde complexities

We fix a standard Weyl system (X, T ), where X = T d and

T (x 1 , x 2 , . . . , x d ) = x 1 + α, x 2 + x 1 , x 3 + x 2 , . . . , x d + x d-1 , x = (x 1 , . . . , x d ) ∈ X,
with an irrational α ∈ T; we will always assume that d is large enough so that its value will not affect our further computations. (Namely, d will have to be larger than the complexity of the polynomial systems under consideration.) For k = 0, . . . , d we define subtori

L k = (0, . . . , 0, x k , . . . , x d ), x i ∈ T ⊂ T d , F k = (0, . . . , 0, x k , 0, . . . , 0), x k ∈ T} ⊂ T d ,
a factor torus X k = X/L k+1 , and let π k : X -→ X k be the projection map. We will also denote by F k the image of F k under π k , so that if we identify X k with T k , we identify F k with the subgroup F k = (0, . . . , 0, x k ), x k ∈ T} of T k .

Let now P = {p 1 , . . . , p r } be a system of integral polynomials with zero constant term. (We will always assume that the polynomials p 1 , . . . , p r are all distinct.) One checks by induction that for any n ∈ Z,

T n (x 1 , x 2 , . . . , x d ) = x 1 + nα, x 2 + nx 1 + n 2 α, . . . , x d + d-1 i=1 n i x d-i + n d α .
For a polynomial p and k ∈ N we will write p [k] for p k = 1 k! p(p -1) . . . (pk + 1), and

p [0] = 1. Let g(n) = Id X T p 1 (n) . . . T p r (n) , n ∈ Z. For x = (x 1 , x 2 , . . . , x d ) ∈ X, the orbit O( P , x) = {g(n)x} n∈Z ⊆ X r+1 of the point x = x x . . . x under the action of P = {0, p 1 , . . . , p r } is            x 1 , x 2 , . . . , x d x 1 + p 1 (n)α, x 2 + p 1 (n)x 1 + p 1 (n) [2] α, . . . , x d + d-1 i=1 p 1 (n) [i] x d-i + p 1 (n) [d] α . . . . . . . . . x 1 + p r (n)α, x 2 + p r (n)x 1 + p r (n) [2] α, . . . , x d + d-1 i=1 p r (n) [i] x d-i + p r (n) [d] α            n∈Z (4.1
) By Corollary 3.3, when x 1 , . . . , x d and α are rationally independent in T, O( P , x) is well distributed (and hence, dense) in the subtorus

                       x 1 x 1 . . . x 1 x 2 x 2 . . . x 2 . . . . . . x d-1 x d-1 . . . x d-1 x d x d . . . x d                        + Span                        0 0 0 ... 0
... 0 0 p [d-1] 1 p [d-2] 1 p [d-3] 1 ... p 1 0 . . . . . . . . . . . . . . . p [d-1] r p [d-2] r p [d-3] r ... p r 0 0 0 0 ... 0 0 p [d] 1 p [d-1] 1 p [d-2] 1 ... p [2] 1 p 1 . . . . . . . . . . . . . . . p [d] r p [d-1] r p [d-2] r ... p [2] r p r                        mod 1
of X r+1 T (r+1) d (and is contained in this subtorus if x 1 , . . . , x d , α are rationally dependent). The closure of the orbit O( P , ∆ X r+1 ) of the entire diagonal ∆ X r+1 = {x, x ∈ X} of X r+1 is therefore the subtorus

H = O( P , ∆ X r+1 ) = Span Θ d mod 1 ⊆ X r+1
where for each k ∈ N we define Θ k as the (r + 1)k × 2k matrix

Θ k =                        1 0 ... 0 0 0 0 0 ... 0
0 0 ... 1 0 p [k-1] r p [k-2] r p [k-3] r ... p r 0 0 0 ... 0 1 0 0 0 ... 0 0 0 0 ... 0 1 p [k] 1 p [k-1] 1 p [k-2] 1 ... p [2] 1 p 1 . . . . . . . . . . . . . . . . . . . . . . . . 0 0 ... 0 1 p [k] r p [k-1] r p [k-2] r ... p [2] r p r                        . For k ≤ d, let H k = π r+1 k (H) ⊆ X r+1 k ; identifying X k with T k and X r+1 k with T (r+1) k , we get H k = Span Θ k mod 1 ⊆ X r+1 k . (4.2)
If we supress the 1-st and the (k + 1)-st columns from the matrix Θ k+1 , we obtain the matrix 0 Θ k . Hence we have We note that the first component X of X r+1 actually plays no role in determining

H k+1 ⊇ Span 0 Θ k mod 1. ( 4
W (P ). For k ≤ d let Λ k =                    p 1 0 0 ... 0
p [k-1] 1 p [k-2] 1 p [k-3] 1 ... p 1 0 . . . . . . . . . . . . . . . p [k-1] r p [k-2] r p [k-3] r ... p r 0 p [k] 1 p [k-1] 1 p [k-2] 1 ... p [2] 1 p 1 . . . . . . . . . . . . p [k] r p [k-1] r p [k-2] r ... p [2] r p r                   
.

The subtorus M = Span Λ d mod 1 ⊆ X r is the (translated to 0) orbit of a "generic" point x of the diagonal ∆ X r under the action of P : M = O(P, x) -x where x = x . . .

x and x is a point of X whose coordinates and α are rationally independent. For k ≤ d let

M k = π r k (M ) = Span Λ k mod 1 ⊆ X r k . Then H k = ∆ X r+1 k ⊕ ({0} × M k ) ⊆ X k × X r k . It follows that F r+1 k ⊆ H k iff F r k ⊆ M k . Put w 0 (P ) = 0 and for each k ∈ N let w k (P ) = dim M k = Rank Λ k . Since w k (P ) = w k-1 (P ) + dim(M k ∩ F r k ), we have F r k ⊆ M k iff w k (P ) -w k-1 (P ) = r.
We obtain:

Proposition 4.1. The Weyl complexity W (P ) equals the minimal k for which M k ⊇ F r k , and the minimal k for which w k (P ) -w k-1 (P ) = r.

We will now formally introduce the Vandermonde complexity for our system P. Let τ k be the projection of X to F k ; we define the Vandermonde complexity of P , V (P ) or V (p 1 , . . . , p r ), as the minimal k for which

τ r+1 k (H) = F r+1 k . Identifying the subtorus F r+1 k of X r+1 with T r+1 we have τ r+1 k (H k ) = Span   1 0 0 0 ... 0 0 1 p [k] 1 p [k-1] 1 p [k-2] 1 ... p [2] 1 p 1 . . . . . . . . . . . . . . . . . . 1 p [k] r p [k-1] r p [k-2] r ... p [2] r p r   mod 1 = Span   1 0 0 ... 0 0 0 1 p 1 p 2 1 ... p k-2 1 p k-1 1 p k 1 . . . . . . . . . . . . . . . . . . 1 p r p 2 r ... p k-2 r p k-1 r p k r   mod 1. Define v k (P ) = Rank p 1 p 2 1 ... p k-2 1 p k-1 1 p k 1 . . . . . . . . . . . . . . . p r p 2 r ... p k-2 r p k-1 r p k r , k ∈ N; then τ r+1 k (H k ) = F r+1 k iff τ r k (M k ) = F r k iff v k (P ) = r.
We see that Proposition 4.2. V (P ) equals the minimal k for which τ r k (M k ) = F r k , and the minimal k for which v k (P ) = r.

Properties of Vandermonde and Weyl complexities and examples

We start with the Vandermonde complexity.

Lemma 5.1. For any system P = {p 1 , . . . , p r } of r integral polynomials with zero constant term, V (P ) ≤ r.

Proof. We have det

p 1 p 2 1 ... p r 1 . . . . . . . . . p r p 2 r ... p r r = r i=1 p i • r j=i+1 (p j -p i ) = 0.
(This is the Vandermonde determinant, which explains our terminology.) Thus, the vectors

p 1 (x) . . . p r (x)
, . . . ,

p r 1 (x)
. . .

p r r (x)
are linearly independent for all but finitely many x, and so, v r (P ) = r.

Hence, V (P ) ≤ r.

Here are some properties of the Vandermonde complexity, which are clear from the definition and Proposition 4.2: Proposition 5.2. Let {p 1 , . . . , p r } be a system of integral polynomials with zero constant term. (i) If {q 1 , . . . , q s } ⊆ {p 1 , . . . , p r }, then V (q 1 , . . . , q s ) ≤ V (p 1 , . . . , p r ). (ii) V (p 1 , . . . , p r ) = 1 iff p 1 , . . . , p r are linearly independent. (iii) If p 1 , . . . , p r are all linear, V (p 1 , . . . , p r ) = r. (iv) V is invariant under polynomial substitutions: for any nonzero integral polynomial h with zero constant term, V p 1 (h(x)), . . . , p r (h(x)) = V p 1 (x), . . . , p r (x) . (v) For any nonzero integer m = 0, V (mp 1 , . . . , mp r ) = V (p 1 , . . . , p r ).

Examples of computation of Vandermonde complexity.

Consider the system P = {x, 2x, x 2 }. Using the "coefficient method" from Lemma 2.2(ii), we get

v 1 (P ) = Rank x 2x x 2 = rank 1 0 2 0 0 1 = 2 and v 2 (P ) = Rank x x 2 2x 4x 2 x 2 x 4 = rank 1 0 1 0 2 0 4 0 0 1 0 1 = 3, so V (P ) = 2.
For the system P = {x, x 2 , x + x 2 , x + 2x 2 } we have

v 1 (P ) = Rank x x 2 x+x 2 x+2x 2 = rank 1 0 0 1 1 1 1 2 = 2 and v 2 (P ) = Rank x x 2 x 2 x 4 x+x 2 x 2 +2x 3 +x 4 x+2x 2 x 2 +4x 3 +4x 4 = rank 1 0 1 0 0 0 1 0 0 1 1 1 1 2 1 1 2 1 4 4 = 4, so V (P ) = 2.
For the system P = {x,

x 2 , x + x 2 , x + 2x 2 , x + 3x 2 }, v 1 (P ) = Rank   x x 2 x+x 2 x+2x 2 x+3x 2   = rank 1 0 0 1 1 1 1 2 1 3 = 2, v 2 (P ) = Rank    x x 2 x 2 x 4 x+x 2 x 2 +2x 3 +x 4 x+2x 2 x 2 +4x 3 +4x 4 x+3x 2 x 2 +6x 3 +9x 4    = rank 1 0 1 0 0 0 1 0 0 1 1 1 1 2 1 1 2 1 4 4 1 3 1 6 9 = 4 and v 3 (P ) = Rank    x x 2 x 3 x 2 x 4 x 6 x+x 2 x 2 +2x 3 +x 4 x 3 +3x 4 +3x 5 +x 6 x+2x 2 x 2 +4x 3 +4x 4 x 3 +6x 4 +12x 5 +8x 6 x+3x 2 x 2 +6x 3 +9x 4 x 3 +9x 4 +27x 5 +27x 6    = rank
1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 2 1 1 3 3 1 1 2 1 4 4 1 6 12 8 1 3 1 6 9 1 9 27 27 = 5, so V (P ) = 3.

The Weyl complexity has properties similar to those of the Vandermonde complexity: Proposition 5.3. Let {p 1 , . . . , p r } be a system of integral polynomials with zero constant term. (i) If {q 1 , . . . , q s } ⊆ {p 1 , . . . , p r }, then W (q 1 , . . . , q s ) ≤ W (p 1 , . . . , p r ). (ii) W (p 1 , . . . , p r ) = 1 iff p 1 , . . . , p r are linearly independent. (iii) If all p 1 , . . . , p r are linear, W (p 1 , . . . , p r ) = r. (iv) For any nonzero integral polynomial h with zero constant term, W p 1 (h(x)), . . . , p r (h(x)) = W p 1 (x), . . . , p r (x) . (v) For any nonzero integer m, W (mp 1 , . . . , mp r ) = W (p 1 , . . . , p r ). (vi) W (p 1 , . . . , p r ) ≥ V (p 1 , . . . , p r ).

Proof. (i) is clear from the definition. (ii) and (vi) follow from Proposition 4.1. It follows from formula (4.2) and Lemma 2.2(i) that for the system P (h) = p 1 (h(x)), . . . , p r (h(x))

we have O( P (h), ∆ X r+1 ) = O( P , ∆ X r+1 ); this implies (iv). We postpone the proof of (iii) and of (v) till the end of this section.

Remark. The fact that W (P ) is finite for any system of integral polynomials P is a consequence of the general study of HKZ factors; we do not prove it here. W (P ) may be strictly larger than V (P ) as an example at the end of this section demonstrates. A question that we leave open is whether W (p 1 , . . . , p r ) is always ≤ r.

The definition of the Weyl complexity via the standard Weyl system is, actually, inconvenient for practical usage. We will modify it a little bit by replacing the standard Weyl system by a quasi-standard one. Let (X, T ) be a quasi-standard Weyl system, let L k = (0, . . . , 0, x k , . . . , x d ) , X k = X/L k+1 , F k = (0, . . . , 0, x k ) ⊆ X k , π k be the projection of X to X k and τ k be the projection of X to F k , k = 1, . . . , d; let ∆ X r+1 = x . . .

x , x ∈ X be the diagonal of X r+1 , and let x be a "generic" point of the diagonal of X r . Let P = {p 1 , . . . , p r } be a system of integral polynomials with zero constant term and with

W (P ) ≤ k, let H = O( P , ∆ X r+1 ) ⊆ X r+1 , M = O( P , x) -x ⊆ X r , H k = π r+1 k (H) ⊆ X r+1 k and M k = π r k (M ) ⊆ X r k , k = 1, . . . , d.
Let ( X, T ) be a standard Weyl system for which (X, T ) is a factor, η: X -→ X, as in Lemma 3.4, and let

H, M , L k , F k , H k and M k , k = 1, . . . , d, be the corresponding subtori of X r+1 , X r , X, X k , X r+1 k and X r k respectively. Then for all k, F k = η( F k ), H k = η( H k ) and M k = η(M k ). So, H ⊇ L r+1 k iff H ⊇ L r+1 k , M ⊇ L r k iff M ⊇ L r k , H k ⊇ F r+1 k iff H k ⊇ F r+1 k , and
M k ⊇ F r k iff M k ⊇ F r k . Since η has finite fibers, dim H k = dim H k and dim M k = dim M k .
We obtain that for computing the Weyl complexity of the system {p 1 , . . . , p r } any quasi-standard Weyl system can be used: Proposition 5.4. W (P ) equals the minimal k for which H ⊇ L r+1 k , the minimal k for which M ⊇ L r k , the minimal k for which

H k ⊇ F r+1 k
, and the minimal k for which

M k ⊇ F r k ; w k (P ) = dim M k for all k.
An analogous fact holds for the Vandermonde complexity:

Proposition 5.5. For any quasi-standard Weyl system, v k (P ) = dim τ r k (M ) for all k; V (P ) equals the minimal k for which τ r+1 k (H) = F r+1 k and the minimal k for which τ r k (M ) = F r k . Proof. For any quasi-standard Weyl system (X, T ),

τ r+1 k (H) = Span 1 0 0 ... 0 1 h k (p 1 ) h k-1 (p 1 ) ... h 1 (p 1 ) . . . . . . . . . . . . 1 h k (p r ) h k-1 (p r ) ... h 1 (p r ) mod 1,
where for each i = 1, . . . , k, h i is a polynomial of degree i with zero constant term. (Under h(p) we understand the polynomial h(p(x)).) Performing suitable column transformations of the last matrix and using Lemma 2.1, we come to Span

1 0 0 ... 0 1 h k (p 1 ) h k-1 (p 1 ) ... h 1 (p 1 ) . . . . . . . . . . . . 1 h k (p r ) h k-1 (p r ) ... h 1 (p r ) = Span   1 0 0 ... 0 1 p k 1 p k-1 1 ... p 1 . . . . . . . . . . . . 1 p k r p k-1 r ... p r   .
Similarly,

τ r k (M ) = Span h k (p 1 ) h k-1 (p 1 ) ... h 1 (p 1 ) . . . . . . . . . h k (p r ) h k-1 (p r ) ... h 1 (p r ) mod 1 = Span p k 1 p k-1 1 ... p 1 . . . . . . . . . p k r p k-1 r ... p r mod 1.
(To clarify what we mean under "suitable column transformations" let us consider an example. For the Weyl system (T 3 , T ) where

T (x 1 , x 2 , x 3 ) = x 1 + α, x 2 + 3x 1 , x 3 + x 2 + 2x 1 + α ,
one checks that

T n (x 1 , x 2 , x 3 ) = x 1 +nα, x 2 +3nx 1 + 3 2 n(n-1)α, x 3 +nx 2 + 1 2 (3n 2 +n)x 1 + 1 2 (n 3 -n 2 +2n)α , n ∈ Z,
and so,

τ r 3 (M ) = Span 1 2 (p 3 1 -p 2 1 +2p 1 ) 1 2 (3p 2 1 +p 1 ) p 1 . . . . . . . . . 1 2 (p 3 r -p 2 r +2p r ) 1 2 (3p 2 r +p r ) p r mod 1 = Span p 3 1 p 2 1 p 1 . . . . . . . . . p 3 r p 2 r p r mod 1.)
Now we may also get:

Proof of Proposition 5.3(v). Let (X, T ) be a standard Weyl system and m be a nonzero integer. Put R = T m ; (X, R) is then a quasi-standard Weyl system. Let P = {p 1 , . . . , p r } be a system of integral polynomials with zero constant term and let mP = {mp 1 , . . . , mp r }.

Using an index to specify what transformation we consider, we have O R ( P , ∆ X r+1 ) = O T (m P , ∆ X r+1 ). Since the first orbit is responsible for W (p 1 , . . . , p r ) and the second orbit is responsible for W (mp 1 , . . . , mp r ), these two numbers coincide.

Consider the quasi-standard Weyl system

T (x 1 , . . . , x d ) = x 1 + α, x 2 + 2x 1 + α, . . . , x d + d-1 i=1 d i x i + α . For n ∈ Z one has T n (x 1 , x 2 , . . . , x d ) = x 1 + nα, x 2 + 2nx 1 + n 2 α, . . . , x d + d-1 i=1 d i n i x d-i + n d α . For this system, M k = Span Λ k mod 1 (5.1)
where

Λ k =                    p 1 0 0 ... 0
p k-1 1 ( k-1 k-2 )p k-2 1 ( k-1 k-3 )p k-3 1 ... (k-1)p 1 0 . . . . . . . . . . . . . . . p k-1 r ( k-1 k-2 )p k-2 r ( k-1 k-3 )p k-3 r ... (k-1)p r 0 p k 1 ( k k-1 )p k-1 1 ( k k-2 )p k-2 1 ... ( k 2 )p 2 1 kp 1 . . . . . . . . . . . . . . . p k r ( k k-1 )p k-1 r ( k k-2 )p k-2 r ... ( k 2 )p 2 r kp r                   
and by Proposition 5.4,

w k (P ) = dim M k = Rank Λ k (5.2)
for all k ∈ N. We will use this definition of the numbers w k (P ) in our computations.

Proof of Proposition 5.3(iii). If p i are linear, p i (x) = c i x, i = 1, . . . , r, formula (5.1) and Lemma 2.2 (ii) imply

M k = span              c 1 0 ...
0 0 ... c k 1 0 ... ( k k-1 )c k-1 1 ... ... kc 1 . . . . . . . . . . . . . . . . . . 0 0 ... c k r 0 ... ( k k-1 )c k-1 r ... ... kc r              mod 1 = span             
... c r              mod 1, and one has F r k ⊆ M k iff k ≥ r.

Examples of computation of Weyl complexity.

Consider the system P = {x, 2x, x 2 }. Using the formula (5.2) and Lemma 2.2(ii) we get w 1 (P ) = Rank

x 2x

x 2 = rank

1 0 2 0 0 1 = 2, w 2 (P ) = Rank    x 0 2x 0 x 2 0 x 2 2x 4x 2 4x x 4 2x 2    = rank   1 0 0 0 0 2 0 0 0 0 0 1 0 0 0 0 1 0 2 0 0 4 0 4 0 0 0 1 0 2   = 4, w 3 (P ) = Rank        x 0 0 2x 0 0 x 2 0 0 x 2 2x 0 4x 2 4x 0 x 4 2x 2 0 x 3 3x 2 3x 8x 3 12x 2 6x x 6 3x 4 3x 2        = rank     
1 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 4 0 0 0 4 0 0 0 0 0 0 0 1 0 0 2 0 0 0 0 0 1 0 0 0 3 0 3 0 0 0 8 0 0 0 12 0 6 0 0 0 0 0 1 0 0 3 0 3

     = 7 = w 2 + 3,
and thus, W (P ) = 3. (Recall that V (P ) = 2.)

In contrast, for the system P = {x, 2x, x 3 },

w 1 (P ) = Rank x 2x x 3 = rank 1 0 2 0 0 1 = 2, w 2 (P ) = Rank    x 0 2x 0 x 3 0 x 2 2x 4x 2 4x x 6 2x 3    = rank   1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 2 0 0 4 0 0 4 0 0 0 0 1 0 2   = 5,
and therefore, W (P ) = 2. One can easily see that for any system P of 3 polynomials one has

W (P ) ≤ 3. For example, if a, b, c, d ∈ Z with (a, b) = (c, d), then V (x, ax + bx 2 , cx + dx 2 ) = 2 if at least one of b, d is nonzero; W (x, ax + bx 2 , cx + dx 2 ) = 2 when both b and d are nonzero, W (x, ax, cx + dx 2 ) = 3.
In a recent preprint, [Fr], N. Frantzikinakis classifies all the possibilities for the values of the Weyl complexity for a system of 3 polynomials.

Characteristic factors and large intersections

In this Section we investigate some dynamical properties in Weyl systems: we describe what information is given by Weyl and Vandermonde complexities of a family of polynomials on quantitative multiple recurrence properties along this family. We begin with a simple example that gives a flavor of what we develop in the sequel. Let us consider the quasi-standard Weyl system on X = T 4 ,

T (x 1 , x 2 , x 3 , x 4 ) = (x 1 + α, x 2 + 2x 1 + α, x 3 + 3x 2 + 3x 1 + α, x 4 + 4x 3 + 6x 2 + 4x 1 + α),
where α ∈ T is irrational, and the system of polynomials P = {n, 2n, n 2 }, for which we know that V (P ) = 2 and W (P ) = 3. Let A 0 , A 1 , A 2 , A 3 be four measurable subsets of X with positive measure. We have the following results:

(i) If the sets A i do not depend on the first coordinate x 1 (that is, each

A i = T × I i with I i ⊆ T 3 ), then U C-lim µ X A 0 ∩ T -n A 1 ∩ T -2n A 2 ∩ T -n 2 A 3 > 0.
(ii) If the sets A i are independent of the algebra of subsets which depend only on

x 1 , x 2 (that is, µ T 2 (A i ∩ L x 1 ,x 2 ) = µ X (A i ), where L x 1 ,x 2 = {(x 1 , x 2 )} × T 2 , for almost all (x 1 , x 2 ) ∈ T 2 ) then U C-lim µ X A 0 ∩ T -n A 1 ∩ T -2n A 2 ∩ T -n 2 A 3 = µ X (A 0 )µ X (A 1 )µ X (A 2 )µ X (A 3 ).
(iii) If the sets A i are independent of the algebra of subsets which depend only on

x 1 , x 2 , x 3 then lim n→∞ µ X A 0 ∩ T -n A 1 ∩ T -2n A 2 ∩ T -n 2 A 3 = µ X (A 0 )µ X (A 1 )µ X (A 2 )µ X (A 3 ).
It can be shown (see Lemmas 6.3 and 6.7 and Proposition 7.5 below) that in each of these three statements, the hypothesis of the independence of the sets A i of the corresponding algebras cannot be weakened. Moreover, each of these results still holds if the variable n is replaced by any nonconstant integral polynomial h(n) (see Propositions 6.12-6.14).

We now move to the general situation. Throughout this section let P = {p 1 , . . . , p r } be a system of integral polynomials with zero constant term.

Let X and X be compact commutative Lie groups with normalized Haar measures µ X and µ X thereon, and let π: X -→ X be a surjective (and continuous) homomorphism. Denote by F z , z ∈ X , the fibers of π, F z = π -1 (z). For a function f ∈ L 1 (X), the conditional expectation E(f |X ) of f with respect to X is the function on X defined by

E(f |X )(z) = F z f dµ F z = F 0 f (z + x) dµ F 0 (x). (For f ∈ L 2 (X), E(f |X ) is the orthogonal projection of f onto the subspace π * (L 2 (X ))
of L 2 (X).) We will consider E(f |X ) as a function on X, as well as on X .

We say that a measurable set

A ⊆ X is independent of X if E(1 A |X ) = µ X (A); this is equivalent to saying that for almost all fibers F z , z ∈ Z, of π one has µ F z (A) = µ X (A). If A 1 , . . . , A r are subsets of X independent of X , then r i=1 A i ⊆ X r is independent of (X ) r .
We say that a measurable set B ⊆ X originates from

X if B = π -1 (B ) for some B ⊆ X . If B 1 , . . . , B r ⊆ X originate from X then r i=1 B i ⊆ X r originates from (X ) r . If B is a closed subgroup of X that originates from X then B = π -1 (B ) for the subgroup B = π(B) of X , and for any f ∈ C(X) one has B f dµ B = B E(f |X ) dµ B .
Let (X, T ) be a quasi-standard Weyl system. We will first show that if W (P ) ≤ k, then X k-1 is a characteristic factor for P . (Cf. [F1], §10 and [F3], p.54.) Put g(n) = n) . . . (n) and D n = g(n)∆ X r+1 , n ∈ Z. By Proposition 5.4, the torus H = n∈Z D n ⊆ X r+1 contains L r+1 k . Hence, the property of a point x = (x 1 , . . . , x d ) ∈ (T r+1 ) d to belong to H does not depend on the coordinates x k , . . . , x d . Thus, H = (π r+1 k-1 ) -1 (H k-1 ) so that H originates from X r+1 k-1 . Let f 0 , . . . , f r be continuous functions on X and let f = r i=0 f i (that is, f is the function on X r+1 defined by f (x 0 , . . . , x r ) = f 0 (x 0 ) • . . . • f r (x r )). Since H originates from X r+1 k-1 , we have

Id X T p 1 (
T p r
H f dµ H = H k-1 E(f |X r+1 k-1 ) dµ H k-1 . Since the sequence {D n } n∈Z is well distributed in H, U C-lim n D n f dµ D n = H f dµ H and U C-lim n D n E(f |X r+1 k-1 ) dµ D n = H E(f |X r+1 k-1 ) dµ H = H k-1 E(f |X r+1 k-1 ) dµ H k-1 .
For any z = (z 0 , . . . , z r ) ∈ X r+1 k-1 ,

E(f |X r+1 k-1 )(z) = z+L r+1 k f 0 ⊗. . .⊗f r dµ z+L r+1 k = r i=0 z i +L k f i dµ z i +L k = r i=0 E(f i |X k-1 )(z i ), so E(f |X r+1 k-1 ) = r i=0 E(f i |X k-1
). For any n we have

D n f dµ D n = ∆ X r+1 g(n)f dµ ∆ X r+1 = X f 0 • T p 1 (n) f 1 • . . . • T p r (n) f r dµ X ,
and similarly

D n E(f |X r+1 k-1 ) dµ D n = ∆ X r+1 k-1 g(n)E(f |X r+1 k-1 ) dµ ∆ X r+1 k-1 = X k-1 E(f 0 |X k-1 ) • T p 1 (n) E(f 1 |X k-1 ) • . . . • T p r (n) E(f r |X k-1 ) dµ X k-1 . Thus, U C-lim n X f 0 • T p 1 (n) f 1 • . . . • T p r (n) f r dµ X = U C-lim n X k-1 E(f 0 |X k-1 ) • T p 1 (n) E(f 1 |X k-1 ) • . . . • T p r (n) E(f r |X k-1 ) dµ X k-1 .
Since continuous functions are dense in L ∞ (X) in L 1 -topology, we obtain that X k-1 is a characteristic factor for the system P : Proposition 6.1. Let (X, T ) be a quasi-standard Weyl system, let W (P ) ≤ k, and let

f 0 , . . . , f r ∈ L ∞ (X). Then U C-lim n X f 0 • T p 1 (n) f 1 • . . . • T p r (n) f r dµ X = U C-lim n X k-1 E(f 0 |X k-1 ) • T p 1 (n) E(f 1 |X k-1 ) • . . . • T p r (n) E(f r |X k-1 ) dµ X k-1 .
We remark that one can derive from Proposition 6.1 and Theorem 3.5 the fact that the natural factor X k-1 is a characteristic factor for any (not necessarily quasi-standard) Weyl system. We do not give the details here since this fact is not needed in the sequel. Applying Proposition 6.1 to the characteristic functions 1 A 0 , . . . , 1 A r of subsets A 0 , . . . , A r of X that are independent of X k-1 we get Proposition 6.2. Let (X, T ) be a quasi-standard Weyl system, let W (P ) ≤ k, and let A 0 , . . . , A r be measurable subsets of

X independent of X k-1 . Then U C-lim n µ X A 0 ∩ T -p 1 (n) A 1 ∩ . . . ∩ T -p r (n) A r = r i=0 µ X (A i ).
To be sure that X k-1 , the (k-1)-st natural factor of X, is the "optimal" characteristic factor for a system of Weyl complexity k, we have to check that X k-2 is not characteristic. This is so indeed: Lemma 6.3. Let (X, T ) be a quasi-standard Weyl system of depth d ≥ k -1 and let W (P ) ≥ k. Then there exist functions f

0 , . . . , f r ∈ L ∞ (X) such that U C-lim n X f 0 • T p 1 (n) f 1 • . . . • T p r (n) f r dµ X = U C-lim n X k-2 E(f 0 |X k-2 ) • T p 1 (n) E(f 1 |X k-2 ) • . . . • T p r (n) E(f r |X k-2 ) dµ X k-2 .
Proof. By Proposition 5.4, H does not contain L r+1 k-1 . Thus there exists x = (x 0 , x 1 , . . . , x r ) ∈ L r+1 k-1 \ H. For each i = 0, 1, . . . , r fix a nonnegative continuous function

f i on X such that f i (x i ) > 0 and f 0 ⊗ f 1 ⊗ . . . ⊗ f r | H = 0. The function f 0 ⊗ f 1 ⊗ . . . ⊗ f r is zero on g(n)∆ X r+1 for all n, thus X f 0 • T p 1 (n) f 1 • . . . • T p r (n) f r dµ X = 0
for all n. On the other hand, each function E(f i |X k-2 ) is positive in a neighborhood of the point 0 in H k-2 , so

H k-2 E(f 0 |X k-2 ) ⊗ E(f 1 |X k-2 ) ⊗ . . . ⊗ E(f r |X k-2 ) dµ H k-2 > 0. Since the sequence {g(n)∆ X r+1 k-2 } n∈Z is well distributed in H k-2 , the last expression is equal to U C-lim n X k-2 E(f 0 |X k-2 ) • T p 1 (n) E(f 1 |X k-2 ) • . . . • T p r (n) E(f r |X k-2 ) dµ X k-2 .
In the case W (P ) < k, X k-1 is characteristic for the system P in a stronger sense: Proposition 6.4. Let (X, T ) be a quasi-standard Weyl system, let W (P ) < k, and let f 0 , . . . , f r ∈ L ∞ (X). Then

lim n→∞ X f 0 • T p 1 (n) f 1 • . . . • T p r (n) f r dµ X - X k-1 E(f 0 |X k-1 ) • T p 1 (n) E(f 1 |X k-1 ) • . . . • T p r (n) E(f r |X k-1 ) dµ X k-1 = 0. (6.1)
In particular, we obtain: Proposition 6.5. Let (X, T ) be a quasi-standard Weyl system, let W (P ) < k, and let A 0 , . . . , A r be measurable subsets of

X independent of X k-1 . Then lim n→∞ µ X A 0 ∩ T -p 1 (n) A 1 ∩ . . . ∩ T -p r (n) A r = r i=0 µ X (A i ).
To prove Proposition 6.4 we need to show that if at least one of the functions n) f r dµ = 0. This follows from the following fact: Lemma 6.6. If f 0 , . . . , f r are characters on X of which at least one is orthogonal to n) f r dµ = 0 for all but finitely many n ∈ Z.

f 0 , . . . , f r ∈ L ∞ (X) is orthogonal to the subspace L 2 (X k-1 ) of L 2 (X), then lim n→∞ X f 0 • T p 1 (n) f 1 • . . . • T p r (
L 2 (X k-1 ) then X f 0 • T p 1 (n) f 1 • . . . • T p r (
Proof. We may and, for simplicity, will assume that (X, T ) is a standard Weyl system:

X = T d , T (x 1 , x 2 . . . , x d ) = (x 1 + α, x 2 + x 1 , . . . , x d + x d-1
) (though the proof is the same for any quasi-standard system). Let [j] x d-j + p i (n) [d] α) , i = 0, . . . , r, and

f i = exp 2πi(m i,1 x 1 + . . . + m i,d x d ) ( * ) , m i,j ∈ Z, i = 0, . . . , r. Then T p i (n) f i = exp 2πi(m i,1 (x 1 + p i (n)α) + m i,2 (x 2 + p i (n)x 1 + p i (n) [2] α) + . . . +m i,d (x d + d-1 j=1 p i (n)
f 0 • r i=1 T p i (n) f i = exp 2πi(x 1 m 0,1 + r i=1 d j=1 m i,j p i (n) [j-1] +x 2 m 0,2 + r i=1 d j=2 m i,j p i (n) [j-2] + . . . +x d m 0,d + r i=1 m i,d + α r i=1 d j=1 m i,j p i (n) [j] , n ∈ Z. Thus, X f 0 • T p 1 (n) f 1 • . . . • T p r (n) f r dµ = 0 whenever at least one of the coefficients m 0,1 + r i=1 d j=1 m i,j p i (n) [j-1] , m 0,2 + r i=1 d j=2 m i,j p i (n) [j-2] , . . ., m 0,d + r i=1 m i,d
is nonzero, that is, when N (n)m = 0 where m is the vector [2] ... p r (n) [2] ... ... 0 p 1 (n) [d-2] ... p r (n) [d-2] 0 0 ... 0 0 0 ... 0 1 1 ... 1 0 p 1 (n) ... p r (n) ... ... 0 p 1 (n) [d-3] ... p r (n) [d-3] r+1) . After introducing the standard inner product on the space R (d-1)(r+1) , we interprete this identity as the fact that the vector m is orthogonal to the subspace r+1) . Comparing the formulas (6.2) and (4.2) we see that

     m 0,1 . . . m r,1 . . . m 0,d . . . m r,d      and N (n) is the matrix     1 1 ... 1 0 p 1 (n) ... p r (n) 0 p 1 (n) [2] ... p r (n) [2] 0 p 1 (n) [3] ... p r (n) [3] ... ... 0 p 1 (n) [d-1] ... p r (n) [d-1] 0 0 ... 0 1 1 ... 1 0 p 1 (n) ... p r (n) 0 p 1 (n)
... 1 0 0 ... 0 0 p 1 (n) ... p r (n) 0 p 1 (n) [2] ... p r (n) [2] ... ... 0 p 1 (n) [d-1] ... p r (n) [d-1] 0 0 ... 0 0 0 ... 0 0 p 1 (n) ... p r (n) ... ... 0 p 1 (n) [d-2] ... p r (n) [d-
(n) ... p r (n) 0 p 1 (n) [2] ... p r (n) [2] ... ... 0 p 1 (n) [d-1] ... p r (n) [d-1] 0 0 ... 0 0 p 1 (n) ... p r (n) ... ... 0 p 1 (n) [d-2] ... p r (n) [d-2] . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 ... 0 0 0 ... 0 ... ... 0 p 1 (n) ... p r (n)        m = 0 for all n ∈ Z, where m =      m 0,2 . . . m r,2 . . . m 0,d . . . m r,d      ∈ R (d-1)(
H = Span                  1 0 ... 0 0 0 ... 0 1
0 ... 1 p [d-1] r p [d-2] r ... p r                  (6.2) of R (d-1)( 0
H mod 1 = H d-1 . If W (p 1 , . . . , p r ) ≤ k -1 then H contains L r+1 k-1
, and thus H contains the subspace L k-1 = (0, . . . , 0, u 0,k-1 , . . . , u r,k-1 , . . . , u 0,d-1 , . . . , u r,d-1 ), u i,j ∈ R of R (d-1)(r+1) . But if f i is orthogonal to X k-1 for some i then m i,j = 0 for some j ≥ k and thus m is not orthogonal to L k-1 .

The following lemma shows that the assumption W (P ) < k in Proposition 6.4 cannot be weakened: Lemma 6.7. Let (X, T ) be a quasi-standard Weyl system of depth d ≥ k and let W (P ) ≥ k. Then there exist functions f 0 , . . . , f r ∈ L 1 (X) such that identity (6.1) does not hold.

Proof. In the notation of the proof of Lemma 6.6, if W (P ) ≥ k then H does not contain

L r+1

k-1 , and thus there exists a vector m = r+1) with m i 0 ,j 0 = 0 for some i 0 and some j 0 ≥ k and orthogonal to H. For the vector m

     m 0,2 . . . m r,2 . . . m 0,d . . . m r,d      ∈ Z (d-1)(
=         0 . . . 0 m 0,2 . . . m r,2 . . . m 0,d . . . m r,d         ∈ Z d(r+1) we then have N (n)m = 0 for all n. Put f i = exp 2πi(m i,1 x 1 + . . . + m i,d x d ) , i = 0, . . . , r; then, for any n ∈ Z, f 0 • T p 1 (n) f 1 • . . . • T p r (n) f r is a constant of modulus 1.
On the other hand, since m i 0 ,j 0 = 0 with j 0 ≥ k, we have E(f i 0 |X k-1 ) = 0, and thus

E(f 0 |X k-1 ) • T p 1 (n) E(f 1 |X k-1 ) • . . . • T p r (n) E(f r |X k-1 ) = 0 for all n ∈ Z.
We now turn to the Vandermonde complexity; let us assume that V (P ) ≤ k. To simplify notation, assume also that (X, T ) is a quasi-dtandard Weyl system of depth k (that is, X = X k = T k ). Let functions f i ∈ L 1 (X), i = 0, . . . , r, be nonnegative, with X f i dµ X > 0, and independent of X k-1 in a very strong sense: assume that they only depend on the last, kth coordinate of X. Then Proposition 6.8.

If V (p 1 , . . . , p r ) ≤ k then U C-lim n X f 0 •T p 1 (n) f 1 •. . .•T p r (n) f r dµ X > 0.
Proposition 6.8 is equivalent to the following:

Proposition 6.9. Let V (p 1 , . . . , p r ) ≤ k and let A i = X k-1 × I i , i = 0, . . . , r, where I 0 , . . . , I r are subsets of F k of positive measure. Then U C-lim n µ X A 0 ∩ T -p 1 (n) A 1 ∩ . . . ∩ T -p r (n) A r > 0.
Proof. We may assume that I 0 , . . . , I r are open intervals in

F k T. Let A = r i=0 A i . Since τ r+1 k (H) = F r+1 k , there is a point x ∈ H with τ r+1 k (x) ∈ I 0 × . . . × I r . Thus, A ∩ H = ∅. Since A ∩ H is open in H, µ H (A ∩ H) > 0. Since the sequence D n is well distributed in H, U C-lim n µ X A 0 ∩ T -p 1 (n) A 1 ∩ . . . ∩ T -p r (n) A r = U C-lim n µ D n (A ∩ D n ) = µ H (A ∩ H) > 0.
(i), (ii), (iii) as in Theorem 7.1; (iv) E contains no configuration of the form a, a + p 1 (mn + l), . . . , a + p r (mn + l) , a, n ∈ Z, with l ∈ {l 1 , . . . , l ν }.

Example. Consider the system {x, 2x, . . . , rx}. The Vandermonde complexity of this system equals r, and Span

   1 0 0 ... 0 1 p 1 p 2 1 ... p r-1 1 1 p 2 p 2 2 ... p r-1 2 . . . . . . . . . . . . 1 p r p 2 r ... p r-1 r    = span   1 0 0 ... 0 1 1 1 ... 1 1 2 2 2 ... 2 r-1 . . . . . . . . . . . . 1 r r 2 ... r r-1
  is the hyperplane described by the equation r i=0 (-1) i r i u (i) = 0. For m = 2 and l = 1, the vector u 0 = (1, 0, 1, 0, . . . , 1or0) is not contained in this hyperplane, and thus the pair (2, 1) separates the polynomials x, 2x, . . . , rx on the level r -1. Actually, the following holds: Lemma 7.3. For any r, m, l with l not divisible by m, the pair (m, l) separates the polynomials x, 2x, . . . , rx on the level r -1.

Proof. For any m and any l not divisible by m, the nonzero vectors u i corresponding to these m, l and the system {x, 2x, . . . , rx} are

         1 0 . . . 0 1 0 . . . 0 1 0 . . .          ,          0 1 0 . . . 0 1 0 . . . 0 1 . . .          , . . .          0 0 . . . 0 1 0 . . . 0 1 0 . . .         
; they are periodic with same distance b = m/ gcd(l, m) between "1"s. We therefore have to check that for some j ∈ {0, . . . , b -1} the number e j = 0≤i≤r i≡j mod b (-1) i r i is nonzero. Let λ be a primitive root of unity of degree b; then we have 0

= (λ -1) r = r i=0 (-1) i r i λ r-i = b-1 j=0 0≤i≤r i≡j mod b (-1) i r i λ r-j = b-1 j=0 e j λ r-j ,
and thus one of e j must be nonzero.

Since V (x, 2x, . . . , rx) = r, we obtain:

Corollary 7.4. For any r, m ≥ 2 there is a set E ⊂ Z of positive uniform density such that (i) for any system {q 1 , . . . , q s } of integral polynomials with zero constant term and with V (q 1 , . . . , q s ) ≤ r -1 and any nonconstant integral polynomial h, the set E is UC-positive with respect to the system q 1 (h(n)), . . . , q s (h(n)) ;

(ii) for any system {q 1 , . . . , q s } of integral polynomials with zero constant term and with W (q 1 , . . . , q s ) ≤ r -1, any nonconstant integral polynomial h and any integers c 1 , . . . , c s , the set E is UC-balanced with respect to the system q 1 (h(n)) + c 1 , . . . , q s (h(n)) + c s ;

(iii) for any system {q 1 , . . . , q s } of integral polynomials with zero constant term and with W (q 1 , . . . , q s ) < r -1, any nonconstant integral polynomial h and any integers c 1 , . . . , c s , the set E is balanced with respect to the system q 1 (h(n)) + c 1 , . . . , q s (h(n)) + c s ;

(iv) E contains no arithmetic progressions of the form a, a + (mn + l), . . . , a + r(mn + l) , a, n, l ∈ Z, with l not divisible by m.

Let {p 1 , . . . , p r } be a system of integral polynomials with zero constant term and with V (p 1 , . . . , p r ) > k and let integers m, l 1 , . . . , l ν be such that each of the pairs (m, l 1 ),. . .,(m, l ν ) separates these polynomials on the level k. Consider the system (Y, R) introduced at the end of the previous section, namely, Y = X×Z m and R(x, i) = (T x, i+1), where (X, T ) is a quasi-standard Weyl system of depth k. We keep the notation of the preceding section. Let, again, B = j∈Z m B j = j∈Z m (A j × {j}) where A j = X k-1 × I j , I j are open intervals in F k , j ∈ Z m . The dynamical reason for Theorem 7.2 being true is the following proposition:

Proposition 7.5. The intervals I j can be chosen so that B ∩ R -p 1 (mn+l) B ∩ . . . ∩ R -p r (mn+l) B = ∅ for all n ∈ Z and all l = l 1 , . . . , l ν .

Proof. Let l be one of l 1 , . . . , l ν Let d i = p i (l) mod m ∈ Z m , i = 0, . . . , r. Let u j = (u (0) j , . . . , u (r) j ) ∈ R r+1 , j ∈ Z m , where u (i) j = 1 if d i ≡ j and u (i) j = 0 otherwise. We have U = span(u j , j ∈ Z m ) mod 1 = j∈Z m u j t j , t j ∈ T = (t 0 , t d 1 , . . . , t d r ), t j ∈ T, j ∈ Z m ⊆ T r+1 .

Since (m, l) separates {p 1 , . . . , p r } on the level k, U is not contained in the subtorus τ r+1 k (H) of F r+1 k (where τ k is, again, the projection of X to F k , and where we identify F k with T). Hence, the preimage of τ r+1 k (H) in T m under the mapping (t 0 , t 1 , . . . , t m-1 ) → (t 0 , t d 1 , . . . , t d r ) ∈ F r+1 k is a proper subtorus of T m , so it is "negligible" in T m . Thus, there exist elements t j ∈ T for j ∈ Z m , such that not only (t 0 , t d 1 , . . . , t d r ) ∈ τ r+1 k (H), but also (t σ(0) , t σ(d 1 ) , . . . , t σ(d r ) ) ∈ τ r+1 k (H) for any permutation σ of Z m . Moreover, t j , j ∈ Z m , can be chosen so that this will hold for each l = l 1 , . . . , l ν . Put I j = (t j -δ, t j +δ) ⊂ T = F k , j ∈ Z m , where δ > 0 is small enough to ensure I σ( 0 Example. Consider the polynomial system {x, 2x, 3x, 4x}. We have V (x, 2x, 3x, 4x) = 4, and the pair (2, 1) separates x, 2x, 3x, 4x on the level 3. (Indeed, the vectors u 0 = (1, 0, 1, 0, 1) and u 1 = (0, 1, 0, 1, 0) are not contained in Span    1 0 0 0 1 x x 2

x 3 1 2x (2x) 2 (2x) 3 1 3x (3x) 2 (3x) 3 1 4x (4x) 2 (4x) 3    = span 1 0 0 0 1 1 1 1 1 2 4 8 1 3 9 27 1 4 16 64 .) Consider the Weyl system (Y, R) where Y = X×Z 2 with X = T 3 and R(x 1 , x 2 , x 3 , i) = (x 1 + α, x 2 + x 1 , x 3 + x 2 , i + 1) with an irrational α. For this system we have

τ 5 3 (H) = Span   
1 0 0 0 1 x x [2] x [3] 1 2x (2x) [2] (2x) [3] 1 3x (3x) [2] (3x) [3] 1 4x (4x) [2] (4x) [3]

   = Span    1 0 0 0 1 x x 2
x 3 1 2x (2x) 2 (2x) 3 1 3x (3x) 2 (3x) 3 1 4x (4x) 2 (4x) 3    = span 1 0 0 0 1 1 1 1 1 2 4 8 1 3 9 27 1 4 16 64 ⊂ F 5 3 = T 5 .

The space U = span{u 0 , u 1 } = span

1 0 0 1 1 0 0 1 1 0 =      t



 ∈ τ 5 3 (H) (this is so when t 0 = t 1 ). Next we choose δ > 0 such that for I 0 = (t 0 -δ, t 0 + δ) and I 1 = (t 1 -δ, t 1 + δ) one has I 0 × I 1 × I 0 × I 1 × I 0 ∩ τ 5 3 (H) = ∅ and I 1 × I 0 × I 1 × I 0 × I 1 ∩ τ 5 3 (H) = ∅.

For A 0 = X 2 ×I 0 ⊂ X and A 1 = X 2 ×I 1 ⊂ X we then have

A 0 ×A 1 ×A 0 ×A 1 ×A 0 ∩H = ∅ and A 1 × A 0 × A 1 × A 0 × A 1 ∩ H = ∅. Finally, we put B = (A 0 × {0}) ∪ (A 1 × {1}) ⊂ Y . Let now K =    Id Y R 2n+1 R 2(2n+1) R 3(2n+1) R 4(2n+1)    ∆ Y r+1 ⊂ Y 5 = X 5 × Z 5 2 .
Then K = H 0 ∪ H 1 where H 0 = H × {0, 1, 0, 1, 0} and H 1 = H × {1, 0, 1, 0, 1}. Since B 5 ∩ X 5 × {0, 1, 0, 1, 0} = A 0 × A 1 × A 0 × A 1 × A 0 × {0, 1, 0, 1, 0} and B 5 ∩ X 5 × {1, 0, 1, 0, 1} = A 1 × A 0 × A 1 × A 0 × A 1 × {1, 0, 1, 0, 1}, Since B ∩ R -p 1 (mn+l) B ∩ . . . ∩ R -p r (mn+l) B = ∅ for all n ∈ Z and l ∈ {l 1 , . . . , l ν }, the set E does not contain configurations of the form a, a + p 1 (mn + l), . . . , a + p r (mn + l).

Let {q 1 , . . . , q s } be a system of integral polynomials with zero constant term. Let W (q 1 , . . . , q s ) ≤ k, let h be a nonconstant integral polynomial, and let c 1 , . . . , c s ∈ Z. By Proposition 6.15

U C-lim n µ Y B ∩ R -q 1 (h(n))-c 1 B ∩ . . . ∩ R -q s (h(n))-c s B = µ Y (B) s+1 .
For n ∈ Z put E n = a ∈ Z : a, a + q 1 (h(n)) + c 1 , . . . , a + q s (h(n)) + c s ∈ E . We have U D(E n ) = µ Y B ∩ R -q 1 (h(n))-c 1 B ∩ . . . ∩ R -q s (h(n))-c s B , and so, U C-lim

n U D(E n ) = µ Y (B) s+1 = U D(E) s+1 .
If W (q 1 , . . . , q s ) < k, then by Proposition 6.17 we obtain lim n→∞ U D(E n ) = µ Y (B) s+1 = U D(E) s+1 .

Finally, let V (q 1 , . . . , q s ) ≤ k, and let h be a nonconstant integral polynomial. Put E n = a ∈ Z : a, a + q 1 (h(n)), . . . , a + q s (h(n)) ∈ E , n ∈ Z. By Proposition 6.18,

U C-lim n U D(E n ) = U C-lim n µ Y B ∩ R -q 1 (h(n)) B ∩ . . . ∩ R -q s (h(n)) B > 0.

  We recall that the upper Banach density d * (E) of a set E of integers is given by d* (E) = lim sup N -M →∞ |E∩[M,N ]| N -M +1 . When the limit lim N -M →∞ |E∩[M,N ]|N -M +1 exists we will denote it by d u (E).) Szemerédi's theorem has * Bergelson and Leibman were supported by NSF grants DMS-0345350 and DMS-0600042.

  Proposition 0.1. Let r ∈ N, let b 1 , b 2 , . . . , b r be distinct integers, and let m ∈ N and l ∈ Z, l ≡ 0 mod m. There exists a set E with d u (E) > 0 such that (i) For any integers b 1 , b 2 , . . . , b r-1 , m ∈ N and l ∈ Z the setN = n ∈ Z : {a, a + b 1 (m n + l ), a + b 2 (m n + l ), . . . , a + b r-1 (m n + l )} ⊂ E for some a ∈ Z is syndetic, but (ii) the set N = n ∈ Z : {a, a + b 1 (mn + l), a + b 2 (mn + l), . . . , a + b r (mn + l)} ⊂ Efor some a ∈ Z is empty.

  and for any continuous function f on M one has U C-lim n f (x n ) = M f dµ M . More generally, we will say that a sequence of tori {D n } n∈Z is well distributed in M if D n ⊆ M for all n, and for any continuous function f on M one has U C-lim n D n f dµ D n = M f dµ M .

  y n∈Z . For a torus D ⊆ X r we will denote by O(P, D) the orbit of D under the action of P , that is, O(P, D) = n∈Z T p 1 (n)

  ... ... c k r

  Assume that N (n)m = 0 for infinitely many n ∈ Z. Since the condition N (n)m = 0 is polynomial in n, we then have N (n)m = 0 for all n ∈ Z. In particular, N (0)m = 0, therefore (N (n) -N (0))m = 0 andN (0) N (n) -N (0)m for all n ∈ Z. We haveN (0) =11 ... 1 0 0 ... 0 0 0 ... 0 0 0 ... 0 ... ... 0 0 ... 0 0 0 ... 0 1 1 ... 1 0 0 ... 0 0 0 ... 0 ... ... 0 0 ... 0 .. 0 0 0 ... 0 0 0 ... 0 0 0 ... 0 ... ... 1 1 ...

  ) × I σ(d 1 ) × . . . × I σ(d r ) ∩ τ r+1 k (H) = ∅for all σ, and, again, for any choice of l ∈ {l 1 , . . . , l ν }. Now defineA j = X k-1 × I j ⊂ X. Then for any permutation σ of Z m , A σ(0) × A σ(d 1 ) × . . . × A σ(d r ) ∩ H = ∅. Let l ∈ {l 1 , . . . , l ν }. Put B j = A j × {j} ⊂ Y , j ∈ Z m , and B = j∈Z m B j . Let ∆ Y r+1 be the diagonal in Y r+1 . One has B ∩ R -p 1 (mn+l) B ∩ . . . ∩ R -p r (mn+l) B = ∅ for all n ∈ Z if B r+1 ∩ Id Y R p 1 (mn+l) . . . R p r (mn+l) ∆ Y r+1 = ∅ for all n ∈ Z. Let K = n∈Z Id Y R p 1 (mn+l) . . . R p r (mn+l) ∆ Y r+1 . Put z = (z, . . . , z) ∈ (Z m ) r+1 and ∆ z = ∆ X r+1 × z, z ∈ Z m . Then ∆ Y r+1 = z∈Z m ∆ z and K = z∈Z m H z , where H z = n∈Z Id Y R p 1 (mn+l) . . . R p r (mn+l)∆ z , z ∈ Z m . By Lemma 6.10, for each z ∈ Z m , H z = H × (z, d 1 + z, . . . , d r + z), and soB r+1 ∩ H z = B z × B d 1 +z × . . . × B d r +z ∩ H z = A z × A d 1 +z × . . . × A d r +z ∩ H × (z, d 1 + z, . . . , d r + z) = ∅.

  we obtainB 5 ∩ K = ∅. This implies B ∩ R -(2n+1) B ∩ R -2(2n+1) B ∩ R -3(2n+1) B ∩ R -4(2n+1) B = ∅ for all n ∈ Z.Proof of Theorem 7.2. In the notation of Proposition 7.5, take any point y ∈ Y . Since (Y, R) is an ergodic Weyl system, it is uniquely ergodic and so, U D a ∈ Z : R a y ∈ C = µ Y (C) for any open C ⊆ Y with µ Y (∂C) = 0. Define E = a ∈ Z : R a y ∈ B . Then U D(E) = µ Y (B) > 0, and for any s ∈ N and a, c 1 , . . . , c s ∈ Z one has a, a + c 1 , . .. , a + c s ∈ E iff R a y, R a+c 1 y, . . . , R a+c s y ∈ B iff R a y ∈ B ∩ R -c 1 B ∩ . . . ∩ R -c s B.

( * ) In the expression "2πi", π is not a projection but 3.14 . . ., and i is not the index appearing in the rest of the formula but √ -1.

Remark. If a set A is independent of X k-1 then so is the set T c A for any c ∈ Z; this implies that the assertions of Proposition 6.2 and Proposition 6.5 remain true if the intersection A 0 ∩ T -p 1 (n) A 1 ∩ . . . ∩ T -p r (n) A r is replaced by A 0 ∩ T -p 1 (n)-c 1 A 1 ∩ . . . ∩ T -p r (n)-c r A r with arbitrary c i ∈ Z (see also Proposition 6.15 and Proposition 6.17 below). A similar extension of Proposition 6.9 does not hold: one can construct an explicit example of a system of integer polynomials P = {p 1 , . . . , p r } with V (P ) = 2, integers c 1 , . . . , c r , a quasistandard Weyl system (T 2 , T ) and intervals I 0 , . . . , I r in T such that for

We will now obtain further refinements of the preceding results by considering the system of integral polynomials P (h) = p 1 (h(n)), . . . , p r (h(n)) , where h is any nonconstant integral polynomial. If h(0) = 0, by Proposition 5.3 the system P (h) has the same Weyl complexity as P . Let, again, g(n) =

. . .

, n ∈ Z; then even if h(0) = 0, we have: Lemma 6.10.

For any nonconstant integral polynomial h the sequence

Let x be a "generic" point of X, that is, let the coordinates of x and the elements α i ∈ T in the definition of the quasi-standard Weyl system be rationally independent. Then the closure

We may now strengthen Proposition 6.1: Proposition 6.11. Let W (P ) ≤ k and let f 0 , . . . , f r ∈ L ∞ (X). For any nonconstant integral polynomial h one has

Applying this to f i = 1 A i , we get Proposition 6.12. Let W (P ) ≤ k and let A 0 , . . . , A r be measurable subsets of X independent of X k-1 . For any nonconstant integral polynomial h one has

When W (P ) < k, Lemma 6.6 immediately implies: Proposition 6.13. If W (P ) < k and A 0 , . . . , A r are measurable subsets of X independent of X k-1 , then for any nonconstant integral polynomial h one has

(We will no longer deal with functions on X but only with subsets of X, though our statements can, of course, be easily reformulated in the language of functions.) Assuming that X has depth k, directly from Lemma 6.10 we get Proposition 6.14. Let V (P ) ≤ k and let

, where I 0 , . . . , I r are subsets of F k of positive measure. Then for any nonconstant integral polynomial h,

Let m ≥ 2 and Z m = Z/mZ. We will now investigate the non-connected Weyl system (Y, R) where Y = X × Z m and R: Y -→ Y is defined by R(x, j) = (T x, j + 1); for further generality, we will also add, when possible, "shifting constants" c i in the formulation of our results: Proposition 6.15. Let W (P ) ≤ k, and let B be a measurable subset of Y independent of X k-1 × Z m . Then for any nonconstant integral polynomial h and any c 1 , . . . , c r ∈ Z,

For l ∈ {0, . . . , m -1}, consider the system P (h(mn + l) = p 1 (h(mn + l)) + c 1 , . . . , p r (h(mn + l)) + c r of polynomials in the variable n. For any i and j, R -p i (h(mn+l))-c i B j ⊆ X × {j -d i } for all n ∈ Z, where d i = p i (h(l)) + c i mod m. Thus, for j 0 , j 1 , . . . , j r ∈ Z m , if j i = j 0 + d i for all i = 0, . . . , r then by Proposition 6.12

and otherwise

Since this is true for every l = 0, 1, . . . , m -1, we get

Remark. A similar proof allows one to get a more general result: Proposition 6.16. Let W (P ) ≤ k, and let B (0) , . . . , B (r) be measurable subsets of Y independent of X k-1 × Z m . Then for any nonconstant integral polynomial h

(This proposition gives Proposition 6.15 if we apply it to B (0) = B and

) Same remark applies also to Proposition 6.17 and, with certain modifications, to Proposition 6.18 below.

If in the proof of Proposition 6.15 we replace U C-lim by lim and Proposition 6.12 by Proposition 6.13, we get Proposition 6.17.

then for any nonconstant integral polynomial h and any

In the notation of Proposition 6.15, assume now that V (P ) ≤ k, X has depth k and B = j∈Z m B j = j∈Z m (A j × {j}) where each A j has form X k-1 × I j for I j ⊆ F k , j ∈ Z m , of positive measure. Then, in the same way, we obtain from Proposition 6.14 Proposition 6.18. For any nonconstant integral polynomial h,

Combinatorics

Let E ⊆ Z with U D(E) > 0 (that is, the uniform density U D(E) exists and is positive) and let P = {p 1 , . . . , p r } be a system of integral polynomials (with not necessarily zero constant term). For n ∈ Z, define

Recall that E is UC-positive with respect to

Theorem 7.1. For any k ∈ N and any system {p 1 , . . . , p r } of integral polynomials with zero constant term and with V (p 1 , . . . , p r ) > k, there is a set E ⊂ Z of positive uniform density such that (i) for any system of integral polynomials {q 1 , . . . , q s } with zero constant term and with V (q 1 , . . . , q s ) ≤ k and any nonconstant integral polynomial h the set E is UC-positive with respect to the system q 1 (h(n)), . . . , q s (h(n)) ; (ii) for any system {q 1 , . . . , q s } of integral polynomials with zero constant term and with W (q 1 , . . . , q s ) ≤ k, any nonconstant integral polynomial h and any integers c 1 , . . . , c s the set E is UC-balanced with respect to the system q 1 (h(n)) + c 1 , . . . , q s (h(n)) + c s ; (iii) for any system {q 1 , . . . , q s } of integral polynomials with zero constant term and with W (q 1 , . . . , q s ) < k, any nonconstant integral polynomial h and any integers c 1 , . . . , c s the set E is balanced with respect to the system q 1 (h(n)) + c 1 , . . . , q s (h(n)) + c s ; (iv) there exist nonzero integers m and l such that E contains no configuration of the form a, a + p 1 (mn + l), . . . , a + p r (mn + l) , a, n ∈ Z.

It is possible to characterize the pairs (m, l) that work for (iv). For fixed m and l, consider the vectors u j = (u andu (i) j = 0 otherwise; we assume here p 0 = 0. Let us say that the pair (m, l) separates p 1 , . . . , p r on the level

 for some j. This may only be the case when k < V (p 1 , . . . , p r ). On the other hand, for m large enough there exists l such that 0, p 1 (l), . . . , p r (l) are all different modulo m, and then the pair (m, l) separates p 1 , . . . , p r on the level k for all k < V (p 1 , . . . , p r ).

Example. For the system {x, x 2 , x + x 2 , x + 2x 2 }, m = 2 and l = 1 we have u 0 = 1 0 0 1 0

and u 1 = 0 1 1 0 1

. Since

, the pair (2, 1) separates x, x 2 , x + x 2 , x + 2x 2 on the level 1. For the same system and (m, l) = (3, 1) we have u 0 =

, u 2 = 0 0 0 1 0 , and so, the pair (3, 1) also separates x, x 2 , x + x 2 , x + 2x 2 on the level 1.

We may now strengthen Theorem 7.1: Theorem 7.2. For any k ∈ N, any system {p 1 , . . . , p r } of integral polynomials with zero constant term and with V (p 1 , . . . , p r ) > k, and any integers m, l 1 , . . . , l ν such that each of the pairs (m, l 1 ),. . .,(m, l ν ) separates p 1 , . . . , p r on the level k there is a set E ⊂ Z of positive uniform density such that