The RSB order parameter in finite-dimensional spin glasses: numerical computation at zero temperature

(1)

in finite-dimensional spin glasses.

Numerical computation at zero temperature

Scuola di dottorato Vito Volterra

Dottorato di Ricerca in Fisica – XXXI Ciclo

Candidate

Francesco De Santis ID number 0000

Thesis Advisor Prof. Giorgio Parisi

A thesis submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Physics

(2)

Prof. Andrea Cavagna (chairman) Prof. Matteo Marsili

Prof. Silvio Franz

The RSB order parameter in finite-dimensional spin glasses. Numerical com-putation at zero temperature

Ph.D. thesis. Sapienza – University of Rome ISBN: 000000000-0

This thesis has been typeset by LA_{TEX and the Sapthesis class.}

Version: September 6, 2019

(3)

Abstract

This thesis focuses on the computation of the overlap distribution which characterizes spin glasses with finite connectivity upon an RSB transition at zero temperature. Two models are studied: the J ± Bethe lattice spin glass and the Edwards-Anderson spin glass in three dimensions with random regular bond dilution, a random dilution with the constraint of fixed connectivity z = 3. The overlap distribution is the spin glass order parameter and its form has not been derived yet for models other than mean-field. The approach is based on the study of the effects induced by a bulk perturbation on the energy landscape. In ultrametric spin glasses, the distribution of the excited states is known to be related to the order parameter through a universal formula which is used for deriving the order parameter from the experimental distributions. Besides, the finite-size corrections to the ground state energy are computed for the two models.

(4)

(5)

(6)

(7)

Introduction

The reason why spin glasses have dominated the scene of Statistical Mechanics of Disordered Systems in the last forty years is the complexity of behaviors they manifest even in the simplest form of mean-field approximation. Like glasses, below a certain critical temperature, these systems condensate in an exponential multitude of frozen configurations which are different from each other and not related by any simple symmetry. If one had to classify all the possible states, the organization of these frozen states would remind more of the branching process of a tree than some casual distributions of points in space. Such complexity was frankly unexpected when the model was formulated for the first time by Edwards and Anderson in the seventies [1] as little more than a purely theoretical problem with few practical applications. The subject turned out to be a formidable challenge for physicists and mathematicians, yielding to the formulation of new theories and methods for building a more general Theory of Glasses.

In this respect, spin glasses are probably the simplest realization of a glass. In the Edwards-Anderson (EA) original formulation, a spin glass is nothing more than a collection of Ising spins on a lattice, their nearest-neighbor interactions being a random distribution of ferromagnetic and anti-ferromagnetic bonds. In other words, the Edwards-Anderson spin glass is an Ising model, very well known in Statistical Mechanics, with a pinch of randomness added to the Hamiltonian. As simple as it could seem, this is one of the most complicated models to be approached and its thermodynamics has not been fully understood yet, with a solution being available only in more than six dimensions. In this respect, the infinite-dimensional spin glass is a simplified version of the EA model introduced by Sherrington and Kirkpatrick (SK) [2] as a starting point for building a mean-field solution. Nevertheless, finding the correct solution to this model required a great effort and took several years. The exact solution was found by Parisi [3, 4] in a particular formulation known as Replica

Symmetry Breaking (RSB)[5], whose physical implications were not immediately

understood. When the mystery was solved few years later[5, 6], an unexpected scenario appeared, as the spin glass phase turned out to be organized in a large number of states different from each other, organized in a complex hierarchy of clusters known as ultrametric structure [7].

Many advances have been made since then. First of all, numerous results found initially with a heuristic approach, like the replica method, have been rigorously proved with a more robust mathematical formulation [8, 9], almost twenty-five years after the formulation of the theory. Moreover, new techniques have been forged to extend the theory beyond the mean-field level. The cavity method [10, 11] allows to reformulate the original spin glass problem in a probabilistic framework providing a

(10)

bridge with Combinatorial Optimization [12–16]. Moreover, the spin glass theory has found a wide range of applications in fields ranging from physics to very different areas, like supercooled liquids [17–19], photonics [20, 21], random matrices [22–24], random interfaces [25], inference [26–28], signal processing[29], neural networks [30– 33], immunology [34, 35], epidemic spreading [36, 37], finance [38], game theory [39, 40], quantum algorithms [41], collective behavior [42, 43] and biological networks [44]. The problem of formulating a finite-dimensional theory remains. In this respect, finite-dimensional models represent a more realistic version of spin glasses, where each spin can interact only with a limited number of neighbors, and one wonders how many of the remarkable features of the mean-field description would survive in these models. The theoretical task, however, is not easy. In order to descend to finite-dimensions, one should consider fluctuations around the mean-field solution, a problem studied in the Renormalization group approach [45], whose goal is to compute the upper critical dimension above which the mean-field solution provides a meaningful description of the spin glass transition. It is known that for the EA model the upper critical dimension is du = 6.

Several conjectures have been made about the behavior in dimension lower than six. The investigation in this regime is mostly based on the comparison between numerical evidence on systems of finite-size and the predictions from Finite Scaling Theory (FSC). In the RSB theory, small excitations of finite energy cost produce a global rearrangement of the system whose interface is space-filling, even in the thermodynamic limit. In the Droplet Scaling Theory, or Droplet Model (DM) [46–48], a very different scenario is conjectured, where excitations have the form of compact droplets with a fractal-dimensional interface, whose cost grows with the size of the system.

Unfortunately, the complications which arise in the numerical investigation at low temperature, limit the size of the systems which can be studied. Two main approaches are usually taken. One could either thermalize the system starting from high temperature and performing a simulated annealing (or analog technique based on a Monte-Carlo dynamics), or perform a direct calculation of ground states and proceed with a zero-temperature analysis. In the first case, critical slow-down phenomena arise which make the algorithm very inefficient as the temperature decreases. The second approach has proved to be very useful in the last twenty years, as very effective algorithms for the ground states computation have been borrowed from computer science.

The purpose of this thesis is two-fold. On one side it constitutes a review of the efforts which have been made until today to formulate a finite-dimensional description of spin glasses, focusing mostly on the numerical approach and on the results collected in favor of the different theoretical conjectures. On the other side, we provide an original contribution to the ongoing investigation by deriving the overlap distribution at zero temperature of two models: the Bethe lattice spin glass, and the diluted Edwards-Anderson model in three dimensions. The overlap distribution has great importance in the characterization of the spin glass phase since it constitutes the physical order parameter of the spin glass transition. In other words, the whole information about the organization of the states is encoded within this distribution. The analytical derivation of this quantity is possible only in mean-field models, and its numerical computation has been tried in different contexts. The method adopted

(11)

in this thesis was proposed by Franz and Parisi [49], and is based on the effects induced by a bulk perturbation on the energy landscape. The purpose of the analysis is to gather new information about the nature of spin glasses which deviate from the mean-field description.

This thesis is organized as follows:

Part I : In the first part the fundamentals are introduced and a course is set from mean-field theory to finite-dimensional systems, passing through diluted systems.

In Chapter 1, the general formalism is introduced, providing notions of graph theory and presenting a general introduction to spin glasses and disordered systems. Moreover, a connection between Spin Glass Theory and Combinatorial Optimization is presented to show the extent of the theory.

In Chapter 2, the mean-field theory of spin glasses is presented through the in-troduction of two standard models: the Sherrington-Kirkpatrick model and the Bethe lattice spin glass. The two main approaches used in the mean-field theory are reviewed: the Replica approach and the Cavity method. Moreover, one of the most important concepts of spin glass theory will be introduced: the spin glass order parameter.

In Chapter 3, the state of the art of the investigation at finite dimension is presented, focusing on the numerical approach and on the scaling properties of the ground states.

Part II : In this part, the main results of the numerical simulations concerning several aspects of spin glasses at finite dimension and finite connectivity are presented.

In Chapter 4, the computational setup and the numerical approach are presented, together with the first results of the simulations and a short tentative study of the ultrametricity.

In Chapter 5, the first original contributions of this thesis are presented as the finite-size corrections to the ground state energy of the models are calculated and discussed.

In Chapter 6, the overlap distribution of the models is derived from a direct compu-tation of the ground states. As the technique adopted for the compucompu-tation had never been used before for these models, the results presented in this chapter are an original contribution to the ongoing investigation.

In Chapter 7, some conclusions and perspectives of the present work are discussed.

The project that forms the basis for this thesis was developed gradually during the years of the doctorate. The initial idea suggested by Giorgio Parisi, my thesis advisor, involved the derivation of the RSB order parameter of the Bethe lattice

(12)

from the overlap distribution induced by a bulk perturbation. The starting point consisted in developing and refining the computational framework, and preparing the ground for simulations on a scale large enough to provide statistically significant results. This part was completed by the end of the first year, and the results obtained were in agreement with the presence of an RSB transition at zero temperature at the predicted critical field. During the second year, my advisor suggested that the same method could be used for studying a bond-diluted finite-dimensional model with a degree distribution similar to the one of the Bethe lattice. At the same time, I started to study the finite-size corrections to the ground state energy and the spin glass susceptivity near the critical field. This latter was addressed by studying the scaling properties of the excitations induced by one spin reversal. In this case, the preliminary results showed that the method was affected by excessive noise and the study was postponed for further investigation. The study was refined during the final year of the doctorate, which was also spent on verifying the obtained results. In particular, the results relative to the spin glass models were compared with the results obtained in the random field case, where no RSB transition is expected. Moreover, the consistency of the method for deriving the order parameter was tested and confirmed by a more detailed analysis of the experimental distributions. In conclusion, the different results obtained over the course of these few years of doctorate fall into the branch of finite-dimensional studies. Hopefully, they may provide a useful tool of investigation for deriving a more general theory of spin glasses.

(13)

Part I

(14)

(15)

Chapter 1

Disordered systems

1.1 Elements of Graph Theory

Graphs are mathematical structures able to represent very effectively networks of relationships between elements. The concept of graph was introduced already in the 18th century by Euler to study the problem of the Seven bridges of Königsberg, and formalized in the next two centuries with the works of Cayley on trees, König, and Polya [50]. The probabilistic approach that brought to the formulation of modern

random graph theory [51, 52] started with the article of Erdös and Rényi on random

graphs [53]. Beside the applications in mathematics and physics, graph theory has proven very effective at modeling systems of various nature, from Computer Science to Biology, Finance and Social Science[54–57]. In the context of disordered systems, graph theory provides a useful notation for defining the underlying structure of a model and powerful methods and theorems for characterizing its topology.

In this section, we introduce the basic concepts and the notation which will be used very often throughout the rest of this thesis. For a more detailed introduction to Graph Theory we refer to [52, 58].

1.1.1 Fundamentals

Basic definitions. A graph G(N, M ) = GN,M = (V, E ) consists of a set V 6= ∅ of

N vertices (or nodes) and a set E of M edges (or links). A node is usually identified

by its order i in V, such that V = {1, . . . , N }, while the edges are represented as pairs of elements of V. If the pairs are unordered then the graph is undirected and the edges are represented as lines connecting the nodes, otherwise the graph is directed and the edges are represented as arrows.

An edge l is said to be incident in the node i if i is one of the end-nodes. Two nodes joined by an edge are said to be adjacent or neighboring. The set of vertices incident in a node i is called adjacency or neighborhood of i and is denoted ∂i. An edge of the type (i, i) is called self-loop (or simply loop). If two nodes are joined by more than one edge, then the link is a multi-edge. A graph which does not contain either loops or multi-edges is said to be simple, otherwise is called multigraph. The number of edges M in an undirected graph ranges from zero (edgeless graph) to N₂

(16)

M N2 (or M remains finite in the N → ∞ limit), or dense if M = O(N2). Moreover, if a mapping w : E 7→ R is defined, then the graph is said to be weighted. In simple graphs, the weights are denoted w(i, j) ≡ wij and may specify the cost,

capacity or a measure of distance if the graph is embedded in a metric space. In

the rest of the thesis, we will consider simple graphs which are undirected and unweighted, unless differently specified.

A subgraph G0(V0, E0) is a graph such that V0 ⊆ V and E0 ⊆ E. If E0 contains all the edges incident in the nodes of V0 which are contained in E , then G0 is said to be the subgraph induced by V0, denoted G0 = G[V0]. A subgraph is maximal with respect to a property if it cannot be extended without losing that property.

Node degree and degree distributions. The cardinality of the adjacency of a node is said connectivity of node degree: deg(i) ≡ k_i = |∂i|. If k_i = 0 the node i isolated; if k_i = 1 the node is a leaf. It is convenient to consider the degree

distribution of a graph, defined as the frequency distribution: pG(k) ≡ 1 N X i∈V δ(k − ki), k ∈ N (1.1) The mean degree is

zG≡ 1 N X i∈V =X k≥0 pG(k)k (1.2)

Paths and cycles. A path W` of length ` is an ordered sequence of vertices

W` = (i0, i1, . . . , i`) such that (in, in+1) ∈ E , ∀n = 0, . . . , ` − 1. A path is simple if each node is crossed only once by the path. The distance between two nodes is defined as the length of the shortest path between them. The maximum distance of the graph is said to be the diameter of the graph. A path is called a cycle if i0= i`, otherwise is an open path. A graph with no cycles is called acyclic.

Trees. An acyclic graph is called a forest, and a connected forest is called a

tree. In a tree, any two vertices are connected by only one path. Moreover, if an

edge is removed from a tree, the resulting graph is disconnected; if an edge is added to the tree, a cycle is formed, and the graph is not a tree anymore. Trees contain always at least one leaf with degree 1.

In rooted trees, a vertex is distinguished from the others and called a root. The

depth of a node is defined as its distance from the root. In rooted trees, there is an

orientation for classifying the nodes which goes from the root to the leaves. With respect to a node i, the nodes on the path to the root are called ascending nodes, while the ones on the path to the leaves are called descending nodes. The parent of a node is its neighboring ascendant, while the child of a node is one of the adjacent descendants. Two nodes are siblings if they share the same parent.

A spanning tree of a graph is a tree subgraph which contains all the vertices of the graph.

Other topological properties A graph is connected if for any pair of nodes

i, j there exists a path between them. A graph is K-partite if V can be partioned in K subsets of disconnected graphs. The giant component of a graph is a connected

(17)

Matricial representation. A graph can be completely defined an adjacency

matrix A, an N × N matrix whose coefficients A_ij are equal to 1 if (i, j) ∈ E , 0 otherwise. The adjacency matrix of a simple graph is symmetric and zero-diagonal. Moreover, the sum across the i-th row or column is equal to the ki. An interesting property of the adjacency matrix of a simple graph is that its powers Al are related to the paths of length l between the nodes. The coefficient Al_ij is equal to the number of directed paths between i and j. The coefficients Al_ii are equal to twice the number of cycles of length l passing through i. In weighted graphs, the coefficients of the adjacency matrix may be the weights: Aij = wij.

A graph can be alternatively represented by the incidence matrix B, a N × M matrix whose entries B_ik are 1 if the edge e_k ∈ E is incident in i ∈ V. Typically, this representation is more expensive in terms of storage space in computational applications, and a representation in terms of the adjacency matrix is preferred. The adjacency matrix of sparse graphs is also sparse, and in practical applications is substituted by adjacency list {ai}i∈V in which every vector ai is the list of the adjacent nodes.

1.1.2 Random Graphs

In 1959, Erdös and Renyi introduced a new probabilistic approach to graph theory [53], with the purpose of studying the properties of graphs as a function of the increasing number of random connections, founding a new branch which developed independently as random graphs theory. The approach is based on the definition of a probability space on the set of graphs G with N vertices with a specific probability measure P [G], which together define a graph ensembles. An instance or realization of a particular element of the ensemble is a graph G ∈ G sampled from the distribution

P (G) following a specific random process.

Due to the presence of structural disorder, one is usually interested in the behavior of the typical instance of the ensemble. Thus, it is convenient to define the average

over the ensemble of a property O:

E[OG] ≡ O =

X

G∈G

OGP [G] (1.3)

In the following, we introduce two ensembles particularly important in the theory of spin glasses.

Erdös-Renyi (ER) ensemble: In their first article [53], Erdös and Renyi proposed a model for generating random graphs with N nodes and M edges, which we denote GER_N,M. Starting with an edgeless graph with N nodes, ER graphs are generated by adding randomly M edges, prohibiting loops or multi-edges. A different ensemble GER_N,p is generated by following a different procedure. Starting from a set of N disconnected nodes, each of the N (N − 1)/2 edges is added with probability 0 < p < 1. This ensemble contains graphs with a different number of links, the average being N₂

p, and the probability of a

graph with M edges is:

(18)

The GER_N,M and GER_N,p models coincide in the N → ∞ limit, and they have a strong analogy, respectively, with the canonical and grand canonical ensemble in Statistical Mechanics [59].

The probability that a node i has k = ki edges is the binomial distribution:

P (ki = k) =

N − 1 k

!

pk(1 − p)N −1−k (1.5)

where pk is the probability for k edges to be incident in i with independent probability p, (1 − p)N −1−k is the probability of not having the remaining

N − 1 − k edges, and N −1_k

is the number of different ways of selecting the neighboring nodes. Since all the nodes are statistically equivalent, in the large

N limit and fixed z =< k >, the degree distribution tends to the Poissonian

distribution:

P (k) = e

−z_zk

k! (1.6)

For this reason, ER graphs are called Poissonian random graphs.

Random Regular Graph (RRG) ensemble : The ensemble of the z-regular

random graphs GRRG_N,z (with 3 ≤ z ≤ N ) has uniform measure over the random graphs where each of the N nodes has fixed degree ki = z. The number of edges is M = N z₂ , and N z must be an even number.

Since most of random graphs are non-regular, it is important to implement the selection of the RRGs in an unbiased way, such that the samples are drawn with a uniform distribution over the GRRG_N,z ensemble. The standard method was proposed by Bollobás [60], and goes under the name of configuration model, or pairing model. One starts with a partition of N z points called half-edges in

N cells of z elements, and proceeds by pairing the half-edges through a random

matching. The RRG is generated by contracting each of the N points belonging to different cells into one point. In general, there is a finite probability to obtain a multi-graph, especially for large values of z. In this case, the graph is discarded and the procedure is repeated from the beginning. Due to the possibility of sampling a non-simple graph, this method is computationally expensive and gets exponentially slow with increasing z. Faster algorithms which preserve the uniform measure over the ensemble in the large N limit have been proposed in [61, 62]. In particular, the algorithm can be simplified by rejecting just the last matching which brings to a multi-graph, without repeating the whole procedure. This is the method which has been used for generating the RRG samples in this thesis.

The configuration model, though, provides a uniform measure over the ensemble and can be used for generating random graphs from the ensemble GCON F_N,D with

D = {ki}Ni=1 any given degree distribution [63].

Connectedness. The connectivity properties of random graphs are subject to a dramatic change upon a change of the parameter p below a critical value pc= 1/N .

(19)

Let us consider the GER_N,p model, whose graphs have an average degree z =< k >. Erdös and Renyi proved that almost surely 1:

• if p < p_c, then the graph is disconnected in components not larger than O(ln N ) with no more than one cycle;

• if p = pc, then the larges component has size O(N2/3);

• if p > pc, then the graph has a giant component of size O(N ) with O(N ) cycles, and there are no components larger than O(ln N ) and more than one cycle.

From the statistical physics point of view, the transition at pchas the typical features of a second-order phase transition, and if the size of the largest component is chosen as order parameter, then the transition falls in the same universality class as mean-field percolation transitions. With respect to the property of connectedness in GER

N,p, a random graph is almost surely connected if p ≥ ln N_N . In the GRRG_N,z ensemble, almost any graph is connected for z ≥ 3.

Local tree topology. In the context of statistical physics, one of the most important properties of random graphs concerns the density of cycles of finite length. In this respect, the probability of finding C_` cycles in a random graph is finite in the N → ∞ limit, if ` is kept constant.

In random regular graphs, a given sequence of variables Y₃, . . . , Ym representing the number of cycles of length 3 ≤ ` ≤ m, tend asymptotically to random variables with Poisson distribution [51, 64] and mean:

λ` =

(z − 1)`

2` (1.7)

As the density of cycles of finite length decreases with the size of GRRG_N,z graphs, given any node i, there exist a distance R such that the subgraph induced by the nodes within distance R from i is almost surely a tree. In spin glass theory this property is crucial, since it grants that the frustration affects the system only on large scale, permitting to neglect the correlation between spins at short distance. In this regard, a spin glass model defined on a random graph is a Bethe lattice spin

glass, and will be studied in detail in Section 2.2.

1.1.3 Factor graphs

The representation of systems where local interactions involve more than two variables requires a more general class of bipartite graphs called factor graphs [12]. Factor graphs are normally used for representing the p-spin model and some optimization problem (see Section 1.2.3).

Let us consider a set of N variables x = {x₁, . . . , xN} taking values in a finite set X, and a probability measure defined over the space of the configurations :

P [x] = 1 Z M Y a=1 ψa(x∂a) (1.8) 1

In probability theory, a property is almost sure if it appears with probability one in the large

N limit, or in other words if the set of instances where the property is violated has zero measure in

(20)

where ψa are special compatibility functions which depend on the nature of the problem, defined on a subset ∂a of the N variable indexes.

A factor graph is a bipartite graph which provides an effective representation of the joint probability (1.8). Factor graphs consist of two groups of vertices:

• variable nodes, which correspond to the N variables and whose indexes are denoted i, j, k, l, ...

• function nodes, which correspond to M interactions between nodes, denoted

a, b, c, ..., each one involving a subset of variable nodes ∂a, ∂b, ∂c

Each variable node is connected by edges to all the function nodes in which it appears, and vice versa.

In spin glasses with pairwise interactions, the function nodes are trivial, since they connect only 2 spins. (|∂a| = 2), and simple graphs provide a good representation. In p-spin glasses with p > 2, each function node a has adjacency ∂a = {i1, . . . , ip} and contributes to the Hamiltonian with a term Ea = −Ji1,...,ipσi1. . . σip. Factor

graphs representation provides a powerful connection between statistical physics and combinatorial optimization.

(21)

1.2 Spin glasses

Spin glasses were introduced in the early seventies as a class of magnetic materials with a peculiar response to an oscillating external field. For these systems, the susceptibility has a cusp at a critical temperature T_c, a behavior qualitatively different from ordinary magnetic materials [65]. This singular behavior is explained in terms of a phase transition due to the freezing of the magnetic dipoles of the samples. Like in ordinary ferromagnetic materials, the physical origin of these dipoles is the spin of the electrons, with the difference that the couplings between the spins are somehow irregular. This irregularity can be accounted for by introducing two ingredients in an ordinary d-dimensional ferromagnetic Ising model: disorder and frustration. The disorder is introduced in the form of random anti-ferromagnetic bonds, according to some probability distribution. The frustration is due to the presence of closed cycles in the graph along which it is not possible to satisfy simultaneously all the bonds. This results in the impossibility of minimizing all the terms of the Hamiltonian at the same time.

The systematic study of spin glasses started with the articles of Edwards and Anderson [1] and Sherrington and Kirkpatrick [2]. Since then, spin glasses have gained importance in Statistical Mechanics as representative of a more general class of disordered systems, ranging from supercooled liquids, glass forming, structural glasses, optimization problems, and many other models. In this context, many interesting phenomena concerning glassy systems were discovered for the first time in mean-field spin glasses, models where the mean-field approximation is exact.

Before proceeding further, it is convenient to summarize the most important aspects which account for the glassy behavior of spin glasses:

• Spin glasses undergo a phase transition at critical temperature Tc. The transition from the paramagnetic phase to the spin glass phase is characterized by the appearance of frozen disorder in which the local magnetization is non-zero but the total magnetization is null.

• The energy landscape in the spin glass phase is rough as it consists of many valleys and barriers. In the thermodynamic limit, the barriers are eventually infinite, and the ergodicity is broken in the system. The Gibbs state does not describe anymore the system at the equilibrium and the Boltzmann measure is decomposed in a sum of pure states, corresponding to the measures restricted to ergodically disconnected regions of the space of the configuration.

• The out-of-equilibrium behavior is characterized by a different type of transi-tions which occur in general at different temperatures from T_C. The dynamic evolution of the systems is subject to a critical slowing down upon cooling below the critical temperature starting from high temperature. The dynamics is characterized by history-dependent response and aging.

• The mean-field solution of the SK model provides a scenario known as replica

symmetry breaking (RSB), in which all the states are macroscopically different

and show a form of non-trivial organization. Due to ultrametricity, the states are organized in a structure of clusters with respect to their mutual distances. This hierarchy can be described by representing the states as the leaves of a

(22)

rooted tree and the clusters as the intermediate nodes.

In this section, we will introduce a mathematical definition of disorder and present the main theoretical models of spin glasses. Moreover, we will give a brief review of a different class of disorder systems encountered Optimization. The analogy between spin glasses and optimization problems has widely influenced the development of both Physics and Computer Science, as concepts, methods, and algorithms have been shared to build a more general theory of disordered systems.

1.2.1 Disorder

Quenched disorder. In real disordered systems, different types of variables are normally characterized by different dynamic time scales τ . The variables subject to thermal fluctuations, like spins in magnetic systems, follow a fast thermal dynamics, their values changing in times of order τ_eq. The system is considered at equilibrium for times teq/τeq 1. On the other hand, the variables describing the disorder are governed by much slower dynamics, with time scale τq  τeq. For all practical purposes, these variables are considered frozen, or quenched, as they are constant for

t < teq. In this case, a sample of a disordered system is characterized by a specific configuration of quenched variables.

When describing spin glasses, we will consider two types of disorder. The first one consists in a certain amount of randomness introduced in the mutual interactions between the variables. For a given sample, the coefficients of the coupling matrix

J are i.i.d. quenched random variables drawn from a probability distribution P (J )

which depends on the model considered. In infinite-range models and in the d-dimensional Edwards-Anderson model, this is the only type of disorder present in the system.

The second type of disorder is structural, as randomness is introduced in the

adjacency matrix of the graph which describes the lattice. In Erdos-Reiny random

graphs two nodes are connected with probability p, and the distribution of the node degrees is Poissonian. In random regular graphs the nodes are connected at random, but the number of neighbors of each node is kept constant. In diluted graphs the edges are removed with a certain probability starting from a d-dimensional regular lattice. In the next chapters we will consider a sort of random-regular dilution for the regular lattice, obtained by keeping the number of neighbors of each node constant

z < 2D.

Unless differently specified, in the rest of this thesis we will assume that every form of disorder is contained in the matrix J . A null entry Jij = 0 will denote a missing bond between the sites (i, j), while a non-zero entry will denote both the presence of an edge in the underlying graph (Aij = 1) and the coupling between the two sites.

The average over the disorder. Let us consider a given sample characterized by a specific realization of J , and let us consider an observable OJ describing some thermodynamic property of the sample. Due to the presence of disorder, O_J is different when calculated on two different samples with different realizations of J . When dealing with disordered systems, though we are interested in the behavior of the typical sample, whose properties are supposed to be described by quantities

(23)

which are averaged over the disorder distribution. In our case, we will denote such averages for an observable as:

O = OJ = lim N →∞

Z

OJP (J )dJ (1.9)

This averages are relevant for describing the whole ensemble only if the fluctuations can be kept under control. For instance, as in ordinary statistical mechanics we know that the relative fluctuations of the energy around its thermal mean value are of order O(N−1/2), we also expect that the fluctuations of relevant quantities between different systems go to zero in the thermodynamic limit. If the sample-to-sample fluctuations vanish in the thermodynamic limit, then the observable is said to be

self-averaging. If we know that quantities of interest are self-averaging, then we can

expect the same results in experiments on different macroscopic samples. Moreover, a theoretical computation of the mean value of such quantities over the whole ensemble gives the same results in all of the experiments. Normally, extensive observables such as the free-energy are well-behaved, in the sense that their associated densities are self-averaging in the thermodynamic limit.

However, not all the observables are self-averaging. In some cases, the atypical

samples give a finite contribution to the average even in the thermodynamic limit.

In this case, the sample-to-sample fluctuations do not vanish for N → ∞ and the average over the disorder cannot be assumed to be representative of the behavior of the single sample. An example of non-averaging observable is the overlap distribution in spin-glasses, which will be introduced in the next sections.

Quenched and annealed averages. Let us consider a system described by Hamiltonian HJ, whose equilibrium distribution is characterized by the usual Boltzmann measure, and let Z_J be the partition function:

ZJ(β) = Trσe−βHJ (1.10)

where β is the inverse temperature, and the trace involves the sum over all the configurations of the Boltzmann measure.

We are interested in computing the averaged free-energy density:

f = fJ = − lim N →∞

1

βNlog ZJ (1.11)

The presence of the logarithm here is crucial. The average over the logarithm of the partition function is a quenched average and it turns out to be more complicated than the simpler annealed average ZJ. In the second average, the quenched variables and the thermal variables are treated in the same way. However, we know that quenched variables do not participate in the thermalization of the system and that they must be considered constant in the typical time-scale needed for reaching the equilibrium. For this reason, the two averages have very different physical meaning and cannot be exchanged.

1.2.2 Spin glass models

A spin glass is defined as a set of N variables σ = σii=1,...,N located on the vertices of a graph G. If the interactions between the variables are pairwise, then G is a

(24)

simple graph with only one type of vertices (representing spin variables), and the

edges of the graph represent pairs of interacting spins. If more than two spins are involved in the interactions, like in the more general p-spin model then G is a factor graph. In this thesis, we will consider only models with 2-spin interactions and Ising variables σ_i = ±1, unless differently specified.

Given these premises, let us consider an Ising spin glass defined on a simple graph G = (V, E ): H_J[σ] = − X (i,j)∈E Jijσiσj− X i∈V hiσi (1.12)

The coefficients J_ij are i.i.d. quenched random variables drawn from a probability distribution P (J ), different from zero only in correspondence of an edge. We will assume that the coupling matrix J is symmetric (Jij = Jji) and has zero-diagonal (J_ii= 0).

Two distributions of disorder are usually considered: • Gaussian distribution with mean J and variance J2_:

P (J ) = p 1

2πJ2e −J −J

2J 2 (1.13)

• Bimodal distribution with zero mean and variance 1:

P (J ) = 1

2δ(1 − J ) + 1

2δ(1 + J ) (1.14)

In some cases we will mention biased models in which J 6= 0, otherwise we will consider P (J ) with zero mean.

We also consider four different models:

Sherrington-Kirkpatrick (SK) model [2]: In the fully-connected model all the Jij coefficients are different from zero and drawn from a Gaussian or Bimodal distribution with variance N−12. This ensures that the energy density

does not diverge in the thermodynamic limit when the number of terms in the Hamiltonian grows as O(N2). The mean-field theory gives exact results for this model in the N → ∞ limit [66].

Bethe lattice (BL) model [10, 11]: The model is typically defined on a random regular graph with coordination number z. As the number of edges is N z/2, the variance of the P (J ) distribution is finite and typically set to z−1/2 in order to have a good limit z → ∞. Due to the topology of the underlying graph, the correlations can be neglected in the thermodynamic limit, and the mean-field theory is valid for this model.

Long range (LR) model [67]: The model is defined on a d-dimensional lattice, and the interactions are limited within a radius R from each site. The variance of the disorder distribution is therefore set to 1/RD/2. In this model, the corrections to the mean-field theory are small if R is large. However, the corrections might change the large distance behavior of the correlation functions, and the phase transition might disappear. Normally the long-range model

(25)

represents a good candidate for interpolating between the mean-field results and the short-range model [68].

Edwards-Anderson (EA) model [1, 69]: The model is defined on a d-dimensional lattice with nearest-neighbors interactions, and the variance is normally D−12.

The correlations to the mean-field theory are large, and no spin glass transition is expected in d = 1, 2 (the lower critical dimension is d_c = 2.5) [70]. The upper critical dimension above which the mean-field describes correctly this model is du = 6. The behavior at lower dimension is still debated, and the investigation relies mostly on numerical methods.

From the analytical point of view, the four models have been presented in order of difficulty, the infinite-range model being the simplest and the first to be solved, and the others presenting difficulties in the computation of the corrections to the mean-field theory. Although they belong to different universality classes, the first two being mean-field models, the last two being short-range models, with respect to the free energy, all the models tend to the SK model respectively for z → ∞, R → ∞, d → ∞.

(26)

1.2.3 Optimization

The main concepts and phenomena which characterize spin glasses are analogous to the ones encountered in Combinatorial Optimization, where three types of problems are normally considered:

• optimization problems, which consist in finding an optimal solution;

• evaluation problems, which consist in determining the cost of an optimal solution;

• decision problems, consisting in comparing the cost of two solutions with respect to their cost.

In this section we illustrate the analogies between Spin Glass Theory and Optimiza-tion, reviewing some of the most common models.

Some concepts introduced in this chapter will be encountered in Chapter 6.4, where the problem of computing spin glass ground states will be addressed.

Computational Complexity. Computational complexity theory classifies

problems according to their difficulty in terms of the amount of computational resources needed to solve them.

To evaluate the overall hardness of a problem, for instance, we might consider the time required by an algorithm to solve the worst instance, i.e. the one which takes the longest time tN to be solved, out of all the instances with the same size. Moreover, it is usually important to compare two problems in terms of their hardness. A problem A is said to be not harder than B, if any instance of A can be turned in an instance of B, in polynomial time. This operation is called polynomial reduction and sets a class of equivalence for problems. In this regard, computational problems are generally classified according to the following computational complexity classes:

Class P It’s the class of polynomial problems, whose running time is bounded from above by a fixed polynomial, T_N = O(Nk). These problems are considered

simple and they can be solved by efficient algorithms.

Class NP : Non-deterministic polynomial problems can be solved in polynomial time by algorithms that can run in parallel on an arbitrarily large number of processors. This means that in general, these problems are not solvable in polynomial time but, if a positive instance of the decision problem is found, then it can be verified in polynomial time.

Class NP-complete : A problem A is complete for a class if (a) it belongs to the class and (b) any problem of the class is not harder than A. In this respect, NP-complete problems are the hardest problems in the class NP and if a problem is found to be NP-complete, then all the others cannot be harder than this one.

NP-hard : The problems which do not belong to the previous classes are NP-hard. These problems are at least as difficult as NP-complete problems.

(27)

few cases. As a consequence, exact algorithms can be used only for small systems (N ∼ 102) under certain assumptions. For larger systems heuristic methods are used. A review of these methods will be given in Chapter 4.

Optimization problems. A combinatorial optimization problem is defined by a set of possible instances - a finite set of allowed configurations - and a cost function. The latter is a real-valued function E defined over this set, which corresponds to the energy in the spin glass case. Solving an optimization problem corresponds to finding the optimal configuration which is a global minimum (ground state) for the cost function. In this respect, solving an optimization problem corresponds to finding its equilibrium state at zero temperature.

Search algorithms are used in Computer Science to solve optimization problems

by exploring the space of configuration. As the size of the space grows exponentially with N , a minimization procedure must be defined, an algorithm which dynamically explores the space starting from a configuration, evolving towards the optimal solution until the cost function reaches its minimum.

The optimization problems which are interesting in the context of spin glasses are the ones with a glassy energy landscape. In these systems, the cost function is non-convex and has many valleys. As a consequence, the dynamics of solving algorithms is affected by meta-stable states and ergodicity breaking.

Hereafter, we introduce some of the most common optimization problems which share similarities with glasses.

Assignment : Given two different sets of N elements, for example N persons and N jobs, and a affinity matrix C_ij which defines the affinity between pair of elements belonging to different sets, the problem consists in finding the

assignment which maximizes the total affinity. A configuration is characterized

by a permutation of the N indexes, therefore the size of the space of solutions is N !. The cost of a permutation p isP

iCip(i). These problems belong to the class P and can be solved in times of order O(N3) [12].

Satisfiability The satisfiability problem consists in determining whether there exists a set of N boolean variables which satisfies a set of logical constraints (decision problem) or to find the configurations which minimize the number of violated constraints (optimization problem). The logical constraints are expressed in a special form which contains only logical OR and NOT operators applied to k variables per time, called k-clause. Satisfiability problems where all clauses have the same length k are said k-SAT problems. The 2-SAT decision problem is known to be easy, while in the general case the problem is class NP-complete.

The 2-XORSAT problem in which every variable appears exactly in z random equations (with M = N z/2 total equations) is equivalent to the solving the spin glass problem on the Bethe lattice.

Coloring The q-coloring decision problem consists in finding whether the vertices of a graph can be colored using q colors in such a way that there are no neighboring vertices with the same color. A similar problem is the

(28)

to cover the vertices of a graph in such a way that every edge has an end-point covered.

Random Simple Matching: Given an unoriented graph G(V, E ), a matching M is a set of edges having the property that no two edges in M have an ending in common. A vertex v is matched if there is an edge incident to v in the matching, otherwise v is unmatched. A matching is perfect if every vertex of

G is matched.

Usually a function l(e) : E → R is defined, which can be thought of as a distance, a weight or the cost of a single matching. The cost function is thus

LM =Pe∈Ml(e), the total length of a matching M. The matching problem consists in finding the cheapest matching which minimizes LM.

If the vertices are N points drawn at random in a d-dimensional cube, then the problem is known as random Euclidean matching problem. In this case, the cost l(e) of an edge is the usual Euclidean distance between two points. The mean field approximation of the problem has been investigated in [13, 14, 71–74].

Minimum/Maximum cut Given a graph G(V, E), the MIN-CUT (MAX-CUT) problem consists in finding the cut C(S, T ) of minimum (maximum) weight which partitions V into two subsets S, T . In Ising spin glasses, where the spins can be assigned to one of the two subsets according to their value σ = ±1, this problem corresponds to finding the cut which minimizes the number of broken bonds, i.e. the ground state. If there is no frustration in the system, there are algorithms which solve the problem in polynomial time. The problem is classified simple and can be solved in polynomial time. The MIN-CUT problem will be introduced in more detail in Section 4.2 and in Appendix C.

(29)

Chapter 2

Mean-field scenario

A standard procedure adopted in Statistical Mechanics for deriving the thermo-dynamic properties of a model consists in studying its mean field approximation, a ’simplified’ version of the problem. Since the complications derive usually from the presence of correlations in the system, in the mean-field approximation the partition function is assumed to be in some way factorizable, at the cost of neglecting correlations. At this level, the expressions for the free-energy and the correlation functions are derived in the thermodynamic limit by solving a set of saddle point equations in terms of the order parameter. In general, correlations are not neglectable and correlations must be eventually reintroduced in the model in a second stage by calculating the corrections to the mean-field approximation. Models which are exactly solvable in the mean-field theory are said mean-field models.

The purpose of this chapter is to introduce the main results achieved in the mean-field theory of spin glasses by means of two equivalent although formally very different methods. The replica approach was historically the first one to be used for solving the Sherrington-Kirkpatrick fully connected model, already introduced in the previous section, but the results required several years for obtaining a physical interpretation. The cavity method is a more intuitive probabilistic approach which was introduced few years later [13] and proved to be particularly effective for deriving the mean-field approximation of the Bethe lattice [10, 11] and in general to be implemented on optimization problems defined on sparse graphs.

2.1 The Sherrington-Kirkpatrick model

2.1.1 The replica approach

We consider a system of N Ising spins, with random interactions J drawn from a probability distribution P (J ), eventually in a random external field h, (see Sec. 1.2.2), with general Hamiltonian:

HJ[σ] = − X (i,j) Jijσiσj− X i hiσi (2.1)

where σ is a configuration of the system. For a system at equilibrium at temperature

(30)

Boltzmann-Gibbs distribution:

PJ[σ] = 1

ZJ

e−βH[σ], ZJ = Trσe−βH[σ] (2.2)

where β = 1/T is the inverse temperature and Z is the partition function. The partition function depends on the Hamiltonian HJ, and therefore on the particular realization of the disorder. However, as already seen in Sec. 1.2.1, one is usually interested in the behavior of the typical sample, and therefore thermodynamic quantities should be averaged over the P (J ) distribution. The free energy is thus given by Eq. (1.11):

f = fJ = − lim N →∞

1

βNlog ZJ (1.11)

The computation of ln ZJ is not straightforward, and requires a mathematical workaround known as replica trick. The method is based on the identity:

log Z = lim n→0

Zn− 1

n (2.3)

where Zn is the replicated partition function, which takes into account the space of

n identical independent replicas. The free-energy density is thus: f = − lim N →∞n→0lim 1 + Zn J n , Z n J = Trσne−βH n J _(2.4) where Hn=Pn

a=1HJ[sa] is the replicated Hamiltonian. Proceeding with the mean field approach, one first averages over the disorder, obtaining an integral which depends on a different Hamiltonian in which replicas are coupled. In this respect, it is convenient to introduce the overlap between replicas:

qab= 1 N X i σa_iσ_ib (2.5)

The averaged replicated partition function is:

Zn=Z_Jn= Z Y a<b dQab s N β2 2π exp −N A[Q] A[Q] = −nβ2/4 + β2/4 X 1≤a<b≤n Q2_ab− ln Z[Q] Z[Q] =X {S} exp −βH[Q, σ] H[Q, σ] = −β X 1≤a<b≤n Qabσaσb− h n X a=1 σn (2.6)

where Q is a n × n matrix whose coefficients represents couplings between replicas. The particular form of the partition function suggests that its thermodynamic limit can be computed through the saddle-point method, therefore:

fn≡ lim N →∞ 1 βN nln Zn= 1 βnmin A[Q] (2.7)

(31)

The minimum of A[Q] is found by solving a set of saddle points equations:

∂A ∂Qab

= 0 (2.8)

under the condition that the all the eigenvalues of the Hessian matrix Habcd =

∂2A/∂Qab∂Qcd are non negative. The saddle-point equations admit multiple solu-tions related by a symmetry, a concept known in Statistical Mechanics as symmetry

breaking. In this case, a solution A[Q] should be invariant under the group of

per-mutations of all replicas, called replica group. A solution is Replica Symmetric(RS) if the value of Qab does not depend on the indexes a, b. As soon as the non-diagonal elements of Qab depend on the indexes the replica symmetry is broken.

Replica Symmetric Solution. The simplest choice is to assume that all the replicas are equivalent:

∀a, b, a 6= b : Qab= q; ∀a : Qaa = 0 (2.9) This assumption is called Replica Symmetric Ansatz (RS). The last step consists in calculating the n → 0 limit of the replicated functions to obtain the thermodynamic quantities. We remark that the original order of the limits N → ∞ and n → 0 is here inverted, an operation which in principle is not straightforward and which was proved to be correct only twenty-five years after the formulation of the problem [75, 76].

At zero magnetic field, the analytical continuation of the solution of the equation

dA/dq = 0 provides a solution q = 0 for T > TC = 1, and q 6= 0 for T < TC = 1. Soon after the formulation of the RS solution [2] it was clear that the results presented some inconsistencies which led, for instance, to a negative entropy in the low temperature phase. The main problem is that the RS solution becomes unstable when positive eigenvalues of the Hessian matrix appear [77]. The instability appears along the critical de Almeida-Touless line (dAT line) h_c(T ) defined on the h, T plane. While the RS solution is stable above the dAT line, below the line the correct solution is achieved by a procedure known as replica symmetry breaking (RSB). In the SK model, the AT line diverges at T = 0, implying that there is no transition at zero temperature and the system is the RSB phase. This is an effect of infinite-range interactions, and in dilute models with finite connectivity the hc(T ) line converges to a finite value for T → 0.

Replica Symmetry Breaking. The RSB solution was formulated by Parisi in a series of articles [3, 4, 78] published few years after the original article of Sherrington and Kirkpatrick. The solution is found by an iterative approach which we illustrate for the first step.

At the first step (1RSB) the n replicas are grouped into k blocks of m₁ elements, such that k = n/m₁ _{∈ N. The 1RSB ansatz is:}

       Qab= q0 if I(a/m1) = I(b/m1) Qab= q1 if I(a/m1) 6= I(b/m1) Qaa = 0 if a = b (2.10)

Now every line has m1− 1 off diagonal elements with coefficient q1 and n − m with

(32)

minimized with respect to all the parameters to obtain a saddle-point solution. Even at this first stage, the results are much more satisfactory than the ones obtained with the RS solution, in terms of the corrections to the free energy, which is much more similar to the value obtained numerically, in terms of the entropy, which reduced by a factor ten, and in terms of the stability of the solution.

The procedure can be iterated at further levels of RSB. At each new level k, the diagonal blocks are partitioned hierarchically, and new parameters m_i, qi are introduced in the model. The full RSB solution is found in the k → ∞ limit. At each step, once the saddle-point solution is found, other equivalent solutions are found by a permutation of the replicas into each group, or by a permutation of the groups of replicas. This means that the group which leaves Q invariant is (Sm)⊗n/m⊗ Sn/m, where (S_m)⊗n/m is the direct product of the permutations group of m replicas with itself.

The order parameter Q(x) becomes a piecewise function defined by:

Q(x) = qi if mi < x < mi+1 (2.11)

In the k → ∞ limit it becomes eventually a continuous function:

Q(x) =        qm if x < xm q(x) with dq/dx > 0 if xm< x < xM qM if x > xM (2.12)

In general, x_m → x_M when the system approaches the dAT line from below, and the two values collapse above the dAT line. The full RSB solution is stable at low temperature and provides physically consistent thermodynamic quantities which are in very good agreement with the numerical simulations.

2.1.2 The spin glass order parameter

The meaning of RSB remains quite obscure as long as only replicas are involved, but it gets a clearer physical interpretation when the order parameter is expressed in terms of the overlap between states rather than replicas. The nature of the states in the spin glass phase is better understood in the TAP approach, introduced by Thouless, Anderson and Palmer [66, 79]. The results obtained within the TAP approach are not completely satisfactory but present the spin glass phase as characterized by a rough free-energy landscape with a large number of valleys. As the barriers become infinitely high in the thermodynamic limit, the ergodicity is broken, and the space of configurations is fragmented into pure states.

The usual Boltzmann measure must be decomposed in a sum of pure states:

< · >=X

α

wα< · >α (2.13)

In this sense the Gibbs state is not an equilibrium state, but rather a mixture of equilibrium states.

In order to describe to what extent two states differ from each other, a notion of distance or similarity between states is needed. The overlap between two states is

(33)

defined: qαβ = 1 N N X i=1 mα_imβ_i (2.14)

where mα and mβ are the magnetization of the system in two different states. The self-overlap qαα is the Edwards-Anderson order parameter:

qEA = qαα = 1

N < σi>

2

α (2.15)

and is supposed to be the maximum value of overlap. The probability for two random states to have overlap q is given by:

PJ(q) =

X

α,β

wαwβδ(q − qαβ), P (q) = PJ(q) (2.16)

It is convenient to define the integrated distribution:

x(q) =

Z q

−1

P (q0) dq0 (2.17)

which verifies: x(q_m) = 0, x(q_M) = 1. We recall that in the replica framework the order parameter is given by the n × n matrix Qab representing the overlaps between replicas. In the n → 0 limit the parameter becomes a continuous function

Q(x) defined between 0 and 1. The physical interpretation of the replica symmetry

breaking was given in [4], where it was shown how the inverse function q(x) of the integrated probability (2.17) is the same function as Q(x). In this respect, P (q) is the physical spin glass order parameter.

When the parameters h, T are above the dAT line, the spin glass phase is simple, since it consists only of one state. Thus, in the RS phase the overlap distribution has a sharp peak on the self-overlap:

PRS(q) = δ(q − qEA) (2.18)

This is also the case also of the paramagnetic phase, where qEA = 0.

Below the AT line, the RS solution is unstable, and the number and nature of the states depend on the particular spin glass model. In general the different models can be classified in two main categories, according to the type of RSB transition[12]:

Continuous Glass Transitions (full RSB). In this case, P (q) has form:

P (q) = xmδ(q − qm) + xMδ(q − qM) + ˜P (q) (2.19)

where ˜P (q) is a smooth continuous function defined in the interval [qm, qM].

Discontinuous Glass Transitions (1RSB). In this case, as the AT line is crossed, a new peak appears in q₁ at a value different from q₀ which characterized the RS phase. The width q1− q0 does not vanish as the system approaches the

(34)

Figure 2.1. Overlap distribution in a continuous (top) and discontinuous (bottom) phase

transition. The arrows indicate discrete delta distributions.

Several models have been studied with replica and cavity method and continuous transitions are typically observed in ordinary spin glasses with 2-spin interactions and in vertex coloring problems. Discontinuous transitions are observed in the spherical p-spin model with p ≥ 3, in random SAT problems and structural glasses.

The two-peaks structure of the 1RSB scenario has a simple geometrical inter-pretation. When two configurations are independently chosen from the Boltzmann measure, the overlap is with high probability q₀, or q₁. This means that the Boltz-mann measure concentrates in small regions of the configuration space, and the states can be clustered. With high probability, two independent random configurations in the same cluster have overlap q₁, and two configurations in distinct clusters have overlap q₀.

2.1.3 Ultrametricity

Beside the two spin correlations, one could study higher degrees of correlation and the related probability distribution. When the overlap between three spins is considered, for instance, remarkable properties appear in the spin glass phase.

Let us consider the distances between three randomly chosen states of a spin glass. The joint distribution of their mutual overlaps, in the replica formalism, is:

P (q1, q2, q3) = PJ(q1, q2, q3) = lim n→0 1 n(n − 1)(n − 2) X abc (Qab− q₁)(Qac− q₂)(Qbc− q₃) (2.20)

(35)

In the RSB parametrization it becomes: P (q1, q2, q3) = 1 2P (q1)x(q1)δ(q1− q2)δ(q3− q1)+ +1 2P (q1)P (q2)δ(q1− q2)δ(q3− q1)+ + permutations (2.21)

This distribution implies that either the three states are mutually equidistant or that two of the separations are equal and greater then the third. This property reveals a hierarchical structure in the overlaps between the various phases and it is known as ultrametricity.

A space M is ultrametric if the triangular inequality typical of the Euclidean space is replaced by the ultrametric condition:

d(x, z) = max[d(x, y), d(y, z)], ∀x, y, z ∈ M (2.22)

In unltrametric spaces, three points chosen at random form either an equilateral or an isosceles triangle with two sides longer than the third. An ultrametric ordering can be described by establishing a one-to-one correspondence between the points of the space and the end tips of the branches of a rooted tree. The distance between two points is proportional to the level at which the corresponding branches converge. An alternative consists in partitioning the space in clusters of equally distant points. Under ultrametricity, it can be shown that such a partition would cover the entire space in disjointed clusters of states.

2.1.4 The ultrametric tree of states

The arguments of the previous chapter show that the replica symmetry breaking yields the property of ultrametricity in the space of configurations. In this respect, ultrametricity is a more general geometric property, the simplest form of non-trivial organization arising in systems which admit a taxonomic classification [80]. Two questions arise at this point: the first is whether there is a more profound property of spin glasses which yields RSB and ultrametricity as a consequence; the second is whether there is a set of assumptions which, together with ultrametricity, are equivalent to RSB. The first question was answered by Guerra [81–83], who derived a set of stochastic stability identities, related to the stability of the system against a generic perturbation. In this respect stochastic stability is a theorem which has been proved to be valid in mean-field spin glasses, providing a more general explanation for RSB. The answer to the second question is that RSB can be obtained in an ultrametric system by considering generalized random free energies for the clusters of the system [5].

For a given cluster I, the "free energy" FI is defined by:

WI =

e−βFI

P

Ke−βFK

(2.23)

FI cannot be derived by solving this equation, but it is possible to guess the distributions of the FI’s at each level, and then check a posteriori that they return