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

Considered is the problem of partitioning \(n\) randomly chosen integers between 1 and \(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 or 1. It is proved that there exists a perfect partition with probability 1 or 0 according to whether \(2-\log(M)/n\) has a limit less than 1 or larger than 1 as \(M\) and \(n\) tend to infinity. This result is strengthened to establish the existence of a scaling window. Furthermore, detailed information is given on the distribution of the numbers of perfect and optimum partitions. Distributional estimates of the discrepancy are also given.