ZERO-SUM BALANCED BINARY SEQUENCES
S. Eliahou
LMPA-ULCO, Labo a oi e de Ma h´ema iques Pu es e Appliqu´ees Joseph Liou ille, Uni e si e´ du Li o al
Cˆo e d’Opale, B.P. 699, 62228 Calais cedex, F ance
[email p o ec ed]
J.M. Ma ı´n
Escuela Uni e si a ia de A qui ec u a T´ecnica, Depa amen o de Ma em´a ica Aplicada I, A enida Reina
Me cedes 4, C.P. 41012 Se illa, Spain
[email p o ec ed]
M.P. Re uel a1
Escuela Uni e si a ia de A qui ec u a T´ecnica, Depa amen o de Ma em´a ica Aplicada I, A enida Reina
Me cedes 4, C.P. 41012 Se illa, Spain
[email p o ec ed]
Abs ac
F
whic
o
h
e
is
e y p
balanced,
osi i e in
i.e.,
ege
whose
n ≡ 0
asso
mod
cia ed
4, we
S einhaus
cons uc a
iangle
ze o-sum
con ains
{±1}
as man
-sequence
y +1’s
o
as
leng h
1’s.
n
This implies he exis ence o balanced bina y sequences o e e y leng h m 0 o 3 mo
−
d 4,
≡ he eby
p o iding a new solu ion o a p oblem posed by S einhaus in 1963.
1. In oduc ion
Le X = x1x2 . . . xn be a bina y sequence o leng h n, wi h xi = ±1 o all i. We de ine i s
de i ed sequence ∂X by ∂X = y1y2 . . . yn−1, whe e yi is he p oduc o xi and xi+1 o
all i. This is a bina y sequence again, o leng h n − 1. By con en ion, ∂X = ∅ i n ≤ 1,
whe e ∅ s ands o he emp y sequence o leng h 0. I e a ing he de i a ion p ocess, we deno e
by ∂kX he k h de i ed sequence o X, de ined ecu si ely as usual by ∂0X = X and
∂kX=∂(∂k−1X) o k≥1.
The S einhaus iangle (o de i ed iangle) o Xis he collec ion ∆X={X, ∂X,...,∂n−1X}
1Pa ially suppo ed by p ojec s ORI and PAI FQM-164
o i e a ed de i ed sequences o X. Fo example, i X=++−+, hen
∆X=
+ + −+
+− −
−+
−
.
De ini ion 1 Le Xbe a ini e bina y sequence. We say ha X
•is ze o-sum i i s en ies sum o 0;
•is balanced i i s S einhaus iangle ∆Xis ze o-sum, i.e., i he en ies o ∆Xsum o 0.
Fo example, he abo e bina y sequence X= ++−+ is balanced, as i s S einhaus
iangle con ains exac ly 5 +’s and 5 −’s. This concep was in oduced by S einhaus in [4]
wi h he ollowing p oblem: does he e exis a balanced bina y sequence o leng h m, o
e e y m≡0 o 3 mod 4? (Wi hou his necessa y condi ion, ∆Xwould con ain an odd
numbe o e ms.) S einhaus’ p oblem was i s sol ed posi i ely by Ha bo h in 1972 [3].
New solu ions wi h special p ope ies, such as symme y/an isymme y o ins ance, ecen ly
appea ed in [1] and [2].
The p esen pape is conce ned wi h bina y sequences Xwhich a e bo h ze o-sum and
balanced, o equi alen ly, such ha bo h Xand ∂Xa e balanced. We show ha such
sequences exis in all leng hs n= 4k.
Theo em 2 Fo e e y posi i e in ege n≡0 mod 4, he e exis s a bina y sequence Xo
leng h nwhich is bo h ze o-sum and balanced.
This esul p o ides one mo e solu ion o S einhaus’ o iginal p oblem.
Co olla y 3 Fo e e y posi i e in ege m≡0o 3 mod 4, he e exis s a bina y sequence
X, o leng h m, which is balanced.
P oo . I m≡0 mod 4, we a e done by Theo em 2. I m≡3 mod 4, hen by Theo em 2
again, he e exis s a bina y sequence Yo leng h n=m+ 1 which is bo h ze o-sum and
balanced. Se X=∂Y. No e ha he de i ed iangle ∆Yis he conca ena ion o Y(as i s
i s line) and o ∆X. Now, since Yand ∆Ya e bo h ze o-sum, i ollows ha ∆Xi sel is
ze o-sum. This means ha Xis a balanced bina y sequence o leng h m, as needed.
Theo em 2 answe s a p oblem p oposed by M. Ke ai e and lis ed as open in [1]. I s
p oo is gi en in Sec ion 2. The ele an sequences ha e been cons uc ed by an algo i hmic
p ocedu e explained in Sec ion 3 and e ined in Sec ion 4. The las sec ion desc ibes one
ins ance o unp edic able beha io in he cons uc ion p ocedu e.
2. Explici Solu ions
Gi en a bina y sequence X=x1x2...xno leng h nand an in ege 1 ≤i≤n, we deno e by
X[i] = x1...xi
he ini ial segmen o leng h io X, and by
X∞=x1x2...xnx1x2...xn...
he in ini e pe iodic sequence wi h pe iod X. I Y=y1y2... is ano he bina y sequence,
ini e o in ini e, we deno e by
X Y =x1x2...xny1y2...
he conca ena ion o Xand Y. I Y=y1...ymis ini e, we say ha he sequence
X Y ∞=x1x2...xny1...ymy1...ym...
is e en ually pe iodic, wi h ini ial segmen Xand pe iod Y.
Theo em 4 Le S0=I0P∞
0and S4=I4P∞
4be he e en ually pe iodic in ini e bina y
sequences wi h espec i e ini ial segmen s
I0=+ −−+−+−+
I4=−−++++−−
o leng h 8, and pe iods
P0=−−−+−+++−−+−+−++++−−−−++
P4=−+−++−−−−+++−−+−+−++−+ +−
o leng h 24. Then, o e e y in ege m≥0, he ini ial segmen s S0[8m]o leng h 8mo S0,
and S4[8m+ 4] o leng h 8m+ 4 o S4, a e bo h ze o-sum and balanced.
This is Theo em 2 again, in a mo e de ailed e sion. The emainde o his Sec ion is
de o ed o i s p oo . As such sequences a e ha d o dig ou wi h he equi ed p ope ies, we
shall explain in he nex wo sec ions how hey we e disco e ed.
P oo .
•The case o S0[8m].Le T8m=∆S0[8m] deno e he de i ed iangle o S0[8m].
We shall show ha T8mis made o 10 b icks, all iangles and diamonds o sideleng h 8,
assembled in an e en ually pe iodic s uc u e. I will he e o e be easy o compu e he en y
sum o T8mand show, as equi ed, ha i equals ze o.
Figu e 1: S uc u e o he De i ed T iangle T8mo S0[8m]
Gi en any collec ion Xo ±1’s, we deno e by σ(X) he sum o i s en ies.
Fi s , i is easily checked ha σ(S0[8m]) = 0, using he e en ual pe iodici y o he
sequence S0=I0P∞
0. Indeed, we ha e σ(I0) = 0, and P0is he conca ena ion o h ee
sequences o leng h 8 each summing o 0.
We mus u he show ha σ(T8m) = 0 as well. Assume o he momen ha T8mis
s uc u ed as in Figu e 1, wi h wo ypes o b icks: iangles named T0, T a, Tb, Tc, and
diamonds named L1, L2, L3, Ra, Rb, Rc. He e a e hese 10 building b icks.
+−−+−+−+
−+−−−−−
−−+ + ++
+−+++
−−++
+−+
−−
+
T0
−−−+−+ ++
++−−−+ +
+−++−+
−−+− −
+− −+
−+−
−−
+
T a
−−+−+−++
+−−−−−+
−++++−
−+++−
−+ +−
−+−
−−
+
T b
++−−−−++
+−+++−+
−−++−−
+−+−+
− − −−
+++
++
+
T c
−
+−
+− −
+−++
+−−+ +
+−+−+−
−−−−−−+
−+++++−+
−++++− −
−+++−+
−++− −
−+−+
−−−
++
+
L1
+
−+
−−−
+++−
+++−+
−++− −+
−−+−+−+
−+−−−−−+
−−++++−
+−+++−
−−++−
+−+−
−−−
++
+
L2
−
+−
−−+
++−−
−+−+ +
+−−−+−
+−++−−+
+−−+−+−+
−+−−−−−
−−+ + ++
+−+++
−−++
+−+
−−
+
L3
−
−−
−+ +
+−+−
+−−−+
−−++−−
++−+−+ +
++−−−−++
+−+++−+
−−++−−
+−+−+
− − −−
+++
++
+
Ra
+
++
−+−
+− −−
−−+++
++−+ ++
−+−−+++
−−−+−+ ++
++−−−+ +
+−++−+
−−+− −
+− −+
−+−
−−
+
Rb
−
−−
++−
++−+
−+−−+
−−−+−−
−++−−+ +
−−+−+−++
+−−−−−+
−++++−
−+++−
−+ +−
−+−
−−
+
Rc
As easily checked, hese b icks ha e he ollowing en y sums:
σ(T0)= 0;
σ(Ta)=−2,σ(Tb)=−2,σ(Tc)= 4;
σ(L1)= 2,σ(L2)= 0,σ(L3)=−2;
σ(Ra)= 2,σ(Rb)= 4,σ(Rc)=−6.
Wi h his s uc u e, i is easy o ge σ(T8m) = 0, by induc ion on m. Fi s no e ha he
iangle T8m+8 is ob ained by gluing a band o wid h 8 o he igh side o he iangle T8m.
We call i he band di e ence om T8m o T8m+8. Fo he induc ion s ep, i su ices o check
ha hese band di e ences all ha e en y sum 0.
Fo m= 1, we ha e T8=∆I0=T0, and hus σ(T8) = 0. Fo m= 2, he band di e ence
om T8 o T16, being made o he wo b icks Ta and L1, has en y sum σ(T a) + σ(L1) = 0.

Fo m= 3, he band di e ence om T16 o T24 is made o he b icks Tb,Ra and L2, and
hus again has en y sum 0. Finally, o m= 4, he band di e ence om T24 o T32 is made
o he b icks T c,Rb,Rc and L3, and hence also has en y sum 0.
Assume now m≥5. By he induc ion hypo hesis, we ha e σ(T8k) = 0 o all 1 ≤k≤
m−1. Now obse e on Figu e 1 ha , by pe iodici y, he band di e ence om T8(m−1) o
T8mis made o he same b icks as he band di e ence om T8(m−4) o T8(m−3), plus he h ee
supplemen a y b icks Ra,Rb and Rc. Since σ(Ra) + σ(Rb) + σ(Rc) = 0, i ollows ha his
band di e ence has en y sum 0 and, consequen ly, σ(T8m) = 0 as claimed.
I emains o p o e ha he s uc u e o he iangle T8mis indeed as depic ed in Figu e
1. Le A, B be any wo b icks om he se
{T0, Ta, T b, Tc, L1, L2, L3, Ra, Rb, Rc},
and assume ha hey a e adjacen , in he sense ha , somewhe e in he iangle T8m, he
igh mos en y o some b ick labelled Ais on he same line as, and le -adjacen o, he
le mos en y o some b ick labelled B. Fo ins ance, he b icks T0, T a a e adjacen , and
so a e he b icks L1, Ra.
Clea ly, by he de ining p ope y o de i ed iangles, wo adjacen b icks A, Bin T8m
de e mine a unique diamond loca ed on he sou heas o Aand on he sou hwes o B, ha
we deno e A∗B. Fo ins ance, T0∗T a =L1 and Ta ∗T b =Ra.
The s uc u e o T8m, as depic ed in Figu e 1, now simply ollows om he easily checked
ela ions: Ta ∗T b=Ra, Tb ∗T c=Rb, Tc ∗T a=Rc
T0∗Ta=L1, L1∗Ra=L2, L2∗Rc=L3
Ra ∗Rb=Rc, Rb ∗Rc=Ra, Rc ∗Ra=Rb
L3∗Rb=L1.
The a gumen p oceeds as ollows. By de ini ion o S0[8m] and o i s de i ed iangle,
he i s line o b icks in T8mis he ul ima ely pe iodic sequence
T0, Ta, T b, Tc, T a, Tb, Tc, . . . .
Now, i ollows om he abo e ela ions ha he second b ick line in T8mis he ul ima ely
pe iodic sequence
L1, Ra, Rb, Rc, Ra, Rb, Rc, . . . .
Simila ly, he hi d, ou h and i h b ick lines in T8ma e, espec i ely, he sequences
L2, Rc, Ra, Rb, Rc, Ra, Rb, . . . ,
L3, Rb, Rc, Ra, Rb, Rc, Ra, . . . ,
L1, Ra, Rb, Rc, Ra, Rb, Rc, . . . .
Figu e 2: S uc u e o he De i ed T iangle T8m+4 o S4[8m+ 4]
Since he i h b ick line is equal o he second one, pe iodici y ollows. This es ablishes he
claimed s uc u e o T8m, and hence he equali y σ(T8m) = 0.
•The case o S4[8m+ 4].We deno e by T8m+4 he de i ed iangle o S4[8m+ 4].
This case is simila hough sligh ly mo e complica ed, since mo e b icks a e needed o make
up T8m+4. Ac ually 19 b icks a e needed: he iangle T0 o sideleng h 4, he iangles
T1, Ta, T b, Tc and he diamonds S1, Sa, Sb, Sc, Ra, Rb, Rc, L1, L2, L3 o sideleng h 8, and
inally he pa allelog ams S0, h1, h2, h3 o size 4 ×8. (See Figu e 2.) No e ha he com-
mon symbols be ween he wo cases do no depic he same b icks. We shall only display
T0, T1, T a, Tb, T c; he o he b icks can easily be econs uc ed by he de ining p ope y o
de i ed iangles. We shall, howe e , gi e he en y sums o all he b icks.
−−++
+−+
−−
+
T0
++−−−+−+
+−++−−−
−−+−++
+−−−+
−+ +−
−+−
−−
+
T1
+−−−−+ ++
−+++−+ +
−++− −+
−+−+−
− − −−
+++
++
+
T a
−−+−+−++
+−−−−−+
−++++−
−+++−
−+ +−
−+−
−−
+
T b
−++−−+−+
−+−+−−−
−−−−++
+++−+
++−−
+−+
−−
+
T c
The 19 building b icks ha e he ollowing en y sums. F om his da a and Figu e 2, i is
s aigh o wa d o check ha σ(T8m+4) = 0, as equi ed.
σ(T0) = 0 σ(T1)=−4σ(T a) = 4 σ(Tb) = −2σ(Tc) = −2
σ(S0) = 4 σ(S1)=−4σ(Sa) = −6σ(Sb) = −10 σ(Sc) = −4
σ(h1) = 0 σ(L1) = 10 σ(Ra) = −4σ(Rb) = 2 σ(Rc) = 2
σ(h2)=−2σ(L2) = 18 σ(h3)=−2σ(L3)=−4
The ac ha T8m+4 does ha e he s uc u e depic ed in Figu e 2 uses he same ype o
a gumen as in he p eceding case; namely, ha i A, B a e wo adjacen b icks, hen hey
uniquely de e mine a hi d b ick deno ed A∗B, lying sou heas o Aand sou hwes o B.
3. The Cons uc ion Me hod
The p incipal idea, as in [1], is o seek s ong solu ions, i.e., solu ions swi h he p ope y
ha all ini ial segmen s o so p esc ibed leng hs a e also solu ions. On he one hand, his
makes he p oblem easie o explo e by compu e , as s ong solu ions can be cons uc ed
by ex ending hose al eady ob ained in smalle leng hs. On he o he hand, his s onge
equi emen migh o ce ini ely many solu ions only. A balance mus be ound, hope ully
allowing s ong solu ions in all desi ed small leng hs, ye su icien ly sca ce so ha la ge
leng hs can s ill be explo ed and quasi-pe iodic solu ions, i any, can eme ge.
In [1], a bina y sequence Xo leng h nis called s ongly balanced i all i s ini ial segmen s
o leng h m, wi h m≡nmod 4, a e also balanced. Now his condi ion u ns ou o be oo
s ong he e: i Xhas he p ope y ha all i s ini ial segmen s o leng h m≡nmod 4 a e
bo h ze o-sum and balanced, hen n= 0, 4, o 8.
A weake cons ain consis s in equi ing only ha ini ial segmen s o Xo leng h m≡
nmod 8 (ins ead o mod 4) be ze o-sum and balanced. Bu hen an opposi e di icul y
eme ges: he numbe o s ong solu ions hus de ined seems o explode wi h n, making i
e y ha d o unco e easy- o-desc ibe quasi-pe iodic solu ions.
One way ou consis s in es ic ing he se o allowed ex ensions o leng h 8 o al eady
cons uc ed s ong solu ions. This idea does wo k and has allowed us o ob ain Theo em 4.
Howe e , i equi es some ine- uning. Indeed, depending on he se o allowed ex ensions,
he esul ing cons uc ion algo i hms exhibi comple ely di e en beha io s. In some in-
s ances, he p ocess dies ou a e a ew s eps. In mo e a o able cases, a e a igo ous
ini ial g ow h, he numbe o s ong solu ions dec eases and becomes pe iodic. Finally, in
ye o he cases, he numbe o s ong solu ions seems o explode. We shall p esen ins ances
o all hese phenomena, ending wi h a ela ed easy- o-s a e bu e y challenging open p ob-
lem.
To p oceed wi h mo e de ails, we need he ollowing no a ion.
No a ion 5 We deno e by ZBn he se o all ze o-sum balanced bina y sequences o leng h
n, and by SZBn he subse o ZBnde ined as
SZBn={X∈ZBn:X[m]∈ZBm o e e y m≡nmod 8}.
He e again, X[m] deno es he ini ial segmen o leng h mo X. The elemen s o SZBnwill
be called s ongly ze o-sum-balanced sequences. Clea ly, i ZBn)=∅ hen n≡0 mod 4. Ou
pu pose is o es ablish he con e se. We shall in ac show ha he subse SZBnis nonemp y
whene e n≡0 mod 4.
The e is a simple algo i hm o cons uc he se SZBn+8 assuming we al eady know SZBn,
based on he ollowing.
Rema k 6 Fo each X∈SZBn, and o each ze o-sum bina y sequence zo leng h 8, he
ex ension Xz belongs o SZBn+8 i and only i Xz is balanced.
Indeed, Xz is ze o-sum as bo h Xand za e, and since Xis s ongly ze o-sum-balanced, i
ollows ha Xz is s ongly ze o-sum-balanced whene e i is simply balanced.
The s a ing poin s a e n= 4 and n= 8, whe e we ha e SZBn=ZBnby de ini ion.
Fi s , he numbe o ze o-sum bina y sequences o leng h 4 is !4
2"= 6 and, simila ly, i is
!8
4"= 70 in leng h 8. Among hese ze o-sum sequences, i is easy o selec hose which a e
balanced by cons uc ing hei S einhaus iangles. We ind:
SZB4={− − ++,−+−+,+−+−,++−−},
SZB8={+−−+−+−+,+−+−−+−+,+−+−+− −+,
−+−+−+ +−,−+−++−+−,−++−+−+−}.
S a ing om SZB8and using Rema k 6, i is algo i hmically easy o successi ely build
SZB16,SZB24,SZB32, e c. We ge he ollowing ca dinali ies.