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

On the n-Color Weak Rado Numbers for the Equation x1 + x2 + ··· + xk + c = xk +1 L. Boza, J.M.Marín, M.P.Revuelta, and M.I.Sanz Departamento de Matemática Aplicada I, Universidad de Sevilla, Avenida Reina Mercedes s/n, Sevilla, Spain KEYWORDS Schur numbers; sum-free sets; weak Schur numbers; weakly sum-free sets; Rado numbers; weak Rado numbers MATHEMATICS SUBJECT CLASSIFICATION C; D; -; A ABSTRACT For integers k,n,cwith k,n≥1,and c≥0, the n-color weak Rado number WRk(n,c)is defined as the least integer N, if it exists, such that for every n-coloring of the integer interval [1,N], there exists a monochromatic solution x1,...,xk,xk+1in that interval to the equation x1+x2+···+xk+c=xk+1, with xi= xj,wheni= j.If no such Nexists, then WRk(n,c)is defined as infinite. In this paper, we determine the exact value of some of these numbers for n=2andn=3, namely WR3(2,c)=5c+24, WR4(2,c)=6c+52 for all c≥0andWR2(3,c)=13c+22 for all c>0.Our method consists in translating the problem into a Boolean satisfiability problem, which can then be handled by a SAT solver or by backtrack programming in the language C. 1. Introduction For integers a≤b,weshalldenote[a,b]theinteger interval consisting of all t∈N+={1,2,...}such that a≤ t≤b.Afunction :[1,N]−→ { d1,...,dn}, where d1,...,dn∈N+represent different colors, is a n-coloring of the interval [1,N]. Given a n-coloring and the equation x1+···+ xk=xk+1in k+1variables,thenwesaythatasolution x1,...,xk,xk+1to the equation is monochromatic if and only if (x1)=(x2)=···=(xk+1). For integers k,n,cwith k,n≥1,and c≥0, the n-color weak Rado number WRk(n,c)is defined as the least integer N, if it exists, such that for every n-coloringoftheinte- ger interval [1,N], there exists a monochromatic solution x1,...,xk,xk+1in that interval to the equation x1+x2+···+xk+c=xk+1, with xi= xjwhen i= j.If no such Nexists, then WRk(n,c)is defined as infinite. 1.1. Schur numbers and weak Schur numbers AsetAof integers is called sum-free if it contains no elements x1,x2,x3∈Asatisfying x1+x2=x3,where x1,x2need not be distinct. It is called weakly sum-free if CONTACT M. P. Revuelta [email protected] Departamento de Matemática Aplicada I, Universidad de Sevilla, Avenida Reina Mercedes s/n, C.P.  Sevilla, Spain. it contains no pairwise distinct elements x1,x2,x3∈A satisfying x1+x2=x3. [Schur 16] proved that, given a positive integer n,there exists a greatest positive integer S2(n)=Nwith the property that the integer interval [1,N−1] can be partitioned into nsum-freesets. The numbers S2(n)are called Schur numbers. The current knowledge on these numbers for 1≤n≤7isgiveninTable 1. The exact value of S2(4)was obtained by [Baumert 61]. The lower and upper bounds on S2(5)are due to [Exoo 94]and[Sanz 10], respectively. Finally, the lower bounds on S2(6)and S2(7)were obtained by [Fredricksen and Sweet 00] by considering symmetric sum-free partitions. Many generalizations of Schur numbers have appeared sincetheirintroduction.WedenotebyWS2(n),thegreatest integer N, for which the integer interval [1,N− 1] can be partitioned into nweakly sum-free sets {A1,A2,...,An}. The numbers WS2(n)are called the weak Schur numbers.TheknownweakSchurnumbersaregiveninTable 2. ThecurrentstateofknowledgeconcerningWS2(n)is quite confused. The problem seems to have been first considered in [Walker 52], which is Walker’s solution to Problem E985 proposed a year earlier, in 1951, by Moser. Walker considered the cases n=3,4,and 5, and claimed the values WS2(3)=24,WS2(4)=67 andWS2(5)=197. Unfortunately,theshortaccountwrittenbyMoseronWalker’s Table . The first few Schur numbers S2(n). n     S2(n)161 ≤···≤306 ≥537 ≥1681 solution only gives suitable partitions of [1,23] for n= 3,andnodetailsatallforthecasesn=4and5. Walker’s claimed values of WS2(3)and WS2(4)were later confirmed by [Blanchard et al. 06]. The lower bound WS2(5)≥197 has been confirmed in [Eliahou et al. 12]. Whether equality holds in still an open problem. A lower bound on WS2(6)was obtained by [Eliahou et al. 12]and later improved to WS2(6)≥583 in [Eliahou 13]. 1.2. Rado numbers and weak Rado numbers In terms of coloring, the Schur number S2(n)[Schur 16] is the least positive integer Nsuch that for every n-coloring of [1,N], :[1,N]−→ { d1,...,dn}, where d1,...,dnrepresent ndifferent colors, there exists a monochromatic solution to the equation x1+x2=x3, such that (x1)=(x2)=(x3)where x1and x2need not be distinct. In 1933, [Rado 33,Rado 36] generalized the work of Schurtoarbitrarysystemsoflinearequations.Givenasystem of linear equations Land a natural number n,theleast integer N(if it exists) such that for every coloring of the integer interval [1,N]withncolors there is a monochromatic solution to L,iscalledthen-color Rado number for L.IfnosuchintegerNexists, then the n-color Rado number for the system Lis taken to be infinite. After those first results of Rado, very little progress has been obtained for some systems of linear equations. [Burr and Loo 92] were able to determine the 2-color Rado number for the equations x1+x2+c=x3and x1+x2= kx3for every integer cand for every positive integer k. In 1993, [Schaal 93] determined the 2-color Rado number Rk(2,c)for the equation x1+x2+···+xk+ c=xk+1.Healsoobtained[Schaal 95]the3-colorRado number R2(3,c)for the equation x1+x2+c=x3.There are several results due to Schaal and other authors concerning 2-color and 3-color Rado numbers for particular equations, see [Jones and Schaal 04], [Kosek and Schaal 01], [Rendall and Schaal 06], and other authors [Guo and Sun 08]. In addition, recently we have studied when Rk(n,c)isfiniteorinfiniteandwehaveobtainednew exact values [Adhikari 16,Adhikari 17]. Table . The first few weak Schur numbers WS2(n). n     WS2(n)≥197 ≥583 For every integer c≥0, n≥1, let WR2(n,c)be the least integer N(if it exists) such that, for every coloring of the integer interval [1,N]withncolors, there exists a monochromatic solution to the equation x1+x2+c= x3,wherex1= x2. The numbers WR2(n,c)are called the weak Rado numbers. The number WR2(n,c)can be defined equivalently as the greatest Nsuch that the integer interval [1,N−1] can be partitioned into nsets A1,A2,...,Anwhich are free of solutions to the equation x1+x2+c=x3with x1= x2. Recently,Schaaletal.[Flint 13]haveobtainedthe number WR2(2,c)for every integer c. 1.3. Contents In Section 2, we determine the exact value of the 3-color weak Rado number for the equation x1+x2+c=x3. Computational Theorem 2.1. For every c >0,wehave WR2(3,c)=13c+22. In Section 3, we verify the exact values of the 2-color weak Rado numbers for k=3,4. Computational Theorem 3.1. For every c ≥0,we have WR3(2,c)=∞if codd, 5c+24 if ceven. Computational Theorem 3.2. For every c ≥0,wehave WR4(2,c)=6c+52. In addition, we prove WR5(2,2)=109 and WR5(2,4)=123. These exact values were obtained in two independent ways. One of them, by transforming the problem into a Boolean satisfiability problem and solving it with a SAT solver [Heule 11], and the other one using backtrack programming in the language C [Helsgaun 95]. In Sections 4 and 5, the two computational procedures used in the proofs are shown. 2. Exact value of the weak Rado numbers WR2(3,c) In this section, we shall prove that WR2(3,c)=13c+22 for every positive integer c>0. 2.1. Lower bound We now prove the lower bound. Lemma 2.1. We have WR2(3,c)≥13c+22 for any integer c >0. Proof. Let c>0 be a positive integer. We shall prove WR2(3,c)≥13c+22. Let be a 3-coloring: :[1,13c+22] −→ { d1,d2,d3}, where d1,d2,d3represent 3 different colors. Let Ai= −1(di)for i=1,2,3thus[1,13c+22] =A1A2 A3. Consider the following partition of the integer interval [1,13c+21]: ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ A1=[1,c+2] ∪[3c+7,4c+7] ∪[9c+17,10c+17] ∪[12c+21,13c+21], A2=[c+3,3c+6] ∪[10c+18,12c+20], A3=[4c+8,9c+16]. Hence {A1,A2,A3}is a partition of [1,13c+21]. We now prove that for each i,1≤i≤3, if x1,x2∈Ai with x1= x2then x1+x2+c/∈Ai.Weassume,without any loss of generality, that x1<x2. Case 1: x1,x2∈A1 rIf x2≤c+2, then c+3≤x1+x2+c≤3c+3, therefore x1+x2+c/∈A1. rIf 3c+7≤x2≤4c+7then4c+8≤x1+x2+ c≤9c+13, therefore x1+x2+c/∈A1. rIf 9c+17 ≤x2≤10c+17, we have: –If x1≤c+2then10c+18 ≤x1+x2+c≤ 12c+19, therefore x1+x2+c/∈A1. –If 3c+7≤x1then 13c+24 ≤x1+x2+c, therefore x1+x2+c/∈A1. rIf x2≥12c+21 then x1+x2+c≥13c+22, therefore x1+x2+c/∈A1. Case 2: x1,x2∈A2and x1≥c+3 rIf x2≤3c+6, then 3c+7≤x1+x2+c≤7c+ 11, therefore x1+x2+c/∈A2. rIf x2≥10c+18 then 12c+21 ≤x1+x2+c, therefore x1+x2+c/∈A2. Case 3: x1,x2∈A3 Since 9c+17 ≤x1+x2+c,thenx1+x2+c/∈A3. 2.2. Upper bound Let c>0 be a positive integer. We shall prove WR2(3,c)≤13c+22. This upper bound was establishedinthedoctoralthesis[Sanz 10]throughan exhaustive analysis of nearly 500 cases. We provide here asketchofthatproof,tothisend,weshallprovethat for every 3-coloring of the integer interval [1,13c+22], thereexistsamonochromaticsolutiontotheequation x1+x2+c=x3,x1= x2. Assume, for a contradiction, that there exists a 3- coloring: :[1,13c+22] −→ { d1,d2,d3}, where d1,d2,d3represent three different colors, without any monochromatic solution of the equation x1+x2+ c=x3,x1= x2. Let Ai=−1(di)for i=1,2,3thus[1,13c+22] = A1A2A3. We considered five main cases, depending on the colorsassignedtothenumbers1,2and3: Case 1. A1⊇{1,2,3}. Case 2. A1⊇{1,2}and A2⊇{3}. Case 3. A1⊇{1,3}and A2⊇{2}. Case 4. A1⊇{1}and A2⊇{2,3}. Case 5. A1⊇{1},A2⊇{2}and A3⊇{3}. Given a subset X⊆[1,13c+22], we denote f(X)=(XX+c)∩[1,13c+22] =({x1+x2+c|x1,x2∈X,x1= x2}) ∩[1,13c+22]. By hypothesis on ,for1≤i≤3, we have Ai∩f(Ai)=∅.(1) The proof rests on the following claims, which are both direct consequences of (1). For every integers i,j,ksuch that {i,j,k}={1,2,3},wehave: rClaim I. f(Ai)∩f(Aj)⊆Ak. rClaim II. f(Ai)∩f(Aj)∩f(Ak)=∅ WenowstartouranalysiswithCase1andexplorevar- ious subcases. Case 1: A1⊇{1,2,3} As c+3=1+2+c,withoutanylossofgenerality,we may assume that (c+3)=d2. In addition, since c+ 4=1+3+cthen (c+4)= d1, and therefore (c+ 4)=d2or (c+4)=d3. Case 1.1: (c+4)=d2 A1⊇{1,2,3},A2⊇{c+3,c+4}. Since {3c+7, c+3, c+4} would be a monochromatic solution in A2,wemusthave(3c+7)=d1or (3c+ 7)=d3. Case 1.1.1: (3c+7)=d1 A1⊇{1,2,3,3c+7},A2⊇{c+3,c+4}. As {4c+10, 3c+7, 3} would be a monochromatic solution in A1,wemusthave(4c+10)=d2or (4c+ 10)=d3. Case 1.1.1a: (4c+10)=d2. Hence A1⊇{1,2,3,3c+7},A2⊇{c+3,c+4, 4c+10}.We now show 2c+6∈A3.Indeed, we cannot have 2c+6∈A1,forotherwisewewouldhave 3c+7∈A1∩f({1,2c+6})⊆A1∩f(A1),acontradiction since A1∩f(A1)=∅ by (1). Similarly, we cannot have 2c+6∈A2,forotherwisewewouldhave 4c+10 ∈A2∩f({c+4,2c+6})⊆A2∩f(A2),acontradictionagain.Itfollowsthat2c+6∈A3, i.e. (2c+ 6)=d3,asclaimed. The element 2c+5doesnotbelongtoA1, since otherwise 3c+7∈A1∩f({2,2c+5})⊆A1∩f(A1)=∅. Hence (2c+5)=d2or (2c+5)=d3. Case 1.1.1a1: (2c+5)=d2 Hence A1⊇{1,2,3,3c+7},A2⊇{c+3,c+4, 4c+10,2c+5}and A3⊇{2c+6}. We now show 4c+9∈A3.Infact,wecannothave4c+9∈A1,forotherwise we would have 4c+9∈A1∩f({2,3c+7})⊆ A1∩f(A1), a contradiction since A1∩f(A1)=∅ by (1). The same way, the element 4c+9doesnotbelongto A2,forotherwise4c+9∈A2∩f({c+4,2c+5})⊆ A2∩f(A2), a contradiction again. It follows that 4c+9∈A3, i.e. (4c+9)=d3,asclaimed. Therefore, A1⊇{1,2,3,3c+7},A2⊇{c+3,c+ 4,4c+10,2c+5},and A3⊇{2c+6,4c+9}.Wenow show 7c+15 ∈A1. Indeed, it does not hold that 7c+15 ∈A2,forotherwisewewouldhave7c+15 ∈ A2∩f({4c+10,2c+5})⊆A2∩f(A2), a contradiction since A2∩f(A2)=∅by (1). Similarly, we cannot have 7c+15 ∈A3,forotherwisewewouldhave7c+ 15 ∈A3∩f({2c+6,4c+9})⊆A3∩f(A3), a contradiction again. It follows that 7c+15 ∈A1, i.e. (7c+ 15)=d1,asclaimed. Accordingly, A1⊇{1,2,3,3c+7,7c+15},A2⊇ {c+3,c+4,4c+10,2c+5},and A3⊇{2c+6,4c+ 9}.Wenowshow6c+14 ∈A3.Certainly,wecannothave 6c+14 ∈A1,forotherwisewewouldhave7c+15 ∈ A1∩f({1,6c+14})⊆A1∩f(A1), a contradiction since A1∩f(A1)=∅by (1). Analogously, the element 6c+14 does not belong to A2,forotherwisewewould have 6c+14 ∈A2∩f({c+4,4c+10})⊆A2∩f(A2), a contradiction again. It follows that 6c+14 ∈A3, i.e. (6c+14)=d3,asclaimed. Hence, A1⊇{1,2,3,3c+7,7c+15},A2⊇{c+ 3,c+4,4c+10,2c+5},and A3⊇{2c+6,4c+9, 6c+14}. We now show c+5/∈A1,c+5/∈A2and c+5/∈A3. In fact, it does not hold that c+5∈A1, for otherwise we would have c+5∈A1∩f({2,3})⊆ A1∩f(A1), a contradiction since A1∩f(A1)=∅ by (1). We cannot have c+5∈A2, for otherwise we would have 4c+10 ∈A2∩f({2c+5,c+5})⊆A2∩f(A2), a contradiction since A2∩f(A2)=∅by (1). We cannot have c+5∈A3,forotherwisewewouldhave6c+14 ∈ A3∩f({4c+9,c+5})⊆A3∩f(A3), a contradiction since A3∩f(A3)=∅by (1). This subcase is over. Here is an outline of the proof in Case 1: Case 1.1 ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ (3c+7)=d1 ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ (4c+10)=d2(2c+5)=d2 (2c+5)=d3 (4c+10)=d3(4c+9)=d2 (4c+9)=d3 (3c+7)=d3⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ (c+5)=d2(3c+9)=d1 (3c+9)=d3 (c+5)=d3(5c+12)=d1 (5c+12)=d2 Case 1.2 ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ (c+5)=d1 ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ (3c+8)=d1(4c+11)=d2 (4c+11)=d3 (3c+8)=d3(5c+12)=d1 (5c+12)=d2 (c+5)=d3⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ (3c+9)=d1(4c+10)=d2 (4c+10)=d3 (3c+9)=d2(5c+12)=d1 (5c+12)=d3 The other four cases were obtained in a similar way. We now present two independent computational proofs of the upper bound. Computational Lemma 2.1. Let c>1andXc= {1,2,3,c+2,c+3,c+4,2c+4,2c+5,2c+6,3c+ 5,3c+6,3c+7,4c+7,4c+8,4c+9,5c+9,5c+ 10,5c+11,6c+10,6c+11,6c+12,7c+13,8c+14, 8c+15,9c+16,9c+17,10c+18,10c+19,11c+20, 12c+21,13c+22}then: (1) We have Xc⊆[1,13c+22] and |Xc|=31. (2) For every partition of Xcinto three subsets A1,A2,A3,someAicontains a monochromatic solution of x1+x2+c=x3,x1= x2. Proof. 1. This is trivial. 2. We have checked the result transforming the problem into a Boolean satisfiability problem and solving it with a SAT solver [Heule XX]andusing CBack [Helsgaun 95].  Computational Lemma 2.2. For c=1, let X= {1,2,...,18,20,22,25,26,28,29,31,33,35}then: 1. We have X⊆[1,35]. 2. For every partition of Xinto three subsets A1,A2,A3,someAicontains a monochromatic solution of x1+x2+c=x3,x1= x2. The proof is similar to Lemma 2.1. In Section 4, the proof of the following result is given in detail. Computational Theorem 2.1. For every c>0,we have WR2(3,c)=13c+22. 3. Exact values of weak Rado numbers WRk(2,c) for some k>2 In this section, we prove that WR3(2,c)=5c+24 if cis even, WR4(2,c)=6c+52, WR5(2,2)=109,and WR5(2,4)=123.In addition, we formulate Corollary 3.1,whichrelatesWRk(2,c)and a lower bound on the weak Schur number WSk(2),leadingustoformulate Conjecture 3.1. 3.1. The weak Rado numbersWR3(2,c) For c=0, [Blanchard et al. 06]obtainedtheweakSchur number WS3(2)=WR3(2,0)=24. A partition which is free of monochromatic solutions to the equation x1+x2+x3+c=x4is A1=[1,5] ∪[21,23] and A2= [6,20]. For c≥0andodd,WR3(2,c)≥R3(2,c)=∞[Schaal 93]. Letusfirstconsiderthelowerboundforanyc≥0and even. Lemma 3.1. We have WR3(2,c)≥5c+24 for any c ≥0 and even. Proof. For every even integer c≥0, it is easy to verify that the 2-coloring :[1,5c+23] −→ { d1,d2}, where d1,d2represent 2 different colors, defined by (x)=⎧ ⎨ ⎩ d1if 1 ≤x≤c+5, d2if c+6≤x≤4c+20, d1if 4c+21 ≤x≤5c+23 has no monochromatic solutions to the equation x1+ x2+x3+c=x4such that xi= xjwhen i= j. Computational Lemma 3.1. We have WR3(2,2)=34. A partition which is free of monochromatic solutions to the equation x1+x2+x3+c=x4is A1=[1,7] ∪ [29,33] and A2=[8,28]. Inordertoprovetheupperbounds,weshallusethe following result: Computational Lemma 3.2. Let c≥4 and even. If l=c/2, then the set Yl={1,2,3,4,2+l,3+l,4+ l,3+2l,4+2l,5+2l,6+2l,7+2l,8+2l,6+3l, 7+3l,8+3l,6+4l,9+4l,11 +5l,10 +6l,12 +6l, 13 +7l,14 +8l,15 +8l,16 +8l,18 +8l,21 +8l, 23 +10l,24 +10l}verifies: 1. We have Yl⊆[1,24 +10l]. 2. For every partition of Ylinto two subsets A1,A2, some Aicontains a monochromatic solution of x1+x2+x3+c=x4,xi= xj,withi= j. In the proof of Lemma 3.2, we proceed similarly to Lemma 2.1. Therefore, we conclude with the following result: Computational Theorem 3.1. For every c≥0, we have WR3(2,c)=∞if codd, 5c+24 if ceven. 3.2. The weak Rado numbersWR4(2,c) For c=0, the weak Schur number WS4(2)= WR4(2,0)=52 was obtained [Sanz 10]. A partition which is free of monochromatic solutions to the equation x1+x2+x3+x4+c=x5is A1=[1,9] ∪[46,51] and A2=[10,45]. Wenowconsiderthelowerboundforanyc≥0. Lemma 3.2. We have WR4(2,c)≥6c+52 for any c ≥0. Proof. For every integer c≥0, it is easy to verify that the 2-coloring :[1,6c+51] −→ { d1,d2} defined by (x)=⎧ ⎨ ⎩ d1if 1 ≤x≤c+9, d2if c+10 ≤x≤5c+45, d1if 5c+46 ≤x≤6c+51 has no monochromatic solutions to the equation x1+ x2+x3+x4+c=x5such that xi= xjwhen i= j. In order to prove the opposite inequality, we shall use the following result: Computational Lemma 3.3. Let c≥1. The set Zc={1,2,3,4,5,6,8,c+9,c+10,c+11,c+12, c+13,c+14,c+15,2c+16,2c+17,2c+18,2c+ 19,2c+20,2c+21,2c+22,2c+24,3c+32,4c+33, 5c+43,5c+44,5c+45,5c+46,6c+52}verifies: 1. Zc⊆[1,6c+52]. 2. For every partition of Zcinto two subsets A1,A2, some Aicontains a monochromatic solution of x1+x2+x3+x4+c=x5,xi= xj,withi= j. In the proof of Lemma 3.3, we use similar reasonings to those established in Lemma 2.1 and Lemma 3.2. Therefore, we conclude with the following result: Computational Theorem 3.2. For every c≥0, we have WR4(2,c)=6c+52. 3.3. The weak Rado numbersWR5(2,2)and WR5(2,4) The weak Rado numbers WR5(2,2)and WR5(2,4) have been obtained through backtrack programming [Helsgaun 95]andbytransformingtheproblemintoa Boolean satisfiability problem and solving it with a SAT solver. In the Sections 4.4,5.4,and5.5, the results are shown. InthecaseofWR5(2,2), backtrack programming shows three partitions, which are free of monochromatic solutions to the equation x1+x2+x3+x4+2=x5, xi= xj,withi= j.Theseare A1=[1,16] ∪[97,108],A2=[17,96]. A1=[1,20] ∪[94,108],A2={2}∪[21,93]. A1={1}∪[21,92],A2=[2,20] ∪[93,108]. Therefore, we have that 109 is the lower bound of WR5(2,2).InSection 4.4,weshowthatWR5(2,2)≤109. In the case of WR5(2,4),apartitionfreeofmonochromatic solutions to the equation x1+x2+x3+x4+4= x5,xi= xj,withi= j,is: A1=[1,18] ∪[109,122],A2=[19,108]. Therefore, we have that 123 is the lower bound of WR5(2,4).InSection 5.4,weshowthatWR5(2,4)≤123. Hence, we conclude with the following results: Computational Theorem 3.3. We have WR5(2,2)=109. Computational Theorem 3.4. We haveWR5(2,4)=123. 3.4. Weak Schur numbersWS5(2)and lower bounds In this subsection, we obtain the weak Schur number WS5(2)=101 and we show a lower bound for the weak Schur numbers WSk(2). To obtain the lower bound WS5(2)≥101, the following partition of [1,100] is considered A1={1}∪[20,86] and A2=[2,19] ∪[87,100]. In order to obtain the upper bound WS5(2)≤101, we shall use the following result: Computational Lemma 3.4. The set U=[1,7] ∪ {9,11,13}∪[15,17] ∪[19,23] ∪[25,27] ∪{29,31,35, 39}∪[43,45] ∪{51,75,87,101}⊆[1,101] verifies that for every partition of Uinto two subsets A1,A2,some Aicontains a monochromatic solution of x1+x2+x3+ x4+x5=x6,xi= xj,withi= j. In the proof of Lemma 3.4, we use similar reasonings to those established in Lemma 2.1 and Lemma 3.2. Therefore, we conclude with the following result: Computational Theorem 3.5. We have WS5(2)=101. Here,belowcanbeseeinganewlowerboundforthe weak Schur numbers WSk(2). Lemma 3.3. We have WSk(2)≥(k+2)Tk−2k, with Tk=(1+k) 2k. Proof. It is easy to verify that the 2-coloring :[1,(k+2)Tk−2k−1] −→ { d1,d2} defined by (x)=⎧ ⎨ ⎩ d1if 1≤x≤Tk−1, d2if Tk≤x≤(k+1)Tk−k−1, d1if (k+1)Tk−k≤x≤(k+2)Tk−2k−1 has no monochromatic solution to the equation x1+x2+ ···+xk=xk+1such that xi= xjwhen i= j. Consider the lower bound LWS k(2)=(k+2)Tk−2k. We formulate the following Corollaries that relate the weak Rado numbers WRk(2,c)with the lower bound LWS k(2). Corollary3.1. Let c be a integer with c ≥0and k =2,3,4. Then, WRk(2,c)=(k+2)c+LWS k(2). Corollary 3.2. Let c =2or c =4and k =5.Then, WRk(2,c)=(k+2)c+LWS k(2). The exact values WR2(2,c), WR3(2,c), WR4(2,c), WR5(2,2), and WR5(2,4)have been obtained. All of them verify the following Conjecture 3.1. Conjecture 3.1. Let cand kbe integers with c≥0andk≥ 2, we have WRk(2,c)=(k+2)c+LWS k(2),whencor k is even. 4. Reformulation as a SAT problem Our idea for constructing the above partitions is to express the corresponding combinatorial constraints as Boolean satisfiability problems, to be then fed into a SAT solver. See [Dransfield et al. 04,Eliahou et al. 12,Herwig et al. 07,Kouril and Paul 08,Robilliard et al. 10]forearlier successful uses of SAT solvers in combinatorial number theory. The specific SAT solver used here, is the March rw, the gold medal winner of the 2011 International SAT Competition [Heule XX]. Recall that a logical expression over Boolean variables x1,...,xnis said to be satisfiable if there is an assignment of the xi’s to True or False in such a way that the value evaluates to True. 4.1. Seeking WR2(3,c)by computer Let c>1andconsiderthesetXcof Lemma 2.1.That is, Xc={1,2,3,c+2,c+3,c+4,2c+4,2c+5,2c+ 6,3c+5,3c+6,3c+7,4c+7,4c+8,4c+9,5c+9, 5c+10,5c+11,6c+10,6c+11,6c+12,7c+13, 8c+14,8c+15,9c+16,9c+17,10c+18,10c+19, 11c+20,12c+21,13c+22}. Let cbe a 3-coloring of [1,13c+22]: c:[1,13c+22] −→ { d1,d2,d3}, and let X∗={(a,b):ac +b∈Xcfor any c≥1}, i.e. X∗={(0,1), (0,2), (0,3), (1,2), (1,3), (1,4), (2,4), (2,5), (2,6), (3,5), (3,6), (3,7), (4,7), (4,8), (4,9), (5,9), (5,10), (5,11), (6,10), (6,11), (6,12), (7,13), (8,14), (8,15), (9,16), (9,17), (10,18), (10,19), (11, 20), (12,21), (13,22)}. For any (a,b)∈X∗,weconsidertwoBooleanvariables φ((a,b)) and ψ((a,b)) defined as follow: φ((a,b)) =True if c(ac +b)=d1or d2, False if c(ac +b)=d3. ψ((a,b)) =True if c(ac +b)=d1or d3, False if c(ac +b)=d2. Thus, for any n∈X∗we have that φ(n)is True or ψ(n)is True. Let S={(n1,n2,n3)|ni=(ai,bi)∈X∗,verifying that a1+b1<a2+b2,a1+a2+1=a3,b1+b2= b3}. For any s=(n1,n2,n3)∈S,weconsiderthree clauses: p(s)=(¬φ(n1)∨¬ψ(n1)∨¬φ(n2)∨¬ψ(n2) ∨¬φ(n3)∨¬ψ(n3)), q(s)=(¬φ(n1)∨ψ(n1)∨¬φ(n2)∨ψ(n2) ∨¬φ(n3)∨ψ(n3)), and r(s)=(φ(n1)∨¬ψ(n1)∨φ(n2)∨¬ψ(n2) ∨φ(n3)∨¬ψ(n3)). Then, p(s)is satisfiable if and only if c(n)= d1for some n∈s,q(s)is satisfiable if and only if c(n)= d2for some n∈sand r(s)is satisfiable if and only if c(n)= d3for some n∈s,thusp(s)∧q(s)∧r(s)aresatisfiableifand only if cdoes not induce on sa monochromatic solution of the equation x1+x2+c=x3. Let C= s∈S (p(s)∧q(s)∧r(s)) and D= n∈X∗ (φ(n)∨ψ(n)). Clearly, C∧Dis satisfiable if and only if the restriction of cto Xcis a 3-coloring without monochromatic solution of the equation. The SAT-Solver shows that C∧Dis not satisfiable, therefore there does not exist a 3-coloring of the sets Xcand [1,13c+22] without monochromatic solution. Thus, WR2(3,c)≤13c+22. 4.2. Seeking WR3(2,c)by computer Let c=2l≥4andthesetYlof Lemma 3.2.Thatis,Yl= {1,2,3,4,2+l,3+l,4+l,3+2l,4+2l,5+2l,6+ 2l,7+2l,8+2l,6+3l,7+3l,8+3l,6+4l,9+4l, 11 +5l,10 +6l,12 +6l,13 +7l,14 +8l,15 +8l, 16 +8l,18 +8l,21 +8l,23 +10l,24 +10l}. Let lbe a 2-coloring of [1,24 +10l], l:[1,24 +10l]−→ { d1,d2}, and let Y∗={(a,b):al +b∈Ylfor any l≥2}, i.e. Y∗={(0,1), (0,2), (0,3), (0,4), (1,2), (1,3), (1,4), (2,3), (2,4), (2,5), (2,6), (2,7), (2,8), (3,6), (3,7), (3,8), (4,6), (4,9), (5,11), (6,10), (6,12), (7,13), (8, 14), (8,15), (8,16), (8,18), (8,21), (10,23), (10,24)}. For any (a,b)∈Y∗,weconsideraBooleanvariable φ((a,b)) defined as follows: φ((a,b)) =True if l(2al +b)=d1, False if l(2al +b)=d2. Let S={(n1,...,n4)|ni=(ai,bi)∈Y∗,verifying that 4a1+b1<4a2+b2<4a3+b3,a1+a2+a3+ 2=a4,b1+b2+b3=b4}For any s=(n1,...,n4)∈ S,weconsidertwoclauses: p(s)=(φ(n1)∨φ(n2)∨φ(n3)∨φ(n4)) and q(s)=(¬φ(n1)∨¬φ(n2)∨¬φ(n3)∨¬φ(n4)). Then p(s)is satisfiable if and only if l(n)= d2for some n∈sand q(s)is satisfiable if and only if l(n)= d1for some n∈s,thusp(s)∧q(s)are satisfiable if and only if ldoes not induce on sa monochromatic solution of the equation x1+x2+x3+x4+c=x5. Let C= s∈S (p(s)∧q(s)). Clearly Cis satisfiable if and only if the restriction of l to Ylis a 2-coloring without monochromatic solution of the equation. The SAT-Solver shows that Cis not satisfiable, therefore there does not exist a 2-coloring of the sets Yl and [1,24 +10l] without monochromatic solution. Thus WR3(2,2l)≤24 +10l. 4.3. Seeking WR4(2,c)by computer Let Zcbe the set of Lemma 3.3.Thatis,Zc= {1,2,3,4,5,6,8,c+9,c+10,c+11,c+12,c+13, c+14,c+15,2c+16,2c+17,2c+18,2c+19,2c+ 20,2c+21,2c+22,2c+24,3c+32,4c+33,5c+ 43,5c+44,5c+45,5c+46,6c+52}Let cbe a 2- coloring of [1,6c+52], c:[1,6c+52] −→ { d1,d2} and let Z∗={(a,b):ac +b∈Zcfor any c≥0}, i.e. Z∗={(0,1), (0,2), (0,3), (0,4), (0,5), (0,6), (0,8), (1,9), (1,10), (1,11), (1,12), (1,13), (1,14), (1,15), (2,16), (2,17), (2,18), (2,19), (2,20), (2,21), (2,22), (2,24), (3,32), (4,33), (5,43), (5,44), (5,45), (5,46), (6,52)}.Forany(a,b)∈Z∗we consider a Boolean variable φ((a,b)) defined as follow: φ((a,b)) =True if c(ac +b)=d1, False if c(ac +b)=d2. Let S ={(n1,...,n5)|ni=(ai,bi)∈Z∗,verifying that b1<b2<b3<b4,a1+a2+a3+a4+1= a5,b1+b2+b3+b4=b5}. For any s=(n1,...,n5)∈S,weconsidertwo clauses: p(s)=(φ(n1)∨φ(n2)∨φ(n3)∨φ(n4)∨φ(n5)) and q(s)=(¬φ(n1)∨¬φ(n2)∨¬φ(n3)∨¬φ(n4) ∨¬φ(n5)). Then, p(s)is satisfiable if and only if c(n)= d2for some n∈sand q(s)is satisfiable if and only if c(n)= d1for some n∈s,thusp(s)∧q(s)aresatisfiableifandonlyif cdoes not induce on sa monochromatic solution of the equation x1+x2+x3+x4+c=x5. Let C = s∈S (p(s)∧q(s)). Clearly, C is satisfiable if and only if the restriction of c to Zcis a 2-coloring without monochromatic solution of the equation. The SAT-Solver shows that C is not satisfiable, therefore there does not exist a 2-coloring of the sets Zc and [1,6c+52] without monochromatic solution. Thus WR4(2,c)≤6c+52. 4.4. Seeking WR5(2,2)by computer Let T2=[1,109]. Let be a 2-coloring of T2.Forany n∈T2,weconsideraBooleanvariableφ(n)defined as follow: φ(n)=True if (n)=d1, False if (n)=d2. Let S ={(n1,...,n6)|1≤n1<n2<···<n6≤ 109, and n1+n2+n3+n4+n5+2=n6}. For any s=(n1,...,n6)∈S,weconsidertwo clauses: p(s)=(φ(n1)∨φ(n2)∨φ(n3)∨φ(n4)∨φ(n5) ∨φ(n6)) and q(s)=(¬φ(n1)∨¬φ(n2)∨¬φ(n3)∨¬φ(n4) ∨¬φ(n5)∨¬φ(n6)). Then, p(s)is satisfiable if and only if (n)= d2for some n∈sand q(s)is satisfiable if and only if (n)= d1for some n∈s,thusp(s)∧q(s)are satisfiable if and only if does not induce on sa monochromatic solution of the equation x1+x2+x3+x4+x5+2=x6. Let C = s∈S (p(s)∧q(s)). Clearly, C is satisfiable if and only if is a 2- coloring without monochromatic solution of the equation. The SAT-Solver shows that C is not satisfiable, therefore there does not exist a 2-coloring of the set T2 without monochromatic solution. Thus, WR5(2,2)≤ 109. This result can be generalized to prove WR5(2,4) ࣘ 123. 5. Backtrack programming in language C 5.1. Seeking WR2(3,c)by computer #include "CBack.c" int i, j, k, l, N, Count, Solu; FILE *fp; void PrintSol() { fprintf(fp,"N =%d is the maximum with %d solutions. \n",Count,Solu); } int Problem() { int r, t, c, a, rr, tt; int R[4][600]={0}; int T[4][600]={0}; int L[4]={0}; int VR[31]={0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5, 5, 5, 6, 6, 6, 7, 8, 8, 9, 9,10, 10,11,12,13}; int VT[31]={1,2,3,2,3,4,4,5,6,5,6,7,7,8,9,9,10,11,10,11,12,13,14,15,16,17,18, 19,20,21,22}; Solu=0; Fiasco=PrintSol; N=Select(30,31); for (r =0; r <=N-1; r++) { c=Choice(3); for (i =0; i <=L[c]-1; i++) for (j =0; j <i; j++) { if (VR[r]==R[c][i]+R[c][j]+1&&VT[r]==T[c][i]+T[c][j]) Backtrack(); } R[c][L[c]] =VR[r]; T[c][L[c]] =VT[r]; L[c]++; } Count=0; Solu++; for (c =1; c <=3; c++) { Count+=L[c]; for (r =0; r <=L[c]-1; r++) { if (R[c][r]==0) fprintf(fp,"(%d)",T[c][r]); else if (R[c][r]==1) fprintf(fp,"(%c%c%d)",’a’,’+’,T[c][r]); else fprintf(fp,"(%d%c%c%d)",R[c][r],’a’,’+’,T[c][r]); } /* fprintf(fp,"((%d))\n",L[c]); */ fprintf(fp,"\n"); } fprintf(fp,"%c",’\n’); printf(" Solutions : %d \n",Solu); Backtrack(); } main(int argc, char *argv[]) { char str[80]; strcpy (str,argv[0]); strcat (str,".txt"); fp =fopen(str,"w"); Backtracking(Problem()) fclose(fp); }