# Perfect partitions of a random set of integers

Boris Pittel  Department of Mathematics, The Ohio State University, $231$ West
$18$-th Avenue, Columbus, Ohio $43210-1175$ (USA<EMAIL_ADDRESS>In
loving memory of Irina Pittel, my soulmate for sixty years.

###### Abstract.

Let $X_{1},\dots,X_{n}$ be independent integers distributed uniformly on
$\\{1,\dots,M\\}$, $M=M(n)\to\infty$ however slow. A partition $S$ of $[n]$
into $\nu$ non-empty subsets $S_{1},\dots,S_{\nu}$ is called perfect, if all
$\nu$ values $\sum_{j\in S_{\alpha}}X_{j}$ are equal. For a perfect partition
to exist, $\sum_{j}X_{j}$ has to be divisible by $\nu$. For $\nu=2$, Borgs et
al. proved, among other results, that, conditioned on $\sum_{j}X_{j}$ being
even, with high probability a perfect partition exists if
$\kappa:=\lim\tfrac{n}{\log M}>\tfrac{1}{\log 2}$, and that w.h.p. no perfect
partition exists if $\kappa<\tfrac{1}{\log 2}$. We prove that w.h.p. no
perfect partition exists if $\nu\geq 3$ and $\kappa<\tfrac{2}{\log\nu}$. We
identify the range of $\kappa$ in which the expected number of perfect
partitions is exponentially high. We show that for
$\kappa>\tfrac{2(\nu-1)}{\log[(1-2\nu^{-2})^{-1}]}$ the total number of
perfect partitions is exponentially high with probability
$\gtrsim(1+\nu^{2})^{-1}$.

###### Key words and phrases:

random, integer, partitions, discrepancy, enumeration, asymptotic,
distribution

###### 2010 Mathematics Subject Classification:

05A05, 05A15, 05A16, 05C05, 06B05, 05C80, 05D40, 60C05

##  1\. Introduction and main result

To liberally cite from Wikipedia [12] the partition problem is to determine if
a given multiset of integers can be partitioned into two subsets such that the
sums of numbers in the subsets are the same. An optimization version of the
partition problem is to partition the multiset into two subsets such that the
absolute value of the difference between the sums is minimized. In the
multiway partition problem, there is an integer $\nu$ and the problem is to
determine whether the multiset can be partitioned into $\nu$ subsets, each of
the same total sum. We are interested in the case when the integers to be
partitioned are random.

Specifically we have integers $X_{1},\dots,X_{n}$, which are independent, each
distributed uniformly on $[M]:=\\{1,\dots,M\\}$. Given $\nu\geq 2$, consider
an ordered partition of $[n]$ into non-empty subsets $S_{1},\dots,S_{\nu}$,
which we denote $\mathbb{S}$. A partition $\mathbb{S}$ of $[n]$ is called
perfect if $\sum_{j\in
S_{\alpha}}X_{j}\equiv\tfrac{1}{\nu}\sum_{j\in[n]}X_{j}$, $\alpha\in[\nu]$.
For a perfect partition to exist, it is necessary that $\sum_{j\in[n]}X_{j}$
is divisible by $\nu$. For $\nu=2$, Borgs, Chayes, and Pittel [3] proved the
following result, among a series of other, sharper claims. Conditioned on
$\sum_{j}X_{j}$ even, with high probability, a perfect partition exists (does
not exist) if $\lim\tfrac{n}{\log M}>\tfrac{1}{\log 2}$ (if
$\lim\tfrac{n}{\log M}<\tfrac{1}{\log 2}$). In a follow-up paper Borgs,
Chayes, Mertens, and Pittel [4] analyzed a constrained version, when the
cardinalities of the two sets are given. A constrained version with $k$ sets
of the same cardinality was analyzed later by Bovier and Kurkova [5]. We refer
the reader to Graham [7], Gent and Walsh [6], Hayes [8], Karmarkar, Karp,
Lueker, and Odlyzko [9], Mertens [10], and Yakir [13], for the long history of
the problem and its various aspects, from computational issues to conceptual
connections with statistical physics.

In 2021 Tim Varghese and George Varghese [11] posed a problem of extending
probabilistic analysis of perfect partitions into two subsets to multiway
partitions, i.e. partitions of a set of random integers into $\nu>2$ subsets
with the same sum of integers in each subset. Here is what we have found.

######  Theorem 1.1.

Let $\nu\geq 3$. Suppose $M=M(n)\to\infty$, $M=exp(O(n))$. (1) Expected number
of perfect partitions tends to zero, if $\lim\tfrac{n}{\log
M}<\tfrac{2}{\log\nu}$. (2) Expected number of perfect partitions is
exponentially large (a) for $\nu=3$ and $\lim\tfrac{n}{\log
M}\in\bigl{(}\tfrac{2}{\log 3},\infty\bigr{)}\setminus\\{2,4\\}$, and (b) for
$\nu\geq 4$ and $\lim\tfrac{n}{\log
M}\in\bigl{(}\tfrac{2}{\eta(\nu)},\infty\bigr{)}\setminus\\{2(\nu-1)\\}$,
$\eta(\nu)$ being a single root of $\tfrac{e^{(\nu-1)\eta}}{\nu e\eta}-1$ in
$\bigl{(}\tfrac{1}{\nu-1},\tfrac{2\log\nu}{\nu-1}\bigr{)}$.

We conjecture that $\lim\tfrac{n}{\log M}=2(\nu-1)$ for $\nu\geq 3$, and
$\lim\tfrac{n}{\log M}=2$ for $\nu=3$ need not be excluded for (2) to hold.
What happens when $\nu>3$ and $\lim\tfrac{n}{\log
M}\in\bigl{(}\tfrac{2}{\log\nu},\tfrac{2}{\eta(\nu)}\bigr{)}$? Our second
result is

######  Theorem 1.2.

Suppose $\nu\geq 3$. If $\lim\tfrac{n}{\log
M}>\tfrac{2(\nu-1)}{\log[(1-2\nu^{-2})^{-1}]}$, then with the limiting
probability $\gtrsim(1+\nu^{2})^{-1}$ the total number of perfect partitions
is exponentially large, of the same order of magnitude as the expected number
of perfect partitions.

The lower bound $(1+\nu^{2})^{-1}$ is below
$\nu^{-1}\\!=\\!\lim_{M\to\infty}\mathbb{P}\bigl{(}\sum_{j\in[n]}X_{j}\\!\equiv\\!0(\text{mod
}\nu)\bigr{)}$, uniformly for $n\geq 1$. (A simple, elegant proof of the
latter was conveyed to me by Huseyin Acan [1].)

##  2\. Integral formulas

######  Lemma 2.1.

Suppose $\nu>2$. Let $Z_{n}$ denote the random total number of all perfect
ordered partitions of $[n]$ into $\nu$ non-empty subsets. (1) Then

(2.1)
$\displaystyle\,Z_{n}=\frac{1}{(2\pi)^{\nu}}\\!\\!\\!\int\limits_{\mathbb{x}\in[-\pi,\pi]^{\nu}}\prod_{j\in[n]}f(\mathbb{x},X_{j})\,\,d\mathbb{x},\quad\mathbb{x}:=\\{x_{1},\dots,x_{\nu}\\},$
$\displaystyle
f(\mathbb{x},\eta):=\sum_{\alpha\in[\nu]}\exp\bigl{(}iy_{\alpha}\eta\bigr{)},\quad
y_{\alpha}=y_{\alpha}(\mathbb{x}):=\nu
x_{\alpha}-\sum_{\beta\in[\nu]}x_{\beta}.$

Consequently, denoting by $X$ a random variable distributed as each of
$X_{j}$, we have

(2.2)
$\mathbb{E}\bigl{[}Z_{n}\bigr{]}=\\!\frac{1}{(2\pi)^{\nu}}\int_{\mathbb{x}\in[-\pi,\pi]^{\nu}}\mathbb{E}^{n}\bigl{[}f(\mathbb{x},X)\bigr{]}d\mathbb{x}.$

(2) Furthermore

(2.3) $\displaystyle\mathbb{E}[Z_{n}^{2}]$
$\displaystyle=\frac{1}{(2\pi)^{2\nu}}\\!\\!\\!\int\limits_{\mathbb{x},\mathbb{x}^{\prime}}\mathbb{E}^{n}\bigl{[}f(\mathbb{x},X)\overline{f(\mathbb{x}^{\prime},X)}\bigr{]}\,\,d\mathbb{x}d\mathbb{x}^{\prime}.$

###### Proof.

(1) Given an ordered partition $\mathbb{S}=\\{S_{1},\dots,S_{\nu}\\}$ of $[n]$
into non-empty subsets $S_{\alpha}$, define $Y_{\alpha}:=\sum_{j\in
S_{\alpha}}X_{j}$, so that
$\sum_{\beta\in[\nu]}Y_{\beta}=\sum_{j\in[n]}X_{j}$. $\mathbb{S}$ is perfect
if and only if

(2.4) $\nu\cdot
Y_{\alpha}-\sum_{\beta\in[\nu]}Y_{\beta}=0,\quad\alpha\in[\nu].$

Clearly, for a perfect partition to exist, $\sum_{j\in[n]}X_{j}$ must be
divisible by $\nu$. Let $\mathbb{I}(A)$ denote the indicator of an event $A$.
Then

$\mathbb{I}(\mathbb{S}\text{
perfect})=\prod_{\alpha\in[\nu]}\mathbb{I}\biggl{(}\nu\cdot
Y_{\alpha}-\sum_{\beta\in[\nu]}Y_{\beta}=0\biggr{)}\\\
=\prod_{\alpha\in[\nu]}\frac{1}{2\pi}\int_{x\in[-\pi,\pi]}\exp\biggl{[}ix\biggl{(}\nu\cdot
Y_{\alpha}-\sum_{\beta\in[\nu]}Y_{\beta}\biggr{)}\biggr{]}\,dx\\\
=\frac{1}{(2\pi)^{\nu}}\int_{\mathbb{x}\in[-\pi,\pi]^{\nu}}\exp\biggl{[}i\sum_{\alpha\in[\nu]}x_{\alpha}\biggl{(}\nu\cdot
Y_{\alpha}-\sum_{\beta\in[\nu]}Y_{\beta}\biggr{)}\biggr{]}\,d\mathbb{x},\quad\mathbb{x}:=\\{x_{\alpha}\\}_{\alpha\in[\nu]}.$

Summing the above equation over all ordered partitions $\mathbb{S}$ with
nonempty $S_{\alpha}$’s, and interchanging summation and integration on RHS,
we obtain

(2.5)
$Z_{n}=\frac{1}{(2\pi)^{\nu}}\int_{\mathbb{x}\in[-\pi,\pi]^{\nu}}\sum_{\mathbb{S}}\exp\biggl{[}i\sum_{\alpha\in[\nu]}x_{\alpha}\biggl{(}\nu\cdot
Y_{\alpha}-\sum_{\beta\in[\nu]}Y_{\beta}\biggr{)}\biggr{]}\,d\mathbb{x}.$

What if $\mathbb{S}$ is such that some $S_{\alpha_{0}}=\emptyset$? In this
case $Y_{\alpha_{0}}=\sum_{j\in S_{\alpha_{0}}}X_{j}=0$; so the factor by
$ix_{\alpha_{0}}$ in the exponent sum is $-\sum_{j\in[n]}X_{j}\neq 0$. Then
the integral of the corresponding exponential function over the (hyper)cube
$[-\pi,\pi]^{\nu}$ is zero. Therefore we may, and will extend the sum in (2.5)
to all ordered sequences $\mathbb{S}$ of sets $S_{1},S_{2},\dots,S_{\nu}$,
empty or non-empty, that form a partition of $[n]$. Regrouping summands in the
exponent we obtain

$\displaystyle\exp\biggl{[}i\sum_{\alpha\in[\nu]}x_{\alpha}\biggl{(}\nu\cdot
Y_{\alpha}-\sum_{\beta\in[\nu]}Y_{\beta}\biggr{)}\biggr{]}=\prod_{j\in[n]}\exp(i\sigma_{j}X_{j}),$
$\displaystyle\quad\,\,\sigma_{j}=\sum_{\alpha\in[\nu]}x_{\alpha}\Bigl{(}\nu\,\delta_{\alpha}(j)-1\Bigr{)},\quad\delta_{\alpha}(j):=\mathbb{I}(j\in
S_{\alpha}).$

Such a relaxed partition $\mathbb{S}$ is uniquely determined by values of
$\delta_{\alpha}(j)\in\\{0,1\\}$, subject to
$\sum_{\alpha\in[\nu]}\delta_{\alpha}(j)=1$, ($j\in[n]$), but not to
$\sum_{j\in[n]}\delta_{\alpha}(j)\geq 1$, ($\alpha\in[\nu]$), because empty
$S_{\alpha}$ are allowed now. Thus, $\delta_{\alpha}(j)$ vary independently
for different $j$. So, introducing

$\Sigma(\mathbb{x}):=\biggl{\\{}\sum_{\alpha\in[\nu]}x_{\alpha}\bigl{(}\nu\,\delta_{\alpha}-1\bigr{)}:\delta_{\gamma}\in\\{0,1\\},\,\sum_{\gamma\in[\nu]}\delta_{\gamma}=1\biggr{\\}},$

for the sum over relaxed partitions we obtain

$\sum_{\mathbb{S}}\exp\biggl{[}i\sum_{\alpha\in[\nu]}x_{\alpha}\biggl{(}\nu\cdot
Y_{\alpha}-\sum_{\beta\in[\nu]}Y_{\beta}\biggr{)}\biggr{]}=\prod_{j\in[n]}\sum_{\sigma\in\Sigma(\mathbb{x})}\exp(iX_{j}\sigma)\\\
=\prod_{j\in[n]}\sum_{\alpha\in[\nu]}\exp\biggl{[}i\biggl{(}\nu
x_{\alpha}-\sum_{\beta\in[\nu]}x_{\beta}\biggr{)}X_{j}\biggr{]}=\prod_{j\in[n]}\sum_{\alpha\in[\nu]}\exp\bigl{(}iy_{\alpha}(\mathbb{x})X_{j}\bigr{)}.$

We conclude that

$Z_{n}=\frac{1}{(2\pi)^{\nu}}\int\limits_{\mathbb{x}\in[-\pi,\pi]^{\nu}}\prod_{j\in[n]}\sum_{\alpha\in[\nu]}\exp\bigl{(}iy_{\alpha}(\mathbb{x})X_{j}\bigr{)}\,\,d\mathbb{x},$

which is (2.1) in the lemma. Equating the expectations of both sides and using
independence of $X_{j}$’s, we get (2.2).

(2) The equation (2.1) implies that

$Z_{n}^{2}=\frac{1}{(2\pi)^{2\nu}}\\!\\!\\!\int\limits_{\mathbb{x},\mathbb{x}^{\prime}}\prod_{j\in[n]}f(\mathbb{x},X_{j})\overline{f(\mathbb{x}^{\prime},X_{j})}\,\,d\mathbb{x}d\mathbb{x}^{\prime},$

so that

$\mathbb{E}[Z_{n}^{2}]=\frac{1}{(2\pi)^{2\nu}}\\!\\!\\!\int\limits_{\mathbb{x},\mathbb{x}^{\prime}}\mathbb{E}^{n}\bigl{[}f(\mathbb{x},X)\overline{f(\mathbb{x}^{\prime},X)}\bigr{]}\,\,d\mathbb{x}d\mathbb{x}^{\prime}.$

∎

##  3\. Expected number of perfect partitions

Using Lemma 2.1, we prove

######  Theorem 3.1.

Let $\nu\geq 3$. Suppose that $M=M(n)\to\infty$ however slowly. If
$\lim\tfrac{n}{\log M}<\tfrac{2}{\log\nu}$, then $\lim\mathbb{E}[Z_{n}]=0$.
(i) Suppose $\nu=3$. If $\lim\tfrac{n}{\log M}\in\bigl{(}\tfrac{2}{\log
3},\infty\bigr{)}\setminus\\{2,4\\}$, then

(3.1)
$\mathbb{E}\bigl{[}Z_{n}\bigr{]}=(1+o(1))\frac{\nu^{n}}{M^{\nu-1}}\cdot\frac{\nu^{\nu-3/2}}{(2\pi\nu
c_{M}n)^{\frac{\nu-1}{2}}}\to\infty,\\\ $

$c_{\scriptscriptstyle M}:=M^{-2}\mathbb{E}[X^{2}]=1/3+O(M^{-1})$. (ii)
Suppose $\nu\geq 4$. Then (3.1) holds if $\lim\tfrac{n}{\log
M}\in\bigl{(}\tfrac{2}{\eta(\nu)},\infty)\setminus\\{2(\nu-1)\\}$; here
$\eta(\nu)\in\bigl{(}\tfrac{1}{\nu-1},\tfrac{2\log\nu}{\nu-1}\bigr{)}$ is the
larger of two roots of $\tfrac{e^{(\nu-1)\eta}}{\nu e\eta}-1$, the smaller one
being below $\tfrac{1}{\nu-1}$.

Note. It is unclear whether $\mathbb{E}[Z_{n}]\to\infty$ if $\nu\geq 3$ and
$\lim\tfrac{n}{\log M}=2(\nu-1)$, or if $\nu=3$ and $\lim\tfrac{n}{\log M}=2$.
Perhaps $\mathbb{E}[Z_{n}]\to\infty$ in all these cases, albeit at a rate
lower then for $\lim\tfrac{n}{\log M}$ arbitrarily close to, but different
from $2(\nu-1)$ for $\nu\geq 3$, and from $2$ for $\nu=3$, respectively. The
case $\nu\geq 4$, $\lim\tfrac{n}{\log
M}\in\bigl{(}\tfrac{2}{\log\nu},\tfrac{2}{\eta(\nu)}\bigr{)}$ remains open as
well.

###### Proof.

By (2.2), we have

$\displaystyle\mathbb{E}\bigl{[}Z_{n}\bigr{]}$
$\displaystyle=\\!\frac{1}{(2\pi)^{\nu}}\\!\\!\\!\int\limits_{\mathbb{x}\in[-\pi,\pi]^{\nu}}\\!\\!\\!\mathbb{E}^{n}\bigl{[}f(\mathbb{x},X)\bigr{]}d\mathbb{x},$
$\displaystyle\mathbb{E}\bigl{[}f(\mathbb{x},X)\bigr{]}$
$\displaystyle=\sum_{\alpha\in[\nu]}\mathbb{E}\bigl{[}e^{iy_{\alpha}X}\bigr{]},\quad
y_{\alpha}=y_{\alpha}(\mathbb{x}):=\nu
x_{\alpha}-\sum_{\beta\in[\nu]}x_{\beta}.$

(I) Since $X$ is integer-valued,
$\Big{|}\mathbb{E}\bigl{[}f(\mathbb{x},X)\bigr{]}\Big{|}$ certainly attains
its maximum $\nu$ at every $\mathbb{x}$ such that for each $\alpha\in[\nu]$ we
have $y_{\alpha}=y_{\alpha}(\mathbb{x})=k_{\alpha}\pi$, and $k_{\alpha}$ is
even. Here necessarily $\sum_{\alpha\in[\nu]}k_{\alpha}=0$, since
$\sum_{\alpha\in[\nu]}y_{a}(\mathbb{x})=0$. Given such
$\mathbb{k}=\\{k_{\alpha}\\}_{\alpha\in[\nu]}$, the set of $\mathbb{x}$
satisfying

(3.2) $\nu
x_{\alpha}-\sum_{\beta\in[\nu]}x_{\beta}=k_{\alpha}\pi,\quad(\alpha\in[\nu]),$

is a straight line $\mathcal{L}_{\mathbb{k}}$ in $\mathbb{R}^{\nu}$, since the
$\nu\times\nu$ matrix on the LHS has rank $\nu-1$. We will prove that
$\Big{|}\mathbb{E}\bigl{[}f(\mathbb{x},X)\bigr{]}\Big{|}<\nu$ everywhere else.
Let us enumerate the lines $\mathcal{L}_{\mathbb{k}}$ that contain interior
points of the cube $[-\pi,\pi]^{\nu}$. To this end notice that each line’s
parametric equation is $x_{\alpha}=\nu^{-1}(t+k_{\alpha}\pi)$,
$t\in\mathbb{R}$. This line contains an interior point $\mathbb{x}$ of the
cube $[-\pi,\pi]^{\nu}$ if and only if for some $t$

$\nu^{-1}(t+k_{\alpha}\pi)\in(-\pi,\pi),\quad\forall\,\alpha\in[\nu],$

or equivalently

(3.3) $-\pi(\nu+\min k_{\alpha})<t<\pi(\nu-\max k_{\alpha}).$

In particular, $\max k_{\alpha}-\min k_{\alpha}\leq 2(\nu-1)$, since
$k_{\alpha}$ are even. For $\nu=2$ we have $k_{1}=k_{2}=0$ since
$k_{1}+k_{2}=0$. From now on we focus on $\nu>2$. We consider these
(admissible) lines only, since any other line can share at most one point with
the cube. And the set of all such touch points is finite.

Indeed, suppose $\mathcal{L}$ does not contain interior points of the cube. If
$\mathcal{L}$’s segment is in the cube, then this segment, i.e. a non-zero
multiple of $\mathbb{e}:=(1,\dots,1)\in E^{\nu}$, belongs to one of $2\nu$
faces, cubes of dimension $\nu-1$. Hence the segment is orthogonal to a
coordinate vector $(0,\dots,0,1,0,\dots 0)\in E^{\nu}$– contradiction. So
$\mathcal{L}$ shares at most one point with the cube. Any such touch point
$\mathbb{x}$ satisfies $y_{\alpha}(\mathbb{x})=\pi k_{\alpha}$,
$(\alpha\in[\nu])$, and it has to have a component $x_{\alpha^{\prime}}=\pi$,
and a component $x_{\alpha^{\prime\prime}}=-\pi$, for that matter. Otherwise
$\mathcal{L}$ would have contained interior points of the cube. The linear
system $y_{a}(\mathbb{x})=k_{\alpha}\pi$, $x_{\alpha^{\prime}}=\pi$ has at
most one solution in the cube, because the associated matrix has rank $\nu$.
So, since $|k_{\alpha}|\leq 2(\nu-1)$, $\alpha\in[\nu]$, the number of such
solutions (i.e. touch points) is at most $\nu(2\nu-1)^{\nu}$.

By (3.3), $\mathbb{k}=\\{k_{\alpha}\\}_{\alpha\in[\nu]}$, which consists of
even numbers adding up to $0$, is admissible if and only if
$d(\mathbb{k}):=2\nu+\min_{\alpha}k_{\alpha}-\max_{\alpha}k_{a}\geq 2,$ since
the range of the parameter $t$ is $\pi d(\mathbb{k})$, and the length of the
corresponding line segment is

(3.4) $L(\mathbb{k})=\pi
d(\mathbb{k})\nu^{-1/2}=\pi\nu^{-1/2}\bigl{(}2\nu+\min_{\alpha}k_{\alpha}-\max_{\alpha}k_{a}\bigr{)}.$

Let even numbers $a\leq 0\leq b$ be generic values of
$\min_{\alpha}k_{\alpha}$ and $\max_{\alpha}k_{\alpha}$. Let
$\mathcal{N}(a,b)$ be the total number of admissible
$\\{k_{\alpha}\\}_{\alpha\in[\nu]}$ with parameters $a$, $b$. Obviously
$\mathcal{N}(a,a)=\mathbb{I}(a=0)$, and $\mathcal{N}(a,a+2)=0$. Consider
$r:=b-a\in[4,2(\nu-1)]$, $2(\nu-1)$ coming from $d(\mathbb{k})\geq 2$. A
generic $\\{k_{\alpha}\\}$ with given $a=\min_{\alpha}k_{\alpha}$,
$b=\max_{\alpha}k_{\alpha}$, contains some $\mu_{1}>0$ components equal $a$,
and $\mu_{2}>0$ components equal $b$, with $\mu_{1}+\mu_{2}\leq\nu$, and
$\mu_{3}:=\nu-\mu_{1}-\mu_{2}$ remaining even components, with values strictly
between $a$ and $b$, such that the total sum of all $\nu$ components is zero.
Consequently, if $b\geq a+4$ then

(3.5) $\displaystyle N(a,b)$
$\displaystyle=[\zeta^{0}]\sum_{\mu_{1},\,\mu_{2}>0}\frac{\nu!}{\mu_{1}!\,\mu_{2}!\,\mu_{3}!}\cdot\zeta^{\mu_{1}a+\mu_{2}b}\biggl{(}\sum_{\text{even
}j=a+2}^{b-2}\zeta^{j}\biggr{)}^{\mu_{3}},$

with the last sum equal

(3.6) $\zeta^{a+2}\sum_{\text{even
}j=0}^{r-4}\zeta^{j}=\tfrac{\zeta^{a+2}(1-\zeta^{r-2})}{1-\zeta^{2}},\quad
r:=b-a.$

So, by inclusion-exclusion, the RHS function of $\zeta$ in (3.5) equals

$\biggl{[}\zeta^{a}+\zeta^{b}+\frac{\zeta^{a+2}(1-\zeta^{r-2})}{1-\zeta^{2}}\biggr{]}^{\nu}-\biggl{[}\zeta^{a}+\frac{\zeta^{a+2}(1-\zeta^{r-2})}{1-\zeta^{2}}\biggr{]}^{\nu}\\\
-\biggl{[}\zeta^{b}+\frac{\zeta^{a+2}(1-\zeta^{r-2})}{1-\zeta^{2}}\biggr{]}^{\nu}+\biggl{[}\frac{\zeta^{a+2}(1-\zeta^{r-2})}{1-\zeta^{2}}\biggr{]}^{\nu}\\\
=\zeta^{a\nu}\biggl{[}\biggr{(}\frac{1-\zeta^{r+2}}{1-\zeta^{2}}\biggr{)}^{\nu}-\biggr{(}\frac{1-\zeta^{r}}{1-\zeta^{2}}\biggr{)}^{\nu}-\biggl{(}\frac{\zeta^{2}-\zeta^{r+2}}{1-\zeta^{2}}\biggr{)}^{\nu}+\biggl{(}\frac{\zeta^{2}-\zeta^{r}}{1-\zeta^{2}}\biggr{)}^{\nu}\biggr{]}.$

So, we have

(3.7) $\displaystyle\mathcal{N}(a,b)$
$\displaystyle=[\zeta^{-a\nu}]\mathcal{F}_{r}(\zeta),$
$\displaystyle\mathcal{F}_{r}(\zeta)$
$\displaystyle=\biggr{(}\frac{1-\zeta^{r+2}}{1-\zeta^{2}}\biggr{)}^{\nu}-\biggr{(}\frac{1-\zeta^{r}}{1-\zeta^{2}}\biggr{)}^{\nu}$
$\displaystyle\qquad\qquad\qquad-\biggl{(}\frac{\zeta^{2}-\zeta^{r+2}}{1-\zeta^{2}}\biggr{)}^{\nu}+\biggl{(}\frac{\zeta^{2}-\zeta^{r}}{1-\zeta^{2}}\biggr{)}^{\nu}.$

Since $b=a+r>0$, we must have $\mathcal{N}(a,b)=0$ for $a\leq-r$. As a partial
validation, one can check that the top RHS of (3.7) is indeed zero for
$a\leq-r$, and also for $a=0$. What we will actually need is

(3.8) $\mathcal{N}(r):=\sum_{\text{even
}a<0}\mathcal{N}(a,a+r),\quad\text{even }r\in[4,2(\nu-1)],$

the total number of the relevant $\nu$-tuples of even integers
$\\{k_{\alpha}\\}_{\alpha\in[\nu]}$ adding up to $0$, such that
$\max_{\alpha\in[\nu]}k_{\alpha}-\min_{\alpha\in[\nu]}k_{\alpha}=r$. In fact,
ultimately we are after a single number, namely

$\mathcal{M}=\mathcal{M}(\nu):=2\nu+\sum_{\text{even
}r\in[4,2(\nu-1)]}(2\nu-r)\mathcal{N}(r),$

since $\pi\nu^{-1/2}\mathcal{M}$ is the total length of the in-cube segments
of lines for even tuples $\mathbb{k}$. Combining (3.7) and (3.8) and changing
the order of double summation we obtain

(3.9) $\mathcal{M}=2\nu+\sum_{\text{even }a\leq
0}[\zeta^{-a\nu}]\sum_{\text{even
}r\in[4,2(\nu-1)]}(2\nu-r)\mathcal{F}_{r}(\zeta).$

We included $a=0$ since $\mathcal{F}_{r}(0)=0$. Using the formula for
$\mathcal{F}_{r}(\zeta)$, and telescoping, we get: with $r$ even,

(3.10)
$\sum_{r\in[4,2(\nu-1)]}\\!\\!\\!\\!\\!\\!\\!\\!\\!\mathcal{F}_{r}(\zeta)\\!=\biggr{(}\\!\frac{1-\zeta^{2\nu}}{1-\zeta^{2}}\\!\biggr{)}^{\nu}\\!-\biggr{(}\\!\frac{1-\zeta^{4}}{1-\zeta^{2}}\\!\biggr{)}^{\nu}\\!-\biggl{(}\\!\frac{\zeta^{2}-\zeta^{2\nu}}{1-\zeta^{2}}\\!\biggr{)}^{\nu}\\!\\!+\biggl{(}\\!\frac{\zeta^{2}-\zeta^{4}}{1-\zeta^{2}}\\!\biggr{)}^{\nu}\\\
=\biggr{(}\\!\frac{1-\zeta^{2\nu}}{1-\zeta^{2}}\\!\biggr{)}^{\nu}-\biggl{(}\\!\frac{\zeta^{2}-\zeta^{2\nu}}{1-\zeta^{2}}\\!\biggr{)}^{\nu}-(1+\zeta^{2})^{\nu}+\zeta^{2\nu}:=S_{1}(\zeta^{2}).$

Then

$\sum_{\text{even }a\leq 0}[\zeta^{-a\nu}]\sum_{\text{even
}r\in[4,2(\nu-1)]}\mathcal{F}_{r}(\zeta)=\sum_{\alpha\geq
0}[z^{\alpha\nu}]S_{1}(z),$

and using a simple formula

(3.11) $\sum_{\alpha\geq
0}\,[z^{\alpha\nu}]\,S(z)=\tfrac{1}{\nu}\sum_{j=0}^{\nu-1}S(z_{j}),\quad
z_{j}:=\exp\bigl{(}i\tfrac{2\pi j}{\nu}\bigr{)},$

we obtain

(3.12) $\sum_{\alpha\geq
0}[z^{\alpha\nu}]S_{1}(z)=\tfrac{1}{\nu}\sum_{j=0}^{\nu-1}\Bigl{[}\Bigl{(}\tfrac{1-z_{j}^{\nu}}{1-z_{j}}\Bigr{)}^{\nu}-\Bigl{(}\tfrac{1-z_{j}^{\nu-1}}{1-z_{j}}\Bigr{)}^{\nu}\Bigr{]}-1\\\
=\tfrac{1}{\nu}\bigl{[}\nu^{\nu}-(\nu-1)^{\nu}-(\nu-1)(-1)^{\nu}\bigr{]}-1.$

Combinatorially, the RHS is the total number of all tuples associated with
lines containing interior points of the cube $[-\pi,\pi]^{\nu}$, distinct from
the diagonal $\mathbb{x}=\gamma\mathbb{e}$, i.e. $k_{\alpha}\equiv 0$. In
particular, it is $0$ for $\nu=2$, and it is $6=3!$, as it should be: the
former because the single admissible $2$-tuple is $\\{0,0\\}$, and the latter
because the admissible tuples $\\{k_{1},k_{2},k_{3}\\}\neq\\{0,0,0\\}$ are
$3!$ permutations of the single tuple $\\{-2,0,2\\}$.

Similarly telescoping again,

(3.13) $\sum_{\text{even
}r\in[4,2(\nu-1)]}\\!\\!\\!\\!\\!\\!r\,\mathcal{F}_{r}(\zeta)=2\nu\biggr{(}\\!\frac{1-\zeta^{2\nu}}{1-\zeta^{2}}\\!\biggr{)}^{\nu}\\!-2\nu\zeta^{2\nu}\biggl{(}\\!\frac{1-\zeta^{2(\nu-1)}}{1-\zeta^{2}}\\!\biggr{)}^{\nu}\\\
\quad+2\\!\\!\\!\\!\\!\sum_{\text{even
}r\in[6,2\nu]}\biggl{[}-\biggl{(}\frac{1-\zeta^{r}}{1-\zeta^{2}}\biggr{)}^{\nu}+\zeta^{2\nu}\biggl{(}\frac{1-\zeta^{r-2}}{1-\zeta^{2}}\biggr{)}^{\nu}\biggr{]}\\\
\quad-4(1+\zeta^{2})^{\nu}+4\zeta^{2\nu}.$

Now, analogously to (3.12), we will replace $\zeta^{2}$ with $z$, making
$\zeta^{2\nu}=z^{\nu}=1$ for all $z_{j}=\exp\bigl{(}i\tfrac{2\pi
j}{\nu}\bigr{)}$. Hence we may, and will replace in (3.13) the factor
$\zeta^{2\nu}$ with $1$ beforehand, and make the middle sum perfectly amenable
to another round of telescoping. Diagrammatically,

$\displaystyle\sum_{\text{even
}r\in[4,2(\nu-1)]}\\!\\!\\!\\!\\!\\!r\,\mathcal{F}_{r}(\zeta)\Longrightarrow$
$\displaystyle S_{2}(z):=2(\nu-1)\Bigl{(}\tfrac{1-z^{\nu}}{1-z}\Bigr{)}^{\nu}$
$\displaystyle-2\nu\Bigl{(}\tfrac{1-z^{\nu-1}}{1-z}\Bigr{)}^{\nu}-2(1+z)^{\nu}+4z^{\nu}.$

And

(3.14) $\sum_{\text{even }a\leq 0}[\zeta^{-a\nu}]\sum_{\text{even
}r\in[4,2(\nu-1)]}r\mathcal{F}_{r}(\zeta)\\\ =\sum_{\alpha\geq
0}[z^{\alpha\nu}]S_{2}(z)=\tfrac{2}{\nu}\sum_{j=0}^{\nu-1}\Bigl{[}(\nu-1)\Bigl{(}\tfrac{1-z_{j}^{\nu}}{1-z_{j}}\Bigr{)}^{\nu}-\nu\Bigl{(}\tfrac{1-z_{j}^{\nu-1}}{1-z_{j}}\Bigr{)}^{\nu}\Bigr{]}\\\
=2\bigl{(}1-\tfrac{1}{\nu}\bigr{)}-2(\nu-1)^{\nu}-2(\nu-1)(-1)^{\nu}.$

Combining (3.4), (3.12), and (3.14), we obtain

(3.15) $\mathcal{M}=2\nu\Bigl{(}1+\sum_{\text{even }a\leq
0}[\zeta^{-a\nu}]\sum_{\text{even
}r\in[4,2(\nu-1)]}\mathcal{F}_{r}(\zeta)\Bigr{)}\\\ -\sum_{\text{even }a\leq
0}[\zeta^{-a\nu}]\sum_{\text{even
}r\in[4,2(\nu-1)]}r\mathcal{F}_{r}(\zeta)=2\nu^{\nu-1}.$

Combining (3.4) and (3.15), we have proved

######  Lemma 3.2.

The total length of the in-cube segments of lines for even tuples $\mathbb{k}$
is $2\pi\nu^{\nu-3/2}$.

The reason that asymptotically only $\pi\nu^{-1/2}\mathcal{M}$ matters is that
the dominant contribution to $\mathbb{E}[Z_{n}]$ comes from thin, parallel,
cylinders in the cube $[-\pi,\pi]^{\nu}$, each enclosing its own line segment,
with the integrand asymptotically translation-invariant along the line
segment, and dependent only on the Euclidean distance from $\mathbb{x}$ to the
point on this segment with the same $\sum_{\alpha\in[\nu]}x_{\alpha}$.

(II) To prove this claim, our first step is to upper bound
$\Big{|}\mathbb{E}\bigl{[}f(\mathbb{x},X)\bigr{]}\Big{|}$ for $\mathbb{x}$’s
outside the lines

$\mathcal{L}_{\mathbb{k}}=\\{\mathbb{x}\in[-\pi,\pi]^{\nu}:y_{\alpha}(\mathbb{x})=k_{\alpha}\pi\\},\quad\sum_{\alpha}k_{\alpha}=0,\,\,k_{\alpha}\text{
are all even}.$

(We remind that $y_{\alpha}(\mathbb{x})=\nu
x_{\alpha}-\sum_{\beta}x_{\beta}$.) Start with

$\displaystyle\mathbb{E}[f(\mathbb{x},X)]:=\sum_{\alpha\in[\nu]}\phi(y_{\alpha}),\quad
y_{\alpha}=y_{\alpha}(\mathbb{x}),$ $\displaystyle\phi(y)$
$\displaystyle:=\mathbb{E}[e^{iyX}]=\tfrac{1}{M}\sum_{j\in[M]}e^{iyj}=\frac{e^{iy}(e^{iyM}-1)}{M(e^{iy}-1)},$

so that

(3.16)
$\Big{|}\mathbb{E}\bigl{[}f(\mathbb{x},X)\bigr{]}\Big{|}\leq\sum_{\alpha\in[\nu]}|\phi(y_{\alpha})|,\quad|\phi(y)|=\Big{|}\frac{\sin(My/2)}{M\sin(y/2)}\Big{|}.$

To proceed, given $|y|\leq 2\pi(\nu-1)$, define an even integer $k(y)$ by
condition:

$\min_{\text{even }k:|k|\leq 2(\nu-1)}|y-k\pi|=|y-k(y)\pi|.$

So, $k(y)\pi$ is an even multiple of $\pi$ closest to $y$ among all even
multiples $k\pi$’s with $|k|\leq 2(\nu-1)$. If $y$ is not an odd multiple of
$\pi$, then $k(y)$ is uniquely defined. So, $z(y):=y-k(y)\pi$ is uniquely
defined for almost all $y$, and for those $y$ we have $\phi(y)=\phi(z(y))$,
since $\phi$ is $2\pi$-periodic. Furthermore, $|z(y)|$ is the distance from
those $y$ to the set of even multiples of $\pi$, and as such it has a
continuous extension to all $y$. Therefore, $|z(y)|<\pi$ for almost all $y$.
Slightly abusing notation, from now on let $[-\pi,\pi]^{\nu}$ stand for the
original cube minus the set of $\mathbb{x}$ such that at least one
$y_{\alpha}(\mathbb{x})$ is an odd multiple of $\pi$. The discarded subset has
zero Lebesgue measure. Thus, for $\mathbb{x}$ in the (reduced) cube
$[-\pi,\pi]^{\nu}$, we have: for each $\alpha\in[\nu]$,
$z(y_{\alpha}(\mathbb{x}))=y_{\alpha}(\mathbb{x})-k(y_{\alpha}(\mathbb{x}))\pi$
is well defined, and denoting $z_{\alpha}=z(y_{\alpha}(x))$,
$k_{\alpha}=k(y_{\alpha}(x))$,

(3.17)
$\Big{|}\mathbb{E}\bigl{[}f(\mathbb{x},X)\bigr{]}\Big{|}\leq\sum_{\alpha\in[\nu]}|\phi(z_{\alpha})|,\quad\sum_{\alpha\in[\nu]}z_{\alpha}=-\pi\sum_{\alpha\in[\nu]}k_{\alpha}.$

So, we need to upper bound $|\phi(z_{\alpha})|$, $(\alpha\in[\nu])$, for each
of these subsets. Let $z\in[-\pi,\pi]$. Pick $b>1$. If $|\sin(z/2)|\geq b/M$,
then $|\phi(z)|\leq b^{-1}$. Also, $|\phi(z)|\leq\pi/(M|z|)$, because
$\sin\eta\geq 2\eta/\pi$ for $\eta\in(0,\pi/2)$. Now $|\sin(z/2)|\leq b/M$ if
and only if $|z|\leq b_{0}(M)/M$, where $b_{0}(M)$ is uniquely defined for
$M\geq b$ by the condition $\sin(b_{0}/(2M))=b/M$ with
$b_{0}/(2M)\in(0,\pi/2]$. A closer look shows that, given $b$,

(3.18) $b_{0}(M)=2b\bigl{[}1+O(b^{2}/M^{2})\bigr{]},\quad M\to\infty.$

Therefore $|\phi(z)|\leq b^{-1}$ if $|z|\geq b_{0}(M)/M$, implying that

(3.19) $|\phi(z)|\leq\min\bigl{\\{}\pi/(M|z|);b^{-1}\bigr{\\}},\quad\text{for
}|z|\geq b_{0}(M)/M.$

Consider $|z|\leq b_{0}(M)/M$, and set $z=\xi/M$, i.e., $|\xi|\leq
b_{0}(M)\sim 2b$ for large $M$. Then

$|\phi(z)|=\Big{|}\frac{\sin(\xi/2)}{M\sin(\xi/(2M))}\Big{|}=|\psi(\xi)|\cdot\bigl{|}1+O(\xi^{2}/M^{2})\bigr{|},\quad\psi(\xi):=\frac{\sin(\xi/2)}{\xi/2}.$

Since

$\psi^{2}(\xi)=\frac{1-\cos(\xi)}{\xi^{2}/2}=\sum_{j\geq
1}\tfrac{2(-1)^{j-1}}{(2j)!}\xi^{2(j-1)},$

which is an alternating series with decreasing terms for $|\xi|\leq
3\sqrt{2}$, we obtain that $\psi^{2}(\xi)\leq
1-\tfrac{\xi^{2}}{30},\quad(|\xi|\leq 3\sqrt{2}).$ Therefore,
$|\phi(z)|^{2}\leq 1-\tfrac{\xi^{2}}{31}$ for $|\xi|\leq 3\sqrt{2}$ and $M$
sufficiently large. Furthermore, $\psi^{2}(\xi)\leq\tfrac{2}{9}$ for
$|\xi|\geq 3\sqrt{2}$. So, given $b$, there exists $M_{1}(b)$ such that
$|\phi(z)|^{2}\leq\tfrac{1}{3}$ for $|\xi|\in[3\sqrt{2},b_{0}(M)]$ and $M\geq
M_{1}(b)$. Invoking (3.18), we have: there exists $M(b)\geq M_{1}(b)$ such
that for $M\geq M(b)$

(3.20) $|\phi(z)|^{2}\leq 1-\lambda(b)\xi^{2},\quad\xi:=Mz,\,|\xi|\leq
b_{0}(M),\quad\lambda:=\min\\{\tfrac{1}{31},\tfrac{1}{7b^{2}}\\}.$

It follows from (3.19) and (3.20) that $|\phi(z)|<1$ for $0<|z|\leq\pi$.
Consequently, by (3.16), (3.17), we have
$\Big{|}\mathbb{E}\bigl{[}f(\mathbb{x},X)\bigr{]}\Big{|}<\nu$, unless
$z_{\alpha}(\mathbb{x})\equiv 0$, $(\alpha\in[\nu])$. Moreover, using Cauchy-
Schwartz inequality, and $1-\gamma\leq e^{-\gamma}$, we obtain

######  Lemma 3.3.

Let $\mathbb{x}\in[-\pi,\pi]^{\nu}$. With $z_{\alpha}=z_{\alpha}(\mathbb{x})$,
denote $A(\mathbb{x})=\\{\alpha\in[\nu]:\,|z_{\alpha}|\leq b_{0}(M)/M\\}$,
$a(\mathbb{x}):=|A(\mathbb{x})|$, and define
$\xi_{\alpha}=\xi_{\alpha}(\mathbb{x}):=Mz_{\alpha}$, $\alpha\in[\nu]$. Given
$b>0$, for $M\geq M(b)$ there exists $\lambda=\lambda(b)>0$ such that

(3.21)
$\Big{|}\mathbb{E}\bigl{[}f(\mathbb{x},X)\bigr{]}\Big{|}^{2}\leq\nu\biggl{(}\sum_{\alpha\in
A(\mathbb{x})}|\phi(z_{\alpha})|^{2}+\sum_{\alpha\in
A^{c}(\mathbb{x})}\\!\\!\\!{\min}^{2}\bigl{\\{}\tfrac{\pi}{|\xi_{\alpha}|};b^{-1}\bigr{\\}}\biggr{)}\\\
\leq\nu\biggl{[}a(\mathbb{x})\exp\Bigl{(}-\tfrac{\lambda}{a(\mathbb{x})}\sum_{\alpha\in
A(\mathbb{x})}\xi_{\alpha}^{2}\Bigr{)}+\sum_{\alpha\in
A^{c}(\mathbb{x})}\\!\\!\\!{\min}^{2}\bigl{\\{}\tfrac{\pi}{|\xi_{\alpha}|};b^{-1}\bigr{\\}}\biggr{]}.$

if $A(\mathbb{x})\neq\emptyset$; otherwise the first term within the brackets
is set zero.

Note. Of course, a similar inequality holds for
$\Big{|}\mathbb{E}\bigl{[}f(\mathbb{x},X)\bigr{]}\Big{|}$, but with unsquared
${\min}\bigl{\\{}\tfrac{\pi}{|\xi_{\alpha}|};b^{-1}\bigr{\\}}$ and without
factor $\nu$ on the RHS. The inequality (3.21) has a useful advantage:
${\min}^{2}\bigl{\\{}\tfrac{\pi}{|\xi|};b^{-1}\bigr{\\}}$ is integrable on
$(-\infty,\infty)$. There is a price to pay though: to get a bound for
$\big{|}\mathbb{E}\bigl{[}f(\mathbb{x},X)\bigr{]}\big{|}^{n}$, and then to
integrate it over a peripheral part of the (reduced) cube $[-\pi,\pi]^{\nu}$
in question, we will have to raise both sides of the above inequality to the
$(n/2)$-th power. So, while working on upper bounds, we assume that $n$ is
even, and define $N=n/2$. For odd $n$ we would raise the RHS to the integer
power $N\\!:=\\!(n-1)/2$ and multiply the result by
$\nu\geq\Big{|}\mathbb{E}\bigl{[}f(\mathbb{x},X)\bigr{]}\Big{|}$.

The next step is to use Lemma 3.3 in order to upper bound contribution to
$\mathbb{E}[Z_{n}]$ coming from a vast part of the cube $[-\pi,\pi]^{\nu}$.

######  Lemma 3.4.

Define $D=D_{1}\cup D_{2}$,

$\displaystyle D_{1}$
$\displaystyle=\Bigl{\\{}\mathbb{x}\in[-\pi,\pi]^{\nu}:\,a(\mathbb{x})<\nu\Bigr{\\}},$
$\displaystyle D_{2}$
$\displaystyle=\biggl{\\{}\mathbb{x}\in[-\pi,\pi]^{\nu}:\,a(\mathbb{x})=\nu,\,\,\sum_{\alpha\in[\nu]}\xi^{2}_{\alpha}\geq\tfrac{\log^{2}n}{n}\biggr{\\}}.$

where $\xi_{\alpha}=Mz_{\alpha}$,
$z_{\alpha}=y_{\alpha}(\mathbb{x})-k_{\alpha}\pi$, $\min_{\text{even
}k}|y_{\alpha}(\mathbb{x})-k\pi|=|y_{\alpha}(\mathbb{x})-k_{\alpha}\pi|$.
(Notice at once that

$D^{c}=\biggl{\\{}\mathbb{x}\in[-\pi,\pi]^{\nu}:a(\mathbb{x})=\nu,\sum_{\alpha\in[\nu]}\xi_{\alpha}^{2}<\tfrac{\log^{2}n}{n}\biggr{\\}}\\\
\
=\biggl{\\{}\mathbb{x}\in[-\pi,\pi]^{\nu}:\sum_{\alpha\in[\nu]}\xi_{\alpha}^{2}<\tfrac{\log^{2}n}{n}\biggr{\\}},$

the last equality holding if $\tfrac{\log^{2}n}{n}\leq b_{0}(M)(=O(b))$.) For
$M=e^{O(n)}\to\infty$, and $N=n/2$, within factor $c(b)$ we have

(3.22)
$I_{n}:=\int\limits_{D}\big{|}\mathbb{E}\bigl{[}f(\mathbb{x},X)\bigr{]}\big{|}^{n}\,d\mathbb{x}\\\
\quad\leq\tfrac{\nu^{2N}}{M^{\nu-1}}\exp\Bigl{(}-\tfrac{\lambda\log^{2}N}{4\nu}\Bigr{)}+\left\\{\begin{aligned}
&\tfrac{(\nu e^{O(b^{-2})})^{N}}{M},&&\lim\tfrac{N}{\log M}<1,\\\
&\Bigl{(}\tfrac{\nu Ne^{O(b^{-2})}}{e\log M}\Bigr{)}^{N},&&\lim\tfrac{N}{\log
M}\in(1,\nu-1),\\\
&\tfrac{\bigl{(}\nu(\nu-1)e^{O(b^{-2})}\bigr{)}^{N}}{M^{\nu-1}},&&\lim\tfrac{N}{\log
M}>\nu-1.\end{aligned}\right.$

###### Proof.

(i) Consider $\mathbb{x}\in D_{1}$, so that $|A(\mathbb{x})|\in[0,\nu-1]$. Let
$I_{n,1}$ ($I_{n,1}(a)$ resp.) denote the contribution of $D_{1}$ (of
$D_{1}(a):=\\{\mathbb{x}\in D_{1}:|A(\mathbb{x})|=a\\}$ resp.) to
$\mathbb{E}[Z_{n}]$. For $a>0$ and $\mathbb{x}\in D_{1}(a)$, we use (3.21) and
a union-type bound to get

$\big{|}\mathbb{E}\bigl{[}f(\mathbb{x},X)\bigr{]}\big{|}^{n}\leq\nu^{N}\sum_{A\subset[\nu]:|A|=a}\biggl{[}a\exp\Bigl{(}\\!-\tfrac{\lambda}{a}\sum_{\alpha\in
A}\xi_{\alpha}^{2}\Bigr{)}\cdot I(\max_{\alpha\in A}|\xi_{\alpha}|\leq
b_{0})\\\ +\sum_{\beta\in A^{c}}\mathbb{I}(|\xi_{\beta}|\in[b_{0},\pi
M])\,{\min}^{2}\bigl{\\{}\tfrac{\pi}{|\xi_{\beta}|};b^{-1}\bigr{\\}}\\!\biggr{]}^{N},\quad\xi_{\gamma}=\xi_{\gamma}(\mathbb{x}),\,\,\gamma\in[\nu].$

Each of $\binom{\nu}{a}$ terms contributes equally to the integral of the RHS
over $[-\pi,\pi]^{\nu}$. Therefore, by multinomial formula with
$\mathbb{r}:=(r_{1},r_{a+1},\dots,r_{\nu})$,

(3.23)
$I_{n,1}(a)\leq\nu^{N}\binom{\nu}{a}\sum_{\|\mathbb{r}\|=N}\frac{N!}{r_{1}!\,r_{a+1}!\,\cdots
r_{\nu}!}\\\
\times\\!\\!\\!\int\limits_{\mathbb{x}\in[-\pi,\pi]^{\nu}}\biggl{[}a^{r_{1}}\exp\Bigl{(}-\tfrac{\lambda
r_{1}}{a}\sum_{\alpha\in[a]}\xi_{\alpha}^{2}\Bigr{)}\cdot
I(\max_{\alpha\in[a]}|\xi_{\alpha}|\leq b_{0})\\\
\times\prod_{\beta=a+1}^{\nu}\mathbb{I}(|\xi_{\beta}|\in[b_{0},\pi
M])\,{\min}^{2r_{\beta}}\bigl{\\{}\tfrac{\pi}{|\xi_{\beta}|};b^{-1}\bigr{\\}}\biggr{]}\,d\mathbb{x}.$

Recall that $\\{\xi_{\alpha}\\}=\\{\xi_{\alpha}(\mathbb{x})\\}$ is the
piecewise affine function, with the same matrix of rank $\nu-1$ on each of at
most $(2\nu-1)^{\nu}$ disjoint subsets forming a partition of
$[-\pi,\pi]^{\nu}$. To bound the integral in (3.23) we will switch from
$x_{\alpha}$ to $\xi_{\alpha}$ for all but a single component $x_{\mu}$,
choosing $\mu$ dependent on $\mathbb{r}$. No matter what $\mu$ is, the
Jacobian factor is the same, namely $(M^{\nu-1}\nu^{\nu-2})^{-1}$, on every
subset of the resulting partition. Let $\beta\in\\{a+1,\dots,\nu\\}$; if
$\xi_{\beta}$ is among the new variables, then–upon integration of
$\mathbb{r}$-th term–variable $\xi_{\beta}$ contributes a factor

(3.24) $2\int\limits_{b_{0}}^{\pi
M}\\!\\!\Bigl{(}\\!\min\bigl{\\{}\tfrac{\pi}{\xi};b^{-1}\\!\bigr{\\}}\\!\Bigr{)}^{2r_{\beta}}\\!\\!d\xi\\!\left\\{\begin{aligned}
\\!\\!&=\\!2(\pi M-b_{0})\\!\leq\\!2\pi M,&&r_{\beta}=0,\\\
\\!\\!&\leq\\!\tfrac{2(\pi
b-b_{0})}{b^{2r_{\beta}}}+\tfrac{2\pi}{b^{2r_{\beta}-1}(2r_{\beta}-1)}\\!\leq\\!\tfrac{4\pi}{b^{2r_{\beta}-1}},&&r_{\beta}\geq
1.\end{aligned}\right.$

We will control the factors for $r_{\beta}\geq 1$ by choosing $b$ large. The
case $r_{\beta}=0$ is the crux of the matter. Since $a\geq 1$, the number of
zeros in $\\{r_{a+1},\dots,r_{\nu}\\}$ can be as high as $\nu-a$, if $\mu\in
A$, thus leading to factor $M^{\nu-a}$ in a bound for the product of these
integrals. However, we may and will select $\mu\in A^{c}$, if $r_{\mu}$ is one
of the zeros in $\\{r_{a+1},\dots,r_{\nu}\\}$. For this choice,
$2\int_{b_{0}}^{\pi
M}\Bigl{(}\min\bigl{\\{}\tfrac{\pi}{\xi_{\mu}};b^{-1}\bigr{\\}}\Bigr{)}^{2r_{\mu}}d\xi_{\mu}\approx
2\pi M$ is replaced with $\int_{-\pi}^{\pi}1\,dx_{\mu}=2\pi$. Hence, the
worst-case bound becomes $M^{\nu-a-1}$ instead! Only if there are no zeros in
$\\{r_{a+1},\dots,r_{\nu}\\}$ do we choose $\mu\in A$.

Since $\mu\leq\nu$, we obtain

(3.25) $\displaystyle I_{n,1}(a)$
$\displaystyle\leq\nu^{N}\binom{\nu}{a}\tfrac{(2\nu-1)^{\nu}\nu}{M^{\nu-1}\nu^{\nu-2}}\sum_{\|\mathbb{r}\|=N}\frac{N!\,a^{r_{1}}}{r_{1}!\,r_{a+1}!\cdots
r_{\nu}!}\cdot J(\mathbb{r}),$ $\displaystyle J(\mathbb{r})$
$\displaystyle:=\int\limits_{x_{\mu},\,\\{\xi_{\gamma}\\}_{\gamma\neq\mu}}\\!\\!\\!\\!\exp\Bigl{(}-\tfrac{\lambda
r_{1}}{a}\sum_{\alpha\in[a]}\xi_{\alpha}^{2}\Bigr{)}\cdot
I(\max_{\alpha\in[a]}|\xi_{\alpha}|\leq b_{0})$
$\displaystyle\times\prod_{\beta=a+1}^{\nu}\mathbb{I}(|\xi_{\beta}|\in[b_{0},\pi
M])\,{\min}^{2r_{\beta}}\bigl{\\{}\tfrac{\pi}{|\xi_{\beta}|};b^{-1}\bigr{\\}}\,\,dx_{\mu}\prod_{\gamma\neq\mu}d\xi_{\gamma}.$

Let $\sigma(\mathbb{r})$ stand for the number of zeros in
$\\{r_{a+1},\dots,r_{\nu}\\}$. If $\sigma(\mathbb{r})>0$, then we choose
$\mu\in\\{a+1,\dots,\nu\\}$ such that $r_{\mu}=0$. Rather crudely, we have

$\int\limits_{\xi_{1},\dots,\xi_{a}}\\!\\!\\!\\!\exp\Bigl{(}-\tfrac{\lambda
r_{1}}{a}\sum_{\alpha\in[a]}\xi_{\alpha}^{2}\Bigr{)}\cdot
I(\max_{\alpha\in[a]}|\xi_{\alpha}|\leq
b_{0})\prod_{\alpha\in[a]}d\xi_{\alpha}\leq(2b_{0})^{a}=O(b^{a}).$

Furthermore, using (3.24) and

$\sum_{\beta\in[a+1,\,\nu]:\,r_{\beta}>0}(2r_{\beta}-1)=2(N-r_{1})-\bigl{[}\nu-a-\sigma(\mathbb{r})\bigr{]},$

we bound

$\int\limits_{x_{\mu},\,\\{\xi_{\gamma}\\}_{\mu\neq\gamma>a}}\prod_{\beta=a+1}^{\nu}\mathbb{I}(|\xi_{\beta}|\in[b_{0},\pi
M])\,{\min}^{2r_{\beta}}\bigl{\\{}\tfrac{\pi}{|\xi_{\beta}|};b^{-1}\bigr{\\}}\,\,dx_{\mu}\prod_{\mu\neq\gamma>a}d\xi_{\gamma}\\\
\leq 2\pi\cdot 2^{\nu-a-1}\prod_{\mu\neq\gamma>a}\int\limits_{b_{0}}^{\pi
M}\\!\\!\Bigl{(}\\!\min\bigl{\\{}\tfrac{\pi}{\xi};b^{-1}\\!\bigr{\\}}\\!\Bigr{)}^{2r_{\gamma}}\\!\\!d\xi\\!\\\
\leq 2^{\nu-a}\pi(\pi
M)^{\sigma(\mathbb{r})-1}(4\pi)^{\nu-a-\sigma(\mathbb{r})}b^{-2(N-r_{1})+(\nu-a-\sigma(\mathbb{r}))}\\\
\leq c_{1}M^{\sigma(\mathbb{r})-1}b^{-2(N-r_{1})}\leq
c_{1}M^{\nu-a-1}b^{-2(N-r_{1})}.\\\ $

Here $c_{1}$, and $c_{j}$ below depend on $b$ only. So, $J(\mathbb{r})\leq
c_{2}M^{\nu-a-1}b^{-2(N-r_{1})}$ if $\sigma(\mathbb{r})>0$. Likewise, if
$\sigma(\mathbb{r})=0$ then
$J(\mathbb{r})\\!\leq\\!c_{3}b^{-2(N-r_{1})}\\!\leq\\!c_{3}M^{\nu-a-1}b^{-2(N-r_{1})}$,
since $\nu>a$. Therefore $J(\mathbb{r})\leq c_{4}M^{\nu-a-1}b^{-2(N-r_{1})}$.
Plugging this bound into (3.25) we have: for $a\in[1,\nu-1]$,

(3.26)
$I_{n,1}(a)\leq\tfrac{c_{5}\nu^{N}}{M^{\nu-1}}\sum_{\|\mathbb{r}\|=N}\frac{M^{\nu-a-1}N!}{\prod\limits_{s}r_{s}!}\cdot
a^{r_{1}}b^{-2(N-r_{1})}\\\ =\tfrac{c_{5}\nu^{N}}{M^{\nu-1}}\cdot
M^{\nu-a-1}\sum_{\|\mathbb{r}\|=N}\frac{N!}{\prod\limits_{s}r_{s}!}\,a^{r_{1}}\prod_{s>a}b^{-2r_{s}}\\\
\leq\tfrac{c_{5}\nu^{N}}{M^{\nu-1}}\cdot M^{\nu-a-1}\bigl{(}a+\nu
b^{-2}\bigr{)}^{N}.$

For $a=0$, instead of the bound (3.23) we get

$\big{|}\mathbb{E}\bigl{[}f(\mathbb{x},X)\bigr{]}\big{|}^{n}\leq\nu^{N}\biggl{(}\sum_{\beta=1}^{\nu}\mathbb{I}(|\xi_{\beta}|\in[b_{0},\pi
M])\,{\min}^{2}\bigl{\\{}\tfrac{\pi}{|\xi_{\beta}|};b^{-1}\bigr{\\}}\\!\biggr{)}^{N}\\\
=\nu^{N}\sum_{\|\mathbb{r}\|=N}\frac{N!}{r_{1}!\cdots
r_{\nu}!}\prod_{\beta=1}^{\nu}\mathbb{I}(|\xi_{\beta}|\in[b_{0},\pi
M])\,{\min}^{2r_{\beta}}\bigl{\\{}\tfrac{\pi}{|\xi_{\beta}|};b^{-1}\bigr{\\}},$

$\mathbb{r}=(r_{1},\dots,r_{\nu})$. And, analogously to (3.26), we obtain

(3.27) $I_{n,1}(0)\leq\tfrac{c_{6}\nu^{N}}{M^{\nu-1}}\cdot M^{\nu-2}b^{-2N}.$

Why $M^{\nu-2}$? Because $\sigma(\mathbb{r})\leq\nu-1$, and if
$\sigma(\mathbb{r})=\nu-1$, then we select $\mu$ for which $r_{\mu}=0$.

Adding (3.26) and (3.27), we get

(3.28)
$I_{n,1}\leq\tfrac{c_{7}\nu^{N}}{M}\biggl{(}b^{-2N}+\sum_{a=1}^{\nu-1}M^{-a+1}(a+\nu
b^{-2})^{N}\biggr{)}.$

Let us simplify (3.28). For $n\to\infty$, the (log-concave) function
$\psi(a):=M^{-a+1}\bigl{(}a+\tfrac{\nu}{b^{2}})^{N}$, $(a\in[1,\nu-1])$,
attains its unique maximum at

$a(\nu)=\left\\{\begin{aligned} &1,&&\lim\tfrac{N}{\log
M}<1+\tfrac{\nu}{b^{2}},\\\ &\tfrac{N}{\log
M}-\tfrac{\nu}{b^{2}},&&\lim\tfrac{N}{\log
M}\in(1+\tfrac{\nu}{b^{2}},\nu-1+\tfrac{\nu}{b^{2}}),\\\
&\nu-1,&&\lim\tfrac{N}{\log M}>\nu-1+\tfrac{\nu}{b^{2}}.\end{aligned}\right.$

Consequently

$\psi(a(\nu))=\left\\{\begin{aligned}
&\bigl{(}e^{O(b^{-2})}\bigr{)}^{N},&&\lim\tfrac{N}{\log
M}<1+\tfrac{\nu}{b^{2}},\\\ &M\Bigl{(}\tfrac{Ne^{O(b^{-2})}}{e\log
M}\Bigr{)}^{N},&&\lim\tfrac{N}{\log
M}\in(1+\tfrac{\nu}{b^{2}},\nu-1+\tfrac{\nu}{b^{2}}),\\\
&M^{-\nu+2}\bigl{(}(\nu-1)e^{O(b^{-2})}\bigr{)}^{N},&&\lim\tfrac{N}{\log
M}>\nu-1+\tfrac{\nu}{b^{2}}.\end{aligned}\right.$

The sum in (3.28) is below $b^{-2N}+\nu\psi(a(\nu))$, and $b$ can be chosen
arbitrarily large. So, for $M=e^{O(n)}\to\infty$ and $b$ sufficiently large,
we have

(3.29) $I_{n,1}\leq c_{8}\cdot\left\\{\begin{aligned} &\tfrac{\bigl{(}\nu
e^{O(b^{-2})}\bigr{)}^{N}}{M},&&\lim\tfrac{N}{\log M}<1,\\\
&\Bigl{(}\tfrac{\nu Ne^{O(b^{-2})}}{e\log M}\Bigr{)}^{N},&&\lim\tfrac{N}{\log
M}\in(1,\nu-1),\\\
&\tfrac{\bigl{(}\nu(\nu-1)e^{O(b^{-2})}\bigr{)}^{N}}{M^{\nu-1}},&&\lim\tfrac{N}{\log
M}>\nu-1.\end{aligned}\right.$

(ii) Suppose $\mathbb{x}\in D_{2}$. Let $I_{n,2}$ denote the contribution of
$D_{2}$ to $\mathbb{E}[Z_{n}]$. We switch from $x_{\alpha}$ to $\xi_{\alpha}$
for all but a single $x_{\mu}$ such that
$|\xi_{\mu}|=\min_{\alpha}|\xi_{\alpha}|$. So, here the cube
$[-\pi,\pi]^{\nu}$ is a finite disjoint union of subsets, and the choice of
the new variables depends on a subset in such a way that the condition
$\sum_{a\in[\nu]}\xi_{\alpha}^{2}\geq\tfrac{\log^{2}n}{n}$ implies that
$\sum_{a\neq\mu}\xi_{\alpha}^{2}\geq\tfrac{(\nu-1)\log^{2}n}{\nu
n}\geq\tfrac{\log^{2}N}{4N}$.

Analogously to $I_{n,1}$, by Lemma 3.3 we have

$I_{n,2}\leq\tfrac{c_{1}\nu^{2N}}{M^{\nu-1}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\int\limits_{\sum_{\alpha=1}^{\nu-1}\xi_{\alpha}^{2}\geq\tfrac{\log^{2}N}{4N}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\exp\Bigl{(}-\tfrac{\lambda
N}{\nu}\sum_{\alpha=1}^{\nu-1}\xi_{\alpha}^{2}\Bigr{)}\,\prod_{\alpha=1}^{\nu-1}d\xi_{\alpha}.$

Here, and below, $c_{j}$ is independent of $b$ and $\lambda=\lambda(b)$. Using
spherical coordinates, and denoting
$\zeta_{0}=\bigl{(}\tfrac{\lambda}{4\nu}\bigr{)}^{1/2}\log N$, we bound the
last integral by

$\displaystyle c_{2}\\!\\!\\!\int\limits_{\rho\geq\frac{\log
N}{\sqrt{4N}}}\\!\\!\\!\exp\Bigl{(}-\tfrac{\lambda
N}{\nu}\rho^{2}\Bigr{)}\rho^{\nu-2}\,d\rho$ $\displaystyle=c_{3}\,(\lambda
N)^{-(\nu-1)/2}\\!\\!\int\limits_{\zeta\geq\zeta_{0}}e^{-\zeta^{2}/2}\zeta^{\nu-2}\,d\zeta$
$\displaystyle\leq c_{4}\,\lambda^{-1}N^{-(\nu-1)/2}(\log
N)^{\nu-3}\exp\Bigl{(}-\tfrac{\lambda\log^{2}N}{4\nu}\Bigr{)}.$

The last bound follows from integrating the LHS integral (call it $I$) by
parts once, and bounding the residual integral by
$I\cdot(\nu-3)\zeta_{0}^{-2}$. We conclude that

(3.30) $I_{n,2}\leq\tfrac{c_{5}\,\nu^{2N}}{\lambda
M^{\nu-1}}\exp\Bigl{(}-\tfrac{\lambda\log^{2}N}{4\nu}\Bigr{)}.$

Adding (3.29) and (3.30) we complete the proof of Lemma 3.4. ∎

(III) So, it remains to sharply evaluate an asymptotic contribution to the
integral

$\mathbb{E}\bigl{[}Z_{n}\bigr{]}=\\!\frac{1}{(2\pi)^{\nu}}\\!\\!\\!\int\limits_{\mathbb{x}\in[-\pi,\pi]^{\nu}}\\!\\!\\!\mathbb{E}^{n}\bigl{[}f(\mathbb{x},X)\bigr{]}d\mathbb{x},$

that comes from $C:=[-\pi,\pi]^{\nu}\setminus D$, or more explicitly from
$\mathbb{x}$’s in the (reduced) cube $[-\pi,\pi]^{\nu}$ with
$\sum_{\alpha}\xi_{\alpha}^{2}<n^{-1}\log^{2}n$, where
$\xi_{\alpha}=\xi_{\alpha}(\mathbb{x})$ are uniquely defined by

$\xi_{\alpha}=Mz_{\alpha},\quad
z_{\alpha}=y_{\alpha}(\mathbb{x})-k_{\alpha}(\mathbb{x})\pi,\quad|z_{\alpha}|=\min_{\text{even
}k}|y_{\alpha}(\mathbb{x})-k\pi|.$

That is, $\\{k_{\alpha}(\mathbb{x})\\}$ is an even tuple. To begin,

$\displaystyle\sum_{\alpha}\bigl{(}y_{\alpha}(\mathbb{x})-k_{\alpha}(\mathbb{x})\pi\bigr{)}^{2}=M^{-2}\sum_{\alpha}\xi_{\alpha}^{2}<M^{-2}n^{-1}\log^{2}n$
$\displaystyle\qquad\qquad\Longrightarrow\sum_{\alpha}k_{\alpha}(\mathbb{x})=0\Longrightarrow\sum_{\alpha}\xi_{\alpha}=0,$

if $n$ is large enough. Indeed $\sum_{\alpha}y_{\alpha}(\mathbb{x})\equiv 0$;
so if $\sum_{\alpha}k_{\alpha}(\mathbb{x})\neq 0$, then
$\Big{|}\sum_{\alpha}k_{\alpha}(\mathbb{x})\Big{|}\geq 2$, and for large $n$
we have a contradiction:

$4\pi^{2}\leq\Bigl{|}\sum_{\alpha}(y_{\alpha}(\mathbb{x})-k_{\alpha}(\mathbb{x})\pi)\Bigr{|}^{2}\leq\nu\sum_{\alpha}(y_{\alpha}(\mathbb{x})-k_{\alpha}(\mathbb{x})\pi)^{2}\leq\tfrac{\nu\log^{2}n}{M^{2}n}.$

Conversely, if $\\{y_{\alpha}(\mathbb{x})\\}$ and an even tuple
$\mathbb{k}=\\{k_{\alpha}\\}$, $\bigl{(}\sum_{\alpha}k_{\alpha}=0\bigr{)}$,
satisfy$\sum_{\alpha}\bigl{(}y_{\alpha}(\mathbb{x})-k_{\alpha}\pi\bigr{)}^{2}<M^{-2}n^{-1}\log^{2}n$,
then $\sum_{\alpha}\xi_{\alpha}^{2}\leq n^{-1}\log^{2}n$. Moreover,
$\xi_{\alpha}=M(y_{\alpha}(\mathbb{x})-k_{\alpha}\pi)$, if $n$ is large.
Indeed, $\xi_{\alpha}=M(y_{\alpha}(\mathbb{x})-k_{\alpha}^{\prime}\pi)$, where
$|y_{\alpha}(\mathbb{x})-k_{\alpha}^{\prime}\pi)|=\min_{\text{even
}\kappa}|y_{\alpha}(\mathbb{x})-\kappa\pi|$, and the conditions

$\sum_{\alpha}\bigl{(}y_{\alpha}(\mathbb{x})-k_{\alpha}\pi\bigr{)}^{2},\quad\sum_{\alpha}\bigl{(}y_{\alpha}(\mathbb{x})-k_{\alpha}^{\prime}\pi\bigr{)}^{2}<M^{-2}n^{-1}\log^{2}n,$

combined with the triangle inequality, imply that
$\|\mathbb{k}-\mathbb{k}^{\prime}\|\leq\tfrac{2\log n}{\pi Mn^{1/2}}$.

Therefore, $C=\cup_{\mathbb{k}}C_{\mathbb{k}}$ where
$\mathbb{k}=\\{k_{\alpha}\\}$, with even $k_{\alpha}$ adding up to $0$, and

$C_{\mathbb{k}}:=\Bigl{\\{}\mathbb{x}\in[-\pi,\pi]^{\nu}:\sum_{\alpha}\bigl{(}y_{\alpha}(\mathbb{x})-k_{\alpha}\pi\bigr{)}^{2}<M^{-2}n^{-1}\log^{2}n\Bigr{\\}}.$

And, for large $n$, by the triangle inequality
$C_{\mathbb{k}_{1}}\cap\,C_{\mathbb{k}_{2}}=\emptyset$ if
$\mathbb{k}_{1}\neq\mathbb{k}_{2}$.

Consider the line $\mathcal{L}_{\mathbb{k}}$ given by
$y_{\alpha}(\mathbb{x})=k_{\alpha}\pi$, $(\alpha\in[\nu])$, for any such tuple
$\mathbb{k}$. (In the part (I) we enumerated all $\mathcal{L}_{\mathbb{k}}$
that contain interior points of $[-\pi,\pi]^{\nu}$.) A generic
$\mathcal{L}_{\mathbb{k}}$ is given by its parametric equation

(3.31) $x_{\alpha}(t)=\nu^{-1}(t+k_{\alpha}\pi),\quad\alpha\in[\nu].$

The lines are parallel to each other, running in the direction of
$\mathbb{e}=(1,\dots,1)$, and crossing at $90$ degrees each of the
(hyper)planes $\sum_{\alpha\in[\nu]}x_{\alpha}=t$, with
$\mathbb{x}(t):=\\{x_{\alpha}(t)\\}_{\alpha\in[\nu]}$ being the intersection
point. Using
$x_{\alpha}=\nu^{-1}\Bigl{(}\sum_{\beta}x_{\beta}+y_{\alpha}(\mathbb{x})\Bigr{)},$
and (3.31), we obtain: if $\mathbb{x}=\\{x_{\alpha}\\}\in C_{\mathbb{k}}$
then, with $t:=\sum_{\alpha}x_{\alpha}$,

(3.32) $\displaystyle x_{\alpha}-x_{\alpha}(t)$
$\displaystyle=\tfrac{y_{\alpha}(\mathbb{x})-k_{\alpha}\pi}{\nu}=\tfrac{\xi_{\alpha}(\mathbb{x})}{M\nu}$
$\displaystyle\Longrightarrow\|\mathbb{x}-\mathbb{x}(t)\|^{2}=\tfrac{1}{(M\nu)^{2}}\sum_{\alpha}\xi_{\alpha}^{2}(\mathbb{x})\leq\tfrac{\log^{2}n}{(M\nu)^{2}n}.$

Conversely, if $t=\sum_{\alpha}x_{\alpha}$, then
$\|\mathbb{x}-\mathbb{x}(t)\|^{2}\leq\tfrac{\log^{2}n}{(M\nu)^{2}n}$ implies
that $\mathbb{x}\in C_{\mathbb{k}}$.

Consider a $\nu$-dimensional cylinder $\mathcal{C}_{\mathbb{k}}$ enclosing the
line $\mathcal{L}_{\mathbb{k}}$, such that each of its cross-sections formed
by planes $\sum_{a}x_{\alpha}=t$ orthogonal to $\mathcal{L}_{\mathbb{k}}$ is a
$(\nu-1)$-dimensional (hyper)sphere in that plane, of radius
$r_{n}:=(M\nu)^{-1}n^{-1/2}\log n$, which is centered at the common point
$\mathbb{x}(t)$ of the plane and the line $\mathcal{L}_{\mathbb{k}}$. We
denote the sphere $\mathcal{S}(\mathbb{x}(t),r_{n})$.

The above discussion means the following. If $\mathcal{L}_{\mathbb{k}}$
contains interior points of $[-\pi,\pi]^{\nu}$, then
$C_{\mathbb{k}}=\mathcal{C}_{\mathbb{k}}\cap[-\pi,\pi]^{\nu}$. And shortly we
will see that the contribution of $C_{\mathbb{k}}$ to $\mathbb{E}[Z_{n}]$ is
of exact order $L(\mathbb{k})\nu^{n}M^{-\nu+1}n^{-\tfrac{\nu-1}{2}},$ where
$L(\mathbb{k})\geq 2\pi\nu^{-1/2}$ is the length of line segment of
$\mathcal{L}_{\mathbb{k}}$ in $[-\pi,\pi]^{\nu}$, see (3.4).

In the part (I) we proved that if $\mathcal{L}_{\mathbb{k}}$ contains no
interior points of $[-\pi,\pi]^{\nu}$, then $\mathcal{L}_{\mathbb{k}}$ may
only touch $[-\pi,\pi]^{\nu}$ at a single point
$\mathbb{x}_{\mathbb{k}}=\\{x_{\mathbb{k},\alpha}\\}$, such that
$x_{\mathbb{k},\alpha_{1}}=\pi$ and $x_{\mathbb{k},\alpha_{2}}=-\pi$ for some
$\alpha_{1},\alpha_{2}\in[\nu]$. In this case, $C_{\mathbb{k}}$ is the union
of the parallel line segments
$\mathbb{x}(t)=\tilde{\mathbb{x}}_{\mathbb{k}}+t\mathbb{e}\in[-\pi,\pi]^{\nu}$,
where
$\sum_{\alpha}\tilde{\mathbb{x}}_{\mathbb{k},\alpha}=\sum_{\alpha}x_{\mathbb{k},\alpha}$,
and $\|\tilde{\mathbb{x}}_{\mathbb{k}}-\mathbb{x}_{\mathbb{k}}\|\leq r_{n}$.
Using $x_{\mathbb{k},\alpha_{1}}=\pi$ and $x_{\mathbb{k},\alpha_{2}}=-\pi$ we
obtain that
$t\in[x_{\mathbb{k},\alpha_{2}}-\tilde{x}_{\mathbb{k},\alpha_{2}},x_{\mathbb{k},\alpha_{1}}-\tilde{x}_{\mathbb{k},\alpha_{1}}]$.
Since $|y|$ is convex, we see then that $|t|\leq r_{n}$. So, $C_{\mathbb{k}}$
is enclosed in a sub-cylinder of $\mathcal{C}_{\mathbb{k}}$ sandwiched between
two parallel cross-sections, for
$t_{1}=\sum_{\alpha}x_{\mathbb{k},\alpha}-r_{n}$ and
$t_{2}=\sum_{\alpha}x_{\mathbb{k},\alpha}+r_{n}$, that are at distance
$O(r_{n})$ from each other. Consequently, contribution of $C_{\mathbb{k}}$ to
$\mathbb{E}[Z_{n}]$ is at most of order
$r_{n}\nu^{n}M^{-\nu+1}n^{-\tfrac{\nu-1}{2}}$. And we know that the total
number of the points $\mathbb{x}_{\mathbb{k}}$ is $\nu(2\nu-1)^{\nu}$, at
most. So, the contribution to $\mathbb{E}[Z_{n}]$ from the sets
$C_{\mathbb{k}}$ with the lines $\mathcal{L}_{\mathbb{k}}$ merely touching the
cube $[-\pi,\pi]^{\nu}$ is relatively negligible as $n\to\infty$. Therefore,
we focus on $C_{\mathbb{k}}$ with lines $\mathcal{L}_{\mathbb{k}}$ enumerated
in (I).

For $\mathbb{x}\in\mathcal{S}(\mathbb{x}(t),r_{n})$, we set
$\xi_{\alpha}=M(y_{\alpha}(\mathbb{x})-k_{\alpha}\pi)=M\nu(x_{\alpha}-x_{\alpha}(t))$,
so that $\sum_{\alpha}\xi_{\alpha}^{2}\leq n^{-1}\log^{2}n$ and
$\sum_{\alpha}\xi_{\alpha}=0$. Then

$\mathbb{E}\bigl{[}f(\mathbb{x},X)\bigr{]}=\sum_{\alpha\in[\nu]}\mathbb{E}\bigl{[}e^{iy_{\alpha}(\mathbb{x})X}\bigr{]}=\sum_{\alpha\in[\nu]}\mathbb{E}\bigl{[}e^{i\xi_{\alpha}M^{-1}X}\bigr{]}\\\
=\sum_{\alpha\in[\nu]}\Bigl{[}1+i\tfrac{\mathbb{E}[X]}{M}\xi_{\alpha}-\tfrac{\mathbb{E}[X^{2}]}{2M^{2}}\xi_{\alpha}^{2}+O\bigl{(}|\xi_{\alpha}|^{3}\tfrac{\mathbb{E}[X^{3}]}{M^{3}}\bigr{)}\Bigr{]}\\\
=\nu-\tfrac{\mathbb{E}[X^{2}]}{2M^{2}}\sum_{\alpha\in[\nu]}\xi_{\alpha}^{2}+O\Bigl{(}\tfrac{\mathbb{E}[X^{3}]}{M^{3}}\sum_{\alpha\in[\nu]}|\xi_{\alpha}|^{3}\Bigr{)}\\\
=\nu\exp\Bigl{(}-\tfrac{c_{\scriptscriptstyle
M}}{2\nu}\sum_{\alpha\in[\nu]}\xi_{\alpha}^{2}+O(n^{-3/2}\log^{3}n)\Bigr{)}\\\
=\nu\exp\Bigl{(}-\tfrac{c_{\scriptscriptstyle
M}}{2\nu}(M\nu)^{2}\|\mathbb{x}-\mathbb{x}(t)\|^{2}+O(n^{-3/2}\log^{3}n)\Bigr{)};$

here $c_{\scriptscriptstyle M}=\tfrac{\mathbb{E}[X^{2}]}{M^{2}}$,
$t=\sum_{\alpha}x_{\alpha}$. So, uniformly for
$\mathbb{x}\in\mathcal{S}(\mathbb{x}(t),r_{n})$, we have

(3.33)
$\mathbb{E}^{n}\bigl{[}f(\mathbb{x},X)\bigr{]}=\nu^{n}\exp\Bigl{(}-\tfrac{c_{\scriptscriptstyle
M}n}{2\nu}(M\nu)^{2}\|\mathbb{x}-\mathbb{x}(t)\|^{2}+O(n^{-1/2}\log^{3}n)\Bigr{)}.$

With $\rho_{n}:=n^{-1/2}\log n\to 0$, admissibility issue arises when
$|t-t_{j}|=O(M^{-1}\rho_{n})$, where $t_{1}:=-\pi(\nu+\min k_{\alpha})$ and
$t_{2}:=\pi(\nu-\max k_{\alpha})$ are the endpoints of $t$’s range. Ignoring
this lack of complete homogeneity, and using orthogonality of
$\mathcal{S}(\mathbb{x}(t),r_{n})$ and $\mathcal{L}_{\mathbb{k}}$, we replace
the contribution of $C_{\mathbb{k}}$ to the integral representing $E[Z_{n}]$
with the integral of the RHS in (3.33) over the sphere
$\mathcal{S}(\mathbb{x}(t),r_{n})$, times $C_{\mathbb{k}}$’s length

$L(\mathbb{k}):=\|\mathbb{x}(t_{2})-\mathbb{x}(t_{1})\|=\nu^{-1/2}\pi\bigl{(}2\nu+\min_{\alpha}k_{\alpha}-\max_{\alpha}k_{\alpha}\bigr{)}\geq
2\pi\nu^{-1/2},$

see (3.4). So, introducing $\mathcal{S}(\mathbb{0},\rho)$, the
$(\nu-1)$-dimensional sphere of radius $\rho$, centered at the origin
$\mathbb{0}\in E^{\nu-1}$, and using

$\text{Volume}\bigl{(}\mathcal{S}(\mathbb{0},\rho)\bigr{)}=\tfrac{\pi^{\frac{\nu-1}{2}}\rho^{\nu-1}}{\Gamma(\tfrac{\nu-1}{2}+1)},$

we obtain: within factor $1+o(1)$, contribution of $C_{\mathbb{k}}$ to
$\mathbb{E}[Z_{n}]$ is

$\frac{\nu^{n}L(\mathbb{k})}{(2\pi)^{\nu}(M\nu)^{\nu-1}}\int_{\mathcal{S}(\mathbb{0},\rho_{n})}e^{-\frac{c_{M}n}{2\nu}\rho^{2}}\,dV\\\
=\frac{\nu^{n}L(\mathbb{k})}{(2\pi)^{\nu}(M\nu)^{\nu-1}}\cdot\frac{\pi^{\tfrac{\nu-1}{2}}\tfrac{\nu-1}{2}}{\Gamma\bigl{(}\tfrac{\nu-1}{2}+1\bigr{)}}\bigl{(}\tfrac{2\nu}{c_{M}n}\bigr{)}^{\tfrac{\nu-1}{2}}\int_{0}^{\tfrac{c_{M}n\rho_{n}^{2}}{\nu}}e^{-z}z^{\tfrac{\nu-1}{2}-1}\,dz\\\
=(1+o(1))\frac{\nu^{n}}{M^{\nu-1}}\cdot\frac{L(\mathbb{k})}{2\pi(2\pi\nu
c_{\scriptscriptstyle M}n)^{\tfrac{\nu-1}{2}}}.$

Indeed, the second line integral is asymptotic to $\Gamma(\tfrac{\nu-1}{2})$,
and for the third line we used $\Gamma(z+1)=z\Gamma(z)$. (This estimate
confirms our earlier claim concerning the contribution of every such
$C_{\mathbb{k}}$ to $\mathbb{E}[Z_{n}]$.) Combining the estimate with Lemmas
3.2 and 3.4, we have:

(3.34)
$\mathbb{E}\bigl{[}Z_{n}\bigr{]}=(1+o(1))\frac{\nu^{n}}{M^{\nu-1}}\cdot\frac{\nu^{\nu-3/2}}{(2\pi\nu
c_{\scriptscriptstyle M}n)^{\frac{\nu-1}{2}}}+O(\mathcal{R}_{n}),\\\ $

where (with $N=n/2$)

(3.35)
$\mathcal{R}_{n}=\tfrac{\nu^{n}}{M^{\nu-1}}\exp\Bigl{(}-\tfrac{\lambda\log^{2}N}{4\nu}\Bigr{)}\\\
+\left\\{\begin{aligned} &\tfrac{\bigl{(}\nu
e^{O(b^{-2})}\bigr{)}^{N}}{M},&&\lim\tfrac{N}{\log M}<1,\\\
&\Bigl{(}\tfrac{\nu Ne^{O(b^{-2})}}{e\log M}\Bigr{)}^{N},&&\lim\tfrac{N}{\log
M}\in(1,\nu-1),\\\
&\tfrac{\bigl{(}\nu(\nu-1)e^{O(b^{-2})}\bigr{)}^{N}}{M^{\nu-1}},&&\lim\tfrac{N}{\log
M}>\nu-1.\end{aligned}\right.\\\ $

We will refer to this vertical stack as top, middle, and bottom remainders.

(IV) Let us have a close look at the estimate above.

(a) $\nu=3$. Suppose that $\lim\tfrac{N}{\log M}\in\bigl{(}\tfrac{1}{\log
3},\infty\bigr{)}\setminus\\{1,2\\}$. Then $\tfrac{3^{2N}}{M^{2}}$ grows
exponentially fast, hence
$\tfrac{3^{2N}}{M^{2}}\gg\tfrac{\bigl{(}3e^{O(b^{-2})}\bigr{)}^{N}}{M}$ (top
remainder term in (3.35)), for $b$ chosen sufficiently large. So, if
$\lim\tfrac{N}{\log M}\in\bigl{(}\tfrac{1}{\log 3},1\bigr{)}$, then the above
formula for $\mathbb{E}\bigl{[}Z_{n}\bigr{]}$ implies that

(3.36)
$\mathbb{E}\bigl{[}Z_{n}\bigr{]}=(1+o(1))\frac{\nu^{n}}{M^{\nu-1}}\cdot\frac{\nu^{\nu-3/2}}{(2\pi\nu
c_{\scriptscriptstyle M}n)^{\frac{\nu-1}{2}}}\Big{|}_{\nu=3}\to\infty.$

Let $\lim\tfrac{N}{\log M}\in(1,2)$; (3.36) continues to hold for $b$ large
enough, provided that

$\tfrac{3^{2N}}{M^{2}}\gg\Bigl{(}\tfrac{\nu Ne^{O(b^{-2})}}{e\log
M}\Bigr{)}^{N},$

middle remainder in (3.35). This inequality holds if $\rho:=\lim\tfrac{\log
M}{N}\in(0.5,1)$ satisfies $(3e^{-\rho})^{2}>\tfrac{3}{e\rho}$. And it is
indeed so, since

$\min\\{9\tau e^{-2\tau}:\,\tau\in[1/2,1]\\}=\tfrac{9}{e^{2}}>\tfrac{3}{e}.$

Let $\lim\tfrac{N}{\log M}\in(2,\infty)$; (3.36) again holds for $b$ large
enough, since $3^{n}\gg 6^{N}$, see bottom remainder in (3.35). On the other
hand, if $\lim\tfrac{N}{\log M}<\tfrac{1}{\log 3}$, then $\lim\tfrac{N}{\log
M}<1$, and using top remainder from (3.35) we see that
$\mathbb{E}\bigl{[}Z_{n}\bigr{]}=O\Bigl{(}\tfrac{(3e^{O(b^{-2})})^{N}}{M}\Bigr{)}\to
0$, for $b$ sufficiently large.

(b) Let now $\nu>3$. (3.36) holds if $\lim\tfrac{N}{\log M}>\nu-1$. Indeed, by
(3.35),

$\displaystyle\quad\mathcal{R}_{n}=\tfrac{\nu^{2N}}{M^{\nu-1}}\exp\Bigl{(}-\tfrac{\lambda\log^{2}N}{4\nu}\Bigr{)}+\tfrac{\bigl{(}\nu(\nu-1)e^{O(b^{-2})}\bigr{)}^{N}}{M^{\nu-1}},$
$\displaystyle\tfrac{\nu^{2N}}{M^{\nu-1}}=\exp\Bigl{[}2\log
M\cdot\log\nu\cdot\bigl{(}\tfrac{N}{\log
M}-\tfrac{\nu-1}{2\log\nu}\bigr{)}\Bigr{]}\to\infty,$
$\displaystyle\qquad\,\,\,\frac{\tfrac{\nu^{2N}}{M^{\nu-1}}}{\tfrac{\bigl{(}\nu(\nu-1)e^{O(b^{-2})}\bigr{)}^{N}}{M^{\nu-1}}}=\bigl{(}\tfrac{\nu}{\nu-1}e^{O(b^{-2})}\bigr{)}^{N}\to\infty,$

if $b$ is sufficiently large, since $\tfrac{\nu-1}{2\log\nu}<\nu-1$.

Consider now $\tfrac{\nu-1}{2\log\nu}<\lim\tfrac{N}{\log M}<\nu-1$. Since
$\min_{\nu>3}\tfrac{\nu-1}{2\log\nu}=\tfrac{4-1}{2\log 4}>1$ (notice that
$\tfrac{3-1}{2\log 3}<1$), we use middle remainder from (3.35) to obtain

$\mathcal{R}_{n}=\tfrac{\nu^{2N}}{M^{\nu-1}}\exp\Bigl{(}-\tfrac{\lambda\log^{2}N}{4\nu}\Bigr{)}+\Bigl{(}\tfrac{\nu
Ne^{O(b^{-2})}}{e\log M}\Bigr{)}^{N}.$

Therefore

(3.37)
$\frac{\mathcal{R}_{n}}{\tfrac{\nu^{n}}{M^{\nu-1}}}=\exp\Bigl{(}-\tfrac{\lambda\log^{2}N}{4\nu}\Bigr{)}+\Bigl{(}\tfrac{e^{(\nu-1)\eta_{n}}+O(b^{-2})}{\nu
e\eta_{n}}\Bigr{)}^{N},\quad\eta_{n}:=\tfrac{\log M}{N},$

i.e.
$\lim\eta_{n}\in\bigl{(}\tfrac{1}{\nu-1},\tfrac{2\log\nu}{\nu-1}\bigr{)}$. The
function $f_{\nu}(\eta):=\tfrac{e^{(\nu-1)\eta}}{\nu e\eta}$ increases with
$\eta>(\nu-1)^{-1}$, and

$f_{\nu}((\nu-1)^{-1})=1-\tfrac{1}{\nu}<1,\quad
f_{\nu}\bigl{(}\tfrac{2\log\nu}{\nu-1}\bigr{)}=\tfrac{\nu(\nu-1)}{2e\log\nu}>1,\,\,\forall\nu>3.$

So, there exists a unique root
$\eta(\nu)\in\bigl{(}\tfrac{1}{\nu-1},\tfrac{2\log\nu}{\nu-1}\bigr{)}$ of
$f_{\nu}(\eta)-1$. Using (3.37), we conclude that for $\nu>3$ the equation
(3.36) holds for $\tfrac{1}{\eta(\nu)}<\lim\tfrac{N}{\log M}<\nu-1$, if $b$ is
chosen large enough.

Finally, like the case $\nu=3$, $\lim\mathbb{E}[Z_{n}]=0$ if
$\lim\tfrac{N}{\log M}<\tfrac{1}{\log\nu}$. This completes the proof of
Theorem 3.1.

∎

##  4\. Second order moment of the number of perfect partitions

From Theorem 3.1 we know that, for $\lim\tfrac{n}{\log M}<\tfrac{2}{\log\nu}$,
we have $\mathbb{E}\bigl{[}Z_{n}\bigr{]}\to 0$, so that
$\mathbb{P}(Z_{n}>0)\leq\mathbb{E}[Z_{n}]\to 0$. Furthermore, we stated the
conditions on $\lim\tfrac{n}{\log M}$ under which
$\lim\mathbb{E}[Z_{n}]=\infty$. These conditions make it plausible, but
certainly do not imply, that $\mathbb{P}(Z_{n}>0)$ approaches $1$, or even
that $\lim\mathbb{P}(Z_{n}>0)>0$. In general, if the first order moment grows
very fast, it may well portend that the standard deviation grows even faster.

######  Theorem 4.1.

Suppose that $\lim\tfrac{n}{\log
M}>\tfrac{2(\nu-1)}{\log[(1-2\nu^{-2})^{-1}]}$. Then with the limiting
probability $\gtrsim(1+\nu^{2})^{-1}$, $Z_{n}$ is of order
$\mathbb{E}[Z_{n}]$, i.e. the number of perfect partitions is exponentially
large.

Note. The limiting probability is certainly below

$\tfrac{1}{\nu}\\!=\\!\lim\mathbb{P}\Bigl{(}\sum_{j\in[n]}X_{j}\\!\\!\equiv
0(\text{mod }\nu)\Bigr{)}.$

###### Proof.

By Lemma 2.1, we have

(4.1)
$\mathbb{E}[Z_{n}^{2}]=\frac{1}{(2\pi)^{2\nu}}\\!\\!\\!\int\limits_{\mathbb{x},\mathbb{x}^{\prime}}\mathbb{E}^{n}\bigl{[}f(\mathbb{x},X)\overline{f(\mathbb{x}^{\prime},X)}\bigr{]}\,\,d\mathbb{x}d\mathbb{x}^{\prime}.$

Here, with $\phi(y)=\mathbb{E}[e^{iyX}]$, we have

(4.2)
$\mathbb{E}\bigl{[}f(\mathbb{x},X)\overline{f(\mathbb{x}^{\prime},X)}\bigr{]}=\mathbb{E}\biggl{[}\biggl{(}\sum_{\alpha\in[\nu]}\exp(iy_{\alpha}(\mathbb{x})X)\biggr{)}\biggl{(}\sum_{\beta\in[\nu]}\exp(-iy_{\beta}(\mathbb{x}^{\prime})X)\biggr{)}\biggl{]}\\\
=\mathbb{E}\biggl{[}\sum_{\alpha,\beta\in[\nu]}\exp\bigl{(}i(y_{\alpha}(\mathbb{x})-y_{\beta}(\mathbb{x}^{\prime}))X)\biggr{]}=\sum_{\alpha,\beta\in[\nu]}\phi\bigl{(}y_{\alpha}(\mathbb{x})-y_{\beta}(\mathbb{x}^{\prime})\bigr{)}.$

Let $\varepsilon\in(0,\nu^{-2})$, and introduce

$D_{\varepsilon}=\Bigl{\\{}\mathbb{x},\mathbb{x}^{\prime}\in[-\pi,\pi]^{\nu}:\min_{\alpha,\beta\in[\nu]}\big{|}\phi(y_{\alpha}(\mathbb{x})-y_{\beta}(\mathbb{x}^{\prime}))\big{|}\leq
1-\varepsilon\nu^{2}\Bigr{\\}}.$

For $(\mathbb{x},\mathbb{x}^{\prime})\in D_{\varepsilon}$, we have

$\sum_{\alpha,\beta\in[\nu]}|\phi\bigl{(}y_{\alpha}(\mathbb{x})-y_{\beta}(\mathbb{x}^{\prime})\bigr{)}|\leq(1-\varepsilon\nu^{2})+\nu^{2}-1=\nu^{2}(1-\varepsilon).$

So, $\mathcal{E}[Z_{n}^{2};D_{\varepsilon}]$, the contribution of
$D_{\varepsilon}$ to $\mathbb{E}[Z_{n}^{2}]$, is at most
$\nu^{2n}(1-\varepsilon)^{n}$.

Let $(\mathbb{x},\mathbb{x}^{\prime})\in D_{\varepsilon}^{c}$, so that
$\big{|}\phi(y_{\alpha}(\mathbb{x})-y_{\beta}(\mathbb{x}^{\prime}))\big{|}>1-\varepsilon\nu^{2}$
for all $\alpha,\,\beta$. If
$y=y_{\alpha,\beta}:=y_{\alpha}(\mathbb{x})-y_{\beta}(\mathbb{x}^{\prime})\neq
k\pi$, $k$ even, then

$|\phi(y)|=\bigg{|}\tfrac{e^{iy}(e^{iMy}-1)}{M(e^{iy}-1)}\bigg{|}=\tfrac{\bigl{(}1-\cos(My)\bigr{)}^{1/2}}{M(1-\cos
y)^{1/2}}=\bigg{|}\tfrac{\sin(My/2)}{M\sin(y/2)}\biggr{|}>1-\varepsilon\nu^{2}.\\\
$

Let $k_{\alpha,\beta}(\mathbb{x},\mathbb{x}^{\prime})\pi$ be the even multiple
of $\pi$ closest to $y_{\alpha}(\mathbb{x})-y_{\beta}(\mathbb{x}^{\prime})$,
and set
$z_{\alpha,\beta}(\mathbb{x},\mathbb{x}^{\prime})=y_{\alpha}(\mathbb{x})-y_{\beta}(\mathbb{x}^{\prime})-k_{\alpha,\beta}(\mathbb{x},\mathbb{x}^{\prime})\pi$;
then $|z_{\alpha,\beta}(\mathbb{x},\mathbb{x}^{\prime})|\leq\pi$, and
$\phi(y_{\alpha}(\mathbb{x})-y_{\beta}(\mathbb{x}^{\prime}))=\phi(z_{\alpha,\beta}(\mathbb{x},\mathbb{x}^{\prime}))$.
Therefore

$1-\varepsilon\nu^{2}\leq|\phi(y_{\alpha}(\mathbb{x})-y_{\beta}(\mathbb{x}^{\prime}))|=|\phi(z_{\alpha,\beta}(\mathbb{x},\mathbb{x}^{\prime}))|\\\
\leq\frac{1}{M|\sin(z_{\alpha,\beta}(\mathbb{x},\mathbb{x}^{\prime})/2)|}\leq\tfrac{\pi}{M|z_{\alpha,\beta}(\mathbb{x},\mathbb{x}^{\prime})|},$

whence

$|y_{\alpha}(\mathbb{x})-y_{\beta}(\mathbb{x}^{\prime})-k_{\alpha,\beta}(\mathbb{x},\mathbb{x}^{\prime})\pi|=|z_{\alpha,\beta}(\mathbb{x},\mathbb{x}^{\prime})|\leq\tfrac{\pi}{M(1-\varepsilon\nu^{2})}=O(M^{-1}).$

Since
$\sum_{\alpha}y_{\alpha}(\mathbb{x})=\sum_{\beta}y_{\beta}(\mathbb{x}^{\prime})=0$,
we obtain then

$\displaystyle
y_{\alpha}(\mathbb{x})-\tfrac{\pi}{\nu}k_{\alpha}(\mathbb{x},\mathbb{x}^{\prime})=O(M^{-1}),\quad
k_{\alpha}(\mathbb{x},\mathbb{x}^{\prime}):=\sum_{\beta}k_{\alpha,\beta}(\mathbb{x},\mathbb{x}^{\prime}),$
$\displaystyle
y_{\beta}(\mathbb{x}^{\prime})-\tfrac{\pi}{\nu}\kappa_{\beta}(\mathbb{x},\mathbb{x}^{\prime})=O(M^{-1}),\quad\kappa_{\beta}(\mathbb{x},\mathbb{x}^{\prime}):=\sum_{\alpha}k_{\alpha,\beta}(\mathbb{x},\mathbb{x}^{\prime}).$

Since $\nu$ is fixed and $M\to\infty$,
$\tfrac{\pi}{\nu}k_{\alpha}(\mathbb{x},\mathbb{x}^{\prime})$
($\tfrac{\pi}{\nu}\kappa_{\beta}(\mathbb{x},\mathbb{x}^{\prime})$ resp.) is
again an even multiple of $\tfrac{\pi}{\nu}$ closest to
$y_{\alpha}(\mathbb{x})$ ($y_{\beta}(\mathbb{x}^{\prime})$ resp.), whence
$k_{\alpha}(\mathbb{x},\mathbb{x}^{\prime})$
($\kappa_{\beta}(\mathbb{x},\mathbb{x}^{\prime})$ resp.) depends only on
$\mathbb{x}$ (on $\mathbb{x}^{\prime}$ resp.). Combining the last three
equations, and again using $\sum_{\alpha}y_{\alpha}(\mathbb{x})=0$,
$\sum_{\beta}y_{\beta}(\mathbb{x}^{\prime})=0$, we obtain

$\displaystyle\tfrac{\pi}{\nu}\cdot(k_{\alpha}(\mathbb{x})-\kappa_{\beta}(\mathbb{x}^{\prime}))=\pi
k_{\alpha,\beta}(\mathbb{x},\mathbb{x}^{\prime})+O(M^{-1}),$
$\displaystyle\sum_{\alpha}k_{\alpha}(\mathbb{x})=O(M^{-1}),\quad\sum_{\beta}\kappa_{\beta}(\mathbb{x}^{\prime})=O(M^{-1}),$

implying that for $M$ large

$k_{\alpha,\beta}(\mathbb{x},\mathbb{x}^{\prime})=\tfrac{1}{\nu}(k_{\alpha}(\mathbb{x})-\kappa_{\beta}(\mathbb{x}^{\prime})),\quad\sum_{\alpha}k_{\alpha}(\mathbb{x})=\sum_{\beta}\kappa_{\beta}(\mathbb{x}^{\prime})=0.$

(In particular, all $\nu^{2}$ differences
$k_{\alpha}(\mathbb{x})-\kappa_{\beta}(\mathbb{x}^{\prime})$ are divisible by
$2\nu$.) The first identity above implies that
$z(\mathbb{x},\mathbb{x}^{\prime})=M^{-1}\bigl{(}\xi_{\alpha}(\mathbb{x})-\eta_{\beta}(\mathbb{x}^{\prime})\bigr{)}$,
where

$\xi_{\alpha}(\mathbb{x}):=M\bigl{(}y_{\alpha}(\mathbb{x})-\tfrac{\pi}{\nu}k_{\alpha}(\mathbb{x})\bigr{)},\quad\eta_{\beta}(\mathbb{x}^{\prime}):=M\bigl{(}y_{\beta}(\mathbb{x}^{\prime})-\tfrac{\pi}{\nu}k_{\beta}(\mathbb{x}^{\prime})\bigr{)},$

and by the second identity, $\sum_{\alpha}\xi_{\alpha}(\mathbb{x})=0$,
$\sum_{\beta}\eta_{\beta}(\mathbb{x}^{\prime})=0$. So,

$\phi(z_{\alpha,\beta}(\mathbb{x},\mathbb{x}^{\prime}))=\phi\bigl{(}M^{-1}(\xi_{\alpha}(\mathbb{x})-\eta_{\beta}(\mathbb{x}^{\prime}))\bigr{)}.$

and $|\xi_{\alpha}(\mathbb{x})-\eta_{\beta}(\mathbb{x}^{\prime})|$ is
uniformly bounded for $(\mathbb{x},\mathbb{x}^{\prime})\in
D_{\varepsilon}^{c}$. Now, for each $b>0$, there exists $\lambda=\lambda(b)>0$
such that $u^{-1}|\sin u|\in[1-2\lambda u^{2},1-\lambda^{2}]$ for $u\in(0,b]$.
Since

$|\phi(z)|=\biggl{|}\tfrac{\sin(Mz/2)}{Mz/2}\biggr{|}\cdot\biggl{|}\tfrac{z/2}{\sin(z/2)}\biggr{|},$

we see then that, for $(\mathbb{x},\mathbb{x}^{\prime})\in
D_{\varepsilon}^{c}$ and an absolute constant $\lambda^{\prime}>0$,

(4.3)
$\sum_{\alpha,\beta}|\phi\bigl{(}y_{\alpha}(\mathbb{x})-y_{\beta}(\mathbb{x}^{\prime})\bigr{)}|\leq\sum_{\alpha,\beta}\Bigl{(}1-\lambda^{\prime}(\xi_{\alpha}(\mathbb{x})-\eta_{\beta}(\mathbb{x}^{\prime}))^{2}\Bigr{)}\\\
\leq\nu^{2}\exp\biggl{(}-\tfrac{\lambda^{\prime}}{\nu^{2}}\sum_{\alpha,\beta}(\xi_{\alpha}(\mathbb{x})-\eta_{\beta}(\mathbb{x}^{\prime}))^{2}\biggr{)}\\\
=\nu^{2}\exp\Bigl{(}-\tfrac{\lambda^{\prime}}{\nu^{2}}\bigl{(}\|\boldsymbol{\xi}(\mathbb{x})\|^{2}+\|\boldsymbol{\eta}(\mathbb{x}^{\prime})\|^{2}\bigr{)}\Bigr{)},$

since
$\sum_{\alpha}\xi_{\alpha}(\mathbb{x})=\sum_{\beta}\eta_{\beta}(\mathbb{x}^{\prime})=0$.

Let $\mathcal{E}[Z_{n}^{2};D_{\varepsilon}^{c}]$ be the contribution to
$\mathbb{E}[Z_{n}^{2}]$ from $(\mathbb{x},\mathbb{x}^{\prime})\in
D_{\varepsilon}^{c}$ such that

$\max\bigl{\\{}\|\boldsymbol{\xi}(\mathbb{x})\|,\,\|\boldsymbol{\eta}(\mathbb{x}^{\prime})\|\bigr{\\}}\geq\tfrac{\log
n}{n^{1/2}}.$

Using (4.3), similarly to the part (ii) of the proof of Lemma 3.4, we obtain

$\mathcal{E}[Z_{n}^{2};D_{\varepsilon}^{c}]\leq
c_{1}(\nu)\tfrac{\nu^{2n}}{\lambda^{\prime}M^{2(\nu-1)}}\exp\Bigl{(}-\tfrac{\lambda^{\prime}\log^{2}n}{\nu^{2}}\Bigr{)}.$

Consequently

(4.4)
$\displaystyle\mathcal{E}[Z_{n}^{2};D_{\varepsilon}]+\mathcal{E}[Z_{n}^{2};D_{\varepsilon}^{c}]$
$\displaystyle=O\biggl{(}\nu^{2n}(1-\varepsilon)^{n}+\tfrac{\nu^{2n}}{\lambda^{\prime}M^{2(\nu-1)}}\exp\Bigl{(}-\tfrac{\lambda^{\prime}\log^{2}n}{\nu^{2}}\Bigr{)}\biggr{)}$
$\displaystyle=O\biggl{(}\tfrac{\nu^{2n}}{\lambda^{\prime}M^{2(\nu-1)}}\exp\Bigl{(}-\tfrac{\lambda^{\prime}\log^{2}n}{\nu^{2}}\Bigr{)}\biggr{)},$

provided that

(4.5) $\lim\tfrac{n}{\log M}>\frac{2(\nu-1)}{\log\tfrac{1}{1-\nu^{-2}}}.$

It remains to sharply estimate $\mathcal{E}[Z_{n}^{2};\mathcal{C}]$, the
contribution to $\mathbb{E}[Z_{n}^{2}]$ from

$\mathcal{C}^{*}:=\Bigl{\\{}(\mathbb{x},\mathbb{x}^{\prime})\in
D_{\varepsilon}^{c}:\max\bigl{\\{}\|\boldsymbol{\xi}(\mathbb{x})\|,\,\|\boldsymbol{\eta}(\mathbb{x}^{\prime})\|\bigr{\\}}\leq\tfrac{\log
n}{n^{1/2}}\Bigr{\\}}.$

Analogously to $\mathbb{E}[Z_{n}]$, (see the part (III) of the proof of
Theorem 3.1), $\mathcal{C}$ is the disjoint union of
$\mathcal{C}^{*}_{\mathbb{k},\boldsymbol{\kappa}}$, over all pairs
$\\{\mathbb{k},\boldsymbol{\kappa}\\}$ of $\nu$-long even tuples
$\mathbb{k}=\\{k_{\alpha}\\}$, $\boldsymbol{\kappa}=\\{\kappa_{\beta}\\}$,
with $\sum_{\alpha}k_{\alpha}=\sum_{\beta}\kappa_{\beta}=0$,
$k_{\alpha}-\kappa_{\beta}\equiv 0(\text{mod }2\nu)$, and

$\displaystyle\mathcal{C}^{*}_{\mathbb{k},\boldsymbol{\kappa}}=\Bigl{\\{}(\mathbb{x},\mathbb{x}^{\prime})\in
D_{\varepsilon}^{c}:$
$\displaystyle\max\bigl{\\{}\|\boldsymbol{\xi}(\mathbb{x})\|,\|\boldsymbol{\eta}(\mathbb{x}^{\prime})\|\bigr{\\}}$
$\displaystyle\leq\tfrac{\log
n}{n^{1/2}},\,k_{\alpha}(\mathbb{x})\\!=k_{\alpha},\,\kappa_{\beta}(\mathbb{x}^{\prime})\\!=\\!\kappa_{\beta}\Bigr{\\}}.$

Geometrically, $\mathcal{C}^{*}_{\mathbb{k},\boldsymbol{\kappa}}$ is the
Cartesian product of two thin $\nu$-dimensional cylinders, enclosing
respectively the line $\mathcal{L}^{*}_{\mathbb{k}}$ and the line
$\mathcal{L}^{*}_{\boldsymbol{\kappa}}$, given by the parametric equations

(4.6)
$x_{\alpha}(t)=\nu^{-1}\bigl{(}t+\tfrac{\pi}{\nu}k_{\alpha}\bigr{)},\,\alpha\in[\nu],\quad
x^{\prime}_{\beta}(t^{\prime})=\nu^{-1}\bigl{(}t^{\prime}+\tfrac{\pi}{\nu}\kappa_{\beta}\bigr{)},\,\beta\in[\nu].$

As in the case of $\mathbb{E}[Z_{n}]$, the dominant contributors to
$\mathbb{E}[Z_{n}^{2}]$ are the pairs
$\\{\mathcal{L}^{*}_{\mathbb{k}},\mathcal{L}^{*}_{\boldsymbol{\kappa}}\\}$
that contain interior points of their respective cubes $[-\pi,\pi]^{\nu}$.
However this time we need to consider only the pairs for which the differences
$k_{\alpha}-\kappa_{\beta}$ are all divisible by $2\nu$. Each of the cross-
sections of the two cylinders formed by planes $\sum_{\alpha}x_{\alpha}=t$,
and $\sum_{\beta}x^{\prime}_{\beta}=t^{\prime}$ respectively, is the
$(\nu-1)$-dimensional sphere of radius $r_{n}:=(M\nu)^{-1}n^{-1/2}\log n$,
coming from

$\displaystyle\|\mathbb{x}-\mathbb{x}(t)\|^{2}$
$\displaystyle=\tfrac{1}{(M\nu)^{2}}\sum_{\alpha}\xi_{\alpha}^{2}(\mathbb{x})\leq\tfrac{\log^{2}n}{(M\nu)^{2}n},$
$\displaystyle\|\mathbb{x}^{\prime}-\mathbb{x}^{\prime}(t^{\prime})\|^{2}$
$\displaystyle=\tfrac{1}{(M\nu)^{2}}\sum_{\beta}\eta_{\beta}^{2}(\mathbb{x}^{\prime})\leq\tfrac{\log^{2}n}{(M\nu)^{2}n}.$

For
$(\mathbb{x},\mathbb{x}^{\prime})\in\mathcal{C}^{*}_{\mathbb{k},\boldsymbol{\kappa}}$,
we have

$\phi(y_{\alpha}(\mathbb{x})-y_{\beta}(\mathbb{x}^{\prime}))=\phi(z_{\alpha,\beta}(\mathbb{x},\mathbb{x}^{\prime}))=\phi\bigl{(}M^{-1}(\xi_{\alpha}(\mathbb{x})-\eta_{\beta}(\mathbb{x}^{\prime}))\bigr{)}\\\
=1+i\tfrac{\mathbb{E}[X]}{M}(\xi_{\alpha}(\mathbb{x})-\eta_{\beta}(\mathbb{x}^{\prime}))-\tfrac{\mathbb{E}[X^{2}]}{2M^{2}}(\xi_{\alpha}(\mathbb{x})-\eta_{\beta}(\mathbb{x}^{\prime}))^{2}+O\bigl{(}|\xi_{\alpha}(\mathbb{x})-\eta_{\beta}(\mathbb{x}^{\prime})|^{3}\bigr{)}.$

Summing this equation over $\alpha,\beta\in[\nu]$, and using
$\sum_{\alpha}\xi_{\alpha}(\mathbb{x})=0$,
$\sum_{\beta}\eta_{\beta}(\mathbb{x}^{\prime})=0$, we transform (4.2) into

$\mathbb{E}\bigl{[}f(\mathbb{x},X)\overline{f(\mathbb{x}^{\prime},X)}\bigr{]}=\nu^{2}-\tfrac{\mathbb{E}[X^{2}]}{2M^{2}}\bigl{(}\|\boldsymbol{\xi}(\mathbb{x})\|^{2}+\|\boldsymbol{\eta}(\mathbb{x}^{\prime})\|^{2}\bigr{)}\\\
\quad+O\bigl{(}\|\boldsymbol{\xi}(\mathbb{x})\|^{3}+\|\boldsymbol{\eta}(\mathbb{x}^{\prime})\|^{3}\bigr{)}\\\
=\nu^{2}\Bigl{(}1-\tfrac{M^{2}c_{M}}{2}\bigl{(}\|\mathbb{x}-\mathbb{x}(t)\|^{2}+\|\mathbb{x}^{\prime}-\mathbb{x}^{\prime}(t^{\prime})\|^{2}\bigr{)}\\\
+O\bigl{(}M^{3}\bigl{(}\|\mathbb{x}-\mathbb{x}(t)\|^{3}+\|\mathbb{x}^{\prime}-\mathbb{x}^{\prime}(t^{\prime})\|^{3}\bigr{)}\Bigr{)}\\\
=\nu^{2}\exp\Bigl{(}-\tfrac{M^{2}c_{M}}{2}\bigl{(}\|\mathbb{x}-\mathbb{x}(t)\|^{2}+\|\mathbb{x}^{\prime}-\mathbb{x}^{\prime}(t^{\prime})\|^{2}\bigr{)}+O(n^{-3/2}\log^{3}n)\Bigr{)}.$

So

$\mathbb{E}^{n}\bigl{[}f(\mathbb{x},X)\overline{f(\mathbb{x}^{\prime},X)}\bigr{]}\\\
=\nu^{2n}\exp\Bigl{(}-\tfrac{M^{2}nc_{M}}{2}\bigl{(}\|\mathbb{x}-\mathbb{x}(t)\|^{2}+\|\mathbb{x}^{\prime}-\mathbb{x}^{\prime}(t^{\prime})\|^{2}\bigr{)}+O(n^{-1/2}\log^{3}n)\Bigr{)}.$

So
$\mathcal{E}\bigl{[}Z_{n}^{2};\mathcal{C}^{*}_{\mathbb{k},\boldsymbol{\kappa}}\bigr{]}$,
the contribution of $\mathcal{C}^{*}_{\mathbb{k},\boldsymbol{\kappa}}$ to
$\mathbb{E}[Z_{n}^{2}]$, is given by

$\mathcal{E}\bigl{[}Z_{n}^{2};\mathcal{C}^{*}_{\mathbb{k},\boldsymbol{\kappa}}\bigr{]}=(1+o(1))\tfrac{\nu^{2n}L^{*}(\mathbb{k})L^{*}(\boldsymbol{\kappa})}{(2\pi)^{2\nu}(M\nu)^{2(\nu-1)}}\biggl{(}\int_{\rho\geq
0}e^{-\tfrac{c_{M}n}{2\nu}\rho^{2}}\,dV(\rho)\biggr{)}^{2},$

$V(\rho)$ being the volume of $(\nu-1)$-dimensional sphere of radius $\rho$.
Here $L^{*}(\mathbb{k})$ and $L^{*}(\boldsymbol{\kappa})$ are the lengths of
segments of $\mathcal{L}^{*}(\mathbb{k})$ and
$\mathcal{L}^{*}(\boldsymbol{\kappa})$ within the respective cubes
$[-\pi,\pi]^{\nu}$. Summing over all admissible pairs
$\\{\mathbb{k},\boldsymbol{\kappa}\\}$, we have

$\mathcal{E}\bigl{[}Z_{n}^{2};\mathcal{C}^{*}\bigr{]}\\!=\\!(1+o(1))\biggl{(}\\!\tfrac{\nu^{n}}{(2\pi)^{\nu}(M\nu)^{\nu-1}}\int_{\rho\geq
0}e^{-\tfrac{c_{M}n}{2\nu}\rho^{2}}\,dV(\rho)\\!\biggr{)}^{2}\sum_{\\{\mathbb{k},\boldsymbol{\kappa}\\}}\\!L^{*}(\mathbb{k})L^{*}(\boldsymbol{\kappa}).$

We upper bound the last product by $(L^{*})^{2}$,
$L^{*}:=\sum_{\mathbb{k}}L^{*}(\mathbb{k})$, thus replacing the condition that
all $k_{\alpha}-\kappa_{\beta}$ are divisible by $2\nu$ with the weaker
condition that marginally all the differences $k_{\alpha}-k_{\alpha^{\prime}}$
and all the differences $\kappa_{\beta}-\kappa_{\beta^{\prime}}$ are divisible
by $2\nu$.

By (4.6), for the interior segment of $\mathcal{L}^{*}(\mathbb{k})$ we have

$-\pi\bigl{(}\nu+\tfrac{\min
k_{\alpha}}{\nu}\bigr{)}<t<\pi\bigl{(}\nu-\tfrac{\max
k_{\alpha}}{\nu}\bigr{)}.$

So,

$L^{*}(\mathbb{k})=\pi d^{*}(\mathbb{k})\nu^{-1/2},\quad
d^{*}(\mathbb{k}):=2\nu-\tfrac{r}{\nu},\,\,r:=\max k_{\alpha}-\min
k_{\alpha},$

and $d^{*}(\mathbb{k})>0$ if either $k_{\alpha}\equiv 0$, or
$\tfrac{r}{2\nu}\in[\nu-1]$. Consequently

$\displaystyle\sum_{\mathbb{k}}d^{*}(\mathbb{k})$
$\displaystyle=2\nu(1+\mathcal{M}_{1}^{*})-\tfrac{1}{\nu}\mathcal{M}_{2}^{*},$
$\displaystyle\mathcal{M}_{1}^{*}$
$\displaystyle=\sum_{\tfrac{r}{2\nu}\in[\nu-1]}\mathcal{N}^{*}(r),\quad\mathcal{M}_{2}^{*}=\sum_{\tfrac{r}{2\nu}\in[\nu-1]}r\mathcal{N}^{*}(r),$

Here, following closely the line enumeration in the part (I) of the proof of
Theorem 3.1, we have

$\displaystyle\quad\quad\quad\mathcal{N}^{*}(r)=\sum_{\text{even }a\leq
0}[\zeta^{-a\nu}]\mathcal{F}^{*}_{r}(\zeta),\quad\tfrac{r}{2\nu}\in[\nu-1],$
$\displaystyle\mathcal{F}^{*}_{r}(\zeta)=\bigl{(}\tfrac{1-\zeta^{r+2\nu}}{1-\zeta^{2\nu}}\bigr{)}^{\nu}-\bigl{(}\tfrac{1-\zeta^{r}}{1-\zeta^{2\nu}}\bigr{)}^{\nu}-\bigl{(}\tfrac{\zeta^{2\nu}-\zeta^{r+2\nu}}{1-\zeta^{2\nu}}\bigr{)}^{\nu}+\bigl{(}\tfrac{\zeta^{2\nu}-\zeta^{r}}{1-\zeta^{2\nu}}\bigr{)}^{\nu}.$

So

$\displaystyle\mathcal{M}_{1}^{*}$ $\displaystyle=\sum_{\text{even }a\leq
0}[\zeta^{-a\nu}]\sum_{\tfrac{r}{2\nu}\in[\nu-1]}\mathcal{F}^{*}_{r}(\zeta)$
$\displaystyle=\sum_{\text{even }a\leq
0}[\zeta^{-a\nu}]\Bigl{(}\bigl{(}\tfrac{1-\zeta^{2\nu^{2}}}{1-\zeta^{2\nu}}\bigr{)}^{\nu}-\bigl{(}\tfrac{\zeta^{2\nu}-\zeta^{2\nu^{2}}}{1-\zeta^{2\nu}}\bigr{)}^{\nu}-1\Bigr{)}$
$\displaystyle=\sum_{\alpha\geq
0}[t^{\alpha}]\Bigl{[}\bigl{(}\tfrac{1-t^{\nu}}{1-t}\bigr{)}^{\nu}-\bigl{(}\tfrac{t-t^{\nu}}{1-t}\bigr{)}^{\nu}-1\Bigr{]}$
$\displaystyle=\lim_{t\to
1}\Bigl{[}\bigl{(}\tfrac{1-t^{\nu}}{1-t}\bigr{)}^{\nu}-\bigl{(}\tfrac{t-t^{\nu}}{1-t}\bigr{)}^{\nu}-1\Bigr{]}=\nu^{\nu}-(\nu-1)^{\nu}-1.$

Next, with a bit of telescoping again,

$\sum_{\tfrac{r}{2\nu}\in[\nu-1]}r\mathcal{F}^{*}_{r}(\zeta)=2\nu(\nu-1)\bigl{(}\tfrac{1-\zeta^{2\nu^{2}}}{1-\zeta^{2\nu}}\bigr{)}^{\nu}\\\
-(2\nu(\nu-1)\zeta^{2\nu^{2}}+2\nu)\bigl{(}\tfrac{1-\zeta^{2\nu(\nu-1)}}{1-\zeta^{2\nu}}\bigr{)}^{\nu}\\\
+2\nu(\zeta^{2\nu^{2}}-1)\sum_{j=1}^{\nu-2}\bigl{(}\tfrac{1-\zeta^{2\nu
j}}{1-\zeta^{2\nu}}\bigr{)}^{\nu}=:S^{*}(\zeta^{2\nu}).$

Consequently,

$\displaystyle\mathcal{M}_{2}^{*}$ $\displaystyle=\sum_{\text{even }a\leq
0}[\zeta^{-a\nu}]\sum_{\tfrac{r}{2\nu}\in[\nu-1]}r\mathcal{F}^{*}_{r}(\zeta)=\sum_{\alpha\geq
0}[t^{\alpha}]S^{*}(t)$ $\displaystyle=\lim_{t\to
1}S^{*}(t)=2\nu(\nu-1)\nu^{\nu}-2\nu^{2}(\nu-1)^{\nu}.$

Therefore

$\displaystyle\sum_{\mathbb{k}}d^{*}(\mathbb{k})$
$\displaystyle=2\nu(1+\mathcal{M}_{1}^{*})-\tfrac{1}{\nu}\mathcal{M}_{2}^{*}$
$\displaystyle=2\nu(\nu^{\nu}-(\nu-1)^{\nu})-2(\nu-1)\nu^{\nu}+2\nu(\nu-1)^{\nu}=2\nu^{\nu},$

so that $L^{*}(\mathbb{k})=2\pi\nu^{\nu-1/2}$. So,

$\displaystyle\mathcal{E}\bigl{[}Z_{n}^{2};\mathcal{C}^{*}\bigr{]}\\!$
$\displaystyle\leq\\!(1+o(1))\biggl{(}\\!\tfrac{\nu^{n}\cdot
2\pi\nu^{\nu-1/2}}{(2\pi)^{\nu}(M\nu)^{\nu-1}}\int_{\rho\geq
0}e^{-\tfrac{c_{M}n}{2\nu}\rho^{2}}\,dV(\rho)\\!\biggr{)}^{2}$
$\displaystyle=(1+o(1))\left(\tfrac{\nu^{n}}{M^{\nu}-1}\cdot\frac{\nu^{\nu-1/2}}{(2\pi\nu
c_{M}n)^{\tfrac{\nu-1}{2}}}\right)^{2}.$

In combination with (4.4), and (3.34), this leads to

$\displaystyle\mathbb{E}[Z_{n}^{2}]$
$\displaystyle\leq(1+o(1))\left(\tfrac{\nu^{n}}{M^{\nu}-1}\cdot\frac{\nu^{\nu-1/2}}{(2\pi\nu
c_{M}n)^{\tfrac{\nu-1}{2}}}\right)^{2}$
$\displaystyle=(1+o(1))\nu^{2}\mathbb{E}^{2}[Z_{n}],$

provided that $\lim\tfrac{n}{\log
M}>\tfrac{2(\nu-1)}{\log[(1-2\nu^{-2})^{-1}]}$. By Cantellli’s inequality
(Billingsley [2]),

$\liminf\mathbb{P}\bigl{(}Z_{n}\geq\delta\mathbb{E}[Z_{n}]\bigr{)}\geq\lim\tfrac{(1-\delta)^{2}}{(1-\delta)^{2}+\tfrac{\mathbb{E}[Z^{2}_{n}]}{\mathbb{E}^{2}[Z_{n}]}}\geq\tfrac{(1-\delta)^{2}}{(1-\delta)^{2}+\nu^{2}},\quad\forall\,\delta\in(0,1).\\\
$

∎

Acknowledgment. It is my pleasure to thank the participants of combinatorial
probability seminar at Ohio State University for encouraging discussion of
this study. I owe a debt of gratitude to Huseyin Acan for alerting me to a
possibility of an oversight in the preliminary draft, and to Hoi Nguyen for
pinpointing it with surgical precision. I am grateful to George Varghese for
drawing my attention in Summer 2021 to the perfect multiway partitions. The
thought-provoking paper that George and his son Tim wrote on the subject
slowly but surely pulled me in.

## References

  * [1] H. Acan, Private communication (2022).
  * [2] P. Billingsley, Probability and Measure, 3rd edn, Wiley (1995).
  * [3] C. Borgs, J. Chayes, and B. Pittel, Phase transition and finite-size scaling for the integer partitioning problem, Random Struct. Alg., 19 (2001) 247–288.
  * [4] C. Borgs, J. Chayes, S. Mertens, and B. Pittel, Phase transition for the constrained integer partitioning problem, Random Struct. Alg., 24 (2004) 315–380.
  * [5] A. Bovier and I. Kurkova, Poisson convergence in the restricted k-partitioning problem, Random Struct. Alg,. 30 (2007) 505–531.
  * [6] I. Gent and T. Walsh, Phase transitions and annealed theories: number partitioning as a case study, Proceedings of 12th European Conference on Artificial Intelligence (1996) 170–174.
  * [7] R. Graham, Bounds on multiprocessing timing anomalies, SIAM J. Appl. Math. 17 (1969) 416–429.
  * [8] B. Hayes, The easiest hard problem, American Scientist, 90 (2002) 113–117.
  * [9] N. Karmarkar, R. Karp, G. Lueker, and Odlyzko, Probabilistic analysis of optimum partitioning, J. App. Prob., 23 (1986) 626–645.
  * [10] S. Mertens,  A physicist’s approach to number partitioning, Theor. Comp. Sci, 265 (2001) 79–108.
  * [11] T. Varghese and G. Varghese, The stash-repair method applied to partitionable numbers, Private communication, (2021).
  * [12] Partition problem. https://en.wikipedia.org/wiki/Partition problem
  * [13] B. Yakir, The differencing algorithm LDM for partitioning: a proof of a conjecture of Karmarkar and Karp, Math. Oper. Res. 21 (1996) 85–99.