Proof of the Local REM Conjecture for Number Partitioning. I: Constant Energy Scales
In this article we consider the number partitioning problem (NPP) 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 NPP 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, Franc, 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. (C) 2008 Wiley Periodicals, Ins. Random Struct. Alg., 34, 217-240, 2009
random energy model poisson convergence combinatorial optimization