text:
# Alternating sign matrices and tournaments

## 1 Introduction

An alternating sign matrix of order $`n`$ is an $`n`$-by-$`n`$ matrix with entries in $`\{1,0,1\}`$ such that each row and column has sum 1 and the nonzero entries in each row and column alternate in sign. For example

$$\left(\begin{array}{ccccc}\hfill 0& \hfill 0& \hfill 0& \hfill 1& \hfill 0\\ \hfill 0& \hfill 0& \hfill 1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 1& \hfill 0& \hfill 1& \hfill 1\\ \hfill 1& \hfill 1& \hfill 0& \hfill 1& \hfill 0\\ \hfill 0& \hfill 1& \hfill 0& \hfill 0& \hfill 0\end{array}\right).$$
(1)
The problem of enumerating alternating sign matrices has led to many deep results and difficult conjectures. For a history of alternating sign matrices see .

There are several combinatorial and physical structures equivalent to alternating sign matrices. One of the most fertile has been the square-ice model originally used in statistical mechanics. The square ice graph corresponding to (1) is

$$\begin{array}{ccccccccccc}& & & & & & & & & & \\ & & & & & & & & & & \\ & & & & & & & & & & \\ & & & & & & & & & & \\ & & & & & & & & & & \\ & & & & & & & & & & \\ & & & & & & & & & & \\ & & & & & & & & & & \\ & & & & & & & & & & \\ & & & & & & & & & & \\ & & & & & & & & & & \end{array}.$$
(2)
This directed graph has inward edges at the left and right and outward edges at the top and bottom. Both the in-degree and out-degree of all its degree four vertices equal two. These vertices are of six types, which we label according to their incident in-edges. *Horizontal* vertices have two horizontal in-edges, *vertical* vertices have two vertical in-edges and *northwest* vertices have in-edges pointing in the north (up) and west (left) directions. We define *southwest*, *northeast* and *southeast* vertices similarly. The correspondence between alternating sign matrices and square-ice graphs is characterized as follows: horizontal vertices correspond to entries 1, vertical vertices to entries $`1`$ and all other vertices to entries 0.

Bressoud  has asked for a bijective proof of the following identity

$$\underset{T𝒯_n}{}\lambda ^{U(T)}\underset{i=1}{\overset{n}{}}x_i^{\omega (i)}=\underset{A𝒜_n}{}\lambda ^{SW(A)}(1+\lambda )^{V(A)}\underset{i=1}{\overset{n}{}}x_i^{SW_i(A)+SE_i(A)+V_i(A)}$$
(3)
due essentially to Robbins and Rumsey . Here $`𝒜_n`$ is the set of $`n`$-by-$`n`$ alternating sign matrices, $`SW(A)`$, $`SE(A)`$ and $`V(A)`$ denote respectively the numbers of southwest, southeast and vertical vertices in the square-ice graph corresponding to $`A𝒜_n`$, and $`SW_i(A)`$, $`SE_i(A)`$ and $`V_i(A)`$ denote the numbers of vertices of the appropriate type in the $`i`$-th column of this graph. Also $`𝒯_n`$ is the set of tournaments on the set $`\{1,2,\mathrm{},n\}`$, that is the set of orientations on the complete graph with vertex set $`\{1,2,\mathrm{},n\}`$. Given $`T𝒯_n`$ we denote by $`\omega (i)`$ the out-degree of the vertex $`i`$ in $`T`$, and we let $`U(T)`$ be the number of upsets in $`T`$, that is the number of edges oriented from $`i`$ to $`j`$ with $`i>j`$.

We give a bijective proof of the following refinement of (3):

$$\underset{1i<jn}{}(x_i+y_j)=\underset{A𝒜_n}{}\underset{i=1}{\overset{n}{}}x_i^{SE_i(A)}y_i^{SW_i(A)}(x_i+y_i)^{V_i(A)}.$$
(4)
This equation is equivalent to \[3, Theorem 3.1\]. Putting $`y_i=\lambda x_i`$ in (4) gives (3) since the factor $`x_i+\lambda x_j`$ on the left corresponds to the edge between $`i`$ and $`j`$. This edge is either oriented from $`i`$ to $`j`$ and so contributes $`x_i`$ to the product, or is oriented from $`j`$ to $`i`$ and so contributes $`\lambda x_j`$ to the product. The latter case corresponds to an upset and so the correct power of $`\lambda `$ appears in the product.

## 2 Triangles

We use an alternative combinatorial model for alternating sign matrices, namely complete monotone triangles. A complete monotone triangle of order $`n`$ is a triangular array of integers with $`n`$ rows and $`k`$ entries in the $`k`$-th row. Each row is strictly increasing and the final row contains the entries $`1,2,\mathrm{},n`$ in ascending order. Each entry not in the final row lies weakly between the entries immediately to the left and right in the row below. Here is an example of a complete monotone triangle of order 5:

$$\begin{array}{ccccccccc}& & & & 4& & & & \\ & & & 3& & 4& & & \\ & & 2& & 3& & 5& & \\ & 1& & 3& & 4& & 5& \\ 1& & 2& & 3& & 4& & 5\end{array}.$$
(5)
To produce a complete monotone triangle from an alternating sign matrix we form a new matrix by taking its cumulative column sums. For instance (1) has cumulative column sums

$$\left(\begin{array}{ccccc}0& 0& 0& 1& 0\\ 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1\\ 1& 0& 1& 1& 1\\ 1& 1& 1& 1& 1\end{array}\right).$$
(6)
This new matrix has $`k`$ 1s in the $`k`$-th row with the remaining entries 0. We form a triangle by writing in the $`k`$-th row of the triangle, the positions of the $`k`$ 1s in the column sum matrix. Applying this to (6) gives (5). This gives a bijection between alternating sign matrices and complete monotone triangles of the same order.

The entries not in the bottom row of a complete monotone triangle fall into three types. Consider an entry $`j`$ and let $`i`$ and $`k`$ be its neighbours in the row below, so that

$$\begin{array}{ccc}& j& \\ i& & k\end{array}$$

is part of the triangle. Then either

(i) $`i=j<k`$,

(ii) $`i<j=k`$, or

(iii) $`i<j<k`$.

Entries of types (i), (ii) and (iii) correspond respectively to southeast, southwest and vertical vertices in column $`j`$ of the associated square-ice graph. We introduce a refinement of the notion of complete monotone triangle, namely that of *oriented complete monotone triangle*. An oriented complete monotone triangle is a complete monotone triangle with an orientation (left or right) given to each entry not in the bottom row. Entries of type (i) must be oriented to the right and entries of type (ii) must be oriented to the left. Entries of type (iii) may be oriented in either direction. We shall depict an oriented complete monotone triangle by replacing each right-oriented entry $`j`$ by a symbol $`x_j`$ and each left-oriented entry $`j`$ by a symbol $`y_j`$. Thus in the configuration

$$\begin{array}{cc}x_j& \\ & z_k\end{array}$$

where $`z_k`$ denotes either $`x_k`$, $`y_k`$ or $`k`$ (in the bottom row) we must have $`j<k`$ while in

$$\begin{array}{cc}& y_j\\ z_i& \end{array}$$

we must have $`i<j`$.

As an example, one of the oriented complete monotone triangles arising from (5) is

$$\begin{array}{ccccccccc}& & & & y_4& & & & \\ & & & y_3& & x_4& & & \\ & & y_2& & x_3& & y_5& & \\ & x_1& & y_3& & y_4& & y_5& \\ 1& & 2& & 3& & 4& & 5\end{array}.$$
(7)
As the type (iii) vertices in a complete monotone triangle correspond to the $`1`$ entries in the alternating sign matrix, an alternating sign matrix with $`r`$ $`1`$s gives rise to $`2^r`$ oriented complete monotone triangles. Denote the set of oriented complete monotone triangles of order $`n`$ by $`𝒪_n`$.

We define the *weight* of an oriented complete monotone triangle to be the product of the entries in the rows other than the last. Thus the weight of the triangle in (7) is $`x_1y_2x_3y_3^2x_4y_4^2y_5^2`$. It is clear that the right side of (4) is the sum of the weights of all elements of $`𝒪_n`$.

We define the weight of a tournament $`T𝒯_n`$ as the products of the weights of its edges where the weight of an edge oriented from $`i`$ to $`j`$ is $`x_i`$ if $`i<j`$ and $`y_i`$ if $`i>j`$. Then the left side of (4) is the sum of the weights of all elements of $`𝒯_n`$. We shall prove the following theorem.

###### Theorem 1

There is a weight-preserving bijection between $`𝒪_n`$ and $`𝒯_n`$.

The equation (4) is an immediate corollary. The remainder of the paper is devoted to the construction of the weight-preserving bijection $`\mathrm{\Phi }:𝒪_n𝒯_n`$ and its inverse $`\mathrm{\Psi }:𝒯_n𝒪_n`$.

We first indicate how to display a tournament in a triangle in a similar fashion to an oriented complete monotone triangle. We introduce new indeterminates $`a_{ij}`$ and $`b_{ij}`$ where $`1i<jn`$. For $`1k<n`$, let $`𝒱_k=\{a_{i,j},b_{i,j}:ji=k\}`$. Also let $`𝒳=\{x_i,y_j:1i,jn\}`$. Each tournament corresponds to a set of $`\frac{1}{2}n(n1)`$ of indeterminates in $`_{k=1}^{n1}𝒱_k`$ where we take $`a_{ij}`$ when there is an edge oriented from $`i`$ to $`j`$ and we take $`b_{ij}`$ when there is an edge oriented from $`j`$ to $`i`$. We arrange these symbols in $`n1`$ rows of a triangle where we put those entries in $`𝒱_{nj}`$ in the $`j`$-th row in ‘ascending order’. The $`i`$-th entry in row $`j`$ thus has subscript $`_{i(i+nj)}`$. We fill the $`n`$-th row with the numbers $`1,2,\mathrm{},n`$ in ascending order. For example,

$$\begin{array}{ccccccccc}& & & & a_{15}& & & & \\ & & & b_{14}& & b_{25}& & & \\ & & b_{13}& & b_{24}& & b_{35}& & \\ & b_{12}& & b_{23}& & a_{34}& & a_{45}& \\ 1& & 2& & 3& & 4& & 5\end{array}.$$
(8)
We now identify tournaments with triangles of this form. We define the bijections $`\mathrm{\Phi }`$ and $`\mathrm{\Psi }`$ by taking a triangle of one type and converting it by a series of moves to one of the other type. We pass through a series of intermediate triangles which in general contain variables $`x_i`$ and $`y_i`$ and variables $`a_{ij}`$ and $`b_{ij}`$. We define a *triangle* of order $`n`$ as an $`n`$-rowed triangle with $`k`$ entries in the $`k`$-th row and with $`1,2,\mathrm{},n`$ in the last row and entries drawn from $`𝒳_{k=1}^{n1}𝒱_k`$ in the first $`(n1)`$-rows. Each of our primitive moves either permutes the entries of the triangle or replaces an $`a_{ij}`$ by $`x_i`$ or an $`x_i`$ by an $`a_{ij}`$ or a $`b_{ij}`$ by $`y_j`$ or a $`y_j`$ by a $`b_{ij}`$. We define the *weight* of a triangle as the product of the weights of its entries above its bottom row where $`x_i`$, $`y_j`$, $`a_{ij}`$ and $`b_{ij}`$ have weights $`x_i`$, $`y_j`$, $`x_i`$ and $`y_j`$ respectively. This weighting agrees with that of oriented monotone triangles and tournaments, and will be preserved under each primitive move.

We interpret $`x_j`$ as an outgoing edge from vertex $`j`$ to some as yet unknown larger vertex. Similarly $`y_j`$ represents an outgoing edge from vertex $`j`$ to an unknown smaller vertex. Also $`a_{ij}`$ denotes an edge oriented from $`i`$ to $`j`$ ($`i<j`$) and $`b_{ij}`$ denotes an edge oriented from $`j`$ to $`i`$ ($`i<j`$). At intermediate stages of our algorithm, the $`a_{ij}`$s and $`b_{ij}`$s that occur are still provisional, as for instance $`a_{ij}`$ may be replaced by $`x_i`$ and then by $`a_{ik}`$ for $`kj`$.

For convenience we suppose that our triangles have an empty “row 0” above the first row. We also use the symbols $`z_i`$ to denote indifferently $`x_i`$, $`y_i`$ or $`i`$ (appearing in the final row) and $`c_{ij}`$ to denote indifferently $`a_{ij}`$ or $`b_{ij}`$.

We need to define the notion of an *admissible* triangle. A triangle with no entry in $`_{k=1}^{n1}𝒱_k`$ will be admissible if and only if it lies in $`𝒪_n`$ and a triangle with no entry in $`𝒳`$ will be admissible if and only if it lies in $`𝒯_n`$. At each stage of our algorithm, admissibility will be preserved.

A triangle is admissible if and only if the following conditions hold:

(i) it has an admissible ranking,

(ii) it has the monotone diagonal property,

(iii) it has the monotone row property.

We explain the conditions in turn. We say that a row of a triangle is an $`𝒳`$-row if all its entries lie in $`𝒳`$ and that it is a is a $`𝒱`$-row if all its entries lie in some $`𝒱_k`$. (We regard the notional row 0 as both a $`𝒳`$-row and a $`𝒱`$-row). An *admissible* ranking of a triangle is an assignment of non-negative integers, called ranks, to each row of the triangle (including row 0) with the following properties:

* the $`n`$-th row has rank 0 and the $`(n1)`$-th row has rank 1,
* if the $`r`$-th row ($`r>0`$) has rank $`k`$ then either row $`r`$ is a $`𝒳`$-row and row $`r1`$ also has rank $`k`$, or row $`r`$ has all its entries in $`𝒱_k`$ and row $`r1`$ has rank $`k+1`$.

It follows that the ranks in an admissible ranking decrease weakly as one descends the triangle and that the ranks of the $`𝒱`$-rows form the sequence $`d,d1,\mathrm{},2,1`$ for some $`d0`$. The rank of a $`𝒱`$-row with entries in $`𝒱_k`$ is $`k`$.

If a triangle has an admissible ranking then it is plain that the ranking is uniquely determined. We call such a triangle a *ranked* triangle.

To explain the monotone diagonal and monotone row properties we need the notion of the left and right values of an entry in a ranked triangle. Let $`u`$ be an entry in a ranked triangle. It is assigned a *left value* $`l(u)`$ and a *right value* $`r(u)`$. Note that these values will in general depend on the rank of the row in which $`u`$ lies, not simply on the indeterminate $`u`$ itself. When $`u=a_{ij}`$ or $`b_{ij}`$ we define $`l(u)=i`$ and $`r(u)=j`$. If $`u=x_i`$ lies in a row with rank $`t`$ we define $`l(u)=i`$ and $`r(u)=i+t`$ while if $`u=y_j`$ lies in a row with rank $`t`$ we define $`l(u)=jt`$ and $`r(u)=j`$. Finally if $`u=i`$ is a number in the last row we let $`l(u)=l(v)=i`$. In all cases $`r(u)l(u)`$ is the rank of the row containing $`u`$.

To define the monotone diagonal property consider three entries in a ranked triangle appearing in the following arrangement

$$\begin{array}{ccc}& v& \\ u& & w\end{array}.$$
(9)
An arrangement (9) has the *monotone diagonal property* if

* $`l(u)l(v)`$ and $`r(v)r(w)`$,
* if $`u=y_j`$ for some $`j`$ then $`l(u)<l(v)`$, and
* if $`w=x_j`$ for some $`j`$ then $`r(v)<r(w)`$.

A ranked triangle has the monotone diagonal property if all arrangements (9) within have the monotone diagonal property. The first of these conditions states that the left values increase weakly when traversing northeast diagonals and the right values increase weakly when traversing southeast diagonals. If the second condition is relevant, then the two rows represented in (9) have the same rank, and we can rewrite the condition as $`j<r(v)`$. Similarly the final condition is equivalent to $`l(v)<j`$.

If $`T`$ is a ranked triangle having the monotone diagonal property then the the left value of the $`j`$-th entry in each row is at least $`j`$ and that the right value of the $`k`$-th entry from the right in each row is at most $`n+1k`$.

We say that an arrangement (9) has the *monotone row property* if

* $`l(u)<l(w)`$.

We say that a ranked triangle has the *monotone row property* if every arrangement (9) within has the monotone row property.

###### Lemma 1

A triangle of order $`n`$ all of whose rows but the last are $`𝒳`$-rows is admissible if and only if it lies in $`𝒪_n`$.

Proof  Suppose that $`T𝒪_n`$. Then $`T`$ clearly has an admissible ranking with each row but the last having rank 1. Let us consider the arrangement (9). We divide into cases according to whether $`u`$, $`v`$ and $`w`$ are $`x`$s or $`y`$s or they lie in the last row. The cases where $`v=y_j`$ are similar to those where $`v=x_j`$ so we look at these in detail:

(i) $`u=x_i`$, $`w=x_k`$. Then $`ij<k`$. Hence $`l(u)=ij=l(v)`$ and $`r(v)=j+1<k+1=r(w)`$. Also $`l(u)=i<k=l(w)`$.

(ii) $`u=x_i`$, $`w=y_k`$. Then $`ij<k`$. Hence $`l(u)=ij=l(v)`$ and $`r(v)=j+1k=r(w)`$. We consider the entry between $`u`$ and $`w`$ in the next row:

$$\begin{array}{ccc}& x_j& \\ x_i& & y_k\\ & z_l& \end{array}.$$

We have $`i<l<k`$ so that $`i+1<k`$ and so $`l(u)=i<k1=l(w)`$.

(iii) $`u=y_i`$, $`w=x_k`$. Then $`ij<k`$. Hence $`l(u)=i1<j=l(v)`$ and $`r(v)=j<k=r(w)`$. Also $`l(u)+1=i<k=l(w)`$.

(iv) $`u=y_i`$, $`w=y_k`$. Then $`ij<k`$. Hence $`l(u)=i1<j=l(v)`$ and $`l(v)=jk1=l(w)`$. Also $`l(u)=i1<k1=l(w).`$

(v) $`u=i`$, $`w=k`$ (in the last row). Then $`ij<k`$. Hence $`l(u)=ij=l(v)`$ and $`r(v)=j+1k=r(w)`$.

In each case, the monotone diagonal and monotone row properties are satisfied. Hence $`T`$ is an admissible triangle.

Now suppose that $`T`$ is an admissible triangle with each row but the last an $`𝒳`$-row. Then all rows but the last are ranked 1. Again consider the arrangement (9) and divide into cases as above. As before we consider in detail only the cases where $`v=x_j`$ as the cases where $`v=y_j`$ are similar.

(i) $`u=x_i`$, $`w=x_k`$. Then $`i=l(u)l(v)=j`$ and $`j=r(v)1<r(w)1=k`$. Hence $`i<k`$.

(ii) $`u=x_i`$, $`w=y_k`$. Then $`i=l(u)l(v)=j`$ and $`j=r(v)1r(w)1<r(w)=k`$. Hence $`i<k`$.

(iii) $`u=y_i`$, $`w=x_k`$. Then $`i=l(u)+1<l(v)+1=j+1`$ and so $`ij`$. Also $`j=r(v)1<r(w)1=k`$. Hence $`i<k`$.

(iv) $`u=y_i`$, $`w=y_k`$. Then $`i=l(u)+1<l(v+1)=j+1`$ and so $`ij`$. Also $`j=r(v)1r(w)1=k1`$ and so $`j<k`$. Hence $`i<k`$.

(v) $`u=i`$, $`w=k`$ (in the last row). Then $`i=l(u)l(v)=j`$ and $`j=r(v)1r(w)1=k1`$ and so $`j<k`$.

It follows that $`T`$ is an oriented complete monotone triangle. $`\mathrm{}`$

###### Lemma 2

A triangle of order $`n`$ all of whose rows but the last are $`𝒱`$-rows is admissible if and only if it lies in $`𝒯_n`$.

Proof  If the triangle $`T`$ with no $`𝒳`$-rows is admissible then the rank of the $`k`$-th row must be $`t=nk`$. Its entries must contain each of the $`k`$ possible subscripts of the form $`_{ii+t}`$ in increasing order, by the monotone row property. It must therefore be a tournament.

Conversely suppose that $`T`$ is a tournament. In any arrangement (9) if $`l(u)=i`$ then $`r(u)=i+t`$ where $`t`$ is the rank of the lower row and then $`l(v)=i`$, $`r(v)=i+t+1`$, $`l(w)=i+1`$ and $`r(w)=i+t+1`$. It is then plain that the monotone diagonal and monotone row properties hold, so that $`T`$ is admissible. $`\mathrm{}`$

## 3 The algorithm

We define two operations on admissible triangles. Each operates on a pair of consecutive rows: rows $`d1`$ and $`d`$ where $`1d<n`$. The operation of *raising* can be applied when row $`d`$ is a $`𝒳`$-row and and row $`d1`$ is a $`𝒱`$-row (including the case when $`d1=0`$). Rows $`d1`$ and $`d`$ then have the same rank $`t`$. We start by making the following swaps in rows $`d1`$ and $`d`$ whenever possible

$$\begin{array}{cc}& b_{jk}\\ x_j& \end{array}\begin{array}{cc}& x_j\\ b_{jk}& \end{array}$$

and

$$\begin{array}{cc}a_{jk}& \\ & y_k\end{array}\begin{array}{cc}y_k& \\ & a_{jk}\end{array}.$$

We then replace any $`a_{jk}`$ remaining in row $`d1`$ by $`x_j`$ and any $`b_{jk}`$ remaining in row $`d1`$ by $`y_k`$. We then replace all $`x_i`$ in row $`d`$ by $`a_{ii+t}`$ and all $`y_j`$ in row $`r`$ by $`b_{jtj}`$. For instance

$$\begin{array}{ccccccc}& b_{13}& & a_{57}& & a_{68}& \\ x_1& & y_5& & y_7& & x_7\end{array}$$

first becomes

$$\begin{array}{ccccccc}& x_1& & y_7& & a_{68}& \\ b_{13}& & y_5& & a_{57}& & x_7\end{array}$$

and finally becomes

$$\begin{array}{ccccccc}& x_1& & y_7& & x_6& \\ b_{13}& & b_{35}& & a_{57}& & a_{79}.\end{array}$$

It is not immediately obvious that when we introduce an $`a_{ii+t}`$ or a $`b_{jtj}`$ that $`i+tn`$ or $`jt1`$. For the moment we shall ignore this difficulty. Later we will show that raising preserves admissibility. As the left and right values of each entry in an admissible triangle lie between 1 and $`n`$ inclusive, then we must have $`i+tn`$ or $`jt1`$ as appropriate.

We denote this raising operation by $`R_d`$. The rank of row $`d1`$ has now been raised to $`t+1`$ while the ranks of the remaining rows are left unchanged. Also the weight of the new triangle is the same as that of the old.

###### Proposition 1

When applied to an admissible triangle, the raising operator $`R_d`$ produces an admissible triangle.

Proof  Let $`T`$ be an admissible triangle with row $`d1`$ and $`d`$ having rank $`t`$ and with row $`d1`$ a $`𝒱`$-row and row $`d`$ an $`𝒳`$-row. Let $`T^{}=R_d(T)`$.

First note that the operation of raising does not alter the left and right values of the entries in row $`d`$. In row $`d1`$ suppose the entry $`v`$ is replaced by $`v^{}`$. If $`v^{}=x_i`$ then $`l(v^{})=l(v)`$ and $`r(v^{})=r(v)+1`$, while if $`v^{}=y_j`$ then $`r(v^{})=r(v)1`$ and $`r(u^{})=r(u)`$.

Suppose an arrangement (9) in $`T`$ becomes

$$\begin{array}{ccc}& v^{}& \\ u^{}& & w^{}\end{array}$$
(10)
in $`T^{}`$. We need to check that (10) has the monotone diagonal and monotone row properties. Let the lower row in (10) be row $`e`$. The entries in (9) and (10) will be the same unless $`e=d1`$, $`d`$ or $`d+1`$. Also we only need to show the monotone row property when $`e=d1`$ or $`d`$.

We can swiftly dispose of the monotone diagonal property when $`e=d+1`$. In this case $`u=u^{}`$ and $`w=w^{}`$. Also $`l(v)=l(v^{})`$ and $`r(v)=r(v^{})`$. The monotone diagonal property for (10) follows immediately from that for (9).

Now consider the case where $`e=d1`$. In this case $`l(u^{})=l(u)`$ or $`l(u)1`$ and $`r(w^{})=r(w)`$ or $`r(w)+1`$. Also $`v=v^{}`$. Thus $`l(u^{})l(u)l(v)=l(v^{})`$ and $`r(v^{})=r(v)r(w)r(w^{})`$. If $`u^{}=y_j`$, then $`l(u^{})=l(u)1<l(v)=l(v^{})`$. Similarly if $`w^{}=x_j`$, then $`r(v^{})=r(v)<r(w)+1=r(w^{})`$. Also $`l(u^{})<l(w^{})`$ unless $`l(w)=l(u)+1`$, $`u^{}=x_i`$ and $`w^{}=y_j`$ for some $`i`$ and $`j`$. Then $`l(u)=i`$, $`r(u)=j1`$, $`l(w)=i+1`$, $`r(w)=j`$ and $`ji=t+1`$. Consider the entry in $`T`$ below $`u`$ and $`w`$:

$$\begin{array}{ccc}& v& \\ u& & w\\ & q& \end{array}.$$

From the monotone diagonal property of $`T`$, $`q`$ must be either $`x_{i+1}`$ or $`y_{j1}`$. Suppose the former. Then $`w`$ cannot be $`b_{i+1j}`$ since that would be swapped with $`q`$ yielding $`w^{}=x_{i+1}`$. Thus $`w=a_{i+1,j}`$ and for $`w^{}`$ to be $`y_j`$ we need the entry following $`q`$ in row $`d`$ in $`T`$ to be $`y_j`$:

$$\begin{array}{cccc}u& & a_{i+1j}& \\ & x_{i+1}& & y_j\end{array}.$$

But then in row $`d`$, $`l(x+1)=i+1`$ and $`r(x+1)=jt=i+1`$, violating the monotone row property for (9). A similar argument yields a contradiction when $`q=y_{j1}`$. Hence (10) also has the monotone diagonal and monotone row properties.

Finally suppose that $`d=e`$. Now $`l(u)=l(u^{})`$ and $`l(v^{})\{l(v)1,l(v)\}`$. Thus $`l(u^{})l(v^{})`$ unless $`l(u)=l(v)`$ and $`v^{}=y_j`$. Then $`u=x_{jt}`$ or $`y_j`$ and $`v=a_{jtj}`$ or $`v=b_{jtj}`$. If $`u=y_j`$ then $`l(u)=jt=l(v)`$ contrary to the monotone diagonal property for (9). Thus $`u=x_{jt}`$. If $`v=b_{jtj}`$ then $`u`$ and $`v`$ are swapped giving $`v^{}=x_{jt}`$. Thus $`v=a_{jtj}`$. As $`v^{}=y_j`$ then $`y_j`$ must succeed $`x_{jt}`$ in row $`d`$ of $`T`$:

$$\begin{array}{ccc}& a_{jtj}& \\ x_{jt}& & y_j\end{array}.$$

But then in row $`d`$ of $`T`$, $`l(x_{jt})=jt=l(y_j)`$ contrary to the monotone row property of $`T`$. Thus $`l(u^{})l(v^{})`$. Similarly $`r(v^{})r(w^{})`$. Thus (9) has the monotone diagonal property. As row $`d`$ in $`T^{}`$ has the same left and right values as the row $`d`$ of $`T`$, then (10) has the monotone row property. We conclude that the triangle $`T^{}`$ is admissible. $`\mathrm{}`$

The inverse of raising is *lowering*. This time suppose that row $`d`$ ($`1d<n`$) is a $`𝒱`$-row of rank $`t`$ and that row $`d1`$ (including the case $`d1=0`$) is a $`𝒳`$-row. Then row $`d1`$ has rank $`t+1`$. We make the swaps

$$\begin{array}{cc}& x_j\\ b_{jk}& \end{array}\begin{array}{cc}& b_{jk}\\ x_j& \end{array}$$

and

$$\begin{array}{cc}y_k& \\ & a_{jk}\end{array}\begin{array}{cc}a_{jk}& \\ & y_k\end{array}$$

where possible in rows $`d1`$ and $`d`$. We then replace the $`a_{jk}`$ and $`b_{jk}`$ in row $`d1`$ by $`x_j`$ and $`y_k`$ and the $`x_j`$ and $`y_k`$ in row $`d`$ by $`a_{jj+t}`$ and $`b_{ktk}`$. Again, it will follow from the fact that lowering preserves admissibility that $`j+tn`$ or $`kt1`$ as appropriate. The new triangle has an admissible ranking. All the ranks are unchanged save for row $`d1`$ whose rank is lowered from $`t+1`$ to $`t`$. We denote this lowering operator by $`L_d`$.

###### Proposition 2

When applied to an admissible triangle, the lowering operator $`L_d`$ produces an admissible triangle.

Proof  Let $`T`$ be an admissible triangle with row $`d1`$ an $`𝒳`$-row and row $`d`$ a $`𝒱`$-row of rank $`t`$. Then row $`d1`$ of $`T`$ has rank $`t+1`$. Let $`T^{}=L_d(T)`$.

The lowering operation does not alter the left and right values in row $`d`$. Suppose that the entry $`v`$ in row $`d1`$ is replaced by $`v^{}`$. If $`v=x_j`$ then $`l(v^{})=l(v)`$ and $`r(v^{})=r(v)1`$ while if $`v=y_j`$ then $`l(v^{})=l(v)+1`$ and $`r(v^{})=r(v)`$.

Suppose we have an arrangement (9) having lower row $`e`$, becoming (10) after lowering. They are identical unless $`e\{d1,d,d+1\}`$.

When $`e=d+1`$ the monotone row property of (10) is immediate. Also the monotone diagonal property follows as the values in row $`d`$ and the entries in row $`d+1`$ are unchanged.

Suppose that $`e=d1`$. Row $`d1`$ in $`T^{}`$ is a $`𝒱`$-row. We have $`l(u^{})\{l(u),l(u)+1\}`$ and $`l(v^{})=l(v)`$ so that $`l(u^{})l(v^{})`$ unless $`l(u)=l(v)`$ and $`l(u^{})=l(u)+1`$. In this case $`u=y_j`$ and so $`l(u)<l(v)`$ contrary to hypothesis. Hence $`l(u^{})l(v^{})`$ and similarly $`r(v^{})r(w^{})`$. Thus (10) has the monotone diagonal property. As also $`l(w^{})\{l(w),l(w)+1\}`$ and $`l(u)<l(w)`$ then $`l(u^{})<l(v^{})`$ unless $`l(u)+1=l(w)`$, $`l(u^{})=l(u)+1`$ and $`l(w^{})=l(w)`$. In this case $`u=y_i`$ and $`w=x_j`$ so that by the monotone diagonal property for (9) we have $`l(u)<l(v)`$ and $`r(v)<r(w)`$. Consequently $`l(v)<l(w)`$ and so $`l(w)>l(u)+1`$ contrary to hypothesis. Hence (10) also has the monotone row property.

Finally suppose that $`e=d`$. As $`l(v^{})\{l(v),l(v)+1\}`$ then $`l(u^{})=l(u)l(v)l(v^{})`$. Similarly $`r(v^{})r(v)r(w)=r(w^{})`$. Suppose that $`u^{}=y_i`$. We must show that $`l(u^{})<l(v^{})`$. This is valid unless $`l(u^{})=l(v^{})`$. If so their common value is $`it`$. As $`l(v^{})=it`$ and $`r(v^{})=t`$ then $`v=x_{it}`$ or $`y_i`$. Also $`u=a_{iti}`$ or $`b_{iti}`$. We cannot have $`v=y_i`$ for then $`l(v)=it1`$ and $`l(u)=it`$ so that $`l(u)l(v)`$. But if $`v=x_{it}`$ and $`u=b_{iti}`$ then $`u`$ and $`v`$ are swapped so that $`u^{}=x_{it}`$. If $`v=x_{it}`$ and $`u=a_{iti}`$ the only way that $`u^{}`$ can be equal to $`y_i`$ is if the entry preceding $`u`$ in the $`(d1)`$-th row of $`T`$ is $`y_i`$ so that we get

$$\begin{array}{cccc}y_i& & x_{it}& \\ & a_{iti}& & w\end{array}.$$

But in this case the left values of the entries in row $`d1`$ are $`it1`$ and $`it`$ which violates the the condition that $`T`$ has the monotone row property. Hence $`l(u^{})<l(v^{})`$. Similarly if $`v^{}=x_j`$ then $`r(v^{})<r(w^{})`$ and so (10) has the monotone diagonal property.

As the values of the entries in row $`d`$ do not change, then (10) has the monotone row property. We conclude that the triangle $`T^{}`$ is admissible. $`\mathrm{}`$

###### Lemma 3

The operations $`R_d`$ and $`L_d`$ are inverse: if we operate on an admissible triangle by $`R_d`$ and then $`L_d`$ we regain the initial triangle. Similarly if we follow $`L_d`$ by $`R_d`$.

Proof  Suppose that $`T`$ is an admissible triangle and that $`T^{}=R_d(T)`$ is defined. When we raise $`T`$ by $`R_d`$ we first swap some pairs of entries and then when we lower $`T^{}`$ by $`L_d`$ these entries are swapped back. If we can show that no other pairs of entries are swapped when lowering we are done, since it is plain that the remaining entries return to their original state. Suppose after raising we have a configuration

$$\begin{array}{cc}& x_j\\ b_{jk}& \end{array}$$

which has not arisen from swapping the entries. This must have come from the configuration

$$\begin{array}{cc}& a_{jk}\\ y_k& \end{array}$$

which is banned by the monotone diagonal property. Similarly a configuration

$$\begin{array}{cc}y_k& \\ & a_{jk}\end{array}$$

cannot arise except by swapping. Hence raising followed by lowering gives the identity. Similarly lowering followed by raising gives the identity. $`\mathrm{}`$

We can now describe the bijections $`\mathrm{\Phi }`$ and $`\mathrm{\Psi }`$. We define

$$\mathrm{\Phi }=(R_1R_2R_3\mathrm{}R_{n1})\mathrm{}(R_1R_2R_3)(R_1R_2)(R_1).$$

It is easy to see that $`\mathrm{\Phi }(T)`$ is well-defined for $`T𝒪_n`$ and that $`\mathrm{\Phi }(T)𝒯_n`$. Its inverse $`\mathrm{\Psi }`$ is then

$$(L_1)(L_2L_1)(L_3L_2L_1)\mathrm{}(L_{n1}\mathrm{}L_3L_2L_1).$$

As $`\mathrm{\Phi }`$ and $`\mathrm{\Psi }`$ are composites of weight-preserving maps, they too are weight-preserving. This completes the proof of Theorem 1

## 4 An example

As an example let us apply $`\mathrm{\Phi }`$ to the oriented complete monotone triangle (7). We indicate the rank of each row in brackets at the end, including the rank of the empty row 0. Here is (7) in this notation:

$$\begin{array}{cccccccccc}& & & & & & & & & [1]\\ & & & & y_4& & & & & [1]\\ & & & y_3& & x_4& & & & [1]\\ & & y_2& & x_3& & y_5& & & [1]\\ & x_1& & y_3& & y_4& & y_5& & [1]\\ 1& & 2& & 3& & 4& & 5& [0]\end{array}.$$

We first apply the operator $`R_1`$ giving

$$\begin{array}{cccccccccc}& & & & & & & & & [2]\\ & & & & b_{34}& & & & & [1]\\ & & & y_3& & x_4& & & & [1]\\ & & y_2& & x_3& & y_5& & & [1]\\ & x_1& & y_3& & y_4& & y_5& & [1]\\ 1& & 2& & 3& & 4& & 5& [0]\end{array}.$$

Next apply $`R_2`$:

$$\begin{array}{cccccccccc}& & & & & & & & & [2]\\ & & & & y_4& & & & & [2]\\ & & & b_{23}& & a_{45}& & & & [1]\\ & & y_2& & x_3& & y_5& & & [1]\\ & x_1& & y_3& & y_4& & y_5& & [1]\\ 1& & 2& & 3& & 4& & 5& [0]\end{array}.$$

Then $`R_1`$:

$$\begin{array}{cccccccccc}& & & & & & & & & [3]\\ & & & & b_{24}& & & & & [2]\\ & & & b_{23}& & a_{45}& & & & [1]\\ & & y_2& & x_3& & y_5& & & [1]\\ & x_1& & y_3& & y_4& & y_5& & [1]\\ 1& & 2& & 3& & 4& & 5& [0]\end{array}.$$

Next $`R_3`$:

$$\begin{array}{cccccccccc}& & & & & & & & & [3]\\ & & & & b_{24}& & & & & [2]\\ & & & y_3& & y_5& & & & [2]\\ & & b_{12}& & a_{34}& & a_{45}& & & [1]\\ & x_1& & y_3& & y_4& & y_5& & [1]\\ 1& & 2& & 3& & 4& & 5& [0]\end{array}.$$

Then $`R_2`$:

$$\begin{array}{cccccccccc}& & & & & & & & & [3]\\ & & & & y_4& & & & & [3]\\ & & & b_{13}& & b_{35}& & & & [2]\\ & & b_{12}& & a_{34}& & a_{45}& & & [1]\\ & x_1& & y_3& & y_4& & y_5& & [1]\\ 1& & 2& & 3& & 4& & 5& [0]\end{array}.$$

Now $`R_1`$:

$$\begin{array}{cccccccccc}& & & & & & & & & [4]\\ & & & & b_{14}& & & & & [3]\\ & & & b_{13}& & b_{35}& & & & [2]\\ & & b_{12}& & a_{34}& & a_{45}& & & [1]\\ & x_1& & y_3& & y_4& & y_5& & [1]\\ 1& & 2& & 3& & 4& & 5& [0]\end{array}.$$

Next $`R_4`$:

$$\begin{array}{cccccccccc}& & & & & & & & & [4]\\ & & & & b_{14}& & & & & [3]\\ & & & b_{13}& & b_{35}& & & & [2]\\ & & x_1& & y_4& & y_5& & & [2]\\ & b_{12}& & b_{23}& & a_{34}& & a_{45}& & [1]\\ 1& & 2& & 3& & 4& & 5& [0]\end{array}.$$

Then $`R_3`$:

$$\begin{array}{cccccccccc}& & & & & & & & & [4]\\ & & & & b_{14}& & & & & [3]\\ & & & x_1& & y_5& & & & [3]\\ & & b_{13}& & b_{24}& & b_{35}& & & [2]\\ & b_{12}& & b_{23}& & a_{34}& & a_{45}& & [1]\\ 1& & 2& & 3& & 4& & 5& [0]\end{array}.$$

Next $`R_2`$:

$$\begin{array}{cccccccccc}& & & & & & & & & [4]\\ & & & & x_1& & & & & [3]\\ & & & b_{14}& & b_{25}& & & & [3]\\ & & b_{13}& & b_{24}& & b_{35}& & & [2]\\ & b_{12}& & b_{23}& & a_{34}& & a_{45}& & [1]\\ 1& & 2& & 3& & 4& & 5& [0]\end{array}.$$

Finally $`R_1`$:

$$\begin{array}{cccccccccc}& & & & & & & & & [5]\\ & & & & a_{15}& & & & & [4]\\ & & & b_{14}& & b_{25}& & & & [3]\\ & & b_{13}& & b_{24}& & b_{35}& & & [2]\\ & b_{12}& & b_{23}& & a_{34}& & a_{45}& & [1]\\ 1& & 2& & 3& & 4& & 5& [0]\end{array}.$$

Hence $`\mathrm{\Phi }`$ takes the oriented complete monotone triangle (7) to the tournament (8).

## 5 Remarks

We have defined $`\mathrm{\Phi }`$ and $`\mathrm{\Psi }`$ by using the operators $`R_d`$ and $`L_d`$ in a fixed order. However it is not hard to prove that performing any achievable sequence of $`\left(\genfrac{}{}{0pt}{}{n}{2}\right)`$ raising (or lowering) operations produces the same map.

###### Proposition 3

Let $`N=\frac{1}{2}n(n1)`$ and suppose that $`R_{u_j}`$ $`(1jN)`$ are raising operators such that

$$\mathrm{\Phi }^{}=R_{u_N}R_{u_{N1}}\mathrm{}R_{u_2}R_{u_1}$$

is a well-defined map from $`𝒪_n`$ to $`𝒯_n`$. Then $`\mathrm{\Phi }^{}=\mathrm{\Phi }`$. Similarly if $`L_{u_j}`$ $`(1jN)`$ are lowering operators such that

$$\mathrm{\Psi }^{}=L_{u_N}L_{u_{N1}}\mathrm{}L_{u_2}L_{u_1}$$

is a well-defined map from $`𝒯_n`$ to $`𝒪_n`$. Then $`\mathrm{\Psi }^{}=\mathrm{\Psi }`$.

Proof  We need only prove the assertion concerning raising operators, as that for lowering operators follows by taking inverses. It is easy to see that if $`ij`$, $`T`$ is a triangle and both $`R_i(T)`$ and $`R_j(T)`$ exist, then $`|ij|2`$ and $`R_jR_i(T)`$ and $`R_iR_j(T)`$ exist and are equal. Also if $`|ij|2`$ and $`R_iR_j(T)`$ exists then $`R_i(T)`$ exists. Thus if $`|ij|2`$ we have $`R_iR_j=R_jR_i`$ in the sense that if one side exists so does the other and they are equal.

The definition of $`\mathrm{\Phi }`$ is framed so that

$$\mathrm{\Phi }=R_{v_N}R_{v_{N1}}\mathrm{}R_{v_2}R_{v_1}$$

where for each $`j`$, $`v_j`$ is the least$`v`$ such that

$$R_vR_{v_{j1}}\mathrm{}R_{v_2}R_{v_1}$$

is well-defined on $`𝒪_n`$.

Suppose that $`u_jv_j`$ for some $`j`$, and take $`j`$ to be the least such for which this holds. Then $`u_j>v_j`$. Since $`R_j`$ increases the rank of row $`j1`$ by 1, the sequences of $`u_i`$s and of $`v_i`$s are permutations of each other. Hence for some $`k>j`$ we have $`u_k=v_j`$ and take $`k`$ to be the least such. Let $`T^{}=R_{u_{j1}}\mathrm{}R_1(T)`$ where $`T`$ is any element of $`𝒪_n`$. Then row $`u_j`$ of $`T^{}`$ is an $`𝒳`$-row and all previous rows are $`𝒱`$-rows. When we apply a sequence of raising operators to $`T^{}`$ we cannot apply an operator $`R_w`$ for $`w<v_j`$ until we have applied the operator $`T_{v_j}`$ since the rows 1 to $`v_j1`$ will remain as $`𝒱`$-rows and row $`v_j`$ as a $`𝒳`$-row until this occurs. Also $`T_{v_j+1}`$ cannot be applied until $`T_{v_j}`$ has been since row $`T_{v_j}`$ will remain an $`𝒳`$-row during this process. Thus if $`ji<k`$ then $`u_iv_j+2`$. Hence

$`R_{u_k}R_{u_{k1}}\mathrm{}R_{u_{j+1}}R_{u_j}`$ $`=`$ $`R_{v_j}R_{u_{k1}}\mathrm{}R_{u_{j+1}}R_{u_j}`$
$`=`$ $`R_{u_{k1}}\mathrm{}R_{u_{j+1}}R_{u_j}R_{v_j}.`$
By using this substitution in the definition of $`\mathrm{\Phi }^{}`$, we increase the value of $`j`$. Repeating this process eventually gives $`\mathrm{\Phi }^{}=\mathrm{\Phi }`$. $`\mathrm{}`$

We can define a notion of oriented alternating sign matrix by assigning each $`1`$ in a given alternating sign matrix an orientation (left or right). This is an equivalent notation to oriented complete monotone triangle. There is a natural correspondence between oriented alternating sign matrices of order $`n`$ and domino tilings of the Aztec diamond of order $`n1`$ (see ). We have thus given an implicit bijection between tournaments on vertex set $`\{1,2,\mathrm{},n\}`$ and domino tilings of the Aztec diamond of order $`n1`$. In particular we recover the result that there are $`2^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}`$ such tilings.

We can apply the argument in the proof of Theorem 1 to more general triangles. Instead of having the last row $`1,2,\mathrm{},n`$ choose any set $`S`$ of $`n`$ positive integers and consider the oriented monotone triangles $`𝒪_S`$ with bottom row consisting of the elements of $`S`$ in ascending order. We wish to describe the set $`\mathrm{\Phi }(𝒪_S)`$. Let $`𝒯_S`$ be the set of admissible triangles with bottom row consisting of the elements of $`S`$, and with each entry above the bottom row being an $`a_{ij}`$ or a $`b_{ij}`$. The proof of Theorem 1 immediately adapts to show that $`\mathrm{\Phi }`$ and $`\mathrm{\Psi }`$ are inverse bijections between $`𝒪_S`$ and $`𝒯_S`$. It is immediate that $`|𝒯_S|=2^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}|𝒯_S^{}|`$ where $`𝒯_S^{}`$ is the subset of $`𝒯_S`$ consisting of triangles lacking entries $`b_{ij}`$. This is because each element of $`𝒯_S`$ is derived from a unique element of $`𝒯_S^{}`$ by replacing a subset of its $`a_{ij}`$ entries by the corresponding $`b_{ij}`$. Each triangle in $`𝒯_S^{}`$ is determined by the left values of the entries (recall that $`a_{ij}`$ has left value $`i`$). By replacing each $`a_{ij}`$ in such a triangle by $`i`$ we get a bijection between $`𝒯_S^{}`$ and the set of *strict monotone triangles* with bottom row $`S`$, that is the set of numerical triangles in which each arrangement

$$\begin{array}{ccc}& j& \\ i& & k\end{array}$$

satisfies $`ij<k`$. For instance there are 6 strict monotone triangles with bottom row $`S=\{1,2,4,5\}`$ namely

$$\begin{array}{ccccccc}& & & 1& & & \\ & & 1& & 2& & \\ & 1& & 2& & 4& \\ 1& & 2& & 4& & 5\end{array},\begin{array}{ccccccc}& & & 1& & & \\ & & 1& & 3& & \\ & 1& & 2& & 4& \\ 1& & 2& & 4& & 5\end{array},\begin{array}{ccccccc}& & & 2& & & \\ & & 1& & 3& & \\ & 1& & 2& & 4& \\ 1& & 2& & 4& & 5\end{array},$$

$$\begin{array}{ccccccc}& & & 1& & & \\ & & 1& & 3& & \\ & 1& & 3& & 4& \\ 1& & 2& & 4& & 5\end{array},\begin{array}{ccccccc}& & & 2& & & \\ & & 1& & 3& & \\ & 1& & 3& & 4& \\ 1& & 2& & 4& & 5\end{array},\begin{array}{ccccccc}& & & 2& & & \\ & & 2& & 3& & \\ & 1& & 3& & 4& \\ 1& & 2& & 4& & 5\end{array}.$$

By adapting the proof in \[4, §4\] one can show that if $`S=\{a_1,a_2,\mathrm{},a_n\}`$ with $`a_1<a_2<\mathrm{}<a_n`$ then

$$|𝒯_S^{}|=\underset{1i<jn}{}\frac{a_ja_i}{ji}$$

and so

$$|𝒯_S|=2^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}\underset{1i<jn}{}\frac{a_ja_i}{ji}.$$


format: text

text:
# Segregation transitions in wet granular matter

## Abstract

We report the effect of interstitial fluid on the extent of segregation by imaging the pile that results after bidisperse color-coded particles are poured into a silo. Segregation is sharply reduced and preferential clumping of small particles is observed when a small volume fraction of fluid $`V_f`$ is added. We find that viscous forces in addition to capillary forces have an important effect on the extent of segregation $`s`$ and the angle of repose $`\theta `$. We show that the sharp initial change and the subsequent saturation in $`s`$ and $`\theta `$ occurs over similar $`V_f`$. We also find that a transition back to segregation can occur when the particles are completely immersed in a fluid at low viscosities.

The flow of granular matter shows a number of fascinating properties including segregation. Segregation in granular matter can be a benefit or a nuisance depending on the application. Remarkable sensitivity to small differences in the size, shape and density of the constituent grains has been observed . However, most of this work relates to noncohesive granular matter. Although decrease of percolation in granular matter immersed in a fluid has been noted , systematic studies are required. Furthermore, quantitative experiments on segregation have not been reported in the situation where a small amount of fluid or humidity is present.

Presence of small amounts of interstitial fluid in the system introduces another degree of complexity due to the cohesive forces between particles in addition to the core repulsion force and the friction force present for dry granular matter. Increase in the angle of repose is the most well known effect of presence of interstitial fluid in a granular system and has been a topic of current interest . The interstitial fluid also alters the percolation of particles, and the particles tend to behave as clumps rather than individual grains.

The first quantitative study of the segregation of bidisperse granular matter in the presence of interstitial fluid is reported. The extent of segregation is parameterized by visualizing color-coded particles of different sizes that are poured into a quasi-two dimensional silo. A sharp reduction of segregation is observed when a small volume fraction of fluid $`V_f`$ is added which introduces capillary bridges between particles. Preferential clumping of small particles is observed to cause layering at small $`V_f`$. We obtain the segregation phase diagram as a function of size ratio $`r`$ of the bidisperse particles and $`V_f`$. We show the importance of the viscous force in addition to the capillary force on both the extent of segregation and the angle of repose $`\theta `$ by changing the viscosity $`\nu `$ of the fluid. We find that the sharp change in the extent of segregation and $`\theta `$ occurs over similar $`V_f`$. The development of segregation is also measured when the particles are completely immersed in the fluid. The extent of segregation decreases with viscosity $`\nu `$ of the fluid and disappears for large enough $`\nu `$. This decrease is also observed to depend on $`r`$.

A rectangular silo of dimensions $`50.0\mathrm{cm}\times 30.5\mathrm{cm}`$ and a width $`w`$ of $`3.0\mathrm{cm}`$ is used for the experiments. The flow is visualized through the glass side-walls of the silo using a megapixel Kodak ES 1.0 digital camera. The glass beads and fluids used are listed in Table I. The granular sample is prepared in batches by throughly mixing 1.0 kilograms each of the two kinds of beads with a volume fraction $`V_f`$ of the fluid before the granular material is placed inside the reservoir. The volume fraction $`V_f`$ corresponds to the ratio of the volume of the fluid to the volume of all the particles. The material is first filled into a reservoir and then drained through a pipe into the silo. A tall cylindrical reservoir is used to minimize segregation from occuring during pouring . Pipes with different diameters are used to control the flow rate $`Q`$. Wider diameters are used at higher $`V_f`$ in order to maintain $`Q2.2`$ g/s. The reservoir is raised at a slow constant rate with a stepper motor and a system of pulleys. The slow upward velocity of the reservoir allows the particles to accumulate inside the pipe before flowing down the surface and reduces the kinetic energy of particles due to free fall. Thus the interaction of particles is restricted to that of a moving surface layer with the static bulk. The flow is confined to a thin surface layer and is continuous at $`V_f=0`$ but becomes slip-stick as $`V_f`$ is increased.

To minimize the effect of evaporation, the experiments are conducted within a few minutes after the sample is mixed. Measurement with glycerol and polybutene does not show systematic effects of evaporation by delaying the time between mixing and pouring from 3 to 30 minutes. The data for water at low $`V_f`$ ( $`<2\times 10^3`$), shows some effects of evaporation for long delay times.

Fig. 1(a) represents the segregation displayed by bidisperse dry granular matter flowing down an inclined plane. The segregation mechanism in the dry case is well known and can be explained using (i) the void filling mechanism where smaller particles percolate through the larger particles and are thus found at the bottom of the flow , and (ii) the capture mechanism where the smaller particles which are more sensitive to surface fluctuations are stopped at the top of the pile before the larger particles . The segregation is observed to vanish by adding a small amount of fluid which corresponds to less than 1% of the volume (see Fig. 1(d)). Fig. 1(b),(c) show the intermediate situation where partial segregation is observed. Some layering also occurs although it is not as periodic as in mixtures of particles with dry rough and smooth particles .

To parameterize the extent of segregation, histograms of the ratios of the two types of particles in a $`3.5\mathrm{mm}^2`$ area are made using the light intensity. The light intensity is a monotonic function of the density ratio of the particles and is determined by using known weight ratios of particles in a separate series of calibration experiments. The histogram of local particle density ratio $`P_w`$ of the two kinds of particles in the pile is thus obtained and is plotted in Fig. 1(e)-(h). The peaks in the distribution can be fitted to Gaussians and the mean value used to determine the most common particle ratios $`a`$ and $`b`$. The segregation parameter is defined as $`s=\frac{(ba)}{100}`$ which has a value between 0 and 1 and describes the extent of segregation.

The phase diagram of segregation as a function of $`r`$ and $`V_f`$ is plotted in Fig. 2 for water and glycerol. The $`s=0`$ contour line is observed to close up at much lower $`V_f`$ for glycerol which is almost a thousand times more viscous than water but has similar surface tension $`\mathrm{\Gamma }`$. The phase diagram not only demonstrates the importance of $`r`$ and $`V_f`$ on determining the extent of segregation but also $`\nu `$. The phase diagram also shows that segregation can persist even in the presence of cohesive forces for large $`r`$.

The $`s`$ for $`r=6.2`$ is plotted in Fig. 3(a) as a function of $`V_f`$ for three fluids with different $`\nu `$ and $`\mathrm{\Gamma }`$. The corresponding change in angle of repose $`\theta `$ as a function of $`V_f`$ is plotted in Fig. 3(b) and indicates the increased cohesiveness of the material. The angle of repose increases linearly at low $`V_f`$ and saturates at high $`V_f`$ thus sharing qualitative features with the data reported in Refs.. In Refs. , the maximum angle of stability or repose was measured and estimated by tilting a silo filled with grains. In Ref. , the $`\theta `$ was measured using a draining crater method. However, quantitative agreement is not observed and may not be surprising because of the differences in the definition of the angle of repose in all the studies. Indeed, the published results are not in mutual agreement. In addition, it can be noted from Fig. 3 that $`\theta `$ increases rapidly as the $`\nu `$ of the fluid is increased. To show the dependence on $`\nu `$ more explicitly, the $`\theta `$ for monodisperse particles, BD-2, and BD-3 are plotted at fixed $`V_f`$ in the inset to Fig. 3(b). The $`\nu `$ is varied by mixing water and glycerol which have similar $`\mathrm{\Gamma }`$ . $`\theta `$ is observed to increase for all cases. It can be also noted from this plot that the $`\theta `$ depends on the size ratio $`r`$ of the grains and saturates at a different value for bi-mixtures than for one of its components. This dependence will be reported in greater detail in a future publication .

It can be noted from Fig. 3 that $`s`$ and $`\theta `$ change rapidly over similar $`V_f`$. The $`V_f`$ at which the $`s`$ and the $`\theta `$ begins to saturate is denoted by $`V_c`$ (dashed lines in Fig. 3.) Although the increase of cohesivity between the grains due to the presence of interstitial fluid is well known, the fact that $`s`$ and $`\theta `$ show similar dependence on $`V_f`$ is remarkable. This is also the case not only for water and glycerol but also for polybutene L-50 which has a different combination of $`\mathrm{\Gamma }`$ and $`\nu `$. We find that $`s`$ and $`\theta `$ at other $`r`$ also show a $`V_c`$ which is lower for smaller $`r`$ and higher for larger $`r`$ and can be inferred from Fig. 2.

Although there is a lack of theoretical and experimental consensus on the nature of the force at low $`V_f`$, the saturation force due to the surface tension at large $`V_f`$ is well known  and equals $`\pi \mathrm{\Gamma }d`$ where $`d`$ is the diameter of the particle. For the particles ($`d0.5`$ mm) used in the experiments, and with glycerol or water as interstitial fluid, this force corresponds to $`10^4`$ N. However, Figs. 2 and 3 indicate that $`\nu `$ has an effect on the segregation of granular material and on $`\theta `$ as well.

To see how the viscous force is relevant, one considers a particular case of two particles in contact with a small amount of fluid in between. The importance of such a force has been discussed in the context of lubrication and friction . If $`h`$ is the thickness of the fluid between the particles, and $`R`$ is the radius of the circular contact, then the viscous force is approximately given by $`\frac{3\pi }{2h^3}\nu R^4\frac{h}{t}`$ for $`hR`$ . The curvature of the beads near the contact point is neglected. This formula states that the force directly depends on the rate of separation of the two particles $`\frac{h}{t}`$ and the viscosity of the fluid.

If $`\frac{h}{t}`$ is assumed to be of the same order as the average flow velocity of the particles down the surface then $`\frac{h}{t}`$ 1 mm/s, and for $`h10\mu `$m and $`R100\mu `$m, the viscous force between particles can be estimated to be $`5\times 10^4`$ N, about 5 times larger than the saturation capillary forces for glycerol. On the other hand for water which has lower $`\nu `$, the viscous force will be at least 100 times smaller and therefore irrelevant. As one increases $`V_f`$, the formula for the simple situation considered will need to be modified especially to take into account the shearing motion as well as the separation.

The viscous force damps velocity fluctuations as it increases with relative velocity between particles. Since velocity fluctuations and percolation among particles is required for segregation, $`s`$ is therefore observed to be lower at higher $`\nu `$ for similar $`\mathrm{\Gamma }`$.

In addition to the overall cohesiveness of the granular matter introduced by the fluid, an interesting effect observed below $`V_c`$ is the selective coating and clumping of smaller particles (see inset to Fig. 3(a)). A clump of small particles effectively behaves as a particle with a rough surface which can be larger than the individual large particle. Makse et al. have shown that stratification can occur when two species with different surface roughness are present in granular flows when the size of the rough particles exceeds the smoother particles . The features observed in Fig. 1(c) appear to be related to this mechanism, although the increased stick-slip nature of the flow at the surface brought about by the addition of the fluid makes the layering aperiodic. The strongest layering is observed for BD-2 (see Table I) and decreases at higher $`r`$ where the clumps of small particles stay smaller than the larger bead. The average size of clumps increases at higher $`V_f`$ and the interaction between small and large particles also becomes important. Thus clumps with small and large particles are formed resulting in smaller $`s`$.

Finally the progress of segregation in the limit where particles are completely immersed in fluids was measured. In this case liquid bridges and capillary forces are absent but viscous forces are present. The experimental procedure and system is similar to that described for experiments with partial fluid fraction but with one major difference. The fluid with various $`\nu `$ is first filled into the silo, and then the mixture of dry bidisperse mixture is poured into the silo. Since the terminal velocity for particles decreases with $`\nu `$, the particles take a significantly longer time to drain in a viscous fluid compared to that in air and $`Q<0.02`$g/s in glycerol. The $`s`$ is extracted after analyzing the images of the piles as discussed before and is plotted in Fig. 4 as a function of $`\nu `$ for three different $`r`$. The segregation is observed to decrease as a function of $`\nu `$ and drops to zero at high $`\nu `$ which depends on $`r`$. In contrast to the case of partial fluid fraction, the angle of repose $`\theta `$ of the pile is not observed to change significantly with $`\nu `$.

The boundary layer which develops in the fluid for particles falling with velocity $`v`$ is proportional to $`\sqrt{\nu d/\rho v}`$ from dimensional arguments  and washes away the details of the surface roughness of the pile at higher $`\nu `$. Thus the capture mechanism which is sensitive to surface roughness decreases in importance with $`\nu `$. In addition, velocity fluctuations are damped out at higher $`\nu `$ as particles reach terminal velocity over a short distance leading to a reduction in percolation of particles . Thus, the segregation decreases because the two mechanisms which cause segregation in dry granular matter diminish. Although the terminal velocity reached by a spherical particle is proportional to $`\sqrt{d}`$, this does not appear to aid segregation under the given conditions.

In summary, a sharp reduction of segregation is observed in granular flow when a small volume fraction of fluid is added. A transition back to segregation is observed when the volume fraction is increased so that particles are completely immersed in the fluid depending on the viscosity of the fluid. The role of the size ratio of the particles, volume fraction, surface tension and viscosity on the extent of segregation is clarified based on experiments and physical arguments. The results reported also offer a guide in the interpretation of models of segregation developed for dry granular matter and geophysical phenomena where the presence of interstitial fluid is a fact. An interesting question which remains to be resolved is whether the segregation phase transitions change qualitatively when the size of the system is increased arbitrarily and will be addressed in future work.

This work was supported by the National Science Foundation under grant number DMR-9983659 and by the donors of the Petroleum Research Fund. A.K. also thanks the Alfred P. Sloan Foundation for its support.


text:
# Branched Polymers and Percolation

## Abstract

We study a supposed model for branched polymers which was shown in two dimensions to be in the universality class of ordinary percolation. We confirm this by high statistics simulations and show that it is in the percolation universality class also for three dimensions, in contrast to previous claims. These previous studies seem to have been mislead by huge corrections to scaling in this model.

PACS numbers: 05.70.Jk, 64.60.A, 36.20-r

Although most statistical physicists have an intuitive notion of the concept of universality at second order phase transitions, a rigorous method to delineate universality classes does not yet exist. As a consequence, again and again the problem arises whether two specific models are in the same universality class or not. If critical exponents can be obtained exactly (either by conformal invariance in $`d=2`$, or by an $`ϵ`$-expansion near the upper critical dimension), then one can at least say when they are not in the same class: if the exponents do not coincide. But in general one has to resort to numerical methods, such as series expansions or Monte Carlo simulations. Since both require extrapolations in order to obtain critical exponents, it is not surprising that wrong claims about universality classes appear again and again.

Several years ago, a model was introduced in  (called LATST in the following) which was supposed to describe the growth of branched polymers in a disordered medium. Branched polymers in thermal configurational equilibrium are in the universality class of lattice animals . This is an ensemble of connected clusters of sites on a regular lattice where all configurations with the same number of sites have the same weight.

The LATST model is different. It is defined kinetically. It lives on a randomly diluted hypercubic lattice, such that monomers can be placed only on a fraction $`p`$ of lattice sites. Starting with a monomer as an active point seed, at each time step the oldest active site is chosen and its free neighbours (usable but not yet used) are counted. If there is no free neighbour, the site becomes inactive and the next active site in the list is chosen. Otherwise, one of the free neighbours (chosen randomly) is declared a new active site. In addition, if there is another free neighbour, a second site is made active with probability $`b`$. This is called ‘branching’. After this is done, the old active site is also made inactive and the next active site is chosen from the list. When $`p`$ is smaller than a critical value $`p_c`$, then the process dies with probability 1 for all values of $`b`$. For $`p>p_c`$, there exist a critical value $`b_c=b_c(p_c)`$ such that it has a non-zero chance to survive for $`b>b_c(p_c)`$.

Obviously this is very similar to the growth of an epidemic in the general epidemic process (“dynamical percolation”) . In the latter, the main difference is that all neighbours of an active site have the same chance $`p`$ to be activated, independent of how many other can be or are activated. Thus, if a site has $`m`$ neighbours not yet occupied, the number of its “descendants” is a Poissonian random number with average $`pm`$. In contrast, in the LATST model the variance of the number of activated descendants is reduced. It is always either 0, 1, or 2, but never $`>2`$. This difference is most pronounced for $`p=1`$ and for lattices with high coordination number, because then $`b_c`$ is very small (see below) and most of the time there is just a single descendent. But we should not expect this to be relevant in the renormalization group sense, i.e. we should expect that the LATST model is in the universality class of the general epidemic process and hence of ordinary percolation. In some sense, LATST and general epidemic process are related to each other like ‘growing self avoiding walk’ (GSAW)  and usual self avoiding walk (SAW) which are also known to be in one common universality class.

The transition in the 2-dimensional LATST model was indeed found to be in the percolation universality class in . For $`d=3`$, the same was verified in  for values of $`p`$ close to $`p_c`$, but not for $`p=1`$. In  it was claimed that the latter shows clean scaling which is definitely not in the percolation universality class. We claim here that this is wrong. With present day computers it is practically impossible to obtain the scaling regime for the case $`d=3,p=1`$, but all numerical evidence hints to the fact that the model is in the percolation universality class.

In order to see the origin of the problem, we notice that the LATST model is for $`p=1`$ and $`b=0`$ just the GSAW. As already pointed out, this is in the SAW universality class. But it has greatly reduced attrition since monomers are placed only on free neighbours in the GSAW, while they are placed at randomly chosen neighbours (whether they are free or not) in SAWs. As a consequence, the attrition constant (the rate with which the process dies) is 0.024 in $`d=2`$ and 0.000275 in $`d=3`$. Thus, in order to overcome attrition, it would be sufficient to make an enrichment step  every 40 time steps in $`d=2`$, and every 3600 time steps in $`d=3`$. These give lower estimates $`b_c(p=1)0.024(d=2)`$ and $`b_c(p=1)0.000275(d=3)`$. Indeed, the actual estimates for $`b_c`$ are rather close to these: $`b_c(p=1)=0.056`$  for $`d=2`$ and $`b_c(p=1)=0.00034`$  for $`d=3`$. Since $`1/b`$ sets a time scale (the average time between two branchings), this shows that there are large inherent times $`T20`$ resp. $`T3000`$ in the LATST model. Any critical scaling is expected to show up only for $`tT`$. While such $`t`$ are still feasible in high-statistics simulations in 2d, they are out of reach in 3d.

To verify these predictions, we performed simulations. We studied only the most difficult and controversial case $`p=1`$, for $`p<1`$ it seems accepted that the LATST model is in the percolation class. In order to reach large clusters without finite lattice effects we used hashing. This allowed us to use virtual lattices of sizes up to $`100,000^3`$, so we could study clusters of up to $`10^6`$ sites without any finite lattice corrections. Such corrections were obviously important in the figures shown in , but it is hard to judge from these figures what parts of the distributions are uneffected by them.

We used the fast and reliable 4-tap random number generator of . Each curve in the following figures is based on a sample with at least $`3\times 10^5`$ clusters. Although this statistics is higher than previous ones  by several orders of magnitude, the entire project needed only about 200h CPU time on fast work stations.

Mass distributions of 2-d clusters for 5 values of $`b`$ are shown in Fig.1. Actually, in order to take into account the very small error bars, we plotted not $`P(M)`$ itself but $`M^{\tau 2}P(M)`$ where $`P(M)`$ is the probability that a cluster has mass $`M`$, and $`\tau =96/91`$. This is motivated by the fact that $`P(M)M^{2\tau }`$ for 2-d percolation. Thus we expect our data to be flat for $`b=b_c`$, except for corrections to scaling. This is indeed the case for $`M>10^4`$ and $`b_c=0.05680\pm 0.00004`$. The average square size $`R^2`$ obtained from the sdame runs is shown in Fig.2. Again the asymptotic behaviour $`R^2M^{96/91}`$ expected for percolation is divided out, and again we see flat curves for $`M>10^4`$. Our estimate for $`b_c`$ is in rough agreement with that in  but about ten times more precise (assuming that the error quoted on page 1744 of  is misprinted; otherwise it would be a factor 100 more precise).

For $`d=3`$, $`M^{\tau 2}P(M)`$ versus $`M`$ is plotted in Fig.3. For $`\tau 2`$ we used the value $`0.189`$ from . We see clearly different behaviour for $`M<3000`$ and for $`M>3000`$. For $`M<3000`$ we have the expected scaling of simple random walks. For $`M3000`$ we expect to see percolation, but this sets in only very late. Roughly straight lines in the range $`3000<10^5`$ are seen for $`b0.00034`$. Obviously, the estimate $`b_c=0.000334`$ of  was based on this range, although all log-log plots of  show straight lines in the entire range $`M>10^2`$ for reasons which we do not understand. Anyhow, these straight lines do not represent the asymptotic behaviour, since all our curves except those for $`b0.00036`$ bend down for very large $`M`$ (notice that each curve is based on independent runs, thus all systematic structures seen in any of our plots are significant). Indeed we estimate that the curve for $`b=0.00036`$ in Fig.3 will also bend down for $`M>10^6`$, and the estimated critical value is $`b_c=0.000366\pm 0.000004`$.

Average values of the “chemical radius” (the length of the paths connecting active sites to the seed) and of the number of active sites are shown in Figs. 4 and 5. Here we plotted the raw data themselves. We again see the break in scaling at $`M3000`$. A careful look at the data (e.g. plotting them again with some power split off) shows that the curves are not straight for $`M3000`$ but show similar curvature as $`P(M)`$. Thus also in these cases it is impossible to extract critical exponents from the data. In contrast to this, the authors of  found perfect scaling without visible corrections (and with exponents different from those for percolation) for all cluster masses $`>10^2`$ and chemical radii $`>10`$. We have no explanation for this.

In summary we showed that it is extremely dangerous to estimate critical exponents from data which have important corrections to scaling. In the present case these corrections seem to have lead to wrong claims about universality, but it is not clear why the authors of  have missed them. In any case we see no reason to doubt that the LATST model is in the universality class of percolation, for any finite dimension $`d`$. Numerical verification for $`d4`$ is of course out of question.

Let us finally end with two comments. The first is that the subcritical process is not, as claimed in , in the universality class of SAWs. It is in the lattice animals universality class, like any model whose critical point is in the percolation class . Secondly, it is not clear in what sense the LATST model is a valid model for branched polymers (BP). It certainly does not describe the ensemble of fully annealed BP, except in the sense just mentioned (lattice animals are in the same universality class as BP). It cannot describe either the ensemble of BP in which branch points are frozen but bends between successive monomers are annealed (i.e., BP with fixed topology), since this topology is determined in the LATST model by local configurations. It is for that reason that we avoided the name ‘branched polymer growth model’ (BPGM) proposed in .


text:
# Hot dust in two hard Chandra X-ray sources

## 1 INTRODUCTION

The Chandra X-ray observatory has recently resolved the bulk of the 2–7 keV hard X-ray background (HXB) into point sources (Mushotzky et al. 2000; Brandt et al. 2000). Much effort is now focused on determining the physical nature of these new sources and their relation to existing classes of active galactic nuclei (AGN). Mushotzky et al. (2000) found that roughly a third of their sources were blue broad-line (type I) AGN, one third were identified with apparently normal galaxies, whilst the final third had an extremely faint or no optical counterpart ($`I23`$mag) (see also Fiore et al. 2000). Crawford et al. (2000) confirmed that sources in the last group are easily detected in the near-infrared, with featureless spectra suggesting that the AGN is heavily obscured and colours consistent with reddened elliptical galaxies at $`z=12`$. Further insight has come from cross-correlating Chandra source lists with those from 850µm SCUBA observations of the same fields: for the lensing clusters A2390 and A1835, Fabian et al. (2000) (hereafter F00) found only one source common to both datasets, implying that any AGN in the SCUBA sources must either contribute little to the sub-mm power or be Compton-thick with X-ray scattering fractions below 1 per cent; this result was confirmed by Hornschemeier et al. (2000), who detected none of the 10 sub-mm sources in and around the Hubble Deep Field North (HDFN) in a 166-ks Chandra exposure.

The two brightest X-ray sources in the A2390 field, CXOUJ215334.0+174240 and CXOUJ215333.2+174209 (hereafter sources A and B respectively), have ISOCAM counterparts at 6.7 and 15µm in the literature (Altieri et al. 1999; Lémonon et al. 1998). Together with their non-detection at 850µm by SCUBA, this has implications for the location and properties of the dust which may be associated with the X-ray obscuration. In this paper we use the dust radiative transfer code DUSTY (Ivezić, Nenkova & Elitzur 1999) to model the infrared spectral energy distributions (SEDs) of these two sources as reprocessed optical–UV emission from an AGN. The faint optical light from these sources ($`V25`$) is assumed to be from the host galaxy and the HYPERZ code (Bolzonella, Pelló & Miralles 2000) is used to estimate photometric redshifts.

## 2 SED modelling

For the primary optical–UV AGN continuum input to the DUSTY models, we follow Granato, Danese & Franceschini (1996) and use a broken power-law with $`\alpha =0.5`$ for $`\mathrm{log}\nu <15.4`$, $`\alpha =1.0`$ for $`15.4\mathrm{log}\nu <16`$, and $`\alpha =2.2`$ for $`\mathrm{log}\nu 16`$ ($`L_\nu \nu ^\alpha `$). The central source is surrounded by a spherical dust cloud, specified by its optical depth $`\tau `$ at 0.3µm ($`A_\mathrm{V}0.57\tau `$, and for a Galactic dust:gas ratio $`N_\mathrm{H}1.1\times 10^{21}\tau `$$`\mathrm{cm}^2`$), the ratio $`R=r_{\mathrm{out}}/r_{\mathrm{in}}`$ of the radii of the outer and inner edges of the distribution (between which we take the density to be constant), and the dust temperature $`T_{\mathrm{in}}`$ at $`r_{\mathrm{in}}`$. The code currently only supports grains of a single type, so we adopt the default ‘standard ISM mixture’ comprising grains which mimic a 53:47 mixture of silicate and graphite grains from Draine & Lee (1984). The DUSTY wavelength grid spans 0.01µm–$`3.6\times 10^4`$µm, so the effects of harder radiation are not modelled. Since sources A and B are likely to be Compton-thin with $`N_\mathrm{H}10^{22}10^{23}`$$`\mathrm{cm}^2`$ (as inferred from the hardness ratios in F00 and from AGN synthesis models for the XRB, e.g. Wilman & Fabian 1999), they are transparent to photons above a few keV; there are thus about 1.5 decades of frequency below 0.01µm where photons would be absorbed but which are not included. Given that the input SED cuts off sharply below 0.03 µm, this omission is unimportant.

We adopt the cosmological parameters $`H_0=50`$$`\mathrm{km}\mathrm{s}^1\mathrm{Mpc}^1`$ and $`q_0=0.5`$ throughout the paper.

### 2.1 Source B (CXOUJ215333.2+174209)

Lémonon et al. (1998) give 6.7 and 15µm ISOCAM fluxes for source B of $`110_{60}^{+40}`$ and $`350_{40}^{+50}`$$`\mu `$Jy, respectively. From a total of 33 counts, F00 estimate 0.5–2 and 2–7 keV fluxes of 5.9 and 23$`\times 10^{15}`$$`\mathrm{erg}\mathrm{cm}^2\mathrm{s}^1`$, respectively; the upper limit at 850µm is 5.7 mJy (F00). We use the relative fluxes in the B, V(F555W), R, I(F814W), J and K filters provided by Lémonon et al. along with HYPERZ to compute a photometric redshift (N.B. the HST F555W and F814W magnitudes given by Lémonon et al. differ from those listed in F00, but for internal consistency we adopt the former values). We consider 2 families of HYPERZ models: (i) where at least 80 per cent of the K light (2.103µm) is host galaxy starlight; (ii) where at least 50 per cent of it is nuclear dust emission. A satisfactory HYPERZ model could not be found for the case where all the K light is from the nucleus. HYPERZ uses Bruzual & Charlot (1993) spectral synthesis models and varies the redshift, age and extinction of the population. The elliptical galaxy model we use has an exponentially-declining star formation rate with an e-folding time of 1 Gyr; other models with longer star-formation timescales (S0–Sd and Im), as well as bursts, were also considered, but they do not significantly change the fitted redshift (essentially because the break between the V(F555W) and R points is assumed to be the redshifted 4000Å break).

For case (i), HYPERZ fits a 500 Myr old elliptical galaxy with $`A_\mathrm{V}=2.40`$ mag at $`z=0.575`$. For this redshift, we generated a grid of DUSTY models, with $`\tau =10`$, 20,..,100 (equivalent to $`N_\mathrm{H}10^{22}10^{23}`$$`\mathrm{cm}^2`$ for a Galactic dust:gas ratio, and appropriate for the moderately Compton-thin obscuration implied by the X-ray fluxes), $`T_{\mathrm{in}}=100`$, 200,..,1500 K, and $`R=5`$, 50, 250 and 1000. After integration over the ISOCAM filter bandpasses, the models were normalised to the observed 15µm flux density, and deemed acceptable if the 6.7/15 µm flux ratio fell within the range allowed by the errors on the ISOCAM data, if the 850µm flux fell below the SCUBA limit, and if the K flux was less than 20 per cent of that observed. Fig. 1 shows which models meet these criteria, and Fig. 2 the SED fits for three such cases, with $`(R,\tau ,T_{\mathrm{in}})=`$(250,50,1500), (50,100,700) and (5,60,200). The implied optical-UV DUSTY input luminosity, 2–10 keV X-ray absorption corrected luminosity (derived from the observed 2–7 keV flux, assuming an intrinsic power-law spectrum with a photon index $`\mathrm{\Gamma }=2`$), optical (2500Å) to X-ray (2 keV) spectral index, $`\alpha _{\mathrm{ox}}`$, and the inner radius, $`r_{\mathrm{in}}`$, for each are shown in Table 1. The best fits to the portion of the SED covered by the ISOCAM data are obtained with hot dust (heated close to its sublimation temperature of 1500 K), with an inner radius within a parsec of the central engine; the implied $`\alpha _{\mathrm{ox}}`$ in this case is, however, somewhat flatter than the canonical value of 1.35 for quasars (Elvis et al. 1994). Figs. 1 and 2 also show, however, that models with warm dust at $`T_{\mathrm{in}}=200`$ K cannot be ruled out at present; such models have inner radii of tens of pc and $`\alpha _{\mathrm{ox}}`$ values close to those of quasars. Discrimination between the warm and hot dust models would be possible using data at 70µm; e.g. the 200 K model shown in Fig. 2 has a 70µm flux density of 16 mJy, which is well within the capability of SIRTF (see e.g. Brandl et al. 2000).

For case (ii), HYPERZ fits a 3.5 Gyr old elliptical galaxy at z=0.505 with $`A_\mathrm{V}=0.60`$ mag. The need for DUSTY to reproduce at least half of the K light in this case means that the dust must be hot ($`T_{\mathrm{in}}=10001500`$ K) and not too optically thick at 2µm ($`\tau 2540`$); $`R`$ is not very well constrained, with a value of 100 for $`\tau =35`$, although a more compact structure, $`(R,\tau )=(5,40)`$, is also acceptable. For $`(R,\tau )=(100,35)`$, we find $`L_{210}=4.6\times 10^{43}`$$`\mathrm{erg}\mathrm{s}^1`$ and $`\alpha _{\mathrm{ox}}=1.12`$; the latter model SED is shown in Fig. 2.

We conclude that the best-fitting models are those in which the dust is hot, with an inner radius within $`1`$ pc of the nucleus. Several models with warm dust (200 K) are also formally acceptable, but for $`R=50`$ some of these underpredict the SCUBA upper limit by only a small factor ($`2`$), which, if this source is representative of the new Chandra HXB sources, seems unlikely given the non-detection of large samples of them by SCUBA (see references in section 1).

### 2.2 Source A (CXOUJ215334.0+174240)

This is the brightest Chandra source in the A2390 field, coincident with a slightly reddened $`L^{}`$ mid-type spiral at a photometric redshift of $`z=0.85\pm 0.15`$ (F00). From a total of $`90`$ counts, F00 performed crude X-ray spectral fitting and deduced an intrinsic $`N_\mathrm{H}=(6\pm 2)(9\pm 3)\times 10^{22}`$$`\mathrm{cm}^2`$, with a de-absorbed $`L_{210}23\times 10^{44}`$$`\mathrm{erg}\mathrm{s}^1`$ (after correction for a lensing magnification by a factor of about 2), for $`z=0.71`$, respectively. It is thus an X-ray type II quasar.

It also has ISOCAM counterparts at 6.7 and 15µm (Altieri et al. 1999) but the source fluxes have not been published. We proceed on the assumption that they are equal to those of source B, which appears reasonable from the images in Altieri et al.

For redshifts in the range 0.7–1.0, we find acceptable DUSTY models with $`\tau =5580`$ (equivalent to the fitted $`N_\mathrm{H}=69\times 10^{22}`$$`\mathrm{cm}^2`$ for a Galactic dust:gas ratio) for $`R=100`$ and $`T_{\mathrm{in}}=1500`$ K; they have $`r_{\mathrm{in}}=0.551.0`$ pc and $`\alpha _{\mathrm{ox}}1.0`$.

## 3 DISCUSSION

It is instructive to compare our results with the calculations of Granato, Danese & Franceschini (1997), who compared dust radiative transfer models with the infrared properties of Seyfert galaxies. They concluded that the moderately thick, extended tori of Granato & Danese (1994) (GD) (with $`5A_\mathrm{V}80`$ mag and outer radii of 10’s to 100’s of parsec), provided a better fit to the data than the thick, very compact models of Pier & Krolik (1992a) (PK) (with $`A_\mathrm{V}800`$ mag, all within a pc). They also found that the observed X-ray absorption to the nucleus was much higher than that implied by the $`A_\mathrm{V}`$ obtained by modelling the infrared SED (for a Galactic dust:gas ratio), suggesting that much of the X-ray absorbing gas lies within the dust sublimation radius.

In terms of its optical depth and radial extent, the obscuring dust in these two Compton-thin, absorbed, X-ray background sources more closely resembles the model of GD than that of PK. Indeed, Granato, Danese & Franceshini (1997) predicted a significiant correlation between the HXB sources and those appearing in ISO surveys at 10–20µm, precisely because the GD models are (at the most) only moderately optically thick over this wavelength range. An important difference, however, is that the GD tori have opening angles of 35–45 degrees, whereas the covering fraction of any torus-like structure in the HXB sources must be higher (e.g. Fabian & Iwawasa 1999 deduce that 85 per cent of the accretion power must be absorbed). Note also that the DUSTY calculations assumed a spherical dust geometry. It is thus appropriate to examine how such a high space covering obscuration could be maintained against the dissipative forces which would tend to yield a flattened structure: at the sub-parsec scale inner radii found for sources A and B, Pier & Krolik (1992b) have shown that the pressure of the nuclear radiation on the grains can make the torus geometrically thick, by both reducing the vertical component of gravity, and if the torus is sufficiently clumpy, driving random motions of its constituent clouds. Fabian et al. (1998) demonstrated that a space-covering obscuration could be maintained with energy input from a nuclear starburst within 100 pc, but the distinct lack of emission lines in many of the newly-discovered HXB sources appears to rule this out. More generally, the lack of AGN emission lines in such objects may be due to dust within the narrow line region clouds. Netzer & Laor (1993) showed that its presence could significantly suppress line emission, through absorption of the photoionizing continuum and destruction of line photons, and thereby account for the mismatch between the inferred covering factors of the broad and narrow line regions in classical AGN when dust is not considered (the broad line region lies just within the dust sublimation radius). Our findings suggest the presence of a high covering fraction of dusty gas in the new HXB sources.

Alternatively, the lack of emission lines and non-detections by SCUBA could be used to argue that the new HXB sources are not actually obscured AGN, but some other class of intrinsically hard source (e.g. ADAFs, as proposed for the HXB by Di Matteo & Allen 1999); the present quality of the X-ray spectra is not high enough to discriminate between these two possibilities. Our present findings, however, strongly support the obscured AGN hypothesis, by demonstrating that the energy which is inferred to be absorbed in the optical–UV–X-ray range is reradiated in the infrared. In consequence, the results of deep Chandra surveys of well-studied ISO fields (e.g. from the ELAIS consortium; Rowan-Robinson et al. 1999), are eagerly awaited. Indeed, as noted by F00, 5 of the 6 Chandra sources discovered by Hornschemeier et al. (2000) in the HDFN also have ISOCAM counterparts at 15µm listed by Aussel et al. (1999) (CXOHDFN 123648.1+621309 is the only source not detected).

## ACKNOWLEDGMENTS

We are grateful to Z. Ivezić, M. Nenkova and M. Elitzur for making DUSTY publically available, and likewise to M. Bolzonella, R. Pelló and J.-M. Miralles for HYPERZ. Carolin Crawford is thanked for helpful comments and assistance.

RJW thanks PPARC for support, and PG the Isaac Newton Trust and the Overseas Research Trust. ACF thanks the Royal Society for support.