# On Generalized Schur Numbers of the Equationx+ay=z

Authors: Amir Khamseh
Journal: Journal of Mathematics
 (2020)

---

## Abstract

Letaandr be positive integers. By definition, sar is the least positive integer such that, for any r-coloring of the interval 1,sar, there exists a monochromatic solution to x+ay=z. For a=1, the numbers sr=s1r are classical Schur numbers. In this paper, we study the numbers sar for a≥2.


---

## Body

## 1. Introduction

Ramsey theory, an area that has seen a remarkable burst of research activity during the past twenty years, is the study of the preservation of properties under set partitions. In other words, given a particular setS that has a property P, is it true that whenever S is partitioned into finitely many subsets, one of the subsets must also have property P? Ramsey theory is named after Frank Plumpton Ramsey and his theorem, which he proved in 1928. Ramsey stated his fundamental theorem in a general setting and applied it to formal logic. Schur [1] and van der Waerden [2] obtained similar results in number theory. Dilworth’s theorem [3] for partially ordered sets is another typical example. Ramsey’s theorem was applied to geometry by Erdős and Szekeres [4]. They also defined the Ramsey numbers and gave some upper and lower bounds for them. Ramsey-type theorems have applications in different branches of mathematics such as number theory, set theory, geometry, ergodic theory, and theoretical computer science. In [5], connections between the computation of van der Waerden numbers and propositional theories have been shown. Using these connections, they serve as benchmarks for solvers of satisfiability problems. For more on Ramsey theory and its applications, we refer to the book of Graham et al., [6], and the surveys of Nešetřil [7] and Rosta [8]. Somewhat surprisingly, Ramsey’s theorem was not the first theorem in the area now known as Ramsey theory. The result that is generally accepted to be the first Ramsey-type theorem is due to Schur [1] and it deals with colorings of the integers: if ℕ is partitioned into a finite number of classes, at least one partition class contains a solution to the equation x+y=z.Let us now go over the details of some definitions and notations from [9]. An interval a,b is a set of the form a,a+1,…,b, where a<b are integers.Definition 1.
Anr-coloring of a set S is a function χ:S⟶C, where C=r.
In fact, anr-coloring χ of a set S is a partition of S into r subsets S1,…,Sr, by associating the subset Si with the set x∈S:χx=i.Definition 2.
A coloringχ is monochromatic on a set S if χ is constant on S.
It is often convenient to represent a particular 2-coloring of an interval as a string of 0s and 1s. For example, the coloringχ:1,5⟶0,1 with χ1=χ2=χ3=1 and χ4=χ5=0 could be represented by the string 11100 or 1302. As we mentioned before, one of the earliest results in Ramsey theory was proved by Issai Schur in 1916.Theorem 1.
(Schur’s Theorem). For anyr≥1, there exists a least positive integer sr such that, for any r-coloring of 1,sr, there exists a monochromatic solution to x+y=z.
The numberssr are called the Schur numbers. The known Schur numbers are s1=2, s2=5, s3=14, and s4=45. Note that x and y in Schur’s theorem need not be distinct. If we require that x and y be distinct, the resulting Ramsey-type statement is also true.Theorem 2.
Forr≥1, there exists a minimal integer rs such that every r-coloring of 1,sr admits a monochromatic solution to x+y=z with x and y being distinct.It is known that Schur’s theorem is a consequence of Ramsey’s theorem. There are a number of interesting results proved during the last years concerning Schur’s theorem and generalizations. A triplex,y,z of natural numbers is called a Schur triple if x≠y and x+y=z. Let SN be the minimum number of monochromatic Schur triples in any 2-coloring of N=1,2,…,N. Graham et al. [10] found the lower bound SN≥1/38N2+ON. They used the Ramsey multiplicity result [11, 12], which says that in every 2-coloring of the edges of a complete graph on N vertices, there are at least N3/24+ON2 monochromatic triangles. Answering a question raised in [10], Robertson and Zeilberger [13] and, independently, Schoen [14] showed that SN=1/22N2+ON. Robertson and Zeilberger found a 2-coloring with N2/22 monochromatic Schur triples and formulated a conjecture on the minimum number of triples. Schoen showed that every extremal coloring looks like the Robertson–Zeilberger construction, and he used this result to find the exact number SN=1/22N2−7/22N, for N≡0mod22.One can look at Schur’s theorem in terms of sum-free sets. A setA⊆ℕ is called sum-free if x,y∈A implies x+y∉A. The Schur function st is defined as the maximum m∈ℕ such that 1,2,…,m can be partitioned into t sum-free sets. We mention here a generalization of Schur’s theorem for sum-free sets: if ℕ is finitely colored, there exists arbitrarily large finite set A⊆ℕ such that the sum-free set of A, ∑a∈Ba:B⊆A,1≤B<∞ is monochromatic. Note that Hindman’s theorem [15] gives the same result when A is an infinite set. On the other hand, Alekseev and Savchev [16] considered a similar problem and proved that for every equinumerous 3-coloring of 3n (i.e., a coloring in which different color classes have the same cardinality), the equation x+y=z has a solution, with x,y, and z belonging to different color classes. Such solutions will be called rainbow solutions. Moreover, Schönhei̇m [17] proved that for every 3-coloring of n, every color class has cardinality greater than n/4 and the equation x+y=z has rainbow solutions. Moreover, he showed that n/4 is optimal.We now recall another generalization of Schur’s theorem. Letℒt represent the equation x1+x2+⋯+xt−1=xt, where x1,…,xt are variables.Theorem 3.
Letr≥1 and, for 1≤i≤r, assume that ki≥3. Then, there exists a least positive integer sk1,k2,…,kr such that for every r-coloring of 1,sk1,k2,…,kr, there is a solution to ℒkj of color j for some j∈1,2,…,r.
Just as Schur’s theorem, Theorem3 follows from Ramsey’s theorem. The numbers sk1,k2,…,kr are called the generalized Schur numbers. In [18], the authors determine 26 previously unknown values of sk1,k2,…,kr and conjecture that for 4≤k1≤k2≤k3, sk1,k2,k3=k1k2k3−k3k2−k3−1.
Following a problem proposed in [9], we consider the monochromatic solutions to x+ay=z. For abbreviation, we write sa instead of sa2.Definition 3.
For integersaandr≥1, let sar be the least positive integer such that, for any r-coloring of 1,sar, there exists a monochromatic solution to x+ay=z.
The existence of such monochromatic solutions is implied by Rado’s theorem.Theorem 4.
(Rado’s Theorem). For anyr≥1, there exists n such that for every r-coloring of 1,n, there is a monochromatic solution to the linear equation ∑i=1ncixi=0, where ci∈ℤ−0 for 1≤i≤n, if and only if some nonempty subset of the ci’s sums to 0.


## 2. Exact Value ofsa

In this section, we find the exact value ofsa. The standard methodology for finding the exact value of any particular Ramsey-type number is to show that some number serves both as a lower bound and an upper bound. We may illustrate this phenomenon by a simple example. We will establish that s2=11 by using the above method to prove that s2≥11 and s2≤11.To show thats2≥11, it suffices to exhibit a 2-coloring of 1,10 with no monochromatic solution to x+2y=z. One such coloring is the following: color the intervals 1,2 and 9,10 red and color the interval 3,8 blue. It is easy to see that this coloring avoids any monochromatic solution to x+2y=z. For all possible solutions, see Table 1.Table 1
All solutions tox+2y=z in the interval 1,10.
VariablesValuesx12132413524613572468y11212132132143214321z345566777888999910101010To show thats2≤11, we must show that every 2-coloring of 1,11 admits a monochromatic solution to x+2y=z. Using red and blue as the colors, assume, for a contradiction, that there exists a 2-coloring χ of 1,11 with no monochromatic solution to x+2y=z. Since 1,1,3 and 3,3,9 cannot be monochromatic, without loss of generality, we can assume that χ1=χ9= red and χ3= blue. Since neither of the triples 1,4,9, 7,1,9, and 9,1,11 can be red, 4, 7, and 11 must be blue. From this, we have that 3,4,11 is blue, contradicting our assumption.The method to obtain the lower and upper bounds in general is similar to the one used in the above example. We first establish the lower bound.Theorem 5.
Fora≥1, sa>a2+3a.Proof.
Leta≥1. To show that sa>a2+3a, it suffices to find some 2-coloring of 1,a2+3a that yields no monochromatic solution to x+ay=z. Using 0 and 1 as the colors, it is an easy task to check that the coloring 1a0aa+11a contains no monochromatic solution to x+ay=z. Hence, sa>a+aa+1+a=a2+3a.Theorem 6.
Fora≥1, sa≤a2+3a+1.Proof.
To show thatsa≤a2+3a+1, we must show that every 2-coloring of 1,a2+3a+1 admits a monochromatic solution to x+ay=z. Using red and blue as the colors, assume, for a contradiction, that there exists a 2-coloring χ of 1,a2+3a+1 with no monochromatic solution to x+ay=z. Since 1,1,a+1 and a+1,a+1,a+12 cannot be monochromatic, without loss of generality, we can assume that χ1=χa+12= red and χa+1= blue. Since neither of the triples 1,a+2,a+12, a+12−a,1,a+12, and a+12,1,a+12+a can be red, a+2, a+12−a, and a+12+a must be blue. From this, we have that a+1,a+2,a+12+a is blue, contradicting our assumption.By Theorems5 and 6, we have the following corollary.Corollary 1.
For alla≥1, we have sa=a2+3a+1.


## 3. A General Lower Bound

First, suppose thata=2. The coloring 120612 shows that s22≥11. One can extend to the coloring 021602222021602 to obtain that s23≥43. Continuing in this way, we have the following.Theorem 7.
For allr≥1, s2r≥2×4r+1/3.Proof.
Letn≥1 and assume χ:1,n⟶1,…,r is an r-coloring of 1,n with no monochromatic solution to x+2y=z. Define an r+1-coloring χ^:1,4n+1⟶1,…,r+1 of 1,4n+2 that extends χ as follows. For all x∈n+1,3n+2, let χ^x=r+1, and for all x∈1,n∪3n+3,4n+2, let χ^x=χy, where x≡y (mod 3n+2). Then, χ^ contains no monochromatic solution to x+2y=z. So if s2r≥n+1, then s2r+1≥4n+3 and thus, s2r+1≥4s2r−1. We now prove by induction that s2r≥2×4r+1/3. It is clearly true for r=1. Now, by induction hypothesis,(1)s2r+1≥4s2r−1≥42×4r+13−1=2×4r+1+13.
Fora≥1, the coloring 1a0aa+11a shows that sa2≥aa+3. We can extend this coloring to 1a0aa+11a2aaa+3+11a0aa+1 to obtain sa3>aa+2a+3+1=aa2+5a+7. Similarly, the coloring 1a0aa+11a2aaa+3+11a0aa+13aaa2+5a+7+11a0aa+11a2aaa+3+11a0aa+1 shows that sa4>aa+2a+3+1a+2+1. Continuing in this way, we can easily check that sa5>aa+2a+3+1a+2+1a+2+1. In general, we obtain the following theorem.Theorem 8.
For allr≥1, sar≥aa+2r+1/a+1.Proof.
Letn≥1 and assume χ:1,n⟶1,…,r is an r-coloring of 1,n with no monochromatic solution to x+ay=z. Define an r+1-coloring χ^:1,a+a+2n⟶1,…,r+1 of 1,a+a+2n that extends χ as follows. For all x∈n+1,a+a+1n, let χ^x=r+1, and for all x∈1,n∪a+1n+1,a+a+2n, let χ^x=χy, where x≡y (mod a+1n+1−1=a+a+1n). Then, χ^ contains no monochromatic solution to x+ay=z. So if sar≥n+1, then sar+1≥a+2n+a+1 and thus, sar+1≥a+2sar−1. We now prove by induction that sar≥aa+2r+1/a+1. It is clearly true for r=1. Now, by induction hypothesis,(2)sar+1≥a+2sar−1≥a+2aa+2r+1a+1−1=aa+2r+1+1a+1.


## 4.s23=43 and s33=94

In this section, we show thats23=43. The coloring 021602222021602 shows that s23≥43. We now show the other direction.Theorem 9.
We haves23≤43.Proof.
To show thats23≤43, we must show that every 3-coloring of 1,43 admits a monochromatic solution to x+2y=z. Using red, blue, and green as the colors, assume, for a contradiction, that there exists a 3-coloring χ of 1,43 with no monochromatic solution to x+2y=z. Since 1,1,3 cannot be monochromatic, without loss of generality, we can assume that χ1= red and χ3= blue. Then, χ9 is red or green. We suppose χ9= red and leave the other case to the reader. Since 1,9,11 cannot be red, then χ11= blue or green. If χ11= blue, then χ4= green, and if χ11= green, then χ4= blue or green. For a complete solution, we use the tree representation (see Figures 1 and 2).A computer search showed us thats33≤94, and so by the above upper bound, we have the following.Figure 1
Tree representation forχ9= red.Figure 2
Tree representation forχ9= green.Theorem 10.
We haves33=94.


## 5. Concluding Remark

In this paper, we obtain the lower bound forsar and find the exact value in the case of two colors. Moreover, we show that s23 and s33 are equal to the obtained lower bounds 43 and 94, respectively. It is interesting to prove the general formula for sa3. It seems that sa3=aa+2a+3+1+1.



---

*Source: 7069730-2020-05-31.xml*