Proof of the Local REM Conjecture for Number Partitioning II: Growing Energy Scales

Random Struct. Algorithms |

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 ! 1, 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 ·n1=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.