11institutetext: Loughborough University, UK, 11email<EMAIL_ADDRESS>22institutetext: Kiel University, Germany 22email:
<EMAIL_ADDRESS>
#  $k$-Spectra of $c$-Balanced Words

Joel D. Day 11 Pamela Fleischmann 22 Florin Manea 22 Dirk Nowotka 22

###### Abstract

A word $u$ is a scattered factor of $w$ if $u$ can be obtained from $w$ by
deleting some of its letters. That is, there exist the (potentially empty)
words $u_{1},u_{2},...,u_{n}$, and $v_{0},v_{1},..,v_{n}$ such that
$u=u_{1}u_{2}...u_{n}$ and $w=v_{0}u_{1}v_{1}u_{2}v_{2}...u_{n}v_{n}$. We
consider the set of length-$k$ scattered factors of a given word w, called
here $k$-spectrum and denoted $\operatorname{ScatFact}_{k}(w)$. We prove a
series of properties of the sets $\operatorname{ScatFact}_{k}(w)$ for binary
strictly balanced and, respectively, $c$-balanced words $w$, i.e., words over
a two-letter alphabet where the number of occurrences of each letter is the
same, or, respectively, one letter has $c$-more occurrences than the other. In
particular, we consider the question which cardinalities
$n=|\operatorname{ScatFact}_{k}(w)|$ are obtainable, for a positive integer
$k$, when $w$ is either a strictly balanced binary word of length $2k$, or a
$c$-balanced binary word of length $2k-c$. We also consider the problem of
reconstructing words from their $k$-spectra.

##  1 Introduction

Given a word w, a scattered factor (also called scattered subword, or simply
subword in the literature) is a word obtained by removing one or more factors
from w. More formally, u is a scattered factor of w if there exist
$u_{1},\ldots,u_{n}\in\Sigma^{\ast}$, $v_{0},\ldots,v_{n}\in\Sigma^{\ast}$
such that $u=u_{1}u_{2}\ldots u_{n}$ and $w=v_{0}u_{1}v_{1}u_{1}\ldots
u_{n}v_{n}$. Consequently a scattered factor of w can be thought of as a
representation of w in which some parts are missing. As such, there is
considerable interest in the relationship of a word and its scattered factors
from both a theoretical and practical point of view. For an introduction to
the study of scattered factors, see Chapter 6 of [8]. On the one hand, it is
easy to imagine how, in any situation where discrete, linear data is read from
an imperfect input – such as when sequencing DNA or during the transmission of
a digital signal – scattered factors form a natural model, as multiple parts
of the input may be missed, but the rest will remain unaffected and in-
sequence. For instance, various applications and connections of this model in
verification are discussed in [13, 5] within a language theoretic framework,
while applications of the model in DNA sequencing are discussed in [3] in an
algorithmic framework. On the other hand, from a more algebraic perspective,
there have been efforts to bridge the gap between the non-commutative field of
combinatorics on words with traditional commutative mathematics via Parikh
matrices (cf. e.g., [10, 12]) which are closely related to, and influenced by
the topic of scattered factors.

The set (or also in some cases, multi-set) of scattered factors of a word $w$,
denoted $\operatorname{ScatFact}(w)$ is typically exponentially large in the
length of $w$, and contains a lot of redundant information in the sense that,
for $k^{\prime}<k\leq|w|$, a word of length $k^{\prime}$ is a scattered factor
of $w$ if and only if it is a scattered factor of a scattered factor of $w$ of
length $k$. This has led to the idea of $k$-spectra: the set of all length-$k$
scattered factors of a word. For example, the $3$-spectrum of the word
$\mathtt{a}\mathtt{b}\mathtt{a}\mathtt{b}\mathtt{b}\mathtt{b}$ is the set
$\\{\mathtt{a}\mathtt{a}\mathtt{b},\mathtt{a}\mathtt{b}\mathtt{a},\mathtt{a}\mathtt{b}\mathtt{b},\mathtt{b}\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{b}\mathtt{b}\\}$.
Note that unlike some literature, we do not consider the $k$-spectra to be the
multi-set of scattered factors in the present work, but rather ignore the
multiplicities. This distinction is non-trivial as there are significant
variations on the properties based on these different definitions (cf. e.g.,
[9]). Also, the notion of $k$-spectrum is closely related to the classical
notion of factor complexity of words, which counts, for each positive integer
$k$, the number of distinct factors of length $k$ of a word. Here, the
cardinality of the $k$-spectrum of a word gives the number of the word’s
distinct scattered factors of length $k$.

One of the most fundamental questions about $k$-spectra of words, and indeed
sets of scattered factors in general, is that of recognition: given a set $S$
of words (of length $k$), is $S$ the subset of a $k$-spectrum of some word. In
general, it remains a long standing goal of the theory to give a “nice”
descriptive characterisation of scattered factor sets (and $k$-spectra), and
to better understand their structure [8]. Another fundamental question
concerning $k$-spectra, and one well motivated in several applications, is the
question of reconstruction: given a word $w$ of length $n$, what is the
smallest value $k$ such that the $k$-spectrum of $w$ is uniquely determined?
This question was addressed and solved successively in a variety of cases. In
particular, in [2], the exact bound of $\frac{n}{2}+1$ is given in the general
case. Other variations, including for the definition of $k$-spectra where
multiplicities are also taken into account, are considered in [9], while [6]
considers the question of reconstructing words from their palindromic
scattered factors.

In the current work, we consider $k$-spectra in the restricted setting of a
binary alphabet $\Sigma=\\{\mathtt{a},\mathtt{b}\\}$. For such an alphabet, we
can always identify the natural number $c\in\mathbb{N}_{0}$ which describes
how balanced a word is: $c$ is the difference between the amount of
$\mathtt{a}$s and $\mathtt{b}$s. Thus, it seems natural to categorise all
words over $\Sigma$ according to this difference: a binary word where one
letter has exactly $c$ more occurrences than the other one is called
$c$-balanced. In Section 3 the cardinalities of $k$-spectra of $c$-balanced
words of length $2k-c$ are investigated. Our first results concern the minimal
and maximal cardinality $\operatorname{ScatFact}_{k}$ might have. We show that
the cardinality ranges for $0$-balanced (also called strictly balanced words)
between $k+1$ and $2^{k}$, and determine exactly for which words of length
$2k$ these values are reached. In the case of $c$-balanced words, we are able
to replicate the result regarding the minimal cardinality of
$\operatorname{ScatFact}_{k}$, but the case of maximal cardinality seems to be
more complicated. To this end, it seems that the words containing many
alternations between the two letters of the alphabet have larger sets
$\operatorname{ScatFact}_{k}$. Therefore, we first investigate the scattered
factors of the words which are prefixes of $(\mathtt{a}\mathtt{b})^{\omega}$
and give a precise description of all scattered factors of any length of such
words. That is, not only we compute the cardinality of
$\operatorname{ScatFact}_{k}(w)$, for all such words $w$, but also describe a
way to obtain directly the respective scattered factors, without repetitions.
We use this to describe exactly the sets $\operatorname{ScatFact}_{i}$ for the
word $(\mathtt{a}\mathtt{b})^{k-c}\mathtt{a}^{c}$, which seems a good
candidate for a $c$-balanced word with many distinct scattered factors.

Further, in Section 4, we explore more the cardinalities of
$\operatorname{ScatFact}_{k}(w)$ for strictly balanced words $w$ of length
$2k$. We obtain for these words that the smallest three numbers which are
possible cardinalities for their $k$-spectra are $k+1$, $2k$, and $3k-3$, thus
identifying two gaps in the set of such cardinalities. Among other results on
this topic, we show that for every constant $i$ there exist a word $w$ of
length $2k$ such that $|\operatorname{ScatFact}_{k}(w)|\in\Theta(n^{i})$; we
also show how such a word can be constructed.

Finally, in Section 5, we also approach the question of reconstructing
strictly balanced words from $k$-spectra in the specific case that the spectra
are also limited to strictly balanced words only. While we are not able to
resolve the question completely, we conjecture that the situation is similar
to the general case: the smallest value $k$ such that the $k$-spectrum of $w$
is uniquely determined is $k=\frac{|w|}{2}+1$ if $\frac{|w|}{2}$ is odd and
$k=\frac{|w|}{2}+2$, otherwise, in the case when $w$ contains at most two
blocks of $\mathtt{b}$s.

After introducing a series of basic definitions, preliminaries, and notations,
the organisation of the paper follows the description above.

##  2 Preliminaries

Let $\mathbb{N}$ be the set of natural numbers,
$\mathbb{N}_{0}=\mathbb{N}\cup\\{0\\}$, and let $\mathbb{N}_{\geq k}$ be all
natural numbers greater than or equal to $k$. Let $[n]$ denote the set
$\\{1,\ldots,n\\}$ and $[n]_{0}=[n]\cup\\{0\\}$ for an $n\in\mathbb{N}$.

We consider words $w$ over the alphabet $\Sigma=\\{\mathtt{a},\mathtt{b}\\}$.
$\Sigma^{*}$ denotes the set of all finite words over $\Sigma$, also called
binary words. $\Sigma^{\omega}$ the set of all infinite words over $\Sigma$,
also called binary infinite words. The empty word is denoted by $\varepsilon$
and $\Sigma^{+}$ is the free semigroup
$\Sigma^{*}\backslash\\{\varepsilon\\}$. The length of a word $w$ is denoted
by $|w|$. Let $\Sigma^{\leq k}:=\\{w\in\Sigma^{\ast}|\,|w|\leq k\\}$ and
$\Sigma^{k}$ be the set of all words of length exactly $k\in\mathbb{N}$. The
number of occurrences of a letter $\mathtt{a}\in\Sigma$ in a word
$w\in\Sigma^{\ast}$ is denoted by $|w|_{\mathtt{a}}$. The i${}^{\text{th}}$
letter of a word $w$ is given by $w[i]$ for $i\in[|w|]$. For a given word
$w\in\Sigma^{n}$ the reversal of $w$ is defined by $w^{R}=w[n]w[n-1]\dots
w[2]w[1]$. The powers of $w\in\Sigma^{\ast}$ are defined recursively by
$w^{0}=\varepsilon$, $w^{n}=ww^{n-1}$ for $n\in\mathbb{N}$.

A word $w\in\Sigma^{\ast}$ is called $c$-balanced if $||w|_{a}-|w|_{b}|=c$ for
$c\in\mathbb{N}_{0}$. $1$-balanced words are also called balanced and
$0$-balanced words are also called strictly balanced. Thus strictly balanced
words have the same number of $\mathtt{a}$s and $\mathtt{b}$s. Let
$\Sigma_{sb}^{\ast}$ be the set of all strictly balanced words over $\Sigma$.
For example, $\mathtt{a}\mathtt{b}\mathtt{a}\mathtt{a}$ is $2$-balanced,
$\mathtt{a}\mathtt{b}\mathtt{a}$ is balanced, while
$\mathtt{a}\mathtt{b}\mathtt{b}\mathtt{a}\mathtt{b}\mathtt{a}$ is strictly
balanced ($0$-balanced).

A word $u\in\Sigma^{\ast}$ is a _factor_ of $w\in\Sigma^{\ast}$, if $w=xuy$
holds for some words $x,y\in\Sigma^{\ast}$. Moreover, $u$ is a _prefix_ of $w$
if $x=\varepsilon$ holds and a _suffix_ if $y=\varepsilon$ holds. The factor
of $w$ from the i${}^{\text{th}}$ to the j${}^{\text{th}}$ letter will be
denoted by $w[i..j]$ for $0\leq i\leq j\leq|w|$. Given a letter
$\mathtt{a}\in\Sigma$ and a word $w\in\Sigma^{\ast}$, a _block_ of
$\mathtt{a}$ is a factor $u=w[i..j]$ with $u=\mathtt{a}^{j-i}$, such that
either $i=1$ or $w[i-1]=\mathtt{b}\neq\mathtt{a}$ and either $j=|w|$ or
$w[j+1]=\mathtt{b}\neq\mathtt{a}$. For example the word
$\mathtt{a}\mathtt{b}\mathtt{a}\mathtt{a}\mathtt{a}\mathtt{b}\mathtt{a}\mathtt{a}\mathtt{b}\mathtt{b}$
has 3 $\mathtt{a}$-blocks and 3 $\mathtt{b}$-blocks. Scattered factors and
$k$-spectra are defined as follows.

###### Definition 1

A word $u=a_{1}\dots a_{n}\in\Sigma^{n}$, for $n\in\mathbb{N}$, is a scattered
factor of a word $w\in\Sigma^{+}$ if there exists
$v_{0},\dots,v_{n}\in\Sigma^{\ast}$ with $w=v_{0}a_{1}v_{1}\dots
v_{n-1}a_{n}v_{n}$. Let $\operatorname{ScatFact}(w)$ denote the set of $w$’s
scattered factors and consider additionally $\operatorname{ScatFact}_{k}(w)$
and $\operatorname{ScatFact}_{\leq k}(w)$ as the two subsets of
$\operatorname{ScatFact}(w)$ which contain only the scattered factors of
length $k\in\mathbb{N}$ or the ones up to length $k\in\mathbb{N}$.

The sets $\operatorname{ScatFact}_{\leq k}(w)$ and
$\operatorname{ScatFact}_{k}(w)$ are also known as full $k$-spectrum and,
respectively, $k$-spectrum of a word $w\in\Sigma^{\ast}$ (see [1], [9], [11])
and moreover, scattered factors are often called subwords or scattered
subwords. Obviously the $k$-spectrum is empty for $k>|w|$ and contains exactly
$w$’s letters for $k=1$ and only $w$ for $k=|w|$. Considering the word
$w=\mathtt{a}\mathtt{b}\mathtt{b}\mathtt{a}$, the other spectra are given by
$\operatorname{ScatFact}_{2}(w)=\\{\mathtt{a}^{2},\mathtt{b}^{2},\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}$
and
$\operatorname{ScatFact}_{3}(w)=\\{\mathtt{a}\mathtt{b}^{2},\mathtt{a}\mathtt{b}\mathtt{a},\mathtt{b}^{2}\mathtt{a}\\}$.

It is worth noting that if $u$ is a scattered factor of $w$, and $v$ is a
scattered factor of $u$, then $v$ is a scattered factor of $w$. Additionaly,
notice two important symmetries regarding $k$-spectra. For $w\in\Sigma^{*}$
and the renaming morphism $\overline{\cdot}:\Sigma\rightarrow\Sigma$ with
$\overline{\mathtt{a}}=\mathtt{b}$ and $\overline{\mathtt{b}}=\mathtt{a}$ we
have $\operatorname{ScatFact}(w^{R})=\\{u^{R}\mid
u\in\operatorname{ScatFact}(w)\\}$ and
$\operatorname{ScatFact}(\overline{w})=\\{\overline{u}\mid
u\in\operatorname{ScatFact}(w)\\}$. Thus, from a structural point of view, it
is sufficient to consider only one representative from the equivalence classes
induced by the equivalence relation where $w_{1}$ is equivalent to $w_{2}$
whenever $w_{2}$ is obtained by a composition of reversals and renamings from
$w_{1}$. Considering w.l.o.g. the order $\mathtt{a}<\mathtt{b}$ on $\Sigma$,
we choose the lexicographically smallest word as representative from each
class. As such, we will mostly analyse the $k$-spectra of words starting with
$\mathtt{a}$. We shall make use of this fact extensively in Section 4.

##  3 Cardinalities of $k$-Spectra of $c$-Balanced Words

In the current section, we consider the combinatorial properties of
$k$-spectra of $c$-balanced, finite words. In particular, we are interested in
the cardinalities of the $k$-spectra and in the question: which cardinalities
are (not) possible? Since the $k$-spectra of $\mathtt{a}^{n}$ and
$\mathtt{b}^{n}$ are just $\mathtt{a}^{k}$ and $\mathtt{b}^{k}$ respectively
for all $n\in\mathbb{N}_{0}$ and $k\in[n]_{0}$, we assume
$|w|_{\mathtt{a}},|w|_{\mathtt{b}}>0$ for $w\in\Sigma^{\ast}$. It is a
straightforward observation that not every subset of $\Sigma^{k}$ is a
$k$-spectrum of some word $w$. For example, for $k=2$, $\mathtt{a}\mathtt{a}$
and $\mathtt{b}\mathtt{b}$ can only be scattered factors of a word containing
both $\mathtt{a}$s and $\mathtt{b}$s, and therefore having either
$\mathtt{a}\mathtt{b}$ or $\mathtt{b}\mathtt{a}$ as a scattered factor as
well. Thus, there is no word $w$ such that
$\operatorname{ScatFact}_{2}(w)=\\{\mathtt{a}\mathtt{a},\mathtt{b}\mathtt{b}\\}$.

In general, for any word containing only $\mathtt{a}$’s or only
$\mathtt{b}$’s, there will be exactly one scattered factor of each length,
while for words containing both $\mathtt{a}$’s and $\mathtt{b}$’s, the
smallest $k$-spectra are realised for words of the form
$w=\mathtt{a}^{n}\mathtt{b}$ (up to renaming and reversal), for which
$\operatorname{ScatFact}_{k}(w)=\\{\mathtt{a}^{k},\mathtt{a}^{k-1}\mathtt{b}\\}$
for each $k\in[|w|]$. On the other hand, as Proposition 5 shows, the maximal
$k$-spectra are those containing all words of length $k$ – and hence have size
$2^{k}$, achieved by e.g. $w=(\mathtt{a}\mathtt{b})^{n}$ for $n\geq k$. Note
that when strictly balanced words are considered, the same maximum applies,
since $(\mathtt{a}\mathtt{b})^{n}$ is strictly balanced, while the minimum
does not, since $\mathtt{a}^{n}\mathtt{b}$ is not strictly balanced.

It is straightforward to enumerate all possible k-spectra, and describe the
words realising them for $k\leq 2$, hence we shall generally consider only
$k$-spectra in the sequel for which $k\geq 3$. Our first result generalises
the previous observation about minimal-size $k$-spectra.

###### Theorem 3.2

For $k\in\mathbb{N}_{\geq 3}$, $c\in[k-1]_{0}$, $i\in[c]_{0}$, and a
$c$-balanced word $w\in\Sigma^{2k-c}$, we have
$|\operatorname{ScatFact}_{k-i}(w)|\geq k-c+1$, where equality holds if and
only if
$w\in\\{\mathtt{a}^{k}\mathtt{b}^{k-c},\mathtt{a}^{k-c}\mathtt{b}^{k},\mathtt{b}^{k}\mathtt{a}^{k-c},\mathtt{b}^{k-c}\mathtt{a}^{k}\\}.$
Moreover, if
$w\in\Sigma_{sb}^{2k}\backslash\\{\mathtt{a}^{k}\mathtt{b}^{k}\\}$, then
$|\operatorname{ScatFact}_{k}(w)|\geq k+3$.

###### Proof

Consider firstly only stricly balanced words, i.e. $c=0$ and w.l.o.g. only
$w=\mathtt{a}^{k}\mathtt{b}^{k}$. The cases $k=1$ and $k=2$ are the induction
basis.

The word $\mathtt{a}^{k}\mathtt{b}^{k}$ has obviously all
$\mathtt{a}^{r}\mathtt{b}^{s}$ for $r,s\in[k]_{0}$ as scattered factors, thus
$k+1$ many. This proves the $\Leftarrow$-direction.

Consider now a word
$w\in\Sigma_{sb}^{2k}\backslash\\{\mathtt{a}^{k}\mathtt{b}^{k},\mathtt{b}^{k}\mathtt{a}^{k}\\}$.
Since $w$ is not $\mathtt{a}^{k}\mathtt{b}^{k}$, $w$ contains a factor
$\mathtt{a}\mathtt{b}\mathtt{a}$ or $\mathtt{b}\mathtt{a}\mathtt{b}$. Assume
w.l.o.g. that $w=x\mathtt{a}\mathtt{b}\mathtt{a}y$ holds for
$x,y\in\Sigma^{\ast}$ with $|x|+|y|=2k-3$. By $w\in\Sigma_{sb}^{2k}$ follows
that $|x|_{\mathtt{b}}$ or $|y|_{\mathtt{b}}$ is not zero. Choose w.l.o.g.
$z_{1},z_{2}\in\Sigma^{\ast}$ with $y=z_{1}\mathtt{b}z_{2}$ which implies
$w=x\mathtt{a}\mathtt{b}\mathtt{a}z_{1}\mathtt{b}z_{2}$. Consequently
$|xz_{1}z_{2}|_{a}=|xz_{1}z_{2}|_{b}=k-2$ holds.
case 1: $xz_{1}z_{2}=\mathtt{a}^{k-2}\mathtt{b}^{k-2}$
By induction $|\operatorname{ScatFact}_{k-2}(xz_{1}z_{2})|=(k-2)+1=k-1$. Let
$u$ be a scattered factor of $xz_{1}z_{2}$ of length $k-2$. Then there exist
$u_{1},u_{2}$, and $u_{3}$ such that $u_{1}$ is a scattered factor of $x$,
$u_{2}$ of $z_{1}$, and $u_{3}$ of $z_{3}$ respectively. Consequently

$u_{1}\mathtt{a}\mathtt{a}u_{2}u_{3},\quad
u_{1}\mathtt{a}\mathtt{b}u_{2}u_{3},\quad\mbox{and}\quad
u_{1}\mathtt{b}\mathtt{a}u_{2}u_{3}$

are different elements of $\operatorname{ScatFact}_{k}(w)$. Each scattered
factor of $xz_{1}z_{2}$ is of the form $\mathtt{a}^{r}\mathtt{b}^{s}$ for
$r,s\in[k-2]_{0}$. We will know prove in which cases the aforementioned
scattered factors are different. Consider
$u=u_{1}u_{2}u_{3}=\mathtt{a}^{r}\mathtt{b}^{s}$ and
$u^{\prime}=u_{1}^{\prime}u_{2}^{\prime}u_{3}=\mathtt{a}^{r^{\prime}}\mathtt{b}^{s^{\prime}}$
to be different scattered factors of this form, i.e. $r\neq r^{\prime}$ and
$s\neq s^{\prime}$. Set

$\displaystyle\alpha_{1}$ $\displaystyle=u_{1}\mathtt{a}\mathtt{a}u_{2}u_{3},$
$\displaystyle\beta_{1}$
$\displaystyle=u_{1}^{\prime}\mathtt{a}\mathtt{a}u_{2}^{\prime}u_{3}^{\prime}$
$\displaystyle\alpha_{2}$ $\displaystyle=u_{1}\mathtt{b}\mathtt{a}u_{2}u_{3},$
$\displaystyle\beta_{2}$
$\displaystyle=u_{1}^{\prime}\mathtt{b}\mathtt{a}u_{2}^{\prime}u_{3}^{\prime}$
$\displaystyle\alpha 3$ $\displaystyle=u_{1}\mathtt{a}\mathtt{b}u_{2}u_{3},$
$\displaystyle\beta_{3}$ $\displaystyle=u_{1}\mathtt{a}\mathtt{b}u_{2}u_{3}.$

If $u_{1}=\mathtt{a}^{r_{1}}$, $u_{2}u_{3}=\mathtt{a}^{r_{2}}\mathtt{b}^{s}$
and $u_{1}^{\prime}=\mathtt{a}^{r_{1}^{\prime}}$,
$u_{2}^{\prime}u_{3}^{\prime}=\mathtt{a}^{r_{2}^{\prime}}\mathtt{b}^{s^{\prime}}$
with $r_{1}+r_{2}=r$ and $r_{1}^{\prime}+r_{2}^{\prime}=r^{\prime}$, we get
because of $r\neq r^{\prime}$, $r_{1}\neq-1$,

$\displaystyle\alpha_{1}=\mathtt{a}^{r+2}\mathtt{b}^{s}$
$\displaystyle\neq\mathtt{a}^{r^{\prime}+2}\mathtt{b}^{s}=\beta_{1},$
$\displaystyle\alpha_{1}=\mathtt{a}^{r+2}\mathtt{b}^{s}$
$\displaystyle\neq\mathtt{a}^{r_{1}^{\prime}}\mathtt{b}\mathtt{a}^{r_{2}^{\prime}+1}\mathtt{b}^{s^{\prime}}=\beta_{2}$
$\displaystyle\alpha_{2}=\mathtt{a}^{r_{1}}\mathtt{b}\mathtt{a}^{r_{2}+1}\mathtt{b}^{s}$
$\displaystyle\neq\mathtt{a}^{r_{1}^{\prime}}\mathtt{b}\mathtt{a}^{r_{2}^{\prime}+1}\mathtt{b}^{s^{\prime}}=\beta_{2}.$

If $u_{1}=\mathtt{a}^{r_{1}}$, $u_{2}u_{3}=\mathtt{a}^{r_{2}}\mathtt{b}^{s}$
and $u_{1}^{\prime}=\mathtt{a}^{r^{\prime}}\mathtt{b}^{s_{1}^{\prime}}$,
$u_{2}^{\prime}u_{3}^{\prime}=\mathtt{b}^{s_{2}^{\prime}}$ with
$r_{1}+r_{2}=r$, $s_{1}^{\prime}+s_{2}^{\prime}=s^{\prime}$, and
$s_{1}^{\prime}\neq 0$ (already in the previous case) we get because of
$s_{1}^{\prime}\neq 0$,

$\displaystyle\alpha_{1}=\mathtt{a}^{r+2}\mathtt{b}^{s}$
$\displaystyle\neq\mathtt{a}^{r^{\prime}}\mathtt{b}^{s_{1}^{\prime}}\mathtt{a}\mathtt{a}\mathtt{b}^{s_{2}^{\prime}}=\beta_{1},$
$\displaystyle\alpha_{1}=\mathtt{a}^{r+2}\mathtt{b}^{s}$
$\displaystyle\neq\mathtt{a}^{r^{\prime}}\mathtt{b}^{s_{1}^{\prime}}\mathtt{b}\mathtt{a}\mathtt{b}^{s_{2}^{\prime}}=\beta_{2}$
$\displaystyle\alpha_{2}=\mathtt{a}^{r_{1}}\mathtt{b}\mathtt{a}^{r_{2}+1}\mathtt{b}^{s}$
$\displaystyle\neq\mathtt{a}^{r^{\prime}}\mathtt{b}^{s_{1}^{\prime}}\mathtt{b}\mathtt{a}\mathtt{b}^{s_{2}^{\prime}}=\beta_{2}.$

If $u_{1}=\mathtt{a}^{r}\mathtt{b}^{s_{1}}$, $u_{2}u_{3}=\mathtt{b}^{s_{2}}$
and $u_{1}^{\prime}=\mathtt{a}^{r^{\prime}}\mathtt{b}^{s_{1}^{\prime}}$,
$u_{2}^{\prime}u_{3}^{\prime}=\mathtt{b}^{s_{2}^{\prime}}$ with
$r_{1}+r_{2}=r$, $s_{1}^{\prime}+s_{2}^{\prime}=s^{\prime}$, and
$s_{1},s_{1}^{\prime}\neq 0$ (already in the previous case) we get because of
$r^{\prime}\neq r$ and $s_{1},s_{1}^{\prime}\neq 0$,

$\displaystyle\alpha_{1}=\mathtt{a}^{r}\mathtt{b}^{s_{1}}\mathtt{a}\mathtt{a}\mathtt{b}^{s_{2}}$
$\displaystyle\neq\mathtt{a}^{r^{\prime}}\mathtt{b}^{s_{1}^{\prime}}\mathtt{a}\mathtt{a}\mathtt{b}^{s_{2}^{\prime}}=\beta_{1},$
$\displaystyle\alpha_{1}=\mathtt{a}^{r}\mathtt{b}^{s_{1}}\mathtt{a}\mathtt{a}\mathtt{b}^{s_{2}}$
$\displaystyle\neq\mathtt{a}^{r^{\prime}}\mathtt{b}^{s_{1}^{\prime}}\mathtt{b}\mathtt{a}\mathtt{b}^{s_{2}^{\prime}}=\beta_{2}$
$\displaystyle\alpha_{2}=\mathtt{a}^{r}\mathtt{b}^{s_{1}}\mathtt{b}\mathtt{a}\mathtt{b}^{s_{2}}$
$\displaystyle\neq\mathtt{a}^{r^{\prime}}\mathtt{b}^{s_{1}^{\prime}}\mathtt{b}\mathtt{a}\mathtt{b}^{s_{2}^{\prime}}=\beta_{2}.$

Consequently $\alpha_{1}$ and $\alpha_{2}$ are all different and we get
$2(k-1)$ many different scattered factors. Assume now additionally
$|r-r^{\prime}|=3$. If $u_{1}=\mathtt{a}^{r_{1}}$,
$u_{2}u_{3}=\mathtt{a}^{r_{2}}\mathtt{b}^{s}$ and
$u_{1}^{\prime}=\mathtt{a}^{r_{1}^{\prime}}$,
$u_{2}^{\prime}u_{3}^{\prime}=\mathtt{a}^{r_{2}^{\prime}}\mathtt{b}^{s^{\prime}}$
with $r_{1}+r_{2}=r$ and $r_{1}^{\prime}+r_{2}^{\prime}=r^{\prime}$, we get
because of $s_{1}^{\prime}\neq 0$, $r^{\prime}\neq r$, $r^{\prime}\neq r+1$

$\displaystyle\alpha_{1}=\mathtt{a}^{r+2}\mathtt{b}^{s}$
$\displaystyle\neq=\mathtt{a}^{r_{1}^{\prime}}\mathtt{a}\mathtt{b}\mathtt{a}^{r_{2}^{\prime}}\mathtt{b}^{s^{\prime}}=\beta_{3},$
$\displaystyle\alpha_{2}=\mathtt{a}^{r_{1}}\mathtt{b}\mathtt{a}^{r_{2}+1}\mathtt{b}^{s}$
$\displaystyle\neq\mathtt{a}^{r_{1}^{\prime}}\mathtt{a}\mathtt{b}\mathtt{a}^{r_{2}^{\prime}}\mathtt{b}^{s^{\prime}}=\beta_{3},$
$\displaystyle\alpha_{3}=\mathtt{a}^{r_{1}}\mathtt{a}\mathtt{b}\mathtt{a}^{r_{2}}\mathtt{b}^{s}$
$\displaystyle\neq\mathtt{a}^{r_{1}^{\prime}}\mathtt{a}\mathtt{b}\mathtt{a}^{r_{2}^{\prime}}\mathtt{b}^{s^{\prime}}=\beta_{3},$

If $u_{1}=\mathtt{a}^{r_{1}}$, $u_{2}u_{3}=\mathtt{a}^{r_{2}}\mathtt{b}^{s}$
and $u_{1}^{\prime}=\mathtt{a}^{r^{\prime}}\mathtt{b}^{s_{1}^{\prime}}$,
$u_{2}^{\prime}u_{3}^{\prime}=\mathtt{b}^{s_{2}^{\prime}}$ with
$r_{1}+r_{2}=r$, $s_{1}^{\prime}+s_{2}^{\prime}=s^{\prime}$, and
$s_{1}^{\prime}\neq 0$ (already in the previous case) we get because of
$s_{1}^{\prime}\neq 0$, $r^{\prime}\neq r+2$,

$\displaystyle\alpha_{1}=\mathtt{a}^{r+2}\mathtt{b}^{s}$
$\displaystyle\neq\mathtt{a}^{r^{\prime}}\mathtt{b}^{s_{1}^{\prime}}\mathtt{a}\mathtt{b}\mathtt{b}^{s_{2}^{\prime}}=\beta_{3},$
$\displaystyle\alpha_{2}=\mathtt{a}^{r_{1}}\mathtt{b}\mathtt{a}^{r_{2}+1}\mathtt{b}^{s}$
$\displaystyle\neq\mathtt{a}^{r^{\prime}}\mathtt{b}^{s_{1}^{\prime}}\mathtt{a}\mathtt{b}\mathtt{b}^{s_{2}^{\prime}}=\beta_{3}$
$\displaystyle\alpha_{3}=\mathtt{a}^{r_{1}}\mathtt{a}\mathtt{b}\mathtt{a}^{r_{2}}\mathtt{b}^{s}$
$\displaystyle\neq\mathtt{a}^{r^{\prime}}\mathtt{b}^{s_{1}^{\prime}}\mathtt{a}\mathtt{b}\mathtt{b}^{s_{2}^{\prime}}=\beta_{3}.$

If $u_{1}=\mathtt{a}^{r}\mathtt{b}^{s_{1}}$, $u_{2}u_{3}=\mathtt{b}^{s_{2}}$
and $u_{1}^{\prime}=\mathtt{a}^{r^{\prime}}\mathtt{b}^{s_{1}^{\prime}}$,
$u_{2}^{\prime}u_{3}^{\prime}=\mathtt{b}^{s_{2}^{\prime}}$ with
$r_{1}+r_{2}=r$, $s_{1}^{\prime}+s_{2}^{\prime}=s^{\prime}$, and
$s_{1},s_{1}^{\prime}\neq 0$ (already in the previous case) we get because of
$r^{\prime}\neq r$ and $s_{1},s_{1}^{\prime}\neq 0$, $r^{\prime}\neq r+2$,

$\displaystyle\alpha_{1}=\mathtt{a}^{r}\mathtt{b}^{s_{1}}\mathtt{a}\mathtt{a}\mathtt{b}^{s_{2}}$
$\displaystyle\neq\mathtt{a}^{r^{\prime}}\mathtt{b}^{s_{1}^{\prime}}\mathtt{a}\mathtt{b}\mathtt{b}^{s_{2}^{\prime}}=\beta_{3},$
$\displaystyle\alpha_{2}=\mathtt{a}^{r}\mathtt{b}^{s_{1}}\mathtt{b}\mathtt{a}\mathtt{b}^{s_{2}}$
$\displaystyle\neq\mathtt{a}^{r^{\prime}}\mathtt{b}^{s_{1}^{\prime}}\mathtt{a}\mathtt{b}\mathtt{b}^{s_{2}^{\prime}}=\beta_{3}$
$\displaystyle\alpha_{3}=\mathtt{a}^{r}\mathtt{b}^{s_{1}}\mathtt{a}\mathtt{b}\mathtt{b}^{s_{2}}$
$\displaystyle\neq\mathtt{a}^{r^{\prime}}\mathtt{b}^{s_{1}^{\prime}}\mathtt{a}\mathtt{b}\mathtt{b}^{s_{2}^{\prime}}=\beta_{3}.$

Consequently we have another $\lfloor\frac{k-2}{3}\rfloor+1$ different
scattered factors. This sums up to
$|\operatorname{ScatFact}_{k}(w)|\geq\frac{7k-8}{3}>k+1$. An immediate result
is that the $k$-spectrum has at least $k+3$ elements for $k\geq 5$. For $k=3$
and $k=4$ the results can be easily verified by testing.
case 2: $xz_{1}z_{2}\neq\mathtt{a}^{k-2}\mathtt{b}^{k-2}$
In this case all words of the form
$\mathtt{a}^{r}\mathtt{a}\mathtt{b}\mathtt{a}\mathtt{a}^{s}$ for $r+s=k-3$,
$r\in[|x|_{\mathtt{a}}]_{0}$, and $s\in[|y|_{\mathtt{a}}]_{0}$ are
$|x|_{\mathtt{a}}+1$ different scattered factors of length $k$ of $w$.
Analogously all
$\mathtt{b}^{r^{\prime}}\mathtt{a}\mathtt{b}\mathtt{a}\mathtt{b}^{s^{\prime}}$
with $r^{\prime}+s^{\prime}=k-3$, $r^{\prime}\in[|x|_{\mathtt{b}}]_{0}$,
$s^{\prime}\in[|y|_{\mathtt{b}}]_{0}$ are $|x|_{\mathtt{b}}+1$ different
scattered factors of length $k$ of $w$. All these factors are different and
additionally $w$ has $\mathtt{a}^{k}$ and $\mathtt{b}^{k}$ as scattered
factors. Hence
$|\operatorname{ScatFact}_{k}(w)|\geq|x|_{\mathtt{a}}+|x|_{\mathtt{b}}+4=|x|+4$
holds. Since the length of $w$ is $2k$, the length of $xy$ is $2k-3$ and
consequently $x$ and $y$ have different lengths. Assume w.l.o.g. $|x|>|y|$,
i.e. $|x|\geq k-1$. This implies $|\operatorname{ScatFact}_{k}(w)|\geq k+3$
follows. This proves the claim for $c=0$.

Assume now $c>0$ and let $w=\mathtt{a}^{k}\mathtt{b}^{k-c}$. By the previous
part we know $|\operatorname{ScatFact}_{k-c}(w)|=k-c+1$ if and only if
$w=\mathtt{a}^{k-c}\mathtt{b}^{k-c}$. The claim about the $(k-c)$-spectrum
follows immediately by
$\operatorname{ScatFact}_{k-c}(w)=\operatorname{ScatFact}_{k-c}(\mathtt{a}^{k}\mathtt{b}^{k-c})$
since the prepended $\mathtt{a}$s do not change the $(k-c)$-spectrum. For
$i\in[c-1]_{0}$ notice that
$x\in\operatorname{ScatFact}_{k-i}(\mathtt{a}^{k}\mathtt{b}^{k-c})$ implies
that $\mathtt{a}x$ (resp. $x\mathtt{b}$, $x\mathtt{a}$, $\mathtt{b}x$) is a
scattered factor of $\mathtt{a}^{k}\mathtt{b}^{k-c}$ of length $k-i+1$. Thus
$|\operatorname{ScatFact}_{k-i+1}(w)|\geq k-c+1$ follows. On the other hand a
scattered factor of $\mathtt{a}^{k}\mathtt{b}^{k-c}$ of length $k-i+1$ is
exactly of this form, since it can neither start with $\mathtt{b}$
($\mathtt{a}^{k}\mathtt{b}^{k-c}$ has only $(k-c)$ occurrences of
$\mathtt{b}$) nor contain $\mathtt{b}\mathtt{a}$ resp. $\mathtt{a}\mathtt{b}$
(this would be the implication of a scattered factor being of the form
$\mathtt{a}x^{\prime}$ with $|x^{\prime}|=k-i$,
$x^{\prime}\not\in\operatorname{ScatFact}_{k-i}(\mathtt{a}^{k}\mathtt{b}^{k-c})$).
∎

###### Remark 3

Theorem 3.2 answers immediately the question, whether a given set
$S\subseteq\Sigma^{k}$, with $|S|<k+1$ or $|S|=k+2$, is a $k$-spectrum of a
word $w\in\Sigma_{sb}^{2k}$ in the negative.

Theorem 3.2 shows that the smallest cardinality of the $k$-spectrum of a word
$w$ is reached when the letters in $w$ are nicely ordered, both for strictly
balanced words as well as for $c$-balanced words with $c>0$. The largest
cardinality is, not surprisingly, reached for words where the alternation of
$\mathtt{a}$ and $\mathtt{b}$ letters is, in a sense, maximal, e.g., for
$w=(\mathtt{a}\mathtt{b})^{k}$. To this end, one can show a general result.

###### Theorem 3.4

For $w\in\Sigma^{\ast}$, the $k$-spectrum of $w$ is $\Sigma^{k}$ if and only
if

$\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}^{k}\cap\operatorname{ScatFact}_{2k}(w)\neq\emptyset.$

###### Proof

We will show this result by induction. For $k=1$, the equivalence is:

$\operatorname{ScatFact}_{1}(w)=\Sigma\mbox{ iff
}\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}\cap\operatorname{ScatFact}_{2}(w)\neq\emptyset.$

If both $\mathtt{a}$ and $\mathtt{b}$ are scattered factors of $w$,
$\mathtt{a}\mathtt{b}$ or $\mathtt{b}\mathtt{a}$ has to be a factor and thus a
scattered factor of $w$. On the other hand if $w$ has $\mathtt{a}\mathtt{b}$
or $\mathtt{b}\mathtt{a}$ as a scattered factor, it has $\mathtt{a}$ and
$\mathtt{b}$ as scattered factors.

Assume now that the equivalence holds for an arbitrary but fixed
$k-1\in\mathbb{N}$. We will show it holds for $k$.

For the $\Leftarrow$-direction consider
$u\in\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}^{k}\cap\operatorname{ScatFact}_{2k}(u)$.
Thus,
$u\in\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}^{k-1}\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}$
and hence there exists
$u^{\prime}\in\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}^{k-1}$ with
$u\in u^{\prime}\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}$. By induction
we have $\operatorname{ScatFact}_{k-1}(u^{\prime})=\Sigma^{k-1}$. For any
$x\in\Sigma^{k}$ exists $x^{\prime}\in\Sigma^{k-1}$ with $x\in
x^{\prime}\\{\mathtt{a},\mathtt{b}\\}$. This implies that there exist
$a_{0},\dots$, $a_{k-1}\in\Sigma^{\ast}$ with
$u^{\prime}=a_{0}x^{\prime}[1]a_{1}\dots x^{\prime}[k-1]a_{k-1}$ since
$x^{\prime}\in\operatorname{ScatFact}_{k-1}(u^{\prime})$. By

$u\in a_{0}x^{\prime}[1]a_{1}\dots
x^{\prime}[k-1]a_{k-1}\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}$

it follows in both cases, namely $x=x^{\prime}\mathtt{a}$ or
$x=x^{\prime}\mathtt{b}$, that $x\in\operatorname{ScatFact}_{k}(w)$. This
proves the inclusion $\Sigma^{k}\subseteq\operatorname{ScatFact}_{k}(w)$. By
$\operatorname{ScatFact}_{k}(w)\subseteq\Sigma^{k}$ the first direction is
proven.

For the $\Rightarrow$-direction assume
$\operatorname{ScatFact}_{k}(w)=\Sigma^{k}$. Assume w.l.o.g.
$w[|w|]=\mathtt{a}$. Choose $x,y\in\Sigma^{\ast}$ with $w=xy$ and
$x[|x|]=\mathtt{b}$, and $y\in\mathtt{a}^{\ast}$. As
$\Sigma^{k-1}\mathtt{b}\subset\Sigma^{k}$, it follows that
$\Sigma^{k-1}b\subseteq\operatorname{ScatFact}_{k}(x)$. Clearly, this means
that $\Sigma^{k-1}\subseteq\operatorname{ScatFact}_{k-1}(x[1..|x|-1])$. By the
induction hypothesis, we get that
$\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}^{k-1}\cap\operatorname{ScatFact}_{2(k-1)}(x[1..|x|-1])\neq\emptyset$.
Thus,
$\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}^{k-1}x[|x|]\mathtt{a}\cap\operatorname{ScatFact}_{2k}(w[1..|x|+1])\neq\emptyset$,
because $w[1..|x|+1]=x[1..|x|]\mathtt{b}$. Hence,
$\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}^{k-1}\mathtt{b}\mathtt{a}\cap\operatorname{ScatFact}_{2k}(w)\neq\emptyset$.
The conclusion follows. ∎

The previous theorem has an immediate consequence, which exactly characterises
the strictly balanced words of length $2k$ for which the maximal cardinality
of $\operatorname{ScatFact}_{k}(w)$ is reached.

###### Proposition 5

For $k\in\mathbb{N}_{\geq 3}$ and $w\in\Sigma_{sb}^{2k}$ we have
$w\in\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}^{k}$ if and only if
$\operatorname{ScatFact}_{k}(w)=\Sigma^{k}$.

###### Proof

If $w\in\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}^{k}$, then
$\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}^{k}\cap\operatorname{ScatFact}_{2k}(w)\neq\emptyset$
and the claim follows by Theorem 3.4. On the other hand if
$\operatorname{ScatFact}_{k}(w)=\Sigma^{k}$ then
$\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}^{k}\cap\operatorname{ScatFact}_{k}(w)\neq\emptyset$
and since $|w|=2k$ we get
$w\in\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}^{k}$. ∎

To see why from $w\in\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}^{k}$ it
follows that $\operatorname{ScatFact}_{k}(w)=\Sigma^{k}$, note that, by
definition, a word $w\in\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}^{k}$
is just a concatenation of $k$ blocks from
$\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}$. To construct the scattered
factors of $w$, we can simply select from each block either the $\mathtt{a}$
or the $\mathtt{b}$. The resulting output is a word of length $k$, where in
each position we could choose freely the letter. Consequently, we can produce
all words in $\Sigma^{k}$ in this way. The other implication follows by
induction.

Generalising Proposition 5 for $c$-balanced words requires a more
sophisticated approach. A natural generalisation would be to consider
$w\in\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}^{k-c}\mathtt{a}^{c}$. By
Theorem 3.4 we have $\operatorname{ScatFact}_{k-c}(w)=\Sigma^{k-c}$. But the
size of $\operatorname{ScatFact}_{k-i}(w)$ for $i\in[c]_{0}$ depends on the
specific choice of $w$. To see why, consider the words
$w_{1}=\mathtt{b}\mathtt{a}\mathtt{a}\mathtt{b}\mathtt{b}\mathtt{a}$ and
$w_{2}=(\mathtt{b}\mathtt{a})^{3}$. Then by Proposition 5,
$|\operatorname{ScatFact}_{3}(w_{1})|=8=|\operatorname{ScatFact}_{3}(w_{2})|$.
However, when we append a $\mathtt{a}$ to the end of both $w_{1}$ and $w_{2}$,
we see that in fact $|\operatorname{ScatFact}_{4}(w_{1}\mathtt{a})|=10\neq
12=|\operatorname{ScatFact}_{4}(w_{2}\mathtt{a})|$. The main difference
between strictly and $c$-balanced words for $c>0$, regarding the maximum
cardinality of the scattered factors-sets, comes from the role played by the
factors $\mathtt{a}^{2}$ and $\mathtt{b}^{2}$ occurring in $w$.

In the remaining part of this section we present a series of results for
$c$-balanced words. Intuitively, the words with many alternations between
$\mathtt{a}$ and $\mathtt{b}$ have more distinct scattered factors. So, we
will focus on such words mainly. Our first result is a direct consequence from
Theorem 3.4. The second result concerns words avoiding $\mathtt{a}^{2}$ and
$\mathtt{b}^{2}$ gives a method to identify efficiently the $\ell$-spectra of
words which are prefixes of $(\mathtt{a}\mathtt{b})^{\omega}$, for all $\ell$.
Finally, we are able to derive a way to efficiently enumerate (and count) the
scattered factors of length $k$ of
$(\mathtt{a}\mathtt{b})^{k-c}\mathtt{a}^{c}$.

###### Corollary 6

For $k\in\mathbb{N}_{\geq 3}$, $c\in[k]_{0}$, and $w\in\Sigma^{2k-c}$
$c$-balanced, the cardinality of $\operatorname{ScatFact}_{k-c}(w)$ is exactly
$2^{k-c}$ if and only if
$\operatorname{ScatFact}_{2(k-c)}(w)\cap\\{\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{a}\\}^{k-c}\neq\emptyset$.

###### Proof

The claim follows directly by Theorem 3.4.∎

As announced, we further focus our investigation on the words
$w=(\mathtt{a}\mathtt{b})^{k-c}\mathtt{a}^{c}$. By Theorem 3.4 we have
$|\operatorname{ScatFact}_{i}(w)|=\Sigma^{i}$ for all $i\in[k-c]_{0}$. For all
$i$ with $k-c<i\leq k$, a more sophisticated counting argument is needed.
Intuitively, a scattered factor of length $i$ of
$(\mathtt{a}\mathtt{b})^{k-c}\mathtt{a}^{c}$ consists in a part that is a
subword (of arbitrary length) of $(\mathtt{a}\mathtt{b})^{k-c}$ followed a
(possibly empty) suffix of $\mathtt{a}$s. Thus, a full description of the
$\ell$-spectra of words that occur as prefixes of
$(\mathtt{a}\mathtt{b})^{\omega}$, for all appropriate $\ell$, is useful. To
this end, we introduce the notion of a deleting sequence: for a word $w$ and a
scattered factor $u$ of $w$ the deleting sequence contains (in a strictly
increasing order) $w$’s positions that have to be deleted to obtain $u$.

###### Definition 7

For $w\in\Sigma^{\ast}$, $\sigma=(s_{1},\dots,s_{\ell})\in[|w|]^{\ell}$, with
$\ell\leq|w|$ and $s_{i}<s_{i+1}$ for all $i\in[\ell-1]$, is a deleting
sequence. The scattered factor $u_{\sigma}$ associated to a deleting sequence
$\sigma$ is $u_{\sigma}=u_{1}\dots u_{\ell+1}$, where $u_{1}=w[1..s_{1}-1]$,
$u_{\ell+1}=w[s_{\ell}+1..|w|]$, and $u_{i}=w[s_{i-1}+1..{s_{i}}-1]$ for
$2\leq i\leq\ell$. Two sequences $\sigma,\sigma^{\prime}$ with
$u_{\sigma}=u_{\sigma^{\prime}}$ are called equivalent.

For the word $w=\mathtt{a}\mathtt{b}\mathtt{b}\mathtt{a}\mathtt{a}$ and
$\sigma=(1,3,4)$ the associated scattered factor is
$u_{\sigma}=\mathtt{b}\mathtt{a}$. Since $\mathtt{b}\mathtt{a}$ can also be
generated by $(1,3,5)$, $(1,2,4)$ and $(1,2,5)$, these sequences are
equivalent.

In order to determine the $\ell$-spectrum of a word $w\in\Sigma^{n}$ for
$\ell,n\in\mathbb{N}$, we can determine how many equivalence classes does the
equivalence defined above have, for sequences of length $k=n-\ell$. The
following three lemmata characterise the equivalence of deleting sequences.

###### Lemma 8

Let $w\in\Sigma^{n}$ be a prefix of $(\mathtt{a}\mathtt{b})^{\omega}$. Let
$\sigma=(s_{1},\ldots,s_{k})$ be a deleting sequence for $w$ such that there
exists $j\geq 2$ with $s_{j-1}<s_{j}-1$ and $s_{j}+1=s_{j+1}$. Then $\sigma$
is equivalent
$\sigma^{\prime}=(s_{1},\ldots,s_{j-1},s_{j}-1,s_{j+1}-1,s_{j+2},\ldots
s_{k})$, i.e., $\sigma^{\prime}$ is the sequence $\sigma$ where both $s_{j}$
and $s_{j+1}$ were decreased by $1$.

###### Proof

Since $s_{j-1}<s_{j}-1$, the factor $u_{\sigma}$ contains the letter
$w[s_{j}-1]$. If $w[s_{j}]=\mathtt{a}$ then $w[s_{j+1}]=w[s_{j}+1]=\mathtt{b}$
and $w[s_{j}-1]=\mathtt{b}$. Clearly, when deleting $w[s_{j}-1]$ and
$w[s_{j}]$ according to the sequence $\sigma^{\prime}$, the $\mathtt{b}$ that
was corresponding to $w[s_{j}-1]$ will be replaced by a letter $\mathtt{b}$
corresponding to $w[s_{j+1}]$, which is not deleted. So, in the end,
$u_{\sigma^{\prime}}=u_{\sigma}$. The case $w[s_{j}]=\mathtt{b}$ is analogous.
∎

###### Lemma 9

Let $w\in\Sigma^{n}$ be a prefix of $(\mathtt{a}\mathtt{b})^{\omega}$. Let
$\sigma=(s_{1},\ldots,s_{k})$ be a deleting sequence for $w$. Then there
exists an integer $j\geq 0$ such that $\sigma$ is equivalent to the deleting
sequence $(1,2,\ldots,j,s^{\prime}_{j+1},\ldots,s^{\prime}_{k})$, where
$s^{\prime}_{j+1}>j+1$ and $s^{\prime}_{i}>s^{\prime}_{i-1}+1$, for all
$j<i\leq k$. Moreover, $j\geq 1$ if and only if $\sigma$ contained two
consecutive positions or $\sigma$ started with $1$.

###### Proof

Let $\sigma_{0}=\sigma$. For $i\geq 0$, we iteratively transform $\sigma_{i}$
into $\sigma_{i+1}$ as follows: if $\sigma_{i}$ contains on consecutive
positions the numbers $g,t,t+1,h$, such that $g<t-1$ and $h>t+2$, we replace
them by $g,t-1,t,h$ and obtain the sequnce $\sigma_{i+1}$. By Lemma 8,
$\sigma_{i}$ is equivalent to $\sigma_{i+1}$. It is clear that in $O(n^{2})$
steps we will reach a sequence $\sigma_{\ell}$ which cannot be transformed
anymore. We take $\sigma^{\prime}=\sigma_{\ell}$ and it is immediate that it
will have the required form.∎

###### Lemma 10

Let $w\in\Sigma^{n}$ be a prefix of $(\mathtt{a}\mathtt{b})^{\omega}$. Let
$\sigma_{1}=(1,2,\ldots,j_{1},s^{\prime}_{j_{1}+1}$, $\ldots,s^{\prime}_{k})$,
where $s^{\prime}_{j_{1}+1}>j_{1}+1$ and $s^{\prime}_{i}>s^{\prime}_{i-1}+1$,
for all $j_{1}<i\leq k$, and
$\sigma_{2}=(1,2,\ldots,j_{2},s^{\prime\prime}_{j_{2}+1},\ldots,s^{\prime\prime}_{k})$,
where $s^{\prime\prime}_{j_{2}+1}>j_{2}+1$ and
$s^{\prime\prime}_{i}>s^{\prime\prime}_{i-1}+1$, for all $j_{2}<i\leq k$. If
$\sigma_{1}\neq\sigma_{2}$ then $\sigma_{1}$ and $\sigma_{2}$ are not
equivalent (i.e., $u_{\sigma_{1}}\neq u_{\sigma_{2}}$).

###### Proof

We first consider the case $j_{1}=j_{2}$. Let $\ell$ to be minimum such that
$s^{\prime}_{\ell}\neq s^{\prime\prime}_{\ell}$. We can assume without losing
generality that $s^{\prime}_{\ell}<s^{\prime\prime}_{\ell}$. Then
$u_{\sigma_{1}}$ and $u_{\sigma_{2}}$ share the same prefix of length
$t=(s^{\prime}_{\ell}-1)-(\ell-1)$. This prefix ends with
$w[s^{\prime}_{\ell}-1]$ and is followed by $w[s^{\prime}_{\ell}+1]$ in
$u_{\sigma_{1}}$ and, respectively, by $w[s^{\prime}_{\ell}]$ in
$u_{\sigma_{1}}$. But $w[s^{\prime}_{\ell}+1]\neq w[s^{\prime}_{\ell}]$, so
$u_{\sigma_{1}}\neq u_{\sigma_{2}}$.

Further, we consider the case when $j_{1}<j_{2}$ (the case $j_{2}<j_{1}$ is
symmetric); assume, as a convention, that $s^{\prime\prime}_{k+1}=0$ and let
$d=j_{2}-j_{1}$. Clearly, $j_{1}$ and $j_{2}$ must have the same parity, or
$u_{\sigma_{1}}$ and $u_{\sigma_{2}}$ would start with different letters, so
they would not be equal. Let $\ell$ to be minimum integer such that
$s^{\prime}_{\ell}-j_{1}\neq s^{\prime\prime}_{\ell+d}-j_{2}$; because
$s^{\prime\prime}_{k+1}=0$ by convention, we have $\ell\leq k$. If both $\ell$
and $\ell+d$ are at most $k$, then we get similarly to the case $j_{1}=j_{2}$
that $u_{\sigma_{1}}\neq u_{\sigma_{2}}$. In the case when $\ell\leq
k<\ell+d$, then, by length reasons, all positions $j>s_{\ell}$ (so, including
$s_{\ell}+1$) in $w$ should belong to $\sigma_{1}$, a contradiction. This
concludes our proof. ∎

Lemmas 8, 9, 10 show that the representatives of the equivalence classes
w.r.t. the equivalence relation between deleting sequences, introduced in
Definition 7, are the sequences
$(1,2,\ldots,j,s^{\prime}_{j+1},\ldots,s^{\prime}_{k})$, where
$s^{\prime}_{j+1}>j+1$ and $s^{\prime}_{i}>s^{\prime}_{i-1}+1$, for all
$j<i\leq k$. For a fixed $j\geq 1$, the number of such sequences is
${{(n-j-1)-(k-j)+1}\choose{k-j}}={{n-k}\choose{k-j}}$. For $j=0$, we have
${{(n-1)-k+1}\choose{k}}={{n-k}\choose{k}}$ nonequivalent sequences (note that
none starts with $1$, as those were counted for $j=1$ already). In total, we
have, for a word $w$ of length $n$, which is a prefix of
$(\mathtt{a}\mathtt{b})^{\omega}$, exactly
$\sum_{j\in[k]_{0}}{{n-k}\choose{k-j}}$ nonequivalent deleting sequences of
length $k$, so $\sum_{j\in[k]_{0}}{{n-k}\choose{k-j}}$ different scattered
factors of length $n-k$. In the above formula, we assume that ${a\choose b}=0$
when $a<b$.

Moreover, the distinct scattered factors of length $\ell=n-k$ of $w$ can be
obtained efficiently as follows. For $j$ from $0$ to $\ell$, delete the first
$j$ letters of $w$. For all choices of $\ell-j$ positions in $w[j+1..n]$, such
that each two of these positions are not consecutive, delete the letters on
the respective positions. The resulted word is a member of
$\operatorname{ScatFact}_{\ell}(w)$, and we never obtain the same word twice
by this procedure. The next theorem follows from the above.

###### Theorem 3.11

Let $w$ be a word of length $n$ which is a prefix of
$(\mathtt{a}\mathtt{b})^{\omega}$. Then
$|\operatorname{ScatFact}_{\ell}(w)|=\sum_{j\in[n-\ell]_{0}}{{\ell}\choose{n-\ell-j}}$.

A straightforward consequence of the above theorem is that, if $\ell\leq
n-\ell$ then $|\operatorname{ScatFact}_{\ell}(w)|=2^{\ell}$. With Theorem
3.11, we can now completely characterise of the cardinality of the
$\ell$-spectra of the $c$-balanced word
$(\mathtt{a}\mathtt{b})^{k-c}\mathtt{a}^{c}$ for $\ell\leq k$.

###### Theorem 3.12

Let $w=(\mathtt{a}\mathtt{b})^{k-c}\mathtt{a}^{c}$ for $k\in\mathbb{N}$,
$c\in[k]_{0}$. Then, for $i\leq k-c$ we have
$|\operatorname{ScatFact}_{i}(w)|=2^{i}$. For $k\geq i>k-c$ we have
$|\operatorname{ScatFact}_{i}(w)|=1+2^{k-c}+\sum_{j\in[(i+c)-k-1]_{0}}|\operatorname{ScatFact}_{i-j-1}((\mathtt{a}\mathtt{b})^{k-c-1}\mathtt{a})|$.

###### Proof

We will need to show the proof for $k\geq i>k-c$, as the other part follows
immediately from Theorem 3.4.

We give a method to count the scattered factors of
$w=(\mathtt{a}\mathtt{b})^{k-c}\mathtt{a}^{c}$. To begin with, we have the
scattered factor $\mathtt{a}^{i}$. All the other scattered factors must
contain a letter $\mathtt{b}$. Thus, we count separately the scattered factors
of the form $u\mathtt{b}\mathtt{a}^{j}$, for each $j\in[i-1]_{0}$. This is
equivalent to counting in how many ways we can choose $u$. For each such $u$
we will just have to append $\mathtt{b}\mathtt{a}^{j}$ at the end to get the
desired scattered factors of length. Thus, $|u|=i-j-1$. If $j\geq c$ then $u$
should occur as a scattered factor of
$(\mathtt{a}\mathtt{b})^{k-j-1}\mathtt{a}$ (in order to be able to append
$\mathtt{b}\mathtt{a}^{j}$ at its end and still stay as a scattered factor of
$w$), while if $j<c$ then $u$ should occur as a scattered factor of
$(\mathtt{a}\mathtt{b})^{k-c-1}\mathtt{a}$. In the first case, the length of
the scattered factor $u$ we want to generate is less than half of the length
of the word $(ab)^{t}a$ from which we generate it. So, there are $2^{i-j-1}$
choices for $u$. In the second case, if $j\geq(i+c)-k$, again, the length of
the scattered factor $u$ we want to generate is less than half of the length
of the word $(ab)^{k-c-1}a$ from which we generate it. So, there are
$2^{i-j-1}$ choices for $u$ again. Finally, if $j<(i+c)-k$, then there
$i-j-1>k-c-1$, and we need Theorem 3.4 to generate $u$. There are
$|\operatorname{ScatFact}_{i-j-1}((\mathtt{a}\mathtt{b})^{k-c-1}\mathtt{a})|$
ways to choose $u$ in this case. Summing all these up, we get the result from
the statement:

$1+\sum^{i-1}_{j=i+c-k}2^{i-j-1}+\sum_{j\in[i+c-k-1]_{0}}\operatorname{ScatFact}_{i-j-1}((\mathtt{a}\mathtt{b})^{k-c-1}\mathtt{a})=$
$1+2^{k-c}+\sum_{j\in[i+c-k-1]_{0}}\operatorname{ScatFact}_{i-j-1}((\mathtt{a}\mathtt{b})^{k-c-1}\mathtt{a}).$

This concludes our proof.∎

As in the case of the scattered factors of prefixes of
$(\mathtt{a}\mathtt{b})^{\omega}$, we have a precise and efficient way to
generate the scattered factors of
$w=(\mathtt{a}\mathtt{b})^{k-c}\mathtt{a}^{c}$. For scattered factors of
length $i\leq k-c$ of $w$, we just generate all possible words of length $i$.
For greater $i$, on top of $\mathtt{a}^{i}$, we generate separately the
scattered factors of the form $u\mathtt{b}\mathtt{a}^{j}$, for each
$j\in[i-1]_{0}$. It is clear that, in such a word, $|u|=i-j-1$, and if $j\geq
c$ then $u$ must be a scattered factor of
$(\mathtt{a}\mathtt{b})^{k-j-1}\mathtt{a}$, while if $j<c$ then $u$ must be a
scattered factor of $(\mathtt{a}\mathtt{b})^{k-c-1}\mathtt{a}$. If
$j\geq(i+c)-k$ then, by Theorem 3.11, $u$ can take all $2^{i-j-1}$ possible
values. For smaller values of $j$, we need to generate $u$ of length $i-j-1$
as a scattered factor of $(\mathtt{a}\mathtt{b})^{k-c-1}\mathtt{a}$, by the
method described after Proposition 5.

Nevertheless, Theorems 3.11 and 3.12 are useful to see that in order to
determine the cardinality of the sets of scattered factors of words consisting
of alternating $\mathtt{a}$s and $\mathtt{b}$s or, respectively, of
$(ab)^{k-c}a^{c}$, it is not needed to generate these sets effectively.

##  4 Cardinalities of $k$-Spectra of Strictly Balanced Words

In the last section a characterisation for the smallest and the largest
$k$-spectra of words of a given length are presented (Proposition 3.2 and 5).
In this section the part in between will be investigated for strictly balanced
words (i.e. words of length $2k$ with $k$ occurrences of each letter). As
before, we shall assume that $k\in\mathbb{N}_{\geq 3}$. In the particular case
that $k=3$, we have already proven that the k-spectrum with minimal
cardinality has $4$ elements and that the maximal cardinality is $8$. Moreover
as mentioned in Remark 3 a $k$-spectrum set of cardinality $5$ does not exist
for strictly balanced words of length $2k$. The question remains if
$k$-spectra of cardinalities $6$ and $7$ exist, and if so, for which words.

Befor showing that a $k$-spectrum of cardinality $2^{k}-1$ for strictly
balanced words of length $2k$ also exists for all $k\in\mathbb{N}_{\geq 3}$,
we prove that only scattered factors of the form
$\mathtt{b}^{i+1}\mathtt{a}^{k-i-1}$ for $i\in[k-2]_{0}$ (up to renaming,
reversal) can be “taken out” from the full set of possible scattered factors
independently, without additionally requiring the removal of additional
scattered factors as well. In particular, if a word of length $k$ of another
form is absent from the set of scattered factors of $w$, then
$|\operatorname{ScatFact}_{k}(w)|<2^{k}-1$ follows.

###### Lemma 13

If for $w\in\Sigma_{sb}^{2k}$ there exists
$u\notin\operatorname{ScatFact}_{k}(w)$ with
$u\notin\\{\mathtt{b}^{i}\mathtt{a}^{k-i}\mid
i\in[k-1]\\}\cup\\{\mathtt{a}^{i}\mathtt{b}^{k-i}\mid i\in[k-1]\\}$, then
$|\operatorname{ScatFact}_{k}(w)|<2^{k}-1$.

###### Proof

Let be $i\in[k-2]_{0}$. Consider firstly $u=\mathtt{b}^{r}\mathtt{a}^{s}$ for
$r+s=k$ and $r\not\in[i]\cup\\{k-i,\dots,k\\}$ and
$\Sigma^{k}\backslash\\{u\\}\supset\operatorname{ScatFact}_{k}(w)$ for a word
$w\in\Sigma_{ed}^{2k}$. If $\mathtt{b}^{r+1}\mathtt{a}^{s-1}$ is also not a
scattered factor of $w$, the claim is proven (in this case two elements of
$\Sigma^{k}$ are missing in $\operatorname{ScatFact}_{k}(w)$). Assume
$\mathtt{b}^{r+1}\mathtt{a}^{s-1}\in\operatorname{ScatFact}(w)$. This implies
that (possibly intertwined) $(s-1)$ occurrences of $\mathtt{a}$ follow $(r+1)$
occurrences of $\mathtt{b}$. Since $u$ is not a scattered factor of $w$, after
these $(s-1)$ $\mathtt{a}$s only $\mathtt{b}$s may occur. If
$\mathtt{b}^{r-1}\mathtt{a}^{s}\mathtt{b}$ is not a scattered factor, the
claim is again proven and so suppose that it is one. This implies that the
$(r-1)$ $\mathtt{b}$s are preceded by $\mathtt{a}$s and not by $\mathtt{b}$s.
This implies that $\mathtt{b}^{r+1}\mathtt{a}^{s-1}$ is not a scattered factor
and that contradicts the assumption. Consider now
$u=u_{1}\mathtt{b}^{r}\mathtt{a}^{s}\mathtt{b}^{t}u_{2}$ with $|u|=k$ not to
be a scattered factor of $w$ for $r,s,t\in\mathbb{N}$. Following the same
arguments as before, the claim is proven if
$u_{1}\mathtt{b}^{r-1}\mathtt{a}^{s}\mathtt{b}^{t+1}u_{2}$ is not a scattered
factor and hence it is assumed to be one. This implies that exactly
$|u_{1}|_{\mathtt{b}}$ $\mathtt{b}$s occur before $\mathtt{b}^{r-1}$. This
implies that $u_{1}\mathtt{b}^{r+1}\mathtt{a}^{s}\mathtt{b}^{t-1}u_{2}$ is not
a scattered factor of $w$ of length $k$. Analogously it can be proven that
scattered factors containing the switch from $\mathtt{a}$ to $\mathtt{b}$ and
back to $\mathtt{a}$ cannot lead to the cardinality $2^{k}-1$.∎

###### Proposition 14

For $k\in\mathbb{N}_{\geq 3}$ and $w\in\Sigma^{2k}_{sb}$, the set
$\operatorname{ScatFact}_{k}(w)$ has $2^{k}-1$ elements if and only if
$w\in\\{(\mathtt{a}\mathtt{b})^{i}\mathtt{a}^{2}\mathtt{b}^{2}(\mathtt{a}\mathtt{b})^{k-i-2}\mid
i\in[k-2]_{0}\\}$ (up to renaming and reversal). In particular
$\operatorname{ScatFact}_{k}(w)=\Sigma^{k}\backslash\\{\mathtt{b}^{i+1}\mathtt{a}^{k-i-1}\\}$
holds for
$w=(\mathtt{a}\mathtt{b})^{i}\mathtt{a}^{2}\mathtt{b}^{2}(\mathtt{a}\mathtt{b})^{k-i-2}$
with $i\in[k-2]_{0}$.

###### Proof

Let be $i\in[k-2]_{0}$. First ”$\Leftarrow$” will be proven and for that
consider
$w=(\mathtt{a}\mathtt{b})^{i}\mathtt{a}^{2}\mathtt{b}^{2}(\mathtt{a}\mathtt{b})^{k-i-2}$.
By Lemma 5 follows

$\operatorname{ScatFact}_{i}((\mathtt{a}\mathtt{b})^{i})=\Sigma^{i}\mbox{ and
}\operatorname{ScatFact}_{k-i-2}((\mathtt{a}\mathtt{b})^{k-i-2})=\Sigma^{k-i-2}.$

With
$\operatorname{ScatFact}_{2}(\mathtt{a}^{2}\mathtt{b}^{2})=\\{\mathtt{a}\mathtt{a},\mathtt{a}\mathtt{b},\mathtt{b}\mathtt{b}\\}$
the $k$-spectrum of $w$ has at least $3\cdot 2^{i}\cdot 2^{k-i-2}=3\cdot
2^{k-2}=2^{k}-2^{k-2}$ elements. Notice that by this construction, scattered
factors with a $\mathtt{b}\mathtt{a}$ at the middle position cannot be
reached. For this reason we have to have a look at $w$’s remaining scattered
factors not being gained by the above construction. This means that not only
$i$ letters are allowed to be taken of the first part and not only $k-i-2$
letters from the last part.

Having a deeper look into $(\mathtt{a}\mathtt{b})^{i}$ one can notice that all
binary numbers (encoded by $\mathtt{a},\mathtt{b}$) of length $i$ are
scattered factors of $(\mathtt{a}\mathtt{b})^{i-1}\mathtt{a}$. This implies
that nearly all binary numbers concatenated with $\mathtt{b}$ are in the
$i+1$-spectrum of $\mathtt{a}\mathtt{b}^{i}$. Appending now a $\mathtt{a}$
from the middle part and then each of the words from the last part leads to
nearly all remaining scattered factors of the $k$-spectrum of $w$. The only
missing word is $\mathtt{b}^{i+i}$, since the last $\mathtt{b}$ cannot be
reached within the first part. This implies that the word
$\mathtt{b}^{i+1}\mathtt{a}^{k-i-1}$ is not in the $k$-spectrum of $w$ since
with the (i+1)${}^{\text{th}}$ $\mathtt{b}$ the middle part is reached and the
last part contains only $k-i-2$ $\mathtt{a}$s. This concludes
$|\operatorname{ScatFact}_{k}(w)|=2^{k}-1$.

On the other hand if $|\operatorname{ScatFact}_{k}(w)|=2^{k}-1$ an element of
the form $\mathtt{b}^{i+1}\mathtt{a}^{k-i-1}$ for an $i\in[k-2]_{0}$ is
missing in the $k$-spectrum of $w$. Moreover this is exactly the only element
missing. Fix an $i\in[k-2]_{0}$ and set
$u=\mathtt{b}^{i+1}\mathtt{a}^{k-i-1}$. The proof will be very technically and
exclude step by step all other possibilities than $w$ being
$(\mathtt{a}\mathtt{b})^{i}\mathtt{a}^{2}\mathtt{b}^{2}(\mathtt{a}\mathtt{b})^{k-i-2}$.
Firstly consider $i=k-2$. This implies $u=\mathtt{b}^{k-1}\mathtt{a}$. In this
case $w$ has to end in $\mathtt{b}^{2}$ but not in $\mathtt{b}^{3}$ since
otherwise $\mathtt{b}^{k-2}\mathtt{a}^{2}$ would not be a scattered factor. If
$w$ were of the form $w_{1}\mathtt{b}\mathtt{a}\mathtt{b}^{2}$,
$|w_{1}|_{a}=k-1$ and $|w_{1}|_{b}=k-3$ would hold which would imply that
$\mathtt{b}^{k-2}\mathtt{a}^{2}$ is not a scattered factor. If $w$ ended in
$\mathtt{a}^{3}\mathtt{b}^{2}$, $\mathtt{a}^{k-2}\mathtt{b}\mathtt{a}$ would
be excluded. Hence, $w$ ends in $\mathtt{a}^{2}\mathtt{b}^{2}$. Suppose at
last that $w=(\mathtt{a}\mathtt{b})^{\ell}\mathtt{a}^{2}\mathtt{b}^{2}w_{2}$
holds for $\ell<k-2$ and $w_{2}\in\Sigma^{\ast}$. Then $w_{2}$ has each
$(k-\ell-2)$ $\mathtt{a}$ and $\mathtt{b}$. Thus
$\mathtt{b}^{\ell+1}\mathtt{a}^{k-\ell-1}$ is not a scattered factor of length
$k$. This proofs that for $i=k-2$
$w=(\mathtt{a}\mathtt{b})^{k-2}\mathtt{a}^{2}\mathtt{b}^{2}$ is implied by
$\mathtt{b}^{k-2}\mathtt{a}^{1}$ being the only excluded scattered factor from
$\Sigma^{k}$. Hence assume $i\in[k-3]_{0}$.
Supposition: $w$ ends in $\mathtt{b}^{\ell}$ for $\ell\geq 2$
If $i<k-2$ holds, then
$\mathtt{b}^{k-1}\mathtt{a}\not\in\operatorname{ScatFact}_{k}(w)$ follows and
since $i+1<k-1$ holds, this element is different from $u$.
In the next step it will be shown that exactly $k-i-1$ repetitions of
$\mathtt{a}\mathtt{b}$ are a suffix of $w$.
Supposition: $w=w_{1}\mathtt{b}^{2}(\mathtt{a}\mathtt{b})^{\ell}$
If $\ell>k-i-2$ held, $\mathtt{b}^{i+1}\mathtt{a}^{k-i-1}$ would not be a
scattered factor of $w$. If $\ell<k-i-2$ held,
$\mathtt{b}^{k-\ell-1}\mathtt{a}^{\ell+1}$ would not be a scattered factor
since $w_{1}$ has $(k-1)$ $\mathtt{a}$ and $(k-\ell-2)$ $\mathtt{b}$.
Supposition: $w=w_{1}\mathtt{a}^{2}(\mathtt{b}\mathtt{a})^{\ell}b$
In this case $|w_{1}|_{\mathtt{a}}=k-2-\ell$ and
$|w_{1}|_{\mathtt{b}}=k-\ell-1$ holds. This implies that
$\mathtt{a}^{k-2-\ell}\mathtt{b}^{\ell+1}\mathtt{a}$ is not in the
$k$-spectrum of $w$.
Consequently there exists a $w_{1}$ such that
$w=w_{1}\mathtt{b}^{2}(\mathtt{a}\mathtt{b})^{k-i-2}$ holds. In the next it
will be shown that $\mathtt{b}^{2}$ has to be preceded by $\mathtt{a}^{2}$.
Supposition: $w=w_{1}\mathtt{b}^{3}(\mathtt{a}\mathtt{b})^{k-i-2}$
Here $w_{1}$ has $(i+2)$ $\mathtt{a}$ and $(i-1)$ $\mathtt{b}$ and hence
$\mathtt{b}^{i}\mathtt{a}^{k-i-2}\mathtt{b}^{2}$ is not a scattered factor of
length $k$ of $w$.
Supposition:
$w=w_{1}\mathtt{b}\mathtt{a}\mathtt{b}^{2}(\mathtt{a}\mathtt{b})^{k-i-2}$
This implies
$\mathtt{a}^{i+2}\mathtt{b}\mathtt{a}\mathtt{b}^{k-i}\not\in\operatorname{ScatFact}_{k}(w)$
since $w_{1}$ has $i+1$ occurrences of $\mathtt{a}$ and $i-1$ occurrences of
$\mathtt{b}$.
This proofs that $\mathtt{a}^{2}\mathtt{b}^{2}(\mathtt{a}\mathtt{b})^{k-i-2}$
is a suffix of $w$. The case that this is preceded by another $\mathtt{a}$ is
excluded since then $\mathtt{a}^{i}\mathtt{b}\mathtt{a}^{k-i-1}$ would not be
in the $k$-spectrum of $k$. In the last step it will be shown that the first
occurrence of $\mathtt{a}^{2}$ is at the point $2\ell$.
Supposition: $w=(\mathtt{a}\mathtt{b})^{\ell}\mathtt{a}^{2}w_{2}$ for
$\ell\neq i$
If $\ell$ is smaller than $i$, $|w_{2}|_{\mathtt{a}}=k-\ell-2$ and
$|w_{2}|_{\mathtt{b}}=k-\ell$ hold and
$\mathtt{b}^{\ell+1}\mathtt{a}^{k-\ell-1}\not\in\operatorname{ScatFact}_{k}(w)$
follows. If $\ell$ is greater than $i$, in contradiction to the main
assumption $\mathtt{b}^{i+1}\mathtt{a}^{k-i-1}$ is a scattered factor, because
$\mathtt{b}^{i+1}$ is a scattered factor of $(\mathtt{a}\mathtt{b})^{\ell}$
and $k-\ell+\ell-(i+1)=k-i-1$ $\mathtt{a}$ are left in the rest of $w$.
Combining $w=(\mathtt{a}\mathtt{b})^{i}\mathtt{a}^{2}w_{2}$ and
$w=w_{1}\mathtt{a}^{2}\mathtt{b}^{2}(\mathtt{a}\mathtt{b})^{k-i-2}$ the claim
that $w$ is of the form
$(\mathtt{a}\mathtt{b})^{i}\mathtt{a}^{2}\mathtt{b}^{2}(\mathtt{a}\mathtt{b})^{k-i-2}$
is proven.∎

By Proposition 14 we get that $7$ is a possible cardinality of the set of
scattered factors of length $3$ of strictly balanced words of length $6$ and,
moreover, that exactly the words
$\mathtt{a}^{2}\mathtt{b}^{2}\mathtt{a}\mathtt{b}$ and
$\mathtt{a}\mathtt{b}\mathtt{a}^{2}\mathtt{b}^{2}$ (and symmetric words
obtained by reversal and renaming) have seven different scattered factors. The
following lemma demonstrates that there always exists a strictly balanced word
$w$ of length $2k$ such that $|\operatorname{ScatFact}_{k}(w)|=2k$. Thus, for
the case $k=3$ also the question if six is a possible cardinality of
$\operatorname{ScatFact}_{3}(w)$ can be answered positively.

###### Theorem 4.15

The $k$-spectrum of a word $w\in\Sigma_{sb}^{2k}$ has exactly $2k$ elements if
and only if
$w\in\\{\mathtt{a}^{k-1}\mathtt{b}\mathtt{a}\mathtt{b}^{k-1},\mathtt{a}^{k-1}\mathtt{b}^{k}\mathtt{a}\\}$
holds (up to renaming and reversal). Moreover, there does not exist a strictly
balanced word $w\in\Sigma_{sb}^{2k}$ with a $k$-spectrum of cardinality $2k-i$
for $i\in[k-2]$.

###### Proof

Consider first $w=\mathtt{a}^{k-1}\mathtt{b}\mathtt{a}\mathtt{b}^{k-1}$. By
Lemma LABEL:lemenougha follows $w$ has at least $k+1$ elements since the
$k$-spectrum of $\mathtt{a}^{k}\mathtt{b}^{k}$ is a subset of the $k$-spectrum
of $w$. Additionally $w$ has the scattered factors of the form
$\mathtt{a}^{i}\mathtt{b}\mathtt{a}\mathtt{b}^{k-2-i}$, which sum up to $k-1$.
Hence $|\operatorname{ScatFact}_{k}(w)|=k+1+k-1=2k$ holds. Again by Lemma
LABEL:lemenougha, $\mathtt{a}^{k-1}\mathtt{b}^{k}\mathtt{a}$ has all elements
of $\mathtt{a}^{k}\mathtt{b}^{k}$’s $k$-spectrum as scattered factors. Here
the word has in addition all words of the form
$\mathtt{a}^{i}\mathtt{b}^{k-1-i}\mathtt{a}$ as scattered factors which sum up
to $k-1$ as well. This proves that both words have a scattered factor set of
cardinality $2k$.

The other direction will be proven by contraposition following the two main
cases

$\mathtt{a}^{k-1}\mathtt{b}\mathtt{a}\mathtt{b}^{k-1}\quad\mbox{and}\quad\mathtt{a}^{k-1}\mathtt{b}^{k}\mathtt{a}.$

Assume first $w=\mathtt{a}^{\ell}\mathtt{b}x$ for $\ell\in[k-2]_{\geq 2}$.
Notice that it does not have to be considered that the word starts with one
$\mathtt{a}$, since this is symmetric to the reversal of the case
$\mathtt{a}^{k-1}\mathtt{b}^{k}\mathtt{a}$. This implies $|x|_{a}=k-\ell$ and
$|x|_{b}=k-1$. Notice here $k-\ell<k-1$. Thus, there exists a scattered factor
$x^{\prime}$ of $x$ of length $2(k-\ell)$ with
$|x^{\prime}|_{a}=|x^{\prime}|_{b}=k-\ell$. By Lemma 3.2 follows

$|\operatorname{ScatFact}_{k-\ell}(y)|=k-\ell+1\Leftrightarrow
y\in\\{\mathtt{a}^{k-\ell}\mathtt{b}^{k-\ell},\mathtt{b}^{k-\ell}\mathtt{a}^{k-\ell}\\}$

and $|\operatorname{ScatFact}_{k-\ell}(y)|>k-\ell+1$ otherwise. This implies
that the $(k-\ell)$-spectrum of $x^{\prime}$ is minimal with respect to
cardinality if $x^{\prime}$ is either $\mathtt{a}^{k-\ell}\mathtt{b}^{k-\ell}$
or $\mathtt{b}^{k-\ell}\mathtt{a}^{k-\ell}$. For giving a lower bound of the
cardinality of $w$’s scattered factor set of length $k$, it is sufficient to
only take these both options into consideration. This implies that it is not
necessary to examine the cases where $x$ contains other scattered factors with
both $k-\ell$ $\mathtt{a}$ and $\mathtt{b}$.

case 1: $x^{\prime}=\mathtt{a}^{k-\ell}\mathtt{b}^{k-\ell}$
Thus $x$ contains $\ell-1$ $\mathtt{b}$ which are not in $x^{\prime}$.
case a: $x=\mathtt{b}^{\ell-1}\mathtt{a}^{k-\ell}\mathtt{b}^{k-\ell}$
In this case
$w=\mathtt{a}^{\ell}\mathtt{b}^{\ell}\mathtt{a}^{k-\ell}\mathtt{b}^{k-\ell}$
holds and that the $k$-spectrum of $\mathtt{a}^{k}\mathtt{b}^{k}$ is a subset
of $\operatorname{ScatFact}_{k}(w)$ follows.
case i: $\ell<k-\ell$
For all $s\in[\ell]$ the words
$\mathtt{a}^{\ell-s}\mathtt{b}^{s}\mathtt{a}^{k-\ell},\dots,\mathtt{a}^{\ell}\mathtt{b}^{s}\mathtt{a}^{k-\ell-s}$
are well-defined and sum up to $s+1$. Moreover for every $s_{2}\in[k-\ell]$
exists $r_{1}\in\mathbb{N}_{0}$ and exist $r_{2},s_{2}\in\mathbb{N}$ such that
the words
$\mathtt{a}^{r_{1}}\mathtt{b}^{s_{1}}\mathtt{a}^{r_{2}}\mathtt{b}^{s_{2}}$
with $s_{1}+r_{1}+s_{2}+r_{2}=k$ are all distinct and distinct to the
aforementioned. Thus, in this case

$k+1+\sum_{s=1}^{\ell}(s+1)+k-\ell=2k+1-\ell+\frac{\ell(\ell+1)}{2}+\ell\geq
2k+4$

is a lower bound for $\operatorname{ScatFact}_{k}(w)$.
case ii: $\ell>k-\ell$
Consider here for $r\in[k-\ell]$ the words
$\mathtt{b}^{\ell-r}\mathtt{a}^{r}\mathtt{b}^{k-\ell},\dots,\mathtt{b}^{\ell}\mathtt{a}^{r}\mathtt{b}^{k-\ell-r}$.
For fixed $r$ these are $r+1$. Moreover in this case for all $r_{1}\in[\ell]$
exist $s_{1},r_{2}\in\mathbb{N}$ and $s_{2}\in\mathbb{N}$ such that the words
$\mathtt{a}^{r_{1}}\mathtt{b}^{s_{1}}\mathtt{a}^{r_{2}}\mathtt{b}^{s_{2}}$
with $s_{1}+r_{1}+s_{2}+r_{2}=l$ are all distinct and distinct to the
aforementioned. In total this sums up to

$k+1+\sum_{r=1}^{k-\ell}(r+1)+\ell=k+1+\frac{(k-\ell)(k-\ell+1)}{2}+(k-\ell)+\ell\geq
2k+4$

different scattered factors.
case b: $x=\mathtt{a}^{k-\ell}\mathtt{b}^{k-1}$
Thus, $w=\mathtt{a}^{\ell}\mathtt{b}\mathtt{a}^{k-\ell}\mathtt{b}^{k-1}$
holds. Here it holds as well that the $k$-spectrum of
$\mathtt{a}^{k}\mathtt{b}^{k}$ is a subset of
$\operatorname{ScatFact}_{k}(w)$. Moreover all words of the form
$\mathtt{b}\mathtt{a}^{r}\mathtt{b}^{s}$ for $r+s=k-1$ and $r\in[k-\ell]$ are
different scattered factors, i.e. $k-\ell$ many. Additionally the words
$\mathtt{a}^{r}\mathtt{b}\mathtt{a}\mathtt{b}^{s}$ for $r+s=k-2$ and $r,s>0$
are different scattered factors and distinct to the aforementioned. This sums
up to $k+1+k-1+k-2=3k-2$ for the cardinality of
$\operatorname{ScatFact}_{k}(w)$. This proves the claim for $k\geq 3$.

case 2: $x^{\prime}=\mathtt{b}^{k-\ell}\mathtt{a}^{k-\ell}$
Consequently
$x\in\\{\mathtt{b}^{k-1}\mathtt{a}^{k-\ell},\mathtt{b}^{k-\ell}\mathtt{a}^{k-\ell}\mathtt{b}^{\ell-1}\\}$
holds.
case a: $x=\mathtt{b}^{k-1}\mathtt{a}^{k-\ell}$
Hence $w=\mathtt{a}^{\ell}\mathtt{b}^{k}\mathtt{a}^{k-\ell}$. Here only
$\ell+1$ different scattered factors are of the form
$\mathtt{a}^{r}\mathtt{b}^{s}$ exist and $k-\ell$ of the form
$\mathtt{b}^{s}\mathtt{a}^{r}$ with $r+s=k$ (notice that the latter ones are
only $k-\ell$ since among all of them one is in common with the first ones).
Finally consider the words of the form
$\mathtt{a}^{r}_{1}\mathtt{b}^{s}\mathtt{a}^{r_{2}}$ with $r_{1}+r_{2}+s=k$
and $r_{1},r_{2},s>0$. This sums up to $\ell+1+k-\ell+k$. By
$\mathtt{a}^{k}\in\operatorname{ScatFact}_{k}(w)$,
$|\operatorname{ScatFact}_{k}(w)|\geq 2k+2$ follows.
case b: $x=\mathtt{b}^{k-\ell}\mathtt{a}^{k-\ell}\mathtt{b}^{\ell-1}$
In this case
$w=\mathtt{a}^{\ell}\mathtt{b}^{k-\ell+1}\mathtt{a}^{k-\ell}\mathtt{b}^{\ell-1}$
holds. Here the cardinality of the $k$-spectrum of $w$ is determined
analogously to case 1a.∎

By Lemma 14 and Theorem 4.15 the possible cardinalities of
$\operatorname{ScatFact}_{3}(w)$ for strictly balanced words $w$ of length $6$
are completely characterized.

Figure 1: For $k=3$ there exist strictly balanced words of length $2k$, such
that their $k$-spectra have cardinality $k+1,2k,2^{k}-1$ and $2^{k}$.

Theorem 4.15 determines the first gap in the set of cardinalities of
$|\operatorname{ScatFact}_{k}(w)|$ for $w\in\Sigma_{sb}^{2k}$: there does not
exist a word $w\in\Sigma_{sb}^{2k}$ with
$|\operatorname{ScatFact}_{k}(w)|=k+i+1$ for $i\in[k-2]$ and $k\geq 3$, since
all words that are not of the form $\mathtt{a}^{k}\mathtt{b}^{k}$,
$\mathtt{b}^{k}\mathtt{a}^{k},\mathtt{a}^{k-1}\mathtt{b}\mathtt{a}\mathtt{b}^{k-1}$,
or $\mathtt{a}^{k-1}\mathtt{b}^{k}\mathtt{a}$ have a scattered factor set of
cardinality at least $2k+1$. As the size of this first gap is linear in $k$,
it is clear that the larger $k$ is, the more unlikely it is to find a
$k$-spectrum of a small cardinality.

In the following we will prove that the cardinalities $2k+1$ up to $3k-4$ are
not reachable, i.e. $3k-3$ is the thirst smallest cardinality after $k+1$ and
$2k$ (witnessed by, e.g. $\mathtt{a}^{k-2}\mathtt{b}^{k}\mathtt{a}^{2}$).

###### Lemma 16

For $i\in\big{[}\lfloor\frac{k}{2}\rfloor\big{]}$ and $j\in[k-1]$

  * •

$|\operatorname{ScatFact}_{k}(\mathtt{a}^{k-i}\mathtt{b}^{k}\mathtt{a}^{i})|=k(i+1)-i^{2}+1$
for $k\geq 4$,

  * •

$|\operatorname{ScatFact}_{k}(\mathtt{a}^{k-1}\mathtt{b}^{2}\mathtt{a}\mathtt{b}^{k-2})|=3k-2$,

  * •

$|\operatorname{ScatFact}_{k}(\mathtt{a}^{k-2}\mathtt{b}^{j}\mathtt{a}\mathtt{b}^{k-j}\mathtt{a})|=k(2j+2)-6j+2$
for $k\geq 5$, and

  * •

$|\operatorname{ScatFact}_{k}(\mathtt{a}^{k-2}\mathtt{b}^{j}\mathtt{a}^{2}\mathtt{b}^{k-j})|=k(2j+1)-4j+2$.

###### Proof

For the first part, let be $i\in\big{[}\lfloor\frac{k}{2}\rfloor\big{]}_{\geq
2}$. The $k$-spectrum of $\mathtt{a}^{k-i}\mathtt{b}^{k}\mathtt{a}^{i}$
contains exactly all words of the form
$\mathtt{a}^{r}\mathtt{b}^{s}\mathtt{a}^{t}$ with $r+s+t=k$, $t\in[i]_{0}$,
$r\in[k-i]_{0}$, and $s\in[k]_{0}$. If $t$ and $r$ are fixed, $s$ is uniquely
determined. Since all these scattered factors are different, the $k$-spectrum
has $(i+1)(k-i+1)=k(i+1)-i^{2}-1$ elements.

For the second part, notice that the scattered factors
$\mathtt{a}^{k-1}\mathtt{b}^{2}\mathtt{a}\mathtt{b}^{k-2}$ are of four
different forms: $\mathtt{b}^{r}\mathtt{a}\mathtt{b}^{t}$,
$\mathtt{a}^{r}\mathtt{b}^{s}\mathtt{a}$, $\mathtt{a}^{r}\mathtt{b}^{s}$, and
$\mathtt{a}^{r}\mathtt{b}^{s_{1}}\mathtt{a}\mathtt{b}^{s_{2}}$. All these
scattered factors are different if in the second one $s$ is chosen greater
than or equal to $1$ and in the last one $r,s_{1},s_{2}\geq 1$ holds. The
first and second one lead to two scattered factors, since for every $s\in[2]$
there are enough $\mathtt{a}$ at the beginning for padding from the left. The
third form leads to $k+1$ different scattered as shown in Lemma 3.2. The last
one is a little bit more complicated. Notice firstly that $r$ is at most $k-3$
since $s_{1},s_{2}>0$ holds. In this case there exists only one possibility
for chosing $s_{1}$ and $s_{2}$, namely as $1$. If $r$ is $k-4$ there exist
two possibilities, namely $s_{1}=1$ and $s_{2}=2$ or vice versa. For
$r\in[k-5]$ there exist always $2$ possibilities for the $\mathtt{b}$s between
the $\mathtt{a}$s. This leads to $2(k-5)$ possibilities. Allover it sums up to
$2+2+k+1+1+2+2(k-5)=8+3k-10=3k-2$.

As in the proof of the second part for the third and fourth part the scattered
factors can be categorized in the form $\mathtt{a}^{r}\mathtt{b}^{s}$,
$\mathtt{b}^{r_{1}}\mathtt{a}^{s}\mathtt{b}^{r_{2}}$,
$\mathtt{a}^{r_{1}}\mathtt{b}^{s}\mathtt{a}^{r_{2}}$, and
$\mathtt{a}^{r_{1}}\mathtt{b}^{s_{1}}\mathtt{a}^{r_{2}}\mathtt{b}^{s_{2}}$,
where with appropriate chosen exponents no factors is counted twice. Also as
before, $i$ can be chosen in $\left[\lfloor\frac{k}{2}\rfloor\right]$, since
otherwise the proof is analogous for $k-i$. The first form contributes $k+1$
elements. The second and third form contribute $2i$ each, since $s$ resp.
$r_{2}$ range in $[2]$. For the last form a distinction is necessary. If
$r=k-3$ holds, $\mathtt{a}^{k-3}\mathtt{b}\mathtt{a}\mathtt{b}$ is the only
scattered factor. If $r$ is smaller than $k-3$, $2i$ possibilites for each
$r\in[k-3]$ lead to scattered factors. Allover this sums up to
$k+1+2i+2i+1+2i(k-4)=k(2i+1)-4i+2$. By this the first claim is proven.

For the fourth claim again scattered factors of different forms will be
distinguished. Since also here the minimal $k$-spectrum is a subset of the
$k$-spectrum of $w$, these $k+1$ elements counts for the cardinality. There
exists $i$ many scattered factors of the form
$\mathtt{a}^{r}\mathtt{b}^{s}\mathtt{a}^{2}$ and $k-2$ of the form
$\mathtt{a}^{r}\mathtt{b}^{s}\mathtt{a}$, since with the last $\mathtt{a}$ all
occurrences of $\mathtt{b}$ are before it. Assuming w.l.o.g. again that $i$ is
at most $\frac{k}{2}$ only $\mathtt{b}^{k-1}\mathtt{a}$ is a scattered factor
of the form $\mathtt{b}^{s}\mathtt{a}^{r}$. The scattered factors of the form
$\mathtt{b}^{r_{1}}\mathtt{a}\mathtt{b}^{r_{2}}\mathtt{a}$ contribute $i$
many. The remaining two forms need again a case analysis. There exists exactly
one scattered factor of the form
$\mathtt{a}^{r}\mathtt{b}^{s_{1}}\mathtt{a}\mathtt{b}^{s_{2}}$ for $r=k-3$ and
exactly one scattered factor of the form
$\mathtt{a}^{r_{1}}\mathtt{b}^{s_{1}}\mathtt{a}\mathtt{b}^{s_{2}}\mathtt{a}$
for $r_{1}=k-4$. If $r$ resp. $r_{1}$ are smaller there exists $i$ different
scattered factors for each choice of $r\in[k-4]$ resp. $r_{1}\in[k-5]$. This
sums up to
$k+1+k-2+i+i+1+i+1+i(k-5)+1+k(i-4)=2k+2+3i+ik-5i+ik-4i=k(2+2i)-6i+2$. ∎

Notice that for $i\in\left[\lfloor\frac{k}{2}\rfloor\right]$ the sequence
$(k(2i+1)-4i+2)_{i}$ is increasing and its minimum is $3k-2$ while for
$i\in\left[\lfloor\frac{k}{2}\rfloor\right]$ the sequence $(k(2i+2)-6i+2)_{i}$
is increasing and its minimum is $4k-4$. The following lemma only gives lower
bounds for specific forms of words, since, on the one hand, it proves to be
sufficient for the Theorem 4.18 which describes the second gap, and, on the
other hand, the proofs show that the formulas describing the exact number of
scattered factors of a specific form are getting more and more complicated. It
has to be shown that also words starting with $i$ letters $\mathtt{a}$, for
$i\in[k-3]$, have a $k$-spectrum of greater (as lower is already excluded)
cardinality. By Lemma 16 only words with another transition from
$\mathtt{a}$’s to $\mathtt{b}$’s need to be considered,
($w=\mathtt{a}^{r_{1}}\mathtt{b}^{s_{1}}w_{1}\mathtt{a}^{r_{1}}\mathtt{b}^{s_{2}}$).
W.l.o.g. we can assume $s_{1}$ to be maximal, such that $w_{1}$ starts with an
$\mathtt{a}$, and similarly, by maximality of $r_{2}$, ends with a
$\mathtt{b}$, thus only words of the form
$\mathtt{a}^{r_{1}}\mathtt{b}^{s_{1}}\dots\mathtt{a}^{r_{n}}\mathtt{b}^{s_{n}}$
have to be considered, and by Proposition 5, it is sufficient to investigate
$n<k$.

###### Lemma 17

  * •

$|\operatorname{ScatFact}_{k}(\mathtt{a}^{k-2}\mathtt{b}^{i}\mathtt{a}\mathtt{b}^{j}\mathtt{a}\mathtt{b}^{k-i-j})|\geq
3k-3$ for $i,j\in[k-2]$, $i+j\leq k-1$,

  * •

$|\operatorname{ScatFact}_{k}(\mathtt{a}^{k-2}\mathtt{b}^{s_{1}}\mathtt{a}^{r_{1}}\mathtt{b}^{s_{2}}\mathtt{a}^{r_{2}}\mathtt{b}^{s_{3}})|\geq
3k-4$ for $s_{1}+s_{2}+s_{3}=k$, $r_{1}+r_{2}=2$,$s_{1}>0$,
$r_{1},r_{2},s_{2},s_{3}\geq 0$,

  * •

$|\operatorname{ScatFact}_{k}(\mathtt{a}^{r_{1}}\mathtt{b}^{s_{1}}\dots\mathtt{a}^{r_{n}}\mathtt{b}^{s_{n}})|\geq
3k-3$ for $r_{1}\leq k-3$, $\sum_{i\in[n]}r_{i}=\sum_{i\in[n]}s_{i}=k$, and
$r_{i},s_{i}\geq 1$.

###### Proof

Choose for the first claim $i,j\in[k-2]$. Then all words of the form
$\mathtt{a}^{r}\mathtt{b}^{s}$ for $r,s\in[k]_{0}$ are scattered factors of
$w_{ij}$ and by Lemma 3.2 follows that $w_{ij}$ has $k+1$ scattered factors of
this form. Scattered factors of the form
$\mathtt{a}^{r_{1}}\mathtt{b}^{s}\mathtt{a}^{r_{2}}$ can occur in three
variants. In the first variant only the second block of $\mathtt{a}$ is
involved after the first block of $\mathtt{b}$, namely the second single
$\mathtt{a}$ is not involved. Since $i\in[k-2]$ holds, for each $s\in[i]$
exists $r_{1},r_{2}$ ($r_{2}=1$) such that
$\mathtt{a}^{r_{1}}\mathtt{b}^{s}\mathtt{a}^{r_{2}}$ is a scattered factor of
$w_{ij}$, i.e. $w_{ij}$ has additionally $i$ scattered factors. The second
variant uses the $\mathtt{a}$ of each the second and the third
$\mathtt{a}$-block. This only scattered factors of the form
$\mathtt{a}^{r_{1}}\mathtt{b}^{s}\mathtt{a}^{r_{2}}$ are of interest, the
second $\mathtt{b}$-block is not involved. If $i+j=k-1$ holds only $i-1$
scattered factors of this form occurs, otherwise again $i$ new elements are in
the $k$-spectrum. If only the $\mathtt{a}$ from the third block is involved
then $j$ (resp. $j-1$) new elements are in the spectrum. This sums up to at
least $2i+j-2$ elements of the form
$\mathtt{a}^{r_{1}}\mathtt{b}^{s}\mathtt{a}^{r_{2}}$. A similar distinction
leads to the number of scattered factors of the form
$\mathtt{a}^{r_{1}}\mathtt{b}^{s_{1}}\mathtt{a}^{r_{2}}\mathtt{b}^{s_{2}}$.
Assume first $r_{2}=1$ and for this only the $\mathtt{a}$ from the second
$\mathtt{a}$-block. This implies that either only $\mathtt{b}$ from the second
block or from the second and third block can be taken for the last
$\mathtt{b}$-block in the scattered factor. Moreover $r_{1},s_{1},s_{2}$ are
at most $k-3$. For each choice of $r_{1}$ in $[k-3]$ there are
$\min\\{j,k-2-i\\}$ possibilities, which leads to

$i\left((k-j-2)j+\sum_{\ell=1}^{k-j-2}k-2-\ell\right)=6i+1\frac{1}{2}k^{2}i-kji-3\frac{1}{2}ki+1\frac{1}{2}j^{2}i+1\frac{1}{2}ji.$

If $\mathtt{b}$ from the second and third block are allowed, all of the second
block have to occur for obtaining different scattered factors to the previous
ones. Thus,

$i\left((k-j-i-2)j+\sum_{\ell=1}^{k-j-i-2}k-2-\ell\right)\\\
=kij+\frac{1}{2}k^{2}-1\frac{1}{2}k-ik-jk-
ij^{2}-i^{2}j-ij+1\frac{1}{2}i+1\frac{1}{2}j+\frac{1}{2}i^{2}+\frac{1}{2}j^{2}.$

If both, the second and the third $\mathtt{a}$-block, are involved
$ik-1\frac{1}{2}i^{2}-ij-\frac{1}{2}i$ additional scattered factors are in the
$k$-spectrum. This all sums up to

$\displaystyle
k+1+9i-2+1\frac{1}{2}k^{2}i-3\frac{1}{2}ki+\frac{1}{2}j^{2}i-\frac{1}{2}ji+\frac{1}{2}j+\frac{1}{2}i^{2}+\frac{1}{2}j^{2}.$

Since either $i^{2}\geq ij$ or $j^{2}\geq ij$ and $i,j\in[k-3]$ hold, this is
greater than or equal to

$1\frac{1}{2}k^{2}-2\frac{1}{2}k+9\frac{1}{2}\geq 3k-3.$

Notice that additionally there exist scattered factors of other forms, which
enlarge the concrete $k$-spectrum.

For the second claim. consider first the case, when $s_{2}=0$, $r_{1}=0$, or
$r_{2}=0$. This leads to words of the form matching Lemma 16 and consequently
the $k$-spectrum has $k(2i+1)-4i+2\geq 3k-2>3k-4$ elements. Consider now the
case that $s_{3}=0$ holds and all other exponents are at least $1$. By Lemma
16 follows again that each such word has at least $k(2i+2)-6i+2\geq 4k-4>3k-4$
elements. Finally by Lemma 17 follows that the remaining words of the given
form have at least $3k-3$ scattered factors.

For the third claim, obviously $\mathtt{a}^{k}$ is a scattered factor and
$\mathtt{a}^{k-i}\mathtt{b}^{i}$ for $s_{n}$ also. Notice here, that the proof
leads to $s_{n-1}$ scattered factors, if in the claim $s_{n}=0$ would be
allowed. Consider now the scattered factors of the form
$\mathtt{a}^{i}\mathtt{b}^{j}$ for $i,j\in[k]$. Let $m$ be the number of the
block in which the i${}^{\text{th}}$ $\mathtt{a}$ occurs. If
$s_{m}+\dots+s_{n}\geq k-i$ holds, $\mathtt{a}^{i}\mathtt{b}^{k-i}$ is a
scattered factor of $w$. Consider the opposite. This implies that from the
m${}^{\text{th}}$ till the n${}^{\text{th}}$ block less then $k-i$
$\mathtt{b}$ occur. Thus in the blocks $1$ to $i$ there occur more than $i$
$\mathtt{b}$. Since the i${}^{\text{th}}$ $\mathtt{a}$ is in the
m${}^{\text{th}}$ block, from this point till the end there are $k-i$
$\mathtt{a}$. Hence $\mathtt{b}^{i}\mathtt{a}^{k-i}$ is a scattered factor of
$w$. So in each case at least one scattered factor occurs, i.e. at least $k+1$
scattered factors of this form are in the $k$-spectrum. Notice here, that the
argument holds still if $s_{m}=0$ is allowed. With a similar argumentation the
number of occurrences of the form
$\mathtt{a}^{i}\mathtt{b}^{j}\mathtt{a}^{k-i-j}$ will be shown. If for a
specific $i,j$-combination $\mathtt{a}^{i}\mathtt{b}^{j}\mathtt{a}^{k-i-j}$ is
not a scattered factor, then choose $m_{1},m_{2}$ such that the
i${}^{\text{th}}$ $\mathtt{a}$ is in block $m_{1}$ and the j${}^{\text{th}}$
$\mathtt{b}$ after that is in block $m_{2}$. Thus in the blocks $m_{2}+1$ to
$n$ are less than $k-i-j$ $\mathtt{a}$. Let $r_{m_{1}}^{\prime}$ be the
$\mathtt{a}$ in the $m_{1}$${}^{\text{th}}$ block which don’t belong to
$\mathtt{a}^{i}$. Then $r_{m_{1}}^{\prime}+\dots+r_{m_{2}}$ contains more than
$k-j$ $\mathtt{a}$ since $k-j-i$ $\mathtt{a}$ occur in the
$m_{1}$’${}^{\text{th}}$ to the n${}^{\text{th}}$ block. Thus
$\mathtt{a}^{r_{m_{1}}^{\prime}}\mathtt{b}^{s_{m_{1}}}\dots\mathtt{a}^{r_{m_{2}}}\mathtt{b}^{s_{m_{2}}^{\prime}}$
is a scattered factor of length at least $k+1$ where $s_{m_{2}}^{\prime}$
describes the part of the $m_{2}$${}^{\text{th}}$ block until the
j${}^{\text{th}}$ $\mathtt{b}$. If $1<m_{1},m_{2}<n$ holds,
$\mathtt{b}\mathtt{a}^{k-j-1}\mathtt{b}^{j-2}$ is a scattered factor of $w$.
If $m_{1}=m_{2}=1$ holds, $\mathtt{a}^{k-j-3}\mathtt{b}\mathtt{a}\mathtt{b}$
is a scattered factor. If both are equal to $n$,
$\mathtt{b}\mathtt{a}^{k-j-1}\mathtt{b}^{j-2}$ is a scattered factor. In both
cases the last $\mathtt{b}$ exist even if $s_{m}=0$ holds, since the scattered
factor ends in the examined block $m_{2}$. If $m_{1}<m_{2}$ holds, there
exists a factor of length $>k$ which can be narrowed to a factor starting in
$\mathtt{a}$, ending in $\mathtt{b}$, and having at least one switch from
$\mathtt{b}$ back to $\mathtt{a}$ and back to $\mathtt{b}$. This concludes to
at least $(k-2)^{2}$ scattered factors of the form
$\mathtt{a}^{i}\mathtt{b}^{j}\mathtt{a}^{k-i-j}$ (or a different one in
exchange). By $k^{2}-k+3\geq 3k-3$ for $k\geq 5$ follows the claim.∎

By Lemmas 16 and 17 we are able to prove the following theorem, which shows
the second gap in the set of cardinalities of $\operatorname{ScatFact}_{k}$
for words in $\Sigma_{sb}^{2k}$.

###### Theorem 4.18

For $k\geq 5$ there does not exist a word $w\in\Sigma_{sb}^{2k}$ with
$k$-spectrum of cardinality $2k+i$ for $i\in[k-4]$. In other words, i.e.
between $2k+1$ and $3k-4$ is a cardinality-gap.

###### Proof

The Lemmas 3.2 and 4.15 show that exactly the words
$\mathtt{a}^{k}\mathtt{b}^{k}$,
$\mathtt{a}^{k-1},\mathtt{b}\mathtt{a}\mathtt{b}^{k-1}$, and
$\mathtt{a}^{k-1}\mathtt{b}^{k}$ $\mathtt{a}$ have $k$-spectra of cardinality
less than or equal to $2k$. By Lemma 16 and 17 follows that
$\mathtt{a}^{k-2}\mathtt{b}^{k}\mathtt{a}^{2}$ has a $k$-spectrum of
cardinality $3k-3$. Assume a
$w\in\Sigma_{sb}^{2k}\backslash\\{\mathtt{a}^{k}\mathtt{b}^{k},\mathtt{a}^{k-1}\mathtt{b}\mathtt{a}$
$\mathtt{b}^{k-1},\mathtt{a}^{k-1}\mathtt{b}^{k}\mathtt{a},\mathtt{a}^{k-2}\mathtt{b}^{k}\mathtt{a}^{2}\\}$.
Since renaming and reversal do not influence the cardinality, it can be
assumed w.l.o.g. that $w$ starts with $\mathtt{a}$. By assumption $w$ does not
start with $\mathtt{a}^{k}$. If $w$ starts with $\mathtt{a}^{k-1}$,
$w=\mathtt{a}^{k-1}\mathtt{b}^{i}\mathtt{a}\mathtt{b}^{k-i}$ follows with
$i\in[k-1]_{\geq 2}$ and by Lemma 16 the $k$-spectrum has $(i+1)k-4i+6\geq
3k-2>3k-4$ elements. By Lemma 17 the claim follows for words starting with
$(k-2)$ $\mathtt{a}$. and it is shown that words starting with at least two
and at most $k-3$ $\mathtt{a}$ lead to $k$-spectra of cardinality greater than
$3k-3$.∎

Going further, we analyse the larger possible cardinalities of
$\operatorname{ScatFact}_{k}$, trying to see what values are achievable (even
if only asymptotically, in some cases).

###### Corollary 19

All square numbers, greater or equal to four, occur as the cardinality of the
$k$-spectrum of a word $w\in\Sigma^{2k}_{sb}$; in particular
$|\operatorname{ScatFact}_{k}(\mathtt{a}^{\frac{k}{2}}\mathtt{b}^{k}\mathtt{a}^{\frac{k}{2}})|=\left(\frac{k}{2}+1\right)^{2}$
holds for $k$ even.

###### Proof

Apply Lemma 16 to $i=\frac{k}{2}$. This implies that the cardinality of the
$k$-spectrum of
$\mathtt{a}^{\frac{k}{2}}\mathtt{b}^{k}\mathtt{a}^{\frac{k}{2}}$ is

$\displaystyle
k\left(\frac{k}{2}+1\right)-\frac{k^{2}}{4}-1=\frac{1}{4}k^{2}+k-1=\left(\frac{k}{2}+1\right)^{2}.\squareforqed$

Inspired by the previous Corollary, we can show the following result
concerning the asymptotic behaviour of the cardinality of
$\operatorname{ScatFact}_{k}$ for words of length $2k$.

###### Proposition 20

Let $i>1$ be a fixed (constant) integer. Let $d=\lfloor\frac{k}{i}\rfloor$ and
$r=k-di$, and $d^{\prime}=\lfloor\frac{k}{i-1}\rfloor$ and
$r^{\prime}=k-d^{\prime}(i-1)$ . Then the following hold:

  * •

the word $\mathtt{a}^{r}\mathtt{b}^{r}(\mathtt{a}^{d}\mathtt{b}^{d})^{i}$ has
$\Theta(k^{2i-1})$ scattered factors of length $n$;

  * •

the word
$\mathtt{a}^{r}\mathtt{b}^{r^{\prime}}(\mathtt{a}^{d}\mathtt{b}^{d^{\prime}})^{i-1}\mathtt{a}^{d}$
has $\Theta(k^{2i-2})$ scattered factors of length $n$.

###### Proof

Let us first show the upper bounds. The following algorithm can be used to
find the scattered factors of length $k$ of
$\mathtt{a}^{r}\mathtt{b}^{r}(\mathtt{a}^{d}\mathtt{b}^{d})^{i}$. Choose $2$
numbers $q_{1}$ and $q_{2}$ from $[i]_{0}$, and $2i-1$ integers
$r_{1},\ldots,r_{2i-1}$ from $[d]_{0}$. Let
$r_{2i}=k-(q_{1}+q_{2}+\sum_{j\in[2i-1]}r_{j})$. If $r_{2i}\geq 0$ then the
word

$w^{\prime}=a^{q_{1}}b^{q_{2}}(a^{r_{1}}b^{r_{2}})(a^{r_{3}}b^{r_{4}})\cdots(a^{r_{2i-1}}b^{r_{2i}})$

is a scattered factor of
$\mathtt{a}^{r}\mathtt{b}^{r}(\mathtt{a}^{d}\mathtt{b}^{d})^{i}$, and all
scattered factors of length $k$ of this word have this form. From the
construction of $w^{\prime}$, because $d\leq\frac{k}{i}$, it follows that
there are at most $O(i^{2}k^{2i-1})$ possible ways to obtain it. As $i$ is
seen as a constant, this means that
$\mathtt{a}^{r}\mathtt{b}^{r}(\mathtt{a}^{d}\mathtt{b}^{d})^{i}$ has
$O(n^{2i-1})$ scattered factors of length $k$.

In the same way one can show that
$\mathtt{a}^{r}\mathtt{b}^{r^{\prime}}(\mathtt{a}^{d}\mathtt{b}^{d^{\prime}})^{i-1}\mathtt{a}^{d}$
has $O(n^{2i-2})$ scattered factors of length $n$.

Let us now show the lower bounds. We first consider the word
$\mathtt{a}^{r}\mathtt{b}^{r}(\mathtt{a}^{d}\mathtt{b}^{d})^{i}$. As $i$ is
constant, let us assume that $k>\frac{i(2i-1)}{i-1}$. Clearly,
$\frac{k(i-1)}{i(2i-1)}<\frac{k}{2i-1}\leq\frac{k}{i}-1\leq d\leq\frac{k}{i}$
and $d+r\geq\frac{k}{i}$. We generate scattered factors of the word
$\mathtt{a}^{r}\mathtt{b}^{r}(\mathtt{a}^{d}\mathtt{b}^{d})^{i}$ as follows.
We firstly choose $2i-1$ integers $r_{1},\ldots,r_{2i-1}$ between
$\frac{k(i-1)}{i(2i-1)}$ and $\frac{k}{2i-1}$. Under our assumptions, the word

$w^{\prime\prime}=b^{r_{1}}(a^{r_{2}}b^{r_{3}})\cdots(a^{r_{2i-2}}b^{r_{2i-1}})$

is a scattered factor of the suffix
$\mathtt{b}^{d}(\mathtt{a}^{d}\mathtt{b}^{d})^{i-1}$ of
$\mathtt{a}^{r}\mathtt{b}^{r}(\mathtt{a}^{d}\mathtt{b}^{d})^{i}$. Let
$r_{0}=k-\sum_{j\in[2i-1]}r_{j}$. We have $r_{0}\leq\frac{k}{i}\leq d+r$, so
$a^{r_{0}}w^{\prime\prime}$ is a scattered factor of
$\mathtt{a}^{r}(\mathtt{a}^{d}\mathtt{b}^{d})^{i}$, so also of
$\mathtt{a}^{r}\mathtt{b}^{r}(\mathtt{a}^{d}\mathtt{b}^{d})^{i}$. Moreover,
each choice of a tuple $(r_{1},\ldots,r_{2i-1})$ leads to a different
scattered factor of
$\mathtt{a}^{r}\mathtt{b}^{r}(\mathtt{a}^{d}\mathtt{b}^{d})^{i}$. The total
number of tuples we choose is

$\left(\frac{k}{2i-1}-\frac{k(i-1)}{i(2i-1)}\right)^{2i-1}=\left(\frac{k}{i(2i-1)}\right)^{2i-1}.$

So the total number of scattered factors of length $k$ of
$\mathtt{a}^{r}\mathtt{b}^{r}(\mathtt{a}^{d}\mathtt{b}^{d})^{i}$ is at least
$\left(\frac{k}{i(2i-1)}\right)^{2i-1}$. As the total number of scattered
factors of length $k$ of
$\mathtt{a}^{r}\mathtt{b}^{r}(\mathtt{a}^{d}\mathtt{b}^{d})^{i}$ is also
$O(k^{2i-1})$, we get that
$\mathtt{a}^{r}\mathtt{b}^{r}(\mathtt{a}^{d}\mathtt{b}^{d})^{i}$ has
$\Theta(k^{2i-1})$ scattered factors of length $k$.

The proof that
$\mathtt{a}^{r}\mathtt{b}^{r^{\prime}}(\mathtt{a}^{d}\mathtt{b}^{d^{\prime}})^{i-1}\mathtt{a}^{d}$
has $\Theta(n^{2i-2})$ scattered factors of length $k$ follows in a very
similar manner. ∎

###### Remark 21

Let $i$ be an integer, and consider $k$ another integer divisible by $i$.
Consider the word $w_{k}=(a^{\frac{k}{i}}b^{\frac{k}{i}})^{i}$. The exact
number of scattered factors of length $k$ of $w_{k}$ equals to the number
$C\left(k,2i,\frac{k}{i}\right)$ of weak $2i$-compositions of $k$, whose terms
are bounded by $\frac{k}{i}$, i.e., the number of ways in which $k$ can be
written as a sum $\sum_{j\in[2i]}r_{j}$ where
$r_{j}\in\left[\frac{k}{i}\right]_{0}$. From Lemma 20 we also get that this
number is $\Theta(n^{2k-1})$, but we also have:

$C\left(k,2i,\frac{k}{i}\right)=\sum_{0\leq
j<M}(-1)^{j}{{2i}\choose{j}}{{k+2i-j(\frac{k}{i}+1)-1}\choose{2i-1}},$

for $M=\frac{i(k+2i-1)}{k+i}.$ It is known that there exists a constant $E>0$
such that

$C\left(k,2i,\frac{k}{i}\right)\leq E\cdot\sum_{0\leq
j<M}(-1)^{j}{{2i}\choose{j}}\left(k+2i-j\left(\frac{k}{i}+1\right)-1\right)^{2i-1}.$

The coefficient of $k^{2i-1}$ in the right hand side of this inequality has to
be positive. Consequently $\sum_{0\leq
j<M}(-1)^{j}{{2i}\choose{j}}(i-j)^{2i-1}>0$. This seems to be an interesting
combinatorial inequality in itself.

One can also show as in Lemma 20 that the number of scattered factors of
length $k$ of $w_{k}$, which have, at their turn, $(ab)^{i}$ as a scattered
factor, is $\Theta(k^{2i-1})$. This number also equals the number
$C^{\prime}\left(k,2i,\frac{k}{i}\right)$ of $2i$-compositions of $k$ whose
terms are strictly positive integers upper bounded by $\frac{k}{i}$, i.e., the
number of ways in which $k$ can be written as a sum $\sum_{j\in[2i]}r_{j}$
where $r_{j}\in\left[\frac{k}{i}\right]$. Just as above, from this we get
$\sum_{0\leq j<i}(-1)^{j}{{2i}\choose{j}}(i-j)^{2i-1}>0$. Again, this
inequality seems interesting to us.∎

We will end this analysis with the conjecture that, in contrast to the first
gap, which always starts immediately after the first obtainable cardinality,
the last gap ends earlier the larger $k$ is. More precisely, if
$w=\mathtt{a}^{2}\mathtt{b}^{2}(\mathtt{a}\mathtt{b})^{k-3-i}\mathtt{b}\mathtt{a}(\mathtt{a}\mathtt{b})^{i}$
for $k\in\mathbb{N}_{\geq 4}$, $i\in[k-2]_{0}$ then
$|\operatorname{ScatFact}_{k}(w)|=2^{k}-2-i$.

At the end of this section, we will briefly introduce $\theta$-palindromes in
this specific setting. Let $\theta:\Sigma^{\ast}\rightarrow\Sigma^{\ast}$ be
an antimorphic involution, i.e. $\theta(uv)=\theta(v)\theta(u)$ and
$\theta^{2}$ is the identity on $\Sigma^{\ast}$. By
$\Sigma=\\{\mathtt{a},\mathtt{b}\\}$ only the identity and renaming are such
mappings. The fixed points of $\theta$ are called $\theta$-palindromes
($\mathtt{a}\mathtt{b}^{3}.\theta(\mathtt{b})^{3}\theta(\mathtt{a})$) and
exactly the words where $w^{R}=\overline{w}$ holds. They were studied in
different fields well (see e.g., [4], [7]). A word $w\in\Sigma_{sb}^{2k}$ is a
$\theta$-palindrome iff either
$w\in\\{\mathtt{a}w^{\prime}\mathtt{b},\mathtt{b}w^{\prime}\mathtt{a}\\}$ for
some $\theta$-palindrome $w^{\prime}\in\Sigma_{sb}^{2(k-1)}$ or additionally
$w=\mathtt{a}^{\frac{k}{2}}\mathtt{b}^{k}\mathtt{a}^{\frac{k}{2}}$ in the case
that $k$ is even. Two cardinality results for $\theta$-palindromes are
presented in Lemma 16 and Corollary 19. We believe that persuing the
$k$-spectra of $\theta$-palindromes may lead to a deeper insight of which
cardinalities can be reached, but due to space restrictions we will only
mention one conjecture here, which may already show that cardinalities are
somehow propagating for $\theta$-palindromes. Notice that this conjecture
implies that indeed similar to the second gap here $4k-4$ is always reached
but that in contrast to the second gap, the third gap is not of the form
$4k-4-i$ for $i\in[k-4]$. (see Figure 2).

###### Conjecture 22

The $k$-spectrum of $w=\mathtt{a}\mathtt{b}^{k-1}\mathtt{a}^{k-1}\mathtt{b}$
has $4(k-1)$ elements and moreover if $w^{\prime}=w^{R}$ with a $k$-spectrum
of cardinality $\ell\in\mathbb{N}_{\geq 12}$ then the scattered factor set of
$\mathtt{a}w\mathtt{b}$ has cardinality $2\frac{1}{4}\ell-5$.

##  5 Reconstructing Strictly Balanced Words from their $k$-Spectra

In the final section we consider the slightly different problem of
reconstructing a word from its scattered factors, or more specifically in this
case, k-spectra. More generally, we are interested in how much information
about a (strictly balanced) word $w$ is contained in its scattered factors,
and more precisely, which scattered factors are, respectively, are not
necessary or useful for reconstructing the word $w$, or distinguishing it from
others. Since $w$ is a scattered factor of itself, it is trivial that the
scattered factor of length $|w|$ is sufficient to uniquely reconstruct $w$. On
the other hand, all words over $\\{a,b\\}^{*}$ containing both letters will
have the same $1$-spectrum. Thus we see that the length of the scattered
factors of a word $w$plays a role in how much information about $w$ they
contain. This relationship is described more precisely by the following result
of Dress and Erdös [2] along with the fact that (cf. e.g. Proposition 5) a
word of length $2k$ is not uniquely determined by its scattered factors of
length $k$.

######  Proposition 23 (Dress and Erdös [2])

If
$\operatorname{ScatFact}_{k+1}(w)=\operatorname{ScatFact}_{k+1}(w^{\prime})$
holds for $w,w^{\prime}\in\Sigma^{\leq 2k}$ then $w=w^{\prime}$ follows.

Proof of Proposition 23 in the case that $w$, $w^{\prime}$ are strictly
balanced.

###### Proof

We give a procedure for uniquely reconstructing $w$ from
$\operatorname{ScatFact}_{k}{w}$. For all $i,j\in\mathbb{N}_{0}$ such that
$i+j=k$, ask whether
$\mathtt{a}^{i}\mathtt{b}\mathtt{a}^{j}\in\operatorname{ScatFact}_{k}{w}$.
Since there are exactly $i+j$ occurrences of $\mathtt{a}$ in $w$, all are
accounted for in the (potential) scattered factor
$\mathtt{a}^{i}\mathtt{b}\mathtt{a}^{j}$, and thus the answer is ‘yes’ if and
only if there are one or more $\mathtt{b}$s between the $i$th and $i+1$th
occurrences of $\mathtt{a}$ in $w$. Hence after these queries, we know exactly
which $\mathtt{a}$s are consecutive (i.e. do not have a $\mathtt{b}$ between
them) in $w$. Similarly we ask for all $i,j\in\mathbb{N}_{0}$ such that
$i+j=k$, ask whether
$\mathtt{b}^{i}\mathtt{a}\mathtt{b}^{j}\in\operatorname{ScatFact}_{k}{w}$. By
symmetry, this tells us exactly which $\mathtt{b}$s are consecutive. This is
sufficient information to specify $w$ completely.∎

In the proof of Proposition 23, a pivotal role is played by particularly
unbalanced scattered factors, which contain many $\mathtt{a}$’s and a few
$\mathtt{b}$’s or vice-versa. The question arises as to whether this is due to
the fact that these unbalanced scattered factors contain inherently more
information about the structure of the whole word than the strictly balanced
ones? In the general case, the answer is, sometimes at least, yes: we cannot
distinguish between e.g. two words in $\\{a\\}^{*}$ by their strictly balanced
scattered factors, as the only such factor is $\epsilon$. The same problem
arises for all words which are sufficiently unbalanced. However, if in
addition we consider only strictly balanced words $w$, then the situation
changes. We conjecture that in fact, for strictly balanced words $w$, the
strictly balanced scattered factors are just as informative about the $w$ as
the unbalanced ones. More formally, we believe the following adaptation of
Proposition 23 holds:

###### Conjecture 24

Let $k\in\mathbb{N}$. Let $k^{\prime}=k+1$ for odd $k$, and $k^{\prime}=k+2$
for even $k$. Let $w,w^{\prime}\in\Sigma_{sb}^{2k}$ such that
$\operatorname{ScatFact}_{k^{\prime}}(w)\cap\Sigma^{k^{\prime}}_{sb}=\operatorname{ScatFact}_{k^{\prime}}(w^{\prime})\cap\Sigma^{k^{\prime}}_{sb}$.
Then $w=w^{\prime}$.

While we do not resolve the conjecture, we give an example of a subclass of
words for which it holds true, namely when there are at most two ‘blocks’ of
$\mathtt{b}$’s (and therefore by symmetry if there are at most two ‘blocks’ of
$\mathtt{a}$’s).

###### Proposition 25

Let $k\in\mathbb{N}$. If $k$ is odd, then each word
$w\in\mathtt{a}^{*}\mathtt{b}^{*}\mathtt{a}^{*}\mathtt{b}^{*}\mathtt{a}^{*}\cap\Sigma_{sb}^{2k}$
is uniquely determined by the set
$\operatorname{ScatFact}_{k+1}(w)\cap\Sigma_{sb}^{k+1}$. Similarly, if $k$ is
even, then each word
$w\in\mathtt{a}^{*}\mathtt{b}^{*}\mathtt{a}^{*}\mathtt{b}^{*}\mathtt{a}^{*}\cap\Sigma_{sb}^{2k}$
is uniquely determined by the set
$\operatorname{ScatFact}_{k+2}(w)\cap\Sigma_{sb}^{k+2}$.

###### Proof

As in the proof of Proposition 23, we give an algorithm for uniquely
reconstructing $w$. W.l.o.g., let $k$ be odd. The case that $k$ is even is
easily adapted. Let
$w=\mathtt{a}^{i}\mathtt{b}^{j}\mathtt{a}^{\ell}\mathtt{b}^{k-j}\mathtt{a}^{k-i-\ell}$
and let $S=\operatorname{ScatFact}_{k+1}(w)\cap\Sigma^{*}_{sb}$. Firstly, we
shall deal with the case that $\ell=0$. Note that we can decide whether
$\ell=0$ by querying whether there exists a scattered factor $u\in S$ such
that
$u\in\mathtt{a}^{*}\mathtt{b}^{+}\mathtt{a}^{+}\mathtt{b}^{+}\mathtt{a}^{*}$.
Now, if $\ell=0$, we have $w=\mathtt{a}^{i}\mathtt{b}^{k}\mathtt{a}^{k-i}$.
Since $k$ is odd, exactly one of $i,k-i$ will be at most $\frac{k-1}{2}$. We
can decide which one by querying whether
$\mathtt{a}^{\frac{k+1}{2}}\mathtt{b}^{\frac{k+1}{2}}\in S$. W.l.og., suppose
$i\leq{\frac{k-1}{2}}$ (so the query returns “no”). The other case is
symmetric. Then note that
$\mathtt{a}^{i}\mathtt{b}^{\frac{k+1}{2}}\mathtt{a}^{\frac{k+1}{2}-i}\in S$
but
$\mathtt{a}^{i+1}\mathtt{b}^{\frac{k+1}{2}}\mathtt{a}^{\frac{k+1}{2}-i-1}\notin
S$. Thus the exact value of $i$ (and therefore $k-i$) can be inferred directly
from observing scattered factors of this form in $S$.

Now consider the the case that $\ell\not=0$. Note that there exists
$u\in\mathtt{b}^{+}\mathtt{a}^{\frac{k+1}{2}}\mathtt{b}^{+}\cap S$ if and only
if $\ell\geq\frac{k+1}{2}$. Suppose firstly that $\ell\geq\frac{k+1}{2}$. Then
$i+(k-i-\ell)\leq\frac{k-1}{2}$. Thus we can determine $i$ and $(k-i-\ell)$
(and therefore $\ell$) by looking for the maximum $m_{1},m_{2}$ such that
there exists
$u\in\mathtt{a}^{m_{1}}\mathtt{b}^{+}\mathtt{a}^{+}\mathtt{b}^{+}\mathtt{a}^{m_{2}}$
with $u\in S$ ($i$ is the maximum $m_{1}$ while $k-i-\ell$ is the maximum
$m_{2}$). Moreover, exactly one of $j,k-j$ will be less than $\frac{k+1}{2}$.
We can decide which one by querying whether
$\mathtt{a}^{\frac{k+1}{2}}\mathtt{b}^{\frac{k+1}{2}}\in S$. If so, it must be
that $k-j\geq{\frac{k+1}{2}}$. Suppose that this is the case (the other case
is symmetric). Then as before, we can determine the exact value of $j$ by
looking at the scattered factors of the form
$\mathtt{b}^{m}\mathtt{a}^{+}\mathtt{b}^{+}\mathtt{a}^{*}$ (i.e., $j$ is the
maximum $m$) and we are done.

Finally, we consider the case that $0<\ell<{\frac{k+1}{2}}$. Then $\ell$ can
be uniquely determined as the maximum $m$ such that there exists
$u\in\mathtt{a}^{*}\mathtt{b}^{+}\mathtt{a}^{m}\mathtt{b}^{+}\mathtt{a}^{*}$
with $u\in S$. In order to determine $i$ (or equivalently $k-i-\ell$), we look
for the maximum $m_{1},m_{2}$ such that there exist
$u_{1}\in\mathtt{a}^{m_{1}}\mathtt{b}^{+}\mathtt{a}^{+}\mathtt{b}^{+}\mathtt{a}^{*}$
and
$u_{2}\in\mathtt{a}^{*}\mathtt{b}^{+}\mathtt{a}^{+}\mathtt{b}^{+}\mathtt{a}^{m_{2}}$
with $u_{1},u_{2}\in S$. In particular at least one of $m_{1},m_{2}$ must be
strictly less than $\frac{k-1}{2}$. If $m_{1}<\frac{k-1}{2}$, then $j=m_{1}$
and if $m_{2}<{\frac{k-1}{2}}$ then $k-\ell-i=m_{2}$. In either case, since
$\ell$ is already known, this uniquely determines both $i$ and $k-i-\ell$.

It remains to determine $j$ (or equivalently $k-j$). Recall that exactly one
of $j,k-j$ will be less than $\frac{k+1}{2}$. Let $m_{1}$ be the maximum $m$
such that there exists
$u\in\mathtt{a}^{*}\mathtt{b}^{m}\mathtt{a}^{+}\mathtt{b}^{+}\mathtt{a}^{*}$
with $u\in S$ and let $m_{2}$ be the maximum $m$ such that there exists
$u\in\mathtt{a}^{*}\mathtt{b}^{+}\mathtt{a}^{+}\mathtt{b}^{m}\mathtt{a}^{*}$
with $u\in S$. Note that $m_{1},m_{2}\leq\frac{k-1}{2}$. If
$m_{1}<\frac{k-1}{2}$ (resp. $m_{2}<\frac{k-1}{2}$), then $j=m_{1}$ (resp
$k-j=m_{2}$), and thus $j$ and $j-k$ can be inferred. If
$m_{1}=m_{2}=\frac{k-1}{2}$, then either $j=\frac{k-1}{2}$ or
$k-j=\frac{k-1}{2}$. Now, if $k-i-\ell<\frac{k+1}{2}$, there exists
$u\in\mathtt{a}^{*}\mathtt{b}^{\frac{k+1}{2}}\mathtt{a}^{+}\mathtt{a}^{k-i-\ell}$
with $u\in S$ if and only if $j=\frac{k+1}{2}$ (in which case
$k-j=\frac{k-1}{2}$). On the other hand, if $k-i-\ell\geq\frac{k+1}{2}$, then
$i<\frac{k+1}{2}$ and there exists
$u\in\mathtt{a}^{i}\mathtt{a}^{+}\mathtt{b}^{\frac{k+1}{2}}\mathtt{a}^{*}$
with $u\in S$ if and only if $k-j=\frac{k+1}{2}$ (in which case
$j=\frac{k-1}{2}$). In either case, all exponents are known and we have
uniquely reconstructed $w$.∎

The difficulty in proving Conjecture 24 seems to arise from the fact that, for
different pairs of words $w,w’\in\Sigma_{sb}$, the set of scattered factors
which distinguish them, namely the symmetric difference of
$\operatorname{ScatFact}_{k}(w)\cap\Sigma^{k}_{sb}$ and
$\operatorname{ScatFact}_{k}(w)\cap\Sigma^{k}_{sb}$ (for appropriate $k$),
varies considerably, unlike with the proof(s) of Proposition 23, where the set
of distinguishing scattered factors is always made up words of the same form,
regardless of the choice of $w$ and $w’$. As an example, consider the words
$w=\mathtt{a}\mathtt{b}\mathtt{a}\mathtt{b}\mathtt{a}\mathtt{b}$,
$w^{\prime}=\mathtt{b}\mathtt{a}\mathtt{b}\mathtt{a}\mathtt{b}\mathtt{a}$, and
$w^{\prime\prime}=\mathtt{a}\mathtt{b}\mathtt{a}\mathtt{b}\mathtt{b}\mathtt{a}$.
Then the symmetric difference of
$\operatorname{ScatFact}_{4}(w)\cap\Sigma_{sb}^{4}$ and
$\operatorname{ScatFact}_{4}(w^{\prime})\cap\Sigma_{sb}^{4}$ is
$\\{\mathtt{a}\mathtt{a}\mathtt{b}\mathtt{b},\mathtt{b}\mathtt{b}\mathtt{a}\mathtt{a}\\}$.
On the other hand, considering
$\operatorname{ScatFact}_{4}(w^{\prime})\cap\Sigma_{sb}^{4}$ and
$\operatorname{ScatFact}_{4}(w^{\prime\prime})\cap\Sigma_{sb}^{4}$, the
symmetric difference is $\\{\mathtt{b}\mathtt{a}\mathtt{a}\mathtt{b}\\}$.

##  6 Conclusions

We have considered properties of $k$-spectra of strictly balanced words. In
particular, in Section 3 we give several insights into the structure of the
set of all $k$-spectra of strictly balanced words of length $2k$ by
considering for which numbers $n$ there exists $w$ such that the $k$-spectrum
of $w$ has cardinality $n$. In particular, we characterise the first two gaps
in the possibilities for each $k$ which are regular (in the sense that the
first and second gaps are always from $k+2$ to $2k-1$ and $2k+1$ to $3k-4$
(inclusive). On the other hand, we see that the third gap is considerably less
regular and thus resists a natural characterisation.

In Section 4, we consider the task of reconstructing strictly balanced words
from their $k$-spectra. We note that this is, in a sense, as hard as in the
general case, however, we also conjecture that even if we consider only the
scattered factors which are also strictly balanced, then the situation remains
the same, in the sense that it can be achieved for the same choices of $k$.
Resolving this conjecture appears to require some new approach however since
the techniques for the general case are not easily adapted.

As mentioned at the end of Section 3 some of the strictly balanced words are
$\theta$-palindromes. Since the $\theta$-palindromes of length $2k$ are
constructible from the ones of length $2(k-1)$ (except for each even $k$
exactly one $\theta$-palindrome) we surmised that the structure and properties
propagate. Moreover we expected that the knowledge of the word’s second half
helps in finding the cardinalities of the $k$-spectra. Nevertheless we were
only able to get results for $\theta$-palindromes in the same manner as for
the other words, but we still believe that the structure of the
$\theta$-palindromes can reveal more insights with further work.

Figure 2: On the left hand side the lower part of possible cardinalities is
shown. The numbers surrounded by the thicker borders are proven in the paper,
the others are calculated by a computer program. The both grey areas are the
first and the second gap. On the right hand side the upper part is shown,
where the grey area is a conjecture. There the line indicates a jump of
unknowns and then the first (again as a result of a computer program) and the
last missing number is given. In both figures grey numbers indicate that there
is not a $k$-spectrum of this cardinality and the black ones are reached.

## References

  * [1] J. Berstel and J. Karhumäki.  Combinatorics on words – A tutorial.  BEATCS: Bulletin of the European Association for Theoretical Computer Science, 79, 2003.
  * [2] A. W.M. Dress and P. Erdös.  Reconstructing words from subwords in linear time.  Annals of Combinatorics, 8(4):457–462, 2004.
  * [3] Cees H. Elzinga, Sven Rahmann, and Hui Wang.  Algorithms for subsequence combinatorics.  Theor. Comput. Sci., 409(3):394–404, 2008.
  * [4] S. Z. Fazekas, F. Manea, R. Mercas, and K. Shikishima-Tsuji.  The pseudopalindromic completion of regular languages.  Information and Compution, 239:222–236, 2014.
  * [5] Simon Halfon, Philippe Schnoebelen, and Georg Zetzsche.  Decidability, complexity, and expressiveness of first-order logic over the subword ordering.  In Proc. LICS 2017, pages 1–12, 2017.
  * [6] Š. Holub and K. Saari.  On highly palindromic words.  Descrete Applied Mathematics, 157:953–959, 2009.
  * [7] L. Kari and K. Mahalingam.  Watson-crick palindromes in dna computing.  Natural Computing, 9(2):297–316, 2010.
  * [8] M. Lothaire.  Combinatorics on Words.  Cambridge University Press, 1997.
  * [9] J. Manǔch.  Characterization of a word by its subwords.  In Developments in Language Theory, pages 210–219. World Scientific, 1999.
  * [10] A. Mateescu, A. Salomaa, and S. Yu.  Subword histories and parikh matrices.  Journal of Computer and System Sciences, 68(1):1–21, 2004.
  * [11] G. Rozenberg and A. Salomaa, editors.  Handbook of Formal Languages (3 volumes).  Springer, 1997.
  * [12] A. Salomaa.  Connections between subwords and certain matrix mappings.  Theoretical Computer Science, 340(2):188–203, 2005.
  * [13] Georg Zetzsche.  The complexity of downward closure comparisons.  In Proc. ICALP 2016, volume 55 of LIPIcs, pages 123:1–123:14, 2016.