text:
# Pattern frequency sequences and internal zeros

## 1 Introduction

Let $`q=q_1q_2\mathrm{}q_l`$ be a permutation in the symmetric group $`S_l`$. We call $`l`$ the length of $`q`$. We say that the permutation $`p=p_1p_2\mathrm{}p_nS_n`$ contains a $`q`$-pattern if and only if there is a subsequence $`p_{i_1}p_{i_2}\mathrm{}p_{i_l}`$ of $`p`$ whose elements are in the same relative order as those in $`q`$, i.e.,

$$p_{i_j}<p_{i_k}\text{ if and only if }q_j<q_k$$

whenever $`1j,kl`$. For example, 41523 contains exactly two 132-patterns, namely 152 and 153. We let

$$c_q(p)=\text{ the number of copies of }q\text{ in }p,$$

so that $`c_{132}(41523)=2`$. Permutations containing a given number of $`q`$-patterns have been extensively studied recently \[1–11\].

In this paper, we consider permutations with a given number of $`q`$-patterns from a new angle. Let

$$S_{n,q}(c)=\text{ the number of }n\text{-permutations with exactly }c\text{ patterns of type }q.$$

For $`n`$ and $`q`$ fixed, the sequence $`(S_{n,q}(c))_{c0}`$ is called the frequency sequence of the pattern $`q`$ for $`n`$. Clearly this sequence consists entirely of zeros if $`n`$ is less than the length of $`q`$ and so we call these sequences trivial and all others nontrivial. We also say that an $`n`$-permutation $`p`$ is $`q`$-optimal if there is no $`n`$-permutation with more copies of $`q`$ than $`p`$, and let

$$M_{n,q}=c_q(p)\text{ for an optimal }p.$$

The only $`q`$ for which the frequency sequence is well understood is $`q=21`$ (or equivalently $`q=12`$). Occurences of this pattern are called inversions. It is well known  that for all $`n`$, the frequency sequence of inversions is log-concave, and so is unimodal and has no internal zeros.

When $`q`$ is has length greater than 2, numerical evidence suggests that the frequency sequence of $`q`$ will no longer be unimodal, let alone log-concave. In fact, internal zeros seem to be present in most frequency sequences. An integer $`c`$ is called an internal zero of the sequence $`(S_{n,q}(c))_{c0}`$ if for some $`c`$ we have $`S_{n,q}(c)=0`$, but there exist $`c_1`$ and $`c_2`$ with $`c_1<c<c_2`$ and $`S_{n,q}(c_1)`$, $`S_{n,q}(c_2)0`$.

In the rest of this paper we study the frequency sequences of the monotone pattern $`q=12\mathrm{}l`$ and the pattern $`q=1(l+1)l\mathrm{}2`$. We will show that in the first case, when $`l3`$ (the case $`l=2`$ has already been mentioned) the nontrivial sequences always have internal zeros. For $`1(l+1)l\mathrm{}2`$-patterns there are infinitely many $`n`$ where the sequence has internal zeros. For the $`132`$-pattern there are also infinitely many $`n`$ where the sequence has no internal zeros. And internal zeros can only appear in positions $`M_{n,132}1`$ or $`M_{n,132}2`$.

## 2 The monotone case

We will now consider the sequence $`(S_{n,q}(c))_{c0}`$ where $`q=12\mathrm{}l`$. For later reference, we single out the known case when $`l=2`$ discussed in the introduction.

###### Proposition 2.1

The sequence $`(S_{n,12}(c))_{c0}`$ has no internal zeros (and is, in fact, log concave). The unique optimal permutation is $`p=12\mathrm{}n`$ with

$$M_{n,12}=\left(\genfrac{}{}{0pt}{}{n}{2}\right)\mathrm{}$$

It turns out that this is the only monotone pattern (aside from 21) whose sequence has no internal zeros. To prove this result, define an inversion (respectively, noninversion) in $`p=p_1p_2\mathrm{}p_n`$ to be a pair $`(p_i,p_j)`$ such that $`i<j`$ and $`p_i>p_j`$ (respectively, $`p_i<p_j`$).

###### Theorem 2.2

Let $`q=12\mathrm{}l`$ where $`l3`$. Then in $`S_n`$, the unique optimal permutation is $`p=12\mathrm{}n`$ and

$$M_{n,12\mathrm{}l}=\left(\genfrac{}{}{0pt}{}{n}{l}\right).$$

The set of permutations having the next greatest number of copies of $`q`$ are those obtained from $`p`$ by an adjacent transposition and this number of copies is

$$\left(\genfrac{}{}{0pt}{}{n1}{l}\right)+\left(\genfrac{}{}{0pt}{}{n2}{l1}\right).$$
(1)
Proof: Consider any $`rS_n`$ different from $`p`$. Then $`r`$ has an inversion $`(r_i,r_j)`$. So the number of copies of $`q`$ in $`r`$ is the number not containing $`r_i`$ plus the number which do contain $`r_i`$. The permutations in the latter case can not contain $`r_j`$. So (1) gives an upper bound for the number of copies of $`q`$ which is strict unless $`r`$ has exactly one inversion. The theorem follows. $`\mathrm{}`$

###### Corollary 2.3

Let $`q=12\mathrm{}l`$ where $`l3`$. Then for $`nl`$ the sequence $`(S_{n,12\mathrm{}l}(c))_{c0}`$ has internal zeros.

Proof: From the previous theorem, we see that the number of zeros directly before $`S_{n,q}(M_{n,q})=1`$ is

$$\left(\genfrac{}{}{0pt}{}{n}{l}\right)\left(\genfrac{}{}{0pt}{}{n1}{l}\right)\left(\genfrac{}{}{0pt}{}{n2}{l1}\right)=\left(\genfrac{}{}{0pt}{}{n2}{l2}\right)n21$$

since $`nl3`$. $`\mathrm{}`$

For use in the 132 case, we record the following observation.

###### Lemma 2.4

For any integer $`c`$ with $`0c\left(\genfrac{}{}{0pt}{}{n}{2}\right)`$ there is a permutation $`pS_n`$ having $`c`$ copies of the pattern $`21`$ and no copies of $`132`$.

Proof: We induct on $`n`$. The result is clearly true if $`n2`$. Assuming it is true for $`n1`$, first consider $`c\left(\genfrac{}{}{0pt}{}{n1}{2}\right)`$ and let $`pS_{n1}`$ satisfy the lemma. Then the concatenation $`pnS_n`$ works for such $`c`$. On the other hand, if $`\left(\genfrac{}{}{0pt}{}{n1}{2}\right)<c\left(\genfrac{}{}{0pt}{}{n}{2}\right)`$ then consider $`c^{}=c(n1)\left(\genfrac{}{}{0pt}{}{n1}{2}\right)`$. Pick $`pS_{n1}`$ with $`c^{}`$ copies of $`21`$ and none of $`132`$. Then $`npS_n`$ is the desired permutation. $`\mathrm{}`$

## 3 The case $`q=1(l+1)l\mathrm{}2`$ and layered patterns

The rest of this paper is devoted to the study of the frequency sequences of the patterns $`1(l+1)l\mathrm{}2`$ for $`l2`$. To simplify notation, and write $`F_{n,1(l+1)l\mathrm{}2}`$ for the sequence $`(S_{n,1(l+1)l\mathrm{}2}(c))_{c0}`$. One crucial property of these patterns is that they are layered. This section gives an overview of some important results on layered patterns.

A pattern is layered if it is the concatenation of subwords (the layers) where the entries decrease within each layer, and increase between the layers. For example, $`\mathrm{3\hspace{0.25em}2\hspace{0.25em}1\hspace{0.25em}5\hspace{0.25em}4\hspace{0.25em}8\hspace{0.25em}7\hspace{0.25em}6\hspace{0.25em}9}`$ is a layered pattern with layers $`\mathrm{3\hspace{0.25em}2\hspace{0.25em}1},\mathrm{\hspace{0.25em}5\hspace{0.25em}4},\mathrm{\hspace{0.25em}8\hspace{0.25em}7\hspace{0.25em}6}`$, and 9. Layered patterns are examined in Stromquist’s work  and in Price’s thesis . The most important result for our current purposes is the following theorem.

###### Theorem 3.1 ()

Let $`q`$ be a layered pattern. Then the set of $`q`$-optimal $`n`$-permutations contains at least one layered permutation.

Layered $`1(l+1)l\mathrm{}2`$-optimal permutations have a simple recursive structure. This comes from the fact, which we will use many times, that to form a $`1(l+1)l\mathrm{}2`$ pattern in a layered permutation one must take a single element from some layer and $`l`$ elements from a subsequent layer

###### Proposition 3.2

Let $`p`$ be a layered $`1(l+1)l\mathrm{}2`$-optimal $`n`$-permutation whose last layer is of length $`m`$. Then the leftmost $`k=nm`$ elements of $`p`$ form a $`1(l+1)l\mathrm{}2`$-optimal $`k`$-permutation.

Proof: Let $`D_k`$ be the number of $`1(l+1)l\mathrm{}2`$-copies of $`p`$ that are disjoint from the last layer. The number of $`1(l+1)l\mathrm{}2`$-copies of $`p`$ is clearly $`k\left(\genfrac{}{}{0pt}{}{m}{l}\right)+D_k.`$ So once $`k`$ is chosen, $`p`$ will have the maximum number of copies only if $`D_k`$ is maximal. $`\mathrm{}`$

We point out that the proof of this proposition uses the fact that $`1(l+1)l\mathrm{}2`$ has only two layers, the first of which is a singleton. Let $`M_n=M_{n,1(l+1)l\mathrm{}2}`$. Then the previous proposition implies that

$$M_n=\underset{1k<n}{\mathrm{max}}\left(M_k+k\left(\genfrac{}{}{0pt}{}{m}{l}\right)\right).$$
(2)
The integer $`k`$ for which the right hand side attains its maximum will play a crucial role throughout this paper. Therefore, we introduce specific notation for it.

###### Definition 3.3

For any positive integer $`n`$, let $`k_n=k_{n1(l+1)l\mathrm{}2}`$ be the positive integer for which $`M_n=\mathrm{max}_k(M_k+k\left(\genfrac{}{}{0pt}{}{m}{l}\right))`$ is maximal. If there are several integers with this property, then let $`k_n`$ be the largest among them.

In other words, $`k_n`$ is the largest possible length of the remaining permutation after removing the last layer of a $`1(l+1)l\mathrm{}2`$-optimal $`n`$-permutation $`p`$. When there is no danger of confusion, we will only write $`k`$ to simplify notation. We will also always use $`m=nk`$ to denote the length of the last layer of $`p`$.

## 4  Construction of Permutations with a given number of copies of $`q=132`$

We will first show that if $`q=132`$ then there are infinitely many integers $`n`$ such that $`F_n`$ does not have internal zeros. We will call such an integer, or its corresponding sequence, NIZ (no internal zero), and otherwise IZ. Our strategy is recursive: We will show that if $`k_n`$ is NIZ, then so is $`n`$. As $`k_n<n`$, this will lead to an infinite sequence of NIZ integers. There is a problem, however. In order for this strategy to work, we must ensure that given $`k`$, then there is an $`n`$ such that $`k=k_n`$. This is the purpose of the following theorem which is in fact true for the general pattern $`q=1(l+1)l\mathrm{}2`$.

###### Theorem 4.1

For $`k_n=k_{n,1(l+1)l\mathrm{}2}`$, the sequence $`(k_n)_{n1}`$ diverges to infinity and satisfies

$$k_nk_{n+1}k_n+1$$

for all $`nl+1`$. So, since $`k_{l+1}=1`$, for all positive integers $`k`$ there is a positive integer $`n`$ so that $`k_n=k`$.

The next section is devoted to a proof of this theorem. We suggest that the reader assume the result now and continue with this section to preserve continuity. We now consider the case $`q=132`$ which behaves differently from $`q=1(l+1)l\mathrm{}2`$ for $`l3`$. This is essentially due to the difference between the patterns $`q=12`$ and $`q=12\mathrm{}l`$ for $`l3`$ as seen in Proposition 2.1 and Theorem 2.2. First we note the useful fact that

$$M_{k,132}\left(\genfrac{}{}{0pt}{}{k1}{2}\right)$$
(3)
which follows by considering the permutation $`1k(k1)(k2)\mathrm{}32`$.

###### Theorem 4.2

For $`q=132`$ There are infinitely many NIZ integers.

Proof: It is easy to verify that $`n=4`$ is NIZ. So, by Theorem 4.1, it suffices to show that if $`k_n4`$ is NIZ then so is $`n`$. To simplify notation in the two proofs which follow, we will write $`k`$ for $`k_{n,132}`$, $`M_n`$ for $`M_{n,132}`$, and so forth.

Now given $`c`$ with $`0cM_n=M_k+k\left(\genfrac{}{}{0pt}{}{m}{2}\right)`$ we will construct a permutation $`pS_n`$ having $`c`$ copies of 132. Because of (3) and $`k4`$ we have $`M_kk1`$. So it is possible to write $`c`$ (not necessarily uniquely) as $`c=ks+t`$ with $`0s\left(\genfrac{}{}{0pt}{}{m}{2}\right)`$ and $`0tM_k`$. Since $`k`$ is NIZ, there is a permutation $`p^{}S_k`$ with $`c_{132}(p^{})=t`$. Also, by Lemma 2.4, there is a permutation in $`S_m`$ with no copies of 132 and $`s`$ copies of 21. Let $`p^{\prime \prime }`$ be the result of adding $`k`$ to every element of that permutation. Then, by construction, $`p=p^{}p^{\prime \prime }S_n`$ and $`c_{132}(p)=ks+t=c`$ as desired. $`\mathrm{}`$

One can modify the proof of the previous theorem to locate precisely where the internal zeros could be for an IZ sequence. We will need the fact (established by computer) that for $`n12`$ the only IZ integers were 6, 8, and 9, and that they all satisfied the following result.

###### Theorem 4.3

For any positive integer $`n`$, the sequence $`F_{n,132}`$ does not have internal zeros, except possibly for $`c=M_{n,132}1`$ or $`c=M_{n,132}2`$, but not both.

Proof: We prove this theorem by induction on $`n`$. As previously remarked, it is true if $`n12`$. Now suppose we know the statement for all integers smaller than $`n`$, and prove it for $`n`$. If $`n`$ is NIZ, then we are done.

If $`n`$ is IZ then, by the proof of Theorem 4.2, $`k=k_n`$ is IZ. So $`k6`$ and we have $`M_kk+2`$ by (3). Now take $`c`$ with $`0cM_n3`$ so that we can write $`c=ks+t`$ with $`0s\left(\genfrac{}{}{0pt}{}{m}{2}\right)`$ and $`0tM_k3`$. Since the portion of $`F_k`$ up to $`S_k(M_k3)`$ has no internal zeros by induction, we can use the same technique as in the previous theorem to construct a permutation $`p`$ with $`c_{132}(p)=c`$ for $`c`$ in the given range. Furthermore, this construction shows that if $`S_k(M_ki)0`$ for $`i=1`$ or $`2`$ then $`S_n(M_ni)0`$. This completes the proof. $`\mathrm{}`$

## 5 The sequence $`(k_n)_{nl+1}`$ for $`q=1(l+1)l\mathrm{}2`$

For the rest of this paper, all invariants will refer to the pattern $`q=1(l+1)l\mathrm{}2`$ unless explicitly stated otherwise.

In order to prove Theorem 4.1, we first need a lemma about the lengths of various parts of a $`1(l+1)l\mathrm{}2`$-optimal permutation $`p`$. In all that follows, we use the notation

$`b`$ $`=`$ the length of the penultimate layer of $`p`$
$`a`$ $`=`$ the length of the permutation gotten by removing the last two layers of $`p`$
$`=`$ $`nmb`$
$`=`$ $`kb.`$
Also observe that the sequence $`(M_n)_{nl+1}`$ is strictly increasing. This is because when $`nl+1`$, any layered $`1(l+1)l\mathrm{}2`$-optimal permutation $`pS_n`$ contains at least one copy of $`1(l+1)l\mathrm{}2`$. So inserting $`n+1`$ in front of any layer contributing to the $`(l+1)l\mathrm{}2`$ portion of some copy results in a permutation with more $`1(l+1)l\mathrm{}2`$-patterns than $`p`$. It follows from (2) that $`ml`$ for $`nl+1`$, a fact that will be useful in proving the following result.

###### Lemma 5.1

Let $`q=1(l+1)l\mathrm{}2`$, $`k=k_{n,q}`$, and $`nl+1`$. Then we have the following inequalities

1. $`bm`$,
2. $`a(ml+1)/l`$,
3. $`k<n/l`$, so in particular $`k<m`$,
4. $`ml(n+1)/(l+1)`$.

Proof: The basic idea behind all four of the inequalities is as follows. Let $`p^{}`$ be the permutation obtained from our $`1(l+1)l\mathrm{}2`$\- optimal permutation $`p`$ by replacing its last two layers with a last layer of length $`m^{}`$ and a next-to-last layer of length $`b^{}`$. Then in passing from $`p`$ to $`p^{}`$ we lose some $`1(l+1)l\mathrm{}2`$-patterns and gain some. Since $`p`$ was optimal, the number lost must be at least as large as the number gained. And this inequality can be manipulated to give the one desired.

For the details, the following chart gives the relevant information to describe $`p^{}`$ for each of the four inequalities. In the second case, the last two layers of $`p`$ are combined into one, so the value of $`b^{}`$ is irrelevant.

$$\begin{array}{ccc}m^{}& b^{}& \text{number of gained }1(l+1)l\mathrm{}2\text{-patterns }\text{ number of lost }1(l+1)l\mathrm{}2\text{-patterns}\\ & & \\ & & \\ b& m& m\left(\genfrac{}{}{0pt}{}{b}{l}\right)b\left(\genfrac{}{}{0pt}{}{m}{l}\right)\text{}\\ & & \\ b+m& \text{}& a\left(\left(\genfrac{}{}{0pt}{}{m+b}{l}\right)\left(\genfrac{}{}{0pt}{}{m}{l}\right)\left(\genfrac{}{}{0pt}{}{b}{l}\right)\right)b\left(\genfrac{}{}{0pt}{}{m}{l}\right)\text{}\\ & & \\ m+1& b1& (a+b1)\left(\genfrac{}{}{0pt}{}{m}{l1}\right)a\left(\genfrac{}{}{0pt}{}{b1}{l1}\right)+\left(\genfrac{}{}{0pt}{}{m}{l}\right)\text{}\\ & & \\ m1& b+1& a\left(\genfrac{}{}{0pt}{}{b}{l1}\right)+\left(\genfrac{}{}{0pt}{}{m1}{l}\right)(a+b)\left(\genfrac{}{}{0pt}{}{m1}{l1}\right)\text{}\end{array}$$

Now (i) follows easily by cancelling $`bm/l!`$ from the inequality in the first row of the table.

From the second line of the table, we have

$$ab\left(\genfrac{}{}{0pt}{}{m}{l1}\right)a\underset{i=1}{\overset{l1}{}}\left(\genfrac{}{}{0pt}{}{b}{i}\right)\left(\genfrac{}{}{0pt}{}{m}{li}\right)=a\left(\left(\genfrac{}{}{0pt}{}{m+b}{l}\right)\left(\genfrac{}{}{0pt}{}{m}{l}\right)\left(\genfrac{}{}{0pt}{}{b}{l}\right)\right)b\left(\genfrac{}{}{0pt}{}{m}{l}\right),$$

and cancelling $`b\left(\genfrac{}{}{0pt}{}{m}{l1}\right)`$, which is not zero becase $`ml`$, gives us (ii).

To prove (iii) we induct on $`n`$. If $`n=l+1`$, then we must have $`p=1(l+1)l\mathrm{}2`$, so $`k=1<(l+2)/l=(n+1)/l`$. Now we assume $`n>l+1`$.

If $`k<l+1`$, then the leftmost $`k`$ elements of $`p`$ contain no copies of $`1(l+1)l\mathrm{}2`$, so we may replace them with any $`k`$-permutation and still have $`p`$ optimal. Therefore we may pick $`b=1`$ and $`a=k1`$, and thus the second row of the table shows

$$\frac{l(k1)}{ml+1}\left(\genfrac{}{}{0pt}{}{m}{l}\right)=(k1)\left(\genfrac{}{}{0pt}{}{m}{l1}\right)=(k1)\left(\left(\genfrac{}{}{0pt}{}{m+1}{l}\right)\left(\genfrac{}{}{0pt}{}{m}{l}\right)\left(\genfrac{}{}{0pt}{}{1}{l}\right)\right)\left(\genfrac{}{}{0pt}{}{m}{l}\right),$$

so $`k(m+1)/l(n+1)/l`$, as desired.

If $`kl+1`$, recall that from Proposition 3.2, the leftmost $`k=a+b`$ elements of $`p`$ form a $`1(l+1)l\mathrm{}2`$-optimal permutation, so we may, without loss, choose $`a`$ maximal and thus assume that $`a=k_k`$.

From the third line of the chart, we have

$$\frac{l(k1)}{ml+1}\left(\genfrac{}{}{0pt}{}{m}{l}\right)=(a+b1)\left(\genfrac{}{}{0pt}{}{m}{l1}\right)a\left(\genfrac{}{}{0pt}{}{b1}{l1}\right)+\left(\genfrac{}{}{0pt}{}{m}{l}\right).$$

Using (i) we get that $`\left(\genfrac{}{}{0pt}{}{b1}{l1}\right)\left(\genfrac{}{}{0pt}{}{m1}{l1}\right)=\frac{l}{m}\left(\genfrac{}{}{0pt}{}{m}{l}\right)`$. Substituting this in the previous equation, cancelling $`\left(\genfrac{}{}{0pt}{}{m}{l}\right)`$, and solving for $`k`$ gives

$$k\frac{m+1}{l}+\frac{a(ml+1)}{m}$$

Since $`kl+1`$, we have by induction that $`a=k_k<k/l`$. Substituting and solving for $`k`$ again and then cancelling $`m+1`$, we get $`k<\frac{m}{l1}`$. A final substitution of $`m=nk`$ results in (iii).

For (iv), notice that the last row of the table gives

$$\left(\genfrac{}{}{0pt}{}{m1}{l}\right)a\left(\genfrac{}{}{0pt}{}{b}{l1}\right)+\left(\genfrac{}{}{0pt}{}{m1}{l}\right)(a+b)\left(\genfrac{}{}{0pt}{}{m1}{l1}\right)=(nm)\left(\genfrac{}{}{0pt}{}{m1}{l1}\right).$$
(4)
so cancelling $`\left(\genfrac{}{}{0pt}{}{m1}{l1}\right)`$ gives $`nm(ml)/l`$, which can be converted to the desired inequality. $`\mathrm{}`$

We now turn to the proof of Theorem 4.1. First note that, by Lemma 5.1 (iv), we have

$$k=nm\frac{nl}{l+1}.$$
(5)
So $`(k_n)_{n1}`$ clearly diverges to infinity. For our next step, we prove that $`(k_n)_{n1}`$ is monotonically weakly increasing. Let $`p_{n,i}`$ denote an $`n`$-permutation whose last layer is of length $`ni`$, and whose leftmost $`i`$ elements form a $`1(l+1)l\mathrm{}2`$-optimal $`i`$-permutation, and let $`c_{n,i}=c_{1(l+1)l\mathrm{}2}(p_{n,i})`$. Clearly

$$c_{n,i}=M_i+i\left(\genfrac{}{}{0pt}{}{ni}{l}\right).$$

###### Proposition 5.2

For $`q=1(l+1)l\mathrm{}2`$ and all integers $`nl+1`$, we have $`k_nk_{n+1}`$.

Proof: It suffices to show that $`c_{n+1,k}>c_{n+1,i}`$ for all $`i<k`$. This is equivalent to showing that

$$M_k+k\left(\genfrac{}{}{0pt}{}{nk+1}{l}\right)>M_i+i\left(\genfrac{}{}{0pt}{}{ni+1}{l}\right).$$
(6)
However, by definition of $`k`$, we know that for all $`i<k`$,

$$M_k+k\left(\genfrac{}{}{0pt}{}{nk}{l}\right)M_i+i\left(\genfrac{}{}{0pt}{}{ni}{l}\right).$$
(7)
Subtracting (7) from (6), we are reduced to proving $`k\left(\genfrac{}{}{0pt}{}{nk}{l1}\right)>i\left(\genfrac{}{}{0pt}{}{ni}{l1}\right)`$. We will induct on $`ki`$. If $`ki=1`$, then we would like to show that

$$\frac{k(nkl+2)}{nk+1}\left(\genfrac{}{}{0pt}{}{nk+1}{l1}\right)=k\left(\genfrac{}{}{0pt}{}{nk}{l1}\right)>(k1)\left(\genfrac{}{}{0pt}{}{nk+1}{l1}\right),$$

so it suffices to show that $`k<(n+1)/l`$, which follows from Lemma 5.1 (iii).

For $`ki>1`$ we have, by induction, that $`k\left(\genfrac{}{}{0pt}{}{nk}{l1}\right)>(i+1)\left(\genfrac{}{}{0pt}{}{ni1}{l1}\right)`$, so it suffices to show that

$$\frac{(i+1)(nil+1)}{(ni)}\left(\genfrac{}{}{0pt}{}{ni}{l1}\right)=(i+1)\left(\genfrac{}{}{0pt}{}{ni1}{l1}\right)>i\left(\genfrac{}{}{0pt}{}{ni}{l1}\right),$$

which simplifies to $`(i+1)<(n+1)/l`$, and this is is true because $`i+1<k`$. $`\mathrm{}`$

The proof of the upper bound on $`k_{n+1}`$ is a bit more involved but follows the same general lines as the previous demonstration. Note that this will finish the proof of Theorem 4.1.

###### Lemma 5.3

For $`q=1(l+1)l\mathrm{}2`$ and all integers $`nl+1`$, we have $`k_nk_{n+1}k_n+1`$.

Proof: Induct on $`n`$. The lemma is true for $`n=l+1`$ since $`k_{l+1}=k_{l+2}=1`$. Suppose the lemma is true for integers smaller than or equal to $`n`$, and prove it for $`n+1`$. For simplicity, let $`k=k_n`$, $`m=nk`$, and $`c_i=c_{n+1,i}`$. Since we have already proved the lower bound, it suffices to show that

$$c_ic_{i+1}\text{ for }k+1i<\frac{n+1}{l}\text{ with strict inequality for }i=k+1.$$
(8)
Note that we do not have to consider $`i(n+1)/l`$ because of Lemma 5.1 (iii).

We prove (8) by induction on $`i`$. For the base case, $`i=k+1`$, we wish to show

$$M_{k+1}+(k+1)\left(\genfrac{}{}{0pt}{}{m}{l}\right)>M_{k+2}+(k+2)\left(\genfrac{}{}{0pt}{}{m1}{l}\right).$$
(9)
But since $`p_{n,k}`$ is optimal by assumption, we have

$$M_k+k\left(\genfrac{}{}{0pt}{}{m}{l}\right)>M_{k+1}+(k+1)\left(\genfrac{}{}{0pt}{}{m1}{l}\right).$$
(10)
Subtracting (10) from (9) and rearranging terms, it suffices to prove

$$\left(\genfrac{}{}{0pt}{}{m1}{l1}\right)(M_{k+2}M_{k+1})(M_{k+1}M_k).$$
(11)
First, if $`k<l+1`$, then (11) is easy to verify using Lemma 5.1 (iii) and the values $`M_{l+2}=l+1`$, $`M_{l+1}=1`$, and $`M_k=0`$ for $`kl`$. Therefore we may assume that $`kl+1`$. Let $`p^{}S_k`$, $`p^{\prime \prime }S_{k+1}`$, and $`p^{\prime \prime \prime }S_{k+2}`$ be layered $`1(l+1)l\mathrm{}2`$-optimal permutations having last layer lengths $`m^{}`$, $`m^{\prime \prime }`$, and $`m^{\prime \prime \prime }`$, respectively, as short as possible. Also let $`k^{}=km^{}`$, $`k^{\prime \prime }=k+1m^{\prime \prime }`$, and $`k^{\prime \prime \prime }=k+2m^{\prime \prime \prime }`$. We would like to be able to assume the lemma holds for these permutations, and thus we would like to have $`k+2n`$. But by Lemma 5.1 (iii) we have $`k+2<n/2+2n`$ if $`n4`$. Since $`nl+1`$ this holds for $`l3`$ and the case $`l=2,n=3`$ is easy to check directly. Therefore we may assume that $`p^{}`$, $`p^{\prime \prime }`$, and $`p^{\prime \prime \prime }`$ all satisfy the lemma.

If $`m^{\prime \prime }=m^{}+1`$ then let $`x`$ be the largest element in the last layer of $`p^{\prime \prime }`$ (namely $`x=k+1`$). Otherwise, $`m^{\prime \prime }=m^{}`$ and removing the last layer of both $`p^{}`$ and $`p^{\prime \prime }`$ leaves permutations in $`S_{km^{}}`$ and $`S_{km^{}+1}`$, respectively. So we can iterate this process until we find the single layer where $`p^{}`$ and $`p^{\prime \prime }`$ have different lengths (those lengths must differ by 1) and let $`x`$ be the largest element in that layer of $`p^{\prime \prime }`$. Similarly we can find the element $`y`$ which is largest in the unique layer were $`p^{\prime \prime }`$ and $`p^{\prime \prime \prime }`$ have different lengths.

Now let

$`r`$ $`=`$ the number of $`1(l+1)l\mathrm{}2`$-patterns in $`p^{\prime \prime \prime }`$ containing neither $`x`$ nor $`y`$,
$`s`$ $`=`$ the number of $`1(l+1)l\mathrm{}2`$-patterns in $`p^{\prime \prime \prime }`$ containing $`x`$ but not $`y`$,
$`t`$ $`=`$ the number of $`1(l+1)l\mathrm{}2`$-patterns in $`p^{\prime \prime \prime }`$ containing $`y`$ but not $`x`$, and
$`u`$ $`=`$ the number of $`1(l+1)l\mathrm{}2`$-patterns in $`p^{\prime \prime \prime }`$ containing both $`x`$ and $`y`$.
Note that there is a bijection between the $`1(l+1)l\mathrm{}2`$-patterns of $`p^{\prime \prime \prime }`$ not containing $`y`$ and the $`1(l+1)l\mathrm{}2`$-patterns of $`p^{\prime \prime }`$. A similar statement holds for $`p^{\prime \prime }`$ and $`p^{}`$. So

$$M_k=r,M_{k+1}=r+s,M_{k+2}=r+s+t+u.$$

Note also that $`st`$ because increasing the length of the layer of $`x`$ results in the most number of $`1(l+1)l\mathrm{}2`$-patterns being added to $`p^{}`$. It follows that $`(M_{k+2}M_{k+1})(M_{k+1}M_k)=t+usu`$.

By Lemma 5.1 (iii), $`k<m`$, so to obtain (11) it suffices to show that $`u\left(\genfrac{}{}{0pt}{}{k}{l1}\right)`$. But $`\left(\genfrac{}{}{0pt}{}{k}{l1}\right)`$ is the total number of subsequences of $`p^{\prime \prime \prime }`$ having length $`l+1`$ and containing $`x`$ and $`y`$. So the inequality follows.

The proof of the induction step is similar. Assume that (8) is true for $`i1`$ so that

$$M_{i1}+(i1)\left(\genfrac{}{}{0pt}{}{r+1}{l}\right)M_i+i\left(\genfrac{}{}{0pt}{}{r}{l}\right).$$
(12)
where $`r=n+1i`$. We wish to prove

$$M_i+i\left(\genfrac{}{}{0pt}{}{r}{l}\right)M_{i+1}+(i+1)\left(\genfrac{}{}{0pt}{}{r1}{l}\right).$$
(13)
Subtracting as usual and simplifying, we need to show

$$2\left(\genfrac{}{}{0pt}{}{r1}{l1}\right)(i1)\left(\genfrac{}{}{0pt}{}{r1}{l2}\right)(M_{i+1}M_i)(M_iM_{i1}).$$

Proceeding exactly as in the base case, we will be done if we can show that

$$\frac{2rlil+i+1}{rl+1}\left(\genfrac{}{}{0pt}{}{r1}{l1}\right)=2\left(\genfrac{}{}{0pt}{}{r1}{l1}\right)(i1)\left(\genfrac{}{}{0pt}{}{r1}{l2}\right)\left(\genfrac{}{}{0pt}{}{i1}{l1}\right).$$

Because $`i<\frac{n+1}{l}`$ we have $`ri`$, so it suffices to show that

$$\frac{2rlil+i+1}{rl+1}\left(\genfrac{}{}{0pt}{}{r1}{l1}\right)1.$$

This simplifies to showing that $`i(r+i)/l=(n+1)/l`$, and this is guaranteed by our choice of $`i`$. $`\mathrm{}`$

The following lemma contains two inequalities essentially shown in the proof of Lemma 5.3 which we will need to use again.

###### Lemma 5.4

If $`q=1(l+1)l\mathrm{}2`$ then $`0(M_{i+2}M_{i+1})(M_{i+1}M_i)\left(\genfrac{}{}{0pt}{}{i}{l1}\right)`$.

Proof: For the upper bound, recall that $`\left(\genfrac{}{}{0pt}{}{i}{l1}\right)`$ is the total number of subsequences of $`p^{\prime \prime \prime }`$ of length $`l+1`$ containing $`x`$ and $`y`$ while the double difference just counts those subsequences corresponding to the pattern $`q=1(l+1)l\mathrm{}2`$. For the lower bound, we showed that

$$(M_{i+2}M_{i+1})(M_{i+1}M_i)=t+us.$$

Recall that $`t+u`$ is the total contribution of $`y`$ in $`p^{\prime \prime \prime }`$, and $`s`$ is the total contribution of $`x`$ in $`p^{\prime \prime }`$. Therefore $`t+us0`$, as otherwise one could create a permutation with more $`1(l+1)l\mathrm{}2`$-patterns than $`p^{\prime \prime \prime }`$ by inserting a new element in the same layer as $`x`$ $`\mathrm{}`$

## 6 The sequence $`(c_{n,i})_{i=1}^{n1}`$ for $`q=1(l+1)l\mathrm{}2`$

Now that we have completed the proof of Theorem 4.1, we turn our attention to the tools which will enable us to show that there are infinitely many IZ integers. As before, all invariants are for $`q=1(l+1)l\mathrm{}2`$ unless otherwise stated.

For $`l=2`$, we will need the following lemma.

###### Lemma 6.1

For all $`n`$, we have $`M_{n+1,132}M_{n,132}5n^2/16`$.

Proof: Let $`k=k_n`$. We induct on $`n`$. It is easy to check the base cases $`n=1,2`$. Note that by Theorem 4.1, either $`k_{n+1}=k`$ or $`k_{n+1}=k+1`$. If $`k_{n+1}=k`$, then we have

$$M_{n+1}M_n=nkk^2$$

and maximizing this as a function of $`k`$ gives

$$M_{n+1}M_n\frac{n^2}{4}\frac{5n^2}{16}.$$

If $`k_{n+1}=k+1`$, then we have

$$M_{n+1}M_n=M_{k+1}M_k+\left(\genfrac{}{}{0pt}{}{nk}{2}\right).$$

By induction, we have $`M_{k+1}M_k\frac{5k^2}{16}`$, and thus we have that

$$M_{n+1}M_n\frac{13k^2}{16}+\frac{n^2+kn2kn}{2}.$$

By Lemma 5.1 (iii) and (iv), this function is to be maximized on the interval $`[(n2)/3,n/2]`$ and for $`n3`$ this maximum occurs at $`k=(n2)/3`$. So

$$M_{n+1}M_n\frac{37n^24n+4}{144}\frac{5n^2}{16},$$

as desired. $`\mathrm{}`$

###### Definition 6.2

For $`q=1(l+1)l\mathrm{}2`$ and any positive integer $`n`$, let $`l_n`$ be the least integer greater than $`k_n`$ such that $`c_{n,i}c_{n,i+1}`$. If there is no integer with this property, let $`l_n=n1`$.

Do not confuse $`l_n`$, which will always be subscripted, with the length-related parameter $`l`$ , which will never be. Our next result shows that the sequence $`(c_{n,i})_{i=1}^{n1}`$ is “bimodal” with a maximum at $`i=k_n`$ and a minimum at $`i=l_n`$.

###### Theorem 6.3

For $`q=1(l+1)l\mathrm{}2`$ and all positive integers $`n`$, we have the following three results about the shape of $`(c_{n,i})_{i=1}^{n1}`$

1. $`c_{n,i}c_{n,i+1}`$ for all $`i<k_n`$,
2. $`c_{n,i}c_{n,i+1}`$ for all $`k_ni<l_n`$,
3. $`c_{n,i}c_{n,i+1}`$ for all $`il_n`$.

Proof: For (i) we induct on $`n`$. The claim is true trivially for $`n<l+1`$ since then $`c_{n,i}=0`$ for all $`i`$, so we will assume $`nl+1`$. If $`i=k_n1`$ then the claim is true by definition. If $`i<k_n1`$ then $`i<k_{n1}`$ by Theorem 4.1 and we are able to apply induction. We would like to show that

$$M_i+i\left(\genfrac{}{}{0pt}{}{ni}{l}\right)M_{i+1}+(i+1)\left(\genfrac{}{}{0pt}{}{ni1}{l}\right)$$

and we know by induction that

$$M_i+i\left(\genfrac{}{}{0pt}{}{ni1}{l}\right)M_{i+1}+(i+1)\left(\genfrac{}{}{0pt}{}{ni2}{l}\right).$$

Subtracting as usual, we are reduced to showing that $`i\left(\genfrac{}{}{0pt}{}{ni1}{l1}\right)(i+1)\left(\genfrac{}{}{0pt}{}{ni2}{l1}\right)`$. This further reduces to $`i(nl)/l`$ which is true by Lemma 5.1 (iii) and the fact that $`i<k_n1`$.

Statement (ii) is implied by the definition of $`l_n`$, so we are left with (iii). By the definition of $`l_n`$ we have that $`c_{n,l_n}c_{n,l_n+1}`$, so it suffices to show that for all $`il_n`$, if $`c_{n,i}c_{n,i+1}`$ then $`c_{n,i+1}c_{n,i+2}`$. Subtracting in the usual way, we are reduced to showing that

$$(M_{i+2}M_{i+1})(M_{i+1}M_i)\frac{2n2li(l+1)}{l1}\left(\genfrac{}{}{0pt}{}{ni2}{l2}\right).$$
(14)
Since we know that $`(M_{i+2}M_{i+1})(M_{i+1}M_i)0`$ by Lemma 5.4, our approach will be to show that $`2n2li(l+1)0`$ for $`il_n`$ by showing that

$$l_n(2n2l)/(l+1).$$
(15)
Before we prove (15), we will need the following two facts.

$`l_nn/l`$ and $`l_nl_{n1}`$.

The first fact follows from our proof of Lemma 5.3, in which we showed that $`c_{n,i}c_{n,i+1}`$ for $`k_ni<n/l`$. So to prove the second fact, it suffices to show that $`c_{n1,i}>c_{n1,i+1}`$ implies $`c_{n,i}>c_{n,i+1}`$ for $`in/l`$. This is proved in exactly the same way as (i) with all the inequalities reversed.

Now we are ready to prove (15). First we tackle the case where $`l3`$ by induction. If $`n3`$ then $`(2n2l)/(l+1)0`$ and we are done. So suppose $`n4`$. If $`l_{n2}>(n1)/2`$, then since $`l_nl_{n2}`$ and $`l3`$ we have $`l_n>(2n2l)/(l+1)`$ as desired. Hence we may assume that $`(n2)/ll_{n2}(n1)/2`$. In this case we claim that $`l_nl_{n2}+1`$, which will imply (15) by induction.

Let $`i=l_{n2}`$. We want to show that

$$M_i+i\left(\genfrac{}{}{0pt}{}{ni}{l}\right)>M_{i+1}+(i+1)\left(\genfrac{}{}{0pt}{}{ni1}{l}\right),$$

and we have

$$M_{i1}+(i1)\left(\genfrac{}{}{0pt}{}{ni1}{l}\right)>M_i+i\left(\genfrac{}{}{0pt}{}{ni2}{l}\right).$$

Subtracting, it suffices to show that

$$(M_{i+1}M_i)(M_iM_{i1})i\left(\genfrac{}{}{0pt}{}{ni2}{l2}\right).$$

By Lemma 5.4, $`(M_{i+1}M_i)(M_iM_{i1})\left(\genfrac{}{}{0pt}{}{i1}{l1}\right)`$, so it suffices to show that

$$\left(\genfrac{}{}{0pt}{}{i1}{l1}\right)\frac{ili}{nil}\left(\genfrac{}{}{0pt}{}{ni2}{l1}\right).$$
(16)
Since $`i(n2)/l`$, we have that $`(ili)/(nil)1`$, and since $`i(n1)/2`$, we have that $`ni2i1`$, so (16) is true, and thus (15) holds.

For the case where $`l=2`$, we examine the quadratics

$$d_i(n)=\frac{1}{2}n^2\left(2i+\frac{3}{2}\right)n+\left(M_{i+1}M_i+\frac{3}{2}i^2+\frac{5}{2}i+1\right),$$

which agree with $`c_{n,i+1}c_{n,i}`$, wherever both $`c_{n,i+1}`$ and $`c_{n,i}`$ are defined. We will also need to refer to the roots of $`d_i(n)`$, which occur at

$$r_i=2i+\frac{3}{2}\sqrt{i^2+i+\frac{1}{4}2\left(M_{i+1}M_i\right)},\text{ and}$$

$$s_i=2i+\frac{3}{2}+\sqrt{i^2+i+\frac{1}{4}2\left(M_{i+1}M_i\right)}.$$

Lemma 6.1 gives us that

$$r_i<(2\sqrt{3/8})i+3/2,$$
(17)
so $`r_i`$ and $`s_i`$ are real numbers and for $`i>13`$, $`r_i<3i/2`$. These roots are important in our situation for the following reasons:

$$d_i(n)<0\text{ if and only if }r_i<n<s_i,$$
(18)
$$ns_i\text{ if and only if }ik_n,\text{ and}$$
(19)
$$nr_{l_n}.$$
(20)
Statement (18) is easily verified. Assume to the contrary that the forward direction of (19) is not true, and thus $`ns_i`$ but $`i>k_n`$. Let $`n^{}`$ be such that $`k_n^{}=i`$. By Proposition 5.2, we have that $`n^{}>ns_i`$, and thus $`d_i(n^{})0`$ by (18). However because $`i=k_n^{}`$, we have that $`d_i(n^{})<0`$, a contradiction. To prove the reverse direction of (19), notice that if $`ik_n`$ then by (i) and the definition of $`k_n`$, we must have that $`d_i(n)0`$. Therefore by (18), either $`ns_i`$ (as we would like) or $`nr_i`$, and by (17), it cannot be the case that $`nr_i`$, as that would imply that $`nr_i<3i/2<3k_n/2`$ if $`i>13`$, contradicting Lemma 5.1 (iii).

To prove (20), note that by (18) we cannot have $`r_{l_n}<n<s_{l_n}`$ as then we would have $`d_{l_n}(n)<0`$, contradicting the definition of $`l_n`$. Also, we cannot have $`ns_{l_n}`$ as then we would have $`l_nk_n`$ by (19), again contradicting the definition of $`l_n`$. Hence we must have (20).

With these tools, (15) is easy to prove; we have $`nr_{l_n}<3l_n/2`$ for $`l_n>13`$, and thus $`l_n>2n/3`$, as desired. It is easily checked that $`l_n>2n/3`$ for $`l_n13`$. $`\mathrm{}`$

We will depend on the following lemma to find integers $`n`$ with an internal zero at $`M_n1`$.

###### Lemma 6.4

For $`q=1(l+1)l\mathrm{}2`$, $`l2`$ and all $`n2l+2`$, if $`k_{n2}=k1`$ and $`k_{n1}=k`$, then $`M_nc_{n,i}>1`$ for all $`ik`$, so in particular, $`k_n=k`$.

Proof: By Theorem 6.3 it suffices to show the following inequalities:

$$c_{n,k}c_{n,k1}>1,$$
(21)
$$c_{n,k}c_{n,k+1}>1,$$
(22)
and

$$c_{n,k}c_{n,n1}>1.$$
(23)
Statement (23) is clear for $`n2l+2`$ because $`c_{n,n1}=M_{n1}`$, $`(M_iM_{i1})(M_{i1}M_{i2})`$ for all $`i`$ by Lemma 5.4, and $`M_{l+2}M_{l+1}=l`$.

We prove (22) by induction on $`n`$. First, if $`k<l`$, then $`M_{k1}=M_k=M_{k+1}=0`$, so it suffices to show that

$$k\left(\genfrac{}{}{0pt}{}{nk}{l}\right)>(k+1)\left(\genfrac{}{}{0pt}{}{nk1}{l}\right)+1,$$

and since $`k_{n2}=k1`$, we have

$$(k1)\left(\genfrac{}{}{0pt}{}{nk1}{l}\right)>k\left(\genfrac{}{}{0pt}{}{nk2}{l}\right).$$

Subtracting that latter from the former, it suffices to show that

$$1k\left(\genfrac{}{}{0pt}{}{nk2}{l2}\right).$$

So we’re done in this case since $`nkl`$ which follows from $`n2l+2`$ and $`k<l`$.

Now assume that $`kl`$, so we may prove (22) by showing the stronger statement that

$$c_{n,k}c_{n,k+1}>\left(\genfrac{}{}{0pt}{}{k2}{l2}\right),$$

and thus we would like to show that

$$M_k+k\left(\genfrac{}{}{0pt}{}{nk}{l}\right)>M_{k+1}+(k+1)\left(\genfrac{}{}{0pt}{}{nk1}{l}\right)+\left(\genfrac{}{}{0pt}{}{k2}{l2}\right),$$

and as $`k_{n2}=k1`$, we have

$$M_{k1}+(k1)\left(\genfrac{}{}{0pt}{}{nk1}{l}\right)>M_k+k\left(\genfrac{}{}{0pt}{}{nk2}{l}\right).$$

Subtracting as usual, we are reduced to showing

$$(M_{k+1}M_k)(M_kM_{k1})k\left(\genfrac{}{}{0pt}{}{nk2}{l2}\right)\left(\genfrac{}{}{0pt}{}{k2}{l2}\right).$$

By Lemma 5.1 (iii)

$$k\left(\genfrac{}{}{0pt}{}{nk2}{l2}\right)\left(\genfrac{}{}{0pt}{}{k2}{l2}\right)>k\left(\genfrac{}{}{0pt}{}{k2}{l2}\right)\left(\genfrac{}{}{0pt}{}{k2}{l2}\right)=(l1)\left(\genfrac{}{}{0pt}{}{k1}{l1}\right).$$

The upper bound in Lemma 5.4 now completes the proof of (22).

To prove (21), we want to show

$$M_k+k\left(\genfrac{}{}{0pt}{}{nk}{l}\right)>M_{k1}+(k1)\left(\genfrac{}{}{0pt}{}{nk+1}{l}\right)+1,$$

and we are given

$$M_k+k\left(\genfrac{}{}{0pt}{}{nk1}{l}\right)M_{k1}+(k1)\left(\genfrac{}{}{0pt}{}{nk}{l}\right).$$

Subtracting as usual, we are reduced to showing that

$$k\left(\genfrac{}{}{0pt}{}{nk1}{l1}\right)>(k1)\left(\genfrac{}{}{0pt}{}{nk}{l1}\right)+1.$$

Cancelling $`\left(\genfrac{}{}{0pt}{}{nk1}{l1}\right)`$ and simplifying, it suffices to show that

$$n>lk+\frac{nkl+1}{\left(\genfrac{}{}{0pt}{}{nk1}{l1}\right)}.$$
(24)
By Lemma 5.1 (iii), $`nlk+1`$, so it suffices to show that

$$nkl+1<\left(\genfrac{}{}{0pt}{}{nk1}{l1}\right),$$

which is true for $`l3`$. For $`l=2`$, note that proving (24) reduces to showing $`n>2k+1`$ which we will prove by induction on $`n`$. Checking the base cases $`n=6,7`$ is easy. Also note that (24) holds for $`l=2`$ if we make the strict inequality weak, so we still can conclude the $`k_n=k`$ part of the Lemma. There are now two cases. If $`k_{n1}=k_n=k`$ then by induction $`n>n1>2k+1`$. By Theorem 4.1 and the part of the Lemma that we’ve already proved, the only other possibility is $`k_{n1}=k1`$ and $`k_{n2}=k1`$. But then $`n2>2(k1)+1`$ which is equivalent to the desired inequality. $`\mathrm{}`$

## 7 The poset connection

There is an intimate connection between partially ordered sets, called posets for short, and permutations. Using this connection, we will provide characterizations of all $`n`$-permutations $`p`$ which have $`c_{1(l+1)l\mathrm{}2}(p)M_{n,1(l+1)l\mathrm{}2}1`$ for $`l2`$. This will provide us with the tools we need to show that there are an infinite number of IZ sequences for each of these patterns. Any necessary definitions from the theory of posets that are not given here will be found in Stanley’s text .

If $`P`$ is a poset such that any two distinct elements of $`P`$ are incomparable we say that $`P`$ is an antichain. Since there is a unique unlabelled antichain on $`n`$ elements, we denote this poset by $`𝒜_n`$.

Given posets $`P`$ and $`Q`$, the ordinal sum of $`P`$ and $`Q`$, denoted $`PQ`$, is the unique poset on the elements $`PQ`$ where $`xy`$ in $`PQ`$ if either

1. $`x,yP`$ with $`xy`$,
2. $`x,yQ`$ with $`xy`$, or
3. $`xP`$ and $`yQ`$.

A poset $`P`$ is layered if it is an ordinal sum of antichains, i.e. if $`P=𝒜_{p_1}𝒜_{p_2}\mathrm{}𝒜_{p_k}`$ for some $`p_1,\mathrm{},p_k`$. To introduce a related notion, let $`\mathrm{max}P`$ denote the set of maximal elements of $`P`$ and $`\overline{P}=P(\mathrm{max}P)`$. Then $`P`$ is LOT (layered on top) if $`P=\overline{P}\mathrm{max}P`$. Note that if $`P`$ is layered then it is LOT, but not conversely.

If $`p=p_1p_2\mathrm{}p_n`$ is a permutation, then the corresponding poset $`P_p`$ has elements $`p_1,p_2,\mathrm{},p_n`$ with partial order $`p_i<p_j`$ if $`(p_i,p_j)`$ is a noninversion in $`p`$. So, for example, $`P_{12\mathrm{}n}`$ is a chain, $`P_{n\mathrm{}21}=𝒜_n`$ and $`P_{1(l+1)l\mathrm{}2}=𝒜_1𝒜_l`$. Clearly not every poset is of the form $`P_p`$ for some $`p`$. In fact, the $`P_p`$ are exactly the posets of dimension at most 2, being the intersection of the total orders $`1<2<\mathrm{}<n`$ and $`p_1<p_2<\mathrm{}<p_n`$.

Given posets $`P`$ and $`Q`$ let

$$c_Q(P)=\text{ the number of induced subposets of }P\text{ isomorphic to }Q.$$

Now given permutations $`p,q`$ with corresponding posets $`P=P_p,Q=P_q`$, we have $`c_q(p)c_Q(P)`$ since the elements of each copy of $`q`$ in $`p`$ form a subposet of $`P`$ isomorphic to $`Q`$.

If $`SP`$ then let

$`c_Q(P;S)`$ $`=`$ $`\text{the number of induced }Q^{}P\text{ with }Q^{}Q\text{ and }SQ^{}\mathrm{},`$
$`c_Q(P;notS)`$ $`=`$ $`\text{the number of induced }Q^{}P\text{ with }Q^{}Q\text{ and }SQ^{}=\mathrm{}.`$
We will freely combine these notations and eliminate the subscript when talking about a fixed poset $`Q`$. We will also abbreviate $`c_Q(P;\{x\})`$ to $`c_Q(P;x)`$ and $`c_Q(P;not\{x\})`$ to $`c_Q(P;notx)`$.

As with permutations, for any non-negative integer $`n`$ we will let $`M_{n,Q}=\mathrm{max}\{c_Q(P):|P|=n\}`$. We will say a poset $`P`$ is $`Q`$-optimal if $`c_Q(P)=M_{|P|,Q}`$.

Stromquist proved Theorem 3.1 by first demonstrating the following stronger result.

###### Theorem 7.1 ()

If $`Q`$ is a LOT pattern, then there is some $`Q`$-optimal LOT poset $`P`$. The same holds with “LOT” replaced by “layered.”

To show that the sequences of the patterns $`1(l+1)l\mathrm{}2`$, for $`l2`$, have infinitely many IZ integers, we will need to know more about $`𝒜_1𝒜_l`$-optimal posets. The best possible case would be if all (sufficiently large) $`𝒜_1𝒜_l`$-optimal posets were layered. This is true for the pattern $`P_{132}=𝒜_1𝒜_2`$, but not in general. For example, it can be computed that $`P_{231}𝒜_8`$ is $`𝒜_1𝒜_3`$-optimal, but $`P_{231}𝒜_8`$ is not layered. Fortunately, we are able to show that all $`𝒜_1𝒜_l`$-optimal posets are of the following slightly more general form.

###### Definition 7.2

We say $`P=P_1P_2`$ is an $`l`$-decomposition of $`P`$ if $`P_2`$ is layered and for all $`AP`$ with $`A𝒜_1𝒜_l`$ we have $`|AP_1|1`$.

The first part of this section concerns the proof of the following theorem.

###### Theorem 7.3

If $`P`$ is an $`𝒜_1𝒜_l`$-optimal poset then $`P`$ has an $`l`$-decomposition.

After this proof we will investigate ‘almost’ $`𝒜_1𝒜_l`$-optimal posets, that is, posets $`P`$ with $`c_{𝒜_1𝒜_l}(P)=M_{|P|,𝒜_1𝒜_l}1`$.

If $`q`$ and $`p`$ are permutations, it is generally not the case that $`c_{P_q}(P_p)=c_q(p)`$. For example, $`P_{231}P_{312}`$ and thus $`c_{P_{231}}(P_{312})=1`$, but $`c_{231}(312)=0`$. However, there is an important case in which we do get equality.

###### Lemma 7.4

If $`q`$ and $`p`$ are permutations then $`c_q(p)c_{P_q}(P_p)`$. Furthermore, if either $`q`$ or $`p`$ is layered then $`c_q(p)=c_{P_q}(P_p)`$.

Proof: The inequality follows from the fact that each copy of $`q`$ in $`p`$ gives rise to a copy of $`P_q`$ in $`P_p`$. For the equality, if $`q`$ is layered then it is the unique permutation giving rise to the poset $`P_q`$. So every copy of $`P_q`$ in $`P_p`$ corresponds to a copy of $`q`$ in $`p`$ and we are done. The only other case we need to consider is if $`p`$ is layered and $`q`$ is not. But then both sides of the equality are zero. $`\mathrm{}`$

This lemma and the preceeding theorems imply several important features about the connection between pattern matching in posets and permutations. Given any pattern $`q`$, the first statement in Lemma 7.4 implies that $`M_{n,q}M_{n,P_q}`$ for all $`n`$. If $`q`$ is layered, then by Theorem 7.1 there is a layered $`P_q`$-optimal poset $`P=𝒜_{p_1}𝒜_{p_2}\mathrm{}𝒜_{p_k}`$ for some positive integers $`p_1,\mathrm{},p_k`$. It follows that there is a layered permutation $`p`$ such that $`P_pP`$, namely $`p`$ is the permutation whose layer lengths from left to right are $`p_1,\mathrm{},p_k`$. By the preceeding lemma, $`c_q(p)=c_{P_q}(P)`$, so $`M_{|P|,q}=M_{|P|,P_q}`$.

###### Lemma 7.5

For all patterns $`Q`$, the sequence $`(M_{n,Q})_{n|Q|}`$ is positive and strictly increasing.

Proof: We will write $`M_n`$ for $`M_{n,Q}`$ and $`c(P)`$ for $`c(P)`$. Given $`n|Q|`$, it is easy to construct a poset $`P`$ with $`c(P)>0`$. So let $`P`$ be a $`Q`$-optimal poset. Now there must be some $`xP`$ with $`c(P;x)>0`$. Now adjoin an element $`y`$ to $`P`$ to form a poset $`P^{}`$ with $`a<b`$ in $`P^{}`$ if either

1. $`a,bP`$ with $`a<b`$,
2. $`a=y`$, $`bP`$ with $`x<b`$, or
3. $`b=y`$, $`aP`$ with $`a<x`$.

Then

$$c(P^{})=c(P^{};noty)+c(P^{};y)=c(P)+c(P^{};y)c(P)+c(P;x)>c(P)$$

so $`M_{n+1}c(P^{})>c(P)=M_n`$. $`\mathrm{}`$

We now begin the proof of Theorem 7.3 by making a few definitions. If $`P`$ is a poset and $`xP`$ then the open down-set generated by $`x`$ is

$$P_{<x}=\{yP:y<x\}.$$

If $`x,y\mathrm{max}P`$ then let $`P^{xy}`$ be the unique poset on the same set of elements which satisfies

$$P_{<z}^{xy}=P_{<z}\text{ for }zx\text{ and }P_{<x}^{xy}=P_{<y}.$$

Note that $`Px=P^{xy}x`$. The following lemma is essentially in Stromquist , but is not explicitly proved there. So we will provide a demonstration.

###### Lemma 7.6

Let $`Q`$ be a LOT pattern and $`P`$ be any poset with $`x,y\mathrm{max}P`$. Then

$$c_Q(P^{xy})c_Q(P)+c_Q(P;y)c_Q(P;x).$$

Proof: As before, we write $`c(P)`$ for $`c_Q(P)`$. Since

$`c(P)`$ $`=`$ $`c(P;notx)+c(P;y,notx)+c(P;x,y),\text{ and}`$
$`c(P^{xy})`$ $`=`$ $`c(P^{xy};notx)+c(P^{xy};x,noty)+c(P^{xy};x,y),`$
it is enough to show that

$`c(P^{xy};noty)`$ $`=`$ $`c(P;noty),`$ (25)
$`c(P^{xy};x,noty)`$ $``$ $`c(P;x,noty)+c(P;y)c(P;x),`$ (26)
$`c(P^{xy};x,y)`$ $``$ $`c(P;x,y).`$ (27)
First, (25) is clear since $`P`$ and $`P^{xy}`$ agree on all subsets not including $`x`$.

Next, notice that

$$c(P;x,noty)+c(P;y)c(P;x)=c(P;y,notx),$$

and thus to prove (26), it suffices to show that $`c(P^{xy};x,noty)c(P;y,notx)`$, but this is easy. Let $`AP`$ with $`yA`$, $`xA`$, and $`(A,)Q`$. Then $`A^{}=A\{x\}y`$ is an occurance of $`Q`$ in $`P^{xy}`$, i.e., $`(A^{},_{P^{xy}})Q`$, so (26) is proved.

Finally, to prove (27), let $`AP`$ be an occurance of $`Q`$ in $`P`$ which contains $`x`$ and $`y`$, i.e., $`(A,_P)Q`$. Then we have that $`(A,_{P^{xy}})Q`$ as well. This is because $`A_{<x}=A_{<y}`$ in $`P`$ since $`x,y`$ are maximal and $`Q`$ is LOT. So $`A`$ forms an occurance of $`Q`$ in $`P^{xy}`$, and thus (27) is proven. $`\mathrm{}`$

For the rest of this section, let $`Q_l=𝒜_1𝒜_l`$, $`c(P)=c_{Q_l}(P)`$ and $`M_n=M_{n,Q_l}`$.

###### Lemma 7.7

Let $`P`$ be a poset such that $`|P|>l2`$. If for some $`a0`$ and $`x\mathrm{max}P`$ we have

1. $`Px`$ is LOT,
2. $`c_{Q_l}(P)=M_{|P|,Q_l}a`$, and
3. $`c_{Q_l}(P;x)=c_{Q_l}(P;y)a`$ for all $`y\mathrm{max}Px`$,

then $`P`$ is LOT (and thus $`a`$ is actually $`0`$).

Proof: Choose $`y\mathrm{max}P`$ with $`yx`$, let $`m=|\mathrm{max}P|`$ and $`k=|\overline{P}|=|P|m`$. First consider what happens when $`m<l`$. Then (a) implies that $`C(P;y)=0`$ for all $`y\mathrm{max}Px`$. This forces $`c(P;x)=a=0`$ by (c). Now (b) yields $`c(\overline{P})=c(P)=M_{|P|}`$, contradicting Lemma 7.5. So we may assume $`ml`$.

Note that $`c(P)=c(Px)+c(P;x)`$, and since $`c(P;x)=c(P;y)a=c(P;x,y)+c(P;notx,y)a=c(P;x,y)+c(Px;y)a`$ we get that

$$c(P)=c(Px)+c(Px;y)+c(P;x,y)a.$$

Furthermore, since $`Px`$ is LOT we get that

$$c(Px)=c(\overline{P})+\left(\genfrac{}{}{0pt}{}{m1}{l}\right)k,$$

and

$$c(Px;y)=\left(\genfrac{}{}{0pt}{}{m2}{l1}\right)k.$$

Also, since $`P_{<x}\overline{P}=P_{<y}`$, we have that

$$c(P;x,y)=\left(\genfrac{}{}{0pt}{}{m2}{l2}\right)|P_{<x}|,\text{ so}$$

$$c(P)=c(\overline{P})+\left(\left(\genfrac{}{}{0pt}{}{m1}{l}\right)k+\left(\genfrac{}{}{0pt}{}{m2}{l1}\right)k+\left(\genfrac{}{}{0pt}{}{m2}{l2}\right)|P_{<x}|\right)a.$$
(28)
Furthermore, since $`Px`$ is LOT, $`P^{xy}`$ is LOT, so we have

$$c(P^{xy})=c(\overline{P})+\left(\genfrac{}{}{0pt}{}{m}{l}\right)k.$$

Therefore

$`c(P^{xy})c(P)`$ $`=`$ $`a+\left(\left(\left({\displaystyle \genfrac{}{}{0pt}{}{m}{l}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{m1}{l}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{m2}{l1}}\right)\right)k\left({\displaystyle \genfrac{}{}{0pt}{}{m2}{l2}}\right)|P_{<x}|\right)`$ (29)
$`=`$ $`a+\left({\displaystyle \genfrac{}{}{0pt}{}{m2}{l2}}\right)\left(k|P_{<x}|\right).`$
Furthermore, by Lemma 7.6 and assumptions (b) and (c) we have that $`c(P^{xy})M_{|P|}`$. So we must have $`c(P^{xy})=M_{|P|}`$ and, by (b) again, $`c(P^{xy})c(P)=a`$. It follows that $`\left(\genfrac{}{}{0pt}{}{m2}{l2}\right)\left(k|P_{<x}|\right)=0`$. Therefore since $`ml`$ we have $`\left(\genfrac{}{}{0pt}{}{m2}{l2}\right)>0`$ and so $`k=|P_{<x}|`$. Also, because $`P_{<x}\overline{P}`$, we have $`P_{<x}=\overline{P}`$ and thus $`P`$ is LOT, as desired. $`\mathrm{}`$

###### Definition 7.8

For any poset $`P`$, let $`\mu (P)`$ be defined by

$$\mu (P)=\mathrm{max}\{k:\text{ there exists }S\mathrm{max}P\text{ with }|S|=k\text{ such that if }x,yS\text{ then }P_{<x}=P_{<y}\}$$

Clearly $`\mu (P)|\mathrm{max}P|`$, with equality if and only if $`P`$ is LOT. It turns out that $`\mu (P)`$ is a useful statistic for induction. We now have all the necessary tools to prove Theorem 7.3.

Proof of Theorem 7.3: Notice that the claim is trivial for $`|P|<l+1`$ as all posets on less than $`l+1`$ elements cannot have any $`Q_l`$-patterns and thus they have the trivial $`l`$\- decomposition $`P\mathrm{}`$.

Assume to the contrary that the claim is not true and let $`P`$ be an $`Q_l`$\- optimal poset of least cardinality that does not have a LOT $`l`$-decomposition with $`\mu (P)`$ maximal over all such choices of $`P`$ and $`|P|l+1`$. Let $`S`$ be the set from Definition 7.8, $`m=|\mathrm{max}P|`$ and $`k=|\overline{P}|=|P|m`$.

First, we claim that $`P`$ is LOT. If not, then there is some element, say $`x(\mathrm{max}P)S`$. Also let $`yS`$. If $`c(P;x)c(P;y)`$, then by Lemma 7.6 either $`c(P^{xy})>M_{|P|}`$ or $`c(P^{yx})>M_{|P|}`$, both contradictions, so $`c(P;x)=c(P;y)`$ and $`P^{xy}`$ is $`Q_l`$-optimal. Since $`\mu (P^{xy})>\mu (P)`$, by our choice of $`P`$ we know that $`P^{xy}`$ has an $`l`$-decomposition $`P_1P_2`$.

If $`P_2=\mathrm{}`$, then $`c(P^{xy})=0`$, so by Lemma 7.5, $`|P|<l+1`$ (because $`M_{l+1}=1`$), a contradiction to our choice of $`P`$.

Hence we may assume that $`P_2\mathrm{}`$, so $`P^{xy}`$ is LOT. As the only element $`P`$ and $`P^{xy}`$ disagree on is $`x`$, we have that $`Px`$ is LOT. Hence by Lemma 7.7, $`P`$ is also LOT.

Now that we know that $`P`$ is LOT, we get that $`c(P)=c(\overline{P})+\left(\genfrac{}{}{0pt}{}{m}{l}\right)k`$, so $`\overline{P}`$ is $`Q_l`$\- optimal. By induction, $`\overline{P}`$ has an $`l`$-decomposition $`\overline{P}=P_1P_2`$ and thus $`P=P_1(P_2\mathrm{max}P)`$ is an $`l`$\- decomposition for $`P`$. $`\mathrm{}`$

Note that by using the ideas in the last paragraph of this proof one may show that if $`P=P_1P_2`$ is an $`l`$-decomposition for an $`Q_l`$-optimal poset $`P`$ then $`|P_1|<l+1`$. Hence because all posets on less than three elements are layered, all $`P_{132}`$-optimal posets (and thus $`132`$-optimal permutations) are layered. This observation will be useful in the following proof.

###### Theorem 7.9

If $`P`$ is such that $`c_{Q_l}(P)=M_{|P|,Q_l}1`$ then there is a poset $`Q`$ with $`|Q|=|P|`$ and one of the following:

1. $`c_{Q_l}(Q)=M_{|P|,Q_l}1`$ and $`Q`$ is LOT, or
2. $`Q`$ is $`Q_l`$-optimal and $`|\mathrm{max}Q|=l`$, or
3. $`l=2`$ and $`|P|=5.`$

Proof: Assume that (i) does not hold and choose $`P`$ with $`c(P)=M_{|P|}1`$ and $`\mu (P)`$ maximal over all such choices. Let $`n=|P|`$, $`m=|\mathrm{max}P|`$ and $`k=|\overline{P}|=nm`$.

We must have $`|c(P;x)c(P;y)|1`$ for all $`x,y\mathrm{max}P`$ as otherwise by Lemma 7.6 we would have either $`c(P^{yx})>M_n`$ or $`c(P^{xy})>M_n`$, a contradiction. Hence we have

$$\mathrm{max}\{c(P;x)c(P;y):x,y\mathrm{max}P\}\{0,1\}.$$

First we tackle the easier case, where $`\mathrm{max}\{c(P;x)c(P;y):x,y\mathrm{max}P\}=1`$. Pick two maximal elements of $`P`$, say $`x,y\mathrm{max}P`$, so that $`c(P;y)c(P;x)=1`$. By Lemma 7.6 we have that $`c(P^{xy})=M_n`$, and thus by Theorem 7.3 we know $`P^{xy}`$ has an $`l`$-decomposition $`P_1P_2`$. Since $`c(P)=M_n1`$, we must have $`M_n>0`$, so we also have that $`nl+1`$ and $`P_2\mathrm{}`$. Therefore $`P^{xy}`$ and consequently $`Px`$ are LOT. Hence by Lemma 7.7, $`P`$ is LOT, a contradiction.

Now assume $`\mathrm{max}\{c(P;x)c(P;y):x,y\mathrm{max}P\}=0`$. Let $`S`$ be as in Definition 7.8, pick $`x(\mathrm{max}P)S`$ ($`x`$ must exist as $`P`$ is not LOT) and $`yS`$. Now $`c(P;x)=c(P;y)`$ and thus $`c(P^{xy})M_n1`$ by Lemma 7.6. However if $`c(P^{xy})=M_n1`$ then we have contradicted our choice of $`P`$ as $`\mu (P^{xy})>\mu (P)`$. Therefore $`c(P^{xy})=M_n`$ so by Theorem 7.3, $`P^{xy}`$ has an $`l`$-decomposition $`P_1P_2`$. By the same reasoning as the previous case, $`P_2\mathrm{}`$, so again $`P^{xy}`$ and $`Px`$ are both LOT.

Although we cannot apply Lemma 7.7 in this case, (29) still holds for $`P`$ with $`a=0`$, so

$$c(P^{xy})c(P)=1=\left(\genfrac{}{}{0pt}{}{m2}{l2}\right)\left(k|P_{<x}|\right).$$

Therefore we must have $`\left(\genfrac{}{}{0pt}{}{m2}{l2}\right)=1`$. If $`l>2`$, this implies that $`m=l`$, so (ii) is true with $`Q=P^{xy}`$.

If $`l=2`$ then we must have $`k|P_{<x}|=1`$, so there is precisely one element, say $`z\overline{P}P_{<x}`$. Since $`Px`$ is LOT, $`z`$ must lie in $`\mathrm{max}\overline{P}`$. Let $`b=|\mathrm{max}\overline{P}|`$. Then we have

$$c(P)=c(\overline{P})+c(Pz;\mathrm{max}P)+c(Px;z,\mathrm{max}P)+c(P;x,z)$$
(30)
Because $`Pz`$ is LOT, we have that $`c(Pz;\mathrm{max}P)=\left(\genfrac{}{}{0pt}{}{m}{2}\right)(k1)`$, and because $`Px`$ is LOT we have that $`c(Px;z,\mathrm{max}P)=\left(\genfrac{}{}{0pt}{}{m1}{2}\right)`$. Notice that because $`P^{xy}`$ is $`𝒜_1𝒜_2`$-optimal, by the comment after the proof of Theorem 7.3, $`P^{xy}`$ is layered, and thus $`\overline{P}`$ is layered. Since the $`𝒜_1𝒜_2`$-patterns in $`P`$ containing both $`x`$ and $`z`$ are formed with exactly one element which lies in $`P_{<z}`$, $`c(P;x,z)=kb`$. Finally, $`c(P^{xy})=c(\overline{P})+\left(\genfrac{}{}{0pt}{}{m}{l}\right)k`$. Now combining all these $`c`$-values with equation (30) gives

$$c(P^{xy})c(P)=1=\left(\genfrac{}{}{0pt}{}{m}{2}\right)k\left(\genfrac{}{}{0pt}{}{m}{2}\right)(k1)\left(\genfrac{}{}{0pt}{}{m1}{2}\right)k+b,$$
(31)
so $`k+2=b+m`$. We have by Lemma 5.1 (iii) that $`m>k`$ and $`b>k/2`$ (this follows from the fact that $`\overline{P}`$ is layered and $`𝒜_1𝒜_2`$-optimal), which forces $`k3`$. This in turn implies $`|P|=k+m7`$. Now it can be checked by direct computation that for $`|P|`$ in this range either the theorem is true vacuously or one of (i) to (iii) holds. $`\mathrm{}`$

###### Theorem 7.10

If there is an $`n`$-poset $`P`$ with $`c_{Q_l}(P)=M_{n,Q_l}1`$ then there is an $`n`$-poset $`Q`$ with $`c_{Q_l}(Q)=M_{n,Q_l}1`$ and

1. if $`l>2`$ then $`Q`$ is layered, or
2. if $`l=2`$ then $`Q=Q_1Q_2`$ where $`|Q_1|5`$ and $`Q_2`$ is layered.

Furthermore, in either case $`Q=P_r𝒜_m`$ for some permutation $`rS_{nm}`$ and integer $`m`$ which is positive unless $`l=2`$ and $`n=5`$.

Proof: Induct on $`n`$. If $`n<l+1`$, then $`M_n=0`$, so the theorem is true vacuously. If $`n=l+1`$, then $`M_n=1`$ and $`c(𝒜_{l+1})=0=M_n1`$. Hence we may assume that $`n>l+1`$.

If case (ii) of Theorem 7.9 is true, let $`Q`$ be the poset guaranteed there, $`k=|\overline{Q}|`$ and $`m=|\mathrm{max}Q|=l`$. Then by Lemma 5.1 (iii), $`k<(k+m)/l<2m/m=2`$, so $`n=k+ml+1`$, a case we have already dealt with.

It is routine to check that the poset $`P_{15423}`$ satisfies case (ii) of this theorem if case (iii) of Theorem 7.9 is true.

Therefore we may assume that case (i) of Theorem 7.9 is true, and thus there is a LOT $`n`$-poset $`Q`$ so that $`c(Q)=M_n1`$. Since $`Q`$ is LOT, $`Q=\overline{Q}\mathrm{max}Q=\overline{Q}𝒜_m`$. As $`c(Q)=c(\overline{Q})+k\left(\genfrac{}{}{0pt}{}{m}{l}\right)`$, we must have $`c(\overline{Q})M_k1`$. If $`c(\overline{Q})=M_k`$, then by Theorem 3.1, there is some layered $`k`$-poset $`R`$ so that $`c(R)=M_k`$, and thus $`R𝒜_m`$ is layered, $`c(R𝒜_m)=M_n1`$ and $`R=P_r`$ for some $`rS_k`$. If $`c(\overline{Q})=M_k1`$, then by induction, there is some poset $`R`$, $`|R|=k`$, which satisfies this theorem. So $`R𝒜_m`$ is the desired poset. $`\mathrm{}`$

###### Theorem 7.11

For the pattern $`q=1(l+1)l\mathrm{}2`$, there are infinitely many IZ integers.

Proof: Assume that the theorem is false. Since $`S_6(M_61)=0`$ for $`l=2`$ and $`S_{l+2}(M_{l+2}1)=0`$ for $`l3`$, there must be some maximal $`kl+2`$ so that $`S_k(M_k1)=0`$. By Theorem 4.1, there is some $`n`$ so that $`k_{n2}=k1`$ and $`k_{n1}=k`$. Also note that since $`k_nk_{n1}=kl+2`$, by Lemma 5.1 (iii) we have $`n>lk_nl(l+2)>2l+2`$, so we may apply Lemma 6.4 to see that $`k_n=k`$.

By our choice of $`k`$, $`S_n(M_n1)0`$, so there is some $`pS_n`$ so that $`c(p)=M_n1`$. By Lemma 7.4, $`c(P_p)=M_n1`$, and thus Theorem 7.10 produces a poset $`Q=P_r𝒜_m`$ for some $`rS_{nm}`$ and integer $`m`$ which is positive since $`n>6`$.

Let $`\overline{k}=nm`$. By Theorem 3.1, there is a layered $`Q_l`$-optimal $`\overline{k}`$-poset $`R`$, and so we must have $`c(R𝒜_m)c(Q)`$. Therefore, by Lemma 7.4, we have $`c(R𝒜_m)=c_{n,\overline{k}}c(Q)=M_n1`$, and thus the inequality in Lemma 6.4 implies that $`\overline{k}=k`$. However, if $`\overline{k}=k`$ then we have $`c(r)=M_k1`$, contradicting our choice of $`k`$. $`\mathrm{}`$

Numerical evidence and the contrast between Proposition 2.1 and Theorem 2.2 amkes us suspect that Theorem 4.2 is not true for $`q=1(l+1)l\mathrm{}2`$, $`l3`$. In fact, we believe the following is true.

###### Conjecture 7.12

The frequency sequence for $`q=1(l+1)l\mathrm{}2`$, $`l3`$ has internal zeros for all $`nl+1`$.

It would be interesting to find a proof of this conjecture. Perhaps a first step would be to find a simpler proof of Theorem 7.11.

Acknowledgement. This paper was written, in part, when Bruce Sagan was resident at the Isaac Newton Institute for Mathematical Sciences. He would like to express his appreciation for the support of the Institute during this period.


format: text

text:
# Continuously-variable survival exponent for random walks with movable partial reflectors

## Abstract

We study a one-dimensional lattice random walk with an absorbing boundary at the origin and a movable partial reflector. On encountering the reflector, at site $`x`$, the walker is reflected (with probability $`r`$) to $`x1`$ and the reflector is simultaneously pushed to $`x+1`$. Iteration of the transition matrix, and asymptotic analysis of the probability generating function show that the critical exponent $`\delta `$ governing the survival probability varies continuously between 1/2 and 1 as $`r`$ varies between 0 and 1. Our study suggests a mechanism for nonuniversal kinetic critical behavior, observed in models with an infinite number of absorbing configurations.

Random walks find application in virtually every area of physics . Random walks in the presence of traps or absorbing boundaries, and/or reflectors, are much studied as models of exciton recombination , diffusion-limited reactions , and polymer-surface interactions .

In this Letter we study an unbiased random walk with an absorbing boundary at the origin, and a movable, partial reflector. At each encounter between walker and reflector, the latter moves one step to the right (i.e., to a site not yet visited by the walker), while the walker is reflected to its previous position with probability $`r`$. Thus the reflector hampers the advance of the walker into new territory, but does not otherwise influence its motion. (Note that in the limit $`r=0`$ the reflector has no effect, but it does mark the span of the walk.) We are primarily interested in the effect of the reflector on the asymptotic scaling properties of the walk.

The process defined above admits various physical interpretations. One is in terms of adlayer growth, with deposition and evaporation at the edge of the adlayer (but not in the bulk). The substrate adsorption sites are originally in a “non-activated” state, with a low sticking probability for incident molecules, but after a first adsorption attempt (at a step edge) the substrate site becomes activated, with a high sticking probability. Biological interpretations are also possible, e.g., of the advance of a bacterial colony in a growth medium, with a preliminary contact facilitating expansion into new regions, or, similarly, the spread of a political viewpoint in an initially skeptical population. Our results are of interest as an example of nonuniversality (a continuously-variable critical exponent) in a model that allows an exact asymptotic analysis.

A further motivation for our study is provided by absorbing-state phase transitions, an area of great current interest in nonequilibrium statistical physics , in which a many-particle system, such as directed percolation, becomes trapped in a configuration allowing no further evolution. Continuous transitions to an absorbing state have been invoked in models of epidemics , catalysis , and the transition to turbulence , to cite but a few examples. The connection between absorbing-state phase transitions and random walks lies in compact directed percolation (CDP) . CDP is defined on a discrete space-time $`(x,t)`$ with time-slices corresponding to diagonals of a square lattice, so that the neighbors of site $`(x,t)`$ at the previous time are $`(x1,t1)`$ and $`(x+1,t1)`$. Each site is either occupied or vacant. If $`(x,t1)`$ has $`n`$ occupied neighbors, then $`(x,t)`$ is vacant (occupied) with probability 1 if $`n=0`$ (2), and is occupied with probability $`p`$ if $`n=1`$. CDP exhibits an absorbing-state phase transition at $`p=1/2`$. Consider an initial state of a single occupied site in an otherwise empty lattice. The boundaries between the occupied region (descended from the initial seed particle) and the outer vacant regions follow simple random walks, which are unbiased if $`p=1/2`$. Thus the length $`X(t)`$ of the occupied region, being the distance between two random walks, is also a random walk, with an absorbing boundary at the origin. For $`p<1/2`$ ($`>1/2`$) $`X(t)`$ is attracted to (repelled by) the origin. For $`p=1/2`$, $`X(t)`$ is unbiased, and well known results for random walks  imply that the survival probability decays for long times $`t^\delta `$, with $`\delta =1/2`$.

The motivation for introducing mobile reflectors in CDP (and thus in the simple random walk studied here) arises from the puzzling behavior of models that can become trapped in one of an infinite number of absorbing configurations (INAC) . Anomalies in critical spreading for INAC, such as continuously variable critical exponents, have been traced to a long memory in the dynamics of the order parameter, $`\rho `$, due to coupling to an auxiliary field that remains frozen in regions where $`\rho =0`$ . INAC appears to be particularly relevant to the transition to spatio-temporal chaos, as shown in a recent study of a coupled-map lattice with ‘laminar’ and ‘turbulent’ states, which revealed continuously-variable spreading exponents .

Grassberger, Chaté and Rousseau (GCR)  proposed that spreading in systems with INAC could be understood by studying a model with a unique absorbing configuration, but in which the spread of activity to previously inactive regions is hampered (or facilitated). Our model represents a two-fold simplification of the GCR model: first, the appearance of inactive sites within a string of active ones is prohibited (analogous to going from DP to the more restrictive CDP process); second, we study a single random walker rather than the pair needed to describe CDP . We believe, nonetheless, that our model captures the essential physics underlying anomalous critical behavior in models with INAC.

We study an unbiased, discrete-time random walk on the nonnegative integers, $`x_t=0,1,2,\mathrm{}`$, with $`x=0`$ absorbing. Initially the walker is at $`x_0=1`$ and the reflector, whose position we denote by $`R_t`$, is at $`R_0=2`$. Each time the walker steps to the site occupied by the reflector, it is reflected back to $`R1`$ with probability $`r`$ (and remains at $`R`$ with probability $`1r`$), while the reflector moves (with probability 1) to $`R+1`$. Evidently the process $`x_t`$ is non-Markovian, since the transition probability into a given site depends on whether it has been visited before. We can transform the model to a Markov process by enlarging the state space to include the reflector position; it is convenient to introduce the variable $`y_t=R_t1`$ for this purpose. The process $`(x,y)`$ is restricted to the wedge between $`x=0`$ (absorbing) and $`x=y`$, with transitions from $`y`$ to $`y+1`$ allowed only from the diagonal $`x=y`$. At this point it is useful to include a further generalization of our model, by assigning a probability $`p^{}`$ for the walker to jump to the right (and $`q^{}=1p^{}`$ to jump to the left) when on the diagonal; these transition probabilities are summarized in Fig. 1. For $`p^{}<1/2`$ the walker experiences an additional impediment to visiting new territory, while for $`p^{}(1r)>1/2`$ the ‘reflector’ effectively becomes an accelerator, drawing the walker forward to a previously unvisited site.

The nonzero transition probabilities for the Markov chain are:

$`W[(x,y)(x\pm 1,y)]`$ $`=`$ $`1/2,x=1,\mathrm{},y1`$ (1)
$`W[(y,y)(y,y+1)]`$ $`=`$ $`p^{}r`$ (2)
$`W[(y,y)(y+1,y+1)]`$ $`=`$ $`p^{}(1r)`$ (3)
$`W[(y,y)(y1,y)]`$ $`=`$ $`1p^{}.`$ (4)
The probability $`P(x,y,t)`$ follows the master equation

$$P(x,y,t+1)=\frac{1}{2}P(x1,y,t)+\frac{1}{2}P(x+1,y,t),x=1,2,\mathrm{},y2;y3,$$
(5)
with $`P(0,y,t)=0`$, representing the absorbing boundary at $`x=0`$. Letting $`D(y,t)P(y,y,t)`$, the boundary conditions along the diagonal are:

$`P(y1,y,t+1)={\displaystyle \frac{1}{2}}P(y2,y,t)+p^{}rD(y1,t)+(1p^{})D(y,t),`$ (6)
$`D(y,t+1)={\displaystyle \frac{1}{2}}P(y1,y,t)+p^{}(1r)D(y1,t),`$ (7)
for $`y3`$. For $`y=1`$, 2 the evolution equations depend on the initial condition; here $`P(x,y,0)=\delta _{x,1}\delta _{y,1}`$ .

Define the generating function $`\widehat{P}(x,y,z)=_{t=0}^{\mathrm{}}z^tP(x,y,t)`$ (and similarly for $`D`$, etc.). $`\widehat{P}`$ satisfies

$$z^1\widehat{P}(x,y)=\frac{1}{2}\widehat{P}(x1,y)+\frac{1}{2}\widehat{P}(x+1,y),x=1,2,\mathrm{},y2;y3.$$
(8)
(we drop the argument $`z`$ for brevity), subject to the boundary conditions

$`\widehat{P}(0,y)=0,`$ (9)
$`z^1\widehat{P}(y1,y)={\displaystyle \frac{1}{2}}\widehat{P}(y2,y)+p^{}r\widehat{D}(y1)+(1p^{})\widehat{D}(y),`$ (10)
$`z^1\widehat{D}(y)={\displaystyle \frac{1}{2}}\widehat{P}(y1,y)+p^{}(1r)\widehat{D}(y1).`$ (11)
The solution of Eqs. (8) and (9) is

$$\widehat{P}(x,y)=\widehat{C}(y)(\lambda _+^x\lambda _{}^x);\lambda _\pm =z^1\pm \sqrt{z^21},$$
(12)
with $`\widehat{C}(y)`$ yet to be determined. Noting that $`\lambda _+=\lambda _{}^1\lambda `$, we define $`\lambda (x)\lambda ^x\lambda ^x`$; thus $`\widehat{P}(x,y)=\widehat{C}(y)\lambda (x)`$. Note also the recurrence relation for integer $`x`$: $`\lambda (x1)2z^1\lambda (x)+\lambda (x+1)=0`$.

¿From Eq. (11) we find

$$\widehat{D}(y)=\omega ^{y2}\widehat{D}(2)+\frac{1}{2}z\omega ^y\underset{y^{}=3}{\overset{y}{}}\omega ^y^{}\widehat{P}(y^{}1,y^{}),\omega =p^{}(1r)z.$$
(13)
It follows that $`\widehat{D}(y)\omega \widehat{D}(y1)=\frac{z}{2}\widehat{C}(y)\lambda (y1)`$. Therefore, subtracting from Eq. (10) $`\omega `$ times the corresponding equation for $`y1`$, and using the recursion relation for $`\lambda (x)`$, we find

$$\frac{\widehat{C}(y)}{\widehat{C}(y1)}=p^{}\frac{r\lambda (y2)+(1r)\lambda (y1)}{(p^{}\frac{1}{2})\lambda (y1)+\frac{1}{2}\lambda (y+1)},$$
(14)
which, noting that $`\widehat{C}(2)=\widehat{P}(1,2)/\lambda (1)`$, provides the complete solution for the probability generating function.

To determine the survival probability $`S(t)=_{y=0}^{\mathrm{}}_{x=0}^yP(x,y,t)`$ as $`t\mathrm{}`$, we analyze the singular behavior of $`\widehat{S}(z)`$ as $`z1`$. In this limit $`\lambda =1+\sqrt{2ϵ}+𝒪(ϵ)`$, where $`ϵ=1z`$, and we find the dominant term to be

$$\widehat{S}\frac{1}{\sqrt{2(1z)}}\underset{y=3}{\overset{\mathrm{}}{}}\widehat{C}(y)[\lambda (y/2)]^2,$$
(15)
which converges for $`z<1`$. Note that $`\lambda (n)2n\sqrt{2ϵ}`$ for $`nϵ1`$, while in the opposite limit $`\lambda (n)\lambda ^n`$. For $`nϵ1`$ we may thus use the $`z1`$ limiting expression for $`\widehat{C}(n)`$, that is,

$$\widehat{C}_0(y)=\frac{\widehat{P}(1,2)}{2\sqrt{2(1z)}}\frac{\mathrm{\Gamma }(2+1/p^{})}{\mathrm{\Gamma }(2r)}\frac{\mathrm{\Gamma }(yr)}{\mathrm{\Gamma }(y+1/p^{})}.$$
(16)
We then approximate the summand in Eq. (15) by

$$f_n=\{\begin{array}{cc}2n^2\widehat{C}_0(n)ϵ,\hfill & nϵ1,\hfill \\ 2N^2\widehat{C}_0(N)ϵa^{nN}\lambda ^{nN},\hfill & nϵ>1,\hfill \end{array}$$
(17)
where $`N=1/\sqrt{ϵ}`$ rounded to an integer, and

$$a=p^{}\frac{r+(1r)\lambda }{(p^{}1/2)\lambda +(1/2)\lambda ^3}.$$
(18)
Since $`\widehat{S}`$ and $`F(z)_{n=0}^{\mathrm{}}f_n`$ have the same radius of convergence and $`lim_n\mathrm{}\widehat{C}(n)[\lambda (n/2)]^2/f_n`$ is finite, an Abelian theorem implies that the singular behavior of $`\widehat{S}`$ is the same as that of $`F(z)/\sqrt{ϵ}`$ . Write $`F(z)/\sqrt{ϵ}=2ϵ^{1/2}_{n=0}^Nn^2\widehat{C}_0(n)+2ϵ^{1/2}N^2\widehat{C}_0(N)_{n=N+1}^{\mathrm{}}(\lambda a)^{nN}`$. We approximate the first sum by an integral; using $`\widehat{C}_0(n)ϵ^{1/2}n^{r1/p^{}}`$ we then find that the first term $`ϵ^{(r+1/p^{}3)/2}`$. The same holds for the second term when we note that $`1a\lambda ϵ^{1/2}`$ and $`\widehat{C}_0(N)ϵ^{\frac{1}{2}(1+r+1/p^{})}`$. Thus $`\widehat{S}(1z)^{\delta 1}`$ (plus less singular terms) as $`z1`$, where $`\delta =(r+1/p^{}1)/2`$. Finally, noting that for large $`n`$, the coefficient of $`z^n`$ in $`(1z)^{\delta 1}`$ is $`n^\delta /\mathrm{\Gamma }(1\delta )`$, we have that the survival probability decays asymptotically $`t^\delta `$; in particular, for $`p^{}=1/2`$ we have $`S(t)t^{(1+r)/2}`$. Note also that the larger $`p^{}`$ is, the slower the decay of the survival probability, as expected.

While the amplitude of the leading term in $`S(t)`$ can be evaluated exactly for $`p^{}=1/2`$ and $`r=0`$ or 1 , we have not found a closed-form expression in the general case. Numerical evaluation of the exact expression for $`\widehat{S}`$ does, however, lead to an amplitude in perfect agreement with that found in the transition matrix analysis.

We turn now to results obtained via numerical iteration of the transition matrix defined in Eq. (4). We studied the process to a maximum time of up to $`3\times 10^5`$, quite sufficient to observe asymptotic behavior. In Fig. 2 we show the survival probability for $`p^{}=1/2`$ and various values of $`r`$. In each case there is a power-law decay, with the decay exponent $`\delta `$ varying continuously with $`r`$. (The plateaus in $`S(t)`$ at short times reflect that for $`r=0`$ the walker can only reach the origin on odd-numbered steps. Similarly, for $`r=1`$ the walker cannot reach the origin on the third step.) We verify that the mean position $`x_tt^{1/2}`$ (and that $`x_t^2t`$; the averages are over surviving walks) independent of $`r`$. The amplitudes for the displacement and its second moment do decrease with increasing $`r`$.

To determine the decay exponent precisely, we study the local slope $`\delta (t)`$, given by a least-squares linear fit to the $`\mathrm{ln}S`$ data for a set of 11 equally-spaced values (increments of 0.05) of $`\mathrm{ln}t`$. Plots of $`\delta (t)`$ vs. $`t^1`$ lead to asymptotic ($`t\mathrm{}`$) values confirming $`\delta =(1+r)/2`$ to better than one part in 2000. It is possible to improve the analysis further by determining the leading correction to scaling in an expansion of the form: $`S(t)At^\delta [1Bt^{\mathrm{\Delta }_1}+\mathrm{}]`$. For $`r=0`$ we find $`A=0.7979`$, $`B=0.78`$ and $`\mathrm{\Delta }_1=1.00`$, in accord with the exact expansion $`P(t)\sqrt{2/(\pi t)}[1(3/4)t^1+\mathrm{}]`$. For $`r=1`$ our data yield $`A=1.0000`$ (in agreement with the exact result), $`B=1.332`$ and $`\mathrm{\Delta }_1=1.00`$. In these two cases, plotting $`\delta (t)`$ versus $`t^{\mathrm{\Delta }_1}=t^1`$ we obtain $`\delta =0.5000.`$ and 0.999985, respectively. For $`r`$ in the interval \[0.1,0.8\] we find a much smaller correction to scaling exponent, $`\mathrm{\Delta }_10.54`$, while for $`r=0.9`$, $`\mathrm{\Delta }_10.62`$. Plotting $`\delta (t)`$ versus $`t^{\mathrm{\Delta }_1}`$ (see Fig. 3), we obtain exponents that agree with the theoretical value to better than one part in $`2\times 10^4`$. The attractive simplification, $`\mathrm{\Delta }_1=1/2`$ for $`r0`$, 1, yields essentially the same values for $`\delta `$, and is in fact to be expected, given that generic corrections to $`\widehat{S}`$ should be $`(1z)^{\delta 1+\frac{1}{2}m}`$ $`(m=1,2,\mathrm{})`$.

The case of compact directed percolation is somewhat more complicated than the random walk problem analyzed above, as we must now keep track of three variables, viz., the distance $`X`$ between the two walkers, and the respective distances between the walkers and the associated reflectors . Simulation results for CDP with movable partial reflectors again show $`\delta `$ varying continuously with $`r`$, but over a somewhat wider range: for $`r=1`$, $`\delta =1.158(3)`$.

In one-dimensional spreading models (contact process , pair contact process , etc.) the survival and spread of activity may again be described in terms of the position of two points that bound the active region, as in CDP. But here the boundaries of the active region do not follow simple random walks: their dynamics involves a variable step size (due to gaps in the distribution of active sites), and a significant memory (the step-size distribution depends on the history of the previous step directions). It seems reasonable, nevertheless, to expect that varying the probability for advancing into virgin territory will change the scaling of the survival probability, just as observed here. A detailed investigation of this issue is a high priority for future work.

In summary, we have uncovered the rather remarkable property of a continuously varying critical exponent governing the survival probability of a random walk with an absorbing boundary, in the presence of a movable partial reflector. Our results suggest a new approach to understanding nonuniversal spreading in models with an infinite number of absorbing configurations.

###### Acknowledgements.

We thank L. S. Schulman for stimulating discussions. R.D. is supported by CNPq. D.b.-A. thanks the NSF (PHY-9820569) for support.

electronic address: dickman@cedro.fisica.ufmg.br
electronic address: benavraham@clarkson.edu

Figure Captions

FIG. 1. Transition probabilities in the (x,y) plane.

FIG. 2. Survival probability versus time for random walk with a movable partial reflector, $`p^{}=1/2`$. Reflection probability (top to bottom) $`r=0,0.1,\mathrm{},1`$.

FIG. 3. Local slope $`\delta (t)`$ for $`p^{}=r=1/2`$. The inset shows the same data plotted versus $`1/t`$.


text:
# Self-similarity and novel sample-length-dependence of conductance in quasiperiodic lateral magnetic superlattices

## I Introduction

The discovery of quasicrystals in 1984  has attracted a great amount of experimental and theoretical attention to quasiperiodic systems. It has been shown that a 1D quasiperiodic array of electric barriers is characterized by its self-similar energy spectrum and critical (neither extended nor localized) states. Recent advances in semiconductor and nano-technologies have permitted the realization of a uniform magnetic field at nanometer scales, by creating magnetic dots or depositing ferromagnetic or superconducting material patterns on heterostructures . The energy spectrum and transport properties of a two-dimensional electron gas (2DEG) modulated by a regular array of nanoscale magnetic field inhomogeneities have been investigated both theoretically and experimentally .

In this paper we discuss electron motion in a 2DEG subject to the field of a nearby quasiperiodic array of parallel magnetic stripes. This case differs from electric or dielectric modulation in that 2DEG electron tunneling through magnetic barriers is inherently a two-dimensional process . The effective potential experienced by the electron is dependent on the wave vector perpendicular to the tunneling direction. As we show below, since for a quasiperiodic magnetic pattern this potential is still quasiperiodic for any given transverse wavevector, both the transmission and conductance display quasiperiodic properties. Our main finding, however, is that the presence of extended states somewhere in the spectrum produces a residual conductivity at infinite length, which is lost as the incident energy decreases, much in the manner of a metal-insulator transition.

## II Formulaton

We consider a $`2DEG`$ under an inhomogeneous perpendicular magnetic field produced by two types of magnetic blocks $`P`$ and $`Q`$ arranged in a Fibonacci sequence (Fig. 1 (a)). The magnetic field is assumed to be uniform along the $`y`$ direction and to vary along the $`x`$ direction. Throughout this work we use the Landau gauge $`𝐀=(0,A(x),0)`$. For magnetic block $`P/Q`$ of width $`L_{P/Q}=d_{P/Q}+l_{P/Q}`$, we assume for simplicity a magnetic profile $`B(x)=B_{P/Q}l_B[\delta (x)\delta (xd_{P/Q})]`$ (Fig. 1 (b)). Its corresponding vector potential can be chosen as $`A(x)=B_{P/Q}l_B[\theta (x)\theta (xd_{P/Q})]`$ (Fig. 1 (c)), where $`l_B=\sqrt{\mathrm{}/eB_P}`$ and $`\theta (x)`$ is the Heaviside step function. By introducing in addition the cyclotron frequency $`\omega _c=eB_P/m^{}`$ ($`m^{}`$ is the effective mass of electrons), all quantities below are transformed into dimensionless units. For $`GaAs`$ and an estimated $`B_P=0.1T`$, then $`l_B=81.3nm`$, $`\mathrm{}\omega _c=0.17mev`$ and $`l_B\omega _c=1.4m/sec`$. Writing the wavefunction in the form $`e^{iqy}\psi (x)`$ ($`q`$ is the wavenumber associated with the spatial degree of freedom in the direction of the stripes), one obtains the following $`1D`$ Schrödinger equation governing the motion of $`2DEG`$ electrons in the presence of the magnetic modulation,

$$\{\frac{d^2}{dx^2}f_j(x)[f_j(x)+2q]\}\psi (x)=2(q^2/2E)\psi (x).$$
(1)
Here $`f_j(x)`$ is an oscillating function arising from the Fibonacci sequence $`S_j`$ constructed from the vector potentials $`A_P`$ and $`A_Q`$, and $`V(x,q)=f_j(x)[f_j(x)+2q]/2`$ can be considered as an effective q-dependent potential for motion along the tunneling direction. The dependence on $`q`$ of the quantity $`V(x,q)`$ implies that this problem is inherently two dimensional. Here and in what follows, we assume $`B_PB_Q`$. Then, in the units chosen, the function $`f_j(x)`$ is a sequence of barriers of height $`r=B_Q/B_P1`$. For a given $`q`$, electron tunneling through the magnetic structure will be equivalent to electron motion in a $`1D`$ Fibonacci electric potential with square barriers ($`qr/2`$), square barriers and wells ($`1/2<q<r/2`$), or square wells ($`q1/2`$).

Matching wave functions at the edges of the magnetic block $`Q`$ yields the following transfer matrix $`M_Q`$ for an electron propagating through such block,

$$M_Q=\left(\begin{array}{cc}[\mathrm{cos}(k_Qd_Q)i\mu _Q^+\mathrm{sin}(k_Qd_Q)]e^{ik_0l_Q}& i\mu _Q^{}\mathrm{sin}(k_Qd_Q)e^{ik_0l_Q}\\ \\ i\mu _Q^{}\mathrm{sin}(k_Qd_Q)e^{ik_0l_Q}& [\mathrm{cos}(k_Qd_Q)+i\mu _Q^+\mathrm{sin}(k_Qd_Q)]e^{ik_0l_Q}\end{array}\right),$$
(2)
where $`k_Q=\sqrt{2Eq^2r(r+2q)}`$, $`k_0=\sqrt{2Eq^2}`$, and $`\mu _Q^\pm =\frac{1}{2}(k_Q/k_0\pm k_0/k_Q)`$, The transfer matrix $`M_P`$ can be obtained by the replacements $`QP`$ and $`r1`$ in the above Eq.(2).

A Fibonacci multilayer system $`S_j`$ has $`F_j`$ layers, where $`F_j`$ is a Fibonacci number satisfying the recursion relation $`F_{j+1}=F_j+F_{j1}`$ $`(j1)`$, with $`F_0=F_1=1`$. Then $`M_{j+1}=M_jM_{j1}`$ $`(j1)`$, with initial condition $`M_0=M_Q`$, $`M_1=M_P`$, which yields a trace map $`x_{j+1}=2x_jx_{j1}x_{j2}`$ and a constant of motion $`I=x_{j+1}^2+x_j^2+x_{j1}^22x_{j+1}x_jx_{j1}1`$ , where $`x_j=TrM_j/2`$. The constant of motion $`I`$ characterizes the extent of quasiperiodicity of the Fibonacci system.

Now we consider a simple case, i.e., $`r=1`$, $`d_P=d_Q=d`$, which is likely to be the easiest to realize experimentally. Then one has $`k_P=k_Q=k`$ and the constant of motion

$$I=\{(k^2k_0^2)\mathrm{sin}(kd)\mathrm{sin}[k_0(l_Ql_P)]/2kk_0\}^2.$$
(3)
For the case $`l_P=l_Q`$, $`I=0`$, which corresponds to a purely periodic magnetic superlattice. According to Eq. (3) $`I`$ is also dependent on the normal wavevector $`q`$ through $`k_0`$ and $`k`$. It is in general positive definite for most incident energies $`E`$ if $`l_Pl_Q`$. One thus expects the quasiperiodic self-similarity to appear in the energy spectra, transmission and, possibly, the conductance. In terms of the matrix $`M_j`$ the transmission coefficient becomes

$$T(E,q)=4/[Tr(M_j^tM_j)+2],$$
(4)
where the superscript $`t`$ denotes the transpose of a matrix. The conductance $`g`$ is calculated from the Landauer-Büttiker formula  by averaging the electron flow over half the Fermi surface,

$$g=_{\pi /2}^{\pi /2}T(E,\sqrt{2E}\mathrm{sin}\theta )\mathrm{cos}\theta d\theta .$$
(5)
Here $`\theta `$ is the angle between the velocity of incidence and the tunneling axis $`x`$, $`E`$ is the incident energy, and the conductance is expressed in units of the quantity $`e^2m^{}vl_y/\mathrm{}^2`$, where $`v`$ is the velocity of the incident electrons and $`l_y`$ the width of the sample.

## III Results and discussion

We show in figure 2 typical transmission spectra for different transverse wavenumbers and Fibonacci sequences $`S_9,S_{12}`$ and $`S_{15}`$. The magnetic structure parameters are chosen as $`r=1,d_P=d_Q=1,l_P=1,l_Q=2`$. From the left to the right column, $`q`$ is $`0.7`$, $`0.0`$ and $`0.7`$, which corresponds to the equivalent Fibonacci electric superlattices constructed from two square-well, two low square-barrier and two high square-barrier blocks, respectively. From the top to bottom row the transmission spectra are for $`S_9,S_{12}`$ and $`S_{15}`$. respectively. As clearly shown in figure 2, the transmission spectra for $`S_9,S_{12}`$ and $`S_{15}`$ are self-similar, i.e., the transmission peak clusters and the transmission gaps for different Fibonacci sequences are arranged in a very similar way , regardless of the value of the transverse wave-number $`q`$. In fact, the self-similar transmission spectra are the refection of the self-similarity in the corresponding energy spectra (not shown).

Figure 3 illustrates the self-similarity of the transmission spectra more clearly. The first and second rows show that, regardless of the value of $`q`$, the transmission bands are tribranching hierarchically in a self-similar way. It is the self-similarity between the whole and the local spectra. Also one can readily observe the similarity between the transmission spectra of $`S_{12}`$ and $`S_{15}`$ at quite different scales. The third column shows in more detail this scaling property at $`q=0`$ as the length is increased. We notice in this data that the evolving structure has a six-circle symmetry, arising from the property $`M_{j+6}=M_j`$. In fact, the scale change of the incident energy $`E`$ between the spectra for $`S_9`$, $`S_{12}`$ and $`S_{15}`$ is given by the scaling index of the renormalization group transformation of the six-circle map $`[1+4(1+I)^2]^{1/2}+2(1+I)`$ . The self-similarities of the transmission spectra arise from the self-similar energy spectra (not shown) of this special structure. Close inspection of the data in the third column shows in addition that there are states with transmission coefficient equal to unity, that persist as the length is increased (arrows in the figure) . These exotic extended states play a crucial role in the unusual length dependence of the conductance described below.

Numerical results for the conductance for structures $`S_9`$, $`S_{12}`$ and $`S_{15}`$ are shown in Fig. 4. The first column shows the development of further fine structure each time the Fibonacci number increases, keeping the position of the main dips at each step roughly unchanged. Although according to (5) the conductance is an average of transmission coefficients over half the Fermi surface, self-similarity is still present, as made evident in the next two columns. In the center column we repeat the central panel of the first column in order to show how a change of scale produces a similar spectra in $`S_{12}`$, while an increase in length ($`S_{15}`$) gives more detailed structure, also similar to the whole pattern. The column in the right illustrates the six-circle scaling property of the conductance.

Close inspection of Fig. 4 also shows that as the length of the sample increases, the conductance decreases. To find out what governs this behavior we have calculated the conductance at incident energies $`E=0.125,0.30,0.45`$ and $`0.60`$ for different sample lengths $`l_x`$, and plotted them in the upper ($`r=0.5`$) and bottom panels ($`r=1.0`$) of Fig. 5. We find that in all cases the conductance dependence in $`l_x`$ is bounded from below by a power law decrease . In order to investigate the possibility of a residual conductivity at infinite length, we include in the figures a fit using the function $`g=g_0e^{\beta l_x^\alpha }g_0(1+\beta l_x^\alpha )`$. We notice that in the upper panels the residual conductivity $`g_0`$ rises abruptly by four orders of magnitude when increasing the energy from $`.30`$ to $`.45`$. Closer study of this range shows that the rise occurs between $`.43`$ and $`.45`$. We interpret the change as the capturing of one or more conducting channels by the convolution (5), arising possibly from exotic extended states. The bottom panels, showing the special case $`r=1`$, permit a check of this ansatz. Since the conductance is a convolution over a range of wavenumbers $`q`$, if at a particular value of this quantity an extended state is present, it will contribute to transport at infinite length. As may be easily checked, when $`r=1`$ the effective potential in Eq. 2 vanishes everywhere at wavenumber $`q_c=1/2`$, a state captured by the convolution (2) at energies $`E>0.125`$. The bottom panels show that a drop by several orders of magnitude occurs when this energy is approached from above, confirming that the loss of an extended state is indeed reflected in a large change in the conductance.

This novel behavior is different from either the usual $`1D`$  or the $`2D`$  Fibonaci systems. We attribute it as a manifestation of the presence of exotic extended states within the spectrum of a Fibonacci structure. Since the conductance is a convolution over a range of wavenumbers $`q`$, if at a particular value of this quantity an extended state is present, it will contribute to transport at infinite length. When such conducting channels are present, one may write $`gg_0+g_c`$, exhibiting the contributions from the critical and the extended states. Since $`g_0`$ has no dependence on $`l_x`$ and $`g_cg_\alpha l_x^\alpha `$ , the conductance $`g`$ may be approximated by the function $`g_0e^{\beta l_x^\alpha }`$, where $`\beta g_\alpha /g_0`$. It can be expected $`\beta >1`$ due to the predominant weight of the critical channels.

The self-similarities and the length-dependence of the transmission and conductance of a Fibonacci magnetic superlattice reported above are robust with regard to changes in the particular shape of the magnetic barriers, and the choice of vector potential . This makes an experimental verification of the properties found very plausible. As our results suggest, a 2DEG subject to the inhomogeneous magnetic field of a Fibonacci or other quasiperiodic sequence of magnetic stripes deposited on a nearby parallel surface should exhibit self-similarity and an unusual length-dependence in the conductance perpendicular to the stripes. Extended states along the direction perpendicular to the stripes may contribute or not to the bulk conductance depending on the energy of the incoming electrons. A possible experimental test of this finding is to measure the conductance as the Fermi energy is varied by means of a gate voltage. The loss of extended states within the energy range available for transport would reveal a drop akin to a metal-insulator transition.

## IV conclusion

In summary, we have discussed the quasiperiodic behavior of electrons in a Fibonaci lateral magnetic superlattice. We have shown that its transmission and conductance possess both the self-similarity and six-circle properties found in other kinds of quasiperiodic systems. Moreover, novel scaling properties of conductance with respect to the sample size in the tunneling direction have been found, exhibiting the presence of exotic extended states.

###### Acknowledgements.

This work was supported in part by a Cátedra Presidencial en Ciencias and FONDECYT 1990425 (Chile), and NSF grant No. 53112-0810 of Hunan Normal University (China). We are indebted to J. Bellissard for useful comments and suggestions relating to our results. Discussions with W. Yan and L. D. Zhang and communications with F.M. Peeters and M. Büttiker are also acknowledged.