Weak Schur numbers and the search for G.W. Walker’s lost partitions

Weak Schur numbers and the search for G.W. Walker’s lost partitions S. Eliahou a,b,c,∗, J.M. Marín d, M.P. Revuelta d, M.I. Sanz d a Univ Lille Nord de France, F-59000 Lille, France b ULCO, LMPA J. Liouville, B.P. 699, F-62228 Calais, France c CNRS, FR 2956, France d Escuela Técnica Superior de Ingeniería de Edificación, Departamento de Matemática Aplicada I, Avenida Reina Mercedes 4, C.P. 41012 Sevilla, Spain Keywords: Schur numbers Sumfree sets Weakly sum-free sets Boolean variables SAT problem SAT solver abstract A set Aof integers is weakly sum-free if it contains no three distinct elements x,y,zsuch that x+y=z. Given k≥1, let WS(k)denote the largest integer nfor which {1, . . . , n} admits a partition into kweakly sum-free subsets. In 1952, G.W. Walker claimed the value WS(5)=196, without proof. Here we show WS(5)≥196, by constructing a partition of {1, . . . , 196}of the required type. It remains as an open problem to prove the equality. With an analogous construction for k=6, we obtain WS(6)≥572. Our approach involves translating the construction problem into a Boolean satisfiability problem, which can then be handled by a SAT solver. 1. Introduction A set Aof integers is called sum-free if it contains no elements x,y,z∈Asatisfying x+y=z. It is called weakly sumfree [1] if it contains no pairwise distinct elements x,y,z∈Asatisfying x+y=z. Clearly, sum-free implies weakly sum-free; the converse is false, as shown by A= {1,2}. This paper is concerned with partitions of the set [1,n] = {1,2,...,n}into ksum-free, or kweakly sum-free parts, with kfixed and nas large as possible with respect to k. 1.1. Schur numbers A theorem of Schur states that, given k≥1, there is indeed a largest integer nfor which [1,n]admits a partition into k sum-free sets [2]. This largest nis called the k-th Schur number and is denoted by S(k). For instance, one has S(1)=1 and S(2)=4. For k=2, a partition of [1,4]into 2 sum-free sets is provided by {1,2,3,4} = {1,4} ⊔ {2,3}, and it is easy to check that there is no such partition for [1, 5]. Only two more exact values of S(k)are known so far, namely S(3)=13,S(4)=44. The currently available bounds for S(5)are 160 ≤S(5)≤305,(1) ∗ Corresponding author at: Univ Lille Nord de France, F-59000 Lille, France. E-mail addresses: [email protected] (S. Eliahou), [email protected] (J.M. Marín), [email protected] (M.P. Revuelta), [email protected] (M.I. Sanz). and it is conjectured in [3] that the lower bound 160, settled in [4], is perhaps sharp. For the upper bound 305, see [5,6]. While the value S(3)=13 can still be settled by hand, the value S(4)=44 relies on an exhaustive computer search [7,8]. Also note the bounds S(6)≥536 and S(7)≥1680 established in [3]. For general k≥1, Schur proved the following lower and upper bounds [2]: (3k−1)/2≤S(k)≤ ⌊k!e⌋ − 1. 1.2. Weak Schur numbers As for partitions of [1,n]into weakly sum-free sets, a result analogous to Schur’s holds, due to Rado [9]. See also [10,1,11]. Let us denote by WS(k)the largest integer nfor which [1,n]can be partitioned into kweakly sum-free parts. We call WS(k) the k-th weak Schur number. Note that some authors prefer to speak of Nk=WS(k)+1, the smallest integer n′for which every k-coloring of [1,n′]contains a monochromatic triple {a,b,a+b}with a= b. The current state of knowledge concerning WS(k)is quite confused. The problem seems to have been first considered in [12], which is Walker’s solution to Problem E 985 proposed a year earlier, in 1951, by Leo Moser1. Subsequent mentions appear in [13,1,14,10,11,6], in the chronological order. The values WS(1)=2 and WS(2)=8 are easy to check. It is established in [10], by exhaustive computer search, that WS(3)=23, WS(4)=66, WS(5)≥189. However, the authors of [10] seem to have been unaware of Walker’s note [12]. Indeed, that note contains amazing claims that go beyond [10]. Not only does it give the exact values for WS(3)and WS(4), it further claims the equality WS(5)=196. Unfortunately, Walker only discusses the case k=3, by giving a suitable partition of [1,23]and explaining why 23 is optimal. He gives no details for k=4 and 5, not even suitable partitions which would establish WS(4)≥66 and WS(5)≥196. Nobody today seems to know how Walker managed to make these amazing claims back in 1952, when computers were not generally available. The situation is somewhat reminiscent of Fermat’s claimed Last Theorem which, incidentally, was the main motivation behind Schur’s discovery of his numbers S(k)in [2]. Finally, let us mention the following upper bound, improving an earlier one by Irving [1] and due to Bornsztein [14]: WS(k)≤ ⌊k!k e⌋. 1.3. Comparing S(k)and WS(k) It is clear from the definitions that S(k)≤WS(k)(2) for all k≥1. Indeed, the set [1,S(k)]admits a partition into ksum-free, and hence weakly sum-free, subsets. This inequality is important, as it provides a natural upper bound for the Schur numbers S(k). In particular, Walker’s claim on WS(5)yields a major potential improvement, apparently not mentioned before, of the best known upper bound on S(5): S(5)≤WS(5)? =196, as compared to S(5)≤305 in (1). This certainly provides a strong call to definitively settle the exact value of WS(5). There is a long time interval, from [1] in 1973 to [14] in 2002, during which Walker’s note seems to have fallen into oblivion. One possible reason is that yet another claim of Walker’s, namely WS(k+1)≤3 WS(k)+1 for k≥3, was pointed out by Irving [1] as being incompatible with the following bound of Abbott and Hanson [15] on the ordinary Schur numbers: S(k)≥c89k/4 for all k≥4, where c=44/89. 1.4. Links with multicolor Ramsey numbers The classical and weak Schur numbers are related to some multicolor Ramsey numbers, as we now recall. For integers k,m≥1, denote by Rk(m)the smallest integer n≥1 such that, for every k-coloring of the edges of the complete graph Kn 1In fact, Moser’s informal challenge was about S(3); Walker considered WS(3)instead. on nvertices, there is a subgraph Km, all of whose edges are colored the same. A short argument (see e.g. [16, p. 69]) yields the bound S(k)≤Rk(3)−2; the idea is to transport a k-coloring of [1,n−1]to a k-coloring of the edges of Knby assigning to any edge {x,y}the color of |x−y|. As for weak Schur numbers, suitable adaptations of this idea yield two different bounds, namely WS(k)≤Rk(4)−2 and WS(k)≤R2k(3)−2. See [10, p. 2] for the first bound, and [11, p. 303] for the second one. 1.5. Contents In this paper, we do give a proof of the inequality WS(5)≥196, by providing an actual partition of [1, 196] into 5 weakly sum-free sets. Our efforts to do the same with [1, 197] completely failed. It remains as a challenge to prove, by theory or by machine, that 196 is the exact value of WS(5). Our construction showing WS(5)≥196 is given in Section 2, together with reasons pointing to the probable sharpness of this bound. In Section 3, we treat the case of 6-partitions and obtain WS(6)≥572, apparently the first known realistic lower bound on WS(6). Our method is described in Section 4. It involves translating the problem of constructing partitions of the desired type into a Boolean satisfiability problem, to be handled by a SAT solver. The actual computations are briefly commented in Section 5. 2. Is it true that WS(5)=196? There are no details in [12] substantiating the claim WS(5)=196, not even an actual partition of [1, 196] into 5 weakly sum-free subsets which would establish WS(5)≥196. Surely Walker knew such partitions, but we do not know how he proceeded, and these are probably lost forever. Here we fill this literature gap by providing one such partition, constructed using the methods of Section 4and the SAT solver march [17]. As a matter of notation, we shall abbreviate runs of consecutive integers as intervals. For instance, [8, 9] 12 [14, 17] stands for the set {8,9,12,14,15,16,17}. Theorem 2.1. WS(5)≥196. Proof. Consider the following partition A1⊔A2⊔A3⊔A4⊔A5of [1, 196]: A1: 1 2 4 8 11 22 25 50 63 69 135 140 150 155 178 183 193 A2: 3 [5, 7] 19 21 23 [51, 53] [64, 66] [137, 139] [151, 153] [180, 182] [194, 196] A3: [9, 10] [12, 18] 20 [54, 62] [141, 149] [184, 192] A4: 24 [26, 49] 154 [156, 177] 179 A5: [67, 68] [70, 134] 136. It is straightforward to check that each Aiis weakly sum-free. This finishes the proof.  Is this lower bound on WS(5)sharp? If not, there would exist a partition of [1, 197] into 5 weakly sum-free sets. In order to try and find one, we applied the same methods as above. But these attempts completely failed, as no conclusion of existence or non-existence was reached after several weeks of running time. This strongly supports Walker’s claim. Yet it remains as an open problem to prove or disprove the inequality WS(5)≤196. 2.1. Fixing the 5th part Here are two more computational results in support of Walker’s claim. Fixing the 5th part of a tentative partition of [1,n] into 5 weakly sum-free sets reduces the number of Boolean variables involved in our method from 3nto 2n. The reason, made clear in Section 4, is that ⌈log2(5)⌉ = 3 whereas ⌈log2(4)⌉ = 2. This reduction allows march to terminate its computations and reach definitive conclusions, even for n=197. The following results were obtained in this way. The first statement concludes an attempt to improve Theorem 2.1 by constructing a partition of [1, 197] into 5 weakly sum-free sets, while keeping the same 5th part A5. Not surprisingly, the conclusion is negative. Computational Theorem 2.2. There is no partition of [1,197]into 5weakly sum-free parts with A5= [67,68] ∪ [70,134] ∪ {136}as one part. Our second statement deals with the following question: to what extent is it possible to replace A5in Theorem 2.1 by a single interval? More precisely, we looked for the largest possible nfor which [1,n]admits a partition into 5 weakly sum-free sets B1,...,B5such that: •B1,B2,B3,B4is a partition of [1, 66], •B5is a single interval. Observe that the first requirement is satisfied by A1,A2,A3,A4in Theorem 2.1, and recall that 66 =WS(4). Consequently, B5must contain 67 and cannot be strictly larger than [67, 134]. Thus, without loss of generality, we may and will assume B5= [67,134]. Quite surprisingly, the largest admissible nturns out to be n=194 only. Computational Theorem 2.3. The largest n for which [1,n]admits a partition into 5weakly sum-free parts, with [67,134]as one part, is n =194. For the record, here is such a partition of [1, 194]. B1: 1 2 4 8 11 22 25 50 66 138 148 153 176 181 194 B2: 3 [5, 7] 19 21 23 [51, 53] [63, 65] [135, 137] [149, 151] [178, 180] [191, 193] B3:[9, 10] [12, 18] 20 [54, 62] [139, 147] [182, 190] B4: 24 [26, 49] 152 [154, 175] 177 B5: [67, 134]. These two results were reached in about 17 and 18 h, respectively, on a 3.33 GHz Intel i7 processor PC with the SAT solver march. 3. A lower bound on WS(6) We obtain here the lower bound WS(6)≥572, by exhibiting a suitable partition of [1, 572] into 6 weakly sum-free subsets. Instructed by a fair amount of experimentation, we think that this bound is quite realistic, with a margin of error possibly less than 10. In the partition below, we keep the same notational convention with intervals as in the preceding section. Theorem 3.1. WS(6)≥572. Proof. Consider the following partition A1⊔A2⊔A3⊔A4⊔A5⊔A6of [1, 572]: A1: 1 2 4 8 11 22 25 50 63 69 135 140 150 155 178 183 193 395 412 516 526 531 554 559 572 A2: 3[5, 7] 19 21 23 [51, 53] [64, 66] [137, 139] [151, 153] [180, 182] [194, 196] [396, 398] [408, 410] 435 [513, 515] [527, 529] [556, 558] [569, 571] A3: [9, 10] [12, 18] 20 [54, 62] [141, 149] [184, 192] [399, 407] [437, 445] [517, 525] [560, 568] A4: 24 [26, 49] 154 [156, 177] 179 411 [413, 434] 436 530 [532, 553] 555 A5: [67, 68] [70, 134] 136 [446, 512] A6: [197, 394]. Again, it is straightforward to check that each Aiis weakly sum-free.  The only previously available firm lower bound on WS(6)was 536, which is the lower bound for S(6)given in [3]. Another lower bound could be obtained from the claimed inequality WS(k)≥3(3k+2k−1)/4−1, which gives 554 at k=6. However, this inequality does not seem to be backed up by any available proof. It is attributed to Braun in [12]. Note that it is sharp for k=1,2,3, and gives 65 =WS(4)−1 at k=4. 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 to a SAT solver. See [18–21] for earlier successful uses of SAT solvers in combinatorial number theory. Recall that a logical formula 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 formula evaluates to True. Let n,k≥2. Let T1,...,Trbe a family of subsets of [1,n]. Assume that we are seeking k-colorings of [1,n]for which no Tjis monochromatic. Such k-colorings correspond of course to k-partitions of [1,n]for which no Tjis contained in a single part. We shall translate this existence problem into one asking whether some associated logical formula is satisfiable or not. In the applications in Section 5, the subsets Tjwill be all possible triples in [1,n]of the form {a,b,a+b}with a= b. It is sometimes convenient to express logical formulas in conjunctive normal form, or CNF for short. That is, as conjunctions t  l=1 Cl(3) of clauses C1,...,Cl, a clause being a disjunction of the form xi1∨ · · · ∨ xis∨ ¬xj1∨ · · · ∨ ¬xjt. Here, as usual, the symbols ∧,∨and ¬denote the logical operations AND, OR and NOT, respectively. Most formulas below are in CNF. From now on, we shall write 1 for True and 0 for False. In particular, we have ¬1=0 and ¬0=1. 4.1. The case k =2 We start with two colors. Let x1,...,xnbe nBoolean variables. There is a bijective correspondence between {0,1}- assignments of the xi’s and 2-colorings of [1,n]. For a subset T⊂ [1,n], define the CNF formula cl2(T, (x1,...,xn)) = i∈T xi∧ i∈T ¬xi.(4) Lemma 4.1. Let T ⊂ [1,n]. The 2-colorings of [1,n]for which T is non-monochromatic correspond to the {0,1}-assignments xi=ϵi(i=1,...,n)for which cl2(T, (ϵ1, . . . , ϵn)) =1. Proof. By construction, cl2(T, (ϵ1, . . . , ϵn)) =1 if and only if there are indices i,j∈Tsuch that ϵi= ¬ϵj=1, or equivalently ϵi=1 and ϵj=0; this happens if and only if Tis non-monochromatic for the corresponding 2-coloring of [1,n]. When several subsets of [1,n]are required to be simultaneously non-monochromatic, it suffices to satisfy the conjunction of the corresponding formulas. This yields the following equivalence. Proposition 4.2. Let n ≥1and let T1,...,Trbe subsets of [1,n]. Let x1,...,xnbe Boolean variables. There exists a 2-coloring of [1,n]such that no Tjis monochromatic if and only if the formula r  j=1 cl2(Tj, (x1,...,xn)) is satisfiable.  4.2. The case k =2t We first extend the above considerations to k=2tfor any integer t≥1. Our set of 2tcolors is taken to be the Cartesian product {0,1}t. Let (xi,l) (1≤i≤n,1≤l≤t)be a collection of nt Boolean variables. The unknown color of any i∈ [1,n]may and will be represented by the t-tuple (xi,1,...,xi,t). Let T⊂ [1,n]. The 2t-colorings of [1,n]for which Tis non-monochromatic correspond to those {0,1}-assignments (ϵi,l)of (xi,l)for which there are indices l∈ [1,t]and i,j∈Tsuch that ϵi,l= ϵj,l. By the case of two colors, this condition is equivalent to the Boolean one cl2(T, (ϵ1,l, . . . , ϵn,l)) =1. Since indices lwhere a difference occurs may be arbitrary, one needs to take the disjunction over all l∈ [1,t]of the above formula. Moreover, when several subsets of [1,n]are involved, the conjunction of the corresponding formulas must be satisfied. This yields the following generalization of Proposition 4.2. Proposition 4.3. Let n,t≥1and let T1,...,Trbe subsets of [1,n]. Let (xi,l)(1≤i≤n,1≤l≤t)be nt Boolean variables. There exists a 2t-coloring of [1,n]such that no Tjis monochromatic if and only if the formula r  j=1t  l=1 cl2(Tj, (x1,l,...,xn,l)) is satisfiable.  This formula is not in CNF, but this can be fixed using the distributivity of ∨over ∧. To wit, an equivalent CNF formula is given by r  j=1  U⊔V=[1,t]   i∈Tj u∈U xi,u ∨  i∈Tj v∈V ¬xi,v   , where ⊔denotes a disjoint union. 4.3. The general case We now treat any number k≥2 of colors. Let t≥1 be the unique integer such that 2t−1+1≤k≤2t. That is, t= ⌈log2(k)⌉. Within the set {0,1}tof 2tcolors, we forbid some 2t−kones. The remaining kcolors then constitute our final palette of colors. It remains to translate the requirement that some colors are forbidden into the satisfiability of appropriate Boolean formulas. For this, it suffices to consider a single forbidden color; the case of several ones follows by taking the conjunction of the corresponding formulas. First observe that, for x,y∈ {0,1}, the condition x= yis equivalent to the logical formula (x∨y)∧(¬x∨ ¬y)=1. Now, let µ=(µ1, . . . , µt)∈ {0,1}tbe a fixed color. Given tBoolean variables z1,...,zt, define fµ(z1,...,zt)= t  l=1 (zl∨µl)∧(¬zl∨ ¬µl). It then follows from the above observation that, for all ϵ=(ϵ1, . . . , ϵt)∈ {0,1}t, we have ϵ= µ⇔fµ(ϵ) =1. Thus, forbidding color µmay be achieved using formula fµ. This yields the following result. Theorem 4.4. Let n,k,t be integers with k,n≥2and 2t−1+1≤k≤2t. Let T1,...,Trbe subsets of [1,n]. The existence of k-colorings of [1,n]for which no Tjis monochromatic is equivalent to the satisfiability of the formula r  j=1t  l=1 cl2(Tj, (x1,l,...,xn,l))∧ n  i=1 2t−k  s=1 fµs(xi,1,...,xi,t), where µ1, . . . , µ2t−kis any choice of 2t−k distinct elements in {0,1}t. Proof. By Proposition 4.3, satisfying the left-hand subformula gives 2t-colorings of [1,n]with no Tjmonochromatic. Satisfying the right-hand one guarantees that no µsis used in those colorings.  5. Applications The above result implies the following SAT characterization of the weak Schur numbers, made explicit for completeness. Corollary 5.1. Let n,k,t be integers, with k,n≥2and 2t−1+1≤k≤2t. The following conditions are equivalent. 1. WS(k)≥n. 2. The formula  a<bt  l=1 cl2({a,b,a+b}, (x1,l,...,xn,l))∧ n  i=1 2t−k  j=1 fµj(xi,1,...,xi,t) is satisfiable, where a,b run over all integers satisfying 1≤a<b≤n−a−b, and where µ1, . . . , µ2t−kare any 2t−k elements in {0,1}t. Moreover, every variable assignment for which the above formula is satisfied corresponds to an actual partition of [1,n]into k weakly sum-free subsets. Proof. This directly follows from the definition of WS(k)and from Theorem 4.4, specialized to the case where the subsets Tjof [1,n]are all triples {a,b,a+b}with a<b. This SAT reformulation, together with the SAT solver march, allowed us to construct the weakly sum-free partitions of Sections 2and 3. Recall that these partitions yield the lower bounds WS(5)≥196 and WS(6)≥572, respectively. Our Computational Theorems 2.2 and 2.3 were obtained with those same tools. However, for this attack on WS(5)and WS(6), the corresponding SAT problems are somewhat too large. In order to reduce the number of variables and clauses, we performed experiments with selected elements of [1,n]pre-located in the same part of the tentative partitions. For instance, we looked for 5-partitions of [1, 196] into weakly sum-free sets which would extend chosen 4-partitions of [1, 66], where 66 =WS(4). This removes many variables. Without such reductions, it seems difficult for a SAT solver to construct from scratch a partition of [1, 196] of the desired type, let alone to conclude WS(5) < 197. The case k=4, in contrast, can be fully handled. We were able to recover the known values WS(4)=66 and S(4)=44, the latter with a SAT characterization of S(k)similar to that of WS(k)above. The corresponding running times are displayed below. Output Conclusion Time in seconds A suitable 4-partition of [1, 44] S(4)≥44 0 ‘‘Unsatisfiable’’ S(4) < 45 60 A suitable 4-partition of [1, 66] WS(4)≥66 917 ‘‘Unsatisfiable’’ WS(4) < 67 24,450 We confirmed the equality WS(4)=66 by running march on two distinct files embodying Corollary 5.1, namely wschur4_66.txt and wschur4_67.txt. These files are available at [22], for the reader wishing to reproduce these computations with any SAT solver. They contain, in standard DIMACS format, a list of CNF clauses whose satisfiability or not is equivalent to the existence or not of a suitable 4-partition of [1, 66] and [1, 67], respectively. The file wschur4_66.txt contains 4224 clauses on 132 Boolean variables. Its first clause reads 1 2 3 67 68 69 0, with 0 as a closing symbol, and codes for x1∨x2∨x3∨x67 ∨x68 ∨x69. Its next clause reads −1−2−3 67 68 69 0 and codes for ¬x1∨ ¬x2∨ ¬x3∨x67 ∨x68 ∨x69. Any SAT solver running it should end up displaying an assignment of the variables that will satisfy all the clauses. As for the file wschur4_67.txt, which contains 4356 clauses on 134 Boolean variables, any SAT solver running it should conclude that its set of clauses is unsatisfiable. We end with a few technical details. The version of march we used was march_hi [17], running on an Intel i7 processor PC with a CPU clock speed of 3.33 GHz and 16 GB of RAM memory. As far as we know, the multi-core architecture of the CPU is not exploited by this implementation of march_hi. Acknowledgments We thank Amine Boumaza, Jonathan Chappelon, Philippe Marion, Virginie Marion-Poty, Denis Robilliard and Dominique Verhaghe for helpful discussions and/or technical help during the preparation of this paper. We also thank both referees for their careful reading and very useful comments. Note. While this paper was being refereed, our colleagues Amine Boumaza, Cyril Fonlupt, Virginie Marion-Poty and Denis Robilliard succeeded in improving our lower bound on WS(6), from 572 to 574. They used a completely different method, namely an enhanced tabu search scheme. See their forthcoming paper, to appear in the proceedings of Artificial Evolution 2011. Note added in proof. We have further improved the lower bound on WS(6), which is now given by WS(6) ≥575. References [1] Robert W. Irving, An extension of Schur’s theorem on sum-free partitions, Acta Arith. 25 (1973/74) 55–64. [2] Issai Schur, Uber die Kongruenz xm+ym≡zm(mod p), Jahresber. Deutsch. Math.-Verein. 25 (1916) 114–117. [3] Harold Fredricksen, Melvin M. Sweet, Symmetric sum-free partitions and lower bounds for Schur numbers, Electron. J. Combin. 7 (2000) Research Paper 32, 9, electronic. [4] Geoffrey Exoo, A lower bound for Schur numbers and multicolor Ramsey numbers of K3, Electron. J. Combin. 1 (1994) Research Paper 8, approx. 3, electronic. [5] S. Radziszowski, Small Ramsey numbers, Electron. J. Combin. 1 (1994) Dynamic Survey DS1, Revision #6 (1999), 35, electronic. [6] M.I. Sanz, Números de Schur y de Rado, Ph.D Thesis, Departamento de Matemática Aplicada I, Universidad de Sevilla, 2010. [7] Leonard D. Baumert, Sum-free sets, J.P.L. Res. Summary 1 (36–10) (1961) 16–18. [8] Solomon W. Golomb, Leonard D. Baumert, Backtrack programming, J. Assoc. Comput. Mach. 12 (1965) 516–524. [9] R. Rado, Some solved and unsolved problems in the theory of numbers, Math. Gaz. 25 (1941) 72–77. [10] Peter F. Blanchard, Frank Harary, Rogerio Reis, Partitions into sum-free sets, Integers 6 (A7) (2006) 10, electronic. [11] A. Soifer, The Mathematical Coloring Book. Mathematics of Coloring and the Colorful Life of its Creators, Springer, New York, ISBN: 978-0-387-74640-1, 2009. [12] G.W. Walker, A problem in partitioning, Amer. Math. Monthly 59 (1952) 253. [13] W. Sierpiński, Elementary theory of numbers. Translated from Polish by A. Hulanicki. Monografie Matematyczne, Tom 42 Państwowe Wydawnictwo Naukowe, Warsaw, 1964. [14] Pierre Bornsztein, On an extension of a theorem of Schur, Acta Arith. 101 (2002) 395–399. [15] H.L. Abbott, D. Hanson, A problem of Schur and its generalizations, Acta Arith. 20 (1972) 175–187. [16] R.L. Graham, B.L. Rothschild, J.H. Spencer, Ramsey theory. Second edition. Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1990. [17] http://www.st.ewi.tudelft.nl/sat/. [18] Michael R. Dransfield, Lengning Liu, Victor W. Marek, Miroslaw Truszczyński, Satisfiability and computing van der Waerden numbers, Electron. J. Combin. 11 (1) (2004) Research Paper 41, 15, electronic. [19] P.R. Herwig, M.J.H. Heule, P.M. van Lambalgen, H. van Maaren, A new method to construct lower bounds for van der Waerden numbers, Electron. J. Combin. 14 (2007) Research Paper 6, 18, electronic. [20] M. Kouril, J.L. Paul, The van der Waerden number W(2,6)is 1132, Experiment. Math. 17 (2008) 53–61. [21] D. Robilliard, A. Boumaza, V. Marion-Poty, Meta-heuristic search and square Erickson matrices, in: Proceeding of the IEEE Congress on Evolutionary Computation (CEC’10), pp. 3237–3244, IEEE, 2010. [22] http://www-lmpa.univ-littoral.fr/~eliahou/schur/.