# In search of maximum non-overlapping codes

Lidija Stanovnik  University of Ljubljana, Faculty of Computer and Information
Science, Večna pot 113, Ljubljana, Slovenia  Miha Moškon  University of
Ljubljana, Faculty of Computer and Information Science, Večna pot 113,
Ljubljana, Slovenia  Miha Mraz  University of Ljubljana, Faculty of Computer
and Information Science, Večna pot 113, Ljubljana, Slovenia

###### Abstract

Non-overlapping codes are block codes that have arisen in diverse contexts of
computer science and biology. Applications typically require finding non-
overlapping codes with large cardinalities, but the maximum size of non-
overlapping codes has been determined only for cases where the codeword length
divides the size of the alphabet, and for codes with codewords of length two
or three. For all other alphabet sizes and codeword lengths no computationally
feasible way to identify non-overlapping codes that attain the maximum size
has been found to date. Herein we characterize maximal non-overlapping codes.
We formulate the maximum non-overlapping code problem as an integer
optimization problem and determine necessary conditions for optimality of a
non-overlapping code. Moreover, we solve several instances of the optimization
problem to show that the hitherto known constructions do not generate the
optimal codes for many alphabet sizes and codeword lengths. We also evaluate
the number of distinct maximum non-overlapping codes.

#### Keywords:

non-overlapping code, cross-bifix-free code, mutually uncorrelated code,
strong comma-free code

##  1 Introduction

_Non-overlapping codes_ , also known under the terms _strongly regular codes_
[10], _cross-bifix-free codes_ [1, 6], _mutually uncorrelated codes_ (MU-
codes) [15, 12], and _strong comma-free codes_ [7], are block codes with the
property that no prefix of a codeword occurs as a suffix of any not
necessarily distinct codeword. Over the past sixty years, they have provided
solutions to various problems in different fields. They construct a special
class of finite automata [11], provide codes for frame synchronization [1],
and even build addresses for DNA-storage [15, 12]. For most purposes, non-
overlapping codes with large cardinalities are favorable and therefore
researchers have developed several constructions of such codes [2, 5, 3, 6,
4].

Identifying non-overlapping codes with the largest cardinality, however,
appears to be a hard nut to crack and little progress has been done in this
direction. Chee et al. [6] searched through binary codes of lengths up to
sixteen to show that known constructions of non-overlapping codes obtain the
maximum size, but for larger alphabet sizes and code lengths, their approach
cannot be used due to its double exponential time complexity and exponential
space complexity. Later, Blackburn [5] provided formulas for the size of
maximum two- and three-letter non-overlapping codes, and for the sizes of
maximum $q$-ary $n$-letter non-overlapping codes where $n$ divides $q$. The
number of maximal two- and three-letter, and maximum three-letter non-
overlapping codes was recently computed [9].

Fimmel et al. [9] also proposed an algorithm that they believe generates all
maximal non-overlapping codes. After proving the statement holds, it could
theoretically be used to find the maximum $q$-ary $n$-letter non-overlapping
codes, but the approach is impractical due to its double exponential time and
exponential space complexity. Nevertheless, by studying some equivalence
relations we show that the time complexity of their algorithm can be reduced
to exponential and the space complexity of their algorithm to polynomial in
$n$. We further prove some necessary conditions for optimality. We employ the
results to compute optimal values for the size and number of maximum non-
overlapping codes that were not yet known, and demonstrate that other existing
constructions fail to generate a maximum code for many alphabet sizes and
codeword lengths.

This article is arranged as follows: Section 2 introduces definitions and
briefly presents existing methods to construct non-overlapping codes. In
Section 3 we prove that the algorithm proposed by Fimmel et al. generates non-
overlapping codes only, determine the sizes of the constructed codes, show
that the algorithm produces all maximal non-overlapping codes and characterize
when a code is maximal. We formulate an integer optimization problem for non-
overlapping codes of maximum size and determine necessary conditions for its
optimality in Section 4. Section 5 provides exact formulas for the number of
maximal four-letter non-overlapping codes, and the size and the number of
maximum four-letter non-overlapping codes. In Section 6 we compare the largest
codes produced by existing constructions and the newly computed optimal
solutions for small parameter values.

##  2 Definitions and constructions

Throughout this paper, we let $\Sigma$ be a finite alphabet with $q\geq 2$
elements and $n$ a positive integer.

######  Definition 1.

Words $c_{1}=x_{1}\cdots x_{n}\in\Sigma^{n}$ and $c_{2}=y_{1}\cdots
y_{n}\in\Sigma^{n}$ are _non-overlapping_ if

$\displaystyle\forall k\in\\{1,\dots,n-1\\}:\quad$ $\displaystyle
x_{n+1-k}\cdots x_{n}\neq y_{1}\cdots y_{k}$ and $\displaystyle
y_{n+1-k}\cdots y_{n}\neq x_{1}\cdots x_{k}.$

In other words, no prefix of $c_{1}$ occurs as a suffix of $c_{2}$ and vice
versa.

######  Example 1.

The word VRV is not non-overlapping because V occurs as a prefix and a suffix.
The words VRT and KRT are non-overlapping because the prefixes V, VR, K and KR
never occur as suffixes.

######  Definition 2.

$X\subseteq\Sigma^{n}$ is a _non-overlapping code_ if all (not necessarily
distinct) elements $c_{1},c_{2}\in X$ are non-overlapping.

######  Definition 3.

A non-overlapping code $X$ is _maximal_ , if it cannot be expanded, meaning
that every $n$-letter word over $\Sigma$ that is not in $X$ either has a
prefix that overlaps with a suffix in $X$ or a suffix that overlaps with a
prefix in $X$.

######  Example 2.

The non-overlapping code $\\{\text{VRT},\text{KRT}\\}$ is not maximal, because
it could be expanded by adding the word RRT. The non-overlapping code
$\\{\text{VRT},\text{VVT},\text{RVT},\text{RRT}\\}$ is maximal over the
alphabet $\\{\text{V},\text{R},\text{T}\\}$, because no other three-letter
word exists that starts with V or R, ends with T, and includes neither prefix
VT nor prefix RT.

######  Definition 4.

A non-overlapping code $X$ is _maximum_ if for all non-overlapping codes
$Y\subseteq\Sigma^{n}$:

$\lvert X\rvert\geq\lvert Y\rvert.$

We denote this greatest cardinality with $S(q,n)$ and define $N(q,n)$ to be
the number of codes that achieve it.

######  Remark 1.

Every maximum non-overlapping code is maximal.

Non-overlapping codes were first defined by Levenshtein [10] who found that
they coincide with a class of codes for which there exists a decoding
automaton that correctly decodes a sequence of input letters independently of
the choice of the initial state of the automaton [11]. This property ensures
that errors in the input word and random transitions between states of the
automaton do not affect the decoding of subsequent input words. He proposed
Construction 1 (below) that generates non-overlapping codes of not necessarily
optimal sizes. He also established a lower bound
$S(q,n)\gtrsim\frac{q-1}{qe}\frac{q^{n}}{n}$ [10] and an upper bound
$S(q,n)\leq\left(\frac{n-1}{n}\right)^{n-1}\frac{q^{n}}{n}$ [11] for the size
of a maximum non-overlapping code.

######  Construction 1.

Let $n>1$ and $q>1$ be integers and $1\leq k\leq n-1$. Denote by $C$ the set
of all codewords $s=(s_{1},s_{2},\dots,s_{n})\in\mathbb{Z}_{q}^{n}$ such that
$s_{1}\neq 0$, $s_{n-k}\neq 0$, $s_{n-k+1}=s_{n-k+2}=\cdots=s_{n}=0$, and
$(s_{1},\dots,s_{n-k})$ does not contain $k$ consecutive 0’s. Then $C$ is a
non-overlapping code.

His construction was later rediscovered by Chee et al. [6], who reversed the
codewords. They showed that the size of a code $C$ obtained using this
construction and parameter $2\leq k\leq n-2$ equals $\lvert
C\rvert=(q-1)^{2}F_{k,q}(n-k-2)$ with initialization
$F_{k,q}(i)=q^{i}\;\forall i\in\\{0,\dots,k-1\\}$ and a $(q-1)$-weighted
$k$-generalized Fibonacci recurrence relation
$F_{k,q}(n)=(q-1)\sum_{l=1}^{k}F_{k,q}(n-l)$. Additionally, they searched for
maximum binary non-overlapping codes with $n\leq 16$ by determining a maximum
clique in a graph with vertices that correspond to words in
$\mathbb{Z}_{2}^{n}$ that are non-overlapping and edges that correspond to
pairs of non-overlapping words. Note that this approach cannot be efficiently
applied to larger alphabets and code lengths because computing a maximum
clique of a graph with $m$ vertices requires $O(2^{\frac{m}{4}})$ time [13]
and the graph has $O(q^{n})$ vertices.

Another construction that generates binary non-overlapping codes was provided
by Bilotta et al. [4]. It uses Dyck sequences as described in Construction 2,
and for both even length $2n+2$ and odd length $2n+1$ it generates codes with
$n$-th Catalan number of codewords, $\lvert C_{2n+2}\rvert=\lvert
C_{2n+1}\rvert=\frac{1}{n+1}\binom{2n}{n}$.

######  Construction 2.

Let $\mathcal{D}$ be a set of Dyck sequences of even length $2n$, i.e. binary
sequences composed of $n$ zeros and $n$ ones such that no prefix of the
sequences has more zeros than ones. The set of sequences of even length
$C_{2n+2}=\\{1a0:a\in\mathcal{D}\\}$ and the set of sequences of odd length
$C_{2n+1}=\\{1a:a\in\mathcal{D}\\}$ are non-overlapping codes.

This class of codes is not restricted to binary codes as Wang and Wang [14]
showed that any binary non-overlapping code can be generalized to $q$-ary non-
overlapping codes using Construction 3 (below). The size of the generalized
codes was, however, not further theoretically analysed.

######  Construction 3.

Let $S$ be a binary non-overlapping code and $(I,J)$ a partition of
$\mathbb{Z}_{q}$ with $q\geq 2$. For $w=w_{1}\cdots w_{n}\in S$ we define a
mapping $\Phi(w)=\\{y_{1}\cdots y_{n}\mid y_{i}\in I\text{ if }w_{i}=0\text{
and }y_{i}\in J\text{ if }w_{i}=1\\}$. The set $\Phi(S)=\bigcup_{w\in
S}\Phi(w)$ is a non-overlapping code.

Blackburn [5] provided the class of non-overlapping codes described in
Construction 4 (below) and proved that it contains a maximum non-overlapping
code when $n$ divides $q$, as a code with $k=n-1$ and $S=I^{k}$ reaches the
upper bound set by Levenshtein. He also proved that
$S(q,2)=\lfloor\frac{q}{2}\rfloor\lceil\frac{q}{2}\rceil$ and
$S(q,3)=\left[\frac{2q}{3}\right]^{2}\left(q-\left[\frac{2q}{3}\right]\right)$,
where $\left[x\right]$ denotes the rounding of $x$ to the closest integer. He
conjectured that for $n>2$ and sufficiently large $q$, a maximum non-
overlapping code is given by Construction 4 with $k=n-1$ and some value of
$l$, but this conjecture is yet to be (dis)proven.

######  Construction 4.

Let $k$ and $l$ be such integers that $1\leq k\leq n-1$ and $1\leq l\leq q-1$.
Let $\Sigma=I\cup J$ be a partition of a set $\Sigma$ of cardinality $q$ into
two parts $I$ and $J$ of cardinalities $l$ and $q-l$ respectively. Let
$S\subseteq I^{k}\subseteq\Sigma^{k}$. Let $C_{S,J}(n)$ be the set of all
words $c\in\Sigma^{n}$ such that $c_{1}c_{2}\cdots c_{k}\in S$, $c_{k+1}\in
J$, $c_{n}\in J$ and no subword of the word $c_{k+2}c_{k+3}\cdots c_{n-1}$
lies in $S$. Then $C_{S,J}(n)$ is a non-overlapping code.

The size of a general code obtained using Blackburn’s construction is still an
open problem, but Wang and Wang [14] provided a formula for the case
$S=I^{k}$. It states that for $k\in\\{n-1,n-2\\}:\;$ $\lvert
C_{I^{k},J}(n)\rvert=\lvert I\rvert^{k}\lvert J\rvert^{n-k}$ and for $k\leq
n-3:\;$ $\lvert C_{I^{k},J}(n)\rvert=q\cdot\lvert
C_{I^{k},J}(n-1)\rvert-\lvert I\rvert^{k}\lvert J\rvert\cdot\lvert
C_{I^{k},J}(n-k-1)\rvert$.

Barcucci et al. [3] defined a set of non-overlapping codes given in
Construction 5 (below) that are generated using colored Motzkin words and
showed they are all maximal. They did not compute the size of the codes.

######  Definition 5.

A sequence in $\mathbb{Z}_{q+2}^{n}$ that contains the same number of zeros
and ones, such that no prefix of the sequences has more zeros than ones is
called a _$q$ -colored Motzkin word_ of length $n$. We denote the set of all
such sequences with $\mathcal{M}_{q}(n)$.

######  Definition 6.

An _elevated $q$-colored Motzkin word_ of length $n$ is a sequence $1\alpha
0$, where $\alpha\in\mathcal{M}_{q}(n-2)$. We denote the set of all such words
with $\hat{\mathcal{M}}_{q}(n)$.

######  Construction 5.

$CBFS_{q}(n)=A_{q}(n)\cup B_{q}(n)\cup C_{q}(n)$ is a maximal non-overlapping
code where
$A_{q}(n)=\\{\alpha\beta:\alpha\in\mathcal{M}_{q-2}(i),\beta\in\hat{\mathcal{M}}_{q-2}(n-i)\\}\setminus\\{\alpha\beta:\alpha,\beta\in\hat{\mathcal{M}}_{q-2}(\frac{n}{2})\\}$,
$B_{q}(n)=\\{1\alpha\beta:\beta\in\mathcal{M}_{q-2}(i),\beta\in\hat{\mathcal{M}}_{q-2}(n-i-1)\\}$,
and $C_{q}(n)=\\{\gamma 0:\gamma\in\mathcal{M}_{q-2}(n-1),\gamma\neq u\beta
v,\beta\in\hat{\mathcal{M}}_{q-2}(j)\\}$.

Fimmel, Michel and Strüngmann [7] proposed that three-letter non-overlapping
codes emerged naturally. In living cells the ribosome behaves as a decoding
automata that decodes a sequence of codons to a sequence of amino acids using
the genetic code as a decoding function. Data suggests that ancestral genetic
code was indeed a non-overlapping code. Inspired by Blackburn’s work, they
recently showed that the set of maximal two-letter non-overlapping codes over
$\Sigma$ is exactly the set of partitions of $\Sigma$ into two non-empty parts
and counted that there are $2^{q}-2$ such codes [9]. Moreover, they
characterized maximal three-letter non-overlapping codes (see Proposition 1
below) and counted that there are $\sum_{m=1}^{q-1}\binom{q}{m}2^{m(q-m)}$
such codes. They also determined
$N(q,3)=2\binom{q}{\left[\frac{2q}{3}\right]}$.

######  Definition 7.

Let $L$ and $R$ be sets of strings.
(i) $\left(LR\right)$ denotes the concatenation of sets $L$ and $R$, i.e. the
set of all strings of the form $lr$, where $l\in L$ and $r\in R$,
(ii) $L^{i}$ denotes the concatenation of the set $L$ with itself $i$ times,
(iii) the Kleene star denotes the smallest superset that is closed under
concatenation and includes the empty set $L^{*}=\bigcup_{i\geq 0}L^{i}$ and
(iv) the Kleene plus denotes the smallest superset that is closed under
concatenation and does not include the empty set $L^{+}=\bigcup_{i>0}L^{i}$.

######  Proposition 1 ([9], Theorem 5.3).

The set of maximal three-letter non-overlapping codes is exactly the set of
all three-letter codes $X_{3}=(L_{1}R_{2})\cup(L_{2}R_{1})$, where
(i) $(L_{1},R_{1})$ is a partition of $\Sigma$ into two non-empty parts, and
(ii) $(L_{2},R_{2})$ is a partition of $(L_{1}R_{1})$.

##  3 Constructing maximal non-overlapping codes

Fimmel et al. [9] show that a straightforward generalisation of Proposition 1
does not hold. The underlying construction can, however, be generalized as
described in Construction 6 (below). They posit that it is composed of non-
overlapping codes only and that it contains all maximal non-overlapping codes.

######  Construction 6.

Let $n\geq 3$. We define $\mathcal{M}_{q,n}$ to be the set of all codes
$C=\bigcup_{i=1}^{n-1}\left(L_{i}R_{n-i}\right)\subseteq\Sigma^{n}$, where
(i) $(L_{1},R_{1})$ is a partition of $\Sigma$ into two non-empty parts, and
(ii) $(L_{i},R_{i})$ is a partition of
$\bigcup_{j=1}^{i-1}\left(L_{j}R_{i-j}\right)$ for every
$i\in\\{2,\dots,n-1\\}$.

Before proving both statements, let us observe that the mapping from the
partitions of Construction 6 to the set of codes $C\subseteq\Sigma^{n}$ is not
injective. Two distinct collections of partitions
$(L_{i},R_{i})_{i=1,\dots,n-1}$ can determine the same code as demonstrated by
Example 3.

######  Example 3.

Set $n=4$ and take a partition $(L_{1},R_{1})$ of $\Sigma$. If
$L_{2}=(L_{1}R_{1})$, $R_{2}=\emptyset$ and $L_{3}=\emptyset$,
$R_{3}=(L_{1}R_{2})\cup(L_{2}R_{1})=(L_{1}R_{1}^{2})$, we get a code
$C_{1}=(L_{1}R_{3})\cup(L_{2}R_{2})\cup(L_{3}R_{1})=(L_{1}^{2}R_{1}^{2})$. Now
observe $L_{2}=\emptyset$, $R_{2}=(L_{1}R_{1})$ and
$L_{3}=(L_{1}R_{2})\cup(L_{2}R_{1})=(L_{1}^{2}R_{1})$, $R_{3}=\emptyset$. We
get a code
$C_{2}=(L_{1}R_{3})\cup(L_{2}R_{2})\cup(L_{3}R_{1})=(L_{1}^{2}R_{1}^{2})$. In
particular, $C_{1}=C_{2}$.

######  Proposition 2.

Let $C=\bigcup_{i=1}^{n-1}\left(L_{i}R_{n-i}\right)\in\mathcal{M}_{q,n}$.
Define $X\coloneqq\bigcup_{i=1}^{2n+1}X_{i}$, such that

$\displaystyle X_{2i-1}$ $\displaystyle\coloneqq L_{i},$ $\displaystyle
X_{2i}$ $\displaystyle\coloneqq R_{i},$ $\displaystyle X_{2n+1}$
$\displaystyle\coloneqq C.$

No proper prefix in $X$ occurs as a proper suffix in $X$.

###### Proof.

Assume, for sake of contradiction, that the statement does not hold. Let $p$
be the length of the shortest proper prefix in $X$ that occurs as a proper
suffix in $X$. Let $i$ be the smallest index such that there exists a word
$w\in X_{i}$ with a prefix $x_{1}\cdots x_{p}$ that occurs as a suffix in $X$.
Let $j$ be the smallest index such that $X_{j}$ contains a word $w^{\prime}$
that ends in $x_{1}\cdots x_{p}$. Clearly $i,j>2$, as $X_{1}$ and $X_{2}$ have
no proper prefixes nor suffixes. Therefore
$w\in(L_{k}R_{\lceil\frac{i}{2}\rceil-k})\subseteq X_{i}$ for some
$k<\lceil\frac{i}{2}\rceil$.

If $k<p$, then $x_{k+1}\cdots x_{p}$ is a prefix in
$R_{\lceil\frac{i}{2}\rceil-k}=X_{2{\lceil\frac{i}{2}\rceil}-2k}$ and suffix
in $X_{j}$ that is shorter than $p$. Since $\lceil\frac{i}{2}\rceil-k>1$
(otherwise $x_{1}\cdots x_{p}=w$ is not a proper prefix of $w$), this
contradicts the minimality of $p$. If $p<k$, then $x_{1}\cdots x_{p}$ is a
prefix in $L_{k}=X_{2k-1}$. Since for $l>2$ every one-letter prefix in $X$ is
from $L_{1}$ and every one-letter suffix from $R_{1}$, $p>1$ and $k>2$.
Therefore $2k-1>1$ and $2k-1<i$. This contradicts minimality of $i$. So $p=k$
and hence $x_{1}\cdots x_{p}\in L_{k}=L_{p}$. Repeat the symmetric procedure
on $X_{j}$ to obtain a word
$w^{\prime}\in(L_{\lceil\frac{j}{2}\rceil-l}R_{l})$ ending in $x_{1}\cdots
x_{p}$ and $p=l$. So $x_{1}\cdots x_{p}\in R_{l}=R_{p}$. Then $x_{1}\cdots
x_{p}\in L_{p}\cap R_{p}$, but $L_{p}\cap R_{p}=\emptyset$ by definition. ∎

######  Theorem 3.

$C\in\mathcal{M}_{q,n}$ is a non-overlapping code.

###### Proof.

The theorem follows directly from Proposition 2. ∎

######  Corollary 1.

(i) $L_{k}\cup R_{k}$ is a non-overlapping code for all $1\leq k\leq n-1$.
(ii) If $w_{1}\cdots w_{k}\in L_{k}\cup R_{k}$ for some $k>1$, then $w_{1}\in
L_{1}$ and $w_{k}\in R_{1}$.

###### Proof.

The corollary follows directly from Construction 6 and Theorem 3. ∎

###  3.1 Size of $C\in\mathcal{M}_{q,n}$

Now that we know that every $C\in\mathcal{M}_{q,n}$ is non-overlapping, we
want to determine the size of $C$. Theorem 6 (below) shows that it depends on
the sizes of the sets partitions $(L_{i},R_{i})_{i=1,\dots,n-1}$ only. Before
stating and proving the formula, we define a finite sequence of decompositions
due to Fimmel et al. [8] and prove some of its properties.

######  Definition 8.

Let $w\in\bigcup_{i=1}^{n-1}\left(L_{i}R_{n-i}\right)$ and let us set
$L\coloneqq\bigcup_{i<n}L_{i}$ and $R\coloneqq\bigcup_{i<n}R_{i}$. Define
$\\{p_{k}(w)\\}_{k\geq 0}$ to be a sequence of decompositions of $w$ in
$\left(L\left(L\cup R\right)^{*}R\right)$ encoded with a binary word ${p_{k}}$
over the alphabet $\\{\text{l},\text{r}\\}$ such that
(i) $p_{0}(w)\in\left(\text{l}\\{\text{l},\text{r}\\}^{n-2}\text{r}\right)$
with $p_{0}(w)_{i}=\text{l}$ if $w_{i}\in L_{1}$ and $p_{0}(w)_{i}=\text{r}$
if $w_{i}\in R_{1}$,
(ii) if $p_{k}(w)\in\left(\text{l}\\{\text{l},\text{r}\\}^{+}\text{r}\right)$,
then $p_{k+1}(w)\in\left(\text{l}\\{\text{l},\text{r}\\}^{*}\text{r}\right)$
is obtained by replacing each occurrence of lr in $p_{k}(w)$ by l if lr
corresponds to a subword $w^{\prime}$ of $w$ in $(L_{i}R_{j})\subseteq
L_{i+j}$, or by r if it corresponds to a subword $w^{\prime}$ of $w$ in
$(L_{i}R_{j})\subseteq R_{i+j}$ for some positive integers $i$ and $j$.

######  Proposition 4.

Let $x\in L$ and $y\in R$. If the length of $xy$ is at most $n-1$, then $xy\in
L\cup R$.

###### Proof.

Since $x\in L$ there exists some $i$, $0<i<n$, such that $x\in L_{i}$. Since
$y\in R$ there exists some $j$, $0<j<n$, such that $y\in R_{j}$. Therefore
$xy\in(L_{i}R_{j})\subseteq\bigcup_{k<i+j}(L_{k}R_{i+j-k})$. If $i+j<n$, the
latter is partitioned into $(L_{i+j},R_{i+j})$, so either $xy\in
L_{i+j}\subseteq L$ or $xy\in R_{i+j}\subseteq R$. ∎

######  Proposition 5.

The sequence $\\{p_{k}(w)\\}_{k\geq 0}$ is
(i) well-defined,
(ii) finite and its last element is lr.

###### Proof.

(i) Every letter in $w$ belongs to $\Sigma=L_{1}\cup R_{1}$. If lr occurs as a
proper substring of $p_{k}(w)$, then by Proposition 4 it corresponds to some
$k$-letters long substring $w^{\prime}$ of $w$, such that $w^{\prime}\in L\cup
R$. Therefore lr can be replaced by either l or r. If lr occurs at the
beginning of $p_{k}(w)$, then it is replaced by l. Otherwise $w^{\prime}\in
R_{i}$ for some $i<n-1$ and there is a word in $(L_{1}R_{i})\in L\cup R$ that
ends in $w^{\prime}$ which contradicts Proposition 2. A symmetric observation
guarantees that a lr at the end of $p_{k}(w)$ is replaced by r.

(ii) If $p_{k}(w)\in(\text{l}\\{\text{l},\text{r}\\}^{+}\text{r})$, then the
length of $p_{k+1}(w)$ is strictly smaller then the length of $p_{k}(w)$. If
$p_{k}(w)\not\in(\text{l}\\{\text{l},\text{r}\\}^{+}\text{r})$, then $p_{k+1}$
is not defined and $p_{k}(w)$ is the last element of the sequence. The
previous step reveals that then $p_{k}(w)=\text{lr}$. ∎

######  Corollary 2.

Let $1<l<n$ and $w\in L_{l}\cup R_{l}$.
The sequence $\\{p_{k}(w)\\}_{k\geq 0}$ is finite. The last element of the
sequence is lr.

###### Proof.

If $w$ belongs to $L_{l}$ (alternatively to $R_{l}$), then it also belongs to
$L_{l}\cup R_{l}$. The latter is a non-overlapping code as noted in Corollary
1, so the statement follows from Proposition 5. ∎

######  Theorem 6.

$\lvert\bigcup_{i=1}^{n-1}\left(L_{i}R_{n-i}\right)\rvert=\sum_{i=1}^{n-1}\lvert
L_{i}\rvert\lvert R_{n-i}\rvert$.

###### Proof.

It is sufficient to explain that for every word
$w\in\bigcup_{i=1}^{n-1}\left(L_{i}R_{n-i}\right)$ there is a unique pair of
sets $L_{i}$ and $R_{n-i}$ such that $w\in\left(L_{i}R_{n-i}\right)$.

Assume, for sake of contradiction, that there exists a word $w=w_{1}\cdots
w_{n}\in\bigcup_{i=1}^{n-1}\left(L_{i}R_{n-i}\right)$ and indices $i<j$ such
that $w\in(L_{i}R_{n-i})$ and $w\in(L_{j}R_{n-j})$. Observe the sequence
$\\{p_{k}(w_{i+1}\cdots w_{j})\\}_{k\geq 0}$.
STEP 1: The sequence $\\{p_{k}(w_{i+1}\cdots w_{j})\\}_{k\geq 0}$ is well-
defined, i.e. $\forall k\geq
0:\;p_{k}\in(\text{l}\\{\text{l},\text{r}\\}^{*}\text{r})$.

(i) $p_{0}(w_{i+1}\cdots
w_{j})\in(\text{l}\\{\text{l},\text{r}\\}^{j-i-2}\text{r})$.
Since $1\leq i<j$ and $w_{1}\cdots w_{j}\in L_{j}$, Corollary 1 implies
$w_{j}\in R_{1}$. $i+1\leq j<n$ and $w_{i+1}\cdots w_{n}\in R_{n-i}$, so
Corollary 1 implies $w_{i+1}\in L_{1}$.

(ii) If $p_{k}(w_{i+1}\cdots
w_{j})\in(\text{l}\\{\text{l},\text{r}\\}^{+}\text{r})$, then
$p_{k+1}(w_{i+1}\cdots
w_{j})\in(\text{l}\\{\text{l},\text{r}\\}^{*}\text{r})$.
Suppose lr occurs in a decomposition $p_{k}(w_{i+1}\cdots
w_{j})\in(\text{l}\\{\text{l},\text{r}\\}^{+}\text{r})$ and corresponds to a
substring $w^{\prime}$. Then the same lr occurs in the part of the
decomposition $p_{k}(w_{1}\cdots w_{j})$ that corresponds to the substring
$w^{\prime}$ of $w_{i+1}\cdots w_{j}$. Therefore, $w^{\prime}\in L\cup R$. If
$w^{\prime}$ is a suffix of $w_{i+1}\cdots w_{j}$, then lr is also a suffix of
$p_{k}(w_{1}\cdots w_{j})$ and $w^{\prime}\in R$. At the same time lr occurs
in the part of the decomposition $p_{k}(w_{i+1}\cdots w_{n})$ that corresponds
to $w^{\prime}$. If $w^{\prime}$ is a prefix of $w_{i+1}\cdots w_{j}$, then lr
occurs as a prefix of $p_{k}(w_{i+1}\cdots w_{n})$ and $w^{\prime}\in L$.
Therefore $p_{k+1}(w_{i+1}\cdots
w_{j})\in(\text{l}\\{\text{l},\text{r}\\}^{*}\text{r})$.
STEP 2: The sequence $\\{p_{k}(w_{i+1}\cdots w_{j})\\}_{k\geq 0}$ is finite,
the last element $p_{\hat{k}}(w_{i+1}\cdots w_{j})=\text{lr}$.
We noticed in step 1 that every decomposition $p_{k}(w_{i+1}\cdots w_{j})$ is
a substring of $p_{k}(w_{i+1}\cdots w_{n})$. Since $\\{p_{k}(w_{i+1}\cdots
w_{n})\\}_{k\geq 0}$ is finite due to Corollary 2, $\\{p_{k}(w_{i+1}\cdots
w_{j})\\}_{k\geq 0}$ is also finite. From part (ii) of step 1 it follows that
the last element $p_{\hat{k}}(w_{i+1}\cdots w_{j})$ equals lr.
STEP 3: $w_{i+1}\cdots w_{j}\in L_{j-i}\cap R_{j-i}$.
The process described in part (ii) of Step 1 shows that
$p_{\hat{k}}(w_{1}\cdots
w_{j})\in(\text{l}\\{\text{l},\text{r}\\}^{*}\text{lr})$ and the last lr
corresponds to $w_{i+1}\cdots w_{j}$, so $w_{i+1}\cdots w_{j}\in R_{j-i}$. Due
to the same argument $w_{i+1}\cdots w_{j}$ corresponds to the first lr of
$p_{\hat{k}}(w_{i+1}\cdots
w_{n})\in(\text{lr}\\{\text{l},\text{r}\\}^{*}\text{r})$, so $w_{i+1}\cdots
w_{j}\in L_{j-i}$. $(L_{j-i},R_{j-i})$ is a partition, so $L_{j-i}\cap
R_{j-i}=\emptyset$ and $w_{i+1}\cdots w_{j}=\epsilon$, but this contradicts
the assumption that $i<j$. ∎

###  3.2 Characterization of maximal non-overlapping codes

We will now show that $\mathcal{M}_{q,n}$ contains all maximal non-overlapping
codes and determine which collections of partitions
$(L_{i},R_{i})_{i=1,\dots,n-1}$ generate maximal non-overlapping codes.

######  Proposition 7.

Every maximal non-overlapping code is contained in $\mathcal{M}_{q,n}$.

###### Proof.

Let $X$ be a maximal $q$-ary $n$-letter non-overlapping code. Now construct
the sets $(L_{i},R_{i})$ corresponding to $X$ for $i<n$ as follows

$\displaystyle L_{1}$ $\displaystyle\coloneqq\\{x\in\Sigma\mid\text{there
exists a word in $X$ beginning with $x$}\\},$ $\displaystyle R_{1}$
$\displaystyle\coloneqq\Sigma\setminus L_{1},$

and for $1<i<n$

$\displaystyle L_{i}$ $\displaystyle\coloneqq\\{x_{1}\cdots
x_{i}\in\bigcup_{j<i}(L_{j}R_{i-j})\mid\text{there exists a word in $X$
beginning with $x_{1}\cdots x_{i}$}\\},$ $\displaystyle R_{i}$
$\displaystyle\coloneqq\bigcup_{j<i}(L_{j}R_{i-j})\setminus L_{i}.$

Note that if a word in $X$ ends in $x_{1}\cdots
x_{i}\in\bigcup_{j<i}(L_{j}R_{i-j})$, then $x_{1}\cdots x_{i}\in R_{i}$
(otherwise $x_{1}\cdots x_{i}\in L_{i}$ and there exists a word in X that
starts in $x_{1}\cdots x_{i}$ by definition of $L_{i}$ which contradicts the
fact that $X$ is non-overlapping). Define
$Z\coloneqq\bigcup_{j<i}(L_{j}R_{i-j})$. We will prove that $X\subseteq Z$.
Since $X$ is maximal and $Z$ is non-overlapping by Theorem 3, it immediately
follows that $X=Z$.

Let $w\in X$. We will show that $\\{p_{k}(w)\\}_{k\geq 0}$ is well-defined.
Every letter in $w$ belongs to $L_{1}\cup R_{1}=\Sigma$ since
$w\in\Sigma^{n}$. The first letter of $w$ belongs to $L_{1}$ by definition of
$L_{1}$ and we explained earlier that the last letter belongs to $R_{1}$.
Decomposition $p_{0}(w)$ is therefore well-defined. Now suppose
$p_{k}(w)\in\\{\text{l}\\{\text{l},\text{r}\\}^{*}\text{r}\\}$ for some $k\geq
0$. If $p_{k}(w)=\text{lr}$, then there exists some $i$ such that
$w\in(L_{i}R_{n-i})$ and $w\in Z$. Otherwise
$p_{k}(w)\in\\{\text{l}\\{\text{l},\text{r}\\}^{+}\text{r}\\}$ and there
exists some lr in $p_{k}(w)$ that corresponds to a proper substring
$w^{\prime}$ of $w$. The length of $w^{\prime}$ is at most $n-1$ and
$w^{\prime}\in L\cup R$, so lr can be replaced by either l or r in
$p_{k+1}(w)$. If $p_{k}(w)$ starts with lr that corresponds to a $k$-letters
long substring of $w$, $w_{L}$, then by definition of $L_{k}$ $w_{L}\in L_{k}$
and lr is replaced by l in $p_{k+1}(w)$. If $p_{k}(w)$ ends with lr that
corresponds to a $k$-letters long substring of $w$ $w_{R}$, then $w_{R}\not\in
L_{k}$ since $X$ is a non-overlapping code. So $w_{R}\in R_{k}$ and lr is
replaced by r in $p_{k+1}(w)$. The length of $p_{k+1}(w)$ is strictly smaller
than the length of $p_{k}(w)$ so the sequence $\\{p_{k}(w)\\}_{k\geq 0}$ is
indeed finite and its last element is lr. As shown earlier this implies that
$w\in Z$. ∎

######  Theorem 8.

$C\in\mathcal{M}_{q,n}$ is maximal if and only if all the following statements
hold.
(i) If $L_{i}$ is non-empty and $R_{n-i}=\emptyset$, then every $x\in L_{i}$
is a prefix in some $L_{j}$ such that $i<j<n$ and $R_{n-j}$ is non-empty or
$q=2$, $i=\frac{n}{2}$ and $\lvert L_{i}\rvert=1$.
(ii) If $R_{i}$ is non-empty and $L_{n-i}=\emptyset$, then every $x\in R_{i}$
is a suffix in some $R_{j}$ such that $i<j<n$ and $L_{n-j}$ is non-empty or
$q=2$, $i=\frac{n}{2}$ and $\lvert R_{i}\rvert=1$.
(iii) If $q=2$ and $L_{\frac{n}{2}}=\\{u\\}$ such that $u$ is not a prefix in
$C$, then for every non-empty $L_{j}$, $2\leq j\leq\frac{n}{2}-2$, the word in
$(L_{j}L_{\frac{n}{2}})$ is a prefix in $C$. Moreover, the word in
$(L_{1}L_{\frac{n}{2}})$ is a prefix in $C$ or $L_{\frac{n}{2}-1}$ is empty
and for every non-empty $L_{j}$, $1\leq j\leq n/2-2$, the word in
$(L_{j}L_{1}L_{\frac{n}{2}})$ is a prefix in C.
(iv) If $q=2$ and $R_{\frac{n}{2}}=\\{u\\}$ such that $u$ is not a suffix in
$C$, then for every non-empty $R_{j}$, $2\leq j\leq\frac{n}{2}-2$, the word in
$(R_{\frac{n}{2}}R_{j})$ is a suffix in $C$. Moreover, the word in
$(R_{\frac{n}{2}}R_{1})$ is a suffix in $C$ or $R_{\frac{n}{2}-1}$ is empty
and for every non-empty $R_{j}$, $1\leq j\leq n/2-2$, the word in
$(R_{\frac{n}{2}}R_{1}R_{j})$ is a suffix in C.

###### Proof.

STEP 1: If $C$ is maximal, then statements (i) to (iv) hold.
Suppose $C=\bigcup_{i<n}(L_{i}R_{n-i})$ is maximal.
(i) Let $x\in L_{i}$. If for every $j$, $i<j<n$, $x$ is not a prefix in
$L_{j}$ or $R_{n-j}$ is empty, then $x$ is not a prefix in
$\bigcup_{j=i}^{n-1}(L_{j}R_{n-j})\subseteq C$. It is also not a prefix in
$\bigcup_{j<i}(L_{j}R_{n-j})$, otherwise $R_{n-j}$ has a prefix that is a
suffix of $x\in L_{i}$. So $x$ is not a prefix in $C$. It is also not a suffix
in $C$ due to Proposition 2.

CASE 1: $i\neq\frac{n}{2}$
$R_{n-i}$ is empty, therefore
$L_{n-i}=\bigcup_{j<n-i}(L_{j}R_{n-i-j})\setminus
R_{n-i}=\bigcup_{j<n-i}(L_{j}R_{n-i-j})$ is non-empty. Observe the set
$(L_{n-i}x)$. If $yx$ is a suffix in $(L_{n-i}x)$, then $y$ is a suffix in
$L_{n-i}$, and it is neither a prefix in $C$ nor in $L_{n-i}$ by Proposition
2. Since $n-i\neq\frac{n}{2}$, then $x$ itself is not a prefix in
$(L_{n-i}x)$, and we already showed that it is not a prefix in $C$. If $y$ is
a suffix of length $k$ in $(L_{n-i}x)$ that is shorter than $x$, then it is
not a prefix in $C$ by Proposition 2. If $k\leq n-i$ then $y$ is not a prefix
in $(L_{n-i}x)$ as it cannot be a prefix in $L_{n-i}$ by Proposition 2. If
$k>n-i$ then $y$ can be a prefix in $(L_{n-i}x)$ only if it has a suffix that
is a prefix in $x$, but $x$ is itself non-overlapping. Therefore
$C\cup(L_{n-i}x)$ is a non-overlapping code. This contradicts the maximality
of $C$.

CASE 2: $i=\frac{n}{2}$
Suppose there exists $y\in L_{\frac{n}{2}}\setminus\\{x\\}$. Observe the word
$yx$. If $z$ is a suffix of $x$, then it is not a prefix of $y$ nor of any
word in $C$ by Proposition 2. If $z$ is a suffix of $yx$ longer than
$\frac{n}{2}$, then $z$ is not a prefix of $yx$ nor of any word in $C$,
otherwise $y$ is not non-overlapping or it has a suffix that is a prefix of a
word in $C$ which contradicts Proposition 2. So $C\cup\\{yx\\}$ is a non-
overlapping code, but this contradicts the maximality of $C$. Now notice that
for $j>2$, $\lvert L_{j}\cup R_{j}\rvert=\sum_{k<j}\lvert L_{k}\rvert\lvert
R_{j-k}\rvert\geq\lvert L_{1}\rvert\lvert R_{j-1}\rvert+\lvert
L_{j-1}\rvert\lvert R_{1}\rvert\geq\lvert L_{j-1}\rvert+\lvert
R_{j-1}\rvert=\lvert L_{j-1}\cup R_{j-1}\rvert$. If $j=2$, then $\lvert
L_{j}\cup R_{j}\rvert=\lvert L_{1}\rvert\lvert R_{1}\rvert$. In both cases
$\lvert L_{\frac{n}{2}}\rvert=1$ is only possible if $\lvert L_{1}\cup
R_{1}\rvert=2$.
(ii) The proof is symmetric to the proof of statement (i).
(iii) The case $\lvert L_{\frac{n}{2}}\rvert$ is only possible if either
$L_{2}=\cdots=L_{\frac{n}{2}-2}=\emptyset$ or
$R_{2}=\cdots=R_{\frac{n}{2}-2}=\emptyset$. Suppose that for some
$k\in\\{1,\dots,\frac{n}{2}-2\\}$ the word in $(L_{k}L_{\frac{n}{2}})$ is not
a prefix in X. Then if $L_{\frac{n}{2}-k}$ is non-empty,
$(L_{\frac{n}{2}-k}L_{k}L_{\frac{n}{2}})\cup C$ is a non-overlapping code
larger than C. If $k>1$, $L_{k}$ is non-empty if and only if
$L_{\frac{n}{2}-k}$ is non-empty. If $k=1$, $L_{\frac{n}{2}-1}=\emptyset$ and
$L_{l}$ non-empty for some $l<\frac{n}{2}-1$ it follows that
$(L_{\frac{n}{2}-l-1}L_{l}L_{1}L_{\frac{n}{2}})\cup C$ is a non-overlapping
code larger than C if the word in $(L_{l}L_{1}L_{\frac{n}{2}})$ is not a
prefix in C.
(iv) The proof is symmetric to the proof of statement (iii).
STEP 2: If statements (i) to (iv) hold, then $C$ is maximal.
Let $C=\bigcup_{i<n}(L_{i}R_{n-i})\in\mathcal{M}_{q,n}$ that satisfies (i) and
(ii). Suppose $C$ is not maximal. Then there exists a word
$w\in\Sigma^{n}\setminus C$ such that no proper prefix of $w$ is a suffix in
$C$ and no proper suffix of $w$ is a prefix in $C$. Let
$\\{\hat{p}_{k}(w)\\}_{k\geq 0}$ be a sequence of decompositions of
$w\in\Sigma^{n}\setminus C$ in $(L\cup R)^{+}$ encoded with a binary word
$\hat{p}_{k}$ over the alphabet $\\{\text{l},\text{r}\\}$ such that
(a) $\hat{p}_{0}(w)\in\\{\text{l},\text{r}\\}^{n}$ with
$\hat{p}_{0}(w)_{i}=\text{l}$ if $w_{o}\in L_{1}$ and
$\hat{p}_{0}(w)=\text{r}$ if $w_{i}\in R_{1}$,
(b) if $\hat{p}_{k}(w)$ contains lr as a proper substring, then obtain
$\hat{p}_{k+1}(w)\in\\{\text{l},\text{r}\\}^{+}$ by replacing each occurrence
of lr in $\hat{p}_{k}(w)$ by l if lr corresponds to a subword $w^{\prime}$ of
$w$ in $(L_{i}R_{j})\subseteq L_{i+j}$ or by r if it corresponds to a subword
$w^{\prime}$ of $w$ in $(L_{i}R_{j})\subseteq R_{i+j}$ for some positive
integers $i$ and $j$.

Decomposition $\hat{p}_{0}(w)$ is well-defined as every letter of $w$ is an
element of $L_{1}\cup R_{1}=\Sigma$. If $\hat{p}_{k}(w)$ contains a substring
lr that corresponds to a substring $w^{\prime}$ of $w$ then there exist
integers $i$ and $j$ such that $w^{\prime}\in L_{i+j}\cup R_{i+j}$. The
sequence is therefore well-defined. The length of decompositions is strictly
decreasing, so the sequence $\\{\hat{p}_{k}(w)\\}_{k\geq 0}$ is finite. Denote
the last element with $\hat{p}_{\hat{k}}(w)$. The sequences in
$\\{\text{l},\text{r}\\}^{+}$ that have no lr as a proper substring are of the
forms lr, r+l+, l+, r+. Decomposition $\hat{p}_{\hat{k}}(w)$ cannot be lr,
otherwise $w\in C$.

If $n$ is odd or every word in $L_{\frac{n}{2}}$ is a prefix in $C$ and every
word in $R_{\frac{n}{2}}$ is a suffix in $C$, it follows from (i) that for
every $x\in L$ there exists a word $w^{\prime}\in C$ that starts in $x$ and
from (ii) that for every $x\in R$ there exists a word $w^{\prime}\in C$ that
ends in $x$. Therefore $C\cup\\{w\\}$ is not non-overlapping if
$\hat{p}_{\hat{k}}(w)\in\text{r}^{+}\text{l}^{+}\cup\text{r}^{+}\cup\text{l}^{+}$.

Otherwise $q=2$ and $\lvert L_{\frac{n}{2}}\cup R_{\frac{n}{2}}\rvert=1$. The
latter is only possible if either $L_{2}=\cdots=L_{\frac{n}{2}-2}=\emptyset$
or $R_{2}=\cdots=R_{\frac{n}{2}-2}=\emptyset$. Since every word in $L$ of
length distinct from $\frac{n}{2}$ is a prefix in $C$ by (i) and every word in
$R$ of length distinct from $\frac{n}{2}$ is a suffix in $C$ by (ii),
$\hat{p}_{\hat{k}}(w)\in\text{r}^{+}\text{l}^{+}$ implies
$\hat{p}_{\hat{k}}(w)=\text{rl}$ and
$w\in(R_{\frac{n}{2}}L_{\frac{n}{2}})=\emptyset$. Therefore
$\hat{p}_{\hat{k}}(w)\in\text{r}^{+}\cup\text{l}^{+}$ and
$w\in(L^{+}LL_{\frac{n}{2}})\cup(R_{\frac{n}{2}}RR^{+})$ since $w$ itself is
non-overlapping. Suppose $R_{\frac{n}{2}}$ is empty (the proof when
$L_{\frac{n}{2}}$ is empty is symmetric using statement (iv) instead of (ii)).
The set $(R_{\frac{n}{2}}RR^{+})$ is empty and hence
$w\in(L^{+}LL_{\frac{n}{2}})$. If $(L_{k}L_{\frac{n}{2}})$ is non-empty for
some $k\in\\{2,\dots,\frac{n}{2}-2\\}$, then $w\in(L_{k}L_{\frac{n}{2}})$ is a
prefix in $C$ by (iii). Also the word in $(L_{1}L_{\frac{n}{2}})$ is a prefix
in $C$ or $L_{\frac{n}{2}-1}$ is empty and for every nonempty $L_{k}$,
$k\in\\{1,\dots,\frac{n}{2}-2\\}$, the word in $(L_{k}L_{1}L_{\frac{n}{2}})$
is a prefix in $C$. Hence $w\in(L_{1}L_{\frac{n}{2}-1}L_{\frac{n}{2}})$ and
$L_{\frac{n}{2}-1}$ is non-empty, but the word in
$(L_{\frac{n}{2}-1}L_{\frac{n}{2}})$ is a prefix in
$(L_{\frac{n}{2}-1}R_{\frac{n}{2}+1})\subseteq C$ since $L_{\frac{n}{2}}$ is
not a prefix in C. No word can therefore be added to $C$, so $C$ is maximal. ∎

We showed earlier that the mapping from collections
$(L_{i},R_{i})_{i=1,\dots,n-1}$ to non-overlapping codes is not injective.
Nevertheless, we will show that almost every maximal non-overlapping code
corresponds to exactly one collection of partitions. Unfortunately, a
characterization of maximal non-overlapping codes in terms of partition sizes
cannot be given as demonstrated by Example 4, and we will therefore not use it
directly when computing $S(q,n)$.

######  Proposition 9.

Let
$C=\bigcup_{i<n}(L_{i}R_{n-i})=\bigcup_{i<n}(\hat{L}_{i}\hat{R}_{n-i})\in\mathcal{M}_{q,n}$
be a maximal non-overlapping code. Then

$\displaystyle\forall i<\frac{n}{2}:\;L_{i}$ $\displaystyle=\hat{L}_{i}\text{
and }R_{i}=\hat{R}_{i}.$

Moreover, exactly one of the following statements holds.
(i) $\forall i\geq\frac{n}{2}:\;L_{i}=\hat{L}_{i}$ and  $R_{i}=\hat{R}_{i}$,
(ii) $q=2$, $L_{\frac{n}{2}}=\hat{R}_{\frac{n}{2}}$ and
$\hat{L}_{\frac{n}{2}}=R_{\frac{n}{2}}=\emptyset$,
(iii) $q=2$, $L_{\frac{n}{2}}=\hat{R}_{\frac{n}{2}}=\emptyset$ and
$\hat{L}_{\frac{n}{2}}=R_{\frac{n}{2}}$.

###### Proof.

Suppose there exists some $i$ such that $L_{i}\neq\hat{L}_{i}$ and $\forall
j<i:L_{j}=\hat{L}_{j}$. $L_{j}\cup R_{j}=\hat{L}_{j}\cup\hat{R}_{j}$ for all
$j\leq i$ by definition, so $R_{j}=\hat{R}_{j}$ for all $j<i$. Furthermore at
least one of the sets $L_{i}\cap\hat{R}_{i}$ and $R_{i}\cap\hat{L}_{i}$ is
non-empty. Without loss of generality suppose
$L_{i}\cap\hat{R}_{i}\neq\emptyset$ (otherwise $R_{i}\cap\hat{L}_{i}$ is non-
empty and a symmetric argument follows). Let $x\in L_{i}\cap\hat{R}_{i}$. From
Proposition 2 we know that $x$ is neither a prefix nor a suffix in $C$. If
$i\neq\frac{n}{2}$ then Theorem 8 implies that $C$ is not maximal, so
$L_{j}=R_{j}$ for every $j$, $1\leq j<n$. If $i=\frac{n}{2}$ then Theorem 8
implies $q=2$, $\lvert
L_{\frac{n}{2}}\rvert=1=\lvert\hat{R}_{\frac{n}{2}}\rvert$ and
$\hat{L}_{\frac{n}{2}}=R_{\frac{n}{2}}=\emptyset$, so
$L_{\frac{n}{2}}=\hat{R}_{\frac{n}{2}}$. ∎

######  Corollary 3.

If $n$ is odd or $q\geq 3$, then every maximal non-overlapping code
corresponds to exactly one partition $(L_{i},R_{i})_{i=1,\dots,n-1}$.

###### Proof.

The second and third case of Proposition 9 cannot hold for an odd $n$ nor for
$q\geq 3$. ∎

######  Example 4.

Let $n=6$ and $\Sigma=\\{0,1,2\\}$. Set $L_{1}=\\{0\\}$, $R_{1}=\\{1,2\\}$,
$L_{2}=\emptyset$, $R_{2}=\\{01,02\\}$, $L_{3}=\\{001\\}$, $R_{3}=\\{002\\}$,
$L_{4}=\\{0002\\}$, $R_{4}=\\{0011,0012\\}$. If we set
$L_{5}=\\{00011,00012\\}$ and $R_{5}=\\{00101,00102,00021,00022\\}$, we obtain

$\displaystyle C_{1}=\\{$ $\displaystyle
000101,000102,000021,000022,001002,000201,000202,000111,000112,$
$\displaystyle 000121,000122\\},$

which is not maximal as $C_{1}\cup\\{001101\\}$ is a non-overlapping code. Now
take $L_{5}=\\{00101,00102\\}$ and $R_{5}=\\{00011,00012,00021,00022\\}$. Code

$\displaystyle C_{2}=\\{$ $\displaystyle
000011,00012,000021,000022,001002,000201,000202,001011,001012,$ $\displaystyle
001021,001022\\}$

has partitions of the same sizes as $C_{1}$ but is maximal due to Theorem 8.

##  4 An integer optimization problem

Now that we know that $M_{q,n}$ contains all maximal non-overlapping codes and
we have a formula to compute their sizes, we can clearly determine the maximum
non-overlapping codes by maximizing the value $\sum_{i=1}^{n-1}\lvert
L_{i}\rvert\lvert R_{n-i}\rvert$ over all constraints given by Construction 6.
An integer optimization problem is formulated as follows (see Proposition 10
below). We call this formulation SQN(q, n) throughout the paper.

######  Proposition 10 (SQN).

$\displaystyle S(q,n)=$ $\displaystyle\max\sum_{i=1}^{n-1}x_{i}y_{n-i}$
subject to $\displaystyle x_{1}+y_{1}=q$ $\displaystyle
x_{i}+y_{i}=\sum_{j=1}^{i-1}x_{j}y_{i-j}\quad\forall i>1$ $\displaystyle
x_{1},y_{1}>0$ $\displaystyle x_{i},y_{i}\geq 0\quad\forall i>1$
$\displaystyle x_{i},y_{i}\in\mathbb{Z}\quad\forall i\geq 1.$

If $(x^{*},y^{*})$ is an optimal solution to the above optimization problem,
then $C=\bigcup_{i=1}^{n-1}\left(L_{i}R_{n-i}\right)$ is a maximum non-
overlapping code if it satisfies
(i) $\left(L_{1},R_{1}\right)$ is a partition of $\Sigma$ with $\lvert
L_{1}\rvert=x_{1}^{*}$ and
(ii) for $n>i>1:\;\left(L_{i},R_{i}\right)$ is a partition of
$C=\bigcup_{j=1}^{i-1}\left(L_{j}R_{i-j}\right)$ with $\lvert
L_{i}\rvert=x_{i}^{*}$.

###### Proof.

The proposition follows directly from the definition of $S(q,n)$, Construction
6, Theorem 3 and Theorem 6 if we denote the size of the set $L_{i}$ by $x_{i}$
and the size of the set $R_{i}$ by $y_{i}$. ∎

The evaluation of the objective function for all feasible solutions to SQN
requires $O\left(q^{n^{2}}\right)$ time and $\Theta\left(n\right)$ space. If
we also want to store all the optimal solutions, space requirement increases
to $\Theta\left(nm\right)$ where $m$ denotes the number of optimal solutions.
To determine $N(q,n)$ from the optimal solutions of SQN(q, n), we have to
evaluate whether any pair of solutions of SQN(q, n) constructs the same
maximum code to prevent double counting. Proposition 11 shows that for most
parameter values one can compute the value $N(q,n)$ directly.

######  Proposition 11.

$N(q,n)=\sum_{\begin{subarray}{c}x,y\textnormal{ optimal}\\\
\textnormal{solution of
SQN(q,n)}\end{subarray}}\binom{q}{x_{1}}\cdot\prod_{i=2}^{n-1}\binom{\sum_{j=1}^{i-1}x_{j}y_{i-j}}{x_{i}}$

if at least one of the following holds:
(i) $q>2$,
(ii) $n$ is odd,
(iii) no pair of solutions $(x,y),(\hat{x},\hat{y})$ of SQN(q,n) satisfies
$x_{i}=\hat{x}_{i}$ for all $i<\frac{n}{2}$,
$x_{\frac{n}{2}}=\hat{y}_{\frac{n}{2}}=0$,
$\hat{x}_{\frac{n}{2}}=y_{\frac{n}{2}}=1$.

###### Proof.

Let $(x,y)$ be an optimal solution of SQN. There are $\binom{q}{x_{1}}$
choices for a partition of $\Sigma$ into $\left(L_{1},R_{1}\right)$ such that
$\lvert L_{1}\rvert=x_{1}$ and $\lvert R_{1}\rvert=y_{1}$. For fixed
partitions $\left(L_{1},R_{1}\right),\dots,\left(L_{i-1},R_{i-1}\right)$ there
are $\binom{\sum_{j=1}^{i-1}\lvert L_{j}\rvert\lvert
R_{i-j}\rvert}{x_{i}}=\binom{\sum_{j=1}^{i-1}x_{j}y_{i-j}}{x_{i}}$ choices for
a partition of $\bigcup_{j=1}^{i-1}\left(L_{j}R_{i-j}\right)$ with $\lvert
L_{i}\rvert=x_{i}$ and $\lvert R_{i}\rvert=y_{i}$. No code is double counted
as the non-overlapping codes corresponding to solutions of SQN(q, n) are
distinct due to Proposition 9 and Corollary 3. ∎

###  4.1 Reduction of SQN

The set of feasible solutions of SQN can be reduced. We provide some
equivalence transformations on $(x,y)$ that preserve the value of the
objective function. These enable us to evaluate only one feasible solution for
each equivalence set. Moreover, we will show that every maximum
$C\in\mathcal{M}_{q,n}$ either satisfies the property

$\lvert L_{i}\rvert\lvert R_{i}\rvert=0\qquad\forall i>\frac{n}{2},$ (1)

or it can be mapped to a non-overlapping code that satisfies property (1)
using a transformation we will define later.

######  Proposition 12.

$(x,y)$ is an optimal solution of SQN if and only if $(y,x)$ is optimal for
SQN.

###### Proof.

Feasible solutions $(x,y)$ and $(y,x)$ have the same value of the objective
functions $\sum_{i=1}^{n-1}x_{i}y_{n-i}=\sum_{i=1}^{n-1}y_{i}x_{n-i}$. ∎

######  Proposition 13.

Let $((x_{1},\dots,x_{n-1}),(y_{1},\dots,y_{n-1}))$ be a feasible solution of
SQN. If there exists some $i>1$ such that $x_{k}=y_{k}$ for all $k\leq i$,
then $((x_{1},\dots,x_{n-1}),(y_{1},\dots,y_{n-1}))$ is an optimal solution of
SQN if and only if
$((x_{1},\dots,x_{i},y_{i+1},\dots,y_{n-1}),(y_{1},\dots,y_{i},x_{i+1},\dots
x_{n-1}))$ is an optimal solution.

###### Proof.

Clearly
$((x_{1},\dots,x_{i},y_{i+1},\dots,y_{n-1}),(y_{1},\dots,y_{i},x_{i+1},\dots,x_{n-1}))$
is feasible. Let $o$ denote the objective function of
$((x_{1},\dots,x_{n-1}),(y_{1},\dots,y_{n-1}))$ and $\hat{o}$ the objective
function of
$((x_{1},\dots,x_{i},y_{i+1},\dots,y_{n-1}),(y_{1},\dots,y_{i},x_{i+1},\dots,x_{n-1}))$.

$\displaystyle\hat{o}=$ $\displaystyle\sum_{\begin{subarray}{c}1\leq j\leq
i\\\ n-j>i\end{subarray}}x_{j}x_{n-j}+\sum_{\begin{subarray}{c}1\leq j\leq
i\\\ n-j\leq i\end{subarray}}x_{j}y_{n-j}+\sum_{\begin{subarray}{c}i<j<n\\\
n-j>i\end{subarray}}y_{j}x_{n-j}+\sum_{\begin{subarray}{c}i<j<n\\\ n-j\leq
i\end{subarray}}y_{j}y_{n-j}$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}1\leq j\leq i\\\
n-j>i\end{subarray}}y_{j}x_{n-j}+\sum_{\begin{subarray}{c}1\leq j\leq i\\\
n-j\leq i\end{subarray}}y_{j}x_{n-j}+\sum_{\begin{subarray}{c}i<j<n\\\
n-j>i\end{subarray}}y_{j}x_{n-j}+\sum_{\begin{subarray}{c}i<j<n\\\ n-j\leq
i\end{subarray}}y_{j}x_{n-j}$ $\displaystyle=$ $\displaystyle\sum_{1\leq j\leq
i}y_{j}x_{n-j}+\sum_{i<j<n}y_{j}x_{n-j}=o.\mbox{}$ ∎

Before providing a formula for expressing the sizes of the sets
$L_{i+1},R_{i+1},\dots,L_{n-1},R_{n-1}$ is terms of $\lvert L_{1}\rvert,\lvert
R_{1}\rvert,\dots,\lvert L_{i}\rvert,\lvert R_{i}\rvert$ when property (1)
holds, let us first introduce few more definitions.

######  Definition 9.

Let $i$ be an integer such that $n>i>\frac{n}{2}$ and $\lvert
L_{k}\rvert\lvert R_{k}\rvert=0$ for all $k>i$.
(i) Coefficients $\delta_{R,k}$ and $\delta_{L,k}$ for $k>i$ express which of
the sets $R_{k}$ and $L_{k}$ is non-empty:

$\displaystyle\delta_{R,k}$ $\displaystyle\coloneqq\begin{cases}1&\text{if
}L_{k}=\emptyset\\\ 0&\text{if }R_{k}=\emptyset,\end{cases}$
$\displaystyle\delta_{L,k}$ $\displaystyle\coloneqq\begin{cases}1&\text{if
}R_{k}=\emptyset\\\ 0&\text{if }L_{k}=\emptyset.\end{cases}$

(ii) The coefficients $p_{jk}$ satisfy the following relations:

$\displaystyle p_{jj}$ $\displaystyle\coloneqq 1,$ $\displaystyle p_{jk}$
$\displaystyle\coloneqq\sum_{m=k}^{j-1}\left(\delta_{L,i+m}\lvert
R_{j-m}\rvert+\delta_{R,i+m}\lvert L_{j-m}\rvert\right)p_{mk}.$

(iii) Condition $c_{i}$ is defined as follows. We will use its value to
determine which part of partition $(L_{i},R_{i})$ is empty.

$\displaystyle c_{i}\coloneqq\sum_{j=1}^{n-1-i}\left(\delta_{L,i+j}\lvert
R_{n-i-j}\rvert+\delta_{R,i+j}\lvert
L_{n-i-j}\rvert\right)\left(\sum_{l=1}^{j}p_{jl}(\lvert R_{l}\rvert-\lvert
L_{l}\rvert)\right)+\lvert R_{n-i}\rvert$ $\displaystyle-\lvert
L_{n-i}\rvert.$

######  Proposition 14.

Let $i$ be an integer such that $n>i>\frac{n}{2}$ and let $\lvert
L_{i+j}\rvert\lvert R_{i+j}\rvert=0$ for all $1\leq j<n-i$. Then

$\lvert L_{i+j}\rvert=\delta_{L,i+j}\sum_{l=1}^{j}\sum_{k=l}^{i}p_{jl}\lvert
L_{k}\rvert\lvert R_{i+l-k}\rvert$ $\lvert
R_{i+j}\rvert=\delta_{R,i+j}\sum_{l=1}^{j}\sum_{k=l}^{i}p_{jl}\lvert
L_{k}\rvert\lvert R_{i+l-k}\rvert.$

###### Proof.

We will prove the proposition by induction on $j$. Let $j=1$. Because $\lvert
L_{i+1}\rvert\lvert R_{i+1}\rvert=0,$

$\displaystyle\lvert L_{i+1}\rvert$
$\displaystyle=\delta_{L,i+1}\sum_{k=1}^{i}\lvert L_{k}\rvert\lvert
R_{i+1-k}\rvert$ $\displaystyle=\delta_{L,i+1}\sum_{k=1}^{i}p_{11}\lvert
L_{k}\rvert\lvert R_{i+1-k}\rvert$
$\displaystyle=\delta_{L,i+1}\sum_{l=1}^{1}\sum_{k=1}^{i}p_{1l}\lvert
L_{k}\rvert\lvert R_{i+1-k}\rvert,$

and following the same procedure $\lvert
R_{i+1}\rvert=\delta_{R,i+1}\sum_{l=1}^{1}\sum_{k=1}^{n}p_{1l}\lvert
L_{k}\rvert\lvert R_{i+1-k}\rvert$. Now let us suppose that the statement
holds for all positive integers smaller than $j$. The set
$\bigcup_{k=1}^{i+j-1}\left(L_{k}R_{i+j-k}\right)$ can be expressed as a union
of those words that end in $R_{i+k}$, words that start in $L_{i+k}$, and words
that start and end in substrings shorter or equal to $i$. Hence

$\displaystyle\bigcup_{k=1}^{i+j-1}\left(L_{k}R_{i+j-k}\right)=$
$\displaystyle\bigcup_{k=i+1}^{i+j-1}\left(L_{i+j-k}R_{k}\right)\cup\bigcup_{k=i+1}^{i+j-1}\left(L_{k}R_{i+j-k}\right)$
$\displaystyle\cup\bigcup_{k=j}^{i}\left(L_{k}R_{i+j-k}\right).$

Since $i>\frac{n}{2}$, these three sets never overlap, so the size of their
union is equal to the sum of their sizes. The size of
$\bigcup_{k=j}^{i}\left(L_{k}R_{i+j-k}\right)$ can be expressed using the
coefficients $p_{jj}$ as follows.

$\displaystyle\lvert\bigcup_{k=j}^{i}\left(L_{k}R_{i+j-k}\right)\rvert=\sum_{k=j}^{i}\lvert
L_{k}\rvert\lvert R_{i+j-k}\rvert=\sum_{k=j}^{i}p_{jj}\lvert L_{k}\rvert\lvert
R_{i+j-k}\rvert.$

To compute the size of the sets
$\bigcup_{k=i+1}^{i+j-1}\left(R_{k}L_{i+j-k}\right)\cup\bigcup_{k=i+1}^{i+j-1}\left(L_{k}R_{i+j-k}\right)$,
we apply the induction hypothesis, then change the order of summation,
introduce $\bar{k}\coloneqq k-i$, and recognise the formula for $p_{jl}$.

$\displaystyle\sum_{k=i+1}^{i+j-1}\lvert R_{k}\rvert\lvert
L_{i+j-k}\rvert+\sum_{k=i+1}^{i+j-1}\lvert L_{k}\rvert\lvert R_{i+j-k}\rvert$
$\displaystyle=\sum_{k=i+1}^{i+j-1}\sum_{l=1}^{k-i}\sum_{m=l}^{i}p_{k-i,l}\lvert
L_{m}\rvert\lvert R_{i+l-m}\rvert\left(\lvert
L_{i+j-k}\rvert\delta_{R,k}+\lvert R_{i+j-k}\rvert\delta_{L,k}\right)$
$\displaystyle=\sum_{l=1}^{j-1}\sum_{m=l}^{i}\sum_{k=i+l}^{i+j-1}p_{k-i,l}\lvert
L_{m}\rvert\lvert R_{i+l-m}\rvert\left(\lvert
L_{i+j-k}\rvert\delta_{R,k}+\lvert R_{i+j-k}\rvert\delta_{L,k}\right)$
$\displaystyle=\sum_{l=1}^{j-1}\sum_{m=l}^{i}\left(\sum_{\bar{k}=l}^{j-1}p_{\bar{k},l}\left(\lvert
L_{j-\bar{k}}\rvert\delta_{R,i+\bar{k}}+\lvert
R_{j-\bar{k}}\rvert\delta_{L,i+\bar{k}}\right)\right)\lvert L_{m}\rvert\lvert
R_{i+l-m}\rvert$ $\displaystyle=\sum_{l=1}^{j-1}\sum_{m=l}^{i}p_{jl}\lvert
L_{m}\rvert\lvert R_{i+l-m}\rvert.$

We now combine the results to obtain

$\displaystyle\lvert L_{i+j}\rvert$
$\displaystyle=\delta_{L,i+j}\sum_{k=1}^{i+j-1}\lvert L_{k}\rvert\lvert
R_{i+j-k}\rvert$ $\displaystyle=\delta_{L,i+j}\left(\sum_{k=j}^{i}p_{jj}\lvert
L_{k}\rvert\lvert R_{i+j-k}\rvert+\sum_{l=1}^{j-1}\sum_{m=l}^{i}p_{jl}\lvert
L_{m}\rvert\lvert R_{i+l-m}\rvert\right)$
$\displaystyle=\delta_{L,i+j}\sum_{l=1}^{j}\sum_{m=l}^{i}p_{jl}\lvert
L_{m}\rvert\lvert R_{i+l-m}\rvert,$

and equivalently

$\lvert R_{i+j}\rvert=\delta_{R,i+j}\sum_{l=1}^{j}\sum_{m=l}^{i}p_{jl}\lvert
L_{m}\rvert\lvert R_{i+l-m}\rvert.\mbox{}$ ∎

######  Theorem 15.

There exists a maximum non-overlapping code
$C=\bigcup_{i=1}^{n-1}\left(L_{i}R_{n-i}\right)$ satisfying the property
$\forall i>\frac{n}{2}:\;|L_{i}\rvert\lvert R_{i}\rvert=0$.
Moreover, when $i>\frac{n}{2}$ the condition $c_{i}$ from Definition 9
satisfies:
(i) $c_{i}\geq 0$ if $R_{i}=\emptyset$ and
(ii) $c_{i}\leq 0$ if $L_{i}=\emptyset$ .

###### Proof.

Let $C=\bigcup_{i=1}^{n-1}\left(L_{i}R_{n-i}\right)$ be a maximum non-
overlapping code satisfying the property that there exists an integer $j$,
$\frac{n}{2}<j\leq n-1$, such that $\lvert L_{j}\rvert\lvert R_{j}\rvert\neq
0$. Let us denote the largest such integer by $m$. Now rearrange the formula
$\lvert C\rvert=\sum_{j=1}^{n-1}\lvert L_{j}\rvert\lvert R_{n-j}\rvert$ in
order to apply Proposition 14 to it.

$\displaystyle\lvert C\rvert=$ $\displaystyle\sum_{j=m+1}^{n-1}\left(\lvert
L_{j}\rvert\lvert R_{n-j}\rvert+\lvert R_{j}\rvert\lvert
L_{n-j}\rvert\right)+\sum_{j=n-m}^{m}\lvert L_{j}\rvert\lvert R_{n-j}\rvert$
$\displaystyle=$ $\displaystyle\sum_{j=1}^{n-1-m}\left(\lvert
L_{m+j}\rvert\lvert R_{n-m-j}\rvert+\lvert R_{m+j}\rvert\lvert
L_{n-m-j}\rvert\right)+\sum_{j=n-m}^{m}\lvert L_{j}\rvert\lvert R_{n-j}\rvert$
$\displaystyle=$ $\displaystyle\sum_{j=1}^{n-1-m}\left(\delta_{L,m+j}\lvert
R_{n-m-j}\rvert+\delta_{R,m+j}\lvert
L_{n-m-j}\rvert\right)\left(\sum_{l=1}^{j}\sum_{k=l}^{m}p_{jl}\lvert
L_{k}\rvert\lvert R_{m+l-k}\rvert\right)$
$\displaystyle+\sum_{j=n-m}^{m}\lvert L_{j}\rvert\lvert R_{n-j}\rvert.$

Define
$\bar{C}\coloneqq\bigcup_{i=1}^{n-1}\left(\bar{L}_{i}\bar{R}_{n-i}\right)$
such that

$\forall i<m:\bar{L}_{i}\coloneqq L_{i}\text{ and }\bar{R}_{i}\coloneqq
R_{i},$ $\bar{L}_{m}\coloneqq\begin{cases}\emptyset&\text{if }c_{m}\leq 0\\\
\bigcup_{i=1}^{m-1}\left(\bar{L}_{i}\bar{R}_{m-i}\right)&\text{if }c_{m}>0,\\\
\end{cases}$
$\bar{R}_{m}\coloneqq\begin{cases}\bigcup_{i=1}^{m-1}\left(\bar{L}_{i}\bar{R}_{m-i}\right)&\text{if
}c_{m}\leq 0\\\ \emptyset&\text{if }c_{m}>0,\\\ \end{cases}$

and $\forall j\in\\{1,\dots,n-1-m\\}$:

$\bar{L}_{m+j}=\begin{cases}\emptyset&\text{if }L_{m+j}=\emptyset\\\
\bigcup_{i=0}^{m+j-1}(\bar{L}_{i}\bar{R}_{m+j-i})&\text{if
}R_{m+j}=\emptyset,\end{cases}$
$\bar{R}_{m+j}=\begin{cases}\bigcup_{i=0}^{m+j-1}(\bar{L}_{i}\bar{R}_{m+j-i})&\text{if
}L_{m+j}=\emptyset\\\ \emptyset&\text{if }R_{m+j}=\emptyset.\end{cases}$

$\bar{C}$ is non-overlapping due to Theorem 3. Now we observe the size of the
code $\bar{C}$. From Proposition 14 we get

$\lvert\bar{L}_{m+j}\rvert\coloneqq\delta_{L,m+j}\sum_{l=1}^{j}\sum_{k=l}^{m}p_{jl}\lvert\bar{L}_{k}\rvert\lvert\bar{R}_{m+l-k}\rvert,$
$\lvert\bar{R}_{m+j}\rvert\coloneqq\delta_{R,m+j}\sum_{l=1}^{j}\sum_{k=l}^{m}p_{jl}\lvert\bar{L}_{k}\rvert\lvert\bar{R}_{m+l-k}\rvert,$

and from Theorem 6

$\displaystyle\lvert\bar{C}\rvert=$
$\displaystyle\sum_{j=1}^{n-1}\lvert\bar{L}_{j}\rvert\lvert\bar{R}_{n-j}\rvert=\sum_{j=m+1}^{n-1}\left(\lvert\bar{L}_{j}\rvert\lvert\bar{R}_{n-j}\rvert+\lvert\bar{R}_{j}\rvert\lvert\bar{L}_{n-j}\rvert\right)+\sum_{j=n-m}^{m}\lvert\bar{L}_{j}\rvert\lvert\bar{R}_{n-j}\rvert$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{n-1-m}\left(\lvert\bar{L}_{m+j}\rvert\lvert\bar{R}_{n-m-j}\rvert+\lvert\bar{R}_{m+j}\rvert\lvert\bar{L}_{n-m-j}\rvert\right)+\sum_{j=n-m}^{m}\lvert\bar{L}_{j}\rvert\lvert\bar{R}_{n-j}\rvert$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{n-1-m}\left(\delta_{L,m+j}\lvert\bar{R}_{n-m-j}\rvert+\delta_{R,m+j}\lvert\bar{L}_{n-m-j}\rvert\right)\left(\sum_{l=1}^{j}\sum_{k=l}^{m}p_{jl}\lvert\bar{L}_{k}\rvert\lvert\bar{R}_{m+l-k}\rvert\right)$
$\displaystyle+\sum_{j=n-m}^{m}\lvert\bar{L}_{j}\rvert\lvert\bar{R}_{n-j}\rvert.$

We notice that in the above sum only $\bar{L}_{i}$ and $\bar{R}_{i}$ with
$1\leq i\leq m$ occur. We know that unless $i=m$, it holds that
$\bar{L}_{i}=L_{i}$ and $\bar{R}_{i}=R_{i}$. Therefore

$\displaystyle\lvert\bar{C}\rvert=$
$\displaystyle\sum_{j=1}^{n-1-m}\delta_{L,m+j}\lvert
R_{n-m-j}\rvert\left(\sum_{l=1}^{j}p_{jl}\left(\lvert\bar{L}_{m}\rvert-\lvert
L_{m}\rvert\right)\lvert R_{l}\rvert+\sum_{l=1}^{j}p_{jl}\lvert
L_{l}\rvert\left(\lvert\bar{R}_{m}\rvert-\lvert R_{m}\rvert\right)\right)$
$\displaystyle+$ $\displaystyle\sum_{j=1}^{n-1-m}\delta_{R,m+j}\lvert
L_{n-m-j}\rvert\left(\sum_{l=1}^{j}p_{jl}\left(\lvert\bar{L}_{m}\rvert-\lvert
L_{m}\rvert\right)\lvert R_{l}\rvert+\sum_{l=1}^{j}p_{jl}\lvert
L_{l}\rvert\left(\lvert\bar{R}_{m}\rvert-\lvert R_{m}\rvert\right)\right)$
$\displaystyle+$ $\displaystyle\left(\lvert\bar{L}_{m}\rvert-\lvert
L_{m}\rvert\right)\lvert R_{n-m}\rvert+\lvert
L_{n-m}\rvert\left(\lvert\bar{R}_{m}\rvert-\lvert R_{m}\rvert\right)+\lvert
C\rvert.$

We know that

$\lvert R_{m}\rvert=\sum_{i=1}^{m-1}\lvert L_{i}\rvert\lvert
R_{m-1-i}\rvert-\lvert L_{m}\rvert,$
$\lvert\bar{R}_{m}\rvert=\sum_{i=1}^{m-1}\lvert L_{i}\rvert\lvert
R_{m-1-i}\rvert-\lvert\bar{L}_{m}\rvert,$

and therefore

$\lvert\bar{R}_{m}\rvert-\lvert R_{m}\rvert=\lvert
L_{m}\rvert-\lvert\bar{L}_{m}\rvert.$ $\displaystyle\lvert\bar{C}\rvert=$
$\displaystyle\left(\lvert\bar{L}_{m}\rvert-\lvert
L_{m}\rvert\right)\sum_{j=1}^{n-1-m}\left(\delta_{L,m+j}\lvert
R_{n-m-j}\rvert+\delta_{R,m+j}\lvert
L_{n-m-j}\rvert\right)\left(\sum_{l=1}^{j}p_{jl}\left(\lvert
R_{l}\rvert-\lvert L_{l}\rvert\right)\right)$
$\displaystyle+\left(\lvert\bar{L}_{m}\rvert-\lvert
L_{m}\rvert\right)\left(\lvert R_{n-m}\rvert-\lvert
L_{n-m}\rvert\right)+\lvert C\rvert$ $\displaystyle=$
$\displaystyle\left(\lvert\bar{L}_{m}\rvert-\lvert
L_{m}\rvert\right)c_{m}+\lvert C\rvert.$

Recall that we set

$\lvert\bar{L}_{m}\rvert=0<\lvert L_{m}\rvert\quad\text{ if }\;c_{m}<0,$

and

$\lvert\bar{L}_{m}\rvert=\sum_{i=1}^{m-1}\lvert L_{i}\rvert\lvert
R_{m-1-i}\rvert>\lvert L_{m}\rvert\quad\text{if }\;c_{m}>0,$

so $\lvert\bar{C}\rvert>\lvert C\rvert,$ as soon as $c_{m}\neq 0$ which
contradicts the fact that $C$ is maximum. In the other case, when $c_{m}=0$,
we get $\lvert\bar{C}\rvert=\lvert C\rvert$. Notice that in this case both
$\lvert\bar{C}\rvert$ and $\lvert C\rvert$ are expressed as the same function
in $\lvert L_{1}\rvert,\lvert R_{1}\rvert,\dots,\lvert L_{m-1}\rvert,\lvert
R_{m-1}\rvert$, and indeed $\lvert\bar{L}_{j}\rvert\lvert\bar{R}_{j}\rvert=0$
for all $\frac{n}{2}<j\leq m-1$ if and only if $\lvert L_{j}\rvert\lvert
R_{j}\rvert=0$ for all $\frac{n}{2}<j\leq m-1$. The theorem therefore holds. ∎

The proof revealed that it is easy to determine all maximum non-overlapping
codes if we know all solutions that satisfy Property (1). The algorithm to
generate them is summarized in the following corollary.

######  Corollary 4.

Let $C=\bigcup_{i=1}^{n-1}\left(L_{i}R_{n-i}\right)$ be a maximum non-
overlapping code with $c_{m}=0$ for some $m>\frac{n}{2}$. Define
$\hat{L}_{i}\coloneqq L_{i}$ for $i<m$, $(\hat{L}_{m},\hat{R}_{m})$ a
partition of $\bigcup_{i<m}(L_{i}R_{m-i})$, and for $i>m$

$\displaystyle\hat{L}_{i}$
$\displaystyle\coloneqq\begin{cases}\bigcup_{j<i}(\hat{L}_{j}\hat{R}_{i-j})&\text{if
}c_{i}\geq 0\\\ \emptyset&\text{if }c_{i}<0,\end{cases}$
$\displaystyle\hat{R}_{i}$
$\displaystyle\coloneqq\begin{cases}\emptyset&\text{if }c_{i}\geq 0\\\
\bigcup_{j<i}(\hat{L}_{j}\hat{R}_{i-j})&\text{if }c_{i}<0.\end{cases}$

$C=\bigcup_{i=1}^{n-1}\left(\hat{L}_{i}\hat{R}_{n-i}\right)$ is a maximum non-
overlapping code.

##  5 Exact formulas for four-letter codes

######  Theorem 16.

Let $q\geq 3$. The number of distinct maximal four-letter $q$-ary non-
overlapping codes equals

$\displaystyle\sum_{m=1}^{q-1}\binom{q}{m}\left(2(2^{q-m}-1)^{m(q-m)}+(2^{m}+2^{q-m})^{m(q-m)}-2^{m^{2}(q-m)}-2^{m(q-m)^{2}}\right).$

###### Proof.

By Corollary 3 it is sufficient to count the number of distinct partitions
$(L_{1},R_{1}),(L_{2},R_{2}),(L_{3},R_{3})$ that satisfy the requirements of
Theorem 8. Sets $L_{1}$ and $R_{1}$ cannot be empty by definition. If $L_{2}$
is empty, then for every $y\in R_{2}$ there exists $x\in L_{1}$ such that
$xy\in R_{3}$. $R_{3}$ is therefore non-empty, but $L_{3}$ can be empty as
every $y\in R_{1}$ occurs as a suffix in $R_{2}=(L_{1}R_{1})$. Therefore there
are

$\displaystyle\sum_{m=1}^{q-1}\binom{q}{m}\prod_{j=1}^{m(q-m)}\left(\sum_{i=1}^{q-m}\binom{q-m}{i}\right)$
$\displaystyle=\sum_{m=1}^{q-1}\binom{q}{m}\prod_{j=1}^{m(q-m)}\left(2^{q-m}-1\right)$
$\displaystyle=\sum_{m=1}^{q-1}\binom{q}{m}\left(2^{q-m}-1\right)^{m(q-m)}$

maximal non-overlapping codes with empty $L_{2}$. There are also as many
maximal codes when $R_{2}$ is empty due to a symmetric observation.
Suppose $L_{2}$ and $R_{2}$ are both non-empty. If $L_{3}$ and $R_{3}$ are
non-empty, then the code is clearly maximal. If $L_{3}$ is empty, then every
$x\in R_{1}$ is a suffix in $(L_{2}R_{1})\subseteq R_{3}$, so the code is
maximal. If $R_{3}$ is empty, then every $x\in L_{1}$ is a prefix in
$(L_{2}R_{1})\subseteq L_{3}$, so the code is maximal. Therefore there are

$\displaystyle\sum_{m=1}^{q-1}\binom{q}{m}$
$\displaystyle\sum_{i=1}^{q(m-q)-1}\binom{m(q-m)}{i}\sum_{j=0}^{m^{2}(q-m)+i(q-2m)}\binom{m^{2}(q-m)+i(q-2m)}{j}=$
$\displaystyle=\sum_{m=1}^{q-1}\binom{q}{m}\sum_{i=1}^{q(m-q)-1}\binom{m(q-m)}{i}2^{m^{2}(q-m)+i(q-2m)}$
$\displaystyle=\sum_{m=1}^{q-1}2^{m^{2}(q-m)}\binom{q}{m}\sum_{i=1}^{q(m-q)-1}\binom{m(q-m)}{i}2^{(q-2m)i}$
$\displaystyle=\sum_{m=1}^{q-1}2^{m^{2}(q-m)}\binom{q}{m}\left((1+2^{q-2m})^{m(q-m)}-1-2^{m(q-m)(q-2m)}\right)$

maximal non-overlapping codes with $\lvert L_{2}\rvert\lvert R_{2}\rvert\neq
0$. ∎

Blackburn [5] computed $S(q,2)$ and $S(q,3)$ by proving that Construction 4
with $k=1$ and $k=2$ respectively gives us codes of maximum sizes. Using the
results from the previous section, we further prove that this construction
with $k=3$ always yields the optimum for four-letter codes. Before showing the
result, we will provide Lemma 17 and Proposition 18 regarding the sizes of
codes generated by Construction 4.

######  Lemma 17.

Let $q,n,m\leq\frac{n}{2}$ and $2\leq j\leq n$ be positive integers, and $f$
the following function

$\displaystyle
f(j)=(n-m-1)\left(\frac{(n-1)q-m}{n}\right)^{n-j+1}\prod_{i=2}^{j-2}\frac{n-i}{i}$
$\displaystyle+\frac{n-q-m}{n}\sum_{i=0}^{n-j}\binom{n-1}{i}\left(\frac{(n-1)q-m}{n}\right)^{i}.$

Then $f(j)\geq f(j+1)$.

###### Proof.

The coefficient in front of $\left(\frac{(n-1)q-m}{n}\right)^{n-j}$ in $f(j)$
is
$\left(\frac{(n-m-1)((n-1)q-m)}{n}+\frac{(n-q-m)(n-1)(n-j)}{nj}\right)\prod_{i=2}^{j-2}\frac{n-i}{i}$.
Because $m\leq\frac{n}{2}$, it holds that
$n-m-1\geq\frac{n-2}{2}\geq\frac{n-j}{j}$, so the coefficient in front of
$\left(\frac{(n-1)q-m}{n}\right)^{n-j}$ in $f(j)$ is greater or equal to
$\left(\frac{(n-1)q-m}{n}+\frac{(n-q-m)(n-1)}{n}\right)\prod_{i=2}^{j-1}\frac{n-i}{i}$.
We now compute the sum

$\frac{(n-1)q-m}{n}+\frac{(n-q-m)(n-1)}{n}=n-m-1,$

and see that the statement follows. ∎

######  Proposition 18.

Let $C$ be the largest $q$-ary non-overlapping code of length $n$ obtained by
Construction 4 with $k=n-1$. Then the value of the parameter $l$ equals:

$\displaystyle l=\begin{cases}\frac{(n-1)q}{n}&\text{if $n$ divides $q$}\\\
\left\lceil{\frac{(n-1)q}{n}}\right\rceil&\text{if }(n-1)q\mod{n}=n-1\\\
\left\lfloor{\frac{(n-1)q}{n}}\right\rfloor&\text{if
}(n-1)q\mod{n}\leq\frac{n}{2}.\end{cases}$

######  Remark 2.

Note that we skip the case $\frac{n}{2}<(n-1)q\mod{n}<n-1$, as we do not need
it throughout our paper. Although one would wish that in that case
$l=\left\lceil{\frac{(n-1)q}{n}}\right\rceil$, this does not always hold. If
we take for example $n=11$ and $q=16$, then the code with parameter $l=14$
contains 576 650 390 625 codewords, but the code with parameter $l=15$
contains 578 509 309 952 codewords.

###### Proof.

The largest $q$-ary non-overlapping code of length $n$ obtained by
Construction 4 with $k=n-1$ has size $\max_{l\in\\{1,\dots,q-1\\}}f(l),$ where
$f(l)=(q-l)l^{n-1}$. First we observe the first derivative of $f$,
$f^{\prime}(l)=l^{n-2}((n-1)q-nl)$ and notice that $f(l)$ is strictly
increasing on the interval $\left[1,\frac{(n-1)q}{n}\right)$ and strictly
decreasing on the interval $\left(\frac{(n-1)q}{n},q-1\right]$. If $n$ divides
$q$, the maximum $\max_{l\in\\{1,\dots,q-1\\}}f(l)$ is achieved at
$l=\frac{(n-1)q}{n}$.

Now, let us suppose $q$ is not a multiplier of $n$. The maximum
$\max_{l\in\\{1,\dots,q-1\\}}f(l)$ is achieved either at
$l=\left\lfloor{\frac{(n-1)q}{n}}\right\rfloor$ or
$l=\left\lceil{\frac{(n-1)q}{n}}\right\rceil=\left\lfloor{\frac{(n-1)q}{n}}\right\rfloor+1$.
We denote the values of $f$ in these two points with
$F=f\left(\left\lfloor{\frac{(n-1)q}{n}}\right\rfloor\right)$ and
$C=f\left(\left\lceil{\frac{(n-1)q}{n}}\right\rceil\right)=f\left(\left\lfloor{\frac{(n-1)q}{n}}\right\rfloor+1\right)$.
Using the binomial theorem we obtain

$\displaystyle
F-C=\sum_{i=0}^{n-1}\binom{n-1}{i}\left\lfloor{\frac{(n-1)q}{n}}\right\rfloor^{i}-\left(q-\left\lfloor{\frac{(n-1)q}{n}}\right\rfloor\right)\sum_{i=0}^{n-2}\binom{n-1}{i}\left\lfloor{\frac{(n-1)q}{n}}\right\rfloor^{i}.$

Now let us introduce $m$, such that $(n-1)q\equiv m\pmod{n}$, to rewrite the
difference

$\displaystyle F-C=$
$\displaystyle\left(\frac{(n-1)q-m}{n}\right)^{n-1}+\frac{n-q-m}{n}\sum_{i=0}^{n-2}\binom{n-1}{i}\left(\frac{(n-1)q-m}{n}\right)^{i}$
$\displaystyle=$
$\displaystyle(n-k-1)\left(\frac{(n-1)q-m}{n}\right)^{n-2}+\frac{n-q-m}{n}\sum_{i=0}^{n-3}\binom{n-1}{i}\left(\frac{(n-1)q-m}{n}\right)^{i}.$

First let us explain that the coefficient $\frac{n-q-m}{n}$ is non-positive.
Suppose for contradiction that $q<n-m$. Then
$\frac{(n-1)q}{n}<n-m+1+\frac{m}{n}$. Since $(n-1)q\equiv m\pmod{n}$, it
follows $\frac{(n-1)q}{n}\leq n-m+1+\frac{m}{n}-n=\frac{m}{n}-m-1<0$ but
$\frac{(n-1)q}{n}<0$ cannot hold for $n>1$ and $q>1$. We also see that
$\frac{n-q-m}{n}=0$ if and only if
$\left\lceil{\frac{(n-1)q}{n}}\right\rceil=q$. In this case, $F-C>0$ and
therefore $\max_{i\in\\{1,\dots,q-1\\}}f(i)=F$. We immediately see that for
$m=n-1$, $F<C$ since $q>1$ always holds. To get a lower bound on $F-C$ when
$m\leq\frac{n}{2}$ we apply lemma 17 for $j=3,\dots,n$ consecutively. We
obtain $F-C\geq(n-m-1)\prod_{i=2}^{n-1}\frac{n-i}{i}>0$. ∎

Now we can compute the sizes of maximum four-letter non-overlapping codes. The
proof of Theorem 19 reveals that they can indeed be generated using
Construction 4.

######  Theorem 19.

$S(q,4)=\left[{\frac{3q}{4}}\right]^{3}\left(q-\left[{\frac{3q}{4}}\right]\right),$

where $\left[x\right]$ is the rounding of $x$ to the closest natural number
that rounds half down.

###### Proof.

Let $C$ be a maximum code that satisfies property (1). Without loss of
generality we can assume $\lvert R_{1}\rvert\geq\lvert L_{1}\rvert$ (otherwise
we can switch L’s and R’s and obtain a code of the same size), meaning that
$R_{3}=\emptyset$ and $\lvert L_{3}\rvert=\lvert L_{1}\rvert\lvert
R_{2}\rvert+\lvert L_{2}\rvert\lvert R_{1}\rvert$. We also know that $\lvert
R_{2}\rvert=\lvert L_{1}\rvert\lvert R_{1}\rvert-\lvert L_{2}\rvert$, so the
size of $C$ equals

$\displaystyle\lvert C\rvert=$ $\displaystyle\lvert L_{1}\rvert\lvert
R_{3}\rvert+\lvert L_{2}\rvert\lvert R_{2}\rvert+\lvert L_{3}\rvert\lvert
R_{1}\rvert$ $\displaystyle=$ $\displaystyle\lvert L_{2}\rvert\lvert
R_{2}\rvert+\lvert L_{1}\rvert\lvert R_{2}\rvert\lvert R_{1}\rvert+\lvert
L_{2}\rvert\lvert R_{1}\rvert^{2}$ $\displaystyle=$ $\displaystyle-\lvert
L_{2}\rvert^{2}+\lvert L_{2}\rvert\lvert R_{1}\rvert^{2}+\lvert
L_{1}\rvert^{2}\lvert R_{1}\rvert^{2}.$

Using the derivative test, we know that for fixed sets $L_{1}$ and $R_{1}$
with $\lvert R_{1}\rvert\leq 2\lvert L_{1}\rvert$ the above function achieves
its maximum when $\lvert L_{2}\rvert=\frac{\lvert R_{1}\rvert^{2}}{2}$. A
feasible partition $(L_{1},R_{1})$ with $\lvert R_{1}\rvert\leq 2\lvert
L_{1}\rvert$ exists for every $q\geq 2$ (take $\lvert
R_{1}\rvert=\lceil\frac{q}{2}\rceil$), so $\lvert C\rvert\leq\frac{\lvert
R_{1}\rvert^{4}}{4}+\lvert R_{1}\rvert^{2}\lvert L_{1}\rvert^{2}\leq 8\lvert
L_{1}\rvert^{4}\leq\frac{8q^{4}}{3^{4}}$. If $\lvert R_{1}\rvert>2\lvert
L_{1}\rvert$, the maximum code size is achieved when $\lvert
L_{2}\rvert=\lvert L_{1}\rvert\lvert R_{1}\rvert$. Then $C$ is constructed
using Construction 4 with $k=3$. A feasible partition $(L_{1},R_{1})$ with
$\lvert R_{1}\rvert>2\lvert L_{1}\rvert$ exists for every $q>3$ (take $\lvert
L_{1}\rvert=1$).

If $q=2$ then all feasible partitions $(L_{1},R_{1})$ satisfy $\lvert
L_{1}\rvert=\lvert R_{1}\rvert=1$. Therefore $\lvert L_{2}\rvert\in\\{0,1\\}$
and $\lvert L_{2}\rvert^{2}=\lvert L_{2}\rvert$, so

$\displaystyle S(2,4)$ $\displaystyle=-\lvert L_{2}\rvert^{2}+\lvert
L_{2}\rvert+1=1$ $\displaystyle=1^{3}\left(2-1\right)$
$\displaystyle=\left[\frac{3\cdot 2}{4}\right]^{3}\left(2-\left[\frac{3\cdot
2}{4}\right]\right).$

If $q=3$ then for all feasible partitions $(L_{1},R_{1})$ such that $\lvert
R_{1}\rvert\geq\lvert L_{1}\rvert$, $\lvert L_{1}\rvert=1$ and $\lvert
R_{1}\rvert=2$ holds. Therefore $\lvert R_{1}\rvert=2\lvert L_{1}\rvert$. A
feasible partition $L_{2}=\left(L_{1}R_{1}\right)$ with $\lvert
L_{2}\rvert=\frac{\lvert R_{1}\rvert^{2}}{2}$ exists, so

$\displaystyle S(3,4)$ $\displaystyle=8\lvert L_{1}\rvert=8$
$\displaystyle=2^{3}\left(3-2\right)$ $\displaystyle=\left[\frac{3\cdot
3}{4}\right]^{3}\left(3-\left[\frac{3\cdot 3}{4}\right]\right).$

We are left to prove that
$\frac{8q^{4}}{3^{4}}\leq\max_{i\in\\{1,\dots,q-1\\}}(q-i)i^{3}$ for $q\geq
4$. We use Proposition 18 to divide the problem into four subproblems.
(i) If $4\mid q$, we already know that Blackburn’s construction yields the
optimum. Still we can check that $\frac{8q^{4}}{3^{4}}<\frac{27q^{4}}{4^{4}}$
or equivalently $2^{11}=2048<2187=3^{7}$.
(ii) If $3q\equiv 1\pmod{4}$, we have to check that
$\frac{\left(q+1\right)\left(3q-1\right)^{3}}{4^{4}}>\frac{8q^{4}}{3^{4}}$ or
equivalently
$\frac{139}{2048}q^{4}+\frac{81}{2048}\left(-18q^{2}+8q-1\right)>0$. The two
real roots of this polynomial are $q\approx-3.4482$ and $q=3$. A strong
inequality therefore holds for $q\geq 4$.
(iii) If $3q\equiv 2\pmod{4}$, we have to check that
$\frac{\left(q+2\right)\left(3q-2\right)^{3}}{4^{4}}>\frac{8q^{4}}{3^{4}}$ or
equivalently
$\frac{139}{2048}q^{4}+\frac{81}{2048}\left(-18q^{2}+32q-4\right)>0$. The two
real roots of this polynomial are $q\approx-3.9235$ and $q\approx 0.13528$, so
the inequality holds.
(iv) If $3q\equiv 3\pmod{4}$,
$\frac{\left(q-1\right)\left(3q+1\right)^{3}}{4^{4}}>\frac{8q^{4}}{3^{4}}$ or
equivalently
$\frac{139}{2048}q^{4}-\frac{81}{2048}\left(18q^{2}+8q+1\right)>0$. The two
real roots of this polynomial are $q=-3$ and $q\approx 3.4482$, so the
inequality holds for $q\geq 4$. ∎

######  Theorem 20.

$N(q,4)=\begin{cases}2\binom{q}{\left[{\frac{3q}{4}}\right]}&q\geq 3\\\
6&q=2.\end{cases}$

###### Proof.

The proof of the Theorem 19 showed that for $q\geq 3$ all maximum non-
overlapping codes with $\lvert R_{1}\rvert\geq\lvert L_{1}\rvert$ are given by
partitions $\left(L_{1},R_{1}\right)$ with $\lvert
L_{1}\rvert=\left[\frac{3q}{4}\right]$. There are
$\binom{q}{\left[{\frac{3q}{4}}\right]}$ such partitions. Since $\lvert
R_{1}\rvert>\lvert L_{1}\rvert$, all maximum non-overlapping codes satisfy
Property 1. For each partition $(L_{1},R_{1})$ partitions
$(L_{2},R_{2}),(L_{3},R_{3})$ are uniquely determined. From Proposition 12 we
know that there are also $\binom{q}{\left[{\frac{3q}{4}}\right]}$ maximum non-
overlapping codes with $\lvert R_{1}\rvert<\lvert L_{1}\rvert$.

If $q=2$ then every four-letter non-overlapping code is maximum as we know
from Theorem 19 that $S(2,4)=1$. Hence $\lvert L_{1}\rvert=\lvert
R_{1}\rvert=1$ and $\lvert L_{i}\rvert+\lvert R_{i}\rvert=1$ for
$i\in\\{2,3\\}$. Although there are 8 choices for the selection of partitions,
we obtain only 6 distinct codes $\\{0111\\}$, $\\{0001\\}$, $\\{0011\\}$,
$\\{1000\\}$, $\\{1110\\}$, and $\\{1100\\}$. Each of the codes $\\{0011\\}$
and $\\{1100\\}$ is given by two collections of partitions. ∎

Unfortunately Construction 4 fails to generate a maximum five-letter non-
overlapping code, as we will see later.

##  6 Comparison to other constructions

At the moment we are not able to provide any simple formula to compute the
size of a maximum non-overlapping code with a larger codeword length. However,
we solved SQN for $5\leq n\leq 30$ when $q=2$, and $5\leq n\leq 16$ when
$3\leq q\leq 6$ using a search algorithm that incorporates the observations
from previous sections (see Appendix A). For each pair of parameter values $q$
and $n$, a single optimal solution of SQN was found up to the transformations
of Propositions 12, 13 and Corollary 4. We computed the full set of optimal
solutions of SQN by applying those propositions, and $N(q,n)$ from Proposition
11. The results are presented in Tables 1 and 2.

We checked that for $q=2,n\leq 16$ the computed values of $S(q,n)$ agree with
the values obtained by Chee et al [6], and for $n>16$ the determined values
are not smaller than the largest code obtained by Constructions 1 and 2. For
$16<n\leq 30$ the gap between $S(q,n)$ and the size of the largest code given
by these two constructions is given in Table 2. Note that for this set of
parameters Construction 1 always yields larger codes than Construction 2 [6].

Table 1: $S(q,n)$ and $N(q,n)$ for $2\leq q\leq 6$ and $3\leq n\leq 16$.

|  | $q$
---|---|---
$n$ |  |  2 |  3 |  4 |  5 |  6
3 |  $S(q,n)$ |  1 |  4 |  9 |  18 |  32
|  $N(q,n)$ |  4 |  6 |  8 |  20 |  30
4 |  $S(q,n)$ |  1 |  8 |  27 |  64 |  128
|  $N(q,n)$ |  6 |  6 |  8 |  10 |  30
5 |  $S(q,n)$ |  2 |  17 |  81 |  256 |  625
|  $N(q,n)$ |  8 |  12 |  8 |  10 |  12
6 |  $S(q,n)$ |  3 |  41 |  251 |  1024 |  3125
|  $N(q,n)$ |  16 |  12 |  24 |  10 |  12
7 |  $S(q,n)$ |  5 |  99 |  829 |  4181 |  15625
|  $N(q,n)$ |  48 |  12 |  24 |  40 |  12
8 |  $S(q,n)$ |  8 |  247 |  2753 |  17711 |  79244
|  $N(q,n)$ |  288 |  36 |  24 |  40 |  60
9 |  $S(q,n)$ |  14 |  656 |  9805 |  76816 |  411481
|  $N(q,n)$ |  1132 |  6 |  24 |  60 |  60
10 |  $S(q,n)$ |  24 |  1792 |  34921 |  341792 |  2188243
|  $N(q,n)$ |  $2^{15}$ |  6 |  24 |  60 |  120
11 |  $S(q,n)$ |  44 |  4896 |  124373 |  1520800 |  11755857
|  $N(q,n)$ |  $2^{26}$ |  6 |  24 |  60 |  120
12 |  $S(q,n)$ |  81 |  13376 |  446496 |  6817031 |  63281718
|  $N(q,n)$ |  $2^{46}$ |  6 |  120 |  360 |  2040
13 |  $S(q,n)$ |  149 |  36544 |  1619604 |  31438129 |  350255809
|  $N(q,n)$ |  $2^{83}$ |  6 |  120 |  40 |  120
14 |  $S(q,n)$ |  274 |  99840 |  5941181 |  146053729 |  19404900978
|  $N(q,n)$ |  $2^{151}$ |  6 |  240 |  40 |  120
15 |  $S(q,n)$ |  504 |  274384 |  21917583 |  678529303 |  * $\geq 10755272317$
|  $N(q,n)$ |  $2^{276}$ |  24 |  240 |  40 |  *
16 |  $S(q,n)$ |  927 |  759847 |  82990089 |  * $\geq 3152278399$ |  * $\geq 59811113295$
|  $N(q,n)$ |  $2^{506}$ |  24 |  8 |  * |  *

  * *

The (exact) value was not determined due to the long expected runtime of the
algorithm.

Table 2: $S(2,n)$ and $N(2,n)$ for $17\leq n\leq 30$. The last column equals
the difference between $S(2,n)$ and the largest non-overlapping code given by
Construction 1.

$n$ |  $S(2,n)$ |  $N(2,n)$ |  gap
---|---|---|---
17 |  1705 |  $2^{930}$ |  0
18 |  3160 |  $2^{1677}$ |  24
19 |  5969 |  $2^{3163}$ |  201
20 |  11272 |  $2^{5974}$ |  601
21 |  21287 |  $2^{11277}$ |  718
22 |  40202 |  $2^{21292}$ |  554
23 |  76424 |  $2^{39653}$ |  0
24 |  147312 |  $2^{76429}$ |  0
25 |  283953 |  $2^{147317}$ |  0
26 |  547337 |  $2^{283958}$ |  0
27 |  1055026 |  $2^{547342}$ |  0
28 |  2033628 |  $2^{1055031}$ |  0
29 |  3919944 |  $2^{2033633}$ |  0
30 |  *$\geq$ 7555935 |  * |  $\geq$ 0

  * *

The (exact) value was not determined due to the long expected runtime of the
algorithm.

For $3\leq q\leq 6$ and $5\leq n\leq 16$, we compared our values with the
optimal values of Construction 1, Wang and Wang’s [14] modification of
Construction 4, Wang and Wang’s [14] generalization of Construction 2, and
Construction 5 that have been included as a supplement to [14]. The gap
between the optimal values of these constructions and the newly determined
values of $S(q,n)$ are given in Table 3. Our implementation of the algorithm
always returned a value for $S(q,n)$ that is larger or equal to the size of
the largest code given by any of those constructions. Whenever we got a
strictly better solution for some $q$ and $n$, we also checked that none of
the maximum codes can be obtained using Construction 4. This can be done by
observing the set of optimal solutions of SQN and Proposition 21.

######  Proposition 21.

Let $C=\bigcup_{i=1}^{n-1}\left(L_{i}R_{n-i}\right)$ be a maximum non-
overlapping code given by Construction 4 for some value of $k$. If
$R_{k+1}=\emptyset$, then $S=I^{k}=L_{1}^{k}$ and $C$ can be obtained by Wang
and Wang’s modification.

###### Proof.

Since $S\subseteq I^{k}$, $L_{2}=\cdots=L_{k}=\emptyset$ and
$L_{k+1}=\bigcup_{i=1}^{k}\left(L_{i}R_{k+1-i}\right)=\left(L_{1}R_{k}\right)$.
Similarly, $R_{k}=\left(L_{1}^{k-1}R_{1}\right)$, so
$L_{k+1}=\left(L_{1}^{k}R_{1}\right)$ and $S=L_{1}^{k}$. ∎

Table 3: Gap between $S(q,n)$ and the largest non-overlapping codes given by Construction 1 (C1), Wang and Wang’s generalization of Construction 2 (W2), Wang and Wang’s modification of Construction 4 (W4), and Construction 5 (C5). For each parameter value $3\leq q\leq 6$ and $5\leq n\leq 16$ the first column states the gap between the code sizes, and the second column provides the list of constructions that yield the largest code. | $q$
---|---
| 3 |  | 4 |  | 5 |  | 6
$n$ |  gap |  constructions |  |  gap |  constructions |  |  gap |  constructions |  |  gap |  constructions
5 |  1 |  C1,W2,W4,C5 |  |  0 |  C1,W4 |  |  0 |  C1,W4 |  |  0 |  C1,W4
6 |  5 |  C5 |  |  8 |  C1,W4 |  |  0 |  C1,W4 |  |  0 |  C1,W4
7 |  11 |  C1,W4 |  |  100 |  C1,W4 |  |  85 |  C1,W4 |  |  0 |  C1,W4
8 |  7 |  C1,W4 |  |  419 |  C5 |  |  1327 |  C1,W4 |  |  1119 |  C1,W4
9 |  0 |  C1,W4 |  |  1937 |  C5 |  |  11280 |  C1,W4 |  |  20856 |  C1,W4
10 |  0 |  C1,W4 |  |  6976 |  C1,W4 |  |  62826 |  W4 |  |  235118 |  C1,W4
11 |  0 |  C1,W4 |  |  18425 |  C1,W4 |  |  300940 |  W4 |  |  172849 |  W4
12 |  0 |  C1,W4 |  |  44817 |  C1,W4 |  |  1483667 |  W4 |  |  8493622 |  W4
13 |  0 |  C1,W4 |  |  96723 |  C1,W4 |  |  7922993 |  C1,W4 |  |  50887361 |  W4
14 |  0 |  C1, W4 |  |  167501 |  C1, W4 |  |  32512609 |  C1, W4 |  |  305122418 |  W4
15 |  1616 |  C1, W4 |  |  27900 |  C1, W4 |  |  130304279 |  C1, W4 |  |  $\geq$ 1817210513 |  W4
16 |  14631 |  C1, W4 |  |  0 |  C1, W4 |  |  $\geq$ 505213823 |  C1, W4 |  |  $\geq$ 10972637519 |  W4

In spite of the reduction of the optimization problem, finding all solutions
to SQN still requires years of CPU time for some parameter values. We
therefore analysed the sets of optimal solutions to find some common
properties. The results lead to the following conjecture.

######  Conjecture 1.

For every $q\geq 2$ and $n\geq 3$ there exists a maximum non-overlapping code
$C=\bigcup_{i<n}\left(L_{i}R_{n-i}\right)\in\mathcal{M}_{q,n}$ that satisfies
$R_{i}=\emptyset$ for every $i>\frac{n}{q+1}+1$.

######  Remark 3.

If Conjecture 1 holds, then Blackburn’s conjecture holds for $q\geq n$.

We reduced the set of feasible solutions accordingly to find a large non-
overlapping code for the parameter values, for which we could not solve the
original optimization problem. As shown in Table 3 for all three parameter
values a code was obtained that is much larger than the hitherto known ones.
In the binary case, $n=30$, a code with exactly the same size as the one given
by Construction 1 was found.

## Declarations

### Funding

The research was partially supported by the scientific-research program
P2-0359 and by the basic research project J1-50024, both financed by the
Slovenian Research and Innovation Agency, and by the infrastructure program
ELIXIR-SI RI-SI-2 financed by the European Regional Development Fund and by
the Ministry of Education, Science and Sport of Republic of Slovenia.

### Competing interests

The authors have no competing interests to declare that are relevant to the
content of this article.

### Availability of data and materials

The set of optimal solutions of SQN that were determined in this study is
available at: https://github.com/magdevska/nono-codes.

### Code availability

All code is available for download at: https://github.com/magdevska/nono-
codes.

## References

  * [1] Bajic, D., Stojanovic, J.: Distributed sequences and search process. In: 2004 IEEE International Conference on Communications (IEEE Cat. No. 04CH37577), vol. 1, pp. 514–518 (2004).
  * [2] Bajic, D., Loncar-Turukalo, T.: A simple suboptimal construction of cross-bifix-free codes. Cryptography and Communications 6(1), 27–37 2014\.
  * [3] Barcucci, E., Bilotta, S., Pergola, E., Pinzani, R., Succi, J.: Cross-bifix-free sets generation via motzkin paths. RAIRO-Theoretical Informatics and Applications 50(1), 81–91 (2016).
  * [4] Bilotta, S., Pergola, E., Pinzani, R.: A new approach to cross-bifix-free sets. IEEE Transactions on Information Theory 58(6), 4058–4063 (2012).
  * [5] Blackburn, S.R.: Non-overlapping codes. IEEE Transactions on Information Theory 61(9), 4890–4894 (2015).
  * [6] Chee, Y.M., Kiah, H.M., Purkayastha, P., Wang, C.: Cross-bifix-free codes within a constant factor of optimality. IEEE Transactions on Information Theory 59(7), 4668–4674 (2013).
  * [7] Fimmel, E., Michel, C.J., Strüngmann, L.: Strong comma-free codes in genetic information. Bulletin of mathematical biology 79(8), 1796–1819 (2017).
  * [8] Fimmel, E., Michel, C.C., Pirot, F., Sereni, J.-S., Strüngmann, L.: Comma-free Codes Over Finite Alphabets. preprint (2019). https://hal.archives-ouvertes.fr/hal-02376793
  * [9] Fimmel, E., Michel, C.J., Pirot, F., Sereni, J.-S., Strüngmann, L.: Diletter and triletter comma-free codes over finite alphabets. Australasian Journal of Combinatorics 86(2), 233–270 (2023).
  * [10] Levenshtein, V.: Decoding automata, invariant with respect to the initial state. Problemy Kibernet 12(1), 125–136 (1964).
  * [11] Levenshtein, V.I.: Maximum number of words in codes without overlaps. Problemy Peredachi Informatsii 6(4), 88–90 (1970).
  * [12] Levy, M., Yaakobi, E.: Mutually uncorrelated codes for DNA storage. IEEE Transactions on Information Theory 65(6), 3671–3691 (2018).
  * [13] Robson, J.M.: Finding a maximum independent set in time O (2n/4). Technical report, Technical Report 1251-01, LaBRI, Université Bordeaux I (2001).
  * [14] Wang, G., Wang, Q.: Q-ary non-overlapping codes: a generating function approach. IEEE Transactions on Information Theory (2022).
  * [15] Yazdi, S.T., Kiah, H.M., Gabrys, R., Milenkovic, O.: Mutually uncorrelated primers for DNA-based data storage. IEEE Transactions on Information Theory 64(9), 6283–6296 (2018).

##  Appendix A The algorithm for SQN

Here we provide a pseudo-code of an algorithm that searches for a maximum non-
overlapping code. Procedure compute_size is due to Theorem 6. We obtain
procedures compute_conditions and compute_parameters from Definition 9.
Theorem 15 raises procedure determine_upper_half. Procedure branch_at_level
combines Construction 6, Propositions 12 and 13, and Theorem 15. The solutions
are compared with procedure update_maximum. Procedure solve_sqn initializes
the optimal solution and starts the branching algorithm.

In order to obtain the results in a reasonable amount of time, our
implementation uses multi-threading. A depth of parallelization $d$ is given
as parameter and should be selected depending on the available number of CPU
cores and $q$. We divide the branching stage into subproblems as follows. If
$i$ is smaller than $d$, then the branching procedure creates a new thread for
each feasible value of $x_{i}$. After the child threads are joined, the parent
thread selects the maximum values of its children $s^{*}$ and the
corresponding solution set $C^{*}$. If $i$ equals $d$, then the branching
stage runs sequentially.

Algorithm 1 Non-overlapping code size

1:$\\{x_{1},\dots,x_{i}\\}$, $\\{y_{1},\dots,y_{i}\\}$

2:procedure compute_size($i$)

3: $s\leftarrow 0$

4: for $j\leftarrow 1\dots i-1$ do

5: $s\leftarrow s+x_{j}y_{i-j}$

6: end for

7:end procedure

Algorithm 2 Computing the conditions $c_{i}$

1:$\\{x_{1},\dots,x_{n-i}\\}$, $\\{y_{1},\dots,y_{n-i}\\}$,
$\\{\delta_{i+1},\dots,\delta_{n-1}\\}$, $\\{p_{1},\dots,p_{n-1-i}\\}$,
$i>\frac{n}{2}$

2:procedure compute_conditions($i$)

3: $p_{i}\leftarrow$ compute_parameters($i$)

4: $c_{i}\leftarrow y_{n-i}-x_{n-i}$

5: for $j\leftarrow 1\dots n-1-i$ do

6: $v\leftarrow 0$

7: for $l\leftarrow 1\dots j$ do

8: $v\leftarrow v+p_{lj}(y_{l}-x_{l})$

9: end for

10: $c_{i}\leftarrow
c_{i}+\left(\delta_{i+j}y_{n-i-j}+(1-\delta_{i+j})x_{n-i-j}\right)v$

11: end for

12: if $c_{i}\geq 0$ then

13: $\delta_{i}\leftarrow 1$

14: else

15: $\delta_{i}\leftarrow 0$

16: end if

17:end procedure

18:

19:procedure compute_parameters($i$)

20: $p_{ii}\leftarrow 1$

21: for $j\leftarrow i-1\dots 1$ do

22: $p_{ij}\leftarrow 0$

23: for $k\leftarrow j\dots i-1$ do

24: $p_{ij}\leftarrow
p_{ij}+(\delta_{i+k}y_{i-k}+(1-\delta_{i+k})x_{i-k})p_{ik}$

25: end for

26: end for

27:end procedure

Algorithm 3 Determine $x_{i}$, $y_{i}$ for $i>\frac{n}{2}$

1:$n$, $\\{\delta_{\lfloor\frac{n}{2}\rfloor+1},\dots,\delta_{n-1}\\}$

2:procedure determine_upper_half

3: for $i\leftarrow\lfloor\frac{n}{2}\rfloor+1\dots n-1$ do

4: if $\delta_{i}=1$ then

5: $x_{i}\leftarrow$ compute_size(i)

6: $y_{i}\leftarrow 0$

7: else

8: $x_{i}\leftarrow 0$

9: $y_{i}\leftarrow$ compute_size(i)

10: end if

11: end for

12:end procedure

Algorithm 4 Branch

1:$n\geq 3$, $q\geq 2$, $\\{x_{1},\dots,x_{i-1}\\}$,
$\\{y_{1},\dots,y_{i-1}\\}$

2:procedure Branch_at_level($i$)

3: if $i=1$ then

4: for $x_{i}\leftarrow 1\dots\lfloor\frac{n}{2}\rfloor$ do

5: $y_{i}\leftarrow q-x_{i}$

6: compute_conditions($n-1$)

7: branch_at_level($i+1$)

8: end for

9: else if $i\leq\frac{n}{2}$ then

10: $s\leftarrow$ compute_size($i$)

11: if $x_{1}=y_{1},\dots,x_{i-1}=y_{i-1}$ then

12: max_size $\leftarrow\lfloor\frac{s}{2}\rfloor$

13: else

14: max_size $\leftarrow s$

15: end if

16: for $x_{i}\leftarrow 0\dots$ max_size do

17: $y_{i}\leftarrow s-x_{i}$

18: compute_conditions($n-i$)

19: branch_at_level($i+1$)

20: end for

21: else

22: determine_upper_half()

23: update_maximum()

24: end if

25:end procedure

Algorithm 5 Update current maximum if necessary

1:$S^{*},C^{*},n$

2:procedure update_maximum($x,y$)

3: $s\leftarrow$ compute_size($n$)

4: if $s=s^{*}$ then

5: $C^{*}\leftarrow C\cup(x,y)$

6: else if $s>s^{*}$ then

7: $C^{*}\leftarrow(x,y)$

8: $s^{*}\leftarrow s$

9: end if

10:end procedure

1:procedure solve_sqn($q,n$)

2: $s^{*}\leftarrow 0$

3: branch_at_level(1)

4:end procedure