Premium
Proof of the local REM conjecture for number partitioning. I: Constant energy scales
Author(s) -
Borgs Christian,
Chayes Jennifer,
Mertens Stephan,
Nair Chandra
Publication year - 2009
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20255
Subject(s) - conjecture , mathematics , spin glass , partition (number theory) , combinatorics , uncorrelated , probabilistic logic , energy (signal processing) , spin (aerodynamics) , constant (computer programming) , poisson distribution , discrete mathematics , quantum mechanics , physics , statistics , computer science , thermodynamics , programming language
In this article we consider the number partitioning problem (N PP ) in the following probabilistic version: Given n numbers X 1 ,…, X n drawn i.i.d. from some distribution, one is asked to find the partition into two subsets such that the sum of the numbers in one subset is as close as possible to the sum of the numbers in the other set. In this probabilistic version, the N PP is equivalent to a mean‐field antiferromagnetic Ising spin glass, with spin configurations corresponding to partitions, and the energy of a spin configuration corresponding to the weight difference. Although the energy levels of this model are a priori highly correlated, a surprising recent conjecture of Bauke, Franz, and Mertens asserts that the energy spectrum of number partitioning is locally that of a random energy model (REM): the spacings between nearby energy levels are uncorrelated. More precisely, it was conjectured that the properly scaled energies converge to a Poisson process, and that the spin configurations corresponding to nearby energies are asymptotically uncorrelated. In this article, we prove these two claims, collectively known as the local REM conjecture. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009