text:
# Theorem 2.1

ON THE DIAGRAM OF SCHRÖDER PERMUTATIONS
Astrid Reifegerste

Institut für Algebra und Geometrie

Otto-von-Guericke-Universität Magdeburg

Postfach 4120, D-39016 Magdeburg, Germany

astrid.reifegerste@mathematik.uni-magdeburg.de
September 17, 2002

Abstract. Egge and Mansour have recently studied permutations which avoid $`1243`$ and $`2143`$ regarding the occurrence of certain additional patterns. Some of the open questions related to their work can easily be answered by using permutation diagrams. Like for $`132`$-avoiding permutations the diagram approach gives insights into the structure of $`\{1243,2143\}`$-avoiding permutations that yield simple proofs for some enumerative results concerning forbidden patterns in such permutations.

1 Introduction

Let $`𝒮_n`$ be the set of all permutations of $`\{1,\mathrm{},n\}`$. Given a permutation $`\pi =\pi _1\mathrm{}\pi _n𝒮_n`$ and a permutation $`\tau =\tau _1\mathrm{}\tau _k𝒮_k`$, we say that $`\pi `$ contains the pattern $`\tau `$ if there is a sequence $`1i_1<i_2<\mathrm{}<i_kn`$ such that the elements $`\pi _{i_1}\pi _{i_2}\mathrm{}\pi _{i_k}`$ are in the same relative order as $`\tau _1\tau _2\mathrm{}\tau _k`$. Otherwise, $`\pi `$ avoids the pattern $`\tau `$, or alternatively, $`\pi `$ is $`\tau `$-avoiding. The set of $`\tau `$-avoiding permutations in $`𝒮_n`$ is denoted by $`𝒮_n(\tau )`$. For an arbitrary finite collection $`T`$ of patterns we write $`𝒮_n(T)`$ to denote the permutations of $`\{1,\mathrm{},n\}`$ which avoid each pattern in $`T`$.
Egge and Mansour  studied permutations which avoid both $`1243`$ and $`2143`$. This work was motivated by the parallels to $`132`$-avoiding permutations. In \[7, Lem. 2 and Cor. 9\] was shown that the number of elements of $`𝒮_n(1243,2143)`$ is counted by the $`(n1)`$st Schröder number $`r_{n1}`$. The (large) Schröder numbers may be defined by

$$r_0:=1,r_n:=r_{n1}+\underset{i=0}{\overset{n1}{}}r_ir_{n1i}\text{for }n1.$$

For this reason the authors of  called the permutations which avoid $`1243`$ and $`2143`$ Schröder permutations; we will do this as well. (The reference to Schröder numbers may be somewhat inexact because there are ten inequivalent pairs $`(\tau _1,\tau _2)𝒮_4^2`$ for which $`|𝒮_n(\tau _1,\tau _2)|=r_{n1}`$, see \[7, Theo. 3\]. However, it is sufficient for our purposes.)

Schröder permutations are known to have a lot of properties which are analogous to properties of $`132`$-avoiding permutations. Why it needs to be so, a look at their diagrams shows.
Given a permutation $`\pi 𝒮_n`$, we obtain its diagram $`D(\pi )`$ as follows: first let $`\pi `$ be represented by an $`n\times n`$-array with a dot in each of the squares $`(i,\pi _i)`$. Shadow all squares due south or due east of some dot and the dotted cell itself. The diagram $`D(\pi )`$ is defined as the region left unshaded after this procedure. A square that belongs to $`D(\pi )`$ we call a diagram square; a row (column) of the array that contains a diagram square is called a diagram row (diagram column). (The diagram is an important tool in the theory on the Schubert polynomial of a permutation. Schubert polynomials were extensively developed by Lascoux and Schützenberger. See  for a treatment of this work.)
By the construction, each of the connected components of $`D(\pi )`$ is a Young diagram. Their corners are defined to be the elements of the essential set $`(\pi )`$ of the permutation $`\pi `$. In , Fulton introduced this set which together with a rank function was used as a tool for algebraic treatment of Schubert polynomials. For any element $`(i,j)(\pi )`$, its rank is defined to be the number of dots northwest of $`(i,j)`$, and is denoted by $`\rho (i,j)`$. Furthermore, by $`_r(\pi )`$ we denote the set of all elements of $`(\pi )`$ whose rank equals $`r`$.
It is clear from the construction that the number of dots in the northwest is the same for all diagram squares which are connected. Consequently, we can extend the rank function on the diagram squares. It is a fundamental property of the ranked essential set of a permutation $`\pi `$, that it uniquely determines $`\pi `$. (This result was first proved by Fulton, see \[5, Lem. 3.10b\]; alternatively, an algorithm for retrieving the permutation from its ranked essential set was provided in .)
Answering a question of Fulton, Eriksson and Linusson gave in  a characterization of all ranked sets of squares that arise as ranked essential set of a permutation.
To recover a permutation from its diagram is trivial: row by row, put a dot in the leftmost shaded square such that there is exactly one dot in each column.
The concept should be clear from Figure 1.

Figure 1 Diagram and ranked essential set of $`\pi =\mathrm{9\hspace{0.25em}4\hspace{0.25em}8\hspace{0.25em}10\hspace{0.25em}3\hspace{0.25em}1\hspace{0.25em}7\hspace{0.25em}6\hspace{0.25em}2\hspace{0.25em}5}𝒮_{10}`$.

In , we used permutation diagrams to give combinatorial proofs for some enumerative results concerning forbidden subsequences in $`132`$-avoiding permutations. Now we develop analogues of these bijections. In particular, we will discuss some open problems which have been raised in .
The following section begins with a characterization of Schröder permutation diagrams. Then we will give a surjection that takes any Schröder permutation to a $`132`$-avoiding permutation of the same inversion number. On the other hand, a simple way to generate all Schröder permutation diagrams from those corresponding to $`132`$-avoiding permutations is described.
Section 3 deals with additional restrictions of Schröder permutations. As it was done for $`132`$-avoiding permutations we will characterize from the diagram the occurrence of increasing and decreasing subsequences of prescribed length, as well as of some modifications. This yields simple combinatorial proofs for some results appearing in .
In the same reference a bijection between Schröder permutations and lattice paths was given. Section 4 shows how the path can immediately be obtained from the diagram of the corresponding permutation.
The paper ends with some remarks about potential generalizations of its results.

2 A description of Schröder permutation diagrams

By \[9, Theo. 2.2\], $`132`$-avoiding permutations are precisely those permutations for which the diagram corresponds to a partition, or equivalently, for which the rank of every element of the essential set equals $`0`$. Analogously, we can characterize the elements of $`𝒮_n(1243,2143)`$.

###### Theorem 2.1

A permutation $`\pi 𝒮_n`$ is a Schröder permutation if and only if every element of its essential set is of rank at most $`1`$.

Proof. If there exists an element $`(i,j)(\pi )`$ (or equivalently, any diagram square $`(i,j)`$) with $`\rho (i,j)2`$ then, by definition, at least two dots appear in the northwest of $`(i,j)`$, say in the rows $`i_1<i_2`$. Obviously, the subsequence $`\pi _{i_1}\pi _{i_2}\pi _i\pi _{i_3}`$ is of type $`1243`$ (represented in the following figure) or $`2143`$ where $`\pi _{i_3}=j`$:

On the other hand, it is clear from the construction that the occurrence of a pattern $`1243`$ or $`2143`$ in a permutation yields a diagram corner of rank at least $`2`$. $`\mathrm{}`$

We wish to describe the diagrams more precisely that arise as diagram of a Schröder permutation. First we state two elementary properties of each permutation diagram.

###### Lemma 2.2

Let $`\pi 𝒮_n`$ be an arbitrary permutation.

* We have $`i+jn+r`$ for each $`(i,j)_r(\pi )`$.
* Let $`(i,j)`$ be a diagram square of rank $`1`$ for which $`(i1,j)`$ and $`(i,j1)`$ do not belong to $`D(\pi )`$. Then $`\pi _{i1}=j1`$. Furthermore, for any element $`(i,j)_1(\pi )`$ there exists no square $`(i^{},j^{})(\pi )`$ with $`i^{}<i`$ and $`j^{}<j`$.

Proof. a) Let $`(i,j)(\pi )`$ be of rank $`r`$. Then exactly $`r`$ indices $`k<i`$ satisfy $`\pi _k<j`$. By construction, we have $`\pi _i>j`$ and $`i<\pi _j^1`$. Thus there exist $`ir`$ integers $`ki`$ with $`\pi _k>j`$. Clearly, the number of all elements $`\pi _k>j`$ in $`\pi `$ equals $`nj`$. This yields the restriction.
b) By definition, there is exactly one dot (representing a pair $`(i^{},j^{})`$ where $`\pi _i^{}=j^{}`$) northwest of $`(i,j)`$. From the condition that $`(i,j)`$ forms the upper left-hand corner of a connected component of diagram squares follows $`\pi _{i1}<j`$ and $`\pi _{j1}^1<i`$. Thus we have $`i^{}=i1`$ and $`j^{}=j1`$.
For the second assertion let $`(i,j)_1(\pi )`$. Suppose that there exists a diagram corner $`(i^{},j^{})`$ with $`i^{}<i`$ and $`j^{}<j`$. Obviously, $`(i^{},j^{})`$ must be of rank $`0`$, and by the first part, it is different from $`(i1,j1)`$. Thus $`(i^{},j^{})`$ is a corner of the Young diagram formed from the diagram squares that are connected with $`(1,1)`$. Hence $`\pi _{i^{}+1}j^{}`$ and $`\pi _{j^{}+1}^1i^{}`$. (Note that $`i^{}+1<i`$ and $`j^{}+1<j`$; otherwise $`(i,j)`$ is not a diagram square.) Consequently, there are two dots northwest of $`(i,j)`$, contradicting to $`(i,j)_1(\pi )`$. $`\mathrm{}`$

###### Remark 2.3

Condition a) is a part of Eriksson’s and Linusson’s characterization of ranked essential sets, see \[4, Theo. 4.1\].
In case of Schröder permutations, the second claim of b) means: there are no diagram corners $`(i,j)`$ and $`(i^{},j^{})`$ such that $`i^{}<i`$ and $`j^{}<j`$. By \[5, Prop. 9.6\], just this property characterizes vexillary permutations. Fulton’s description is an important example of characterization classes of permutations by the shape of their essential set. He gave a set of sufficient conditions that all except for one are also necessary. Later, Eriksson and Linusson strengthened that condition to obtain a set of necessary and sufficient conditions. Note that vexillary permutations can alternatively be characterized as $`2143`$-avoiding ones, see \[8, (1.27)\]. Of course, every Schröder permutation is vexillary.

Consequently, we can answer the question when a subset of the $`n^2`$ squares of $`\{1,\mathrm{},n\}^2`$ is the essential set of a Schröder permutation in $`𝒮_n`$. In particular, this yields a further combinatorial interpretation of Schröder numbers.

###### Proposition 2.4

For $`s0`$ let $`i_1i_2\mathrm{}i_s`$ and $`j_1j_2\mathrm{}j_s`$ be positive integers, and let $`r_1,r_2,\mathrm{},r_s`$ be $`0`$ or $`1`$ such that

$`i_1r_1>i_2r_2>\mathrm{}>i_sr_s>0\text{and}0<j_1r_1<j_2r_2<\mathrm{}<j_sr_s.`$ (1)
For any $`ni_1+j_s`$ there is a unique permutation $`\pi 𝒮_n`$ with $`(\pi )=\{(i_1,j_1),\mathrm{},(i_s,j_s)\}`$ and $`\rho (i_k,j_k)=r_k`$ for $`k=1,\mathrm{},s`$. In particular, $`\pi `$ avoids $`1243`$ and $`2143`$, and every Schröder permutation arises from a unique collection of such integers.

Proof. See Fulton’s \[5, Prop. 9.6\]. The condition $`r_k\{0,1\}`$ follows from Therorem 2.1. $`\mathrm{}`$

In \[4, Prop. 2.2\], the condition $`ni_1+j_s`$ has been replaced by $`i_k+j_kn+r_k`$ for $`k=1,\mathrm{},s`$.

###### Corollary 2.5

*
* The $`(n1)`$st Schröder number $`r_{n1}`$ counts the number of tripels of the integer sequences $`i_1i_2\mathrm{}i_s>0`$ and $`0<j_1j_2\mathrm{}j_s`$, and the binary sequence $`r_1,\mathrm{},r_s`$ satisfying (1) and $`i_k+j_kn+r_k`$ for all $`k`$.
* The $`n`$th Catalan number $`C_n`$ counts the number of pairs of integer sequences $`i_1>i_2>\mathrm{}>i_s>0`$ and $`0<j_1<j_2<\mathrm{}<j_s`$ such that $`i_k+j_kn`$ for all $`k`$. In particular, the number of such pairs of sequences of length $`s`$ is counted by the Narayana number $`N(n,s+1)`$.

Proof. The special case of $`132`$-avoiding permutations ($`\rho (i,j)=0`$ for each element $`(i,j)`$ of the essential set) in 2.4 yields part b). It is well known that $`|𝒮_n(132)|=C_n=\frac{1}{n+1}\left(\genfrac{}{}{0pt}{}{2n}{n}\right)`$ for all $`n`$. The second result of b) where $`N(n,s+1)=\frac{1}{n}\left(\genfrac{}{}{0pt}{}{n}{s}\right)\left(\genfrac{}{}{0pt}{}{n}{s+1}\right)`$ appeared in \[9, Rem. 2.6c\]. $`\mathrm{}`$

Some of the results of this paper are given in terms of essential sets. Therefore we will describe first how one can retrieve a Schröder permutation from its ranked essential set. In the special case of Schröder permutations the retrieval algorithm due to Eriksson and Linusson is an evident procedure; that’s why we will do this without any technical notation used in .
Let $`\pi 𝒮_n`$ be a Schröder permutation, and $`E:=(\pi )`$ its essential set. Hence $`E`$ is a subset of labeled squares in $`\{1,2,\mathrm{},n\}^2`$ satisfying Proposition 2.4. Let the elements of $`E`$ be represented as white labeled squares in an $`n\times n`$-array. (All squares that do not belong to $`E`$ are shaded.)

Figure 2a Ranked essential set of $`\pi =\mathrm{4\hspace{0.25em}7\hspace{0.25em}5\hspace{0.25em}2\hspace{0.25em}6\hspace{0.25em}3\hspace{0.25em}1}𝒮_7(1243,2143)`$.

(1) Colour white all squares $`(i^{},j^{})`$ with $`i^{}i`$ and $`j^{}j`$ where $`(i,j)E`$ is a square labeled with $`0`$. In this way we obtain the connected component of all diagram squares which are of rank $`0`$. (Note that the rank function can be extended on the set of diagram squares.)

Figure 2b All diagram squares of rank $`0`$ are known.

(2) Put a dot in each shaded square $`(i,j)`$ for which every square $`(i^{},j^{})`$ with $`i^{}i`$ and $`j^{}j`$, different from $`(i,j)`$, is a diagram square of rank $`0`$. Obviously, these dots just represent the left-to-right minima of the permutation. (A left-to-right minimum of a permutation $`\pi `$ is an element $`\pi _i`$ which is smaller than all elements to its left, i.e., $`\pi _i<\pi _j`$ for every $`j<i`$.)

Figure 2c All dotted squares connected with a diagram square of rank $`0`$ are known.

(3) For each dot contained in a square $`(i,j)`$, colour white all squares $`(i^{\prime \prime },j^{\prime \prime })`$ with $`i<i^{\prime \prime }i^{}`$ and $`j<j^{\prime \prime }j^{}`$ where $`(i^{},j^{})E`$ is a square labeled with $`1`$. By this step, all diagram squares of rank $`1`$ are obtained. (Note that all squares which are situated in the southeast area of a given dot belong to the same connected component.)

Figure 2d The diagram is completed.

(4) Row by row, if no dot exists in the row, put such a one in the leftmost shaded square such that there is exactly one dot in each column. Now the permutation can read off from the array.

Figure 2e The permutation $`\pi =\mathrm{4\hspace{0.25em}7\hspace{0.25em}5\hspace{0.25em}2\hspace{0.25em}6\hspace{0.25em}3\hspace{0.25em}1}`$ is recovered.

The following transformation explains the close connection between $`132`$-avoiding permutations and Schröder permutations.

###### Proposition 2.6

Let $`\pi 𝒮_n`$ be a Schröder permutation. Let $`^{}(\pi )`$ be the set which we obtain from $`(\pi )`$ by replacing every element $`(i,j)_1(\pi )`$ by $`(i1,j1)`$ and defining it to be of rank $`0`$. Then $`^{}(\pi )`$ is an essential set. (In particular, $`^{}(\pi )`$ is the essential set of a $`132`$-avoiding permutation.)

Proof. Let $`(\pi )=\{(i_1,j_1),\mathrm{},(i_s,j_s)\}`$. We may assume that $`\rho (i_k,j_k)=1`$ for any $`k`$, otherwise the assertion is trivial. Set $`i_k^{}:=i_k1,j_k^{}:=j_k1,r_k^{}:=r_k1=0`$, and check Proposition 2.4 for $`E=(\pi )\{(i_k^{},j_k^{})\}\{(i_k,j_k)\}`$. Evidently, all the conditions are satisfied (we have $`i_kr_k=i_k^{}r_k^{},j_kr_k=j_k^{}r_k^{}`$). $`\mathrm{}`$

###### Example 2.7

Let $`\pi =\mathrm{4\hspace{0.25em}7\hspace{0.25em}5\hspace{0.25em}2\hspace{0.25em}6\hspace{0.25em}3\hspace{0.25em}1}𝒮_7(1243,2143)`$. Then the transformation $`(\pi )^{}(\pi )`$ yields the essential set of $`\sigma =\mathrm{6\hspace{0.25em}4\hspace{0.25em}5\hspace{0.25em}3\hspace{0.25em}2\hspace{0.25em}7\hspace{0.25em}1}𝒮_7(132)`$:

Figure 3 On the left the diagram of $`\pi `$; on the right the diagram of $`\sigma `$.

Let $`\varphi :𝒮_n(1243,2143)𝒮_n`$ be the map which takes any Schröder permutation $`\pi `$ to the permutation whose essential set equals $`^{}(\pi )`$. Obviously, $`\varphi `$ is a surjection to $`𝒮_n(132)`$.
It follows from Lemma 2.2b and the retrieval procedure that $`D(\pi )`$ and $`D(\varphi (\pi ))`$ have the same number of squares. By \[8, (1.21)\], for any permutation $`\pi 𝒮_n`$ the number of diagram squares is equal to the number of inversions $`\mathrm{𝗂𝗇𝗏}(\pi )`$ of $`\pi `$. Thus we have $`\mathrm{𝗂𝗇𝗏}(\pi )=\mathrm{𝗂𝗇𝗏}(\varphi (\pi ))`$ for every $`\pi 𝒮_n(1243,2143)`$. Furthermore, Fulton observed in  that a permutation $`\pi 𝒮_n`$ has a descent at position $`i`$ if and only if there exists a diagram corner in the $`i`$th row of the $`n\times n`$-array representing $`\pi `$. (An integer $`i\{1,\mathrm{},n1\}`$ for which $`\pi _i>\pi _{i+1}`$ is called a descent of $`\pi 𝒮_n`$. The number of descents of $`\pi `$ is denoted by $`\mathrm{𝖽𝖾𝗌}(\pi )`$.) Lemma 2.2b implies that $`\mathrm{𝖽𝖾𝗌}(\pi )\mathrm{𝖽𝖾𝗌}(\varphi (\pi ))`$ for each $`\pi 𝒮_n(1243,2143)`$.
The left-to-right minima of a permutation $`\pi 𝒮_n`$ are represented by such dots $`(i,j)`$ for which $`(i1,j)`$ or $`(i,j1)`$ are diagram squares of rank $`0`$. To master the case $`\pi _1=1`$ we assume that $`(0,1)`$ is a diagram square of rank $`0`$. Consequently, every left-to-right minimum of $`\pi 𝒮_n(1243,2143)`$ is also such a one for $`\varphi (\pi )`$.
In \[9, Theo. 5.1\] we have shown that the number of subsequences of type $`132`$ in an arbitrary permutation is equal to the sum of ranks of all diagram squares. For Schröder permutations this value is just the number of all diagram squares of rank $`1`$.
The conversion of the above transformation is a simple way to construct Schröder permutations which contain a prescribed number of occurrences of the pattern $`132`$.
Given the essential set of a $`132`$-avoiding permutation $`\sigma 𝒮_n(132)`$ (recall that $`(\sigma )`$ is the corner set of a Young diagram fitting in $`(n1,n2,\mathrm{},1)`$; all elements are of rank $`0`$), we replace some elements $`(i,j)(\sigma )`$ by $`(i+1,j+1)`$ and increase their label by $`1`$. It follows from Proposition 2.4 and Lemma 2.2a that the resulting set is an essential set of a Schröder permutation in $`𝒮_n`$ if and only if we have $`i+j<n`$ for all replaced elements $`(i,j)`$.
For instance, from $`\sigma =\mathrm{6\hspace{0.25em}4\hspace{0.25em}5\hspace{0.25em}3\hspace{0.25em}2\hspace{0.25em}7\hspace{0.25em}1}𝒮_7(132)`$ we obtain:

Figure 4 (All the) Schröder permutations obtained from $`\sigma `$.

Obviously, these are all the Schröder permutations which can be constructed in this way, that is, whose image with respect to $`\varphi `$ equals $`\sigma `$. Note that $`\mathrm{𝗂𝗇𝗏}(\sigma )=15=\mathrm{𝗂𝗇𝗏}(\pi _i)`$ for $`i=1,\mathrm{},8`$.

###### Proposition 2.8

Let $`\sigma 𝒮_n(132)`$, and let $`s`$ be the number of elements $`(i,j)(\sigma )`$ satisfying $`i+j<n`$. Then there exist $`2^s`$ Schröder permutations $`\pi 𝒮_n`$ for which $`\varphi (\pi )=\sigma `$.

Proof. This follows from the preceding discussion. $`\mathrm{}`$

In \[9, Cor. 3.7\], we have enumerated the Young diagrams fitting in $`(n1,n2,\mathrm{},1)`$ according to the number of their corners in the diagonal $`i+j=n`$. The number of such diagrams with $`k0`$ corners $`(i,ni)`$ equals the ballot number $`b(n1,n1k)=\frac{k+1}{2n1k}\left(\genfrac{}{}{0pt}{}{2n1k}{n}\right)`$.
Now we are interested in the distribution of corners outside that diagonal.

###### Proposition 2.9

Let $`c(n1,k)`$ be the number of Young diagrams fitting in the shape $`(n1,n2,\mathrm{},1)`$ with $`k1`$ corners satisfying $`i+j<n`$. Then we have

$$c(n1,k)=\underset{i=1}{\overset{n1k}{}}\frac{i}{ni}\left(\genfrac{}{}{0pt}{}{ni}{k}\right)\left(\genfrac{}{}{0pt}{}{n1}{k+i}\right).$$

Furthermore, there are $`2^{n1}`$ such diagrams with no corner outside the diagonal $`i+j=n`$.

Proof. Consider the Young diagram as being contained in an $`n\times n`$-rectangle, and consider the lattice path from the upper right-hand to the lower left-hand corners of the rectangle that travels along the boundary of the diagram. Defining the rectangle diagonal to be the $`x`$-axis with origin in the lower left-hand corner, we obtain a Dyck path of length $`2n`$, that is, a lattice path from $`(0,0)`$ to $`(2n,0)`$ which never falls below the $`x`$-axis. (In , we have noted that the lattice path resulting from the diagram of a $`132`$-avoiding permutation $`\pi 𝒮_n`$ in this way is just the Dyck path corresponding to $`\pi `$ according a bijection proposed by Krattenthaler in .) In terms of Dyck paths, a diagram corner satisfying $`i+j<n`$ means a valley at a level greater than $`0`$ (where the $`x`$-axis marks the $`0`$-level). The distribution of the number of these valleys was given in \[2, Sect. 6.11\]. $`\mathrm{}`$

The previous both propositions immediately yield an explicit description for the Schröder numbers.

###### Corollary 2.10

For $`n0`$ we have $`r_n=2^n+_{k=1}^{n1}2^kc(n,k)`$.

###### Remark 2.11

Another one is $`r_n=_{k=0}^n\left(\genfrac{}{}{0pt}{}{2nk}{k}\right)C_{nk}`$ where $`C_n=\frac{1}{n+1}\left(\genfrac{}{}{0pt}{}{2n}{n}\right)`$ denotes the $`n`$th Catalan number. This formula follows directly from an interpretation in terms of lattice paths, see \[11, Exc. 6.19 and 6.39\].

3 Forbidden subsequences in Schröder permutations

In this section we will demonstrate that diagrams can be used to obtain simple proofs for enumerative results concerning certain restrictions of Schröder permutations. Most of numbers $`|𝒮_n(1243,2143,\tau )|`$ appearing below are known from their analytical derivation in .
For the following investigation, only one case is really of interest: the essential set of $`\pi 𝒮_n(1243,2143)`$ contains both elements of rank $`0`$ and $`1`$. If $`_1(\pi )=\mathrm{}`$ then $`\pi `$ avoids $`132`$, and all has been done in . If there is no diagram corner of rank $`0`$ then we have $`\pi _1=1`$, and $`\pi _2\mathrm{}\pi _n`$ can be identified with a permutation in $`𝒮_{n1}(132)`$. In particular, these permutations contain as many subsequences of type $`21`$ (inversions) as of type $`132`$. (Note that the number of the first ones equals the number of all diagram squares, and the number of the latter counts all diagram squares of rank $`1`$).
Let us start with the consideration of increasing subsequences. In \[9, Theo. 4.1b\] we proved that a permutation $`\pi 𝒮_n(132)`$ avoids the pattern $`12\mathrm{}k`$ if and only if its diagram contains $`(n+1k,nk,\mathrm{},1)`$. (Recall that in case of $`132`$-avoiding permutations the diagram corresponds to a Young diagram fitting in the shape $`(n1,n2,\mathrm{},1)`$.) This condition will be useful for Schröder permutations as well.

###### Theorem 3.1

Let $`\pi 𝒮_n(1243,2143)`$ be a Schröder permutation. Then $`\pi `$ avoids $`12\mathrm{}k`$ for any $`k1`$ if and only if $`\varphi (\pi )`$ avoids $`12\mathrm{}k`$.

Proof. We may assume that the essential set $`(\pi )`$ contains at least one element, say $`(i,j)`$, of rank $`1`$; otherwise the assertion is trivial. The proof of 2.6 implies that the set $`^{}(\pi ):=(\pi )\{(i1,j1)\}\{(i,j)\}`$ is the essential set of a Schröder permutation again. The rank of $`(i1,j1)`$ is defined as $`0`$. (Successive determining yields the set $`^{}(\pi )`$ stated in Proposition 2.6.) Now we consider which consequences for the corresponding permutation result from this transformation.
Let $`\sigma 𝒮_n(1243,2143)`$ such that $`(\sigma )=^{}(\pi )`$. Then $`\sigma `$ differs from $`\pi `$ at exactly three positions. Let $`\pi _{i_1}`$ be the element represented by the only dot in the northwest of $`(i,j)`$. Furthermore let $`\pi _{i_2}=j`$. Then we have $`\sigma _i=\pi _{i_1},\sigma _{i_2}=\pi _i,\sigma _{i_1}=\pi _{i_2}`$, and $`\sigma _k=\pi _k`$ for all $`k`$, different from $`i,i_1,i_2`$. The proof for this fact, we find in the retrieval procedure given in Section 2. (For a better understanding it is helpful to consider simultaneously the example following the proof.)

* The element $`\pi _{i_1}`$ is a left-to-right minimum of $`\pi `$. All the squares due north or due west of the dot $`(i_1,\pi _{i_1})`$ are diagram squares of rank $`0`$. Let $`i^{}`$ be the smallest integer greater than $`i_1`$ such that a corner of rank $`0`$ appears in row $`i^{}`$. (If such a corner does not exist, set $`i^{}=\mathrm{}`$.) By Lemma 2.2b, we have $`ii^{}`$. In the array representing $`\sigma `$, the square $`(i1,j1)`$ forms a corner of the $`0`$-component, and the next one appears in row $`i^{}`$. Thus the dot representing $`\sigma _i`$ is contained in column $`\pi _{i_1}`$.
* By the transformation, all squares $`(i^{\prime \prime },j^{\prime \prime })`$ for which $`i_1<i^{\prime \prime }i`$ and $`\pi _{i_1}<j^{\prime \prime }j`$ are moved northwestwards. Let $`j^{}`$ be the column index of the corner of rank $`0`$ which appears in row $`i_11`$. (Note that for $`i_1>1`$ such a one has to exist since $`\pi _{i_1}`$ is a left-to-right minimum. For $`i_1=1`$ set $`j^{}=\mathrm{}`$.) By Lemma 2.2b again, we have $`jj^{}`$. Hence in the array of $`\sigma `$ the square $`(i_1,j)`$ is dotted.
* Now all dots $`(i^{},\sigma _i^{})`$ with $`i^{}i`$ are fixed. It follows from the construction that these dots are just $`(i^{},\pi _i^{})`$ if $`i^{}i_1,i`$. Since all diagram squares south of row $`i`$ appear at the same position in $`D(\sigma )`$, the only possible position for the missing dot in row $`i_2`$ is $`(i_2,\pi _i)`$. For all other indices $`k`$ we have $`\sigma _k=\pi _k`$. (Note that $`\pi _i>\pi _{i_1}`$ and $`\pi _i>\pi _{i_2}`$.)

Consequently, if $`\pi `$ contains any increasing subsequence of length $`k`$, the permutation $`\sigma `$ contains such a sequence as well, and vice versa: by definition and step 2), the elements $`\pi _{i_1}`$ and $`\sigma _{i_1}`$ are left-to-right minima of $`\pi `$ and $`\sigma `$, respectively. If these elements occur in an increasing subsequence then as the first term. Obviously, all the elements $`\pi _{i_1+1},\mathrm{},\pi _{i1}`$ are greater than $`\pi _{i_2}`$ ($`=\sigma _{i_1}`$). Furthermore we have $`\pi _k<\pi _{i_2}`$ for $`k=i+1,\mathrm{},i_21`$. (Note that there exists no diagram square in the southeast area of $`(i,j)`$.) Thus, and since $`\pi _{i_1}<\pi _{i_2}<\pi _i`$ each increasing subsequence in $`\pi _{i_1}\pi _{i_1+1}\mathrm{}\pi _{i_2}`$ corresponds to an increasing subsequence of the same length in $`\sigma _{i_1}\sigma _{i_1+1}\mathrm{}\sigma _{i_2}`$.
Using the arguments successively (until the permutation $`\varphi (\pi )`$ is obtained) proves the assertion of the theorem. $`\mathrm{}`$

###### Example 3.2

For $`\pi =\mathrm{5\hspace{0.25em}9\hspace{0.25em}8\hspace{0.25em}10\hspace{0.25em}4\hspace{0.25em}2\hspace{0.25em}6\hspace{0.25em}7\hspace{0.25em}3\hspace{0.25em}1}𝒮_{10}(1243,2143)`$ we obtain the essential set $`(\pi )=\{(9,1),(8,3),(5,3),(4,4),(4,7),(2,8)\}`$ where $`(4,7)`$ is of rank $`1`$. Replacing this element yields the essential set of $`\sigma =\mathrm{7\hspace{0.25em}9\hspace{0.25em}8\hspace{0.25em}5\hspace{0.25em}4\hspace{0.25em}2\hspace{0.25em}6\hspace{0.25em}10\hspace{0.25em}3\hspace{0.25em}1}𝒮_{10}(1243,2143)`$:

Figure 5  On the left the diagram of $`\pi `$; on the right the diagram of $`\sigma `$. Only the given dots change their position.

The pattern considered now is closely related to the increasing subsequences. In special case of $`132`$-avoiding permutations the following characterization is identical with \[9, Theo. 4.1c\].

###### Theorem 3.3

Let $`\pi 𝒮_n(1243,2143)`$ be a Schröder permutation. Then $`\pi `$ avoids $`213\mathrm{}k`$ if and only if every element $`(i,j)(\pi )`$ satisfies $`i+jn+3k+\rho (i,j)`$.

Proof. Let $`(i,j)(\pi )`$. The $`n`$ dots representing $`\pi `$ are arranged as follows (the labels are the numbers of dots contained in the certain regions where $`r:=\rho (i,j)`$):

If there is no corner $`(i,j^{})`$ such that $`j<j^{}`$ (see the left-hand picture) then for all elements $`\pi _k`$ with $`k>i`$ and $`\pi _k>j`$ we have $`\pi _k>\pi _i`$. Clearly, $`\pi _{i+1}<\pi _i`$. On the other hand, if there exists such a corner $`(i,j^{})`$ (see the right-hand picture; necessarily, $`\rho (i,j)=0`$ and $`\rho (i,j^{})=1`$) then the dot northwest of $`(i,j^{})`$ is contained in column $`j+1`$, otherwise Lemma 2.2b fails to hold. (Note that this dot marks an inner corner of the $`0`$-component.) In this case, all elements $`\pi _k`$ with $`k>i`$ and $`\pi _k>j`$ satisfy $`\pi _k>j+1`$. Clearly, $`\pi _{i+1}j`$. In both cases the elements representing by dots in the lower right-hand region appear in increasing order since $`\pi `$ is $`2143`$-avoiding. If $`i+j<n+3k+\rho (i,j)`$ then their number $`n(i+j)+\rho (i,j)`$ is at least $`k2`$.
To prove the converse, suppose that every element of the essential set satisfies the above condition. Then we have $`\pi _i+i>n+3k`$ for all $`i𝖣(\pi )`$. Hence for each descent $`i`$ of $`\pi `$ there exist at most $`k3`$ elements $`\pi _j`$ with $`j>i`$ and $`\pi _j>\pi _i`$. Since $`\pi `$ is $`2143`$-avoiding these elements form an increasing sequence. Thus there is no pattern $`2134\mathrm{}k`$ in $`\pi `$. $`\mathrm{}`$

Now we are in the position to answer the first of a collection of open problems given in . Theorem 6.5 of this reference implies the Wilf-equivalence of $`\{1243,2143,12\mathrm{}k\}`$ and $`\{1243,2143,213\mathrm{}k\}`$, that is, $`|𝒮_n(1243,2143,12\mathrm{}k)|=|𝒮_n(1243,2143,213\mathrm{}k)|`$ for all $`n`$ and $`k`$. The authors asked for a combinatorial proof of this fact. There is a simple bijection in terms of diagrams whose essence was already used to prove the analogue for $`132`$-avoiding permutations.

###### Corollary 3.4

There is a bijection $`\omega :𝒮_n(1243,2143)𝒮_n(1243,2143)`$ such that for all $`k1`$ and any permutation $`\pi 𝒮_n(1243,2143)`$, we have that $`\pi `$ avoids $`12\mathrm{}k`$ if and only if $`\omega (\pi )`$ avoids $`213\mathrm{}k`$.

Proof. Let $`\pi 𝒮_n(1243,2143)`$ be a Schröder permutation which avoids $`12\mathrm{}k`$. By Theorem 3.1 and \[9, Theo. 4.1b\], the diagram of $`\varphi (\pi )𝒮_n(132)`$ contains $`(n+1k,nk,\mathrm{},1)`$. Since all the corners of $`(n+1k,nk,\mathrm{},1)`$ are in the diagonal $`i+j=n+2k`$ we have $`i+jn+2k+2\rho (i,j)`$ for all $`(i,j)(\pi )`$. Hence the diagram corners of rank $`1`$ satisfy the condition of Theorem 3.3 anyway. Thus every diagram corresponding to a $`12\mathrm{}k`$-avoiding Schröder permutation is uniquely determined by its corners outside the shape $`(n+1k,nk,\mathrm{},1)`$, that is, by all corners except for those satisfying $`i+j=n+2k`$. Consequently, the diagram of $`\omega (\pi )`$ we define to be this one whose corners are the corners of $`D(\pi )`$ which are not contained in $`(n+1k,nk,\mathrm{},1)`$. Ranks are kept up.
Conversely, given any Schröder permutation $`\sigma 𝒮_n(1243,2143)`$ whose all diagram corners satisfy $`i+jn+3k+\rho (i,j)`$ we construct the permutation $`\omega ^1(\sigma )`$ as follows: let $`E`$ be the corner set of the diagram obtained as union of $`D(\varphi (\sigma ))`$ and $`(n+1k,nk,\mathrm{},1)`$. (Note that this is a Young diagram since $`D(\varphi (\pi ))`$ is such a one.) Then we form the essential set of $`\omega ^1(\sigma )`$ from the pairs $`(i,j)E`$ for which $`(i+1,j+1)_1(\sigma )`$, and all elements of $`_1(\sigma )`$. The first ones are defined to be of rank $`0`$, the rank of the latter should be $`1`$. Obviously, the resulting set is an essential set of a $`12\mathrm{}k`$-avoiding Schröder permutation. $`\mathrm{}`$

###### Example 3.5

The maximum length of an increasing subsequence in the Schröder permutation $`\pi =\mathrm{4\hspace{0.25em}6\hspace{0.25em}3\hspace{0.25em}1\hspace{0.25em}5\hspace{0.25em}7\hspace{0.25em}2}𝒮_7(1243,2143)`$ equals $`3`$. Taking $`k=4`$, we obtain $`\omega (\pi )=\mathrm{1\hspace{0.25em}6\hspace{0.25em}3\hspace{0.25em}4\hspace{0.25em}5\hspace{0.25em}7\hspace{0.25em}2}`$:

Figure 6 Construction of $`\omega (\pi )`$: the corners crossed out satisfy $`i+j=n+2k`$.

###### Remarks 3.6

*
* Since $`_1(\pi )=_1(\omega (\pi ))`$ for all $`\pi 𝒮(1243,2143,12\mathrm{}k)`$ the map $`\omega `$ takes any $`132`$-avoiding permutation to a permutation which avoids $`132`$ as well. Indeed, the restriction of $`\omega `$ on $`𝒮(132,12\mathrm{}k)`$ is precisely the bijection given in \[9, Cor. 4.4\] that proves the Wilf-equivalence of $`\{132,12\mathrm{}k\}`$ and $`\{132,213\mathrm{}k\}`$.
* It is clear from the construction that a $`12\mathrm{}k`$-avoiding Schröder permutation also avoids $`213\mathrm{}k`$ if and only if it is a fixed point of $`\omega `$. The essential set of such a permutation can be constructed as follows: consider the corner set of a Young diagram which contains $`(n+1k,nk,\mathrm{},1)`$, and fits in $`(n1,n2,\mathrm{},1)`$. Now replace at least all elements $`(i,j)`$ by $`(i+1,j+1)`$ for which $`i+j=n+2k`$. Some further corners can be replaced if these satisfy $`i+j<n`$. The rank of all new corners is set as $`1`$; let the others be of rank $`0`$.
We will discuss the enumerative consequence only for $`k=3`$.

###### Corollary 3.7

$`|𝒮_n(1243,2143,123,213)|=2^{n1}`$ for all $`n1`$.

Proof. Taking up again the idea of the previous remark, the diagram of a Schröder permutation $`\pi 𝒮_n(1243,2143)`$ which avoids both $`123`$ as $`213`$ arises from a Young diagram that contains $`(n2,n3,\mathrm{},1)`$, and fits in $`(n1,n2,\mathrm{},1)`$. Clearly, each such Young diagram is uniquely determined by its corners in the diagonal $`i+j=n`$. In particular, there are $`2^{n1}`$ diagrams of this kind. (This implies $`|𝒮_n(132,123)|=2^{n1}`$; see \[10, Prop. 7\] for another proof.)
From the corner set of each Young diagram the essential set of only one permutation $`\pi 𝒮_n(1243,2143,123,213)`$ can be generated because all the corners $`(i,n1i)`$ must be replaced, but all the corners $`(i,ni)`$ must not be replaced. $`\mathrm{}`$

###### Remark 3.8

To obtain a $`\{132,123,213\}`$-avoiding permutation in the way described in the proof, the Young diagram must not have any corner in the diagonal $`i+j=n1`$. We can identify such a diagram by a binary sequence of length $`n1`$ whose $`i`$th element is defined as $`1`$ (or $`0`$) if $`(i,ni)`$ is a corner (or not). The condition that there is no diagram corner outside the diagonal $`i+j=n`$ means that the corresponding sequence contains no consecutive zeros. The number of such sequences is known to be equal the $`(n+1)`$st Fibonacci number $`F_{n+1}`$. (The Fibonacci numbers are defined by $`F_1=F_2=1`$ and $`F_n=F_{n1}+F_{n2}`$ for $`n3`$.) The result $`|𝒮_n(132,123,213)|=F_{n+1}`$ already appears in \[10, Prop. 15\].

The next result deals with the occurrence of a decreasing subsequence of length $`k`$ in Schröder permutations. The analogue for $`132`$-avoiding permutations is simple: a permutation $`\pi 𝒮_n(132)`$ avoids $`k(k1)\mathrm{}1`$ if and only if $`|(\pi )|k2`$, see \[9, Theo. 4.1a\]. Now the condition is some more difficult.
To state it, we first set some notation. For a permutation $`\pi 𝒮_n`$ we denote by $`r(\pi )`$ and $`c(\pi )`$ the number of rows and columns, respectively, that contain a diagram corner. As mentioned above, we have $`r(\pi )=\mathrm{𝖽𝖾𝗌}(\pi )`$, and $`c(\pi )=\mathrm{𝖽𝖾𝗌}(\pi ^1)`$. (Note that the transpose of $`D(\pi )`$ is just the diagram of $`\pi ^1`$.) It follows from Proposition 2.4 that any diagram row (column) contains at most two corners (necessarily of different rank) if $`\pi 𝒮_n(1243,2143)`$. Let $`r_2(\pi )`$ and $`c_2(\pi )`$ be the number of diagram rows and diagram columns, respectively, containing two corners.

###### Theorem 3.9

Let $`\pi 𝒮_n(1243,2143)`$ be a Schröder permutation. Then $`\pi `$ avoids $`k(k1)\mathrm{}1`$ if and only if one of the following conditions holds:

* $`r(\pi )k2`$ or $`c(\pi )k2`$;
* $`r(\pi )=k1,r_2(\pi )=c_2(\pi )=1`$, and there is no element $`(i,j)(\pi )`$ that such both row $`i`$ and column $`j`$ contain another corner.

Proof. Suppose that $`\pi `$ contains a decreasing subsequence of length $`k`$. Obviously, its inverse contains such a sequence as well. Consequently, both $`\pi `$ and $`\pi ^1`$ must have at least $`k1`$ descents, that is, $`r(\pi )k1`$ and $`c(\pi )k1`$. Now let $`r(\pi )=k1`$ and $`r_2(\pi )=c_2(\pi )=1`$. (Then we also have $`c(\pi )=k1`$.)
If the essential corners are arrange as in the picture opposite (where $`i_2i_3`$) we have $`\pi _{i_1}>\pi _{i_1+1},\pi _{i_2}>\pi _{i_2+1}`$ (corners correspond to descents) but $`\pi _{i_1}<\pi _{i_2}`$, and $`\pi _{i_1+1}<\pi _{i_2+1}`$. The last relation follows from the fact that $`(i_2,\pi _{i_2}+1)`$ is a diagram square by the construction. If its rank would be equal to $`0`$ then

$`r_2>1`$. Since $`\mathrm{𝖽𝖾𝗌}(\pi )=k1`$ there is no decreasing subsequence of length $`k`$ in $`\pi `$ which contradicts the assumption. In the second case (corners $`(i_1,j_2),(i_2,j_1)`$ of rank $`0`$, corners $`(i_1,j_3),(i_3,j_1)`$ of rank $`1`$ where $`i_1<i_2<i_3`$ and $`j_1<j_2<j_3`$) use the same arguments.
On the other hand, if condition (i) holds then $`\mathrm{𝖽𝖾𝗌}(\pi )k2`$ or $`\mathrm{𝖽𝖾𝗌}(\pi ^1)k2`$ and hence $`\pi 𝒮_n(k\mathrm{}1)`$. If (ii) is satisfied then (as shown in the first part of the proof) $`\pi `$ cannot contain any decreasing subsequence of length $`k`$. $`\mathrm{}`$

Here we will enumerate the permutations described in Theorem 3.9 only for $`k=3`$. To satisfy condition (ii) is impossible in this case. Thus a Schröder permutation is $`321`$-avoiding if and only if all its diagram corners are either in the same row or in the same column. This characterization was already given in \[4, Prop. 5.4\] for $`321`$-avoiding vexillary permutations. (Note that the essential set of a vexillary permutation can contain elements of rank greater than $`1`$; for example, $`1243`$ is such a permutation.)
Egge and Mansour have shown (derived from the generating function in \[3, Prop. 7.4\]) that

$$|𝒮_n(1243,2143,321)|=\left(\genfrac{}{}{0pt}{}{n1}{0}\right)+\left(\genfrac{}{}{0pt}{}{n1}{1}\right)+2\left(\genfrac{}{}{0pt}{}{n1}{2}\right)+2\left(\genfrac{}{}{0pt}{}{n1}{3}\right)\text{for all }n1.$$

Their fourth problem asked for a combinatorial proof. Here it is.

###### Corollary 3.10

$`|𝒮_n(1243,2143,321)|=n+2\left(\genfrac{}{}{0pt}{}{n}{3}\right)`$ for all $`n1`$.

Proof. Let $`\pi `$ be a Schröder permutation avoiding $`321`$. We distinguish the three cases mentioned at the begin of the section.
If $`\pi 𝒮_n(132)`$, different from the identity, then its diagram is a rectangle whose lower right-hand corner $`(i,j)`$ satisfies $`i+jn`$. There are

$$\underset{i=1}{\overset{n1}{}}(ni)=\left(\genfrac{}{}{0pt}{}{n}{2}\right)$$

such diagrams. (The enumeration of $`\{132,321\}`$-avoiding permutations was first done in \[10, Prop. 11\].) If there exists no element of rank $`0`$ in $`(\pi )`$, the permutation $`\pi _21\mathrm{}\pi _n1`$ belongs to $`𝒮_{n1}(132,321)`$.
It remains to consider the case that $`D(\pi )`$ has corners of rank $`0`$ and $`1`$. Since these squares are in the same row or column there is exactly one corner of each rank. Without loss of generality, we may assume that the both elements of $`(\pi )`$ are in the same row. (For the result in terms of columns consider the transpose that corresponds to the inverse of $`\pi `$.) Let $`(i,j)_0(\pi )`$ and $`(i,j^{})_1(\pi )`$. From Proposition 2.4 the conditions $`1<i`$, $`j+1<j^{}`$, and $`i+j^{}n+1`$ results. Given the pair $`(i,j)`$, the integer $`j^{}`$ can be chosen in $`nij`$ ways where $`i\{2,\mathrm{},n2\}`$, and $`j\{1,\mathrm{},n1i\}`$. Clearly,

$$\underset{i=2}{\overset{n2}{}}\underset{j=1}{\overset{n1i}{}}(nij)=\frac{1}{2}\underset{i=1}{\overset{n3}{}}i(i+1)=\left(\genfrac{}{}{0pt}{}{n1}{3}\right).$$

Summarized, we obtain $`|𝒮_n(1243,2143,321)|=1+\left(\genfrac{}{}{0pt}{}{n}{2}\right)+\left(\genfrac{}{}{0pt}{}{n1}{2}\right)+2\left(\genfrac{}{}{0pt}{}{n1}{3}\right)`$. (Note that the term $`1`$ stands for the identity; the factor $`2`$ regards rows and columns in the third case.) $`\mathrm{}`$

The last pattern we will discuss is a special case of an important class as well. In \[9, Theo. 4.5\], we characterized $`132`$-avoiding permutations which avoid the additional pattern $`s(s+1)\mathrm{}k12\mathrm{}(s1)`$ where $`s\{2,\mathrm{},k\}`$, and $`k3`$. The condition given there was of technical nature but for $`s=2`$ and $`k=3`$ it is equivalent to the following simple one: a permutation $`\pi 𝒮_n(132)`$ avoids $`231`$ if and only if all its diagram rows are of distinct length, that means, all diagram rows contain a corner. Analogously to that, $`231`$-avoiding Schröder permutations can be described.

###### Proposition 3.11

A Schröder permutation $`\pi 𝒮_n(1243,2143)`$ avoids $`231`$ if and only if

* every diagram row contains a (namely, exactly one) element of the essential set,
* and every diagram column contains at most an element of the essential set.

Proof. Suppose that $`\pi 𝒮_n(1243,2143)`$ contains a $`231`$-pattern: let $`i_1<i_2<i_3`$ such that $`\pi _{i_3}<\pi _{i_1}<\pi _{i_2}`$. Since diagram corners and permutation descents corresponds to each other, there is an integer $`i`$ with $`i_1i<i_2`$ such that row $`i`$ contains no corner. We assume that this row does not belong to the diagram, otherwise condition (i) fails to hold. Since $`(i_2,\pi _{i_3})D(\pi )`$ we have $`\pi _i=1`$, and all diagram squares appearing below the $`i`$th row are of rank $`1`$. By the construction, $`(i+1,2)`$ is the upper left-hand corner of the component which contains $`(i_2,\pi _{i_3})`$ (and all the other diagram squares of rank $`1`$). By Lemma 2.2b there is no corner in the strict northwest of another one. Therefore, and since $`\pi _{i_1}<\pi _{i_2}`$, the diagram corners containing in row $`i1`$ and $`i+1`$, respectively, have to be in the same column.
For the other direction, we suppose that there are a diagram square $`(i_1,j)`$ for which $`(i_1,j+1)D(\pi )`$, and a square $`(i_2,j)(\pi )`$ with $`i_1<i_2`$. (Then one of the conditions (i) and (ii) is not satisfied.) It is easy to see that $`\pi _{i_1}\pi _{i_2}\pi _{i_3}`$ where $`\pi _{i_3}=j`$ is a subsequence of type $`231`$. $`\mathrm{}`$

From the first part of the proof, it is clear how the diagram of a $`231`$-avoiding Schröder permutation has to look.

###### Corollary 3.12

The diagram of a Schröder permutation satisfies the conditions of Proposition 3.11 if and only if it is of the following shape:

where the diagram components $`E_0`$ and $`E_1`$ are Young diagrams whose row lengths are each distinct. (It may be that $`E_0`$ and/or $`E_1`$ are empty.)

As an immediate consequence we can characterize $`231`$-avoiding Schröder permutations from their descent set.

###### Corollary 3.13

Let $`\pi 𝒮_n`$ be a permutation, and $`𝖣(\pi )`$ the set of its descents. Then $`\pi `$ avoids the patterns $`1243`$, $`2143`$, and $`231`$ if and only if one of the following conditions is satisfied:

* $`s>d`$ and $`𝖣(\pi )=\{1,2,\mathrm{},d\}`$;
* $`sd`$ and $`𝖣(\pi )=\{1,2,\mathrm{},s1,s+1,s+2,\mathrm{},d+1\}`$, and $`\pi _{s1}>\pi _{s+1}`$ if $`1<s<n`$

where $`\pi _s=1`$ and $`d=\mathrm{𝖽𝖾𝗌}(\pi )`$.

###### Remark 3.14

We can decide by the conditions whether a $`231`$-avoiding Schröder permutation avoids the pattern $`132`$ in addition or not. The first condition describes all permutations in $`𝒮_n(132,231)`$.

Corollary 3.12 yields the answer to the third question of the Egge-Mansour list.

###### Corollary 3.15

For $`n2`$ we have $`|𝒮_n(1243,2143,231)|=(n+2)2^{n3}`$.

Proof. Let $`\pi 𝒮_n(1243,2143,231)`$. Consider the partition $`\lambda (\pi )`$ whose parts are just the lengths of the diagram rows where the length of the first row containing squares of rank 1 is listed twice. (By this information $`D(\pi )`$ and hence $`\pi `$ is completely described.) Adding some zeros (if necessary), we may assume that $`\lambda =(\lambda _1,\mathrm{},\lambda _{n1})`$ is of length $`n1`$. By the previous discussion, we have

$$n>\lambda _1>\lambda _2>\mathrm{}>\lambda _{i1}\lambda _i>\lambda _{i+1}>\mathrm{}>\lambda _l>\lambda _{l+1}=\lambda _{l+2}=\mathrm{}=\lambda _{n1}=0$$

with $`l\{0,\mathrm{},n1\}`$, and $`\lambda (n1,n1,n2,\mathrm{},2)`$ (where $``$ means the containment of the corresponding diagrams). Furthermore we have $`\lambda _j1`$ for all $`j`$ if any positive part exists twice.
To set $`\lambda `$ such that all the positive parts of $`\lambda `$ are distinct, there are $`_{l=0}^{n1}\left(\genfrac{}{}{0pt}{}{n1}{l}\right)=2^{n1}`$ ways. (This case corresponds to 132-avoiding permutations; hence $`|𝒮_n(132,231)|=2^{n1}`$, see also \[10, Prop. 9\].) If there exists a positive part twice then the number of partitions be considered equals

$$\underset{l=1}{\overset{n2}{}}\left(\genfrac{}{}{0pt}{}{n2}{l}\right)\left(\genfrac{}{}{0pt}{}{l}{1}\right)=(n2)\underset{l=0}{\overset{n3}{}}\left(\genfrac{}{}{0pt}{}{n3}{l}\right)=(n2)2^{n3}.$$

Note that $`1`$ must not a part of $`\lambda `$ now. Consequently, there are $`2^{n1}+(n2)2^{n3}=(n+2)2^{n3}`$ Schröder permutations in $`𝒮_n`$ which avoid $`231`$. $`\mathrm{}`$

4 A correspondence to lattice paths

It is well known that the $`n`$th Schröder number $`r_n`$ counts the number of all lattice paths from the origin to $`(n,n)`$, with steps $`[1,0]`$ (called East steps), $`[0,1]`$ (called North steps), and $`[1,1]`$ (called Diagonal steps), that never pass below the line $`y=x`$. Such paths we call Schröder paths. (See \[11, Exc. 6.39\] for further combinatorial interpretations of the Schröder numbers.)
Egge and Mansour have given a bijection $`\mathrm{\Psi }_{EM}`$ between these paths and Schröder permutations in $`𝒮_{n+1}`$, see \[3, Sect. 4\]. Its essential property is: the number of subsequences $`12\mathrm{}k`$ occuring in $`\pi 𝒮_{n+1}(1243,2143)`$ can read off (more or less) directly from the path $`\mathrm{\Psi }_{EM}(\pi )`$.
This bijection can be unterstood as analogue of Krattenthaler’s correspondence $`\mathrm{\Psi }_K`$ between $`132`$-avoiding permutations in $`𝒮_n`$ and lattice paths from $`(0,0)`$ to $`(n,n)`$ without diagonal steps, never passing below the line $`y=x`$. The map $`\mathrm{\Psi }_K`$ encodes the number of increasing subsequences of prescribed length in the same way, see \[6, (3.2)\].
We pointed out in  that the path $`\mathrm{\Psi }_K(\pi )`$ and the diagram of a $`132`$-avoiding permutation $`\pi `$ are closely related to each other. Considering the diagram of $`\pi 𝒮_n(132)`$ as being contained in an $`n\times n`$-rectangle, $`\mathrm{\Psi }_K(\pi )`$ is the lattice path which goes from the upper right-hand to the lower left-hand corners of the rectangle, and travels along the diagram boundary.
For $`\pi =\mathrm{6\hspace{0.25em}4\hspace{0.25em}5\hspace{0.25em}3\hspace{0.25em}2\hspace{0.25em}7\hspace{0.25em}1}𝒮_7(132)`$, for example, $`\mathrm{\Psi }_K(\pi )`$ equals the lattice path printed in bold:

Figure 7 Lattice path $`\mathrm{\Psi }_K(6453271)`$.

We can construct the path $`\mathrm{\Psi }_{EM}`$ just as simple from the permutation diagram.
Note again that each (Schröder) permutation is uniquely determined by its ranked essential set. Consequently, position and rank of the diagram corners are all that we have to transfer to a path corresponding to the permutation. Since a permutation $`\pi 𝒮_{n+1}(1243,2143)`$ should correspond to a Schröder path from $`(0,0)`$ to $`(n,n)`$, we cannot use $`D(\pi )`$ itself but the diagram of $`\varphi (\pi )`$ is fitting. Recall that the diagram of $`\varphi (\pi )`$ is obtained from that one of $`\pi `$ by ”moving” each diagram square of rank $`1`$ northwestwards. Hence it is a Young diagram which is contained in $`(n1,n2,\mathrm{},1)`$. Labeling all corners with their original rank we have all information needed to recover $`\pi `$.
Now the Schröder path corresponding to $`\pi `$ is constructed as follows: let $`D(\varphi (\pi ))`$ be embeded in an $`(n1)\times (n1)`$-rectangle. Analogously to the construction of $`\mathrm{\Psi }_K`$, the lattice path is defined to go from the upper right-hand to the lower left-hand corners of the rectangle, along the diagram boundary, where every step sequence NE representing a corner labeled with $`0`$ is replaced by a step D. Last we convert the path into the form used in . To this end, the rectangle is reflected such that the origin is placed at the bottom left instead at the top right.

###### Example 4.1

Let $`\pi =\mathrm{4\hspace{0.25em}7\hspace{0.25em}5\hspace{0.25em}2\hspace{0.25em}6\hspace{0.25em}3\hspace{0.25em}1}𝒮_7(1243,2143)`$. Using the diagram of $`\varphi (\pi )`$ we can immediately determine the Schröder path corresponding to $`\pi `$ (printed in bold again):

Figure 8  Construction of the path $`\mathrm{\Psi }_{EM}(\pi )`$: On the left the diagram of $`\pi `$; in the centre the diagram of $`\varphi (\pi )`$ with plotted path; on the right the converted path.

By Lemma 2.2a, each element $`(i,j)_1(\pi )`$ satisfies $`i+jn+1`$. Thus, for every corner $`(i^{},j^{})`$ of $`D(\varphi (\pi ))`$ labeled with $`1`$ we have $`i^{}+j^{}n1`$. Therefore, and since $`D(\varphi (\pi ))`$ is contained in $`(n1,n2,\mathrm{},1)`$, this construction indeed yields a Schröder path.
It is not difficult to see that the path obtained in this way is just $`\mathrm{\Psi }_{EM}(\pi )`$ for $`\pi 𝒮_n(1243,2143)`$ but the construction via diagram requires less effort.
In , the path statistic $`\tau _k`$ corresponding to the number of subsequences of type $`12\mathrm{}k`$ in $`\pi 𝒮_n(1243,2143)`$ is defined for $`k2`$ by

$$\underset{s\{𝖤,𝖣\}}{}\left(\genfrac{}{}{0pt}{}{h(s)}{k1}\right)$$

where $`h(s)`$ denotes the height of the starting point of step $`s`$. (The height of a point $`(x,y)`$ in the plane we define to be the difference $`yx`$.)

###### Example 4.2

Consider the Schröder path NENNEDENED appearing in the previous example. For each east and diagonal step the height is given in the picture.

Figure 9 Schröder path with step heights.

Thus there occur six subsequences of type $`12`$ (noninversions), one of type $`123`$, and no one of type $`12\mathrm{}k`$ for $`k4`$ in the corresponding permutation $`\pi =\mathrm{4\hspace{0.25em}7\hspace{0.25em}5\hspace{0.25em}2\hspace{0.25em}6\hspace{0.25em}3\hspace{0.25em}1}𝒮_7(1243,2143)`$

###### Remarks 4.3

*
* In particular, a permutation $`\pi 𝒮_n(1243,2143)`$ avoids $`12\mathrm{}k`$ if and only if the path $`\mathrm{\Psi }_{EM}(\pi )`$ has no step of height at least $`k1`$. This result is equivalent to Theorem 3.1.
* Combining $`\mathrm{\Psi }_{EM}:𝒮_n(1243,2143)S_{n1}`$ with the bijection $`\omega `$ stated in Corollary 3.4 yields the answer to the first part of the first problem raised in . (By $`S_{n1}`$ the set of Schröder paths from $`(0,0)`$ to $`(n1,n1)`$ is denoted.) The map $`\omega \mathrm{\Psi }_{EM}^1:S_{n1}𝒮_n(1243,2143)`$ takes every Schröder path whose maximum step height is at most $`k2`$ to a $`213\mathrm{}k`$-avoiding Schröder permutation, and is bijective, of course.
* Obviously, the path $`\mathrm{\Psi }_{EM}(\pi )`$ contains no diagonal step if and only if $`_0(\pi )=\mathrm{}`$. As already noted, then $`\pi _1=1`$ and $`\pi ^{}:=(\pi _21)(\pi _31)\mathrm{}(\pi _n1)`$ belongs to $`𝒮_{n1}(132)`$. In particular, we have $`\mathrm{\Psi }_{EM}(\pi )=\mathrm{\Psi }_K(\pi ^{})`$ in this case.

5 Perspectives

As already observed by Egge and Mansour in , the investigation of $`132`$-avoiding permutations and $`\{1243,2143\}`$-avoiding ones, respectively, can be continued in a canonical way. For $`m3`$ let $`T_m`$ be the set of permutations in $`𝒮_m`$ for which $`\pi _{m1}=m`$ and $`\pi _m=m1`$. For example, $`T_3=\{132\}`$ and $`T_4=\{1243,2143\}`$. (The integer sequences counting the permutations in $`𝒮_n(T_m)`$ were determined in .) Some of what we have done for $`132`$-avoiding permutations in , and for $`T_4`$-avoiding permutations in this paper can be generalized for an arbitrary integer $`m`$.

###### Theorem 5.1

A permutation $`\pi 𝒮_n`$ avoids each pattern in $`T_m`$ if and only if every element of its essential set is of rank at most $`m3`$.

Proof. If there exists an element $`(i,j)(\pi )`$ with $`\rho (i,j)m2`$ then at least $`m2`$ dots appear northwest of $`(i,j)`$. Consequently, there are integers $`i_1<i_2<\mathrm{}<i_{m2}<i`$ for which $`\pi _{i_1},\mathrm{},\pi _{i_{m2}}<j`$. Furthermore, we have $`i<i_{m1}`$ and $`\pi _i>j`$ where $`\pi _{i_{m1}}=j`$. Thus the subsequence $`\pi _{i_1}\mathrm{}\pi _{i_{m2}}\pi _i\pi _{i_{m1}}`$ forms a pattern belonging to $`T_m`$. (For a better understanding draw a picture similar that one in the proof of Theorem 2.1.)
On the other hand, it is clear from the diagram construction that the occurrence of a pattern of $`T_m`$ in a permutation yields a diagram corner of rank at least $`m2`$. $`\mathrm{}`$

In order to study increasing subsequences in permutations which belong to $`𝒮_n(T_m)`$ it would be nice to have a surjection $`𝒮_n(T_m)𝒮_n(T_{m1})`$ similar the map $`\varphi `$ stated in Section 2. Thus the problem could successively put down to the case $`m=3`$.
By reasoning similar to the proof of Theorem 3.3, one can show that this theorem holds for each $`m3`$ if $`k=3`$. In case $`k4`$ and $`m5`$, the condition $`i+jn+3k+\rho (i,j)`$ for all diagram corners $`(i,j)`$ is only sufficient for avoiding $`213\mathrm{}k`$ and all the patterns of $`T_m`$.
For example, the permutation $`\pi =\mathrm{5\hspace{0.25em}4\hspace{0.25em}7\hspace{0.25em}1\hspace{0.25em}3\hspace{0.25em}2\hspace{0.25em}6}𝒮_7(T_5)`$ avoids $`2134`$ but the square $`(1,4)`$ is a diagram corner of rank $`0`$.
Confirmed by computer tests, we believe in the Wilf-equivalence of $`T_m\{12\mathrm{}k\}`$ and $`T_m\{213\mathrm{}k\}`$ for all $`k1`$ and $`m3`$.

###### Conjecture 5.2

For $`m3`$, and all $`n`$ and $`k`$ we have

$$|𝒮_n(T_m\{12\mathrm{}k\})|=|𝒮_n(T_m\{213\mathrm{}k\})|.$$

References


format: text

text:
# Diquark interaction and gaps for color superconductivity

## Abstract

Using flow equations, we derive an effective quark-quark interaction and obtain the coupled set of gap equations for the condensates of the CFL phase of massless $`N_f=3`$ dense QCD. The formalism developed here enables one to consider more general case of nonzero $`s`$-quark mass.

We apply flow equations to the Coulomb gauge QCD Hamiltonian with $`N_f=3`$ at nonzero quark density. Coulomb gauge QCD Hamiltonian, $`A=0`$, at nonzero quark density

$`H`$ $`=`$ $`H_0+H_{inst}+H_{dyn},`$ (1)
includes the free Hamiltonian $`H_0`$, the instantaneous interaction $`H_{inst}`$ describing static properties, and the dynamical interaction $`H_{dyn}`$ involving gluon propagation. The free Hamiltonian is given by

$`H_0`$ $`=`$ $`{\displaystyle 𝑑𝒙\overline{\psi }(𝒙)\left(i𝜸\mathbf{}\mu \gamma _0+m\right)\psi (𝒙)}`$ (2)
$`+`$ $`\mathrm{Tr}{\displaystyle 𝑑𝒙\left(𝚷^2(𝒙)+𝑩_A^2(𝒙)\right)}.`$
The physical degrees of freedom are the transverse gluon field $`𝑨`$, its conjugate momentum $`\mathrm{\Pi }`$, and the quark field in the Coulomb gauge; $`𝑩_A`$ is the abelian component of the magnetic field. The instantaneous interaction is given by

$`H_{inst}`$ $`=`$ $`{\displaystyle \frac{1}{2}}{\displaystyle 𝑑𝒙𝑑𝒚\rho ^a(𝒙)V_{inst}^{ab}(𝒙,𝒚)\rho ^b(𝒚)},`$ (3)
where the quark charge density is $`\rho ^a(𝒙)=\overline{\psi }(𝒙)\gamma _0T^a\psi (𝒙)`$, and in the leading order the kernel is diagonal $`\delta ^{ab}`$ Coulomb potential $`V_{inst}(r)=\alpha _s/r`$ in coordinate space or $`V_{inst}(q)=g^2/𝒒^2`$ in momentum space. In high density quark matter the non-abelian contributions from three- and four-gluon interactions are suppressed. Therefore we consider only the quark-gluon interaction, $`H_{dyn}=V_{qg}`$,

$`V_{qg}`$ $`=`$ $`g{\displaystyle 𝑑𝒙\overline{\psi }(𝒙)𝜸𝑨(𝒙)\psi (𝒙)},`$ (4)
in dense QCD.

We eliminate the quark-gluon coupling by the first order flow equation $`dV_{qg}/dl=[[H_0,V_{qg}],H_0]`$. As a result, in the second order we generate the dynamical interaction between quarks $`dV_{dyn}/dl=[[H_0,V_{qg}],V_{qg}]_{twoparticles}`$, and the quark self-energy $`d\mathrm{\Sigma }_{dyn}/dl=[[H_0,V_{qg}],V_{qg}]_{oneparticle}`$ in the channel of $`qq`$-pair creation/annihilation. The resulting diquark interaction and self-energy include dynamical terms generated by flow equations, $`V_{dyn}(\mathrm{\Lambda }0)`$ and $`\mathrm{\Sigma }(\mathrm{\Lambda })`$, respectively, and the instantaneous terms in corresponding channels, i.e. $`V_{qq}=V_{dyn}+V_{inst}`$ and $`\mathrm{\Sigma }_{qq}=\mathrm{\Sigma }_{dyn}(\mathrm{\Lambda })+\mathrm{\Sigma }_{inst}(\mathrm{\Lambda })+CT(\mathrm{\Lambda })`$. Here $`\mathrm{\Lambda }`$ is the UV cutoff connected to the flow parameter $`l`$ as $`l=1/\mathrm{\Lambda }^2`$, and $`CT(\mathrm{\Lambda })`$ are the second order counterterms. Having the effective interaction between quarks $`V_{qq}`$, we allow for diquark condensation, which can be parametrized as  $`\mathrm{\Delta }_{\alpha \gamma }^{ij}(𝒑)=3\left(\frac{1}{3}\left[\mathrm{\Delta }_8(𝒑)+\frac{1}{8}\mathrm{\Delta }_1(𝒑)\right]\delta _\alpha ^i\delta _\gamma ^j+\frac{1}{8}\mathrm{\Delta }_1(𝒑)\delta _\gamma ^i\delta _\alpha ^j\right)`$, where $`\mathrm{\Delta }_1`$ and $`\mathrm{\Delta }_8`$ are the eigenvalues of $`\mathrm{\Delta }_{\alpha \gamma }^{ij}`$ in the CFL basis. Here $`i,j`$ are flavor and $`\alpha ,\gamma `$ color indices, which are substituted by $`\rho `$ index in the CFL basis, $`b(𝒌)_\alpha ^i=_\rho \lambda _{i\alpha }^\rho b(𝒌)^\rho /\sqrt{2}`$, $`\lambda ^\rho `$ are the Gell-Mann matrices for $`\rho =1,\mathrm{},8`$ and $`\lambda ^9=\sqrt{2/3}`$. Combining all the terms the high density effective Hamiltonian is given by

$`H_{eff}`$ $`=`$ $`H_0+\mathrm{\Sigma }_{qq}+V_{qq}.`$ (5)
Using Weyl spinors, the individual terms are written in the CFL basis as

$`H_0`$ $`=`$ $`{\displaystyle \underset{𝒌,\rho }{}}|k\mu |b_\rho ^{}(𝒌)b_\rho (𝒌)+{\displaystyle \underset{𝒌}{}}ka^{}(𝒌)a(𝒌)`$
$`\mathrm{\Sigma }_{qq}`$ $`=`$ $`{\displaystyle \frac{1}{2}}{\displaystyle \underset{𝒑,\rho }{}}\mathrm{\Delta }_\rho (𝒑)\mathrm{e}^{i\varphi (𝒑)}b_\rho (𝒑)b_\rho (𝒑)+c.c.`$
$`V_{qq}`$ $`=`$ $`{\displaystyle \underset{𝒌,𝒑,\rho ,\rho ^{}}{}}V_{qq}^{\rho \rho ^{}}(k,p)c^{\rho \rho ^{}}\mathrm{e}^{i\varphi (𝒌)}\mathrm{e}^{i\varphi (𝒑)}`$ (6)
$`\times `$ $`b_\rho ^{}(𝒌)b_\rho ^{}(𝒌)b_\rho ^{}(𝒑)b_\rho ^{}(𝒑),`$
where $`_𝒌=𝑑𝒌/(2\pi )^3`$, and $`c^{\rho \rho ^{}}=1`$ for $`(\rho ,\rho ^{})=(1,8)`$ or $`(8,1)`$, $`c^{\rho \rho ^{}}=2`$ for $`(\rho ,\rho ^{})=(8,8)`$ and $`c^{\rho \rho ^{}}=0`$ for $`(\rho ,\rho ^{})=(1,1)`$. We did not include antiparticles since their contribution is suppressed near the Fermi surface. Performing the Bogoliubov-Valatin transformation for quark fields from $`(b,b^{})`$ to $`(y,y^{})`$, we absorb the self-energy into the new free Hamiltonian , $`H_0+\mathrm{\Sigma }_{qq}\stackrel{~}{H}_0`$,

$`\stackrel{~}{H}_0`$ $`=`$ $`{\displaystyle \underset{𝒌,\rho }{}}E_\rho (𝒌)y_\rho ^{}(𝒌)y_\rho (𝒌)`$ (7)
$`+`$ $`{\displaystyle \underset{𝒌}{}}\omega (𝒌)a^{}(𝒌)a(𝒌),`$
where the effective quark energy is given by $`E_\rho (𝒌)=\sqrt{(k\mu )^2+\mathrm{\Delta }_\rho (𝒌)^2}`$, and the gluon energy $`\omega `$ includes polarization effects of a gluon propagating in the quark medium. The resulting high density effective Hamiltonian is given by

$`H_{eff}`$ $`=`$ $`\stackrel{~}{H}_0+V_{qq},`$ (8)
where $`V_{qq}`$ Eq. (6) is also subject to the BV transformation. $`H_{eff}`$ describes dynamics of quarks near the Fermi surface in dense QCD. In order to make calculations selfconsistent we use $`\stackrel{~}{H}_0`$ instead of $`H_0`$ in the flow equations.

Further we specify the terms in the high density effective Hamiltonian $`H_{eff}`$ Eq. (8) or Eq. (5). The kernel of the effective diquark interaction Eq. (6) is given by

$`V_{qq}^{\rho \rho ^{}}(𝒌,𝒑)`$ $`=`$ $`V_{dyn}^{\rho \rho ^{}}(𝒌,𝒑)\left({\displaystyle \frac{3\widehat{k}\widehat{p}}{2}}\right)`$ (9)
$`V_{inst}^{\rho \rho ^{}}(𝒌,𝒑)\left({\displaystyle \frac{1+\widehat{k}\widehat{p}}{2}}\right),`$
where

$`V_{dyn}^{\rho \rho ^{}}(𝒌,𝒑)`$ $`=`$ $`{\displaystyle \frac{2g^2}{3}}{\displaystyle \frac{1}{\delta E^{\rho \rho ^{}}(𝒌,𝒑)^2+\omega _M(𝒌𝒑)^2}}`$
$`V_{inst}(𝒌,𝒑)`$ $`=`$ $`{\displaystyle \frac{2g^2}{3}}{\displaystyle \frac{1}{\omega _E(𝒌𝒑)^2}}.`$ (10)
and the energy difference of in- and out-going quarks is $`\delta E^{\rho \rho ^{}}(𝒌,𝒑)=E^\rho (𝒌)E^\rho ^{}(𝒑)`$. Gluon energy, $`\omega (𝒒)^2=𝒒^2+M(𝒒)^2`$, contains the Debye screening mass for electric gluon, $`M_E^2g^2\mu ^2N_f`$, and the Landau damping mass for magnetic gluon, $`M_M(𝒒)^2g^2\mu ^2N_fE(𝒒)/|𝒒|`$. In the magnetic interaction $`V_{dyn}`$ both factors $`\delta E^2`$ and Landau damping mass $`M_M^2`$ are dynamical, i.e. they depend on energies/momenta. Dispersion relation is $`|𝒒|E(𝒒)`$ when $`\delta E^2`$ is taken into account, and it changes to $`|𝒒|E(𝒒)^{1/3}`$ for Landau damping. Effective gluon dispersion determines the numerical factor in exponent for the gap solution. Dynamical magnetic interaction generated by flow equations has the form $`1/(𝒒^2+\delta E^2)`$ as compared with the equal time perturbation theory result (or interaction obtained in the second order via Frölich transformation) $`1/(𝒒^2\delta E^2)`$ where the energy difference has opposite sign. The latter interaction has an unphysical pole. To avoid it $`\delta E^2`$ is usually neglected near the Fermi surface. This is a valid argument when only the BCS singularity through the anomalous quark propagator is present, and the gluon propagator $`1/𝒒^2`$ is replaced by a point-like interaction in the gap equation. However in our case of a regular interaction it is safe to keep $`\delta E^2`$, which might play a role of the IR regulator in the collinear limit $`𝒒0`$.

The system of gap equations for the condensates defined in Eq. (6) is given by

$`\mathrm{\Delta }_1(𝒑)`$ $`=`$ $`8G^{81}(𝒑)`$
$`\mathrm{\Delta }_8(𝒑)`$ $`=`$ $`G^{18}(𝒑)2G^{88}(𝒑),`$ (11)
where the integral in the right hand side

$`G^{\rho \rho ^{}}(𝒑)`$ $`=`$ $`{\displaystyle \frac{1}{4}}{\displaystyle \frac{d𝒌}{(2\pi )^3}\frac{1}{2}\frac{\mathrm{\Delta }_\rho (𝒌)}{E_\rho (𝒌)}}`$
$`\times `$ $`V_{qq}^{\rho \rho ^{}}(𝒌,𝒑)R^{\rho \rho ^{}}(𝒌,𝒑;\mathrm{\Lambda })+CT(\mathrm{\Lambda }),`$
includes the anomalous $`3`$-d quark propagator, $`\mathrm{\Delta }_\rho /2E_\rho `$, the effective gluon propagator in the form of the effective diquark interaction, $`V_{qq}`$, given in Eq. (9), and the UV regulating function $`R^{\rho \rho ^{}}(𝒌,𝒑;\mathrm{\Lambda })=\mathrm{exp}\left([𝒌𝒑]^2/\mathrm{\Lambda }^2\right)`$. Regulating function generated by flow equations is $`\mathrm{exp}\left([\delta E^{\rho \rho ^{}}(𝒌,𝒑)^2+\omega _M(𝒌𝒑)^2]/\mathrm{\Lambda }^2\right)`$, which we approximate by $`\mathrm{exp}\left([𝒌𝒑]^2/\mathrm{\Lambda }^2\right)`$ for high densities. It is important that the UV regulator $`R^{\rho \rho ^{}}`$ arises automatically from flow equations that supports an underlying concept of flow equations being a renormalization group method. $`CT(\mathrm{\Lambda })`$ is the second order local counterterm chosen from the requirement that the condesates do not depend on the UV cutoff, $`d\mathrm{\Delta }_i/d\mathrm{\Lambda }=0`$ for $`i=1,8`$. Calculations by flow equations are done in the gapped theory that is reflected by the energies $`E(𝒌)`$ containing condensates.

System of gap equations, Eqs. (11,Diquark interaction and gaps for color superconductivity), can be solved only numerically. However, an approximate analytical analyses can be done by converting integral gap equation into differential one . Approximate solution is given by $`\mathrm{\Delta }_i=\mathrm{\Delta }_0^{(i)}\mathrm{sin}(\overline{g}x)`$ with $`\mathrm{\Delta }_0^{(i)}=2b_i\mu \mathrm{exp}(\pi /2\overline{g})`$ for $`i=1,8`$, where $`x`$ is a new energy variable, $`\overline{g}`$ is an effective coupling proportional to $`g`$ and depending on effective gluon dispersion, and $`b_i`$ are numerical factors ($`b_1=2b_8`$ for color and flavor antisymmetric condensate). Integral $`G`$ in the right hand side of the gap equation, Eq. (Diquark interaction and gaps for color superconductivity), has the collinear (through the gluon propagator) and the BCS (through the quark propagator) IR singularities. Together these singularities give double logarithm structure for $`G`$ and characteristic enhanced solution $`\mathrm{\Delta }_0\mathrm{exp}(c/g)`$ for color superconductivity instead of the BCS solution $`\mathrm{exp}(c/g^2)`$. BSC singularity is regulated by the condensate $`\mathrm{\Delta }_\rho `$ in the energy $`E_\rho `$. In the case of all three quarks are massless, the collinear singularity is cutoff by $`\delta E(𝒌,𝒑)^2`$ for the momenta close to the Fermi surface $`|𝒌\mu |\mathrm{\Delta }`$ and by the Landau damping factor $`M_M(𝒌,𝒑)^2`$ for the momenta away from the Fermi surface $`\mathrm{\Delta }|𝒌\mu |\mu `$. Landau damping of a magnetic gluon is calculated in a quark-gluon plasma, which is a normal phase, since for large momenta gluon distingiushes individual quarks in a Cooper pair and effectively ’sees’ quark plasma rather than a superconducting state. For massless quarks and zero temperatures the characteristic double logaritm in $`G`$ which leads to enhanced solution is saturated by momenta away from the Fermi surface, and hence as first realized by Son Landau damping determines the gap . Changing parameters may change numerical factors in the solution for the gap. In the case of massive $`s`$-quark, $`m_u,m_dm_s`$, the factor $`\delta E^2`$ might regulate the collinear singularity contributing to the condensate $`\mathrm{\Delta }`$.

Generalization to nonzero temperature is done by inserting factor $`\mathrm{tanh}(E_\rho (𝒌)/2T)`$ into $`G`$, Eq. (Diquark interaction and gaps for color superconductivity). We assume that the effective gluon mass is not affected by small temperatures, since $`Mg\mu `$ and $`T\mathrm{\Delta }g\mu `$ otherwise superconducting condensate will melt. For the momenta away from the Fermi surface, $`\mathrm{\Delta }|𝒌\mu |\mu `$, $`\mathrm{tanh}(E(𝒌)/2T)1`$, hence there are no temperature effects for large energies. For the momenta close to the Fermi surface, $`|𝒌\mu |\mathrm{\Delta }`$, temperature distribution factor is important. Thus only region around the Fermi surface is affected by the temperature. However, this region of momenta does not contribute to the double logarithm of $`G`$ and hence to the enhanced gap, but rather to the BCS solution (momenta close to the Fermi surface give single logarithm). Therefore, temperature dependence of the condensate is of the BCS type, i.e. $`\mathrm{\Delta }(T)\mathrm{\Delta }(T=0)\left(1T/T_c\right)^{1/2}`$ with the connection between zero temperature condensate and the critical temperature given by $`T_c=0.577\mathrm{\Delta }(T=0)`$.

In conclusion, we obtained an effective high density Hamiltonian for superconductivity which includes an effective interaction between quarks. Also we obtained the coupled set of gap equations for the condensates of the CFL phase of massless $`N_f=3`$ dense QCD. The formalism used enables one to consider a more general case of nonzero $`s`$-quark mass.


text:
# A new Eulerian-Lagrangian length-scale in turbulent flows

## I Introduction

Turbulent diffusion is a phenomenon of central importance in oceanic, atmospheric, engineering and astrophysical flows. It is known, since the seminal work of Taylor , that the turbulent diffusivity (of contaminants, pollutants or other substances advected by the turbulent flow) is proportional to the time-integral of the Lagrangian velocity autocorrelation function $`R_L(\tau )`$ of the turbulence. The Lagrangian study of fluid element trajectories is therefore central to understanding and calculating turbulent diffusion.

A consequence of Taylor’s (1921)  theory is that the turbulent diffusivity is larger/smaller depending on whether Lagrangian velocities are correlated over longer/shorter times along trajectories. Such long/short correlation times reflect large/small Lagrangian velocity variations, and Lagrangian velocity variations over a time interval $`\tau `$ are characterized by the second order Lagrangian structure function which is proportional to $`1R_L(\tau )`$. In statistically stationary and isotropic turbulence it is sufficient to consider only one component of the Lagrangian velocity, say $`v(t)`$; its second order structure function is $`\delta v^2(\tau )(v(t)v(t+\tau ))^2`$ corresponding to the Lagrangian velocity power spectrum $`E_L(\omega )`$ in the frequency ($`\omega `$) domain. As noted by Inoue  (see also Tennekes & Lumley ), Kolmogorov similarity arguments imply that, in the inertial range of times and frequencies, $`\delta v^2(\tau )ϵ\tau `$ and $`E_L(\omega )ϵ\omega ^2`$ where $`ϵ`$ is the kinetic energy dissipation rate per unit mass. Support for these scalings has recently been obtained in highly turbulent oceanic environments by Lien et al. , in the laboratory by Mordant et al.  and in Direct Numerical Simulations (DNS) by Yeung . However, Kolmogorov similarity arguments provide very little understanding of the underlying processes responsible for these scaling laws. What properties of the spatio-temporal flow structure of the turbulence determine that $`\delta v^2(\tau )`$ is proportional to $`\tau `$, and what do these properties imply for turbulent diffusion?

In this letter we address this question by use of Kinematic Simulation (KS, see Nicolleau & Vassilicos , Davila & Vassilicos  and references therein). KS is a Lagrangian model of turbulent diffusion based on kinematically simulated turbulent velocity fields which are incompressible and consistent with up to second order Eulerian statistics of the turbulence such as energy spectra $`E(k)`$ in the wavenumber ($`k`$) domain. There is no assumption of Markovianity or delta correlation in time made at any level. Instead, a parameter $`\lambda `$ controls the degree of unsteadiness of the turbulence. It might be worth mentioning that, when the energy spectrum input has the Kolmogorov $`k^{5/3}`$ form, KS is in good agreement with laboratory experiments for one-particle statistics , two-particle statistics , three-particle statistics  and concentration variances  (particle is used here to mean fluid element). KS is also in good agreement with DNS for two-particle statistics when the KS energy spectrum has the same overall shape as that of the DNS . In this letter, we modify the spatio-temporal flow structure of the KS turbulence by changing the input energy spectrum $`E(k)`$ and the input unsteadiness parameter $`\lambda `$ and study how $`\delta v^2(\tau )`$ changes as a result.

## II Kinematic simulation

In our KS we use 3D turbulent-like velocity fields of the form

$`𝐮={\displaystyle \underset{n=1}{\overset{N_k}{}}}𝐀_n\widehat{𝐤}_n\mathrm{cos}(𝐤_n𝐱+\omega _nt)`$ $`+`$ (1)
$`𝐁_n\widehat{𝐤}_n\mathrm{sin}(𝐤_n𝐱+\omega _nt)`$ (2)
where $`N_k`$ (typically of order 100) is the number of modes, $`\widehat{𝐤}_n`$ is a random unit vector ($`𝐤_n=k_n\widehat{𝐤}_n`$), and the directions and orientations of $`𝐀_n`$ and $`𝐁_n`$ are chosen randomly under the constraint that they be normal to $`\widehat{𝐤}_n`$ and uncorrelated with the directions and orientations of all other wave modes. Note that the velocity field (2) is incompressible by construction, and also statistically stationary, homogeneous and isotropic as shown by Fung et al.  and Fung & Vassilicos . The amplitudes $`A_n`$ and $`B_n`$ of the vectors $`𝐀_n`$ and $`𝐁_n`$ are determined by $`A_n^2=B_n^2=\frac{2}{3}E(k_n)\mathrm{\Delta }k_n`$ where $`E(k)`$ is the energy spectrum prescribed to be of the form

$$E(k)=\frac{v^2(p1)}{2(L/2\pi )^{p1}}k^p$$
(3)
in the range $`2\pi /L=k_1kk_{N_k}=2\pi /\eta `$ assumed large (i.e. $`L/\eta 1`$), and $`E(k)=0`$ otherwise; $`v^{}`$ is the rms of one velocity component of the KS turbulent-like flow; $`\mathrm{\Delta }k_n=(k_{n+1}k_{n1})/2`$ for $`2nN_k1`$, $`\mathrm{\Delta }k_1=(k_2k_1)/2`$ and $`\mathrm{\Delta }k_{N_k}=(k_{N_k}k_{N_k1})/2`$. The distribution of wavenumbers is geometric (see ), specifically $`k_n=k_1a^{n1}`$ with a constant $`a`$ determined by $`L/\eta =a^{N_k1}`$. The frequencies $`\omega _n`$ in (2) are proportional to the eddy-turnover frequency of mode $`n`$, and the dimensionless constant of proportionality is $`\lambda `$, i.e. $`\omega _n=\lambda \sqrt{k_n^3E(k_n)}`$.

Particle trajectories are numerically integrated in (2) and the velocities of the particles are recorded along their flight. By averaging over $`5\times 10^3`$ trajectories in $`5\times 10^3`$ realizations of the velocity field we obtain $`\delta v^2(\tau )`$ for different values of $`p`$ and $`\lambda `$ (see Fig. 1 which has been obtained for $`L/\eta =1690`$, but note that we corroborated these results for much higher values of $`L/\eta `$ too). We try values of $`p`$ larger than 1 to ensure that the total kinetic energy of the turbulence is finite in the large $`L/\eta `$ limit, and values of $`p`$ smaller than 2 for the power spectrum $`k^2E(k)`$ of the vorticity and strain rate fields to be an increasing function of $`k`$ (see ).

## III Results

A first observation is that when $`E(k)`$ has the Kolmogorov similarity dependence on wavenumber (i.e. $`p=5/3`$), $`\delta v^2(\tau )`$ exhibits the Kolmogorov similarity scaling $`\delta v^2(\tau )\tau `$ over an intermediate range of time-scales only for large enough values of $`\lambda `$ and not otherwise. This intermediate range of scales turns out to be $`t_\eta \tau T_L`$ where $`t_\eta =2\pi /\omega _{N_k}`$. For values of $`\lambda `$ smaller than 1 and close to 0 as well as equal to 0, we find $`\delta v^2(\tau )\tau ^{2/3}`$ over the intermediate range $`\tau _\eta \tau T_L`$ where $`\tau _\eta 2\pi /\sqrt{(2\pi /\eta )E(2\pi /\eta )}`$ and $`T_L_0^{\mathrm{}}R_L(\tau )𝑑\tau `$ ($`t_\eta =\tau _\eta /\lambda `$). Fung et al.  have already observed this 2/3 scaling in frozen ($`\lambda =0`$) KS turbulence and added to (2) a sweeping of the small-scales (2) by larger small-scales which restored the Kolmogorov similarity scaling $`\delta v^2(\tau )\tau `$. Hence, large values of the unsteadiness parameter $`\lambda `$ reproduce this sweeping effect on the scaling of $`\delta v^2(\tau )`$. Kolmogorov similarity is conditional on large values of the dimensionless parameter $`\lambda `$, perhaps a surprising result.

Running simulations for a variety of values of $`p`$ between 1 and 2 we find

$$\delta v^2(\tau )\tau ^\alpha $$
(4)
in the intermediate ranges mentioned above and $`\alpha =\alpha (p,\lambda )`$ (see figures 1 and 2). For values of $`\lambda `$ smaller than 1 including $`\lambda =0`$,

$$\alpha =p1,$$
(5)
but for values of $`\lambda `$ much larger than 1, $`\alpha `$ is a monotonically increasing nonlinear function of $`p`$, in fact the same function of $`p`$ for all large enough $`\lambda `$, and is such that $`\alpha >p1`$ and $`\alpha =1`$ at $`p=5/3`$. What is this function of $`p`$?

To answer this question we proceed by analogy with Richardson’s locality hypothesis for two-particle diffusion in statistically homogeneous turbulence. According to this hypothesis, the rate of change of the mean square separation between two particles, i.e. $`\frac{d}{dt}\mathrm{\Delta }^2`$, is a function only of $`\mathrm{\Delta }^2`$ and of the variance of Eulerian velocity variations across that length-scale (see ). That is

$$\frac{d}{dt}\mathrm{\Delta }^2=f(\mathrm{\Delta }^2,\delta u^2(\sqrt{\mathrm{\Delta }^2}))$$
(6)
where $`\delta u^2(r)`$ is the second order structure function of one component of the Eulerian velocity field. It is well known that $`\delta u^2(r)r^{p1}`$ for small enough values of $`r`$ is equivalent to $`E(k)k^p`$ for large enough values of $`k`$. The analogy we are trying here, which we call the inverse locality hypothesis, is to say that the rate of change of $`\delta v^2(\tau )`$ with respect to $`\tau `$ is a function only of $`\delta v^2(\tau )`$ and of the length-scale across which the variance of Eulerian velocity variations is equal to $`\delta v^2(\tau )`$. That is

$$\frac{d}{d\tau }\delta v^2(\tau )=f(\delta v^2(\tau ),l_e(\tau ))$$
(7)
where $`l_e(\tau )`$ is an Eulerian-Lagrangian length-scale defined as follows:

$$\delta u^2(l_e(\tau ))=\delta v^2(\tau ).$$
(8)
We call $`l_e(\tau )`$ the equivalent length-scale. Dimensional analysis applied to (7) and use of (8) and $`\delta u^2(r)r^{p1}`$ leads to (4) with

$$\alpha =\frac{2(p1)}{3p}.$$
(9)
This dependence of $`\alpha `$ on $`p`$ fits surprisingly well the results obtained by KS for large values of $`\lambda `$ (see Fig. 2). These results reveal, therefore, the existence of an Eulerian-Lagrangian length-scale $`l_e(\tau )`$ which controls the second order Lagrangian structure function and Lagrangian frequency spectrum provided that the sweeping effects are taken into account by high values of $`\lambda `$. Our results (figures 1 and 2 and equations (5) and (9)) also reveal the impact that the two-point spatial flow structure (as reflected in the scaling of the energy spectrum) has on one-particle Lagrangian statistics whether with or without sweeping.

Changes in $`\delta v^2(\tau )`$ imply changes in $`R_L(\tau )`$ and therefore in turbulent diffusion. Taylor’s (1921) formula for the mean square one-particle displacement $`x^2(t)`$ is

$$\frac{d}{dt}x^2(t)=v^2_0^tR_L(\tau )𝑑\tau $$
(10)
which implies a turbulent diffusivity equal to $`v^2T_L`$. Of course this relation remains valid in our KS for any value of $`p`$ but the Lagrangian correlation time scale $`T_L`$ is found to be an increasing function of $`p`$ (see Fig. 3 ), thus implying a turbulent diffusivity that is also an increasing function of $`p`$. This conclusion can be explained qualitatively by the relation $`p+2D_s/3=3`$ between $`p`$ and the fractal dimension $`D_s`$ of the set of straining stagnation points that has recently been obtained by Davila & Vassilicos  for KS turbulence. As $`p`$ decreases, $`D_s`$ increases implying an increase in the number density of straining stagnation points and thereby an increased probability for particle trajectories to come in the vicinity of such points and experience sudden changes of tack. As a consequence, the Lagrangian correlation time scale is smaller/larger for smaller/larger values of $`p`$. In terms of $`D_s`$, $`\alpha =2\frac{3D_s}{D_s}`$ when $`\lambda `$ is large and $`\alpha =\frac{2}{3}(3D_s)`$ when $`\lambda `$ is small; $`\alpha `$ is therefore a decreasing function of $`D_s`$ thus reflecting the fact that a larger number of changes of tack produces more irregular particle trajectories.

## IV Acknowledgements

MAIK and JCV acknowledge support from EPSRC grant GR/K50320, from EC TMR Research network on intermittency in turbulent systems and from the Hong Kong Research Grant Council, China (Project No. HKUST6121/00P). MAIK also wishes to thank the Cambridge Commonwealth Trust, Wolfson College, Cambridge and DAMTP for financial support while this work was being completed. JCV is grateful to the Royal Society of London for its unflinching support over the past eight years.


text:
# Depinning by Fracture in a Glassy Background

\[

## Abstract

We force a single particle through a two-dimensional simulated glass. We find that the particle velocity obeys a robust power law that persists to drives well above threshold. As the single driven particle moves, it induces cooperative distortions in the surrounding medium. We show theoretically that a fracture model for these distortions produces power law behavior, and discuss implications for experimental probes of soft matter systems.

\]

Recently, there has been considerable interest in the behavior of systems of interacting particles that resist flow, including vortex glasses in superconductors , charge-density-wave metals, Wigner crystals , dense colloidal suspensions, and Coulomb-blockade arrays. In each of these systems, quenched disorder and repulsive interactions from the surrounding particles prevent any individual particle from moving in response to a small external force. As a result, below a threshold force, the system behaves as a solid, while above the threshold, the system can flow plastically and is soft and disordered. Once the system depins, increasing the force leads to rapidly increasing motion, as the speed and transport response increase faster than linearly with the flow over a range of applied force. Theories have attributed this anomalous transport to the concerted action of many driven particles across a rough pinscape. They predict power-law growth of the velocity with force in the vicinity of a threshold force $`F_c`$: $`v(FF_c)^\beta `$. In experiments and simulations, the velocity above threshold has been observed to vary as a power $`\beta `$ of the force, with $`\beta `$ in the range 1.5 to 2.2 . In contrast to the critical-state model of elastic depinning, where scaling occurs only very close to threshold, the power law is observed to hold for forces of several times the threshold force.

In this work we demonstrate power-law collective transport with a single driven particle in a disordered glassy matrix of other non-driven particles in two dimensions, realized via a molecular-dynamics simulation. We find a power law with $`\beta =1.5`$ over two decades of force that is insensitive to the system size, the size of the driven particle, or the density of the surrounding medium. This contrasts with a single particle driven over a substrate with quenched disorder where a scaling of $`\beta =1/2`$ is expected . Our result suggests that the origin of the $`\beta >1`$ scaling in a variety of systems may be simpler than previously supposed. A single driven particle drags other particles with it, thus slowing it down. The faster it moves, the fewer particles it drags, and hence the exponent $`\beta `$ becomes larger than $`1.0`$. We explicitly show that an analysis in terms of fracture in front of the particle gives $`\beta =1.5`$. The fracture leads to a one dimensional (1D) plastic zone, which appears as a river-like flow of particles. While in other cases such rivers are attributed to easy paths through a background of quenched disorder, in our system the only disorder is due to the glassiness of the medium. The plastic zone appears due to the softness of the system; for stiffer interactions, the plastic zone disappears and $`\beta =1`$ is the observed scaling.

In addition to offering a simpler model of depinning, our results are relevant to systems in which two species of particles move in opposite directions with respect to each other. Such situations can arise in certain types of electrophoresis experiments, pedestrian motion, self driven particles and molecular motors , as well as in vortex experiments in which a vortex lattice is driven past a low density of pinning sites.

Further, driving a single particle through a soft matter system can be used as a powerful experimental probe of dynamics of the medium far from equilibrium. For example, in recent experiments a magnetic particle is dragged through a colloidal system near the glass transition. The absence of momentum conservation in our system leads to very different physics from the transfer of momentum through hydrodynamic and hard-core interactions. However, such experiments on colloidal systems and emulsions in confined geometries, in particular between parallel walls, are predicted to have similar features to those found here.

Simulations and Dissipation Balance– We drive a single particle with a charge $`q_D`$ at constant force through a two dimensional (2D) disordered system with periodic boundary conditions in the $`x`$ and $`y`$ directions. To create a glassy medium and prevent formation of a triangular lattice, we simulate a mixture of two species of particles with different charges $`q_A=q`$ and $`q_B=2q`$, where $`q=1`$. For the driven particle, we consider a range of values from $`q_D=0.15q`$ to $`q_D=60q`$. The overdamped equation of motion for particle $`i`$ is $`\eta 𝐯=𝐟_i=_jU(r_{ij})+F_d\widehat{𝐱}`$, where $`𝐯`$ is the particle velocity, the damping coefficient $`\eta =1`$, and $`F_d=0`$ on all particles except the one with charge $`q_D`$. We use a screened Coulomb interaction, given by:

$$U(r_{ij})=q_iq_j\frac{e^{2r_{ij}}}{r_{ij}},$$
(1)
between particles $`i`$ and $`j`$ separated by a distance $`r_{ij}`$. We have considered a variety of system sizes for $`N=480`$ and $`N=2150`$ particles, as well as lattice constants of $`a=1.08`$ to $`2.3`$.

In Fig. 1 we show the positions of the particles and the trajectories for a fixed number of time steps for a system with $`N=2100`$ particles at a drive $`F_d=0.75`$. The driven particle, marked as a large dot, has $`q_D=20`$. We find that in general there is a finite threshold force $`F_c`$ for the particle to move. The perturbation of the other particles by the driven particle is anisotropic, with a larger perturbation in the direction of drive than in the transverse direction. Particles more than a few $`a`$ away from the path of the driven particle move elastically in small nearly closed orbits of radius less than $`a`$. Particles in front and behind the driven particle exhibit plastic motion. This plastic zone decreases in size for higher velocities.

The medium, while disordered, is a solid. It has a threshold, $`F_d=F_c`$, for failure, and can support shear stress. Thus, the particle must fracture the medium to move through it. From momentum balance, we have that at all times $`F_d=\eta V+\eta v_A`$, where $`V`$ is the velocity of the driven particle and the sum ranges over all other particles. Below threshold, where the medium moves with the particle, the momentum balance yields $`V=F_d/N`$, where $`N`$ is the number of particles. Above threshold, to obtain power law scaling, some large number $`n`$ of other particles, $`1nN`$, must move with the driven particle, with some finite size corrections to scaling due to net background motion of the remaining $`Nn`$ particles. Eventually, as $`n1`$ far above threshold, the velocity returns to linear scaling.

In Fig. 2 (lower solid curve) we show the log-log plot for the velocity vs applied drive $`F_dF_c`$, for the driven particle in Fig. 1, where $`F_c=0.7`$ is the threshold for the large particle to move. We find a good scaling with a fit of $`\beta =1.47\pm 0.03`$. We find a similar scaling for a variety of other parameters with the exponents of $`1.5\pm 0.05`$. At sufficiently large drive, $`\beta `$ returns to 1, as expected. The size of the scaling region decreases with decreasing $`q_D/q`$, until for $`q_D/q<1.0`$, no anomalous scaling is observed. In this case the driven particle does not induce plasticity in the other particles but only a smaller perturbation of size less than $`a`$. In the upper solid curve in Fig. 2 we show the velocity force curve for $`q_D=0.5`$ showing a scaling fit with $`\beta =1.0`$. For a fixed value of $`F_d`$ the velocity decreases with increasing $`q_D`$ as the driving particle interacts more strongly with the surrounding particles. In Fig. 3(b), $`V`$ vs $`q_D`$ for $`F_d=4.0`$ shows a $`q_D^{1/2}`$ scaling in the regime where there is plastic deformation, and then $`V`$ flattens out in the elastic regime for $`q_D<1`$. Additionally in the plastic flow regime the particle motion is highly intermittent as illustrated in Fig. 3(a), where a time trace of $`V`$ for $`q_D/q=20.0`$ shows the motion occurring in bursts separated by quiet periods. As the drive increases, the motion becomes less intermittent, and the noise spectrum of the time trace develops a well-defined rollover frequency $`\omega `$, with $`\omega `$ scaling approximately linearly in $`F_dF_c`$. We find that the rollover frequency corresponds to the time scale between peaks in Fig. 3(a), rather than to the duration of a single peak.

In Fig. 4, we show a contour plot of the average of $`v^2`$ for the other particles in the medium, as a function of position relative to the driven particle, for systems with $`q_D/q=20`$, $`N=2100,a=1.085`$ and $`F_d=0.9,1.5,`$ and $`40`$ respectively. This measures energy dissipation, as from energy balance $`F_d\overline{V}=\eta (\overline{V^2}+\overline{v_A^2})`$. These systems are above the depinning threshold of $`0.7`$, but still within the scaling regime. The dissipation is centered strongly around the moving particle, and extends anisotropically into the surrounding medium, with a larger region of dissipation in the direction of drive.

Theory: Elasticity and Fluid Flow— We now consider various scenarios for the particle motion to understand the simulation results. We begin by considering the response of the medium away from the plastic zone, where the particles move less than $`a`$ and elasticity theory is applicable. The driven particle exerts a force on the elastic medium at a location that is moving at velocity $`\overline{V}`$. At long wavelengths, elasticity theory gives for a lattice displacement $`\stackrel{}{u}(\stackrel{}{k})`$ the equation of motion

$$\dot{\stackrel{}{u}}(\stackrel{}{k})=C_1\stackrel{}{k}(\stackrel{}{k}\stackrel{}{u})+C_2\stackrel{}{k}\times (\stackrel{}{u}\times \stackrel{}{k}).$$
(2)
To obtain elastic constants $`C_1,C_2`$, we consider a triangular lattice of particles, with appropriate lattice constant $`a`$, and assume that all particles have the same charge, $`q_{A,B}=\sqrt{2}q`$. For a lattice constant $`a=1.085`$ and the chosen $`q0.086`$, one finds $`C_10.025/\eta ,C_20.0018/\eta `$. The particle exerts a force on this medium, along the direction of motion of the particle. There is also a force normal to this direction, pushing the medium out sideways in opposite directions on opposite sites of the moving fracture. In the co-moving frame, the displacement in any given direction decays exponentially at large distance with a characteristic length $`l=C_1/\overline{V}`$ along that direction and $`l=C_2/\overline{V}`$ normal to the direction. The energy dissipation rate resulting is of order $`\eta \overline{V}^2(l/a)^2=\eta C_1C_2/a^2`$, and is thus independent of $`\overline{V}`$. This indicates a force on the driven particle of order $`1/\overline{V}`$, in addition to the drag force, $`\eta \overline{V}`$, on the driven particle. For small $`\overline{V}`$, this force becomes arbitrarily large, ultimately exceeding the yield stress of the medium. In such a region the material must yield and the elastic picture becomes invalid.

Thus, we must consider the plastic zone. It is not consistent to have a 2D chunk of solid moving with the particle, with a plastic zone between that solid and the rest of the medium: if the particle force is sufficient to fracture the medium, it would fracture the solid moving with it. At the same time, one cannot have a 2D fluid zone around the particle. The overdamped nature of the dynamics (assuming viscosity and pressure terms like a Newtonian fluid) would concentrate all the vorticity of the fluid within a length $`a`$ around the particle, and thus this scenario is also inconsistent: more than a length $`a`$ from the particle, the stress is too small to fracture the medium and produce the fluid. By elimination we turn next to a 1D plastic zone.

Theory: Compressed Column— We now propose a scenario based on competition between shear and compressive failure which accounts for all the numerical results, and illustrate it using the specific systems of Fig. 4. The driven particle creates a fracture in front of it. Naively the fracture force would be expected to be of order the particle interaction force $`aU^{\prime \prime }(a)`$, or roughly $`0.015`$ for the given $`q_D=20`$. In fact, it is equal to $`0.7`$, nearly two orders of magnitude greater, for two reasons: the force $`U^{}(r)`$ rises rapidly at short $`r`$, while the charge $`q_D>q`$ further increases the fracture force. After fracture, the particles in front of the driven particle must then move out of its way, either by failing in shear and moving along with the driven particle, or by failing in compression and moving transversely out of its way. Initially, consider just the first possibility so that in front of the driven particle there is a growing 1D column of particles failing in shear. One finds that the rate at which this length increases is determined not by the velocity of the driven particle, but by the (faster) velocity at which a compressive front ahead of that particle moves. 1D elasticity theory would imply that in time $`t`$, this compression reaches a distance $`la\sqrt{U^{\prime \prime }t/\eta }`$. Since this system is far from equilibrium, we have checked this result by simulating a 1D system with a single driven particle in a fixed, periodic background potential to mimic the medium. We find that this behavior remains valid, even close to the depinning transition, albeit with a greatly increased value for $`U^{\prime \prime }`$.

The 1D column does not grow indefinitely in length due to the possibility of transverse motion of the particles, in which case they squirt out of the column. The time scale for this process would naturally be of order $`\eta a/(F_dF_c)`$. Thus, the number of particles in the column is $`l/a\sqrt{U^{\prime \prime }a/(F_dF_c)}`$. By momentum balance, this number is equal to $`\eta \overline{V}/(F_dF_c)`$, giving

$$v(F_dF_c)^{3/2},$$
(3)
as observed, where some fixed force $`F_c`$ is required to create the fracture. The exit of particles from the column due to compressive failure is naturally highly intermittent, leading to intermittent motion of the driven particle, as seen in Fig. 3(a). This predicts the linear scaling of the rollover frequency with $`F_dF_c`$, with the prefactors such that the rollover frequency is increased above the naive expectation: at $`F_d=1.5`$, $`\omega =0.05`$, larger than $`\eta a/(F_dF_c)`$.

The 1D plastic zone is visible in the contours shown in Fig. 4. The aspect ratio of the contour increases for lower drives as the length of the contours increases at constant width, confirming that dissipation arises in a 1D plastic zone, rather than due to the elastic response of a 2D medium which would instead give a constant aspect ratio. Further, the size of the contours is not consistent with 2D elastic response, which would appear in Fig. 4(b) as an exponential decay of the dissipation on a length scale of approximately $`0.35`$ for $`\overline{V}=0.072`$, while the actual contours are significantly larger.

As the charge of the driven particle increases, it produces a depletion zone of missing particles around it to compensate its charge; the area of this zone is proportional to $`q_D/q`$. The length of the compression was determined above; the width will be proportional to the radius of the depletion zone, $`\sqrt{q_D/q}`$, accounting for the scaling of velocity with $`q_D`$, as seen in Fig. 3(b).

Summary— We have found a robust power-law for the velocity of a single driven particle fracturing a glassy environment, with $`\beta =1.5\pm 0.05`$. We give a theoretical explanation based on a 1D plastic zone, which decreases in size as the particle moves faster leading to $`\beta >1`$. This behavior arises due to the softness of the material, as for larger lattice constants $`a`$ or smaller $`q_D`$, the interaction becomes stiffer, and the width of the scaling region decreases until it eventually disappears leaving only linear scaling. While for conventional solids this scaling region is absent with no column observed in front of the particle, the origin of anomalous transport features in many disordered systems may be due to the mechanisms discussed herein.

Acknowledgments— We thank Eric Weeks for sharing his experimental results which inspired this work. We thank Tom Witten for many very useful discussions and for a critical reading of the manuscript. This work was performed at the Non-Equilibrium Summer Institute at Los Alamos. This work was supported by DOE Contract No. W-7405-ENG-36.