On the n-Color Weak Rado Numbers for the Equation x1 + x2 + ··· + xk + c = xk +1

MATHEMATICS OF COMPUTATION Volume 85, Number 300, July 2016, Pages 2047–2064 http://dx.doi.org/10.1090/mcom3034 Article electronically published on September 14, 2015 ON THE n-COLOR RADO NUMBER FOR THE EQUATION x1+x2+···+xk+c=xk+1 S. D. ADHIKARI, L. BOZA, S. ELIAHOU, J. M. MAR´ IN, M. P. REVUELTA, AND M. I. SANZ Abstract. For integers k, n, c with k, n ≥1, the n-color Rado number Rk(n, c) is defined to be the least integer N,ifitexistsor∞otherwise, such that for every n-coloring of the set {1,2,...,N}, there exists a monochromatic solution in that set to the equation x1+x2+···+xk+c=xk+1. In this paper, we mostly restrict to the case c≥0, and consider two main issues regarding Rk(n, c): is it finite or infinite, and when finite, what is its value? Very few results are known so far on either one. On the first issue, we formulate a general conjecture, namely that Rk(n, c) should be finite if and only if every divisor d≤nof k−1 also divides c.The “only if” part of the conjecture is shown to hold, as well as the “if” part in the cases where either k−1 divides c,orn≥k−1, or k≤7, except for two instances to be published separately. On the second issue, we obtain new bounds on Rk(n, c) and determine exact formulae in several new cases, including R3(3,c)andR4(3,c). As for the case R2(3,c), first settled by Schaal in 1995, we provide a new shorter proof. Finally, the problem is reformulated as a Boolean satisfiability problem, allowing the use of a SAT solver to treat some instances. 1. Introduction Throughout the paper, we shall denote by Z,Nand N+the set of integers, nonnegative integers and positive integers, respectively. Let n∈N+.Ann-coloring of a set Ais a function Δ:A−→ C, where Cis some finite set of cardinality |C|=n. Here, we shall mostly deal with n-colorings of integer intervals [1,N], where [a, b]={a, a +1,...,b} for integers a≤b. Given an n-coloring Δ of [1,N] and a linear equation Lin k+ 1 variables with integer coefficients, a solution (x1,...,x k,x k+1)toLis said to be monochromatic if Δ(x1)=Δ(x2)=···=Δ(xk+1). Received by the editor June 4, 2014 and, in revised form, December 17, 2014. 2010 Mathematics Subject Classification. Primary 05A17, 11P83, 05C55, 05D10, 05-04. Key words and phrases. Schur numbers, sum-free sets, Rado numbers, Boolean variables, SAT problem, SAT solver. The authors acknowledge partial support from the Instituto de Matem´aticas; Antonio de Castro Brzezicki de la Universidad de Sevilla during research on this work. c 2015 American Mathematical Society 2047 License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use 2048 S. D. ADHIKARI ET AL. 1.1. Some earlier results. In 1916, Schur [22] proved that for every n≥1, there exists a least integer S2(n)=N, such that for every n-coloring of [1,N], there exists a monochromatic solution to the equation x1+x2=x3. The integers S2(n) are called the Schur numbers and are currently known only for n≤4, namely: S2(1) = 2, S2(2) = 5, S2(3) = 14 and S2(4) = 45. While these stated values for n≤3 can easily be settled by hand, the one for n= 4 relies on an exhaustive computer search [2]. For n= 5, the currently available bounds for S2(5) are 161 ≤S2(5) ≤306, and it is conjectured in [8] that the lower bound 161, established in [7], is perhaps sharp. For the upper bound 306, see [18]. For general n≥1, Schur [22] obtained the following bounds: (3n+1)/2+1 ≤S2(n)≤n!e+1. Slightly improved upper bounds were subsequently provided by Whitehead [23] and Honghui Wan [10], whereas for lower bounds, the inequalities S2(m+n)≥2S2(m)S2(n)−S(m)−S(n)+1 of Abbott and Hanson [1], and S2(5) ≥161 of Fredricksen and Sweet [8], together yield the sharpening S2(n)≥c322n/5≥c3.17nfor n≥6, where cis some absolute positive constant. In 1933, Rado [13] generalized the work of Schur to arbitrary systems of linear equations. Given n≥1 and a system of linear equations L, the least integer N(if it exists) such that for every n-coloring of the set [1,N], there is a monochromatic solution to the system L, is called the n-color Rado number for L. If no such integer Nexists, then this Rado number is defined to be infinite. Given a linear system Las above, and n≥1, there are two main issues regarding its corresponding n-color Rado number: is it finite or infinite? When it is finite, what is its exact value? In particular, for the equation x1+x2+···+xk=xk+1 where k≥2, Rado’s results imply that for all n≥1, the corresponding n-color Rado number is actually finite, i.e., there exists a least integer Sk(n)=Nsuch that for every n-coloring of [1,N], there is a monochromatic solution of that equation [13]. In 1982, Beutelspacher and Brestovansky [5] showed that Sk(2) = k2+k−1 for k≥2. More than twenty years later, Sanz [18] established the value S3(3) = 43 with an exhaustive computer search. Burr and Loo [3] were able to determine the 2-color Rado numbers for the equations x1+x2+c=x3and x1+x2=kx3for every integer cand for every positive integer k. There are several results due to Schaal and other authors, about 2-color and 3-color Rado numbers for particular equations; see [11,12,15,21]. 1.2. The main conjecture. Let n, k, c be integers with n, k ≥1andc≥0. In this paper, we shall be concerned with the above-mentioned equation (1) x1+x2+···+xk+c=xk+1. Notation 1.1.We shall denote by Rk(n, c)then-color Rado number corresponding to equation (1), i.e., the smallest positive integer N, if it exists, such that every n-coloring of [1,N] admits a monochromatic solution to it. For what values of the parameters n, k, c is Rk(n, c) finite? By Rado’s result, recalled above, it holds that Rk(n, 0) = Sk(n) is always finite. Now, for n=2, License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use ON THE n-COLOR RADO NUMBER FOR x1+x2+···+xk+c=xk+1 2049 Schaal [19] showed that Rk(2,c)is finite if and only if kor cis even,inwhichcase Rk(2,c)=(k+1) 2+(c−1)(k+2). Later on, he further showed that the 3-color Rado number R2(3,c) is always finite [20], and obtained the exact value R2(3,c)=13c+ 14 for all c≥0. In this paper, we provide further instances of n, k, c for which Rk(n, c)isshown to be finite or infinite, respectively. These results, as well as those of Schaal on Rk(2,c)andR2(3,c), fit into one single conjecture. Conjecture 1.2. For integers k,n, c with k≥2,n≥1and c≥0,then-color Rado number Rk(n, c)is finite if and only if every divisor d≤nof k−1also divides c. In the sequel, we settle this conjecture if either k−1 divides c,orn≥k−1, or k≤7, except for two special cases which need a completely different approach and will be presented elsewhere. 1.3. Contents. In Section 2, we settle the “only if” part of Conjecture 1.2 by giving a sufficient condition on n, k, c ensuring that Rk(n, c) is infinite. In Section 3, we study how Rk(n, c) behaves under changes on nand c, and then exploit the results to settle Conjecture 1.2 in cases n≥k−1andk≤7. In Section 4, we introduce new numbers S∗ k(n), smaller and easier to study than Sk(n), and show how they help bounding Rk(n, c) from below. This is then exploited in Section 5, in conjunction with SAT solvers, to get new formulae for some instances of Rk(n, c). 2. An obstacle to finiteness We start by treating the cases n=1ork=1. Forn= 1, the Rado number Rk(n, c) is given by the formula (2) Rk(1,c)=k+c for all k≥1andc≥0, as readily verified. The case k=1isalsoeasytodetermine. Indeed, for c=0wehave R1(n, 0) = 1 for all n≥2, whereas the following holds for c≥1. Proposition 2.1. For all n≥2and c≥1, we have R1(n, c)=+∞. Proof. The statement follows from the following 2-coloring of N+: Δ: N+−→ { 0,1}, x−→ the class of x/cmod 2. Since (x+c)/c=x/c+ 1, implying Δ(x+c)≡Δ(x)+1mod2,thereareno monochromatic solution to the equation x1+c=x2, thereby implying R1(n, c)= +∞as stated.  Therefore, from now on, we shall assume k,n ≥2. Here is an obstacle to the finiteness of Rk(n, c), which settles the “only if” part of Conjecture 1.2. Proposition 2.2. If there exists a divisor d≤nof k−1which does not divide c, then Rk(n, c)=+∞. License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use 2050 S. D. ADHIKARI ET AL. Proof. Color each integer by its class mod d, taken in the set {0,1,...,d−1}. This yields a d-coloring of N+.Letx1,...,x k+1 ∈N+be monochromatic for this coloring, say all of the same color class rmod d.Then x1+···+xk−xk+1 ≡(k−1)r≡0modd, where the second congruence follows from the hypothesis that ddivides k−1. Now since c≡ 0moddby hypothesis, it follows that (x1,...,x k+1)cannotsatisfythe equation x1+···+xk−xk+1 =−c. Therefore this equation does not admit any monochromatic solution. It follows that Rk(d, c)=+∞, whence also Rk(n, c)=+∞, as claimed.  In fact, the above condition is the only general one we are aware of which implies Rk(n, c)=∞. This is what led us to formulate Conjecture 1.2. 3. Varying nand c In this section, we shall vary the parameters nand cand show how this affects the value of Rk(n, c). This study will ultimately allow us to settle Conjecture 1.2 in the cases where either k−1 divides c,orn≥k−1, or k≤7, except for two key instances which need a different approach and will be published separately. 3.1. Reducing n.Our first result is a relation between n-color and (n−1)-color Rado numbers. Trivially, one has Rk(n, c)≥Rk(n−1,c), but a sharper inequality holds. Lemma 3.1. Let k,n, c ∈N+.ThenRk(n, c)≥(k+1)Rk(n−1,c)+c−1. Proof. To ease notation, set M=Rk(n−1,c)andN=kM +c.Thus (k+1)Rk(n−1,c)+c−1=N+M−1, and our aim is to show that Rk(n, c)≥N+M−1. In order to do that, it suffices to construct an n-coloring of the integer interval [1,N+M−2] for which that interval contains no monochromatic xi’s satisfying the equation (3) x1+···+xk+c=xk+1. The minimality property of Rk(n, c) will then imply the desired inequality. By definition of M, there exists an (n−1)-coloring (4) Δ: [1,M −1] −→ [1,n−1] such that [1,M−1] contains no Δ-monochromatic xi’s satisfying equation (3). We now extend (4) to an n-coloring Δ:[1,N +M−2] −→ [1,n] as follows: Δ(x)=⎧ ⎨ ⎩ Δ(x)ifx∈[1,M −1], nif x∈[M,N −1], Δ(x−(N−1)) if x∈[N,N +M−2]. It remains to show that [1,N +M−2] is free of a Δ-monochromatic solution to (3). Assuming the contrary, let x1,...,x k+1 ∈[1,N+M−2] satisfy (3) and be of the same Δ-color in [1,n]. License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use ON THE n-COLOR RADO NUMBER FOR x1+x2+···+xk+c=xk+1 2051 First, that common color cannot be n, for otherwise all xi’s would belong to [M,N −1], thereby yielding xk+1 =x1+···+xk+c≥kM +c=N, a contradiction. Therefore, that common color of x1,...,x k+1 belongs to [1,n−1]. Hence, some xi’s belong to [1,M −1] and the rest to [N,N +M−2]. How do they distribute among these two intervals? First, we may assume that x1≤···≤xk. Note further that xk<x k+1,since xk+1 =x1+···+xk+c≥k+c≥2 by hypothesis on c. Clearly, the xi’s cannot all belong to [1,M −1] by our hypothesis on (4). It follows that the largest one, namely xk+1, belongs to [N,N +M−2]. We claim that x1,...,x k−1∈[1,M −1] and xk∈[N,N +M−2]. Indeed, by (3) and the fact that xk+1 ∈[N,N +M−2], at most one among {x1,...,x k}maybelongto[N,N +M−2], since 2N>N+M−2 as readily verified. Similarly, at least one among {x1,...,x k}must belong to [N,N +M−2], for otherwise xk≤M−1, and by (3) we would have xk+1 ≤k(M−1) + c<N, a contradiction. Subtracting N−1fromxkand xk+1, it follows that x1,...,x k−1,x k−(N−1),x k+1 −(N−1) are Δ-monochromatic, belong to [1,M−1], and satisfy (3), a contradiction. Therefore, the interval [1,N+M−2] contains no Δ-monochromatic solution to (3), and the proof is finished.  Applying the above result inductively, we obtain the following absolute lower bound. Theorem 3.2. Let k,n,c ∈N+.ThenRk(n, c)≥(k+1)n−1 k(k+c−1) + 1. Proof. The inequality holds for n=1,sinceRk(1,c)=k+cby (2). For general n≥2, we apply induction and Lemma 3.1.  3.2. Reducing c.We now vary the parameter cand show how Rk(n, c) is affected. Several consequences will then be presented in subsequent sections. Lemma 3.3. Let α, β ∈Zsuch that α≥1and β≥1−α. Then for all integers k,n,c with k,n ≥2and c≥0, we have Rk(n, αc −β(k−1)) ≤αRk(n, c)+β. License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use 2052 S. D. ADHIKARI ET AL. Proof. Let Ibe the integer interval I=[1,αR k(n, c)+β] and let Δ: I→[1,n]beanyn-coloring of I. We must show that there exist x1,...,x k+1 ∈Iwhich are monochromatic under Δ and which satisfy the equation x1+···+xk+(αc −β(k−1)) = xk+1. By the defining minimality property of Rk(n, (αc −β(k−1))), this will suffice to establish the stated inequality. Let J=[1,R k(n, c)]. We affinely embed Jin Ias follows: h:J−→ I z−→ αz +β. Note that our hypotheses on α, β ensure that if z≥1, then αz +β≥1 and, more generally, that h(J)⊆I. By composing Δ with h,weobtainann-coloring Δ=Δ◦hon J,namelythemapΔ :J→[1,n] defined by Δ(z)=Δ(αz +β) for all z∈J. Now, by definition of the upper bound Rk(n, c)ofJ, there exists a Δ-monochromatic solution z1+···+zk+c=zk+1 with zi∈Jfor all i. Multiplying by αand adding β’s, we get (αz1+β)+···+(αzk+β)+(αc −β(k−1)) = (αzk+1 +β). Now (αzi+β)∈Ifor all i, and since the ziare Δ-monochromatic, it follows that the (αzi+β) are Δ-monochromatic. This concludes the proof of the lemma.  3.3. The case n≥k−1.A first consequence of the above lemma is the verification of Conjecture 1.2 in the cases where either c≡0modk−1 (Proposition 3.4) or n≥k−1(Theorem3.5). Proposition 3.4. If cis a multiple of k−1,thenRk(n, c)is finite. More precisely, if c=q(k−1) for some integer q≥1,then Rk(n, c)≤(q+1)Sk(n)−q. Proof. It follows from Lemma 3.3, with values β=−q,α=q+1 (so that α+β≥1 as required), and c= 0 (the cin that lemma, not the present one), that Rk(n, q(k−1)) ≤(q+1)Rk(n, 0) −q =(q+1)Sk(n)−q.  We may now settle Conjecture 1.2 in the case n≥k−1. Theorem 3.5. Assume n≥k−1and c≥0.ThenRk(n, c)is finite if and only if cis a multiple of k−1. Proof. If cis a multiple of k−1, the statement follows from the above proposition. On the other hand, if cis not a multiple of k−1, then Proposition 2.2, with divisor d=k−1, implies Rk(n, c)=+∞. License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use ON THE n-COLOR RADO NUMBER FOR x1+x2+···+xk+c=xk+1 2053 3.4. Further consequences. Our next consequence of Lemma 3.3 is a bound on Rk(n, c)intermsofRk(n, 1). Proposition 3.6. For all c≥1, we have Rk(n, c)≤cRk(n, 1).Inparticular,if Rk(n, 1) is finite, then Rk(n, c)is finite for all c≥0. Proof. Applying Lemma 3.3 with c= 1 (the cin that lemma again, not the current one) yields Rk(n, α −β(k−1)) ≤αRk(n, 1) + β for all integer α≥1andβ≥1−α. Now, setting α=c(the current one) and β=0 in the above relation yields the stated inequality.  Finally, we find that if c≥k−1, then Rk(n, c) may be bounded below by Rk(n, c)−q,wherecis the class of cmod k−1andqis the floor of c/(k−1). Proposition 3.7. Assume c≥k−1,andletc=q(k−1) + cbe the Euclidean division of cby k−1,withq≥0and 0≤c≤k−2.Then Rk(n, c)≤Rk(n, c)+q. Proof. It follows from Lemma 3.3, with values α=1andβ=q,that Rk(n, c)=Rk(n, c −(k−1)q)≤Rk(n, c)+q.  3.5. The case k≤7.We now verify Conjecture 1.2 in case k≤7, except for the instances R5(3,2) and R6(4,1) which require completely different methods and will be presented elsewhere. Only the “if” part of the conjecture remains open. It states that if every divisor d≤nof k−1 also divides c,thenRk(n, c) should be finite. This is known to be true in the following cases: •if c=0,inwhichcaseRk(n, 0) is finite by Rado’s results [13]. •if n= 2, by Schaal’s results recalled in [19, Section 1.2]. •if c≡0modk−1, in which case Rk(n, c) is finite by Proposition 3.4. •if n≥k−1, by Theorem 3.5. Consequently, for k≤7, it remains to verify the “if” part of the conjecture only for n∈[3,k−2]. In particular, Conjecture 1.2 holds for k≤4. The case k= 5. It remains to discuss the case n=3andc≡ 0mod4. •For codd, there is a divisor d≤nof k−1 = 4 not dividing c,namely d= 2. Therefore R5(3,c)=∞in that case, by the “only if” part of the conjecture, i.e., by Proposition 2.2. •For c≡2 mod 4: according to the conjecture, we must show that R5(3,c) is finite in this case. Now Lemma 3.3 reduces that statement to the sole finiteness of R5(3,2). Indeed, it implies R5(3,2α)≤αR5(3,2) for all α≥1, by setting β=0andc= 2 there. Finally, it turns out that R5(3,2) is indeed finite, as will be proved elsewhere. We conclude that the conjecture holds for k=5. The case k= 6. We may assume n∈[3,4] and c≡ 0 mod 5. The only divisor d≤nof k−1 = 5 is 1, which divides any c. Therefore, according to the conjecture, we must show that R6(n, c) is finite for n∈[3,4] and all c≥1. Proposition 3.6 and the obvious bound Rk(3,c)≤Rk(4,c) reduce that statement to the sole finiteness of R6(4,1). Again, R6(4,1) turns out to be finite, with a proof similar to that for License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use 2054 S. D. ADHIKARI ET AL. R5(3,2) and to appear in the same paper. We conclude that the conjecture also holds for k=6. The case k= 7. We may assume n∈[3,5] and c≡ 0 mod 6. The only divisors d≤nof k−1=6are1,2and3. Ifeither2or3doesnotdividec,thenR7(n, c)=∞ in these cases, by the “only if” part of the conjecture, i.e., by Proposition 2.2. Now, if both 2 and 3 divide c,thenc≡0 mod 6, an already settled case. Therefore, the conjecture holds for k= 7, with a proof entirely contained in the present paper in contrast to the cases k=5and6. The conjecture remains open for k≥8. However, in order to settle the smallest open case k= 8, it would suffice, by using the same reduction tools as above, to show that R8(6,1) is finite. 3.6. Yet another case of the conjecture. Here is yet another case where Conjecture 1.2 is shown to hold. Its interest lies in the fact that nis smaller than k−1, in contrast with the situation in Section 3.3. Proposition 3.8. Let nbe an integer such that gcd(n, 6) = 1 and n≥5.Let k=6n+1. The following statements are equivalent. (1) Rk(n, c)is finite. (2) Every divisor d≤nof k−1also divides c. (3) k−1divides c. Proof. That (1) implies (2) directly follows from Proposition 2.2. Now assume (2). Applying this to d=2,d=3andd=n, it follows that 2·3·ndivides c, since these numbers are pairwise coprime. That is, k−1 divides c, as stated in (3). Finally, that (3) implies (1) directly follows from Proposition 3.4.  Needless to say, the same proof tools yield the same equivalences under this set of hypotheses: gcd(n, 30) = 1, n≥5andk=30n+ 1; or, for that matter, under the set of hypotheses gcd(n, 210) = 1, n≥7andk= 210n+1;andsoon. 4. Bounds and exact values In this section, we define new numbers S∗ k(n) which are smaller and easier to determine than Sk(n). We then show how they provide a lower bound to Rk(n, c), and we give an estimate for them. Finally, we use them to obtain a new shorter proof for Schaal’s formula on R2(3,c), exact formulae for R3(3,c)andR4(3,c), and sharper bounds in some other cases. 4.1. The numbers S∗ k(n).Before defining the S∗ k(n) proper, we introduce and generalize some terminology from additive number theory. Given nonempty sets A1,A 2of integers, their sumset A1+A2is defined as A1+A2={x1+x2|x1∈A1,x 2∈A2}. In particular, if A2={c}is a singleton, then A1+A2={x+c|x∈A1};itis the translate of A1by c, and will be denoted by A1+cinstead of A1+{c}.If A1=A2=A,thenwedenote2A=A+A, and more generally, for any integer k≥1, we denote by kA the k-fold sumset of Awith itself, i.e., kA =A+···+A   k ={x1+···+xk|xi∈Afor all 1 ≤i≤k}. License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use ON THE n-COLOR RADO NUMBER FOR x1+x2+···+xk+c=xk+1 2055 AsetAof integers is said to be sum-free if A∩2A=∅. As a generalization well-suited to our purposes here, and with k,c integers with k≥1, we shall say that Ais (kX +c)-free if (kA +c)∩A=∅. More generally, given a set Cof integers, we shall say that Ais (kX +C)-free if it is (kX +c)-free for all c∈C, or equivalently, if (kA +C)∩A=∅. Clearly, for c∈Z,thesetAis (kX +c)-free if and only if it contains no solution to the equation (5) x1+···+xk+c=xk+1 with x1,...,x k+1 ∈A. Thus, the n-color Rado number Rk(n, c) may equivalently be described as the smallest integer N, if it exists, or ∞if not, such that for every n-coloring of [1,N], at least one of the color classes Ain [1,N] fails to be (kX +c)-free. We are now in a position to define the S∗ k(n). Definition 4.1. Let n, k be positive integers with k≥2. Denote by S∗ k(n) the least integer Nsuch that, for every n-coloring of [1,N], there exists a monochromatic solution (x1,...,x k+1) to the equation (6) x1+···+xk+s=xk+1 for some s∈[−k+2,1]. Equivalently, let I=[−k+2,1]. Then S∗ k(n)is the least integer Nsuch that, for every n-coloring of [1,N], at least one of its color classes fails to be (kX +I)-free. Indeed, a set Ais (kX +I)-freeifandonlyifitis(kX +s)-free for all s∈I,or equivalently if, for all s∈I, it contains no solution to equation (6). It directly follows from the definitions that S∗ k(n)≤min c∈[−k+2,1] Rk(n, c). In particular, at c=0,wehaveS∗ k(n)≤Sk(n). 4.2. Bounding Rk(n, c)with S∗ k(n).Ourfirstresultconstructsa(kX +c)-free set Afrom a (kX +I)-free set B,whereI=[−k+2,1]. This will then be used to bound Rk(n, c)intermsofS∗ k(n). Notation 4.2.For a subset B⊆Zand a positive integer λ,wedenote λ·B={λy |y∈B}. The dot here is important since it helps distinguish λ·Bfrom the λ-fold sumset λB =B+···+B. Lemma 4.3. Let k, c be integers such that k≥2and c≥0.LetB⊆Zbe a (kX +I)-free subset, where I=[−k+2,1].Let A=(c+k−1) ·B+[−(c+k−2),0]. Then Ais (kX +c)-free. License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use 2062 S. D. ADHIKARI ET AL. 5.3. Seeking R2(4,c)by computer. Having fixed c≥0, we seek successive integers Msuch that [1,M] admits a 4-coloring all of whose color classes are (2X+c)-free; or equivalently, such that no triplet of the form {i, j, i +j+c}, with 1 ≤i≤M−cand i≤j≤M−i−c, is monochromatic. When the largest possible such Mis found, we are done: R2(4,c)=M+1. We now reformulate this problem as a Boolean satisfiability problem [6]. We proceed as follows. First, any 4-coloring of [1,M] may be viewed as a function Δ: [1,M]−→ { 0,1}2. By setting Δ(i)=(xi,x i+M) for all i∈[1,M], this 4-coloring may be represented by 2Mbinary variables x1,...,x 2Mwith values in {0,1}. We now view 0 and 1 as representing the Boolean values False and True, respectively. This allows us to use the logical operators AND, OR and NOT, denoted respectively by ∧,∨and ¬,ontheset{0,1}, with the purpose of translating the nonequality of elements by the validity of some associated logical formula. Indeed, for any x, y ∈{0,1},wehave (14) x=y⇐⇒ (x∨y)∧(¬x∨¬y)isTrue, as readily checked. It is easy to similarly translate the non-equality of two given colors in {0,1}2,sincefor(x1,y 1),(x2,y 2)∈{0,1}2,wehave (x1,y 1)=(x2,y 2)⇐⇒ x1=x2or y1=y2. Let us go back to our generic 4-coloring Δ: [1,M]−→ { 0,1}2 represented by the Boolean variables x1,...,x 2M. Given an arbitrary subset A⊆ [1,M], we may associate to A, in the way described above, a logical formula λ(A) in the variables x1,...,x 2M, in such a way that Afails to be monochromatic if and only if λ(A)is True. Therefore, given a family of subsets A1,...,A r⊆[1,M], prohibiting all of them to be monochromatic admits the following Boolean translation: (15) no Aiis monochromatic ⇐⇒ r  i=1 λ(Ai)isTrue. Now, applying this translation to the above-mentioned set of triplets, namely the subsets {i, j, i +j+c}⊆[1,M]with1≤i≤M−cand i≤j≤M−i−c,we obtain by (15) a system of logical formulas that can be simultaneously satisfied if and only if [1,M] admits a 4-coloring all of whose color classes are (2X+c)-free. Fixing successive values of M, we feed the associated system to a SAT solver, which will then attempt to say whether that system is satisfiable or not. As long as it is, we increase M. When, for some M0, we reach nonsatisfiability as an output, we know we are done: R2(4,c)=M0. 5.4. Exact values of R2(4,c)for c≤6.Applying the above method, we have obtained, by computer, the following exact value of the Rado numbers R2(4,c)for 0≤c≤6. Theorem 5.8. We have R2(4,0) = 40 ·0+45 = 45, R2(4,1) = 40 ·1+43 = 83,and R2(4,c)=40·c+41 for2≤c≤6. License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use ON THE n-COLOR RADO NUMBER FOR x1+x2+···+xk+c=xk+1 2063 Proof. The value R2(4,0) = 45 is due to [2]. A 4-coloring of [1,82] with (2X+1)-free color classes, implying R2(4,1) ≥83, is given by the following 4 color classes: {1,2,15,16,21,22,28,29,35,36,47,54,55,61,62,67,68,81,82}, {3,4,5,6,17,18,19,20,33,34,49,50,63,64,65,66,77,78,79,80}, {23,24,25,26,27,37,38,39,40,41,42,43,44,45,46,56,57,58,59,60}, {7,8,9,10,11,12,13,14,30,31,32,48,51,52,53,69,70,71,72,73,74,75,76}, thereby improving the lower bound R2(4,1) ≥81 given by Proposition 4.4 and the value S∗ 2(4) = 41 of Proposition 5.1. For 2 ≤c≤6, the lower bound is achieved by Proposition 4.4, and is revealed to be sharp by computations using the SAT solver March [9]. The running times on a standard desktop computer were as follows: Values of c R2(4,c)Time in seconds c=1 83 13 c=2 121 50 c=3 161 1260 c=4 201 2810 c=5 241 9270 c=6 281 593000  5.5. Conclusions and open problems. Combined with a separate forthcoming paper establishing the finiteness of R5(3,2) and R6(4,1), Conjecture 1.2 turns out to be true for k≤7. It remains to settle it in general. The smallest open case is R8(6,1), conjectured to be finite. In addition, in view of the above determination of R2(4,c)forc≤6, it is natural to conjecture that the formula R2(4,c)=40c+41 also holds for c≥7. Is it true or not? Along the same line, we are also interested in determining exact values or sharper bounds for R2(5,c). References [1] H. L. Abbott and D. Hanson, A problem of Schur and its generalizations,ActaArith.20 (1972), 175–187. MR0319934 (47 #8475) [2] L.D.Baumert,Sum-free sets, J.P.L. Research Summary 36-10, 16–18, (1961). [3] S. A. Burr and S. Loo, On Rado number I,Preprint. [4] S. A. Burr and S. Loo, On Rado number II,Preprint. [5] A. Beutelspacher and W. Brestovansky, Generalized Schur numbers, Combinatorial Theory (Schloss Rauischholzhausen, 1982), Lecture Notes in Math., vol. 969, Springer, Berlin-New York, 1982, pp. 30–38. MR692232 (84f:10019) [6] S. Eliahou, J. M. Mar´ın,M.P.Revuelta,andM.I.Sanz,Weak Schur numbers and the search for G. W. Walker’s lost partitions, Comput. Math. Appl. 63 (2012), no. 1, 175–182, DOI 10.1016/j.camwa.2011.11.006. MR2863489 [7] G. Exoo, A lower bound for Schur numbers and multicolor Ramsey numbers of K3, Electron. J. Combin. 1(1994), Research Paper 8 (electronic). MR1293398 (95k:05122) [8] H. Fredricksen and M. M. Sweet, Symmetric sum-free partitions and lower bounds for Schur numbers, Electron. J. Combin. 7(2000), Research Paper 32 (electronic). MR1763971 (2000m:05228) [9] M. Heule, http://www.st.ewi.tudelft.nl/sat/, March RW. SAT Competition 2011 (2011). [10] H. Wan, Upper bounds for Ramsey numbers R(3,3,··· ,3) and Schur numbers,J.Graph Theory 26 (1997), no. 3, 119–122, DOI 10.1002/(SICI)1097-0118(199711)26:3119::AIDJGT13.3.CO;2-1. MR1475891 (98f:05114) License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use 2064 S. D. ADHIKARI ET AL. [11] S. Jones and D. Schaal, Two-color Rado numbers for x+y+c=kz, Discrete Math. 289 (2004), no. 1-3, 63–69, DOI 10.1016/j.disc.2004.06.022. MR2106029 (2005g:05149) [12] W. Kosek and D. Schaal, Rado numbers for the equation m−1 i=1 xi+c=xm, for negative values of c, Adv. in Appl. Math. 27 (2001), no. 4, 805–815, DOI 10.1006/aama.2001.0762. MR1867934 (2002i:05117) [13] R. Rado, Studien zur Kombinatorik (German), Math. Z. 36 (1933), no. 1, 424–470, DOI 10.1007/BF01188632. MR1545354 [14] S. P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. 1(1994), Dynamic Survey 1, 30 pp. (electronic). MR1670625 (99k:05117) [15] K. Rendall Truman and D. Schaal, Three-color Rado numbers for x1+x2+c=x3for negative values of c, Proceedings of the Thirty-Seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 183 (2006), 5–10. MR2311465 (2007m:05224) [16] A. Robertson, Difference Ramsey numbers and Issai numbers, Adv. in Appl. Math. 25 (2000), no. 2, 153–162, DOI 10.1006/aama.2000.0678. MR1780763 (2001f:05098) [17] A. S´anchez-Flores, An improved upper bound for Ramsey number N(3,3,3,3; 2), Discrete Math. 140 (1995), no. 1-3, 281–286, DOI 10.1016/0012-365X(93)E0187-9. MR1333725 (96b:05121) [18] I. Sanz Dom´ınguez, N´umeros de Schur y Rado, Ph. Thesis, Universidad de Sevilla, 2010. [19] D. Schaal, On generalized Schur numbers, Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1993), Congr. Numer. 98 (1993), 178–187. MR1267352 (95f:05113) [20] D. Schaal, Afamilyof3-color Rado numbers, Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995), Congr. Numer. 111 (1995), 150–160. MR1369349 (96h:05006) [21] D. Schaal and D. Vestal, Rado numbers for x1+x2+···+xm−1=2xm, Proceedings of the Thirty-Ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 191 (2008), 105–116. MR2489815 (2010f:05184) [22] I. Schur, Uber die Kongruenz xm+ym≡zm(mod p), Jahresber. Deutsch. Math.-Verein. 25, 114–117 (1916). [23] E. G. Whitehead Jr., The Ramsey number N(3,3,3,3; 2), Discrete Math. 4(1973), 389–396. MR0314678 (47 #3229) [24] ˇ S. Zn´am, Generalisation of a number-theoretical result,Mat.-Fyz.˘ Casopis Sloven. Akad. Vied 16 (1966), 357–361. MR0209175 (35 #78) Harish-Chandra Research Institute, Chhathnag Road, Jhunsi, Allahabad-211 019, India E-mail address:[email protected] Escuela T´ ecnica Superior de Arquitectura, Departamento de Matem´ atica Aplicada I, Avenida de la Reina Mercedes 2, C.P. 41012 Sevilla, Spain E-mail address:[email protected] ULCO, LMPA J. Liouville, CS 80699 – 62228 Calais Cedex, France — and — CNRS, FR 2956, France E-mail address:[email protected] Escuela T´ ecnica Superior de Ingenier´ ıa de Edificaci´ on, Departamento de Matem´ atica Aplicada I, Avenida de la Reina Mercedes 4, C.P. 41012 Sevilla, Spain E-mail address:[email protected] Escuela T´ ecnica Superior de Ingenier´ ıa de Edificaci´ on, Departamento de Matem´ atica Aplicada I, Avenida de la Reina Mercedes 4, C.P. 41012 Sevilla, Spain E-mail address:[email protected] Escuela T´ ecnica Superior de Ingenier´ ıa de Edificaci´ on, Departamento de Matem´ atica Aplicada I, Avenida de la Reina Mercedes 4, C.P. 41012 Sevilla, Spain E-mail address:[email protected] License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use