nexoncn.com

文档资料共享网 文档搜索专家

文档资料共享网 文档搜索专家

当前位置：首页 >> >> Infinite partition regular matrices – solutions in central sets

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 355, Number 3, Pages 1213–1235 S 0002-9947(02)03191-4 Article electronically published on November 7, 2002

INFINITE PARTITION REGULAR MATRICES: SOLUTIONS IN CENTRAL SETS

NEIL HINDMAN, IMRE LEADER, AND DONA STRAUSS

Abstract. A ?nite or in?nite matrix A is image partition regular provided that whenever N is ?nitely colored, there must be some x with entries from N such that all entries of Ax are in the same color class. In contrast to the ?nite case, in?nite image partition regular matrices seem very hard to analyze: they do not enjoy the closure and consistency properties of the ?nite case, and it is di?cult to construct new ones from old. In this paper we introduce the stronger notion of central image partition regularity , meaning that A must have images in every central subset of N. We describe some classes of centrally image partition regular matrices and investigate the extent to which they are better behaved than ordinary image partition regular matrices. It turns out that the centrally image partition regular matrices are closed under some natural operations, and this allows us to give new examples of image partition regular matrices. In particular, we are able to solve a vexing open problem by showing that whenever N is ?nitely colored, there must exist ∞ injective sequences xn ∞ n=0 and zn n=0 in N with all sums of the forms xn + xm and zn + 2zm with n < m in the same color class. This is the ?rst example of an image partition regular system whose regularity is not guaranteed by the Milliken-Taylor Theorem, or variants thereof.

1. Introduction In 1933, R. Rado [9] characterized those (?nite) matrices with rational entries that are kernel partition regular, that is, those matrices A with the property that whenever N is ?nitely colored, there exists some x with monochrome entries such that Ax = 0. He showed that A is kernel partition regular if and only if A satis?es a computable property called the columns condition. (See [4] or [7] for a presentation and proof of Rado’s Theorem.) Sixty years later, several characterizations of (?nite) image partition regular matrices were obtained [5]. These are the matrices A with the property that whenever N is ?nitely colored, there will be some x (with entries from N) such that the entries of Ax are monochrome. Image partition regular matrices are of special interest because many of the classical theorems of Ramsey Theory are naturally stated as statements about image partition regular matrices. For example, Schur’s Theorem [10] and the length 4 version of van der Waerden’s Theorem [12] amount to the

Received by the editors May 10, 2001. 2000 Mathematics Subject Classi?cation. Primary 05D10; Secondary 22A15, 54H13. The ?rst author acknowledges support received from the National Science Foundation (USA) via grant DMS-0070593.

c 2002 American Mathematical Society

1213

1214

NEIL HINDMAN, IMRE LEADER, AND DONA STRAUSS

assertions that the matrices ?

1 ? 0 1

0 1 ? 1

? and

?

1 ? 1 ? ? 1 1

? 0 1 ? ? 2 ? 3

are image partition regular. In [6] additional characterizations of ?nite image partition regular matrices were obtained. Some of these involve the notion of central sets. Central sets were introduced by Furstenberg [3] and de?ned in terms of notions of topological dynamics. These sets enjoy very strong combinatorial properties. (See [3, Proposition 8.21] or [7, Chapter 14].) They have a nice characterization in terms of the algebraic ˇ structure of β N, the Stone-Cech compacti?cation of N. We shall present this characterization below, after introducing the necessary background information. Let (S, +) be an in?nite discrete semigroup. We take the points of βS to be the ultra?lters on S , the principal ultra?lters being identi?ed with the points of S . Given a set A ? S , we de?ne A = {p ∈ βS : A ∈ p}. The set {A : A ? S } is a basis for the open sets (as well as a basis for the closed sets) of βS . There is a natural extension of the operation + of S to βS making βS a compact right topological semigroup with S contained in its topological center. This says that for each p ∈ βS , the function ρp : βS → βS is continuous and for each x ∈ S , the function λx : βS → βS is continuous, where ρp (q ) = q + p and λx (q ) = x + q . See [7] for an elementary introduction to the semigroup βS . Any compact Hausdor? right topological semigroup (T, +) has a smallest twosided ideal K (T ) which is the union of all of the minimal left ideals of T , each of which is closed [7, Theorem 2.8], and any compact right topological semigroup contains idempotents. Since the minimal left ideals are themselves compact right topological semigroups, this says in particular that there are idempotents in the smallest ideal. There is a partial ordering of the idempotents of T determined by p ≤ q if and only if p = p + q = q + p. An idempotent p is minimal with respect to this order if and only if p ∈ K (T ) [7, Theorem 1.59]. Such an idempotent is called simply “minimal”. De?nition 1.1. Let (S, +) be an in?nite discrete semigroup. A set A ? S is central if and only if there is some minimal idempotent p such that A ∈ p. See [7, Theorem 19.27] for a proof of the equivalence of the de?nition above with the original dynamical de?nition. We present in Theorem 1.2 a few known characterizations of ?nite image partition regular matrices. (There and elsewhere we take N = {1, 2, 3, . . .} and ω = {0, 1, 2, . . .}. Also, ω is the ?rst in?nite cardinal.) We use the x notation throughout to represent both column and row vectors, expecting the reader to rely on the context to tell which is meant. Theorem 1.2. Let u, v ∈ N and let A be a u × v matrix with entries from Q. The following statements are equivalent. (a) A is image partition regular. (b) For every central subset C of N, there exists x ∈ Nv such that Ax ∈ C u . (c) For every central subset C of N, {x ∈ Nv such that Ax ∈ C u } is central in v N .

PARTITION REGULAR MATRICES: SOLUTIONS IN CENTRAL SETS

1215

(d) For each r ∈ Qv \{0} there exists b ∈ Q\{0} such that br A is image partition regular. (e) For every central subset C of N, there exists x ∈ Nv such that y = Ax ∈ C u , all entries of x are distinct, and for all i, j ∈ {1, 2, . . . , u}, if rows i and j of A are unequal, then yi = yj . Proof. [6, Theorem 2.10]. In?nite image partition regular matrices are also of signi?cant interest. For example, the Finite Sums Theorem (see [4, Theorem 3.15] or [7, Corollary 5.9]) is the assertion that the matrix ? ? 1 0 0 ... ? 0 1 0 ... ? ? ? ? 1 1 0 ... ? ? ? ? 0 0 1 ... ? ? ? ? 0 1 1 ... ? ? ? ? 1 1 1 ... ? ? ? . . . .. . . . . . . . (whose rows are all vectors with entries from {0, 1} with only ?nitely many 1’s and not all 0’s) is image partition regular. The fact, guaranteed by statement (d) of Theorem 1.2, that ?nite image partition regular matrices can be almost arbitrarily extended is very useful (and a property we would hope to maintain with in?nite image partition regular matrices). Another important property was originally established by W. Deuber in [1] in terms of “(m, p, c)-sets”. That property is an immediate consequence of Theorem 1.2(b), namely that if A and B are ?nite image partition regular matrices, then the matrix A O O B

is also image partition regular. The question of which in?nite matrices are image partition regular seems to be signi?cantly more complicated than the ?nite case. For example, it was shown in [2] that there are in?nite image partition regular matrices A and B such that the A O ) is not image partition regular. (See Theorem 2.2 below.) Not many matrix ( O B examples of in?nite image partition regular matrices are known. The matrices which we shall describe now have been essentially the only known examples, all based on the Milliken-Taylor Theorem ([8], [11], or see [7, Section 18.1]) or variants thereof. De?nition 1.3. Let a be a (?nite or in?nite) sequence in Q with only ?nitely many nonzero entries. Then c(a) is the ?nite sequence obtained by ?rst deleting all occurrences of 0 and then deleting any term equal to its predecessor. A compressed sequence is a (necessarily ?nite) sequence a such that c(a) = a. For example, if a = (1, 0, 0, 1, 1, ?2, 0, ?2, 0, 3, 0, 0, 0, 0, . . .), then c(a) = (1, ?2, 3). In [2, Theorem 2.5] it was shown that if A is an ω × ω matrix with entries from ω (and only ?nitely many nonzero entries on each row) such that the compressed forms

1216

NEIL HINDMAN, IMRE LEADER, AND DONA STRAUSS

of all rows were equal, then A is image partition regular, and it is a consequence of Corollary 3.6 below, that the same statement holds if the entries are allowed to come from Z, provided the rightmost nonzero entries are positive. It has not even been known if even the simplest diagonal sums are image partition regular. For example, let ? ? ? ? 1 1 0 ··· 1 2 0 ··· ? 1 0 1 ··· ? ? 1 0 2 ··· ? ? ? ? ? A = ? 0 1 1 · · · ? and B = ? 0 1 2 · · · ? . ? ? ? ? . . . . . . .. .. . . . . . . . . . . . . . . It is an immediate consequence of Ramsey’s Theorem that both A and B are image partition regular by way of vectors x and z without repeated terms, but it has not A O ) is image partition regular in the same fashion. That been known whether ( O B is, it has not been known whether whenever N is ?nitely colored, there must exist ∞ injective sequences xn ∞ n=0 and zn n=0 in N with all sums of the forms xn + xm and zn + 2zm with n < m in the same color class. In Section 2 we shall present some contrasts between ?nite and in?nite partition regular matrices and, motivated by considerations presented there, introduce the notions of centrally image partition regular matrices (those having images in any central subset of N) and strongly centrally image partition regular matrices (those centrally image partition regular matrices for which distinct rows produce distinct entries of the image). It turns out that these classes do have some of the closure properties that one would like. In particular, if A and B are both centrally image A O) partition regular or both strongly centrally image partition regular, then ( O B has the corresponding property. It is not true that matrices whose rows have the same compressed form are centrally image partition regular. However, we show in Section 3 that matrices whose rows have the same compressed form and the same nonzero row sum are strongly centrally image partition regular, and we show that the corresponding statement for matrices with row sums of zero is not true. We obtain as a consequence, in Corollary 3.8, new results about (ordinary) image partition regularity, such as the result mentioned in the abstract. 2. Contrasts between finite and infinite matrices We take, as the principal good properties of ?nite partition regular matrices that we would like in?nite partition regular matrices to share, the characterization of Theorem 1.2(d) and the result of [6, Corollary 2.11]. That is, we would like it to be true that whenever A is an in?nite image partition regular matrix and r ∈ Qω \{0} (with only ?nitely many nonzero entries) there should be some b ∈ Q\{0} such br that is image partition regular. We would also like it to be the case that A A O ). (If A whenever A and B are in?nite image partition regular matrices, so is ( O B A O and B are ω × ω matrices, then ( O B ) is an (ω + ω ) × (ω + ω ) matrix. We shall blissfully ignore this and similar distinctions throughout this paper.) We shall see in Theorems 2.1 and 2.2 that neither of our main wishes with respect to in?nite image partition regular matrices can be granted. Theorem 2.1. Let A be a matrix whose rows are all rows a ∈ Qω with only ?nitely many nonzero entries such that c(a) = (1, 2). Let r = 1 0 0 0 . . . . Then

PARTITION REGULAR MATRICES: SOLUTIONS IN CENTRAL SETS

1217

A is image partition regular, but there does not exist b ∈ Q such that image partition regular.

br A

is

Proof. As we remarked above, that A is image partition regular follows from [2, Theorem 2.5]. br Suppose we have b ∈ Q such that is image partition regular, and notice A m that trivially b > 0. Write b = n , where m and n are relatively prime positive integers. Case 1. m = 1. Given x ∈ N, let α(x) = max{t ∈ ω : mt |x}. For i ∈ {0, 1}, let Bi = {x ∈ N : α(x) ≡ i(mod 2)}. Choose i ∈ {0, 1} and x ∈ Nω such that br A

ω . x ∈ Bi

m m Then the ?rst row says that m n x0 ∈ Bi , and so α( n x0 ) ≡ i(mod 2). Also α( n x0 ) = α(mx0 ), since m and n are relatively prime. Consequently, α(x0 ) ≡ i (mod 2). Let s = α(x0 ) and pick F ∈ Pf (N) such that ms+1 | t∈F xt , where Pf (N) is the set of ?nite nonempty subsets of N. Pick G ∈ Pf (N) such that max F < min G br x and ms+1 | t∈G 2xt . Then x0 + t∈F xt + t∈G 2xt is an entry of A while α(x0 + t∈F xt + t∈G 2xt ) = s ≡ i (mod 2), a contradiction. Case 2. m = 1 and n = 1. Given x ∈ N, let α(x) = max{t ∈ ω : nt |x}. For i ∈ {0, 1}, let Bi = {x ∈ N : α(x) ≡ i (mod 2). Choose i ∈ {0, 1} and x ∈ Nω such that br ω . x ∈ Bi A 1 1 x0 ∈ Bi , and so α( n x0 ) ≡ i (mod 2). Consequently, Then the ?rst row says that n α(x0 ) ≡ i (mod 2). Choosing F and G as in Case 1, we again obtain a contradiction. Case 3. b = 1. For x ∈ N, let ?(x) count the number of odd length blocks of 0’s interior to the binary expansion of x. (More formally, if x = t∈F 2t and k = max F , then ?(x) = |{t ∈ F \{k } : (min{s ∈ F : s > t} ? t) is even}|.) For j ∈ {0, 1, 2}, let Bj = {x ∈ N : ?(x) ≡ j (mod 3)}. r ω x ∈ Bj . The ?rst row of Choose j ∈ {0, 1, 2} and x ∈ Nω such that A this equation says that ?(x0 ) ≡ j (mod 3). Choose inductively a sequence Ht ∞ t=1 in Pf (N) such that for each t, max Ht < min Ht+1 and, if 2s ≤ i∈Ht xi , then 2s+1 | i∈Ht+1 xi . For each t ∈ N, let zt = i∈Ht xi and choose Ft ∈ Pf (N) such that zt = i∈Ft 2i . Notice that for each t, max Ft < min Ft+1 . Pick s ∈ N such that 2s > x0 . Choose u < k < l in N such that ?(xu ) ≡ ?(xk ) ≡ ?(xl ) (mod 3), min Fu ≡ min Fk ≡ min Fl (mod 2), and max Fu ≡ max Fk ≡ max Fl (mod 2). Notice that 2zl + zk + zu and 2zl + zk + zu + x0 are both entries r of x, and so 2zl + zk + zu ∈ Bj and 2zl + zk + zu + x0 ∈ Bj . A Now ?(2zl + zk + zu ) = ?(zl ) + ?(zk ) + ?(zu ) + 1. (Exactly one odd block of 0’s is added in addition to those interior to the expansions of 2zl , zk , and zu . It is between zk and zu if max Fu ≡ min Fu (mod 2), and it is between 2zl and zk if max Fu ≡ min Fu (mod 2).) Consequently, ?(2zl + zk + zu ) ≡ 1 (mod 3), and thus j = 1, and so ?(x0 ) ≡ 1 (mod 3). Now ?(2zl + zk + zu + x0 ) = ?(2zl + zk + zu ) + ?(x0 ) + 1 or

1218

NEIL HINDMAN, IMRE LEADER, AND DONA STRAUSS

?(2zl + zk + zu + x0 ) = ?(2zl + zk + zu ) + ?(x0 ), depending on whether or not an odd block of 0’s is introduced between the expansions of zu and x0 . Consequently, ?(2zl + zk + zu + x0 ) ≡ 0 (mod 3) or ?(2zl + zk + zu + x0 ) ≡ 2 (mod 3). In either case, we have a contradiction. Theorem 2.2. Let b be a compressed sequence with entries from N such that b = (1). Let A be a matrix whose rows are all rows a ∈ Qω with only ?nitely many nonzero entries such that c(a) = b. Let B be the ?nite sums matrix. (a) The matrices A and B are image partition regular. (b) There is a subset C of N that is a member of every idempotent in β N (and is thus, in particular, central) such that for no x ∈ Nω does one have Ax ∈ C ω . A O ) is not image partition regular. (c) The matrix ( O B Proof. Note that B is a matrix whose rows are all rows a ∈ Qω with only ?nitely many nonzero entries such that c(a) = (1). That A and B are image partition regular follows from [2, Theorem 2.5]. By [2, Theorem 3.14], there exist C1 and C2 such that N = C1 ∪ C2 and there ω ω and there does not exist y ∈ Nω with By ∈ C2 , does not exist x ∈ Nω with Ax ∈ C1 A O and thus ( O B ) is not image partition regular. By [7, Theorem 5.8], C2 is not a member of any idempotent in β N, and thus C1 is a member of every idempotent in β N. By way of contrast with Theorem 2.2(c), we see that in?nite image partition regular matrices can be extended by ?nite ones. (We are grateful to V. R¨ odl for providing us with this result and its proof.) Lemma 2.3. Let A and B be ?nite and in?nite image partition regular matrices A O ) is image partition regular. respectively (with rational coe?cients). Then ( O B Proof. Assume that A is a u × v matrix. Let r ∈ N and let N be r-colored by ?. Let (by compactness) n be large enough so that whenever {1, 2, . . . , n} is r-colored, there exists x ∈ Nv such that the entries of Ax are monochrome. Now color N with rn colors via ψ , where ψ (x) = ψ (y ) if and only if for all t ∈ {1, 2, . . . , n}, ?(tx) = ?(ty ). Pick y ∈ Nω such that the entries of By are monochrome with respect to ψ . Pick an entry a of By and de?ne γ : {1, 2, . . . , n} → {1, 2, . . . , r} by γ (i) = ?(ia). Pick x ∈ Nv such that the entries of Ax are monochrome with respect to γ . Pick an entry i of Ax and let j = γ (i). ax A O ), ?(w · z ) = j . To see Let z = . We claim that for any row w of ( O B iy this, ?rst assume that w is a row of A O , so that w = s 0, where s is a row of A. Then w · z = a(s · x) and j = γ (s · x) = ? a(s · x) = ?(w · z ). Next assume that w is a row of O B , so that w = 0 s, where s is a row of B . Then w · z = i(s · y ). Now ψ (s · y) = ψ (a), and so ? i(s · y ) = ?(ia) = γ (i) = j. De?nition 2.4. Let A be a ?nite or in?nite matrix with entries from Q. Then C (A) = {p ∈ β N : for every P ∈ p, there exists x with entries from N such that all the entries of Ax are in P }. Lemma 2.5. Let A be a matrix with entries from Q. (a) The set C (A) is compact, and C (A) = ? if and only if A is image partition regular.

PARTITION REGULAR MATRICES: SOLUTIONS IN CENTRAL SETS

1219

(b) If A is a ?nite image partition regular matrix, then C (A) is a subsemigroup of β N. Proof. (a) The fact that C (A) is compact is trivial, as is the fact that A is image partition regular if C (A) = ?. Assume that A is image partition regular and let C = {B ? N : for every x with entries from N and the same number of entries as A has columns, some entry of Ax is in B } . We claim that C has the ?nite intersection property. To see this, suppose instead that we have n ∈ N and B1 , B2 , . . . , Bn ∈ C with n i=1 Bi = ?. Then ( N \ B ), and so there are some i ∈ { 1 , 2 , . . . , n } and some x with all N = n i i=1 entries of Ax in N\Bi , contradicting the fact that Bi ∈ C . Since C has the ?nite intersection property, pick p ∈ β N with C ? p. To see that p ∈ C (A), let P ∈ p. If there were no x with entries from N such that all entries of Ax are in P , we would have N\P ∈ C ? p, a contradiction. (b) Let u, v ∈ N be such that A is a u × v matrix. We have C (A) = ? by (a). Let p, q ∈ C (A) and let B ∈ p + q . Then C = {y ∈ N : ?y + B ∈ q } ∈ p; so pick u x ∈ Nv such that y = Ax ∈ C u . Then D = i=1 (?yi + B ) ∈ q ; so pick z ∈ Nv such u u that Az ∈ D . Then A(x + z ) ∈ B . The set C (A) need not be a semigroup if A is an in?nite image partition regular matrix, as can be seen from Theorem 2.2, wherein the matrix A is image partition regular, but C (A) contains no idempotents. Corollary 2.6. Let F denote the set of ?nite image partition regular matrices over Q. If B is an in?nite partition regular matrix, then C (B ) ∩ A∈F C (A) = ?. Proof. Let A1 , A2 , · · · , An be a ?nite number ? A1 O · · · ? O A2 · · · ? ? . . .. . M =? . . . ? . ? O O ··· O O ··· of elements of F . Let ? O O O O ? ? ? . . . . . . . ? ? ? An O O B

n

By Lemma 2.3, M is image partition regular, and so ? = C (M ) ? C (B ) ∩

i=1

C (Ai ).

Our claim now follows from compactness. We saw in Theorem 2.2(b) that the characterization of Theorem 1.2(b) need not be valid for in?nite image partition regular matrices. This leads us to hope that perhaps matrices with this stronger property are better behaved. De?nition 2.7. Let A be an ω × ω matrix. Then A is centrally image partition regular if and only if whenever C is a central set in N, there exists x ∈ Nω such that Ax ∈ C ω . It is trivial that whenever A and B are centrally image partition regular matrices, A O ). Unfortunately, our other desired characteristic does not hold. then so is ( O B

1220

NEIL HINDMAN, IMRE LEADER, AND DONA STRAUSS

Proposition 2.8. There is an ω × 2 centrally image partition regular matrix A with b entries from Q such that there does not exist b ∈ Q making ?b image partition A x0 2 b x ∈ Nω . regular. In fact, there do not exist b ∈ Q and x = ( x1 ) ∈ N with ?b A Proof. Let ? ? ? ? ? ? ? A=? ? ? ? ? ?

1 2 1 3 1 4 1 5 1 2 2 3 3 4 4 5

? ? ? ? ? ? ? ?. ? ? ? ? ?

. . .

. . .

Given any central set C , pick a ∈ C and let x = ( a a ). Then all entries of Ax are equal to a. 0 2 ?b b x ∈ Nω . Suppose that we have b ∈ Q and x = ( x x1 ) ∈ N with A Since ?b · x0 + b · x1 ∈ N, we have that x0 = x1 . Pick n ∈ N such that |x0 ? x1 | < n. x 0 ?x 1 1 1 1 n?1 · x0 + n? Then n n · x1 ∈ N while n · x0 + n · x1 = x1 + n . But x1 ∈ N and | x 0 ?x 1 | < 1, a contradiction. 0< n We now turn our attention to the characterization of Theorem 1.2(e). Considering the matrix of Proposition 2.8, which could only produce entries in N if the entries of x were equal, it seems reasonable to ask that the entries of x be required to be distinct. However, we see now that this also would do no good. (We also see that requiring the entries of the matrix to come from Z rather than Q is of no use either.) Proposition 2.9. There is an ω × 2 matrix A with entries from Z with the property that whenever C is a central set in N, there exists x0 = x1 such that all entries of 2b ?b 0 image partition A(x x1 ) are in C , but there does not exist b ∈ Q making A regular. Proof. Let ? ?

? ? ? ? A=? ? ? ? 2n + 1 ? . . .

1 3 5 . . .

? ? ? ? ? ? ? ?n ? ? . . .

0 ?1 ?2 . . .

and let {D1 , D2 } be any partition of N such that neither D1 nor D2 contains in?nite arithmetic progressions. To see that A has the ?rst claimed property, let C be a central set and pick x0 ∈ C . Let x1 = 2x0 . Then all entries of Ax are equal to x0 . 2 0 Suppose that we have b ∈ Q, i ∈ {1, 2}, and x = ( x x1 ) ∈ N with 2b ? b A

ω . x ∈ Di

PARTITION REGULAR MATRICES: SOLUTIONS IN CENTRAL SETS

1221

th 1 Then 2bx0 ? bx1 > 0; so 2x0 = x1 . Let a = x entry of Ax is x0 . Then the n x0 + (2 ? a) · x0 · n. This tells us in fact that a < 2, and consequently Di contains an in?nite arithmetic progression, a contradiction.

In view of Proposition 2.9, we turn our attention to the other half of the characterization of Theorem 1.2(e). De?nition 2.10. Let A be an ω × ω matrix. Then A is strongly centrally image partition regular if and only if whenever C is a central set in N, there exists x ∈ Nω such that y = Ax ∈ C ω and for all i, j ∈ ω , if rows i and j of A are unequal, then yi = yj . There is a simple necessary condition for a matrix to be strongly centrally image partition regular. Theorem 2.11. Let A be a strongly centrally image partition regular matrix without repeated rows. Then for each k ∈ N, {i : for all j ≥ k , ai,j = 0} is ?nite. Proof. Suppose instead that {i : for all j ≥ k , ai,j = 0} is in?nite. Then by discarding the other rows we may presume that A is an ω × k matrix. Let D = {x ∈ Nk : all entries of Ax are distinct}. Enumerate D as x(n) ∞ n=1 . Inductively choose distinct yn and zn in Ax(n) , with {yn , zn }∩ ( yt : t ∈ {1, 2, . . . , n ? 1} ∪ zt : t ∈ {1, 2, . . . , n ? 1} ) = ? if n > 1. Let C = {yn : n ∈ N}. Then there is no x ∈ D with Ax ∈ C ω , and no x ∈ D with Ax ∈ (N\C )ω . We shall see in Theorem 3.9 that there is a strongly centrally image partition br regular matrix A such that there is no b ∈ Q\{0} for which is image A partition regular, where r = 1 0 0 0 . . . . We shall see in Corollary 2.14 that the strongly centrally image partition regular matrices do maintain one of the properties that we desire. First we shall have need of the following algebraic result, which we think is of interest in its own right. (The information about the minimal left and minimal right ideals involved is not needed here. But it is interesting algebraically and costs us little additional e?ort.) Notice that since, by [7, Theorem 2.7] R ∩ L is a group, p is the unique idempotent of R ∩ L. Theorem 2.12. Let p be a minimal idempotent in (β N, +) and let L and R be respectively the minimal left and minimal right ideals of (β N, +) with p ∈ L ∩ R. Then for each C ∈ p, there are 2c minimal idempotents in L ∩ C and 2c minimal idempotents in R ∩ C . Proof. Let C ∈ p, let C = {x ∈ C : ?x + C ∈ p}, and notice that, by [7, Lemma 4.14], for each x ∈ C we have ?x + C ∈ p. For each m ∈ ω , let Sm = 2 m N ∩ C ∩ ? k + C : k ∈ C ∩ { 1 , 2 , . . . , m} . Let V = m∈N Sm . For every m ∈ N we have 2m N ∈ p (by [7, Lemma 6.6]), and so Sm ∈ p. Thus p ∈ V . We show that V is a subsemigroup of β N, using [7, Theorem 4.20]. So, let m ∈ N and let n ∈ Sm . It su?ces to show that n + Sm+n ? Sm . Let r ∈ Sm+n . Certainly n + r ∈ 2m N. Since n ∈ C ∩{1, 2, . . . , m + n}, n + r ∈ C . Let k ∈ C ∩{1, 2, . . . , m}. Then n ∈ ?k + C ; so k + n ∈ C ∩ {1, 2, . . . , m + n}, and thus r ∈ ?(k + n) + C , so that n + r ∈ ?k + C , as required.

1222

NEIL HINDMAN, IMRE LEADER, AND DONA STRAUSS

Since p ∈ V , we have by [7, Theorem 6.32] that V contains a copy of H = N2n . (This copy is guaranteed to be both an algebraic and topological copy, via the same function, but here we only care about the fact that it is an algebraic copy.) By [7, Theorem 6.9], (β N, +) has 2c minimal left ideals. So there is a set W ? β N of idempotents such that |W | = 2c and, whenever u and v are distinct members of W , u + v = u and v + u = v . Since by [7, Lemma 6.6], W ? H and V contains a copy of H, we have a set E ? V of idempotents such that |E | = 2c and, whenever u and v are distinct members of E , u + v = u and v + u = v . By [7, Corollary 6.20], if u and v are distinct members of E , then (β N + u) ∩ (β N + v ) = ?; so, in particular, (V + u) ∩ (V + v ) = ?. For each u ∈ E , pick an idempotent αu ∈ (p + V ) ∩ (V + u) with αu minimal in V . (By [7, Corollary 2.6 and Theorem 2.7], p + V contains a minimal right ideal of V and V + u contains a minimal left ideal of V , and the intersection of a minimal right ideal of V with a minimal left ideal of V is a group. Let αu be the identity of this group.) Then {αu : u ∈ E } is a set of 2c idempotents in p + V ? R, each minimal in V . Since p ∈ V ∩ K (β N), we have that K (V ) = V ∩ K (β N) by [7, Theorem 1.65], so that each αu is minimal in β N. Now we verify the assertion about L. For each x ∈ N de?ne supp(x) ∈ Pf (ω ) by x = t∈supp(x) 2t . Inductively choose a sequence rn ∞ n=1 in N such that, for each n ∈ N, rn ∈ Sn and max supp(rn ) < min supp(rn+1 ). Let X = {rn : n ∈ N} and note that X ∩ N? = β N\N ? V . Note also that, since Sn ? N2n , V ? H. De?ne f : N → ω by f (n) = min supp(n), and let f : β N → βω be its continuous extension. Notice that if x ∈ β N and q ∈ H, then f (x + q ) = f (x). (To see this it su?ces to show that the continuous functions f ? ρq and f agree on N. If n ∈ N and m = f (n) + 1, then f ? λn is constantly equal to f (n) on N2m , and so f (n + q ) = f (n).) For each y ∈ f [X ∩ N? ] we know that {q ∈ V : f (q ) = y } is a right ideal of V . So pick an idempotent δy ∈ {q ∈ V : f (q ) = y } ∩ L that is minimal in V . Each δy is minimal in V , hence in β N, and if y = z , then {q ∈ V : f (q ) = y } ∩ {q ∈ V : f (q ) = z } = ?. It thus su?ces to show that |f [X ∩ N? ]| = 2c . To see this, let v be any nonprincipal ultra?lter on {f (rn ) : n ∈ N} (of which there are 2c ). For A ∈ v , let B (A) = {rn : f (rn ) ∈ A}. Then {B (A) : A ∈ v } has the ?nite intersection property; so pick q ∈ β N with {B (A) : A ∈ v } ? q . Since A∈v B (A) = ?, q ∈ N? . Also, f (q ) = v .

∞ n=1

Corollary 2.13. Let C be a central set in N. Then there exists a sequence Cn ∞ of pairwise disjoint central sets in N with n=1 Cn ? C .

∞ n=1

Proof. By Theorem 2.12, the set of minimal idempotents in C is in?nite, hence contains an in?nite strongly discrete subset. (Alternatively, there are two minimal idempotents in C , so that C can be split into two central sets, C1 and D1 . Then D1 can be split into two central sets, C2 and D2 , and so on.)

PARTITION REGULAR MATRICES: SOLUTIONS IN CENTRAL SETS

1223

Corollary 2.14. For each n ∈ N, let regular matrix. Then the matrix ? A1 ? O ? M =? O ? . . .

An be a strongly centrally image partition O A2 O . . . O O A3 . . . ... ... ... .. . ? ? ? ? ?

is also strongly centrally image partition regular. Proof. Let C be a central set and choose by Corollary 2.13 a sequence Cn ∞ n=1 ∞ of pairwise disjoint central sets in N with n=1 Cn ? C . For each n ∈ N choose ω and, if rows i and j of An are unequal, x(n) ∈ Nω such that y (n) = An x(n) ∈ Cn (n) (n) yi = yj . Let ? (1) ? x ? x(2) ? z=? ?. . . . Then all entries of M z are in C , and entries from distinct rows are unequal. Of course Corollary 2.14 remains valid if “strongly centrally image partition regular” is replaced by “centrally image partition regular”. The same proof applies, and one does not need to introduce the pairwise disjoint central sets, which were required to guarantee that the entries of M z from distinct rows were distinct. 3. Constant row sums Notice that trivially, if A is an ω × ω matrix with entries from Q and there is some positive m ∈ Q such that each row of A sums to m, then A is centrally image partition regular. (Given a central set C , simply pick d ∈ N such that dm ∈ C , which one can do because for each n ∈ N, Nn is a member of every idempotent by [7, Lemma 6.6]. Then let xi = d for each i ∈ ω .) We also saw in Theorem 2.2(b) that if b is a compressed sequence with entries from ω such that b = (1) and A is a matrix whose rows are all rows a ∈ Qω with only ?nitely many nonzero entries such that c(a) = b, then A is not centrally image partition regular. We shall show in this section (in Theorem 3.7) that if A is a matrix with entries from Z with ?nitely many nonzero entries in each row such that the compressed forms of all rows of A are the same and all rows of A have the same nonzero sum, then A is strongly centrally image partition regular. We shall also show (in Corollary 3.15) that a matrix with the same compressed form for all rows and zero sum for each row need not be centrally image partition regular. We show now that any matrix with constant positive row sums and a limited number of patterns in any ?nite set of columns can be extended at will. That the restriction on the number of patterns in a ?nite set of columns is needed can be seen by considering the matrix of Proposition 2.8. We shall see in Theorem 3.9 that we cannot extend the following theorem to the case in which m ∈ Z. In Theorem 3.1 we talk of adding ?nitely many rows, rather than adding rows one at a time as in Theorem 1.2(d), because we cannot simply iterate the procedure. (If the row sums of A are all m and the sum of row r is not 0, one can multiply r by b so that its sum is m and iterate. However, in the interesting cases, some or all of the added rows will sum to 0.)

1224

NEIL HINDMAN, IMRE LEADER, AND DONA STRAUSS

Theorem 3.1. Let k ∈ N, let m ∈ Q with m > 0, and let A be an ω × ω matrix with entries from Q such that (i) the sum of each row of A is m, and (ii) for each l ∈ ω , { ai,0 , ai,1 , . . . , ai,l : i ∈ ω } is ?nite. Let r (1) , r (2) , . . . , r (k) ∈ Qω \{0} such that each r (i) has only ?nitely many nonzero entries. Then there exist b1 , b2 , . . . , bk ∈ Q\{0} such that ? ? b1 r (1) ? b2 r (2) ? ? ? ? ? . . ? ? . ? ? ? b k r (k ) ? A is centrally image partition regular. Proof. Pick l ∈ N such that for every j ∈ {1, 2, . . . , k } and every i ≥ l we have (j ) (j ) (j ) (j ) ri = 0. For each j ∈ {1, 2, . . . , k }, let s(j ) = r0 , r1 , . . . , rl . Enumerate { ai,0 , ai,1 , . . . , ai,l?1 : i ∈ ω } as w(0) , w(1) , . . . , w(u) . For each i ∈ {0, 1, . . . , u}, let di = m ? the (u + 1) × (l + 1) matrix with entries ei,j = wj di

(i) l? 1 j =0 (i)

wj . Let E be

if j ∈ {0, 1, . . . , l ? 1}, if j = l .

Then E has constant row sums, so is image partition regular. By applying Theorem 1.2(d) u + 1 times, pick b1 , b2 , . . . , bk ∈ Q\{0} such that the matrix ? ? b1 s (1) ? b2 s (2) ? ? ? ? ? . . H=? ? . ? ? ? b k s (k ) ? E is image partition regular, hence, by Theorem 1.2(b), centrally image partition regular. Let C be a central set and pick z0 , z1 , . . . , zl ∈ Nl+1 such that Hz ∈ C u+1 . For n ∈ {0, 1, . . . , l ? 1}, let xn = zn . For n ∈ {l, l + 1, l + 2, . . .}, let xn = zl . Then ? ? ? ? ? ? ? b k r (k ) A b1 r (1) b2 r (2) . . . ? ? ? ? ? x ∈ Cω. ? ?

We see now that matrices with constant positive row sums need not be strongly centrally image partition regular. Proposition 3.2. Let A be an ω × ω matrix whose rows are all those rows with entries from {0, 1, 2} with exactly one 1 and exactly one 2 (and no repeated rows).

PARTITION REGULAR MATRICES: SOLUTIONS IN CENTRAL SETS

1225

While A is centrally image partition regular, it is not strongly centrally image partition regular. In fact, there is a two-cell partition {D0 , D1 } of N such that there ω and all entries of y distinct. do not exist t ∈ {0, 1} and x ∈ Nω with y = Ax ∈ Dt

t Proof. For x ∈ N, let f (x) = max supp(x), where x = t∈supp(x) 2 . (Then f (x ) f (x)+1 ≤x<2 .) For t ∈ {0, 1}, let Dt = {x ∈ N : f (x) ≡ t (mod 2)}. Suppose 2 ω and all entries of y distinct. that we have t ∈ {0, 1} and x ∈ Nω with y = Ax ∈ Dt Then also all entries of x are distinct. (If i = j , then 2xi + xj and xi + 2xj are distinct entries of y .) Pick k < l < m in ω such that f (xk ) + 3 < f (xl ) < f (xm ). If we had i < j in {k, l, m} such that xj < 2f (xj )+1 ? 2xi , then we would have f (xj + 2xi ) = f (xj ) while f (2xj + xi ) = f (xj ) + 1, a contradiction. Thus for i < j in {k, l, m} we have xj ≥ 2f (xj )+1 ? 2xi and f (xj + 2xi ) = f (xj ) + 1. In particular,

(?) and (??)

xl ≥ 2f (xl )+1 ? 2xk xm ≥ 2f (xm )+1 ? 2xk .

If we had 2xm ≥ 2f (xm )+2 ? xl , then we would have f (2xm + xl ) = f (xm ) + 2 ≡ f (xm + 2xl ) (mod 2), again a contradiction. Thus, using (?) and (??), we have 2f (xm )+2 ? 4xk ≤ 2xm < 2f (xm )+2 ? xl ≤ 2f (xm )+2 ? 2f (xl )+1 + 2xk , so that xl < 2f (xl )+1 < 6xk < 8xk < 2f (xk )+4 ≤ 2f (xl ) ≤ xl , a contradiction. Notice that any ?nite set of rows of the matrix A in Proposition 3.2 forms a ?nite image partition regular matrix (after throwing away columns with all zeroes). Thus by Theorem 1.2(e), given any central set C and any n ∈ N, there must exist x ∈ Nω such that the ?rst n entries of Ax are distinct and lie in C . It is a consequence of Theorem 3.7 below that if the matrix A de?ned in Proposition 3.2 is modi?ed by requiring that the occurrence of 1 comes before the occurrence of 2 on each row (or vice versa), then the resulting matrix is strongly centrally image partition regular. The proof of Theorem 3.7 uses a quite general construction, which we present now. Recall that if D is a discrete space, p ∈ βD, X is a topological space, y ∈ X , and f : D → X , then p- lim f (s) = y if and only if for every neighborhood U of y in X , {s ∈ D : f (s) ∈ U } ∈ p. See [7, Section 3.5] for a presentation of the basic properties of these limits. Given a sequence xk ∞ k=0 in a semigroup (S, ·), we write F P ( xk

∞ k=0 ) s∈D

={

k ∈F

xk : F ∈ Pf (ω )}

for the set of ?nite products of terms of the sequence. If the operation is denoted by +, then we write F S ( xk ∞ k=0 ) = { k∈F xk : F ∈ Pf (ω )}. Theorem 3.3. Let S and T be discrete spaces, let n ∈ N, and let f : S n → T . De?ne g : βS → βT by g (p) = p- lim p- lim . . . p- lim f (s1 , s2 , . . . , sn ) .

s1 ∈S s2 ∈S k sn ∈S

Let p ∈ S = βS \S , let h :

?

∞ k=1

S → p, let Q ∈ g (p), and let A ∈ p.

1226

NEIL HINDMAN, IMRE LEADER, AND DONA STRAUSS

(1) There exists a sequence xk ∞ k=0 in A such that whenever r1 < r2 < . . . < rn we have f (xr1 , xr2 , . . . , xrn ) ∈ Q, and for each k ∈ N, xk ∈ h(x0 , x1 , . . . , xk?1 ). (2) If (S, ·) is a semigroup and p is an idempotent, then the sequence xk ∞ k=0 can be chosen so that, in addition to the above conclusions, F P ( xk ∞ k=0 ) ? A and whenever F1 , F2 , . . . , Fn are ?nite nonempty subsets of ω with max Fk < min Fk+1 for every k ∈ {1, 2, . . . , n ? 1}, one has f (Πt∈F1 xt , Πt∈F2 xt , . . . , Πt∈Fn xt ) ∈ Q. Proof. Let P = {z ∈ A : p- lims2 ∈S p- lims3 ∈S . . . p- limsn ∈S f (z, s2 , s3 , . . . , sn ) ∈ Q}. Note that P ∈ p. For k ∈ {1, 2, . . . , n ? 2} and y1 , y2 , . . . , yk ∈ S , let Py1 ,y2 ,...,yk = {z ∈ S : p- limsk+2 ∈S p- limsk+3 ∈S . . . p- limsn ∈S f (y1 , y2 , . . . , yk , z, sk+2 , . . . , sn ) ∈ Q} and for y1 , y2 , . . . , yn?1 ∈ S , let Py1 ,y2 ,...,yn?1 = {z ∈ S : f (y1 , y2 , . . . , yn?1 , z ) ∈ Q}. Notice that, if y ∈ P , then Py ∈ p and, if k ∈ {1, 2, . . . , n ? 2} and yk+1 ∈ Py1 ,y2 ,...,yk , then Py1 ,y2 ,...,yk+1 ∈ p. To establish the conclusions in (1), pick x0 ∈ P , let m ∈ ω , and assume that we have chosen x0 , x1 , . . . , xm ∈ P such that (i) for each k ∈ {1, 2, . . . , m}, xk ∈ h(x1 , x2 , . . . , xk?1 ), and (ii) for each k ∈ {1, 2, . . . , m}, if k ≤ n and 0 ≤ r1 < r2 < . . . < rk ≤ m, then xrk ∈ Pxr1 ,xr2 ,...,xrk?1 . For k ∈ {1, 2, . . . , n ? 1}, let Vk = {(xr1 , xr2 , . . . , xrk ) : 0 ≤ r1 < r2 < . . . < rk ≤ m} . Choose xm+1 ∈ P ∩ h(x0 , x1 , . . . , xm ) ∩

min{n?1,m+1} k=1 (y1 ,y2 ,...,yk )∈Vk

Py1 ,y2 ,...,yk .

The induction hypotheses guarantee that the set on the right is a member of p, and is therefore nonempty. Now, to verify the conclusions in (2), assume that (S, ·) is a semigroup and p = p · p. For any B ∈ p, let B = {x ∈ B : x?1 B ∈ p}, where x?1 B = {y ∈ S : x · y ∈ B }. Then B ∈ p and, by [7, Lemma 4.14], whenever x ∈ B , one has x?1 B ∈ p. Choose x0 ∈ P . Let m ∈ N, and assume that we have chosen x0 , x1 , . . . , xm such that (i) for each k ∈ {1, 2, . . . , m}, xk ∈ h(x1 , x2 , . . . , xk?1 ), (ii) if ? = F ? {0, 1, . . . , m}, then t∈F xt ∈ P , and (iii) if k ∈ {2, 3, . . . , n} and F1 , F2 , . . . , Fk ∈ Pf ({1, 2, . . . , m}) with max Fj < min Fj +1 for each j ∈ {1, 2, . . . , k ? 1}, then

t∈Fk

xt ∈ (PΠt∈F1 xt ,Πt∈F2 xt ,...,Πt∈Fk?1 xt ) .

For r ∈ {0, 1, . . . , m}, let Er = t∈F xt : ? = F ? {r, r + 1, . . . , m} , and for k ∈ {1, 2, . . . , n ? 1} and r ∈ {0, 1, . . . , m}, let Wk,r = ( t∈F1 xt , t∈F2 xt , . . . , t∈Fk xt ) : F1 , F2 , . . . , Fk ∈ Pf ({0, 1, . . . , r}) and max Fj < min Fj +1 for every j ∈ {1, 2, . . . , k ? 1} .

Note that Wk,r = ? if and only if k ≤ m + 1. Hypothesis (ii) tells us that if y ∈ E0 (equivalently if (y ) ∈ W1,m ), then y ∈ P , so that y ?1 P ∈ p and Py ∈ p. Hypothesis (iii) tells us that whenever k ∈ {2, 3, . . . , n ? 1} and (y1 , y2 , . . . , yk ) ∈ Wk,m , one has yk ∈ Py1 ,y2 ,...,yk?1 , so that Py1 ,y2 ,...,yk ∈ p.

PARTITION REGULAR MATRICES: SOLUTIONS IN CENTRAL SETS

1227

Hypothesis (iii) also tells us that if r ∈ {0, 1, . . . , m ? 1}, k ∈ {1, 2, . . . , n ? 1}, (y1 , y2 , . . . , yk ) ∈ Wk,r , and z ∈ Er+1 , then z ∈ (Py1 ,y2 ,...,yk ) , and thus z ?1 (Py1 ,y2 ,...,yk ) ∈ p . Thus we may choose xm+1 ∈ h(x0 , x1 , . . . , xm ) ∩ P ∩ y∈E0 y ?1 P min{m+1,n?1} ∩ k=1 (y1 ,y2 ,...,yk )∈Wk,m (Py1 ,y2 ,...,yk ) ∩

m? 1 r =0 min{r +1,n?1} k=1 (y1 ,y2 ,...,yk )∈Wk,r z ∈Er+1

z ?1 (Py1 ,y2 ,...,yk ) ,

because this set is a member of p and is therefore nonempty. Hypothesis (i) holds directly. To verify hypothesis (ii), let ? = F ? {1, 2, . . . , m + 1} with m + 1 ∈ F . If F = {m + 1}, then t∈F xt = xm+1 ∈ P . Otherwise, let G = F \{m + 1} and let y = t∈G xt . Then y ∈ E0 , and so xm+1 ∈ y ?1 P , and thus t∈F xt ∈ P . To verify hypothesis (iii), let k ∈ {2, 3, . . . , n} and let F1 , F2 , . . . , Fk ∈ Pf ({1, 2, . . . , m + 1}) with max Fj < min Fj +1 for each j ∈ {1, 2, . . . , k ? 1} and with m + 1 ∈ Fk . If Fk = {m + 1}, then we have

t∈Fk

xt = xm+1 ∈ (PΠt∈F1 xt ,Πt∈F2 xt ,...,Πt∈Fk?1 xt ) .

So assume that Fk = {m + 1}, let G = F \{m + 1}, and let r = min G ? 1. Let z = Πt∈G xt , and for j ∈ {1, 2, . . . , k ? 1} let yj = t∈Fj xt . Then (y1 , y2 , . . . , yk?1 ) ∈ Wk?1,r and z ∈ Er+1 , so that t∈Fk xt = z · xm+1 ∈ (Py1 ,y2 ,...,yk?1 ) , as required. As we have previously remarked, in [2, Theorem 2.5] it was shown that if A is an ω × ω matrix with entries from ω (and only ?nitely many nonzero entries on each row) such that the compressed forms of all rows were equal, then A is image partition regular. We extend this result now to allow negative entries. Notice that in the following lemma and beyond, if p ∈ β N and a ∈ Z, then the product a · p refers to multiplication in the semigroup (β Z, ·). In particular, if a ∈ N, a · p is not the sum of p with itself a times. (If, as here, p = p + p, that sum is just p.) In our remaining results we shall be assuming that the entries of our matrices come from Z rather than Q. This is a convenient, but not essential, restriction because we shall also be assuming that the compressed forms of all rows are equal, so that any such matrix with rational entries can be turned into one with integer entries by multiplying by a constant. Since multiplying a central set by a constant produces another central set [6, Lemma 2.1], the corresponding results hold. Lemma 3.4. Let a1 , a2 , . . . , ak be a sequence in Z\{0}. Let m = max |aj | : j ∈ {1, 2, . . . , k } , let p be an idempotent in β N, and let q = a1 · p + a2 · p + . . . + ak · p ∈ β Z. If A ∈ q and P ∈ p, then there is a sequence xn ∞ n=0 in N such that n k ∞ xn+1 > 2m · t=0 xt for each n ∈ ω , F S ( xn n=0 ) ? P and n∈Ft xn : t=1 at · F1 , F2 , . . . , Fk ∈ Pf (N) and max Ft < min Ft+1 for t ∈ {1, 2, . . . , k ? 1} ? A. Proof. De?ne h : n=1 Nn → p and f : Nk → Z by h(x0 , x1 , . . . , xn?1 ) = {z ∈ N : n?1 z > 2m · t=1 xt } and f (y1 , y2 , . . . , yk ) = a1 · y1 + a2 · y2 + . . . + ak · yk . Then p- lim p- lim . . . p- lim f (y1 , y2 , . . . , yk ) = a1 · p + a2 · p + . . . + ak · p.

y 1 ∈N y 2 ∈N y k ∈N ∞

So Theorem 3.3 applied to the semigroup (N, +) yields the desired conclusion.

1228

NEIL HINDMAN, IMRE LEADER, AND DONA STRAUSS

We observe now that the sequence produced in Lemma 3.4 satis?es a strong uniqueness of sums property. Lemma 3.5. Let a1 , a2 , . . . , ak be a compressed sequence in Z\{0}, let m = max |aj | : j ∈ {1, 2, . . . , k } , and let xn ∞ n=0 be a sequence in N such that xn+1 > n 2m · t=0 xt for each n ∈ ω . Then whenever F1 , F2 , . . . , Fk , G1 , G2 , . . . , Gk ∈ Pf (N), max Ft < min Ft+1 and max Gt < min Gt+1 for t ∈ {1, 2, . . . , k ? 1}, and k k n∈Ft xn = n∈Gt xn , one must have Ft = Gt for each t ∈ {1, 2, t=1 at · t=1 at · . . . , k }. Proof. Suppose instead that we have some F1 , F2 , . . . , Fk , G1 , G2 , . . . , Gk ∈ Pf (N) such that max Ft < min Ft+1 and max Gt < min Gt+1 for t ∈ {1, 2, . . . , k ? 1}, k k n∈Ft xn = n∈Gt xn , but Ft = Gt for some t ∈ {1, 2, . . . , k }. t=1 at · t=1 at · l Pick the largest l ∈ {1, 2, . . . , k } such that Fl = Gl . Then t=1 at · n∈Ft xn = l n∈Gt xn . Let r = max(Fl ?Gl ). By subtracting any larger terms from t=1 at · both sides of the last equation, we may presume that r = max(Fl ∪ Gl ). Assume without loss of generality that r ∈ Fl . We may also assume that al > 0. (Otherwise, multiply both sides by ?1.) Then

l r ?1

at ·

t=1 n∈Ft

xn ≥ ar xr ?

n=1 r ?1

mxn

>

n=1 l

mxn at ·

t=1 n∈Gt

≥ a contradiction.

xn ,

Corollary 3.6. Let a1 , a2 , . . . , ak be a compressed sequence in Z\{0} with ak > 0. Let M be a matrix, with ?nitely many nonzero entries in each row, such that the compressed form of each row is a1 , a2 , . . . , ak . Then M is image partition regular. Indeed, given any idempotent p ∈ β N and any function h : t∈N Nt → p, ∞ if q = a1 · p + a2 · p + . . . + ak · p, then q ∈ n=1 nN, and, for any A ∈ q and any ω P ∈ p, there is an increasing sequence x ∈ N such that F S ( xn ∞ n=0 ) ? P , xn+1 ∈ h(xi1 , xi2 , · · · , xim ) for every n ∈ N and every choice of 0 ≤ i1 < i2 . . . < im ≤ n, M x ∈ Aω , and entries corresponding to distinct rows are distinct. Proof. Let p be an idempotent in β N and let q = a1 · p + a2 · p + . . . + ak · p. Let ∞ T = ∞ n=1 nZ. We show ?rst that q ∈ T ∩ β N = n=1 nN. By [7, Lemma 6.6], p ∈ T . Since, by [7, Theorems 2.15 and 2.17], T is an ideal of (β Z, ·), we have that each ai · p ∈ T . By [7, Exercise 2.3.2] T is a subsemigroup of (β Z, +), and so q ∈ T . Since ak > 0 we have that ak · p ∈ N? , and so q ∈ β N by [7, Exercise 4.3.5]. Let A ∈ q and P ∈ p, and choose a sequence xn ∞ n=0 as guaranteed by Lemma , then all the entries of M x are in A. By Lemma 3.4 for A and P . If x = xn ∞ n=0 3.5, entries that correspond to distinct rows are distinct. Notice that if x is as guaranteed by Corollary 3.6 and z is a subsequence of x, then also M z ∈ Aω , and entries that correspond to distinct rows are distinct, because any entry of M z is also an entry of M x.

PARTITION REGULAR MATRICES: SOLUTIONS IN CENTRAL SETS

1229

We remark that the possibility of choosing xn+1 ∈ h(xi1 , xi2 , · · · , xim ), guaranteed by Corollary 3.6, yields nontrivial information about simple ?nite matri2 ces. For example, let A = ( 1 0 1 ). Then A is image partition regular. Color N according to the parity of max supp(n) . (Recall that supp(n) ∈ Pf (ω ) is dei 2 ?ned for n ∈ N by n = i∈supp(n) 2 .) We cannot choose x ∈ N such that min supp(x2 ) > max supp(x1 ) and the entries of Ax are monochrome. However, 12 if B = ( 1 0 1 2 ), then, de?ning h(x) = {y ∈ N : min supp(y ) > max supp(x) and h(x, y ) = {z ∈ N : min supp(z ) > max supp(y ) , Corollary 3.6 guarantees that, in any ?nite coloring of N, there exists x ∈ N3 such that min supp(xi+1 ) > max supp(xi ) if i ∈ {1, 2} and the entries of Bx are monochrome. Theorem 3.7. Let k ∈ N, let a1 , a2 , . . . , ak be a compressed sequence in Z\{0} with ak > 0, and let m ∈ Z\{0}. Let M be a matrix, with ?nitely many nonzero entries in each row, such that (i) the compressed form of each row is a1 , a2 , . . . , ak , and (ii) the sum of each row is m. Then M is strongly centrally image partition regular. Proof. Let L = {q ∈ β N : for every A ∈ q and every k ∈ N , there exists x ∈ {k + 1, k + 2, k + 3, . . .}ω such that M x ∈ Aω and entries corresponding to distinct rows of M are distinct} . It is obvious that L is closed. By Corollary 3.6, L ∩ |m| · β N = ?. We claim that L ∩|m|· β N is a left ideal of |m|· β N. To this end, let q ∈ L ∩|m|· β N. It su?ces to show that |m| · N + q ? L ∩ |m| · β N. We have immediately that |m|· N + q ? |m|· β N. To see that |m|· N + q ? L, let n ∈ N, let A ∈ |m|· n + q , and let k ∈ N. Pick x ∈ {k +n+1, k +n+2, k +n+3, . . .}ω such that y = M x ∈ (?|m|·n+A)ω m| and the entries of y corresponding to distinct rows are distinct. Let s = |m and for each i ∈ ω let zi = sn + xi . Then each zi > k . Let w = M z . Then for each j ∈ ω we have that wj = |m| · n + yj ∈ A, and entries of w corresponding to distinct rows of M are distinct. Let C be a central set in N, and pick a minimal idempotent r in β N such that 1 · r (multiplication in β Qd , where Qd is the set Q with the C ∈ r. Let p = a k discrete topology). It is routine to check that p ∈ β N, p + p = p, and ak · p = r. Let q = a1 · p + a2 · p + . . . + ak · p. By Corollary 3.6, q ∈ L ∩ |m| · β N. Since ak · p = r, it follows that q ∈ β Z + r = β Z + r + r ? β N + r (the last inclusion by [7, Exercise 4.3.5]). Since q ∈ |m| · β N and r ∈ |m| · β N, we have that q ∈ |m| · β N + r. Now r ∈ |m| · β N ∩ K (β N); so by [7, Theorem 1.65], r ∈ K (|m| · β N). Thus, by [7, Theorem 2.9], |m| · β N + r is a minimal left ideal of |m| · β N. Since q ∈ (L ∩ |m| · β N) ∩ (|m| · β N + r), we have |m| · β N + r ? L, and so r = r + r ∈ |m| · β N + r ? L. Observe that, if all terms of a come from N, then the number of entries of any row of a matrix M as in Theorem 3.7 is limited. However, this need not be the case if one or more entries are negative. We shall see in Theorem 3.14 that the requirement that m = 0 cannot be eliminated. (We saw in Theorem 2.2(b) that the restriction on the row sums cannot simply be omitted.)

1230

NEIL HINDMAN, IMRE LEADER, AND DONA STRAUSS

Consider the following consequence of Theorem 3.7. Let ? ? ?2 1 0 . . . ? ?2 0 1 . . . ? ? ? M = ? 0 ?2 1 . . . ? , ? ? . . . .. . . . . . . . a matrix whose rows have somewhere a single ?2 followed somewhere by a single 1. Even though matrices with constant positive row sums are trivially centrally image partition regular via a constant vector x, it does not seem to be trivial that the matrix M is even centrally image partition regular, while Theorem 3.7 tells us that it is in fact strongly centrally image partition regular. As we promised earlier, we obtain, as a consequence of our consideration of strongly centrally image partition regular matrices, new results about ordinary image partition regular matrices. (The last result mentioned in the abstract is the instance of Corollary 3.8 for which a = 1 , b = 1, 2 , m = 2, and n = 3.) Corollary 3.8. Let k, s ∈ N, let a = a1 , a2 , . . . , ak and b = b1 , b2 , . . . , bs be compressed sequences in Z\{0} with ak > 0 and bs > 0, let m, n ∈ Z\{0}, and assume that there exist r, t ∈ Zω such that c(r ) = a, c(t) = b, ∞ j =0 rj = m, and ∞ q t = n . Let q ∈ N and let N = C . Then there exist i ∈ {1, 2, . . . , q } j i j =0 i=0 ∞ and z in N such that, for every r and g in and injective sequences xn ∞ n n=0 n=0 ∞ ω Z with only ?nitely many nonzero entries, if c(r ) = a, c(g ) = b, j =0 rj = m, ∞ ∞ ∞ ∞ and j =0 gj = n, then j =0 rj · xj ∈ Ci , j =0 gj · zj ∈ Ci , and j =0 rj · xj = ∞ j =0 gj · zj . Proof. Let M and N be matrices with ?nitely many nonzero entries in each row such that (a) the compressed form of each row of M is a; (b) the sum of each row of M is m; (c) all rows with compressed form a and sum m occur in M ; (d) the compressed form of each row of N is b; (e) the sum of each row of N is n; and (f) all rows with compressed form b and sum n occur in N . O Then by Theorem 3.7 and Corollary 2.14, the matrix ( M O N ) is strongly centrally image partition regular. So pick i ∈ {1, 2, . . . , q } such that Ci is central, and x O are in Ci and entries pick x and z in Nω such that all entries of ( M O N) z O corresponding to distinct rows of ( M O N ) are distinct. Then one has immediately ∞ ∞ that for any row r of M and any row g of N , u=0 ru · xu = u=0 gu · zu . To see, for example, that x is injective, let j < l in ω and pick t0 , t1 , . . . , tv ∈ Z\{0} such v that c( t0 , t1 , . . . , tv ) = a and u=0 tu = m. De?ne r and g in Zω by rj = gl = t0 , rl+u = gl+u = tu for u ∈ {1, 2, . . . , v } (if any), and all other entries of r and g are ∞ ∞ equal to 0. Then r and g are distinct rows of m. So u=0 ru · xu = u=0 gu · xu , and thus xj = xl . We see now that strongly centrally image partition regular matrices need not have one of our desired properties, namely the analogue of Theorem 1.2(d).

PARTITION REGULAR MATRICES: SOLUTIONS IN CENTRAL SETS

1231

Proposition 3.9. Let r = 1 0 0 0 . . . . There is an ω × ω matrix M with entries from Z such that the compressed form of each row is (?2, 1) and the sum of each row is ?1 (so M is strongly centrally image partition regular), but there is br no b ∈ Q\{0} such that the matrix is image partition regular. M Proof. Let ? ? ? M =? ? ?2 1 ?2 0 0 ?2 . . . . . . ? 0 ... 1 ... ? ? 1 ... ? ? . .. . . .

br is image partition regular for some M b ∈ Q\{0}. This implies that b > 0. Let b = k l , where k, l ∈ N. Let r be a prime number satisfying r > k + 2l. i Each n ∈ N can be expressed uniquely as n = i∈ω ai r , where each i ∈ {0, 1, 2, . . . , r ? 1}. Let suppr (n) = {i ∈ ω : ai = 0} and m(n) = min suppr (n) . We de?ne f : N → {1, 2, . . . , r ? 1} by f (n) = am(n) . br x ∈ C ω , where Choose x ∈ Nω and c ∈ {1, 2, . . . , r ? 1} such that M C = f ?1 [{c}]. Then bx0 ∈ C and ?2xm + xn ∈ C whenever n, m ∈ ω with m < n. Let d = f (x0 ). We claim that m(xn ) ≤ m(x0 ) for every n ∈ N. To see this, observe that m(xn ) > m(x0 ) implies that f (?2x0 + xn ) = ?2d in Zr . Since f (bx0 ) = k l d in Zr , k it follows that ?2d = l d in Zr and k + 2l = 0 in Zr , a contradiction. Thus, by the pigeonhole principle, there exist s, t ∈ N such that t > s, m(xt ) = m(xs ) and f (xt ) = f (xs ) = e, say. Then f (?2xs + xt ) = ?e = c in Zr . We consider two cases: (i) If m(xs ) = m(2x0 ), then f (?2x0 + xs ) = ?2d + e = c in Zr , and so d = ?c in Zr . We also have k l d = c in Zr , and thus k + l = 0 in Zr , a contradiction. (ii) If m(xs ) < m(2x0 ), then f (?2x0 + xs ) = e. So e = ?e in Zr , again a contradiction. as described above. Suppose that

The fact that the row sums in Proposition 3.9 were negative is needed to prebr vent the image partition regularity of , as we shall see now. We do not M know whether matrices with ?xed compressed form and ?xed positive row sum can necessarily be arbitrarily extended to strongly centrally image partition regular matrices. Corollary 3.10. Let k, l, m ∈ N, let a1 , a2 , . . . , ak be a compressed sequence in Z\{0}, and let A be an ω × ω matrix such that (i) the compressed form of each row is a, and (ii) the sum of each row of A is m.

1232

NEIL HINDMAN, IMRE LEADER, AND DONA STRAUSS

Let r (1) , r (2) , . . . , r (l) ∈ Qω \{0} such that each r (i) has only ?nitely many nonzero entries. Then there exist b1 , b2 , . . . , bk ∈ Q\{0} such that ? ? b1 r (1) ? b2 r (2) ? ? ? ? ? . . ? ? . ? ? ? b k r ( l) ? A is centrally image partition regular. Proof. The matrix A satis?es the hypotheses of Theorem 3.1. We note now that the requirement in Theorem 3.7 that ak > 0 is essential. Theorem 3.11. Let k ∈ N, let a1 , a2 , . . . , ak be a compressed sequence in Z\{0} with ak < 0, and let m ∈ Z be any number expressible in the form k t=1 αt at with each αt ∈ N. Let M be a matrix (with ?nitely many nonzero entries in each row) such that (i) the compressed form of each row is a1 , a2 , . . . , ak , (ii) the sum of each row is m, and (iii) any row with compressed form a1 , a2 , . . . , ak and row sum m occurs in M . Then M is not strongly centrally image partition regular, and if m ≤ 0, M is not centrally image partition regular. Proof. If M x ∈ Nω and either the entries of M x corresponding to distinct rows are distinct or m ≤ 0, there must be in?nitely many distinct entries in x. This in turn forces some entries of M x to be negative. Recall that we have de?ned the (binary) support of a positive integer n by n = t∈supp(n) 2t . We introduce now some special notation needed for the proof of Theorem 3.14. De?nition 3.12. Let n ∈ N. The set H is a block of n if and only if H is a maximal set of consecutive integers contained in supp(n). Also, b(n) is the number of blocks of n. Thus if, written in binary, n = 10011101011, then the blocks of n are {0, 1}, {3}, {5, 6, 7}, and {10}, and so b(n) = 4. Lemma 3.13. Let B = {n ∈ N : b(n) ≡ 0 (mod 2)}. (a) For n ∈ N, let h(n) ∈ {0, 1} be such that h(n) ≡ b(n) (mod 2). Let h : β N → ∞ Z2 be the continuous extension of h. Then the restriction of h to n=1 c (N2n ) is a homomorphism. (b) If q + q = q ∈ β N, then B ∈ q . / ? p + p. (c) If p ∈ β N and for each n ∈ N, N2n ∈ p, then B ∈ Proof. (a) This is an immediate consequence of [7, Theorem 4.21]. ∞ (b) By [7, Lemma 6.6] q ∈ n=1 c (N2n ); so this follows from (a). / supp(x)} and let D1 = {x ∈ N : (c) Let D0 = {x ∈ N : min supp(x) + 1 ∈ min supp(x) + 1 ∈ supp(x)}. Notice that if x, y ∈ D0 and max supp(x) + 1 < min supp(y ) , then b(y ? x) = b(y ) + b(x) ? 1, while if x, y ∈ D1 and max supp(x) + 1 < min supp(y ) , then

PARTITION REGULAR MATRICES: SOLUTIONS IN CENTRAL SETS

1233

b(y ? x) = b(y ) + b(x) + 1. Hence, in either case, if b(x) ≡ b(y ) (mod 2), then y?x∈ / B. Pick t ∈ {0, 1} such that Dt ∈ p. Also pick i ∈ {0, 1} such that C ∈ p, where C = {x ∈ N : b(x) ≡ i (mod 2)}. Now {y ? x : x, y ∈ C ∩ Dt and max supp(x) + 1 < min supp(y ) } ∈ ?p + p by [7, Theorem 4.15]. We have seen that this set does not meet B ; so B ∈ / ? p + p. Theorem 3.14. Let A be an ω × ω matrix with the property that r ∈ Qω occurs as a row of A if and only if the nonzero entries of r are 1, ?1, ?1, 1, in that order. Then there is a subset B of N that is a member of every idempotent in β N and there is no x ∈ Nω for which all the entries of Ax are in B . Proof. Let B = {n ∈ N : b(n) ≡ 0 (mod 2)} and suppose we have x ∈ Nω with Ax ∈ B ω . Note that we cannot have more than three entries of x with the same value, since otherwise 0 would be an entry of Ax. Thus we may pick q ∈ N? ∩ {xn : n ∈ ω }. Since {xn1 ? xn2 ? xn3 + xn4 : n1 < n2 < n3 < n4 } ? B , we have that B ∈ q + ?q + ?q + q . Let p = ?q + q . Then p ∈ β N by [7, Exercise 4.3.5]. Also ?p = q + ?q by [7, Lemma 13.1], so that B ∈ ?p + p. It is easy to check that N2n ∈ p for each n ∈ N by picking i ∈ {0, 1, . . . , 2n ? 1} such that N2n + i ∈ q . Thus we have a contradiction to Lemma 3.13(c). Corollary 3.15. Let M be a matrix (with ?nitely many nonzero entries in each row) such that (i) the compressed form of each row is 1, ?1, 1 , (ii) the sum of each row is 0, and (iii) any row with compressed form 1, ?1, 1 and row sum 0 occurs in M . Then M is not centrally image partition regular. Proof. The matrix M includes all the rows of the matrix A of Theorem 3.14. Let F denote the set of ?nite image partition regular matrices over Q. For F ∈ F , let C (F ) be de?ned as in De?nition 2.4. We know, from Theorem 1.2(b) and Lemma 2.5(b), that F ∈F C (F ) contains the smallest closed subsemigroup of β N containing the minimal idempotents. We now see that F ∈F C (F ) contains elements which do not belong to this semigroup. Corollary 3.16. The set F ∈F C (F ) contains elements which do not belong to the smallest closed subsemigroup of β N containing the idempotents. Proof. Let A be the matrix de?ned in Theorem 3.14. Let B = {n ∈ N : b(n) ≡ 0 (mod 2)}. By Theorem 3.13(a) and the fact from [7, Lemma 6.6] that each ∞ idempotent is in n=1 c β N (N2n ), we have that c β N (B ) contains the smallest closed subsemigroup of β N that contains the idempotents. By Theorem 3.14, C (A)∩ c β N (B ) = ?. However, by Corollary 2.6, C (A) ∩ F ∈F C (F ) = ?. On the other hand, we see that some matrices with all row sums equal to 0 are strongly centrally image partition regular. Theorem 3.17. Let A be an ω × ω matrix whose entries are all in {?1, 0, 1}. Assume that (i) the number of nonzero entries in each row is positive but ?nite, (ii) the last nonzero entry in each row is 1, and

1234

NEIL HINDMAN, IMRE LEADER, AND DONA STRAUSS

(iii) the nonzero entries in each row alternate in sign. Then, A is strongly centrally image partition regular. In fact, if P is a member of any idempotent in β N, then there is an increasing sequence x ∈ Nω such that all the entries of Ax are in P and entries corresponding to distinct rows are distinct.

∞ Proof. We can choose a sequence vn ∞ n=0 such that F S ( vn n=0 ) ? P by [7, Theon rem 5.8]. By taking sums of terms, we may suppose that vn+1 > i=0 vi for every n ∈ ω , and hence that i∈F1 vi = i∈F2 vi if F1 and F2 are distinct members of n Pf (ω ). For every n ∈ ω , let xn = i=0 vi . ω Suppose that r ∈ {?1, 0, 1} \0 has a ?nite number of nonzero entries and that its nonzero entries alternate in sign. Let rn be the last nonzero entry of r . It is easy to see, by induction on the number of nonzero entries in r , that there exists F ∈ Pf (ω ) such that max(F ) = n, and r · x = i∈F vi if rn = 1, while r · x = ? i∈F vi if rn = ?1. It follows that the entries of Ax are in P . It is simple to verify that entries corresponding to distinct rows are distinct.

We do not know whether there is any matrix with all rows having a ?xed compressed form and zero sums which is centrally image partition regular. We see however, that if such exists, it is also strongly centrally image partition regular. Theorem 3.18. Let k ∈ N, let a1 , a2 , . . . , ak be a compressed sequence in Z\{0} k with ak > 0, and assume that 0 is expressible in the form t=1 αt at with each αt ∈ N. Let M be a matrix (with ?nitely many nonzero entries in each row) such that (i) the compressed form of each row is a1 , a2 , . . . , ak , (ii) the sum of each row is 0, and (iii) any row with compressed form a1 , a2 , . . . , ak and row sum 0 occurs in M . If M is centrally image partition regular, then M is strongly centrally image partition regular. Proof. Let C be central in N and pick x ∈ Nω such that M x ∈ C ω . We claim ?rst that no value of x repeats in?nitely often. Suppose instead that we have d s such that |{n ∈ N : xn = d}| = ω . Pick b1 , b2 , . . . , bs such that t=1 bt = 0 and c( b1 , b2 , . . . , bs ) = a. Pick t1 < t2 < . . . < ts such that xt1 = xt2 = . . . = xts = d. Pick a row i of M that has mi,tj = bj for each j ∈ {1, 2, . . . , s} and all other entries ∞ s / C , a contradiction. equal to 0. Then j =0 mi,j xj = j =1 bj d = 0 ∈ Let m = max |aj | : j ∈ {1, 2, . . . , k } . Since no value of x repeats in?nitely often, choose an in?nite B ? ω such that for each n ∈ B with n > min B , xn > 2m · {xt : t ∈ B and t < n} .

Let D be the matrix consisting of those columns of M corresponding to members of B . Then let A be the matrix consisting of those rows of D that sum to 0. Let zn ∞ n=0 enumerate in order {xn : n ∈ B }. Then A has all of the rows of M , y = Az ∈ C ω and, by Lemma 3.5, if i and j are distinct rows of A, then yi = yj . Piecewise syndetic subsets of N are characterized [7, Theorem 4.40] as those sets whose closure meets K (β N). In particular, any central set is piecewise syndetic. Further, piecewise syndetic sets are guaranteed to contain substantial combinatorial structures. For example [7, Theorem 14.1], any piecewise syndetic subset of N contains arbitrarily long arithmetic progressions.

PARTITION REGULAR MATRICES: SOLUTIONS IN CENTRAL SETS

1235

We note that the matrix A in the next theorem need not be centrally image partition regular. Indeed, if each ak ∈ N, k > 1, and every row with compressed form a1 , a2 , . . . , ak occurs in A, then as a consequence of [2, Theorem 3.14], one has that any idempotent p ∈ β N has a member P such that no x ∈ Nω has Ax ∈ P ω . Theorem 3.19. Let k ∈ N and let a1 , a2 , . . . , ak be a compressed sequence in Z\{0} with ak > 0. Let A be an ω × ω matrix with entries in Z, such that each row has a ?nite number of nonzero entries and has a1 , a2 , . . . , ak as its compressed form. If C is a piecewise syndetic subset of N, then there exist c ∈ N and an increasing sequence x ∈ Nω such that all the entries of Ax are in ?c + C and entries corresponding to distinct rows are distinct. Proof. Pick by [7, Theorem 2.8] a minimal left ideal L of β N such that C ∩ L = ?, 1 ·r and pick s ∈ C ∩ L. Pick by [7, Corollary 2.6] an idempotent r ∈ L. Let p = a k and let q = a1 · p + a2 · p + . . . + ak · p. Then, as in the proof of Theorem 3.7, p is an idempotent and q ∈ L. Thus L = l + q by [7, Lemma 1.52]; so s = t + q for some t ∈ L. Since C ∈ s, there is some c ∈ N such that ?c + C ∈ q . The conclusion now follows by Corollary 3.6. References

1. W. Deuber, Partitionen und lineare Gleichungssysteme, Math. Zeit. 133 (1973), 109-123. MR 48:3753 2. W. Deuber, N. Hindman, I. Leader, and H. Lefmann, In?nite partition regular matrices , Combinatorica 15 (1995), 333-355. MR 96i:05173 3. H. Furstenberg, Recurrence in ergodic theory and combinatorial number theory , Princeton University Press, Princeton, 1981. MR 82j:28010 4. R. Graham, B. Rothschild, and J. Spencer, Ramsey Theory, Wiley, New York, 1990. MR 90m:05003 5. N. Hindman and I. Leader, Image partition regularity of matrices, Comb. Prob. and Comp. 2 (1993), 437-463. MR 95j:05167 6. N. Hindman, I. Leader, and D. Strauss, Image partition regular matrices – bounded solutions and preservation of largeness, Discrete Math. 242 (2002), 115-144. MR 2002j:05146 ˇ 7. N. Hindman and D. Strauss, Algebra in the Stone-Cech compacti?cation – theory and applications , W. de Gruyter & Co., Berlin, 1998. MR 99j:54001 8. K. Milliken, Ramsey’s Theorem with sums or unions, J. Combinatorial Theory (Series A) 18 (1975), 276-290. MR 51:10106 9. R. Rado, Studien zur Kombinatorik, Math. Zeit. 36 (1933), 242-280. ¨ 10. I. Schur, Uber die Kongruenz xm + y m = z m (mod p), Jahresbericht der Deutschen Math.Verein. 25 (1916), 114-117. 11. A. Taylor, A canonical partition relation for ?nite subsets of ω , J. Combinatorial Theory (Series A) 21 (1976), 137-146. MR 54:12530 12. B. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wiskunde 19 (1927), 212-216. Department of Mathematics, Howard University, Washington, DC 20059 E-mail address : nhindman@aol.com URL: http://members.aol.com/nhindman/ Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge CB2 1SB, United Kingdom E-mail address : I.Leader@dpmms.cam.ac.uk Department of Pure Mathematics, University of Hull, Hull HU6 7RX, United Kingdom E-mail address : d.strauss@maths.hull.ac.uk

更多相关文档:

are naturally stated *in* terms of image *partition* *regularity* of *matrices*. Many...Key words: Ramsey Theory, Image *partition* *regular* *matrix*, *Central* *Sets* ...

where the *central* node belongs to one *set* and ...11/5/2012 10 Adjacency and Incidence *Matrices* ?...and *in* this case f = 1, the *infinite* face. ...

and ntheta semi-*infinite* constraints (vectors or *matrices*) K1, K2,..., ...*partition* those objectives into the first elements of F and *set* options.Min...

On a Decomposition for *Infinite* Transition *Matrices*...censored Markov chain with censoring *set* f0; 1;...*regular* vector (see 5]) can be computed ...

Noise sequences of *infinite* *matrices* and their applications to the ...N Z The *sets* FD and FD of such functions are convex *in* a natural way...

Miller, Integral equation *solutions* of three...*Matrices* are smaller than *in* FEM or FDTD (only...*infinite* thin metallic layer vias Larissa Vietzor...

Cloud computing platforms provide a near *infinite* ...Fig.5: Data mining *partition* Fig.3: *Matrix* ...The master creates *matrices* A and B and sends ...

更多相关标签:

相关文档

- Maximality of Infinite Partition Regular Matrices
- Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models II. Exten
- Randomized greedy algorithms for independent sets and matchings in regular graphs Exact res
- Transfer Matrices for the Partition Function of the Potts Model on Cyclic and Mobius Lattic
- Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Furth
- Least-Square Solutions for Inverse Problems of Centrosymmetric Matrices
- Central points for sets in R n (or The Chocolate Ice-Cream Problem)
- Transfer matrices and partition-function zeros for antiferromagnetic Potts models
- Ergodic Theory and Visualization I Visualization of Ergodic Partition and Invariant Sets
- Regular Bouncing Cosmological Solutions in Effective Actions in Four Dimensions

文档资料共享网 nexoncn.com
copyright ©right 2010-2020。

文档资料共享网内容来自网络，如有侵犯请联系客服。email:zhit325@126.com