From Schur's Theorem to the Pairwise Sum Theorem

#A105 INTEGERS 25 (2025) FROM SCHUR’S THEOREM TO THE PAIRWISE SUM THEOREM Mauro Di Nasso Dipartimento di Matematica, Universit`a di Pisa, Italy [email protected] Renling Jin Department of Mathematics, College of Charleston, South Carolina [email protected] Received: 9/13/25, Accepted: 11/3/25, Published: 11/25/25 Abstract We show that by only assuming Schur’s Theorem and the existence of a nonprincipal ultrafilter, one can directly prove that in every finite coloring of Nthere exist infinite disjoint sets A, B such that all elements of A∪B∪(A+B) are monochromatic. This gives a partial answer to a question posed by N. Hindman, I. Leader, and D. Strauss in 2003. In the last section we propose a formalization of that open question in purely topological terms. 1. Introduction In their 2003 article [7] entitled “Open problems in partition regularity,” N. Hindman, I. Leader, and D. Strauss compiled a list of 13 open problems considered to be the most relevant in that field at the time. After more than twenty years, questions enumerated there as Questions 5, 6, 7, 8, 9, 10, and 13, have now been solved. Specifically, Questions 5 and 6 have been settled with positive answers in [1] by B. Barber, N. Hindman, and I. Leader, and Questions 7, 8, and 9 have been settled with negative answers in [2] by B. Barber and I. Leader. Besides, I. Leader and P.A. Russell gave a negative answer to Question 10 in the paper [9];1and finally, the conjecture of Question 13 was recently proved to be true by Z. Zelenyk in [10]. Here we focus on Open Question 12 (see below), which is about the strength of a reduced version of Hindman’s Theorem where only pairwise sums from an infinite sequence are considered. DOI: 10.5281/zenodo.17711561 1This paper [9] is actually referenced in the open problems paper [7] as “manuscript”, but before publication the authors found a counterexample and included it in the final version. INTEGERS: 25 (2025) 2 Before proceeding, let us recall some basic terminology. A finite coloring of a set Xis a finite partition X=C1∪. . . ∪Crwhere the pieces Ciare called colors. A set Ais monochromatic with respect to a given finite coloring if all elements of Abelong to the same color, i.e.,A⊆Cifor some i. A family P⊆ P(X) is called weakly partition regular on Xif for every finite coloring of Xthere exists A∈Pwhich is monochromatic. For example, Schur’s Theorem states that the family {{a, b, a +b} | a, b ∈N}is weakly partition regular on N. Let us recall the Finite Sums Theorem, a cornerstone of combinatorics proved by N. Hindman in 1974. Theorem 1.1 (Finite Sums Theorem [6]).For every finite coloring of the natural numbers there exists an infinite set Asuch that its set of finite sums FS(A) := (X a∈F a| ∅ =F⊂Afinite) is monochromatic. Shortly after Hindman’s article was published, Galvin and Glazer found a different proof using “idempotent ultrafilters”; this proof paved the way for an entire field of research based on the algebraic properties of the space of ultrafilters βN(see the comprehensive monograph [8]). The following problem was posed in [7] as Open Question 12, with the comment: “It seems truly remarkable that this can be unknown”. (Q12) Is there a proof that whenever Nis finitely coloured there is a 1-1 sequence x1, x2, . . . such that all xiand all xi+xj(i=j) have the same colour, that does not also prove the Finite Sums Theorem? For convenience, let us give a name to the property considered in the above question. Theorem 1.2 (Pairwise Sum Theorem).For every finite coloring of the natural numbers there exists an infinite Asuch that the set of pairwise sums FS≤2(A) = A∪ {a+a′|a, a′∈A, a =a′} is monochromatic. We will show that by only using Schur’s Theorem and the existence of a nonprincipal ultrafilter on N, one can prove the following weaker version of the Pairwise Sum Theorem, thus providing a partial answer to (Q12). Theorem 2.2.For every finite coloring of the natural numbers there exist infinite disjoint sets A, B such that A∪B∪(A+B)is monochromatic. We observe that (Q12), as formulated in [7], is somewhat vague and ambiguous. In the last section we propose a possible rigorous formalization as a purely topological property of the space βN2. INTEGERS: 25 (2025) 3 2. The Proof Let us first recall a few notions and facts about ultrafilters. The tensor product U ⊗ V between ultrafilters on Nis defined by setting, for every X⊆N×N, X∈ U ⊗ V if and only if {n∈N|Xn∈ V} ∈ U where Xn={m∈N|(n, m)∈X}is the vertical n-fiber of X. The pseudo-sum U ⊕ V is the ultrafilter on Ndefined by setting, for every A⊆N, A∈ U ⊕ V if and only if {n∈N|A−n∈V}∈U where A−n:= {m∈N|m+n∈A}. Observe that U ⊕ V = Sum(U ⊗ V) is the image ultrafilter of the tensor product under the sum function Sum(n, m)=n+m. Recall that if Uis an ultrafilter on a set Iand f:I→J, the image ultrafilter f(U) on Jis defined by setting A∈f(U) if and only if f−1(A)∈ U for all A⊆J.2 In our proof, we will use the following combinatorial property of tensor products. It is a particular case of a general result presented in [3]. However, for completeness, we give here a self-contained proof. Lemma 2.1. For every X⊆N×N, the following conditions are equivalent. 1. There exist disjoint increasing sequences (an)n∈Nand (bn)n∈Nsuch that {(ai, bj)|i≤j} ∪ {(bj, ai)|j < i}⊆X. 2. There exist non-principal ultrafilters V1,V2on Nsuch that X∈(V1⊗ V2)∩(V2⊗ V1). Proof. (1) ⇒(2). Let A={an|n∈N}and B={bn|n∈N}. We observe that the family F1:= {A}∪{Xbj|j∈N} ∪ {[n, ∞]|n∈N}has the finite intersection property; indeed, ai∈A∩Xb1∩...∩Xbk∩[n, ∞] for every i > k, n. Similarly, the family F2:= {B} ∪ {Xai|i∈N} ∪ {[n, ∞]|n∈N}also has the finite intersection property. So, we can pick non-principal ultrafilters V1⊇ F1and V2⊇ F2. Note that the set Y1:= {(ai, bj)|i≤j} ∈ V1⊗ V2because for every as∈Athe vertical fiber (Y1)as={bj|j≥s}=B∩[as,∞]∈ V2. Similarly, Y2:= {(bj, ai)|i≤j} ∈ V2⊗ V1because for every bt∈Bthe vertical fiber (Y2)bt∈ V1. We conclude that X⊇Y1∪Y2∈(V1⊗ V2)∩(V2⊗ V1), as desired. (2) ⇒(1). Let X(1) := {n|Xn∈ V1}and X(2) := {n|Xn∈ V2}. By definition, X∈ V1⊗ V2⇔X(2) ∈ V1and X∈ V2⊗ V1⇔X(1) ∈ V2. Pick 2The standard reference for pseudo-sums of ultrafilters, and more generally for the algebra on the space of ultrafilters on a set Sas determined by an arbitrary associative operation on S, is Hindman-Strauss’ book [8]. For more information on tensor products, see [8, §11.1]; see also [3] where their combinatorial properties are investigated. INTEGERS: 25 (2025) 4 a1∈X(2); then Xa1∈ V2. Pick b1∈X(1) ∩Xa1∈ V2with b1> a1(this is possible because V2is non-principal); then (a1, b1)∈Xand Xb1∈ V1. Inductively, pick an+1 ∈X(2) ∩Tn i=1 Xbi∈ V1with an+1 > bn, so that (bi, an+1)∈Xfor all i= 1, . . . , n and Xan+1 ∈ V2. Then pick bn+1 ∈X(1) ∩Tn+1 i=1 Xai∈ V2with bn+1 > an+1, so that (ai, bn+1)∈Xfor all i= 1,...,n + 1 and Xbn+1 ∈ V1. It is easily verified that the increasing sequences (an) and (bn) satisfy the desired properties. We are finally ready to give a proof of the Pairwise Sum Theorem. Theorem 2.2. For every finite coloring of the natural numbers there exist infinite disjoint sets A, B such that A∪B∪(A+B)is monochromatic. Proof. Let Ube a non-principal ultrafilter on N. For n∈N, denote by Un⊕the iterated sum of the ultrafilter Uwith itself, i.e.,U1⊕=U, and inductively U(n+1)⊕= Un⊕⊕ U. We observe that Un⊕⊕ Um⊕=U(n+m)⊕. Given a finite coloring N=C1∪. . . ∪Cr, consider the coloring N=D1∪. . . ∪Dr where we put n∈Diif and only if Ci∈ Un⊕. By Schur’s Theorem there exists a color Diand a pair a=bsuch that a, b, a +b∈Di. This means that the color C=Ciis a member of V1∩V2∩W, where V1:= Ua⊕,V2:= Ub⊕, and W:= U(a+b)⊕. We now observe that the image ultrafilters π1(V1⊗ V2) = π2(V2⊗ V1)=V1and π2(V1⊗ V2)=π1(V2⊗ V1)=V2where π1, π2:N×Nare the canonical projections. We also observe that W=V1⊕ V2=V2⊕ V1= Sum(V1⊗ V2) = Sum(V2⊗ V1), and so, X:= π−1 1(C)∩π−1 2(C)∩Sum−1(C) = ={(a, b)∈C×C|a+b∈C}∈(V1⊗ V2)∩(V2⊗ V1). Now apply Lemma 2.1 to X, and obtain the existence of disjoint increasing sequences (an)n∈Nand (bn)n∈Nsuch that Γ:={(ai, bj)|i≤j} ∪ {(bj, ai)|j < i}⊆X. Let A:= {an|n∈N}and B:= {bn|n∈N}. Then A=π1(Γ) ⊆π1(X)⊆C, B=π2(Γ) ⊆π2(X)⊆C, and A+B= Sum(Γ) ⊆Sum(X)⊆C, as desired. 3. A Topological Formalization As already remarked in the introduction, Open Question (Q12) as formulated in [7] is somewhat vague and ambiguous. Here we propose a formalization in topological terms. As it is well-known, there is a close connection between weak partition regularity and ultrafilters, grounding on the following fact. INTEGERS: 25 (2025) 5 Proposition 3.1 ([8, Thm. 5.7]).Let F ⊆ P(S). The following properties are equivalent: 1. Fis weakly partition regular on S. 2. There exists an ultrafilter Uon Ssuch that for every A∈ U there exists F∈ F with F⊆A. An ultrafilter Uas above is called a PR-witness of the family F. Notation 3.2. Following a common use, given sets of natural numbers A={an|n∈N}and B={bn|n∈N} where the sequences (an) and (bn) are increasing, we write A⊕B={ai+bj|i < j}. In particular, A⊕Acontains all pairwise sums of distinct elements of A.3 Notice that Hindman’s Theorem states that H:= {FS(X)|X⊆Ninfinite}is a weakly partition regular family; and similarly, the Pairwise Sum Theorem states that S2={B∪(B⊕B)|B⊆Ninfinite}is a weakly partition regular family. One can formalize the Open Question (Q12) as a precise mathematical statement in terms of witness ultrafilters, as follows: (†)Is there an ultrafilter Uthat is a PR-witness of S2but not a PR-witness of H? As we will show below, property (†) can be reformulated in purely topological terms within the Stone–ˇ Cech compactification βN2of the discrete space N2. Recall that βN2is usually represented as the space of ultrafilters on N2where a base of (cl)open sets is given by the family of sets of the form OX:= {W ∈ βN2|X∈ W} (see [8, Section 3.2]). Recall the following fact. Proposition 3.3 ([8, Lemma 5.19]).An ultrafilter is a PR-witness of the family H if and only if it belongs to the topological closure of the set of idempotents: H={U ∈ βN| U ⊕ U =U}. In the recent paper [4], the class of witnesses of the PR property given by Ramsey’s Theorem on pairs was introduced and studied. 3We observe that the same ⊕symbol is also used for the “pseudo-sum” operation between ultrafilters on N; however, here this should not cause misunderstandings. INTEGERS: 25 (2025) 6 Definition 3.4. An ultrafilter Won N2isaRamsey’s witness if for every X∈ W there exists an infinite Hsuch that [H]2={(h, h′)∈H×H|h < h′}⊆X. The following fact was already pointed out in [4]. For completeness, we give a proof here. Proposition 3.5. An ultrafilter W ∈ βN2is a Ramsey’s witness if and only if it belongs to the closure Tof the set of tensor powers T:= {U ⊗ U | U ∈ βN\N}. Proof. Let W ∈ T, and let X∈ W. Then X∈ U ⊗U for some non-principal U. Now we observe that every such tensor power is a Ramsey’s witness. Indeed, X∈ U ⊗ U if and only if XU:= {n|Xn∈U}∈U. Pick h1∈XUand, inductively, pick hn+1 ∈XU∩Xh1∩. . . ∩Xhn∈ U. Since Uis non-principal we can pick hn+1 > hn. Then H={hn|n∈N}is the desired infinite homogeneous set [H]2⊆X. Conversely, let H={h1< . . . < hn< . . .}be an infinite set with [H]2⊆X. The family F:= {{hm|m≥n} | n∈N}has the finite intersection property, and it is easily verified that every (necessarily non-principal) ultrafilter U ⊇ F is such that [H]2∈ U ⊗ U, and hence X∈ U ⊗ U. We now observe the following property that connects Ramsey’s witnesses with the Pairwise Sum Theorem. Proposition 3.6. Uis a PR-witness of the family S2if and only if there exists a Ramsey’s witness Wsuch that U=π1(W)=π2(W)=Sum(W). Proof. Let A∈ U =π1(W)=π2(W) = Sum(W). Then XA:= π−1 1(A)∩π−1 2(A)∩Sum−1(A)={(a, a′)∈A×A|a+a′∈A} ∈ W. Pick an infinite B={b1< . . . < bn< . . .}with [B]2⊆XA. Then it is easily verified from the definitions that B∪(B⊕B)⊆A. For the converse implication, observe that an ultrafilter Won N2has the property π1(W) = π2(W) = Sum(W) = Uif and only if the preimages π−1 1(A), π−1 2(A), and Sum−1(A) belong to Wfor every A∈ U; equivalently, if and only if ΓA:= (A×A)∩Sum−1(A)∈ W for every A∈ U. Observe also that an ultrafilter Won N2is a Ramsey’s witness if and only if Wextends the following family: R={X⊆N2|[H]2⊆ Xcfor every infinite H}. Thus we reach the thesis if we show that there exists an ultrafilter Wthat extends the family R∪{ΓA|A∈ U}, and this is equivalent to having R∪{ΓA|A∈ U} satisfy the finite intersection property. Assume towards a contradiction that there INTEGERS: 25 (2025) 7 are X1, . . . , Xs∈ R and A1, . . . , At∈ U such that Ts i=1 Xi∩Tt j=1 ΓAj=∅. If A:= A1∩. . . ∩Atthen we have (A×A)∩Sum−1(A) = t \ j=1 ΓAj⊆(X1)c∪. . . ∪(Xs)c. Since A∈ U we can pick an infinite B={b1< . . . < bn< . . .}such that B∪ (B⊕B)⊆A. This means that [B]2⊆(A×A)∩Sum−1(A)⊆(X1)c∪. . . ∪(Xs)c. Finally, consider the finite coloring [N]2=C1∪...∪Cswhere (n, m)∈Ci⇔iis the least index such that (bn, bm)∈(Xi)c. By Ramsey’s Theorem there exists an infinite Hsuch that its pairs [H]2⊆Ciare monochromatic. But then we would have [{bh|h∈H}]2⊆(Xi)c, a contradiction. Putting all of the above together, we can finally give a precise formalization of Open Question 12 from [7] as the following property of the topological space βN2, obtained as a reformulation of the previous (†). (Q12) Consider the following subspaces of βN2: –T:= {U ⊗ U | U ∈ βN\N}. –S:= {W ∈ βN2|π1(W)=π2(W) = Sum(W)}, Is it true that Sum T∩S=Sum (T∩S)? Acknowledgement. M. Di Nasso is supported by the Italian research project PRIN 2022: “Logical methods in combinatorics”, 2022BXH4R5, MIUR (Italian Ministry of University and Research), and is a member of the INdAM research group GNSAGA. R. Jin is supported by Simons Foundation (grant number 513023). References [1] B. Barber, N. Hindman, and I. Leader, Partition regularity in the rationals, J. Comb. Theory Ser. A 120 (2013), 1590-1599. [2] B. Barber and I. Leader, Partition regularity with congruence conditions, J. Comb. 4(2013), 293-297. [3] M. Di Nasso, The magic of tensor products of ultrafilters, preprint, ArXiv:2506.14344. [4] M. Di Nasso, L. Luperi Baglini, M. Mamino, R. Mennuni, and M. Ragosta, Ramsey’s witnesses, preprint, ArXiv:2503.09246. [5] M. Di Nasso and R. Jin, Foundations of iterated star maps and their use in combinatorics, Ann. Pure Appl. Logic 176 (2025), 103511. INTEGERS: 25 (2025) 8 [6] N. Hindman, Finite sums from sequences within cells of a partition of N,J. Comb. Theory Ser. A 17 (1974), 1-11. [7] N. Hindman, I. Leader, and D. Strauss, Open problems in partition regularity, Combinatorics, Probability, and Computing 12 (2003), 571-583. [8] N. Hindman and D. Strauss, Algebra in the Stoneˇ Cech compactification: Theory and Applications, 2nd ed., Walter de Gruyter, Berlin, 2012. [9] I. Leader and P.A. Russell, Independence for partition regular equations, J. Comb. Theory Ser. A 114 (2007), 825-839. [10] Y. Zelenyuk, Elements of order 2 in βN,Fund. Math. 252 (2021), 355-360.