text:
# Large-scale low-energy excitations in 3-d spin glasses

## 1 Introduction

The physics of spin glasses Young98  is an old yet still very active subject of study. Much progress has been made in understanding the nature of the low temperature phase, but some fundamental issues remain open. Among these is whether the free-energy landscape consists of multiple valleys all contributing to the partition function in the thermodynamic limit. This is what happens in mean field theory MezardParisi87b , and a growing consensus is that it also arises in finite dimensions. Perhaps the strongest numerical evidence in favor of this comes from the spin overlap probability distribution $`P(q)`$ that seems to be non-trivial (see MarinariParisi99b  for a review).

Several other striking properties of mean field may also hold in finite dimensions; the purpose of our work is to test this by numerically characterizing the valley states in the energy landscape of the 3-dimensional Edwards-Anderson EdwardsAnderson75  (EA) spin glass model. In the mean field picture, one expects some system-size excitations (configurations obtained from the ground state by flipping a finite fraction of all the spins) to have excess energies of $`O(1)`$. Furthermore, these excitations should (i) be sponge-like with non-zero surface to volume ratios; and (ii), be homogeneous on scales larger than the lattice spacing.

We first describe how we find excitations in Section 2 and then discuss in Section 3 some possible scenarios for how replica symmetry breaking may arise in position space (unfortunately sometimes called real space). In Section 4 we investigate topological properties of system-size excitations. Previous work KrzakalaMartin00  gave evidence that the $`3d`$ EA model with free boundary conditions had system-size excitations whose energies were $`O(1)`$. In the present work, we use periodic boundary conditions and consider the excitations’ windings around the lattice to classify them topologically. We conclude again that it is possible to flip a finite fraction of all the spins at an $`O(1)`$ energy cost. Furthermore, most of these excitations are sponge-like, and our data are compatible with the possibility that all system-size excitations are sponge-like in the thermodynamic limit. Then in Section 5 we try to characterize the geometrical properties of these excitations. We measure their surface area and correlation functions, and then probe the distribution of their hole sizes. The data is most naturally interpreted as indicating that there is an intrinsic length scale that grows with the lattice size; if this scale grows indefinitely, then surface to volume ratios of the excitations go to zero KrzakalaMartin00 ; PalassiniYoung00a  asymptotically. Beyond this scale (which is much smaller than the lattice size), excitations may be homogeneous, in agreement with the mean field picture. Given the small range in sizes that we can treat, it is also possible, though less likely, that the growth of this length scale is a finite size effect which saturates for larger sizes; if this is the case, the mean field picture holds and excitations are spongy beyond a few lattice spacings; whether they are homogeneous or lumpy is less clear as we find evidence for heterogeneities on scales much larger than the lattice spacing.

## 2 System-size excitations

### 2.1 Valleys

Consider a general Ising spin glass model with pairwise couplings

$$H=\underset{i<j}{}J_{ij}S_iS_j$$
(1)
Let $`N`$ be the total number of spins. We would like to characterize the energy landscape of this system through the statistical properties of its valleys. In the infinite volume case, one can define a valley via the configuration at its bottom; the bottom of a valley can be defined as a minimum of the energy under all finite number of spin flips. Unfortunately, this simple definition has to be modified in finite volume; a simple yet heuristic modification consists in imposing the energy to be a minimum under any number of spin flips fewer than $`vN`$. $`v[0,1/2]`$ is a distance parameter (in fact it is the Hamming distance divided by $`N`$) related to the usual spin overlap $`q`$ by $`q=12v`$. Because of the global spin flip symmetry of the Hamiltonian, hereafter we will force $`q0`$.

The influence of $`v`$ on the definition of the valleys is important as all valley bottoms by construction will differ by at least $`vN`$ spin flips. Suppose one had a 1-step replica symmetry breaking with a spin overlap probability distribution

$$P(q)=\alpha \delta (q)+(1\alpha )\delta (qq_1)$$
(2)
If $`q_11`$ as the temperature goes to zero, all choices of $`v`$ satisfying $`v<1/2`$ would recover the thermodynamically relevant valleys as $`N\mathrm{}`$. However, in the EA model, one expects the replica symmetry breaking to be continuous and valleys with overlaps arbitrarily close to 1 should arise in the zero temperature limit. Then any fixed choice of $`v`$ will eliminate some of the thermodynamically relevant valleys. Since this effect decreases as $`v`$ does, one could simply choose a small value of $`v`$ and determine empirically the extent of the robustness in $`v`$ of the analysis.

However from a numerical point of view, the main difficulty lies in finding low energy states rather than in classifying them. In fact, it is at present nearly impossible to find the minimum number of spins to flip before the energy of a configuration is lowered. Thus we cannot even tackle the task of finding the best valley lying within a reduced distance $`v`$ and $`(v+\mathrm{\Delta }v)`$ from the ground state. Because of this limitation, we have chosen a more hands-on approach where we just sample low-lying excitations. Given the way we find these configurations, we expect that nearly always they will in fact be bottoms of valleys.

### 2.2 Low energy excitations

From an algorithmic point of view, the ground state configuration $`𝒞^0`$ of a spin glass can be determined with a high level of confidence as long as $`N`$ is not too large. In this work, we have used a genetic renormalization algorithm HoudayerMartin99b  which allows us to go to lattices up to $`12^3`$. Now for extracting valleys or excited states, it is necessary to first compute $`𝒞^0`$ and then to introduce a $`𝒞^0`$-dependent constraint or perturbation to the Hamiltonian that will lead to a modified ground state labeled $`𝒞^1`$.

We have followed the constraint-based technique proposed in KrzakalaMartin00 : given the ground state, we flip the relative orientation of $`2`$ selected spins and compute the new ground state with this constraint. A large scale excitation is obtained only if its energy is smaller than that of all the droplets surrounding either of the two selected spins. In practice, we repeat this multiple times by randomizing the choice of the two selected spins, obtaining a collection of $`𝒞^1`$ excitations. Note that this method gives no control over the number $`V`$ of spins that will flip when going from $`𝒞^0`$ to $`𝒞^1`$.

For each instance (set of $`J_{ij}`$), our numerical simulation then leads to $`𝒞^0`$ (the ground state), and a number of excitations. From this set, one can extract the configurations that satisfy any desired constraint. For instance, one may impose $`V/Nv_{min}`$ when looking for excitations of size growing linearly with $`N`$ and study the energy and position space properties of these excitations.

### 2.3 Two scales for finite energy excitations

Hereafter, we consider only the three-dimensional Edwards-Anderson model with nearest-neighbor interactions. The $`J_{ij}`$ are i.i.d. Gaussian random variables of zero mean and unit variance, and we work with $`L\times L\times L`$ cubic lattices ($`L^3=N`$) and periodic boundary conditions.

Our procedure for sampling excitations can extract low energy droplets, but within the mean field picture one expects to also find large-scale excitations whose size grows linearly with $`N`$. We can test this two-scale picture by considering the probability distribution of $`V`$, the number of spins flipped when going from the ground state to the excited state. Suppose that the only excitations having $`O(1)`$ energy are the droplets ($`V`$ finite as $`L\mathrm{}`$) and system-size excitations ($`v=V/N`$ finite as $`L\mathrm{}`$). Then excitations where $`V\mathrm{}`$ but $`v0`$ as $`L\mathrm{}`$ will have a probability tending towards $`0`$. Mathematically, this means that our extraction of excitations leads to a probability distribution for $`V`$ of the form

$$P_L(V)\underset{L\mathrm{}}{}\alpha P_l(V)+(1\alpha )P_g(v)$$
(3)
where $`P_l`$ and $`P_g`$ are the normalized probability distributions associated with droplet (local) and system-size (global) excitations.

We have measured the frequencies of “events” with $`V`$ for instance in the range $`[L^2,2L^2]`$ as a function of $`L`$. (We say that we have an event in our data set whenever an instance and our sampling procedure lead to an excitation satisfying chosen criteria. Here and in the rest of our study, we generated three excitations for each instance; we have $`10000`$ instances at each value of $`L10`$, $`8000`$ at $`L=11`$, and $`5000`$ at $`L=12`$.) The frequencies decrease with $`L`$ and quite reasonably can be extrapolated to zero. As an example, for the interval given above, we find the frequencies $`0.520`$ ($`L=4`$), $`0.397`$ ($`L=5`$), $`0.321`$ ($`L=6`$), $`0.256`$ ($`L=7`$), $`0.232`$ ($`L=8`$), $`0.208`$ ($`L=9`$), $`0.187`$ ($`L=10`$), $`0.170`$ ($`L=11`$), and $`0.162`$ ($`L=12`$). Note that by construction, one cannot get excitations whose energies are larger than those of droplets, so all states found in our sampling necessarily have $`O(1)`$ energies. This analysis then confirms the two-scale form given in equation (3).

## 3 Spin glass scenarios in finite dimensions

### 3.1 Length scales for self-averaging

Consider first the energy of system-size excitations. In the mean field picture (as motivated by the properties of the SK model) we expect to be able to find a $`𝒞^1`$ (for any choice of $`v_{min}`$) with a finite probability, and that its energy will be $`O(1)`$, i.e., finite when $`N\mathrm{}`$. On the contrary, in the droplet FisherHuse88  and scaling BrayMoore86  pictures, the characteristic energy of large scale excitations grows as a power of $`L`$. In HoudayerMartin00b  it was argued that one should distinguish the energy scaling of large-scale excitations from that of droplets in an infinite system; it is then necessary to introduce two exponents, $`\theta _g`$ ($`g`$ for global) and $`\theta _l`$ ($`l`$ for local); for instance the lowest system-size excitations have energies scaling as $`L^{\theta _g}`$. Section 4.2 will lead us to the conclusion that $`\theta _g0`$. Extrapolating to finite temperature as is now commonly done MarinariParisi00b , this indicates that replica symmetry is broken in the three-dimensional Edwards-Anderson model, i.e., the overlap probability distribution $`P(q)`$ is non-trivial in agreement with many previous studies (see MarinariParisi99b  for a review).

Consider now the position-space characteristics of these large scale excitations. We are concerned here with the properties of the (connected) cluster of spins that are flipped when comparing to the ground state; we shall use the term excitation when referring to this cluster in addition to the configuration $`𝒞^1`$ itself. By definition, the sizes of these clusters are $`O(N)`$ (those are the events we focus upon). Of major interest is to understand whether these excitations are topologically non-trivial or not, homogeneous or inhomogeneous, fractal, multi-fractal, etc… To classify the different possibilities, we ask how the properties of the clusters depend on the scale of observation and on $`L`$, the size of the lattice. Clearly there are many observables that can be considered; to stay as simple as possible this discussion will focus on the cluster’s density or equivalently on its local overlap as a function of the scale of observation.

Consider an $`M\times M\times M`$ window or box and let $`q_M`$ be the overlap between $`𝒞^0`$ and $`𝒞^1`$ restricted to this box. (The cluster’s density in the box is just $`(1q_M)/2`$.) Obviously $`q_M`$ fluctuates no matter how large $`M`$ is as the global overlap $`q`$ itself is not self-averaging. But if we fix $`q`$, at what scale in $`M`$ do the fluctuations in $`q_M`$ disappear, or equivalently, what is the typical fluctuation of $`q_M`$ as a function of the observation scale $`M`$? Let $`P_{M,L}(q_M)`$ be the disorder-averaged distribution of $`q_M`$; its mean is $`q`$ and its variance will decrease to zero as $`M`$ approaches $`L`$. We can distinguish different scenarios according to the behavior of this distribution. We can expect and will assume that we have pointwise convergence in the infinite volume, i.e,. that at fixed $`M`$

$$P_{M,L}(q_M)\underset{L\mathrm{}}{}P_M(q_M)$$
(4)
(Note that the global overlap between the two configurations must be fixed, and so this distribution depends implicitly on $`q`$.) It is possible that in fact this convergence will be uniform in the mathematical sense, that is one converges to the same function even if $`M`$ varies with $`L`$. We then say that the limit is “regular”, leading to “regular” scenarios. The other scenarios will be non-regular, i.e., the convergence will be non-uniform. The key property that distinguishes these scenarios is whether or not $`q_M`$ becomes self-averaging at a fixed ($`L`$-independent) scale. In the regular scenarios, the fluctuations in $`q_M`$ disappear as $`M`$ grows, so that the scale for self-averaging is a few (or many) times the lattice spacing. In the non-regular scenarios, $`P_M(q_M)`$ will not tend towards a delta function as $`M\mathrm{}`$; fluctuations will go to zero only when $`M`$ is sufficiently big compared to an $`L`$-dependent scale.

In physical terms, the regular scenarios have no hidden scale; as soon as one takes large enough windows, one has convergence of $`q_M`$ towards $`q`$ in the probabilistic sense. As a consequence, once the global overlap $`q`$ has been fixed, there are essentially no significant fluctuations in density down to a few lattice spacings, $`P_{M,L}`$ being very peaked about its mean. $`q_M`$ is then self-averaging when $`q`$ is fixed as soon as $`M`$ becomes large compared to $`1`$. On the contrary, in the non-regular scenarios, $`P_{M,L}`$ does not become peaked about its mean. For $`q_M`$ to become self-averaging, one needs to go out to an $`L`$-dependent scale, for instance $`ML^\gamma `$. A simple system that realizes this scenario is a ferro-magnet with anti-periodic boundary conditions; then $`\gamma =1`$, and for scales $`ML`$, $`P_{M,L}`$ has a two peak structure; $`q_M`$ is not self-averaging on any scale smaller than $`L`$.

Our presentation has concentrated on the behavior of density fluctuations on different scales, but it generalizes in a straightforward manner to other observables (surface of the clusters, number of handles, etc…). Since different observables may become self-averaging on different scales, it is best to keep in mind that the complete picture may be more complicated than that obtained by looking at density fluctuations alone.

### 3.2 Two scenarios with uniform convergence

With uniform convergence, the limit $`L\mathrm{}`$ in equation 4 need not be restricted to $`M`$ fixed; any $`M`$ (dependent or not on $`L`$) will lead to the value given by the pointwise limit. We can say that there is a smooth or regular infinite volume limit on all scales simultaneously.

Our classification of regular scenarios is based on the way $`P_M`$ converges towards a (single!) delta function as $`M\mathrm{}`$. Zooming into the region around its peak, one may expect $`P_M`$ to have a limiting shape if we rescale the $`x`$ axis so that the full-width half-max stays constant. If the limiting shape, $`P^{}`$, decays quickly so all moments exist, then fluctuations much larger than typical ones will be very rare and we will say that the system is homogeneous. If, on the contrary, $`P^{}`$ is a broad distribution, then rare events can dominate the mean square of density fluctuations, and we will say that the system is heterogeneous. Let us give physical pictures of these two cases.

#### Regular homogeneous sponges

Consider first the regular homogeneous scenario. A well known system having this behavior is the Ising model near its Curie point. Long wave-length fluctuations occur and decrease in intensity with wave-length. The dependence of this intensity on the scale ($`M`$) is not the point here, rather we focus on the distribution of the fluctuations at given $`M`$. In this physical system, fluctuation intensities much larger than the typical ones are very rare, the probability distribution $`P^{}`$ decays faster than any power. For our spin glass problem, we will have the regular homogeneous scenario if the density fluctuations of the clusters have this same property as long as we keep the global overlap $`q`$ fixed. In a pictorial language, the clusters associated with an excitation will be rather random at scales larger than the lattice spacing, and can be thought of as homogeneous sponges characterized mainly by their density $`v`$ and their effective mesh spacing $`\mathrm{}_c`$. The terminology “sponge” comes from the fact that such objects are full of handles and are bicontinuous: they and their complement are connected, and the local density beyond the scale $`\mathrm{}_c`$ is nearly uniform. This length $`\mathrm{}_c`$, called the cohesive length of the sponge HoudayerMartin00b , is just a few lattice spacings. (Since the convergence is uniform, the lattice spacing is the only scale, $`\mathrm{}_c`$ cannot diverge with $`L`$ and it is unnatural for it to be many lattice spacings.)

#### Regular inhomogeneous sponges

A different scenario is obtained if we give up the homogeneity hypothesis. We still maintain uniform convergence of observables towards their large $`L`$ limit, but now we assume that the density fluctuations arise not via low intensity modes but via holes in the sponges. To use the picture of Villain, we have something like a swiss cheese, except that the starting point is a sponge rather than the whole lattice, and from this we take out (or put in) blocks of contiguous spins. The resulting object is lumpy on all finite scales and the distribution of hole sizes and thus $`P^{}`$ has long tails. But as long as large holes are sufficiently rare, we can maintain the uniform convergence so that this lumpy system has no characteristic scale other than the lattice spacing.

#### The mean field picture

In any uniform convergence or regular scenarios, a finite fraction of the sites in the cluster are at a finite distance from the cluster’s complement; thus the surface area of the cluster grows as $`L^3`$, and the link overlap $`q_L`$ cannot go to $`1`$ as $`L\mathrm{}`$; $`P(q)`$ and $`P(q_l)`$ are both non-trivial, as in the SK model. Within mean field theory there is no intrinsic scale for self-averaging that grows with $`L`$, thereby suggesting that all observables converge uniformily to their limits; because of that, we shall hereafter simply say that the “mean field picture” corresponds to having uniform convergence of observables.

### 3.3 Scenarios without uniform convergence

In this class of scenarios, the $`L\mathrm{}`$ limit does not commute with the scale of observation ($`M`$) going to infinity. In other words, there is at least one $`L`$-dependent scale that affects the large $`L`$ limit MarinariParisi00b . The simplest such case has a single scale (also called $`\mathrm{}_c`$) such that the observable under consideration (for instance the local density) is self-averaging beyond $`\mathrm{}_c`$ and has a non trivial distribution below. When $`L`$ is finite but large, $`P_{M,L}(q_M)`$ can be approximated by considering its difference with $`P_M(q_M)`$; it is natural to expect this difference to depend only on the ratio $`M/\mathrm{}_c`$. We can then write

$$P_{M,L}(q_M)\underset{L\mathrm{}}{}P_M(q_M)+A_1f_{M/\mathrm{}_c}^1(q_M)$$
(5)
More generally, if there were many characteristic lengths $`\mathrm{}_c^i`$, we could construct such an expression recursively by imposing the condition $`f_0^i=0`$; the first term is always the pointwise limit, and the terms following give the correction associated with passing through the scale $`\mathrm{}_c^i`$. Note that once a scale $`M\mathrm{}_c^k`$ is reached where $`P_{M,L}`$ is a single delta function, then for observables such as density that involve additive quantities no further change in the distribution is possible.

In their full generality, these scenarios with multiple scales are quite complicated. Let us expose a few possibilities in the simplest case where there is a single $`\mathrm{}_c`$. That scale must grow indefinitely with $`L`$, for instance as a power of $`L`$. Suppose now that $`P_M(q_M)`$ converges at large $`M`$ to two delta function peaks centered at $`q_{min}`$ and $`q_{max}`$, while if we take $`M\mathrm{}_c`$ $`P_{M,L}(q_M)`$ converges to the single delta function peak at $`q`$ (recall that beyond the scale $`\mathrm{}_c`$, $`q_M`$ becomes self-averaging and thus must equal the global overlap $`q`$). We have two simple candidate scenarios depending on $`q_{min}`$ and $`q_{max}`$.

#### Fat sponges

If $`q_{min}=0`$ and $`q_{max}=1`$, then at finite scales one never sees the surface of the cluster, while at scales larger than $`\mathrm{}_c`$ the cluster is homogeneous so should ressemble a sponge. (For this last property we assume $`\mathrm{}_cL`$.) We call this case the “fat sponge” scenario as the clusters are just sponges whose characteristic mesh spacing is $`\mathrm{}_c`$. Indeed, up to a dilation of the clusters, everything looks like the regular homogeneous scenario except that $`\mathrm{}_c(L)\mathrm{}`$ in the infinite volume limit.

We can consider several properties of such sponges. First, since the surface of the cluster does not grow as fast as its volume, the standard link overlap converges to a delta function at $`q_l=1`$, and we have a scenario that realizes the TNT KrzakalaMartin00 ; PalassiniYoung00a  (trivial $`q_l`$, non-trivial $`q`$) behavior. Second, the nature of the cluster’s surface on scales smaller than $`\mathrm{}_c`$ will play an important role. The surface is unlikely to be smooth as in the ferromagnetic case; instead, it might be continuum fractal, having a fractal dimension $`2<d_f<3`$. But once one reaches the scale $`\mathrm{}_c`$, everything becomes homogeneous as $`q_M`$ becomes self-averaging.

#### Hierarchical sponges

Consider now the possibility that $`q_{min}0`$ and $`q_{max}1`$. Then below the scale $`\mathrm{}_c`$ one is in either of two phases differing in their density, but neither of these two phases ressembles the ground state locally. In fact these two phases could ressemble sponges, differing mainly by their densities. We will call this a “hierarchical sponge” scenario because one can produce such clusters by hierarchically applying sponge excitations to the ground state. Indeed, start with the ground state and create a fat sponge by flipping a spongy cluster whose characteristic mesh spacing is $`\mathrm{}_c`$. Then if we take that state and flip a spongy cluster whose characteristic mesh spacing is $`O(1)`$, we find that there are locally only two densities and we obtain a two-step hierarchical sponge. (Naturally this construction can be generalized to any number of levels.)

#### Fractals

Consider the fat sponge scenario but take $`\mathrm{}_c`$ to grow linearly with $`L`$. Then there is no regime where $`M\mathrm{}_c`$ and the cluster never becomes homogeneous. There is thus no reason to expect it to be sponge-like (although it may with a finite probability wrap around the lattice and have some of the topological properties that sponges have). The main motivation for this scenario is that it is what arises in a disordered ferro-magnet. Its characteristic is that $`q_M`$ is not self-averaging until $`ML`$ and we can expect to get non-trivial distributions for observables such as $`q_M`$ when $`M`$ is a finite fraction of $`L`$.

Overall, we see that there is a great diversity of possible scenarios. Ideally our goal would be to test for the uniform or not convergence of observables as $`L\mathrm{}`$. However, from the point of view of the mean field picture, we shall be plagued by finite size effects, whereas from non-mean field viewpoints the results will be encouraging but still a bit muddled. The main conclusion will be that $`\mathrm{}_c`$ grows with $`L`$, i.e., the clusters coarsen as $`L`$ grows. This coarsening may stop as in the mean field scenarios, or we may be seeing evidence in favor of the fat sponge scenario. But certainly $`\mathrm{}_c`$ does not grow linearly with $`L`$, ruling out the fractal scenario having heterogeneities on the scale $`L`$.

## 4 Topological properties

### 4.1 Classification by windings

Suppose we consider all events in our data set with $`v=V/N`$ in a given window; we then find that the relative frequency of these events decreases as $`L`$ increases. Within the droplet model, this is expected, and in fact the frequency should decrease to zero as $`L^\theta `$. On the contrary, in the mean field picture, that frequency should go to a constant non-zero value, and its decrease is interpreted as a finite size effect. Because $`\theta `$ is quite small, we cannot use that data alone to discriminate between these two pictures. Thus for each excitation we will also look at its topological properties as defined from the connected cluster of spins that are flipped in that excitation. Our motivation is if that there are system-size excitations of low energy, we expect them to be topologically non-trivial, and so a joint study of topology and $`v`$ may allow one to extrapolate to $`L\mathrm{}`$ cleanly. Indeed, if the frequency of these types of events grows rather than diminishes as $`L`$ increases, it becomes plausible that they survive in the thermodynamic limit.

Clearly a complete topological characterization of the clusters is not necessary. With free boundary conditions, it was possible KrzakalaMartin00  to limit oneself to finding out whether the cluster and its complement touched the different faces of the cube. Here, since we insist on maintaining periodic boundary conditions, we generalize that criterion by considering the winding properties of the cluster in the cube. Given a cluster, we determine whether there are paths on that cluster (going from site to nearest neighboring site) that wind around in any of the three directions $`(x,y,z)`$ of the cubic lattice. From this, we define three classes of clusters as follows. A cluster (and thus the event and excitation) belongs to the first class if it and its complement have a non-trivial winding in all $`3`$ directions of the cube. A cluster belongs to the third class if it has no windings at all. Finally, the second class consists of all other events. We will refer to events in the first class as sponges for obvious reasons, while events in the third class will be referred to as droplets.

### 4.2 Sponges with $`O(1)`$ energies

For each excitation obtained from an instance, we compute its overlap $`q`$ with the ground state or equivalently its $`v`$, and determine to which topological class it belongs. Figure 1 gives the probability density of $`v`$ for each of the three classes defined. The data represented is for $`10000`$ different instances with $`L=10`$, and for each instance we generated $`3`$ excitations. The droplets (events in the third class) create a peak at small $`v`$ while the other two classes are responsible for the rest of the distribution. Now to understand how these distributions evolve with $`L`$, we consider the total contribution of the different classes, integrated over $`v`$. From Table 1 we see that sponge (first class) events have an increasing frequency with $`L`$ and so can reasonably be extrapolated to constitute a non-zero fraction in the large volume limit. This had also already been the case with free boundary conditions KrzakalaMartin00 .

We feel that these data provide strong evidence that there are system-size excitations with $`O(1)`$ energies. Extrapolating to finite temperature, this leads to replica symmetry breaking in the 3d Edwards-Anderson model. Furthermore, because of the constraints built into the first class, these excitations span the whole system. From a direct visualisation of the clusters, we also see that their topology is highly non-trivial: they ressemble sponges in that they have handles everywhere on a scale of a few lattice spacings. They are thus both space spanning (extending throughout the whole system) and space filling, at least on the scale of $`L`$.

### 4.3 Are all valleys sponge-like?

Given the data in Table 1, one can ask whether all low-energy system-size excitations asymptotically fall into the first class. In particular, if a uniform convergence scenario of spin glasses is correct, one expects to find only sponges in the thermodynamic limit as argued in HoudayerMartin00b , so that the second (intermediate) class should disappear when $`L\mathrm{}`$.

To see whether this is the case, we have studied the probability density of $`v`$ as a function of $`L`$, decomposed according to the topological classes. The results for class $`2`$ are displayed in figure 2. It shows that as $`L`$ increases, the curves shift towards smaller $`v`$ while the fraction of all events falling into class $`2`$ (given by the area under each curve) decreases. That this fraction decreases is necessarily the case as we saw that the fractions of the other two classes grow with $`L`$. Can we extrapolate this fraction of class $`2`$ events to zero as $`L\mathrm{}`$? We have performed fits of this fraction to the functions $`a+b/L+c/L^2`$ and $`a+b/L^c`$; both fits give reasonable $`\chi ^2`$s and lead to values for $`a`$ that are in reasonable agreement: $`0.18(0.01)`$ and $`0.17(0.01)`$. Taken at face value, these extrapolations indicate that the uniform scenarios are not correct. However, we believe that regardless of what the correct scenario is, finite size effects are subtle for class $`2`$ events. To justify this, let us look again at the data.

In Figure 3 we show the fraction of class $`2`$ events as a function of $`1/L`$ (top curve). Because of the positive curvature of this data, it seems likely that this class survives in the thermodynamic limit, confirming the conclusion drawn from the fits.

But as argued in HoudayerMartin00b , it is difficult to create sponges in finite dimensions when $`L`$ is smaller than a typical “cohesion” length $`\mathrm{}_c`$ that may be substantially bigger than one lattice spacing, especially if the dimension is not large. This effect should be much more severe for small $`v`$; indeed in that limit, creating a spongy yet connected cluster requires the sponge to be very “thin”, most of its sites being at its surface. The energy of such a sponge is likely to be high, and so our procedure for generating large scale excitations should not pick them up. We have explored the validity of this point of view by considering the fraction of class $`2`$ events subject to a further selection in $`v`$. The three curves of Figure 3 are associated with the events satisfying $`v>0`$, $`v>0.2`$, and $`v>0.25`$ (from top to bottom). We see that the fraction of these last events cannot be extrapolated to positive values, as confirmed by detailed fits. In fact, when we look at Figure 2, we can now reasonably assume that the curves all go to zero when $`L`$ grows, but the smaller $`v`$ is, the later the asymptotic behavior sets in. More convincing evidence of this is beyond the scope of our data, but we hope to have made the case that our results are not incompatible with class $`2`$ events disappearing altogether in the large $`L`$ limit.

In conclusion, great care is needed when performing extrapolations to large $`L`$ because finite size effects are subtle when $`v`$ is small. Therefore, in what follows, we will focus exclusively on the region near $`v=1/2`$ ($`q=0`$). If we are to provide any evidence that there is a growing length scale, it is only at $`q0`$ that such evidence can be solid.

## 5 Geometrical properties

We now move on to geometrical properties of low-energy system-size excitations: link overlaps, correlation functions, window overlaps, etc… From these measurements, we hope to test whether or not there is a growing intrinsic scale $`\mathrm{}_c`$, and to thereby weight the balance in favor of some of the scenarios. Since spin glasses have resisted simple solutions, we do not expect the reader to find that any scenario comes out a clear winner but we do hope to convince her or him that the clusters coarsen slignificantly as $`L`$ grows. Whether or not this coarsening continues to infinite sizes may be of fundamental importance; however, if it turns out that the growth is very slow, it should be of limited experimental relevance.

### 5.1 Mean link overlaps

We begin by considering the link overlap between the ground state and an excited state:

$$q_l=\frac{1}{3L^3}\underset{i,\widehat{\mu }}{}S^0(i)S^1(i)S^0(i+\widehat{\mu })S^1(i+\widehat{\mu })$$
(6)
We will take the surface $`S`$ of the corresponding cluster to be the number of links that connect the cluster to its complement. Then we have $`q_l=12S/3L^3`$. One of the main issues in this section is whether $`q_l1`$ at large $`L`$, that is we want to know whether the system-size clusters have a surface to volume ratio that goes to zero at large $`L`$.

In the SK model, $`q_l`$ is a deterministic function of the spin overlap $`q`$ in the thermodynamic limit: $`q_l=q^2`$. An analogous deterministic relation will be satisfied in any scenario that is homogeneous on the length scale $`L`$. We can see whether this is the case in our system by considering the probability distribution of $`q_l`$ at fixed $`q`$; Figure 4 shows this distribution for different $`L`$ values when $`0<q<0.1`$. (Note that for such small values of $`q`$, essentially all the excitations are sponge-like, i.e., fall into class $`1`$ except for the smallest $`L`$s, and so a nearly identical plot is obtained if one restricts oneself to class $`1`$ events.) Clearly the distributions are becoming more narrow with increasing $`L`$ while drifting to the right. So we will look at both the mean and variance of these distributions.

In the uniform convergence scenarios the mean of these curves should settle at a $`q_l<1`$ as $`L\mathrm{}`$ and so the drift is a finite size effect. On the contrary, in the fat sponge and fractal scenarios, the limiting $`q_l`$ is equal to $`1`$ and the drift is the signal that $`\mathrm{}_c`$ is increasing with $`L`$. (In the hierarchical sponge scenario, $`q_l`$ should again converge to a value strictly smaller than $`1`$.)

In geometrical terms, having $`q_l1`$ means that the surface to volume ratios of the clusters go to zero at large $`L`$. Such a property was referred to as TNT in KrzakalaMartin00  as the link overlap $`q_l`$ then has a trivial probability distribution PalassiniYoung00a  (it is infinitely narrow and localized at $`q_l=1`$) while the distribution of the spin overlap $`q`$ remains non-trivial.

We can try to discriminate between such different scenarios by performing fits, but it is necessary to parametrize the dependence of the mean on $`L`$ for each scenario. Suppose that the asymptotic behavior of a quantity is $`L^\alpha `$; then we postulate that the finite size effects are multiplicative, with a finite size correction given by a function $`f(1/L)`$ where the argument is simply the ratio of the two scales of the problem, i.e., the lattice spacing and the lattice size. It is natural to assume that $`f`$ can be Taylor expanded for small arguments, so we shall parametrize all our finite size effects by polynomials in $`1/L`$.

In TNT scenarios, one expects $`q_l1`$ to go to zero as an inverse power of $`L`$, whereas in the scenarios with uniform convergence $`q_l1`$ goes to a strictly positive constant. We have performed fits for these two types of scaling behavior. (We have also considered the possibility that $`q_l1`$ vanishes as an inverse power of the logarithm of $`L`$, but the results are not convincing.) Consider first the fits having two free parameters. There is a linear fit in $`1/L`$, and a pure power fit, $`q_l1=a/L^\gamma `$, as shown in figure 5. We do not include the $`L=4`$ data when fitting, and obtain $`\chi ^2`$s of $`67`$ and $`19.5`$ for the two fits. (If instead we do leave the point at $`L=4`$, the $`\chi ^2`$s are increased to $`149`$ and $`49`$.) It seems plausible that we need to allow for more parameters and finite size corrections. So we allow now for three fitting parameters. The new $`\chi ^2`$s are $`7.5`$ and $`6.3`$. This same pattern is repeated when one goes on to $`4`$ free parameters. Certainly the case of a power law in $`L`$ leads to the best fits and so is favored by the data. However, this advantage is only significant for the two parameter fits. (Note that when repeating all the fits after restricting the events to belong the sponge class, we find similar results.) Since it is quite possible that our parametrizations do not capture correctly the finite size effects, we cannot rule out the scenarios where $`q_l`$ does not go to $`1`$. Even so, it is worrisome that the asymptotic $`q_l`$ values predicted by such scenarios drift with the number of parameters in the fits: we obtain $`q_l(L=\mathrm{})=.68`$, $`.72`$, and $`.75`$ for the fits with $`2`$, $`3`$, and $`4`$ parameters.

To have a completely convincing test, we would need to have a range in $`L`$ where only one of the fits gave $`\chi ^2`$s that were close to the theoretically expected value. As can be seen in the figure, such a situation may not be so far: it might be enough to go to sizes up to $`L=16`$ to finally obtain a clear cut discrimination of the different scenarios. In the mean time, we shall simply say that the TNT scenarios are slightly preferred.

Regardless of the scenario favored by the reader, perhaps the most striking point made here is that $`q_l`$ undeniably increases for the currently accessible values of $`L`$, and that this is most simply interpreted by having $`\mathrm{}_c`$ growing with $`L`$. In models without geometry $`\mathrm{}_c`$ is small (for instance in the SK it is $`1`$) whereas it seems to be at least $`4`$ here even if we stick to the uniform convergence scenarios and identify $`\mathrm{}_c`$ with $`1/(1q_l)`$.

### 5.2 Variance of link overlaps

We come back now to the way the distribution of $`q_l`$ becomes narrow. If the lattice spacing is the only relevant scale as in the homogeneous sponge scenario, we can expect $`P(q_l)`$ to converge to a delta function following the central limit theorem scaling law:

$$(q_lq_l)^2CL^3$$
(7)
However the data very clearly shows that $`(q_lq_l)^2\times L^3`$ grows tremendously with $`L`$ and we see no way this can be compatible with finite size corrections to a constant asymptotic value. On the contrary, a fit to a power law looks sensible and we find that $`(q_lq_l)^2\times L^{1.1}`$ has no trend with $`L`$. This value for the exponent of the scaling of the variance of $`q_l`$ is not very different from the value found by Marinari and Parisi MarinariParisi00c  who extracted excitations in a very different way. This scaling suggests to us that there is an underlying length $`\mathrm{}_c`$ that diverges with $`L`$ and that the density of the cluster’s interface fluctuates on scales much larger than the lattice spacing. We also have measured the kurtosis of the distribution; we find that it does not decrease with $`L`$, showing explicitly that there is no central limit behavior. Overall, we feel that these results rule out the homogeneous sponge scenario for which the central limit theorem should hold. However we have nothing to say concerning the heterogeneous sponge scenario which can very well violate the central limit theorem.

### 5.3 Spin overlap correlation functions

Now we focus on the two-point correlation function defined by:

$$G(L,r)=S^0(i)S^1(i)S^0(i+r)S^1(i+r)$$
(8)
We present in figure 6 this correlation function, as usual for events with $`0<q<0.1`$. We see again that finite size effects are very severe, making it quite difficult to guess what is the limiting curve when $`L\mathrm{}`$. In the regular scenarios, one expects $`G(r,L)`$ to converge to a limiting curve with for instance $`1/L`$ corrections, just as we saw for the mean link overlaps. For the TNT scenarios, the limiting curve is $`G(r,L\mathrm{})=1`$, and we can follow the discussion of finite size effects for $`q_l`$ to motivate those of $`G(r,L)`$. (Note in particular that $`G(1,L)=q_l`$.) Since $`G(r,L)`$ probes properties at distance $`r`$, we will postulate in the fat sponge scenario that the finite size effects can be parametrized through

$$G(r,L)=1A(r)L^\delta (1+\frac{B_1(r)}{L}+\mathrm{})$$
(9)
in the region $`r\mathrm{}_c`$, while $`G(r,L)`$ should be constant and equal to $`q^2`$ for $`r\mathrm{}_c`$.

We have performed these fits. Since it was possible to fit reasonably well $`G(1,L)`$ to a constant different from $`1`$ plus $`1/L`$ corrections, (cf. the previous section), it will be no surprise to find out that this remains true of $`G(2,L)`$. The difference between the $`r=1`$ and $`r=2`$ cases is that now the quality of the fits with $`G(r,L=\mathrm{})`$ equal to $`1`$ or less than $`1`$ are similar, no scenario is favored. We have also tried to see whether a simple scaling law of the type $`G(r,l)=G(r/L^\delta )`$ might hold, but given the small useful range in $`r`$, no solid conclusion can be drawn. However, there should be a large usable range in $`r`$ if we assume $`G(r,l)=G(r/L)`$ as in the fractal scenario. When we try that rescaling the data do not superpose at all: the large $`L`$ curves that were above are now far below the others. There seems no way to avoid the conclusion that the correlation function data unambiguously rule out fractal scenario.

### 5.4 Window overlaps

Now consider the probability $`P(M,L)`$ that a cubic box of size $`M`$ is entirely contained either in the cluster or in its complement. $`P(M,L)`$ has been studied in previous work, in particular by Palassini and Young PalassiniYoung99a . Figure 7 gives these probabilities for our excitations at $`M=2`$ and $`3`$ for the window $`0<q<0.1`$. In any TNT scenario and in particular in the fat sponge scenario, $`P(M,L)1`$ as $`L\mathrm{}`$ at any fixed $`M`$. We have performed the fits to this quantity in the same way as previously. The mean field picture is associated with polynomial fits in $`1/L`$, while in the fat sponge scenario we take

$$P(M,L)=1A(M)L^\delta (1+\frac{B_1(M)}{L}+\mathrm{})$$
(10)
For $`M=2`$, we find the following $`\chi ^2`$s for these two pictures: $`311`$ and $`10.6`$ for two free parameters, $`14.4`$ and $`7.5`$ for three free parameters, and $`8.4`$ and $`7.2`$ for four free parameters. (The same pattern transpires if we include the $`L=4`$ data.) So here we seem to find more convincing evidence that the fat sponge scenario is significantly favored over the uniform convergence scenarios. The same study at $`M=3`$ leads to the same conclusion, i.e., that the fat sponge scenario is favored.

### 5.5 Tube observables

In the context of the fat sponge scenario with a length scale $`\mathrm{}_c`$, we may expect $`P(M,L)`$ to be a function only of the reduced variable $`M/\mathrm{}_c(L)`$. Unfortunately, the usable range in $`M`$ is small (the data at $`M=4`$ is not exploitable), and so the scaling cannot be reliably tested. This leads us to consider other observables that may have a larger useful range.

Rather than increase the size of the window in all three directions, we increase it in just one direction; because of this, we refer to these windows as “tubes”. We have investigated four different types of cross-sections for these tubes, as displayed in figure 8. Essentially, we use these objects to probe the size of holes in the clusters as follows. Given a tube type and a lattice site, we ask for the length of the longest tube along the $`x`$ axis that passes through this site and is entirely contained in the cluster (or in its complement). We compute this length for each site of the lattice and for the four different tube types. Then we extract the mean length found, averaged over lattice sites and over the disorder.

In figure 9 we see that the mean tube length increases very clearly as $`L`$ increases, even for events with $`0<q<0.1`$.

Within the fat sponge scenario, this is simply the reflection of the growth of $`\mathrm{}_c`$ with $`L`$. Is such a behavior compatible with the heterogeneous sponge scenario (having uniform convergence)? If the distribution of hole sizes is broad in heterogeneous sponges, the first moment may no longer be finite, leading to a divergence in the mean tube length. It is thus necessary to look directly at the probability distribution of these lengths. In Figure 10 we show the distribution of the tube lengths for tubes of type $`2`$. (Tubes of type $`1`$ show a much more severe drift with $`L`$, and the other tube types are quite similar to the one displayed.) We see that as $`L`$ increases, the curves shift to the right while the values at small $`l`$ decrease. In the uniform convergence scenarios, these distributions have a limiting shape, while in the fat sponge scenario for instance, the values at any finite $`l`$ will go to zero. We have fitted the first three values ($`l=0,1,2`$) in the figure as we have previously, i.e., to a finite or null asymptote, using the data with $`L>5`$. The fits at $`l=0`$ have the same kind of behavior we saw before, i.e, the best fit is the extrapolation to zero, but the pure $`1/L`$ fit should not be excluded. (For two parameter fits, the $`\chi ^2`$s are $`27`$ for a non-zero extrapolation and $`8.6`$ for the zero extrapolation; for the $`3`$ and $`4`$ parameter fits the zero extrapolations remain the best but are only marginally better than the ones for non-zero extrapolation.) For $`l=1`$ and $`2`$, there is no trend, but the extrapolated values are always very small, being below $`0.03`$ and often ten times smaller than that. This result could have been guessed at from looking at Figure 10. Naturally, given the form of these histograms, it is much too difficult to extrapolate the data for still larger values of $`l`$, but nevertheless our conclusion is that the data do not support a point-wise convergence to a non-trivial distribution. At face value, this means that the uniform convergence scenarios are incorrect.

We can also look at the tail of the distribution. If $`L\mathrm{}_c`$, we can expect the tail of the histogram to fall to zero rather rapidly with $`L`$. In practice though, we find that the histogram at $`l=L`$ grows with $`L`$ for the tube types $`3`$ and $`4`$ for all values explored, while it first grows then decreases very slowly for type $`2`$ tubes. At the very least, this is totally unexpected within the uniform convergence scenarios. Because of this, we have investigated the probability that a cluster has somewhere a tube of maximum length (that is of length $`L`$, the tube spanning the whole system along the $`x`$ direction). We find that for tubes of the first type, $`99\%`$ of the instances have at least one spanning tube, and that this ratio does not seem to depend on $`L`$. For the other tube types, we have collected the ratios in table 2. One sees that the ratios all increase with $`L`$. If we take into account the data for tubes of the first type, we are lead to extrapolate these ratios to finite quantities, distinct from $`0`$ and $`1`$. This goes strongly against the idea that the clusters are homogeneous beyond $`\mathrm{}_cL`$. Indeed, in such a picture, the probability of having a tube span the whole system decreases exponentially. Here we need the decrease to be power-like so it can be compensated by the $`L^2`$ places where the tube can be located. Thus we are driven to a rather heterogeneous picture (in the sense discussed in Section 3.2) where large fluctuations on scales larger than $`\mathrm{}_c`$ are possible, being suppressed by powers of $`L`$ rather than exponentially in $`L/\mathrm{}_c`$.

## 6 Conclusions

The only truely compelling property that emerges from this study is that the clusters coarsen as $`L`$ grows. Naturally, this can be interpreted within the uniform scenarios as being a finite size effect; the issue is whether this is believable given the size of this effect. In essentially all the measurements we have made, the fat sponge type picture was favored over the homogeneous sponge scenario by a detailed $`\chi ^2`$ analysis. Furthermore as we saw from the tube observables, heterogeneities are large, so a scenario that is homogeneous on the scale of the lattice spacing seems ruled out. (We also saw for instance from the measurements of $`G(r,L)`$ that the scenarios where $`L`$ is the only relevant scale are not supported by the data.) So our conclusion is mainly that the scenarios at the end of the spectrum (homogenous regular sponge and fractal or droplet-like model) are no longer compelling. We are thus left with uniform convergence scenarios having large heterogeneities, and scenarios with at least one scale $`\mathrm{}_c`$ growing with $`L`$. In the first case, we have large finite size corrections because of the heterogenities, while in the second we can realize the TNT scenario where $`q_l`$ has a trivial distribution in the thermodynamic limit.

The difficulty of the problem should be all the more evident from the focus of our study: essentially all of our measurements were for the region $`q0`$. Obviously there is room for much more heterogeneities when $`q`$ is larger. Nevertheless we hope to have shed new light on the problem of replica symmetry breaking in finite dimensional systems. And, as we have pointed out before, a convincing test of the major scenarios may not be so far off: we believe it is enough to go to slightly larger systems before the tests will become clear-cut to a vast majority.

Acknowledgments

We thank J.-P. Bouchaud and M. Mézard for very stimulating discussions and for their continuous encouragement. J.H acknowledges financial support from the Max Planck Institut, F.K. a fellowship from the MENRT, and O.C.M. support from the Institut Universitaire de France. The LPTMS is an Unité de Recherche de l’Université Paris XI associée au CNRS.


format: text

text:
# Reply to “Comment on: A Quantum Approach to Static Games of Complete Information” 11footnote 1Work supported in part by Istituto Nazionale di Fisica Nucleare, Sezione di Trieste, Italy

In a recent comment  S.C. Benjamin made some interesting remarks about the terminology, the postulates and the mathematical results of a new quantum scheme  proposed in order to solve the paradigmatic dilemma arising in a famous game ( Battle of the Sexes ) in the framework of the classical Theory of Games. In answering these remarks we take the opportunity of outlining some topical points of our work which we hold to be crucial for a better comprehension of our new approach to the Quantum Theory of Games, and which differs from the other proposed versions  and .

As regards terminology, we think that the choice of calling strategies the quantum states instead of the operators used to manipulate them, is very natural and quite consistent with the spirit of the classical game theory. In fact, in the classical framework of the theory, starting a game each player has at his disposal an ensemble of strategies $`𝒮`$ which is no more than a set ( i.e. a collection of objects, equipped with the only concept of “belonging to” represented by the symbol $``$ ). In pursuing the aim of finding new results beyond the ones which are predicted by the classical theory, we felt as a natural request adding an Hilbert space structure to this strategic set $`𝒮`$, in order to be allowed to use the methods of Quantum Mechanics. As a consequence the pure strategies of the classical framework are now represented by an orthonormal and complete set of vectors, and their linear combinations represent the mixed ( i.e. probabilistic ) strategies, the probabilities being quantified by the squared modula of the complex coefficients of the combination. Clearly this strategic quantum space exhibits a richer structure, since it contains not only the subset of the factorizable states, which correspond to the pure and mixed strategies of the classical theory, but also non-factorizable states, which we hold to constitute the real powerful tool enabling the players to solve the unescapable dilemma of the classical theory. On the other hand, in our terminology the act of choosing a move ( which for Eisert et al.  corresponds to a strategy ) means choosing in a given set of operators the one to be applied to the quantum strategies, and does not belong to the strategic space, pertaining instead to the cathegory of tactics which can be used in that space.

The second issue faced in the comment concerns the choice of the tactics set, i.e. the set of local operations each player has at his disposal in order to manipulate his own starting strategy. Our main purpose was consisting in choosing the smallest set of operations able to reproduce, when applied to a factorizable couple of strategies, the results of the classical Theory of Games. In fact we have been able to show that, limiting ourselves to a probabilistic choice between operators $`I`$ and $`\sigma _x`$, was sufficient to reach our goal. On the other hand, our belief was that new results should have come out from the richer structure of the strategic space, i.e. from taking into account entangled couple of strategies, and in fact it happened. Obviously the class of allowed manipulations could be enlarged, but in our paper we did not take care of this possibility since our minimal choice was enough to reproduce intact the classical results when considering only factorizable strategies and to obtain the disappearance of the dilemma when resorting to entangled strategies. Therefore we do not reject the possibility of improving our scheme of the Quantum Theory of Games ( for static games and complete information ) by extending the set of tactics to include other quantum mechanical manipulations, provided that the results of the classical behaviour are always reproduced.

The third remark, concerning the impossibility of solving the dilemma even when resorting to the entangled strategy $`|\psi =1/\sqrt{2}(|OO+|TT)`$ is the most important one. The author of the comment claims that the dilemma persists since the players cannot decide between manipulating the initial strategy $`(p^{}=0,q^{}=0)`$ and leaving it unchanged $`(p^{}=1,q^{}=1)`$. We maintain that the claim is not correct, since both the choices will eventually lead to the same final strategy, which is exactly the same the players possess from the beginning of the game. It is therefore apparent, on the ground of reasonableness, that both players, knowing this fact, will decide to do nothing on their strategies. Both players are in fact restrained from manipulating their own strategy since there exist at least one possibility of obtaining the wrong result ( this will happen for example if Alice decides to choose $`p^{}=0`$ while Bob chooses $`q^{}=1`$ ). The choice wheter manipulating or not the compound strategy $`|\psi `$ is not a matter of cost ( in fact doing nothing could be considered cheaper than doing something, in terms of resources needed to operate on the strategies ), but instead it represents the most rational behaviour of the two players. Which player will in fact decide to refuse a certain gain, without prospects of a better gain and running the risk of incurring a loss? The hypothesis of Complete Information and the supposed rational way of thinking of the players forces us to affirm again that our quantum approach to Battle of the Sexes game is able to solve the dilemma of the existence of two equally attractive Nash strategies which is present in its classical version.


text:
# Particle Rapidity Density Saturation in Heavy Ion Collisions and the Dual String Model

## 1 Introduction

Recently, experimental  and theoretical  papers have addressed the question of the dependence of measurable quantities (charged particle density, transverse energy, $`J/\psi `$ production rate) on the number $`N_{\text{part}}`$ of participant nucleons in high energy heavy ion collisions. That information, as stressed in , as well as in , is extremely important as it allows for a better understanding of the initial conditions in the evolution of newly created dense matter and provides the information for discriminating among different models.

In the analysis of the data of  made in  it was emphasised the role of the dependence of the particle rapidity density, $`dN/dy`$, normalised to the number of pairs of participants, and two models were considered.

The HIJING Monte Carlo model  contains soft and semi-hard interactions in an unitarised form, the $`p_T`$ threshold for jet production, $`p_0`$, being independent of energy and atomic mass number $`A`$. As in the model there is a growing number of hard collisions, growing faster than $`N_{\text{part}}`$, the quantity

$$\mathrm{\Phi }(N_{\text{part}},y,\sqrt{s})\frac{1}{\frac{1}{2}N_{\text{part}}}\frac{dN}{dy}$$
(1)
is an increasing function of $`N_{\text{part}}`$, or

$$\frac{\mathrm{\Phi }}{N_{\text{part}}}>0.$$
(2)
The EKRT model , on the other hand, relates the hard physics threshold $`p_s`$ to a saturation criterion : the number of partons multiplied by their effective area ($`1/p_T^2`$) must be less than the transverse area of interaction. The saturation transverse momentum $`p_s`$, in contrast to the parameter $`p_0`$ of the previous model, is a growing function of $`\sqrt{s}`$ and $`A`$. The assumption that physics is controlled by $`p_T=p_s`$ leads to the result that $`\mathrm{\Phi }`$ is a decreasing function of $`N_{\text{part}}`$,

$$\frac{\mathrm{\Phi }}{N_{\text{part}}}<0.$$
(3)
In Fig. 1, taken from , we show the predictions for the two models, histogram for HIJING and dot-dashed line for EKRT.

The Dual String Model (DSM) with string fusion was developed in . Concerning this model two remarks can be made:

(i) There exist two components, a valence-valence component, proportional to $`N_{\text{part}}`$, and a sea-sea (including gluons) component which grows faster than $`N_{\text{part}}`$ and corresponds to multiple scattering. We have a structure somewhat similar to the HIJING model. Without fusion DSM gives an increase of $`\mathrm{\Phi }`$ as, roughly, $`N_{\text{part}}^{1/3}`$.

(ii) With fusion, DSM leads to saturation of $`\mathrm{\Phi }`$ as $`N_{\text{part}}`$ increases, not very different from what is obtained in the EKRT model (see, in particular, ).

In conclusion, in DSM with fusion,

$$\frac{\mathrm{\Phi }}{N_{\text{part}}}>0,$$
(4)
as in HIJING, and, as $`N_{\text{part}}`$ becomes larger and larger,

$$\frac{\mathrm{\Phi }}{N_{\text{part}}}\underset{N_{\text{part}}\mathrm{}}{\overset{}{}}0,$$
(5)
The $`N_{\text{part}}`$ dependence of $`\mathrm{\Phi }`$ in DSM with fusion is also shown in Fig. 1 (solid lines). The parameters used are precisely those used in  to describe NA49 and PHOBOS data .

## 2 DSM and particle densities

DSM is essentially the Dual Parton Model  with the inclusion of strings . The strings may interact by fusing  in the transverse plane of interaction and eventually one may reach a situation of percolation with the formation of extended regions of colour freedom, with the features of the expected Quark-Gluon Plasma.

In the Dual Parton Model hadrons are considered as made up of constituents quarks (valence and sea quarks) and gluons. Two basic diagrams contribute to particle production (see ). The valence-valence diagram corresponds to single inelastic scattering and the wounded nucleon model . The sea-sea diagram (including gluons) corresponds to the additional inelastic multiple scattering contributions. These contributions may be internal, parton multiple scattering within the original valence-valence contribution, or external, involving other nucleons.

If $`h`$ is the height of the valence-valence plateau, $`\alpha h`$ the height of the sea-sea plateau, $`2k`$ the average number of strings produced in a nucleon-nucleon collision we can write  for the (pseudo-)rapidity particle density

$$\frac{dN}{dy}|_{N_AN_A}=N_A\left[2+(2k1)\alpha \right]h+(\nu _{_{N_A}}N_A)2k\alpha h,$$
(6)
where $`N_A`$ is the number of pairs of participant nucleons

$$N_A=\frac{1}{2}N_{\text{part}},$$
(7)
and $`\nu _{_{N_A}}`$ is the average number of nucleon-nucleon collisions. From elementary multiple scattering arguments  we have

$$\nu _{_{N_A}}=N_A^{4/3}$$
(8)
One should notice that the number of nucleon-nucleon collisions is $`N_A+(\nu _{_{N_A}}N_A)=\nu _{_{N_A}}`$ and the number of strings is $`N_A\left[2+2(k1)\right]+(\nu _{_{N_A}}N_A)2k=2k\nu _{_{N_A}}`$.

For $`N_A=1`$, nucleon-nucleon collision, Eq. (6) gives

$$\frac{dN}{dy}|_{pp}=\left[2+2(k1)\alpha \right]h.$$
(9)
Assuming that $`h`$ and $`\alpha `$ are energy independent (constant plateaus) the energy dependence of $`dN/dy|_{pp}`$ fixes the energy dependence of $`k`$.

From Eq.s (1), (6), (7), (8) and (9) we can write

$$\mathrm{\Phi }(N_A,\sqrt{s},y)=\varphi (\sqrt{s},y)+(N_A^{1/3}1)2k\alpha h$$
(10)
with

$$\varphi (\sqrt{s},y)\frac{dN}{dy}|_{pp}.$$
(11)
The number of strings coming from nucleon multiple scattering —the second term in Eq. (6)—is $`N_A(N_A^{1/3}1)2k`$ and they occupy the transverse interaction area $`S_{_{N_A}}`$, which, for central collisions, is approximately given by

$$S_{_{N_A}}\pi \left(1.14N_A^{1/3}\right)^2,$$
(12)
such that the dimensionless transverse density parameter $`\eta `$ is

$$\eta =\left(\frac{r_s}{1.14}\right)^22kN_A^{1/3}(N_A^{1/3}1),$$
(13)
where $`r_s0.2`$ fm is the string transverse section radius. Note that $`\eta `$ increases with $`N_A`$ and $`\sqrt{s}`$.

When fusion occurs, i.e., when strings cluster in the transverse plane, Eq. (10) becomes

$$\mathrm{\Phi }(N_A,\sqrt{s},y)=\varphi (\sqrt{s},y)+F(\eta )(N_A^{1/3}1)2k\alpha h,$$
(14)
where $`F(\eta )`$ is the particle production reduction factor ,

$$F(\eta )\sqrt{\frac{1e^\eta }{\eta }}.$$
(15)
We shall next discuss the $`N_A`$, $`\sqrt{s}`$ and $`y`$ dependence of $`\mathrm{\Phi }`$, Eq. (14).

For the $`N_A`$ dependence we have

$$\frac{\mathrm{\Phi }}{N_A^{1/3}}=2k\alpha h\frac{}{N_A^{1/3}}\left[F(\eta )(N_A^{1/3}1)\right],$$
(16)
and, making use of the definition of $`\eta `$, Eq. (13),

$$\frac{\mathrm{\Phi }}{N_A^{1/3}}=\frac{1.14}{r_s}\sqrt{2k}\alpha h\frac{}{N_A^{1/3}}\left[(1e^\eta )\frac{N_A^{1/3}1}{N_A^{1/3}}\right]^{1/2},$$
(17)
As both $`(1e^\eta )`$ and $`(N_A^{1/3}1)/N_A^{1/3}`$ are increasing functions of $`N_A`$, becoming constant as $`N_A\mathrm{}`$,

$$\frac{\mathrm{\Phi }}{N_A}>0\text{with}\frac{\mathrm{\Phi }}{N_A}0\text{as}N_A\mathrm{}.$$
(18)
These are the results announced in the Introduction, Eq.s (4) and (5).

The DSM with fusion thus predicts saturation of the particle rapidity densities per participant pair of nucleons, $`\mathrm{\Phi }`$, as $`N_A`$ increases.

In Fig 2 we compare our model Eq. (14) with the very recent results  of WA98 Collaboration on central Pb+Pb collisions at the CERN SPS. For large values of $`N_{\text{part}}`$ the saturation is very clearly seen, Fig. 2a, while for small values of $`N_{\text{part}}`$ the rise of particle density with $`N_{\text{part}}`$, Fig. 2b, is well described. The values used for the parameters were $`h=0.77`$ and $`\alpha =0.11`$, and for the $`pp`$ density we used the same value as WA98, from . Note that the parameters here have slightly different values in comparison to the ones used in . This is not surprising as the WA98 data are not compatible with NA49 data as given by PHOBOS .

Concerning the energy dependence of Eq. (14), if the energy is high enough

$$\varphi (\sqrt{s},y)\frac{dN}{dy}|_{pp}2k\alpha h,$$
(19)
and

$$\mathrm{\Phi }(N_A,\sqrt{s},y)/\varphi (\sqrt{s},y)=1+F(\eta )(N_A^{1/3}1).$$
(20)
As $`F(\eta )`$ goes to zero as $`\sqrt{s}`$ increases we obtain the prediction that asymptotically the particle density per participant, for a fixed number of participants, approaches the nucleon-nucleon density and this approach is controlled by the function $`F(\eta )`$, Eq. (15). This means that asymptotically heavy ion collisions, with respect to particle densities, become similar to nucleon-nucleon collisions. This is a consequence of the increasing role played by string fusion.

In Fig. 3 we present our prediction for the dependence of the ratio (20) on the energy for fixed values of $`N_{\text{part}}`$.

Regarding the (pseudo-)rapidity dependence of $`\mathrm{\Phi }`$, Eq. (14), even without a more specific model, we can say that the valence-valence contribution dominates the large centre-of-mass $`|y|`$ region, as most of rapidity is taken by the valence diquarks. In the fragmentation region we expect the particle density per participant nucleon to be equal to the nucleon-nucleon density,

$$\mathrm{\Phi }(N_A,\sqrt{s},y_{\text{fragm}})\varphi (\sqrt{s},y_{\text{fragm}}).$$
(21)
The sea-sea contributions are naturally shorter and more central in rapidity.

## 3 Conclusions

The DSM is a model with two components, the valence-valence component and the sea-sea component, the sea-sea component increasing its importance with energy and number of participants. This is somewhat similar to the HIJING Monte Carlo model, with soft and hard components.

On the other hand, with fusion the DSM behaves, for large $`N_A`$, similarly to the EKRT model, but with strict saturation of the particle density per participant nucleon. However, in the original EKRT model the saturation criterion in the transverse plane is stronger than in case of fusion of strings. Here, saturation in the interaction area is asymptotic (when $`\eta \mathrm{}`$) while in the EKRT model it occurs, using the string language, when $`\eta (\pi r_s^2)/(\pi 1.14^2N_A^{2/3})(2kN_A(N_A^{1/3}1))=1`$. This causes the decrease of $`\mathrm{\Phi }`$ with $`N_A`$ in the EKRT original model.

Probably different explanations, such as the ones based on string fusion, parton saturation, parton shadowing, are in some sense dual and refer to the same underlying physics . What is becoming clear is that saturation of particle density puts strong constraints in models, and limits the rise of the (pseudo-)rapidity plateau at RHIC and LHC.

## Acknowledgements

R.U. gratefully acknowledges the financial support of the Funda o Ci ncia e Tecnologia via the “Sub-Programa Ciência e Tecnologia do $`2^o`$ Quadro Comunitário de Apoio.”


text:
# Combinatorial and algebraic structure in Orlik-Solomon algebrasrevised July 31, 2000

## 1 Introduction: <br>The Orlik-Solomon algebra of a matroid

Let $`G`$ be a simple matroid with ground set $`[n]:=\{1,\mathrm{},n\}`$. The Orlik-Solomon ($`OS`$) algebra of $`G`$ is defined as follows. Let $`=\mathrm{\Lambda }(e_1,\mathrm{},e_n)`$ be the graded exterior algebra on elements $`e_i`$ of degree one corresponding to the points of $`G`$. For simplicity we will assume the ground field is $``$. Except where noted, all of the results will hold for coefficients in an arbitrary commutative ring.

Define the linear mapping $`:^p^{p1}`$ by

$$(e_{i_1}\mathrm{}e_{i_p})=\underset{k=1}{\overset{p}{}}(1)^{k1}e_{i_1}\mathrm{}\widehat{e}_{i_k}\mathrm{}e_{i_p},$$

where $`\widehat{}`$ indicates an omitted factor.

If $`S=(i_1,\mathrm{},i_p)`$ is an ordered $`p`$-tuple we denote the product $`e_{i_1}\mathrm{}e_{i_p}`$ by $`e_S`$. Let $``$ denote the ideal of $``$ generated by $`\{e_S|S\text{is dependent}\}`$.

###### Definition 1.1

The Orlik-Solomon algebra $`𝒜=𝒜(G)`$ of $`G`$ is the quotient $`/`$.

Since $``$ is generated by homogeneous elements, both $``$ and $`𝒜`$ inherit gradings from $``$. We will denote the image of $`e_S`$ in $`𝒜`$ by $`a_S`$.

The $`OS`$ algebra has both combinatorial and topological significance, as demonstrated by these two results from . Recall that a projective realization of $`G`$ gives rise to a linear hyperplane arrangement. Throughout the paper $`A`$ will denote a hyperplane arrangement arising from a complex projective realization of $`G`$, and $`M`$ will denote the complement of $`A`$, $`M=^{\mathrm{}}_{HA}H`$.

###### Theorem 1.2

The $`OS`$ algebra $`𝒜(G)`$ is isomorphic to the cohomology algebra $`H^{}(M)`$.

The Whitney numbers of the second kind are defined in terms of the Möbius function $`\mu :L(G)`$ of the lattice of flats $`L(G)`$. Specifically,

$$w_p(G)=\underset{XL,\mathrm{rk}(X)=p}{}(1)^p\mu (0_L,X).$$

###### Theorem 1.3

The dimension of $`𝒜^p(G)`$ is equal to the $`p^{\mathrm{th}}`$ Whitney number $`w_p(G)`$ of $`G`$.

Theorem 1.2 motivates what is for us the main problem concerning $`OS`$ algebras: to classify $`𝒜(G)`$ up to isomorphism of graded algebras. This type of problem is more familiar in topology than combinatorics, but the classification in this instance will be purely matroidal. Theorem 1.3 provides one line along which a classification could proceed, that is to extract combinatorial features of the matroid $`G`$ from algebraic invariants of $`𝒜(G)`$. In this regard we note that there are many sets of matroids with identical Whitney numbers while, on the other hand, the betti numbers $`dim(𝒜^p(G))`$ in a sense take no account of the ring structure of $`𝒜(G)`$.

These observations set the tone for the exposition to follow. We will construct multiplicative invariants of $`𝒜(G)`$ and attempt to extract combinatorial structure from them. The most delicate of these are the resonance varieties, discussed in Section 2. In Section 3 we show how “stabilized” parallel connection and direct sum of matroids yield isomorphic $`OS`$ algebras. We also show that truncations of matroids with isomorphic $`OS`$ algebras will have the same property. We make sense of these results using the categories of pointed matroids and affine $`OS`$ algebras, indicating a framework for the eventual classification. In Section 4 we describe recent work relating the $`k`$-adic closure of $`𝒜(G)`$ to the “$`k`$-closure” of the matroid $`G`$.

We close this introduction by recalling the oldest multiplicative invariant of $`𝒜(G)`$, termed “the global invariant” $`\varphi _3`$ in . Consider the multiplication map

$$d:^1^2^3.$$

This linear map can be shown to be an invariant of $`𝒜(G)`$. The nullity of $`d`$ is denoted by $`\varphi _3(𝒜)`$. This quantity has a topological interpretation in terms of the fundamental group of the complement $`M`$. Indeed, the definition of $`\varphi _3`$ comes directly out of the study of the rational homotopy type of hyperplane complements . And of course $`\varphi _3(𝒜)`$ can be thought of as an invariant of the matroid $`G`$. But the following problem remains open, even for graphic matroids.

###### Problem 1.4

Give a combinatorial interpretation of $`\varphi _3(G)`$.

We will return to this problem in Section 4.

The reader is referred to  for background material on complex hyperplane arrangements and Orlik-Solomon algebras, and to  for matroid theory. Section 2 is largely based on , and much of Section 3 is a reformulation of part of . Section 4 is a brief report on work in progress; details and proofs will appear in  and .

## 2 Resonance varieties

To answer questions concerning generalized hypergeometric functions, we began studying the $`OS`$ algebra as a differential complex in , and then realized that our work could be used to define algebraic invariants .

Fix an element $`a_\lambda =_{i=1}^n\lambda _ia_i`$ in $`𝒜^1`$. Then left multiplication by $`a_\lambda `$ defines a map $`𝒜^p𝒜^{p+1}`$, which squares to zero. Thus we have a cochain complex

$$0𝒜^0\stackrel{a_\lambda }{}𝒜^1\stackrel{a_\lambda }{}\mathrm{}\stackrel{a_\lambda }{}𝒜^\mathrm{}1\stackrel{a_\lambda }{}𝒜^{\mathrm{}}0.$$

The cohomology of this complex determines a stratification of the parameter space $`^n`$. The $`p^{\mathrm{th}}`$ resonance variety of $`𝒜`$ is defined by

$$R_p(𝒜)=\{\lambda ^n|H^p(𝒜,a_\lambda )0\}.$$

It is shown in  that $`R_p(𝒜)`$, up to ambient linear isomorphism, is an invariant of $`𝒜`$.

Basic properties of resonance varieties follow from the main results of . Let $`\mathrm{\Delta }`$ denote the diagonal hyperplane $`_{i=1}^n\lambda _i=0.`$ Then

* $`0R_p(𝒜)`$ for $`0p\mathrm{}`$.
* $`R_0(𝒜)=\{0\}.`$
* $`R_p(𝒜)\mathrm{\Delta }`$ for all $`p`$.
* $`R_{\mathrm{}}(𝒜)R_\mathrm{}1(𝒜)`$.
* if $`G`$ is connected, then $`R_{\mathrm{}}(𝒜)=R_\mathrm{}1(𝒜)=\mathrm{\Delta }`$.
* $`R_p(𝒜)`$ is a proper subvariety of $`\mathrm{\Delta }`$ for $`0p\mathrm{}2`$.

Under some genericity conditions on $`\lambda `$, the cohomology $`H^{}(𝒜,a_\lambda )`$ is isomorphic to the cohomology of $`M`$ with coefficients in a rank-one complex local system $`_\lambda `$ with monodromy determined by $`\lambda `$. This local system cohomology plays a role in the definition of generalized (multivariate) hypergeometric integrals. In a sense made precise in recent work of D. Cohen and P. Orlik , the complex $`(𝒜,a_\lambda )`$ is the derivative at the identity of a cochain complex $`(𝒜,\mathrm{\Delta }_\lambda )`$ that computes the local system cohomology. The resonance variety $`R_p(A)`$ is then the tangent cone at the identity to the “jumping locus” for the local system cohomology, the set of local systems for which the cohomology $`H^p(M,_\lambda )`$ is non-vanishing. For $`p=1`$ the jumping locus for local system cohomology coincides with the character variety in $`(^{})^n`$ associated with the Alexander invariant of the fundamental group. For any $`p`$, a theorem of D. Arapura asserts that these jumping loci are subtori of $`(^{})^n`$, possibly translated by elements of finite order. This gives an indication of the proof of the following result, originally conjectured for $`p=1`$ in , proved in that special case in  and , and finally established for arbitrary $`p`$ in  and . See those papers for complete references.

###### Theorem 2.1

The resonance variety $`R_p(𝒜)`$ is a union of linear subspaces of $`^n`$.

By Theorem 2.1, $`R_p(𝒜)`$ can be thought of as a subspace arrangement, and as such, realizes a polymatroid $`\mathrm{𝑝𝑜𝑙𝑦}_p(𝒜)`$, which in essence records the dimension of the span of each subcollection of irreducible components of $`R_p(𝒜)`$. Because $`R_p(𝒜)`$ is invariant up to linear change of coordinates, the polymatroid $`\mathrm{𝑝𝑜𝑙𝑦}_p(𝒜)`$ is indeed an invariant of $`𝒜`$, powerful enough (at least for $`p=1`$) to distinguish $`OS`$ algebras of matroids which are almost identical in other respects .

The first cohomology $`H^1(𝒜,a_\lambda )`$ can be computed directly, yielding a description of $`R_1(𝒜)`$. The following lemma reduces the calculation to an analysis of elements of $`^2`$.

###### Lemma 2.2

$`\lambda R_1(𝒜)`$ if and only if $`e_\lambda `$ is one factor of a nonzero elementary tensor in $`^2`$.

Proof of this lemma and the results to follow can be found in .

Irreducible components of $`R_1(𝒜)`$ are contained in intersections of $`\mathrm{\Delta }`$ with hyperplanes $`H_X`$ defined by $`_{iX}\lambda _i=0`$, where $`X`$ runs over certain flats of $`G`$. The flats which occur in these intersections are determined by so-called “neighborly partitions” of $`G`$.

###### Definition 2.3

A neighborly partition of $`G`$ is a partition $`\mathrm{\Pi }`$ of $`[n]`$ such that $`|\pi X||X|1`$ for all blocks $`\pi \mathrm{\Pi }`$ and flats $`X`$ of rank two in $`L`$.

We say a flat $`X`$ is “multi-colored” if $`X`$ meets more than one block of $`\mathrm{\Pi }`$. Given a neighborly partition $`\mathrm{\Pi }`$ of a submatroid $`S[n]`$ of $`G`$, set

$$L_\mathrm{\Pi }=\mathrm{\Delta }\underset{iS}{}H_i\underset{X\mathrm{mc}(\mathrm{\Pi })}{}H_X,$$

where the last intersection runs over the set $`\mathrm{mc}(\mathrm{\Pi })`$ multi-colored rank-two flats of $`\mathrm{\Pi }`$. Note that $`H_i=\{\lambda ^n|\lambda _i=0\}`$. The support $`\mathrm{supp}(\lambda )`$ of $`\lambda `$ is $`\{i[n]|\lambda _i0\}`$, considered as a submatroid of $`G`$. Let $``$ denote the equivalence relation associated with $`\mathrm{\Pi }`$. Finally, for $`\tau ^2`$ write $`\tau =_{i<j}\tau _{ij}e_ie_j`$. Here then is a description of $`R_1(𝒜)`$, from , to which the reader is referred for the proof, examples and consequences.

###### Theorem 2.4

$`\lambda R_1(𝒜)`$ if and only if $`\mathrm{supp}(\lambda )`$ affords a neighborly partition $`\mathrm{\Pi }`$ such that (i) $`\lambda L_\mathrm{\Pi }`$, and (ii) there exists $`\mu L_\mathrm{\Pi }`$ not proportional to $`\lambda `$ such that $`(\lambda \mu )_{ij}=0`$ for every $`i<j`$ with $`ij`$ under $`\mathrm{\Pi }`$.

The second condition will be replaced with a simpler criterion below.

If $`X`$ is a flat of rank two with $`|X|3`$, then $`\mathrm{\Pi }=\{\{i\}|iX\}`$ is a neighborly partition of $`X`$, and $`L_\mathrm{\Pi }=\mathrm{\Delta }_{iX}H_i`$ has dimension $`|X|12`$. Thus condition (ii) is satisfied, and indeed $`L_\mathrm{\Pi }`$ is a component of $`R_1(𝒜)`$ . The components which arise in this way are called the local components of $`R_1(𝒜)`$. Here is a sample result from  showing how combinatorial structure may be extracted from $`R_1(𝒜)`$.

###### Corollary 2.5

Suppose every non-local component of $`R_1(𝒜)`$ has dimension two. Then $`R_1(𝒜)`$ determines the number of rank-two flats of $`G`$ of each cardinality. In particular, if $`G`$ has rank three, $`R_1(𝒜)`$ determines the Tutte polynomial of $`G`$.

D. Cohen informs us that he and J. Oxley have found examples for which the hypothesis fails. We will see in the next section that $`𝒜(G)`$ does not generally determine the Tutte polynomial of $`G`$ for matroids of high rank.

In  A. Libgober and S. Yuzvinsky base a study of the resonance variety $`R_1(𝒜)`$ on the Vinberg classification of Cartan matrices for affine Kac-Moody Lie algebras. Their approach yields substantial additional detail about $`R_1(𝒜)`$ and the associated neighborly partitions. We state some of their more general conclusions in the following theorem.

###### Theorem 2.6 ()

1. The irreducible components of $`R_1(𝒜)`$ are precisely the $`L_\mathrm{\Pi }`$ of dimension at least two.
2. If $`L_\mathrm{\Pi }`$ and $`L_\mathrm{\Pi }^{}`$ are two irreducible components of $`R_1(𝒜)`$, then $`L_\mathrm{\Pi }L_\mathrm{\Pi }^{}=\{0\}`$.
3. For any component $`L_\mathrm{\Pi }`$ of $`R_1(𝒜)`$, each multi-colored flat of $`G`$ meets every block of $`\mathrm{\Pi }`$.

Theorem 2.6(i) effectively replaces condition (ii) of Theorem 2.4 with the much simpler requirement $`dim(L_\mathrm{\Pi })2`$. Theorem 2.1 for $`p=1`$ is an immediate corollary.

Matroids of rank greater than two which support neighborly partitions $`\mathrm{\Pi }`$ for which $`L_\mathrm{\Pi }`$ has dimension at least two are quite rare. Some examples appear in . The classification theory used in  imposes some restrictions, and also yields a method of constructing examples as a kind of inverse problem. The first part of the following problem is solved in some special cases in .

###### Problem 2.7

1. Characterize those matroids which support neighborly partitions $`\mathrm{\Pi }`$ satisfying $`dim(L_\mathrm{\Pi })2`$.
2. Describe the polymatroid $`\mathrm{𝑝𝑜𝑙𝑦}_1(G)`$ associated with the arrangement of subspaces $`\{L_\mathrm{\Pi }|\mathrm{\Pi }\text{is neighborly and}dim(L_\pi )2\}`$.

Libgober and Yuzvinsky  also uncover a connection between non-local components of $`R_1(𝒜)`$, for arrangements of rank three, and pencils of curves $`P^2P^1`$ which include the arrangement in their singular locus. The existence of such pencils imposes further restrictions on the structure of matroids supporting nontrivial ($`dim(L_\pi )2`$) neighborly partitions. In addition, these pencils of curves bear a relationship to the $`K(\pi ,1)`$ problem for complex hyperplane arrangements, and were studied in that vein in . So a solution to Problem 2.7(i) might have some implications for the $`K(\pi ,1)`$ problem .

In another direction, D. Matei and A. Suciu  discovered deep connections between the resonance varieties of $`𝒜(G)_p`$ and the structure of the second nilpotent quotient of the fundamental group $`\pi _1(M)`$. This work leads to some other interesting open questions. We briefly summarize.

Write $`R_1(𝒜,_p)`$ for the first resonance variety of $`𝒜(G)_p`$, and let

$$R_{1,d}(𝒜,_p)=\{\lambda R_1(𝒜,_p)|dimH^1(𝒜_p,a_\lambda )d\}.$$

These are subvarieties of $`(_p)^n`$, easily seen to be homogeneous. Let $`\widehat{R}_{1,d}(𝒜,_p)`$ denote the projective image of $`R_{1,d}(𝒜,_p)`$. Finally, let $`\pi =\pi ^1\pi ^2\pi ^3\mathrm{}`$ denote the descending central series of $`\pi =\pi _1(M)`$, and $`\mathrm{\Gamma }=\pi /\pi ^3`$ the second nilpotent quotient. Let $`\nu _{p,d}`$ denote the number of normal subgroups $`K`$ of $`\mathrm{\Gamma }`$ of index $`p`$, such that the abelianization of $`\mathrm{\Gamma }/K`$ has $`p`$-torsion of rank $`d`$.

###### Theorem 2.8 ()

$$\nu _{p,d}=\mathrm{}\left(\widehat{R}_{1,d}(𝒜,_p)\widehat{R}_{1,d+1}(𝒜,_p)\right)$$

The quantity on the right-hand side is also an invariant of $`𝒜(G)`$.

The proof uses a relationship between the resonance varieties and the Alexander invariant of the fundamental group, similar to the observations used to prove Theorem 2.1 in . In this case, the (linearized) Alexander matrix (mod $`p`$) is used to count normal subgroups of index $`p`$ in the second nilpotent quotient of $`\pi _1(M)`$, on one hand, and to define the resonance variety of $`𝒜(G)_p`$ on the other.

Theorem 2.8 leads to the study of resonance varieties of $`OS`$ algebras over finite fields. Because the variety $`R_1(𝒜)`$ is defined over $``$, we can reduce mod $`p`$. But there are matroids $`G`$ which have “exceptional primes” $`p`$, for which the reduction $`R_1(𝒜)_p`$ does not coincide with $`R_1(𝒜,_p)`$. The basic results of this section, from , will hold over an arbitrary ground field, but the techniques of  and , for instance, and thus Theorems 2.1 and 2.6, require complex coefficients. In  the authors give examples of matroids for which

1. $`R_1(𝒜,_p)`$ has non-local components while $`R_1(𝒜)`$ has none.
2. $`R_1(𝒜,_p)`$ has a non-local components of dimension greater than two, while all non-local components of $`R_1(𝒜)`$ are $`2`$-dimensional.
3. $`R_{1,d}(𝒜,_p)`$ has components which are not $`(d+1)`$-dimensional. By contrast, the components of the analogous variety $`R_{1,d}(𝒜)`$ over $``$ always have dimension $`d+1`$ .

This suggests a variation of Problem 2.7, suggested by A. Suciu.

###### Problem 2.9

Given a matroid $`G`$, determine the exceptional primes for $`G`$, that is, the primes $`p`$ for which $`_1(𝒜,_p)\cong ̸_1(𝒜)_p`$.

## 3 Isomorphisms: Affine $`OS`$ algebras and pointed matroids

In  we showed how one could construct, from an arbitrary pair of (realizable) matroids $`G_0`$ and $`G_1`$, a pair of non-isomorphic matroids $`G`$ and $`G^{}`$ for which $`𝒜(G)𝒜(G^{})`$. The matroids $`G`$ and $`G^{}`$ are, respectively, the direct sum $`G_0G_1`$, and any parallel connection $`P(G_0,G_1)`$, stabilized by adding an isthmus (so $`G`$ and $`G^{}`$ have the same number of points). In this section we cast this result in a simpler conceptual framework, motivated by the fact that parallel connection is the categorical direct sum of base-pointed matroids .

We will also prove that, for two matroids $`G`$ and $`G^{}`$, if $`𝒜(G)𝒜(G^{})`$, then $`𝒜(\overline{G})𝒜(\overline{G^{}})`$, where the bar denotes truncation. Together with the equivalences involving direct sum, this result explains all known instances of isomorphisms of $`OS`$ algebras, and so we are led to a possible formulation for a classification result.

We start with some fundamental observations. The elementary proofs are left to the reader.

###### Proposition 3.1

1. If $`iS`$ then $`e_ie_S=\pm e_S`$.
2. If $`S`$ is dependent then $`e_S.`$
3. The ideal $``$ is generated by $`\{e_C|C\text{is a circuit}\}`$.

Our setup involves generalizing the definition of $`OS`$ algebra. This is carried out in  by giving an algebra presentation associated with an arrangement of affine hyperplanes. We adopt a different approach, so that we can stay in the realm of matroid theory. The combinatorial model for an affine arrangement is a pointed matroid, that is, a matroid with a specified base point. Given an arrangement $`A`$ of affine hyperplanes, the underlying pointed matroid will be the matroid of the cone $`cA`$ of $`A`$ , with the hyperplane at infinity as base point. Conversely, given a central arrangement $`A`$ realizing the matroid $`G`$, the effect of choosing a base point in $`G`$ will yield the pointed matroid associated with the decone $`dA`$ of $`A`$ relative to the hyperplane corresponding to the chosen base point. In keeping with the notation of , we will write $`dG`$ to denote a pointed matroid, with underlying unpointed matroid $`G`$. Our convention will be that $`G`$ has ground set $`\{0,\mathrm{},n\}`$, and that $`dG`$ has $`0`$ as base point. More generally, the pointed matroid on $`G`$ with base point $`i`$ will be denoted $`d_iG`$.

###### Definition 3.2

The Orlik-Solomon ($`OS`$) algebra of the pointed matroid $`dG`$ is the subalgebra $`𝒜_d(dG)`$ of the $`OS`$ algebra $`𝒜(G)`$ generated by $`\{a_1a_0,\mathrm{},a_na_0\}`$.

The reader will find that this definition agrees with the definition of  of the $`OS`$ algebra of an affine arrangement $`dA`$ with underlying pointed matroid $`dG`$. In particular we have \[22, Corollary 3.58\]

$$\underset{p}{}dim(𝒜^p(G))t^p=(1+t)\underset{p}{}dim(𝒜_d(dG))t^p.$$

We recover the ordinary $`OS`$ algebra as follows. Given an unpointed matroid $`G`$ on ground set $`[n]`$, let $`cG`$ denote the matroid $`\{0\}G`$ of rank $`\mathrm{rk}(G)+1`$, with the point $`0`$ marked. Here $`\{0\}`$ is understood to be the rank-one matroid with one point, an isthmus. The reader is invited to verify the following result.

###### Lemma 3.3

$`𝒜_d(cG)𝒜(G)`$.

There are two operations on pointed matroids which have a predictable effect on $`OS`$ algebras. The first of these will be obvious to those familiar with the topology of hyperplane arrangements. Indeed, the complement $`M`$ supports an action of $`^{}`$, and the induced map $`H^{}(M/^{})H^{}(M)`$ is a split injection with image $`𝒜_d(d_iG)`$, for any $`i`$ \[22, Prop. 5.1\].

###### Theorem 3.4

For any $`i,j\{0,\mathrm{},n\}`$,

$$𝒜_d(d_iG)=𝒜_d(d_jG).$$

###### Proof.

This is immediate from the identities $`a_ka_j=(a_ka_i)(a_ja_i)`$ for $`ki,j`$ and $`a_ia_j=(a_ja_i)`$. ∎

The parallel connection of pointed matroids $`dG_0`$ and $`dG_1`$ is the unique (up to isomorphism) pointed matroid $`P_d(dG_0,dG_1)`$ of largest rank which is a union of pointed submatroids isomorphic to $`dG_0`$ and $`dG_1`$, whose ground sets intersect only at the base point . The underlying matroid of $`P_d(dG_0,dG_1)`$ is called a parallel connection of $`G_0`$ and $`G_1`$, denoted $`P(G_0,G_1)`$. The following result from  motivated the present formulation of the equivalence discovered in .

###### Lemma 3.5

Parallel connection is a sum in the category of pointed matroids and pointed strong maps. That is,

$$\begin{array}{ccc}\{0\}& & G_0\\ & & & & \\ G_1& & P(G_0,G_1)\end{array}$$

is a pushout diagram of pointed strong maps.

###### Lemma 3.6

The assignment $`dG𝒜_d(dG)`$ yields a functor from the category of pointed matroids and pointed strong maps to the category of connected (i.e., $`𝒜^0`$) graded algebras over $``$.

###### Proof.

Let $`dG`$ and $`dG^{}`$ be pointed matroids on $`\{0,\mathrm{},n\}`$ and $`\{0,\mathrm{},m\}`$ respectively. A pointed strong map $`dGdG^{}`$ arises from a set function $`\eta :\{0,\mathrm{},n\}\{0,\mathrm{},m\}`$ mapping $`0`$ to $`0`$. This function yields a homomorphism of exterior algebras $`\widehat{\eta }:^{}`$ determined by $`\widehat{\eta }(e_i)=e_{\eta (i)}`$. According to \[25, Lemmas 8.1.4 and 8.1.6\], the image of each circuit of $`G`$ is dependent in $`G^{}`$. Using Lemma 3.1 this implies that $`\widehat{\eta }`$ sends $``$ into $`^{}`$, inducing a homomorphism $`𝒜(G)𝒜(G^{})`$. Since $`\widehat{\eta }(a_0)=a_0^{}`$, $`\widehat{\eta }`$ restricts to a homomorphism $`𝒜_d(dG)𝒜_d(dG^{})`$. ∎

As a consequence of these observations, the effect of parallel connection on $`OS`$ algebras becomes natural.

###### Theorem 3.7

The $`OS`$ algebra of $`P_d(dG_0,dG_1)`$ is isomorphic to $`𝒜_d(dG_0)𝒜_d(dG_1)`$.

###### Proof.

Let us write $`dG`$ for $`P_d(dG_0,dG_1)`$. Using the fact that tensor product is a sum in the category of connected graded algebras, together with Lemma 3.6, we obtain a surjective homomorphism $`𝒜_d(dG_0)𝒜_d(dG_1)𝒜_d(G)`$. Using Theorem 1.3 and \[26, Prop. 7.2.9\], one can show that the domain and target have the same dimension in each degree. Thus the two algebras are isomorphic. ∎

As a consequence of Theorems 3.7 and 3.4, we easily obtain the combinatorial/algebraic version of the main topological result of .

###### Theorem 3.8

Let $`G_0`$ and $`G_1`$ be arbitrary matroids. Then $`G=G_0G_1`$ and $`G^{}=\{0\}P(G_0,G_1)`$ have isomorphic $`OS`$ algebras.

###### Proof.

Consider the pointed parallel connection $`d\widehat{G}=P_d(cG_0,cG_1)`$. The underlying matroid $`\widehat{G}`$ is $`\{0\}G_0G_1=\{0\}G`$, which is precisely $`cG`$. Then, by Lemma 3.3, the $`𝒜_d(dG)𝒜(G)`$. On the other hand, by Theorem 3.7, $`𝒜_d(dG)`$ is also isomorphic to $`𝒜_d(cG_0)𝒜_d(cG_1)`$, which again by Lemma 3.3, is isomorphic to $`𝒜(G_0)𝒜(G_1)`$.

Now, according to Theorem 3.4, we may change the base points of $`cG_0`$ and $`cG_1`$ without affecting the affine $`OS`$ algebras. The pointed parallel connection $`d\widehat{G}^{}`$ of these new pointed matroids will have underlying matroid $`\widehat{G}^{}`$ isomorphic to the the sum of two isthmuses (neither marked) with an ordinary parallel connection $`P(G_0,G_1)`$ of $`G_0`$ and $`G_1`$ along the new marked points of each. Again, we have $`𝒜_d(d\widehat{G}^{})𝒜_d(cG_0)𝒜_d(cG_1)𝒜(G_0)𝒜(G_1)`$. Now we change the base point of $`d\widehat{G}^{}`$ to one of the isthmuses, and recognize the resulting pointed matroid as $`cG^{}`$. We apply Lemma 3.3 once more to obtain the result. ∎

We regard the method of proof above as “diagrammatic,” and indeed the argument is easier to follow in pictures than in words. See Figure 1.

It should now be clear that these isomorphisms arise from the trivial operations of changing base points and forming sums.

In  we proved a stronger result for realizations of $`G_0`$ and $`G_1`$, by constructing a natural realization of $`P(G_0,G_1)`$ and proving that the complements of the arrangements realizing $`G`$ and $`G^{}`$ are in fact diffeomorphic. Theorem 3.8 follows in this case by Theorem 1.2.

We state two interesting consequences of Theorem 3.8 from . The first should be compared with Theorems 1.3 and 2.5.

###### Corollary 3.9

Given an arbitrary matroid $`G_0`$, there exist extensions $`G`$ and $`G^{}`$ of $`G_0`$ with isomorphic $`OS`$ algebras but different Tutte polynomials.

The second corollary results from the indeterminacy in the change of base point in the proof of Theorem 3.8.

###### Corollary 3.10

For any positive integer $`n`$, there exist $`n`$ nonisomorphic matroids with isomorphic $`OS`$ algebras.

The original examples of nonisomorphic matroids with isomorphic $`OS`$ algebras, which appeared in , are truncations of $`G`$ and $`G^{}`$, where the factors $`G_0`$ and $`G_1`$ both have rank two. In an NSF-sponsored REU undergraduate research project directed by the author, C. Pendergrass showed that truncation of matroids always preserves isomorphisms of the associated $`OS`$ algebra .

###### Theorem 3.11

Suppose $`𝒜(G)𝒜(G^{})`$, and let $`\overline{G}`$ and $`\overline{G^{}}`$ denote the (corank-one) truncations of $`G`$ and $`G^{}`$ respectively. Then $`𝒜(\overline{G})𝒜(\overline{G^{}})`$.

###### Proof.

Suppose $`\eta `$ is an isomorphism of $`𝒜(G)`$ to $`𝒜(G^{})`$. To begin with, we can then assume without loss that $`G`$ and $`G^{}`$ have the same ground set. The isomorphism $`\eta :𝒜^1(G)𝒜^1(G^{})`$ determines an isomorphism $`\widehat{\eta }:(G)(G^{})`$, and $`\widehat{\eta }((G))=(G^{}).`$ We need only show that $`\widehat{\eta }((\overline{G}))=(\overline{G^{}}).`$

Let $`n=\mathrm{rk}(G)=\mathrm{rk}(G^{})`$. Then, for $`p<n1`$,

$$\widehat{\eta }(^p(\overline{G}))=\widehat{\eta }(^p(G))=^p(G^{})=^p(\overline{G^{}}).$$

Since the truncations have rank $`n1`$, we also have, for $`pn1`$, $`^p(\overline{G})=^{p+1}=^p(\overline{G^{}})`$. Since $`\widehat{\eta }`$ is an algebra homomorphism, it commutes with $``$, and thus $`\widehat{\eta }(^p(\overline{G}))=^p(\overline{G^{}})`$ for $`pn1`$. This completes the proof. ∎

All known examples of isomorphisms of $`OS`$ algebras arising from nonisomorphic matroids are consequences of Theorems 3.8 and 3.11. So we are led to the following problem. Recall that a matroid which is not a truncation is called inerectible.

###### Problem 3.12

For inerectible parallel-irreducible matroids $`G`$ and $`G^{}`$, $`𝒜(G)𝒜(G^{})`$ if and only if $`GG^{}`$.

We prefer an alternate formulation based on the categorical framework developed earlier.

###### Problem 3.13

Suppose $`dG`$ and $`dG^{}`$ are inerectible pointed matroids which are irreducible in the category of pointed matroids. Then $`𝒜_d(dG)𝒜_d(dG^{})`$ if and only if $`dGdG^{}`$ up to change of base point.

## 4 The $`k`$-adic closure of $`𝒜(G)`$

We have recently become interested in quadratic $`OS`$ algebras, and more generally the quadratic closure of $`𝒜=𝒜(G)`$. This is the first in a series of $`k`$-adic closures whose dimensions are algebraic invariants of $`𝒜`$, and about which little is known. In this section we briefly present these ideas and describe some recent results and work in progress, to appear in  and .

For $`k2`$, define the $`k`$-adic $`OS`$ ideal $`_k`$ to be the ideal generated by $`_{jk}^j`$ and the $`k`$-adic closure of $`𝒜`$ to be the quotient $`𝒜_k=/_k`$. These algebras form a sort of resolution of $`𝒜`$:

$$=𝒜_1𝒜_2𝒜_3\mathrm{}𝒜_\mathrm{}1𝒜_{\mathrm{}}=𝒜.$$

The following problem is wide open, even for $`k=2`$.

###### Problem 4.1

Calculate the dimension of $`𝒜_k^p`$ in terms of the underlying matroid $`G`$.

Of special interest is the condition $`𝒜_2=𝒜`$, in which case we say $`𝒜`$ is quadratic. Examples indicate that this condition is related to the notion of line-closed matroid. The line-closure of a set $`S[n]`$ is the smallest subset $`\mathrm{}c(S)`$ of $`n`$ containing $`S`$ and containing the entire line in $`G`$ spanned by any pair of points of $`\mathrm{}c(S)`$. The matroid $`G`$ is line-closed if and only if every line-closed set is closed. A proof of the following result will appear in .

###### Theorem 4.2

If $`𝒜`$ is quadratic then $`G`$ is line-closed.

This result was originally announced in , at which time we conjectured that the converse is also true, that is, that line-closed matroids have quadratic $`OS`$ algebras. S. Yuzvinsky subsequently found a counterexample to this conjecture, the matroid on eight points with nontrivial lines

$$123,3456,167,258,\text{and}478.$$

Yuzvinsky proposed a different condition for quadraticity of $`𝒜`$, which fails for the example above. This condition is also necessary for quadraticity, and is demonstrably stronger than line-closure. G. Denham subsequently found an example (a $`9_3`$ configuration) showing this stronger condition is still not sufficient for quadraticity. The work of Denham and Yuzvinsky is based on a detailed study of the annihilator of the quadratic $`OS`$ ideal $`I_2`$ inside the full tensor algebra, and is reported on in . At this point there seems to be no easily stated matroidal criterion equivalent to quadraticity.

Theorem 4.2 is actually a corollary of a more general result concerning $`𝒜_2`$. We define a set $`\mathrm{𝑛𝑏𝑏}(G)`$ of increasing subsets of $`[n]`$ by $`S=(i_1,\mathrm{},i_p)_<\mathrm{𝑛𝑏𝑏}(G)`$ if and only if $`i_j=\mathrm{min}\mathrm{}c(\{i_j,\mathrm{},i_p\})`$ for all $`j`$. This is an analogue of the set $`\mathrm{𝑛𝑏𝑐}(G)`$ of nbc (=“no-broken-circuit”) sets of $`G`$ . In fact these sets are precisely the NBB (=“not-bounded-below”) sets of A. Blass and B. Sagan , which generalize nbc sets, for the lattice of line-closed sets of $`G`$, with a linear ordering of the atoms. It is the case that $`\mathrm{𝑛𝑏𝑏}(G)=\mathrm{𝑛𝑏𝑐}(G)`$ if and only if $`G`$ is line-closed. Then 4.2 follows easily from the next theorem.

###### Theorem 4.3

The set of monomials $`\{a_S|S\mathrm{𝑛𝑏𝑏}(G)\}`$ forms a linearly independent subset of $`𝒜_2`$.

This generalizes half of the well-known theorem  that $`\{a_S|S\mathrm{𝑛𝑏𝑐}(G)\}`$ yields a basis for the $`OS`$ algebra $`𝒜`$. Yuzvinsky’s example shows that the set $`\{a_S|S\mathrm{𝑛𝑏𝑏}(G)\}`$ cannot form a basis for $`𝒜_2`$ in general.

An analogue of Theorem 4.3 holds for $`𝒜_k`$ for each $`k2`$, giving a partial solution to Problem 4.1 in the form of combinatorial lower bounds. Of course, a formula for the cardinality of $`\mathrm{𝑛𝑏𝑏}(G)`$ has not been found. In fact, this cardinality can change if the linear order of the points is changed.

###### Problem 4.4

Calculate the maximal cardinality of $`\mathrm{𝑛𝑏𝑏}(G)`$ over all linear orderings of the points of $`G`$.

L. Paris has informed us that $`\{e_C|C\text{is a circuit}\}`$ can be shown directly to be a Gröbner basis for the $`OS`$ ideal $``$. A complete direct proof is seemingly not extant. The fact that nbc monomials form a basis for $`𝒜`$ is an immediate consequence. In fact the latter assertion implies the former – see \[23, Theorem 4.1\]. The following problem seems more delicate.

###### Problem 4.5

Find a Gröbner basis for the quadratic $`OS`$ ideal $`_2`$.

Our experiments lead us to another interesting question, which seems to be related.

###### Problem 4.6

Determine conditions on $`S`$ under which $`e_S`$ will lie in the $`k`$-adic $`OS`$ ideal $`_k`$.

We close by returning to the invariant $`\varphi _3`$ defined in the Introduction. It turns out that a calculation of $`dim(𝒜_2^3)`$ would yield a combinatorial formula for $`\varphi _3`$. Indeed, $`\varphi _3`$ is the nullity of $`^1^2^3`$, while the cokernel of the same map is precisely $`𝒜_2^3`$. The dimension of $`^2`$ is just $`dim(^2)dim(𝒜^2)`$, so we obtain the following formula.

###### Theorem 4.7

Let $`n=\mathrm{rk}(G)`$ and $`w_2=dim(𝒜^2)`$, the second Whitney number of $`G`$. Then

$$\varphi _3=2\left(\genfrac{}{}{0pt}{}{n+1}{3}\right)nw_2+dim(𝒜_2^3).$$

Thus Problem 1.4 is a special case of Problem 4.1.

Acknowledgements. I am grateful to Raul Cordovil and Michel Las Vergnas for inviting me to speak at the CIRM conference, and for providing financial support. I thank Sergey Yuzvinsky for his help in studying quadratic $`OS`$ algebras, and Alex Suciu for his suggestion to include resonance varieties over $`_p`$, and his help in understanding them. My REU students Carrie Eschenbrenner, Cayley Pendergrass, and Samantha Melcher assisted me in sorting out much of the material in the last two sections. Finally I wish to thank Diane MacLagan for a helpful correspondence concerning Gröbner bases.

Department of Mathematics and Statistics
Northern Arizona University
Flagstaff, AZ 86011-5717
michael.falk@nau.edu