Phase transition and finite‐size scaling for the integer partitioning problem

Abstract

Abstract We consider the problem of partitioning n randomly chosen integers between 1 and 2 m into two subsets such that the discrepancy, the absolute value of the difference of their sums, is minimized. A partition is called perfect if the optimum discrepancy is 0 when the sum of all n integers in the original set is even, or 1 when the sum is odd. Parameterizing the random problem in terms of κ= m / n , we prove that the problem has a phase transition at κ=1, in the sense that for κ<1, there are many perfect partitions with probability tending to 1 as n →∞, whereas for κ>1, there are no perfect partitions with probability tending to 1. Moreover, we show that this transition is first‐order in the sense the derivative of the so‐called entropy is discontinuous at κ=1. We also determine the finite‐size scaling window about the transition point: κ n =1−(2 n ) −1 log 2 n +λ n / n , by showing that the probability of a perfect partition tends to 1, 0, or some explicitly computable p (λ)∈(0, 1), depending on whether λ n tends to −∞, ∞, or λ∈(−∞, ∞), respectively. For λ n →−∞ fast enough, we show that the number of perfect partitions is Gaussian in the limit. For λ n →∞, we prove that with high probability the optimum partition is unique, and that the optimum discrepancy is Θ(2 ). Within the window, i.e., if |λ n | is bounded, we prove that the optimum discrepancy is bounded. Both for λ n →∞ and within the window, we find the limiting distribution of the (scaled) discrepancy. Finally, both for the integer partitioning problem and for the continuous partitioning problem, we find the joint distribution of the k smallest discrepancies above the scaling window. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 247–288, 2001