Proof of the local REM conjecture for number partitioning I: Constant energy scales

In this paper we consider the number partitioning problem (Npp) in the following probabilistic version: Given n numbers X1;…;Xn 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, 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 paper, we prove these two claims, collectively known as the local REM conjecture.