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.