format: text

text:
# Theorem 1.

A Note on Planar and Dismantlable Lattices

Karen L. Collins

Dept. of Mathematics, Wesleyan University

Middletown, CT 06459-0128

## Abstract.

It is shown that any finite, rank-connected, dismantlable lattice is lexicographically shellable (hence Cohen-Macaulay). A ranked, interval-connected lattice is shown to be rank-connected, but a rank-connected lattice need not be interval-connected. An example of a planar, rank-connected lattice that is not admissible is given.

Keywords: dismantlable, lexicographically shellable, Cohen–Macaulay, planar, lattice.

All lattices are assumed to be finite. Björner  has shown that a dismantlable (see Rival, ) lattice $`L`$ is Cohen-Macaulay (see  for definition) if and only if $`L`$ is ranked and interval-connected. A lattice is planar if its Hasse diagram can be drawn in the plane with no edges crossing. Baker, Fishburn and Roberts have shown that planar lattices are dismantlable, see . Lexicographically shellable lattices are Cohen-Macaulay, see . In a recent paper, , the author proved that a planar lattice $`L`$ is lexicographically shellable if and only if $`L`$ is rank-connected.

We prove a conjecture of Björner that a dismantlable, rank-connected lattice is lexicographically shellable. We also show that an ranked and interval-connected lattice must be rank-connected. Hence, if $`L`$ is a dismantlable lattice, $`L`$ ranked and is interval-connected if and only if $`L`$ is rank-connected. However, a rank-connected lattice need not be interval-connected. Figure 1(a) is a rank-connected lattice that is neither interval-connected nor planar. Not every dismantlable lattice is planar, see, for instance, Figure 1(d).

In  it was conjectured that planar, rank-connected lattices are admissible (see Stanley, ). However, Figure 1(b) is a counterexample to that conjecture. Figure 1(c) is a planar, rank-connected lattice that is neither upper nor lower semi-modular.

A lattice must have a least element $`\widehat{0}`$, and a greatest element $`\widehat{1}`$. A lattice that contains only a least element and a greatest element is trivial. A lattice is ranked if every maximal chain from $`\widehat{0}`$ to $`\widehat{1}`$ has the same length. For element $`x`$, $`r(x)`$ is defined to be the length of a maximal chain from the least element to $`x`$. Let $`R_i`$ be the set of elements of rank $`i`$. A lattice is rank-connected if it is ranked and the subgraph of the Hasse diagram induced by $`R_i`$ and $`R_{i+1}`$ forms a connected graph for all $`0i<r(\widehat{1})`$.

An element in a lattice is said to be join-irreducible if it covers exactly one element, and meet-irreducible if it is covered by exactly one element. An element that is both join- and meet-irreducible is said to be doubly irreducible. A lattice $`L`$ is dismantlable if there is a chain $`L_1L_2\mathrm{}L_n=L`$ of sublattices of $`L`$ such that the lattice $`L_i`$ has $`i`$ elements for $`1in`$. Each single element in $`L_kL_{k1}`$ is doubly irreducible in $`L_k`$. Equivalently, a lattice is dismantlable if and only if every non-trivial sublattice has a doubly irreducible element, see .

Let $`L`$ be a ranked lattice. Let $`C(L)`$ equal the set of covering relations of $`L`$. Then $`L`$ is lexicographically shellable if there exists a labeling $`f:C(L)𝐑`$ such that

1. in every interval $`[x,y]`$ of $`L`$ there is a unique unrefinable chain $`x=x_0<x_1<\mathrm{}<x_n=y`$ such that $`f(x_0,x_1)f(x_1,x_2)\mathrm{}f(x_{n1},x_n)`$.
2. for every interval $`[x,y]`$ of $`L`$, if $`x=x_0<x_1<\mathrm{}<x_n=y`$ is the unique unrefinable chain with rising labels, and if $`z[x,y]`$ covers $`x`$ with $`zx_1`$, then $`f(x,x_1)<f(x,z)`$.

###### Theorem 1.

Let $`L`$ be a rank-connected, dismantlable lattice. Then $`L`$ is lexicographically shellable.

###### Proof.

We prove this by induction. First, we make a reduction. Suppose that some rank other than the top and bottom rank contains a single vertex $`x`$. Then the lattices $`[\widehat{0},x],[x,\widehat{1}]`$ are dismantlable and rank-connected. Any lexicographic shelling of $`[\widehat{0},x]`$ and separately of $`[x,\widehat{1}]`$ will be a lexicographic shelling of $`L`$ as long as all labels in $`[x,\widehat{1}]`$ are greater than all labels of $`[\widehat{0},x]`$. By induction, therefore, we may assume that every rank except the very top and the very bottom contains at least two elements.

Since $`L`$ is dismantlable, every non-trivial sublattice of $`L`$ contains a doubly irreducible element. We show that the covers of doubly irreducible elements and the vertices covered by doubly irreducible elements cannot themselves be doubly irreducible. Let $`x`$ be doubly irreducible in $`L`$. Suppose $`r(x)=i`$. Let the unique vertex that $`x`$ covers be $`z`$ and the unique vertex that covers $`x`$ be $`y`$. Let $`G`$ be the induced bipartite graph of the Hasse diagram with vertices $`R_iR_{i+1}`$. Then both $`x`$ and $`y`$ are in $`G`$, and $`G`$ is a connected graph because $`L`$ is rank-connected. Since $`x`$ is doubly irreducible, $`x`$ is a degree 1 vertex in $`G`$, hence $`Gx`$ is still connected. Since $`R_i`$ contains at least two vertices, $`Gx`$ must contain $`y`$ and at least one vertex in $`R_i`$, hence $`y`$ has an edge to another vertex of rank $`i`$. Therefore $`y`$ (and similarly $`z`$) cannot be doubly irreducible in $`L`$.

For rest of the proof, we rely on the following definition and previous result. We say that $`w`$ is a corner of $`x`$ in $`L`$ if there exist $`z`$ and $`y`$ such that $`x,w`$ both cover $`z`$ and are covered by $`y`$, and $`x`$ is doubly irreducible. Theorem 1 of  guarantees that $`L`$ is lexicographically shellable if $`Lx`$ is lexicographically shellable. We prove that there must always exist a doubly irreducible element of $`L`$ that has a corner, hence $`L`$ is lexicographically shellable by induction.

Let the doubly irreducible vertices of $`L`$ be $`D:=\{x_1,x_2,x_3,\mathrm{},x_t\}`$. Suppose that no element of $`D`$ has a corner. Let $`x_j`$ cover $`z_j`$ and be covered by $`y_j`$ in $`L`$ for $`1jt`$. As seen before, rank connectedness guarantees that $`z_j`$ and $`y_j`$ are not doubly irreducible in $`L`$. Consider the relation $`z_jy_j`$ (which is true in $`L`$) in the sublattice $`LD`$. There must be a chain from $`z_j`$ to $`y_j`$ in $`LD`$.

However in $`L`$, the rank of $`z_j`$ and $`y_j`$ differs by exactly 2. Therefore, any chain between $`z_j`$ and $`y_j`$ in $`LD`$ must have length less than or equal to 2, since removing vertices cannot make chains longer. If the length of the chain is 2, then the middle vertex of the chain will be a corner of $`x_j`$. By our assumption, $`x_j`$ has no corners, hence $`y_j`$ must cover $`z_j`$ in $`LD`$.

Suppose that $`y_j`$ covers both $`x_j`$ and $`x_k`$ for some $`k`$. Now $`x_k`$ is not a corner of $`x_j`$, so $`z_jz_k`$. Therefore, $`y_j`$ covers both $`z_j`$ and $`z_k`$ in $`LD`$. Thus if element $`u`$ covers $`s`$ vertices in $`L`$, after removing the doubly irreducible vertices, $`u`$ still covers $`s`$ vertices in $`LD`$. Each doubly irreducible vertex $`x_j`$ is replaced by the unique vertex $`z_j`$ that it covers. Similarly, if element $`u`$ is covered by $`s`$ vertices in $`L`$, it is still covered by $`s`$ elements in $`LD`$.

Hence the sublattice $`LD`$ is composed entirely of elements that are not doubly irreducible. It is not empty, since $`L`$ must contain at least one doubly irreducible element $`x`$ and therefore contains both the unique element that covers and the unique element that is covered by $`x`$. Since $`L`$ is dismantlable, $`LD`$ must be the trivial lattice that contains only a top and bottom element. Thus, $`L`$ must have rank 2 and all its doubly irreducible elements have rank 1. Each of these rank 1 elements is a corner of every other, contradicting our assumption that no doubly irreducible element has a corner. ∎

Define $`[x,y]=\{z|xzy\}`$. A lattice is interval-connected if for every pair $`x,y`$ with $`r(y)2+r(x)`$ the Hasse diagram of $`[x,y]\{x,y\}`$ is connected.

###### Theorem 2.

Let $`L`$ be an interval-connected, ranked lattice. Then $`L`$ is rank-connected.

###### Proof.

Any sublattice $`[x,y]`$ of $`L`$ must be interval-connected. Assume by induction that every interval $`[x,y][\widehat{0},\widehat{1}]`$ is rank-connected. We will show that $`[\widehat{0},\widehat{1}]`$ is rank-connected.

Let $`\widehat{L}`$ be the subposet of $`L`$ that contains all vertices except $`\widehat{0},\widehat{1}`$. Let $`G`$ be the subgraph of the Hasse diagram induced by $`R_i`$ and $`R_{i+1}`$. Since $`L`$ is interval-connected, there must be some path between any two vertices in $`G`$ in $`\widehat{L}`$. Suppose that $`G`$ is not connected. Let $`u,v`$ be elements of $`G`$ such that $`u`$ and $`v`$ are not in the same connected component of $`G`$ and such that $`p(u,v)`$ is the shortest possible path between any two elements in different connected components of $`G`$ that is contained in $`\widehat{L}`$. Let $`P`$ be the set of vertices in $`p(u,v)\{u,v\}`$. Then $`P`$ does not intersect the vertices in $`G`$, so $`u,v`$ both have rank $`i`$ or both have rank $`i+1`$, and the rank of all vertices in $`P`$ must be less than $`i`$ or greater than $`i+1`$, respectively. Without loss of generality, assume that $`u,v`$ have rank $`i`$ and let $`a`$ be the last element of $`p(u,v)`$ that is strictly less than $`u`$.

We observe that if $`uv>\widehat{0}`$, then $`[uv,\widehat{1}]`$ is smaller than $`L`$, and therefore is rank-connected by induction. This means there is a path from $`u`$ to $`v`$ in $`G[uv,\widehat{1}]`$, which is clearly a path in $`G`$. Therefore we may assume that $`uv=\widehat{0}`$. Similarly, we can assume $`uv=\widehat{1}`$. Now $`a<u`$ and $`av`$ since $`r(v)=r(u)`$. Let $`b`$ be the next element after $`a`$ in $`p(u,v)`$. Then $`a`$ and $`b`$ are comparable, hence $`ba`$, since $`ub`$. If $`vba`$, then $`\widehat{0}=uva>\widehat{0}`$, a contradiction. So $`b`$ is incomparable to both $`u`$ and $`v`$.

There exists a path from $`b`$ to $`\widehat{1}`$ in $`L`$ that is strictly rank increasing. Let $`p(b,\widehat{1})`$ be such a path. Now $`r(b)=r(a)+1r(u)=i`$. Let $`b(i)`$ be the element on $`p(b,\widehat{1})`$ that has rank equal to $`i`$. Then $`b(i)ba`$ and $`ua`$ imply that $`b(i)ua>\widehat{0}`$. Therefore, $`b(i)`$ and $`u`$ must be in the same connected component of $`G`$.

If $`b(i)`$ is in the same connected component of $`G`$ as $`v`$, then by transitivity $`u`$ and $`v`$ are in the same component. If $`b(i)`$ and $`v`$ are in different components, then we replace the pair $`u`$ and $`v`$ by the pair $`b(i)`$ and $`v`$ and take a path from $`b(i)`$ to $`v`$ that consists of starting at $`b(i)`$ and following a strictly rank decreasing path to $`b`$ and then following the portion of $`p(u,v)`$ from $`b`$ to $`v`$. This must be a shorter path than $`p(u,v)`$ between a rank $`i`$ element and a rank $`i+1`$ element in different connected components of $`G`$, because the portion of $`p(u,v)`$ from $`u`$ to $`b`$ goes through $`a`$ and is therefore longer than the strictly rank decreasing path from $`b(i)`$ to $`b`$. We bypass $`a`$, and $`a`$ has lower rank than $`b`$. This contradicts the selection of $`p(u,v)`$ as the shortest possible path. ∎

Admissible lattices are lexicographically shellable, but not all lexicographically shellable lattices are admissible. See Stanley’s paper for details . We define admissible lattices and show that there is a planar, rank-connected lattice which is lexicographically shellable, but not admissible. Let $`J`$ be the set of join-irreducibles of a lattice. Define a natural labeling $`\omega `$ of $`J`$ to be a map $`\omega :J𝐍`$ where $`𝐍`$ is the positive integers such that if $`z,wJ`$ and $`zw`$, then $`\omega (z)\omega (w)`$. Let $`\gamma `$ be derived from $`\omega `$ by $`\gamma (x<y)=min\{\omega (z)|zJ,x<xzy\}`$. A lattice $`L`$ is admissible if whenever $`x<y`$ in $`L`$, there is a unique unrefinable chain $`x=x_0<x_1<\mathrm{}<x_m=y`$ such that $`\gamma (x_0,x_1)\gamma (x_1,x_2)\mathrm{}\gamma (x_{m1},x_m)`$.

The planar, rank-connected lattice in Figure 1(b) is lexicographically shellable, but it is not admissible. Label the vertices with $`0`$ to $`11`$ starting at the lowest rank and moving left to right. Then the join irreducibles are $`1,2,3,4,6,7`$. Suppose we have an admissible labeling of the poset. Then $`\omega (3),\omega (4)\omega (1)`$, hence $`\gamma (10<11)=\omega (1)`$. Clearly $`\gamma (7<10)=\omega (6)`$. Since there is a unique chain from $`7`$ to $`11`$, it must be rising and $`\omega (6)\omega (1)\omega (4)`$. By left-right symmetry, $`\omega (4)\omega (2)\omega (6)`$. Thus $`\omega (1)=\omega (2)`$, which cannot happen, since the two chains from $`0`$ to $`5`$ will then both be rising.

The author would like to thank the referees for their helpful suggestions.


text:
# 1 Introduction

## 1 Introduction

Conley’s homotopy index has proved to be a useful tool in critical point theory. In most of the applications of critical point theory, we deal with a $`C^1`$-function on a complete Finsler manifold satisfying Palais-smale condition and we desire to estimate the number of critical points of such a function. There are two different viewpoints: the number of analytically distinct critical points which is discussed by Morse theory and the number of geometrically distinct critical points which is investigated by Lusternik-Schnirelmann theory . The applications of Conley index in Morse theory has been studied in details . This paper is concerned with the applications in Lusternik-Schnirelmann theory. (See also .) We consider the flow relative to a pseudo-gradient vector field for a $`C^1`$-function on a complete Finsler manifold satisfying Palais-Smale condition. Then we prove the deformation results for index pairs in the sense of Conley index theory for such a flow. Using a modification of the relative Lusternik-Schnirelmann category, we obtain a Lusternik-Schnirelmann type result in Conley index theory.

We need some basic results from Conley index theory which are presented in Section 2. Here we have extended the concept of regular index pair  for the noncompact case. Then in Section 3, we define the concept of relative Lusternik-Schnirelmann category with a little modification so that it can be applied to index pairs and yield sharper results in critical point theory. Finally in Section 4, we prove our result concerning the existence of critical points for a $`C^1`$-function on a complete Finsler manifold.

## 2 Index Pair

Let $`\phi ^t`$ be a continuous flow on a metric space $`X`$. An isolated invariant set is a subset $`IX`$ which is the maximal invariant subset in a closed neighborhood of itself. such a neighborhood is called an isolating neighborhood. In order to define the concept of index pair, we follow  and .

Given a closed pair $`(N,L)`$ in $`X`$, we define the induced semi-flow on $`N/L`$ by

$$\phi _{\mathrm{}}^t:N/LN/L,\phi _{\mathrm{}}^t(x)=\{\begin{array}{cc}\phi ^t(x)\hfill & \text{if}\phi ^{[0,t]}(x)NL\hfill \\ \left[L\right]\hfill & \text{otherwise.}\hfill \end{array}$$

In  it is proved that $`\phi _{\mathrm{}}:N/L\times ^+N/L`$ is continuous if and only if

* $`L`$ is positively invariant relative to $`N`$, i.e.

$$xL,t0,\phi ^{[0,t]}(x)N\phi ^{[0,t]}(x)L.$$
* Every orbit which exits $`N`$ goes through $`L`$ first, i.e.

$$xN,\phi ^{[0,\mathrm{})}(x)N_{t0}\text{with}\phi ^{[0,t]}(x)N,\phi ^t(x)L,$$

or equivalently if $`xNL`$ then there is a $`t>0`$ such that $`\phi ^{[0,t]}(x)N`$.

### Definition.

An index pair for an isolated invariant set $`IX`$ is a closed pair $`(N,L)`$ in $`X`$ such that $`\overline{NL}`$ is an isolating neighborhood for $`I`$ and the semi-flow $`\phi _{\mathrm{}}^t`$ induced by $`\phi ^t`$ is continuous.

For every subset $`AX`$ and $`T^+`$, we define

$$\begin{array}{c}G^T(A)=\{xA|\phi ^{[T,T]}(x)A\},\hfill \\ \mathrm{\Gamma }^T(A)=\{xG^T(A)|\phi ^{[0,T]}(x)A\mathrm{}\}.\hfill \end{array}$$

Now suppose that $`G^T(A)int(A)`$ for a closed subset $`AX`$. Then $`A`$ is an isolating neighborhood for $`I:=_{T>0}G^T(A)`$. In , Benci proved that $`(G^T(A),\mathrm{\Gamma }^T(A))`$ is an index pair for $`I`$. This index pair has a special property, that is for every $`x\mathrm{\Gamma }^T(A)`$, $`\phi ^{[0,3T]}(x)G^T(A)`$. To see this, suppose that $`\phi ^{[0,3T]}G^T(A)`$, then $`\phi ^{[T,4T]}(x)A`$, hence $`\phi ^{[T,2T]}(x)G^{2T}(A)int(G^T(A))`$. So $`\phi ^T(x)\mathrm{\Gamma }^T(A)`$ and by (i), $`x\mathrm{\Gamma }^T(A)`$.

### Definition.

An index pair $`(N,L)`$ is called regular if the exit time map

$$\tau _+:N[0,+\mathrm{}],\tau _+(x)=\{\begin{array}{cc}sup\{t|\phi ^{[0,t]}(x)NL\}\hfill & \text{if}xNL,\hfill \\ 0\hfill & \text{if}xL,\hfill \end{array}$$

is continuous. For every regular index pair $`(N,L)`$, we define the induced semi-flow on $`N`$ by

$$\phi _{\mathrm{}}^t:N\times ^+N,\phi _{\mathrm{}}^t(x)=\phi ^{min\{t,\tau _+(x)\}}(x)$$

The reader is referred to  to see the details about regular index pairs and the proof of the following useful criterion.

### Proposition 2.1.

An index pair $`(N,L)`$ is regular provided that $`\phi ^{[0,t]}(x)\overline{NL}`$ for every $`xL`$ and $`t>0`$.

### Definition.

An index pair $`(N,L)`$ is called weakly regular if for every $`xL`$, there exists $`t^+`$ such that $`\phi ^t(x)\overline{NL}`$.

We showed that if $`G^T(A)int(A)`$ for a closed subset $`AX`$, then $`(G^T(A),\mathrm{\Gamma }^T(A))`$ is a weakly regular index pair. Now let $`(N,L)`$ be an index pair and $`V:=\overline{NL}`$. We define $`I^+(V)=\{xV|\phi ^{[0,+\mathrm{})}(x)V\}`$. It is not hard to see that $`I^+(V)`$ is closed subset of $`V`$. Notice that if $`(N,L)`$ is a weakly regular index pair, then $`I^+(V)L=\mathrm{}`$. The following theorem asserts that there is a Lyapunov function for $`\phi _{\mathrm{}}^t`$ on $`N/L`$ which separates $`[L]`$ and $`I^+(V)`$. If we consider the natural projection $`\pi :NN/L`$, then we obtain a Lyapunov function on $`N`$ which separates $`L`$ and $`I^+(V)`$. (See  for a similar result in the compact case.)

### Theorem 2.2.

Let $`(N,L)`$ be a weakly regular index pair and $`V=\overline{NL}`$. Then there exists a continuous function $`g:N/L[0,1]`$ such that

* $`g^1(0)=[L]`$ and $`g^1(1)=I^+(V)`$.
* If $`0<g(x)<1`$ and $`t^+`$, then $`g(\phi _{\mathrm{}}^t(x))<g(x)`$.

Proof. Let $`\rho :N/L[0,1]`$ be a continuous function with $`\rho ^1(0)=[L]`$ and $`\rho ^1(1)=I^+(V)`$. We define $`f:N/L[0,1]`$ by $`f(x)=\underset{t0}{sup}\rho (\phi _{\mathrm{}}^t(x))`$. Then $`f^1(0)=[L],f^1(1)=I^+(V)`$ and $`f(\phi _{\mathrm{}}^t(x))f(x)`$ for every $`xN/L`$. Moreover it is not hand to check that $`f`$ is continuous in $`I^+(V)`$. Now suppose that $`0<f(x)<1`$ for some $`xNL`$. Then there is $`t_0^+`$ such that $`\phi ^{t_0}(x)L`$. Since $`(N,L)`$ is a weakly regular index pair there is a $`t_1^+`$ such that $`\phi ^{t_0+t_1}V`$. Thus there is a neighborhood $`A`$ of $`x`$ such that $`\phi ^{t_0+t_1}(A)V=\mathrm{}`$ which means that $`\phi _{\mathrm{}}^{t_0+t_1}(A)=[L]`$. Therefore $`\underset{t0}{sup}\rho (\phi _{\mathrm{}}^t(y))=\underset{0tt_0+t_1}{sup}\rho (\phi _{\mathrm{}}^t(y))`$ for every $`xA`$, hence $`f`$ is continuous at $`x`$. It remains to show the continuity of $`f`$ at $`[L]`$. Let $`\epsilon `$ be a given positive number. For every $`xL`$, there is a $`t^+`$ such that $`\phi ^t(x)V`$. Thus there exists a neighborhood $`U_x`$ of $`x`$ such that $`\rho (\phi _{\mathrm{}}^{[0,t]}(U_x))<\epsilon `$ and $`\phi ^t(U_x)V=\mathrm{}`$. If we set $`U=_{xL}U_x`$, then $`U`$ is a neighborhood of \[L\] in $`N/L`$ with $`\rho (\phi _{\mathrm{}}^{[0,+\mathrm{})}(U))<\epsilon `$, hence $`f|_U<\epsilon `$. The above argument shows that $`f`$ is continuous. Now it is not hand to check that $`g:=_0^+\mathrm{}e^tf(\phi _{\mathrm{}}^t(x))𝑑t`$ is the desired function . $`\mathrm{}`$

### Corollary 2.3.

Let $`(N,L)`$ be a weakly regular index pair for an isolated invariant set $`I`$. Then there exists a subset $`L^{}N`$ such that $`LL^{}`$ and $`(N,L^{})`$ is a regular index pair for $`I`$ .
Proof. Let $`g:N/L[0,1]`$ be the Lyapunov function described above. Take $`L^{}:=\pi ^1(g^1[0,\epsilon ])`$ where $`\pi :NN/L`$ is the natural projection and $`\epsilon (0,1)`$. Now by Proposition 2.1., $`(N,L^{})`$ is a regular index pair for $`I`$. $`\mathrm{}`$

## 3 Relative Category

The relative Lusternik-Schnirelmann category introduced by Fadell and Husseini  has shown to give important information about the existence of critical points . For every topological space $`X`$ and a closed subset $`AX`$, the relative category cat $`(X,A)`$ is defined to be the minimum $`n`$ for which there exists an open cover $`X=U_0\mathrm{}U_n`$ such that $`U_0`$ can be retracted to $`A`$ and $`U_i`$ is contractible in $`X`$ for $`1in`$. Unfortunately this definition is not so efficient in Conley index theory. Indeed in this theory we deal with a pair in the form of $`(N/L,[L])`$ where $`(N,L)`$ is an index pair for a continuous flow. Now one can see that if $`L`$ is a large subset of $`N`$, then $`cat(N/L,[L])`$ is possibly a small number. Since the relative category is used to find a lower bound for the number of critical points, we can not obtain good estimates in critical point theory. (See .) For this reason, we use a little modification of the relative category which is more efficient in Conley index theory.

### Definition.

(Relative HLS category) Let $`X`$ be a topological space and $`AX`$ be a closed subset. The relative Homotopy Lusternik-Schnirelmann category $`\nu _H(X,A)`$ is defined to be the minimum of $`n`$ for which there exists an open covering $`X=U_0\mathrm{}U_n`$ such that $`A`$ is a deformation retract of $`U_0`$ and $`U_i`$ is contractible in $`XA`$ for $`1in`$.

It is easy to see that $`\nu _H(X,A)cat(X,A)`$. Unfortunately the relative category is not easy to compute. It is more convenient to use cohomological category  to find lower bounds for it. (See  and references therein for other tools.) Suppose that $`H^{}`$ is a cohomology functor on $`X`$. A subset $`SX`$ is called cohomologically trivial if the restriction map $`H^k(X)H^k(S)`$ is zero for every $`k`$. Similarly for $`ASX`$, we say that $`(S,A)`$ is cohomologically trivial in $`(X,A)`$ if the restriction map $`H^k(X,A)H^k(S,A)`$ is zero for every $`k`$.

### Definition.

(Relative CLS category) The relative Cohomology Ljusternik-Schnirelmann category $`\nu _C(X,A)`$ is defined to be the minimum $`n`$ for which there is an open covering $`U_0,\mathrm{},U_n`$ such that $`AU_0`$ and $`(U_0,A)`$ is cohomologically trivial in $`(X,A)`$ and $`U_iXA`$ is cohomologically trivial in $`XA`$ for $`1in`$. If such a covering does not exist, we set $`\nu _C(X,A)=+\mathrm{}`$. When $`A=\mathrm{}`$, then $`\nu _C(X):=\nu _C(X,\mathrm{})`$ is called CLS category.

Recall that the cuplenth of a topological space $`X`$ is defined to be the minimum integer $`N>0`$ such that for any set of cohomology classes $`\alpha _jH^{k_j}(M)`$, $`j=1,\mathrm{},N`$ of degree $`k_j1`$, the class $`(\alpha _1\mathrm{}\alpha _N)|_A=j^{}(\alpha _1\mathrm{}\alpha _N)`$ is zero. It is well-known that $`\nu _C(X)cuplength(X)`$. (cf. .) Now we introduce the concept of relative cuplength which gives a lower bound for the relative CLS category.

### Definition.

(Relative Cuplength) For $`AX`$, we define the relative cuplength $`CL(X,A)`$ to be the minimum integer $`N>0`$ such that for any set of cohomology classes $`\alpha _jH^{k_j}(X)`$, $`j=1,\mathrm{},N`$ and $`\alpha _0H^{k_0}(X,A)`$ of degree $`k_j>0`$, the class $`(\alpha _0\alpha _1\mathrm{}\alpha _N)`$ is zero in $`H^{}(X,A)`$.

### Proposition 3.1.

$`\nu _C(X,A)CL(X,A)`$.
Proof. Let $`U`$ and $`V`$ be open subsets of $`X`$ with $`AV`$. Suppose that $`\alpha H^{}(X,A)`$ and $`\beta H^{}(X)`$ such that $`\alpha |_V=0`$ in $`H^{}(V,A)`$ and $`\beta |_U=0`$ in $`H^{}(U)`$. Since $`U`$ and $`V`$ are excisive subsets of $`X`$, the cup product map $`H^{}(X,V)H^{}(X,U)H^{}(X,VU)`$ is defined  and the following diagram is commutative with exact columns:

$$\begin{array}{ccccc}H^{}(X,V)& & H^{}(X,U)& & H^{}(X,VU)\\ & & & & \\ H^{}(X,A)& & H^{}(X)& & H^{}(X,A)\\ & & & & \\ H^{}(V,A)& & H^{}(U)& & H^{}(VU,A)\end{array}$$

A diagram chase shows that $`(\alpha \beta )=0`$ in $`H^{}(VU,A)`$. Now the proposition is obvious by induction. $`\mathrm{}`$

### Example 3.2.

Let $`\pi :EB`$ be an $`m`$-dimensional orientable vector bundle over a metric space $`B`$. Then $`E`$ admits a Euclidean metric and we may consider the disk bundle $`D(E)`$ and sphere bundle $`S(E)`$. Using the Thom isomorphism, we conclude that $`CL(D(E)/S(E),[S(E)])=CL(D(E),S(E))=cuplength(M)`$. (See  for the details.)

## 4 Critical Point Theory

Let $`X`$ be a complete Finsler manifold and $`fC^1(X,)`$. In , it has been shown that $`f`$ admits a pseudo-gradient vector field i.e. a map $`Y:XT(X)`$ such that

* The equation $`\dot{x}=Y(x)`$ has a unique solution for every initial point $`x_0X`$,
* $`Y.f:=Df(x),Y(x)\alpha (Df(x))`$ where $`\alpha `$ is a strictly increasing continuous function with $`\alpha (0)=0`$,
* $`Y`$ is bounded.

Therefore we can consider the flow relative to a pseudo-gradient vector field for $`f`$. From now on, suppose that $`\phi ^t`$ is the flow relative to the pseudo-gradient vector field $`Y`$ for $`fC^1(X,R)`$ and $`(N,L)`$ is an index pair for $`\phi ^t`$ such that $`f`$ is bounded on $`V:=\overline{NL}`$. Moreover we assume that $`f`$ satisfies Palais-Smale condition in $`V`$. (See also .)

### Definition.

We say that $`f`$ satisfies Palais-Smale condition in $`V`$ if any sequence $`\{x_n\}V`$ such that $`f(x_n)`$ is bounded and $`Df(x_n)0`$ possesses a convergent subsequence.

The following lemma shows that under the above assumptions, $`(N,L)`$ is a weakly regular index pair. Therefore we can use Corollary 2.3. to show the existence of a regular index pair in this situation.

### Lemma 4.1.

There exists $`T^+`$ such that for every $`xL`$, $`\phi ^{[0,T]}(x)V`$.
Proof. Suppose the contrary, then there is a sequence $`x_iL`$ and $`t_i^+`$ such that $`t_i+\mathrm{}`$ and $`\phi ^{[0,t_i]}(x_i)V`$. Since $`L`$ is positively invariant relative to $`N`$, we get $`\phi ^{[0,t_i]}(x_i)L`$. Now $`LV`$ is a closed set which does not contain any critical point of $`f`$. Since $`f`$ satisfies Palais-Smale condition in $`V`$, there is $`\delta >0`$ such that $`Y.f(x)>\delta `$ for every $`xLV`$. Therefore $`f(\phi ^{t_i}(x_i))f(x_i)>\epsilon t_i`$. Since $`t_i+\mathrm{}`$, it follows that $`f(\phi ^{t_i}(x_i))+\mathrm{}`$ which contradicts the boundedness of $`f`$ on $`V`$. $`\mathrm{}`$

### Lemma 4.2.

For large values of $`t^+`$, $`(\phi _{\mathrm{}}^t)^1([L])`$ is a neighborhood of $`[L]`$ in $`N/L`$.
Proof. By the above lemma, there exists $`T^+`$ such that $`\phi ^{[0,T]}(x)V`$ for every $`xL`$. Thus there is a neighborhood $`U_x`$ of $`x`$ such that $`\phi ^{[0,T]}(y)V`$ for every $`yU_x`$. Now $`_{xL}U_x`$ is a neighborhood of $`L`$, hence it defines a neighborhood $`U`$ of $`[L]`$ with $`\phi _{\mathrm{}}^T(U)=[L]`$. Therefore $`(\phi _{\mathrm{}}^t)^1([L])`$ is a neighborhood of $`[L]`$ in $`N/L`$ for every $`tT`$. $`\mathrm{}`$

For every $`a`$, we define $`(N/L)^a=[L]\{xNL|f(x)a\}.`$ The following two lemmas are reformulation of Deformation Theorems  for index pairs.

### Lemma 4.3.

(First Deformation Theorem) Suppose that $`f`$ has no critical points in $`(NL)f^1[a,b]`$ for some $`a<b`$. Then there exists $`T^+`$ such that $`(N/L)^a(\phi _{\mathrm{}}^T)^1((N/L)^b)`$.
Proof. Since $`f`$ has no critical points in the closed subset $`Vf^1[a,b]`$ and $`f`$ satisfies Palais-Smale condition in $`V`$, there is a $`\delta >0`$ such that $`Y.f>\delta `$ in $`Vf^1[a,b]`$. Now for every $`T\frac{ba}{\delta }`$ and $`xVf^1[a,b]`$, we have $`f(\phi ^T(x))a+\delta Tb`$. $`\mathrm{}`$

### Lemma 4.4.

(Second Deformation Theorem) Suppose that $`f`$ has exactly $`m`$ critical points $`y_1,\mathrm{},y_m`$ in $`(NL)f^1[c\epsilon _0,c+\epsilon _0]`$ and $`f(y_i)=c`$ for some $`c`$ and $`\epsilon _0>0`$. If $`U_i`$ is a neighborhood of $`x_i`$ in $`NL`$ and $`T^+`$, then there is an $`\epsilon [0,\epsilon _0]`$ such that $`(N/L)^{c\epsilon }(\phi _{\mathrm{}}^T)^1((N/L)^{c+\epsilon })_{i=1}^mU_i`$.
Proof. Since $`y_i`$ is a rest point for $`\phi ^t`$, there is an open set $`V_iU_i`$ such that $`\phi ^{[0,T]}(x)V_i=\mathrm{}`$ for every $`xU_i`$. Since $`f`$ has no critical point in $`Vf^1[c\epsilon _0,c+\epsilon _0]_{i=1}^nV_i`$ which is a closed subset of $`V`$ and $`f`$ satisfies Palais-Smale condition in $`V`$, there exists $`\delta >0`$ such that $`Y.f>\delta `$ in $`Vf^1[c\epsilon _0,c+\epsilon _0]_{i=1}^nV_i`$. If we set $`\epsilon =\frac{T\delta }{2}`$, then for every $`xVf^1[c\epsilon ,c+\epsilon ]_{i=1}^nU_i`$, we have $`f(\phi ^T(x))f(x)+T\delta c\epsilon +2\epsilon =c+\epsilon `$. $`\mathrm{}`$

### Proposition 4.5.

Suppose that $`f`$ has a finite number of critical points $`x_1,\mathrm{},x_n`$ in $`V`$ and $`U_i`$ is a neighborhood of $`x_i`$ in $`NL`$ for $`1in`$. Then there are $`t_0,t_1,\mathrm{},t_n^+`$ such that $`N/L=(\phi _{\mathrm{}}^{t_0})^1([L])_{i=1}^n(\phi _{\mathrm{}}^{t_i})^1(U_i)`$. In particular if $`(N,L)`$ is a regular index pair, then $`N=(\phi _{\mathrm{}}^{t_0})^1(L)_{i=1}^n(\phi _{\mathrm{}}^{t_i})^1(U_i)`$
Proof. We use induction on the number of critical values of $`f|_V`$. For $`k=0`$, $`f`$ has no critical points in $`V`$. Since $`f`$ is bounded on $`V`$, there are $`a<b`$ such that $`(N/L)^b=[L]`$ and $`(N/L)^a=N/L`$. Thus by Lemma 4.3., $`(\phi _{\mathrm{}}^T)^1([L])=N/L`$ for some $`T^+`$. Now suppose that $`f`$ has $`k+1`$ critical values $`c_0<c_1<c\mathrm{}<c_k`$ and $`x_{\mathrm{}},\mathrm{},x_n`$ are critical points with $`f(x_i)=c_k`$ for $`\mathrm{}in`$. If we use Lemma 4.4. for $`\epsilon _0=\frac{c_kc_{k1}}{2}`$ and $`T=1`$, we obtain an $`\epsilon [0,\epsilon _0]`$ such that $`(N/L)^{c\epsilon }\phi _{\mathrm{}}^1((N/L)^{c+\epsilon })_{i=\mathrm{}}^nU_i`$. Moreover by Lemma 4.3., there is a $`T^+`$ such that $`(N/L)^{c\epsilon }\phi _{\mathrm{}}^T([L])`$. Therefore we have $`(N/L)^{c\epsilon }(\phi _{\mathrm{}}^{T+1})^1([L])_{i=\mathrm{}}^nU_i`$. Now if we set $`L_1=Nf^1[c\epsilon ,+\mathrm{})`$, then $`(N,L_1)`$ is an index pair with $`k`$ critical values, hence there are $`t_0^{},t_1^{},\mathrm{},t_\mathrm{}1^{}`$ such that $`N/L_1=(\phi _{\mathrm{}}^{t_0^{}})^1([L_1])_{i=1}^\mathrm{}1(\phi _{\mathrm{}}^{t_i^{}})^1(U_i)`$. Now we set $`t_0=t_0^{}+T+1,t_i=t_i^{}`$ for $`1i\mathrm{}1`$ and $`t_i=t_0^{}`$ for $`\mathrm{}in`$. Then it is not hard to check that

$$N/L=(\phi _{\mathrm{}}^{t_0})^1([L])\underset{i=1}{\overset{n}{}}(\phi _{\mathrm{}}^{t_i})^1(U_i).\mathrm{}$$

### Theorem 4.6.

$`f`$ has at least $`\nu _H(N/L,[L])`$ critical points in $`V`$. Moreover if $`(N,L)`$ is a regular index pair, then $`f`$ has at least $`\nu _H(N,L)`$ critical points in $`V`$.
Proof. We may assume that $`f`$ has a finite number of critical points $`x_1,\mathrm{},x_n`$ in $`V`$. Since $`X`$ is a Banach manifold, we may choose a contractible open set $`U_iNL`$ which contains $`x_i`$ for $`1in`$. Now by the above proposition, there are $`t_0,t_1,\mathrm{},t_n^+`$ such that $`N/L=(\phi _{\mathrm{}}^{t_0})^1([L])_{i=1}^n(\phi _{\mathrm{}}^{t_i})^1(U_i)`$. It is easy to see that each $`(\phi _{\mathrm{}}^{t_i})^1(U_i)`$ is contractible in $`NL`$. The only problem is that $`(\phi _{\mathrm{}}^{t_0})^1([L])`$ is not an open set. By Lemma 4.2, there is $`T^+`$ such that $`int((\phi _{\mathrm{}}^T)^1([L]))\mathrm{}`$. Now we replace $`(\phi _{\mathrm{}}^{t_0})^1([L])`$ by $`int((\phi _{\mathrm{}}^{t_0+T})^1([L]))`$ which is obviously invariant under $`\phi _{\mathrm{}}^t`$ and conrtactible to $`[L]`$. Therefore we obtain an open covering which follows that $`\nu _H(N/L,[L])n`$. A similar argument for $`\phi _{\mathrm{}}`$ shows that if $`(N,L)`$ is a regular index pair, then $`\nu _H(N,L)n`$. $`\mathrm{}`$

### Example 4.7.

Let $`E`$ be an orientable vector bundle over a Finsler manifold $`X`$ and $`B`$ be a closed subset of $`X`$. We denote the disk and sphere bundles of $`E|_B`$ by $`D`$ and $`S`$ respectively. Let $`f:E`$ be a $`C^1`$ function satisfying Palai-Smale condition in $`B`$ and $`\phi ^t`$ be the flow relative to a pseudo-gradient vector field for $`f`$ such that $`(D,S)`$ is an index pair for $`\phi ^t`$. Then by Example 2.3. and the above theorem, $`f`$ has at least $`\nu _H(D,S)cuplength(B)`$ critical points in $`D`$. If we consider the case $`X=M\times ^n,E=X\times ^m`$ and $`B=M\times D^nM\times ^n`$, then we obtain a noncompact version of a well-known result of .

### Acknowledgment.

The author would like to thank Institute for Studies in Theoretical Physics and Mathematics for supporting this research.


text:
# Theory of Distinct Crystal Structures of Polymerized Fullerides AC60, A=K, Rb, Cs: the Specific Role of Alkalis

## Abstract

The polymer phases of AC60 form distinct crystal structures characterized by the mutual orientations of the $`(C_{60}^{})_n`$ chains. We show that the direct electric quadrupole interaction between chains always favors the orthorhombic structure $`Pmnn`$ with alternating chain orientations. However the specific quadrupolar polarizability of the alkali metal ions leads to an indirect interchain coupling which favors the monoclinic structure $`I2/m`$ with equal chain orientations. The competition between direct and indirect interactions explains the structural difference between KC60 and RbC60, CsC60.

Alkali metal doped C60 (AxC60), A=K, Rb, Cs, form stable crystalline phases (fullerides) with a broad range of physical and chemical properties comprising superconductors and polymer phases. For a review, see . In particular the $`x=1`$ compounds  exhibit plastic crystalline phases with cubic rocksalt structure at high temperature ($`T350`$ K) and polymeric phases  of reduced symmetry at lower $`T`$. In the latter the C60 molecules are linked through a \[2+2\] cycloaddition , a mechanism originally proposed for photo-induced polymerization  in pristine C60. From X-ray powder diffraction  it was concluded that the crystal structure of both KC60 and RbC60 was orthorhombic (space group $`Pmnn`$). Polymerization occurs along the orthorhombic $`\stackrel{}{a}`$ axis (the former cubic  direction), where the orientation of the polymer chain is characterized by the angle $`\mu `$ of the planes of cycloaddition with the $`\stackrel{}{c}`$ axis. In the $`Pmnn`$ structure (Fig. 1a), these orientations are alternatively $`\mu `$ and $`\mu `$, $`|\mu |45^0\pm 5^0`$. Notwithstanding this apparent structural similarity, the electronic and magnetic properties of KC60 on one hand and RbC60, CsC60 on the other hand, were found to be very different . ESR and optical conductivity data  show that RbC60 and CsC60 exhibit a transition from a quasi-one dimensional metal to an insulating magnetic state near 50 K, while KC60 stays metallic and nonmagnetic at low $`T`$. NMR spectra also showed marked differences between KC60 and Rb-, Cs- polymers . The contradiction between similar crystalline structures and different electromagnetic properties was resolved by single crystal X-ray diffraction and diffuse scattering studies . Indeed the polymer phases of KC60 and RbC60 are different. While the space group $`Pmnn`$ is confirmed for KC60, it is found that RbC60 is body centered monoclinic, with space group $`I2/m`$. In the latter structure, the polymer chains have the same orientation $`\mu `$ (Fig. 1b). Electronic band structure calculations for the $`I2/m`$ structure have shown the importance of transverse interchain coupling for RbC60 . Recently  high-resolution synchrotron powder diffraction results demonstrated that CsC60 has the same structure as RbC60.

In this paper we study the mechanism which leads to the distinct polymer phases and we demonstrate the active role of the distinctive quadrupolar electronic polarizability of the alkali ions (cations). We start from the high temperature orientationally disordered cubic phase (space group $`Fm\overline{3}m`$) and describe the formation of the polymer phases as a scenario with several steps: i) the charge transfer of one electron from the alkali atom to the C60 molecule leads to an occupation of the lowest unoccupied molecular orbital levels which are of $`t_{1u}`$ symmetry. Thereby the crystal field of the C$`{}_{}{}^{}{}_{60}{}^{}`$ ion acquires an electronic component  which favors a same orientation of neighboring molecules along  such that the stereospecific cycloaddition occurs. ii) The cycloaddition between neighboring molecules then acts as a negative internal stress (chemical pressure) along . iii) The mutual orientation of neighboring C$`{}_{}{}^{}{}_{60}{}^{}`$ chains, which distinguishes between the orthorhombic and monoclinic structures, should depend on the intercalated alkali ions.

We first show that the orthorhombic lattice is the result of the cycloaddition. Using concepts of the theory of elasticity , we find that the cubic crystal is deformed into an orthorhombic one (point group $`D_{2h}`$). Taking the cubic , \[1$`\overline{1}`$0\] and  as new $`x`$, $`y`$ and $`z`$ axes (orthorhombic $`\stackrel{}{a}`$, $`\stackrel{}{b}`$ and $`\stackrel{}{c}`$) respectively, we find the deformations

$`ϵ_{xx}={\displaystyle \frac{K}{dc_{44}}}[c_{11}(c_{11}+c_{12}+2c_{44})2c_{12}^2],`$ (2)
$`ϵ_{yy}={\displaystyle \frac{K}{dc_{44}}}[c_{11}(c_{11}+c_{12}2c_{44})2c_{12}^2],`$ (3)
$`ϵ_{zz}=Kc_{12}/d,`$ (4)
where $`c_{ij}`$ are the cubic elastic constants, $`d=c_{11}(c_{11}+c_{12})2c_{12}^2`$ and where $`K<0`$ is the uniaxial stress. Obviously $`ϵ_{xx}<0`$, $`ϵ_{yy}>0`$ and $`ϵ_{zz}>0`$ which corresponds to contraction along $`\stackrel{}{a}`$ and elongations along $`\stackrel{}{b}`$ and $`\stackrel{}{c}`$. We next investigate the orientation of the polymer chains. Following the experimental breakthrough , preliminary calculations of interchain energies have been performed . The interaction energy is highly sensitive to the lattice constants and a plausible scenario is that C60-C60 interchain distances impose different relative chain orientations. However the last argument is at variance with single crystal X-ray diffraction results of pressure polymerized C60 . There the space group is $`Pmnn`$, $`i.e.`$ isostructural with polymerized KC60. However the orthorhombic cell volume of polymerized C60 and the distance between a corner and the center of the cell, 1326 Å3 and 9.956 Å, respectively, are closer to the corresponding values in RbC60, 1314.9 Å3 and 9.852 Å, than to those of KC60, 1298 Å3 and 9.836 Å. We conclude that the alkalis must play a more specific role in triggering the structural difference between KC60 and RbC60, CsC60. From the theory of bilinear rotation-translation (RT) coupling between molecular rotations and lattice displacements of the counterions which plays an essential role in determining the elastic properties of ionic molecular crystals , one finds an effective rotation-rotation (RR) interaction that competes with the direct intermolecular RR interaction. However the lattice mediated RR interaction is found to be independent of the alkali mass and hence no distinction on basis of the different masses is possible. A further distinctive property of the alkali metal ions is the dipolar electronic polarizability, with values 0.9, 1.7 and 2.5 Å3 for K+, Rb+ and Cs+, respectively . We expect that also the quadrupolar polarizability is larger for the heavy alkali metal ions than for K+. In the following we will show that the electric quadrupole interaction between C$`{}_{}{}^{}{}_{60}{}^{}`$ chains and the alkali ions leads to an effective orientational interaction between the C$`{}_{}{}^{}{}_{60}{}^{}`$ chains.

We will study first the electric multipole interaction between polymer chains. Polymerization reduces the symmetry, the C$`{}_{}{}^{}{}_{60}{}^{}`$ chain is composed of units with $`D_{2h}`$ symmetry. We have used a tight-binding model to study the electronic charge distribution on the C$`{}_{}{}^{}{}_{60}{}^{}`$ units in the chain . The charge is mainly concentrated in the equatorial region of C$`{}_{}{}^{}{}_{60}{}^{}`$, in agreement with recent NMR results . We find that only even $`l`$ multipoles are allowed, in particular each C$`{}_{}{}^{}{}_{60}{}^{}`$ unit has an electric quadrupole. In the following we adopt a simple model of charge distribution. Using the labeling of C atoms of , we locate a charge of $`0.15`$ (units $`|e|=1`$) on each bond C15-C16. These charges are fixed at a distance $`d=3.52`$ Å from the center of the C$`{}_{}{}^{}{}_{60}{}^{}`$ ball. Such a charge distribution is sufficient to obtain a quadrupole (see also Eq. (5)), the accompanying monopole is irrelevant. The chains are taken as rigid units with sole degree of freedom the rotation angle $`\mu `$ about the axis $`\stackrel{}{a}`$. Hence we can treat the three dimensional crystal in the polymer phase as a two dimensional problem in the $`(\stackrel{}{b}\stackrel{}{c})`$ plane. Here we consider one chain per unit cell with basis vectors $`\stackrel{}{r}_1=(\stackrel{}{c}/2)+(\stackrel{}{b}/2)`$ and $`\stackrel{}{r}_2=(\stackrel{}{c}/2)(\stackrel{}{b}/2)`$. The chains are labeled by a two dimensional array $`\stackrel{}{n}=(n_1,n_2)`$ and lattice vectors are given by $`\stackrel{}{X}(\stackrel{}{n})=n_1\stackrel{}{r}_1+n_2\stackrel{}{r}_2`$, where $`n_1`$, $`n_2`$ are integers. The Coulomb interaction between chains depends on their mutual orientation. We introduce symmetry adapted rotator functions (SAF’s) $`S_l(\stackrel{}{n})=\mathrm{sin}(l\mu (\stackrel{}{n}))`$. Symmetry of the chain for $`\mu \mu +\pi `$ implies $`l=2`$, 4, … . These functions are ungerade in $`\mu `$ and $`S_2`$ is maximum for $`\mu =45^0`$. Expanding the Coulomb interaction in terms of SAF’s we consider in lowest order of $`l`$ the quadrupole-quadrupole interaction

$`H_{SS}={\displaystyle \frac{1}{2}}{\displaystyle \underset{\stackrel{}{n}\stackrel{}{n}^{}}{}}(J_a(\stackrel{}{n},\stackrel{}{n}^{})+J_b(\stackrel{}{n},\stackrel{}{n}^{}))S_2(\stackrel{}{n})S_2(\stackrel{}{n}^{}).`$ (5)
More involved molecular charge distributions would lead to higher ($`l4`$) multipoles , but their interactions are negligible. We observe that nearest neighbor chains are shifted by a translation $`a/2`$ along the $`\stackrel{}{a}`$ axis with respect to each other. For a C$`{}_{}{}^{}{}_{60}{}^{}`$ molecule at $`\stackrel{}{n}`$ as origin, $`J_a`$ takes into account the interaction with the two molecules at $`\pm a/2`$ on the neighboring four chains $`X(\stackrel{}{n}^{})=\pm \stackrel{}{r}_1`$ and $`X(\stackrel{}{n}^{})=\pm \stackrel{}{r}_2`$, $`J_b`$ describes the interaction with one molecule on the chains $`X(\stackrel{}{n}^{})=\pm (\stackrel{}{r}_1\stackrel{}{r}_2)`$. In two dimensional Fourier space we obtain

$`H_{SS}={\displaystyle \frac{1}{2}}{\displaystyle \underset{\stackrel{}{q}}{}}J(\stackrel{}{q})S_2(\stackrel{}{q})S_2(\stackrel{}{q}),`$ (7)
$`J(\stackrel{}{q})=8J_a\mathrm{cos}\left({\displaystyle \frac{q_yb}{2}}\right)\mathrm{cos}\left({\displaystyle \frac{q_zc}{2}}\right)+2J_b\mathrm{cos}(q_yb),`$ (8)
where $`q_y`$ and $`q_z`$ are components along the original orthorhombic axes $`\stackrel{}{b}`$ and $`\stackrel{}{c}`$. With the simple model of charge distribution for the C$`{}_{}{}^{}{}_{60}{}^{}`$ units and the orthorhombic lattice constants of Table I, we have calculated the quadrupolar interaction energies $`J_a`$ and $`J_b`$ quoted in Table I.

From Eq. (8) we find that $`J(\stackrel{}{q})`$ is negative and maximum in absolute value at the boundary of the Brillouin zone (BZ). For all three compounds we have $`|J(\stackrel{}{q}_Z)|>|J(\stackrel{}{q}_\mathrm{\Gamma })|`$, where $`\stackrel{}{q}_Z=(0,2\pi /c)`$ is a BZ boundary vector and $`\stackrel{}{q}_\mathrm{\Gamma }=(0,0)`$ is the BZ center. This result is independent of the strength of the molecular quadrupoles but is a consequence of the orthorhombic lattice. The dominance of $`J(\stackrel{}{q}_Z)`$ leads to a condensation of $`S_2(\stackrel{}{q})`$ for $`\stackrel{}{q}=\stackrel{}{q}_Z`$: $`S_2(\stackrel{}{q}_Z)=\eta /\sqrt{N}`$. Here $`\eta `$ is the order parameter amplitude and $`N`$ is the number of chains ($`i.e.`$ lattice points in the $`(\stackrel{}{b}\stackrel{}{c})`$ plane). Condensation at $`\stackrel{}{q}_Z`$ implies that the chains in a same basal plane $`(\stackrel{}{a}\stackrel{}{b})`$ of the orthorhombic lattice all have the same orientation, but the orientation alternates in neighboring planes at distance $`c/2`$. This is the “antiferrorotational” structure $`Pmnn`$, Fig. 1a. We find that the quadrupolar interaction between C60 chains leads to $`Pmnn`$ for KC60, RbC60, CsC60, irrespective of the different orthorhombic lattice constants. For RbC60 and CsC60 the experimental result is $`I2/m`$ . We now include the role of the alkali ions with their distinctive polarizability. It is known from work on the ammonium halides  that the indirect interaction of two NH$`{}_{}{}^{+}{}_{4}{}^{}`$ tetrahedra via the polarizable halide ions plays an essential role in determining the various crystalline phases of the ammonium halides NH4X, X=Cl, Br, I . However in the present problem, by symmetry the dipolar polarizability of the alkali metal ions is irrelevant and we have to resort to the quadrupolar polarizability. Since the C$`{}_{}{}^{}{}_{60}{}^{}`$ units in a polymer chain are rigidly linked in a same orientation, the C$`{}_{}{}^{}{}_{60}{}^{}`$ chains produce coherent electric field gradients which induce an anisotropic (quadrupolar) deformation of the electron shell of the alkalis. We model the corresponding charge distribution of each alkali by a symmetric linear dumbbell centered on lines along $`\stackrel{}{a}`$ directions. On a same line, these induced dumbbells are parallel with their axis perpendicular to $`\stackrel{}{a}`$ and a same orientation angle $`\nu `$ with the $`\stackrel{}{c}`$ axis. We consider chains of alkali dumbbells, where the rigid chain aspect is not imposed by intrachain interactions but by the surrounding C$`{}_{}{}^{}{}_{60}{}^{}`$ chains. The orientational motion of an alkali dumbbell is characterized by the SAF’s $`s_2(\stackrel{}{n})=\mathrm{sin}(2\nu (\stackrel{}{n}))`$, where $`\stackrel{}{n}`$ is again a two dimensional array labeling the chains. The quadrupole-quadrupole interaction between the C$`{}_{}{}^{}{}_{60}{}^{}`$ chains and the surrounding alkalis is then given by

$`H_{sS}={\displaystyle \underset{\stackrel{}{n}\stackrel{}{n}^{}}{}}(\lambda _b(\stackrel{}{n},\stackrel{}{n}^{})+\lambda _c(\stackrel{}{n},\stackrel{}{n}^{}))S_2(\stackrel{}{n})s_2(\stackrel{}{n}^{}),`$ (9)
where $`\lambda _b(\stackrel{}{n},\stackrel{}{n}^{})`$ accounts for the two alkalis at $`\pm a/2`$ on the chains $`X(\stackrel{}{n}^{})=\pm (\stackrel{}{r}_1\stackrel{}{r}_2)/2`$ and where $`\lambda _c(\stackrel{}{n},\stackrel{}{n}^{})`$ describe the interaction with one alkali on the chains $`X(\stackrel{}{n}^{})=\pm (\stackrel{}{r}_1+\stackrel{}{r}_2)/2`$. In Fourier space we have

$`H_{sS}={\displaystyle \underset{\stackrel{}{q}}{}}\lambda (\stackrel{}{q})S_2(\stackrel{}{q})s_2(\stackrel{}{q}),`$ (11)
$`\lambda (\stackrel{}{q})=4\lambda _b\mathrm{cos}\left({\displaystyle \frac{q_yb}{2}}\right)+2\lambda _c\mathrm{cos}\left({\displaystyle \frac{q_zc}{2}}\right).`$ (12)
We take dumbbells with charges $`q_A`$ at distances $`\pm d_A`$ from the center. Here $`A`$ refers to K, Rb, or Cs. The numerical values of $`d_A`$ (Table I) are the average radii of valence electron $`d`$ shells calculated with atomic wave functions $`3d_{3/2}`$, $`4d_{3/2}`$, $`5d_{3/2}`$ for K+, Rb+ and Cs+ respectively. We consider $`d`$-shells because they can support an electric quadrupole moment. We observe that the values for Cs+ and Rb+ are close to each other but differ from K+. The alkali ions are isoelectronic with the rare gas atoms Ar, Kr, Xe. There the role of excited $`d`$ states has been found to be important in the explanation of the face centered cubic structure . With the same value $`q_A=0.15|e|`$ for the three cases, we have calculated the interaction energies $`\lambda _b`$ and $`\lambda _c`$ quoted in Table I. The quantity $`|\lambda (\stackrel{}{q})|`$ is maximum for $`\stackrel{}{q}=\stackrel{}{q}_\mathrm{\Gamma }`$ in contradistinction with $`|J(\stackrel{}{q})|`$. The intra ionic restoring forces which oppose the deformation of the electron shells of the alkalis are described by a sum of single particle energy terms

$`H_{ss}=g_A{\displaystyle \underset{\stackrel{}{n}}{}}s_2^2(\stackrel{}{n})=g_A{\displaystyle \underset{\stackrel{}{q}}{}}s_2(\stackrel{}{q})s_2(\stackrel{}{q}),`$ (13)
with $`g_A>0`$. The self energy $`g_A`$ is inversely proportional to the quadrupolar electronic polarizability and hence $`g_{Cs}<g_{Rb}<g_K`$ (see Table I). These concepts are inspired from the shell model of lattice dynamics . The direct interchain coupling of alkali quadrupoles is numerically found to be small and will be neglected. We consider the total interaction $`H=H_{SS}+H_{sS}+H_{ss}`$. The induced alkali quadrupoles follow adiabatically the motion of the C$`{}_{}{}^{}{}_{60}{}^{}`$ chains. For a given configuration $`\{S_2(\stackrel{}{q})\}`$ of the latter, we minimize $`H`$ with respect to $`s_2(\stackrel{}{q})`$ and find

$`s_2(\stackrel{}{q})={\displaystyle \frac{1}{2}}{\displaystyle \frac{\lambda (\stackrel{}{q})}{g_A}}S_2(\stackrel{}{q}),`$ (14)
Substituting this result for $`s_2`$ in $`H`$ we get

$`H={\displaystyle \frac{1}{2}}{\displaystyle \underset{\stackrel{}{q}}{}}\stackrel{~}{J}(\stackrel{}{q})S_2(\stackrel{}{q})S_2(\stackrel{}{q}),`$ (16)
where

$`\stackrel{~}{J}(\stackrel{}{q})=J(\stackrel{}{q})+C(\stackrel{}{q}),`$ (17)
$`C(\stackrel{}{q})={\displaystyle \frac{1}{2}}{\displaystyle \frac{\lambda ^2(\stackrel{}{q})}{g_A}}.`$ (18)
The coupling to the alkalis leads to an effective orientational interaction $`C(\stackrel{}{q})`$ between C$`{}_{}{}^{}{}_{60}{}^{}`$ chains. This interaction is attractive and since $`|C(\stackrel{}{q})|`$ with $`\lambda (\stackrel{}{q})`$ is maximum at $`\stackrel{}{q}=\stackrel{}{q}_\mathrm{\Gamma }`$, it favors a “ferrorotational” structure (space group $`I2/m`$). On the other hand the direct quadrupolar interaction between C$`{}_{}{}^{}{}_{60}{}^{}`$ chains with $`|J(\stackrel{}{q}_Z)|>|J(\stackrel{}{q}_\mathrm{\Gamma })|`$ favors the antiferrorotational structure. The system of interacting polymer chains described by Eq. (16) chooses the lowest energy structure which is $`Pmnn`$ or $`I2/m`$ depending on whether $`|\stackrel{~}{J}(\stackrel{}{q}_Z)|>|\stackrel{~}{J}(\stackrel{}{q}_\mathrm{\Gamma })|`$, $`i.e.`$ $`J_a>\lambda _b\lambda _c/g_A`$, or the opposite holds respectively. Using the numerical values from Table I, we have plotted $`\stackrel{~}{J}(\stackrel{}{q})`$ for $`\stackrel{}{q}=(q_y=0,q_z)`$ in Fig. 2. For KC60  with the small polarizability of the K+ ion, the direct interchain interaction $`J(\stackrel{}{q}_Z)`$ dominates and leads to $`Pmnn`$ while for RbC60  and even more for CsC60  the alkali mediated interaction $`C(\stackrel{}{q}_\mathrm{\Gamma })`$ dominates and leads to $`I2/m`$.

A condensation of $`S_2(\stackrel{}{q})`$ at the BZ center leads, via coupling to the center of mass displacements of the alkali ions (bilinear RT-coupling) to $`ϵ_{yz}`$ shear modes and hence to a deviation of the $`(\stackrel{}{b},\stackrel{}{c})`$ angle $`\alpha `$ from 900 in the $`I2/m`$ structure. However this RT-coupling is not the driving process of the monoclinic structure. Indeed, the deviations of $`\alpha `$ are very small .

In conclusion we have shown that the cycloaddition between C$`{}_{}{}^{}{}_{60}{}^{}`$ units leads to an orthorhombic lattice structure. The concomitant symmetry reduction produces a quadrupolar electric charge distribution on the C$`{}_{}{}^{}{}_{60}{}^{}`$ units. The interaction between C$`{}_{}{}^{}{}_{60}{}^{}`$ chains has two competing components: a direct quadrupole-quadrupole interaction $`J(\stackrel{}{q})`$ and an indirect one $`C(\stackrel{}{q})`$. The latter is mediated by the induced quadrupoles on the polarized alkali metal ions. The direct quadrupolar interaction drives the antiferrorotational structure $`Pmnn`$ while the indirect one yields the ferrorotational structure $`I2/m`$. In RbC60 and CsC60 with larger electronic polarizability and quadrupolar radius $`d_A`$ of the alkalis, $`\lambda _b\lambda _c/g_A>J_a`$, the ferrorotational structure is realized while in KC60, $`J_a>\lambda _b\lambda _c/g_A`$, the antiferrorotational structure is realized. Within the present theory, the alkalis play a specific role beyond the function of lattice spacers. The study of alkali specific effects is a problem of broad interest and likely to be relevant for the understanding of superconducting fullerides .

We acknowledge useful discussions with K. Knorr, P. Launois and R. Moret. This work has been financially supported by the Fonds voor Wetenschappelijk Onderzoek, Vlaanderen.


text:
# 1 Introduction

## 1 Introduction

The DNA microarray technology  has greatly facilitated the study of gene expressions. With a single microarray, the expression of thousands of genes can be measured simultaneously. Based on the central dogma it is reasonable to understand these expression vectors as a description of the functional state of the cell. The dynamics of the state-trajectory observed in expression time series reveals much information about the regulatory network underlying gene expression. A detailed knowledge of this network would allow for the analysis of possible states and trajectories, including, say, transitions from disease to a healthy state.

Therefore, it is very tempting to try to infer the regulatory network from the data. One should, however, be aware of the limitations in the data available so far. It is very possible that large parts of the network were inactive for the states observed. These “unexcited” parts of the network can not be deduced from the data. Furthermore important parts of the regulatory network, like e.g. inter- and intra-cell signalling, are observed only indirectly by back reaction on the gene expression pattern.

Cluster algorithms have been used successfully in the analysis of gene expression data. Using for example hierarchical clustering it has been demonstrated  that many genes, which on biological grounds are known to be related, are located near by in the similarity tree. It is however difficult to identify genes which belong to a larger functional context, like for example cell cycle regulated genes. If two of the corresponding patterns are expressed with a phase difference close to $`\pi /4`$, they are uncorrelated and therefore placed on remote sites in the similarity tree.

The prior knowledge of the cell cycle frequency $`\nu _{cc}`$ was used to identify the cell cycle regulated genes by inspection . In  a spectral filter was used for this purpose. Expression patterns, for which the spectral energy at frequency $`\nu \nu _{cc}`$ is larger than some threshold, were selected as cell cycle regulated.

In this work we use a new method, the re-shuffling algorithm , to identify functional groups in the expression data. The algorithm sorts the data based on a global similarity score, which makes it very robust with respect to noise. The method does not distribute the data into clusters. The structure found in the data is rather reflected in a re-ordered sequence of expression patterns. Using this algorithm we are able to identify the cell cycle regulated genes in the budding yeast S. cerevisae without referring to prior knowledge. Furthermore we find a second, independent clock in the cell. The reordered sequence of expression patterns can reflect the propagation of a signal in the data. Patterns, which respond to the same, deformed signal are grouped together, even if they are mutually uncorrelated.

## 2 Algorithm

In this section we briefly describe the algorithm used to analyze the data. A more detailed description can be found elsewhere .

The starting point is a matrix $`C_{ij}`$ encoding the similarity between expression patterns $`i`$ and $`j`$. This similarity can, for example, be the mutual information or correlation for the two patterns. The purpose of the algorithm is to find a relabeling $`i\sigma (i)`$ such that similar patterns $`i,j`$, i.e. $`|C_{ij}|1`$, get similar labels: $`|\sigma (i)\sigma (j)|1`$. This is, however, not achieved by performing local, mutual, comparisons, but rather by letting expression patterns move freely in a “force-field” generated by all other particles. This field is is described by the energy

$$S_\sigma (\alpha ,\gamma ,\lambda )=\underset{i,j}{}\text{sgn}(C_{\sigma (i)\sigma (j)})^\gamma |C_{\sigma (i)\sigma (j)}|^\alpha \mathrm{exp}\frac{d(i,j)^2}{N\lambda }.$$
(1)
The optimal sorting in the sense described above is the one minimizing this energy. The parameter $`\alpha `$ controls the importance of the similarity in the sorting procedure, we use $`\alpha =2`$. The variable $`\lambda `$ is a localization parameter. For small $`\lambda `$, mainly similarities close in index space contribute to the energy. This leads to a local optimization. For large $`\lambda `$ a more global optimization is achieved. The parameter $`\gamma `$ is used to switch between maintaining ($`\gamma =1`$) or ignoring ($`\gamma =0`$) the sign of $`C_{ij}`$.

Obviously the average distance $`\overline{d}`$ of indices from all other indices is not evenly distributed. It reaches its maximum on the border $`i=1,N`$. This non-flat distribution is not desired, therefore we use a cyclic distance measure in index space. With

$$d(i,j)=\{\begin{array}{ccc}\hfill |ij|& & \mathrm{if}|ij|<N/2\hfill \\ \hfill |ijN|& & \mathrm{if}|ij|N/2\hfill \end{array},$$
(2)
the first and the last pattern in the list are direct neighbors, the system has no boundary and therefore the $`\overline{d}`$ distribution is flat.

Unless $`C_{ij}`$ has a very simple form, the minimization of equation (1) is a non-trivial task. We use simulated annealing  for this purpose. In the annealing procedure a fictious ensemble temperature $`T`$ is lowered. At the beginning, at high temperature, the global aspects of the structure contained in the data should be built into the order of expression patterns, while towards the end of the annealing procedure, at low temperature, the more local optimization takes place. Therefore the localization parameter $`\lambda `$ is lowered together with the temperature from typically $`\lambda =1`$ to $`\lambda =0.05`$ in this procedure.

## 3 Results

For this work we used the expression data for S. cerevisae, which is available on the internet http://cellcycle-www.standford.edu and described in . Here we want to demonstrate the feasibility of our algorithm on a subset of this data set.

The original data consists of $`82`$ experiments, which were done at different time points and/or boundary conditions. Each experiment provides measurements of $`6177`$ expression ratios. The subset used here was extracted in the following way:

1. Experiments with more than 400 missing expression ratios were removed.
2. Expression patterns (in gene direction) with more than 8 missing ratios were removed.
3. From the remaining genes measured in $`\tau =69`$ experiments we kept those $`N=803`$ patterns with variance $`\sigma >0.5`$.

In the following the Pearson correlation

$$C_{ij}=\frac{_t^\tau (D_{i,t}\overline{D_i})(D_{j,t}\overline{D_j})}{\tau \sqrt{\text{Var}(D_i)\text{Var}(D_j)}}$$
(3)
is used as the similarity score in equation (1). First the absolute value $`|C_{ij}|`$ is used ($`\gamma =0`$), because we are interested in analyzing functional groups of genes, which show up by (anti)-correlated expression patterns. The result of the sorting procedure is visualized in figure 1, a graphical representation of the correlation matrix. In this diagram the intensity of the pixel at coordinate $`(i,j)`$ is proportional to the absolute value $`|C_{ij}|`$. Red color represents correlation, green color anti-correlation.

At coordinates adjacent to the main diagonal of the matrix one clearly observes a grouping of gene expression patterns. With the help of the annotations for the genes involved one can verify that the grouping reflects a classification with respect to gene function. The annotation displayed in figure 1 refers to the most frequent phrase found in the annotation database for the genes in these groups. These typical phrases do not exclusively show up there, their distribution over the whole dataset is, however, strongly peaked in the marked groups.

The diagram does not only contain information about the dominant correlation, which clusters the genes into groups. Sub-dominant co-regulations can be seen in the more off-diagonal parts of the matrix. As expected, the non-local interaction (1) sorts the groups on the main diagonal such that clusters with sub-dominant co-regulation group together. Therefore the distance of groups on the main diagonal reflects the relative strength of co-regulation. In the off-diagonal correlation coefficients an interesting fine structure can be observed: for example in the region marked with an arrow one sees that two groups, which are internally correlated, can be correlated and anti-correlated at the same time. From this observation one can infer a fine-structure into the groups on the diagonal.

The checker board patterns observed in the upper left and lower right in figure 1 are very interesting. Obviously they are generated by oscillatory processes: adjacent red and green blocks indicate co-regulated, but mutually exclusive expressed genes. These genes are active in different parts of a cycle. By inspection of gene annotations, the lower right functional group is identified as cell-cycle regulated genes. In  these genes were identified using a different method. Expression patterns, for which the Fourier component for frequencies close to the expected cell-cycle frequency were larger than some threshold were identified as cell-cycle regulated. For our method, the introduction of a threshold and knowledge of the oscillator frequency is not necessary.

The checker board in the upper left corner represents a second cell “clock”. From the intensity of the correlation of this group with the cell-cycle, we conclude that this second clock is not strongly coupled to the cell cycle. Therefore this functional group is an independent oscillator. To elaborate this further we have analyzed the frequency spectrum for the expression patterns of genes in this group and for the cell-cycle regulated genes. Both spectral power distributions show a clear maximum at a frequency $`\nu `$, which differs significantly for the two groups. For the second clock we find $`\nu =4/7\nu _{\text{cc}}`$, where $`\nu _{\text{cc}}`$ is the frequency which maximizes the cell cycle power spectrum. The method used in  could therefore not identify the genes in this group as cyclic regulated.

A list of genes controlled by this cell-clock is available at http://www.thep.lu.se/$`\stackrel{~}{}`$sven. Unfortunately, the maximal time-span, for which experiments were done, contains only one complete cycle of this clock. It is therefore not possible to decide, if this is a continuous oscillator or a one-shot clock. Some annotations which appear frequently for the genes found in this functional group make it plausible, that this clock controls the transcription of genes and the synthesis of proteins.

Next we want to show how the non-local part of the interaction in (1) influences the ordering of gene expression patterns. For each site $`i`$ in the list of expression patterns one can define an effective prototype expression $`P_i`$, which is induced by all expression patterns in the data set via the energy. This prototype is the pattern which minimizes the energy, the solution $`D_{i,t}`$ of

$$0=\frac{}{D_{i,t}}S(\alpha ,\beta ),t=1\mathrm{}\tau .$$
(4)
In general this optimal pattern will differ from site to site. Hence it can follow a signal which is deformed from a pattern $`A`$ to a pattern $`B`$.

To demonstrate this property we choose the cell-cycle regulated genes, where the signal “activated” travels through the system. Differently from above, where the list of patterns was sorted with with respect to co-regulation, anti-correlated genes should not be grouped together in this case, because presumably they belong to opposite parts of the cell cycle. We therefore choose $`\gamma =1`$, when relabeling the expression patterns. In figure 2 the correlation coefficients for the cell cycle regulated genes sorted in this way are displayed. We have used the analysis in  to assign the genes to a specific part in the cell-cycle, the result is presented as the annotation in the diagram. Obviously the data is correctly time-ordered Remember the list is cyclic, i.e. the last line is logically adjacent to the first line. Note that the algorithm does in no way explicitly refer to the time aspect in the data. In fact, the energy (1) is invariant under the exchange of experiments, different time-points. This observation confirms the capability of the algorithm to identify a previously unknown signal-pathway hidden in the data.

## 4 Discussion

Re-shuffling is efficient in finding functional groups in the expression data. The philosophy of this algorithm is considerably different from cluster algorithm, which compare each pattern $`p`$ locally with some prototypic pattern for each cluster and finally assign $`p`$ to the cluster with the most similar prototype. In this way many of these algorithms do not use the information available about inter-cluster similarities. Re-shuffling is based on a global comparison with all patterns in the ensemble. In this way it makes use of the information contained in sub-leading similarities as well. We want to emphasize that this method is not restricted to the analysis of time expression data. It can also be used to detect patterns in static data to identify, for example, genes which are responsible for a certain phenotype or disease.

Self organizing maps use a non-local assignment of patterns to neurons. Therefore they can reflect inter-cluster similarities. They were used in  to classify yeast gene expression patterns. With this method it is possible to identify the cell cycle oscillation as a dominant motif in the expression data . However, the neurons most active for the corresponding patterns at different parts of the cell cycle were not grouped in an obvious way. It was not possible to identify these patterns as belonging to the same functional cycle.

The re-shuffling method is able to extract this information. Without any prior knowledge it can identify the cell cycle regulated genes. It is very interesting to observe that the algorithm extracts time information from the data without actually referring to the time aspect. This demonstrates that the pathways of signals can be extracted from the data using this method. This aspect can be very useful when analyzing functional groups which are not so well known as the cell cycle. A further example of the algorithms power is the identification of a second independent clock in yeast.

A general problem when analyzing expression data is noise. When measurements are easily available, the usual way to reduce noise is to increase the number $`M`$ of measurements until the noise level $`\sigma 1/\sqrt{M}`$ is small enough. Repeated measurements of the same system would also allow for a reliable estimation of the noise level. This knowledge is crucial when interpreting the results of an analysis. However, gene expression measurements are quite costly in time and are usually not repeated. Therefore the methods used to analyze the data have to be relatively insensitive to noise. The re-shuffling algorithm is very robust in this respect because the energy function (1) used in the sorting procedure averages over all patterns in the data set. Many cluster algorithms and self organizing maps only average over a subset of the data when extracting a prototype for a cluster (or a neighborhood of a neuron). They are therefore more sensitive with respect to noise.

The visualization of the correlation matrix gives some insight into the connectivity of the underlying regulatory network. One may ask if it is possible to learn the full network from the data. The complexity of the model that can be inferred from the data is strictly limited by Shannons theorem

$$\frac{I_{\text{xmit}}}{N}=\nu _{\text{max}}\mathrm{log}_2\left(1+\frac{S}{P}\right).$$
(5)
The signal $`S`$ – the mRNA concentration in the cell-plasma – is “transmitted” over a channel (the measurement process) with noise $`P`$. With an estimated $`15\%`$ noise-level and the bandwidth given by the Nyquist frequency $`\nu _{\text{max}}=1/2`$, the maximal amount of information extractable from one measurement of $`N`$ ORF’s is less than $`I_x=\frac{3N}{2}`$ bits. This is the theoretical upper limit on the information content in the data. It can only be reached if an optimal code is used. This is certainly not the case for the gene expression data, as it contains a lot of redundancy. The maximal complexity of a model which can be inferred from the data is therefore considerably smaller than estimated by equation (5). The amount of information required to describe the connectivity of a possibly fully connected network of $`N`$ nodes is $`I_fN(N1)/2>>\tau I_{\text{xmit}}`$, much larger than available from the $`\tau `$ measurements. Even if one restricts the maximal number of connections to $`k`$, the information $`I_rNk\mathrm{log}_2N`$ required to describe the connectivity of this network is larger than available already for small $`k`$. It seems therefore necessary to reduce the number $`N`$ of nodes in the network. This can be done by introducing collective nodes representing a whole subset of the original genes. The groups resulting from re-shuffling the data might be a good starting point for this.

In the future the algorithm can be modified to operate in a higher dimensional index space. In this way a more refined representation of structure found in the data is possible. It may also be useful to combine hierarchical clustering with this method, which can be used to freeze the orientation degree of freedom on each branching point in the similarity tree.

## 5 Acknowledgement

I want to thank Å. Borg, C. Peterson and M. Ringnér for fruitful discussions. This work was supported by the Swedish Foundation for Strategic Research.


text:
# 1 Introduction

## 1 Introduction

Although the theory of multi-particle correlations in free-electron beams is relatively well developed (see e.g. ), up to now there has not been much attention devoted to the electron spin. We feel this as a deficiency because the spin degree of freedom is a significant feature of the electron and should be therefore taken into account. In this paper we try to reduce this deficiency for one particular case that is, as we believe, the most typical one in electron correlation experiments. Namely, we calculate the multi-electron correlation function for an electron chaotic beam with an arbitrary degree of spin polarization.

Moreover, the presented theory can be applied not only to chaotic electron (or generally spin-1/2-particle) beams, but also to a chaotic photon beams because the corresponding Hilbert space of possible photon polarization states is two-dimensional precisely as is the Hilbert space of the spin-1/2 states. We will speak about electrons for brevity, but the argumentation and the results can be applied also to the case of photons.

## 2 Chaotic state

The reason why we concentrate on the chaotic state is that we believe it is a good approximation for a state produced by the most coherent electron source available nowadays – the field-emission tip. This source is the only candidate for electron correlation experiments at the present time  because it offers both high brightness and a relatively monochromatic energy spectrum. The electrons emitted from a field-emission tip originate from a quasi-equilibrium state in the metal very close to a thermal state, which is an example of the chaotic state. We do not expect an additional coherence to come into existence during the tunneling process and therefore suppose that the state remains chaotic also outside the metal111this might be no longer true for a polarized field-emission source , where a correlation between the spin and coordinate can come into existence; however, it can be shown that our results remain valid as long as the energy spectra of the spin components “up” and “down” are close to each other.

The chaotic state has been first introduced by Glauber for a mode of the electromagnetic field  as a state with a maximum entropy for a given occupation number of this mode. We generalize this definition to an electron field with the spin taken into account: the chaotic state is a state of a maximum entropy for given occupation numbers of the individual modes of the field and for a given spin polarization.

From the condition of the maximum entropy it follows that there is no correlation between the coordinate and the spin components of the chaotic state, which allows to treat the spin degree of freedom separately from the coordinate degrees of freedom. In calculating the correlation functions one can avoid in this way the formalism of spin-dependent electron field operators and use a relatively simple argumentation based on the probability theory. As will be seen in the following, this enables to express the correlation functions of a partially spin-polarized chaotic electron beam in terms of the degree of spin polarization and the correlation functions corresponding to a completely polarized beam, the form of which is known .

For our purpose it is fully sufficient to define the $`k`$-electron correlation function $`O^{(k)}(\stackrel{}{r}_1,t_1,\mathrm{},\stackrel{}{r}_k,t_k)`$ as the probability of detecting $`k`$ electrons at the $`k`$ space-time points $`(\stackrel{}{r}_1,t_1)`$, $`(\stackrel{}{r}_2,t_2)`$, …, $`(\stackrel{}{r}_k,t_k)`$. To get a more compact form of the equations, the shortened notation $`O_{12\mathrm{}k}^{(k)}`$ instead of $`O^{(k)}(\stackrel{}{r}_1,t_1,\mathrm{},\stackrel{}{r}_k,t_k)`$ will be used, each index $`i`$ standing for one space-time point $`(\stackrel{}{r}_i,t_i)`$. Analogous correlation functions for a spin-polarized beam will be denoted by $`G`$ instead of $`O`$, so for example the two-electron correlation function for a polarized beam is $`G_{1,2}^{(2)}`$. For a more precise definition of correlation functions in terms of electron field operators see e.g. .

## 3 Two spin-polarized sources

Consider an electron that has been emitted from the source. Its state can be described by the spin density operator $`\widehat{\rho }_s`$ that is represented by a Hermitian matrix of the second order in any orthonormal basis. As $`\widehat{\rho }_s`$ can be diagonalized by a unitary transformation, there exists an orthonormal basis $`\{|1,|2\}`$ in which $`\widehat{\rho }_s`$ has the diagonal form

$$\widehat{\rho }_s=\left(\begin{array}{cc}\rho _1& 0\\ 0& \rho _2\end{array}\right)=\rho _1|11|+\rho _2|22|$$
(1)
The states $`|1`$, $`|2`$ correspond to the spin orientation “up” and “down”, respectively, with respect to some particular axis $`\stackrel{}{a}`$ in space. In the case of photons, the states $`|1`$, $`|2`$ would describe two orthogonal polarizations, e.g. two linearly polarized waves with the polarization planes perpendicular to each other or a pair of the left- and right circularly polarized waves, depending on the properties of the source.

It is useful to express the probabilities $`\rho _1`$ and $`\rho _2`$ in terms of the degree of polarization. This quantity is defined as $`P=(\rho _1\rho _2)/(\rho _1+\rho _2)=\rho _1\rho _2`$ (provided that $`\rho _1\rho _2`$), which yields

$$\rho _1=\frac{1+P}{2},\rho _2=\frac{1P}{2}.$$
(2)
Now, the spin state of the ensemble of electrons coming from the source is completely described by the density operator (1). As can be seen from its form, $`\widehat{\rho }_s`$ corresponds to the situation as if just two types of electrons were emitted from the source: first, electrons polarized up with respect to the axis $`\stackrel{}{a}`$ and second, electrons polarized down with respect to $`\stackrel{}{a}`$. The probabilities that an electron emitted from the source is of the first or second type are $`\rho _1`$ or $`\rho _2`$, respectively. The fact that the spin density operator $`\widehat{\rho }_s`$ is diagonal means that there is no correlation between the two spin components up and down. At the same time, there is no correlation between the spin and the coordinate because the complete multi-electron state is chaotic. This allows the following consideration to be made.

We substitute formally the original electron source $`S`$ by two independent sources $`S_{\mathrm{up}}`$ and $`S_{\mathrm{down}}`$ that emit electrons polarized up and down with respect to the axis $`\stackrel{}{a}`$, respectively. If this should be correct, the sources $`S_{\mathrm{up}}`$ and $`S_{\mathrm{down}}`$ must have the same properties (of course except for the spin) as the original source $`S`$ has. This implies for example that they are located at the place of the original source $`S`$ and have the same energy spectrum. Moreover, the emission intensities of the sources $`S_{\mathrm{up}}`$ and $`S_{\mathrm{down}}`$ must be equal to $`\rho _1`$ and $`\rho _2`$ times the intensity of the original source $`S`$, respectively. In the following, the idea of substituting formally the original source by two polarized ones will be used for a direct derivation of the correlation function for a partially polarized electron beam. To see the idea more clearly, we will consider the simple case $`k=2`$ first and then go over to a general $`k`$.

## 4 Two-electron correlation function

The two-electron correlation function expresses the probability of the event of detecting two electrons at the space-time points $`(\stackrel{}{r}_1,t_1)`$ and $`(\stackrel{}{r}_2,t_2)`$. This event can happen in one of four ways that are distinguishable in principle because the coordinate and spin operators mutually commute:

1. the spins of both electrons are oriented up with respect to the axis $`\stackrel{}{a}`$,
2. the spins of both electrons are oriented down,
3. the spin of the electron at $`(\stackrel{}{r}_1,t_1)`$ is oriented down, the spin of the electron at $`(\stackrel{}{r}_2,t_2)`$ is oriented up,
4. the spin of the electron at $`(\stackrel{}{r}_1,t_1)`$ is oriented up, the spin of the electron at $`(\stackrel{}{r}_2,t_2)`$ is oriented down.

If cases 1 or 2 occur, then according to the previous section we deal with two electrons from the same polarized source. Therefore the two-electron correlation function is equal to the analogous correlation function $`G_{12}^{(2)}`$ for polarized electrons. On the other hand, if cases 3 or 4 occur, we deal with two electrons from two independent, oppositely polarized sources. The electrons are then completely uncorrelated and the correlation function is equal to the product of one-electron correlation functions, i.e., $`G_1^{(1)}G_2^{(1)}`$. As the probability that one electron is polarized up or down is $`\rho _1`$ or $`\rho _2`$, respectively, the probabilities of the cases 1.–4. are $`\rho _1^2`$, $`\rho _2^2`$, $`\rho _1\rho _2`$, and $`\rho _1\rho _2`$, respectively. The total correlation function $`O_{12}^{(2)}`$ can be then written as the weighed average of the polarized correlation functions,

$$O_{1,2}^{(2)}=(\rho _1^2+\rho _2^2)G_{1,2}^{(2)}+2\rho _1\rho _2G_1^{(1)}G_2^{(1)},$$
(3)
which is the desired result for $`k=2`$.

## 5 $`k`$-electron correlation function

In the derivation of the $`k`$-electron correlation function for a partially polarized chaotic electron beam we proceed in a completely analogous way. If $`k`$ electrons at the space-time points $`(\stackrel{}{r}_1,t_1),\mathrm{},(\stackrel{}{r}_k,t_k)`$ should be detected, there are $`2^k`$ possibilities how they can be polarized (instead of the four possibilities discussed in the previous section). We denote each of them by the sequence $`s_1,s_2,\mathrm{},s_k`$, every $`s_i`$ expressing the spin polarization of the electron at the point $`(\stackrel{}{r}_i,t_i)`$ and having one of two possible values, 1 for spin up and or 2 for spin down. The probability $`P(s_1,\mathrm{},s_k)`$ that the electrons have polarizations $`s_1,\mathrm{},s_k`$ is equal to $`\rho _1^{n_1}\rho _2^{n_2}`$, where $`n_1`$ and $`n_2`$ expresses how many times there appears 1 and 2 among the numbers $`s_1,\mathrm{},s_k`$, respectively. If $`O_{1,\mathrm{},k}^{(k)}(s_1,\mathrm{},s_k)`$ denotes the $`k`$-electron correlation function for this particular spin combination, the total $`k`$-electron correlation function can be written as

$$O_{1,\mathrm{},k}^{(k)}=\underset{s_1,\mathrm{},s_k}{}P(s_1,\mathrm{},s_k)O_{1,\mathrm{},k}^{(k)}(s_1,\mathrm{},s_k),$$
(4)
the sum being made over all the possibilities $`s_1,\mathrm{},s_k`$. Now, if the spin polarizations of the electrons are $`s_1,\mathrm{},s_k`$, the situation is the same as if we dealt with two independent sets of electrons — one set of $`n_1`$ up-polarized electrons originating from the source $`S_{\mathrm{up}}`$ and another set of $`n_2`$ down-polarized electrons originating from the source $`S_{\mathrm{down}}`$. The correlation function $`O_{1,\mathrm{},k}^{(k)}(s_1,\mathrm{},s_k)`$ factorizes therefore into a product of two correlation functions for polarized electrons:

$$O_{1,\mathrm{},k}^{(k)}(s_1,\mathrm{},s_k)=G^{(n_1)}\left(\{\stackrel{}{r},t\}_{\mathrm{up}}\right)G^{(n_2)}\left(\{\stackrel{}{r},t\}_{\mathrm{down}}\right).$$
(5)
Here $`\{\stackrel{}{r},t\}_{\mathrm{up}}`$ and $`\{\stackrel{}{r},t\}_{\mathrm{down}}`$ denote the sets of points at which the electrons are polarized up and down, respectively. Substituting Eq. (5) into Eq. (4) and re-arranging the sum, we can write the correlation function $`O_{1,\mathrm{}k}^{(k)}`$ as follows:

$$\begin{array}{c}O_{1,\mathrm{},k}^{(k)}=\left(\rho _1^k+\rho _2^k\right)G_{1,\mathrm{},k}^{(k)}\hfill \\ \hfill +\left(\rho _1^{k1}\rho _2+\rho _2^{k1}\rho _1\right)\left(G_{2,\mathrm{},k}^{(k1)}G_1^{(1)}+G_{1,3,\mathrm{},k}^{(k1)}G_2^{(1)}+\mathrm{}+G_{1,\mathrm{},k1}^{(k1)}G_k^{(1)}\right)\\ \hfill +(\rho _1^{k2}\rho _2^2+\rho _2^{k2}\rho _1^2)\left(G_{3,\mathrm{},k}^{(k2)}G_{1,2}^{(2)}+G_{2,4,\mathrm{},k}^{(k2)}G_{1,3}^{(2)}\mathrm{}+G_{1,\mathrm{},k2}^{(k2)}G_{k1,k}^{(2)}\right)+\mathrm{}\end{array}$$
(6)
To see the structure of such a series better, we write down the three- and four-electron correlation functions for illustration:

$$O_{1,2,3}^{(3)}=\left(\rho _1^3+\rho _2^3\right)G_{1,2,3}^{(3)}+\left(\rho _1^2\rho _2+\rho _2^2\rho _1\right)\left(G_{1,2}^{(2)}G_3^{(1)}+G_{1,3}^{(2)}G_2^{(1)}+G_{2,3}^{(2)}G_1^{(1)}\right),$$
(7)
$$\begin{array}{c}O_{1,2,3,4}^{(4)}=\left(\rho _1^4+\rho _2^4\right)G_{1,2,3,4}^{(4)}\hfill \\ \hfill +\left(\rho _1^3\rho _2+\rho _2^3\rho _1\right)\left(G_{1,2,3}^{(3)}G_4^{(1)}+G_{1,2,4}^{(3)}G_3^{(1)}+G_{1,3,4}^{(3)}G_2^{(1)}+G_{2,3,4}^{(3)}G_1^{(1)}\right)\\ \hfill +2\rho _1^2\rho _2^2\left(G_{1,2}^{(2)}G_{3,4}^{(2)}+G_{1,3}^{(2)}G_{2,4}^{(2)}+G_{1,4}^{(2)}G_{2,3}^{(2)}\right).\end{array}$$
(8)
In this way the $`k`$-electron correlation function for partially polarized electrons is expressed in terms of the one-, two- etc. up to the $`k`$-electron correlation functions for polarized electrons and the degree of polarization \[that is connected with $`\rho _1`$, $`\rho _2`$ via the relations (2)\].

The considerations made in the sections 3. – 5. as well as the results (3) and (6) can be applied step by step also to a chaotic photon field because up to now we have not supposed anything about the quantum statistics of the electrons. In fact, this statistics is hidden in the spin-polarized correlation functions $`G`$ and in this way it is reflected also in the correlation function $`O_{1,\mathrm{},k}^{(k)}`$. As has been mentioned, the similarity between electrons and photons in this sense comes from the same dimensions of the photon polarization Hilbert space and the electron spin Hilbert space.

We return to the electrons again. According to , the $`k`$-electron correlation function for a spin-polarized chaotic electron beam can be expressed as

$$G_{1,\mathrm{},k}^{(k)}=G_1^{(1)}G_2^{(1)}\mathrm{}G_k^{(1)}det\widehat{\gamma }$$
(9)
where $`\widehat{\gamma }=(\gamma _{ij})`$ is a matrix composed of the complex degrees of coherence $`\gamma _{ij}`$ at the points $`(\stackrel{}{r}_i,t_i)`$ and $`(\stackrel{}{r}_j,t_j)`$. Combining Eqs. (6) and (9), we arrive at the explicit form for the correlation function for a chaotic electron beam with an arbitrary spin polarization.

## 6 Influence of polarization on multi-electron correlations

To see how the spin polarization influences the correlations in an electron beam, we first return to the case of $`k=2`$. According to Eq. (9), the two-electron correlation function for a spin-polarized chaotic electron beam is equal to

$$G_{1,2}^{(2)}=G_1^{(1)}G_2^{(1)}(1|\gamma _{12}|^2)$$
(10)
where we used the fact that $`\gamma _{11}=\gamma _{22}=1`$. With the help of Eqs. (2) and (3), we then get for $`O_{1,2}^{(2)}`$

$$O_{1,2}^{(2)}=G_1^{(1)}G_2^{(1)}\left(1\frac{1+P^2}{2}|\gamma _{12}|^2\right).$$
(11)
If there were no correlation between the detection probabilities at the points $`(\stackrel{}{r}_1,t_1)`$ and $`(\stackrel{}{r}_2,t_2)`$, the correlation function $`O_{1,2}^{(2)}`$ would be simply equal to the product of the one-electron correlation functions $`O_1^{(1)}=G_1^{(1)}`$ and $`O_2^{(1)}=G_2^{(1)}`$. Therefore the second term in the parentheses in Eq. (11) is responsible for the two-electron correlation. As we can see, this term increases with the increasing degree of polarization of the beam, varying between one half for an unpolarized beam and unity for a completely polarized beam. For electrons, this result has been known  but it has been derived heuristically only until now. For photons a similar effect of the polarization on the correlation function is known .

Next we go over to the case of an arbitrary $`k`$. According to Eq. (6), the factor $`w=\left(\rho _1^k+\rho _2^k\right)`$ expresses the weight of the $`k`$-electron correlation in the partially polarized beam compared to a completely polarized beam because the $`k`$-electron correlation is given just by the correlation function $`G_{1,2,\mathrm{},k}^{(k)}`$. It is evident that for large $`k`$ the factor $`w`$ is small as soon as $`P`$ differs even slightly from unity. Figure 1 shows the dependence $`w(P)`$ for $`k=10`$. For example if $`P=0.7`$, then $`w`$ is equal to only about 0.2, so the ten-electron correlation is reduced to one fifth with respect to a polarized beam. Thus we must conclude that if no beam with a high degree of polarization is available, it is difficult to observe correlations of higher orders. On the other hand, from the experimental point of view observing even two-electron correlations is very difficult . In comparison to the extreme difficulty of, say, a ten-electron correlation experiment, making a 99%-polarized electron beam seems to be an easy task and in this way the spin degree of freedom should have no limitation effect on the measurement of multi-electron correlations.

## Acknowledgments

I would like to thank professor M. Lenc for helpful discussions. This work was supported by the Czech Ministry of Education, contract No. 144310006.