Proof of the local REM conjecture for number partitioning. II. Growing energy scales

We continue our analysis of the number partitioning problem with n weights chosen i.i.d. from some fixed probability distribution with density ρ. In Part I of this work, we established the so‐called local REM conjecture of Bauke, Franz and Mertens. Namely, we showed that, as n → ∞, the suitably rescaled energy spectrum above some fixed scale α tends to a Poisson process with density one, and the partitions corresponding to these energies become asymptotically uncorrelated. In this part, we analyze the number partitioning problem for energy scales α n that grow with n , and show that the local REM conjecture holds as long as n ‐1/4 α n → 0, and fails if α n grows like κ n 1/4 with κ > 0. We also consider the SK‐spin glass model, and show that it has an analogous threshold: the local REM conjecture holds for energies of order o ( n ), and fails if the energies grow like κ n with κ > 0. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009