A general lower bound on the weak Schur number

A general lower bound on the weak Schur number L. Boza, M.P. Revuelta, M.I. Sanz 1 Departamento de Matem´atica Aplicada I Universidad de Sevilla, Sevilla, Spain Abstract For integers k,nwith k,n≥1, the n-color weak Schur number W Sk(n) is defined as the least integer N, such that for every n-coloring of the integer interval [1, N], there exists a monochromatic solution x1, . . . , xk, xk+1 in that interval to the equation x1+x2+. . .+xk=xk+1,with xi6=xj, when i6=j. We show a relationship between W Sk(n+ 1) and W Sk(n) and a general lower bound on the W Sk(n) is obtained. Keywords: Schur numbers, sum-free sets, weak Schur numbers, weakly sum-free sets, n-coloring. 1 Introduction For integers a≤b, we shall denote [a, b] the integer interval consisting of all t∈N+={1,2, . . .}such that a≤t≤b. A function ∆ : [1, N]−→ {c1, . . . , cn}, where c1, . . . , cn∈N+represent different colors, is a n-coloring of the interval [1, N]. 1Email: [email protected], [email protected], [email protected] Given a n-coloring ∆ and the equation x1+. . .+xk=xk+1 in k+1 variables, then we say that a solution x1, . . . , xk, xk+1 to the equation is monochromatic if and only if ∆(x1) = ∆(x2) = . . . = ∆(xk+1). For integers k,nwith k,n≥1, the n-color weak Schur number WSk(n) is defined as the least integer N, such that for every n-coloring of the integer interval [1, N], there exists a monochromatic solution x1, . . . , xk, xk+1 in that interval to the equation x1+x2+. . . +xk=xk+1,with xi6=xjwhen i6=j. In [11], the last author proved that WSk(n)≤t−1, where t=r(Tk+ 1, Tk+ 1, . . . , Tk+ 1) is the Ramsey number, with Tk= (1 + k)k/2,therefore the n-color weak Schur number exists. A set Aof integers is called sum-free if it contains no elements x1, x2, x3∈A satisfying x1+x2=x3where x1, x2need not be distinct. Schur [13] in 1916 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-free sets. The numbers S2(n) are called Schur numbers. The current knowledge on these numbers for 1 ≤n≤7 is given in Table 1. n1 2 3 4 5 6 7 S2(n) 2 5 14 45 161 ≥537 ≥1681 Table 1 The first few Schur numbers S2(n). The exact value of S2(4) was given by Baumert [1] and recently S2(5) has been obtained by Heule [9] . Finally, the lower bounds on S2(6) and S2(7) were obtained by Fredricksen and Sweet [7] by considering symmetric sum-free partitions. Many generalizations of Schur numbers have appeared since their introduction. Now, a set Aof integers is called weakly sum-free if it contains no pairwise distinct elements x1, x2, x3∈Asatisfying x1+x2=x3.We denote by WS2(n), the greatest integer N, for which the integer interval [1, N −1] can be partitioned into nweakly sum-free sets {A1, A2, . . . , An}. A result similar to that of Schur [13] was shown by Rado [10] : given n≥1, there is a greatest integer Nfor which the interval set [1, N −1] admits a partition into nweakly sum-free sets. The numbers WS2(n) are called the weak Schur numbers for the equation x1+x2=x3.The known weak Schur numbers are given in Table 2. The current state of knowledge concerning WS2(n) is quite confused. The n1 2 3 4 5 6 7 8 9 WS2(n) 3 9 24 67 ≥197 ≥583 ≥1741 ≥5202 ≥15597 Table 2 The first few weak Schur numbers W S2(n). problem seems to have been first considered in [14], 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 and WS2(5) = 197. Unfortunately, the short account written by Moser on Walker’s solution only gives suitable partitions of [1,23] for n= 3, and no details at all for the cases n= 4 and 5. Walker’s claimed values of WS2(3) and WS2(4) were later confirmed by Blanchard, Harary and Reis using computers [2]. The lower bound WS2(5) ≥197 has been confirmed in [4]. Whether equality holds in still an open problem. A lower bound on WS2(6) was obtained by Eliahou et al. [4] and later improved to WS2(6) ≥583 in [5].The lower bounds for 7 ≤n≤9 were obtained [6] in 2015. In terms of coloring the WSk(n) is the least positive integer Nsuch that for every n-coloring of [1, N], ∆ : [1, N]−→ {c1, . . . , cn}, where c1, . . . , cnrepresent ndifferent colors, there exists a monochromatic solution to the equation x1+. . . +xk=xk+1, such that ∆(x1) = . . . = ∆(xk) = ∆(xk+1) where xi6=xjwhen i6=j. In addition, for 2-coloring, the known weak Schur numbers WSk(2) are in Table 3. k2 3 4 5 WSk(2) 9 24 52 101 Table 3 The first few weak Schur numbers W Sk(2). The exact values of WSk(2) for k= 3,4 and the lower bounds were obtained in [11] and WS5(2) [3] in 2017. 2 A lower bound on WSk(2) and WSk(3) Lemma 2.1 We have WSk(2) ≥1 2(k3+ 3k2−2k)for any integer k≥6. Proof. Let ∆ be a 2-coloring: ∆ : [1,1 2(k3+ 4k2−5k+ 2)] −→ {c1, c2}, where c1, c2represent 2 different colors. Let Ai= ∆−1(ci) for i= 1,2 thus [1,1 2(1 2(k3+ 3k2−2k) + 2)] = A1tA2. We consider the partition of the interval [1,1 2(k3+ 3k2−2k)]:      A1= [1,1 2(k2+k−2)] ∪[1 2(k3+ 2k2−k),1 2(k3+ 3k2−2k−2)], A2= [1 2(k2+k),1 2(k3+ 2k2−k−2)]. We prove that for every i, 1 ≤i≤k, if x1, . . . , xk∈Aiwith xi6=xj, when i6=j, then x1+. . . +xk/∈Ai. 2 Lemma 2.2 We have WSk(3) ≥1 2(k4+ 4k3+ 2k2−7k+ 2) for any integer k≥2. Proof. We defined a 3-coloring, ∆ : [1,1 2(k4+ 4k3+ 2k2−7k)] −→ {c1, c2, c3}, where c1, c2, c3represent 3 different colors. Let Ai= ∆−1(ci) for i= 1,2,3. The interval [1,1 2(k4+ 4k3+ 2k2−7k)] = A1tA2tA3with A1=A1,1tA1,2tA1,3,A2=A2,1tA2,2and A3. The sets {A1,1, A2,1}are weakly k-sum-free, for 2-coloring in [1,1 2(k3+3k2− 2k−2)]: A1,1= [1,1 2(k2+k−2)] t[1 2(k3+ 2k2−k),1 2(k3+ 3k2−2k−2)] and A2,1= [1 2(k2+k)] t[1 2(k3+ 2k2−k−2)]. The intervals: A3= [1 2(k3+ 3k2−2k),1 2(k4+ 3k3−k2−k−2)], A1,2= [1 2(k4+ 3k3−k2−k),1 2(k4+ 3k3−2k−2)], A2,2= [1 2(k4+ 3k3−2k),1 2(k4+ 4k3+k2−6k)] and A1,3= [1 2(k4+ 4k3+k2−6k+ 2),1 2(k4+ 4k3+ 2k2−7k)]. The sets {A1, A2, A3}are weakly k-sum-free for the 3 −coloring above. 2 3 A general lower bound on WSk(n) We prove the following relationship between the weak Schur numbers for ncoloring and (n+ 1)-coloring for the equation x1+x2+. . . +xk=xk+1,with xi6=xj, when i6=j. Lemma 3.1 We have WSk(n+ 1) ≥kWSk(n) + (k−1)p(k)for any integer k≥2,n≥2, with p(k) = 1 2(k2+ 5k−2). Proof. We consider a partition with nweakly k-sum-free sets on the interval [1, WSk(n)−1] = A1t. . . tAn. Applying the procedure of the Lemma 2.2 we can extend this partition to get an n+ 1- partition weakly ksum-free. This partition is {B1, B2, A3, . . . , An, An+1},an the intervals are: An+1 = [WSk(n), kWSk(n) + 1 2(k2−k−2)], A1,1= [kWSk(n) + 1 2(k2−k), kWSk(n) + 1 2(2k2−2k−2)], A2,1= [kWSk(n) + 1 2(2k2−2k), kWSk(n) + 1 2(k3+ 3k2−6k)], A1,2= [kWSk(n) + 1 2(k3+ 3k2−6k+ 2), kWSk(n) + 1 2(k3+ 4k2−7k)], B1=A1tA1,1tA1,2and B2=A2tA2,1. Then WSk(n+1) ≥kWSk(n)+1 2(k3+4k2−7k)+1 = kWSk(n)+(k−1)p(k). 2 We obtain a general lower bound for WSk(n) in the following result: Theorem 3.2 For the equation x1+. . . +xk=xk+1 such that xi6=xjwhen i6=j, we have WSk(n)≥q(k)kn−2−p(k), with q(k) = 1 2k3+ 2k2+3 2k−1 and p(k) = 1 2(k2+ 5k−2) for n≥2,k≥2. References [1] L.D. Baumert. Sum-free sets. J.P.L. Research Summary, 36-10: 16–18, 1961. [2] P. F. Blanchard, F. Harary, and R. Reis. Partitions into sum-free sets. Electronic Journal of Combinatorial Numbers theory 6:1–10, 2006. [3] L. Boza, J.M. Mar´ın, M.P. Revuelta and M.I. Sanz. On the n-color weak Rado numbers for the equation x1+x2+. . . +xk+c=xk+1.Experiment. Math., accepted 2017. [4] S. Eliahou, J. M. Mar´ın, M. P. Revuelta and M. I. Sanz. Weak Schur numbers and the search for G.W. Walker’s lost partitions. Computers and Mathematics with Applications, 63:175–182, 2012. [5] S. Eliahou, C. Fonlupt, J. Fromentin, V. Marion-Poty, D. Robilliard and F. Teytaud. Investigating Monte-Carlo methods on the weak Schur problem. Lecture Notes in Computer Science, 7832:191–201, 2013. [6] F.A. Rafilipojaona. Nombres de Schur classiques et faibles. Ph. Thesis, Universit Lille Nord-de-France, 2015. [7] H. Fredricksen and M. Sweet. Symmetric sum-free partitions and lower bounds for Schur numbers. The Electronic Journal of Combinatorics, 7:#R32, 2000. [8] K. Helsgaun. CBack: A Simple Tool for Backtrack Programming in C. Softw. pract.exp., 25(8):905-934, 1995. [9] M.J.H. Heule. Schur Number Five. Discrete Mathematics, preprint, 2017. [10] R. Rado. Some solved and unsolved problems in the theory of numbers. Math. Gaz., 25:72-77, 1941. [11] M.I. Sanz. N´umeros de Schur y Rado. Ph. Thesis, Universidad de Sevilla, 2010. [12] M. Heule, http://www.st.ewi.tudelft.nl/sat/, March RW. SAT Competition 2011, 2011. [13] I. Schur. Uber die Kongruenz xm+ym≡zm(mod p). Jber. Deutsch. Math.- Verein., 25:114–117, 1916. [14] G.W. Walker. A problem in partitioning. The American Mathematical Monthly . 59:253, 1952.