text:
# Avoiding Large Squares in Infinite Binary Words

## 1 Introduction

A square is a nonempty word of the form $`xx`$, as in the English word murmur. It is easy to see that every word of length $`4`$ constructed from the symbols $`0`$ and $`1`$ contains a square, so it is impossible to avoid squares in infinite binary words. However, in 1974, Entringer, Jackson, and Schatz  proved the surprising fact that there exists an infinite binary word containing no squares $`xx`$ with $`|x|3`$. Further, the bound $`3`$ is best possible.

A cube is a nonempty word of the form $`xxx`$, as in the English sort-of-word shshsh. Dekking  showed that there exists an infinite binary word that contains no cubes $`xxx`$ and no squares $`yy`$ with $`|y|4`$. Furthermore, the bound $`4`$ is best possible.

Dekking’s construction used iterated morphisms. By a morphism we understand a map $`h:\mathrm{\Sigma }^{}\mathrm{\Delta }^{}`$ such that $`h(xy)=h(x)h(y)`$ for all $`x,y\mathrm{\Sigma }^{}`$. A morphism may be specified by providing the image words $`h(a)`$ for all $`a\mathrm{\Sigma }`$. If $`h:\mathrm{\Sigma }^{}\mathrm{\Sigma }^{}`$ and $`h(a)=ax`$ for some letter $`a\mathrm{\Sigma }`$, then we say that $`h`$ is prolongable on $`a`$, and we can then iterate $`h`$ infinitely often to get the fixed point $`h^\omega (a):=axh(x)h^2(x)h^3(x)\mathrm{}`$.

A morphism is $`k`$-uniform if $`|h(a)|=k`$ for all $`a\mathrm{\Sigma }`$; it is uniform if it is $`k`$-uniform for some $`k`$. Uniform morphisms have particularly nice properties. For example, the class of words generated by iterating $`k`$-uniform morphisms coincides with the class of $`k`$-automatic sequences, generated by finite automata .

Dekking’s construction used a non-uniform morphism. In this paper we first show how to obtain, using the image of a uniform morphism, an infinite binary word that is cubefree and avoids squares $`yy`$ with $`|y|4`$. Our construction is somewhat simpler than Dekking’s.

Fraenkel and Simpson  strengthened the results of Entringer, Jackson, and Schatz by showing that there exists an infinite binary word avoiding all squares except $`0^2`$, $`1^2`$, and $`(01)^2`$. Their construction, however, was rather complicated, involving several steps and non-uniform morphisms. In this paper we show how to obtain a word where the only squares are $`0^2`$, $`1^2`$, and $`(01)^2`$, using a uniform morphism. Our construction is somewhat simpler than that of Fraenkel and Simpson.

We also consider the number of finite binary words satisfying the Dekking and Fraenkel-Simpson avoidance properties. We give exponential upper and lower bounds on this number in both cases.

Prodinger and Urbanek  also studied words avoiding large squares, in particular with reference to operations that preserve this property, such as the perfect shuffle SH . Let $`w=a_1a_2\mathrm{}a_n`$ and $`x=b_1b_2\mathrm{}b_n`$ be words of length $`n`$. The perfect shuffle $`w\text{SH}x`$ is defined to be the word $`a_1b_1a_2b_2\mathrm{}a_nb_n`$ of length $`2n`$. The definition can easily be extended to infinite words. They stated the following open question: do there exist two infinite words avoiding large squares such that their perfect shuffle has arbitrarily large squares? In this paper we resolve this question by exhibiting an example.

## 2 A cubefree word without arbitrarily long squares

In this section we construct an infinite cubefree binary word avoiding squares $`yy`$ with $`|y|4`$. The techniques we use are also used in later sections, so in this section we spell them out in some detail.

We introduce the following notation for alphabets: $`\mathrm{\Sigma }_k:=\{0,1,\mathrm{},k1\}`$.

###### Theorem 1

There is a squarefree infinite word over $`\mathrm{\Sigma }_4`$ with no occurrences of the subwords $`12`$, $`13`$, $`21`$, $`32`$, $`231`$, or $`10302`$.

Proof.  Let the morphism $`h`$ be defined by

$`0`$ $``$ $`0310201023`$
$`1`$ $``$ $`0310230102`$
$`2`$ $``$ $`0201031023`$
$`3`$ $``$ $`0203010201`$
Then we claim the fixed point $`h^\omega (0)`$ has the desired properties.

First, we claim that if $`w\mathrm{\Sigma }_4^{}`$ then $`h(w)`$ has no occurrences of $`12`$, $`13`$, $`21`$, $`32`$, $`231`$, or $`10302`$. For if any of these words occur as subwords of $`h(w)`$, they must occur within some $`h(a)`$ or straddling the boundary between $`h(a)`$ and $`h(b)`$, for some single letters $`a,b`$. They do not; this easy verification is left to the reader.

Next, we prove that if $`w`$ is any squarefree word over $`\mathrm{\Sigma }_4`$ having no occurrences of $`12`$, $`13`$, $`21`$, or $`32`$, then $`h(w)`$ is squarefree.

We argue by contradiction. Let $`w=a_1a_2\mathrm{}a_n`$ be a squarefree string such that $`h(w)`$ contains a square, i.e., $`h(w)=xyyz`$ for some $`x,z\mathrm{\Sigma }_4^{}`$, $`y\mathrm{\Sigma }_4^+`$. Without loss of generality, assume that $`w`$ is a shortest such string, so that $`0|x|,|z|<10`$.

Case 1: $`|y|20`$. In this case we can take $`|w|5`$. To verify that $`h(w)`$ is squarefree, it therefore suffices to check each of the 49 possible words $`w\mathrm{\Sigma }_4^5`$ to ensure that $`h(w)`$ is squarefree in each case.

Case 2: $`|y|>20`$. First, we establish the following result.

###### Lemma 2

* Suppose $`h(ab)=th(c)u`$ for some letters $`a,b,c\mathrm{\Sigma }_4`$ and strings $`t,u\mathrm{\Sigma }_4^{}`$. Then this inclusion is trivial (that is, $`t=ϵ`$ or $`u=ϵ`$) or $`u`$ is not a prefix of $`h(d)`$ for any $`d\mathrm{\Sigma }_4`$.
* Suppose there exist letters $`a,b,c`$ and strings $`s,t,u,v`$ such that $`h(a)=st`$, $`h(b)=uv`$, and $`h(c)=sv`$. Then either $`a=c`$ or $`b=c`$.

Proof.

* This can be verified with a short computation. In fact, the only $`a,b,c`$ for which the equality $`h(ab)=th(c)u`$ holds nontrivially is $`h(31)=th(2)u`$, and in this case $`t=020301`$, $`u=0102`$, so $`u`$ is not a prefix of any $`h(d)`$.
* This can also be verified with a short computation. If $`|s|6`$, then no two distinct letters have images under $`h`$ that share a prefix of length $`6`$. If $`|s|5`$, then $`|t|5`$, and no two distinct letters have images under $`h`$ that share a suffix of length $`5`$.

Once Lemma 2 is established, the rest of the argument is fairly standard. It can be found, for example, in , but for completeness we repeat it here.

For $`i=1,2,\mathrm{},n`$ define $`A_i=h(a_i)`$. Then if $`h(w)=xyyz`$, we can write

$$h(w)=A_1A_2\mathrm{}A_n=A_1^{}A_1^{\prime \prime }A_2\mathrm{}A_{j1}A_j^{}A_j^{\prime \prime }A_{j+1}\mathrm{}A_{n1}A_n^{}A_n^{\prime \prime }$$

where

$`A_1`$ $`=`$ $`A_1^{}A_1^{\prime \prime }`$
$`A_j`$ $`=`$ $`A_j^{}A_j^{\prime \prime }`$
$`A_n`$ $`=`$ $`A_n^{}A_n^{\prime \prime }`$
$`x`$ $`=`$ $`A_1^{}`$
$`y`$ $`=`$ $`A_1^{\prime \prime }A_2\mathrm{}A_{j1}A_j^{}=A_j^{\prime \prime }A_{j+1}\mathrm{}A_{n1}A_n^{}`$
$`z`$ $`=`$ $`A_n^{\prime \prime },`$
where $`|A_1^{\prime \prime }|,|A_j^{\prime \prime }|>0`$. See Figure 1.

If $`|A_1^{\prime \prime }|>|A_j^{\prime \prime }|`$, then $`A_{j+1}=h(a_{j+1})`$ is a subword of $`A_1^{\prime \prime }A_2`$, hence a subword of $`A_1A_2=h(a_1a_2)`$. Thus we can write $`A_{j+2}=A_{j+2}^{}A_{j+2}^{\prime \prime }`$ with

$$A_1^{\prime \prime }A_2=A_j^{\prime \prime }A_{j+1}A_{j+2}^{}.$$

See Figure 2.

But then, by Lemma 2 (a), either $`|A_j^{\prime \prime }|=0`$, or $`|A_1^{\prime \prime }|=|A_j^{\prime \prime }|`$, or $`A_{j+2}^{}`$ is a not a prefix of any $`h(d)`$. All three conclusions are impossible.

If $`|A_1^{\prime \prime }|<|A_j^{\prime \prime }|`$, then $`A_2=h(a_2)`$ is a subword of $`A_j^{\prime \prime }A_{j+1}`$, hence a subword of $`A_jA_{j+1}=h(a_ja_{j+1})`$. Thus we can write $`A_3=A_3^{}A_3^{\prime \prime }`$ with

$$A_1^{\prime \prime }A_2A_3^{}=A_j^{\prime \prime }A_{j+1}.$$

See Figure 3.

By Lemma 2 (a), either $`|A_1^{\prime \prime }|=0`$ or $`|A_1^{\prime \prime }|=|A_j^{\prime \prime }|`$ or $`A_3^{}`$ is not a prefix of any $`h(d)`$. Again, all three conclusions are impossible.

Therefore $`|A_1^{\prime \prime }|=|A_j^{\prime \prime }|`$. Hence $`A_1^{\prime \prime }=A_j^{\prime \prime }`$, $`A_2=A_{j+1}`$, $`\mathrm{}`$, $`A_{j1}=A_{n1}`$, and $`A_j^{}=A_n^{}`$. Since $`h`$ is injective, we have $`a_2=a_{j+1},\mathrm{},a_{j1}=a_{n1}`$. It also follows that $`|y|`$ is divisible by $`10`$ and $`A_j=A_j^{}A_j^{\prime \prime }=A_n^{}A_1^{\prime \prime }`$. But by Lemma 2 (b), either (1) $`a_j=a_n`$ or (2) $`a_j=a_1`$. In the first case, $`a_2\mathrm{}a_{j1}a_j=a_{j+1}\mathrm{}a_{n1}a_n`$, so $`w`$ contains the square $`(a_2\mathrm{}a_{j1}a_j)^2`$, a contradiction. In the second case, $`a_1\mathrm{}a_{j1}=a_ja_{j+1}\mathrm{}a_{n1}`$, so $`w`$ contains the square $`(a_1\mathrm{}a_{j1})^2`$, a contradiction.

It now follows that the infinite word

$$h^\omega (0)=03102010230203010201031023010203102010230201031023\mathrm{}$$

is squarefree and contains no occurrences of $`12`$, $`13`$, $`21`$, $`32`$, $`231`$, or $`10302`$.

###### Theorem 3

Let $`𝐰`$ be any infinite word satisfying the conditions of Theorem 1. Define a morphism $`g`$ by

$`0`$ $``$ $`010011`$
$`1`$ $``$ $`010110`$
$`2`$ $``$ $`011001`$
$`3`$ $``$ $`011010`$
Then $`g(𝐰)`$ is a cubefree word containing no squares $`xx`$ with $`|x|4`$.

Before we begin the proof, we remark that all the words $`12`$, $`13`$, $`21`$, $`32`$, $`231`$, $`10302`$ must indeed be avoided, because

$`g(12)`$ $`\text{contains the squares}(0110)^2,(1100)^2,(1001)^2`$
$`g(13)`$ $`\text{contains the square}(0110)^2`$
$`g(21)`$ $`\text{contains the cube}(01)^3`$
$`g(32)`$ $`\text{contains the square}(1001)^2`$
$`g(231)`$ $`\text{contains the square}(10010110)^2`$
$`g(10302)`$ $`\text{contains the square}(100100110110)^2.`$
Proof.  The proof parallels the proof of Theorem 1. Let $`w=a_1a_2\mathrm{}a_n`$ be a squarefree string, with no occurrences of $`12`$, $`13`$, $`21`$, $`32`$, $`231`$, or $`10302`$. We first establish that if $`g(w)=xyyz`$ for some $`x,z\mathrm{\Sigma }_4^{}`$, $`y\mathrm{\Sigma }_4^+`$, then $`|y|3`$. Without loss of generality, assume $`w`$ is a shortest such string, so $`0|x|,|z|<6`$.

Case 1: $`|y|12`$. In this case we can take $`|w|5`$. To verify that $`g(w)`$ contains no squares $`yy`$ with $`|y|4`$, it suffices to check each of the $`41`$ possible words $`w\mathrm{\Sigma }_4^5`$.

Case 2: $`|y|>12`$. First, we establish the analogue of Lemma 2.

###### Lemma 4

* Suppose $`g(ab)=tg(c)u`$ for some letters $`a,b,c\mathrm{\Sigma }_4`$ and strings $`t,u\mathrm{\Sigma }_4^{}`$. Then this inclusion is trivial (that is, $`t=ϵ`$ or $`u=ϵ`$) or $`u`$ is not a prefix of $`g(d)`$ for any $`d\mathrm{\Sigma }_4`$.
* Suppose there exist letters $`a,b,c`$ and strings $`s,t,u,v`$ such that $`g(a)=st`$, $`g(b)=uv`$, and $`g(c)=sv`$. Then either $`a=c`$ or $`b=c`$, or $`a=2`$, $`b=1`$, $`c=3`$, $`s=0110`$, $`t=01`$, $`u=0101`$, $`v=10`$.

Proof.

* This can be verified with a short computation. The only $`a,b,c`$ for which $`g(ab)=tg(c)u`$ holds nontrivially are

$`g(01)`$ $`=`$ $`010g(3)110`$
$`g(10)`$ $`=`$ $`01g(2)0011`$
$`g(23)`$ $`=`$ $`0110g(1)10.`$
But none of $`110`$, $`0011`$, $`10`$ are prefixes of any $`g(d)`$.
* If $`|s|5`$ then no two distinct letters have images under $`g`$ that share a prefix of length $`5`$. If $`|s|3`$ then $`|t|3`$, and no two distinct letters share a suffix of length $`3`$. Hence $`|s|=4`$, $`|t|=2`$. But only $`g(2)`$ and $`g(3)`$ share a prefix of length $`4`$, and only $`g(1)`$ and $`g(3)`$ share a suffix of length $`2`$.

The rest of the proof is exactly parallel to the proof of Theorem 1, with the following exception. When we get to the final case, where $`|y|`$ is divisible by $`6`$, we can use Lemma 4 to rule out every case except where $`x=0101`$, $`z=01`$, $`a_1=1`$, $`a_j=3`$, and $`a_n=2`$. Thus $`w=1\alpha 3\alpha 2`$ for some string $`\alpha \mathrm{\Sigma }_4^{}`$. This special case is ruled out by the following lemma:

###### Lemma 5

Suppose $`\alpha \mathrm{\Sigma }_4^{}`$, and let $`w=1\alpha 3\alpha 2`$. Then either $`w`$ contains a square, or $`w`$ contains an occurrence of one of the subwords $`12`$, $`13`$, $`21`$, $`32`$, $`231`$, or $`10302`$.

Proof.  This can be verified by checking (a) all strings $`w`$ with $`|w|4`$, and (b) all strings of the form $`w=abcw^{}de`$, where $`a,b,c,d,e\mathrm{\Sigma }_4`$ and $`w^{}\mathrm{\Sigma }_4^{}`$. (Here $`w^{}`$ may be treated as an indeterminate.)

It now remains to show that if $`w`$ is squarefree and contains no occurrence of $`12`$, $`13`$, $`21`$, $`32`$, $`231`$, or $`10302`$, then $`g(w)`$ is cubefree. If $`g(w)`$ contains a cube $`yyy`$, then it contains a square $`yy`$, and from what precedes we know $`|y|3`$. It therefore suffices to show that $`g(w)`$ contains no occurrence of $`0^3`$, $`1^3`$, $`(01)^3`$, $`(10)^3`$, $`(001)^3`$, $`(010)^3`$, $`(011)^3`$, $`(100)^3`$, $`(101)^3`$, $`(110)^3`$. The longest such string is of length $`9`$, so it suffices to examine the $`16`$ possibilities for $`g(w)`$ where $`|w|=3`$. This is left to the reader.

The proof of Theorem 3 is now complete.

###### Corollary 6

If $`g`$ and $`h`$ are defined as above, then

$$g(h^\omega (0))=010011011010010110010011011001010011010110010011011001011010\mathrm{}$$

is cubefree, and avoids all squares $`xx`$ with $`|x|4`$.

Next, based on the morphism $`h`$, we define the substitution $`h^{}:\mathrm{\Sigma }_4^{}2^{\mathrm{\Sigma }_4^{}}`$ as follows:

$`0`$ $``$ $`\{h(0)\}`$
$`1`$ $``$ $`\{h(1),0310230201\}`$
$`2`$ $``$ $`\{h(2)\}`$
$`3`$ $``$ $`\{h(3)\}`$
Thus, if $`w\mathrm{\Sigma }_4^{}`$, $`h^{}(w)`$ is a language of $`2^r`$ words over $`\mathrm{\Sigma }_4`$, where $`r=|w|_1`$. Each of these words is of length $`10|w|`$.

###### Lemma 7

Let $`g`$, $`h`$, and $`h^{}`$ be defined as above. Let $`w=h^m(0)`$ for some positive integer $`m`$. Then $`g(h^{}(w))`$ is a language of $`2^{n/300}`$ words over $`\mathrm{\Sigma }_2`$, where $`n=6010^m`$ is the length of each of these words. Furthermore, each of these words is cubefree and avoids all squares $`xx`$ with $`|x|4`$.

Proof.  Note that there are exactly two 1’s in every image word of $`h`$. Hence, $`|w|_1=\frac{1}{5}|w|=\frac{1}{5}10^m`$. We have then that $`g(h^{}(w))`$ consists of $`2^{\frac{1}{5}10^m}`$ binary words. Since $`n=61010^m`$, we see that $`g(h^{}(w))`$ consists of $`2^{n/300}`$ words.

To see that the words in $`g(h^{}(w))`$ are cubefree and avoid all squares $`xx`$ with $`|x|4`$, it suffices by Theorem 3 to show that the words in $`h^{}(w)`$ are squarefree and contain no occurrences of the subwords 12, 13, 21, 32, 231, or 10302. By the same reasoning as in Theorem 1, the reader may easily verify that no word in $`h^{}(w)`$ contains an occurrence of 12, 13, 21, 32, 231, or 10302.

To show that the words in $`h^{}(w)`$ are squarefree, we will, as a notational convenience, prefer to consider $`h^{}`$ to be a morphism defined as follows:

$`0`$ $``$ $`h(0)`$
$`1`$ $``$ $`h(1)`$
$`\widehat{1}`$ $``$ $`0310230201`$
$`2`$ $``$ $`h(2)`$
$`3`$ $``$ $`h(3)`$
Here, 1 and $`\widehat{1}`$ are considered to be the same alphabet symbol; the ‘hat’ simply serves to distinguish between which choice is made for the substitution. To show that $`h^{}(w)`$ is squarefree, it suffices to show that $`h^{}`$ satisfies the conditions of Lemma 2. For Lemma 2 (a) we have $`h^{}(22)=th^{}(\widehat{1})u`$, but we can rule this case out since $`w`$ avoids the square 22. For Lemma 2 (b) we again have that no two distinct letters have images under $`h^{}`$ that share a prefix of length 6 or a suffix of length 5 (since 1 and $`\widehat{1}`$ are not considered to be distinct letters). Hence, $`h^{}`$ satisfies the conditions of Lemma 2, and so $`h^{}(w)`$ is squarefree.

###### Theorem 8

Let $`G_n`$ denote the number of cubefree binary words of length $`n`$ that avoid all squares $`xx`$ with $`|x|4`$. Then $`G_n=\mathrm{\Omega }(1.002^n)`$ and $`G_n=O(1.178^n)`$.

Proof.  Noting that $`2^{1/300}1.002`$, we see that the lower bound follows immediately from Lemma 7.

For the upper bound we reason as follows. The set of binary words of length $`n`$ avoiding cubes and squares $`xx`$ with $`|x|4`$ is a a subset of the set of binary words avoiding 000 and 111. The number $`G_n^{}`$ of binary words avoiding 000 and 111 satisfies the linear recurrence $`G_n^{}=G_{n1}^{}+G_{n2}^{}`$ for $`n3`$. From well-known properties of linear recurrences, it follows that $`G_n^{}=O(\alpha ^n)`$, where $`\alpha `$ is the largest zero of $`x^2x1`$, the characteristic polynomial of the recurrence. Here $`\alpha <1.618`$, so $`G_n^{}=O(1.618^n)`$.

This argument can be extended by using a symbolic algebra package such as Maple. Noonan and Zeilberger  have written a Maple package, `DAVID_IAN`, that allows one to specify a list $`L`$ of forbidden words, and computes the generating function enumerating words avoiding members of $`L`$. We used the package for a list $`L`$ of 90 words of length $`20`$:

$$000,111,\mathrm{},11011001001101100100$$

obtaining a characteristic polynomial of degree 44 with dominant root $`1.178`$.

The following table gives the number $`G_n`$ of binary words of length $`n`$ avoiding both cubes $`xxx`$ and squares $`y`$ with $`|y|4`$.

| $`n`$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $`G_n`$ | 1 | 2 | 4 | 6 | 10 | 16 | 24 | 36 | 52 | 72 | 90 | 116 | 142 | 178 | 220 | 264 | 332 | 414 |

## 3 A uniform version of Fraenkel-Simpson

In this section we construct an infinite binary word avoiding all squares except $`0^2`$, $`1^2`$, and $`(01)^2`$.

Roughly speaking, verifying that the image of a morphism avoids arbitrarily large squares breaks up into two parts: checking a finite number of “small” squares, and checking an infinite number of “large” squares. The small squares can be checked by brute force, while for the large squares we need a version of Lemma 2. Referring to Lemma 2 (a), if $`h(c)`$ is a subword of $`h(ab)`$ for some letters $`a,b,c`$, we call this an “inclusion”. Inclusions can be ruled out either by considering prefixes, as we did in Lemma 2 (a), or suffixes. Referring to Lemma 2 (b), if $`h(a)=st`$, $`h(b)=uv`$, and $`h(c)=sv`$, we call that an “interchange”.

The basic idea of the proofs in this section parallels that of the previous section, so we just sketch the basic ideas, pointing out the properties of the inclusions and interchanges.

Consider the 24-uniform morphism $`h`$ defined as follows:

$`0`$ $``$ $`012321012340121012321234`$
$`1`$ $``$ $`012101234323401234321234`$
$`2`$ $``$ $`012101232123401232101234`$
$`3`$ $``$ $`012321234323401232101234`$
$`4`$ $``$ $`012321234012101234321234`$
###### Theorem 9

If $`w\mathrm{\Sigma }_5^{}`$ is squarefree and avoids the patterns $`02,03,04,14,20,30,41`$, then $`h(w)`$ is squarefree and avoids the patterns $`02,03,04,13,14,20,24,30,31,41,42,010,434`$.

Proof.  The only inclusion is $`h(32)=0123212343234h(0)01232101234`$, and $`0123212343234`$ is not a suffix of the image of any letter.

There are no interchanges for this morphism.

Now consider the 6-uniform morphism

$`g(0)`$ $`=`$ $`011100`$
$`g(1)`$ $`=`$ $`101100`$
$`g(2)`$ $`=`$ $`111000`$
$`g(3)`$ $`=`$ $`110010`$
$`g(4)`$ $`=`$ $`110001`$
###### Theorem 10

If $`w`$ is squarefree and avoids the patterns $`02,03,04,13,14,20,24,30,31,41,42,434010`$ then the only squares in $`g(w)`$ are $`00,11,0101`$.

Proof.

There are no examples of interchanges for $`g`$.

There are multiple examples of inclusions, but many of them can be ruled out by properties of $`w`$ and $`g`$:

* $`g(02)=01110g(0)0`$ but $`02`$ cannot occur
* $`g(24)=1g(4)10001`$ but $`24`$ cannot occur
* $`g(12)=10110g(0)0`$ but $`10110`$ is not a suffix of any $`g(a)`$
* $`g(32)=11001g(0)0`$ but $`11001`$ is not a suffix of any $`g(a)`$
* $`g(21)=1g(4)01100`$ but $`01100`$ is not a prefix of any $`g(a)`$
* $`g(23)=1g(4)10010`$ but $`10010`$ is not a prefix of any $`g(a)`$

Since $`g(434010)=1100(01110010110001)^21100`$, we need a special argument to rule this out. There are four special cases that must be handled:

* $`g(43)=1100g(0)10`$
* $`g(34)=1100g(1)01`$
* $`g(01)=01g(3)1100`$
* $`g(10)=10g(4)1100`$

In the first example, $`g(43)=1100g(0)10`$, since $`10`$ is only a prefix of $`g(1)`$, we can extend on the right to get $`g(43)1100=1100g(01)`$. But since $`1100`$ is only a prefix of $`g(3)`$ or $`g(4)`$, this gives either the forbidden pattern $`33`$ or the forbidden pattern $`434`$.

In the second example, $`g(34)=1100g(1)01`$, since $`01`$ is only a prefix of $`g(0)`$, we can extend on the right to get $`g(34)1100=1100g(10)`$. But $`1100`$ is a suffix of only $`g(0)`$ and $`g(1)`$, so on the right we get either the forbidden pattern $`010`$ or the forbidden pattern $`11`$.

The other two cases are handled similarly.

As in the previous section, we now define the substitution $`h^{}:\mathrm{\Sigma }_5^{}2^{\mathrm{\Sigma }_5^{}}`$ as follows:

$`0`$ $``$ $`\{h(0),012101232123401234321234\}`$
$`1`$ $``$ $`\{h(1)\}`$
$`2`$ $``$ $`\{h(2)\}`$
$`3`$ $``$ $`\{h(3)\}`$
$`4`$ $``$ $`\{h(4)\}`$
Thus, if $`w\mathrm{\Sigma }_5^{}`$, $`h^{}(w)`$ is a language of $`2^r`$ words over $`\mathrm{\Sigma }_5`$, where $`r=|w|_0`$. Each of these words is of length $`24|w|`$.

###### Lemma 11

Let $`g`$, $`h`$, and $`h^{}`$ be defined as above. Let $`w=h^m(0)`$ for some positive integer $`m`$. Then $`g(h^{}(w))`$ is a language of $`2^{n/1152}`$ words over $`\mathrm{\Sigma }_2`$, where $`n=14424^m`$ is the length of each of these words. Furthermore, these words avoid all squares except $`0^2`$, $`1^2`$, and $`(01)^2`$.

Proof.  The proof is analogous to that of Lemma 7. Note that there are at least three 0’s in every image word of $`h`$. Hence, $`|w|_0\frac{1}{8}|w|=\frac{1}{8}24^m`$. We have then that $`g(h^{}(w))`$ consists of at least $`2^{\frac{1}{8}24^m}`$ binary words. Since $`n=62424^m`$, we see that $`g(h^{}(w))`$ consists of at least $`2^{n/1152}`$ words.

To see that the words in $`g(h^{}(w))`$ avoid all squares except $`0^2`$, $`1^2`$, and $`(01)^2`$ it suffices by Theorem 10 to show that the words in $`h^{}(w)`$ are squarefree and contain no occurrences of the subwords 02, 03, 04, 13, 14, 20, 24, 30, 31, 41, 42, or 434010. The reader may easily verify that the words in $`h^{}(w)`$ contain no occurrences of the subwords 02, 03, 04, 13, 14, 20, 24, 30, 31, 41, 42, or 434010.

To show that the words in $`h^{}(w)`$ are squarefree, we will, as before, consider $`h^{}`$ to be a morphism defined as follows:

$`0`$ $``$ $`h(0)`$
$`\widehat{0}`$ $``$ $`012101232123401234321234`$
$`1`$ $``$ $`h(1)`$
$`2`$ $``$ $`h(2)`$
$`3`$ $``$ $`h(3)`$
$`4`$ $``$ $`h(4)`$
There are no inclusions for $`h^{}`$ other than the one identified in the proof of Theorem 9. There are three interchanges: referring to Lemma 2 (b), we have that $`(a,b,c)\{(2,1,\widehat{0}),(2,4,\widehat{0}),(\widehat{0},3,2)\}`$ satisfies $`h^{}(a)=st`$, $`h^{}(b)=uv`$, and $`h^{}(c)=sv`$. We may rule out the first two cases by showing that $`w`$ avoids all subwords of the form $`1\alpha 0\alpha 2`$ and $`4\alpha 0\alpha 2`$, where $`\alpha \mathrm{\Sigma }_5^{}`$. Note that in the word $`w`$, any occurrence of 0 must be followed by a 1, since $`w`$ avoids the patterns 02, 03, and 04. Let $`x`$ be a subword of $`w`$ of the form $`1\alpha 0\alpha 2`$ or $`4\alpha 0\alpha 2`$. Then $`x`$ must begin with 11 or 41. This is a contradiction, as $`w`$ avoids both 11 and 41.

We may rule out the third case by showing that $`w`$ avoids all subwords of the form $`3\alpha 2\alpha 0`$, where $`\alpha \mathrm{\Sigma }_5^{}`$. Note that in the word $`w`$, any occurrence of 2 must be followed by either 1 or 3, since $`w`$ avoids the patterns 20 and 24. Let $`x`$ be a subword of $`w`$ of the form $`3\alpha 2\alpha 0`$. Then $`x`$ must begin with 31 or 33. This is a contradiction, as $`w`$ avoids both 31 and 33.

###### Theorem 12

Let $`H_n`$ denote the number of binary words of length $`n`$ that avoid all squares except $`0^2`$, $`1^2`$, and $`(01)^2`$. Then $`H_n=\mathrm{\Omega }(1.0006^n)`$ and $`H_n=O(1.135^n)`$.

Proof.  The proof is analogous to that of Theorem 8. Noting that $`2^{1/1152}1.0006`$, we see that the lower bound follows immediately from Lemma 11.

For the upper bound, we again used the `DAVID_IAN` Maple package for a list of 65 words of length $`20`$:

$$0000,1010,\mathrm{},1110001011100010$$

obtaining a characteristic polynomial of degree 58 with dominant root $`1.135`$.

The following table gives the number $`H_n`$ of binary words of length $`n`$ containing only the squares $`0^2`$, $`1^2`$, and $`(01)^2`$.

| $`n`$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $`H_n`$ | 1 | 2 | 4 | 8 | 13 | 22 | 31 | 46 | 58 | 78 | 99 | 124 | 144 | 176 | 198 | 234 | 262 | 300 | 351 |

## 4 The Prodinger-Urbanek problem

Prodinger and Urbanek  stated they were unable to find an example of two infinite binary words avoiding large squares such that their perfect shuffle had arbitrarily large squares. In this section we give an example of such words.

###### Theorem 13

There exist two infinite binary words $`𝐱`$ and $`𝐲`$ such that neither $`𝐱`$ nor $`𝐲`$ contain a square $`ww`$ with $`|w|4`$, but $`𝐱\text{SH}𝐲`$ contains arbitrarily large squares.

Proof.  Consider the morphism $`f:\mathrm{\Sigma }_2^{}\mathrm{\Sigma }_2^{}`$ defined as follows:

$`f(0)`$ $`=`$ $`001`$
$`f(1)`$ $`=`$ $`110.`$
We will show that $`f^\omega (0)=001001110001001110110110001\mathrm{}`$ contains arbitrarily large squares and is the perfect shuffle of two words, each avoiding squares $`ww`$ with $`|w|4`$.

First, we define the morphisms $`h:\mathrm{\Sigma }_4^{}\mathrm{\Sigma }_4^{}`$, $`g_1:\mathrm{\Sigma }_4^{}\mathrm{\Sigma }_2^{}`$, and $`g_2:\mathrm{\Sigma }_4^{}\mathrm{\Sigma }_2^{}`$ defined as follows:

$`h(0)`$ $`=`$ $`012`$
$`h(1)`$ $`=`$ $`302`$
$`h(2)`$ $`=`$ $`031`$
$`h(3)`$ $`=`$ $`321,`$
$`g_1(0)`$ $`=`$ $`001`$
$`g_1(1)`$ $`=`$ $`101`$
$`g_1(2)`$ $`=`$ $`010`$
$`g_1(3)`$ $`=`$ $`110,`$
and

$`g_2(0)`$ $`=`$ $`010`$
$`g_2(1)`$ $`=`$ $`100`$
$`g_2(2)`$ $`=`$ $`011`$
$`g_2(3)`$ $`=`$ $`101.`$
We now show

###### Lemma 14

$`f^\omega (0)=g_2(h^\omega (0))\text{SH}g_1(h^\omega (0)).`$

Proof.  We prove the following identities by induction on $`n`$.

$`f^{n+1}(00)`$ $`=`$ $`g_2(h^n(0))\text{SH}g_1(h^n(0))`$ (1)
$`f^{n+1}(10)`$ $`=`$ $`g_2(h^n(1))\text{SH}g_1(h^n(1))`$ (2)
$`f^{n+1}(01)`$ $`=`$ $`g_2(h^n(2))\text{SH}g_1(h^n(2))`$ (3)
$`f^{n+1}(11)`$ $`=`$ $`g_2(h^n(3))\text{SH}g_1(h^n(3))`$ (4)
It is easy to verify that these equations hold for $`n=0`$. We assume that they hold for $`n=k`$, where $`k>0`$, and show that they hold for $`n=k+1`$. We first consider $`f^{k+2}(00)`$, where we have

$`f^{k+2}(00)`$ $`=`$ $`f^{k+1}(001001)`$
$`=`$ $`f^{k+1}(00)f^{k+1}(10)f^{k+1}(01)`$
$`=`$ $`\left(g_2(h^k(0))\text{SH}g_1(h^k(0))\right)\left(g_2(h^k(1))\text{SH}g_1(h^k(1))\right)\left(g_2(h^k(2))\text{SH}g_1(h^k(2))\right)`$
$`=`$ $`\left(g_2(h^k(0))g_2(h^k(1))g_2(h^k(2))\right)\text{SH}\left(g_1(h^k(0))g_1(h^k(1))g_1(h^k(2))\right)`$
$`=`$ $`g_2(h^k(0)h^k(1)h^k(2))\text{SH}g_1(h^k(0)h^k(1)h^k(2))`$
$`=`$ $`g_2(h^k(012))\text{SH}g_1(h^k(012))`$
$`=`$ $`g_2(h^{k+1}(0))\text{SH}g_1(h^{k+1}(0))`$
as desired. The other cases of the induction for $`f^{k+2}(10),f^{k+2}(01)`$, and $`f^{k+2}(11)`$ follow similarly. The result now follows from (1).

We now prove

###### Lemma 15

The infinite word $`h^\omega (0)`$ is squarefree.

Proof.  This follows immediately by the analogue of Lemma 2. An easy computation shows there are no inclusions or interchanges for $`h`$.

We now define

$$𝒜=\{010,013,021,030,032,102,121,131,202,212,231,301,303,312,320,323\}.$$

###### Lemma 16

1. $`h^\omega (0)`$ contains no subwords $`x`$ where $`x𝒜`$; and
2. $`h^\omega (0)`$ contains no subwords of the form $`0\alpha 1\alpha 3`$, $`1\alpha 0\alpha 2`$, $`2\alpha 3\alpha 1`$, or $`3\alpha 2\alpha 0`$, where $`\alpha \mathrm{\Sigma }_4^{}`$.

Proof.

1. This can be verified by inspection.
2. We argue by contradiction. Let $`w`$ be a shortest subword of $`h^\omega (0)`$ such that $`w`$ is of the form $`0\alpha 1\alpha 3`$, $`1\alpha 0\alpha 2`$, $`2\alpha 3\alpha 1`$, or $`3\alpha 2\alpha 0`$. Suppose $`w`$ is of the form $`0\alpha 1\alpha 3`$. Note that the only image words of $`h`$ that contain the letter 1 are $`h(0)=012`$, $`h(2)=031`$, and $`h(3)=321`$. Hence it must be the case that $`\alpha `$ is of the form $`2\alpha ^{}0`$, $`\alpha ^{}03`$, or $`\alpha ^{}32`$ for some $`\alpha ^{}\mathrm{\Sigma }_4^{}`$. We therefore have three cases.

1. $`w=02\alpha ^{}012\alpha ^{}03`$ for some $`\alpha ^{}\mathrm{\Sigma }_4^{}`$. We have two subcases.

    1. $`|w|12`$. A short computation suffices to verify that, contrary to (a), all words $`w`$ of the form $`02\alpha ^{}012\alpha ^{}03`$ with $`|w|12`$ contain a subword $`x`$ where $`x𝒜`$.
        2. $`|w|>12`$. We first make the observation that any image word of $`h`$ is uniquely specified by its first two letters and also by its last two letters. Thus, if $`w=02\alpha ^{}012\alpha ^{}03`$, it must be the case that $`3w1=302\alpha ^{}012\alpha ^{}031=h(1)\alpha ^{}h(0)\alpha ^{}h(2)`$ is also a subword of $`h^\omega (0)`$. Furthermore, since $`h`$ has no inclusions, the infinite word $`h^\omega (0)`$ can be uniquely parsed into image words of $`h`$. Since we have that $`h(1)\alpha ^{}h(0)\alpha ^{}h(2)`$ is a subword of $`h^\omega (0)`$, this implies that $`|\alpha ^{}|`$ is a multiple of 3 and that $`h(1)\alpha ^{}h(0)\alpha ^{}h(2)=h(1\beta 0\beta 2)`$ for some $`\beta \mathrm{\Sigma }_4^{}`$, $`|\beta |<|\alpha ^{}|`$. So $`1\beta 0\beta 2`$ must also be a subword of $`h^\omega (0)`$. This contradicts the minimality of $`w`$.
    2. $`w=0\alpha ^{}031\alpha ^{}033`$ for some $`\alpha ^{}\mathrm{\Sigma }_4^{}`$. But then $`w`$ contains the square 33, contrary to Lemma 15.
    3. $`w=0\alpha ^{}321\alpha ^{}323`$ for some $`\alpha ^{}\mathrm{\Sigma }_4^{}`$. But by (a) $`w`$ cannot contain the subword 323.

The cases where $`w`$ is of the form $`1\alpha 0\alpha 2`$, $`2\alpha 3\alpha 1`$, or $`3\alpha 0\alpha 2`$ follow similarly.

We now give the analogue of Lemma 2 for $`g_1`$ and $`g_2`$. Let $`g_i`$ represent either $`g_1`$ or $`g_2`$. Then we have

###### Lemma 17

1. Suppose $`g_i(ab)=tg_i(c)u`$ for some letters $`a,b,c\mathrm{\Sigma }_4`$ and words $`t,u\mathrm{\Sigma }_2^{}`$. Then at least one of the following holds:

1. this inclusion is trivial (that is, $`t=ϵ`$ or $`u=ϵ`$);
    2. $`u`$ is not a prefix of $`g_i(d)`$ for any $`d\mathrm{\Sigma }_4`$;
    3. $`t`$ is not a suffix of $`g_i(d)`$ for any $`d\mathrm{\Sigma }_4`$; or
    4. for all $`v,w\mathrm{\Sigma }_2^{}`$ and all $`e,e^{}\mathrm{\Sigma }_4`$, if $`vg_i(ab)w=g_i(ece^{})`$, then at least one of the following holds:

    1. this inclusion is trivial (that is, $`v=ϵ`$ or $`w=ϵ`$);
        2. $`w`$ is not a prefix of $`g_i(d)`$ for any $`d\mathrm{\Sigma }_4`$;
        3. $`v`$ is not a suffix of $`g_i(d)`$ for any $`d\mathrm{\Sigma }_4`$;
        4. either $`e=c`$ or $`e^{}=c`$;
        5. $`ece^{}𝒜`$;
        6. for all $`x,y\mathrm{\Sigma }_2`$ and all $`k\mathrm{\Sigma }_4`$, if $`g_i(kab)x=yg_i(ece^{})`$, then $`k=a`$; or
        7. for all $`x,y\mathrm{\Sigma }_2`$ and all $`k\mathrm{\Sigma }_4`$, if $`xg_i(abk)=g_i(ece^{})y`$, then $`k=b`$.
2. Suppose there exist letters $`a,b,c\mathrm{\Sigma }_4`$ and words $`s,t,u,v\mathrm{\Sigma }_2^{}`$ such that $`g_i(a)=st`$, $`g_i(b)=uv`$, $`g_i(c)=sv`$, and $`b\alpha c\alpha a`$ is a subword of $`h^\omega (0)`$ for some $`\alpha \mathrm{\Sigma }_4^{}`$. Then either $`a=c`$ or $`b=c`$.

Proof.

1. We give one example of each case and list the other non-trivial cases in a table below.

1. Trivial.
    2. $`g_2(32)=1g_2(0)11`$, but 11 is not a prefix of $`g_2(d)`$ for any $`d\mathrm{\Sigma }_4`$.
    3. $`g_1(02)=00g_1(1)0`$, but 00 is not a suffix of $`g_1(d)`$ for any $`d\mathrm{\Sigma }_4`$.
    4. 1. Trivial.
        2. $`g_2(01)=01g_2(0)0`$ and $`1g_2(01)11=g_2(302)`$, but 11 is not a prefix of $`g_2(d)`$ for any $`d\mathrm{\Sigma }_4`$.
        3. $`g_1(31)=1g_1(1)01`$ and $`00g_1(31)0=g_1(012)`$, but 00 is not a suffix of $`g_1(d)`$ for any $`d\mathrm{\Sigma }_4`$.
        4. $`g_1(23)=0g_1(1)10`$ and $`01g_1(23)1=g_1(211)`$, but $`e^{}=c=1`$.
        5. $`g_1(21)=0g_1(1)01`$ and $`01g_1(21)0=g_1(212)`$, but $`ece^{}=212𝒜`$.
        6. $`g_2(30)=1g_2(0)10`$, $`01g_2(30)0=g_2(201)`$, and $`g_2(330)0=1g_2(201)`$, but $`k=a=3`$.
        7. $`g_1(12)=10g_1(1)0`$, $`0g_1(12)01=g_1(210)`$, and $`0g_1(122)=g_1(210)0`$, but $`k=b=2`$.

| Case | $`g_i(ab)=tg_i(c)u`$ | $`vg_i(ab)w=g_i(ece^{})`$ | $`g_i(kab)x=yg_i(ece^{})`$ or |
| --- | --- | --- | --- |
|  |  |  | $`xg_i(abk)=g_i(ece^{})y`$ |
| a.ii | $`g_2(01)=0g_2(3)\mathrm{𝟎𝟎}`$ | - | - |
|  | $`g_2(02)=0g_2(1)\mathrm{𝟏𝟏}`$ | - | - |
|  | $`g_2(31)=1g_2(2)\mathrm{𝟎𝟎}`$ | - | - |
|  | $`g_2(32)=1g_2(0)\mathrm{𝟏𝟏}`$ | - | - |
| a.iii | $`g_1(01)=\mathrm{𝟎𝟎}g_1(3)1`$ | - | - |
|  | $`g_1(02)=\mathrm{𝟎𝟎}g_1(1)0`$ | - | - |
|  | $`g_1(31)=\mathrm{𝟏𝟏}g_1(2)1`$ | - | - |
|  | $`g_1(32)=\mathrm{𝟏𝟏}g_1(0)0`$ | - | - |
| a.iv.B | $`g_2(01)=01g_2(0)0`$ | $`1g_2(01)\mathrm{𝟏𝟏}=g_2(302)`$ | - |
|  | $`g_2(32)=10g_2(3)1`$ | $`0g_2(32)\mathrm{𝟎𝟎}=g_2(031)`$ | - |
| a.iv.C | $`g_1(02)=0g_1(2)10`$ | $`\mathrm{𝟏𝟏}g_1(02)1=g_1(321)`$ | - |
|  | $`g_1(31)=1g_1(1)01`$ | $`\mathrm{𝟎𝟎}g_1(31)0=g_1(012)`$ | - |

Table 1: Forbidden Patterns in the Proof of Lemma 17

| Case | $`g_i(ab)=tg_i(c)u`$ | $`vg_i(ab)w=g_i(ece^{})`$ | $`g_i(kab)x=yg_i(ece^{})`$ or |
| --- | --- | --- | --- |
|  |  |  | $`xg_i(abk)=g_i(ece^{})y`$ |
| a.iv.D | $`g_1(10)=1g_1(2)01`$ | $`00g_1(02)0=g_1(0\mathrm{𝟐𝟐})`$ | - |
|  | $`g_1(10)=1g_1(2)01`$ | $`10g_1(02)0=g_1(1\mathrm{𝟐𝟐})`$ | - |
|  | $`g_1(02)=0g_1(2)10`$ | $`01g_1(02)1=g_1(\mathrm{𝟐𝟐}1)`$ | - |
|  | $`g_1(23)=0g_1(1)10`$ | $`01g_1(23)1=g_1(2\mathrm{𝟏𝟏})`$ | - |
|  | $`g_1(23)=0g_1(1)10`$ | $`11g_1(23)1=g_1(3\mathrm{𝟏𝟏})`$ | - |
|  | $`g_1(31)=1g_1(1)01`$ | $`10g_1(31)0=g_1(\mathrm{𝟏𝟏}2)`$ | - |
|  | $`g_2(01)=1g_2(2)01`$ | $`1g_2(01)10=g_2(3\mathrm{𝟎𝟎})`$ | - |
|  | $`g_2(13)=1g_2(2)01`$ | $`0g_2(13)00=g_2(\mathrm{𝟎𝟎}1)`$ | - |
|  | $`g_2(13)=0g_2(2)10`$ | $`0g_2(13)01=g_2(\mathrm{𝟎𝟎}3)`$ | - |
|  | $`g_2(20)=0g_2(1)10`$ | $`1g_2(20)10=g_2(\mathrm{𝟑𝟑}0)`$ | - |
|  | $`g_2(20)=0g_2(1)10`$ | $`1g_2(20)11=g_2(\mathrm{𝟑𝟑}2)`$ | - |
|  | $`g_2(32)=10g_2(3)1`$ | $`0g_2(32)01=g_2(0\mathrm{𝟑𝟑})`$ | - |
| a.iv.E | $`g_1(12)=10g_1(1)0`$ | $`0g_1(12)10=g_1(\mathrm{𝟐𝟏𝟐})`$ | - |
|  | $`g_1(12)=10g_1(1)0`$ | $`1g_1(12)10=g_1(\mathrm{𝟑𝟏𝟐})`$ | - |
|  | $`g_1(12)=1g_1(2)10`$ | $`00g_1(12)1=g_1(\mathrm{𝟎𝟐𝟏})`$ | - |
|  | $`g_1(12)=1g_1(2)10`$ | $`10g_1(12)1=g_1(\mathrm{𝟏𝟐𝟏})`$ | - |
|  | $`g_1(21)=0g_1(1)01`$ | $`01g_1(21)0=g_1(\mathrm{𝟐𝟏𝟐})`$ | - |
|  | $`g_1(21)=0g_1(1)01`$ | $`11g_1(21)0=g_1(\mathrm{𝟑𝟏𝟐})`$ | - |
|  | $`g_1(21)=01g_1(2)1`$ | $`0g_1(21)01=g_1(\mathrm{𝟎𝟐𝟏})`$ | - |
|  | $`g_1(21)=01g_1(2)1`$ | $`1g_1(21)01=g_1(\mathrm{𝟏𝟐𝟏})`$ | - |
|  | $`g_2(03)=01g_2(0)1`$ | $`1g_2(03)00=g_2(\mathrm{𝟑𝟎𝟏})`$ | - |
|  | $`g_2(03)=01g_2(0)1`$ | $`1g_2(03)01=g_2(\mathrm{𝟑𝟎𝟑})`$ | - |
|  | $`g_2(03)=0g_2(3)01`$ | $`01g_2(03)0=g_2(\mathrm{𝟎𝟑𝟎})`$ | - |
|  | $`g_2(03)=0g_2(3)01`$ | $`01g_2(03)1=g_2(\mathrm{𝟎𝟑𝟐})`$ | - |
|  | $`g_2(30)=1g_2(0)10`$ | $`10g_2(30)0=g_2(\mathrm{𝟑𝟎𝟏})`$ | - |
|  | $`g_2(30)=1g_2(0)10`$ | $`10g_2(30)1=g_2(\mathrm{𝟑𝟎𝟑})`$ | - |
|  | $`g_2(30)=10g_2(3)0`$ | $`0g_2(30)10=g_2(\mathrm{𝟎𝟑𝟎})`$ | - |
|  | $`g_2(30)=10g_2(3)0`$ | $`0g_2(30)11=g_2(\mathrm{𝟎𝟑𝟐})`$ | - |
| a.iv.F | $`g_2(03)=0g_2(3)01`$ | $`10g_2(03)0=g_2(130)`$ | $`g_2(\mathrm{𝟎𝟎}3)0=0g_2(130)`$ |
|  | $`g_2(03)=0g_2(3)01`$ | $`10g_2(03)1=g_2(132)`$ | $`g_2(\mathrm{𝟎𝟎}3)1=0g_2(132)`$ |
|  | $`g_2(30)=1g_2(0)10`$ | $`01g_2(30)0=g_2(201)`$ | $`g_2(\mathrm{𝟑𝟑}0)0=1g_2(201)`$ |
|  | $`g_2(30)=1g_2(0)10`$ | $`01g_2(30)1=g_2(203)`$ | $`g_2(\mathrm{𝟑𝟑}0)1=1g_2(203)`$ |
| a.iv.G | $`g_1(12)=10g_1(1)0`$ | $`0g_1(12)01=g_1(210)`$ | $`0g_1(1\mathrm{𝟐𝟐})=g_1(210)0`$ |
|  | $`g_1(12)=10g_1(1)0`$ | $`1g_1(12)01=g_1(310)`$ | $`1g_1(1\mathrm{𝟐𝟐})=g_1(310)0`$ |
|  | $`g_1(21)=01g_1(2)1`$ | $`0g_1(21)10=g_1(023)`$ | $`0g_1(2\mathrm{𝟏𝟏})=g_1(023)1`$ |
|  | $`g_1(21)=01g_1(2)1`$ | $`1g_1(21)10=g_1(123)`$ | $`1g_1(2\mathrm{𝟏𝟏})=g_1(123)1`$ |

Table 1 (continued): Forbidden Patterns in the Proof of Lemma 17
2. The only $`a,b,c`$ that satisfy $`g_1(a)=st`$, $`g_1(b)=uv`$, and $`g_1(c)=sv`$ such that $`ac`$ and $`bc`$ are $`(a,b,c)\{(0,3,2),(1,2,3),(2,1,0),(3,0,1)\}`$. But by Lemma 16, the infinite word $`h^\omega (0)`$ contains no subwords of the form $`3\alpha 2\alpha 0`$, $`2\alpha 3\alpha 1`$, $`1\alpha 0\alpha 2`$, or $`0\alpha 1\alpha 3`$. This contradicts the assumption that $`b\alpha c\alpha a`$ is a subword of $`h^\omega (0)`$ for some $`\alpha \mathrm{\Sigma }_4^{}`$. The same result holds true for $`g_2`$.

###### Lemma 18

Neither $`g_1(h^\omega (0))`$ nor $`g_2(h^\omega (0))`$ contain squares $`yy`$ with $`|y|4`$.

Proof.  As in the case of Lemma 2, this follows from Lemma 17.

We can now complete the proof of Theorem 13. Let $`𝐱:=g_2(h^\omega (0))=010100011101010011\mathrm{}`$ and $`𝐲:=g_1(h^\omega (0))=001101010110001010\mathrm{}`$. Then by Lemma 14 we have $`𝐱\text{SH}𝐲=f^\omega (0)`$. But $`f^\omega (0)=f^\omega (001)`$ and so $`f^\omega (0)`$ begins with $`f^n(0)f^n(0)`$ for all $`n0`$. Hence $`f^\omega (0)`$ begins with an arbitrarily large square.

On the other hand, by Lemma 18, we have that $`𝐱`$ and $`𝐲`$ avoid all squares $`ww`$ with $`|w|4`$.

## 5 Acknowledgments

We thank Jean-Paul Allouche for helpful discussions.


format: text

text:
# CMS Data Analysis: Current Status and Future Strategy

## I Introduction

Requirements on CMS software and computing resources cmsctp  will far exceed those of any existing high energy physics experiment, not only because of the complexity of the detector and of the physics task but also for the size and the distributed nature of the collaboration (today encompassing 2000 physicists from 150 institutions in more than 30 countries) and the long time scale (20 or more years). It was widely recognised from the outset of planning for the LHC Experiments in the mid-1990s, that the computing systems required to collect, analyse and store the physics data would need to be distributed and global in scope. In particular, studies of the computing industry and its expected development showed that utilising computing resources external to CERN, at the collaborating institutes (as had been done on a limited scale for the LEP experiments) would continue to be an essential strategy, and that a global computing system architecture would need to be developed.

Therefore, since 1995 the CMS computing group has been engaged in an extensive R&D program to evaluate and prototype a computing architecture that will allow to perform the task of collecting, reconstructing, distributing and storing the physics data correctly and efficiently in the LHC demanding environment, and, at the same time, to present the user, either local or remote, with a simple logical view of all objects needed to perform physics analysis or detector studies.

More recently, CMS undertook a major requirements and consensus building effort to modernise this vision of a distributed computing model to a Grid-based computing infrastructure. Accordingly, the current vision sees CMS computing as an activity that is performed on the “CMS Data Grid System” whose properties have been described in considerable detail cmsgridreqs . The CMS Data Grid System specifies a division of labour between the various Grid projects and the CMS core computing project.

## II CMS Analysis Environment

Figure 1 shows the current model of the CMS Analysis Environment.

CMS goal is to deploy a Coherent Analysis Environment that goes beyond the interactive analysis tool that provides classical data analysis and presentation functionalities such as N-tuples, histograms, fitting, plotting. We aim to allow an easy and coherent access to the great range of other activities typical of the development of physics analysis and detector studies in HEP. Support will be provided for both batch and interactive work with interface ranging from “pointy-clicky” to Emacs-like power tool to scripting. The environment will encompass configuration management tools, application frameworks, simulation, reconstruction and analysis packages.

Most of the activity will be seen as operations on data-stores: Replicating entire data-stores; Copying runs, events, event parts between stores. A “copy” operation will often encompass something more complicated such as filtering, reconstruction, analysis.

A particular enphasys will be placed on browsing data-stores down to object detail level including support for 2D and 3D visualisation.

A final aim of such a coherent environment will be the ability to move and share code across final analysis, reconstruction and triggers.

## III CMS Software System

In order to achieve such a Coherent Analysis Environment the software system has to provide a Consistent User interface on one side and a coherent set of basic tools and mechanisms on the other. CMS software system, presented in figure 2, is based on a modular and layered architecturecmsarch  centred around the COBRACOBRA  and IGUANAIGUANA  frameworks. It relies on a high-quality service and utility toolkit provided by the LCG projectLCG  in the form of either certified and maintained external software components or as packages developed by the project itself.

The framework defines the top level abstractions, their behaviour and collaboration patterns. It comprises two components: a set of classes that capture CMS specific concepts like detector components and event features and a control policy that orchestrates the instances of those classes taking care of the flow of control, module scheduling, input/output, etc. This control policy is tailored to the task in hand and to the computing environment.

The physics and utility modules are written by detector groups and physicists. The modules can be plugged into the application framework at run time, independently of the computing environment. One can easily choose between different versions of various modules. The physics modules do not communicate with each other directly but only through the data access protocols that are part of the framework itself.

Both the application framework and the service and utility toolkit shield the physics software modules from the underlying technologies which will be used for the computer services. This will ensure a smooth transition to new technologies with changes localised in the framework and in specific components of the service toolkit.

## IV Distributed Analysis

Physicists analysing data will access a great variety of sources and services ranging from simple histograms and n-tuples, to Relational Data-Bases. Analysis activity may include simple “tag” selections, more complex SQL-like queries up to running CMS simulation, calibration and/or reconstruction applications. A combination of generic grid tools and specialised CMS tools will be required to optimise the use of computing resources. Figure 3 shows the current view of CMS architecture for Distributed Analysis. Physicists will use a single access point that will allow them to gain access to the required resources and services depending both on the task in hand and the nature of the data. An Analysis Server, such as the Clarens Remote Dataserver CLARENS  described in next section, will act as mediator between the user, and his front-end application, and the back-end services. These three-tier architecture realises a clean separation between the user environment and the service environment. This will enable the user to maintain a consistent personalised environment while the various services may be configured and deployed according to policies specific to each provider site.

### IV.1 The Clarens Remote Analysis Server

The Clarens Remote Dataserver CLARENS  project aims to build a wide-area network client/server system for remote access to a variety of data and analysis services.

The first service envisaged (and partly implemented) is analysis of events from Spring 2002 production currently stored in centralised Objectivity databases, but in future may be stored in a combination of relational databases and/or files. Other services include remote access to Globus functionality for non-Globus clients, including file transfer, replica catalog access and job scheduling.

The concept of a “server” is currently the traditional interpretation of the word, but might in future also refer to the multi-tiered data-GRID for data access and analysis.

Communication between the client and server is conducted via the lightweight XML-RPC XMLRPC  remote procedure call mechanism. This was chosen both for its simplicity, good standardisation, and wide support by almost all programming languages. Work is also underway to enable communication using the widely supported SOAP SOAP  protocol.

The server is implemented using a modular combination of Python and C++ that executes directly in the Apache APACHE  web server’s address space. This increased performance roughly by a factor of five w.r.t. a cgi-bin implementation. Clients connecting to the server are authenticated using Grid certificates, while the server can likewise be authenticated by clients. Client session data is tracked using the high-performance embedded Berkeley database. Sessions can optionally be conducted over strongly encrypted SSL/TLS connections. Authentication information is always strongly encrypted, irrespective of whether the session is encrypted.

The modular nature of the server allows functionality to be added to a running server without taking it off-line by way of drop-in components written in Python of a combination of C++ and Python. An example module that allows browsing and down-loading of histograms and Tag objects in an Objectivity database federation has been implemented in this way.

The multi-process model of the underlying server (Apache) is uniquely suited to handling large volumes of clients as well as long-running client requests. These server processes are protected from other malicious or faulty requests made by other clients as each process runs in its own address space.

There are currently three clients that are evolving along with the server:

* Python command line
* C++ command line client as an extension of the ROOT analysis environment
* Python GUI client in the SciGraphica analysis environment

Support for the Java Analysis Studio client has been dropped in favour of the ROOT client due to the latter’s greater popularity in the CMS community. A web-based front-end that supports the new authentication mechanism will be deployed in the near future to replace the current non-authenticated version.

The command-line Python client may also be used directly in any Python-based analysis environment such as the IGUANA scripting service.

## V Data Challenges

In order to test its Software system and its computing model CMS is engaged in an aggressive program of “data challenges” of increasing complexity:

* Data Challenge ‘02
Focus on High–Level Trigger studies
* Data Challenge ‘04
Focus on “real-time” mission critical tasks
* Data Challenge ‘06
Focus on distributed physics analysis

Even if each data challenge is focus on a given aspect, all encompass the whole data analysis process: Simulation, reconstruction and statistical analysis running either as organised production, end-user batch job or interactive work.

### V.1 Spring 2002 Production

In Spring 2002 the CMS production team completed a production of Monte–Carlo data Prod02  for the DAQ TDR DAQTDR . Almost 6 million events were simulated with the CMS GEANT3-based detector simulation program CMSIMCMSIM  and then digitised and reconstructed under a variety of conditions with the CMS Object Oriented reconstruction and analysis program ORCAORCA  based on the COBRA framework. About 20 regional centres participated in this work running about 100 000 jobs for a total of 45 years CPU (wall-clock) distributed over about 1000 cpus. 20TB of data were produced. Of these more than 10TB travelled on the Wide area network. More than 100 physics were involved in the final analysis. PAW, and in a later stage ROOT, were the preferred analysis tools. Less specialised tools, such as Mathematica and Excel, were also used for some analyses. IGUANA was used for interactive graphical inspection of detector components and of single events. The result of this workDAQTDR  was the successful validation of CMS High–Level Trigger algorithms including rejection factors, computing performance and functionality of the reconstruction-framework.

### V.2 Data Challenge in 2004 (DC04)

The previous data challenge has concentrated on the simulation and digitisation phase and the preparation of datasets for asynchronous analysis. With this challenge CMS intends to perform a large-scale test of the computing and analysis models themselves. Thus we anticipate a pre-challenge period comprising the preparation of the data samples, while the challenge itself consists of the reconstruction and selection of the data at the T0 (Tier-0 computing centre at CERN), with distribution to the distributed T1/T2 sites and synchronous analysis.

DC04 DC04  will run in the LCG LCG  production grid. We anticipate that the T0 part of the challenge is entirely CERN based, but the subsequent data replication and analysis run in a common prototype grid environment. All T0-T2 resources of the Data Challenge should be operating in a common GRID prototypeclaudio .

In this data challenge, to be completed in April 2004, CMS will reconstruct 50 million events in real time coping with a data rate equivalent to an event data acquisition running at 25 Hz for a luminosity $`2\times 10^{33}cms^2s^1`$ for one month. Besides this pure computation goal CMS will use this opportunity to test the software system, the event model, define and validate datasets for analysis, identify reconstruction and analysis objects each physics group would like to have for the full analysis, develop selection algorithms necessary to obtain the required sample, and prepare for “mission critical” analysis, calibration and alignment.

## VI Summary

CMS is actively pursuing a development and test activity to be able to deploy a fully distributed computing architecture in time for the LHC start-up. A distributed production and analysis of 6 million Monte–Carlo events have been successfully completed in 2002 involving 20 regional centres. Next major data challenge is scheduled for the year 2004 and comprises a complexity scale equal to about 5% of that foreseen for LHC high luminosity running. It will run in the LCG production grid and will be used to exercise a fully distributed physics analysis using tools such as the Clarens Remote Dataserver running in conjunction with CMS specific applications based on the COBRA and IGUANA frameworks.


text:
# BdbServer++: A User Driven Data Location and Retrieval Tool

## I Introduction

BaBar, and HEP users in general, have long faced the challenge of locating and retrieving data remotely from large storage systems. With the increasingly distributed nature of the Computing Models used by HEP experiments there is an additional dispersed geographical element to this problem. This paper outlines our understanding of the issues, with an emphasis on the BaBar experiment, and our attempts to address it. We outline the framework we have used and the projects progress.

The BdbServer++ project attempts to build on both prior work, the original BdbServer, and the current work of other groups, notably the European DataGridEDG  (EDG) and BaBarGridBBG . It is our intention to tackle the generic issues facing us in data distribution, from primary to secondary and tertiary locations, and provide a useful tool to assist BaBar users. BdbServer++ is a complimentary project to the work currently being done with the SDSC Storage Resource BrokerWILCO  which, it is foreseen, will be used by BaBar for bulk data transfer between primary computing sites.

In this paper we discuss the background to this problem, with specific reference to the evolving state of the BaBar Computing ModelCMWG , the evolution and adoption of Grid technologies, and outline the areas which we believe have the greatest impact.

We describe our work in this area and the results we have achieved so far. We discuss what has been learnt from this with the intention of assisting other experiments in deciding how they wish to tackle the problem of data distribution for analysis and conclude with suggestions for how our work will progress in the future. We comment on aspects of interest to the community.

In this paper Section II provides a background to the project, covering the framework it has developed within, the context and objectives. Section III describes our current progress and sub-projects. Section IV presents the implementation issues of the project which are commented upon in context with other groups work in Section V and our concluding remarks in Section VI.

## II Background

### II.1 The BaBar Computing Model

The BaBar Computing Model calls for there to be, at minimum, two distinct classes of Computing Site. These are currently entitled Tier A and Tier C. Tier A sites are major resource centres, having MoUs with the Collaboration. Tier C sites refer to institute level facilities, ranging from a single workstation to a major computing cluster and disk facility.

There are five locations currently classed as Tier A sites located in France111IN2P3, Lyon, Germany222GridKa, Karlsruhe, Italy333INFN, Padova, the UK444RAL, Didcot and the USA555SLAC, Menlo Park. These sites store a quantity of Monte Carlo and Production data, provide computing resources and accounts for users. Sites specialise in specific tasks - such as data storage, data re-processing and Monte Carlo production.

Due to the quantity of data produced by both the detector and simulation, no site stores a complete set of all data online. SLAC maintains a complete archive but the majority of this is on Tape. The other sites may store all data in a particular format or a selection of data. BaBar maintains data in a variety of formats, of different granularities. These range from the MiniMINI  to the MicroMICRO  and KangaKANGA .

To summarise these formats, the Micro contained events with sufficient detail for most physics analyses and had a fast enough access time to run a realistic analysis. However, it provided only the pion hypothesis track fit at the origin of the event which led to the development of the Mini.

The Mini contains enough detail to provide a track reconstruction object which has information about fits for all physically distinct hypotheses valid throughout the entire detector.

Kanga, the Kind ANd Gentle Analysis, is the de-facto format for physics analysis at Tier-C sites. It is used for micro analysis using standard framework, but without Objectivity.

Tier C sites are the User Institutes, which exist in far greater numbers than the much larger Tier A sites. Tier C sites typically request data be extracted from the database at a Tier A site and copied to their location for analysis. Data at these locations is typically not available to users at other institutes.

### II.2 A Historical Context for BdbServer

The BdbServer project was started in the late 1990’s to automate the process of extracting collections from the Objectivity/DB databases at SLAC and IN2P3. These sites have also behaved as the primary and backup database for the experiment. The presence of a backup copy of the data at a different location serves as a safeguard against catastrophic problems at any one site.

The original BdbServer was developed using server resident Perl scripts and a generic system account. Users submitted requests to a SLAC email address in a set format, specifying various parameters for the data they required.

These requests were collated every 15 minutes by the BdbServer software and submitted to the batch system. The required data was extracted and stored in temporary disk space at SLAC. Users were informed by email when their request had been fulfilled.

As BdbServer was run as a single instance, and ran in a sequential manner over the requests it received, there were obvious issues of scalability and performance. The system lacked the ability to remember previous requests and as a result was unable to utilise caching techniques for optimisation.

The BdbServer++ project was started in 2002 to investigate migrating BdbServer to a Grid framework and to investigate options for alternative interfaces. This was inspired by both the roll out of Grid infrastructure at Tier A sites and changes to the BaBar Computing Model.

### II.3 BdbServer++ Objectives

The primary aim of BdbServer++ is to migrate the currently available functionality of BdbServer to the existing Grid infrastructure. This should allow users to submit a request from a remote location to a central resource. This will extract a copy of the required data and store it in a location accessible to the user.

The secondary aims of BdbServer++ are to improve the availability of Grid clients at user institutes, review available alternative interfaces to this resource and investigate Grid technologies which could be of use to the project.

As a byproduct we hope to increase the reliability, scalability and optimisation of the software.

## III Current Progress

### III.1 User Submission

While email is now, and has been for many years, available to all BaBar users, the same is not true of the Grid. Wide scale adoption in Europe, as part of the European DataGrid and various government initiatives, has not been matched in the USA. As a result a need was demonstrated for a simple to install, minimal Grid client. This resulted in the BBGUtils project outlined in III.1.1.

Various submission methods were considered including a web interface and a command line interface. It was rapidly ascertained that a web interface for this project was inappropriate. The user community was uncomfortable with a move away from the command line and discussions with the SLAC Computing Security Group rapidly outlined a number of security implications inherent in the web interface and the need for secure data to transfer between multiple hosts.

As a result, the command line interface option was chosen. This is discussed in detail in IV.2.

#### III.1.1 BBGUtils

Early feedback from our user community showed that while the major computing centres such as SLAC, had adopted the Grid and have a large number of experienced staff, many of the user institutes are not in the same position.

From discussions with users we realised that there were two main issues which were slowing the uptake of BdbServer++. Site security issues with the Globus Toolkit™Globus , especially the server components, and limited user experience in installing Grid software software, posed a barrier to the adoption of BdbServer++.

Site security is frequently handled by different groups and individuals to those who require physics data for analysis. Their objective, to secure their site against intrusion and limit the risk to their network, is often at odds with the users wish to perform productive work easily.

Many of the concerns expressed by the security groups centred around superuser based installations, potential attacks on their networks and the ability of outside users to log into local accounts. We were able to address and avoid these problems by re-wrapping the three client bundles of the Globus Toolkit (Data, Resource and Information) as a single package.

This new package, which we named BBGUtils, can be installed under a standard user account and does not have the ability to allow remote users to log into the client machine. We included copies of the various Certificate Authority Certificates and automatically install them so the user can start submitting jobs as soon as the client is installed.

Site specific configuration proved unnecessary as host certificates for the client machine are unnecessary and our target users generate their personal certificates using other methods. This removes the need for this configuration and gives our users less detail to concern themselves with.

A bash script was originally used for installation under Linux but has since evolved into a perl version which operates successfully under Linux and Solaris.

### III.2 Request Management

A dedicated test machine was configured at SLAC to deal with BdbServer++ requests. For security reasons this was placed outside the SLAC firewall and is only able to access system resources specifically needed for BdbServer++.

The grid-mapfile was attached to the BaBar VO which contains all users with a valid Grid Certificate.

The server was configured to allow it to submit jobs, under the users’ ID, to the batch system for database operations.

GridFTP was enabled to allow data to be transferred to remote locations on completion. Two other file transfer applications bbcpbbcp  and bbftpbbftp  used by BaBar that also allow third party file transfers are available, but have not been tested yet.

## IV Implementation Issues

### IV.1 Implementation

The majority of our implementation has been in Perl as this provides support for all platforms currently supported by BaBar. Perl is also widely used by members of the collaboration and has widespread use in industry and academia.

### IV.2 User Interface

Development on the user interface has two tracks. Submission to SLAC is achieved by using either the globusrun or globus-job-run commands which come as standard with Globus. We are in the process of developing a utility to assist users in formulating their requests. This is intended to allow pre-prepared requests which can be used multiple times by the user.

### IV.3 Server Performance

We conducted simple tests on our development system by using a basic shell script to submit multiple simultaneous requests. The results of these tests showed that our current server, a duel Intel®Pentium™III-866 is able to handle in the region of 20 simultaneous requests before we encounter dropped and lost requests.

This is obviously not enough for a production environment but has shown us the areas we need to address to move to a production environment.

### IV.4 User Accounts, Auditing and Caching

We are currently looking at moving toward using a pool of user accounts for date extraction. This will have the advantage of allowing us to catalogue what has been recently requested, and hopefully utilise cached collections to satisfy multiple requests. We will also be able to sandbox accounts, limiting the potential damage intruders could cause.

Our progress in this area is hampered by the requirements for audit trails and the structure of the BaBar Computing Model. As each user is automatically assigned an account at SLAC it was a simple task for us to map the users grid certificate onto their local account.

The use of individual user accounts is, in theory, advantageous as it allows the manipulation of data in the users home directory. In reality this is a problem as users have only limited disk space for their accounts and with some requests this can be rapidly filled. With pool accounts we can allow a much greater use of disk space for a restricted number of sessions.

## V Related Projects

BdbServer++ is both middleware and a work in progress. It relies on the development of other projects to extend its capabilities and these are evolving on a daily basis. As a result, a clear picture of how the production version of BdbServer++ will appear is difficult to define.

We are actively reviewing, and learning from, the work being done in the areas of distributed replica catalogues, replica location services and automated processes for discovery and registering of data. Much work is being done on this by the EDG Work Package 2WP2  group.

Work being done by EDG Work Package 1WP1  in the area of Resource Brokers is of interest in the longer term. When coupled with a replica catalogue this would allow us to improve performance and reliability measurably.

## VI Conclusions

We have presented the current status of BdbServer++, an overview of what has lead us to this stage and an outline of the avenues we are currently investigating to improve it. Much work remains to be done but we have outlined a coherent strategy and discussed the issues we feel are important to the project and research in this area in general.

###### Acknowledgements.

This paper is based on work supported by the UK Particle Physics and Astronomy Research Council (www.pparc.ac.uk) Studentship PPA/S/E/2001/0338, the US Department of Energy (www.energy.gov), the Particle Physics Data Grid (www.ppdg.org) and LAPP-Annecy CNRS/IN2P3 (www.in2p3.fr). We wish to thank the members of the BaBar Computing Group and especially the members of the Data Distribution Group and the BaBarGrid Group and others who have assisted in providing information and suggestions for this project.


text:
# Novel Data Acquisition System for Silicon Tracking Detectors

## I INTRODUCTION

In order to cope with the challenging LHC-like running environment of high event rates, high number of channels, limited processing time and limited storing capability, the Data Acquisition System (DAQ) of the Helsinki Silicon Beam Telescope (SiBT) SiBT\_hardware99 ; SiBT2000a  was rebuilt. The SiBT device is operated by Helsinki Institute of Physics at the CERN H2 beam line. It is used to measure tracks of incoming particles with high resolution to offer reference tracks to the CERN CMS subdetector systems for testing their detectors at the H2 beam. The SiBT is based on position sensitive silicon detectors attached to appropriate readout electronics and DAQ. daq\_tdr ; daq\_tdr2

## II EXPERIMENTAL SETUP

### II.1 Silicon strip detectors

Fig. 1 shows the schematical layout of the SiBT setup. The SiBT apparatus consists of eight single-sided silicon microstrip detector planes. The detectors with 1024 p+ strips are processed on n-type Float Zone silicon wafers that are 300 $`\mu `$m thick. The width of the strips is 14 $`\mu `$m and pitch 55 $`\mu `$m giving a total detector area of 5.6 $`\times `$ 5.6 cm2 harkonen2002a . Each silicon detector is glued and bonded on a hybrid containing 8 VA1 readout chips.

The eight detectors are installed as four pairs orthogonal to the beam axis. Every pair consists of one detector with strips positioned horizontally and another with strips positioned vertically. The aluminum housings, which enclose the detector hybrids, are attached on aluminum forks that are mounted on an optical precision bench consisting of a 492 mm long brass rail sitting on top of a granite block.

During the summer 2002 tests, a muon beam of the energy of 225 GeV was used to study the performance of the SiBT and a new Czochralski type silicon detector.

### II.2 Front-end electronics

Each silicon detector has a separate front-end electronics unit consisting of 8 daisy-chained VA1 readout chips and a repeater card. Each VA1 chip has 128 identical channels with a charge sensitive amplifier, a shaper and a track-and-hold circuitry in each. The output of each detector is multiplexed and activated by the output shift register using a clock signal of 6 MHz.

The readout chips of a hybrid are controlled from the counting room. The controls cable has a 50-pin flat cable connector that is connected to the protective housing to a repeater card mounted on an additional rail next to the detector housings. Each repeater card contains four voltage regulators to supply the readout chips and a high-speed differential I/O amplifier to buffer and amplify the balanced analog output signal. Line receivers and analog and digital circuits control the readout electronics and set the necessary working parameters for both the detector and the VA1 chips. In addition, the repeater card has an efficient protection circuit against breakdown damage in latch-up conditions. All supply voltages are cut off sharply, if one of the input power lines fail to work.

### II.3 Triggering

Mounted before the first and after the last detector are two standard plastic scintillators attached to photomultiplier tubes that are shielded against a magnetic field of up to 1 T. The photomultiplier signals are shaped and put through a coincidence unit in the counting room and the resulting trigger signal is sent back to the repeater cards to activate the readout modules. The trigger signal starts the readout sequence simultaneously on each of the eight repeater cards.

Analog delay is added to the trigger signal to achieve optimum charge collection time in the detectors. The triggering system is protected against events that are very close to each other by vetoing any additional trigger signals that should occur while the repeater cards are busy reading the last event. The dead time for reading one event using a 6 MHz clock on the repeater cards and taking into account cable delays is 172 $`\mu `$s.

## III DATA ACQUISITION SYSTEM

### III.1 Digitization

The readout of the detectors is controlled from the counting room using standard commercially available VME-based technology. A commercial 8-channel VME ADC card SIS3300 with 12-bit resolution is used to digitize the analog signals from the repeater cards. The eight repeater cards are connected through equally long coaxial cables to the ADC. A ninth cable is used to send the clock pulse of one of the repeater cards to the ADC to trigger the sampling.

The ADC samples simultaneously all the eight channels. It is operated in asynchronous clock mode, in which the 6 MHz clock pulse of the repeater cards activates the taking of one sample simultaneously from all channels at the 100 MHz internal clock rate. Each channel has an independent ADC circuit and the data of each channel pair is combined as one 32-bit word and pushed via pipeline into a 128 ksample SDRAM memory bank. The ADC can thus store 128 events containing data of the 1024 channels of a single detector.

There are two equal size memory banks on the ADC for each channel pair to allow operation in circular buffer mode. In circular buffer mode the active bank is automatically switched to the empty bank once the active bank has become full and data taking can resume without any delay and thus no additional dead time is caused.

The ADC provides automatically a time stamp for each event with respect to the first event in the bank with a time resolution of its internal clock. The blocks of 128 events are thus internally synchronized with high precision and therefore, to achieve overall synchronization of the events, only the first event of the block needs to be synchronized with the accelerator time frame.

### III.2 Timing

The DAQ is equipped with time stamping capabilities to ensure the synchronizability of the events with other experiments using the same testbeam facility. A fast commercial VME scaler unit is used to provide time stamps for the first event in the ADC bank. The 100 MHz internal clock of the ADC is used to provide the count, which is synchronized to the accelerator hardware by resetting the count at one second before the spill starts. In the future it is planned to use a custom-built multi-DAQ card specially designed for high accuracy and reliable event timing.

### III.3 VME-PCI interface

The VME crate is controlled with a commercial VME-PCI interface card SIS3100. It uses a Gigabit Optical Link (GOL) to transmit data via an optical fiber between the DAQ PC and the VME crate. The interface is also equipped with 512 MB of SDRAM and a programmable SHARC circuit, which could be used to process the signals. The optical link has, however, proven to be sufficiently fast at the current DAQ speeds for pushing the data directly from the VME-bus into the memory of the DAQ-PC without storing it to the memory of the interface card.

The interface card also includes three digital input and output channels, which are used to give information for the DAQ PC about the phase of the accelerator.

## IV DAQ SOFTWARE

Because the accelerator cycle consists of a spill period, during which particles are extracted to the test beam area, and an idle period, during which new particles are accelerated and other beams are served, it is logical to divide the DAQ operation into two operation cycles. When particles are passing through the detector and thus producing data during spill cycle, the DAQ is concentrating only on reading the new data in order to maximize the number of events that are read. This raw event data is further processed and stored on a hard drive during the idle period while waiting for new data.

The key challenge that the structure of the DAQ software faces is the fact that large amounts of data have to be read and processed reliably in real time. Usually, the amount of data that needs to be transferred to a PC is reduced by using pipelined programmable circuits inside the VME crate. Because no fast enough commercial modules were available, a custom built VME card or a large number of costly ADC modules would have been needed. The GOL of the VME-PCI interface was found to have a high enough data transfer rate to allow the transfer of all the raw data to the memory of the PC with minimal performance losses. This way the data processing is more reliable as the whole process can be monitored on the PC and the physics cuts on the data may be altered in real time.

### IV.1 Software architecture

The DAQ software is realized using C++ object orientated techniques on a PC equipped with a 1200 MHz AMD Athlon processor and running CERN RedHat Linux 7.1. The UML diagram of the software is shown in Fig. 2. The raw data is stored as a vector of DAQEventTrain objects each containing four 128K long arrays of 32-bit unsigned integers and 128 32-bit time stamps thus providing storage for a total of 128 events. Each DAQEventTrain object further contains a vector of 128 DAQRawEvent objects. The DAQRawEvent objects contain pointers to the data that is in the DAQEventTrain object and the data can thus be accessed from both the DAQEventTrain and DAQRawEvent objects.

The pedestal and noise calibration data for the individual detector channels are stored into the DAQStripData object and accessed directly from the events during processing. The detector channels are labeled dead or noisy if the noise level is outside certain user-defined thresholds and the user may also deliberately mark known channels to be ignored.

The DAQStatistics object contains information on how the selection process is working, what percentage of channels is passing through each selection level and what are the efficiencies for having at least one hit on a detector plane per event. More detailed information about the quality of data and the behavior of the detector planes is stored into the DAQHistogram object, which is an interface to the Histo-Scope histogramming package. The histograms may be viewed online, but it does significantly slow down the DAQ operation.

Data concerning the operation and status of the DAQ are stored into DAQRunControl and DAQStatusWord objects. The memory space of the VME crate is accessed via a C-based driver that is controlled through the DAQVMEInterface object.

In order to retain real time operation, the memory of the whole data structure is dynamically allocated from the memory of the PC as the software is started. Thus no time consuming memory allocation needs to be conducted during the operation of the software. The drawback is that large amounts of memory are required, as a spill cycle length of 4.8 seconds requires about 360 MB of memory for the raw data.

### IV.2 Reading data from hardware

Once the accelerator hardware provides a pre-spill signal one second before the spill starts, the software prepares to start reading the data and arms the hardware. Once the spill is on, the software keeps checking, whether an ADC bank has been filled with data. If an ADC bank is full, the software reads the sample data, which has been stored into four memory banks, each containing the data of two channels.

Fig. 3 shows the flow of the reading sequence. The data is read to the actual DAQEventTrain object in four blocks of 128 ksamples of 32-bit data via the VME-PCI interface using 2eVME cycles. Previous data is overwritten. Additionally, the ADC-internal time stamp register of the events is read. The speed of the reading process is optimized by minimizing the number of blocks to be read, since in this way the number of time-costly interrupts on the VME bus can be minimized.

Once the reading of the blocks is complete, the bank full flag of the ADC is cleared and the software waits for the first event to arrive in order to catch its time stamp. The reading sequence repeats this pattern until the spill is over. To maximize the number of events that can be read, the software does not answer any user commands during the reading sequence.

### IV.3 Data processing

The data structure of the software allows the data to be accessed either on a single event basis or as blocks of 128 events. This is crucial for the performance of the software, because this structure allows the software optimization of both reading and processing the data. The reading of the data is at its fastest, if the data can be read in as large blocks as possible from the VME-bus thus minimizing the number of time consuming VME interrupts. On the other hand, if the events can be accessed on a single event basis during processing, several if-clauses are rendered obsolete and valuable processing time is saved.

In order to process the data efficiently without compromising the physical performance, three different selection levels are imposed on the data. On the average, 99.6 % of the raw data is just electronical noise, which has to be filtered out of the data of maximally $`1.910^8`$ samples (360 MB) during 10.9 seconds. In order to complete this task, three selection levels are imposed on the data.

For each strip $`i`$ of each detector a long term average pedestal $`P`$ is modeled using an IIR filter described by

$$P_i^n=\frac{m1}{m}P_i^{n1}+\frac{1}{m}R_i^n,$$
(1)
where $`m=64`$, $`R`$ the raw data value and $`n`$ is the current event. Additionally, the noise $`N`$ of each strip approximating the standard deviation is calculated with

$$N_i^n=\frac{m1}{m}N_i^{n1}+\frac{1}{m}|R_i^nP_i^n|,$$
(2)
where $`m=32`$.

In the first selection level, the raw data value is compared to its corresponding old pedestal value

$$RP>0.$$
(3)
If this criterion isn’t matched, the strip is discarded. With this simple and fast rejection 50 % of the noise is rejected. Only if the criterion is passed, the new pedestal and noise values are calculated for the strip. This method can be safely used, because the noise distribution of the pulse height spectrum is symmetrical around zero.

The second selection level enhances the first selection level by demanding, that a certain constant level of pedestal $`k_P`$ individually specifiable for each detector plane is exceeded

$$RP>k_P.$$
(4)
This criterion can be used to reject a further 80-90 % of the remaining noise and thus additional processing time is saved before a more elaborate and exact cut is made on the data.

Once the second selection level has been passed, the signal $`S`$ is calculated by subtracting the noise and pedestal from the raw data:

$$S=RPN$$
(5)
The third selection level is defined as

$$S>(N+k_{N_1})k_{N_2},$$
(6)
where $`k_{N_1}`$ is a small constant set to avoid dead strips and $`k_{N_2}`$ is usually set to 4.5 in order to make approximately a 4.5 $`\sigma `$ cut on the signal.

If the third selection level is passed, the actual strip and its neighboring left and right strips are selected to make a cluster and they are saved with all their data values to disk. The events are attached with header information describing the run, spill and event numbers as well as the time stamp to allow offline synchronization with data of other experiments. The size of saved data during one spill cycle amounts on the average to 6.5 MB for 22800 events including the event header information. The flow of the processing sequence is shown in Fig. 3.

### IV.4 User interface

The DAQ software is operated via a graphical user interface (GUI) that has been created with C++ using the Qt package qt . The GUI has direct access via pointers to all the objects of the DAQ software and thus it doesn’t need any additional objects to propagate the data. The GUI is updated and its requests are executed only when the program is not busy. Therefore, during the reading and processing periods, the GUI is neither updated nor responding to user actions in order to provide the maximum amount of CPU resources to the more important tasks. User actions are executed in the idle time after the processing has been finished and while the DAQ is waiting for the next spill.

The user may conveniently define data collection and processing parameters through the GUI as well as monitor the performance of the separate detectors and individual detector channels. A light histogram package Histo-Scope is integrated into the GUI to allow monitoring of the detector hardware and data quality. The histogrammer is however intended for slow data taking, as it will considerably slow down the processing.

## V RESULTS OF CZOCHRALSKI SETUP

The modeling of the detector channel properties with a fast algorithm is essential, because the channels have to be continuously calibrated. Fig. 4 shows that the pedestal modeling is functioning well for the detector channels. It is noticeable that there are discrete transitions after every 128 nels, because of the different noise levels in the VA1 amplifier chips on the detectors.

The noise filtering was found to work excellently using the three-step selection levels. Fig. 5 shows the pulse height distribution recorded for the Cz-detector. It displays in arbitrary units how the signal (dark gray tones) is cleanly extracted using the cut of the selection levels and the offline track fitting parameters from the total data (light gray). Most of the noise is already cut away before the figure and thus the noise doesn’t peak around zero ADC counts and the difference between 6 and 7 hits is accounted for one faulty detector while one detector was completely taken away from the setup. The plot shows that it is possible to use a fast algorithm based on selection levels even at high event rates without compromising with the physical content of the data.

To test the highest sustainable event rate with the current combination of hardware and software, a sequential trigger was fed to the system. The average event rate that the DAQ was able to cope with was measured to be $`4.74\pm 0.01`$ kHz.

The novel Czochralski type silicon detector was tested using the new DAQ by replacing one of the older detectors with the Cz-module. The efficiency of the detector was measured to be 95 %, the resolution about 10 $`\mu `$m, and the signal to noise ratio about 10.

## VI CONCLUSIONS

The results show that it is possible to construct an efficient and accurate Data Acquisition System for a challenging LHC-like environment of high event rates, high number of channels, limited processing time and limited storage capability. It has been shown that it is possible to build and successfully operate a DAQ system fulfilling these criteria using the C++ programming language and object orientated techniques on a Linux platform by using sophisticated yet fast selection techniques and optimization based on software architecture.

###### Acknowledgements.

The authors wish to thank Dragoslav Lazic and the CMS HCAL group for their valuable technical support and excellent collaboration at the H2 beamline at CERN. The authors also wish to thank Dr. M. Kirsch and Struck Innovative Systeme GmbH for excellent customer support and assistance in using their VME modules.


text:
# On the p-mode asymmetry between velocity and intensity from the GONG+ data

## Acknowledgements

This work utilises data obtained by the Global Oscillation Network Group (GONG) project, managed by the National Solar Observatory, which is operated by AURA, Inc., under a cooperative agreement with the National Science Foundation. The data were acquired by instruments operated by the Big Bear Solar Observatory and National Solar Observatory at Tucson.