text:
# Vertex cover problem studied by cavity method: Analytics and population dynamics

## I  Introduction

The statistical physics of spin glass systems on infinitely connected lattices (e.g., the Sherrington-Kirkpatrick model) has been well understood Mézard et al. (1987) and research interest is now focused on systems of finite connectivity (FC). For the limiting example of FC random lattice, development of the cavity method has been made in recent few years Mézard and Parisi (2001). In a FC random lattice, each vertex interacts only with a finite number of randomly chosen neighbours; and the local structure of the lattice is tree-like, with the shortest distance between two randomly chosen vertices diverging as the system size goes to infinity. This tree-like property makes it feasible to study the system by iterative cavity method not (a). The cavity method for $`n`$-dimensional regular lattice systems is yet to be worked out, and some aspects of such kind of systems has been understood using the well-developed mathematical tool of gauge transformation Toulouse (1977); Nishimori (2002).

The zero-temperature property of random lattice spin glasses is especially interesting. Here, the cavity formalism could be greatly simplified because only the minimum energy states are relevant Mézard and Parisi (2003). Furthermore, many combinatorial optimisation problems in computer sciences could be studied through a mapping into an appropriate random spin glass model, examples of which include the K-sat Monasson and Zecchina (1997), the XOR-sat Ricci-Tersenghi et al. (2001); Caracciolo and Sportiello (2002), the vertex covering problem Weigt and Hartmann (2000, 2001a), the number partition problem Mertens (1998), and so on. Recently, the zero-temperature cavity method was used on the random K-sat problem and the phase diagram for $`k=3`$ was obtained Mézard et al. (2002); Mézard and Zecchina (2002).

In this work we hope to improve our understanding on the vertex cover problem. Consider a random graph $`G`$ composed of $`N`$ vertices $`V=\{1,2,\mathrm{},N\}`$. Between any two vertices an edge is present with probability $`c/(N1)`$ and absent with probability $`1c/(N1)`$, so that on average each vertex has $`c`$ neighbours (i.e., the average connectivity is $`c`$). The resulting edge set of graph $`G`$ is denoted by $`E(G)`$. A vertex cover of this graph consists of a set of vertices $`\mathrm{\Lambda }=\{i_1,i_2,\mathrm{},i_m\}`$, with the property that if edge $`(i,j)E(G)`$, then either $`i\mathrm{\Lambda }`$ or $`j\mathrm{\Lambda }`$ or both Weigt and Hartmann (2000). In the general case there are many different ways to cover a graph of size $`N`$; an interesting question is: Does there exist a vertex cover of size not exceeding $`xN`$ ($`0<x<1`$)?

For large systems it was revealed that a sharp threshold value $`x_c(c)`$ exists. When $`x>x_c(c)`$, with probability approaching unity a vertex cover of size $`xN`$ could be constructed for a given graph; while when $`x<x_c(c)`$ this probability approaches zero. This sharp threshold is also closely related to computational complexity. The vertex cover problem is NP-complete Garey and Johnson (1979), and a time growing exponentially with $`N`$ may be needed to determine whether a vertex cover of size $`xN`$ exists or not for a given graph Weigt and Hartmann (2001b). In the case of FC random graphs, when $`x>x_c(c)`$ or $`x<x_c(c)`$, it is relatively easy for a heuristic algorithm to check the existence of such a vertex cover; however, when $`xx_c(c)`$, search complexity increases dramatically Weigt and Hartmann (2000). For the practical purpose of designing better algorithms, it is important for us to understand the reason of this easy-hard-easy transition and to obtain a precise estimate of the threshold value $`x_c(c)`$.

An rigorous bound exists for $`x_c(c)`$ Gazmuri (1984): $`x_l(c)<x_c(c)<1\mathrm{ln}c/c`$, where $`x_l(c)`$ is the root of

$`x_l(c)\mathrm{ln}x_l(c)+[1x_l(c)]\mathrm{ln}[1x_l(c)]`$
$`+(c/2)[1x_l(c)]^2=0;`$ (1)
furthermore, $`x_c(c)`$ approaches the following asymptotic form at large $`c`$ Frieze (1990):

$$x_c(c)=1(2/c)[\mathrm{ln}c\mathrm{ln}\mathrm{ln}c+1\mathrm{ln}2]+o(1/c).$$
(2)
Using replica method of statistical physics, an analytical expression for $`x_c`$ was found in Weigt and Hartmann (2000):

$$x_c(c)=1W(c)/cW^2(c)/2c,$$
(3)
where $`W(c)`$ is the Lambert-W-function defined by $`W(c)\mathrm{exp}[W(c)]=c`$. Equation (3) is exact when $`ce=2.718282`$ Bauer and Golinelli (2001). For $`c>e`$ Eq. (3) underestimates the true threshold value, and for $`c>20.7`$ it is lower than the rigorous lower bound Eq. (1).

The present work focuses on the case of $`c>e`$. Using zero-temperature cavity method, we calculate both analytically and numerically the value of $`x_c(c)`$ and compare it with Eqs. (1) and (2) and with numerical calculations reported in Weigt and Hartmann (2000). In Section II an energy functional is introduced. In Section III the cavity formalism is outlined and the free energy expression is given. We investigate the $`y\mathrm{}`$ situation in Section IV ($`y`$ is a reweighting parameter Mézard and Parisi (2003); Mézard et al. (2002); Mézard and Zecchina (2002), it plays the role of the inverse temperature $`\beta `$ of conventional statistical mechanics). Section V reports the population dynamics results on the threshold value $`x_c(c)`$ and on the backbone size. We conclude the work in Section VI.

## II  The energy functional

We attach to each vertex of the random graph $`G`$ an Ising spin $`\sigma =\{1,+1\}`$. Associated with each spin micro-configuration is the following energy functional

$$E[\{\sigma _i\}]=\underset{i=1}{\overset{N}{}}\sigma _i+\frac{\lambda }{2}\underset{(i,j)E(G)}{}(1+\sigma _i)(1+\sigma _j),$$
(4)
where $`\lambda `$ is an constant parameter chosen to be greater than unity not (b). Denote $`N_{\mathrm{mvc}}(G)`$ as the size of the minimum vertex cover(s) of graph $`G`$, then the minimum energy over all the $`2^N`$ possible spin configurations of graph $`G`$ is

$$E_{\mathrm{min}}=2N_{\mathrm{mvc}}(G)N.$$
(5)
Some explanation on Eq. (5). First, $`E_{\mathrm{min}}`$ is reachable. We denote $`\mathrm{\Lambda }_{\mathrm{mvc}}(G)`$ as (one of) the minimum-sized vertex cover(s), and assign $`\sigma =1`$ to vertices in $`\mathrm{\Lambda }_{\mathrm{mvc}}(G)`$ and $`\sigma =+1`$ to vertices outside. The energy of this spin configuration is $`2N_{\mathrm{mcv}}(G)N`$. Second, no spin configuration could have lower energy. To see this, suppose that another spin configuration has lower energy than Eq. (5). This spin configuration must contain $`N_a<N_{\mathrm{mvc}}(G)`$ negative spins, with $`N_a+\lambda N_0<N_{\mathrm{mvc}}(G)`$, where $`N_0=(1/4)_{(i,j)E(G)}(1+\sigma _i)(1+\sigma _j)`$. However, one at most need to change the spin values of $`N_0`$ vertices from $`+1`$ to $`1`$ to make the sum $`_{(i,j)E(G)}(1+\sigma _i)(1+\sigma _j)=0`$, and the resulting new set of negative spin vertices is a vertex cover with size $`N_a+N_0<N_{\mathrm{mvc}}(G)`$. This conflicts with our original assumption that $`N_{\mathrm{mvc}}(G)`$ is the minimum vertex cover size.

The problem of finding $`x_c(c)`$ is converted to finding the average of $`E_{\mathrm{min}}/N`$ over the random graphs $`G`$:

$$x_c(c)=(1/2)(1+\overline{E_{\mathrm{min}}}/N).$$
(6)
Here $`\overline{()}`$ means the average of $`()`$ over different realizations of the random graph. We use cavity method to estimate $`\overline{E_{\mathrm{min}}}/N`$. In the next section, the cavity formalism for the present problem is outlined. The reader is referred to Mézard et al. (1987); Mézard and Parisi (2001, 2003); Mézard et al. (2002); Mézard and Zecchina (2002) for more detailed discussion.

## III  The zero-temperature cavity formalism

At zero temperature, only the minimum energy configurations are relevant. There could be a great many energy local-minima for Eq. (4). For very large system size $`N`$, we group these configurations into different $`\mathrm{`}\mathrm{`}`$states”. A state of the system corresponds to a set of spin micro-configurations. These spin configurations all have the same energy, which is a local minimum of Eq. (4); and two such spin configurations differ only in a finite number of spin flips. The average number of states at given density $`ϵ`$ of local minimum energy is assumed to be an exponentially increasing function of system size $`N`$, and is characterised by the entropy density $`\mathrm{\Sigma }(c,ϵ)`$. We can introduce a reweighting parameter $`y`$ and define an zero-temperature free energy density $`\mathrm{\Phi }(y)`$ through the following equation

$$𝑑ϵ\mathrm{exp}[Nyϵ+N\mathrm{\Sigma }(c,ϵ)]=\mathrm{exp}[Ny\mathrm{\Phi }(y)].$$
(7)
Equation (7) has the same form as the conventional definition of free energy in textbooks of equilibrium statistical physics. The reweighting parameter $`y`$ plays the role of inverse temperature. A large value of $`y`$ ensures that states with lower energies will be favoured, provided that such states exist (i.e., $`\mathrm{\Sigma }(c,ϵ)0`$).

Suppose we have a system of $`N`$ vertices (spins). Now add a new spin $`\sigma _0`$ into the system and connect it to $`k`$ preexisting spins $`\sigma _1,\mathrm{},\sigma _k`$, where $`k`$ obeys the Poisson distribution of mean $`c`$, $`P_P(k,c)=e^cc^k/k!`$. The energy of the $`N`$-spin system at fixed value of the spins $`\sigma _1,\mathrm{},\sigma _k`$ is supposed to be

$$E^{(N)}(\sigma _1,\mathrm{},\sigma _k)=A\underset{i=1}{\overset{k}{}}h_i\sigma _i,$$
(8)
with $`A`$ being a constant. In the above equation, $`h_i`$ is the local field (called the cavity field) felt by spin $`\sigma _i`$ in the absence of $`\sigma _0`$ in a given macroscopic state. Since the graph is locally tree-like, as the system size becomes very large, the shortest distance between two randomly chosen cavity spins also becomes large; therefore, the cavity field $`h_i`$ felt by spin $`\sigma _i`$ becomes independent of the values of all the other cavity spins not (c). After the addition of spin $`\sigma _0`$, the minimum energy of the $`(N+1)`$-spin system at fixed value of $`\sigma _0`$ is

$$E(\sigma _0)=\{\begin{array}{cc}A\sigma _0,\hfill & \mathrm{if}k=0\hfill \\ A_{i=1}^k\widehat{w}(h_i)\hfill & \\ [1+_{i=1}^k\widehat{u}(h_i)]\sigma _0,\hfill & \mathrm{if}k1.\hfill \end{array}$$
(9)
Here,

$$\begin{array}{cccc}\widehat{w}(h)=0\hfill & \mathrm{if}h=1\hfill & \mathrm{and}=|h|\hfill & \mathrm{if}h0,\hfill \\ \widehat{u}(h)=1\hfill & \mathrm{if}h=1\hfill & \mathrm{and}=0\hfill & \mathrm{if}h0.\hfill \end{array}$$
(10)
(We have used the fact that the cavity fields at zero temperature are integer-valued and do not exceed unity not (c).) The energy shift caused by the addition of spin $`\sigma _0`$ is $`\mathrm{}E_1=1`$ (if $`k=0`$) and $`\mathrm{}E_1=_{i=1}^k[\widehat{w}(h_i)|h_i|]|1+_{i=1}^k\widehat{u}(h_i)|`$ (if $`k1`$).

Equation (9) indicates that the cavity field at spin $`\sigma _0`$ is $`h_0=1`$ (if $`k=0`$) or $`h_0=1+_{i=1}^k\widehat{u}(h_i)`$ (if $`k1`$). By definition not (c), the cavity field of a spin at each state has unique value; however, its value may be different for different states. Denote the probability distribution of the cavity field at vertex $`i`$ among different states as $`P_i(h)`$ (it is called the h-survey in Ref. Mézard and Zecchina (2002)). Because different vertices have different local environments, the h-surveys are different for different vertices. With the introduction of the reweighting parameter $`y`$ which favours lower-energy states, the h-survey at spin $`\sigma _0`$ is related to those of the cavity spins by

$$P_0(h)=\delta _k^0\delta (h1)+[1\delta _k^0]C\underset{i=1}{\overset{k}{}}[P_i(h_i)dh_i]\delta [h1\underset{i=1}{\overset{k}{}}\widehat{u}(h_i)]\mathrm{exp}(y\mathrm{}E_1),$$
(11)
where $`C`$ is an normalisation constant. Eq. (11) is actually a self-consistent equation for the h-survey. A careful analysis of Eq. (11) leads to the following expression

$$P(h)=\{\begin{array}{cc}_{l=0}^{\mathrm{}}\zeta _l\delta (h+l),\hfill & \mathrm{with}\mathrm{probability}p_1\hfill \\ \delta (h1),\hfill & \mathrm{with}\mathrm{probability}p_2\hfill \\ \alpha _{l=0}^{\mathrm{}}\zeta _l\delta (h+l)+(1\alpha )\delta (h1),\hfill & \mathrm{with}\mathrm{probability}p_3=1p_1p_2\hfill \end{array}$$
(12)
where $`\zeta _l0`$ and $`_l\zeta _l=1`$; $`\alpha (0,1)`$ is determined by certain probability distribution $`\rho (\alpha )`$, and

$`p_1`$ $`=`$ $`1\mathrm{exp}(cp_2),`$
$`p_2`$ $`=`$ $`\mathrm{exp}(c(1p_1)).`$ (13)
For very large system size $`N`$, Eq. (7) suggests that at fixed value of $`y`$, $`\mathrm{\Phi }(y)=ϵ\mathrm{\Sigma }(c,ϵ)/y`$, with $`ϵ`$ being implicitly determined by $`\mathrm{\Sigma }(c,ϵ)/ϵ=y`$. An explicit expression for the free energy density could be obtained by the following way:

After the addition of spin $`\sigma _0`$, the averaged number of states of the $`(N+1)`$-system is

$$\mathrm{exp}[(N+1)\mathrm{\Sigma }(\frac{2E(G(N))+2k}{N+1},\frac{E}{N+1})]=𝑑\mathrm{}E_1P^{(1)}(\mathrm{}E_1)\mathrm{exp}[N\mathrm{\Sigma }(\frac{2E(G(N))}{N},\frac{E\mathrm{}E_1}{N})],$$
(14)
where $`P^{(1)}(\mathrm{}E_1)`$ is the probability distribution function of the energy shift $`\mathrm{}E_1`$:

$$P^{(1)}(\mathrm{}E_1)=\delta _k^0\delta (\mathrm{}E_1+1)+(1\delta _k^0)\underset{i=1}{\overset{k}{}}[P_i(h_i)dh_i]\delta [\mathrm{}E_1+\underset{i=1}{\overset{k}{}}(\widehat{w}(h_i)|h_i|)+|1+\underset{i=1}{\overset{k}{}}\widehat{u}(h_i)|].$$
(15)
A logarithm operation is performed on Eq. (14), and the resulting equation is averaged over all the possible realizations of the cavity fields and $`k`$ (this average operation is denoted by an overbar in the following equation). We obtain that

$$y\mathrm{\Phi }(y)=\mathrm{\Sigma }(c,ϵ)yϵ=c\frac{\mathrm{\Sigma }(c,ϵ)}{c}+\overline{\mathrm{ln}𝑑\mathrm{}E_1P^{(1)}(\mathrm{}E_1)\mathrm{exp}(y\mathrm{}E_1)}.$$
(16)
To compute $`\mathrm{\Sigma }/c`$, we setup an edge between two cavity spins. The energy shift, $`\mathrm{}E_2`$, caused by this new edge obeys the following distribution

$$P^{(2)}(\mathrm{}E_2)=\underset{i=1}{\overset{2}{}}[dh_iP_i(h_i)]\delta [\mathrm{}E_2(\mathrm{min}_{\sigma _1,\sigma _2}[\frac{\lambda }{2}(1+\sigma _1)(1+\sigma _2)h_1\sigma _1h_2\sigma _2]+|h_1|+|h_2|)].$$
(17)
The averaged number of states of the new system is

$$\mathrm{exp}[N\mathrm{\Sigma }(\frac{2E(G(N))+2}{N},\frac{E}{N})]=𝑑\mathrm{}E_2P^{(2)}(\mathrm{}E_2)\mathrm{exp}[N\mathrm{\Sigma }(\frac{2E(G(N))}{N},\frac{E\mathrm{}E_2}{N})].$$
(18)
After performing the same procedure as mentioned below Eq. (15), we find that

$$\frac{\mathrm{\Sigma }(c,ϵ)}{c}=(1/2)\overline{\mathrm{ln}𝑑\mathrm{}E_2P^{(2)}(\mathrm{}E_2)\mathrm{exp}(y\mathrm{}E_2)}.$$
(19)
The free energy density expression could be obtained from Eqs. (16) and (19). After taking into consideration Eq. (12), we arrive at the following expression for the free energy density:

$`\mathrm{\Phi }(y)`$ $`=`$ $`2p_11cp_2^2+{\displaystyle \frac{cp_2p_3}{y}}{\displaystyle 𝑑\alpha \rho (\alpha )\mathrm{ln}(\alpha +(1\alpha )e^{2y})}`$ (20)
$`{\displaystyle \frac{p_3}{y}}{\displaystyle \underset{m=1}{\overset{\mathrm{}}{}}}{\displaystyle \frac{P_P(m,cp_3)}{1e^{ch}}}{\displaystyle \underset{i=1}{\overset{m}{}}[\rho (\alpha _i)d\alpha _i]\mathrm{ln}(e^{2y}+(1e^{2y})\underset{i=1}{\overset{m}{}}\alpha _i)}`$
$`+{\displaystyle \frac{cp_3^2}{2y}}{\displaystyle \underset{i=1}{\overset{2}{}}[d\alpha _i\rho (\alpha _i)]\mathrm{ln}(1(1e^{2y})\underset{i=1}{\overset{2}{}}(1\alpha _i))}.`$
At given $`y`$, the energy density and the entropy density are calculated by $`ϵ=\mathrm{\Phi }(y)yd\mathrm{\Phi }(y)/dy`$ and $`\mathrm{\Sigma }=y^2d\mathrm{\Phi }(y)/dy`$, respectively.

## IV  The $`y\mathrm{}`$ limit

At this stage, it is helpful for us to introduce an auxiliary probability distribution function called the u-survey Mézard and Zecchina (2002):

$$Q_i(u)=C𝑑hP(h)\delta (u\widehat{u}(h))\mathrm{exp}(y(\widehat{w}(h)|h|)).$$
(21)
Based on Eq. (12) we know that $`Q_i(u)=\delta (u)`$ (with probability $`p_1`$) or $`Q_i(u)=\delta (u+1)`$ (with probability $`p_2`$), or

$$Q_i(u)=\eta \delta (u)+[1\eta ]\delta (u+1).$$
(22)
The hybrid h-survey and u-survey at a given vertex are related by $`\alpha =\eta /(\eta +(1\eta )e^y)`$. The distribution of the $`\eta `$ value in the hybrid u-survey Eq. (22) is governed by

$$\rho (\eta )=\underset{m=1}{\overset{\mathrm{}}{}}\frac{P_P(m,cp_3)}{1e^{cp_3}}\underset{i=1}{\overset{n}{}}[\rho (\eta _i)d\eta _i]\delta (\eta 1+\frac{e^y\underset{l=1}{\overset{n}{}}\eta _l}{\underset{l=1}{\overset{n}{}}[\eta _l+e^y(1\eta _l)]+(e^y1)\underset{l=1}{\overset{n}{}}\eta _l}).$$
(23)
The free energy expression of Eq. (20) could be rewritten in the following form

$`\mathrm{\Phi }(y)`$ $`=`$ $`p_1p_2{\displaystyle \frac{c}{2}}[(1p_1)^2+(p_2)^2]+{\displaystyle \frac{p_3(1+cp_2)}{y}}\overline{\mathrm{ln}[\eta +e^y(1\eta )]}`$ (24)
$``$ $`{\displaystyle \frac{p_3[1+c(1p_1)]}{y}}\overline{\mathrm{ln}[1\eta +e^y\eta ]}+{\displaystyle \frac{cp_3^2}{2y}}\overline{\mathrm{ln}[e^y+(1e^y)(\eta _1+\eta _22\eta _1\eta _2)]}.`$
The overbars in Eq. (24) denote the average over the $`\eta `$ distribution given by Eq. (23).

When $`ce`$, the only solution of Eq. (III) is that $`p_1=1p_2`$, $`p_2=\mathrm{exp}(cp_2)=W(c)/c`$, and $`p_3=0`$. In this case we recover Eq. (3). $`\mathrm{\Sigma }(c,ϵ)=0`$ for this solution, indicating that there is only one state. It was found that for $`ce`$, all the vertices of the random graph could be removed by application of an leaf-removal algorithm Bauer and Golinelli (2001).

When $`c>e`$ the above-mentioned solution becomes unstable, and a new solution appears with $`p_2=\mathrm{exp}[c\mathrm{exp}(cp_2)]<\mathrm{exp}(cp_2)`$, $`p_1=1\mathrm{exp}(cp_2)`$, and $`p_3>0`$. The analysis of Bauer and Golinelli Bauer and Golinelli (2001) reveals that a core with size proportional to $`N`$ remains after application of the leaf-removal algorithm. The core is a strongly connected subgraph, in which each vertex is connected at least to two other vertices.

To estimate the value of $`x_c(c)`$ for $`c>e`$, let we first consider the limiting situation of $`y\mathrm{}`$. Equation (7) ensures that the minimum $`ϵ`$ corresponds to $`y=\mathrm{}`$, provided that the configurational entropy is non-negative at this limit.

From Eq. (23) we know that as $`y\mathrm{}`$,

$$\rho (\eta )=r_1\delta (\eta 0^+)+r_2\delta (\eta 1^{})+r_3\rho ^{}(\eta ),$$
(25)
where $`\rho ^{}(\eta )`$ is a uniform distribution over $`(0,1)`$. Equation (25) is confirmed by the population dynamics calculation (Fig. 1). It is easy to verify that

$$r_1=\frac{1cp_2}{cp_3},r_2=\frac{c+cp_1\mathrm{ln}c}{cp_3},r_3=\frac{\mathrm{ln}c1}{cp_3}.$$
(26)
Consequently, we obtain from Eq. (24) that

$`ϵ_{\mathrm{}}`$ $`=`$ $`1\mathrm{ln}^2(c)/2c\mathrm{ln}(c)/c3/2c,`$
$`\mathrm{\Sigma }_{\mathrm{}}`$ $`=`$ $`\pi ^2(\mathrm{ln}c1)^2/16c.`$ (27)
The minimum energy value given in the above equation is an improved lower-bound of the true average minimum energy. It was obtained also in Weigt and Hartmann (2001a) by replica method. However, at $`y=\mathrm{}`$ the entropy density $`\mathrm{\Sigma }_{\mathrm{}}`$ is negative, suggesting that there is no state at this energy density. Indeed the $`x_c(c)`$ value \[Eq. (6)\] of this solution also exceeds the rigorous lower-bound when $`c>27.3`$. The true energy density must be higher than the value given in Eq. (IV). A better estimate of the minimum energy density could be obtained by calculating the maximum value of $`\mathrm{\Phi }(y)`$ with respect to the reweighting parameter $`y`$ not (d). This is done in the next section with population dynamics Mézard and Parisi (2001).

## V  Population dynamics at finite $`y`$

To obtain the value of $`\mathrm{\Phi }(y)`$ at any given $`y`$, the technique of population dynamics is used Mézard and Parisi (2001). A large population of $`\eta `$’s is generated and this population then evolves according to Eq. (23). The averages in Eq. (24) are calculated numerically. The resulting estimates of $`x_c(c)`$ are shown in Fig. 2 and listed in Table 1.

The threshold curve $`x_c(c)`$ obtained by the present method lies within the rigorous bound given by Eq. (1). It is therefore an improved estimate compared with Eq. (3) and Eq. (IV), both of which exceed the rigorous lower-bound when $`c`$ is larger than certain value. However, the values of $`x_c`$ estimated by the cavity method is systematically smaller than enumeration results on finite systems (Fig. 2). When the average connectivity $`c`$ is large, the estimated $`x_c(c)`$ value approaches the asymptotic value but it lies below the asymptotic curve (Fig. 2 inset). These discrepancies suggest that the $`x_c(c)`$ threshold value obtained by the cavity method is not exact; it could serve as an improved lower-bound of the real threshold curve. The reason for the failure of the cavity method to obtain exact threshold values for $`c>e`$ are discussed in the next section.

The cavity field distribution Eq. (12) contains information on the spin state at a given vertex. A spin $`\sigma _i`$ will be fixed at $`\sigma _i=+1`$ if the local cavity field is distributed according to $`P(h_i)=\delta (h1)`$ or $`P(h_i)=\alpha _{l=0}^{\mathrm{}}\zeta _l\delta (h+l)+(1\alpha )\delta (h1)`$ but with $`\alpha 0^+`$ not (e); on the other hand, $`\sigma _i`$ will be fixed at $`\sigma _i=1`$ with probability $`_{l=1}^{\mathrm{}}\zeta _l`$ if $`P(h_i)=_{l=0}^{\mathrm{}}\zeta _l\delta (h+l)`$ or $`P(h_i)=\alpha _{l=0}^{\mathrm{}}\zeta _l\delta (h+l)+(1\alpha )\delta (h1)`$ but with $`\alpha 1^{}`$ not (e). For the minimum vertex covers at $`y=y^{}`$, the probability for a randomly chosen vertex to have fixed spin value is calculated by population dynamics (see Fig. 3). The fraction of frozen spins calculated by the population dynamics is much lower that that obtained by numerical enumeration Weigt and Hartmann (2001a). This discrepancy may be further indication that the full hierarchy of replica symmetry breaking is needed to completely describe the property of the minimum vertex covers. We have noticed that the fraction of frozen spins strongly depends on the value of the reweighting parameter $`y`$. When $`y\mathrm{}`$ the replica-symmetric result of Weigt and Hartmann (2001a) is recovered; while for $`y2y^{}`$$`3y^{}`$ the data obtained by numerical enumeration is approached.

## VI  Discussion

In this work, we estimate the average minimum vertex cover size $`x_c(c)`$ for random graphs of finite connectivity $`c>e`$ in the large $`N`$ limit. The obtained $`x_c(c)`$ curve lies within the rigorous bound Gazmuri (1984) and approaches the asymptotic curve Eq. (2) at large $`c`$ values. It could be regarded as an improved lower-bound of the real threshold $`x_c(c)`$ value.

When $`c>e`$ the threshold $`x_c`$ estimated by the cavity method is not exact. The reason may be the following: The cavity method is equivalent to one-step replica-symmetry-breaking Mézard et al. (1987); Mézard and Parisi (2001, 2003), and the cavity fields on different vertices are considered as uncorrelated. Because of the core percolation beyond $`c=e`$ Bauer and Golinelli (2001) in the random graph, the cavity fields of different vertices may actually be correlated strongly. To partly account for this effect, one possibility is to consider also non-integer cavity fields. We hope to return to this point in a latter work.

The cavity method has inspired very efficient algorithms to tackle the random K-sat problem. In the random K-sat problem, there exists a glassy phase at $`y\mathrm{}`$ for certain range of the connectivity $`c`$ Mézard et al. (2002); Mézard and Zecchina (2002). In this glassy phase, the minimum energy is still located at $`y=\mathrm{}`$ but the complexity is positive, and the algorithm based on the idea of cavity field Mézard and Zecchina (2002) works well in this phase. For the vertex cover problem, the present work suggests that such a $`y=\mathrm{}`$ glass phase does not exist (this conclusion seems also true for the vertex cover problem on random hyper-graphs where each <sup>′′</sup>edge” is a triangle wei ). This indicates that vertex covers of size $`Nx_c(c)+O(1)`$ are extremely few. It remains to be seen whether or not algorithms based on cavity method could efficiently find vertex covers of size slightly beyond $`Nx_c(c)`$ for a given random graph.

## Acknowledgment

This work is made possible by a post-doctoral fellowship of the Max Planck Society. I thank M. Weigt for suggestions concerned with earlier versions of this manuscript, and A. K. Hartmann and M. Weigt for sharing numerical data. I also thank Professor R. Lipowsky and professor YU Lu for support.


format: text

text:
# 1 Introduction

## 1 Introduction

As is well known the entropy of a black hole is

$$S_{BH}=\frac{A}{4G}$$
(1)
where $`A`$ is the area of the horizon and $`G`$ is Newton constant. This has led to the idea of holography , which claims that the number of degrees of freedom in a gravitational system is proportional to its area and not its volume, and that black hole configurations maximize the entropy for a given energy and charge.

In the context of $`AdS/CFT`$  this takes a more precise form. There is a connection between a CFT with a cut-off (to be defined later) and portions of AdS  . The full CFT lives at the boundary of AdS and is dual to string theory in the whole bulk of AdS. If one considers a CFT with some cut-off then one can think of the cut-off CFT as ‘living” on some time-like hyper-surfaces in AdS, and this cut-off CFT is dual to string theory in the inner bulk. Holography then implies that the number of degrees of freedom of the cut-off CFT (to be defined), related to some constant radial hyper-surface, is exactly the area of the hyper-surface in the AdS space divided by $`4G`$. In  some definitions of the number of degrees of freedom of a cut-off CFT were used and it was shown that it is proportional to the area in Planck units but they have not specified the regularization scheme that one should use.

Three quantities; The black hole entropy, the area in Planck units and the number of degrees of freedom in a cutoff CFT need to match to each other. Given the $`AdS/CFT`$ one should be able to understand why these quantities are equal. Recently the relationship between black hole entropy and the area in Planck units was explained in this context . In this note we would like to give a better understanding of the equality between the black hole entropy, which is the dual QFT thermal entropy and the number of degrees of freedom of the QFT with some cutoff.

## 2 Thermality and cut-off

Let us start with a CFT and label the number of states with energy $`E`$ by $`\mathrm{\Omega }(E)`$. The total number of states in a local quantum field theory without a cut-off

$$_{\mathrm{}}^{\mathrm{}}\mathrm{\Omega }(E)𝑑E$$
(2)
is of course infinite. At any given energy one could have defined (ad hoc) the number of degrees of freedom to be

$$\mathrm{ln}\mathrm{\Omega }(E)$$
(3)
If one looks at a quantum field theory with some cut-off scheme then one can define a regulated version of (2)

$$N(\mathrm{\Lambda })=f(\mathrm{\Lambda },E)\mathrm{\Omega }(E)𝑑E$$
(4)
where $`f(\mathrm{\Lambda },E)`$ is a regulating function defining the regularization scheme. How should one define then the regulated number of degrees of freedom ?. Since $`\mathrm{\Omega }(E)`$ is a rapidly increasing function (at least if the number of degrees of freedom is large) and $`f(\mathrm{\Lambda },E)`$ a rapidly decreasing function of $`E`$, then to compute the number of states with this regulating scheme one has to preform a saddle point approximation to find a saddle point $`\overline{E}`$, and the regulated number of degrees of freedom can then be defined as

$$\mathrm{ln}\mathrm{\Omega }(\overline{E})$$
(5)
On the other hand the black hole is dual to the CFT at some finite temperature. The partition function of the CFT at finite temperature is

$$Z(\beta )=e^{\beta E}\mathrm{\Omega }(E)𝑑E$$
(6)
We can now view equation (6) in another manner. $`Z(\beta )`$ can be viewed as a regulated number of states with a particular regulator(cut-off). Namely $`e^{\beta E}`$ is just a cut-off function of the states of the CFT. Then the regulated number of degrees of freedom $`\mathrm{ln}\mathrm{\Omega }(\overline{E})`$ is of course just the definition of the entropy if one views $`Z(\beta )`$ as a finite temperature partition function. This suggests that the appropriate definition of the cut-off CFT is with an exponential decreasing regulating function. The question is, is this compatible with other properties of the AdS.

## 3 Gravity side

In this section we will show that the $`AdS/CFT`$ in the regime of semiclassical supergravity suggests a regularization scheme one should use, which matches the one from the previous section.

### 3.1 Cut-off and lightcone

The relation between the energy cut-off and the radial coordinate of the hyper-surface on which the cut-off theory is defined, is encoded in the null geodesic equation. A localized object in the bulk is represented by a blob on the boundary. let us denote the size of the blob as $`L`$. The Lorentzian nature of the boundary theory implies (where $`t`$ is the boundary time)

$$\frac{dL}{dt}1$$
(7)
Let us now imagine the object moving radially on some trajectory where the radial position is changing (and hence the cut-off $`\mathrm{\Lambda }`$, where $`\mathrm{\Lambda }^1`$ is the energy cut-off)), then

$$\frac{dL}{dt}=\frac{dL}{d\mathrm{\Lambda }}\frac{d\mathrm{\Lambda }}{dt}.$$
(8)
Now since the blob size changes due to the changing cut-off and in order not to violate equation (7) one has

$$\frac{dL}{d\mathrm{\Lambda }}1\frac{d\mathrm{\Lambda }}{dt}1.$$
(9)
Since equation (7) can be saturated this implies that the lightcone condition on the boundary is related to the lightcone condition in the bulk . Since $`\mathrm{\Lambda }`$ is a function of the radial direction (labeled by $`r`$) this gives the bulk lightcone condition in the form

$$|\frac{d\mathrm{\Lambda }(r)}{dt}|=1.$$
(10)
Let us now look at some examples.

We start with the metric

$$ds^2=\frac{l^2}{z^2}(dt^2+dx_i^2+dz^2)$$
(11)
The lightcone condition is

$$\frac{dz}{dt}=1$$
(12)
which then gives

$$\mathrm{\Lambda }=z$$
(13)
In another form we can take

$$ds^2=\frac{U^2}{R^2}(dt^2+dx_i^2)+\frac{R^2}{U^2}dU^2$$
(14)
The lightcone condition is

$$\frac{dU}{dt}=\frac{U^2}{R^2}$$
(15)
To turn this equation into the form of (10) one gets

$$\mathrm{\Lambda }=|R^2\frac{dU}{U^2}|=\frac{R^2}{U}.$$
(16)
which agrees with . One can also take the metric for global AdS, of the form

$$ds^2=(1+\frac{r^2}{l^2})dt^2+(1+\frac{r^2}{l^2})^1dr^2+r^2d\mathrm{\Omega }^2$$
(17)
Here we find

$$\mathrm{\Lambda }=l\frac{dr}{1+\frac{r^2}{l^2}}=l(\mathrm{arctan}(\frac{r}{l})+c).$$
(18)
We need to obey the boundary condition $`\mathrm{\Lambda }(r=\mathrm{})=0`$, so we find

$$r=l\mathrm{tan}(\frac{\mathrm{\Lambda }}{l}+\frac{\pi }{2})$$
(19)
Notice that this implies that at $`r=0`$ the energy cut-off is $`\frac{2}{l\pi }`$ which is appropriate for a theory on a sphere.

### 3.2 Regulating function

For simplicity we work with the Euclidean metric

$$ds^2=\frac{l^2}{z^2}(dz^2+dx_i^2).$$
(20)
In the semiclassical gravity regime a scalar field in the bulk is related to a scalar field at the boundary as

$$\varphi (x,z)=𝑑x^{}G(z,x,x^{})\varphi (x^{})$$
(21)
Where the kernel depends on the mass of the scalar (or on the conformal dimension of the corresponding CFT operator $`\mathrm{\Delta }`$), and is given by

$$G(z,x,x^{})(\frac{z}{z^2|xx^{}|^2})^\mathrm{\Delta }.$$
(22)
Since the supergravity fields are dual to sources that couple to operators in the CFT, We can think of equation (21) as defining a smeared source and thus a regularization scheme111In general bulk operators are not simply related to boundary operators  other than in the semiclassical regime.. To see more clearly the content of this scheme we Fourier transform equation (21)

$$\varphi (\stackrel{}{k})K_{\mathrm{\Delta }d/2}(kz)\varphi ^{}(\stackrel{}{k})$$
(23)
where $`K_\nu (x)`$ is a Bessel function and $`k=|\stackrel{}{k}|`$. The asymptotic behavior of the Bessel function is (up to powers of $`kz`$ which are not relevant for the saddle point)

$$e^{kz}$$
(24)
for all $`\nu `$. Similar regularization scheme can be found for vector and higher spin fields. The important thing is that they all have the same exponential asymptotic form at large $`kz`$. So we see that indeed the $`AdS/CFT`$ relationship predicts a regulating function of the form that is compatible with the relationship to the thermal partition function of the CFT and thus to the black hole entropy222The saddle point is expected to be at $`\overline{𝐏}=0`$ where $`𝐏`$ is the momenta, with a cutoff

$$z1/T.$$
(25)
To see if this cut-off relationship is correct, all we have to do is to check if the radius size of a black hole at temperature $`T`$ obeys equation (25).

Indeed for $`AdS_3`$ we have

$$z_h=\frac{1}{2\pi T}$$
(26)
and for $`AdS_5`$ one gets

$$z_h=\frac{1}{\pi T}$$
(27)
Note that this does not follow from dimensional analysis since any function of the dimensionless coupling constant could have been involved. Now we see that approximating the regularization function by its asymptotic behavior is valid since in the semiclassical regime $`\overline{E}/TS_{bh}1`$.

### 3.3 Non conformal case

For non conformal theories which are dual to the near horizon geometry of p-branes, one can do a similar analysis. The geometry is given by

$`ds^2={\displaystyle \frac{U^{(7p)/2}}{\sqrt{d_pe^2}}}(dt^2+dx_i^2)+{\displaystyle \frac{\sqrt{d_pe^2}}{U^{(7p)/2}}}dU^2+\sqrt{d_pe^2}U^{(p3)/2}d\mathrm{\Omega }_{8p}^2`$ (28)
where $`e^2=g_{ym}^2N`$ and $`d_p=2^{72p}\pi ^{\frac{93p}{2}}\mathrm{\Gamma }(\frac{7p}{2})`$. The wave equation for a massless scalar in ten dimension is given by (see for example )

$$[_U(U^{8p}_U)\sqrt{d_pe^2}k^2U+l(l+7p)U^{6p}]\varphi =0$$
(29)
where $`l(l+7p)`$ is some eigenvalue of the Laplacian on the sphere $`S^{8p}`$. If we define

$$z=\frac{\sqrt{d_pe^2}}{\frac{5p}{2}U^{(5p)/2}}$$
(30)
Then the appropriate solution takes the form

$$(z)^{(p7)/(p5)}K_\nu (zk)$$
(31)
Since Solution of equation (29) controls the behavior of the bulk to boundary Greens function at large $`kz`$, we see that the behavior at large $`kz`$ is again

$$e^{kz}.$$
(32)
For this to match the gauge theory thermal entropy one should then have that a black hole of temperature $`T`$ have a horizon size

$$T1/z_h$$
(33)
which is indeed the case since for these black holes

$$T=\frac{7p}{2\pi (5p)}\frac{1}{z_h}$$
(34)
To conclude, we see that the thermal entropy relationship with the number of degrees of freedom of a cut-off gauge theory is based on a certain regulating scheme whose functional form (in the large $`N`$ large t Hooft coupling region) can be predicted from the semiclassical gravity.

## 4 Acknowledgments

I would like to thank D. Kabat for many helpful discussions.


text:
# Finite entropy characterizes topological rigidity on connected groups

## 1. Introduction

An algebraic $`^d`$-action $`\alpha `$ on a compact abelian group $`X`$ is a homomorphism $`\alpha :𝐧\alpha (𝐧)`$ from $`^d`$ to the group $`\mathrm{Aut}(X)`$ of continuous automorphisms of $`X`$. Compact groups are assumed to be metrizable throughout and are written multiplicatively; $`e`$ is used to denote the identity element of any group. Write $`𝖷=(X,\alpha )`$ for such an algebraic dynamical system, and call the system $`𝖷`$ connected, mixing and so on if $`X`$ is connected, $`\alpha `$ is mixing, and so on.

Any algebraic system $`𝖷`$ preserves $`\lambda _X`$, the Haar measure on $`X`$. The system $`𝖷`$ is mixing if

$$\underset{𝐧\mathrm{}}{lim}\lambda _X(A_1\alpha (𝐧)(A_2))=\lambda _X(A_1)\lambda _X(A_2)$$

for all measurable sets $`A_1,A_2X.`$

A map $`\varphi :𝖷_1𝖷_2`$ between algebraic dynamical systems is equivariant if $`\varphi \alpha _1(𝐧)=\alpha _2(𝐧)\varphi `$ for all $`𝐧^d`$, and is affine if there is a continuous group homomorphism $`\psi :X_1X_2`$ and an element $`yX_2`$ with $`\varphi (x)=\psi (x)y`$.

Topological (respectively, measurable) rigidity is a property of the target system $`𝖷_2`$ that forces an equivariant continuous (resp. measurable) map to coincide everywhere (resp. almost everywhere) with an affine map.

For $`d1`$, denote by $`R_d=[u_1^{\pm 1},\mathrm{},u_d^{\pm 1}]`$ the ring of Laurent polynomials with integral coefficients in $`d`$ commuting variables $`u_1,\mathrm{},u_d`$. An element $`f`$ of $`R_d`$ is written

$$f(𝐮)=\underset{𝐧^d}{}f_𝐧𝐮^𝐧$$

with $`𝐮^𝐧=u_1^{n_1}\mathrm{}u_d^{n_d}`$, $`f_𝐧`$ for all $`𝐧=(n_1,\mathrm{},n_d)^d`$, and $`f_𝐧=0`$ for all but finitely many $`𝐧^d`$.

If $`𝖷=(X,\alpha )`$ is an algebraic $`^d`$-action on a compact abelian group $`X`$, then the countable dual group $`M=\widehat{X}`$ is a module over the ring $`R_d`$ under the operation

$$fa=\underset{𝐧^d}{}f_𝐧\widehat{\alpha }(𝐧)(a)$$

for $`fR_d`$ and $`aM`$. The module $`M`$ is called the *dual module* of $`𝖷`$. Conversely, a countable module $`M`$ over $`R_d`$ determines an algebraic $`^d`$-action $`𝖷_M=(X_M,\alpha _M)`$ by setting

$$\widehat{\alpha _M}(𝐧)(a)=𝐮^𝐧a$$

for every $`𝐧^d`$ and $`aM`$.

An algebraic $`^d`$-action $`𝖷`$ is Noetherian if the dual module is Noetherian. The following properties are equivalent.

* $`𝖷_M`$ is Noetherian.
* $`M`$ is finitely-generated over $`R_d`$ (this is equivalent to $`M`$ being Noetherian since $`R_d`$ is itself Noetherian).
* Any descending chain of closed $`\alpha _M`$-invariant subgroups of $`X_M`$ stabilizes (the Descending Chain Condition; see ).

The topological entropy of the system $`𝖷_M`$ is defined and computed in terms of the module $`M`$ in .

Rigidity properties of algebraic $`^d`$-actions have been studied by several authors. Measurable equivariant maps between mixing zero-entropy algebraic $`^d`$-actions exhibit strong regularity properties (see , ,  and ). For a $``$-action generated by an automorphism $`\theta `$ on a connected finite-dimensional compact abelian group, it is known that the topological centralizer of the action admits non-affine maps if and only if $`\theta `$ is not ergodic (cf. ,  and ). Ergodic automorphisms of infinite-dimensional groups may have non-affine maps in their centralizers (see Example 1.3). In  it is shown that for any expansive connected algebraic $`^d`$-action $`𝖷`$, the topological centralizer of $`\alpha `$ consists of affine maps (expansiveness is a condition that implies the Descending Chain Condition; for $`d=1`$ it forces the compact group $`X`$ to be finite-dimensional).

In this note we prove the following result, which characterizes a form of topological rigidity in terms of topological entropy.

###### Theorem 1.1.

Let $`𝖷_1`$, $`𝖷_2`$ be connected mixing Noetherian algebraic $`^d`$-actions. Then the following properties are equivalent.

1. Every equivariant continuous map $`𝖷_1𝖷_2`$ is an affine map.
2. The system $`𝖷_2`$ has finite topological entropy.

For $`d2`$, this result applies to situations where the underlying group $`X_2`$ is infinite-dimensional, so the lifting techniques of  and  cannot be applied directly. Write $`𝕋`$ for the multiplicative unit circle.

###### Example 1.2.

To illustrate Theorem 1.1, consider the $`^2`$-action $`𝖷`$ where $`X𝕋^^2`$ is the closed subgroup consisting of all $`x𝕋^^2`$ with

$$x(m+1,n)x(m,n)x(m,n+1)=1\text{ for all }m,n,$$

and $`\alpha `$ is the shift action of $`^2`$ on $`X`$. The system $`𝖷`$ is mixing and has finite entropy. It follows that every continuous equivariant map from $`𝖷`$ to itself is an affine map. In contrast, the measurable centraliser of $`𝖷`$ contains many non-affine maps, since $`𝖷`$ is measurably isomorphic to a $`^2`$ Bernoulli shift (see , ).

###### Example 1.3.

For the case of a single automorphism, the compact group being finite-dimensional forces the entropy to be finite. Ergodic automorphisms of infinite-dimensional groups are not topologically rigid in general.

For example, the shift automorphism of $`X=𝕋^{}`$ defines an ergodic $``$-action of infinite entropy that is not topologically rigid: if $`f:𝕋𝕋`$ is any map, then the shift map commutes with the map $`\varphi :XX`$ defined by $`(\varphi (x))_k=f(x_k)`$. The module corresponding to this action is a Noetherian $`R_1`$-module.

On the other hand, an ergodic automorphism of $`𝕋^{}`$ that splits into a direct product of automorphisms of finite-dimensional tori is topologically rigid. The module corresponding to this action is not Noetherian. It is not know whether such an action can have finite topological entropy (see ).

The next example again shows that Theorem 1.1 does not hold for non-Noetherian actions.

###### Example 1.4.

Let $`F_d`$ denote the field of fractions of $`R_d`$, considered as a $`R_d`$-module. Let $`𝖷_1`$ denote the algebraic $`^d`$-action corresponding to $`F_d`$. Notice that $`F_d`$ is torsion-free as a $`R_d`$-module, and $`𝖷_1`$ has infinite entropy. For any $`𝐧^d`$, multiplication by $`𝐮^𝐧1`$ is an automorphism of $`F_d`$. By duality, the map $`x\alpha _1(𝐧)(x)x`$ is a continuous automorphism of $`X_1`$ for any $`𝐧^d`$. In particular, $`𝖷_1`$ does not have any non-trivial periodic orbits. Now let $`𝖷_2`$ be any mixing connected algebraic $`^d`$-action with a dense set of periodic orbits (any Noetherian system has this property). Since continuous equivariant maps take periodic orbits to periodic orbits, it follows that any continuous equivariant map from $`𝖷_2`$ to $`𝖷_1`$ is trivial.

Example 1.4 is similar in spirit to a remark of Comfort (see ): there are no non-trivial homomorphisms $`𝕋\widehat{}`$ since torsion elements are dense in $`𝕋`$ but absent in $`\widehat{}`$.

## 2. Algebraic $`^d`$-actions

In this section basic results and terminology on algebraic $`^d`$-actions is collected. A prime ideal $`𝔭R_d`$ is associated with the $`R_d`$-module $`M`$ if there exists $`mM`$ with $`𝔭=\{fR_d|fm=0\}`$. The set of prime ideals associated with $`M`$ is denoted $`\mathrm{Asc}(M)`$. If $`M`$ is Noetherian, then $`\mathrm{Asc}(M)`$ is finite. The torsion submodule of $`M`$ is defined by

$$\mathrm{Tor}(M)=\{mMrm=0\text{ for some non-zero }rR_d\}.$$

A module $`M`$ is said to be a torsion module if $`\mathrm{Tor}(M)=M`$.

The following result taken from \[14, Theorem 6.5\] characterizes mixing in algebraic terms.

###### Lemma 2.1.

The algebraic $`^d`$-action $`𝖷_M`$ is mixing if and only if for every $`𝔭\mathrm{Asc}(M)`$ and for every non-zero $`𝐧^d`$, the polynomial $`𝐮^𝐧1`$ does not lie in $`𝔭`$.

An algebraic $`^d`$-action $`𝖷_2`$ is an algebraic factor of $`𝖷_1`$ if there is a surjective continuous equivariant homomorphism $`\varphi :X_1X_2`$.

The next lemma shows that if the module corresponding to an algebraic $`^d`$-action is Noetherian, then infinite topological entropy can only be created by the presence of (a factor of) a full shift with infinite alphabet.

###### Lemma 2.2.

For a Noetherian system $`𝖷_M`$ the following conditions are equivalent.

1. $`X_M`$ does not admit a non-trivial closed $`\alpha _M`$-invariant subgroup $`H`$ with the property that the restriction of $`\alpha _M`$ to $`H`$ is an algebraic factor of the shift action of $`^d`$ on $`(𝕋^n)^^d`$ for some $`n>0`$.
2. $`M`$ is a torsion module.
3. $`𝖷_M`$ has finite topological entropy.

###### Proof.

$`(1)(2).`$ Suppose that $`M`$ is not a torsion module and $`N=M/\mathrm{Tor}(M)`$. Then $`N`$ is a non-zero torsion-free $`R_d`$-module.

We claim that $`N`$ is isomorphic to a submodule of the free module $`R_d^n`$ of rank $`n`$ for some $`n1`$. Let $`N_0`$ denote the localisation of $`N`$ at the prime ideal $`\{0\}`$. Since $`N`$ is Noetherian, $`N_0`$ is a finite-dimensional vector space over $`F=(u_1^{\pm 1},\mathrm{},u_d^{\pm 1})`$, the quotient field of $`R_d`$. Let $`B=\{b_1,\mathrm{},b_n\}`$ be any $`F`$-basis of $`N_0`$. The map $`mm/1`$ embeds $`N`$ as a submodule of $`N_0`$. Choose a finite $`R_d`$-generating set $`A`$ of $`N`$, and an element $`pR_d`$ with the property that $`pa`$ lies in the $`R_d`$-submodule generated by $`B`$ for all $`aA`$. The submodule generated by $`\{b_1/p,\mathrm{},b_n/p\}`$ contains $`N`$, and is a free $`R_d`$-module of rank $`n`$. This proves the claim.

The system $`𝖷_N`$ is therefore an algebraic factor of the shift action on $`(𝕋^n)^^d`$. Since $`N`$ is a quotient of $`M`$, by duality there exists a closed $`\alpha `$-invariant subgroup $`HX`$ such that the restriction of $`\alpha `$ to $`H`$ is conjugate to $`𝖷_N`$.

$`(2)(1).`$ Let $`HX`$ be a closed $`\alpha `$-invariant subgroup such that the restriction of $`\alpha `$ to $`H`$ is an algebraic factor of the shift action on $`(𝕋^n)^^d`$ for some $`n>0`$. The dual module of the shift action on $`(𝕋^n)^^d`$ is isomorphic to the direct sum of $`n`$ copies of $`R_d`$, which implies that $`\widehat{H}`$ is a torsion-free $`R_d`$-module. On the other hand, $`\widehat{H}`$ is a quotient of the $`R_d`$-module $`M`$, which is a torsion module by assumption (2). Hence $`\widehat{H}=\{0\}`$ so $`H`$ is trivial.

$`(2)(3).`$ Let $`\{m_1,\mathrm{},m_k\}`$ generate $`M`$ as an $`R_d`$-module. For $`j=1,\mathrm{},k`$ let $`I_jR_d`$ denote the ideal defined by

$$I_j=\{pR_dpm_j=0\}.$$

Since $`M`$ is a torsion module, each $`I_j`$ is non-zero. For $`j=1,\mathrm{},k`$ let $`M_j`$ denote the $`R_d`$-module $`R_d/I_j`$. Since each $`I_j`$ is non-zero, $`𝖷_{M_j}`$ has finite entropy by \[11, Theorem 3.1\]. Let

$$M^{}=M_1\mathrm{}M_k.$$

Since each $`𝖷_{M_j}`$ has finite entropy, $`𝖷_M^{}`$ also has finite entropy. The map $`(r_1,\mathrm{},r_k)r_1m_1+\mathrm{}+r_km_k`$ expresses $`M`$ as a quotient of $`M^{}`$. The dual of this map embeds $`𝖷_M`$ as a sub-action of $`𝖷_M^{}`$, so in particular $`𝖷_M`$ has finite entropy.

$`(3)(2).`$ If $`M`$ is not a torsion module, then it contains $`R_d`$ as a submodule. By duality, the shift action of $`^d`$ on $`𝕋^^d`$ is therefore an algebraic factor of $`𝖷_M`$. Since the former action has infinite entropy, $`𝖷_M`$ has infinite topological entropy. ∎

## 3. van Kampen’s theorem

In the proof of Theorem 1.1 the following structure theorem of van Kampen  will be used in place of the lifting of toral maps. This result splits continuous maps into a ‘linear’ part (a character) and a ‘non-linear’ part in a unique way. It is also used in this connection by Walters . We include a short proof for the convenience of the reader.

###### Theorem 3.1.

Let $`X`$ be a compact connected abelian group and let $`f:X𝕋`$ be a continuous map with $`f(e)=1`$. Then there exist a character $`\varphi \widehat{X}`$ and a continuous map $`S(f):X`$ such that

$$S(f)(e)=0,f(x)=\varphi (x)e^{2\pi iS(f)(x)}\text{ for all }xX.$$
(1)
Moreover, $`\varphi `$ and $`S(f)`$ are uniquely defined by (1).

###### Proof.

Write $`\mathrm{exp}(t)=e^{2\pi it}`$. We first prove that (1) determines $`\varphi `$ and $`S(f)`$ uniquely. Suppose that

$$f=\varphi _1(\mathrm{exp}h_1)=\varphi _2(\mathrm{exp}h_2).$$

Then $`\varphi (\mathrm{exp}h)=1`$, where $`\varphi =\varphi _1\varphi _2`$ and $`h=h_1h_2`$. Define $`p:X\times X`$ by

$$p(x,y)=h(x+y)h(x)h(y).$$

Since $`\varphi `$ and $`\mathrm{exp}`$ are homomorphisms and $`\mathrm{exp}h=\overline{\varphi }`$, it follows that $`\mathrm{exp}p`$ is trivial, so the image of $`p`$ is contained in $``$. Since $`X`$ is connected, this implies that $`p`$ is identically zero, so $`h`$ is a continuous homomorphism from $`X`$ to $``$. This forces $`h`$ to be identically zero (since $``$ has no non-trivial compact subgroups), so $`h_1=h_2`$ and $`\varphi _1=\varphi _2`$.

Turning to the existence of $`\varphi `$ and $`S(f)`$, we first consider two special cases.

1. If $`X=𝕋^n`$ for some $`n`$, then let $`\pi _1(f):^n`$ be the induced map between fundamental groups. Choose $`\varphi \widehat{X}`$ with the property that $`\pi _1(f)=\pi _1(\varphi )`$. Since the map $`f\overline{\varphi }`$ is null-homotopic and $`\mathrm{exp}:𝕋`$ is a covering map, there exists a unique continuous map $`h:X`$ such that $`h(e)=0`$ and $`f\overline{\varphi }=\mathrm{exp}h`$.
2. If $`f(X)V=\mathrm{exp}(1/4,1/4)`$ then, since the restriction of $`\mathrm{exp}`$ to $`(1/4,1/4)`$ is one-to-one, there exists a unique map

$$p:V(1/4,1/4)$$

such that $`\mathrm{exp}p`$ is the identity on $`V`$. Thus $`f=\mathrm{exp}pf`$.

To prove the general case, choose a translation-invariant metric $`\rho `$ on $`X`$. Since $`f`$ is uniformly continuous, there exists $`\delta >0`$ such that

$$\rho (x,y)<\delta f(x)\overline{f(y)}V.$$

For any finite set $`A\widehat{X}`$, let

$$X(A)=\{xX\varphi (x)=1\text{ for all }\varphi A\}.$$

Then $`X(A)`$ is a closed subgroup of $`X`$ since it is a finite intersection of kernels of characters. Moreover, the family of sets

$$\{X(A)A\widehat{X}\text{ is finite}\}$$

has the finite intersection property, and their intersection is $`\{e\}`$ since the character group separates points.

Let $`YX`$ denote the open subset defined by

$$Y=\{xX\rho (e,x)<\delta /2\}.$$

Since $`Y^c=X\backslash Y`$ is compact, there exists a finite set $`B\widehat{X}`$ such that $`X(B)Y`$. For any $`xX`$, let

$$A_x=\{f(xz)zX(B)\}𝕋.$$

Since the diameter of $`A_x`$ is strictly less than $`1/2`$, there exists a unique closed ball of minimal radius, $`B_x𝕋`$, that contains $`A_x`$. Let $`r(x)`$ be the center of $`B_x`$. The map $`xr(x)`$ is well-defined, continuous, and invariant under translations by elements of $`X(B)`$. Since $`X`$ is compact and connected, $`\widehat{X}`$ is torsion-free. On the other hand, the annihilator $`X(B)^{}`$ is finitely-generated, so $`X/X(B)`$ is isomorphic to a torus. It follows that $`r=\varphi (\mathrm{exp}p)`$ for some $`\varphi \widehat{X}`$ and some $`p:X`$ with $`p(e)=0`$. Since $`f\overline{r}(X)V`$, $`f\overline{r}=\mathrm{exp}q`$ for some $`q:X`$ with $`q(e)=0`$. Now $`f=r(f\overline{r})=\varphi (\mathrm{exp}(p+q))`$. ∎

## 4. Rigidity of equivariant maps

For any algebraic $`^d`$-action $`𝖷=(X,\alpha )`$ and for any locally compact abelian group $`A`$, denote by $`A^X`$ the group of all continuous maps

$$h:XA,h(e)=e,$$

equipped with point-wise multiplication. The action $`\alpha `$ induces the structure of an $`R_d`$-module on $`A^X`$ by defining

$$ph(x)=\underset{𝐧^d}{}p(𝐧)h\alpha (𝐧)(x).$$

A key observation is that $`\widehat{X}`$ can be regarded as a submodule of $`𝕋^X`$ with this structure.

###### Proposition 4.1.

Let $`𝖷=(X,\alpha )`$ be a connected $`^d`$-action. Then $`^X`$ and $`𝕋^X/\widehat{X}`$ are isomorphic as $`R_d`$-modules.

###### Proof.

The correspondence $`fS(f)`$ from Theorem 3.1 induces a map $`S`$ from $`𝕋^X`$ to $`^X`$. If $`f_1,f_2`$ are elements of $`𝕋^X`$ then, by the uniqueness part of Theorem 3.1, $`S(f_1\overline{f_2})=S(f_1)S(f_2)`$ so $`S`$ is a group homomorphism. Similarly, if $`\theta `$ is a continuous endomorphism of $`G`$, then $`S(f\theta )=S(f)\theta .`$ Hence $`S:𝕋^X^X`$ is an $`R_d`$-module homomorphism. For any $`f`$ in $`^X`$, $`S(e^{2\pi if})=f`$, so the map $`S`$ is surjective. Since $`\mathrm{ker}(S)=\widehat{X}`$, the statement follows. ∎

If $`f`$ and $`g`$ are functions from $`^d`$ to $``$ and $`g`$ has finite support, the convolution $`fg:^d`$ is given by

$$fg(𝐢)=\underset{𝐣^d}{}f(𝐢𝐣)g(𝐣).$$

Write $`L^2(^d)`$ for the set of all square-integrable functions $`^d`$ (with respect to the counting measure on $`^d`$).

In addition to van Kampen’s theorem, a simple version of the $`L^2`$ zero-divisor problem is needed (see  for an overview).

###### Proposition 4.2.

If $`fL^2(^d)`$ has $`fg=0`$ for some non-zero function $`g:^d`$ with finite support, then $`f`$ is identically zero.

###### Proof.

Since the support of $`g`$ is finite, there exists $`𝐧^d`$ such that the support of $`g\delta _𝐧`$ is contained in $`^d`$. Replacing $`g`$ by $`g\delta _𝐧`$ if necessary, we may assume that the support of $`g`$ is contained in $`^d`$. Let $`\widehat{f},\widehat{g}L^2(𝕋^d)`$ denote the Fourier transforms of $`f`$ and $`g`$ respectively. By the choice of $`g`$, $`\widehat{g}=p|_{𝕋^d}`$ for some non-zero polynomial $`p(𝐳)[z_1,\mathrm{},z_d]`$. Define $`V(p)𝕋^d`$ by

$$V(p)=\{x𝕋^dp(x)=0\}.$$

We claim that $`\lambda _d(V(p))=0`$ for any non-zero $`p`$, where $`\lambda _d`$ is Haar measure on $`𝕋^d`$. This may be proved by induction on $`d`$. If $`d=1`$, then $`V(p)𝕋`$ is finite since every non-zero polynomial has only finitely many roots. If $`d>1`$, choose polynomials $`p_0,\mathrm{},p_k`$ in $`[z_1,\mathrm{},z_{d1}]`$ such that

$$p(z_1,\mathrm{},z_d)=\underset{i=0}{\overset{k}{}}p_i(z_1,\mathrm{},z_{d1})z_d^i.$$

Since $`p`$ is non-zero, $`p_i`$ is non-zero for some $`i`$. By the inductive hypothesis, $`\lambda _{d1}(V(p_i))=0`$. If $`(z_1,\mathrm{},z_{d1})`$ lies in $`𝕋^{d1}\backslash V(p_i)`$, then the map $`zp(z_1,\mathrm{},z_{d1},z)`$ is a non-zero polynomial in $`[z]`$. This implies that for any $`(z_1,\mathrm{},z_{d1})𝕋^{d1}\backslash V(p_i)`$, the set

$$\{z𝕋(z_1,\mathrm{},z_{d1},z)V(p)\}$$

is finite. By Fubini’s theorem,

$$\lambda _d(V(p))=_{𝕋^{d1}}_𝕋^{}𝕀_{V(p)}\text{d}\lambda _1𝑑\lambda _{d1}=0,$$

where $`𝕀`$ is the indicator function, which proves the claim. Since $`\widehat{g}=p|_{𝕋^d}`$ and $`\widehat{f}\widehat{g}=\widehat{fg}=0`$, it follows that $`\widehat{f}=0`$ almost everywhere, so $`f=0`$. ∎

###### Lemma 4.3.

If $`𝖷=(X,\alpha )`$ is a mixing connected algebraic $`^d`$-action, then $`\mathrm{Tor}(𝕋^X)\widehat{X}`$.

###### Proof.

Let $`M`$ denote the set of all square-integrable functions

$$h:\widehat{X},h(e)=0.$$

Defining

$$ph(\varphi )=\underset{𝐢^d}{}p(𝐢)h(\varphi \alpha (𝐢))$$

for $`pR_d`$ gives $`M`$ the structure of an $`R_d`$-module.

We claim first that $`M`$ is torsion-free. Let $`h`$ be an element of $`\mathrm{Tor}(M)`$; for any non-trivial $`\chi \widehat{X}`$ define a function $`h_\chi :^d`$ by

$$h_\chi (𝐢)=h(\chi \alpha (𝐢)).$$

Since $`\alpha `$ is mixing, the map $`𝐢\chi \alpha (𝐢)`$ is one-to-one. Hence

$$\underset{𝐢^d}{}|h_\chi (𝐢)|^2\underset{\chi \widehat{X}}{}|h(\chi )|^2<\mathrm{}.$$

This shows that $`h_\chi L^2(^d)`$ for all $`\chi \widehat{X}`$. Note that $`L^2(^d)`$ itself is an $`R_d`$-module with respect to the multiplication $`ph=ph`$. Furthermore, the map $`hh_\chi `$ is an $`R_d`$-module homomorphism from $`M`$ to $`L^2(^d)`$. Since $`\mathrm{Tor}(L^2(^d))=\{0\}`$ by Proposition 4.2, we conclude that $`h_\chi =0`$ for all $`\chi `$, so $`h=0`$. This proves that $`M`$ is torsion-free.

For $`f`$ in $`^X`$, let $`\widehat{f}M`$ denote the Fourier transform of $`f`$. Since $`\widehat{f\theta }(\varphi )=\widehat{f}(\varphi \theta )`$ for any continuous endomorphism $`\theta `$ of $`X`$, the map $`f\widehat{f}`$ is an $`R_d`$-module homomorphism from $`^X`$ to $`M`$. By the Fourier inversion theorem this map is injective. Since $`\mathrm{Tor}(M)=\{0\}`$, this implies that $`\mathrm{Tor}(^X)=\{0\}`$. Proposition 4.1 then shows that $`\mathrm{Tor}(𝕋^X)\widehat{X}`$. ∎

We are now ready to prove Theorem 1.1.

###### Proof.

Suppose that $`𝖷_2`$ has finite entropy, and let $`f`$ be an equivariant continuous map $`𝖷_1𝖷_2`$. Define $`f_0:X_1X_2`$ by

$$f_0(x)=f(x)f(e).$$
(2)
Since $`f`$ is equivariant, so is $`f_0`$.

Fix an arbitrary character $`\varphi \widehat{X_2}`$. By Lemma 2.2, $`\widehat{X_2}`$ is a torsion module, so $`\varphi `$ lies in the torsion submodule of $`𝕋^{X_2}`$. Since $`f_0`$ is equivariant and $`f_0(e)=1`$, the map $`hhf_0`$ is an $`R_d`$-module homomorphism $`𝕋^{X_2}𝕋^{X_1}`$. Hence $`\varphi f_0`$ is an element of the torsion submodule of $`𝕋^{X_1}`$. By Lemma 4.3, $`\varphi f_0`$ lies in $`\widehat{X_1}`$. Since the initial choice of $`\varphi `$ was arbitrary, this shows that $`\varphi \varphi f_0`$ is a group homomorphism from $`\widehat{X_2}`$ to $`\widehat{X_1}`$. By duality, there exists a continuous homomorphism $`\theta :X_1X_2`$ such that $`\varphi f_0=\varphi \theta `$ for all $`\varphi \widehat{X_2}.`$ Since characters separate points, this implies that $`f_0=\theta `$. Hence $`f=f(e)+f_0`$ is an affine map.

If $`𝖷_2`$ has infinite entropy, then by Lemma 2.2 there exists a non-trivial closed $`\alpha _2`$-invariant subgroup $`HX_2`$ with the property that the restriction of $`\alpha _2`$ to $`H`$ is an algebraic factor of the shift action on $`(𝕋^n)^^d`$ for some $`n>0`$. Let $`K(𝕋^n)^^d`$ be a proper, closed shift-invariant subgroup such that the restriction of $`\alpha _2`$ to $`H`$ is algebraically conjugate to the shift action of $`^d`$ on $`(𝕋^n)^^d/K`$. Since any non-affine equivariant map from $`X_1`$ to $`H`$ gives rise to a non-affine equivariant map $`𝖷_1𝖷_2`$, without loss of generality we may assume that $`X_2=(𝕋^n)^^d/K`$, and $`\alpha _2`$ is the shift action.

For any continuous map $`q:X_1^n`$ define a map

$$\sigma (q):X_1(𝕋^n)^^d$$

by

$$\sigma (q)(x)(𝐧)=\mathrm{exp}q\alpha _1(𝐧)(x).$$

Let $`\pi :(𝕋^n)^^d(𝕋^n)^^d/K`$ denote the projection map. For any

$$q:X_1^n,$$

$`\pi \sigma (q)`$ is a continuous equivariant map from $`𝖷_1`$ to $`𝖷_2`$. We claim that there exists a non-zero continuous equivariant map from $`𝖷_1`$ to $`𝖷_2`$ of the form $`\pi \sigma (q)`$ for some continuous map $`q:X_1^n`$ with $`q(e)=0`$.

For any finite set $`F^d`$, let $`\mathrm{\Pi }_F`$ denote the projection map

$$\mathrm{\Pi }_F:(𝕋^n)^^d(𝕋^n)^F.$$

Since $`K`$ is a proper closed subgroup of $`(𝕋^n)^^d`$, there exists a finite set $`F^d`$, and a point $`𝐱(𝕋^n)^F`$, such that $`𝐱`$ does not lie in the image of $`\mathrm{\Pi }_F`$. Since $`𝖷_1`$ is mixing, for any $`𝐢𝐣^d`$, the kernel of $`\alpha _1(𝐢)\alpha _1(𝐣)`$ is a proper closed subgroup of $`X_1`$. In particular, there exists $`yX_1`$ such that $`ye`$, and

$$\alpha _1(𝐢)(y)\alpha _1(𝐣)(y)\text{ for any }𝐢,𝐣F.$$

Choose $`𝐳(^n)^F`$ such that $`\mathrm{exp}(𝐳(𝐢))=𝐱(𝐢)`$ for all $`𝐢F`$. Let

$$q:X_1^n$$

be any continuous map with $`q(e)=0`$ and $`q\alpha _1(𝐢)(y)=𝐳(𝐢)`$ for all $`𝐢F`$. Since $`\pi \sigma (q)(y)`$ does not lie in $`K`$, this proves the claim.

Now let $`q:X_1^n`$ be any continuous map such that $`q(e)=0`$, and $`\pi \sigma (q):X_1X_2`$ is a non-zero map. For any $`t[0,1]`$, define maps $`q_t:X_1^n`$ and $`h_t:X_1X_2`$ by $`q_t(x)=tq(x)`$, $`h_t(x)=\pi \sigma (q_t)`$. For any $`t[0,1]`$, $`h_t`$ is a continuous equivariant map from $`X_1`$ to $`X_2`$, and $`h_t(e)=e`$. We claim that $`h_t`$ is non-affine for some $`t(0,1]`$.

Suppose this is not the case. Then for each $`t[0,1]`$, $`h_t`$ is a continuous homomorphism from $`X_1`$ to $`X_2`$. Let $`Y`$ denote the set of all continuous maps from $`X_1`$ to $`X_2`$. Choose any metric $`\rho `$ on $`X_2`$ that gives the topology, and define a metric $`\rho _0`$ on $`Y`$ by

$$\rho _0(h_1,h_2)=sup\{\rho (h_1(x),h_2(x))xX_1\}.$$

The map $`th_t`$ is continuous with respect to $`\rho _0`$ and the set of all continuous homomorphisms from $`X_1`$ to $`X_2`$ forms a discrete subset of $`Y`$. Hence $`th_t`$ is constant, which contradicts the fact that $`h_0=0`$ and $`h_10`$. This proves that some $`h_t`$ is not an affine map. Since $`h_t`$ is a continuous equivariant map from $`𝖷_1`$ to $`𝖷_2`$ for any $`t[0,1]`$, Theorem 1.1 follows. ∎


text:
# Significance of log-periodic signatures in cumulative noise

## 1. Introduction

Speculative bubbles, crashes and depressions are some of the most puzzling phenomena in financial markets. Even though these are rare events they occur much more often, than expected from standard models of financial markets. For example the otherwise very successfull GARCH-Model predicts only one crash of a magnitute comparable to the events of 1929 and 1987 in 16000 years \[JS98\]. This suggest that the very largest crashes are outliers that are caused by phenomena not considered in the standard models.

Several authors \[DS96\], \[JAF96\], \[VBMA98\] have argued that this behavior is natural, if one considers the stock-market as a complex system. When this system is far away from critical points, standard models are a good description of the systems dynamics, but when a critical point is approached the dynamics change completely. In this picture a crash occurs, when a critical point is reached.

The theory of critical phenomena predicts that all observables of a complex system near a critical point are scale invariant. In the case of stock markets this would mean that the price $`p(t)`$ near a critical point should follow a power-law

$$\mathrm{log}p(t)A+B(t_ct)^\beta .$$

where $`t_c`$ is the time of crash. Unfortunately it is rather difficult to distinguish this from the exponential growth

$$\mathrm{log}p(t)A+Bt$$

predicted by standard theory.

Help in this situation comes from the concept of discrete scale invariance. If the system considered has a hirachical structure it might scale only in accordance with these hirachies. This allows the scaling coefficient $`\beta `$ to be a complex number and the observables will obey

$`\mathrm{log}p(t)`$ $`Re(A+B(t_ct)^\beta )`$
$`=A+B(t_ct)^\alpha +C(t_ct)^\alpha \mathrm{cos}(\omega ln(t_ct)+\varphi ),`$
Such a power-law with log-periodic signature is much easier to detect than a pure power-law. In fact sizable log-periodic signatures have been detected before many financial crashes, including the ones from 1929 and 1987 (\[DS96\], \[JAF96\], \[VBMA98\], \[SLJ99\], \[AJ00\]). Also they have been found after the bursting of some speculative bubbles, for example gold after 1980, the Nikkei-Index after 1990 and most recently after the bursting of the new economy bubble in 2000 (\[AJ99\], \[SZ02\]).

Still there is some reason for doubt. As several authors have pointed out (\[HJL+00\], \[Fei01b\]), log-periodic signatures can often arise by chance in systems that do not exhibit discrete scale invariance. Even simple Brownian motion produces log-periodic signatures quite often. Therefore there has been a heated discussion about the significance of the found log-periodic signatures in financial data \[Fei01b\], \[SJ01\], \[Fei01a\].

One tool to detect these signatures has been the Lomb periodogram introduced by Lomb \[Lom76\] and improved by Scargle in \[Sca82\]. An important property of Scargle’s periodogram is that the individual Lomb powers of independently normal distributed noise follow approximately an exponential distribution.

Unfortunately this property is lost, when one calculates Scargle’s periodogram for cumulative noise, where the differences between two observations are independently normal distributed. In this Brownian-Motion case, the expected Lomb powers are much greater for small frequencies than for large ones. Therefore the significance of large Lomb powers at small frequencies is difficult to estimate. Huang, Saleur, Sornette and Zhou tackle this problem and several related ones with extensive Monte Carlo simulations in \[HJL+00\] and \[ZS02\].

In this paper we present an analytic approach to the problem of estimating the significance of log-periodic signatures. We start by introducing a small correction to Scargle’s Lomb periodogram, that makes the distribution of Lomb powers exactly exponential for independently normal distributed noise.

In the second part we use the same methods to derive a normalisation of the Lomb periodogram that assures an frequency independent exponential distribution of Lomb powers for cumulative noise.

In the last section we apply these new methods to estimate the significance of log-periodic signatures in so called S&P 500-anti-bubble after the crash of 2000. We show how our methods greatly simplify the whole analysis and derive that there is about a $`6\%`$ chance that a signature like the one detected by Sornette and Zhou in \[SZ02\] arises by chance if one only considers frequencies smaller than $`10.0`$. If one searches all frequencies up to the Nyquist frequency, peaks of this height become much more common.

Furthermore we detect equally significant peaks at harmonics of the fundamental frequency of Sornette and Zhou. This complements evidence for a more sophisticated modelling of the S&P 500 anti-bubble by Sornette and Zhou in \[ZS03\].

We would like to thank Volker Möller for hosting our database of financial data and donating cpu-time for the Monte Carlo simulations that lead to this paper.

## 2. Independent Noise

Consider the classical periodogram

$$P(\omega )=\frac{1}{N_0}\left[\left(\underset{j=1}{\overset{N_0}{}}X_j\mathrm{cos}\omega t_j\right)^2+\left(\underset{j=1}{\overset{N_0}{}}X_j\mathrm{sin}\omega t_j\right)^2\right].$$

This is a generalization of the Fourier transform to the case of unevenly spaced measurements. Unfortunately this classical form has difficult statistical behavior for uneven spacing. Scargle therefore proposed in \[Sca82\] a normalized from of the periodogram, that restores good statistical properties in the case where all $`X_j`$ are independently normal distributed with mean zero and variance $`\sigma _0^2`$. For this he observes that

$$S(w)=\underset{j=1}{\overset{N_0}{}}X_j\mathrm{cos}\omega t_j$$

and

$$C(w)=\underset{j=1}{\overset{N_0}{}}X_j\mathrm{sin}\omega t_j$$

are again normally distributed, with variances

$$\sigma _c^2=N_0\sigma _0^2\underset{j=1}{\overset{N_0}{}}\mathrm{cos}^2\omega t_j$$

and

$$\sigma _s^2=N_0\sigma _0^2\underset{j=1}{\overset{N_0}{}}\mathrm{sin}^2\omega t_j.$$

Also he claims that for normally distributed random variables with unit variance their sum of squares is exponentially distributed. Therefore he proposes to look at

$$P(\omega )=\left[\frac{\left(_{j=1}^{N_0}X_j\mathrm{cos}\omega t_j\right)^2}{\sigma _c}+\frac{\left(_{j=1}^{N_0}X_j\mathrm{sin}\omega t_j\right)^2}{\sigma _s}\right].$$

Scargles claim, that this sum is exponentially distributed is only correct when $`S(\omega )`$ and $`C(\omega )`$ are independent. This is approximately true, when the observation times $`t_j`$ are ”not to badly bunched”. In other cases whole variance/covariance matrix

$$\mathrm{\Sigma }=\left(\begin{array}{cc}\sigma _c^2& \sigma _{cs}\\ \sigma _{cs}& \sigma _s^2\end{array}\right)$$

with

$$\sigma _{cs}=N_0\sigma _0^2\underset{j=1}{\overset{N_0}{}}\mathrm{cos}\omega t_j\mathrm{sin}\omega t_j$$

has to be considered.

If $`\mathrm{\Sigma }`$ is invertible the values of the quadratic form

$$P(\omega )=\frac{1}{2}(C(\omega ),S(\omega ))\mathrm{\Sigma }^1\left(\begin{array}{c}C(\omega )\\ S(\omega )\end{array}\right)$$

are exponentially distributed, i.e.

$$Probability(P(\omega )>z)=\mathrm{exp}(z).$$

by standard facts about multivariate normal distributions (for example \[Mui82, Theorem 1.4.1\]). Explicitly we can calculate

$$\mathrm{\Sigma }^1=\frac{1}{\sigma _c^2\sigma _s^2\sigma _{cs}^2}\left(\begin{array}{cc}\sigma _s^2& \sigma _{cs}\\ \sigma _{cs}& \sigma _c^2\end{array}\right).$$

This means the natural form of the periodogram is

$$P(\omega )=\frac{1}{2}\frac{\sigma _s^2C^2(\omega )+\sigma _c^2S^2(\omega )2\sigma _{cs}C(\omega )S(\omega )}{\sigma _c^2\sigma _s^2\sigma _{cs}^2},$$

which reduces to Scargle’s case for $`C`$ and $`S`$ independent ($`\sigma _{cs}=0`$), and to the classical case for even spacing ($`\sigma _c=\sigma _s`$). This $`P(\omega )`$ is always exponentially distributed.

As Scargle we also replace $`t_j`$ by $`t_j\tau `$ with

$$\tau =\frac{1}{2\omega }\mathrm{arctan}\frac{_{j=1}^{N_0}\mathrm{sin}2\omega t_j}{_{j=1}^{N_0}\mathrm{cos}2\omega t_j}$$

in all formulas, to make the diagram time-translation invariant.

## 3. Cumulative Noise

Assume now, that the differences $`Y_j=(X_jX_{j1})`$ are independently normal distributed with zero mean and variance $`\sigma _0^2`$. Then the distribution of powers in Scargle’s periodogram depends on the angular frequency $`\omega =2\pi f`$. See figure 1 for the result of a Monte Carlo simulation of this case. In small frequencies much higher Lomb powers can occur by chance, then in high frequencies. This reflects the well known fact that the expected value at frequency $`f`$ of the evenly spaced Fourier transform of a brownian motion is proportional to $`1/f^2`$. Our idea is now to normalize the periodogram by adjusting Scargle’s methods to this case.

First notice that

$$X_jX_0=\underset{k=1}{\overset{j}{}}Y_k$$

in this situation. From this we obtain

$`C(\omega )`$ $`={\displaystyle \underset{j=1}{\overset{n}{}}}(X_jX_0)\mathrm{cos}\omega t_j`$
$`={\displaystyle \underset{j=1}{\overset{n}{}}}\left({\displaystyle \underset{k=1}{\overset{j}{}}}Y_k\right)\mathrm{cos}\omega t_j`$
$`={\displaystyle \underset{k=1}{\overset{n}{}}}Y_k{\displaystyle \underset{j=k}{\overset{n}{}}}\mathrm{cos}\omega t_j`$
and a similar formula for $`S(\omega )`$. Notice that $`C(\omega )`$ and $`S(\omega )`$ are still normally distributed with

$`\sigma _c^2`$ $`=C^2(\omega )`$
$`={\displaystyle \underset{kl}{}}Y_k,Y_l\left({\displaystyle \underset{j=k}{\overset{n}{}}}\mathrm{cos}\omega t_j\right)\left({\displaystyle \underset{j=l}{\overset{n}{}}}\mathrm{cos}\omega t_j\right)`$
$`=\sigma _0^2{\displaystyle \underset{k=1}{\overset{n}{}}}\left({\displaystyle \underset{j=k}{\overset{n}{}}}\mathrm{cos}\omega t_j\right)^2`$
and

$`\sigma _s^2`$ $`=S^2(\omega )`$
$`={\displaystyle \underset{kl}{}}Y_k,Y_l\left({\displaystyle \underset{j=k}{\overset{n}{}}}\mathrm{sin}\omega t_j\right)\left({\displaystyle \underset{j=l}{\overset{n}{}}}\mathrm{sin}\omega t_j\right)`$
$`=\sigma _0^2{\displaystyle \underset{k=1}{\overset{n}{}}}\left({\displaystyle \underset{j=k}{\overset{n}{}}}\mathrm{sin}\omega t_j\right)^2`$
and

$`\sigma _{cs}`$ $`=C(\omega )S(\omega )`$
$`={\displaystyle \underset{kl}{}}Y_k,Y_l\left({\displaystyle \underset{j=k}{\overset{n}{}}}\mathrm{sin}\omega t_j\right)\left({\displaystyle \underset{j=l}{\overset{n}{}}}\mathrm{cos}\omega t_j\right)`$
$`=\sigma _0^2{\displaystyle \underset{k=1}{\overset{n}{}}}\left({\displaystyle \underset{j=k}{\overset{n}{}}}\mathrm{cos}\omega t_j\right)\left({\displaystyle \underset{j=k}{\overset{n}{}}}\mathrm{sin}\omega t_j\right).`$
With these values

$$P(\omega )=\frac{1}{2}\frac{\sigma _s^2C^2(\omega )+\sigma _c^2S^2(\omega )2\sigma _{cs}C(\omega )S(\omega )}{\sigma _c^2\sigma _s^2\sigma _{cs}^2},$$

is again exponentially distributed:

$$Probability\left(P(\omega )>z\right)=\mathrm{exp}(z)$$

In particular the distribution is now independent of $`\omega `$ as exemplified by figure 2 which shows the cumulative Lomb periodogram for a Monte Carlo simulation as above.

Notice that is essential to consider the correlation between $`C(\omega )`$ and $`S(\omega )`$ in this case. Figure 3 shows the cumulative Lomb periodograms for 1000 random walks of length 500 in logarithmic time without the correlation term above. Notice how this introduces spurious peaks at several frequencies.

Again we replace $`t_j`$ by $`t_j\tau `$ with

$$\tau =\frac{1}{2\omega }\mathrm{arctan}\frac{_{j=1}^{N_0}\mathrm{sin}2\omega t_j}{_{j=1}^{N_0}\mathrm{cos}2\omega t_j}$$

in all formulas, to make the diagram time-translation invariant.

## 4. Application to log-periodicity in financial data

Recently Sornette and Zhou have suggested that there is a log periodic signature in the S&P 500 index after the bursting of the new economy bubble \[SZ02\]. Among other methods they use Scargle’s periodogram with $`\stackrel{~}{t}_j=\mathrm{log}(t_jt_c)`$ and $`X_j`$ the logarithm of the index price $`j`$ days after a critical date $`t_c`$ for frequencies $`0f10`$. To account for a nonlinear trend of the form

$$A+B(t_jt_c)^\alpha $$

they first detrend the index values. For this they use a value of $`A`$ obtained from a nonlinear fit of

$$()A+B(t_jt_c)^\alpha +C(t_jt_c)^\alpha \mathrm{cos}(\omega \mathrm{ln}(t_jt_c)+\varphi )$$

to the logarithm of the index price and then determine $`B`$ and $`\alpha `$ for different choices of $`t_c`$ by linear regression.

We follow the same procedure, but estimate $`A`$ by a different method. For this we consider the correlation coefficient

$$r_A=\frac{_i(\stackrel{~}{t}_j\overline{t})(\mathrm{log}(X_jA)\overline{X})}{\sqrt{_i(\stackrel{~}{t}_j\overline{t})^2}\sqrt{_i(\mathrm{log}(X_jA)\overline{X})^2}}$$

with $`\overline{t}`$ the average of the $`\stackrel{~}{t_j}`$’s and $`\overline{X}`$ the average of the $`\mathrm{log}(X_jA)`$’s. This correlation coefficient measures how well $`\mathrm{log}(X_jA)`$ can be approximated by a linear model

$$\mathrm{log}B+\alpha \mathrm{log}(t_jt_c).$$

Notice that $`r_A`$ does not depend on $`B`$ and $`\alpha `$. Since correlation coefficiens near $`+1`$ and $`1`$ indicate strong explanatory value of the proposed trend, while coefficients near $`0`$ indicate that a trend with this value of $`A`$ seems not to be present, we first search the value of $`A`$ that maximises $`r_A^2`$. Then, like Sornette and Zhou, we find $`B`$ and $`\alpha `$ by linear regression

With this method we address a critique of Feigenbaum \[Fei01a\]. He points out that the detection of log-periodicity by lomb periodograms is not independent of the detection via nonlinear fits of equation $`()`$ to the price data, if values produced by the second are reused in the first. Our approach eliminates this dependance.

Figure 4 shows the highest Lomb powers obtained by this method for $`2`$-year intervals starting from August $`1`$st to September $`5`$th, 2000. The highest peak in our dataset is observed for the critical date August $`22`$th, 2000. This is in reasonable agreement with the critical date found by Sornette and Zhou (August $`9`$th, 2000).

To estimate the significance of this peak we calculated the 203 Lomb periodograms of $`2`$-year intervals starting at the $`22`$nd of each month from Jannuary $`1984`$ to November $`2000`$. Figure 5 shows a comparison of these periodograms with the one from August $`22`$nd, 2002. Notice that the distribution of Lomb-powers depends strongly on the frequency. For small frequencies high Lomb powers are much more probable than at high frequencies. The absence of large powers for very small frequencies is due to the detrending procedure. These facts have also been observed by \[HJL+00\] in a somewhat different setting.

Notice also that the peak at $`f1.6`$ is nevertheless quite large, in fact it is the largest one observed at this frequency. But how probable is it that we have a peak of this relative height for any of the tested frequencies? The SnP500 data set is not large enough, to estimate this probability accurately, but a count shows that there are 39 datasets that have at least one frequency with a peak that is higher than any of the other at the same frequency. This gives a naive estimate of $`39/20219,3\%`$.

The cumulative Lomb periodogram proposed above improves and greatly simplifies this analysis. Figure 6 shows the cumulative Lomb periodograms of the S&P 500 anti-bubble together with the cumulative Lomb periodograms of all other datasets. A detrending of the data as above was not necessary. Notice that there are now several peaks of comparable size at frequencies $`1.7`$, $`3.4`$, $`7.4`$ and $`8.4`$. The fact that these lie close to the harmonics of $`1.7`$ compares well to the results of \[ZS03\].

We have included the theoretical $`99.9\%`$, $`99\%`$ and $`95\%`$-quantiles for each frequency derived above together with the $`95\%`$-quantiles of the actual S&P 500 data. Notice the excellent agreement for frequencies greater than $`1`$.

Since the height of the peaks is now largely independent from the frequency, we can estimate the global significance of the peak at $`1.7`$ with cumulative Lomb power $`5.61`$ by counting the number of cumulative Lomb-periodograms with at least one peak of higher power for frequencies $`0f10`$. We find $`12`$ of those which implies a significance of approximately $`12/2035.9\%`$. In figure 7 we compare the global significance of peaks in cumulative Lomb periodograms of the S&P 500 with those obtained from a Monto Carlo simulation of brownian motion with zero mean and unit variance . There is a reasonable agreement for significances smaller than $`0.1`$ even though brownian motion is only a very rough model of stock market prices.

Notice that the global significance of a peak depends strongly on the number of frequencies considered. If we consider all frequencies up to the Nyquist frequency for the average sampling interval

$$f_N=\frac{N_0}{2T}=\frac{500}{2\mathrm{log}(500)}40.2,$$

a peak of height $`5.61`$ as above is found in $`27.6\%`$ of simulated periodograms and in $`28.3\%`$ of the historical S&P 500 periodograms. In this light the choice of $`0f10`$ by Sornette and Zhou seems to call for an apriori justification if one wants to keep up the claim of a significant log-periodic signature around $`f=1.7`$.

## 5. Conclusion

We have indrocuced a new version of the Lomb periodigram that exhibits good statistical properties when applied to cumulative noise. With this we were able to detect the log-periodic signature in the S&P 500 anti-bubble with better significance than with the ususal periodigram, even without a detrending procedure. More importantly this method allows us to estimate the significance of the found log periodic signature which is a reasonable $`5.9\%`$ if we only consider fequencies smaller than $`10.0`$, and a disappointing $`27.6\%`$ if one considers all frequencies up to the Nyquist frequency for the average sampling interval. We also detect cumulative Lomb peaks of similar significance at harmonics of the fundamental frequency $`1.7`$.


text:
# Enhanced Production of Neutron-Rich Rare Isotopes in Peripheral Collisions at Fermi Energies

## Abstract

A large enhancement in the production of neutron-rich projectile residues is observed in the reactions of a 25 MeV/nucleon 86Kr beam with the neutron rich 124Sn and 64Ni targets relative to the predictions of the EPAX parametrization of high-energy fragmentation, as well as relative to the reaction with the less neutron-rich 112Sn target. The data demonstrate the significant effect of the target neutron-to-proton ratio (N/Z) in peripheral collisions at Fermi energies. A hybrid model based on a deep-inelastic transfer code (DIT) followed by a statistical de-excitation code accounts for part of the observed large cross sections. The DIT simulation indicates that the production of neutron-rich nuclides in these reactions is associated with peripheral nucleon exchange in which the neutron skins of the neutron-rich 124Sn and 64Ni target nuclei may play an important role. From a practical viewpoint, such reactions between massive neutron-rich nuclei offer a novel synthetic avenue to access extremely neutron-rich rare isotopes towards the neutron-drip line.

Rare isotope production, neutron-rich nuclides, nuclear reactions, deep inelastic transfer, Fermi energy, peripheral collisions, neutron skin

Exploration of the nuclear landscape towards the neutron-drip line Moller et al. (1997) is currently of great interest in order to elucidate the evolution of nuclear structure with increasing neutron-to-proton ratio (N/Z) Casten and Sherrill (2000); Meng and Ring (1998) and understand important nucleosynthesis pathways Sneden and Cowan (2003), most notably the r-process Langanke and Wiescher (2001). Reactions induced by neutron-rich nuclei provide invaluable information on the isospin dependence of the nuclear equation of state Danielewicz et al. (2002); Li (2002). Extremely neutron-rich nuclei offer the unprecedented opportunity to extrapolate our knowledge to the properties of bulk isospin-rich matter, such as neutron stars Pethick and Ravenhall (1995); Sil et al. (2002). The efficient production of very neutron-rich nuclides is a key issue in current and future rare isotope beam facilities around the world Morrissey (2002); Nolen (2002); Guerreau (2002) and, in parallel, the search for new synthetic approaches is of exceptional importance.

Neutron-rich nuclides have traditionally been produced in spallation reactions, fission, and projectile fragmentation Geissel and Munzenberg (1995). In high-energy fragmentation reactions, the production of the most neutron-rich isotopes is based on a “clean-cut” removal of protons from the projectile. The world’s data on fragmentation cross sections are well represented by the empirical parametrization EPAX Sümmerer and Blank (2000). EPAX is currently the common basis for predictions to plan rare beam experiments and facilities. In addition to the widely used projectile fragmentation approach, neutron-rich nuclides can be produced in multinucleon transfer reactions Corradi et al. (2002) and deep-inelastic reactions near the Coulomb barrier (e.g. Volkov (1978); Broda (2002); Lee et al. (1997)). In such reactions, the target N/Z significantly affects the production cross sections, but the low velocities of the fragments and the ensuing wide angular and ionic charge state distributions render practical applications rather limited.

The Fermi energy regime (20–40 MeV/nucleon) Fuchs and Möhring (1994) offers the unique opportunity to combine the advantages of both low- and high-energy reactions. At this energy, the synergy of projectile and target enhances the N/Z of the fragments, while the velocities are high enough to allow efficient in-flight collection and separation. Early work on neutron-rich fragment production from heavy projectiles at Fermi energies Borrel et al. (1986); Bacri et al. (1993); Bazin et al. (1990) provided no production cross sections, hampering quantitative comparisons to parametrizations or reaction simulations. In order to explore the possibilities offered at Fermi energies, we recently undertook an experimental study of the production cross sections of projectile residues from the reaction 25 MeV/nucleon 86Kr+64Ni, in which enhanced production of neutron-rich fragments was observed Souliotis et al. (2002).

In this Letter, we focus on a subsequent detailed study of near-projectile residues from the reactions of 86Kr (25 MeV/nucleon) with 124Sn and 112Sn targets and present a comparison with the results from 86Kr+64Ni Souliotis et al. (2002), as well as with the expectations of EPAX Sümmerer and Blank (2000). We demonstrate that the production of neutron-rich projectile residues is substantially enhanced in the reactions involving the most neutron-rich systems and we provide an interpretation based on a deep inelastic transfer model.

The measurements were performed at the Cyclotron Institute of Texas A&M University, following the experimental scheme of our previous work Souliotis et al. (2002). A concise description is given in the following. A 25 MeV/nucleon 86Kr22+ beam ($``$1 pnA) from the K500 superconducting cyclotron interacted with 124Sn and 112Sn targets (2 mg/cm2). Projectile residues were analyzed with the MARS recoil separator Tribble et al. (1989) offering an angular acceptance of 9 msr and momentum acceptance of 4%. The beam struck the target at 4.0o relative to the optical axis of MARS. Thus, fragments were accepted in the polar angular range 2.7o–5.4o (lying inside the grazing angle of 6.5o for the Kr+Sn reaction at 25 MeV/nucleon). At the MARS focal plane, the fragments were collected in a two-element ($`\mathrm{\Delta }`$E, E) Si detector telescope. Time of flight was measured between two PPACs (parallel plate avalanche counters) placed at the MARS dispersive image and at the focal plane, respectively. The horizontal position from the first PPAC and the field of the MARS first dipole magnet determined the magnetic rigidity, $`B\rho `$. The fragments were characterized event-by-event by energy-loss, residual energy, time of flight, and $`B\rho `$. With the procedures described in Ref. Souliotis et al. (2002), the atomic number Z, the ionic charge q, the mass number A and the velocity were obtained with high resolution (0.5, 0.4, 0.6 units and 0.3%, respectively). After summation over ionic charge states (with corrections for missing charge states), fragment cross sections with respect to Z, A and velocity were obtained in the angular range 2.7o–5.4o and $`B\rho `$ range 1.3–2.0 T m. To extract total cross sections, the measured yield data were corrected for the limited angular acceptance and magnetic rigidity range covered. The corrections were obtained from the ratio of the total to the filtered cross sections (with angular and momentum acceptance cuts) calculated using the simulation approach described below. The corrections involved an azimuthal angular factor of 10 and mass-dependent polar factors ranging from 2 to 4 for A=85 to 50, respectively (resulting in, e.g., a total factor of 20 for fragments very close to the projectile). The systematic uncertainty in the extracted cross sections is estimated to be a factor of 2 Souliotis et al. (2002).

Fig. 1 shows the results of the mass distributions (cross sections) of elements Z=30–35 from the reactions of 86Kr (25 MeV/nucleon) with 124Sn (full circles) and 112Sn (full squares). The dotted lines are the predictions of the EPAX parametrization Sümmerer and Blank (2000). We observe that the neutron-rich projectile fragments produced in the reaction with the more neutron-rich 124Sn (N/Z=1.48) target have considerably larger yields compared to those obtained in the reaction with the less neutron-rich 112Sn target (N/Z=1.24). Typical ratios are 3–10 for the most neutron-rich isotopes observed in both reactions. In most of the cases of the present data, the most neutron-rich nuclides have been observed only in the 86Kr+124Sn reaction. Compared to EPAX, the yields from 86Kr+124Sn are substantially larger, whereas those from 86Kr+112Sn are in reasonable agreement with EPAX. It should be pointed out that EPAX represents an abrasion-ablation type of fragmentation scenario in which the target is a mere spectator having (almost) no effect on the production cross section (apart from a geometrical factor) Sümmerer and Blank (2000). To quantify the comparison between the present data and EPAX, we show in Fig. 2a the ratio of the measured cross sections of fragments with Z=28–35 from 86Kr+124Sn with respect to EPAX expectations. The same ratio is presented in Fig. 2b for our previous data on 86Kr+64Ni Souliotis et al. (2002). In the EPAX calculation, we extended the prediction up to one neutron pick-up products to allow comparison with the present data. However, our data on 86Kr+124Sn and 86Kr+64Ni show the production of nuclides with up to 3–4 neutrons picked-up from the target, along with usual proton removal products. In both figures, we observe that for nuclei far from the projectile (Z=28–30), as well as for N/Z less than that of the projectile (N/Z=1.39, arrow in Fig. 2), the experimental cross sections are in remarkable agreement with EPAX (within a factor of $``$2). However, for heavier elements (Z=31–35) and for progressively higher N/Z, a striking increase in the ratio is observed, especially for near-projectile products involving neutron pick-up. The observed yield amplification over EPAX for neutron-rich nuclei demonstates the dramatic effect of the neutron-rich target on the production mechanism at Fermi energies, which involves substantial nucleon exchange Veselsky et al. (2000).

To gain insight into the mechanism of neutron-rich nuclide production at this energy, we performed simulations using a hybrid Monte Carlo approach, as in Souliotis et al. (2002). The dynamical stage of the collision was described by the deep inelastic transfer (DIT) code of Tassan-Got Tassan-Got and Stefan (1991) and the de-excitation stage was simulated by the statistical code GEMINI Charity et al. (1988). Comparison of the DIT/GEMINI predictions with the data is shown in Fig. 3 for Se (Z=34), Ge (Z=32) and Zn (Z=30) (thick solid lines). We observe that the calculation describes well, in most cases, the central and the neutron-deficient part of the measured distributions. However, it cannot fully account for the enhancement observed on the neutron-rich sides for near-projectile elements. Backtracing of the DIT simulations indicates that neutron-rich products originate in peripheral collisions in which the projectile–target density distributions overlap by up to 1–1.5 fm. For larger projectile–target overlaps, the observed enhancement diminishes and the cross sections agree with DIT/GEMINI Souliotis et al. (2002) and EPAX (Fig. 2). It is worth noting the large cross sections from 86Kr+64Ni Souliotis et al. (2002) relative to 86Kr + 112Sn, although the targets have nearly equal N/Z. In this case it is their position with respect to the valley of $`\beta `$-stability (64Ni is neutron-rich and 112Sn is neutron-poor) that determines the nucleon flow. Consequently, the potential energy surface (appropriately taken into account in the DIT code) plays a definitive role in the production of neutron-rich fragments at Fermi energies.

We should point out that, in the original DIT code Tassan-Got and Stefan (1991), the nuclei are assumed spherical with homogeneous neutron and proton density distributions. However, it is well established that neutron-rich nuclei possess neutron-skins; namely, their neutron density distributions extend further out relative to the proton distributions. As well known, the neutron skin is predicted by a variety of theoretical models including microscopic Thomas-Fermi, Skyrme Hartree-Fock and relativistic mean-field approaches (e.g. Kolomietz et al. (2001),Brown (1998),Hofmann et al. (2001)). Also, it has recently been demonstrated experimentally in annihilation studies of antiprotonic atoms Trzcinska et al. (2001). Some time ago, Harvey Harvey (1985) took into consideration the neutron skin of heavy targets (208Pb, 197Au) in a microscopic nucleon-nucleon scattering model to explain the enhanced production of neutron-rich projectile fragments from 16O and 20Ne at Fermi energies relative to those at relativistic energies. His approach also served as an interpretation of the N/Z properties of projectile fragment yield data from 40Ar (44 MeV/nucleon) on heavy targets Borrel et al. (1986). Although the DIT code employed in our simulations is based on nucleon exchange (rather than nucleon-nucleon collisions) in the overlap zone, we may attribute its partial success to describe the observed enhanced cross sections to the inadequate treatment of peripheral nucleon exchange, in which the neutron skins of the reaction partners may play important roles. To investigate this assumption further, we included neutron and proton density distributions into the DIT code. The density distributions were calculated with a microscopic Thomas-Fermi code Kolomietz et al. (2001) and employed in DIT. In the simulation, at a given projectile-target overlap and a given nucleon exchange site, the transfer probabilities were scaled by the local peripheral (“halo”) factors, $`(\rho _n/\rho _p)/(N/Z)`$, of the respective reaction partners. The change of the density profiles was followed during the (sequential) nucleon exchange. The results of this modified-DIT/GEMINI calculation are shown in Fig. 3 by dashed lines. A qualitative improvement in the description of the neutron-rich sides of the distributions for near-projectile elements from the very neutron-rich systems 86Kr+64Ni and 86Kr+124Sn is found. However, for the 86Kr+112Sn reaction, the standard DIT/GEMINI calculation agrees better with the data. These calculations indicate, although qualitatively, the possible effect of the neutron skin of the neutron-rich targets 64Ni and 124Sn in the observed enhancement. Guided by these observations, we infer that an improved deep-inelastic transfer model, or an equivalent approach, which self-consistently takes into account the neutron and proton density distributions of the reaction partners may account for the large cross sections of the neutron-rich products observed in such reactions.

From a practical viewpoint, the large production cross section of neutron-rich fragments indicate that such reactions offer an attractive approach to produce very neutron-rich nuclides. Apart from direct in-flight or IGISOL-type options, we propose the application of such reactions as a second stage in two-stage rare beam production schemes. For example, a beam of 92Kr from an ISOL-type facility (or, from the proposed Rare Isotope Accelerator Facility (RIA) Morrissey (2002); Nolen (2002)) can be accelerated around the Fermi energy and interact with a very neutron-rich target (e.g. 64Ni, 124Sn, 208Pb, 238U) to produce extremely neutron-rich nuclides that cannot be accessed by fission or projectile fragmentation. A quantitative prediction of rates of such nuclides will be possible after further experimental studies and improvement of the description of peripheral collisions between very neutron-rich heavy nuclei in the Fermi energy regime.

In summary, a substantial enhancement in the production cross sections of neutron-rich projectile fragments is observed in the reactions 86Kr (25 MeV/nucleon)+124Sn and 86Kr (25 MeV/nucleon)+64Ni relative to the EPAX parametrization, as well as relative to the less neutron-rich system 86Kr+112Sn. The hibrid DIT/GEMINI model provides a partial interpretation of the observed cross sections. The DIT simulations indicate that the enhanced production of neutron-rich isotopes in the reactions 86Kr+124Sn and 86Kr+64Ni is associated with peripheral nucleon exchange. In such collisions, the neutron skins of the 124Sn and 64Ni target nuclei may play a significant role. For practical purposes, such reactions offer a novel and competitive pathway to produce extremely neutron-rich isotopes towards the neutron-drip line.

We are thankful to L. Tassan-Got for his DIT code and useful suggestions. We also wish to thank A. Sanzhur for insightful discussions and R. Charity for using the GEMINI code. We gratefully acknowledge the support of the operations staff of the Cyclotron Institute during the measurements. Financial support for this work was provided, in part, by the U.S. Department of Energy under Grant No. DE-FG03-93ER40773 and by the Robert A. Welch Foundation under Grant No. A-1266.