Synchronization Strings: Efficient and Fast Deterministic
Constructions over Small Alphabets∗
Kuan Cheng†

Bernhard Haeupler

‡

Xin Li§

Amirbehshad Shahrasbi

¶

Ke Wuk

arXiv:1803.03530v1 [cs.IT] 8 Mar 2018

March 12, 2018

Abstract
Synchronization strings are recently introduced by Haeupler and Shahrasbi [15] in the study
of codes for correcting insertion and deletion errors (insdel codes). A synchronization string
is an encoding of the indices of the symbols in a string, and together with an appropriate
decoding algorithm it can transform insertion and deletion errors into standard symbol erasures
and corruptions. This reduces the problem of constructing insdel codes to the problem of
constructing standard error correcting codes, which is much better understood. Besides this,
synchronization strings are also useful in other applications such as synchronization sequences
and interactive coding schemes. For all such applications, synchronization strings are desired to
be over alphabets that are as small as possible, since a larger alphabet size corresponds to more
redundant information added.
Haeupler and Shahrasbi [15] showed that for any parameter ε > 0, synchronization strings of
arbitrary length exist over an alphabet whose size depends only on ε. Specifically, [15] obtained
an alphabet size of O(ε−4 ), which left an open question on where the minimal size of such
alphabets lies between Ω(ε−1 ) and O(ε−4
 ). In this work, we partially bridge this gap by
 providing
an improved lower bound of Ω ε−3/2 , and an improved upper bound of O ε−2 . We also
provide fast explicit constructions of synchronization strings over small alphabets.
Further, along the lines of previous work on similar combinatorial objects, we study the
extremal question of the smallest possible alphabet size over which synchronization strings can
exist for some constant ε < 1. We show that one can construct ε-synchronization strings over
alphabets of size four while no such string exists over binary alphabets. This reduces the extremal
question to whether synchronization strings exist over ternary alphabets.

∗
Supported in part by NSF grants CCF-1527110, CCF-1618280, CCF-1617713 and NSF CAREER award CCF1750808.
†
kcheng17@jhu.edu. Department of Computer Science, Johns Hopkins University.
‡
haeupler@cs.cmu.edu. Department of Computer Science, Carnegie Mellon University
§
lixints@cs.jhu.edu. Department of Computer Science, Johns Hopkins University.
¶
shahrasbi@cs.cmu.edu. Department of Computer Science, Carnegie Mellon University
k
AshleyMo@jhu.edu. Department of Computer Science, Johns Hopkins University.

1

1

Introduction

This paper focuses on the study of a combinatorial object called synchronization string. Intuitively, a
synchronization string is a (finite or infinite) string that avoids similarities between pairs of intervals
in the string. Such nice properties and synchronization strings themselves can actually be motivated
from at least two different aspects: coding theory and pattern avoidance. We now discuss the
motivations and previous work in each aspect below.

1.1

Motivation and Previous Work in Coding Theory

The general and most important goal of the coding theory is to obtain a reliable transmission
of information in the presence of noise or adversarial error. Starting from the pioneering works
of Shannon, Hamming, and many others, coding theory has evolved into an extensively studied
field, with applications found in various areas in computer science. Regarding the general goal of
correcting errors, we now have a very sophisticated and almost complete understanding of how
to deal with symbol erasures and corruptions. On the other hand, the knowledge of codes for
synchronization errors such as insertions and deletions, has lagged far behind despite also being
studied intensively since the 1960s. In practice, this is one of the main reasons why communication
systems require a lot of effort and resources to maintain synchronization strictly.
One major difficulty in designing codes for insertion and deletion errors is that in the received
codeword, the positions of the symbols may have changed. This is in contrast to standard symbol
erasures and corruptions, where the positions of the symbols always stay the same. Thus, many of
the known techniques in designing codes for standard symbol erasures and corruptions cannot be
directly utilized to protect against insertion and deletion errors.
In this context, a recent work of Haeupler and Shahrasbi [15] introduced synchronization strings,
which enable a black-box transformation of Hamming-type error correcting codes to codes that
protect against insertions and deletions. Informally, a synchronization string of length n is an
encoding of the indices of the n positions into a string over some alphabet Σ, such that, despite
some insertion and deletion errors, one can still recover the correct indices of many symbols. With
the correct indices of these symbols, a standard error correcting code can then be used to recover the
original message. This then gives a code for insertion and deletion errors, which is the combination
of a standard error correcting code and a synchronization string.
The simplest example of a synchronization string is just to record the index of each symbol,
i.e, the string 1, 2, · · · , n. It can be easily checked that even if (1 − ε) fraction of these indices are
deleted, one can still correctly recover the positions of the remaining εn symbols. However, this
synchronization string uses an alphabet whose size grows with the length of the string. The main
contribution of [15] is to show that under a slight relaxation, there exist synchronization strings of
arbitrary length n over an alphabet with fixed size. Further, [15] provided efficient and streaming
methods to correctly recover the indices of many symbols from a synchronization string after being
altered by insertion and deletion errors. Formally, [15] defines ε-synchronization strings as follows.
A string S is an ε-synchronization string if the edit distance of any two consecutive substrings S[i, j)
and S[j, k) is at least (1 − ε)(k − i).
Using the construction and decoding methods for ε-synchronization strings, [15] gives a code
that for any δ ∈ (0, 1) and ε > 0, can correct δ fraction of insertion and deletion errors with rate
1 − δ − ε. Besides this, synchronization strings have found a variety of applications, such as in
synchronization sequences [22], interactive coding schemes [8, 9, 11, 10, 13, 19, 18, 16], coding
against synchronization errors [16, 17], and edit distance tree codes [3, 18].
For all such applications, synchronization strings are desired to be over alphabets that are as small

2

as possible, since a larger alphabet size corresponds to more redundant information added. Thus a
natural question here is how small the alphabet size can be. In [15], Haeupler and Shahrasbi showed
that ε-synchronization strings with arbitrary length exist over an alphabet of size O(ε−4 ), they also
gave a randomized polynomial time algorithm to construct such strings. In a very recent work [16],
they further gave various efficient deterministicconstructions for finite/infinite ε-synchronization
strings, which have alphabets of size poly ε−1 for some unspecified large polynomials. On the
other hand, the definition of synchronization strings implies that any ε−1 consecutive symbols in an
ε-synchronization string have to be distinct—providing an Ω ε−1 lower-bound for the alphabet
size.

1.2

Motivation and Previous Work in Pattern Avoidance

Apart from applications in coding theory and other communication problems involving insertions
and deletions, synchronization strings are also interesting combinatorial objects from a mathematical
perspective. As a matter of fact, plenty of very similar combinatorial objects have been studied
prior to this work.
A classical work of Axel Thue [26] introduces and studies square-free strings, i.e., strings that do
not contain two identical consecutive substrings. Thue shows that such strings exist over alphabets
of size three and provides a fast construction of such strings using morphisms. The seminal work of
Thue inspired further works on the same problem [27, 21, 7, 24, 25, 28] and problems with a similar
pattern avoidance theme.
Krieger et. al. [20] study strings that satisfy relaxed variants of square-freeness, i.e., strings that
avoid approximate squares. Their study provides several results on strings that avoid consecutive
substrings of equal length with small additive or multiplicative Hamming distance in terms of their
length. In each of these regimes, [20] gives constructions of approximate square free strings over
alphabets with small constant size for different parameters.
Finally, Camungol and Rampersad [5] study approximate squares with respect to edit distance,
which is equivalent to the ε-synchronization string notion except that the edit distance property is
only required to hold for pairs of consecutive substrings of equal length. [5] employs a technique
based on entropy compression to prove that such strings exist over alphabets that are constant in
terms of string length but exponentially large in terms of ε−1 . We note that the previous result of
Haeupler and Shahrasbi [15] already improves this dependence to O(ε−4 ).
Again, a main question addressed in most of the above-mentioned previous work on similar
mathematical objects is how small the alphabet size can be.

1.3

Our Results

In this paper we study the question of how small the alphabet size of an ε-synchronization string
can be. We address this question both for a specified ε and
 for unspecified ε. In the first case we
−4 provided in [15] and the lower bound of
try to bridge
the
gap
between
the
upper
bound
of
O
ε

Ω ε−1 . In the second case we study the question of how small the alphabet size can be to ensure
the existence of an ε-synchronization string for some constant ε < 1. In both cases we also give
efficient constructions that improve previous results.
1.3.1

New Bounds on Minimal Alphabet Size for a given ε

Our first theorem gives improved upper bound and lower bound for the alphabet size of an
ε-synchronization string for a given ε.

3


Theorem 1.1. For any 0 < ε < 1, there exists an alphabet Σ of size O ε−2 such that an infinite
ε-synchronization string exists over Σ. In addition, ∀n ∈ N, a randomized algorithm can construct
an ε-synchronization string of length n in expected time O(n5 log n). Further, the alphabet
 size of
any ε-synchronization string that is long enough in terms of ε has to be at least Ω ε−3/2 .
Next, we provide efficient and even linear-time constructions of ε-synchronization strings over
drastically smaller alphabets than the efficient constructions in [16].
Theorem 1.2. For every n ∈ N and any constant ε ∈ (0, 1), there is a deterministic construction
of a (long-distance) ε-synchronization string of length n over an alphabet of size O(ε−2 ) that runs
in poly(n) time. Further, there is a highly-explicit linear time construction of such strings over an
alphabet of size O(ε−3 ).
Moreover, in Section 4.3, we present a method to construct infinite synchronization strings using
constructions for finite ones that only increases the alphabet size by a constant factor—as opposed
to the construction in [16] that increases the alphabet size quadratically.
Theorem 1.3. For any constant 0 < ε < 1, there exists an explicit construction of an infinite
ε-synchronization string S over an alphabet of size O(ε−2 ). Further, there exists a highly-explicit
construction of an infinite ε-synchronization string S over an alphabet of size O(ε−3 ) such that for
any i ∈ N, the first i symbols can be computed in O(i) time and S[i, i + log i] can be computed in
O(log i) time.
1.3.2

Minimal Alphabet Size for Unspecified ε: Three or Four?

One interesting question that has been commonly addressed by previous work on similar combinatorial objects is the size of the smallest alphabet over which one can find such objects. Along
the lines of [26, 28, 20, 5], we study the existence of synchronization strings over alphabets with
minimal constant size.
It is easy to observe that no such string can exist over a binary alphabet since any binary
string of length four either contains two consecutive identical symbols or two consecutive identical
substrings of length two. On the other hand, one can extract constructions over constant-sized
alphabets from the existence proofs in [15, 16], but the unspecified constants there would be quite
large. In Section 6.2, for some ε < 1, we provide a construction of arbitrarily long ε-synchronization
strings over an alphabet of size four. This narrows down the question to whether such strings exist
over alphabets of size three.
To construct such strings, we introduce the notion of weak synchronization string, which requires
substrings to satisfy a similar property as that of an ε-synchronization string, except that the lower
bound on edit distance is rounded down to the nearest integer. We show that weak synchronization
strings exist over binary alphabets and use one such string to modify a ternary square-free string
([26]) into a synchronization string over an alphabet of size four.
Finally, in Appendix A, we provide experimental evidence for the existence of synchronization
strings over ternary alphabets by finding lower-bounds for ε for which ε-synchronization strings
over alphabets of size 3, 4, 5, and 6 might exist. Similar experiments have been provided for related
combinatorial objects in the previous work [20, 5].
1.3.3

Constructing Synchronization Strings Using Uniform Morphisms

Morphisms have been widely used in previous work as a tool to construct similar combinatorial
objects. A uniform morphism of rank r over an alphabet Σ is a function φ : Σ → Σr that maps
4

any symbol of an alphabet Σ to a string of length r over the same alphabet. Using this technique,
some similar combinatorial objects in previous work have been constructed by taking a symbol
from the alphabet and then repeatedly using an appropriate morphism to replace each symbol
with a string [28, 20]. Here we investigate whether such tools can also be utilized to construct
synchronization strings. In Section 6.1, we show that no such morphism can construct arbitrarily
long ε-synchronization strings for any ε < 1.

2

Some Notations and Definitions

Usually we use Σ (probably with some subscripts) to denote the alphabet and Σ∗ to denote all
strings over alphabet Σ.
Definition 2.1 (Subsequence). The subsequence of a string S is any sequence of symbols obtained
from S by deleting some symbols. It doesn’t have to be continuous.
Definition 2.2 (Edit distance). For every n ∈ N, the edit distance ED(S, S 0 ) between two strings
S, S 0 ∈ Σn is the minimum number of insertions and deletions required to transform S into S 0 .
Definition 2.3 (Longest Common Subsequence). For any strings S, S 0 over Σ, the longest common
subsequence of S and S 0 is the longest pair of subsequence that are equal as strings. We denote by
LCS(S, S 0 ) the length of the longest common subsequence of S and S 0 .
Note that ED(S, S 0 ) = |S| + |S 0 | − 2LCS(S, S 0 ) where |S| denotes the length of S.
Definition 2.4 (ε-synchronization string). A string S is an ε-synchronization string if ∀1 ≤ i <
j < k ≤ |S| + 1, ED(S[i, j), S[j, k)) > (1 − ε)(k − i).
Definition 2.5 (square-free string). A string S is a square free string if ∀1 ≤ i < i + 2l ≤ |S| + 1,
(S[i, i + l) and S[i + l, i + 2l)) are different as words.
We also introduce the following generalization of a synchronization string, which will be useful
in our deterministic constructions of synchronization strings.
Definition 2.6 (ε-synchronization circle). A string S is an ε-synchronization circle if ∀1 ≤ i ≤ |S|,
Si , Si+1 , . . . , S| S|, S1 , S2 , . . . , Si−1 is an ε-synchronization string.

3

ε-synchronization Strings and Circles with Alphabet Size O(ε−2 )

In this section we show that by using a non-uniform sample space together with the Lovász Local
Lemma, we can have a randomized polynomial time construction of an ε-synchronization string with
alphabet size O(ε−2 ). We then use this to give a simple construction of an ε-synchronization circle
with alphabet size O(ε−2 ) as well. Although the constructions here are randomized, the parameter ε
can be anything in (0, 1) (even sub-constant), while our deterministic constructions in later sections
usually require ε to be a constant in (0, 1).
We first recall the General Lovász Local Lemma.
Lemma 3.1. (General Lovász Local Lemma) Let A1 , ..., An be a set of bad events. G(V, E) is a
dependency graph for this set of events if V = {1, . . . , n} and each event Ai is mutually independent
of all the events {Aj : (i, j) ∈
/ E}.

5

If there exists x1 , ..., xn ∈ [0, 1) such that for all i we have
Y
(1 − xj )
Pr(Ai ) ≤ xi
(i,j)∈E

Then the probability that none of these events happens is bounded by
Pr[

n
^

i=1

Āi ] ≥

n
Y
(1 − xi ) > 0
i=1

Using this lemma, we have the following theorem showing the existence of ε-synchronization
strings over an alphabet of size O(ε−2 ).
Theorem 3.2. ∀ε ∈ (0, 1) and ∀n ∈ N, there exists an ε-synchronization string S of length n over
alphabet Σ of size Θ(ε−2 ).
Proof. Suppose |Σ| = c1 ε−2 where c1 is a constant. Let t = c2 ε−2 and 0 < c2 < c1 . The sampling
algorithm is as follows:
1. Randomly pick t different symbols from Σ and let them be the first t symbols of S. If t ≥ n,
we just pick n different symbols.
2. For t + 1 ≤ i ≤ n, we pick the ith symbol S[i] uniformly randomly from Σ \ {S[i − 1], . . . , S[i −
t + 1]}
Now we prove that there’s a positive probability that S contains no bad interval S[i, k] which violates
the requirement that ED(S[i, j], S[j + 1, k]) > (1 − ε)(k − i) for any i < j < k. This requirement is
equivalent to LCS(S[i, j], S[j + 1, k]) < 2ε (k − i).
Notice that for k − i ≤ t, the symbols in S[i, k] are completely distinct. Hence we only need to
consider the case where k − i > t. First, let’s upper bound the probability that an interval is bad:
 
εl
l
Pr[interval I of length l is bad] ≤
(|Σ| − t)− 2
εl
εl
el εl
(|Σ| − t)− 2
εl p
ε |Σ| − t −εl
≤(
)
e
= C −εl

≤

The first inequality holds because if the interval is bad, then it has to contain a repeating sequence
a1 a2 . . . ap a1 a2 . . . ap where p is at least εl2 . Such sequence can be specified via choosing εl positions
in the interval and the probability that a given sequence is valid for the string in this construction
εl
is at most (|Σ| − t)− 2 . The second inequality comes from Stirling’s inequality.
The inequality above indicates that the probability that an interval of length l is bad can be
upper bounded by C −εl , where C is a constant and can be arbitrarily large by modifying c1 and c2 .
Now we use general Lovász local lemma to show that S contains no bad interval with positive
probability. First we’ll show the following lemma.
Claim. The badness of interval I = S[i, j] is mutually independent of the badness of all intervals
that do not intersect with I.

6

Proof. Suppose the intervals before I that do not
0 . We denote the indicator variables
are I10 , . . . , Im
0
is,
(
(
0 if I is not bad
0 if Ik
b=
, bk =
1 if I is bad
1 if Ik

intersect with I are I1 , . . . , Im , and those after I
of each interval being bad as b, bk and b0k0 . That
is not bad
,
is bad

b0k0

(
0 if Ik0 0 is not bad
=
1 if Ik0 0 is bad

First we prove that there exists p ∈ (0, 1) such that ∀x1 , x2 , . . . , xm ∈ {0, 1},
Pr[b = 1|bk = xk , k = 1, . . . , m] = p
According to our construction, we can see that for any fixed prefix S[1, i − 1], the probability
that I is bad is a fixed real number p0 . That is,
∀ valid S̃ ∈ Σi−1 , Pr[b = 1|S[1, i − 1] = S̃] = p0
This comes from the fact that, the sampling of the symbols in S[i, k] only depends on the previous
h = min{i − 1, t − 1} different symbols, and up to a relabeling these h symbols are the same h
symbols (e.g., we can relabel them as {1, · · · , h} and the rest of the symbols as {h + 1, · · · , |Σ|}). On
the other hand the probability that b = 1 remains unchanged under any relabeling of the symbols,
since if two sampled symbols are the same, they will stay the same; while if they are different, they
will still be different. Thus we have:
Pr[b = 1|bk = xk , i = 1, . . . , m]
Pr[b = 1, bk = xk , i = 1, . . . , m]
=
Pr[bk = xk , k = 1, . . . , m]
P
Pr[b = 1, S[1, i − 1] = S̃]
= S̃P
S̃ Pr[S[1, i − 1] = S̃]
X Pr[b = 1, S[1, i − 1] = S̃] Pr[S[1, i − 1] = S̃]
)
=
(
P
0
Pr[S[1, i − 1] = S̃]
S̃ 0 Pr[S[1, i − 1] = S̃ ]
S̃

X
Pr[S[1, i − 1] = S̃]
)
=
(Pr[b = 1|S[1, i − 1] = S̃] P
0
S̃ 0 Pr[S[1, i − 1] = S̃ ]
S̃

=p0

X

Pr[S[1, i − 1] = S̃]
0
S̃ 0 Pr[S[1, i − 1] = S̃ ]

P
S̃

0

=p

In the equations, S̃ indicates all valid string that prefix S[1, i − 1] can be such that bk = xk , k =
1, . . . , m. Hence, b is independent of {bk , k = 1, . . . , m}. Similarly, we can prove that the joint
distribution of {b0k0 , k 0 = 1, . . . , m0 } is independent of that of {b, bk , k = 1, . . . , m}. Hence b is
independent of {bk , b0k0 , k = 1, . . . , m, k 0 = 1, . . . , m0 }, which means, the badness of interval I is
mutually independent of the badness of all intervals that do not intersect with I.
Obviously, an interval of length l intersects at most l + l0 intervals of length l0 . To use Lovász
local lemma, we need to find a sequence of real numbers xi,k ∈ [0.1) for intervals S[i, k] for which
Y

Pr[S[i, k]is bad] ≤ xi,k

(1 − xi0 ,k0 )

S[i,k]∩S[i0 ,k0 ]6=∅

7

The rest of the proof is the same as that of Theorem 5.7 in [15].
We propose xi,k = D−ε(k−i) for some constant D ≥ 1. Hence we only need to find a constant D
such that for all S[i, k],
n
Y
C −ε(k−i) ≤ D−ε(k−i) [1 − D−εl ]l+(k−i)
l=t

That is, for all

l0

∈ {1, ..., n},
C

−l0

≤D

−l0

n
Y
l+l0
[1 − D−εl ] ε
l=t

which means that

D

C≥Q
n

−εl ]
l=t [1 − D

l/l0 +1
ε

Notice that the righthand side is maximized when n = ∞, l0 = 1. Hence it’s sufficient to show that
D

C≥Q
∞

l=t [1

Let L = maxD>1 Q
∞

D

−εl ]
l=t [1 − D

l+1
ε

− D−εl ]

. We only need to guarantee that C > L.

We claim that L = Θ(1). Since that t = c2 ε−2 = ω(
D
Q∞

l=t [1

l+1
ε

− D−εl ]

l+1
ε

log
ε

1
ε

),

D
l+1 −εl
]
l=t [1 − ε D

< Q∞
<
=
=

1−

D
P∞ l+1

1−

1
ε

1−

1 2tD−εt
ε (1−D−ε )2

l=t

ε

D−εl

D
−εl
l=t (l + 1)D

P∞
D
D

=

1

1−

2
D− ε
ε3 (1−D−ε )2

(1)
(2)
(3)
(4)
(5)

Inequality (1) comes from the fact that (1 − x)α > 1 − αx, (2) comes from he fact that
Q∞
P∞
P∞
xt (1+t−tx)
2txt
l
< (1−x)
2 , x < 1.
i=1 (1 − xi ) ≥ 1 −
i=1 xi and (3) is a result from
l=t (l + 1)x =
(1−x)2
−1

D ε
We can see that for D = 7, maxε { ε23 (1−D
−ε )2 } < 0.9. Therefore (5) is bounded by a constant,
which means L = Θ(1) and the proof is complete.

Using a modification of an argument in [15], we can also obtain a randomized construction.
Lemma 3.3. There exists a randomized algorithm which for any ε ∈ (0, 1) and any n ∈ N, constructs
an ε-synchronization string of length n over alphabet of size O(ε−2 ) in expected time O(n5 log n).
Proof. The algorithm is similar to that of Lemma 5.8 in [15], using algorithmic Lovász Local lemma
[23] and the extension in [14]. It starts with a string sampled according to the sampling algorithm
in the proof of Theorem 3.2, over alphabet Σ of size Cε−2 for some large enough constant C. Then
8

the algorithm checks all O(n2 ) intervals for a violation of the requirements for ε-synchronization
string. If a bad interval is found, this interval is re-sampled by randomly choosing every symbol
s.t. each one of them is different from the previous t − 1 symbols, where t = c0 ε−2 with c0 being a
constant smaller than C.
One subtle point of our algorithm is the following. Note that in order to apply the algorithmic
framework of [23] and [14], one needs the probability space to be sampled from n independent
random variables P = {P1 , · · · , Pn } so that each event in the collection A = {A1 , · · · , Am } is
determined by some subset of P. Then, when some bad event Ai happens, one only resamples the
random variables that decide Ai . Upon first look, it may appear that in our application of the Lovász
Local lemma, the sampling of the i’th symbol depends on the the previous h = min{i − 1, t − 1}
symbols, which again depend on previous symbols, and so on. Thus the sampling of the i’th symbol
depends on the sampling of all previous symbols. However, we can implement our sampling process
as follows: for the i’th symbol we first independently generate a random variable Pi which is uniform
over {1, 2, · · · , |Σ| − h}, then we use the random variables {P1 , · · · , Pn } to decide the symbols, in
the following way. Initially we fix some arbitrary order of the symbols in Σ, then for i = 1, · · · , n,
to get the i’th symbol, we first reorder the symbols Σ so that the previous h chosen symbols are
labeled as the first h symbols in Σ, and the rest of the symbols are ordered in the current order as
the last |Σ| − h symbols. We then choose the i’th symbol as the (h + Pi )’th symbol in this new
order. In this way, the random variables {P1 , · · · , Pn } are indeed independent, and the i’th symbol
is indeed chosen uniformly from the |Σ| − h symbols excluding the previous h symbols. Furthermore,
the event of any interval S[i, k] being bad only depends on the random variables (Pi , · · · , Pk ) since
no matter what the previous h symbols are, they are relabeled as {1, · · · , h} and the rest of the
symbols are labeled as {h + 1, · · · , |Σ|}. From here, the same sequence of (Pi , · · · , Pk ) will result in
the same behavior of S[i, k] in terms of which symbols are the same. We can thus apply the same
algorithm as in [15].
Note that the time to get the i’th symbol from the random variables {P1 , · · · , Pn } is O(n log 1ε )
since we need O(n) operations each on a symbol of size Cε−2 . Thus resampling each interval takes
O(n2 log 1ε ) time since we need to resample at most n symbols. For every interval, the edit distance
can be computed using the Wagner-Fischer dynamic programming within O(n2 log 1ε ) time. [14]
shows that the expected number of re-sampling is O(n). The algorithm will repeat until no bad
interval can be found. Hence the overall expected running time is O(n5 log 1ε ).
√
Note that without loss of generality we can assume that ε > 1/ n because for smaller errors we
can always use the indices directly, which have alphabet size n. So the overall expected running
time is O(n5 log n).
We can now construct an ε-synchronization circle using Theorem 3.2.
Theorem 3.4. For every ε ∈ (0, 1) and every n ∈ N, there exists an ε-synchronization circle S of
length n over alphabet Σ of size O(ε−2 ).
Proof. First, by Theorem 3.2, we can have two ε-synchronization strings: S1 with length d n2 e over
Σ1 and S2 with length b n2 c over Σ2 . Let Σ1 ∩ Σ2 = ∅ and |Σ1 | = |Σ2 | = O(ε−2 ). Let S be the
concatenation of S1 and S2 . Then S is over alphabet Σ = Σ1 ∪ Σ2 whose size is O(ε−2 ). Now we
prove that S is an ε-synchronization circle.
∀1 ≤ m ≤ n, consider string S 0 = sm , sm+1 , . . . , sn , s1 , s2 , . . . , sm−1 . Notice that for two strings
T and T 0 over alphabet Σ, LCS(T, T 0 ) ≤ 2ε (|T |+|T 0 |) is equivalent to ED(T, T 0 ) ≥ (1−ε)(|T |+|T 0 |).
For any i < j < k, we call an interval S 0 [i, k] good if LCS(S 0 [i, j], S 0 [j + 1, k]) ≤ 2ε (k − i). It suffices
to show that ∀1 ≤ i, k ≤ n, the interval S 0 [i, k] is good.
Without loss of generality let’s assume m ∈ [d n2 e, n].
9

Intervals which are substrings of S1 or S2 are good intervals, since S1 and S2 are ε-synchronization
strings.
We are left with intervals crossing the ends of S1 or S2 .
If S 0 [i, k] contains sn , s1 but doesn’t contain sd n2 e : If j < n − m + 1, then there’s no common
subsequence between s0 [i, j] and S 0 [n − m + 2, k]. Thus
ε
ε
LCS(S 0 [i, j], S 0 [j + 1, k]) ≤ LCS(S 0 [i, j], S 0 [j + 1, n − m + 1]) ≤ (n − m + 1 − i) < (k − i)
2
2
If j ≥ n − m + 1, then there’s no common subsequence between S 0 [j + 1, k] and S 0 [i, n − m + 1].
Thus
ε
ε
LCS(S 0 [i, j], S 0 [j + 1, k]) ≤ LCS(S 0 [n − m + 2, j], S 0 [j + 1, k]) ≤ (k − (n − m + 2)) < (k − i)
2
2
Thus intervals of this kind are good.

Figure 1: Example where S 0 [i, k] contains sn , s1 but doesn’t contain sd n2 e
If S 0 [i, k] contains sb n2 c , sd n2 e but doesn’t contain sn : If j ≤ n − m + b n2 c + 1, then there’s
no common subsequence between S 0 [i, j] and S 0 [n − m + d n2 e + 1, k], thus
ε
n
LCS(S 0 [i, j], S 0 [j + 1, k]) ≤ LCS(S 0 [i, j], S 0 [j + 1, n − m + b c + 1]) < (k − i)
2
2
If j ≥ n−m+b n2 c+1, then there’s no common subsequence between S 0 [j+1, k] and S 0 [i, n−m+b n2 c+1].
Thus
n
ε
LCS(S 0 [i, j], S 0 [j + 1, k]) ≤ LCS(S 0 [n − m + d e + 1, j], S 0 [j + 1, k]) < (k − i)
2
2
10

Thus intervals of this kind are good.

Figure 2: Example where S 0 [i, k] contains sb n2 c , sd n2 e
If S 0 [i, k] contains sd n2 e and sn : If n − m + 2 ≤ j ≤ n − m + b n2 c + 1, then the common
subsequence is either that of S 0 [i, n − m + 1] and S 0 [n − m + d n2 e + 1, k] or that of S 0 [n − m + 2, j]
and S 0 [j + 1, n − m + b n2 c + 1]. This is because Σ1 ∩ Σ2 = ∅. Thus
LCS(S 0 [i, j], S 0 [j + 1, k])
n
≤ max{LCS(S 0 [i, n − m + 1], S 0 [n − m + d e + 1, k]),
2
n
0
0
LCS(S [n − m + 2, j], S [j + 1, n − m + b c + 1])}
2
ε
< (k − i)
2

11

Figure 3: Example where S 0 [i, k] contains sd n2 e and sn
If j ≤ n − m + 1, then there’s no common subsequence between S 0 [i, j] and S 0 [n − m + 2, n −
m + b n2 c + 1]. Thus
LCS(S 0 [i, j], S 0 [j + 1, k])
n
≤LCS(S 0 [i, j], S 0 [j + 1, n − m + 1]) + LCS(S 0 [i, j], S 0 [n − m + d e + 1, k])
2
ε
n
ε
< (n − m + 1 − i) + (n − d e)
2
2
2
ε
ε
≤ (n − m + 1 − i) + (k − (n − m + 2))
2
2
ε
= (k − 1 − i)
2
ε
< (k − i)
2
If j ≥ S 0 [n − m + d n2 e + 1], the proof is similar to the case where j ≤ n − m + 1.
This shows that S 0 is an -synchronization string. Thus by the definition of synchronization
circle, the construction gives an -synchronization circle.

4

Deterministic Constructions of Long-Distance Synchronization
Strings

In this section, we give deterministic constructions of synchronization strings. In fact, we consider
a generalized version of synchronization strings, i.e., f (l)-distance ε-synchronization strings first
defined by Haeupler and Shahrasbi [16]. Throughout this section, ε is considered to be a constant
in (0, 1).
12

Definition 4.1 (f (l)-distance ε-synchronization string). A string S ∈ Σn is an f (l)-distance εsynchronization string if for every 1 ≤ i < j ≤ i0 < j 0 ≤ n + 1, ED (S[i, j), S[i0 , j 0 )) > (1 − ε)(l) for
i0 − j ≤ f (l) where l = j + j 0 − i − i0 .
As a special case, 0-distance synchronization strings are standard synchronization strings.
Similar to [16], we focus on f (l) = n · 1l>c log n where 1l>c log n is the indicator function for
l > c log n. This function considers the edit distance of all pairs of large intervals and adjacent small
intervals.
Definition 4.2 (c-long-distance ε-synchronization strings). We call n·1l>c log n -distance ε-synchronization
strings c-long-distance ε-synchronization strings.

4.1

Polynomial Time Constructions of Long-Distance Synchronization Strings

Here, by combining the deterministic Lovász local lemma of Chandrasekaran et al. [6] and the
non-uniform sample space used in Theorem 3.2, we give a deterministic polynomial-time construction
of c-long ε-synchronization strings over an alphabet of size O(ε−2 ).
First we recall the following property of c−long synchronization strings.
Lemma 4.3 (Corollary 4.4 of [16]). If S is a string which satisfies the c-long-distance ε-synchronization
property for any two non-adjacent intervals of total length 2c log n or less, then it satisfies the property
for all pairs of non-adjacent intervals.
We now have the following theorem.
Theorem 4.4. For any n ∈ N and any constant ε ∈ (0, 1), there is a deterministic construction
of a O(1/ε)-long-distance ε-synchronization string of length n, over an alphabet of size O(ε−2 ), in
time poly(n).
Proof. To prove this, we will use the Lovśz Local Lemma and its deterministic algorithm in [6].
Suppose the alphabet is Σ with |Σ| = q = c1 ε−2 where c1 is a constant. Let t = c2 ε−2 and
0 < c2 < c1 . We denote |Σ| − t as q. The sampling algorithm of string S (1-index based)is as follows:
• Initialize an arbitrary order for Σ.
• For ith symbol:
– Denote h = min{t−1, i−1}. Generate a random variable Pi uniformly over {1, 2, . . . , |Σ|−
h}.
– Reorder Σ such that the previous h chosen symbols are labeled as the first h symbols in
Σ, and the rest are ordered in the current order as the last |Σ| − h symbols.
– Choose the (Pi + h)’th symbol in this new order as S[i].
Define the bad event Ai1 ,l1 ,i2 ,l2 as intervals S[i1 , i1 + l1 ) and S[i2 , i2 + l2 ) violating the c = O(1/ε)long-distance synchronization string property for i1 + l1 ≤ i2 . In other words, Ai1 ,l1 ,i2 ,l2 occurs if
and only if ED(S[i1 , i1 + l1 ), S[i2 , i2 + l2 )) ≤ (1 − ε)(l1 + l2 ), which is equivalent to LCS(S[i1 , i1 +
l1 ), S[i2 , i2 + l2 )) ≥ 2ε (l1 + l2 ).
Note that according to the definition of c-long distance ε-synchronization string and Lemma 4.3,
we only need to consider Ai1 ,l1 ,i2 ,l2 where l1 + l2 < c log n and c log n ≤ l1 + l2 ≤ 2c log n. Thus we
can upper bound the probability of Ai1 ,l1 ,i2 ,l2 ,



ε(l1 +l2 )
l1
l2
Pr [Ai1 ,l1 ,i2 ,l2 ] ≤
(|Σ| − t)− 2
ε(l1 + l2 )/2 ε(l1 + l2 )/2
13


≤
=

≤

ε(l1 +l2 )/2 
ε(l1 +l2 )/2
ε(l1 +l2 )
l2 e
l1 e
(|Σ| − t)− 2
ε(l1 + l2 )/2
ε(l1 + l2 )/2
!ε(l1 +l2 )
√
2e l1 l2
p
ε(l1 + l2 ) |Σ| − t
!εl
!εl
el
e
p
p
=
= Ĉ εl ,
εl |Σ| − t
ε |Σ| − t

where l = l1 + l2 and Ĉ is a constant which depends on c1 and c2 .
However, to apply the deterministic Lovśz Local Lemma (LLL), we need to have two additional
requirements. The first requirement is that each bad event depends on up to logarithmically many
variables, and the second is that the inequalities in the Lovśz Local Lemma hold with a constant
exponential slack [16].
The first requirement may not be true under the current definition of badness. Consider for
example the random variables Pi1 , . . . , Pi1 +l1 −1 , Pi2 , Pi2 +l2 −1 for a pair of split intervals S[i1 , i1 +
l1 ), S[i2 , i2 + l2 ) where the total length l1 + l2 is at least 2c log n. The event Ai1 ,l1 ,i2 ,l2 may depend
on too many random variables (i.e., Pi1 , . . . , Pi2 +l2 −1 ).
To overcome this, we redefine the badness of the split interval S[i1 , i1 + l1 ) and S[i2 , i2 + l2 )
as follows: let Bi1 ,l1 ,i2 ,l2 be the event that there exists Pi1 +l1 , . . . , Pi2 −1 (i.e., the random variables
chosen between the two intervals) such that the two intervals generated by Pi1 . . . , Pi1 +l1 −1 and
Pi2 , . . . , Pi2 +l2 −1 (together with Pi1 +l1 , . . . , Pi2 −1 ) makes LCS(S[i1 , i1 + l1 ), S[i2 , i2 + l2 )) ≥ 2ε (l1 + l2 )
according to the sampling algorithm. Note that if Bi1 ,l1 ,i2 ,l2 does not happen, then certainly Ai1 ,l1 ,i2 ,l2
does not happen.
Notice that with this new definition of badness, Bi1 ,l1 ,i2 ,l2 is independent of {Pi1 +l1 , . . . , Pi2 −1 }
and only depends on {Pi1 . . . , Pi1 +l1 −1 , Pi2 , . . . , Pi2 +l2 }. In particular, this implies that Bi1 ,l1 ,i2 ,l2
is independent of the badness of all other intervals which have no intersection with (S[i1 , i1 + l1 ),
S[i2 , i2 + l2 )).
We now bound Pr[Bi1 ,l1 ,i2 ,l2 ]. When considering the two intervals S[i1 , i1 + l1 ), S[i2 , i2 + l2 ) and
their edit distance under our sampling algorithm, without loss of generality we can assume that the
order of the alphabet at the point of sampling S[i1 ] is (1, 2, . . . , q) just by renaming the symbols.
Now, if we fix the order of the alphabet at the point of sampling S[i2 ] in our sampling algorithm,
then S[i2 , i2 + l2 ) only depends on {Pi2 , . . . , Pi2 +l2 } and thus LCS(S[i1 , i1 + l1 ), S[i2 , i2 + l2 )) only
depends on {Pi1 . . . , Pi1 +l1 −1 , Pi2 , . . . , Pi2 +l2 }.
Conditioned on any fixed order of the alphabet at the point of sampling S[i2 ], we have that
LCS(S[i1 , i1 + l1 ), S[i2 , i2 + l2 )) ≥ 2ε (l1 + l2 ) happens with probability at most Ĉ εl by the same
computation as we upper bound Pr[Ai1 ,l1 ,i2 ,l2 ]. Note that there are at most q! different orders of the
alphabet. Thus by a union bound we have
Pr[Bi1 ,l1 ,i2 ,l2 ] ≤ Ĉ εl × q! = C εl ,
for some constant C.
In order to meet the second requirement of the deterministic algorithm of LLL, we also need to
find real numbers xi1 ,i1 +l1 ,i2 ,i2 +l2 ∈ [0, 1] such that for any Bi1 ,l1 ,i2 ,l2 ,
1.01


Y

Pr[Bi1 ,l1 ,i2 ,l2 ] ≤ xi1 ,l1 ,i2 ,l2

(1 − xi01 ,l10 ,i02 ,l20 )

[S[i1 ,i1 +l1 )∪S[i2 ,i2 +l2 )]∩[S[i01 ,i01 +l10 )∪S[i02 ,i02 +l20 )]6=∅

14

.

We propose xi1 ,l1 ,i2 ,l2 = D−ε(l1 +l2 ) for some D > 1 to be determined later. D has to be chosen such
that for any i1 , l1 , i2 , l2 and l = l1 + l2 :

e
p
ε |Σ|

1.01



!εl

D−εl

≤



Y

1−D

−ε(l10 +l20 )




(6)

[S[i1 ,i1 +l1 )∪S[i2 ,i2 +l2 )]∩[S[i01 ,i01 +l10 )∪S[i02 ,i02 +l20 )]6=∅

Notice that


Y

D−εl

0

0

1 − D−ε(l1 +l2 )



(7)

[S[i1 ,i1 +l1 )∪S[i2 ,i2 +l2 )]∩[S[i01 ,i01 +l10 )∪S[i02 ,i02 +l20 )]6=∅

≥ D

−εl

l0 
Y

2cY
log n

1 − D−εl

0

[(l1 +l10 )+(l1 +l20 )+(l2 +l10 )+(l2 +l20 )]n

l0 =c log n l10 =1

×

= D

cY
log n 

1 − D−εl

l00 =t
2cY
log n
−εl

l+l00

00

l0 
Y

(8)

1 − D−εl

0

4(l+l0 )n

cY
log n 

×

= D

−εl



1−D

−εl0

4l0 (l+l0 )n

×

"c log n
Y 

(9)

1−D

−εl00



#l
×

cY
log n 

1 − D−εl

00

l00

(10)

l00 =t



2cX
log n

≥ D−εl 1 −

l+l00

l00 =t

l0 =c log n



00

l00 =t

l0 =c log n l10 =1
2cY
log n

1 − D−εl

4l0 (l + l0 )n D


−εl0



l0 =c log n

"
× 1−

cX
log n

#l
D

−εl00

×

1−

l00 =t


≥ D−εl 1 −

cX
log n

!
00

l D

−εl00

(11)

l00 =t
2cX
log n


0
(4 · 2c log n(2c log n + 2c log n)n) D−εl 

(12)

l0 =c log n

"
× 1−

∞
X

#l
D

−εl00

×

1−

l00 =t



∞
X

!
l00 D

−εl00

(13)

l00 =t
2cX
log n



"

−1

−c2 ε
× 1− D
= D 1 −
32c n log n D
1 − D−ε
l0 =c log n
!
D−c2 /ε (D−ε + c2 /ε2 − c2 D−ε /ε2 )
× 1−
(1 − D−ε )2
"
#l


−c2 ε−1
D
≥ D−εl 1 − 32c3 n log3 nD−εc log n 1 −
1 − D−ε
!
D−c2 /ε (D−ε + c2 /ε2 − c2 D−ε /ε2 )
× 1−
(1 − D−ε )2
−εl

2

2



#l

−εl0

15

(14)

(15)

Equation 8 holds because there are two kinds of pairs of intervals. The first kind contains all
pairs of intervals whose total length is between c log n and 2c log n intersecting with S[i1 , i1 + l1 ) or
S[i2 , i2 + l2 ). The number of such pairs is at most (l1 + l10 ) + (l1 + l20 ) + (l2 + l10 ) + (l2 + l20 ). The
second kind contains all adjacent intervals of total length less than c log n. Notice that according
to our sampling algorithm, every t consecutive symbols are distinct, thus any adjacent intervals
whose total length is less than t cannot be bad. Hence the second term contains intervals such that
t ≤ l00 = l100 + l200 ≤ c log n.
The rest of the proof is the same as that of Theorem 4.5 in [16].
Equation 11 comes from the fact that for 0 < x, y < 1:
(1 − x)(1 − y) > 1 − x − y
For D = 2 and c = 2/ε,
2−c2 /ε
=0
ε→0 1 − 2−ε
lim

Thus, for sufficiently small ε,

2−c2 /ε
1−2−ε

< 21 . Moreover,
0

32c2 n log2 nD−εl =
−c2 /ε

28 log3 n
= o(1)
ε3 n

−ε

2

−ε

2

(D +c2 /ε −c2 D /ε )
Finally, for sufficiently small ε, 1 − D
> 2−ε . Therefore, for sufficiently
(1−D−ε )2
small ε and sufficiently large n, 15 is satisfied under the condition:


Y
0
0
D−εl
1 − D−ε(l1 +l2 )
[S[i1 ,i1 +l1 )∪S[i2 ,i2 +l2 )]∩[S[i01 ,i01 +l10 )∪S[i02 ,i02 +l20 )]6=∅

1
1
4−εl
≥ 2−εl (1 − )(2−ε )l (1 − ) ≥
2
2
4
So for LLL to work, the following should be guaranteed:
e
p
ε |Σ| − t

!

εl
1.01

2

4−εl
42.02(1+ε)e
≤
⇐
≤ |Σ| − t
4
ε2

Hence the second requirement holds for |Σ| − t =

44.04 e2
ε2

= O(ε−2 ).

Corollary 4.4.1. For any n ∈ N and any constant ε ∈ (0, 1), there is a deterministic construction
of an ε-synchronization string of length n, over an alphabet of size O(ε−2 ), in time poly(n).
By a similar concatenation construction used in the proof of Theorem 3.4, we also have a
deterministic construction for synchronization circles.
Corollary 4.4.2. For any n ∈ N and any constant ε ∈ (0, 1), there is a deterministic construction
of an ε-synchronization circle of length n, over an alphabet of size O(ε−2 ), in time poly(n).

4.2

Deterministic linear time constructions of c-long distance ε-synchronization
string

Here we give a much more efficient construction of a c-long distance ε-synchronization string, using
synchronization circles and standard error correcting codes. We show that the following algorithm
gives a construction of c-long distance synchronization strings.
16

Algorithm 1 Explicit Linear Time Construction of c-long distance ε-synchronization string
Input:
• An ECC Cˆ ⊂ Σm
, with distance δm and block length m = c log n.
Ĉ
• An ε0 -synchronization circle SC = (sc1 , . . . , scm ) of length m over alphabet ΣSC .
Operations:
• Construct a code C ⊂ Σm such that
ˆ
C = {((ĉ1 , sc1 ), . . . , (ĉm , scm ))|(ĉ1 , . . . , ĉm ) ∈ C}
where Σ = ΣĈ × ΣSC .
• Let S be concatenation of all codewords C1 , . . . , CN from C.
Output: S.
To prove the correctness, we first recall the following theorem from [15].
Theorem 4.5 (Theorem 4.2 of [15]). Given an ε0 -synchronization string S with length n, and
0
an efficient ECC C with block length n, that corrects up to nδ 1+ε
1−ε0 half-errors, one can obtain an
0
insertion/deletion code C that can be decoded from up to nδ deletions, where C 0 = {(c01 , . . . , c0n )|∀i ∈
[n], c0i = (ci , S[i]), (c1 , . . . , cn ) ∈ C}.
We have the following property of longest common subsequence.
Lemma 4.6. Suppose T1 is the concatenation of `1 strings, T1 = S1 ◦ · · · ◦ S`1 and T2 is the
concatenation of `2 strings, T2 = S10 ◦ · · · ◦ S`0 2 . If there exists an integer t such that for all i, j, we
have LCS(Si , Sj0 ) ≤ t, then we have LCS(T1 , T2 ) ≤ (`1 + `2 )t.
Proof. We rename the strings in T2 by S`1 +1 , · · · , S`1 +`2 . Suppose the longest common subsequence
between T1 and T2 is T̃ , which can be viewed as a matching between T1 and T2 .
we can divide T̃ sequentially into disjoint intervals, where each interval corresponds to a common
subsequence between a different pair of strings (Si , Sj ), where Si is from T1 and Sj is from T2 . In
addition, if we look at the intervals from left to right, then for any two consecutive intervals and
their corresponding pairs (Si , Sj ) and (Si0 , Sj 0 ), we must have i0 ≥ i and j 0 ≥ j since the matchings
which correspond to two intervals cannot cross each other. Furthermore either i0 > i or j 0 > j as
the pair (Si , Sj ) is different from (Si0 , Sj 0 ).
Thus, starting from the first interval, we can label each interval with either i or j such that every
interval receives a different label, as follows. We label the first interval using either i or j. Then,
assuming we have already labeled some intervals and now look at the next interval. Without loss of
generality assume that the previous interval is labeled using i, now if the current i0 > i then we can
label the current interval using i0 ; otherwise we must have j 0 > j so we can label the current interval
using j 0 . Thus the total number of the labels is at most l1 + l2 , which means the total number of
the intervals is also at most l1 + l2 . Note that each interval has length at most t, therefore we can
upper bound LCS(T1 , T2 ) by (l1 + l2 )t.
1−ε0
Lemma 4.7. The output S in Algorithm 1 is an ε1 -synchronization circle, where ε1 ≤ 10(1 − 1+ε
δ).
0

17

Proof. Suppose Cˆ can correct up to δm half-errors. Then according to lemma 4.5, C can correct up
0
to 1−ε
1+ε0 δm deletions.
0
Let α = 1 − 1−ε
1+ε0 δ. Notice that C has the following properties:
1. LCS(C) = maxc1 ,c2 ∈C LCS(c1 , c2 ) ≤ αm
2. Each codeword in C is an ε-synchronization circle over Σ.
Consider any shift of the start point of S, we only need to prove that ∀1 ≤ i < j < k ≤
n, LCS(S[i, j], S[j + 1, k]) < ε21 (k − i).
Suppose S1 = S[i, j] and S2 = S[j + 1, k]. Let ε1 = 10α.
Case 1: k − i > m. Let |S1 | = s1 and |S2 | = s2 , thus s1 + s2 > m. If we look at each Sh for
h = 1, 2, then Sh can be divided into some consecutive codewords, plus at most two incomplete
codewords at both ends. In this sense each Sh is the concatenation of `h strings with `h < smh + 2.
An example of the worst case appears in Figure 4.

Figure 4: Example of the worst case, where j splits a codeword, and there are two incomplete
codewords at both ends.
Now consider the longest common subsequence between any pair of these strings where one is
from S1 and the other is from S2 , we claim that the length of any such longest common subsequence
is at most αm. Indeed, if the pair of strings are from two different codewords, then by the property
of the code C we know the length is at most αm. On the other hand, if the pair of strings are from
a single codeword (this happens when j splits a codeword, or when S[i] and S[k] are in the same
codeword), then they must be two disjoint intervals within a codeword. In this case, by the property
that any codeword is also a synchronization circle, the length of the longest common subsequence of
this pair is at most ε20 m.
2ε0
ε0
1−ε0
0
Note that α = 1 − 1−ε
1+ε0 δ ≥ 1 − 1+ε0 = 1+ε0 ≥ ε0 (since δ, ε0 ∈ (0, 1)). Thus 2 m < αm.
Therefore, by Lemma 4.6, we have
LCS(S1 , S2 )
s1
s2
<( + 2 +
+ 2)αm
m
m
=α(s1 + s2 + 4m)

(16)

<5α(s1 + s2 )
ε1
(k − i)
2
Case 2: If k − i ≤ m, then according to the property of synchronization circle SC, we know
that the longest common subsequence of S1 and S2 is less than ε20 (k − i) ≤ α(k − i) ≤ ε21 (k − i).
As a result, the longest common subsequence of S[i, j] and S[j + 1, k] is less than ε21 (k − i),
which means that S is an ε1 -synchronization circle.
=5α(k − i) =

Similarly, we also have the following lemma.

18

Lemma 4.8. The output S of algorithm 1 is a c-long distance ε-synchronization string of length
0
n = N m where N is the number of codewords in C, ε = 12(1 − 1−ε
1+ε0 δ).
Proof. By Lemma 4.7, S is an ε1 -synchronization string, thus the length of longest common
subsequence for adjacent intervals S1 , S2 with total length l < c log n is less than ε21 l. We only need
to consider pair of intervals S1 , S2 whose total length l ∈ [c log n, 2c log n].
Notice that the total length of S1 and S2 is at most 2c log n, which means that S1 and S2 each
intersects with at most 3 codewords from C. Using Lemma 4.6, we have that LCS(S1 , S2 ) ≤ 6αl.
0
Thus picking ε = max{12α, ε1 } = 12α = 12(1 − 1−ε
1+ε0 δ), S from algorithm 1 is a c-long distance
ε-synchronization circle.
We need the following code constructed by Guruswarmi and Indyk [12].
Lemma 4.9 (Theorem 3 of [12]). For every 0 < r < 1, and all sufficiently small ε > 0, there exists
−4 −1
a family of codes of rate r and relative distance (1 − r − ε) over an alphabet of size 2O(ε r log(1/ε))
such that codes from the family can be encoded in linear time and can also be uniquely decoded in
linear time from 2(1 − r − ε) fraction of half errors.
Lemma 4.10 (ECC by Brute Force Search). For any n ∈ N, any ε ∈ [0, 1], one can construct
n
εn
a ECC in time O(2εn ( 2e
ε ) n log(1/ε)) and space O(2 n log(1/ε)), with block length n, number of
εn
codewords 2 , distance d = (1 − ε)n, alphabet size 2e/ε.
We can now use Algorithm 1 to give a linear time construction of c − long − distance εsynchronization strings.
Theorem 4.11. For every n ∈ N and any constant 0 < ε < 1, there is a deterministic construction
of a c = O(ε−2 ) − long − distance ε-synchronization string S ∈ Σn where |Σ| = O(ε−3 ), in time
n
O(n). Moreover, S[i, i + log n] can be computed in O( log
) time.
ε2
Proof. Suppose we have an error correcting code Cˆ with distance rate 1 − ε0 =

ε
1+ 36
ε
1− 36

ε
(1 − 12
), message

rate rc = O(ε02 ), over an alphabet of size |Σc | = O(ε0−1 ), with block length m = O(ε0−2 log n).
ε
Let c = O(ε0−2 ) = O(ε−2 ). We apply Algorithm 1, using Ĉ and an 36
-synchronization circle
−2
SC of length m over an alphabet of size O(ε ). Here SC is constructed by Corollary 4.4.2 in
1− ε
time poly(m) = poly(log n). By Lemma 4.8, we have a c-long-distance 12(1 − 1+ 36ε (1 − ε0 )) = ε36
synchronization string of length m · |Σc |rc m ≥ n.
It remains to show that we can have such a Cˆ with linear time encoding. We use the code in
Lemma 4.9 as the outer code and the one in Lemma 4.10 as inner code. Let Cout be an instantiation
of the code in Lemma 4.9 with rate ro = εo = 13 ε0 , relative distance do = (1 − 2εo ) and alphabet size
−5

4

εo log n
2O(εo log(1/εo )) , and block length no = log(1/ε
, which is encodable and decodable in linear time.
o)
Further, according to Lemma 4.10 one can find a code Cin with rate ri = O(εi ) where εi = 13 ε0 ,
−6
relative distance 1 − εi , over an alphabet of size 2e
εi , and block length ni = O(εi log(1/εi )). Note
that since the block length and alphabet size are both constant because ε is a constant. So the
encoding can be done in constant time.
Concatenating Cout and Cin gives the desire code Cˆ with rate O(ε02 ), distance 1 − O(ε0 ) and
alphabet of size O(ε0−1 ) and block length O(ε0−2 log n). Moreover, the encoding of Cˆ can be done in
linear time, because the encoding of Cout is in linear time and the encoding of Cin is in constant
time.
n
Note that since every codeword of Cˆ can be computed in time O( log
), S[i, i + log n] can be
ε2
log n
computed in O( ε2 ) time.

19

Corollary 4.11.1. For every n ∈ N and any constant 0 < ε < 1, there is a deterministic
construction of an ε-synchronization string S ∈ Σn where |Σ| = O(ε−3 ), in time O(n). Moreover,
n
S[i, i + log n] can be computed in O( log
) time.
ε2

4.3

Explicit Constructions of Infinite Synchronization Strings

In this section we focus on the construction of infinite synchronization strings.
The definition of infinite synchronization strings is similar to that of standard synchronization
strings except that the length of the string is infinite.
Definition 4.12 (Infinite ε-synchronization string). A string S is an infinite ε-synchronization
string if it has infinite length and ∀1 ≤ i < j < k, ED(S[i, j), S[j, k)) > (1 − ε)(k − i).
To measure the efficiency of the construction of an infinite string, we consider the time complexity
for computing the first n elements of that string. An infinite synchronization string is said to have
an explicit construction if there is an algorithm that computes any position S[i] in time poly(i).
Moreover, it is said to have a highly-explicit construction if there is an algorithm that computes any
position S[i] in time O(log i).
We have the following algorithm.
Algorithm 2 Construction of infinite ε-synchronization string
Input:
• A constant ε ∈ (0, 1).
Operations:
• Let q ∈ N be the size of an alphabet large enough to construct an 2ε -synchronization string.
Let Σ1 and Σ2 be two alphabets of size q such that Σ1 ∩ Σ2 = ∅.
• Let k = 4ε . For i = 1, 2, . . ., construct an 2ε -synchronization string Ski of length k i , where
Ski is over Σ1 if i is odd and over Σ2 otherwise.
• Let S be the sequential concatenation of Sk , Sk2 , Sk3 , . . . , Skt , . . .
Output: S.
Lemma 4.13. If there is a construction of 2ε -synchronization strings with alphabet size q, then
Algorithm 2 constructs an infinite ε-synchronization string owith alphabet size 2q.
Proof. Algorithm 2 can be shown as in the figure below.

Figure 5: Sk and Sk3 are over alphabet Σ1 and Sk2 is over Σ2 .
Now we show that S is an infinite ε-synchronization string.
Claim. Let x < y < z be positive integers and let t be such that k t ≤ |S[x, z)| < k t+1 . Then
ED(S[x, y), S[y, z)) ≥ (1 − 2ε )(z − x)(1 − k2 ).
20

P
i+1
Proof. Let li be the index of S where Ski+1 starts. Then li = ij=1 k j = k k−1−k . Notice that
lt−1 < 2k t−1 and |S[x, z)| ≥ k t , one can throw away all elements of S[x, z) whose indices are less
t−1
than lt−1 without losing more than 2kkt = k2 fraction of the elements of S[x, z). We use S[x0 , z) to
denote the substring after throwing away the symbols before lt−1 . Thus x0 ≥ lt−1 .
Since x0 ≥ lt−1 , S[x0 , z) either entirely falls into a synchronization string Skl or crosses two
synchronization strings Skl and Skl+1 over two entirely different alphabets Σ1 and Σ2 . Thus the
edit distance of S[x0 , y) and S[y, z) is at least (1 − 2ε )(z − x).
Since k = 4ε , we have that
 


ε 2
2
ε
= 1−
(z − x) ≥ (1 − ε)(z − x).
(z − x) 1 −
ED(S[x, y), S[y, z)) ≥ 1 −
2
k
2
This shows that S is an ε-synchronization string.
If we instantiate Algorithm 2 using Corollary 4.4.1, then we have the following theorem.
Theorem 4.14. For any constant 0 < ε < 1, there exists an explicit construction of an infinite
ε-synchronization string S over an alphabet of size O(ε−2 ).
Proof. We combine Algorithm 2 and Corollary 4.4.1. In the algorithm, we can construct every
substring Ski in polynomial time with alphabet size q = O(ε−2 ), by Corollary 4.4.1. So the first n
symbols of S can be computed in polynomial time.
By Lemma 4.13, S is an infinite ε-synchronization string over an alphabet of size 2q = O(ε−2 ).
If we instantiate Algorithm 2 using Corollary 4.11.1, then we have the following theorem.
Theorem 4.15. For any constant 0 < ε < 1, there exists a highly-explicit construction of an infinite
ε-synchronization string S over an alphabet of size O(ε−3 ). Moreover, for any i ∈ N, the first i
symbols can be computed in O(i) time and S[i, i + log i] can be computed in O(log i) time.
Proof. Combine Algorithm 2 and Corollary 4.11.1. In the algorithm, we can construct every
substring Ski in linear time with alphabet size q = O(ε−3 ), by Corollary 4.11.1. So the first i
symbols can be computed in O(i) time. Also any substring S[i, i + log i] can be computed in time
O(log i).
By Lemma 4.13, S is an infinite ε-synchronization string over an alphabet of size 2q = O(ε−3 ).

5


Ω ε−3/2 Lower-Bound on Alphabet Size

The twin word problem was introduced by Axenovich, Person, and Puzynina [1] and further studied
by Bukh and Zhou [4]. Any set of two identical disjoint subsequences in a given string is called a
twin word. [1, 4] provided a variety of results on the relations between the length of a string, the
size of the alphabet over which it is defined, and the size of the longest twin word it contains. We
will make use of the following result from [4] that is built upon Lemma 5.9 from [2] to provide a
new lower-bound on the alphabet size of synchronization strings.
Theorem 5.1 (Theorem 3 from [4]). There exists a constant c so that every word of length n over
a q-letter alphabet contains two disjoint equal subsequences of length cnq −2/3 .
Further, Theorem 6.4 of [15] states that any ε-synchronization string of length n has to satisfy
ε-self-matching property which essentially means that it cannot contain two (not necessarily disjoint)
subsequences of length εn or more. These two requirements lead to the following inequality for an
ε-synchronization string of length n over an alphabet of size q.
cnq −2/3 ≤ εn ⇒ c0 ε−3/2 ≤ q
21

6

Synchronization Strings over Small Alphabets

In this section, we focus on synchronization strings over small constant-sized alphabets. We study the
question of what is the smallest possible alphabet size over which arbitrarily long ε-synchronization
strings can exist for some ε < 1, and how such synchronization strings can be constructed.
Throughout this section, we will make use of square-free strings introduced by Thue [26], which
is a weaker notion than synchronization strings that requires all consecutive equal-length substrings
to be non-identical. Note that no synchronization strings or square-free strings of length four
or more exist over a binary alphabet since a binary string of length four either contains two
consecutive similar symbols or two identical consecutive substrings of length two. However, for
ternary alphabets, arbitrarily long square-free strings exist and can be constructed efficiently using
uniform morphism [28]. In Section 6.1, we will briefly review this construction and show that no
uniform morphism can be used to construct arbitrary long synchronization strings. In Section 6.2,
we make use of ternary square-free strings to show that arbitrarily long ε-synchronization strings
exist over alphabets of size four for some ε < 1. Finally, in Section A, we provide experimental
lower-bounds on ε’ for which ε-synchronization strings exist over alphabets of size 3, 4, 5, and 6.

6.1

Morphisms cannot Generate Synchronization Strings

Previous works show that one can construct infinitely long square-free or approximate-square-free
strings using uniform morphisms. A uniform morphism of rank r over an alphabet Σ is a function
φ : Σ → Σr that maps any symbol out of an alphabet Σ to a string of length r over the same
alphabet. Applying the function φ over some string S ∈ Σ∗ is defined as replacing each symbol of S
with φ(S).
[20, 27, 21, 7, 28] show that there are uniform morphisms that generate the combinatorial
objects they study respectively. More specifically, one can start from any letter of the alphabet and
repeatedly apply the morphism on it to construct those objects. For instance, using the uniform
morphisms of rank 11 suggested in [28], all such strings will be square-free. In this section, we
investigate the possibility of finding similar constructions for synchronization strings. We will show
that no such morphism can possibly generate an infinite ε-synchronization strings for any fixed
0 < ε < 1.
The key to this claim is that a matching between two substrings is preserved under an application
of the uniform morphism φ. Hence, we can always increase the size of a matching between two
substrings by applying the morphism sufficiently many times, and then adding new matches to the
matching from previous steps.
Theorem 6.1. Let φ be a uniform morphism of rank r over alphabet Σ. Then φ does not generate
an infinite ε-synchronization string, for any 0 < ε < 1.
Proof. To prove this, we show that for any 0 < ε < 1, applying morphism φ sufficiently many
times over any symbol of alphabet Σ produces a strings that has two neighboring intervals which
contradict ε-synchronization property. First, we claim that, without loss of generality, it suffices to
prove this for morphisms φ for which φ(σ) contains all elements of Σ for any σ ∈ Σ. To see this,
consider the graph G with |Σ| vertices where each vertex corresponds to a letter of the alphabet
and there is a (σ1 , σ2 ) edge if φ(σ1 ) contains σ2 . It is straightforward to verify that after applying
morphism φ over a letter sufficiently many times, the resulting string can be split into a number of
substrings so that the symbols in any of them belong to a subset of Σ that corresponds to some
strongly connected component in G. As ε-synchronization string property is a hereditary property
over substrings, this gives that one can, without loss of generality, prove the above-mentioned claim
22

for morphisms φ for which the corresponding graph G is strongly connected. Further, let d be the
greatest common divisor of the size of all cycles in G. One can verify that, for some sufficiently
large k, φkd will be a morphism that, depending on the letter σ to perform recursive applications
of the morphism on, will always generate strings over some alphabet Σσ and φkd (σ 0 ) contains all
symbols of Σσ for all σ 0 ∈ Σσ . As proving the claim for φkd implies it for φ as well, the assumption
mentioned above does not harm the generality.
We now proceed to prove that for any morphism φ of rank r as described above, any positive
integer n ∈ N, and any positive constant 0 < δ < 1, there exists m ∈ N so that
n



1
m
m
− δ · rm
LCS(φ (a), φ (b)) ≥ 1 − 1 −
|Σ|2 r
for any a, b ∈ Σ where φm represents m consecutive applications of morphism φ and LCS(., .)
denotes the longest common substring.
Having such claim proved, one can take δ = (1 − ε)/2 and n large enough so that m applications
of φ over any pair of symbols entail strings with a longest common substring that is of a fraction
larger than 1 − (1 − ε) = ε in terms of the length of those strings. Then, for any string S ∈ Σ∗ ,
one can take two arbitrary consecutive symbols of φ(S) like S[i] and S[i + 1]. Applying morphism
φ, m more times on φ(S) makes the corresponding intervals of φm+1 (S) have an edit distance
that is smaller than 1 − ε fraction of their combined lengths. This shows that φm+1 (S) is not an
ε-synchronization string and finishes the proof.
Finally, we prove the claim by induction on n. For the base case of n = 1, given the assumption
of all members of Σ appearing in φ(σ) for all σ ∈ Σ, φ(a) and φ(b) have a non-empty common
subsequence. This gives that







1
1
LCS(φ(a), φ(b)) ≥ 1 = 1 − 1 −
·r > 1− 1−
− δ · r.
r
|Σ|2 r
Therefore, choosing m = 1 finishes the induction base.
We now prove the induction step. Note that by induction hypothesis, for some given n, one can
find m1 such that


n

1
δ
m1
m1
LCS(φ (a), φ (b)) ≥ 1 − 1 −
−
· rm1 .
|Σ|2 r
2


Now, let m2 = logr 2δ . Consider φm2 (a) and φm2 (b). Note that among all possible pairs of symbols
m
from Σ2 , one appears at least r|Σ|22 times in respective positions of φm2 (a) and φm2 (b). Let (a0 , b0 )
be such pair. As φ(a0 ) and φ(b0 ) contain all symbols of Σ, one can take one specific occurrence of
a fixed arbitrary symbol σ ∈ Σ in all appearances of the pair φ(a0 ) and φ(b0 ) to find a common
m
m +1
subsequence of size r|Σ|22 = r|Σ|22 r or more between φm2 +1 (a) and φm2 +1 (b) (See Figure 6).
𝜙 𝑚2 (𝑎)

𝜙 𝑚2 (⋅)

𝜙 𝑚2 +1 (𝑎)

𝜙(⋅)

𝑎

𝑎

𝑏

𝑐

𝑏

𝑎

𝜙(𝑎)

𝑏

𝑐

𝑎

𝑏

𝑎

𝑏

𝜙(𝑐)

𝜙(𝑏)
𝜎

𝜙(𝑐)

𝜙(𝑎)

𝜙(𝑏)

𝜎
𝜙

𝑚2

(𝑏)

𝜙(𝑏)
𝜎

𝜙(𝑎)

𝜙(𝑎)

𝜙(𝑏)

𝜎
𝜙

𝑚2 +1

(𝑏)

Figure 6: Induction step in Theorem 6.1; Most common pair (a0 , b0 ) = (b, a).
23

Note that one can apply the morphism φ further times over φm2 +1 (a) and φm2 +1 (b) and such
common subsequence will still be preserved; However, one might be able to increase the size of it
by adding new elements to the common subsequence from equal length pairs of intervals between
current common subsequence elements (denoted by blue dashed line in Figure 6). The total length
of such intervals is
1
1
r
δ
1−
− m2 +1 = 1 −
−
2
2
|Σ| r r
|Σ| r 2
or more. In fact, using the induction hypothesis, by applying the morphism m1 more times, one can
get the following for m = m1 + m2 + 1.
"


n

1
δ
1
m
m
+ 1− 1−
−
LCS(φ (a), φ (b)) ≥
|Σ|2 r
|Σ|2 r
2
#


1
δ
· 1−
rm
−
|Σ|2 r 2
"
#

n+1
1
≥ 1− 1−
− δ rm
|Σ|2 r
This completes the induction step and finishes the proof.

6.2

Synchronization Strings over Alphabets of Size Four

In this section, we show that synchronization strings of arbitrary length exist over alphabets of size
four. In order to do so, we first introduce the notion of weak ε-synchronization strings. This weaker
notion is very similar to the synchronization string property except the edit distance requirement is
rounded down.
Definition 6.2 (weak ε-synchronization strings). String S of length n is a weak ε-synchronization
string if for every 1 ≤ i < j < k ≤ n,
ED(S[i, j), S[j, k)) ≥ b(1 − ε)(k − i)c.
We start by showing that binary weak ε-synchronization strings exist for some ε < 1.
6.2.1

Binary Weak ε-Synchronization Strings

Here we prove that an infinite binary weak ε-synchronization string exists. The main idea is to take
a synchronization string over some large alphabet and convert it to a binary weak synchronization
string by mapping each symbol of that large alphabet to a binary string and separating each binary
encoded block with a block of the form 0k 1k .
Theorem 6.3. There exists a constant ε < 1 and an infinite binary weak ε-synchronization string.
Proof. Take some arbitrary ε0 ∈ (0, 1). According to [15], there exists an infinite ε0 -synchronization
string S over a sufficiently large alphabet Σ. Let k = dlog |Σ|e. Translate each symbol of S into k
binary bits, and separate the translated k-blocks with 0k 1k . We claim that this new string T is a
weak ε-synchronization binary string for some ε < 1.
First, call a translated k-length symbol followed by 0k 1k a full block. Call any other (possibly
empty) substring a half block. Then any substring of T is a half-block followed by multiple full
blocks and ends with a half block.
24

Let A and B be two consecutive substrings in T . Without loss of generality, assume |A| ≤ |B|
(because edit distance is symmetric). Let M be a longest common subsequence between A and B.
Partition blocks of B into the following 4 types of blocks:
1. Full blocks that match completely to another full block in A.
2. Full blocks that match completely but not to just 1 full block in A.
3. Full blocks where not all bits within are matched.
4. Half blocks.
The key claim is that the 3k elements in B which are matched to a type-2 block in A are not
contiguous and, therefore, there is at least one unmatched symbol in B surrounded by them. To see
this, assume by contradiction that all letters of some type-2 block in A are matched contiguously.
The following simple analysis over 3 cases contradicts this assumption:
• Match starts at middle of some translated k-length symbol, say position p ∈ [2, k]. Then the
first 1 of 1k in A will be matched to the (k − p + 2)-th 0 of 0k in B, contradiction.
• Match starts at 0-portion of 0k 1k block, say at the p-th 0. Then the p-th 1 of 1k in A will be
matched to the first 0 of 0k in B, contradiction.
• Match starts at 1-portion of 0k 1k block, say at the p-th 1. Then the p-th 0 of 0k in A will be
matched to the first 1 of 1k in B, contradiction.
Let the number of type-i blocks in B be ti . For every type-2 block, there is an unmatched letter
in A between its first and last matches. Hence, |A| ≥ |M | + t2 . For every type-3 block, there is an
unmatched letter in B within. Hence, |B| ≥ |M | + t3 . Therefore, |A| + |B| ≥ 2|M | + t2 + t3 .
Since |A| ≤ |B|, the total number of full blocks in both A and B is at most 2(t1 + t2 + t3 ) + 1.
(the additional +1 comes from the possibility that the two half-blocks in B allows for one extra full
block in A) Note t1 is a matching between the full blocks in A and the full blocks in B. So due to
the ε0 -synchronization property of S, we obtain the following.
t1 ≤

ε0
ε0
ε0
(2(t1 + t2 + t3 ) + 1) =⇒ t1 ≤
(t
+
t
)
+
2
3
2
1 − ε0
2(1 − ε0 )

|A|+|B|
Furthermore, t1 + t2 + t3 + 2 > |B|
3k ≥
6k . This, along with the above inequality, implies the
following.
|A| + |B|
1
4 − 3ε0
(t
+
t
)
+
>
.
2
3
0
0
1−ε
2(1 − ε )
6k
The edit distance between A and B is

ED(A, B) = |A| + |B| − 2|M | ≥ t2 + t3
1 − ε0
4 − 3ε0
1 − ε0
>
(|A| + |B|) −
>
(|A| + |B|) − 2.
6k
2
6k
Set ε = 1 −

1−ε0
18k .

If |A| + |B| ≥

1
1−ε ,

then



1 − ε0
1 − ε0
(|A| + |B|) − 2 ≥
− 2(1 − ε) (|A| + |B|)
6k
6k
= (1 − ε)(|A| + |B|) ≥ b(1 − ε)(|A| + |B|)c.
As weak ε-synchronization property trivially holds for |A| + |B| <
weak ε-synchronization string.
25

1
1−ε ,

this will prove that T is a

6.2.2

ε-Synchronization Strings over Alphabets of Size Four

A corollary of Theorem 6.3 is the existence of infinite synchronization strings over alphabets of size
four. Here we make use of the fact that infinite ternary square-free strings exist, which was proven
in previous work [26]. We then modify such a string to fulfill the synchronization string property,
using the existence of an infinite binary weak synchronization string.
Theorem 6.4. There exists some ε ∈ (0, 1) and an infinite ε-synchronization string over an alphabet
of size four.

Proof. Take an infinite ternary square-free string T over alphabet {1, 2, 3} [26] and some ε ∈ 11
12 , 1 .
Let S be an infinite weak binary ε0 = (12ε − 11)-synchronization string. Consider the string W that
is similar to T except that the i-th occurrence of symbol 1 in T is replaced with symbol 4 if S[i] = 1.
Note W is still square-free. We claim W is an ε-synchronization string as well.
Let A = W [i, j), B = W [j, k) be two consecutive substrings of W . If k − i < 1/(1 − ε), then
ED(A, B) ≥ 1 > (1 − ε)(k − i) by square-freeness.
Otherwise, k − i ≥ 1/(1 − ε) ≥ 12. Consider all occurrences of 1 and 4 in A and B, which form
consecutive subsequences As and Bs of S respectively. Note that |As | + |Bs | ≥ (k − i − 3)/4, because,
by square-freeness, there cannot be a length-4 substring consisting only of 2’s and 3’s in W .
By weak synchronization property,
ED(As , Bs ) ≥ b(1 − ε0 )(|As | + |Bs |)c
≥ b3(1 − ε)(k − i − 3)c > 3(1 − ε)(k − i) − 9(1 − ε) − 1
≥ (1 − ε)(k − i),
and hence, ED(A, B) ≥ ED(As , Bs ) ≥ (1 − ε)(k − i). Therefore, W is an ε-synchronization
string.

Organization and Acknowledgements
All detailed proofs appear in the appendix. Specifically, proofs in Section 3 appear in Appendix A,
proofs in Section 4 appear in Appendix B, and proofs in Section 6 appear in Appendix C.
The authors thank Raymond Kang for valuable discussions in the early stages of this work,
contributions to Theorem 6.1, and experiments in Appendix A. We also thank Noga Alon for
referring us to the previous work on the twin word problem.

References
[1] Maria Axenovich, Yury Person, and Svetlana Puzynina. A regularity lemma and twins in words.
Journal of Combinatorial Theory, Series A, 120(4):733–743, 2013.
[2] Paul Beame and Dang-Trinh Huynh-Ngoc. On the value of multiple read/write streams for
approximating frequency moments. In Foundations of Computer Science, 2008. FOCS’08.
IEEE 49th Annual IEEE Symposium on, pages 499–508. IEEE, 2008.
[3] Mark Braverman, Ran Gelles, Jieming Mao, and Rafail Ostrovsky. Coding for interactive
communication correcting insertions and deletions. IEEE Transactions on Information Theory,
63(10):6256–6270, 2017.

26

[4] Boris Bukh and Lidong Zhou. Twins in words and long common subsequences in permutations.
Israel Journal of Mathematics, 213(1):183–209, 2016.
[5] Serina Camungol, Narad Rampersad, et al. Avoiding approximate repetitions with respect to
the longest common subsequence distance. inv lve, page 657, 2016.
[6] Karthekeyan Chandrasekaran, Navin Goyal, and Bernhard Haeupler. Deterministic algorithms
for the lovász local lemma. SIAM Journal on Computing, 42(6):2132–2155, 2013.
[7] Max Crochemore. Sharp characterizations of squarefree morphisms. Theoretical Computer
Science, 18(2):221–226, 1982.
[8] Ran Gelles. Coding for interactive communication: A survey, 2015.
[9] Ran Gelles and Bernhard Haeupler. Capacity of interactive communication over erasure channels
and channels with feedback. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium
on Discrete Algorithms, pages 1296–1311. Society for Industrial and Applied Mathematics,
2015.
[10] Mohsen Ghaffari and Bernhard Haeupler. Optimal error rates for interactive coding ii: Efficiency
and list decoding. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual
Symposium on, pages 394–403. IEEE, 2014.
[11] Mohsen Ghaffari, Bernhard Haeupler, and Madhu Sudan. Optimal error rates for interactive
coding i: Adaptivity and other settings. In Proceedings of the forty-sixth annual ACM symposium
on Theory of computing, pages 794–803. ACM, 2014.
[12] V. Guruswami and P. Indyk. Linear-time encodable/decodable codes with near-optimal rate.
IEEE Transactions on Information Theory, 51(10):3393–3400, Oct 2005. doi:10.1109/TIT.
2005.855587.
[13] Bernhard Haeupler. Interactive channel capacity revisited. In Foundations of Computer Science
(FOCS), 2014 IEEE 55th Annual Symposium on, pages 226–235. IEEE, 2014.
[14] Bernhard Haeupler, Barna Saha, and Aravind Srinivasan. New constructive aspects of the
lovász local lemma. Journal of the ACM (JACM), 58(6):28, 2011.
[15] Bernhard Haeupler and Amirbehshad Shahrasbi. Synchronization strings: codes for insertions
and deletions approaching the singleton bound. In Proceedings of the 49th Annual ACM
SIGACT Symposium on Theory of Computing, pages 33–46. ACM, 2017.
[16] Bernhard Haeupler and Amirbehshad Shahrasbi. Synchronization strings: Explicit constructions,
local decoding, and applications. arXiv preprint arXiv:1710.09795, 2017.
[17] Bernhard Haeupler, Amirbehshad Shahrasbi, and Madhu Sudan. Synchronization strings: List
decoding for insertions and deletions, 2018.
[18] Bernhard Haeupler, Amirbehshad Shahrasbi, and Ellen Vitercik. Synchronization strings:
Channel simulations and interactive coding for insertions and deletions. arXiv preprint
arXiv:1707.04233, 2017.
[19] Gillat Kol and Ran Raz. Interactive channel capacity. In Proceedings of the forty-fifth annual
ACM symposium on Theory of computing, pages 715–724. ACM, 2013.
27

[20] Dalia Krieger, Pascal Ochem, Narad Rampersad, and Jeffrey Shallit. Avoiding approximate
squares. In International Conference on Developments in Language Theory, pages 278–289.
Springer, 2007.
[21] John Leech. 2726. a problem on strings of beads. The Mathematical Gazette, 41(338):277–278,
1957.
[22] Hugues Mercier, Vijay K Bhargava, and Vahid Tarokh. A survey of error-correcting codes
for channels with symbol synchronization errors. IEEE Communications Surveys & Tutorials,
12(1), 2010.
[23] Robin A Moser and Gábor Tardos. A constructive proof of the general lovász local lemma.
Journal of the ACM (JACM), 57(2):11, 2010.
[24] Robert Shelton. Aperiodic words on three symbols. Journal für die Reine und Angewandte
Mathematik, 321:195–209, 1981.
[25] Robert O Shelton and Raj P Soni. Aperiodic words on three symbols. iii. Journal für die Reine
und Angewandte Mathematik, 330:44–52, 1982.
[26] A Thue. Über unendliche zeichenreihen (1906). Selected Mathematical Papers of Axel Thue.
Universitetsforlaget, 1977.
[27] Axel Thue. Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, von Axel Thue...
J. Dybwad, 1912.
[28] Boris Zolotov. Another solution to the thue problem of non-repeating words. arXiv preprint
arXiv:1505.00019, 2015.

28

Appendices
A

Lower-bounds for ε in Infinite ε-Synchronization Strings

It is known from Section 6.2 that infinite synchronization strings exist over alphabet sizes |Σ| ≥ 4.
A natural question to ask is the optimal value of ε for each such |Σ|. Formally, we seek to discover
Bk = inf{ε : there exists an infinite ε-synchronization string with |Σ| = k}
for small values of k. To that end, a program was written to find an upper bound for Bk for k ≤ 6.
The program first fixes an ε, then exhaustively enumerates all possible ε-synchronization strings
over an alphabet size of k by increasing length. If the program terminates, then this ε is a proven
lower bound for Bk . Among every pair of consecutive substrings in each checked string that failed
the ε-synchronization property, we find the one that has the lowest edit distance relative to their
total length and such fraction would be a lower-bound for Bk as well. Such experimentally obtained
lower-bounds for alphabets of size 3, 4, 5, and 6 are listed in Table 1.
k
3
4
5
6

Bk ≥ ·
12/13
10/13
2/3
18/29

Table 1: Computationally proven lower-bounds of Bk

29

