text:
# A New Class of Wilf-Equivalent Permutations

## 1. Introduction

A permutation $`\tau `$ of length $`k`$ is written as $`(a_1,a_2,\mathrm{},a_k)`$ where $`\tau (i)=a_i,\mathrm{\hspace{0.17em}1}ik`$. For $`k<10`$ we suppress the commas without causing confusion. As usual, $`S_n`$ denotes the symmetric group on $`[n]=\{1,2,\mathrm{},n\}`$.

###### Definition 1.

Let $`\tau `$ and $`\pi `$ be two permutations of lengths $`k`$ and $`n`$, respectively. We say that $`\pi `$ is $`\tau `$-avoiding if there is no subsequence $`i_{\tau (1)},i_{\tau (2)},\mathrm{},i_{\tau (k)}`$ of $`[n]`$ such that $`\pi (i_1)<\pi (i_2)<\mathrm{}<\pi (i_k)`$. If there is such a subsequence, we say that the subsequence $`\pi (i_{\tau (1)}),`$ $`\pi (i_{\tau (2)})`$,…, $`\pi (i_{\tau (k)})`$ is of type $`\tau `$.

For example, the permutation $`\omega =(52687431)`$ avoids $`(2413)`$ but does not avoid $`(3142)`$ because of its subsequence $`(5283)`$. An equivalent, but perhaps more insightful, definition is the following reformulation in terms of matrices.

###### Definition 2.

Let $`\tau S_n`$. The permutation matrix $`M(\tau )`$ is the $`n\times n`$ matrix having a $`1`$ in position $`(i,\tau (i))`$ for $`1in`$, and having $`0`$ elsewhere.111To keep the resemblance with the “shape” of $`\tau `$, we coordinatize $`M(\tau )`$ from the bottom left corner. Given two permutation matrices $`M`$ and $`N`$, we say that $`M`$ avoids $`N`$ if no submatrix of $`M`$ is identical to $`N`$.

Note that a permutation matrix $`M`$ of size $`n`$ is simply a transversal of an $`n\times n`$ matrix, i.e. an arrangement of 1’s for which there is exactly one 1 in every row and in every column of $`M`$. It is clear that a permutation $`\pi S_n`$ contains a subsequence $`\tau S_k`$ if and only if $`M(\pi )`$ contains $`M(\tau )`$ as a submatrix.

Let $`S_n(\tau )`$ denote the set of $`\tau `$-avoiding permutations in $`S_n`$.

###### Definition 3.

Two permutations $`\tau `$ and $`\sigma `$ are called Wilf-equivalent if they are equally restrictive: $`|S_n(\tau )|=|S_n(\sigma )|`$ for all $`nN`$. We denote this by $`\tau \sigma `$. If $`|S_k(\tau )|=|S_k(\sigma )|`$ for $`kn`$, then we say that $`\tau `$ and $`\sigma `$ are equinumerant up to level $`n`$.

The basic problem in the theory of forbidden subsequences is to classify all permutations up to Wilf-equivalence. Obviously, if two permutations are Wilf-equivalent, then they must be of the same length. Further, many Wilf-equivalences can be deduced by symmetry arguments within the same $`S_k`$. For instance, if $`M(\pi )`$ contains $`M(\tau )`$ as a submatrix, then the transpose matrix $`M(\pi )^t=M(\pi ^t)`$ contains $`M(\tau )^t=M(\tau ^t)`$. The same is true when simultaneously reflecting both matrices $`M(\pi )`$ and $`M(\tau )`$ in either a horizontal or a vertical axis of symmetry. The three operations defined above generate the dihedral group $`D_4`$ acting on the set of permutation matrices in the obvious way. The orbits of $`D_4`$ in $`S_k`$ are called symmetry classes. It is clear that if $`\tau `$ and $`\sigma `$ belong to the same symmetry class in $`S_k`$, then $`\tau \sigma `$. However, Wilf-classes are in general, but apparently rarely, larger than single symmetry classes. This makes the classification of permutations up to Wilf-equivalence a subtle and difficult process.

The first major result in the theory of forbidden subsequences states that $`(123)(132)`$, and hence $`S_3`$ is one Wilf-class, which combines the two symmetry classes of $`(123)`$ and $`(132)`$. As the behest of Wilf, bijections between $`S_n(123)`$ and $`S_n(132)`$ were given by Simion-Schmidt , Rotem , Richards , and West . They all prove $`|S_n(123)|=c_n`$, where $`c_n`$ is the $`n`$th Catalan number. Permutations with forbidden subsequences arise naturally in computer science in connection with sorting problems and strings with forbidden subwords. For example, in - Knuth shows that $`S_n(231)`$ is the set of stack-sortable permutations (see also ), so that $`|S_n(231)|`$ is the number of binary strings of length $`2n`$, in which 0 stands for a “move into a stack” and 1 symbolizes a “move out from the stack”.

Numerous problems involving forbidden subsequences have also appeared in algebraic combinatorics. In the late 1980s, it was discovered that the property of avoiding 2143 exactly characterizes the vexillary permutations, i.e. those whose Stanley symmetric function is a Schur function. (See  for a good exposition.) Lakshimibai and Sandhya  likewise show that $`S_n(3412,4231)`$ is the set of permutations indexing an interesting subclass of Schubert varieties. And Billey and Warrington  have very recently defined a class of permutations under 5 restrictions which are related to the Kazhdan-Lusztig polynomials. This all naturally leads to the study and classification of Wilf-classes of permutations of length 4 or more.

The classification of $`S_4`$ turns out to be much more complicated than that of $`S_3`$. It is completed in a series of papers by Stankova and West. They utilize the concept of a generating tree $`𝔗(\tau )`$ of $`\tau S_k`$: the nodes on the $`k`$th level of $`𝔗(\tau )`$ are the permutations in $`S_n(\tau )`$, and the descendants of $`\pi S_n(\tau )`$ are obtained from $`\pi `$ by inserting $`n+1`$ in appropriate places in $`\pi `$. Clearly, the tree isomorphism $`𝔗(\tau )𝔗(\sigma )`$ implies $`\tau \sigma `$, but the converse is far from true. In , West shows $`𝔗(1234)𝔗(1243)𝔗(2143)`$. In , Stankova constructs a specific isomorphism $`𝔗(4132)𝔗(3142)`$. In , she completes the classification of $`S_4`$ by proving $`(1234)(4123)`$; there she uses a different approach which yields the somewhat surprising result that, while $`𝔗(1234)\cong ̸𝔗(4123)`$, on every level of the two trees the number of nodes with a given number of descendants is the same for both trees. Thus, the seven symmetry classes of $`S_4`$ are grouped in three Wilf-classes, with representatives (4132), (1234) and (1324) (cf. Fig. 11.)

In , Babson-West show $`(n1,n,\tau )(n,n1,\tau )`$ for any $`\tau S_{n2}`$, and $`(n2,n1,n,\tau )(n,n1,n2,\tau )`$ for any $`\tau S_{n3}`$, thus completing the classification up to level 5. The key idea is the concept of a stronger Wilf-equivalence relation.

###### Definition 4.

A transversal $`T`$ of a Young diagram $`Y`$ is an arrangement of 1’s and 0’s such that every row and every column of $`Y`$ has exactly one 1 in it. A subset of 1’s in $`T`$ is said to form a submatrix of $`Y`$ if all columns and rows of $`Y`$ passing through these 1’s intersect inside $`Y`$. For a permutation $`\tau S_k`$, we say that $`T`$ contains pattern $`\tau `$ if some $`k`$ 1’s of $`T`$ form a submatrix of $`Y`$ identical to $`M(\tau )`$ (cf. Fig. 4.)

Given several 1’s in a transversal $`T`$, the condition for them to form a submatrix of $`T`$ is the same as the requirement that the column of the rightmost 1 and the row of the lowest 1 must intersect inside $`Y`$. This condition is necessary for the new definition to be a useful generalization of the classical definition of a forbidden subsequence, as we shall see below. In particular, when $`Y`$ is a square diagram, the two definitions coincide. Let us denote by $`S_Y(\tau )`$ the set of all transversals of $`Y`$ which avoid $`\tau `$.

###### Definition 5.

Two permutations $`\tau `$ and $`\sigma `$ are called shape-Wilf-equivalent (SWE) if $`|S_Y(\tau )|=|S_Y(\sigma )|`$ for all Young diagrams $`Y`$. We denote this by $`\tau \stackrel{s}{}\sigma `$.

Clearly, $`\tau \stackrel{s}{}\sigma `$ implies $`\tau \sigma `$, but not conversely. We will write $`Y(a_1,a_2,\mathrm{},a_n)`$ for the Young diagram $`Y`$ whose $`i`$-th row has $`a_i`$ cells, $`1in`$. In order for a Young diagram $`Y`$ to have any transversals at all, $`Y`$ must have the same number of rows and columns and $`Y`$ must contain the staircase diagram $`St=Y(n,n1,\mathrm{},2,1)`$, where $`n`$ is the number of cells in the top (largest) row of $`Y`$. Thus, from now on, when we talk about a Young diagram $`Y`$ of size $`n`$, we will assume that $`Y`$ has $`n`$ rows and $`n`$ columns and contains $`St`$ of size $`n`$.

SWE is a very strong relation on two permutations and it is certainly too restrictive on its own to be useful in the general classification of permutations. However, combined with the proposition below (see ), it allows for more Wilf-equivalences to be established.

###### Proposition 1.

Let $`A\stackrel{s}{}B`$ for some permutation matrices $`A`$ and $`B`$. Then for any permutation matrix $`C`$:

$$\left(\begin{array}{cc}A& 0\\ & \\ 0& C\end{array}\right)\stackrel{s}{}\left(\begin{array}{cc}B& 0\\ & \\ 0& C\end{array}\right)$$

Let $`I_k`$ be the $`k\times k`$ identity matrix, and let $`J_k`$ be its reflection across a vertical axis of symmetry. According to Backelin-West-Xin in , $`I_k\stackrel{s}{}J_k`$ for any $`k`$, and hence $`(n,n1,\mathrm{},m,\tau )(m,\mathrm{},n1,n,\tau )`$ for any $`\tau S_{nm}`$. This SWE generalizes the results in  and , but it is not sufficient to complete the classification of $`S_7`$, nor of $`S_6`$.

In 2001, Stankova-Frenkel noticed a missing case of a plausible Wilf-equivalence in $`S_6`$: (546213) and (465213) were equinumerant up to level $`11`$, but no reference was found regarding why these permutations were thought to be in different Wilf classes. Stankova-Frenkel further found an infinite class of Wilf-equivalences

(1)
$$(n1,n2,n,\tau )(n2,n,n1,\tau ),$$

At her request, West confirmed (1) by computer checks for $`n=6,7`$ up to level 13.222In all tables, we skip the column corresponding to $`|S_{n+1}(\tau )|`$ if $`\tau S_n`$. It is easy to see that all permutations in $`S_n`$ are equinumerant on level $`n+1`$ (for example, cf. ).

The purpose of this paper is to explain the proof of the new Wilf-equivalences in (1). The idea is to show $`(213)\stackrel{s}{}(132)`$ and apply then Proposition 1. Even though $`M(213)`$ and $`M(132)`$ are transposes of each other, their SWE relationship is far from trivial, as the present paper will reveal. It is surprising that, since the launch of the theory of forbidden subsequences in the early 1980s, and the introduction of SWE in the early 1990s, such a basic relationship is discovered only now.

###### Theorem 1 (Main result of the paper).

The permutations $`(213)`$ and $`(132)`$ are shape-Wilf-equivalent. Consequently, for any $`\tau S_{n3}`$, the permutations $`(n1,n2,n,\tau )`$ and $`(n2,n,n1,\tau )`$ are Wilf-equivalent.

Theorem 1 finally accounts for the last missing case in $`S_6`$ and the remaining cases in $`S_7`$, thus completing the classification of forbidden subsequences up to length $`n=7`$.

In summary, modulo symmetry classes, as of now there are essentially two known infinite families of Wilf-equivalences, resulting from  and the present paper:

(2)
$$\left(\begin{array}{cc}I_k& 0\\ & \\ 0& C\end{array}\right)\stackrel{s}{}\left(\begin{array}{cc}J_k& 0\\ & \\ 0& C\end{array}\right)\text{and}\left(\begin{array}{cc}M(213)& 0\\ & \\ 0& C\end{array}\right)\stackrel{s}{}\left(\begin{array}{cc}M(132)& 0\\ & \\ 0& C\end{array}\right)$$

Further, there is only one known “sporadic” case of Wilf-equivalence, from :

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

Of all symmetry classes in $`S_4`$, the classes of the above (4132) and (3142) in (3) are the most unexpected to fall into the same Wilf-class: (3142) has the smallest symmetry class as it corresponds geometrically to the quadrilateral with most symmetries - the square, while $`(4132)`$ has the largest symmetry class as it corresponds to the quadrilateral with least number of symmetries - a quadrilateral with 4 different angles. And yet, not only $`(4132)(3142)`$, but also their trees are isomorphic. In a similar vein, the permutations in (2) are more than just Wilf-equivalent - they are SWE. This is an interesting phenomenon - so far, every known Wilf-equivalence can be explained by a stronger relationship: either symmetry, tree isomorphism, SWE, or a combination of these.

For further discussion, we refer the reader to Sections 5-6.

## 2. The Row-Decomposition Formula

Let $`Y`$ be a Young diagram with $`n`$ rows and $`n`$ columns. We denote by $`(k,l)`$ the intersection cell of row $`k`$ and column $`l`$, counted from the top left corner of $`Y`$. A cell in the bottom row of $`Y`$ is called a bottom cell of $`Y`$. Let $`m`$ be the number of bottom cells in $`Y`$.

###### Definition 6.

For a subset $`X`$ of cells in $`Y`$, define the reduction $`Y/_X`$ of $`Y`$ along $`X`$ to be a new Young diagram obtained from $`Y`$ by deleting all rows and columns of $`Y`$ which intersect $`X`$.

For example, if the cross of a cell $`C`$ in $`Y`$ is the union of the row and column containing $`C`$, then the reduction $`Y/_C`$ is the diagram obtained from $`Y`$ by deleting the cross of $`C`$. The reduction of $`Y`$ along an arbitrary bottom cell of $`Y`$ is denoted by $`Y^r`$, and it clearly does not depend on the choice of the bottom cell. We will use this fact frequently when reducing along cell $`(1,n)`$ (and $`(n,1)`$) in the proof of the commitativity argument in Lemma 3 in Section 4.

###### Definition 7.

To any bottom cell $`C`$ in $`Y`$, we associate a cross-product $`Y_C`$ of Young diagrams in the following way. Mark by $`P`$ the top right corner of $`C`$ (this is a grid point on $`Y`$), and consider the reduction $`Y/_C`$, which still contains point $`P`$. Starting from $`P`$ in $`Y/_C`$, draw a $`45^{}`$ ray in north-east direction until the ray intersects for the first time the border of $`Y/_C`$, and use the resulting segment as the diagonal of a smaller subdiagram $`A_C`$ of $`Y/_C`$. Delete the rows and columns of $`A_C`$ in $`Y/_C`$, leaving a subdiagram $`B_C=Y/_{\{C,A_C\}}`$. Thus, any bottom cell $`C`$ in the original diagram $`Y`$ determines a pair $`(A_C,B_C)`$ of smaller Young diagrams, which we call the cross-product of $`A_C`$ and $`B_C`$ and denote by $`Y_C:=A_C\times B_C`$.

If one of the subdiagrams $`A_C`$ or $`B_C`$ is empty, we define $`Y_C`$ to equal the other subdiagram. This case occurs exactly when $`C`$ is the first or the last bottom cell of $`Y`$:

$$Y_{(n,1)}=Y^r\times \mathrm{}=Y^r=\mathrm{}\times Y^r=Y_{(n,m)}.$$

Example 1. Let $`Y=Y(10,10,9,8,8,8,8,7,4,3)`$. Let $`C=(10,2)`$. Then $`Y_C=A_C\times B_C=Y(6,6,6,6,5,2)\times Y(3,3,2)`$ (cf. Fig. 3.)

###### Definition 8.

Let $`Y`$ be a Young diagram of size $`n`$. The row decomposition of $`Y`$ is the formal sum $`(Y)`$ of cross-products of smaller Young diagrams:

$$(Y):=\underset{C}{}Y_C=\underset{C}{}A_C\times B_C,$$

where the sum is taken over all bottom cells $`C`$ of $`Y`$.

As noted above, the first and the last summands of $`(Y)`$ are identical to $`Y^r`$.

###### Definition 9.

A transversal of a diagram $`Y`$ which avoids (resp. contains) a $`(213)`$–pattern is called a good (resp. bad) transversal of $`Y`$. Denote by $`𝒯(Y)=𝒯(a_1,a_2,\mathrm{},a_n)`$ the number of good transversals of $`Y=Y(a_1,a_2,\mathrm{},a_n)`$.

We use the convention $`𝒯(\mathrm{})=1`$. For some $`1`$ already placed in a cell of $`Y`$, we say that it imposes a $`(213)`$-condition on $`Y`$ if it plays the role of a “1” in a $`(213)`$-pattern contained in some bad transversal of $`Y`$; the (213)-condition is the actual condition on the rest of $`Y`$ in order to avoid a (213)-pattern containing this 1.

###### Definition 10.

Two diagrams $`Y`$ and $`X`$ are said to be numerically equivalent if $`𝒯(Y)=𝒯(X)`$. We denote this by $`YX`$.

Clearly, $`𝒯(A_C\times B_C)=𝒯(A_C)𝒯(B_C)`$. Moreover, to obtain the number $`𝒯(Y)`$, we can apply the function $`𝒯`$ to all terms in the formal sum $`(Y)`$:

###### Theorem 2 (Row-Decomposition).

Let $`Y`$ be a Young diagram of size $`n`$. Then

(4)
$$𝒯(Y)=\underset{C}{}𝒯(A_C)𝒯(B_C)$$

where the sum is taken over all bottom cells $`C`$ in $`Y`$.

Proof: For a bottom cell $`C=(n,i)`$, let $`Y_i`$ denote the diagram $`Y`$ with the additional data of $`1`$ in cell $`C`$. We claim that the good transversals of $`Y_i`$ are in 1-1 correspondence with the good transversals of the pair of diagrams $`(A_C,B_C)`$, and hence

(5)
$$𝒯(Y_i)=𝒯(A_C)𝒯(B_C).$$

This, and the fact that any transversal of $`Y`$ must contain exactly one 1 in the bottom row, immediately establishes Theorem 2. Hence, it suffices to prove (5) for $`Y_i`$.

When $`i=1`$ or $`i=m`$, the claim (5) is trivial. Indeed, in these cases, the 1 in the bottom row of $`Y`$ is either in the first or last bottom cell, and hence it doesn’t impose any (213)-conditions on $`Y`$. The question reduces to finding all good transversals of $`Y/_C=Y^r=Y_C`$. Therefore, $`Y_1Y_mY^r`$.

Assume now that $`1<i<m`$. Fix a good transversal $`T`$ of $`Y_i`$. Denote by $`1_j`$ the 1 in column $`j`$. By $`1_j>1_k`$ we mean that $`1_j`$ is in a row above the row of $`1_k`$. Similarly, for two disjoint sets $`A`$ and $`B`$ of 1’s, by $`A>B`$ we mean that all 1’s in A are above all 1’s in B. Let $`B_L=\{1_1,1_2,\mathrm{},1_{i1}\}`$ denote the set of all 1’s in $`T`$ appearing in columns to the left of cell $`C`$. Similarly, let $`A=\{1_{i+1},1_{i+2},\mathrm{},1_k\}`$ be the set of all 1’s appearing in the columns of $`Y`$ intersecting $`A_C`$, and let $`B_R=\{1_{k+1},1_{k+2},\mathrm{},1_n\}`$ be the set of all 1’s appearing in the remaining columns, i.e. all columns to the right of $`A_C`$. Notice that no 1 in $`B_R`$ can appear in a row intersecting $`A_C`$: the rows of the 1’s in $`B_R`$ are above all rows of $`A_C`$ as enforced by the construction of $`A_C`$ via the $`45^{}`$ segment.

The key idea of the proof is contained in the following lemma:

###### Lemma 1.

In any good transversal $`T`$ of $`Y_i`$, we have $`B_L>A`$.

Proof (of Lemma 1): Given a row $`j`$ of $`A`$, let the level $`L_j`$ be the subset of $`A`$ consisting of all 1’s whose orthogonal projections onto row $`j`$ are inside $`A_C`$. Clearly, every $`1A`$ belongs to at least one level $`L_j`$, and $`L_{n1}L_{n2}\mathrm{}L_{nk}=A`$, where $`k`$ is the size of $`A_C`$. Recall that $`i<m`$, so that $`L_{n1}A\mathrm{}`$, and that the bottom row of $`Y`$ is filled by $`1_i`$. This imposes a (213)-condition on $`Y_i`$: $`B_L>L_{n1}`$. Finally, from the construction of $`A_C`$, $`|L_{nj}|>j`$ for $`j=1,2,..,k1`$, and $`|L_{nk}|=k`$.

We will prove simultaneously the following two statements for all $`1jk`$:

* $`B_L>L_{nj}`$;
* All rows $`n1`$, $`n2`$, …, $`nj`$ of $`Y_i`$ are filled in with 1’s on level $`L_{nj}`$.

For $`j=1`$, (i) was shown above. But then row $`n1`$ in $`Y_i`$ must be filled with an element of $`L_{n1}`$, so (ii) is also true. Assume (i) and (ii) for some $`j<k`$. Then (ii) for $`j`$, together with $`|L_{nj}|>j`$, implies that at least one element $`1_s`$ of $`L_{nj}`$ is in row $`nj1`$ or above. Now (i) for $`j`$ implies in particular $`B_L>1_s`$, so that a new (213)-condition is imposed: $`B_L>(L_{nj1}\backslash L_{nj})`$. Combining, $`B_L>L_{nj1}`$: this is (i). By definition of $`L_{nj1}`$, the only $`1_h`$ that can possibly fill in row $`nj1`$ in $`Y_i`$ must belong either to $`L_{nj1}`$, or to $`B_L`$. Because $`|L_{nj1}|j+1`$ and $`B_L>L_{nj1}`$, we conclude that $`1_hL_{nj1}`$. This shows (ii) for $`j+1`$ and completes the inductive proof of the above statement. Lemma 1 follows automatically from (i) for $`j=k`$.∎

End of Proof of Theorem 2: Combining Lemma 1 with a previous observation, we see that no 1’s from $`B_L`$ or from $`B_R`$ can fill the rows intersecting $`A_C`$. In other words, all rows of $`A_C`$ must be filled exactly with the 1’s from set $`A`$: the number of necessary 1’s to make a transversal of $`A_C`$ matches $`|A|=k`$ because, by construction, $`A_C`$ has as many rows as columns. This in turn forces all 1’s in $`B_L`$ and $`B_R`$ to make a good transversal of the subdiagram $`B_C`$. It remains to show that there are no further (213)-conditions imposed by a triple of 1’s coming from $`A_C`$ and $`B_C`$.

The only way for $`A_C`$ and $`B_C`$ to engage together in a (213)-pattern is to have the “2” in $`B_L`$, the “1” in $`A`$, and the “3” in $`B_R`$; or, to have the “2” and the “1” in $`A`$, and the “3” in $`B_R`$. Even though such configurations of three 1’s are possible, their “full” matrices will not be contained entirely in $`Y`$ because of the relative positioning of $`A_C`$ and $`B_R`$.

Putting everything together, the good transversals of $`Y_i`$ are in 1–1 correspondence with pairs of good transversals of $`A_C`$ and $`B_C`$, i.e. $`𝒯(Y_i)=𝒯(A_C)𝒯(B_C)`$ for all bottom cells $`C`$ of $`Y`$. This completes the proof of the Row-Decomposition formula. ∎

Example 2. To illustrate the above proof, consider $`Y(10,10,9,8,8,8,8,7,4,3)`$. Let $`Y_2`$ denote the diagram $`Y`$ with the additional data that the 1 in the bottom row is in cell $`C=(10,2)`$. We have to show that $`𝒯(Y_2)=𝒯(6,6,6,6,5,2)𝒯(3,3,2)`$ (cf. Fig. 3.)

The initial condition that $`1_2`$ is in the bottom row forces the (213)-condition $`1_1>1_3`$. Since $`1_3`$ is above row 10, the only 1’s which can fill row 9 are $`1_3`$ and $`1_4`$. If $`1_3`$ is in row 9, then $`1_1>1_4`$ in order to avoid (213); if $`1_4`$ in in row 9, then $`1_1>1_3>1_4`$. In any case, $`1_1>1_3,1_4`$. Without loss of generality, assume that $`1_3`$ is in row 9, so that $`1_4`$ is in row 8 or above. From $`1_1>1_4`$ and avoiding (213), we conclude that $`1_1>1_4,1_5,1_6,1_7`$. One of the latter four 1’s must fill in row $`8`$. Without loss of generality, assume that $`1_4`$ is in row 8; hence $`1_5,1_6,1_7`$ are in rows $`7`$ or above. But then, to avoid (213), we are forced to conclude that $`1_1>1_8`$, i.e. $`1_1`$ is above all of $`1_3,\mathrm{},1_8`$. We need six 1’s to fill in the six rows $`9,8,\mathrm{},4`$. It immediately follows that $`1_3,\mathrm{},1_8`$ must have filled all 6 rows and columns of subdiagram $`A_C`$, leaving all remaining 1’s (except for $`1_2`$) to form a good transversal of subdiagram $`B_C`$ (cf. Fig. 4.)

We note that $`B_C`$ consists of two disjoint parts: $`B_L(1,1,1)`$ and $`B_R(2,2,1)`$. The argument that $`B_C`$ and $`A_C`$ cannot engage together in a pattern (213) is identical to the corresponding part of the proof of Theorem 2. ∎

Given a diagram $`Y`$, let $`C_b`$ be its rightmost bottom cell, which we call the bottom corner of $`Y`$, and let $`C_{b1}`$ be the bottom cell to the left of $`C_b`$. (In our previous notation, $`C_b=(n,m)`$, $`C_{b1}=(n,m1)`$.) Deleting $`C_b`$ from $`Y`$ results in a new diagram, which we denote by $`Y_r^{}`$ and call the row-deletion of $`Y`$. Similarly, we define the right corner $`C_t`$ of $`Y`$ as the bottom cell in the rightmost column of $`Y`$, $`C_{t1}`$ as the cell directly above $`C_t`$, and the column-deletion $`Y_c^{}`$ by deleting $`C_t`$ from $`Y`$. Note that $`(Y_r^{})^t=(Y^t)_c^{}`$, where $`X^t`$ denotes as usual the transpose of diagram $`X`$ along its main (north-west to south-east) diagonal.

In the row-decomposition of $`Y`$, we distinguish one special summand: the last but one summand $`Y_{C_{b1}}=A_{C_{b1}}\times B_{C_{b1}}`$, which we denote by $`Y_r^{\prime \prime }`$.

###### Corollary 1.

For any diagram $`Y`$, $`YY_r^{}+Y_r^{\prime \prime }`$.

Proof: The row-decomposition of $`Y`$ includes one more summand than the row-decomposition of $`Y_r^{}`$, namely, $`Y_r^{\prime \prime }`$: $`(Y)=Y_r^{}+Y_r^{\prime \prime }`$. Theorem 2 completes the proof.∎

From now on, we shall refer to Corollary 1 as Row-Decomposition (RD).

Example 3. Fig. 5 illustrates Corollary 1 for $`𝒯(9,9,9,9,7,7,7,7,4)`$.

## 3. Column Decomposition

###### Definition 11.

The column decomposition $`𝒞(Y)`$ of $`Y`$ is defined by:

$$𝒞(Y)=\underset{C}{}((Y^t)_{C^t})^t$$

where $`C`$ runs over all cells in the rightmost column of $`Y`$, and $`C^t`$ is the image of the cell $`C`$ after transposing $`Y`$.

Note that the column decomposition $`𝒞(Y)`$ can be obtained directly from $`Y`$ without going through the transpose $`Y^t`$: for a cell $`C`$ in the rightmost column of $`Y`$, mark the south-west corner of $`C`$, draw the $`45^{}`$ ray in south-west direction until it intersects the border of $`Y`$, delete the cross of $`C`$ and define analogously the product $`Y_C=A_C\times B_C`$.

As with row decomposition, we denote by $`Y_c^{}`$ the diagram resulting from $`Y`$ by deleting the right corner cell $`C_t`$, and by $`Y_c^{\prime \prime }`$ the summand in $`𝒞(Y)`$ corresponding to the cell $`C_{t1}`$ right above $`C_t`$. By definition, it is clear that

$$𝒞(Y)=Y_c^{}+Y_c^{\prime \prime }.$$

It is not obvious, however, why the same formula should be true after applying the function $`𝒯`$ to all terms: why is $`YY_c^{}+Y_c^{\prime \prime }`$?

###### Lemma 2.

The following statements are equivalent:

* $`(213)\stackrel{S}{}(132)`$.
* $`YY^t`$ for all Young diagrams $`Y`$.
* $`YY_c^{}+Y_c^{\prime \prime }`$.

Proof: Let $`𝒯_\tau (Y)`$ be the number of transversals of $`Y`$ avoiding permutation $`\tau `$. In our previous notation, $`𝒯(Y)=𝒯_{(213)}(Y)`$. Since $`M(132)=M(213)^t`$, $`𝒯_{(132)}(Y)=𝒯_{(213)}(Y^t)`$. By definition of SWE, (i) and (ii) are equivalent.

We will show the equivalence of (ii) and (iii) by induction on the size $`n`$ of $`Y`$. When $`n3`$, (ii) and (iii) can be easily checked by hand. Note that from the definitions of column reduction, deletion and decomposition, $`(Y^t)_c^{}=(Y_r^{})^t`$ and $`(Y^t)_c^{\prime \prime }=(Y_r^{\prime \prime })^t`$. Assume now that (ii) and (iii) are equivalent for size $`n`$.

Assume first that (iii) is true for size $`n+1`$. Then we can use (ii) for sizes $`n`$:

$$Y^t\stackrel{\text{(iii)}}{}(Y^t)_c^{}+(Y^t)_c^{\prime \prime }\stackrel{\text{def}}{=}(Y_r^{})^t+(Y_r^{\prime \prime })^t\stackrel{\text{(ii)}}{}Y_r^{}+Y_r^{\prime \prime }\stackrel{\text{RD}}{}Y.$$

This shows $`YY^t`$ and completes the proof of $`\text{(iii)}\text{(ii)}`$ for size $`n+1`$.

Conversely, assume that (ii) is true for size $`n+1`$.

(6)
$$Y^t\stackrel{\text{(ii)}}{}Y\stackrel{\text{RD}}{}Y_r^{}+Y_r^{\prime \prime }\stackrel{\text{(ii)}}{}(Y_r^{})^t+(Y_r^{\prime \prime })^t\stackrel{\text{def}}{=}(Y^t)_c^{}+(Y^t)_c^{\prime \prime }.$$

Replacing $`Y`$ by $`Y^t`$ in (6), reads $`YY_c^{}+Y_c^{\prime \prime }`$. This shows $`\text{(ii)}\text{(iii)}`$ for size $`n+1`$, and completes the proof of $`\text{(ii)}\text{(iii)}`$ and of Lemma 2. ∎

From now on, we shall refer to statement (iii) as Column-Decomposition (CD).

## 4. Commutativity of Row and Column Decompositions

###### Lemma 3.

$`YY_c^{}+Y_c^{\prime \prime }`$ for all Young diagrams $`Y`$.

Proof: Assume that the statement is true for all diagrams of size smaller than the size of $`Y`$. The idea is to apply RD and the assumed CD one after the other in different orders: this results in representing both sides of the equality as sums of the same four terms. Let us start with $`Y`$. Recall that $`C_b`$ and $`C_t`$ are the bottom and right corners of $`Y`$, respectively. Apply first RD:

$$Y\stackrel{\text{RD}}{}Y_r^{}+Y_r^{\prime \prime }.$$

Next, apply the assumed CD to $`Y_r^{}`$, and to the factor of $`Y_r^{\prime \prime }`$ that still contains $`C_t`$, leaving the other factor of $`Y_r^{\prime \prime }`$ unchanged:

(7)
$$Y_r^{}\stackrel{\text{CD}}{}(Y_r^{})_c^{}+(Y_r^{})_c^{\prime \prime },Y_r^{\prime \prime }\stackrel{\text{CD}}{}(Y_r^{\prime \prime })_c^{}+(Y_r^{\prime \prime })_c^{\prime \prime }.$$

Now start with $`Y_c^{}+Y_c^{\prime \prime }`$, and apply RD to $`Y_c^{}`$, and to the factor of $`Y_c^{\prime \prime }`$ that still contains $`C_b`$, leaving the other factor of $`Y_c^{\prime \prime }`$ unchanged:

(8)
$$Y_c^{}+Y_c^{\prime \prime }\stackrel{\text{RD}}{}(Y_c^{})_r^{}+(Y_c^{})_r^{\prime \prime }+(Y_c^{\prime \prime })_r^{}+(Y_c^{\prime \prime })_r^{\prime \prime }.$$

In both equations (7) and (8), by abuse of notation, we wrote $`(Y_r^{\prime \prime })_c^{}`$, $`(Y_r^{\prime \prime })_c^{\prime \prime }`$, $`(Y_c^{\prime \prime })_r^{}`$ and $`(Y_c^{\prime \prime })_r^{\prime \prime }`$ for the cross-products of diagrams resulting from applying CD, resp. RD, to the factors containing $`C_t`$, resp. $`C_b`$. From the definition of row and column deletion, it is clear that the first terms in (7) and (8) are equal: $`(Y_r^{})_c^{}=YC_bC_t=(Y_c^{})_r^{}`$. We claim that the remaining three terms also pair up as:

(9)
$$(Y_r^{})_c^{\prime \prime }=(Y_c^{\prime \prime })_r^{},(Y_r^{\prime \prime })_c^{}=(Y_c^{})_r^{\prime \prime },(Y_r^{\prime \prime })_c^{\prime \prime }=(Y_c^{\prime \prime })_r^{\prime \prime },$$

except in Case IV below where

(10)
$$(Y_r^{})_c^{\prime \prime }(Y_c^{})_r^{\prime \prime },(Y_r^{\prime \prime })_c^{}(Y_c^{\prime \prime })_r^{},(Y_r^{\prime \prime })_c^{\prime \prime }(Y_c^{\prime \prime })_r^{\prime \prime }.$$

Before we embark on the proofs of (9-10), note how they fit in the general outline of the proof of CD:

$`Y`$ $`\stackrel{\text{RD}}{}`$ $`Y_r^{}+Y_r^{\prime \prime }\text{(known)}`$
$`\stackrel{\text{CD}}{}`$ $`(Y_r^{})_c^{}+(Y_r^{})_c^{\prime \prime }+(Y_r^{\prime \prime })_c^{}+(Y_r^{\prime \prime })_c^{\prime \prime }\text{(assumed)}`$
$``$ $`(Y_c^{})_r^{}+(Y_c^{})_r^{\prime \prime }+(Y_c^{\prime \prime })_r^{}+(Y_c^{\prime \prime })_r^{\prime \prime }\text{(by examining cases below)}`$
$``$ $`Y_c^{}+Y_c^{\prime \prime }\text{(converse RD, known)}.\mathit{}`$
One of the reasons that this works is that the CD-factor in $`Y_r^{}`$ can be anticipated from $``$, the CD-factor in the original $`Y`$.

The proof of (9-10) depends solely on how the row and column decomposition interact with each other in any given Young diagram $`Y`$, more precisely, on the relative position of the two $`45^{}`$ segments used in the decompositions. Let the RD-segment be the segment used in RD, and let the RD-factor be the subdiagram $`A_C`$ determined by the RD-segment, and similarly for CD. Set $`𝒜:=`$RD-factor, and $`:=`$CD-factor in $`Y`$. To see that equations (9-10) are true, divide all Young diagrams $`Y`$ into four cases: since the RD- and CD-segments are parallel to each other, there are only four possible relative positions for them. We will use $`\stackrel{\text{sym}}{}`$, $`\stackrel{\text{sym}}{=}`$ and $`\stackrel{\text{sym}}{}`$ as shortcuts for “by symmetry arguments”.

Case I. The RD- and CD-factors do not overlap ($`𝒜=\mathrm{}`$), i.e. the RD- and CD-segments hit $`Y`$’s border before they “come close” to each other. Then

$`(Y_r^{})_c^{\prime \prime }`$ $`=`$ $`(YC_b)_c^{\prime \prime }=(YC_b)/_{\{(1,n),\}}\times =`$
$`=`$ $`\left(Y/_{\{(1,n),\}}\right)_r^{}\times =(Y_c^{\prime \prime })_r^{};`$
$`\stackrel{\text{sym}}{}(Y_c^{})_r^{\prime \prime }`$ $`=`$ $`(YC_t)/_{\{(n,1),𝒜\}}\times 𝒜=(Y_r^{\prime \prime })_c^{};`$
$`(Y_r^{\prime \prime })_c^{\prime \prime }`$ $`=`$ $`(Y/_{\{(n,1),𝒜\}}\times 𝒜)_c^{\prime \prime }=\left(Y/_{\{(n,1),𝒜\}}\right)_c^{\prime \prime }\times 𝒜`$
$`=`$ $`Y/_{\{(n,1),(1,n),,𝒜\}}\times \times 𝒜\stackrel{\text{sym}}{=}(Y_c^{\prime \prime })_r^{\prime \prime }.\mathit{}`$
Case II. The RD-factor contains the CD-factor ($`𝒜`$), i.e. the RD-segment runs “on the inside” of the CD-segment. As in Case II, $`(Y_r^{})_c^{\prime \prime }=(Y_c^{\prime \prime })_r^{}`$. Note that $`C_t𝒜`$, and therefore $`Y/_𝒜`$ is a square. This justifies step ($``$) below, where $`𝒜^{tr}`$ denotes the top right cell of $`𝒜`$. Note that $`𝒜^{tr}`$ has the same function in $`𝒜`$ as the cell $`(1,n)`$ has in $`Y`$. The proof works even in the extreme case where $`𝒜^{tr}=(1,n)`$.

$`(Y_c^{})_r^{\prime \prime }`$ $`=`$ $`(YC_t)_r^{\prime \prime }=(𝒜C_t)\times Y/_{\{(n,1),𝒜\}}`$
$`=`$ $`𝒜_c^{}\times Y/_{\{(n,1),𝒜\}}=(𝒜\times Y/_{\{(n,1),𝒜\}})_c^{}=(Y_r^{\prime \prime })_c^{};`$
$`(Y_r^{\prime \prime })_c^{\prime \prime }`$ $`=`$ $`(𝒜\times Y/_{\{(n,1),𝒜\}})_c^{\prime \prime }=𝒜_c^{\prime \prime }\times Y/_{\{(n,1),𝒜\}}`$
$`=`$ $`𝒜/_{\{,𝒜^{tr}\}}\times \times Y/_{\{(n,1),𝒜\}};`$
$`\stackrel{()}{=}`$ $`\left(Y/_{\{(1,n),\}}\right)_r^{\prime \prime }\times =(Y/_{\{(1,n),\}}\times )_r^{\prime \prime }=(Y_c^{\prime \prime })_r^{\prime \prime }.\mathit{}`$
Case III. The CD-factor contains the RD-factor ($`𝒜`$), i.e. the CD-segment runs “on the inside” of the RD-segment. This case is symmetric to Case II. ∎

Case IV. The RD- and CD-segments overlap. This happens exactly when the RD- and CD-segments differ from each other only in their final cells: the RD-segment intersects the rightmost column of $`Y`$, while the CD-segment intersects the bottom row of $`Y`$. Let $`𝒟:=/_{C_{b1}}=𝒜/_{C_{t1}}`$. Since $`C_b`$ and $`𝒜C_t`$ contain exactly one bottom, resp. rightmost, cell, then $`C_b𝒟𝒜C_t`$ and $`_r^{\prime \prime }=𝒟=𝒜_c^{\prime \prime }`$. Clearly, $`𝒮:=Y/_𝒟`$ is a square. Moreover, $`𝒮_b=/_𝒟=C_{b1}`$, $`𝒮_t=𝒜/_𝒟=C_{t1}`$; the top right cell of $`𝒮`$ is the cell $`(1,n)`$ of $`Y`$, and the bottom left cell of $`𝒮`$ is the cell $`(n,1)`$ of $`Y`$. From this, we see that $`Y/_{\{𝒞,(1,n)\}}=Y/_{\{𝒟,(n,1)\}}\text{and}Y/_{\{,(1,n)\}}=Y/_{\{𝒜,(n,1)\}}.`$ Therefore,

$`(Y_r^{})_c^{\prime \prime }`$ $`=`$ $`(YC_b)_c^{\prime \prime }=/_{C_{b1}}\times Y/_{\{/_{C_{b1}},(1,n)\}}`$
$`=`$ $`𝒟\times Y/_{\{𝒟,(1,n)\}}=𝒟\times Y/_{\{𝒟,(n,1)\}}\stackrel{\text{sym}}{=}(Y_c^{})_r^{\prime \prime };`$
$`(Y_c^{\prime \prime })_r^{}`$ $`=`$ $`(Y/_{\{,(1,n)\}}\times )_r^{}=Y/_{\{,(1,n)\}}\times (C_b)`$
$``$ $`Y/_{\{,(1,n)\}}\times 𝒟=Y/_{\{𝒜,(n,1)\}}\times 𝒟\stackrel{\text{sym}}{}(Y_r^{\prime \prime })_c^{};`$
$`(Y_r^{\prime \prime })_c^{\prime \prime }`$ $`=`$ $`(𝒜\times Y/_{\{𝒜,(n,1)\}})_c^{\prime \prime }=𝒜_c^{\prime \prime }\times Y/_{\{𝒜,(n,1)\}}=`$
$`=`$ $`𝒟\times Y/_{\{𝒜,(n,1)\}}=𝒟\times Y/_{\{,(1,n)\}}\stackrel{\text{sym}}{=}(Y_c^{\prime \prime })_r^{\prime \prime }.`$
The three special subcases when $`C_{b1}=(n,1)`$ (and hence $`C_{t1}=(1,n)`$), when $`C_b=(n,1)`$ (and hence $`C_t=(1,n)`$) and when $`C_b=C_t`$ (i.e. $`Y`$ is a square), are easily checked to satisfy the desired equalities. ∎

The discussion of these four cases completes the proof of Lemma 3. ∎

We remark that, due to the degenerate nature of Case IV, two of the final cross-products turn out to be equal: $`(Y_c^{\prime \prime })_r^{}=(Y_c^{\prime \prime })_r^{\prime \prime }`$, and hence $`(Y_c^{\prime \prime })_r^{\prime \prime }`$ has only two factors, rather than the three it has in Cases I–III.

## 5. New Wilf Equivalences and Consequences

Lemmas 2 and 3 imply the main result of the paper: $`(213)\stackrel{S}{}(132)`$. Combined with Proposition 1, this establishes a new class of Wilf-equivalent permutations.

Theorem 1. The permutations $`(213)`$ and $`(132)`$ are shape-Wilf-equivalent. Consequently, for any $`\tau S_{n3}`$, the permutations $`(n1,n2,n,\tau )`$ and $`(n2,n,n1,\tau )`$ are Wilf-equivalent.

In particular, this completes the classification up to Wilf-equivalences of $`S_n`$, for $`n7`$. Fig. 9 lists the number of symmetry classes and Wilf-classes in each such $`S_n`$.

An amusing corollary about numerical equivalence of Young diagrams can be deduced from the above theorem and the row-decomposition formula. Recall that $`St`$ is the standard staircase diagram. The $`k`$-staircase $`St_k`$ is the Young diagram which consists of $`St`$ plus the full $`k1`$ diagonals below the diagonal of $`St`$. In particular, $`St`$ is $`St_1`$, and the square $`n\times n`$ is $`St_n`$. The critical staircase $`St_k`$ of $`Y`$ is the first staircase whose complement $`Y\backslash St_k`$ is a union of at least two connected components. Label such components by $`St_k^j`$, for $`j=1,2,\mathrm{}`$, starting at the bottom left corner of $`Y`$. Thus, for every $`Y`$ with critical staircase $`St_k`$, we have the critical decomposition $`Y=St_k_jSt_k^j`$.

###### Corollary 2.

Let $`Y=St_k_{j=1}^lSt_k^j`$ be the critical decomposition of $`Y`$. The operations of permuting and of transposing the components $`St_k^j`$ result in Young diagrams numerically equivalent to $`Y`$.

In other words, let $`\tau S_l`$ be any permutation, and let $`\stackrel{}{t}=(t_1,t_2,\mathrm{},t_l)\{1,t\}^l`$ correspond to a choice $`t_j=t`$ to transpose, resp. $`t_j=1`$ not to transpose, the component $`St_k^{\tau (j)}`$. Then the following (ordered) critical decompositions represent numerically equivalent Young diagrams (cf. Fig. 10):

$$St_k\underset{j=1}{\overset{l}{}}St_k^jSt_k\underset{j=1}{\overset{l}{}}\left(St_k^{\tau (j)}\right)^{t_j}.$$

Proof: We use induction on the size of $`Y`$. The initial cases are easily verified. Moreover, when there is only one “hanging” shape, the corollary simply states that transposing $`Y`$ will yield a numerically equivalent diagram $`Y^t`$: this is the content of Theorem 1.

Suppose now that there are at least two hanging shapes: $`St_k^1`$ is the bottom shape, and let’s name the remaining shapes the “upper” shapes. Choose a permutation $`\sigma `$ and a transposition vector $`\stackrel{}{t}`$ both of which leave the bottom shape $`St_k^1`$ fixed, and operate on the upper shapes of $`Y`$. Apply the row-decomposition formula to $`Y`$: when $`C`$ runs over all bottom cells of $`Y`$, we have

(11)
$$Y\underset{C}{}Y_C=\underset{C}{}A_C\times B_C.$$

From the definition of the critical decomposition of $`Y`$, all RD-factors $`A_C`$ are parts of the bottom shape $`St_k^1`$, except for the first and the last RD-factors: there $`A_C=Y_r`$ or $`A_C=\mathrm{}`$. In any case, none of the upper shapes $`St_k^2,St_k^3,\mathrm{}`$ are broken up in (11). Thus, by induction hypothesis, we can apply $`\sigma `$ and $`\stackrel{}{t}`$ to each $`Y_C`$: $`\left(Y_C^\sigma \right)^\stackrel{}{t}=A_C\times \left(B_C^\sigma \right)^\stackrel{}{t}`$. We can then put back together the resulting diagrams via another application of the row-decomposition formula:

$$Y\underset{C}{}Y_C=\underset{C}{}A_C\times B_C\stackrel{\text{ind.}}{}\underset{C}{}A_C\times \left(B_C^\sigma \right)^\stackrel{}{t}\left(Y^\sigma \right)^\stackrel{}{t}.$$

This shows that leaving the bottom shape fixed, we can permute and transpose the upper shapes in any way we like. We also know, again from Theorem 1, that transposing the whole diagram $`Y`$ yields a numerically equivalent diagram $`Y^t`$. It is an easy exercise in algebra to verify that these two types of operations generate the whole group of operations required in Corollary 2. ∎

The conclusion of Corollary 2 holds under a slightly relaxed hypothesis regarding which staircases can be used instead of the critical staircase: as long as the RD (or CD) formula breaks up only the bottom (or only the top) hanging shape, the above proof goes through without modifications. Further generalizations are also possible, for instance, applying recursively the Corollary just within a hanging shape. Finally, this can all be used to write down a generating function for the numbers $`T_{(213)}(Y)`$, but we will not do this here since it will take us too far afield.

## 6. Further Discussion

A careful investigation of the new Wilf-pair $`(546213)(465213)`$ in $`S_6`$, leads to the observation that both permutation matrices can be decomposed into two blocks of $`3\times 3`$ matrices, and further, that moving from one decomposition to the other involves a transposition of one of the blocks. Thus, one might be lead to conjecture that for any permutation matrices $`A`$ and $`B`$, the following permutation matrices are Wilf-equivalent:

(12)
$$\left(\begin{array}{cc}A& 0\\ & \\ 0& B\end{array}\right)\left(\begin{array}{cc}A^t& 0\\ & \\ 0& B\end{array}\right)$$

In order for (12) to give any new Wilf-classes, other than those obtained by symmetry or $`I_t\stackrel{s}{}J_t`$, both $`A`$ and $`B`$ must be non-symmetric matrices. In $`S_6`$, there is only one such pair up to symmetry (denote the 1’s by dots, and omit all 0’s):

$$M\left(546213\right)=\left(\begin{array}{cccccc}& & & & & \\ & & & & & \\ & & & & & \\ & & & & & \\ & & & & & \\ & & & & & \\ & & & & & \end{array}\right)\left(\begin{array}{cccccc}& & & & & \\ & & & & & \\ & & & & & \\ & & & & & \\ & & & & & \\ & & & & & \\ & & & & & \end{array}\right)=M\left(465213\right)$$

In $`S_7`$, there are essentially 7 new Wilf-pairs which are covered by (12). Not surprisingly, these are the same pairs appearing in Fig. 2. One possible approach to prove (12) would be to show $`A\stackrel{s}{}A^t`$ for any permutation matrix $`A`$. Unfortunately, this is not true; it fails already in $`S_4`$, e.g. $`(3142)\overline{)\stackrel{s}{}}(2413)`$ since

$$|S_{(6,6,6,6,5,5)}(3142)|=394<395=|S_{(6,6,6,6,5,5)}(2413)|.$$

The Wilf-equivalence in (12) also fails in $`S_8`$. For example:

$$M\left(68572413\right)=\left(\begin{array}{cccccccc}& & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \end{array}\right)\sim ̸\left(\begin{array}{cccccccc}& & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \end{array}\right)=M\left(75862413\right)$$

The two permutations are equinumerant up to level 11, but they split on level 12:

$$|S_{12}(75862413)|=476576750<476576751=|S_{12}(68572413)|.$$

This forces a reexamination of the 8 new Wilf-pairs in $`S_6`$ and $`S_7`$. If we choose the “right” representatives of the symmetry classes, we can see that each permutation matrix contains a block corresponding to $`(213)`$ or $`(132)`$. This led to conjecturing and proving the shape-Wilf-equivalence $`(213)\stackrel{s}{}(132)`$. As we can see, this SWE is far from coincidental, and it is the reason for the infinitely many new Wilf-equivalences of Theorem 1.

Let us now shift the emphasis of our discussion to a slightly different question. If we write down a table enumerating $`|S_n(\tau )|`$ for a fixed $`\tau S_4`$ as $`n`$ increases, we notice a very plausible conjecture (cf. ):

###### Conjecture 1.

If $`|S_k(\tau )|<|S_k(\sigma )|`$ for some $`k`$, then $`|S_n(\tau )|<|S_n(\sigma )|`$ for all $`nk`$. In other words, modulo Wilf-equivalence, we can order all permutations in $`S_n`$ according to their relative restrictiveness: $`\tau <\sigma `$ if $`|S_k(\tau )|<|S_k(\sigma )|`$ for some $`k`$.

$`S_4`$ is the first non-trivial case of Conjecture 1. It was partially proved by Bona in , where he shows $`|S_n(1423)|<|S_n(1324)|`$ for $`n6`$ and $`|S_n(1234)|<|S_n(1324)|`$ for $`n7`$, in relation to a conjecture of Wilf and Stanley. To the best of our knowledge, no one had published a counterexample to Conjecture 1, until we found a counterexample in $`S_5`$, followed by various types of counterexamples in $`S_6`$ and $`S_7`$.

As Fig. 12 suggests, $`(53241)`$ and $`(43251)`$ cannot be ordered since $`S_k(53241)<S_k(43251)`$ for $`k12`$, but $`S_{13}(53241)>S_{13}(43251)`$. Fig. 13-14 list all counterexamples up to level $`13`$ in $`S_6`$, and some counterexamples in $`S_7`$. The asterisks indicate the first level at which the corresponding permutations “switch” their relative restrictiveness, and hence cannot be ordered as in Conjecture 1. The “!!” in Fig. 13 refers to the permutation (546213), which is also part of the new Wilf-equivalence of Theorem 1.

However, the above counterexamples do not preclude an asymptotic ordering of all permutations in $`S_n`$.

###### Definition 12.

For $`\tau ,\sigma S_n`$, we say that $`\tau `$ is asymptotically smaller than $`\sigma `$ if $`|S_k(\tau )|<|S_k(\sigma )|`$ for all $`k0`$.

###### Conjecture 2.

We can order asymptotically all permutations in $`S_n`$, modulo Wilf-equivalence.

Regev  and Bona  have worked on asymptotic behavior of certain types of permutations, but as of now, Conjecture 2 and some possible modifications of it are far from proven.

## Acknowledgments

Zvezdelina Stankova-Frenkel is grateful to Bernd Sturmfels (UC Berkeley) for his helpful suggestions both on mathematical and computational issues related to the project; to David Moews (University of Connecticut) for writing two of the computer programs used in this project; and to Paulo de Souza (UC Berkeley) and Tom Davis (Palo Alto) for their generous help in installing, testing and running the necessary computer software. Both authors would like to thank Olivier Guibert (Université Bordeaux 1, Talence Cedex, France) for providing his computer program on enumeration of forbidden subsequences.


format: text

text:
# The Meaning of the Interaction-Free Measurements

## I INTRODUCTION

The interaction-free measurements proposed by Elitzur and Vaidman  (EV IFM) led to numerous investigations and several experiments have been performed . One of the possible applications of the interaction-free measurements for quantum communication is that it opens up the way to novel quantum non-demolition techniques . Other applications are using the idea of interaction-free measurements for “interaction-free” computation  and for improving cryptographic schemes . However, there have been several objections to the name “interaction-free”. Some authors in trying to avoid it, made modifications such as “interaction (energy exchange) free measurements” , “indirect measurements” , “seemingly interaction-free measurements” , “interaction-free” interrogation , “exposure-free imaging” , “interaction-free interaction” , “absorption-free measurements” , etc. Moreover, Simon and Platzman  claimed that there is a “fundamental limit on ‘interaction-free’ measurements”. In many works on the implementation and the analysis of the EV IFM there is a considerable confusion about the meaning of the term “interaction-free”. For example, a very recent paper  stated that “energy exchange free” is now well established as a more precise way to characterize IFM in the case of classical objects. On the other hand, Ryff and Ribeiro  used the name “interaction-free” for a very different experiment. In this paper I want to clarify in which sense the interaction-free measurements are interaction free. I will also make a comparison with procedures termed “interaction-free measurements” in the past and will analyze conceptual advantages and disadvantages of various modern schemes for the IFM.

The plan of this paper is as follows: in Section II I will describe the original proposal of Elitzur and Vaidman. Section III is devoted to a particular aspect of the IFM according to which the measurement is performed without any particle being at the vicinity of the measured object. The discussion relies on the analogy with the “delayed choice experiment” proposed by Wheeler . In Section IV I make a comparative analysis of the “interaction-free measurements” by Renninger and Dicke. In Section V I analyze interaction-free measurements of quantum objects. Section VI devoted to the controversy related to the momentum and energy transfer in the process of the IFM. In Section VII I discuss modifications of the original EV proposal, in particular, the application of the quantum Zeno effect for obtaining a more efficient IFM. I end the paper with a few concluding remarks in Section VIII.

## II THE ELITZUR-VAIDMAN INTERACTION-FREE MEASUREMENTS

In the EV IFM paper the following question has been considered:

> Suppose there is an object such that any interaction with it leads to an explosion. Can we locate the object without exploding it?

The EV method is based on the Mach-Zehnder interferometer. A photon (from a source of single photons) reaches the first beam splitter which has a transmission coefficient $`\frac{1}{2}`$. The transmitted and reflected parts of the photon wave are then reflected by the mirrors and finally reunite at another, similar beam splitter, see Fig. 1a. Two detectors are positioned to detect the photon after it passes through the second beam splitter. The positions of the beam splitters and the mirrors are arranged in such a way that (because of destructive interference) the photon is never detected by one of the detectors, say $`D_2`$, and is always detected by $`D_1`$.

This interferometer is placed in such a way that one of the routes of the photon passes through the place where the object (an ultra-sensitive bomb) might be present (Fig. 1b). A single photon passes through the system. There are three possible outcomes of this measurement: i) explosion, ii) detector $`D_1`$ clicks, iii) detector $`D_2`$ clicks. If detector $`D_2`$ clicks (the probability for that is $`\frac{1}{4}`$), the goal is achieved: we know that the object is inside the interferometer and it did not explode.

The EV method solves the problem which was stated above. It allows finding with certainty an infinitely sensitive bomb without exploding it. The bomb might explode in the process, but there is at least a probability of 25% to find the bomb without the explosion. “Certainty” means that when the process is successful ($`D_2`$ clicks), we know for sure that there is something inside the interferometer.

The formal scheme of the EV method is as follows. The first stage of the process (the first beam splitter) splits the wave packet of the test particle into superposition of two wave-packets. Let us signify $`|\mathrm{\Phi }_{\mathrm{int}}`$ is the wave packet which goes through the interaction region and $`|\mathrm{\Phi }_{\mathrm{free}}`$ is the wave packet which does not enter the interaction region. In the basic EV procedure the first stage is

$$|\mathrm{\Phi }\frac{1}{\sqrt{2}}(|\mathrm{\Phi }_{\mathrm{int}}+|\mathrm{\Phi }_{\mathrm{free}}).$$
(1)
The next stage is the interaction between the object (the bomb) and the test particle. If the test particle enters the interaction region when the bomb is present, it causes an explosion:

$$|\mathrm{\Phi }_{\mathrm{int}}|\mathrm{bomb}\mathrm{in}|\mathrm{explosion}.$$
(2)
If the test particle does not enter the interaction region or if the bomb is not present, then nothing happens at this stage:

FIG. 1. (a) When the interferometer is properly tuned, all photons are detected by $`D_1`$ and none reach $`D_2`$. (b) If the bomb is present, detector $`D_2`$ has the probability 25% to detect the photon sent through the interferometer, and in this case we know that the bomb is inside the interferometer without exploding it.

$`|\mathrm{\Phi }_{\mathrm{free}}|\mathrm{bomb}\mathrm{in}`$ $``$ $`|\mathrm{\Phi }_{\mathrm{free}}|\mathrm{bomb}\mathrm{in},`$ (3)
$`|\mathrm{\Phi }_{\mathrm{int}}|\mathrm{bomb}\mathrm{out}`$ $``$ $`|\mathrm{\Phi }_{\mathrm{int}}|\mathrm{bomb}\mathrm{out},`$ (4)
$`|\mathrm{\Phi }_{\mathrm{free}}|\mathrm{bomb}\mathrm{out}`$ $``$ $`|\mathrm{\Phi }_{\mathrm{free}}|\mathrm{bomb}\mathrm{out}.`$ (5)
The next stage is the observation of the interference between the two wave packets of the test particle; it takes place at the second beam-splitter and detectors. It is achieved by splitting the noninteracting wave packet

$$|\mathrm{\Phi }_{\mathrm{free}}\frac{1}{\sqrt{2}}(|\mathrm{\Phi }_1+|\mathrm{\Phi }_2),$$
(6)
and splitting the wave packet which passed through the interaction region (if it did)

$$|\mathrm{\Phi }_{\mathrm{int}}\frac{1}{\sqrt{2}}(|\mathrm{\Phi }_1|\mathrm{\Phi }_2).$$
(7)
The observation of the test particle is described by

$`|\mathrm{\Phi }_1|D_1\mathrm{ready}|D_2\mathrm{ready}|\mathrm{\Phi }_1|D_1\mathrm{clicks}|D_2\mathrm{ready},`$ (8)
$`|\mathrm{\Phi }_2|D_1\mathrm{ready}|D_2\mathrm{ready}|\mathrm{\Phi }_2|D_1\mathrm{ready}|D_2\mathrm{clicks}.`$ (9)
The state $`|D_2\mathrm{clicks}`$ corresponds to the success of the experiment, when we know that the bomb is present in the interaction region; we signify it by the state $`|\mathrm{know}\mathrm{bomb}\mathrm{in}`$.

If the bomb is not present then the the EV measurement is described by

$`|\mathrm{\Phi }|\mathrm{bomb}\mathrm{out}|D_1\mathrm{ready}|D_2\mathrm{ready}`$ $``$ (10)
$`|\mathrm{\Phi }_1|\mathrm{bomb}\mathrm{out}|D_1\mathrm{clicks}|D_2\mathrm{ready}.`$ (11)
If the bomb is inside the interferometer, then the the EV measurement is described by

$`|\mathrm{\Phi }|\mathrm{bomb}\mathrm{in}|D_1\mathrm{ready}|D_2\mathrm{ready}`$ (12)
$`{\displaystyle \frac{1}{\sqrt{2}}}|\mathrm{explosion}+{\displaystyle \frac{1}{2}}|\mathrm{know}\mathrm{bomb}\mathrm{in}`$ (13)
$`+{\displaystyle \frac{1}{2}}|\mathrm{\Phi }_1|\mathrm{bomb}\mathrm{in}|D_1\mathrm{clicks}|D_2\mathrm{ready}.`$ (14)
The experiment ends up in finding the bomb with the probability of $`25\%`$, explosion with the probability of $`50\%`$, and no information but no explosion with the probability of $`25\%`$. In the latter case we can repeat the procedure and in this way (by repeating again and again) we can find one third of bombs without exploding them. It was found  that changing the reflectivity of the beam splitters can improve the method such that the fraction of the bombs remaining intact almost reaches one half.

## III Measurement without “touching”

The name “interaction-free” seems very appropriate for a procedure which allows finding objects without exploding them, in spite of the fact that these objects explode due to any interaction. Simple logic tells us: given that any interaction leads to an explosion and given that there has been no explosion, it follows that there has been no interaction. This argument which sounds unambiguous in the framework of classical physics requires careful definition of the meaning of “any interaction” in the domain of quantum mechanics.

The weakness of the definition: “The IFM is a procedure which allows finding an object exploding due to any interaction without exploding it,” is that quantum mechanics precludes existence of such objects. Indeed, a good model for an “explosion” is an inelastic scattering . The Optical Theorem  tells us that there cannot be an inelastic scattering without some elastic scattering. The latter does not change the internal state of the object, i.e., the object does not explode. In order to avoid non-existing concepts in the definition of the IFM, we should modify the definition in the following way:

> The IFM is a procedure which allows finding (at least sometimes) bombs of any sensitivity without exploding them.

The method presented in the EV IFM paper have certain additional features which further justify the name “interaction-free”. The method is applicable for finding the location of objects which do not necessarily explode. Even for such an object we can claim that, in some sense, finding its location is “interaction-free”. The discussion about the justification of the term “interaction-free” for the EV procedure has started in the original EV IFM paper :

> The argument which claims that this is an interaction-free measurement sounds very persuasive but is, in fact, an artifact of a certain interpretation of quantum mechanics (the interpretation that is usually adopted in discussions of Wheeler’s delayed-choice experiment). The paradox of obtaining information without interaction appears due to the assumption that only one “branch” of a quantum state exists. (p. 991)

One of the “choices” of Wheeler’s delayed-choice experiment is an experiment with a Mach-Zehnder interferometer in which the second beam splitter is missing (see Fig. 2). In the run of the experiment with a single photon detected by $`D_2`$, it is usually accepted that the photon had a well defined trajectory: the upper arm of the interferometer. In contrast, according to the von Neumann approach, the photon was in a superposition inside the interferometer until the time when one part of the superposition reached the detector $`D_2`$ (or until the time the other part reached the detector $`D_1`$ if that event was earlier). At that moment the wave function of the photon collapses to the vicinity of $`D_2`$. The justification of Wheeler’s claim that the photon detected by $`D_2`$ never was in the lower arm of the interferometer is that, according to the quantum mechanical laws, we cannot see any physical trace from the photon in the lower arm of the interferometer. This is true if (as it happened to be in this experiment) the photon from the lower arm of the interferometer cannot reach the detector $`D_2`$.

The fact that there cannot be a physical trace of the photon in the lower arm of the interferometer can be explained in the framework of the two-state vector formulation of quantum mechanics . This formalism is particularly suitable for this case because we have pre- and post-selected situation: the photon was post-selected at $`D_2`$. While the wave function of the photon evolving forward in time does not vanish in the lower arm of the interferometer, the backward-evolving wave function does. Vanishing one of the waves (forward or backward) at a particular location is enough to ensure that the photon cannot cause any change in the local variables of the lower arm of the interferometer.

FIG. 2. (a) The “trajectory” of the photon in the Wheeler experiment given that $`D_2`$ detected the photon, as it is usually described. The photon cannot leave any physical trace outside its “trajectory”. (b) The “trajectory” of the quantum wave of the photon in the Wheeler experiment according to the von Neumann approach. The photon remains in a superposition until the collapse which takes place when one of the wave packets reaches a detector.

In our experiment (Fig. 1.) we have the same situation. If there is an object in the lower arm of the interferometer, the photon cannot go through this arm to the detector $`D_1`$. This is correct if the object is such that it explodes whenever the photon reaches its location, but moreover, this is also correct in the case in which the object is completely nontransparent and it blocks the photon in the lower arm eliminating any possibility of reaching $`D_1`$. Even in this case we can claim that we locate the object “without touching”. This claim is identical to the argument according to which the photon in Wheeler’s experiment went solely through the upper arm. In the framework of the two-state vector approach we can say that the forward-evolving quantum state is nonzero in the lower arm of the interferometer only up to the location of the object, while the backward-evolving wave function is nonzero only from the location of the object. Thus, at every point of the lower arm of the interferometer one of the quantum states vanishes. The two-state vector formalism does not suggest that the photon is not present at the lower arm of the interferometer; it only helps to establish that the photon does not leave a trace there. The latter is the basis for the claim that, in some sense, the photon was not there.

## IV  The IFM of Renninger and Dicke

In many papers describing experiments and modifications of the EV IFM the first cited papers are one by Renninger  and another by Dicke . It is frequently claimed that Elitzur and Vaidman “extended ideas of Renninger and Dicke” or just “amplified the argument by inventing an efficient interferometric set” . In fact, there is little in common between Renninger-Dicke IFM and the EV IFM. Dicke’s paper is cited in the EV IFM paper, but the citation is given only for the justification of the name: “interaction-free measurements”. Renninger’s and Dicke’s papers do not have the method, and, more importantly, they do not address the question which the EV IFM paper have solved.

FIG. 3. Renninger’s experiment. The photon spherical wave is modified by the scintillation detector $`D_1`$ in spite of the fact that it detects nothing.

FIG. 4. Dicke’s Experiment. The ground state of a particle in the potential well (solid line) is changed to a more energetic state (dashed line) due to short radiation pulse, while the quantum state of the photons in the pulse remains unchanged.

Renninger discussed a negative result experiment: a situation in which the detector does not detect anything. In spite of the fact that nothing happened to the detector, there is a change in the measured system. He considered a spherical wave of a photon after it extended beyond the radius at which a scintillation detector was located in part of the solid angle, see Fig. 3. The state of the detector remained unchanged but, nevertheless, the wave-function of the photon is modified. The name “interaction-free” for Renninger’s setup might be justified because there is not any, not even an infinitesimally small, change in the state of the detector in the described process. This is contrary to the classical physics in which interaction in a measurement process can be made arbitrary small, but it cannot be exactly zero.

Dicke considered the paradox of the apparent non-conservation of energy in a Renninger-type experiment. He considered an atom in a ground state inside a potential well. Part of the well was illuminated by a beam of photons. A negative result experiment was considered in which no scattered photons were observed, see Fig. 4. The atom changed its state from the ground state to some superposition of energy eigenstates (with a larger expectation value of energy) in which the atom does not occupy the part of the well illuminated by the photons. The photons, however, apparently have not changed their state at all. Then, Dicke asked: “What is the source of the additional energy of the atom?!”

Careful analysis  (in part, made by Dicke himself) shows that there is no real paradox with the conservation of energy, although there are many interesting aspects in the process of an ideal measurement . One of the key arguments is that the photon pulse has to be well localized in time and, therefore, it must have a large uncertainty in energy.

The word “measurement” in quantum theory have many very different meanings . The purpose of the Renninger and Dicke measurements is preparation of a quantum state. In contrast, the purpose of the EV interaction-free measurement is to obtain information about the object. In Renninger and Dicke measurements the measuring device is undisturbed (these are negative result experiments) while in the EV measurement the observed object is, in some sense, undisturbed. In fact, in general EV IFM the quantum state of the observed object is disturbed: the wave function becomes localized at the vicinity of the lower arm of the interferometer (see Sec. 3 of the EV paper). The reasons for using the term “interaction-free measurements” are that the object does not explode (if it is a bomb), it does not absorb any photon (if it is an opaque object) and that we can claim that, in some sense, the photon does not reach the vicinity of the object.

A variation of Dicke’s measurement which can serve as a measurement of the location of an object was considered in the EV IFM paper for justifying the name “interaction-free measurements” of the EV procedure. An object in a superposition of being in two far away places was considered. A beam of light passed through one of the locations and no scattered photons were observed. This yields the information that the object is located in the other place. The described experiment is interaction-free because the object (if it is a bomb) would not explode: the object is found in the place where there were no photons.

In such an experiment, however, it is more difficult to claim that the photon was not at the vicinity of the object: the photon was not at the vicinity of the future location of the object. But the main weakness of this experiment relative to the EV scheme is that we get information about the location of the object only if we have prior information about the state of the object. If it is known in advance that the object can be found in one of two boxes and it was not found in one, then obviously, we know that it is in the second box. The whole strength of the EV method is that we get information that an object is inside the box without any prior information! The latter, contrary to the former task cannot be done without help of a quantum theory.

In order to see the difference more vividly let us consider an application of the EV method to Dicke’s experimental setup. Instead of the light pulse we send a “half photon”: We arrange the EV device such that one arm of the Mach-Zehnder interferometer passes through the location of the particle, see Fig. 5. Then, if detector $`D_2`$ clicks, the particle is localized in the interaction region.

In both cases (the Renninger-Dicke IFM and this EV IFM) there is a change in the quantum state of the particle without, in some sense, interaction with the photon. However, the situations are quite different. In the original Dicke’s experiment we can claim that the dashed line of Fig. 4. is the state of the particle after the experiment only if we have prior information about the state of the particle before the experiment (solid line of Fig. 4.) In contrast, in the EV modification of the experiment, we can claim that a particle is localized in the vicinity of the interaction region (dashed line of Fig. 5.) even if we had no prior information about the state of the particle.

It seems that Dicke named his experiment “interaction-free” mainly because the photons did not scatter: this is a “negative result experiment”. In the EV experiment the photon clearly changes its state and it is essential that it was detected: this is not a “negative result experiment” in this sense.

Paul  noted that there is an earlier paper by Renninger  in which an experimental setup almost identical to that of the EV IFM was considered: a Mach-Zehnder interferometer tuned to have a dark output towards one of the detectors. However, Renninger never regarded his experiment as a measurement on an object which was inside the interferometer: Renninger’s argument, as in the experiment described in Fig. 3, was about “interaction-free” changing the state of the photon. Renninger has not asked the key question of the EV IFM: How to get information in an interaction-free manner?

I can see something in common between the Renninger-Dicke IFM and the EV IFM in the framework of the many-worlds interpretation. In both cases there is an “interaction”: radiation of the scintillator in the Renninger experiment or explosion of the bomb in the EV experiment, but these interactions take place in the “other” branch, not in the branch we end up discussing the experiment. In an attempt to avoid adopting the many-worlds interpretation such interactions were considered as counterfactual .

FIG. 5. The EV modification of Dicke’s Experiment. The ground state of a particle in the potential well (solid line) is changed to a well localized state (dashed line) when the photon is detected by the detector $`D_2`$.

## V  Interaction-free localization of a quantum object

We name the experiment described in Fig. 5. “interaction-free” measurement (cf. “interaction-free collapse” of the EV IFM paper) in spite of the fact that both the particle and the photon change their states. The main motivation for the name is that the interaction between the particle and the photon is such that there is an “explosion” if they “touch” each other, but the experiment (when $`D_2`$ clicks) ends up without explosion.

The second aspect of the EV IFM, when applied to quantum objects, encounters a subtle difficulty. After performing the procedure of the IFM and obtaining the photon click at $`D_2`$, we cannot claim that the photon was not present at the region of interaction; moreover, it might be the case that, in some sense, the photon was there with certainty.

First, let us repeat the argument which led us to think that the photon was not there. Consider again the experiment described on Fig. 1., but now the “bomb” is replaced by a quantum object in a superposition of being in the “interaction region” and somewhere else outside the interferometer. If $`D_2`$ clicks, we can argue that the object had to be on the way of the photon in the lower arm of the interferometer, otherwise, it seems that we cannot explain the arrival of the photon to the “dark” detector $`D_2`$. If the object was on the way of the photon, we can argue that the photon was not there, otherwise we had to see the explosion. Therefore, the photon went through the upper arm of the interferometer and it was not present in the interaction region.

The persuasive argument of the previous paragraph is incorrect! Not just the semantic point discussed above, i.e., that according to the standard approach the quantum wave of the photon in the lower arm of the interferometer was not zero until it reached the interaction region. It is wrong to say that the photon was not in the lower arm even in the part beyond the interaction region. In the experiment in which $`D_2`$ clicks, the photon can be found in any point of the lower arm of the interferometer!

This claim can be seen most clearly by considering “nested interaction-free measurements” . The object is in a superposition of two wave packets inside its own Mach-Zehnder interferometer (see Fig. 6.) If $`D_2`$ (for the photon) clicks, the object is localized inside the interaction region $`W`$. However, the object itself is the test particle of another IFM (we can consider a gedanken situation in which the object which explodes when the photon reaches its location can, nevertheless, be manipulated by other means). If this other IFM is successful (i.e. “$`D_2`$” for the object clicks) then the other observer can claim that she localized the photon of the first experiment at $`W`$, i.e. that the photon passed through the lower arm of the interferometer on its way to $`D_2`$.

FIG. 6. Hardy’s Paradox. Two interferometers are tuned in such a way that, if they operate separately, there is a complete destructive interference towards detectors $`D_2`$. The lower arm of the photon interferometer intersects the upper arm of the object interferometer in $`W`$ such that the object and the photon cannot cross each other. When the photon and the object are sent together (they reach $`W`$ at the same time) then there is a nonzero probability for clicks of both detectors $`D_2`$. In this case one can infer that the object was localized at $`W`$ and also that the photon was localized at $`W`$. However, the photon and the object were not present in $`W`$ together. This apparently paradoxical situation does not lead to a real contradiction because all these claims are valid only if tested separately.

Paradoxically, all these claims are true (in the operational sense): if we look for the photon in $`W`$, we find it with certainty; if we look, instead, for the object in $`W`$, we find it with certainty too. Both claims are true separately, but not together: if we look for the pair, the photon and the object together, in $`W`$, we fail with certainty. Such peculiarities take place because we consider a pre- and post-selected situation (the post-selection is that in both experiments detectors $`D_2`$ click) . An interesting insight about this peculiar situation can be learned through the analysis of the weak measurements performed on the object and the photon inside their interferometers .

In spite of this peculiar feature, the experiment is still interaction-free in the following sense. If somebody would test the success of our experiment for localization of the object, i.e. would measure the location of the object shortly after the “meeting time” between the object and the photon, then we know with certainty that she would find the object in $`W`$ and, therefore, the photon cannot be there. Discussing the issue of the presence of the object with her, we can correctly claim that in our experiment the photon was not in the vicinity of the object. Indeed, given the assumption that she found the object, we know that she has not seen the photon in the lower arm of the interferometer, even if she looked for it there. However, if, instead of measuring the position of the object after the meeting time, she finds the object in a particular superposition (the superposition which with certainty reaches $`D_2`$), she can claim with certainty that the photon was in $`W`$. (Compare this with deterministic quantum interference experiments ).

## VI Momentum and energy transfer in the IFM

Probably, the largest misconception about the IFM is defining them as momentum and energy exchange-free measurements . The EV IFM can localize a bomb in an arbitrary small region without exploding it even if the quantum state of the bomb was spread out initially. Localization of an object without uncertain change in its momentum leads to immediate contradiction with the Heisenberg uncertainty principle. Identifying the interaction-free measurements as momentum-exchange free measurements, Simon and Platzman  derived “fundamental limits” on the IFM. They argued that the IFM can be performed only on infinitely sensitive bomb and that a bomb which is infinitely sensitive to any momentum transfer could not be placed in the vicinity of the IFM device from the beginning. These arguments fail because the EV IFM are not defined as momentum-exchange free measurements. (Probably, the misconception came because of frequent mentioning of Dicke’s paper  which concentrated on the issue of the energy exchange in his IFM.)

The arguments, similar to those of Simon and Platzman might be relevant for performing a modification of the EV IFM proposed by Penrose . He proposed a method for testing some property of an object without interaction. The object is again a bomb which explodes when anything, even a single photon, “touches” its trigger device. Some of the bombs are “duds”: their trigger device is locked to a body of the bomb and no explosion and no relative motion of the trigger device would happen when it is “touched”. Again, the paradox is that any touching of a trigger of a good bomb leads to an explosion, but, nevertheless, good bombs can be found (at least sometimes) without the explosion.

In the Penrose version of IFM, the bomb plays the role of one mirror of the interferometer, see Fig. 7. It has to be placed in the correct position. We are allowed to do so by holding the body of the bomb. However, the uncertainty principle puts limits on placing the bomb in its place before the experiment . Only if the position of the bomb (in fact, what matters is the position of the dud) is known exactly, the limitations are not present. In contrast, in the EV IFM the bomb need not be localized prior to the measurement: the IFM localizes it by itself.

FIG. 7. The Penrose bomb-testing device. The mirror of the good bomb cannot reflect the photon, since the incoming photon causes an explosion. Therefore, $`D_2`$ sometimes clicks. The mirror of a dud is connected to the massive body, and therefore the interferometer “works”, i.e. $`D_2`$ never clicks when the mirror is a dud.

The zero change in the momentum of the object, location of which is found in the IFM, is not a necessary condition for the measurement to be IFM, but there are IFM in which there is no change of the momentum of the object. Indeed, if the object has been localized before the IFM procedure, then its state and, therefore, its momentum distribution do not change during the process.

The relevant issue seems to be the change in the momentum of the observed object, but it is interesting to consider also the change in the momentum of the measuring device, thus analyzing the question of the exchange of the momentum. If the object is localized from the beginning then its state does not change, but the state of the photon does change: from the superposition of being in two arms of the interferometer it collapses into a localized wave packet in one arm of the interferometer. It can be arranged that the two separate wave packets of the photon have the same distribution of momentum. Then, the collapse to one wave packet will not change expectation value of any power of momentum of the photon.

Aharonov  has pointed out that although in this process there is no exchange of momentum in the above sense, still there is an exchange of certain physical variable. In the EV procedure there is an exchange of modular momentum. The collapse of the quantum wave of the photon from the superposition of the two wave packets separated by a distance $`a`$ to a single wave packet is accompanied by the change in the modular momentum $`p_{phot}\mathrm{mod}\frac{\mathrm{}}{a}`$. The modular momentum of the object localized at the lower arm of the interferometer from the beginning, $`p_{obj}\mathrm{mod}\frac{\mathrm{}}{a}`$, does not change (there is no any change in the quantum state of the object). One can, nevertheless, consider an exchange of modular momentum in this process: since $`p_{obj}\mathrm{mod}\frac{\mathrm{}}{a}`$ is completely uncertain, there is no contradiction with the conservation law for the total modular momentum.

Note that the situation in which the expectation values of any power of momentum remains unchanged, while expectation values of powers of modular momentum change, is also a feature of Aharonov-Bohm type effects in which the quantum state changes even though no local forces are acting.

The method of the EV IFM can be applied for performing various non-demolition measurements . Indeed, even if the measurement interaction can destroy the object, the method allows measurement without disturbing the object. However, not any non-demolition measurement is an IFM in the sense I discussed it here. In some nondemolition experiments the test particle of the measuring device explicitly passes through the location of the measured object. In other experiments the state of the object changes, but these changes are compensated at the end of the process . I suggest that such measurements should not be considered as interaction-free.

## VII  Modifications of the EV IFM

The optimal scheme presented in the IFM paper allows detection of almost 50% of the bombs without explosion (the rest explode in the process). Kwiat et al.  applied quantum Zeno effect for constructing the IFM scheme which, in principle, can be made arbitrary close to the 100% efficiency. The experiment with theoretical efficiency higher than 50% has been performed .

The almost 100% efficient scheme of Kwiat et al.  can be explained as follows. The experimental setup consists of two identical optical cavities coupled through a highly reflective mirror, see Fig. 8. A single photon initially placed in the left cavity. If the right cavity is empty, then, after a particular number $`N`$ of reflections, the photon with certainty will be in the right cavity. If, however, there is a bomb in the right cavity, the photon, with the probability close to 1 for large $`N`$, will be found in the left cavity. Testing at the appropriate time for the photon in the left cavity, will tell us if there is a bomb in the right cavity.

This method keeps all conceptual features of the EV IFM. If the photon is found in the left cavity, we are certain that there is an object in the right cavity. If the object is an ultra-sensitive bomb or if it is completely non-transparent object which does not reflect light backwards (e.g., it is a mirror rotated by $`45`$ degrees relative to the optical axes of the cavity as in the Kwiat et al. experiment) then, when we detect the photon in the left cavity we can claim that it never “touched” the object in the same sense as it is true in the original EV method.

FIG. 8. The almost 100% efficient scheme of the IFM. If there is a “bomb” or a nontransparent object in the right cavity, then the photon stays in the left cavity, with a probability to go to the right cavity which can be made arbitrary small by increasing the reflectivity of the mirror between the cavities. If, however, the right cavity is empty, then after some time the photon will move there with certainty.

Another modification of the EV IFM which leads to the efficiency of almost 100% has been proposed by Paul and Pavičić  and implemented in a laboratory by Tsegaye et al. . The basic ingredient of this method is an optical resonance cavity which is almost transparent when empty, and is an almost perfect mirror when there is an object inside. The advantage of the proposal of Paul and Pavičić is that it has just one cavity, and is easier to perform. In fact, this method has been recently applied for “exposure-free imaging” of a two-dimensional object . However, one cavity method has a conceptual drawback. In this experiment there is always a nonzero probability to reflect the photon even if the cavity is empty. Thus, detecting reflected photon cannot ensure presence of the object with 100% certainty. Essentially, this drawback has only an academic significance. In any real experiment there will be uncertainty anyway, and the uncertainty which I mentioned can be always reduced below the level of the experimental noise.

Other modifications of the IFM are related to interaction-free “imaging” and interaction-free measurements of semi-transparent objects . These experiments hardly pass the strict definition of the IFM in the sense that the photons do not pass in the vicinity of the object. However, they all achieve a very important practical goal, since we “see” the object reducing very significantly the irradiation of the object: this can allow measurements on fragile objects. Indeed, in spite of the fact that for distinguishing small differences in the transparency of an object the method is not very effective , it still can be useful for reduced irradiation pattern recognition .

Reasoning in the framework of the many-worlds interpretation (MWI)  leads to the statement that while we can find an object in the interaction-free manner, we cannot find out that a certain place is empty in the interaction-free way. Here, I mean “interaction-free” in the sense that no photons (or other particles) pass through the place in question. Getting information about some location in space without any particle being there is paradoxical because physical laws include only local interactions. In the case of finding the bomb, the MWI solves the paradox. Indeed, the laws apply to the whole physical Universe which includes all the worlds and, therefore, the reasoning must be true only when we consider all the worlds. Since there are worlds with the explosion we cannot say on the level of the physical Universe that no photons were at the location of the bomb. In contrast, when there is no bomb, there are no other worlds. The paradox in our world becomes the paradox for the whole Universe which is a real paradox. Thus, it is impossible to find a procedure which tests the presence of an object in a particular place such that no particles visit the place both in the case the object is there and in the case the object is not there. Quantitative analysis of the limitations due to this effect were recently performed by Reif who called the task “interaction-free sensing” . This effect also leads to limitations on the efficiency of “interaction-free computation” when all possible outcomes are considered .

## VIII  Conclusions

I have reviewed various analyses, proposals, and experiments of IFM and measurements based on the EV IFM method. The common feature of these proposals is that we obtain information about an object while significantly reducing its irradiation.

The meaning of the EV IFM is that if an object changes its internal state (not the quantum state of its center of mass) due to the radiation, then the method allows detection of the location of the object without any change in its internal state. There is no any fundamental limit on such IFM. The IFM allow measurements of position of infinitely fragile objects. In some sense it locates objects without “touching”, i.e. without particles of any kind passing through its vicinity. I have clarified the limited validity of this feature for IFM performed on quantum objects.

Numerous papers on the IFM interpreted the concept of “interaction-free” in many different ways. I hope that in this work I clarified the differences and stated unambiguously the meaning of the original proposal.

ACKNOWLEDGMENTS

It is a pleasure to thank Yakir Aharonov, Berge Englert, and Philip Pearle for helpful discussions. This research was supported in part by grant 471/98 of the Basic Research Foundation (administered by the Israel Academy of Sciences and Humanities) and the EPSRC grant GR/N33058.


text:
# How to observe fluctuating temperature?

## Abstract

We provide arguments that event-by-event (EBE) analysis of multiparticle production data are ideal place to search for the possible fluctuation of temperature characterizing hadronizing source in thermodynamical approach.

PACS numbers: 25.75.-q 24.60.-k 05.20.-y 05.70.Ln

In this note we would like to advertise the feasibility and importance of the observations of fluctuating temperature in high energy multiparticle production processes. Let us first list our chain of reasoning:

* ALICE will look (among other things) for the creation of Quark Gluon Plasma (QGP);
* this calls for a thermodynamical description of (at least some) relevant observables and this in turn calls for the temperature $`T`$ of the system under investigation as one of the most important quantities;
* $`T`$ can be deduced most directly (at least this is believed to be the case) by looking at $`p_T`$ spectra because ($`\mu _T=\sqrt{m^2+p_T^2}`$)

$$\frac{dN}{dp_T}\mathrm{exp}\left(\frac{\mu _T}{T}\right).$$
(1)

This is widely accepted approach, notwithstanding the fact that both details of what $`T`$ really means or whether (1) is a proper form for $`\mu _T`$-dependence are still subject to hot debate and modelling. Taking therefore (1) as our starting point we want to concentrate on question: is it possible that $`T`$ is fluctuating quantity  and if so, does it fluctuates only from event-to-event or also in a given event?

We are not going to discuss here the problem of internal consistency (or inconsistency) of the notion of fluctuations of temperature in thermodynamics referring in this matter to . What we want to do is to brings to ones attention the fact that event-by-event analysis allows (at least in principle) to detect fluctuations of temperature taking place in a given event. This is more than indirect measure of fluctuations of $`T`$ proposed some time ago in  or more direct fluctuations of $`T`$ from event to event discussed in .

To this end let us first remind our results presented in  where we have shown that fluctuation of the parameter in exponential distribution leads in a natural way (under some circumstances, of course, to be mentioned in a moment) to final distribution of the power-like form (know also as Lévy distribution):

$$\mathrm{exp}\left[\left(\frac{1}{T}\right)\mu _T\right]\left[1+(1q)\left(\frac{1}{T_0}\right)\mu _T\right]^{\frac{1}{1q}}.$$
(2)
Here averaging $`\mathrm{}`$ is performed over fluctuations of parameter (here our temperature) $`\frac{1}{T}`$ which take place around some mean value $`T_0`$ and should follow gamma distribution (see  for details). The new parameter occuring here (identical to the so called entropic index or nonextensivity parameter in Tsallis statistics ) is tightly connected with the size of such fluctuations, namely

$$q=\mathrm{\hspace{0.17em}1}+\omega $$
(3)
where

$$\omega =\frac{\left(\frac{1}{T}\right)^2\frac{1}{T}^2}{\frac{1}{T}^2}.$$
(4)
It is worth to mention that distribution of the Lévy type (2) has been observed already in inclusive processes . However, inclusive processes are not able to provide unambiguous answer what is the source of such behaviour. This can be done, such is our belief, only in the careful analysis of event-by-event data, especially those for heavy ion collisions. Two scenarios are possible here and should be subjected to experimental verification:

* $`T`$ is constant in each event but because of different initial conditions it fluctuates from event to event. In this case in each event one should find exponential dependence (1) with $`T=T_{event}`$ and possible departure from it will occur only after averaging over all events. It will reflect fluctuations originating in different initial conditions for each collision from which given event originates. This situation is illustrated in Fig. 1 where $`p_T`$ distributions for $`T=200`$ MeV (black symbols) and $`T=250`$ MeV (open symbols) are presented. All other details are the same as listed below for Fig. 2. Such values of $`T`$ correspond to typical uncertainties in $`T`$ expected at LHC due to different initial conditions. Notice that both curves presented here are straight lines.
* $`T`$ fluctuates in each event around some value $`T_0`$. In this case one should observe departure from the exponential behaviour already on the single event level which should be fully given (2) with $`q>1`$. It reflects situation when, due to some intrinsically dynamical reasons, different parts of a given event can have different temperatures . Fig. 2 shows typical event of this type obtained in simulations performed for central $`Pb+Pb`$ collisions taking place for beam energy equal $`E_{beam}=3A`$TeV in which density of particles in central region (defined by rapidity window $`1.5<y<1.5`$) is equal to $`\frac{dN}{dy}=6000`$ (this is the usual value given by event generators like VENUS, SHAKER, HIJING). Black symbols represent exponential dependence obtained for $`T=200`$ MeV (the same as in Fig. 1), open symbols show the power-like dependence as given by (2) with the same $`T`$ and with $`q=1.05`$ (notice that the corresponding curve bends slightly upward here). In this typical event we have $`18000`$ secondaries, i.e., practically the maximal possible number. Notice that points with highest $`p_T`$ correspond already to single particles.

One should stress here the following important fact: our $`\omega =q1`$ has physical meaning of the total heat capacity $`C`$, because according to a basic relation of thermodynamic  ($`\beta =\frac{1}{T}`$)

$$\frac{\sigma ^2(\beta )}{\beta ^2}=\frac{1}{C}=\omega =q1.$$
(5)
Therefore measuring in addition to the temperature $`T`$ also nonextensivity $`q`$ describing its fluctuation (and, because of this, the total heat capacity $`C`$) could be of great practical importance for our understanding of dynamics of heavy ion collisions . In particular it should not only facilitate checking the commonly made assumption that an approximate thermodynamics state is obtained in a single collision but also, by knowing the heat capacity, provide considerable information about its thermodynamics (especially on the existence and type of the possible phase transitions ) .

This work was partially supported by Polish Committee for Scientific Research (grants 2P03B 011 18 and 621/E-78/SPUB/CERN/P-03/DZ4/99).

Figure 1

Figure 2