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

Weak Schu numbe s and he sea ch o G.W. Walke ’s los pa i ions S. Eliahou a,b,c,∗, J.M. Ma ín d, M.P. Re uel a d, M.I. Sanz d a Uni Lille No d de F ance, F-59000 Lille, F ance b ULCO, LMPA J. Liou ille, B.P. 699, F-62228 Calais, F ance c CNRS, FR 2956, F ance d Escuela Técnica Supe io de Ingenie ía de Edi icación, Depa amen o de Ma emá ica Aplicada I, A enida Reina Me cedes 4, C.P. 41012 Se illa, Spain Keywo ds: Schu numbe s Sum- ee se s Weakly sum- ee se s Boolean a iables SAT p oblem SAT sol e abs ac A se Ao in ege s is weakly sum- ee i i con ains no h ee dis inc elemen s x,y,zsuch ha x+y=z. Gi en k≥1, le WS(k)deno e he la ges in ege n o which {1, . . . , n} admi s a pa i ion in o kweakly sum- ee subse s. In 1952, G.W. Walke claimed he alue WS(5)=196, wi hou p oo . He e we show WS(5)≥196, by cons uc ing a pa i ion o {1, . . . , 196}o he equi ed ype. I emains as an open p oblem o p o e he equali y. Wi h an analogous cons uc ion o k=6, we ob ain WS(6)≥572. Ou app oach in ol es ansla ing he cons uc ion p oblem in o a Boolean sa is iabili y p oblem, which can hen be handled by a SAT sol e . 1. In oduc ion A se Ao in ege s is called sum- ee i i con ains no elemen s x,y,z∈Asa is ying x+y=z. I is called weakly sum- ee [1] i i con ains no pai wise dis inc elemen s x,y,z∈Asa is ying x+y=z. Clea ly, sum- ee implies weakly sum- ee; he con e se is alse, as shown by A= {1,2}. This pape is conce ned wi h pa i ions o he se [1,n] = {1,2,...,n}in o ksum- ee, o kweakly sum- ee pa s, wi h k ixed and nas la ge as possible wi h espec o k. 1.1. Schu numbe s A heo em o Schu s a es ha , gi en k≥1, he e is indeed a la ges in ege n o which [1,n]admi s a pa i ion in o k sum- ee se s [2]. This la ges nis called he k- h Schu numbe and is deno ed by S(k). Fo ins ance, one has S(1)=1 and S(2)=4. Fo k=2, a pa i ion o [1,4]in o 2 sum- ee se s is p o ided by {1,2,3,4} = {1,4} ⊔ {2,3}, and i is easy o check ha he e is no such pa i ion o [1, 5]. Only wo mo e exac alues o S(k)a e known so a , namely S(3)=13,S(4)=44. The cu en ly a ailable bounds o S(5)a e 160 ≤S(5)≤305,(1) ∗ Co esponding au ho a : Uni Lille No d de F ance, F-59000 Lille, F ance. E-mail add esses: [email p o ec ed] (S. Eliahou), [email p o ec ed] (J.M. Ma ín), [email p o ec ed] (M.P. Re uel a), [email p o ec ed] (M.I. Sanz). and i is conjec u ed in [3] ha he lowe bound 160, se led in [4], is pe haps sha p. Fo he uppe bound 305, see [5,6]. While he alue S(3)=13 can s ill be se led by hand, he alue S(4)=44 elies on an exhaus i e compu e sea ch [7,8]. Also no e he bounds S(6)≥536 and S(7)≥1680 es ablished in [3]. Fo gene al k≥1, Schu p o ed he ollowing lowe and uppe bounds [2]: (3k−1)/2≤S(k)≤ ⌊k!e⌋ − 1. 1.2. Weak Schu numbe s As o pa i ions o [1,n]in o weakly sum- ee se s, a esul analogous o Schu ’s holds, due o Rado [9]. See also [10,1,11]. Le us deno e by WS(k) he la ges in ege n o which [1,n]can be pa i ioned in o kweakly sum- ee pa s. We call WS(k) he k- h weak Schu numbe . No e ha some au ho s p e e o speak o Nk=WS(k)+1, he smalles in ege n′ o which e e y k-colo ing o [1,n′]con ains a monoch oma ic iple {a,b,a+b}wi h a= b. The cu en s a e o knowledge conce ning WS(k)is qui e con used. The p oblem seems o ha e been i s conside ed in [12], which is Walke ’s solu ion o P oblem E 985 p oposed a yea ea lie , in 1951, by Leo Mose 1. Subsequen men ions appea in [13,1,14,10,11,6], in he ch onological o de . The alues WS(1)=2 and WS(2)=8 a e easy o check. I is es ablished in [10], by exhaus i e compu e sea ch, ha WS(3)=23, WS(4)=66, WS(5)≥189. Howe e , he au ho s o [10] seem o ha e been unawa e o Walke ’s no e [12]. Indeed, ha no e con ains amazing claims ha go beyond [10]. No only does i gi e he exac alues o WS(3)and WS(4), i u he claims he equali y WS(5)=196. Un o una ely, Walke only discusses he case k=3, by gi ing a sui able pa i ion o [1,23]and explaining why 23 is op imal. He gi es no de ails o k=4 and 5, no e en sui able pa i ions which would es ablish WS(4)≥66 and WS(5)≥196. Nobody oday seems o know how Walke managed o make hese amazing claims back in 1952, when compu e s we e no gene ally a ailable. The si ua ion is somewha eminiscen o Fe ma ’s claimed Las Theo em which, inciden ally, was he main mo i a ion behind Schu ’s disco e y o his numbe s S(k)in [2]. Finally, le us men ion he ollowing uppe bound, imp o ing an ea lie one by I ing [1] and due o Bo nsz ein [14]: WS(k)≤ ⌊k!k e⌋. 1.3. Compa ing S(k)and WS(k) I is clea om he de ini ions ha S(k)≤WS(k)(2) o all k≥1. Indeed, he se [1,S(k)]admi s a pa i ion in o ksum- ee, and hence weakly sum- ee, subse s. This inequali y is impo an , as i p o ides a na u al uppe bound o he Schu numbe s S(k). In pa icula , Walke ’s claim on WS(5)yields a majo po en ial imp o emen , appa en ly no men ioned be o e, o he bes known uppe bound on S(5): S(5)≤WS(5)? =196, as compa ed o S(5)≤305 in (1). This ce ainly p o ides a s ong call o de ini i ely se le he exac alue o WS(5). The e is a long ime in e al, om [1] in 1973 o [14] in 2002, du ing which Walke ’s no e seems o ha e allen in o obli ion. One possible eason is ha ye ano he claim o Walke ’s, namely WS(k+1)≤3 WS(k)+1 o k≥3, was poin ed ou by I ing [1] as being incompa ible wi h he ollowing bound o Abbo and Hanson [15] on he o dina y Schu numbe s: S(k)≥c89k/4 o all k≥4, whe e c=44/89. 1.4. Links wi h mul icolo Ramsey numbe s The classical and weak Schu numbe s a e ela ed o some mul icolo Ramsey numbe s, as we now ecall. Fo in ege s k,m≥1, deno e by Rk(m) he smalles in ege n≥1 such ha , o e e y k-colo ing o he edges o he comple e g aph Kn 1In ac , Mose ’s in o mal challenge was abou S(3); Walke conside ed WS(3)ins ead. on n e ices, he e is a subg aph Km, all o whose edges a e colo ed he same. A sho a gumen (see e.g. [16, p. 69]) yields he bound S(k)≤Rk(3)−2; he idea is o anspo a k-colo ing o [1,n−1] o a k-colo ing o he edges o Knby assigning o any edge {x,y} he colo o |x−y|. As o weak Schu numbe s, sui able adap a ions o his idea yield wo di e en bounds, namely WS(k)≤Rk(4)−2 and WS(k)≤R2k(3)−2. See [10, p. 2] o he i s bound, and [11, p. 303] o he second one. 1.5. Con en s In his pape , we do gi e a p oo o he inequali y WS(5)≥196, by p o iding an ac ual pa i ion o [1, 196] in o 5 weakly sum- ee se s. Ou e o s o do he same wi h [1, 197] comple ely ailed. I emains as a challenge o p o e, by heo y o by machine, ha 196 is he exac alue o WS(5). Ou cons uc ion showing WS(5)≥196 is gi en in Sec ion 2, oge he wi h easons poin ing o he p obable sha pness o his bound. In Sec ion 3, we ea he case o 6-pa i ions and ob ain WS(6)≥572, appa en ly he i s known ealis ic lowe bound on WS(6). Ou me hod is desc ibed in Sec ion 4. I in ol es ansla ing he p oblem o cons uc ing pa i ions o he desi ed ype in o a Boolean sa is iabili y p oblem, o be handled by a SAT sol e . The ac ual compu a ions a e b ie ly commen ed in Sec ion 5. 2. Is i ue ha WS(5)=196? The e a e no de ails in [12] subs an ia ing he claim WS(5)=196, no e en an ac ual pa i ion o [1, 196] in o 5 weakly sum- ee subse s which would es ablish WS(5)≥196. Su ely Walke knew such pa i ions, bu we do no know how he p oceeded, and hese a e p obably los o e e . He e we ill his li e a u e gap by p o iding one such pa i ion, cons uc ed using he me hods o Sec ion 4and he SAT sol e ma ch [17]. As a ma e o no a ion, we shall abb e ia e uns o consecu i e in ege s as in e als. Fo ins ance, [8, 9] 12 [14, 17] s ands o he se {8,9,12,14,15,16,17}. Theo em 2.1. WS(5)≥196. P oo . Conside he ollowing pa i ion A1⊔A2⊔A3⊔A4⊔A5o [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. I is s aigh o wa d o check ha each Aiis weakly sum- ee. This inishes he p oo .  Is his lowe bound on WS(5)sha p? I no , he e would exis a pa i ion o [1, 197] in o 5 weakly sum- ee se s. In o de o y and ind one, we applied he same me hods as abo e. Bu hese a emp s comple ely ailed, as no conclusion o exis ence o non-exis ence was eached a e se e al weeks o unning ime. This s ongly suppo s Walke ’s claim. Ye i emains as an open p oblem o p o e o disp o e he inequali y WS(5)≤196. 2.1. Fixing he 5 h pa He e a e wo mo e compu a ional esul s in suppo o Walke ’s claim. Fixing he 5 h pa o a en a i e pa i ion o [1,n] in o 5 weakly sum- ee se s educes he numbe o Boolean a iables in ol ed in ou me hod om 3n o 2n. The eason, made clea in Sec ion 4, is ha ⌈log2(5)⌉ = 3 whe eas ⌈log2(4)⌉ = 2. This educ ion allows ma ch o e mina e i s compu a ions and each de ini i e conclusions, e en o n=197. The ollowing esul s we e ob ained in his way. The i s s a emen concludes an a emp o imp o e Theo em 2.1 by cons uc ing a pa i ion o [1, 197] in o 5 weakly sum- ee se s, while keeping he same 5 h pa A5. No su p isingly, he conclusion is nega i e. Compu a ional Theo em 2.2. The e is no pa i ion o [1,197]in o 5weakly sum- ee pa s wi h A5= [67,68] ∪ [70,134] ∪ {136}as one pa . Ou second s a emen deals wi h he ollowing ques ion: o wha ex en is i possible o eplace A5in Theo em 2.1 by a single in e al? Mo e p ecisely, we looked o he la ges possible n o which [1,n]admi s a pa i ion in o 5 weakly sum- ee se s B1,...,B5such ha : •B1,B2,B3,B4is a pa i ion o [1, 66], •B5is a single in e al. Obse e ha he i s equi emen is sa is ied by A1,A2,A3,A4in Theo em 2.1, and ecall ha 66 =WS(4). Consequen ly, B5mus con ain 67 and canno be s ic ly la ge han [67, 134]. Thus, wi hou loss o gene ali y, we may and will assume B5= [67,134]. Qui e su p isingly, he la ges admissible n u ns ou o be n=194 only. Compu a ional Theo em 2.3. The la ges n o which [1,n]admi s a pa i ion in o 5weakly sum- ee pa s, wi h [67,134]as one pa , is n =194. Fo he eco d, he e is such a pa i ion o [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 wo esul s we e eached in abou 17 and 18 h, espec i ely, on a 3.33 GHz In el i7 p ocesso PC wi h he SAT sol e ma ch. 3. A lowe bound on WS(6) We ob ain he e he lowe bound WS(6)≥572, by exhibi ing a sui able pa i ion o [1, 572] in o 6 weakly sum- ee subse s. Ins uc ed by a ai amoun o expe imen a ion, we hink ha his bound is qui e ealis ic, wi h a ma gin o e o possibly less han 10. In he pa i ion below, we keep he same no a ional con en ion wi h in e als as in he p eceding sec ion. Theo em 3.1. WS(6)≥572. P oo . Conside he ollowing pa i ion A1⊔A2⊔A3⊔A4⊔A5⊔A6o [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, i is s aigh o wa d o check ha each Aiis weakly sum- ee.  The only p e iously a ailable i m lowe bound on WS(6)was 536, which is he lowe bound o S(6)gi en in [3]. Ano he lowe bound could be ob ained om he claimed inequali y WS(k)≥3(3k+2k−1)/4−1, which gi es 554 a k=6. Howe e , his inequali y does no seem o be backed up by any a ailable p oo . I is a ibu ed o B aun in [12]. No e ha i is sha p o k=1,2,3, and gi es 65 =WS(4)−1 a k=4. 4. Re o mula ion as a SAT p oblem Ou idea o cons uc ing he abo e pa i ions is o exp ess he co esponding combina o ial cons ain s as Boolean sa is iabili y p oblems, o be hen ed o a SAT sol e . See [18–21] o ea lie success ul uses o SAT sol e s in combina o ial numbe heo y. Recall ha a logical o mula o e Boolean a iables x1,...,xnis said o be sa is iable i he e is an assignmen o he xi’s o T ue o False in such a way ha he o mula e alua es o T ue. Le n,k≥2. Le T1,...,T be a amily o subse s o [1,n]. Assume ha we a e seeking k-colo ings o [1,n] o which no Tjis monoch oma ic. Such k-colo ings co espond o cou se o k-pa i ions o [1,n] o which no Tjis con ained in a single pa . We shall ansla e his exis ence p oblem in o one asking whe he some associa ed logical o mula is sa is iable o no . In he applica ions in Sec ion 5, he subse s Tjwill be all possible iples in [1,n]o he o m {a,b,a+b}wi h a= b. I is some imes con enien o exp ess logical o mulas in conjunc i e no mal o m, o CNF o sho . Tha is, as conjunc ions  l=1 Cl(3) o clauses C1,...,Cl, a clause being a disjunc ion o he o m xi1∨ · · · ∨ xis∨ ¬xj1∨ · · · ∨ ¬xj . He e, as usual, he symbols ∧,∨and ¬deno e he logical ope a ions AND, OR and NOT, espec i ely. Mos o mulas below a e in CNF. F om now on, we shall w i e 1 o T ue and 0 o False. In pa icula , we ha e ¬1=0 and ¬0=1. 4.1. The case k =2 We s a wi h wo colo s. Le x1,...,xnbe nBoolean a iables. The e is a bijec i e co espondence be ween {0,1}- assignmen s o he xi’s and 2-colo ings o [1,n]. Fo a subse T⊂ [1,n], de ine he CNF o mula cl2(T, (x1,...,xn)) = i∈T xi∧ i∈T ¬xi.(4) Lemma 4.1. Le T ⊂ [1,n]. The 2-colo ings o [1,n] o which T is non-monoch oma ic co espond o he {0,1}-assignmen s xi=ϵi(i=1,...,n) o which cl2(T, (ϵ1, . . . , ϵn)) =1. P oo . By cons uc ion, cl2(T, (ϵ1, . . . , ϵn)) =1 i and only i he e a e indices i,j∈Tsuch ha ϵi= ¬ϵj=1, o equi alen ly ϵi=1 and ϵj=0; his happens i and only i Tis non-monoch oma ic o he co esponding 2-colo ing o [1,n]. When se e al subse s o [1,n]a e equi ed o be simul aneously non-monoch oma ic, i su ices o sa is y he conjunc ion o he co esponding o mulas. This yields he ollowing equi alence. P oposi ion 4.2. Le n ≥1and le T1,...,T be subse s o [1,n]. Le x1,...,xnbe Boolean a iables. The e exis s a 2-colo ing o [1,n]such ha no Tjis monoch oma ic i and only i he o mula  j=1 cl2(Tj, (x1,...,xn)) is sa is iable.  4.2. The case k =2 We i s ex end he abo e conside a ions o k=2 o any in ege ≥1. Ou se o 2 colo s is aken o be he Ca esian p oduc {0,1} . Le (xi,l) (1≤i≤n,1≤l≤ )be a collec ion o n Boolean a iables. The unknown colo o any i∈ [1,n]may and will be ep esen ed by he - uple (xi,1,...,xi, ). Le T⊂ [1,n]. The 2 -colo ings o [1,n] o which Tis non-monoch oma ic co espond o hose {0,1}-assignmen s (ϵi,l)o (xi,l) o which he e a e indices l∈ [1, ]and i,j∈Tsuch ha ϵi,l= ϵj,l. By he case o wo colo s, his condi ion is equi alen o he Boolean one cl2(T, (ϵ1,l, . . . , ϵn,l)) =1. Since indices lwhe e a di e ence occu s may be a bi a y, one needs o ake he disjunc ion o e all l∈ [1, ]o he abo e o mula. Mo eo e , when se e al subse s o [1,n]a e in ol ed, he conjunc ion o he co esponding o mulas mus be sa is ied. This yields he ollowing gene aliza ion o P oposi ion 4.2. P oposi ion 4.3. Le n, ≥1and le T1,...,T be subse s o [1,n]. Le (xi,l)(1≤i≤n,1≤l≤ )be n Boolean a iables. The e exis s a 2 -colo ing o [1,n]such ha no Tjis monoch oma ic i and only i he o mula  j=1  l=1 cl2(Tj, (x1,l,...,xn,l)) is sa is iable.  This o mula is no in CNF, bu his can be ixed using he dis ibu i i y o ∨o e ∧. To wi , an equi alen CNF o mula is gi en by  j=1  U⊔V=[1, ]   i∈Tj u∈U xi,u ∨  i∈Tj ∈V ¬xi,    , whe e ⊔deno es a disjoin union. 4.3. The gene al case We now ea any numbe k≥2 o colo s. Le ≥1 be he unique in ege such ha 2 −1+1≤k≤2 . Tha is, = ⌈log2(k)⌉. Wi hin he se {0,1} o 2 colo s, we o bid some 2 −kones. The emaining kcolo s hen cons i u e ou inal pale e o colo s. I emains o ansla e he equi emen ha some colo s a e o bidden in o he sa is iabili y o app op ia e Boolean o mulas. Fo his, i su ices o conside a single o bidden colo ; he case o se e al ones ollows by aking he conjunc ion o he co esponding o mulas. Fi s obse e ha , o x,y∈ {0,1}, he condi ion x= yis equi alen o he logical o mula (x∨y)∧(¬x∨ ¬y)=1. Now, le µ=(µ1, . . . , µ )∈ {0,1} be a ixed colo . Gi en Boolean a iables z1,...,z , de ine µ(z1,...,z )=  l=1 (zl∨µl)∧(¬zl∨ ¬µl). I hen ollows om he abo e obse a ion ha , o all ϵ=(ϵ1, . . . , ϵ )∈ {0,1} , we ha e ϵ= µ⇔ µ(ϵ) =1. Thus, o bidding colo µmay be achie ed using o mula µ. This yields he ollowing esul . Theo em 4.4. Le n,k, be in ege s wi h k,n≥2and 2 −1+1≤k≤2 . Le T1,...,T be subse s o [1,n]. The exis ence o k-colo ings o [1,n] o which no Tjis monoch oma ic is equi alen o he sa is iabili y o he o mula  j=1  l=1 cl2(Tj, (x1,l,...,xn,l))∧ n  i=1 2 −k  s=1 µs(xi,1,...,xi, ), whe e µ1, . . . , µ2 −kis any choice o 2 −k dis inc elemen s in {0,1} . P oo . By P oposi ion 4.3, sa is ying he le -hand sub o mula gi es 2 -colo ings o [1,n]wi h no Tjmonoch oma ic. Sa is ying he igh -hand one gua an ees ha no µsis used in hose colo ings.  5. Applica ions The abo e esul implies he ollowing SAT cha ac e iza ion o he weak Schu numbe s, made explici o comple eness. Co olla y 5.1. Le n,k, be in ege s, wi h k,n≥2and 2 −1+1≤k≤2 . The ollowing condi ions a e equi alen . 1. WS(k)≥n. 2. The o mula  a<b  l=1 cl2({a,b,a+b}, (x1,l,...,xn,l))∧ n  i=1 2 −k  j=1 µj(xi,1,...,xi, ) is sa is iable, whe e a,b un o e all in ege s sa is ying 1≤a<b≤n−a−b, and whe e µ1, . . . , µ2 −ka e any 2 −k elemen s in {0,1} . Mo eo e , e e y a iable assignmen o which he abo e o mula is sa is ied co esponds o an ac ual pa i ion o [1,n]in o k weakly sum- ee subse s. P oo . This di ec ly ollows om he de ini ion o WS(k)and om Theo em 4.4, specialized o he case whe e he subse s Tjo [1,n]a e all iples {a,b,a+b}wi h a<b. This SAT e o mula ion, oge he wi h he SAT sol e ma ch, allowed us o cons uc he weakly sum- ee pa i ions o Sec ions 2and 3. Recall ha hese pa i ions yield he lowe bounds WS(5)≥196 and WS(6)≥572, espec i ely. Ou Compu a ional Theo ems 2.2 and 2.3 we e ob ained wi h hose same ools. Howe e , o his a ack on WS(5)and WS(6), he co esponding SAT p oblems a e somewha oo la ge. In o de o educe he numbe o a iables and clauses, we pe o med expe imen s wi h selec ed elemen s o [1,n]p e-loca ed in he same pa o he en a i e pa i ions. Fo ins ance, we looked o 5-pa i ions o [1, 196] in o weakly sum- ee se s which would ex end chosen 4-pa i ions o [1, 66], whe e 66 =WS(4). This emo es many a iables. Wi hou such educ ions, i seems di icul o a SAT sol e o cons uc om sc a ch a pa i ion o [1, 196] o he desi ed ype, le alone o conclude WS(5) < 197. The case k=4, in con as , can be ully handled. We we e able o eco e he known alues WS(4)=66 and S(4)=44, he la e wi h a SAT cha ac e iza ion o S(k)simila o ha o WS(k)abo e. The co esponding unning imes a e displayed below. Ou pu Conclusion Time in seconds A sui able 4-pa i ion o [1, 44] S(4)≥44 0 ‘‘Unsa is iable’’ S(4) < 45 60 A sui able 4-pa i ion o [1, 66] WS(4)≥66 917 ‘‘Unsa is iable’’ WS(4) < 67 24,450 We con i med he equali y WS(4)=66 by unning ma ch on wo dis inc iles embodying Co olla y 5.1, namely wschu 4_66. x and wschu 4_67. x . These iles a e a ailable a [22], o he eade wishing o ep oduce hese compu a ions wi h any SAT sol e . They con ain, in s anda d DIMACS o ma , a lis o CNF clauses whose sa is iabili y o no is equi alen o he exis ence o no o a sui able 4-pa i ion o [1, 66] and [1, 67], espec i ely. The ile wschu 4_66. x con ains 4224 clauses on 132 Boolean a iables. I s i s clause eads 1 2 3 67 68 69 0, wi h 0 as a closing symbol, and codes o x1∨x2∨x3∨x67 ∨x68 ∨x69. I s nex clause eads −1−2−3 67 68 69 0 and codes o ¬x1∨ ¬x2∨ ¬x3∨x67 ∨x68 ∨x69. Any SAT sol e unning i should end up displaying an assignmen o he a iables ha will sa is y all he clauses. As o he ile wschu 4_67. x , which con ains 4356 clauses on 134 Boolean a iables, any SAT sol e unning i should conclude ha i s se o clauses is unsa is iable. We end wi h a ew echnical de ails. The e sion o ma ch we used was ma ch_hi [17], unning on an In el i7 p ocesso PC wi h a CPU clock speed o 3.33 GHz and 16 GB o RAM memo y. As a as we know, he mul i-co e a chi ec u e o he CPU is no exploi ed by his implemen a ion o ma ch_hi. Acknowledgmen s We hank Amine Boumaza, Jona han Chappelon, Philippe Ma ion, Vi ginie Ma ion-Po y, Denis Robillia d and Dominique Ve haghe o help ul discussions and/o echnical help du ing he p epa a ion o his pape . We also hank bo h e e ees o hei ca e ul eading and e y use ul commen s. No e. While his pape was being e e eed, ou colleagues Amine Boumaza, Cy il Fonlup , Vi ginie Ma ion-Po y and Denis Robillia d succeeded in imp o ing ou lowe bound on WS(6), om 572 o 574. They used a comple ely di e en me hod, namely an enhanced abu sea ch scheme. See hei o hcoming pape , o appea in he p oceedings o A i icial E olu ion 2011. No e added in p oo . We ha e u he imp o ed he lowe bound on WS(6), which is now gi en by WS(6) ≥575. Re e ences [1] Robe W. I ing, An ex ension o Schu ’s heo em on sum- ee pa i ions, Ac a A i h. 25 (1973/74) 55–64. [2] Issai Schu , Ube die Kong uenz xm+ym≡zm(mod p), Jah esbe . Deu sch. Ma h.-Ve ein. 25 (1916) 114–117. [3] Ha old F ed icksen, Mel in M. Swee , Symme ic sum- ee pa i ions and lowe bounds o Schu numbe s, Elec on. J. Combin. 7 (2000) Resea ch Pape 32, 9, elec onic. [4] Geo ey Exoo, A lowe bound o Schu numbe s and mul icolo Ramsey numbe s o K3, Elec on. J. Combin. 1 (1994) Resea ch Pape 8, app ox. 3, elec onic. [5] S. Radziszowski, Small Ramsey numbe s, Elec on. J. Combin. 1 (1994) Dynamic Su ey DS1, Re ision #6 (1999), 35, elec onic. [6] M.I. Sanz, Núme os de Schu y de Rado, Ph.D Thesis, Depa amen o de Ma emá ica Aplicada I, Uni e sidad de Se illa, 2010. [7] Leona d D. Baume , Sum- ee se s, J.P.L. Res. Summa y 1 (36–10) (1961) 16–18. [8] Solomon W. Golomb, Leona d D. Baume , Back ack p og amming, J. Assoc. Compu . Mach. 12 (1965) 516–524. [9] R. Rado, Some sol ed and unsol ed p oblems in he heo y o numbe s, Ma h. Gaz. 25 (1941) 72–77. [10] Pe e F. Blancha d, F ank Ha a y, Roge io Reis, Pa i ions in o sum- ee se s, In ege s 6 (A7) (2006) 10, elec onic. [11] A. Soi e , The Ma hema ical Colo ing Book. Ma hema ics o Colo ing and he Colo ul Li e o i s C ea o s, Sp inge , New Yo k, ISBN: 978-0-387-74640-1, 2009. [12] G.W. Walke , A p oblem in pa i ioning, Ame . Ma h. Mon hly 59 (1952) 253. [13] W. Sie piński, Elemen a y heo y o numbe s. T ansla ed om Polish by A. Hulanicki. Monog a ie Ma ema yczne, Tom 42 Pańs wowe Wydawnic wo Naukowe, Wa saw, 1964. [14] Pie e Bo nsz ein, On an ex ension o a heo em o Schu , Ac a A i h. 101 (2002) 395–399. [15] H.L. Abbo , D. Hanson, A p oblem o Schu and i s gene aliza ions, Ac a A i h. 20 (1972) 175–187. [16] R.L. G aham, B.L. Ro hschild, J.H. Spence , Ramsey heo y. Second edi ion. Wiley-In e science Se ies in Disc e e Ma hema ics and Op imiza ion, John Wiley & Sons, Inc., New Yo k, 1990. [17] h p://www.s .ewi. udel .nl/sa /. [18] Michael R. D ans ield, Lengning Liu, Vic o W. Ma ek, Mi oslaw T uszczyński, Sa is iabili y and compu ing an de Wae den numbe s, Elec on. J. Combin. 11 (1) (2004) Resea ch Pape 41, 15, elec onic. [19] P.R. He wig, M.J.H. Heule, P.M. an Lambalgen, H. an Maa en, A new me hod o cons uc lowe bounds o an de Wae den numbe s, Elec on. J. Combin. 14 (2007) Resea ch Pape 6, 18, elec onic. [20] M. Kou il, J.L. Paul, The an de Wae den numbe W(2,6)is 1132, Expe imen . Ma h. 17 (2008) 53–61. [21] D. Robillia d, A. Boumaza, V. Ma ion-Po y, Me a-heu is ic sea ch and squa e E ickson ma ices, in: P oceeding o he IEEE Cong ess on E olu iona y Compu a ion (CEC’10), pp. 3237–3244, IEEE, 2010. [22] h p://www-lmpa.uni -li o al. /~eliahou/schu /.