text:
# Little Higgs Models: New Approaches to the Hierarchy Problem

## 1 Introduction

The experimental results of the past decade indicate that the chiral Lagrangian describing EWSB works to one loop accuracy and irrelevant operators (such as $`|D\omega |^4`$, where $`\omega `$ are the Goldstone bosons eaten by $`W^\pm `$ and $`Z^0`$) are suppressed by a scale $`\mathrm{\Lambda }1\text{ TeV}`$. This strongly indicates perturbative physics at $`1\text{ TeV}`$ and a physical Higgs boson $`H=(h^0+v)\omega `$. However, this linear sigma model is unstable to quantum corrections leading to the hierarchy problem, meaning that the Standard Model is in an incomplete description of physics parametrically above the weak scale. To date, only the MSSM provides a solution to the hierarchy problem and weakly coupled physics at 1 TeV.

In this note we review models where the Higgs is a pseudo-Goldstone boson, $`\mathrm{\Sigma }=e^{i\sigma /f}`$ , for early attempts see . Approximate global symmetries, $`\mathrm{\Sigma }L\mathrm{\Sigma }R^{}`$ keep the Higgs vev small relative to the cut-off, $`\mathrm{\Lambda }4\pi f`$. The global symmetries are broken by couplings, however, the structure of the symmetry breaking prevents large corrections to the Higgs vev. At 100 GeV the model is a two Higgs doublet model with a Higgs potential identical to the MSSM. There is a mini-desert up to 1-3 TeV where new particles emerge that cancel the quadratic divergences of the Standard Model. The novelty of this set of models is that particles of the same spin cancel the respective quadratic divergences. Above the TeV scale there is another mini-desert until the 10-30 TeV scale where the description of the model becomes strongly coupled and new physics emerges. However, the Standard Model is insensitive to this physics.

## 2 Little Higgs Models

Little Higgs models are gauged non-linear sigma model with Lagrangians that can be divided into four pieces:

$$=_{\text{Gauge}}+_{\text{nl}\sigma \text{m Kin}}+_{\text{Plaq}}+_{\text{Yuk}}$$
(1)
The first term is the standard kinetic term for gauge bosons. The second term is the nl$`\sigma `$m kinetic terms that give mass to some of the gauge bosons. There is the possibility of adding a scalar potential, often called the plaquette potential, that gives mass to some of the nl$`\sigma `$m fields. Finally there are the Yukawa couplings between the nl$`\sigma `$m fields and fermions. To study the low energy dynamics of the theory we want to integrate out all the states that are classically massive and have an effective Lagrangian in terms of the classically massless fields. Some nl$`\sigma `$m can be represented by theory spaces where points denote gauge groups, lines are nl$`\sigma `$m fields, and faces are plaquette potentials. This was studied in depth in . The classically massless scalars are the little Higgs and are associated with non-contractible loops in theory space. The little Higgs has a mass generated radiatively, but the size of the radiative corrections are parametrically smaller than the TeV scale.

In the limit of vanishing couplings the nl$`\sigma `$m fields become exact Goldstone bosons under the symmetry $`\mathrm{\Sigma }L\mathrm{\Sigma }R^{}`$. This leaves the little Higgs exactly massless, but also without non-derivative interactions. Coupling constants break these chiral symmetries and allow masses for the little Higgs to be generated radiatively. Little Higgs models always require at least two couplings to communicate sufficient chiral symmetry breaking to generate a mass radiatively, and therefore quadratic divergences first arise at two loop order. To ensure that there are no one loop quadratic divergences to the the little Higgs mass there are simple rules for theory space models . The first rule is that if all nl$`\sigma `$m fields are bi-fundamentals, then there are no one loop gauge quadratic divergences. If no plaquette contains any nl$`\sigma `$m field more than once, then there one loop quadratic divergences to the little Higgs mass from the scalar potential.

Having removed the one loop quadratic divergences, there are always finite contributions to the little Higgs mass. We can estimate the size of these finite contributions by studying the theory beneath the scale of the classically massive modes. In this low energy thoery there are a quadratic divergences and they are cut-off by the mass of the first heavy states and become finite corrections to the mass squared of the little Higgs. The mass of the heavy modes is roughly $`M_\text{H}gf`$. This means that the correction to the little Higgs mass from the low energy quadratic divergence is:

$`\delta m_{\text{LH}}^2{\displaystyle \frac{g^2}{16\pi ^2}}M_\text{H}^2={\displaystyle \frac{g^2}{16\pi ^2}}g^2f^2=\left({\displaystyle \frac{g^2}{16\pi ^2}}\right)^2\mathrm{\Lambda }^2.`$ (2)
This is the same size as the two loop quadratic divergence in the full theory. Thus, even if we remove higher order quadratic divergences, we can not push the cut-off higher than two loop factors above the EW scale, setting $`\mathrm{\Lambda }1030\text{ TeV.}`$ This still allows for a seperation of scales $`m_{\text{LH}}M_\text{H}\mathrm{\Lambda }.`$ Furthermore, this means that the states that stabilizes the electroweak scale is invisible to roughly $`1\text{ TeV.}`$

## 3 The Minimal Moose

The minimal theory space model111 see  for other classes of models that has the requisite properties for EWSB has two gauge group and four nl$`\sigma `$m fields and is illustrated in Fig. 1. The two gauge groups are taken to be $`SU(3)`$ and $`SU(2)\times U(1)`$ with the $`U(1)`$ embedded as the $`𝐓_\mathrm{𝟖}`$ generator of $`SU(3)`$. There are two plaquettes added:

$`_{\text{Plaq.}}`$ $`=`$ $`\lambda _1f^4\text{ Tr }X_1X_2^{}X_3X_4^{}+\text{ h.c.}`$ (3)
$`+\lambda _2f^4\text{ Tr }X_2X_3^{}X_4X_1^{}+\text{ h.c.}`$
This gauged nl$`\sigma `$m breaks the $`SU(3)\times [SU(2)\times U(1)]`$ gauge symmetry down to the diagonal $`[SU(2)\times U(1)]`$ that is identified as the electroweak gauge group. The plaquettes give mass to one linear combination of nl$`\sigma `$m fields and leave three massless. One is eaten by the massive $`SU(3)`$ gauge bosons while two are physical and massless and are the little Higgs of the theory.

Since all the link fields are bi-fundamentals under the two gauge groups and the plaquettes contain each link field only once, there are no one loop quadratic divergences to the little Higgs masses.

The scalar potential for little Higgs, $`\mathrm{\Sigma }_{1,2}`$, is of the form $`\text{ Tr }\mathrm{\Sigma }_1\mathrm{\Sigma }_2\mathrm{\Sigma }_1^{}\mathrm{\Sigma }_2^{}`$ or in terms of the linearized modes:

$$V(\sigma _1,\sigma _2)=\lambda _{\text{eff}}\text{ Tr }[\sigma _1,\sigma _2]^2+\mathrm{}$$
(4)
where $`\lambda _{\text{eff}}^1=\lambda _1^1+\lambda _2^1`$. Written in terms of the doublets, the potential is:

$`V(h_1,h_2)=\lambda _{\text{eff}}\left(|h_1|^2|h_2|^2\right)^2`$ (5)
This is identical to the Higgs potential inside the MSSM except that the coefficient is undetermined. Hence, the mass of the Higgs is undetermined, although we do expect $`\lambda _{\text{eff}}𝒪(1)`$, leading to a physical Higgs mass in the $`100300`$ GeV range.

The Standard Model fermions are charged under the $`SU(2)\times U(1)`$ gauge group. It is convenient to write the fermions as triplets under the global $`SU(3)`$, i.e. $`Q=(q,0)`$ and $`U^c=(0,0,u^c)`$. They are coupled to the little Higgs, $`\mathrm{\Sigma }=\mathrm{exp}(i(\sigma _1\pm \sigma _2))`$, through operators such as:

$`yfQ\mathrm{\Sigma }U^cyq(h_1\pm ih_2)u^c+\mathrm{}.`$ (6)
This operator induces a one loop quadratically divergent contribution to the little Higgs mass. For everything but the top quark, the quadratic divergence is negligeable. For the top quark, the one loop quadratic divergence must be dealt with. By adding an additional massive vector-like fermion, $`\chi `$ and $`\chi ^c`$, we can promote the quark doublet, $`q`$, to quark triplet under the global $`SU(3)`$, $`Q=(q,\chi )`$. By preserving the global symmetry of the coupling, we remove the one loop quadratic divergence to the top quark. The quadratically divergent part of the one loop Coleman-Weinberg effective potential is:

$$V_{\text{eff}}=\frac{y^2\mathrm{\Lambda }^2f^2}{16\pi ^2}\text{ Tr }P_R\mathrm{\Sigma }P_L\mathrm{\Sigma }^{}$$
(7)
where $`P_R=(0,0,1)`$ from the $`U^c`$ coupling and $`P_L=(1,1,0)`$ if without the vector-like fermion $`\chi `$ and becomes the identity matrix with with $`\chi `$. When $`P_L`$ is the identity matrix, we preserve the $`SU(3)`$ symmetry and the effective potential is independent of $`\mathrm{\Sigma }`$.

One loop log divergences from the top sector drives one linear combination of the Higgs to acquire a mass and the orthogonal combination are stabilized by one loop log divergences from the gauge and scalar sectors . This leads to phenomenologically acceptable EWSB driven radiatively much as in the MSSM. We refer the reader to  for more details.

## 4 Conclusions and Outlook

We have presented new models of EWSB that stabilize the weak scale to radiative corrections and have weakly coupled physics at 1 TeV. At the 100 GeV scale it is a 2HDM model with possibly additional scalar singlets and $`SU(2)`$ triplets. At 1 TeV there are additional vector bosons that cancel the SMs guage $`\mathrm{\Lambda }^2`$ divergences, additional scalars that cancel the Higgs quartic interaction $`\mathrm{\Lambda }^2`$ divergence and additional coloured fermions that cancel the top’s $`\mathrm{\Lambda }^2`$ divergence. This description is valid up to $`1030`$ TeV where the nl$`\sigma `$m becomes strongly coupled and new physics emerges.

There is a tremendous amount of physics that is still to be done: precision studies , experimental signature , exploring other little Higgs models , and UV completing the theory above $`1030`$ TeV.


format: text

text:
# On the Elliptic Genus of Generalised Kummer varieties

## 1. Introduction

The elliptic genus can be defined for every compact complex manifold as a function of a complex variable $`\tau `$ and a complex variable $`z`$. For a Calabi-Yau manifold (Calabi-Yau in the (very weak) sense that its first Chern class vanishes up to torsion) the elliptic genus turns out to be a weak Jacobi form of weight zero and index $`d/2`$, where $`d`$ is the dimension of the manifold. A proof of this fact can be found in , and also in .

The elliptic genus is a generalization of Hirzebruch’s $`\chi _y`$-genus. It was shown in  that in fact the elliptic genus of a Calabi-Yau generally encodes more information than the $`\chi _y`$-genus provided the dimension of the manifold is twelve or greater than thirteen.

Compact hyperkähler (see for example ) manifolds are in particular Calabi-Yau manifolds in the sense given above. There are two main series of examples of compact hyperkähler manifolds, the Hilbert schemes of points on surfaces and the generalised Kummer varieties (see ). The $`\chi _y`$-genera for these manifolds have been known for quite some time (see ) since they depend only on the Hodge numbers of these manifolds. One is naturally led to the question of generalising these results to elliptic genera.

Dijkgraaf, Moore, Verlinde and Verlinde showed in  that the elliptic genus of a symmetric product of a manifold can be expressed in terms of the elliptic genus of the manifold itself. They conjectured that their formula also holds for the Hilbert scheme of points on surfaces since these Hilbert schemes can be seen as resolutions of symmetric powers of surfaces. Very recently, Borisov and Libgober managed to prove that conjecture (see ) with methods of toric geometry.

In  we expressed the value of a genus on a generalised Kummer variety in terms of twisted versions of this genus evaluated on the Hilbert schemes of points on a surface $`X`$ with $`c_1(X)^20`$. In this work it is shown that the result of  on the elliptic genera of these Hilbert schemes can be used to calculate their twisted elliptic genera. We do this and are led to a formula for the elliptic genus of a generalised Kummer variety. By specialising our result we reproduce Göttsche’s and Soergel’s formula for the $`\chi _y`$-genus of the generalised Kummer varieties.

One last word on the notation: The symbol $`_{a|n}`$ stands for summing over the *positive* divisors of the integer $`n`$.

## 2. Complex genera

### 2.1. Some notes on complex genera and the elliptic genus

Let $`\mathrm{\Omega }:=\mathrm{\Omega }^\mathrm{U}`$ denote the (rational) complex cobordism ring. By a result of Milnor (), it is generated by the cobordism classes $`[X]`$ of all complex manifolds $`X`$, and two complex manifolds $`X`$ and $`Y`$ lie in the same cobordism class if and only if they have the same Chern numbers, i.e. the Chern numbers determine the cobordism class and vice versa. Recall that the sum in the ring is induced by the disjoint union of manifolds, and the product by the cartesian product of manifolds.

By a *complex genus $`\varphi `$ with values in a $``$-algebra $`R`$* we want to understand a $``$-algebra homomorphism $`\varphi :\mathrm{\Omega }R`$. Examples of complex genera can be constructed in the following way:

###### Example 1.

Let $``$ be the category of complex manifolds and $`𝔄`$ the category of abelian groups. Let $`R`$ be any $``$-algebra and $`\mathrm{\Phi }`$ a natural transformation from the functor $`𝔄,X\mathrm{K}^0(X)`$ to the functor $`𝔄,X(\mathrm{K}^0(X)R)^\times `$ that associates to each $`X`$ in the category of compact complex manifolds a group homomorphism $`\mathrm{\Phi }_X:\mathrm{K}^0(X)(\mathrm{K}^0(X)R)^\times `$. For every such natural transformation,

$$\varphi :X\chi (X,\mathrm{\Phi }_X(𝒯_X))$$
(1)
defines a complex genus.

###### Proof.

It follows directly from the naturality of $`\mathrm{\Phi }_X`$ that $`\varphi (X+Y)=\varphi (X)+\varphi (Y)`$. Obviously, $`\varphi (\mathrm{})=0`$, where “$`+`$” denotes the disjoint union of manifolds. Furthermore,

$`\varphi (X\times Y)=`$ $`\chi (X\times Y,\mathrm{\Phi }_{X\times Y}(𝒯_{X\times Y}))`$
$`=`$ $`\chi (X\times Y,\mathrm{\Phi }_{X\times Y}(𝒯_X𝒯_Y))`$
$`=`$ $`\chi (X\times Y,\mathrm{\Phi }_{X\times Y}(𝒯_X)\mathrm{\Phi }_{X\times Y}(𝒯_Y))`$
$`=`$ $`\chi (X\times Y,\mathrm{\Phi }_X(𝒯_X)\mathrm{\Phi }_Y(𝒯_Y))`$
$`=`$ $`\chi (X,\mathrm{\Phi }_X(𝒯_X))\chi (Y,\mathrm{\Phi }_Y(𝒯_Y))`$
$`=`$ $`\varphi (X)\varphi (Y)`$
and
$`\varphi (\mathrm{point})=`$ $`\chi (\mathrm{point},\mathrm{\Phi }_{\mathrm{point}}(0))=\chi (\mathrm{point},1)=1.`$
Finally, we have to show that $`\varphi `$ depends only on the characteristic numbers of $`X`$. By the Hirzebruch-Riemann-Roch formula, we have $`\varphi (X)=_X\mathrm{ch}(\mathrm{\Phi }_X(𝒯_X))\mathrm{td}(𝒯_X)`$, i.e. it suffices to show that $`\mathrm{ch}(\mathrm{\Phi }_X(E))`$ depends only on the Chern classes of $`E`$ for any bundle $`E`$ on $`X`$. This can be seen as follows: Obviously, $`E\mathrm{ch}(\mathrm{\Phi }_X(E))`$ is a natural transformation from the functor $`X\mathrm{K}^0(X)`$ to the functor $`X\mathrm{H}^0(X)R`$. By the universality property of the Chern classes it follows that $`\mathrm{ch}(\mathrm{\Phi }_X(E))`$ can be given as an universal polynomial (depending only on $`\mathrm{\Phi }_X`$) in the Chern classes of $`E`$ over $`R`$ (see for example ) ∎

The definition of the *elliptic genus* is an application to the concept outlined in the example. From now on let use write $`q:=e^{2\pi i\tau }`$ for $`\tau `$, and $`y^{\frac{1}{2}}:=e^{\pi iz}`$ for $`z`$, i.e. $`y=e^{2\pi iz}`$.

###### Definition 1.

For every complex manifold $`X`$ of dimension $`d`$, we define the following virtual bundle

$$_X(z,\tau ):=\mathrm{\Phi }_X(𝒯_X,z,\tau )\mathrm{K}^0(X)[[q]][y^{\pm \frac{1}{2}}]$$
(2)
on $`X`$, where
$$\begin{array}{cc}\hfill \mathrm{\Phi }_X(E,z,\tau )& =y^{d/2}\underset{n=1}{\overset{\mathrm{}}{}}\left(_{yq^{n1}}E^{}_{y^1q^n}E\mathrm{S}_{q^n}E^{}\mathrm{S}_{q^n}E\right)\hfill \\ & \mathrm{K}^0(X)[[q]][y^{\pm \frac{1}{2}}],\hfill \end{array}$$
(3)
for any bundle $`E`$ on $`X`$. Here, $`_t(E):=_{i=0}^{\mathrm{}}^i(E)t^i`$ and $`\mathrm{S}_t(E):=_{i=0}^{\mathrm{}}\mathrm{S}^i(E)t^i`$ for any bundle $`E`$ denote the generating functions for the exterior respective symmetric powers of $`E`$.

###### Definition 2 (see ).

Let $`X`$ be a compact complex manifold of dimension $`d`$. The *elliptic genus $`\mathrm{Ell}(X,z,\tau )`$ of $`X`$* is defined to be the Euler characteristic $`\chi (X,_X(z,\tau ))[[q]][y^{\pm \frac{1}{2}}]`$ of the bundle $`_X(z,\tau )`$ on $`X`$.

The natural transformation $`X\mathrm{\Phi }_X`$ of Definition 1 is in fact a natural transformation as in Example 1. Therefore, $`X\mathrm{Ell}(X)`$ induces in fact a complex genus.

###### Remark 1.

The elliptic genus is a generalization of the $`\chi _y`$-genus of Hirzebruch. More precisely,

$$\chi _y(X)=y^{d/2}\underset{\tau i\mathrm{}}{lim}\mathrm{Ell}(X,z,\tau )=y^{d/2}\mathrm{Ell}(X,z,\tau )|_{q=0}[y],$$
(4)
which follows directly from the definitions.

By Hirzebruch’s theory of genera and multiplicative sequences (), the $`R`$-valued complex genera $`\varphi `$ are in one-to-one correspondence with the formal power series $`f_\varphi R[[x]]`$ over $`R`$ with constant coefficient one. The correspondence is given as follows:

$$\varphi (X)=_X\underset{i=1}{\overset{d}{}}f_\varphi (x_i)$$
(5)
for all complex manifolds $`X`$, where $`d`$ is the dimension of $`X`$, and $`x_1,\mathrm{},x_d`$ are the Chern roots of its tangent bundle.

The representation of the elliptic genus in terms of power series is as follows:

###### Proposition 1.

Let $`x_1,\mathrm{},x_d`$ be the Chern roots of $`X`$. We have

$$\mathrm{Ell}(X,z,\tau )=_X\underset{i=1}{\overset{d}{}}\left(x_i\frac{\vartheta (\frac{x_i}{2\pi i}z,\tau )}{\vartheta \left(\frac{x_i}{2\pi i}\right)}\right),$$
(6)
where Jacobi’s theta function is defined as

$$\vartheta :\times ,(z,\tau )2q^{1/8}\mathrm{sin}(\pi z)\underset{n=1}{\overset{\mathrm{}}{}}\left((1q^n)(1q^ny)(1q^ny^1)\right).$$
(7)
###### Proof.

See . ∎

However, the power series in $`x_i`$ on the right hand side of the product sign has not constant coefficient one. Nevertheless, we can achieve this by following an idea proposed in , where it has been worked out on the $`\chi _y`$-genus: Let us define

$$\psi (z,\tau ):=\underset{x0}{lim}x\frac{\vartheta (\frac{x}{2\pi i}z,\tau )}{\vartheta (\frac{x}{2\pi i},\tau )}=2\pi i\frac{\vartheta (z,\tau )}{\vartheta ^{}(0,\tau )}[[q]][y^{\pm \frac{1}{2}}],$$
(8)
where $`\vartheta ^{}(0,\tau ):=\frac{}{z}|_{z=0}\vartheta (z,\tau )`$. Furthermore, we set

$$f(z,\tau )(x):=\frac{x}{\psi }\frac{\vartheta (\frac{x\psi }{2\pi i}z,\tau )}{\vartheta (\frac{x\psi }{2\pi i},\tau )}[[q]][y^{\pm \frac{1}{2}}][[x]].$$
(9)
This is a power series in $`x`$ with constant coefficient one. With this definition, we have

$$\mathrm{Ell}(X,z,\tau )=_X\underset{i=1}{\overset{d}{}}f(z,\tau )(x_i),$$
(10)
which can be seen by expanding $`f(z,\tau )`$ as a Taylor series in $`x`$ and looking at the degree $`d`$ term.

###### Remark 2.

The power series $`\psi `$ has the following representation as an infinite product:

$$\psi (z,\tau )=\left(y^{\frac{1}{2}}y^{\frac{1}{2}}\right)\underset{n=1}{\overset{\mathrm{}}{}}\frac{(1q^ny)(1q^ny^1)}{(1q^n)^2}.$$
(11)
This can be seen for example by considering the product representations of $`\vartheta (\tau ,z)`$ and $`\vartheta ^{}(0,\tau )`$ given in .

### 2.2. Twisted genera and the twisted elliptic genus

Following our work on complex genera of generalised Kummer varieties (), we define *twisted genera of compact complex manifolds* as follows:

###### Definition 3.

Let $`\varphi `$ be a complex genus with values in the $``$-algebra $`R`$. By $`\varphi _t`$ we denote the genus with values in $`R[t]`$ that is given by

$$\varphi _t(X):=_X\underset{i=1}{\overset{d}{}}\left(f_\varphi (x_i)e^{tx_i}\right)$$
(12)
for any complex manifold $`X`$ of dimension $`d`$, and with Chern roots $`x_1,\mathrm{},x_d`$.

###### Remark 3.

Obviously, if a the genus $`\varphi `$ is given by a natural transformation $`\mathrm{\Phi }`$ as in Example 1, we have

$$\varphi _t(X)=\chi (X,\mathrm{\Phi }_X(𝒯_X)K_X^t).$$
(13)
for any integer $`t`$. Of course, this can also be written as

$$\varphi _t(X)=\chi (X,\mathrm{\Phi }_{t,X}(𝒯_X))$$
(14)
with the natural transformation $`\mathrm{\Phi }_t`$ defined by $`\mathrm{\Phi }_{t,X}(E):=\mathrm{\Phi }_X(E)(detE)^t`$ for any bundle $`E`$ on $`X`$.

In general, the twisted version of a complex genus holds more information than the untwisted genus itself. In the case of the elliptic genus, however, this is not true, i.e. the elliptic genus encodes all the information of its twisted version.

As we are interested only in manifolds of even dimension for the purpose of proving our main theorem, let $`X`$ be of even dimension $`d=2n`$ from now on.

###### Proposition 2.

The elliptic genus twisted by $`t\psi `$, t an integer, of the compact complex manifold $`X`$ can be expressed by the usual elliptic genus via

$$\mathrm{Ell}_{t\psi }(X,z,\tau )=y^{2nt}q^{nt^2}\mathrm{Ell}(X,z+t\tau ,\tau ).$$
(15)
###### Proof.

We will make use of the following transformation property of the theta function (see for example ):

$$\vartheta (z+\tau ,\tau )=q^{\frac{1}{2}}y^1\vartheta (z,\tau )$$
(16)
where $`q^{\frac{1}{2}}`$ stands for $`\mathrm{exp}(\pi i\tau )`$. It follows by definition that

$$f(z,\tau ,x)=q^{\frac{1}{2}}ye^{x\psi }f(x,z+\tau ,\tau ).$$
(17)
Now we use (10) and find that

$$\mathrm{Ell}_{t\psi }(X,z,\tau )=q^ny^{2n}\mathrm{Ell}_{(t1)\psi }(X,z+\tau ,\tau )$$
(18)
by the definition of twisted genera. The proposition then follows by induction on $`t`$. ∎

From this we deduce the following proposition on the Fourier coefficients of twisted elliptic genera:

###### Proposition 3.

Let $`t`$ be an integer and $`c_t(m,l)`$ for $`m,2l`$ be such that

$$\underset{m,2l}{}c_t(m,l)q^my^l=\mathrm{Ell}_{t\psi }(X,z,\tau ).$$
(19)
These coefficients are connected to the coefficients $`c(m,l):=c_0(m,l)`$ of the untwisted elliptic genus via

$$c_t(m,l)=c(mlt+nt^2,l2t).$$
(20)
###### Proof.

By Proposition 2, we have

$$\begin{array}{c}\underset{m,2l}{}c_t(m,l)q^my^l=\mathrm{Ell}_{t\psi }(X,z,\tau )=y^{2nt}q^{nt^2}\mathrm{Ell}(X,z+t\tau ,\tau )\hfill \\ \hfill =y^{2nt}q^{nt^2}\underset{m,2lZ}{}c(m,l)q^m(yq^t)^l=\underset{m,2l}{}c(m,l)q^{m+lt+nt^2}y^{l+2nt}\\ \hfill =\underset{m,2l}{}c(m,l2nt)q^{m+ltnt^2}y^l=\underset{m,2l}{}c(mlt+nt^2,l2nt)q^my^l.\end{array}$$

Now compare coefficients. ∎

## 3. The generalised Kummer varieties

### 3.1. Definition of generalised Kummer varieties

Let $`X`$ be a smooth projective surface over the field of complex numbers. For every nonnegative integer we denote by $`X^{[n]}`$ the Hilbert scheme of zero-dimensional subschemes of $`X`$ of length $`n`$. By a result of Fogarty , this scheme is smooth and projective of dimension $`2n`$. It can be viewed as a resolution $`\rho :X^{[n]}X^{(n)}`$ of the $`n`$-fold symmetric product $`X^{(n)}:=X^n/𝔖_n`$ of $`X`$. The morphism $`\rho `$, sending closed points, i.e. subschemes of $`X`$, to their support counting multiplicities, is called the Hilbert-Chow morphism.

Let us briefly recall the construction of the generalised Kummer varieties introduced by Beauville . Let $`A`$ be an abelian surface and $`n>0`$. There is an obvious summation morphism $`A^{(n)}A`$. We denote its composition with the Hilbert-Chow morphism $`\rho :A^{[n]}A^{(n)}`$ by $`\sigma :A^{[n]}A`$.

###### Definition 4.

The *$`n^{\text{th}}`$ generalised Kummer variety $`A^{[[n]]}`$* is the fibre of $`\sigma `$ over $`0A`$.

###### Remark 4.

It was Beauville who showed among other things in  that the $`n^{\mathrm{th}}`$ generalised Kummer variety is smooth projective, and irreducible holomorphic symplectic of dimension $`2(n1)`$.

### 3.2. Complex genera of generalised Kummer varieties

Let

$$K(p):=\underset{n=1}{\overset{\mathrm{}}{}}\left[A^{[[n]]}\right]p^n\mathrm{\Omega }[[p]]$$
(21)
be the generating series of the complex cobordism classes of the generalised Kummer varieties and similarly

$$H_X(p):=\underset{n=0}{\overset{\mathrm{}}{}}\left[X^{[n]}\right]p^n\mathrm{\Omega }[[p]]$$
(22)
the generating series to the Hilbert schemes of points on a surface $`X`$.

In  we proved the following theorem:

###### Theorem 1.

Let $`\varphi :\mathrm{\Omega }R`$ be a complex genus with values in the $``$-algebra $`R`$. For every smooth projective surface $`X`$ with $`_Xc_1(X)^20`$,

$$\varphi (K(p))=\frac{1}{c_1(X)^2}\left(p\frac{\mathrm{d}}{\mathrm{d}p}\right)^2\mathrm{ln}\frac{\varphi _1(H_X(p))\varphi _1(H_X(p))}{\varphi (H_X(p))^2}.$$
(23)
###### Proof.

See . ∎

Taking a look at the proofs of  or at the results of , we see that $`\mathrm{ln}\varphi _t(H_X(p))`$ is a polynomial in $`t`$ of degree $`2`$, and therefore

$$\mathrm{ln}\frac{\varphi _1(H_X(p))\varphi _1(H_X(p))}{\varphi (H_X(p))^2}=\frac{\mathrm{d}^2}{\mathrm{d}t^2}|_{t=0}\mathrm{ln}\varphi _t(H_X(p)).$$
(24)
So, the genus $`\varphi `$ of $`K(p)`$ can be expressed as

$$\varphi (K(p))=2\left(p\frac{\mathrm{d}}{\mathrm{d}p}\right)^2A_\varphi (p)$$
(25)
for any smooth projective surface $`X`$ with $`c_1(X)^20`$. Here,

$$A_\varphi (p):=\frac{1}{2c_1(X)^2}\frac{\mathrm{d}^2}{\mathrm{d}t^2}|_{t=0}\mathrm{ln}\varphi _t(H_X(p)),$$
(26)
which is independent of $`X`$. We shall use the formula (25) to calculate the elliptic genera of the generalised Kummer varieties.

## 4. Elliptic genera of generalised Kummer varieties

In the following proposition, we shall calculate twisted elliptic genera of Hilbert schemes of points on surfaces. We shall make use of the following recent theorem of Borisov and Libgober ():

###### Theorem 2.

Let $`X`$ be a complex projective surface. Let $`c(m,l)`$ for $`m,2l`$ be the Fourier coefficients of the elliptic genus of $`X`$, i.e. $`\mathrm{Ell}(X,z,\tau )=_{m,2l}c(m,l)q^my^l`$. Then the elliptic genera of the Hilbert schemes $`X^{[n]}`$ of zero-dimensional subschemes of length $`n`$ on $`X`$ are given by:

$$\mathrm{Ell}(H_X(p),z,\tau ):=\underset{n=0}{\overset{\mathrm{}}{}}p^n\mathrm{Ell}(X^{[n]},z,\tau )=\underset{i=1}{\overset{\mathrm{}}{}}\underset{m,2l}{}(1p^iq^my^l)^{c(mi,l)}.$$
(27)
###### Proof.

See . ∎

###### Proposition 4.

As a corollary to the previous theorem, we have

$$\mathrm{Ell}_{t\psi }(H_X(p),z,\tau ):=\underset{n=0}{\overset{\mathrm{}}{}}p^n\mathrm{Ell}_{t\psi }(X^{[n]},z,\tau )=\underset{i=1}{\overset{\mathrm{}}{}}\underset{m,2l}{}(1p^iy^lq^m)^{c_{it}(mi,l)},$$
(28)
for every integer $`t`$, i.e.
$$\mathrm{ln}\mathrm{Ell}_{t\psi }(H_X(p),z,\tau )=\underset{i,k=1}{\overset{\mathrm{}}{}}\underset{m,2l}{}\frac{1}{k}c_{it}(mi,l)p^{ik}y^{lk}q^{mk}.$$
(29)
###### Proof.

This proof consists just of a straight-forward calculation:

$`{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}p^n\mathrm{Ell}_{t\psi }(X^{[n]},z,\tau )={\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}p^ny^{2nt}q^{nt^2}\mathrm{Ell}(X^{[n]},z+t\tau ,\tau )`$
$`=`$ $`{\displaystyle \underset{i=1}{\overset{\mathrm{}}{}}}{\displaystyle \underset{m,2l}{}}(1(py^{2t}q^{t^2})^iq^m(yq^t)^l)^{c(mi,l)}`$
$`=`$ $`{\displaystyle \underset{i=1}{\overset{\mathrm{}}{}}}{\displaystyle \underset{m,2l}{}}(1p^iq^{m+lt+it^2}y^{l+2it})^{c(mi,l)}`$
$`=`$ $`{\displaystyle \underset{i=1}{\overset{\mathrm{}}{}}}{\displaystyle \underset{m,2l}{}}(1p^iy^lq^{m+ltit^2})^{c(mi,l2it)}`$
$`=`$ $`{\displaystyle \underset{i=1}{\overset{\mathrm{}}{}}}{\displaystyle \underset{m,2l}{}}(1p^iy^lq^m)^{c(milit+i^2t^2,l2it)}`$
$`=`$ $`{\displaystyle \underset{i=1}{\overset{\mathrm{}}{}}}{\displaystyle \underset{m,2l}{}}(1p^iy^lq^m)^{c_{it}(mi,l)}.`$
###### Lemma 1.

Let $`X`$ be a smooth projective surface. Let $`c_t(m,l)`$ for $`m,2l`$ be the Fourier coefficients of the twisted elliptic genus $`\mathrm{Ell}_{t\psi }`$ of $`X`$. We have

$$\frac{\mathrm{d}^2}{\mathrm{d}t^2}|_{t=0}c_t(m,l)=u(m,l)c_1(X)^2,$$
(30)
where $`u(m,l)`$ for $`m,2l`$ is such that

$$\underset{m,2l}{}u(m,l)q^my^l=\psi ^2(z,\tau ).$$
(31)
###### Proof.

Such a statement is actually true for any genus on a surface $`X`$: If $`\varphi `$ is any complex genus, then

$$\frac{\mathrm{d}^2}{\mathrm{d}t^2}|_{t=0}\varphi _t(X)=c_1(X)^2,$$
($``$)
which follows from the fact that $`\varphi _t(X)`$ is polynomial of degree two in $`t`$ with leading coefficient $`c_1(X)^2/2`$. From ($``$) the lemma follows by the chain rule. ∎

###### Proposition 5.

For every smooth projective surface $`X`$ and $`u(m,l)`$ for $`m,2l`$ as in Lemma 1 we have:

$$\frac{\mathrm{d}^2}{\mathrm{d}t^2}|_{t=0}\mathrm{ln}\mathrm{Ell}_{t\psi }(H_X(p),z,\tau )=c_1(X)^2\underset{i,k=1}{\overset{\mathrm{}}{}}\underset{m,2l}{}i^2\frac{1}{k}p^{ik}q^{mk}y^{lk}u(mi,l).$$
(32)
###### Proof.

This proposition follows immediately from Proposition 4 and Lemma 1. ∎

Now we can use that proposition together with the theorem on complex genera of generalised Kummer varieties to prove our main theorem:

###### Theorem 3.

Let $`J_{k,r}`$ for $`k,2r`$ be the space of weak Jacobi forms of weight $`k`$ and index $`r`$. Following  we define for every $`i`$ a Hecke operator

$$V(i):J_{k,r}J_{k,ir},\varphi \varphi |_kV(i)$$
(33)
by

$$(\varphi |_kV(i))(z,\tau ):=\underset{a|i}{}a^{k1}\underset{m,2l}{}c(\frac{mi}{a},l)q^{am}y^{al},$$
(34)
where the $`c(m,l)`$ are the Fourier coefficients of $`\varphi `$, i.e. $`\varphi (z,\tau )=_{m,2l}c(m,l)q^my^l`$.

The following statements hold true: $`\psi ^2`$ is a weak Jacobi form of weight $`2`$ and index $`1`$, $`\psi ^2\left(\psi ^2|_2V(i)\right)`$ is a weak Jacobi form of weight $`0`$ and index $`i1`$, and the elliptic genera of the generalised Kummer varieties are given by

$$\mathrm{Ell}(K(p))=\underset{i=1}{\overset{\mathrm{}}{}}\mathrm{Ell}(A^{[[n]]})p^n=\psi ^2\underset{i=1}{\overset{\mathrm{}}{}}i^4\left(\psi ^2|_2V(i)\right)p^i.$$
(35)
###### Proof.

The holomorphic function $`\psi ^2`$ is (up to a factor) *the* weak Jacobi form of weight $`2`$ and weight index $`1`$ (see ). Then note that the space of weak Jacobi forms of weight $`2`$ lies inside the principal ideal spanned by $`\psi ^2`$ in $`J_{2,}`$ which follows from the classification theorem on weak Jacobi forms in .

Let $`X`$ be any smooth projective surface with $`c_1(X)^20`$. By (25) and the previous proposition we have

$`{\displaystyle \underset{i=1}{\overset{\mathrm{}}{}}}\mathrm{Ell}(A^{[[n]]})p^n`$
$`=`$ $`{\displaystyle \frac{1}{c_1(X)^2}}\left(p{\displaystyle \frac{\mathrm{d}}{\mathrm{d}p}}\right)^2{\displaystyle \frac{\mathrm{d}^2}{\mathrm{d}t^2}}|_{t=0}\mathrm{ln}\mathrm{Ell}_t(H_X(p))`$
$`=`$ $`\psi ^2{\displaystyle \underset{i,k=1}{\overset{\mathrm{}}{}}}{\displaystyle \underset{m,2l}{}}i^4kp^{ik}q^{mk}y^{lk}u(mi,l)`$
$`=`$ $`\psi ^2{\displaystyle \underset{i=1}{\overset{\mathrm{}}{}}}i^4{\displaystyle \underset{a|i}{}}a^3{\displaystyle \underset{m,2l}{}}u({\displaystyle \frac{mi}{a}},l)q^{am}y^{al},`$
which proves the rest of the theorem. ∎

We can easily deduce Göttsche’s and Soergel’s formula on the $`\chi _y`$-genus of a generalised Kummer variety () from this theorem:

###### Corollary 1 (Göttsche, Soergel ()).

Let $`n`$ be a positive integer. The $`\chi _y`$-genus of the generalised Kummer variety $`A^{[[n]]}`$ is given by:

$$\chi _y(A^{[[n]]})=y^{n1}n^4\underset{a|n}{}a^3\frac{y^a+y^a2}{y+y^12}$$
(36)
###### Proof.

We have

$$\chi _y(A^{[[n]]})=y^{n1}\mathrm{Ell}(A^{[[n]]},\tau ,z)|_{q=0}=y^{n1}\psi ^2(\tau ,z)|_{q=0}n^4(\psi ^2|_2V(n))(\tau ,z)|_{q=0}.$$

Now we use that $`\psi ^2(\tau ,z)|_{q=0}=(y+y^12)`$ and the following representation of the Hecke operators (see )

$$\left(\psi ^2|_2V(n)\right)(\tau ,z)=n^1\underset{a|n}{}\underset{b=0}{\overset{n/a1}{}}a^2\psi ^2(\frac{a\tau +b}{n/a},az),$$

i.e.
$$\begin{array}{cc}\hfill \left(\psi ^2|_2V(n)\right)(\tau ,z)|_{q=0}=& n^1\underset{a|n}{}\underset{b=0}{\overset{n/a1}{}}a^2\underset{\tau i\mathrm{}}{lim}\psi ^2(\frac{a\tau +b}{n/a},az)\hfill \\ \hfill =& n^1\underset{a|n}{}\underset{b=0}{\overset{n/a1}{}}a^2\left(y^a+y^a+2\right)\hfill \\ \hfill =& \underset{a|n}{}a^3\left(y^a+y^a+2\right),\hfill \end{array}$$

to conclude the formula given in the corollary. ∎


text:
# The evolution of radio galaxy emission line regions: Breaking the P-z degeneracy

## 1. Introduction

The emission line regions (ELRs) of high redshift radio galaxies are generally more extensive than those of lower redshift sources. Spectroscopic studies of 3CR sources at $`z1`$ (Best, Röttgering & Longair 2000a, 2000b) reveal that the size of the radio source plays an important role in determining the dominant ionization mechanism. The emission lines of small sources are best explained by the predictions of shock ionization associated with the passage of the radio cocoon. Larger sources usually appear photoionized by the central AGN, and typically exist in a higher ionization state than their smaller counterparts.

Studies of 3CR radio galaxies reveal considerable changes with redshift, with the lower redshift/radio power sources (degenerate in the flux limited 3CR sample) generally having much less extreme kinematics than sources at $`z1`$ (Baum & McCarthy 2000; Best et al 2000b). This degeneracy can be broken by means of a comparison with other radio galaxy surveys, e.g. the 6C sample.

## 2. Breaking the redshift–radio power degeneracy

We have studied a complete subsample of 8 6C galaxies within the redshift range $`0.85<z<1.3`$ (Inskip et al, in prep). These are a factor of $`6`$ lower in radio power than 3CR sources at the same redshift. The ionization and kinematic properties of the ELRs of these galaxies have been compared with those of the $`z1`$ 3CR subsample of Best et al (2000a), and also with lower redshift 3CR sources matched in radio power to the 6C $`z1`$ subsample. Low redshift ELR kinematic data were obtained from Baum & McCarthy (2000); ionization data were obtained from Tadhunter et al (1998). This combination of samples allows us to break the P–z degeneracy effectively.

Fig. 1 displays kinematic data for three subsamples, plotted against D and P. Principal component analysis and partial rank correlation tests on these data sets have been used to determine the relative importance of P, D and z on the changing ionization and kinematic properties of radio galaxy ELRs. For larger radio galaxies, the gas kinematics become less extreme, and the ionization state increases, as has been found in previous studies (e.g. Best et al 2000b). In addition to this, we also find that ionization state is strongly dependent on P but not z, with the more powerful radio sources existing in higher ionization states than less powerful sources independent of redshift. On the other hand, the FWHM of the ELRs is correlated most strongly with redshift, as well as with radio power. The most extreme kinematics are observed in powerful radio sources at high redshift.

From this analysis we conclude that:
1. AGN properties vary little with redshift, and the power/age of a radio source is the determining factor in the ionization mechanism of the emission line gas.
2. The gas kinematics points to significant evolution of the host galaxy and ELR properties with redshift, in addition to their dependency on the properties of the radio source.

## References

Baum S.A., McCarthy P.J., 2000, ApJ, 119, 2634

Best P.N., Röttgering H.J.A., Longair M.S., 2000a, MNRAS, 311, 1

Best P.N., Röttgering H.J.A., Longair M.S., 2000b, MNRAS, 311, 23

Inskip K. J., Best P. N., Rawlings S., Cotter G., Longair M. S., Röttgering H. J. A., Eales S. A., in prep.

Tadhunter C.N., Morganti R., Robinson A., Dickson R., Villar-Martín M., 1998, MNRAS, 298, 1035


text:
# Nature of Integer Quantum Hall Transitions

\[

## Abstract

The mapping between the metal-insulator transition of the quantum Hall system and a superfluid-to-insulator transition is revisited based on a disordered anyon model. The one-parameter scaling of the superfluid-to-insulator transition is employed for the analysis of the scaling behavior of the integer quantum Hall transitions. The analysis reveals the direct transition from a quantum Hall plateau to the insulator in weak disorder limit, and a float-down transition for strong disorders. In either cases, the transition corresponds to a non-chirality superfluid-to-insulator transition, with the longitudinal and transverse quantum Hall conductivities following a semi-circle relation.

preprint: January 27, 1998
\]

The problem of metal-insulator transition in quantum Hall systems has attracted much attention \[1-4\] since the discovery of integer quantum Hall (IQH) effect. As the scaling theory of localization  predicts localization of all non-interacting electrons in two dimensions, a natural challenge has been to understand the extended states at the center of disorder-broadened Laudau bands in the IQH system. Laughlin  and Khmelnitskii  proposed a quasi-classical theory on the float-up of the extended states near the band edge. Based on the float-up scenario, Pruisken  concluded that there exists two sets of fixed point in the renormalization group phase diagram for the IQH system. One set of stable fixed point is located at $`\sigma _{xx}^H=0`$ and $`\sigma _{xy}^H=n`$ (in the unit of $`e^2/h`$), corresponding to the Hall plateau. The other set of unstable fixed points is located at $`\sigma _{xx}^H`$ (independent of $`n`$) and $`\sigma _{xy}^H=n\pm \frac{1}{2}`$, corresponding to the center of each Laudau band, which signals a localization-delocalization phase transition. A renormalization group flow diagram showing two-parameter scaling for the IQH system was established; the Hall conductance appears as a second coupling constant, in addition to the dissipative conductance. The sets of fixed points are subsequently employed to the study of the global phase diagram of the quantum Hall effect .

Kivelson, Lee and Zhang  (KLZ) proposed a global phase diagram for the quantum Hall system based on a mapping of the corresponding states of the metal-to-insulator transition to ones of a superfluid-to-insulator transition. The theory predicted the critical conductance $`\sigma _{xx}^H=\frac{1}{2}`$ that is supported by subsequent simulation studies for $`n=10`$ transition . The global phase diagram was then constructed using symmetry transformations of the float-up picture, including the particle-hole, flux attachment, and the Laudau level addition transformations. By construction, the global phase diagram allows only nearest-neighbor IQH plateau transitions. However, the direct transitions from high IQH plateau ($`n>1`$) to insulator have been observed by both experiments \[7-8\] and computer simulations \[9-13\]. It was argued that the incapability of predicting the direct transitions in the global phase diagram is attributed to the lattice effects that are not present in the continuum models.

In this Letter, I revisit the mapping between the metal-to-insulator transitions and the superfluid-to-insulator transition based on a disordered anyon model . The resultant mapping relations are essentially the same as those obtained by KLZ in the weak disorder limit. However, closer scrutiny of the self-duality relations without invoking the symmetry transformations a priori, reveals the existence of direct transitions form high quantum Hall plateaus to the insulator. This finding and the associated predictions based on one-parameter scaling flow are remarkably in agreement with the numerical simulations \[9-13\]; thereby providing important information on the microscopic origin of the direct transitions. Subsequently, we consider the strong disorder limit where the float-down transitions become appropriate. A distinct feature of our analysis is the realization that a superfluid-to-insulator transition with non-chirality constraint, maps to a quantum Hall critical region where the longitudinal and transverse quantum Hall conductivities satisfy a semi-circle relation. The semi-circle relation was proposed by Ruzin and co-workers  based on a phenomenological two-fluid theory.

$`Statistical`$ $`mapping.`$The disordered anyon model is described by the Hamiltonian

$$\widehat{H}=\underset{i}{}\left\{\frac{1}{2m}\left(𝐏_i\widehat{𝐀}(𝐫_i)\right)^2+V(𝐫_i)\right\},$$
(1)
where $`V(𝐫_i)`$ is short-range correlated random potential, and $`\widehat{𝐀}(𝐫_i)`$ is a statistical field operator given by

$$\widehat{𝐀}(𝐫_i)\frac{\mathrm{}}{n}\underset{j}{}\frac{\widehat{𝐳}\times (𝐫_i𝐫_j)}{|𝐫_i𝐫_j|^2},$$
(2)
with $`\widehat{𝐳}`$ a unit vector normal to the plane, and $`n`$ the so-called statistics parameter ($`n=1`$ for bosons; $`n=2`$ for semions; and $`n=\mathrm{}`$ for fermions) characterizing the specific form of the fractional statistics. The system is equivalent to spinless fermions interacting through Chern-Simons gauge field and disordered impurity scattering. It is worth noting that disordered-fermion system stands for the $`n=\mathrm{}`$ limit of the model.

We first consider the average statistical field that yields a fictitious magnetic field $`𝐁=B\widehat{𝐳}`$. The resulting mean-field Hamiltonian

$$\widehat{H_0}=\underset{i}{}\frac{1}{2m}(𝐏_i\overline{𝐀}_i)^2+V(𝐫_i),$$
(3)
describes a collection of spinless particles moving in a strong magnetic field $`𝐁`$ with $`n`$ filled Laudau bands and the random potential $`V`$. The equivalence between the IQH system and the mean-field solution of the disordered anyon system is crucial in the statistical mapping.

The effect of statistical-field fluctuations around the mean-field solution, $`\widehat{H}\widehat{H_0}`$, can be evaluated by a consistent $`1/n`$-expansion scheme . In the absence of the random potential, the leading-$`1/n`$-order results are the same as those obtained in the calculation of the random-phase-approximation (RPA) response functions . Based on a correlated RPA calculation , we have shown that the next-leading-order corrections to the RPA results have no effect in the long-wavelength limit. As a consequence, the longitudinal and transverse conductivities, $`\sigma _{xx}`$ and $`\sigma _{xy}`$, can be evaluated from the leading-$`1/n`$-order current-current correlation functions at $`T=0`$, and are related to those for IQH systems, $`\sigma _{xx}^H`$ and $`\sigma _{xy}^H`$, by expressions :

$`\sigma _{xx}`$ $`=`$ $`n^2{\displaystyle \frac{\sigma _{xx}^H}{(\sigma _{xx}^H)^2+(\sigma _{xy}^Hn)^2}},`$ (4)
$`\sigma _{xy}`$ $`=`$ $`\sigma _R+n^2{\displaystyle \frac{\sigma _{xy}^Hn}{(\sigma _{xx}^H)^2+(\sigma _{xy}^Hn)^2}}.`$ (5)
Here $`\sigma _R=n`$ in the absence of disorders. This set of equations is equivalent to that obtained by KLZ  via a transformation $`n1/n`$. In fact, they become identical if one changes the unit of conductivities in Eqs. (4-5) from $`e^2/h`$ to $`e^2/h`$ where $`e^{}=ne`$.

The mapping of conductivities between the disordered anyon system and the IQH system is self-dual in that exchanging $`(\sigma _{xx}^H,\sigma _{xy}^H)`$ with $`(\sigma _{xx},\sigma _{xy})`$, the function form of Eqs. (4-5) remains invariant. The self-duality is the ramification of the particle-vortex duality in connection to the Chern-Simons gauge field.

It is worth pointing out that the effect of disorder plays an important role in the IQH systems. As such, it is necessary to evaluate the effect of disorder on the mapping relations. In the weak disorder limit, the self-duality equations was argued to be intact . The weak-disorder limit refers to the case that there exists IQH effect for $`n`$ Landau bands. In this case, the contribution to $`\sigma _R`$ for the anyon model can be calculated using the quasi-classical theory \[1-2\].

Considerable insight of the scaling behavior of the quantum Hall transitions can be gained from the mapping . To this end, we first construct the corresponding states between the two systems. From Eqs. (4-5), $`(\sigma _{xx}^H,\sigma _{xy}^H)=(0,0)`$ maps to $`(\sigma _{xx},\sigma _{xy})=(0,0)`$, corresponding to an insulating state. The “localization” fixed points associated with the plateau solutions in the IQH system correspond to two types of states in the disordered anyon system. $`(\sigma _{xx}^H,\sigma _{xy}^H)=(0,m)`$ ($`mn`$) maps to a quantum Hall conductor, and $`(\sigma _{xx}^H,\sigma _{xy}^H)=(0,n)`$ was shown to map to $`(\sigma _{xx},\sigma _{xy})=(\mathrm{},n)`$, corresponding to an anyon-type superfluid state , characterized by a spontaneous breaking of parity and time-reversal invariance. Based on the concept of corresponding states, KLZ  constructed the global phase diagram using symmetry transformations.

Direct transition.$``$While the corresponding state for the insulator is unique, the corresponding state for the superfluid state is not. As a matter of fact, the corresponding state for $`(\sigma _{xx}^H,\sigma _{xy}^H)=(0,n)`$ depends on the approaching path. For our purpose, we are motivated to search for a critical flow without breaking the parity and time-reversal symmetries, characterized by $`\sigma _{xy,c}=0`$. In the context of two-parameter renormalization flow, this amounts to finding the critical regions that follow a one-parameter (here it stands for $`\sigma _{xx,c}`$) scaling. From Eq. (5), one has

$$\sigma _{xy,c}=n^2\frac{\sigma _{xy,c}^Hn}{(\sigma _{xx,c}^H)^2+(\sigma _{xy,c}^Hn)^2}+n=0.$$
(6)
The solution of the above equation leads to a flow line where the longitudinal and transverse quantum Hall conductivities follow a semi-circle relation:

$$(\sigma _{xx,c}^H)^2+(\sigma _{xy,c}^H\frac{n}{2})^2=(\frac{n}{2})^2.$$
(7)
Summarized in Table I are the corresponding states in concord with the one-parameter scaling flow. It is interesting to observe that an anyon superfluid state without breaking the parity and time-reversal symmetries can be reached if the corresponding quantum Hall conductivities following a semi-circle relation in the critical region. From a general two-parameter scaling point of view, it is expected a general points at the $`\sigma _{xx}^H\sigma _{xy}^H`$ plane will flow into the semi-circle critical regions. There exists three fixed points in the critical region: two stable ones at $`(\sigma _{xx}^H,\sigma _{xy}^H)=(0,0)`$ and $`(\mathrm{},0)`$, corresponding to the insulator and superfluid states, respectively. The unstable one is located at $`(\sigma _{xx}^H,\sigma _{xy}^H)=(n/2,n/2)`$, corresponding a quantum normal critical point for the non-chirality superfluid-to-insulation transition point with a critical normal conductance $`\sigma _R`$.

It is intriguing to note that the direct metal-insulator transition is exactly what Sheng and Weng  have identified based on their tight-binding lattice model study of the IQH effect. Apart from the case of $`n=1`$, it is different from the nearest-neighbor plateau transitions. Our analysis shows that for this universality class, the critical fixed points, $`(\sigma _{xx}^H,\sigma _{xy}^H)=(n/2,n/2)`$, can be derived from the symmetry considerations of the duality transformation.

An important implication of the above mapping analysis is that the longitudinal conductance of the IQH system follows a scaling form (using the self-dual transformation Eqs. (4-5) and the semi-circle relation)

$$\frac{\sigma _{xx}^H}{\sigma _{xx}^H}=\frac{2(\sigma _{xx}/\sigma _R)}{1+(\sigma _{xx}/\sigma _R)^2}.$$
(8)
Remarkably, this is exactly the form that has been found empirically from numerical simulations .

It is gratifying to show that the direct transitions are intimately connected to the particle-vortex duality intrinsic in the self-duality mapping. It becomes clear that the symmetry transformations used in the global phase diagram , however, are in general not in conformity to the self-duality. The self-duality between the particle and vortex yields non-trivial coupling and/or merging of the edge states.

$`Float`$-$`down`$ $`transition.`$With the increase of disorder, the IQH effect for the high Laudau band disappears one after another . As a result, the particle-vortex duality is broken. Thus we need to consider the effect of disorder on the change of mapping relations. From the correlated RPA equations , it is worth noting that for averaging over the disorder, the longitudinal and transverse conductivities appearing in Eqs (4-5) are treated in the equal footing. The only part that needs to be reevaluated is the disconnected part that contributes to $`\sigma _R`$. In principle, the contribution depends on the strength and the specific form of the disorder. However, one can consider the strong disorder case when all the extended states of the anyons are projected onto the lowest Laudau level for composite fermions. In this limit, the vortices are pinned by disorder and bidding together as composite fermions, with charge $`ne`$. One can argue that the contribution of a charge $`ne`$ composite fermion with flux quantization $`h/ne`$ is $`\sigma _R=n^2`$. This is equivalent to set $`\sigma _R`$ equal to 1 in the unit of $`e^2/h`$ ($`e^{}=ne`$), the value for the lowest Landau level.

With $`\sigma _R=n^2`$, it is readily observable from Eqs. (4-5) that the delocalization point is located at $`\sigma _{xx}^H=\frac{1}{2}`$ and $`\sigma _{xy}^H=n\frac{1}{2}`$, in concord with the float-up fixed points. Also listed in Table I are the corresponding states for this case. In contrast to the direct transition scenario where there exits a particle-vortex duality, here $`(\sigma _{xx}^H,\sigma _{xy}^H)=(0,n1)`$ maps to the insulating state $`(\sigma _{xx},\sigma _{xy})=(0,0)`$. The float-down transitions can be viewed as follows: $`(\sigma _{xx}^H,\sigma _{xy}^H)=(0,n)`$ maps to a superfluid state for $`n`$-anyons. Through a metal-to-insulator transition following a semi-circle law

$$(\sigma _{xx,c}^H)^2+(\sigma _{xy,c}^Hn+\frac{1}{2})^2=(\frac{1}{2})^2,$$
(9)
which corresponds to a superfluid-to-insulator transition for $`n`$anyons, it reaches $`(\sigma _{xx}^H,\sigma _{xy}^H)=(0,n1)`$ that is an insulating state for $`n`$anyons as well as a superfluid state for $`(n1)`$anyons. This leads to successive multi-step transitions, in agreement with the scenario provided by the global phase diagram for float-down transitions .

It is interesting to note that the projection of extended states onto the lowest Laudau band for composite fermions refers to a situation appropriate for the fractional quantum Hall systems. The symmetry transformations employed in the global phase diagram are valid for fractional quantum Hall transitions. Therefore, the float-down transition can be realized for system of composite fermions. In general, both direct and float-down transitions can happen in the IQH phase diagram. A detailed determination of the complicated phase boundaries requires the reference of numerical simulations \[9-13\]. It is attempting to argue that there exists two critical magnetic fields, $`B_{c1}`$ and $`B_{c2}`$. When $`B_{c1}`$ is reached from low-$`B`$ side, the phase diagram shows direct transition, following a scaling behavior as given by Eq. (8) . In the region $`B_{c1}<B<B_{c2}`$, there exist regions for float-down transitions, and the one-parameter scaling form of Eq. (8) is no longer valid. A detailed analysis of the IQH phase diagrams deserves further studies.

$`Semi`$-$`circle`$ $`relation.`$The above analysis can be extended to the general case of $`nm`$ plateau-plateau transitions. The critical region is defined by a semi-circle relation:

$$(\sigma _{xx,c}^H)^2+(\sigma _{xy,c}^H\frac{n+m}{2})^2=(\frac{nm}{2})^2.$$
(10)
Remarkably, this is exactly the form that Ruzin and co-workers  proposed based on phenomenological arguments. Our analysis shows that this critical region corresponds to a non-chirality superfluid-insulator transition governed by one parameter scaling. The success in extracting this phenomenological theory from the mapping relations provides strong support for the correctness and consistency of our analysis.

$`Conclusions.`$The revisit of the mapping relations between the superfluid-to-insulator transition and the metal-insulator transition of the IQH system reveals the existence of two types of universality classes in the IQH system: the direct transitions in the weak disorder limit, and the float-down transition in the strong disorder limit. Our analysis is based on the physics intuition that the one-parameter scaling of the non-chirality superfluid-to-insulator transition corresponds to critical regions for the quantum Hall system. The resulting predictions provides theoretical foundation for features observed in computer simulations based on the lattice model \[9-13\], such as the the existence of plateau-insulator direct transition universality class  and the universal scaling form of conductancei \[10-11\]. In addition, the analysis shed important light into the microscopic origin of the phenomenological semi-circle relation  for the longitudinal and transverse quantum Hall conductivities at the critical region.

This work was supported by Air Force Office of Scientific Research Grant No. F49620-96-1-0211, US Army Grant No. DAAE07-99-C-L065, and National Science Foundation Grant No. DMR-02-05328.


text:
# The many faces of alternating-sign matrices

## 1 Introduction

An *alternating-sign matrix of order $`n`$* is an $`n`$-by-$`n`$ array of 0’s, $`+1`$’s and $`1`$’s with the property that in each row and each column, the non-zero entries alternate in sign, beginning and ending with a $`+1`$. For example, Figure 1 shows an alternating-sign matrix (ASM for short) of order 4.

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

Figure 1: An alternating-sign matrix of order 4.

Figure 2 exhibits all seven of the ASMs of order 3.

$$\left(\begin{array}{ccc}\hfill 0& \hfill 0& \hfill +1\\ \hfill 0& \hfill +1& \hfill 0\\ \hfill +1& \hfill 0& \hfill 0\end{array}\right)\left(\begin{array}{ccc}\hfill 0& \hfill 0& \hfill +1\\ \hfill +1& \hfill 0& \hfill 0\\ \hfill 0& \hfill +1& \hfill 0\end{array}\right)\left(\begin{array}{ccc}\hfill 0& \hfill +1& \hfill 0\\ \hfill 0& \hfill 0& \hfill +1\\ \hfill +1& \hfill 0& \hfill 0\end{array}\right)\left(\begin{array}{ccc}\hfill 0& \hfill +1& \hfill 0\\ \hfill +1& \hfill 1& \hfill +1\\ \hfill 0& \hfill +1& \hfill 0\end{array}\right)$$

$$\left(\begin{array}{ccc}\hfill 0& \hfill +1& \hfill 0\\ \hfill +1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 0& \hfill +1\end{array}\right)\left(\begin{array}{ccc}\hfill +1& \hfill 0& \hfill 0\\ \hfill 0& \hfill 0& \hfill +1\\ \hfill 0& \hfill +1& \hfill 0\end{array}\right)\left(\begin{array}{ccc}\hfill +1& \hfill 0& \hfill 0\\ \hfill 0& \hfill +1& \hfill 0\\ \hfill 0& \hfill 0& \hfill +1\end{array}\right)$$

Figure 2: The seven alternating-sign matrices of order 3.

Matrices satisfying these constraints were first investigated by Mills, Robbins and Rumsey . The matrices arose from their investigation of Dodgson’s scheme for computing determinants via “condensation” (see section 10). The number of ASMs of order $`n`$, for small values of $`n`$, goes like $`1,2,7,42,429,7436,\mathrm{}`$, and it was conjectured by Mills et al. that the number of ASMs of order $`n`$ is given by the product

$$\frac{1!4!7!\mathrm{}(3n2)!}{n!(n+1)!(n+2)!\mathrm{}(2n1)!}.$$

However, it took over a decade before this conjecture was proved by Zeilberger . For more details on this history, see the expository article by Robbins , the survey article by Bressoud and Propp , or the book by Bressoud .

Here my concern will be not with the alternating-sign matrix conjecture and its proof by Zeilberger, but with the inherent interest of alternating-sign matrices as combinatorial objects admitting many different representations. I will present here a number of different ways of looking at an ASM. Along the way, I will also mention a few topics related to ASMs in their various guises, such as weighted enumeration formulas and asymptotic shape. Much of what is in this article has appeared elsewhere, but I hope that by gathering these topics together in one place, I will help raise the level of knowledge and interest of the mathematical community concerning these fascinating combinatorial objects.

## 2 Corner-sum, heights, and colorings

Given an ASM $`(a_{i,j})_{i,j=1}^n`$ of order $`n`$, we can define a *corner-sum matrix* $`(c_{i,j})_{i,j=0}^n`$ of order $`n`$ by putting $`c_{i,j}=_{i^{}i,j^{}j}a_{i^{},j^{}}`$. This definition was introduced in . Figure 3 shows the seven corner-sum matrices of order 3 (note that they are 4-by-4 matrices).

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

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

Figure 3: The seven corner-sum matrices of order 3.

Corner-sum matrices, viewed as objects in their own right, have a very simple description: the first row and first column consist of 0’s, the last row and last column consist of the numbers from 0 to $`n`$ (in order), and within each row and column, each entry is either equal to, or one more than, the preceding entry.

Note that the seven corner-sum matrices in Figure 3 correspond respectively to the seven alternating-sign matrices in Figure 2. I will adhere to this pattern throughout, to make it easier for the reader to verify the bijections between the different representations.

Corner-sum matrices can in turn be transformed into a somewhat more symmetrical form. Given a corner-sum matrix $`(c_{i,j})_{i,j=0}^n`$ define $`h_{i,j}=i+j2c_{i,j}`$. Call the result a *height-function matrix* (see ). Figure 4 shows the seven height-function matrices of order 3 (4-by-4 matrices).

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

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

Figure 4: The seven height-function matrices of order 3.

Height-function matrices have a simple intrinsic description: the first row and first column consist of the numbers from 0 to $`n`$ (consecutively), the last row and last column consist of the numbers from $`n`$ to 0 (consecutively), and any two entries that are row-adjacent or column-adjacent differ by 1.

If one reduces a height-function matrix modulo 3, and views the residues 0, 1, and 2 as “colors”, one obtains a proper 3-coloring of the $`n+1`$-by-$`n+1`$ square grid satisfying specific boundary conditions. Here “proper” means that adjacent sites get distinct colors, and the specific boundary conditions are as follows: colors increase modulo 3 along the first row and first column and decrease modulo 3 along the last row and last column, with the color 0 occurring in the upper left. Figure 5 shows the seven such 3-colorings of the 4-by-4 grid.

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

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

Figure 5: The seven colorings associated with the ASMs of order 3.

Conversely, every proper 3-coloring of that graph that satisfies the boundary conditions is associated with a unique height-function matrix .

## 3 Monotone triangles and order ideals

Another way to “process” an ASM is to form partial sums of its columns from the top toward the bottom, as shown in Figure 6 for a 4-by-4 ASM. In the resulting square matrix of partial sums, the $`i`$th row has $`i`$ 1’s in it and $`ni`$ 0’s. Hence we may form a triangular array whose $`i`$th row consists of precisely those values $`j`$ for which the $`i,j`$th entry of the partial-sum matrix is 1. The result is called a *monotone triangle*  (or *Gog triangle* in the terminology of Zeilberger ). Figure 7 shows the seven monotone triangles of order 3.

$$\left(\begin{array}{cccc}\hfill 0& \hfill +1& \hfill 0& \hfill 0\\ \hfill +1& \hfill 1& \hfill +1& \hfill 0\\ \hfill 0& \hfill 0& \hfill 0& \hfill +1\\ \hfill 0& \hfill +1& \hfill 0& \hfill 0\end{array}\right)\left(\begin{array}{cccc}\hfill 0& \hfill 1& \hfill 0& \hfill 0\\ \hfill 1& \hfill 0& \hfill 1& \hfill 0\\ \hfill 1& \hfill 0& \hfill 1& \hfill 1\\ \hfill 1& \hfill 1& \hfill 1& \hfill 1\end{array}\right)\begin{array}{ccccccc}& & & \hfill 2& & & \\ & & \hfill 1& & \hfill 3& & \\ & \hfill 1& & \hfill 3& & \hfill 4& \\ \hfill 1& & \hfill 2& & \hfill 3& & \hfill 4\end{array}$$

Figure 6: Turning an ASM into a monotone triangle.

$$\begin{array}{ccccc}& & \hfill 3& & \\ & \hfill 2& & \hfill 3& \\ \hfill 1& & \hfill 2& & \hfill 3\end{array}\begin{array}{ccccc}& & \hfill 3& & \\ & \hfill 1& & \hfill 3& \\ \hfill 1& & \hfill 2& & \hfill 3\end{array}\begin{array}{ccccc}& & \hfill 2& & \\ & \hfill 2& & \hfill 3& \\ \hfill 1& & \hfill 2& & \hfill 3\end{array}\begin{array}{ccccc}& & \hfill 2& & \\ & \hfill 1& & \hfill 3& \\ \hfill 1& & \hfill 2& & \hfill 3\end{array}$$

$$\begin{array}{ccccc}& & \hfill 2& & \\ & \hfill 1& & \hfill 2& \\ \hfill 1& & \hfill 2& & \hfill 3\end{array}\begin{array}{ccccc}& & \hfill 1& & \\ & \hfill 1& & \hfill 3& \\ \hfill 1& & \hfill 2& & \hfill 3\end{array}\begin{array}{ccccc}& & \hfill 1& & \\ & \hfill 1& & \hfill 2& \\ \hfill 1& & \hfill 2& & \hfill 3\end{array}$$

Figure 7: The seven monotone triangles of order 3.

One may intrinsically describe a monotone triangle of order $`n`$ as a triangular array with $`n`$ numbers along each side, where the numbers in the bottom row are $`1`$ through $`n`$ in succession, the numbers in each row are strictly increasing from left to right, and the numbers along diagonals are weakly increasing from left to right. Zeilberger’s proof of the ASM conjecture  used these Gog triangles and a natural generalization, “Gog trapezoids”.

A different geometry comes from looking at the set of ASMs as a distributive lattice. Given two height-function matrices $`(h_{i,j})_{i,j=0}^n`$ and $`(h_{i,j}^{})_{i,j=0}^n`$, we can define new matrices (called the *join* and *meet*) whose $`i,j`$th entries are $`\mathrm{max}(h_{i,j},h_{i,j}^{})`$ and $`\mathrm{min}(h_{i,j},h_{i,j}^{})`$, respectively. These new matrices are themselves height-function matrices, and the operations of join and meet turn the set of ASMs of order $`n`$ into a distributive lattice $`L`$ (see  for background on finite posets and lattices).

The fundamental theorem of finite distributive lattices tells us that $`L`$ can be realized as the lattice of order-ideals of a certain poset $`P`$, namely, the poset of join-irreducibles of the lattice $`L`$. There is a nice geometric description of the ranked poset $`P`$. It has $`(1)(n1)`$ elements of rank 0, $`(2)(n2)`$ elements of rank 1, $`(3)(n3)`$ elements of rank 2, etc., up through $`(n1)(1)`$ elements of rank $`n1`$. These elements are arranged in the fashion of a tetrahedron resting on its edge. A generic element of $`P`$, well inside the interior of the tetrahedron, covers 4 elements and is covered by 4 elements.

Using this poset $`P`$, we can give a picture of the lattice $`L`$ that does not require a knowledge of poset-theory (also described in ). Picture a tetrahedron that is densely packed with $`(1)(n1)+(2)(n2)+(3)(n3)+\mathrm{}+(n1)(1)`$ balls, resting on an edge. Carefully remove the two upper faces of the tetrahedron so as not disturb the balls. One may now start to remove some of the balls, starting from the top, so that removal of a ball does not affect any of the balls below. There are many configurations of this kind, ranging from the full packing to the empty packing. These configurations are in bijective correspondence with the ASMs of order $`n`$, and the lattice operations of meet and join correspond to intersection and union.

## 4 Square ice

Zeilberger’s proof of the ASM conjecture was followed in short order by a simpler proof due to Kuperberg . Kuperberg’s proof made use of a different representation of ASMs, the “6-vertex model” of statistical mechanics. This model is also called square ice on account of its origin as a two-dimensional surrogate for a more realistic (and still intractable) three-dimensional model of ice proposed by physicists . A square ice state is an orientation of the edges of a square grid or a finite sub-graph thereof with the property that each vertex other than vertices on the boundary has two incoming arrows and two outgoing arrows. Each internal vertex must be of one of the six kinds shown in Figure 8 (hence the name “six-vertex model”). The markings under the six vertex-types can be ignored for the time being.

$$\begin{array}{c}\text{}\\ +1\end{array}\begin{array}{c}\text{}\\ 1\end{array}\begin{array}{c}\text{}\\ 0\end{array}\begin{array}{c}\text{}\\ 0\end{array}\begin{array}{c}\text{}\\ 0\end{array}\begin{array}{c}\text{}\\ 0\end{array}$$

Figure 8: The six vertex-types for the square-ice model.

As our finite subgraph of the square grid, we will take the “generalized tic-tac-toe graph” formed by $`n`$ horizontal lines and $`n`$ vertical lines meeting in $`n^2`$ intersections of degree 4, with $`4n`$ vertices of degree 1 at the boundary. We say that an ice state on this graph satisfies *domain-wall boundary conditions*  if all the arrows along the left and right flank point inward and all the arrows along the top and bottom point outward.

Figure 9 shows the possibilities when $`n=3`$.

Figure 9: The seven square-ice states for $`n=3`$ with domain-wall boundary conditions.

These states of the square-ice model are in bijective correspondence with ASMs. To turn a state of the square-ice model on an $`n`$-by-$`n`$ grid with domain-wall boundary conditions into an alternating-sign matrix of order $`n`$, replace each vertex by $`+1`$, $`1`$, or 0 according to the marking given in Figure 8. Kuperberg was able to give a simplified proof of the ASM conjecture by making use of results about the square-ice model in the mathematical physics literature .

An amusing variant of the square-ice model is a tiling model in which the tiles are deformed versions of squares that the physicist Joshua Burton has dubbed “gaskets” and “baskets”, depicted in Figure 10. (To see why the basket deserves its name, you might want to rotate the page by 45 degrees, so that the “handle” of the basket is pointing up.)

Figure 10: A gasket and a basket.

The gasket and basket correspond respectively to the first and last vertex-types shown in Figure 8; the other five vertex-types correspond to tiles obtained by rotating the gasket by 90 degrees or by rotating the basket by 90, 180, or 270 degrees. The directions of the bulges of the four sides of a tile correspond to the orientations of the four edges incident with a vertex. Thus, the seven ASMs of order 3 correspond to the seven distinct ways of tiling the region shown in Figure 11 (a “supergasket” of order 3) with gaskets and baskets.

Figure 11: The seven tilings of an order-3 supergasket with gaskets and baskets.

For another fanciful embodiment of ASMs as tilings, see the cover of .

## 5 Symmetric ASMs and partial ASMs

Some ASMs are more symmetrical than others. More precisely, the eight-element dihedral group $`D_4`$ acts on ASMs, and for every subgroup $`G`$ of $`D_4`$ there are ASMs that are invariant under the action of every element of $`G`$. In , Robbins gave some conjectures for the number of ASMs of order $`n`$ that are invariant under particular groups $`G`$; for most (but not all) of the subgroups $`G`$ of $`D_4`$, numerical evidence suggested specific product-formula. Since then, Kuperberg  has proved some of these, but others remain conjectural.

At the same time, one may also look at halves (or even quarters or eighths) of ASMs — the fundamental regions under the action of the aforementioned groups $`G`$ — and look at them in their own right, asking, How many partial ASMs are there if one limits attention to such a region? There are some interesting phenomena here.

For instance, for $`c_1`$,$`c_2`$,$`c_3`$ each equal to $`+1`$ or $`1`$, define $`N(c_1,c_2,c_3)`$ as the number of 4-by-7 partial height-function matrices of the form shown in Figure 12.

$$\begin{array}{ccccccc}0& 1& 2& 3& 4& 5& 6\\ 1& \mathrm{?}& \mathrm{?}& \mathrm{?}& \mathrm{?}& \mathrm{?}& 5\\ 2& \mathrm{?}& \mathrm{?}& \mathrm{?}& \mathrm{?}& \mathrm{?}& 4\\ 3& 3+c_1& 3& 3+c_2& 3& 3+c_3& 3\end{array}$$

Figure 12: Half of a height-function matrix of order 6.

Not surprisingly, the eight values of $`N(c_1,c_2,c_3)`$ as $`c_1,c_2,c_3`$ vary are not all equal to one another. But it is surprising that the four numbers

$$N(1,1,1),$$

$$(N(1,1,1)+N(1,1,1)+N(1,1,1))/3,$$

$$(N(1,1,1)+N(1,1,1)+N(1,1,1))/3,$$

and

$$N(1,1,1)$$

are all equal. More generally, consider $`(n+1)`$-by-$`(2n+1)`$ partial height-function matrices of the following form:

$$\begin{array}{ccccccccc}0& 1& 2& 3& 4& 5& \mathrm{}& 2n1& 2n\\ 1& \mathrm{?}& \mathrm{?}& \mathrm{?}& \mathrm{?}& \mathrm{?}& \mathrm{}& \mathrm{?}& 2n1\\ 2& \mathrm{?}& \mathrm{?}& \mathrm{?}& \mathrm{?}& \mathrm{?}& \mathrm{}& \mathrm{?}& 2n2\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ n1& \mathrm{?}& \mathrm{?}& \mathrm{?}& \mathrm{?}& \mathrm{?}& \mathrm{}& \mathrm{?}& n+1\\ n& n+c_1& n& n+c_2& n& n+c_3& \mathrm{}& n+c_n& n\end{array}.$$

Figure 13: Half of a height-function matrix of order $`2n`$.

Here each $`c_i`$ ($`1in`$) is either $`+1`$ or $`1`$. Let $`N(c_1,c_2,\mathrm{},c_n)`$ be the number of such partial height-function matrices. Then one finds empirically that for every $`k`$ in $`n,(n2),(n4),\mathrm{},n4,n2,n`$, the average of $`N(c_1,c_2,\mathrm{},c_n)`$ over all vectors $`(c_1,\mathrm{},c_n)`$ satisfying $`c_1+\mathrm{}+c_n=k`$ depends only on $`n`$, not on $`k`$. Kuperberg has found an algebraic proof of this using the Tsuchiya determinant formula  invented for the study of the square ice model, but there ought to be a purely combinatorial proof of this simple relation.

## 6 Weighted enumeration

There are some interesting results in the literature on weighted enumeration of ASMs. Here one assigns to each ASM of order $`n`$ some weight, and tries to compute the sum of the weights of all the ASMs of order $`n`$. A priori it might be unclear why this would be interesting, but with certain weighting schemes one gets beautiful (and mysterious) formulas, which are their own justification.

For instance, following , one can assign weight $`x^k`$ to every ASM that contains exactly $`k`$ entries equal to $`1`$. What is the sum of the weights of the ASMs of order $`n`$? When $`x=1`$, this is nothing other than ordinary enumeration of ASMs. When $`x=2`$, there is a very nice answer : the sum of the weights is exactly $`2^{n(n1)/2}`$. When $`x=3`$, the answer is more complicated, but it is roughly similar in type to the formula for the case $`x=1`$, and roughly similar in difficulty; the “3-enumeration” formula was first conjectured by Mills, Robbins and Rumsey  and was eventually proved by Kuperberg  (with corrections provided by Robin Chapman). No other positive integer $`x`$ seems to give nice answers. One can also assign weight $`x^k`$ to every ASM that contains exactly $`k`$ entries equal to $`+1`$, but this is essentially the same weighting scheme, since in any ASM of order $`n`$, the number of $`+1`$’s is always $`n`$ plus the number of $`1`$’s.

More interestingly, one can also use a hybrid weighting scheme in which the exponent of $`x`$ is equal to the number of entries $`a_{i,j}`$ such that *either* $`i+j`$ is even and $`a_{i,j}=1`$ *or* $`i+j`$ is odd and $`a_{i,j}=+1`$. When $`x=2`$, this too leads to an interesting result: the sum of the weights is always a power of two times a power of five!

One can come up with many open problems by combining the ideas of this section and the previous section. Here is one example: Each way of filling in Figure 13 (with the $`c_i`$’s now permitted to vary freely) gives rise to a “half-ASM”. For instance, the filling

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

of Figure 12 gives rise to the half-ASM

$$\begin{array}{cccccc}\hfill 0& \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 0& \hfill 0& \hfill 1& \hfill +1\end{array}$$

which has a single $`1`$. If we assign each rectangular array that arises in this way a weight equal to 2 to the power of the number of $`1`$’s, we get $`2^{n^2}`$ (Robin Chapman and Theresia Eisenkölbl have independently found nice proofs of this). On the other hand, suppose we now permit every entry in the bottom row of Figure 13 to vary freely (aside from the $`n`$ on the left and the $`n`$ on the right). When we 2-enumerate half-ASMs of this sort, as a function of $`n`$, we get the following sequence of numbers: $`2`$, $`20=2^25`$, $`896=2^77`$, $`177408=2^83^2711`$, $`154632192=2^{15}311^213`$, $`592344383488=2^{17}11^213^317`$, $`\mathrm{}`$. Clearly the absence of larger prime factors indicates that there is some nice product formula governing these numbers. Can someone find the right conjecture? Can someone prove it? (For more data of this kind, see:

http://www.math.wisc.edu/$``$propp/half-asm

Late-breaking news: Theresia Eisenkölbl  has made progress with the data-set and proved a number of theorems about half-ASMs.)

## 7 Full packings of loops

Given an ice state of order $`n`$, we can form a subgraph of the underlying tic-tac-toe graph by selecting precisely those edges that are oriented so as to point from an odd vertex to an even vertex, where we have assigned parities to vertices so that each odd vertex has only even vertices as neighbors and vice versa. Then one gets a subgraph of the tic-tac-toe graph such that each of the $`n^2`$ internal vertices lies on exactly 2 of the selected edges, and the $`4n`$ external vertices, taken in cyclical order, alternate between lying on a selected edge and not lying on a selected edge. Moreover, every such subgraph arises from an ice state in this way.

Let us say that the leftmost vertex in the top row of external vertices is even. Figure 14 shows the seven subgraphs that result from applying the transformation to the seven ice states of order 3.

Figure 14: The seven FPL states of order 3.

Leaving aside the behavior at the boundary, these are states of what physicists call the fully packed loop (FPL) model on the square grid (see e.g. ). I sometimes prefer to call such states “near 2-factors” since nearly all of the vertices in these subgraphs have degree 2; only the external vertices have smaller degree (specifically, they alternate between having degree 0 and having degree 1).

If one starts from an external vertex, there is a unique path that one can follow using edges in the subgraph; this path must eventually lead to one of the other external vertices. In addition to these paths (“open loops”), the edges of the subgraph can also form closed loops (see Figure 15, for example).

Note that these loops (both open and closed) cannot cross one another. In particular, the open loops must join up the $`2n`$ external edges in some non-crossing fashion. If one numbers the vertices of degree 1 in cyclic order from 1 to $`2n`$, the FPL state yields a pairing of odd-indexed external vertices with even-indexed external vertices. For instance, the FPL state shown in Figure 15 links 1 with 12, 2 with 11, 3 with 4, 5 with 6, 7 with 8, and 9 with 10.

Figure 15: A fully packed loop state of order 6.

It has been conjectured, on the strength of numerical evidence, that the number of ASMs of order $`n`$ in which the open paths link 1 with 2, 3 with 4, …, and $`2n1`$ with $`2n`$ is exactly the total number of ASMs of order $`n1`$.

We do not have a proof of this, but curiously, we have a proof of something else: that the number of FPL states of order $`n`$ in which the open paths link 1 with 2, 3 with 4, …, and $`2n1`$ with $`2n`$ is equal to the number of FPL states of order $`n`$ in which the open paths link 1 with $`2n`$, 2 with 3, 4 with 5, …, and $`2n2`$ with $`2n1`$. Note that when $`n`$ is divisible by 4, the geometries of the two linking-patterns is different, with respect to the tic-tac-toe graph. Yet the number of FPL states is the same.

This is a special case of a far more general fact proved by Wieland . For any two non-crossing pairings $`\pi `$ and $`\pi ^{}`$ of the numbers 1 through $`2n`$ (viewed as equally spaced points on a circle), if $`\pi `$ and $`\pi ^{}`$ are conjugate via a rotation or reflection, then (if we now treat the numbers 1 through $`2n`$ as the labels of vertices of degree 1 in the tic-tac-toe graph of order $`n`$) the number of FPL states with linking-pattern $`\pi `$ equals the number of FPL states with linking-pattern $`\pi ^{}`$. It is as if the tic-tac-toe graph, in some mystical sense, had an automorphism sending 1 to 2, 2 to 3, etc.

One might also ask for the number of FPL states of order $`n`$ in which 1 is linked with 2 (ignoring all the other linking going on). Here too we have a conjectural answer, due to David Wilson: the number of such FPL states is just the total number of FPL states of order $`n`$ multiplied by

$$\frac{3}{2}\frac{n^2+1}{4n^21}.$$

This would imply, in particular, that as $`n`$ goes to infinity, the probability that a randomly chosen FPL state links 1 with 2 is asymptotically $`3/8`$.

For a very recent discussion of the FPL model, see . In this article, Razumov and Stroganov point out that the FPL model is closely related to a seemingly quite different lattice model.

It is worth pointing out that these conjectures are truly native to the FPL incarnation of ASMs; it is hard to see how they could have arisen from one of the other models. So, even though the transformation between ASMs and FPL states is fairly shallow mathematically, some interesting questions can arise from it that might not otherwise have been noticed. Likewise, the passage between square-ice states and ASMs is not conceptually deep, but it made possible the shortest known solution of the ASM problem by putting the problem into a form where known methods from the physics literature could be applied. Hence a good subtitle for this paper might have been “The non-trivial power of trivial transformations”.

## 8 Numerology

As far as I know, the first manifestation of the sequence 1,2,7,42,429,7436,…occurred in connection with combinatorial objects called descending plane partitions or DPPs . Another manifestation was totally symmetric self-complementary plane-partitions (TSSCPPs) . Andrews discovered the proofs of both these formulas. Indeed, it was Andrews’ proof of the 1,2,7,42,…formula for TSSCPPs that galvanized Zeilberger into tackling the ASM conjecture. Zeilberger showed that ASMs are equinumerous with TSSCPPs. However, his proof was not bijective, and to this day nobody knows of a good bijection between ASMs of order $`n`$ and TSSCPPs of order $`n`$.

Another context in which these numbers arise is the study of the XXZ model in statistical mechanics  .

A different context in which numbers related to ASMs have occurred is certain “number walls” investigated by Somos . (Number walls are arrays of Hankel determinants, arranged so as to faciliate calculations of successively larger ones; see  for details.) In Somos’ examples it is not the sequence 1,2,7,42,…that crops up, but sequences that enumerate various sorts of symmetric ASMs. Xin  has found a Hankel determinant theorem that involves the sequence $`1,2,7,42,\mathrm{}`$ itself: he has shown that for all $`n`$, the determinant of the $`n`$-by-$`n`$ matrix whose $`i,j`$th entry is equal to the coefficient of $`x^{i+j2}`$ in the Taylor expansion of the generalized Catalan generating function $`\frac{1(19x)^{1/3}}{3x}`$  is equal to

$$3^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}$$

times the number of $`n`$-by-$`n`$ alternating-sign matrices.

It would be desirable to have some sort of understanding of why the number of ASMs of order $`n`$ (with or without symmetry-constraints) turns up in these seemingly disparate situations.

## 9 Large random ASMs

Another sort of phenomenon associated with ASMs of order $`n`$ is their typical “shape” when $`n`$ is large. I remarked above that the ASMs of order $`n`$ form a distributive lattice; consequently, the method of “coupling from the past” can be applied  for the purpose of generating a random ASM of fixed order governed by the uniform distribution. Figure 16 shows a random ASM of order 40, represented as a gaskets-and-baskets tiling (where an attempt has been made to give each of the six tile-types its own distinctive shading).

Note that the gaskets (which correspond to the non-zero entries of the ASM) stay away from the corners. Computer experiments strongly indicate that this is typical behavior: the probability of finding a non-zero entry close to one of the corners appears to be quite small. Another way of expressing this is in terms of the entries $`h_{i,j}`$ of the height-function matrix. Say that a location $`(i,j)`$ in a particular height-function matrix of order $`n`$ is *frozen* if the height there is equal to either the maximum possible height that any height-function matrix of order $`n`$ can exhibit at that location or the minimum possible height that any height-function matrix of order $`n`$ can exhibit at that location. Then the claim is that a significant portion of the height-function matrix, concentrated in the four corners, tends to be frozen.

This is analogous to phenomena that have been observed for other sorts of combinatorial models. Indeed, if one adopt a non-uniform distribution on the set of ASMs of order $`n`$, where the probability associated with an ASM containing exactly $`k`$ entries equal to $`1`$ is proportional to $`2^k`$, then it is rigorously known that the frozen region tend in probability to a perfect circular disk  . However, it is not known that this holds when the uniform distribution on ASMs is used.

## 10 Back to Dodgson

I conclude this article by coming full circle and returning the context in which ASMs first came to light: the study of Dodgson’s condensation algorithm and its variants. I will not discuss Dodgson’s algorithm per se, but rather a variation of it invented by Robbins and Rumsey . This modified form of Dodgson condensation is an algebraic recurrence relation

$$f_{i,j,k+1}=(f_{i+1,j,k}f_{i1,j,k}+f_{i,j+1,k}f_{i,j1,k})/f_{i,j,k1}$$

satisfied by certain functions $`f:𝐙^3𝐑`$. (Note that this equation can be written slightly more symmetrically as

$$f_{i,j,k+1}f_{i,j,k1}f_{i+1,j,k}f_{i1,j,k}f_{i,j+1,k}f_{i,j1,k}=0.$$

Physicists and researchers in the field of integrable systems call this a discrete Hirota equation, and have developed a great deal of theory associated with it; however, the observations I make here seem to be currently unknown outside of a small circle of algebraic combinatorialists.) If we let $`f_{i,j,1}=x_{i,j}`$ and $`f_{i,j,0}=y_{i,j}`$ for formal indeterminates $`x_{i,j},y_{i,j}`$ (with $`(i,j)`$ ranging over $`𝐙^2`$), then the recurrence relation lets us express all the $`f_{i,j,k}`$’s in terms of the $`x_{i,j}`$’s and $`y_{i,j}`$’s, at least formally. A priori, one expects each $`f_{i,j,k}`$ to be a rational function of the $`x`$ and $`y`$ variables; the surprise (the first of several surprises, in fact) is that these rational functions are actually Laurent polynomials (that is, they are polynomials functions of the $`x`$ and $`y`$ variables along with their reciprocals).

This observation seems to have first been made by Mills, Robbins and Rumsey, who actually considered a more general recurrence

$$f_{i,j,k+1}=(f_{i+1,j,k}f_{i1,j,k}+\lambda f_{i,j+1,k}f_{i,j1,k})/f_{i,j,k1}.$$

The case $`\lambda =1`$ corresponds to the original Dodgson algorithm, but Mills et al. noticed that the same surprising cancellation occurs for more general values of $`\lambda `$, including the especially nice case $`\lambda =1`$, and that one always obtains Laurent polynomials.

It was from studying these Laurent polynomials that Mills, Robbins and Rumsey were led to discover alternating-sign matrices. Every term in one of these Laurent polynomials has a coefficient equal to 1 (that is the second surprise), and is a product of powers of a finite number of $`x`$ and $`y`$ variables. The third surprise is that all the exponents of the variables are $`+1`$, $`1`$, and $`0`$. The fourth and final surprise is that these patterns of exponents encode ASMs. More specifically, the exponents of the $`x`$ variables (after a global sign flip) encode one ASM, and the exponents of the $`y`$ variables encode another. These two ASMs satisfy a combinatorial relationship that the researchers dubbed “compatibility”. They showed that the number of compatible pairs of ASMs is exactly $`2^{n(n+1)/2}`$.

As it happens, this formula is not hard to verify as a consequence of the other claims I have made. If indeed all the coefficients in the Laurent polynomial equal 1, then one can count the terms (and thereby count the compatible pairs of ASMs) just by setting all the $`x`$ and $`y`$ variables equal to 1. But in this case, $`f_{i,j,k}`$ depends only on $`k`$ (call it $`F_k`$), and the three-dimensional recurrence boils down to the one-dimensional recurrence

$$F_{k+1}=(F_kF_k+F_kF_k)/F_{k1}$$

with initial conditions $`F_0=F_1=1`$, which is readily solved.

The terms of these Laurent polynomials were originally understood in terms of compatible pairs of ASMs. A few years after this work was done, it turned out that compatible pairs of ASMs admit a much more geometrical representation, namely, as tilings of regions called Aztec diamonds by means of tiles called dominos (1-by-2 and 2-by-1 rectangles). See  for more details.

I will close by pointing out that a kindred recurrence relation cries out to be studied, namely

$$f_{i,j,k}=(f_{i1,j,k}f_{i,j1,k1}+f_{i,j1,k}f_{i1,j,k1}+f_{i,j,k1}f_{i1,j1,k})/f_{i1,j1,k1},$$

with initial conditions

$$f_{i,j,k}=\{\begin{array}{cc}x_{i,j,k}\hfill & \text{if }i+j+k=1,\hfill \\ y_{i,j,k}\hfill & \text{if }i+j+k=0,\hfill \\ z_{i,j,k}\hfill & \text{if }i+j+k=+1.\hfill \end{array}$$

Here (just as in the Mills, Robbins, and Rumsey recurrence) one finds empirically that each value of $`f_{i,j,k}`$ is expressible as a Laurent polynomial in the $`x`$, $`y`$, and $`z`$ variables (in fact, shortly before this article went to press, this Laurent property was proved by Fomin and Zelevinsky); here too one finds empirically that each coefficient in these Laurent polynomials is equal to 1; and here too one finds that the exponents of the $`x`$, $`y`$ and $`z`$ variables that occur in the Laurent monomials are universally bounded (in this case between $`1`$ and $`+4`$ rather than between $`1`$ and $`+1`$). If all this is true, then the exponent-patterns that arise are some sort of analogue of compatible pairs of ASMs, and moreover, we know exactly how many there are: $`3^{n^2/4}`$. (This comes from reducing the original three-dimensional recurrence to a one-dimensional recurrence, as we did before.) So, assuming that our empirical observations are not leading us astray, there is some new kind of combinatorial gadget that governs these Laurent polynomials (or vice versa!), and we know exactly how many gadgets of order $`n`$ there are. And it is easy to generate these Laurent polynomials (and with them the gadgets) using Maple, e.g. with the following short program:

```
f := proc (i,j,k)
        if   (i+j+k < 3) then x(i,j,k) else
        simplify(
        ( f(i-1,j,k)*f(i,j-1,k-1)+
          f(i,j-1,k)*f(i-1,j,k-1)+
          f(i,j,k-1)*f(i-1,j-1,k) )
        /f(i-1,j-1,k-1));
        fi; end;

```

Nonetheless, we do not know what these gadgets are, combinatorially! They are analogous to pairs of compatible ASMs, which in turn are equivalent to domino tilings of Aztec diamonds, so one hopes that the gadgets have some intuitive geometric meaning. For more information about the properties of these gadgets, see http://www.math.wisc.edu/$``$propp/cube-recur.

More late-breaking news: Harvard undergraduates Gabriel Carroll and David Speyer solved this problem in 2002, as participants in the Research Experiences in Algebraic Combinatorics at Harvard program. More details will at some point become available through links at the REACH web-site:

http://www.math.harvard.edu/$``$propp/reach/.