Search Results

In the past twenty-five years, the replica method has evolved into a rather sophisticated tool for attacking theoretical problems as diverse as spin glasses, protein folding, vortices in superconductors, combinatorial optimization, etc. Although it is not be the main tool of this book, it is nevertheless instructive to have some knowledge of replicas: the replica method is a non-trivial construction which is surprisingly powerful. Several of its most important predictions have been confirmed rigorously through alternative approaches. This chapter gives a compact account of the replica method. It describes the close connection between replica symmetry breaking and the Poisson–Dirichlet process, and it emphasizes the role played by ‘overlaps’ between replicas.

The main topic of this chapter is the problem posed to the mathematical community by the non-rigorous methods used by physicists in investigating mathematical problems. These methods are often highly successful in finding concrete results, but cannot be justified by standard methods. The chapter illustrates methods used by mathematicians in assimilating such non-rigorous techniques by reference to areas such as the umbral calculus of Blissard, Dirac's delta function, and the use of infinitesimals in calculus. It concludes with an example of an area where assimilation is currently incomplete, the replica method in statistical physics.

Real materials always contain randomness or disorder that cannot be expressed by idealized simple model systems. The present chapter studies the effects of randomness on phase transitions and critical phenomena. Although randomness may seem to obscure singular behaviour such as divergence of physical quantities at the critical temperature, it is established that well-defined phase transitions exist as long as randomness is not too strong, but the critical behaviour may get modified with respect to the pure sample. After the introduction of basic concepts and methods such as self-averaging and replica method, it is elucidated what type of phase transitions exist in the random-field Ising model and the SK model of spin glasses. Also explained are the percolation transitions using the fractal structure and the Potts model.

This chapter discusses the problem of spin glasses. If the interactions between spins are not uniform in space, the analysis of the previous chapter does not apply. In particular, when the interactions are ferromagnetic for some bonds and antiferromagnetic for others, the spin orientation cannot be uniform in space, unlike the ferromagnetic system. Under such a circumstance it sometimes happens that spins become randomly frozen — random in space but frozen in time. This is the intuitive picture of the spin glass phase. The chapter investigates the condition for the existence of the spin glass phase as an extension of the mean-field theory. In particular, the properties of the so-called replica-symmetric solution are explained in detail for the Sherrington–Kirkpatrick (SK) model.

Reliable transmission of information through noisy channels plays a vital role in modern society. Some aspects of this problem have close formal similarities to the theory of spin glasses. Noise in the transmission channel can be related to random interactions in spin glasses and the bit sequence representing information corresponds to the Ising spin configuration. The replica method serves as a powerful tool of analysis, and TAP-like equations can be used as a practical implementation of the algorithm to infer the original message. The gauge theory also provides an interesting point of view. This chapter introduces these problems.

A decision-making problem is often formulated as the minimization or maximization of a multivariable function, an optimization problem. This chapter shows that the methods of statistical mechanics are useful to study some types of optimization problems including the number partitioning, the graph partitioning, the knapsack problem, and the satisfiability problem. All these problems are shown to be formulated and solved using the theory of spin glasses, in particular the replica method. Then, discussions are continued on the mathematical properties of simulated annealing, an approximate numerical method for generic optimization problems.

This chapter starts with an introduction to the replica method, a standard method in statistical physics, along with a concrete application to the computation of the eigenvalue distribution of random matrices in the Gaussian orthogonal ensemble. The solution of the Sherrington–Kirkpatrick (SK) disordered spin-glass model is then derived, along with the phenomenon of replica symmetry breaking (RSB). The physical meaning of the RSB is explained. The ultrametricity of the space of pure states emerges as a consequence of the hierarchical RSB scheme. Moreover, it is shown how some low-temperature properties of physical observables can be derived by invoking the stochastic stability principle. Some rigorous results on the SK model are described: the existence of the thermodynamic limit, and the proof of the exactness of the hierarchical RSB solution.

In this chapter we present the minority game, which is one of the keystone models of econophysics. It is the mathematic implementation of the idea of inductive, rather than deductive, thinking. First, we explain how the agents adapt to each other, and how the efficiency of the system as a whole is increased by such an adaptation. Then the properties of the phase transition from efficient but non-ergodic to inefficient ergodic phase is discussed. In the following the replica formalism is introduced, and the full replica solution of the thermal batch minority game is shown. Finally, it is shown what modifications make the minority game useful as a model for stock-market fluctuations.

The cavity method is introduced as a heuristic framework from a physics perspective to solve probabilistic graphical models and is presented at both the replica symmetry (RS) and one-step replica symmetry breaking (1RSB) levels. This technique has been applied with success to a wide range of models and problems, such as spin glasses, random constraint satisfaction problems (rCSP), and error correcting codes. First, the RS cavity solution for the Sherrington–Kirkpatrick model—a fully connected spin glass model—is derived and its equivalence to the RS solution obtained using replicas is discussed. The general cavity method for diluted graphs is then illustrated at both RS and 1RSB levels. The latter was a significant breakthrough in the last decade and has direct applications to rCSP. Finally, as an example of an actual problem, k-SAT is investigated using belief and survey propagation.

One of the most challenging problems in probability and complexity theory is to establish and determine the satisfiability threshold, or phase transition, for random 3-SAT instances: Boolean formulas consisting of clauses with exactly k literals. As the previous part of the volume has explored, empirical observations suggest that there exists a critical ratio of the number of clauses to the number of variables, such that almost all randomly generated formulas with a higher ratio are unsatisfiable while almost all randomly generated formulas with a lower ratio are satisfiable. The statement that such a crossover point really exists is called the satisfiability threshold conjecture. Experiments hint at such a direction, but as far as theoretical work is concerned, progress has been difficult. In an important advance, Friedgut [177] showed that the phase transition is a sharp one, though without proving that it takes place at a “fixed” ratio for large formulas. Otherwise, rigorous proofs have focused on providing successively better upper and lower bounds for the value of the (conjectured) threshold. In this chapter, our goal is to review the series of improvements of upper bounds for 3-SAT and the techniques leading to these. We give only a passing reference to the improvements of the lower bounds as they rely on significantly different techniques, one of which is discussed in the next chapter. Let ϕ be a random k-SAT formula constructed by selecting, uniformly and with replacement, ra clauses from the set of all possible clauses with k literals (no variable repetitions allowed within a clause) over n variables. It has been experimentally observed that as the numbers m, n of variables and clauses tend to infinity while the ratio or clause density m/n is fixed to a constant a, the property of satisfiability exhibits a phase transition. For the case of 3-SAT, when a is greater than a number that has been experimentally determined to be approximately α < 4.27, then almost all random 3-SAT formulas are unsatisfiable; that is, the fraction of unsatisfiable formulas tends to 1.