N
U
IVERSITA DI ISA
P
Facoltà di Scienze Matematiche, Fisiche e Naturali Corso di Laurea in Matematica
Tesi di Laurea Magistrale
Finite colorings, partition
regularity and families of large sets
Candidato:
Giacomo Bertolucci
Relatore:
Prof. Mauro Di Nasso
Contents
Introduction 3
Notations and conventions 6
1 A combinatorial proof of Moreira’s Theorem 7
1.1 Syndetic, thick and piecewise syndetic sets . . . 7 1.2 Moreira’s theorem . . . 8
2 Generalizations of Moreira’s Theorem 13
2.1 PS-chains and a first generalization of Moreira’s theorem . . . . 13 2.2 Families of large sets and a second generalization of Moreira’s
theorem . . . 19 2.3 Properties that syndetic sets does not have . . . 22
3 Monochromatic solutions of Diophantine equations 23
3.1 Quadratic Diophantine equations . . . 23 3.2 Cubic Diophantine equations . . . 28
4 Families of large sets 32
4.1 n-S-chains and S-subsets of Nn . . . . 32
4.2 Furstenberg families and partition regularity . . . 38 4.3 S-chains and tensor product of families . . . 40
Appendices 58
A A possible combinatorial proof of Theorem 1.6 58
B More on piecewise syndetic sets 63
C More on partition regular families 67
Introduction
Ramsey Theory is a branch of Combinatorics and Number Theory mostly de-veloped in the second half of the last century, which is currently a highly active area of research. Its foundation can be made to coincide with the publications of B.L. van der Waerden [29] (1927), and F.P. Ramsey [26] (1930). Today Ram-sey Theory has ramifications which reach logic, set theory, geometry, topology, algebra, analysis, dynamical systems, and so on. In order to give a definition of Ramsey Theory, we can say that it concerns the preservation of structures under partitions and the unavoidability of a certain regularity in “large enough” objects [16].
A central topic in Ramsey Theory is to determine which configurations have a monochromatic representative for every finite coloring N = C1t . . . t Crof the
natural numbers. Already in 1916, I. Schur [27] proved that for each finite color-ing of N there exists a monochromatic triple of the form {x, y, x + y}; as a con-sequence, there will always be also a monochromatic triple of the form {x, y, xy} (simply define a new coloring N = C10 t . . . t Cr0 with n ∈ Ci0 ⇔ 2n ∈ Ci). We
say that the sets {x, y, x + y} and {x, y, xy} are Ramsey families. Other Ram-sey families in this sense are {x, x + y, . . . , x + ky} and x, xy, . . . , xyk
for every k ∈ N (see [29]), and {x + p1(y), . . . , x + pk(y)} for all p1, . . . , pk ∈ Z[x]
with null constant term [8]. Rado’s Theorem [25] provides necessary and suffi-cient conditions for a system of linear polynomials in Z [x1, . . . , xn] to be
Ram-sey. However, many polynomial families are not Ramsey, such as {x, x + 2019} and {x, y, xy + 1}. In this field of research, one of the most elusive family is {x, y, x + y, xy}; in fact, the question of whether this simple family is Ramsey or not has remained unanswered for many years and it is still open. In 2017, J. Moreira showed that the members of a particular class of sets of functions are Ramsey families [23]; in particular, the family {x, x + y, xy} was proved to be Ramsey. In order to obtain his result, Moreira transferred the problem to the language of topological dynamics, then he solved the problem using dynamical methods inspired by [8] and [9]. However, Moreira remarked that his proof could be rephrased in a completely combinatorial way, showing this in the particular case of the family {x, x + y, xy}. The first chapter of this thesis focuses on that result.
This thesis is organized as follows. We will start by introducing some no-tations and conventions, and by defining the concepts of coloring, partition (quasi)-regularity and union (quasi)-regularity.
In Section 1.1 we will define the families of syndetic, thick and piecewise syndetic subsets of N, of which we will give some basic properties.
In Section 1.2 we will enunciate Moreira’s Theorem, stating that the mem-bers of a special class of families of functions are Ramsey; this is based on Theorem 1.6, which is a result by V. Bergelson and N. Hindman. We will give a combinatorial proof of Moreira’s Theorem, obtained from the original dynamical proof taking inspiration from a sketch by Moreira himself.
In Section 2.1 we will introduce a particular family of subsets of Nn, which
we will call PS-chains, and we will give some of their properties; we will prove that the image of a PS-chain under certain functions is piecewise syndetic (prod-uct chain property), and that the family of n-PS-chains (i.e. of PS-chains in Nn) is partition quasi-regular (partition chain property). We will use PS-chains and the relative statements in order to enunciate and prove a first
generaliza-tion of Moreira’s Theorem (Theorem 2.6), which adds some informageneraliza-tion about the largeness of the set of monochromatic configurations in terms of piecewise syndetic sets.
In Section 2.2 we will characterize a class of families of large sets which share appropriate features with the family of piecewise syndetic sets; we will say that the families in this class have the largeness property. For every family S ⊆ P(N) with the largeness property, we will define the S-chains retracing the definition of PS-chain. Then we will give a second generalization of Moreira’s Theorem (Theorem 2.12), replacing the family of piecewise syndetic sets with a generic family of large sets. We will also prove some properties of S-chains when S is a family of large sets.
In Section 2.3 we will exhibit some examples which show that the family of syndetic sets does not have some properties which the family of piecewise syndetic sets instead has; in particular it is not partition regular, it has not the largeness property, the partition chain property or the product chain property. In Chapter 3 we will show an application of our generalizations of Moreira’s theorem, proving the existence of a large set of monochromatic solutions for two particular classes of Diophantine equations. The first class (Section 3.1), which has already been identified by Moreira [23], is made by the equations of the form:
c1x21+ . . . + cnx2n− x0= 0,
where the coefficients c1, . . . , cnare nonzero integers with c1+ . . . + cn= 0. The
second class (Section 3.2) is made by equations of the form: c1x31+ . . . + cnx3n− x0y0= 0,
where the coefficients c1, . . . , cn are nonzero integers with c1+ . . . + cn = 0
satisfying appropriate conditions; as an example, the equation: x31+ x32− x3
3− x 3
4− yz = 0
belongs to this class. Our proofs are inspired by Moreira’s proof for the first class of equations.
In Section 4.1 we will generalize the concepts of syndeticity, thickness and piecewise syndeticity to subsets of a generic semigroup, giving some characteri-zations. Then we will show the (lack of) relations between these families in the case of the semigroup Nn and the corresponding families of chains, showing a
syndetic subset of Nn which is not an n-SY-chain (where SY is the family of syndetic subsets of N), and an n-SY-chain which is not a syndetic subset of Nn, and similar examples for thick sets and piecewise syndetic sets.
In Section 4.2 we will introduce Furstenberg families, i.e. families of subsets which are closed under the operation of taking a superset, and the main op-erations on them, giving some basic properties; we will show that intersection families, such as the family of piecewise syndetic subsets of N, are union regular. In Section 4.3 we will introduce the tensor product of families extending a usual operation between ultrafilters and we will show some of its properties; in particular we will prove that the tensor product is associative and it preserves being a Furstenberg family. We will also prove that the tensor product of n copies of a family S ⊆ P(X), denoted S⊗n, contains all the n-S-chains (under appropriate hypotheses); moreover, if S is a Furstenberg family then S⊗n is
the smallest Furstenberg family containing all the n-S-chains. This connection between tensor products and chains allows to transfer some properties of chains, such as the partition chain property and the product chain property, to prop-erties of tensor products. We will analyze the behavior of the tensor product with respect to other operations on families (taking a subfamily, taking the dual family, taking the smallest Furstenberg superfamily, taking the complementary family, taking the family of the complementary sets, taking the product family and taking the intersection family). Eventually, we will show that, under cer-tain hypotheses, the tensor product preserves filters, ultrafilters and partition quasi-regular families.
Theorem 1.6 is a weaker form of [7, Th. 4.5], which V. Bergelson and N. Hindman derived from a result by A. Leibman and Bergelson himself [8, Cor. 1.12]; the proof given in [8] uses methods of topological dynamics. A proof which makes use of the algebra of βN is given in [17]. A weaker form of Theorem 1.6 is proved by Moreira in [22] in a more general context; Moreira’s proof makes use only of combinatorial ideas, such as the Arithmetic van der Corput Trick [11]. In Appendix A we will display some sketches about a possible combinatorial proof for Theorem 1.6, trying to expand the one given by Moreira. We will see that many parts of it can effectively be improved and used in the proof of Theorem 1.6. It is open the possibility of also generalizing Moreira’s proof of the Arithmetic van der Corput Trick (possibly with additional assumptions). This would yield an improvement of Theorem 1.6.
In Appendix B we will analyze the properties of piecewise syndetic sets in more depth. We will prove a characterization of piecewise syndetic sets, showing that a subset A ⊆ N is piecewise syndetic if and only if there exists a syndetic set which is finitely embeddable in A. Next we will give the definitions of three notions of density for subsets of N: upper asymptotic density, lower asymptotic density and upper Banach density. Then we will enunciate some results stating that, if A, B ⊆ N have positive density in a certain sense, then A+B is piecewise syndetic (in some cases even in an appropriate strong form). At last we will expose another characterization of piecewise syndetic sets, stating that a subset A ⊆ N is piecewise syndetic if and only if A ∈ U for some ultrafilters U ∈ K (βN). Finally, in Appendix C we will prove the equivalence between being a par-tition quasi-regular family, having a filter as dual family and (for Furstenberg families) being a union of ultrafilters.
Notations and conventions
In this paper we will use the following notation, conventions and definitions. • N = Z+
= {1, 2, 3, 4, . . .}, while N0= N ∪ {0}.
• If A, B ⊆ N and n ∈ N, then:
– n + Adef= A + ndef= {n + k | k ∈ A};
– A − ndef= {k − n | k ∈ A, k > n} = {x ∈ N | x + n ∈ A}; – nAdef= n · Adef= Andef= A · ndef= {n · k | k ∈ A};
– A + Bdef= {k + h | k ∈ A, h ∈ B};
– A − Bdef= {k − h | k ∈ A, h ∈ B, k > h} =S
h∈B(A − h);
– A · B def= {k · h | k ∈ A, h ∈ B}.
• Given a set A and an r ∈ N, we will call r-coloring (or simply coloring) of A each partition A = C1t . . . t Crin non-empty subsets.
• Given a family S ⊆ P(X) of subsets of a set X, we will say that S is partition regular if, for all A ∈ S and for all colorings A = C1t . . . t Cr,
there exists 1 ≤ i ≤ r such that Ci ∈ S.
• Given a family S ⊆ P(X) of subsets of a set X, we will say that S is partition quasi-regular if, for all A ∈ S and for all colorings A = C1t . . . t
Cr, there exist B ∈ S and 1 ≤ i ≤ r such that B ⊆ Ci.
• Given a family S ⊆ P(X) of subsets of a set X, we will say that S is union regular if, for all A ∈ S and for all finite unions A = C1∪ . . . ∪ Cr, there
exists 1 ≤ i ≤ r such that Ci∈ S.
Observe that a partition quasi-regular family S ⊆ P(X) is automatically union quasi-regular, meaning that for all A ∈ S and for all finite unions A = C1∪ . . . ∪
Cr there exist B ∈ S and 1 ≤ i ≤ r such that B ⊆ Ci. Moreover, a partition
quasi-regular family which is closed under taking supersets is automatically union regular (see Remark 2.9).
• Given n ∈ N and f1, . . . , fk : Nn→ N, we say that {f1, . . . , fk} is a Ramsey
family if for each coloring N = C1t . . . t Cr there exist i ∈ {1, . . . , r} and
x ∈ Nn such that f
1
A combinatorial proof of Moreira’s Theorem
1.1
Syndetic, thick and piecewise syndetic sets
Two of the most common notions of large subsets of N are that of syndetic sets, i.e. sets with bounded gaps, and that of thick sets, i.e. sets which contain arbitrarily long intervals. A set which is syndetic relative to a thick set is called piecewise syndetic. The formal definitions are the following.
Definition 1.1. A subset S ⊆ N is called syndetic if there exists a finite subset F ⊆ N such that S − F = N. Equivalently, S ⊆ N is syndetic if there exists a n ∈ N such that {m, m + 1, . . . , m + n} ∩ S 6= ∅ for all m ∈ N.
Definition 1.2. A subset T ⊆ N is called thick if, for every finite subset F ⊆ G, there exists n ∈ N such that F + n ⊆ T . Equivalently, T ⊆ N is thick if for all n ∈ N there exists m ∈ N such that {m, m + 1, . . . , m + n} ⊆ T .
Observe that a subset T ⊆ N is thick if and only if T ∩ S 6= ∅ for all syndetic sets S ⊆ N.
Definition 1.3. A subset P ⊆ N is called piecewise syndetic if there exists a finite subset F ⊆ N such that P − F is thick. Equivalently, S ⊆ N is piecewise syndetic if P = S ∩ T for some syndetic set S and some thick set T .
We easily see that the property to be syndetic (resp. thick, resp. piecewise syndetic) is closed under supersets, addition and subtraction of natural numbers, i.e.:
• if P1⊆ P2⊆ N and P1 is syndetic (resp. thick, resp. piecewise syndetic),
then P2 is syndetic (resp. thick, resp. piecewise syndetic), too;
• if P ⊆ N is syndetic (resp. thick, resp. piecewise syndetic) and n ∈ N, then P + n and P − n are syndetic (resp. thick, resp. piecewise syndetic), too.
Furthermore, the property to be syndetic and the property to be piecewise syndetic are closed under multiplication by natural numbers, i.e. if P ⊆ N is (piecewise) syndetic and n ∈ N, then nP is (piecewise) syndetic, too. It is also true that, if any among P + n, P − n and nP is syndetic (resp. thick, resp. piecewise syndetic), with P ⊆ N and n ∈ N, then P is syndetic (resp. thick, resp. piecewise syndetic), too.
Again, if P is syndetic (resp. thick, resp. piecewise syndetic), then his subset {n ∈ N | n ∈ P, n > m} is syndetic (resp. thick, resp. piecewise syndetic), for all m ∈ N. For piecewise syndetic sets, the following proposition holds (see also Section 4.2).
Proposition 1.4. The family of piecewise syndetic sets is partition regular. Remark 1.5. Using the closure properties above, we obtain that the family of piecewise syndetic sets is also union regular. We will prove this statement in a more general form in Section 2.2 (see Proposition 2.8).
1.2
Moreira’s theorem
In this section we will consider Moreira’s Theorem on Ramsey families [23, Th. 1.4], and we will give a combinatorial proof inspired by Moreira’s proof of [23, Cor. 1.5]. We need to recall the following result, a weaker form of [7, Th. 4.5], which is in turn a variant of the Polynomial van der Waerden Theorem (see [8]). Theorem 1.6. Let B ⊆ N be a piecewise syndetic set and let p1, . . . , pl∈ Q[x]
be polynomial such that:
pi(0) = 0, ∀n ∈ Z pi(n) ∈ Z,
for all i ∈ {1, . . . , l}. Then there exist a piecewise syndetic set Y ⊆ N such that, for all y ∈ Y , the set:
{n ∈ N | n + p1(y), . . . , n + pl(y) ∈ B} = l \ m=1 B − pm(y) is piecewise syndetic.
In this thesis we will not give a complete proof of Theorem 1.6 (see also Appendix A). Next, we define a special class of functions.
Definition 1.7. Given i ∈ N, we say that a function f : Ni → Z is i-nice if, for all x1, . . . , xi−1∈ N, the function x 7→ f (x1, . . . , xi−1, x) is polynomial with
null constant term, i.e. if f is of the form:
f (x1, . . . , xi−1, x) = fd(x1, . . . , xi−1) · xd+ fd−1(x1, . . . , xi−1) · xd−1+ . . .
. . . + f2(x1, . . . , xi−1) · x2+ f1(x1, . . . , xi−1) · x,
for some d ∈ N0 and some f1, . . . , fd : Ni−1 → Q (if d = 0, this means that
f ≡ 0).
Now we can prove the main result of this section.
Moreira’s Theorem. Let F = F1∪ . . . ∪ Fs, with Fi a finite set of i-nice
functions for every i ∈ {1, . . . , s}. Then for any r-coloring N = C1t . . . t Cr,
there exist c ∈ {1, . . . , r} and infinitely many (s + 1)-tuples (x0, . . . , xs) ∈ Ns+1
such that:
{x0· . . . · xs} ∪ {x0· . . . · xj+ f (xj+1, . . . , xi) | 0 ≤ j < i ≤ s, f ∈ Fi−j} ⊆ Cc.
Putting F = F1= {0, Id} we obtain the following corollary.
Corollary 1.8. For any r-coloring N = C1t . . . t Cr, there exist c ∈ {1, . . . , r}
and infinitely many (x, y) ∈ N2 such that: {x, x + y, xy} ⊆ Cc.
This means, in particular, that {x, x + y, xy} is a Ramsey family. This is an important result, since it links the additive structure and the multiplicative structure of N. However, the set {x, y, x + y, xy} is not included in the fami-lies obtainable directly from Moreira’s Theorem, thus the question of whether {x, y, x + y, xy} is a Ramsey family or not remains unanswered.
Moreira’s Theorem also has relevant applications about Ramsey properties of (nonlinear) Diophantine equations such as x2
1−x22= y and x31+x32−x33−x34= yz
Proof of Moreira’s Theorem. We begin with the inductive construction of four sequences:
• a sequence (tn)n∈N0 in {1, . . . , r};
• a sequence (Bn)n∈N0of piecewise syndetic subsets of N such that Bn ⊆ Ctn for every n ≥ 0;
• an increasing sequence (yn)n∈N in N;
• another sequence (Dn)n∈N of piecewise syndetic subsets of N.
Using Proposition 1.4, we can choose t0such that Ct0 is piecewise syndetic, then we put B0
def
= Ct0. Now, supposing that n ∈ N and we have already defined tk, Bk for every k ∈ {0, . . . , n − 1} and yk, Dk for every k ∈ {1, . . . , n − 1}; we
want to define yn, Dn, tn and Bn.
• Firstly, for all i ∈ {1, . . . , s} and for all f ∈ Fi we define Gn(f ) to be the
(finite) collection of all functions g : Z → Z of the form: g (z) = n−1 Y k=m1+1 yk ! · · f Ñ m2 Y k=m1+1 yk, m3 Y k=m2+1 yk, . . . , mi Y k=mi−1+1 yk, z · n−1 Y k=mi+1 yk é ,
where 0 ≤ m1 < m2 < . . . < mi−1 < mi < n. From the fact that f is
i-nice it immediately follows that, for all g ∈ Gn(f ), g is a polynomial in
Q[x] which satisfies:
g (0) = 0, ∀z ∈ Z g (z) ∈ Z. • From Theorem 1.6 with:
B = Bn−1, {p1, . . . , pl} = {0} ∪
[
f ∈F
Gn(f ),
we know that there exist a piecewise syndetic set Y ⊆ N such that, for all y ∈ Y : Bn−1∩ \ f ∈F \ g∈Gn(f ) Bn−1− g (y)
is piecewise syndetic. Then we choose yn ∈ Y , with the condition that
yn> yn−1. • We put: Dn def = Bn−1∩ \ f ∈F \ g∈Gn(f ) Bn−1− g (yn),
which, as we have just said, is piecewise syndetic. So ynDn is piecewise
syndetic as well.
• From Proposition 1.4, since ynDn = (ynDn∩ C1) t . . . t (ynDn∩ Cr) is
piecewise syndetic, there exists t ∈ {1, . . . , r} such that ynDn ∩ Ct is
• Finally we define:
Bn
def
= ynDn∩ Ctn,
which, as we said, is piecewise syndetic, and of course Bn⊆ Ctn.
Let n ∈ N; by definition of Bn we have Bn ⊆ ynDn, while by definition of
Dn we have Dn⊆ Bn−1; putting them together we obtain:
Bn ⊆ ynBn−1.
Iterating we deduce that:
∀m, n ∈ N0 m ≤ n =⇒ Bn⊆ n Y k=m+1 yk ! Bm. (1)
The sequence (tn)n∈N0 takes values in the finite set {1, . . . , r}, so there exists
c ∈ {1, . . . , r} and infinitely many (s + 1)-tuples (n0, . . . , ns) ∈ Ns+1 such that
tni = c for each i ∈ {0, . . . , s}. Let N be the (infinite) set of such tuples. For every N = (n0< . . . < ns) ∈ N , we define: ∀i ∈ {1, . . . , s} xN,i def = ni Y k=ni−1+1 yk.
Since N is infinite, then the value of the largest elements nsof the tuples N ∈ N
is unbounded, and so is xN,s, using that (yn)n∈Nis an increasing sequence. This
means that in this way we obtain an infinite set X of s-tuples (xN,1, . . . , xN,s).
Now, we fix N ∈ N and we simplify the notation denoting xi
def
= xN,i for
each i ∈ {1, . . . , s}; we will show that the set: Idef= Cc∩ \ 0≤j<i≤s \ f ∈Fi−j xj+1· . . . · xs· (Cc− f (xj+1, . . . , xi))
is not empty; this will conclude our proof. In fact, without lost of generality we can assume that the identically zero function belongs to Fs; if we take ex ∈ I,
then for j = 0, i = s and f ≡ 0 we havex ∈ xe 1· . . . · xs· Cc. Defining:
x0 def = xe x1· . . . · xs ∈ Cc, by definition of I we have: e x ∈ xj+1· . . . · xs· (Cc− f (xj+1, . . . , xi)) ∀0 ≤ j < i ≤ s, ∀f ∈ Fi−j; therefore: x0· x1· . . . · xj = = xe xj+1· . . . · xs ∈ Cc− f (xj+1, . . . , xi) ∀0 ≤ j < i ≤ s, ∀f ∈ Fi−j, and finally: x0· . . . · xj+ f (xj+1, . . . , xi) ∈ Cc ∀0 ≤ j < i ≤ s, ∀f ∈ Fi−j,
We just need to prove that I 6= ∅. We will show that Bns ⊆ I, so I is even piecewise syndetic. We already know that Bns ⊆ Ctns = Cc. Fix 0 ≤ j < i ≤ s and f ∈ Fi−j; we want to show that:
Bns ⊆ xj+1· . . . · xs· (Cc− f (xj+1, . . . , xi)) .
Let gf : Z → Z be the function in Gni(f ) obtained by putting mh = nj−1+h for all h ∈ {1, . . . , i − j}, i.e.:
gf(z) = Ñ ni−1 Y k=nj+1 yk é · · f Ñ n j+1 Y k=nj+1 yk, nj+2 Y k=nj+1+1 yk, . . . , ni−1 Y k=ni−2+1 yk, z · ni−1 Y k=ni−1+1 yk é = = Ñ ni−1 Y k=nj+1 yk é · f Å xj+1, xj+2, . . . , xi−1, z · xi yni ã . So, in particular: gf(yni) = Ñ ni−1 Y k=nj+1 yk é · f (xj+1, xj+2, . . . , xi−1, xi). (2)
Using (1) with m = ni and n = ns:
Bns⊆ ns Y k=ni+1 yk ! Bni; by definition of Bni: ns Y k=ni+1 yk ! Bni⊆ ns Y k=ni+1 yk ! yniDni = ns Y k=ni yk ! Dni; by definition of Dni: ns Y k=ni yk ! Dni ⊆ ns Y k=ni yk ! (Bni−1− g (yni)) ; using (2): ns Y k=ni yk ! (Bni−1− g (yni)) = = ns Y k=ni yk !Ñ Bni−1− Ñ ni−1 Y k=nj+1 yk é · f (xj+1, xj+2, . . . , xi−1, xi) é ;
using (1) with m = nj and n = ni− 1: ns Y k=ni yk !Ñ Bni−1− Ñ ni−1 Y k=nj+1 yk é · f (xj+1, xj+2, . . . , xi−1, xi) é =
= ns Y k=ni yk !ÑÑ ni−1 Y k=nj+1 yk é Bnj− Ñ ni−1 Y k=nj+1 yk é · f (xj+1, . . . , xi) é = = Ñ ns Y k=nj+1 yk é Bnj − f (xj+1, . . . , xi) = = xj+1· . . . · xs· Bnj − f (xj+1, . . . , xi) . Finally, by definition of Bnj: xj+1· . . . · xs· Bnj− f (xj+1, . . . , xi) ⊆ ⊆ xj+1· . . . · xs· Ä Ctnj − f (xj+1, . . . , xi) ä = = xj+1· . . . · xs· (Cc− f (xj+1, . . . , xi)) .
Putting all together:
Bns ⊆ xj+1· . . . · xs· (Cc− f (xj+1, . . . , xi)) , which is what we wanted.
2
Generalizations of Moreira’s Theorem
In this chapter we will generalize Moreira’s Theorem by using the notion of S-chain, for a fixed family of sets S. In Section 2.1 we will deal with the case in which S is the family of piecewise syndetic subsets of N. The general case is treated in Section 2.2.
2.1
PS-chains and a first generalization of Moreira’s
the-orem
In this section we will introduce the notion of chain for piecewise syndetic sets (see Section 2.2 for a more general definition). We will use some properties of this structure in order to improve our proof of Moreira’s Theorem, obtaining Theorem 2.6.
Given n, k ∈ N and given i1, . . . , ik ∈ {1, . . . , n}, we denote by:
πi1,...,ik : N
n −→
Nk (x1, . . . , xn) 7−→ (xi1, . . . , xik)
the projection on the coordinates i1, . . . , ik. Later in this thesis it will be
some-times convenient to use the notation (x0, . . . , xn) for elements of Nn+1; in that
case our notation will remain coherent with the above definition. For example, the projection on the x0 coordinate will be denoted as π1, and in general the
projection on the xi coordinate will be denoted as πi+1.
Definition 2.1. Given n ∈ N, we call n-PS-chain, or simply PS-chain, a subset Y ⊆ Nn with the following properties:
1. the set Y1
def
= π1(Y ) is piecewise syndetic;
2. for all k ∈ {2, . . . , n} and for all (y1, . . . , yk−1) ∈ π1,...,k−1(Y ), the set:
Yk(y1, . . . , yk−1)
def
= {yk ∈ N | (y1, . . . , yk−1, yk) ∈ π1,...,k(Y )}
is piecewise syndetic.
In other words, Y is an n-PS-chain if it can be constructed in this way: • take a piecewise syndetic set Y1;
• for all y1∈ Y1, take a piecewise syndetic set Y2(y1);
• for all y1∈ Y1, for all y2∈ Y2(y1), take a piecewise syndetic set Y3(y1, y2);
• iterate the procedure until for all y1 ∈ Y1, for all y2 ∈ Y2(y1), ..., for all
yn−1∈ Yn−1(y1, . . . , yn−2), one takes a piecewise syndetic set Yn(y1, . . .
. . . , yn−1).
• Then put:
Y = {(y1, . . . , yn) ∈ Nn| y1∈ Y1,
y2∈ Y2(y1), . . . , yn∈ Yn(y1, . . . , yn−1)} .
Recall the following notion, which is widely used in arithmetic Ramsey the-ory.
Definition 2.2. Given a subset Y ⊆ N, the set of finite products if Y is: FP (Y )def= Y y∈F y F ⊆ Y, F is finite, F 6= ∅ .
In a similar way, if y1, . . . , yn∈ N, then we put:
FP (y1, . . . , yn) def = ( Y i∈S yi S ⊆ {1, . . . , n} , S 6= ∅ ) = FP ({y1, . . . , yn}).
Similar definitions can be given in a generic (abelian) semigroup (see [18]). Now we have all we need to prove the following two lemmas, which will be useful later.
Lemma 2.3. Let n ∈ N and let Y ⊆ Nn be a PS-chain. Let H : Y → N be a
function such that:
∀ (y1, . . . , yn) ∈ Y H (y1, . . . , yn) ∈ FP (y1, . . . , yn).
Then the image of H is piecewise syndetic.
Proof. We prove the Lemma by induction on n. The case n = 1 is trivially true, since Y = Y1 is piecewise syndetic and H can only be the identity.
Let’s suppose now that the Lemma is true for n ≤ ˜n for some ˜n ∈ N; we will prove that it is also true for n = ˜n + 1, which will complete the proof. We define:
X def= π1,...,˜n(Y ),
which is so that:
Y = {(y1, . . . , yn˜, yn+1˜ ) | (y1, . . . , yn˜) ∈ X, yn+1˜ ∈ Yn+1˜ (y1, . . . , yn˜)} .
Let’s consider the set: X1
def
= {(y1, . . . , y˜n) ∈ X | ∃˜y˜n+1∈ Y˜n+1(y1, . . . , yn˜) s.t.
H (y1, . . . , yn˜, ˜yn+1˜ ) ∈ FP (y1, . . . , yn˜)} ⊆ X.
We distinguish two cases:
Case 1: X1= X. We define the function:
G : X −→ N
(y1, . . . , yn˜) 7−→ H (y1, . . . , yn˜, ˜yn+1˜ )
where ˜yn+1˜ is (one of) the element(s) of Yn+1˜ (y1, . . . , yn˜) the existence of
which is guaranteed by the definition of X1. Now we can use the induction
hypothesis for n = ˜n, applied to G, and we get that Im G is piecewise syndetic. Since Im G ⊆ Im H, then Im H is piecewise syndetic too.
Case 2: X1( X. Then there exists (y1, . . . , yn˜) ∈ X such that, for all yn+1˜ ∈
Yn+1˜ (y1, . . . , yn˜), we have:
H (y1, . . . , yn˜, yn+1˜ ) ∈ FP (y1, . . . , yn˜, y˜n+1) r FP (y1, . . . , y˜n),
hence:
H (y1, . . . , yn˜, yn+1˜ ) = yn+1˜ · p (y˜n+1),
for some p (yn+1˜ ) ∈ FP (y1, . . . , yn˜) ∪ {1}. Now we have:
Yn+1˜ (y1, . . . , yn˜) =
[
S⊆{1,...,˜n}
Y˜n+1(S),
where we have denoted: Y˜n+1(S) def= ( yn+1˜ ∈ Y˜n+1(y1, . . . , yn˜) p (yn+1˜ ) = Y i∈S yi ) ,
for each S ⊆ {1, . . . , ˜n} (we agree that Q
i∈Syi = 1 when S = ∅). Since
Yn+1˜ (y1, . . . , yn˜) is piecewise syndetic, by Remark 1.5 there exists S ⊆
{1, . . . , ˜n} such that Yn+1˜(S)is piecewise syndetic. Then we define the set: Y (S)def= ß (y1, . . . , y˜n, y˜n+1) yn+1˜ ∈ Y (S) ˜ n+1 ™ ⊆ Y, which is so that: H Y (S)= [ yn+1˜ ∈Y (S) ˜ n+1 {yn+1˜ · p (yn+1˜ )} = = [ y˜n+1∈Y (S) ˜ n+1 y˜n+1· Y i∈S yi = Ñ Y i∈S yi é · Yn+1˜(S).
Hence HY (S) is piecewise syndetic, and so is Im H, since Im H ⊇ H
Y (S).
Lemma 2.4. For each n ∈ N, the family of n-PS-chains is partition quasi-regular. I.e., let n, r ∈ N and let Y ⊆ Nn be a n-PS-chain. Given a function H : Y → {1, . . . , r}, there exists c ∈ {1, . . . , r} such that H (Y0) = {c} for some n-PS-chain Y0⊆ Y .
Proof. Again, we prove the Lemma by induction on n. The case n = 1 is equivalent to Proposition 1.4, hence it’s true.
Let’s suppose now that the Lemma is true for n ≤ ˜n for some ˜n ∈ N; we will prove that it is also true for n = ˜n + 1, which will complete the proof. For each y1∈ Y1, we define: X (y1) def =(y2, . . . , yn+1˜ ) ∈ N˜n (y1, y2, . . . , yn+1˜ ) ∈ Y .
It is easy to see that X (y1) is a ˜n-PS-chain. Defining:
Gy1 : X (y1) −→ {1, . . . , r} ,
(y2, . . . , y˜n+1) 7−→ H (y1, y2, . . . , yn+1˜ )
by inductive hypothesis we have:
∀y1∈ Y1, ∃c ∈ {1, . . . , r} , ∃ X0(y1) ⊆ X (y1) ˜n-PS-chain s.t. Gy1(X 0(y 1)) = {c} . Then we have: Y1= r [ c=1 Y1(c), where we have denoted:
Y1(c)def= {y1∈ Y1| ∃ X0(y1) ⊆ X (y1) ˜n-PS-chain s.t. Gy1(X
0(y
1)) = {c}} .
Since Y1 is piecewise syndetic, by Remark 1.5 there exists 1 ≤ c ≤ s such that
Y1(c) is piecewise syndetic. Defining: Y0 def= ¶(y1, . . . , yn+1˜ ) ∈ Y y1∈ Y (c) 1 , (y2, . . . , y˜n+1) ∈ X0(y1) © , we have that Y0 is a (˜n + 1)-PS-chain such that H (Y0) = {c}, which is our thesis.
Remark 2.5. Since the 1-PS-chains are exactly the piecewise syndetic sets, then the family of 1-PS-chain is also partition regular. Conversely, for all n ∈ N with n > 1, the family of n-PS-chains is not partition regular (this is because the family of n-PS-chains is not closed under taking supersets; see also Chapter 4). For example, Nn
is an n-PS-chain; defining H : Nn→ {1, 2} such that:
H (y1, . . . , yn) = ß 1 if y1= 1, ∃ 2 ≤ i ≤ n s.t. yi6= 1 2 otherwise , neither: H−1(1) = {1} ×ÄNn−1r {1}n−1 ä nor: H−1(2) = (N r {1}) × Nn−1 ∪ {1}n
are n-PS-chain, even if H−1(2) contain the n-PS-chain (N r {1}) × Nn−1.
We can finally prove the following generalization of Moreira’s Theorem. Theorem 2.6. Let F = F1∪ . . . ∪ Fs, with Fi a finite set of i-nice functions
for all i ∈ {1, . . . , s}. Then for any r-coloring N = C1t . . . t Cr, there exist
c ∈ {1, . . . , r} and a subset X ⊆ Ns+1such that:
1. for all (x0, . . . , xs) ∈ X it holds that:
x0· . . . · xs∈ Cc;
2. for every i ∈ {0, . . . , s} the projection πi+1(X) is piecewise syndetic;
i.e., the values of the component xi form a piecewise syndetic set when
(x0, . . . , xs) ranges over X;
3. for all (x1, . . . , xs) ∈ π2,...,s+1(X), the set:
{x0∈ N | (x0, x1, . . . , xs) ∈ X}
is piecewise syndetic; i.e., fixed (x1, . . . , xs) ∈ Ns, the set:
{x0∈ N | (x0, x1, . . . , xs) ∈ X}
is either empty or piecewise syndetic.
Observe that when s = 1 Theorem 2.6 is exactly Theorem 1.6.
Proof. We fix r, s, F1, . . . , Fs and the coloring N = C1t . . . t Cr, then we
define t0 and B0 as in the proof of Moreira’s Theorem. Now we consider the
constructions of Gn, Bn, Dn, tn and yn which we have done in that proof:
• for all i ∈ {1, . . . , s} and for all f ∈ Fi, the set Gn(f ) depends only on
y1, . . . , yn−1;
• the set Dn depends only on Bn−1, Gn(f ) (where f ranges in F ) and yn,
so by the previous point it depends only on Bn−1, y1, . . . , yn;
• tn depends only on yn and Dn, hence it depends only on Bn−1, y1, . . . , yn;
• the set Bn depends only on yn, Dn and tn, then it depends only on
Bn−1, y1, . . . , yn.
From the last point, we can immediately prove by induction on n that Bn
depends only on y1, . . . , yn, for all n ∈ N. Hence the set:
Yn def = y ∈ N y > yn−1, Bn−1∩ \ f ∈F \ g∈Gn(f )
Bn−1− g (y) is piecewise syndetic
depends only on y1, . . . , yn−1 and it is piecewise syndetic, as we stated in the
proof of Moreira’s Theorem. Then the set: Y def= (y1, . . . , ysr+1) ∈ Nsr+1 y1∈ Y1, y2∈ Y2(y1), . . . , ysr+1∈ Ysr+1(y1, . . . , ysr) is a (sr + 1)-PS-chain.
Given (y1, . . . , ysr+1) ∈ Y , the corresponding values of t1, . . . , tsr+1are sr+1
elements of the set {1, . . . , r}, hence by the Pigeonhole Principle there exist s+1 different indices n0, . . . , ns ∈ {1, . . . , sr + 1} such that tn0 = . . . = tns = c for some c ∈ {1, . . . , r}. Of course this c depends on y1, . . . , ysr+1; we denote as
corresponding value of c. By Lemma 2.4, there exist a (sr + 1)-PS-chain Y0⊆ Y and a c ∈ {1, . . . , r} such that H (Y0) = {c}. For all y = (y1, . . . , ysr+1) ∈ Y0,
let ty,1, . . . , ty,sr+1be the corresponding values of the ti’s and let ny,0< . . . <
ny,s∈ {1, . . . , sr + 1} be indices such that ty,ny,0= . . . = ty,ny,s= c; in analogy with the proof of Moreira’s Theorem, we define:
xy,i def = ny,i Y k=ny,i−1+1 yi,
for each i ∈ {1, . . . , s}; then we define: Iy def = Cc∩ \ 0≤j<i≤s \ f ∈Fi−j
xy,j+1· . . . · xy,s· (Cc− f (xy,j+1, . . . , xy,i)),
and finally: e Iy def = Iy xy,1· . . . · xy,s .
In a completely analogous way as in the proof of Moreira’s Theorem we have that, for all y ∈ Y , Iy is piecewise syndetic, hence eIy is piecewise syndetic too;
moreover, the set:
X def=¶(x0, xy,1, . . . , xy,s)
y ∈ Y, x0∈ eIy ©
satisfies point (1) of our thesis. It also trivially satisfies point (3), since eIy is
piecewise syndetic for every y ∈ Y . Of course this implies point (2) in the case i = 0. Fixed i ∈ {1, . . . , s}, let Hi0: Y → N be the function given by:
Hi0(y) = xy,i;
by Lemma 2.3 the set πi+1(X) = Im Hi0 is piecewise syndetic, which is point
2.2
Families of large sets and a second generalization of
Moreira’s theorem
In this section, we will rephrase Theorem 2.6 in a more general framework, isolating the properties of piecewise syndetic sets which are used in its proof. Definition 2.7. Given a family S ⊆ P (N) of subsets of natural numbers, we say that S has the largeness property if:
1. ∅ /∈ S and N ∈ S;
2. for all A ∈ S and for all B ⊇ A, B ∈ S;
3. for all A ∈ S and for all n ∈ N, {a ∈ A | a > n} ∈ S; 4. S is partition regular;
5. for all A ⊆ N and for all n ∈ N, nA ∈ S if and only if A ∈ S.
The families S which satisfy point (2) of the above definition are called Furstenberg families (see also Section 4.2). As we anticipated in Section 1.1, the following proposition holds.
Proposition 2.8. If S ⊆ P (N) has the largeness property, then it is union regular.
Proof. Let r ∈ N, A ∈ S, A = C1∪ . . . ∪ Cr. Then A = ‹C1t . . . t ‹Cr, where:
‹ C1 def = C1, C‹i def = Cir [ 1≤j<i Cj ∀i ∈ {2, . . . , r} .
We can assume that none of the ‹Ci’s is empty, otherwise we simply erase the
empty ones from the disjoint union. By partition regularity of S, there exists i ∈ {1, . . . , r} such that ‹Ci∈ S; since ‹Ci⊆ Ci, then Ci∈ S too.
Remark 2.9. In the previous proof we only used that S satisfies points (2) and (4) of the largeness property, i.e. that S is closed under taking supersets and it is partition regular. Observe that a partition quasi-regular family which is closed under taking supersets is automatically partition regular. See also Section 4.2.
The family of piecewise syndetic sets has the largeness property. Other examples of families with the largeness property are the family of sets with positive upper asymptotic density (see Appendix B for the definition), the family of syndetic subsets of (N, ·) (see Section 4.1) and the family of AP-rich sets, i.e. sets which contain arbitrarily long arithmetic progressions.
We define the S-chains for a generic family S ⊆ P(N) in the same way as we did for PS-chains.
Definition 2.10. Given n ∈ N and S ⊆ P (N), we call n-S-chain, or simply S-chain, a subset Y ⊆ Nn with the following properties:
1. π1(Y ) ∈ S;
2. for all k ∈ {2, . . . , n} and for all (y1, . . . , yk−1) ∈ π1,...,k−1(Y ):
The same definition can be used when S ⊆ P(X) for a generic set X. We say that S has the product chain property if Lemma 2.3 holds replacing the family of piecewise syndetic sets with S.
Definition 2.11. A family S ⊆ P (N) has the product chain property if for every n ∈ N, for every n-S-chain Y and for every function H : Y → N such that:
∀ (y1, . . . , yn) ∈ Y H (y1, . . . , yn) ∈ FP (y1, . . . , yn),
it holds that Im H ∈ S.
We say that S has the partition chain property if, for each n ∈ N, the family of n-S-chains is partition quasi-regular (i.e., if Lemma 2.4 holds replacing “PS” with “S”). We say that S has the Bergelson-Hindman property if, given B ∈ S, l ∈ N, p1, . . . , pl∈ Q[x] such that, for all i ∈ {1, . . . , l}, pi(0) = 0 and
∀n ∈ Z pi(n) ∈ Z, there exist a set Y ∈ S such that, for all y ∈ Y , the set:
{n ∈ N | n + p1(y), . . . , n + pl(y) ∈ B} = l
\
m=1
B − pm(y)
belongs to S. With these notations Theorem 1.6, Lemma 2.3 and Lemma 2.4 state that the family of piecewise syndetic sets has the Bergelson-Hindman prop-erty, the product chain property and the partition chain propprop-erty, respectively. Using the same arguments as in the proof of Lemma 2.3 and Lemma 2.4 we obtain that, if S ⊆ P (N) has the largeness property, then it also has the product chain property and the partition chain property. With a proof analogous to the ones of Moreira’s Theorem and Theorem 2.6, we can prove the following generalization.
Theorem 2.12. Let F = F1∪ . . . ∪ Fs, with Fi a finite set of i-nice functions
for all i ∈ {1, . . . , s}. Let S ⊆ P (N) be a family of sets with both the largeness property and the Bergelson-Hindman property. Then for any r-coloring N = C1t . . . t Cr, there exist c ∈ {1, . . . , r} and a subset X ⊆ Ns+1 such that:
1. for all (x0, . . . , xs) ∈ X it holds that:
x0· . . . · xs∈ Cc;
{x0· . . . · xj+ f (xj+1, . . . , xi) | 0 ≤ j < i ≤ s, f ∈ Fi−j} ⊆ Cc;
2. for all i ∈ {0, . . . , s} the projection πi+1(X) belongs to S; i.e., the values
of the component xi form a set Si∈ S when (x0, . . . , xs) ranges over X;
3. for all (x1, . . . , xs) ∈ π2,...,s+1(X), the set:
{x0∈ N | (x0, x1, . . . , xs) ∈ X}
belongs to S; i.e., fixed (x1, . . . , xs) ∈ Ns, we have:
{x0∈ N | (x0, x1, . . . , xs) ∈ X} ∈ S ∪ {∅} .
Some other results which will be useful later are the following, stating that a large set remains large if we subtract a finite number of elements from it, as well as an S-chain remains an S-chain (if S has the largeness property).
Proposition 2.13. If S ⊆ P (N) has the largeness property, A ∈ S and F ⊆ N is a finite set, then A r F ∈ S.
Proof. If mdef= max F , we have:
A r F ⊇ {a ∈ A | a > m} ,
which belongs to S by the largeness property; hence A r F ∈ S, again by the largeness property.
Corollary 2.14. If S ⊆ P (N) has the largeness property, Y is an n-S-chain for some n ∈ N and F ⊆ N is a finite set, then Y r F × Nn−1
is still an n-S-chain.
Proof. We have:
π1 Y r F × Nn−1 = π1(Y ) r F ∈ S,
by Proposition 2.13. Moreover, for all k ∈ {2, . . . , n} and for all (y1, . . . , yk−1) ∈
π1,...,k−1 Y r F × Nn−1, we have:
yk∈ N
(y1, . . . , yk) ∈ π1,...,k Y r F × Nn−1 =
= {yk ∈ N | (y1, . . . , yk) ∈ π1,...,k(Y )} ∈ S.
Corollary 2.15. If S ⊆ P (N) has the largeness property, Y is an n-S-chain for some n ∈ N and F ⊆ Nn
is a finite set, then Y r F is still an n-S-chain. Proof. By Proposition 2.13 we have:
π1(Y r F ) ⊇ π1(Y ) r π1(F ) ∈ S,
so π1(Y r F ) ∈ S by the largeness property. Moreover, for all k ∈ {2, . . . , n}
and for all (y1, . . . , yk−1) ∈ π1,...,k−1(Y r F ), again by Proposition 2.13 we
obtain:
{yk | (y1, . . . , yk) ∈ π1,...,k(Y r F )} ⊇
⊇ {yk| (y1, . . . , yk) ∈ π1,...,k(Y )} r πk(F ) ∈ S,
2.3
Properties that syndetic sets does not have
Theorem 1.6 is a weaker form of [7, Th. 4.5]; the latter states that Y (with the notation of Theorem 1.6) can be chosen with stronger properties than piecewise syndeticity; in particular, it can be chosen syndetic. This may suggest that our proof of Theorem 2.6 can be improved using this stronger result. However, it does not seem to be easily done, since syndetic sets does not have some of the properties of piecewise syndetic sets which we used as integral parts of that proof, as we will show in this section.
Proposition 2.16. SY is not partition regular. Moreover, for all S ∈ SY there exist A, B ∈ P (N) r SY disjoint such that A t B = S.
Proof. We define:
T def= {n ∈ N | the decimal representation of n has an even number of digits} . Both T and N r T are thick sets, so none of their subsets is a syndetic set; we put Adef= S ∩ T and Bdef= S r T , and the proof is completed.
Corollary 2.17. SY has neither the largeness property nor the partition chain property.
Proposition 2.18. SY does not have the product chain property. Moreover, for all n ∈ N with n ≥ 2, for all n-SY-chain Y , there exists a function H : Y → N such that:
∀ (y1, . . . , yn) ∈ Y H (y1, . . . , yn) ∈ F P (y1, . . . , yn),
but Im H /∈ SY.
Proof. Firstly we define the following subset T ⊆ N: T def= [
n∈N
¶
23n, 23n+ 1, . . . , 23n+ n©.
By definition, T is a thick set. Furthermore, we have: (T · T ) ∩ T = ∅; in fact, if a, b ∈ T with a ≤ b, then 23n≤ a ≤ 23n
+ n and 23m
≤ b ≤ 23m + m for some n ≤ m, so:
a · b ≥ 23n· 23m = 23n+3m > 21+3m = 2 · 23m > 23m+ m;
a · b ≤Ä23n+ nä Ä23m+ mä<Ä2 · 23nä Ä2 · 23mä= 22+3n+3m< 23·3m = 23m+1; hence a · b /∈ T . Then we can define:
H (y1, . . . , yn) def = y1 if y1∈ T/ y2 if y1∈ T, y2∈ T/ y1y2 if y1, y2∈ T .
3
Monochromatic solutions of Diophantine
equa-tions
3.1
Quadratic Diophantine equations
In [23], Moreira shows an application of his theorem to prove the existence of monochromatic solutions for a certain form of Diophantine equations; us-ing Theorem 2.12, we will now improve his proof obtainus-ing a stronger result (Theorem 3.2).
Definition 3.1. Given n ∈ N, a pointed set (S, 0S) and a function f : Nn→ S,
we say that the equation:
f (x1, . . . , xn) = 0S
is partition regular if, for any r ∈ N and for any r-coloring N = C1t . . . t Cr,
there exists a solution (a1, . . . , an) ∈ Nn with a1, . . . , an all of the same color.
Given S ⊆ P (N), we say that the equation f (x1, . . . , xn) = 0S is S-strongly
partition regular if, for any r ∈ N and for any r-coloring N = C1t . . . t Cr, there
exist a subset A ⊆ Nn and a c ∈ {1, . . . , r} such that:
1. all the components of the elements of A belong to the color Cc, i.e.:
∀i ∈ {1, . . . , n} πi(A) ⊆ Cc;
2. A is made of solutions for the equation f (x1, . . . , xn) = 0S, i.e.:
∀ (a1, . . . , an) ∈ A f (a1, . . . , an) = 0S;
3. each component of the elements of A range over a set in S, i.e.: ∀i ∈ {1, . . . , n} πi(A) ∈ S.
Moreover, if A can be chosen in such a way that his elements have pairwise distinct components, i.e.:
∀ (a1, . . . , an) ∈ A, ∀i, j ∈ {1, . . . , n} i 6= j =⇒ ai6= aj,
we say that the equation f (x1, . . . , xn) = 0S is S-strongly injective partition
regular.
Typical choices for (S, 0S) are (N, 0) and (R, 0).
Theorem 3.2. Let n ∈ N, n ≥ 2, and let c1, . . . , cn ∈ Z r {0} be such that
c1+ . . . + cn = 0. Let S ⊆ P (N) be a family of sets with both the largeness
property and the Bergelson-Hindman property. Then the equation: c1x21+ . . . + cnx2n− x0= 0
Proof. Consider the following polynomials: p1(t) def = c1(1 + t) 2 + c2(1 + 2t) 2 + . . . + cn(1 + nt) 2 = n X i=1 ci(1 + it) 2 , p2(t) def = n−1 X i=1 ci(1 + it) 2 + cn(1 + 2nt) 2 . We have: p1(0) = p2(0) = c1+ . . . + cn= 0.
Deriving these polynomials we obtain:
p01(t) = n X i=1 2ici(1 + it), p02(t) = n−1 X i=1 2ici(1 + it) + 4ncn(1 + 2nt) .
Evaluating them at t = 0 we have:
p01(0) = n X i=1 2ici, p02(0) = n−1 X i=1 2ici+ 4ncn= p01(0) + 2ncn.
Since cn6= 0, at least one of p01(0) and p02(0) is not zero, say pj(0), j ∈ {1, 2}. So
the second root of pj(t) is some t0∈ Q r {0} (it must be rational, since pj∈ Z[t]
and the other root is rational). We write t0=α/β, with α, β ∈ Z r {0}.
Case j = 1. We can put:
∀i ∈ {1, . . . , n} ui def = β + αi, obtaining: n X i=1 ciu2i = n X i=1 β2ci(1 + it0) 2 = β2p1(t0) = 0.
Case j = 2. We can put:
∀i ∈ {1, . . . , n − 1} ui def = β + αi, un def = β + 2αn, obtaining: n X i=1 ciu2i = n−1 X i=1 β2ci(1 + it0) 2 + β2cn(1 + 2nt0) 2 = β2p2(t0) = 0.
In both cases we have u1, . . . , un∈ Z such that:
c1u21+ . . . + cnu2n= 0. (3)
Observe that u1, . . . , unare pairwise distinct. We can assume that c1u1+ . . . +
cnun 6= 0, otherwise we simply change the sign of some nonzero ui. We can also
Now, let ddef= 2 (c1u1+ . . . + cnun) ∈ N; we define a new (r + d − 1)-coloring of N in this way: N = C10 t . . . t Cr0 t R1t . . . t Rd−1, where: ∀i ∈ {1, . . . , r} Ci0def= d · Ci; ∀i ∈ {1, . . . , d − 1} Ri def = d · N + i.
We also denote Cr+i0 def= Rifor all i ∈ {1, . . . , d − 1}. We can now apply Theorem
2.12 to this coloring, putting s = 1, F = {id, f0, . . . , fn} with id the identity
function, f0 the zero function and fi the function which maps k to uik, for all
i ∈ {1, . . . , n}; we obtain c ∈ {1, . . . , r + d − 1} and a subset X ⊆ N2such that: • Xr
def
= (y2, y1) ∈ N2
(y1, y2) ∈ X is a 2-S-chain;
• for all (y1, y2) ∈ X it holds that:
{y1y2, y1+ y2, y1, y1+ u1y2, . . . , y1+ uny2} ⊆ Cc0.
These two properties continue to hold if we remove from X all the couples (y1, y2) which satisfy:
y1y2= y1+ uiy2,
for some i ∈ {1, . . . , n}. In fact, if ui6= 0, then we have:
y1y2= y1+ uiy2 ⇐⇒ y2= y1 y1− ui = 1 + ui y1− ui ,
which has a finite number of solutions (y1, y2), since they are at most as many
as the number of divisors of ui; observe that, if y1− ui= 0, then we would have
y1= 0, which is impossible. Otherwise, if ui= 0, then we have:
y1y2= y1+ uiy2 ⇐⇒ y2= 1.
Hence, putting:
X0def= X r [
1≤i≤n
{(y1, y2) ∈ X | y1y2= y1+ uiy2},
by Corollaries 2.14 and 2.15 the set Xr0
def
=(y2, y1) ∈ N2
(y1, y2) ∈ X0 is still
a 2-S-chain.
The (r + d − 1)-coloring we defined has the property that all its colors Ci0are entirely contained in some congruence class modulo d, so, for all (y1, y2) ∈ X0,
we have:
y1y2≡ y1+ y2≡ y1≡ y1+ u1y2≡ . . . ≡ y1+ uny2 (mod d).
In particular:
y1+ y2≡ y1 (mod d) =⇒ y2≡ 0 (mod d) =⇒ y1y2≡ 0 (mod d),
hence the color Ccis contained in the congruence class of 0, i.e. 1 ≤ c ≤ r. This
means that, for all (y1, y2) ∈ X0, we have:
ny1y2 d , y1+ y2 d , y1 d, y1+ u1y2 d , . . . , y1+ uny2 d o ⊆ Cc.
We put: Adef= ny1y2 d , y1+ u1y2 d , . . . , y1+ uny2 d (y1, y2) ∈ X0 o .
• by construction, A satisfies point (1) of the definition of S-strongly parti-tion regular.
• A satisfies point (2) of the definition of S-strongly partition regular. In fact, if (y1, y2) ∈ X0, then: c1 y1+ u1y2 d 2 + . . . + cn y1+ uny2 d 2 = = 1 d2 n X i=1 ciy21+ 2ciuiy1y2+ ciu2iy22= = 1 d2 y 2 1 n X i=1 ci+ 2y1y2 n X i=1 ciui+ y22 n X i=1 ciu2i ! = = 1 d2(0 + y1y2d + 0) = y1y2 d , where we used (3).
• A satisfies point (3) of the definition of S-strongly partition regular. In fact, since Xr0 is a 2-S-chain, we have:
P def= {y1y2| (y1, y2) ∈ X0} = {y1y2| (y2, y1) ∈ Xr0} ∈ S,
using that S, having the largeness property, also has the product chain property; since d · π1(A) = P , by largeness property also π1(A) ∈ S.
Moreover, given i ∈ {1, . . . , n} andy2∈ π2(X0), since Xr0 is a 2-S-chain,
we have:
{y1| (y1, y2) ∈ X 0} ∈ S;
hence, by the largeness property:
P0def= {y1| (y1, y2) ∈ X0} + uiy2∈ S;
since P0 ⊆ d · πi+1(A), also d · πi+1(A) ∈ S, and finally πi+1(A) ∈ S,
again by the largeness property.
• A satisfies the definition of S-strongly injective partition regular. In fact, if (y1, y2) ∈ X0, then: 1 ≤ i < j ≤ n =⇒ ui6= uj =⇒ y1+ uiy2 d 6= y1+ ujy2 d ; moreover, given i ∈ {1, . . . , n}, if y1y2 d = y1+uiy2 d then y1y2 = y1+ uiy2,
which contradicts the definition of X0.
When S is the family of piecewise syndetic sets, which we denote with PS, we obtain the following corollary.
Corollary 3.3. Let n ∈ N, n ≥ 2, and let c1, . . . , cn ∈ Z r {0} be such that
c1+ . . . + cn= 0. Then the equation:
c1x21+ . . . + cnx2n− x0= 0
is PS-strongly injective partition regular.
Setting n = 2, c1 = 1 and c2 = −1 in Theorem 3.2, we obtain that the
equation:
x2− y2− z = 0
is S-strongly injective partition regular, for every S ⊆ P (N) which has both the largeness property and the Bergelson-Hindman Property.
3.2
Cubic Diophantine equations
We will now use an argument similar to the one deployed in the proof of Theorem 3.2, in order to show the S-strong injective partition regularity of another class of Diophantine equations, not considered by Moreira in [23].
Theorem 3.4. Let S ⊆ P (N) be a family of sets with both the largeness property and the Bergelson-Hindman property. Let n ∈ N, n ≥ 2, and let c1, . . . , cn ∈
Z r {0} be such that: • c1+ . . . + cn= 0;
• there exists v1, . . . , vn∈ Z such that:
c1v31+ . . . + cnv3n= 0, c1v1+ . . . + cnvn 6= 0.
Then the equation:
c1x31+ . . . + cnx3n− x0y0= 0
is S-strongly partition regular. Moreover, if v1, . . . , vn can be chosen in such a
way that they are pairwise distinct and: c1v12+ . . . + cnvn2
c1v1+ . . . + cnvn
6= vi ∀i ∈ {1, . . . , n} ,
then the above equation is S-strongly injective partition regular. Proof. We define: V def= c1v1+ . . . + cnvn 6= 0; ∀i ∈ {1, . . . , n} ui def = V · vi; then we have: c1u1+ . . . + cnun= V · (c1v1+ . . . + cnvn) = V2> 0; c1u31+ . . . + cnu3n= V 3 · c1v13+ . . . + cnvn3 = 0.
Observe that now we have: γdef= c1u 2 1+ . . . + c1u21 c1u1+ . . . + cnun = V 2· c 1v21+ . . . + cnv2n V2 ∈ Z.
Let ddef= 3 (c1u1+ . . . + cnun) ∈ N; we define a new (r + d − 1)-coloring of N in
this way: N = C10 t . . . t Cr0 t R1t . . . t Rd−1, where: ∀i ∈ {1, . . . , r} Ci0def= d · Ci; ∀i ∈ {1, . . . , d − 1} Ri def = d · N + i.
We also denote Cr+i0 def= Rifor all i ∈ {1, . . . , d − 1}. We can now apply Theorem
2.12 to this coloring, putting s = 1, F = {id, f0, g, f1, . . . , fn} with:
• f0 the zero function,
• g the function which maps k to γk,
• fi the function which maps k to uik, for all i ∈ {1, . . . , n};
we obtainc ∈ {1, . . . , r + d − 1} and a subset X ⊆ N2such that: • Xr
def
= (y2, y1) ∈ N2
(y1, y2) ∈ X is a 2-S-chain;
• for all (y1, y2) ∈ X it holds that:
{y1y2, y1+ y2, y1, y1+ γy2, y1+ u1y2, . . . , y1+ uny2} ⊆ Cc0.
As in the proof of Theorem 3.2, these two properties continue to hold if we replace X with: X0def= X r Ñ {(y1, y2) ∈ X | y1y2= y1+ γy2} ∪ ∪ [ 1≤i≤n {(y1, y2) ∈ X | y1y2= y1+ uiy2} é .
The (r + d − 1)-coloring we defined has the property that all its colors Ci0are entirely contained in some congruence class modulo d, so, for all (y1, y2) ∈ X0,
we have:
y1+ y2≡ y1 (mod d) =⇒ y2≡ 0 (mod d) =⇒ y1y2≡ 0 (mod d),
hence the color Ccis contained in the congruence class of 0, i.e. 1 ≤ c ≤ r. This
means that, for all (y1, y2) ∈ X0, we have:
ny1y2 d , y1+ γy2 d , y1+ u1y2 d , . . . , y1+ uny2 d o ⊆ Cc. We put: Adef=ny1y2 d , y1+ γy2 d , y1+ u1y2 d , . . . , y1+ uny2 d (y1, y2) ∈ X0 o . • by construction, A satisfies point (1) of the definition of S-strongly
parti-tion regular.
• A satisfies point (2) of the definition of S-strongly partition regular (mean-ing that the variables in the equation are ordered as (x0, y0, x1, . . . , xn)).
In fact, if (y1, y2) ∈ X0, then: c1 y1+ u1y2 d 3 + . . . + cn y1+ uny2 d 3 = = 1 d3 n X i=1 ciy31+ 3ciy21uiy2+ 3ciy1u2iy 2 2+ ciu3iy 3 2= = 1 d3 y 3 1 n X i=1 ci+ 3y21y2 n X i=1 ciui+ 3y1y22 n X i=1 ciu2i + y 3 2 n X i=1 ciu3i ! = = 1 d3 0 + y 2 1y2d + y1y22γd + 0 = y1y2 d · y1+ γy2 d .
• A satisfies point (3) of the definition of S-strongly partition regular. In fact, since Xr0 is a 2-S-chain, we have:
P def= {y1y2| (y1, y2) ∈ X0} = {y1y2| (y2, y1) ∈ Xr0} ∈ S,
using that S, having the largeness property, also has the product chain property; since d · π1(A) = P , by largeness property also π1(A) ∈ S.
Moreover, given i ∈ {1, . . . , n} and y2∈ π2(X0), since Xr0 is a 2-S-chain,
we have:
{y1| (y1, y2) ∈ X 0} ∈ S;
hence, by the largeness property:
P0def= {y1| (y1, y2) ∈ X 0} + u
iy2∈ S;
since P0 ⊆ d · πi+2(A), also d · πi+2(A) ∈ S, and finally πi+2(A) ∈ S,
again by the largeness property. For the same reason, π2(A) ∈ S too.
• With the stronger hypotheses on v1, . . . , vn we have that A satisfies the
definition of S-strongly injective partition regular. In fact, if (y1, y2) ∈ X0,
then: 1 ≤ i < j ≤ n =⇒ ui6= uj =⇒ y1+ uiy2 d 6= y1+ ujy2 d . Moreover, given i ∈ {1, . . . , n}, if y1y2 d = y1+uiy2 d then y1y2 = y1+ uiy2,
which contradicts the definition of X0, while if y1+γy2
d =
y1+uiy2
d then
γ = ui, which contradicts the hypothesis:
c1v12+ . . . + cnvn2 c1v1+ . . . + cnvn 6= vi. Finally, if y1+γy2 d = y1y2
d then y1+ γy2 = y1y2, which again contradicts
the definition of X0.
As for Theorem 3.2, when S = PS we obtain the following corollary. Corollary 3.5. Let n ∈ N, n ≥ 2, and let c1, . . . , cn∈ Z r {0} be such that:
• c1+ . . . + cn= 0;
• there exists v1, . . . , vn∈ Z such that:
c1v31+ . . . + cnv3n= 0, c1v1+ . . . + cnvn 6= 0.
Then the equation:
c1x31+ . . . + cnx3n− x0y0= 0
is PS-strongly partition regular. Moreover, if v1, . . . , vn can be chosen in such
a way that they are pairwise distinct and: c1v12+ . . . + cnvn2
c1v1+ . . . + cnvn
6= vi ∀i ∈ {1, . . . , n} ,
Setting n = 4, c1= c2= 1 and c3= c4= −1 we have:
483+ 63− 453− 273= 0, 48 + 6 − 45 − 27 6= 0,
483+ 63− 453− 273
48 + 6 − 45 − 27 = 23 /∈ {48, 6, 45, 27} ; then the following corollary holds.
Corollary 3.6. The equation:
x31+ x32− x3 3− x
3
4− yz = 0
is S-strongly injective partition regular, for every S ⊆ P (N) which has both the largeness property and the Bergelson-Hindman Property.
Remark 3.7. In Theorem 3.4 we need to assume the existence of v1, . . . , vn
satisfying:
c1v31+ . . . + cnv3n= 0, c1v1+ . . . + cnvn6= 0,
since there are equations which do not admit them; for example, there is no (v1, v2) ∈ Z2which satisfies both:
v13− v3
2= 0, v1− v26= 0.
Other Diophantine equations could be proved to be (injective) partition regu-lar or S-strongly (injective) partition reguregu-lar with simiregu-lar methods by exploiting Moreira’s Theorem or Theorem 2.12; however, while we did the step from the equation c1x21+ . . . + cnx2n− x0= 0 to the equation c1x31+ . . . + cnx3n− x0x00= 0
without any great difficulty, the step from these ones to an equation of degree four or more seem to be much more complex.
Many results are known about partition regularity of polynomial equations (see for example [3], [13] and [14]). In [2, Cor. 6.14] is stated the following proposition.
Proposition 3.8. Let p ∈ Z[x1, . . . , xn] be a homogeneous polynomial. These
facts are equivalent:
1. the equation p (x1, . . . , xn) = 0 is partition regular;
2. for every A ⊆ N which is piecewise syndetic in the semigroup (N, ·) (see Section 4.1 for the definition) there exist a1, . . . , an ∈ A such that:
p (a1, . . . , an) = 0.
The proof given in [2] makes use of ultrafilters and the structure of βN, which is strictly linked to piecewise syndeticity. The possibility of a generalization of Proposition 3.8 involving S-strong (injective) partition regularity should be investigated. However, the polynomials involved in the equations which we treat above in this section are not homogeneous.
4
Families of large sets
4.1
n-S-chains and S-subsets of N
nThe notions of syndetic, thick and piecewise syndetic set can be generalized to subsets of Nn; in fact, they can also be generalized to subsets of a generic semigroup. In this section we will give these generic definitions and we will see the relationships between these families of subsets of Nn and the corresponding
families of n-S-chains.
Definition 4.1. Given a semigroup (G, +) (not necessarily commutative), a subset A ⊆ G is called:
• syndetic if there exists a finite subset F ⊆ G such that: [
g∈F
−g + A = G;
• thick if, for every finite subset F ⊆ G, there exists g ∈ G such that: F + g ⊆ A;
• piecewise syndetic if there exists a finite subset F ⊆ G such that the set: [
g∈F
−g + A
is thick (as a subset of G). We used the notations:
−g + Adef
= {h ∈ G | g + h ∈ A} ∀g ∈ G, ∀A ⊆ G;
A + gdef= {a + g | a ∈ A} ∀g ∈ G, ∀A ⊆ G.
These definitions are coherent with the ones we gave for subsets of N. Given n ∈ N, we will use the following notations:
1. SYn is the family of syndetic subsets of Nn,
2. Tn is the family of thick subsets of Nn,
3. PSn is the family of piecewise syndetic subsets of Nn.
We will simply denote SY1, T1, PS1 with SY, T , PS respectively. Again, given
n, l, x1, . . . , xn∈ N, we will use the notation Cl(x1, . . . , xn) meaning the
follow-ing n-dimensional cube: Cl(x1, . . . , xn)
def
= {x1, x1+ 1, . . . , x1+ l} × . . . × {xn, xn+ 1, . . . , xn+ l} .
Now we will show some useful characterizations for the elements of the families SYn, Tn and PSn.
Proposition 4.2. Given n ∈ N and S ⊆ Nn, S ∈ SYn if and only if there
exists ∆ ∈ N such that, for all (x1, . . . , xn) ∈ Nn:
Proof. If S ∈ SYn, then by definition there exists a finite subset F ⊆ Nn such
that:
[
(a1,...,an)∈F
S − (a1, . . . , an) = Nn.
We choose ∆ to be the maximum value which appears as a component of some n-uple in F , i.e.:
∆def= max {πi(a) | a ∈ F, 1 ≤ i ≤ n}.
Given (x1, . . . , xn) ∈ Nn, let (a1, . . . , an) ∈ F such that:
(x1, . . . , xn) ∈ S − (a1, . . . , an) ;
then:
(x1+ a1, . . . , xn+ an) ∈ S ∩ C∆(x1, . . . , xn).
On the other hand, if S ⊆ Nn is such that, for some ∆ ∈ N and for all
(x1, . . . , xn) ∈ N:
S ∩ C∆(x1, . . . , xn) 6= ∅,
then we can choose:
F def= {1, . . . , ∆}n, and we have: [ (a1,...,an)∈F S − (a1, . . . , an) = Nn, i.e. S ∈ SYn.
Proposition 4.3. Given n ∈ N and T ⊆ Nn, T ∈ T
n if and only if, for all
N ∈ N, there exists (x1, . . . , xn) ∈ Nn such that:
CN(x1, . . . , xn) ⊆ T.
Proof. If T ∈ Tn, given N ∈ N, by definition, since CN(1, . . . , 1) is a finite set,
there exists (a1, . . . , an) ∈ Nn such that:
CN(1, . . . , 1) + (a1, . . . , an) ⊆ T ;
choosing xi = ai+ 1 for each i ∈ {1, . . . , n}, we have:
CN(x1, . . . , xn) ⊆ T.
On the other hand, if T ⊆ Nn
is so that, for all N ∈ N, there exists (x1, . . . , xn) ∈
N such that:
CN(x1, . . . , xn) ⊆ T,
then, given F ⊆ Nn a finite set, we can choose N to be the maximum value which appears as a component of some n-uple in F , i.e.:
Ndef= max {πi(a) | a ∈ F, 1 ≤ i ≤ n}.
Now we have:
F + (x1, . . . , xn) ⊆ CN(x1, . . . , xn) ⊆ T,
Proposition 4.4. Given n ∈ N and P ⊆ Nn, P ∈ PS
n if and only if:
∃∆ ∈ N, ∀N ∈ N, ∃ (x1, . . . , xn) ∈ Nn, ∀ (y1, . . . , yn) ∈ CN(x1, . . . , xn),
P ∩ C∆(y1, . . . , yn) 6= ∅.
Proof. If P ∈ PSn, then by definition there exists a finite subset F ⊆ Nn such
that:
[
(z1,...,zn)∈F
P − (z1, . . . , zn) ∈ Tn,
hence, by Proposition 4.3, for all N ∈ N there existsÄx(N )1 , . . . , x(N )n
ä ∈ Nnsuch that: CN Ä x(N )1 , . . . , x(N )n ä⊆ [ (z1,...,zn)∈F P − (z1, . . . , zn), i.e.: ∀ (y1, . . . , yn) ∈ CN Ä x(N )1 , . . . , x(N )n ä, ∃ (z1, . . . , zn) ∈ F s.t. (y1+ z1, . . . , yn+ zn) ∈ P.
Again, we choose ∆ to be the maximum value which appears as a component of some n-uple in F , i.e.:
∆def= max {πi(a) | a ∈ F, 1 ≤ i ≤ n}.
Then F ⊆ C∆(1, . . . , 1); hence, given N ∈ N, for all (y1, . . . , yn) ∈ CN
Ä x(N )1 , . . . . . . , x(N )n ä we have that: ∃ (z1, . . . , zn) ∈ F ⊆ C∆(1, . . . , 1) s.t. (y1+ z1, . . . , yn+ zn) ∈ P, and so: (y1+ z1, . . . , yn+ zn) ∈ P ∩ C∆(y1, . . . , yn).
On the other hand, if P ⊆ Nn is such that:
∃∆ ∈ N, ∀N ∈ N, ∃ (x1, . . . , xn) ∈ Nn, ∀ (y1, . . . , yn) ∈ CN(x1, . . . , xn),
P ∩ C∆(y1, . . . , yn) 6= ∅,
then we put F = C∆(1, . . . , 1); given N ∈ N, let (x1, . . . , xn) ∈ Nn be such that:
∀ (y1, . . . , yn) ∈ CN(x1, . . . , xn) P ∩ C∆(y1, . . . , yn) 6= ∅, hence: ∀ (y1, . . . , yn) ∈ CN(x1, . . . , xn), ∃ (z1, . . . , zn) ∈ F s.t. (y1+ z1, . . . , yn+ zn) ∈ P, i.e.: CN(x1, . . . , xn) ⊆ [ (z1,...,zn)∈F P − (z1, . . . , zn),
which means that:
[
(z1,...,zn)∈F
P − (z1, . . . , zn) ∈ Tn,
We can ask ourselves if the two concepts of n-SY-chains and syndetic subsets of Nn are in a fixed relation; we will now show that the answer is negative if
n ≥ 2 (while they are trivially equivalent for n = 1). Given n ≥ 2, let Y be the n-SY-chain defined by:
Y = {(y1, . . . , yn) ∈ Nn | ∀k ∈ {2, . . . , n} yk > y1} .
Y is actually an n-SY-chain. However, Y /∈ SYn by Proposition 4.2; in fact,
given ∆ ∈ N, we put (x1, x2, . . . , xn) = (∆ + 1, 1, . . . , 1); then:
Y ∩ C∆(x1, . . . , xn) = Y ∩
Ä
{∆ + 1, . . . , 2∆ + 1} × {1, . . . , ∆ + 1}n−1ä= ∅. On the other hand, the set:
Y0= {(1, . . . , 1)} ∪ (N r {1})n
is clearly syndetic as a subset of Nn (simply choose F = {(1, . . . , 1)}), but it is not an n-SY-chain, since the set {y2∈ N | (1, y2) ∈ π1,2(Y0)} = {1} is not
syndetic.
The set Y0we just defined is also a thick subset of Nn(choose g = (1, . . . , 1)) and a piecewise syndetic subset of Nn (choose F = {(1, . . . , 1)}); however, it is neither an n-PS-chain nor an n-T -chain, by the same argument as above. As an example of an n-T -chain (n ≥ 2) which is not a thick subset of Nn, we can
consider the following:
Z def= {(z1, . . . , zn) ∈ Nn| blog2(z2)c ≡ z1 (mod 2)} .
Z is actually an n-T -chain. However, Z /∈ Tn; in fact, if we take:
F = {(1, 1, . . . , 1) , (2, 1, . . . , 1)} ,
if (x1+ 1, x2+ 1, . . . , xn+ 1) ∈ Z, then blog2(x2+ 1)c ≡ x1+ 1 (mod 2), hence
blog2(x2+ 1)c 6≡ x1+ 2 (mod 2), ans so (x1+ 2, x2+ 1, . . . , xn+ 1) /∈ Z.
In order to complete our analysis of the possible relations between n-S-chains and Sn (with S = SY, T , PS), we only need to check if there exist some
n-PS-chains (n ≥ 2) which are not in PSn. Moreover, we will now display an
n-SY-chain (which of course is also an n-PS-chain) which is not a piecewise syndetic subset of Nn. Consider the following:
W def= {(w1, . . . , wn) | ∀k ∈ {2, . . . , n} wk≡ 0 (mod w1)} .
W is actually an n-SY-chain. In order to prove that W /∈ PSn, by Proposition
4.4 it is sufficient to show that:
∀∆ ∈ N, ∃N ∈ N, ∀ (x1, . . . , xn) ∈ Nn, ∃ (y1, . . . , yn) ∈ CN(x1, . . . , xn),
P ∩ C∆(y1, . . . , yn) = ∅.
Given N, x1, . . . , xn∈ N, we want to estimate from above the cardinality of the
intersection: W ∩ CN(x1, . . . , xn). We can write: CN(x1, . . . , xn) = N G i=0 Si,
where: Si def = {(y1, . . . , yn) ∈ CN(x1, . . . , xn) | y1= x1+ i} ∀i ∈ {0, . . . , N } . Hence, by definition of W : |W ∩ Si| = |{(x1+ i, y2, . . . , yn) ∈ Nn| ∀k ∈ {2, . . . , n} xk≤ yy ≤ xk+ N ∧ yk ≡ 0 (mod x1+ i)}| ≤ ≤° N + 1 x1+ i §n−1 <Å N + 1 1 + i + 1 ãn−1 =Å N + i + 2 i + 1 ãn−1 ; then: |W ∩ CN(x1, . . . , xn)| = N X i=0 |W ∩ Si| < N X i=0 Å N + i + 2 i + 1 ãn−1 . (4)
Fixed ∆ ∈ N, for any choice of N ∈ N and (x1, . . . , xn) ∈ Nn we can consider
the set: Ldef= {(x1+ k1(∆ + 1) , . . . , xn+ kn(∆ + 1)) | 0 ≤ k1, . . . , kn≤ ≤õ N + 1 ∆ + 1 û − 1 ™ ⊆ CN(x1, . . . , xn),
which has a cardinality equal to:
õ N + 1 ∆ + 1
ûn . L is defined in such a way that the following family:
{C∆(y1, . . . , yn) | (y1, . . . , yn) ∈ L}
consists oföN +1∆+1ùn disjoint “subcubes” of CN(x1, . . . , xn). If we choose N such
that, for all (x1, . . . , xn) ∈ Nn:
õ N + 1 ∆ + 1
ûn
> |W ∩ CN(x1, . . . , xn)| ,
then at least one of this cubes must be disjoint from W , and we have finished. We only need to prove that there is always such a feasible choice for N . We will limit our search to N > 2∆. By (4), it is sufficient to prove that:
∃N ∈ N, N > 2∆, õ N + 1 ∆ + 1 ûn ≥ N X i=0 Å N + i + 2 i + 1 ãn−1 . (5) We have: N > ∆ =⇒ õ N + 1 ∆ + 1 ûn ≥Å N + 1 ∆ + 1 − 1 ãn =Å N − ∆ ∆ + 1 ãn ; so (5) is implied by: ∃N ∈ N, N > 2∆, 1 (∆ + 1)n ≥ PN i=0 ÄN +i+2 i+1 än−1 (N − ∆)n . (6)
But: PN i=0 ÄN +i+2 i+1 än−1 (N − ∆)n ≤ PN i=0 ÄN +N +2 i+1 än−1 (N − ∆)n = =Å 2N + 2 N − ∆ ãn−1 · PN i=0 1 (i+1)n−1 N − ∆ ≤ Å 2N + 2 N − ∆ ãn−1 · PN i=0 1 (i+1)n−1 N +1 2 , where we used: N > 2∆ =⇒ N ≥ 2∆ + 1 =⇒ N − ∆ ≥ N − N − 1 2 = N + 1 2 . We have: lim N →+∞ Å 2N + 2 N + ∆ + 2 ãn−1 · 2 · PN i=0 1 (i+1)n−1 N + 1 = 0,
since the first factor tends to 2n−1and the last factor is the arithmetic mean of
the first N + 1 terms of the sequence: Ç 1 (i + 1)n−1 å i≥0 ,
which tends to 0, so the last factor tends to 0. Then also the RHS in (6) tends to 0, hence (6) holds.
Summarizing, if we denote as SYCn, T Cn, PSCn respectively the families of
n-SY-chains, n-T -chains and n-PS-chains, we achieved the following result. Proposition 4.5. For all n ≥ 2, it holds that:
SYn6⊆ SYCn, SYCn6⊆ SYn;
Tn6⊆ T Cn, T Cn6⊆ Tn,
4.2
Furstenberg families and partition regularity
In Section 1.1 we stated (Proposition 1.4) that the family of piecewise syndetic sets is partition regular, and we observed that it is also union regular; we proved the implication between partition regularity and union regularity in a more general context in Section 2.2 (Proposition 2.8). In fact, partition regularity is a common property to all the intersection families, as we will see in this Section. Definition 4.6. A Furstenberg family is a family S ⊆ P(N) of subsets of N which is closed under taking supersets, i.e. such that:
∀S ∈ S, ∀S0 ⊇ S S0∈ S. Given a family S, we call dual family of S the family:
S∗def= {T ⊆ N | ∀S ∈ S T ∩ S 6= ∅} ⊆ P(N),
which is always a Furstenberg family. Given two Furstenberg families S, T , we call product family of S and T the family:
S · T def
= {S ∩ T | S ∈ S, T ∈ T } ⊆ P(N),
which is a Furstenberg family. We call intersection family of S the family: b
Sdef = S · S∗.
The dual family of S is often defined as {T ⊆ N | N r T /∈ S} in the litera-ture.
Remark 4.7. If S is a Furstenberg family the two definitions of dual family coincide. Hence:
(S∗)∗= S.
The · product is clearly associative and commutative. Since S · {N} = S for every Furstenberg family S, the collection of Furstenberg families endowed with the · product is a commutative monoid, with {N} as the identity element.
As we anticipated above, the following proposition holds.
Proposition 4.8. Given any Furstenberg family S, the intersection family bS is always partition regular.
Proof. By induction, it is sufficient to prove the case of 2-coloring. Given P =
S ∩ T ∈ bS, with S ∈ S and T ∈ S∗, and a 2-coloring P = P
1 t P2, let
S0 def
= P1∪ (S r P ); then:
S0∩ T = (P1∪ (S r P )) ∩ T = (P1∩ T ) ∪ ((S ∩ T ) r (P ∩ T )) =
= P1∪ (P r P ) = P1.
Hence, if S0 ∈ S then P1∈ bS; otherwise, we have T0
def = N r S0∈ S∗; but: T0∩ S = (N r (P1∪ (S r P ))) ∩ S = S r ((S ∩ P1) ∪ ((S ∩ S) r (P ∩ S))) = = S r (P1∪ (S r P )) = S r (P1∪ (S r P )) = (S r P1) ∩ (S r (S r P )) = = (S r P1) ∩ (S ∩ P ) = (S r P1) ∩ P = P2, then P2∈ bS.
