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

We consider the problem of partitioning n randomly chosen integers between I and 2(m) into two subsets such that the discrepancy, the absolute value o f 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 orig inal set is even, or 1 when the sum is odd. Parameterizing the random probl em in terms of kappa = m/n, we prove that the problem has a phase transitio n at kappa = 1, in the sense that for kappa < 1, there are many perfect par titions with probability tending to 1 as n --> infinity, whereas for kappa > 1, there are no per-feet partitions with probability tending to 1. Moreov er, we show that this transition is first-order in the sense the derivative of the so-called entropy is discontinuous at kappa = 1. We also determine the finite-size scaling window about the transition point: kappa (n) = 1 - (2n)(-1) log(2)n + lambda (n)/n, by showing that the probability of a perfe ct partition tends to 1, 0, or some explicitly computable p(lambda) epsilon (0, 1), depending on whether lambda (n) tends to -infinity, infinity lambd a epsilon (-infinity, infinity), respectively. For lambda (n) --> -infinity fast enough, we show that the number of perfect partitions is Gaussian in the limit. For lambda (n) --> -infinity, we prove that with high probabilit y the optimum partition is unique, and that the optimum discrepancy is Thet a (2(lambdan)). Within the window, i.e., if \ lambda (n)\ is bounded, we pr ove that the optimum discrepancy is bounded. Both for lambda (n) --> infini ty and within the window, we find the limiting distribution of the (scaled) discrepancy. Finally, both for the integer partitioning problem and for th e continuous partitioning problem, we find the joint distribution of the k smallest discrepancies above the scaling window. (C) 2001 John Wiley & Sons , Inc.