text:
# Cluster expansions in dilute systems: applications to satisfiability problems and spin glasses

## 1 Introduction

Very few analytical tools have been successfully employed to study disordered systems beyond mean-field. Mainly, one can mention the functional renormalization group analysis , high-temperature expansions of finite dimensional systems , expansion in the concentration of disordered models defined on finite dimensional lattices  and expansions around mean-field theories . The replica method has been used to study dilute spin-glass models - and, even if it allows one to obtain a number of analytical results, it has revealed particularly difficult to implement when applied to dilute systems. It is then desirable to develop other analytical methods to treat these problems, at least in their simplest phase. In this article we investigate an independent analytic approach that is based on a cluster expansion. It allows one to compute several “additive” quantities of interest in dilute systems such as the energy density, the entropy, the free-energy, etc. We shall apply this tool to the study of two standard problems, with definitions recalled below, that are random K-satisfiability (K-sat)  and the Viana-Bray dilute spin-glass . The method is similar to one of the techniques used by Weigt and Hartmann  in their study of the vertex-cover problem on a random graph. The application to other dilute systems is straightforward. Some of the advantages of this method with respect to replicas are: it allows one to compute the corrections to the thermodynamic limit in a simple way; it allows one to pinpoint a possible limitation of the replica symmetric (rs) Ansatz in the satisfiable and paramagnetic (pm) phases of dilute disordered systems and, not less importantly, it can be straightforwardly adapted to study the evolution of some of the algorithms developed to analyze K-sat numerically .

The paper is organized as follows. In Section 2 we define the random K-sat problem and recall its main properties. In Section 3 we define the clusters, as well as several useful notions associated to them, and we introduce the cluster expansion. Section 4 is devoted to the explicit calculation of the entropy of K-sat. The finite $`N`$ corrections are also described. In Section 5 we discuss the interplay between the percolation and easy-to-hard transition. We underline the consequences of this calculation as regards to the validity of the rs Ansatz in the satisfiable and pm phases. As an application to a physical system, we discuss the calculation of the paramagnetic pm free-energy of the Viana-Bray  dilute spin-glass in Section 6. Finally, in Section 7 we present our conclusions.

## 2 K-satisfiability

The theory of complexity has been developed to characterize worst-case instances of hard computational problems . A classification scheme, according to the time needed to find solutions with the best performing algorithms, or to prove that a problem is not solvable, is one of the outcomes of these studies. Of particular importance is the problem of K-satisfiability  (K-sat) that has been used as a testing ground for these theories.

However, it has been recently realized that in many interesting cases in computer science, it is more relevant to determine the properties of typical, and not worst, realizations of a given problem . Random K-sat, defined as the ensemble of randomly generated instances of K-sat, is the paradigm and the goal is now to predict the behavior of a typical element of the ensemble.

The relation between phase transitions, or threshold phenomena, and intractability in random combinatorial problems has been stressed by several authors . Problems that are very hard to solve in the worst case, are not so in the typical case, unless the control parameter takes values within a finite interval that defines the critical region. Away from the critical region, simple algorithms are capable of finding a solution, or showing that there is no solution, in polynomial time. Random K-sat has a well-defined threshold phenomenon.

Random K-sat, as well as other random optimization problems, can be mapped onto disordered spin models. The mapping is done by associating the cost function in the optimization problem to an energy density in the physical system . Consequently, the random character associated to the choice of different instances in the optimization problem translates into quenched disordered interactions in the physical system. The most interesting optimization problems like K-sat become spin-glass models of a particularly difficult type, where each spin interacts with a finite fraction of other spins in the sample. These are called dilute spin-glasses and they are interesting per se since they appear as a case of intermediate difficulty between solvable mean-field spin-glasses and realistic finite dimensional ones.

The quest of the threshold value of the control parameter becomes then a search for a phase transition. Thus, all tools developed to treat disordered physical systems in statistical mechanics  can be adapted to study random optimization problems. In the context of random K-sat two main techniques have been used so far: the replica approach in the thermodynamic limit  and numerical simulations complemented by finite size scaling when the number of variables remains finite . The same two techniques are used in the study of dilute spin-glasses.

Random K-sat is defined as follows. Consider $`N`$ Boolean variables, $`\{x_1,\mathrm{},x_N\}`$, that can take two logical values $`x_i=`$ TRUE or FALSE, for each $`i`$. Firstly, choose K indices from the set of $`N`$ elements, $`i=1,\mathrm{},N`$. Secondly, assign to each of these indices the literal $`x_j`$, or its negation $`\overline{x}_j`$, with equal probability $`p=1/2`$. Thirdly, construct a clause $`C_1`$ as the logical OR ($``$) of the K previously determined literals. If K$`=3`$ and $`N=10`$ a possible clause is $`x_1\overline{x_5}x_7`$. New clauses are generated in identical manner, independently of the previous ones. One usually calls $`M`$ the total number of clauses. A formula $`F`$ is the logical AND ($``$) of $`M`$ such clauses. It reads

$$F=\underset{l=1}{\overset{M}{}}C_l=\underset{l=1}{\overset{M}{}}\left(\underset{i=1}{\overset{K}{}}z_i^l\right),$$
(1)
where $`z_i^l\{x_1,\overline{x}_1,\mathrm{},x_N,\overline{x}_N\}`$. A solution, if it exists, is an assignment of the $`N`$ variables that satisfies $`F`$, that is to say, for which all clauses are verified simultaneously.

Note that in the process of generation of a clause, two random processes intervene. In the first one, one selects the variables, in the second one, once the variables have been chosen, one determines the requirements that will be imposed on them. We shall later take advantage of this two-step process to perform the average over disorder in a convenient order.

It is clear that if $`MN`$ it will be very easy to find a solution to $`F`$. On the contrary, if $`MN`$, it will be extremely difficult to satisfy all requirements simultaneously. Indeed, a well-defined critical value $`\alpha _c(\text{K})`$ of the parameter $`\alpha M/N`$ appears when $`M\mathrm{}`$ and $`N\mathrm{}`$ with their ratio $`\alpha `$ kept fixed. This limit corresponds to a thermodynamic limit, in the physical language. A threshold phenomenon, reminiscent of a phase transition, is observed: for $`\alpha <\alpha _c(\text{K})`$ all formulæ have at least one solution with probability one, whereas for $`\alpha >\alpha _c(\text{K})`$ any formula has no solution with probability one.

Different values of K lead to different critical behaviors. When K $`=1`$, the model is unsatisfiable for all finite values of $`\alpha `$, i.e. $`\alpha _c(\text{K}=1)=0`$. When K $`=2`$, K-sat has a continuous phase transition at $`\alpha _c(\text{K}=2)=1`$. This is a rigorous result proven by using a mapping on a directed graph problem . For K $`3`$ only numerical estimates for $`\alpha _c(\text{K}3)`$ and approximate results obtained with the replica method are available , these yield $`\alpha _c(\text{K}=3)4.2`$.

The replica method is a powerful tool of statistical mechanics that allows one to compute the statistical properties of a disordered physical problem in equilibrium with a thermal environment. In order to use it to study optimization problems in general, and K-sat in particular, one first maps the optimization problem onto a statistical mechanics model. In the case of K-sat, the physical model is a spin-glass model with dilute interactions of random sign. Indeed, a natural representation of any K-sat formula is obtained by introducing an $`M\times N`$ matrix $`C_{li}`$, whose elements are

$`C_{li}`$ $`=`$ $`\{\begin{array}{ccc}\hfill 0& \text{if}& \hfill \text{neither}x_i\text{nor}\overline{x}_iC_l,\\ \hfill 1& \text{if}& \hfill x_iC_l,\\ \hfill 1& \text{if}& \hfill \overline{x}_iC_l.\end{array}`$ (5)
The random generation of clauses is equivalent to a uniform distribution of the matrices $`C_{li}`$ that satisfy the constraints $`_iC_{li}^2=`$K, $`l`$.

A cost function for K-sat is given by the number of unsatisfied clauses in a given formula. If one identifies the logical state $`x_i=`$ TRUE with a spin $`S_i=1`$ and the logical state $`x_i=`$ FALSE with a spin $`S_i=1`$, it is then easy to verify that the following expression counts the number of unsatisfied clauses

$$E[\{C_{li},x_i\}]=\underset{l=1}{\overset{M}{}}\delta ^{(\text{K})}(\underset{i=1}{\overset{N}{}}C_{li}S_i,\text{K}),$$
(6)
where $`\delta ^{(\text{K})}(a,b)`$ is the Kronecker delta function. Using a polynomial representation of $`\delta ^{(\text{K})}`$ this expression can be rewritten as the total energy of a sum of dilute $`p`$ spin-glass models in a random field (several values of $`p`$ intervene, how many depends on the value of $`K`$.

Once the energy function is identified, one introduces a fictive temperature $`T`$, then computes the average free-energy with the help of the replica trick, and finally takes the limit $`T0`$ to study the ground state properties of the physical model. This gives access to quantities such as, for example, the average entropy of the satisfiable phase. This is defined as the average over disorder of the logarithm of the number of solutions. One of the drawbacks of the use of the replica method is that an Ansatz is necessary to pursue the calculation. Even in the simplest phases, the satisfiable one for K-sat, it is not obvious to show that the simplest Ansatz, called replica symmetric (rs), solves the problem exactly. Moreover, it has been proven that in the unsatisfiable phase one has to go beyond the rs Ansatz and develop a replica symmetry breaking (rsb) scheme. This is indeed a very difficult task since the order parameters for dilute systems have a much more intricate structure than for infinitely connected cases . Recent progress in this direction has been presented in Ref. .

In this paper we re-derive a generic expression for the entropy of K-sat using a very simple method that avoids the use of replicas. Furthermore, the method allows us to compute the finite-size corrections. Our derivation gives information about the domain of validity of Monasson and Zecchina’s conjecture that the rs Ansatz is exact in the satisfiable phase. We explain the expansion using the formalism of K-sat but the line of reasoning can be applied to any dilute system in the dilute regime. In Section 6 we shall analyze the Viana-Bray model  along the same lines.

## 3 The method

Let us start this Section by setting the notation and defining a set of notions that will be used later.

Given a formula $`F`$ of K-sat, two variables $`x_i`$ and $`x_j`$ are called adjacent if there is at least one clause in $`F`$ in which both $`x_i`$ and $`x_j`$ appear, irrespectively of the fact that they are negated or not. Two variables are connected if and only if there is a path of adjacent variables between them. A cluster is a set of connected variables that are disconnected from all others. Let us label with an integer $`r`$ the different clusters of the formula $`F`$, $`r=1,\mathrm{},𝒩_c(F)`$, where $`𝒩_c(F)`$ is the total number of clusters in $`F`$. We shall call $`n_0(F)`$ the number of variables that do not belong to any cluster.

These definitions are very easy to picture. For instance, take a 3-sat problem with ten variables, $`i=1,\mathrm{},10`$, that is defined by the formula $`F=(x_1\overline{x_2}\overline{x_3})(x_3x_4\overline{x_5})(\overline{x_6}\overline{x_7}\overline{x_8})`$. The variables $`i=9`$ and $`i=10`$ do not belong to any cluster, thus $`n_0(F)=2`$. A graphical representation of each clause is very useful. We associate a point to each variable. Each clause is represented by a star with K legs, $`3`$ in the example, with endpoints that represent the variables. In the formula $`F`$ there are two clusters, $`𝒩_c=2`$, that link $`i=1,\mathrm{},5`$ and $`i=6,7,8`$, respectively. When a variable appears in two (or more) clauses it will be shared by two stars. This is the case in the cluster on the left of Fig. 1. More complicated structures are possible, particularly when $`N`$ and $`M`$ are large. The assignment $`x_i`$ ($`\overline{x}_i`$) of the $`i`$th literal in a clause can be represented with a plus (minus) sign on its leg. These are the signs in Fig. 1. In this way, a one-to-one correspondence between formulæ and graphs is constructed.

When $`\alpha `$ is small, the typical cluster size is expected to be small as well, as there are much less clauses than variables. Indeed, for K $`=2`$ this problem is the one of percolation in an infinite dimensional space, also known as the random graph. Many properties of this model are known , among which the fact that for $`\alpha <1/2`$ all variables belong to clusters of size at most proportional to $`\mathrm{ln}N`$, in the thermodynamic limit. When $`\alpha `$ crosses $`1/2`$ a giant cluster containing a finite fraction of the variables grows continuously. For K $`3`$ the equivalent geometrical problem relies on the theory of hyper-graphs, for which less is known. The percolation occurs at $`\alpha =\alpha _p1/(\text{K}(\text{K}1))`$ . In these two cases the system percolates much before it becomes unsatisfiable, $`\alpha _p<\alpha _c`$. Indeed the appearance of a contradiction requires an intricate structure in the giant cluster.

Let us define the ground state entropy of a formula $`S_{\mathrm{gs}}(F)`$ as the logarithm of the number of assignments of the variables that minimize the number of violated clauses. If $`F`$ is satisfiable, $`S_{\mathrm{gs}}(F)`$ is the logarithm of the number of solutions of $`F`$. It is clear from the clusters’ definition that $`S_{\mathrm{gs}}`$ is the sum of contributions of the different independent sub-formulæ:

$$S_{\mathrm{gs}}(F)=n_0(F)\mathrm{ln}2+\underset{r=1}{\overset{𝒩_c(F)}{}}S_{\mathrm{gs}}(F_r).$$
(7)
We are interested in the entropy averaged over the ensemble of formulæ, $`\overline{S_{\mathrm{gs}}}`$. We shall henceforth denote ensemble averages with an over-bar. As stressed in Section 2 this average is twofold. Indeed, clusters can be separated into ensembles with the same topology, ignoring for the moment the sign assignment of the literals. Thus, the averaging proceeds in two steps; one first chooses the topology of the cluster, with its associated probability, and then one averages over the two possibilities for each literal in the cluster. For a given cluster, once the latter average is performed, the entropy depends only on the topology of the cluster. This remark allows us to rewrite the average of the sum in Eq. (7) in a more convenient manner. If we introduce a new integer $`t`$ that labels all possible topologies, and $`n_t(F)`$ and $`S_t`$ the number of $`t`$-like clusters in formula $`F`$ and the average over the sign assignement of the entropy of the $`t`$-like clusters, respectively, we arrive at the following expression for the averaged entropy:

$$\overline{S_{\mathrm{gs}}}=\underset{t}{}[n_t]S_t.$$
(8)
We have here included the isolated variables in the sum, associating them to the index $`t=0`$, $`S_0=\mathrm{ln}2`$ and we denote with $`[n_t]`$ the average number of $`t`$-like clusters.

A more convenient expression for $`[n_t]`$ can now be worked out. Let us call $`X_t^i(F)`$ the function which takes the value $`1`$ if the variable $`i`$ belongs to a $`t`$-like cluster of the formula $`F`$ and $`0`$ otherwise; let $`L_t`$ be the number of variables in such a cluster. Then

$$n_t(F)=\frac{1}{L_t}\underset{i}{}X_t^i(F),$$
(9)
that implies

$$\frac{1}{N}[n_t]=\frac{1}{L_t}[X_t^1]=\frac{P_t}{L_t},$$
(10)
where $`P_t[X_t^1]`$ is the probability that a given variable belong to a $`t`$-like cluster. Finally,

$$\frac{1}{N}\overline{S_{\mathrm{gs}}}=\underset{t}{}\frac{1}{L_t}P_tS_t.$$
(11)
$`P_t`$ and $`S_t`$ can now be obtained using elementary combinatorial arguments and simple enumeration.

This formulation can be adapted to any quantity for which the clusters contribute additively, the free-energy for instance, and to other dilute problems where there is also a decoupling in the randomness between a geometrical part and an interaction one, as in the Viana-Bray model .

## 4 Cluster expansion of the K-SAT entropy

In this Section we shall apply the cluster expansion to the calculation of the average entropy of random K-sat. For our present purposes K$`=1`$-sat is not interesting since it is unsatisfiable for all finite values of $`\alpha `$. We shall then start by analyzing in detail K$`=2`$-sat. Afterwards, we shall discuss how the approach generalizes to larger values of K.

### 4.1 K$`=\mathrm{𝟐}`$-sat in the thermodynamic limit

For a cluster of $`n`$ variables connected by $`p`$ distinct clauses, the probability $`P_t`$ reads

$`P_t`$ $`=`$ $`p!\left(\begin{array}{c}M\\ p\end{array}\right)\left({\displaystyle \frac{2}{N(N1)}}\right)^p\left({\displaystyle \frac{(Nn)(Nn1)}{N(N1)}}\right)^{Mp}`$ (17)
$`\times (n1)!\left(\begin{array}{c}N1\\ n1\end{array}\right)K_t.`$
Let us briefly describe the origin of the factors in this equation. Each of the $`p`$ clauses is chosen with probability $`2/(N(N1))`$ at each of the $`M`$ steps in the formula generation process. For the variables belonging to the cluster to be disconnected from all other sites, the $`Mp`$ other clauses must belong to the set of the $`(Nn)(Nn1)/2`$ clauses connecting the other sites. The first two factors come from the possible permutation of the $`p`$ steps where the considered clauses appear. The last three factors arise from the freedom in the choice of $`n1`$ sites connected to the chosen site. In particular, $`K_t`$ is a symmetry factor that equals the number of distinct labellings of the $`n`$ sites, divided by $`(n1)!`$. Note that two labellings which lead to the same set of clauses are not distinct: for the linear three site cluster $`123`$ and $`321`$ correspond to the same labelling, with clauses $`(12)`$ and $`(23)`$. But $`123`$ and $`213`$ are distinct.

In the thermodynamic limit $`N\mathrm{}`$ and $`\alpha `$ fixed, and for $`n`$ and $`p`$ finite, this expression is proportional to $`N^{n1p}`$ ($`pn1`$). It is then finite only if $`p=n1`$, that is to say for tree-like clusters. This justifies the choice of distinct clauses. In this limit, for $`p=L_t1`$ and $`n=L_t`$, this expression simplifies greatly:

$$P_t=(2\alpha )^{L_t1}e^{2L_t\alpha }K_t.$$
(18)
The different clusters considered in the expansion are represented in Fig. 2. For each type, the relevant quantities, obtained by basic enumeration, are given in Table 1. For instance, the average entropy of the linear three sites cluster is made of two parts: if the clauses require the same sign for the central variable, one can find five solutions of the formula; if the clauses are contradictory for the central variable, there are only four solutions.

Expanding in $`\alpha `$ up to $`O(\alpha ^4)`$ we obtain

$`{\displaystyle \frac{1}{N}}\overline{S_{GS}}=`$
$`\mathrm{ln}2+\alpha \mathrm{ln}\left({\displaystyle \frac{3}{4}}\right)+\alpha ^2\mathrm{ln}\left({\displaystyle \frac{80}{81}}\right)+{\displaystyle \frac{\alpha ^3}{3}}\mathrm{ln}\left({\displaystyle \frac{3^{29}7^6}{5^{15}2^{28}}}\right)+{\displaystyle \frac{\alpha ^4}{12}}\mathrm{ln}\left({\displaystyle \frac{2^{225}5^{160}11^{36}13^{24}17}{3^{216}7^{168}}}\right).`$
(19)
Monasson and Zecchina obtained this series by using the replica trick, with a rs Ansatz, to average the free-energy of the physical model related to 2-sat . The averaged entropy follows from the averaged free-energy density that itself depends on the probability distribution of the local fields. This quantity is determined by an integro-differential equation that cannot be solved analytically. Monasson and Zecchina developed a perturbative solution in $`\alpha `$ that allowed them to derive a series for $`\overline{S}_{\mathrm{sg}}/N`$ that coincides, up to $`O(\alpha ^4)`$, with the one in Eq. (19). The perturbative nature of this result is now clarified from the cluster analysis. Note that we performed two expansions to obtain this series: the cluster enumeration and an expansion in powers of $`\alpha `$ of the exponentials in $`P_t`$. We shall further discuss this issue in Section 5.

### 4.2 Finite size corrections to the entropy of K$`=2`$-sat

There are two kinds of finite size corrections to the expansion presented in Eq. (19). On the one hand, the probability $`P_t`$ of a variable belonging to a tree-like cluster has $`1/N`$ corrections that can be simply computed from the general expression (17). On the other hand, clusters that include loops also contribute to the $`1/N`$ corrections.

The expansion of expression (17) up to order $`1/N`$ for tree-like clusters with $`n=L_t`$ and $`p=L_t1`$ yields

$`P_t`$ $`=`$ $`(2\alpha )^{L_t1}e^{2L_t\alpha }K_t`$
$`\times \left(1+{\displaystyle \frac{1}{N}}\left[2L_t(L_t1)\alpha L_t(L_t+1){\displaystyle \frac{(L_t1)(L_t2)}{2}}\left(1+{\displaystyle \frac{1}{\alpha }}\right)\right]\right).`$
Clusters with $`l`$ loops contribute to the order $`1/N^l`$. Hence, if we only wish to compute the $`1/N`$ corrections we can content ourselves with clusters that have only one loop. These have $`L_t`$ variables and also $`L_t`$ clauses. One obtains

$$P_t=\frac{1}{N}(2\alpha )^{L_t}e^{2L_t\alpha }K_t,$$
(21)
with $`K_t`$ defined as before and multiplied by $`1/2`$ if there is a repeated clause. The one-loop clusters that we considered are represented in Fig. 3.

Including the $`1/N`$ corrections in Eq. (LABEL:nueva) and the ones stemming from the new diagrams in Fig. 3 and Eq. (21) calculated with the results of Table 2, the correction to $`\overline{S_{\mathrm{gs}}}/N`$ reads

$$\frac{1}{N}\left[\alpha \mathrm{ln}\left(\frac{3^4}{2^45}\right)+\frac{\alpha ^2}{4}\mathrm{ln}\left(\frac{2^{107}5^{56}}{3^{107}7^{24}}\right)+\frac{\alpha ^3}{2}\mathrm{ln}\left(\frac{3^{193}7^{156}}{2^{199}5^{141}11^{36}13^{24}17}\right)\right].$$
(22)
This result has to be checked against exhaustive numerical evaluation of the entropy for small systems.

### 4.3 K $`\mathrm{𝟑}`$-sat in the thermodynamic limit

The method described in detail for K $`=2`$ can be used for any value of K. As the graphical representation and the enumeration of clusters are, however, more cumbersome than for K $`=2`$ we shall present less detailed results for the case K $`3`$.

The probability for a given variable to be present in a cluster of $`L_t`$ variables that are linked by $`p`$ clauses is of order $`1`$ in the thermodynamic limit only if $`p(K1)=L_t1`$, which is the tree-like condition for these hyper-graphs. If this holds

$$P_t=(\alpha K!)^pe^{L_t\alpha K}K_t.$$
(23)
In Fig. 4 we have drawn the diagrams leading to the main contributions for K $`=3`$. In the text we give the analytic expression for general K.

With these values we obtain

$`{\displaystyle \frac{1}{N}}\overline{S_{GS}}`$ $`=`$ $`\mathrm{ln}2+\alpha \mathrm{ln}\left(1{\displaystyle \frac{1}{2^K}}\right)`$ (24)
$`+{\displaystyle \frac{\alpha ^2K^2}{2}}\left[\mathrm{ln}\left(1{\displaystyle \frac{1}{2^K}}\right)+{\displaystyle \frac{1}{2}}\mathrm{ln}\left(1{\displaystyle \frac{1}{2^K1}}\right)+{\displaystyle \frac{1}{2}}\mathrm{ln}\left(1{\displaystyle \frac{2^{K1}1}{2^{K1}(2^K1)}}\right)\right].`$
Again we recover the rs result of Ref. . The contributions to the finite size corrections are similar to the ones discussed for 2-sat; we obtain at the leading order in $`\alpha `$:

$$\frac{1}{N}\frac{\alpha K^2}{2}\left[\mathrm{ln}\left(1\frac{1}{2^K}\right)\frac{1}{2}\mathrm{ln}\left(1\frac{1}{2^K1}\right)\frac{1}{2}\mathrm{ln}\left(1\frac{2^{K1}1}{2^{K1}(2^K1)}\right)\right].$$
(25)
We have shown that the perturbative analysis of the rs Ansatz leads to a series in $`\alpha `$ which leading orders coincide with the ones stemming from the finite cluster expansion, for all K. In the next Section we shall discuss the relevance of the contributions from the infinite cluster that appears at the percolation transition $`\alpha _p<\alpha _c`$.

## 5 Discussion

The domain of validity of our expansion, and of the results obtained with the replica method , can be enlighted by studying the percolation phenomenon in detail.

The series expansion in (11) is ordered following the index $`t`$ that is directly related to the size of the clusters. The dependence on $`\alpha `$ is involved since the coefficients $`P_t`$ are $`\alpha `$-dependent via an exponential times a power. The expansion of the exponential factors in powers of $`\alpha `$ leads to a rearrangement of the series in powers of $`\alpha `$.

The range of validity of both series is not obvious. We can start by analysing the simpler series $`_tP_t`$ that should count the total fraction of sites and be identical to $`1`$. For K$`=2`$, its direct summation yields $`1`$ for $`\alpha <\alpha _p`$ and $`1P`$ for $`\alpha >\alpha _p`$, where $`P`$ is the solution to $`1P=e^{2\alpha P}`$ (see Eq. (26) below). Thus, it fails above $`\alpha _p`$ because of the emergence of a giant cluster at the percolation transition. Instead, if one expands the exponentials in powers of $`\alpha `$, the result is $`_tP_t=1+0\times \alpha +0\times \alpha ^2+\mathrm{}`$. The sum yields $`1`$ independently of $`\alpha `$ even beyond the percolation threshold. The rearragement in powers of $`\alpha `$ captures the correct behavior of this quantity.

One can conjecture that the rearrangement yields the exact result for all $`\alpha `$ for all quantities that depend mainly on the locally tree-like structure of the percolating cluster, and only weakly on its loops, which show up only on a scale of order $`\mathrm{ln}N`$. As can be seen in Eq. (9), the exponentials in $`P_t`$ arise from the requirement that the considered cluster is disconnected from the rest of the sites. Expanding the exponentials amounts basically to assuming that a sub-tree of the giant cluster gives the same contribution as its disconnected counterpart. The alternative signs arise from the need to avoid the double counting of the smaller clusters contained in the giant cluster.

As regards to the calculation of the averaged entropy, if one could compute all the terms in (11) and sum the series, the result would be exact under the percolation threshold, $`\alpha _p=1/(K(K1))`$. Indeed all sites belong to clusters of size at most proportional to $`\mathrm{ln}N`$ in this regime. As soon as $`\alpha `$ goes beyond $`\alpha _p`$, the direct summation of (11) should fail.

In spite of the discussion of the next to last paragraph, we do not expect that reordering the series in powers of $`\alpha `$ gives the correct result for the entropy. Our argument is based on the drastic influence of loops on this quantity. Let us compare the entropy of a loop and of a linear cluster of the same size, for $`2`$-sat. There are roughly twice as many solutions for the linear cluster as for the loop, as one does not require the ending variables to be the same. The difference of entropy between the two should then be finite. As there are an extensive number of loops in the percolating cluster, one can expect a finite deviation in the average entropy per site between the result assuming a tree-like structure of the giant cluster (i.e. the expansion in alpha of the original series) and the correct one.

We have examined these issues with the help of numerical simulations of systems with small sizes.

Firstly, we compare the averaged total entropy per degree of freedom, $`\overline{S}/N`$, to the value predicted by the series expansion once reordered in powers of $`\alpha `$. In Fig. 5 we plot $`\overline{S}/N`$ against $`1/N`$ with linespoints $`+`$ for K=2-sat problems with $`N=16(50000),20(50000)`$, $`24(50000)`$, $`28(10000)`$, $`32(15000)`$, $`36(10000)`$ and $`\alpha _p<\alpha =0.75<\alpha _c`$. For each sample we computed the entropy by exhaustive enumeration. The numbers between parenthesis are the number of realizations of random instances of K-sat used to compute the averages. The accord with the analytical prediction of the truncated series expansion in the thermodynamic limit (horizontal line below) and including $`1/N`$ corrections (tilted line above) is very good within $`0.3\%`$. We have also computed the variance, $`1/N(\overline{S^2}\overline{S}^2)`$, and checked that it is in good accord with the analytical result, $`0.025\alpha ^2`$, that we obtained with an extension of the cluster expansion described in previous sections.

Even if the accord between numerical results and theory is almost perfect for these small sizes, a more careful inspection of the different contributions to the total entropy shows that one could expect important deviations for increasing $`N`$. We have computed separately the contribution of the largest cluster. Figure 7 represents its study. We here plot, with crosses, the averaged entropy of the largest cluster, per degree of freedom, $`\overline{S_{\mathrm{max}}}/N`$. Its contribution, even for these small sizes, represents roughly a half of the total entropy (note that below the percolation threshold the contribution of the largest cluster is much smaller) and that does not seem to vanish in the thermodynamic limit. A simple linear fit of $`\overline{S_{\mathrm{max}}}/N`$ yields, when $`N\mathrm{}`$, the finite limit $`0.1906\pm 0.0008`$. This may be taken as a guess for a lower limit for the contribution of the largest cluster.

In the same figure we compare the averaged entropy of the largest cluster $`\overline{S_{\mathrm{max}}}/N`$ to the “factorized” quantity $`\overline{L_{\mathrm{max}}}/N\overline{S_{\mathrm{max}}/L_{\mathrm{max}}}`$, where $`L_{\mathrm{max}}`$ is the number of variables in the largest cluster, that is represented with squares. For finite sizes we have shown that these two quantities coincide. The good accord between the two curves suggests that the factorization also holds when $`N\mathrm{}`$.

This observation suggests an improvement of the finite-size numerical study. If we assume that the factorization holds in the limit $`N\mathrm{}`$ for the percolating cluster, we can then replace the fraction of sites that belong to the largest cluster, $`P_{\mathrm{max}}\overline{L_{\mathrm{max}}}/N`$, by its analytical value in the thermodynamic limit. This is given by

$$1P_{\mathrm{max}}=\mathrm{exp}\left(\alpha K\left((1P_{\mathrm{max}})^{K1}1\right)\right).$$
(26)
This result is obtained using a self-consistent equation on the generating function that counts the number of sites in finite size clusters . For $`K=2`$ and $`\alpha =0.75`$, $`P_{\mathrm{max}}0.5828`$. Figure 7 displays $`P_{\mathrm{max}}`$ as a function of $`\alpha `$ for $`K=2`$ and different system sizes, $`N=25`$,$`100`$,$`1000`$,$`10000`$. One sees that the percolation transition is reached only for a too large size, $`N10000`$ that is far beyond the largest sample for which one can compute the entropy by exhaustive enumeration. Moreover, it is important to notice that the approach to the asymptotic value is nonmonotonic since, for these values of $`N`$ the approach to the asympote comes from below while one can easily prove that $`P_{\mathrm{max}}(N=4,\alpha =0.75)0.75`$.

Finally, the third curve in Fig. 7 (stars) represents the “improved” contribution of the largest cluster, $`0.5828\overline{S_{\mathrm{max}}/L_{\mathrm{max}}}`$. For $`N>20`$ the improved curve is still higher than the actual one and a linear fit yields the limiting value $`lim_N\mathrm{}\overline{S_{\mathrm{max}}}/N0.2143\pm 0.0003`$.

This numerical analysis, even if based on simulations of very small systems and highly speculative, suggests that the contribution of the percolating cluster is finite in the thermodyamic limit. On the analytical side, it might be possible to compute the entropy of the percolating cluster, at least for 2-sat, by taking profit of the numerous mathematical results on the structure of random graphs . Such a study is necessary to settle the problem.

This picture could also explain the discrepancy between numerical studies and a rigorous bound for the value of the exponent governing the size of the scaling window of the satisfiability transition . For the relatively small system sizes first studied, the observed exponent may have been altered by percolation, as its asymptotic regime was not reached yet . At larger sizes, and in mathematical studies, the exponent is purely due to the satisfiability threshold inside the giant cluster; one might observe the true exponent for lower system sizes by studying the probability of the largest cluster to be satisfiable.

Let us summarize briefly the route followed in studies based on the replica trick to attempt to identify the effect of the percolation transition within this calculation . In the rs Ansatz, an intricate integral equation over the probability of local fields, $`P(h)`$, that is the order parameter of the system, is obtained. From $`P(h)`$ all thermodynamic quantities follow, including the entropy of the satisfiable phase. As the analytical resolution of the equation that determines $`P(h)`$ seems out of reach, it has been solved order by order in $`\alpha `$. This yields an $`\alpha `$ expansion for the entropy which is in exact coincidence with ours up to $`O(\alpha ^4)`$ for $`K=2`$ and up to $`O(\alpha ^2)`$ for $`K3`$. It seems natural to assume that the two expansions coincide to all orders. The rs Ansatz is thus proven to be exact for all $`\alpha `$ such that $`\alpha <\alpha _p=1/(K(K1))`$. Beyond this value if, as we discussed above, the influence of the loops on the entropy of the percolating cluster is not negligible, two possibilities arise: either the rs Ansatz is wrong, or a more refined handling of the integral equation on $`P(h)`$ is required . A careful analysis of this problem is worthwhile. One could, for instance, investigate the presence of a singularity at the percolation threshold. In any case, the fact that the entropy of the satisfiable phase remains finite up to the satisfiability transition is confirmed: at the threshold a finite, even if small ($`0.2`$ for $`K=2`$), fraction of sites are in finite size clusters, and their contribution provides a lower bound for the entropy of the system.

## 6 Dilute spin glasses: an exact solution for the paramagnetic phase of the Viana Bray model

Spin glasses are magnetic systems where the interactions between degrees of freedom (spins) are disordered. The key quantity that determines all the statistical properties of such systems is the free energy averaged over the distribution of the interactions. In most cases this average can only be computed with the replica trick , often involving the technically subtle replica symmetry breaking (rsb). For infinitely connected models, in which each spin interacts with all others in the sample, like the Sherrington-Kirkpatrick model , the rsb scheme that yields the exact solution in both high and low-temperature phases is well understood. The final aim, far from being reached, is to determine the nature of the spin-glass phase of disordered models on a $`d`$-dimensional lattice with only short range interactions. Dilute spin glasses can be viewed as an intermediate step between these two limits: each spin interacts with a finite number of other spins but the model includes no notion of distance since the “neighbors” are randomly chosen from the whole set of spins of the system.

The standard dilute spin-glass model has been introduced by Viana and Bray . It is defined by the following Hamiltonian involving $`N`$ classical Ising spins, $`S_i=\pm 1`$,

$$H=\underset{ij}{}J_{ij}S_iS_j.$$
(27)
The interactions $`J_{ij}`$ are independently distributed with the same probability law:

$$P(J_{ij})=\left(1\frac{c}{N}\right)\delta (J_{ij})+\frac{c}{N}\rho (J_{ij}).$$
(28)
$`\rho `$ is normalized to one, and has average and mean square deviation of order one to obtain a sensible thermodynamic limit. $`c`$ is the mean connectivity per spin.

Despite numerous studies , a complete understanding of this model has not been reached yet. The main difficulty in the study of dilute models is that even without rsb, the order parameter is a function instead of a number as in the ic case. In order to introduce rsb one has to cope with an order parameter which is at least a functional, leading to very difficult calculations.

The mean connectivity per spin $`c`$ plays here the same role as $`\alpha `$ in our expansion of the 2-sat entropy. As opposed to K-sat, for the Viana-Bray model the percolation and the paramagnetic (pm) to spin-glass transition occur at the same critical value $`c=1`$. In the dilute phase, $`c<1`$, the clusters have not percolated and the model is in the pm phase . The statistical properties in this phase can be studied with the cluster expansion. The average free-energy per site reads

$$\beta f=\underset{t}{}\frac{1}{L_t}c^{L_t1}e^{L_tc}K_t\overline{\mathrm{ln}Z_t},$$
(29)
where the over-line denotes an average with respect to $`\rho `$ and only tree clusters contribute in the thermodynamic limit. This is the analog of Eq. (11) with a slightly different expression for $`P_t`$ where $`2\alpha `$ is replaced by $`c`$. $`Z_t`$ is the partition function of the cluster. One can easily prove that for trees,

$$\overline{\mathrm{ln}Z_t}=L_t\mathrm{ln}2+(L_t1)\overline{\mathrm{ln}\mathrm{cosh}\beta J},$$
(30)
irrespectively of the topology. Then the sum of symmetry factors for all trees of $`L_t`$ sites is $`L_t^{L_t2}/(L_t1)!`$ (a well-known result from graph theory ), and results in

$$\beta f=\mathrm{ln}2\left(\underset{k=1}{\overset{\mathrm{}}{}}\frac{(e^c)^k}{k!}(ck)^{k1}\right)+\overline{\mathrm{ln}\mathrm{cosh}\beta J}\left(c\underset{k=1}{\overset{\mathrm{}}{}}\frac{(e^c)^k}{k!}(k1)(ck)^{k2}\right).$$
(31)
The two sums can be evaluated (cf Appendix) to yield

$$\beta f=\mathrm{ln}2+\frac{c}{2}\overline{\mathrm{ln}\mathrm{cosh}\beta J}.$$
(32)
This result has a simple interpretation: from Eq. (30), each site contributes with $`\mathrm{ln}2`$ to the free energy, each link with $`\overline{\mathrm{ln}\mathrm{cosh}\beta J}`$ for tree-like sructures. As there are $`N`$ sites and $`cN/2`$ links on average, the result follows. One obtains exactly the same free energy following the replica method with a rs Ansatz. The exactness of the rs Ansatz in this phase is then proven.

The cluster expansion allows to compute finite size corrections in a rather simple manner. These read, upto $`O(c^3/N)`$,

$`{\displaystyle \frac{1}{N}}\left[{\displaystyle \frac{c}{2}}\overline{\mathrm{ln}\mathrm{cosh}\beta J}+c^3\left({\displaystyle \frac{4}{3}}\mathrm{ln}2+\overline{\mathrm{ln}\mathrm{cosh}\beta J}+{\displaystyle \frac{1}{6}}\overline{\mathrm{ln}(1+\mathrm{tanh}\beta J_1\mathrm{tanh}\beta J_2\mathrm{tanh}\beta J_3)}\right)\right]`$
where $`J_1`$, $`J_2`$ and $`J_3`$ are three independent couplings taken from the probability distribution $`\rho (J_{ij})`$. It will be very interesting to confront this result with the finite size corrections to the replica calculation using the rs Ansatz.

As in the K-sat problem, the expansion cannot be used beyond $`c=1`$, since it does not take into account the giant cluster appearing at the percolation transition.

## 7 Conclusions and perspectives

The cluster expansion relies on very simple combinatorial arguments. It allows one to solve optimization problems in the “easy” phase avoiding the introduction of replicas and it is a general method to obtain finite $`N`$ corrections. Most importantly, it has allowed us to signal the possible need for a revision of the replica solution of the K-sat, and similar problems, with two successive percolation and easy-to-hard transition.

For spin-glasses without a difference in these two transitions the interest of the method is less apparent, as highly diluted systems are in the less interesting pm phase. Still, it would be interesting to test if the rs Ansatz is exact for any spin-glass model under its percolation threshold, as was proven here for the Viana-Bray spin-glass in the thermodynamic limit.

Let us note, however, the difference in the percolating and critical behavior of K-sat and the Viana-Bray dilute spin-glass. In the former, percolation occurs before the satisfiability transition ($`\alpha _p<\alpha _c`$); in the latter both phenomena arise at the same value of the control parameter ($`c=1`$). This can be understood as being due to the fact that 2-sat is, in a way, less frustrated than VB. Two manifestations of this fact are given by the behavior of a single loop and a linear cluster. A single loop in 2-sat is always satisfiable while in VB it is frustrated each time there is an odd number of antiferromagnetic couplings on it. A linear cluster in 2-sat can be satisfied by a large number of configurations while in VB only two spin configurations satisfy all bonds.

The cluster expansion can be applied to a variety of interesting problems. For instance, algorithms that solve satisfiability problems through local search, like walk-sat , can also be studied with this method . The number of steps needed to solve a formula is the sum of the number of steps needed to solve each cluster. Improvements of the algorithms by means of better heuristics can thus be quantified .

Acknowledgements

Very useful discussions with S. Mertens, R. Monasson and M. Weigt are gratefully acknowledged. GS warmly thanks D. S. Sherrington for introducing him to the subject of disordered systems and optimization problems during a long visit to Oxford. We acknowledge financial support from the ACI “Algorithmes d’optimisation et systèmes désordonnés quantiques”.

Appendix

In this appendix we shall derive a proof of the two summations used in eq. (31):

$`A`$ $`=`$ $`{\displaystyle \underset{k=1}{\overset{\mathrm{}}{}}}{\displaystyle \frac{(e^c)^k}{k!}}(ck)^{k1}=1,`$ (33)
$`B`$ $`=`$ $`{\displaystyle \underset{k=1}{\overset{\mathrm{}}{}}}{\displaystyle \frac{(e^c)^k}{k!}}(k1)(ck)^{k2}={\displaystyle \frac{1}{2}}.`$ (34)
The proof relies on a mathematical identity proven with the help of analytical function tools . Let $`w(z)`$ be a given function which can be inverted to $`z(w)`$. Then the coefficients of the serie expansion of $`z(w)`$ are obtained via the following expression:

$`z(w)`$ $`=`$ $`{\displaystyle \underset{k=1}{\overset{\mathrm{}}{}}}{\displaystyle \frac{1}{k!}}b_kw^k,`$ (35)
$`b_k`$ $`=`$ $`{\displaystyle \frac{d^{k1}}{dt^{k1}}}\left[\left({\displaystyle \frac{t}{w(t)}}\right)^k\right]_{t=0}.`$ (36)
Let us consider the function $`w(z)=z\mathrm{exp}(cz)`$, which is a bijection from $`[0,1]`$ to $`[0,e^c]`$ if $`c<1`$. The coefficients of the series expansion of the reciprocal $`z(w)`$ are

$$b_k=\frac{d^{k1}}{dt^{k1}}\left[\left(\frac{t}{te^{ct}}\right)^k\right]_{t=0}=(kc)^{k1}.$$
(37)
Thus, $`A=z(e^c)=1`$, as $`w(1)=e^c`$.

The second series can be transformed using $`A=1`$ :

$$B=\frac{1e^c}{c}\underset{k=2}{\overset{\mathrm{}}{}}\frac{(e^c)^k}{k!}(ck)^{k2}.$$
(38)
If we define

$$g(w)\underset{k=2}{\overset{\mathrm{}}{}}\frac{w^k}{k!}(ck)^{k2},$$
(39)
then $`B=(1e^c)/cg(e^c)`$. To compute $`g(w)`$, we note that $`g(0)=0`$ and $`g^{}(w)=z(w)/(cw)1/c`$. By integration and with the change of variables $`z=z(w)`$, one obtains

$$g(e^c)=\frac{e^c}{c}+\frac{1}{c}_0^1𝑑zw^{}(z)\frac{z}{w(z)}=\frac{1e^c}{c}\frac{1}{2}.$$
(40)
This yields the final result $`B=1/2`$.


format: text

text:
# Superfluid neutron stars

## 1 Superfluid relativistic hydrodynamics

Neutrons stars are believed to contain in their interior superfluid neutrons and superconducting protons. This is suggested by nuclear physics calculations and by the very long relaxation time scales after ‘glitches’ (sudden increases of the neutron star angular velocity). Over the last years, we have been developing a formalism that can describe the relativistic hydrodynamics of mixtures of superfluid or superconductors and possibly ordinary fluids .

The hydrodynamics of several species labelled by the index X, with respective particle currents $`n__\mathrm{X}^\rho `$ and respective electric charge per particle $`e^_\mathrm{X}`$, can be described by the Lagrangian

$$=\mathrm{\Lambda }_\mathrm{M}+\underset{\mathrm{X}}{}e^_\mathrm{X}n__\mathrm{X}^\rho A_\rho +\frac{1}{16\pi }F_{\rho \sigma }F^{\sigma \rho },$$
(1)
where $`A_\rho `$ is the electromagnetic gauge form and $`F_{\rho \sigma }`$ the corresponding electromagnetic tensor, and where $`\mathrm{\Lambda }_\mathrm{M}`$ is the ‘hydrodynamical’ part of the Lagrangian, depending only on the particle currents $`n__\mathrm{X}^\rho `$, the variations of which define the momentum covectors: $`\delta \mathrm{\Lambda }_\mathrm{M}=\mu _\rho ^_\mathrm{X}\delta n__\mathrm{X}^\rho `$. This variational principle, corresponding to perfectly conducting fluids, leads to matter conservation equations, one for each species, $`_\rho n__\mathrm{X}^\rho =0`$ (one can generalize to allow for chemical reactions between various species ), and to Euler-type equations of motion, which can be written in the very compact form

$$n__\mathrm{X}^\sigma _{[\rho }\pi _{\sigma ]}^_\mathrm{X}=0,\mathrm{with}\pi _\rho ^_\mathrm{X}\mu _\rho ^_\mathrm{X}+e^_\mathrm{X}A_\rho $$
(2)
In order to deal with superfluids or superconductors, one must impose the further condition that the momentum covectors $`\pi _\rho ^_\mathrm{X}`$ are gradients. This is in fact true on small scales only, because on larger scales the superfluid or the superconductor will be threaded in general by arrays of vortices, due to a global angular momentum (for superfluids) or an external magnetic field (for superconductors). The macroscopic description, which takes into account the average effect of the vortices, can be done by considering the (generalized) vorticity tensors $`w_{\rho \sigma }^_\mathrm{X}2_{[\rho }\pi _{\sigma ]}^_\mathrm{X}`$, now non-zero since there are vorticies, as fundamental quantities .

## 2 Oscillations of superfluid neutron stars

In a neutron star, the existence of a superfluid component, weakly connected to the normal component, leads to a richer spectrum of oscillations. In general relativity, one must take into account not only the matter perturbations but also the perturbations of the metric $`g_{\mu \nu }`$. In a specific gauge, the even-parity modes can be written (the study of the $`m=0`$ modes is enough because of the degeneracy in $`m`$) in the form

$`\delta g_{00}=e^\nu r^lH_0e^{i\omega t}P_l(\theta ),`$ $`\delta g_{0r}=\delta g_{r0}=i\omega r^{l+1}H_1e^{i\omega t}P_l(\theta ),`$ (3)
$`\delta g_{rr}=e^\lambda r^lH_2e^{i\omega t}P_l(\theta ),`$ $`\delta g_{\theta \theta }=\delta g_{\varphi \varphi }/\mathrm{sin}^2\theta =r^{l+2}Ke^{i\omega t}P_l(\theta ),`$ (4)
where $`P_l`$ stands for the Legendre polynomial of order $`l`$. In a two-component model, the matter perturbations can be described by the two matter displacements $`\xi _n`$ and $`\xi _p`$,

$`\xi _n^r=`$ $`r^{l1}e^{\lambda /2}W_ne^{i\omega t}P_l(\theta ),\xi _n^\theta =`$ $`r^{l2}V_ne^{i\omega t}_\theta P_l(\theta ),`$ (5)
$`\xi _p^r=`$ $`r^{l1}e^{\lambda /2}W_pe^{i\omega t}P_l(\theta ),\xi _p^\theta =`$ $`r^{l2}V_pe^{i\omega t}_\theta P_l(\theta ).`$ (6)
Inserting the above expressions for the perturbations into the perturbed Einstein’s equations as well as the perturbed Euler equations, one ends up with a system of linear equations, consisting of two contraints (one is $`H_2=H_0`$, the other expresses $`H_0`$ in terms of the other perturbations) and of first order differential equations of the form

$$\frac{dY}{dr}=Q_{l,\omega }Y,$$
(7)
where $`Y`$ is 6-dimensional column vector containing $`H_1`$, $`K`$, $`W_n`$, $`V_n`$, $`W_p`$ and $`V_p`$, and $`Q_{l,\omega }`$ is a $`6\times 6`$ matrix with $`r`$-dependent coefficients that depend only on the background configuration, as well as on $`l`$ and $`\omega `$. Considering the boundary conditions at the center and at the surface of the star, this system can be solved, up to a global amplitude, for any value of $`\omega `$. The physically relevant modes, however, also called quasi-normal modes, correspond the specific values of $`\omega `$ for which the metric outside the star represents only outgoing gravitational waves.

A numerical investigation for a very crude model of two independent polytropes (with different adiabatic indices) has shown that the two-component star will exhibit new modes, superfluid modes, which are specific of the existence of two components since the two fluids are counter-moving for these modes .


text:
# GRB 000418: A Hidden Jet Revealed?

## 1 Introduction

GRB 000418 was detected on April 18, 2000, at 09:53:10 UT by the Ulysses, KONUS-Wind and NEAR spacecraft, which are part of the third interplanetary network (IPN) . The event lasted $``$30 s, and a re-analysis of the early Ulysses data (Hurley, Cline & Mazets (2000)) gives a fluence of $`4.7\times 10^6`$ erg cm-2 in the 25-100 keV band. A fit to the total photon spectrum from the KONUS data $`2\times 10^5`$ erg cm-2 in the energy range 15 - 1000 keV. Intersecting IPN annuli resulted in a 35 arcmin2 error box, in which Klose et al. (2000b) identified a variable near-infrared (NIR) source. The early R-band light curve of this source was described by Mirabal et al. (2000) as having a power-law decay $`t^{0.84}`$, typical for optical afterglows. The redshift for the host galaxy of $`z1.119`$ was measured by Bloom et al. (2000) from an \[OII\] emission line doublet. Assuming cosmological parameters of $`\mathrm{\Omega }_M`$=0.3, $`\mathrm{\Lambda }_0`$=0.7 and H0=65 km s-1 Mpc-1, this redshift corresponds to a luminosity distance d$`{}_{\mathrm{L}}{}^{}=2.5\times 10^{28}`$ cm and gives an implied isotropic $`\gamma `$-ray energy release of E$`{}_{\gamma }{}^{}=1.7\times 10^{52}`$ erg.

Klose et al. (2000b) have recently summarized optical/NIR data observations of GRB 000418. In this paper we present additional optical/NIR data and a complete set of radio observations between 1.4 GHz and 22 GHz, from 10 to 200 days after the burst. We use this broad band data set to fit several models, deriving the physical parameters of the system.

## 2 Observations

### 2.1 Optical Observations

In Table 1 we present deep optical photometry obtained at Palomar, Keck111The W. M. Keck Observatory is operated by the California Association for Research in Astronomy, a scientific partnership among California Institute of Technology, the University of California and the National Aeronautics and Space Administration., and MDM observatories covering six weeks following the GRB as well as data from the extant literature.

All of the optical data was overscan corrected, flat-fielded, and combined in the usual manner using IRAF (Tody (1993)). PSF-fitting photometry was performed relative to several local comparison stars measured by Henden (2000) using DoPhot (Schechter, Mateo & Saha (1993)). Short exposures of the field in each band were used to transfer the photometry (Henden (2000)) to several fainter stars in the field. Several of the Keck+ESI measurements, and the Palomar 200” measurement were made in Gunn-r and Gunn-i respectively and were calibrated by transforming the local comparison stars to the Gunn system using standard transformations (Wade et al. (1979), Jorgensen (1994)). We add an additional 5% uncertainty in quadrature with the statistical uncertainties to reflected the inherent imprecision in these transformations.

The Ks-band image of the field was obtained on the Keck I Telescope on Manua Kea, Hawaii with the Near Infrared Camera. We obtained a total of 63 one-minute exposures which we reduced and combined with the IRAF/DIMSUM package modified by D. Kaplan. There was significant cloud and cirrus cover and so the night was not photometric.

The HST STIS/Clear image was obtained on 4 June 2000 UT as part of the TOO program # 8189 (P.I. A. Fruchter) and made public on 2 September 2000 UT. Five images of 500 s each were obtained which we combined using the IRAF/DITHER task. The final plate scale is 25 milliarcsec pixel-1.

We corrected all optical measurements in Table 1 for a Galactic foreground reddening of $`E(BV)=0.032`$ (Schlegel, Finkbeiner & Davis (1998)) at the position of the burst $`(l,b)=(261.16,80.78)`$ before converting to flux units (Fukugita, Shimasaku & Ichikawa (1995), Bessell & Brett (1988)) assuming RV=3.1.

### 2.2 Radio Observations

Radio observations were undertaken at a frequency of 15 GHz with the Ryle Telescope. All other frequencies were observed with either the NRAO222The NRAO is a facility of the National Science Foundation operated under cooperative agreement by Associated Universities, Inc. NRAO operates the VLA and the VLBA Very Large Array (VLA) or the Very Long Baseline Array (VLBA). A log of these observations can be found in Table 2. The data acquisition and calibration for the Ryle and the VLA were straightforward (see Frail et al. 2000a  for details).

The single VLBA observation was carried out at 8.35 GHz with a total bandwidth of 64 MHz in a single polarization using 2 bit sampling for additional sensitivity. The nearby ($`<`$1.3) calibrator J1224+2122 was observed every 3 minutes for delay, rate and phase calibration. Amplitude calibration was obtained by measurements of the system temperature in the standard way. The coordinates for GRB 000418 derived from the VLBA detection are (epoch J2000) $`\alpha `$ = $`12^h25^m19.2840^s`$ ($`\pm 0.015^s`$) $`\delta `$ = $`+20^{}06^{}11.141^{\prime \prime }`$ ($`\pm 0.001^{\prime \prime }`$).

## 3 The Optical Light Curve and Host Galaxy

In Figure 1 we display the R and K-band light curves constructed from measurements in Table 1. The pronounced flattening of the R-band light curve at late times is reasonably attributed to the optical afterglow fading below the brightness of the underlying host galaxy. A noise-weighted least squares fit was made to the data of the form $`f_R=f_ot_o^\alpha `$ \+ $`f_{host}`$ for which we derive $`f_o=23.4\pm 2.1`$ $`\mu `$Jy, $`\alpha _o=1.41\pm 0.08`$ and $`f_{host}=1.08\pm 0.06`$ $`\mu `$Jy with a reduced $`\chi _r^2=0.94`$. Our inferred R-band magnitude for the host galaxy R$`{}_{host}{}^{}=23.66\pm 0.06`$ is nearly identical to that obtained from a similar analysis by Klose et al. (2000b). In order to estimate the effect of the host in other optical bands we scaled Rhost for GRB 000418 to a spectrum of the host galaxy of GRB 980703 (Bloom et al. (1998)) ($`z=0.966`$) whose magnitude was measured in seven broad-band colors (B, V, R, I, J, H, and K). Our results indicate that 50-100% of the flux in some bands is due to the host galaxy after the first 10 days. Therefore, for the afterglow modeling in §5 we chose not to include the late-time measurements of GRB 000418 in the B, V, and Gunn-i bands.

## 4 The Radio Light Curves

In Figure 1 we display the radio light curves at 4.86, 8.46, 15 and 22 GHz. To first order all four frequencies show a maximum near 1 mJy on a time scale of 10 to 20 days. There is no discernible rising trend at any frequency. This is most clear at 8.46 GHz, where beginning 10 days after the burst, the light curve undergoes a steady decline, fading from 1 mJy to 0.1 mJy over a six month period. The temporal slope of the 8.46 GHz light curve after the first two months $`\alpha _{\mathrm{rad}}=1.37\pm 0.10`$ ($`\chi _r^2=1.4`$) is similar to the optical R-band curve $`\alpha _{\mathrm{opt}}=1.41\pm 0.08`$.

Superimposed on this secular decrease, there exist point-to-point variability of order 50%, especially in the early measurements. We attribute these variations to interstellar scintillation (ISS) (Goodman (1997), Walker (1998)). The method by which we estimate the magnitude of the intensity fluctuations induced by ISS as a function of frequency and time is described in full by Berger et al. (2000). Briefly, we estimate the magnitude of scattering with the model of Taylor & Cordes (1993), and use this to calculate the transition frequency $`\nu _0`$ between weak and strong scattering using Walker (1997). The normalizations used in Goodman (1997) give slightly larger values of $`\nu _0`$.

In the direction toward GRB 000418 we derive $`\nu _03.6`$ GHz and therefore most of our measurements were taken in the weak ISS regime. In this case the modulation scales as $`\nu ^{17/12}`$, with a maximum of 65% expected at 4.86 GHz and 30% at 8.46 GHz. At 15 GHz and 22 GHz we estimate that the ISS-induced fluctuations are only a fraction of the instrumental noise. The expansion of the fireball will eventually quench ISS when the angular size of the fireball exceeds the angular size of the first Fresnel zone at the distance of the scattering screen. The fireball size, and hence the quenching timescale, is model-dependent, and we use the derived total energy and density from the global fits (see §5 below) to estimate this time for each model. For example, in a simple spherical fireball this occurs after 15 days at 4.86 GHz and 10 days at 8.46 GHz, and thereafter the modulation indices decline as $`t^{35/48}`$. We note that the observed fluctuations at 4.86 and 8.46 GHz conform to the predicted level of ISS, but that the measurements at 8.46 GHz from around 50 days after the burst deviate by a factor of three from the predicted ISS level.

In addition, we use the scintillation pattern to estimate the true $`\chi _r^2`$ for each model, by adding in quadrature to the instrumental noise an additional ISS-induced uncertainty, $`\sigma _{\mathrm{ISS}}=m_pF_{\nu ,\mathrm{model}}`$, where $`m_p`$ and $`F_{\nu ,\mathrm{model}}`$ are the modulation index and model flux density at frequency $`\nu `$, respectively (Berger et al. 2000).

## 5 Global Model Fits

The optical and radio data presented here have allowed us to track the evolution of the GRB 000418 afterglow from 2 to 200 days after the burst. With careful modeling of the light curves, it should be possible to infer the physical parameters of the blast wave and thereby gain some insight into the nature of GRB progenitors. In particular, the hydrodynamic evolution of the shock is governed by the energy of the explosion, the geometry of the expanding ejecta shock and the type of environment into which the GRB explodes (Sari, Piran & Narayan (1998), Wijers & Galama (1999), Chevalier & Li (1999), Panaitescu & Kumar 2000a ). We will consider three basic models: a spherical explosion in a constant density medium, collimated ejecta (i.e., jets) interacting with a constant density medium, and a spherical explosion in a wind-blown medium.

The starting point for any afterglow interpretation is the cosmological fireball model (e.g. Mészáros & Rees (1997), Waxman (1997)). A point explosion of energy E0 expands relativistically into the surrounding medium (with density $`\rho r^s`$, where $`s=0`$ for constant density ISM and $`s=2`$ for a wind) and the shock produced as a result of this interaction is a site for particle acceleration. The distribution of electrons is assumed to be a power-law of index $`p`$, and the fraction of the shock energy available for the electrons and the magnetic field is $`ϵ_e`$ and $`ϵ_B`$, respectively. The values of these three quantities ($`p`$, $`ϵ_e`$ and $`ϵ_B`$) are determined by the physics of the shock and the process of particle acceleration and in the absence of detailed understanding are taken to be constant with time.

The instantaneous broad-band synchrotron spectrum can be uniquely specified by the three characteristic frequencies $`\nu _a`$, $`\nu _m`$, and $`\nu _c`$ (i.e., synchrotron self-absorption, synchrotron peak, and cooling), the peak flux density $`f_m`$, and $`p`$. For this work we adopt the smooth spectral shape as given by Granot et al. (1999a, 1999b) rather than the piecewise, broken power-law spectrum used by other authors (e.g., Wijers & Galama (1999)). The evolution of the spectrum (and thus the time dependence of $`\nu _a`$, $`\nu _m`$, $`\nu _c`$ and $`f_m`$) is governed by the geometry of the explosion (spherical or a collimated into a jet-like outflow), and the properties of the external environment (constant density or a radial density profile). Our approach is to adopt a model (sphere, wind, jet, etc.) and solve for the above spectral parameters using the entire optical and radio data set. The advantages and details of global model fitting are discussed by Berger et al. (2000).

The simplest model is a spherically symmetric explosion in a constant density medium (ISM: Sari et al. 1998). The total $`\chi _r^2`$ for this model (see Table 3) gives a highly unsatisfactory fit to the data. On close inspection (Figure 1) we find that the model systematically underpredicts the optical flux. Adding extinction from the host galaxy only makes this worse. The fundamental difficulty with the ISM model is that it predicts $`f_m=constant`$, independent of frequency. In this case, since it is the radio data that is responsible for defining the peak of spectrum, it results in a value of $`f_m`$ that is too low at higher frequencies.

To obtain better fits to the joint optical and radio data sets we look to models for which $`f_m`$ is time-dependent. One such model is a collimated outflow into a medium with uniform density (Jet: Rhoads (1997), Rhoads (1999), Sari, Piran & Halpern (1999)). The clearest observational signature of the Jet model is an achromatic break in the light curves at $`t_j`$ (e.g., Harrison et al. (1999)). At radio wavelengths (i.e., below $`\nu _m`$) at $`t_j`$ we expect a transition from a rising $`t^{1/2}`$ light curve to a shallow decay of $`t^{1/3}`$, while at optical wavelengths the decay is expected to steepen to $`t^p`$. These decay indices refer to the asymptotic values.

Detecting a jet transition at optical wavelengths may be difficult if it occurs on timescales of a week or more. In these cases the afterglow is weak and the light from the host galaxy may start to dominate the light curve (e.g., Halpern et al. 2000). In such instances radio observations may be required to clarify matters, since the radio flux is increasing prior to $`t_j`$ and changes in the lightcurve evolution due to the jet break are easily detected. Indeed, the jet in GRB 970508, which was very well observed in the radio is not discernible in the optical data. In this case, Frail, Waxman & Kulkarni (2000) found a wide-angle jet with an opening angle of 30 and $`t_j30`$ days (but see Chevalier & Li (2000)).

A Jet model with $`t_j26`$ days fits the data remarkably well (see Figure 1). The strongest point in favor of the Jet model is that it reproduces the broad maximum ($``$1 mJy) seen from 5 GHz to 22 GHz. We expect such a plateau at $`t_j`$ as all light curves for $`\nu _a<\nu \nu _m`$ reach their peak fluxes (with only a weak $`\nu ^{1/3}`$ frequency dependence) before undergoing a slow decline. Most other models predict a strong frequency dependence in peak flux which is not seen in this case.

Knowing $`t_j`$ and the density of the ambient medium n0 from the model fit (Table 3) we can make a geometric correction to the total isotropic energy Eγ, as determined from either the observed $`\gamma `$-ray fluence or the total energy of the afterglow E52, from the fit to the afterglow data (Sari et al. 1999, Livio & Waxman (2000)). This approach gives values for the jet opening angle $`\theta _j`$ between 10 and 20, which for a two-sided jet reduces the GRB energy to $`10^{51}`$ erg. The rapid lateral expansion of the jet also accelerates the transition to the non-relativistic regime, resulting in a change in the evolution of the light curves. Since this occurs on a timescale $`t_{\mathrm{NR}}t_j\theta _j^2350`$ days (Waxman, Kulkarni & Frail (1998)), we do not expect the non-relativistic transition to be important for our data.

There is some freedom in our choice of $`\nu _c`$. We know that a cooling break (i.e., $`\mathrm{\Delta }\alpha =0.25`$) is not apparent in the R band light curve on timescales of 2-10 days, so we searched for solutions with $`\nu _c`$ above or below this frequency. We found that physically consistent solutions (i.e., with non-negative host fluxes, and $`ϵ_B<1`$) were only possible for values of $`\nu _c`$ below the optical band.

As part of the fitting process we also solved for the host flux density in the R and K bands and for any local dust obscuration, assuming an LMC-like extinction law. This yields $`f_{host}`$(R)=1.1 $`\mu `$Jy, $`f_{host}`$(K)=1.7 $`\mu `$Jy and A$`{}_{\mathrm{V}}{}^{}{}_{}{}^{host}`$=0.4 (in the host galaxy restframe). Klose et al. (2000b) argued for significant dust extinction with A$`{}_{\mathrm{V}}{}^{}{}_{}{}^{host}`$=0.96. However, they likely overestimated A$`{}_{\mathrm{V}}{}^{}{}_{}{}^{host}`$ since they assumed a spherical fireball model and arbitrarily located $`\nu _c`$ above the optical band. Moreover, we find that there is some covariance between the values of A$`{}_{\mathrm{V}}{}^{}{}_{}{}^{host}`$ and $`p`$ so that only with a global fit, in which $`p`$ is constrained by the radio data as well as the optical data, we can solve for A$`{}_{\mathrm{V}}{}^{}{}_{}{}^{host}`$ in a self-consistent manner.

In view of the claims linking GRBs with the collapse of massive stars (Galama et al. (1998), Bloom et al. (1999), Reichart (1999), Piro et al. (2000)), we considered a final model of a spherical explosion into a wind-blown circumburst medium (Wind: Chevalier & Li (1999), Li & Chevalier (1999)). The Wind model (Figure 1) fits the data as well as the Jet model. In fact, the two models have sufficiently similar $`\chi ^2`$ to be indistinguishable. The close match between the temporal slopes of the late-time 8.46 GHz light curve and the early R band light curve (see §4) is a point in favor of the Wind model since a steeper decline is expected for a jet geometry. Our failure to distinguish between these two models can be blamed on the absence of radio measurements (particularly at millimeter wavelengths) at early times. The rapid rise of the flux density below $`\nu _a`$ and $`\nu _m`$ in the Wind model and the strong frequency dependence of the peak flux (see Figure 1), make such measurements advantageous (Panaitescu & Kumar 2000a ). Moreover, in principle the Wind model can be distinguished from the other models by the fact that in this model $`\nu _c`$ is increasing with time ($`\nu _ct^{1/2}`$). However, in this case since $`\nu _c`$ lies below the optical/IR bands, this behavior would be distinguishable only at late time when the host flux dominates over the OT. As before we solved for the host flux and any dust extinction, yielding $`f_{host}`$(R)=0.9 $`\mu `$Jy, $`f_{host}`$(K)=1.3 $`\mu `$Jy and A$`{}_{\mathrm{V}}{}^{}{}_{}{}^{host}`$=0.3. In our view further (and more sophisticated) model fits are not warranted by these data.

In summary, we find that the radio and optical/NIR observations of the afterglow emission from GRB 000418 can be fit by two different models. The close similarity between the results of the Wind and Jet models has been noted for other GRBs: GRB 970508 (Frail et al. (2000), Chevalier & Li (2000)), GRB 980519 (Frail et al. 2000b , Chevalier & Li (1999)), GRB 000301C (Berger et al. (2000), Li & Chevalier (2000)), and GRB 991208 (Galama et al. (2000), Li & Chevalier (2000)). The resolution of this conflict is important, since it goes to the core of the GRB progenitor issue. If the GRB progenitor is a massive star then there must be evidence for a density gradient in the afterglow light curves, reflecting the stellar mass loss that occurs throughout the star’s lifetime (Chevalier & Li (1999), Panaitescu & Kumar 2000a ). At present, an unambiguous case for a GRB afterglow expanding into a wind has yet to be found. On the contrary, most afterglows are better fit by a jet expanding in a constant density medium (e.g., Harrison et al. (1999), Halpern et al. (2000), Panaitescu & Kumar 2000b ) and thus we are faced with a peculiar situation. While there is good evidence linking GRBs to the dusty, gas-rich environments favored by hypernova progenitors (Bloom, Kulkarni & Djorgovski (2000), Galama & Wijers (2000)), the expected mass loss signature is absent (or at best ambiguous) in all afterglows studied to date.

A. Diercks is supported by a Millikan Fellowship at Caltech. GRB research at Caltech is supported by NSF and NASA grants (SRK, SGD, FAH). KH is grateful for Ulysses support under JPL Contract 958056, and for NEAR support under NAG 5 9503.


text:
# 1 Introduction

## 1 Introduction

The study on unstable D-brane systems in recent years has taught us many new aspects of string theory . It is believed that the unstable D-brane systems decay into the perturbative vacuum of closed strings or lower dimensional stable D-branes. The occurrence of such phenomena has been shown by some analyses . These phenomena are understood in terms of tachyon condensation, i.e. condensation of open string tachyons. In other words, these researches have clarified the mechanism of the stabilization of the tachyons. The occurance of the tachyon condensation had also been investigated in .

Some of the unstable D-branes can be described by a class of worldsheet theory  whose action contains a boundary term representing the effect of the tachyon as well as the bulk action. In general, the boundary term can be regarded as a relevant parturbation, so the condensation of the tachyon can be studied by analyzing the renormalization group flow induced by the boundary term. The simplest choice of the boundary term is

$$u_\mathrm{\Sigma }𝑑\xi X(\xi )^2.$$
(1.1)
Since the worldsheet theory with this term remains a free theory, some exact results can be extracted from this theory. One remarkable example is the result obtained by boundary string field theory  which enables one to derive an effective action of spacetime fields from the disk partition function of the above theory. The exact value of the D-brane tension is also obtained. For this purpose, it is suitable to compactify the theory on $`S^1`$ and this leads one to the study of an integrable system .

To identify the decay remnants as D-branes, it should also be checked that the physical degrees of freedom on the remnants coincide with that of the open string on D-branes. This has been considered in  by using toy models which capture some properties of the unstable brane system.

In this paper we argue this problem in terms of the worldsheet theory perturbed by the boundary term introduced above. The spectrum of an open string can be obtained by calculating 1-loop (annulus) partition function. We perform the calculation of the partition function including the boundary term (1.1) and show that this connects continuously the partition functions of open strings with different boundary conditions. Similar analyses on the effect of boundary terms have been done . Thrust of this paper is to show a connection between the Neumann-Neumann (NN) strings (or the Dirichlet-Dirichlet (DD) strings) and the Neumann-Dirichlet (ND) strings as well as between the NN strings and the DD strings. They are shown by explicitly deriving their partition functions as limiting forms of the same function.

This paper is organized as follows. In section 2 the effect of the boundary term (1.1) is shown in view of classical solutions. To obtain the 1-loop partition function, we calculate in section 3 the Green’s function on annulus with appropriate boundary conditions. This is used to obtain the partition function in section 4. A possible extension and a suggestion of this result to the structure of string theory are discussed in section 5.

## 2 Classical solution

The phenomena of tachyon condensation in bosonic string theory can be described by the following very simple action .

$$S=\frac{1}{4\pi \alpha ^{}}\left[_\mathrm{\Sigma }𝑑\tau 𝑑\sigma _aX_\mu _aX^\mu +_\mathrm{\Sigma }𝑑\xi \underset{\nu =p}{\overset{25}{}}u_\nu (X^\nu )^2\right]$$
(2.1)
$`\xi `$ parametrizes the boundary $`\mathrm{\Sigma }`$ of the worldsheet $`\mathrm{\Sigma }`$. The couplings $`u_\nu `$ increase along the renormalization group flow, and in the IR limit ($`u_\nu +\mathrm{}`$) the second term of the action (2.1) imposes $`X^\nu =0`$. So the Neumann boundary condition in the UV limit turns into the Dirichlet boundary condition in the IR limit. This indicates the decay of the original D25-brane into a Dp-brane at $`x^\nu =0`$.

This can also be seen by solving the equation of motion, taking into account the boundary term. To see the effect of the boundary term, we discuss the following situation. Let us consider two Dp-branes and an open string stretched between them. If one of the Dp-branes decays into a D(p$``$1)-brane, one of the coordinates of the open string will obey the Neumann-Dirichlet condition (i.e. the Neumann condition at one end and the Dirichlet condition at the other end) after the decay.

We will focus on the coordinate $`X`$ along which the Dp-brane shrinks. The solution of the equation of motion is as follows,

$$X(z,\overline{z})=\underset{\lambda \mathrm{\Lambda }}{}(a_\lambda z^\lambda +\stackrel{~}{a}_\lambda \overline{z}^\lambda )$$
(2.2)
where $`z=e^{\tau +i\sigma }`$ and $`\tau ,\sigma `$ are the worldsheet coordinates. The scalar $`X`$ must satisfy the boundary conditions

$$\{\begin{array}{cc}_\sigma X=0,\hfill & (\sigma =0)\hfill \\ _\sigma X+uX=0.\hfill & (\sigma =\pi )\hfill \end{array}$$
(2.3)
These conditions are satisfied if all $`\lambda `$’s are solutions of the following equation.

$$\lambda \mathrm{tan}(\lambda \pi )=u$$
(2.4)
This equation can be easily solved when $`u=0,+\mathrm{}`$ i.e. UV and IR limit.

$$\lambda \{\begin{array}{cc}𝐙\hfill & (u=0)\hfill \\ 𝐙+\frac{1}{2}\hfill & (u=\mathrm{})\hfill \end{array}$$
(2.5)
So one can see that the NN string (integral moding) turns continuously into the ND string (half-integral moding) as $`u`$ increases.

In principle, one can calculate, for example, 1-loop partition function with general $`u`$ by quantizing the open string coordinate (2.2). However, solving the eq.(2.4) is difficult in general $`u`$. Moreover the $`\lambda `$’s are not at regular intervals, so the calculations will be very hard. In the following sections, we will take another way to calculate the 1-loop partition function.

## 3 Green’s function on annulus

In this section, we calculate Green’s function of the scalar field $`X`$ on annulus $`A`$ .

$$A=\left\{z𝐂\right|r|z|1\}$$
(3.1)
$`r`$ is related to the modulus of the annulus.

Again we consider an open string stretched between two Dp-branes. Then each end of the string interacts with tachyon field on each Dp-brane. Therefore the action of the open string has, in general, different boundary term for each boundary of the annulus $`A`$. This corresponds to imposing different boundary condition on the Green’s function for each boundary.

The Green’s function $`G(z,w)`$ we would like to find is the solution of the equation

$$\frac{1}{\pi \alpha ^{}}_z_{\overline{z}}G(z,w)=\delta ^2(z,w),$$
(3.2)
satisfying the following boundary conditions

$`\left[z_z+\overline{z}_{\overline{z}}+u\right]G(z,w)|_{|z|=1}`$ $`=`$ $`0,`$ (3.3)
$`\left[r^1(z_z+\overline{z}_{\overline{z}})+v\right]G(z,w)|_{|z|=r}`$ $`=`$ $`0.`$ (3.4)
$`u,v=0`$ corresponds to the NN condition, $`u,v+\mathrm{}`$ to the DD condition and $`u=0,v+\mathrm{}`$ (and $`u+\mathrm{},v=0`$) to the ND condition. In addition, $`G(z,w)`$ should have the following properties.

$`G(z,w)`$ $`=`$ $`G(w,z)`$
$`G(e^{i\phi }z,e^{i\phi }w)`$ $`=`$ $`G(z,w)\text{(rotation around the origin)}`$ (3.5)
We start with the following ansatz.

$`G(z,w)`$ $`=`$ $`{\displaystyle \frac{\alpha ^{}}{2}}\mathrm{log}|zw|^2+a\mathrm{log}|z|^2\mathrm{log}|w|^2+b(\mathrm{log}|z|^2+\mathrm{log}|w|^2)+c`$ (3.6)
$`+{\displaystyle \underset{k=1}{\overset{\mathrm{}}{}}}d_k\left\{\left({\displaystyle \frac{z}{w}}\right)^k+\left({\displaystyle \frac{w}{z}}\right)^k\right\}+{\displaystyle \underset{k=1}{\overset{\mathrm{}}{}}}\stackrel{~}{d}_k\left\{\left({\displaystyle \frac{\overline{z}}{\overline{w}}}\right)^k+\left({\displaystyle \frac{\overline{w}}{\overline{z}}}\right)^k\right\}`$
$`+{\displaystyle \underset{k=1}{\overset{\mathrm{}}{}}}e_k\left\{(z\overline{w})^k+(\overline{z}w)^k\right\}+{\displaystyle \underset{k=1}{\overset{\mathrm{}}{}}}\stackrel{~}{e}_k\left\{(z\overline{w})^k+(\overline{z}w)^k\right\}`$
This is, of course, a solution of the eq.(3.2). The boundary conditions (3.3)(3.4) are now reduced to linear equations of the coefficients.

The condition (3.3) implies, for each $`k`$,

$`2a+ub`$ $`=`$ $`0,`$
$`2b+uc`$ $`=`$ $`\alpha ^{},`$
$`(k+u)d_k+(k+u)\stackrel{~}{e}_k`$ $`=`$ $`0,`$ (3.7)
$`(k+u)d_k+(k+u)e_k`$ $`=`$ $`{\displaystyle \frac{\alpha ^{}}{2}}\left(1{\displaystyle \frac{u}{k}}\right),`$
$`(k+u)\stackrel{~}{d}_k+(k+u)\stackrel{~}{e}_k`$ $`=`$ $`0,`$
$`(k+u)\stackrel{~}{d}_k+(k+u)e_k`$ $`=`$ $`{\displaystyle \frac{\alpha ^{}}{2}}\left(1{\displaystyle \frac{u}{k}}\right).`$
The condition (3.4) means

$`{\displaystyle \frac{2a}{r}}2av\mathrm{log}rbv`$ $`=`$ $`{\displaystyle \frac{\alpha ^{}}{2}}v,`$
$`{\displaystyle \frac{2b}{r}}2bv\mathrm{log}rcv`$ $`=`$ $`0,`$
$`\left({\displaystyle \frac{k}{r}}v\right)d_k\left({\displaystyle \frac{k}{r}}+v\right)r^{2k}\stackrel{~}{e}_k`$ $`=`$ $`{\displaystyle \frac{\alpha ^{}}{2}}\left({\displaystyle \frac{1}{r}}{\displaystyle \frac{v}{k}}\right),`$ (3.8)
$`\left({\displaystyle \frac{k}{r}}+v\right)d_k+\left({\displaystyle \frac{k}{r}}v\right)r^{2k}e_k`$ $`=`$ $`0,`$
$`\left({\displaystyle \frac{k}{r}}v\right)\stackrel{~}{d}_k\left({\displaystyle \frac{k}{r}}+v\right)r^{2k}\stackrel{~}{e}_k`$ $`=`$ $`{\displaystyle \frac{\alpha ^{}}{2}}\left({\displaystyle \frac{1}{r}}{\displaystyle \frac{v}{k}}\right),`$
$`\left({\displaystyle \frac{k}{r}}+v\right)\stackrel{~}{d}_k+\left({\displaystyle \frac{k}{r}}v\right)r^{2k}e_k`$ $`=`$ $`0.`$
These equations have the following solution,

$`a`$ $`=`$ $`{\displaystyle \frac{\alpha ^{}}{4}}uv\left({\displaystyle \frac{u}{r}}+uv\mathrm{log}rv\right)^1,`$
$`b`$ $`=`$ $`{\displaystyle \frac{\alpha ^{}}{2}}v\left({\displaystyle \frac{u}{r}}uv\mathrm{log}r+v\right)^1,`$
$`c`$ $`=`$ $`{\displaystyle \frac{\alpha ^{}}{2}}\left({\displaystyle \frac{2}{r}}2v\mathrm{log}r\right)^1\left({\displaystyle \frac{u}{r}}+uv\mathrm{log}rv\right)^1,`$ (3.9)
$`d_k`$ $`=`$ $`\stackrel{~}{d}_k=(ku)\left({\displaystyle \frac{k}{r}}v\right)r^{2k}f_k,`$
$`e_k`$ $`=`$ $`(ku)\left({\displaystyle \frac{k}{r}}+v\right)f_k,`$
$`\stackrel{~}{e}_k`$ $`=`$ $`(k+u)\left({\displaystyle \frac{k}{r}}v\right)r^{2k}f_k,`$
where

$$f_k=\frac{\alpha ^{}}{2k}\left\{(ku)\left(\frac{k}{r}v\right)r^{2k}(k+u)\left(\frac{k}{r}+v\right)\right\}^1.$$
(3.10)
## 4 1-loop partition function

From the Green’s function obtained in the previous section, one can calculate the expectation value of the energy-momentum tensor. From the following OPE

$$X(z)X(w)=\frac{\alpha ^{}}{2}\frac{1}{(zw)^2}\alpha ^{}T_{ww}(w)+O(zw)$$
(4.1)
where

$$T_{zz}=\frac{1}{\alpha ^{}}XX,$$
(4.2)
one can obtain

$`T_{zz}(z)`$ $`=`$ $`{\displaystyle \frac{1}{\alpha ^{}}}\underset{wz}{lim}\left[_z_wG(z,w)+{\displaystyle \frac{\alpha ^{}}{2}}{\displaystyle \frac{1}{(zw)^2}}\right]`$ (4.3)
$`=`$ $`{\displaystyle \frac{1}{\alpha ^{}}}{\displaystyle \frac{1}{z^2}}\left(a{\displaystyle \underset{k=1}{\overset{\mathrm{}}{}}}2k^2d_k\right).`$
Similar result can be obtained for $`\overline{T}_{\overline{z}\overline{z}}(\overline{z})`$.

It is convenient to map the annulus $`A`$ into rectangle $`R`$.

$$R=\{\rho 𝐂|\pi \mathrm{}\rho 0,0\mathrm{}\rho 2\pi t\}$$
(4.4)
$`z`$ and $`\rho `$ are related as $`z=\mathrm{exp}(\rho /t)`$, where $`t=\pi /\mathrm{log}r`$.

The expectation value of $`T_{\rho \rho }(\rho )`$ on $`R`$ is

$`T_{\rho \rho }(\rho )`$ $`=`$ $`\left({\displaystyle \frac{dz}{d\rho }}\right)^2T_{zz}(z)+{\displaystyle \frac{c}{12}}\{z,\rho \}`$ (4.5)
$`=`$ $`{\displaystyle \frac{1}{t^2}}\left[{\displaystyle \frac{1}{\alpha ^{}}}\left(a{\displaystyle \underset{k=1}{\overset{\mathrm{}}{}}}2k^2d_k\right)+{\displaystyle \frac{1}{24}}\right].`$
The change of the modulus of the worldsheet corresponds to a change of the metric. Therefore the variation of the 1-loop partition function $`Z`$ with respect to the modulus is proportional to the expectation value of the energy-momentum tensor. The precise relation we need is as follows.

$$\delta \mathrm{log}Z=\frac{1}{2\pi }d^2\rho \left(\delta g_{\rho \rho }\overline{T}_{\overline{\rho }\overline{\rho }}(\overline{\rho })+\delta g_{\overline{\rho }\overline{\rho }}T_{\rho \rho }(\rho )\right)$$
(4.6)
If the length $`t`$ of the rectangle $`R`$ changes by $`\delta t`$, the corresponding change of the metric is

$$\delta g_{\rho \rho }=\delta g_{\overline{\rho }\overline{\rho }}=\frac{1}{2t}\delta t,$$
(4.7)
up to a rescaling of the metric.

Now we obtain a differential equation for the 1-loop partition function

$$\frac{d}{dt}\mathrm{log}Z(t)=\frac{2\pi }{t^2}\left[\frac{1}{\alpha ^{}}\left(a\underset{k=1}{\overset{\mathrm{}}{}}2k^2d_k\right)+\frac{1}{24}\right].$$
(4.8)
Note that since the conformal invariance is broken at the boundary for general $`u`$ and $`v`$, the argument above might not be valid in general. Nevertheless, the equation (4.8) is meaningful at least at the conformal limits of $`u,v`$ which we would like to discuss.

Let us see whether the solution of the above equation reproduces the well-known form of the partition functions for (i) NN string, (ii) DD string and (iii) ND string.

(i) NN string

This case corresponds to taking $`u,v=0`$. In this limit,

$$a=0,d_k=\frac{\alpha ^{}}{2k}\frac{r^{2k}}{r^{2k}1}.$$
(4.9)
Note that the singularity in the Green’s function does not appear in the eq.(4.8). The partition function is

$`\mathrm{log}Z(t)`$ $`=`$ $`{\displaystyle 𝑑t\frac{1}{t^2}\left(\underset{k=1}{\overset{\mathrm{}}{}}\frac{2\pi ke^{2\pi k/t}}{e^{2\pi k/t}1}+\frac{2\pi }{24}\right)}`$ (4.10)
$`=`$ $`{\displaystyle \underset{k=1}{\overset{\mathrm{}}{}}}\mathrm{log}\left(1e^{2\pi k/t}\right)+{\displaystyle \frac{2\pi }{24t}}+\text{const.}`$
$`=`$ $`\mathrm{log}\eta \left({\displaystyle \frac{i}{t}}\right)+\text{const.}`$
Thus

$`Z(t)`$ $``$ $`\eta \left({\displaystyle \frac{i}{t}}\right)`$ (4.11)
$`=`$ $`{\displaystyle \frac{1}{\sqrt{t}}}{\displaystyle \frac{1}{\eta (it)}}.`$
This is the precise form including the zeromode contribution.

(ii) DD string

This case corresponds to the limit $`u,v+\mathrm{}`$. Then

$$a=\frac{\alpha ^{}}{4}\frac{1}{\mathrm{log}r},d_k=\frac{\alpha ^{}}{2k}\frac{r^{2k}}{r^{2k}1}.$$
(4.12)
In this case,

$`\mathrm{log}Z(t)`$ $`=`$ $`{\displaystyle 𝑑t\frac{1}{t^2}\left(\frac{t}{2}+\underset{k=1}{\overset{\mathrm{}}{}}\frac{2\pi ke^{2\pi k/t}}{e^{2\pi k/t}1}+\frac{2\pi }{24}\right)}`$ (4.13)
$`=`$ $`\mathrm{log}\left({\displaystyle \frac{1}{\sqrt{t}}}\eta \left({\displaystyle \frac{i}{t}}\right)\right).`$
Thus the correct result

$$Z(t)\frac{1}{\eta (it)}$$
(4.14)
is obtained.

(iii) ND string

The remaining case can be realized by taking $`u=0,v+\mathrm{}`$ (the limit $`u\mathrm{},v=0`$ gives the same result). In this case,

$$a=0,d_k=\frac{\alpha ^{}}{2k}\frac{r^{2k}}{r^{2k}+1}.$$
(4.15)
From these data, one obtains

$`Z(t)`$ $``$ $`e^{2\pi /24t}{\displaystyle \underset{k=1}{\overset{\mathrm{}}{}}}\left(1+e^{2\pi k/t}\right)^1`$ (4.16)
$`=`$ $`{\displaystyle \frac{\eta (i/t)}{\eta (2i/t)}}`$
$``$ $`{\displaystyle \frac{\eta (it)}{\eta (it/2)}}`$
$`=`$ $`q^{1/48}{\displaystyle \underset{k=1}{\overset{\mathrm{}}{}}}{\displaystyle \frac{1}{1q^{k1/2}}}.(q=e^{2\pi t})`$
## 5 Discussions

The calculations we have performed will also be able to apply to superstring theory. Consider an open string on, say, D9-brane in IIA theory. The spectrum of the open string is the one without GSO-projection . So the 1-loop partition function of the worldsheet fermions in the NS-sector will be

$$Z\text{Tr}_{NS}q^{L_0}.$$
(5.1)
If the D9-brane decays into a D8-brane, the GSO-projection is imposed on the spectrum and the partition function in the NS-sector becomes

$$Z\frac{1}{2}\text{Tr}_{NS}q^{L_0}+\frac{1}{2}\text{Tr}_{NS}(1)^Fq^{L_0}.$$
(5.2)
The boundary term corresponding to this decay in the case of superstring is

$$u_\mathrm{\Sigma }𝑑\xi \left[X^2+\psi \frac{1}{_\xi }\psi \right].$$
(5.3)
These terms depend only on one worldsheet fermion. Therefore they do not affect the other fermions. In the case of bosonic string, the 1-loop partition function is just a product of scalar partition functions. So the decay of D-branes can be described only by the scalars corresponding to the directions along which the D-branes shrink. On the other hand, the partition function of the fermions will not have such product form in general, as seen above. So it seems difficult that the partition function with the boundary term (5.3) connects (5.1) with (5.2) continuously. It is interesting to see how the GSO-projection is imposed automatically in the IR limit.

The decay of the D-branes to lower dimensional BPS branes in superstring is also interesting for the following reason. After the tachyon condensation, half of the physical degrees of freedom on the original unstable brane disappears due to the GSO-projection. This resembles the phenomenon which occurs in the decay of D-branes into the vacuum, which is rather difficult to analyze. In this case all of the open string degrees of freedom is assumed to disappear . So discussing the former decay may be helpful for the study of the latter decay and the physics around the minimum of the tachyon potential.

The calculation of the partition functions on annulus would be suitable for the study of the brane-antibrane systems 111We thank G.Mandal for valuable discussions on this direction.. The string which feels the existence of both D-brane and $`\overline{\text{D}}`$-brane is the one stretched between them. So the fundamental quantities for that system would be annulus amplitudes. It will be natural to expect that an annulus partition function with boundary terms corresponding to tachyon and gauge fields provides an effective action of the spacetime fields if one can relate the partition function to the spacetime action, as has been done for disk partition functions in boundary string field theory .

It has been shown  that the tree-level calculation provides the correct value of the D-brane tension. The form of the worldvolume is well described by the classical solutions of the spacetime effective field theory of open string states . And we have shown in this paper that the correct spectrum on the D-branes can also be obtained from the 1-loop calculation. These results seem to indicate that, at least in the bosonic case, whole information on D-branes is “built-in” in the open string sector. The appropriate open strings would appear by choosing the tachyonic background, rather than choosing the boundary conditions of open strings by hand. If the same is true for superstring, it might be that the inclusion of D-branes into the theory of superstrings is equivalent to the inclusion of open superstrings without GSO-projection . We hope that such a viewpoint will be a guide to formulate the string theory.

Acknowledgements

I would like to thank H. Itoyama, G. Mandal and K. Murakami for valuable discussions. This work is supported in part by JSPS Reseach Fellowships.