# Two-dimensional Fibonacci Words: Tandem Repeats and Factor Complexity

Sivasankar M<EMAIL_ADDRESS>Rama R<EMAIL_ADDRESS>Department of
Mathematics, Indian Institute of Technology Madras, Chennai, India

###### Abstract

If $x$ is a non-empty string then the repetition $xx$ is called a tandem
repeat. Similarly, a tandem in a two dimensional array $X$ is a configuration
consisting of a same primitive block $W$ that touch each other with one side
or corner. In [1], Apostolico and Brimkov have proved various bounds for the
number of tandems in a two dimensional word of size $m\times n$. Of the two
types of tandems considered therein, they also proved that, for one type, the
number of occurrences in an $m\times n$ Fibonacci array attained the general
upper bound, $\mathcal{O}(m^{2}n\hskip 2.84544pt\mbox{log}\hskip 2.84544ptn)$.
In this paper, we derive an expression for the exact number of tandems in a
given finite Fibonacci array $f_{m,n}$. As a required result, we derive the
factor complexities of $f_{m,n}$, $m,n\geq 0$ and that of the infinite
Fibonacci word $f_{\infty,\infty}$. Generations of $f_{\infty,\infty}$ and
$f_{m,n}$, for any given $m,n\geq 1$ using a two-dimensional homomorphism is
also achieved.

###### keywords:

Fibonacci Words , Fibonacci Arrays , Tandems , Two-dimensional Factor
Complexity , Two-dimensional Morphic Words

###### MSC:

[2020] 68R15 , 68Q45

##  1 Introduction

The field of combinatorics of words produces many path breaking results which
are directly used in computer science, molecular biology and particle physics.
To be more specific, we can mention pattern recognition, image processing
techniques in computer science, DNA computing in molecular biology and
crystallography in physics [2, 3, 4]. In these research directions, similar to
palindromes, another interesting and important structure is repetitive
substrings. If $x$ is a non-empty string then the repetition $xx$ is called a
tandem repeat or a square. Axel and Thue’s work on square free words and
avoidable patterns, provided more insights in to tandems [5]. In DNAs, when a
pattern of one or more nucleotides is repeated, with the repetitions directly
adjacent to each other, we say a tandem has occurred. More information about
tandem repeats can help in determining inherited traits of an individual and
are useful in genealogical DNA tests. The capacity and expressiveness of
genomic tandem duplication is explored in [6]. In computer science
engineering, tandem repeats are used in compression algorithms [7].

A natural extension of one dimensional (hereafter, sometimes denoted by $1D$)
words is to two dimensions. A two dimensional (hereafter, sometimes denoted by
$2D$) word of size $m\times n$ is a rectangular arrangement of symbols from an
alphabet, in $m$ rows and $n$ columns. A tandem in a two dimensional array $X$
is a configuration consisting of a same primitive block $W$ that touch each
other with one side or corner. Basically, tandem repeats in one dimensional
strings are detected using suffix trees [8, 9]. It is natural to expect more
amount of work (compared to the one dimensional setup) to detect a tandem in
two dimensions. Algorithms to locate periods,palindromes, runs etc. also
become more complex in a multi dimensional setup [10, 11, 12, 13].

In [1],the authors have proved various bounds for the number of tandems in a
two dimensional word of size $m\times n$. In fact they have considered two
types of tandems. They have introduced a sequence of $2D$ words called $2D$
Fibonacci arrays and proved that the number of occurrences of one of the
tandem type attains the general upper bound of $\mathcal{O}(m^{2}n\hskip
2.84544pt\mbox{log}\hskip 2.84544ptn)$ in an $m\times n$ Fibonacci array. Like
Fibonacci numbers, Fibonacci words/arrays are very exciting. For a detailed
study of Fibonacci words [14, 15] can be referred. Continuing the work done in
[1] on Fibonacci arrays, we count the exact number of tandems in a given
Fibonacci array $f_{m,n}$.

The main contributions of this paper are:

  * -

The exact number of tandems occurring (with repetition and without repetition)
in a given $f_{m,n}$ are counted.

  * -

Factor complexity of finite Fibonacci words are obtained.

  * -

A two dimensional morphism generating the 2D infinite Fibonacci word
$f_{\infty,\infty}$ is developed.

  * -

A Deterministic Finite state Automaton with Output (DFAO) is constructed for
$f_{\infty,\infty}$.

This paper is organised as follows. Section 2 has the prerequisites for
understanding the later sections. Section 3 explains the types of tandems that
occur in a $2D$ word. Section 4 counts the number of Tandems (repetitions
included) in a given $f_{m,n}$. In Section 5 we find the factor complexity of
the one-dimensional Fibonacci word $f_{n}$ which is used in Section 6 to find
the number of distinct tandems in $f_{m,n}$. In Section 7 the $2D$ morphism
generating $f_{\infty,\infty}$ is developed. In Section 8 the factor
complexities of $f_{m,n}$ and $f_{\infty,\infty}$ are found out. Section 9
discusses the DFAO generating $f_{\infty,\infty}$.

##  2 Preliminaries

###  2.1 Words Over an Alphabet

A finite non-empty set of symbols is called an alphabet and is denoted by
$\Sigma$. A word $w=x_{1}x_{2}\cdots x_{n}$ of length $n$, is the
juxtaposition (familiarly known as concatenation) of symbols
$x_{1},x_{2},\ldots,x_{n}$ taken from $\Sigma$. The length of the word $w$,
that is the number of symbols in $w$, is denoted by $|w|$. The set of all
words over $\Sigma$ including the empty word $\lambda$, is denoted by
$\Sigma^{*}$, whereas $\Sigma^{+}$ denotes the set of all non-empty words over
$\Sigma$. In fact, $\Sigma^{*}$ is a free monoid under the operation
concatenation. A word $x\in\Sigma^{*}$ is a factor of another word
$w\in\Sigma^{*}$ if $w=uxv$ for some $u,v\in\Sigma^{*}$. A word
$x\in\Sigma^{*}$ is a prefix (suffix, respectively) of the word $w$ if $w=xy$
($w=yx$, respectively) for some $y\in\Sigma^{*}$. The reversal of
$w=x_{1}x_{2}\cdots x_{n}$ is defined to be the string $w^{R}=x_{n}\cdots
x_{2}x_{1}$. A word $w$ is said to be a palindrome or a one-dimensional
palindrome if $w=w^{R}$. Powers $w^{k}$, $k\geq 0$ of a word $w$ are obtained
by concatenating $w$ with itself, $k$ number of times. A word $w$ is said to
be primitive if $w=u^{n}$ implies $n=1$ and $w=u$. A square in a word $w$ is a
subword of $w$, which is of the form $xx$, $x\in\Sigma^{+}$. For a more
elaborate study of formal language theory and combinatorics on words, the
reader is referred to [16, 17].

###  2.2 Two-dimensional Words

A subset of $\Sigma^{*}$ is called a language. Studying the type and the
grammar of the words in a language constitute the formal language theory where
as analysing number of squares, palindromes etc. is combinatorics on words.
Extending formal language theory and combinatorics of words to two dimensions
is a challenging task. The difficulty arises due to the presence of two
directions. Below a short introduction to two-dimensional languages is given.
Interested reader can refer [18] for further concepts.

######  Definition 1.

[18] Let $\Sigma$ be an alphabet. An array $($also called a picture or two-
dimensional word$)$ $u=[u_{i,j}]_{1\leq i\leq m,1\leq j\leq n}$ of size
$(m,n)$ over $\Sigma$ is a two-dimensional rectangular finite arrangement of
letters:

$u=\begin{matrix}u_{1,1}&u_{1,2}&\cdots&u_{1,n-1}&u_{1,n}\\\
u_{2,1}&u_{2,2}&\cdots&u_{2,n-1}&u_{2,n}\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
u_{m-1,1}&u_{m-1,2}&\cdots&u_{m-1,n-1}&u_{m-1,n}\\\
u_{m,1}&u_{m,2}&\cdots&u_{m,n-1}&u_{m,n}\\\ \end{matrix}$

The number of rows and columns of $u$ are denoted, respectively, by
$|u|_{\text{row}}$ and $|u|_{\text{col}}$. The array of size $(0,0)$ denoted
by $\Lambda$ is the empty array. The arrays of sizes $(m,0)$ and $(0,m)$ for
$m>0$ are not defined. It is noted that some authors consider these arrays
also as the empty array. The set of all arrays over $\Sigma$ including the
empty array, $\Lambda$, is denoted by $\Sigma^{**}$, whereas $\Sigma^{++}$ is
the set of all non-empty arrays over $\Sigma$.

To locate any position or region in an array, we require a reference system
[19]. Given an array $u$, the set of coordinates
$\\{1,2,\ldots,|u|_{\text{row}}\\}\times\\{1,2,\ldots,|u|_{\text{col}}\\}$ is
referred to as the domain of $u$. We also use t, b, l, r (the initials of the
words top, bottom, left, right, respectively) to detect the sides or
boundaries of $u$. A subdomain or subarray of an array $u$, denoted by
$u[(i,j),(i^{\prime},j^{\prime})]$, is the portion of $u$ located in the
region $\\{i,i+1,\ldots,i^{\prime}\\}\times\\{j,j+1,\ldots,j^{\prime}\\}$,
where $1\leq i\leq|u|_{\text{row}},1\leq j\leq|u|_{\text{col}}$. Below we
state the concatenation operation between two arrays and further definitions
associated with 2D arrays.

######  Definition 2.

[18] Let $u,v$ be arrays over $\Sigma$, of sizes $(m_{1},n_{1})$ and
$(m_{2},n_{2})$, respectively with $m_{1},n_{1},m_{2},n_{2}>0$. Then,

  1. 1.

The column concatenation of $u$ and $v$, denoted by $\obar$, is a partial
operation, defined if $m_{1}=m_{2}=m$, and is given by

$u\obar
v=\begin{matrix}u_{1,1}&\cdots&u_{1,n_{1}}&v_{1,1}&\cdots&v_{1,n_{2}}\\\
\vdots&&\vdots&\vdots&&\vdots\\\
u_{m,1}&\cdots&u_{m,n_{1}}&v_{m,1}&\cdots&v_{m,n_{2}}\end{matrix}$

  2. 2.

The row concatenation of $u$ and $v$, denoted by $\ominus$, is a partial
operation, defined if $n_{1}=n_{2}=n$, and is given by

$u\ominus v=\begin{matrix}u_{1,1}&\cdots&u_{1,n}\\\ \vdots&&\vdots\\\
u_{m_{1},1}&\cdots&u_{m_{1},n}\\\ v_{1,1}&\cdots&v_{1,n}\\\ \vdots&&\vdots\\\
v_{m_{2},1}&\cdots&v_{m_{2},n}\end{matrix}$

Note that, the operations of column and row concatenations are associative but
not commutative and $\Lambda$ is the neutral element for both the operations.

With these operations defined, the definitions of a subword, prefix, primitive
word and palindromes follow.

######  Definition 3.

[20] Given $u\in\Sigma^{**}$, $v\in\Sigma^{**}$ is said to be a subword
(respectively, proper subword) of $u$, denoted by $v\leq_{sw}u$ (respectively
$v<_{sw}u)$ if $u=x\obar(x^{\prime}\ominus v\ominus y^{\prime})\obar y$ or
$u=x\ominus(x^{\prime}\obar v\obar y^{\prime})\ominus y$ for some
$x,x^{\prime},y,y^{\prime}\in\Sigma^{**}$ (respectively if any of
$x,x^{\prime},y,y^{\prime}$ are non-empty).

######  Definition 4.

[20] Let $u\in\Sigma^{**}$. An array $v\in\Sigma^{**}$ is said to be a prefix
of $u$ $($suffix of $u$, respectively$)$, denoted by $v\leq_{p}^{2d}u$
$(v\leq_{s}^{2d}u$, respectively$)$ if $u=(v\ominus x)\obar y$
$(u=y\obar(x\ominus v)$, respectively$)$ for some $x,y\in\Sigma^{**}$.
Furthermore, $v$ is said to be a proper prefix of $u$ $($proper suffix of $u$,
respectively$)$ denoted by $v<_{p}^{2d}u$ $(v<_{s}^{2d}u$, respectively$)$ if
either $x\neq\Lambda$ or $y\neq\Lambda$, or both $x,y\in\Sigma^{++}$.

######  Definition 5.

[21] If $x\in\Sigma^{++}$, then by $(x^{k_{1}\obar})^{k_{2}\ominus}$ we mean
that the array is constructed by repeating $x$, $k_{1}$ times column-wise to
get $x^{k_{1}\obar}$, and repeating $x^{k_{1}\obar}$, $k_{2}$ times row-wise.
An array $w\in\Sigma^{++}$ is said to be 2D primitive if
$w=(x^{k_{1}\obar})^{k_{2}\ominus}$ implies that $k_{1}k_{2}=1$ and $w=x$.

By $Q_{2d}$, let us denote the set of all 2D primitive arrays. Also, if
$w=(x^{k_{1}\obar})^{k_{2}\ominus}$ and $x$ is 2D primitive, then $x$ is said
to be a 2D-primitive root of $w$ denoted by $\rho_{2d}(w)$. Note that
2D-primitive root is always unique for a given array.

######  Definition 6.

[22] Let $u=[u_{i,j}]_{1\leq i\leq m,1\leq j\leq n}$ be an array of size
$(m,n)$. The reverse image of $u$, denoted by $u^{R}$ is
$[u_{m-i+1,n-j+1}]_{1\leq i\leq m,1\leq j\leq n}$. Furthermore, if $u$ is
equal to its reverse image $u^{R}$, then $u$ is said to be a two-dimensional
palindrome. By $P_{2d}$, we denote the set of all 2D palindromes in
$\Sigma^{**}$.

Just for completion, recall that the transpose of $u=[u_{i,j}]_{1\leq i\leq
m,1\leq j\leq n}$, denoted by $u^{T}$ is defined as:

$\displaystyle u^{T}=(u_{1,1}\obar u_{2,1}\obar\cdots\obar
u_{m,1})\ominus\cdots\ominus(u_{1,n}\obar u_{2,n}\obar\cdots\obar u_{m,n}).$

###  2.3 Two-dimensional Fibonacci Words

We are familiar with the Fibonacci numerical sequence $F(n)$ is defined
recursively as $F(0)=1$, $F(1)=1$, $F(n)=F(n-1)+F(n-2)$ for $n\geq 2$.
Similarly, the sequence $\\{f_{n}\\}_{n\geq 0}$ of Fibonacci words over
$\Sigma=\\{a,b\\}$, is defined recursively by $f_{0}=a$, $f_{1}=b$,
$f_{n}=f_{n-1}f_{n-2}$ for $n\geq 2$ . Note that the Fibonacci words are
always defined over the binary alphabet and $|f_{n}|=F(n)$ for $n\geq 0$.

The 2D extension to Fibonacci arrays is defined in [1], as below.

######  Definition 7.

[1] Let $\Sigma=\\{a,b,c,d\\}$. The sequence of Fibonacci arrays,
$\\{f_{m,n}\\}_{m,n\geq 0}$, is defined as:

  1. 1.

$f_{0,0}=\beta,f_{0,1}=\gamma,f_{1,0}=\delta,f_{1,1}=\alpha$ where
$\alpha,\beta,\gamma$ and $\delta$ are symbols from $\Sigma$ with some but not
all, among $\alpha,\beta,\gamma$ and $\delta$ might be identical.

  2. 2.

For $k\geq 0$ and $m,n\geq 1$,

$f_{k,n+1}=f_{k,n}\obar f_{k,n-1},\hskip 5.69046ptf_{m+1,k}=f_{m,k}\ominus
f_{m-1,k}.$

For convenience, throughout this paper we fix
$f_{0,0}=a,f_{0,1}=b,f_{1,0}=c,f_{1,1}=d$, where some but not all of $a,b,c$
and $d$ might be identical. Let us call $f_{k,n+1}=f_{k,n}\obar f_{k,n-1}$ as
column-wise expansion and $f_{m+1,k}=f_{m,k}\ominus f_{m-1,k}$ as row-wise
expansion. Example 1 explains the construction of $f_{2,3}$ in two ways. In
the first way, row-wise expansions precede column-wise expansions and in the
second way column-wise expansions precede row-wise expansions.

######  Example 1.

Let $\Sigma=\\{a,b,c,d\\}$. Then,

$\displaystyle f_{2,3}=f_{1,3}\ominus f_{0,3}$ $\displaystyle=(f_{1,2}\obar
f_{1,1})\ominus(f_{0,2}\obar f_{0,1})$ $\displaystyle=(f_{1,1}\obar
f_{1,0}\obar f_{1,1})\ominus(f_{0,1}\obar f_{0,0}\obar f_{0,1}).$

Or,

$\displaystyle f_{2,3}=f_{2,2}\obar f_{2,1}$ $\displaystyle=f_{2,1}\obar
f_{2,0}\obar f_{2,1}$ $\displaystyle=(f_{1,1}\ominus
f_{0,1})\obar(f_{1,0}\ominus f_{0,0})\obar(f_{1,1}\ominus f_{0,1}).$

Since, $f_{0,0}=a,f_{0,1}=b,f_{1,0}=c,f_{1,1}=d$, $f_{2,3}$ we can write,

$\displaystyle f_{2,3}=\begin{matrix}d&c&d\\\ b&a&b\end{matrix}$

We state here some required properties of $f_{m,n}$.

######  Lemma 1.

[20] Let $f_{m,n},(m,n=0,1,2,\dotsc)$ be the sequence of 2D Fibonacci arrays
over $\Sigma=\\{a,b,c,d\\}$, with $f_{0,0}=a,f_{0,1}=b,f_{1,0}=c,f_{1,1}=d$.
Also let $\Sigma_{1}=\\{a,b\\}$, $\Sigma_{2}=\\{c,d\\}$,
$\Sigma_{1}^{\prime}=\\{a,c\\}$ and $\Sigma_{2}^{\prime}=\\{b,d\\}$ such that
$\Sigma=\Sigma_{1}\cup\Sigma_{2}=\Sigma_{1}^{\prime}\cup\Sigma_{2}^{\prime}$.
Then,

  * a.

Any row of $f_{m,n}$ is a 1D Fibonacci word over either $\Sigma_{1}$ or
$\Sigma_{2}$.

  * b.

If $\Sigma_{1}\neq\Sigma_{2}$ then all the rows of $f_{m,n}$, over
$\Sigma_{1}$ are identical and all the rows of $f_{m,n}$, over $\Sigma_{2}$
are identical.

  * c.

Any column of $f_{m,n}$ is a 1D Fibonacci word over either
$\Sigma_{1}^{\prime}$ or $\Sigma_{2}^{\prime}$.

  * d.

If $\Sigma_{1}^{\prime}\neq\Sigma_{2}^{\prime}$ then all the columns of
$f_{m,n}$, over $\Sigma_{1}^{\prime}$ are identical and all the columns of
$f_{m,n}$, over $\Sigma_{2}^{\prime}$ are identical.

  * e.

If $\Sigma_{1}=\Sigma_{2}(\Sigma_{1}^{\prime}=\Sigma_{2}^{\prime})$, then
either all the rows$($columns$)$ of $f_{m,n}$ are identical or a set of rows
are identical and are complementary to the set of remaining rows $($columns,
respectively$)$ which are identical.

For more properties of 2D Fibonacci words the reader can refer [20] and [23].

##  3 Tandem Repeats in $f_{m,n}$

In molecular genetics, data is represented as a sequence of characters. Many
algorithms in molecular biology try to find structures called tandems, which
are patterns of nucleotides repeated adjacent to each other in a DNA. In fact
more than half of the human genome contains repeated sequences [24, 25]. They
are related to inherited traits of an individual and play a role in DNA tests.
Even an approximate tandem repeat is related to some human diseases [26].
Tandem repeats in $2D$ words were studied in [1, 11, 10, 12] with varying
interests.

###  3.1 Types of Tandems

######  Definition 8.

[1] In a two dimensional array $X$, a tandem is a configuration consisting of
two occurrences of a same primitive block $W$ that touch each other with one
side($Type~{}I$ tandem) or with a corner($Type~{}II$ tandem).

We further divide Type I and Type II tandems as defined below.

######  Definition 9.

Let $u$ be a 2D word. For a primitive block $W$, the $Type~{}I$ tandem $W\obar
W$ is called a $Type~{}I(a)$ tandem of $u$ and $W\ominus W$ is called a
$Type~{}I(b)$ tandem of $u$.

######  Definition 10.

Let $u$ be a 2D word. For a primitive block $W$ which is a subarray of $u$,
and for $A$,$B\in\Sigma^{++}$, whose sizes are the same as that of $W$, if the
$Type~{}II$ tandem is such that $(W\obar A)\ominus(B\obar W)$ is a sub array
of $u$, then it is called a $Type~{}II(a)$ tandem of $u$. And if the
$Type~{}II$ tandem is such that $(C\obar W)\ominus(W\obar D)$ is a sub array
of $u$, for some $C$,$D\in\Sigma^{++}$, whose sizes are the same as that of
$W$, then it is called a $Type~{}II(b)$ tandem of $u$.

All the four types of tandems are shown in Figure 1.

Figure 1: Types of tandems that can occur in a two-dimensional array

######  Remarks.

Block $W$ is called the root of the tandem. A tandem need not be a 2D array.
Also note that, $Type~{}I(b)~{}(Type~{}II(b)$, respectively$)$ tandem will be
a $90^{\circ}$ rotation of $Type~{}I(a)~{}(Type~{}II(a)$, respectively$)$ and
vice versa.

Formulas to count the exact number of squares including repetitions and
without including repetitions(i.e. distinct) are established in [27]. Both the
theorems are recalled here. Note that, there is a corrigendum [28] to [27]
correcting an error in the formula for number of squares, derived in [27]. The
correct formula was verified in [29] also, using a logic-based decision
procedure, implemented as $Walnut$.

Denote by $D(n)$ and by $R(n)$ the exact number of distinct and repeated
squares, respectively, in $f_{n}$. Then,

######  Theorem 1.

[27] For $n\geq 5$, $D(n)=2(F(n-2)-1)$.

######  Theorem 2.

[28] For $n\geq 3$,
$R(n)=\frac{4}{5}nF(n)-\frac{2}{5}(n+6)F(n-1)-4F(n-2)+n+1$.

##  4 Number of Tandems of $f_{m,n}$

In this section we count the number of tandems (with repetition included, i.e.
same tandems, but positioned at different locations are included in the
counting) in the given Fibonacci array $f_{m,n}$.

###  4.1 The number of $Type~{}I$ Tandems in the Fibonacci Array $f_{m,n}$

First we prove two Propositions to help our counting.

######  Proposition 1.

Let $S$ be a $Type~{}I(a)$ tandem of size $(r,c)$, with $r\geq 1$ and $c\geq
2$ is even. Then there are $\frac{r(r+1)}{2}$ number of $TypeI(a)$ tandems in
$S$.

###### Proof.

Observe that if $S$ is a $Type~{}I(a)$ tandem, then every row of $S$ will be a
$Type~{}I(a)$ tandem. Conversely, if every row of an array is a $Type~{}I(a)$
tandem then the array itself will be a $Type~{}I(a)$ tandem.

Denote the top left corner of $S$ as position $[1,1]$. Consider the
$Type~{}I(a)$ tandem, $S_{1}$, with $r$ rows, and $c$ columns, located at
$[1,1]$ (i.e. $S_{1}=S$ itself). The sub arrays of $S_{1}$ consisting of its
first $i$ rows alone, $1\leq i\leq r$, will be $Type~{}I(a)$ tandems of sizes
$(i,c)$. Hence there are $r$ tandems, located at $[1,1]$. Now consider the
tandem, $S_{2}$, with $(r-1)$ rows, located at $[2,1]$. The sub arrays of
$S_{2}$ consisting of its first $i$ rows alone, $1\leq i\leq r-1$ will be
$Type~{}I(a)$ tandems of sizes $(i,c)$. Hence there are $r-1$ tandems, located
at $[2,1]$. Continuing this process we get $r+(r-1)+\cdots+1=\frac{r(r+1)}{2}$
$Type~{}I(a)$ tandems in $S$. ∎

######  Proposition 2.

Let $S$ be a $Type~{}I(b)$ tandem of size $(r,c)$, with $c\geq 1$ and $r\geq
2$ is even. Then there are $\frac{c(c+1)}{2}$ number of $Type~{}I(b)$ tandems
in $S$.

###### Proof.

The proof is similar to the proof of Proposition1. ∎

Now through a combinatorial argument we can count the number of $Type~{}I(a)$
and $Type~{}I(b)$ tandems in $f_{m,n}$.

######  Theorem 3.

For $m\geq 1$ and $n\geq 3$, let $R(m,n;I(a))$ denote the exact number of
$Type~{}I(a)$ tandems occurring in $f_{m,n}$. Then,

$R(m,n;I(a))=R(n)\frac{F(m)(F(m)+1)}{2}$,

where $R(n)$ is the number of squares in the Fibonacci word $f_{n}$ (see
Theorem 2).

###### Proof.

Due to the characteristics of $f_{m,n}$, as mentioned in the Lemma 1, if there
is a $Type~{}I(a)$ tandem (square) of length $2l$, $1\leq
l\leq\lfloor\frac{F(n)}{2}\rfloor$ in the first row, occurring at the position
$[1,s],1\leq s\leq F(n)-1$, then there will be squares of the same length
$2l$, at the positions $[i,s]$ for all $2\leq i\leq F(m)$. Therefore, there
will be a $Type~{}I(a)$ tandem of size $(F(m),2l)$ located at $[1,s]$. Now by
Proposition 1, we get $\frac{F(m)(F(m)+1)}{2}$ number of $Type~{}I(a)$ tandems
from this tandem. Note that, for every square present in the first row of
$f_{m,n}$, we get $\frac{F(m)(F(m)+1)}{2}$ number of $Type~{}I(a)$ tandems.

By Theorem 2, we have,

$R(n)=\frac{4}{5}nF_{n}-\frac{2}{5}(n+6)F_{n-1}-4F_{n-2}+n+1~{}$

number of squares present in the first row of $f_{m,n}$. Hence, $f_{m,n}$ has
$R(n)\frac{F(m)(F(m)+1)}{2}$ number of $Type~{}I(a)$ tandems. ∎

######  Theorem 4.

For $m\geq 3$ and $n\geq 1$, Let $R(m,n;I(b))$ denote the exact number of
$Type~{}I(b)$ tandems occurring in $f_{m,n}$. Then,

$R(m,n;I(b))=R(m)\frac{F(n)(F(n)+1)}{2}$,

where $R(m)$ is the number of squares in the Fibonacci word $f_{m}$ (see
Theorem 2)

###### Proof.

The proof is similar to the proof of Theorem 3. ∎

###  4.2 The Number $Type~{}II$ Tandems in the Fibonacci Array $f_{m,n}$

In this section we count the number of $Type~{}II$ tandems (repetition
included) in the given Fibonacci array $f_{m,n}$.

######  Proposition 3.

Let $\Sigma=\\{a,b,c,d\\}$ be the alphabet. Let $A,B,C,D\in\Sigma^{++}$ be
arrays of same size such that $(A\obar B)\ominus(C\obar D)$ is a sub array of
$f_{m,n}$. Then, $A=D=W$ (i.e. a $Type~{}II(a)$ tandem occurs) iff
$A=B=C=D=W$.

###### Proof.

If $A=B=C=D=W$, then obviously there occurs a $Type~{}II(a)$ tandem.
Conversely, Let $A=D=W$ (i.e. a $Type~{}II(a)$ tandem occurs) in $(A\obar
B)\ominus(C\obar D)$. Then $A$ and $D$ have identical first rows over a same
alphabet say $\Sigma^{\prime}\subset\Sigma$. By Lemma 1, the first rows of
$(A\obar B)$ and $(C\obar D)$ will be identical. A similar argument on the
other rows show that $A=B=C=D=W$. ∎

######  Definition 11.

[1] Given a 2D array $X$, a quartic in $X$ is a configuration consisting of
the form  $W$ $W$ $W$ $W$ where block $W$ is primitive.

From Proposition 3 and Definition 11 we infer that, in Fibonacci arrays,
$Type~{}II(a)$ tandems occur only as a part of quartics. Hence, the number of
$Type~{}II(a)$ tandems in a Fibonacci array equals the number of quartics in
the Fibonacci array. In the next theorem we count the number of quartics and
hence the number of $Type~{}II(a)$ tandems.

######  Theorem 5.

For $m,n\geq 3$, let $R(m),R(n)$ denote the number of squares $($repetitions
included$)$ in the Fibonacci words $f_{m},f_{n}$ respectively. Then, there are
$R(m)R(n)$ quartics in the Fibonacci array $f_{m,n}$ and hence there are as
many $Type~{}II(a)$ tandems in $f_{m,n}$.

###### Proof.

We know that, every row of a $Type~{}I(a)$ tandem will be a $Type~{}I(a)$
tandem and every column of $Type~{}I(b)$ tandem will be a $Type~{}I(b)$
tandem. Since a quartic is both a $Type~{}I(a)$ and a $Type~{}I(b)$ tandem,
only the sub arrays having the intersection of a $Type~{}I(a)$ tandem and a
$Type~{}I(b)$ tandem as its domain, can be quartics of $f_{m,n}$. In fact a
$Type~{}I(a)$ tandem of size $(F(m),2l)$, $1\leq
l\leq\lfloor\frac{F(n)}{2}\rfloor$ and a $Type~{}I(b)$ tandem of size
$(2k,F(n))$, $1\leq k\leq\lfloor\frac{F(m)}{2}\rfloor$ will create a quartic
of size $(2k,2l)$ (Refer Figure 2). Now, as there are $R(m),R(n)$ number
squares, respectively, in the Fibonacci words $f_{m},f_{n}$ there will be
$R(m)$ number of squares in the first column and $R(n)$ number of squares the
first row of $f_{m,n}$. Hence, there will be $R(m)R(n)$ quartics in the
Fibonacci array $f_{m,n}$. Therefore by proposition 3 there are as many
$Type~{}II(a)$ tandems in $f_{m,n}$. (Values of $R(m)$ and $R(n)$ are given in
proposition 1 as derived in [27]) . ∎

Figure 2: Formation of a quartic

######  Theorem 6.

There are $R(m)R(n)$ number of $Type~{}II(b)$ tandems in $f_{m,n}$.

###### Proof.

Like $Type~{}II(a)$ tandems, a $Type~{}II(b)$ tandem can occur as a part of
some quartic only. Hence the number of $Type~{}II(b)$ tandems will be the same
as the number of quartics in $f_{m,n}$. Hence by the Theorem 5 there will be
$R(m)R(n)$ number of $Type~{}II(b)$ tandems in $f_{m,n}$. ∎

##  5 Number of Distinct Factors of $f_{n}$

We derive an important result of factor complexity of finite 1D Fibonacci
words here. This will help us to count the distinct $Type~{}I$, $Type~{}II$
tandems in $f_{n}$ and $f_{m,n}$. Analysing the factor complexity of an
infinite word is crucial as we can conclude many things about the nature of
the word. For an infinite word $u$, the factor complexity function is bounded
if $u$ is ultimately periodic. Conversely, $u$ will be ultimately periodic, if
$p_{n}(u)\leq n$ for some $n$ [30]. Balanced words, Sturmian words, Arnoux-
Rauzy word over a ternary alphabet all have been characterised through their
complexity functions. Entropy of an infinite word and unavoidable patterns in
an infinite word are also closely related to the concept complexity function.

######  Definition 12.

[17] For an infinite word $w$, the subword complexity function of $w$,
$p_{w}(n)$, counts the number of distinct subwords of length $n$ in $w$. The
subword complexity sequence of $w$ is the sequence
$p_{w}=(p_{w}(1),p_{w}(2),p_{w}(3),\dotsc)$.

Recall that, the 1D infinite Fibonacci word [17],

$f_{\infty}=\lim_{n\to\infty}h^{n}(a)=h^{\omega}(a)=babbabab\cdots\cdots$

is the fixed point of the morphism $h(a)=b,h(b)=ba$ on $\Sigma=\\{a,b\\}$.

######  Proposition 4.

[17] The subword complexity function of $f_{\infty}$ is
$p_{f_{\infty}}(n)=n+1$. That is the infinite Fibonacci word has exactly $n+1$
factors of length $n$.

Proposition 4 says that the 1D infinite Fibonacci word $f_{\infty}$ has
exactly $n+1$ factors of length $n$ for any $n\geq 1$. This characterisation
itself is sometimes used as the definition of 1D Fibonacci words (in fact the
broad category of 1D Sturmian words). Though the count for distinct factors
$($of any length$)$ of the infinite Fibonacci word is already available, the
count for the number of distinct factors of the finite Fibonacci word $f_{n}$,
$n\geq 2$, is not available. In this section we derive a formula for this
count. Later we use it to count the number of distinct tandems in a given 2D
Fibonacci array, $f_{m,n}$.

We recall the following theorem regarding the positions of all the distinct
factors of length $k\geq 1$, of $f_{\infty}=f$.

######  Theorem 7.

[31] Let $n\geq 2$ and $F(n)\leq k<F(n+1)$. Define

$z_{j}^{(k)}=\begin{cases}f[j+1;k],&0\leq j\leq F(n)-1\\\
f[j+F(n+1)-k;k],&F(n)\leq j\leq k\end{cases}$

where $f[i^{\prime};j^{\prime}]$, $j^{\prime}\geq i^{\prime}$ is the sub word
of $f$ of length $j^{\prime}$ starting at position $i^{\prime}$. Then the
words $z_{0}^{(k)}$,$z_{1}^{(k)}$,$\cdots$,$z_{k}^{(k)}$ are the $k+1$
distinct factors of $f$ of length $k$ which are listed in the order of their
first occurrences in $f$.

We now state and prove one of the major theorems of this paper, related to the
factor complexity of $f_{n}$.

######  Theorem 8.

For $n\geq 2$, let $p_{k}(f_{n})$ denote the number of distinct subwords of
length $k$, $1\leq k\leq F(n)$ in $f_{n}$. Then,

$p_{k}(f_{n})=\begin{cases}k+1~{},&1\leq k\leq F(n-2)\\\
F(n-2)+2~{},&F(n-2)+1\leq k\leq F(n-1)-1\\\ F(n)+1-k~{},&F(n-1)\leq k\leq
F(n)\end{cases}$

Given $f_{n}$, proof is done in three cases.

Table 1 lists the number of distinct factors of various lengths that occur in
$f_{n}$ for $n=2,3,4,5,6$.

Table 1: Number of distinct factors of various lengths occurring in $f_{n}$ Factor Length $\rightarrow$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13
---|---|---|---|---|---|---|---|---|---|---|---|---|---
$f_{n}$ and $F(n)$ $\downarrow$ |  |  |  |  |  |  |  |  |  |  |  |  |
$f_{2}$ , $F(2)=2$ | 2 | 1 |  |  |  |  |  |  |  |  |  |  |
$f_{3}$ , $F(3)=3$ | 2 | 2 | 1 |  |  |  |  |  |  |  |  |  |
$f_{4}$ , $F(4)=5$ | 2 | 3 | 3 | 2 | 1 |  |  |  |  |  |  |  |
$f_{5}$ , $F(5)=8$ | 2 | 3 | 4 | 5 | 4 | 3 | 2 | 1 |  |  |  |  |
$f_{6}$ , $F(6)=13$ | 2 | 3 | 4 | 5 | 6 | 7 | 7 | 6 | 5 | 4 | 3 | 2 | 1

######  Corollary 1.

For $n\geq 2$, let $p(f_{n})$ denote the number of distinct subwords of
$f_{n}$. Then $p(f_{n})=\sum_{k=1}^{F(n)}p_{k}(f_{n})$.

###### Proof.

As $p_{k}(f_{n})$ denote the number of distinct subwords of length $k$ in
$f_{n}$, summation over $k$ yields the value of $p(f_{n})$. ∎

##  6 Number of Distinct Tandems of $f_{m,n}$

We use the result obtained in Theorem 8 to count the number of distinct
tandems in $f_{m,n}$.

Recall from Theorem 1 that, For $n\geq 5$, $D(n)=2(F(n-2)-1)$, where $D(n)$
denotes the exact number of distinct squares in $f_{n}$.

###  6.1 The Number of Distinct $Type~{}I$ Tandems in $f_{m,n}$

######  Theorem 9.

For $m\geq 2$ and $n\geq 5$, let $D(m,n;I(a))$ denote the exact number of
distinct $Type~{}I(a)$ tandems occurring in $f_{m,n}$. Then,

$D(m,n;I(a))=D(n)~{}p(f_{m})$.

###### Proof.

The counting process is very similar to the process explained in the proof of
Theorem 3, except that, we have to consider only the distinct squares in the
first row and the distinct factors of the first column. Hence by Theorem
1(number of distinct squares in any row) and Corollary 1(number of distinct
factors in $f_{m}$), the result follows. ∎

######  Theorem 10.

For $m\geq 5$ and $n\geq 2$, let $D(m,n;I(b))$ denote the exact number of
distinct $Type~{}I(b)$ tandems occurring in $f_{m,n}$. Then,

$D(m,n;I(b))=D(m)~{}p(f_{n})$.

###### Proof.

The proof is similar to the proof of Theorem 9 with the roles of $m$ and $n$
interchanged. ∎

###  6.2 The Number of Distinct $Type~{}II$ Tandems in $f_{m,n}$

In this section we count the number of distinct $Type~{}II$ tandems in
$f_{m,n}$.

######  Theorem 11.

For $m,n\geq 3$, let $D(m),D(n)$ denote the number distinct squares in the
Fibonacci words $f_{m},f_{n}$ respectively. Then, there are $D(m)D(n)$
distinct quartics in the Fibonacci array $f_{m,n}$; and hence there are as
many distinct $Type~{}II(a)$ and $Type~{}II(b)$ tandems in $f_{m,n}$.

###### Proof.

The proof is similar to Theorem 5 except that only distinct squares are
considered in the counting. ∎

##  7 The 2D Infinite Fibonacci Word, $f_{\infty,\infty}$

We know that, a morphism is a map $h:\Sigma^{*}\rightarrow\Delta^{*}$, where
$\Sigma$,$\Delta$ are alphabets, such that $h(xy)=h(x)h(y)$ for all strings
$x,y\in\Sigma^{*}$. If $\Sigma=\Delta$ we can iterate $h$. That is
$h^{n}(x)=h(h^{n-1}(x)),n\geq 2$. In the literature, analysis of the Fibonacci
language, $\\{f_{n}\\}_{n\geq 0}$, over the alphabet $\Sigma=\\{a,b\\}$, is
done with the help of the Fibonacci morphism, $h:a\rightarrow b,b\rightarrow
ba$. That is to say that, the infinite Fibonacci word
$\mathbf{f_{\infty}}=babbababbabba\cdots$ is the limit of the sequence
$\\{f_{n}\\}_{n\geq 0}$. That is,

$f_{\infty}=\lim_{n\to\infty}h^{n}(a)=h^{\omega}(a)=babbabab\cdots\cdots$

is the fixed point of the morphism $h(a)=b,h(b)=ba$ on $\Sigma=\\{a,b\\}$.

Also, note that, finitely many iterations of the above morphism
($h(a)=b,h(b)=ba$) generates the intermediate finite Fibonacci words, $f_{n}$
for all $n\geq 0$, ultimately leading to $f_{\infty}$, the fixed point of the
morphism, when $n\rightarrow\infty$.

###  7.1 $d-$dimensional Morphisms

Similar to $f_{\infty}$ we define $f_{\infty,\infty}$, the 2D infinite
Fibonacci word. It is noted that, the concept of two dimensional iterated
morphisms was first introduced in [32]. But, such morphisms might not always
result in rectangular patterns. Interestingly, in [33], $d-$dimensional
morphisms are introduced and using them $d-$dimensional infinite words are
defined. After stating the required definitions and results from [33, 34], we
will define and validate the 2D morphism generating $f_{\infty,\infty}$. As a
continuation, in section 9 , we construct a DFAO (Deterministic Finite
Automaton with Output) which generates $f_{\infty,\infty}$.

###  7.2 The 2D Fibonacci Morphism

Now, we state and prove another important theorem of this paper. Consider the
case $d=2$ in [33].

######  Definition 13.

Let $\mu:\Sigma\rightarrow B_{2}(\Sigma)$ be a map and $x$ be a 2-dimensional
array such that,

$\forall i\in\llbracket 1,2\rrbracket,\forall k<|x|_{i},\forall a,b\in
Fact_{\textbf{1}}(x_{|i,k}):|\mu(a)|_{i}=|\mu(b)|_{i}.$ (1)

Then the image of x by $\mu$ is the 2-dimensional array defined as,

$\mu(x)=\odot_{0\leq n_{1}<|x|_{1}}^{1}\left(\odot_{0\leq
n_{2}<|x|_{2}}^{2}\mu(x(n_{1},n_{2}))\right).$

If for all $a\in\Sigma$ and all $n\geq 1$, $\mu^{n-1}(a)$ satisfies (1), then
$\mu$ is said to be a 2-dimensional morphism. Further, the properties of $\mu$
being prolongable on $a$ and $\mu$ having a fixed point, follow automatically.

Now, consider the map,

$\mu:~{}~{}d\rightarrow\begin{matrix}d&c\\\
b&a\end{matrix},~{}~{}c\rightarrow\begin{matrix}d\\\
b\end{matrix},~{}~{}b\rightarrow\begin{matrix}d&c\end{matrix},~{}~{}~{}a\rightarrow
d.$ (2)

We have written in the order $d,c,b,a$ as $(\mu(d))_{\textbf{0}}=d$ (i.e. as
$\mu$ is prolongable on $d$).

The following result is proved by induction technique.

######  Theorem 12.

Let $f_{0,0}=a,~{}f_{0,1}=b,~{}f_{1,0}=c,~{}f_{1,1}=d$ and $\mu$ be defined as
in (2). Then for $m,n\geq 1,$

$\mu(f_{m,n})=f_{m+1,n+1}.$

######  Corollary 2.

For $n\geq 1,~{}~{}\mu(f_{n,n})=f_{n+1,n+1}.$

###### Proof.

By taking $m=n$ in the theorem, the corollary follows. ∎

######  Corollary 3.

$w=\mu^{\omega}(d)$ exists.

###### Proof.

Since, $\mu(f_{n,n})=f_{n+1,n+1}$, $\mu^{n}(d)$ is inductively well defined
from $\mu^{n-1}(d)$ and hence $\mu$ is a 2D morphism. Now, since
$(\mu(d))_{\textbf{0}}=d$, $\mu$ is prolongable on $d$, and

$w=\lim_{n\rightarrow+\infty}\mu^{n}(d)=\mu^{\omega}(d)$

exists. This fixed point $w$ is called the infinite 2D Fibonacci word and is
denoted by $f_{\infty,\infty}$. ∎

First few iterations of $\mu$ on $d$ are shown below.

$d\rightarrow\begin{matrix}d&c\\\
b&a\end{matrix}\rightarrow\begin{matrix}d&c&d\\\ b&a&b\\\
d&c&d\end{matrix}\rightarrow\begin{matrix}d&c&d&d&c\\\ b&a&b&b&a\\\
d&c&d&d&c\\\ d&c&d&d&c\\\ b&a&b&b&a\\\
\end{matrix}\rightarrow\begin{matrix}d&c&d&d&c&d&c&d&\cdots\\\
b&a&b&b&a&b&a&b&\cdots\\\ d&c&d&d&c&d&c&d&\cdots\\\ d&c&d&d&c&d&c&d&\cdots\\\
b&a&b&b&a&b&a&b&\cdots\\\ d&c&d&d&c&d&c&d&\cdots\\\ b&a&b&b&a&b&a&b&\cdots\\\
d&c&d&d&c&d&c&d&\cdots\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{matrix}$

###  7.3 2D Finite Fibonacci Words as Morphic Words

As $\mu(f_{m,n})=f_{m+1,n+1}$, it is interesting to note that, the morphism
$\mu$ behaves like a shift operator. Hence, iterated applications of $\mu$ on
$f_{1,n^{\prime}}$ or $f_{m^{\prime},1}$ with appropriate
$m^{\prime},n^{\prime}$ values, can generate any finite 2D Fibonacci word.

######  Corollary 4.

Let $m,n\geq 2$ and $m\neq n$. Then, we have

$f_{m,n}=\left\\{\begin{array}[]{ll}\mu^{(m-1)}(f_{1,n-m+1})&\mbox{if }m<n\\\
\\\ \mu^{(n-1)}(f_{m-n+1,1})&\mbox{if }m>n\end{array}\right.$

###### Proof.

We know that the 2D Fibonacci words $f_{1,n^{\prime}}$ and $f_{m^{\prime},1}$
for any $m^{\prime},n^{\prime}\geq 2$ can be easily obtained, as they are
literally 1D Fibonacci words over $\\{d,c\\}$ and $\\{d,b\\}$ respectively.

Now, since $\mu(f_{m,n})=f_{m+1,n+1}$, for $k\geq
1,~{}\mu^{k}(f_{m,n})=f_{m+k,n+k}$.

Therefore,

$\begin{array}[]{ll}~{}~{}\mbox{if
}~{}m<n,{}{}{}&\mu^{(m-1)}(f_{1,n-m+1})=f_{1+m-1,n-m+1+m-1}=f_{m,n}~{}~{}~{}~{}\mbox{and
}\\\ \\\ ~{}~{}\mbox{if
}~{}m>n,{}{}{}&\mu^{(n-1)}(f_{m-n+1,1})=f_{m-n+1+n-1,1+n-1}=f_{m,n}.\end{array}$

∎

######  Example 2.

Suppose we want to generate $f_{3,5}$.

Since $n>m$ , $n-m\geq 1$ and we start with $f_{1,n-m+1}=f_{1,3}=d~{}c~{}d$,
so that, $\mu^{2}(f_{1,3})$ will be $f_{3,5}$.

$\displaystyle\mu^{2}(f_{1,3})=\mu^{2}(d~{}c~{}d)$
$\displaystyle=\mu\left(\begin{matrix}d&c&d&d&c\\\
b&a&b&b&a\end{matrix}\right)$ $\displaystyle=\begin{matrix}d&c&d&d&c&d&c&d\\\
b&a&b&b&a&b&a&b\\\ d&c&d&d&c&d&c&d\end{matrix}=f_{3,5}.$

##  8 Factor Complexities of $f_{\infty,\infty}$ and $f_{m,n}$

In this section we find the number of distinct subwords of any given $f_{m,n}$
and also of $f_{\infty,\infty}$. The result proved in Theorem 8, will be used
to find the factor complexity of $f_{m,n}$. We denote by $p_{k,l}(u)$, the
complexity function of the two dimensional word $u$. It is understood through
the subscripts $k$ and $l$ that $u$ is a two dimensional word.

######  Proposition 5.

For $u$, a 2D word over $\Sigma$, let $p_{k,l}(u),~{}k,l\geq 1$ denote the
number of subwords (subarrays) of $u$ of size $(k,l)$. Then, for the two
dimensional infinite Fibonacci word, $f_{\infty,\infty}$,
$p_{k,l}(f_{\infty,\infty})=(k+1)(l+1)$.

###### Proof.

The result is immediate through a simple combinatorial argument. By lemma 1,
every row (every column) of $f_{\infty,\infty}$ written as a 1D word is an 1D
infinite Fibonacci word $f_{\infty}$ over any one of the two letter alphabets
$\\{d,c\\},\\{b,a\\}(\\{d,b\\},\\{c,a\\})$. By proposition 4, there are $k+1$
distinct subwords of length $k$ in every column (we call them, vertical
factors) and $l+1$ distinct subwords of length $l$ in every row (we call them,
horizontal factors). Since there are only two distinct columns (one over
$\\{d,b\\}$ and one over $\\{c,a\\}$) in $f_{\infty,\infty}$, there are
$2(k+1)$ vertical factors of length $k$. Similarly, there are $2(l+1)$
horizontal factors of length $l$. By pairing the vertical(horizontal) factors
located in the same row(column), we get $k+1$ ( l+1 ) pairs of
vertical(horizontal) factors. Now, note that a 2D subword of
$f_{\infty,\infty}$ is formed by the process similar to the one explained in
the proof of Theorem 2 from [23]. That is, a vertical factor will produce a 2D
factor through a horizontal factor, if both have the same prefix of size
$(1,1)$. Now, as one factor in a pair of vertical factors shares a common
prefix of size $(1,1)$ with one factor in a pair of horizontal factors, there
will be $(k+1)(l+1)$ distinct factors of size $(k,l)$ in $f_{\infty,\infty}$.
∎

To understand the process, in Example 3 we list the factors of size $(2,3)$ in
$f_{\infty,\infty}$.

######  Example 3.

Consider $f_{\infty,\infty}$.

Horizontal Factors of dcd cdd ddc cdc length $3$ $\rightarrow$ (or) (or) (or)
(or) $Vertical$ bab abb bba aba Factors of length 2 $\downarrow$
$\begin{tabular}[]{c}d\\\ b\end{tabular}(or)\begin{tabular}[]{c}c\\\
a\end{tabular}$ d c d b a b c d d a b b d d c b b a c d c a b a
$\begin{tabular}[]{c}b\\\ d\end{tabular}(or)\begin{tabular}[]{c}a\\\
c\end{tabular}$ b a b d c d a b b c d d b b a d d c a b a c d c
$\begin{tabular}[]{c}d\\\ d\end{tabular}(or)\begin{tabular}[]{c}c\\\
c\end{tabular}$ d c d d c d c d d c d d d d c d d c c d c c d c

We have $3\times 4=12$ factors of size $(2,3)$.

The count, carried out in proposition 5 can be restricted to any finite
Fibonacci word $f_{m,n}$. Note that, while counting factors of size $(k,l)$ in
a given $f_{m,n}$, contrary to the availability of all $(k+1)$ vertical
factors and $(l+1)$ horizontal factors in $f_{\infty,\infty}$, not all will be
available in $f_{m,n}$. This is due to the finite nature of $f_{m,n}$. But, by
theorem 8, we know the exact number of horizontal and vertical factors
available in any given $f_{m,n}$. Hence we have the following result.

######  Proposition 6.

Given a finite Fibonacci array, $f_{m,n}$, the number of factors of size
$(k,l)$ in it are,

$p_{k,l}(f_{m,n})=p_{k}(f_{m})p_{l}(f_{n}).$

###### Proof.

Using the count derived in theorem 8, one can show the equality in identical
lines with the proof of proposition 5. ∎

In Example 4 also, we count the factors of size $(2,3)$, but in $f_{3,4}$. We
can observe the non availability of some horizontal, vertical factors due to
the finite nature of $f_{3,4}$.

######  Example 4.

Consider $f_{3,4}=\begin{tabular}[]{|c c c c c|}\hline\cr d&c&d&d&c\\\
b&a&b&b&a\\\ d&c&d&d&c\\\ \hline\cr\end{tabular}$.

Horizontal dcd cdd ddc Factors of length $3$ $\rightarrow$ (or) (or) (or)
$Vertical$ bab abb bba Factors of length 2 $\downarrow$ d b (or) c a d c d b a
b c d d a b b d d c b b a b d (or) a c b a b d c d a b b c d d b b a d d c

We have, $p_{2}(f_{3})\times p_{3}(f_{4})=2\times 3=6$ factors of size
$(2,3)$.

##  9 2D Fibonacci Words as $S-automatic$ Words

In this section we construct a DFAO which generates $f_{\infty,\infty}$.

To construct the DFAO, first we construct $|\Sigma|$ number of automata, one
for each letter of $\Sigma$, as outlined [33].These automata will be
integrated to get the required DFAO.

######  Definition 14.

[33] For each d-dimensional morphism $\mu:\Sigma\rightarrow B_{d}{(\Sigma)}$
and for each letter $a\in\Sigma$, define a DFA $\mathscr{A}_{\mu,a}$ over the
alphabet $\\{0,1,\ldots,r_{\mu}-1\\}^{d}$ where
$r_{\mu}:=max\\{|\mu(b)|_{i}~{}~{}|~{}b\in\Sigma,i=1,\ldots,d\\}$. The set of
states is $\Sigma$, the initial state is $a$ and all states are final. The
(partial) transition function is defined by

$\delta_{\mu}(b,\textbf{n})=(\mu(b))_{\textbf{n}},~{}~{}~{}\forall
b\in\Sigma~{}\text{and}~{}\textbf{n}\leq|\mu(b)|.$

This automaton will be such that, for all $m,n\geq 0$,

$y_{m,n}=\delta_{\mu}(a,(rep_{S}(m),rep_{S}(n))^{0}),$

where we have padded the shortest word with enough $0$s to make the length of
the two words the same. If we consider the coding
$v:\Sigma^{*}\rightarrow\Gamma^{*}$, as the output function, the corresponding
DFAO generates $x$ as an S-automatic sequence.

The procedure is outlined below.

  * Step 1

From the first rows of the morphism $\mu$, derive the one dimensional morphism
$\mu_{1}:\Sigma_{1}\rightarrow\Sigma_{1}^{*}$ , $\Sigma_{1}\subseteq\Sigma$ ,
which is prolongable on $a$ (This is the restricted morphism along the first
direction)

  * Step 2

Construct the automaton $\mathscr{A}_{\mu_{1},a}$ and obtain the directive
language $L{\mu_{1},a}$

( Alternatively, we can consider the first columns of the morphism $\mu$ to
derive the one dimensional morphism
$\mu_{2}:\Sigma_{2}\rightarrow\Sigma_{2}^{*}$ , $\Sigma_{2}\subseteq\Sigma$,
which is also prolongable on $a$. Note that, this is the restricted morphism
along the second direction. Then by constructing the automaton
$\mathscr{A}_{\mu_{2},a}$ we can obtain the directive language $L{\mu_{2},a}$.
But since $Shape_{\mu_{1}}(x)=Shape_{\mu_{2}}(y)$, where x =
$\mu_{1}^{\omega}(a)$ and $y=\mu_{2}^{\omega}(a)$, the languages
$L_{\mu_{1},a}$ and $L_{\mu_{2},a}$ will be equal [33])

  * Step 3

For each letter $a\in\Sigma$, define a DFA $\mathscr{A}_{\mu,a}$ as described
in the Definition 14. The DFAO $\mathscr{A}_{\mu}$ is constructed by combining
(superimposing) these DFAs.

  * Step 4

For an input $(rep_{S}(m),rep_{S}(n))^{0}$, the output of $\mathscr{A}_{\mu}$
is the symbol $s\in\Sigma$ in the accepting state which will be written at
$x_{m,n}$, the $(m,n)^{th}$ entry in the 2D infinite word.

###  9.1 DFAO Generating $f_{\infty,\infty}$ as an S-automatic word

As explained earlier, we have the two unidimensional morphisms derived from
(2). Let $\Sigma_{1}=\\{d,c\\}$ and $\Sigma_{2}=\\{d,b\\}$. Then,

$\mu_{1}:\Sigma_{1}\rightarrow\Sigma_{1}^{*}~{}~{}:=d\rightarrow
dc,~{}~{}c\rightarrow d$ and
$\mu_{2}:\Sigma_{2}\rightarrow\Sigma_{2}^{*}~{}~{}:=d\rightarrow
db,~{}~{}b\rightarrow d$.

The automaton $\mathscr{A}_{\mu_{1},d}$ will be as in Figure 3. And the
directive language will be

$L_{\mu_{1},d}=\\{\epsilon,1,10,100,101,1000,1001,1010,\dots\\}.$

Figure 3: Automaton $\mathscr{A}_{\mu_{1},d}$

Note that $r_{\mu}:=max\\{|\mu(b)|_{i}~{}~{}|~{}b\in\Sigma,i=1,2\\}=2$. Hence,
for each letter $a\in\Sigma$, we define a DFA, $\mathscr{A}_{\mu,a}$ over the
alphabet $\\{0,1\\}^{2}=\\{(0,0),(0,1),(1,0),(1,1)\\}$. All the four automata
are given in Figure 4. We combine all the four automata to get the required
automaton, $\mathscr{A}_{\mu}$ , given in Figure 5.

Figure 4: $\mathscr{A}_{\mu,d}$, $\mathscr{A}_{\mu,c}$ , $\mathscr{A}_{\mu,b}$
, $\mathscr{A}_{\mu,a}$ Figure 5: DFAO $\mathscr{A}_{\mu}$ generating
$f_{\infty,\infty}$

For a given $m,n\geq 0$, the steps involved in obtaining the symbol at $(m,n)$
in $f_{\infty,\infty}$ are briefly explained in Example 5, using the values
$m=2$ and $n=4$..

######  Example 5.

Let us generate the symbol at $(2,4)$ in $f_{\infty,\infty}$. From the
directive language we get $rep_{S}(2)=10$ and $rep_{S}(4)=101$.

The $(2,4)^{th}$ entry will be
$\delta_{\mu}(d,(10,101)^{0})=\delta_{\mu}(d,(010,101))$.

$d\xrightarrow{(0,1)}c\xrightarrow{(1,0)}b\xrightarrow{(0,1)}c.$

By generating all the symbols at $(i,j)$, $i\in\llbracket 0,s-1\rrbracket$,
$j\in\llbracket 0,t-1\rrbracket$ the prefix of size, (s,t) of
$f_{\infty,\infty}$ can be generated. More specifically any finite 2D
Fibonacci array can be generated.

##  10 Conclusion

Though the theory of two-dimensional words is a natural extension of the
theory of one-dimensional words, exploring their combinatorial and structural
properties is not a straightforward task. In this paper we have analysed two
important properties - tandem repeats and factor complexity - of finite 2D
Fibonacci words and the infinite 2D Fibonacci word. A 2D homomorphism with the
infinite 2D Fibonacci word as its fixed point is presented, proving that the
infinite 2D Fibonacci word is a morphic word. A DFAO generating the 2D
Fibonacci words is also constructed. Some closely related properties to tandem
repeats are, approximate tandem repeats and approximate periodicity of 2D
Fibonacci words. Future research might concentrate on these properties.

## References

  * [1] A. Apostolico, V. E. Brimkov, Fibonacci arrays and their two-dimensional repetitions, Theoretical Computer Science 237 (1–2) (2000) 263–273.
  * [2] M. Lothaire, Combinatorics on words, Cambridge University Press, 1997.
  * [3] G. Paun, G. Rozenberg, A. Salomaa, DNA Computing: New Computing Paradigms, Springer-Verlag Berlin Heidelberg, 1998.
  * [4] R. Dallapiccola, A. Gopinath, F. Stellacci, L. D. Negro, Quasi-periodic distribution of plasmon modes in two-dimensional Fibonacci arrays of metal nanoparticles, Optics Express 16 (8) (2008) 5544–5555.
  * [5] J. Berstel, Axel Thue’s work on repetitions in words, Series Formelles et Combinatoire Algerique 11 (1992) 65–80.
  * [6] S. Jain, F. F. Hassanzadeh, J. Bruck, Capacity and expressiveness of genomic tandem duplication, IEEE Transactions on Information Theory 63 (10) (2017) 6129–6138.
  * [7] D. Salomon, Data Compression: The Complete Reference, 4th Edition, Springer, 2007\.
  * [8] D. Gusfield, J. Stoye, Linear time algorithms for finding and representing all the tandem repeats in a string, Journal of Computer and System Sciences 69 (4) (2004) 525–546.
  * [9] M. Crochemore, L. Ilie, W. Rytter, Repetitions in strings: Algorithms and combinatorics, Theoretical Computer Science 410 (50) (2009) 5227–5235.
  * [10] A. Amir, G. M. Landau, S. Marcus, D. Sokol, Two-dimensional maximal repetitions, Theoretical Computer Science 812 (2020) 49–61.
  * [11] P. Charalampopoulos, J. Radoszewski, W. Rytter, T. Waleń, W. Zuba, The number of repetitions in 2D-strings, in: F. Grandoni, G. Herman, P. Sanders (Eds.), 28th Annual European Symposium on Algorithms (ESA 2020), Vol. 173 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020, pp. 32:1–32:18.
  * [12] A. Amir, A. Butman, G. M. Landau, S. Marcus, D. Sokol, Double String Tandem Repeats, in: I. L. Gørtz, O. Weimann (Eds.), 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020), Vol. 161 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020, pp. 3:1–3:13.
  * [13] A. Amihood, B. Ayelet, K. Eitan, L. Avivit, S. Dina, Multidimensional period recovery, Algorithmica.
  * [14] J. Berstel, Fibonacci words - a survey, in: G. Rozenberg, A. Salomaa (Eds.), The book of L, Springer-Verlag, 1986, pp. 13–27.
  * [15] S. S. Yu, Y. K. Zhao, Properties of Fibonacci languages, Discrete Mathematics 224 (2000) 215–223.
  * [16] K. Kamala, R. Rama, Introduction to Formal Languages, Automata Theory and Computation, Pearson Education, 2009.
  * [17] M. Lothaire, Algebraic combinatorics on words, Cambridge University Press, 2002\.
  * [18] D. Giammarresi, A. Restivo, Two-dimensional languages, in: G. Rozenberg, A. Salomaa (Eds.), Handbook of formal languages, Springer, 1997, pp. 215–267.
  * [19] M. Anselmo, D. Giammarresi, M. Madonia, Prefix picture codes: a decidable class of two-dimensional codes, International Journal of Foundations of Computer Science 25 (08) (2014) 1017–1031.
  * [20] M. S. Kulkarni, K. Mahalingam, M. Sivasankar, Combinatorial properties of Fibonacci arrays, in: T. V. Gopal, J. Watada (Eds.), Theory and Applications of Models of Computation, Springer International Publishing, 2019, pp. 448–466.
  * [21] G. Gamard, G. Richomme, J. Shallit, T. J. Smith, Periodicity in rectangular arrays, Information Processing Letters 118 (2017) 58–63.
  * [22] V. Berthe, L. Vuillon, Palindromes and two-dimensional sturmian sequences, Journal of Automata, Languages and Combinatorics 6 (2) (2001) 121–138.
  * [23] K. Mahalingam, M. Sivasankar, K. Krithivasan, Palindromic properties of two dimensional Fibonacci words, The Romanian Journal of Information Science and Technology 21 (3) (2018) 256–266.
  * [24] E. S. Lander, Initial sequencing and analysis of the human genome, Nature 409 (6822) (2001) 860–921.
  * [25] N. I. Mundy, A. J. Helbig, Origin and evolution of tandem repeats in the mitochondrial DNA control region of shrikes, Journal of Molecular Evolution 59 (2) (2004) 250–257.
  * [26] G. M. Landau, J. P. Schmidt, An algorithm for approximate tandem repeats, in: A. Apostolico, M. Crochemore, Z. Galil, U. Manber (Eds.), Combinatorial Pattern Matching, Springer Berlin Heidelberg, 1993, pp. 120–133.
  * [27] A. Fraenkel, J. Simpson, The exact number of squares in Fibonacci words, Theoretical Computer Science 218 (1) (1999) 83–94.
  * [28] A. Fraenkel, J. Simpson, Corrigendum to “The exact number of squares in Fibonacci words” [Theoretical computer science 218 (1) (1999) 95–106], Theoretical Computer Science 547 (2014) 122.
  * [29] C. F. Du, H. Mousavi, L. Schaeffer, J. Shallit, Decision algorithms for Fibonacci-automatic words, III: Enumeration and abelian properties, International Journal of Foundations of Computer Science 27 (8) (2016) 943 – 963.
  * [30] J. P. Allouche, J. Shallit, Automatic sequences: Theory, applications, generalizations, Cambridge University Press, 2003.
  * [31] W. F. Chuan, H. L. Ho, Locating factors of the infinite Fibonacci word, Theoretical Computer Science 349 (3) (2005) 429–442.
  * [32] P. Arnoux, V. Berthé, A. Siegel, Two dimensional iterated morphisms and discrete planes, Theoretical Computer Science 319 (1) (2004) 145 – 176.
  * [33] E. Charlier, T. Karki, M. Rigo, Multidimensional generalized automatic sequences and shape-symmetric morphic words, Discrete Mathematics 310 (6) (2010) 1238–1252.
  * [34] P. B. A. Lecomte, M. Rigo, Numeration systems on a regular language, Theory of Computing Systems 34 (1) (2000) 27–44.


# Demystifying Quantum Mechanics

Ana Elisa D. Barioni  Felipe B. Mazzi  Elsa Bifano Pimenta  Willian Vieira dos
Santos  Marco A. P. Lima  Instituto de Física “Gleb Wataghin”, Universidade
Estadual de Campinas, 13083-859, Campinas, SP, Brazil

###### Abstract

Why does such a successful theory like Quantum Mechanics have so many
mysteries? The history of this theory is replete with dubious interpretations
and controversies, and yet a knowledge of its predictions, however,
contributed to the amazing technological revolution of the last hundred years.
In its very beginning Einstein pointed out that there was something missing,
due to contradictions with the relativity theory. So, even though Quantum
Mechanics explains all the nanoscale physical phenomena, there were many
attempts to find a way to “complete” it, e.g. hidden-variable theories. In
this paper, we discuss some of those enigmas, with special attention to the
concepts of physical reality imposed by quantum mechanics, the role of the
observer, prediction limits, a definition of collapse, and how to deal with
correlated states (the basic strategy for quantum computers and quantum
teleportation). That discussion is carried out within the framework of
accepting that there is in fact nothing important missing, rather we are just
restricted by the limitations imposed by quantum mechanics. The mysteries are
thus explained by a proper interpretation of those limitations, which is
achieved by introducing two interpretation rules within the Copenhagen
paradigm.

###### pacs:

03.65.-w, 03.65.Ca, 03.65.Ta

In the series “Cosmos: Possible Worlds”cpw , Neil deGrasse Tyson, presenting
the double slit experiment for photons, says: “On the smallest possible scale
that we’ve ever discovered, the quantum universe, the mere act of observation
changes reality”. This interpretation can be misleading, but it is very
present in physics classes all over the world. Indeed, it brings us back to
the well considered and famous Schrödinger’s cat dilemma: can the cat be in a
mixed state of dead and alive? The interpretation given by the Cosmos show,
seen by millions of people, by itself justifies the discussion below.
Furthermore, one of the most puzzling mysteries of quantum mechanics is in
entangled particle systems. For these systems, Einstein created the term
“spooky action at a distance”, which can be put in the following terms, if
information is instantly transmitted between correlated particles, it would be
in direct confrontation with special relativity theory. This was published in
Einstein et al.’s famous article EPR , entitled “Can Quantum-Mechanical
Description of Physical Reality Be Considered Complete?”, followed by one with
the same title by N. Bohr NB , defending a different vision. Another
motivation for this paper is examining the mystery of collapses of wave
functions in quantum mechanics.

All the aforementioned difficulties in interpreting the outcomes of quantum
mechanics inspired several attempts to complete the theory. We mention here
only some of them, such as another famous paper by D. Bohm, entitled “A
Suggested Interpretation of the Quantum Theory in Terms of ‘Hidden’ Variables”
BI , the Many-Words interpretation MWI , and more recently, the QBism
interpretation QBI1 ; QBI2 . In 1964, for entangled particles, Bell BT
proposed an inequality theorem, based on the hidden variables assumption in a
paper entitled “On the Einstein-Podolsky-Rosen Paradox”, and later experiments
Bex  have shown that Quantum Mechanics in fact gives the right predictions,
but this did not stop the interpretation discussions. A nice debate about
these interpretations (just to mention that the mysteries interpretations are
still very much “alive”) can be found in the World Science Festival, “Measure
for Measure: Quantum Physics and Reality”, a debate moderated by Brian Greene
with David Z. Albert, Sean Carroll, Sheldon Goldstein, and Ruëdiger Schack WSF
.

Quantum Mechanics is a very well established theory, and we will assume that
the reader is familiar with some of the most common text books that describe
it. References book1 -book5  are a few examples (used at our university), but
there exist many others. All these books follow what is known as the
Copenhagen paradigm. We will not make a revision of the theory here, and we
will cite and use known aspects of it without any formality.

The historical heart of the theory can be represented by the time-dependent
Schrödinger equation for a particle:

$i\hbar\frac{\partial\Psi({\vec{r}},t)}{\partial t}=H\Psi({\vec{r}},t)\;,$ (1)

where $\psi({\vec{r}},t)$ is the wave function of the particle in the time $t$
and $H$ is the Hamiltonian (it describes the environment of the particle). The
wave function is a map of possibilities of what can happen to the particle.
This equation allows the prediction of the future of the wave function,
$\psi({\vec{r}},t)$, at $t$, if we know this wave function,
$\psi({\vec{r}},t_{0})$, at a particular time $t_{0}$. The idea of predicting
the future of a particle, knowing its environment and its initial state
(position and velocity of the particle at time $t_{0}$), came from Isaac
Newton’s classical equations (which can be written in different forms, as the
Lagrangian equations, derived from the principle of least action, the
Hamilton-Jacobi equations, and others). Wave equations, like Eq. 1, spoil the
classical logic. Uncertainty relations, inherent to wave equations, prohibit
the precise knowledge of the position and velocity of a particle at the same
time. The Schrödinger equation predicts no specific trajectories, only
combinations of all possible trajectories (like in the Feynman formalism book1
). The most you can get is the knowledge of the wave function in the future
and everything you can extract from it. To solve Eq. 1 you need the
Hamiltonian and the wave function in a particular time of your choice (the
initial state). Academic Hamiltonians are relatively easy to assemble and the
task is made even easier if the quantum problem has a classical analog. Real
Hamiltonians, containing all sorts of traps and structures of the real world
that can interact with the particle, are often too difficult to write so that
we impose simplifications taking us towards the academic Hamiltonians, but
always aiming to be good approximations of the real Hamiltonians. On the other
hand, the initial state is impossible to determine without you or somebody (or
something) interfering in the system. The collapse of the wave function, as
being due to measurement, is well accepted in the Copenhagen paradigm of
Quantum Mechanics.

This leads us to our first interpretation rule: there is no way you can
determine the initial state of a particle beforehand, unless (i) you have
interfered in the system, by making a measurement of a particular observable
that causes the collapse of the original state to an eigenstate of your
observable or (ii) because nature (the environment) has collapsed NC  the
original state to a particular eigenstate of some observable, and you know
which one it is. Either way you have no idea about the original state (the
state prior to any of these collapses) of the system.

A good example for this rule is the oven of silver atoms in the Stern-Gerlach
experiment SG . There is nothing you can do to learn which spin state a given
silver atom is in, when it leaves the oven. Any attempt to measure the spin of
the atom will collapse the original state into an eigenstate associated with
the value of your measurement. The only information acquired about the
original state, after you have performed a measurement, is that it had the
component associated with your result. As discussed further on, this first
rule will explain the spooky action at a distance mystery EPR  of correlated
(entangled) particles.

You could argue that you know how to get the stationary states from Eq. 1, and
that the future of these states is very simple to predict since
$\psi({\vec{r}},t)=e^{-\frac{iE}{\hbar}(t-t_{0})}\psi({\vec{r}},t_{0})$.
Indeed, systems in stationary states are in a kind of quantum mechanics frozen
reality. This follows as the wave functions at different times differ among
themselves only by a phase factor, that does not affect any prediction about
the system. Hence, if you know that the system has collapsed to a particular
stationary state, it will be there forever (unless the environment acts on it,
like the broadening of the electronic lines of an excited atom, due to local
and non-local effects, that will eventually take the system to its ground
state - in this case you have a collapse due to the environment that nobody
needs to observe for it to happen). Stationary states, even for continuum
states, might thus be considered as boring because they represent a frozen
situation. Consider, for example, the free-particle wave function
$\psi({\vec{r}},t)=e^{-\frac{iE}{\hbar}(t-t_{0})}e^{i{\vec{p}}\cdot{\vec{r}}/\hbar}$.
This free-particle solution is obtained by assuming a very simplified
scenario, in which there is nothing in the universe besides the free particle
and that the space is homogeneous. Even the probability flux of this situation
behaves as a homogeneous river pointing in the ${\vec{k}}$ direction. The
situation gets more elaborate if you look for a solution for the scattering of
this particle against a target with structure (i.e. possessing internal
degrees of freedom). In this case, you can get probability fluxes for all
processes due to the collision of the particle against the structured target.
For this you have to include the structured target and its interaction with
the particle in the Hamiltonian, with the solution showing that the outgoing
particle may leave the target in any of the energetically possible states. You
don’t know which process will take place, but you know the probabilities
(related to the cross sections) of each one.

If you want to develop intuition for more abrupt changes in reality (with
respect to time), such as collapses of the wave function, you must first place
the particle in a particular region and throw it against the structured
target, for instance, the apparatus of a two slit interference experiment. For
this you need a combination of free solutions (which is also a solution),
where the combination places the particle within a wave packet centered at a
particular position. This packet center, not the particle, follows a classical
trajectory (the same as the classical free particle), and the particle, of
course, can only be found inside the wave packet. For a proper description of
this problem, the Hamiltonian of the system must contain the barrier and the
free passage through the two slits. Suppose we have sufficient detectors
(described in our Hamiltonian), so that the particle can be detected if it
bounces back or if it hits any place of the barrier. This set of detectors is
thus triggered only if the particle does not go through one of the slits. If
the particle’s collision against the detectors causes a click, the absence of
clicks would mean that the incident wave packet became two small packets
emerging from the slits. If you now place a sensitive screen in front of these
combined wave packets, you will produce a mark in this screen. Where? Wherever
the combination of the two packets is different from zero. For each particle,
we will have only one mark on the screen. The repetition of this experiment,
however, ultimately gives the well known interference pattern of the double-
slit experiment and it appears only if the wave packet goes through both
slits. If the act of an observer were to block one of the slits, the
interference pattern would disappear. If a particle interacts with the
environment (suppose that this may happen only when it passes through one of
the slits) the interference pattern also disappears, no matter if it is being
observed or not. The interaction with the environment represents a collapse,
which ensures that the particle really passed through one of the slits. Hence
the mark on the screen of a single particle experiment represents another
collapse of the wave function. If it happens in one place, it cannot happen in
any other place. There are no interference effects without diffraction. So the
observer in the double-slit experiment must be at least destroying (reshaping)
the diffraction pattern, due to each slit, in order to remove the interference
pattern. This can be done by focusing the beam, or something else, that
changes the photon/electron wave packet or/and the Hamiltonian.

This leads us to our second important interpretation rule, which is: the wave
function is just a map of possibilities and probabilities. The environment
(described by the Hamiltonian) shapes the wave packet, but the wave packet
does not change the environment. Only the particle (inside the packet) can
interact with the environment, and when that happens you have a collapse of
the wave packet. The map (this human invention) of probabilities and
possibilities zeroes out everywhere, except in the region where the
interaction with the environment took place.

Good examples book1 ; G  of Hamiltonians shaping the packets (in this case
split packets), are the Aharonov-Bohm effect experiment and the gravity-
induced quantum interference experiment. Now, let us use the above discussion
to reinterpret the Schrödinger’s cat experiment, to discuss the phenomenon of
correlation between two particles, and take a short look at the collapses.
Schrödinger’s cat:  Let us look at this with the help of the Stern-Gerlach
experiment. We have a poor cat inside a closed cage, tubed to receive gas from
two possible triggers. Outside we have an oven expelling silver atoms and a
Stern-Gerlach apparatus. One single atom enters the apparatus, and we have no
a priori idea if it will move up or down along the strongly varying magnetic
field. After going through the apparatus the associated wave packet is split
in two. If the particle goes up, it triggers (very sensitive multiplier) a cat
enjoyable perfume. If it goes down, it conversely triggers the Schrödinger
deadly poison gas. Our dynamic map says that the split packet hits the two
triggers at about the same time, but only one of them contains the particle.
Only the one containing the particle (rule 2) will trigger the respective
gases, the other packet piece will disappear with the collapse. Thus the cat
has never been in a mixed dead/alive state, namely it will be either dead or
alive depending on the spin state of the silver atom. Therefore the wave
function just represents a map of probabilities. When your detector finds a
particle you don’t even know if you had a split packet before the detection.
The collapse can happen instantly, respecting special relativity, because it
does not carry any information. Although you can induce collapses, exact
predictions of where it is going to happen are not defined by Eq. 1. This
equation only furnishes the quantum mechanics probabilistic rules. Hence the
theory seems to be complete, so that we just have to accept these imposed
limitations to predict the future.

Correlation between two particles:  The simplest case is a positronium atom in
its ground state (singlet state, total spin equals zero - if one particle has
spin up, in any direction, the other has spin down in the same direction). If
the atom is now taken apart (ionized), without changing the total angular
momentum, we have the well-established situation: if the positron has spin up
(down) the electron has spin down (up), as long as they are measured in the
same direction. The first important question derived from the above discussion
is: after the particles have been separated, can you tell that the system is
really correlated by making any kind of measurement on the positron or
electron particles? According to our interpretation rule 1, the answer is NO.
If you measure one particle with spin up and the other spin down, your only
conclusion is that this collapsed state was part of the original state. When
you measure the spin of one of the particles, the result you get is one of the
results you would get from an uncorrelated system. You cannot say anything
about the other particle, without being sure that the system is correlated.
This argument by itself addresses Einstein’s concerns about the non-locality
of quantum mechanics, as no message (information) is transmitted. The
preparation of the system involves a collapse with the following properties:
(1) the overall singlet state ensures that one spin particle is up and the
other is down, if measured in the same direction; (2) the separation ensures
that only one particle will be found on each location. The map (initial state)
could be represented by two wave packets of spin up and down on each location
(for any, but the same, direction). Note that if the direction of measurement
is not the same, any information revealed by the collapse becomes irrelevant
to the other measurement. For a given direction, if you find spin up at one
location, the spin down packet disappears at that location (i.e. there can be
only one particle on each side). The packet with spin up at the other location
also disappears (as one is spin up the other is spin down). The new map, due
to the measurement (new collapse), is the spin down on the other side and it
must contain a particle. If you want to consider the particle separation
process, imagine the pair being created in the same position (i.e. a
positronium formation in the singlet state). This state book1  can be written
as:

$|{\rm spin\ singlet}\rangle=\frac{1}{\sqrt{2}}(|\hat{\bf z}+;\hat{\bf
z}-\rangle-|\hat{\bf z}-;\hat{\bf z}+\rangle),$ (2)

and has the same form for any orientation. Suppose now a general rotation
represented by $\theta$ around the $y$-axis and $\varphi$ around the $z$-axis.
This gives that the same state (differing at most by a phase factor) can be
written, with the help of the kets, in the $\hat{\bf n}(\theta,\varphi)$
direction, by:

$|{\rm spin\ singlet}\rangle=\frac{1}{\sqrt{2}}(|\hat{\bf n}+;\hat{\bf
n}-\rangle-|\hat{\bf n}-;\hat{\bf n}+\rangle).$ (3)

This analysis shows that UP , at the birth of a singlet state of positronium
(where the two particles are in the same position), if you measure the spin of
one particle, in any direction, the other particle will have the opposite spin
in the same direction. If you now impose a Hamiltonian that separates the
particles with no spin dependencies, the spin map will be preserved. The
change in the probability map, caused by a measurement on one of the separated
particles, collapses the wave function instantaneously, without any
information transmitted between the particles. Besides, you can only store and
retrieve important information from this situation if you know that the system
is correlated and that no dissipative Hamiltonian’s act on it. This lies at
the heart of quantum computing and quantum teleportation.

Collapses:  Finally, let us understand that collapses happen all the time
without any observer. In the beginning of the universe we had a hot plasma,
and eventually electrons and protons, with their huge wave packets, found each
other to form Hydrogen atoms. Nobody was observing this. If you “throw” a high
energy electron against a gas or a surface, it will ionize along its path.
Every collision can cause a collapse of the wave function until the electron
is stopped and trapped, forming an atomic or molecular anion (the final
situation if nothing else happens). In the case of Schrödinger’s cat, the
collapse does not occur when the box is opened, but in the fact that,
invariably, the silver atom hits only one of the triggers and the state is
collapsed. Gravitational fields reshape wave packets all the time (star
formation is a good example), and again, no observer is necessary. The
observer in the double slit experiment can destroy the interference pattern by
acting on the map of probabilities and/or causing collapses, but it is
important to remember that nature (the environment) does this all the time and
quantum mechanics imposes tough but clear rules to predict where they can be.
Conclusion:  Einstein said: “I cannot seriously believe in (The Quantum
Theory) because it cannot be reconciled with the idea that physics should
represent a reality in time and in space, free from spooky actions at a
distance”. However, the brake of Bell’s inequality theorem supported the
Quantum Mechanics predictions. Reality in time and space may suggest that a
possible hidden variable theory could reveal a particular path between two
points, where this path is one of the (all possible) paths given by the
Feynman formalism. The path integral formalism is only equivalent to the
Schrödinger equation if all possible paths (in the probability map) are taken
into account. We therefore conclude that quantum mechanics is complete. Indeed
we only need to accept the idea that we cannot know everything. Our
interpretation rules 1 and 2 support this concept, clarifying the so-called
mysteries and thus helping to demystify quantum mechanics.

The first four authors are graduate students and their names appear in
alphabetical order. F.B.M. and M.A.P.L. acknowledge support from the Brazilian
agency Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
and A.E.D.B. from the Brazilian agency Fundação de Amparo à Pesquisa do Estado
de São Paulo (FAPESP). The authors are grateful to Profs. Marcus Aguiar
(UNICAMP, ResearcherID C-9137-2012) and Michael Brunger (Flinders University,
ResearcherID D-4733-2013) for their critical reading of the manuscript and
constructive comments and suggestions.

## References

  * (1) A. Druyan and B. Braga, Cosmos: Possible Worlds  (2020), Fuzzy Door Productions. Presented by Neil deGrasse Tyson, S1:E9 (17’), Magic Without Lies, National Geographic.
  * (2) A. Einstein, B. Podolsky, and N. Rosen, Phys. Rev. 47, 777 (1935).
  * (3) N. Bohr, Phys. Rev. 48, 696 (1935).
  * (4) D. Bohm, Phys. Rev. 85, 166 (1952).
  * (5) H. Everett, Rev. Mod. Phys. 29, 454 (1957).
  * (6) C. A. Fuchs, “QBism, the Perimeter of Quantum Bayesianism,” e-print arXiv:1003.5209 (2010).
  * (7) See also, C. A. Fuchs, N. D. Mermin, and R. Schack, Am. J. Phys. 82, 749 (2014).
  * (8) J. S. Bell, Physics 1, 195 (1964).
  * (9) S. J. Freedman and J. F. Clauser, Phys. Rev. Lett. 28, 938 (1972).
  * (10) Measure for Measure: Quantum Physics and Reality, World Science Festival (2014), hosted by Brian Greene. [Video]. https://www.worldsciencefestival.com/videos/measure-for-measure-quantum-physics-and-reality/.
  * (11) J.J. Sakurai e Jim Napolitano, Modern Quantum Mechanics (Addison-Wesley, Boston, 2011), 2nd edition.
  * (12) R. Shankar, Principles of Quantum Mechanics” (Springer, USA, 2014), 2nd edition.
  * (13) Claude Cohen-Tannoudji, Bernard Diu, Franck Laloë, Quantum Mechanics (John Wiley and Sons, Paris, 1977), Vols. 1 and 2.
  * (14) Nouredine Zettili, Quantum Mechanics, Concepts and applications (John Wiley and Sons, New York, 2001).
  * (15) Eugen Merzbacher, Quantum Mechanics (John Wiley and Sons, New York, 1998), 3rd edition.
  * (16) In the discussion about collapses, we give several examples.
  * (17) W. Gerlach and O. Stern, Zeitschrift für Physik 9, 353 (1922).
  * (18) A didactic approach discussing the reshaping of split wave packets may be found in Gabriela M. Amaral, David Q. Aruquipa, Ludwing F. M. Camacho, Luiz F. C. Faria, Sofía I. C. Guzmán, Damaris T. Maimone, Melissa Mendes, and Marco A. P. Lima, Revista Brasileira de Ensino de Física 38, e3309 (2016).
https://www.scielo.br/j/rbef/a/HjjLkdmb9z4Q5BkvfbhsFhm/?lang=en/.

  * (19) Since the state of the system can be generally written as in Eq. 3, if one wants to measure the spin along the $\hat{\bf n}^{\prime}$ direction, the easiest way to predict what is going to happen is to write the initial state as $|{\rm spin\ singlet}\rangle=\frac{1}{\sqrt{2}}(|\hat{\bf n}^{\prime}+;\hat{\bf n}^{\prime}-\rangle-|\hat{\bf n}^{\prime}-;\hat{\bf n}^{\prime}+\rangle)$. In this case, it is clear (done, for instance, in Ref. book1 ), using Eq. 2), that the measurement of the spin of particle one collapses the state to either the $|\hat{\bf n}^{\prime}+;\hat{\bf n}^{\prime}-\rangle$ or $|\hat{\bf n}^{\prime}-;\hat{\bf n}^{\prime}+\rangle$ state. The collapsed map says, if one find $+\hbar/2$ the other will find $-\hbar/2$ and vice-versa.