format: text

text:
# Phase Diagram for the Constrained Integer Partitioning Problem.

## 1 Introduction

Phase transitions in random combinatorial problems have been the subject of much recent attention. The random optimum partitioning problem is the only NP-hard problem for which the existence of a sharp phase transition has been rigorously established, as have many detailed properties of the transition (, see  for a short overview). Here we study a constrained version of the random optimum partitioning problem, and extend some of the results of  to that case.

The integer optimum partitioning problem is a classic problem of combinatorial optimization in which a given set of $`n`$ integers is partitioned into two subsets in order to minimize the absolute value of the difference between the sum of the integers in the two subsets, the so-called discrepancy. Notice that for any given set of integers, the discrepancies of all partitions have the same parity, namely that of the sum of the $`n`$ integers. We call a partition perfect if its discrepancy is $`0`$, when this sum is even, or $`1`$, when this sum is odd. The decision question is whether there exists a perfect partition. In the uniformly random version, an instance is a given a set of $`n`$ i.i.d. integers drawn uniformly at random from $`\{1,2,\mathrm{},M\}`$. We will sometimes use the notation $`m=\mathrm{log}_2M`$; notice that each of the random integers has $`m`$ binary bits. Previous work had established a sharp transition as a function of the parameter $`\kappa :=m/n`$, characterized by a dramatic change in the probability of a perfect partition. For $`M`$ and $`n`$ tending to infinity in the limiting ratio $`\kappa =m/n`$, the probability of a perfect partition tends to $`0`$ for $`\kappa <1`$, while the probability tends to $`1`$ for $`\kappa >1`$. This result was suggested by the work of one of the authors  and proved in a paper by the three other authors . See  for a beautiful introduction to the optimum partitioning phase transition and some of its properties.

Here we consider a constrained variant of the problem in which we require that the two subsets have given cardinalities; we say that the difference of the two cardinalities is the bias, $`s`$, of the partition. We establish the phase diagram of the random constrained integer partitioning problem as a function of the two parameters $`\kappa :=m/n`$ and $`b:=|s|/n`$. In the language of statistical physics, $`b`$ would be called the magnetization, and the problem considered here, where $`b`$ is constrained to assume a particular value, would be called the “microcanonical” integer partitioning problem. Microcanonical problems are known to be much more difficult than their unconstrained analogues, particularly in the case of random systems.

Let us first review previous rigorous and nonrigorous work on the random optimum partitioning problem. A good deal of rigorous work has been done for the unconstrained random partitioning problem with random numbers drawn from a compact interval in $``$, which can be interpreted informally as the limiting case of $`mn`$. Karmarkar and Karp  gave a linear time algorithm for a suboptimal solution with a typical discrepancy of order at most $`O(n^{c\mathrm{log}n})`$ for some constant $`c>0`$. Confirming a conjecture by Karmakar and Karp, Yakir  proved that the expected discrepancy delivered by this algorithm is indeed $`n^{\theta (\mathrm{log}n)}`$. The optimum solution was studied by Karmarkar, Karp, Lueker and Odlyzko  who proved that the typical minimum discrepancy is much smaller, with the median of order $`\theta (2^nn^{1/2})`$. More recently, Lueker  proved exponential bounds for the expected minimum discrepancy. Loosely speaking, these results correspond to $`m`$ far exceeding $`n`$, and hence $`\kappa \mathrm{}`$, thus well above the phase transition of the unconstrained problem which occurs for $`\kappa =1`$.

There have also been (nonrigorous) studies of optimum partitioning in the theoretical physics and artificial intelligence communities, where the possibility of a phase transition was examined. Fu  noted that the minimum discrepancy is analogous to the ground state energy of an infinite-range, random antiferromagnetic spin model, but concluded incorrectly that the model did not have a phase transition. Gent and Walsh  studied the problem numerically and introduced the parameter $`\kappa =m/n`$. They noticed that the number of perfect partitions falls off dramatically at a transition point estimated to be close to $`\kappa =0.96`$. Ferreira and Fontanari studied the random spin model of Fu, and used statistical mechanical methods to get estimates of the optimum partition  and to evaluate the average performance of simple heuristics . Ferreira and Fontanari  also considered the constrained optimum partitioning problem, noted that the constrained problem is analogous to putting the random antiferromagnet in an external field, and observed that the problem becomes much easier when the bias parameter $`b`$ satisfies $`b>\sqrt{2}1`$.

Returning to the unconstrained problem, one of the authors of this paper used statistical mechanical methods and the parameterization of Gent and Walsh to derive a compelling, but nonrigorous argument for a phase transition at $`\kappa =1`$, and also derived many of the properties of the transition . In a later work, this author  analyzed Fu’s model by using a heuristic approximation known in statistical mechanics as Derrida’s random energy model , and obtained the limiting distribution of the $`k`$-th smallest discrepancy.

Motivated by the statistical mechanics analysis in  and , the other three authors of this paper undertook an extensive rigorous study of the random integer partitioning problem . They established the existence of a transition at $`\kappa _c=1`$ below which the probability of a perfect partition tends to one with $`n`$ and $`m`$, and above which it tends to zero, and also gave the finite-size scaling window of the transition: namely, in terms of the more detailed parametrization $`m=\kappa _n`$ with $`\kappa _n=1\mathrm{log}_2n/(2n)+\lambda _n/n,`$ the probability of a perfect partition tends to $`1`$, $`0`$, or a computable $`\lambda `$-dependent constant strictly between $`0`$ and $`1`$, depending on whether $`\lambda _n`$ tends to $`\mathrm{}`$, $`\mathrm{}`$, or $`\lambda (\mathrm{},\mathrm{})`$, respectively. The work also calculated the distribution of the number of perfect partitions, the distribution of the minimum discrepancy, and the joint distribution of the $`k`$ smallest discrepancies, which give the entropy, the ground state energy and the bottom of the energy spectrum, respectively. In particular, the paper  provided a rigorous justification of the Derrida-type approximation both inside and above the scaling window, insofar as the joint distribution of $`k`$ (finite) smallest discrepancies is concerned.

The location of the phase transition for the unconstrained problem immediately yields a one-dimensional phase diagram as a function of $`\kappa `$: For $`\kappa (0,\kappa _c)`$ with $`\kappa _c=1`$, the system is in a “perfect phase” in which the probability of a perfect partition tends to $`1`$ as $`M`$ and $`n`$ tend to infinity in the fixed function $`\kappa `$. For $`\kappa (\kappa _c,\mathrm{})`$, the probability of a perfect partition tends to $`0`$, and moreover, there is an unique optimal partition. We call this the “hard phase,” since for $`\kappa >\kappa _c`$, it is presumably computationally difficult to find the optimal partition.

In this work, we consider the constrained optimum partitioning problem with bias $`s`$ and extend the phase diagram to the two-dimensional $`\kappa b`$-plane. See Figure 1. In addition to the extensions of the perfect and hard phases, we establish the existence of a new phase which we call the “sorted phase.”

The sorted phase is easy to understand. One way to meet the bias constraint is to take the $`(s+n)/2`$ smallest integers and put them in one subset of the partition.111Note that the task of finding this partition is even easier than the task of sorting the $`n`$ integers, which would take, on average, $`\theta (n\mathrm{log}n)`$ comparisons. Instead, the $`(s+n)/2`$ smallest integers can be found in strictly linear time in $`n`$. It is not difficult to see that the resulting “sorted partition” is optimal if the total weight of this subset is at least half of the sum of all $`n`$ integers. We define the sorted phase as the subset of the $`\kappa b`$-plane where the sorted partition is optimal. We prove that the sorted phase is given by the condition

$$b>b_c:=\sqrt{2}1,$$
(1.1)
see region III in Figure 1. Moreover, we show that the minimal discrepancy in this phase is of the order $`Mn`$. The region $`b>\sqrt{2}1`$ is precisely where Ferreira and Fontanari  observed that the corresponding statistical mechanical problem becomes “self-averaging.”

Our analysis of the perfect and hard phases for $`b<b_c`$ is much more difficult. In this region, we use integral representations for the number of partitions with a given discrepancy and bias; these representations generalize those used in . The asymptotic analysis of the resulting two-dimensional random integrals leads to saddle point equations for a saddle point described in terms two real parameters $`\eta `$ and $`\zeta `$. For discrepancies of order $`o(M)`$ (including, in particular, the case of perfect partitions), the saddle point equations determining $`\zeta `$ and $`\eta `$ are:

$`{\displaystyle \underset{0}{\overset{1}{}}}x\mathrm{tanh}(\zeta x+\eta )𝑑x=0,`$ (1.2)
$`{\displaystyle \underset{0}{\overset{1}{}}}\mathrm{tanh}(\zeta x+\eta )𝑑x=b.`$
The solution $`(\zeta ,\eta )`$ of these equations can be used to define the two convex curves in Figure 1. To this end, let222It turns out the solutions of the saddle point equations 1.2 are just the stationary points of the function $`L(\zeta ,\eta )`$

$$L(\zeta ,\eta ):=b\eta +\underset{0}{\overset{1}{}}\mathrm{log}(2\mathrm{cosh}(\zeta x+\eta ))𝑑x$$
(1.3)
$$\rho (\zeta ,\eta ):=1\frac{\mathrm{tanh}(\zeta +\eta )\mathrm{tanh}(\eta )}{2\zeta }.$$
(1.4)
For $`(\zeta ,\eta )`$ a solution of (1.2), we then define

$`\kappa _{}(b):`$ $`=\mathrm{log}_2\rho (\zeta ,\eta ),`$ (1.5)
$`\kappa _c(b):`$ $`=\frac{1}{\mathrm{log}2}L(\zeta ,\eta ).`$
From bottom to top, the two convex curves joining $`(0,b_c)`$ and $`(1,0)`$ in Figure 1 are then given by $`\kappa =\kappa _{}(b)`$ and $`\kappa =\kappa _c(b)`$.

In this paper, we prove that, in the region $`\kappa <\kappa _{}(b)`$, with probability tending to one as $`n`$ tends to infinity (or, more succinctly, with high probability, w.h.p.) there exist perfect partitions; see region I in Figure 1. Moreover the number of perfect partitions is about $`2^{(\kappa _c\kappa )n}`$ in this “perfect phase.” We also prove that w.h.p. there are no perfect partitions in the region $`b<b_c`$ and $`\kappa >\kappa _c(b)`$. As in the unconstrained problem, we call this the “hard phase.” Our results leave open the question of what happens in the narrow region $`\kappa _{}<\kappa <\kappa _c`$, and also whether the optimal partition is unique in the hard phase; see the final section for a discussion of this and other open questions.

We are also able to prove that these phase transitions correspond to qualitative changes in the solution space of the associated linear programming problem (LPP). In the actual optimum partitioning problem, each integer is put in one subset or the other. The relaxed version is defined by allowing any fraction of each integer to be put in either of the two partitions. Using our theorems on the typical behavior of integer partitioning problem and some general properties of the LPP, we show the following. In the sorted phase, i.e. for $`b>b_c=\sqrt{2}1`$, w.h.p. the LPP has a unique solution given by the sorted partition itself. For $`b<b_c`$, i.e. in the perfect and hard phases, w.h.p. the relaxed minimum discrepancy is zero, and the total number of optimal basis solutions is exponentially large, of order $`2^{k_c(b)n+O_p(n^{1/2})}`$. Finally, in the perfect and hard phases, we consider the fraction of these basis solutions whose integer-valued components form an optimal integer partition of the subproblem with the corresponding subset of the weights. We show that this fraction is exponentially small. Moreover, except for the crescent-shaped region between $`\kappa =\kappa _{}(b)`$ and $`\kappa =\kappa _c(b)`$, we show that the fraction is strictly exponentially smaller in the hard phase than in the perfect phase. This fraction thus represents some measure of the algorithmic difficulty of the problem, see Remark 8.1.

The outline of the paper is as follows. In the next section, we define the problem in detail, and precisely state our main results. In Section 3, we introduce our integral representation and show how it leads to the relevant saddle point equations. We also give a brief heuristic derivation of some of the phase boundaries. Section 4 contains a proof of existence and properties of the solution of the saddle point equations for $`b<b_c`$. In Section 5, we establish an asymptotic formula for the number of partitions with given discrepancy and bias in the perfect phase. As a corollary, we obtain both the existence of exponentially many perfect partitions for $`\kappa <\kappa _{}(b)`$, and a theorem on the distribution of the bias in the unconstrained problem for $`\kappa <1`$. The analysis of the hard phase is done in Section 6. In Section 7, we prove that the sorted partitions are optimal for $`b>b_c`$. We also show why the sorted phase boundary coincides with the boundary for existence of solutions of the saddle point equations. In Section 8, we formulate the relaxed version of the optimum partitioning problem, and establish our results on the space of basis solutions of the LPP. Finally, in Section 9, we discuss open problems and a few numerical experiments addressing some of these problems.

## 2 Statement of Main Results

Let $`X_1,\mathrm{},X_n`$ be $`n`$ independent copies of a generic random variable which is distributed uniformly on $`\{1,\mathrm{},M\}`$. We are interested in the case when $`M`$ grows exponentially with $`n`$, and define $`\kappa `$ as the exponential rate, i.e.

$$\kappa =\frac{1}{n}\mathrm{log}_2M.$$
(2.1)
To avoid trivial counterexamples, we will always assume that $`\kappa `$ stay bounded away from both $`0`$ and $`\mathrm{}`$ as $`n\mathrm{}`$. We will use $``$ and $`𝔼`$, with or without subindex $`n`$, to denote the probability measure and the expectation induced by $`𝕏=(X_1,\mathrm{},X_n)`$.

A partition of integers into two disjoint subsets is coded by an $`n`$-long binary sequence $`𝝈=(\sigma _1,\mathrm{},\sigma _n),\sigma _j\{1,1\}`$; so the subsets are $`\{j:\sigma _j=1\}`$ and $`\{j:\sigma _j=1\}`$. Obviously $`𝝈`$ and $`𝝈`$ are the codes of the same partition. Given a partition $`𝝈`$, we define its discrepancy (or energy), $`d(𝕏,𝝈)`$, and bias (or magnetization), $`s(𝝈)`$, as

$`d(𝕏,𝝈)=`$ $`|𝝈𝕏|,\text{ with }𝝈𝕏={\displaystyle \underset{j=1}{\overset{n}{}}}\sigma _jX_j,`$ (2.2)
$`s(𝝈)=`$ $`𝝈𝕖=|\{j:\sigma _j=1\}||\{j:\sigma _j=1\}|.`$ (2.3)
Here $`𝕖`$ is the vector $`(1,\mathrm{},1)`$. Clearly $`s(𝝈)`$ is an integer in $`\{n,\mathrm{},n\}`$, so let $`s\{n,\mathrm{},n\}`$ and define the bias density

$$b=\frac{|s|}{n}$$
(2.4)
so that $`b[0,1]`$. Note that by symmetry it suffices to consider $`s(𝝈)\{0,\mathrm{},n\}`$, so we will often take a non-negative integer $`s\{0,\mathrm{},n\}`$, in which case $`s=bn`$. We define an optimum partition as a partition $`𝝈`$ that minimizes the discrepancy $`d(𝕏,𝝈)`$ among all the partitions with bias equal to $`s`$, and a perfect partition as a partition $`𝝈`$ with $`|d(𝕏,𝝈)|1`$.

Theorems B, C and D below describe our main results on the phases labelled I, II, and III in Figure 1 in the introduction. In the statement of these theorems we will use the parameters $`\zeta ,\eta ,\kappa _c(b)`$ and $`\kappa _{}(b)`$ defined in (1.2) – (1.5). Before getting to principal results, we must begin with an existence statement for the parameters $`\zeta ,\eta `$.

###### Theorem A

Let $`b<b_c`$, where $`b_c=\sqrt{2}1`$. Then the saddle point equations (1.2) have a unique solution $`(\zeta ,\eta )=(\zeta (b),\eta (b))`$.

This theorem is proved in Section 4.

Let

$$Z_n(\mathrm{},s)=Z_n(\mathrm{},s;𝕏)$$
(2.5)
denote the random number of partitions $`𝝈`$ with $`𝝈𝕏=\mathrm{}`$ and $`𝝈𝕖=s`$. Since $`s(𝝈)`$ has the same parity as $`n`$, and $`d(𝕏,𝝈)`$ has the same parity as $`_{j=1}^nX_j`$, we will only consider values of $`s`$ which have the same parity as $`n`$, and values of $`\mathrm{}`$ which have the same parity as $`_{j=1}^nX_j`$. In the theorems in this section and in much of the rest of the paper, we will not state these restrictions explicitly.

Our central goal is to use the saddle point solution in order to bound the $`Z_n(\mathrm{},s)`$ for various given values of $`\mathrm{}`$ and $`s`$. To formulate our results in a compact, yet unambiguous form, we use a shorthand $`a_n<a`$ ($`a_n>a`$, resp.) instead of $`lim\; supa_n<a`$ ($`lim\; infa_n>a`$, resp.), even when the $`n`$-dependence of $`a_n`$ is only implicit, as in $`\kappa =n^1\mathrm{log}_2M`$ and $`b=|s/n|`$. We will also use the notation $`f_n=O_p(g_n)`$ and $`f_n=o_p(h_n)`$ if $`f_n/g_n`$ is bounded in probability and $`f_n/h_n`$ goes to zero in probability, respectively. Also, as is customary, we will say that an event happens with high probability (w.h.p.) if the probability of this event approaches $`1`$ as $`n\mathrm{}`$. In all our statements $`n`$, $`M`$, $`s`$ and $`\mathrm{}`$ will be integers with $`n1`$, $`M1`$ and $`s0`$. Our main results in the perfect phase are summarized in the next theorem and remark.

###### Theorem B

Let $`\mathrm{}=o(Mn^{1/2}),b<b_c`$ and $`\kappa <\kappa _{}(b)`$. Then w.h.p. $`Z_n(\mathrm{},s)1`$ and

$$Z_n(\mathrm{},s)=2^{[\kappa _c(b)\kappa ]n}e^{S_nn^{1/2}+o(n^{1/2})},$$
(2.6)
where $`S_n`$ converges in probability to a Gaussian with mean zero and variance $`\sigma ^2=\text{Var}(\mathrm{log}(2\mathrm{cosh}(\zeta U+\eta )))`$, with $`U`$ uniformly distributed on $`[0,1]`$. Consequently, w.h.p., there exist exponentially many perfect partitions, with $`\mathrm{}=0`$ if $`_jX_j`$ is even, and $`|\mathrm{}|=1`$ if $`_jX_j`$ is odd.

###### Remark 2.1

Under the conditions of Theorem B, we actually prove a much more accurate estimate. Namely, we show that there are $`2\times 2`$ positive definite matrices $`R`$ and $`K`$ with deterministic entries, and a constant $`q<1`$ such that, with probability $`1O(q^{\mathrm{log}^2n})`$,

$$Z_n(\mathrm{},s)=\mathrm{exp}\left(\zeta \frac{\mathrm{}}{M}+\eta s+\underset{j=1}{\overset{n}{}}\mathrm{log}(2\mathrm{cosh}(\zeta X_j/M+\eta ))\right)\frac{\mathrm{exp}(\frac{1}{4}𝝉_nR^1𝝉_n^{})}{\pi Mn\sqrt{\text{det }R}}(1+o(1)).$$
(2.7)
Here $`𝛕_n`$ is a two-dimensional random vector which converges in probability to a Gaussian vector $`𝛕`$ with zero mean and covariance matrix $`K`$. See Theorem 5.1 in Section 5.1.

We also prove a corollary relating the distribution of the bias in the unconstrained problem to the distribution of the bias between heads and tails in fair coin flips; see Subsection 5.2.

The proof of Theorem B and Remark 2.1 is given in Section 5.

Note that the above expression for $`Z_n(\mathrm{},s)`$ is much more complicated than its analogue in the unconstrained case, see equation (2.6) in . Both the sum in the first exponent and the entire second exponent represent fluctuations which were not present in the unconstrained case, and which make the analysis of the perfect phase much more difficult here; see also Remark 2.4 below.

Our next theorem, which describes our main results on the hard phase, has two parts: The first shows that there are no perfect partitions above $`\kappa =\kappa _c(b)`$, and the second gives a bound on the number of optimum partition for $`\kappa >\kappa _{}`$. To state the theorem, let $`d_{opt}=d_{opt}(n;s)`$ denote the discrepancy of the optimal partition, and let $`Z_{opt}=Z_{opt}(n;s)`$ denote the number of optimal partitions.

###### Theorem C

Let $`b<b_c`$.

1. If $`\kappa >\kappa _c(b)`$, then there exists a $`\delta >0`$ such that with probability $`1O(e^{\delta \mathrm{log}^2n})`$ there are no perfect partitions, and moreover

$$d_{opt}2^{n[\kappa \kappa _c(b)]O_p(n^{1/2})}.$$
(2.8)
2. If $`\kappa >\kappa _{}(b)`$ and $`\epsilon >0`$, then there exists a constant $`\delta >0`$ such that

$$d_{opt}2^{n[\kappa \kappa _{}(b)+\epsilon ]},$$
(2.9)
and

$$Z_{opt}2^{n[\kappa _c(b)\kappa _{}(b)+\epsilon ]},$$
(2.10)
both with probability $`1O(e^{\delta \mathrm{log}^2n})`$.

This theorem is proved in Section 6. However, perhaps somewhat surprisingly, the proof of the upper bound in (2.9) runs parallel to the proof of Theorem B that established existence of perfect partitions for $`\kappa <\kappa _{}(b)`$.

###### Remark 2.2

We believe that the bound in (2.8) is actually sharp. If we assume that this is the case, in fact, even if we assume that the weaker bound

$$d_{opt}=2^{n(\kappa \kappa _c+o_p(1))}$$
(2.11)
holds w.h.p. whenever $`\kappa >\kappa _c`$, then we can significantly improve the upper bound (2.10). Indeed, under the assumption (2.11), $`Z_{opt}`$ grows subexponentially with $`n`$ whenever $`\kappa >\kappa _c(b)`$, see Remark 6.1 (iii).

The optimum partition problem is much simpler for $`b>b_c`$. Our main result on the sorted phase is the following theorem, which is proved in Section 7.

###### Theorem D

Let $`b>b_c`$. Then w.h.p. the optimal partition is uniquely obtained by putting $`(s+n)/2`$ smallest integers $`X_j`$ in one part, and the remaining $`(ns)/2`$ integers into another part. W.h.p., $`d_{opt}`$ is asymptotic to $`\frac{Mn}{4}\left[(1+b)^22\right]`$, i.e., of order $`Mn`$.

By this theorem, for $`b`$ sufficiently large, the partition is determined by the decreasing order of weights $`X_j`$, but not by the actual values of $`X_j`$.

Until now, all our statements have been about the likely properties of the optimum partition $`𝝈`$, whose components are allowed to assume only two values, $`1`$ and $`+1`$. In an interesting twist, these results shed light on the likely properties of the related linear programming problem (LPP): find the minimum value of $`d`$ subject to linear constraints

$`d{\displaystyle \underset{j=1}{\overset{n}{}}}\sigma _jX_j,{\displaystyle \underset{j=1}{\overset{n}{}}}\sigma _jX_jd,`$
$`{\displaystyle \underset{j=1}{\overset{n}{}}}\sigma _j=s,`$
$`1\sigma _j1,(1jn).`$
We denote this minimum value of $`d`$ by $`d_{opt}^{LPP}`$. Our last theorem indicates that the LPP inherits the phase diagram of the optimum partition problem, and moreover provides, however incomplete, some way to rate the three regions according the algorithmic difficulty of the optimal partition problem. To make this precise, we define $`F_n(\kappa ,b)`$ to be the fraction of basis solutions $`𝝈`$ with the property that the $`\pm 1`$-valued components $`\sigma _i`$ form an optimal partition of the corresponding subproblem with weights $`X_i`$. Henceforth, we will call this the “optimal subpartition property.”

###### Theorem E

1. If $`b>b_c`$, then w.h.p. the sorted partition is a unique solution of the LPP, and thus $`d_{opt}^{LPP}=\mathrm{\Theta }(Mn)`$ and $`F_n(\kappa ,b)=1`$.

Let $`b<b_c`$.
2. Then w.h.p. $`d_{opt}^{LPP}=0`$. In addition, w.h.p. there are $`2^{[\kappa _c(b)+o(1)]n}`$ basis solutions, each having either none or exactly two components $`\sigma _i\pm 1`$.
3. W.h.p. $`F_n(\kappa ,b)=2^{[\kappa +o(1)]n}`$ for $`\kappa <\kappa _{}(b)`$, and $`2^{[\kappa _c(b)+o(1)]n}F_n(\kappa ,b)2^{[\kappa _{}(b)+o(1)]n}`$ for $`\kappa >\kappa _{}(b)`$.

###### Remark 2.3

(i) If one assume that the number of optimal partitions $`Z_{opt}`$ in the hard phase grows subexponentially with probability at least $`1o(n^2)`$ (see Remark 2.2 for a motivation of this assumption), our upper bound on the fraction $`F_n(\kappa ,b)`$ in the hard phase can be improved to match the lower bound, yielding $`F_n(\kappa ,b)=2^{n[\kappa _c(b)+o(1)]}`$ in the hard phase, see Remark 8.1 (i).

(ii) If, on the other hand, the asymptotics of Theorem 5.1 hold up to $`\kappa _c`$, more precisely, if one assumes that for $`b<b_c`$ and $`\kappa <\kappa _c(b)`$

$$Z_n(\mathrm{},s)=2^{n[\kappa _c(b)\kappa +o(1))]}$$
(2.12)
holds with probability least $`1o(n^2)`$, then a bound of the form $`F_n(\kappa ,b)=2^{n[\kappa +o(1)]}`$ can be extended to all $`\kappa <\kappa _c`$, see Remark 8.1 (ii).

We close this section with a few additional remarks and an additional theorem on the expected number of perfect partitions. We start with a discussion of Theorem B.

###### Remark 2.4

While (2.6) has only been proved for $`\kappa <\kappa _{}(b)`$, an upper bound of the same form can be shown to hold for all $`\kappa `$, see Theorem 6.1. Due to the random fluctuations of the Gaussian term, this upper bound is of order $`e^{\mathrm{\Theta }(n^{1/2})}`$ with positive probability as soon as $`\kappa \kappa _c(b)O(n^{1/2})`$, so that in this regime, there are no perfect partitions with probability bounded away from zero. Note, however, that as $`b0`$, the variance $`\sigma ^2=\text{Var}(\mathrm{log}(2\mathrm{cosh}(\zeta U+\eta )))`$ of the Gaussian term tends to zero.

We expect that for all $`b(0,b_c)`$ fluctuations of this kind persist around the true threshold, whether it is actually equal to $`\kappa _c(b)`$, or whether it is some other value $`\stackrel{~}{\kappa }_c(b)<\kappa _c(b)`$. For the constrained partition problem with $`b(0,b_c)`$, we therefore expect a scaling window of width at least $`n^{1/2}`$ in which the probability of perfect partitions lies strictly between $`0`$ and $`1`$. This is to be contrasted with the unconstrained case, where we had a very narrow scaling window of width $`\mathrm{\Theta }(n^1)`$ about the transition point $`\kappa _c`$, see .

Next let us consider the statements of Theorem C. Here again the situation is much more complicated than in the unconstrained case. By Theorem B and the lower bound in Theorem Ca, the minimum discrepancy changes from being at most one to being exponentially large as $`\kappa `$ crosses the interval $`[\kappa _{},\kappa _c]`$. However, we also prove (see Section 6.2) that the expected number of perfect partitions remains exponentially large until $`\kappa `$ reaches a value strictly exceeding $`\kappa _c`$. This is the content of the following theorem and remark.

###### Theorem F

Let $`\mathrm{}\{1,0,1\}`$ and $`b(0,1)`$. Then

$$\underset{n\mathrm{}}{lim}\left[n^1\mathrm{log}𝔼(Z_n(\mathrm{},s))R(\kappa ,b)\right]=0$$
(2.13)
where

$$R(\kappa ,b)=H((1+b)/2)+\lambda b+\mathrm{log}(\lambda ^1\mathrm{sinh}\lambda )\kappa \mathrm{log}2,$$
(2.14)
with $`H(u)=u\mathrm{log}(1/u)+(1u)\mathrm{log}(1/(1u))`$, and $`\lambda `$ satisfying $`\mathrm{coth}\lambda =\lambda ^1b.`$

###### Remark 2.5

Graphing the curve $`R(\kappa ,b)=0`$, i.e.

$$\kappa =\kappa _e(b):=\frac{H((1+b)/2)+\lambda b+\mathrm{log}(\lambda ^1\mathrm{sinh}\lambda )}{\mathrm{log}2},$$
(2.15)
we see that it lies strictly above $`\kappa =\kappa _c(b)`$, except at the only common point $`\kappa =1,b=0`$, see Fig. 2. In particular, the curve intersects the $`b`$-axis at $`b=0.56\mathrm{}>b_c=0.41`$. Thus for the points $`(\kappa ,b)`$ between the curves $`\kappa =\kappa _c(b)`$ and $`\kappa =\kappa _e(b)`$, the expected number of perfect partitions grows exponentially, while w.h.p. there are no perfect partitions at all. This complex behavior did not manifest itself in the unconstrained optimum partitioning problem .

We close this section with a discussion of the results of Theorem E.

###### Remark 2.6

Clearly, the fraction $`[F_n(\kappa ,b)]^1`$ is the expected number of times one has to generate a uniformly random basis solution of the LPP to get a basis solution with the optimal subpartition property. In absence of a better candidate, $`[F_n(\kappa ,b)]^1`$ seems to be a possible measure of algorithmic difficulty of the integer partition problem. Our theorem says that w.h.p. this measure is lowest for the sorted phase ($`b>b_c`$) where $`[F_n(\kappa ,b)]^1=1`$), next lowest for the perfect phase ($`b<b_c`$ and $`\kappa <\kappa _{}(b)`$) where $`[F_n(\kappa ,b)]^1=2^{\kappa n+o(n)}`$, and indeed hardest in the hard phase ($`b<b_c`$ and $`\kappa >\kappa _c(b)`$) where $`[F_n(\kappa ,b)]^12^{(\kappa _{}(b)+o(1))n}`$.

If we make the additional assumptions of Remark 2.3, we have that $`[F_n(\kappa ,b)]^1=2^{\kappa n+o(n)}`$ for $`b<b_c`$ and $`\kappa <\kappa _c(b)`$, while $`[F_n(\kappa ,b)]^1=2^{\kappa _cn+o(n)}`$ for $`\kappa >\kappa _c`$. This gives an easy-hard-easy picture along any curve $`b=b(\kappa )`$, $`\kappa 0`$, that crosses the lines $`\kappa =\kappa _c(b)`$ and $`b=b_c`$, provided that $`b(\kappa )`$ is strictly increasing in $`\kappa `$. Indeed, at a point $`(\kappa ,b)`$ on such a curve $`[F_n]^1`$ grows exponentially in $`n\kappa `$, as long as $`\kappa <\kappa _c(b(\kappa ))`$, i.e. until the curve $`b=b(\kappa )`$ intersects $`\kappa =\kappa _c(b)`$. For larger values of $`\kappa `$, $`[F_n]^1`$ grows at the exponential rate $`n\kappa _c(b(\kappa ))<n\kappa `$. Once the curve $`b=b(\kappa )`$ crosses the horizontal line $`b=b_c`$, the problem becomes even easier with $`[F_n]^1=1`$. In fact, above this line, the problem becomes easy in the usual sense, since the rounded and the fractional problem are identical, and sorted partitions can be found in linear time.

## 3 Preliminaries and Outline of Proof Strategy

In this section, we define our notation, review the heuristics of the proof, and point out why naive extensions of the unconstrained analysis of  fail in the constrained case.

### 3.1 Sorted Partitions

We first discuss our strategy to prove that in region III, the optimal partition is sorted and has discrepancy of order $`Mn`$. To this end, we consider $`n`$ weights $`X_1,\mathrm{},X_n`$, chosen uniformly at random from $`\{1,\mathrm{},M\}`$, and reorder them in such a way that their sizes are increasing, $`X_{\pi (1)}X_{\pi (2)}\mathrm{}X_{\pi (n)}`$, where $`\pi (1),\mathrm{},\pi (n)`$ is a suitable permutation of $`1,\mathrm{},n`$. Since $`M`$ is assumed to grow exponentially with $`n`$, we have, in particular, $`n^2=o(M)`$, which implies that w.h.p. no two weights are equal. So w.h.p. the permutation $`\pi `$ is unique and $`X_{\pi (1)}<X_{\pi (2)}<\mathrm{}<X_{\pi (n)}`$.

Given a bias $`s>0`$, (with $`sn(\text{mod }2`$)), we need to find an optimum partition that puts $`k=(s+n)/2`$ integers in one part, and the remaining $`nk`$ integers into another part. One such feasible partition is obtained if we select the $`k`$ smallest integers for the first part; we call it the sorted partition. It is coded by the $`𝝈`$, with $`\sigma _{\pi (i)}=1`$ for $`ik`$ and $`\sigma _{\pi (i)}=1`$ for $`i>k`$. If the total weight of $`(nk)`$ largest weights is, at most, the total weight of $`k`$ smallest weights, then it is intuitively clear that the sorted partition is optimal. More precisely: if

$$\delta _s(𝑿)=\underset{j=1}{\overset{k}{}}X_{\pi (j)}\underset{j=k+1}{\overset{n}{}}X_{\pi (j)}0$$
(3.1)
then the sorted partition is the unique, optimal partition, and the minimal discrepancy is

$$d_{opt}=\delta _s(𝑿).$$
(3.2)
See Section 6.3 for a formal proof.333If $`\delta _s(𝑿)=1`$, the sorted partition is still optimal (it is, in fact, perfect). But in general, it is not the unique optimum partition.

To determine the phase boundary of the phase III, we thus have to determine the region of the phase diagram in which w.h.p. the sorted partition meets the condition (3.1). Leaving the probabilistic technicalities out of our heuristic discussion, let us replace the condition (3.1) by its mean version, namely $`𝔼(\delta _s(𝐗))0`$. Consider an arbitrary $`b(0,1]`$. Let $`x_0=(1+b)/2`$ and $`M_0=x_0M`$. For a typical set of weights $`X_1,\mathrm{},X_n`$, let us consider the sorted partition with $`\sigma _j=1`$ for $`X_jM_0`$, and $`\sigma _j=1`$ for $`X_j>M_0`$. Since the probability that $`X_jM_0`$ is equal to $`\stackrel{~}{x}_0=M_0/M=x_0+O(M^1)`$, we get that the expected number of weights $`X_j`$ with $`X_jM_0`$ is $`n\stackrel{~}{x}_0`$, implying that the expected bias is $`2n\stackrel{~}{x}_0n=nb+O(n/M)`$. The expected discrepancy can be calculated in a similar manner, giving the expression

$`𝔼[{\displaystyle \underset{j}{}}X_j𝕀(X_jx_0M)`$ $`{\displaystyle \underset{j}{}}X_j𝕀(X_j>x_0M)]`$ (3.3)
$`={\displaystyle \frac{n}{M}}\left[M_0(1+M_0){\displaystyle \frac{M(1+M)}{2}}\right]`$
$`=\left[x_0^2{\displaystyle \frac{1}{2}}+O(M^1)\right]Mn`$
$`=\left[\left({\displaystyle \frac{b+1}{2}}\right)^2{\displaystyle \frac{1}{2}}+O(M^1)\right]Mn.`$
So, $`𝔼(\delta _s(𝐗))`$ is large positive, of order $`Mn`$, iff $`(b+1)^2/41/2>0`$, or equivalently $`b>b_c=\sqrt{2}1`$. In Section 6.3 we prove the condition $`b>b_c`$ is both necessary and sufficient for $`\delta _s(𝐗)`$ to be, w.h.p., positive, of order $`Mn`$. In language of statistical mechanics, we show that, for $`b>b_c`$, $`\delta _s(𝐗)`$ is “self-averaging,” i.e. its distribution is sharply concentrated around $`𝔼(\delta _s(𝐗))`$.

###### Remark 3.1

On the heuristic level presented here, the above arguments can easily be generalized to an arbitrary distribution for the weights $`X_1,\mathrm{},X_n`$, as long as these weights are independent copies of a generic (discrete) variable $`X`$ with a reasonably well behaved probability distribution. Assuming, e.g., that the variable $`X/M`$ has a limiting distribution with density $`\mu `$, one obtains that the critical value of $`b`$ is given by $`b_c=b_c(\mu )=2_0^{x_0}\mu (x)𝑑x1`$, where $`x_0`$ is determined by the equation $`_0^{x_0}x\mu (x)𝑑x=_{x_0}^{\mathrm{}}x\mu (x)𝑑x`$. However, we have not tried to extend all our results to this more general $`\mu `$-density case.

### 3.2 Integral Representations

Let us now turn to the much more difficult region $`b<b_c`$. Without loss of generality, we may take $`s0`$, so that $`b=s/n`$.

Let $`Z_n(\mathrm{},s)=Z_n(\mathrm{},s;𝕏)`$ denote the total number of partitions $`𝝈`$ such that $`𝝈𝕏=\mathrm{}`$ and $`𝝈𝕖=s`$. Guided by the results of , one might hope to prove that, as the parameter $`\kappa =n^1\mathrm{log}_2M`$ is varied, the model undergoes a phase transition between a region with exponentially many perfect partitions and a region with no perfect partitions. Since perfect partitions correspond to $`\mathrm{}=0`$ or $`\mathrm{}=\pm 1`$, we will be mainly interested in $`Z_n(\mathrm{},s)`$ for $`|\mathrm{}|1`$, while $`s`$ will typically be chosen proportional to $`n`$.

A starting point in  was an integral (Fourier-inversion) type formula for $`Z_n(\mathrm{})=Z_n(\mathrm{};𝕏)`$, the total number of $`𝝈`$’s such that $`𝝈𝕏=\mathrm{}`$, namely

$$Z_n(\mathrm{})=\frac{2^n}{\pi }\underset{x(\pi /2,\pi /2]}{}\mathrm{cos}(\mathrm{}x)\underset{j=1}{\overset{n}{}}\mathrm{cos}(xX_j)dx.$$
(3.4)
We need to derive a two-dimensional counterpart of that formula for $`Z_n(\mathrm{},s)`$. To this end, let us first recall that by (2.3), $`s=2|\{j:\sigma _j=1\}|n`$, so that a generic value $`s`$ of $`s(𝝈)`$ must meet the condition $`n+s0(\text{mod }2)`$. In a similar way, we get that $`𝝈𝕏`$ has the same parity as the sum $`_jX_j`$. Keeping this in mind, we have that on the event $`\{_jX_j\mathrm{}(\text{mod }2)\}`$, for $`n+s0(\text{mod }2)`$,

$$𝕀(𝝈𝕏=\mathrm{},𝝈𝕖=s)=\frac{1}{\pi ^2}\underset{x,y(\pi /2,\pi /2]}{}e^{i(𝝈𝕏\mathrm{})x}e^{i(𝝈𝕖s)y}𝑑x𝑑y,$$
(3.5)
thus extending (4.6) in . Multiplying both sides of the identity by $`2^n`$, and summing over all $`𝝈`$, we obtain

$`Z_n(\mathrm{},s)`$ $`={\displaystyle \frac{2^n}{\pi ^2}}{\displaystyle \underset{x,y(\pi /2,\pi /2]}{}}e^{i(\mathrm{}x+sy)}{\displaystyle \underset{j=1}{\overset{n}{}}}\mathrm{cos}\left(xX_j+y\right)dxdy.`$ (3.6)
$`=2^n_{1/2}(𝝈𝕏=\mathrm{},𝝈𝕖=s|.𝑿),`$
where $`𝝈=(\sigma _1,\mathrm{},\sigma _n)`$ is a sequence of i.i.d. Bernoulli random variables with probability of $`\sigma _i=\pm 1`$ equal to $`1/2`$.

We would like to estimate the asymptotics of the integral in (3.6), which is equivalent to proving a local limit theorem for the conditional probability in (3.6). In general, to compute – via local limit theorems – the probability that some random variable $`A`$ takes the value $`a`$, it must be the case that the corresponding expectation of $`A`$ is near $`a`$. Thus the analogue of the representation (3.6) for the unconstrained problem was well adapted to the analysis of perfect partitions. Indeed, in that case, we wanted to estimate $`_{1/2}(|𝝈𝕏|1|𝕏)`$, and we had $`𝔼_{1/2}(𝝈𝕏|𝕏)=0`$. However, in the constrained case, this strategy cannot be expected to work for $`b>0`$, since $`s=bn`$ is very far from the expectation of $`𝝈𝕖`$, namely $`𝔼_{1/2}(𝝈𝕖|𝕏)=0`$.

To resolve this substantial difficulty, we introduce a two-parameter family of distributions for $`\sigma _j`$ as follows: Given $`\xi ,\eta `$, let $`𝝈=(\sigma _1,\mathrm{},\sigma _n)`$ be a sequence of random variables such that, conditioned on $`𝕏`$, $`\sigma _1,\mathrm{},\sigma _n`$ are mutually independent, and

$$(\sigma _j=1|𝕏)=P(\xi X_j+\eta ),(\sigma _j=1|𝕏)=1P(\xi X_j+\eta ),$$
(3.7)
where

$$P(u):=\frac{e^u}{2\mathrm{cosh}u}.$$
(3.8)
In terms of these random variables, $`Z_n(\mathrm{},s)`$ can be rewritten as

$`Z_n(\mathrm{},s)`$ $`=e^{nL_n(\xi ,\eta ;𝕏)}\left(𝝈𝕏=\mathrm{},𝝈𝕖=s|𝕏\right)`$ (3.9)
$`=e^{nL_n(\xi ,\eta ;𝕏)}{\displaystyle \frac{1}{\pi ^2}}{\displaystyle \underset{x,y(\pi /2,\pi /2]}{}}e^{i(\mathrm{}x+sy)}𝔼\left(\mathrm{exp}(i(x𝝈𝕏+y𝝈𝕖))|𝕏\right)𝑑x𝑑y,`$
where

$$L_n(\xi ,\eta ;𝕏):=\frac{\mathrm{}\xi }{n}+\frac{s\eta }{n}+\frac{1}{n}\underset{j=1}{\overset{n}{}}\mathrm{log}(2\mathrm{cosh}(\xi X_j+\eta )).$$
(3.10)
Indeed, fix $`\xi ,\eta `$. Then $`Z_n(\mathrm{},s)`$ can be rewritten as

$`Z_n(\mathrm{},s)`$ $`={\displaystyle \underset{𝝉\{1,+1\}^n}{}}𝕀(𝝉𝕏=\mathrm{},𝝉𝕖=s)`$ (3.11)
$`={\displaystyle \underset{\genfrac{}{}{0pt}{}{𝝉:𝝉𝕏=\mathrm{},}{𝝉𝕖=s}}{}}e^{\xi (\mathrm{}𝝉𝕏)+\eta (s𝝉𝕖)}=e^{\xi \mathrm{}+\eta s}{\displaystyle \underset{\genfrac{}{}{0pt}{}{𝝉:𝝉𝕏=\mathrm{},}{𝝉𝕖=s}}{}}{\displaystyle \underset{j=1}{\overset{n}{}}}e^{(\xi X_j+\eta )\tau _j}`$
$`=\left[e^{\xi \mathrm{}+\eta s}{\displaystyle \underset{j=1}{\overset{n}{}}}(2\mathrm{cosh}(\xi X_j+\eta ))\right]{\displaystyle \underset{\genfrac{}{}{0pt}{}{𝝉:𝝉𝕏=\mathrm{},}{𝝉𝕖=s}}{}}{\displaystyle \underset{j^{}=1}{\overset{n}{}}}P\left((\xi X_j^{}+\eta )\tau _j^{}\right)`$
$`=e^{nL_n(\xi ,\eta ;𝐗)}{\displaystyle \underset{\genfrac{}{}{0pt}{}{\tau :\tau 𝐗=\mathrm{},}{\tau 𝐞=s}}{}}{\displaystyle \underset{j=1}{\overset{n}{}}}(\sigma _j=\tau _j|𝐗)`$
$`=e^{nL_n(\xi ,\eta ;𝐗)}(𝝈𝐗=\mathrm{},𝝈𝐞=s|𝐗),`$
since $`P(u)=1P(u)`$, see equation (3.8).

### 3.3 Saddle Point Equations and their Solution

Given $`\xi ,\eta `$, we now face the problem of determining an asymptotic value of the local probability in (3.9). This will obviously be easier if the chosen parameters $`\mathrm{}`$ and $`s`$ are among the more likely values of $`𝝈𝕏`$ and $`𝝈𝕖`$, respectively. A natural choice is to take $`\mathrm{}`$ and $`s`$ equal to their expected values, that is

$$𝔼\left(\sigma 𝕏|𝕏\right)=\mathrm{},𝔼\left(𝝈𝕖|𝕏\right)=s,$$
(3.12)
or explicitly (using (3.8), (3.7))

$`{\displaystyle \underset{j=1}{\overset{n}{}}}X_j\mathrm{tanh}(\xi X_j+\eta )=\mathrm{},`$ (3.13)
$`{\displaystyle \underset{j=1}{\overset{n}{}}}\mathrm{tanh}(\xi X_j+\eta )=s.`$
Note that the equations (3.13) also arise naturally in an apparently different approach to estimate the integral in (3.6), the “method of steepest descent.” In our context, this corresponds to a complex shift of the integration path, i.e., to changing the path of integration for $`x`$ to the complex path from $`\pi /2+i\xi `$ to $`\pi /2+i\xi `$, and the path of integration for $`y`$ to the complex path from $`\pi /2+i\eta `$ to $`\pi /2+i\eta `$, where $`\xi `$ and $`\eta `$ are determined by a suitable saddle point condition. For general $`\xi `$ and $`\eta `$, this leads to (3.9), while the saddle point conditions turn our to be nothing but (3.13). In fact, this is how we first obtained (3.9) and (3.13).

Both approaches raise the question of uniqueness and existence of a solution to the saddle point equations(3.13). In this context, it is useful to realize that the conditions (3.13) can be rewritten as

$$\frac{L_n(\xi ,\eta ;𝐗)}{\xi }=0,\frac{L_n(\xi ,\eta ;𝐗)}{\eta }=0.$$
(3.14)
Therefore any solution $`(\xi ,\eta )`$ is a stationary point of the strictly convex function $`L_n(\xi ,\eta ;𝐗)`$. If a solution exists, it is therefore the unique minimum point of $`L_n`$. Using the first equation in (3.9), we see also that $`(\xi ,\eta )`$ maximizes the local probability $`(𝝈𝐗=\mathrm{},𝝈e=s|𝐗)`$, and hence makes it easier to do an asymptotic analysis. This observation justifies our choice of $`\xi ,\eta `$.

In the actual proof, we modify this approach a little since the solution $`\xi =\xi (𝐗)`$, $`\eta =\eta (𝕏)`$ does not lend itself to a rigorous analysis of $`(𝝈𝐗=\mathrm{},𝝈e=s|𝐗)`$. Instead, we will resort to ”suboptimal” $`\xi =\zeta /M,\eta `$, where $`\zeta ,\eta `$ are nonrandom constants, and $`(\zeta ,\eta )`$ is a solution of nonrandom equations, obtained by replacing the (scaled) sums in (3.13) with their weak-law limits, see equations (3.18) below. This way we will be able to establish an explicit asymptotic formula for $`Z_n(\mathrm{},s)`$, which will ultimately lead us to determine the phase boundaries.

In Section 4, we will show that these deterministic equations have a (unique) solution $`\zeta =\zeta (b),\eta =\eta (b)`$ iff $`b<b_c=\sqrt{2}1`$, the same $`b_c`$ that determines the sorted phase. In other words, the threshold $`b_c`$ plays two seemingly unrelated roles: both as a threshold value of $`b`$ for solvability of the deterministic saddle point equations (3.18), and as a threshold for the sorted partition being optimal. On an informal level, the reason for the coincidence is as follows: For simplicity, suppose that the weights $`X_j`$ are all distinct, so that $`X_1<\mathrm{}<X_n`$ after reordering. As $`b`$ approaches the point where the solutions $`(\zeta ,\eta )`$ to the saddle point equations (3.18) stop existing, these solutions actually diverge, one tending to $`+\mathrm{}`$ and the other to $`\mathrm{}`$. According to equations (3.7) and (3.8), this in turn means that $`(\sigma _j=1|𝕏)`$ tends to zero or one, depending on whether $`j<j_o`$ or $`j>j_o`$, where $`j_o=|\{j:\sigma _j=1\}|`$ is the cutoff of the sorted partition for $`𝕏`$ with bias $`s=nb_c`$. Hence, the product measure $`(𝝈𝐗=\mathrm{},𝝈𝐞=s|𝐗)`$ tends to a delta function on the (unique) sorted partition which is the solution to the number partitioning problem for $`𝕏`$ at $`b=b_c`$. See Subsection 7.2 for details.

### 3.4 Asymptotic behavior of $`Z_n(\mathrm{},s)`$.

Proceeding with our heuristic discussion, let us simply assume that the equations (3.13) do have a solution $`\xi =\xi (𝐗),\eta =\eta (𝐗)`$. Then we may hope that, with this choice of the parameters $`\xi =\xi (𝕏)`$, $`\eta =\eta (𝕏)`$, we have a reasonable chance to prove—at least for the likely values of $`𝕏`$—a local limit theorem for the conditional probability in (3.9), namely that w.h.p.

$$(𝝈𝕏=\mathrm{},𝝈𝕖=s|𝕏)\frac{2}{\pi \sqrt{\text{det }Q}},$$
(3.15)
where

$$Q=\left(\begin{array}{cc}\text{Var}(𝝈X)& \text{cov}(𝝈𝕏,𝝈𝕖)\\ \text{cov}(𝝈𝕏,𝝈𝕖)& \text{Var}(𝝈𝕖)\end{array}\right).$$
(3.16)
Here the (co)variances are conditioned on $`𝐗`$, so, e.g., $`Q_{11}=\text{Var}(𝝈𝐗|𝐗)`$. If (3.15) holds then by (3.11), w.h.p.,

$$Z_n(\mathrm{},s)e^{nL_n(\xi ,\eta ;𝕏)}\frac{2}{\pi \sqrt{\text{det }Q}}=e^{nL_n(\xi ,\eta ;𝕏)}\frac{2}{\pi nM\sqrt{\text{det }R^{(n)}}},$$
(3.17)
where $`R^{(n)}`$ is the matrix with matrix elements $`R_{11}^{(n)}=\frac{1}{nM^2}\text{Var}(𝝈X)`$, $`R_{12}^{(n)}=R_{21}^{(n)}=\frac{1}{nM}\text{cov}(𝝈𝕏,𝝈𝕖)`$ and $`R_{22}^{(n)}=\frac{1}{n}\text{Var}(𝝈𝕖)`$.

Note that, in the limit $`M\mathrm{}`$, $`X_j/M`$ are independent, uniform random variables in $`[0,1]`$. We therefore expect that as $`M,n\mathrm{}`$ with $`\kappa =n^1log_2M`$ fixed, both $`\zeta (𝕏):=M\xi (𝕏)`$ and $`\eta (𝕏)`$ are close, in probability, to the deterministic $`\zeta ,\eta `$, defined as the roots of the averaged version of the “saddle point equations” (3.13), namely

$`{\displaystyle \underset{0}{\overset{1}{}}}x\mathrm{tanh}(\zeta x+\eta )𝑑x=`$ $`{\displaystyle \frac{\mathrm{}}{Mn}},`$ (3.18)
$`{\displaystyle \underset{0}{\overset{1}{}}}\mathrm{tanh}(\zeta x+\eta )𝑑x=`$ $`b,b={\displaystyle \frac{s}{n}}.`$
Recall that, without loss of generality, we have taken $`s0`$, so $`b0`$.

Furthermore, approximating $`\xi (𝕏)`$ and $`\eta (𝕏)`$ by $`M\zeta `$ and $`\eta `$, respectively and using the bound $`|d\mathrm{cosh}u/du|1`$, it is easy to see that, because of the weak law of large numbers, w.h.p.

$`L_n(\xi (𝕏),\eta (𝕏);𝕏)`$ $`={\displaystyle \frac{1}{n}}{\displaystyle \underset{j=1}{\overset{n}{}}}\mathrm{log}\left(e^{\mathrm{}\xi (𝕏)+s\eta (𝕏)}2\mathrm{cosh}(\xi (𝕏)X_j+\eta (𝕏))\right)`$
$`{\displaystyle \frac{\mathrm{}}{Mn}}\zeta +b\eta +{\displaystyle \underset{0}{\overset{1}{}}}\mathrm{log}(2\mathrm{cosh}(\zeta x+\eta ))𝑑x,`$ (3.19)
and similarly for the matrix elements of $`R^{(n)}`$,

$$R_{ij}^{(n)}\underset{0}{\overset{1}{}}x^{2(i+j)}(1\mathrm{tanh}^2(\zeta x+\eta ))𝑑x.$$
(3.20)
Putting everything together, we thus may hope to prove that for $`|\mathrm{}|1`$ and $`M`$ growing exponentially with $`n`$, (i.e. $`\mathrm{log}_2M\kappa n`$ for some $`n`$-independent $`\kappa `$), we have w.h.p.

$`{\displaystyle \frac{1}{n}}\mathrm{log}Z_n(\mathrm{},s)`$ $`{\displaystyle \underset{0}{\overset{1}{}}}\mathrm{log}(2\mathrm{cosh}(\zeta x+\eta ))𝑑x+b\eta \kappa `$ (3.21)
$`=\kappa _c(b)\kappa ,`$
suggesting that for $`\kappa <\kappa _c(b)`$ there are exponentially many perfect partitions, while for $`\kappa >\kappa _c(b)`$ there are none.

However, this informal argument is too naive. Equation (3.21) could not possibly hold for $`\kappa >\kappa _c(b)`$. Indeed, $`Z_n(\mathrm{},s)`$ is an integer, and thus cannot be asymptotically equivalent to an exponentially small, yet positive number. This means that a rigorous proof of (3.21) must be based on the condition $`\kappa <\kappa _c(b)`$. But our heuristic discussion provides no clue as to how this condition might enter the picture. Furthermore, our attempts to find such a proof are stymied by mutual dependence of the random variables $`(\sigma _j=1|𝐗),(1jn)`$, a consequence of the fact that $`(\xi (𝐗),\eta (𝐗))`$ depends, in an unwieldy manner, on the whole $`𝐗`$. This complicated dependence of $`(\xi (𝐗),\eta (𝐗))`$ on $`𝐗`$ would have made it very hard to gain an insight into the random fluctuations of the sum in (3.19), even if we had found a proof.

Fortunately, once we have informally connected $`(\xi (𝕏),\eta (𝐗))`$ to $`(\zeta ,\eta )`$ via $`\xi (𝐗)=(1+o_p(1))\zeta /M`$, $`\eta (𝐗)=(1+o_p(1))\eta `$, we may try to use the suboptimal parameters $`(\zeta /M,\eta )`$ instead. The corresponding random variables $`(\sigma _j=1|𝐗)`$ each depend on their own $`X_j`$, and are thus mutually independent. A key technical issue is whether the suboptimal parameters are good enough to get an asymptotic formula for the corresponding probability $`(𝝈𝐗,𝝈𝐗=s|𝐗)`$, given that now the random equations (3.13) may hold only approximately. Our proof below shows that they are indeed sufficient. With those parameters, we will be able to get a sharp explicit approximation for $`\mathrm{log}Z_n(\mathrm{},s)`$, at least in the range $`\kappa <\kappa _{}(b)`$.

We prove the existence and uniqueness of the solution to (3.18) in the next section, and then use them in Section 5.1 to derive the asymptotics of $`Z_n(\mathrm{},s)`$.

## 4 Solution of the Deterministic Saddle Point Equations

Based on the heuristic discussion of the last section, we define $`𝝈`$ as the random sequence $`(\sigma _1,\mathrm{},\sigma _n)`$ such that, conditioned on $`𝕏`$, the $`\sigma _j`$ are independent and

$$(\sigma _j=1|𝕏)=P\left(\zeta \frac{X_j}{M}+\eta \right),(\sigma _j=1|𝕏)=1P\left(\zeta \frac{X_j}{M}+\eta \right),$$
(4.1)
with $`P(u)`$ defined in (3.8), and $`(\zeta ,\eta )`$ is a solution of the equations

$`{\displaystyle \underset{0}{\overset{1}{}}}x\mathrm{tanh}(\zeta x+\eta )𝑑x=0,`$ (4.2)
$`{\displaystyle \underset{0}{\overset{1}{}}}\mathrm{tanh}(\zeta x+\eta )𝑑x=b.`$
These are the equations (3.18), except that the right hand side of the first equation is set $`0`$, since our focus is on $`\mathrm{}Mn`$.

However, does such a solution exist? A key observation here is that the equations (4.2) mean that $`(\zeta ,\eta )`$ is a stationary point of the function

$$L(\zeta ,\eta ):=b\eta +\underset{0}{\overset{1}{}}\mathrm{log}(2\mathrm{cosh}(\zeta x+\eta ))𝑑x$$
(4.3)
which is the r.h.s. in (3.19), without the term $`\zeta \mathrm{}/(Mn)`$, i.e., the (weak) limit of the function $`L_n(\xi (𝕏),\eta (𝕏);𝕏)`$ defined in (3.10). Since $`L(\zeta ,\eta )`$ is strictly convex, it may have at most one stationary point, and this point is a global minimum. So a solution to (4.2) exists iff $`L(\zeta ,\eta )`$ attains its global infimum.

###### Theorem 4.1

Let $`0b<b_c:=\sqrt{2}1`$. Then:

(1) $`L(\zeta ,\eta )`$ attains its infimum, hence there exists a unique solution $`(\zeta ,\eta )=(\zeta (b),\eta (b))`$ of the equations (4.2).

(2) The minimizers $`\zeta (b),\eta (b)`$ are continuous functions, with $`\zeta (b)>0`$, $`\eta (b)<0`$ and $`\zeta (b)+\eta (b)>0`$ whenever $`0<b<b_c`$.

(3) $`\widehat{L}(b):=L(\zeta (b),\eta (b))`$, the minimum of $`L(\zeta ,\eta )`$, decreases with $`b`$. For $`b(0,b_c)`$, its derivative is $`d\widehat{L}(b)/db=\eta (b)`$.

(4) $`lim_{bb_c}\zeta (b)=\mathrm{}`$, $`lim_{bb_c}\eta (b)=\mathrm{}`$,

$$\underset{bb_c}{lim}\frac{\eta (b)}{\zeta (b)}=\frac{1}{\sqrt{2}},$$
(4.4)
and $`lim_{bb_c}\widehat{L}(b)=0`$.

(5) $`lim_{b0}\zeta (b)=0`$, $`lim_{b0}\eta (b)=0`$, and $`lim_{b0}\widehat{L}(b)=\mathrm{log}2`$.

Proof of Theorem 4.1.

(1) Since $`\mathrm{log}(2\mathrm{cosh}u)|u|`$, we have

$$L(\zeta ,\eta )(\zeta ,\eta ),$$
(4.5)
where

$$(\zeta ,\eta )=b\eta +\underset{0}{\overset{1}{}}|\zeta x+\eta |𝑑x.$$
(4.6)
It thus suffices to prove that

$$\underset{(\zeta ,\eta )_{\mathrm{}}\mathrm{}}{lim\; inf}(\zeta ,\eta )=\mathrm{},$$
(4.7)
where $`(\zeta ,\eta )_{\mathrm{}}=\mathrm{max}\{|\zeta |,|\eta |\}`$.

Since $``$ is homogeneous, degree $`1`$, and continuous, it suffices to prove that $`(\zeta ,\eta )>0`$ for all $`(\zeta ,\eta )`$ such that $`(\zeta ,\eta )_{\mathrm{}}=1`$. To this end, we will first show that

$$\underset{(\zeta ,\eta )_{\mathrm{}}=1}{\mathrm{min}}(\zeta ,\eta )=\underset{1\eta 0}{\mathrm{min}}(1,\eta ).$$
(4.8)
Since $`(\zeta ,\eta )(|\zeta |,|\eta |)`$, it suffices to consider $`\eta 0`$ and $`\zeta 0`$. But $`\eta 0`$, $`\zeta 0`$ and $`(\zeta ,\eta )_{\mathrm{}}=1`$ implies that either $`\zeta =1`$ and $`1\eta 0`$ or $`\eta =1`$ and $`0\zeta 1`$. We thus have to show $`(\zeta ,\eta )`$ is bounded below by the right hand side of (4.8) if $`\eta =1`$ and $`0\zeta 1`$. Indeed, under these conditions, $`|\zeta x+\eta |=1\zeta x1x=|x+\eta |`$, implying that $`(\zeta ,\eta )(1,1)`$, which is clearly bounded below by the right hand side of (4.8).

It remains to bound $`(1,\eta )`$ from below, for $`1\eta 0`$. Setting $`\stackrel{~}{x}=\eta `$, we have

$$(1,\eta )=b\stackrel{~}{x}+\underset{0}{\overset{1}{}}|x\stackrel{~}{x}|𝑑x=\frac{1}{2}+\stackrel{~}{x}^2\stackrel{~}{x}(1+b).$$
(4.9)
At $`\stackrel{~}{x}=x_0:=(1+b)/2`$ the right hand side attains its minimum value $`\frac{1}{2}[1(1+b)^2/2]`$, which is bounded away form zero as $`b<b_c=\sqrt{2}1`$. Thus we have proved that for $`b[0,\sqrt{2}1)`$, and all $`\zeta ,\eta `$,

$$(\zeta ,\eta )c^{}(b)\mathrm{max}\{|\zeta |,|\eta |\},$$
(4.10)
where $`c^{}(b)=\frac{1}{2}[1(1+b)^2/2]>0`$. Therefore $`(\zeta ,\eta )`$ attains its infimum, hence so does $`L(\zeta ,\eta )`$. We conclude that (4.2) has a unique solution solution $`(\zeta ,\eta )=(\zeta (b),\eta (b))`$.

(2) Suppose $`\eta (b)0`$. Using (4.2), and $`y\mathrm{tanh}y>0`$ if $`y0`$, one can show easily that $`\eta (b)>0`$ and $`\zeta (b)<0`$. But such a point $`(\zeta (b),\eta (b))`$ cannot be a minimum point of $`L(\zeta ,\eta )`$, since $`L(\zeta (b),\eta (b))>L(\zeta (b),\eta (b))`$, due to the symmetry of $`\mathrm{cosh}y`$, and the fact that $`b\eta (b)>b\eta (b)`$. Therefore $`\eta =\eta (b)<0`$, and

$$\zeta +\eta =(\zeta x+\eta )|_{x=1}>0.$$
(4.11)
Continuity will be proved along with (3), where we actually prove continuous differentiability.

(3) The equations (4.2) are an explicit form of $`L_\zeta =0`$, $`L_\eta =0`$. It is easy to show that the Jacobian matrix $`\left(\begin{array}{cc}L_{\zeta \zeta }& L_{\eta \zeta }\\ L_{\zeta \eta }& L_{\eta \eta }\end{array}\right)`$ is nonsingular. Therefore $`\zeta (b)`$, $`\eta (b)`$ are continuously differentiable, and consequently

$`\widehat{L}_b(b)=`$ $`\left[L_b(b,\eta ,\zeta )+L_\zeta (b,\zeta ,\eta )\zeta _b(b)+L_\eta (b,\zeta ,\eta )\eta _b(b)\right]_{\zeta =\zeta (b),\eta =\eta (b)}`$ (4.12)
$`=`$ $`L_b(b,\eta (b),\zeta (b))=\eta (b)<0.`$ (4.13)
Therefore $`\widehat{L}(b)`$ decreases with $`b`$.

(4) Pick $`\zeta >0`$, $`x_0(0,1)`$, and set $`\eta =x_0\zeta `$. Breaking the integral (4.3) into two parts, $`x[0,x_0]`$ and $`x[x_0,1]`$, and using

$$\mathrm{log}(e^u+e^u)=u+\mathrm{log}(1+e^{2u}),$$
(4.14)
we get:

$`L(\zeta ,\eta )=`$ $`{\displaystyle \frac{\zeta }{2}}\left(2x_0^22x_0(1+b)+1\right)`$ (4.15)
$`+{\displaystyle \frac{1}{2\zeta }}{\displaystyle \underset{0}{\overset{2\zeta x_0}{}}}\mathrm{log}(1+e^u)𝑑u+{\displaystyle \frac{1}{2\zeta }}{\displaystyle \underset{0}{\overset{2\zeta (1x_0)}{}}}\mathrm{log}(1+e^u)𝑑u.`$
At $`x_0=(1+b)/2`$ the quadratic polynomial attains its minimum value $`1(1+b)^2/2`$, which is positive since $`b<b_c`$. With this $`x_0`$, choose $`\zeta =\left(1\frac{(1+b)^2}{2}\right)^{1/2}`$. Then $`\zeta \mathrm{}`$ as $`bb_c`$, so that the integral terms add up to $`O(\zeta ^1)`$, which is also the order of the first term. Hence $`L(\zeta ,\eta )0`$, and therefore $`lim_{bb_c}\widehat{L}(b)0`$. To see that $`lim_{bb_c}\widehat{L}(b)=0`$, we just note that $`\widehat{L}(b)=\mathrm{min}_{\eta ,\zeta }L(\zeta ,\eta )\mathrm{min}_{\eta ,\zeta }(\zeta ,\eta )=0`$.

To complete the proof, in (4.15) set $`\zeta =\zeta (b)`$ and $`x_0=\eta (b)/\zeta (b)`$, so that $`\eta =\eta (b)`$. (Note that $`x_0(0,1)`$ as $`\zeta (b)+\eta (b)>0`$.) Since the quadratic polynomial in (4.15) is non-negative if $`bb_c`$, and $`\mathrm{max}(x_0,1x_0)1/2`$, we have that

$$\underset{bb_c}{lim}\widehat{L}(b)\underset{bb_c}{lim\; inf}\frac{1}{2\zeta (b)}\underset{0}{\overset{\zeta (b)}{}}\mathrm{log}(1+e^u)𝑑u>0,$$
(4.16)
if $`lim\; inf_{bb_c}\zeta (b)<\mathrm{}`$. So, since $`lim_{bb_c}\widehat{L}(b)=0`$, we conclude that $`\zeta (b)\mathrm{}`$ as $`bb_c`$. But then, using (4.15) again,

$`0=\underset{bb_c}{lim}{\displaystyle \frac{\zeta (b)}{2}}\left[2x_0^22x_0(1+b)+1\right]`$ $`\underset{bb_c}{lim}\left[2x_0^22x_0(1+b)+1\right]=0`$ (4.17)
$``$ $`\underset{bb_c}{lim}x_0={\displaystyle \frac{1}{\sqrt{2}}},`$ (4.18)
the only root of $`2x^22x\sqrt{2}+1=0`$.

(5) This statement is immediate from the fact that $`\zeta (b)`$, $`\eta (b)`$ are continuously differentiable on $`(0,b_c)`$ and the observation that for $`b=0`$, $`L(\zeta ,\eta )`$ attains its minimum value of $`\mathrm{log}2`$ at $`(\zeta ,\eta )=(0,0)`$. $`\mathrm{}`$

###### Remark 4.1

Theorem 4.1 can easily be generalized to the case of non-uniform i.i.d. random variables $`X_j`$ provided $`X_j/M`$ has a limiting density $`\mu (x),x0`$. In that case, $`b_c`$ is replaced by $`b_c=b_c(\mu )`$, as defined in Remark 3.1, i.e.

$$b_c=2_0^{x_0}\mu (x)𝑑x1,_0^{x_0}x\mu (x)𝑑x=_{x_0}^{\mathrm{}}x\mu (x)𝑑x.$$
(4.19)
The counterpart of $`L(\zeta ,\eta )`$ is obviously

$$L(\zeta ,\eta )=b\eta +_0^{\mathrm{}}\mathrm{log}(2\mathrm{cosh}(\zeta x+\eta ))\mu (x)𝑑x.$$
(4.20)
Remarkably, this extension requires only obvious changes in the above proof. For instance, below is the proof of the item (1). Note that the surprising dual role of $`b_c`$, namely as both the point at which the saddle point equation stops having a solution and as the threshold for optimality of sorted partitions, still holds for $`b_c(\mu )`$. In fact, if correctly interpreted, this dual role persists deterministically for any fixed instance $`\{X_1,\mathrm{},X_n\}`$, see Subsection 7.2.

Proof of (1) for an arbitrary distribution $`\mu `$: First, we write

$$L(\zeta ,\eta )(\zeta ,\eta )=b\eta +_0^{\mathrm{}}|\zeta x+\eta |\mu (x)𝑑x.$$
(4.21)
Second, we bound

$$\underset{(\zeta ,\eta )_{\mathrm{}}=1}{\mathrm{min}}(\zeta ,\eta )\mathrm{min}(\underset{1\eta 0}{\mathrm{min}}(1,\eta ),\underset{0\zeta 1}{\mathrm{min}}(\zeta ,1)).$$
(4.22)
Furthermore,

$`(\zeta ,1)`$ $`=b+M(\zeta ^1),,`$
$`M(y)`$ $`:={\displaystyle _0^y}(1xy^1)\mu (x)𝑑x+{\displaystyle _y^{\mathrm{}}}(xy^11)\mu (x)𝑑x.`$
Using 4.19, we see that

$$\underset{y0}{\mathrm{min}}M(y)=M(x_0)=b_c(\mu ),$$
(4.23)
hence

$$(\zeta ,1)b+b_c(\mu )>0,$$
(4.24)
for $`b<b_c(\mu )`$. Likewise, if $`\eta <0`$, we set $`\eta =\stackrel{~}{x}`$, and easily obtain

$$(1,\eta )=\stackrel{~}{x}\left(b+M(\stackrel{~}{x})\right)\stackrel{~}{x}(b+b_c(\mu ))>0,$$
(4.25)
for $`b<b_c(\mu )`$. $`\mathrm{}`$

## 5 The Perfect Phase

### 5.1 Asymptotic Enumeration of Partitions by Discrepancy and Bias

Now that we have proved existence of the solution $`(\zeta ,\eta )`$ of (4.2) for $`b<\sqrt{2}1`$, we are justified in using the marginals (4.1). It is critically important that each $`(\sigma _j=\pm 1|𝕏)`$ depends only on its own $`X_j`$, so that they are mutually independent. This would not have been the case if we had used $`(\xi (𝕏),\eta (𝕏))`$, the solution of the random equations (3.13).

The corresponding version of (3.9) is

$`Z_n(\mathrm{},s)=\mathrm{exp}\left(\zeta {\displaystyle \frac{\mathrm{}}{M}}+s\eta +{\displaystyle \underset{j=1}{\overset{n}{}}}\mathrm{log}\left(2\mathrm{cosh}\left(\zeta {\displaystyle \frac{X_j}{M}}+\eta \right)\right)\right)I_n(𝕏).`$ (5.1)
Here $`I_n(𝕏)`$ is the random integral

$$I_n(𝕏)=\frac{1}{\pi ^2}\underset{x,y(\pi /2,\pi /2]}{}e^{i(\mathrm{}x+sy)}f(x,y;𝕏)𝑑x𝑑y,$$
(5.2)
where

$`f(x,y;𝕏):=`$ $`𝔼(\mathrm{exp}(i(x𝝈𝕏+y𝝈𝕖))|𝕏)`$ (5.3)
$`=`$ $`{\displaystyle \underset{j=1}{\overset{n}{}}}\left[p(X_j/M)e^{i\left(xX_j+y\right)}+q(X_j/M)e^{i\left(xX_j+y\right)}\right],`$
with the shorthands $`p(u)`$ and $`q(u)`$ for $`P(\zeta u+\eta )`$ and $`1P(\zeta u+\eta )`$, where $`(\zeta ,\eta )`$ is the solution of (4.2), and $`P()`$ is given by (3.8). Now that the summands in (5.1) are simply i.i.d. random variables, the core of the problem is to determine the asymptotically likely behavior of $`I_n(𝕏)`$.

###### Theorem 5.1

Suppose that $`lim\; sup|s|/n<b_c`$, $`0<lim\; inf\kappa `$, $`lim\; sup(\kappa \kappa _{}(b))<0`$, $`\mathrm{}=o(Mn^{1/2})`$ and $`n=o(M^2)`$. Then there is a constant $`\delta >0`$ such that, with probability $`1O(e^{\delta \mathrm{log}^2n})`$,

$$I_n(𝕏)=(1+o(1))\frac{1}{\pi Mn\sqrt{\text{det}R}}\mathrm{exp}(\frac{1}{4}𝝉_nR^1𝝉_n^{}).$$
(5.4)
Here

$$R=\left(\begin{array}{cc}2𝔼(U^2p(U)q(U))& 2𝔼(Up(U)q(U))\\ 2𝔼(Up(U)q(U))& 2𝔼(p(U)q(U))\end{array}\right),$$
(5.5)
and $`𝛕_n`$ is a two-dimensional random vector which converges in probability to a Gaussian vector $`𝛕`$, with mean zero and covariance matrix

$$K=\left(\begin{array}{cc}\text{Var}(U(p(U)q(U))& \text{cov}(U(p(U)q(U)),p(U)q(U))\\ \text{cov}(U(p(U)q(U)),p(U)q(U))& \text{Var}(p(U)q(U))\end{array}\right),$$
(5.6)
where $`U`$ is uniformly distributed on $`[0,1]`$. Furthermore, $`𝛕_n\mathrm{log}n`$ with probability at least $`1O(e^{\delta log^2n})`$.

Consequently, with probability $`1O(e^{\delta \mathrm{log}^2n})`$, $`Z_n(\mathrm{},s)1`$ and

$$\mathrm{log}Z_n(\mathrm{},s)=n[L(\zeta ,\eta )\kappa \mathrm{log}2]+n^{1/2}S_n+o(n^{1/2}),$$
(5.7)
where

$$S_n=\frac{1}{n^{1/2}}\underset{j=1}{\overset{n}{}}\left(\mathrm{log}\left(2\mathrm{cosh}\left(\zeta \frac{X_j}{M}+\eta \right)\right)𝔼\left[\mathrm{log}\left(2\mathrm{cosh}\left(\zeta \frac{X_j}{M}+\eta \right)\right)\right]\right)$$
(5.8)
is asymptotically Gaussian with zero mean and variance $`\sigma ^2=\text{Var}(\mathrm{log}(2\mathrm{cosh}(\zeta U+\eta )))`$.

###### Remark 5.1

It is a consequence of Theorem 4.1 and Theorem 5.1 that for all $`b[0,b_c)`$,

$$\kappa _{}(b)\kappa _c(b),$$
(5.9)
with

$$\kappa _{}(0)=\kappa _c(0)=1\text{and}\kappa _{}(b_c)=\kappa _c(b_c)=0.$$
(5.10)
Indeed, let us assume that $`lim\; inf(\kappa _{}(b)\kappa )>0`$. By Theorem 5.1, we then have that $`n^1\mathrm{log}Z_n(\mathrm{},s)\left[L(\zeta ,\eta )\kappa \mathrm{log}2\right]0`$ in probability. In particular, since w.h.p. $`Z_n(\mathrm{},s)1`$, we have $`lim\; inf(L(\zeta ,\eta )\kappa \mathrm{log}2)=lim\; inf(\kappa _c(b)\kappa )\mathrm{log}20.`$ So the condition $`lim\; inf(\kappa _{}(b)\kappa )>0`$ implies that $`lim\; inf(\kappa _c(b)\kappa )0`$, which proves (5.9). Since $`\zeta (0)=\eta (0)=0`$, it follows from the definitions (1.3) – (1.5) that $`\kappa _{}(0)=\kappa _c(0)=1`$. Finally, by Theorem 4.1, we have $`\widehat{L}(b_c)=0`$, or $`\kappa _c(b_c)=1`$. Numerical computations indicate that $`\kappa _{}(b)<\kappa _c(b)`$ for $`0<b<b_c`$, but the graphs of two functions remain surprisingly close to each other. Our limited attempts to prove this strict inequality have not succeeded.

Proof of Theorem 5.1: Pick a large, but fixed, $`B>0`$. Split the integration into two parts, $`|x|B/M`$ and $`|x|>B/M`$, and denote the corresponding integral $`I_{n1}(𝕏)`$ and $`I_{n2}(𝕏)`$, respectively. Consider $`I_{n1}(𝕏)`$ first. Begin with

$`|p(X_j/M)e^{i\left(xX_j+y\right)}+`$ $`q(X_j/M)e^{i\left(xX_j+y\right)}|^2`$ (5.11)
$`=12p_jq_j(1\mathrm{cos}(2\left(xX_j+y\right)))`$
$`\mathrm{exp}\left(2p_jq_j(1\mathrm{cos}(2(xX_j+y)))\right),`$
where we have introduced the abbreviations $`p_j=p(X_j/M)`$ and $`q_j=q(X_j/M)`$. Let

$$𝒮_n=\{j:X_j/M\pi /(3B)\}.$$
(5.12)
Clearly, $`j𝒮_n`$ implies

$$2|xX_j+y|2\left(\frac{B}{M}X_j+\frac{\pi }{2}\right)\frac{5\pi }{3}<2\pi .$$
(5.13)
Now, there exist a constant $`c_1>0`$ such that

$$1\mathrm{cos}\alpha c_1\alpha ^2,\alpha [5\pi /3,5\pi /3].$$
(5.14)
Since

$$2p_jq_j=\frac{1}{2\mathrm{cosh}^2(\zeta X_j/M+\eta )}\frac{1}{\mathrm{max}\{2\mathrm{cosh}^2(\eta ),\mathrm{\hspace{0.17em}2}\mathrm{cosh}^2(\zeta +\eta )\}},$$
(5.15)
we thus have shown that there exist a $`c_2>0`$ such that

$`|f(x,y;𝕏)|`$ $`\mathrm{exp}\left(c_2{\displaystyle \underset{j𝒮_n}{}}\left(xX_j+y\right)^2\right)`$ (5.16)
$`=`$ $`\mathrm{exp}\left(c_2(x^2M_2+2xyM_1+y^2M_0)\right),`$
where

$$M_k=M_k(B)=\underset{j𝒮_n}{}X_j^{(k)}=\underset{j=1}{\overset{n}{}}X_j^{(k)}(B),X_j^{(k)}(B):=X_j^k𝕀_{\{X_j/M\pi /(3B)\}}.$$
(5.17)
Since $`X_j^{(k)}(B)`$ are independent with $`X_j^{(k)}(B)/𝔼[X_j^{(k)}(B)]=O(B)`$, the event

$$A_n=\{M_k[0.99n𝔼(X^{(k)}(B)),\mathrm{\hspace{0.17em}1.01}n𝔼(X^{(k)}(B))],k=0,1,2\}$$
(5.18)
has probability $`1O(e^{\delta _1n})`$ for some $`\delta _1>0`$, by, e.g., the Azuma-Hoeffding inequality.

We continue our computation on the event $`A_n`$. It is easy to see that

$$x^2M_2+2xyM_1+y^2M_0c_3n\left[(Mx)^2+y^2\right],c_3>0.$$
(5.19)
Set $`r_n=n^{1/2}\mathrm{log}n`$. From (5.16) and (5.19), it follows that, for $`c_4=c_2c_3`$,

$`{\displaystyle \underset{\genfrac{}{}{0pt}{}{(Mx,y)r_n}{|x|B/M}}{}}|f(x,y;𝕏)|𝑑x𝑑y`$ $`{\displaystyle \frac{1}{Mn}}\left({\displaystyle \underset{𝕫\mathrm{log}n}{}}e^{c_4𝕫^2}𝑑z_1𝑑z_2\right)=O\left((Mn)^1e^{c_4\mathrm{log}^2n}\right).`$ (5.20)
For $`(Mx,y)r_n`$, we expand and exponentiate:

$`p_je^{i\left(xX_j+y\right)}+`$ $`q_je^{i\left(xX_j+y\right)}=`$ (5.21)
$`=1+i\left(xX_j+y\right)(p_jq_j){\displaystyle \frac{1}{2}}\left(xX_j+y\right)^2+O(|xX_j|^3+|y|^3)`$
$`=\mathrm{exp}(i(xX_j+y)(p_jq_j){\displaystyle \frac{1}{2}}(xX_j+y)^2`$
$`+{\displaystyle \frac{1}{2}}(xX_j+y)^2(p_jq_j)^2+O(|xX_j|^3+|y|^3))`$
$`=\mathrm{exp}(i(xX_j+y)(p_jq_j)`$
$`2p_jq_j(x^2X_j^2+2X_jxy+y^2)+O(|xX_j|^3+|y|^3)).`$
Therefore,

$`e^{i(\mathrm{}x+sy)}f(x,y;𝕏)=`$ $`e^{i(Mx)(T_{n1}\mathrm{}/M)+iy(T_{n2}s)}`$ (5.22)
$`\times \mathrm{exp}((Mx,y)Q(Mx,y)^{}+O(nM^3|x|^3+n|y|^3)),`$
where $`(Mx,y)^{}`$ denotes the transpose of $`(Mx,y)`$, and

$`T_{n1}=`$ $`{\displaystyle \underset{j}{}}(X_j/M)(p_jq_j),`$ (5.23)
$`T_{n2}=`$ $`{\displaystyle \underset{j}{}}(p_jq_j),`$
$`Q_{11}=`$ $`{\displaystyle \underset{j}{}}(X_j/M)^22p_jq_j,`$ (5.24)
$`Q_{12}=`$ $`{\displaystyle \underset{j}{}}(X_j/M)2p_jq_j`$
$`Q_{22}=`$ $`{\displaystyle \underset{j}{}}2p_jq_j.`$
Here $`T_{n1},T_{n2}`$ are sums of i.i.d. random variables, and it is easy to show that the random vector

$$𝝉_n=(\tau _{n1},\tau _{n2}):=n^{1/2}(T_{n1}𝔼(T_{n1}),T_{n2}𝔼(T_{n2}))$$
(5.25)
is asymptotically Gaussian, with zero means, and the covariance matrix $`\{K_M(i,j)\}`$, with

$`K_M(1,1)=`$ $`\text{Var}(U_M(p(U_M)q(U_M))),`$ (5.26)
$`K_M(1,2)=`$ $`\text{cov}(U_M(p(U_M)q(U_M)),p(U_M)q(U_M)),`$
$`K_M(2,2)=`$ $`\text{Var}(p(U_M)q(U_M)),`$
and $`U_M`$ distributed uniformly on $`\{1/M,\mathrm{},M/M\}`$. Consequently

$$K_M=K+O(M^1),$$
(5.27)
where $`K`$ is defined like $`K_M`$, with $`U_M`$ replaced by the $`[0,1]`$-uniform $`U`$, which is the matrix $`K`$ defined in (5.6). We can use $`K`$ as the limiting covariance matrix for $`𝝉_n`$. Also, again by Azuma-Hoeffding, for any $`c>0`$,

$$𝝉_nc\mathrm{log}n$$
(5.28)
with probability $`1O(e^{\delta _2\mathrm{log}^2n})`$ for some $`\delta _2=\delta _2(c)>0`$. In addition,

$`𝔼(T_{n1})=`$ $`n𝔼\left[(X/M)(p(X/M)q(X/M))\right]=n𝔼(U(p(U)q(U)))+O(n/M)`$ (5.29)
$`=`$ $`O(n/M),`$
$`𝔼(T_{n2})=`$ $`n𝔼\left[p(X/M)q(X/M)\right]=n𝔼(p(U)q(U))+O(n/M)`$
$`=`$ $`s+O(n/M).`$
Using the equations (5.25) and (5.29), we obtain

$`T_{n1}\mathrm{}/M`$ $`=`$ $`n^{1/2}\left(\tau _{n1}+O(n^{1/2}/M+|\mathrm{}|/(Mn^{1/2}))\right),`$
$`T_{n2}s`$ $`=`$ $`n^{1/2}\left(\tau _{n2}+O(n^{1/2}/M)\right).`$
Both remainder terms are $`o(1)`$ since $`n^{1/2}=o(M)`$ and $`\mathrm{}=o(Mn^{1/2})`$. Since $`Q_{ij}`$ is a sum of $`n`$ bounded i.i.d. random variables, $`Q_{ij}=𝔼(Q_{ij})+O(n^{1/2}\mathrm{log}n)`$ with probability $`1O(e^{\delta _3log^2n})`$ for some $`\delta _3>0`$. Approximating $`𝔼(Q_{ij})`$ as $`𝔼(Q_{ij})=n[R_{ij}+O(M^1)]=n[R_{ij}+o(n^{1/2})]`$, where

$`R_{11}=`$ $`2𝔼(U^2p(U)q(U)),`$ (5.30)
$`R_{12}=`$ $`2𝔼(Up(U)q(U)),`$
$`R_{22}=`$ $`2𝔼(p(U)q(U)),`$
we get

$$Q=n(R+O(n^{1/2}\mathrm{log}n))$$
(5.31)
with probability $`1O(e^{\delta _3\mathrm{log}^2n})`$.

Consequently, with probability $`1O(e^{\delta _3\mathrm{log}^2n})`$,

$$\begin{array}{c}\underset{(Mx,y)r_n}{}e^{i(\mathrm{}x+sy)}f(x,y;𝕏)𝑑x𝑑y\hfill \\ \hfill =\underset{(Mx,y)r_n}{}\mathrm{exp}\left(i(Mn^{1/2}x)(\tau _{n1}+o(1))+i(n^{1/2}y)(\tau _{n2}+o(1))\right)\\ \hfill \mathrm{exp}\left((Mx,y)Q(Mx,y)^{}+O(|Mx|^3n+|y|^3n)\right)dxdy\\ \hfill =\frac{1}{Mn}\left[\frac{\pi }{\sqrt{\text{det }R}}\mathrm{exp}\left(\frac{1}{4}𝝉_nR^1𝝉_n^{}\right)+o(1)\right].\end{array}$$
(5.32)
Using (5.20) and (5.28), we see that the r.h.s. of (5.32) also gives the asymptotics of $`I_{n1}(𝕏)`$, the integral over all $`(x,y)`$ with $`|x|B/M`$.

Let us turn now to $`I_{n2}(𝕏)`$. We want to show that for some $`\delta >0`$ we have $`I_{n2}=o(I_{n1})`$ with probability $`1O(e^{\delta \mathrm{log}^2n})`$. First of all, by (5.2), (5.3) and the definition of $`I_{n2}(𝕏)`$,

$$|I_{n2}(𝕏)|^2=\frac{1}{\pi ^4}\underset{\genfrac{}{}{0pt}{}{|x_1|,|x_2|[B/M,\pi /2]}{y_1,y_2(\pi /2,\pi /2]}}{}e^{i\mathrm{}(x_1x_2)is(y_1y_2)}F(𝕩,𝕪;𝕏)𝑑𝕩𝑑𝕪,$$
(5.33)
where

$`F(𝕩,𝕪;𝕏)=`$ $`f(x_1,y_1;𝕏)\overline{f(x_2,y_2;𝕏)}`$ (5.34)
$`=`$ $`{\displaystyle \underset{j=1}{\overset{n}{}}}[p_j^2e^{i(x_1^{}X_j+y_1^{})}+q_j^2e^{i(x_1^{}X_j+y_1^{})}`$ (5.35)
$`+`$ $`p_jq_j(e^{i(x_2^{}X_j+y_2^{})}+e^{i(x_2^{}X_j+y_2^{})})],`$ (5.36)
and

$$x_1^{}=x_1x_2,x_2^{}=x_1+x_2;y_1^{}=y_1y_2,y_2^{}=y_1+y_2.$$
(5.37)
Therefore

$$𝔼(|I_{n2}(𝕏)|^2)\frac{1}{\pi ^4}\underset{\genfrac{}{}{0pt}{}{|x_1|,|x_2|[B/M,\pi /2]}{y_1,y_2(\pi /2,\pi /2]}}{}|F(𝕩,𝕪)|^n𝑑𝕩𝑑𝕪,$$
(5.38)
where

$`F(𝕩,𝕪)=`$ $`{\displaystyle \frac{1}{M}}{\displaystyle \underset{j}{}}p^2(j/M)e^{i(x_1^{}j+y_1^{})}+{\displaystyle \frac{1}{M}}{\displaystyle \underset{j}{}}q^2(j/M)e^{i(x_1^{}j+y_1^{})}`$ (5.39)
$`+`$ $`{\displaystyle \frac{1}{M}}{\displaystyle \underset{j}{}}p(j/M)q(j/M)(e^{i(x_2^{}j+y_2^{})}+e^{i(x_2^{}j+y_2^{})}).`$
To proceed, we need the following lemma.

###### Lemma 5.1

Let $`g(u)`$ be continuously differentiable on $`[0,1]`$. Then, for $`x2\pi `$ and for all $`y`$,

$$\left|\underset{j=1}{\overset{M}{}}g(j/M)e^{i(xj+y)}\right|\frac{2g+g^{}}{|e^{ix}1|},$$
(5.40)
where $`g:=\mathrm{max}\{|g(u)|:u[0,1]\}`$, and $`g^{}:=\mathrm{max}\{|g^{}(u)|:u[0,1]\}`$.

Proof of Lemma 5.1. First write

$$\begin{array}{c}\underset{j=1}{\overset{M}{}}g(j/M)e^{i(xj+y)}=\underset{j=1}{\overset{M}{}}\frac{e^{i(x(j+1)+y)}e^{i(xj+y)}}{e^{ix}1}g(j/M)\hfill \\ \hfill =\frac{1}{e^{ix}1}[g(1/M)e^{i(x+y)}+g(M/M)e^{i(x(M+1)+y)}\\ \hfill \underset{j=1}{\overset{M1}{}}(g((j+1)/M)g(j/M))e^{i(x(j+1)+y)}].\end{array}$$
(5.41)
Since each of the differences in the last sum has absolute value bounded by $`M^1g^{}`$, while the first two terms are clearly bounded by $`g`$, we obtain (5.40). $`\mathrm{}`$

Returning to the proof of the theorem, we observe that since $`|x_t|\pi /2`$, we have $`|x_t^{}|\pi `$, $`t=1,2`$. Furthermore,

$$B/M|x_t|=0.5|x_1^{}\pm x_2^{}|,t=1,2,$$
(5.42)
implies that $`\mathrm{max}\{|x_1^{}|,|x_2^{}|\}B/M`$. If $`|x_1^{}|B/M`$, then applying Lemma 5.1 to the first two sums in (5.39), we obtain

$`|F(𝕩,𝕪)|`$ $`{\displaystyle \frac{2}{M}}{\displaystyle \underset{j}{}}p(j/M)q(j/M)+O(B^1)`$ (5.43)
$`=`$ $`2{\displaystyle _0^1}p(u)q(u)𝑑u+O(B^1).`$
If $`|x_2^{}|B/M`$, then likewise

$$|F(𝕩,𝕪)|_0^1(p^2(u)+q^2(u))𝑑u+O(B^1).$$
(5.44)
And, if $`\mathrm{min}\{|x_1^{}|,|x_2^{}|\}B/M`$, then

$$|F(𝕩,𝕪)|=O(B^1).$$
(5.45)
Since the right hand side of (5.43) is dominated by the right hand side of (5.44) (just use that $`2pqp^2+q^2`$), we conclude that there is a constant $`c`$ independent of $`B`$ such that

$$|F(𝕩,𝕪)|\rho +cB^1\text{or}|F(𝕩,𝕪)|cB^1,$$
(5.46)
depending upon whether only one or both $`|x_t^{}|`$ exceeds $`B/M`$. Here

$`\rho =`$ $`{\displaystyle _0^1}(p^2(u)+q^2(u))𝑑u={\displaystyle _0^1}\left(1{\displaystyle \frac{1}{2}}\mathrm{cosh}^2(\zeta u+\eta )\right)𝑑u`$ (5.47)
$`=`$ $`1{\displaystyle \frac{\mathrm{tanh}(\zeta +\eta )\mathrm{tanh}(\eta )}{2\zeta }}`$
$`=2^{\kappa _{}(b)}.`$
We conclude then that

$$𝔼(|I_{n2}(𝕏)|^2)(c/B)^n+O\left(M^1(\rho +c/B)^n\right).$$
(5.48)
Since $`M\rho ^n`$ is exponentially small if $`lim\; sup(\kappa \kappa _{}(b))<0`$, we get that for $`B`$ large enough, there exists a $`\delta _4>0`$ such that

$$𝔼(|I_{n2}(𝕏)|^2)e^{\delta _4n}(Mn)^2.$$
(5.49)
On the other hand, $`|I_{n1}(𝐗)|^2=(Mn)^2e^{O(\mathrm{log}n^2)}`$ with probability $`1O(e^{\delta _2\mathrm{log}^2n})O(e^{\delta _3\mathrm{log}^2n})`$ by (5.28) and (5.32). Thus $`|I_{n2}(𝕏)|=o(|I_{n1}(𝐗)|)`$ with probability at least $`1O(e^{\delta _5\mathrm{log}^2n})`$, implying (5.4). To prove (5.7), we just note that the prefactor in (5.1) can be rewritten as

$`\mathrm{exp}(`$ $`\zeta {\displaystyle \frac{\mathrm{}}{M}}+s\eta +{\displaystyle \underset{j=1}{\overset{n}{}}}\mathrm{log}\left(2\mathrm{cosh}(\zeta {\displaystyle \frac{X_j}{M}}+\eta )\right))`$ (5.50)
$`=\mathrm{exp}\left(\zeta {\displaystyle \frac{\mathrm{}}{M}}+s\eta +n^{1/2}S_n+n{\displaystyle _0^1}\mathrm{log}\left(2\mathrm{cosh}(\zeta x+\eta )\right)𝑑x+O(nM^1)\right)`$
$`=\mathrm{exp}\left(nL(\zeta ,\eta )+n^{1/2}S_n+O(nM^1)+\zeta \mathrm{}/M\right),`$
while, with probability $`1O(e^{\delta \mathrm{log}^2n})`$,

$$I_n(𝕏)=M^1e^{O(\mathrm{log}^2n)}=M^1e^{o(n^{1/2})}.$$
(5.51)
$`\mathrm{}`$

###### Remark 5.2

As the reader may have noticed, the condition that $`\mathrm{}`$ has the same parity as $`_jX_j`$ has not been used in the above proof. Thus the asymptotics stated in (5.4) hold for all $`\mathrm{}`$ with $`\mathrm{}=o(Mn^{1/2})`$, independent of the parity of $`\mathrm{}`$. But this does not mean that the corresponding asymptotics hold for the number of partitions $`Z_n(\mathrm{},s)`$, since (5.1) is valid only if the parity of $`\mathrm{}`$ is the same as that of $`_jX_j`$. If this condition is violated, the left hand side of (5.1) is zero, while w.h.p., the random integral $`I_n(𝕏)`$ is different from zero.

Applied to the special case $`|\mathrm{}|1`$, Theorem 5.1 asserts, roughly, that for every point $`(b,\kappa )`$ such that $`b<b_c`$ and $`\kappa <\kappa _{}(b)<1`$, w.h.p. there are exponentially many perfect partitions. In fact, if in the right hand side of (5.1) the random integral $`I_n(𝐗)`$ is replaced by the leading term in (5.4), then the resulting product remains exponentially large within the narrow (crescent-shaped) region between $`\kappa =\kappa _{}(b)`$ and $`\kappa =\kappa _c(b)`$. In principle, this may mean that the likely number of perfect partitions remains exponentially large in this extended region! An extensive numerical simulation (see Section 9) strongly suggests that the expected logarithm of the number of perfect partitions at every point of the region $`\kappa <\kappa _c(b)`$ is extremely well approximated by the expected logarithm of the above-mentioned product. Based on our experience with the unconstrained problem and these simulations, we expect that w.h.p. at least the weaker formula

$$\mathrm{log}Z_n(\mathrm{},s)=n[L(\zeta ,\eta )\kappa \mathrm{log}2+o(1)]n,$$
(5.52)
cf.(5.7), remains valid in the whole region $`lim\; sup(\kappa \kappa _c(b))<0`$.

### 5.2 Distribution of the Bias

Let us have a closer look at the case $`|\mathrm{}|1`$ and $`s=o(n)`$. A simple computation shows that

$$\zeta =6\frac{s}{n}+O((s/n)^2),\eta =4\frac{s}{n}+O((s/n)^2),$$
(5.53)
so that

$$p(u)=P(\zeta u+\eta )=\frac{1}{2}+O(|s|/n),$$
(5.54)
and the entries of the covariance matrix $`K`$ are of order $`O(|s|/n)`$. Furthermore

$$R=\left(\begin{array}{cc}1/6+O(|s|/n)& 1/4+O(|s|/n)\\ 1/4+O(|s|/n)& 1/2+O(|s|/n)\end{array}\right),$$
(5.55)
so that $`\text{det}R=1/(48)+O(|s|/n)`$, and (5.4) yields

$$I_n(𝕏)=(1+o_p(1))\frac{4\sqrt{3}}{\pi Mn}.$$
(5.56)
In addition, the exponential factor in the formula for $`Z_n(\mathrm{},s)`$ becomes $`2^ne^{S_n}`$, where

$`S_n=`$ $`4{\displaystyle \frac{s^2}{n}}+O(|s|/(nM)+|s|^3/n^2)`$ (5.57)
$`+{\displaystyle \frac{1}{2}}{\displaystyle \underset{j=1}{\overset{n}{}}}(\zeta X_j/M+\eta )^2+O(s^4/n^3).`$
By the central limit theorem and (5.53), the sum can be written as

$`\zeta ^2\left(n𝔼(U^2)+O_p(n^{1/2})\right)+2\zeta \eta \left(n𝔼(U)+O_p(n^{1/2})\right)+\eta ^2n`$ (5.58)
$`=`$ $`4{\displaystyle \frac{s^2}{n}}+O(|s|^3/n^2)+O_p(s^2/n^{3/2})`$
$`=`$ $`4{\displaystyle \frac{s^2}{n}}+o_p(1),`$
uniformly for $`|s|n^{2/3}\omega ^1(n)`$, where $`\omega (n)\mathrm{}`$, however slowly. Thus (5.57) simplifies to

$$S_n=2\frac{s^2}{n}+o_p(1).$$
(5.59)
Using this formula and (5.56) we obtain

$$Z_n(\mathrm{},s)=(1+o_p(1))\frac{4\sqrt{3}}{\pi }\frac{2^n}{Mn}e^{2s^2/n},$$
(5.60)
uniformly for $`|s|n^{2/3}\omega ^1(n)`$ and $`|\mathrm{}|1`$; and, of course, $`sn(\text{mod }2)`$, and $`\mathrm{}_jX_j(\text{mod }2)`$. In  it was shown that, for $`Mn^{1/2}/2^n0`$, $`Y_n(\mathrm{})=_{s=\mathrm{}}^{\mathrm{}}Z_{\mathrm{},s}`$, the total number of partitions444Note that $`Y_n(\mathrm{})`$ is equal to the total number of perfect partitions if $`\mathrm{}=0`$, and equal to half the total number of perfect partitions if $`\mathrm{}=1`$. In a similar way, $`Z_n(\mathrm{},s)`$ is the total number of perfect partitions with bias $`s`$ if $`\mathrm{}=0`$, and half that number if $`\mathrm{}=1`$. with $`𝝈𝕏=\mathrm{}`$ is asymptotic, in probability, to $`\frac{2^{n+1}\sqrt{3}}{M\sqrt{2\pi n}}`$. Let $`s_n`$ denote the bias of a perfect partition $`𝝈^{(n)}`$ chosen uniformly at random from all perfect partitions. The formula for $`Y_n(\mathrm{})`$ and (5.60) prove the following corollary of Theorem 5.1.

###### Corollary 5.1

Assume that $`lim\; sup\frac{1}{n}\mathrm{log}_2M<1`$. Then

$$(s_n=s|𝕏)=(1+o_p(1))\frac{2\sqrt{2}}{\sqrt{\pi n}}e^{2s^2/n}$$
(5.61)
uniformly for $`|s|n^{2/3}\omega ^1(n)`$, ($`sn(\text{mod }2)`$), and consequently

$$\left(\frac{|s_n|}{\frac{n^{1/2}}{2}}a|𝕏\right)_p\sqrt{\frac{2}{\pi }}\underset{0}{\overset{a}{}}e^{u^2/2}𝑑u.$$
(5.62)
###### Remark 5.3

Thus the bias of the randomly selected (typical) perfect partition is exactly of order $`n^{1/2}`$, just like $`t_n`$, the bias of the sequence of $`n`$ flips of a fair coin, i.e. the difference between number of heads and number of tails of a fair coin. However,

$$\left(\frac{|t_n|}{n^{1/2}}a\right)\sqrt{\frac{2}{\pi }}\underset{0}{\overset{a}{}}e^{u^2/2}𝑑u,$$
(5.63)
i.e. in distribution the bias of the random perfect partition is, in the limit, half as large as the bias of the sequence of $`n`$ coin flips. Perhaps we should have anticipated some reduction of the typical bias, since perfect partitions are by definition those with the smallest discrepancy, which should favor smaller bias. In retrospect, the fact that most perfect partitions turn out to have small bias may be responsible for the greater mathematical tractability of the unconstrained problem.

## 6 The Hard Phase

### 6.1 Lower Bounds on the Minimal Discrepancy

Cautiously extrapolating the asymptotic formula in Theorem 5.1, we expect that w.h.p. there will be no perfect partitions in the domain where this expression tends to zero, that is where $`\kappa >\kappa _c(b)`$. Here we establish this result outside a small window of width $`n^{1/2}`$ above $`\kappa _c`$.

###### Theorem 6.1

Suppose that $`lim\; sup|s|/n<b`$ and that $`0<lim\; inf\kappa lim\; sup\kappa <\mathrm{}`$. Let $`S_n`$ be the random variable defined in (5.8), let $`\mathrm{}_n`$ be a sequence of positive integers with $`\mathrm{}_n=o(Mn^{1/2})`$ and let $`|\mathrm{}|<\mathrm{}_n`$. Then, with probability at least $`1O(e^{\mathrm{log}^2n})`$,

$$Z_n(\mathrm{},s)2^{[\kappa _c(b)\kappa ]n}e^{n^{1/2}S_n}e^{\mathrm{log}^2n+O(\mathrm{}/M)}$$
(6.1)
and

$$\underset{\mathrm{}:|\mathrm{}|<\mathrm{}_n}{}Z_n(\mathrm{},s)\mathrm{}_n2^{[\kappa _c(b)\kappa ]n}e^{n^{1/2}S_n}e^{\mathrm{log}^2n+O(\mathrm{}_n/M)}.$$
(6.2)
If $`(\kappa \kappa _c(b))n^{1/2}\mathrm{}`$, we thus have

$$d_{opt}2^{[\kappa \kappa _c(b)O_p(n^{1/2})]n},$$
(6.3)
so that w.h.p. there are no perfect partitions.

###### Remark 6.1

(i) The proof of (6.3) can be generalized to show that there is a constant $`\delta >0`$ such that, with probability $`1O(e^{\delta \mathrm{log}^2n})`$,

$$d_{opt}2^{[\kappa \kappa _c(b)n^{1/2}\mathrm{log}n]n}.$$
(6.4)
For $`\kappa \kappa _c(b)1+n^{1/2}\mathrm{log}n`$, there are therefore no perfect partitions with probability $`1O(e^{\delta \mathrm{log}^2n})`$.

(ii) If $`|\kappa \kappa _c(b)|=O(n^{1/2})`$, the term $`n^{1/2}S_n`$ is larger than $`n|\kappa \kappa _c(b)|`$ with positive probability, implying that with positive probability, $`Z_n(\mathrm{},s)`$ is smaller than $`1`$, and hence zero. The above theorem therefore implies that for $`|\kappa \kappa _c(b)|=O(n^{1/2})`$, the probability that there are no perfect partitions stays bounded away from zero.

(iii) As mentioned in Remark 2.2, we believe that $`d_{opt}=2^{[\kappa \kappa _c+o_p(1)]n}`$ whenever $`lim\; inf(\kappa \kappa _c)>0`$. In other words, we believe that for every $`\epsilon >0`$, w.h.p., $`d_{opt}2^{[\kappa \kappa _c+\epsilon ]n}`$. If we assume such a bound, then w.h.p. the number of optimal partition $`Z_{opt}`$ is bounded by the right hand side of (6.2) with $`\mathrm{}_n=2^{[\kappa \kappa _c+\epsilon ]n}`$, implying that w.h.p. $`Z_{opt}2^{2\epsilon n}`$. Since $`\epsilon `$ was arbitrary, we get $`Z_{opt}=e^{o_p(n)}`$ whenever $`lim\; inf(\kappa \kappa _c)>0`$.

Proof of Theorem 6.1 and Remark 6.1 (i). The bounds (6.3) and (6.4) follow from (6.2). Indeed, let $`\omega _n`$ be such that $`\omega _n\mathrm{}`$ and $`[\kappa \kappa _c(n)]n^{1/2}\omega _n\mathrm{}`$ as $`n\mathrm{}`$. Setting $`\mathrm{}_n=2^{[\kappa \kappa _c(b)]nn^{1/2}\omega _n}`$, the bound (6.2) immediately implies $`d_{opt}\mathrm{}_n`$, which gives (6.3). To prove (6.4), we set $`\mathrm{}_n=2^{[\kappa \kappa _c(b)n^{1/2}\mathrm{log}n]n}`$ and observe that for $`\delta `$ sufficiently small, $`S_n`$ is bounded by $`\frac{1}{2}\mathrm{log}n`$ with probability $`1O(e^{\delta \mathrm{log}^2n})`$. As a consequence, the r.h.s. of (6.2) goes to zero with probability $`1O(e^{\delta \mathrm{log}^2n})`$, implying again that $`d_{opt}\mathrm{}_n`$.

It is thus enough to prove (6.1) and (6.2). Note that the bound (6.2) is not just a consequence of the bound (6.1) since the intersection of $`2\mathrm{}_n1`$ events happening with high probability does not necessarily happen with high probability if $`\mathrm{}_n`$ is not bounded.

Using (5.50), we rewrite $`Z_n(\mathrm{},s)`$ as

$$Z_n(\mathrm{},s)=2^{n\kappa _c(b)}e^{n^{1/2}S_n+\zeta \mathrm{}/M+O(nM^1)}𝒵_n(\mathrm{},s),$$
(6.5)
where $`S_n`$ is defined in (5.8) and

$$𝒵_n(\mathrm{},s)=\frac{1}{2\pi ^2}\underset{\genfrac{}{}{0pt}{}{x(\pi ,\pi ]}{y(\pi /2,\pi /2]}}{}e^{i(\mathrm{}x+sy)}f(x,y;𝕏)𝑑x𝑑y,$$
(6.6)
with $`f(x,y;𝕏)`$ as defined in (5.3). In contrast to (5.1), the relation (6.5) holds whether $`\mathrm{}`$ has the same parity as $`_jX_j`$ or not, since $`x`$ is now integrated over $`[\pi ,\pi )`$ instead of $`[\pi /2,\pi /2)`$. Introducing finally

$$𝒵_n(s)=\underset{\mathrm{}:|\mathrm{}|<\mathrm{}_n}{}𝒵_n(\mathrm{},s),$$
(6.7)
we have

$`{\displaystyle \underset{\mathrm{}:|\mathrm{}|<\mathrm{}_n}{}}Z_n(\mathrm{},s)`$ $`=2^{n\kappa _c}e^{n^{1/2}S_n+O(\mathrm{}_n/M)+O(nM^1)}𝒵_n(s).`$ (6.8)
Since $`nM^1=o(\mathrm{log}^2n)`$, the bounds (6.1) and (6.2) are equivalent to proving that, with probability $`1O(e^{\mathrm{log}^2n})`$, we have $`𝒵_n(\mathrm{},s)M^1e^{\mathrm{log}^2n}`$ and $`𝒵_n(s)\mathrm{}_nM^1e^{\mathrm{log}^2n}`$.

We will prove these bounds by establishing a suitable bound on the expectation of $`𝒵_n(\mathrm{},s)`$. To this end, we first rewrite $`𝔼(𝒵_n(\mathrm{},s))`$ as

$`𝔼(𝒵_n(\mathrm{},s))=`$ $`{\displaystyle \frac{1}{\pi ^2}}{\displaystyle \underset{\genfrac{}{}{0pt}{}{x(\pi ,\pi ]}{y(\pi /2,\pi /2]}}{}}e^{i\mathrm{}xisy}f^n(x,y)𝑑x𝑑y,`$ (6.9)
$`f(x,y)=`$ $`{\displaystyle \frac{1}{M}}{\displaystyle \underset{j}{}}p(j/M)e^{i(xj+y)}+{\displaystyle \frac{1}{M}}{\displaystyle \underset{j}{}}q(j/M)e^{i(xj+y)}.`$ (6.10)
As in the estimates of $`𝔼(|I_{n2}(𝕏)|^2)`$ in the proofs of Theorem 5.1, we need the bounds of $`|f(x,y)|`$ for various ranges of $`x,y`$.

Pick $`B>0`$. Let $`|x|B/M`$. Using Lemma 5.1 and (6.10), we get

$$|f(x,y)|c/B.$$
(6.11)
Let $`|x|B/M`$. Setting $`x=z/M`$, we have $`|z|B`$. For these $`x`$’s, let us bound $`|f(x,y)|`$ more sharply. We have

$$\begin{array}{c}\left|\frac{1}{M}\underset{j=1}{\overset{M}{}}p(j/M)e^{i(zj/M)+iy}\right|^2\hfill \\ \hfill =\frac{1}{M^2}\underset{j=1}{\overset{M}{}}p^2(j/M)+\frac{2}{M^2}\underset{j_1<j_2}{}p(j_1/M)p(j_2/M)\mathrm{cos}(z(j_1/Mj_2/M))\\ \hfill =\left(\frac{1}{M}\underset{j=1}{\overset{M}{}}p(j/M)\right)^2\frac{2}{M^2}\underset{j_1<j_2}{}p(j_1/M)p(j_2/M)\left(1\mathrm{cos}(z(j_1/Mj_2/M))\right).\end{array}$$
(6.12)
Here

$$\frac{1}{M}\underset{j=1}{\overset{M}{}}p(j/M)=_0^1p(u)𝑑u+O(M^1).$$
(6.13)
Pick a small $`\epsilon `$ and consider $`j_1<j_2`$ such that

$$B\frac{j_2j_1}{M}2\pi \epsilon j_2j_1\beta M,\beta =\frac{2\pi \epsilon }{B}.$$
(6.14)
Clearly there are $`\mathrm{\Theta }(\beta M^2)`$ such pairs $`(j_1,j_2)`$. For those $`(j_1,j_2)`$, and $`|z|B`$, there is a positive constant $`c=c(\epsilon )`$, such that

$$1\mathrm{cos}(z(j_1/Mj_2/M))c\left[z(j_1/Mj_2/M)\right]^2$$
(6.15)
So the double sum in (6.12) is bounded below by

$`{\displaystyle \frac{cz^2}{M^2}}{\displaystyle \underset{|j_1/Mj_2/M|\beta }{}}p(j_1/M)`$ $`p(j_2/M)(j_1/Mj_2/M)^2=(c^{}B^1+O(M^1))z^2,`$ (6.16)
$`c^{}=`$ $`{\displaystyle \frac{c}{B}}{\displaystyle \underset{\genfrac{}{}{0pt}{}{u_1,u_2[0,1]}{|u_1u_2|\beta }}{}}p(u_1)p(u_2)(u_1u_2)^2𝑑u_1𝑑u_2.`$
We thus obtain

$$\left|\frac{1}{M}\underset{j=1}{\overset{M}{}}p(j/M)e^{i(zj/M+y)}\right|^2\left(_0^1p(u)𝑑u+O(1/M)\right)^2(c^{}B^1+O(M^1))z^2,$$
(6.17)
so that

$$\left|\frac{1}{M}\underset{j=1}{\overset{M}{}}p(j/M)e^{i(zj/M+y)}\right|\left(_0^1p(u)𝑑u+O(M^1)\right)e^{\alpha _1B^1z^2},$$
(6.18)
for some positive constant $`\alpha _1`$. Analogously to (6.18),

$$\left|\frac{1}{M}\underset{j=1}{\overset{M}{}}q(j/M)e^{i(zj/M+y)}\right|\left(_0^1q(u)𝑑u+O(1/M)\right)e^{\alpha _2B^1z^2},(\alpha _2>0),$$
(6.19)
hence, for $`\alpha =\mathrm{min}\{\alpha _1,\alpha _2\}`$,

$$|f(x,y)|(1+O(M^1))e^{\alpha B^1z^2}e^{\alpha ^{}B^1z^2},\alpha ^{}>0,$$
(6.20)
for $`B|z|\mathrm{\Theta }(\sqrt{B/M})`$. The bounds (6.11) and (6.20) indicate that $`|f(x,y)|^n`$ is small for large and moderate values of $`z(=xM)`$, regardless of $`y`$. The value of $`y`$ begins to matter when $`z`$ is small. To see how, we need yet a sharper bound for $`|f(x,y)|`$ for small $`|z|`$. By the definition (6.10) of $`f(x,y)`$, we have

$`|f(x,y)|^2=`$ $`{\displaystyle \frac{1}{M^2}}{\displaystyle \underset{j_1,j_2}{}}p(j_1/M)p(j_2/M)e^{iz(j_1/Mj_2/M)}`$ (6.21)
$`+{\displaystyle \frac{1}{M^2}}{\displaystyle \underset{j_1,j_2}{}}q(j_1/M)q(j_2/M)e^{iz(j_2/Mj_1/M)}`$
$`+{\displaystyle \frac{1}{M^2}}{\displaystyle \underset{j_1,j_2}{}}p(j_1/M)q(j_2/M)e^{i(z(j_1/M+j_2/M)+2y)}`$
$`+{\displaystyle \frac{1}{M^2}}{\displaystyle \underset{j_1,j_2}{}}q(j_1/M)p(j_2/M)e^{i(z(j_1+j_2)+2y)},`$
so that

$`|f(x,y)|^2`$ $`\left({\displaystyle \frac{1}{M}}{\displaystyle \underset{j}{}}p(j/M)\right)^2+\left({\displaystyle \frac{1}{M}}{\displaystyle \underset{j}{}}q(j/M)\right)^2`$ (6.22)
$`+2\left({\displaystyle \frac{1}{M}}{\displaystyle \underset{j}{}}p(j/M)\right)\left({\displaystyle \frac{1}{M}}q(j/M)\right)`$
$`{\displaystyle \frac{2}{M^2}}{\displaystyle \underset{j_1,j_2}{}}p(j_1/M)q(j_2/M)\left[1\mathrm{cos}(z(j_1/M+j_2/M)+2y)\right].`$
Here the first three terms add up to

$$\left(\frac{1}{M}\underset{j}{}(p(j/M)+q(j/M))\right)^2=1.$$
(6.23)
Furthermore, picking $`z_0>0`$ small enough so that

$$2z_0+2|y|2(z_0+\pi /2)<2\pi \epsilon ,$$
(6.24)
we get: for $`|z|z_0`$,

$$1\mathrm{cos}(z(j_1/M+j_2/M)+2y)c\left[z(j_1/M+j_2/M)+2y\right]^2.$$
(6.25)
The first inequality in (6.24) holds because $`|y|\pi /2`$, a consequence of $`sn(\text{mod }2)`$.

So, within the factor $`2c`$, the double sum in (6.22) exceeds

$`{\displaystyle \frac{1}{M^2}}{\displaystyle \underset{j_1,j_2}{}}p(j_1/M)q(j_2/M)\left[z^2(j_1/M+j_2/M)^2+4yz(j_1/M+j_2/M)+4y^2\right]`$ (6.26)
$`=`$ $`z^2\left({\displaystyle \underset{u_1,u_2[0,1]}{}}p(u_1)q(u_2)(u_1+u_2)^2𝑑u_1𝑑u_2+O(M^1)\right)`$
$`+4yz\left({\displaystyle \underset{u_1,u_2[0,1]}{}}p(u_1)q(u_2)(u_1+u_2)𝑑u_1𝑑u_2+O(M^1)\right)`$
$`+4y^2\left({\displaystyle \underset{u_1,u_2[0,1]}{}}p(u_1)q(u_2)𝑑u_1𝑑u_2+O(M^1)\right),`$
Since the functions $`1`$ and $`u_1+u_2`$ are linearly independent, there exists $`c_0>0`$ such that, for $`M`$ large enough, the quadratic form is bounded below by $`c_0(z^2+y^2)`$. So

$$|f(x,y)|^21c_0(z^2+y^2)|f(x,y)|e^{c_0(z^2+y^2)/2},$$
(6.27)
if $`|z|z_0,y(\pi /2,\pi /2],MM(z_0)`$. Putting (6.20) and (6.27) together enables us to conclude that (6.27), with a possibly smaller $`c_0`$, holds for all $`z,y`$ with $`|z|B`$ and $`|y|\pi /2`$. Note however, that $`c_0`$ now depends on $`B`$ and goes to zero like $`B^1`$ as $`B\mathrm{}`$. Making this dependence explicit, we have that

$$|f(x,y)|e^{c_0^{}(z^2+y^2)/B}$$
(6.28)
whenever $`M`$ is large enough, $`|z|B`$ and $`|y|\pi /2`$.

Finally, for $`|z|,|y|`$ both small

$$e^{\pm i(z(j/M)+y)}=1\pm i(z\frac{j}{M}+y)\frac{1}{2}(z\frac{j}{M}+y)^2+O(|z|^3+|y|^3).$$
(6.29)
So

$`f(x,y)=`$ $`1+i\left(z{\displaystyle \frac{1}{M}}{\displaystyle \underset{j}{}}{\displaystyle \frac{j}{M}}\left(p({\displaystyle \frac{j}{M}})q({\displaystyle \frac{j}{M}})\right)+y{\displaystyle \frac{1}{M}}{\displaystyle \underset{j}{}}\left(p({\displaystyle \frac{j}{M}})q({\displaystyle \frac{j}{M}})\right)\right)`$ (6.30)
$`{\displaystyle \frac{1}{2}}{\displaystyle \frac{1}{M}}{\displaystyle \underset{j}{}}(z^2({\displaystyle \frac{j}{M}})^2+2zy{\displaystyle \frac{j}{M}}+y^2)+O(|z|^3+|y|^3)`$
$`=1+ia_nz+i(b_n+s/n)y{\displaystyle \frac{1}{2}}{\displaystyle \frac{1}{M}}{\displaystyle \underset{j}{}}(z^2({\displaystyle \frac{j}{M}})^2+2zy{\displaystyle \frac{j}{M}}+y^2)+O(|z|^3+|y|^3),`$
where, by the definitions $`p(u)=P(\zeta u+\eta )`$ and $`q(u)=1P(\zeta u+\eta )`$, and equations (3.8) and (4.2),

$`a_n={\displaystyle \frac{1}{M}}{\displaystyle \underset{j}{}}{\displaystyle \frac{j}{M}}\left(p({\displaystyle \frac{j}{M}})q({\displaystyle \frac{j}{M}})\right)=`$ $`{\displaystyle _0^1}u(p(u)q(u))𝑑u+O(M^1)=O(M^1)`$ (6.31)
$`b_n={\displaystyle \frac{1}{M}}{\displaystyle \underset{j}{}}\left(p({\displaystyle \frac{j}{M}})q({\displaystyle \frac{j}{M}})\right){\displaystyle \frac{s}{n}}=`$ $`{\displaystyle _0^1}(p(u)q(u))𝑑ub+O(M^1)=O(M^1).`$ (6.32)
Exponentiating the expansion for $`f`$, we arrive at

$`f(x,y)=`$ $`\mathrm{exp}\left(iza_n+iy\left({\displaystyle \frac{s}{n}}+b_n\right)\right)`$ (6.33)
$`\times \mathrm{exp}\left({\displaystyle \frac{1}{2}}(z,y)𝒬(z,y)^{}+O(|z|^3+|y|^3)\right),`$
where

$`𝒬_{11}=`$ $`𝔼[(X/M)^2]+O(M^2)𝔼[(X/M)^2],`$ (6.34)
$`𝒬_{12}=`$ $`𝔼(X/M)+O(bM^1)𝔼(X/M),`$
$`𝒬_{22}=`$ $`1(b+O(M^1))^21b^2.`$
Note that the matrix $`𝒬`$ is positive definite in the limit since

$$𝔼[(X/M)^2](1b^2)𝔼^2(X/M)\frac{1}{3}(1b^2)\frac{1}{4}=\frac{14b^2}{12}>0,$$
(6.35)
since $`b<1/2`$. By (6.33) and (6.34)

$$e^{i\mathrm{}xisy}f^n(x,y)=\mathrm{exp}(iz(\stackrel{~}{a}_n+iyb_n\frac{n}{2}(z,y)𝒬(z,y)^{}+O(n(|z|^3+|y|^3))),$$
(6.36)
where $`\stackrel{~}{a}_n=na_n\mathrm{}/M`$ and $`\stackrel{~}{b}_n=nb_n`$.

Let us derive an asymptotic formula for $`𝔼(𝒵_n(\mathrm{},s))`$, using (6.11), (6.28), and (6.33)-(6.36). By (6.9) and (6.11), the contribution of the $`(x,y)`$ with $`|x|>B/M`$ to $`𝔼(𝒵_n(\mathrm{},s))`$ is of order $`O((c/B)^n)`$. Let $`|x|B/M`$. Switch to $`z=Mx,y=y`$. By (6.28), the contribution of the $`(z,y)`$’s with $`(z,y)r_n:=n^{1/2}\mathrm{log}n`$ is of order

$$M^1\underset{rr_n}{}re^{nc_0^{}r^2/B}𝑑r=M^1e^{\mathrm{\Theta }(B^1\mathrm{log}^2n)}.$$
(6.37)
By (6.33)-(6.36), the contribution of the $`(z,y)`$’s with $`(z,y)r_n`$ is asymptotic to

$$\begin{array}{c}\frac{1}{2M\pi ^2}\underset{(z,y)r_n}{}\mathrm{exp}\left(iz\stackrel{~}{a}_n+iy\stackrel{~}{b}_n\frac{n}{2}(z,y)𝒬(y,z)^{}\right)\left(1+O(n|z|^3+n|y|^3)\right)𝑑z𝑑y\hfill \\ \hfill =\frac{1}{2M\pi ^2}\underset{(z,y)r_n}{}\mathrm{exp}\left(iz\stackrel{~}{a}_n+iy\stackrel{~}{b}_n\frac{n}{2}(z,y)𝒬(z,y)^{}\right)𝑑z𝑑y+O\left(\frac{1}{Mn}n^{1/2}\right).\end{array}$$
(6.38)
The first term on the r.h.s. of (6.38) is equal to

$$\frac{1}{Mn\pi \sqrt{\text{det }𝒬}}\left[\mathrm{exp}\left(\frac{1}{2n}(\stackrel{~}{a}_n,b_n)𝒬^{1/2}^2\right)+O\left(\underset{t\mathrm{\Theta }(\mathrm{log}n)}{}te^{t^2/2}𝑑t\right)\right],$$
(6.39)
where the exponential term is

$$1+O(n^1(\stackrel{~}{a}_n^2+b_n^2))=1+O(n/M^2)+O(n^1(\mathrm{}/M)^2=1+O(e^{\mathrm{\Theta }(n)})+O(n^1(\mathrm{}/M)^2),$$
(6.40)
while the integral is of order $`e^{\mathrm{\Theta }(\mathrm{log}^2n)}`$. Combining the last formula with the estimates of contributions of other ranges of $`(x,y)`$, we obtain

$`𝔼(𝒵_n(\mathrm{},s))`$ $`=(1+O(n^{1/2})+O((\mathrm{}/M)^2n^1)){\displaystyle \frac{1}{Mn}}{\displaystyle \frac{1}{\pi \sqrt{(1b^2)𝔼(U^2)𝔼^2(U)}}}`$ (6.41)
$`=(1+o(1)){\displaystyle \frac{2\sqrt{3}}{\pi \sqrt{1b^2}}}{\displaystyle \frac{1}{Mn}},`$
whenever $`|\mathrm{}|\mathrm{}_n=o(n^{1/2}M)`$. Summing over $`\mathrm{}\{(\mathrm{}_n1),\mathrm{},\mathrm{}_n1\}`$, the bound (6.41) clearly implies a similar bound for $`𝒵_n(s)`$, namely

$$𝔼(𝒵_n(s))=(1+o(1))\frac{2\sqrt{3}}{\pi \sqrt{1b^2}}\frac{2\mathrm{}_n1}{Mn}.$$
(6.42)
By the bounds (6.41) and (6.42) and Markov’s inequality, we have that $`Z_n(\mathrm{},s)M^1e^{\mathrm{log}^2n}`$ and $`𝒵_n(s)\mathrm{}_nM^1e^{\mathrm{log}^2n}`$ with probability $`1O(e^{\mathrm{log}^2n})`$. Combined with (6.5) and (6.8) this implies (6.1) and (6.2). $`\mathrm{}`$

### 6.2 A Digression: The Expected Number of Perfect Partitions

The reader may have noticed how gingerly we have tiptoed around the first factor in (5.1), concentrating instead on the asymptotic behavior of the double integral. To see why, we will show that $`𝔼(Z_n(\mathrm{},s))`$ remains exponentially large above the curve $`\kappa =\kappa _c(b)`$, in sharp contrast to the fact that, in this domain, w.h.p. there are no perfect partitions at all.

###### Theorem 6.2

Let $`|\mathrm{}|1`$. For $`s>0`$, $`s+n0(\text{mod }2)`$, and $`b=s/n`$ bounded away from $`0`$ and $`1`$,

$$𝔼[Z_n(\mathrm{},s)]\frac{2}{M}\left(\genfrac{}{}{0pt}{}{n}{\frac{n+s}{2}}\right)\frac{e^{\lambda s}\varphi ^n(\lambda )}{\sqrt{2\pi n\text{Var}(U_\lambda )}},\varphi (\lambda ):=\frac{\mathrm{sinh}\lambda }{\lambda }.$$
(6.43)
where $`U_\lambda [1,1]`$ has density

$$\frac{e^{\lambda x}/2}{_{y[1,1]}e^{\lambda y}/2𝑑y},$$
(6.44)
and $`\lambda <0`$ is such that $`𝔼(U_\lambda )=b`$, or explicitly:

$$\mathrm{coth}\lambda \frac{1}{\lambda }=b.$$
(6.45)
Consequently,

$$\underset{n\mathrm{}}{lim}\frac{1}{n}\mathrm{log}𝔼[Z_n(\mathrm{},s)]=R(\kappa ,b),$$
(6.46)
where

$$R(\kappa ,b)=\frac{1+b}{2}\mathrm{log}\frac{2}{1+b}+\frac{1b}{2}\mathrm{log}\frac{2}{1b}+\lambda b+\mathrm{log}\frac{\mathrm{sinh}\lambda }{\lambda }\kappa \mathrm{log}2.$$
(6.47)
Proof of Theorem 6.2. In order to calculate the expectation of $`Z_n(\mathrm{},s)`$, we use the following analogue of (3.6), which is valid whether or not $`\mathrm{}`$ has the same parity as $`_jX_j`$:

$$Z_n(\mathrm{},s)=\frac{2^n}{2\pi ^2}\underset{\genfrac{}{}{0pt}{}{x(\pi ,\pi ]}{y(\pi /2,\pi /2]}}{}e^{i(\mathrm{}x+sy)}\underset{j=1}{\overset{n}{}}\mathrm{cos}\left(xX_j+y\right)dxdy.$$
(6.48)
This gives

$$𝔼(Z_n(\mathrm{},s))=\frac{2^n}{2\pi ^2}\underset{\genfrac{}{}{0pt}{}{x(\pi ,\pi ]}{y(\pi /2,\pi /2]}}{}e^{i(\mathrm{}x+sy)}𝔼^n\left(\mathrm{cos}(xX+y)\right)𝑑x𝑑y,$$
(6.49)
where

$`𝔼\left(\mathrm{cos}(xX+y)\right)=`$ $`\text{Re }\left[e^{iy}M^1{\displaystyle \underset{j=1}{\overset{M}{}}}e^{ixj}\right]=\text{Re }\left[M^1e^{i(x+y)}{\displaystyle \frac{e^{ixM}1}{e^{ix}1}}\right]`$ (6.50)
$`=`$ $`{\displaystyle \frac{\mathrm{sin}\left(\frac{Mx}{2}\right)}{M\mathrm{sin}\left(\frac{x}{2}\right)}}\mathrm{cos}\left({\displaystyle \frac{(M+1)x}{2}}+y\right).`$
Notice that the first factor is a function of $`x`$ only, and the argument of the cosine is $`y`$ shifted by $`x(M+1)/2`$. Integrating first with respect to $`y`$, we can choose $`y(\pi /2+x(M+1)/2,\pi /2+x(M+1)/2]`$, thus reducing the $`y`$-integral to

$$e^{isx\frac{M+1}{2}}\frac{1}{\pi }\underset{y(\pi /2,\pi /2]}{}e^{isy}\mathrm{cos}^nydy.$$
(6.51)
Here we can write $`\mathrm{cos}y=𝔼(e^{iy\sigma })`$, $`(\sigma =\pm 1)=1/2`$. So, introducing the independent copies $`\sigma _1,\mathrm{},\sigma _n`$ of $`\sigma `$, we write the last integral as

$$\left(\underset{j=1}{\overset{n}{}}\sigma _j=s\right)=\frac{1}{2^n}\left(\genfrac{}{}{0pt}{}{n}{\frac{n+s}{2}}\right).$$
(6.52)
Therefore we get the simpler expression

$`𝔼(Z_n(\mathrm{},s))=`$ $`\left({\displaystyle \genfrac{}{}{0pt}{}{n}{\frac{n+s}{2}}}\right){\displaystyle \frac{1}{2\pi }}{\displaystyle \underset{x(\pi ,\pi ]}{}}e^{ixt}\left({\displaystyle \frac{\mathrm{sin}\frac{Mx}{2}}{M\mathrm{sin}\frac{x}{2}}}\right)^n𝑑x;`$ (6.53)
$`t:=`$ $`\mathrm{}+s{\displaystyle \frac{M+1}{2}}.`$ (6.54)
To simplify the rest of the exposition, let us assume that $`\mathrm{sin}x/2`$ in denominator can be replaced asymptotically by $`x/2`$. (A refined version of the argument shows that this replacement is asymptotically correct for $`n=o(M)`$. We leave it to the interested reader to check this.) Substituting $`z=Mx/2`$, we get then

$`𝔼(Z_n(\mathrm{},s))`$ $`\left({\displaystyle \genfrac{}{}{0pt}{}{n}{\frac{n+s}{2}}}\right){\displaystyle \frac{1}{\pi M}}{\displaystyle \underset{z(M\pi /2,M\pi /2]}{}}e^{i\tau z}\left({\displaystyle \frac{\mathrm{sin}z}{z}}\right)^n𝑑z,`$ (6.55)
$`\tau :=`$ $`s(1+M^1)2\mathrm{}/M,`$
so that $`\tau `$ is very close to $`s`$, since $`|\mathrm{}|1`$. Next, we observe that $`y^1\mathrm{sin}y`$ is the characteristic function of the random variable $`U`$, uniformly distributed on $`[1,1]`$. Hence $`\left(\frac{\mathrm{sin}z}{z}\right)^n`$ is the characteristic function of $`S_n=_{j=1}^nU_j`$, where $`U_j`$ are the independent copies of $`U`$. In particular, using the Fourier inversion formula for $`f_{S_n}`$, the density of $`S_n`$,

$$f_{S_n}(\tau )=\frac{1}{2\pi }\underset{z(\mathrm{},\mathrm{})}{}e^{i\tau z}\left(\frac{\mathrm{sin}z}{z}\right)^n𝑑z,$$
(6.56)
we get from (6.55):

$$𝔼(Z_n(\mathrm{},s))\frac{2}{M}\left(\genfrac{}{}{0pt}{}{n}{\frac{n+s}{2}}\right)f_{S_n}(\tau ).$$
(6.57)
(The error caused by extending the integration interval in (6.55) to $`(\mathrm{},\mathrm{})`$ is extremely small, of order $`M^n=2^{\kappa n^2}`$.) We cannot use the local limit theorem for $`f_{S_n}(\tau )`$ directly as $`𝔼S_n=n𝔼U\tau `$. So we introduce an auxiliary random variable $`U_\lambda `$ with density proportional to $`e^{\lambda x}`$ on $`[1,1]`$, choosing $`\lambda `$ such that $`𝔼(U_\lambda )=\tau /n`$, that is setting $`\lambda `$ equal the root of

$$\frac{\varphi ^{}(\lambda )}{\varphi (\lambda )}=\frac{\tau }{n},\varphi (\lambda ):=\frac{1}{2}\underset{x[1,1]}{}e^{\lambda x}𝑑x=\frac{\mathrm{sinh}\lambda }{\lambda }.$$
(6.58)
Then

$$f_{S_n}(\tau )=e^{\lambda (\tau )}\varphi ^n(\lambda )f_{S_{n,\lambda }}(\tau ),$$
(6.59)
where $`S_{n,\lambda }=_{j=1}^nU_{j,\lambda }`$. By the local limit theorem (see, e.g., , Sect. 5.10), the density $`f_{S_{n,\lambda }}(\tau )`$ of $`S_{n,\lambda }`$ is asymptotic to

$$\frac{1}{\sqrt{2\pi n\text{Var}U_\lambda }},$$
(6.60)
where $`\text{Var}(U_\lambda )`$ can be explicitly calculated, giving

$$\text{Var}(U_\lambda )=\frac{\varphi ^{\prime \prime }(\lambda )}{\varphi (\lambda )}(\tau /n)^2.$$
(6.61)
Thus

$$𝔼(Z_n(\mathrm{},s))\frac{2}{M}\left(\genfrac{}{}{0pt}{}{n}{\frac{n+s}{2}}\right)e^{\lambda \tau }\varphi ^n(\lambda )f_{S_{n,\lambda }}(\tau )\frac{2}{M}\left(\genfrac{}{}{0pt}{}{n}{\frac{n+s}{2}}\right)\frac{e^{\lambda s}\varphi ^n(\lambda )}{\sqrt{2\pi n\text{Var}(U_\lambda )}},$$
(6.62)
as claimed. $`\mathrm{}`$

### 6.3 Optimal Imperfect Partitions

In Theorem 6.1 we proved that, for $`\kappa >\kappa _c(b)`$ and $`b<b_c`$, w.h.p. the minimum discrepancy is at least $`2^{n(\kappa \kappa _c(b))O_p(n^{1/2})}`$. The next theorem provides a complementary upper bound for the minimum discrepancy.

###### Theorem 6.3

Suppose that $`lim\; sup|s|/n<b`$ and that $`0<lim\; inf\kappa lim\; sup\kappa <\mathrm{}`$. Let $`\epsilon >0`$, let $`S_n`$ be the random variable defined in (5.8), and let $`\mathrm{}_n`$ be a sequence of positive integers with $`\mathrm{}_n=o(Mn^{1/2}/\mathrm{log}n)`$ and $`\mathrm{}_n2^{[\kappa \kappa _{}(b)+\epsilon ]n}`$. Then there is a constant $`\delta >0`$ such that, with probability $`1O(e^{\delta \mathrm{log}^2n})`$,

$$\underset{\mathrm{}:|\mathrm{}|<\mathrm{}_n}{}Z_n(\mathrm{},s)=\mathrm{}_{n,𝕏}2^{[\kappa _c(b)\kappa ]n}e^{n^{1/2}S_n+o(n^{1/2})},$$
(6.63)
where $`\mathrm{}_{n,𝕏}`$ is the number of integers $`\mathrm{}`$ with $`|\mathrm{}|<\mathrm{}_n`$ with the same parity as $`_jX_j`$. With probability $`1O(e^{\delta \mathrm{log}^2n})`$, we thus have

$$d_{opt}2^{(\kappa \kappa _{}(b)+\epsilon )n},$$
(6.64)
implying in particular that $`M^1d_{opt}`$ is exponentially small in $`n`$.

Note that for $`lim\; sup(\kappa \kappa _{}(b))<0`$, we recover that $`d_{opt}1`$. Not astonishingly, the proof of Theorem 6.3 follows closely the proof of Theorem 5.1, which established that, w.h.p., there are exponentially many perfect partitions for $`lim\; sup(\kappa \kappa _{}(b))<0`$.

Proof of Theorem 6.3. Let us first note that depending on the parity of $`_jX_j`$, the number $`\mathrm{}_{n,𝕏}`$ is either $`\mathrm{}_n`$ or $`\mathrm{}_n1`$, implying in particular that $`\mathrm{}_{n,𝕏}\mathrm{}_n1`$. Using this fact, it is not hard to see that the bound (6.64) follows from (6.63). Indeed, let $`\mathrm{}_n=2^{(\kappa \kappa _{}+\epsilon )n}+1`$. Since $`\mathrm{}_{n𝕏}\mathrm{}_n12^{(\kappa \kappa _{}+\epsilon )n}`$, the right hand side of (6.63) goes to infinity, implying that $`d_{opt}\mathrm{}_n1`$. It is therefore enough to prove (6.63). Also, since both sides of (6.63) are identically zero if $`\mathrm{}_{n,𝕏}=0`$, it is enough to consider $`\mathrm{}_{n,𝕏}>0`$.

Analogously to the proof of Theorem 6.1, we set

$$𝒵_n(s)=\underset{\mathrm{}:|\mathrm{}|<\mathrm{}_n}{}𝒵_n(\mathrm{},s),$$
(6.65)
where $`𝒵_n(\mathrm{},s)`$ is the random integral defined in (6.6). Let us note, however, that $`𝒵_n(\mathrm{},s)`$ is equal to the random integral defined in (5.2) if $`\mathrm{}`$ is of the same parity as $`_jX_j`$, and equal to zero otherwise. The sum in (6.65) can therefore be replaced by the sum over all $`\mathrm{}`$ with the same parity as $`_jX_j`$, and

$$𝒵_n(s)=\frac{1}{\pi ^2}\underset{\genfrac{}{}{0pt}{}{x(\pi /2,\pi /2]}{y(\pi /2,\pi /2]}}{}\left[\underset{\mathrm{}:|\mathrm{}|<\mathrm{}_n}{}^{}e^{i\mathrm{}x}\right]e^{isy}f(x,y;𝕏)𝑑x𝑑y,$$
(6.66)
where the sum $`^{}`$ indicates the sum over all $`\mathrm{}`$ with the same parity as $`_jX_j`$. Obviously, we have

$$\left|\underset{\mathrm{}:|\mathrm{}|<\mathrm{}_n}{}^{}e^{i\mathrm{}x}\right|\mathrm{}_{n,𝕏}$$
(6.67)
and

$$\underset{\mathrm{}:|\mathrm{}|<\mathrm{}_n}{}^{}e^{i\mathrm{}x}=\mathrm{}_{n,𝕏}\left(1+O\left((\mathrm{}_n|x|)^2\right)\right)\text{as}\mathrm{}_n|x|0.$$
(6.68)
Recalling that, depending on the parity of $`_jX_j`$, the number $`\mathrm{}_{n,𝕏}`$ of terms in the sum $`^{}`$ is either $`\mathrm{}_n`$ or $`\mathrm{}_n1`$, we also have

$$\left|\underset{\mathrm{}:|\mathrm{}|<\mathrm{}_n}{}^{}e^{i\mathrm{}x}\right|=\left|\underset{k=0}{\overset{\mathrm{}_{n,𝕏}1}{}}e^{i2kx}\right|1+\left|\frac{\mathrm{sin}((\mathrm{}_n1)x)}{\mathrm{sin}x}\right|\mathrm{}_n.$$
(6.69)
As in the proof of Theorem 5.1, we split the right hand side of (6.66) into two parts, $`J_{n1}(𝕏)`$ and $`J_{n2}(𝕏)`$, for $`|x|B/M`$ and $`|x|>B/M`$ respectively. We start with $`J_{n1}(𝕏)`$. As in (5.20), we restrict ourselves to the event $`A_n`$ defined in (5.18). With the help of (6.67), we then bound the contributions of all $`x`$ with $`(Mx,y)r_n=n^{1/2}\mathrm{log}n`$ by

$`{\displaystyle \frac{\mathrm{}_{n,𝕏}}{\pi ^2}}{\displaystyle \underset{\genfrac{}{}{0pt}{}{(Mx,y)r_n}{|Mx|B}}{}}|f(x,y;𝕏)|𝑑x𝑑y`$ $`{\displaystyle \frac{\mathrm{}_{n,𝕏}}{Mn}}{\displaystyle \underset{𝕫\mathrm{log}n}{}}e^{c_4𝕫^2}𝑑z_1𝑑z_2=O\left({\displaystyle \frac{\mathrm{}_{n,𝕏}}{Mn}}e^{c_4(\mathrm{log}^2n)}\right).`$ (6.70)
For $`(Mx,y)r_n`$, we may use (6.68) since $`\mathrm{}_n|x|M^1\mathrm{}_nr_n=o(r_nn^{1/2}\mathrm{log}^1n)0`$. And, analogously to (5.32), we have that with probability at least $`1O(e^{\delta _3\mathrm{log}^2n})`$

$$\begin{array}{c}\frac{1}{\pi ^2}\underset{(Mx,y)r_n}{}\left[\underset{\mathrm{}:|\mathrm{}|<\mathrm{}_n}{}^{}e^{i\mathrm{}x}\right]e^{isy}f(x,y;𝕏)𝑑x𝑑y\hfill \\ \hfill =\frac{\mathrm{}_{n,𝕏}}{Mn}\left[\frac{1}{\pi \sqrt{\text{det }R}}\mathrm{exp}\left(\frac{1}{4}𝝉_nR^1𝝉_n^{}\right)+o(1)\right].\end{array}$$
(6.71)
Comparing (6.70) and (6.71) (and using again the bound (5.28), this time to get a lower bound on the right hand side of (6.71)), we see that the last expression is a sharp asymptotic formula for $`J_{n1}(𝕏)`$.

Next, we use (6.69) to bound

$$𝔼(|J_{n2}(𝕏)|^2)\frac{1}{\pi ^4}\underset{\genfrac{}{}{0pt}{}{|x_1|,|x_2|[B/M,\pi /2]}{y_1,y_2(\pi /2,\pi /2]}}{}(1+S(x_1))(1+S(x_2))|F(𝕩,𝕪)|^n𝑑𝕩𝑑𝕪,$$
(6.72)
where $`F(𝕩,𝕪)`$ is defined in (5.39) and

$$S(x)=\frac{|\mathrm{sin}((\mathrm{}_n1)x)|}{|\mathrm{sin}(x)|}.$$
(6.73)
Arguing as in the case of $`I_{n2}(𝕏)`$, we thus obtain that $`𝔼(|J_{n2}(𝕏)|^2)`$ is of order

$$\begin{array}{c}(c/B)^n\left(1+\underset{x(\pi /2,\pi /2]}{}\frac{|\mathrm{sin}((\mathrm{}_n1)x)|}{|\mathrm{sin}(x)|}𝑑x\right)^2\hfill \\ \hfill +(\rho +c/B)^n\underset{\genfrac{}{}{0pt}{}{x_1,x_2(\pi /2,\pi /2]}{|x_1+x_2|B/M}}{}\left(1+\frac{|\mathrm{sin}((\mathrm{}_n1)x_1)|}{|\mathrm{sin}(x_1)|}\right)\left(1+\frac{|\mathrm{sin}((\mathrm{}_n1)x_2)|}{|\mathrm{sin}(x_2)|}\right)𝑑x_1𝑑x_2,\end{array}$$
(6.74)
with, as before, $`\rho =2^\kappa _{}`$. Here the single integral is of order

$$\underset{x(\pi /2,\pi /2]}{}\frac{|\mathrm{sin}((\mathrm{}_n1)x)|}{|x|}𝑑x=\underset{|t|\pi (\mathrm{}_n1)/2}{}\frac{|\mathrm{sin}t|}{|t|}𝑑t=O(\mathrm{log}\mathrm{}_n)=O(n),$$
(6.75)
and the double integral is of order

$$\frac{B}{M}\underset{x(\pi /2,\pi /2]}{}\mathrm{}_n\left(1+\frac{|\mathrm{sin}((\mathrm{}_n1)x)|}{|\mathrm{sin}(x)|}\right)𝑑x=O(M^1\mathrm{}_n\mathrm{log}\mathrm{}_n)=O(n\mathrm{}_nM^1).$$
(6.76)
Combining the contributions from (6.75) and (6.76), we get that for $`B`$ sufficiently large

$`𝔼(|J_{n2}(𝕏)|^2)`$ $`=O\left(n^2(c/B)^n\right)+O\left(n\mathrm{}_nM^1(\rho +c/B)^n\right)`$ (6.77)
$`=O\left({\displaystyle \frac{\mathrm{}_n}{Mn^2}}\rho ^ne^{(\epsilon /2)n}\right)=O\left(\left({\displaystyle \frac{\mathrm{}_n}{Mn}}\right)^2e^{(\epsilon /2)n}\right).`$
Here, in the second step we used that $`\rho `$ is bounded away from $`0`$ and $`1`$, and that $`B`$ is large enough, while in the third step, we used that $`\mathrm{}_n/M`$ is assumed to be at least $`\rho ^ne^{\epsilon n}`$. By Markov’s inequality (and the fact that $`\mathrm{}_n\mathrm{}_{n,𝕏}+12\mathrm{}_{n,𝕏}`$ whenever $`\mathrm{}_{n,𝕏}0`$), we conclude that with probability $`1O(e^{(\epsilon /4)n})`$,

$$|J_{n2}(𝕏)|\frac{\mathrm{}_n}{Mn}e^{(\epsilon /8)n}\frac{2\mathrm{}_{n,𝕏}}{Mn}e^{(\epsilon /8)n}.$$
(6.78)
By (6.70), (6.71) and (5.28), $`J_{n1}(𝕏)`$ is of order at least $`\frac{\mathrm{}_{n,𝕏}}{Mn}e^{\mathrm{log}^2n}`$ with probability $`e^{\delta _4\mathrm{log}^2n}`$ for some $`\delta _4>0`$, much larger than the above order of $`|J_{n2}(𝕏)|`$. We thus have shown that there is a constant $`\delta =\delta (\epsilon )>0`$ such that with probability at least $`1O(e^{\delta \mathrm{log}^2n})`$,

$$𝒵_n(s)=(1+o(1))\frac{\mathrm{}_{n,𝕏}}{Mn}\frac{1}{\pi \sqrt{\text{det}R}}\mathrm{exp}\left(𝝉_n(4R)^1𝝉_n^{}\right).$$
(6.79)
Together with (6.8), this implies the bound (6.63). $`\mathrm{}`$

The following corollary follows immediately from Remark 6.1 (i) and Theorem 6.3.

###### Corollary 6.1

Assume that $`lim\; sup|s|/n<b`$, $`lim\; sup\kappa <\mathrm{}`$ and $`lim\; inf[\kappa \kappa _c(b)]>0`$, and let $`\epsilon >0`$. Then there exists a constant $`\delta >0`$ such that with probability $`1O(e^{\delta \mathrm{log}^2n})`$,

$$2^{[\kappa \kappa _c(b)n^{1/2}\mathrm{log}n]n}d_{opt}2^{[\kappa \kappa _{}(b)+\epsilon ]n}.$$
(6.80)
As argued in Remark 6.1(iii), we expect that for $`lim\; inf\kappa >\kappa _c`$, the number of optimal partitions $`Z_{opt}`$ grows subexponentially. But so far, we only can prove the following corollary to Theorem 6.3.

###### Corollary 6.2

Suppose that $`lim\; sup|s|/n<b`$ and that $`0<lim\; inf\kappa lim\; sup\kappa <\mathrm{}`$. Then for every $`\epsilon >0`$, there exists a constant $`\delta >0`$ such that

$$Z_{opt}2^{(\kappa _c+\epsilon )n}\mathrm{max}\{2^{\kappa n},2^{\kappa _{}n}\}$$
(6.81)
with probability $`1O(e^{\delta \mathrm{log}^2n})`$.

Proof. Let $`\mathrm{}_n=2^{[\kappa \kappa _{}(b)+\epsilon /2]n}+1`$. By the bound (6.64) of Theorem 6.3, we have that there exists some $`\delta >0`$ such that $`d_{opt}\mathrm{}_n1`$ with probability $`1O(e^{\delta \mathrm{log}^2n})`$. Using the bound (6.63), we therefore get

$$Z_{opt}\mathrm{}_n2^{[\kappa _c(b)\kappa ]n}e^{n^{1/2}S_n+o(n^{1/2})}\mathrm{}_n2^{[\kappa _c(b)\kappa ]n}e^{O(n^{1/2}\mathrm{log}n)},$$
(6.82)
again with probability $`1o(e^{\delta \mathrm{log}^2n})`$. Bounding $`\mathrm{}_n3\mathrm{max}\{1,2^{[\kappa \kappa _{}(b)+\epsilon /2]n}\}`$, we obtain the bound (6.81). $`\mathrm{}`$

## 7 The Sorted Phase

It remains to study the minimum discrepancy for $`b>b_c`$.

### 7.1 Characteristics of the Sorted Phase

###### Theorem 7.1

Suppose that $`Mn^2`$ and $`lim\; infs/n>b_c`$. Then w.h.p. the optimal partition $`𝛔^{}`$ is the sorted partition obtained as follows. Order $`X_j`$ in the increasing order, so that $`X_{\pi (1)}\mathrm{}X_{\pi (n)}`$ for some permutation $`\pi `$ of $`\{1,\mathrm{},n\}`$. W.h.p. there will be no ties, and the ordering $`\pi `$ will be uniquely defined. Denoting $`j_n=(n+s)/2=n(1+b)/2`$, $`b=s/n`$,

$$\sigma _j^{}=\{\begin{array}{cccc}& 1,\hfill & & 1jj_n,\hfill \\ & 1,\hfill & & j_n<jn,\hfill \end{array}$$
(7.1)
and w.h.p. the minimum discrepancy is asymptotic to $`\frac{Mn}{4}[(1+b)^22]`$, i.e. of order $`Mn`$.

Proof of Theorem 7.1. We begin with the following observation. If

$$\delta _s(𝑿)=\underset{j=1}{\overset{j_n}{}}X_{\pi (j)}\underset{j=j_n+1}{\overset{n}{}}X_{\pi (j)}0,$$
(7.2)
then the sorted partition is optimal, and $`d_{opt}=\delta _s(𝕏)`$. Indeed, let $`𝝈`$ be any feasible partition $`𝝈`$. Then $`s(𝝈)=|\{j:\sigma _j=1\}||\{j:\sigma _j=1\}|=2|\{j:\sigma _j=1\}|n`$ so that $`|\{j:\sigma _j=1\}|=j_n`$. Thus

$`𝝈𝕏=`$ $`{\displaystyle \underset{\{j:\sigma _j=1\}}{}}X_j{\displaystyle \underset{\{j:\sigma _j=1\}}{}}X_j`$ (7.3)
$``$ $`{\displaystyle \underset{j=1}{\overset{j_n}{}}}X_{\pi (j)}{\displaystyle \underset{j=j_n+1}{\overset{n}{}}}X_{\pi (j)}0,`$ (7.4)
which implies optimality of the partition $`𝝈^{}`$ and $`d_{opt}=\delta _s(𝕏)`$.

In light of this property, all we need to do is to show that, for $`b>b_c`$ and bounded away from $`b_c`$, w.h.p.

$$\delta _s(𝕏)=\frac{Mn}{4}\left[(1+b)^22\right](1+o(1))0.$$
(7.5)
Let $`U`$ be $`[0,1]`$-uniform, and $`U_1,\mathrm{},U_n`$ be the independent copies of $`U`$. Then the sequence $`\{X_j^{}\}:=\{MU_j\}`$ has the same distribution as our sequence $`\{X_j:1jn\}`$. So we will consider $`\{X_j^{}\}`$ instead. Since $`Mn^2`$, it follows easily that w.h.p. $`X_{\pi (1)}^{}<\mathrm{}<X_{\pi (n)}^{}`$ if and only if $`U_{\pi (1)}<\mathrm{}<U_{\pi (n)}`$. Furthermore

$$0MU_jMU_j1,$$
(7.6)
so it suffices to show that w.h.p.

$$\underset{j=1}{\overset{j_n}{}}U_{\pi (j)}\underset{j=j_n+1}{\overset{n}{}}U_{\pi (j)}=\frac{n}{4}\left[(1+b)^22\right](1+o(1)).$$
(7.7)
A second simplification is based on a fact that the sequence $`\{U_{\pi (j)}\}_{1jn}`$ has the same distribution as $`\{\frac{S_j}{S_{n+1}}\}_{1jn}`$, where $`S_j=_{k=1}^jZ_k`$, and $`Z_1,\mathrm{},Z_n`$ are independent copies of $`Z`$, the Exponential $`(\lambda )`$, $`\lambda >0`$ being arbitrary. Choose $`\lambda =1`$ for certainty. Since $`S_{n+1}`$ is w.h.p. asymptotic to $`(n+1)𝔼Z=n+1`$, it suffices to show that w.h.p.

$$\underset{j=1}{\overset{j_n}{}}S_j\underset{j=j_n+1}{\overset{n}{}}S_j=\frac{n^2}{4}\left[(1+b)^22\right](1+o(1)),$$
(7.8)
or, in terms of $`Z_t`$’s, that w.h.p.

$$\mathrm{\Sigma }_1\mathrm{\Sigma }_2=\frac{n^2}{4}\left[(1+b)^22\right](1+o(1)),$$
(7.9)
where

$`\mathrm{\Sigma }_1=`$ $`{\displaystyle \underset{k=1}{\overset{j_n}{}}}(j_nk+1)Z_k,`$ (7.10)
$`\mathrm{\Sigma }_2=`$ $`(nj_n){\displaystyle \underset{k=1}{\overset{jn}{}}}Z_k+{\displaystyle \underset{k=j_n+1}{\overset{n}{}}}(nk+1)Z_k.`$
Finally, introduce $`\{Z_k^{}\}`$, the truncated version of $`\{Z_k\}`$, namely

$$Z_k^{}=\mathrm{min}(Z_k,2\mathrm{log}n),1kn.$$
(7.11)
Noticing that

$`(kn:Z_k^{}Z_k)`$ $`n(Z_1^{}Z_1)`$ (7.12)
$`=`$ $`n(Z_1>2\mathrm{log}n)=n^10,`$ (7.13)
we can and will replace $`Z_k`$ by $`Z_k^{}`$ in (7.10), denoting the corresponding sums by $`\mathrm{\Sigma }_i^{}`$. Observe that

$$𝔼(Z_k^{})=𝔼(Z_k)\underset{2\mathrm{log}n}{\overset{\mathrm{}}{}}(y2\mathrm{log}n)e^y𝑑y=1n^2,$$
(7.14)
so that

$$𝔼(\mathrm{\Sigma }_i^{})=𝔼(\mathrm{\Sigma }_i)+O(1),i=1,2.$$
(7.15)
By the Azuma-Hoeffding inequality (see, e.g., , Section 12.2) and $`Z_k^{}2\mathrm{log}n`$, we have: for every $`\alpha >0`$,

$$(|\mathrm{\Sigma }_i^{}𝔼(\mathrm{\Sigma }_i^{})|>\alpha )2\mathrm{exp}\left(\frac{\alpha ^2}{2n(2n\mathrm{log}n)^2}\right)=2\mathrm{exp}\left(\frac{\alpha ^2}{8n^3\mathrm{log}^2n}\right).$$
(7.16)
Using this bound with $`\alpha =n^{7/4}`$, we obtain that w.h.p.

$$|\mathrm{\Sigma }_i^{}𝔼(\mathrm{\Sigma }_i^{})|n^{7/4}n^2,$$
(7.17)
implying that w.h.p.

$$\mathrm{\Sigma }_1\mathrm{\Sigma }_2=\mathrm{\Sigma }_1^{}\mathrm{\Sigma }_2^{}=𝔼(\mathrm{\Sigma }_1^{})𝔼(\mathrm{\Sigma }_2^{})+O(n^{7/4}).$$
(7.18)
It remains to observe that

$`𝔼(\mathrm{\Sigma }_1^{}\mathrm{\Sigma }_2^{})=`$ $`𝔼(\mathrm{\Sigma }_1)𝔼(\mathrm{\Sigma }_2)+O(1)`$ (7.19)
$`=`$ $`{\displaystyle \frac{j_n(j_n1)}{2}}(nj_n)j_n{\displaystyle \frac{(nj_n)(nj_n+1)}{2}}+O(1)`$
$`=`$ $`{\displaystyle \frac{2j_n^2n^2}{2}}+O(n)`$
$`=`$ $`{\displaystyle \frac{n^2}{4}}[(1+b)^22]+O(n),`$
which completes the proof. $`\mathrm{}`$

###### Remark 7.1

Consider a point $`(\kappa ,b)`$ such that $`b<b_c`$. From the above proof, it is easy to show that w.h.p. the sorted partition $`𝛔^{}`$ cannot be optimal. Indeed, by (7.19), we see that

$`𝔼(\mathrm{\Sigma }_1^{}\mathrm{\Sigma }_2^{})={\displaystyle \frac{n^2}{4}}\left[(1+b)^22\right]+O(n)\mathrm{\Theta }(n^2).`$ (7.20)
This means that w.h.p.

$$𝝈^{}𝕏\mathrm{\Theta }(Mn)|𝝈^{}𝕏|\mathrm{\Theta }(Mn),$$
(7.21)
and we know that $`d_{opt}=o(Mn)`$ for every $`(\kappa ,b)`$, with $`b<b_c`$.

### 7.2 The Dual Role of $`b_c`$.

In Theorem 4.1, we proved that $`b_c`$ is the threshold of the values of $`b`$ for solvability of the saddle point equations (3.18). Then, in Theorem 7.1, we proved that the same $`b_c`$ is also the threshold for optimality of the sorted partition. At this point, while the results are complete, the equality of these two thresholds seems to be nothing but a numerical coincidence. In this subsection, we give an explanation of this coincidence. It turns out that the coincidence reflects a deterministic property of the integer partitioning problem which holds for a broad set of $`𝐗`$, see Theorem 7.2 below.

We caution the reader that Theorem 7.2 does not directly imply the two Theorems 4.1 and 7.1. Theorem 7.2 holds only for a given instance $`𝐗`$, and states that for $`s/n`$ greater than some $`b_c(𝐗)`$, the sorted partition is optimal, while for $`s/n<b_c(𝐗)`$, the saddle point equations (3.13) have an unique solution. In order to apply this theorem to the random integer partitioning problem, we would have to address two issues. First, we would have to show that if $`b>b_c`$, then w.h.p., $`b>b_c(𝐗)`$. This follows in a relatively straightforward fashion using the techniques of the last subsection. The more difficult issue is to relate existence of solutions of the saddle point equations (3.13) to that of the averaged saddle point equations (3.18). This requires that we establish existence and commutation of the limits $`n\mathrm{}`$ and $`s/nb`$, and deal with the fact that $`nb_c`$ is generally not an integer so that, as $`bb_c`$, the solution to the saddle point equations gives a $`𝝈`$ with some $`\sigma _j`$ in the interval $`[1,+1]`$ rather than all $`\sigma _j\{1,+1\}`$, see below. Since the coincidence is already proved in Theorems 4.1 and 7.1, and since the purpose of this section is simply to elucidate the coincidence, we do not deal with these, admittedly difficult, issues here. We just present the result for a given $`𝐗`$.

Consider $`n`$ arbitrary numbers $`X_1,\mathrm{},X_n\{1,\mathrm{},M\}`$, subject to the constraints that no two of them are equal, and that their sum is even (the odd case is similar and is left to the reader). Without loss of generality, further assume that the $`X_i`$ are ordered in increasing order, so that $`X_1<X_2<\mathrm{}<X_n`$. Consider the equations (3.13) with $`\mathrm{}=0`$, and define $`s_c(𝕏)`$ as the supremum over all $`s`$ for which the equations (3.13) have a solution.

Let $`𝝈`$ be a fractional partition, i.e., let $`𝝈[1,1]^n`$. We say that $`𝝈`$ has bias $`s`$, if $`_{i=1}^n\sigma _i=s`$, and we say that it is sorted, if $`\sigma _i\sigma _{i+1}`$ for all $`i`$ and $`|\sigma _i|=1`$ for all but at most one $`i`$. Note that there is exactly one sorted partition with bias $`s`$ for any real $`s[n,n]`$. We finally introduce the critical sorted partition as the sorted (fractional) partition $`\stackrel{~}{𝝈}`$ that obeys the condition

$$\underset{j=1}{\overset{n}{}}\stackrel{~}{\sigma }_jX_j=0.$$
(7.22)
There is at most one such partition for a fixed set of weights $`X_1,\mathrm{},X_n`$. With slight abuse of notation, we say that a probability distribution $`(𝝈)`$ on partitions is concentrated on a fractional sorted partition $`\stackrel{~}{𝝈}`$ if $`(\sigma _i=\stackrel{~}{\sigma }_i)=1`$ whenever $`|\stackrel{~}{\sigma }_i|=1`$, and $`(\sigma _i=1)=p`$ when $`\stackrel{~}{\sigma }_i`$ takes the fractional value $`2p1`$.

The following theorem shows that the critical bias for the existence of a solution to the random saddle point equations and the critical bias for the optimality of the fractional sorted partition are identical. For brevity, we drop the term “fractional” throughout.

###### Theorem 7.2

Let $`X_1<X_2<\mathrm{}<X_n\{1,\mathrm{},M\}`$, and assume that the sum $`_{i=1}^nX_i`$ is even.

i) If $`\mathrm{}=0`$ and $`0<s<s_c(𝕏)`$, then the saddle point equations (3.13) have a unique solution $`(\xi ,\eta )`$ with $`\mathrm{}<\eta <0`$, $`0<\xi <\mathrm{}`$ and $`|\eta |/\xi <M`$.

ii) For $`\mathrm{}=0`$, $`s<s_c(𝕏)`$, and a solution $`(\xi ,\eta )`$ of the saddle point equations (3.13), let $`_s()`$ be the probability distribution on partitions defined in (3.7). If $`ss_c(𝕏)`$, then $`\xi \mathrm{}`$, $`\eta \mathrm{}`$, and the distribution $`_s()`$ gets concentrated on the critical sorted partition.

iii) If $`\mathrm{}=0`$ and $`ss_c(𝕏)`$, then the saddle point equations (3.13) have no solution, and the sorted partition with bias $`s`$ is optimal; if $`s>s_c(𝕏)`$, this partition has non-zero discrepancy, implying that there are no perfect partitions with bias $`s>s_c(𝕏)`$.

###### Remark 7.2

Statement ii) clearly implies that the critical sorted partition has bias $`s_c(𝕏)`$. As a consequence, a sorted partition with bias $`s>s_c(𝕏)`$ has non-zero discrepancy. By an easy extension of the argument given for non-fractional partitions, this in turn implies that sorted partitions with bias $`ss_c(𝕏)`$ are optimal. Except for the statement that the saddle point equations (3.13) have no solution for $`\mathrm{}=0`$ and $`s=s_c(𝕏)`$, statement iii) is therefore an immediate consequence of statement ii).

Proof of Theorem 7.2: i) Given $`X_1<X_2<\mathrm{}<X_n\{1,\mathrm{},M\}`$, let

$`F(\xi ,\eta )`$ $`={\displaystyle \underset{j=1}{\overset{n}{}}}X_j\mathrm{tanh}(\xi X_j+\eta ),`$ (7.23)
$`G(\xi ,\eta )`$ $`={\displaystyle \underset{j=1}{\overset{n}{}}}\mathrm{tanh}(\xi X_j+\eta ).`$
Since the partial derivatives $`F(\xi ,\eta )/\xi `$ and $`F(\xi ,\eta )/\eta `$ are strictly positive for all $`(\xi ,\eta )^2`$, the equation

$$F(\xi ,\eta (\xi ))=0$$
(7.24)
has a well defined, unique solution $`\eta (\xi )`$ for all $`\xi `$, and $`\eta (\xi )`$ is strictly decreasing on $``$. Let

$$g(\xi )=G(\xi ,\eta (\xi )).$$
(7.25)
Each solution $`(\xi ,\eta )`$ of the saddle point equations (3.13) is then a solution of $`g(\xi )=s`$ and $`\eta =\eta (\xi )`$, and vice versa. Using the fact that the derivatives of $`F`$ and $`G`$ are second order derivatives of the strictly convex function $`L_n(\xi ,\eta )`$, one easily shows that $`g()`$ is strictly decreasing. Combined with the fact that $`\eta (0)=0`$ so that $`g(0)=0`$, we easily complete that proof of i). Indeed, by the monotonicity of $`g`$, the equation $`g(\xi )=s`$ has a unique solution $`\xi (0,\mathrm{})`$ whenever

$$g(0)=0<s<s_c=\underset{\xi \mathrm{}}{lim}g(\xi ).$$
(7.26)
But $`\xi >0`$ implies $`\eta =\eta (\xi )<0`$, so we are just left with the proof of the inequality $`|\eta |<\xi M`$. To this end, we just observe that $`F(\xi ,\eta )=0`$, $`\xi >0`$ and the fact that not all $`X_j\{1,\mathrm{},M\}`$ are equal imply that

$$0=\underset{j=1}{\overset{n}{}}X_j\mathrm{tanh}(\xi X_j+\eta )<\mathrm{tanh}(\xi M+\eta )\underset{j=1}{\overset{n}{}}X_j,$$
(7.27)
which in turn gives $`\xi M+\eta >0`$, as desired.

ii) By the strict monotonicity of $`g`$, $`\xi \mathrm{}`$ as $`ss_c`$ (otherwise, the equation $`g(\xi )=s_c`$ would have a finite solution $`\xi <\mathrm{}`$, which contradicts the strict monotonicity of $`g`$ on $`(0,\mathrm{})`$). If $`\eta =\eta (\xi )`$ stayed bounded away from $`\mathrm{}`$ as $`\xi \mathrm{}`$, the function $`F(\xi ,\eta (\xi ))`$ would converge to the sum of the weights $`X_j`$, which is not compatible with $`F(\xi ,\eta (\xi ))=0`$. Thus $`\eta \mathrm{}`$ as $`ss_c`$. We now set $`\sigma _j(\xi )=\mathrm{tanh}(\xi X_j+\eta (\xi ))`$, so that

$$F(\xi ,\eta (\xi ))=\underset{j=1}{\overset{n}{}}X_j\sigma _i(\xi ).$$
(7.28)
In order to complete the proof of ii), we have to show that $`𝝈(\xi )`$ converges to the critical sorted partition as $`\xi \mathrm{}`$.

To this end, we first note

$$|1|\sigma _j(\xi )||2e^\xi ,$$
(7.29)
for all but at most one $`j`$. Indeed, let $`X(\xi )=\eta (\xi )/\xi `$, so that $`\sigma _j(\xi )=\mathrm{tanh}(\xi (X_jX(\xi )))`$. Let $`j_0`$ be such that $`|X_{j_0}X(\xi )|`$ is minimal. Since two consecutive weights $`X_j`$, $`X_{j+1}`$ differ by at least $`1`$, we conclude that $`|X_jX(\xi )|1/2`$ for all $`jj_0`$. Together with the bound $`||\mathrm{tanh}x|1|2e^{2|x}|`$ this proves (7.29) for $`jj_0`$.

Consider now a sequence $`(\xi _r)`$ with $`\xi _r\mathrm{}`$ as $`r\mathrm{}`$. By compactness, we can always find a subsequence such that $`𝝈(\xi _r)`$ converges to some $`\stackrel{~}{𝝈}`$. Due to (7.29), we must have that $`|\stackrel{~}{\sigma }_j|=1`$ for all but at most one $`j`$. Since $`F(\xi _r,\eta (\xi _r))=_j\sigma _j(\xi _r)X_j=0`$ and $`\sigma _1(\xi )\mathrm{}\sigma _n(\xi )`$, the same holds for the limiting sequence $`\stackrel{~}{\sigma }_1,\mathrm{},\stackrel{~}{\sigma }_n`$. As a consequence, $`\stackrel{~}{𝝈}`$ is the critical sorted partition defined in (7.22) (recall that the critical sorted partition is unique). Thus any convergent subsequence of $`𝝈(\xi _r)`$ converges to the critical sorted partition $`\stackrel{~}{𝝈}`$, implying that $`𝝈(\xi _r)`$ itself converges to $`\stackrel{~}{𝝈}`$. This concludes the proof of ii).

iii) We already showed above that the equation $`g(\xi )=s_c`$ has no finite solution $`\xi <\mathrm{}`$. As pointed out in the remark following the theorem, this is the only statement in iii) which does not follow directly from the statements in ii).

## 8 Relaxed Version of the Integer Partitioning Problem

It is a rather common idea to approximate an optimization problem defined with integer-valued variables by its relaxed version, where the variables are now allowed to assume any value within the real intervals whose endpoints are the admissible values of the original integer variables. In our case, the relaxed version is a linear programming problem (LPP) which can be stated as follows. Find the minimum value $`d_{opt}`$ of $`d`$, subject to linear constraints

$`d{\displaystyle \underset{j}{}}\sigma _jX_j,{\displaystyle \underset{j}{}}\sigma _jX_jd,`$ (8.1)
$`{\displaystyle \underset{j}{}}\sigma _j=s,`$
$`1\sigma _j1,(1jn).`$
As usual, the LPP has at least one basis solution, i.e. a solution $`(𝝈,d_{opt})`$, which is an extreme (vertex) point of the polyhedron defined by the constraints (8.1). Let $`N(𝝈):=|\{j:\sigma _j(1,1)\}|`$ be the number of components of $`𝝈`$ which are non-integer. It is easy for the reader to verify that $`N(𝝈)2`$ for all basis solutions $`𝝈`$. In fact, $`N(𝝈)`$ cannot be $`1`$ either, since in this case the exceptional $`\sigma _{j_0}\pm 1`$ must be zero, which contradicts to $`sn(\text{mod }2)`$. Thus, for a basis solution, $`N(𝝈)\{0,2\}`$. $`N(𝝈)=0`$ signals that $`𝝈`$ is an optimal partition. Suppose $`N(𝝈)=2`$, and let $`\{j_1,j_2\}=\{j:\sigma _j(1,1)\}`$. Using the second line in (8.1), we see that

$$\sigma _{j_1}+\sigma _{j_2}\{1,0,1\}.$$
(8.2)
Moreover, the second condition in (8.1), combined with $`sn(\text{mod }2)`$, rules out the values $`\pm 1`$. Therefore, $`\{\sigma _j\}_{jj_1,j_2}`$ is a partition of $`\{X_j\}_{jj_1,j_2}`$, of bias $`s`$.

Our last theorem shows that the horizontal line $`b=b_c`$ is a phase boundary for the LPP as well. For $`b>b_c`$ the solutions of the initial partition problem and of its LPP version coincide. For $`b<b_c`$ they are very far apart, in terms of the ratio of respective optimal discrepancies. To state this precisely, we introduce the fraction of basis solutions $`𝝈`$ with a property that the deletion of the $`N(𝝈)`$ components of $`𝝈`$ with values in $`(1,1)`$ produces an optimal integer partition for the remaining weights $`X_j`$. We denote this fraction by $`F_n(\kappa ,b)`$.

###### Theorem 8.1

Let $`lim\; sup\kappa <\mathrm{}`$ and $`0<lim\; inf\kappa `$.

(i) If $`lim\; infs/n>b_c`$, then w.h.p. the sorted partition $`𝝈^{}`$ is an unique solution of the LLP (8.1), so that in particular $`F_n(\kappa ,b)=1`$ and $`d_{opt}=\mathrm{\Theta }(Mn)`$.

Let $`lim\; sups/n<b_c`$.

(ii) W.h.p. $`d_{opt}=0`$, and there are $`2^{\kappa _c(b)n+O(n^{1/2}\mathrm{log}n)}`$ basis solutions $`(𝝈,0)`$.

(iii) If $`lim\; inf(\kappa \kappa _c(b))>0`$, all basis solutions are fractional (i.e. have $`N(𝝈)=2`$), and if $`lim\; sup(\kappa \kappa _{}(b))<0`$, the number of basis solutions with $`N(𝝈)=0`$ is at most $`2^{(\kappa _c(b)\kappa )n+O_p(n^{1/2})}`$.

(iv) If $`0<\epsilon <\kappa _{}(b)`$ and $`lim\; inf(\kappa \kappa _{}(b))>0`$, then, w.h.p., $`2^{\kappa _c(b)n\epsilon n}F_n(\kappa ,b)2^{\kappa _{}(b)n+\epsilon n}`$. If $`lim\; sup(\kappa \kappa _{}(b))<0`$, then, w.h.p., $`F_n(\kappa ,b)=2^{\kappa n+O(n^{1/2}\mathrm{log}n)}`$.

###### Remark 8.1

(i) As discussed in Remark 6.1 (iii), we believe that the number of optimal partitions above $`\kappa _c`$ grows subexponentially in $`n`$. Let us assume such a bound, more precisely, assume that for $`\epsilon >0`$, for $`b<b_c`$, and for $`\kappa `$ with $`lim\; inf(\kappa \kappa _c(b))>0`$, we have that the number of optimal partitions is bounded by $`2^{\epsilon n}`$, with probability at least $`1o(n^2)`$. Under this assumption, the proof of Theorem 8.1 can be easily generalized to show that, w.h.p., $`2^{\kappa _c(b)n\epsilon n}F_n(\kappa ,b)2^{\kappa _c(b)n+\epsilon n}`$ whenever $`b<b_c`$ and $`lim\; inf(\kappa \kappa _c(b))>0`$.

(ii) If, on the other hand, one believes that the asymptotics of Theorem 5.1 hold up to $`\kappa _c`$, more precisely, if we assume that the bound (5.52) holds with probability at least $`1o(n^2)`$, whenever $`b<b_c`$ and $`lim\; sup(\kappa \kappa _c(b))<0`$, then one can prove that, w.h.p., $`F_n(\kappa ,b)=2^{\kappa n+o(n))}`$ for all $`(b,\kappa )`$ with $`b<b_c`$ and $`lim\; sup(\kappa \kappa _c(b))<0`$.

Proof of Theorem 8.1 and Remark 8.1. (i) Suppose $`lim\; infs/n>b_c`$. Then w.h.p. $`_j\sigma _j^{}X_{\pi (j)}=\mathrm{\Theta }(Mn)>0`$, where $`𝝈^{}`$ is the sorted partition, so that $`X_{\pi (1)}<\mathrm{}<X_{\pi (n)}`$, and

$$\sigma _j^{}=\{\begin{array}{cccc}& 1,\hfill & & jj_n,\hfill \\ & 1,\hfill & & j>j_n.\hfill \end{array}$$
(8.3)
Let $`𝝈[1,1]^n`$ be an arbitrary relaxed partition with $`𝝈𝕖=𝝈^{}𝕖`$. The proof of (1) then reduces to the proof of the statement that

$$\underset{j}{}\sigma _jX_{\pi (j)}>\underset{j}{}\sigma _j^{}X_{\pi (j)}\text{if}𝝈𝝈^{}.$$
(8.4)
If $`𝝈𝝈^{}`$, then there exists a pair of indices $`i<j`$ such that $`\sigma _i<1`$ and $`\sigma _j>1`$. Assume that $`i`$ is the first such index, and that $`j`$ is the last such index. Since $`X_{\pi (i)}<X_{\pi (j)}`$, we can strictly lower the value of $`_j\sigma _jX_{\pi (j)}`$ by raising $`\sigma _i`$ and lowering $`\sigma _j`$, and preserving $`\sigma _i+\sigma _j`$, until at least one of them has absolute value 1, i.e. either $`\sigma _i=\sigma _i^{}`$ or $`\sigma _j=\sigma _j^{}`$. Repeating this procedure with the lowest $`i`$ and the largest $`j`$ such that $`\sigma _i<1`$ and $`\sigma _j>1`$ in the new configuration, we will eventually arrive at the configuration $`𝝈^{}`$. Since the value of $`_j\sigma _jX_{\pi (j)}`$ was strictly lowered in each step, this proves (8.4), and thus statement (i).

(ii) Let $`lim\; sups/n<b_c`$, and consider the partitioning problem for $`\{X_j\}_{j3}`$. Let $`a>0`$, and set $`\mathrm{}_n=Mn^a`$. By Theorem 6.3, we have that with probability $`1O(e^{\delta \mathrm{log}^2n})`$, there are at least $`2^{n\kappa _cO(n^{1/2}\mathrm{log}n)}`$ tuples $`\{\sigma _j\}_{j3}`$ such that

$$|\underset{j3}{}\sigma _jX_j|\mathrm{}_n.$$
(8.5)
We will denote the event expressed in (8.5) by $`𝒜`$. On the other hand, introducing the event $`=\{|X_1X_2|>Mn^{a_1}\}`$, $`a_1(0,a)`$, we have

$`()=`$ $`1{\displaystyle \frac{1}{M^2}}{\displaystyle \underset{\genfrac{}{}{0pt}{}{1i,jM}{|ij|Mn^{a_1}}}{}}1`$ (8.6)
$`=`$ $`1O(n^{a_1}).`$
Introducing $`𝒞=𝒜`$, we have then that $`1(𝒞)0`$. On $`𝒞`$, we can define $`\sigma _1=\sigma _2`$ where

$$\sigma _1=\frac{_{j1,2}\sigma _jX_j}{X_1X_2}=O(n^{(aa_1)})[1,1].$$
(8.7)
Clearly $`_{j=1}^n\sigma _jX_j=0`$, and denoting $`𝝈=\{\sigma _j\}_{1jn}`$, we have that $`(𝝈,0)`$ is a basis solution of the LPP. Thus w.h.p. the LPP has at least $`2^{n\kappa _cO(n^{1/2}\mathrm{log}n)}`$ basis solutions.

Conversely, suppose $`𝝈`$ is a basis solution, with $`\sigma _1,\sigma _2(1,1)`$, and $`\sigma _1+\sigma _2=0`$. Then

$$\left|\underset{j3}{}\sigma _jX_j\right||X_1X_2|M=o(Mn^{1/2}\mathrm{log}^1n).$$
(8.8)
Again by Theorem 6.3, we know that with probability $`1O(e^{\delta \mathrm{log}^2n})`$, the total number of all such $`(n2)`$-tuples with bias $`s`$ is $`2^{n\kappa _c+O(n^{1/2}\mathrm{log}n)}`$, and for each such tuple, the feasible values of $`\sigma _1,\sigma _2`$ are determined uniquely. Since there are $`\left(\genfrac{}{}{0pt}{}{n}{2}\right)`$ ways to select $`j_1,j_2`$ as indices of components $`\sigma _j(1,1)`$, and since the union of $`\left(\genfrac{}{}{0pt}{}{n}{2}\right)`$ events happening with probability $`1O(e^{\delta \mathrm{log}^2n})`$ happens with probability $`1O(n^2e^{\delta \mathrm{log}^2n})`$, we get that $`2^{n\kappa _c+O(n^{1/2}\mathrm{log}n)}`$ is also w.h.p. an upper bound on the number of basis solutions $`𝝈`$ with $`N(𝝈)=2`$.

If $`N(𝝈)=0`$ then, since $`b<b_c`$, $`𝝈`$ is a perfect partition, and thus of zero discrepancy. The number of such partitions can clearly be bounded by the number of partitions with discrepancy smaller than $`\mathrm{}_n=M`$. By Theorem 6.3, this is in turn bounded by $`2^{n\kappa _c+O(n^{1/2}\mathrm{log}n)}`$, completing the proof that the number of basis solutions with $`N(𝝈)=0`$ or $`N(𝝈)=2`$ is $`2^{n\kappa _c+O(n^{1/2}\mathrm{log}n)}`$.

(iii) If $`lim\; inf(\kappa \kappa _c(b))>0`$ or $`lim\; sup(\kappa \kappa _{}(b))<0`$, we know a little bit more. In the first case, w.h.p. there are no perfect partitions, and thus no basis solutions with $`N(𝝈)=0`$. In the latter case, w.h.p. the number of perfect partitions of zero discrepancy (and thus the number of basis solutions with $`N(𝝈)=0`$) is at most $`2^{(\kappa _c(b)\kappa )n+O_p(n^{1/2})}`$, which is negligible relative to $`2^{\kappa _c(b)n+O(n^{1/2}\mathrm{log}n)}`$.

(iv) If $`\epsilon >0`$ and $`lim\; inf(\kappa \kappa _{}(b))>0`$, then with probability $`1O(n^2e^{\delta \mathrm{log}^2n})`$, for every subset of $`(n2)`$ weights $`X_j`$, there are at most $`2^{(\kappa _c\kappa _{}+\epsilon )n}`$ optimal integer partitions by Corollary 6.2. As in (ii), once the $`\pm 1`$ values of the corresponding $`\sigma _j`$ are known, the values of the two remaining $`\sigma _j`$ are determined uniquely. So w.h.p. the LPP may have at most $`\left(\genfrac{}{}{0pt}{}{n}{2}\right)2^{(\kappa _c\kappa _{}+\epsilon )n}`$ basis solutions with $`N(𝝈)=2`$ that have the optimal subpartition property. Similarly, the number of $`𝝈`$ with $`N(𝝈)=0`$ is at most $`2^{(\kappa _c\kappa _{}+\epsilon )n}`$. So for every $`\epsilon `$, w.h.p.

$$F_n(\kappa ,b)2^{\kappa _{}(b)n+2\epsilon n}.$$
(8.9)
If we assume that for $`lim\; inf(\kappa \kappa _c(b))>0`$, the number of optimal partitions obeys the bound $`Z_{opt}2^{\epsilon n}`$ with probability at least $`1o(n^2)`$, so that w.h.p. for every subset of $`(n2)`$ weights $`X_j`$ there are at most $`2^{\epsilon n}`$ many optimal integer partitions, the above argument gives that for $`lim\; inf(\kappa \kappa _c(b))>0`$, w.h.p.,

$$F_n(\kappa ,b)2^{\kappa _c(b)n+2\epsilon n}.$$
(8.10)
Combined with the bound (8.13) below, this proves Remark 8.1.

Conversely, given $`j_1,j_2`$, with probability $`1O(e^{\delta \mathrm{log}^2n})`$ there exists at least one optimal partition $`\{\sigma _j\}_{jj_1,j_2}`$ of the subset $`\{X_j\}_{jj_1,j_2}`$, with discrepancy

$$\left|\underset{jj_1,j_2}{}\sigma _jX_j\right|M2^{\kappa _{}(b)n+ϵn}$$
(8.11)
by the bound (6.64) of Theorem 6.3. Given such an optimal subpartition (and assuming that $`\epsilon `$ has been chosen smaller than $`\kappa _{}(b)`$), with sufficiently high probability we can find an unique pair $`\sigma _{j_1},\sigma _{j_2}(1,1)`$ such that $`\{\sigma _j\}_{1jn}`$ is a basis solution of the full LPP, by solving

$`\sigma _{j_1}X_{j_1}+\sigma _{j_2}X_{j_2}`$ $`=`$ $`{\displaystyle \underset{jj_1,j_2}{}}\sigma _jX_j,`$
$`\sigma _{j_1}+\sigma _{j_2}`$ $`=`$ $`0.`$
Indeed, with probability $`1O(e^{\delta \mathrm{log}^2n})`$, the sum on the right is bounded by $`M2^{\kappa _{}(b)n+\epsilon n}`$, and with probability $`1O(2^{\kappa _{}(b)n+ϵn})`$,

$$|X_{j_1}X_{j_2}|M2^{\kappa _{}(b)n+ϵn}.$$
(8.12)
Thus w.h.p. there exist at least $`\left(\genfrac{}{}{0pt}{}{n}{2}\right)`$ basis solutions with the optimal subpartition property, so that

$$2^{\kappa _c(b)n\epsilon n}F_n(\kappa ,b)$$
(8.13)
as long as $`0<\epsilon <\kappa _{}(b)`$.

Consider finally $`lim\; sup(\kappa \kappa _{}(b))<0`$. Then, by Theorem 5.1, on the event “$`_jX_j`$ is even,” w.h.p. we have $`2^{(\kappa _c(b)\kappa )n+O(n^{1/2}\mathrm{log}n)}`$ perfect partitions $`𝝈`$ of discrepancy zero, each being a basis solution of the LPP with $`N(𝝈)=0`$. On the complementary event “$`_jX_j`$ is odd”, w.h.p. there are $`2^{(\kappa _c(b)\kappa )n+O(n^{1/2}\mathrm{log}n)}`$ perfect partitions $`\{\sigma _j\}_{j1,2}`$ of $`\{X_j\}_{j1,2}`$, of discrepancy one, and we can find, uniquely, $`\sigma _1,\sigma _2(1,1)`$ such that

$$\sigma _1+\sigma _2=0,\sigma _1X_1+\sigma _2X_2=\underset{j1,2}{}\sigma _jX_j.$$
(8.14)
Indeed $`|X_1X_2|`$ is w.h.p. of order, say, $`Mn^a`$ at least $`(a>0)`$, and the last sum is in $`[1,1]`$. Thus, regardless of the parity of $`_jX_j`$, the LPP has w.h.p. at least $`2^{(\kappa _c(b)\kappa )n+O(n^{1/2}\mathrm{log}n)}`$ basis solutions with the optimal subpartition property.

On the other hand, the total number of the optimal subpartition basis solutions $`𝝈`$ is at most $`2^{(\kappa _c(b)\kappa )n+O(n^{1/2}\mathrm{log}n)}`$ with probability $`1O(n^2e^{\delta \mathrm{log}^2n})`$. Indeed, for $`N(𝝈)=0`$, $`𝝈`$ is a perfect partition, and for $`N(𝝈)=2`$, the $`\pm 1`$-valued $`\sigma _j`$ form an optimal, hence perfect partition of the corresponding weights $`X_j`$. In either case, the number of corresponding perfect partitions is asymptotic to $`2^{(\kappa _c(b)\kappa )n+O(n^{1/2}\mathrm{log}n)}`$, and $`F_n(k,b)=2^{\kappa n+O(\sqrt{n}\mathrm{log}n)}`$.

Finally, if we assume that the bound (5.52) holds with probability at least $`1o(n^2)`$, whenever $`b<b_c`$ and $`lim\; sup(\kappa \kappa _c(b))<0`$, then the above arguments immediately give that, w.h.p., $`F_n(k,b)=2^{\kappa n+o(n)}`$. $`\mathrm{}`$

## 9 Open Problems and Numerical Experiments

### 9.1 Open Problems

Many problems are left open in our analysis. Most important is the question of how we characterize the phase transition from the perfect phase to the hard phase. In the unconstrained case , our theorems would have allowed us to give at least three equivalent definitions.

First, in the unconstrained problem, we defined the phase transition to be the point $`\kappa =\kappa _c=1`$ at which the probability of a perfect partition decreases abruptly from $`1`$ to $`0`$. For the constrained case considered in this paper, we have proved only that such a transition occurs somewhere within the interval $`(\kappa _{}(b),\kappa _c(b))`$. In particular, we have not proved that such a transition is sharp.

Second, in the constrained case, we could have characterized the phase transition as the point up to which the expected number of perfect partitions remains exponential, which again would have led to the value $`\kappa =\kappa _c=1`$ . In contrast, in the unconstrained case, here we have shown that the expected number of perfect partitions remains exponential until some $`\kappa =\kappa _e(b)>\kappa _c(b)`$, because up to $`\kappa =\kappa _e(b)`$, with vanishingly small probability, there are very many perfect partitions. Thus we cannot use the second definition in the constrained case. Alternatively, one could ask whether the typical (say median) number of perfect partitions changes from exponentially large to $`0`$ at $`\kappa =\kappa _c(b)`$, a definition that would have given the same transition point $`\kappa _c=1`$ in the unconstrained case, and that might also work here.

A third possible definition of the transition point is the point above which there is an unique optimal partition, a definition which would have again led to $`\kappa _c=1`$ in the unconstrained case . Here we cannot prove uniqueness until we are in the sorted phase ($`b>b_c`$), far above $`\kappa =\kappa _c(b)`$.

A natural conjecture would be that at least the first and third definitions coincide and that both lead to a sharp transition along the line $`\kappa =\kappa _c(b)`$.

Assuming we could establish a sharp transition, we could then examine some other open problems. In the unconstrained problem, we were able to determine the finite-size scaling window around the transition point $`\kappa =\kappa _c`$, i.e. the region in which the probability of a perfect partition has nontrivial distribution. In , we showed that the window has width of order $`n^1`$, and is centered at $`\kappa _c+\mathrm{\Theta }(n^1\mathrm{log}n)`$ . In the constrained case, as discussed in Remark 2.4, the fluctuations in the number of perfect partitions should be large enough to lead to a nontrivial probability distribution within a window of width of order $`n^{1/2}`$ about $`\kappa _c`$. Hence we expect the width of the window to be larger here than it was in the unconstrained case, at least of order $`n^{1/2}`$. Our numerical experiments, reviewed in the next subsection, support this expectation.

Next, detailed estimates in the unconstrained case proved that the $`k`$ smallest discrepancies (i.e., for a given set of $`n`$ random integers, the $`k`$ smallest absolute values of the difference in the sums of the integers in the two subsets) have a Poisson joint distribution . This is the behavior that would be observed if the discrepancies of $`2^{n1}`$ partitions (with $`\sigma _1`$ fixed) were independent random variables. This result confirmed the validity of the so-called Random Energy Model or REM approximation for the continuous case, proposed earlier by Mertens . We have no analogous estimates for the constrained problem.

Finally, for both the constrained and unconstrained problems, it would be very useful to have theorems which establish the relevance of our phase transition results (and associated results like the Poisson joint distribution) to the complexity of the number partitioning problem, and to the performance of widely used algorithms for the problem. In particular, is the perfect phase easy, i.e., in this phase, is it possible to find some perfect partition in polynomial time? Is the so-called hard phase actually computationally difficult (under the usual assumptions, e.g., P $``$ NP)? What are the changes in the behavior of commonly used algorithms at $`\kappa =\kappa _c(b)`$? Is $`\kappa _{}(b)`$ an artifact of our proofs or does it reflect some change in the complexity of the problem? For example, is there a change in the (admittedly non-rigorous, but often very instructive) replica solution at $`\kappa =\kappa _{}(b)`$? Do commonly used algorithms experience any slowdown across this curve? And finally, can our LPP results be extended to establish genuine average-case complexity results for a class of partitioning algorithms?

### 9.2 Numerics

In this subsection, we present some simulations which address the question of sharpness of the transition and finite-size scaling. We begin with a brief discussion of methods, then go on to finite-size effects, since this is important for the interpretation of the results. Most of our simulations concern the number of perfect partitions in the crescent-shaped region from $`\kappa =\kappa _{}(b)`$ to $`\kappa =\kappa _c(b)`$.

#### 9.2.1 Methods and Accessible System Sizes

The general experimental setup is this: generate a random instance, i.e. $`n`$ random integers $`X_j`$, uniformly drawn from the interval $`[1,M]`$ and calculate the optimum discrepancy and the number of optimal solutions of the corresponding constrained partitioning problem. Loop over many such instances to get the empirical mean and the empirical standard deviation of quantities like the logarithm of the number of optimal partitions.

The numbers $`X_j`$ are constructed from the output of pseudorandom number generators; we use LCG64, a 64 bit linear congruential random number generator from the TRNG collection . It is known that the least significant bits of linear congruential recurrences are correlated, so it is dangerous to use the elements of such sequences directly as a random instance. Instead, we use a random number for each bit in $`X_j`$. The bits are set to 1 or 0 with probability $`\frac{1}{2}`$, depending on the most significant bits of the corresponding random number, thereby minimizing the influence of hidden correlations in the pseudorandom sequence. On the other hand, this restricts us to values of $`M`$ that are integer powers of 2.

We can afford these extra calls to the random number generator, since the generation of the random instances is not the part of the simulation that limits the accessible system sizes. The hard part of the simulations is the solution of the particular instance. (After all, we are dealing with an NP-hard problem.) Even in the perfect phase, where a smart heuristic algorithm might find one of the exponentially many perfect partitions quickly, we want to find them all, so there is no obvious way to avoid an exhaustive enumeration of all partitions. The corresponding $`O(2^n)`$ time complexity is the limiting factor for our accessible system sizes.

Horowitz and Sahni  presented an algorithm that solves the unconstrained integer partitioning problem in time $`O(n2^{\frac{n}{2}})`$, and this algorithm can easily be modified to count all perfect partitions for the constrained problem within the same time complexity. The Horowitz-Sahni algorithm achieves its prodigious speed-up by dividing the set of numbers $`X_j`$ in two halves and tabulating all $`2^{\frac{n}{2}}`$ possible discrepancies of the two half-sized sets. Each discrepancy of the original problem can then be represented by the sum or the difference of two elements, one from each table. The tables are sorted (this is the origin of the complexity $`O(n2^{\frac{n}{2}})`$), and due to the monotonicity of the sorted tables, the perfect partitions of the original problem can be found with only one single scan through both lists.

The drawback of the Horowitz-Sahni algorithm is that it trades time against space. For $`\kappa =1`$, the $`X_j`$’s are $`n`$-bit numbers, hence the tables require $`2n2^{\frac{n}{2}}`$ bits of computer memory. Equipped with 512 MByte of main memory, this means $`n50`$. For a single instance of size $`n=50`$, the optimum discrepancies for all (discrete) values of $`b`$ can be found in about 4 minutes on a Pentium III CPU with 800 Mhz clock rate. Averages over $`10^3`$ random instances can be calculated in less than half an hour using 156 CPUs of a Beowulf cluster . Counting all perfect partitions in the perfect phase can take considerably longer if there are many such partitions, i.e. for small values of $`\kappa `$.

#### 9.2.2 Concentration and Finite-Size Effects

For our first numerical experiment, we study the finite-size effects of the central quantity in the perfect phase, namely the number $`Z`$ of perfect partitions for given $`b`$ and $`\kappa `$.

Optimistically extending the formula (5.1) – (5.6) (Theorem 5.1), we expect that for large $`n`$

$$𝔼\left(\frac{1}{n}\mathrm{log}Z\right)L(\zeta ,\eta )\kappa \mathrm{log}2\frac{1}{n}\mathrm{log}\left(\pi n\sqrt{detR}\right)\frac{1}{4n}\text{Tr}R^1K$$
(9.1)
is a valid approximation for all $`\kappa <\kappa _c(b)`$. It is illuminating to check accuracy of this approximation numerically, even in absence of an error term bound, better than $`o(n^1)`$, which is implicit in (9.1).

Figure 4 shows the results of the simulation. For each data point we generated $`10^3`$ instances of $`n`$ random $`\kappa n`$-bit integers and counted the number $`Z`$ of perfect partitions using the Horowitz-Sahni algorithm. Each symbol in Figure 4 denotes the empirical average over the $`10^3`$ values of $`n^1\mathrm{log}Z`$, and the error bars indicate $`\pm 1`$ empirical standard deviation.

For $`n50`$, finite-size effects are clearly visible. On the other hand, the error bars decrease with increasing $`n`$, indicating a concentration of $`n^1\mathrm{log}Z`$ around its expected value. Note that the size of the error bars does not decrease if the number of random samples increases. This indicates that the error bars are a measure of the inherent fluctuations in $`n^1\mathrm{log}Z`$. Note also that for $`b>0`$, the statistical fluctuations are much larger than in the $`b=0`$ case, consistent with our rigorous results in Theorem B and Remark 2.4.

The most surprising observation is that Eq. 9.1 is a very good approximation for finite $`n>30`$. Note that the “finite-size corrections” in Eq. 9.1, i.e. the $`O(n^1\mathrm{log}n)`$-term and $`O(n^1)`$-term, are essential for a good approximation: even for $`n=50`$, the measured values of $`n^1𝔼(\mathrm{log}Z)`$ are about $`20\%`$ below the predicted asymptotic values.

#### 9.2.3 Sharpness and Location of the Perfect to Hard Transition

The major open problem with the phase diagram is the behavior of the system inside the crescent-shaped region between $`\kappa =\kappa _{}(b)`$ and $`\kappa =\kappa _c(b)`$. From Theorems 5.1 and 6.1, we know that w.h.p. there are exponentially many perfect partitions for $`\kappa <\kappa _{}`$ and no perfect partitions for $`\kappa >\kappa _c`$. What happens to the number of perfect partitions between $`\kappa =\kappa _{}`$ and $`\kappa =\kappa _c`$? Is there a sharp transition from “no” to “exponentially many” perfect partitions, like in the unconstrained case or the case $`b=0`$? If so, where does it occur?

For all numerical experiments shown in this section, we have chosen $`b=0.25`$ because here the gap between $`\kappa _{}=0.674\mathrm{}`$ and $`\kappa _c=0.799\mathrm{}`$ is relatively large. Setting $`b=0.25`$ means that $`n`$ must be a multiple of $`8`$.

In the first experiment, we determine $`_{\text{perfect}}`$, the fraction of randomly generated instances that have a perfect partition. According to Theorems 5.1 and 6.2, as $`n\mathrm{}`$, this fraction should tend to $`1`$ for $`\kappa <\kappa _{}`$ and to $`0`$ for $`\kappa >\kappa _c`$ . Figure 5 shows the results for $`n=32,40,48`$. For these finite $`n`$, the decay of $`_{\text{perfect}}`$ from $`1`$ to $`0`$ extends over an interval larger than the crescent-shaped region, but the values outside this region seem to converge to their limits $`1`$ and $`0`$ as $`n`$ gets larger.

To see more clearly what is happening with $`_{\text{perfect}}`$, we define555 Of course, for finite $`n`$, there is in general no solution $`\overline{\kappa }`$ to the equation $`_{\text{perfect}}(\overline{\kappa })=\frac{1}{2}`$. Instead, we take $`\overline{\kappa }_n`$ to be the closest linear interpolation of solutions with parameters $`n`$ and $`M=2^{\overline{\kappa }_nn}`$.  $`\overline{\kappa }`$ by $`_{\text{perfect}}(\overline{\kappa })=\frac{1}{2}`$ and plot $`_{\text{perfect}}`$ versus the rescaled control parameter $`\mathrm{\Delta }\kappa =(\kappa \overline{\kappa })n^{1/2}`$ for various values of $`n`$. By definition, all these curves intersect at $`\mathrm{\Delta }\kappa =0`$, but the simulation shows that the curves coincide for all values of $`\mathrm{\Delta }\kappa `$ (Figure 6). This data collapse indicates that $`_{\text{perfect}}`$ is not a function of the two parameters $`\kappa `$ and $`n`$, but of one single parameter $`\mathrm{\Delta }\kappa =(\kappa \overline{\kappa })n^{1/2}`$,

$$_{\text{perfect}}(\kappa ,n)=f\left((\kappa \overline{\kappa })n^{1/2}\right).$$
(9.2)
Validity of this scaling hypothesis in particular would imply that the transition $`_{\text{perfect}}=1`$ to $`_{\text{perfect}}=0`$ becomes sharp as $`n\mathrm{}`$ and that the width of the transition region scales like $`O(n^{1/2})`$. The transition point $`\overline{\kappa }`$ itself depends on $`n`$ but seems to converge to $`\kappa _c`$ as $`n\mathrm{}`$ (see Figure 8). Our simulation results support the conclusion that the probability of a perfect partition shows a sharp transition at $`\kappa _c`$:

$$\underset{n\mathrm{}}{lim}_{\text{perfect}}=\{\begin{array}{cc}1& \kappa <\kappa _c\\ 0& \kappa >\kappa _c\end{array}$$
(9.3)
So far, the crescent-shaped region is not visible in the simulations, but this may change if we look at other quantities like the number of perfect partitions for $`\kappa <\kappa _c`$.

Figure 7 shows the result of a simulation with $`n=40`$. The mean value of $`n^1\mathrm{log}Z`$ is very well approximated by a piecewise linear function

$$n^1𝔼\left(\mathrm{log}Z(\kappa )\right)=\{\begin{array}{cc}(\stackrel{~}{\kappa }\kappa )\mathrm{log}2& \kappa <\stackrel{~}{\kappa }\\ 0& \kappa >\stackrel{~}{\kappa }\end{array}$$
(9.4)
where $`\stackrel{~}{\kappa }`$ is a fit parameter that depends on $`n`$. Eq. 9.4 is a very accurate description of the numerical data even for rather small values of $`n`$. The value of $`n`$ influences only the size of the fluctuations of $`n^1\mathrm{log}Z(\kappa )`$ around its expected value and the value of $`\stackrel{~}{\kappa }`$. As $`n`$ becomes larger, the fluctuations decrease and $`\stackrel{~}{\kappa }`$ increases, moving beyond $`\kappa _{}`$ and towards $`\kappa _c`$ (see Figure 8). Note that Theorem 5.1 implies that $`lim_n\mathrm{}n^1\mathrm{log}Z`$ is linear function of $`\kappa `$ for $`\kappa <\kappa _{}`$.

Of course, the numerical data on $`\stackrel{~}{\kappa }`$ and $`\overline{\kappa }`$ do not allow us to conclude that both values will converge to $`\kappa _c`$ as $`n\mathrm{}`$, but it is obvious that both values increase with increasing $`n`$ and are larger than $`\kappa _{}`$. Again we can use Theorem 5.1 to estimate the finite-size corrections to $`\kappa _c`$,

$$\kappa _c(n)=\frac{L(\zeta ,\eta )}{\mathrm{log}2}\frac{\mathrm{log}\left(n\pi \sqrt{detR}\right)}{n\mathrm{log}2}\frac{\text{Tr}R^1K}{4n\mathrm{log}2}.$$
(9.5)
Figure 8 shows that both $`\overline{\kappa }`$ and $`\stackrel{~}{\kappa }`$ are close to the finite-size estimate of $`\kappa _c`$.

In all our simulations, we did not find any trace of a critical line $`\kappa _{}`$. The properties of the system do change for values below $`\kappa _c`$, but above $`\kappa _{}`$, but there is some evidence that this is a finite-size effect and that for really large systems, it is only $`\kappa _c`$ that matters.