text:
# Packing patterns into words

## 1 Preliminaries

Let $`[k]=\{1,2,\mathrm{},k\}`$ be our canonical totally ordered alphabet on $`k`$ letters, and consider the set $`[k]^n`$ of $`n`$-letter words over $`[k]`$. We say that a pattern $`\pi [l]^m`$ *occurs* in $`\sigma [k]^n`$, or $`\pi `$ *hits* $`\sigma `$, or that $`\sigma `$ *contains* the pattern $`\pi `$, if there is a subsequence of $`\sigma `$ order-isomorphic to $`\pi `$.

Given a word $`\sigma [k]^n`$ and a set of patterns $`\mathrm{\Pi }[l]^m`$, let $`\nu (\mathrm{\Pi },\sigma )`$ be the total number of occurrences of patterns in $`\mathrm{\Pi }`$ ($`\mathrm{\Pi }`$-patterns, for short) in $`\sigma `$. Obviously, the largest possible number of $`\mathrm{\Pi }`$-occurrences in $`\sigma `$ is $`\left(\genfrac{}{}{0pt}{}{n}{m}\right)`$, when each subsequence of length $`m`$ of $`\sigma `$ is an occurrence of a $`\mathrm{\Pi }`$-pattern. Define

$$\begin{array}{cc}\hfill \mu (\mathrm{\Pi },k,n)& =\mathrm{max}\{\nu (\mathrm{\Pi },\sigma )|\sigma [k]^n\},\hfill \\ \hfill d(\mathrm{\Pi },\sigma )& =\frac{\nu (\mathrm{\Pi },\sigma )}{\left(\genfrac{}{}{0pt}{}{n}{m}\right)}\mathrm{and}\hfill \\ \hfill \delta (\mathrm{\Pi },k,n)& =\frac{\mu (\mathrm{\Pi },k,n)}{\left(\genfrac{}{}{0pt}{}{n}{m}\right)}=\mathrm{max}\{d(\mathrm{\Pi },\sigma )|\sigma [k]^n\},\hfill \end{array}$$

respectively, the maximum number of $`\mathrm{\Pi }`$-patterns in a word in $`[k]^n`$, the probability that a subsequence of $`\sigma `$ of length $`m`$ is an occurrence of a $`\mathrm{\Pi }`$-pattern, and the maximum such probability over words in $`[k]^n`$. We want to consider the asymptotic behavior of $`\delta (\mathrm{\Pi },k,n)`$ as $`n\mathrm{}`$ and $`k\mathrm{}`$.

###### Proposition 1.1

If $`n>m`$, then $`\delta (\mathrm{\Pi },k,n)\delta (\mathrm{\Pi },k,n1)`$ and $`\delta (\mathrm{\Pi },k,n)\delta (\mathrm{\Pi },k1,n)`$.

###### Proof.

The proof of Proposition 1.1 in  also applies to the first inequality in our proposition, since possible repetition of letters is irrelevant here. To see that the second inequality is true, note that increasing $`k`$, i.e. allowing more letters in our alphabet, can only increase $`\mu (\mathrm{\Pi },k,n)`$, and hence $`\delta (\mathrm{\Pi },k,n)`$. $`\mathrm{}`$

The greatest possible number of distinct letters in a word $`\sigma `$ of length $`n`$ is $`n`$, which implies that $`\mu (\mathrm{\Pi },k,n)=\mu (\mathrm{\Pi },n,n)`$ for $`kn`$, and hence, $`\delta (\mathrm{\Pi },k,n)=\delta (\mathrm{\Pi },n,n)`$ for $`kn`$. Therefore,

$$\delta (\mathrm{\Pi },n,n)=\underset{k\mathrm{}}{lim}\delta (\mathrm{\Pi },k,n).$$

We also have $`\delta (\mathrm{\Pi },n,n)=\delta (\mathrm{\Pi },n+1,n)\delta (\mathrm{\Pi },n+1,n+1)`$, so $`\delta (\mathrm{\Pi },n,n)`$ is non-increasing and nonnegative, and there exists

$$\delta (\mathrm{\Pi })=\underset{n\mathrm{}}{lim}\delta (\mathrm{\Pi },n,n)=\underset{n\mathrm{}}{lim}\underset{k\mathrm{}}{lim}\delta (\mathrm{\Pi },k,n).$$

We call $`\delta (\mathrm{\Pi })`$ the *packing density* of $`\mathrm{\Pi }`$.

Obviously, there are two double limits. Since $`0\delta (\mathrm{\Pi },k,n)1`$, it immediately follows that there exists

$$\delta (\mathrm{\Pi },k)=\underset{n\mathrm{}}{lim}\delta (\mathrm{\Pi },k,n)[0,1]$$

and that $`\{\delta (\mathrm{\Pi },k)|k\}`$ is nondecreasing as $`k\mathrm{}`$. Hence, there exists

$$\delta ^{}(\mathrm{\Pi })=\underset{k\mathrm{}}{lim}\delta (\mathrm{\Pi },k)=\underset{k\mathrm{}}{lim}\underset{n\mathrm{}}{lim}\delta (\mathrm{\Pi },k,n).$$

It is easy to see that $`\delta ^{}(\mathrm{\Pi })\delta (\mathrm{\Pi })`$. Naturally, one wishes to determine when $`\delta ^{}(\mathrm{\Pi })=\delta (\mathrm{\Pi })`$. In this paper, we will provide a sufficient condition for this equality.

The set $`[k]^n`$ is finite, so for each $`k`$ and $`n`$, there is a string $`\sigma (\mathrm{\Pi },k,n)[k]^n`$ such that $`d(\mathrm{\Pi },\sigma (\mathrm{\Pi },k,n))=\delta (\mathrm{\Pi },k,n)`$. To find $`\delta (\mathrm{\Pi })`$, we will need to find $`\delta (\mathrm{\Pi },k,n)`$, hence maximal $`\mathrm{\Pi }`$-containing permutations $`\sigma (\mathrm{\Pi },k,n)`$ are of interest to us, especially, their asymptotic shape as $`n\mathrm{}`$ and $`k\mathrm{}`$.

###### Example 1.2

Let $`\mathrm{\Pi }=\{c_m\}`$, where $`c_m`$ is a constant string of $`m`$ 1’s. Then, clearly, $`\sigma (\mathrm{\Pi },k,n)=c_n`$ and $`d(c_m,c_n)=1`$ for $`nm`$, so $`\delta (c_m,k,n)=1`$ for $`nm`$, and hence $`\delta ^{}(c_m)=\delta (c_m)=1`$ for any $`m1`$.

###### Example 1.3

Let $`\mathrm{\Pi }=\{id_m\}`$, where $`id_m`$ is the identity permutation of $`S_m`$. Then $`\sigma (id_m,n,n)=id_n`$, so $`d(id_m,id_n)=1`$, $`\delta (id_m,n,n)=1`$ and $`\delta (id_m)=1`$.

Determining $`\delta ^{}(id_m)`$ is a bit harder. It is easy to see that $`\sigma (id_m,k,n)`$ must be a nondecreasing string of digits in $`[k]`$. Let $`n_i`$ be the number of digits $`i`$ in $`\sigma (id_m,k,n)`$, then $`\mu (id_m,k,n)=\nu (id_m,\sigma (id_m,k,n))=n_1n_2\mathrm{}n_k`$ and $`n_1+n_2+\mathrm{}+n_k=n`$. To maximize the above product we need $`n_1=n_2=\mathrm{}=n_k=\frac{n}{k}`$. (More exactly,  shows that we should choose for $`n_i`$’s to be such integers that $`|n_i\frac{n}{k}|<1`$ and $`|n_1+\mathrm{}+n_r\frac{rn}{k}|<1`$ for each $`r=1,2,\mathrm{},k`$.) It follows that

$$\delta (id_m,k,n)\frac{\left(\genfrac{}{}{0pt}{}{k}{m}\right)\left(\frac{n}{k}\right)^m}{\left(\genfrac{}{}{0pt}{}{n}{m}\right)}$$

(where $`a_nb_n`$ means $`lim_n\mathrm{}a_n/b_n=1`$), so $`\delta (id_m,k)=\left(\genfrac{}{}{0pt}{}{k}{m}\right)\frac{m!}{k^m}`$, and thus $`\delta ^{}(id_m)=1`$ as expected.

Packing density was initially defined for patterns in permutations. Therefore, we must show that the packing density on permutations agrees with the packing density on words.

###### Theorem 1.4

Let $`\mathrm{\Pi }S_m`$ be a set of permutation patterns, then

$$\delta (\mathrm{\Pi })=\underset{n\mathrm{}}{lim}\frac{\mathrm{max}\{\nu (\mathrm{\Pi },\sigma )|\sigma S_n\}}{\left(\genfrac{}{}{0pt}{}{n}{m}\right)},$$

i.e. the packing density of $`\mathrm{\Pi }`$ on words is equal to that on permutations.

###### Proof.

It is enough to prove that

$$\mu (\mathrm{\Pi },n,n)=\mathrm{max}\{\nu (\mathrm{\Pi },\sigma )|\sigma S_n\},$$

in other words, that there is a permutation in $`S_n`$ among the maximal $`\mathrm{\Pi }`$-containing words in $`[n]^n`$. Consider any maximal $`\mathrm{\Pi }`$-containing word $`\sigma [n]^n`$. Let $`n_i`$ be the multiplicity of the letter $`i`$ in $`\sigma `$. Let $`i_j`$ denote the $`j`$th occurrence of the letter $`i`$, and consider the map $`f:[n]^nS_n`$ induced by the map $`i_j_{r=1}^in_rj+1`$. Since all letters of each pattern in $`\mathrm{\Pi }`$ are distinct, $`\mathrm{\Pi }`$ occurs in $`f(\sigma )`$ at least at the same positions $`\mathrm{\Pi }`$ occurs in $`\sigma `$, so $`\nu (\mathrm{\Pi },f(\sigma ))\nu (\mathrm{\Pi },\sigma )`$. The rest is easy. $`\mathrm{}`$

Apart from computing packing densities of patterns, we would also like to determine which patterns have equal packing densities, which ones are asymptotically more packable than others, etc. For example, it is easy to see that the packing density is invariant under the usual symmetry operations on $`[l]^m`$: *reversal* $`r:\tau (i)\tau (mi+1)`$ and *complement* $`c:\tau (i)l\tau (i)+1`$, (packing density is also invariant under inverse $`i:\tau \tau ^1`$ when packing permutations into permutations). The operations $`r`$ and $`c`$ generate $`D_2`$, while $`r,c,i`$ generate $`D_4`$. Patterns which can be obtained from each other by a sequence of symmetry operations are said to belong to the same *symmetry class*.

###### Example 1.5

The symmetry class representatives of patterns in $`[3]^3`$ are $`111`$, $`112`$, $`121`$, $`123`$ and $`132`$. We know that $`\delta (111)=1=\delta (123)`$. Galvin, Kleitmann and Stromquist (independently, unpublished, see chronology in ) showed that $`\delta (132)=2\sqrt{3}30.4641`$. Thus, we only need to determine the packing densities of 112 and 121 to completely classify patterns of length 3.

Price  extended Stromquist’s results  to packing a single pattern $`\pi =1m(m1)\mathrm{}2`$ and handled other single patterns such as $`2143`$. Since we will also be concerned mostly with singleton sets of patterns $`\mathrm{\Pi }=\{\pi \}`$, we will write $`\delta (\pi )`$ for $`\delta (\{\pi \})`$, etc.

Price’s results deal with patterns of specific type, the so-called *layered* patterns.

###### Definition 1.6

A *layered* pattern is a strictly increasing sequence of strictly decreasing substrings. These substrings are called the *layers* of $`\sigma `$.

###### Notation 1.7

It easy to see that a layered pattern is uniquely determined by the sequence of its layer lengths, hence we may denote it by such sequence, e.g. $`\widehat{321}\widehat{54}\widehat{9876}=[3,2,4]`$, $`\widehat{1}\widehat{2}\widehat{3}=[1,1,1],\widehat{1}\widehat{32}=[1,2],\widehat{21}\widehat{3}=[2,1],\widehat{321}=[3]`$ are layered, with layers denoted by hats, while $`312,231`$ are non-layered.

In fact, note that the union of symmetry classes of layered patterns consists of exactly the permutations avoiding patterns in the symmetry classes of $`1342,1423,2413`$.

In , Stromquist proved a theorem (later generalized in ) on packing layered patterns into permutations. The inductive proof of this theorem defines a permutation (or a poset) $`\pi `$ to be *layered on top* (or *LOT*) if any of its maximal elements is greater than any non-maximal element. The set of these maximal elements is called the *final layer* of $`\pi `$ (even if $`\pi `$ is not necessarily layered).

###### Proposition 1.8

Let $`\mathrm{\Pi }`$ be a multiset of LOT permutations (not necessarily all distinct or of equal length). Then there is an LOT permutation $`\sigma ^{}`$ which maximizes the expression

$$\nu (\mathrm{\Pi },\sigma )=\underset{\pi \mathrm{\Pi }}{}a_\pi \nu (\pi ,\sigma ),a_\pi 0.$$
(1.1)
Furthermore, if the final layer of every $`\pi \mathrm{\Pi }`$ has size greater than 1, then every such $`\sigma ^{}`$ is LOT.

Applying this proposition inductively, , following , obtains

###### Theorem 1.9

Let $`\mathrm{\Pi }`$ be a multiset of layered permutations. Then there is a layered permutation $`\sigma ^{}`$ which maximizes the expression (1.1). Furthermore, if all the layers of every $`\pi \mathrm{\Pi }`$ have size greater than 1, then every such $`\sigma ^{}`$ is layered.

Following , we will also define the *$`\mathrm{}`$-layer packing density* $`\delta _{\mathrm{}}(\mathrm{\Pi })`$ for sets of layered permutations $`\mathrm{\Pi }`$ as the packing density of $`\mathrm{\Pi }`$ among the permutations with at most $`\mathrm{}`$ layers. It was shown in both of the above works that $`\delta (\mathrm{\Pi })=\underset{\mathrm{}\mathrm{}}{lim}\delta _{\mathrm{}}(\mathrm{\Pi })`$.

## 2 Monotone and layered patterns

The easiest type of patterns with repeated letters are those whose letters are nondecreasing (or non-increasing) from left to right. By analogy with layered patterns, we will consider nondecreasing patterns.

We will call a maximal constant segment of a word a *block*. For a letter $`a`$ and integer $`k1`$, we will define $`a^k=\underset{k}{\underset{}{a\mathrm{}a}}`$.

###### Theorem 2.1

Let $`\mathrm{\Pi }[l]^m`$ be a set of nondecreasing patterns $`\pi =1^{a_1(\pi )}2^{a_2(\pi )}\mathrm{}l^{a_l(\pi )}`$. For each $`\pi \mathrm{\Pi }[l]^m`$, let $`\widehat{\pi }S_m`$ be the layered pattern $`\widehat{\pi }=[a_1(\pi ),\mathrm{},a_l(\pi )]`$, and let $`\widehat{\mathrm{\Pi }}=\{\widehat{\pi }|\pi \mathrm{\Pi }\}`$. Then $`\delta (\mathrm{\Pi },k)=\delta _k(\widehat{\mathrm{\Pi }})`$ and $`\delta ^{}(\mathrm{\Pi })=\delta (\mathrm{\Pi })=\delta (\widehat{\mathrm{\Pi }})`$.

###### Proof.

There is a natural bijection between nondecreasing patterns on $`l`$ letters and layered patterns with $`l`$ layers. The map $`f`$ of Theorem 1.4, induced by the map $`i_j_{r=1}^ia_r(\pi )j+1`$ (where $`i_j`$ is the $`j`$th $`i`$ from the left), maps $`\pi `$ to $`\widehat{\pi }`$. Clearly, $`f^1`$ is induced by a map which takes each element in the $`i`$th layer (the $`i`$th basic subsequence, in general) to integer $`i`$. $`\mathrm{}`$

###### Example 2.2

Using the previous theorem and results of Price , we obtain $`\delta (112)=\delta (\widehat{21}\widehat{3})=2\sqrt{3}3`$, $`\delta (1122)=\delta (\widehat{21}\widehat{43})=3/8`$. More generally, for $`k2`$,

$$\delta (\underset{k}{\underset{}{1\mathrm{}1}}2)=ka(1a)^{k1},\text{ where }0<a<1,ka^{k+1}(k+1)a+1=0.$$

Similarly, for $`r,s2`$,

$$\delta (\underset{r}{\underset{}{1\mathrm{}1}}\underset{s}{\underset{}{2\mathrm{}2}})=\delta (\underset{r}{\underset{}{1\mathrm{}1}}\underset{s}{\underset{}{2\mathrm{}2}},\mathrm{\hspace{0.17em}2})=\left(\genfrac{}{}{0pt}{}{r+s}{r}\right)\frac{r^rs^s}{(r+s)^{r+s}}.$$

Using the results of Albert et al. , we also find that $`\delta (1123)=\delta (1233)=\delta (1243)=3/8`$, $`\delta (\{122,112\})=\delta (\{132,213\})=3/4`$.

###### Notation 2.3

A monotone nondecreasing pattern is uniquely determined by the sequence of its block lengths. Because of this and as a consequence of Theorem 2.1, we may by abuse of notation denote a monotone nondecreasing pattern by the sequence of its block lengths, e.g. $`112=[2,1],122=[1,2],123=[1,1,1]`$.

By analogy with layered permutations, we define layered strings as follows.

###### Definition 2.4

A string $`\pi [l]^m`$ is *layered* if it is a concatenation of a strictly increasing sequence of non-increasing substrings. In other words, $`\pi =\pi _1\mathrm{}\pi _r`$, where $`\pi _i`$ are non-increasing, and $`\pi _1<\mathrm{}<\pi _r`$ (that is any letter of $`\pi _i`$ is less than any letter of $`\pi _j`$ if $`ij`$). Substrings $`\pi _i`$ maximal with respect to these properties are called the layers of $`\pi `$.

###### Definition 2.5

Let us say that the layered permutation $`\pi `$ is simple if there exists a sequence $`\{\sigma _n\}`$ of layered permutations with $`\sigma _nS_n`$ such that every $`\sigma _n`$ has $`r`$ layers and $`lim_n\mathrm{}d(\pi ,\sigma _n)=\delta (\pi )`$.

Simple permutations are, as indicated by the name, the easiest type of permutations to calculate the packing density of. Indeed, it was show in \[6, Theorem 1.2\] that the layered permutation $`\pi `$ of type $`[m_1,\mathrm{},m_r]`$ with $`\mathrm{log}_2(r+1)\mathrm{min}\{m_i\}`$ is simple and that in this case

$$d(\pi )=\frac{m!}{m^m}\underset{k=1}{\overset{r}{}}\frac{m_k^{m_k}}{m_k!},$$

where $`m:=m_1+\mathrm{}+m_r`$.

###### Theorem 2.6

Let $`\pi `$ be layered pattern with each layer isomorphic to either $`k\mathrm{}1`$ or $`1\mathrm{}1`$. Let $`\pi ^{}`$ be the layered permutation with layer lengths equal to those of $`\pi `$. If $`\pi `$ is simple, then $`\delta (\pi )=\delta (\pi ^{})`$.

###### Proof.

Let us denote by $`m`$ the number of layers in $`\pi `$. If $`f`$ is an operation as in Theorems 1.4 and 2.1 and $`\pi `$ is layered, then $`\pi ^{}=f(\pi )`$ is layered. Since $`\pi ^{}`$ is simple, the $`\pi ^{}`$-maximal permutation is essentially one with $`m`$ layers of size proportional to those of $`\pi `$. But transforming this permutation into a layered pattern by changing a layer to block if the corresponding layer of $`\pi `$ is a block gives a pattern $`\sigma `$ for which $`d(\pi ,\sigma )\delta (\pi ^{})`$. Therefore $`\delta (\pi )\delta (\pi ^{})`$.

Let $`\sigma `$ be a $`\pi `$-maximal pattern. Then every occurence of $`\pi `$ in $`\sigma `$ is an occurence of $`f(\pi )=\pi ^{}`$ in $`f(\sigma )`$, so that $`\delta (\pi )\delta (\pi ^{})`$. It follows that $`\delta (\pi )=\delta (\pi ^{})`$. $`\mathrm{}`$

###### Example 2.7

Let $`\pi =k(k1)\mathrm{}1(k+1)^q`$. If $`q2`$ then

$$\delta (\pi )=\left(\genfrac{}{}{0pt}{}{k+q}{k}\right)\frac{k^kq^q}{(k+q)^{k+q}}.$$

If $`q=1`$ then $`\delta (\pi )=\delta (1^k2)=\delta ([k,1])`$, given in Example 2.2. The first claim follows by Theorem 2.6 and \[6, Theorem 1.2\]. The second claim follows by Theorem 2.6 and \[8, Theorem 5.2\].

###### Conjecture 2.8

If $`\mathrm{\Pi }`$ is a set of layered patterns, then $`\delta ^{}(\mathrm{\Pi })=\delta (\mathrm{\Pi })`$ and among maximal $`\mathrm{\Pi }`$-containing strings in $`[k]^n`$, there is one which is layered.

Next we will discuss a non-monotone type of patterns related to monotone patterns.

###### Theorem 2.9

Let $`\pi =1^p2^r1^q`$, for $`p,q,r1`$. Then

$$\delta (\pi )=\left(\genfrac{}{}{0pt}{}{p+q}{p}\right)\frac{p^pq^q}{(p+q)^{p+q}}\delta (1^{p+q}2^r)=\left(\genfrac{}{}{0pt}{}{p+q}{p}\right)\frac{p^pq^q}{(p+q)^{p+q}}\delta ([p+q,r]).$$

###### Proof.

Let $`\sigma `$ be a $`\pi `$-maximal pattern of length $`n`$. Denote by $`a_i`$ the number of $`i`$’s in $`\sigma `$. It is clear that $`\sigma `$ can be assumed to have at least two blocks at every height except the greatest.

Let us compare the hits (occurrences) of $`\pi `$ in $`\sigma `$ with those of the pattern $`\pi ^{}=1^{p+q}2^r`$ in $`\sigma ^{}=1^{a_1}2^{a_2}\mathrm{}k^{a_k}`$. Lets count the number of hits in each case with the blocks of $`1`$’s at height $`i`$ and the $`2`$’s at height $`j>i`$. The maximum number of such hits of $`\pi `$ in $`\sigma `$ occurs in the pattern $`i^{pa_i/(p+q)}j^{a_j}i^{qa_i/(p+q)}`$ and equals

$$\left(\genfrac{}{}{0pt}{}{pa_i/(p+q)}{p}\right)\left(\genfrac{}{}{0pt}{}{a_j}{r}\right)\left(\genfrac{}{}{0pt}{}{qa_i/(p+q)}{q}\right).$$

(This argument is strictly true only if $`a_i`$ is divisible by $`p+q`$, otherwise we have to round suitably.) On the other hand the hits of $`\pi ^{}`$ in $`\sigma ^{}`$ with the $`1`$’s and the $`2`$’s at these heights occurs in

$$\left(\genfrac{}{}{0pt}{}{a_i}{p+q}\right)\left(\genfrac{}{}{0pt}{}{a_j}{r}\right)$$

cases. By considering this ratio for large $`a_i`$, we find that

$$\nu (\pi ,\sigma )\left(\genfrac{}{}{0pt}{}{p+q}{p}\right)\frac{p^pq^q}{(p+q)^{p+q}}\nu (\pi ^{},\sigma ^{}).$$

(We do not need to consider small $`a_i`$’s since their contribution as $`n\mathrm{}`$ will be negligible.) But we know the density of $`\pi ^{}`$ by Theorem 2.1, and so it follows that

$$\delta (\pi )\left(\genfrac{}{}{0pt}{}{p+q}{p}\right)\frac{p^pq^q}{(p+q)^{p+q}}\delta ([p+q,r]).$$

On the other hand it is easy to see that we can construct patterns containing this many $`\pi `$’s; we take a $`\pi ^{}`$-maximal pattern and split each block except the one on the highest level into two blocks of relative sizes $`p`$ and $`q`$ and place the first before and the latter after all higher height blocks. Therefore the inequality is in fact is an equality, and the theorem is proved. $`\mathrm{}`$

###### Remark 2.10

If $`r>1`$ in the previous theorem, then

$$\delta ([p+q,r])=\left(\genfrac{}{}{0pt}{}{p+q+r}{r}\right)\frac{(p+q)^{p+q}r^r}{(p+q+r)^{p+q+r}},$$

and so

$$\delta (\pi )=\left(\genfrac{}{}{0pt}{}{p+q+r}{p,q,r}\right)\frac{p^pq^qr^r}{(p+q+r)^{p+q+r}}.$$

The $`\pi `$-maximizing string here is of the type $`1^a2^c1^b`$ with asymptotic layer lengths

$$(\frac{p}{p+q+r},\frac{r}{p+q+r},\frac{q}{p+q+r}).$$

###### Remark 2.11

When $`r=1`$, we can calculate $`\delta ([p+q,r])`$ as in Example 2.2, which yields

$$\delta (\pi )=\left(\genfrac{}{}{0pt}{}{p+q}{p}\right)p^pq^q\left(1(p+q)\alpha \right)\alpha ^{p+q1},$$

where $`\alpha (0,1)`$ is the unique solution of $`(1sx)^{s+1}=1(s+1)x`$ and $`s=p+q`$. It is easy to see that

$$\alpha =\frac{1}{s+1}(s+1)^{(s+2)}+O\left((s+1)^{2s}\right),$$

since for $`x_0=1/(s+1)(s+1)^{(s+2)}`$ we have

$$\begin{array}{cc}\hfill (1sx_0)^{s+1}+(s+1)x_01& =\left(\frac{1}{s+1}+\frac{s}{(s+1)^{s+2}}\right)^{s+1}(s+1)^{(s+1)}\hfill \\ & =\frac{s}{(s+1)^{2s+1}}+O\left((s+1)^{13s}\right)\hfill \end{array}$$

For $`s3`$, the error in $`\alpha `$ is at most $`4^6<0.00025`$, so $`x_0`$ approximates $`\alpha `$ up to at least 3 decimal places. Note that Theorem 2.6 also applies when $`p=0`$ or $`q=0`$. Note also that for $`a`$ in Example 2.2 we have $`a=1s\alpha `$.

The $`\pi `$-maximizing string here is of the type $`1^{a_1}2^{a_2}3^{a_3}\mathrm{}\mathrm{}3^{b_3}2^{b_2}1^{b_1}`$ with asymptotic layer lengths $`(p\alpha ,p\alpha (1s\alpha ),p\alpha (1s\alpha )^2,\mathrm{},\mathrm{},q\alpha (1s\alpha )^2,q\alpha (1s\alpha ),q\alpha )`$.

###### Example 2.12

$`\delta (121)=\frac{1}{2}\delta (112)=\frac{1}{2}\delta (213)=\sqrt{3}3/2`$. This completes the inventory of packing densities of 3-letter patterns by symmetry class.

| Symmetry class | 111 | 112 | 121 | 123 | 132 |
| --- | --- | --- | --- | --- | --- |
| Packing density | 1 | $`2\sqrt{3}3`$ | $`{\displaystyle \frac{2\sqrt{3}3}{2}}`$ | 1 | $`2\sqrt{3}3`$ |

## 3 Generalized patterns

Here we consider packing generalized patterns into words. *Generalized patterns* were introduced by Babson and Steingrímsson  and allow the requirement that some adjacent letters in a pattern be adjacent in its occurrences in an ambient string as well. For example, an occurrence of a generalized pattern $`21\text{-}3`$ in a permutation $`\pi =a_1a_2\mathrm{}a_n`$ is a subsequence $`a_ia_{i+1}a_j`$ of $`\pi `$ such that $`a_{i+1}<a_i<a_j`$. Clearly, in the new notation, classical patterns are those with all hyphens, such as $`1\text{-}3\text{-}2`$.

###### Notation 3.1

This notation (introduced in ) may be a little confusing since classical patterns (the ones with all hyphens) were previously written the same way as the generalized patterns with all adjacent letters (i.e. with no hyphens). From now on, we will use the generalized pattern notation. However, if we consider subword patterns (those with no hyphens), we may write $`\pi _\text{g}`$ for a generalized pattern $`\pi `$ without hyphens where the context allows for ambiguity.

If $`\pi [l]^m`$ is a generalized pattern with $`b`$ blocks of consecutive letters (i.e. $`b1`$ hyphens), then it is easy to see by considering the positions of the first letters of the blocks of $`\pi `$ that the maximum possible number of times $`\pi `$ can occur in $`\sigma [k]^n`$ is at most

$$\left(\genfrac{}{}{0pt}{}{nm+b}{b}\right)$$

(this yields $`\left(\genfrac{}{}{0pt}{}{n}{m}\right)`$ when $`b=m`$, i.e. when $`\pi `$ is a classical pattern).

In fact, this maximum is achieved when $`\pi `$ is a *constant* generalized pattern, i.e. any of the generalized patterns obtained from the constant strings $`11\mathrm{}1`$ by inserting hyphens at arbitrary positions (possibly, none). Obviously, maximal $`\pi `$-containing strings are the constant strings of length $`n`$. Thus, any set of constant generalized patterns has packing density 1. Similarly, any set $`\mathrm{\Pi }`$ of hyphenated identity generalized patterns has $`\delta (\mathrm{\Pi })=1`$.

Given a set of generalized patterns with $`b`$ blocks, $`\mathrm{\Pi }[l]^m`$, we define the packing density of $`\mathrm{\Pi }`$ similarly to that of a set of classical patterns. We will use the same notation as in Section 1 for the generalized patterns.

It is not difficult to see that the analog of Theorem 1.4 holds for generalized patterns as well.

###### Theorem 3.2

Let $`\mathrm{\Pi }S_m`$ be a set of generalized permutation patterns, then the packing density of $`\mathrm{\Pi }`$ on words is equal to that on permutations.

###### Proof.

The same argument as in Theorem 1.4 shows that among maximal $`\mathrm{\Pi }`$-containing strings in $`[n]^n`$ there is one that has no repeated letters. $`\mathrm{}`$

### 3.1 Generalized patterns without hyphens

###### Theorem 3.3

Let $`\pi =1^{a_1}2^{a_2}\mathrm{}l^{a_l}[l]^m(l>1)`$ be a nonconstant monotone generalized pattern without hyphens. If there exists a positive integer $`jl2`$ such that $`a_1a_{j+1}`$, $`a_i=a_{i+j}(2ilj1)`$ and $`a_{lj}a_l`$, then we denote by $`j_0`$ the least such $`j`$ and define $`M_\pi =a_2+\mathrm{}+a_{j_0+1}`$. Otherwise we set $`M_\pi =\mathrm{max}\{a_1,a_l\}+a_2+\mathrm{}+a_{l1}`$. In either case we have $`\delta (\pi )=\delta ^{}(\pi )=1/M_\pi `$.

###### Proof.

$`M_\pi `$ is the smallest shift at which $`\pi `$ overlaps with itself. The rest is clear. $`\mathrm{}`$

###### Theorem 3.4

Let $`\pi =[a_1,a_2,\mathrm{},a_l]S_m`$ be any $`l`$-layer $`(l>1)`$ generalized pattern without hyphens. Let $`M_\pi `$ be as in Theorem 3.3. Then $`\delta (\pi )=\delta ^{}(\pi )=1/M_\pi `$.

###### Proof.

The same mapping as in Theorem 2.1 shows that our $`\pi `$ has the same packing density as the corresponding monotone generalized pattern without hyphens of Theorem 3.3. $`\mathrm{}`$

###### Corollary 3.5

Let $`\pi _1=11\mathrm{}12_g[2]^m`$ and $`\pi _2=1m(m1)\mathrm{}2_g[m]^m`$, then $`\delta (\pi _1)=\delta ^{}(\pi _1)=1/(m1)`$ and $`\delta (\pi _2)=\delta ^{}(\pi _2)=1/(m1)`$.

For instance, $`\delta (112_g)=\delta ^{}(112_g)=1/2`$, $`\delta (132_g)=\delta ^{}(132_g)=1/2`$ and $`\delta (123_g)=\delta ^{}(123_g)=1`$.

### 3.2 Generalized patterns with one hyphen

The maximal number of occurrences of a generalized pattern in $`[l]^m`$ with one hyphen (i.e. with $`b=2`$ blocks) is $`\left(\genfrac{}{}{0pt}{}{nm+2}{2}\right)n^2/2`$ as $`n\mathrm{}`$.

###### Proposition 3.6

$`\delta (11\text{-}2)=\delta ^{}(11\text{-}2)=1`$.

###### Proof.

Let $`\sigma [k]^n`$ be a maximal $`(11\text{-}2)`$-containing word, then $`\sigma `$ is a monotone nondecreasing string in which letter $`i`$ occurs $`n_i`$ times, $`n_1+\mathrm{}+n_k=n`$. Then $`\mu (11\text{-}2,n,k)=\mathrm{max}\{_{i=1}^k(n_i1)(n_{i+1}+\mathrm{}+n_k):n_1+\mathrm{}+n_k=n\}`$. From here, it is not difficult to determine that $`\mu (11\text{-}2,n,k)n^2/2`$ as $`n\mathrm{}`$. Choose $`n_i`$’s to be such integers that $`|n_i\frac{n}{k}|<1`$ and $`|n_1+\mathrm{}+n_r\frac{rn}{k}|<1`$ for each $`r=1,2,\mathrm{},k`$. Then

$$\mu (11\text{-}2,n,k)\left(\frac{n}{k}\right)^2\left(\genfrac{}{}{0pt}{}{k}{2}\right),$$

out of $`\left(\genfrac{}{}{0pt}{}{n1}{2}\right)`$ maximum possible occurrences, and the result follows. $`\mathrm{}`$

###### Proposition 3.7

$`\delta (12\text{-}3)=\delta (21\text{-}3)=1`$.

###### Proof.

For pattern $`12\text{-}3`$, consider the identity permutation. For pattern $`21\text{-}3`$, consider the layered permutations of length $`n`$ with $`\sqrt{n}`$ layers of length $`\sqrt{n}`$. $`\mathrm{}`$

We think, but have not been able to prove rigorously, that $`\delta (12\text{-}1)=\delta ^{}(12\text{-}1)=1/3`$. At least $`\delta (12\text{-}1,2)=1/3`$, since in this case the string with the maximal number of occurrences of $`12\text{-}1`$ is of the type

$$\sigma =1212\mathrm{}\mathrm{1211..1}[2]^n$$

where the string $`12`$ occurs in $`\sigma `$ exactly $`d`$ times. So

$$\mu (12\text{-}1,n,2)=\underset{1dn}{\mathrm{max}}(d(d1)/2+d(n2d)),$$

and the maximum occurs at $`dn/3`$. It seems that allowing more symbols in $`\sigma `$ does not change anything, but here we could not find a proof.

A more general question related to this and somewhat analogous to the question of simple layered permutations is: for which $`\pi [k]^n`$ is $`\delta (\pi ,k)=\delta (\pi )`$?

## 4 The problem of the shortest common superpattern

This problem deals with packing different patterns into a word. Let $`n(l,m)`$ be the length of the shortest word which contains every pattern of length $`m`$ on at most $`l`$ letters. Clearly, $`n(l,m)=n(m,m)`$ for $`ml`$, hence we are interested only in the values of $`n(l,m)`$ for $`ml`$.

For example, $`n(2,2)=3`$ (since $`121`$ contains patterns $`11,12,21`$) and $`n(3,3)=7`$ (since $`1231231`$ contains patterns $`111,112,121,211,122,212,221,123,132,213,231,312,321`$).

###### Lemma 4.1

For $`ml`$, $`n(l,m)l(m1)+1`$.

###### Proof.

Consider the word $`\tau =(id_l)^{m1}1`$ where $`id_l=123\mathrm{}l`$. The rest is obvious. $`\mathrm{}`$

At least in the case of $`n(l,l)`$, this upper bound is apparently a lower bound as well, although we have not been able to prove it.

###### Conjecture 4.2

For any $`l1`$, $`n(l,l)=l^2l+1`$.

This differs from the corresponding result in  on permutation patterns, i.e. those in $`S_l`$, where the upper bound of $`3l^2/4`$ for the length of the shortest common superpattern was established, and there is numerical evidence that the actual value is closer to $`l^2/2`$.


format: text

text:
# Foliations with unbounded deviation on 𝑇²

## 1 Introduction

The goal of this note is to prove the following statement.

###### Theorem 1

There exists a $`C^{\mathrm{}}`$ foliation with 3 singular points on the two-dimensional torus such that any lifting of a leaf of this foliation on the universal covering of the torus is a dense subset of the covering.

This foliation is nonorientable and it has a transversal measure. The measure can be given locally out of the singularities by a closed 1-form.

Half translation surfaces. Let $`M`$ be a two-dimensional surface with a flat metric which has only conical singularities. The surface is called a half translation if the holonomy along any path on the surface is either $`Id`$ or -$`Id`$. It is clear that the angles around the conical points should be an integer multiple of $`\pi `$. The surface is called a translation if the holonomy is always Id.

A half translation structure gives rise to a family of foliations on the surface parametrized by the circle $`S^1`$. To construct a foliation from this family fix a tangent vector on the surface and move it to all the points of the surface by means of parallel translation. Since the holonomy is $`\pm Id`$ we obtain a foliation.

A half translation surface can have only a finite group of automorphisms (with the only one exception of a flat torus). But if we forget about the metric and remember only the underlying affine structure on the surface we can have an interesting group of automorphisms preserving affine structure.

The idea of the proof of the theorem 1 is the following. We construct a half translation torus with 3 singular points such that the underlying affine structure has a big group of automorphisms. In particular there is an automorphism of the torus which acts trivially in the first homology of the torus but is a locally hyperbolic map (in affine coordinates on the torus). The expanding foliation of this automorphism will be the foliation mentioned in the theorem 1.

Remarks. There is a classical resalt of A.Weil \[We\] about oriented foliation with finite number of singularities on $`T^2`$. The deviation of such a foliation is always bounded i.e. any lifting of any leaf of the foliation to the universal covering of the torus is contained in a finite neighborhood of a strait line. First example of a nonoriented foliation with unbounded deviation was constructed by A.D. Anosov \[An1\], \[An2\]. In \[EMZ\] you can find a good introduction to translation surfaces.

## 2 Construction of the foliation

Construction of the half translation structure on the torus. The half translation structure on the torus will be obtained from a usual flat torus by the operation of folding.

Definition of folding. Let $`[AB]`$ be a geodesic segment on a flat surface M. Cut M along $`[AB]`$ and denote by $`C_+`$ and $`C_{}`$ two centers of different shores of the cut. Glue together segment $`[AC_+]`$ with $`[C_+B]`$ and $`[AC_{}]`$ with $`[C_{}B]`$. On the resulting surface we obtain two new singular points with ’angles’ $`\pi `$ (these points appear from $`C_+`$ and $`C_{}`$) and a singular point with ’angle’ $`4\pi `$.

The torus we are looking for is the flat torus $`^2/(3)`$ folded along the segment $`[(1,0);(1,0)]`$. We denote this torus by $`T`$. The structure of the folded torus is given on the fig.2. The arrows connect pieces of the border of the rectangle that should be glued.

Affine automorphisms of $`T`$. Decomposition on cylinders. Consider the $`\mathrm{ℎ𝑜𝑟𝑖𝑧𝑜𝑛𝑡𝑎𝑙}`$ foliation (i.e. the foliation whose leaves are parallel to the $`x`$-axis) on the torus $`T`$ and remove the leaf passing through singular points. It cuts $`T`$ into the cylinder with height 1 and length 3. The horizontal foliation fills the cylinder by closed leaves of length 3. There is an obvious automorphism $`\gamma _h`$ of $`T`$ preserving the horizontal foliation. It fixes the singular leaf and it makes a twist of the cylinder. This map can be given by the formula $`\gamma _h(x,y)=(x+3y(mod3),y)`$.

Now consider the $`\mathrm{𝑣𝑒𝑟𝑡𝑖𝑐𝑎𝑙}`$ foliation. This foliation has three connected singular leaves. They split $`T`$ into two cylinders $`1\times 1`$ and $`2\times 1`$ (here and later the cylinder $`m\times n`$ is the cylinder with the height $`m`$ and the length $`n`$). There is an automorphism $`\gamma _v`$ of $`T`$ which makes the full twist of the cylinder $`1\times 1`$ and it makes the half twist of the cylinder $`2\times 1`$. The automorphism $`\gamma _v`$ fixes the singular point having the conical angle $`4\pi `$ and permutes two singular points having the conical angle $`\pi `$.

There is a natural map from the group of affine automorphisms of $`T`$ to $`PSL(2,)`$. It is given by the action of the automorphisms on the tangent space of $`T`$. The images of $`\gamma _h`$ and $`\gamma _v`$ are given by

$$\left(\begin{array}{cc}1& 3\\ 0& 1\end{array}\right),\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)$$

These matrixes are defined only up to a sign,

The automorphism we are looking for is $`(\gamma _v\gamma _h^1\gamma _v)^4`$.

Construction of the foliation. We denote by $`_1`$ the expanding foliation of the map $`\gamma _v\gamma _h^1\gamma _v`$ and by $`_2`$ the contracting foliation. These foliations are parallel to the directions $`(\sqrt{3},1)`$ and $`(\sqrt{3},1)`$.

###### Lemma 2

Any leaf of the foliation $`_1`$ is a dense subsets of the torus.

The proof of this lemma is standard. It follows from the absence of separatrices joining singular points of the foliation.

## 3 Proof of the theorem

Action on homology. We note by $`e_1`$ the class in the homology group of a nonsingular leaf of the horizontal foliation and we note by $`e_2`$ the class of homology of a leaf of the vertical cylinder $`1\times 1`$. It is clear that $`e_1,e_2`$ form a basis for $`H_1(T,)`$.

###### Lemma 3

The action of the induced homomorphism $`\gamma _v\gamma _h^1\gamma _v`$ on the fist homology of $`T`$ with respect to the basis $`(e_1,e_2)`$ is given by the matrix

$$\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$$

Proof. Since $`\gamma _h`$ makes the single twist of the horizontal cylinder $`1\times 3`$ and $`\gamma _v`$ makes the single twist of the vertical cylinder $`1\times 1`$ the action of $`\gamma _h`$ and $`\gamma _v`$ in $`H_1(T,)`$ is given by the matrixes

$$\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)$$

It proves the lemma. $`\mathrm{}`$

Lemma 3 implies that the induced action of $`(\gamma _v\gamma _h^1\gamma _v)^4`$ on $`H_1(T,)`$ is trivial.

Action on the universal covering of torus $`T`$. The universal covering of $`T`$ can be viewed as the usual plane $`^2`$ folded along the segments $`[(n,3k1),(n,3k+1)]`$, $`n,k`$. After folding the origin $`(0,0)`$ of the plane gives rise to two singular points of the angle $`\pi `$. We denote these points by $`(0,0_+)`$ and $`(0,0_{})`$. The action of $`\gamma _v\gamma _h^1\gamma _v`$ on $`T`$ can be lifted to the action on the folded plane in such a way that point $`(0,0_+)`$ is fixed. All singular points of type $`(m,3n_+)`$ can be naturally identified with $`H_1(T,)`$. So these points are invariant under the fourth power of the automorphism $`\gamma _v\gamma _h^1\gamma _v`$ (lemma 3).

Denote by $`\stackrel{~}{_1}`$ and $`\stackrel{~}{_2}`$ the liftings of the foliations $`_1`$ and $`_2`$ on the universal covering of the torus $`T`$. Denote by $`\stackrel{~}{f_1}`$ the leaf of $`\stackrel{~}{_1}`$ starting at the point $`(0,0_+)`$ and by $`\stackrel{~}{f_2}`$ the leaf of $`\stackrel{~}{_2}`$ starting in $`(3,0_+)`$

###### Lemma 4

The leaf $`\stackrel{~}{f_1}`$ of the foliation $`\stackrel{~}{_1}`$ comes arbitrary close to the point $`(3,0_+)`$.

Proof. The point $`(\frac{3}{2},\frac{\sqrt{3}}{2})`$ is an intersection of the leaves $`\stackrel{~}{f_1}`$ and $`\stackrel{~}{f_2}`$. The transformation $`(\gamma _v\gamma _h^1\gamma _v)^4`$ preserves points $`(0,0_+)`$ and $`(3,0_+)`$ so it preserves leaves $`\stackrel{~}{f_1}`$ and $`\stackrel{~}{f_2}`$. It means that the point $`(\gamma _v\gamma _h^1\gamma _v)^4(\frac{3}{2},\frac{\sqrt{3}}{2})`$ is also a point of the intersection of $`\stackrel{~}{f_1}`$ and $`\stackrel{~}{f_2}`$. Now use the fact that the action of $`(\gamma _v\gamma _h^1\gamma _v)^4`$ contracts $`\stackrel{~}{f_2}`$. Applying the map $`(\gamma _v\gamma _h^1\gamma _v)^4`$ inductively we construct a sequence of intersections of $`\stackrel{~}{f_1}`$ and $`\stackrel{~}{f_2}`$ which tends to the point $`(3,0_+)`$. $`\mathrm{}`$

Now we give a proof of the theorem 1 for the foliation $`\stackrel{~}{_1}`$ and its leaf $`\stackrel{~}{f_1}`$. Since $`\gamma _v\gamma _h^1\gamma _v`$ performs a cyclic permutation of points $`(\pm 3,0_+)`$, $`(0,\pm 1_+)`$ (lemma 1) the leaf $`\stackrel{~}{f}_1`$ approaches arbitrary close to all these points. It means that the closure of $`\stackrel{~}{f}_1`$ in $`^2`$ contains the leaves of $`\stackrel{~}{_1}`$ passing through fore points $`(\pm 3,0_+)`$, $`(0,\pm 1_+)`$. Since $`\stackrel{~}{_1}`$ is periodic in $`^2`$ the same argument tells that the leaf $`\stackrel{~}{f_1}`$ approaches arbitrary close to every singular point of the type $`(3n,k_+)`$. So its closure in the plane contains the closure of the union of all leaves of the foliation $`\stackrel{~}{_1}`$ passing through singular points of type $`(3n,k_+)`$. The last closure is the whole plane (lemma 2). $`\mathrm{}`$

Final remarks. The leaf $`\stackrel{~}{f_1}`$ constructed in the theorem 1 is everywhere dense in the plane. One can see that this leaf propagates in the plane with a logarithmic speed.

Here is an optical interpretation of the constructed foliation. Consider the two dimensional plane $`^2`$ with the integer lattice $`^2`$. Put in any vertex of the lattice a $`90^o`$ rotation invariant cross in such a way that all the picture is $`^2`$ invariant (fig.3). Send a light in the direction parallel to the bissectrix of crosses and consider it reflections from edges of crosses. The constructed ray corresponds to a leaf of some foliation on the two-dimensional torus with 3 singular points.

Acknowledgments. The author is grateful to M.Kontsevich for introducing to the subject and very helpful discussions, to A.Glutsuk for communication of results of the article \[An1\] and to A.Zorich for his interest to the work.


text:
# Phase-field approach to heterogeneous nucleation

## I Introduction

Processes driven by nucleation and growth have attracted much attention during past decades, from a fundamental point of view  and for tailoring some technological applications. Some of them are: the recrystallization of deformed metals , controlling the nucleation and growth of islands on terraces in order to get large scale arrays of nanostructures , or the manufacturing of thin-film transistors which are the basic devices for some applications as solar cells , random access static memories , or active matrix-addressed flat-panel displays .

In all the above-mentioned processes, a metastable phase decays into a stable one via a fluctuation which produces a critical cluster of atoms (for instance, a critical island in the case of terrace growth, or a critical atom cluster in the case of crystallization). This transition is called nucleation. At a certain fixed temperature, clusters with sizes greater than a critical one become stable nuclei; otherwise they shrink and eventually vanish. Such a critical size arises from the competition between the surface tension and the chemical potential difference between phases, yielding an energy barrier that has to be overcome to build up a critical nucleus. For the examples presented above, the system can be considered, under certain conditions, two dimensional so it is straightforward to write the free energy of circular grain of radius $`r`$:

$$\mathrm{\Delta }F(r)=2\pi r\sigma \pi r^2\mathrm{\Delta }\mu /\mathrm{\Omega },$$
(1)
where, $`\sigma `$, $`\mathrm{\Delta }\mu `$, and $`\mathrm{\Omega }`$ are the surface tension, the chemical potential difference between phases, and the mean volume occupied by an atom, respectively.

Notwithstanding, in some practical situations this transformation is not perfectly homogeneous due to, for instance, the presence of physical boundaries, such as terrace steps, the interplay between different kinds of particles, or the appearance of impurities , or even to some preexisting order embedded in the initial phase formed during its manufacturing . The lack of uniformity not only catalyzes the transformation but affects the final size distribution of grains .

Much work has been devoted to the study of homogeneous nucleation in different contexts , and to the so-called site saturation in which nucleation takes place just at the beginning of the transformation , but only a few studies were devoted to the intermediate situations in which nucleation is heterogeneous, both in space and in time. The spatial extent of heterogeneity can be measured using the fraction of transformed material (or more generically, the volume fraction of the newly transformed phase) onto the stable phase which often obeys the Kolmogorov-Johnson-Mehl-Avrami (KJMA) equation :

$$X(t)=1\mathrm{exp}\left\{\left[(t\tau _i)/\tau _c\right]^m\right\},$$
(2)
where $`\tau _i`$ is the incubation time, $`\tau _c`$ is the characteristic transformation time, and $`m`$ is an exponent which characterizes the degree of heterogeneity of the system and its dimensionality . For instance, for a two-dimensional system in the two limiting cases, homogeneous nucleation and site saturation, $`m`$ takes the values $`3`$ and $`2`$, respectively.

There have been some approaches to the problem of heterogeneous nucleation in the past. For instance, Karpov et al.  generalized the homogeneous case by adding random contributions to the surface tension and the chemical potential, which affects the nucleation rate. A similar static approach was followed by Liu , who calculated the variation suffered by the surface tension and the chemical potential due to the presence of a circular impurity. Other authors such as Enomoto  or Weinberg  considered a phenomenological time-dependent nucleation rate to analyze heterogeneous nucleation. More recently, Castro and co-workers  have introduced a lattice model to determine both time-dependent and spatial effects of heterogeneities.

The main aim of this paper is analyze, both analytically and numerically, the origin and effect of impurities or defects on grain nucleation and subsequent growth. The rest of the paper is organized as follows. In Sec. II we introduce a phase field model obtained from a functional free energy and report some results for homogeneous nucleation. In Sec. III, we include impurities through the boundary conditions of the main equation and calculate the effect of those impurities in nucleation rate and KJMA exponent. In Sec. IV, we consider a more general case in which the disorder can be due to mechanisms which are different with the ones presented in Sec. III. These mechanisms are introduced as quenched noise. Finally, we end the paper by summarizing the main results in Sec. V, focusing on the applicability of the equations to different physical processes, and discussing further generalizations of the model.

## II Evolution equation

Phase-field models have been widely studied in the last few years, as an efficient computational tool to simulate some moving boundary problems which, in the so-called sharp interface limit (or sometimes thin interface limit, see below), are physically equivalent . Among them, Jou and Lusk  studied homogeneous nucleation and site saturation using a one-field phase field model. The main objection of their approach is the fact that the critical clusters are created ad hoc so, on the one hand, the model explains the KJMA equation just by construction and, on the other hand, it cannot explain the existence of an incubation time observed in the experiments. A similar approach was used by Roy et al.  to study nucleation in a phase field model with nonlocal interactions. Recently, more complex phase field models have been proposed for similar systems: The so-called multi-phase-field models , in which every cluster appearing embedded in the metastable phase is described by its own field and, on the other hand, those models in which the phase field is coupled with another field representing the orientation of crystalline planes . The main problem concerning the multiphase-field models is that the free energy depends explicitly on the grain orientation (or phase). This is solved by the second ones but, besides this, what depends on the grain orientation is the grain-boundary velocity. Although this second kind of approach seems to be very promising, in both cases the symmetry under rotations of the grain crystalline planes is broken.

In this paper we are interested only in the overall dynamics of the nucleation process, thus, we simply generalize the model presented in Ref. , supplementing it with thermal noise to make explicit the temperature dependence of the system. To make clearer this generalization, we advance that the noise term is the driving force for nucleation, so it is not needed to create artificially critical clusters every integration time step as in Ref. .

Let us introduce the main ingredients of the model. We define an order parameter $`\varphi `$, which takes the value $`1`$ in the metastable phase and $`+1`$ in the stable phase. The grain boundary (which separates both phases) is located at $`\varphi =0`$ . We also define a free-energy functional which takes into account the grain-boundary energy and the chemical potential difference between phases. Generically, we can define

$$[\varphi (𝐫,t)]=𝑑x𝑑z\left(\frac{W^2}{2}|\varphi |^2+f(\varphi )\lambda g(\varphi )\right),$$
(3)
where $`f(\varphi )`$ and $`g(\varphi )`$ are generic functions of the order parameter: $`f(\varphi )`$ is an even function of $`\varphi `$ with local minima at $`\pm 1`$ and $`g(\varphi )`$ breaks the symmetry between phases. As we will see below, $`W`$ is a typical length scale related to the surface tension, and $`\lambda `$ is a dimensionless parameter proportional to the chemical potential difference between phases. We will assume that the system relaxes towards equilibrium according to the following evolution equations :

$`\tau _t\varphi `$ $`=`$ $`{\displaystyle \frac{\delta }{\delta \varphi }}+\theta `$ (4)
$`\tau _t\varphi `$ $`=`$ $`W^2^2\varphi f_\varphi (\varphi )+\lambda g_\varphi +\theta ,`$ (5)
where $`\tau `$ is the typical time scale at which the atoms from a phase incorporate to the other; $`f_\varphi `$ and $`g_\varphi `$ denote the partial derivatives of $`f`$ and $`g`$ with respect to $`\varphi `$. Finally, $`\theta (𝐫,t)`$ is a Gaussian white noise which stands for the thermal fluctuations of the system, with zero mean and correlations given by the fluctuation-dissipation theorem :

$$\theta (𝐫,t)\theta (𝐫^{},t^{})=2\tau k_BT\delta (𝐫𝐫^{})\delta (tt^{}),$$
(6)
$`T`$ being the temperature at which the transformation takes place.

To be more specific, we choose

$$f(\varphi )=\varphi ^2/2+\varphi ^4/4,$$
(7)
The main advantage of this choice is that Eq. (5) admits a simple stationary solution given by:

$$\varphi _0(z)=\mathrm{tanh}\left(\frac{z}{\sqrt{2}W}\right),$$
(8)
which represents a front of characteristic width $`W`$ placed at $`z=0`$. In the same way, we choose :

$$g(\varphi )=\varphi \frac{\varphi ^3}{3}.$$
(9)
The main reason to use Eq. (9) instead of the traditional one, $`g(\varphi )=\varphi `$, is that, in the first case, $``$ has local minima at $`\pm 1`$ independently of the value of $`\lambda `$, otherwise, those minima would be $`\lambda `$ dependent.

Using Eq. (8) we can make some considerations about the stability of a given fluctuation. To compare with the classical nucleation theory , let us consider the free energy difference between a system which is initially at the metastable phase, and a circular grain of radius $`R`$ given approximately by $`\varphi _0(rR)`$. Thus it can be straightforwardly shown that, in the thin interface limit :

$$\mathrm{\Delta }[\varphi =\varphi _0][\varphi =1]2\pi R\sigma _l\pi R^2\mathrm{\Delta }\mu /\mathrm{\Omega },$$
(10)
where $`\sigma _l=2\sqrt{2}W/3`$ is the surface tension, and $`\mathrm{\Delta }\mu /\mathrm{\Omega }=\lambda \delta g`$, with $`\delta g=g(+1)g(1)`$. This equation shows the competition between the gain arising from the reduction of the grain perimeter, and that related to the increasing of its size. As we mentioned above, the critical radius arises from this competition. Thus if we take into account that $`\mathrm{exp}[\mathrm{\Delta }(R)/k_BT]`$ can be interpreted as the barrier that has to be overcome to create a nucleus of radius $`R`$, then the critical radius is the one which minimizes that barrier, the one which maximizes $`\mathrm{\Delta }`$. Hence

$$R^{}=\frac{2\sqrt{2}W}{3\lambda \delta g},$$
(11)
and its corresponding critical free energy is given by

$$\mathrm{\Delta }^{}=\frac{8\pi W^2}{9\lambda \delta g}.$$
(12)
Once we have established the connection between the physical system and the model, let us numerically check its capability to reproduce the KJMA equation (2). In Fig. 1 we show the results from simulation using the Euler integration scheme , and the corresponding KJMA fit to the fraction of transformed material, $`X(t)`$, taking $`m=3`$ (measured as the fraction of sites where $`\varphi >0`$). We have reproduced this result for a wide range of parameters. The first important result concluded from these simulations is related to the nonzero value of the incubation time $`\tau _i`$. This time is almost always present in the experiments, and is related to the free-energy difference between the well $`\varphi =1`$ and the maximum of the free-energy separating this well with the one at $`\varphi =+1`$. Similar results were obtained by Elder et al.  in the context of eutectic growth. Despite the good agreement between simulations and theory, it is important to stress that the derivation of KJMA equation makes uses of some assumptions: infinite system size, uniform nucleation, spherical particles, and constant growth rate. Some care must be taken in this respect. Despite Eq. (5) provides circular grains, those grains do not grow at constant velocity. Actually, the grain radius is related to time through the following equation:

$$t=\frac{1}{V}\left[RR_0+R^{}\mathrm{ln}\left(\frac{RR^{}}{R_0R^{}}\right)\right],$$
(13)
where $`R_0`$ is the initial grain radius and $`V`$ is the grain growth velocity which, in the thin interface limit, is given by

$$V=\frac{3W\lambda \delta g}{\sqrt{8}\tau }.$$
(14)
Thus the velocity is constant just after a short time of order $`R^{}/V`$. Hence there are slight deviations of the numerical data from the KJMA equation up to times of order $`R^{}/V`$. Besides this, the infinite size condition has not to be fulfilled necessarily. Actually, the KJMA equation is still valid when the number of grains contributing to growth is large, when the system size $`L`$, is much larger than the characteristic length scale related to nucleation and growth, $`l=(V/N)^{1/3}`$, $`N`$ being the nucleation rate . Finally, the KJMA equation does not take into account interfacial effects that govern the growth just before the grains meet each other, so there are also some differences between the numerical data and the KJMA equation predictions, in this case, at the later stages of the transformation. Fortunately, the mentioned deviations from the KJMA equation at short and long times are quite small. Notwithstanding, it is quite convenient to perform the fitting of $`X(t)`$ between the $`1\%`$ and the $`99\%`$ to improve it (see Ref.  for further details about the validity of KJMA equation).

To point out the crucial role played by thermal noise in Eq. (5), we show in Fig. 2 the spontaneous and continuous nucleation and growth of grains, which are almost circular despite the underlying integration lattice is square. In other words, the model captures all the essential ingredients of a first-order transition, not only in terms of the free-energy difference between phases, but also in terms of the dynamical path followed from the metastable phase to the stable one.

## III Nucleation at defects

In the previous section we have demonstrated the validity of our model to describe homogeneous nucleation. This section deals with nucleation in the neighborhood of some parts of the system which are structurally different, namely, at domain walls or at the surrounding of foreign particles. Thus we will consider two kinds of defects: Walls and circular defects. Our main assumption here is that the particles in the metastable phase do not interact with the defects, which is included in the model through the boundary condition

$$\frac{\varphi }{n}=\varphi 𝐧|_b=0,$$
(15)
where the subscript $`b`$ stand for boundary; and $`n`$ is the normal coordinate to the defect boundary.

In order to clarify the relevance of this boundary condition on nucleation we have integrated Eq. (5) with the prescribed condition (15). Figure 3 shows how nucleation is

enhanced at the walls. Actually, this is the most relevant mechanism of nucleation when the chemical potential difference between phases, $`\mathrm{\Delta }\mu \lambda `$, is small. The situation changes dramatically if we increase $`\lambda `$ (or if we raise the temperature). This can be better understood in the context of island formation in which $`\lambda `$ can be understood as the flux of particles arriving at the surface. In such case, when the flux of particles is large, islands nucleate everywhere in the sample due to the large probability of dimer formation , as can be seen in Fig. 3.

As we have mentioned, the other interesting geometry is circular one. Thus Fig. 4 shows how nucleation is enhanced at the boundary of a circular impurity. Moreover, we can use this result to relate the KJMA exponent, $`m`$, and the effect of impurities using a finite concentration $`c`$, of circular impurities of small radius. The results are plotted in Fig. 5, where time has been rescaled to reveal the differences between several $`m`$ values, for different temperatures. At this point, we want to stress that this dependence of $`m`$ on temperature has been obtained qualitatively in some Pd1-xSix crystallization experiments . Furthermore, if we change the concentration of impurities, we can also modify the value of $`m`$ (see inset in Fig. 5). This result agrees with that in Ref. . Thus the effect of temperature in KJMA equation is not only present in the characteristic times, $`\tau _i`$ and $`\tau _c`$, but even in the exponent $`m`$ in a nontrivial way.

## IV Generalized heterogeneous nucleation

The results reported in the last section demonstrates that our phase field model is a powerful tool to further advance in the knowledge and modeling of nucleation and growth phenomena, in the homogeneous case and in the situation where impurities catalyze the transformation in a subtle way. Notwithstanding, the heterogeneities of a sample are not always due to isolated impurities. This is the main reason for the generalization that we introduce in this section.

We will assume that nucleation is heterogeneous, not in a phenomenological way as in other proposed models , but sticking to the classic ideas due to Cahn . Thus the system contains regions with some extra energy (for instance due to some order produced during deposition of the amorphous material), or at which nucleation is more probable. Let us show how we can cast this model on a mathematical footing.

### A Quenched white noise

An intuitive way to introduce the latter idea in our model is sustained on the assumption that the chemical potential depends locally on position,

$$\lambda \lambda +\rho (𝐫),$$
(16)
$`\rho (𝐫)`$ being a Gaussian random variable with zero mean and correlations given by

$$\rho (𝐫)\rho (𝐫^{})=\mathrm{\Lambda }\delta (𝐫𝐫^{}),$$
(17)
where $`\mathrm{\Lambda }`$ measures the degree of heterogeneity of the sample. The main part of this generalization is that it does not make any specific assumption about the physical system under consideration. Unfortunately, numerical simulations suggest that it cannot provide a KJMA exponent $`m`$, different from $`3`$ (homogeneous nucleation) . Nevertheless, before exploring new possibilities, we will show that the quenched white noise given by Eq. (17) unveils that disorder enhances nucleation (Fig. 6).

The fact that white noise is not capable to provide realistic values of $`m`$ stems with intuition but, actually, it is very physical. Let us make some calculations to show it clearly. If we perform again the thin interface limit of Eq. (5) with $`\lambda \lambda +\rho (𝐫)`$, we obtain the stochastic version of Eq. (10). Hence:

$$\mathrm{\Delta }=2\pi R\sigma _l\pi R^2\mathrm{\Delta }\mu /\mathrm{\Omega }+\chi (R),$$
(18)
where $`\chi (R)`$ is given by

$$\chi (R)=\delta g𝑑𝐫\rho (𝐫)\mathrm{\Theta }(rR),$$
(19)
$`\mathrm{\Theta }`$ being the Heaviside step function. The new noise term $`\chi (R)`$ has also zero mean and correlations given by:

$$\chi (R)\chi (R^{})=\delta g\mathrm{\Lambda }\pi R^2\delta (RR^{}).$$
(20)
For brevity, we denote $`F=\mathrm{\Delta }`$, $`F_0=2\pi R\sigma _l\pi R^2\mathrm{\Delta }\mu /\mathrm{\Omega }`$ and $`D(R)=\delta g\mathrm{\Lambda }\pi R^2`$. Consequently, for every value of $`R`$ the free energy is a random number with a distribution given by (recall that $`\rho `$ is Gaussian)

$$P(F)=\frac{1}{\sqrt{2\pi D(R)}}e^{(FF_0)^2/2D(R)}.$$
(21)
Taking into account that $`\mathrm{exp}[\mathrm{\Delta }(R)/k_BT]`$ can be understood as the barrier that has to be overcome to create a nucleus of radius $`R`$, the critical radius will be simply the one which minimizes that barrier. In the simplest case where $`\mathrm{\Lambda }=0`$, this minimum is the same as the maximum of $`\mathrm{\Delta }`$, but the situation changes because now $`\mathrm{\Delta }`$ is a random variable. Thus in the physical system, we can only obtain information about its mean value:

$$e^{F/k_BT}=𝑑Fe^{F/k_BT}P(F)=\mathrm{exp}\left[\frac{D(R)}{2(k_BT)^2}\frac{F_0}{k_BT}\right].$$
(22)
To be more specific, the critical radius is the solution of

$$\frac{d}{dR}\left(\frac{D(R)}{2k_BT}F_0\right)_{R=R^{}}=0R^{}=\frac{2\sqrt{2}W}{3\delta g(\lambda +\mathrm{\Lambda }/2k_BT)}.$$
(23)
This is the result we were seeking: The critical radius diminishes so that the nucleation rate increases and also depends on temperature. But, as we anticipated above, the only effect of quenched white noise is changing the time and length scales of the system, but not the nucleation conditions necessary to obtain $`m<3`$. Moreover, if we re-scale both length and time, then the systems with $`\mathrm{\Lambda }=0`$ or $`\mathrm{\Lambda }0`$ cannot be distinguished. There is another interesting point of this theory which should be remarked. In some experiments of recrystallization the a priori value of $`\mathrm{\Delta }^{}`$ is actually much smaller than that measured from the experiments , confirming that there is some kind of disorder which affects significantly this magnitude.

### B Quenched colored noise

At this point, we must collect some of the successful ingredients of the theory and try to find out which must be the new ones in order to provide a general model of heterogeneous nucleation. Then, the main question is: What was implicit in the approach to heterogeneous nucleation in Sec. III which is missing in Sec. IV A? The answer is related to the new length scale introduced in Sec. III through the concentration of impurities (and which is proportional to $`c^{1/2}`$). Therefore we need both ingredients: disorder and a new independent length scale. The simplest way to include both is by means of a quenched colored noise term:

$$\rho (𝐫)\rho (𝐫^{})=\mathrm{\Lambda }e^{(𝐫𝐫^{})^2/2l_c^2}.$$
(24)
For the sake of completeness we have performed the simulations below using Ornstein-Uhlenbeck correlations  instead of Gaussian as in Eq. (24), but the results did not change significantly. With this choice we have the same free-energy distribution of probability $`P(F)`$ as in the white noise case, and also introduced the required length scale. As we expected, the KJMA exponent $`m`$ depends on the correlation length $`l_c`$ as we show in Fig. 7 as also the nucleation rate is larger than in the homogeneous case. These results can be straightforwardly understood in terms of the involved characteristic length scales, the nucleation and growth length scale, $`l=(V/N)^{1/3}`$, and the quenched noise correlation length, $`l_c`$. Thus if $`l_cl`$ then the system hardly see the defects, and it is almost homogeneous, so $`m3`$. On the contrary, if $`l_cl`$, as grains nucleate preferentially at the defects, and they grow so fast that they impinge to each other at a mean distance $`l_c`$, so there is not enough time to allow other grains to nucleate. Consequently, $`m2`$ because every grain that nucleates does it mainly at the beginning of the transformation. Note that these assumptions are valid whenever both $`l`$ and $`l_c`$ are much smaller than the system size $`L`$. Notwithstanding, some care must be taken when simulating the model using large values of $`l_c`$ because the nucleation events are restricted to the surroundings of the defects so there are not many grains to sustain the validity of the KJMA equation.

Therefore the latter result contains relevant physical information relative to the basic conditions yielding an exponent $`m<3`$. For instance, it is consistent with those crystallization experiments of Si1-xGex by Olivares et al.  or recrystallization of Pd1-xSix by Price . In the first case that correlation length could be related to the concentration of preexisting SiGe crystals created during deposition, and in the second case with the former polycrystalline structure which has been deformed before recrystallization.

## V Discussion and Conclusions

In this paper we investigated a phase field model modeling nucleation and growth events, such as crystallization, island formation, or recrystallization. Starting from a Langevin equation we have shown how it is a simple (and computationally efficient) way to explore homogeneous nucleation, in terms of the well-known description provided by the KJMA equation, Eq. (2). Taking this equation as a starting point, we have provided several approaches to the problem of heterogeneous nucleation. The first approach is related to the existence of defects which are inert for the main growing material, such as wall domains or impurities. In both cases we have shown how nucleation is enhanced near those defects. Moreover, a finite concentration of isolated defects is able to modify the value of the KJMA exponent $`m`$, which takes values lower than $`m=3`$, the known value for homogeneous nucleation. This kind of defects can be suitable to study secondary crystallization, island nucleation in heteroepitaxial systems (if one of the growing particles presents a slow dynamics compared to the others), or nucleation at step edges in terrace growth. In particular, wall defects can be used to investigate the influence of a terrace step on island formation (note that $`\lambda `$ plays the role of the flux of particles arriving at the terrace). In fact, the competition between dimer formation and nucleation at step edges has been reported in Ref. , and can be graphically seen in Fig. 3. Generalizing the model to higher dimensions, this kind of wall defect could simulate the glass substrate on which the amorphous material is grown prior to crystallization. In the context of amorphous crystallization, circular defects can also be understood as crystals created at the growing stage, before crystallization takes place.

We have also presented a generalized model for heterogeneous nucleation which deals statistically with imperfections or impurities by means of a quenched noise term. The main result is related to the fact that this quenched noise must be spatially correlated to provide a general description in terms of the KJMA exponent. As we mentioned above, the correlation length can be related to preexisting crystalline regions embedded in the amorphous host or, some deformed polycrystalline structure, but it may also be used to quantify the effect on island formation of mechanical stresses caused by the growth of multilayer devices.

Due to the general character of the model, it can be easily generalized. For instance, a model that takes into account the possible time dependence of the disorder should include two fields: the phase-field and another one related to the motion of impurities. Besides this, sometimes the nucleating grains present some kind of anisotropy that should be included in the free-energy functional, given by Eq. (3). Moreover, the model presented is only suitable for isothermal transformations so, to study non isothermal effects, we should couple the phase field with an evolution equation for the temperature, similar to some prescriptions provided in the context of non-isothermal eutectic crystallization . Finally, there is some work left to do related to the suitable range of parameters which allow comparisons with experimental data and also to improve the efficiency of the numerical simulations, in particular when using circular impurities to simulate heterogeneous nucleation.

###### Acknowledgements.

The author thanks A. Sánchez, R. González Cinca, and T. Arribas for useful discussions and helpful comments, and F. Domínguez-Adame for a critical reading of this manuscript. This work has been partially supported by DGES (Spain) Grant No. BFM2000-0006.


text:
# Band structure of new superconducting AlB2-like ternary silicides M(Al0.5Si0.5)2 and M(Ga0.5Si0.5)2 (M= Ca, Sr and Ba).

(28 November 2002)

## Abstract

The electronic band structures of the new superconducting (with TC up to 7.7K) ternary silicides M(A0.5Si0.5)2 (M= Ca, Sr, Ba; A= Al, Ga) in the AlB2-type structure have been investigated using the full-potential LMTO method. The calculations showed that the trend in transition temperatures doesn’t follow the changes in the density d-states at the Fermi level and probably is associated with phonon-mode frequencies.

E-mail: shein@ihim.uran.ru

The discovery of superconductivity (SC) in hexagonal AlB2-like MgB2 (Tc $``$ 39K) Akimitsu  and creation of promising materials based thereon2-4 have attracted a great deal of interest in related compounds isostructural with magnesium diboride because of their potential as a new superconductors. One of the remarkable results is the synthesis by a floating zone and a Ar arc melting methods the series of the new ternary layered silicides Sr(GaxSi1-x)2 Imai1 , Ca(Al0.5Si0.5)2 Imai2  and (Ca,Sr,Ba)(GaxSi1-x)2 7,8 with transition temperatures Tc ranging 3.3 - 7.7 K, except for Ba(AlxSi1-x)2. They have the AlB2-type structure in which Si and Al,Ga atoms are arranged in honeycomb sheets and alkaline-earth metals are intercalated between them. Furthemore, a series of the compounds (Ca,Sr,Ba)(AlxSi1-x)2 were synthesized by varying Al/Si (0.6$`<`$x$`<`$1.2) Lorenz  and the maximum Tc for these phases appears at the 1:1:1 composition.
Electrical resistivity and dc magnetization results5-8 revealed that these layered silicides are a type-II superconductors. The observed different Tc of these phases would be qualitatively attributed to the change in densities of states at EF, N(EF) Imai3 . The Seebeck coefficient measurements for (Ca,Sr,Ba)(AlxSi1-x)2 Lorenz  indicate that their carriers are predominantly electrons, in contrast to the holes in magnesium diboride1-4.
Recently, the first band structure study of the layered silicides Sr(GaxSi1-x)2, x = 0.375, 0.5, 0.625 and Ca(Al0.5Si0.5)2 has been performedShein . It has been shown that the SC properties may be due to the high density of (Ca,Sr)d-states at the Fermi level. In the present work we report the results of first-principles calculations for all known 1:1:1 ternary compounds M(A0.5Si0.5)2 (M=Ca, Sr, Ba; A=Al, Ga) and analyze the band structure parameters in association of SC properties for the isostructural and isoelectronic compounds: Ca(Al0.5Si0.5)2, Sr(Al0.5Si0.5)2, Ba(Al0.5Si0.5)2 and Ca(Ga0.5Si0.5)2, Sr(Ga0.5Si0.5)2, Ba(Ga0.5Si0.5)2. The band structures of the above silicides were calculated by the scalar relativistic full-potential LMTO methodSavrasov . The lattice parameters used are listed in the Table 1.
Energy bands, total and site projected $`\mathrm{}`$-decomposed densities of states (DOS, LDOS) of M(A0.5Si0.5)2 are presented in Figs. 1-7. Let us discuss the band structures of M(A0.5Si0.5)2 for example Ca(Al0.5Si0.5)2. The valence band (VB) for Ca(Al0.5Si0.5)2 includes four fully occupied bands and has a width of about 10 eV. The quasi-core s-like band is located in the interval from 10.0 to 7.8 eV below the Fermi level and separated by a gap ($``$ 1.45 eV) from the hybrid (Al,Si)sp-states which form four $`\sigma `$(2px,y) and two $`\pi `$(pz) bands, Fig. 1. The E(k) dependence for px,y and pz bands differs considerably. For 2px,y like bands the most pronounced dispersion of E(k) is observed along the direction kx,y ($`\mathrm{\Gamma }`$-K of the Brillouin zone (BZ)). These bands are of the quasi two dimensional (2D) type. They form a quasi-flat zone along kz ($`\mathrm{\Gamma }`$-A). The (Al,Si)px,y orbitals participate strong covalent $`\sigma `$-states to form 2D honeycomb network bonds of sp2 type with the s states. The (Al,Si)pz-like bands are responsible for weaker $`\pi `$(pz) interactions. These 3D-type bands have the maximum dispersion in the direction kz($`\mathrm{\Gamma }`$-A). The Cas,p,d-states are admixed to p-like bands. The $`\sigma `$(px,y) and $`\pi `$(pz) bands intersect at the $`\mathrm{\Gamma }`$ point of the BZ. It is important that the (Al,Si)p-bands are located below EF and do not contain hole states as well as those in non-superconducting AlB22-4, which is isoelectronic to the Ca(Al0.5Si0.5)2. The main contribution to the Ca(Al0.5Si0.5)2 DOS in the vicinity of the Fermi level is made by the Ca3d-states: their constribution in N(EF) is about 59 % compared with 9 % and 10% for Alp- and Sip-states, respectively.
Let us compare the band structures of Ca(Al0.5Si0.5)2, Sr(Al0.5Si0.5)2 and Ba(Al0.5Si0.5)2. The most obvious consequence of the alkaline-earth metal variation (Ca $``$ Sr $``$ Ba) is the decreasing of VB width from 10.0 (Ca(Al0.5Si0.5)2) to $``$ 9.1 eV (Ba(Al0.5Si0.5)2) caused by the increased cell volume. The location and dispersion of lowest d-bands depend from the alkaline-earth metals. As is seen from Fig.1, (Sr,Ba)d-states form the nearly flat bands in the direction L-H, close to EF. As a result for Sr(Al0.5Si0.5)2, Ba(Al0.5Si0.5)2 the sharp peaks in LDOS of (Sr,Ba)d-states hybridized with (Al,Si) -orbitals, appear which are separated by a pseudogap from the bonding p-bands (Figs. 2-4). The values of N(EF) increases more than twice going from Ca(Al0.5Si0.5)2 to Ba(Al0.5Si0.5)2. It is important to note that the increase in N(EF) is due to similtaneously growth in LDOS of valence states for all atoms in silicates , see Table 1.
The band structures of M(Al0.5Si0.5)2 and M(Ga0.5Si0.5)2 are similar, Fig.1. Their differences are revealed in an increase in the dispersion of $`\sigma `$-, $`\pi `$-bands in the A-L-H directions an decreasein band gap (at $``$ 1.0-0.9 eV) between s- and p-like bands for M(Ga0.5Si0.5)2 compared with M(Al0.5Si0.5)2. The VB width of M(Ga0.5Si0.5)2 increases by $``$ 1.3-1.0 eV. The change of the alkaline-earth metal in the sequence Ca $``$ Sr $``$ Ba causes the increase of the N(EF), the M d-states make the main contribution to near-Fermi DOS, Figs. 5-7, Table 1.
Thus, the band structure of the ternary AlB2-like silicides is quite different from SC MgB2. As compared by magnesium diboride, for M(A0.5Si0.5)2 were found (i) the filling of the bonding $`p_{x,y}`$-bands and the absence of $`\sigma `$ -holes, (ii) the increase of covalent interactions (due to p-d-hybridization) between graphene-like (Al,Si) or (Ga,Si) sheets and metal hexagonal layers and (iii) the principal change in the composition of N(EF), where the alkaline-earth metal d-states make the main contributions ( 55-60 %, Table 1).
According to the experimental data5-9: (i) in the silicides M(Al0.5Si0.5)2 the Tc decreases monotonically when the metal M is changed from Ca to Ba; (ii) in the silicides M(Ga0.5Si0.5)2 the Tc changes slightly (within range 3.9-5.1 ) with the maximum (5.1K) for Sr(Ga0.5Si0.5)2, Table 1.
In framework of BCS theory, the Tc can be estimated by the McMillan equation Tc $``$ $`<\omega >`$ expf($`\lambda `$), where $`<\omega >`$ is the averaged phonon frequency (inversely proportional to the atomic masses), $`\lambda `$ is the electron-phonon coupling constant ($`\lambda `$=N(EF)$`<I^2>`$/$`<M^2>`$,$`<I^2>`$ is the electron-phonon matrix element, the value of $`<M^2>`$ does not depend on mass and is determined by force constants).
The values of N(EF) (as the contributions in N(EF) from Md-,(Si, Al, Ga)p-states) obtained here showed that (i) in the silicides M(Al0.5Si0.5)2 and M(Ga0.5Si0.5)2 N(EF) increases monotonically when the alkaline-earth metal is changed from Ca to Ba (it is opposite to Tc trend5-9), (ii) N(EF) in the silicides M(Al0.5Si0.5)2 are higher than N(EF) in the silicides M(Ga0.5Si0.5)2 based on the same M, what also does not correlate with the observed critical temperatures. Thus, the direct relationship Tc $``$ N(EF), suggested in Imai2  for the ”strong stoichiometric” compositions of silicides M(A0.5Si0.5)2 are impossible.
It may be supposed that the main factor, determinimg the variation in Tc in a number of isostructural and isoelectronic compounds M(A0.5Si0.5)2, is the change of phonon frequencies depending from the atomic masses. Additionally, the shape of DOS (and the value of N(EF)) may be changed owing to disorder in the distribution of (Al,Ge)/Si atoms in honeycomb layers. As a result alkaline-earth metals will be in different trigonal- prizmatic positions, that may lead to the splitting of near-Fermi bands and to a decrease in N(EF). This effect will be more strong for Sr,Ba-containing silicides, where for ”ideal ordering” state the N(EF) is determined by narrow intensive peaks in DOS, Figs. 3,4,6,7. The possibilty of chemical disordering and the inhomogenity in the arc melted samples of silicides were noted by authors of Imai2 .
In summary, our calculations of the band structure of all known ternary silicides with the stoichiometry M(A0.5Si0.5)2 showed that the Fermi level is located in the region of a sharp DOS peak originated mainly from alkaline-earth metal d-states with some contributions of (Al,Ge,Si)p-orbitals. The Tc behavior for the isostructural and isoelectronic M(A0.5Si0.5)2 cannot be identified with the variation of N(EF), and probably connected with phonon-mode frequencies determined by atomic masses.
Acknowledgement.
This work was supported by the RFBR, grant 02-03-32971.


text:
# Dynamics of text generation with realistic Zipf distribution

## Abstract

We investigate the origin of Zipf’s law for words in written texts by means of a stochastic dynamical model for text generation. The model incorporates both features related to the general structure of languages and memory effects inherent to the production of long coherent messages in the communication process. It is shown that the multiplicative dynamics of our model leads to rank-frequency distributions in quantitative agreement with empirical data. Our results give support to the linguistic relevance of Zipf’s law in human language.

Natural languages are complex systems that have evolved as effective dynamical structures, capable of codifying and transmitting highly nontrivial information. The foremost example of the kind is the genetic code, which evolved as a very efficient way of coding instructions to replicate living things smith . Another example of a natural code is human language. Although it evolved in shorter time scales than the genetic code and was subject to a noisier environment, it also achieved its present complexity by the natural process of evolution nowak . In recent years we have witnessed a gradual extension of the ideas and methods of statistical physics onto a vast range of complex phenomena outside the traditional boundaries of physical science. When language is studied with tools originally developed within statistical mechanics, a very rich structure emerges at levels ranging from simple word counts to large scale organizational patterns that span many thousand of words vocabulary ; EN ; kanter ; mmdz ; mmpp . The use of statistics applied to human language records draws a picture of its macroscopic structure, at a level of description that may disclose traces of its evolutionary history and provide information on the complex processes behind its generation by the brain.

One the most generic statistical properties of written language is established by Zipf’s law, in the form of a mathematical relation between the rank of each word in a list of all the words used in a text ordered by decreasing frequency, and its frequency zipf1 ; zipf2 . Defining the normalized frequency of a word in a text as $`f(r)=n(r)/T`$, where $`n(r)`$ is the number of occurrences of the word at rank $`r`$ in the frequency-ordered list and $`T`$ is the total number of words in the text, Zipf’s law reads

$$f(r)r^z.$$
(1)
In the original formulation of this empirical law, the exponent $`z`$ was taken to be exactly equal to one. If, instead, the exponent is assumed as a parameter and fitted to empirical data it may take on values different from unity.

After more than fifty years since the discovery of Zipf’s law in human language, its ultimate origin remains elusive. However, the remarkable ubiquity of this law over diverse languages suggests that its origin must be looked for in very general probabilistic aspects associated with the process of language generation. Two models explaining Zipf’s law are worth mentioning, which represent two very different positions with respect to the linguistic significance of the law. The first one, a stochastic process put forward by H. Simon simon , simulates the dynamics of text generation as a multiplicative process that leads to Zipf’s law for asymptotically long texts. The second model is due to B. Mandelbrot mandel , who explained Zipf’s law as a static feature of the statistical structure of random symbolic sequences. While Simon’s model gives Zipf’s law a nontrivial linguistic significance, Mandelbrot’s explanation renders the law as a mere property of a random array of symbols. Let us also recall that, recently, it has been proposed that Zipf’s law could be the result of Markov processes underlying text-generation dynamics kanter . However, the analytical results were only tested against the text of the Bible, which is in fact a large collection of relatively short writings and whose statistics would therefore be subject to strong random fluctuations.

In this paper, we present a dynamical model that explains the empirical behavior of words frequencies as a consequence of two processes acting at different scales: a global memory effect driven by context, essentially related to the interplay between multiplicative and additive dynamics in word selection, and a local grammar-dependent effect associated with the appearance of word inflections. This model is able to reproduce realistic Zipf distributions and, additionally, has a linguistic interpretation. We show that the controversy between Simon’s and Mandelbrot’s views may be solved after explaining the particular deviations that empirical distributions exhibit with respect to the original form of Zipf’s law.

As advanced above, empirical rank-frequency distributions from real text sources are more complex than the original form of Zipf’s law, Eq. (1). The three uppermost curves in Fig. 1 show, from top to down, the rank-frequency distribution of words for three literary works written in English, Spanish and Latin, respectively. In all three cases the qualitative features of the distributions are similar, but some quantitative differences are worth mentioning. Above a short range corresponding to the most frequent words, where the behavior of $`f(r)`$ is rather irregular, the distributions decay as a power law in an interval of ranks spanning, for these texts, little less than two decades. Immediately following the power-law regime, the distributions fall slightly faster, as can be seen by comparing with the pure power laws shown in the graph as dot lines. Note that the values of the exponent $`z`$ measured in the power-law regime deviate appreciably from unity in the English and Latin texts. This phenomenology seems to be generic, since consistent quantitative results are found for other works in the same languages.

Simon’s model simon  intends to capture the essential features of actual text generation by specifying how words are added to the text, as follows. Suppose that at each step $`t`$ a new word is added to the text beginning with just one word at $`t=1`$ such that, at any step, the length of the text is $`t`$. With a fixed probability $`\alpha `$, a new word not present in the text is added at $`t+1`$ or, with the complementary probability, the new word is chosen among the previous $`t`$ words at random. Since the probability of repeating words that have already appeared is taken to be proportional to their number of previous occurrences, this process establishes a strong competition among different words. It can be shown that the long time rank-frequency distribution arising from Simon’s model is a power law of the form of Eq.(1) with $`z=1\alpha `$. We have included in Fig. 1 the results of a simulation of Simon’s model, with $`\alpha =0.01`$. Comparison with distributions obtained from real texts reveals qualitative agreement, though quantitative differences are apparent also. In particular, Simon’s model does not reproduce the faster decay at low frequencies, and is unable to explain power-law exponents larger than unity, as observed in English and Spanish texts. We show in the following that the model admits to be modified on the base of linguistically sensible assumptions, in such a way as to correct such differences.

In Simon’s model, new words are introduced at a constant rate $`\alpha `$, such that the vocabulary size at step $`t`$ is, on the average, $`V_t=\alpha t`$. Empirical data show however that the growth of vocabulary in real texts is typically sublinear vocabulary , and may be approximated by

$$V_t=\alpha t^\nu ,$$
(2)
with $`0<\nu <1`$. This generalized form of $`V_t`$ correspond to a rate of introduction of new words given by $`\alpha \nu t^{\nu 1}`$. This provides the first modification to Simon’s model, introducing a new parameter $`\nu `$. Instead of using a constant probability for the introduction of new words, we take a step–dependent probability $`\alpha _0t^{\nu 1}`$, with $`\alpha _0=\alpha \nu `$. We distinguish two main factors that affect the value of $`\nu `$. One factor depends on author and style and may explain small differences of vocabulary growth between works in the same language. However, a stronger effect on $`\nu `$ results from the degree of inflection of each language: highly inflected languages like Latin—where a single root produces, through declination and conjugation, many different words—require a higher value of $`\nu `$ than poorly inflected languages, such as English. In a text written in a highly inflected language, word forms will proliferate significantly faster than in languages with few inflected forms.

The original dynamics of Simon’s model implies that, when a word has to be taken from the text written so far, the probability that a word is repeated is proportional to $`n_i`$, the number of its previous occurrences. However, newly introduced words do not have a clearly defined influence on the context yet, and the probability that they are used again should be treated in a slightly different way. Our second modification to the model, thus, incorporates a word-dependent threshold $`\delta _i`$, in such a way that the probability of a new occurrence of word $`i`$ is proportional to $`\mathrm{max}\{n_i,\delta _i\}`$. The choice of this set of thresholds is to a great extent arbitrary. For simplicity we have chosen an exponential distribution, for which we just have to specify one parameter, namely the mean $`\delta `$. The dynamical effect of this new addition to the model is that words that have been recently introduced, for which $`n_i<\delta _i`$, have a slightly higher competition advantage and their reappearance in the text is favored. Since this parameter has no influence on words for which $`n_i>\delta _i`$, we expect that the power law region of the distribution, where $`n_i\delta _i`$, will not be affected by $`\delta _i`$.

In Fig. 2 we show three realizations of the model that fit quite well the empirical data already shown in Fig. 1. The slope of the distribution in the power-law region is accurately reproduced for the three literary works. Moreover, its faster decay in the low-frequency regime is also in close agreement with the actual linguistic data. Table 1 reports the value of the parameters used to fit the distributions.

We have performed the same analysis using other literary works, and obtained consistent results. In particular, the model reproduces Zipf distributions of texts written in languages with many inflexions, like Latin or Russian for instance, with higher values of $`\nu `$ than those required to fit Zipf distributions obtained from texts written in less inflective languages such as English or Spanish. In all cases, the faster decay exhibited by the rank-frequency distributions at high ranks was obtained by choosing the parameter $`\delta `$ between $`2`$ and $`4`$.

We can analytically explain the behavior of our modified Simon’s model starting from Simon’s equations for the mean number $`P_n(t)`$ of words with $`n`$ occurrences at step $`t`$. These are simon

$$P_n(t+1)=P_n(t)+\frac{1\alpha }{t}[(n1)P_{n1}(t)nP_n(t)]$$
(3)
for $`n>1`$, and

$$P_1(t+1)=P_1(t)+\alpha \frac{1\alpha }{t}P_1(t).$$
(4)
Replacing $`n`$ and $`t`$ by continuous variables, $`ny`$ and $`tt`$, and $`P_n(t)P(y,t)`$, Eq. (3) can be approximated by

$$_tP+\frac{1\alpha }{t}_y(yP)=0,$$
(5)
while for $`P(1,t)P_1(t)`$ we have

$$\dot{P}_1=\alpha \frac{1\alpha }{t}P_1.$$
(6)
Consider first the situation where the rate at which new words are added depends on $`t`$ as $`\alpha =\alpha _0t^{\nu 1}`$ ($`0<\nu <1`$), describing a vocabulary that grows less than linearly, $`Vt^\nu `$. Equations (5) and (6) can be solved assuming that $`\alpha 1`$ for all $`t`$. In such limit, in fact, the general solution to Eq. (5) is given by

$$P(y,t)=\frac{1}{y}\mathrm{\Pi }[yt^1],$$
(7)
where $`\mathrm{\Pi }(x)`$ is an arbitrary function. For the words that just appeared once in the text, we have

$$P_1(t)=At^1+\frac{\alpha _0}{\nu +1}t^\nu ,$$
(8)
with $`A`$ an arbitrary constant. The second term dominates the large-$`t`$ regime. Focusing on this regime and comparing with Eq. (7), we find $`\mathrm{\Pi }(x)=\alpha _0x^\nu /(\nu +1)`$ and, thus,

$$P(y,t)=\frac{\alpha _0}{\nu +1}t^\nu y^{1\nu }.$$
(9)
Taking into account that $`P(y,t)`$ and $`n(r)`$ are related according to $`r=_n^{\mathrm{}}P𝑑y`$, the Zipf exponent resulting from Eq. (9) is $`z=1/\nu >1`$. We therefore conclude that sublinear vocabulary growth, associated with a poorly inflective language, is able to explain a relatively large value of $`z`$, beyond the predictions of the original Simon’s model.

The analytical treatment of our second modification to the model requires a preliminary discussion. In fact, the thresholds $`\delta _i`$ cannot be straightforwardly incorporated to Simon’s equations. We can however approximate the dynamical features associated with them by introducing a few simplifications to the process. Let us first assume that all the thresholds are set to a value equal to their mean, namely $`\delta `$. Consider now the events in which a word must be chosen among those written so far. There are two possibilities: with probability $`\gamma `$ the word is chosen among those for which $`n_i<\delta `$, with uniform probability, or with probability $`1\gamma `$ the word is chosen among those for which $`n_i>\delta `$, with probability proportional to $`n_i`$. A kind of mean field approximation of these dynamical rules would imply that with probability $`\gamma `$ the new word is chosen with uniform probability among all the previous words regardless of $`n_i`$, and with the complementary probability the word is chosen with probability proportional to $`n_i`$.

In the case of constant $`\alpha `$, we introduce this additive contribution to the evolution of $`P_n(t)`$ in the following way:

$`P_n(t+1)`$ $`=`$ $`P_n(t)`$ (10)
$`+`$ $`{\displaystyle \frac{(1\alpha )(1\gamma )}{t}}[(n1)P_{n1}(t)nP_n(t)]`$
$`+`$ $`{\displaystyle \frac{(1\alpha )\gamma }{t}}[P_{n1}(t)P_n(t)].`$
The evolution of $`P_1`$ is still given by Eq. (4). Particular solutions to the continuous version of Eq. (10), indexed by the parameter $`\lambda `$, read

$$P(y,t)=a_\lambda t^\lambda [(1\gamma )y+\gamma ]^{1\lambda /(1\alpha )(1\gamma )},$$
(11)
where $`a_\lambda `$ is an arbitrary constant.

In the large-$`t`$ regime and within the assumption $`\alpha 1`$ we can put together the effect of $`t`$-dependent $`\alpha `$, $`\alpha (t)=\alpha _0t^{\nu 1}`$, and of the additive process. In fact, the large-$`t`$ dominant contribution in Eq. (8) is compatible with solution (11) for $`\lambda =\nu `$. We obtain

$$P(y,t)=\frac{\alpha _0}{1+\nu }t^\nu [(1\gamma )y+\gamma ]^{1\nu /(1\gamma )}.$$
(12)
Zipf’s law results

$$n=\frac{1}{1\gamma }[(r/r_0)^{(1\gamma )/\nu }\gamma ],$$
(13)
with $`r_0(t)=\alpha _0t^\nu /(1+\nu )`$. The distribution shows a cutoff at $`r=gr_0`$, with $`g=\gamma ^{\nu /(1\gamma )}`$, which explains its faster decay for large ranks.

In summary, we have investigated the origin of Zipf’s law, which stands for the most basic statistical pattern found in written human language. Our results confirm that the rank-frequency distribution of words is mainly the consequence of multiplicative processes underlying the language generation process. Moreover, we have been able to associate the finer details of empirical distributions with two key subprocesses that participate in text production. First, a sublinear vocabulary growth law that integrates the effect of the inflective structure of language. Second, context-dependent dynamics and activation thresholds related to the dynamical effect of newly introduced words. Our main conclusion is that linguistically sensible modifications of Simon’s model eliminate the slight deviations between the results of the original model and actual Zipf distributions. This gives additional support to the interpretation of Zipf’s law as a linguistically significant feature of written texts.