ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

0. Plenary Lectures

1991 MS Classification: Michel Talagrand, C. N. R. S., Université Paris VI, France Huge random structures and mean field models for spin glasses

Consider a large population, the individuals being labeled 1 to N. Assume that any pair (ϵ_{ij}), i < j of them know each other, and let g_{ij} measure their respective feelings. In particular g_{ij} > 0 when they are friends, g_{ij} < 0 when they are enemies. Assume that (as a consequence of brilliant minds and strong personalities) the numbers (g_{ij}) are independent standard normal random variables. Then for many triples i, j, k, i is a friend of both j and k, but j and k are enemies. This creates a rather tense situation. To alleviate the problem, one can try to split the population in two parts, trying, as far as possible to put friends together and enemies apart. To determine to which group individual i belongs we assign to it a number σ_{i} ∈ {−1, 1}, using the fact that there is a one to one correspondence between the sequences σ σ σ = (σ_{i})_{i≤N} and the partitions of {1, ⋯, N}. The function

H(σ σ σ) = ∑_{i<j} σ_{i}σ_{j}g_{ij}

that adds the interaction numbers g_{ij} of pairs in each group and subtract them for pairs in different groups is a natural measure of how successful the given partition is. How large can H(σ σ σ) be? Finding σ σ σ that maximizes H(σ σ σ) is an extremely difficult optimization problem. Numerical evidence (and extraordinarily clever speculation from the physicists) suggests that, for N large,

max_{σ σ σ} H(σ σ σ) ≃ .7633N^{3/2}

(Comparing to the natural scaling factor N^{2}, the philosophy of this is that splitting the population does not really improve matters). Suppose now that, instead of individuals, we are dealing with magnetic impurities, and that σ_{i} represents the spin of impurity i. As a first approximation, we need not be concerned about the precise location of the impurities, and we can assume that each of them interacts equally with all the other impurities of the sample (a so called mean field model). Then a very natural candidate for the energy of configuration σ σ σ is

H(σ σ σ) = −\frac{1}{\sqrt{N}} ∑_{i<j} σ_{i}σ_{j}g_{ij} − ∑_{i≤N} hσ_{i} (1)

There the minus sign follows physic’s convention; the factor 1/\sqrt{N} is an appropriate normalization (to ensure that H(σ σ σ)/N remains bounded) and h is an external field, that favors the plus spins over the minus ones. Formula (1) is the Hamiltonian of the famous Sherrington-Kirkpatrick (SK) model for spin glasses. Rather than just being concerned with the minimum of H(σ σ σ), (i. e. the ground state energy), statistical mechanics brings in an inverse temperature β and considers Gibb’s measure, a probability on the set of all configurations given by

G(σ σ σ) = Z^{−1} exp(−βH(σ σ σ))

where Z = ∑_{σ σ σ} exp(−βH(σ σ σ)) is a normalization factor. Thus G gives large

weight to the configurations with low energy, and all the more so when β is large (low temperature). Gibbs’ measure is a random object (through the g_{ij}) and the problem is to understand its typical structure for N large. The physicists have put much effort into this question, and have obtained a very precise picture (although mathematicians might object to some of their methods, that involve concepts such as functions of a negative number of variables, diagonalization of matrices of dimension 0 × 0, and more). It is believed that at given h, if β ≤ β(h) the system “is in a pure state” (in a sense that will be made mathematically precise). This behavior will be called the high temperature region. On the other hand, if β > β(h) (the low temperature region) it is believed that the system exhibits a very complex structure (the Parisi solution) involving in particular a spontaneous breaking of the system into different states (which means that when we observe the system at very long intervals we might see what appears to be different objects). Besides the fascinating fact that the simple Hamiltonian (1) gives rise to extreme subtlety, the importance of this subject is that a number of (apparently unrelated) random combinatorial problems of considerable importance exhibit similar behavior. For example, let us consider the discrete cube Σ_{N} = {−1, 1}^{N} in dimension N, and half spaces at a given distance from the origin, oriented in random directions. What is the typical size of their intersection with Σ_{N}? (a problem motivated by the theory of neural networks). To bring in statistical mechanics, one introduces the Hamiltonian on Σ_{N} defined at σ σ σ by counting the number of random half spaces to which σ σ σ belongs. Or consider the random K-sat problem, which is to know what proportion of the truth assignments of N Boolean variables will simultaneously satisfy M random clauses of length K. For all these models and others (among which the famous Hopfield model of associative memory) we have been able to prove that the physicist’s magical formulas are indeed true at high enough temperatures, and for several of these models we obtained a very precise picture (capturing all effects of size 1/\sqrt{N}). High temperature results are motivated by the fact that for several models, the “high temperature” region is thought to extend all the way to temperature zero. But of course, the main challenge is the low temperature region. There also has been progress there. For the p-spin interaction model (closely related to the SK model), we did succeed in rigorously proving the most striking prediction of physics: the spontaneous appearance of different “states”, any two of them very far apart.