Premium
Proof of the local REM conjecture for number partitioning. II. Growing 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.20256
Subject(s) - conjecture , mathematics , combinatorics , poisson distribution , spin glass , spectrum (functional analysis) , energy (signal processing) , order (exchange) , uncorrelated , distribution (mathematics) , statistical physics , physics , mathematical analysis , quantum mechanics , statistics , finance , economics
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