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 /.