text:
# Comment on “Stability of Small Carbon-Nitride Heterofullerenes”

In a recent Letter , Schultz et al. proposed the existence of heterofullerenes Cn-xNx ($`40n50`$) based on the pattern of the peaks in the mass spectrum of carbon-nitride nanostructures produced by the arc-discharge technique. Using PM3 semiempirical calculations, they predicted the most stable structures of the N-substituted fullerenes, C33N9 and C44N6, to have $`C_3`$ symmetry. While some level of symmetry seems to maximize stability, the highest symmetry often sacrifices it, as in the case of fullerene C84. Using PM3 and density functional theory (DFT), we argue that a highly systematic investigation is needed to determine the most stable structures of both pristine and N-substituted fullerenes. We demonstrate this explicitly for two particular cases, C40 and C44N6, for which the authors of Ref. only considered four and two isomers, respectively.

Mathematically, there are 40 possible isomers for C40. We optimized the geometries of the 37 isomers with non-vanishing HOMO-LUMO gaps using the PM3 Hamiltonian and the B3LYP functional with STO-3G, 3- 21G and 6-31G\* basis sets as implemented in Gaussian 98 . The closed-shell formalism was used and the topological symmetry was maintained throughout. Isomers 1, 30 and 40 (note: the isomer index follows Ref.) have zero HOMO-LUMO gaps at the Hückel level of theory. Geometric convergence could not be achieved for these cases at the PM3 level and no further calculation was performed.

The most stable isomer of C40 is predicted to be isomer 38 ($`D_2`$) by all levels of theory. Analysis of the heats of formation (not shown) indicated that isomer 38 is not among the four isomers studied in Ref., although the authors did not identify the isomers. Isomers with low relative energies include isomer 39 ($`D_{5d}`$, 10.9 kcal/mol) and isomer 31 ($`C_s`$, 16.1 kcal/mol), see Fig. 1. All other isomers have energies higher than 20 kcal/mol. These results are in agreement with earlier predictions. The stabilities from different levels of theory agree with each other.

In Ref. , Schultz et al. showed an isomer with $`C_3`$ symmetry as the most stable structure for $`C_{50}`$ substituted with six nitrogen atoms (Fig.4b in Ref. ). Here we present a complete search of the N6-substituted isomers within the frame of C50:270 ($`D_3`$). Dividing the six N atoms into two groups of three atoms and substituting different groups of carbon atoms in C50:270 gives 64 possible structures. We first performed calculations at PM3 and B3LYP/STO-3G levels, which gave similar relative energies. Three structures have relative energies lower than 16 kcal/mol, whereas all others have relative energies higher than 40 kcal/mol. Further calculations at the B3LYP/6-31G\* level gave relative energies as 0.00 ($`D_3`$), 6.78 ($`C_3`$) and 9.63 ($`D_3`$) kcal/mol, confirming results from lower levels. The HOMO-LUMO gaps, 2.70 eV, 2.85 eV and 2.58 eV, respectively, are large by DFT standards, indicating their kinetic stability. Fig.2 shows the most stable structure of $`\mathrm{C}_{50}`$:270 with $`N_6`$-substitution having $`D_3`$ symmetry.

In summary, quantum chemical calculations at both DFT and PM3 levels indicate that either a complete survey or a more rational selection scheme is needed to determine the ground state structures of fullerenes.

Caption of Figures

Fig.1: Relative energy of isomers of fullerene $`\mathrm{C}_{40}`$. The isomer index follows Ref..

Fig.2: The most stable structure of $`\mathrm{C}_{50}`$:270 with $`N_6`$-substitution has $`D_3`$ symmetry.


format: text

text:
# Free hyperplane arrangements associated to labeled rooted trees

## 0 Introduction

This article is centered on labeled rooted trees. This kind of tree is very classical in combinatorics, since the enumerative results of Cayley . More recently, it has surfaced, with more algebraic structure, in the study of pre-Lie algebras  and in relation with a Hopf algebra in renormalization .

Here, we deal with other algebraic and geometric aspects of rooted trees. It is not yet clear if these new aspects are related to the previous ones.

The starting point is the definition of a hyperplane arrangement for each individual rooted tree. One can consider a rooted tree as a poset, and from this viewpoint directly follow the equations of the arrangement. Apart from being quite simple, these arrangements have the remarkable property of being free, in the sense of Saito . More precisely, the arrangement associated to a rooted tree is free with exponents given by the depths of the vertices of this tree.

After the first version of this article was completed, I learned from R. Stanley that this result is a consequence of the theory of graphical arrangements \[6, §3, Th. 3.3\] and supersolvable lattices \[11, Prop. 2.8, Ex. 4.6\]. A graphical arrangement is known to be free if and only if the corresponding graph is chordal. As the comparability graphs for rooted trees are indeed chordal, one can recover in this way Theorem 1. My proof of freeness avoids using these general theories and gives explicit information on logarithmic vector fields and differential forms.

Besides, it turns out that the intersection lattices of these hyperplane arrangements admit a neat combinatorial description in terms of forests of labeled rooted trees. This leads to the definition of a partial order on the set of forests labeled by a finite set, which contains intersection lattices as intervals.

Next, inspired by similarity with the study of binary leaf-labeled trees made in , the posets of forests are used to define coalgebras on forests. The dual algebras of these coalgebras are then shown to have a simple presentation by generators and relations.

Thanks to David Bessis for helpful discussions on the topology of the complement.

## 1 The category of labeled rooted trees

Let $`I`$ be a finite set. A tree on $`I`$ is a connected, simply connected graph on the vertex set $`I`$ endowed with a distinguished vertex called the root.

It will be convenient to use the following equivalent definition. A tree on $`I`$ is given by a partial order relation on the finite set $`I`$ with a unique minimal element (the root) and such that the interval between the root and any element of $`I`$ is a chain. The order relation corresponding to a tree $`T`$ is denoted by $`_T`$.

The depth of a vertex $`i`$ is defined to be the number of edges in the maximal chain from the root to $`i`$ and is denoted by $`0pt(i)`$, see Fig. 1.

By convention, trees are drawn with their root at the bottom and edges are oriented towards the root, in the decreasing direction for the poset structure. The valence of a vertex is the number of its incoming edges.

A linear tree is a tree whose vertices have valence at most $`1`$.

The category $`\mathrm{𝖳𝗋𝖾𝖾}`$ is defined as follows. Its objects are the trees on $`I`$ for all finite sets $`I`$. Morphisms from a tree on $`I`$ to a tree on $`J`$ are the maps from $`I`$ to $`J`$ which are morphisms of posets.

## 2 The hyperplane arrangement of a rooted tree

Let $`I`$ be a finite set. Consider the vector space $`^I`$ with coordinates $`x_i`$. Let $`T`$ be a tree on $`I`$. The equations

$$x_i=x_j\text{if}i_Tj$$
(1)
define a central hyperplane arrangement in $`^I`$ denoted by $`H_T`$.

Note that the complement of the union of these hyperplanes is an algebraic variety defined over $``$ which depends functorially from the tree in the category $`\mathrm{𝖳𝗋𝖾𝖾}`$ of rooted labeled trees defined above.

Let $`𝖰_T`$ be the product of all the equations $`x_ix_j`$ for $`i_Tj`$. It is called the defining form of the arrangement $`H_T`$.

Here is the first main result of this article.

###### Theorem 1

The arrangement $`H_T`$ is free. Its exponents are the depths of the vertices of $`T`$.

Remark that the arrangement $`H_T`$ for $`T`$ a linear tree on $`I`$ is simply the braid arrangement given by the reflection hyperplanes of the symmetric group of $`I`$. Therefore the classical freeness of this braid arrangement is recovered as a special case of Theorem 1.

The proof of Theorem 1 uses the Saito criterion of freeness \[10, Th. 1.8 (ii)\] involving logarithmic vector fields and is the object of the next section.

## 3 Logarithmic vector fields

First one can associate a vector field $`\theta _i`$ to each vertex $`i`$ of $`T`$. Define the vector field $`\theta _i`$ on $`^I`$ by

$$\theta _i=\underset{j_Ti}{}\left(\underset{k<_Ti}{}(x_kx_j)\right)_j.$$
(2)
The degree of $`\theta _i`$ is one less than the depth of $`i`$ in $`T`$.

This definition can be restated as

$$\theta _i(x_j)=\{\begin{array}{cc}_{k<_Ti}(x_kx_j)\hfill & \text{ if }i_Tj,\hfill \\ 0\hfill & \text{ otherwise.}\hfill \end{array}$$
(3)
Let $`\mathrm{Der}(H_T)`$ be the space of logarithmic vector fields for the arrangement $`H_T`$, i.e. the space of polynomial vector fields $`\theta `$ on $`^I`$ such that $`\alpha `$ divides $`\theta (\alpha )`$ for all hyperplanes $`\alpha `$ of $`H_T`$.

###### Proposition 1

The vector fields $`\theta _i`$ belong to $`\mathrm{Der}(H_T)`$.

* Proof. Let $`j`$ and $`k`$ be distinct vertices of $`T`$ with $`j_Tk`$.

Assume first that neither $`i_Tj`$ nor $`i_Tk`$. Then $`\theta _i(x_jx_k)`$ is zero.

Assume then that $`i_Tj`$ but $`i_Tk`$. As $`T`$ is a tree, these conditions together with $`j_Tk`$ implies that $`j<_Ti`$. It follows that $`\theta _i(x_jx_k)=_{\mathrm{}<_Ti}(x_{\mathrm{}}x_k)`$ is divisible by $`x_jx_k`$.

Assume now that $`i_Tj`$, then also $`i_Tk`$ by transitivity. Then $`\theta _i(x_jx_k)=_{\mathrm{}<_Ti}(x_{\mathrm{}}x_j)_{\mathrm{}<_Ti}(x_{\mathrm{}}x_k)`$ is divisible by $`x_jx_k`$, because this expression vanishes when $`x_j=x_k`$.

Therefore $`\theta _i(x_jx_k)`$ is always divisible by $`x_jx_k`$.

One can now prove Theorem 1.

* Proof. By Formula (3), the matrix $`\mathrm{\Theta }=[\theta _i(x_j)]`$ is triangular for the poset structure on $`I`$ given by $`_T`$. The determinant of the matrix $`\mathrm{\Theta }`$ is therefore

$$\underset{\genfrac{}{}{0pt}{}{(k,i)}{k<_Ti}}{}(x_kx_i),$$
(4)
which is the defining form $`𝖰_T`$ of the arrangement $`H_T`$. Hence the Saito criterion applies and the arrangement $`H_T`$ is free. The exponents are by definition one more than the degrees of the vector fields $`\theta _i`$, which are one less than the depths of the vertices of $`T`$.

Freeness of the arrangement $`H_T`$ means that $`\mathrm{Der}(H_T)`$ is a free module over the ring of polynomials on $`^I`$. The proof via the Saito criterion implies further that the set of vector fields $`(\theta _i)_{iI}`$ is a basis of $`\mathrm{Der}(H_T)`$.

## 4 Logarithmic differential forms

Define a differential $`1`$-form $`\omega _i`$ for each vertex $`i`$ of $`T`$ by

$$\omega _i=\underset{j_Ti}{}\left(\underset{\genfrac{}{}{0pt}{}{k_Ti}{kj}}{}\frac{1}{x_kx_j}\right)dx_j.$$
(5)
Recall the definition of the space of logarithmic differential forms for an hyperplane arrangement . A differential form $`\omega `$ with coefficients in the field of rational functions on $`^I`$ is called a logarithmic differential form for $`H_T`$ if $`𝖰_T\omega `$ and $`𝖰_Td\omega `$ are polynomial forms on $`^I`$.

###### Proposition 2

The forms $`\omega _i`$ are logarithmic $`1`$-forms for $`H_T`$.

* Proof. It is clear that $`𝖰_T\omega _i`$ is polynomial. On the other hand, one has

$$d\omega _i=\underset{j_Ti}{}\underset{\genfrac{}{}{0pt}{}{k_Ti}{kj}}{}\left(\underset{\genfrac{}{}{0pt}{}{\mathrm{}_Ti}{\genfrac{}{}{0pt}{}{\mathrm{}j}{\mathrm{}k}}}{}\frac{1}{x_{\mathrm{}}x_j}\right)\frac{1}{(x_kx_j)^2}dx_kdx_j.$$
(6)
Consider now the coefficient of $`dx_kdx_j`$ in $`d\omega _i`$. It is sufficient to prove that it has only a simple pole at $`x_k=x_j`$. This follows from the vanishing of

$$\left(\underset{\genfrac{}{}{0pt}{}{\mathrm{}_Ti}{\genfrac{}{}{0pt}{}{\mathrm{}j}{\mathrm{}k}}}{}\frac{1}{x_{\mathrm{}}x_j}\right)\left(\underset{\genfrac{}{}{0pt}{}{\mathrm{}_Ti}{\genfrac{}{}{0pt}{}{\mathrm{}j}{\mathrm{}k}}}{}\frac{1}{x_{\mathrm{}}x_k}\right)$$
(7)
when $`x_k=x_j`$.

As the arrangement $`H_T`$ is free, it is known that the space of logarithmic $`1`$-forms is a free module over the the ring of polynomials on $`^I`$. Furthermore this module is in duality with the module of logarithmic vector fields by restriction of the duality between vector fields and $`1`$-forms .

More precisely, one has the following proposition in the case of $`H_T`$.

###### Proposition 3

The set of logarithmic $`1`$-forms $`(\omega _i)_{iI}`$ is the dual basis to the basis $`(\theta _i)_{iI}`$.

* Proof. One has

$$\begin{array}{c}\omega _i,\theta _i^{}=\underset{i^{}_Tj_Ti}{}\left(\underset{\genfrac{}{}{0pt}{}{k_Ti}{kj}}{}\frac{1}{x_kx_j}\right)\left(\underset{j^{}<_Ti^{}}{}x_j^{}x_j\right)\hfill \\ \hfill =\underset{i^{}_Tj_Ti}{}\left(\underset{\genfrac{}{}{0pt}{}{i^{}_Tk_Ti}{kj}}{}\frac{1}{x_kx_j}\right).\end{array}$$
(8)
The proposition now follows from Lemma 1 below.

###### Lemma 1

The sum

$$\underset{i^{}_Tj_Ti}{}\left(\underset{\genfrac{}{}{0pt}{}{i^{}_Tk_Ti}{kj}}{}\frac{1}{x_kx_j}\right)$$
(9)
equals $`1`$ if $`i^{}=i`$ and vanishes otherwise.

* Proof. This sum is clearly equal to $`1`$ when $`i=i^{}`$ and $`0`$ when $`i^{}>_Ti`$. Assume now that $`i^{}<_Ti`$. Then the sum is homogeneous of negative degree. As poles are at most of order one, it is sufficient to prove that all residues vanish. The residue at $`x_{j_0}=x_{k_0}`$ is given by the value of

$$\left(\underset{\genfrac{}{}{0pt}{}{i^{}_Tk_Ti}{\genfrac{}{}{0pt}{}{kj_0}{kk_0}}}{}\frac{1}{x_kx_{j_0}}\right)\left(\underset{\genfrac{}{}{0pt}{}{i^{}_Tk_Ti}{\genfrac{}{}{0pt}{}{kj_0}{kk_0}}}{}\frac{1}{x_kx_{k_0}}\right)$$
(10)
at $`x_{j_0}=x_{k_0}`$, which is zero.

## 5 Topology of the complement

Let $`M_T`$ denote the complexified complement of the union of all hyperplanes of $`H_T`$. Using the general theory of supersolvable arrangements  and the results of  on graphical arrangements, the complement $`M_T`$ can be precisely described.

One can map a tree $`T`$ to the comparability graph $`\mathrm{\Gamma }_T`$ for the relation $`_T`$. In this way, a rooted tree is seen as a special case of a graph on $`I`$. Then $`H_T`$ is the graphical arrangement corresponding to $`\mathrm{\Gamma }_T`$. It is also easy to see that the graph $`\mathrm{\Gamma }_T`$ is chordal (see  for the definition).

Recall from \[6, §3\] the notions of simplicial vertex and vertex elimination ordering of a graph. For the graph $`\mathrm{\Gamma }_T`$, one has

###### Lemma 2

The leaves of $`T`$ (maximal vertices for $`_T`$) are simplicial vertices. Any total order extending the partial order $`_T`$ on $`I`$ gives a vertex elimination ordering.

Such an ordering will be called a leaf-removal ordering.

As $`\mathrm{\Gamma }_T`$ is chordal, Theorem 3.3 of  implies that $`H_T`$ is a supersolvable arrangement and that each leaf-removal ordering gives a modular chain in $`L_T`$. By results of Terao , each modular chain in a supersolvable arrangement gives rise to a description of the complement as an iterated fibration of punctured $``$.

Hence the complement $`M_T`$ is an iterated fibration of the spaces $`S_i`$ for $`iI`$, where $`S_i`$ is a finite set of distinct points in $``$ of cardinality the depth of $`i`$ in $`T`$. The order of the fibration tower is given by the chosen leaf-removal ordering of $`I`$. From this, one can deduce the following proposition.

###### Proposition 4

The space $`M_T`$ is a $`K(\pi ,1)`$ space and its fundamental group is an iterated extension of free groups on $`0pt(i)`$ generators for $`iI`$, in the order given by any leaf-removal ordering of $`I`$.

## 6 Cohomology of the complement

One can recall the results of Orlik and Solomon  on the cohomology of the complexified complement.

###### Proposition 5

The cohomology of the complex complement of $`H_T`$ is generated by the differential forms $`d(\mathrm{log}(x_ix_j))`$ for $`i_Tj`$.

In the same way, the similar results of Gelfand and Varchenko  on the filtered algebra of locally constant integral functions on the real complement of a real hyperplane arrangement can be applied.

It would be interesting to find the relations for these algebras, i.e. to describe the dependent sets of hyperplanes. As a first step in this direction, one can give a generating set of relations between the linear forms $`\alpha _{i,j}=x_ix_j`$ for $`i_Tj`$.

###### Lemma 3

Any linear relation between the linear forms $`\alpha _{i,j}`$ for $`i_Tj`$ is a linear combination of relations

$$\alpha _{i,j}+\alpha _{j,k}\alpha _{i,k}=0,$$
(11)
with $`i_Tj_Tk`$.

* Proof. Let $`\mathrm{}`$ be the root of $`T`$. Consider an arbitrary linear relation

$$\underset{i_Tj}{}\lambda _{i,j}\alpha _{i,j}=0.$$
(12)
This relation can be rewritten, using all relations

$$\alpha _{i,j}=\alpha _{\mathrm{},j}\alpha _{\mathrm{},i},$$
(13)
as a relation of the following kind:

$$\underset{i\mathrm{}}{}\mu _i\alpha _{\mathrm{},i}=0.$$
(14)
Now the coefficients $`\mu _i`$ vanish because the forms $`\alpha _{\mathrm{},i}`$ are obviously linearly independent. Note that among relations (11) only relations (13) involving the root are really used.

## 7 The lattice of a labeled rooted tree

Let $`L_T`$ be the intersection lattice of the arrangement $`H_T`$, i.e. the lattice of intersections of the hyperplanes of $`H_T`$ for the reverse inclusion order.

### 7.1 Characteristic polynomial

The characteristic polynomial of $`H_T`$ can be deduced from a theorem of Terao on free arrangements (Main Theorem of , see also \[9, Th. 5.1\]). Recall that the characteristic polynomial of the hyperplane arrangement $`H_T`$ is

$$\chi _T(y)=\underset{aL_T}{}\mu (a)y^{dima},$$
(15)
where $`\mu `$ is the Möbius function of the lattice $`L_T`$.

###### Proposition 6

The characteristic polynomial of the arrangement $`H_T`$ is

$$\chi _T(y)=\underset{iI}{}(y0pt(i)),$$
(16)
where $`0pt(i)`$ is the depth of $`i`$ in $`T`$.

The number of chambers (connected components) in the real complement is related by a theorem of Zaslavsky  to the value at $`y=1`$ of the characteristic polynomial .

###### Proposition 7

The number of chambers in the real arrangement $`H_T`$ is given by

$$\underset{iI}{}(0pt(i)+1).$$
(17)
### 7.2 Partial order $``$ on the set of forests

Here is defined a partial order on the set of forests on $`I`$, denoted by $``$. This poset will be shown in the next paragraphs to contain (as intervals) all lattices $`L_T`$ for trees $`T`$ on $`I`$. A similar (but different) partial order on forests has appeared in  and Exercise 5.29 of .

Let $`I`$ be a finite set. A forest on $`I`$ is a simply connected graph on the vertex set $`I`$ where each connected component has a distinguished vertex called its root. Therefore a forest on $`I`$ is a partition of $`I`$ together with a rooted tree on each part. The partition of $`I`$ underlying a forest $`F`$ is denoted by $`\pi (F)`$. The set of forests on $`I`$ is denoted by $`\mathrm{𝖿𝗈𝗋}(I)`$. Vertices of a forest which are not roots are called nodes. Let $`N(F)`$ be the set of nodes of a forest $`F`$.

One can see a forest on $`I`$ as a structure of poset on $`I`$. The partial order is the ascendance relation, i.e. a vertex $`i`$ is lower than $`j`$ if they belong to the same tree in $`F`$ and $`i`$ is on the path from $`j`$ to the root of this tree. This order relation is denoted by $`_F`$. This is an extension of the definition of a tree as a poset in §1.

Let us define the partial order $``$ on $`\mathrm{𝖿𝗈𝗋}(I)`$ as follows. Let $`F`$ and $`F^{}`$ be two forests on $`I`$. Then set $`F^{}F`$ if

* the partition $`\pi (F^{})`$ is finer than $`\pi (F)`$,
* each tree of $`F^{}`$ is induced by $`F`$ as a poset.

This clearly defines a partial order relation.

###### Lemma 4

If $`F^{}F`$, then $`N(F^{})`$ is contained in $`N(F)`$.

* Proof. A root in $`F`$ is a minimal element for $`_F`$ so it is also a minimal element for $`_F^{}`$ i.e. a root in $`F^{}`$.

###### Lemma 5

If $`F^{}F`$ and $`N(F^{})=N(F)`$, then $`F=F^{}`$.

* Proof. If $`F`$ and $`F^{}`$ have the same nodes, they have the same roots, hence the same number of connected components. Therefore their partitions are the same, hence $`F=F^{}`$.

The poset $`(\mathrm{𝖿𝗈𝗋}(I),)`$ has a unique minimal element, which is the forest made uniquely of roots and will be denoted by $`\widehat{0}`$.

### 7.3 Intervals for $``$

Let $`T`$ be a fixed tree on $`I`$. This section gives a simple description of the interval between $`\widehat{0}`$ and $`T`$ in the poset $`(\mathrm{𝖿𝗈𝗋}(I),)`$.

###### Lemma 6

A forest $`FT`$ is uniquely determined by its partition $`\pi (F)`$.

* Proof. Given $`\pi (F)`$, one can reconstruct $`F`$ by inducing the partial order $`_T`$ on the parts of $`\pi (F)`$.

###### Lemma 7

A partition $`\pi `$ can be written $`\pi (F)`$ for a forest $`FT`$ if and only if each part of $`\pi `$ has a unique minimal element for the partial order induced by $`_T`$.

* Proof. If $`\pi =\pi (F)`$, then each part of $`\pi `$ is a tree, so has a unique minimal element. Conversely, if a part $`c`$ of $`\pi `$ has a unique minimal element, then in fact it is a tree, because a poset induced by a tree is either a tree or a forest.

###### Lemma 8

Let $`FT`$ and $`F^{}T`$. Then $`FF^{}`$ if and only if $`\pi (F)`$ is finer than $`\pi (F^{})`$.

* Proof. By definition of the partial order $``$, if $`FF^{}`$ then $`\pi (F)`$ is finer than $`\pi (F^{})`$. Conversely, assume that $`\pi (F)`$ is finer than $`\pi (F^{})`$. As $`F`$ and $`F^{}`$ are recovered from their partitions by inducing $`_T`$, $`F`$ is in fact induced from $`F^{}`$, so $`FF^{}`$.

### 7.4 Lattices $`L_T`$ and forests

In this section, one obtains a description of the lattice $`L_T`$ in terms of forests.

###### Proposition 8

The elements of $`L_T`$ are in bijection with the forests $`F`$ on $`I`$ which satisfy $`FT`$.

* Proof. Let $`a`$ be an element of $`L_T`$, i.e. the intersection of some hyperplanes $`\alpha _{i,j}`$ with $`i_Tj`$.

Define a relation $`_a`$ on $`I`$ by setting $`i_aj`$ if $`\alpha _{i,j}`$ vanishes on $`a`$. Remark that $`i_aj`$ implies $`i_Tj`$. That $`_a`$ is a partial order follows from relations (11). Let $`\pi _a`$ be the partition of $`I`$ given by the connected components of $`_a`$.

Now consider a part $`c`$ of $`\pi _a`$. Let us prove that $`c`$ has a unique minimal element. Let $`i`$ and $`j`$ be two minimal elements of $`c`$ and assume additionally that there exists $`k`$ in $`c`$ such that $`i_ak`$ and $`j_ak`$. One has either $`i_Tj`$ or $`j_Ti`$. Then relations (11) imply that $`i_aj`$ or $`j_ai`$, so that in fact $`i=j`$. Now any two minimal elements $`i`$ and $`j`$ in $`c`$ can be connected by an alternating chain

$$i_ak_0_ai_0_ak_1_ai_1_a\mathrm{}_ak_N_aj,$$
(18)
where one can assume without restriction that $`i_0,\mathrm{},i_{N1}`$ are minimal elements. Then a repeated application of the preceding argument implies that $`i=i_0=i_1=\mathrm{}=i_{N1}=j`$. Therefore each part $`c`$ of $`\pi _a`$ has a unique minimal element for $`_a`$.

The partial order $`_a`$ on each part $`c`$ is induced by $`_T`$. Indeed let $`i,j`$ be two elements of $`c`$. As said before, if $`i_aj`$, then $`i_Tj`$. Conversely, assume that $`i_Tj`$. Let $`k`$ be the minimal element of $`c`$ for $`_a`$. Then $`k_ai`$ and $`k_aj`$, so relations (11) implies that $`i_aj`$.

Therefore to each element $`a`$ of $`L_T`$ is associated a forest $`F_aT`$, which is defined as a poset by $`i_{F_a}j`$ if and only if $`\alpha _{i,j}`$ vanishes on $`a`$.

Conversely, one can map each forest $`FT`$ to the intersection $`a_F`$ of the hyperplanes $`\alpha _{i,j}`$ for $`i_Fj`$. This set of linear forms is closed with respect to the relations (11). Therefore the linear forms of $`H_T`$ vanishing on $`a_F`$ are exactly the $`\alpha _{i,j}`$ for $`i_Fj`$.

Furthermore, it is easy to see that the element of $`L_T`$ associated in this way to the forest $`F_a`$ is exactly $`a`$.

This gives the sought-for bijection.

###### Theorem 2

The interval between the minimal forest $`\widehat{0}`$ and a tree $`T`$ is isomorphic to the lattice $`L_T`$, i.e. the reverse inclusion order in $`L_T`$ is mapped by the bijection to the relation $``$.

* Proof. Let $`a`$ and $`b`$ in $`L_T`$ and let $`F_a`$ and $`F_b`$ be the corresponding forests.

That $`a`$ is smaller than $`b`$ in $`L_T`$ means that each equation $`\alpha _{i,j}=0`$ satisfied in $`a`$ is also satisfied in $`b`$. This imply that the partition $`\pi (F_a)`$ is finer than the partition $`\pi (F_b)`$.

Conversely, if the partition $`\pi (F_a)`$ is finer than the partition $`\pi (F_b)`$, then each tree of $`a`$ is induced by a tree of $`b`$ as a poset hence each relation satisfied in $`a`$ is also satisfied in $`b`$.

For an example of lattice $`L_T`$, see Fig. 2.

This result shows that there is some similarity between the poset $`(\mathrm{𝖿𝗈𝗋}(I),)`$ on rooted vertex-labeled forests and the poset on forests of leaf-labeled binary trees introduced in  and further studied in , notably because the characteristic polynomials of intervals have a nice factorization in both cases. This will motivate the construction of a coalgebra in §8.

###### Proposition 9

The dimension of a element $`aL_T`$ is mapped by the bijection to the number of nodes of the associated forest $`F_a`$.

* Proof. It is known that $`L_T`$ is a ranked lattice. All maximal chains have the same length and contain one element in each dimension. On the other hand, consider a maximal chain in the interval $`[\widehat{0},T]`$ in $`\mathrm{𝖿𝗈𝗋}(I)`$. As the set of nodes must grow at each step of the chain by Lemma 5, it must grow by one element only. From this follows the lemma.

###### Lemma 9

The interval between $`\widehat{0}`$ and a forest $`F`$ is a lattice.

* Proof. There exists a tree $`T`$ such that $`FT`$. To build one such $`T`$, choose one root $`r`$ of $`F`$ and glue the other roots of $`F`$ to some vertices of the tree with root $`r`$. Therefore the interval $`[\widehat{0},F]`$ is an interval in the lattice $`[\widehat{0},T]`$.

###### Lemma 10

Let $`T`$ be a tree, $`F_1`$ and $`F_2`$ be forests in $`L_T`$ and $`F`$ be the supremum of $`F_1`$ and $`F_2`$. Assume that $`N(F_1)N(F_2)=\mathrm{}`$. Then $`N(F)=N(F_1)N(F_2)`$.

* Proof. Let $`N_1=N(F_1)`$ and $`N_2=N(F_2)`$ for short. Let $`R`$ be the complement of $`N_1N_2`$ in $`I`$. By Lemma 4, one has an inclusion $`N_1N_2N(F)`$.

As the lattice $`L_T`$ is graded by the number of nodes, it is enough to prove that there exists a forest $`F`$ greater than $`F_1`$ and $`F_2`$ with nodes $`N_1N_2`$.

Consider the partition $`\pi `$ of $`I`$ which is the sup of the partitions $`\pi _1`$ and $`\pi _2`$ associated to $`F_1`$ and $`F_2`$ respectively.

Let $`c`$ be an arbitrary part of $`\pi `$ endowed with the partial order $``$ induced from $`_T`$. Then any minimal element of $`c`$ is in $`R`$. Assume on the contrary that it is in $`N_1`$ for example. Then it cannot be minimal in $`c`$, for it is already not minimal in the part of $`\pi _1`$ in which it is contained, because it is a node there. The same is true for $`N_2`$ by symmetry.

Now take $`rR`$. As $`I`$ is finite, the part $`c`$ of $`\pi `$ containing $`r`$ can be built by iterated closures of $`\{r\}`$ with respect to the partitions $`\pi _1`$ and $`\pi _2`$. Closing $`\{r\}`$ with respect to $`\pi _1`$ can only add elements of $`N_1`$. Then closing with respect to $`\pi _2`$ can only add elements of $`N_2`$. This goes on in the same way, adding in an alternating way elements of $`N_1`$ and $`N_2`$ until the full part $`c`$ of $`\pi `$ containing $`r`$ is reached. This implies that each part of $`\pi `$ contains an unique element of $`R`$, which is its minimum.

Therefore $`\pi `$ defines a forest $`F`$ in $`L_T`$, which is greater than $`F_1`$ and $`F_2`$ by construction and has $`R`$ as its set of roots. So $`N(F)=N_1N_2`$ and the proof is done.

### 7.5 Cardinality

Here is computed the cardinality polynomial of the graded lattice $`L_T`$, which counts elements of $`L_T`$ according to their rank. More precisely, a recursion is found for a refinement of the cardinality polynomial.

Define the refined generating polynomial

$$C_T(y,z)=\underset{FL_T}{}y^{\mathrm{crk}(F)}z^{\mathrm{Stump}(F)},$$
(19)
where $`\mathrm{Stump}(F)`$ is one less than the cardinal of the part of $`\pi (F)`$ containing the root of $`T`$ and $`\mathrm{crk}(F)`$ is the corank of $`F`$ (i.e. one less than the number of roots). The value at $`z=1`$ of $`C(y,z)`$ is the cardinality polynomial.

Let $`T`$ be a tree on $`I`$. Let $`o(T)`$ be the tree on $`I\{j\}`$ obtained from $`T`$ by grafting the root of $`T`$ on a new root $`j`$.

###### Proposition 10

One has

$$C_{o(T)}(y,z)=zC_T(y,z)+yC_T(y,1+z).$$
(20)
* Proof. Let $`iI`$ be the root of $`T`$. Let $`F`$ be a forest in $`L_{o(T)}`$.

Assume first that $`F`$ does not have a tree with root $`i`$. The set of such forests in $`L_{o(T)}`$ is in bijection with the set of forests in $`L_T`$ in the following way. Necessarily $`i`$ belongs to a tree of $`F`$ with root $`j`$, and $`i`$ is the only vertex related by an edge to $`j`$. By removing $`j`$, one can therefore define a forest $`F^{}`$, with a tree of root $`i`$. This forest $`F^{}`$ is in $`L_T`$. Conversely, by grafting back $`j`$ under the root $`i`$ in any forest $`F^{}`$ in $`L_T`$, one gets an element $`F`$ of $`L_{o(T)}`$. This gives the sought-for bijection.

Through this bijection, the number of roots is unchanged between $`F`$ and $`F^{}`$. The number of nodes in the component of $`j`$ in $`F`$ is one more than the number of nodes in the component of $`i`$ in $`F^{}`$. This gives the term $`zC_T(y,z)`$.

Assume now that $`F`$ does have a tree with root $`i`$. The set of such forests in $`L_{o(T)}`$ is in bijection with the set of pairs $`(F^{},S)`$ where $`F^{}`$ is a forest in $`L_T`$ and $`S`$ is a subset of the set of nodes in the component of $`i`$ in $`F^{}`$. Consider the partition of $`I`$ defined by gathering the parts containing $`i`$ and $`j`$ in the partition of $`I\{j\}`$ defined by $`F`$, then removing $`j`$. Taking the order induced by $`_T`$ on each part of this partition define a forest $`F^{}`$ in $`L_T`$. The forest $`F^{}`$ differs from $`F`$ only by the replacement of the trees $`t_i`$ with root $`i`$ and $`t_j`$ with root $`j`$ in $`F`$ by a tree $`t_i^{}`$ of root $`i`$ in $`F^{}`$. The set $`S`$ is defined as the set of nodes in the component of $`j`$ in $`F`$. Conversely, one can recover $`F`$ from the data of $`F^{}`$ and $`S`$. It is enough to recover the trees $`t_i`$ and $`t_j`$. The tree $`t_i`$ of $`F`$ is induced by the tree $`t_i^{}`$ on the set of vertices not in $`S`$. The tree $`t_j`$ can be defined by replacing $`i`$ by $`j`$ in the tree induced on $`\{i\}S`$ by the tree $`t_i^{}`$.

The number of roots in $`F`$ is one more than the number of roots in $`F^{}`$. The number of nodes in the component of $`j`$ in $`F`$ is the cardinal of $`S`$. This gives the term $`yC_T(y,1+z)`$.

On the other hand, the lattice $`L_T`$ is isomorphic to the product of the lattices $`L_{T_k}`$ where the $`T_k`$ are the trees with root of valence one obtained by separately grafting back the different subtrees of the root. For example, Fig. 3 depicts this decomposition for the rooted tree of Fig. 1.

###### Proposition 11

One has

$$C_T(y,z)=\underset{k}{}C_{T_k}(y,z).$$
(21)
* Proof. The bijection between $`L_T`$ and $`_kL_{T_k}`$ can be described as follows. An element of $`L_T`$ is a forest $`F`$ with a unique tree containing the root of $`T`$. One can decompose this tree into trees contained in $`T_k`$ as in Fig. 1. Each other tree of $`F`$ is contained in some unique $`T_k`$. Collecting trees according to the $`T_k`$ in which they are contained, one gets a collection of forests in $`L_{T_k}`$, which is the image of $`F`$ in $`_kL_{T_k}`$. The statement of the proposition follows easily.

Together, Prop. 10 and Prop. 11 give a recursive procedure for computing the refined cardinality polynomial.

## 8 Coalgebras on forests

In this section is defined a coalgebra, using the poset $`\mathrm{𝖿𝗈𝗋}(I)`$.

Let $`F`$ be a forest on $`I`$ and $`N`$ be a subset of $`N(F)`$. Define

$$\gamma (F,N)=\underset{\genfrac{}{}{0pt}{}{F^{}F}{N(F^{})=N}}{}F^{}.$$
(22)
As this sum is without multiplicity, $`\gamma (F,N)`$ can also be seen as a set.

From now on, modules, algebras and coalgebras are in the category of $``$-graded abelian group with Koszul sign rules for the tensor product.

An orientation $`o`$ of a forest $`F`$ is a maximal exterior product of the set $`N(F)\{R_F\}`$, where $`R_F`$ is an auxiliary element. An oriented forest is a tensor product $`oF`$, where $`o`$ is an orientation of the forest $`F`$.

Let $`𝖥(I)`$ be the free $``$-module on the set of oriented forests on $`I`$ modulo the relations $`(o)F=(oF)`$. This module is graded by $`\mathrm{deg}(oF)=\mathrm{\#}N(F)`$. A map $`\mathrm{\Delta }`$ from $`𝖥(I)`$ to $`𝖥(I)𝖥(I)`$ is defined as follows:

$$\mathrm{\Delta }(oF)=\underset{N(F)=N_1N_2}{}(o_1\gamma (F,N_1))(o_2\gamma (F,N_2)),$$
(23)
where the orientations satisfy $`o=o_1ro_2`$ modulo $`R=R_1rR_2`$.

###### Lemma 11

Let $`F`$ be a forest in $`L_T`$. Let $`N_1`$ be a subset of $`N(F)`$ and fix a partition $`N_1=N_1^{}N_1^{\prime \prime }`$. Then (not taking care of orientations), one has

$$\underset{F_1\gamma (F,N_1)}{}\gamma (F_1,N_1^{})\gamma (F_1,N_1^{\prime \prime })=\gamma (F,N_1^{})\gamma (F,N_1^{\prime \prime }).$$
(24)
* Proof. It is sufficient to give a bijection between the set of triples $`(F_1^{},F_1^{\prime \prime },F_1)`$ satisfying

$`F_1`$ $`\gamma (F,N_1),`$ (25)
$`F_1^{}`$ $`\gamma (F_1,N_1^{}),`$ (26)
$`F_1^{\prime \prime }`$ $`\gamma (F_1,N_1^{\prime \prime }),`$ (27)
and the set of pairs $`(F_1^{},F_1^{\prime \prime })`$ satisfying

$`F_1^{}`$ $`\gamma (F,N_1^{}),`$ (28)
$`F_1^{\prime \prime }`$ $`\gamma (F,N_1^{\prime \prime }).`$ (29)
In one direction, a triple is mapped to a pair by forgetting $`F_1`$.

In the other direction, let $`F_1^{}`$ and $`F_1^{\prime \prime }`$ be a pair as above. By Lemma 10, the supremum $`F_1`$ of $`F_1^{}`$ and $`F_1^{\prime \prime }`$ (well-defined by Lemma 9) satisfies the conditions $`F_1^{}F_1`$, $`F_1^{\prime \prime }F_1`$ and $`N(F)=N_1`$. By Lemma 5, this is the unique forest satisfying these conditions.

###### Proposition 12

Formula (23) endows $`𝖥(I)`$ with the structure of a cocommutative coassociative counital coalgebra with coproduct $`\mathrm{\Delta }`$.

* Proof. Cocommutativity is clear from Formula (23). Coassociativity is deduced from the following formula for the double coproduct, which is a consequence of Lemma 11: (details are left to the reader)

$$\underset{N_F=N_1N_2N_3}{}(o_1\gamma (F,N_1))(o_2\gamma (F,N_2))(o_3\gamma (F,N_3)),$$
(30)
where $`o=o_1ro_2so_3`$ modulo $`R=R_1rR_2sR_3`$. The counit is the projection to the degree-zero component, which is one-dimensional.

###### Lemma 12

Let $`F`$ be a forest on $`I`$ and $`F_1F_2`$ be a term in the coproduct $`\mathrm{\Delta }(F)`$. Then the set of nodes of $`F_1`$ and $`F_2`$ are disjoint in $`I`$.

* Proof. Obvious from Formula (23).

###### Lemma 13

Let $`F`$ be a forest on $`I`$ and $`F_1F_2\mathrm{}F_k`$ be a term in the iterated coproduct of $`F`$. Assume that one has $`i_F_{\mathrm{}}j`$ for some $`\mathrm{}`$. Then one has $`i_Fj`$. In words, each ascendance relation in a term of a coproduct of $`F`$ is also satisfied in $`F`$.

* Proof. By definition of the partial order $``$, each tree in each $`F_{\mathrm{}}`$ is induced by $`F`$ as a poset.

## 9 Algebras on forests

### 9.1 Partial order $``$ on forests

Consider the following partial order $``$ on the set of forests on $`I`$. One sets $`FF^{}`$ if the identity of $`I`$ is a morphism of posets from $`(I,_F)`$ to $`(I,_F^{})`$. Note that in order to check if $`FF^{}`$, it is enough to check the relations $`i_F^{}j`$ for all edges $`ij`$ of $`F`$ .

Observe that this partial order is completely different from the partial order $``$ introduced in §7.2. For example, there are distinct forests with the same nodes which are comparable for $``$ (compare to Lemma 5).

### 9.2 Generators and relations

Recall that the ambient category is that of $``$-graded abelian groups with Koszul sign rules. So there are appropriate signs to be inserted whenever two elements are exchanged.

In this category, consider the commutative associative unital algebra $`𝖬(I)`$ defined by generators $`\mathrm{\Omega }_{i,j}`$ of degree $`1`$ for $`ij`$ in $`I`$ and relations

$$\mathrm{\Omega }_{i,k}\mathrm{\Omega }_{j,k}=0,$$
(31)
for $`i,j,k`$ pairwise different in $`I`$, and

$$\mathrm{\Omega }_{i_0,i_1}\mathrm{\Omega }_{i_1,i_2}\mathrm{}\mathrm{\Omega }_{i_n,i_0}=0,$$
(32)
for $`n1`$ and pairwise different $`i_0,\mathrm{},i_n`$ in $`I`$.

###### Proposition 13

The algebra $`𝖬(I)`$ is spanned by monomials $`m_F`$ indexed by the set $`\mathrm{𝖿𝗈𝗋}(I)`$ of forests of rooted trees on $`I`$.

* Proof. One can represent (up to sign) a monomial in the generators as an oriented graph on $`I`$ by drawing an oriented edge $`ij`$ for the generator $`\mathrm{\Omega }_{i,j}`$.

The relation (31) says exactly that graphs containing two edges going out of the same vertex vanish. Therefore any cycle in a non-vanishing graph is oriented.

The relations (32) say exactly that graphs containing an oriented cycle vanish.

It follows that the algebra $`𝖬(I)`$ is spanned by monomials indexed by oriented simple graphs on $`I`$ with no cycle and no divergence of arrows, i.e. rooted forests on $`I`$. For each forest $`F`$, choose (well defined up to sign) a monomial $`m_F`$.

In fact, this set of monomials $`(m_F)_F`$ form a basis of $`𝖬(I)`$. This property can be seen directly or will follow from Theorem 3.

### 9.3 Isomorphism

Consider now the dual algebra $`𝖥^{}(I)`$ of the coalgebra $`𝖥(I)`$, for the pairing $`:𝖥^{}(I)𝖥(I)`$. Let $`(F^{})_F`$ be the basis of $`𝖥^{}(I)`$ dual to the basis $`F`$ of $`𝖥(I)`$ for this pairing.

Define elements $`F_{i,j}^{}`$ of degree $`1`$ in $`𝖥^{}(I)`$ by

$$F_{i,j}^{},F_{k,\mathrm{}}=\delta _{i,k}\delta _{j,\mathrm{}},$$
(33)
where $`F_{k,\mathrm{}}`$ is the unique forest of degree $`1`$ on $`I`$ with only one node, labeled $`\mathrm{}`$ and attached to a root labeled $`k`$. The orientation of $`F_{k,\mathrm{}}`$ is prescribed by $`\mathrm{}R`$.

###### Theorem 3

The algebra $`𝖥^{}(I)`$ is isomorphic to the algebra $`𝖬(I)`$.

First, one has to define a map from $`𝖬(I)`$ to $`𝖥^{}(I)`$.

###### Proposition 14

There is a map $`\rho `$ from $`𝖬(I)`$ to $`𝖥^{}(I)`$ satisfying

$$\rho (\mathrm{\Omega }_{i,j})=F_{i,j}^{}.$$
(34)
* Proof. One has to show that the elements $`F_{i,j}^{}`$ of $`𝖥^{}(I)`$ satisfy the relations (31) and (32).

To check the relation (31), it is sufficient to prove that the term $`F_{i,k}F_{j,k}`$ does not appear in the coproduct $`\mathrm{\Delta }(F)`$ of any forest $`F`$ on $`I`$. This follows from Lemma 12, because $`k`$ is a node of both $`F_{i,k}`$ and $`F_{j,k}`$.

To check the relation (32), it is sufficient to prove that the term

$$F_{i_0,i_1}F_{i_1,i_2}\mathrm{}F_{i_n,i_0}$$
(35)
does not appear in the iterated coproduct of any forest $`F`$ on $`I`$. Assume that it does appear in the iterated coproduct of $`F`$. Then by Lemma 13, one has

$$i_0_Fi_1_Fi_2_F\mathrm{}_Fi_n_Fi_0,$$
(36)
which would mean that there is a cycle in $`F`$, which is absurd.

Therefore the map $`\rho `$ is well-defined.

The crucial part of the proof of Theorem 3 is the following Lemma.

###### Lemma 14

Let $`F`$ be a forest on $`I`$. The image by $`\rho `$ of the monomial $`m_F`$ is the sum (with coefficients $`\pm 1`$) of $`G^{}`$ over the set of all forests $`G`$ which are $``$ than $`F`$ and have the same nodes as $`F`$.

* Proof. Write $`m_F`$ as a product $`\mathrm{\Omega }_{i_0,j_0}\mathrm{}\mathrm{\Omega }_{i_n,j_n}`$ over the set of edges of $`F`$, in some order. Then $`\rho (m_F)`$ is $`F_{i_0,j_0}^{}\mathrm{}F_{i_n,j_n}^{}`$.

Let $`G`$ be a forest on $`I`$. The coefficient of $`G^{}`$ in $`F_{i_0,j_0}^{}\mathrm{}F_{i_n,j_n}^{}`$ is (up to sign) the coefficient of $`F_{i_0,j_0}\mathrm{}F_{i_n,j_n}`$ in the iterated coproduct of $`G`$.

Assume that the coefficient of $`G^{}`$ in $`\rho (m_F)`$ is non-zero. Then the coefficient of $`F_{i_0,j_0}\mathrm{}F_{i_n,j_n}`$ in the iterated coproduct of $`G`$ is non-zero. Lemma 13 implies, for each edge $`ij`$ of $`F`$, that $`i_Gj`$. Hence by definition of $``$, one has $`FG`$.

By homogeneity of the product, one also has that $`G`$ and $`F`$ have the same number of nodes and the same number of roots. As $`FG`$, each root of $`F`$ is also a root of $`G`$, so $`F`$ and $`G`$ have the same roots and nodes.

Now consider any forest $`G`$ with the same nodes and roots as $`F`$ and satisfying $`FG`$. For such a $`G`$, the tensor $`F_{i_0,j_0}\mathrm{}F_{i_n,j_n}`$ does appear with coefficient $`\pm 1`$ in the iterated coproduct of $`G`$, in the term of the sum (23) corresponding to the partition of $`N(G)=\{j_0,j_1,\mathrm{},j_n\}`$ into singletons. Indeed, for any $`k`$, $`FG`$ implies $`i_k_Gj_k`$, which in turn implies that $`F_{i_k,j_k}`$ belongs to the set $`\gamma (G,\{j_k\})`$.

The proof of Theorem 3 can now be completed.

* Proof. By Lemma 14, the image by $`\rho `$ of the set $`(m_F)_F`$ which spans $`𝖬(I)`$ is a basis of $`𝖥^{}(I)`$. As the rank of $`𝖥^{}(I)`$ is the cardinal of $`\mathrm{𝖿𝗈𝗋}(I)`$, one deduces that $`(m_F)_F`$ is in fact a basis of $`𝖬(I)`$. So $`\rho `$ is an isomorphism.


text:
# 1 Multiparton scatterings and Jets in proton-proton collisions

## 1 Multiparton scatterings and Jets in proton-proton collisions

The description of jet production in hadronic collisions with a momentum transfer of the order of the c.m. energy, where the process is characterized by a single large energy scale factor, represents one of the most successful applications of the conventional, fixed$`x`$, perturbative QCD. In this regime higher orders in the perturbative expansion of the elementary interaction are related directly to processes where an increasing number of large $`p_t`$ jets are produced and virtual corrections are a rapidly converging expansion in powers of the strong coupling constant. The simplest perturbative scheme is however no more adequate when two or more different scales become relevant. An interesting case where two scales play an important role is when the c.m. energy of the partonic process, although much larger than the hadronic scale, is nevertheless very small as compared with the c.m. energy of the hadronic interaction, namely $`\widehat{s}s`$, where $`\widehat{s}xx^{}s`$, with $`x`$, $`x^{}`$ the momentum fractions of the interacting partons and $`s`$ the Mandelstam invariant of the hadronic collision. In this kinematical regime the typical final state is characterized by the presence of many jets and, while the partonic collision is still well described by the conventional perturbative approach, the overall semi-hard component of the hadronic interaction acquires a much richer structure. A recent analysis performed by CDF of the jet evolution and underlying event in $`p\overline{p}`$ collisions shows that, while the leading jet is fairly well described by QCD Monte Carlo models in a wide kinematical range, the models fail do describe correctly the underlying event, which is populated by several further jets at a relatively low $`p_t`$. From the theoretical point of view one may get in touch with the problem looking at the cross section to produce large $`p_t`$ jets, integrated on the exchanged momentum with the cutoff $`p_{cut}`$. When $`p_{cut}`$ is moved towards relatively small values, the integrated cross section, being divergent for $`p_{cut}0`$, becomes very large already well inside the kinematical regime where perturbation theory is meaningful, so that one faces a unitarity problem. Indeed the cross section for production of jets with $`p_t>5`$GeV measured by UA1 is about $`1520mb`$, in $`p\overline{p}`$ collisions at a c.m. energy of $`900`$ GeV.

In fig.2 the total, the inelastic non-diffractive and the cross section to produce jets with $`p_t>5`$GeV (minijets) are plotted as a function of energy, showing that one foresees a high energy regime where the integrated inclusive cross section of jet production (long-dashed curve in the figure) exceeds the value of the total inelastic cross section. If considering hadron-nucleus and nucleus-nucleus collisions, the unitarity problem in jet production appears at larger transverse momenta and with smaller nucleon-nucleon c.m. energies.

The origin of the unitarity problem is in the large flux of partons, active for producing large $`p_t`$ processes at high energies. When the incoming partons flux is very large there is a finite probability of producing events where different pairs of partons interact independently in a given hadronic interaction, with momentum exchange above $`p_{cut}`$, generating states with many jets at a relatively large $`p_t`$. In the integrated inclusive cross section of jet production, those events count with the multiplicity factor of the partonic collisions and, as a consequence, the inclusive cross section is not bounded by the value of the total inelastic cross section. In the kinematical region where the inclusive cross sections of jet production is comparable to the total inelastic cross section, the average number of partonic interactions in a typical inelastic event is close to one and the probability of multiple parton collisions is large. Interestingly in this regime the single scattering expression of perturbative QCD is still meaningful, and represents correctly the integrated inclusive cross section, which, as required by the cancellation property discussed by Abramovsky, Gribov and Kancheli for interactions where multiple exchanges take place, is given by the single scattering term expression. Notice that, since in the inclusive each partonic collision contributes with its multiplicity, the inclusive cross section is proportional to the average number of multiple interactions, which ultimately is also the reason of the simple theoretical result of the AGK cancellation. On the other hand, precisely for the same motivation, the inclusive cross section gives only a rather limited information on the production dynamics.

To gain a deeper insight one needs to look at different and less inclusive physical observables. From the experimental point of view the simplest quantity of this kind is the semi-hard cross section, namely the cross section which counts all events with at least one jet produced, which is related to the probability of not having any hard interactions at all in a inelastic event. The semi-hard cross section is hence bounded by the value of the total inelastic cross section and therefore characterized by an intrinsic dimensional scale factor. A consequence is that the semi-hard cross section, contrarily to the inclusive cross section, cannot be obtained by evaluating the single scattering expression of perturbative QCD (where the only relevant dimensional factors are the kinematical variables). In fact the semi-hard cross section needs an infinite number of perturbative terms to be evaluated, corresponding to all possible processes with any number of multiple parton collisions. To obtain a complete information on the semi-hard interaction dynamics one needs to measure systematically all the moments of the distribution of multiple parton collisions, which implies measuring all inclusive cross sections with any number of produced jets and isolating the corresponding multiple parton scattering contributions. A given configuration with many jets may be in fact originated in various ways with different elementary partonic processes. Each multiple scattering term is nevertheless characterized by a different dimensional scale factor so each multiparton scattering process has a peculiar dependence on the c.m. energy and on the lower cutoff in $`p_t`$, while the typical pattern of the final state produced is obtained by superposing single scattering events. The different contributions to the semi-hard cross section, with a given number of elementary partonic collisions, may be therefore disentangled by looking at the energy and cutoff dependence of the cross section and by studying the pattern of the final states produced. A possible way to obtain the dimensional scale factors characterizing the different multiparton scatterings, is to measure the relative rates of production of 1, 2, 3 etc. jets as a function of the lower cutoff in $`p_t`$. By moving from the large to a relatively low $`p_t`$ region the ratios in fact change, as compared to the expectations bases on the conventional single scattering production mechanism, because of the increasingly large contribution of multiple scatterings at relatively low $`p_t`$. The measurement of the azimuthal correlations between charged tracks at relatively large $`p_t`$ is a further tool to identify production processes characterized by independent hard collisions at the parton level.

The non-perturbative input to a multiparton interaction is a multiparton distribution, which contains independent informations on the hadron structure, as compared to the one-body parton distributions usually considered in large-$`p_t`$ processes. Multiparton distributions depend in fact linearly on the multiparton correlations of the hadron structure. Notice that multi-parton scatterings have been already implemented in some QCD Monte Carlo program, to the purpose of describing the minimum bias event in high energy hadronic collisions. A basic hypothesis there is however that all input multi-parton distributions are trivial (namely poissonians at a fixed impact parameter), which amounts neglecting all multiparton correlations. The difficulties of the QCD Monte Carlo programs to describe the underlying event in hard collisions at $`1.8`$TeV, even after switching on multi-parton scatterings, and the results of the analysis of the simplest case of multi-parton scattering, the double parton collision, point on the contrary in the direction of the existence of non trivial correlations effects in the hadron structure. An exhaustive description of the hard component of the interaction, in high energy hadronic collisions, requires therefore an explicit investigation of each different multiparton scattering process and the measurement of all various correlation parameters.

## 2  Double parton scattering

The simplest case of multiparton interaction is the double collision. Correspondingly the simplest state produced is represented by four jets with transverse momenta above the cutoff $`p_{cut}`$ and balanced in pairs. The same state may also be produced by the leading QCD $`24`$ process. While the latter process can be estimated at the three level without much effort, the evaluation of the double parton scattering contribution is in principle much more uncertain. The main reason of uncertainty is represented by the non-perturbative input needed to the double parton collision, the two-body parton distributions, which contains the information on the two-body parton correlations. All discussions on the double parton collision process rely on assumptions on the two-body parton correlations. Since multiple parton interactions are a sizable effect at low $`x`$, where the parton flux is large, correlations in momentum fraction should not be a major effect, so that a reasonable hypothesis is to neglect correlations in fractional momenta in the multi-parton distributions. Not all possible correlations can however be neglected, since the interacting partons must be correlated in transverse space, belonging to the same hadron. It seems therefore reasonable, at least in the low $`x`$ region, to make the hypothesis that the only relevant correlations are those in the transverse parton coordinates. With this assumption, on rather general grounds, the inclusive double parton scattering cross section is given by the product of two single parton scattering cross sections with a scale factor, which depends smoothly on the c.m. energy and on the cut-off and which, in general, depends on the parton process considered. One might in fact expect different kinds of partons to have a different distribution in transverse space inside the hadron. The double scattering cross section $`\sigma _D(A,B)`$ for the two parton processes $`A`$ and $`B`$ is then written as

$$\sigma _D(A,B)=\frac{m}{2}\underset{ijkl}{}\mathrm{\Theta }_{kl}^{ij}\sigma _{ij}(A)\sigma _{kl}(B)$$
(1)
where $`\sigma _{ij}(A)`$ is the hadronic inclusive cross section for two partons of kind $`i`$ and $`j`$ to undergo the hard interaction $`A`$, while the partons $`k`$ and $`l`$ undergo the hard interaction $`B`$ with cross section $`\sigma _{kl}(B)`$. The factor $`m`$ equals 1 when the two parton processes $`A`$ and $`B`$ are identical, while its value is $`2`$ if they are distinguishable.

The factors

$$\mathrm{\Theta }_{kl}^{ij}=d^2bF_k^i(b)F_l^j(b)$$
(2)
are geometrical coefficients, with dimensions of inverse cross section. The function $`F_k^i(b)`$ represents the density of the pair of partons $`k,i`$ in a hadron as a function of the relative transverse distance $`b`$, normalized to one. Since the partonic interactions $`A`$ and $`B`$, being characterized by a scale of momentum transfer much larger than the hadronic dimension ($`p_t1/R`$) are well localized in transverse space inside the hadron, the relative transverse distance between the pair $`k,i`$ and between the pair $`l,j`$ of the two colliding hadrons must be equal, in order to have the alignment necessary for the double interaction to take place. The cross section is then obtained by summing over all possible configurations, with the interacting parton pairs at the same relative transverse distance $`b`$ in the two hadrons.

Double parton collisions have been measured by CDF looking at final states with three minijets and one photon. The cross section has been expressed as

$$\sigma _D=\frac{1}{\sigma _{eff}}\sigma _S(\gamma j)\sigma _S(jj)$$
(3)
which may be obtained from Eq.1 making the assumption that the geometrical coefficients $`\mathrm{\Theta }_{kl}^{ij}`$ do not depend on the different kinds of interacting partons $`ijkl`$. The experiment gives as a output the value of the scale factor:

$$\sigma _{eff}=14.5\pm 1.7_{2.3}^{+1.7}\mathrm{mb}$$
(4)
Given the kinematical range available to the CDF experiment, the sum on the different kinds of partons is dominated by the contribution where three of the indices in Eq.1 refer to gluons and one to quarks, so that basically $`\sigma _{eff}1/\mathrm{\Theta }_{gg}^{qg}`$.

While, at least in the limited kinematical range available, the scale factor does not show evidence of dependence on the fractional momenta of the interacting partons, consistently with the hypothesis of no correlation in the $`x`$-variables, the actual measured value of $`\sigma _{eff}`$ points, on the contrary, towards the existence of non-trivial correlations of the proton structure in transverse space. In the case of no correlations, one would in fact expect $`\sigma _{eff}=h\sigma _{NSD}`$, where $`h`$ is a geometrical enhancement factor and $`\sigma _{NSD}`$ the nucleon non-single-diffractive cross section (namely the inelastic cross section minus the single diffractive cross section) whose value, measured by CDF, is $`50.9\pm 1.5`$ mb. The geometrical enhancement factor keeps into account that multiple parton collisions are more likely to take place at small impact parameters, where the overlap of the matter distributions of the two interacting hadrons is larger. The indication obtained, considering different possibilities for the density of partons in space, is that the value of $`h`$ should be close to $`1/2`$, which would give a $`\sigma _{eff}`$ roughly twice as big as the measured value. One may then argue that the experimental indication points towards the existence of non trivial correlation effects in transverse space.

A natural implication of the existence of correlations in transverse space is that different pairs of partons are characterized by different typical transverse distances, which amounts to a non negligible dependence of the scale factors $`\mathrm{\Theta }_{kl}^{ij}`$ on the different indices. Even if this is the case, the double parton scattering cross section may still be expressed by the factorized form in Eq.3 used by the CDF experimental analysis. When $`\mathrm{\Theta }_{kl}^{ij}`$ has a sizable depence on the indices, $`\sigma _{eff}`$ however not only changes with the kind of double parton process considered, but also depends on the c.m. energy of the hadronic collision and on the phase space cuts applied, since, given a definite final state, the luminosity of the different kinds of initial state partons contributing to the process changes both with energy and with the cuts applied to the final state. On the other hand the indication of non-trivial correlations in transverse space implies a structure of the proton much richer than obtainable through deep inelastic scattering experiments with electron beams, where the information accessible is limited by the pointlike structure of the projectile.

To access the transverse space structure one needs therefore to measure the different scale factors which characterize the multiple parton collision processes. By selecting final states as $`jjjj`$, $`b\overline{b}b\overline{b}`$, $`c\overline{c}c\overline{c}`$ one would measure $`\mathrm{\Theta }_{gg}^{gg}`$, while final states with a prompt photon as, $`\gamma jjj`$, $`\gamma jb\overline{b}`$ or $`\gamma jc\overline{c}`$ will allow one to obtain $`\mathrm{\Theta }_{gg}^{qg}`$ and to test, by comparing with the CDF result, its energy dependence. The scale factor $`\mathrm{\Theta }_{qg}^{qg}`$ may be measured by looking at double parton collisions with a Drell-Yan pair accompanied by two minijets or by a pair of heavy quarks. Another interesting case is that of the production of two equal sign $`W`$ bosons, which, at relatively low transverse momenta, is dominated by double parton collisions and which allows one to have information on the correlation in transverse space of valence quarks.

All final states produced by double parton collisions can be produced also by the more conventional leading QCD mechanism, where the hard process is initiated by two partons. The contribution of multiparton scatterings is however enhanced with energy, in such a way that, while the probability of a double parton collision generating two equal sign $`b`$-quarks is rather small at Tevatron energy, one may estimate a cross section of the order of $`1`$ $`\mu b`$ to observe two equal sign $`b`$ quarks with $`|\eta |.9`$ at LHC. To compare the two sources of two equal sign $`b`$ quark production, in the ALICE detector, the rates of the two processes are plotted in the fig. 4. The c.m. energies are 14 TeV and 5.5 TeV. In the upper figures the curves are plotted against $`p_t^{min}`$, which is the smallest among all the transverse momenta of the produced quarks. All the quarks are inside the pseudorapidity interval $`|\eta |.9`$. The lower figures represent the distributions of the pseudorapidity difference between two $`b`$-quarks. In this last case the two $`b`$-quarks only are within $`|\eta |.9`$. All processes have been evaluated at the lowest order in $`\alpha _s`$; a factor $`k=5.5`$ has been however introduced to account for higher order corrections, which have been assumed to be the same in the $`22`$ and in the $`24`$ processes. The value of the $`k`$-factor has been obtained using the results on heavy quark production in the $`k_t`$-factorization approach. As a scale factor for the double collision term the value of $`\sigma _{eff}`$ measured by CDF has been used. The leading QCD $`24`$ contribution is represented by the dashed lines and the double parton scattering term by the continuous lines. In the low $`p_t^{min}`$ region double parton scatterings dominate over the leading QCD $`24`$ process by a large factor. Preliminary estimates indicate that the effect of multiple parton interactions is even more pronounced when considering $`c\overline{c}`$ pairs production. The large values obtained for the double parton scattering cross sections are an indication that on one hand one should be able to isolate easily the double parton scattering contributions while, on the other, there should be a sizable probability of observing also triple, quadruple etc. parton collision processes.

As the single scattering term is proportional to the average number of partonic collisions, the double is proportional to the dispersion in the distribution of multiple collisions. The relatively small value measured for $`\sigma _{eff}`$, whose inverse is proportional to the double scattering term, is therefore an indication of large fluctuations in the number of produced jets. One therefore expects a relatively large number of events without much activity and a relatively small number of events with many more large $`p_t`$ fragments than average. Given the large cross section expected at the LHC a similar effect should be observed also in charm production. At the LHC the inclusive cross section of $`c\overline{c}`$ production, integrated over all phase space, might in fact be of the order of $`20`$ mb, while the corresponding double parton scattering cross section might reach values as high as $`12`$ mb. One would then observe a relatively small number of events with charm, with the unusual feature of being however characterized by a considerably large number of $`c\overline{c}`$ pairs. In such a scenario triple and even quadruple parton collisions leading to several $`c\overline{c}`$ pairs would be easily measurable.

The simplest estimate of the triple scattering cross section may be obtained by neglecting all correlations in $`x`$ and assuming that the scale factors do not depend on the different species of interacting partons. In that case all unknowns of the triple scattering process are reduced to a single quantity, so that, for three identical interactions, one may write

$$\sigma _T=\frac{1}{3!}\frac{\sigma _S^3}{\tau \sigma _{eff}^2}$$
(5)
where $`\tau `$ is the unknown, dimensionless quantity (of order unity) to be measured by the triple scattering experiment, while $`\sigma _{eff}`$ is the scale factor already measured in a double parton scattering experiment. More general expressions of the triple, quadruple etc. cross sections may be easily written introducing different scale factors, depending on the different species of interacting partons and expressed through integrals of the n-parton densities in transverse space, in a way analogous to the double scattering cross section in Eq.s (1)(2).

## 3 Summary

All multiple parton scattering effects increase considerably at the LHC, enhancing features of the typical inelastic event as the increase of $`p_t`$ with multiplicity, already observed by UA1, and changing the distribution in multiplicity of the jets produced with a relatively low $`p_t`$. A characteristic feature of multiparton interactions is the dependence of the cross section on dimensional scale factors, whose origin is geometrical and which are introduced into dynamics by the non-perturbative input to the process. Differently with respect to the usual non-perturbative input to a large $`p_t`$ \- fixed $`x`$ interaction, the non-perturbative input to a multiparton process is in fact a multiparton distribution, which is a dimensional quantity and contains information on the non perturbative structure independent on the knowledge of the one-body structure functions usually investigated in large $`p_t`$ processes. In the simplest case of a double collision the information is represented by the factors $`\mathrm{\Theta }_{kl}^{ij}`$ discussed above. It should be stressed that one cannot obtain the factors $`\mathrm{\Theta }_{kl}^{ij}`$ by testing the hadron with an elementary probe. Multiparton scatterings are hence a unique tool for a deeper investigation on the hadron structure, which have the potential of providing a rather interesting new physical output. The scale factors are in fact a measure of the typical transverse distance between different pairs of partons inside the hadron, so their determination gives one access to the three-dimensional structure of the hadron.


text:
# 1 Fermion masses in MeV.

Fermion mass and mixing patterns from a rotating mass matrix

TSOU Sheung Tsun

Mathematical Institute, Oxford University

24–29 St. Giles’, Oxford OX1 3LB

United Kingdom

tsou @ maths.ox.ac.uk

Abstract

It is shown that all existing data on mixing between up and down fermion states (i.e. CKM matrix and neutrino oscillations) and on the hierarchical quark and lepton mass ratios between generations are consistent with the two phenomena being both consequences of a mass matrix rotating in generation space with changing energy scale. As a result, the rotation of the mass matrix can be traced over some 14 orders of magnitude in energy from the mass scale of the $`t`$-quark at 175 GeV to below that of the atmospheric neutrino at 0.05 eV. This is a summary of recent work done in collaboration with Chan Hong-Mo and José Bordes.

In celebration of the 80th birthday of Professor Yang
May we meet again in 10, 20, 30, …years

By a rotating mass matrix we mean that the mass matrix of a fermion species, for example any one of $`U`$ the up quarks ($`t,c,u`$), $`D`$ the down quarks ($`b,s,c`$), $`L`$ the charged leptons ($`\tau ,\mu ,e`$) and $`N`$ the neutrinos ($`\nu _\tau ,\nu _\mu ,\nu _e`$), not only has scale-dependent eigenvalues but also eigenvectors which depend on scale. This last property means that the eigenvectors change orientation or rotate in generation space.

This is not just a hypothetical situation, because already in the Standard Model the renormalization group equation for the $`U`$ mass matrix has a term

$$16\pi ^2\frac{dU}{dt}=\frac{3}{2}DD^{}U+\mathrm{},$$
(1)
where the factor $`D^{}U=V`$ is the CKM quark mixing matrix. Now this matrix is experimentally found to be non-diagonal, meaning that even if $`U`$ is diagonal at a certain scale, it will become nondiagonal as a result of running to a different scale, at which when it is re-diagonalized the eigenvector will have rotated from its previous orientation. However, given that the off-diagonal elements of the CKM matrix are small, this effect can usually be neglected in practice in the Standard Model. This may very well not be the case in extensions of the Standard Model, where other forces may contribute to the mass matrix rotation to an observable extent.

In this note we shall turn the argument around and seek experimental evidence of a rotating mass matrix, in the manner we shall now detail.

There are two well established experimental facts which the Standard Model does not explain, namely fermion mass hierarchy and fermion mass mixing. The masses of the up and down quarks, and the charged fermions differ by more than 1–2 orders of magnitude as one goes from one generation to the next , as can be seen in Table 1.

The absolute values of the various CKM matrix elements have been measured to a good accuracy :

$$\left(\begin{array}{ccc}V_{ud}\hfill & V_{us}\hfill & V_{ub}\hfill \\ V_{cd}\hfill & V_{cs}\hfill & V_{cb}\hfill \\ V_{td}\hfill & V_{ts}\hfill & V_{tb}\hfill \end{array}\right)=\left(\begin{array}{ccc}0.97420.9757\hfill & 0.2190.226\hfill & 0.0020.005\hfill \\ 0.2190.225\hfill & 0.97340.9749\hfill & 0.0370.043\hfill \\ 0.0040.014\hfill & 0.0350.043\hfill & 0.99900.9993\hfill \end{array}\right)$$

The absolute values of the leptonic MNS mixing matrix, on the other hand, are not so well determined at present, but from neutrino oscillation experiments  we know that the mixing is in general considerably larger than the corresponding CKM mixing. The experimental estimates are:

$$\left(\begin{array}{ccc}U_{e1}\hfill & U_{e2}\hfill & U_{e3}\hfill \\ U_{\mu 1}\hfill & U_{\mu 2}\hfill & U_{\mu 3}\hfill \\ U_{\tau 1}\hfill & U_{\tau 2}\hfill & U_{\tau 3}\hfill \end{array}\right)=\left(\begin{array}{ccc}& 0.40.7& 0.00.15\\ & & 0.560.83\\ & & \end{array}\right)$$

Since the Standard Model gives no explanation for these two very remarkable experimental facts, one is tempted to seek other origins for them, and if one could find a single mechanism which could give rise to both, it would certainly provide a very interesting and promising avenue of study .

We now make the following rotating hypothesis:

> The rotating mass matrix gives rise to all observed mixing and lower generation masses.

We note as a side remark that this hypothesis is made and implemented in the Dualized Standard Model , from which we obtain good agreement with experiment111Specifically, with 3 real parameters fitted to data, it gives correctly to within present experimental bounds the following measured quantities: the mass ratios $`m_c/m_t`$, $`m_s/m_b`$, $`m_\mu /m_\tau `$, all 9 elements $`|V_{rs}|`$ of the CKM matrix, plus the 2 elements $`|U_{\mu 3}|`$ and $`|U_{e3}|`$ of the MNS matrix. It gives further by interpolation sensible though inaccurate estimates for the following: the mass ratios $`m_u/m_t`$, $`m_d/m_b`$, $`m_e/m_\tau `$ and the solar neutrino angle $`U_{e2}`$. Moreover, numerous detailed predictions have been made, and tested against data, in flavour-violation effects over a wide area comprsising meson mass differences, rare hadron decays, $`e^+e^{}`$ collisions, and muon-electron conversion in nuclei, with further predictions on effects as far apart in energy as neutrinoless double-beta decays in nuclei and cosmic ray air showers beyond the GZK cut-off of $`10^{20}`$ eV at the extreme end of the present observable energy range..

So we start with a mass matrix which is of rank 1, and which remains factorized on running, so that at any scale we have only one non-zero eigenvalue $`m_T`$:

$$m=m_T\left(\begin{array}{c}\xi \\ \eta \\ \zeta \end{array}\right)(\xi \eta \zeta )=m_T\left(\begin{array}{ccc}\xi ^2& \xi \eta & \xi \zeta \\ \xi \eta & \eta ^2& \eta \zeta \\ \xi \zeta & \eta \zeta & \zeta ^2\end{array}\right),$$
(2)
Thus the whole mass matrix can be encapsulated by one single normalized rotating vector $`v=(\xi ,\eta ,\zeta )`$ (without loss of generality we may assume $`\xi \eta \zeta `$). Note that the eigenvalue $`m_T`$ depends on the fermion species $`T=U,D,L,N`$.

Care has to be taken in defining physical masses and states when the mass matrix runs with scale. In our case when the mass matrix is given by a single vector we can adopt the following procedure  which guarantees that:

* lepton state vectors are always orthogonal,
* mixing matrix is always unitary,
* mass hierarchy is automatic.

First we run $`m`$ to a scale $`\mu `$ such that $`\mu =m_T(\mu )`$; this value we can reasonably call the mass of the highest generation. To fix ideas, let us concentrate on the $`U`$ type quarks $`t,c,u`$. The corresponding eigenvector $`v_t`$ is then the state vector of the $`t`$ quark. Having fixed this, we now know that the $`c`$ and $`u`$ lie in the 2-dimensional subspace $`V`$ orthogonal to $`v_t`$. As we go down in scale the eigenvector $`v`$ rotates so that $`V`$ is no longer the null eigenspace, and the projection of $`m`$ onto $`V`$ is a $`2\times 2`$ matrix, again of rank 1. We now repeat the procedure for this submatrix and determine both the mass and the state of the $`c`$ quark (Figure 1).

Once the $`c`$ state is determined, we know the $`u`$ state as well, as being the third vector of the orthonormal triad $`(t,c,u)`$. The $`u`$ mass is similarly determined.

The above procedure can be repeated for the other three types of fermions222Neutrinos will need further special treatment which we shall omit here. Instead see reference .. The direction cosines of the two triads $`(t,c,u)`$ and $`(b,s,d)`$, in other words, the 9 inner products, will give us the CKM matrix, Figure 2.

Similarly for the MNS mixing matrix of the leptons.

The above procedure takes a much simpler form when we have only two generations, and we shall in fact study this case first, as a planar approximation for the full three generation case, to better illustrate the methodology and the results .

Consider the up quarks first. When applied to this simple case, the procedure detailed above for defining masses and state vectors of flavour states gives the state vector $`v_t`$ of $`t`$ as the single massive eigenstate $`v`$ of the $`U`$-quark mass matrix at the scale $`\mu =m_t`$, and the vector $`v_c`$ as a vector orthogonal to $`v_t`$, as depicted in Figure 3.

But this should not be interpreted to mean that $`c`$ has zero mass, because $`m_c`$ is given by the nonzero eigenvalue of the mass submatrix, now only $`1\times 1`$, and is hence just the expectation value of $`m`$ in the state vector $`v_c`$, namely

$$m_c=m_t\mathrm{sin}^2\theta _{tc}0,$$
(3)
where $`\theta _{tc}`$ is the rotation angle between the scales $`\mu =m_t`$ and $`\mu =m_c`$. Similarly, although the mass matrices of the $`U`$ and $`D`$ quarks are aligned in orientation at all scales, one sees from

Figure 4 that by virtue of the rotation of the vector $`v`$ from the scale $`\mu =m_t`$ to the scale $`\mu =m_b`$ where the state vectors $`v_t`$ and $`v_b`$ are respectively defined, the two state vectors will not point in the same direction, having rotated by an angle $`\theta _{tb}`$ between the two scales:

$$V_{tb}=𝐯_t.𝐯_b=\mathrm{cos}\theta _{tb}1.$$
(4)
Other fermion species are similar.

Using (3) and (4), and Figures 3 and 4, and similar ones for the other fermions, we obtain the following relations:

$$V_{tb}=\mathrm{cos}\theta _{tb},|V_{ts}|=|V_{cb}|=\mathrm{sin}\theta _{tb},$$
(5)
from the mixing, and from the masses

$$m_c/m_t=\mathrm{sin}^2\theta _{tc},m_s/m_b=\mathrm{sin}^2\theta _{bs},m_\mu /m_\tau =\mathrm{sin}^2\theta _{\tau \mu }.$$
(6)
Inputting from data  on mixing

$$|V_{tb}|=0.99900.9993|V_{ts}|=0.0350.043,|V_{cb}|=0.0370.043,$$
(7)
and on masses for up quarks

$$m_t=174.3\pm 5.1\mathrm{GeV},m_c=1.151.35\mathrm{GeV},$$
(8)
for down quarks

$$m_b=4.04.4\mathrm{GeV},m_s=75170\mathrm{MeV},$$
(9)
and for charged leptons

$$m_\tau =1.777\mathrm{GeV},m_\mu =105.66\mathrm{MeV};$$
(10)
we obtain compatible values for

$$\theta _{tb}=0.03740.0447,0.03500.0430,0.03700.0430$$
(11)
and

$$\theta _{tc}=0.08010.0894,\theta _{bs}=0.13090.2076,\theta _{\tau \mu }=0.2463.$$
(12)
These values suggest a smooth curve, which will be the case if these angles are swept out by a rotating vector $`v`$. This is clearly borne out by Figure 5,

where the dotted curve represents the best-fit to data using MINUIT:

$$\theta =\mathrm{exp}(2.2670.509\mathrm{ln}\mu )0.0075$$
(13)
$`\mu `$ in GeV, with an excellent $`\chi ^2`$ of 0.21 per degree of freedom. The solid curve shown is an earlier calculation  to 1-loop in the Dualized Standard Model (see Footnote 1). The two curves are almost indistinguishable, and hence fit the data points equally well.

The positive result from the two-generation case is encouraging, but below the scale of roughly the $`s`$ quark mass, nonplanar effects begin to be appreciable, as can be estimated by the square of the Cabibbo angle which gives about 4 %. Therefore to go further down the scale it is necessary to study the full three-generation case . Writing

$$v(\mu )=(\xi (\mu ),\eta (\mu ),\zeta (\mu )),$$
(14)
we shall present the extracted angles by plotting $`\eta (\mu ),\zeta (\mu )`$ against scale $`\mu `$.

First we fix the $`U`$ triad to be

$$U:(1,0,0),(0,1,0),(0,0,1).$$
(15)
Then the $`D`$ triad is just given by the elements of the CKM matrix:

$$D:(V_{tb},V_{cb},V_{ub}),(V_{ts},V_{cs},V_{us}),(V_{td},V_{cd},V_{ud}).$$
(16)
We thus obtain the points $`t`$ and $`b`$ on the plot (Figure 6).

Next we consider $`v(\mu =m_c)`$. Since the mass $`m_c`$ comes from ‘leakage’ from $`m_t`$, we can write

$`v(\mu =m_c)`$ $`=`$ $`\mathrm{cos}\theta _{tc}v_t+\mathrm{sin}\theta _{tc}v_c`$ (17)
$`=`$ $`\sqrt{1m_c/m_t}v_t+\sqrt{m_c/m_t}v_c,`$
which gives the point $`c`$ in Figure 6. Note that the existence of another disjoint branch of the square root does not affect the question of interest to us here, namely, whether the allowed region is consistent with data lying on a smooth rotation curve, so long as the first branch already does, and can therefore be ignored.

Similar considerations give us a line as the allowed region for the $`s`$ quark. We shall leave open the question of the light quarks $`u`$ and $`d`$, since they are tightly bound and both the definition and the value of their masses are quite uncertain.

In principle the leptons are not linked to the quarks, but the planar approximation above (Figure 5) and the DSM calculations  both suggest that they can be put on the same trajectory as the quarks. In fact, by putting the $`\tau `$ point by interpolation between the $`b`$ and $`c`$ points, we can easily continue the rotation curve with the leptons, as is again evident from Figure 6.

We have not given in any detail on how the actual angles are extracted from the quark and lepton data, only the theory of it. Full details can be found in .

In conclusion we can say that, using the rotation hypothesis, and all the fermion mass and mixing data (apart from $`m_u`$ and $`m_d`$), we exhibit a smooth curve in 3-d space, passing through all the allowed regions, and spanning some 14 orders of magnitude in energy. Moreover, this curve coincides with the DSM curve  where we expect it to do, that is, where the 1-loop approximation is good.


text:
# Stochastic Annealing

Present address: \]Met Office, Maclean Building, Crowmarsh-Gifford, Oxfordshire OX10 8BB, UK.

## Abstract

We demonstrate that is it possible to simulate a system in thermal equilibrium even when the energy cannot be evaluated exactly, provided the error distribution is known. This leads to an effective optimisation strategy for problems where the evaluation of each design can only be sampled statistically.

stochastic optimisation, simulated annealing

We consider thermal equilibrium simulation of systems in which the energy of any given state is either not known exactly, or else can much more cheaply be estimated. A classic example which occurs in Physics is where each energy calculation itself involves sampling over a distribution or numerical integration, or the estimation of parameters of a numerical model. In this letter we show how, by Stochastic Annealing, thermal equilibrium distributions can nevertheless be sampled exactly, the essence of our method being that the energy errors can be precisely absorbed as a contribution to thermal noise.

Our thermal sampling technique can be applied to optimisation problems where the objective function is analogously difficult to evaluate, using Simulated AnnealingKirkpatrick83  (meaning simulated cooling) or related methods Harju97 ; Anderson01 . As an example we consider designing model protein molecules to fold as fast as possible, where the only way to evaluate a particular design is to run a sample of folding simulations. Confronted by similar problems others have developed more empirical methods robbins ; gong ; bulgak , but none of these is underpinned by simulation of true thermal equilibrium.

In a thermal ensemble the probability of the system occupying a state $`\mu `$ with energy $`E(\mu )`$ is

$$P(\mu )e^{\beta E(\mu )}$$
(1)
where $`\beta =\frac{1}{T}`$ is the inverse temperature. It is convenient to sample this distribution by a Markov process, in which the system is allowed to make a transition (move) from one state to another with rate constant $`K(\mu \nu )`$ which depends only on the two states concerned. This is generally more efficient than trying to choose the states directly, provided we can assume that the move set is ergodic, meaning that all states can be reached (eventually) from any given starting state. The more strict condition of detailed balance,

$$P(\mu )K(\mu \nu )=P(\nu )K(\nu \mu ),$$
(2)
imposes the correct equilibrium distribution provided

$$\frac{K(\mu \nu )}{K(\nu \mu )}=e^{\beta \mathrm{\Delta }E}$$
(3)
where $`\mathrm{\Delta }E`$ is the energy difference $`E(\nu )E(\mu )`$.

Whilst eq. (3) ensures thermal equilibrium at inverse temperature $`\beta `$, it does not fully determine the form of $`K`$. Typically $`K(\mu \nu )`$ is the combination of an attempt frequency to move to state $`\nu `$ given that the system is in state $`\mu `$, multiplied by an acceptance probability. For simplicity of exposition we will take all the attempt frequencies to be equal to unity, so that $`K`$ is just an acceptance probability and so must obey $`0K1`$. The Metropolis algorithmmetropolis  is fully specified by requiring that $`K(\mathrm{\Delta }E)=1`$ for $`\mathrm{\Delta }E<C`$, with $`C`$ as large as possible (maximising acceptance rates) leading to

$$K_{\text{Metropolis}}(\mathrm{\Delta }E)=\mathrm{min}(1,e^{\beta \mathrm{\Delta }E}),$$
(4)
whereas the Glauber acceptance function glauber  arises by requiring that $`K(\mathrm{\Delta }E)+K(\mathrm{\Delta }E)=1`$, leading to

$$K_{\text{Glauber}}(\mathrm{\Delta }E)=1/\left(1+e^{\beta \mathrm{\Delta }E}\right).$$
(5)
These are compared graphically in Fig. 1.

We now consider the case when the true energy change is not known exactly, and we must accept moves with probabilty $`A(x)`$ where $`x`$ is only an *estimate* of the energy change. We will assume that these estimates have statistically independent errors. If $`f(x|\mathrm{\Delta }E)`$ is the probability density of estimating that the energy change is $`x`$ when its true value is $`\mathrm{\Delta }E`$, then the net probability of accepting a move whose true energy change is $`\mathrm{\Delta }E`$ is given by

$$K(\mathrm{\Delta }E)=_{\mathrm{}}^{\mathrm{}}f(x\mathrm{\Delta }E)A(x)𝑑x.$$
(6)
It is our aim to choose $`A(x)`$ such that $`K(\mathrm{\Delta }E)`$ satisfies detailed balance (3).

We can gain insight by considering the crude choice $`A(x)=1`$ for $`x<0`$ and $`A(x)=0`$ otherwise. This simple strategy can give a good aproximation to eq. (3) of great value in optimisation. The resulting acceptance function $`K`$ when $`f`$ is given by a Gaussian distribution is simply related to the standard Error Function and is graphed in Fig. 1. The resemblance between this and the Glauber acceptance function (whose symmetry it shares) is striking, showing how the random energy errors make the selection look thermal - although in this case the match is not exact, so detailed balance is not strictly achieved. The standard deviation $`\sigma `$ of the Gaussian distribution controls an approximate effective temperature using this rule, as inverting eq. (3) gives

$$T\sqrt{\frac{\pi }{8}}\sigma \left(10.018\left(\mathrm{\Delta }E/T\right)^2+\text{order}\left(\mathrm{\Delta }E/T\right)^4\right).$$
(7)
For many optimisation purposes the departure from detailed balance, due to the energy dependent terms at large $`\left|\mathrm{\Delta }E/T\right|`$, is not a problem. Fig. 2 shows how we successfully used this approach to optimise model protein folding: for each design change considered we obtained estimates of the change in mean folding time from a limited sample of folding simulations, and as the annealing proceeded we gradually cooled the system by increasing the sample sizes leading to reduced error size and reduced temperatures through Eq 7. In another paperbowler  we show that this approach can be exploited to unravel a benchmark problem in stochastic optimisation, the probabilistic travelling salesman problem Jaillet88 ; Jaillet93 .

We now attempt directly to choose $`A(x)`$ properly, such that $`K`$ exactly satisfies detailed balance, eq. 3, assuming that the error distribution $`f(x|\mathrm{\Delta }E)`$ is fully known. We first note that this leads to some bounds on the behaviour of the right tail of $`A(x)`$ and a left tail of $`f(x|\mathrm{\Delta }E)`$.

Given that $`K(\mathrm{\Delta }E)1`$ even for negative arguments, the detailed balance condition requires $`_{\mathrm{}}^{\mathrm{}}f(x\mathrm{\Delta }E)A(x)𝑑xe^{\beta \mathrm{\Delta }E}`$ and for large positive $`\mathrm{\Delta }E`$ this severely restricts all contributions to the LHS. First consider $`x\mathrm{\Delta }E`$ for which $`f(x\mathrm{\Delta }E)`$ is not expected to be small. Then the exponential decay on this contribution must come from $`A(x)`$ falling off at least as fast as $`e^{\beta x}`$ as $`x\mathrm{}`$, which becomes important in our later analysis. Second consider $`x0`$, for which $`A(x)`$ cannot become small or we would be heavily rejecting even moves which appear to be downwards in energy. Then the exponential decay on this contribution must come from $`f(x|\mathrm{\Delta }E)`$, $`x0`$, falling off at least as fast as $`e^{\beta \mathrm{\Delta }E}`$ for $`\mathrm{\Delta }E\mathrm{}`$. This latter sets a fundamental restriction on our stochastic annealing: the probability for large energy increases to be estimated as negative must fall off faster than a thermal Boltzmann factor.

Now we begin direct analysis of the detailed balance condition (3), inroducing the substitutions $`f(x|\mathrm{\Delta }E)=e^{\frac{\beta }{2}(x\mathrm{\Delta }E)}g(x,\mathrm{\Delta }E)`$ and $`A(x)=e^{\frac{\beta x}{2}}a(x)`$ so that eqs. (3) and (6) combined simplify down to

$$_{\mathrm{}}^{\mathrm{}}a(x)\left(g(x,\mathrm{\Delta }E)g(x,\mathrm{\Delta }E)\right)𝑑x=0.$$
(8)
Without significant loss of generality we can try

$$a(x)=_{\mathrm{}}^{\mathrm{}}h(\mathrm{\Delta }E^{})j(x,\mathrm{\Delta }E^{})𝑑\mathrm{\Delta }E^{}$$
(9)
where $`h`$ and $`j`$ are functions to be chosen. Substituting this into equation 8 we find

$$_{\mathrm{}}^{\mathrm{}}h(\mathrm{\Delta }E^{})\left[k(\mathrm{\Delta }E,\mathrm{\Delta }E^{})k(\mathrm{\Delta }E,\mathrm{\Delta }E^{})\right]𝑑\mathrm{\Delta }E^{}=0$$
(10)
where

$$k(\mathrm{\Delta }E,\mathrm{\Delta }E^{})=_{\mathrm{}}^{\mathrm{}}g(x,\mathrm{\Delta }E)j(x,\mathrm{\Delta }E^{})𝑑x.$$
(11)
Then eq. 10 is satisfied when $`h(\mathrm{\Delta }E^{})=h(\mathrm{\Delta }E^{})`$ and $`k(\mathrm{\Delta }E,\mathrm{\Delta }E^{})=k(\mathrm{\Delta }E,\mathrm{\Delta }E^{})`$ are even functions in the given sense. We have not succeeded in taking this most general case significantly further, the hard part being to implement $`0A(x)1`$ for a probability.

For further progress we now specialise to the case of invariant error distributions, where $`f(x|\mathrm{\Delta }E)=f(x\mathrm{\Delta }E)`$, meaning that the distribution of error is independent of $`\mathrm{\Delta }E`$ itself. For this case, we can choose $`j(x,\mathrm{\Delta }E^{})=g(x\mathrm{\Delta }E^{})`$ and then from eq. 11 we find $`k(\mathrm{\Delta }E,\mathrm{\Delta }E^{})`$ is a suitably even function. Then we have a solution to eq 8 given by

$$a(x)=_{\mathrm{}}^{\mathrm{}}h(\mathrm{\Delta }E^{})g(x\mathrm{\Delta }E^{})𝑑\mathrm{\Delta }E^{}$$
(12)
provided $`h(x)`$, and correspondingly $`\stackrel{~}{h}(p)`$ below, is even.

We now aim to choose $`h`$ to maximise the move acceptance rates, which are governed by $`A(x)`$. We follow the Metropolis methodology in choosing $`A(x)`$ ($`=e^{\frac{\beta x}{2}}a(x)`$) to be identically $`1`$ below some threshold, $`x<C`$. Then using the Fourier-Laplace transform defined by $`\stackrel{~}{f}(p)=_{\mathrm{}}^{\mathrm{}}e^{px}f(x)𝑑x,`$ the transform of $`a`$ becomes

$$\stackrel{~}{a}(p)=_{\mathrm{}}^Ce^{\frac{\beta x}{2}}e^{px}𝑑x+_C^{\mathrm{}}b(x)e^{px}𝑑x$$
(13)
where $`b(x)=A(x)e^{\frac{\beta x}{2}}`$ for $`xC`$, $`b(x)=0`$ for $`x<C`$. From eq.(12) the transform of the new function $`b(x)`$ is given by

$$\stackrel{~}{b}(p)=\stackrel{~}{h}(p)\stackrel{~}{g}(p)\frac{e^{\left(\frac{\beta }{2}p\right)C}}{\frac{\beta }{2}p}.$$
(14)
The exponential bound we established on the right tail of $`A(x)`$ implies that $`\stackrel{~}{b}(p)`$ is bounded for all $`\mathrm{Re}p>\frac{\beta }{2}`$, whereas the integrability of $`f(x)`$ together with the exponential bound on its left tail only imply that $`\stackrel{~}{g}(p)`$ is bounded for $`\frac{\beta }{2}\mathrm{Re}p<\frac{\beta }{2}`$. Thus $`\stackrel{~}{h}(p)`$ must be chosen to cancel both any divergences of $`\stackrel{~}{g}(p)`$ in $`\mathrm{Re}p\frac{\beta }{2}`$ and the apparent pole at $`p=\beta /2.`$ We first turn to the Wiener-Hopf method morse  to define

$$\stackrel{~}{g}(p)=\stackrel{~}{g_L}(p)\stackrel{~}{g_R}(p)$$
(15)
where $`\stackrel{~}{g_L}(p)`$ is bounded and non-zero for $`\mathrm{Re}p<\frac{\beta }{2}`$, and $`\stackrel{~}{g_R}(p)`$ is bounded and non-zero for $`\mathrm{Re}p>\frac{\beta }{2}`$ ; it also follows from the bounded window for $`\stackrel{~}{g}(p)`$ that $`\stackrel{~}{g_R}(p)`$ is bounded for the wider range $`\mathrm{Re}p>\frac{\beta }{2}`$. Then by choosing $`\stackrel{~}{h}(p)=\frac{B}{\left(\left(\beta /2\right)^2p^2\right)}\frac{1}{\stackrel{~}{g_L}(p)\stackrel{~}{g_L}(p)}`$ , we can ensure that $`\stackrel{~}{h}(p)\stackrel{~}{g}(p)=\frac{B}{\left(\left(\beta /2\right)^2p^2\right)}\frac{\stackrel{~}{g_R}(p)}{\stackrel{~}{g_L}(p)}`$ is duly bounded for $`\mathrm{Re}p>\frac{\beta }{2}`$ except for the (desired) pole at $`p=\frac{\beta }{2}`$. Choosing the constant $`B=\beta \frac{\stackrel{~}{g_L}\left(\frac{\beta }{2}\right)}{\stackrel{~}{g_R}\left(\frac{\beta }{2}\right)}`$ makes the residue of this pole cancel when we reassemble the expression (14) for $`\stackrel{~}{b}(p)`$ to give

$$\stackrel{~}{b}(p)=\frac{e^{\left(\frac{\beta }{2}p\right)C}}{\frac{\beta }{2}p}+\frac{\beta }{\left(\left(\beta /2\right)^2p^2\right)}\frac{\stackrel{~}{g_R}(p)\stackrel{~}{g_L}\left(\frac{\beta }{2}\right)}{\stackrel{~}{g_R}\left(\frac{\beta }{2}\right)\stackrel{~}{g_L}(p)}.$$
(16)
This should be the optimal solution. We cannot incorporate any new factors into $`\stackrel{~}{h}(p)`$ because, being even, they would have to be bounded both for $`Re(p)>\frac{\beta }{2}`$ and for $`Re(p)>\frac{\beta }{2}`$, and we would run up against the limitations of Liouville’s Theorem. The parameter $`C`$ might appear to be a remaining degree of freedom, but it drops out of the acceptance function itself which is given directly in terms of

$$\stackrel{~}{a}(p)=\stackrel{~}{h}(p)\stackrel{~}{g}(p)=\frac{\beta }{\left(\left(\beta /2\right)^2p^2\right)}\frac{\stackrel{~}{g_R}(p)\stackrel{~}{g_L}\left(\frac{\beta }{2}\right)}{\stackrel{~}{g_R}\left(\frac{\beta }{2}\right)\stackrel{~}{g_L}(p)}.$$
(17)
The parameter $`C`$ drops out because it simply reflects the partition we introduced in equation (13). The feature which we have not strictly guaranteed is that $`A(x)=1`$ for $`x<C`$ rather than some different cutoff.

As an example of our approach above, consider the simple case where

$$f(x\mathrm{\Delta }E)=\frac{\gamma }{2}e^{\gamma \left|x\mathrm{\Delta }E\right|}$$
(18)
which leads to $`\stackrel{~}{g}(p;\gamma )=\frac{\gamma ^2}{\left(\gamma \frac{\beta }{2}p\right)\left(\gamma +\frac{\beta }{2}+p\right)}.`$ The choice of $`\stackrel{~}{g_L}`$ and $`\stackrel{~}{g_R}`$ is trivial by inspection, giving $`\stackrel{~}{a}(p)=\frac{\beta }{\left(\beta /2\right)^2p^2}\frac{\gamma +\beta }{\gamma }\frac{\gamma \frac{\beta }{2}+p}{\gamma +\frac{\beta }{2}+p}.`$ The inverse transformation can also be performed by inspection to give

$$A(x)=\mathrm{min}(1,\frac{\gamma ^2\beta ^2}{\gamma ^2}e^{\beta x}+\frac{\beta ^2}{\gamma ^2}e^{(\gamma +\beta )x}).$$
(19)
We note that this acceptance function only remains positive for $`x0`$ when $`\gamma \beta `$, which is precisely the limit of achievable stochastic annealing discussed earlier, and the case $`\gamma \mathrm{}`$ also duly recovers the straightforward Metropolis method. We have analysed other simple cases such as a rectangular error distribution, the superposition of two exponentials as above, and the multiple convolution of exponentials, all leading to results of equivalent properties.

The analysis of a Gaussian error distribution turns out to be slightly singular, in that its corresponding $`\stackrel{~}{g}(p)`$ has no obvious Wiener-Hopf factorisation. However we can approach it by considering the case where $`x`$ is taken to be a sum of $`N`$ independent exponential-distributed variables, the error distribution taking the solvable form of multiply convolved exponentials and (by the Central Limit Theorem) approaching Gaussian form as $`N\mathrm{}.`$ In this case $`\stackrel{~}{g}(p)=\stackrel{~}{g}(p;\gamma )^N`$ with $`\gamma =\sqrt{2N}/\sigma `$, where $`\sigma `$ is the standard deviation of $`x`$, leading to $`\stackrel{~}{a}(p)=\frac{\beta }{\left(\beta /2\right)^2p^2}\left(\frac{\gamma +\beta }{\gamma }\frac{\gamma \frac{\beta }{2}+p}{\gamma +\frac{\beta }{2}+p}\right)^N\frac{\beta }{\left(\beta /2\right)^2p^2}e^{\beta (p\beta /2)\sigma ^2/2}`$ as $`N\mathrm{}`$ at fixed $`\sigma `$. The corresponding acceptance function by inverse transformation is then given by

$$A(x)=\mathrm{min}(1,e^{\beta (x+\beta \sigma ^2/2)})$$
(20)
The optimal acceptance rules found above all obey the bounds that $`0A(x)1`$ required for a probability, but they only do so a postiori so it can be objected that our optimal method gives no guarrantee of this outcome a priori. We have discovered a general but sub-optimal solution for the acceptance function which does assure the requirement. The key to this solution is to note that, given the result 17, our requirements on the factorisation of $`\stackrel{~}{g}(p)`$ can be relaxed to require only that $`\stackrel{~}{g_R}(p)`$ is bounded for $`\mathrm{Re}p>\frac{\beta }{2}`$ and that $`\stackrel{~}{g_L}(p)`$ is non-zero for $`\mathrm{Re}p<\frac{\beta }{2}`$. Then assuming that $`f(x)=0`$ for $`x<C`$, an acceptable factorisation is given by $`\stackrel{~}{g_R}(p)=`$ $`\stackrel{~}{g}(p)e^{pC}`$, $`\stackrel{~}{g_L}(p)=`$ $`e^{pC}`$ leading directly to $`\stackrel{~}{a}(p)=\stackrel{~}{h}(p)\stackrel{~}{g}(p)=\frac{\beta }{\left(\left(\beta /2\right)^2p^2\right)}\frac{\stackrel{~}{g}(p)}{\stackrel{~}{g}\left(\frac{\beta }{2}\right)}`$, at which point we can let $`C\mathrm{}`$ so no significant new restriction has been imposed on $`f`$. The resulting acceptance function by inverse transformation can be expressed as the convolution

$$A(x)=\frac{1}{\stackrel{~}{f}(\beta )}_{\mathrm{}}^{\mathrm{}}K_{\text{Metropolis}}(xy)e^{\beta y}f(y)𝑑y.$$
(21)
It can be verified by direct substitution that this does obey the detailed balance condition (3), it is manifestly positive definite, and it gives maximum acceptance $`1`$ as $`x\mathrm{}`$. Simple comparison shows the resulting acceptance probabilities are lower than the optimal values which we have calculated these, and the key difference is that an interval where $`A=1`$ is no longer imposed.

Given the wide impact of equilibrium statistical mechanics, we are confident that our new method of exactly thermal stochastic annealing will find significant direct application. The chief limitation is that the error distribution must be known. In this context the Gaussian case is particulary important as it can be approached simply through multiple sampling, although its variance is also required. Estimating the variance from the same sample does induce errors, but these can be quantified and become negligible as the sample size becomes largeNeillPhD . It is a more open question whether it is viable to estimate by measurement the full distribution of error and apply this to eq. (21).

Underpinned by the exact results our analysis provides a powerful new tool in stochastic optimisation. Generally it will be sufficient and convenient to use the approximately thermal method we presented, of simply accepting moves which appear to be an improvement. Then all the benefits of simulated annealing are obtained by deliberately using crude estimates for each decision! In the protein folding problem we used limited samples of folding time for these estimates, making the high temperature part of the annealing computationally the cheapest. This interestingly complicates the long noted problem of how to choose the optimum cooling schedule, because cooling by reducing sample errors introduces computational costs growing as $`1/T^2`$ per move.

NEB would like to thank BP and EPSRC for the support of a CASE award during this research.